大三-编译原理第11章代码优化

第第11章wuchxcourse@sinacom第11章代码优化学习学习目掌中间代码优化的基本思了11.1概目提高目标程序的效率11.111.1概2．注意事项：⑴等价原则——不应改变程序⑵有效原则——优化后的目标代码效率确实提高⑶合算原则——以较低的代价取得较好的优化效果11.1概3．优化的消除公共子表达式利用(基本块优化)删除无用赋循环不变式循环优化强度削T7:=T6T7:=T6T10:=T8gotoT7:=T6T10:=T8gotogoto11.2基本块优化11.2基本块优化中只有一个和一个出口，就是第一个语句，出口就其进入，从其出口退出。11.2基本块优化① 语程序的第一个语句能由条件转语句/无条件转语句转移到的语句紧跟在条件转移语句后面②对每 语句，构造其所属的基本由 语句到另 语句(不含该语句)到一转移语句(包括到一停语句(包括①①read②read③R:=Xmod④ifR=0goto⑤⑥⑦goto⑧wrtie⑨①read②read③R:=X④ifR=0goto⑤⑥⑦goto⑧wrtie⑨程序的流11.2基本块优3 11.2基11.2基本块优3 T7:= T10:= goto goto删除公共子表达T7:=T6T10:=T8goto复goto删除无用代11.2基本块优基本块的DAG(DirectedAcyclicGraph)表示叶结点用标识符(变量名)或常数作为其惟一的标记，当叶结点是标识符时，代表名字的初值，给它加下标0；结点个结点上的若干个标识符有相同的值。11.2基本块优化411.2基本块优化4．基本块的DAG(DirectedAcyclicGraph)表示本算法只对如下三种四元式构造0型1型opA2型opAB引进函数noeA)，它将返回与标识符A相应的最近建立的结点。o是双目运算符，还可以是或。步骤1初始DAG步骤2依次对基本块中的每一个四元式“opABC”，步骤3如果noeA)没有定义，则建立叶结点，标记为A，让noe(A)等于这个结点。如果对于2型四元式noeB)没有定义，则建立叶结点，这时标记为B，且让noe(B)等于该新建结点，如果noeA)和noeB)都是已知常量，则执行Aop合并常量)，得到新常量P，为P建立一个叶结点，标记为P，如果nodeA)或noe(B)是处理当前四元式时建立的新结点，则删除它。基本基本块的DAG图的构造算步骤4对三种四元式分别处理如下①对于0型，让n是node(A)②对于1型，查看是否存在标记为o的结点，且它有惟一的子结点noe(A)。如果不存在，则建立这样的结点。让n是找到或建立的结点。③对于2型，查看是否存在标记为o的结点，且其左右子结点分别是nodeA)与noeB)。如果不存在，则建立这样的结点。让是找到或建立的结点。步骤5当C为标识符时，从node(C)的标识符表删去C，11.2基本块优5．利用DAG①从基本块构造②从DAG重写11.2基11.2基本块优5．利用DAG图进行基本块的优n-11t9:=t4-n8+n10-n6t3+n2t1*n5t2* 111.2基本块优n7*n6R,H/nSn4-n5+3/ n0S0,S4n1 (104)(107)(10) B(103)(102)'(+,T，10,T(110)(104)(:=，TB删除归纳变11.311.3如循环中对变量I只有惟一的形如I:=I±C的赋值，且C为循环的区域常量，则称I为循环的基本归纳变量。基本归纳变量除用于自身的递归定值外，往往只在循环中用来计算其它归纳变量以及用来控制循环的进行。(103)(+，I，T1，T2)B(102)(*，10，k，T(107)(:=，T4(109)(:=，T(103)(+，I，T，T(100)(102)B3(103)B4(109)(:=，T删除公共子表达(110)B1(100)(:=,1,_,BB(102)(*，10，k，T)B(103)(104)(j，_，_(103)(104)(:=，TB(102)‘(+,T,10,T(110)(j,_,_消减强(106)(+，J，T，T(110)(j，_，_B1(100)B(101)(j>,k,10,(111)优化B(100)(101)'(j>,T(102)第11章小结第11章小结《编译原理》(第1版《编译原理》(第2版等， 技大等， 技大《程序设计语言