编译原理第六章 代码优化ok

1、一. 代码优化概念、目的与原则二. 代码优化器的地位和结构三. 代码优化分类四. 代码优化涉及的各个环节五. 四元式的改写六. 引例：优化主要方法简介优化的目的目的是为了产生更高效的代码更高效的代码。对程序进行各种等价变换等价变换，使得从变换后的程序出发，能生成更有效的目标代码更有效的目标代码，我们通常称这种变换为优化优化。优化的原则：优化的原则：(1)(1)等价原则等价原则(3)(3)合算原则合算原则(2)(2)有效原则有效原则经过优化后不应改变不应改变程序运行的结果。使优化后所产生的目标代码运行时间较短运行时间较短，占用的存储空间较小存储空间较小。应尽可能以较低的代价较低的代价取得较好的优

2、化效果。编译前端代码生成代码优化器代码优化器控制流分析控制流分析代码变换代码变换数据流分析数据流分析另一类重要的优化是在生成目标代码目标代码时进行的这类优化很大程序上依赖于很大程序上依赖于具体的计算机。优化可在编译的各个阶段进行，不是优化可在编译的各个阶段进行，不是“最佳化最佳化”最主要一类优化是在目标代码生成以前，对语法分析后的中间代码中间代码进行的。这类优化不依赖于不依赖于具体的计算机。1.1. 按所处阶段分类按所处阶段分类高级语言的源程序代码优化，由编程人员根据程序设计技术来进行； 单个基本块内局部优化2.2. 按所涉及范围按所涉及范围循环优化 涉及所有代码全局优化可能涉及多个基本块选择

3、适当的算法算法 源代码源代码安排适当的实现语句实现语句源代码的优化很重要源代码的优化很重要设计语义设计语义动作时动作时考虑产生更加高效的更加高效的中间代码中间代码为后面的优化阶段做一些可能的预备工作可能的预备工作中间代码中间代码安排专门专门的优化阶段，进行各种等价变换本章讨论的重点目标代码目标代码有效地利用寄存器选择指令( := , B, , A) 改写成 A:=B(op , B, , A) 改写成 A:=op B(op , B, C, A) 改写成 A:=B op C(=, B, C, A) 改写成 A:=BC (=,B, ,DC) 改写成 DC:=B (jrop, B, C, L) 改写成

4、 if B rop C goto L(j , , , L) 改写成 goto L 一.基本块 二.基本块内的优化方法 三.流图 四.基本块的DAG表示及其应用 五.应用DAG时的相关问题2. 2. 各个操作按代码的排列顺各个操作按代码的排列顺序执行；序执行；3. 3. 若任一语句被执行，则块若任一语句被执行，则块内所有语句都被执行；否则，内所有语句都被执行；否则，块内语句都不执行。块内语句都不执行。1.1.入口入口就是其中的第一个语句； 出口出口就是其中的最后一个语句，都是唯唯一的一的局限于基本块范围内的优化称为基本块内的优化基本块内的优化，或称为局部局部优化优化。所谓基本块基本块，是指程序中

5、一顺序执行一顺序执行的语句序列，其中只有一个一个入入口和一个出口口和一个出口。1.1.基本块基本块在一个基本块中的一个名字，在程序中的某个给定点是活跃的活跃的，是指如果在程序中（包括在本基本块或在其他基本块中）它的值在该点以后被引用如果一条三地址语句为 x：=y + z ，则称对x定值定值 并 引用引用y和z此时T2被定值引用了 a 和 b2.2.定值与引用定值与引用此点T2是活跃的因为后面两处引用了T2T T2 2T T2 2T T2 21. 确定四元式程序中各个基本块的入口语句6.2.1.6.2.1. 划分四元式程序为基本块的算法划分四元式程序为基本块的算法(1)程序的第一个语句(2)能由

6、条件转移语句或无条件转移语句转移到的语句(3)紧跟在条件转移语句后面的语句2. 对以上求出的每一入口语句，构造其所属的基本块它是由该入口语句（开始）到另一入口语句(不包括该入口语句)，或到一停语句(包括该停语句)一转移语句(包括该转移语句)，或到之间的语句序列组成的3. 删除无用代码凡未被纳入某一基本块中的语句，都是程序中控制流程无法到达的语句，从而也是不会被执行到的语句，我们可把它们从程序中删除入口语句4.4.划分基本块示例划分基本块示例(1)(1)read Xread X(2)(2)read Yread Y(3)(3)R := X mod YR := X mod Y(4)(4)if R=0

7、 goto(8)if R=0 goto(8)(5)(5)X := YX := Y(6)(6)Y := RY := R(7)(7)goto (3)goto (3)(8)(8)write Ywrite Y(9)(9)halthalt程序的第一条语句条件转移语句转到的语句在条件转移语句后的语句无条件转移语句转到的语句基 本 块如：对于如：对于 T T1 1 := 2 := 2 . . T T2 2 := 4 := 4 * * T T1 1此时可把此时可把 T T2 2 := 4 := 4 * * T T1 1 变换为变换为 T T2 2 := 8 := 8若两个运算对象都是编译时的已知量编译时的已知

