编译原理及实现技术：第八章 中间代码优化

1、第八章 中间代码优化 引言 常量表达式优化 公共表达式优化 循环不变式外提 优化的目标： 优化的要求： 优化的对象：深层循环和下标变量地址的计算 优化的种类： 常表达式优化（合并常数项） 公共表达式优化（消除重复操作） 循环不变表达式外提 削减运算强度等等 优化方法： 全局优化：全局信息 局部优化：局部信息基本块和程序流图 基本块：单入口单出口的程序段。 程序流图：以基本块为结点的有向图，有向边表示 程序执行的流程。 中间代码基本块的划分： 初始代码为第一个基本块的入口 遇转移性中间代码时，结束当前基本块，下一条 代码作为新基本块的入口 遇标号性代码结束当前基本块，代码本身作为新 基本块的入口

2、。 遇（ASSIG, A, X）时，如果X为引用型形参时结 束当前块，并作为该块的出口。基本块划分的例子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 ; 基本块划分的例子B1:(ASSIG ,1,_,y)B2:(LABEL,L) (AND, A, B, t) (THEN,t,_,_)B3:(ASSIG,0,_,x) (ELSE,_,_,_)B4:(ASSIG,0,_,y) (ENDIF,_,_,_)B5:(ADDI,x,1,t1) (

3、ASSIG,t1,_,x) (SUBI,y,1,t2) (ASSIG,t2,_,y) B1B2 B4B3B5B6B8B7 程序流图例B6:(WHILE,_,_,) (ADDI,x,y,t3) (GT,t3,0,t4) (DO,t4,_,_)B7:(SUBI,x,1,t5) (ASSIG,t5,_,x) (ENDWHILE,_,_,_)B8:(ASSIG,0,_,z) 常表达式局部优化 常表达式：任何时候都取固定常数值的表达式 处理思想：针对每个基本块，如果一个多元式的两 个分量的值已知，则计算其值，并删掉 相应的中间代码。 原理：常量定值表ConsDef：(Var,Val)。 基本块入口置Co

4、nstDef为空； 对当前多元式的分量利用ConstDef表进行值代换； 新多元式形如（，A, B,t）:如果A和B是常数， 则计算AB的值v，并将（t,v）填入ConsDef表。并 删除该多元式 形如（ASSIG，A, B）:如果A是常数，则把（B,A） 填入ConsDef表，若已有B项，只需修改其值； 否则从ConsDef中删除B的登记项。 常表达式局部优化的例子源程序 中间代码 ConstDef 优化后的代码a:=1 (ASSIGN, 1,a) (a,1 ) (ASSIGN,1,a)b:=a+1 (ADDI,a,1,t1) (a,1)(t1,2) （ ) (ASSIGN,t1,b) (a

5、,1)(t1,2)(b,2) (ASSIGN,2,b)a:=x (ASSIGN, x,a) (t1,2)( b,2) (ASSIGN,a,x)c:=b+5 (ADDI,b,5,t2) (t1,2)(b,2)(t2,7) ( ) (ASSIGN,t2,c) (t1,2)(b,2) (t2,7)(c,7) (ASSIGN,7,c) 基于值编码的公共表达式局部优化 按值等价原理 优化思想： 对一个多元式的分量分别编码，具 有相同编码的分量等价。 值编码表ValuNnm: 可用表达式代码表UsableExpr 临时变量等价表TempEqua基于值编码的ECC优化算法入口处初始化：ValueNum,Us

6、ableExp和TempEqua为空。对当前多元式用TempEqua等价替换，生成NewTuple.如果NewTuple的A和B分量是未编码的，则编新码；如果多元式形如： dk:(, A, B, tk )若存在diUsableExpr使得dk是 di的ECC，则删掉dk，将(tk,ti)填入TempEqua表； 否则，为tk编码；把dk加入到UsableExpr表； dk:(ASSIG, A, B )则令B的值编码等于A的值编码，填入ValuNum表中；从UsableExpr删除所有含B的 中间代码。基于值编码的优化实例A:=B*C+B*CD:=BE:=D*C+B*C循环不变式外提优化 循环的

7、识别：识别循环的入口、重复体、出口部分 识别方法：基于程序文本，基于程序图。 外提对象：循环不变式 安全性: 除法表达式不能外提(除零溢出) 赋值表达式不能外提(不一定执行该循环） 外提原理： 定义LoopDef是在循环体内被定义的变量集合; 对每层循环记录LoopDef; 若循环体内的多元式( ,A,B,t)中的A,B不在本 层的LoopDef中,则把( ,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 DO FOR j :=0 TO 9 D

8、OFOR k:=0 TO 9 DO Aijk:=(ij)k ENDFOR ENDFOR ENDFOR ( , i ,100, t1 ) ( , A,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 )