目标代码生成是编译程序的最后一个工作阶段。其任务是把先行阶段所产生的中间代码转换为相应的目标代码。
 
        一般而言，构造一个高效的代码生成程序并不容易，因为代码生成总是与某一具体的目标计算机密切相关，很难找到一种对各编译程序都普遍适用的好的生成算法。然而我们仍应研究这一课题，因为，一个精巧的代码生成程序所产生的目标代码，在执行效率上，要比那些拙劣的代码生成程序所产生的目标代码要高得多。对于一个好的代码生成程序来说，通常我们要求它至少能做到如下两点：第一，使所生成的目标代码尽可能的短。第二，能较充分地发挥目标计算机可用资源的效率，如尽可能地使用执行速度较快的指令；充分利用计算机的寄存器或变址器，以节省访问内存的时间；等等。
 
1、目标代码的形式
 
代码生成程序所输出的目标程序可以有如下三种形式：
 
( 1 )、具有绝对地址的机器语言程序；
 
( 2 )、可浮动的机器语言程序；
 
( 3 )、汇编语言形式的程序。
 
       就所需花费的机器时间而言，应当说第一种形式的目标代码最为有效，因为它们在存储空间中有固定的位置，一旦产生出此种形式的目标程序之后，便可直接投入运行。其缺点是不能独立地完成源程序各程序块的编译，即使是供源程序调用的子程序也必须同时进行编译，因而灵活性较差。通常是在程序较短，而调试工作量较大的情况下，采用此种方式。
 
       第二种形式的目标程序由若干个目的模块组成，各个模块中都包含目标程序中的一部分代码，且这些代码可在存储空间进行浮动（即可将它们装入到存储空间的任何位置）。此外，在各目的模块中还含有一些连接信息（如本模块需引用的其它模块中的符号名或子程序入口名）。所以，对于此种形式的目标代码，需经过连接装入程序把它们和所需的运行子程序的目的模块连接起来之后，才能投入运行。这种目标代码结构无疑有较大的灵活性，故为许多编译程序所采用，惟执行连接装入程序本身需耗费一些时间。
 
       第三种形式的目标程序是让代码生成程序产生汇编语言形式的目标程序，比前两种方式容易实现一些，但需在编译完毕之后额外增加一个汇编目标程序的阶段。所以，尽管此种方式有某些优点，但并不是一种最好的方案。

             目标代码的生成与机器的硬件环境有关，所以有些语言不能跨平台的原因就在于编译时需要了解机器的寄存器等资源，不同的机器寄存器不同，导致代码需要二次编译。
 
             java语言由于是半编译半解释的语言，之所以能跨平台是因为在编译的阶段只生成java虚拟机能识别的中间代码，而不是目标代码，再由Java虚拟机来解释成机器码。
 
            目标代码的生成需要获取寄存器的个数和使用情况，这里需要用到寄存器选择算法。
 
            为了使目标代码的执行效率更高，需要设置两个数据结构：待用信息，活跃信息。在基本模块之内，记录各个变量的使用情况，然后根据待用信息来确定是否将寄存器的数据替换或者保留。活跃信息是在模块之外确定数据否需要保留或者替换。
 
            代码优化包括：代码外提，删除无用代码，删除公共子表达式等。
 
           代码外提：主要在循环结构中使用，这样能成倍的提高代码的运行效率。
 
           删除公共表达式： 对于相同的三地址代码可以进行合并，删除。
 
           删除无用代码： 对于一些临时变量和没有使用的代码可以进行删除。
 
        程序流图的画法：
 
                  
 
 

 
 
        DAG图代码优化方法：
 
                        
 
 

 
 

 
 

 
 

 
 
   
 

 
 
 
 
  

   代码生成阶段的主要任务是：
  
 
 
 
 
 
 
 正确答案: C   你的答案: 空 (错误)
 
 
 
  
把高级语言翻译成机器语言
 
 
 
 
 
  
把高级语言翻译成汇编语言
 
 
 
 
 
  
把中间代码变换成依赖具体机器的目标代码
 
 
 
 
 
  
把汇编语言翻译成机器语言
 
 
 
 
 
  
添加笔记
 求解答(25)
 收藏
 纠错
 
 
 
 

 
 

 
 
源码 ->（扫描）-> 标记 ->（语法分析）-> 语法树 ->（语义分析）-> 标识语义后的语法树 ->（源码优化）-> 中间代码 ->（代码生成）-> 目标机器代码 ->（目标代码优化）-> 最终目标代码
 
 

 

一、目标代码
 
 
实际目标代码：实际机器上的指令序列
 绝对地址机器代码；可重定位的机器代码； 汇编代码：
 
 
