川师编译原理课件11.ppt
第十一 章 代码优化,教学目的：让学生了解几种常见的代码优化技术，掌握局部优化、循环优化、数据流分析方法。教学重点：代码优化技术、基本块的DAG及应用。课时分配：4学时。教学过程：,11.1 优化技术简介,一、代码优化分类,编译前端,中间代码优化,目标代码,中间代码,目标代码优化,1、按阶段分类 中间代码优化、目标代码优化。2、按程序范围分类 局部（基本块）优化、循环优化、全局优化。二、代码优化原则 等价原则、高效原则。,三、代码优化技术 例：有如下源程序段，求其四元式形式的中间代码，并优化之(设A为实型 数组，每个元素占四个字节)。P：=0；for i:=1 to 20 do P:=P+Ai*Bi;,1、数组的存储空间,设数组中每个元素占t个存储空间，则,数组首地址Addr(A),Ai的地址为：Addr(A)+(i-1)*t=Addr(A)-t+i*t令为T=Addr(A)-t，则Ai的地址为：T+i*t,(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),2、程序段对应的中间代码为如下四元式序列,B2：,B1：,每个元素占四个字节，故 t=4,1）删除公共子表达式(4*i)和代码外提(4)(7),(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(A)-4,B1：,B2：,2）强度削弱(T1的乘法变为加法),(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(A)-4(3)T1:=4*i,B1：,B2：,3）变换循环控制条件(T1=80)、合并已知量(T1:=4)和复写传播(T6:=T5T1),(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(2)i:=1(4)T2:=addr(A)-4(7)T5:=addr(A)-4(3)T1:=4,B1：,B2：,4）删除无用赋值(2)、(6)、(11),(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(4)T2:=addr(A)-4(7)T5:=addr(A)-4(3)T1:=4,B1：,B2：,11.2 局部优化,一、局部优化的概念 1、基本块的定义：一个基本块是指程序中一顺序执行的语句序列，其中只有一个入口和一个出口。入口是程序第一个语句或转移语句的目标语句，或转移语句的后继第一个语句。出口是程序最后一个语句或转移语句。2、对中间代码求基本块后，凡是没被纳入某个基本块的语句，则是控制流程无法到达的、也不会被执行的语句，可删去。3、在基本块范围内的优化称为局部优化。,二、基本块的变换1、提高运算效率的代数变换；2、四种保结构变换）删除公共子表达式；）删除无用代码；）重新命名临时变量：引入新的临时变量不影响基本块的运算结果；4）变换语句次序：当两个语句相互没有引用关系时，变换语句次序也不影响基本块的运算结果。例如：1)t1:=a+b;2)t2:=c+d;3)t1:=t2+b;其中，1)和2)可交换次序。,三、基本块的DAG表示1、DAG图即有向无环图例：,n1,n2,n2,n2,2、附加信息的DAG图1）以四元式为结点构造中间代码 的DAG，其中，ni表示结点编号，结点下符号为结点标记，结点右边符号为附加标识符。2）基本块中各种四元式及对应DAG图的结点形式：(0)A:=B(:=,B,_,A),n1,A,B,(1)A：=op B(op,B,_,A)(2)A：=B op C(:=,B,C,A),n1,n2,A,B,op,n1,n3,A,B,op,n2,C,(3)A：=BC(=,BC,_,A)或(=,B,C,A)(4)if B rop C goto(s)(jrop,B,C,(s),n1,n3,A,B,=,n2,C,n1,n3,(s),B,rop,n2,C,(5)DC:=B(=,B,_,DC)(6)goto(s)(j,_,_,(s),n1,n4,(s),D,=,n3,B,n2,C,n1,(s),3）按基本块后继结点数，可将四元式分为四类：0型，1型，2型，3型4）对由0、1、2型四元式构成的基本块，其DAG构造算法描述如教材P242所示。,4）DAG的应用例子：构造右边所示基本块B1的的DAG。,B1:(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,n1,3.14,T0,n2,6.28,T1,n3,R,n4,r,n5,T2,+,n6,A,*,B,T3,T4,T5,n7,T6,-,n8,B,*,根据DAG结点原来的构造顺序重写四元式如下：,B1：(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(6)A:=6.28*T2(9)B:=A*T6,n1,3.14,T0,n2,6.28,T1,n3,R,n4,r,n5,T2,+,n6,A,*,B,T3,T4,T5,n7,T6,-,n8,B,*,可见：根据DAG结点重写的四元式已是进行了合并已知量、删除多余运算和无用赋值等优化后的结果。结论：利用DAG可进行代码优化。这种优化提供了：）基本块的保结构变换：代数和语序变换；）其他优化信息，如：在基本块外被定值而在块内被引用的所有标识符，就是叶结点上的标识符；在基本块内被定值而在块后被引用的所有标识符，就是各结点上的那些附加标识符。,上例中：若假设T0,T1,T6在基本块B1后不会再被引用，则通过重新命名临时变量的基本块保结构变换，可将B1的四元式代码进一步优化为:,B1：(1)S1:=R+r(2)A:=6.28*S1(3)S2:=R-r(4)B:=A*S2,四、构造算法的讨论,、对于数组元素赋值、间接赋值、多变量共享一单元的情况，应修改DAG构造算法，否则会引起DAG与代码不等价的问题；例：X:=AI;AJ=Y;Z:=AI是否可变换为：X:=AI;Z:=AI;AJ=Z?问题：当I=J 时，对AJ的赋值即对AI的赋值。、解决方法：在适当的时候“注销”引发问题的标识符，其所代表的变量不再取该点的值。若在此后该变量的值还要引用，则需要重新构造一个以它为标记的叶结点。,、根据作过注销处理的DAG重写四元式时，DAG结点应遵循如下顺序：）对数组任何元素赋值和引用都有必须跟在原来位于其前面的对的任何元素赋值和引用之后。）对间接赋值、多变量共享一单元、过程调用的情况，也用类似数组赋值处理。,11.3 控制流分析与循环优化,一、基本问题：、循环的概念：即程序中可能反复执行的代码。、如何找出程序的循环？利用控制流（程）图来查找循环。、找出循环后如何优化？代码外提、删除归纳变量、强度削弱。,二、控制流图,、控制流图即具有只唯一首结点的有向图。、控制流图可表示为三元式(N,E,n0)。、以N表示程序的基本块，E表示基本块间的流程关系。这样的图称为程序流图。,三、循环的定义,在程序流中，一个循环必须具有以下性质：、强连通：序列中任意两点都可达，若只有一个结点，则有一条返回本身的回边；、有且只有一个入口结点：从序列外某结点，有一条有向边指向它，或它为图中首结点。,例：图中的循环有：64,5,6,72,3,4,5,6,7强连通但不是循环的例子：2,4,2,3,4,4,6,7,4,5,7,1,2,3,4,5,7,6,四、循环的查找,、为找出循环，需分析流图中的控制关系；、从流图的首结点(入口)开始，到n如果必须经m，则称m是n的必经结点。记作：m DOM n；、n的所有必经点的集合，称必经结点集，记作D(n)；、求必经点集的算法：见教材P249的迭代算法。newD=n、例子：,1,2,3,4,5,7,6,、循环的查找算法,1）通过必经点集求回边，利用回边即可求出循环；2）回边：设ab是一条有向边，如b DOM。a，则称ab是流图中的一条回边。3）例子：,图中回边有：66,74,42；对于回边nd，存在循环以d为入口点，以d,n 存在可达n但不可达d的结点的点集：6，4，5，6，7，2，3，4，5，6，7,1,2,3,4,5,7,6,7、求循环算法基本思想1）求回边nd组成的循环，有d为循环入口点，n是它的一个出口.将n的前驱结点以及前驱的前驱.加入循环，直至所求出的前驱是d2）算法:insert(m)if（m不属于loop）m加入循环；m下推进栈stack,main()stack:=空；loop=d;insert(n);while(stack不空)栈顶元素m出栈;对m的所有前驱 p属于P(m)做 insert(p);,8、流图的深度为主扩展树(DFST),1,2,3,4,5,7,6,1,2,4,6,7,5,3,五、可归约流图,1、一个流图被称为可归约的，当且仅当流图中除去回边后，其余的边构成一个无环路流图。2、如果程序流图是可归约的，则程序中任何能反复执行的代码都会被纳入一个循环中。3、对可归约流图进行优化比较容易。,六、循环优化,1、代码外提的问题 对于不变运算，是否都能外提？1）定值点：变量被赋值或被输入值的地点。2）引用点：变量被引用的地点。3）例子：下例中将 B3的 i:=2外提会改变原来程序的运行结果：外提后j值总为2，实际上当xy（如取x=20,y=15）时，j值应为1。,i:=1,B1,if xy then goto B3,i=2;x:=x+1,B2,B3,y:=y-1;if y=20 then goto B5,B4,j:=i,B5,2、代码外提规则,将循环不变运算s:A:=B op C 外提时，必须满足下列条件(a)(b)之一：(a)：1)S所在的结点是L的所有出口点的必经点；2)A在L中其它地方未定值；3)L中所有A的引用点，只有s中A的定值才能到达。(b)：A在离开L之后不再是活跃(即不再被引用)的。,3、强度削弱和删除归纳变量,1）强度削弱 指将程序中执行时间较长的运算替换为执行时间较短的运算。如将乘方换乘法，乘法换加法等；2）删除归纳变量 如果循环中有I:=I+C;J=C1*I+C2，则对于基本归纳变量I 的线性增长关系（C为循环不变量）可转换成为与I同族的归纳变量J的线性增长关系，从而可删除I的递归定值四元式。3）删除归纳变量在强度削弱之后进行。,11.4 数据流的分析与全局优化,一、基本概念1、到达-定值：定值点d到达p是指流图中从d有一条路径到达p且该通路上没有A 的其它定值。2、引用-定值链(u-d)链：到达u的所有A的定值点的全体。3、定值-引用链(d-u)链：d能到达的所有引用点的全体。,二、到达-定值方程1、方程：outs=(ins-kills)gens inB:到达基本块入口前的变量定值点；killB：在基本块中被“注销”的定值点；genB：在B中定值并到达B出口之后的所有定值点集。2、例子：,d1:i=2;d2:j:=i+1,d3:i:=1,d4:j:=j+1,d5:j:=j-4,d6:a:=i;d7:b:=j,B1,B2,B3,B4,B5,求ud链的迭代过程(in初值为,out初值为gen),