8、量。可以在在编译时计算出它的值编译时计算出它的值，而不必等到程序运行时再计算。我们称这种变换为合并已知量合并已知量。1.1.合并常数和已知量合并常数和已知量 如：假定在一个基本块里有语句：如：假定在一个基本块里有语句： （1 1）T1 := A T1 := A * * B B （6 6）T4 := A T4 := A * * B B四元式（四元式（1 1）和（）和（6 6）中，它们的运算相同）中，它们的运算相同而且值不变，因此（而且值不变，因此（6 6）的运算是多余的，）的运算是多余的，可将它等价变换为：（可将它等价变换为：（66）T4 := T1T4 := T1消除多余运算是指对程序中重复而

9、且结果消除多余运算是指对程序中重复而且结果不变的运算，不变的运算， 2.2.消除多余运算；消除多余运算； 如：如：（5 5）C := 2C := 2 （6 6）T4 := A T4 := A * * B B （7 7）T5 := 18 + CT5 := 18 + C （8 8）T6 := 4 T6 := 4 * * T5 T5 （9 9）Y := T6Y := T6消除无用赋值是指对程序中的无用赋值消除无用赋值是指对程序中的无用赋值予以消除予以消除 。3.3.消除无用赋值消除无用赋值 如：语句 x := y y * * * 2 2中的乘方运算，通常需要调用一个函数来实现。可以用代数上等价的形式

10、，用简单的运算替换。 x := y y * * y y对基本块中求值的表达式，用代数上等价的形式替换，以期使复杂运算变成简单运算。我们称这种变换为代数变换代数变换。4.4. 代数变换代数变换如果一个表达式 E 在前面已计算过，并且在这之后在这之后E E 中中变量的值没有改变变量的值没有改变，则称 E 为公共子表达式公共子表达式。删除公共子表示式删除公共子表示式( (删除多余运算删除多余运算) )对于公共子表达式，我们可以避免对它的重复计算避免对它的重复计算，称为删除公共子表达式删除公共子表达式(有时称删除多余运算删除多余运算)。公共子表达式可以在基本块内基本块内，也可以在全局范围内全局范围内消

11、除。T6：=T2(复写语句复写语句)把T2赋给T6，x：=aT6中引用引用了T6的值，而这中间没有改变这中间没有改变T T6 6的值的值。因此，可以把x：=aT6变换为x：=aT2 这种变换称为复写传播复写传播。5.5.复写传播复写传播( (重复传送重复传送) )“复写”强调了重复性重复性，传播是由复写引起的复写传播的目的目的是使对某些变量的赋值变为无用赋值变为无用换言之，将来可以删除删除这些无用赋值语句6.6.复写传播示例复写传播示例T T6 6 := T := T2 2x := aT6x := aT2T T6 6 := T := T2 2T7 := T6T7 := T2T T6 6 :=

12、T := T2 2aT7 := T9aT2 := T9T T7 7 := T := T6 6T T8 8 := T := T4 4T9 := aT8T9 := aT4T T8 8 := T := T4 4T10 := T8T10 := T4T T8 8 := T := T4 4aT10 := xaT4 := xT T1010 := T := T8 8在在B2B2中有中有T T3 3 := aT := aT2 2 x := aT2x := T3在在B2B2中有中有T T3 3 := aT := aT2 2 aT4 := xaT4:= T3x := aTx := aT2 2 在在B3B3中有中有T

13、 T5 5 := aT := aT4 4 T9 := aT4T9 := T5在在B3B3中有中有T T5 5 := aT := aT4 4 aT2 := T9aT2 := T5T T9 9 := aT := aT4 4 由于某些变量的值在整个程序中不再被使用值在整个程序中不再被使用，因此，这些变量的赋值对程序运算结果没有任何作赋值对程序运算结果没有任何作用用。我们可以删除对这些变量赋值的代码。我们称之为删除无用赋值删除无用赋值或删除无用代码删除无用代码。7.7. 删除无用代码删除无用代码( (删除无用赋值删除无用赋值) )8.8. 删除无用代码示例删除无用代码示例aTaT2 2 := T :=

14、 T5 5aTaT4 4 := T := T3 3gotogoto B2 B2无用代码无用代码DAG (Directed Acyclic Graph)DAG (Directed Acyclic Graph)无环路有向图无环路有向图一个基本块的DAG是一种其结点带有下述标记或附加信息的DAG，描述出基本块中每个运算结果如何用于块中后续运算。 1.1. 概念概念1. 叶结点叶结点值值3. 结点标识符结点标识符2.其他结点其他结点运算或运算或变量变量图的叶结点以一标识标识符符( (变量名变量名) )或常数常数作为标记，表示该结点代表该变量或常数的值值。如果叶结点用来代表某变量变量A A的地址的地址，

15、则用addr(A)addr(A)作为该结点的标记内部结点内部结点以一运算符运算符作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果运算的结果图中各个结点上可能附加一个或多个一个或多个标识符，表示这些变量这些变量具有该结点所代表的值 四元式的类型与DAG结点 数组元素的赋值数组元素的赋值AB := CAB := C为为3 3型四元式，将在型四元式，将在6.2.46.2.4节节讨论；转移讨论；转移gotogoto (s) (s) 是一个孤立结点是一个孤立结点 。2.2. 构造基本块的构造基本块的DAGDAG的思想的思想对于基本块中的每个四元式对于基本块中的每个四元式A :=

