编译原理教程 第九章 目标代码生成.ppt

第9章 目标代码生成 以源程序的中间代码作为输入，产生等价的目标代码作为输出，如图。 9.1 概述 1. 代码生成器的输入： 源程序的中间表示：如三地址代码； 符号表中的信息：在数据区中的相对地址 2. 目标程序： 绝对机器语言代码； 可再定位机器语言代码； 汇编语言程序。 代码生成着重考虑两个问题： 如何使生成的目标代码较短； 如何充分利用寄存器，减少目标代码访问存储单元的次数。 9.2 假想的目标机器模型 采用一个模型作为目标机器： 1、具有多个寄存器，regs可作为累加器或变址器；具有四种类型的指令形式 2、其它指令的意义： 9.3 简单代码生成器 功能：依次把每条中间代码变换成目标代码，并且在一个基本块的范围内考虑充分利用寄存器。 例： 为了能够进行上述优化,代码生成器必须了解一些信息： 9.3.1 待用信息与活跃信息 变量在基本块内的待用信息：从基本块的出口由后向前扫描，对每个变量建立相应的待用信息链和活跃变量信息链。 简化：基本块中的所有临时变量均看作基本块出口之后的非活跃变量；所有非临时变量均看作基本块出口之后的活跃变量。 计算变量待用信息的算法： 例 考察基本块 (1)T=A-B (2)U=A-C (3)V=T+U (4)W=V+U 寄存器描述和变量地址描述 1、在代码生成过程中，建立寄存器描述数组RVALUE，动态地记录各reg是空闲的、已分配给某个变量、或已分配给某几个变量。 2、在代码生成过程中，建立变量地址描述数组AVALUE，动态地记录各变量现行值的存放位置：是在某个reg中、在某主存单元中、或在某reg和主存单元中。 9.3.2 代码生成算法 假设基本块中每个中间代码形式为 A=B op C。 对每条中间代码 i:A=B op C依次执行如下步骤： (1)调用函数GETREG(i:A=B op C)； (2)利用地址描述数组AVALUE[B]和AVALUE[C]确定变量B和C的现行值存放位置B’和C’； (3)如果B’?R,则生成目标代码: LD R,B’ op R,C’ ;否则生成目标代码 op R,C’ ; 若B’或C’为R,则删除AVALUE[B]或AVALUE[C]中的R; (4)令AVALUE[A]={R} ,并令RVALUE[R]={A}; (5)如果B和C的现行值在基本块中不再被引用，则释放所占用RK（即，删除RVALUE[RK]中的B或C以及AVALUE[B]中的RK ）。 各中间代码对应的目标代码: 注：处理完所有代码后，对现行值只在reg中，而在基本块的出口后是活跃的变量，要用ST指令把值存放到主存单元中。 9.3.3 寄存器分配 有效利用寄存器，生成更高效的目标代码。 指令的执行代价：指令访问主存单元次数+1 如： op Ri,Rj 执行代价为1 op Ri,M 执行代价为2 op Ri,*Rj 执行代价为2 op Ri,*M 执行代价为3 对于循环，把可用的几个寄存器固定分配给节省执行代价最多的那几个变量。 节省代价计算公式： ?[USE(M,B)+ 2*LIVE(M,B)] B?L 其中，USE(M,B)=基本块B中对M定值前引用M的次数； LIVE(M,B)=1(当M在B中被定值且在B的出口之后是活跃的） 0（其他情况） 分配好寄存器后,就可以生成目标代码。 与简单代码生成器不同之处在于： (1)固定分配了寄存器的变量用相应reg表示； (2)循环前置结点中存值到寄存器； (3)循环出口结点中存值到主存单元； (4)循环中每个基本块的出口，未固定分配reg的变量按需要回存到主存单元，固定分配了reg的变量不须回存到主存单元。 5 DAG的目标代码 对基本块中的中间代码序列，按怎样的次序来生成目标代码？ DAG的目标代码 G的目标代码： 1 LD R0,A 2 ADD R0,B 3 LD R1,C 4 ADD R1,D 5 ST R0,T1 6 LD R0,E 7 SUB R0,R1 8 LD R1,T1 9 SUB R1,R0 10 ST R1,T4 结论: 对表达式X=A*B+C*D的求值,从右往左算得到的目标代码较优。 利用基本块的DAG，将基本块的中间代码序列重新排列。 给DAG中的N个内部结点重新排序的算法： 接上页: 置初值； FOR K=1 TO N DO T[K]=null; i=N; WHILE 存在未列入T的内部结点 DO BEGIN 选一个未列入T但其全部父结点均已入T或无父结点的内部结点n;