第七章 目标代码生成
7.1 对下列四元式序列生成目标代码：
T=A-B
S=C+D
W=E-F
U=W/T
V=U*S
其中，V 是基本块出口的活跃变量，R0和R1是可用寄存器。
【解答】 简单代码生成算法依次对四元式进行翻译。我们以四元式T=a+b为例来说明其翻译过程。
汇编语言的加法指令代码形式为
ADD R, X
其中，ADD 为加法指令；R 为第一操作数，第一操作数必须为寄存器类型；X 为第二操作数，它可以是寄存器类型，也可以是内存型的变量。ADD R,X 指令的含意是：将第一操作数R 与第二操作数相加后，再将累加结果存放到第一操作数所在的寄存器中。要完整地翻译出四元式T=a+b，则可能需要下面三条汇编指令：
MOV R, a
ADD R, b
MOV T, R
第一条指令是将第一操作数a 由内存取到寄存器R 中；第二条指令完成加法运算；
第三条指令将累加后的结果送回内存中的变量T 。是否在翻译成目标代码时都必须生成这三条汇编指令呢？从目标代码生成的优化角度考虑，即为了使生成的目标代码更短以及充分利用寄存器，上面的三条指令中，第一条和第三条指令在某些情况下是不必要的。这是因为，如果下一个四元式紧接着需要引用操作数T ，则第三条指令就不急于生成，可以推迟到以后适当的时机再生成。
此外，如果必须使用第一条指令，即第一操作数不在寄存器而是在内存中，且此时所有可用寄存器都已分配完毕，这时就要根据寄存器中所有变量的待用信息(也即引用点) 来决定淘汰哪一个寄存器留给当前的四元式使用。寄存器的淘汰策略如下：
(1) 如果某寄存器中的变量已无后续引用点且该变量是非活跃的，则可直接将该寄存器作为空闲寄存器使用。
(2) 如果所有寄存器中的变量在基本块内仍有引用点且都是活跃的，则将引用点最远的变量所占用寄存器中的值存放到内存与该变量对应的单元中，然后再将此寄存器分配给当前的指令使用。
因此，本题所给四元式序列生成的目标代码如下：
MOV R0, A
SUB R0, C /*R0=T*/
MOV R1, C
ADD R1, D /*R1=S*/
MOV S, R1 /*S引用点较T 引用点远，故将R1的值送内存单元S*/ MOV R1, E
SUB R1, F /*R1=W*/
SUB R1, R0 /*R1=U*/
MUL R1, S /*R1=V*/
7.2 假设可用的寄存器为R0和R1，且所有临时单元都是非活跃的，试将以下四元式基本
块：
T1=B-C
T2=A*T1
T3=D+1
T4=E-F
T5=T3*T4
W=T2/T5
用简单代码生成算法生成其目标代码。
【解答】 该基本块的目标代码如下(指令后面为相应的注释) ：
MOV R0, B /*取第一个空闲寄存器R0*/
SUB R0, C /*运算结束后R0中为T1结果，内存中无该结果*/
MOV R1, A /*取一个空闲寄存器R1*/
MUL R1, R0 /*运算结束后R1中为T2结果，内存中无该结果*/
MOV R0, D /*此时R0中结果T1已经没有引用点，且临时单元T1是 非活跃的，所以，寄存器R0可作为空闲寄存器使用*/
ADD R0, ″1″ /*运算结束后R0中为T3结果，内存中无该结果*/
MOV T2, R1 /*翻译四元式T4=E-F时，所有寄存器已经分配完毕，寄存器R0中存的T3和寄存器R1中存的T2都是有用的。由于T2的下一个引用点较T3的下一个引用点更远，所以暂时可将寄存器R1中的结果存回到内存的变量T2中，从而将寄存器R1空闲以备使用*/
MOV R1, E
SUB R1, F /*运算结束后R1中为T4结果，内存中无该结果*/
MUL R0, R1 /*运算结束后R0中为T5结果，内存中无该结果。注意，该指令将寄存器R0中原来的结果T3冲掉了。可以这么做的原因是，T3在该指令后不再有引用点，且是非活跃变量*/
MOV R1, T2 /*此时R1中结果T4已经没有引用点，且临时单元T4是非活跃的，因此寄存器R1可作为空闲寄存器使用*/
DIV R1, R0 /*运算结束后R1中为W 结果，内存中无该结果。此时所有指令部分已经翻译完毕*/
MOV W, R1 /*指令翻译完毕时，寄存器中存有最新的计算结果，必须将它们存回到内存相应的单元中去，否则，在翻译下一个基本块时，所有的寄存器被当成空闲的寄存器使用，从而造成计算结果的丢失。考虑到寄存器R0中的T5和寄存器R1中的W ，临时单元T5是非活跃的，因此只要将结果W 存回对应单元即可*/
7.3 对基本块P ：
S0=2
S1=3/S0
S2=T-C
S3=T+C
R=S0/S3
H=R
S4=3/S1
S5=T+C
S6=S4/S5
H=S6*S2
(1) 试应用DAG 进行优化；
(2) 假定只有R 、H 在基本块出口是活跃的，写出优化后的四元式序列；
(3) 假定只有两个寄存器AX 、BX ，试写出上述优化后的四元式序列的目标代码。
【解答】 (1) 根据DAG 的构造算法构造基本块P 的DAG 步骤如图7-1所示的(a)到(h)。
S 2
S 0S 0S 1
S 0S 1S 0S 1
(a) (b) (c) (d )
S 2S 2
(e) ( f )
S 2S 2
(g) (h)
图
7-1 基本块P 的DAG
按图7-1(h)和原来构造结点的顺序，优化后的四元式序列为
S0=2
S4=2
S1=1.5
S2=T-C
S3=T+C
S5=S3
R=2/S3
S6=R
H=S6*S2
(2) 假定只有R 、H 在基本块出口是活跃的，则上述优化后的四元式序列可进一步优化为
S0=T-C
S3=T+C
R=2/S3
H=R*S2
(3) 假定只有两个寄存器AX 、BX ，上述优化后的四元式序列的目标代码为
MOV AX, T
SUB AX, C
MOV AX, S2
MOV AX, T
ADD AX, C
MOV BX, 2
DIV BX
MOV AX, S2
MUL BX
MOV BX, H
7.4 参考附录1和附录2(《编译原理教程》一书) ，将下列汇编程序片段翻译为对应的8086/8088机器语言代码(汇编地址由1000开始) ：
MOV AX,01
MOV BX,10
CMP AX,BX
JA L1
ADD AX,BX
L1:
【解答】 该汇编程序片段翻译如下：
地址 机器码
1000 B80100
1003 BB1000
1006 39D8
1008 7702
100A 01D8
100C
第七章 目标代码生成
7.1 对下列四元式序列生成目标代码：
T=A-B
S=C+D
W=E-F
U=W/T
V=U*S
其中，V 是基本块出口的活跃变量，R0和R1是可用寄存器。
【解答】 简单代码生成算法依次对四元式进行翻译。我们以四元式T=a+b为例来说明其翻译过程。
汇编语言的加法指令代码形式为
ADD R, X
其中，ADD 为加法指令；R 为第一操作数，第一操作数必须为寄存器类型；X 为第二操作数，它可以是寄存器类型，也可以是内存型的变量。ADD R,X 指令的含意是：将第一操作数R 与第二操作数相加后，再将累加结果存放到第一操作数所在的寄存器中。要完整地翻译出四元式T=a+b，则可能需要下面三条汇编指令：
MOV R, a
ADD R, b
MOV T, R
第一条指令是将第一操作数a 由内存取到寄存器R 中；第二条指令完成加法运算；
第三条指令将累加后的结果送回内存中的变量T 。是否在翻译成目标代码时都必须生成这三条汇编指令呢？从目标代码生成的优化角度考虑，即为了使生成的目标代码更短以及充分利用寄存器，上面的三条指令中，第一条和第三条指令在某些情况下是不必要的。这是因为，如果下一个四元式紧接着需要引用操作数T ，则第三条指令就不急于生成，可以推迟到以后适当的时机再生成。
此外，如果必须使用第一条指令，即第一操作数不在寄存器而是在内存中，且此时所有可用寄存器都已分配完毕，这时就要根据寄存器中所有变量的待用信息(也即引用点) 来决定淘汰哪一个寄存器留给当前的四元式使用。寄存器的淘汰策略如下：
(1) 如果某寄存器中的变量已无后续引用点且该变量是非活跃的，则可直接将该寄存器作为空闲寄存器使用。
(2) 如果所有寄存器中的变量在基本块内仍有引用点且都是活跃的，则将引用点最远的变量所占用寄存器中的值存放到内存与该变量对应的单元中，然后再将此寄存器分配给当前的指令使用。
因此，本题所给四元式序列生成的目标代码如下：
MOV R0, A
SUB R0, C /*R0=T*/
MOV R1, C
ADD R1, D /*R1=S*/
MOV S, R1 /*S引用点较T 引用点远，故将R1的值送内存单元S*/ MOV R1, E
SUB R1, F /*R1=W*/
SUB R1, R0 /*R1=U*/
MUL R1, S /*R1=V*/
7.2 假设可用的寄存器为R0和R1，且所有临时单元都是非活跃的，试将以下四元式基本
块：
T1=B-C
T2=A*T1
T3=D+1
T4=E-F
T5=T3*T4
W=T2/T5
用简单代码生成算法生成其目标代码。
【解答】 该基本块的目标代码如下(指令后面为相应的注释) ：
MOV R0, B /*取第一个空闲寄存器R0*/
SUB R0, C /*运算结束后R0中为T1结果，内存中无该结果*/
MOV R1, A /*取一个空闲寄存器R1*/
MUL R1, R0 /*运算结束后R1中为T2结果，内存中无该结果*/
MOV R0, D /*此时R0中结果T1已经没有引用点，且临时单元T1是 非活跃的，所以，寄存器R0可作为空闲寄存器使用*/
ADD R0, ″1″ /*运算结束后R0中为T3结果，内存中无该结果*/
MOV T2, R1 /*翻译四元式T4=E-F时，所有寄存器已经分配完毕，寄存器R0中存的T3和寄存器R1中存的T2都是有用的。由于T2的下一个引用点较T3的下一个引用点更远，所以暂时可将寄存器R1中的结果存回到内存的变量T2中，从而将寄存器R1空闲以备使用*/
MOV R1, E
SUB R1, F /*运算结束后R1中为T4结果，内存中无该结果*/
MUL R0, R1 /*运算结束后R0中为T5结果，内存中无该结果。注意，该指令将寄存器R0中原来的结果T3冲掉了。可以这么做的原因是，T3在该指令后不再有引用点，且是非活跃变量*/
MOV R1, T2 /*此时R1中结果T4已经没有引用点，且临时单元T4是非活跃的，因此寄存器R1可作为空闲寄存器使用*/
DIV R1, R0 /*运算结束后R1中为W 结果，内存中无该结果。此时所有指令部分已经翻译完毕*/
MOV W, R1 /*指令翻译完毕时，寄存器中存有最新的计算结果，必须将它们存回到内存相应的单元中去，否则，在翻译下一个基本块时，所有的寄存器被当成空闲的寄存器使用，从而造成计算结果的丢失。考虑到寄存器R0中的T5和寄存器R1中的W ，临时单元T5是非活跃的，因此只要将结果W 存回对应单元即可*/
7.3 对基本块P ：
S0=2
S1=3/S0
S2=T-C
S3=T+C
R=S0/S3
H=R
S4=3/S1
S5=T+C
S6=S4/S5
H=S6*S2
(1) 试应用DAG 进行优化；
(2) 假定只有R 、H 在基本块出口是活跃的，写出优化后的四元式序列；
(3) 假定只有两个寄存器AX 、BX ，试写出上述优化后的四元式序列的目标代码。
【解答】 (1) 根据DAG 的构造算法构造基本块P 的DAG 步骤如图7-1所示的(a)到(h)。
S 2
S 0S 0S 1
S 0S 1S 0S 1
(a) (b) (c) (d )
S 2S 2
(e) ( f )
S 2S 2
(g) (h)
图
7-1 基本块P 的DAG
按图7-1(h)和原来构造结点的顺序，优化后的四元式序列为
S0=2
S4=2
S1=1.5
S2=T-C
S3=T+C
S5=S3
R=2/S3
S6=R
H=S6*S2
(2) 假定只有R 、H 在基本块出口是活跃的，则上述优化后的四元式序列可进一步优化为
S0=T-C
S3=T+C
R=2/S3
H=R*S2
(3) 假定只有两个寄存器AX 、BX ，上述优化后的四元式序列的目标代码为
MOV AX, T
SUB AX, C
MOV AX, S2
MOV AX, T
ADD AX, C
MOV BX, 2
DIV BX
MOV AX, S2
MUL BX
MOV BX, H
7.4 参考附录1和附录2(《编译原理教程》一书) ，将下列汇编程序片段翻译为对应的8086/8088机器语言代码(汇编地址由1000开始) ：
MOV AX,01
MOV BX,10
CMP AX,BX
JA L1
ADD AX,BX
L1:
【解答】 该汇编程序片段翻译如下：
地址 机器码
1000 B80100
1003 BB1000
1006 39D8
1008 7702
100A 01D8
100C