《《编译原理》第章-中间代码优化.ppt》由会员分享，可在线阅读，更多相关《《编译原理》第章-中间代码优化.ppt（18页珍藏版）》请在三一文库上搜索。
1、第九章 中间代码优化,引言 常量表达式优化 公共表达式优化 循环不变式外提,例 i:=0; j:=0; while i10 do begin while j10 do begin Aij:=Aij+Aij+1; j:=j+1; end i:=i+1; end,优化的目标： 优化的要求： 优化的对象：深层循环和下标变量地址的计算 优化的种类： 常表达式优化（合并常数项） 公共表达式优化（消除重复操作） 循环不变表达式外提 削减运算强度等等 优化方法： 全局优化：全局信息 局部优化：局部信息,基本块和程序流图,基本块：单入口单出口的程序段。 程序流图：以基本块为结点的有向图，有向边表示 程序执行的
2、流程。 中间代码基本块的划分： 初始代码为第一个基本块的入口 遇转移性中间代码时，结束当前基本块，下一条 代码作为新基本块的入口 遇标号性代码结束当前基本块，代码本身作为新 基本块的入口。 遇（ASSIG, A, X）时，如果X为引用型形参时结 束当前块，并作为该块的出口。,基本块划分的例子,B1:( ASSIGN,1, Y ) B6:( LABEL, L6)B2:( LABEL, L0 ) (ADDI, X, Y,t3 ) ( AND，A, B, t ) (GT, t3, 0, t4 ) ( JUMP0, t, L4) (JUMP0, t4, L8)B3:( ASSIGN, 0, X ) B
3、7:( SUBI, X, 1,t5 ) ( JUMP, L5 ) ( ASSIGN, t5, X )B4:( LABEL, L4) ( JUMP, L6 ) ( ASSIG,0, Y ) B8:( LABEL, L8 )B5:( LABEL, L5 ) ( ASSIGN, 0, Z ) ( ADDI, X, 1, t1) ( STOP ) ( ASSIGN, t1, X ) ( SUBI Y, 1, t2 ) ( ASSIGN, t2, Y),常表达式局部优化,常表达式：任何时候都取固定常数值的表达式 处理思想：针对每个基本块，如果一个多元式的两 个分量的值已知，则计算其值，并删掉 相应的中间
4、代码。 原理：常量定值表ConstDef：(Var,Val)。 基本块入口置ConstDef为空； 对当前多元式的分量利用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)
5、 (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),基于常量定值分析的常量表达式全局优化,思想：可利用基本块外的常量信息进行优化。基本块 入口处的ConstDef不简单的定义为空，基本块出口 处的ConstDef还在后面的基本块中用到。 问题：计算入口处和
6、出口处的常量定值集合。 方法：用常量定值的数据流分析。 计算四种集合： in-c(Bi)：在Bi块的入口处可用的常量定值之集。 out-c(Bi):在Bi块的出口处可用的常量定值之集。 def-c(Bi):在Bi块内产生并且在Bi的出口处可用 的常量定值之集。 kill-c(Bi):被Bi块所杀死的常量定值之集。若Bi 块有对X的赋值，则称Bi块将杀死X的常量定值。,def-c(Bi) 和kill-c(Bi)可以确定 out-c(Bi)= (in-c(Bi) - kill-c(Bi) def-c(Bi)in-c(Bi)= jpre(i) out-c(Bj)应用in_c(Bi)可以对Bi进行常量
7、表达式优化。常表达式优化原理： 对每一基本块Bi求出in-c(Bi)集合， 其中in-c(B0)为空； 用in-c(Bi)代替基本块Bi的ConstDef； 优化过程同局部常表达式优化原理，,基于相似性的公共表达式局部优化,相似多元式：设(1,A1,B1,T1)和(2 ,A2,B2,T2) 是两个非赋值型多元式，1 = 2，且A1和A2，B1 和B2的名字彼此相同，则称这两个多元式相似。 公共子表达式（可节省的公共代码ECC）： di所定义的表达式在dk处是 可用的； UsableExpr:可用表达式集 等价表(PAIR)：(ti,tj)表示ti和tj是等价的，需用tj 替换ti。,.di:
8、( , A, B, ti ).dk: ( , A, B, tk ).,基于相似性的ECC优化算法,设UsableExp 和 PAIR 为空； 对当前多元式根据PAIR来进行等价替换，生成 NewTuple; 如果NewTuple 形如： dk:( , A, B, tk ): 若UsableExp 中存在相似表 达式di:(, A, B, tj )，则删掉dk,并在PAIR 表中填入(tk,tj)；否则dk不优化，把dk加到 UsableExpr中； dk:( ASSIG, A, B )：从UsableExpr删除含B的所 有可用表达式代码。,实例： D:=D+CB; A:=D+CB; C:=D
9、+CB; A:=D+CB；,基于值编码的公共表达式局部优化,按值等价原理 优化思想： 对一个多元式的分量分别编码，具 有相同编码的分量等价。 值编码表ValuNnm: 可用表达式代码表UsableExpr 临时变量等价表TempEqua,基于值编码的ECC优化算法,入口处初始化：ValueNum,UsableExp和TempEqua为空。对当前多元式用TempEqua等价替换，生成NewTuple.如果NewTuple的A和B分量是未编码的，则编新码；如果多元式形如： dk:(, A, B, tk )若存在diUsableExpr使得dk是 di的ECC，则删掉dk，将(tk,ti)填入Tem
10、pEqua表； 否则，为tk编码；把dk加入到UsableExpr表； dk:(ASSIG, A, B )则令B的值编码等于A的值编码， 填入ValuNum表中；从UsableExpr删除所有含B的 中间代码。,基于值编码的优化实例,循环不变式外提优化,循环的识别：识别循环的入口、重复体、出口部分。 识别方法：基于程序文本，基于程序图。 外提对象：循环不变式 安全性: 除法表达式不能外提(除零溢出) 赋值表达式不能外提(不一定执行该循环） 外提原理： 定义LoopDef是在循环体内被定义的变量集合; 对每层循环记录LoopDef; 若循环体内的多元式( ,A,B,t)中的A,B不在本 层的LoopDef中,则把( ,A,B,t)外提到循环体 的入口处。,外提实例,FOR i :=0 TO 9 DO FOR j :=0 TO 9 DOFOR 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 ),