第11 章目标代码生成文档格式.docx
《第11 章目标代码生成文档格式.docx》由会员分享，可在线阅读，更多相关《第11 章目标代码生成文档格式.docx（17页珍藏版）》请在冰点文库上搜索。
目标程序
例X：
=Y+Z其中：
X，Y，Z对应的地址分别为t0，t0+1，t0+2。
符号表
t0
t0+1
t0+2
地址
X
Y
Z
LDR0，Y—取数
ADDR0Z
STR0X—送数
2、在语义检查时发现了一些明显的错误，并加入了类型转换操作，可假设代码生成阶段的输入没有错误。
四、指令的选择
生成的代码质量取决于它的速度和大小，因此，指令集的一致性和完整性，指令速度和机器用语是非常重要的。
五、寄存器分配
如何充分利用寄存器，对于生成好的代码是非常重要的。
1、在寄存器分配期间，为程序的某一点选择驻留在寄存器中的一组变量；
2、在随后的寄存器指派阶段，挑出变量将要驻留的具体寄存器。
六、计算顺序选择
计算的顺序会影响目标代码的有效性和代码的执行效率。
第二节目标机器的模型
要设计一个好的代码生成器，必须预先熟悉目标机器和它的指令系统。
一、硬件设置
1、主存器；
2、字长；
3、寄存器。
二、指令系统
1、传送指令；
2、运算指令（算术运算，逻辑运算）；
3、比较指令；
4、控制指令。
假设计算机指令
指令
意义
LDRi,B
STRi,B
JX
CMPA,B
J<
J≤X
J=X
J≠X
J>
J≥X
把B单元的内容取到寄存器R，即（B）Ri
把寄存器Ri的内容存到B单元，即（Ri）B
无条件转向X单元
单元A与单元B比较，并根据比较情况把机器内部特征寄存器CT置成相应状态。
CT占两个二进位。
根据A<
B分别置CT为0或1或2
如CT＝0，转X单元
如CT＝0或CT＝1转X单元
如CT＝1转X单元
如CT≠1转X单元
如CT＝2转X单元
如CT＝2或CT＝1转X单元
以上指令中运算符op包括一般计算机上常见的一些运算符，如ADD、SUB、MUL、DIV等等，
三、寻址方式
假设机器的寻址方式
类型
指令形式
意义（设op是二目运算符）
直接地址型
寄存器型
变址型
间接型
opRi,M
opRi,Rj
opRi,c（Rj）
opRi,*M
opRi,*Rj
opRi,*c（Rj）
（Ri）op（M）Ri
（Ri）op（Rj）Ri
（Ri）op（（Rj）+c）Ri
（Ri）op（（M））Ri
（Ri）op（（Rj））Ri
例1：
STＲ0,M表示把寄存器R0的内容存到M单元，即
（Ri）M
例2：
STＲ0,4（R1）表示把寄存器R0的内容存到（4+（R1））单元,此为变址指令
例3：
LDＲ0,*4（R1）表示把（4+（R1））所指的单元的内容存到寄存器R0中,此为间址指令
例4：
STＲ0,#1表示把常数1存到寄存器R0中。
第三节一个简单的代码生成器
一、代码生成器的任务
把每条中间代码变换成目标代码，并考虑在基本块内，充分利用寄存器的优化。
实现策略：
当前操作数在寄存器中直接引用，不在产生访问主存的目标代码；
应尽可能使执行的结果保留在寄存器中；
需要释放寄存器产生转存贮器的目标代码；
对于X:
=Y+Z一般翻译为：
LDR0，Y
ADDR0，Z
STR0，X
目标代码应尽量减少访问主存次数,可以提高目标代码的运行速度,为此要充分利用寄存器来保存变量的值和中间结果。
二、使用寄存器的算法
1、在基本块中，当生成计算某变量值的目标代码时，尽可能地让该变量的值保留在寄存器中，直到该寄存器必须用来存放新的值或者到达基本块出口为止；
2、后续的目标代码尽可能地引用变量在寄存器中的值，而不访问主存；
3、到达基本块的出口，把寄存器的值存到主存器的指令。
A：
=（B+C）*D+E把它翻译为中间代码为：
T1：
=B+C
T2：
=T1*D
A：
=T2+E
翻译成目标代码序列为:
（1）LDR，B
（2）ADDR，C
（3）STR，T1
（4）LDR，T1
（5）MULR，D
（6）STR，T2
（7）LDR，T2
（8）ADDR，E
（9）STR，A
考虑了效率和充分利用寄存器的问题之后，代码生成器就可以生成如下代码：
（3）MULR，D
（4）ADDR，E
（5）STR，A
三、活跃变量和待用信息
1、活跃变量
某变量A在程序中某点p是活跃变量（或称A在点p是活跃的）,是指A的值要在从p开始的某通路上被引用。
（p）A:
=BopC或（p）B:
=AopC
活跃活跃
（q）T:
=AopV（q）T:
=AopV
A的值在（q）点被引用。
2、待用信息
表示变量的值在后面的中间代码中任何处被引用。
（i）A：
=BopC
…无对A再定值
（j）X：
=AopD
称（j）是（i）的下一个引用点（或称j是i的变量A的待用信息,A在点i是活跃的）。
上例中,点q是变量A的待用信息,或称A在点p是活跃的。
一般将临时变量均看作基本块出口之后的非活跃变量,非临时变量均看作基本块出口之后的活跃变量.
3、建立待用信息链和活跃变量信息链
可以从基本块的出口，由后向前把基本块中每个变量建立待用信息链和活跃变量信息链。
算法如下：
开始时，把基本块中各变量的符号表登记项的待用信息栏填写“非待用”，并根据该变量选择基本块的出口之后是不活跃的，把其中活跃信息栏填写“非活跃”。
从基本块的出口到基本块入口由后向前依次处理各中间代码。
对每个中间代码（i）A:
=BopC,依次执行下述步骤：
①把符号表中变量A的待用信息和活跃信息附加到中间代码i上；
②把符号表中变量A的待用信息和活跃信息分别置为“非待用”和“非活跃”；
③把符号表中变量B和C的待用信息和活跃信息附加到中间代码i上；
④把符号表中变量B和C的待用信息均置为i,活跃信息均置为“活跃”。
有一基本块中间代码为:
T:
=A-B
U:
=A-C
V:
=T+U
W:
=V+U
变量的符号表中待用信息、活跃信息
T（非,非）（3,y）（非,非）
A（非,非）（2,y）（非,非）
B（非,非）（1,y）
C（非,非）（2,y）
U（非,非）（4,y）（3,y）（非,非）
V（非,非）（4,y）（非,非）
W（非,y）（非,非）
（1）T：
=A-B
3,y2,y非,非
（2）U：
=A-C
3,y非,非非,非
（3）V：
=T+U
4,y非,非4,y
（4）W：
=V+U
非,y非,非非,非
注：
j,y表示j点引用，非活跃变量。
四、寄存器和地址描述
1、寄存器描述数组（Rvalue）
记录可用寄存器的现行使用情况，并对寄存器的分配作出确定的判断。
了解当前未被占用的寄存器；
了解当前被占用的寄存器所分配的变量。
分配的变量
R0
A
R1
（空闲）
R2
B
2、变量地址描述数组（Avalue）
动态记录目标程序运行时，变量现行值存放的位置。
寄存器
主存
在
C
五、代码生成算法（P315）
对于中间代码（i）A:
1、调用GETREG（（i）A:
=BopC）,得到一个寄存器R存放A。
2、查找Rvalue和Avalue若B,C在B′,C′中。
3、如果B′≠R,则生成目标代码：
LDＲ，B′
opR,C′
若B′为寄存器,则生成目标代码：
opR,C′
4、令Avalue[A]={R},Rvalue[R]={A}
5、如果B和C的值在基本块中不再被引用，也不是基本块出口之后的活跃变量，并且其值在某个寄存器Rk中，则删除RVALUE[Rk]中的B或C以及AVALUE[B]中的Rk，使寄存器不再为B或C所占用。
GETREG是一个函数过程，GETREG（（i）A:
=BopC）给出一个用来存放A的当前值的寄存器R，其中要用到中间代码i上的待用信息。
GETREG的算法如下：
如果B的现行值在某个寄存器Ri中，RVALUE[Ri]只包含B此外，或者B与A是同一标识符，或者B的现行值在执行中间代码A:
=BopC之后不会再引用（此时，该中间代码i的附加信息中，B的待用信息和活跃信息分别为“非待用”和“非活跃”），则选取Ri为所需的寄存器R，并转
。
如果有尚未分配的寄存器，则从中选取一个Ri为所需的寄存器R，并转
从已分配的寄存器中选取一个Ri为所需的寄存器R，Ri满足以下条件：
占用Ri变量的值，同时存放在该变量主存单元中。
对RVALUE[Ri]中每一变量M，如果M不是A，或者如果M是A又是C，但不是B并且B也不在RVALUE[Ri]中，则:
如果AVALUE[M]不包含M，则生成目标代码STRi，M；
如果M是B，或者M是C但同时B也在RVALUE[Ri]中，则令AVALUE[M]＝{M};
删除RVALUE[Ri]中的M；
给出R，返回。
中间代码
目标代码
RVALUE
AVALUE
T:
＝A-B
LDR0,A
SUBR0,B
R0含有T
T在R0中
U:
＝A-C
LDR1,A
SUBR1,C
R1含有U
U在R1中
V:
＝T＋U
ADDR0,R1
R0含有V
V在R0中
W:
＝V＋U
Ro含有W
W在R0中
序号
备注
1
A:
＝BopC
opRi,C
其中Ri是新分配给A的寄存器
如果B和/或C的现行值在寄存器中，
则目标中B和/或C用寄存器表示。
但如果C的现行值在Ri中，而B
的现行值不在Ri中，则C要用其
主存单元表示。
如果B的现行值也在Ri中，
则不生成第一条目标代码。
2
＝op1B
op1Ri,Ri
同1中备注
（1）
同1中备注（3）
op1指一目运算符
3
＝B
如果B的现行值在Ri中，
则如前所述，不生成目标代码
4
＝B[I]
LDRj,I
LDRi,B（Rj）
如果I的现行值在Rj中，
则不生成第一条目标代码，
否则Rj是新分配给I的寄存器
5
A[I]:
STRi,A（Rj）
同4中备注
（2）
6
gotoX
JX’
X’是标号为X的中间代码的目标代码的首地址
7
IfAropBgotoX
LDRi,A
CMPRi,B
JropX’
X’的意义同6中备注
（1）
若A的现行值在Ri中，则不生成第一条目标代码
如果B的现行值也在Ri中，则目标代码中的B就是Ri
rop指<
,=,,>
或
8
＝P
LDRi,*P
9
P:
＝A
STRi,*P
如果A的现行值在Ri中，则不生成第一条目标代码。
第四节寄存器分配
为了生成更有效的目标代码，需要考虑的一个问题就是如何更有效的利用寄存器，寄存器分配的策略：
1、把寄存器尽量优先分配给引用频繁的变量独占；
2、把寄存器作为操作数地址；
3、把变量的现行值保存在寄存器中。
一、执行代价算法（P318）
执行代价=每条指令访问主存单元次数+1
1、仅当变量在基本块中被定值时，其值才存放在寄存器中。
把寄存器分配给某变量使用，当该变量在基本块中被定值前，每引用一次，就可少访问一次主存，执行代价就节省1。
2、如果某变量在基本块中被定值且在基本块出口之后是活跃的，出在基本块时，就无须把它的值存放到主存单元中，执行代价就节省2。
3、计算公式（略）
二、执行代价计算注意的问题
1、变量是活跃的，在入口先把它的值从主存单元取到寄存器，执行代价为2，可忽略不计。
2、对于循环程序每循环一次，由于执行路径的不同，在计算执行代价时，认为循环体中的个基本块都被执行一次，可忽略不计。
三、循环中的目标代码生成算法
1、凡涉及到已固定分配到寄存器的变量，用寄存器表示；
2、某变量在循环入口之前是活跃的，在循环入口之前产生把结果值存入寄存器的目标代码。
3、某变量在循环出口是活跃的，在循环出口产生把寄存器的结果存入主存的目标代码。
4、在循环中的每个基本块出口，对没固定分配到寄存器的变量，产生把寄存器的结果存入主存的目标代码。
5、对已固定分配到寄存器的变量，在循环中某基本块出口不是活跃的可释放，作一般寄存器使用。
思考题：
P3271。
升级会员 