16、B op CA := B op C 1.1.如果它们都是叶结点，且其标记均为常数，则如果它们都是叶结点，且其标记均为常数，则直接执行运算直接执行运算B op CB op C，然后建立以其运算结果，然后建立以其运算结果P P为标记的叶结点并把为标记的叶结点并把A A附加到此结点上去附加到此结点上去 （如果以B或C为标记的结点是为处理本四元式才建立的，则将它们删除） 。首先找出（或建立）代表B和C“当前值”的结点 2. 2. 如果如果B B或（和）或（和）C C是内部结点，则建立以是内部结点，则建立以opop为为标记的新结点，此结点分别以标记的新结点，此结点分别以B B、C C所标记的所标记的结点

17、为其左、右直接后继结点，并将结点为其左、右直接后继结点，并将A A附加到附加到新建的结点上。新建的结点上。 注意，若在此之前，注意，若在此之前，DAGDAG中已有结点其上有附中已有结点其上有附加标记加标记A A，且此结点无前驱，则在建立新结点，且此结点无前驱，则在建立新结点的同时，应把老结点上附加的的同时，应把老结点上附加的A A删除，以表示删除，以表示A A的当前值由新建立的结点代表；的当前值由新建立的结点代表； v3.若DAG中原来已有代表B op C的结点，则不必建立新的结点，只须把变量A附加到表示B op C之值的结点上去即可。2.2. 构造基本块的构造基本块的DAGDAG的算法（算法

18、的算法（算法6.26.2）1. 叶结点生成叶结点生成 代码类型判断代码类型判断3.查找、处理公共子表达式查找、处理公共子表达式2.常数参数与非常数参数的判断常数参数与非常数参数的判断4.赋值号处理赋值号处理 构造基本块的构造基本块的DAGDAG的算法流程的算法流程初始化生成B01生成CB是常数2B不是常数寻找公共子表达式B、C都是常数B或者C不是常数合并已知量生成新常数P处理赋值号处理A合并已知量生成新常数P寻找公共子表达式n13.14T0T T0 0 := 3.14 := 3.14T T1 1 := 2 := 2 * * T T0 0T T2 2 := R + r := R + rA :=

19、TA := T1 1 * * T T2 2B := AB := AT T3 3 := 2 := 2 * * T T0 0T T4 4 := R + r := R + rT T5 5 := T := T3 3 * * T T4 4T T6 6 := R r := R rB := TB := T5 5 * * T T6 6文法文法G GNODE(3.14)NODE(3.14)无定义，构造一个标记为无定义，构造一个标记为3.143.14的结点的结点当前代码为当前代码为0 0型，记型，记NODE(3.14)NODE(3.14)的值为的值为n1,n1,转转4 4T T0 0 := 3.14 := 3.1

20、4NODE(TNODE(T0 0) )无定义，将无定义，将T T0 0附加在结点附加在结点n1n1上上令令NODE(TNODE(T0 0) = n1) = n1，转处理下一条代码，转处理下一条代码T T1 1 := 2 := 2 * * T T0 0NODE(2)NODE(2)无定义，构造一个标记为无定义，构造一个标记为2 2的结点的结点当前代码为当前代码为2 2型，型，NODE(TNODE(T0 0) )已定义，转已定义，转2 2（2 2）NODE(2) NODE(2) 和和NODE(TNODE(T0 0) )均均已定义，转已定义，转2 2（4 4）执行执行 2 2 * * T T0 0 ，

21、新得到常数，新得到常数6.28 ,NODE(2) 6.28 ,NODE(2) 是处理当前代码时是处理当前代码时新构造出来的，删除之，新构造出来的，删除之，NODE(6.28)NODE(6.28)无定义，无定义，构造一个标记构造一个标记为为6.286.28的结点的结点n2n2，置，置NODE(6.28) = n2NODE(6.28) = n2，转，转4 4NODE(TNODE(T1 1) )无定义，将无定义，将T T1 1附加在结点附加在结点n2n2上上令令NODE(TNODE(T1 1) = n2) = n2，转处理下一条代码，转处理下一条代码n22T1n26.28T T2 2 := R +

22、r := R + rNODE(R)NODE(R)无定义，构造一个标记为无定义，构造一个标记为R R的结点的结点n3n3，令令NODE(R) = NODE(R) = n3n3当前代码为当前代码为2 2型，型，NODE(r) NODE(r) 无定义，无定义，构造一个标记为构造一个标记为r r的结点的结点n4n4，令令NODE(r) = n4NODE(r) = n4，转，转2 2（2 2）n3Rn4rNODE(R) NODE(R) 不是标记为常数的结点，转不是标记为常数的结点，转3 3（2 2）DAGDAG中无结点其左后继为中无结点其左后继为NODE(R) NODE(R) ，故构造一个结点，故构造一

23、个结点n5n5，其左后继为其左后继为NODE(R)NODE(R)，右后继为，右后继为 NODE(r)NODE(r)，转，转4 4n5+NODE(TNODE(T2 2) )无定义，将无定义，将T T2 2附加在结点附加在结点n5n5上，上，令令NODE(T2) = n5NODE(T2) = n5，转处理下一条代码，转处理下一条代码T2A := TA := T1 1 * * T T2 2NODE(TNODE(T1 1) )已定义，当前代码为已定义，当前代码为2 2型，型， NODE(TNODE(T2 2) )已定义，转已定义，转2 2（2 2）NODE(TNODE(T1 1) )不是标记为常数的结

