目标代码生成

1、目标代码生成,编译技术之十一,主讲,鲁 斌,2,源程序,编译前端,中间,代码,代码优化,中间,代码,代码生成器,目标程序,符 号 表,代码生成器的位置,3,代码生成器的输入包括中间代码和符号表中的信息 目标代码一般有以下三种形式： 能独立执行的机器语言代码，所有地址均已定位（代真） 待装配的机器语言模块。当需要执行时，由连接装入程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码 汇编语言代码，尚须经过汇编程序汇编，转换成可执行的机器代码 代码生成器着重考虑两个问题 一是如何使生成的目标代码较短 二是如何充分利用计算机的寄存器，减少目标代码中访问存储单元的次数 这两个问题直接影响代码的

2、执行速度,4,1 基本问题,代码生成器的输入：中间代码和符号表信息 目标程序、指令选择、寄存器分配、计算顺序选择,5,2 目标机器模型,假定一个计算机有N个通用寄存器R0，R1,Rn-1，Op表示运算符，M表示内存单元，c表示常数，*表示间接寻址，变量名表示变量所在单元 指令形式有以下四种：,6,如果op是一目运算符，则op Ri, M的意义为： op(M)=Ri，其余类型可类推 指令的意义说明：,7,3 一个简单的代码生成器,简单的代码生成器（基本块内）：输入四元式的中间代码，输出计算机的目标代码 在一个基本块范围内考虑如何充分利用寄存器的问题,8,3.1 寄存器分配的原则,尽可能地让该变量

3、的值保留在寄存器中，尽可能引用变量在寄存器中的值 对于在基本块内不再被引用的变量所占用的寄存器应尽早释放，以提高寄存器的利用率,9,例如： T1:=B+C T2:=T1*D A:=T2+E 考虑了效率和充分利用寄存器的问题之后，代码生成器可以生成如下代码： (1) LD R, B (2) ADD R, C (3) MUL R, D (4) ADD R, E (5) ST R, A,10,3.2 待用信息链表法,目的：在基本块内还要被引用的变量尽可能保存在寄存器内 待用信息：若在一个基本块中，变量A在四元式i中被定值，在i后面的四元式j中要引用A值，且从i到j间没有A的其它定值，这时称j是四元式

4、i中对变量A的待用信息或下次引用信息，同时也称A是活跃的,11,若A被多次引用则可构成待用信息链与活跃信息链 可从基本块的出口由后向前扫描，对每个变量建立相应的待用信息链和活跃信息链,i : A:= . j: := A j是i中A的下次引用信息（在基本块之内）。,12,计算变量待用信息的算法,开始时，把基本块中各变量的符号表表项中的待用信息域置为“非待用”，并根据变量在基本块出口之后是否活跃，将活跃信息域置为“活跃”或“非活跃” 从基本块出口到基本块入口由后向前依次处理各个三地址语句。对每一个三地址语句 i：x：=y op z，依次执行下述步骤： 把当前符号表中变量x的待用信息和活跃信息附加到

5、语句i上 把符号表中x的待用信息和活跃信息分别置为“非待用”和“非活跃”,13,把当前符号表中变量y和z的待用信息和活跃信息附加到语句i上 把符号表中y和z的待用信息均置为i，活跃信息均置为“活跃” 注意: 以上次序不可颠倒，因为y和z也可能是x 例：W是基本块出口的活跃变量 T :=A-B U:=A-C V:=T+U W:=V+U,14,（1）T:=A+B （2）U:=A-C （3）V:=T+U （4）W:=V+U,名字 待用 活跃 T 无 非 A 无 非 B 无 非 C 无 非 W 无 活 U 无 非 V 无 非,W:无,活; U,V:无,非,无,非,4,4,活,活,U,V:4,活; T:

