编译原理：第10章 代码优化

《编译原理：第10章 代码优化》由会员分享，可在线阅读，更多相关《编译原理：第10章 代码优化（98页珍藏版）》请在金锄头文库上搜索。

1、第十章第十章 代码优化代码优化School of Computer Science & Technology Harbin Institute of Technology重点：重点：代码优化的任务，局部优化、循环优化、代码优化的任务，局部优化、循环优化、 全局优化的基本方法。全局优化的基本方法。 难点：难点：控制流分析，数据流分析。控制流分析，数据流分析。 2024/8/32第第10章章代码优化代码优化 10.1 优化的种类优化的种类10.2 控制流分析控制流分析10.3 数据流分析数据流分析10.4 局部优化局部优化10.5 循环优化循环优化10.6 全局优化全局优化10.6 本章小结本章小

2、结2024/8/33第第10章章代码优化代码优化n代代码优化就是化就是为了提高目了提高目标程序的效率，程序的效率，对程序程序进行等价行等价变换，亦即在保持功能不，亦即在保持功能不变的的前提下，前提下，对源程序源程序进行合理的行合理的变换，使得目，使得目标代代码具有更高的具有更高的时间效率和效率和/ /或空或空间效率。效率。n空空间效率和效率和时间效率有效率有时是一是一对矛盾，有矛盾，有时不能兼不能兼顾。n优化的要求：化的要求：n必必须是等价是等价变换( (保持功能保持功能) )n为优化的努力必化的努力必须是是值得的。得的。n有有时优化后的代化后的代码的效率反而会下降。的效率反而会下降。2024

3、/8/34代码优化程序的结构代码优化程序的结构n控制流分析控制流分析的主要目的是分析出程序的循的主要目的是分析出程序的循环结构。循构。循环结构中的代构中的代码的效率是整个程序的效率的关的效率是整个程序的效率的关键。n数据流分析数据流分析进行数据流信息的收集，主要是行数据流信息的收集，主要是变量的量的值的的获得和使用情况的数据流信息。得和使用情况的数据流信息。n到达到达- -定定义分析分析; ;活活跃变量分析量分析; ;可用表达式分析可用表达式分析. .n代码变换代码变换: :根据上面的分析根据上面的分析, ,对中中间代代码进行等价行等价变换. .控制流分析控制流分析数据流分析数据流分析代码变换

4、代码变换2024/8/3510.1 优化的种类优化的种类n机器相关性机器相关性n机器相关机器相关优化：寄存器化：寄存器优化，多化，多处理器理器优化，特殊指令化，特殊指令优化，无用指令消除等。化，无用指令消除等。n机器无关机器无关优化：化：n优化范化范围n局部局部优化：化：单个基本个基本块范范围内的内的优化，常量合并化，常量合并优化，化，公共子表达式公共子表达式删除，除，计算算强度削弱和无用代度削弱和无用代码删除。除。n全局全局优化：主要是基于循化：主要是基于循环的的优化：循化：循环不不变优化，化，归纳变量量删除，除，计算算强度削减。度削减。n优化化语言言级n优化化语言言级：针对中中间代代码，针

5、对机器机器语言。言。2024/8/36程序例子程序例子本本节所用的例子所用的例子i = m 1; j = n; v = an;(1) i := m 1while (1) (2) j := n do i = i +1; while(aiv);(4) v := at1 if (i = j) break;(5) i := i + 1 x=ai; ai=aj; aj=x;(6) t2 := 4 * i (7) t3 := at2 x=ai; ai=an; an=x; (8)if t3v goto(5)2024/8/37程序例子程序例子本本节所用的例子所用的例子i = m 1; j = n; v = a

6、n;(9) j := j 1 while (1) (10) t4 := 4 * j do i = i +1; while(aiv); (12)if t5v goto(9) if (i = j) break; (13)if i=j goto(23) x=ai; ai=aj; aj=x; (14) t6:=4 * i (15) x := at6x=ai; ai=an; an=x; . . .2024/8/38流图流图i := m 1j := nt1 := 4 * * nv := at1i := i + 1t2 := 4 * * it3 := at2if t3 v goto B3if i = j g

7、oto B6B4B3B5B6t6 := 4 * * ix := at6t7 := 4 * * i t8 := 4 * * jt9 := at8at7 := t9t10 := 4 * * jat10 := xgoto B2t11 := 4 * * ix := at11t12 := 4 * * i t13 := 4 * * nt14 := at13at12 := t14t15 := 4 * * n at15 := x 2024/8/39i := m 1j := nt1 := 4 * * nv := at1i := i + 1t2 := 4 * * it3 := at2if t3 v goto B3

8、if i = j goto B6B4B3B5B6t6 := 4 * * ix := at6t7 := 4 * * i t8 := 4 * * jt9 := at8at7 := t9t10 := 4 * * jat10 := xgoto B2t11 := 4 * * ix := at11t12 := 4 * * i t13 := 4 * * nt14 := at13at12 := t14t15 := 4 * * n at15 := x 10.1.1公共子表达式删除公共子表达式删除局部公共子表达式局部公共子表达式B5 x=ai; ai=aj; aj=x;2024/8/310i := m 1j :=

9、 nt1 := 4 * * nv := at1i := i + 1t2 := 4 * * it3 := at2if t3 v goto B3if i = j goto B6B4B3B5B6t6 := 4 * * ix := at6t7 := 4 * * i t8 := 4 * * jt9 := at8at7 := t9t10 := 4 * * jat10 := xgoto B2t11 := 4 * * ix := at11t12 := 4 * * i t13 := 4 * * nt14 := at13at12 := t14t15 := 4 * * n at15 := x 10.1.1公共子表达

10、式删除公共子表达式删除局部公共子表达式局部公共子表达式B5 x=ai; ai=aj; aj=x;2024/8/311i := m 1j := nt1 := 4 * * nv := at1i := i + 1t2 := 4 * * it3 := at2if t3 v goto B3if i = j goto B6B4B3B5B6t6 := 4 * * ix := at6t8 := 4 * * jt9 := at8at6 := t9at8 := xgoto B2t11 := 4 * * ix := at11t12 := 4 * * i t13 := 4 * * nt14 := at13at12 :

11、= t14t15 := 4 * * n at15 := x 10.1.1公共子表达式删除公共子表达式删除局部公共子表达式局部公共子表达式B5 x=ai; ai=aj; aj=x;2024/8/312i := m 1j := nt1 := 4 * * nv := at1i := i + 1t2 := 4 * * it3 := at2if t3 v goto B3if i = j goto B6B4B3B5B6t6 := 4 * * ix := at6t8 := 4 * * jt9 := at8at6 := t9at8 := xgoto B2t11 := 4 * * ix := at11t12 :

12、= 4 * * i t13 := 4 * * nt14 := at13at12 := t14t15 := 4 * * n at15 := x 10.1.1公共子表达式删除公共子表达式删除全局公共子表达式全局公共子表达式B5 x=ai; ai=aj; aj=x;2024/8/313i := m 1j := nt1 := 4 * * nv := at1i := i + 1t2 := 4 * * it3 := at2if t3 v goto B3if i = j goto B6B4B3B5B6x := at2t9 := at4at2 := t9at4 := xgoto B2t11 := 4 * *

