编译原理第11章

1、第十一章第十一章 目标代码生成目标代码生成介绍实现简单代码生成器需要考虑的问题；介绍实现简单代码生成器需要考虑的问题；寄存器分配的原则；寄存器分配的原则；使用待用信息链的代码生成算法；使用待用信息链的代码生成算法；按减少执行代价的原则，为循环生成目标代码按减少执行代价的原则，为循环生成目标代码11.1 基本问题基本问题 11.1 基本问题基本问题 一、代码生成器在编译程序中的位置：一、代码生成器在编译程序中的位置：二、代码生成器的输入：中间代码及符号表信息；二、代码生成器的输入：中间代码及符号表信息； 三、代码生成器的输出：目标代码（绝对机器代码、可再定位机器三、代码生成器的输出：目标代码（绝

2、对机器代码、可再定位机器 代码、汇编语言代码）；代码、汇编语言代码）； 四、寄存器分配四、寄存器分配 1 1、寄存器分配期间、寄存器分配期间: :为程序选择一组要驻留在寄存器中的变量；为程序选择一组要驻留在寄存器中的变量； 2 2、寄存器指派阶段、寄存器指派阶段: :为变量指派具体寄存器；为变量指派具体寄存器； 五、选择计算顺序五、选择计算顺序 11.2 目标机器模型目标机器模型 11.2 目标机器模型目标机器模型 一、多个通用寄存器：也可做累加器和变址器；一、多个通用寄存器：也可做累加器和变址器； 二、指令类型：二、指令类型： 三、操作码三、操作码opop：ADD(ADD(加加) )、SUB

3、(SUB(减减) )、MUL(MUL(乘乘) )、DIV(DIV(除除) )； 11.2 目标机器模型目标机器模型 四、基本指令：四、基本指令： 1 1、LD RiLD Ri , B: , B: 把把B B单元的内容取到寄存器单元的内容取到寄存器RiRi，即，即 ( B )( B )RiRi； 2 2、ST RiST Ri , B: , B: 把寄存器把寄存器RiRi的内容存到的内容存到B B单元，即单元，即 ( Ri)( Ri)B B； 3 3、J X: J X: 无条件转向无条件转向X X单元；单元； 4 4、CMP A , B: CMP A , B: 把把A A单元和单元和B B单元的值

4、进行比较，并根据比较情况把机器内部单元的值进行比较，并根据比较情况把机器内部 特征寄存器特征寄存器CTCT置成相应状态。置成相应状态。CTCT占两个二进位，根据占两个二进位，根据ABAB分别分别 置置CTCT为为0 0或或1 1或或2 2； 5 5、J op X: J op X: 根据根据CTCT的状态转向的状态转向X X单元单元 （opop为为 、）；）； 11.3一个简单的代码生成器一个简单的代码生成器 11.311.3一个简单的代码生成器一个简单的代码生成器 一、功能：依次把每条中间代码转换成目标代码，并在基本块内一、功能：依次把每条中间代码转换成目标代码，并在基本块内 考虑充分利用寄存

5、器等问题；考虑充分利用寄存器等问题； 例：例：11.3一个简单的代码生成器一个简单的代码生成器 二、待用信息二、待用信息 1 1、含义：某变量被定值后，将在何处被引用；、含义：某变量被定值后，将在何处被引用； 2 2、获取待用信息的方法：从基本块的出口由后向前扫描，对每、获取待用信息的方法：从基本块的出口由后向前扫描，对每 个变量建立待用信息链和活跃变量信息链；个变量建立待用信息链和活跃变量信息链； 3 3、记录待用信息和活跃信息：符号表增待用信息和活跃信息栏；、记录待用信息和活跃信息：符号表增待用信息和活跃信息栏； 4 4、计算变量待用信息和活跃信息的算法：计算变量待用信息和活跃信息的算法：

6、 11.3一个简单的代码生成器一个简单的代码生成器 例：计算变量的例：计算变量的 待用信息和待用信息和 活跃信息活跃信息11.3一个简单的代码生成器一个简单的代码生成器 三、寄存器描述和地址描述三、寄存器描述和地址描述 1 1、寄存器描述数组、寄存器描述数组RValueRValue：记录寄存器使用情况：记录寄存器使用情况( (空闲或已分配空闲或已分配) ) 2 2、变量地址描述数组、变量地址描述数组AValueAValue：记录各变量现行值的存放位置：记录各变量现行值的存放位置( (在在 寄存器或内存单元寄存器或内存单元) )； 四、四、基本块内代码生成算法基本块内代码生成算法 对块内每个中间

7、代码对块内每个中间代码 i: A:= B op Ci: A:= B op C，依次执行：，依次执行：11.3一个简单的代码生成器一个简单的代码生成器 过程过程GetRegGetReg算法算法( (参数为参数为i:Ai:A:=B op C ,:=B op C ,返回存放返回存放A A值的寄存器值的寄存器R) R) 10.1 概述概述基本块内代码生成算法流程图：基本块内代码生成算法流程图：10.1 概述概述修改修改RValue和和AValue流程图流程图 :11.3一个简单的代码生成器一个简单的代码生成器 例：例：中间代码中间代码目标代码目标代码RValueRValueAValueAValueT:

