编译原理-之-代码优化

第十一章代码优化11．1代码优化技术简介11．2局部优化11．3控制流程分析和循环11．4数据流分析举例优化分类按阶段分:与机器无关的优化---对中间代码进行依赖于机器的优化---对目标代码进行根据优化所涉及的程序范围分成:(1)局部优化:(基本块)(2)循环优化:对循环中的代码进行优化(3)全局优化:大范围的优化优化工作数据流分析(data-flowanalysis)控制流分析(control-flowanalysis)变换(transformations)优化技术简介:1.删除多余运算2.循环不变代码外提3.强度削弱4.变换循环控制条件5.合并已知量与复写传播6.删除无用赋值P:=0forI:=1to20doP:=P+A[I]*B[I]从例子P:=0forI:=1to20doP:=P+A[I]*B[I]看优化技术是什么:(假定数组按每个元素占4个字长编址)(1)P:=0(2)I:=1(3)T1:=4*I(4)T2:=addr(A)-4(5)T3:=T2[T1](6)T4:=4*I(7)T5:=addr(B)-4(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI=20goto(3)(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI=20goto(3)2.代码外提1.删除多余运算(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI=20goto(3)(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI=20goto(5)(3)T1:=4*I(3′)T1:=T1+43强度削弱：乘法改成加法(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3’)T1:=T1+4(12)ifI=20goto(5)(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3’)T1:=T1+4(12)if=80goto(5)(3)T1:=4T1T15合并已知量4变换循环控制条件.I的值在变换后不再被引用5复写传播(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3’)T1:=T1+4(12)ifT1=80goto(5)(1)P:=0(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2[T1](8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(3’)T1:=T1+4(12)ifT1=80goto(5)6删除无用赋值T4后面没有被引用6删除无用赋值I后面没有被引用6删除无用赋值由(11),I是多余赋值11.2局部优化基本块：是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。入口语句：程序的第一个语句；或者，条件转移语句或无条件转移语句的转移目标语句；或者紧跟在条件转移语句后面的语句。划分基本块的算法：1.求出四元式程序之中各个基本块的入口语句。2.对每一入口语句，构造其所属的基本块。它是由该语句到下一入口语句（不包括下一入口语句），或到一转移语句（包括该转移语句），或到一停语句（包括该停语句）之间的语句序列组成的。3.凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，我们可以把它们删除。(1)read(C)(2)A:=0(3)B:=1(4)L1:A:=A+B(5)ifB=CgotoL2(6)B:=B+1(7)gotoL1(8)L2:write(A)(9)halt划分成四个基本块B1，B2，B3，B4B1(1)(2)(3)基本块内实行的优化:合并已知量删除多余运算B2(4)删除无用赋值(5)B3(6)(7)B4(8)(9)基本块的DAG表示及其应用DAG(DirectedAcyclicGraph)无环路有向图基本块的DAG是在结点上带有标记的DAG•叶结点:独特的标识符(名字,常数)标记•内部结点:运算符号标记•各个结点:附加标识符标记用DAG进行基本块的优化四元式DAG结点0型：A:=B(:=,B,—,A)n1AB1型:A:=opB(op,B,—,A)n2Aopn1B2型:A:=BopC(op,B,C,A)Aopn1n2BCn1n2n1n3n1n2仅含0，1，2型四元式的基本块的DAG构造算法:首先，DAG为空。对基本块的每一四元式，依次执行：1．如果NODE（B）无定义，则构造一标记为B的叶结点并定义NODE（B）为这个结点；如果当前四元式是0型，则记NODE(B)的值为n，转4。如果当前四元式是1型，则转2(1）。如果当前四元式是2型，则：(I)如果NODE(1)无定义，则构造一标记为C的叶结点并定义NODE(1)为这个结点；(II)转2(2)2．（1）如果NODE(B)是标记为常数的叶结点，则转2(3)，否则转3（1）。（2）如果NODE(B)和NODE(C)都是标记为常数的叶结点，则转2（4），否则转3（2）。（3）执行opB（即合并已知量），令得到的新常数为P。如果NODE(B)是处理当前四元式时新构造出来的结点，则删除它。如果NODE(P)无定义，则构造一用P做标记的叶结点n。置NODE(P)=n，转4。（4）执行BopC（即合并已知量），令得到的新常数为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。转处理下一四元式。而后，我们可由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*T6To3.14(a)n1(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*T6T0T13.146.28(b)n2n1(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*T6T2+T0T13.146.28Rr(c)n2n5n3n1n4(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*T6A*T2+T0T13.146.28Rr(d)n2n5n3n1n4n6(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*T6A,B*T2+T0T13.146.28Rr(e)n2n5n3n1n4n6(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*T6A,B*T2+T0T1,T33.146.28Rr(f)n2n5n3n1n4n6(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*T6A,B*T2,T4+T0T1,T33.146.28Rr(g)n2n5n3n1n4n6(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*T6A,B,T5*T2,T4+T0T1,T33.146.28Rr(h)n2n5n3n1n4n6(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*T6A,B,T5*T2,T4T6+-T0T1,T33.146.28Rrn2n5n3n7n1n4n6(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*T6B*A,T5*T2,T4T6+-T0T1,T33.146.28Rr(j)n2n5n3n7n1n4n6n8(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(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(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*T61.G中的代码（2）和（6）的已知量都已合并。2.G中的（5）的无用赋值已被删除。3.G中的（3）和（7）的公共子表达式R+r只被计算一次，删除了多余运算。B*A,T5*T2,T4T6+-T0T1,T33.146.28Rr(j)n2n5n