13、ix := at11t12 := 4 * * i t13 := 4 * * nt14 := at13at12 := t14t15 := 4 * * n at15 := x 10.1.1公共子表达式删除公共子表达式删除全局公共子表达式全局公共子表达式B5 x=ai; ai=aj; aj=x;2024/8/314i := m 1j := nt1 := 4 * * nv := at1i := i + 1t2 := 4 * * it3 := at2if t3 v goto B3if i = j goto B6B4B3B5B6x := at2t9 := at4at2 := t9at4 := xgoto

14、B2t11 := 4 * * ix := at11t12 := 4 * * i t13 := 4 * * nt14 := at13at12 := t14t15 := 4 * * n at15 := x 10.1.1公共子表达式删除公共子表达式删除全局公共子表达式全局公共子表达式B5 x=ai; ai=aj; aj=x;2024/8/315i := m 1j := nt1 := 4 * * nv := at1i := i + 1t2 := 4 * * it3 := at2if t3 v goto B3if i = j goto B6B4B3B5B6x := t3at2 := t5at4 := x

15、goto B2t11 := 4 * * ix := at11t12 := 4 * * i t13 := 4 * * nt14 := at13at12 := t14t15 := 4 * * n at15 := x 10.1.1公共子表达式删除公共子表达式删除全局公共子表达式全局公共子表达式B5 x=ai; ai=aj; aj=x;2024/8/316i := m 1j := nt1 := 4 * * nv := at1i := i + 1t2 := 4 * * it3 := at2if t3 v goto B3if i = j goto B6B4B3B5B6x := t3at2 := t5at4

16、 := xgoto B2t11 := 4 * * ix := at11t12 := 4 * * i t13 := 4 * * nt14 := at13at12 := t14t15 := 4 * * n at15 := x 10.1.1公共子表达式删除公共子表达式删除将上述过程用于将上述过程用于B6B6 x = ai; ai = an; an = x;2024/8/317i := m 1j := nt1 := 4 * * nv := at1i := i + 1t2 := 4 * * it3 := at2if t3 v goto B3if i = j goto B6B4B3B5B6x := t3a

17、t2 := t5at4 := xgoto B2x := at3t14 := at1at2 := t14at1 := x 10.1.1公共子表达式删除公共子表达式删除将上述过程用于将上述过程用于B6B6 x = ai; ai = an; an = x;at1能能否否作作为为公公共共子子表表达达式？式？2024/8/318i := m 1j := nt1 := 4 * * nv := at1i := i + 1t2 := 4 * * it3 := at2if t3 v goto B3if i = j goto B6B4B3B5B6x := t3at2 := t5at4 := xgoto B2x :

18、= at3t14 := at1at2 := t14at1 := x 10.1.1公共子表达式删除公共子表达式删除将上述过程用于将上述过程用于B6B6 x = ai; ai = an; an = x;把把at1作为公作为公共子表达式是共子表达式是不稳妥的：不稳妥的：控制离开控制离开B B1 1进进入入B B6 6之前可能之前可能进入进入B B5 5，而，而B B5 5有对有对a a的赋值的赋值 2024/8/31910.1.2 复制传播复制传播n 形如形如f := g的的赋值语句叫做复制句叫做复制语句句n优化化过程中会大量引入复制程中会大量引入复制t := d + ea := t 删除局部公共子

19、表达式期间引进复制删除局部公共子表达式期间引进复制t := d + eb := tc := tc := d + eb := d + ea := d + e2024/8/32010.1.2 复制传播复制传播n复制复制传播播变换的思想是在复制的思想是在复制语句句f := g之后之后尽可能用尽可能用g代替代替fn复制复制传播播变换本身并不是本身并不是优化，但它化，但它给其它其它优化化带来机会来机会n无用代无用代码删除除x := t3at2 := t5at4 := t3goto B2x := t3at2 := t5at4 := xgoto B22024/8/32110.1.3 无用代码删除无用代码删除

20、n无用代无用代码是指是指计算算结果以后不被引用的果以后不被引用的语句句n一些一些优化化变换可能会引入无用代可能会引入无用代码n例：例：debug := true; debug := false; . . . 测试后改成后改成 . . .if(debug)print if(debug)print 2024/8/32210.1.3 无用代码删除无用代码删除n无用代无用代码是指是指计算算结果以后不被引用的果以后不被引用的语句句n一些一些优化化变换可能会引入无用代可能会引入无用代码例：复制例：复制传播可能会引入播可能会引入无用代无用代码x := t3at2 := t5at4 := t3goto B2a

21、t2 := t5at4 := t3goto B22024/8/32310.1.4 代码外提代码外提n结果独立于循果独立于循环执行次数的表达式称行次数的表达式称为循循环不不变计算。如果将循算。如果将循环不不变计算从循算从循环中移出到循中移出到循环的前的前面，将会减少循面，将会减少循环执行的代行的代码总数，大大提高代数，大大提高代码的的执行效率。行效率。这种与循种与循环有关的有关的优化方法称化方法称为代代码外提。外提。n例如，下面的例如，下面的while语句中，句中，limit-2就是循就是循环不不变计算。算。nwhile(i =limit-2 ) /*假假设循循环体中的体中的语句不改句不改变li

22、mit的的值*/n代代码外提将生成如下的等价外提将生成如下的等价语句：句：nt := limit-2;nwhile (i = t) /*假假设循循环体中的体中的语句不改句不改变limit或或t*/2024/8/32410.1.5 强度削弱强度削弱n实现同同样的运算可以有多种方式。用的运算可以有多种方式。用计算算较快的运算代替快的运算代替较慢的运算。慢的运算。nx2变成成x*x。n2*x或或2.0*x变成成x+xnx/2变成成x*0.5nanxn+an-1xn-1+a1x+a0变成成 (anx+an-1)x+ an-2)x+a1)x+a02024/8/32510.1.5 强度削弱强度削弱图图10

23、.6 将强度削弱应用到块将强度削弱应用到块B3中的中的4*j2024/8/32610.1.5 归纳变量删除归纳变量删除n在在围绕B3的循的循环的每次迭代中，的每次迭代中，j和和t4的的值总是同步是同步变化，每次化，每次j的的值减减l，t4的的值就减就减4，这是因是因为4*j赋给了了t4，我，我们将将这样的的变量称量称为归纳变量量 n如果循如果循环中存在两个或更多的中存在两个或更多的归纳变量，量，也也许可以只保留一个，而去掉其余的，以可以只保留一个，而去掉其余的，以便提高程序的运行效率。便提高程序的运行效率。 2024/8/32710.1.5 归纳变量删除归纳变量删除图图10.7 归纳变量删除后

24、的流图归纳变量删除后的流图2024/8/32810.2 控制流分析控制流分析n为了了对程序程序进行行优化，尤其是化，尤其是对循循环进行行优化，化，必必须首先分析程序中的控制流程，以便找出程首先分析程序中的控制流程，以便找出程序中的循序中的循环结构，构，这是控制流分析的主要任是控制流分析的主要任务。n为此，首先需要将程序划分此，首先需要将程序划分为基本基本块集合并集合并转换成流成流图，然后再从流，然后再从流图中找出循中找出循环。 2024/8/32910.2.1 基本块基本块n基本基本块(basic block)是一个是一个连续的的语句序列，句序列，控制流从它的开始控制流从它的开始进入，并从它的