虚拟目标代码：虚拟机上的目标程序。
 在本地机器上具备虚拟机的解释器。
 
 
 
 
目标程序的生成和目标机是密切相关联的，也就是说目标机的结构、能力会直接影响我们生成目标程序的难易程度和质量。在实际中也有很多程序设计语言的编译过程并不是直接对具体的目标机生成目标代码，而是产生到一种类似于汇编的虚拟目标机上，然后由虚拟目标机的虚拟指令到具体目标机的转换。比如java语言，编译完到一个中间语言的形式，然后利用相对应的解释程序在不同的目标机进行解释和执行。
当前考虑的四元式的生成对象中没有具体的目标机，所以这里也使用虚拟目标机
 
 
二、虚拟目标机的指令系统
 
目标机指令系统的指令分成如下的形式：（汇编类似）
 
存取指令：LD ST
输入输出：IN OUT
运算型指令：ADD SUB MUL DIV GT GE...
转移型指令：JMP  JMPT JMPF
地址运算指令和块传递指令：LEA  MOVEB
 
存取指令：
 假定有若干通用的寄存器是可用的，可以把内存单元中的内容取到寄存器中，比如LD，另一个是把寄存器中的内容存到内存中，如ST
运算型指令：
 ADD R X，表示寄存器R中的内容+X中的内容，结果存在R中，其他的运算类似
转移性指令：
 要进行转移性操作，JUMP 地址 表示无条件转移，另外还有条件为真进行转移和条件为假进行转移，比方说 JUMPT R 地址L表示寄存器R中值为真的时候转移到L这个地址去执行，JUMPF R L表示R中为假的时候转移到L去执行
地址运算指令和块传递指令：
 一个起始位置和个数，对数组传送非常方便。给一个起始位置，然后给定一个数组的大小，这样通过一条语句就可以把数组的内容都传递过去
 
 
目前考虑的是如何将输入的四元式转换成目标指令，虚拟的目标指令和实际的汇编指令存在一定程度上的差别，某些语言可能不会直接提供某些运算的指令，可能通过一个宏汇编或者是其他方式来实现。但是现在都直接假定具有这种操作的方式。
 
若目标机指令集中有“自增”指令INC，就可以被高效地翻译为一条指令：INC a ;否则，按照前面的模式将被翻译为指令序列：
 
LD  R , a
ADD R , 1
ST  a , R
 
三、虚拟目标机的寄存器
 
寄存器是CPU内部的元件，寄存器拥有非常高的读写速度 ，它们可用来暂存指令、数据和位址。
 寄存器种类：累加器、变址器、通用寄存器等等
 在虚拟目标机中，取出几个寄存器作为地址计算专用的寄存器分别为SP、TOP、SP0；其他寄存器用R1、R2…表示
 
 
 
要考虑目标机中有哪些通用的寄存器，哪些可以作为累加器，哪些可以作为变址寄存器，可以使用某些寄存器专门执行想要的功能：
 
 
sp：程序运行时存储空间当前活动记录的首地址/调用链活动记录的首地址
top：第一个可用的存储单元的地址
sp0：记录静态存储器的首地址，sp0+偏移量就可以计算出静态变量分配在静态区的哪个位置
其他寄存器可以用R1、R2等表示
 
 
四、四元式转化为目标指令
 
 
 
在生成过程中，首先考虑的是单寄存器的情形，如果单寄存器的目标程序都可以完成的话，多个寄存器的目标程序的完成应该是没有任何问题的，所以只考虑单寄存器的情况，在不考虑优化的情况下，看如何将四元式等价的转化成目标指令（重复，不考虑效率，如何等价的翻译），在能够翻译过去之后，再考虑如何来提高目标程序的质量，如何来评价这些目标指令。
 四元式如何翻译？
 
 
在翻译的过程中，用到两个栈，第一个是标号定位的栈，有些定位性标号为了某些转移提供地址的，把没有用到的标号存在栈中，比方说while四元式可能是由嵌套的，在定位产生的时候，还没产生跳转指令，当前的while地址还没用到，为了让后面能用到，将这个地址保存下来，由于循环可能是嵌套的，所以用栈来保存，用L1来表示
第二个栈在有些产生跳转至零的时候，还不知道后面的转移地址，比如 do四元式，尚且不知道后面的转移地址，就要把这个指令地址存到栈里，以后知道转移地址以后，需要回填这个指令地址（回填地址技术）
 
 
标号定位栈L1：
 定位性标号是为了某些转移提供地址的，需要把暂时没用到的标号存在栈中，例如while四元式可以对应一个嵌套的循环，在定位产生时还没产生跳转指令，它的地址还没用到，为了让后面能用到需要用栈把标号保存下来