24、点，不是标记为常数的结点，转转3 3（2 2）DAGDAG中无结点其左后继为中无结点其左后继为NODE(TNODE(T1 1) )，故构造结点，故构造结点n6n6，其左后继为其左后继为NODE(TNODE(T1 1) )，右后继为右后继为NODE(TNODE(T2 2) )，转，转4 4n6*NODE(A)NODE(A)无定义，将无定义，将A A附加到结点附加到结点n6n6上，上，令令NODE(A) = n6NODE(A) = n6，转处理下一条代码，转处理下一条代码AB := AB := ANODE(A)NODE(A)已定义，当前代码为已定义，当前代码为0 0型，转型，转4 4NODE(B)

25、NODE(B)无定义，将无定义，将B B附加到结点附加到结点n6n6上，上，令令NODE(B) = n6NODE(B) = n6，转处理下一条代码，转处理下一条代码T T3 3 := 2 := 2 * * T T0 0NODE(2)NODE(2)无定义，构造一个标记为无定义，构造一个标记为2 2的结点的结点n7n7，令令NODE(2) = n7NODE(2) = n7n72当前代码为当前代码为2 2型，型，NODE(TNODE(T0 0) )已定义，转已定义，转2 2（2 2）NODE(2)NODE(2)和和NODE(TNODE(T0 0) )都为标记为常数的结点，转都为标记为常数的结点，转2

26、 2（4 4）执行执行2 2 * * T T0 0 ，得到，得到6.286.28，NODE(2)NODE(2)是处理当前代码时构造出来的，删除之；是处理当前代码时构造出来的，删除之；NODE(6.28)NODE(6.28)已有定义已有定义n2n2，转，转4 4NODE(TNODE(T3 3) )无定义，将无定义，将T3T3附加到附加到NODE(6.28)NODE(6.28)上，上，即附加到即附加到n2n2上，转处理下一条代码上，转处理下一条代码T1,T3A,BT T4 4 := R + r := R + rNODE(R)NODE(R)已定义，当前代码为已定义，当前代码为2 2型，型， NODE

27、(rNODE(r) )已定义，转已定义，转2 2（2 2）NODE(R)NODE(R)不是标记为常数的叶结点，转不是标记为常数的叶结点，转3 3（2 2）DAGDAG中结点中结点n5n5其左后继为其左后继为NODE(R)NODE(R)，右后继为，右后继为NODE(rNODE(r),),且其标记为且其标记为 + + ，故将，故将n5n5作为当前结点，转作为当前结点，转4 4NODE(TNODE(T4 4) )无定义，将无定义，将T T4 4附加到结点附加到结点n5n5上，上，令令NODE(TNODE(T4 4) = n5 ) = n5 ，转处理下一条代码，转处理下一条代码T2,T4T T5 5

28、:= T := T3 3 * * T T4 4NODE(TNODE(T3 3) )已定义，当前代码为已定义，当前代码为2 2型，型，NODE(TNODE(T4 4) ) 已定义已定义 ，转，转2 2（2 2）NODE(TNODE(T4 4) ) 不是标记为常数的叶结点不是标记为常数的叶结点 ，转，转3 3（2 2）DAGDAG中结点中结点n6n6其左后继为其左后继为NODE(TNODE(T3 3) )，右后继为，右后继为NODE(TNODE(T4 4) )，且标记为且标记为 * * ，故将，故将n6n6作为当前结点，转作为当前结点，转4 4NODE(TNODE(T5 5) )无定义，故将无定义

29、，故将T T5 5附加到结点附加到结点n6n6上，上，转处理下一条代码转处理下一条代码A,B,T5T T6 6 := R r := R rNODE(R)NODE(R)已定义，当前代码为已定义，当前代码为2 2型，型，NODE(rNODE(r) )已定义，转已定义，转2 2（2 2）NODE(R)NODE(R)不是标记为常数的叶结点，转不是标记为常数的叶结点，转3 3（2 2）DAGDAG中无结点其左后继为中无结点其左后继为NODE(R)NODE(R)，右后继为，右后继为NODE(rNODE(r) )，且标记为且标记为 - - ；故构造结点；故构造结点n7n7，使，使其左后继为其左后继为NODE

30、(R)NODE(R)，右后继为右后继为NODE(rNODE(r) )，且标记为，且标记为 - - ，转，转4 4n7-NODE(TNODE(T6 6) )无定义，将无定义，将T T6 6附加到结点附加到结点n7n7上，上，转处理下一条代码转处理下一条代码T6B := TB := T5 5 * * T T6 6NODE(TNODE(T5 5) )已定义，当前代码为已定义，当前代码为2 2型，型，NODE(TNODE(T6 6) )已定义，已定义，转转2 2（2 2）NODE(TNODE(T5 5) )不是标记为常数的叶结点，不是标记为常数的叶结点，转转3 3（2 2）DAGDAG中无结点其左后继

