第12章 代码生成

1、武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 第十二章 代码生成 12.1 12.1 代码生成概述代码生成概述 12.2 12.2 一个简单的代码生成程序一个简单的代码生成程序 12.3 12.3 几种常用的代码生成程序的开发方法几种常用的代码生成程序的开发方法 12.4 12.4 全局寄存器分配全局寄存器分配 12.5 12.5 代码生成程序的自动化构造代码生成程序的自动化构造 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 12.1 12.1 代码生成概述代码生成概述 12.1.1 12.1.1 目标代码的三种形式目标代码的三种形式: : 能够立即执行的机器语言代码，

2、所有地址均已能够立即执行的机器语言代码，所有地址均已 定位；定位； 待装配的机器代码模块，当需要执行时，由连待装配的机器代码模块，当需要执行时，由连 接装入程序把它们和某些运行程序连接起来，接装入程序把它们和某些运行程序连接起来， 转换成能执行的机器语言代码；转换成能执行的机器语言代码； 汇编语言代码，需经过汇编程序汇编，转换成汇编语言代码，需经过汇编程序汇编，转换成 可立即执行的机器语言代码。可立即执行的机器语言代码。 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 12.1.2 12.1.2 代码生成要考虑的主要问题代码生成要考虑的主要问题 具体细节依赖于目标机器和操作系统具体细

3、节依赖于目标机器和操作系统 (1)代码生成程序的输入代码生成程序的输入: : 线性表示、三地址表示、图形表示线性表示、三地址表示、图形表示 (2)计算机指令的选择计算机指令的选择 x:=y+z LD R0, y ADD R0, z ST R0, x a:=a+1 INC a (3)(3)充分利用寄存器充分利用寄存器( (寄存器分配寄存器分配) ) (4)(4)选择计算次序选择计算次序( (指令调度指令调度) ) 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 12.2 12.2 简单的简单的代码生成程序代码生成程序 12.2.1 12.2.1 计算机模型计算机模型 机器指令形式机器指

4、令形式 指令意义指令意义 op Ri, M (Ri) op (M)= Ri op Ri, Rj (Ri) op (Rj)= Ri op Ri, c(Rj) (Ri) op( (Rj)+c)= Ri op Ri, *M (Ri) op (M)= Ri op Ri, *Rj (Ri) op (Rj)= Ri op Ri, c*(Rj) (Ri) op( (Rj)+c)= Ri 机器指令开销机器指令开销 (cost)(cost) op R, M 开销开销 2 op Ri, Rj 开销开销 1 op Ri, *M 开销开销 3 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 目标机器的地址方