目标指令地址栈L2：
 在有些产生跳转指令的时候，转移地址暂时无法确定，例如do四元式，不知道后面的转移地址，则把当前目标指令地址存到栈里，在知道转移地址以后，回填这个指令地址。回填地址是编译中的一项非常重要的技术
 
每一条指令如何生成目标指令的翻译：
 

 ⚠️这里的x和y不是真正的x和y的值，而是x和y对应的指向符号表中的地址，是一个指针。如果是正常情况下的话直接是sp+offx，如果在不是本层的就是sp+display[L]+off。
 ⚠️如果x和y是间接变量需要用间接寻址，间接寻址方式使用*x，但是这里仍然使用x来表示，所以这里的x是一种概括所有能够找到x的各种寻址方式，为了表示简便而使用。
 
 
 第三类是输入输出四元式
 输入四元式一般是read，x 这对应的目标指令是两条：
 
IN R，把外部的数据输入到R中；
ST R x，把r中的存到x中去。
 
输出四元式是write x：
 
把x的值取到R中；
再用输出命令输出出去，第一条是取LD R x；OUT，R。
 
 
then x，实际上是要产生两条指令，先是要把x的值取到寄存器中，然后根据寄存器中的值来判断转移，ld R x，把x取到寄存器R中，第二条是跳转指令，如果r中是真，执行then的部分，假就跳过去，所以是jumpF R，地址，也就是寄存器R中的内容是跳转，但是现在要转移的地址是不确定的，还没有处理后面的指令，所以要转移到哪是不知道的，所以这个四元式的翻译时，要生成一条半的指令，第二个指令的跳转地址部分没有填上。
如何生成半条指令？
 指令有自己的格式，这里的操作码是确定的，第一个寄存器R地址也是确定的，即只有后面转移的地址是不确定的。所以前半部分全部生成，后半部分使用0代替，一旦后面出现合适的地址就填充进去。还要将当前这条指令保存到栈L2中，等到具体知道指令的地址时弹栈地址回填。
 ⚠️生成一条半指令；半条指令压入堆栈L2
 
 
else四元式:
 执行到else有两种情况：
 （1）一个是按照顺序执行完then的部分该到else了，但是因为这个时候if的条件判断是正确的，所以else部分应该被跳过，这时的else部分的地址已知，所以要产生一条跳转指令，但是这时候并不知道跳转到的地址，所以压入L2栈，等待后面的地址回填。
 （2）而于此同时上面的then如果跳过了，这个时候也知道上面的then的跳转部分应该转移到哪里了，所以可以将前面的then部分的跳转地址回填了。
 
回填地址具体怎么填？
 首先将L2栈顶的元素弹出，然后生成一条只有后面跳转地址部分为m+1，前面为0的一条指令，然后从L1栈中弹出之前的需要回填地址的指令两条指令相加得到完整的指令，当前地址已经回填完毕，将其从L2栈中去掉，
 
endif四元式：
 实际上不产生跳转指令，但是处理的时候要回填地址，因为出现endif的时候就知道前面的指令的跳转地址了，比如前面的else，就把endif当前的指令地址回填给L2，形成一条完整的指令然后退栈。
 
综上：
 
else就是一个完成回填指令的地址，另一个是生成半条指令，然后压栈；
endif不产生跳转指令，进行回填工作
 
 
关于while起到定位作用的解释：
 当循环结束之后要返回去，重新计算表达式的值是否继续执行循环，所以只起到一个定位的作用，要把它的地址存储起来，压入到L1栈中
 
 
do四元式：生成两条指令，把x取到寄存器R中，根据R中的值来决定是否进行循环，所以要产生一个跳转指令，jumpF R ，- ，假跳出循环，真执行循环体，但是注意跳出循环体跳转的地址未知，所以生成的半条指令，跟前面的一样，把这条指令的地址 ，压入L2栈。后面遇到地址再回填。
 
 
endwhile四元式：有两个作用，一个是产生一个跳转指令，无条件转移指令，转回去，转移地址是在L1栈里存着的栈顶元素，可以生成一个完整的跳转指令；第二个是回填地址，在do四元式的指令中不知道转移地址，现在知道了，所以把L2地址取出来，把跳转指令下一条地址回填到L2中栈顶跳转地址部分，构成一个完整的指令。
 

 
 
 
过程函数声明：
 
 
过程函数声明部分的四元式处理，有两个部分需要注意：
 
