第九章 目标代码生成

1、第第9 9章章 目标代码生成目标代码生成n以源程序的中间代码作为输入，产生等价以源程序的中间代码作为输入，产生等价的目标代码作为输出，如图。的目标代码作为输出，如图。源程序编译前端中间代码代码优化中间代码代码生成器符号表目标程序b代码生成器的输入包括中间代码和符号表中的信息；b代码生成是把语义分析后或优化后的中间代码变换成目标代码。9.1 9.1 概述概述1. 1. 代码生成器的输入：代码生成器的输入：n源程序的中间表示：如三地址代码；源程序的中间表示：如三地址代码；n符号表中的信息：在数据区中的相对地址符号表中的信息：在数据区中的相对地址2. 2. 目标程序：目标程序：n绝对机器语言代码；绝

2、对机器语言代码；n可再定位机器语言代码；可再定位机器语言代码；n汇编语言程序。汇编语言程序。代码生成着重考虑两个问题：代码生成着重考虑两个问题：( 优化优化 )n如何使生成的目标代码较短；如何使生成的目标代码较短；n如何充分利用寄存器，减少目标代码访如何充分利用寄存器，减少目标代码访问存储单元的次数。问存储单元的次数。9.1 9.1 概述概述9.2 9.2 假想的目标机器模型假想的目标机器模型n采用一个模型作为目标机器：采用一个模型作为目标机器：n1 1、具有多个寄存器，、具有多个寄存器，regsregs可作为累加器或变址可作为累加器或变址器；具有四种类型的指令形式器；具有四种类型的指令形式类

3、型指令形式直接地址型 op Ri,M寄存器型 op Ri, Rj变址型 op Ri,c(Rj)间址型 op Ri,*M op Ri, *Rj op Ri,*c(Rj)运算符运算符opop包括：包括：ADDADD、SUBSUB、MULMUL、DIVDIV等等2 2、其它指令的意义：、其它指令的意义： 指令指令意义意义 LD Ri,B LD Ri,B (B) (B)RiRi ST Ri,B ST Ri,B (Ri) (Ri) B B J X J X 无条件转移到无条件转移到X X单元单元 CMP A,B CMP A,B 比较比较A A、B B单元的值，并根据单元的值，并根据ABAB分别置分别置CT

4、CT为为0 0或或1 1或或2 2 JX JX JX CT=2 CT=2 则转移则转移 J J X X CT=2 CT=2或或 CT=1CT=1则转移则转移9.3 9.3 简单代码生成器简单代码生成器功能：依次把每条中间代码变换成目标代码，功能：依次把每条中间代码变换成目标代码，并且在一个基本块的范围内考虑充分利用并且在一个基本块的范围内考虑充分利用寄存器。寄存器。例：例：A=(B+C)A=(B+C)* *D+ED+E中间代码：中间代码：T T1 1=B+C=B+CT T2 2= T= T1 1 * *D DA= TA= T2 2 +E +E(1) LD R,B(1) LD R,B(2) AD

5、D R,C(2) ADD R,C(3) ST R, T(3) ST R, T1 1(4) LD R, T(4) LD R, T1 1(5) MUL R,D(5) MUL R,D(6) ST R, T(6) ST R, T2 2(7)LD R, T(7)LD R, T2 2(8)ADD R,E(8)ADD R,E(9)ST R,A(9)ST R,A例：例：(1) LD R,B(1) LD R,B(2) ADD R,C(2) ADD R,C(3) ST R, T(3) ST R, T1 1(4) LD R, T(4) LD R, T1 1(5) MUL R,D(5) MUL R,D(6) ST R

6、, T(6) ST R, T2 2(7)LD R, T(7)LD R, T2 2(8)ADD R,E(8)ADD R,E(9)ST R,A(9)ST R,A(1) LD R,B(1) LD R,B(2) ADD R,C(2) ADD R,C(5) MUL R,D(5) MUL R,D(8)ADD R,E(8)ADD R,E(9)ST R,A(9)ST R,A为了能够进行上述优化为了能够进行上述优化, ,代码生成器必须了解代码生成器必须了解一些信息：一些信息：9.3.1 9.3.1 待用信息与活跃信息待用信息与活跃信息n变量在基本块内的待用信息：从基本块的变量在基本块内的待用信息：从基本块的出口

7、由后向前扫描，对每个变量建立相应出口由后向前扫描，对每个变量建立相应的待用信息链和活跃变量信息链。的待用信息链和活跃变量信息链。简化：基本块中的所有临时变量均看作基本简化：基本块中的所有临时变量均看作基本块出口之后的非活跃变量；所有非临时变块出口之后的非活跃变量；所有非临时变量均看作基本块出口之后的活跃变量。量均看作基本块出口之后的活跃变量。计算变量待用信息的算法：计算变量待用信息的算法：例例 考察基本块考察基本块(1)T=A-B (2)U=A-C (3)V=T+U (4)W=V+U(1)T=A-B (2)U=A-C (3)V=T+U (4)W=V+U(1)(1)开始时开始时, ,符号表中各变

