第八章中间代码优化试卷.ppt

第八章 中间代码优化 引言 常量表达式优化 公共表达式优化 循环不变式外提 优化的目标： 优化的要求： 优化的对象：深层循环和下标变量地址的计算 优化的种类： 常表达式优化（合并常数项） 公共表达式优化（消除重复操作） 循环不变表达式外提 削减运算强度等等 优化方法： 全局优化：全局信息 局部优化：局部信息 基本块和程序流图 基本块：单入口单出口的程序段。 程序流图：以基本块为结点的有向图，有向边表示 程序执行的流程。 中间代码基本块的划分： ? 初始代码为第一个基本块的入口。 ? 遇转移性中间代码时，结束当前基本块，下一条 代码作为新基本块的入口。 ? 遇标号性代码结束当前基本块，代码本身作为新 基本块的入口。 ? 遇（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) (ASSIG,t1,_,x) (SUBI,y,1,t2) (ASSIG,t2,_,y) B1 B2 B4 B3 B5 B6 B8 B7 程序流图例 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)。 ? 基本块入口置ConstDef为空； ? 对当前多元式的分量利用ConstDef表进行值代换； ? 新多元式形如（?，A, B,t）:如果A和B是常数， 则计算A?B的值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,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,UsableExp和TempEqua为空。 对当前多元式用TempEqua等价替换，生成NewTuple。 如果NewTuple的A和B分量是未编码的，则编新码； 如果多元式形如：