6、无,非,无,非,3,活,活,3,U:3,活; A,C:无,非,无,非,2,2,活,活,T:3,活; A:2,活; B:无,非,无,非,1,1,活,活,15,例11.1： 若用A，B，C，W表示变量，用T，U，V表示中间变量，有四元式如下： (1) T:=A-B (2) U:=A-C (3) V:=T+U (4) W:=V+U 设W是基本块出口的活跃变量，其名字表中的待用信息和活跃信息如下表，用“”表示“非待用”“非活跃”，用“Y”表示活跃。(1)(2)(3)(4)表示四元式序号。,16,待用信息和活跃信息：,17,表中“待用信息链”与“活跃信息链”的每列从左至右为每从后向前扫描一个四元式时相应

7、变量的信息变化情况，空白处为没变化 待用信息和活跃信息在四元式上的标记如下所示： (1) T(3,Y):= A(2,Y) B(,)(2) U(3,Y):= A(,) C(,)(3) V(4, Y):= T(,) + U(4,Y)(4) W(, Y):= V(, ) + U(, ),18,3.3 寄存器描述和地址描述,充分利用寄存器 尽可能地让变量的值保留在寄存器中（即不把该变量的值存到内存单元），直到该寄存器必须用来存放别的变量值或者已到达基本块出口为止 后续的目标代码尽可能地引用变量在寄存器中的值，而不访问内存 为随时掌握各寄存器的情况，设置两个数组： 寄存器描述数组RVALUE: 描述每个

8、寄存器当前的状况 如：RVALUERi=A, C：表示Ri的现行值是变量A，C的值 变量地址描述数组AVALUE：表示变量的存放情况 如：AVALUEA=A, Ri：表示A 的值在寄存器Ri中，又在内存中,19,3.4 代码生成算法,假设只有A:=B op C的四元式序列，对每个四元式i: A:=B op C，依次执行下述步骤： 以四元式i: A:=B op C为参数，调用过程getreg(i: A:=B op C)。从getreg返回时，得到一寄存器R，用它作存放A现行值的寄存器 利用AVALUEB和AVALUEC，确定出B和C现行值存放位置B和C，如果其现行值在寄存器中，则把寄存器取作B和

9、C 如BR，则生成目标代码： LD R，B op R，C 否则，生成目标代码op R，C；如果B或C为R，则删除AVALUEB或AVALUEC中的R。,20,令AVALUEA=R，并令RVALUER=A，以表示变量A的现行值只在R中并且R中的值只代表A的现行值 如B或C的现行值在基本块中不再被引用，它们也不是基本块出口之后的活跃变量（由四元式i上的附加信息知道），并且其现行值在某个寄存器Rk中，则删除RVALUERk中的B或C以及AVALUEB或AVALUEC中的Rk，使该寄存器不再为B或C所占用,21,设GETREG是一个函数过程，它的参数是一个形如i: A:=B op C的四元式，每次调用

10、GETREG(i: A:=B op C)则返回一个寄存器R，用以存放A的结果值。对如何给出寄存器R，要用到四元式i上的待用信息，以使寄存器分配合理，对每个四元式的代码生成都要调用函数GETREG GETREG分配寄存器的算法为： 如果B的现行值在某寄存器Ri中，且该寄存器只包含B的值，或者B与A是同一标识符，或B在该四元式后不会再被引用，则可选取Ri作为所需的寄存器R，并转(4) 如果有尚未分配的寄存器，则从中选用一个Ri为所需的寄存器R，并转(4),22,从已分配的寄存器中选取一个Ri作为所需寄存器R，其选择原则为：占用该寄存器的变量值同时在主存中，或在基本块中引用的位置最远，这样对寄存器Ri所含的变量和变量在主存中的情况必须先做如下调整：即对RVALUERi中的每一变量M，如果M不是A且AVALUEM不包含M，则需完成以下处理 生成目标代码ST Ri, M，即把不是A的变量值由Ri中送入内存中 如果M不是B，则令AVALUEM=M，否则，令AVALUEM=M, Ri 删除RVALUERi中的