编译原理与技术讲义 第11章 代码优化

1、编译原理与技术第11章 代码优化 青岛大学信息工程学院主要内容优化的概念 代码优化的基本技术 局部优化机器代码优化窥孔技术 编译原理与技术211.1 代码优化的概念代码优化在整个编译过程的位置编译前端中间代码优化目标代码生成中间代码生成源程序目标程序中间代码中间代码目标代码优化中间代码编译前端编译器可以改进过程调用、循环和地址计算目标代码生成中间代码源程序目标程序程序员可以改进算法，改变循环编译器可以利用寄存器，选择指令和窥孔优转换程序员和编译器可能改上程序的位置 编译原理与技术311.1 代码优化的概念设计和实现编译程序代码优化的原则：（1）等价原则：经过优化后的代码应该保持程序的输入输出，

2、不应改变程序运行的结果。（2）有效原则：优化后的代码应该在占用空间、运行速度这两个方面，或者其中的一个方面得到改善。（3）经济原则：代码优化需要占用计算机和编译程序的资源，代码优化取得的效果应该超出优化工作所付出的代价。否则，代码优化就失去了意义。编译原理与技术411.1 代码优化的概念代码优化依据机器相关性、优化范围和优化语言级别的分类按照与机器相关的程度，可以分为与机器相关的代码优化和与机器无关的代码优化。与机器相关的优化一般有寄存器的优化、多处理器的优化、特殊指令的优化以及无用指令的消除等技术。显然， 这几类优化与具体机器的特性密切相关，例如寄存器的总数，寄存器的具体使用规定，等等。这类

3、优化通常的在目标代码生成之后进行。与机器无关的优化是在目标代码生成以前进行，主要是根据程序的控制信息和数据信息，对程序进行优化，与机器无关。 编译原理与技术511.1 代码优化的概念根据优化的范围，可以划分为局部优化和全局优化两类。考察一个基本块的三地址中间代码序列就可以完成的优化，称为局部优化。而全局优化则必须在考察基本块之间的相互联系与作用的基础上才能完成。代码优化总是在内部的中间代码和目标代码上进行的。在通常的编译程序中，代码优化往往是在中间代码这一级执行，例如对源程序的三地址代码或抽象语法树上采取优化措施。相对于在目标代码级别的优化，在中间代码优化的好处是：（1）容易从中间代码中识别处

4、进行优化的情况，对目标语言代码的信息识别要困难，成本较高；（2）中间代码于机器无关，因此，一个代码优化的程序可以适用于多种型号的机器。有时也在目标代码语言级上进行代码优化，如寄存器优化等。在目标代码级别上进行全局优化的代价昂贵，本书仅仅讨论局部范围的目标代码优化技术，即所谓的窥孔优化。编译原理与技术611.2 代码优化的基本技术 分类：与机器无关的、在中间代码语言级的代码优化主要包括：删除公共子表达式复写传播删除无用代码代码外提强度消弱删除归纳变量其中最后三种是专门针对循环语句的优化。编译原理与技术711.2 代码优化的基本技术void quicksort(m, n)int m, n;int

5、i, j, v, x;if ( n = m ) return;/* 程序段开始*/i = m 1; j = n; v = an;while (1) do i = i1; while (ai v); if ( i = j ) break; x = ai; ai = aj; aj = x;x = ai; ai = an; an = x/* 程序段结束*/quicksort(m, j); quicksort(i+1, n);图11.3 快速排序的C代码(1) i := m 1(2) j := n(3) t1 := 4n(4) v := at1(5) i := i 1(6) t2 := 4i(7) t

6、3 := at2(8) if t3 v goto (5)(9) j := j 1(10) t4 := 4j(11) t5 := at4(12) if t5 v goto (9)(13) if i = j goto (23)(14) t6 := 4i(15) x := at6(16) t7 := 4i(17) t8 := 4j(18) t9 := at8(19) at7 := t9(20) t10 := 4j(21) at10 := x(22) goto (5)(23) t11 := ai(24) x := at11(25) t12 := 4i(26) t13 := 4n(27) t14 :=