5、式目标机器的地址方式 地址方式汇编形式地址增加的开销 直接地址方式 MM1 寄存器方式 RR0 间接寄存器方式 *Rcontents(R)0 索引方式 c(R)c+contents(R)1 间接索引方式 *c(R)contents(c+contents(R)1 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 12.2.2 12.2.2 待用信息链法待用信息链法 在一个基本块范围内考虑如何充分利用寄存器的问题：在一个基本块范围内考虑如何充分利用寄存器的问题： l 尽可能地让该变量的值保留在寄存器中尽可能地让该变量的值保留在寄存器中 l 尽可能引用变量在寄存器中的尽可能引用变量在寄存器中

6、的值值 A在四元式在四元式i中被定中被定 ijAij A的定值点，这时我们称的定值点，这时我们称 jiA A 待用信息：若在一个基本块中，变量待用信息：若在一个基本块中，变量 值，在值，在 后面的四元式后面的四元式 中要引用中要引用值，且从值，且从 到到 之间没有其之间没有其 它对它对是四元式是四元式 中对变量中对变量的待用的待用 信息或称下次引用信息，同时也称信息或称下次引用信息，同时也称是活跃的，若是活跃的，若 A 被多次被多次 引用则可构成待用信息链与活跃信息链。引用则可构成待用信息链与活跃信息链。 可从基本块的出口由后向前扫描，对每个变量建立相应的待用可从基本块的出口由后向前扫描，对每

7、个变量建立相应的待用 信息链和活跃变量信息链。信息链和活跃变量信息链。 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 计算待用信息的算法：计算待用信息的算法： （1 1）符号表中增加）符号表中增加“待用信息待用信息”栏和栏和“活跃信息活跃信息”栏栏: : 对各基本块的符号表中的对各基本块的符号表中的“待用信息待用信息”栏和栏和“活跃信活跃信 息息”栏置初值，即把栏置初值，即把“待用信息待用信息”栏置栏置“非待用非待用”，对，对“活活 跃信息跃信息”栏按在基本块出口处是否为活跃而置成栏按在基本块出口处是否为活跃而置成“活跃活跃”或或 “非活跃非活跃”。这里假定变量都是活跃的，临时变量

8、都是非活。这里假定变量都是活跃的，临时变量都是非活 跃的。跃的。 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 （2 2）从基本块出口到基本块入口由后向前依次处理每个四）从基本块出口到基本块入口由后向前依次处理每个四 元式。对每个四元式元式。对每个四元式i:A := B op Ci:A := B op C，依次执行下述步骤：，依次执行下述步骤： a） ） 把符号表中变量把符号表中变量A的待用信息和活跃信息附加到四元式的待用信息和活跃信息附加到四元式i 上。上。 b） 把符号表中变量把符号表中变量A的待用信息栏和活跃信息栏分别置为 的待用信息栏和活跃信息栏分别置为 “非待用非待用”和

9、和 “非活跃非活跃”。 （由于在（由于在i 中对中对A的定值只能的定值只能 在在 i以后的四元式才能引用，因而对以后的四元式才能引用，因而对 i以前的四元式来说以前的四元式来说A 是不活跃也不可能是待用的）是不活跃也不可能是待用的） c） ） 把符号表中变量把符号表中变量B和和 C的待用信息和活跃信息附加到四元的待用信息和活跃信息附加到四元 式式 i上。上。 d） 把符号表中变量把符号表中变量B和 和 C的待用信息栏置为的待用信息栏置为“i”，活跃信，活跃信 息栏置为息栏置为“活跃活跃”。 注意，以上注意，以上a）和）和b），），c）和）和d）的次序不能颠倒。）的次序不能颠倒。 武汉理工大学计

10、算机科学系林泓武汉理工大学计算机科学系林泓 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 12.2.3 12.2.3 代码生成算法代码生成算法 基本块的代码生成算法基本块的代码生成算法: : 假设只有假设只有A:=B op CA:=B op C的四元式序列的四元式序列 A A 对每个四元式对每个四元式i: A:=B op Ci: A:=B op C，依次执行下述，依次执行下述 步骤：步骤： (1) (1) 以四元式以四元式i: A:=B op Ci: A:=B op C为参数，调用过程为参数，调用过程 getreg(i: A

11、:=B op C)getreg(i: A:=B op C)。从。从getreggetreg返回时，得返回时，得 到一寄存器到一寄存器R R，用它作存放，用它作存放A A现行值的寄存器；现行值的寄存器； (2) (2) 利用利用AVALUEBAVALUEB和和AVALUECAVALUEC，确定出，确定出B B和和C C现现 行值存放位置行值存放位置BB和和CC，如果其现行值在寄存器，如果其现行值在寄存器 中，则把寄存器取作中，则把寄存器取作BB和和CC； 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 其中假定其中假定d在基本块

12、的出口是活跃的。在基本块的出口是活跃的。 uvd utv cau bat cacabad + += = + += = - -= = - -= = - -+ +- -+ +- -= = : : : : )()()(: 源代码：源代码： 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 代码序列 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 例：赋值语句例：赋值语句 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 n1n2n7 n6 n4 n5 T4

13、T1 T3 T2 + - - + 从从DAG生成目标代码生成目标代码 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 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

14、 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列入表中列入表

15、中; (4) while n的最左子结点的最左子结点m不是叶结点并且其所有不是叶结点并且其所有 父结点均已列入表中父结点均已列入表中do (5) begin将将m列入表中列入表中; (6) n: =m (7) end (8) end 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 t8:=d+e t6:=a+b t5:= t6 c t4:= t5 * t8 t3:= t4 e t2:= t6 +t4 t1:= t2 *t3 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 基于树重写的代码生成基于树重写的代码生成 例例

16、:ai:=b+1 : = ind + Membconst1 ind + consti regsp constaregsp + + 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 regi+ADD Rj,Ri regiregj 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 (1) regi constcMOV #c, Ri (2) regi memaMOV a, Ri (3) mem MOV Ri, a (4) mem MOV Rj, *Ri (5) regi MOV c(Rj), Ri : = memaregi : = memaregj ind constcregj re

17、gi + 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 (6) regi ADD c(Rj), Ri (7) regi ADD Rj, Ri (8) regi INC Ri + regiind constcregj + + regicost1 + regiregj 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 : = ind+ Membconst1 ind + constiregSP reg0 + (1) Reg 0 consta MOV #a, R0 (7) reg 0 ADD SP, R0 + reg 0 regSP 武汉理工大学计算机科学系林泓武汉理工大学计算机科学系林泓 ind const i reg SP + + reg