编译原理 第十章.ppt

《编译原理 第十章.ppt》由会员分享，可在线阅读，更多相关《编译原理 第十章.ppt（72页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第十章第十章 优化优化l优化化：对程序程序进行各种等价行各种等价变换，使得从，使得从变换后的程序出后的程序出发，能生成更有效的目，能生成更有效的目标代代码。等价等价：指不改：指不改变程序的运行程序的运行结果。果。有效有效：指目：指目标代代码运行运行时间短，占用的存短，占用的存储空空间小。小。编译前端编译前端代码优化器代码优化器编译后端编译后端控制流分析控制流分析数据流分析数据流分析代码变换代码变换10.1 10.1 概述概述l优化的目的是化的目的是为了了产生更高效的代生更高效的代码。由。由优化化编译程序提供的程序提供的对代代码的各种的各种变换必必须遵循一定的原遵循一定的原则：等价原等价原则：经

2、过优化后不化后不应改改变程序运行的程序运行的结果；果；有效原有效原则：使：使优化后所化后所产生的目生的目标代代码运行运行时间较短，占用的存短，占用的存储空空间较小；小；合算原合算原则：应尽可能以尽可能以较低的代价取得低的代价取得较好的好的优化效果。化效果。10.1 10.1 概述概述l优化的种化的种类：删除多余运算除多余运算(或称或称删除公用子表达式除公用子表达式)代代码外提外提强度消弱度消弱变换循循环控制条件控制条件合并已知量合并已知量复写复写传播播删除无用除无用赋值l优化的三个不同化的三个不同级别：局部局部优化化循循环优化化全局全局优化化void quicksort(m,n);int m,

3、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 iv);if(i=j)break;x=a i;ai=a j;aj=x;x=ai;ai=a n;a n=x;/*fragment ends here*/quicksort(m,j);quicksort(i+1,n);q中间代码程序段中间代码程序段 i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6

4、:=4*ix:=a T6T7:=4*iT8:=4*jT9:=a T8a T7=T9T10:=4*j a T10=xgoto B2B5T11:=4*ix:=a T11T12:=4*iT13:=4*nT14:=a T13a T12=T14T15:=4*na T15=xB6q中间代码程序段中间代码程序段 i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6:=4*ix:=a T6T7:=4*iT8:=4*jT9:=a T8a T7=T9T10:=4*j a T10=xgoto B2B5T11:

5、=4*ix:=a T11T12:=4*iT13:=4*nT14:=a T13a T12=T14T15:=4*na T15=xB6q删除公用子表达式后删除公用子表达式后i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6:=T2x:=a T6T7:=T6T8:=T4T9:=a T8a T7=T9T10:=T8a T10=xgoto B2B5T11:=T2x:=a T11T12:=T11T13:=T1T14:=a T13a T12=T14T15:=T13a T15=xB6q复写传播复写传播i

6、:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6:=T2x:=a T6T7:=T6T8:=T4T9:=a T8a T7=T9T10:=T8a T10=xgoto B2B5T11:=T2x:=a T11T12:=T11T13:=T1T14:=a T13a T12=T14T15:=T13a T15=xB6q复写传播复写传播(一一)后后i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T

7、6:=T2x:=aT2T7:=T2T8:=T4T9:=a T4a T2=T9T10:=T4a T4=xgoto B2B5T11:=T2x:=a T2T12:=T2T13:=T1T14:=a T1a T2=T14T15:=T1a T1=xB6q复写传播复写传播(一一)后后i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6:=T2x:=aT2T7:=T2T8:=T4T9:=a T4a T2=T9T10:=T4a T4=xgoto B2B5T11:=T2x:=a T2T12:=T2T13:=

8、T1T14:=a T1a T2=T14T15:=T1a T1=xB6q复写传播复写传播(二二)后后i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4T6:=T2x:=T3T7:=T2T8:=T4T9:=T5a T2=T5T10:=T4a T4=T3goto B2B5T11:=T2x:=T3T12:=T2T13:=T1T14:=va T2=vT15:=T1a T1=T3B6q删除无用赋值删除无用赋值i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2i

