编译原理及实现技术 教学课件 作者 刘磊 第08章 中间代码优化.ppt

《编译原理及实现技术 教学课件 作者 刘磊 第08章 中间代码优化.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、遇（ASSIG,A,X）时，如果X为引用型形参时结束当前块，并作为该块的出口。基本块划分的例子y:=1;L:ifAandBthenx:=0elsey:=0;x:=x+1;y:=y–1;whilex+y>0dox:=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)(AS

3、SIG,t2,_,y)B1B2B4B3B5B6B8B7程序流图例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为空；对当前多元式的分量利用Con

4、stDef表进行值代换；新多元式形如（，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,

5、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为空。对当前多

6、元式用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*CD:=BE:=D*C+B*C循环不变式外提优化循环的识别：识别循环

7、的入口、重复体、出口部分识别方法：基于程序文本，基于程序图。外提对象：循环不变式安全性:除法表达式不能外提(除零溢出)赋值表达式不能外提(不一定执行该循环）外提原理：定义LoopDef是在循环体内被定义的变量集合;对每层循环记录LoopDef;若循环体内的多元式(,A,B,t)中的A,B不在本层的LoopDef中,则把(,A,B,t)外提到循环体的入口处。循环优化实例i:=1whilei<=100dobeginz:=i*k*5a:=2*k+2*k*2i:=i+1;end外提实例FORi:=0TO9DOFORj:=0TO9DOFORk:=0TO9DO

8、A[i][j][k]:=(ij)kENDFORENDFORENDFOR(,i,100,t