《11目标代码生成.ppt》由会员分享，可在线阅读，更多相关《11目标代码生成.ppt（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、目标代码生成编译技术之十一主讲 鲁 斌源程序源程序编译前端编译前端中间中间代码代码代码优化代码优化中间中间代码代码代码生成器代码生成器目标程序目标程序符符 号号 表表 代码生成器的位置代码生成器的位置2v代码生成器的输入包括中间代码和符号表中的信息代码生成器的输入包括中间代码和符号表中的信息v目标代码一般有以下三种形式：目标代码一般有以下三种形式：能独立执行的机器语言代码，所有地址均已定位（代真）能独立执行的机器语言代码，所有地址均已定位（代真）待装配的机器语言模块。当需要执行时，由连接装入程序把待装配的机器语言模块。当需要执行时，由连接装入程序把它们和某些运行程序连接起来，转换成能执行的机器
2、语言代它们和某些运行程序连接起来，转换成能执行的机器语言代码码汇编语言代码，尚须经过汇编程序汇编，转换成可执行的机汇编语言代码，尚须经过汇编程序汇编，转换成可执行的机器代码器代码v代码生成器着重考虑两个问题代码生成器着重考虑两个问题n一是如何使生成的目标代码较短一是如何使生成的目标代码较短n二是如何充分利用计算机的寄存器，减少目标代码中访问存二是如何充分利用计算机的寄存器，减少目标代码中访问存储单元的次数储单元的次数n这两个问题直接影响代码的执行速度这两个问题直接影响代码的执行速度31基本问题基本问题v代码生成器的输入：中间代码和符号表信息代码生成器的输入：中间代码和符号表信息v目标程序、指令
3、选择、寄存器分配、计算顺序选择目标程序、指令选择、寄存器分配、计算顺序选择42 目标机器模型目标机器模型v假定一个计算机有假定一个计算机有N个通用寄存器个通用寄存器R0，R1,Rn-1，Op表示表示运算符，运算符，M表示内存单元，表示内存单元，c表示常数，表示常数，*表示间接寻址，变表示间接寻址，变量名表示变量所在单元量名表示变量所在单元v指令形式有以下四种：指令形式有以下四种：类类型型指令形式指令形式意意义义（设设op是二目运算是二目运算)直接地址型直接地址型Op Ri,M(Ri)op(M)=Ri寄存器型寄存器型Op Ri,Rj(Ri)op(Rj)=Ri变变址型址型Op Ri,c(Rj)(R
4、i)op(Rj)+C)=Ri间间接型接型Op Ri,*MOp Ri,*RjOp Ri,*c(Rj)(Ri)op(M)=Ri(Ri)op(Rj)=Ri(Ri)op(Rj)+c)=Ri5v如果如果op是一目运算符，则是一目运算符，则opRi,M的意义为：的意义为：op(M)=Ri，其余类型可类推其余类型可类推v指令的意义说明：指令的意义说明：指令指令意意 义义指令指令意意 义义LD Ri,B把把B单单元的内容取到寄存器元的内容取到寄存器R，即即（B）=RiJ BJX如如CT=0或或CT=1 转转X单单元元J X无条件无条件转转到到X单单元元J=X如如CT=1 转转X单单元元CMP A,B比比较较A
5、，B两个两个单单元的内容元的内容,将内部特将内部特征寄存器征寄存器CT置成相置成相应应状状态态(:2)JX如如CT1 转转X单单元元JX如如CT=2 转转X单单元元JX如如CT=2或或CT=1 转转X单单元元63一个简单的代码生成器一个简单的代码生成器v简单的代码生成器（基本块内）：输入四元式的中简单的代码生成器（基本块内）：输入四元式的中间代码，输出计算机的目标代码间代码，输出计算机的目标代码v在一个基本块范围内考虑如何充分利用寄存器的问在一个基本块范围内考虑如何充分利用寄存器的问题题73.1寄存器分配的原则寄存器分配的原则v尽可能地让该变量的值保留在寄存器中，尽可能引尽可能地让该变量的值保
6、留在寄存器中，尽可能引用变量在寄存器中的值用变量在寄存器中的值v对于在基本块内不再被引用的变量所占用的寄存器对于在基本块内不再被引用的变量所占用的寄存器应尽早释放，以提高寄存器的利用率应尽早释放，以提高寄存器的利用率8例如：例如：T1:=B+CT2:=T1*DA:=T2+E考虑了效率和充分利用寄存器的问题之后，代码生成器可考虑了效率和充分利用寄存器的问题之后，代码生成器可以生成如下代码：以生成如下代码：(1)LDR,B(2)ADDR,C(3)MULR,D(4)ADDR,E(5)STR,A93.2待用信息链表法待用信息链表法v目的：目的：在基本块内还要被引用的变量尽可能保存在在基本块内还要被引用
7、的变量尽可能保存在寄存器内寄存器内v待用信息：待用信息：若在一个基本块中，变量若在一个基本块中，变量A在四元式在四元式i中中被定值，在被定值，在i后面的四元式后面的四元式j中要引用中要引用A值，且从值，且从i到到j间没有间没有A的其它定值，这时称的其它定值，这时称j是四元式是四元式i中对变量中对变量A的的待用信息待用信息或或下次引用信息下次引用信息，同时也称，同时也称A是是活跃的活跃的10v若若A被多次引用则可构成待用信息链与活跃信息链被多次引用则可构成待用信息链与活跃信息链v可从基本块的出口由后向前扫描，对每个变量建立可从基本块的出口由后向前扫描，对每个变量建立相应的待用信息链和活跃信息链相
8、应的待用信息链和活跃信息链 i:A:=.j:=Aj是是i中中A的下次引用信息（在基本块之内）。的下次引用信息（在基本块之内）。11计算变量待用信息的算法计算变量待用信息的算法1.开始时，把基本块中各变量的符号表表项中的待用开始时，把基本块中各变量的符号表表项中的待用信息域置为信息域置为“非待用非待用”，并根据变量在基本块出口，并根据变量在基本块出口之后是否活跃，将活跃信息域置为之后是否活跃，将活跃信息域置为“活跃活跃”或或“非非活跃活跃”2.从基本块出口到基本块入口由后向前依次处理各个从基本块出口到基本块入口由后向前依次处理各个三地址语句。对每一个三地址语句三地址语句。对每一个三地址语句i：x
9、：=yopz，依次执行下述步骤：依次执行下述步骤：把当前符号表中变量把当前符号表中变量x的待用信息和活跃信息附加到语的待用信息和活跃信息附加到语句句i上上把符号表中把符号表中x的待用信息和活跃信息分别置为的待用信息和活跃信息分别置为“非待用非待用”和和“非活跃非活跃”12把当前符号表中变量把当前符号表中变量y和和z的待用信息和活跃信息附加到的待用信息和活跃信息附加到语句语句i上上把符号表中把符号表中y和和z的待用信息均置为的待用信息均置为i，活跃信息均置为活跃信息均置为“活跃活跃”v注意注意:以上次序不可颠倒，因为以上次序不可颠倒，因为y和和z也可能是也可能是x例：例：W是基本块出口的活跃变量
10、是基本块出口的活跃变量T:=A-BU:=A-CV:=T+UW:=V+U13（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活活3U:3,活;A,C:无,非无非22活活T:3,活;A:2,活;B:无,非无非11活活14例例11.1：若用若用A，B，C，W表示变量，用表示变量，用T，U，V表示中间变表示中间变量，有四元式如下：量，有四元式如下：(1)T:=A-B(2)U:=A-C(3)V:=T+U(4)W:
11、=V+U设设W是基本块出口的活跃变量，其名字表中的待用信息和活跃是基本块出口的活跃变量，其名字表中的待用信息和活跃信息如下表，用信息如下表，用“”表示表示“非待用非待用”“非活跃非活跃”，用，用“Y”表示活跃。表示活跃。(1)(2)(3)(4)表示四元式序号。表示四元式序号。15v待用信息和活跃信息：待用信息和活跃信息：变变量量名名待用信息待用信息/活活跃跃信息信息初初值值待用信息待用信息链链/活活跃跃信息信息链链T,3,Y,A,2,Y1,YB,1,YC,2,YU,4,Y3,Y,V,4,Y,W,Y,16v表中表中“待用信息链待用信息链”与与“活跃信息链活跃信息链”的每列从左的每列从左至右为每从
12、后向前扫描一个四元式时相应变量的信至右为每从后向前扫描一个四元式时相应变量的信息变化情况，空白处为没变化息变化情况，空白处为没变化v待用信息和活跃信息在四元式上的标记如下所示：待用信息和活跃信息在四元式上的标记如下所示：(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(,)173.3寄存器描述和地址描述寄存器描述和地址描述v充分利用寄存器充分利用寄存器n尽可能地让变量的值保留在寄存器中（即不把该变量的值存到内存尽可能地让变量的值保留在寄存器中（即不把该变量的值存到内存单元），直到该寄存器
13、必须用来存放别的变量值或者已到达基本块单元），直到该寄存器必须用来存放别的变量值或者已到达基本块出口为止出口为止n后续的目标代码尽可能地引用变量在寄存器中的值，而不访问内存后续的目标代码尽可能地引用变量在寄存器中的值，而不访问内存v为随时掌握各寄存器的情况，设置两个数组：为随时掌握各寄存器的情况，设置两个数组：n寄存器描述数组寄存器描述数组RVALUE:描述每个寄存器当前的状况描述每个寄存器当前的状况如：如：RVALUERi=A,C：表示表示Ri的现行值是变量的现行值是变量A，C的值的值n变量地址描述数组变量地址描述数组AVALUE：表示变量的存放情况表示变量的存放情况如：如：AVALUEA=
14、A,Ri：表示表示A的值在寄存器的值在寄存器Ri中，又在内存中中，又在内存中183.4代码生成算法代码生成算法v假设只有假设只有A:=BopC的四元式序列，对每个四元式的四元式序列，对每个四元式i:A:=BopC，依次执行下述步骤：依次执行下述步骤：以四元式以四元式i:A:=BopC为参数，调用过程为参数，调用过程getreg(i:A:=BopC)。从。从getreg返回时，得到一寄存器返回时，得到一寄存器R，用它作存放用它作存放A现行值的寄存器现行值的寄存器利用利用AVALUEB和和AVALUEC，确定出确定出B和和C现行值存放位置现行值存放位置B和和C，如果其现行值在寄存器中，则把寄存器取
15、作如果其现行值在寄存器中，则把寄存器取作B和和C如如BR，则生成目标代码：则生成目标代码：LDR，BopR，C否则，生成目标代码否则，生成目标代码opR，C；如果；如果B或或C为为R，则删除则删除AVALUEB或或AVALUEC中的中的R。19令令AVALUEA=R，并令并令RVALUER=A，以以表示变量表示变量A的现行值只在的现行值只在R中并且中并且R中的值只代中的值只代表表A的现行值的现行值如如B或或C的现行值在基本块中不再被引用，它们的现行值在基本块中不再被引用，它们也不是基本块出口之后的活跃变量（由四元式也不是基本块出口之后的活跃变量（由四元式i上的附加信息知道），并且其现行值在某个
16、寄上的附加信息知道），并且其现行值在某个寄存器存器Rk中，则删除中，则删除RVALUERk中的中的B或或C以及以及AVALUEB或或AVALUEC中的中的Rk，使该寄存器使该寄存器不再为不再为B或或C所占用所占用20v设设GETREG是一个函数过程，它的参数是一个形如是一个函数过程，它的参数是一个形如i:A:=BopC的四元式，每次调用的四元式，每次调用GETREG(i:A:=BopC)则返回一则返回一个寄存器个寄存器R，用以存放用以存放A的结果值。对如何给出寄存器的结果值。对如何给出寄存器R，要用到四元式要用到四元式i上的待用信息，以使寄存器分配合理，对每上的待用信息，以使寄存器分配合理，对
17、每个四元式的代码生成都要调用函数个四元式的代码生成都要调用函数GETREGvGETREG分配寄存器的算法为：分配寄存器的算法为：如果如果B的现行值在某寄存器的现行值在某寄存器Ri中，且该寄存器只包含中，且该寄存器只包含B的值，或者的值，或者B与与A是同一标识符，或是同一标识符，或B在该四元式后不会再被引用，则可选取在该四元式后不会再被引用，则可选取Ri作作为所需的寄存器为所需的寄存器R，并转并转(4)如果有尚未分配的寄存器，则从中选用一个如果有尚未分配的寄存器，则从中选用一个Ri为所需的寄存器为所需的寄存器R，并转并转(4)21从已分配的寄存器中选取一个从已分配的寄存器中选取一个Ri作为所需寄
18、存器作为所需寄存器R，其选择原则为：其选择原则为：占用该寄存器的变量值同时在主存中，或在基本块中引用的位置最占用该寄存器的变量值同时在主存中，或在基本块中引用的位置最远，这样对寄存器远，这样对寄存器Ri所含的变量和变量在主存中的情况必须先做如所含的变量和变量在主存中的情况必须先做如下调整：即对下调整：即对RVALUERi中的每一变量中的每一变量M，如果如果M不是不是A且且AVALUEM不包含不包含M，则需完成以下处理则需完成以下处理生成目标代码生成目标代码STRi,M，即把不是即把不是A的变量值由的变量值由Ri中送入内存中中送入内存中如果如果M不是不是B，则令则令AVALUEM=M，否则，令否
19、则，令AVALUEM=M,Ri删除删除RVALUERi中的中的M给出给出R，返回返回v处理完基本块中所有四元式之后，对现行值在某寄存器处理完基本块中所有四元式之后，对现行值在某寄存器R中中的每个变量的每个变量M，若它在出口之后是活跃的，则生成若它在出口之后是活跃的，则生成STR,M放到主存中放到主存中22例例11.2：T:=A-BU:=A-CV:=T+UW:=V+U其中假定其中假定W在基本块的出口是活跃的，只有在基本块的出口是活跃的，只有R0和和R1是是可用寄存器。用以上算法生成的目标代码如表所列可用寄存器。用以上算法生成的目标代码如表所列23v代码序列：代码序列：语语句句生成的代生成的代码码
20、 寄存器描述器寄存器描述器地址描述器地址描述器T:=AT:=AB BLD RLD R0 0,A,ASUB RSUB R0 0,B,B空寄存器空寄存器R R0 0包含包含T TT T在在R R0 0中中U:=AU:=AC CLD RLD R1 1,A,ASUB R1,CSUB R1,CR R0 0包含包含T TR R1 1包含包含U UT T在在R R0 0中中U U在在R R1 1中中V:=TV:=TU UADD RADD R0 0,R,R1 1R R0 0包含包含V VR R1 1包含包含U UV V在在R R0 0中中U U在在R R1 1中中W:=VW:=VU UADD RADD R0 0,R,R1 1R R0 0包含包含W WW W在在R R0 0中中ST RST R0 0,W,WW W在在R R0 0和存和存储储器中器中24