第八章-中间代码优化.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 ; 基本块划分的例子 常表达式局部优化 常表达式：任何时候都取固定常数值的表达式 处理思想：针对每个基本块，如果一个多元式的两 个分量的值已知，则计算其值，并删掉 相应的中间代码。 原理：常量定值表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的登记项。 常表达式局部优化的例子 基于值编码的公共表达式局部优化 按值等价原理 优化思想 对一个多元式的分量分别编码，具 有相同编码的分量等价。 值编码表ValuNnm 可用表达式代码表UsableExpr 临时变量等价表TempEqua 基于值编码的ECC优化算法 入口处初始化：ValueNum,UsableExp和TempEqua为空。 对当前多元式用TempEqua等价替换，生成NewTuple。 如果NewTuple的A和B分量是未编码的，则编新码； 如果多元式形如： dk:(?, A?, B?, tk )若存在di?UsableExpr使得dk是 di的ECC，则删掉dk，将(tk,ti)填入TempEqua表； 否则，为tk编码；把dk加入到UsableExpr表； dk:(ASSIG, A?, B? )则令B?的值编码等于A?的值编码，填入ValuNum表中；从UsableExpr删除所有含B的 中间代码。 基于值编码的优化实例 A:=B*C+B*C D:=B E:=D*C+B*C 循环不变式外提优化 循环的识别：识别循环的入口、重复体、出口部分。 识别方法：基于程序文本，基于程序图。 外提对象：循环不变式。 安全性: 除法表达式不能外提(除零溢出)； 赋值表达式不能外提(不一定执行该循环）。 外提原理： 定义LoopDef是在循环体内被定义的变量集合; 对每层循环记录LoopDef; 若循环体内的多元式( ?,A,B,t)中的A,B不在本 层的LoopDef中,则把( ?,A,B,t)外提到循环体 的入口处。 循环优化实例 i:=1 while i=100 do begin z:=i*k*5 a:=2*k+2*k*2 i:=i+1; end 外提实例 * * 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