9、f T3v goto B3B3if i=j goto B6B4T6:=T2x:=T3T7:=T2T8:=T4T9:=T5a T2=T5T10:=T4a T4=T3goto B2B5T11:=T2x:=T3T12:=T2T13:=T1T14:=va T2=vT15:=T1a T1=T3B6q删除无用赋值后删除无用赋值后 i:=m-1j:=nT1:=4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4a T2=T5a T4=T3goto B2B5a T2=va T1=T3B6q强度削弱强度削弱 i:=m-1j:=nT1:=

10、4*nv:=aT1B1i:=i+1T2:=4*i T3:=aT2if T3v goto B3B3if i=j goto B6B4a T2=T5a T4=T3goto B2B5a T2=va T1=T3B6q强度削弱后强度削弱后 i:=m-1j:=nT1:=4*nv:=aT1T2:=4*iT4:=4*jB1i:=i+1T2:=T2+4 T3:=aT2if T3v goto B3B3if i=j goto B6B4a T2=T5a T4=T3goto B2B5a T2=va T1=T3B6q删除归纳变量删除归纳变量i:=m-1j:=nT1:=4*nv:=aT1T2:=4*iT4:=4*jB1i:=

11、i+1T2:=T2+4 T3:=aT2if T3v goto B3B3if i=j goto B6B4a T2=T5a T4=T3goto B2B5a T2=va T1=T3B6q删除归纳变量后删除归纳变量后i:=m-1j:=nT1:=4*nv:=aT1T2:=4*iT4:=4*jB1T2:=T2+4 T3:=aT2if T3v goto B3B3if T2=T4 goto B6B4a T2=T5a T4=T3goto B2B5a T2=va T1=T3B610.210.2 局部局部优化化l基本基本块：指程序中一：指程序中一顺序序执行行语句序列，其中只句序列，其中只有一个入口和一个出口。入口就

12、是其中第一个有一个入口和一个出口。入口就是其中第一个语句，出口就是其中最后一个句，出口就是其中最后一个语句。句。T1:=a*a T2:=a*b T3:=2*T2 T4:=T1+T2 T5:=b*b T6:=T4+T5q如果一条三地址语句为如果一条三地址语句为x:=y+z，则称对则称对x定值定值并并引用引用y和和z。q在一个基本块中的一个名字，在一个基本块中的一个名字，所谓在程序中的某个给定点是所谓在程序中的某个给定点是活跃的活跃的，是指如果在程序中，是指如果在程序中(包包括在本基本块或在其它基本块括在本基本块或在其它基本块中中)它的值在该点以后被引用。它的值在该点以后被引用。10.210.2局

13、部局部优化化l局限于基本局限于基本块范范围内的内的优化称化称为基本基本块内的内的优化化，或称，或称局部局部优化化。l在一个基本在一个基本块内通常可以内通常可以实行下面的行下面的优化化:删除公共子表达式除公共子表达式删除无用除无用赋值合并已知量合并已知量临时变量改名量改名交交换语句的位置句的位置代数代数变换l划分四元式程序划分四元式程序为基本基本块的算法的算法:1.1.求出四元式程序中各个基本求出四元式程序中各个基本块的入口的入口语句句:1)1)程序第一个程序第一个语句，或句，或2)2)能由条件能由条件转移移语句或无条件句或无条件转移移语句句转移到的移到的语句，或句，或3)3)紧跟在条件跟在条件

14、转移移语句后面的句后面的语句。句。l划分四元式程序划分四元式程序为基本基本块的算法的算法:2.2.对以上求出的每个入口以上求出的每个入口语句，确定其所属句，确定其所属的基本的基本块。它是由。它是由该入口入口语句到下一入口句到下一入口语句句(不包括不包括该入口入口语句句)、或到一、或到一转移移语句句(包包括括该转移移语句句)、或一停、或一停语句句(包括包括该停停语句句)之之间的的语句序列句序列组成的。成的。3.3.凡未被凡未被纳入某一基本入某一基本块中的中的语句，可以从句，可以从程序中程序中删除。除。l例：划分基本例：划分基本块(1)read X(2)read Y(3)R:=X mod Y(4)

15、if R=0 goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)write Y(9)haltl例：划分基本例：划分基本块(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)haltl例：划分基本例：划分基本块(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)haltl例：划分基本例：划分基本块(1)read X(2)read Y(3)R:=X

