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