例 i:=0 0 while i<10 do begin while j<10 do beg in A[i[j]:=A[i[j+A[i][j+1]; j:=j+1 d+ en en d
例 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
第九章中间代码优化 引言 c常量表达式优化 C公共表达式优化 C循环不变式外提
第九章 中间代码优化 引言 常量表达式优化 公共表达式优化 循环不变式外提
优化的目标: 优化的要求: 优化的对象:深层循环和下标变量地址的计算 优化的种类 常表达式优化(合并常数项) 公共表达式优化(消除重复操作) 循环不变表达式外提 削减运算强度等等 优化方法 全局优化:全局信息 局部优化:局部信息
优化的目标： 优化的要求： 优化的对象：深层循环和下标变量地址的计算 优化的种类： 常表达式优化（合并常数项） 公共表达式优化（消除重复操作） 循环不变表达式外提 削减运算强度等等 优化方法： 全局优化：全局信息 局部优化：局部信息
基本块和程序流图 的基本块:单入口单出口的程序段。 程序流图:以基本块为结点的有向图,有向边表示 程序执行的流程。 中间代码基本块的划分: 令初始代码为第一个基本块的入口 令遇转移性中间代码时,结束当前基本块,下一条 代码作为新基本块的入口 令遇标号性代码结束当前基本块,代码本身作为新 基本块的入口。 遇( ASSIG,A,X)时,如果X为引用型形参时结 束当前块,并作为该块的出口
基本块和程序流图 基本块：单入口单出口的程序段。 程序流图：以基本块为结点的有向图，有向边表示 程序执行的流程。 中间代码基本块的划分： ❖ 初始代码为第一个基本块的入口 ❖ 遇转移性中间代码时，结束当前基本块，下一条 代码作为新基本块的入口 ❖ 遇标号性代码结束当前基本块，代码本身作为新 基本块的入口。 ❖ 遇（ASSIG, A, X）时，如果X为引用型形参时结 束当前块，并作为该块的出口
基本块划分的例子 B,:( ASSIGN, 1,Y)B:( LABEL, L6) B,:( LABEL, LO (ADDI, X,Y,t3) B AND, A, b, t) (GT,t3,0,t4) B JUMPO, t, L4 (JUMPO, t4, L8) B3: ASSIGN,0,X)B,: SUBI, X, 1, t5 3 B JUMP, L5 ( ASSIGN, t5, x) B:( LABEL, L4) JUMP, L6) B (ASSIG, 0, Y) B:( LABEL, L8 B:( LABEL, L5) ASSIGN, 0,Z) B 6 ADDI, X,1, t1) STOP B7 B ASSIGN, t1, X suBY 1. t2 程序流图例 ASSIGN, t2, y
基本块划分的例子 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 B3 B4 B5 B6 B7 B8 程序流图例
常表达式局部优化 常表达式:任何时候都取固定常数值的表达式 处理思想:针对每个基本块,如果一个多元式的两 个分量的值已知,则计算其值,并删掉 相应的中间代码。 原理:常量定值表 ConstDef;(Var,Va) 基本块入口置 ConstDef为空 ◆对当前多元式的分量利用 ConstDef表进行值代换; ◆新多元式形如(o,A,B,t):如果A和B是常数, 则计算AωB的值v,并将(t,ν)填入 Cons Def表 形如( ASSIG,A,B):如果A是常数,则把(B,A) 填入 Cons Def表,若已有B项,只需修改其值; 否则从 ConsDefi中删除B的登记项
常表达式局部优化 常表达式：任何时候都取固定常数值的表达式 处理思想：针对每个基本块，如果一个多元式的两 个分量的值已知，则计算其值，并删掉 相应的中间代码。 原理：常量定值表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优化后的代码 (ASSIGN, 1, a( a,1) (ASSIGN, 1, a) b:=a+1(ADDI,a,1,t1)(a,1)(t1,2) (ASS IGN, t1, b)( a, 1)(t1, 2)(b, 2)(ASS IGN, 2, b) a:-X (ASS|GN,x,a)(t1,2)(b,2) (ASSIGN, a, x) c:=b+5(ADD,b,5,t2)(t1,2)(b,2)(t2,7)( ( ASSIGN,t2,c)(t1,2)(b,2)(t2,7)(o,7) (ASSIGN, 7, c)
常表达式局部优化的例子 源程序 中间代码 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)
常量表达式全局优化 思想:可利用基本块外的常量信息进行优化。基本块 入口处的 ConstDe不简单的定义为空,基本块出口 处的 ConstDef还在后面的基本块中用到 问题:计算入口处和出口处的常量定值集合。 方法:用常量定值的数据流分析。 计算四种集合: inc(Bi):在B块的入口处可用的常量定值之集 outc(Bi):在Bi块的出口处可用的常量定值之集。 defc(Bi):在B块内产生并且在B的出口处可用 的常量定值之集。 kill c(Bi):被Bi块所杀死的常量定值之集。若B 块有对X的赋值,则称B块将杀死X的常量定值
常量表达式全局优化 思想：可利用基本块外的常量信息进行优化。基本块 入口处的ConstDef不简单的定义为空，基本块出口 处的ConstDef还在后面的基本块中用到。 问题：计算入口处和出口处的常量定值集合。 方法：用常量定值的数据流分析。 计算四种集合： in_c(Bi)：在Bi块的入口处可用的常量定值之集。 out_c(Bi):在Bi块的出口处可用的常量定值之集。 def_c(Bi):在Bi块内产生并且在Bi的出口处可用 的常量定值之集。 kill_c(Bi):被Bi块所杀死的常量定值之集。若Bi 块有对X的赋值，则称Bi块将杀死X的常量定值
defc(Bi)和 kill c(bi)可以确定 out c(Bi)=(in c(bi-kill c bi))u def c bi inc(Bi)=∩ jEpre(i) out_c(B 应用inc(Bi)可以对B进行常量表达式优化。 常表达式全局优化原理 对每一基本块B求出inc(Bi)集合, 其中inc(B)为空; 用inc(Bi)代替基本块Bi的 ConstDef 优化过程同局部常表达式优化原理
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 X y:=x+1 y:=2 2 z:=a+1 z:=a+1 z:=a+1 3 b: Z b:=1 3 u:=X+5 z:=3 x+5 Z 6 W:=6+z W:=9 W:=9 k:=7 =k+z m:=k+z m:=10 n:=m+1 n:=m+1 6 b:=k+1 zty b::=k+1 :=zty b:=8 l:=5 d: =mtn d: =k+xd:=m+n d:=k+x d:=21 d:=8
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