8、量为符号表中各变量为“非待用非待用”, ,变量在出变量在出口之后是否活跃填入活跃信息栏口之后是否活跃填入活跃信息栏; ;(2)(2)从基本块出口到入口由后向前依次处理各个中间代从基本块出口到入口由后向前依次处理各个中间代码。对每一条代码码。对每一条代码 i: A:=B op Ci: A:=B op C，执行步骤：，执行步骤：把符号表中变量把符号表中变量A A的待用和活跃信息附加到中间代码的待用和活跃信息附加到中间代码i i上；上；把符号表中把符号表中A A的待用和活跃信息置为的待用和活跃信息置为“非待用非待用”、“非活非活跃跃”；把符号表中变量把符号表中变量B.CB.C的待用和活跃信息附加到中

9、间代码的待用和活跃信息附加到中间代码i i上；上；把符号表中把符号表中B.CB.C的待用信息置为的待用信息置为i i，活跃信息置为，活跃信息置为“活跃活跃”。寄存器描述和变量地址描述寄存器描述和变量地址描述1 1、在代码生成过程中，建立寄存器描述数组、在代码生成过程中，建立寄存器描述数组RVALUERVALUE，动态地记录各，动态地记录各regreg是空闲的、已分是空闲的、已分配给某个变量、或已分配给某几个变量。配给某个变量、或已分配给某几个变量。2 2、在代码生成过程中，建立变量地址描述数、在代码生成过程中，建立变量地址描述数组组AVALUEAVALUE，动态地记录各变量现行值的存，动态地记

10、录各变量现行值的存放位置：是在某个放位置：是在某个regreg中、在某主存单元中、中、在某主存单元中、或在某或在某regreg和主存单元中。和主存单元中。9.3.2 9.3.2 代码生成算法代码生成算法假设基本块中每个中间代码形式为假设基本块中每个中间代码形式为 A=B op CA=B op C。对每条中间代码对每条中间代码 i:A=B op Ci:A=B op C依次执行如下步骤：依次执行如下步骤：(1)(1)调用函数调用函数GETREG(i:A=B op C)GETREG(i:A=B op C)；(2)(2)利用地址描述数组利用地址描述数组AVALUEBAVALUEB和和AVALUECAV

11、ALUEC确定变量确定变量B B和和C C的现的现行值存放位置行值存放位置B B和和C C；(3)(3)如果如果B B R,R,则生成目标代码则生成目标代码: LD R,B: LD R,B op R,C op R,C ; ;否则否则生成目标代码生成目标代码 op R,Cop R,C ; ; 若若B B或或C C为为R,R,则删除则删除AVALUEBAVALUEB或或AVALUECAVALUEC中的中的R;R;(4)(4)令令AVALUEA=R ,AVALUEA=R ,并令并令RVALUER=A;RVALUER=A;(5)(5)如果如果B B和和C C的现行值在基本块中不再被引用，则释放所占用的

12、现行值在基本块中不再被引用，则释放所占用R RK K（即，删除（即，删除RVALUERRVALUERK K 中的中的B B或或C C以及以及AVALUEBAVALUEB中的中的R RK K ）。）。各中间代码对应的目标代码各中间代码对应的目标代码: :序号序号中间代码中间代码目标代码目标代码1A=B op CLD Ri,Bop Ri,C2A= op BLD Ri,Bop Ri,Ri3A=BLD Ri,B4A=BILD Rj,ILD Ri,B(Rj)5AI=BLD Ri,BLD Rj,IST Ri,A(Rj)序号序号 中间代码中间代码目标代码目标代码6goto XJ X7if A rop Bgo

13、to XLD Ri,ACMP Ri,BJ rop X8A=P LD Ri,*P9P =ALD Rj,AST Ri,*P注：处理完所有代码后，对现行值只在注：处理完所有代码后，对现行值只在regreg中，而在基本块的出口中，而在基本块的出口后是活跃的变量，要用后是活跃的变量，要用STST指令把值存放到主存单元中。指令把值存放到主存单元中。9.3.3 9.3.3 寄存器分配寄存器分配n有效利用寄存器，生成更高效的目标代码。有效利用寄存器，生成更高效的目标代码。指令的执行代价：指令访问主存单元次数指令的执行代价：指令访问主存单元次数+1+1如：如： op Ri,Rj op Ri,Rj 执行代价为执行

