编译原理代码优化.ppt

第八章 代码优化,8.1 什么是代码优化8.2 局部优化8.3 循环优化8.4 数据流分析,2,2023/10/4,中南大学软件学院 陈志刚,8.1 什么是代码优化,1、优化：对程序进行各种等价变换，使变换后的程序能生成更有效的目标代码。优化可在编译的任何阶段进行，但最主要的一类优化是对中间代码进行优化。2、常见的优化方式 删除多余运算（又称删除公共子表达式）代码外提：循环体中不变的运算提到循环体外 强度削弱：把乘法变成加法,3,2023/10/4,中南大学软件学院 陈志刚,变换循环控制条件：目的是删除那些纯粹为控制循环而设立的语句，因此又称删除归纳变量。合并已知量：对于那些编译时便可静态确定的运算结果事先运算出来，不必等到运行程序时再执行。复写传播：某些变量的值并未被改变，便赋给其他变量，则可直接引用原值本身。删除无用赋值：有些变量在赋值后并未引用，却又被重新赋值了，称为无用赋值（前面的赋值）,4,2023/10/4,中南大学软件学院 陈志刚,3、优化分类,按阶段分:与机器无关的优化-对中间代码进行 依赖于机器的优化-对目标代码进行根据优化所涉及的程序范围分成:(1)局部优化:在程序基本块内进行的优化。(2)循环优化:在程序循环体内进行的优化。(3)全局优化:在整个程序范围内进行的优化。优化工作 数据流分析(control-flow analysis)控制流分析(data-flow analysis)变换(transformations),5,2023/10/4,中南大学软件学院 陈志刚,4、优化技术简介 1.删除多余运算 2.循环不变代码外提 3.强度削弱 4.变换循环控制条件 5.合并已知量与复写传播 6.删除无用赋值例：P:=0 for I:=1 to 20 do P:=P+AI*BI,6,2023/10/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(3)T1:=4*I(5)T3:=T2T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)if I=20 goto(3),(4)T2:=addr(A)-4(7)T5:=addr(B)-4,(6)T4:=T1,7,2023/10/4,中南大学软件学院 陈志刚,(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,8,2023/10/4,中南大学软件学院 陈志刚,(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,9,2023/10/4,中南大学软件学院 陈志刚,(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),10,2023/10/4,中南大学软件学院 陈志刚,对程序以基本块为范围来讨论的优化，称为局部优化。基本块：指程序中一顺序执行的语句序列，它只有一个入口语句和一个出口语句。基本块的入口语句：1.程序的第一个语句；或者，2.条件转移语句或无条件转移语句的转移目标语句；或者 3.紧跟在条件转移语句后面的语句。,8.2 局部优化：基本块内的优化,11,2023/10/4,中南大学软件学院 陈志刚,基本块的划分1、求基本块入口语句2、寻找基本块 从入口语句到下一入口语句（不包括该入口）；从入口语句到下一转移语句（包括转移语句）；从入口语句到下一停止语句（包括该停止语句）。3、基本块的整理 程序中所有基本块之外的语句为无用语句，应删除。基本块优化 在一个基本块内通常可实行三种优化：合并已知量、删除无用赋值（难判断）以及删除多余运算。,12,2023/10/4,中南大学软件学院 陈志刚,例：(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,13,2023/10/4,中南大学软件学院 陈志刚,14,2023/10/4,中南大学软件学院 陈志刚,基本块的DAG表示及其应用,DAG Directed Acyclic Graph 无环路有向图基本块的DAG是在结点上带有标记的DAG 叶结点 独特的标识符(名字,常数)标记 内部结点 运算符号标记 各个结点 附加标识符标记,15,2023/10/4,中南大学软件学院 陈志刚,用,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),n3 A,op,n1,n2,B,C,n1,n2,n1,n3,n1,n2,16,2023/10/4,中南大学软件学院 陈志刚,17,2023/10/4,中南大学软件学院 陈志刚,18,2023/10/4,中南大学软件学院 陈志刚,19,2023/10/4,中南大学软件学院 陈志刚,例：,20,2023/10/4,中南大学软件学院 陈志刚,21,2023/10/4,中南大学软件学院 陈志刚,22,2023/10/4,中南大学软件学院 陈志刚,23,2023/10/4,中南大学软件学院 陈志刚,24,2023/10/4,中南大学软件学院 陈志刚,25,2023/10/4,中南大学软件学院 陈志刚,26,2023/10/4,中南大学软件学院 陈志刚,27,2023/10/4,中南大学软件学院 陈志刚,28,2023/10/4,中南大学软件学院 陈志刚,29,2023/10/4,中南大学软件学院 陈志刚,控制流程图,（流图）：具有唯一首结点的有向图,G=,（,N,，,E,，,n,0,）,N,：结点集,基本块集,E,：有向边集,n,0,：首结点,包含程序第一个,语句的基本块,8.3 循环优化,30,2023/10/4,中南大学软件学院 陈志刚,31,2023/10/4,中南大学软件学院 陈志刚,32,2023/10/4,中南大学软件学院 陈志刚,33,2023/10/4,中南大学软件学院 陈志刚,34,2023/10/4,中南大学软件学院 陈志刚,分析程序流图中结点间的关系m DOM n 定义 在程序流图中,对任意两个结点m和n,如果从流图的首结点出发,到达n的任意通路都要经过m,则称m是n的必经结点,记为m DOM n(a,a MOD a)必经结点集 定义 结点n的所有必经结点的集合,称为结点n的必经结点集,记为D(n).,35,2023/10/4,中南大学软件学院 陈志刚,例,:,6,7,3,4,1,2,3,5,7,6,1,2,1,2,1,2,1,3,36,2023/10/4,中南大学软件学院 陈志刚,循环的查找,循环的查找算法,回边：假设,a,b,是流图中的一条有向边，如果,b DOM a,，则,称,a,b,是流图中的一条回边。,有向边,nd,是回边，组成的循环是由结点,d,，结点,n,以及有,通路到达,n,而该通路不经过,d,的所有结点组成，并且,d,是该循,环的唯一入口结点。,循环(结点序列的性质)1.强连通的(任意两结点间,必有一条通路,且该通路上各结点都属于该结点序列)2.它们中间有且只有一个是入口结点.,37,2023/10/4,中南大学软件学院 陈志刚,8.4 数据流分析,1.活跃变量数据流方程2.到达-定值数据流方程3.讨论 数据流问题分类 路径 数据流方程解不唯一,38,2023/10/4,中南大学软件学院 陈志刚,活跃变量的数据流分析,所谓活跃变量就是它的当前值还将被引用（在赋予一个新值之前）。在全局范围来分析的话，一个变量是活跃的，如果存在一条路径使得该变量被重新定值之前它的当前值还要被引用。通过全局活跃变量分析，识别出其当前值不再活跃（即，它的值已经死了）的那些变量。死变量的值在基本块的出口处不需要保存。,39,2023/10/4,中南大学软件学院 陈志刚,令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集中，或者它在基本块的出口处为活跃的且在基本块中没有重新定值,40,2023/10/4,中南大学软件学院 陈志刚,a:=1;if a=b then b:=1 else c:=1endif;d:=a+b,41,2023/10/4,中南大学软件学院 陈志刚,提取Def和LiveUse集合,42,2023/10/4,中南大学软件学院 陈志刚,从最后一个基本块开始由后往前计算，可以得到一定的解 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,43,2023/10/4,中南大学软件学院 陈志刚,分析程序中所有变量的定值和引用之间的关系,到达-定值数据流方程OUTB=(INB-KILLB)GENBINB=OUTp pPBPB:B的所有前驱基本块GENB:B中定值并到达B出口之后的所有定值点集.KILLB:B之外的那些定值点集,其定值的变量在B中 又重新定值.INB:到B入口之前(紧)的各变量的所有定值点集OUTB:到达B出口之后(紧)各变量的所有定值点集.,44,2023/10/4,中南大学软件学院 陈志刚,45,2023/10/4,中南大学软件学院 陈志刚,B,3,0111100,0011000,B,4,0011000,0010100,B,5,0011100,0011100,46,2023/10/4,中南大学软件学院 陈志刚,47,2023/10/4,中南大学软件学院 陈志刚,48,2023/10/4,中南大学软件学院 陈志刚,入口结点 循环L,前置结点 入口结点 循环L,49,2023/10/4,中南大学软件学院 陈志刚,50,2023/10/4,中南大学软件学院 陈志刚,1,2,3,4,5,51,2023/10/4,中南大学软件学院 陈志刚,52,2023/10/4,中南大学软件学院 陈志刚,B,1,B,2,B,3,B,4,B,5,(1)I:=1,I:=3;(2)if xy goto(3),(3)I:=2,(4)x:=x+1,(5)y:=y-1,(6)if y,=20,goto B,2,(7)J:=I,53,2023/10/4,中南大学软件学院 陈志刚,B,1,B,2,B,3,B,4,B,5,(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 B,2,(7)J:=I,54,2023/10/4,中南大学软件学院 陈志刚,当把循环中的不变运算s:A:=B op C外提时注意：,（,2,）,要求循环中其它地方不再有A的定值点。,（3,）,要求循环中A的所有引用点都是而且仅仅是这个定值所能达到的,（1）要求s所在结点是循环的所有出口结点的必经结点,（4）要求A在离开循环之后不再是活跃的,55,2023/10/4,中南大学软件学院 陈志刚,数据流问题的讨论合流问题,向前流（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),56,2023/10/4,中南大学软件学院 陈志刚,数据流问题的讨论路径问题,任意路径数据流分析讨论的数据流假定这么一个性质，即某条路径为真，（如果存在某条路径上被引用这个变量就认为是活跃的；如果存在任何一条路径上被定值，则就认为这个变量是被定值的）。这种数据流问题被称为任意路径问题。任意路径问题的解不能保证所需的性质一定会满足，仅仅是可能满足。全路径数据流分析数据流问题也可以用全路径（all-path）形式来解决，使所需的性质在所有可能的路径都满足。对于全路径问题的解，所需的性质可以保证总是满足。,57,2023/10/4,中南大学软件学院 陈志刚,数据流问题的解不一定唯一,考察图10.20的流图，其中有一个简单的循环。在这个流图中，没有对任何变量定值，a在B4中被引用。应用向后流方法传播可以得到一个最明显的解，即四个基本块的LiveIn集合均为a。但是，不太合理的解也是可能的。,58,2023/10/4,中南大学软件学院 陈志刚,若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)=a,B1,B2,B3,B4,59,2023/10/4,中南大学软件学院 陈志刚,例如，下面解是满足数据流方程的：,注意b没有在任何基本块中被引用！问题所在是基本块B2和B3互为祖先；而且，因为b从未定值（所有Def集为空），一旦b被包括在LiveIn集合中，它就永远消除不了,