编译原理第9章课件.pptVIP

第9章 代码优化;目录;9.1 优化技术简介;与机器无关的优化---对中间代码进行； 依赖于机器的优化--对目标代码进行;四、优化分类;五、常用优化技术简介;目的：提高目标代码速度。 例如： P:=0 for I:=1 to 20 do P:=P+A[I]*B[I];(1)P:=0 (2)I:=1 (3)T1:=4*I (4)T2:=addr(A)-4 (5)T3:=T2[T1] (6)T4:=4*I (7)T5:=addr(B)-4 (8)T6:=T5[T4] (9)T7:=T3*T6 (10)P:=P+T7 (11)I:=I+1 (12)if I=20 goto(3); 减少循环中代码总数的重要办法。 方法：把循环不变运算，即其结果独立于循环执行次数的表达式提到循环的前面，使之只在循环外计算一次。 例如： P:=0 for I:=1 to 20 do P:=P+A[I]*B[I];(1)P:=0 (2)I:=1 (3)T1:=4*I (4)T2:=addr(A)-4 (5)T3:=T2[T1] (6)T4:=T1 (7)T5:=addr(B)-4 (8)T6:=T5[T4] (9)T7:=T3*T6 (10)P:=P+T7 (11)I:=I+1 (12)if I=20 goto(3);基本思想：把强度大的运算换算成强度小的。例如： a) i*2 = 2*i = i+i = i1 b) i/2 = (int)(i*0.5) c) 0-1 = -1 d) f*2 = 2.0 * f = f + f e) f/2.0 = f*0.5;(1)P:=0 (2)I:=1 (4)T2:=addr(A)-4 (7)T5:=addr(B)-4 (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) ;4、变换循环控制条件;(1)P:=0 (2)I:=1 (4)T2:=addr(A)-4 (7)T5:=addr(B)-4 (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) ;5、合并已知量与复写传播;(1)P:=0 (2)I:=1 (4)T2:=addr(A)-4 (7)T5:=addr(B)-4 (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:=1 (4)T2:=addr(A)-4 (7)T5:=addr(B)-4 (3)T1:=4 (5)T3:=T2[T1] (6)T4:=T1 (8)T6:=T5[T1] (9)T7:=T3*T6 (10)P:=P+T7 (3’)T1:=T1+4 (12)if T1=80 goto(5) ;局部优化：基本块内的优化;a)求出各基本块的入口语句 对四元式程序，各个基本块的入口语句是： 1)程序的第一个语句 ；或 2)能由条件转移语句和无条件转移语句转移到达的语句；或 3)紧跟在条件转移语句后面的语句。 注：若条件语句由真转移和假转移两条语句组成，则跟在转移语句后面的语句是指假转移语句后面的一条语句。;b)根据入口语句，构造其所属的基本块 一入口语句所属的基本块是由该入口语句到: 下一入口语句(不包括该入口语句); 或到一转移语句(包括转移语句); 或到一停(halt)语句(包括该语句) 之间的语句序列组成。 C)删除不会被执行的语句 凡是没有纳入到任何一个基本块中的语句，都是程序控制流程所无法到达的语句，即不会被执行到的语句，可将其删除。;例：求最大公因子算法 begin read X; read Y; while (X mod Y0) do begin T:=X mod Y; X:=Y; Y:=T end; write Y end;(1)Read X (2)Read Y; 主要是进行已知量合并、删除公共子表达式、删除无用赋值。 注：仅在一个基本块中，