第八章中间代码优化

1、Z 引言引言Z 常量表达式优化常量表达式优化Z 公共表达式优化公共表达式优化Z 循环不变式外提循环不变式外提 优化的目标：优化的目标： 优化的要求：优化的要求： 优化的对象：优化的对象：深层循环和下标变量地址的计算深层循环和下标变量地址的计算 优化的种类：优化的种类： 常表达式优化（合并常数项）常表达式优化（合并常数项） 公共表达式优化（消除重复操作）公共表达式优化（消除重复操作） 循环不变表达式外提循环不变表达式外提 削减运算强度等等削减运算强度等等 优化方法：优化方法： 全局优化：全局信息全局优化：全局信息 局部优化：局部信息局部优化：局部信息 基本块：基本块：单入口单出口的程序段。单入口

2、单出口的程序段。 程序流图：程序流图：以基本块为结点的有向图，有向边表示以基本块为结点的有向图，有向边表示 程序执行的流程。程序执行的流程。 中间代码基本块的划分：中间代码基本块的划分： 初始代码为第一个基本块的入口。初始代码为第一个基本块的入口。 遇转移性中间代码时，结束当前基本块，下一条遇转移性中间代码时，结束当前基本块，下一条 代码作为新基本块的入口。代码作为新基本块的入口。 遇标号性代码结束当前基本块，代码本身作为新遇标号性代码结束当前基本块，代码本身作为新 基本块的入口。基本块的入口。 遇（遇（ASSIG, A, XASSIG, A, X）时，如果时，如果X X为引用型形参时结为引用

3、型形参时结 束当前块，并作为该块的出口。束当前块，并作为该块的出口。y := 1 ;L: if A and B then x := 0 else y := 0 ;x := x + 1 ;y := y 1 ;while x + y 0 do x := x - 1 ;z := 0 ; B1B1:(ASSIG ,1,_,y):(ASSIG ,1,_,y)B2B2:(LABEL,L):(LABEL,L) (AND, A, B, t) (AND, A, B, t) (THEN,t,_,_)(THEN,t,_,_)B3:(ASSIG,0,_,x)B3:(ASSIG,0,_,x) (ELSE,_,_,_)(

4、ELSE,_,_,_)B4:(ASSIG,0,_,y)B4:(ASSIG,0,_,y) (ENDIF,_,_,_)(ENDIF,_,_,_)B5:(ADDI,x,1,t1)B5:(ADDI,x,1,t1) (ASSIG,t1,_,x) (ASSIG,t1,_,x) (SUBI,y,1,t2) (SUBI,y,1,t2) (ASSIG,t2,_,y) (ASSIG,t2,_,y) B B1 1B B2 2 B B4 4B B3 3B B5 5B B6 6B B8 8B B7 7 程序流图例程序流图例B6B6:(WHILE,_,_,):(WHILE,_,_,) (ADDI,x,y,t3) (ADD

5、I,x,y,t3) (GT,t3,0,t4) (GT,t3,0,t4) (DO,t4,_,_)(DO,t4,_,_)B7:(SUBI,x,1,t5)B7:(SUBI,x,1,t5) (ASSIG,t5,_,x) (ASSIG,t5,_,x) (ENDWHILE,_,_,_)(ENDWHILE,_,_,_)B8:(ASSIG,0,_,z) B8:(ASSIG,0,_,z) 常表达式常表达式：任何时候都取固定常数值的表达式：任何时候都取固定常数值的表达式 处理思想：处理思想：针对每个基本块，如果一个多元式的两针对每个基本块，如果一个多元式的两 个分量的值已知，则计算其值，并删掉个分量的值已知，则计

6、算其值，并删掉 相应的中间代码。相应的中间代码。 原理：原理：常量定值表常量定值表ConsDefConsDef：( (Var,Val)Var,Val)。 基本块入口置基本块入口置ConstDefConstDef为空；为空； 对当前多元式的分量利用对当前多元式的分量利用ConstDefConstDef表进行值代换；表进行值代换； 新多元式新多元式形如（形如（ ，A, B,tA, B,t）: :如果如果A A和和B B是常数，是常数， 则计算则计算A A B B的值的值v v，并将（并将（t,vt,v）填入填入ConsDefConsDef表。并表。并 删除该多元式；删除该多元式； 形如（形如（AS

7、SIGASSIG，A, BA, B）: :如果如果A A是常数，则把（是常数，则把（B,AB,A） 填入填入ConsDefConsDef表，若已有表，若已有B B项，只需修改其值；项，只需修改其值； 否则从否则从ConsDefConsDef中删除中删除B B的登记项。的登记项。 源程序源程序 中间代码中间代码 ConstDef ConstDef 优化后的代码优化后的代码a:=1a:=1 (ASSIGN, 1,a) (ASSIGN, 1,a) (a,1 )(a,1 ) (ASSIGN,1,a) (ASSIGN,1,a)b:=a+1b:=a+1 (ADDI,a,1,t1) (ADDI,a,1,t1

8、) (a,1)(t1,2)(a,1)(t1,2) （ ) ) (ASSIGN,t1,b) (ASSIGN,t1,b) (a,1)(t1,2)(b,2)(a,1)(t1,2)(b,2) (ASSIGN,2,b)(ASSIGN,2,b)a:=xa:=x (ASSIGN, x,a) (ASSIGN, x,a) (t1,2)( b,2)(t1,2)( b,2) (ASSIGN,a,x) (ASSIGN,a,x)c:=b+5c:=b+5 (ADDI,b,5,t2) (ADDI,b,5,t2) (t1,2)(b,2)(t2,7)(t1,2)(b,2)(t2,7) ( )( ) (ASSIGN,t2,c)

