编译原理优化词法分析器语法分析器中间代码生成器优化段源程序单词符号语法单位四元式表格管理出错处理目标代码生成器四元式目标代码优化可在编译的各个阶段进行。
但其中最主要的优化是在目标代码生成前，对语法分析得到的中间代码进行的，
与具体机器无关。
另一类重要的优化是在生成目标代码时进行的，
与具体机器有关。
第十章 优化
优化,对程序进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码。
等价,指不改变程序的运行结果 。
有效,指目标代码运行时间短,占用的存储空间小 。
编译前端 代码优化器 编译后端控制流分析 数据流分析 代码变换代码优化器的地位和结构
10.1 概述
优化的目的是为了产生更高效的代码。由优化编译程序提供的对代码的各种变换必须遵循一定的原则：
等价 原则：经过优化后不应改变程序运行的结果；
有效 原则：使优化后所产生的目标代码运行时间较短，占用的存储空间较小；
合算 原则：应尽可能以较低的代价取得较好的优化效果。
10.1 概述
优化的三个不同级别：
局部优化
基于块的局部优化比较容易实现。
循环优化
在程序的执行过程中，相当多的一部分时间花在循环上，因此，循环优化比较重要。
全局优化
全局优化涉及整个程序的控制流和数据流分析，
因此实现代价较高。
10.1 概述
优化实施可从不同环节着手
1.源代码
选择合适的算法和实现语句，如排序时选择快速排序比插入排序快。
2.设计语义动作
考虑产生更加高效的中间代码，并为后面的代码优化作准备。
如：在循环语句的头和尾对应的中间代码打上标记，有助于后面的控制流和数据流分析；代码的交叉处和交汇处也可以打上标记，以便于识别程序流图中的直接前驱和直接后继。在目标代码这一级，可以考虑怎样重复利用寄存器，
如何选择指令，进行窥孔优化等。
10.1 概述
优化的种类 （后面举例说明）
删除多余运算 (或称删除公用子表达式 )
复写传播
代码外提
强度消弱
变换循环控制条件
合并已知量
删除无用赋值
void quicksort (m,n); /*快速排序 */
int m,n;
{
int i,j;
int v,x;
if (n<=m) return;
/* fragment begins here*/
i=m-1; j=n; v=a [n];
while (1) {
do i=i+1; while (a [i]<v);
do j=j-1; while (a [j]>v);
if (i>=j) break;
x=a [i]; a[i]=a [j]; a[j]=x;
}
x=a[i]; a[i]=a [n]; a [n]=x;
/*fragment ends here*/
quicksort (m,j); quicksort (i+1,n);
}以下列出在两个 fragment直接代码的中间代码
中间代码程序段
i:=m-1
j:=n
T1:=4*n
v:=a[T1] B1
i:=i+1
T2:=4*i
T3:=a[T2]
if T3<v goto B2
B2
j:=j-1
T4:=4*j
T5:=a[T4]
if T5>v goto B3
B3
if i>=j goto B6 B4
T6:=4*i
x:=a [T6]
T7:=4*i
T8:=4*j
T9:=a [T8]
a [T7]=T9
T10:= 4*j
a [T10]=x
goto B2
B5
T11:=4*i
x:=a [T11]
T12:=4*i
T13:=4*n
T14:=a [T13]
a [T12]=T14
T15:= 4*n
a [T15]=x
B6
中间代码程序段
i:=m-1
j:=n
T1:=4*n
v:=a[T1] B1
i:=i+1
T2:=4*i
T3:=a[T2]
if T3<v goto B2
B2
j:=j-1
T4:=4*j
T5:=a[T4]
if T5>v goto B3
B3
if i>=j goto B6 B4
T6:=4*i
x:=a [T6]
T7:=4*i
T8:=4*j
T9:=a [T8]
a [T7]=T9
T10:= 4*j
a [T10]=x
goto B2
B5
T11:=4*i
x:=a [T11]
T12:=4*i
T13:=4*n
T14:=a [T13]
a [T12]=T14
T15:= 4*n
a [T15]=x
B6
如果一个表达式 E在前面已经计算过，并且之后 E中变量的值没有改变，则称 E
为公共子表达式。对公共子表达式可避免重复计算，称为删除公共子表达式。
删除公用子表达式后
i:=m-1
j:=n
T1:=4*n
v:=a[T1] B1
i:=i+1
T2:=4*i
T3:=a[T2]
if T3<v goto B2
B2
j:=j-1
T4:=4*j
T5:=a[T4]
if T5>v goto B3
B3
if i>=j goto B6 B4
T6:= T2
x:=a [T6]
T7:= T6
T8:= T4
T9:=a [T8]
a [T7]=T9
T10:= T8
a [T10]=x
goto B2
B5
T11:= T2
x:=a [T11]
T12:= T11
T13:= T1
T14:=a [T13]
a [T12]=T14
T15:= T13
a [T15]=x
B6
复写传播
i:=m-1
j:=n
T1:=4*n
v:=a[T1] B1
i:=i+1
T2:=4*i
T3:=a[T2]
if T3<v goto B2
B2
j:=j-1
T4:=4*j
T5:=a[T4]
if T5>v goto B3
B3
if i>=j goto B6 B4
T6:= T2
x:=a [T6]
T7:= T6
T8:= T4
T9:=a [T8]
a [T7]=T9
T10:= T8
a [T10]=x
goto B2
B5
T11:= T2
x:=a [T11]
T12:= T11
T13:= T1
T14:=a [T13]
a [T12]=T14
T15:= T13
a [T15]=x
B6
T6:= T2把 T2的值赋给 T6,x:=a [T6]引用了 T6的值，这中间 T6的值没变，可把 x:=a
[T6]变为 x:=a [T2]，称为复写传播。
复写传播 (一 )后
i:=m-1
j:=n
T1:=4*n
v:=a[T1] B1
i:=i+1
T2:=4*i
T3:=a[T2]
if T3<v goto B2
B2
j:=j-1
T4:=4*j
T5:=a[T4]
if T5>v goto B3
B3
if i>=j goto B6 B4
T6:= T2
x:=a[T2]
T7:= T2
T8:= T4
T9:=a [T4]
a [T2]=T9
T10:= T4
a [T4]=x
goto B2
B5
T11:= T2
x:=a [T2]
T12:= T2
T13:= T1
T14:=a [T1]
a [T2]=T14
T15:= T1
a [T1]=x
B6
复写传播 (一 )后
i:=m-1
j:=n
T1:=4*n
v:=a[T1] B1
i:=i+1
T2:=4*i
T3:=a[T2]
if T3<v goto B2
B2
j:=j-1
T4:=4*j
T5:=a[T4]
if T5>v goto B3
B3
if i>=j goto B6 B4
T6:= T2
x:=a[T2]
T7:= T2
T8:= T4
T9:=a [T4]
a [T2]=T9
T10:= T4
a [T4]=x
goto B2
B5
T11:= T2
x:=a [T2]
T12:= T2
T13:= T1
T14:=a [T1]
a [T2]=T14
T15:= T1
a [T1]=x
B6
进一步考察：在 B5里用到了 x:=a[T2]在 B2里已经计算过了，在 B5里可以删除公共子表达式，将 x:=a[T2]改为 x:=T3,进而通过复写传播把 a [T4]=x改为 a [T4]=T3
复写传播 (二 )后
i:=m-1
j:=n
T1:=4*n
v:=a[T1] B1
i:=i+1
T2:=4*i
T3:=a[T2]
if T3<v goto B2
B2
j:=j-1
T4:=4*j
T5:=a[T4]
if T5>v goto B3
B3
if i>=j goto B6 B4
T6:= T2
x:=T3
T7:= T2
T8:= T4
T9:=T5
a [T2]=T5
T10:= T4
a [T4]= T3
goto B2
B5 T11:= T2x:=T3
T12:= T2
T13:= T1
T14:= v
a [T2]=v
T15:= T1
a [T1]= T3
B6
删除无用赋值
i:=m-1
j:=n
T1:=4*n
v:=a[T1] B1
i:=i+1
T2:=4*i
T3:=a[T2]
if T3<v goto B2
B2
j:=j-1
T4:=4*j
T5:=a[T4]
if T5>v goto B3
B3
if i>=j goto B6 B4
T6:= T2
x:=T3
T7:= T2
T8:= T4
T9:=T5
a [T2]=T5
T10:= T4
a [T4]= T3
goto B2
B5 T11:= T2x:=T3
T12:= T2
T13:= T1
T14:= v
a [T2]=v
T15:= T1
a [T1]= T3
B6
复写传播的目的是为了使某些赋值变得无用，对于进行了复写传播的变量，由于这些变量在整个程序中都不再使用，因此它们的赋值对程序没有任何影响，可删去
删除无用赋值后
i:=m-1
j:=n
T1:=4*n
v:=a[T1] B1
i:=i+1
T2:=4*i
T3:=a[T2]
if T3<v goto B2
B2
j:=j-1
T4:=4*j
T5:=a[T4]
if T5>v goto B3
B3
if i>=j goto B6 B4
a [T2]=T5
a [T4]= T3
goto B2
B5
a [T2]=v
a [T1]=T3
B6
强度削弱
i:=m-1
j:=n
T1:=4*n
v:=a[T1] B1
i:=i+1
T2:=4*i
T3:=a[T2]
if T3<v goto B2
B2
j:=j-1
T4:=4*j
T5:=a[T4]
if T5>v goto B3
B3
if i>=j goto B6 B4
a [T2]=T5
a [T4]= T3
goto B2
B5
a [T2]=v
a [T1]=T3
B6
强度削弱后
i:=m-1
j:=n
T1:=4*n
v:=a[T1]
T2:=4*i
T4:=4*j
B1
i:=i+1
T2:= T2+4
T3:=a[T2]
if T3<v goto B2
B2
j:=j-1
T4:= T4-4
T5:=a[T4]
if T5>v goto B3
B3
if i>=j goto B6 B4
a [T2]=T5
a [T4]= T3
goto B2
B5
a [T2]=v
a [T1]=T3
B6
将循环内的乘法运算变为循环外的一次乘法和循环内的加、减法运算
删除归纳变量
i:=m-1
j:=n
T1:=4*n
v:=a[T1]
T2:=4*i
T4:=4*j
B1
i:=i+1
T2:= T2+4
T3:=a[T2]
if T3<v goto B2
B2
j:=j-1
T4:= T4-4
T5:=a[T4]
if T5>v goto B3
B3
if i>=j goto B6 B4
a [T2]=T5
a [T4]= T3
goto B2
B5
a [T2]=v
a [T1]=T3
B6
注意到 i每次循环加 1,而 t2始终保持 t2=4*i的线性关系，而 j每次循环减 1,而 t4始终保持 t4=4*j的线性关系。这种变量称为归纳变量。注意到 i和 j除了在 B4的条件判断外，其他地方都不用，因此可将条件 if i>=j goto B6变为 if t2>=t4
goto B6,删去 B2和 B3中 i和 j的代码。
删除归纳变量后
i:=m-1
j:=n
T1:=4*n
v:=a[T1]
T2:=4*i
T4:=4*j
B1
T2:= T2+4
T3:=a[T2]
if T3<v goto B2
B2
T4:= T4-4
T5:=a[T4]
if T5>v goto B3
B3
if T2>=T4 goto B6 B4
a [T2]=T5
a [T4]= T3
goto B2
B5
a [T2]=v
a [T1]=T3
B6
中间代码程序段
i:=m-1
j:=n
T1:=4*n
v:=a[T1] B1
i:=i+1
T2:=4*i
T3:=a[T2]
if T3<v goto B2
B2
j:=j-1
T4:=4*j
T5:=a[T4]
if T5>v goto B3
B3
if i>=j goto B6 B4
T6:=4*i
x:=a [T6]
T7:=4*i
T8:=4*j
T9:=a [T8]
a [T7]=T9
T10:= 4*j
a [T10]=x
goto B2
B5
T11:=4*i
x:=a [T11]
T12:=4*i
T13:=4*n
T14:=a [T13]
a [T12]=T14
T15:= 4*n
a [T15]=x
B6
优化前
删除归纳变量后
i:=m-1
j:=n
T1:=4*n
v:=a[T1]
T2:=4*i
T4:=4*j
B1
T2:= T2+4
T3:=a[T2]
if T3<v goto B2
B2
T4:= T4-4
T5:=a[T4]
if T5>v goto B3
B3
if T2>=T4 goto B6 B4
a [T2]=T5
a [T4]= T3
goto B2
B5
a [T2]=v
a [T1]=T3
B6
优化后
B2和 B3的代码由 4条变 3条，一条从乘法变加法,B5从 9条变 3条,B6从 8条变 3条。 B1虽然从 4
条变 6条，但 B1只执行一次。
10.2 局部优化
基本块,指程序中一顺序执行语句序列，其中只有一个入口和一个出口。入口就是其中第一个语句，出口就是其中最后一个语句。如下所示：
T1:=a*a
T2:=a*b
T3:=2*T2
T4:=T1+T2
T5:=b*b
T6:=T4+T5
如果一条三地址语句为 x:=y+z
,则称对 x定值 并 引用 y和 z。
在一个基本块中的一个名字，
所谓在程序中的某个给定点是活跃的,是指如果在程序中 (包括在本基本块或在其它基本块中 )它的值在该点以后被引用。
10.2 局部优化
对于一个给定的程序，可将它划分为一系列的基本块。在各个基本块内分别进行优化。
局限于基本块范围内的优化称为 基本块内的优化,或称 局部优化 。
在一个基本块内通常可以实行下面的优化,
删除公共子表达式
删除无用赋值
合并已知量
临时变量改名
交换语句的位置
代数变换
划分四元式程序为基本块的算法,
1.求出四元式程序中各个基本块的入口语句,
1) 程序第一个语句,或
2) 能由条件转移语句或无条件转移语句转移到的语句,或
3) 紧跟在条件转移语句后面的语句 。
划分四元式程序为基本块的算法,
2,对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到 下一入口语句 (不包括该入口语句 ) 之间的语句序列组成的。
入口语句 n
…
…
入口语句 m
划分四元式程序为基本块的算法,
2,对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到 下一入口语句 (不包括该入口语句 ),或到 一转移语句 (包括该转移语句 ) 之间的语句序列组成的。
入口语句 n
…
…
入口语句 m
入口语句 n
…
…
转移语句 m
划分四元式程序为基本块的算法,
2,对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到 下一入口语句 (不包括该入口语句 )、或到 一转移语句 (包括该转移语句 ),或 一停语句 (包括该停语句 )之间的语句序列组成的。
入口语句 n
…
…
入口语句 m
入口语句 n
…
…
转移语句 m
入口语句 n
…
…
停语句 m
划分四元式程序为基本块的算法,
2,对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到 下一入口语句 (不包括该入口语句 )、或到 一转移语句 (包括该转移语句 )、或 一停语句 (包括该停语句 )之间的语句序列组成的。
3,凡未被纳入某一基本块中的语句，都是控制流无法到达的语句，不会被执行，可以从程序中删除。
例：划分基本块
(1) read X
(2) read Y
(3) R:=X mod Y
(4) if R=0 goto (8)
(5) X:=Y
(6) Y:=R
(7) goto (3)
(8) write Y
(9) halt
1.求出四元式程序中各个基本块的入口语句,
1) 程序第一个语句，或
2) 能由条件转移语句或无条件转移语句转移到的语句，或
3) 紧跟在条件转移语句后面的语句。
例：划分基本块
(1) read X
(2) read Y
(3) R:=X mod Y
(4) if R=0 goto (8)
(5) X:=Y
(6) Y:=R
(7) goto (3)
(8) write Y
(9) halt
1.求出四元式程序中各个基本块的入口语句,
1) 程序第一个语句,或
2) 能由条件转移语句或无条件转移语句转移到的语句，或
3) 紧跟在条件转移语句后面的语句。
例：划分基本块
(1) read X
(2) read Y
(3) R:=X mod Y
(4) if R=0 goto (8)
(5) X:=Y
(6) Y:=R
(7) goto (3)
(8) write Y
(9) halt
1.求出四元式程序中各个基本块的入口语句,
1) 程序第一个语句，或
2) 能由条件转移语句或无条件转移语句转移到的语句,或
3) 紧跟在条件转移语句后面的语句。
例：划分基本块
(1) read X
(2) read Y
(3) R:=X mod Y
(4) if R=0 goto (8)
(5) X:=Y
(6) Y:=R
(7) goto (3)
(8) write Y
(9) halt
1.求出四元式程序中各个基本块的入口语句,
1) 程序第一个语句，或
2) 能由条件转移语句或无条件转移语句转移到的语句,或
3) 紧跟在条件转移语句后面的语句。
例：划分基本块
(1) read X
(2) read Y
(3) R:=X mod Y
(4) if R=0 goto (8)
(5) X:=Y
(6) Y:=R
(7) goto (3)
(8) write Y
(9) halt
1.求出四元式程序中各个基本块的入口语句,
1) 程序第一个语句，或
2) 能由条件转移语句或无条件转移语句转移到的语句，或
3) 紧跟在条件转移语句后面的语句 。
例：划分基本块
(1) read X
(2) read Y
(3) R:=X mod Y
(4) if R=0 goto (8)
(5) X:=Y
(6) Y:=R
(7) goto (3)
(8) write Y
(9) halt
2,对以上求出的每个入口语句，
确定其所属的基本块。它是由该入口语句到 下一入口语句 (不包括该入口语句 )、或到 一转移语句 (包括该转移语句 )、
或 一停语句 (包括该停语句 )之间的语句序列组成的。
优化措施
合并已知量
T1:=2
…
T2:=4*T1
将 T2:=4*T1变换成
T2:=8
临时变量改名
T:=b+c
其中 T是一个临时变量名 。 把这个语句改成：
S:=b+c
S是另一个临时变量名,并将本基本块中出现的 t都变成 S，
不改变基本块的值 。
优化措施
交换语句的位置
T1:=b+c
T2:=x+y
如果 x和 y都不是 T1,b和 c都不是 T2,则可以交换语句的位置不影响基本块的值。
优化措施
代数变换
对基本块中求值的表达式，用代数上等价的形式替换，以期将复杂运算变为简单运算。
如：
x:=x+0
或 x:=x*1可删去
x:=y**2
变换成
x:=y*y
将需要调用函数的乘方运算变为简单运算 。
流图
通过构造一个有向图 —— 流图，可将控制流的信息加在基本块的集合上来表示一个程序。
每个流图以基本块为 结点 。
如果一个结点的基本块的入口语句是程序的第一条语句，则称此结点为 首结点 。
如果在某个执行顺序中，基本块 B2紧接在基本块 B1之后执行，
则从 B1到 B2有一条有向边。即，如果
有一个条件或无条件转移语句从 B1的最后一条语句转移到
B2的第一条语句；或者
在程序的序列中,B2紧接在 B1的后面，并且 B1的最后一条语句不是一个无条件转移语句。
我们就说 B1是 B2的 前驱,B2是 B1的 后继 。
(1) read X
(2) read Y
(3) R:=X mod Y
(4) if R=0 goto (8)
(5) X:=Y
(6) Y:=R
(7) goto (3)
(8) write Y
(9) halt (8) write Y(9) halt
(5) X:=Y
(6) Y:=R
(7) goto (3)
(3) R:=X mod Y
(4) if R=0 goto (8)
(1) read X
(2) read Y B1
B2
B3 B
4
10.2.2 基本块的 DAG表示及其应用
有向图
有向边,ni?nj
前驱,ni是 nj的前驱
后继,nj是 ni的后继
通路,n1?n2,n2?n3,...,nk-
1?nk
环路,n1=nk
DAG,有向无环图 (Directed
Acyclic Graph)
n1 n2
n3n
4
不是 DAG!
n1 n2
n3n
4
是 DAG!
描述计算过程的 DAG是一种带有下述标记或附加信息的 DAG:
n1
3.14
n3 n4
R r
n5
+
T2,T4
图的 叶结点 以一 标识符 或 常数 作为标记，表示该结点代表该变量或常数的值 ;
图的 内部结点 以一 运算符 作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果 ;
图中各个结点上可能附加一个或多个标识符 (称附加标识符 )表示这些变量具有该结点所代表的值。
10.2.2 基本块的 DAG表示及应用
一个基本块，可用一个 DAG来表示与各四元式相对应的 DAG结点形式,
四元式 DAG 图
(0) 0型,A:=B
(:=,B,-,A) n1
A
B
四元式 DAG 图
(1) 1型,A:=op B
(op,B,-,A)
n1
A
B
n2
op
(2) 2型,A:=B op C
(op,B,C,A)
n2
A
B
n1
op
n3
C
四元式 DAG 图
(3) 2型,A:=B[C]
(=[],B[C],-,A)
n2
A
B
n1
=[]
n3
C
(4) 2型,if B rop C goto (s)
(jrop,B,C,(s))
n2
(s)
B
n1
rop
n3
C
四元式 DAG 图
(5) 3型,D[C]:=B
([]=,B,-,D[C])
(6) 0型,goto (s)
(j,-,-,(s)) (s)n
1
n2
B
n1
[]=
n4
C
n3
D
假设 DAG各结点信息将用某种适当的数据结构存放 (如链表 )。另设置一个标识符与结点的对应的表，函数 Node（ A)描述这种对应关系,
否则识符是其上的标记或附加标
，如果存在一个结点
)(
nu l l
A
nn
AN ode
0,1,2型四元式的基本块的 DAG构造算法对基本块中每一四元式，依次执行以下步骤,
1,准备操作数的结点
2,合并已知量
3,删除公共子表达式
4,删除无用赋值
1.准备操作数的结点
如果 NODE(B)无定义，则构造一标记为 B的叶结点并定义 NODE(B)为这个结点 ;
如果当前四元式是 0型，则记 NODE(B)的值为 n，
转 4。
如果当前四元式是 1型，则转 2(1)
如果当前四元式是 2型，则 (i)如果 NODE(C)无定义，则构造一标记为 C的叶结点并定义 NODE(C)为这个结点； (ii)转 2(2)。
2.合并已知量
(1) 如果 NODE(B)是标记为常数的叶结点，则转 2(3)；
否则，转 3(1)。
(2) 如果 NODE(B)和 NODE(C)都是标记为常数的叶结点，
则转 2(4)；否则，转 3(2)。
(3) 执行 op B (即合并已知量 )。令得到的新常数为 P。
如果 NODE(B)是处理当前四元式时新构造出来的结点，则删除它。如果 NODE(P)无定义，则构造一用 P作标记的叶结点 n。 置 NODE(P)=n,转 4。
(4)执行 B op C (即合并已知量 )。令得到的新常数为
P。 如果 NODE(B)或 NODE(C)是处理当前四元式时新构造出来的结点，则删除它。如果 NODE(P)无定义，则构造一用 P作标记的叶结点 n。 置
NODE(P)=n,转 4。
3,寻找公共子表达式
(1) 检查 DAG中是否已有一结点，其唯一后继为
NODE(B)且标记为 op(即公共子表达式 )。如果没有，则构造该结点 n,否则，把已有的结点作为它的结点并设该结点为 n。 转 4。
(2) 检查 DAG中是否已有一结点，其左后继为
NODE(B),右后继为 NODE(C),且标记为 op(即公共子表达式 )。如果没有，则构造该结点 n，
否则，把已有的结点作为它的结点并设该结点为 n。 转 4。
4,删除无用赋值如果 NODE(A)无定义，则把 A附加在结点 n上并令 NODE(A)=n;否则，先把 A从
NODE(A)结点上的附加标识符集中删除
(注意，如果 NODE(A)是叶结点，则其 A标记部不删除 )。把 A附加到新结点 n上并置
NODE(A)=n。 转处理下一四元式。
例 10.4 试构造以下基本块 G的 DAG
(1) T0:=3.14
(2) T1:=2*T0
(3) T2:=R+r
(4) A:=T1*T2
(5) B:=A
(6) T3:=2*T0
(7) T4:=R+r
(8) T5:=T3*T4
(9) T6:=R-r
(10) B:=T5*T6
(1) T0:=3.14
n1
3.14
T0 n2
6.28
T1 n3 n
4
R r
n5
+
T2
n6
*
A,B
,T3
,T4
,T5
n7 T6
-
n8
*
B(2) T1:=2*T0
(3) T2:=R+r
(4) A:=T1*T2
(5) B:=A
(6) T3:=2*T0
(7) T4:=R+r
(8) T5:=T3*T4
(9) T6:=R-r
(10) B:=T5*T6
优化后的四元式
(1) T0:=3.14
(2) T1:=6.28
(3) T3:=6.28
(4) T2:=R+r
(5) T4:=T2
(6) A:=6.28*T2
(7) T5:=A
(8) T6:=R-r
(9) B:=A*T6
n1
3.14
T0 n2
6.28
T1 n3 n
4
R r
n5
+
T2
n6
*
A,B
,T3
,T4
,T5
n7 T6
-
n8
*
B
从 DAG中还能得到其他的优化信息：
在基本块外被定值并在基本块内被引用的所有标识符，就是作为叶子结点上标记的那些标识符。
在基本块内被定值并且该值在基本块后面可以被引用的所有标识符，就是 DAG各结点上的那些附加标识符。
优化后的四元式 —— 若只有 A和 B是出基本块之后活跃的
(1) T2:=R+r
(2) A:=6.28*T2
(3) T6:=R-r
(4) B:=A*T6
临时变量改名后
(1) S1:=R+r
(2) A:=6.28*S1
(3) S2:=R-r
(4) B:=A*S2
n1
3.14
T0 n2
6.28
T1 n3 n
4
R r
n5
+
T2
n6
*
A,B
,T3
,T4
,T5
n7 T6
-
n8
*
B
10.3 循环优化
计算机科学最著名的说法之一是,90/10规则,—
— 程序 90%的执行时间花在 10%的代码上。这样寻找那些一旦优化必将产生极大改进的,热点,显得更为明智。
对循环中的代码，可以实行：
代码外提
强度消弱
删除归纳变量 (变换循环控制条件 )
循环展开
循环合并
10.3.1 代码外提
代码外提,将 循环不变式 从循环体中提到循环外的循环首部。
循环不变式：那些在循环中值保持不变的表达式。
循环不变运算,对四元式 A:=B op C,若 B和 C是常数，或者到达它们的 B和 C的定值点都在循环外。
所谓变量 A在某点 d的 定值到达 另一点 u（ 或称变量
A的定值点 d到达另一点 u）,是指流图中从 d有一通路到达 u且该通路上没有 A的其它定值。
d,A:=B op C…
u,D:=A op E
入口结点循环 L
入口结点循环 L
前置结点
代码外提举例例 1,for I:=1 to 10 do
A[I,2*J],= A[I,2*J] + 1
分析,2*J在循环中保持不变数组 A的 conspart不变
(1) I:=1
(2) if I>10 goto (15)
(3) T1=2*J
(4) T2=10*I
(5) T3= T2+ T1
(6) T4=addr(A)-11
(7) T5=2*J
(8) T6=10*I
(9) T7= T6+ T5
(10) T8=addr(A)-11
(11) T9= T8[T7]
(12) T4[T3]= T9+1
(13) I:=I+1
(14) goto B2
B3
B2
B1
(15)
(1) I:=1
(2) if I>10 goto (15)
(4) T2=10*I
(5) T3= T2+T1
(8) T6=10*I
(9) T7= T6+ T5
(11) T9= T8[T7]
(12) T4[T3]= T9+1
(13) I:=I+1
(14) goto B2
B3
B2
B1
(15)
(3) T1=2*J
(6) T4=addr(A)-11
(7) T5=2*J
(10) T8=addr(A)-11
B2’
问题
是否所有循环不变式都可以外提呢？
不是！
下面举例说明循环不变式可以代码外提的条件。
(1) I:=1
(2) if X<Y goto B3
B1
B2
(3) I:=2
(4) X:=X+1 (5) Y:=Y-1(6) if Y<=20 goto B5
(7) J:=I
B3 B4
B5
X=30,Y=25
B1? B2?B4?B2?B4?…?B2?B4?B5
J=1,I=1
（ 3)是循环不变式例 2
(3) I:=2
(2) if X<Y goto B3
B1
B2
(4) X:=X+1 (5) Y:=Y-1(6) if Y<=20 goto B
5
(7) J:=I
B3 B4
B5
(1) I:=1
B2’
X=30,Y=25
B1? B2?B4?B2?B4?…?B2?B4?B5
J=2,I=2，外提后结果变了，因为 B3不是所有出口节点必经节点。
代码外提条件,不变运算所在的结点是 L所有出口结点的必经结点,
(1) I:=1
(2‘ ) I:=3
(2) if X<Y goto B3
B1
B2
(3) I:=2
(4) X:=X+1 (5) Y:=Y-1(6) if Y<=20 goto B5
(7) J:=I
B3 B4
B5
考虑,B2?B3?B4?B2?B4?B5
I=3,J=3
例 3
（ 2‘）也是循环不变运算，且是所有出口节点的必经节点，是否可以外提呢？
(2‘ ) I:=3
(2) if X<Y goto B3
B1
B2
(3) I:=2
(4) X:=X+1
(5) Y:=Y-1
(6) if Y<=20 goto B5
(7) J:=I
B3 B4
B5
(1) I:=1
B2’
考虑,B2?B3?B4?B2?B4?B5
I=2,J=2
代码外提条件,A在循环中其他地方未再定值,才能把循环不变运算 A:=B op C外提 ;
例 3
考虑,X=0,Y=2
B2?B3?B4?B2?B4?B5
A=2,J=2
(1) I:=1
(2) if X<Y goto B3
B1
B2
(3) A:=I+1
(4) X:=X+1
(5) I:=2
(6) Y:=Y-1
(7) if Y<=0 goto B5
(8) J:=A
B3 B4
B5
例 4
（ 5）是循环不变式，本身就是出口节点，循环内也没有对 I的定值。
(5) I:=2
(2) if X<Y goto B3
B1
B2
(3) A:=I+1
(4) X:=X+1
(6) Y:=Y-1
(7) if Y<=20 goto B5
(8) J:=A
B3 B4
B5
(1) I:=1
B2’
考虑,X=0,Y=2
B2?B3?B4?B2?B4?B5
A=3,J=3
S(A:=B OP C)外提条件,循环中所有 A的引用点只有 S中的 A的定值才能到达。
例 4
循环不变式外提的条件
S(A:=B OP C)外提条件,
A在循环中其他地方未再定值,才能把循环不变运算 A:=B op C外提 ;
不变运算所在的结点是 L所有出口结点的必经结点,
循环中所有 A的引用点只有 S中的 A的定值才能到达。
查找循环 L的不变运算的算法：
① 依次查看 L中各基本块的每个四元式，如果它的每个运算对象或为常数，或者定值点在 L
外，则将此四元式标记为 "不变运算 ";
② 重复第 3步直至没有新的四元式被标记为 "不变运算 "为止 ;
③ 依次查看尚未被标记为 "不变运算 "的四元式，
如果它的每个运算对象或为常数，或定值点在 L之外，或只有一个到达 -定值点且该点上的四元式已被标记为 "不变运算 "，则把被查看的四元式标记为 "不变运算 "。
代码外提算法,
1,求出 L的所有不变运算
2,对每个不变运算 s:A:=B op C 或 A:=op
B 或 A:=B检查是否满足条件 (1)或 (2)
(1)
(i) s所在的结点是 L所有出口结点的必经结点 ;
(ii) A在 L中其他地方未再定值 ;
(iii) L中所有 A的引用点只有 s中的 A的定值才能到达。
(2) A在离开 L后不再是活跃的，并且条件 (1)
的 (ii)和 (iii)成立。所谓 A在离开 L后不是活跃的是指,A在 L的任何出口结点的后继结点入口处不是活跃的。
3.按步骤 1所找出的不变运算的次序，依次把符合条件 2的条件 (1)或 (2)的不变运算 s
外提到 L的前置结点中。但是，如果 s的运算对象 (B或 C)是在 L中定值的，那么，只有当这些定值四元式都已外提到前置结点中时，才能把 s也外提到前置结点中。
外提循环举例
试分析以下程序哪些代码可以外提？
For I in 1..100 loop
for j in 1..100 loop
For k in 1..100 loop
A(I,J,K):=I*J*K
End loop
End loop
End loop
外提循环举例
假定数组行主为序，则这些循环被翻译成如下样式：
For I in 1..100 loop
for j in 1..100 loop
For k in 1..100 loop
A(I)(J)(K):=(I*J)*K
End loop
End loop
End loop
分析：对于内层循环来说,A(I)(J)和 i*j都是循环不变式。可移至中间的循环。
外提循环举例
将 A(I)(J)和 i*j移至中间的循环后
For I in 1..100 loop
for j in 1..100 loop
t1=adr(a(i)(j))
t2=i*j
For k in 1..100 loop
t1(K):=t2*K
End loop
End loop
End loop
分析：对于第 2层循环来说,A(I）都是循环不变式，可外提。
外提循环举例
将 A(I）外提。
For I in 1..100 loop
T3=adr(a(i))
for j in 1..100 loop
t1=adr(t3(j))
t2=i*j
For k in 1..100 loop
t1(K):=t2*K
End loop
End loop
End loop
比较：外提前执行 300万次下标操作和 200万次乘法操作。
外提后执行 1,010,100次下标操作和 1,010,100次乘法操作。
10.3.2 强度消弱
把程序中执行时间较长的运算转换为执行时间较短的运算。
如：把循环中的乘法运算用递归加法运算来替换。
乘法通常比加法慢 3～ 10倍。因此，强度削弱能够产生显著的加速。
(1) I:=1
(2) if I>10 goto (15)
(4) T2=10*I
(5) T3= T2+ T1
(8) T6=10*I
(9) T7= T6+ T5
(11) T9= T8[T7]
(12) T4[T3]= T9+1
(13) I:=I+1
(14) goto B2
B3
B2
B1
(15)
(3) T1=2*J
(6) T4=addr(A)-11
(7) T5=2*J
(10) T8=addr(A)-11
B2’
(1) I:=1
(2) if I>10 goto (15)
(5) T3= T2+ T1
(9) T7= T6+ T5
(11) T9= T8[T7]
(12) T4[T3]= T9+1
(13) I:=I+1
(4‘ ) T2= T2 +10
(8’) T6= T6 +10
(14) goto B2
B3
B2
B1
(15)
(3) T1=2*J
(6) T4=addr(A)-11
(7) T5=2*J
(10) T8=addr(A)-11
(4) T2=10*I
(8) T6=10*I
B2’
(1) I:=1
(2) if I>10 goto (15)
(5) T3= T2+ T1
(9) T7= T6+ T5
(11) T9= T8[T7]
(12) T4[T3]= T9+1
(13) I:=I+1
(4‘ ) T2= T2 +10
(8’) T6= T6 +10
(14) goto B2
B3
B2
B1
(15)
(3) T1=2*J
(6) T4=addr(A)-11
(7) T5=2*J
(10) T8=addr(A)-11
(4) T2=10*I
(8) T6=10*I
B2’
(1) I:=1
(2) if I>10 goto (15)
(11) T9= T8[T7](12) T
4[T3]= T9+1(13) I:=I+1
(4‘ ) T2= T2 +10(8’) T
6= T6 +10(5‘ ) T
3= T3+ 10(9‘ ) T
7= T7+ 10(14) goto B
2
B3
B2
B1
(15)
(3) T1=2*J(6) T
4=addr(A)-11(7) T
5=2*J(10) T
8=addr(A)-11(4) T
2=10*I(8) T
6=10*I(5) T
3= T2+ T1(9) T
7= T6+ T5
B2’
强度消弱
强度消弱主要是对与 归纳变量 有 线性关系 的变量赋值进行；
经过强度消弱后，循环中可能出现一些新的无用赋值；
对于消弱下标变量地址计算的强度非常有效。
10.3.3 删除归纳变量
如果循环中对变量 I只有唯一的形如 I:=I?C
的赋值，且其中 C为循环不变量，则称 I为循环中的 基本归纳变量 。
如果 I是循环中一基本归纳变量,J在循环中的定值总是可化归为 I的同一线性函数，
也即 J=C1*I? C2,其中 C1和 C2都是循环不变量，则称 J是 归纳变量,并称它与 I同族。一个基本归纳变量也是一归纳变量。
(1) I:=1
(2) if I>10 goto (15)
(11) T9= T8[T7](12) T
4[T3]= T9+1(13) I:=I+1
(4‘ ) T2= T2 +10(8’) T
6= T6 +10(5‘ ) T
3= T3+ 10(9‘ ) T
7= T7+ 10(14) goto B
2
B3
B2
B1
(15)
(3) T1=2*J(6) T
4=addr(A)-11(7) T
5=2*J(10) T
8=addr(A)-11(4) T
2=10*I(8) T
6=10*I(5) T
3= T2+ T1(9) T
7= T6+ T5
B2’
(1) I:=1
(2) if T3>R goto (15)
(11) T9= T8[T7]
(12) T4[T3]= T9+1
(5‘ ) T3= T3+ 10
(9‘ ) T7= T7+ 10
(14) goto B2
B3
B2
B1
(15)
(3) T1=2*J
(6) T4=addr(A)-11
(7) T5=2*J
(10) T8=addr(A)-11
(4) T2=10*I
(8) T6=10*I
(5) T3= T2+ T1
(9) T7= T6+ T5
(21) R=100+T1
B2’
删除归纳变量是在强度削弱以后进行的。强度削弱和删除归纳变量的统一算法框架，其步骤如下：
1,利用循环不变运算信息，找出循环中所有基本归纳变量。
2,找出所有其它归纳变量 A,并找出 A与已知基本归纳变量 X的同族线性函数关系 FA(X)。
3,对 2中找出的每一归纳变量 A,进行强度削弱。
4,删除对归纳变量的无用赋值。
5,删除基本归纳变量。如果基本归纳变量 B在循环出口之后不是活跃的，并且在循环中，
除在其自身的递归赋值中被引用外，只在形如
if B rop Y goto L
中被引用，则可选取一与 B同族的归纳变量
M来替换 B进行条件控制。最后删除循环中对 B的递归赋值的代码。
但其中最主要的优化是在目标代码生成前，对语法分析得到的中间代码进行的，
与具体机器无关。
另一类重要的优化是在生成目标代码时进行的，
与具体机器有关。
第十章 优化
优化,对程序进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码。
等价,指不改变程序的运行结果 。
有效,指目标代码运行时间短,占用的存储空间小 。
编译前端 代码优化器 编译后端控制流分析 数据流分析 代码变换代码优化器的地位和结构
10.1 概述
优化的目的是为了产生更高效的代码。由优化编译程序提供的对代码的各种变换必须遵循一定的原则：
等价 原则：经过优化后不应改变程序运行的结果；
有效 原则：使优化后所产生的目标代码运行时间较短，占用的存储空间较小；
合算 原则：应尽可能以较低的代价取得较好的优化效果。
10.1 概述
优化的三个不同级别：
局部优化
基于块的局部优化比较容易实现。
循环优化
在程序的执行过程中，相当多的一部分时间花在循环上，因此，循环优化比较重要。
全局优化
全局优化涉及整个程序的控制流和数据流分析，
因此实现代价较高。
10.1 概述
优化实施可从不同环节着手
1.源代码
选择合适的算法和实现语句，如排序时选择快速排序比插入排序快。
2.设计语义动作
考虑产生更加高效的中间代码，并为后面的代码优化作准备。
如：在循环语句的头和尾对应的中间代码打上标记，有助于后面的控制流和数据流分析；代码的交叉处和交汇处也可以打上标记，以便于识别程序流图中的直接前驱和直接后继。在目标代码这一级，可以考虑怎样重复利用寄存器，
如何选择指令，进行窥孔优化等。
10.1 概述
优化的种类 （后面举例说明）
删除多余运算 (或称删除公用子表达式 )
复写传播
代码外提
强度消弱
变换循环控制条件
合并已知量
删除无用赋值
void quicksort (m,n); /*快速排序 */
int m,n;
{
int i,j;
int v,x;
if (n<=m) return;
/* fragment begins here*/
i=m-1; j=n; v=a [n];
while (1) {
do i=i+1; while (a [i]<v);
do j=j-1; while (a [j]>v);
if (i>=j) break;
x=a [i]; a[i]=a [j]; a[j]=x;
}
x=a[i]; a[i]=a [n]; a [n]=x;
/*fragment ends here*/
quicksort (m,j); quicksort (i+1,n);
}以下列出在两个 fragment直接代码的中间代码
中间代码程序段
i:=m-1
j:=n
T1:=4*n
v:=a[T1] B1
i:=i+1
T2:=4*i
T3:=a[T2]
if T3<v goto B2
B2
j:=j-1
T4:=4*j
T5:=a[T4]
if T5>v goto B3
B3
if i>=j goto B6 B4
T6:=4*i
x:=a [T6]
T7:=4*i
T8:=4*j
T9:=a [T8]
a [T7]=T9
T10:= 4*j
a [T10]=x
goto B2
B5
T11:=4*i
x:=a [T11]
T12:=4*i
T13:=4*n
T14:=a [T13]
a [T12]=T14
T15:= 4*n
a [T15]=x
B6
中间代码程序段
i:=m-1
j:=n
T1:=4*n
v:=a[T1] B1
i:=i+1
T2:=4*i
T3:=a[T2]
if T3<v goto B2
B2
j:=j-1
T4:=4*j
T5:=a[T4]
if T5>v goto B3
B3
if i>=j goto B6 B4
T6:=4*i
x:=a [T6]
T7:=4*i
T8:=4*j
T9:=a [T8]
a [T7]=T9
T10:= 4*j
a [T10]=x
goto B2
B5
T11:=4*i
x:=a [T11]
T12:=4*i
T13:=4*n
T14:=a [T13]
a [T12]=T14
T15:= 4*n
a [T15]=x
B6
如果一个表达式 E在前面已经计算过，并且之后 E中变量的值没有改变，则称 E
为公共子表达式。对公共子表达式可避免重复计算，称为删除公共子表达式。
删除公用子表达式后
i:=m-1
j:=n
T1:=4*n
v:=a[T1] B1
i:=i+1
T2:=4*i
T3:=a[T2]
if T3<v goto B2
B2
j:=j-1
T4:=4*j
T5:=a[T4]
if T5>v goto B3
B3
if i>=j goto B6 B4
T6:= T2
x:=a [T6]
T7:= T6
T8:= T4
T9:=a [T8]
a [T7]=T9
T10:= T8
a [T10]=x
goto B2
B5
T11:= T2
x:=a [T11]
T12:= T11
T13:= T1
T14:=a [T13]
a [T12]=T14
T15:= T13
a [T15]=x
B6
复写传播
i:=m-1
j:=n
T1:=4*n
v:=a[T1] B1
i:=i+1
T2:=4*i
T3:=a[T2]
if T3<v goto B2
B2
j:=j-1
T4:=4*j
T5:=a[T4]
if T5>v goto B3
B3
if i>=j goto B6 B4
T6:= T2
x:=a [T6]
T7:= T6
T8:= T4
T9:=a [T8]
a [T7]=T9
T10:= T8
a [T10]=x
goto B2
B5
T11:= T2
x:=a [T11]
T12:= T11
T13:= T1
T14:=a [T13]
a [T12]=T14
T15:= T13
a [T15]=x
B6
T6:= T2把 T2的值赋给 T6,x:=a [T6]引用了 T6的值，这中间 T6的值没变，可把 x:=a
[T6]变为 x:=a [T2]，称为复写传播。
复写传播 (一 )后
i:=m-1
j:=n
T1:=4*n
v:=a[T1] B1
i:=i+1
T2:=4*i
T3:=a[T2]
if T3<v goto B2
B2
j:=j-1
T4:=4*j
T5:=a[T4]
if T5>v goto B3
B3
if i>=j goto B6 B4
T6:= T2
x:=a[T2]
T7:= T2
T8:= T4
T9:=a [T4]
a [T2]=T9
T10:= T4
a [T4]=x
goto B2
B5
T11:= T2
x:=a [T2]
T12:= T2
T13:= T1
T14:=a [T1]
a [T2]=T14
T15:= T1
a [T1]=x
B6
复写传播 (一 )后
i:=m-1
j:=n
T1:=4*n
v:=a[T1] B1
i:=i+1
T2:=4*i
T3:=a[T2]
if T3<v goto B2
B2
j:=j-1
T4:=4*j
T5:=a[T4]
if T5>v goto B3
B3
if i>=j goto B6 B4
T6:= T2
x:=a[T2]
T7:= T2
T8:= T4
T9:=a [T4]
a [T2]=T9
T10:= T4
a [T4]=x
goto B2
B5
T11:= T2
x:=a [T2]
T12:= T2
T13:= T1
T14:=a [T1]
a [T2]=T14
T15:= T1
a [T1]=x
B6
进一步考察：在 B5里用到了 x:=a[T2]在 B2里已经计算过了，在 B5里可以删除公共子表达式，将 x:=a[T2]改为 x:=T3,进而通过复写传播把 a [T4]=x改为 a [T4]=T3
复写传播 (二 )后
i:=m-1
j:=n
T1:=4*n
v:=a[T1] B1
i:=i+1
T2:=4*i
T3:=a[T2]
if T3<v goto B2
B2
j:=j-1
T4:=4*j
T5:=a[T4]
if T5>v goto B3
B3
if i>=j goto B6 B4
T6:= T2
x:=T3
T7:= T2
T8:= T4
T9:=T5
a [T2]=T5
T10:= T4
a [T4]= T3
goto B2
B5 T11:= T2x:=T3
T12:= T2
T13:= T1
T14:= v
a [T2]=v
T15:= T1
a [T1]= T3
B6
删除无用赋值
i:=m-1
j:=n
T1:=4*n
v:=a[T1] B1
i:=i+1
T2:=4*i
T3:=a[T2]
if T3<v goto B2
B2
j:=j-1
T4:=4*j
T5:=a[T4]
if T5>v goto B3
B3
if i>=j goto B6 B4
T6:= T2
x:=T3
T7:= T2
T8:= T4
T9:=T5
a [T2]=T5
T10:= T4
a [T4]= T3
goto B2
B5 T11:= T2x:=T3
T12:= T2
T13:= T1
T14:= v
a [T2]=v
T15:= T1
a [T1]= T3
B6
复写传播的目的是为了使某些赋值变得无用，对于进行了复写传播的变量，由于这些变量在整个程序中都不再使用，因此它们的赋值对程序没有任何影响，可删去
删除无用赋值后
i:=m-1
j:=n
T1:=4*n
v:=a[T1] B1
i:=i+1
T2:=4*i
T3:=a[T2]
if T3<v goto B2
B2
j:=j-1
T4:=4*j
T5:=a[T4]
if T5>v goto B3
B3
if i>=j goto B6 B4
a [T2]=T5
a [T4]= T3
goto B2
B5
a [T2]=v
a [T1]=T3
B6
强度削弱
i:=m-1
j:=n
T1:=4*n
v:=a[T1] B1
i:=i+1
T2:=4*i
T3:=a[T2]
if T3<v goto B2
B2
j:=j-1
T4:=4*j
T5:=a[T4]
if T5>v goto B3
B3
if i>=j goto B6 B4
a [T2]=T5
a [T4]= T3
goto B2
B5
a [T2]=v
a [T1]=T3
B6
强度削弱后
i:=m-1
j:=n
T1:=4*n
v:=a[T1]
T2:=4*i
T4:=4*j
B1
i:=i+1
T2:= T2+4
T3:=a[T2]
if T3<v goto B2
B2
j:=j-1
T4:= T4-4
T5:=a[T4]
if T5>v goto B3
B3
if i>=j goto B6 B4
a [T2]=T5
a [T4]= T3
goto B2
B5
a [T2]=v
a [T1]=T3
B6
将循环内的乘法运算变为循环外的一次乘法和循环内的加、减法运算
删除归纳变量
i:=m-1
j:=n
T1:=4*n
v:=a[T1]
T2:=4*i
T4:=4*j
B1
i:=i+1
T2:= T2+4
T3:=a[T2]
if T3<v goto B2
B2
j:=j-1
T4:= T4-4
T5:=a[T4]
if T5>v goto B3
B3
if i>=j goto B6 B4
a [T2]=T5
a [T4]= T3
goto B2
B5
a [T2]=v
a [T1]=T3
B6
注意到 i每次循环加 1,而 t2始终保持 t2=4*i的线性关系，而 j每次循环减 1,而 t4始终保持 t4=4*j的线性关系。这种变量称为归纳变量。注意到 i和 j除了在 B4的条件判断外，其他地方都不用，因此可将条件 if i>=j goto B6变为 if t2>=t4
goto B6,删去 B2和 B3中 i和 j的代码。
删除归纳变量后
i:=m-1
j:=n
T1:=4*n
v:=a[T1]
T2:=4*i
T4:=4*j
B1
T2:= T2+4
T3:=a[T2]
if T3<v goto B2
B2
T4:= T4-4
T5:=a[T4]
if T5>v goto B3
B3
if T2>=T4 goto B6 B4
a [T2]=T5
a [T4]= T3
goto B2
B5
a [T2]=v
a [T1]=T3
B6
中间代码程序段
i:=m-1
j:=n
T1:=4*n
v:=a[T1] B1
i:=i+1
T2:=4*i
T3:=a[T2]
if T3<v goto B2
B2
j:=j-1
T4:=4*j
T5:=a[T4]
if T5>v goto B3
B3
if i>=j goto B6 B4
T6:=4*i
x:=a [T6]
T7:=4*i
T8:=4*j
T9:=a [T8]
a [T7]=T9
T10:= 4*j
a [T10]=x
goto B2
B5
T11:=4*i
x:=a [T11]
T12:=4*i
T13:=4*n
T14:=a [T13]
a [T12]=T14
T15:= 4*n
a [T15]=x
B6
优化前
删除归纳变量后
i:=m-1
j:=n
T1:=4*n
v:=a[T1]
T2:=4*i
T4:=4*j
B1
T2:= T2+4
T3:=a[T2]
if T3<v goto B2
B2
T4:= T4-4
T5:=a[T4]
if T5>v goto B3
B3
if T2>=T4 goto B6 B4
a [T2]=T5
a [T4]= T3
goto B2
B5
a [T2]=v
a [T1]=T3
B6
优化后
B2和 B3的代码由 4条变 3条，一条从乘法变加法,B5从 9条变 3条,B6从 8条变 3条。 B1虽然从 4
条变 6条，但 B1只执行一次。
10.2 局部优化
基本块,指程序中一顺序执行语句序列，其中只有一个入口和一个出口。入口就是其中第一个语句，出口就是其中最后一个语句。如下所示：
T1:=a*a
T2:=a*b
T3:=2*T2
T4:=T1+T2
T5:=b*b
T6:=T4+T5
如果一条三地址语句为 x:=y+z
,则称对 x定值 并 引用 y和 z。
在一个基本块中的一个名字，
所谓在程序中的某个给定点是活跃的,是指如果在程序中 (包括在本基本块或在其它基本块中 )它的值在该点以后被引用。
10.2 局部优化
对于一个给定的程序，可将它划分为一系列的基本块。在各个基本块内分别进行优化。
局限于基本块范围内的优化称为 基本块内的优化,或称 局部优化 。
在一个基本块内通常可以实行下面的优化,
删除公共子表达式
删除无用赋值
合并已知量
临时变量改名
交换语句的位置
代数变换
划分四元式程序为基本块的算法,
1.求出四元式程序中各个基本块的入口语句,
1) 程序第一个语句,或
2) 能由条件转移语句或无条件转移语句转移到的语句,或
3) 紧跟在条件转移语句后面的语句 。
划分四元式程序为基本块的算法,
2,对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到 下一入口语句 (不包括该入口语句 ) 之间的语句序列组成的。
入口语句 n
…
…
入口语句 m
划分四元式程序为基本块的算法,
2,对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到 下一入口语句 (不包括该入口语句 ),或到 一转移语句 (包括该转移语句 ) 之间的语句序列组成的。
入口语句 n
…
…
入口语句 m
入口语句 n
…
…
转移语句 m
划分四元式程序为基本块的算法,
2,对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到 下一入口语句 (不包括该入口语句 )、或到 一转移语句 (包括该转移语句 ),或 一停语句 (包括该停语句 )之间的语句序列组成的。
入口语句 n
…
…
入口语句 m
入口语句 n
…
…
转移语句 m
入口语句 n
…
…
停语句 m
划分四元式程序为基本块的算法,
2,对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到 下一入口语句 (不包括该入口语句 )、或到 一转移语句 (包括该转移语句 )、或 一停语句 (包括该停语句 )之间的语句序列组成的。
3,凡未被纳入某一基本块中的语句，都是控制流无法到达的语句，不会被执行，可以从程序中删除。
例：划分基本块
(1) read X
(2) read Y
(3) R:=X mod Y
(4) if R=0 goto (8)
(5) X:=Y
(6) Y:=R
(7) goto (3)
(8) write Y
(9) halt
1.求出四元式程序中各个基本块的入口语句,
1) 程序第一个语句，或
2) 能由条件转移语句或无条件转移语句转移到的语句，或
3) 紧跟在条件转移语句后面的语句。
例：划分基本块
(1) read X
(2) read Y
(3) R:=X mod Y
(4) if R=0 goto (8)
(5) X:=Y
(6) Y:=R
(7) goto (3)
(8) write Y
(9) halt
1.求出四元式程序中各个基本块的入口语句,
1) 程序第一个语句,或
2) 能由条件转移语句或无条件转移语句转移到的语句，或
3) 紧跟在条件转移语句后面的语句。
例：划分基本块
(1) read X
(2) read Y
(3) R:=X mod Y
(4) if R=0 goto (8)
(5) X:=Y
(6) Y:=R
(7) goto (3)
(8) write Y
(9) halt
1.求出四元式程序中各个基本块的入口语句,
1) 程序第一个语句，或
2) 能由条件转移语句或无条件转移语句转移到的语句,或
3) 紧跟在条件转移语句后面的语句。
例：划分基本块
(1) read X
(2) read Y
(3) R:=X mod Y
(4) if R=0 goto (8)
(5) X:=Y
(6) Y:=R
(7) goto (3)
(8) write Y
(9) halt
1.求出四元式程序中各个基本块的入口语句,
1) 程序第一个语句，或
2) 能由条件转移语句或无条件转移语句转移到的语句,或
3) 紧跟在条件转移语句后面的语句。
例：划分基本块
(1) read X
(2) read Y
(3) R:=X mod Y
(4) if R=0 goto (8)
(5) X:=Y
(6) Y:=R
(7) goto (3)
(8) write Y
(9) halt
1.求出四元式程序中各个基本块的入口语句,
1) 程序第一个语句，或
2) 能由条件转移语句或无条件转移语句转移到的语句，或
3) 紧跟在条件转移语句后面的语句 。
例：划分基本块
(1) read X
(2) read Y
(3) R:=X mod Y
(4) if R=0 goto (8)
(5) X:=Y
(6) Y:=R
(7) goto (3)
(8) write Y
(9) halt
2,对以上求出的每个入口语句，
确定其所属的基本块。它是由该入口语句到 下一入口语句 (不包括该入口语句 )、或到 一转移语句 (包括该转移语句 )、
或 一停语句 (包括该停语句 )之间的语句序列组成的。
优化措施
合并已知量
T1:=2
…
T2:=4*T1
将 T2:=4*T1变换成
T2:=8
临时变量改名
T:=b+c
其中 T是一个临时变量名 。 把这个语句改成：
S:=b+c
S是另一个临时变量名,并将本基本块中出现的 t都变成 S，
不改变基本块的值 。
优化措施
交换语句的位置
T1:=b+c
T2:=x+y
如果 x和 y都不是 T1,b和 c都不是 T2,则可以交换语句的位置不影响基本块的值。
优化措施
代数变换
对基本块中求值的表达式，用代数上等价的形式替换，以期将复杂运算变为简单运算。
如：
x:=x+0
或 x:=x*1可删去
x:=y**2
变换成
x:=y*y
将需要调用函数的乘方运算变为简单运算 。
流图
通过构造一个有向图 —— 流图，可将控制流的信息加在基本块的集合上来表示一个程序。
每个流图以基本块为 结点 。
如果一个结点的基本块的入口语句是程序的第一条语句，则称此结点为 首结点 。
如果在某个执行顺序中，基本块 B2紧接在基本块 B1之后执行，
则从 B1到 B2有一条有向边。即，如果
有一个条件或无条件转移语句从 B1的最后一条语句转移到
B2的第一条语句；或者
在程序的序列中,B2紧接在 B1的后面，并且 B1的最后一条语句不是一个无条件转移语句。
我们就说 B1是 B2的 前驱,B2是 B1的 后继 。
(1) read X
(2) read Y
(3) R:=X mod Y
(4) if R=0 goto (8)
(5) X:=Y
(6) Y:=R
(7) goto (3)
(8) write Y
(9) halt (8) write Y(9) halt
(5) X:=Y
(6) Y:=R
(7) goto (3)
(3) R:=X mod Y
(4) if R=0 goto (8)
(1) read X
(2) read Y B1
B2
B3 B
4
10.2.2 基本块的 DAG表示及其应用
有向图
有向边,ni?nj
前驱,ni是 nj的前驱
后继,nj是 ni的后继
通路,n1?n2,n2?n3,...,nk-
1?nk
环路,n1=nk
DAG,有向无环图 (Directed
Acyclic Graph)
n1 n2
n3n
4
不是 DAG!
n1 n2
n3n
4
是 DAG!
描述计算过程的 DAG是一种带有下述标记或附加信息的 DAG:
n1
3.14
n3 n4
R r
n5
+
T2,T4
图的 叶结点 以一 标识符 或 常数 作为标记，表示该结点代表该变量或常数的值 ;
图的 内部结点 以一 运算符 作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果 ;
图中各个结点上可能附加一个或多个标识符 (称附加标识符 )表示这些变量具有该结点所代表的值。
10.2.2 基本块的 DAG表示及应用
一个基本块，可用一个 DAG来表示与各四元式相对应的 DAG结点形式,
四元式 DAG 图
(0) 0型,A:=B
(:=,B,-,A) n1
A
B
四元式 DAG 图
(1) 1型,A:=op B
(op,B,-,A)
n1
A
B
n2
op
(2) 2型,A:=B op C
(op,B,C,A)
n2
A
B
n1
op
n3
C
四元式 DAG 图
(3) 2型,A:=B[C]
(=[],B[C],-,A)
n2
A
B
n1
=[]
n3
C
(4) 2型,if B rop C goto (s)
(jrop,B,C,(s))
n2
(s)
B
n1
rop
n3
C
四元式 DAG 图
(5) 3型,D[C]:=B
([]=,B,-,D[C])
(6) 0型,goto (s)
(j,-,-,(s)) (s)n
1
n2
B
n1
[]=
n4
C
n3
D
假设 DAG各结点信息将用某种适当的数据结构存放 (如链表 )。另设置一个标识符与结点的对应的表，函数 Node（ A)描述这种对应关系,
否则识符是其上的标记或附加标
，如果存在一个结点
)(
nu l l
A
nn
AN ode
0,1,2型四元式的基本块的 DAG构造算法对基本块中每一四元式，依次执行以下步骤,
1,准备操作数的结点
2,合并已知量
3,删除公共子表达式
4,删除无用赋值
1.准备操作数的结点
如果 NODE(B)无定义，则构造一标记为 B的叶结点并定义 NODE(B)为这个结点 ;
如果当前四元式是 0型，则记 NODE(B)的值为 n，
转 4。
如果当前四元式是 1型，则转 2(1)
如果当前四元式是 2型，则 (i)如果 NODE(C)无定义，则构造一标记为 C的叶结点并定义 NODE(C)为这个结点； (ii)转 2(2)。
2.合并已知量
(1) 如果 NODE(B)是标记为常数的叶结点，则转 2(3)；
否则，转 3(1)。
(2) 如果 NODE(B)和 NODE(C)都是标记为常数的叶结点，
则转 2(4)；否则，转 3(2)。
(3) 执行 op B (即合并已知量 )。令得到的新常数为 P。
如果 NODE(B)是处理当前四元式时新构造出来的结点，则删除它。如果 NODE(P)无定义，则构造一用 P作标记的叶结点 n。 置 NODE(P)=n,转 4。
(4)执行 B op C (即合并已知量 )。令得到的新常数为
P。 如果 NODE(B)或 NODE(C)是处理当前四元式时新构造出来的结点，则删除它。如果 NODE(P)无定义，则构造一用 P作标记的叶结点 n。 置
NODE(P)=n,转 4。
3,寻找公共子表达式
(1) 检查 DAG中是否已有一结点，其唯一后继为
NODE(B)且标记为 op(即公共子表达式 )。如果没有，则构造该结点 n,否则，把已有的结点作为它的结点并设该结点为 n。 转 4。
(2) 检查 DAG中是否已有一结点，其左后继为
NODE(B),右后继为 NODE(C),且标记为 op(即公共子表达式 )。如果没有，则构造该结点 n，
否则，把已有的结点作为它的结点并设该结点为 n。 转 4。
4,删除无用赋值如果 NODE(A)无定义，则把 A附加在结点 n上并令 NODE(A)=n;否则，先把 A从
NODE(A)结点上的附加标识符集中删除
(注意，如果 NODE(A)是叶结点，则其 A标记部不删除 )。把 A附加到新结点 n上并置
NODE(A)=n。 转处理下一四元式。
例 10.4 试构造以下基本块 G的 DAG
(1) T0:=3.14
(2) T1:=2*T0
(3) T2:=R+r
(4) A:=T1*T2
(5) B:=A
(6) T3:=2*T0
(7) T4:=R+r
(8) T5:=T3*T4
(9) T6:=R-r
(10) B:=T5*T6
(1) T0:=3.14
n1
3.14
T0 n2
6.28
T1 n3 n
4
R r
n5
+
T2
n6
*
A,B
,T3
,T4
,T5
n7 T6
-
n8
*
B(2) T1:=2*T0
(3) T2:=R+r
(4) A:=T1*T2
(5) B:=A
(6) T3:=2*T0
(7) T4:=R+r
(8) T5:=T3*T4
(9) T6:=R-r
(10) B:=T5*T6
优化后的四元式
(1) T0:=3.14
(2) T1:=6.28
(3) T3:=6.28
(4) T2:=R+r
(5) T4:=T2
(6) A:=6.28*T2
(7) T5:=A
(8) T6:=R-r
(9) B:=A*T6
n1
3.14
T0 n2
6.28
T1 n3 n
4
R r
n5
+
T2
n6
*
A,B
,T3
,T4
,T5
n7 T6
-
n8
*
B
从 DAG中还能得到其他的优化信息：
在基本块外被定值并在基本块内被引用的所有标识符，就是作为叶子结点上标记的那些标识符。
在基本块内被定值并且该值在基本块后面可以被引用的所有标识符，就是 DAG各结点上的那些附加标识符。
优化后的四元式 —— 若只有 A和 B是出基本块之后活跃的
(1) T2:=R+r
(2) A:=6.28*T2
(3) T6:=R-r
(4) B:=A*T6
临时变量改名后
(1) S1:=R+r
(2) A:=6.28*S1
(3) S2:=R-r
(4) B:=A*S2
n1
3.14
T0 n2
6.28
T1 n3 n
4
R r
n5
+
T2
n6
*
A,B
,T3
,T4
,T5
n7 T6
-
n8
*
B
10.3 循环优化
计算机科学最著名的说法之一是,90/10规则,—
— 程序 90%的执行时间花在 10%的代码上。这样寻找那些一旦优化必将产生极大改进的,热点,显得更为明智。
对循环中的代码，可以实行：
代码外提
强度消弱
删除归纳变量 (变换循环控制条件 )
循环展开
循环合并
10.3.1 代码外提
代码外提,将 循环不变式 从循环体中提到循环外的循环首部。
循环不变式：那些在循环中值保持不变的表达式。
循环不变运算,对四元式 A:=B op C,若 B和 C是常数，或者到达它们的 B和 C的定值点都在循环外。
所谓变量 A在某点 d的 定值到达 另一点 u（ 或称变量
A的定值点 d到达另一点 u）,是指流图中从 d有一通路到达 u且该通路上没有 A的其它定值。
d,A:=B op C…
u,D:=A op E
入口结点循环 L
入口结点循环 L
前置结点
代码外提举例例 1,for I:=1 to 10 do
A[I,2*J],= A[I,2*J] + 1
分析,2*J在循环中保持不变数组 A的 conspart不变
(1) I:=1
(2) if I>10 goto (15)
(3) T1=2*J
(4) T2=10*I
(5) T3= T2+ T1
(6) T4=addr(A)-11
(7) T5=2*J
(8) T6=10*I
(9) T7= T6+ T5
(10) T8=addr(A)-11
(11) T9= T8[T7]
(12) T4[T3]= T9+1
(13) I:=I+1
(14) goto B2
B3
B2
B1
(15)
(1) I:=1
(2) if I>10 goto (15)
(4) T2=10*I
(5) T3= T2+T1
(8) T6=10*I
(9) T7= T6+ T5
(11) T9= T8[T7]
(12) T4[T3]= T9+1
(13) I:=I+1
(14) goto B2
B3
B2
B1
(15)
(3) T1=2*J
(6) T4=addr(A)-11
(7) T5=2*J
(10) T8=addr(A)-11
B2’
问题
是否所有循环不变式都可以外提呢？
不是！
下面举例说明循环不变式可以代码外提的条件。
(1) I:=1
(2) if X<Y goto B3
B1
B2
(3) I:=2
(4) X:=X+1 (5) Y:=Y-1(6) if Y<=20 goto B5
(7) J:=I
B3 B4
B5
X=30,Y=25
B1? B2?B4?B2?B4?…?B2?B4?B5
J=1,I=1
（ 3)是循环不变式例 2
(3) I:=2
(2) if X<Y goto B3
B1
B2
(4) X:=X+1 (5) Y:=Y-1(6) if Y<=20 goto B
5
(7) J:=I
B3 B4
B5
(1) I:=1
B2’
X=30,Y=25
B1? B2?B4?B2?B4?…?B2?B4?B5
J=2,I=2，外提后结果变了，因为 B3不是所有出口节点必经节点。
代码外提条件,不变运算所在的结点是 L所有出口结点的必经结点,
(1) I:=1
(2‘ ) I:=3
(2) if X<Y goto B3
B1
B2
(3) I:=2
(4) X:=X+1 (5) Y:=Y-1(6) if Y<=20 goto B5
(7) J:=I
B3 B4
B5
考虑,B2?B3?B4?B2?B4?B5
I=3,J=3
例 3
（ 2‘）也是循环不变运算，且是所有出口节点的必经节点，是否可以外提呢？
(2‘ ) I:=3
(2) if X<Y goto B3
B1
B2
(3) I:=2
(4) X:=X+1
(5) Y:=Y-1
(6) if Y<=20 goto B5
(7) J:=I
B3 B4
B5
(1) I:=1
B2’
考虑,B2?B3?B4?B2?B4?B5
I=2,J=2
代码外提条件,A在循环中其他地方未再定值,才能把循环不变运算 A:=B op C外提 ;
例 3
考虑,X=0,Y=2
B2?B3?B4?B2?B4?B5
A=2,J=2
(1) I:=1
(2) if X<Y goto B3
B1
B2
(3) A:=I+1
(4) X:=X+1
(5) I:=2
(6) Y:=Y-1
(7) if Y<=0 goto B5
(8) J:=A
B3 B4
B5
例 4
（ 5）是循环不变式，本身就是出口节点，循环内也没有对 I的定值。
(5) I:=2
(2) if X<Y goto B3
B1
B2
(3) A:=I+1
(4) X:=X+1
(6) Y:=Y-1
(7) if Y<=20 goto B5
(8) J:=A
B3 B4
B5
(1) I:=1
B2’
考虑,X=0,Y=2
B2?B3?B4?B2?B4?B5
A=3,J=3
S(A:=B OP C)外提条件,循环中所有 A的引用点只有 S中的 A的定值才能到达。
例 4
循环不变式外提的条件
S(A:=B OP C)外提条件,
A在循环中其他地方未再定值,才能把循环不变运算 A:=B op C外提 ;
不变运算所在的结点是 L所有出口结点的必经结点,
循环中所有 A的引用点只有 S中的 A的定值才能到达。
查找循环 L的不变运算的算法：
① 依次查看 L中各基本块的每个四元式，如果它的每个运算对象或为常数，或者定值点在 L
外，则将此四元式标记为 "不变运算 ";
② 重复第 3步直至没有新的四元式被标记为 "不变运算 "为止 ;
③ 依次查看尚未被标记为 "不变运算 "的四元式，
如果它的每个运算对象或为常数，或定值点在 L之外，或只有一个到达 -定值点且该点上的四元式已被标记为 "不变运算 "，则把被查看的四元式标记为 "不变运算 "。
代码外提算法,
1,求出 L的所有不变运算
2,对每个不变运算 s:A:=B op C 或 A:=op
B 或 A:=B检查是否满足条件 (1)或 (2)
(1)
(i) s所在的结点是 L所有出口结点的必经结点 ;
(ii) A在 L中其他地方未再定值 ;
(iii) L中所有 A的引用点只有 s中的 A的定值才能到达。
(2) A在离开 L后不再是活跃的，并且条件 (1)
的 (ii)和 (iii)成立。所谓 A在离开 L后不是活跃的是指,A在 L的任何出口结点的后继结点入口处不是活跃的。
3.按步骤 1所找出的不变运算的次序，依次把符合条件 2的条件 (1)或 (2)的不变运算 s
外提到 L的前置结点中。但是，如果 s的运算对象 (B或 C)是在 L中定值的，那么，只有当这些定值四元式都已外提到前置结点中时，才能把 s也外提到前置结点中。
外提循环举例
试分析以下程序哪些代码可以外提？
For I in 1..100 loop
for j in 1..100 loop
For k in 1..100 loop
A(I,J,K):=I*J*K
End loop
End loop
End loop
外提循环举例
假定数组行主为序，则这些循环被翻译成如下样式：
For I in 1..100 loop
for j in 1..100 loop
For k in 1..100 loop
A(I)(J)(K):=(I*J)*K
End loop
End loop
End loop
分析：对于内层循环来说,A(I)(J)和 i*j都是循环不变式。可移至中间的循环。
外提循环举例
将 A(I)(J)和 i*j移至中间的循环后
For I in 1..100 loop
for j in 1..100 loop
t1=adr(a(i)(j))
t2=i*j
For k in 1..100 loop
t1(K):=t2*K
End loop
End loop
End loop
分析：对于第 2层循环来说,A(I）都是循环不变式，可外提。
外提循环举例
将 A(I）外提。
For I in 1..100 loop
T3=adr(a(i))
for j in 1..100 loop
t1=adr(t3(j))
t2=i*j
For k in 1..100 loop
t1(K):=t2*K
End loop
End loop
End loop
比较：外提前执行 300万次下标操作和 200万次乘法操作。
外提后执行 1,010,100次下标操作和 1,010,100次乘法操作。
10.3.2 强度消弱
把程序中执行时间较长的运算转换为执行时间较短的运算。
如：把循环中的乘法运算用递归加法运算来替换。
乘法通常比加法慢 3～ 10倍。因此，强度削弱能够产生显著的加速。
(1) I:=1
(2) if I>10 goto (15)
(4) T2=10*I
(5) T3= T2+ T1
(8) T6=10*I
(9) T7= T6+ T5
(11) T9= T8[T7]
(12) T4[T3]= T9+1
(13) I:=I+1
(14) goto B2
B3
B2
B1
(15)
(3) T1=2*J
(6) T4=addr(A)-11
(7) T5=2*J
(10) T8=addr(A)-11
B2’
(1) I:=1
(2) if I>10 goto (15)
(5) T3= T2+ T1
(9) T7= T6+ T5
(11) T9= T8[T7]
(12) T4[T3]= T9+1
(13) I:=I+1
(4‘ ) T2= T2 +10
(8’) T6= T6 +10
(14) goto B2
B3
B2
B1
(15)
(3) T1=2*J
(6) T4=addr(A)-11
(7) T5=2*J
(10) T8=addr(A)-11
(4) T2=10*I
(8) T6=10*I
B2’
(1) I:=1
(2) if I>10 goto (15)
(5) T3= T2+ T1
(9) T7= T6+ T5
(11) T9= T8[T7]
(12) T4[T3]= T9+1
(13) I:=I+1
(4‘ ) T2= T2 +10
(8’) T6= T6 +10
(14) goto B2
B3
B2
B1
(15)
(3) T1=2*J
(6) T4=addr(A)-11
(7) T5=2*J
(10) T8=addr(A)-11
(4) T2=10*I
(8) T6=10*I
B2’
(1) I:=1
(2) if I>10 goto (15)
(11) T9= T8[T7](12) T
4[T3]= T9+1(13) I:=I+1
(4‘ ) T2= T2 +10(8’) T
6= T6 +10(5‘ ) T
3= T3+ 10(9‘ ) T
7= T7+ 10(14) goto B
2
B3
B2
B1
(15)
(3) T1=2*J(6) T
4=addr(A)-11(7) T
5=2*J(10) T
8=addr(A)-11(4) T
2=10*I(8) T
6=10*I(5) T
3= T2+ T1(9) T
7= T6+ T5
B2’
强度消弱
强度消弱主要是对与 归纳变量 有 线性关系 的变量赋值进行；
经过强度消弱后，循环中可能出现一些新的无用赋值；
对于消弱下标变量地址计算的强度非常有效。
10.3.3 删除归纳变量
如果循环中对变量 I只有唯一的形如 I:=I?C
的赋值，且其中 C为循环不变量，则称 I为循环中的 基本归纳变量 。
如果 I是循环中一基本归纳变量,J在循环中的定值总是可化归为 I的同一线性函数，
也即 J=C1*I? C2,其中 C1和 C2都是循环不变量，则称 J是 归纳变量,并称它与 I同族。一个基本归纳变量也是一归纳变量。
(1) I:=1
(2) if I>10 goto (15)
(11) T9= T8[T7](12) T
4[T3]= T9+1(13) I:=I+1
(4‘ ) T2= T2 +10(8’) T
6= T6 +10(5‘ ) T
3= T3+ 10(9‘ ) T
7= T7+ 10(14) goto B
2
B3
B2
B1
(15)
(3) T1=2*J(6) T
4=addr(A)-11(7) T
5=2*J(10) T
8=addr(A)-11(4) T
2=10*I(8) T
6=10*I(5) T
3= T2+ T1(9) T
7= T6+ T5
B2’
(1) I:=1
(2) if T3>R goto (15)
(11) T9= T8[T7]
(12) T4[T3]= T9+1
(5‘ ) T3= T3+ 10
(9‘ ) T7= T7+ 10
(14) goto B2
B3
B2
B1
(15)
(3) T1=2*J
(6) T4=addr(A)-11
(7) T5=2*J
(10) T8=addr(A)-11
(4) T2=10*I
(8) T6=10*I
(5) T3= T2+ T1
(9) T7= T6+ T5
(21) R=100+T1
B2’
删除归纳变量是在强度削弱以后进行的。强度削弱和删除归纳变量的统一算法框架，其步骤如下：
1,利用循环不变运算信息，找出循环中所有基本归纳变量。
2,找出所有其它归纳变量 A,并找出 A与已知基本归纳变量 X的同族线性函数关系 FA(X)。
3,对 2中找出的每一归纳变量 A,进行强度削弱。
4,删除对归纳变量的无用赋值。
5,删除基本归纳变量。如果基本归纳变量 B在循环出口之后不是活跃的，并且在循环中，
除在其自身的递归赋值中被引用外，只在形如
if B rop Y goto L
中被引用，则可选取一与 B同族的归纳变量
M来替换 B进行条件控制。最后删除循环中对 B的递归赋值的代码。
