第09章中间代码优化.ppt

第09章中间代码优化
第1页，共17页，2022年，5月20日，14点5分，星期五
优化的目标：
优化的要求：
优化的对象：深层循环和下标变量地址的计算
优化的种类：
常表达式优化（合并常数项）
公共表达式优化数据流分析。
计算四种集合：
in_c(Bi)：在Bi块的入口处可用的常量定值之集。
out_c(Bi):在Bi块的出口处可用的常量定值之集。
def_c(Bi):在Bi块内产生并且在Bi的出口处可用
的常量定值之集。
kill_c(Bi):被Bi块所杀死的常量定值之集。若Bi
块有对X的赋值，则称Bi块将杀死X的常量定值。
第7页，共17页，2022年，5月20日，14点5分，星期五
def_c(Bi) 和kill_c(Bi)可以确定
out_c(Bi)= (in_c(Bi) – kill_c(Bi))  def_c(Bi)
in_c(Bi)= j∈pre(i) out_c(Bj)
应用in_c(Bi)可以对Bi进行常量表达式优化。
常表达式全局优化原理：
对每一基本块Bi求出in_c(Bi)集合，
其中in_c(B0)为空；
用in_c(Bi)代替基本块Bi的ConstDef；
优化过程同局部常表达式优化原理，
第8页，共17页，2022年，5月20日，14点5分，星期五
x:=1
y:=2
z:=a+1
z:=3
u:=x+5
w:=9
b:=y-1
z:=3
k:=7
m:=k+z
n:=m+1
b:=k+1
d:=m+n
l:=z+y
d:=k+x
x:=1
y:=2
z:=a+1
z:=3
u:=6
w:=9
b:=1
z:=3
k:=7
m:=10
n:=11
b:=8
d:=21
l:=5
d:=8
x:=1
y:=x+1
z:=a+1
z:=3
u:=x+5
w:=6+z
b:=y-1
z:=3
k:=7
m:=k+z
n:=m+1
b:=k+1
d:=m+n
l:=z+y
d:=k+x
1
2
3
4
5
6
第9页，共17页，2022年，5月20日，14点5分，星期五
基于相似性的公共表达式局部优化
相似多元式：设(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: ( , A, B, ti )
...
dk: ( , A, B, tk )
...
第10页，共17页，2022年，5月20日，14点5分，星期五
基于相似性的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的所
有可用表达式代码。
第11页，共17页，2022年，5月20日，14点5分，星期五
优化前
优化后
UE
PAIR
1. ( ×, 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)
(