第七章目标代码生成ppt课件

1、第7章目的代码生成 代码生成是指把语法分析后或者优化后的中间代码(如四元式或三元式)变换成目的代码，所生成的目的代码普通有如下三种方式：(1) 可以立刻执行的机器言语代码，它们通常放在固定的存储区中并可直接执行，如PC机中后缀为或.EXE的文件。(2) 待装配的机器言语模块，其地址均为相对地址，所以不能直接执行。当需求执行时由衔接装配程序把它们与其它运转程序和库函数衔接起来，装配成可执行的机器言语代码，如PC机中后缀为.OBJ的文件都属于待装配的模块(文件)。(3) 汇编言语程序，必需经过汇编程序的汇编方可转换成可执行的机器言语代码，如PC机中后缀为.ASM的文件即为汇编言语程序。一个高级言语

2、程序的目的代码要经常、反复运用，因此代码生成要着重思索两个问题：一是如何使生成的目的代码较短，二是如何充分利用计算机的存放器以减少目的代码中访问存储单元的次数。生成的目的代码越短，存放器的利用越充分，目的代码的质量也就越高。设计一个代码生成器需求思索详细的机器构造、指令格式、字长及存放器个数和种类，并且与指令的语义和所用的操作系统、存储管理等都亲密相关。7.1 一个简单代码生成器一个简单的代码生成器，此生成器依次把每条中间代码变换成目的代码，并且在一个根本块范围内思索如何充分利用存放器的问题。一方面，在根本块中，当生成计算某变量值的目的代码时，尽能够地让该变量的值保管在存放器中(即不编出把该变

3、量的值存到内存单元的指令)，直到该存放器必需用来存放其它变量的值或已达根本块出口为止；另一方面，后续的目的代码尽能够地援用变量在存放器中的值而不访问内存。如一C言语语句A=(B+C)*D+E，翻译为四元式G：T1=B+CT2=T1*DA=T2+E假设不思索代码的效率，可以简单地把每条中间代码(四元式)映射成假设干条目的指令，如将x=y+z映射为MOV AX, y /*AX为存放器*/ADD AX, zMOV x, AX其中，x、y、z均为数据区的内存变量。上述四元式代码序列G可翻译为(1) MOV AX, B (2) ADD AX, C(3) MOV T1, AX(4) MOV AX, T1

4、(5) MUL AX, D(6) MOV T2, AX(7) MOV AX, T2(8) ADD AX, E (9) MOV A, AX 从正确性来看，这种翻译不存在问题，但却存在冗余。指令序列中的(4)和(7)两条指令是多余的；而T1、T2均是中间代码生成时产生的暂时变量，它们在出了根本块后将不再运用，故(3)、(6)两条指令也可删去。因此，在思索了效率和充分运用存放器之后，应生成如下代码：(1) MOV AX, B (2) ADD AX, C(3) MUL AX, D(4) ADD AX, E (5) MOV A, AX为了实现这一目的，代码生成器就必需了解一些信息：在产生T2=T1*D对

5、应的目的代码时，为了省去指令MOV AX, T1，就必需知道T1的当前值已在存放器AX中；为了省去MOV T1, AX，就必需知道出了根本块后T1不再被援用。7.1.1 待用信息与活泼信息在一个根本块内的目的代码中，为了提高存放器的运用效率，应将根本块内还要被援用的值尽能够地保管在存放器中，而将根本块内不再被援用的变量所占用的存放器尽早释放。每当翻译一条四元式如A=B op C时，需求知道在根本块中还有哪些四元式要对变量A、B、C进展援用，为此，需求搜集一些待用信息。在一个根本块中，四元式i对变量A定值，假设i后面的四元式j要援用A且从i到j的四元式没有其它对A的定值点，那么称j是四元式i中对

