编译原理 之 代码优化

第十一章,代码优化,11,1,代码优化技术简介,11,2,局部优化,11,3,控制流程分析和循环,11,4,数据流分析举例,优化分类,按阶段分: 与机器无关的优化-对中间代码进行 依赖于机器的优化-对目标代码进行根据优化所涉及的程序范围分成: (1)局部优化:(基本块) (2)循环优化:对循环中的代码进行优化 (3)全局优化:大范围的优化优化工作数据流分析(data-flow analysis)控制流分析(control-flow analysis) 变换(transformations),优化技术简介: 1.删除多余运算 2.循环不变代码外提 3.强度削弱 4.变换循环控制条件 5.合并已知量与复写传播 6.删除无用赋值 P:=0 for I:=1 to 20 doP:=P+AI*BI,从例子P:=0for I:=1 to 20 doP:=P+AI*BI 看优化技术是什么: (假定数组按每个元素占4个字长编址),(1)P:=0 (2)I:=1(3)T1:=4*I (4)T2:=addr(A)-4 (5)T3:=T2T1 (6)T4:=4*I (7)T5:=addr(B)-4 (8)T6:=T5T4 (9)T7:=T3*T6 (10)P:=P+T7 (11)I:=I+1 (12)if I<=20 goto(3),(1)P:=0 (2)I:=1 (4)T2:=addr(A)-4 (7)T5:=addr(B)-4(3)T1:=4*I (5)T3:=T2T1 (6)T4:=T1 (8)T6:=T5T4 (9)T7:=T3*T6 (10)P:=P+T7 (11)I:=I+1 (12)if I<=20 goto(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:=T2T1 (6)T4:=T1 (8)T6:=T5T4 (9)T7:=T3*T6 (10)P:=P+T7 (11)I:=I+1 (12)if I<=20 goto(3),(1)P:=0 (2)I:=1 (4)T2:=addr(A)-4 (7)T5:=addr(B)-4(5)T3:=T2T1 (6)T4:=T1 (8)T6:=T5T4 (9)T7:=T3*T6 (10)P:=P+T7 (11)I:=I+1(12)if I<=20 goto(5),(3)T1:=4*I,(3)T1:=T1+4,3 强度削弱： 乘法改成加法,(1)P:=0 (2)I:=1 (4)T2:=addr(A)-4 (7)T5:=addr(B)-4 (3)T1:=4*I(5)T3:=T2T1 (6)T4:=T1 (8)T6:=T5T4 (9)T7:=T3*T6 (10)P:=P+T7 (11)I:=I+1 (3)T1:=T1+4 (12)if I<=20 goto(5),(1)P:=0 (2)I:=1 (4)T2:=addr(A)-4 (7)T5:=addr(B)-4(5)T3:=T2T1 (6)T4:=T1 (8)T6:=T5 (9)T7:=T3*T6 (10)P:=P+T7 (11)I:=I+1 (3)T1:=T1+4 (12)if <=80 goto(5),(3)T1:=4,T1,T1,5 合并已知量,4 变换循环控制条件. I的值在变换后不再被引用,5 复写传播,(1)P:=0 (2)I:=1 (4)T2:=addr(A)-4 (7)T5:=addr(B)-4 (3)T1:=4(5)T3:=T2T1 (6)T4:=T1 (8)T6:=T5T1 (9)T7:=T3*T6 (10)P:=P+T7 (11)I:=I+1 (3)T1:=T1+4 (12)if T1<=80 goto(5),(1)P:=0 (4)T2:=addr(A)-4 (7)T5:=addr(B)-4 (3)T1:=4(5)T3:=T2T1 (8)T6:=T5T1 (9)T7:=T3*T6 (10)P:=P+T7 (3)T1:=T1+4 (12)if T1<=80 goto(5),6删除无用赋值 T4后面没有被引用,6删除无用赋值 I后面没有被引用,6删除无用赋值 由(11),I是多余赋值,11.2 局部优化,基本块：是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。 入口语句： 程序的第一个语句；或者， 条件转移语句或无条件转移语句的转移目标语句；或者 紧跟在条件转移语句后面的语句。,划分基本块的算法：,求出四元式程序之中各个基本块的入口语句。 对每一入口语句，构造其所属的基本块。它是由该语句到下一入口语句（不包括下一入口语句），或到一转移语句（包括该转移语句），或到一停语句（包括该停语句）之间的语句序列组成的。 凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，我们可以把它们删除。,(1) read (C) (2) A:= 0 (3) B:= 1 (4) L1: A:=A + B (5) if B>= C goto L2 (6) B:=B+1 (7) goto L1 (8) L2: write (A) (9) halt,基本块的DAG表示及其应用,DAG ( Directed Acyclic Graph) 无环路有向图基本块的DAG是在结点上带有标记的DAG叶结点: 独特的标识符(名字,常数)标记内部结点: 运算符号标记各个结点: 附加标识符标记,用,DAG,进行基本块的优化,四元式,DAG,结点,0,型：,A:=B(:=,B,A),n1,A,B,1,型,: A:=op B(op,B,A),n2 A,op,n1,B,2,型,: A:=B op C(op, B, C,A),A,op,n1,n2,B,C,n1,n2,n1,n3,n1,n2,T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 B:=A T3:=2*T0 T4:=R+r T5:=T3*T4 T6:=R-r B:=T5*T6,T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 B:=A T3:=2*T0 T4:=R+r T5:=T3*T4 T6:=R-r B:=T5*T6,T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 B:=A T3:=2*T0 T4:=R+r T5:=T3*T4 T6:=R-r B:=T5*T6,T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 B:=A T3:=2*T0 T4:=R+r T5:=T3*T4 T6:=R-r B:=T5*T6,T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 B:=A T3:=2*T0 T4:=R+r T5:=T3*T4 T6:=R-r B:=T5*T6,T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 B:=A T3:=2*T0 T4:=R+r T5:=T3*T4 T6:=R-r B:=T5*T6,T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 B:=A T3:=2*T0 T4:=R+r T5:=T3*T4 T6:=R-r B:=T5*T6,T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 B:=A T3:=2*T0 T4:=R+r T5:=T3*T4 T6:=R-r B:=T5*T6,T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 B:=A T3:=2*T0 T4:=R+r T5:=T3*T4 T6:=R-r B:=T5*T6,T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 B:=A T3:=2*T0 T4:=R+r T5:=T3*T4 T6:=R-r B:=T5*T6,G中的代码（2）和（6）的已知量都已合并。 G中的（5）的无用赋值已被删除。 G中的（3）和（7）的公共子表达式R+r只被计算一次，删除了多余运算。,除了可应用DAG进行上述优化外, 还可从基本块的DAG中得到一些其它优化信息：在基本块外被定值并在基本块内被引用的所以标识符，就是作为叶子结点上标识的哪些标识符.在基本块内被定值且该值能在基本块后被引用的所有标识符，就是DGA各结点上的那些附加标识符.,根据有关变量在基本块后被引用的情况，可以进一步删除基本块中的其它无用赋值.假设T0,T1, ,T6在基本块后都没有被引用，则可将上述DAG重写为新的四元式代码序列.,S1=R+r A=6.28*S1 S2=R-r B=A*S2 S1和S2用于存放中间临时变量.,作业：,练习（P271） 1，2,11,3,控制流分析和循环,控制流程图,（流图）：具有唯一首结点的有向图,G=,（,N,，,E,，,n,0,）,N,：结点集,基本块集,E,：有向边集,n,0,：首结点,包含程序第一个,语句的基本块,分析程序流图中结点间的关系 m DOM n 定义在程序流图中,对任意两个结点m和n,如果从流图的首结点出发,到达n的任意通路都要经过m,则称m是n的必经结点,记为m DOM n (a,a DOM a) 必经结点集 定义结点n的所有必经结点的集合,称为结点n的必经结点集,记为D(n).,例,:,6,7,3,4,1,2,3,5,7,6,1,2,1,2,1,2,1,3,begin D(n0) := n0 for nN-n0 do D(n) := N; /*置初值 */ CHANGE := TRUE; while CHANGE do beginCHANGE := FALSEfor nN -n0 do beginNEWD := n D(p); pP(n)if D(n) NEWD then beginCHANGE := TRUE;D(n) := NEWD end end end end,循环的查找,循环的查找算法,回边：假设,a,b,是流图中的一条有向边，如果,b DOM a,，则,称,a,b,是流图中的一条回边。,有向边,nd,是回边，组成的循环是由结点,d,，结点,n,以及有,通路到达,n,而该通路不经过,d,的所有结点组成，并且,d,是该循,环的唯一入口结点。,回边 6 6循环67 4 4,5,6,74 2 2,3,4,5,6,7 循环(结点序列的性质) 1.强连通的(任意两结点间,必有一条通路,且该通路上各结点都属于该结点序列) 2.它们中间有且只有一个是入口结点.,例,:,6,7,3,4,1,2,3,5,7,6,1,2,1,2,1,2,3,1,一些主要的概念,到达-定值 引用-定值链(ud链) 活跃变量 定值-引用链(du链),循环优化,代码外提 删除归纳变量 强度销弱,入口结点循环L,前置结点入口结点循环L ,1,2,3,4,5,