11目标代码生成

目标代码生成编译技术之十一主讲鲁斌2源程序编译前端中间代码代码优化中间代码代码生成器目标程序符号表代码生成器的位置3代码生成器的输入包括中间代码和符号表中的信息目标代码一般有以下三种形式：①能独立执行的机器语言代码，所有地址均已定位（代真）②待装配的机器语言模块。当需要执行时，由连接装入程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码③汇编语言代码，尚须经过汇编程序汇编，转换成可执行的机器代码代码生成器着重考虑两个问题一是如何使生成的目标代码较短二是如何充分利用计算机的寄存器，减少目标代码中访问存储单元的次数这两个问题直接影响代码的执行速度41基本问题代码生成器的输入：中间代码和符号表信息目标程序、指令选择、寄存器分配、计算顺序选择52目标机器模型假定一个计算机有N个通用寄存器R0，R1…,Rn-1，Op表示运算符，M表示内存单元，c表示常数，*表示间接寻址，变量名表示变量所在单元指令形式有以下四种：类型指令形式意义（设op是二目运算)直接地址型OpRi,M(Ri)op(M)=Ri寄存器型OpRi,Rj(Ri)op(Rj)=Ri变址型OpRi,c(Rj)(Ri)op((Rj)+C)=Ri间接型OpRi,*MOpRi,*RjOpRi,*c(Rj)(Ri)op((M))=Ri(Ri)op((Rj))=Ri(Ri)op(((Rj)+c))=Ri6如果op是一目运算符，则opRi,M的意义为：op(M)=Ri，其余类型可类推指令的意义说明：指令意义指令意义LDRi,B把B单元的内容取到寄存器R，即（B）=RiJX如CT=0转X单元STRi,B把寄存器R的内容存到B单元，即（Ri）=BJ≤X如CT=0或CT=1转X单元JX无条件转到X单元J=X如CT=1转X单元CMPA,B比较A，B两个单元的内容,将内部特征寄存器CT置成相应状态(:0,=:1,:2)J≠X如CT≠1转X单元JX如CT=2转X单元J≥X如CT=2或CT=1转X单元73一个简单的代码生成器简单的代码生成器（基本块内）：输入四元式的中间代码，输出计算机的目标代码在一个基本块范围内考虑如何充分利用寄存器的问题83.1寄存器分配的原则尽可能地让该变量的值保留在寄存器中，尽可能引用变量在寄存器中的值对于在基本块内不再被引用的变量所占用的寄存器应尽早释放，以提高寄存器的利用率9例如：T1:=B+CT2:=T1*DA:=T2+E考虑了效率和充分利用寄存器的问题之后，代码生成器可以生成如下代码：(1)LDR,B(2)ADDR,C(3)MULR,D(4)ADDR,E(5)STR,A103.2待用信息链表法目的：在基本块内还要被引用的变量尽可能保存在寄存器内待用信息：若在一个基本块中，变量A在四元式i中被定值，在i后面的四元式j中要引用A值，且从i到j间没有A的其它定值，这时称j是四元式i中对变量A的待用信息或下次引用信息，同时也称A是活跃的11若A被多次引用则可构成待用信息链与活跃信息链可从基本块的出口由后向前扫描，对每个变量建立相应的待用信息链和活跃信息链i:A:=………………….j:…:=…A…j是i中A的下次引用信息（在基本块之内）。12计算变量待用信息的算法1.开始时，把基本块中各变量的符号表表项中的待用信息域置为“非待用”，并根据变量在基本块出口之后是否活跃，将活跃信息域置为“活跃”或“非活跃”2.从基本块出口到基本块入口由后向前依次处理各个三地址语句。对每一个三地址语句i：x：=yopz，依次执行下述步骤：①把当前符号表中变量x的待用信息和活跃信息附加到语句i上②把符号表中x的待用信息和活跃信息分别置为“非待用”和“非活跃”13③把当前符号表中变量y和z的待用信息和活跃信息附加到语句i上④把符号表中y和z的待用信息均置为i，活跃信息均置为“活跃”注意:以上次序不可颠倒，因为y和z也可能是x例：W是基本块出口的活跃变量T:=A-BU:=A-CV:=T+UW:=V+U14（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:无,非}无非44活活{U,V:4,活;T:无,非}无非3活活3{U:3,活;A,C:无,非}无非22活活{T:3,活;A:2,活;B:无,非}无非11活活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待用信息和活跃信息：变量名待用信息/活跃信息初值待用信息链/活跃信息链T∧,∧3,Y∧,∧A∧,∧2,Y1,YB∧,∧1,YC∧,∧2,YU∧,∧4,Y3,Y∧,∧V∧,∧4,Y∧,∧W∧,Y∧,∧17表中“待用信息链”与“活跃信息链”的每列从左至右为每从后向前扫描一个四元式时相应变量的信息变化情况，空白处为没变化待用信息和活跃信息在四元式上的标记如下所示：(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(∧,∧)183.3寄存器描述和地址描述充分利用寄存器尽可能地让变量的值保留在寄存器中（即不把该变量的值存到内存单元），直到该寄存器必须用来存放别的变量值或者已到达基本块出口为止后续的目标代码尽可能地引用变量在寄存器中的值，而不访问内存为随时掌握各寄存器的情况，设置两个数组：寄存器描述数组RVALUE:描述每个寄存器当前的状况如：RVALUE[Ri]={A,C}：表示Ri的现行值是变量A，C的值变量地址描述数组AVALUE：表示变量的存放情况如：AVALUE[A]={A,Ri}：表示A的值在寄存器Ri中，又在内存中193.4代码生成算法假设只有A:=BopC的四元式序列，对每个四元式i:A:=BopC，依次执行下述步骤：①以四元式i:A:=BopC为参数，调用过程getreg(i:A:=BopC)。从getreg返回时，得到一寄存器R，用它作存放A现行值的寄存器②利用AVALUE[B]和AVALUE[C]，确定出B和C现行值存放位置B`和C`，如果其现行值在寄存器中，则把寄存器取作B`和C`③如B`≠R，则生成目标代码：LDR，B`opR，C`否则，生成目标代码opR，C`；如果B`或C`为R，则删除AVALUE[B]或AVALUE[C]中的R。20④令AVALUE[A]={R}，并令RVALUE[R]={A}，以表示变量A的现行值只在R中并且R中的值只代表A的现行值⑤如B或C的现行值在基本块中不再被引用，它们也不是基本块出口之后的活跃变量（由四元式i上的附加信息知道），并且其现行值在某个寄存器Rk中，则删除RVALUE[Rk]中的B或C以及AVALUE[B]或AVALUE[C]中的Rk，使该寄存器不再为B或C所占用21设GETREG是一个函数过程，它的参数是一个形如i:A:=BopC的四元式，每次调用GETREG(i:A:=BopC)则返回一个寄存器R，用以存放A的结果值。对如何给出寄存器R，要用到四元式i上的待用信息，以使寄存器分配合理，对每个四元式的代码生成都要调用函数GETREGGETREG分配寄存器的算法为：①如果B的现行值在某寄存器Ri中，且该寄存器只包含B的值，或者B与A是同一标识符，或B在该四元式后不会再被引用，则可选取Ri作为所需的寄存器R，并转(4)②如果有尚未分配的寄存器，则从中选用一个Ri为所需的寄存器R，并转(4)22③从已分配的寄存器中选取一个Ri作为所需寄存器R，其选择原则为：占用该寄存器的变量值同时在主存中，或在基本块中引用的位置最远，这样对寄存器Ri所含的变量和变量在主存中的情况必须先做如下调整：即对RVALUE[Ri]中的每一变量M，如果M不是A且AVALUE[M]不包含M，则需完成以下处理①生成目标代码STRi,M，即把不是A的变量值由Ri中送入内存中②如果M不是B，则令AVALUE[M]={M}，否则，令AVALUE[M]={M,Ri}③删除RVALUE[Ri]中的M④给出R，返回处理完基本块中所有四元式之后，对现行值在某寄存器R中的每个变量M，若它在出口之后是活跃的，则生成STR,M放到主存中23例11.2：T:=A-BU:=A-CV:=T+UW:=V+U其中假定W在基本块的出口是活跃的，只有R0和R1是可用寄存器。用以上算法生成的目标代码如表所列24代码序列：语句生成的代码寄存器描述器地址描述器T:=A－BLDR0,ASUBR0,B空寄存器R0包含TT在R0中U:=A－CLDR1,ASUBR1,CR0包含TR1包含UT在R0中U在R1中V:=T＋UADDR0,R1R0包含VR1包含UV在R0中U在R1中W:=V＋UADDR0,R1R0包含WW在R0中STR0,WW在R0和存储器中