例
i:=0; j:=0;
while i<10 do
begin
while j<10 do
begin
A[i][j]:=A[i][j]+A[i][j+1];
j:=j+1;
end
i:=i+1;
end
第九章 中间代码优化
?引言
?常量表达式优化
?公共表达式优化
?循环不变式外提
? 优化的目标：
? 优化的要求：
? 优化的对象,深层循环和下标变量地址的计算
? 优化的种类：
常表达式优化（合并常数项）
公共表达式优化（消除重复操作）
循环不变表达式外提
削减运算强度等等
? 优化方法：
全局优化：全局信息
局部优化：局部信息
基本块和程序流图
? 基本块,单入口单出口的程序段。
? 程序流图,以基本块为结点的有向图，有向边表示
程序执行的流程。
? 中间代码基本块的划分：
? 初始代码为第一个基本块的入口
? 遇转移性中间代码时，结束当前基本块，下一条
代码作为新基本块的入口
? 遇标号性代码结束当前基本块，代码本身作为新
基本块的入口。
? 遇（ 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 ) B7:( 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)
B1
B2
B4B3
B5
B6
B8B7
程序流图例
常表达式局部优化
? 常表达式,任何时候都取固定常数值的表达式
? 处理思想,针对每个基本块，如果一个多元式的两
个分量的值已知，则计算其值，并删掉
相应的中间代码。
? 原理,常量定值表 ConstDef,(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的登记项。
常表达式局部优化的例子
源程序 中间代码 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,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还在后面的基本块中用到 。
? 问题,计算入口处和出口处的常量定值集合 。
? 方法,用常量定值的数据流分析 。
计算四种集合：
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)= ?j∈pre(i) out_c(Bj)
应用 in_c(Bi)可以对 Bi进行常量表达式优化 。
常表达式全局优化原理：
对每一基本块 Bi求出 in_c(Bi)集合,
其中 in_c(B0)为空；
用 in_c(Bi)代替基本块 Bi的 ConstDef；
优化过程同局部常表达式优化原理,
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
基于相似性的公共表达式局部优化
? 相似多元式,设 (?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 )
...
基于相似性的 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的所
有可用表达式代码 。
优化前 优化后 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)
( ×,C,B,t1)
(＋,D,t1,t2)
(:=,t2,D)
( )
(＋,D,t1,t4)
(:=,t4,A)
( )
( )
(:=,t4,C)
(×,C,B,t7)
(＋,D,t7,t8)
(:=,t8,A)
{1}
{1,2}
{1}
{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+C× B; A:=D+C× B; C:=D+C× B; A:=D+C× 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的
中间代码 。
基于值编码的优化实例
中间代码 映象 TempEqua UE 优化代码
(×,B,C,t1)
(×,B,C,t2)
(+,t1,t2,t3)
(:=,t3,A)
(:=,B,D)
(×,D,C,t4)
(×,B,C,t5)
(+,t4,t5,t6)
(:=,t6,E)
(1,2,3)
(1,2,3)
(3,3,4)
?(A)=4
?(D)=1
(1,2,3)
(1,2,3)
(3,3,4)
?(E)=4
1
(t2,t1) 1
1,3
..
..
(t4,t1),.
(t5,t1),,
(t6,t3),.
..
(×,B,C,t1)
( )
(+,t1,t1,t3)
(:=,t3,A)
(:=,B,D)
( )
( )
( )
(:=,t3,E)
循环不变式外提优化
? 循环的识别,识别循环的入口、重复体、出口部分
? 识别方法,基于程序文本，基于程序图。
? 外提对象,循环不变式
? 安全性, 除法表达式不能外提 (除零溢出 )
赋值表达式不能外提 (不一定执行该循环）
? 外提原理：
定义 LoopDef是在循环体内被定义的变量集合 ;
对每层循环记录 LoopDef;
若循环体内的多元式 ( ?,A,B,t)中的 A,B不在本
层的 LoopDef中,则把 ( ?,A,B,t)外提到循环体
的入口处。
外提实例
FOR i,=0 TO 9 DO
FOR j,=0 TO 9 DO
FOR k:=0 TO 9 DO
A[i][j][k]:=(i?j)?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 )
( ?,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 )
i:=0; j:=0;
while i<10 do
begin
while j<10 do
begin
A[i][j]:=A[i][j]+A[i][j+1];
j:=j+1;
end
i:=i+1;
end
第九章 中间代码优化
?引言
?常量表达式优化
?公共表达式优化
?循环不变式外提
? 优化的目标：
? 优化的要求：
? 优化的对象,深层循环和下标变量地址的计算
? 优化的种类：
常表达式优化（合并常数项）
公共表达式优化（消除重复操作）
循环不变表达式外提
削减运算强度等等
? 优化方法：
全局优化：全局信息
局部优化：局部信息
基本块和程序流图
? 基本块,单入口单出口的程序段。
? 程序流图,以基本块为结点的有向图，有向边表示
程序执行的流程。
? 中间代码基本块的划分：
? 初始代码为第一个基本块的入口
? 遇转移性中间代码时，结束当前基本块，下一条
代码作为新基本块的入口
? 遇标号性代码结束当前基本块，代码本身作为新
基本块的入口。
? 遇（ 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 ) B7:( 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)
B1
B2
B4B3
B5
B6
B8B7
程序流图例
常表达式局部优化
? 常表达式,任何时候都取固定常数值的表达式
? 处理思想,针对每个基本块，如果一个多元式的两
个分量的值已知，则计算其值，并删掉
相应的中间代码。
? 原理,常量定值表 ConstDef,(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的登记项。
常表达式局部优化的例子
源程序 中间代码 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,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还在后面的基本块中用到 。
? 问题,计算入口处和出口处的常量定值集合 。
? 方法,用常量定值的数据流分析 。
计算四种集合：
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)= ?j∈pre(i) out_c(Bj)
应用 in_c(Bi)可以对 Bi进行常量表达式优化 。
常表达式全局优化原理：
对每一基本块 Bi求出 in_c(Bi)集合,
其中 in_c(B0)为空；
用 in_c(Bi)代替基本块 Bi的 ConstDef；
优化过程同局部常表达式优化原理,
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
基于相似性的公共表达式局部优化
? 相似多元式,设 (?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 )
...
基于相似性的 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的所
有可用表达式代码 。
优化前 优化后 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)
( ×,C,B,t1)
(＋,D,t1,t2)
(:=,t2,D)
( )
(＋,D,t1,t4)
(:=,t4,A)
( )
( )
(:=,t4,C)
(×,C,B,t7)
(＋,D,t7,t8)
(:=,t8,A)
{1}
{1,2}
{1}
{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+C× B; A:=D+C× B; C:=D+C× B; A:=D+C× 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的
中间代码 。
基于值编码的优化实例
中间代码 映象 TempEqua UE 优化代码
(×,B,C,t1)
(×,B,C,t2)
(+,t1,t2,t3)
(:=,t3,A)
(:=,B,D)
(×,D,C,t4)
(×,B,C,t5)
(+,t4,t5,t6)
(:=,t6,E)
(1,2,3)
(1,2,3)
(3,3,4)
?(A)=4
?(D)=1
(1,2,3)
(1,2,3)
(3,3,4)
?(E)=4
1
(t2,t1) 1
1,3
..
..
(t4,t1),.
(t5,t1),,
(t6,t3),.
..
(×,B,C,t1)
( )
(+,t1,t1,t3)
(:=,t3,A)
(:=,B,D)
( )
( )
( )
(:=,t3,E)
循环不变式外提优化
? 循环的识别,识别循环的入口、重复体、出口部分
? 识别方法,基于程序文本，基于程序图。
? 外提对象,循环不变式
? 安全性, 除法表达式不能外提 (除零溢出 )
赋值表达式不能外提 (不一定执行该循环）
? 外提原理：
定义 LoopDef是在循环体内被定义的变量集合 ;
对每层循环记录 LoopDef;
若循环体内的多元式 ( ?,A,B,t)中的 A,B不在本
层的 LoopDef中,则把 ( ?,A,B,t)外提到循环体
的入口处。
外提实例
FOR i,=0 TO 9 DO
FOR j,=0 TO 9 DO
FOR k:=0 TO 9 DO
A[i][j][k]:=(i?j)?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 )
( ?,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 )
