# 代码生成

## 概述与简单机器模型

1. 代码生成器的主要任务及问题
   - 指令选择：为中间表示语句选择适当的目标机器指令
   - 不考虑效率则十分简单
   - 同一中间代码可以由多组指令序列实现，不同实现效率差别大
   - 还需要考虑运算对象和结果如何存储
   - 寄存器分配和指派
     - 每个程序点决定哪些值在哪些寄存器中
     - 一个变量被存在哪个寄存器中
     - 寄存器获得运算分量比内存快，但寄存器数量有限
     - 高效利用寄存器可以减少 CPU 等待时间
   - 求值顺序
     - 计算执行的顺序会影响目标代码效率
     - 好的执行顺序可以使寄存器需求降低

2. 三地址机器模型
   - 目标机器指令集
   - 内存寻址方式
   - 通用寄存器数量
   - 运算分量类型
   - 可能有标签

3. 指令的代价
   - 指令代价简化为 1 + 指令源和目的寻址模式的附加代价
   - 寄存器寻址模式附加代价为 0
   - 设计内存位置或常数的寻址方式代价为 1

4. 寄存器与地址描述符
   - 寄存器描述符：寄存器当前存放的是哪些变量的值
   - 地址描述符：记录运行时每个名字的当前值存放在哪个或哪些位置，可能是寄存器、栈单元、内存地址或它们的集合，这些信息可以存放在变量名对应的符号表条目中

5. 基本块的收尾处理
   - 对于一个在基本块出口处可能活跃的变量 $x$，如果它的地址描述符表明它的值没有被存放在对应内存位置上，应生成指令将其存回内存中

6. 管理寄存器和地址描述符
   - 生成加载、保存和其他指令时，必须同时更新寄存器和地址描述符
   - `LD R, x`，修改 R 的寄存器描述符使只包含 x，修改 x 的地址描述符把 R 作为新增位置加入到 x 的位置集合中，从任何不同于 x 的地址描述符中删除 R
   - `OP Rx, Ry, Rz`，修改 Rx 的寄存器描述符使只包含 x，修改 x 的地址描述符使只包含位置 Rx，从任何不同于 Rx 的寄存器描述符中删除 x，从任何不同于 x 的地址描述符中删除 Rx
   - `ST x, R`，修改 x 的地址描述符使包含自己的内存位置
   - `x=y`，需要先为 x 和 y 分配同一个寄存器，除了之前 `LD Ry, y` 的操作外，还要修改 Ry 的寄存器描述符，使也包含 x，修改 x 的地址描述符使只包含 Ry

7. getReg 返回一个保存 x = y op z 值场所 L
   - 如果 y 在 R 中，且 R 不含其他名字值，并且执行本次之后不再有 y 的下次引用，直接返回 R 作为 L
   - 否则返回一个空闲寄存器
   - 如果没有空闲寄存器，且 x 在块中有下次引用，需要找一个已被占用的寄存器，将其值存回内存，然后返回该寄存器作为 L
   - 如果没有空闲寄存器，且 x 在块中不再引用，选择 x 的内存单元作为 L