25、末尾离开，入，并从它的末尾离开，中中间不存在中断或分支不存在中断或分支(末尾除外末尾除外)。下面的三。下面的三地址地址码序列就形成了一个基本序列就形成了一个基本块：nt1 : a*ant2 : a*bnt3 : 2*t2nt4 : t1+t3nt5 : b*bnt6 : t4+t52024/8/330基本块的划分算法基本块的划分算法n算法算法10.1 基本基本块的划分。的划分。n输入：一个三地址入：一个三地址码序列；序列；n输出：一个基本出：一个基本块列表，其中每个三地址列表，其中每个三地址码仅在一在一个个块中；中；n步步骤：n1首先确定所有的入口首先确定所有的入口(leader)语句，即基本

26、句，即基本块的第的第一个一个语句。确定入口的句。确定入口的规则如下：如下：na) 第一个第一个语句是入口句是入口语句；句；nb) 任何能由条件任何能由条件转移移语句或无条件句或无条件转移移语句句转移到的移到的语句句都是入口都是入口语句；句；nc) 紧跟在跟在转移移语句或条件句或条件转移后面的移后面的语句是入口句是入口语句。句。n2对于每个入口于每个入口语句，其基本句，其基本块由它和直到下一个入口由它和直到下一个入口语句句(但不含但不含该入口入口语句句)或程序或程序结束束为止的所有止的所有语句句组成。成。 2024/8/33110.2.2 流图流图n程序的控制流信息可以用流程序的控制流信息可以用

27、流图表示，流表示，流图是一是一个个节点点为基本基本块的有向的有向图。n以程序的第一个以程序的第一个语句作句作为入口入口语句的句的节点称点称为初始初始节点点。n如果在某个如果在某个执行序列中行序列中B2跟随在跟随在Bl之后，之后，则从从Bl到到B2有一条有向有一条有向边。n如果从如果从Bl的最后一条的最后一条语句有条件或无条件句有条件或无条件转移移到到B2的第一个的第一个语句；或者按程序正文的次序句；或者按程序正文的次序B2紧跟在跟在Bl之后，并且之后，并且Bl不是不是结束于无条件束于无条件转移，移，则称称B1是是B2的的前前驱，而，而B2是是Bl的的后后继。2024/8/33210.2.3 循

28、环循环n流流图中的中的循循环就是具有唯一入口的就是具有唯一入口的强连通子通子图，而且从循而且从循环外外进入循入循环内，必内，必须首先首先经过循循环的入口的入口节点。点。 n如果从流如果从流图的初始的初始节点到点到节点点n的每条路径都的每条路径都要要经过节点点d，则说节点点d支配支配(dominate)节点点n，记作作d dom n，d又称又称为n的的必必经节点点。n根据根据该定定义，每个，每个节点都支配它自身，而循点都支配它自身，而循环的入口的入口节点点则支配循支配循环中的所有中的所有节点。点。 2024/8/333支配节点集计算支配节点集计算 算法算法10.2 支配支配节点集点集计算。算。输

29、入：流入：流图G，其，其节点集点集为N，边集集为E，初始，初始节点点为n0输出：关系出：关系dom；步步骤：1D(n0) := n0;2for Nn0中的中的n do D(n) := ; /* 初始化完初始化完毕 */3while D(n)发生生变化化 do 4 for Nn0中的中的n do 5 D(n) := n D(p);2024/8/334循环循环 n循循环的性的性质：n循循环必必须有唯一的入口点，称有唯一的入口点，称为首首节点点(header)。首。首节点支点支配循配循环中的所有中的所有节点。点。n循循环至少迭代一次，亦即至少有一条返回首至少迭代一次，亦即至少有一条返回首节点的路径。

30、点的路径。n为了了寻找流找流图中的循中的循环，必，必须寻找可以返回到循找可以返回到循环入入口口节点的有向点的有向边，这种种边叫做叫做回回边(back edge)，如果，如果b dom a，则边ab称称为回回边。 利用支配利用支配节点集可以求点集可以求出流出流图中的所有回中的所有回边。n给定一条回定一条回边nd，定，定义该边的的自然循自然循环(natural loop)为d加上所有不加上所有不经过d而能到达而能到达n的的节点集合。点集合。d是是该循循环的首的首节点。点。 2024/8/335例例10.6n3 dom 4n回回边43n4 dom 7n回回边74n107的自然循的自然循环7，8，10

31、n74的自然循的自然循环4,5,6,7,8,10n43，83的自然循的自然循环3,4,5,6,7,8,102024/8/336自然循环的构造自然循环的构造 算法算法10.3 构造回构造回边的自然循的自然循环。输入：流入：流图G和回和回边nd；输出：由出：由nd的自然循的自然循环中所有中所有节点构成的集合点构成的集合loop；procedure insert(m);if m不在不在loop中中 then begin loop := loop m;将将m压入入栈stack end;/* 下面是主程序下面是主程序 */stack := 空空; loop := d; insert(n);while s

32、tack非空非空 do begin从从stack弹出第一个元素出第一个元素m;for m的每个前的每个前驱p do insert(p)end2024/8/337循环循环n如果将自然循如果将自然循环当作当作“循循环”，则循循环或者互不相或者互不相交，或者一个在另外一个里面。交，或者一个在另外一个里面。n内循内循环：不包含其他循：不包含其他循环的循的循环称称为内循内循环。n如果两个循如果两个循环具有相同的首具有相同的首节点，那么很点，那么很难说一个一个包含另外一个。此包含另外一个。此时把两个循把两个循环合并。合并。B0B1B2B32024/8/338循环循环n某些某些变换要求我要求我们将循将循环中

33、中的某些的某些语句移到首句移到首节点的前点的前面。因此，在开始面。因此，在开始处理循理循环L之前，往往需要先之前，往往需要先创建一建一个称个称为前置首前置首节点点的新的新块。前置首前置首节点的唯一后点的唯一后继是是L的首的首节点，原来从点，原来从L外到达外到达L首首节点的点的边都将改成都将改成进入入前置首前置首节点，从循点，从循环L里面里面到达首到达首节点的点的边不改不改变。n初始初始时前置首前置首节点点为空，但空，但对L的的变换可能会将一些可能会将一些语句放到句放到该节点中。点中。 首节点首节点 首节点首节点 前置首节点前置首节点2024/8/339可归约流图可归约流图n可可归约流流图：一个

34、流：一个流图G是可是可约的，当且的，当且仅当可以把它的当可以把它的边分成两个不相交的分成两个不相交的组，其中一其中一组仅含回含回边，另一，另一组的的边都不是都不是回回边，这些些边被称被称为前向前向边，所有前向，所有前向边形成一个无形成一个无环有向有向图，在，在该图中，每中，每个个节点都可以从点都可以从G的初始的初始节点到达。点到达。n循循环的可的可约流流图具有一个重要的性具有一个重要的性质，就是当流就是当流图中的一些中的一些节点被看作是循点被看作是循环的的节点集合点集合时，这些些节点之点之间一定包含一定包含一条回一条回边。于是，。于是，为了找出流了找出流图可可约程程序中的所有循序中的所有循环，