31、为中无结点其左后继为NODE(TNODE(T5 5) )，故构造结点故构造结点n8n8，使其左后继为，使其左后继为NODE(TNODE(T5 5) )，右后继为右后继为NODE(TNODE(T6 6) )，且标记为，且标记为 * * ，转，转4 4n8*NODE(B)NODE(B)已定义，故将已定义，故将B B从从NODE(B)NODE(B)结点（当前为结点（当前为n6n6）中的附加标识符集中删除中的附加标识符集中删除A,T5B将将B B附加到附加到n8n8上，令上，令NODE(B) = n8NODE(B) = n8，转处理下一条代码，转处理下一条代码所有代码处理完毕，构造过程结所有代码处理完

32、毕，构造过程结束束文法文法G G的最终的最终DAGDAG如上图所示如上图所示4.4. 构构造造DAGDAG示例示例例例6.2 对如下的基本块构造基本块DAG ：（1） T1 := A*B（2） T2 := 3/2（3） T3 := T1-T2（4） X := T3（5） C := 5（6） T4 := A*B（7） C := 2（8） T5 := 18+C（9） T6 := T4*T5（10）Y := T 基本块的优化处理 v第一，合并常数和已知量的运算，并将产生第一，合并常数和已知量的运算，并将产生的运算结果标记为叶结点，不再产生运算的的运算结果标记为叶结点，不再产生运算的内部结点（见图内部

33、结点（见图6-2(b), (g)） T2 := 3/2v第二，合并公共子表达式第二，合并公共子表达式v 基本块内多次出现同一运算的四元式，仅基本块内多次出现同一运算的四元式，仅构造第一个四元式运算的内部结点；以后的构造第一个四元式运算的内部结点；以后的各次出现，只把要赋予结果的各变量标识符各次出现，只把要赋予结果的各变量标识符附加到相应内部结点（见图附加到相应内部结点（见图6-2(e)）（1） T1 := A*B（3） T3 := T1-T2（4） X := T3（6） T4 := A*Bv第三，消除基本块内无用赋值。第三，消除基本块内无用赋值。v在基本块内被多次赋值的变量，若在被引用之在基本

34、块内被多次赋值的变量，若在被引用之前被再次赋值，算法前被再次赋值，算法6.2的第（的第（4）步，除了把）步，除了把此变量名附加到新产生的结点之外，还把它从此变量名附加到新产生的结点之外，还把它从老结点的附加标识符集中逐出（见图老结点的附加标识符集中逐出（见图6-2(f)），），使对该变量的前一次赋值无效使对该变量的前一次赋值无效v C=5 v c=2由由DAGDAG重写代码重写代码重写中间代码的顺序应遵循重写中间代码的顺序应遵循(2)(2)转移语句转移语句( (如果有的话如果有的话) )仍然是基本仍然是基本块的最后一个语句块的最后一个语句 ( (保证基本块的正确性保证基本块的正确性) )(1)

35、(1)其中任一内部结点在其后继结点之其中任一内部结点在其后继结点之前被重写前被重写( (保证计算的正确性保证计算的正确性) )目的：生成有效目标代码目的：生成有效目标代码n13.14T0B := A B := A * * T T6 6n26.28n3Rn4rn5+n6*T1,T3T2,T4n7-T6n8*A,T5BT T0 0 := 3.14 := 3.14T T1 1 := 6.28 := 6.28T T3 3 := 6.28 := 6.28T T2 2 := R + r := R + rT T4 4 := T := T2 2A := 6.28 A := 6.28 * * T T2 2T T

36、5 5 := A := AT T6 6 := R r := R rT T0 0T T1 1T T3 3T T2 2T T4 4A AT T5 5T T6 6B B基本块基本块n1n1结点标记为常数，结点标记为常数，故产生故产生 T T0 0 := 3.14 := 3.14n2n2结点标记为常数，结点标记为常数，故产生故产生 T T1 1 := 6 := 6.28.286.6. 由由DAGDAG重写重写代码示例代码示例n2n2结点标记为常数，结点标记为常数，故产生故产生 T T3 3 := 6.28 := 6.28T T4 4与与T T2 2同标记在一个结点，同标记在一个结点，故产生故产生 T

37、T4 4 := T := T2 2T T5 5与与A A同标记在一个结点，同标记在一个结点，故产生故产生 T T5 5 := A := An2n2结点标记为常数，结点标记为常数，故产生故产生 A := 6.28 A := 6.28 * * T T2 2重写过程结束重写过程结束，基本块基本块如上所示如上所示B := A B := A * * T T6 6T T0 0 := 3.14 := 3.14T T1 1 := 6.28 := 6.28T T3 3 := 6.28 := 6.28T T2 2 := R + r := R + rT T4 4 := T := T2 2A := 6.28 A :=

38、 6.28 * * T T2 2T T5 5 := A := AT T6 6 := R r := R rT T0 0 := 3.14 := 3.14T T1 1 := 2 := 2 * * T T0 0B := TB := T5 5 * * T T6 6T T2 2 := R + r := R + rA := TA := T1 1 * * T T2 2B := AB := AT T3 3 := 2 := 2 * * T T0 0T T4 4 := R + r := R + rT T5 5 := T := T3 3 * * T T4 4T T6 6 := R r := R r基本块基本块G G基

