什么是代码优化优化技术简介课件

什么是代码优化优化技术简介第十章代码优化第十章代码优化某些编译程序在中间代码或目标代码生成之后要对生成的代码进行优化。所谓优化，实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。优化可在编译的不同阶段进行，对同一阶段，涉及的程序范围也不同，在同一范围内，可进行多种优化 优化分类优化分类:按阶段分按阶段分与机器无关的优化与机器无关的优化 对中间代码进行对中间代码进行 依赖于机器的优化依赖于机器的优化 对目标代码进行对目标代码进行根据优化所涉及的程序范围分成:(1)局部优化:(基本块)(2)循环优化:对循环中的代码进行优化(3)全局优化:大范围的优化优化工作 数据流分析 控制流分析 优化技术简介1.删除多余运算2.循环不变代码外提3.强度削弱4.变换循环控制条件5.合并已知量与复写传播6.删除无用赋值例：P:=0for:=1 to 20 do P:=P+A*B(1)P:=0(2):=1(3)T1:=4*(4)T2:=addr(A)-4(5)T3:=T2T1(6)T4:=4*(7)T5:=addr(B)-4(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11):=+1(12)if=20 goto(3)1.删除多余运算2.循环不变代码外提(1)P:=0(2):=1(3)T1:=4*(4)T2:=addr(A)-4(5)T3:=T2T1(6)T4:=4*(7)T5:=addr(B)-4(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11):=+1(12)if =20 goto(3)(1)P:=0(2):=1(3)T1:=4*(5)T3:=T2T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11):=+1(12)if=20 goto(3)(4)T2:=addr(A)-4(7)T5:=addr(B)-4(6)T4:=T13.强度削弱(1)P:=0(2):=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11):=+1(12)if=20 goto(3)(1)P:=0(2):=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):=+1(12)if=20 goto(5)(3)T1:=4*I(3)T1:=T1+44.变换循环控制条件5.合并已知量与复写传播(1)P:=0(2):=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11):=+1(3)T1:=T1+4(12)if=20 goto(5)(1)P:=0(2):=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T1(9)T7:=T3*T6(10)P:=P+T7(11):=+1(3)T1:=T1+4(12)if T1 =80 goto(5)(3)T1:=46.删除无用赋值(1)P:=0(2):=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):=+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)局部优化：基本块内的优化基本块：是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。入口语句：、程序的第一个语句；或者，、条件转移语句或无条件转移语句的转移目 标语句；或者、紧跟在条件转移语句后面的语句。划分基本块的算法：、求出四元式程序之中各个基本块的入口语 句。、对每一入口语句，构造其所属的基本块。它是由该语句到下一入口语句（不包括下 一入口语句），或到一转移语句（包括该 转移语句），或到一停语句（包括该停语 句）之间的语句序列组成的。、凡未被纳入某一基本块的语句，都是程序 中控制流程无法到达的语句，因而也是不 会被执行到的语句，我们可以把它们删除。(1)P:=0(2):=1B1(3)T1:=4*(4)T2:=addr(A)-4(5)T3:=T2T1(6)T4:=4*(7)T5:=addr(B)-4(8)T6:=T5T4 B2(9)T7:=T3*T6(10)P:=P+T7(11):=+1(12)if=C goto L2(6)B:=B+1(7)goto L1(8)L2:write(A)(9)halt基本块的基本块的DAG表示表示DAG Directed Acyclic Graph 无环路有向图n1n2n3n4n1n2n3n5n4n6n7n8n9在一个有向图中，我们称任一有向边ninj（或表示为有序对（ni,nj）中的结点ni为结点nj的前驱（父结），结点nj为结点ni的后继（子结）。又称任一有向边序列n1n2,n2n3,nk1nk为从结点n1到结点nk的一条通路。如果其中n1=nk，则称通路为环路。该结点序列也记为（n1,n2,nk）。n1n2n3n4n1n2n3n5n4n6n7n8n9图中有向图的通路（n2,n2）和（n3,n4,n3）就是环路。如果有向图中任一通路都不是环路，则称该有向图为无环路有向图，简称DAG。有向图就是一个DAG。在DAG中，如果（n1,n2,nk）是其中一条通路，则称结点n1为结点nk的祖先，结点nk为结点n1的后代。我们这一节中要用到的有向图，是一种其结点带有标记或附加信息的DAG：1、图的叶结点，即无后继的结点，以一标识符（变量名）或常数作为标记，表示该结点代表该变量或常数的值。如果叶结点用来代表某变量A的地址，则用addr（A）作为该结点的标记。通常把叶结点上作为标记的标识符加上下标0，以表示它是该变量的初值。2、图的内部结点，即有后继的结点以一运算符作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果。3、图中各个结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。上述这种DAG可用来描述计算过程，又称描述计算过程的DAG。在以下的讨论中，我们简称DAG。一个基本块，可用一个DAG来表示。下面列出各种四元式及相对应的DAG的结点形式。1、图中ni为结点编号2、结点下面的符号（运算符、标识符或常 数）是各结点的标记3、各结点右边的标识符是结点的附加标识符。基本块的基本块的DAG表示与构造表示与构造DAG结点结点n1 A B n2 A op n1 B四元式四元式0型：型：A:=B(:=,B,A)1型型:A:=op B(op,B,A)2型型:A:=B op C(op,B,C,A)n3 Aop n1 n2B Cn1n2n1n3n1n2用DAG进行基本块的优化仅含0，1，2型四元式的基本块的DAG构造算法:首先，DAG为空。对基本块的每一四元式，依次执行：DAG构造算法构造算法、如果NODE（B）无定义，则构造一标记为B的叶结点并定义NODE（B）为这个结点；如果当前四元式是0型，则记NODE(B)的值为n，转4。如果当前四元式是1型，则转2(1）。如果当前四元式是2型，则：()如果NODE(1)无定义，则构造一标记为C的叶结点并定义NODE(C)为这个结点；()转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。转处理下一四元式。而后，我们可由DAG重新生成原基本块的一优化的代码序列。构造以下基本块构造以下基本块G的的DAG。To 3.14 (a)n1T0:=3.14 T0 T1 3.14 6.28 (b)n2n1T0:=3.14T1:=2*T0 T2 +T0 T1 3.14 6.28 R r (c)n2n5n3n1n4T0:=3.14T1:=2*T0T2:=R+r A *T2 +T0 T1 3.14 6.28 R r (d)n2n5n3n1n4n6T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2 A,B *T2 +T0 T1 3.14 6.28 R r (e)n2n5n3n1n4n6T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=A A,B *T2 +T0 T1,T3 3.14 6.28 R r (f)n2n5n3n1n4n6T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0 A,B *T2,T4 +T0 T1,T3 3.14 6.28 R r (g)n2n5n3n1n4n6T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+r A,B,T5 *T2,T4 +T0 T1,T3 3.14 6.28 R r (h)n2n5n3n1n4n6T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T6:=R-rT0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T6:=R-rB:=T5*T6DAG的应用我们将四元式表示成DAG后，可以利用DAG进行优化首先由DAG构造优化的四元式序列在构造相应的DAG的过程中已经进行了一些基本的优化工作而后，可由DAG重新生成原基本块的一个优化的代码序列T0:=3.14T1:=6.28T3:=6.28T2:=R+rT4:=T2A:=6.28*T2T5:=AT6:=R-rB:=A*T6T0:=3.14T1:=6.28T3:=6.28T2:=R+rT4:=T2A:=6.28*T2T5:=AT6:=R-rB:=A*T6T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T6:=R-rB:=T5*T6优化后：优化后：例：赋值语句例：赋值语句 T4:=A+B-(E-(C+D)四元式序列四元式序列GT1：=A+BT2：=C+DT3：=E-T2T4：=T1-T3DAG：A B E C Dn9n3n8n1n2n7n6n4n5 T4 T1 T3 T2 +-+控制流分析和循环优化：控制流程图（流图）：具有唯一首结点的有向图G=（N，E，n0）N：结点集 基本块集 E：有向边集 n0：首结点 包含程序第一个语句的基本块分析程序流图中结点间的关系m DOM n 定义（定义（必经结点）在程序流图中,对任意两个结点m和n,如果从流图的首结点出发,到达n的任意通路都要经过m,则称m是n的必经结点,记为m DOM n集集 定义定义 结点结点n的所有的所有的集合,称为结点n的必经结点集,记为D(n).例例:2 6 1 5 7 3 4必经结点和必经结点集必经结点和必经结点集D(1)=1D(2)=1,2D(3)=1,2,3D(4)=1,2,4D(5)=1,2,4,5D(6)=1,2,4,6D(7)=1,2,4,7113 控制流分析和循环控制流分析和循环控制流程图控制流程图（流图）：具有唯一首结点的有向图（流图）：具有唯一首结点的有向图G=（N，E，n0）N：结点集：结点集 基本块集基本块集 E：有向边集：有向边集 n0：首结点：首结点 包含程序第一个包含程序第一个 语句的基本块语句的基本块有有向向边边 基基本本块块 j j 在在程程序序的的位位置置紧紧跟跟在在 i i 后后,且且 i i 的的出出口口语语句句不不是是转转移移或或停停语语句句i i 的的出出口口是是 g go ot to o(S S)或或 i if f g go ot to o(S S),而而(S S)是是 j j 的的入入口口语语句句 i j例例：*(1)read x(20read y*(3)r:=x m od y(4)if r=0 goto(8)*(5)x:=y(6)y:=r(7)goto(3)*(8)w rite y(9)halt(1)read x B1(2)read y(3)r:=x mod y B2(4)if r=0 goto(8)(5)x:=y (8)write y B4(6)y:=r B3 (9)halt(7)goto(3)1 2 4 3分析程序流图中结点间的关系m DOM n 定义定义 在程序流图中,对任意两个结点m和n,如果从流图的首结点出发,到达n的任意通路都要经过m,则称m是n的必经结点,记为m DOM n (a,a MOD a)集 定义定义 结点n的所有的集合,称为结点n的必经结点集,记为D(n).例例:6 73 4 1 2 3 5 7 6 1 2 1 2 1 2 1必经结点必经结点 必经结点集必经结点集D(1)=1D(2)=1,2D(3)=1,2,3D(4)=1,2,4D(5)=1,2,4,5D(6)=1,2,4,6D(7)=1,2,4,7 3循环的查找循环的查找循环的查找算法循环的查找算法回边：假设回边：假设 ab 是流图中的一条有向边，如果是流图中的一条有向边，如果b DOM a，则，则称称 a b 是流图中的一条回边。是流图中的一条回边。有向边有向边 ndnd是回边，组成的循环是由结点是回边，组成的循环是由结点d，结点，结点 n以及有以及有通路到达通路到达 n而该通路不经过而该通路不经过 d的所有结点组成，并且的所有结点组成，并且d是该循是该循环的唯一入口结点。环的唯一入口结点。回边 6 6循环6 7 4 4,5,6,7 4 2 2,3,4,5,6,7循环(结点序列的性质)1.强连通的(任意两结点间,必有一条通路,且该通路上各结点都属于该结点序列)2.它们中间有且只有一个是入口结点.例例:6 73 4 1 2 3 5 7 6 1 2 1 2 1 2 3 1 数据流分析1.活跃变量数据流方程2.到达-定值数据流方程3.讨论 数据流问题分类 路径 数据流方程解不唯一活跃变量的数据流分析所谓活跃变量就是它的当前值还将被引用（在赋予一个新值之前）。在全局范围来分析的话，一个变量是活跃的，如果存在一条路径使得该变量被重新定值之前它的当前值还要被引用。通过全局活跃变量分析，识别出其当前值不再活跃（即，它的值已经死了）的那些变量。死变量的值在基本块的出口处不需要保存。令B为一个基本块，定义LiveIn(B)为在基本块B入口处为活跃的变量的集合。定义LiveOut(B)为基本块B的出口处的活跃变量的集合。LiveIn和LiveOut并不是相互独立的，令S（B）为流图中基本块B的后继的集合，则有 LiveOut(B)=LiveIn(i)is(B)如果基本块没有后继，则其LiveOut为空令LiveUse(B)为B中被定值之前要引用变量的集合。这个集合由 基 本 块 B 中 的 语 句 唯 一 确 定。容 易 看 出，如 果vLiveUse(B)，则vLiveIn(B)；即LiveIn(B)LiveUse(B)。令Def(B)为在B中定值的变量集合。如果一个变量在基本块B的出口处为活跃的且vDef(B)，则它在B的入口处也是活跃的，即：LiveIn(B)LiveOut(B)-Def(B)因此有：LiveIn(B)=LiveUse(B)(LiveOut(B)-Def(B)即：一个变量在基本块入口处为活跃的，则一定有：或者它在基本块的LiveUse集中，或者它在基本块的出口处为活跃的且在基本块中没有重新定值 a:=1;if a=b then b:=1 else c:=1endif;d:=a+ba:=1if a=b goto B2b:=1c:=1d:=a+bB1B2B3B4提取Def和LiveUse集合基本块DefLiveUseB1abB2bB3cB4da,ba:=1if a=b goto B2b:=1c:=1d:=a+bB1B2B3B4从最后一个基本块开始由后往前计算，可以得到一定的解 LiveIn(B)=LiveUse(B)(LiveOut(B)-Def(B)LiveOut(B)=LiveIn(i)is(B)LiveOut(B4)=，因此：LiveIn(B4)=LiveUse(B4)=a,b-d现在LiveOut(B2)=LiveIn(B4)=a,b-dLiveOut(B3)=LiveIn(B4)=a,b-dLiveIn(B2)=LiveOut(B2)-Def(B2)=a,b-b-d=a-dLiveIn(B3)=LiveOut(B3)-Def(B3)=a,b c-d=a,b c-dLiveOut(B1)=LiveIn(B2)LiveIn(B3)=a a,b-d=a,b-d c 最后LiveIn(B1)=LiveUse(B1)(LiveOut(B1)-Def(B1)=b(a,b c-d a)=b-d c a:=1if a=b goto B2b:=1c:=1d:=a+bB1B2B3B4分析程序中所有变量的定值和引用之间的关系到达-定值数据流方程OUTB=(INB-KILLB)GENBINB=OUTp pPB PB:B的所有前驱基本块GENB:B中定值并到达B出口之后的所有定值点集.KILLB:B之外的那些定值点集,其定值的变量在B中 又重新定值.INB:到B入口之前(紧)的各变量的所有定值点集OUTB:到达B出口之后(紧)各变量的所有定值点集.d1 B1 d2 d3 B2 d4 B3 d5 B4 d6 B5 d7 到达一定值I:=2J:=I+1I:=1J:=J+1J:=J-4 :=I :=JGEN位向量KILLB1d1,d211000000011100B2d300100001000000B3d400010000100100B4d500001000101000B5 00000000000000INBOUTBB101111001100000B211111000111100B301111000011000B400110000010100B500111000011100求求解解数数据据流流方方程程(含含 n个个结结点点的的流流图图)begin for i:=1 to n do begin IN Bi:=;OUTBi :=GENBi;end;change:=true;while change do begin change:=false;for i:=1 to n do begin newin:=OUTp;/p PBi if newin INBi then begin change:=ture;INBi:=newin;OUTBi:=(INBi KILLBi)GENBi end end end end应用 -查找循环不变式(量)x:=y+z 条件 y 和 z 的所有可能的定值点在该循环外.ud 链 若 x:=y+z 是循环不变式,w 是循环外定值的.则 v:=x+w 也是循环不变式 -全局优化 入口结点 循环L 前置结点 入口结点 循环L B1 B2 B3 B4 B5(1)i:=1(2)if x y goto B3(5)y:=y-1(6)if y=20 gotoB5(3)i:=2(4)x:=x+1(7)j:=i12345 B1 B2 B2 B3 B4 B5 i:=2 if x y goto B3y:=y-1if y=20 gotoB5x:=x+1 j:=i i:=1 B1 B2 B3 B4 B5(1)I:=1I:=3;(2)if xy goto(3)(3)I:=2(4)x:=x+1(5)y:=y-1(6)if y=20 goto B2(7)J:=I B1 B2 B3 B4 B5(1)I:=1(2)if xy goto(3)(3)I:=2(4)x:=x+1(5)k:=I;y:=y-1(6)if y=20 goto B2(7)J:=I当把循环中的不变运算当把循环中的不变运算s:s:A:=B op C外提时注意：外提时注意：（2）要求循环中其它地方不再有要求循环中其它地方不再有A A的定值点。的定值点。（3 3）要求循环中要求循环中A A的所有引用点都是而且仅仅是这个定值所能的所有引用点都是而且仅仅是这个定值所能达到的达到的（1 1）要求）要求s s所在结点是循环的所有出口结点的必经结点所在结点是循环的所有出口结点的必经结点（4 4）要求）要求A A在离开循环之后不再是活跃的在离开循环之后不再是活跃的数据流问题的讨论合流问题向前流（forward-flow)(信息流的方向与控制流是一致的)和向后流（backward flow）对每个基本块有一个IN集合和一个Out集合,在同一基本块中，In和Out集合的关系对于向前流问题：Out(B)=Used(B)(In(B)Killed(B)对于向后流问题：In(B)=Used(B)(Out(B)Killed(B)作为一个边界条件，向前流问题中的起始基本块的In和向后流问题中最后一个基本块的Out集合必须指明，通常，这些边界条件集或者为空，或者包含所有可能的值，因问题而定。如：到达-定值数据流方程 OUTB=(INB-KILLB)GENB活跃变量数据流方程LiveIn(B)=LiveUse(B)(LiveOut(B)-Def(B)数据流问题的讨论路径问题任意路径数据流分析讨论的数据流假定这么一个性质，即某条路径为真，（如果存在某条路径上被引用这个变量就认为是活跃的；如果存在任何一条路径上被定值，则就认为这个变量是被定值的）。这种数据流问题被称为任意路径问题。任意路径问题的解不能保证所需的性质一定会满足，仅仅是可能满足。全路径数据流分析数据流问题也可以用全路径（all-path）形式来解决，使所需的性质在所有可能的路径都满足。对于全路径问题的解，所需的性质可以保证总是满足。数据流问题的解不一定唯一考察图10.20的流图，其中有一个简单的循环。在这个流图中，没有对任何变量定值，a在B4中被引用。应用向后流方法传播可以得到一个最明显的解，即四个基本块的LiveIn集合均为a。但是，不太合理的解也是可能的。若Def(B1)=Def(B2)=Def(B3)=Def(B4)=Liveuse(B1)=Liveuse(B1)=Liveuse(B1)=Liveuse(B1)=a则最明显的解：LiveIn(B1)=LiveIn(B1)=LiveIn(B1)=LiveIn(B1)=aB1B2B3B4例如，下面解是满足数据流方程的：基本块LiveInLiveOutB1a,ba,bB2a,ba,bB3a,ba,bB4a注意b没有在任何基本块中被引用！问题所在是基本块B2和B3互为祖先；而且，因为b从未定值（所有Def集为空），一旦b被包括在LiveIn集合中，它就永远消除不了简要介绍简要介绍vYacc(Yet Another Compiler-Compiler)基于LALR(1)的语法分析程序的生成器vLex(A Lexical Analyzer Generator)v词法分析程序的生成器，其输入是描述三型语言的正规式，输出是一个相应正规表达式的词法分析程序。