35、只要，只要检查回回边的自然的自然循循环即可。即可。 B1B2B3图图10.10 一个不可约流图一个不可约流图 2024/8/34010.3 数据流分析数据流分析n为了了进行代行代码优化，化，编译器必器必须掌握程序中掌握程序中变量的定量的定义和引用情况，有了和引用情况，有了这些信息才能些信息才能对源程序源程序进行合适的等价行合适的等价变换。n例如，了解每个基本例如，了解每个基本块的出口的出口处哪些哪些变量是活量是活跃的可以改的可以改进寄存器的利用率，寄存器的利用率，执行常量合并和无行常量合并和无用代用代码删除除则需要利用需要利用变量的量的“到达到达- -定定义”信息。信息。 n对程序中程序中变量

36、的定量的定义和引用关系的分析称和引用关系的分析称为数据流分析数据流分析 2024/8/341数据流分析的种类数据流分析的种类n到达到达- -定定义分析分析n活活跃变量分析量分析n可用表达式分析可用表达式分析2024/8/34210.3.1 数据流方程的一般形式数据流方程的一般形式n下面的方程叫做数据流方程：下面的方程叫做数据流方程：noutS = genS(inS-killS) (10.3) 该方程的含方程的含义是，当控制流通是，当控制流通过一个一个语句句S时，在，在S末尾得到的信息末尾得到的信息(outS)或者是在或者是在S中中产生的信息生的信息(genS)，或者是，或者是进入入S开始点开始

37、点时携携带的、并且没有的、并且没有被被S注注销的那些信息的那些信息(inS表示表示进入入S开始点开始点时携携带的信息，的信息，killS表示被表示被S注注销的信息的信息)。n也可以根据也可以根据outS来定来定义inS inS = (outS-killS)genS (10.4) 2024/8/34310.3.1 数据流方程的一般形式数据流方程的一般形式n不同的不同的问题方程的意方程的意义可能有所不同，主要可可能有所不同，主要可由以下两点来区由以下两点来区别：n信息流向信息流向问题。根据信息流向可以将数据流分析。根据信息流向可以将数据流分析问题分分为正向和反向两正向和反向两类，正向的含，正向的含

38、义是根据是根据in集合集合来来计算算out集合，反向集合，反向则是从是从out集合来集合来计算算in集合。集合。n聚合操作聚合操作问题。所。所谓聚合操作，是指当有多条聚合操作，是指当有多条边进入某一基本入某一基本块B时，由，由B的前的前驱节点的点的out集集计算算inB时采用的集合操作采用的集合操作(并或交并或交)。到达。到达-定定义等方程等方程采用并操作，全局可用表达式采用的采用并操作，全局可用表达式采用的则是交操作。是交操作。2024/8/34410.3.1 数据流方程的一般形式数据流方程的一般形式n在基本在基本块中，将相中，将相邻语句句间的位置称的位置称为点点，第一个，第一个语句前和最后

39、一个句前和最后一个语句后的位置也称句后的位置也称为点。从点点。从点pl到点到点pn的路径是的路径是这样的点序列的点序列pl，p2,，pn,对于于 i(lin-1)下列条件之一成立：下列条件之一成立：npi是是紧接在一个接在一个语句前面的点，句前面的点，pi+1是同一是同一块中中紧跟在跟在该语句句后面的点；后面的点；npi是某基本是某基本块的的结束点，而束点，而pi+1是后是后继块的开始点。的开始点。n为简单起起见，假，假设控制只能从一个开始点控制只能从一个开始点进入基本入基本块，而当基本而当基本块结束束时控制只能从一个控制只能从一个结束点离开。束点离开。 2024/8/34510.3.2 到达

40、到达-定义分析定义分析n变量量x x的定的定义是一条是一条赋值或可能或可能赋值给x x的的语句。句。最普通的定最普通的定义是是对x x的的赋值或从或从I/OI/O设备读一个一个值并并赋给x x的的语句，句，这些些语句比句比较明确地明确地为x x定定义了一个了一个值，称，称为x x的明确定的明确定义。也有一些。也有一些语句句只是可能只是可能为x x定定义一个一个值，称，称为x x的含糊定的含糊定义，其常其常见形式有：形式有：n1 1以以x x为参数的参数的过程程调用用( (传值方式除外方式除外) )或者可能或者可能访问x x的的过程；程；n2 2通通过可能指向可能指向x x的指的指针对x x赋值

41、。 2024/8/34610.3.2 到达到达-定义分析定义分析n对于定于定义d，如果存在一条从，如果存在一条从紧跟跟d的点到的点到p的路的路径，并且在径，并且在这条路径上条路径上d没有被没有被“注注销”，则称称定定义d到达到达(reach)点点p。n如果沿着如果沿着这条路径的某两点条路径的某两点间存在存在a的其它定的其它定义，则将将注注销(kill)变量量a的那个定的那个定义。注意，只有。注意，只有a的明确定的明确定义才能注才能注销a的其它定的其它定义。n到达定到达定义信息可以用引用信息可以用引用-定定义链(即即ud-链)来保来保存，它是一个存，它是一个链表，表，对于于变量的每次引用，到量的

42、每次引用，到达达该引用的所有定引用的所有定义都保存在都保存在该链表中。表中。2024/8/34710.3.2 到达到达-定义分析定义分析n如果如果块B中在中在变量量a的引用之前没有任何的引用之前没有任何a的明的明确定确定义，那么，那么a的的这次引用的次引用的ud-链为inB中中a的定的定义的集合。如果的集合。如果B中在中在a的的这次引用之前存次引用之前存在在a的明确定的明确定义，那么只有，那么只有a的最后一次定的最后一次定义会会在在ud-链中，而中，而inB不能放在不能放在ud-链中中n另外，如果存在另外，如果存在a的含糊定的含糊定义，那么所有那些在，那么所有那些在该定定义和和a的的这次引用之

43、次引用之间没有没有a的明确定的明确定义的的定定义都将被放在都将被放在a的的这次引用的次引用的ud-链中中n利用利用ud-链可以求出循可以求出循环中的所有循中的所有循环不不变计算，算，常量常量传播也需要用到播也需要用到ud-链信息信息2024/8/348到达定义数据流方程到达定义数据流方程(记号记号)ninB: 表示基本表示基本块B的入口点的入口点处各个各个变量的量的定定义集合。集合。n如果如果B中点中点p之前有之前有x的定的定义d，且，且这个定个定义能能够到达到达p，则点点p处x的的ud链是是d。n否否则，点，点p处x的的ud链就是就是inB中中x的定的定义集合。集合。nPB：B的所有前的所有