7、at12(28) at12 := t14(29) t15 := 4n(30) at15 := x 图11.4 快速排序部分程序的三地址代码编译原理与技术811.2 代码优化的基本技术删除公共子表达式i := m 1j := nt1 := 4nv := at1t11 := 4ix := at11t12 := 4it13 := 4nt14 := at12at12 := t14t15 := 4nat15 := xi := i 1t2 := 4it3 := at2if t3 v goto B1if i = j goto B6B1B2B4j := j 1t4 := 4jt5 := at4if t5 v

8、goto B3t6 := 4ix := at6t7 := 4it8 := 4jt9 := at8at7 := t9t10 := 4jat10 := xgoto B2B3B5B6如果表达式E已经计算过，并且在这之后E中变量的值没有改变，那么，E的这个再次出现称为公共子表达式。如果可以利用先前的计算结果，就可以避免表达式的重复计算，这种优化称为删除公共子表达式。编译原理与技术911.2 代码优化的基本技术这是仅限于基本块的局部优化，B5仍然需要计算4*i和4*j。若在整个图11.3的程序来看，它们依然是公共子表达式，4*i在B2中计算并且赋给了t2，4*j在B2中计算并且赋给了t4。继续删除这些公

9、共子表达，在B5中就可以把t6 := 4*i 替换为 t6 := t2t8 := 4*j 替换为 t8 := t4这是因为在B2中计算的4*i传到B5时，没有改变i的值。同样，在B3中计算的4*j传到B5时，没有改变j的值。对于B6也可以作同样的处理。例如，在图11.5的B5中分别把公共子表达式4*i和4*j的值赋给t7和t10，这些重复计算的公共子表达式可以删除，用t6代替t7，用t8代替t10，这样就把B5变换为如下的代码：B5:t6 := 4ix := at6t7 := t6t8 := 4jt9 := at8at7 := t9t10 := t8at10 := xgoto B2 编译原理与

10、技术1011.2 代码优化的基本技术删除公共子表达式后的B5和B6 分别是t6 := t2x := at6t7 := t6t8 := t4t9 := at8at7 := t9t10 := t8at10 := xgoto B2B5B6t11 := t2x := at11t12 := t11t13 := t1t14 := at12at12 := t14t15 := t1at15 := x编译原理与技术1111.2 代码优化的基本技术复写传播 B5:t6 := t2x := t3t7 := t2t8 := t4t9 := t5at2 := t5t10 := t4at4 := t3goto B2观察上

11、面B5中的语句：t6 := t2和x := at6，t6在赋值完成之后就被引用，而期间没有改变t6的值。因此，可以把x := at6变换为x := at2。这种变换叫做复写传播，它是对形式为f := g的赋值语句（复写）的变换。 完成上述的复写传播之后，进一步考察可以发现，在B2中计算了t3 := at2，因此，在B5中可以删除公共子表达式，把x := at2 替换为 x := t3进而，通过复写传播把B5中at4 := x 替换为 at4 := t3同样，B5中的t9 := at4 和at2 := t9可以分别替换为t9 := t5和at2 := t5。这样，B5就变为编译原理与技术1211

12、.2 代码优化的基本技术i := m 1j := nt1 := 4nv := at1i := i 1t2 := 4it3 := at2if t3 v goto B1if i = j goto B6B1B2B4j := j 1t4 := 4jt5 := at4if t5 v goto B3at2 := t5at4 := t3goto B2at2 := vat1 := t3B3B5B6图11.7 复写传播和删除无用代码之后删除无用语句 观察经过复写变换之后的B5，可以发现，变量x、t7、t8、t9、t10的值在整个程序汇总不再使用，因此，这些变量的赋值对程序的运算结果没有任何作用，可以把他们删除掉

13、。我们称之为删除无用代码。删除无用赋值语句之后的B5变为：B5:at2 := t5at4 := t3goto B2对B6可以进行同样的处理，结果如图11.7所示 编译原理与技术1311.2 代码优化的基本技术代码外提 循环是多次重复执行的代码段，在编译程序的优化工作中，循环优化占有十分重要的地位。这是因为，对于循环次数为n的一个循环，每节省循环体内一条目标指令，运行时间就可以少执行n条指令；特别地，对于m重循环的最内循环，每节省一条指令就可以减少执行n1*n2*nm条指令。此外，现代的高级编程语言中都支持数组、集合、树、图等数据结构，它们广泛地应用在程序中。因此，按照经济原则，循环优化的效果最

