做个编译器——目标代码生成

General #

输入：已经经过了类型检查的无误的中间代码、符号表

输出：目标代码（汇编、绝对指令代码或可重定位目标代码）

主要需要考虑

• 目标机器的特点：例如如果机器具有inc指令，那么其效率就可以比用加法器+1来得高。
• 寄存器的管理：如何确定在给定的时间点下，哪些变量要驻留在寄存器（寄存器分配）、如何选择要驻留的寄存器（寄存器指派），从而减少访存次数。

如果仅考虑“能跑”，那么目标代码的生成是很容易的。但是如图，出现了很多的完全没有用的ST和LD，这些都要访存，会大大拖慢速度。T1、T2、T3作为中间临时变量，其不在此基本块外活跃了，让他们与内存进行交互就显得完全没有意义。

我们的目标代码生成是以基本块为单位的。我们依次把基本块中的每条四元式变成目标代码。

寄存器分配优化的目标代码生成 #

几点前提 #

• 假设在进入该基本块时，寄存器都是空闲状态。我们要实现的目标就是在该基本块内，最充分地利用寄存器来加速。
• 在退出基本块时，应当把仍然驻留在寄存器中的值存入主存。因为我们假设在基本块退出之后，寄存器被全部释放，这样后面的基本块也能在进入时，寄存器都是空闲的。
• 如果不特别说明，该基本块内的变量都不在该基本块外活跃。

目标 #

• 尽可能留：所有的计算结果尽量“晚写回”，能在寄存器中多待一会是一会
• 尽可能用：所有的指令尽量优先使用寄存器中的值，如果没有再去访存
• 及时腾空：离开基本块时必须写回所有寄存器，并腾空

要维护的信息 #

• 要知道四元式中的各变量在以后会不会被用到，如果用到是在哪里用到
  • 待用信息和活跃信息
• 要实时维护每个变量目前是存在寄存器中还是在内存中
  • 变量地址描述数组AVALUE以变量为索引，描述了该变量当前最新结果的位置
  • 例如AVALUE[C] = {R1, R2, C}，表示变量C的目前的最新结果在寄存器R1、R2和内存单元中都有
• 要实时维护每个寄存器的占用情况
  • 寄存器描述数组RVALUE以寄存器为下标，描述了该寄存器此时正在被谁占用
  • 例如RVALUE[R1]={A, B}，那么R1寄存器当前被A和B变量占用（这种情况说明A和B的值相同）。

左值 #

现在可以从三地址代码的层面来了解什么是“左值”。

左值就是可以出现在三地址代码“:=”左边的符号，就是这么简单！

待用信息和活跃信息 #

例如在基本块中，第i条四元式对变量A进行定制，第j条四元式对变量A进行了引用，且i和j之间的其他四元式没有其他对A进行定值操作，则j是i的一个待用信息。

换言之，待用信息就是“下一个引用点”。也就是“在i中对A的定值将来会在j中引用。”

需要注意，一定是引用点，而不是定值点。例如A有一个定值点，又接了一个定值点，然后是一个引用点，那么第一个定值点到第二个定值点之间，A是不活跃的。换言之它被引用点之前的最后一个定值点覆盖了。

所谓活跃信息就是变量在定值后，是否活跃（可能是在基本块外活跃，也可能是在基本块内活跃）。如果之后没有被引用就是不活跃的。这个“活跃”的概念和前面所述是一样的。

值得注意的是，待用信息一定是局限在基本块内的，但是活跃信息可以是在基本块外活跃，也可能是在基本块内活跃。

待用信息和活跃信息相辅相成。后者指出了变量会不会被引用，前者进一步指出了该变量会在何处被引用。

可以用二元组来表示待用信息和活跃信息。定义二元组(x,y)，x、y分别是待用信息和活跃信息。如果不活跃，则用^表示。例如(^,y)代表非待用，活跃；(3,y)代表在3号四元式处待用，活跃。

计算两种信息 #

采用从基本块的出口四元式到入口四元式这种逆序遍历的方式来进行计算。每次都要使用信息链中的最新的待用活跃信息。因为信息链会随着计算而被随时更新（每次在四元式表中填入一个信息，就要在信息链的相应的变量的链上面延长一下）。

定值语句优化 #

例如 A:=B 语句，如果在这个点上，B的AVALUE中有寄存器Ri，那么无需生成目标代码，而是把Ri的RVALUE加一个A进去，并且更新A的AVALUE为Ri即可。