编译原理教程 第七章 代码优化.pptVIP

第7章 代码优化 优化：对程序进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码。 优化可以在编译的各个阶段进行，主要的有两种： 中间代码的优化； 目标代码的优化。 中间代码的优化技术有多种 局部优化 循环优化 代码优化器的地位和结构图 7.1 优化概述 优化的原则： 等价原则。 有效原则。(能提高代码质量) 合算原则。(仅增加最少编译复杂度) 优化的环节： 源代码设计时(选择适当的算法和语句) 设计语义动作时(产生更高质量的中间代码) 目标代码生成时(如何有效地利用寄存器等) 中间代码优化示例： 源代码段： S=0; for(i=1;i=20;i++) S=S+A[i]*B[i]; (1)S=0 (2)i=1 代码优化的常用基本方法： 1. 删除公共子表达式： 公共子表达式：在一个基本程序块内计算结果相同的子表达式。 删除公共子表达式：避免公共子表达式的重复计算（删除多余运算） 删除公共子表达式 涉及循环的优化方法： 涉及循环的优化方法： 涉及循环的优化方法： 代码优化的常用基本方法： 5. 合并已知量： 已知量的计算在编译时进行。 7. 删除无用赋值： 复写传播后，删除无用赋值。 7.2 局部优化 局部优化：应用于代码的线性部分。 7.2.1 划分基本块的方法 基本块：程序中一组顺序执行的语句序列，其中只有一个入口和一个出口。 局部优化：局限于基本块范围内的优化。 划分四元式程序为基本块的算法： 1、求出四元式程序中各个基本块的入口语句，它们是： (1)程序的第一个语句;或者 (2)能由条件转移语句或无条件转移语句转移到的语句;或者 (3)紧跟在条件转移语句后的语句。 2、确定各出口语句：(1)下一入口语句的前导语句；（2）转移语句(包括)；(3)停语句(包括)。 3、凡未被纳入某一基本块中的语句，都是程序控制流无法到达的语句，将其删除。 划分三地址代码程序为基本块的算法示例： 例：求最大公因子程序 ⑴read X ⑵read Y ⑶R=X mod Y ⑷if R=0 goto (8) ⑸X=Y ⑹Y=R ⑺goto (3) (7’)goto (1) ⑻write Y ⑼halt 基本块内的优化方法： 1、删除公共子表达式、删除无用赋值； 2、其它变换： (1)合并已知量：编译时的已知量在编译时计算其值； (2)临时变量改名; (3)交换语句的位置; (4)代数变换。 流图： 定义：将控制流的信息增加到基本块的集合上来表示一个程序。 性质：有向图； 结点：基本块； 有向边：从基本块B1到B2有一条有向边，当且仅当在某个执行顺序中，B2紧接在B1的后面，即： (1)转移语句从B1的最后一条语句转移到B2的第一条语句；或者 (2)在程序的序列中，B2紧接在B1的后面，并且B1的最后一条语句不是无条件转移语句。 前驱、后继 基本块构成流图示例： ⑴read X ⑵read Y 7.2.2 基本块的DAG表示及其应用： 一个基本块的DAG是一种其结点带有下述标记或附加信息的DAG ： 1.图的叶结点以一标识符或常量作为标记，表示该结点代表该变量或常数的值； 2.图的内部结点以一运算符作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果； 3.图中各个结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。 四元式与DAG结点表示(P145)： 基本块的DAG表示示例： 基本块： (1)T1=4*i (2)T2=a[T1] (3)T3=4*i (4)T4=b[T3] (5)T5= T2* T4 (6)T6=prod+ T5 (7)prod = T6 (8)T7=i+1 (9)i=T7 (10)if i=20 goto(1) 基本块的DAG的构造与应用： 根据基本块的DAG的构造，可以应用它实现如下优化： 1、合并已知量； 2、检查公共子表达式； 3、删除无用赋值。 即，利用构造出的DAG，重新生成原基本块的一个优化的中间代码序列。 基本块的DAG的构造算法： (1)若node(B)无定义，构造叶结点node(B)，依据当前四元式类型，0型转(4);1型转(2)中①；2型构造叶结点node(C)后转(2)中②。 基本块的DAG的构造与应用： 基本块的DAG的构造与应用： 注意：把DAG重新写成中间代码时，可以按照原来构造DAG结点的顺序依次进行，也可以采用其它顺序。只要其中任一内部结点在其后继结点之后被重写，并且转移语句（如果有的话）仍然是基本块的最后一个语句；另外，任何数组的引用不可以互相调换次序，任何语句不得跨越一个过程调用或通过指针的间接赋值。 7.3 循环优化 循