编译原理,清华大学,第2版_第11章 代码优化.ppt

第十一章 代码优化 11.1 优化技术简介 11.2 局部优化 11.3 控制流分析和循环优化 11.1 优化技术简介 一、优化的原则 1、等价原则 优化后不改变原程序运行的功能。 2、有效原则 优化后产生的目标代码运行时间较短，占用空间较小。 三、优化分类 (1)局部优化:对基本块内的代码进行优化 (2)循环优化:对循环中的代码进行优化 (3)全局优化:在整个程序范围内的优化 四、常用优化技术简介 1.删除多余运算 2.循环不变代码外提 3.强度削弱 4.变换循环控制条件 5.合并已知量与复写传播 6.删除无用赋值 1.删除多余运算（删除公共子表达式）： 例如：（假设数组元素占用空间为4个字节） P:=0 for I:=1 to 20 do P:=P+A[I]*B[I] (6)T4:=4*I (7)T5:=addr(B) (8)T6:=T5[T4] (9)T7:=T3*T6 (10)P:=P+T7 (11)I:=I+1 (12)if I=20 goto(3) 2、代码外提 目的：减少循环中代码总数。 方法：把循环不变运算，即其结果独立于循环执行次数的表达式提到循环的前面，使之只在循环外计算一次。 (1)P:=0 (2)I:=0 (3)T1:=4*I (4)T2:=addr(A) (5)T3:=T2[T1] (6)T4:=T1 (7)T5:=addr(B) (8)T6:=T5[T4] (9)T7:=T3*T6 (10)P:=P+T7 (11)I:=I+1 (12)if I=20 goto(3) (1)P:=0 (2)I:=0 (3)T1:=4*I (5)T3:=T2[T1] (6)T4:=T1 (8)T6:=T5[T4] (9)T7:=T3*T6 (10)P:=P+T7 (11)I:=I+1 (12)if I=20 goto(3) (1)P:=0 (2)I:=0 (4)T2:=addr(A) (7)T5:=addr(B) (3)T1:=4*I (5)T3:=T2[T1] (6)T4:=T1 (8)T6:=T5[T4] (9)T7:=T3*T6 (10)P:=P+T7 (11)I:=I+1 (12)if I=20 goto(3) (1)P:=0 (2)I:=0 (4)T2:=addr(A) (7)T5:=addr(B) (5)T3:=T2[T1] (6)T4:=T1 (8)T6:=T5[T4] (9)T7:=T3*T6 (10)P:=P+T7 (11)I:=I+1 (12)if I=20 goto(5) 4、变换循环控制条件 经过变换后，有些变量不被引用，可以从循环中删除。 (1)P:=0 (2)I:=0 (4)T2:=addr(A) (7)T5:=addr(B) (3)T1:=4*I (5)T3:=T2[T1] (6)T4:=T1 (8)T6:=T5[T4] (9)T7:=T3*T6 (10)P:=P+T7 (11)I:=I+1 (3’)T1:=T1+4 (12)if I=20 goto(5) (1)P:=0 (2)I:=1 (4)T2:=addr(A) (7)T5:=addr(B) (3)T1:=4*I (5)T3:=T2[T1] (6)T4:=T1 (8)T6:=T5[T4 ] (9)T7:=T3*T6 (10)P:=P+T7 (3’)T1:=T1+4 (12)if goto(5) 5、合并已知量与复写传播 编码时的已知量—常数，可在编译时计算出它的值，这种变换称为合并已知量或常数合并。 通过复制后没有再改变的值可以互相替换，不会改变程序的结果，这种变换称为复写传播。 复写传播 tmp2 = tmp1 ; tmp3 = tmp2 * tmp1; tmp4 = tmp3 ; tmp5 = tmp3 * tmp2 ; c = tmp5 + tmp4 ; tmp3 = tmp1 * tmp1 ; tmp5 = tmp3 * tmp1 ; c = tmp5 + tmp3 ; (1)P:=0 (2)I:=0 (4)T2:=addr(A) (7)T5:=addr(B) (3)T1:=4*I (5)T3:=T2[T1] (6)T4:=T1 (8)T6:=T5[T4] (9)T7:=T3*T6 (10)P:=P+T7 (3’)T1:=T1+4 (12)if T1=80 goto(5) (1)P:=0 (2)I:=0 (4)T2:=addr(A) (7)T5:=addr(B) (5)T3:=T2[T1] (6)T4:=T1 (9)T7:=T3*T6 (10)P:=P+T7 (3’)T1:=T1+4 (12)if T1=80 g