《编译原理课件：Chapter-11 代 码 优 化》由会员分享，可在线阅读，更多相关《编译原理课件：Chapter-11 代 码 优 化（30页珍藏版）》请在金锄头文库上搜索。
1、第十一章第十一章 代代 码码 优优 化化11.1 概述概述11.2 优化的例子优化的例子11.3 基本块的优化基本块的优化11.4 循环优化循环优化111.1 概述概述 经过前面各章所介绍的各个编译阶段，我们已经可经过前面各章所介绍的各个编译阶段，我们已经可以把源程序变换成目标代码了，但这样生成的目标代码效以把源程序变换成目标代码了，但这样生成的目标代码效率未必是最高的。率未必是最高的。代码优化（代码优化（code optimization)目的：目的：提高目标代码运行效率提高目标代码运行效率 原则：进行优化必须严格遵循原则：进行优化必须严格遵循“不能改变原有程序语义不能改变原有程序语义”原则
2、。原则。 时间效率（减少运行时间）时间效率（减少运行时间）空间效率（减少内存容量）空间效率（减少内存容量）2优化的分类：优化的分类： 从优化的层次，与机器是否有关，分为：从优化的层次，与机器是否有关，分为： 从优化涉及的范围，又分为：从优化涉及的范围，又分为： 独立于机器的优化：独立于机器的优化：即与目标机无关的优化，通常是在中间代码上进即与目标机无关的优化，通常是在中间代码上进 行的优化。行的优化。与机器有关的优化：与机器有关的优化：充分利用系统资源（指令系统，寄存器资源）。充分利用系统资源（指令系统，寄存器资源）。局部优化：局部优化：是指在基本块内进行的优化。是指在基本块内进行的优化。循环
3、优化：循环优化：对循环语句所生成的中间代码序列上所进行的优化。对循环语句所生成的中间代码序列上所进行的优化。全局优化：全局优化：顾名思义，跨越多个基本块的全局范围内的优化。因此它顾名思义，跨越多个基本块的全局范围内的优化。因此它是指在非线性程序段上（包括多个基本块是指在非线性程序段上（包括多个基本块, GOTO, 循环）循环）的优化。需要进行全局控制流和数据流分析，比较复杂。的优化。需要进行全局控制流和数据流分析，比较复杂。3 定义定义 基本块基本块（basic block ) 满足以下三个条件的程序段，称为基本块：满足以下三个条件的程序段，称为基本块：l只有一个入口和一个出口，且语句为顺序执
4、行的程序段。只有一个入口和一个出口，且语句为顺序执行的程序段。l它使得所有转向该基本块的入口都是该基本块的第一条它使得所有转向该基本块的入口都是该基本块的第一条语句。语句。l如果块中任一语句被执行，则该块内的所有语句也将被如果块中任一语句被执行，则该块内的所有语句也将被执行（执行（无分支无分支），且执行次数一样（），且执行次数一样（无循环无循环）。）。4例：书上第例：书上第252页图页图11.1的的FORTRAN语言例子语言例子（先编号，后画图先编号，后画图决定基本块）决定基本块）1.FACTOR = A( I ) + 2.0 * B( I )2.EXP 1 = ABS( FACTOR )3.
5、IF ( KEY.NE.0 ) GO TO 10 4.BASE = 2.05.FACTOR = FACTOR * 26.GO TO 207.10. BASE = 10.08.11. FACTOR = SQRT( FACTOR )9.20. Q = ( BASE * EXP ) * FACTOR10.21. RETURN基本块基本块基本块基本块基本块基本块13456201011212基本块基本块5优化所花费的代价和优化产生的效果可用下图表示：优化所花费的代价和优化产生的效果可用下图表示：优化的代价优化的代价 局部优化局部优化循环优化循环优化 全局优化全局优化优优化化的的效效果果 6l图的左部表示
6、只要做些简单的处理，便能得到明显的优化效果。这相当图的左部表示只要做些简单的处理，便能得到明显的优化效果。这相当于局部优化。于局部优化。l若要进一步提高优化效果，就要逐步付出更大的代价若要进一步提高优化效果，就要逐步付出更大的代价循环优化。循环优化。l全局优化进一步提高。全局优化进一步提高。优化的代价优化的代价 局部优化局部优化循环优化循环优化 全局优化全局优化优优化化的的效效果果 7为什么要优化？为什么要优化？l有的大型计算程序一运行就要花上几十分钟，甚至好几小时。有的大型计算程序一运行就要花上几十分钟，甚至好几小时。这时为优化即使付出些代价也是值得的。这时为优化即使付出些代价也是值得的。l
7、另外，程序中的循环往往要占用大量的计算时间，所以为减少另外，程序中的循环往往要占用大量的计算时间，所以为减少循环执行时间所进行的优化对减少整个程序的运行时间有很大循环执行时间所进行的优化对减少整个程序的运行时间有很大的意义。的意义。 尤其有实时要求的程序，如市场决策，供需及求尤其有实时要求的程序，如市场决策，供需及求益的平衡。益的平衡。l对于像学生作业之类的简单小程序对于像学生作业之类的简单小程序(占机器内存、运行速度均可占机器内存、运行速度均可接受接受)，或在程序的调试阶段，花费许多代价去进行一遍又一遍，或在程序的调试阶段，花费许多代价去进行一遍又一遍的优化就毫无必要。的优化就毫无必要。81
8、1.2 优化的基本方法和例子优化的基本方法和例子 在这一节中，我们将介绍一些有代表性的优化处理方法在这一节中，我们将介绍一些有代表性的优化处理方法和例子。实际的优化应在中间代码或目标代码上进行。但为和例子。实际的优化应在中间代码或目标代码上进行。但为了便于说明，这儿我们用源程序形式举例。了便于说明，这儿我们用源程序形式举例。（1）利用代数性质）利用代数性质(代数变换代数变换)l 编译时完成常量表达式的计算，整数类型与实型的转换。编译时完成常量表达式的计算，整数类型与实型的转换。 例：例： a := 5 + 6 + x a := 11 + x 又如：又如： 设设 x 为实型，为实型，x := 3
9、 + 1 可变换成可变换成x := 4.09l 下标变量引用时，其地址计算的一部分工作可在编译时预下标变量引用时，其地址计算的一部分工作可在编译时预先做好先做好(运行时只需计算运行时只需计算“可变部分可变部分”即可即可)。例如：二维数组定义为：例如：二维数组定义为：Array l1 : u1, l2 : u2 令令di = ui li + 1, i = 1, 2 /每一维的尺寸每一维的尺寸假如数组元素按行存放，则假如数组元素按行存放，则Array i1, i2 的位置为的位置为D = a + ( i1 - l1) d2 + ( i2 l2 ) * m / m为每个元素所占大为每个元素所占大小小
10、 = a ( l1 d2 + l2 ) * m + ( i1 d2 + i2 ) * m = CONSPART + VARPART10如如 x * 2 x * x 3 * x x + x + x 8 * x , 4 * x 等换成左移运算等换成左移运算 x / 2 , x / 16 等换成右移运算等换成右移运算 x := x + 1 变为变为INC x指令指令 x / 5 x * 0.2 等等利用机器硬件所提供的一些功能，如左移、右移操作做利用机器硬件所提供的一些功能，如左移、右移操作做乘法或除法，具有更高的代码效率。乘法或除法，具有更高的代码效率。 l 运算强度削弱：运算强度削弱：用一种需要
11、较少执行时间的运算代替另一用一种需要较少执行时间的运算代替另一种运算，以减少运行时的运算强度种运算，以减少运行时的运算强度(时、空开销时、空开销)。11（2） 复写复写(copy)传播传播如如 x := y 这样的赋值语句称为复写语句。由于这样的赋值语句称为复写语句。由于 x 和和 y 值相同，值相同，所以当满足一定条件时，在该赋值语句下面出现的所以当满足一定条件时，在该赋值语句下面出现的 x 可用可用 y 来来代替。代替。例如：例如： x := y ; x := y ; u := 2 * x ; u := 2 * y ; v := x + 1 ; v := y + 1 ; 这就是所谓的复写传
12、播这就是所谓的复写传播 (copy propagation) 。若以后的语句中不再用到若以后的语句中不再用到 x 时，则上面的时，则上面的 x := y 可删去。可删去。12若上例中不是若上例中不是x := y而是而是 x := 3。则复写传播变成了则复写传播变成了常量传播常量传播。即。即 u := 6; v := 4;又如又如 t1 := y / z; x := t1;若这里若这里 t1为暂时为暂时(中间中间)变量，以后不再使用，则可变换为变量，以后不再使用，则可变换为 x := y / z;此外常量传播，引起常量计算，如：此外常量传播，引起常量计算，如： pi = 3.14159 r =
13、pi / 180.0此时：此时：pi = 3.14159 r = 0.0174532 （常量计算）（常量计算）x := y; u := 2 * x; v := x + 1;x := 3; u := 2 * x; v := x + 1;13（3） 删除公共子表达式删除公共子表达式例如：例如：x := ( -y + z ) * z / 2 - ( -y + z )其中其中： ( -y + z )是公共子表达式。是公共子表达式。 我们可用我们可用DAG (directed acyclic graph，有向无循环图，有向无循环图)来表示具有公共子表达式的抽象语法树。来表示具有公共子表达式的抽象语法树。
14、具有相同值的子表达式在两个以上地方出现时，称它为具有相同值的子表达式在两个以上地方出现时，称它为公共子表达式公共子表达式(common subexpression)。14显然，对于公共子表达式显然，对于公共子表达式只要计算只要计算1次即可。次即可。x := ( -y + z ) * z / 2 - ( -y + z )+yz:=x*/215（4） 删除冗余代码删除冗余代码冗余代码就是毫无实际意义的代码，又称死代码冗余代码就是毫无实际意义的代码，又称死代码 (dead code)或无用代码或无用代码(useless code)。例如：例如： x := x + 0; x := x * 1; 等等又
15、例：又例： FLAG := TRUE IF FLAG THEN FLAG永真永真 ELSE 另外在程序中为了调试常有如下：另外在程序中为了调试常有如下： if debug then 的语句。的语句。 但当但当debug为为false时，时，then后面的语句便永远不会执行。这就是可删去后面的语句便永远不会执行。这就是可删去的冗余代码。的冗余代码。 ( 可用条件编译可用条件编译 #if DEBUG 程序编写，而源代码中还应留着）程序编写，而源代码中还应留着）16（5） 循环优化循环优化经验告诉我们：经验告诉我们：“程序运行时间的程序运行时间的80%是由仅占源是由仅占源程序程序20%的部分执行的的
16、部分执行的”。二八定律二八定律(Pareto Principle)这这20%的源程序就是循环部分，特别是多重循环的的源程序就是循环部分，特别是多重循环的最内层的循环部分。因此减少循环部分的目标代码对提最内层的循环部分。因此减少循环部分的目标代码对提高整个程序的时间效率有很大作用。高整个程序的时间效率有很大作用。 for i = 1 to 10 for j = 1 to 100 x := x + 0 ； y := 5 + 7 + x ;优化一条，少优化一条，少10*100次运算次运算17除了对循环体进行优化，还有专用于循环的优化除了对循环体进行优化，还有专用于循环的优化a)循环不变式的代码外提循
17、环不变式的代码外提 不变表达式：不变表达式：不随循环控制变量改变而改变的表达式或子表不随循环控制变量改变而改变的表达式或子表 达式。达式。如：如： FOR I := E1 STEP E2 TO E3 DO BEGIN S := 0.2 * 3.1416 * R P := 0.35 * I V := S * P不能外提不能外提!不变表达式可不变表达式可外提外提18如如 while do x := （b * b - 4.0 * a * c ) 若若a, b, c的值在该循环体中不改变时，则可将循环不的值在该循环体中不改变时，则可将循环不变式移到循环之外，即变为：变式移到循环之外，即变为： t1 :
18、= b * b - 4.0 * a * c while do x := ( t1) 从而减少计算次数从而减少计算次数 也称为频度削弱。也称为频度削弱。19b)循环展开循环展开 循环展开循环展开是一种优化技术。它将构成循环体的代码是一种优化技术。它将构成循环体的代码(不不包括控制循环的测试和转移部分包括控制循环的测试和转移部分)，重新产生许多次，重新产生许多次(这可在这可在编译时确定编译时确定)，而不仅仅是一次。以空间换时间，而不仅仅是一次。以空间换时间!例：例：PL/1中的初始化循环中的初始化循环 DO I = 1 TO 30 A I = 0.0 END I := 1L1: IF I 30 T
19、HEN GOTO L2 代码代码5条语句条语句 A I = 0.0 共执行共执行5*30 I = I+1 条语句条语句 GOTO L1L2:A1 = 0.0 30条语句条语句A2 = 0.0 （指令）执行指令）执行 也是也是30条语条语句句A30 = 0.0 展开展开20说明：说明： l 循环一次执行循环一次执行5条语句才给一个变量赋初值。展开后，一条语句就能赋一条语句才给一个变量赋初值。展开后，一条语句就能赋一个值，运行效率高。个值，运行效率高。l 优化在生成代码时进行，并不是修改源程序。优化在生成代码时进行，并不是修改源程序。l 必须知道循环的初值、终值及步长。必须知道循环的初值、终值及步
20、长。l 但非所有展开都是合适的。如上例中循环展开后节省了测试和转移语句：但非所有展开都是合适的。如上例中循环展开后节省了测试和转移语句：2*30=60语句。语句。 增加增加29条省条省60条条 但若循环体中不是一条而是但若循环体中不是一条而是40条，则展开将有条，则展开将有40*30=1200条，但省的仍是条，但省的仍是60条，就不算优化了。条，就不算优化了。 判断准则：判断准则：1. 主存资源丰富主存资源丰富 处理机时间昂贵处理机时间昂贵 2. 循环体语句越少越好循环体语句越少越好循环展开有利循环展开有利（大型机）（大型机）21实现步骤：实现步骤：1.识别循环结构，确定循环的初值、终值和步长
21、。识别循环结构，确定循环的初值、终值和步长。2.判断。判断。以空间换时间是否合算来决定是否展开。以空间换时间是否合算来决定是否展开。3.展开。展开。重复产生循环体所需的代码个数。重复产生循环体所需的代码个数。空间只多二条，空间只多二条，但省了但省了20次测次测试时间试时间（只循环（只循环10次）次）比较复杂：比较复杂：在对空间与时间进行权衡时，还可以考虑一种折衷的办法，在对空间与时间进行权衡时，还可以考虑一种折衷的办法，即部分展开循环。如上例展为：即部分展开循环。如上例展为：DO I = 1 TO 10 STEP 3 A I = 0.0 A I + 1 = 0.0 A I + 2 = 0.0E
22、ND;DO I = 1 TO 30 A I = 0.0 END22c) 归纳变量的优化和条件判断的替换归纳变量的优化和条件判断的替换归纳变量归纳变量(induction variable): 在每一次执行循环迭代的在每一次执行循环迭代的过程中，若某变量的值固定增加（或减少）一个常量值，过程中，若某变量的值固定增加（或减少）一个常量值，则称该变量为则称该变量为归纳变量归纳变量(induction variable)。即若当前即若当前执行循环的第执行循环的第 j 次迭代，归纳变量的值应为次迭代，归纳变量的值应为c * j + c, 这这里里 c 和和 c 都是循环不变式。都是循环不变式。例：例：
23、for i := 1 to 10 do ai := bi + ci23中间变量中间变量t1 ， t3 ， t6 都是归纳变量。都是归纳变量。t1 := 4 * i , t3 := 4 * i , t6 := 4 * i1) i := 12) labb:3) if i 10 goto labe 4) t1 := 4 * i5) t2 := b t1 6) t3 := 4 * i7) t4 := c t3 8) t5 := t2 + t49) t6 := 4 * i10) a t6 := t511) i := i + 112) goto labb13) labe:for i:= 1 to 10 d
24、o ai := bi + ci1)u := 42)labb:3)if u 40 goto labe4)tb := b u 5)tc := c u 6)t := tb + tc7)a u := t8)u := u + 49)goto labb10)labe:优化优化24d) 其它循环优化方法其它循环优化方法 把多重嵌套的循环变成单层循环。把多重嵌套的循环变成单层循环。 把把 n 个相同形式的循环合成一个循环等。个相同形式的循环合成一个循环等。对于循环优化的效果是很明显的。某对于循环优化的效果是很明显的。某FORTRAN 77 编译程编译程序，在进行不同级别的优化后所得的目标代码指令数为：序，在进
25、行不同级别的优化后所得的目标代码指令数为： 优化级别优化级别 循环内的指令数（包括循环条件判断）循环内的指令数（包括循环条件判断） 0（不优化）（不优化） 21 1（局部优化）（局部优化） 16 2（循环优化）（循环优化） 6 3（全局优化）（全局优化） 525（6） in_line 展开展开 把过程（或函数）调用改为把过程（或函数）调用改为in_line展开可节省许多处理过程展开可节省许多处理过程（函数）调用所花费的开销。（函数）调用所花费的开销。如：如： procedure m( i , j : integer; max : integer); begin if i j then max
26、:= i else max := j end;省去了函数调用时参数压栈，保存返回地址等指令。省去了函数调用时参数压栈，保存返回地址等指令。这也仅仅限于简单的函数。这也仅仅限于简单的函数。若有过程调用若有过程调用 m ( k , 0, max );则内置展开后为：则内置展开后为： if k 0 then max := k else max := 0;26（7）其他，）其他， 如控制流方法如控制流方法如如 BR L 无条件转移无条件转移 为不可达代码为不可达代码 L : 又如：转移到转移指令的指令又如：转移到转移指令的指令 BR L1 BR L2 L1: BR L2 L1: BR L2优化优化27
27、还有：还有： BRCC L1 当条件当条件CC成立，转到成立，转到L1 BR L2L1: . 可改进为：可改进为： BR CC L2 当条件不能成立时当条件不能成立时 ，转到，转到L2 L1: 此外还有其它方法。且随着软件技术的飞速发展，不断会有此外还有其它方法。且随着软件技术的飞速发展，不断会有新的优化方法推出。新的优化方法推出。28练习：作常数合并优化的表达式属性翻译文法及语义动练习：作常数合并优化的表达式属性翻译文法及语义动作程序（中间代码作程序（中间代码栈式抽象机指令）。栈式抽象机指令）。 例：例： A := 2 + 3 + C A := 5 + C 29总结：总结：局部优化局部优化:
28、 （一个入口，一个出口，线性）（一个入口，一个出口，线性）基本块基本块 方法：常数合并方法：常数合并 冗余子表达式的削除等冗余子表达式的削除等循环优化：对循环语句所生成的中间代码序列上所进行的循环优化：对循环语句所生成的中间代码序列上所进行的 优化优化 方法：循环展开方法：循环展开 频度削弱频度削弱 循环不变表达式的外提循环不变表达式的外提 强度削弱强度削弱全局优化：顾名思义，跨越多个基本块的全局范围内的优全局优化：顾名思义，跨越多个基本块的全局范围内的优 化。因此它是在非线性程序段上（包括多个基化。因此它是在非线性程序段上（包括多个基 本块本块, GOTO循环）的优化。循环）的优化。优化优化分为分为两大两大类类与机器无关的与机器无关的优化，即独立优化，即独立于机器的（中于机器的（中间）代码优化间）代码优化与机器有关的与机器有关的优化，即目标优化，即目标代码上的优化代码上的优化（与具体机器（与具体机器有关）有关）30
