1
第 9章 目标代码生成
目标代码生成是把语法分析优化后的中间代码变换成目标
代码 。 目标代码的形式主要包括如下 3种形式,
1,具有绝对地址的机器语言程序 。 能立即执行的机器语言
代码, 主程序与子程序需要同时编译 。
2,可浮动的机器语言程序 。 目标程序由若干个目的模块组
成, 各模块包含目标程序的一部分代码, 这些代码可在存
储空间浮动, 装入到存储空间的任何位置 。 需要连接装入
程序把它们和某些运行程序连接起来才能运行 。
3,汇编语言形式的程序 。 尚须经过汇编程序汇编, 转换成
可执行的机器语言代码 。
2
基本块
? 所谓基本块是指按顺序执行 （ 不含分支结构 ）
的中间代码 （ 四元式 ） 序列, 其中只有一个入
口和一个出口, 入口是第一个操作, 出口是最
后一个操作 。
– 对于基本块来说, 执行只能从其入口进入, 出口退
出 。
– 对于一个中间代码序列, 可以把它划分为一系列的
基本块,在各基本块范围内, 进行代码优化以及目
标代码生成 。
3
基本块划分的算法
1,求出程序中各个基本块的入口语句, 它们是,
(1) 程序的第一个语句, 或
(2) 能由条件转移语句或无条件转移语句转移到的语句, 或
(3) 紧跟在条件转移语句或无条件转移语句后面的语句,
2,对求出的每一入口语句, 构造其所属的基本块
（ 即找出口语句 ） 由该入口语句到,
(1) 下一入口语句 或到
(2) 转移语句 或到
(3) 停语句 之间的语句序列组成一个基本块 。
3,凡未被纳入某一基本块的语句, 都是程序中控制流无法到
达的语句, 可从程序中删除 。
4
§ 9.2 一个假想的计算机模型
? 以字节编址, 主存容量为 216个字节, 机器字长为 16bit,
有 8个通用寄存器,R0,R1,…,R7,且长度也为 16bit。
每条指令占用一个机器字, 形式如下,
OP arc,dst
OP表示操作码，占 4bit； arc和 dst分别表示源操作数
和目的操作数的地址，各占 6bit。
由于 6bit不能对整个内存空间进行寻址，因此将操作
数或其地址存放在紧跟指令之后的单元中。
5
6
常用指令
1,传送指令, MOV arc,dst (arc)?dst
2,运算指令,ADD arc,dst (dst)+(arc) ?dst
SUB arc,dst (dst)-(arc)?dst
3,比较指令,CMP arc,dst
执行 arc-dst，并对状态字 PSW相应的标志位置位。
当 (arc)=(dst)时,PSW的标志位 Z置 1。
当 (arc)<(dst)时,PSW的标志位 N置 1。
当 (arc)>(dst)时,PSW的标志位 P置 1。
4,控制指令,
{BR,j<,j?,j=,j?} dst,分别表示无条件,N=1,N?Z=1,Z=1
和 Z=0转移。
7
常用四元式的的目标代码
1,四元式 （ +,A,B,T） 对
应的指令为,
MOV A,R0；
ADD B,R0；
MOV R0,T；
其余二元操作四元式的翻译
与此类拟；
2,四元式 （ =,B,—,A） 对
应的指令为,
MOV B,R0；
MOV R0,A；
3,四元式 （ jnZ,A,—,P）
对应的指令为,
MOV A,R0；
CMP R0,0;
j? P’；
4,四元式 （ J,—,—,P） 对
应的指令为,BR P’；
5,四元式 （ Jrop,A,B,P）
对应的指令为
MOV A,R0；
CMP R0,B；
Jrop P’；
8
四元式目标地址的确定
（ 1）在把四元式翻译为目标指令时，是按四元式表中
四元式的顺序依次执行，为计算每个四元式所对应
的目标地址，必须累计每条指令的字节数。到达某
四元式时，所累计的字节数就是该四元式的目标地
址（相对的）。
（ 2）转移语句中转移地址所指的四元式是基本块的入
口语句，把这种语句按出现的顺序生成汇编代码标
号 L1,L2 …..,等，并用一张标号表存放起来,表格内
容为四元式序号与对应汇编代码标号。
9
§ 9.3 代码生成程序的雏形
? 为每个基本块的生成高质量代码,
– 总的指令条数要少；
– 尽可能利用寄存器, 少产生访问内存的指令, 为
此需要充分合理的利用寄存器,
? 尽可能把后面还要引用的变量仍保存在寄存器中；
? 应把不再使用的变量所占用的寄存器及时释放掉；
? 为此需引入两个概念：基本块内变量的引用信息和
活跃信息 。
10
引用信息与活跃信息
? 如果变量 A在某点 P的值 （ P是四元式的编号 ） 在从 P可
达的某四元式 q中被引用, 则称变量 A在 P点是 活跃的,
并称四元式 q是变量 A的 引用信息 。
(p) A=B+C; A在 P点是 活跃的
(r) E=A+F;
…,,
(q) D=A+V; q是变量 A的 引用信息
假定
①所有的临时变量均看作是出基本块后的非活跃变量。
②所有的非临时变量都看作是出基本块后的活跃变量。
11
基本块内的引用信息链和活跃信息链
1,数据结构,为四元式中的每个变量设置引用信息栏和
活跃信息栏, 在符号表中也增设引用信息栏和活跃信
息栏, 用于暂存各变量的引用与活跃信息, 临时变量
也如此 。
例：四元式的引用信息与活跃信息表示法
序号 四元式 结果 左变量 右变量
i (op,B,C,A) (引用,活跃） (引用,活跃） (引用,活跃）
i+1 (op,A,C,T) (引用,活跃） (引用,活跃） (引用,活跃）
12
算法
（ 1） 从基本块出口向入口方向逐个扫描每个四元式, 根据
每个变量的引用和定值情况建立各变量的引用和活跃信
息链 。
（ 2） 用 （ U,L） 表示引用 （ U） 与活跃 （ L） 信息 。
用 N表示不引用或不活跃；用 Y表示活跃, 四元式编号
表示下一个引用位置 。
（ 3） 用 FIRST和 LAST分别表示基本块的入口, 出口的语句
号 。
（ 4） 计算基本块各变量引用信息和活跃信息的算法 NEXT-
USE如下 （ 设四元式 （ OP,B,C,A））
13
Procedure NEXT-USE（ FIRST,LAST） ；
把符号表中每个变量的引用栏初始化为 N,
并把每个变量是否活跃的标记填入符号表的活跃栏内；
for I= LAST to FIRST do
begin GET(QUAD) (i) A=B+C
把符号表中 A的 （ U,L） 附加到四元式中的 A上；
让符号表中 A的 （ U,L） =（ ‘ N’,‘ N’） ；
把符号表中 B和 C的 （ U,L） 附加到四元式中的 B和 C上；
让符号表中 B的 （ U,L） =（ i,‘ Y’） ；
让符号表中 C的 （ U,L） =（ i,‘ Y’） ；
end
end;
14
四元式的附加信息
序
号
四元式 结果 左变
量
右变
量
１ (－,A,B,T) (5,Y) (2,Y) (2,Y)
２ (+,A,B,A) (3,Y) (N,N) (5,Y)
３ (－,A,C,U) (6,Y) (N,Y) (4,Y)
４ (+,C,D,V) (N,N) (N,Y) (N,Y)
５ (+,T,B,V) (6,Y) (N,N) (N,Y)
６ (+,V,U,W) (N,Y) (N,Y) (N,Y)
A (N,Y)→(3,Y)→(N,N)→(2,Y)→(1,Y)
B (N,Y)→(5,Y)→(2,Y)→ (1,Y)
T (N,N)→(5,Y)→(N,N)
C (N,Y)→(4,Y)→(3,Y)
U (N,Y)→(6,Y)→(N,N)
D (N,Y)→(4,Y)
V (N,Y)→(6,Y)→(N,N)→(N,N)
W (N,Y)→(N,N)
符号表的变化情况
15
寄存器的分配问题
1,描述寄存器分配信息的数据结构,
VAR栏表示把寄存器分配给哪个变量或哪些变量 （ 复写 ）
（ A,=B）
MEM栏表示占用 R的哪几个变量的值也在内存中
2、寄存器分配信息的描述结构
R VAR MEM
R0
R1
…
R7
16
寄存器分配算法
? 一般在生成四元式 A:=B OP C的代码中, 通常把左操作
数 B取到寄存器 R中, 再和 C操作 （ C可在内存中, 也可
在寄存中 ）, R中的结果就是 A的值, 或者说 A占用了 R,
? 寄存器的分配可以用 RGEREG（ QUAD,R） 实现, QUAD是
待分配寄存器的四元式,i,A:=B OP C,(OP,B,C,A)；
R是分配的寄存器 。
（ 算法需查看附在四元式 i上的活跃与引用信息及上表中
的结构 ）
17
为变量 A分配寄存器的算法应遵循以下原则 （ A:=B OP C）,
（ 1） 如果 B已在寄存器 Ri中 （ VAR（ Ri））,且以后不再引
用 （ 查四元式的 i的附加信息, B（ N,N） 为, 非活跃,
和, 非引用, ）, 则选择 Ri.(因为最后 Ri中存的是 A)。
（ 2） 从空闲寄存器中选一 Ri。
（ 3） 从已分配寄存器中选取其值在最远的将来才会使用的
寄存器 Ri（ 查四元式的附加信息 ）, 如果 Ri中的内容不在
内存中 （ 查 MEM（ Ri））, 则要生成一条存数指令
（ MOV Ri,M） 把 Ri中内容存入 M单元 。
18
基本块的代码生成算法
算法中使用以下过程,
（ 1） ADDR（ B）,获的变量 B当前存放的地方, 只
要 B在寄存器中就返回 R,否则 B在内存中 。
（ 2） FILL（ B,R）,如果变量 B不在 VAR（ R） 中,
则填入；如果 B同时又在内存中, 则把 B填入
MEM（ R） 中 。
（ 3） EMIT（ OP R,X）,向目标文件 QBJ中输出一
条指令 OP R,X。
（ 4） DELETE（ B,R）,如果 B在 VAR（ R） 和 MEM
（ R） 中的活, 则删除其中的 B。
19
算法 GENOBJ的一般描述如下,
输入,QUAD中的四元式 i,A=B OP C
输出：四元式 i的目标代码, 并将其存入目标文件 OBJ
PROCEDURE GENOBJ(QUAD);
BEGIN /*QUAD中的四元式形成 i,A=B OP C */
GETREG（ QUAD,R） ;
IF ADDR（ B） ≠ R THEN
BEGIN EMIT (MOV ADDR(B),R);
EMIT(OP ADDR(C),R);
END
ELSE
BEGIN EMIT (OP ADDR(C),R);
DELETE(B,R);
END
20
FILL(A,R);
for 每个 Rk≠R do DELETE(A,Rk);
for 每个 Rk do
begin if B(i)=(N,N) then Delete (B,Rk)
if C(i)=(N,N) then Delete (C,Rk)
end
end
算法中第一个 for语句保证 A只占有 R,
第二个 for语句释放非活跃跃和非引用变量 B与 C所占用的
寄存器 。
21
例：对以下四元式利用 GENOBJ产生目标代码,假定只有 R0
和 R1两个寄存器可用 。
四元式 R0 R1 QBJ
（ 1） （ -,A,B,T） T （ 1） MOV A,R0；
（ 2） SUB B,R0；
（ 2） （ +,A,B,A） A （ 3） MOV A,R1；
（ 4） ADD B,R1；
（ 3） （ -,A,C,U） U （ 5） SUB C,R1；
（ 4） （ +,C,D,V） V （ 6） MOV R1,U；
（ 7） MOV C,R1；
（ 8） ADD D,R1；
（ 5） （ +,T,B,V） V 空 （ 9） ADD B,R0；
（ 6） （ +,V,U,W） W (10） MOV R0,R1；
（ 11） ADD U,R1；
（ 12） MOV R1,W;
（ 13） MOV R0,V；
22
对算法 GENOBJ还可进一步改进, 如果按照程序控
制流程图去生成每一个基本块的目标代码, 那么在出
基本块的时候, 可以把该基本的寄存器占用情况保留
到下一基本块 。 在下一基本块中应尽量利用在寄存器
的变量值, 这样在每个基本块出口时, 可以不存贮每
个活跃变量的值 。
利用上术基本块的目标代码生成算法, 按此种顺序
所产生的目标代码, 其有效性末必是最佳的, 我们还
可以利用基本块的 DAG表示来重构基本块以改变基本
块的运行次序, 从而得到更有效的目标代码 。
23
四元式（ op,B,C,A)的 DAG结点表示，假定 B,C均
为非常数
n1
B
n2
C
n3
op
A
结点的编号
标记 标记
标记
附加标记
内部结点
前驱
叶结点
后继
§ 9.4 DAG的目标代码生成
24
(1)（ +,A,B,T1)
(2)（ +,C,D,T2)
(3)（ -,E,T2,T3)
(4)（ -,T1,T3,T4)
n4 n5
n6
C D
+
T2
n1 n2
n3
A B
+
T1 n7
E
n8 T3
n9 T4
四元式序列的 DAG表示
-
-
25
更高效的目标代码
(1)（ +,A,B,T1)
(2)（ +,C,D,T2)
(3)（ -,E,T2,T3)
(4)（ -,T1,T3,T4)
MOV A,R0
ADD B,R0
MOV C,R1
ADD D,R1
MOV R0,T1
MOV E,R0
SUB R1,R0
MOV T1,R1
SUB R0,R1
MOV R1,T4
(1)（ +,C,D,T2)
(2)（ -,E,T2,T3)
(3)（ +,A,B,T1)
(4)（ -,T1,T3,T4)
MOV C,R0
ADD D,R0
MOV E,R1
SUB R0,R1
MOV A,R0
ADD B,R0
SUB R1,R0
MOV R0,T4
26
DAG中结点的重构算法
设 DAG中有 M个内部结点,N是一个线形表，共 M项
For k:=1 to M Do N[k]:=null;
I:=M;
while 存在未列入 N的内部结点 do
begin
选一未列入 N但其全部前驱均列入 N或无前驱的内部结点 n;
N[I]:=n; I:=I-1; /*把 n列入 T中 */
while n的最左子结点 m不为叶结点且其全部前驱入 N中 do
begin
N[I]:=m; I:=I-1; n:=m
end
end
27
(1)（ +,A,B,T1)
(2)（ +,C,D,T2)
(3)（ -,E,T2,T3)
(4)（ -,T1,T3,T4)
N[4]
N[3]
N[2]
N[1]
n9
n3
n8
n6 计
算
次
序
DAG重构
(1)（ +,C,D,T2)
(2)（ -,E,T2,T3)
(3)（ +,A,B,T1)
(4)（ -,T1,T3,T4)
n4 n5
n6
C D
+
T2
n1 n2
n3
A B
+
T1 n7
E
n8 T3
n9 F
-
-
28
9.5 全局寄存器分配
? 将寄存器优先分配给引用最频繁的变量独占。
? 以循环 L为例来说明全局寄存器的分配思想, 估
算每一个变量独占寄存器所能降低的代价，为
降低代价最多的变量分配独占的寄存器。
? 执行一次循环所能节省的总执行代价为,
?
?
?
?
??? ?
?
其它
的出口之后活跃在中定值，且在
的访问次数；的定值点之前对中为基本块
0
BB1
),(
),(
)),(2),((
VV
BVL I V E
VVBBVUS E
BVL I V EBVUS E
LB
?
29
举例
? 假定可供独占的寄存器
有 R0,R1和 R2。
? 计算各变量可以节省的
总代价, USE(a,B1)=0
USE(a,B2)=USE(a,B3)=1
USE(a,B4)=0
LIVE(a,B1)=1
LIVE(a,B2)=0
LIVE(a,B3)=0
LIVE(a,B4)=0
所以,?a =4;
? 同理可以计算出
?b =6; ?c =3; ?d =6; ?e =4;
?f =4;
30
? 根据前面的计算结
果，可以将寄存器
R0,R1和 R2分别分
配给变量 a,b和 d独
占。
? 其它变量根据需要
分配其它的寄存器。
? 由此生成的目标代
码如右图所示。
第 9章 目标代码生成
目标代码生成是把语法分析优化后的中间代码变换成目标
代码 。 目标代码的形式主要包括如下 3种形式,
1,具有绝对地址的机器语言程序 。 能立即执行的机器语言
代码, 主程序与子程序需要同时编译 。
2,可浮动的机器语言程序 。 目标程序由若干个目的模块组
成, 各模块包含目标程序的一部分代码, 这些代码可在存
储空间浮动, 装入到存储空间的任何位置 。 需要连接装入
程序把它们和某些运行程序连接起来才能运行 。
3,汇编语言形式的程序 。 尚须经过汇编程序汇编, 转换成
可执行的机器语言代码 。
2
基本块
? 所谓基本块是指按顺序执行 （ 不含分支结构 ）
的中间代码 （ 四元式 ） 序列, 其中只有一个入
口和一个出口, 入口是第一个操作, 出口是最
后一个操作 。
– 对于基本块来说, 执行只能从其入口进入, 出口退
出 。
– 对于一个中间代码序列, 可以把它划分为一系列的
基本块,在各基本块范围内, 进行代码优化以及目
标代码生成 。
3
基本块划分的算法
1,求出程序中各个基本块的入口语句, 它们是,
(1) 程序的第一个语句, 或
(2) 能由条件转移语句或无条件转移语句转移到的语句, 或
(3) 紧跟在条件转移语句或无条件转移语句后面的语句,
2,对求出的每一入口语句, 构造其所属的基本块
（ 即找出口语句 ） 由该入口语句到,
(1) 下一入口语句 或到
(2) 转移语句 或到
(3) 停语句 之间的语句序列组成一个基本块 。
3,凡未被纳入某一基本块的语句, 都是程序中控制流无法到
达的语句, 可从程序中删除 。
4
§ 9.2 一个假想的计算机模型
? 以字节编址, 主存容量为 216个字节, 机器字长为 16bit,
有 8个通用寄存器,R0,R1,…,R7,且长度也为 16bit。
每条指令占用一个机器字, 形式如下,
OP arc,dst
OP表示操作码，占 4bit； arc和 dst分别表示源操作数
和目的操作数的地址，各占 6bit。
由于 6bit不能对整个内存空间进行寻址，因此将操作
数或其地址存放在紧跟指令之后的单元中。
5
6
常用指令
1,传送指令, MOV arc,dst (arc)?dst
2,运算指令,ADD arc,dst (dst)+(arc) ?dst
SUB arc,dst (dst)-(arc)?dst
3,比较指令,CMP arc,dst
执行 arc-dst，并对状态字 PSW相应的标志位置位。
当 (arc)=(dst)时,PSW的标志位 Z置 1。
当 (arc)<(dst)时,PSW的标志位 N置 1。
当 (arc)>(dst)时,PSW的标志位 P置 1。
4,控制指令,
{BR,j<,j?,j=,j?} dst,分别表示无条件,N=1,N?Z=1,Z=1
和 Z=0转移。
7
常用四元式的的目标代码
1,四元式 （ +,A,B,T） 对
应的指令为,
MOV A,R0；
ADD B,R0；
MOV R0,T；
其余二元操作四元式的翻译
与此类拟；
2,四元式 （ =,B,—,A） 对
应的指令为,
MOV B,R0；
MOV R0,A；
3,四元式 （ jnZ,A,—,P）
对应的指令为,
MOV A,R0；
CMP R0,0;
j? P’；
4,四元式 （ J,—,—,P） 对
应的指令为,BR P’；
5,四元式 （ Jrop,A,B,P）
对应的指令为
MOV A,R0；
CMP R0,B；
Jrop P’；
8
四元式目标地址的确定
（ 1）在把四元式翻译为目标指令时，是按四元式表中
四元式的顺序依次执行，为计算每个四元式所对应
的目标地址，必须累计每条指令的字节数。到达某
四元式时，所累计的字节数就是该四元式的目标地
址（相对的）。
（ 2）转移语句中转移地址所指的四元式是基本块的入
口语句，把这种语句按出现的顺序生成汇编代码标
号 L1,L2 …..,等，并用一张标号表存放起来,表格内
容为四元式序号与对应汇编代码标号。
9
§ 9.3 代码生成程序的雏形
? 为每个基本块的生成高质量代码,
– 总的指令条数要少；
– 尽可能利用寄存器, 少产生访问内存的指令, 为
此需要充分合理的利用寄存器,
? 尽可能把后面还要引用的变量仍保存在寄存器中；
? 应把不再使用的变量所占用的寄存器及时释放掉；
? 为此需引入两个概念：基本块内变量的引用信息和
活跃信息 。
10
引用信息与活跃信息
? 如果变量 A在某点 P的值 （ P是四元式的编号 ） 在从 P可
达的某四元式 q中被引用, 则称变量 A在 P点是 活跃的,
并称四元式 q是变量 A的 引用信息 。
(p) A=B+C; A在 P点是 活跃的
(r) E=A+F;
…,,
(q) D=A+V; q是变量 A的 引用信息
假定
①所有的临时变量均看作是出基本块后的非活跃变量。
②所有的非临时变量都看作是出基本块后的活跃变量。
11
基本块内的引用信息链和活跃信息链
1,数据结构,为四元式中的每个变量设置引用信息栏和
活跃信息栏, 在符号表中也增设引用信息栏和活跃信
息栏, 用于暂存各变量的引用与活跃信息, 临时变量
也如此 。
例：四元式的引用信息与活跃信息表示法
序号 四元式 结果 左变量 右变量
i (op,B,C,A) (引用,活跃） (引用,活跃） (引用,活跃）
i+1 (op,A,C,T) (引用,活跃） (引用,活跃） (引用,活跃）
12
算法
（ 1） 从基本块出口向入口方向逐个扫描每个四元式, 根据
每个变量的引用和定值情况建立各变量的引用和活跃信
息链 。
（ 2） 用 （ U,L） 表示引用 （ U） 与活跃 （ L） 信息 。
用 N表示不引用或不活跃；用 Y表示活跃, 四元式编号
表示下一个引用位置 。
（ 3） 用 FIRST和 LAST分别表示基本块的入口, 出口的语句
号 。
（ 4） 计算基本块各变量引用信息和活跃信息的算法 NEXT-
USE如下 （ 设四元式 （ OP,B,C,A））
13
Procedure NEXT-USE（ FIRST,LAST） ；
把符号表中每个变量的引用栏初始化为 N,
并把每个变量是否活跃的标记填入符号表的活跃栏内；
for I= LAST to FIRST do
begin GET(QUAD) (i) A=B+C
把符号表中 A的 （ U,L） 附加到四元式中的 A上；
让符号表中 A的 （ U,L） =（ ‘ N’,‘ N’） ；
把符号表中 B和 C的 （ U,L） 附加到四元式中的 B和 C上；
让符号表中 B的 （ U,L） =（ i,‘ Y’） ；
让符号表中 C的 （ U,L） =（ i,‘ Y’） ；
end
end;
14
四元式的附加信息
序
号
四元式 结果 左变
量
右变
量
１ (－,A,B,T) (5,Y) (2,Y) (2,Y)
２ (+,A,B,A) (3,Y) (N,N) (5,Y)
３ (－,A,C,U) (6,Y) (N,Y) (4,Y)
４ (+,C,D,V) (N,N) (N,Y) (N,Y)
５ (+,T,B,V) (6,Y) (N,N) (N,Y)
６ (+,V,U,W) (N,Y) (N,Y) (N,Y)
A (N,Y)→(3,Y)→(N,N)→(2,Y)→(1,Y)
B (N,Y)→(5,Y)→(2,Y)→ (1,Y)
T (N,N)→(5,Y)→(N,N)
C (N,Y)→(4,Y)→(3,Y)
U (N,Y)→(6,Y)→(N,N)
D (N,Y)→(4,Y)
V (N,Y)→(6,Y)→(N,N)→(N,N)
W (N,Y)→(N,N)
符号表的变化情况
15
寄存器的分配问题
1,描述寄存器分配信息的数据结构,
VAR栏表示把寄存器分配给哪个变量或哪些变量 （ 复写 ）
（ A,=B）
MEM栏表示占用 R的哪几个变量的值也在内存中
2、寄存器分配信息的描述结构
R VAR MEM
R0
R1
…
R7
16
寄存器分配算法
? 一般在生成四元式 A:=B OP C的代码中, 通常把左操作
数 B取到寄存器 R中, 再和 C操作 （ C可在内存中, 也可
在寄存中 ）, R中的结果就是 A的值, 或者说 A占用了 R,
? 寄存器的分配可以用 RGEREG（ QUAD,R） 实现, QUAD是
待分配寄存器的四元式,i,A:=B OP C,(OP,B,C,A)；
R是分配的寄存器 。
（ 算法需查看附在四元式 i上的活跃与引用信息及上表中
的结构 ）
17
为变量 A分配寄存器的算法应遵循以下原则 （ A:=B OP C）,
（ 1） 如果 B已在寄存器 Ri中 （ VAR（ Ri））,且以后不再引
用 （ 查四元式的 i的附加信息, B（ N,N） 为, 非活跃,
和, 非引用, ）, 则选择 Ri.(因为最后 Ri中存的是 A)。
（ 2） 从空闲寄存器中选一 Ri。
（ 3） 从已分配寄存器中选取其值在最远的将来才会使用的
寄存器 Ri（ 查四元式的附加信息 ）, 如果 Ri中的内容不在
内存中 （ 查 MEM（ Ri））, 则要生成一条存数指令
（ MOV Ri,M） 把 Ri中内容存入 M单元 。
18
基本块的代码生成算法
算法中使用以下过程,
（ 1） ADDR（ B）,获的变量 B当前存放的地方, 只
要 B在寄存器中就返回 R,否则 B在内存中 。
（ 2） FILL（ B,R）,如果变量 B不在 VAR（ R） 中,
则填入；如果 B同时又在内存中, 则把 B填入
MEM（ R） 中 。
（ 3） EMIT（ OP R,X）,向目标文件 QBJ中输出一
条指令 OP R,X。
（ 4） DELETE（ B,R）,如果 B在 VAR（ R） 和 MEM
（ R） 中的活, 则删除其中的 B。
19
算法 GENOBJ的一般描述如下,
输入,QUAD中的四元式 i,A=B OP C
输出：四元式 i的目标代码, 并将其存入目标文件 OBJ
PROCEDURE GENOBJ(QUAD);
BEGIN /*QUAD中的四元式形成 i,A=B OP C */
GETREG（ QUAD,R） ;
IF ADDR（ B） ≠ R THEN
BEGIN EMIT (MOV ADDR(B),R);
EMIT(OP ADDR(C),R);
END
ELSE
BEGIN EMIT (OP ADDR(C),R);
DELETE(B,R);
END
20
FILL(A,R);
for 每个 Rk≠R do DELETE(A,Rk);
for 每个 Rk do
begin if B(i)=(N,N) then Delete (B,Rk)
if C(i)=(N,N) then Delete (C,Rk)
end
end
算法中第一个 for语句保证 A只占有 R,
第二个 for语句释放非活跃跃和非引用变量 B与 C所占用的
寄存器 。
21
例：对以下四元式利用 GENOBJ产生目标代码,假定只有 R0
和 R1两个寄存器可用 。
四元式 R0 R1 QBJ
（ 1） （ -,A,B,T） T （ 1） MOV A,R0；
（ 2） SUB B,R0；
（ 2） （ +,A,B,A） A （ 3） MOV A,R1；
（ 4） ADD B,R1；
（ 3） （ -,A,C,U） U （ 5） SUB C,R1；
（ 4） （ +,C,D,V） V （ 6） MOV R1,U；
（ 7） MOV C,R1；
（ 8） ADD D,R1；
（ 5） （ +,T,B,V） V 空 （ 9） ADD B,R0；
（ 6） （ +,V,U,W） W (10） MOV R0,R1；
（ 11） ADD U,R1；
（ 12） MOV R1,W;
（ 13） MOV R0,V；
22
对算法 GENOBJ还可进一步改进, 如果按照程序控
制流程图去生成每一个基本块的目标代码, 那么在出
基本块的时候, 可以把该基本的寄存器占用情况保留
到下一基本块 。 在下一基本块中应尽量利用在寄存器
的变量值, 这样在每个基本块出口时, 可以不存贮每
个活跃变量的值 。
利用上术基本块的目标代码生成算法, 按此种顺序
所产生的目标代码, 其有效性末必是最佳的, 我们还
可以利用基本块的 DAG表示来重构基本块以改变基本
块的运行次序, 从而得到更有效的目标代码 。
23
四元式（ op,B,C,A)的 DAG结点表示，假定 B,C均
为非常数
n1
B
n2
C
n3
op
A
结点的编号
标记 标记
标记
附加标记
内部结点
前驱
叶结点
后继
§ 9.4 DAG的目标代码生成
24
(1)（ +,A,B,T1)
(2)（ +,C,D,T2)
(3)（ -,E,T2,T3)
(4)（ -,T1,T3,T4)
n4 n5
n6
C D
+
T2
n1 n2
n3
A B
+
T1 n7
E
n8 T3
n9 T4
四元式序列的 DAG表示
-
-
25
更高效的目标代码
(1)（ +,A,B,T1)
(2)（ +,C,D,T2)
(3)（ -,E,T2,T3)
(4)（ -,T1,T3,T4)
MOV A,R0
ADD B,R0
MOV C,R1
ADD D,R1
MOV R0,T1
MOV E,R0
SUB R1,R0
MOV T1,R1
SUB R0,R1
MOV R1,T4
(1)（ +,C,D,T2)
(2)（ -,E,T2,T3)
(3)（ +,A,B,T1)
(4)（ -,T1,T3,T4)
MOV C,R0
ADD D,R0
MOV E,R1
SUB R0,R1
MOV A,R0
ADD B,R0
SUB R1,R0
MOV R0,T4
26
DAG中结点的重构算法
设 DAG中有 M个内部结点,N是一个线形表，共 M项
For k:=1 to M Do N[k]:=null;
I:=M;
while 存在未列入 N的内部结点 do
begin
选一未列入 N但其全部前驱均列入 N或无前驱的内部结点 n;
N[I]:=n; I:=I-1; /*把 n列入 T中 */
while n的最左子结点 m不为叶结点且其全部前驱入 N中 do
begin
N[I]:=m; I:=I-1; n:=m
end
end
27
(1)（ +,A,B,T1)
(2)（ +,C,D,T2)
(3)（ -,E,T2,T3)
(4)（ -,T1,T3,T4)
N[4]
N[3]
N[2]
N[1]
n9
n3
n8
n6 计
算
次
序
DAG重构
(1)（ +,C,D,T2)
(2)（ -,E,T2,T3)
(3)（ +,A,B,T1)
(4)（ -,T1,T3,T4)
n4 n5
n6
C D
+
T2
n1 n2
n3
A B
+
T1 n7
E
n8 T3
n9 F
-
-
28
9.5 全局寄存器分配
? 将寄存器优先分配给引用最频繁的变量独占。
? 以循环 L为例来说明全局寄存器的分配思想, 估
算每一个变量独占寄存器所能降低的代价，为
降低代价最多的变量分配独占的寄存器。
? 执行一次循环所能节省的总执行代价为,
?
?
?
?
??? ?
?
其它
的出口之后活跃在中定值，且在
的访问次数；的定值点之前对中为基本块
0
BB1
),(
),(
)),(2),((
VV
BVL I V E
VVBBVUS E
BVL I V EBVUS E
LB
?
29
举例
? 假定可供独占的寄存器
有 R0,R1和 R2。
? 计算各变量可以节省的
总代价, USE(a,B1)=0
USE(a,B2)=USE(a,B3)=1
USE(a,B4)=0
LIVE(a,B1)=1
LIVE(a,B2)=0
LIVE(a,B3)=0
LIVE(a,B4)=0
所以,?a =4;
? 同理可以计算出
?b =6; ?c =3; ?d =6; ?e =4;
?f =4;
30
? 根据前面的计算结
果，可以将寄存器
R0,R1和 R2分别分
配给变量 a,b和 d独
占。
? 其它变量根据需要
分配其它的寄存器。
? 由此生成的目标代
码如右图所示。
