C++ 怎么编写一个支持寄存器分配与指令选择的极简代码生成器-C++-PHP中文网

寄存器分配必须先构建干扰图而非贪心选择：基于变量生命期重叠建边，需控制流合并、统一编号、溢出处理；指令选择应采用树模式匹配而非if-else；ir须用带唯一id和显式数据流的结构。

c++ 怎么编写一个支持寄存器分配与指令选择的极简代码生成器

寄存器分配必须先建图，不能直接贪心选寄存器

寄存器分配不是“哪个空闲用哪个”，而是要先构建干扰图（interference graph）：每个变量是一个节点，若两个变量在程序中存在生命期重叠（live range overlap），就在它们之间连一条边。LLVM 的 LiveIntervals 和 InterferenceGraph 是完整实现，但极简版只需手动做一次线性扫描，生成每个变量的 live_start 和 live_end（以指令序号计），再两两比较即可判断是否干扰。

常见错误是跳过生命期分析，直接按定义-使用顺序硬分配——这会导致静默错误：比如 r1 被 a 定义后又被 b 复用，但 a 尚未死亡，结果值被覆盖。

变量生命期必须基于控制流合并（哪怕只有直线代码，也要考虑 if 分支合并点）
函数参数、返回值、临时计算结果都算独立变量，需统一编号并参与图构建
物理寄存器数量有限（如 x86-64 只有 16 个通用寄存器），图着色失败时必须触发溢出（spill）：把变量存到栈帧，并插入 mov [rbp-8], rax / mov rax, [rbp-8]

指令选择要用树模式匹配，别手写 if-else 套娃

指令选择本质是把中间表示（如三地址码或 DAG）映射成目标指令。硬编码 if (op == ADD && lhs.is_reg() && rhs.is_imm()) emit("add rax, 42") 看似简单，但遇到 a + b * c 这种复合表达式就崩——你得递归判断子树是否可合并，而树匹配天然支持这种结构。

极简做法：为每条目标指令写一个模式，例如 x86-64 的 ADD64ri 模式可定义为 (add (reg) (imm)) → "add {dst}, {imm}"，然后对 IR 树做自底向上遍历，尝试在每个节点匹配所有模式，取最长匹配（即能覆盖最多子树的那个）。

模式优先级很重要：ADD64rr（寄存器+寄存器）和 ADD64ri（寄存器+立即数）不能模糊匹配，否则 r1 + 5 可能错选成 ADD64rr 再补一个加载立即数的指令
立即数范围受限（x86-64 的 add r64, imm32 中 imm32 是符号扩展的），匹配前必须检查 imm 是否在 [-2147483648, 2147483647] 内
没有匹配成功的节点（如浮点运算、除法）必须降级为调用运行时函数（call __div64），并确保调用约定（caller-saved/callee-saved 寄存器）不破坏已有分配

IR 设计决定后续所有复杂度，别用字符串拼接 AST

很多人从 struct Expr { string op; vector<expr> kids; }</expr> 开始，结果指令选择时要反复 op == "add" 字符串比较，寄存器分配时又得重新遍历找变量名——性能差且极易漏掉副作用（如 i++ + i 中 i 被读两次、写一次）。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

必须用带唯一 ID 和显式数据流的结构，例如：

struct Inst {
  enum Op { ADD, MUL, LOAD, STORE };
  Op op;
  int dst_id;        // 目标变量 ID（-1 表示无）
  vector<int> src_ids; // 源操作数变量 ID 列表
  int pos;           // 在指令序列中的位置（用于生命期计算）
};
</int>

这样寄存器分配可直接用 dst_id 和 src_ids 构建干扰关系；指令选择时每个 Inst 就是一个匹配节点，无需解析字符串。