十章节代码优化ppt课件

1、第十章第十章 代码优化代码优化优化的概念优化的概念n编译时辰为改良目的程序的质量而进展的各项任编译时辰为改良目的程序的质量而进展的各项任务。务。n空间效率空间效率n时间效率时间效率n空间效率和时间效率有时是一对矛盾，有时不能空间效率和时间效率有时是一对矛盾，有时不能兼顾。兼顾。n优化的要求：优化的要求：n必需是等价变换必需是等价变换(坚持功能坚持功能)n为优化的努力必需是值得的。为优化的努力必需是值得的。n有时优化后的代码的效率反而会下降。有时优化后的代码的效率反而会下降。优化的分类优化的分类n机器相关性机器相关性n机器相关优化：存放器优化，多处置器优化，特机器相关优化：存放器优化，多处置器优

2、化，特殊指令优化，无用指令消除等。殊指令优化，无用指令消除等。n机器无关优化：机器无关优化：n优化范围优化范围n部分优化：单个根本块范围内的优化，常量合并部分优化：单个根本块范围内的优化，常量合并优化，公共子表达式删除，计算强度减弱和无用优化，公共子表达式删除，计算强度减弱和无用代码删除。代码删除。n全局优化：主要是基于循环的优化：循环不变优全局优化：主要是基于循环的优化：循环不变优化，归纳变量删除，计算强度削减。化，归纳变量删除，计算强度削减。n优化言语级优化言语级n优化言语级：针对中间代码，针对机器言语。优化言语级：针对中间代码，针对机器言语。代码优化程序的构造代码优化程序的构造n控制流分

3、析的主要目的是分析出程序的循环构造。循环控制流分析的主要目的是分析出程序的循环构造。循环构造中的代码的效率是整个程序的效率的关键。构造中的代码的效率是整个程序的效率的关键。n数据流分析进展数据流信息的搜集，主要是变量的值的数据流分析进展数据流信息的搜集，主要是变量的值的获得和运用情况的数据流信息。获得和运用情况的数据流信息。n到达到达- -定义分析；活泼变量分析；可用表达式分析；定义分析；活泼变量分析；可用表达式分析；n代码变换：根据上面的分析，对内部中间代码进展等价代码变换：根据上面的分析，对内部中间代码进展等价变换。变换。控制流分析控制流分析数据流分析数据流分析代码变换代码变换根本块和流图

4、根本块和流图n根本块中，控制流是由第一个四元式进入，根本块中，控制流是由第一个四元式进入，到达最后一个四元式分开。到达最后一个四元式分开。n流图：把一个程序的中间表示中一切的根流图：把一个程序的中间表示中一切的根本块作为节点集合。有边从节点本块作为节点集合。有边从节点n n到节点到节点n n当且仅当控制流能够从当且仅当控制流能够从n n的最后的一个四的最后的一个四元式到达元式到达n n的第一个四元式。的第一个四元式。n首节点：该根本块的第一个四元式是程序首节点：该根本块的第一个四元式是程序的第一个四元式。的第一个四元式。流图的构造流图的构造n以一切的根本块为节点集合。以一切的根本块为节点集合。

5、n有有B1B1到到B2B2的边的边(B2(B2是是B1B1的后继的后继) )当且仅当：当且仅当：nB1B1的最后一个四元式有条件或无条件地转的最后一个四元式有条件或无条件地转移到移到B2B2的第一个四元式。的第一个四元式。nB2B2是紧紧跟随在是紧紧跟随在B1B1后面的四元式，且后面的四元式，且B1B1的的最后四元式不是无条件转向语句。最后四元式不是无条件转向语句。流图的例子流图的例子本节所用的例子本节所用的例子i = m 1; j = n; v = an;(1) i := m 1while (1) (2) j := n do i = i +1; while(aiv);(4) v := at1