44、前驱基本基本块的集合。的集合。2024/8/349到达定义数据流方程到达定义数据流方程(记号记号)ngenB：各个：各个变量在量在B内定内定义，并能，并能够到达到达B的出口点的所有定的出口点的所有定义的集合。的集合。noutB：各个：各个变量的能量的能够到达基本到达基本块B的出的出口点的所有定口点的所有定义的集合。的集合。nkillB：各个：各个变量在基本量在基本块B中重新定中重新定义，即在此即在此块内部被注内部被注销的定的定义点的集合。点的集合。2024/8/350到达定义数据流方程到达定义数据流方程ninB = outp where p is in PBnoutB = genB (inB-

45、killB)n其中：其中：ngenB可以从基本可以从基本块中求出：使用中求出：使用DAG图就就可以得到。可以得到。nkillB中，中，对于整个流于整个流图中的所有中的所有x的定的定义点，点，如果如果B中有中有对x的定的定义，那么，那么该定定义点在点在killB中。中。2024/8/351方程求解算法方程求解算法n使用迭代方法。使用迭代方法。初始初始值设置置为：inBi=空；空；outB=genBi;change = true;while(change) change = false;for each B doinB = outp where p is in PB; outB = genB (i

46、nB-killB); oldout = outB; if(outB != oldout) change = true;2024/8/352算法例子算法例子ngenB1=d1,d2,d3nkillB1=d4,d5,d6,d7ngenB2=d4,d5nkillB2=d1,d2,d7ngenB3=d6nkillB3=d3ngenB4=d7nkillB4=d1,d4d1: -m1id2: = njd3: = u2ad4: + i1id5: -j1jd6: = u2ad7: = u3iB1B2B3B42024/8/353计算过程计算过程n初始化：初始化：ninB1 =inB2 =inB3 = inB4

47、=空空noutB1=d1,d2,d3, outB2=d4,d5noutB3=d6, outB4=d7.n第一次循第一次循环：ninB1=空空; inB2 =d1,d2,d3,d7; inB3=d4,d5;ninB4=d4,d5,d6; outB1=d1,d2,d3;noutB2=d3,d4,d5n结果：果：ninB1=空；空；out B1=d1,d2,d3;ninB2=d1,d2,d3,d5,d6,d7; outB2=d3,d4,d5,d6;ninB3=d3,d4,d5,d6;out B3=d4,d5,d6;ninB4=d3,d4,d5,d6; outB4=d3,d5,d6,d7;2024/8

48、/35410.3.3 活跃变量分析活跃变量分析n对于于变量量x和点和点p，在流，在流图中沿从中沿从p开始的某条路径，开始的某条路径，是否可以引用是否可以引用x在在p点的点的值。如果可以。如果可以则称称x在在p点是活点是活跃的，否的，否则，x在在p点就是无用的。点就是无用的。n活活跃变量信息在目量信息在目标代代码生成生成时具有重要的作用。当具有重要的作用。当我我们在寄存器中在寄存器中计算一个算一个值之后，通常假之后，通常假设在某个在某个块中中还要引用它，如果它在要引用它，如果它在该块的末尾是无用的，的末尾是无用的，则不不需要存需要存储该值。n消除复制四元式的依据也是消除复制四元式的依据也是对活活

49、跃变量的分析。量的分析。如果如果某个某个变量的量的值在以后不被引用，那么在以后不被引用，那么该复制四元式可复制四元式可以被消除。以被消除。2024/8/355记号记号ninB: 基本基本块B的入口点的活的入口点的活跃变量集合。量集合。noutB: 是在基本是在基本块B的出口点的活的出口点的活跃变量集。量集。ndefB: 是在基本是在基本块b内的定内的定义，但是定，但是定义前在前在B中没有被引用的中没有被引用的变量的集合。量的集合。nuseB: 表示在基本表示在基本块中引用，但是引用前在中引用，但是引用前在B中没有被定中没有被定义的的变量集合。量集合。n其中，其中，defB和和useB是可以从基

50、本是可以从基本块B中直接中直接求得的量，因此在方程中作求得的量，因此在方程中作为已知量。已知量。2024/8/356活跃变量数据流方程活跃变量数据流方程ninB = useB (outB-defB)noutB = inS，其中，其中S为B的所有后的所有后继。n变量在某点活量在某点活跃，表示，表示变量在量在该点的点的值在以后会被使用。在以后会被使用。n第一个方程表示：第一个方程表示：n一个一个变量在量在进入入块B时是活是活跃的，如果它在的，如果它在该块中于定中于定义前被引用前被引用n一个一个变量在离开量在离开块B时是活是活跃的，而且在的，而且在该块中没有被重中没有被重新定新定义。 n第二个方程表

51、示：第二个方程表示：n一个一个变量在离开量在离开块B时是活是活跃的，当且的，当且仅当它在当它在进入入该块的某个后的某个后继时是活是活跃的。的。 2024/8/357活跃变量数据流方程求解活跃变量数据流方程求解n设置初置初值：inBi=空空;n重复重复执行以下步行以下步骤直到直到inBi不再改不再改变：for(i=1; i=2)n重复重复执行下列算法直到行下列算法直到out稳定定:for（i=2; i=n ;i+) inBi= outp, p是是Bi的前的前驱；outBi=e_genBi (inBi-e_killBi);2024/8/367算法说明算法说明n初始化初始化值和前面的两个算法不同。和

52、前面的两个算法不同。outBi的初的初值大于大于实际的的值。n在迭代的在迭代的过程种，程种，outBi的的值逐逐渐缩小直小直到到稳定。定。nU表示四元式的全集，就是四元式序列中表示四元式的全集，就是四元式序列中所有表达式所有表达式x op y的集合。的集合。2024/8/36810.4 局部优化局部优化n基本基本块的功能的功能实际上就是上就是计算一算一组表达式，表达式，这些表达式是在基本些表达式是在基本块出口活出口活跃的的变量的量的值。如。如果两个基本果两个基本块计算一算一组同同样的表达式，的表达式，则称它称它们是等价的。是等价的。 n可以可以对基本基本块应用很多用很多变换而不改而不改变它所它

53、所计算算的表达式集合，的表达式集合，许多多这样的的变换对改改进最最终由由某基本某基本块生成的代生成的代码的的质量很有用。量很有用。 n利用基本利用基本块的的dag表示可以表示可以实现一些常用的一些常用的对基本基本块的的变换。 2024/8/36910.4.1 基本块的基本块的dag表示表示 ndag的构造方法的构造方法 基本基本块中出中出现的每个的每个变量都有一个量都有一个dag节点表示其点表示其初始初始值。 基本基本块中的每个中的每个语句句s都有一个都有一个dag节点点n与之相关与之相关联。n的子的子节点是那些在点是那些在s之前、最后一次之前、最后一次对s中用中用到的运算到的运算对象象进行定

54、行定义的的语句所句所对应的的节点。点。 节点点n由由s中用到的运算符来中用到的运算符来标记，节点点n还附加了附加了一一组变量，量，这些些变量在基本量在基本块中都是由中都是由s最后定最后定义的。的。 如果有的如果有的话，还要要记下那些其下那些其值在在块的出口是活的出口是活跃的的节点，它点，它们是是输出出节点。流点。流图的另一个基本的另一个基本块以后可能会用到以后可能会用到这些些变量的量的值。 2024/8/370利用利用dag进行的基本块变换进行的基本块变换 局部公共子表达式局部公共子表达式删除。除。 无用代无用代码删除。除。 交交换两个独立的相两个独立的相邻语句的次序，以便减少句的次序，以便减

