1、编译原理第十一章第十一章 代码生成代码生成第十一章第十一章 代码生成代码生成n基本问题基本问题n目标机器模型目标机器模型n一个简单代码生成器一个简单代码生成器n代码生成代码生成是把语法分析后或优化后的中间代是把语法分析后或优化后的中间代码变换成目标代码。码变换成目标代码。n目标代码一般有以下三种形式：目标代码一般有以下三种形式：绝对指令代码：绝对指令代码：能够立即执行的机器语言代码，能够立即执行的机器语言代码，所有地址已经定位；所有地址已经定位；可重新定位指令代码：可重新定位指令代码：也是机器指令，但这些机也是机器指令，但这些机器指令中的地址分配是以模块为单位进行的，是器指令中的地址分配是以模
2、块为单位进行的，是相对于本模块的相对地址；这种代码必须经过相对于本模块的相对地址；这种代码必须经过链链接接程序，把若干个模块的这种可重定位的指令代程序，把若干个模块的这种可重定位的指令代码连接成一个绝对指令代码，要把相对地址通过码连接成一个绝对指令代码，要把相对地址通过这个链接程序变成绝对地址；这个链接程序变成绝对地址；汇编语言代码：汇编语言代码：尚须经过汇编程序汇编，转换成尚须经过汇编程序汇编，转换成可执行的机器语言代码。可执行的机器语言代码。n代码生成着重考虑的问题：代码生成着重考虑的问题：如何使生成的目标代码如何使生成的目标代码较短较短；如何充分利用计算机的如何充分利用计算机的寄存器寄存
3、器，减少目标代，减少目标代码中访问存贮单元的次数。码中访问存贮单元的次数。如何充分利用计算机的如何充分利用计算机的指令系统的特点指令系统的特点。11.1 基本问题基本问题 n代码生成器的输入代码生成器的输入 代码生成器的输入包括源程序的中间表示，以代码生成器的输入包括源程序的中间表示，以及符号表中的信息及符号表中的信息类型检查类型检查nx:=yi*j 其中其中x、y为实型；为实型；i、j为整型。这个赋值句产生的为整型。这个赋值句产生的三地址代码为：三地址代码为： T1:=i int* j T3:=inttoreal T1 T2:=y real+ T3 x:=T2 11.1 基本问题基本问题 n
4、目标程序目标程序 ：绝对机器代码、可再定位机器语言、汇编语言绝对机器代码、可再定位机器语言、汇编语言采用汇编代码作为目标语言采用汇编代码作为目标语言 n指令选择：指令选择：充分利用计算机的充分利用计算机的指令系统的特点指令系统的特点如如 a:=a+1/若机器有自加若机器有自加+指令，则选择自加指令指令，则选择自加指令INC a 来实现来实现nINC a/若机器上没有自加指令，则用以下三条指令来实现若机器上没有自加指令，则用以下三条指令来实现nLD R0, a ADD R0, #1 ST R0, a 11.1 基本问题基本问题 n寄存器分配寄存器分配 在在寄存器分配寄存器分配期间，为程序的某一点
5、期间，为程序的某一点选择驻留选择驻留在寄存器中的一组变量在寄存器中的一组变量。在随后的在随后的寄存器指派寄存器指派阶段，阶段，挑出变量将要驻留挑出变量将要驻留的具体寄存器的具体寄存器。n计算顺序选择：计算顺序选择：如果需要用到的数据刚好就是刚刚在如果需要用到的数据刚好就是刚刚在寄存器中算出来的数据，这样的计算顺序安排可节约访问寄存器中算出来的数据，这样的计算顺序安排可节约访问存储器的时间，从而提高效率存储器的时间，从而提高效率第十一章第十一章 代码生成代码生成n基本问题基本问题n目标机器模型目标机器模型n一个简单代码生成器一个简单代码生成器11.2 目标机器模型目标机器模型 n考虑一个抽象的计
6、算机模型考虑一个抽象的计算机模型具有多个通用寄存器，他们既可以作为累加器，具有多个通用寄存器，他们既可以作为累加器，也可以作为变址器。也可以作为变址器。运算必须在某个寄存器中进行。运算必须在某个寄存器中进行。含有四种类型的指令形式含有四种类型的指令形式类类 型型指令形式指令形式意义意义(设设 op 是二目运是二目运算符算符)直接地址型直接地址型op Ri, M(Ri) op (M) Ri寄存器型寄存器型op Ri, Rj(Ri) op (Rj) Ri变址型变址型op Ri, c(Rj)(Ri) op (Ri)+c) Ri间接型间接型op Ri, *Mop Ri, *Rjop Ri, *c(Rj
7、) (Ri) op (M) Ri(Ri) op (Rj) Ri(Ri) op (Rj)+c) Ri如果如果op是一目运行符，则是一目运行符，则“op Ri, M”的意的意义为：义为：op（M） Ri，其余类型可类推。其余类型可类推。op 包括一般计算机上常见的一些运算符，如包括一般计算机上常见的一些运算符，如ADD，SUB，MUL，DIV指指 令令意意 义义LD Ri, B把把 B 单元的内容取到寄存器单元的内容取到寄存器 R，即，即（B） RiST Ri, B把寄存器把寄存器 Ri的内容存到的内容存到 B 单元，即单元，即（Ri） BJ X无条件转向无条件转向 X 单元单元CMP A, B
8、把把 A 单元和单元和 B 单元的值进行比较，并根据比较单元的值进行比较，并根据比较情况把机器内部特征寄存器情况把机器内部特征寄存器 CT 置成相应状置成相应状态。态。 CT 占两个二进位。 根据占两个二进位。 根据 AB分别置分别置 CT 为为 0 或或 1 或或 2。J X如如 CT=0 转转 X 单元单元J X如如 CT=0 或或 CT=1 转转 X 单元单元J X如如 CT=1 转转 X 单元单元J X如如 CT1 转转 X 单元单元J X如如 CT=2 转转 X 单元单元J X如如 CT=2 或或 CT=1 转转 X 单元单元n不考虑代码的执行效率，目标代码生成不考虑代码的执行效率，
9、目标代码生成是不难的，例如：是不难的，例如：A:=(B+C)*D+E翻译为四元式：翻译为四元式：T1:=B+CT2:=T1*DT3:=T2+EA:=T3 11.3 一个简单代码生成器一个简单代码生成器G假设只有一个寄存器可供使用假设只有一个寄存器可供使用目标代码：目标代码： LD R0，BADD R0 ，CST R0 ，T1假设假设T1，T2，T3在基本块之在基本块之后不再引用后不再引用:LD R0，BADD R0，CMUL R0，DADD R0，EST R0，A 四元式四元式T1:=B+CT3:=T2+ET2:=T1*DA:=T3 LD R0 ，T1MUL R0，DST R0 ，T2LD R
10、0 ，T2ADD R0 ，EST R0 ，T3LD R0，T3 ST R0 ，A11.3 一个简单代码生成器一个简单代码生成器n四元式的中间代码变换成目标代码，并在一个四元式的中间代码变换成目标代码，并在一个基本块的范围内考虑如何充分利用寄存器：基本块的范围内考虑如何充分利用寄存器：尽可能留尽可能留：在生成计算某变量值的目标代码在生成计算某变量值的目标代码时，尽可能让该变量保留在寄存器中。时，尽可能让该变量保留在寄存器中。尽可能用：尽可能用：后续的目标代码尽可能引用变量后续的目标代码尽可能引用变量在寄存器中的值，而不访问内存。在寄存器中的值，而不访问内存。及时腾空及时腾空：在离开基本块时，把存
11、在寄存器：在离开基本块时，把存在寄存器中的现行的值放到主存中。中的现行的值放到主存中。11.3.1 待用信息待用信息n如果在一个基本块内，四元式如果在一个基本块内，四元式i对对A定值，定值，四元式四元式j要引用要引用A值，而从值，而从i到到j之间没有之间没有A的其他定值，那么，我们称的其他定值，那么，我们称j是四元式是四元式i的的变量变量A的的待用信息待用信息。（即下一个引用点）。（即下一个引用点）i: A:=B op Cj: D:=A op En假设在变量的符号表登记项中含有记录假设在变量的符号表登记项中含有记录待用信息和活跃信息的栏。待用信息和活跃信息的栏。n待用信息和活跃信息的表示：待用
12、信息和活跃信息的表示：1 (x,x)表示变量的待用信息和活跃信息。表示变量的待用信息和活跃信息。其中其中i表示待用信息表示待用信息，y表示活跃表示活跃，表示表示非待用和非活跃；非待用和非活跃；2 在符号表中，在符号表中，(x，x)(x，x)表示后面表示后面的符号对代替前面的符号对；的符号对代替前面的符号对；3 不特别说明，不特别说明，所有所有说明说明变量变量在基本块出在基本块出口之后口之后均为非活跃变量均为非活跃变量。例：基本块例：基本块1. T:=A-B2. U:=A-C3. V:=T+U4. W:=V+U设设W是基本块出口之后的活跃变量。是基本块出口之后的活跃变量。(4)W:=V+U(3)
13、V:=T+U(2)U:=A-C(1)T:=A-B(,y)(,)(,)(4,y)(,)(4,y)(3,y)(,)(,) (3,y)(2,y)(,) 序号序号 四元式四元式 左值左值 左操作数左操作数 右操作数右操作数n计算待用信息和活跃信息的算法步骤：计算待用信息和活跃信息的算法步骤：1. 开始时开始时，把基本块中各变量的符号表登，把基本块中各变量的符号表登记项中的待用信息栏填为记项中的待用信息栏填为“非待用非待用”，并并根据该变量在基本块出口之后是不是根据该变量在基本块出口之后是不是活跃的活跃的，把其中的活跃信息栏填为，把其中的活跃信息栏填为“活活跃跃”或或“非活跃非活跃”；2. 从基本块出口
14、到基本块入口从基本块出口到基本块入口由后向前由后向前依次处依次处理各个四元式。对每一个四元式理各个四元式。对每一个四元式i: A:=B op C，依次执行下面的步骤：依次执行下面的步骤： 1) 把符号表中变量把符号表中变量A的待用信息和活跃信息的待用信息和活跃信息附加到四元式附加到四元式i上；上； 2) 把符号表中把符号表中A的待用信息和活跃信息分别的待用信息和活跃信息分别置为置为“非待用非待用”和和“非活跃非活跃”； 3) 把符号表中变量把符号表中变量B和和C的待用信息和活跃的待用信息和活跃信息附加到四元式信息附加到四元式i上；上； 4) 把符号表中把符号表中B和和C的待用信息均置为的待用信
15、息均置为i，活活跃信息均置为跃信息均置为“活跃活跃”。例：基本块例：基本块1. T:=A-B2. U:=A-C3. V:=T+U4. W:=V+U设设W是基本块出口之后的活跃变量。是基本块出口之后的活跃变量。建立待用信息链表与活跃变量信息链表建立待用信息链表与活跃变量信息链表n附加在四元式上的待用附加在四元式上的待用/活跃信息表：活跃信息表：(4)W:=V+U(3)V:=T+U(2)U:=A-C(1)T:=A-B(,y)(,)(,)(4,y)(,)(4,y)(3,y)(,)(,) (3,y)(2,y)(,) 序号序号 四元式四元式 左值左值 左操作数左操作数 右操作数右操作数变量名变量名初始状
16、态初始状态信息链信息链(待用待用/活跃信息栏活跃信息栏) (3,y) (,) (2,y) (1,y) (1,y) (2,y) (4,y) (,) (3,y)T(,)A(,)B(,)C(,)U(,)V(,)W (,y) (,) (4,y) (,)n寄存器描述数组寄存器描述数组RVALUE动态记录各寄存器的使用信息动态记录各寄存器的使用信息RVALUER=A,Bn变量地址描述数组变量地址描述数组AVALUE动态记录各变量现行值的存放位置动态记录各变量现行值的存放位置AVALUEA=R1, R2, A寄存器描述和变量地址描述寄存器描述和变量地址描述n补充说明：补充说明：因为因为寄存器的分配寄存器的分
17、配是是局限于基本块范围之局限于基本块范围之内内的，一旦处理完基本块中所有四元式，的，一旦处理完基本块中所有四元式，对现行值在寄存器中的每个变量，如果它对现行值在寄存器中的每个变量，如果它在基本块之后是活跃的，则要把它存在寄在基本块之后是活跃的，则要把它存在寄存器中的值存放到它的主存单元中。存器中的值存放到它的主存单元中。要特别强调的是，对形如：要特别强调的是，对形如：A:=B的四元式，的四元式，如果如果B的现行值在某寄存器的现行值在某寄存器Ri中，则无须生中，则无须生成目标代码，只须在成目标代码，只须在RVALUE(Ri)中增加一中增加一个个A，(即把即把Ri同时分配给同时分配给B和和A)，并
18、把并把AVALUE(A)改为改为Ri 。n代码生成算法：代码生成算法：对每个四元式对每个四元式: i: A:=B op C，依次执行：依次执行： 1. 以四元式以四元式: i: A:=B op C 为参数，为参数，调用调用函数过程函数过程GETREG(i: A:=B op C)，返回返回一个寄存器一个寄存器R，用作存放用作存放A的寄存器。的寄存器。 2. 利用利用AVALUEB和和AVALUEC，确定确定B和和C现行值的存放位置现行值的存放位置B和和C。如果其如果其现行值在寄存器中，则把寄存器取作现行值在寄存器中，则把寄存器取作B和和C 3. 如果如果BR，则生成目标代码：则生成目标代码： L
19、D R, B op R, C 否则生成目标代码否则生成目标代码 op R, C 如果如果B或或C为为R，则删除则删除AVALUEB或或AVALUEC中的中的R。 4. 令令AVALUEA=R, RVALUER=A。 5. 若若B或或C的现行值在基本块中不再被引用，的现行值在基本块中不再被引用，也不是基本块出口之后的活跃变量，且其也不是基本块出口之后的活跃变量，且其现行值在某寄存器现行值在某寄存器Rk中，则删除中，则删除RVALUERk中的中的B或或C以及以及AVALUEB或或AVALUEC 中的中的Rk ，使得该寄存器不再，使得该寄存器不再为为B或或C占用。占用。及时腾空及时腾空n寄存器分配寄
20、存器分配：GETREG(i: A:=B op C) 返返回一个用来存放回一个用来存放A的值的寄存器的值的寄存器1 如 果如 果 B 的 现 行 值 在 某 个 寄 存 器的 现 行 值 在 某 个 寄 存 器 Ri中 ，中 ，RVALUERi中只包含中只包含B，此外，或者此外，或者B与与A是是同一个标识符同一个标识符，或者，或者B的现行值在执行四元式的现行值在执行四元式A:=B op C之后不会再引用之后不会再引用，则选取，则选取Ri为所需为所需要的寄存器要的寄存器R，并转并转4；2 如果有尚未分配的寄存器，则从中选取一个如果有尚未分配的寄存器，则从中选取一个Ri为所需要的寄存器为所需要的寄存
21、器R，并转并转4；1 尽可能用尽可能用B独占的寄存器独占的寄存器2 尽可能用空闲寄存器尽可能用空闲寄存器3 抢占用非空闲寄存器抢占用非空闲寄存器3 从已分配的寄存器中选取一个从已分配的寄存器中选取一个Ri为所需要的寄为所需要的寄存器存器R。最好使得最好使得Ri满足一下条件：满足一下条件： 占用占用Ri的变量的值也同时存放在该变量的贮存的变量的值也同时存放在该变量的贮存单元中，或者在基本块中要在最远的将来才会单元中，或者在基本块中要在最远的将来才会引用到或不会引用到。引用到或不会引用到。1 尽可能用尽可能用B所在的寄存器所在的寄存器2 后尽可能用空闲寄存器后尽可能用空闲寄存器3 抢占用非空闲寄存
22、器抢占用非空闲寄存器例：基本块例：基本块1.T:=A-B2.U:=A-C3.V:=T+U4.W:=V+U设设W是基本块出口之后的活跃变量，只有是基本块出口之后的活跃变量，只有R0和和R1是可用寄存器，生成的目标代码和相应是可用寄存器，生成的目标代码和相应的的RVALUE和和AVALUE:中间代码中间代码 目标代码目标代码 RVALUE AVALUET:=ABU:=ACV:=TUW:=VULD R0，ASUB R0，BR0含有含有TT在在R0中中LD R1，ASUB R1，CR0含有含有TR1含有含有UT在在R0中中U在在R1中中ADD R0，R1R0含有含有VR1含有含有UV在在R0中中U在在R1中中ADD R0，R1R0含有含有WW在在R0中中ST R0，W (4)W:=V+U(3)V:=T+U(2)U:=A-C(1)T:=A-B(,y)(,)(,)(4,y)(,)(4,y)(3,y)(,)(,) (3,y)(2,y)(,) 序号序号 四元式四元式 左值左值 左操作数左操作数 右操作数右操作数