6、 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)流图的例子流图的例子本节所用的例子本节所用的例子i = m 1; j = n; v = an;(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; a

7、j=x;(14) t6:=4 * i (15 ) x := at6x=ai; ai=an; an=x; . . .流图的例子流图的例子i := m 1j := nt1 := 4 * nv := at1i := i + 1t2 := 4 * it3 := at2if t3 v goto B2B1B2j := j 1t4 := 4 * jt5 := at4if t5 v goto B3if i = j goto B6B4B3B5B6根本块的优化根本块的优化n公共子表达式删除公共子表达式删除n复制传播复制传播n常量合并常量合并n无用代码删除无用代码删除n强度减弱强度减弱公共子表达式删除公共子表达式删

8、除部分公共子表达式部分公共子表达式B5 x=ai; ai=aj; aj=x;t6 := 4 * ix := at6t7 := 4 * i t8 := 4 * jt9 := at8at7 := t9t10 := 4 * jat10 := xgoto B2公共子表达式删除公共子表达式删除部分公共子表达式部分公共子表达式B5 x=ai; ai=aj; aj=x;t6 := 4 * ix := at6t7 := 4 * i t8 := 4 * jt9 := at8at7 := t9t10 := 4 * jat10 := xgoto B2公共子表达式删除公共子表达式删除部分公共子表达式部分公共子表达式B

9、5 x=ai; ai=aj; aj=x;t6 := 4 * ix := at6t7 := 4 * i t8 := 4 * jt9 := at8at7 := t9t10 := 4 * jat10 := xgoto B2t6 := 4 * ix := at6t8 := 4 * jt9 := at8at6 := t9at8 := xgoto B2公共子表达式删除公共子表达式删除全局公共子表达式全局公共子表达式B5 x=ai; ai=aj; aj=x;t6 := 4 * ix := at6t7 := 4 * i t8 := 4 * jt9 := at8at7 := t9t10 := 4 * jat10

10、 := xgoto B2t6 := 4 * ix := at6t8 := 4 * jt9 := at8at6 := t9at8 := xgoto B2公共子表达式删除公共子表达式删除全局公共子表达式全局公共子表达式B5 x=ai; ai=aj; aj=x;t6 := 4 * ix := at6t7 := 4 * i t8 := 4 * jt9 := at8at7 := t9t10 := 4 * jat10 := xgoto B2t6 := 4 * ix := at6t8 := 4 * jt9 := at8at6 := t9at8 := xgoto B2x := at2t9 := at4at2

11、:= t9at4 := xgoto B2公共子表达式删除公共子表达式删除B5 x=ai; ai=aj; aj=x;t6 := 4 * ix := at6t7 := 4 * i t8 := 4 * jt9 := at8at7 := t9t10 := 4 * jat10 := xgoto B2t6 := 4 * ix := at6t8 := 4 * jt9 := at8at6 := t9at8 := xgoto B2x := at2t9 := at4at2 := t9at4 := xgoto B2公共子表达式删除公共子表达式删除B5 x=ai; ai=aj; aj=x;t6 := 4 * ix :

12、= at6t7 := 4 * i t8 := 4 * jt9 := at8at7 := t9t10 := 4 * jat10 := xgoto B2t6 := 4 * ix := at6t8 := 4 * jt9 := at8at6 := t9at8 := xgoto B2x := at2t9 := at4at2 := t9at4 := xgoto B2x := t3at2 := t5at4 := xgoto B2公共子表达式删除公共子表达式删除B6 x = ai; ai = an; an = x;t11 := 4 * ix := at11t12 := 4 * i t13 := 4 * nt1

13、4 := at13at12 := t14t15 := 4 * n at15 := x x := t3t14 := at1at2 := t14at1 := x 公共子表达式删除公共子表达式删除B6 x = ai; ai = an; an = x;at1能否作为公共子表达式？能否作为公共子表达式？t11 := 4 * ix := at11t12 := 4 * i t13 := 4 * nt14 := at13at12 := t14t15 := 4 * n at15 := x x := t3t14 := at1at2 := t14at1 := x 公共子表达式删除公共子表达式删除i := m 1j

14、:= nt1 := 4 * nv := at1i := i + 1t2 := 4 * it3 := at2if t3 v goto B2B1B2j := j 1t4 := 4 * jt5 := at4if t5 v goto B3if i = j goto B6B4B3B5B6把把at1at1作为作为公共子表达式公共子表达式是不稳妥的：是不稳妥的：控制分开控制分开B1B1进进入入B6B6之前能够之前能够进入进入B5B5，而，而B5B5有对有对a a的赋值的赋值 复制传播复制传播 形如形如f := g的赋值语句叫做复制语句的赋值语句叫做复制语句优化过程中会大量引入复制优化过程中会大量引入复制t

15、:= d + ea := t 删除部分公共子表达式期间引进复制删除部分公共子表达式期间引进复制t := d + eb := tc := tc := d + eb := d + ea := d + e复制传播复制传播 形如形如f := g的赋值语句叫做复制语句的赋值语句叫做复制语句优化过程中会大量引入复制优化过程中会大量引入复制复制传播变换的思想是在复制语句复制传播变换的思想是在复制语句f := g之后之后尽能够用尽能够用g替代替代fx := t3at2 := t5at4 := t3goto B2x := t3at2 := t5at4 := xgoto B2复制传播复制传播 形如形如f := g

16、的赋值语句叫做复制语句的赋值语句叫做复制语句优化过程中会大量引入复制优化过程中会大量引入复制复制传播变换的思想是在复制语句复制传播变换的思想是在复制语句f := g之后之后尽能够用尽能够用g替代替代f复制传播变换本身并不是优化，但它给其它优复制传播变换本身并不是优化，但它给其它优化带来时机化带来时机常量合并常量合并无用代码删除无用代码删除常量合并常量合并n例子：例子：l = 2l = 2* *3.143.14* *r rn* *2 23.143.14 t1t1n* *t1t1r rt2t2n= =t2t2l ln2 2* *3.143.14的值在编译时辰就可以确定。的值在编译时辰就可以确定。n

17、* *6.286.28 r rt2t2n= =t2t2l l无用代码删除无用代码删除 无用代码是指计算结果以后不被援用的语句无用代码是指计算结果以后不被援用的语句一些优化变换能够会引入无用代码一些优化变换能够会引入无用代码例：例：debug := true; debug := false;. . . 测试后改成测试后改成 . . .if(debug)print if(debug)print 无用代码删除无用代码删除 无用代码是指计算结果以后不被援用的语句无用代码是指计算结果以后不被援用的语句一些优化变换能够会引入无用代码一些优化变换能够会引入无用代码例：复制传播能够会引入无用代码例：复制传播能

18、够会引入无用代码x := t3at2 := t5at4 := t3goto B2at2 := t5at4 := t3goto B2强度减弱强度减弱n实现同样的运算可以有多种方式。用计算实现同样的运算可以有多种方式。用计算较快的运算替代较慢的运算。较快的运算替代较慢的运算。nX2X2变成变成x x* *x x。n2 2* *x x或或2.02.0* *x x变成变成x+xx+xnx/2x/2变成变成x x* *0.50.5nanxn+an-1xn-1+a1x+a0anxn+an-1xn-1+a1x+a0变成变成n(anx+an-1)x+ an-2)x+a1)x+a0(anx+an-1)x+ an

19、-2)x+a1)x+a0根本块优化的实现根本块优化的实现n根本块内部优化的实现的主要工具为根本块内部优化的实现的主要工具为DAGDAG图。图。n用用DAGDAG图表示各个值的计算图表示各个值的计算/ /依赖关系。依赖关系。n图中的标志：图中的标志：n叶节点用标识符变量名或常数作为独一的叶节点用标识符变量名或常数作为独一的标志。叶节点是标识符时，用下标标志。叶节点是标识符时，用下标0 0表示它是表示它是初值。初值。n内部节点用运算符作为标志，表示计算的值。内部节点用运算符作为标志，表示计算的值。每个节点的值都可以用关于变量初始值的表达每个节点的值都可以用关于变量初始值的表达式表示。式表示。n各节

20、点能够附加有一个或者多个标识符。同一各节点能够附加有一个或者多个标识符。同一个节点的标识符表示一样的值。个节点的标识符表示一样的值。DAGDAG图的例子图的例子n+ bcan-adbn+ bccn-add+-+b0c0d0b,dac四元式的分类四元式的分类n0 0型：型：= =x x_ _y yn1 1型：型：opopx x_ _y(y(单目运算单目运算n2 2型：型：opopx xy yz znreloprelopx xy yz(zz(z是是序号序号) )根本块根本块DAGDAG图构造算法图构造算法n输入：一个根本块输入：一个根本块输出：相应输出：相应DAGDAG图图n算法阐明：算法阐明：n

21、经过逐个扫描四元式来逐渐建立经过逐个扫描四元式来逐渐建立DAGDAG图。图。n函数函数node(x)node(x)表示和标识符表示和标识符x x相应的最近建立的节点。他代表扫描相应的最近建立的节点。他代表扫描到当前的四元式的时候，标识符到当前的四元式的时候，标识符x x的值对应的节点。的值对应的节点。n步骤步骤1 1：初始化：无任何节点，：初始化：无任何节点，nodenode对任何标识符无定义。对任何标识符无定义。n步骤步骤2 2：依次对根本块中的每个四元式：依次对根本块中的每个四元式op x y zop x y z执行如下步骤。执行如下步骤。n假设假设node(x)node(x)没有定义，建

22、立叶子节点，标志为没有定义，建立叶子节点，标志为x x，让，让node(x) node(x) 等等于这个节点。假设于这个节点。假设node(y)node(y)没有定义，为没有定义，为y y建立节点。建立节点。n假设四元式为假设四元式为0 0型，型，n=node(x);n=node(x);n假设四元式为假设四元式为1 1型，寻觅标志为型，寻觅标志为opop且子节点为且子节点为node(x)node(x)的节点，假的节点，假设找不到，建立这样的节点。设找不到，建立这样的节点。根本块根本块DAGDAG图构造算法续图构造算法续n对于对于2 2型四元式，查看能否存在标志为型四元式，查看能否存在标志为op

23、op的节点，且其左右的节点，且其左右子节点分别为子节点分别为node(x)node(x)和和node(y)node(y)。假设找不到，建立这样。假设找不到，建立这样的节点。的节点。n步骤步骤3 3：假设：假设z z为标识符，从为标识符，从node(z)node(z)中删除标识符中删除标识符z z，并把，并把z z参与到步骤参与到步骤4 4所找到或者建立的节点所找到或者建立的节点n n的标识符表中，并设的标识符表中，并设置置node(z)node(z)为为n n。n阐明：阐明：n处置处置2 2型四元式的时候，假设型四元式的时候，假设opop是可交换的运算符，可以允是可交换的运算符，可以允许其左右

24、节点可以互换。许其左右节点可以互换。生成生成DAGDAG图的例子图的例子n*4it1=at1t2n*4it3=bt3t4n*t2t4t5+prodt5t6n=t6prod+i1t7n=t7i=i20(3)a4i*=b*+prod01+20=DAGDAG图的运用图的运用n公共子表达式：构造中，寻觅能否有标志为公共子表达式：构造中，寻觅能否有标志为opop且子节点为且子节点为node(x), node(y)node(x), node(y)的节点时，自然的节点时，自然完成了公共子表达式的寻觅。完成了公共子表达式的寻觅。n在根本块中，其值被援用的标识符：构造了叶在根本块中，其值被援用的标识符：构造了叶

25、节点的标识符。节点的标识符。n结果可以在根本块外被援用的四元式结果可以在根本块外被援用的四元式op x y zop x y z：设它对应的节点为设它对应的节点为n n，假设，假设DAGDAG图构造终了的时图构造终了的时候，候，n n的标志符表不为空。的标志符表不为空。=和和&=&=运算符的处置运算符的处置n对数组的赋值需求特别的处置，这是由于数组的下标是变量。对数组的赋值需求特别的处置，这是由于数组的下标是变量。对于数组元素的赋值能够改动数组中任何一个元素的值。对于数组元素的赋值能够改动数组中任何一个元素的值。n= A Ai it1t1 =A Aj jt2t2n&=&a

26、mp;=y yt2t2t2t2=A Ai it3t3nAiAi并不是公共子表达式。并不是公共子表达式。n在处置对数组在处置对数组A A的元素的赋值四元式的时候，应该注销一切以的元素的赋值四元式的时候，应该注销一切以=为标志，为标志，A A为左节点的节点。从而不能够在此节点的标识为左节点的节点。从而不能够在此节点的标识符表中再附上其他的标识符。符表中再附上其他的标识符。n处置对指针所指空间的赋值的时候，同样要注销相应的节点。处置对指针所指空间的赋值的时候，同样要注销相应的节点。假设不能确定指针指向的范围，那么，需求注销一切的节点。假设不能确定指针指向的范围，那么，需求注销一切的节点。Ai=j=t

27、1t2y&=从从DAGDAG图到四元式序列图到四元式序列n在在DAGDAG图中，有些运算曾经进展了合并。图中，有些运算曾经进展了合并。n假设不思索假设不思索=和和&=&=算符，可以按照算符，可以按照DAGDAG图中图中的拓扑排序得到的次序进展。但是，有了的拓扑排序得到的次序进展。但是，有了=和和&=&=算符之后，计算的次序必需修正。算符之后，计算的次序必需修正。n实践上，我们可以按照各个节点生成的顺序实践上，我们可以按照各个节点生成的顺序来从来从DAGDAG图生成四元式序列。图生成四元式序列。从从DAGDAG重建四元式序列算法重建四元式序列算法n按照按照

28、DAGDAG图中各个节点的生成次序对每个节点作如下处置：图中各个节点的生成次序对每个节点作如下处置：n假设是叶子节点，且附加标识符表为空，不生成四元式。假设是叶子节点，且附加标识符表为空，不生成四元式。n假设是叶子节点，标志为假设是叶子节点，标志为x x，附加标识符为，附加标识符为z z，生成，生成= = x z x z。n假设是内部节点，附加标识符为假设是内部节点，附加标识符为z z，根据其标志，根据其标志opop和子节点数和子节点数目，生成以下目，生成以下4 4种方式的四元式。种方式的四元式。nopop不是不是=或或=，也不是，也不是reloprelop，有两个子节点，生成，有两个子节点，

29、生成opopx xy yz zn假设是假设是=或或=，生成，生成opop x xy yz z。n假设是假设是reloprelop，生成，生成relop xrelop xy yz z，z z是根本块序号。是根本块序号。n只需一个子节点，生成只需一个子节点，生成opop x x_ _z z。从从DAGDAG重建四元式序列算法重建四元式序列算法( (续续) )n假设是内部节点，且无附加标识符，那么添加一个部分于本假设是内部节点，且无附加标识符，那么添加一个部分于本根本块的暂时性附加标识符，按照上一情况生成。根本块的暂时性附加标识符，按照上一情况生成。n假设节点的标识符重包含多个附加标识符假设节点的标

30、识符重包含多个附加标识符z1,z2,zkz1,z2,zk时：时：n假设是叶子节点，标志为假设是叶子节点，标志为z z，生成一系列四元式，生成一系列四元式n= =z zz1z1n= =z zz2z2nn= =z zznznn不是叶子节点，生成四元式序列：不是叶子节点，生成四元式序列：n= =z zz2z2nn= =z zznzn运用运用DAGDAG图进展优化的例子图进展优化的例子( (四元式序列四元式序列) )n四元式序列片断四元式序列片断: :n* *4 4i it10t10=A At10t10t11t11n= =t11t11x x* *4 4i it12t12n=A At12t12t13t1

31、3* *4 4j jt14t14n=A At14t14t15t15&=&=t15t15t13t13t13t13n* *4 4j jt16t16=A At16t16t17t17n&=&= x xt17t17t17t17 i ij jB2B2运用运用DAGDAG图进展优化的例子图进展优化的例子(DAG(DAG图图) )n在第在第1010个节点生成后个节点生成后, , node(t11)node(t11)变成无定义变成无定义. .1: 42: i3: * t104: At125:=t116:= t138:*7: jt149: = t1510:&=t1611:=

32、 t1712: &=13: B2x从从DAGDAG图到四元式序列图到四元式序列n*4it10(3)n=At10t11(5)n:=t11x(5)n=At10t13(6)n*4jt14(8)n=At14t15(9)n&=t15t13t13(10)n=At14t17(11)n&=xt17t17(12)nijB2(13)DAGDAG的其他运用的其他运用n常量合并常量合并: :n* *2 2pipit1t1n* *t1t1r rt2t2n= =t2t2l ln无用代码删除无用代码删除: :n对于对于= =t10t10t12t12，假设，假设t12t12不需求运用，不需求运用，那么

33、，这个四元式不需求生成。那么，这个四元式不需求生成。*2pir0与循环有关的优化与循环有关的优化n循环不变表达式外提代码外提循环不变表达式外提代码外提n归纳变量删除归纳变量删除n计算强度减弱计算强度减弱循环不变式外提代码外提循环不变式外提代码外提n有些表达式位于循环之内，但是该表达有些表达式位于循环之内，但是该表达式的值不随着循环的反复执行而改动，式的值不随着循环的反复执行而改动，该表达式被称为循环的不变表达式。该表达式被称为循环的不变表达式。n假设按照前面讲的代码生成方案，每一假设按照前面讲的代码生成方案，每一次循环都讲计算一次。次循环都讲计算一次。n假设把这个表达式提取到循环外面，该假设把

34、这个表达式提取到循环外面，该计算就只被执行一次。从而可以获得更计算就只被执行一次。从而可以获得更加好的效率。加好的效率。循环不变式的例子循环不变式的例子n计算半径为计算半径为r r的从的从1010度到度到360360度的扇形的面积：度的扇形的面积：nfor(n=1; n36; n+)for(n=1; n36; n+)nS:=10/360S:=10/360* *pipi* *r r* *r r* *n; printf(n; printf(“Area is %fArea is %f, S); , S); n显然，表达式显然，表达式10/36010/360* *pipi* *r r* *r r中的各

35、个量在循环过程中不改中的各个量在循环过程中不改动。可以修正程序如下：动。可以修正程序如下：nC= 10/360C= 10/360* *pipi* *r r* *r r* *n; n; nfor(n=1; n36; n+)for(n=1; n (2)n n3636(21)(21)n(3)GO(3)GO(4)(4) (4)/ (4)/1010360360tltln(5)(5)* * tl tlpipit2t2(6)(6)* *t2t2r rt3t3n(7)(7)* * t3 t3r rt4t4(8)(8)* *t4t4n nt5t5n(9)=(9)= t5 t5S Sn(18)+ n(18)+ n

36、1 1t9t9(19)=(19)=t9t9n nn(20)GO(20)GO(4)(4)(21)(21)n其中，四元式其中，四元式4,5,6,74,5,6,7是循环不变四元式。是循环不变四元式。循环不变四元式的相对性循环不变四元式的相对性n对于多重嵌套的循环，循环不变四元式是相对于某个对于多重嵌套的循环，循环不变四元式是相对于某个循环而言的。能够对于更加外层的循环，它就不是循循环而言的。能够对于更加外层的循环，它就不是循环不变式。环不变式。n例子：例子：nfor(i = 1; i10; i+)for(i = 1; i10; i+)nfor(n=1; n360/(5for(n=1; n360/(5

37、* *i); n+)i); n+)nS:=(5S:=(5* *i)/360i)/360* *pipi* *r r* *r r* *n;.n;.n5 5* *i i和和(5(5* *i)/360i)/360* *pipi* *r r* *r r对于对于n n的循环内层循环是的循环内层循环是不变表达式，但是对于外层循环，它们不是循环不变不变表达式，但是对于外层循环，它们不是循环不变表达式。表达式。循环不变表达式优化需求循环不变表达式优化需求处理的问题处理的问题n如何识别循环中的不变表达式？如何识别循环中的不变表达式？n把循环表达式外提到什么地方？把循环表达式外提到什么地方？n什么条件下，不变表达式

38、可以外提？什么条件下，不变表达式可以外提？归纳变量的删除例子归纳变量的删除例子n例子：例子：nprod=0; i = 1;prod=0; i = 1;nfor(i = 1; i= 20; i+)for(i = 1; i= 20; i+)nprod = prod+Aiprod = prod+Ai* *Bi;Bi;ni i作为计数器。每次反复，作为计数器。每次反复，i i的值添加的值添加1 1，而，而Ai, Ai, BiBi对应的地址对应的地址t1, t3t1, t3添加添加4 4假定每个数组元假定每个数组元素占素占4 4个字节。个字节。n我们可以删除我们可以删除i i，而运用，而运用t1t1或者

39、或者t3t3进展循环终了进展循环终了条件的测试。条件的测试。归纳变量的删除归纳变量的删除n在循环中，假设变量在循环中，假设变量i i的值随着循环的每的值随着循环的每次反复都固定地添加或者减少某个常量，次反复都固定地添加或者减少某个常量，那么称那么称i i为循环的归纳变量。为循环的归纳变量。n假设在一个循环中有多个归纳变量，归假设在一个循环中有多个归纳变量，归纳变量的个数往往可以减少，甚至减少纳变量的个数往往可以减少，甚至减少到到1 1个。减少归纳变量的优化称为归纳变个。减少归纳变量的优化称为归纳变量的删除。量的删除。归纳变量的删除四元式例子归纳变量的删除四元式例子=0prod=li*4it1=

40、at1t2*4it3=bt3t4*t2t4t5+prodt5t6=t6prod+i1t7=t7i=i20B2=0prod=0t1+4t1t1+4t3t3=at1t2=bt3t4*t2t4t5+prodt5t6=t6prod=t180B2归纳变量的删除归纳变量的删除n归纳变量删除一方面可以删除变量，减归纳变量删除一方面可以删除变量，减少四元式，另外，删除归纳变量同时也少四元式，另外，删除归纳变量同时也削减了计算强度。削减了计算强度。n为了进展归纳变量删除优化，必要的是为了进展归纳变量删除优化，必要的是找出归纳变量。找出归纳变量。计算强度减弱计算强度减弱n在删除归纳变量的过程中在删除归纳变量的过程

41、中, ,曾经将一些乘曾经将一些乘法运算转换成为加法运算。法运算转换成为加法运算。n还有一类经常可以被运用的是对于下标还有一类经常可以被运用的是对于下标变量地址的计算。变量地址的计算。计算强度削减下标变量计算强度削减下标变量n对于数组对于数组T Tan1n2nman1n2nm，其下标变量，其下标变量ai1i2i3imai1i2i3im的地址计算如下：的地址计算如下：nbase+dbase+d；其中；其中basebase为为a000a000的地址。的地址。nd=(i1d=(i1* *n2+i2)n2+i2)* *n3+i3)n3+i3)* *nm+im)nm+im)* *sizeofsizeof(

42、T);(T);n当满足某些情况的时候，地址的计算可以运用当满足某些情况的时候，地址的计算可以运用加法来替代乘法。加法来替代乘法。下标变量计算强度的削减例子下标变量计算强度的削减例子nfor(v1=v10; v1v1f; v1+)for(v1=v10; v1v1f; v1+)nfor(v2=v20; v2v2f; v2+)for(v2=v20; v2v2f; v2+)n Ai1i2i3 Ai1i2i3ni1, i2, i3i1, i2, i3都可以表示成为：都可以表示成为：Ck0+Ck1Ck0+Ck1* *V1+Ck2V1+Ck2* *V2(k=1,2,3);V2(k=1,2,3);nAi1i2