55、少某个某个临时值需要保存在寄存器中的需要保存在寄存器中的时间。 使用代数使用代数规则重新排列三地址重新排列三地址码的运算的运算对象象的的顺序，以便序，以便简化化计算算过程。程。2024/8/37110.4.2 局部公共子表达式删除局部公共子表达式删除 n例例10.12a := b+cb := a-dc := b+cd := a-d (10.8)n如果如果b在出口在出口处不是活不是活跃的：的：a := b+cd := a-dc := d+c 图图10.13 基本块基本块(10.8)的的dag2024/8/37210.4.3 无用代码删除无用代码删除 n在在dag上上删除无用代除无用代码的方法很的

56、方法很简单：只要从：只要从dag上上删除所有没除所有没有附加活有附加活跃变量的根量的根节点点(即没有父即没有父节点的点的节点点)即可。重复即可。重复进行行这样的的处理即可从理即可从dag中中删除所有与无用代除所有与无用代码相相对应的的节点。点。a := b+cb := b-dc := c+de := b+c 图10.14中的中的a和和b是活是活跃变量，量，而而c和和e不是，我不是，我们可以立即可以立即删除除标记为e的根的根节点。随后，点。随后，标记为c的的节点点变成了根成了根节点，点，下一步也可以被下一步也可以被删除。除。 图图10.14基本块基本块(10.9)的的dag2024/8/3731

57、0.4.4代数恒等式的使用代数恒等式的使用 n代数恒等式代表基本代数恒等式代表基本块上另一上另一类重要的重要的优化方化方法，下面是一些常法，下面是一些常见的代数恒等式：的代数恒等式：nx+0 = 0+x = x x0 = x x*1 = 1*x = x x/1 = xn另外一另外一类代数代数优化是局部化是局部强度削弱，即用度削弱，即用较快快的运算符取代的运算符取代较慢的运算符，例如：慢的运算符，例如：nx*2 = x*x 2.0*x = x+x x/2 = x*0.52024/8/37410.4.4代数恒等式的使用代数恒等式的使用 n第三第三类相关的相关的优化技化技术是常量合并。即在是常量合并

58、。即在编译时对常量表达式常量表达式进行行计算，并利用它算，并利用它们的的值取取代常量表达式。例如，表达式代常量表达式。例如，表达式2*3.14可以替可以替换为6.28。ndag构造构造过程可以帮助我程可以帮助我们应用上述和更多其用上述和更多其它的通用代数它的通用代数变换，比如交，比如交换律和律和结合律。合律。 2024/8/37510.4.5 数组引用的数组引用的dag表示表示 n在在dag中表示数中表示数组访问的正确方法的正确方法为：n将数将数组元素元素赋给其他其他变量的运算量的运算(如如x = ai)用一个用一个新新创建的运算符建的运算符为=的的节点表示。点表示。该节点的左右子点的左右子节

59、点分点分别代表数代表数组初始初始值(本例中本例中为a0)和下和下标i。变量量x则是是该节点的附加点的附加标记之一。之一。n对数数组元素的元素的赋值(如如aj=y)则用一个新用一个新创建的运算建的运算符符为=的的节点来表示。点来表示。该节点的三个子点的三个子节点分点分别表表示示a0、j和和y。该节点不点不带任何附加任何附加标记。这是因是因为该节点的点的创建注建注销了所有当前已了所有当前已经创建的、其建的、其值依依赖于于a0的的节点，而一个被注点，而一个被注销的的节点不可能再点不可能再获得得任何任何标记。也就是。也就是说，它不可能成，它不可能成为一个公共子表一个公共子表达式。达式。2024/8/3

60、7610.4.5 数组引用的数组引用的dag表示表示 n例例10.14 基本基本块x = aiaj = yz = ai的的dag如如图10.15所示。所示。图图10.15 将数组元素赋值给将数组元素赋值给其他变量的语句序列的其他变量的语句序列的dag2024/8/37710.4.6 指针赋值和过程调用的指针赋值和过程调用的dag表示表示 n当像当像语句句x=*p或或*q=y那那样通通过指指针进行行间接接赋值时，并不知道并不知道p和和q指向哪里。指向哪里。nx=*p可能是可能是对任意某个任意某个变量的引用，而量的引用，而*q=y则可能是可能是对任意某个任意某个变量的量的赋值。因而，运算符。因而，

61、运算符=*必必须把当前把当前所有所有带有附加有附加标识符的符的节点当作其参数。但点当作其参数。但这么做将么做将会影响无用代会影响无用代码的的删除。更除。更为严重的是，重的是，*=运算符将运算符将把所有迄今把所有迄今为止构造出来的止构造出来的dag中的其他中的其他节点全部注点全部注销。n可以可以进行一些全局指行一些全局指针分析，以便把一个指分析，以便把一个指针在代在代码中某个位置上可能指向的中某个位置上可能指向的变量限制在一个量限制在一个较小的的子小的的子集内。集内。2024/8/37810.4.7 从从dag到基本块的重组到基本块的重组 n对每个具有一个或多个附加每个具有一个或多个附加变量的量

62、的节点，构造点，构造一个三地址一个三地址码来来计算其中某个算其中某个变量的量的值。尽量。尽量把把计算得到的算得到的结果果赋给一个在基本一个在基本块出口出口处活活跃的的变量，如果没有全局活量，如果没有全局活跃变量的信息，量的信息，则假假设程序的所有程序的所有变量在基本量在基本块的出口的出口处都是活都是活跃的的(临时变量除外量除外)。n如果如果节点具有多个附加的活点具有多个附加的活跃变量，量，则必必须引引入复制入复制语句，以便句，以便为每一个每一个变量都量都赋予正确的予正确的值。当然，通。当然，通过全局全局优化技化技术可以消除可以消除这些复些复制制语句。句。 2024/8/37910.4.7 从从

63、dag到基本块的重组到基本块的重组 n当从当从dag重构基本重构基本块时，不，不仅要关心用哪些要关心用哪些变量来存放量来存放dag中中节点的点的值，还要关心要关心计算不同算不同节点点值的的语句句顺序。下面是序。下面是应遵循的遵循的规则： 语句的句的顺序必序必须遵守遵守dag中中节点的点的顺序。也就是序。也就是说，只有在只有在计算出某个算出某个节点的各个子点的各个子节点的点的值之后，才之后，才能能计算算该节点的点的值。 对数数组的的赋值必必须跟在所有跟在所有(按照原基本按照原基本块中的中的语句句顺序序)在它之前的在它之前的对同一数同一数组的的赋值或引用之后或引用之后2024/8/38010.4.

64、7 从从dag到基本块的重组到基本块的重组 对数数组元素的引用必元素的引用必须跟在所有跟在所有(在原基本在原基本块中中)在在它之前的它之前的对同一数同一数组的的赋值语句之后。句之后。对同一数同一数组的两次引用可以交的两次引用可以交换顺序，前提是交序，前提是交换时它它们都没都没有越有越过某个某个对同一数同一数组的的赋值运算。运算。 对某个某个变量的引用必量的引用必须跟在所有跟在所有(在原基本在原基本块中中)在在它之前的它之前的过程程调用或指用或指针赋值运算之后。运算之后。 任何任何过程程调用或指用或指针赋值都必都必须跟在所有跟在所有(在原基在原基本本块中中)在它之前的在它之前的对任何任何变量的引

