编译原理目标代码生成.ppt

《编译原理目标代码生成.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章目标代码生成7.1一个简单代码生成器7.2汇编指令到机器代码的翻译概述7.1一个简单代码生成器我们首先介绍一个简单的代码生成器，此生成器依次把每条中间代码变换成目标代码，并且在一个基本块范围内考虑如何充分利用寄存器的问题。一方面，在基本块中，当生成计算某变量值的目标代码时，尽可能地让该变量的值保留在寄存器中(即不编出把该变量的值存到内存单元的指令)，直到该寄存器必须用来存放其它变量的值或已达基本块出口为止；另一方面，后续的目标代码尽可能地引用变量在寄存器中的值而不访问内存。例如，一C语言语句为A=(B+C)*D+E，把它翻译为四元式G：T1=B+CT2=T1*

2、DA=T2+E如果不考虑代码的效率，可以简单地把每条中间代码(四元式)映射成若干条目标指令，如将x=y+z映射为：MOVAX,y/*AX为寄存器*/ADDAX,zMOVx,AX其中，x、y、z均为数据区的内存变量。这样，上述四元式代码序列G就可翻译为：(1) MOVAX,B(2) ADDAX,C(3) MOVT1,AX(4) MOVAX,T1(5) MULAX,D(6) MOVT2,AX(7) MOVAX,T2(8) ADDAX,E(9) MOVA,AX虽然从正确性来看，这种翻译不存在问题，但它却存在冗余。在上述指令序列中，(4)和(7)两条指令是多余的；而T1、T

3、2均是中间代码生成时产生的临时变量，它们在出了基本块后将不再使用，故(3)、(6)两条指令也可删去。所以，在考虑了效率和充分使用寄存器之后，应生成如下代码：(1) MOVAX,B(2) ADDAX,C(3) MULAX,D(4) ADDAX,E(5) MOVA,AX为了实现这一目的，代码生成器就必须了解一些信息：在产生T2=T1*D对应的目标代码时，为了省去指令MOVAX,T1，就必须知道T1的当前值已在寄存器AX中；为了省去MOVT1,AX，就必须知道出了基本块后T1不再被引用。7.1.1待用信息与活跃信息在一个基本块内的目标代码中，为了提高寄存器的使用效率，应将

4、基本块内还要被引用的值尽可能地保留在寄存器中，而将基本块内不再被引用的变量所占用的寄存器尽早释放。每当翻译一条四元式如A=BopC时，需要知道在基本块中还有哪些四元式要对变量A、B、C进行引用，为此，需要收集一些待用信息。在一个基本块中，四元式i对变量A定值，如果i后面的四元式j要引用A且从i到j的四元式没有其它对A的定值点，则称j是四元式i中对变量A的待用信息，同时也称A是活跃的；如果A被多处引用，则构成了A的待用信息链与活跃信息链。为了取得每个变量在基本块内的待用信息和活跃信息，可从基本块的出口由后向前扫描，对每个变量建立相应的待用信息链与活跃信息链。如果没有进

5、行数据流分析并且临时变量不允许跨基本块引用，则把基本块中的临时变量均看作基本块出口之后的非活跃变量，而把所有的非临时变量均看作基本块出口之后的活跃变量。如果某些临时变量能够跨基本块使用，则把这些临时变量也看成基本块出口之后的活跃变量。假设变量的符号表内有待用信息和活跃信息栏，则计算变量待用信息的算法如下：(1)首先将基本块中各变量的符号表的待用信息栏置为“非待用”，对活跃信息栏则根据该变量在基本块出口之后是否活跃而将该栏中的信息置为“活跃”或“非活跃”。(2)从基本块出口到基本块入口由后向前依次处理各四元式。对每个四元式i：A=BopC依次执行以下步骤：①把符号表中

6、变量A的待用信息和活跃信息附加到四元式i上；②把符号表中变量A的待用信息和活跃信息分别置为“非待用”和“非活跃”；③把符号表中变量B和C的待用信息和活跃信息附加到四元式i上；④把符号表中B和C的待用信息置为i，活跃信息置为“活跃”。例7.1考察基本块：(1) T=A−B(2) U=A−C(3) V=T+U(4) D=V+U其中，A、B、C、D为变量，T、U、V为中间变量，试求各变量的待用信息链和活跃信息链。[解答]我们根据计算变量待用信息的算法得到各变量的待用信息链和活跃信息链如表7.1所示。表中的“F”表示“非待用”或“非活跃”，“L”表示“活跃”，(1)～(4)

7、分别表示基本块中的四个四元式。待用信息链和活跃信息链的每列从左到右为每行从后向前扫描一个四元式时相应变量的信息变化情况(空白处表示没有变化)。表7.1例7.1的待用信息链和活跃信息链变量名待用信息活跃信息初值待用信息链初值活跃信息链TF(3)FFLLFAF(2)(1)LLBF(1)LLCF(2)LLUF(4)(3)FFLLFVF(4)FFLFDFFLF待用信息和活跃信息在四元式上的标记如下：(1) T(3)L=A(2)L− BFL(2) U(3)L=AFL− CFL(3) V(4)L=TFF+U(4)L(4) DFL=VFF+UFF7.1.2代码生成算法为了在代