43、i3Ai1i2i3的地址为的地址为base+d; base+d; d=(i1d=(i1* *n2n2* *n3+i2n3+i2* *n3+i3);n3+i3);n将将i1,i2,i3i1,i2,i3的表达式代入的表达式代入d d的表达式，可以得到的表达式，可以得到d=C0+C1d=C0+C1* *V1+C2V1+C2* *V2.V2.下标变量计算强度的削减例子下标变量计算强度的削减例子n显然，在上面的例子中，每次内循环显然，在上面的例子中，每次内循环d d的值添加的值添加C2C2；每次外循环每次外循环, d, d的值添加的值添加C1C1但是但是V2V2被重置。被重置。n显然我们可以这样计算显然

44、我们可以这样计算Ai1i2i3Ai1i2i3的地址：的地址：n在循环开场的时候，设置初值在循环开场的时候，设置初值d1=(base+C0d1=(base+C0)+C1)+C1* *V10;V10;n在进入外层循环后，进入内存循环前，设置在进入外层循环后，进入内存循环前，设置d2=d1+C2d2=d1+C2* *V20V20n在内存循环，运用在内存循环，运用d2d2作为地址获取作为地址获取Ai1i2i3Ai1i2i3的值。的值。n内存循环体每次运转终了之前，将内存循环体每次运转终了之前，将d2d2的值添加的值添加C2C2。n每次外层循环体运转终了之前，将每次外层循环体运转终了之前，将d1d1的值