8、= A BT:= A BLD R0 , ALD R0 , ASUB R0 , B SUB R0 , B R0R0含有含有T TT T在在R0R0中中U:= A CU:= A CLD R1 , ALD R1 , ASUB R1 , CSUB R1 , CR0R0含有含有T TR1R1含有含有U UT T在在R0R0中中U U在在R1R1中中V:= T + UV:= T + UADD R0 , R1 ADD R0 , R1 R0R0含有含有V VR1R1含有含有U UV V在在R0R0中中U U在在R1R1中中W:= V + UW:= V + UADD R0 , R1ADD R0 , R1R0R0

9、含有含有W WW W在在R0R0中中11.4寄存器分配寄存器分配 11.4寄存器分配寄存器分配 一、问题引入：如何有效的利用寄存器；一、问题引入：如何有效的利用寄存器； 1 1、基本块内：、基本块内： 运算对象的值在寄存器中运算对象的值在寄存器中, ,则把该寄存器作为操作数地址；则把该寄存器作为操作数地址； 尽可能把各变量的现行值保存在寄存器中；尽可能把各变量的现行值保存在寄存器中； 基本块中不再引用的变量所占用的寄存器及早释放；基本块中不再引用的变量所占用的寄存器及早释放； 2 2、循环内：、循环内： 按执行代价把寄存器固定分配给几个变量单独使用；按执行代价把寄存器固定分配给几个变量单独使用

10、；二、指令的执行代价二、指令的执行代价 1 1、定义：指令的执行代价、定义：指令的执行代价= =指令访问内存单元的次数指令访问内存单元的次数+1 +1 2 2、例：、例：op Ri,Riop Ri,Ri执行代价为执行代价为1 1；op Ri,Mop Ri,M执行代价为执行代价为2 2； op Ri,op Ri,* *RiRi执行代价为执行代价为2 2；op Riop Ri, ,* *M M执行代价为执行代价为3 3 3 3、应用：对循环中每个变量计算把某寄存器分配给它时执行代、应用：对循环中每个变量计算把某寄存器分配给它时执行代 价能节省多少，以决定寄存器的固定分配方案；价能节省多少，以决定寄

11、存器的固定分配方案； 11.4寄存器分配寄存器分配 三、计算节省的执行代价（相对于原算法）三、计算节省的执行代价（相对于原算法） 1 1、变量在基本块中被定值时，其值才存放在寄存器中、变量在基本块中被定值时，其值才存放在寄存器中寄存器固寄存器固 定分配给某变量定分配给某变量: :则变量在块中被定值前每引用一次就少访问则变量在块中被定值前每引用一次就少访问 一次内存（节省执行代价一次内存（节省执行代价1 1）；）； 2 2、若变量在基本块内被定值且在块出口之后活跃，则出基本块时、若变量在基本块内被定值且在块出口之后活跃，则出基本块时 要把在寄存器中的值存放到内存单元要把在寄存器中的值存放到内存单

12、元寄存器固定分配给变寄存器固定分配给变 量量: :则出基本块时无须把值写回内存单元则出基本块时无须把值写回内存单元( (节省执行代价节省执行代价2)2)； 3 3、由、由1 1、2 2得到如下公式得到如下公式( (对循环对循环L L中的变量中的变量M,M,若固定分它一寄存器若固定分它一寄存器, , 则每循环一次节省的执行代价）：则每循环一次节省的执行代价）：其中：其中：USE(M ,B)=USE(M ,B)=基本块基本块B B中对中对M M定值前引用定值前引用M M的次数；的次数； 1(1(如如M M在在B B中被定值且在中被定值且在B B出口之后活跃出口之后活跃) ) LIVE= LIVE=

13、 0( 0(其它情况其它情况) )LBBMLIVEBMUSE),(*2),(11.4寄存器分配寄存器分配 例：按减少执行代价的原则，为循环中的变量分配固定寄存器例：按减少执行代价的原则，为循环中的变量分配固定寄存器 ( (有三个可用寄存器有三个可用寄存器R0R0、R1R1、R2)R2)对变量对变量a:a: USE(a USE(a ,B1)=0 ,B1)=0； USE(aUSE(a ,B2)=1 ,B2)=1； USE(aUSE(a ,B3)=1 ,B3)=1； USE(aUSE(a ,B4)=0 ,B4)=0； LIVE(aLIVE(a ,B1)=1 ,B1)=1； LIVE(aLIVE(a

14、,B2)=0 ,B2)=0； LIVE(aLIVE(a ,B3)=0 ,B3)=0； LIVE(aLIVE(a ,B4)=0 ,B4)=0； 节省节省USE(a ,B)+2USE(a ,B)+2* *LIVE(aLIVE(a ,B)=1+1+2 ,B)=1+1+2* *1=4 1=4 对变量对变量b b、c c、d d、e e、f:f:分别节省分别节省6 6、3 3、6 6、4 4、4 4 于是，于是，R0R0分配给分配给d d，R1R1分配给分配给b b，R2R2可分配给可分配给aefaef中任一个；中任一个；11.4寄存器分配寄存器分配 四、生成循环的目标代码四、生成循环的目标代码 1 1、已固定分配寄存器的变量用、已固定分配寄存器的变量用 相应寄存器表示；相应寄存器表示； 2 2、若变量在循环入口前活跃、若变量在循环入口前活跃, ,则则 在入口前在入口前, ,生成把它们的值取生成把它们的值取 到相应寄存器中的目标代码到相应寄存器中的目标代码; ; 3