14、为显著。 编译原理与技术1411.2 代码优化的基本技术如果它产生的结果在循环中保持不变，就可以把它提到循环的外边，以避免每次循环都执行这条代码。例如，对于下面的while语句while ( i = limit -2 ) 如果在循环体内limit的值不变，就可以把它变换为t := limit -2;while ( i = j goto B6之外，不再被引用。因此，可以删除这些归纳变量i和j，把这个语句变换为if t2 = t4 goto B6。经过强度消弱和删除归纳变量，图11.7以及图11.5最后就变换为图11.8。优化的效果:B2和B3的代码数从4条减到3条，其中一条从乘法变为加法；B5从

15、9条变为3条，B6从8条变为2条。尽管B1从4条增加到6条，但是，B1这段代码在程序中仅仅执行一次，所以程序总的运行时间几乎不受B1大小的影响。 i := m 1j := nt1 := 4nv := at1t2 := 4it4 := 4jt2 := t2 4t3 := at2if t3 v goto B1if i = j goto B6B1B2B4t4 := t4-4t5 := at4if t5 v goto B3at2 := t5at4 := t3goto B2at2 := vat1 := t3B3B5B6图11.8 B5和B6删除公共子表达式以后编译原理与技术1711.3 局部优化 基本块

16、的变换 除了上面介绍的删除公共子表达式和删除无用代码这两种优化以外，在基本块内可以进行多种等价变换，改进代码的质量。合并已知量假设在一个基本块内有两条语句：t1 := 2t2 := 3t1如果对t1赋值后，t1的值没有改变过，那么，赋值语句t2 := 3t1右边的两个运算数在编译时刻都是已知量，就可以在编译时计算出这条赋值语句的右边，而不必等到程序运行时再计算。即，可以把这条语句改为t2 := 6。这种变换称为合并已知量。编译原理与技术1811.3 局部优化临时变量更名在一个基本块内有两条语句u := a+b和v := a+b，其中u和v都是基本快内的临时变量，如果用u替换基本块内的所有v的引

17、用，那么，不改变基本块内的值。事实上，总可以通过改变基本块内临时变量的名字而得到一个等价的基本块。交换语句的次序一个基本块内的两条邻近的语句：u := a+bz := x+y当且仅当x和y都不是u，并且a和b都不是z时可以改变这两条语句的位置而不影响基本块。在代码生成的算法中可以发现，有时通过改变语句的执行次序，可以产生更高效的目标代码。编译原理与技术1911.3 局部优化代数变换许多代数变换可以简化表达式的运算或加快计算速度，同时保持表达式的值不变。例如，x := x+0，x := x0 或x := x1执行的运算构没有改变x的值，没有任何意义，可以从基本块中删除。又如，x := y2的指数

18、运算通常要调用一个函数来实现。可以使用等价的代数变换，用简单的乘法运算x := yy代替幂运算。结合性也可以用于生成公共子表达式。例如，如果源程序a := b +ce := c + d + b被翻译成三地址代码：a := b + ct := c + de := t + b如果t的值在基本块之后不再需要了，可以利用加法的结合性和交换性，产生更简洁的代码：a := b +ce := a +d编译原理与技术2011.3 局部优化基本块的DAG实现 如果有向图中不存在环路，则称该有向图为无环有向图，简称DAG。本节使用的DAG的结点，带有下属标记或附加信息：图的叶结点（无后继结点）用一个标识符（变量名

19、）或常量作标记，表示该结点代表该变量或常数的值。如果叶结点代表某变量X的地址，则用addr(X)作为该结点的标记。通常对叶结点上作为标记的标识符使用下标0以表示它是该变量的初始值。图的内部结点（有后继结点）用一个运算符作标记，表示该结点代表应用该运算赋对其后继结点所代表的值进行运算的结果。图上的各个结点还可以附加一个或若干个标识符，表示这些变量具有该结点所代表的值。编译原理与技术2111.3 局部优化基本块的DAG实现n1ABn2Bn1Aopn1ABn2n3C中间代码类型DAG结点（0）A := B（1）A := op B（2）A := B op C= n1An2n3C =n4ABn1n3Cn

20、2(s)n3(s)n1n2ropBCn1(s)（3）A := BC（4）AC := B（5）if B rop C goto (s)（6）goto (s)编译原理与技术2211.3 局部优化算法11.1：基本块的DAG构造算法输入：基本块BBk包含k条语句输出：基本块BBk的DAG图说明：（1）假设DAG结点用一个对象类或结构NODE表示，它包含下列数据成员： label /结点的标记，类型为标识符或常量 left, right/类型为结点NODE，分别指向该结点的左后继结点和右后继结点 labelList/标识符或常量链表，记录结点的附加标识符或常量函数createNode(A)创建并返回一个

21、标记为A的结点，把left，right和labelList初始化为空。（2）假设有一个标识符（常数）与结点的对应表，Node(A)是描述这种对应关系的函数，它对每个标识符给出DAG中一个结点，或者为null表示该标示符还没有定义。NODE n=null, b=null, c=null; / 初始化，b和c用以记录是否为当前语句B和C产生了新结点for BB中的每个变量或常量S Node(S) = null ; / 初始化基本块中的每个变量或常量DAG = null;/ 可以用链表结构编译原理与技术2311.3 局部优化for ( i =1; i k; i+) if (Node(B)= =nul

22、l) b = createNode(B); 把b加入到DAG中;switch BBi的代码类型case 0型：Node(B) = n;case 1型：if （Node(B)的类型是叶子常量）= op B;/ 合并已知量if ( b != null ) 删除结点Node(B)；if ( (n=Node(p) ) = = null) n = createNode(p); Node(p) = n; ;else / 查找公共子表达式Boolean found = false;while (not found & DAG还没有检查的结点n) if (n.left= =Node(B) | n.right=

23、 =Node(B) & n.label= =op) found = true; else 标记该结点为检查过if (not found) n = createNode(op); n.left = Node(B); n.right = Node(C); / 结束case 1的分支语句编译原理与技术2411.3 局部优化case 2型：if (Node(C)= =null) c = createNode(C); 把b加入到DAG中;if (Node(B)的类型是常量 & Node(C)的类型是常量）= B op C;/ 合并已知量if ( b != null ) 删除结点Node(B)；if (

24、c != null ) 删除结点Node(C)；if ( (n=Node(p)= = null) n = createNode(p); Node(p) = n; ;else / 查找公共子表达式Boolean found = false;while (not found & DAG还有没有检查的结点n) if (n.left= =Node(B) & n.right= =Node(C) & n.label= =op)found = true;else 标记该结点为检查过if (not found) n = createNode(op);n.left = Node(B); n.right = No

25、de(C); / 结束case 2的分支语句/ 结束分支语句/ 删除无用赋值语句if (n=Node(A) != null & n不是叶结点）把A从n.labelList中去掉;把A加入n.labelList;/ 把A加入结点n的附加信息中Node(A) = n;b = null; c = null; / 清除b和c以便记录是否为当前语句的B和C产生了新结点编译原理与技术2511.3 局部优化例11.1 构造对下面的基本块B的DAG。(1) T 0 := 3.14(2) T1 := 2T0(3) T2 := R + r(4) A := T1T2(5) B := A(6) T3 := 2T0(7

26、) T 4 := R + r(8) T5 := T3T4(9) T6 := Rr (10) B := T5T6处理每一条语句后构造的DAG如图11.10所示中各个子图所示，每个子图对应每条语句。编译原理与技术2611.3 局部优化图11.10 为例11.1基本块构造的DAG 编译原理与技术2711.3 局部优化基于DAG的局部优化 将中间代码表示成相应的DAG后，就可以对基本块利用DAG进行代码优化。观察DAG的构造过程就可以发现：算法注释的步骤起到了合并已知量的作用。若参与运算的对象都是编译时刻的已知量，则它并不生成计算该结点值的内部结点，而是执行该运算，把计算的结果生成一个叶结点。算法注释

27、的步骤的作用是检查公共子表达式。对所有具有公共子表达式的语句，它只生成一个计算该表达式值的内部结点，而把哪些被赋值的变量标识符附加到该结点。这样就可以删除冗余运算。算法注释的步骤具有删除无用赋值语句的作用。若某变量被赋值以后，在它被引用前又被重新赋值，则把该变量从具有前一个值的结点上删除。编译原理与技术2811.3 局部优化这样，在一个基本块构造成DAG的过程就已经进行了一些局部优化工作。然后，从DAG就可以重新生成优化过的基本块。例如，将图11.10（10）按照构造结点的顺序重新写成四元式的中间代码，得到下列序列B：(1) T 0 := 3.14(2) T1 := 6.28(3) T3 :=

28、 6.28 (4) T2 := R + r (5) T4 := T2(6) A := 6.28T2(7) T 5 := A(8) T6 := Rr(9) B := AT6 和原来的代码相比，可以看出：B中代码（2）和（6）的已知量都被合并了；B中（5）的无用赋值也被删除；B中（3）和（7）的公共子表达式R+r只计算了一次，删除了多余运算。编译原理与技术2911.3 局部优化除了可以DAG进行上述优化以外，还可以从基本块的DAG中得到一些可以用以优化的信息，包括：在基本块外被定值并在基本块内被引用的所有标识符，就是作为叶子结点上标记的那些标识符。在基本块内被定值且该值在基本块后被引用的所有标识符

29、，就是DAG各结点上的那些附加标识符。利用这些信息以及有关变量在基本块之后的引用情况（可以通过全局数据流分析得到，参见10.5节），可以进一步删除基本块中其它情况的无用赋值语句。在上面的例子中，加入临时变量T0、T1、.、T6在基本块之后都没有被引用，则可以把图10.8（10）中的DAG重新写成下列代码：(1) T2 := R + r(2) A := 6.28T2(3) T6 := Rr (4) B := AT6 删除了其中的四个临时变量T1、T3、T4和T5。 编译原理与技术3011.4 机器代码优化窥孔技术 窥孔优化是在目标代码级上进行局部改进的简单而有效的技术，它只考察一小段目标指令（窥

30、孔），只要可能，就把它用更快、更短的指令替换，提高目标指令的质量。这里，窥孔是在目标程序中一个可以移动的窗口。而且，窥孔中的代码不一定是邻接的。窥孔优化的一个特点是，优化后所产生的结果可能会给后面的优化提供进一步的机会。因此，为了得到最大的优化效果，应该对目标代码进行若干遍的优化处理。 编译原理与技术3111.4 机器代码优化窥孔技术冗余存取的删除假设在源程序中有下列两条赋值语句：a = ac; c = ad;编译程序为它们生成的目标代码可能是下列指令序列：（1）MOV b, R0（2）ADD c, R0（3）MOV R0, a（4）MOV a, R0（5）SUB d, R0（6）MOV R0

31、, c前三条指令对应第一条语句，后三条指令对应第二条语句，它们都是正确的。然而，不难指令（4）是多余的，因为指令（3）表明a的值已经在寄存器R0中，可以把指令（4）这条多余的存储删除。但是要注意，如果指令（4）有标号，则有可能抓你指令从其它指令转移控制来执行这条指令，这样的化就不能删除指令（4），以免不能保证a的值在R0中。 编译原理与技术3211.4 机器代码优化窥孔技术不可达代码的删除如果在一条无条件转移指令之后的代码没有标号，就表示没有控制会转移到这条代码，这条代码就是不可能执行的不可达代码或死代码，可以删除。不可达代码的删除可以重复执行，删除一系列指令。产生不可达代码的典型情况是处于调试程序的目的，在一个大程序中插入调试状态变量debug。在程序的调试状态下（debug=1）可以打印调试信息；在程序正常运行的状态下（debug=0），不打印调试信息。例如，在C语言程序中，可以有如下的代码片断：#define debug 0if (debug = = 1) 打印调试信息翻译的中间代码可能是 if debug = 1 goto L1 goto L2L1: 打印调试信息L2: