代码生成

抽离了与机器无关优化相关的内容 - 任务 - 指令选择：选择适当的指令实现 IR 语句 - 寄存器的分配和指派 - 指令排序：按照什么顺序安排指令的执行 - 输出 RISC、CISC 等

对目标机的约定¶

指令：
- 加载：LD dst, addr (把地址 addr 中的内容加载到 dst 所指的寄存器) 相当于进行了解引用
- 保存：ST x, r (把寄存器 r 中的内容保存到 x 中)
- 计算：OP dst, src 1, src 2 (把 src 1 和 src 2 中的值运算后将结果存放到 dst 中)
- 无条件跳转：BR L (控制流转向标号 L 的指令)
- 条件跳转：Bcond r, L (对 r 中的值进行测试，如果为真则转向 L)
寻址模式
- 变量 x：指向分配 x 的内存位置
- a (r)：地址是 a 的左值加上寄存器 r 中的值
- constant (r)：寄存器 r 中内容加上前面的常数即其地址
- *r：寄存器 r 的内容所表示的位置上存放的内容位置
- *constant (r)：寄存器 r 中内容加上常数所代表的位置上的内容所表示的位置
- 常数 #constant
docs/学校课程/课程/编译原理/作业/p10#^ae41a5|8.2.2&8.2.4

代码生成算法¶

根据三地址指令序列生成机器指令

寄存器分配和指派¶

主要的目标是减少加载和保存（IO）指令，即最大限度地利用寄存器
- 只有当运算分量不在寄存器中时，才从内存载入
- 尽量保证只有当寄存器中值不被使用时，才覆盖掉
寄存器描述符：跟踪各个寄存器都存放了哪些变量的当前值
地址描述符：各个变量的当前值存放在哪些位置上
寄存器分配：哪个值应该放在寄存器里
寄存器指派：值应该存放在哪个寄存器里
在循环中频繁使用的值存放在固定寄存器
- 可以通过使用计数的方法来估算把一个变量放到寄存器中会带来多大好处，然后根据这个估算来分配寄存器
Reg() 函数根据寄存器描述符和地址描述符等数据流信息，为三地址指令 I 选择最佳的寄存器，进一步决定了得到的机器指令的质量
代码生成同时更新寄存器和地址描述符
- 对于 LD R, x：R 寄存器描述符-只包含 x；x 地址描述符-添加 R 到地址集合；将 R 从其他变量的地址描述符中删除
- 对于 ST x, R：x 的地址描述符添加存储的内存地址
如果要使用的运算分量不在寄存器重并且没有空闲寄存器
- 寻找一个寄存器 R，其寄存器描述符表示 v 在 R 中
- 如果 v 还存储在其他位置，则直接替换
- v 就是运算结果并且不参与运算，直接替换
- 如果 v 之后不会被使用了，直接替换
- 否则需要生成 ST v 将 R 中存放的所有值逐一存储到内存 p12#^c39f28|8.6.5

窥孔优化¶

使用一个滑动窗口 (窥孔) 来检查目标指令，在窥孔内实现优化
- 冗余指令消除
- 控制流优化
- 代数化简
- 机器特有指令的使用

目标指令生成¶

同一个三地址指令可以使用多种机器指令实现，有时多个三地址指令可以使用一个机器指令实现
用树来表示中间代码，按照特定的规则不断覆盖这棵树并生成机器指令
- 即通过应用一个树重写规则序列来生成，称为一个树翻译方案
- 从一个抽象语法树（中间代码）翻译得到目标代码树（机器语言）
- 如果找到一个匹配的模板，那么输入树中匹配的子树将被替换为相应规则中的替换结点，并执行相应的动作
- 不断匹配，直到这颗树被规约成单个结点，或找不到匹配的模板为止
- 在此过程中生成的机器指令代码序列就是树翻译方案作用于给定输入树而得到的输出
- 这里使用栈寻址（局部变量，因此是相对 Rsp 的偏移量）