45、添加的值添加C1C1。n显然，对于显然，对于Ai1i2i3Ai1i2i3的地址计算变成了加法运算。的地址计算变成了加法运算。下标变量计算强度的削减结果下标变量计算强度的削减结果D1 = base+C0+C1*V10;for(v1=v10; v1v1f; v1+)D2 = D1+C2*V20;for(v2=v20; v2MN-M，那么这条边称为回边。，那么这条边称为回边。n定义定义10.3 10.3 在流图中，给定一个回边在流图中，给定一个回边N-MN-M，与这个回边对应的自然循环为：与这个回边对应的自然循环为：M M，以及一，以及一切可以不经过切可以不经过M M而到达而到达N N的节点。的节点

46、。M M为该循环为该循环的首节点。的首节点。n用节点的集合表示自然循环。用节点的集合表示自然循环。自然循环的例子自然循环的例子n3 dom 43 dom 4n回边回边4-34-3n4 dom 74 dom 7n回边回边7-47-4n10-710-7的自然循环的自然循环77，8 8，1010n7-47-4的自然循环的自然循环4,5,6,7,8,104,5,6,7,8,10n4-34-3，8-38-3的自的自然循环然循环3,4,5,6,7,8,103,4,5,6,7,8,1012345678910回边寻觅算法回边寻觅算法n首先列出一切从首节点开场，不带圈的首先列出一切从首节点开场，不带圈的途径。途

47、径。n节点节点N N的支配节点集是满足以下条件的节的支配节点集是满足以下条件的节点点M M：n一切包含一切包含N N的途径的途径P, MP, M都在都在N N的前面出现。的前面出现。n回边集合如下：回边集合如下：nN-M | NN-M | N是一个节点，是一个节点，M M在在N N的支配节的支配节点集中点集中 寻觅自然循环的算法寻觅自然循环的算法n输入输入: :回边回边N-M; N-M; 输出输出: : 回边对应的自然循环回边对应的自然循环. .n算法算法: :n设置设置loop=N,M;loop=N,M;npush(stack, N);push(stack, N);nwhile non-em

48、pty(stack) dowhile non-empty(stack) donm = top(stack); pop(stack);m = top(stack); pop(stack);nfor mfor m的每个前驱节点的每个前驱节点p p nif p is_not_in loop then if p is_not_in loop then nloop += p; push(stack,p);loop += p; push(stack,p);n 算法的阐明算法的阐明n节点节点M M在初始时辰曾经在在初始时辰曾经在looploop中，所以中，所以, M, M的的前驱不能够被参与到前驱不能够被参

49、与到looploop中。中。n假设假设N-MN-M不是回边，那么，首节点会被参与不是回边，那么，首节点会被参与到到looploop中。此时算法不能得到自然循环。中。此时算法不能得到自然循环。相关概念相关概念n通常，循环互不相交，或者一个在另外一个里面。通常，循环互不相交，或者一个在另外一个里面。n内循环：不包含其他循环的循环称为内循环。内循环：不包含其他循环的循环称为内循环。n假设两个循环具有一样的首节点，那么很难说一个假设两个循环具有一样的首节点，那么很难说一个包含另外一个。此时把两个循环合并。包含另外一个。此时把两个循环合并。B0B1B2B3可归约流图可归约流图n可归约流图：删除了其中回边

50、之后，可归约流图：删除了其中回边之后，可以构成无环有向图的流图。可以构成无环有向图的流图。n特性：不存在循环外向循环内部的特性：不存在循环外向循环内部的转移，进入循环必需经过其首节点。转移，进入循环必需经过其首节点。n实践的程序对应的流图普通都是可实践的程序对应的流图普通都是可归约的流图。归约的流图。n没有没有gotogoto语句的构造化程序的流图语句的构造化程序的流图总是可归约的。普通运用总是可归约的。普通运用gotogoto语句语句的程序也是可归约的。的程序也是可归约的。B1B2B3数据流分析相关概念数据流分析相关概念n变量获得值的方式：变量获得值的方式：n经过赋值语句；经过赋值语句；n经

51、过输入语句；经过输入语句；n经过过程方式参数；经过过程方式参数；n点：流图根本块中的位置，包括：第一个四元式之点：流图根本块中的位置，包括：第一个四元式之前，两个相邻四元式之间，和最后的四元式之后。前，两个相邻四元式之间，和最后的四元式之后。n定义：使变量定义：使变量x x获得值的四元式称为获得值的四元式称为x x的定义，普通的定义，普通用四元式的位置表示。用四元式的位置表示。n援用点：援用某个变量援用点：援用某个变量x x的四元式的位置称为的四元式的位置称为x x的援的援用点。用点。数据流分析的种类数据流分析的种类n到达到达- -定义数据流方程定义数据流方程n活泼变量数据流方程活泼变量数据流

52、方程n可用表达式数据流方程可用表达式数据流方程到达到达- -定义数据流方程定义数据流方程n到达到达- -定义：假定定义：假定x x有定义有定义d d，假设存在一个途径，从，假设存在一个途径，从紧随紧随d d的点到达某点的点到达某点p p，而且在此途径上面没有被注销，而且在此途径上面没有被注销，那么称那么称x x的定义的定义d d到达到达p p。这阐明，在。这阐明，在p p点运用变量点运用变量x x的的时候，时候，x x的值能够是由的值能够是由d d点赋予的。点赋予的。n到达到达- -定义链：设变量定义链：设变量x x有一个援用点有一个援用点u u，变量，变量x x的一切的一切能过到达能过到达u

53、 u的一切定义称为的一切定义称为x x在在u u点处的援用点处的援用- -定义链，定义链，简称简称udud链。链。n显然，经过变量显然，经过变量x x在援用点在援用点u u的的udud链，可以判别链，可以判别x x能否能否循环不变的。循环不变的。到达定义数据流方程记号到达定义数据流方程记号nINB: INB: 表示根本块表示根本块B B的入口点处各个变量的定义集合。的入口点处各个变量的定义集合。n假设假设B B中点中点p p之前有之前有x x的定义的定义d d，且这个定义可以到达，且这个定义可以到达p p，那，那么点么点p p处处x x的的udud链是链是dd。n否那么，点否那么，点p p处处

54、x x的的udud链就是链就是IBBIBB中中x x的定义集合。的定义集合。nPBPB：B B的一切前驱根本块的集合。的一切前驱根本块的集合。nGENBGENB：各个变量在：各个变量在B B内定义，并可以到达内定义，并可以到达B B的出口点的一的出口点的一切定义的集合。切定义的集合。nOUTBOUTB：各个变量的可以到达根本块：各个变量的可以到达根本块B B的出口点的一切定的出口点的一切定义的集合。义的集合。nKILLBKILLB：是各个变量在根本块：是各个变量在根本块B B中重新定义，即在此块内中重新定义，即在此块内部被注销的定义点的集合。部被注销的定义点的集合。到达定义数据流方程到达定义数

55、据流方程nINB = OUTp where p is in PBINB = OUTp where p is in PBnOUTB = GENB U (INB-KILLB)OUTB = GENB U (INB-KILLB)n其中：其中：nGENBGENB可以从根本块中求出：运用可以从根本块中求出：运用DAGDAG图就可图就可以得到。以得到。nKILLBKILLB中，对于整个流图中的一切中，对于整个流图中的一切x x的定义点，的定义点，假设假设B B中有对中有对x x的定义，那么该定义点在的定义，那么该定义点在KILLBKILLB中。中。方程求解算法方程求解算法n运用迭代方法。运用迭代方法。n初始

56、值设置为：初始值设置为：INBi=INBi=空；空；OUTB=GENBi;OUTB=GENBi;nchange = TRUE;change = TRUE;nwhile(change)while(change)n nchange = FALSE;change = FALSE;nfor each B dofor each B donINB = OUTp where p is in PB;INB = OUTp where p is in PB;n OUTB = GENB (INB-KILLB); OUTB = GENB (INB-KILLB);n oldout = OUTB; oldout = OU

57、TB;n if(OUTB != oldout) change = TRUE; if(OUTB != oldout) change = TRUE;n 算法例子算法例子nGENB1=d1,d2,d3nKILLB1=d4,d5,d6,d7nGENB2=d4,d5nKILLB2=d1,d2,d7nGENB3=d6nKILLB3=d3nGENB4=d7nKILLB4=d1,d4d1: -m1id2: =njd3: =u2ad4: +i1id5: -j1jd6: =u2ad7: =u3iB1B2B3B4计算过程计算过程n初始化：初始化：nINB1 = INB2 = INB3 = INB4 =INB1 =

58、INB2 = INB3 = INB4 =空空nOUTB1=d1,d2,d3, OUTB2=d4,d5OUTB1=d1,d2,d3, OUTB2=d4,d5nOUTB3=d6, OUTB4=d7.OUTB3=d6, OUTB4=d7.n第一次循环：第一次循环：nINB1=INB1=空空; INB2 =d1,d2,d3,d7; INB3=d4,d5; INB2 =d1,d2,d3,d7; INB3=d4,d5;nINB4=d4,d5,d6; OUTB1=d1,d2,d3;INB4=d4,d5,d6; OUTB1=d1,d2,d3;nOUTB2=d3,d4,d5OUTB2=d3,d4,d5n结果：结

59、果：nINB1=INB1=空；空；OUTB1=d1,d2,d3;OUTB1=d1,d2,d3;nINB2=d1,d2,d3,d5,d6,d7; OUTB2=d3,d4,d5,d6;INB2=d1,d2,d3,d5,d6,d7; OUTB2=d3,d4,d5,d6;nINB3=d3,d4,d5,d6;INB3=d3,d4,d5,d6; OUTB3=d4,d5,d6;OUTB3=d4,d5,d6;nINB4=d3,d4,d5,d6; OUTB4=d3,d5,d6,d7;INB4=d3,d4,d5,d6; OUTB4=d3,d5,d6,d7;活泼变量数据流方程活泼变量数据流方程n判别在根本块出口之后

60、，变量的值能否还被援用的这判别在根本块出口之后，变量的值能否还被援用的这种判别任务称为活泼变量分析。种判别任务称为活泼变量分析。n消除复制四元式的根据就是对活泼变量的分析。假设消除复制四元式的根据就是对活泼变量的分析。假设某个变量的值在以后不被援用，那么该复制四元式可某个变量的值在以后不被援用，那么该复制四元式可以被消除。以被消除。n对于变量对于变量x x和流图上的某个点和流图上的某个点p p，假设在流图中沿着从，假设在流图中沿着从p p开场的某条途径可以援用开场的某条途径可以援用x x在在p p点的值，那么称变量点的值，那么称变量x x在点在点p p是活泼变量，否那么称是活泼变量，否那么称x x在点在点p p不活泼。不活泼。n无用赋值：假设无用赋值：假设x x在点在点p p的定义在一切根本块内都不被的定义在一切根