第十章 代码生成
代码生成要考虑的主要问题
基本块的代码生成 (在一个基本块范围内考虑如何充分利用寄存器的问题 )
从 dag生成代码
l 代码生成要考虑的主要问题
——具体细节依赖于目标机器和操作系统共同的问题：
1,充分利用寄存器基本块中全局 寄存器分配：不把寄存器平均分配给各个变量使用，而是从可用的寄存器中分出几个，固定分配给几个变量单独使用。标准 ——以各变量在循环内需要访问主存单元的次数为标准。
2,选择计算机指令系统
3,选择计算次序目标代码的三种形式地址代真的机器代码待装配的机器代码模块汇编语言 （宏汇编）
机器指令形式
(op source,destination)
ADD s,d // d+s
SUB s,d //d-s
MOV s,d //s? d
机器指令开销 (cost)
MOV R,M 开销 2
ADD #1,R 开销 2
MOV R0,R1 开销 1
目标机器的地址方式地址方式 汇编形式 地址 增加的开销直接地址方式 M M 1
寄存器方式 R R 0
间接寄存器方式 *R contents(R) 0
索引方式 c(R) c+contents(R) 1
间接索引方式 *c(R) contents(c+contents(R)) 1
a:=b+c
1,MOV b,R0
ADD c,R0 cost=6
MOV R0,a
2,MOV b,a
ADD c,a cost=6
假定 R0,R1和 R2中分别存放了 a,b和 c的地址,采用,
3,MOV *R1,*R0
ADD *R2,*R0 cost=2
假定 R1和 R2中分别包含 b和 c的值,并且 b的值在这个赋值以后不再需要,则还可有
4,ADD R2,R1
MOV R1,a cost=3
T4:=A+B-(E-(C+D))
T1:= A+B MOV A,R0
T2:=C+D ADD B,R0
T3:=E-T2 MOV C,R1
T4:=T1-T3 ADD D,R1
MOV R0,T1
MOV E,R0
SUB R1,R0
MOV T1,R1
SUB R0,R1
MOV R1,T4
T2:=C+D MOV C,R0
T3:=E-T2 ADD D,R0
T1:= A+B MOV E,R1
T4:=T1-T3 SUB R0,R1
MOV A,R0
ADD B,R0
SUB R1,R0
MOV R0,T4
,简单的代码生成器 （基本块内）
在一个基本块范围内考虑如何充分利用寄存器的问题：
l 尽可能地让该变量的值保留在寄存器中
l 尽可能引用变量在寄存器中的值待用信息：若在一个基本块中，变量 A在四元式 i 中被定值，在 i 后面的四元式 j 中要引用 A 值，且从 i 到 j 之间没有其它对 A的定值点，这时我们称 j是四元式 i 中对变量 A 的待用信息或称下次引用信息，同时也称 A 是活跃的，若 A 被多次引用则可构成待用信息链与活跃信息链。
可从基本块的出口由后向前扫描，对每个变量建立相应的待用信息链和活跃变量信息链。
计算待用信息的算法：
对各基本块的符号表中的,待用信息,栏和,活跃信息,
栏置初值，即把,待用信息,栏置,非待用,,对,活跃信息,栏按在基本块出口处是否为活跃而置成,活跃,或
“非活跃,。这里假定变量都是活跃的，临时变量都是非活跃的。
符号表中增加,待用信息,栏和,活跃信息,
栏从基本块出口到基本块入口由后向前依次处理每个四元式。对每个四元式 i,A:=B op C，依次执行下述步骤：
a） 把符号表中变量 A的待用信息和活跃信息附加到四元式 i
上。
b） 把符号表中变量 A的待用信息栏和活跃信息栏分别置为
“非待用,和,非活跃,。 （由于在 i 中对 A 的定值只能在 i 以后的四元式才能引用，因而对 i以前的四元式来说 A
是不活跃也不可能是待用的）
c） 把符号表中变量 B 和 C 的待用信息和活跃信息附加到四元式 i 上。
d） 把符号表中变量 B 和 C 的待用信息栏置为,i”，活跃信息栏置为,活跃,。
注意，以上 a）和 b）,c）和 d）的次序不能颠倒。
例,若用 A,B,C,D 表示变量，用 T,U,V 表示中间变量，有四元式如下：
（ 1 ） T,= A - B
（ 2 ） U,= A - C
（ 3 ） V,= T + U
（ 4 ） D,= V + U
其名字表中的待用信息和活跃信息如下表，用,F,表示,非待用”,非活跃”，用,L,表示活跃。 ( 1 ) ( 2 ) ( 3 ) ( 4 ) 表示四元式序号。
待用信息和活跃信息待用信息 活跃信息变量名初值 待用信息链 初值 活跃信息链
A F ( 2 ) ( 1 ) L L L
B F ( 1 ) L L
C F ( 2 ) L L
D F F L F
T F ( 3 ) F F L F
U F ( 4 ) ( 3 ) F F L L F
V F ( 4 ) F F L F
表中,待用信息链”与,活跃信息链”的每列从左至右为每从后向前扫描一个四元式时相应变量的信息变化情况，空白处为没变化。
待用信息和活跃信息在四元式上的标记如下所示：
( 1 ) T
( 3) L
,=A
( 2) L
-B
FL
( 2 ) U
( 3) L
,=A
FL
-C
FL
( 3 ) V
( 4) L
,=T
FF
+U
( 4) L
( 4 ) D
FL
,=V
FF
+U
FF
2 寄存器描述和地址描述为随时掌握各寄存器的情况，
寄存器描述数组 R V A LU E,描述每个寄存器当前的状况变量地址描述数组 A V A LU E,表示变量的存放情况
3 基本块的代码生成算法假设只有 A,= B o p C 的四元式序列
A,对每个四元式 i,A,= B o p C,依次执行下述步骤：
1,以四元式 i,A,= B o p C 为参数，调用过程 g et re g ( i,A,= B o p
C ) 。从 g et re g 返回时，得到一寄存器 R,用它作存放 A 现行值的寄存器；
2,利用 A V A LU E[ B] 和 A V A LU E[ C ],确定出 B 和 C 现行值存放位置 B` 和 C`,如果其现行值在寄存器中，则把寄存器取作 B` 和 C` ；
1,如 B` ≠ R,则生成目标代码
LD R,B`
o p R,C `
否则，生成目标代码 o p R,C`
如 B` 或 C` 为 R,则删除 A V A LU E [ B] 或 A V A LU E[ C ] 中的 R
2,令 A V A LU E[ B] = { R },并令 R V A LU E[ R ] = { A },以表示变量 A 的现行值只在 R 中并且 R 中的值只代表 A 的现行值；
3,如 B 或 C 的现行值在基本块中不再被引用，它们也不是基本块出口之后的活跃变量 （由四元式 i 上的附加信息知道），并且其现行值在某个寄存器 Rk 中，则删除
R V A LU E[ R k ] 中的 B 或 C 以及 A V A LU E[ B] 或
A V A LU E[ C ] 中的 Rk,使该寄存器不再为 B 或 C 所占用。
B,处理完基本块中所有四元式之后，对现行值在某寄存器 R
中的每个变量 M,若它在出口之后使活跃的，则生成 ST
R,M,放到主存中。
其中假定 d在基本块的出口是活跃的。
uvd
utv
cau
bat
cacabad
:
:
:
:
)()()(:
代码序列语句 生成的代码 寄存器描述器 地址描述器
t,= a － b M OV a,R 0
SUB b,R
0
空寄存器
R
0
包含 t t 在 R 0 中
u,= a － c M OV a,R 1
SUB c,R 1
R
0
包含 t
R
1
包含 u
t 在 R
0
中
u 在 R
1
中
v,= t ＋ u ADD R 1,R 0 R
0
包含 v
R
1
包含 u
u 在 R
1
中
v 在 R
0
中
d,= v ＋ u ADD R 1,R 0
M OV R
0
,d
R
0
包含 d d 在 R
0
中
d 在 R
0
中和存储器中从 dag生成目标代码
B
*
A,T 5
* T 2,T 4 T 6
+ -
T 0 T 1,T 3
3,1 4 6,2 8 R r
( j )
n2
n5
n3
n7
n1
n4
n6
n8
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
T0:=3.14
T1:=6.28
T3:=6.28
T2:=R+r
T4:=T2
A:=6.28*T2
T5:=A
T6:=R-r
B:=A*T6
例：赋值语句 T4:=A+B-(E-(C+D))
四元式序列 G
T1,=A+B
T2,=C+D
T3,=E-T2
T4,=T1-T3
DAG：
A B E
C D
n9
n3 n8
n1 n2 n7 n6
n4 n5
T4
T1 T3
T2
+
-
-
+
T4:=A+B-(E-(C+D))
T1:= A+B MOV A,R0
T2:=C+D ADD B,R0
T3:=E-T2 MOV C,R1
T4:=T1-T3 ADD D,R1
MOV R0,T1
MOV E,R0
SUB R1,R0
MOV T1,R1
SUB R0,R1
MOV R1,T4
排序
T2:=C+D MOV C,R0
T3:=E-T2 ADD D,R0
T1:= A+B MOV E,R1
T4:=T1-T3 SUB R0,R1
MOV A,R0
ADD B,R0
SUB R1,R0
MOV R0,T4
原因,T4的计算紧跟在 T1之后尽可能使一个结点的求值紧接着它的最左变量的求值之后启发式排序算法
(1) while存在未列入表的内部结点 do
(2) begin选取一个未列入表的但其全部父结点均已列入表的结点 n;
(3) 将 n列入表中 ;
(4) while n的最左子结点 m不是叶结点并且其所有父结点均已列入表中 do
(5) begin将 m列入表中 ;
(6) n,=m
(7) end
(8) end
3
t
2
t:
1
t
4
t
6
t:
2
t
e
4
t:
3
t
8
t
5
t:
4
t
c
6
t:
5
t
ba:
6
t
ed:
8
t
基于树重写的代码生成替换 ← 模版 {动作 }
基于树重写的代码生成例,a[i]:=b+1
,=
ind +
Memb const1
ind
+
consti regsp
consta regsp
+
+
regi + {ADD Rj,Ri}
regi regj
(1) reg
i
cons t
c
{MOV #c,R i }
(2) reg
i
me m
a
{MOV a,R i }
(3) me m? {MOV R i,a}
(4) me m? {MOV R j,* R i }
(5) reg
i
{MOV c( R j ),R i }
,=
mem
a
reg
i
,=
mem
a
reg
j
ind
con st
c
reg
j
reg
i
+
(6) re g
i
{ADD c( R j ),R i }
(7) re g
i
{ADD R j,R i }
(8) re g
i
{INC R i }
+
reg
i
ind
con st
c
reg
j
+
+
reg
i
cost
1
+
reg
i
reg
j
(1) R eg
0? co ns t a
{M O V # a,R 0 }
(7) reg
0?
{A D D S P,R 0 }
+
reg 0 reg SP
,=
ind +
Memb const1
ind
+
consti regSP
reg0
+
ind
const i reg SP
++
re g 0 i nd
c on s t i re g SP
+
,=
i nd
reg 0
+
mem b const 1
+
r e g 1 c o n s t 1,=
in d r e g 1
r e g 0
MOV #a,R0
ADD SP,R0
ADD i(SP),R0
MOV b,R1
INC R1
MOV R1,*R0
代码生成要考虑的主要问题
基本块的代码生成 (在一个基本块范围内考虑如何充分利用寄存器的问题 )
从 dag生成代码
l 代码生成要考虑的主要问题
——具体细节依赖于目标机器和操作系统共同的问题：
1,充分利用寄存器基本块中全局 寄存器分配：不把寄存器平均分配给各个变量使用，而是从可用的寄存器中分出几个，固定分配给几个变量单独使用。标准 ——以各变量在循环内需要访问主存单元的次数为标准。
2,选择计算机指令系统
3,选择计算次序目标代码的三种形式地址代真的机器代码待装配的机器代码模块汇编语言 （宏汇编）
机器指令形式
(op source,destination)
ADD s,d // d+s
SUB s,d //d-s
MOV s,d //s? d
机器指令开销 (cost)
MOV R,M 开销 2
ADD #1,R 开销 2
MOV R0,R1 开销 1
目标机器的地址方式地址方式 汇编形式 地址 增加的开销直接地址方式 M M 1
寄存器方式 R R 0
间接寄存器方式 *R contents(R) 0
索引方式 c(R) c+contents(R) 1
间接索引方式 *c(R) contents(c+contents(R)) 1
a:=b+c
1,MOV b,R0
ADD c,R0 cost=6
MOV R0,a
2,MOV b,a
ADD c,a cost=6
假定 R0,R1和 R2中分别存放了 a,b和 c的地址,采用,
3,MOV *R1,*R0
ADD *R2,*R0 cost=2
假定 R1和 R2中分别包含 b和 c的值,并且 b的值在这个赋值以后不再需要,则还可有
4,ADD R2,R1
MOV R1,a cost=3
T4:=A+B-(E-(C+D))
T1:= A+B MOV A,R0
T2:=C+D ADD B,R0
T3:=E-T2 MOV C,R1
T4:=T1-T3 ADD D,R1
MOV R0,T1
MOV E,R0
SUB R1,R0
MOV T1,R1
SUB R0,R1
MOV R1,T4
T2:=C+D MOV C,R0
T3:=E-T2 ADD D,R0
T1:= A+B MOV E,R1
T4:=T1-T3 SUB R0,R1
MOV A,R0
ADD B,R0
SUB R1,R0
MOV R0,T4
,简单的代码生成器 （基本块内）
在一个基本块范围内考虑如何充分利用寄存器的问题：
l 尽可能地让该变量的值保留在寄存器中
l 尽可能引用变量在寄存器中的值待用信息：若在一个基本块中，变量 A在四元式 i 中被定值，在 i 后面的四元式 j 中要引用 A 值，且从 i 到 j 之间没有其它对 A的定值点，这时我们称 j是四元式 i 中对变量 A 的待用信息或称下次引用信息，同时也称 A 是活跃的，若 A 被多次引用则可构成待用信息链与活跃信息链。
可从基本块的出口由后向前扫描，对每个变量建立相应的待用信息链和活跃变量信息链。
计算待用信息的算法：
对各基本块的符号表中的,待用信息,栏和,活跃信息,
栏置初值，即把,待用信息,栏置,非待用,,对,活跃信息,栏按在基本块出口处是否为活跃而置成,活跃,或
“非活跃,。这里假定变量都是活跃的，临时变量都是非活跃的。
符号表中增加,待用信息,栏和,活跃信息,
栏从基本块出口到基本块入口由后向前依次处理每个四元式。对每个四元式 i,A:=B op C，依次执行下述步骤：
a） 把符号表中变量 A的待用信息和活跃信息附加到四元式 i
上。
b） 把符号表中变量 A的待用信息栏和活跃信息栏分别置为
“非待用,和,非活跃,。 （由于在 i 中对 A 的定值只能在 i 以后的四元式才能引用，因而对 i以前的四元式来说 A
是不活跃也不可能是待用的）
c） 把符号表中变量 B 和 C 的待用信息和活跃信息附加到四元式 i 上。
d） 把符号表中变量 B 和 C 的待用信息栏置为,i”，活跃信息栏置为,活跃,。
注意，以上 a）和 b）,c）和 d）的次序不能颠倒。
例,若用 A,B,C,D 表示变量，用 T,U,V 表示中间变量，有四元式如下：
（ 1 ） T,= A - B
（ 2 ） U,= A - C
（ 3 ） V,= T + U
（ 4 ） D,= V + U
其名字表中的待用信息和活跃信息如下表，用,F,表示,非待用”,非活跃”，用,L,表示活跃。 ( 1 ) ( 2 ) ( 3 ) ( 4 ) 表示四元式序号。
待用信息和活跃信息待用信息 活跃信息变量名初值 待用信息链 初值 活跃信息链
A F ( 2 ) ( 1 ) L L L
B F ( 1 ) L L
C F ( 2 ) L L
D F F L F
T F ( 3 ) F F L F
U F ( 4 ) ( 3 ) F F L L F
V F ( 4 ) F F L F
表中,待用信息链”与,活跃信息链”的每列从左至右为每从后向前扫描一个四元式时相应变量的信息变化情况，空白处为没变化。
待用信息和活跃信息在四元式上的标记如下所示：
( 1 ) T
( 3) L
,=A
( 2) L
-B
FL
( 2 ) U
( 3) L
,=A
FL
-C
FL
( 3 ) V
( 4) L
,=T
FF
+U
( 4) L
( 4 ) D
FL
,=V
FF
+U
FF
2 寄存器描述和地址描述为随时掌握各寄存器的情况，
寄存器描述数组 R V A LU E,描述每个寄存器当前的状况变量地址描述数组 A V A LU E,表示变量的存放情况
3 基本块的代码生成算法假设只有 A,= B o p C 的四元式序列
A,对每个四元式 i,A,= B o p C,依次执行下述步骤：
1,以四元式 i,A,= B o p C 为参数，调用过程 g et re g ( i,A,= B o p
C ) 。从 g et re g 返回时，得到一寄存器 R,用它作存放 A 现行值的寄存器；
2,利用 A V A LU E[ B] 和 A V A LU E[ C ],确定出 B 和 C 现行值存放位置 B` 和 C`,如果其现行值在寄存器中，则把寄存器取作 B` 和 C` ；
1,如 B` ≠ R,则生成目标代码
LD R,B`
o p R,C `
否则，生成目标代码 o p R,C`
如 B` 或 C` 为 R,则删除 A V A LU E [ B] 或 A V A LU E[ C ] 中的 R
2,令 A V A LU E[ B] = { R },并令 R V A LU E[ R ] = { A },以表示变量 A 的现行值只在 R 中并且 R 中的值只代表 A 的现行值；
3,如 B 或 C 的现行值在基本块中不再被引用，它们也不是基本块出口之后的活跃变量 （由四元式 i 上的附加信息知道），并且其现行值在某个寄存器 Rk 中，则删除
R V A LU E[ R k ] 中的 B 或 C 以及 A V A LU E[ B] 或
A V A LU E[ C ] 中的 Rk,使该寄存器不再为 B 或 C 所占用。
B,处理完基本块中所有四元式之后，对现行值在某寄存器 R
中的每个变量 M,若它在出口之后使活跃的，则生成 ST
R,M,放到主存中。
其中假定 d在基本块的出口是活跃的。
uvd
utv
cau
bat
cacabad
:
:
:
:
)()()(:
代码序列语句 生成的代码 寄存器描述器 地址描述器
t,= a － b M OV a,R 0
SUB b,R
0
空寄存器
R
0
包含 t t 在 R 0 中
u,= a － c M OV a,R 1
SUB c,R 1
R
0
包含 t
R
1
包含 u
t 在 R
0
中
u 在 R
1
中
v,= t ＋ u ADD R 1,R 0 R
0
包含 v
R
1
包含 u
u 在 R
1
中
v 在 R
0
中
d,= v ＋ u ADD R 1,R 0
M OV R
0
,d
R
0
包含 d d 在 R
0
中
d 在 R
0
中和存储器中从 dag生成目标代码
B
*
A,T 5
* T 2,T 4 T 6
+ -
T 0 T 1,T 3
3,1 4 6,2 8 R r
( j )
n2
n5
n3
n7
n1
n4
n6
n8
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
T0:=3.14
T1:=6.28
T3:=6.28
T2:=R+r
T4:=T2
A:=6.28*T2
T5:=A
T6:=R-r
B:=A*T6
例：赋值语句 T4:=A+B-(E-(C+D))
四元式序列 G
T1,=A+B
T2,=C+D
T3,=E-T2
T4,=T1-T3
DAG：
A B E
C D
n9
n3 n8
n1 n2 n7 n6
n4 n5
T4
T1 T3
T2
+
-
-
+
T4:=A+B-(E-(C+D))
T1:= A+B MOV A,R0
T2:=C+D ADD B,R0
T3:=E-T2 MOV C,R1
T4:=T1-T3 ADD D,R1
MOV R0,T1
MOV E,R0
SUB R1,R0
MOV T1,R1
SUB R0,R1
MOV R1,T4
排序
T2:=C+D MOV C,R0
T3:=E-T2 ADD D,R0
T1:= A+B MOV E,R1
T4:=T1-T3 SUB R0,R1
MOV A,R0
ADD B,R0
SUB R1,R0
MOV R0,T4
原因,T4的计算紧跟在 T1之后尽可能使一个结点的求值紧接着它的最左变量的求值之后启发式排序算法
(1) while存在未列入表的内部结点 do
(2) begin选取一个未列入表的但其全部父结点均已列入表的结点 n;
(3) 将 n列入表中 ;
(4) while n的最左子结点 m不是叶结点并且其所有父结点均已列入表中 do
(5) begin将 m列入表中 ;
(6) n,=m
(7) end
(8) end
3
t
2
t:
1
t
4
t
6
t:
2
t
e
4
t:
3
t
8
t
5
t:
4
t
c
6
t:
5
t
ba:
6
t
ed:
8
t
基于树重写的代码生成替换 ← 模版 {动作 }
基于树重写的代码生成例,a[i]:=b+1
,=
ind +
Memb const1
ind
+
consti regsp
consta regsp
+
+
regi + {ADD Rj,Ri}
regi regj
(1) reg
i
cons t
c
{MOV #c,R i }
(2) reg
i
me m
a
{MOV a,R i }
(3) me m? {MOV R i,a}
(4) me m? {MOV R j,* R i }
(5) reg
i
{MOV c( R j ),R i }
,=
mem
a
reg
i
,=
mem
a
reg
j
ind
con st
c
reg
j
reg
i
+
(6) re g
i
{ADD c( R j ),R i }
(7) re g
i
{ADD R j,R i }
(8) re g
i
{INC R i }
+
reg
i
ind
con st
c
reg
j
+
+
reg
i
cost
1
+
reg
i
reg
j
(1) R eg
0? co ns t a
{M O V # a,R 0 }
(7) reg
0?
{A D D S P,R 0 }
+
reg 0 reg SP
,=
ind +
Memb const1
ind
+
consti regSP
reg0
+
ind
const i reg SP
++
re g 0 i nd
c on s t i re g SP
+
,=
i nd
reg 0
+
mem b const 1
+
r e g 1 c o n s t 1,=
in d r e g 1
r e g 0
MOV #a,R0
ADD SP,R0
ADD i(SP),R0
MOV b,R1
INC R1
MOV R1,*R0