14、代价为1 1 op Ri,M op Ri,M 执行代价为执行代价为2 2 op Ri, op Ri,* *Rj Rj 执行代价为执行代价为2 2 op Ri, op Ri,* *M M 执行代价为执行代价为3 3n把变量把变量a a的值调入寄存器时，应替换哪个寄存的值调入寄存器时，应替换哪个寄存器的内容才能计算更快？器的内容才能计算更快？对于循环，把可用的几个寄存器固定分配给节省对于循环，把可用的几个寄存器固定分配给节省执行代价最多的那几个变量。执行代价最多的那几个变量。a:=b+c d:=d-b e:=a+ff:=a-db:=d+f e:=a-cb:=d+cB1B1B2B2B3B3B4B4b

15、cdfbcdfcdefcdefacdeacdeacdfacdfbdefbdefcdefcdefbcdefbcdefacdefacdef其其它它情情况况0 0值值且且在在B B的的出出口口之之后后如如果果M M在在基基本本块块B B中中1 1B B) )L LI IV VE E( (M M, ,引引用用M M的的次次数数基基本本块块B B中中对对M M定定值值前前B B) )U US SE E( (M M, ,B B) ) L LI IV VE E( (M M, ,* *2 2B B) ) U US SE E( (M M, ,L LB B是活跃的被定分配好寄存器后分配好寄存器后, ,就可以生成目

16、标代码。就可以生成目标代码。与简单代码生成器不同之处在于：与简单代码生成器不同之处在于：(1)(1)固定分配了寄存器的变量用相应固定分配了寄存器的变量用相应regreg表示；表示；(2)(2)循环前置结点中存值到寄存器；循环前置结点中存值到寄存器；(3)(3)循环出口结点中存值到主存单元；循环出口结点中存值到主存单元；(4)(4)循环中每个基本块的出口，未固定分配循环中每个基本块的出口，未固定分配regreg的变量按需要回存到主存单元，固定分的变量按需要回存到主存单元，固定分配了配了regreg的变量不须回存到主存单元。的变量不须回存到主存单元。a:=b+c d:=d-b e:=a+ff:=a

17、-db:=d+f e:=a-cb:=d+cB1B1B2B2B3B3B4B4bcdfbcdfcdefcdefacdeacdeacdfacdfbdefbdefcdefcdefbcdefbcdefacdefacdefLD RLD R0 0,d,dLD RLD R1 1,b,bST RST R0 0,d,dST RST R1 1,b,bST RST R0 0,d,dST RST R1 1,b,bB0B0B5B5B6B65 DAG5 DAG的目标代码的目标代码n对基本块中的中间代码序列，按怎样的次对基本块中的中间代码序列，按怎样的次序来生成目标代码？序来生成目标代码？例例 考查如下中间代码考查如下中间代

18、码序列序列G:G:T1=A+BT1=A+BT2=C+DT2=C+DT3=E-T2T3=E-T2T4=T1-T3T4=T1-T3改写为如下中间代码改写为如下中间代码序列序列G G: :T2=C+DT2=C+DT3=E-T2T3=E-T2T1=A+BT1=A+BT4=T1-T3T4=T1-T3DAGDAG的目标代码的目标代码G G的目标代码：的目标代码：1 LD R0,A1 LD R0,A2 ADD R0,B2 ADD R0,B3 LD R1,C3 LD R1,C4 ADD R1,D4 ADD R1,D5 ST R0,T15 ST R0,T16 LD R0,E6 LD R0,E7 SUB R0,R

19、17 SUB R0,R18 LD R1,T18 LD R1,T19 SUB R1,R09 SUB R1,R010 ST R1,T410 ST R1,T4G G的目标代码：的目标代码：1 LD R0,C1 LD R0,C2 ADD R0,D2 ADD R0,D3 LD R1,E3 LD R1,E4 SUB R1,R04 SUB R1,R05 LD R0,A5 LD R0,A6 ADD R0,B6 ADD R0,B7 SUB R0,R17 SUB R0,R18 ST R0,T48 ST R0,T4省去了省去了ST R0,T1ST R0,T1LD R1,T1LD R1,T1结论结论: :n对表达式对

20、表达式X=AX=A* *B+CB+C* *D D的求值的求值, ,从右往左算得到的从右往左算得到的目标代码较优。目标代码较优。n利用基本块的利用基本块的DAGDAG，将基本块的中间代码序列，将基本块的中间代码序列重新排列。重新排列。n给给DAGDAG中的中的N N个内部结点重新排序的算法：个内部结点重新排序的算法：接上页:n置初值；置初值；nFOR K=1 TO N DO TK=null;FOR K=1 TO N DO TK=null;ni=N;i=N;nWHILE WHILE 存在未列入存在未列入T T的内部结点的内部结点 DODOnBEGINBEGINn选一个未列入选一个未列入T T但其全部父结点均已入但其全部父结点均已入T T或无父结点的内部结或无父结点的内部结点点n;n;nTi=n; i=i-1Ti=n; i=i-1；nWHILE n