第09章中间代码优化精.ppt

第09章中间代码优化第1页，本讲稿共17页 优化的目标：优化的目标：优化的要求：优化的要求：优化的对象：优化的对象：深层循环和下标变量地址的计算深层循环和下标变量地址的计算 优化的种类：优化的种类：常表达式优化（合并常数项）常表达式优化（合并常数项）公共表达式优化（消除重复操作）公共表达式优化（消除重复操作）循环不变表达式外提循环不变表达式外提 削减运算强度等等削减运算强度等等 优化方法：优化方法：全局优化：全局信息全局优化：全局信息 局部优化：局部信息局部优化：局部信息第2页，本讲稿共17页基本块和程序流图基本块和程序流图 基本块：基本块：单入口单出口的程序段。单入口单出口的程序段。程序流图：程序流图：以基本块为结点的有向图，有向边表示以基本块为结点的有向图，有向边表示 程序执行的流程。程序执行的流程。中间代码基本块的划分：中间代码基本块的划分：初始代码为第一个基本块的入口初始代码为第一个基本块的入口 遇转移性中间代码时，结束当前基本块，下一条遇转移性中间代码时，结束当前基本块，下一条 代码作为新基本块的入口代码作为新基本块的入口 遇标号性代码结束当前基本块，代码本身作为新遇标号性代码结束当前基本块，代码本身作为新 基本块的入口。基本块的入口。遇（遇（ASSIG,A,XASSIG,A,X）时，如果）时，如果X X为引用型形参时结为引用型形参时结 束当前块，并作为该块的出口。束当前块，并作为该块的出口。第3页，本讲稿共17页基本块划分的例子基本块划分的例子B B1 1:(ASSIGN,1,Y)(ASSIGN,1,Y)B B6 6:(LABEL,L6):(LABEL,L6)B B2 2:(LABEL,L0):(LABEL,L0)(ADDI,X,Y,t3)(ADDI,X,Y,t3)(AND (AND，A,B,t)(GT,t3,0,t4)A,B,t)(GT,t3,0,t4)(JUMP0,t,L4)(JUMP0,t,L4)(JUMP0,t4,L8)(JUMP0,t4,L8)B B3 3:(ASSIGN,0,X):(ASSIGN,0,X)B B7 7:(SUBI,X,1,t5)(SUBI,X,1,t5)(JUMP,L5 )(JUMP,L5 )(ASSIGN,t5,X)(ASSIGN,t5,X)B B4 4:(LABEL,L4):(LABEL,L4)(JUMP,L6)(JUMP,L6)(ASSIG,0,Y)(ASSIG,0,Y)B B8 8:(LABEL,L8):(LABEL,L8)B B5 5:(LABEL,L5):(LABEL,L5)(ASSIGN,0,Z)(ASSIGN,0,Z)(ADDI,X,1,t1)(ADDI,X,1,t1)(STOP)(STOP)(ASSIGN,t1,X)(ASSIGN,t1,X)(SUBI Y,1,t2)(SUBI Y,1,t2)(ASSIGN,t2,Y)(ASSIGN,t2,Y)B B1 1B B2 2 B B4 4B B3 3B B5 5B B6 6B B8 8B B7 7程序流图例程序流图例第4页，本讲稿共17页常表达式局部优化常表达式局部优化 常表达式：常表达式：任何时候都取固定常数值的表达式任何时候都取固定常数值的表达式 处理思想：处理思想：针对每个基本块，如果一个多元式的两针对每个基本块，如果一个多元式的两 个分量的值已知，则计算其值，并删掉个分量的值已知，则计算其值，并删掉 相应的中间代码。相应的中间代码。原理：原理：常量定值表常量定值表ConstDefConstDef：(Var,Val)(Var,Val)。基本块入口置基本块入口置ConstDefConstDef为空；为空；对当前多元式的分量利用对当前多元式的分量利用ConstDefConstDef表进行值代换；表进行值代换；新多元式新多元式形如（形如（，A,B,tA,B,t）:如果如果A A和和B B是常数，是常数，则计算则计算A A B B的值的值v v，并将（，并将（t,vt,v）填入）填入ConsDefConsDef表。表。形如（形如（ASSIGASSIG，A,BA,B）:如果如果A A是常数，则把（是常数，则把（B,AB,A）填入填入ConsDefConsDef表，若已有表，若已有B B项，只需修改其值；项，只需修改其值；否则从否则从ConsDefConsDef中删除中删除B B的登记项。的登记项。第5页，本讲稿共17页常表达式局部优化的例子常表达式局部优化的例子源程序源程序 中间代码中间代码 ConstDef ConstDef 优化后的代码优化后的代码a:=1a:=1 (ASSIGN,1,a)(ASSIGN,1,a)(a,1)(a,1)(ASSIGN,1,a)(ASSIGN,1,a)b:=a+1b:=a+1 (ADDI,a,1,t1)(ADDI,a,1,t1)(a,1)(t1,2)(a,1)(t1,2)（)(ASSIGN,t1,b)(ASSIGN,t1,b)(a,1)(t1,2)(b,2)(a,1)(t1,2)(b,2)(ASSIGN,2,b)(ASSIGN,2,b)a:=xa:=x (ASSIGN,x,a)(ASSIGN,x,a)(t1,2)(b,2)(t1,2)(b,2)(ASSIGN,a,x)(ASSIGN,a,x)c:=b+5c:=b+5 (ADDI,b,5,t2)(ADDI,b,5,t2)(t1,2)(b,2)(t2,7)(t1,2)(b,2)(t2,7)()()(ASSIGN,t2,c)(ASSIGN,t2,c)(t1,2)(b,2)(t2,7)(c,7)(t1,2)(b,2)(t2,7)(c,7)(ASSIGN,7,c)(ASSIGN,7,c)第6页，本讲稿共17页常量表达式全局优化常量表达式全局优化 思想：思想：可利用基本块外的常量信息进行优化。基本块可利用基本块外的常量信息进行优化。基本块 入口处的入口处的ConstDefConstDef不简单的定义为空，基本块出口不简单的定义为空，基本块出口 处的处的ConstDefConstDef还在后面的基本块中用到。还在后面的基本块中用到。问题：问题：计算入口处和出口处的常量定值集合。计算入口处和出口处的常量定值集合。方法：方法：用常量定值的数据流分析。用常量定值的数据流分析。计算四种集合：计算四种集合：in_c(Bi)in_c(Bi)：在在BiBi块的入口处可用的常量定值之集。块的入口处可用的常量定值之集。out_c(Bi):out_c(Bi):在在BiBi块的出口处可用的常量定值之集。块的出口处可用的常量定值之集。def_c(Bi):def_c(Bi):在在BiBi块内产生并且在块内产生并且在BiBi的出口处可用的出口处可用 的常量定值之集。的常量定值之集。kill_c(Bi):kill_c(Bi):被被BiBi块所杀死的常量定值之集。若块所杀死的常量定值之集。若BiBi 块有对块有对X X的赋值，则称的赋值，则称BiBi块将杀死块将杀死X X的常量定值。的常量定值。第7页，本讲稿共17页def_c(Bi)def_c(Bi)和和kill_c(Bi)kill_c(Bi)可以确定可以确定 out_c(Bi)=out_c(Bi)=(in_c(Bi)(in_c(Bi)kill_c(Bi)kill_c(Bi)def_c(Bi)def_c(Bi)in_c(Bi)=in_c(Bi)=jpre(i)jpre(i)out_c(B out_c(Bj j)应用应用in_c(Bi)in_c(Bi)可以对可以对BiBi进行常量表达式优化。进行常量表达式优化。常表达式全局优化原理：常表达式全局优化原理：对每一基本块对每一基本块BiBi求出求出in_c(Bi)in_c(Bi)集合，集合，其中其中in_c(Bin_c(B0 0)为空；为空；用用in_c(Bi)in_c(Bi)代替基本块代替基本块BiBi的的ConstDefConstDef；优化过程同局部常表达式优化原理，优化过程同局部常表达式优化原理，第8页，本讲稿共17页x:=1x:=1y:=2y:=2z:=a+1z:=a+1z:=3z:=3u:=x+5u:=x+5w:=9w:=9b:=y-1b:=y-1z:=3z:=3k:=7k:=7m:=k+zm:=k+zn:=m+1n:=m+1b:=k+1b:=k+1d:=m+nd:=m+nl:=z+yl:=z+yd:=k+xd:=k+xx:=1x:=1y:=2y:=2z:=a+1z:=a+1z:=3z:=3u:=6u:=6w:=9w:=9b:=1b:=1z:=3z:=3k:=7k:=7m:=10m:=10n:=11n:=11b:=8b:=8d:=21d:=21l:=5l:=5d:=8d:=8x:=1x:=1y:=x+1y:=x+1z:=a+1z:=a+1z:=3z:=3u:=x+5u:=x+5w:=6+zw:=6+zb:=y-1b:=y-1z:=3z:=3k:=7k:=7m:=k+zm:=k+zn:=m+1n:=m+1b:=k+1b:=k+1d:=m+nd:=m+nl:=z+yl:=z+yd:=k+xd:=k+x123456第9页，本讲稿共17页基于相似性的公共表达式局部优化基于相似性的公共表达式局部优化 相似多元式：相似多元式：设设(1 1,A,A1 1,B,B1 1,T,T1 1)和和(2 2,A,A2 2,B,B2 2,T,T2 2)是两个非赋值型多元式，是两个非赋值型多元式，1 1=2 2，且，且A A1 1和和A A2 2，B B1 1 和和B B2 2的名字彼此相同，则称这两个多元式相似。的名字彼此相同，则称这两个多元式相似。公共子表达式（可节省的公共代码公共子表达式（可节省的公共代码ECCECC）：）：didi所定义的表达式在所定义的表达式在dkdk处是处是 可用的；可用的；UsableExpr:UsableExpr:可用表达式集可用表达式集 等价表等价表(PAIR(PAIR)：(t(ti i,t,tj j)表示表示t ti i和和t tj j是等价的，需用是等价的，需用t tj j 替换替换t ti i。.di:di:(,A,B,ti),A,B,ti).dk:dk:(,A,A,B,B,tk),tk).第10页，本讲稿共17页基于相似性的基于相似性的ECCECC优化算法优化算法|设设UsableExp UsableExp 和和 PAIR PAIR 为空；为空；|对当前多元式根据对当前多元式根据PAIRPAIR来进行等价替换，生成来进行等价替换，生成 NewTuple;NewTuple;|如果如果NewTuple NewTuple 形如：形如：dk:(dk:(,A,B,tk):,A,B,tk):若若UsableExp UsableExp 中存在相似表中存在相似表 达式达式di:(di:(,A,B,tj),A,B,tj)，则删掉，则删掉dk,dk,并在并在PAIR PAIR 表中填入表中填入(tk,tj)(tk,tj)；否则；否则dkdk不优化，把不优化，把dkdk加到加到 UsableExprUsableExpr中；中；dk:(ASSIG,A,B)dk:(ASSIG,A,B)：从从UsableExprUsableExpr删除含删除含B B的所的所 有可用表达式代码。有可用表达式代码。第11页，本讲稿共17页 优化前优化前优化后优化后UEUEPAIRPAIR1.(,C,B,t1)2.(,D,t1,t2)3.(:=,t2,D)4.(,C,B,t3)5.(,D,t3,t4)6.(:=,t4,A)7.(,C,B,t5)8.(,D,t5,t6)9.(:=,t6,C)10.(,C,B,t7)11.(,D,t7,t8)12.(:=,t8,A)(,C,B,t1)(,D,t1,t2)(:=,t2,D)()(,D,t1,t4)(:=,t4,A)()()(:=,t4,C)(,C,B,t7)(,D,t7,t8)(:=,t8,A)11,21 1 1,5 1,5 1,5 1,5 5 5,10 5,10,11 5,10,11 (t3,t1).(t3,t1),(t5,t1)(t3,t1),(t5,t1),(t6,t4).|实例：实例：D:=D+CB;A:=D+CB;C:=D+CB;A:=D+CBD:=D+CB;A:=D+CB;C:=D+CB;A:=D+CB；第12页，本讲稿共17页基于值编码的公共表达式局部优化基于值编码的公共表达式局部优化|按值等价原理按值等价原理|优化思想：优化思想：对一个多元式的分量分别编码，具对一个多元式的分量分别编码，具 有相同编码的分量等价。有相同编码的分量等价。|值编码表值编码表ValuNnm:ValuNnm:|可用表达式代码表可用表达式代码表UsableExprUsableExpr|临时变量等价表临时变量等价表TempEquaTempEqua第13页，本讲稿共17页基于值编码的基于值编码的ECCECC优化算法优化算法|入口处初始化：入口处初始化：ValueNum,UsableExpValueNum,UsableExp和和TempEquaTempEqua为空。为空。|对当前多元式用对当前多元式用TempEquaTempEqua等价替换，生成等价替换，生成NewTuple.NewTuple.|如果如果NewTupleNewTuple的的A A和和B B分量是未编码的，则编新码；分量是未编码的，则编新码；|如果多元式形如：如果多元式形如：dk:(dk:(,A,A,B,B,tk),tk)若存在若存在didi UsableExprUsableExpr使得使得dkdk是是 didi的的ECCECC，则删掉，则删掉dkdk，将，将(tk,t(tk,ti i)填入填入TempEquaTempEqua表；表；否则，为否则，为tktk编码；把编码；把dkdk加入到加入到UsableExprUsableExpr表；表；dk:(ASSIG,Adk:(ASSIG,A,B,B )则令则令B B 的值编码等于的值编码等于A A 的值编码，的值编码，填入填入ValuNumValuNum表中；表中；从从UsableExprUsableExpr删除所有含删除所有含B B的的 中间代码。中间代码。第14页，本讲稿共17页基于值编码的优化实例基于值编码的优化实例中间代码中间代码 映象映象TempEqua UETempEqua UE 优化代码优化代码(,B,C,t1),B,C,t1)(,B,C,t2),B,C,t2)(+,t1,t2,t3)(+,t1,t2,t3)(:=,t3,A)(:=,t3,A)(:=,B,D)(:=,B,D)(,D,C,t4),D,C,t4)(,B,C,t5),B,C,t5)(+,t4,t5,t6)(+,t4,t5,t6)(:=,t6,E)(:=,t6,E)(1,2,3)(1,2,3)(1,2,3)(1,2,3)(3,3,4)(3,3,4)(A)=4(A)=4(D)=1(D)=1(1,2,3)(1,2,3)(1,2,3)(1,2,3)(3,3,4)(3,3,4)(E)=4(E)=4 1 1(t2,t1)(t2,t1)1 1 1,3 1,3 .(t4,t1).(t4,t1).(t5,t1).(t5,t1).(t6,t3).(t6,t3).(,B,C,t1),B,C,t1)()()(+,t1,t1,t3(+,t1,t1,t3)(:=,t3,A)(:=,t3,A)(:=,B,D)(:=,B,D)()()()()()()(:=,t3,E)(:=,t3,E)第15页，本讲稿共17页循环不变式外提优化循环不变式外提优化 循环的识别：循环的识别：识别循环的入口、重复体、出口部分识别循环的入口、重复体、出口部分 识别方法：识别方法：基于程序文本，基于程序图。基于程序文本，基于程序图。外提对象：外提对象：循环不变式循环不变式 安全性安全性:除法表达式不能外提除法表达式不能外提(除零溢出除零溢出)赋值表达式不能外提赋值表达式不能外提(不一定执行该循环）不一定执行该循环）外提原理：外提原理：定义定义LoopDefLoopDef是在循环体内被定义的变量集合是在循环体内被定义的变量集合;对每层循环记录对每层循环记录LoopDef;LoopDef;若循环体内的多元式若循环体内的多元式(,A,B,t,A,B,t)中的中的A,BA,B不在本不在本 层的层的LoopDefLoopDef中中,则把则把(,A,B,t),A,B,t)外提到循环体外提到循环体 的入口处。的入口处。第16页，本讲稿共17页外提实例外提实例FOR i:=0 TO 9 DOFOR i:=0 TO 9 DO FOR j:=0 TO 9 DOFOR j:=0 TO 9 DOFOR k:=0 TO 9 DO FOR k:=0 TO 9 DO Aijk:=(i Aijk:=(i j)j)k k ENDFORENDFOR ENDFOR 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)(,i,100,t1)(,A,t1,t2)(,j,10,t3)(,t2,t3,t4)(,i,j,t6)(,t4,k,t5)(,t6,k,t7)(,t7,t5)第17页，本讲稿共17页