39、本块基本块GG优化效果比较优化效果比较消除无用赋值合并公共子表达式合并常数和已知量的运算v3 3型四元式型四元式BC:=DBC:=D对应的对应的DAGDAG结点形式结点形式x := aix := aiaj := yaj := yz := ai z := ai 四元式序列为：四元式序列为：（1 1）T1:=addr(A)-1T1:=addr(A)-1（2 2）X:=T1iX:=T1i（3 3）T2:=addr(A)-1T2:=addr(A)-1（4 4）T2j:=YT2j:=Y（5 5）T3:=addr(A)-1T3:=addr(A)-1（6 6）Z:=T3iZ:=T3i例考虑如下的源程序段：例

40、考虑如下的源程序段：v基本块的DAG，算法6.2（1 1）T1:=addr(A)-1T1:=addr(A)-1（2 2）X:=T1iX:=T1i（3 3）T2:=addr(A)-1T2:=addr(A)-1（4 4）T2j:=YT2j:=Y（5 5）T3:=addr(A)-1T3:=addr(A)-1（6 6）Z:=T3iZ:=T3i；优化：优化：（1 1）T1 := addr(A)-1T1 := addr(A)-1（2 2）X := T1iX := T1i（3 3）Z := XZ := X（4 4）T1j := YT1j := Y原因：原因：对一个数对一个数组元素赋值时，组元素赋值时，可能改

41、变表达可能改变表达式式aiai的的值值，所以即使所以即使a a和和i i都没有改变，都没有改变，其值可能已改其值可能已改变了。变了。优化前优化前x := aix := aiaj := yaj := yz := ai z := ai 此时此时Z=yZ=y优化后优化后x := aix := aiz := xz := xaj := y aj := y 此时此时Z=aiZ=ai例：在例：在 i = j i = j 并且并且 y != ai y != ai 时，时，2.2. 数组元素引用问题解决方法数组元素引用问题解决方法 在建立对一个数组在建立对一个数组A A的元素赋值的结点时，的元素赋值的结点时，“

42、封锁封锁”那些以那些以addr(Aaddr(A) )作为它的后代之一、作为它的后代之一、且所标记的运算符为且所标记的运算符为“= ”= ”的结点。的结点。 谓封锁一个结点，是指在该结点上做一个谓封锁一个结点，是指在该结点上做一个标志标志，表示不允许在这些结点上再附加任，表示不允许在这些结点上再附加任何新的标识符，从而何新的标识符，从而取消了它作为公共子表取消了它作为公共子表达式的资格达式的资格。v所构造的DAG 优化后的四元式序列 （1 1）T1 := addr(A)-1T1 := addr(A)-1（2 2）X := T1iX := T1i（3 3）T1j := Y T1j := Y （4

43、4）Z := T1iZ := T1i与原四元式是完全等价与原四元式是完全等价 6.3 全局优化 全局优化需要在整个程序范围内，对程序全局优化需要在整个程序范围内，对程序中的全部变量的中的全部变量的定值和引用定值和引用之间的关系进行分之间的关系进行分析，这一分析过程称为数据流分析。析，这一分析过程称为数据流分析。 确切地查找基本块中的无用赋值，不仅确切地查找基本块中的无用赋值，不仅需要了解需要了解基本块中基本块中对变量的定值和引用的情况，对变量的定值和引用的情况，还应知道在还应知道在基本块外基本块外变量是否被引用。变量是否被引用。 数据流分析作用：数据流分析作用： 对消除无用赋值提供了可靠的依据

44、，对消除无用赋值提供了可靠的依据， 循环优化和全局优化一种强有力的工具循环优化和全局优化一种强有力的工具 流图以基本块为流图以基本块为结点结点。如果一个结点的入口语句是程序的第一条如果一个结点的入口语句是程序的第一条语句，则称此结点为语句，则称此结点为首结点首结点。通过构造一个有向图，称之为通过构造一个有向图，称之为流图流图，我们，我们可以可以将控制流的信息增加到基本块的集合将控制流的信息增加到基本块的集合上上来表示一个程序。来表示一个程序。1.1. 概念概念程序流图的结点集就是程序的基本块集。程序流图的结点集就是程序的基本块集。v构造构造 程序流图的方法是：程序流图的方法是：v 对于程序中的

45、两个基本块对于程序中的两个基本块Bi和和Bj，如果，如果Bj紧接着紧接着Bi被执行，则从被执行，则从Bi引一条有向边到结引一条有向边到结点点Bj，称，称Bi为为Bj的的直接前驱直接前驱，Bj为为Bi的的直接后直接后继继。 v规则规则1：按基本块在程序中排列的自然次序，：按基本块在程序中排列的自然次序，Bj紧跟在紧跟在Bi之后，且之后，且Bi的出口语句不是无条的出口语句不是无条件转移或停语句；件转移或停语句；v规则规则2：Bi的出口语句是一个无条件转移或条的出口语句是一个无条件转移或条件转移语句，且其目标是件转移语句，且其目标是Bj的入口语句。的入口语句。2. 2. 构造程序流图示例构造程序流图