16、 mod Y(4)if R=0 goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)write Y(9)haltl例：划分基本例：划分基本块(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优化措施化措施l合并已知量合并已知量 T T1 1:=2:=2 T T2 2:=4*T:=4*T1 1变换成成T T2 2:=8:=8l临时变量改名量改名 T:=b+c其中其中T是一个是一个临时变量名。把量名。把这个个语句改成：句改成：S:=b+c优化措施化措施l交

17、交换语句的位置句的位置 T1:=b+c T2:=x+y l代数代数变换 x:=x+0或或 x:=x*1 x:=y*2变换成成x:=y*y流流图l每个流每个流图以基本以基本块为结点。如果一个点。如果一个结点的基点的基本本块的入口的入口语句是程序的第一条句是程序的第一条语句，句，则称此称此结点点为首首结点。如果在某个点。如果在某个执行行顺序中，基本序中，基本块B2紧接在基本接在基本块B1之后之后执行，行，则从从B1到到B2有有一条有向一条有向边。即，如果。即，如果有一个条件或无条件有一个条件或无条件转移移语句从句从B1的最后一的最后一条条语句句转移到移到B2的第一条的第一条语句；或者句；或者在程序

18、的序列中，在程序的序列中，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 YB1B2B3B410.2.210.2.2基

19、本基本块的的DAGDAG表示及其表示及其应用用有向有向图有向有向边:ninj前前驱：ni是是nj的前的前驱后后继：nj是是ni的后的后继通路通路:n1n2,n2n3,.,nk-1nk环路：路：n1=nk DAG：无无环路有向路有向图(Directed Acyclic Graph)n1n2n3n4n1n2n3n47.1.2 图表示法表示法l图表示法表示法DAG抽象抽象语法法树 l无循无循环有向有向图(Directed Acyclic Graph，简称称DAG)对表达式中的每个子表达式，表达式中的每个子表达式，DAG中都有一个中都有一个结点点一个内部一个内部结点代表一个操作符，它的孩子代表操点代表

20、一个操作符，它的孩子代表操作数作数在一个在一个DAG中代表公共子表达式的中代表公共子表达式的结点具有多个点具有多个父父结点点 a:=b*(-c)+b*(-c)的图表示法 assigna+*buminuscDAGassigna+*buminusc抽象语法树抽象语法树*buminusc T1:=-c T1:=-c T2:=b*T1T2:=b*T1T3:=-cT5:=T2+T2 T4:=b*T3a:=T5 T5:=T2+T4 a:=T5对于抽象于抽象语法法树的代的代码对于于DAG的代的代码l描述描述计算算过程的程的DAG是一种是一种带有下述有下述标记或附或附加信息的加信息的DAG:1.图的叶的叶结点

21、以一点以一标识符或常数作符或常数作为标记，表示，表示该结点代表点代表该变量或常数的量或常数的值;2.图的内部的内部结点以一运算符作点以一运算符作为标记，表示，表示该结点代表点代表应用用该运算符运算符对其后其后继结点所代表的点所代表的值进行运算的行运算的结果果;3.图中各个中各个结点上可能附加一个或多个点上可能附加一个或多个标识符符(称附加称附加标识符符)表示表示这些些变量具有量具有该结点所代点所代表的表的值。10.2.2 10.2.2 基本基本块的的DAGDAG表示及表示及应用用l一个基本一个基本块，可用一个，可用一个DAG来表示与各四来表示与各四元式相元式相对应的的DAG结点形式点形式:四元

22、式四元式 DAG 图(0)0型型:A:=B (:=，B，-，A)n1AB四元式四元式 DAG 图(1)1型型:A:=op B (op，B，-，A)n1ABn2op(2)2型型:A:=B op C (op，B，C，A)n2ABn1opn3C四元式四元式 DAG 图图(3)2型型:A:=BC (=，BC，-，A)n2ABn1=n3C(4)2型型:if B rop C goto(s)(jrop，B，C，(s)n2(s)Bn1ropn3C四元式四元式 DAG 图图(5)3型型:DC:=B (=，B，-，DC)(6)0型型:goto(s)(j，-，-，(s)(s)n1n2Bn1=n4Cn3Dl假假设DA

23、G各各结点信息将用某种适当的数据点信息将用某种适当的数据结构存放构存放(如如链表表)。另。另设置一个置一个标识符与符与结点的点的对应函数函数:l0 0，1 1，2 2型四元式的基本型四元式的基本块的的DAGDAG构造算法构造算法对基本基本块中每一四元式，依次中每一四元式，依次执行以下步行以下步骤:1.1.准准备操作数的操作数的结点点 2.2.合并已知量合并已知量3.3.删除除公共子表达式公共子表达式4.4.删除无用除无用赋值1.1.准准备操作数的操作数的结点点 如果如果NODE(B)NODE(B)无定无定义，则构造一构造一标记为B B的叶的叶结点并定点并定义NODE(B)NODE(B)为这个个

24、结点点;如果当前四元式是如果当前四元式是0 0型，型，则记NODE(B)NODE(B)的的值为n n，转4 4。如果当前四元式是如果当前四元式是1 1型，型，则转2(1)2(1)如果当前四元式是如果当前四元式是2 2型，型，则(i)i)如果如果NODE(C)NODE(C)无定无定义，则构造一构造一标记为C C的叶的叶结点并定点并定义NODE(C)NODE(C)为这个个结点；点；(ii)ii)转2(2)2(2)。2.2.合并已知量合并已知量(1)(1)如果如果NODE(B)NODE(B)是是标记为常数的叶常数的叶结点，点，则转2(3)2(3)；否；否则，转3(1)3(1)。(2)(2)如果如果N

25、ODE(B)NODE(B)和和NODE(C)NODE(C)都是都是标记为常数的叶常数的叶结点，点，则转2(4)2(4)；否；否则，转3(2)3(2)。(3)(3)执行行op B(op B(即合并已知量即合并已知量)。令得到的新常数。令得到的新常数为P P。如如果果NODE(B)NODE(B)是是处理当前四元式理当前四元式时新构造出来的新构造出来的结点，点，则删除它。如果除它。如果NODE(P)NODE(P)无定无定义，则构造一用构造一用P P作作标记的叶的叶结点点n n。置置NODE(P)=nNODE(P)=n，转4 4。(4)(4)执行行B op C(B op C(即合并已知量即合并已知量)

26、。令得到的新常数。令得到的新常数为P P。如果如果NODE(B)NODE(B)或或NODE(C)NODE(C)是是处理当前四元式理当前四元式时新构造新构造出来的出来的结点，点，则删除它。如果除它。如果NODE(P)NODE(P)无定无定义，则构构造一用造一用P P作作标记的叶的叶结点点n n。置置NODE(P)=nNODE(P)=n，转4 4。3.3.寻找公共子表达式找公共子表达式(1)(1)检查DAGDAG中是否已有一中是否已有一结点，其唯一后点，其唯一后继为NODE(B)NODE(B)且且标记为op(op(即公共子表达式即公共子表达式)。如果没。如果没有，有，则构造构造该结点点n n，否否

27、则，把已有的，把已有的结点作点作为它的它的结点并点并设该结点点为n n。转4 4。(2)(2)检查DAGDAG中是否已有一中是否已有一结点，其左后点，其左后继为NODE(B)NODE(B)，右后右后继为NODE(C)NODE(C)，且且标记为op(op(即公即公共子表达式共子表达式)。如果没有，。如果没有，则构造构造该结点点n n，否否则，把已有的把已有的结点作点作为它的它的结点并点并设该结点点为n n。转4 4。4.4.删除无用除无用赋值 如果如果NODE(A)NODE(A)无定无定义，则把把A A附加在附加在结点点n n上并令上并令NODE(A)=n;NODE(A)=n;否否则，先把，先把

28、A A从从NODE(A)NODE(A)结点上的附加点上的附加标识符集中符集中删除除(注意，如果注意，如果NODE(A)NODE(A)是叶是叶结点，点，则其其A A标记部不部不删除除)。把。把A A附加到新附加到新结点点n n上并置上并置NODE(A)=nNODE(A)=n。转处理下一四元式。理下一四元式。l例例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.14n13

29、.14T0n26.28T1n3n4Rrn5+T2n6*A,B,T3,T4,T5n7T6-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*T6T6q优化后的四元式优化后的四元式(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*T6n13.14T0n26.28T1n3n4Rrn5+T2n6*A,B,T3,T4,T5n7T6-n

30、8*BT6l从从DAGDAG中中还能得到其他的能得到其他的优化信息：化信息：在基本在基本块外被定外被定值并在基本并在基本块内被引用的所内被引用的所有有标识符，就是作符，就是作为叶子叶子结点上点上标记的那些的那些标识符。符。在基本在基本块内被定内被定值并且并且该值在基本在基本块后面可后面可以被引用的所有以被引用的所有标识符，就是符，就是DAGDAG各各结点上的点上的那些附加那些附加标识符。符。10.3 10.3 循循环优化化l对循循环中的代中的代码，可以，可以实行：行：代代码外提外提强度消弱度消弱删除除归纳变量量(变换循循环控制条件控制条件)循循环展开展开循循环合并合并 10.3.1 10.3.

31、1 代代码外提外提l循循环不不变运算运算:对四元式四元式A:=B op C,A:=B op C,若若B B和和C C是常是常数，或者到达它数，或者到达它们的的B B和和C C的定的定值点都在循点都在循环外。外。l所所谓变量量A A在某点在某点d d的的定定值到达到达另一点另一点u u（或称或称变量量A A的定的定值点点d d到达另一点到达另一点u u），），是指流是指流图中从中从d d有一通路有一通路到达到达u u且且该通路上没有通路上没有A A的其它定的其它定值。d d:A:=B op Cu u:D:=A op El把循把循环不不变运算提到循运算提到循环体外。体外。入口结点入口结点循环循环L

32、入口结点入口结点循环循环L前置结点前置结点l代代码外提条件外提条件for I:=1 to 10 doAI,2*J:=AI,2*J+1(1)I:=1(2)if I10 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=T8T7(12)T4T3=T9+1(13)I:=I+1(14)goto B2B3B2B1(15)(1)I:=1(2)if I10 goto(15)(4)T2=10*I(5)T3=T2+T1(8)T6=10*I(9)T7

33、=T6+T5(11)T9=T8T7(12)T4T3=T9+1(13)I:=I+1(14)goto B2B3B2B1(15)(3)T1=2*J(6)T4=addr(A)-11(7)T5=2*J(10)T8=addr(A)-11B2(1)I:=1(2)if XY goto B3B1B2(3)I:=2(4)X:=X+1(5)Y:=Y-1(6)if Y=20 goto B5(7)J:=IB3B4B5X=30,Y=25B1 B2 B4 B2 B4 B2 B4 B5J=1,I=1(3)I:=2(2)if XY goto B3B1B2(4)X:=X+1(5)Y:=Y-1(6)if Y=20 goto B5(

34、7)J:=IB3B4B5(1)I:=1B2X=30,Y=25B1 B2 B4 B2 B4 B2 B4 B5J=2,I=2代代码外提条件外提条件:不不变运算所在的运算所在的结点是点是L L所有出口所有出口结点的必点的必经结点点.(1)I:=1(2)I:=3(2)if XY goto B3B1B2(3)I:=2(4)X:=X+1(5)Y:=Y-1(6)if Y=20 goto B5(7)J:=IB3B4B5考考虑:B2 B3 B4 B2 B4 B5I=3,J=3(2)I:=3(2)if XY goto B3B1B2(3)I:=2(4)X:=X+1(5)Y:=Y-1(6)if Y=20 goto B

35、5(7)J:=IB3B4B5(1)I:=1B2考考虑:B2 B3 B4 B2 B4 B5I=2,J=2代代码外提条件外提条件:A在循在循环中其他地方未再定中其他地方未再定值,才能才能把循把循环不不变运算运算A:=B op C外提外提;考考虑:X=0,Y=2 B2 B3 B4 B2 B4 B5A=2,J=2(1)I:=1(2)if XY goto B3B1B2(3)A:=I+1(4)X:=X+1(5)I:=2(6)Y:=Y-1(7)if Y=0 goto B5(8)J:=AB3B4B5(5)I:=2(2)if XY goto B3B1B2(3)A:=I+1(4)X:=X+1(6)Y:=Y-1(7

36、)if Y10 goto(15)(4)T2=10*I(5)T3=T2+T1(8)T6=10*I(9)T7=T6+T5(11)T9=T8T7(12)T4T3=T9+1(13)I:=I+1(14)goto B2B3B2B1(15)(3)T1=2*J(6)T4=addr(A)-11(7)T5=2*J(10)T8=addr(A)-11B2(1)I:=1(2)if I10 goto(15)(5)T3=T2+T1(9)T7=T6+T5(11)T9=T8T7(12)T4T3=T9+1(13)I:=I+1(4)T2=T2+10(8)T6=T6+10(14)goto B2B3B2B1(15)(3)T1=2*J(

37、6)T4=addr(A)-11(7)T5=2*J(10)T8=addr(A)-11(4)T2=10*I(8)T6=10*IB2(1)I:=1(2)if I10 goto(15)(5)T3=T2+T1(9)T7=T6+T5(11)T9=T8T7(12)T4T3=T9+1(13)I:=I+1(4)T2=T2+10(8)T6=T6+10(14)goto B2B3B2B1(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*IB2(1)I:=1(2)if I10 goto(15)(11)T9=T8T7(12)

38、T4T3=T9+1(13)I:=I+1(4)T2=T2+10(8)T6=T6+10(5)T3=T3+10(9)T7=T7+10(14)goto B2B3B2B1(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+T5B2l强度消弱度消弱强度消弱主要是度消弱主要是对与与归纳变量有量有线性关系的性关系的变量量赋值进行；行；经过强度消弱后，循度消弱后，循环中可能出中可能出现一些新的无一些新的无用用赋值；对于消弱下于消弱下标变量地址量地址计算的算的强度非常有效。度非

39、常有效。10.3.3 10.3.3 删除除归纳变量量l如果循如果循环中中对变量量I只有唯一的形如只有唯一的形如I:=I C的的赋值，且其中，且其中C为循循环不不变量，量，则称称I为循循环中的中的基本基本归纳变量量。l如果如果I是循是循环中一基本中一基本归纳变量，量，J在循在循环中的定中的定值总是可化是可化归为I的同一的同一线性函数，性函数，也即也即J=C1*I C2，其中其中C1和和C2都是循都是循环不不变量，量，则称称J是是归纳变量量，并称它与，并称它与I同族。同族。一个基本一个基本归纳变量也是一量也是一归纳变量。量。(1)I:=1(2)if I10 goto(15)(11)T9=T8T7(

40、12)T4T3=T9+1(13)I:=I+1(4)T2=T2+10(8)T6=T6+10(5)T3=T3+10(9)T7=T7+10(14)goto B2B3B2B1(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+T5B2(1)I:=1(2)if T3R goto(15)(11)T9=T8T7(12)T4T3=T9+1(5)T3=T3+10(9)T7=T7+10(14)goto B2B3B2B1(15)(3)T1=2*J(6)T4=addr(A)-11(

41、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+T1B2l删除除归纳变量是在量是在强度削弱以后度削弱以后进行的。行的。强度削弱和度削弱和删除除归纳变量的量的统一算法框架，其一算法框架，其步步骤如下：如下：1.利用循利用循环不不变运算信息，找出循运算信息，找出循环中所有基本中所有基本归纳变量。量。2.找出所有其它找出所有其它归纳变量量A，并找出并找出A与已知基本与已知基本归纳变量量X的同族的同族线性函数关系性函数关系 FA(X)。3.对2中找出的每一中找出的每一归纳变量量A，进行行强度削弱。度削弱。4.删除除对归纳变量的无用量的无用赋值。5.删除基本除基本归纳变量。如果基本量。如果基本归纳变量量B在在循循环出口之后不是活出口之后不是活跃的，并且在循的，并且在循环中，中，除在其自身的除在其自身的递归赋值中被引用外，只在形中被引用外，只在形如如 if B rop Y goto L 中被引用，中被引用，则可可选取一与取一与B同族的同族的归纳变量量M来替来替换B进行条件控制。最后行条件控制。最后删除循除循环中中对B的的递归赋值的代的代码。作作业lP306-1，2，3，4，5