65、用之后。量的引用之后。 2024/8/38110.5 循环优化循环优化n循循环不不变计算的算的检测n代代码外提外提n归纳变量量删除和除和强度削弱度削弱2024/8/38210.5.1循环不变计算的检测循环不变计算的检测 算法算法10.7 循循环不不变计算算检测。输入：由一入：由一组基本基本块构成的循构成的循环L，每个基本，每个基本块包括一系列的三包括一系列的三地址地址码，且每个三地址，且每个三地址码的的ud-链均可用；均可用；输出：从控制出：从控制进入循入循环L一直到离开一直到离开L，每次都，每次都计算同算同样值的三地的三地址址码；步步骤：1将如下将如下语句句标记为“不不变”：它：它们的运算的

66、运算对象或者是常数，象或者是常数，或者它或者它们的所有到达的所有到达-定定义都在循都在循环L的外面。的外面。2重复步重复步骤(3),直到某次重复没有新的直到某次重复没有新的语句可句可标记为“不不变”为止止3将如下将如下语句句标记为“不不变”：它：它们先前没有被先前没有被标记，而且它，而且它们的所有运算的所有运算对象或者是常数，或者其到达定象或者是常数，或者其到达定义都在循都在循环L之之外，或者只有一个到达定外，或者只有一个到达定义，这个定个定义是循是循环L中已中已标记为“不不变”的的语句。句。2024/8/38310.5.2 代码外提代码外提n将将语句句s：x:= y+z外提的条件：外提的条件

67、：1含有含有语句句s的的块是循是循环中所有出口中所有出口节点的支配点的支配节点，点，出口出口节点指的是其后点指的是其后继节点不在循点不在循环中的中的节点点2循循环中没有其它中没有其它语句句对x赋值。如果。如果x是只是只赋值一一次的次的临时变量，量，该条件肯定条件肯定满足，因此不必足，因此不必检查。3循循环中中x的引用的引用仅由由s到达，如果到达，如果x是是临时变量，量，该条件一般也可以条件一般也可以满足。足。2024/8/38410.5.2 代码外提代码外提n算法算法10.8 代代码外提外提n输入：入：带有有ud-链和支配和支配节点信息的循点信息的循环L；n输出：循出：循环的修正版本，增加了前

68、置首的修正版本，增加了前置首节点，且点，且(可能可能)有一些有一些语句外提到前置首句外提到前置首节点中；点中；n步步骤：1应用算法用算法10.7寻找循找循环不不变语句。句。2对(1)中找到的每个定中找到的每个定义x的的语句句s，检查是否是否满足下列条件：足下列条件：a) s所在的所在的块支配支配L的所有出口；的所有出口；b) x在在L的其它地方没有被定的其它地方没有被定义，而且，而且c) L中所有中所有x的引用只能由的引用只能由s中中x的定的定义到达。到达。3按算法按算法10.7找出的次序，把找出的次序，把(1)中找出的中找出的满足足(2)中中3个条件的每个条件的每个个语句移到新的前置首句移到

69、新的前置首节点。但是，若点。但是，若s的运算的运算对象在象在L中被定中被定义(由算法由算法10.7的的(3)找出找出这种种s)，那么只有，那么只有这些些对象的定象的定义语句句外提到前置首外提到前置首节点后，才能外提点后，才能外提s。2024/8/38510.5.3 归纳变量删除和强度削弱归纳变量删除和强度削弱 n算法算法10.9 归纳变量量检测输入：入：带有到达定有到达定义信息和循信息和循环不不变计算信息算信息(由算法由算法10.7得到得到)的循的循环L；输出：一出：一组归纳变量，以及与每个量，以及与每个归纳变量量j相关相关联的三的三元元组(i, c, d)，其中，其中i是基本是基本归纳变量，

70、量，c和和d是常量，在是常量，在j的定的定义点，点，j的的值由由c*i+d给出。称出。称j属于属于i族，基本族，基本归纳变量量i也属于它自己的族；也属于它自己的族；步步骤：1在循在循环L中找出所有的基本中找出所有的基本归纳变量，此量，此处需要用到需要用到循循环不不变计算的信息。与每个基本算的信息。与每个基本归纳变量量i相关相关联的的三元三元组为(i, 1, 0)。2024/8/38610.5.3 归纳变量删除和强度削弱归纳变量删除和强度削弱 2在在L中中寻找具有下列形式之一且只被找具有下列形式之一且只被赋值一次的一次的变量量k：k:j*b， k:b*j， k:j/b， k:jb， k:bj其中

71、，其中，b是常数，是常数，j是基本的或非基本的是基本的或非基本的归纳变量。量。如果如果j是基本是基本归纳变量，量，则k在在j族中。族中。k的三元的三元组依依赖于定于定义它的它的语句。例如，如果句。例如，如果k是由是由k:j*b定定义的，的，则k的三元的三元组为(j, b, 0)。类似地可以定似地可以定义其他情况的三元其他情况的三元组。如果如果j不是基本不是基本归纳变量，假量，假设j属于属于i族，族，则j还要要满足如下足如下要求：要求：na) 在循在循环L中中对j的唯一的唯一赋值和和对k的的赋值之之间没有没有对i的的赋值。nb) 循循环L外没有外没有j的定的定义可到达可到达k。 此此时利用利用j

72、的三元的三元组(i, c, d)和定和定义k的的语句即可句即可计算算k的三元的三元组。例如，定。例如，定义k:b*j导致致k的三元的三元组为(i, b*c, b*d)。注意，。注意，b*c和和b*d可以在分析可以在分析过程中完成程中完成计算，因算，因为b，c和和d都是常都是常数。数。2024/8/38710.5.3 归纳变量删除和强度削弱归纳变量删除和强度削弱 算法算法10.10 用于用于归纳变量的量的强度削弱。度削弱。输入：循入：循环L，附，附带有到达定有到达定义信息和由算法信息和由算法10.9算出的算出的归纳变量族；量族；输出：修正后的循出：修正后的循环；步步骤：依次考察每个基本：依次考察

73、每个基本归纳变量量i。对每个三元每个三元组为(i, c, d)的的i族族归纳变量量j，执行如下步行如下步骤：1建立新建立新变量量s，但如果，但如果变量量jl和和j2具有同具有同样的的三元三元组，则只只为它它们建立一个新建立一个新变量。量。2用用j:s代替代替对j的的赋值。2024/8/38810.5.3 归纳变量删除和强度削弱归纳变量删除和强度削弱 3在在L中中紧跟在每个跟在每个赋值语句句i:i+n之后之后(n是常数是常数)，添加上如下添加上如下语句：句：s := s + c*n 其中，表达式其中，表达式c*n的的计算算结果果为一个常数，因一个常数，因为c和和n都是常数。将都是常数。将s放入放

