编译程序的组织 (23).ppt

9.1 代码优化l代码优化目的：生成效率更高的目标代码。l注意：优化优化最佳化最佳化 l要求：相对合理性相对合理性。考虑空间和时间上的取舍及二者的平衡。l优化的要求：必须是等价变换(保持功能)；为优化的努力必须是值得的（获得感）；有时优化后的代码的效率反而会下降（副作用）。l机器相关性机器相关优化：寄存器优化，多处理器优化，特殊指令优化等。机器无关优化：中间代码优化。l注意：本文重点关注中间代码的优化方法。优化的种类l基于中间代码优化的步骤:控制流分析：分析出程序的循环结构（优化关键）；数据流分析：数据流信息的收集，主要是变量值的获得和使用情况的数据流信息；代码变换:根据上面的分析,对中间代码进行等价变换。l优化范围：局部优化：如基于单个基本块范围内的线性窥孔优化等，包括常量合并优化，公共子表达式删除，计算强度削弱和无用代码删除等；全局优化：主要是基于结构信息的优化，包括针对循环的系列优化方法，如循环不变优化，归纳变量删除，计算强度削减等。线性窥孔优化l分类分类：局部优化方法。l基基本本思思想想：考察编译器所生成代码中相邻指令,将其中的某些组合替换为效率更高的指令组。l特点特点：优化的对象可以是中间代码,也可以是目标代码；每次处理的是一组相邻的指令,仿佛将其暴露在一观察窗口(窥孔)中；对优化对象进行线性扫描。l优化项目优化项目：强度削弱、常数合并和常数传播、无用代码删除等。强度削弱l强强度削弱度削弱：用执行效率较高的等价地替换原操作.l例如例如：乘(或除)以2的n次方的运算可用左(或右)移n位实现(X*8等价于X3);类似地,以2的n次方为模的求模运算可用按位与实现(X%8=X&7).另外,用加法代替乘法也可提高效率.如x*=3可替换为:t=x;x+=t;x+=t;联合使用移位和加法,可以削弱乘法的强度:x*=9可替换为 t=x;t=3;x+=t;即x*9=x*8+x=(x3)+x。l优化与具体的运算对象的值有关，有时会得不偿失，应权衡各方面的因素。l对于非算术运算也可削弱强度，如尽量多使用寄存器，少访问内存(或外存)等。常数合并和常数传播l常数合并：指在编译时就将源程序中常数表达式之值先行算出,不必生成计算该表达式的代码。l例如：a+2*3可翻译成a+6。表达式a+1+3在翻译阶段生成的代码为：T1=a；T1+=1；T1+=3；由于对T1的两次定值未被引用，可将其修改为；T1=a；T1+=4；l常数传播：指在程序运行时某段程序中的一些变量之值保持不变，故在此范围内对该变量的引用可替换对其值的直接引用，传播将一直延续到对其重新定值。l例如：a=3;/*未对a重新定值*/;b=a;可改为:a=3;b=3;无用变量与无用代码的删除例如:t0=a;t0+=5;x=t0;t0+=1;t0=b;l无用变量：指在变量的最后一次引用，到对该变量再置初值期间的变量。l相对性：变量是否无用依赖于所处的环境，是相对概念；l例如：右边例子中的T0，在T0+=1被被赋赋值值后后，直直到到再再次次做做T0=bT0=b操操作作，在在这这期期间间，从从未未被被引引用用的的变变量量，其其赋赋值值操操作作是是无无用用赋赋值值，这种变量被称为无用变量。l无用代码：指控制永远到达不了的代码。如if(0)if(0)S S,花括号内为S，是无用代码。