第三节 代码优化
一, 优化的定义
优化是一种等价的，有效的程序变换
?等价 ——不改变程序运行结果
?有效 ——时空效率要高
二, 不同阶段的优化
1,源程序阶段的优化：考虑 DS和算法
2,编译优化 ——中间代码优化和目标代码
优化
3,中间代码优化 ——局部优化和全局优化
?局部优化：在基本块内的优化
?全局优化：超越基本块，在基本块之间的优
化
三, 划分基本块和构造程序流图
1,划分基本块
(1)找入口语句
?程序的第一条语句
?能由条件或无条件转向语句转移到的语
句
?紧跟在条件转向语句后的那个语句
(2)确定基本块
入口语句 入口语句 入口语句
…… …… ……
入口语句 转向语句 停语句
(3)删除未被划入基本块的语句
(1)i:=m-1
(2)j:=n
(3)t1:=4*n
(4)v:=a[t1]
(5)i:=i+1
(6)t2:=4*i
(7)t3:=a[t2]
(8)if t3<v goto (5)
(9)j:=j-1
(10)t4:=4*j
(11)t5:=a[t4]
(12)if t5>v goto (9)
(13)if i>=j goto (23)
(14)t6:=4*i
(15)x:=a[t6]
(16)t7:=4*i
(17)t8:=4*j
(18)t9:=a[t8]
(19)a[t7]:=t9
(20)t10:=4*j
(21)a[t10]:=x
(22)goto (5)
(23)t11:=4*i
(24)x:=a[t11]
(25)t12:=4*i
(26)t13:=4*n
(27)t14:=a[t13]
(28)a[t12]:=t14
(29)t15:=4*n
(30)a[t15]:=x
2,构造流图
G = ( N,E,n0)
(1)基本块集即为结点集 N;
(2)含程序第一个语句的基本块为首结点 n0;
(3)设 Bi,Bj ∈ N, 若满足下列条件之一,
则 Bi ?Bj
?Bj 紧跟在 Bi 之后, 且 Bi 的出口语句不是
无条件转向或停止语句
?Bi 的出口语句为转向语句, 其转向点恰为
Bj 的入口语句
(1)i:=m-1 (2)j:=n
(3)t1:=4*n (4)v:=a[t1]
(5)i:=i+1 (6)t2:=4*i
(7)t3:=a[t2] (8)if t3<v goto (5)
(9)j:=j-1 (10)t4:=4*j
(11)t5:=a[t4] (12)if t5>v goto (9)
(13)if i>=j goto (23)
(14)t6:=4*i (15)x:=a[t6]
(16)t7:=4*i (17)t8:=4*j
(18)t9:=a[t8] (19)a[t7]:=t9
(20)t10:=4*j (21)a[t10]:=x
(22)goto (5)
(23)t11:=4*i (24)x:=a[t11]
(25)t12:=4*i (26)t13:=4*n
(27)t14:=a[t13] (28)a[t12]:=t14
(29)t15:=4*n (30)a[t15]:=x
B1
B2
B3
B4
B5
B6
四, 局部优化
1,合并已知量
2,删除公共子表达式
3,删除死代码
（ a） if 的条件为定值 ;
（ b） 定值后不引用或仅是 A,= A± C
的递归赋值 。
(14)t6:=4*i
(15)x:=a[t6]
(16)t7:=4*i
(17)t8:=4*j
(18)t9:=a[t8]
(19)a[t7]:=t9
(20)t10:=4*j
(21)a[t10]:=x
(22)goto (5)
(14)t6:=4*i
(15)x:=a[t6]
(17)t8:=4*j
(18)t9:=a[t8]
(19)a[t6]:=t9
(21)a[t8]:=x
(22)goto (5)
优化后
例 1
T0, = 3.14
T1, = 2 * T0
T2, = R + r
A, = T1 * T2
B, = A
T3, = 2 * T0
T4, = R + r
T5, = T3 * T4
T6, = R － r
B, = T5 * T6
S1, = R + r
A, = 6.28 * S1
S2, = R － r
B, = A * S2
优化后
例 2
五, 循环优化
1,循环的定义
循环是程序流图中有唯一入口结点
的强连通子图 。
(1)入口结点 子图中满足下列条件的结点 n,
或者 n是流图的首结点,或者在子图外有一
结点 m,它有一有向边 m?n引向结点 n;
(2)强连通子图 。
1
2
3
4
5
6
7 8
9
10
{5,6,7,8,9}是一循环
{4,５ },{２,４｝均不是循环
例,
图 6-3
2,循环的查找
(1)必经结点, 从流图的首结点出发到达结点
n的任一通路都必须经过的结点 d,称为 n的
必经结点, 记为 d DOM n
根据定义可知,
?每个结点是它本身的必经结点, 即 n DOM n
?流图的首结点是流图中任一结点的必经结点,
即 n0 DOM n
例, 图 6 – 3,各结点的必经结点集
D(1)={1}
D(2)={1,2}
D(3)={1,2,3}
D(4)={1,2,4}
D(5)={1,2,4,5}
D(6)={1,2,4,5,6}
D(7)={1,2,4,5,6,7}
D(8)={1,2,4,5,6,8}
D(9)={1,2,4,5,6,9}
D(10)={1,2,4,10}
(2)回边：流图 G=(N,E,n0)中的有向边
n?d,如果 d是 n的必经结点,即 d∈ D(n),则
称 n?d为流图的一条回边 。
例, 图 6-3中有三条回边
5?4,9?5,10?2
(3)由回边组成的循环,若 n?d是流图 G= (N，
E,ｎ 0)的一条回边, M是流图中有通路到
达 n而该通路不经过 d的结点集,则
Loop= {n,d}∪ M
组成了 G的一个子图,称为由回边 n?d组成
的自然循环 。
图 6-3中,5?4 组成 {5,4,6,7,8,9}
9?5 组成 {9,5,6,7,8}
10?2 组成 {10,2,3,4,5,6,7,8,9}
3,循环优化
(1)代码外提
(2)强度削弱
?基本归纳变量, i有唯一定值, i,= i ?c
?同族归纳变量, j,= c1 ? i ? c2
则变成 j,= j ? c1 ? c,但 j必须在循环外赋初
值 j,＝ c1 * i ? c2
(3)删除归纳变量
即改用同族归纳变量作为判断条件
例如将 i > 10 改为 t3 > 100 + t1
因原来 t3,= 10 * i + t1,
而 100 ＋ t1 即 10 * 10 + t1
(1)i:=1
(2)if i>10 goto (16)
(3)t1:=2*j (4)t2:=10*i
(5)t3:=t2+t1 (6)t4:=a0-11
(7)t5:=2*j (8)t6:=10*i
(9)t7:=t6+t5 (10)t8:=a0-11
(11)t9:=t8[t7] (12)t10:=t9+1
(13)t4[t3]:=t10 (14)i:=i+1
(15)goto (2)
(16) …..,
优化之前 B1
B2
B3
B4
(1)i:=1
(4)t2:=10*i (5)t3:=t2+t1
(8)t6:=10*i (9)t7:=t6+t5
(11)t9:=t8[t7] (12)t10:=t9+1
(13)t4[t3]:=t10 (14)i:=i+1
(15)goto (2)
(16) …..,
(2)if i>10 goto (16)
(3)t1:=2*j (6)t4:=a0-11
(7)t5:=2*j (10)t8:=a0-11
代码外提后
B1
B2’
B2
B3
B4
(1)i:=1
(11)t9:=t8[t7] (12)t10:=t9+1
(13)t4[t3]:=t10 (14)i:=i+1
(4’)t2:=t2+10 (8’)t6:=t6+10
(5’)t3:=t3+10 (9’)t7:=t7+10
(15)goto (2)
(16) …..,
(2)if i>10 goto (16)
(3)t1:=2*j (6)t4:=a0-11
(7)t5:=2*j (10)t8:=a0-11
(4)t2:=10*i (8)t6:=10*i
(5)t3:=t2+t1 (9)t7:=t6+t5
强度削弱后 B1
B2’
B2
B3
B4
(1)i:=1
(11)t9:=t8[t7] (12)t10:=t9+1
(13)t4[t3]:=t10 (4’)t2:=t2+10
(8’)t6:=t6+10 (5’)t3:=t3+10
(9’)t7:=t7+10 (15)goto (2)
(16) …..,
(2’’)if t3>s goto (16)
(3)t1:=2*j (6)t4:=a0-11
(7)t5:=2*j (10)t8:=a0-11
(4)t2:=10*i (8)t6:=10*i
(5)t3:=t2+t1 (9)t7:=t6+t5
(2’)s:=100+t1
删除归纳变量后 B1
B2’
B2
B3
B4
另例,(1)PROD,= 0
(2)I,= 1
(3)T1,= 4 * I
(4)T2,= a0 – 4
(5)T3,= T2[T1]
(6)T4,= 4 * I
(7)T5,= b0 – 4
(8)T6,= T5[T4]
(9)T7,= T3 * T6
(10)PROD,= PROD + T7
(11)I,= I + 1
(12)if I ≤ 20 goto (3)
进行,(1)删除多余运算, 代码外提
(2)强度削弱
(3)变换循环控制条件, 复写传播, 合并已知量
(4)删除无用赋值
删除多余运算, 代码外提
(1)PROD,= 0
(2)I,= 1
(4)T2,= a0 – 4
(7) T5,= b0 – 4
(3) T1,= 4 * I
(5)T3,= T2[T1]
(6)T4,= T1
(8) T6,= T5[T4]
(9) T7,= T3 * T6
(10) PROD,= PROD + T7
(11) I,= I +1
(12)if I≤ 20 goto (3)
强度削弱
(1)PROD,= 0
(2)I,= 1
(4)T2,= a0 – 4
(7) T5,= b0 – 4
(3) T1,= 4 * I
(5)T3,= T2[T1]
(6)T4,= T1
(8) T6,= T5[T4]
(9) T7,= T3 * T6
(10) PROD,= PROD + T7
(11) I,= I +1
(3’)T1,= T1 + 4
(12) if I ≤ 20 goto (5)
变换循环控制条件, 合并已知量, 复写传播
(1)PROD,= 0
(2)I,= 1
(4)T2,= a0 – 4
(7) T5,= b0 – 4
(3) T1,= 4
(5)T3,= T2[T1]
(6)T4,= T1
(8) T6,= T5[T1]
(9) T7,= T3 * T6
(10) PROD,= PROD + T7
(11) I,= I +1
(3’)T1,= T1 + 4
(12) if T1 ≤ 80 goto (5)
删除无用赋值
(1)PROD,= 0
(4)T2,= a0 – 4
(7) T5,= b0 – 4
(3) T1,= 4
(5)T3,= T2[T1]
(8) T6,= T5[T4]
(9) T7,= T3 * T6
(10) PROD,= PROD + T7
(3’)T1,= T1 + 4
(12)if T1 ≤ 80 goto (5)
第四节 代码生成
1,代码生成的任务
将中间代码翻译成等价有效的目标代码
2,代码生成器的输入
中间代码，符号表
3,代码生成器的输出
目标代码 —— 绝对机器代码，可重定
位代码或汇编码
4,抽象机的指令形式
op 源, 目的
其中 op是操作码, 源和目的是两个操作对象,
可以是内存地址, 寄存器或常数
（ 1） 直接地址型
op Ri,M (Ri) op (M) => Ri
（ 2） 寄存器型
op Ri,Rj (Ri) op (Rj) => Ri
（ 3） 变址型
op Ri,C(Rj) (Ri) op ((Rj) + C) => Ri
（ 4） 间接型
op Ri,*Rj (Ri) op ((Rj)) => Ri
op Ri,*M (Ri) op ((M)) => Ri
op Ri,*C(Rj) (Ri) op (((Rj) + C)) => Ri
（ 5） 其他几种常用指令
MOV Ri,M (Ri) => M
MOV M,Ri (M) => Ri
J x goto x
CMP A,B 比较 A 和 B, 设定 CJ
A < B 设 C J = 0
A = B 设 C J = 1
A > B 设 C J = 2
J rop x rop 与 C J 一致时, goto x
否则顺序执行下一指令
5,简单的代码生成方法
(1)p,x:= y op z 的翻译
MOV y,Ri
op Ri,z
结果 （ x 的值 ） 在寄存器 Ri中
(2)为 x 分配寄存器的方法
?y 本身占有寄存器 Ri，且 y在 p点后不再被
引用
?有空余的可用寄存器 Ri
?寄存器均被占用：保存副本，选择一
个 ——最好选择占用 Ri的变量在主存中已
有副本的；或者在 p点后该变量不再被引
用的；或者在离 p点最远处才被引用的。
举例,t,= a － b MOV a,R0
u,= a + c SUB R0,b
v,= a － t 翻译成 MOV a,R1
w,= v + u ADD R1,c
假设可用寄存器为 R0,R1 MOV R1,u
MOV a,R1
SUB R1,R0
MOV R1,v
ADD R1,u
6,循环中的寄存器的分配
(1)指令的执行代价
—— 该指令访问主存的次数
寄存器型 op Ri,Rj 执行代价为 1
直接地址型 op Ri,M 执行代价为 2
变址型 op Ri,C(Rj) 执行代价为 2
间址型 op Ri,*Rj 执行代价为 2
op Ri,*M 执行代价为 3
op Ri,*C(Rj) 执行代价为 3
(2)循环中某变量被固定分配了寄存器
后, 两种节省执行代价的情形,
(I)设 USE ( x,B ) 为 x在 B 中被定值前
的引用次数, 则循环 L执行一次, 可
省的执行代价为
?USE(x,B) B?L
(II)对基本块中定值基本块后的活跃变
量 x,省去指令 MOV Ri,Mx,可省
执行代价
?(2*LIVE(x,B))
由 （ I）,(II) 可得, 总共省的执行代价
?(USE(x,B)+2*LIVE(x,B))
B?L
B?L
a:=b+c
d:=d-b
e:=a+f
f:=a-d b:=d+f
e:=a-c
b:=d+c
acdef
cdef
bcdef
bcdef
B1
B2 B3
B4
B1
B2
B3
B4
?
a b c d e f
1
1
2 2
2
2
1
1
1
1
1
1
1
2 2
2
1
2
1
4 6 3 6 4 4
若有三个可固定分配的寄存器,则 b,d可固定分配寄存器,
另一个分配给 a,e,f中的一个
一, 优化的定义
优化是一种等价的，有效的程序变换
?等价 ——不改变程序运行结果
?有效 ——时空效率要高
二, 不同阶段的优化
1,源程序阶段的优化：考虑 DS和算法
2,编译优化 ——中间代码优化和目标代码
优化
3,中间代码优化 ——局部优化和全局优化
?局部优化：在基本块内的优化
?全局优化：超越基本块，在基本块之间的优
化
三, 划分基本块和构造程序流图
1,划分基本块
(1)找入口语句
?程序的第一条语句
?能由条件或无条件转向语句转移到的语
句
?紧跟在条件转向语句后的那个语句
(2)确定基本块
入口语句 入口语句 入口语句
…… …… ……
入口语句 转向语句 停语句
(3)删除未被划入基本块的语句
(1)i:=m-1
(2)j:=n
(3)t1:=4*n
(4)v:=a[t1]
(5)i:=i+1
(6)t2:=4*i
(7)t3:=a[t2]
(8)if t3<v goto (5)
(9)j:=j-1
(10)t4:=4*j
(11)t5:=a[t4]
(12)if t5>v goto (9)
(13)if i>=j goto (23)
(14)t6:=4*i
(15)x:=a[t6]
(16)t7:=4*i
(17)t8:=4*j
(18)t9:=a[t8]
(19)a[t7]:=t9
(20)t10:=4*j
(21)a[t10]:=x
(22)goto (5)
(23)t11:=4*i
(24)x:=a[t11]
(25)t12:=4*i
(26)t13:=4*n
(27)t14:=a[t13]
(28)a[t12]:=t14
(29)t15:=4*n
(30)a[t15]:=x
2,构造流图
G = ( N,E,n0)
(1)基本块集即为结点集 N;
(2)含程序第一个语句的基本块为首结点 n0;
(3)设 Bi,Bj ∈ N, 若满足下列条件之一,
则 Bi ?Bj
?Bj 紧跟在 Bi 之后, 且 Bi 的出口语句不是
无条件转向或停止语句
?Bi 的出口语句为转向语句, 其转向点恰为
Bj 的入口语句
(1)i:=m-1 (2)j:=n
(3)t1:=4*n (4)v:=a[t1]
(5)i:=i+1 (6)t2:=4*i
(7)t3:=a[t2] (8)if t3<v goto (5)
(9)j:=j-1 (10)t4:=4*j
(11)t5:=a[t4] (12)if t5>v goto (9)
(13)if i>=j goto (23)
(14)t6:=4*i (15)x:=a[t6]
(16)t7:=4*i (17)t8:=4*j
(18)t9:=a[t8] (19)a[t7]:=t9
(20)t10:=4*j (21)a[t10]:=x
(22)goto (5)
(23)t11:=4*i (24)x:=a[t11]
(25)t12:=4*i (26)t13:=4*n
(27)t14:=a[t13] (28)a[t12]:=t14
(29)t15:=4*n (30)a[t15]:=x
B1
B2
B3
B4
B5
B6
四, 局部优化
1,合并已知量
2,删除公共子表达式
3,删除死代码
（ a） if 的条件为定值 ;
（ b） 定值后不引用或仅是 A,= A± C
的递归赋值 。
(14)t6:=4*i
(15)x:=a[t6]
(16)t7:=4*i
(17)t8:=4*j
(18)t9:=a[t8]
(19)a[t7]:=t9
(20)t10:=4*j
(21)a[t10]:=x
(22)goto (5)
(14)t6:=4*i
(15)x:=a[t6]
(17)t8:=4*j
(18)t9:=a[t8]
(19)a[t6]:=t9
(21)a[t8]:=x
(22)goto (5)
优化后
例 1
T0, = 3.14
T1, = 2 * T0
T2, = R + r
A, = T1 * T2
B, = A
T3, = 2 * T0
T4, = R + r
T5, = T3 * T4
T6, = R － r
B, = T5 * T6
S1, = R + r
A, = 6.28 * S1
S2, = R － r
B, = A * S2
优化后
例 2
五, 循环优化
1,循环的定义
循环是程序流图中有唯一入口结点
的强连通子图 。
(1)入口结点 子图中满足下列条件的结点 n,
或者 n是流图的首结点,或者在子图外有一
结点 m,它有一有向边 m?n引向结点 n;
(2)强连通子图 。
1
2
3
4
5
6
7 8
9
10
{5,6,7,8,9}是一循环
{4,５ },{２,４｝均不是循环
例,
图 6-3
2,循环的查找
(1)必经结点, 从流图的首结点出发到达结点
n的任一通路都必须经过的结点 d,称为 n的
必经结点, 记为 d DOM n
根据定义可知,
?每个结点是它本身的必经结点, 即 n DOM n
?流图的首结点是流图中任一结点的必经结点,
即 n0 DOM n
例, 图 6 – 3,各结点的必经结点集
D(1)={1}
D(2)={1,2}
D(3)={1,2,3}
D(4)={1,2,4}
D(5)={1,2,4,5}
D(6)={1,2,4,5,6}
D(7)={1,2,4,5,6,7}
D(8)={1,2,4,5,6,8}
D(9)={1,2,4,5,6,9}
D(10)={1,2,4,10}
(2)回边：流图 G=(N,E,n0)中的有向边
n?d,如果 d是 n的必经结点,即 d∈ D(n),则
称 n?d为流图的一条回边 。
例, 图 6-3中有三条回边
5?4,9?5,10?2
(3)由回边组成的循环,若 n?d是流图 G= (N，
E,ｎ 0)的一条回边, M是流图中有通路到
达 n而该通路不经过 d的结点集,则
Loop= {n,d}∪ M
组成了 G的一个子图,称为由回边 n?d组成
的自然循环 。
图 6-3中,5?4 组成 {5,4,6,7,8,9}
9?5 组成 {9,5,6,7,8}
10?2 组成 {10,2,3,4,5,6,7,8,9}
3,循环优化
(1)代码外提
(2)强度削弱
?基本归纳变量, i有唯一定值, i,= i ?c
?同族归纳变量, j,= c1 ? i ? c2
则变成 j,= j ? c1 ? c,但 j必须在循环外赋初
值 j,＝ c1 * i ? c2
(3)删除归纳变量
即改用同族归纳变量作为判断条件
例如将 i > 10 改为 t3 > 100 + t1
因原来 t3,= 10 * i + t1,
而 100 ＋ t1 即 10 * 10 + t1
(1)i:=1
(2)if i>10 goto (16)
(3)t1:=2*j (4)t2:=10*i
(5)t3:=t2+t1 (6)t4:=a0-11
(7)t5:=2*j (8)t6:=10*i
(9)t7:=t6+t5 (10)t8:=a0-11
(11)t9:=t8[t7] (12)t10:=t9+1
(13)t4[t3]:=t10 (14)i:=i+1
(15)goto (2)
(16) …..,
优化之前 B1
B2
B3
B4
(1)i:=1
(4)t2:=10*i (5)t3:=t2+t1
(8)t6:=10*i (9)t7:=t6+t5
(11)t9:=t8[t7] (12)t10:=t9+1
(13)t4[t3]:=t10 (14)i:=i+1
(15)goto (2)
(16) …..,
(2)if i>10 goto (16)
(3)t1:=2*j (6)t4:=a0-11
(7)t5:=2*j (10)t8:=a0-11
代码外提后
B1
B2’
B2
B3
B4
(1)i:=1
(11)t9:=t8[t7] (12)t10:=t9+1
(13)t4[t3]:=t10 (14)i:=i+1
(4’)t2:=t2+10 (8’)t6:=t6+10
(5’)t3:=t3+10 (9’)t7:=t7+10
(15)goto (2)
(16) …..,
(2)if i>10 goto (16)
(3)t1:=2*j (6)t4:=a0-11
(7)t5:=2*j (10)t8:=a0-11
(4)t2:=10*i (8)t6:=10*i
(5)t3:=t2+t1 (9)t7:=t6+t5
强度削弱后 B1
B2’
B2
B3
B4
(1)i:=1
(11)t9:=t8[t7] (12)t10:=t9+1
(13)t4[t3]:=t10 (4’)t2:=t2+10
(8’)t6:=t6+10 (5’)t3:=t3+10
(9’)t7:=t7+10 (15)goto (2)
(16) …..,
(2’’)if t3>s goto (16)
(3)t1:=2*j (6)t4:=a0-11
(7)t5:=2*j (10)t8:=a0-11
(4)t2:=10*i (8)t6:=10*i
(5)t3:=t2+t1 (9)t7:=t6+t5
(2’)s:=100+t1
删除归纳变量后 B1
B2’
B2
B3
B4
另例,(1)PROD,= 0
(2)I,= 1
(3)T1,= 4 * I
(4)T2,= a0 – 4
(5)T3,= T2[T1]
(6)T4,= 4 * I
(7)T5,= b0 – 4
(8)T6,= T5[T4]
(9)T7,= T3 * T6
(10)PROD,= PROD + T7
(11)I,= I + 1
(12)if I ≤ 20 goto (3)
进行,(1)删除多余运算, 代码外提
(2)强度削弱
(3)变换循环控制条件, 复写传播, 合并已知量
(4)删除无用赋值
删除多余运算, 代码外提
(1)PROD,= 0
(2)I,= 1
(4)T2,= a0 – 4
(7) T5,= b0 – 4
(3) T1,= 4 * I
(5)T3,= T2[T1]
(6)T4,= T1
(8) T6,= T5[T4]
(9) T7,= T3 * T6
(10) PROD,= PROD + T7
(11) I,= I +1
(12)if I≤ 20 goto (3)
强度削弱
(1)PROD,= 0
(2)I,= 1
(4)T2,= a0 – 4
(7) T5,= b0 – 4
(3) T1,= 4 * I
(5)T3,= T2[T1]
(6)T4,= T1
(8) T6,= T5[T4]
(9) T7,= T3 * T6
(10) PROD,= PROD + T7
(11) I,= I +1
(3’)T1,= T1 + 4
(12) if I ≤ 20 goto (5)
变换循环控制条件, 合并已知量, 复写传播
(1)PROD,= 0
(2)I,= 1
(4)T2,= a0 – 4
(7) T5,= b0 – 4
(3) T1,= 4
(5)T3,= T2[T1]
(6)T4,= T1
(8) T6,= T5[T1]
(9) T7,= T3 * T6
(10) PROD,= PROD + T7
(11) I,= I +1
(3’)T1,= T1 + 4
(12) if T1 ≤ 80 goto (5)
删除无用赋值
(1)PROD,= 0
(4)T2,= a0 – 4
(7) T5,= b0 – 4
(3) T1,= 4
(5)T3,= T2[T1]
(8) T6,= T5[T4]
(9) T7,= T3 * T6
(10) PROD,= PROD + T7
(3’)T1,= T1 + 4
(12)if T1 ≤ 80 goto (5)
第四节 代码生成
1,代码生成的任务
将中间代码翻译成等价有效的目标代码
2,代码生成器的输入
中间代码，符号表
3,代码生成器的输出
目标代码 —— 绝对机器代码，可重定
位代码或汇编码
4,抽象机的指令形式
op 源, 目的
其中 op是操作码, 源和目的是两个操作对象,
可以是内存地址, 寄存器或常数
（ 1） 直接地址型
op Ri,M (Ri) op (M) => Ri
（ 2） 寄存器型
op Ri,Rj (Ri) op (Rj) => Ri
（ 3） 变址型
op Ri,C(Rj) (Ri) op ((Rj) + C) => Ri
（ 4） 间接型
op Ri,*Rj (Ri) op ((Rj)) => Ri
op Ri,*M (Ri) op ((M)) => Ri
op Ri,*C(Rj) (Ri) op (((Rj) + C)) => Ri
（ 5） 其他几种常用指令
MOV Ri,M (Ri) => M
MOV M,Ri (M) => Ri
J x goto x
CMP A,B 比较 A 和 B, 设定 CJ
A < B 设 C J = 0
A = B 设 C J = 1
A > B 设 C J = 2
J rop x rop 与 C J 一致时, goto x
否则顺序执行下一指令
5,简单的代码生成方法
(1)p,x:= y op z 的翻译
MOV y,Ri
op Ri,z
结果 （ x 的值 ） 在寄存器 Ri中
(2)为 x 分配寄存器的方法
?y 本身占有寄存器 Ri，且 y在 p点后不再被
引用
?有空余的可用寄存器 Ri
?寄存器均被占用：保存副本，选择一
个 ——最好选择占用 Ri的变量在主存中已
有副本的；或者在 p点后该变量不再被引
用的；或者在离 p点最远处才被引用的。
举例,t,= a － b MOV a,R0
u,= a + c SUB R0,b
v,= a － t 翻译成 MOV a,R1
w,= v + u ADD R1,c
假设可用寄存器为 R0,R1 MOV R1,u
MOV a,R1
SUB R1,R0
MOV R1,v
ADD R1,u
6,循环中的寄存器的分配
(1)指令的执行代价
—— 该指令访问主存的次数
寄存器型 op Ri,Rj 执行代价为 1
直接地址型 op Ri,M 执行代价为 2
变址型 op Ri,C(Rj) 执行代价为 2
间址型 op Ri,*Rj 执行代价为 2
op Ri,*M 执行代价为 3
op Ri,*C(Rj) 执行代价为 3
(2)循环中某变量被固定分配了寄存器
后, 两种节省执行代价的情形,
(I)设 USE ( x,B ) 为 x在 B 中被定值前
的引用次数, 则循环 L执行一次, 可
省的执行代价为
?USE(x,B) B?L
(II)对基本块中定值基本块后的活跃变
量 x,省去指令 MOV Ri,Mx,可省
执行代价
?(2*LIVE(x,B))
由 （ I）,(II) 可得, 总共省的执行代价
?(USE(x,B)+2*LIVE(x,B))
B?L
B?L
a:=b+c
d:=d-b
e:=a+f
f:=a-d b:=d+f
e:=a-c
b:=d+c
acdef
cdef
bcdef
bcdef
B1
B2 B3
B4
B1
B2
B3
B4
?
a b c d e f
1
1
2 2
2
2
1
1
1
1
1
1
1
2 2
2
1
2
1
4 6 3 6 4 4
若有三个可固定分配的寄存器,则 b,d可固定分配寄存器,
另一个分配给 a,e,f中的一个