74、入i族，其三元族，其三元组为(i, c, d)。4必必须保保证在循在循环的入口的入口处s的初的初值为c*i+d，该初始化初始化可以放在前置首可以放在前置首节点的末尾，由下面两个点的末尾，由下面两个语句句组成：成：s : c*i * 如果如果c为1，则为s:=i * s : s+d * 如果如果d为0则省略省略 *注意，注意，s是是i族的族的归纳变量。量。2024/8/389图图10.20 强度削弱强度削弱2024/8/39010.5.3 归纳变量删除和强度削弱归纳变量删除和强度削弱 算法算法10.11 归纳变量量删除除输入：入：带有到达有到达-定定义信息、循信息、循环不不变计算信息算信息(利用

75、算法利用算法10.7求得求得)和活和活跃变量信息的循量信息的循环L；输出：修正后的循出：修正后的循环；步步骤：2024/8/39110.5.3 归纳变量删除和强度削弱归纳变量删除和强度削弱 1考考虑每个每个仅用于用于计算同族中其它算同族中其它归纳变量和条件分量和条件分支的基本支的基本归纳变量量i。取。取i族的某个族的某个j，优先取其三元先取其三元组(i, c, d)中的中的c和和d尽可能尽可能简单的的j(即即优先考先考虑cl和和d0的情况的情况)，把每个包含，把每个包含i的的测试语句改成用句改成用j代替代替i。假定。假定下面的下面的c是正的。用下面的是正的。用下面的语句来代替形如句来代替形如i

76、f i relop x goto B的的测试语句，其中句，其中x不是不是归纳变量。量。r:c*x * 如果如果c等于等于1，则为r:x *r:r+d * 如果如果d为0则省略省略 *if i relop x goto B 最后，因最后，因为被被删除的除的归纳变量已量已经没有什么用没有什么用处，所，所以从循以从循环中中删除所有除所有对它它们的的赋值。2024/8/39210.5.3 归纳变量删除和强度削弱归纳变量删除和强度削弱 2再再考考虑由由算算法法10.10为其其引引入入语句句j:=s的的每每个个归纳变量量j。首首先先检查在在引引入入的的j:s和和任任何何j的的引引用用之之间有有没没有有对s

77、的的赋值，应该是是没没有有。一一般般情情况况下下，j在在定定义它它的的块中中被被引引用用，这可可以以简化化该检查；否否则，需需要要用用到到达达定定义信信息息，并并加加上上一一些些对图的的分分析析来来实现这种种检查。然然后后用用对s的的引用代替所有引用代替所有对j的引用，并的引用，并删除除语句句j:s。2024/8/39310.6 全局优化全局优化n全局公共子表达式的全局公共子表达式的删除除n复制复制传播播2024/8/39410.6.1 全局公共子表达式删除全局公共子表达式删除 算法算法10.12 全局公共子表达式全局公共子表达式删除。除。输入：入：带有可用表达式信息的流有可用表达式信息的流图

78、；输出：修正后的流出：修正后的流图；步步骤：对每个形如每个形如x:=y+z的的语句句s，如果，如果y+z在在s所在所在块的开始点是的开始点是可用的，且可用的，且该块中在中在语句句s之前没有之前没有对y或或z的定的定义，则执行下行下面的步面的步骤：1为寻找到达找到达s所在所在块的的y+z的的计算，只需沿流算，只需沿流图的的边从从该块开始开始反向搜索，但不穿反向搜索，但不穿过任何任何计算算y+z的的块。在遇到的每个。在遇到的每个块中，中，对y+z的最后一次的最后一次计算将是到达算将是到达s的的y+z的的计算。算。2建立新建立新变量量u。3把把(1)中找到的每个中找到的每个语句句w:=y+z用如下用

79、如下语句代替：句代替：u := y+zw := u4用用x:=u代替代替语句句s。2024/8/39510.6.2 复制传播复制传播n算法算法10.12、归纳变量量删除算法和其它一些算法除算法和其它一些算法都会引入形如都会引入形如x:y的代的代码。n如果能找出复制代如果能找出复制代码s：x:=y中定中定义x的所有引的所有引用点，并用用点，并用y代替代替x，则可以可以删除除该复制复制语句。句。前提是前提是x的每个引用的每个引用u必必须满足下列条件：足下列条件：1 s必必须是到达是到达u的的x的唯一定的唯一定义(即引用即引用u的的ud-链只只包含包含s)。2在从在从s到到u的每条路径，包括穿的每条

80、路径，包括穿过u若干次若干次(但没有但没有第二次穿第二次穿过s)的路径上，没有的路径上，没有对y的的赋值。2024/8/39610.6.2 复制传播复制传播算法算法10.13复制复制传播。播。输入：流入：流图G；到达每个；到达每个块B的定的定义的的ud-链；c_inB，即沿着每，即沿着每条路径到达条路径到达块B的复制的复制语句句x:=y的集合，在的集合，在这些路径上些路径上x:y的的最后一次出最后一次出现之后没有再之后没有再对x或或y进行行赋值；每个定；每个定义的引用的的引用的du-链；输出：修正后的流出：修正后的流图；步步骤：对每个复制每个复制s：x:=y执行下列步行下列步骤：1确定由确定由

81、该x的定的定义所能到达的那些所能到达的那些x的引用。的引用。2对(1)中找到的每个中找到的每个x的引用，确定的引用，确定s是否在是否在c_inB中，其中中，其中块B是含有是含有x的本次引用的基本的本次引用的基本块，而且，而且块B中中该引用的前面没有引用的前面没有x或或y的定的定义。回想一下，如果。回想一下，如果s在在c_inB中，那么中，那么s是唯一的到是唯一的到达达块B的的x的定的定义。3如果如果s满足足(2)中的条件，中的条件，则删掉掉s，且把，且把(1)中找出的所有中找出的所有x的引的引用用用用y来代替。来代替。 2024/8/397本章小结本章小结n代代码优化就是化就是对程序程序进行等

82、价行等价变换，以提高目，以提高目标程序的效率，通常只程序的效率，通常只对中中间代代码进行行优化。通常化。通常包括控制流分析、数据流分析和包括控制流分析、数据流分析和变换三部分。三部分。n以程序的基本以程序的基本块为基基础，基本，基本块内的内的优化叫局部化叫局部优化，跨基本化，跨基本块的的优化化为全局全局优化，循化，循环优化是化是针对循循环进行的行的优化，是全局化，是全局优化的一部分。化的一部分。n公共子表达式的公共子表达式的删除、复制除、复制传播、无用代播、无用代码删除、除、代代码外提、外提、强度削弱和度削弱和归纳变量量删除等都是一些除等都是一些常用的常用的针对局部或者全局的代局部或者全局的代

83、码优化方法。化方法。2024/8/398本章小结本章小结n划分基本划分基本块、构造并分析表示程序控制流信息、构造并分析表示程序控制流信息的流的流图是是进行控制流分析的基行控制流分析的基础工作。在工作。在对循循环的分析中，用到支配的分析中，用到支配节点、回点、回边、自然循、自然循环、前置首前置首节点、流点、流图的可的可约等重要概念。等重要概念。n对程序中程序中变量的定量的定义和引用关系的分析称和引用关系的分析称为数数据流分析，用数据流方程表达据流分析，用数据流方程表达变量的定量的定义、引、引用等，具体用等，具体进行到达行到达-定定义分析、定分析、定义-引用分引用分析、可用表达式分析。析、可用表达式分析。