最新第十一章代码优化ppt课件.ppt

《最新第十一章代码优化ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十一章代码优化11.1优化技术简介11.2局部优化11.3循环优化简介11.1优化技术简介什么是优化：所谓优化是对代码进行等价变换，使得变换后的代码的效率更高（节省运行时间、存储空间或两者兼而有之）优化可在编译的不同阶段进行，最主要的优化有中间代码优化（不依赖具体计算机）目标代码优化（依赖于具体计算机）(1)和(4)中都有4*I的运算，(1)到(4)之间无对I的赋值，显然两次计算的值是相等的，(4)的运算是多余的例(1)T1:=4*I(2)T2:=addr(A)－4(3)T3:=T2[T1]T4:=4*I(5)……(4

2、)变换成T4:=T12.合并已知量与复写传播如果运算量都是已知量，则在编译时就算出它的值，称为合并已知量若有A:=B，称为把B值复写到A。如果其后有引用A的地方，且其间A、B的值都未改变，则可把对A的引用改为对B引用，称为复写传播。例：（1）I:=1（2）T1:=4*I（3）T4:=T1（4）T6:=T5[T4]I是已知量把T1的值复写到T4（4）T6:=T5[T1]复写传播（2）T1:=4合并已知量3.删除无用赋值有些变量的赋值从未被引用，称为无用赋值，应删除。无用赋值分三种情况：变量被赋值，但在程序中从未被引用（在局

3、部范围内难判定）变量赋值后未被引用又重新赋值，则前面赋值是无用的变量的赋值只被计算变量自己引用，其他变量都不引用它例（1）I:=1（2）T1:=4（3）T3:=T2[T1]（4）T4:=T1（5）I:=I+1（6）T1:=T1+4（7）ifT1≤80goto(3)(4)中对T4赋值，但T4未被引用；(1)和(5)对I赋值，但只有(5)中计算I时引用I如果程序其他地方不需要引用T4和I，则(4)、(1)和(5)是无用赋值，可删除。（2）T1:=4（3）T3:=T2[T1]（6）T1:=T1+4（7）ifT1≤80goto(

4、3)4.其他优化技术以下优化技术将在循环优化中介绍：代码外提强度削弱变换循环控制条件（删除归纳变量）11.2局部优化局部优化是指基本块内的优化基本块是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。执行时只能从入口语句进入，从其出口语句退出11.2.1基本块的划分把程序（中间代码形成）划分成基本块的算法：1.求基本块的入口语句，它们是：程序的第一个语句；或者条件转移或无条件转移语句的转移目标语句；或者紧跟在条件转移语句后面的语句。2．对每一入口语句，构造其所属的基本块:它是由该入口语句到下一入口语句(不

5、包括下一入口语句);或到一转移语句(包括该转移语句);或到一停止语句(包括该停止语句)之间的语句序列组成的。3．凡未被纳入某一基本块的语句，是不会被执行到的语句，可以把它们删除。例：readXreadYR:=XmodYifR=0goto(8)X:=YY:=Rgoto(3)writeYhalt(1)、(3)、(5)和(8)是入口语句，分别构成基本块B1{(1)、(2)}B2{(3)、(4)}B3{(5)、(6)、(7)}B4{(8)、(9)}readXR:=XmodYX:=YwriteY11.2.2基本块的DAG表示DAG

6、(DirectedAcyclicGraph)是无环路有向图的简称1.基本块的DAG是一种其结点带有标记或附加信息的DAG：叶结点(无后继的结点)以一标识符或常数作标记，表示该结点代表该变量或常数的值内部结点(有后继的结点)以一运算符作标记，表示该结点代表用该算符对其后继结点所代表的值进行运算的结果各结点都可以附加上一个或多个标识符，表示这些变量具有该结点所代表的值基本块的DAG的例子T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T6:=R－rB:=T

7、5*T6－+rT6A,B,T5*T1,T3T0R6.283.14T2,T4n5n7n2n3n4n1B*n6n8ni是结点编号结点下面的符号（运算符、标识符或常量）是各结点的标记结点右边的标识符是结点的附加标识符2.四元式及其相应的DAG结点形式0型：A:=B(:=,B,－,A)Bn1An2n1opBA1型：A:=opB(op,B,－,A)2型：A:=BopC(op,B,C,A)n3n1n2BCopA3构造基本块的DAG的算法算法准备：假定DAG各结点信息将用适当的数据结构来存放，并设有一个标识符（包括常数）与结点的对应表

8、。NODE(A)是描述这种对应关系的函数，它的值或为n（表示结点n上有A作为标记或附加标识符），或无定义。算法：首先DAG为空，对基本块的每一四元式，按其类型分别处理：对0型（A:=B）YNNYNODE(B)有定义构造叶结点B令该结点为nNODE(A)有定义从NODE(A)的附加标识符中删去A在结点n上附加A下一四元