6、变量A的待用信息，同时也称A是活泼的。假设A被多处援用，那么构成了A的待用信息链与活泼信息链。为了获得每个变量在根本块内的待用信息和活泼信息，可从根本块的出口由后向前扫描，对每个变量建立相应的待用信息链与活泼信息链。假设没有进展数据流分析并且暂时变量不允许跨根本块援用，那么把根本块中的暂时变量均看作根本块出口之后的非活泼变量，而把一切的非暂时变量均看作根本块出口之后的活泼变量。假设某些暂时变量可以跨根本块运用，那么把这些暂时变量也看成根本块出口之后的活泼变量。假设变量的符号表内有待用信息和活泼信息栏，那么计算变量待用信息的算法如下：(1) 首先将根本块中各变量的符号表的待用信息栏置为“非待用，

7、对活泼信息栏那么根据该变量在根本块出口之后能否活泼而将该栏中的信息置为“活泼或“非活泼。(2) 从根本块出口到根本块入口由后向前依次处置各四元式。对每个四元式i：A=B op C依次执行以下步骤： 把符号表中变量A的待用信息和活泼信息附加到四元式i上； 把符号表中变量A的待用信息和活泼信息分别置为“非待用和“非活泼； 把符号表中变量B和C的待用信息和活泼信息附加到四元式i上； 把符号表中变量B和C的待用信息置为i，活泼信息置为“活泼。留意：以上次序不能颠倒，假设四元式出现A=op B 或者A=B方式，那么以上执行步骤完全一样，只是其中不涉及变量C。例7.1 调查根本块：(1) T=AB(2)

8、U=AC(3) V=T+U(4) D=V+U其中，A、B、C、D为变量，T、U、V为中间变量。试求各变量的待用信息链和活泼信息链。解答 我们根据计算变量待用信息的算法得到各变量的待用信息链和活泼信息链如表7.1所示。表中的“F表示“非待用或“非活泼，“L表示“活泼，(1)(4)分别表示根本块中的四个四元式。待用信息链和活泼信息链的每列从左到右为每行从后向前扫描一个四元式时相应变量的信息变化情况(空白处表示没有变化)。待用信息和活泼信息在四元式上的标志如下(每个变量都先去掉待用信息链和活泼信息链最右的值，然后由右向左依次援用所出现的值)：(1) T(3)L=A(2)LBFL(2) U(3)L=A

9、FLCFL(3) V(4)L=TFF+U(4)L(4) DFL=VFF+UFF7.1.2 代码生成算法为了在代码生成中进展存放器分配，需求随时掌握各存放器的运用情况，即它是处于空闲形状还是已分配给某个变量或已分配给某几个变量。通常用一个存放器描画数组RVALUE动态地记录各存放器的当前情况，并用存放器Ri的编号作为它的下标。此外，还需建立一个变量地址描画数组AVALUE来记录各变量现行值存放的位置，即其是在某存放器中还是在某内存单元中，或者同时存在于某存放器和某内存单元中，可以有如下表示：RVALUERi=A /*存放器Ri分配给变量A*/RVALUERi=A,B /*存放器Ri分配给变量A和

10、B*/RVALUERi= /*未分配*/AVALUEA=A /*表示A的值在内存中*/AVALUEA=Ri /*表示A的值在存放器Ri中*/AVALUEA=Ri,A/*表示A的值既在存放器Ri中又在内存中*/假设根本块中每个四元式的方式都是A=B op C，那么代码生成算法是对每个四元式i：A=B op C执行下述步骤：(1) 调用函数GETREG (i：A=B op C)前往存放A值结果的存放器R。(2) 经过地址描画数组AVALUE B和AVALUE C确定出变量B和变量C的现行值存放位置B和C；假设是存放在存放器中，那么把存放器取作B和C。(3) 假设BR，那么生成目的代码：MOV R,

11、 Bop R, C否那么生成目的代码：op R, C假设B或C为R，那么删除AVALUE B或AVALUE C中的R。(4) 令AVALUEA=R并令RVALUER=A，表示变量A的现行值只在R中且R中的值只代表A的现行值。(5) 假设B和C的现行值在根本块中不再被援用，它们也不是根本块出口之后的活泼变量且它们的现行值存放在存放器Rk中，那么删除RVALUE Rk中的B和C以及AVALUE B中的Rk，使存放器Rk不再为B和C所占用。函数GETREG(i：A=B op C)用来得到存放A的当前值的存放器R；其算法如下：(1) 假设B的现行值在某存放器Ri中，且该存放器只包含B的值，或者B和A是

