7.1优化技术简介中间代码优化优化的分类：根据优化涉及的程序范围，分为：局部优化：在只有一个入口、一个出口的基本块上进行优化循环优化：对循环中的代码进行优化全局优化：在整个程序范围内进行的优化中间代码优化常用技术1.删除多余运算（删除公共子表达式）如果子表达式E在前面计算过，且之后E中的变量值都未改变，那么E的重复出现称为公共子表达式，可避免重复计算2.合并已知量与复写传播如果运算量都是已知量，则在编译时就算出它的值，称为合并已知量若有A:=B，称为把B值复写到A。如果其后有引用A的地方，且其间A、B的值都未改变，则可把对A的引用改为对B引用，称为复写传播。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.其他优化技术以下优化技术将在循环优化中介绍：代码外提强度削弱变换循环控制条件（删除归纳变量）7.2局部优化7.2.1基本块的划分2．对每一入口语句，构造其所属的基本块:它是由该入口语句到下一入口语句(不包括下一入口语句);或到一转移语句(包括该转移语句);或到一停止语句(包括该停止语句)之间的语句序列组成的。3．凡未被纳入某一基本块的语句，是不会被执行到的语句，可以把它们删除。例：readXreadYR:=XmodYifR=0goto(8)X:=YY:=Rgoto(3)writeYhalt7.2.2基本块的DAG表示基本块的DAG的例子T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T6:=R－rB:=T5*T62.四元式及其相应的DAG结点形式3构造基本块的DAG的算法算法准备：假定DAG各结点信息将用适当的数据结构来存放，并设有一个标识符（包括常数）与结点的对应表。NODE(A)是描述这种对应关系的函数，它的值或为n（表示结点n上有A作为标记或附加标识符），或无定义。算法：首先DAG为空，对基本块的每一四元式，按其类型分别处理：对0型（A:=B）对1型（A:=opB）对于2型（A:=BopC）例：构造以下基本块的DAG(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*T67.2.3DAG的应用－原基本块的四元式序列G(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利用DAG进行优化删除在基本块后不被引用变量的赋值7.3循环优化简介7.3.1程序流图例：构造以下程序的流图(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt7.3.2循环优化(1)P:=0(2)I:=1(1)P:=0(2)I:=1(4)T2:=addr(A)－4(7)T5:=addr(B)－4I和T1始终保持T1:=4*I的线性关系这样把(12)的循环控制条件I≤20变换成T1≤80，程序的运行结果不变这种变换称为变换循环控制条件经过这一变换，循环中I的值不被引用，四元式(11)可被删去，这是变换的目的所在。(1)P:=0(2)I:=1(4)T2:=addr(A)－4(7)T5:=addr(B)－4(3)T1:=4*I本章小结主要讨论在中间代码级别上进行的优化优化的种类：局部优化、循环优化、全局优化基本块内的优化删除公共子表达式、合并已知量、复写传播、删除无用赋值借助DAG进行基本块的优化循环优化代码外提、强度削弱、变换循环控制条件