Summary:
- 基本块和流图
- 代码生成基本算法
- 寄存器分配
- 窥孔优化
设计问题
- 输入
- 中间表示形式
- 符号表信息
- 类型检查和转换已经完成
- 输出
- 汇编语言
- 内存管理
- 见 Ch7 中讨论的内存分配策略
- 指令集选择
- 寄存器分配
- allocation, assignment
- regiser-pair
- 计算顺序
- 代码生成方法
寻址方式开销：绝对 M (1)/寄存器 R (0)/索引 c(R) (1)/间接寄存器 *R (0)、间接索引 *c(R) (1)
指令开销：MOV R0,R1（1）/ MOV R5,M (2)/ ADD #1,R3 (2)/ SUB 4(R0),*12(R1) (3)
基本块和流图
把三地址码划分成基本块：
- 确定入口语句 leader
- 程序第一条语句
- 跳转的目的语句
- 跳转之后的第一条语句
- 每个 leader——下个 leader（或程序结尾）是一个基本块
基本块的变换可以提高代码质量
- 保结构变换：公共子表达式删除、无用代码删除、重命名临时变量、语句交换位置
划分基本块之后，命名，根据跳转语句（如果没有，就按顺序）建立逻辑转移关系，得到流图
下次引用信息
对语句 x:=y op z，从后往前扫描基本块，确定 x,y,z 下次使用的位置（确定变量的生存期），决定寄存器能否释放
计算下次引用信息：
- 记录每个变量的下次引用信息和活跃信息
- 假定临时变量在基本块出口后非活跃
- 非临时变量在出口后活跃
- 若临时变量跨基本块，假定其活跃
如果两个临时名字活跃期不重叠，就可以分配相同地址：
代码生成基本算法
每条 LLVM IR 指令 -> 目标语言指令；计算结果尽量存在寄存器里，除非
- 需要用寄存器进行其他计算
- 下面的语句是函数调用、转移、基本块结束
寄存器描述符：保存当前每个寄存器的内容
地址描述符：保存名字的地址（寄存器、栈位置、内存地址）
代码生成基本算法：
- 为计算结果分配位置 L (
getreg) - 提取操作数的值：查询其位置（地址描述符）
- 生成计算指令
- 更新计算结果的地址描述符和位置 L 的寄存器描述符
- 若操作数不再被引用，从寄存器描述符删除
- 如果是赋值语句
x:=y，且y不再被引用，则直接MOV y,x
- 如果是赋值语句
- 在基本块出口，需要将活跃名字值存入内存
getreg 算法，对 x:=y op z，为 x 分配位置 L，依次尝试：
- 占用 y 的寄存器
- y 的寄存器不包含其他名字；y 不再活跃、不再被引用
- 寻找空寄存器
- 寄存器替换
- 数组索引
- 已用寄存器 R，其中变量引用位置最远/已经存在内存中
- 内存
e.g.
寄存器分配
变量在点 p 处活跃：变量在 p 处的值在 p 或 p 之后还会用到
变量编号最小和最大的两个活跃点即其活跃区间
线性扫描寄存器分配（linear scan register allocation）算法：遍历每个活跃区间，分配物理寄存器
如果寄存器已满，则需要溢出到栈中，然后在操作该临时变量时插入对应的 load/store 指令（定义虚拟寄存器后 store 进内存里，使用前 load 其值），将该临时变量的活跃区间进行切分，以便重新进行寄存器分配。
窥孔优化
窥孔 peephole：一个滑动窗口
对窗口中的指令序列进行分析，如果存在性能更好的等价的指令序列，就替换
- 冗余 load/store 指令
- 不可达代码
- 控制流优化
- 代数优化
- 强度削弱：乘方变乘法，乘法变加法
需要得到更全局的信息，和数据流分析相结合；
回退滑动窗口/多次扫描