（entry，Q，...） // q过程的入口四元式，不产生任何指令
 需要将当前的地址存到Q的过程函数信息表中的入口项，每个函数或过程的信息表中含有很多的信息，其中有一项就是函数的入口地址，这个入口地址就是处理entry指令的时候需要填入函数信息表中的，这是当前四元式需要完成的翻译工作。
(endfunc,....)//过程结束的四元式
 
 
 
对于函数过程结束四元式，要做3类工作：
 
生成一组取命令，即恢复寄存器的现场信息，在过程活动记录中有一块存储区保存现场信息，存储函数调用之前的寄存器中的值，现在函数已经结束了要返回，就要把这些信息恢复回去，有若干条取寄存器指令的动作。由于目标机不一样，所以保存的寄存器数量多少也不好确定，只要知道这里是由一组取命令完成的就可以了。
由于函数已经结束了，要把当前的活动记录作废掉，也就是在栈区把栈顶元素去掉，实际上是由两个指令完成的，把sp和top两个指针挪一下位置就可以了，把当前的sp存给top，把老的sp传给sp，也就是当前活动记录中动态链指针那一项传个sp。由于对两个指针进行了调整，就相当于把这个活动记录推掉了，现在sp值的是当前的活动记录。
产生一条返回指令，根据之前存的返回地址要生成一个跳转指令。问题是sp和top都挪下来了，这个返回地址怎么找呢？原来是sp+1，现在是top+1就可以了.就产生一个jump[top+1]，这样就把这个翻译工作做完了。
 
函数调用的四元式处理：
 

 函数调用四元式的处理，分成两块，一个是传参数的四元式，一个是call四元式。注意的问题是参数传递有值引用和地址引用，一个传值 一个传地址，还有实参是直接变量还是间接变量，
 

 在调用之前需要把活动记录栈里面压一个新的活动记录，实际上这部分工作也可以在入口四元式上进行处理，在哪处理时间效率上是一样的，但是可能一个函数被调用多次的话，重复代码就多一些。
 
 
 
五、多寄存器的分配
 
 
之前考虑的都是单寄存器不考虑执行效率然后生成了相应的目标代码，现在如果考虑多寄存器的情况。单寄存器能够完成的多寄存器一定能够完成，只不过希望能够产生更高效的目标程序。构造函数查找寄存器的状态表，其中有寄存器的名字、状态（1-占用；0-空闲）。
现在有多个寄存器，不需要每次使用的时候都频繁的换入换出，当需要一个寄存器的时候查表寻找当前是否有空闲的寄存器然后将空闲的寄存器进行分配，按照之前的存取操作进行，把相应的寄存器的状态和占用者记录在这个表中。
 

 按照淘汰页的算法，实际上有一个最佳算法，在最远使用点的先淘汰，但是后面的程序执行情况是没法判定的，因此这个是做不到的，但是处理四元式的时曾经把它划分成很多个基本块，由于基本块里面的程序都是顺序执行的，因此在基本块内，可以找到最远使用点的，淘汰算法就可以按照最远使用点的先淘汰，特殊情况就是最远使用点都不在这个基本块里。比方说x123，都不在基本块里，只好随机淘汰一个，这样做可以达到局部最优，但是未必能达到全局最优。所以每结束一个基本块的时候，需要把寄存器中的所有内容，都存到对应的内存中去，把所有的寄存器都倒出来，这样多寄存器就可以实现了，达到一个寄存器分配的目的。
 
六、对目标程序的评价
 
在处理过程中，注意——能够不往内存中存取，是最好的。能在寄存器中，尽量不存到内存，不从内存中取值，特别是多寄存器的情形。比如x+y+z，取x到r ，r+y就还到r， 然后r+z就可以了，不用把x+y的结果存到t1，这样的话可以减少指令提高程序的效率。通过将一些运算的结果占用在寄存器里，不用往内存中存，利用在寄存器中的资源，达到减少访问内存的效果，特殊情形可能还有问题，比方说目标代码的优化和带副本的优化。因为有些变量如果是间接变量，或者是往间接变量中存一个值，可能会改变寄存器中某一个变量的值，这种时候就需要把寄存器中的值存回去，否则就可能会发生错误。
 
总结
 

 目标程序的生成
 
要考虑目标机的问题
如何把四元式翻译成目标程序
考虑优化的问题
如何高效的生成目标代码
 
⚠️符号表是一直存在的，到目标代码生成的过程中还一直存在，直到生成了目标代码它的作用就没有了。因为此时已经把变量都换成地址了，把该取该用的内容都取出来了，过程的入口地址已经填上了，等到call的时候，直接到那里找到生成目标指令就可以了。所以，在目标代码生成之后符号表就没用了，以后运行的就是目标程序