ch10--代码优化.

LIWensheng,SCST,BUPT第10章代码优化知识点：基本块优化循环优化窥孔优化dag的应用WenshengLiBUPT@20082/62代码优化10.1优化概述10.2基本块优化10.3dag在基本块优化中的应用10.4循环优化10.5窥孔优化小结WenshengLiBUPT@20083/62代码优化程序的任务–将前端产生的中间代码转换为等价的目标代码代码优化程序的要求–等价变换–提高目标代码的执行速度–减少目标代码占用的空间代码优化程序的地位–目标代码生成之前的中间代码优化–目标代码生成之后的目标代码优化10.1优化概述WenshengLiBUPT@20084/62代码优化程序的位置前端中间代码优化程序代码生成程序目标代码优化程序控制流分析数据流分析代码变换中间代码中间代码目标代码目标代码源程序WenshengLiBUPT@20085/62优化的主要种类基本块优化–基本块内进行的优化–常数合并与传播、冗余子表达式的删除、复制传播、削弱计算强度、死代码的删除等循环优化–在循环语句所生成的中间代码序列上进行的优化–循环展开、代码外提、削弱计算强度、删除归纳变量等全局优化–在非线性程序段上（含多个基本块）进行的优化窥孔优化–在目标代码上进行的优化–删除冗余的传送指令、删除死代码、控制流优化、强度削弱及代数化简等WenshengLiBUPT@20086/6210.2基本块优化一、常数合并及常数传播二、删除冗余的公共表达式三、复制传播四、削弱计算强度五、改变计算次序WenshengLiBUPT@20087/62一、常数合并及常数传播常数合并：将能在编译时计算出值的表达式用其相应的值替代x=2+3+y可代之以：x=5+y常数传播：用在编译时已知的变量值代替程序正文中对这些变量的引用PI:=3.14;D-to-R:=PI/180.0;3.14/180.00.01744i:=010:i:=0+1...ifi10goto10i:=010:i:=i+1...ifi10goto10...a[i]:=9.0...a[j]:=3.0b:=a[i]?WenshengLiBUPT@20088/62常数合并的实现在符号表中增加两个信息域–标志域：指示当前是否存在与该变量相关的常数。–常数域：如果常数存在，则该域存放的即是与该变量相应的当前常数值。常数合并时，注意事项：–不能将结合律与交换律用于浮点表达式，因为浮点运算的精度有限，这两条定律并非是恒真的。–不应将任何附加的错误引入WenshengLiBUPT@20089/62二、删除冗余的公共表达式在一个基本块中，当第一次对表达式E求值之后，如果E中的变量都没有改变，再次对E求值，则除E的第一次出现之外，其余的E都是冗余的公共表达式。删除冗余的公共表达式，用第一次出现时的求值结果代替重复求值的结果。(1)a:=b+c(2)b:=a-d(3)c:=b+c(4)d:=a-dbWenshengLiBUPT@200810/62举例(4)t1:=4*i(5)t2:=a-4(6)t3:=4*i(7)t4:=a-4(8)t5:=t4[t3](9)t6:=4*i(10)t7:=b-4(11)t8:=t7[t6](12)t9:=t5+t8(13)t2[t1]:=t9(14)t10:=i+1(15)i:=t10(16)gotoB2B4(4)t1:=4*i(5)t2:=a-4(6’)t3:=t1(7’)t4:=t2(8)t5:=t4[t3](9’)t6:=t1(10)t7:=b-4(11)t8:=t7[t6](12)t9:=t5+t8(13)t2[t1]:=t9(14)t10:=i+1(15)i:=t10(16)gotoB2WenshengLiBUPT@200811/62三、复制传播为减少重复计算，可以利用复制传播来删除公共表达式思想：在复制语句f:=g之后，尽可能用g代替f(4)t1:=4*i(5)t2:=a-4(6’)t3:=t1(7’)t4:=t2(8)t5:=t4[t3](9’)t6:=t1(10)t7:=b-4(11)t8:=t7[t6](12)t9:=t5+t8(13)t2[t1]:=t9(14)t10:=i+1(15)i:=t10(16)gotoB2(4)t1:=4*i(5)t2:=a-4(6’)t3:=t1(7’)t4:=t2(8’)t5:=t2[t1](9’)t6:=t1(10)t7:=b-4(11’)t8:=t7[t1](12)t9:=t5+t8(13)t2[t1]:=t9(14)t10:=i+1(15)i:=t10(16)gotoB2WenshengLiBUPT@200812/62删除死代码死代码：如果对一个变量x求值之后却不引用它的值，则称对x求值的代码为死代码。死块：控制流不可到达的块称为死块–如果一个基本块是在某一条件为真时进入执行的，经数据流分析的结果知该条件恒为假，则此块是死块。–如果一个基本块是在某个条件为假时才进入执行，而该条件却恒为真，则这个块也是死块。在确定一个基本块是死块之前，需要检查转移到该块的所有转移语句的条件。死块的删除，可能使其后继块成为无控制转入的块，这样的块也成为死块，同样应该删除。WenshengLiBUPT@200813/62删除死代码举例(4)t1:=4*i(5)t2:=a-4(6’)t3:=t1(7’)t4:=t2(8’)t5:=t2[t1](9’)t6:=t1(10)t7:=b-4(11’)t8:=t7[t1](12)t9:=t5+t8(13)t2[t1]:=t9(14)t10:=i+1(15)i:=t10(16)gotoB2(4)t1:=4*i(5)t2:=a-4(8’)t5:=t2[t1](10)t7:=b-4(11’)t8:=t7[t1](12)t9:=t5+t8(13)t2[t1]:=t9(14)t10:=i+1(15)i:=t10(16)gotoB2(4)t1:=4*i(5)t2:=a-4(8’)t5:=t2[t1](10)t7:=b-4(11’)t8:=t7[t1](12)t9:=t5+t8(13)t2[t1]:=t9(15’)i:=i+1(16)gotoB2WenshengLiBUPT@200814/62四、削弱计算强度对基本块的代数变换：对表达式用代数上等价的形式替换，以便使复杂的运算变换成为简单的运算。x:=y**2可以用代数上等价的乘式（如：x:=y*y）代替x:=x+0和x:=x*1–执行的运算没有任何意义–应将这样的语句应从基本块中删除。WenshengLiBUPT@200815/62五、改变计算次序考虑语句序列：t1:=b+ct2:=x+y如果这两个语句是互不依赖的，即x、y均不为t1，b、c均不为t2，则交换这两个语句的位置不影响基本块的值。对基本块中的临时变量重新命名不会改变基本块的值，如：语句t:=b+c改成语句u:=b+c即，把块中出现的所有t都改成u，不改变基本块的值。WenshengLiBUPT@200816/6210.3dag在基本块优化中的应用利用dag对基本块进行某些等价变换，使得从变换后的程序出发，能够生成更有效的目标代码–所谓等价，指不改变程序的运行结果–所谓有效，指目标代码运行时间短、占用空间少基本块的dag是一种结点上有标记的有向非循环图–叶结点由变量名字或常量标记。–根据作用到名字上的算符，决定需要名字的左值还是右值。大多数叶结点代表右值。–叶结点代表名字的初值，通常为标识符加上脚标0。–内部结点由运算符号标记，代表计算出来的值。–图中各结点可能附加一个或多个标识符，表示这些标识符具有该结点所代表的值。WenshengLiBUPT@200817/62本节内容基本块的dag表示基本块的dag构造算法dag的应用WenshengLiBUPT@200818/62一、基本块的dag表示结点用圆圈表示各结点圆圈旁边的数字是dag构造过程中给予结点的编号各结点圆圈中的符号（运算符、变量名或常数）是结点的标记各结点圆圈右边的符号是结点的附加标识符表–除了转移语句对应的结点可以附加一个语句位置以指示转移目标外，其余各类结点只允许附加标识符，可以为空。WenshengLiBUPT@200819/62各种三地址语句的dag结点形式(0)x:=yyxn1(1)x:=yy,x(2)x:=opyyopx(3)x:=yopzopyxz(4)x:=y[z]=[]yxz(5)x[y]:=z[]=xzy(6)ifxopygoto(s)opx(s)y(7)goto(s)(s)WenshengLiBUPT@200820/62例：基本块B4：dag：+--*+=[]=[]t2,t4(2)t1,t3,t6t5t7t8t9t10,iab4i01[]=12345678910111314(4)t1:=4*i(5)t2:=a-4(6)t3:=4*i(7)t4:=a-4(8)t5:=t4[t3](9)t6:=4*i(10)t7:=b-4(11)t8:=t7[t6](12)t9:=t5+t8(13)t2[t1]:=t9(14)t10:=i+1(15)i:=t10(16)goto(2)WenshengLiBUPT@200821/62二、基本块的dag构造算法输入：一个基本块输出：该基本块的dag，其中包括如下的信息：•每个结点都有一个标记，叶结点的标记是一个标识符（允许是常数），内部结点的标记是一个运算符号。•在每个结点上有一个附加的标识符表（该表可能为空），这里的标识符不允许是常数。方法：–用某种适当的数据结构（如数组、链表等）保存dag中各结点的信息–设有一个保存标识符（包括常数）与结点之间对应关系的数据结构。–设函数node(id)描述标识符与结点之间的对应关系，如果dag中存在一个结点，id是其标记或附加标识符，则它返回该结点的编号n，否则node(id)无定义。WenshengLiBUPT@200822/62考虑如下三种形式的三地址语句：1型x:=y2型x:=opy3型x:=yopzifi=20goto(2)当作3型语句处理，其中x无定义假定开始时，dag中没有任何结点WenshengLiBUPT@200823/62构造dag的过程依次对基本块中的每个三地址语句执行下述步骤1.如果node(y)无定义，则建立一个标记为y的叶结点，并定义node(y)为这个结点。–如果是1型语句，则记node(y)为n，转4。–如果是2型语句，则转2(1)。–如果是3型语句，则•如果node(z)无定义，则建立一个标记为z的叶结点，并定义node(z)为此结点。•转2(2)。WenshengLiBUPT@200824/622．常数合并(1)如果node(y)是标记为常数的叶结点，则转2(3)，否则转3(1)。(2)如果node(y)和node(z)都是标记为常数的叶结点，则转2(4)，否则转3(2)。(3)执行opy进行常数合并，令得到的新常数为p。如果node(y)是处理当前三地址语句时新构造的结点，则删除它。如果node(p)无定义，则建立一个标记为p的叶结点n，定义node(p)为n，转4。(4)执行yopz进行常数合并，令得到的新常数为p。如果node(y)或node(z)是处理当前三地址语句时新构造的结点，则删除它。如果node(p)无定义，则建立一个标记为p的叶结点n，定义node(p)为n，转4。WenshengLiBUPT@200825/623．查找公共子表达式(1)检查dag中是否已经存在一个标记为op结点，且它有唯一的子结点node(y)。若不存在，则建立该结点n；否则就把已有的结点作为它的结点并设该结点为n，转4。(2)检查dag中是否已经存在一个标记为op结点，且它的左右子结点分别是node(y)和node(z)。若不存在，则建立该结点n；否则就把已有的结点作为它的结点并设该结点为n，转4。4．如果node(x)无定义，则把x附加在结点n上