46、示例 (1) read X(1) read X(2) read Y(2) read YB1(3) R := X mod Y(3) R := X mod Y (4) if R=0 goto(8) (4) if R=0 goto(8)B2(5) X := Y(5) X := Y(6) Y := R(6) Y := R (7) goto (3) (7) goto (3)B3B3 (8) write Y (8) write Y(9) halt(9) haltB4B4程序流图示例程序流图示例(1)I := 0(1)I := 0(2)I := I + 1(2)I := I + 1(3)If I = N g

47、oto(3)If I = N goto（5 5）(4)goto (4)goto （8 8）(5)T := M + I(5)T := M + I(6)M := T(6)M := T(7)goto (7)goto （2 2）(8)stop(8)stop6.3.2 6.3.2 到达定值数据流方程到达定值数据流方程 为了进行循环优化和全局优化，需要分析为了进行循环优化和全局优化，需要分析程序中所有变量的定值（指对变量赋值）和引程序中所有变量的定值（指对变量赋值）和引用之间的关系，这一工作称为用之间的关系，这一工作称为数据流分析数据流分析 一、作用一、作用 分析程序中所有变量的定值分析程序中所有变量的定

48、值(指对变量的赋指对变量的赋值或输入值值或输入值)和引用之间的关系、基本块出口的和引用之间的关系、基本块出口的活跃变量信息等，以进行循环优化和全局优化。活跃变量信息等，以进行循环优化和全局优化。 二、方法二、方法 1、使用、使用变量到达定值数据流方程变量到达定值数据流方程和和变变量引用定值链量引用定值链 2、使用、使用活跃变量数据流方程活跃变量数据流方程三、基本概念三、基本概念a)点点 程序中某一四元式的位置程序中某一四元式的位置(序号或地址序号或地址)b)定值点定值点 对某变量对某变量赋值或输入值赋值或输入值的四元式的位置的四元式的位置c)引用点引用点 引用某变量的四元式的位置引用某变量的四

49、元式的位置d)变量变量A的到达与定值的到达与定值 若若d点是变量点是变量A的一个定值点，的一个定值点，u点是点是A的的一个引用点，存在一条从一个引用点，存在一条从d到到u的通路，的通路，并在此通路上没有对并在此通路上没有对A的其他定值点，则的其他定值点，则称称d点对点对A的定值能达到的定值能达到u点。点。e)引用定值链引用定值链 假定在程序中某点假定在程序中某点u引用了变量引用了变量A，则把，则把能到达能到达u的的A的所有定值点的全体，称为的所有定值点的全体，称为A在引用点在引用点u的引用定值链的引用定值链(ud链链)到达定值数据流方程求解到达定值数据流方程求解a)基本量基本量 1) INB

50、能到达基本块能到达基本块B入口点的各个变量的定值点集入口点的各个变量的定值点集合。合。 B B入口集合入口集合 2)OUTB 能到达基本块能到达基本块B出口点的各变量全部定值点集出口点的各变量全部定值点集合。合。B B出口集合出口集合 3)GENB 基本块基本块B中定值并能到达中定值并能到达B出口点的所有定值点出口点的所有定值点集合。集合。B B中中“生成生成”的集合的集合 4)KILLB 因因B中定值而注销所有与它相关变量的定值点中定值而注销所有与它相关变量的定值点集合。集合。B B中中“杀死杀死”的集合的集合3 3. . 示例示例(1) a := d(1) a := d(2)if a=b

51、then goto B(2)if a=b then goto B2 2(3)b := 1(3)b := 1(4)c := 1(4)c := 1(5)a := a + b(5)a := a + bB B1 1B B2 2B B3 3B B4 4(1) a := d(1) a := d基本块基本块InGenKillOutB1 1 1B213 1，3B314 1，4B413451345(3)b := 1(3)b := 1(4)c := 1(4)c := 1(5)a := a + b(5)a := a + ba aa ab b 集合集合GENB及及KILLB可以根据程序流图，可以根据程序流图，对基本块

52、对基本块B的的DAG叶结点所标记的叶结点所标记的标识符标识符及及内部结点的内部结点的附加标识符附加标识符进行考察，确定各个进行考察，确定各个定值点。定值点。 对程序流图中的所有基本块对程序流图中的所有基本块B求出相应求出相应INB之后，按如下规则确定到达之后，按如下规则确定到达B中点中点P的任一的任一变量变量A的全部定值点。的全部定值点。 规则规则1：如果：如果B中中P点之前有点之前有A的定值（可的定值（可能为多个），则这些定值点中，离能为多个），则这些定值点中，离P最近最近的那个点就是能到达的那个点就是能到达P的唯一定值点；的唯一定值点； 规则规则2：如果：如果B中中P点之前无点之前无A的定

53、值，则的定值，则能到达能到达P的的A的定值点是包含在集合的定值点是包含在集合INB中的那些中的那些A的定值点。的定值点。 四个集合之间内在的关系四个集合之间内在的关系 首先，程序中某一点首先，程序中某一点d对变量对变量A的定值可到达的定值可到达基本块基本块B的出口之后，当且仅当的出口之后，当且仅当 （1）此定值能到达基本块）此定值能到达基本块B的入口之前，且的入口之前，且B中不再对中不再对A重新定值重新定值 （即（即dINB-KILLB ） ； （2）或者点）或者点d在在B中，且对中，且对A的定值能到达的定值能到达B的出口之后（即的出口之后（即dGENB） OUTB=INBKILLB GENB