9、(ASSIGN,t2,c) (t1,2)(b,2) (t2,7)(c,7)(t1,2)(b,2) (t2,7)(c,7) (ASSIGN,7,c) (ASSIGN,7,c) | 按值等价原理按值等价原理| 优化思想优化思想 对一个多元式的分量分别编码，具对一个多元式的分量分别编码，具 有相同编码的分量等价。有相同编码的分量等价。| 值编码表值编码表ValuNnmValuNnm| 可用表达式代码表可用表达式代码表UsableExprUsableExpr| 临时变量等价表临时变量等价表TempEquaTempEqua|入口处初始化：入口处初始化：ValueNum,UsableExpValueNum

10、,UsableExp和和TempEquaTempEqua为空。为空。|对当前多元式用对当前多元式用TempEquaTempEqua等价替换，生成等价替换，生成NewTupleNewTuple。|如果如果NewTupleNewTuple的的A A和和B B分量是未编码的，则编新码；分量是未编码的，则编新码；|如果多元式形如：如果多元式形如： dk:( dk:( , A, A , B, B , tk ), tk )若存在若存在didi UsableExprUsableExpr使得使得dkdk是是 di di的的ECCECC，则删掉则删掉dkdk，将将( (tk,ttk,ti i) )填入填入Tem

11、pEquaTempEqua表；表； 否则，为否则，为tktk编码；把编码；把dkdk加入到加入到UsableExprUsableExpr表；表； dk:(ASSIG, A dk:(ASSIG, A , B, B ) )则令则令B B 的值编码等于的值编码等于A A 的值编码，的值编码，填入填入ValuNumValuNum表中；表中；从从UsableExprUsableExpr删除所有含删除所有含B B的的 中间代码。中间代码。A:=B*C+B*CD:=BE:=D*C+B*C 循环的识别：循环的识别：识别循环的入口、重复体、出口部分。识别循环的入口、重复体、出口部分。 识别方法：识别方法：基于程

12、序文本，基于程序图。基于程序文本，基于程序图。 外提对象：外提对象：循环不变式。循环不变式。 安全性安全性: : 除法表达式不能外提除法表达式不能外提( (除零溢出除零溢出) )； 赋值表达式不能外提赋值表达式不能外提( (不一定执行该循环）。不一定执行该循环）。 外提原理：外提原理： 定义定义LoopDefLoopDef是在循环体内被定义的变量集合是在循环体内被定义的变量集合; ; 对每层循环记录对每层循环记录LoopDef;LoopDef; 若循环体内的多元式若循环体内的多元式( ( , ,A,B,tA,B,t) )中的中的A,BA,B不在本不在本 层的层的LoopDefLoopDef中中

13、, ,则把则把( ( , ,A,B,t)A,B,t)外提到循环体外提到循环体 的入口处。的入口处。i:=1while i=100 dobegin z:=i*k*5 a:=2*k+2*k*2 i:=i+1;end FOR i :=0 TO 9 DOFOR i :=0 TO 9 DO FOR j :=0 TO 9 DOFOR j :=0 TO 9 DOFOR k:=0 TO 9 DO FOR k:=0 TO 9 DO Aijk:=(i Aijk:=(i j)j) k k ENDFORENDFOR ENDFOR ENDFOR ENDFOR ENDFOR ( , i ,100, t1 ) ( , A,

14、t1, t2 ) ( , j ,10, t3 ) ( , t2, t3, t4 ) ( , t4, k , t5 ) ( , i , j, t6 ) ( , t6,k, t7 ) ( , t7, t5 ) ( , i ,100, t1 ) ( , A,t1, t2 ) ( , j ,10, t3 ) ( , t2, t3, t4 ) ( , i , j, t6 ) ( , t4, k , t5 ) ( , t6,k, t7 ) ( , t7, t5 ) ( , i ,100, t1 ) ( , A,t1, t2 ) ( , j ,10, t3 ) ( , t2, t3, t4 ) ( , i , j, t6 ) ( , t4, k , t5 ) ( , t6,k, t7 ) ( , t7, t5 )|人有了知识，就会具备各种分析能力，人有了知识，就会具备各种分析能力，|明辨是非的能力。明辨是非的能力。|所以我们要勤恳读书，广泛阅读，所以我们要勤恳读书，广泛阅读，|古人说古人说“书中自有黄金屋。书中自有黄金屋。|”通过阅