12、同一标识符，或者B在该四元式之后不再被援用，那么选取Ri为所需存放器并转(4)。(2) 如有尚未分配的存放器，那么从中选取一个Ri为所需存放器并转(4)。(3) 从已分配的存放器中选取一个Ri为所需存放器R。选取原那么为：占用Ri的变量的值也同时放在内存中，或者该值在根本块中要在最远的位置才会援用到。这样，对存放器Ri所含的变量和变量在内存中的情况必需先做如下调整：对RVALUE Ri中的每一个变量M，假设M不是A或者M既是A又是C却不是B，而B又不在RVALUE Ri中，那么： 假设AVALUE Ri中不包含M，那么生成目的代码MOV M, Ri ； 当M不是A时，假设M是B或者M是C且同时

13、B也在RVALUE Ri中，那么令AVALUE M=M,R，否那么令AVALUE M=M； 删除RVALUE Ri中的M。(4) 给出R，前往。例7.2 对例7.1，假设只需AX和BX是可用存放器，用代码生成算法生成目的代码及其相应的RVALUE和AVALUE。解答 用代码生成算法生成的目的代码及其相应的RVALUE和AVALUE，如表7.2所示。对其它方式的四元式也可仿照上述算法生成其目的代码。这里特别要指出的是，对形如A=B的复写，假设B的现行值在某存放器Ri中，那么无需生成目的代码，只需在RVALUE Ri中添加一个A(即把Ri同时分配给B和A)，把AVALUE A改为Ri；而且假设其后

14、B不再被援用，还可把RVALUE Ri中的B和AVALUE B中的Ri删除。处置完根本块中一切的四元式后，对现行只在某存放器中的每个变量，假设它在根本块出口之后是活泼的，那么要用MOV指令把它在存放器中的值存放到数据区以它命名的内存单元中。为进展这一任务，我们利用存放器描画数组RVALUE来决议其中哪些变量的现行值在存放器中，再利用地址描画数组AVALUE来决议其中哪些变量的现行值尚不在其内存单元中，最后利用活泼变量信息来决议其中哪些变量是活泼的。例如，由例7.2的表7.2查RVALUE栏可知：U和D的值在存放器中，而从AVALUE栏知U和D的值都不在内存单元中，假设D在根本块出口之后是活泼变

15、量，那么在表7.2所生成的目的代码后面还要生成一条目的代码：MOV D, AX7.1.3 存放器分配7.1.4 源程序到目的代码生成例如以PC机的汇编言语作为目的代码，假定可用的存放器为AX、BX、CX和DX，那么一C言语源程序转换为四元式代码序列，然后再转换为目的代码程序(转换中不思索优化)的结果如下：(1) C言语源程序(部分)：while (ab)if (m=n) a=a+1;elsewhile (k=h)x=x+2;m=n+x*(m+y);(2) 四元式代码序列：100 (j, a, b, 102)101 (j, _, _, 117 )102 (j=, m, n, 104)103 (j

16、, _, _, 107 )104 (+, a, 1, T1)105 (=, T1, _ , a )106 (j, _, _, 112)107 (j=, k, h, 109 )108 (j, _, _, 112)109 (+, x , 2, T2 )110 (=, T2, _ , x )111 (j, _, _, 107 )112 (+, m, y, T3)113 (*, x, T3, T4 )114 (+, n , T4, T5)115 (=, T5, _ , m )116 (j , _, _, 100)(3) 目的代码程序(汇编言语程序)：; File: compile.asm; *data

17、 segment ; 定义数据段 h DW k DW m DW n DW x DW y DW a DW b DWdata ends ; 数据段定义终了; *code segment ; 定义代码段main proc far ; 程序的执行部分assum cs:code, ds:datastart:push dssub bx, bxpush bxmov bx, data ; 设置DS段为当前数据段mov ds, bx; 语句翻译由此开场：100: mov AX, a cmp AX, b jg 102101: mp 117102: mov AX, m cmp AX, n jge 104103: jmp 107104: mov AX, a add AX, 1D105: mov BX, AX mov a, BX ; 跳出根本块前保管存放器中已改动的变量值106: jmp 112107: mov AX, k cmp A