54、 (6.1)其次，程序中某一点其次，程序中某一点d d对变量对变量A A的定值可到的定值可到达基本块达基本块B B的入口之前，当且仅当此定值能的入口之前，当且仅当此定值能到达到达B B的某一直接前驱之后。的某一直接前驱之后。 （6.26.2）。）。 INB=PrBedbbOUT(PredB代表代表B的所有前驱基本块集合的所有前驱基本块集合)b)基本方程 OUTB=INBKILLBGENB (6.1) INB= （6.2） 注：注：1)由于所有由于所有KILLB和和GENB可从给定的流可从给定的流图中直接求出，所以，上述等式是关于变量图中直接求出，所以，上述等式是关于变量INB和和OUTB的线性

55、联立方程组，称为到达的线性联立方程组，称为到达定值数定值数据流方程。据流方程。 2)流图中若有流图中若有n个基本块，则此方程共有个基本块，则此方程共有2n个，个，其中其中GENB就是基本块内就是基本块内DAG图上的附标，图上的附标， KILLB指若指若Ai在本块内定值，就将所有在本块内定值，就将所有Ai定值点定值点(除本定值点除本定值点)均注销。均注销。PrBedbbOUT(PredB代表B的所有前驱基本块集合)算法算法6.3 迭代法求解集合方程组(6.1)-(6.2)1 for ( i=1; i=N; i+ ) 2 INBi = ;3 OUTBi = GENBi; 4 CHANGE = 1;

56、5 while( CHANGE ) 6 CHANGE=0;7 for ( i=1; i=N; i+ ) 8 NEWIN= ;9 if ( NEWIN! = INBi ) 10 CHANGE=1;11 INBi=NEWIN;12 OUTBi = ( INBi - KILLBi )GENBi; PrBedbbOUT例6.4 图6-66.3.3引用定值链引用定值链(ud链链)的计算及应用的计算及应用1、定义、定义假定在程序中某点假定在程序中某点u u引用了变量引用了变量A A，到达到达u的变量的变量A的的定值点集合定值点集合称为变量称为变量A在在u点的点的ud链。链。2、构成规则、构成规则a)在基本

57、块在基本块B中，变量中，变量A在引用点在引用点u前有定值点前有定值点d，并且并且d点的定值链能到达点的定值链能到达u，则，则A在在u点的点的ud链链=d. (6.5)b)若在基本块若在基本块B中，在中，在u点之前点之前无对无对A的定值点，的定值点，则变量则变量A在在u点的点的ud链链=INB中有关中有关A定值定值的集的集合合注：这里，链是指将集合中各定值点连在一起构注：这里，链是指将集合中各定值点连在一起构成链，以便于检索。成链，以便于检索。(6.6)例例6.5 变量变量I的引用点为的引用点为d2和和d6，J的引用为的引用为d4，d5和和d7。求出它们的求出它们的ud链。链。 对于基本块对于基

58、本块B1，由于，由于I的的引用点引用点d2之前有唯一的之前有唯一的定值点定值点d1，因此，因此， I在在d2的的ud链为链为d1。 对基本块对基本块B3，由于，由于J的引的引用点用点d4之前无之前无J的块内定的块内定值点，故值点，故J在在d4的的ud链为链为INB3中所包含的中所包含的J点的点的定值点，即定值点，即 d2，d4，d5。常数传播及相应地合并已知量 如果能到达某一点如果能到达某一点P有变量有变量A的唯一定值的唯一定值点点d：A := c （c为常数）为常数） P是是A的一个引用点，那么，在的一个引用点，那么，在P点点A的值的值也必然为也必然为c，故可将，故可将P点对点对A的引用代之

59、的引用代之以常数以常数c，这种操作称为常数传播。，这种操作称为常数传播。 在图在图6-6中，由于中，由于INB5=d3，d4，d5，故能到达，故能到达d6的的I 的定值点是的定值点是唯一的，即唯一的，即d3：I := 1 从而可知在从而可知在d6对对I的引用可替之以的引用可替之以常数常数1，也就是可，也就是可将将d6改写为改写为d6：I := 6 算法算法6.4 常数传播和合并已知量的处理CHANGE=1;while(CHANGE) CHANGE=0; for (程序中的每个语句s) for(s的每个运算量v) if(v在引用点s的ud链仅含一个d且语句d为v=C(C为常数) ) 把s中所有对

60、v的引用均替换为C; CHANGE=1; if(s右端含有运算符且每个运算量都为常数) C=s的右端表达式； 把语句s替换为A=C(A为语句的s左部量); CHANGE=1; 6.3.4活跃变量及数据流方程活跃变量及数据流方程1、活跃变量、活跃变量 变量变量A A在程序中某一点在程序中某一点P P是活跃的，是指在程是活跃的，是指在程序流图中，存在一条从序流图中，存在一条从P P到到A A的引用点的通路。的引用点的通路。 显然，如果变量显然，如果变量A A在基本块在基本块B B中的中的P P点定值，点定值，且从且从P P开始直到开始直到B B的出口都没有的出口都没有A A的引用点，若的引用点，若