编译原理课件07代码优化.ppt

1、，1 .优化的基本概念，第七章代码最优化，(1)代码最优化：是什么，并对程序进行各种等价转换，使转换后的程序生成高效的目标代码。高效的目标代码占用的存储空间少，目标代码执行时间短，(2)代码最优化类型：机器相关最优化，(最优化操作主要在目标代码级别执行)，寄存器最优化，多处理器最优化，特殊命令最优化(优化主要在中间代码级别执行)，以及对象优化中涉及的程序范围，局部优化包括：合并已知量、删除公共子表达式(消除重复运算)、删除不必要的分配、第7章代码最优化和循环优化。是指循环中的代码优化。循环优化需要：代码外部，归纳变量消除，强度减弱，第7章代码最优化，节目整体最优化，数据流分析，成本高。全局最优

2、化，第7章代码最优化，S=0；for(I=1)；I=20I)s=s ai * bi；(3)最优化处理(例如，计算两个矢量内积的源节目段3360、7章代码最优化、编译器进行词汇分析、语法分析、语义分析和中间代码生成)，由以下三个地址语句序列表示的中间代码：7章代码最优化、数组元素地址计算、数组元素地址计算1017 在上图所示的中间代码中，t1=4 * I T2=addr (a) 4 * 1，B1，B2，根据节目流特性，分为B1，B2等子表达式，仅在第一次出现时评估一次，计算两次的表达式将被删除。第7章代码最优化，图B2中的公共子表达式4*I出现在四元(3)和(6)中，并且在(3)到(6)之间没有

3、为子表达式中的变量I重新赋值，因此T1=T4，第二个4*I，第7章代码最优化，第7章代码最优化，在图中的四元(3)T1=4*I中，I是循环控制变量，每个循环一次，I是I值加1，T1的值加4，(3) T1=4*I。第7章代码最优化，第7章代码最优化，转换循环控制条件(消除归纳变量)，如果在B2中保持变量T1牙齿循环控制变量I的线性关系，则可以用T1替换I，因此在3地址语句(12)中转换循环控制条件，第7章代码最优化，转换循环控制条件后的3地址语句(11)变量I通过引用I值计算I值，因此称为I递归分配，I称为循环的归纳变量。、第7章代码最优化、已知量合并、已知量是编译时可以确定值的常量或变量。合并

4、已知量意味着，如果参与运算的两个目标在编译时是已知量，则可以在编译时直接计算计算计算结果，而无需创建目标。第7章代码最优化，图B1中的四元(2) I=1，如果以下两个四元中的I值没有变化，则四元(3) T1=4*I中参与运算的两个运算量都是已知的，因此(3)；在图中，T4是这样的变量。第7章代码最优化，四元(6)T4=T1，下一个四元(8)T6=T5T4，其间T4的值保持不变，因此将(8)转换为： T6=T5T1。此时T4变成了无用的分配。第7章代码最优化，删除无用的分配，赋值语句X=Y，在节目任何地方都不引用X，是否运行牙齿语句对节目执行结果没有影响。牙齿语句称为无用分配语句，可以删除。第7

5、章代码最优化，(1)s=0(4)T2=addr(a)4(7)t5=addr(b)4(3)t1=4 B1:减少了循环内的执行代码，从10个减少到6个。把乘法工作的次数从3次减少到了1次。减少整个范围(、I、T4等)中使用的变量。第7章代码最优化，2 .使用DAG的本地最优化、第7章代码最优化和本地优化是指限制在节目基本块范围内的优化。(1)基本块，基本块是程序中按顺序执行的门序列，其中只有一个牙齿的入口门和一个出口门。确定四元序列中基本块的入口语句：四元序列中的第一个语句，从条件切换语句或无条件切换语句发送的语句，紧接着条件切换语句后面的语句。第7章代码最优化，(2)如何分割基本块，确定基本块的

6、出口语句：下一入口语句的前导语句，上一语句(包括上一语句本身)，停止语句(包括停止语句本身)，在入口语句和出口语句之间形成基本块。删除不属于基本块的语句，因为控制流无法到达这些语句。第7章代码最优化，例如，除以以下四元顺序的基本块：(1)read c(2)a=0(3)b=1(4)L1 : a=a b(5)if BC goto L2(6)b=B1(7)，(1)read c(2)a=0(3)b=1(4)L1 : a=a b(5)if BC goto L2(6)b=B1(7) (2)使用DAG的局部最优化思想：第7章代码最优化，基本块DAG还原，DAG(无环路方向(2) A=op B，(3) A=B

7、 op C，四元和DAG，) 示例1构成了以下基本块的DAG:(1)t0=3.14(2)T1=2 * t0(3)T2=r(4)A=T1 * T2(5)B=A(6)T3=t0=3.14(2)t1=2 * t0(3)T2=r(4)a=t1 * T2(5)b=a(6)T3=(1) T3=(1)t0=3.14(2)t1=2 * t0(3)T2=r r(4)a=t1 * T2(5)b=a(6) (1)T0=3.14(2)T1=6.28(3)T3=6.28(4)T2=r(5)T4=T2(6)a=6.28 T3=6.28已优化，G的四元(5)B=A在分配下一个B之前未引用，第7章代码已优化，解释图位于下一页。 (1)t0=3.14(2)t1=6.28(3)T3=6.28(4)T2=R(5)T4=T2(6)a=6.28概括地说，使用DAG可以简化基本块内的优化。，第7章代码最优化，下一页，(1)t0=3.14(2)t1=6.28(3)T3=6.28(4)T2=r(5)T4=(1)x=b* c y=b/c