生院第九章_2_课案.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 含s的块是循环中所有出口结点的必经结点 出口结点是有后继不在循环中的结点 只要循环不是无限循环，则所有出口的必经结点一定会执行 * 循环中没有其它语句对x定值 如果x是只赋值一次的临时变量，这个条件肯定满足 * 循环中x的引用仅由s到达 如果x是临时变量，这个条件一般也满足 * * * * * * * * * 代码外提算法的讨论 条件(2a)和(2b)保证在s中计算的x值必定是L任何出口的x的定值 条件(2c)保证L中任何x的引用在外提前后x都引用s计算的x值 代码外提至少不会增加程序的运行时间（因为外提的代码在每次进入循环时至少要执行一次），而且可能在很大程度上减少运行时间 代码外提后数据流信息的维护 上述代码外提的算法并没有改变ud链信息 根据条件(2a)，(2b)和(2c) 原来由s的定值到达的引用，在s移动位置后，定值仍然能到达 s应用的变量的定值 在循环L外，可以到达前置块 原来在循环L内，由步骤(3)知道，它们已经移到前置块s的前面 ud链的维护 通过指针间址，只需改变指向s的指针即可 直接使用语句指针，则需要根据du链改变所有引用s的ud链 必经结点信息 前置结点称为循环首结点的直接必经结点 首结点的原来的必经结点称为前置结点的直接必经结点 归纳变量 归纳变量定义 在循环中，若变量x值的每次改变都是增加和减少某个固定的常数，则x叫做循环的归纳变量 循环索引变量是一种典型的归纳变量 for j := 1 to n中的j，每次增加1 归纳变量常见于数组的下标 如果循环中的变量i只有唯一形如i := i ± c的赋值，其中c是常量，则i是循环的基本归纳变量 归纳变量的应用 强度削弱 归纳变量的删除 自然循环的规范化 归纳变量识别算法 输入：有到达—定值信息和循环不变信息的循环L 输出：一组归纳变量，联系到每个归纳变量j的三元组(i, c, d),其中i是基本归纳变量，c和d是常量，在j的定值点，j的值是c*i+d。称j属于i族。基本归纳变量属于自己的族 方法： (1) 扫描L的语句，找出所有基本归纳变量（使用循环不变计 算的信息）。对应于基本归纳变量i的是三元组（i, 1, 0） (2) 寻找L中只有一个赋值的变量k，它具有下面的形式之一： k := j * b, k := b * j, k := j / b, k := j ± b, k := b ± j 其中，b是常数，j是基本的和非基本的归纳变量，如果j是 基本的，对应的三元组定义简单； 如果j是非基本的，它属于i族，则附加如下要求： (a) 在循环L中对j唯一赋值和对k的赋值之间没有对i的赋值 (b) 循环L外没有j的定值可到达k的这个定值点 如果j的三元组( i, c, d)，k := b * j，则k的三元组( i, b*c, b*d) 归纳变量的例子 t1 := 202 i := 1 L1:t2 := i 100 if t2 goto L2 t1 := t1 – 2 t3 := addr a t4 := t3 – 4 t5 := 4 * i t6 := t4 + t5 *t6 := t1 i := i + 1 goto L1 L2: t1 := 202 t3 := addr a t4 := t3 – 4 t5 := 4 t6 := t4 t7 := t3 + 396 L1: t2 := t6 t7 if t2 goto L2 t1 := t1 – 2 t6 := t6 + t5 *t6 := t1 goto L1 L2: Integer a(100) Do i = 1 , 100 a( i ) = 202 – 2 * i end 强度削弱 强度削弱 用执行较快的指令代替执行较慢的指令 如在识别了一族归纳变量后，可以修改计算归纳变量，用加法或减法代替乘除法 强度削弱后，有些归纳变量仅用于测试，考虑到归纳变量间存在的一些关系（如t = 4 * i ），因此可以用某个归纳变量的测试（如t）代替这个归纳变量的测试（如i），从而可以删除这个归纳变量 强度削弱的例子 强度削弱的算法 输入：循环L，附带到达—定值信息和归纳变量族 输出：强度削弱后的循环 方法：依次考虑基本归纳变量i，对每个三元组为（i , c , d）的 i 族归纳变量j： (1) 建立新变量s，但如果变量j1和j2有同样的三元组，则仅 建一个新变量用于两者 (2) 用 j := s 代替 j 的赋值 (3) 在L中每个赋值 i := i + n后面（