指令选择

把 IR 操作映射到目标机器指令——不是一一对应,而是树覆盖问题:用指令模式去匹配 IR 表达式树,找代价最小的覆盖方案。从贪心的 maximal munch 到动态规划,再到自动机化的 BURS。

概述

中间表示 是机器无关的——add i32 %a, %b。而目标机器有自己的指令集:x86-64 有 addl %eax, %ebx,ARM64 有 add w0, w1, w2,它们不只看操作码,还要考虑寻址模式、寄存器约束、指令组合。⁠指令选择(instruction selection) 就是把 IR 操作映射到目标机器指令序列。它不是一一对应的映射——一条 IR 指令可能对应多条机器指令(复杂操作被分解),也可能多条 IR 指令对应一条机器指令(复合寻址模式或融合指令)。

问题建模:树覆盖(tree tiling)

IR 被组织成表达式树⁠(每棵树代表一个计算,如 a[i] = x + 2 可以展开成一棵树)。目标机器的每条指令也描述为树形模式:

指令选择 = 用指令模式树去覆盖(tile)IR 树,使得每片叶子被恰好一块覆盖,且总代价最小。

这就是 tree tiling 问题——每条指令 i 有模式树 p_i、执行代价 c_i,找一个覆盖方案最小化总代价。

三种算法,代价与精度依次上升

1. 宏展开(macro expansion):最简

IR 操作 add → 直接输出 addl %src, %dst。不利用任何目标机特性,产出的代码明显差(如 load + add 分两条指令,而 CISC 有 add [addr], %reg)。但实现简单,用于 JIT 的 baseline 编译或代码大小不敏感的场景。

2. maximal munch:贪心,局部最优

从树根开始,选能覆盖当前子树的最大模式⁠(最多节点),对剩余部分递归:

munch(node):
    for each pattern from largest to smallest:
        if pattern matches at node:
            emit instruction for that pattern
            for each leaf in pattern that is a subtree root:
                munch(that leaf)
            return

• 贪心不保证全局最优,但实践中接近最优(因为机器指令模式通常不会"大得能吃进另一条指令的全部节点")。
• 复杂度 O(n),一遍扫描,适合 JIT 编译(如 V8 的 baseline compiler)。

3. 动态规划:全局最优

自底向上,对每个节点计算"覆盖以该节点为根的子树的最小代价":

for each node n in postorder:            ← 自底向上
    for each pattern p that matches at n:
        cost = p.cost + sum(minCost(leaf) for leaf in p.leaves)
        minCost[n] = min(minCost[n], cost)

然后自顶向下回溯,选择每个节点用的模式

• 保证找到全局最优覆盖(在给定的指令模式集和代价模型下)。
• 复杂度 O(n × |patterns|),对大多数 IR 树和指令集,|patterns| 在百量级,可接受。
• BURS(Bottom-Up Rewrite System) 把 dp 做进自动机——预计算"树匹配到状态→替换"的转换表,运行时 O(n)。但 BURS 构造复杂,LLVM 的 SelectionDAG 在多数目标机上使用 dp(非严格 BURS)。

指令选择的额外复杂性

多输出指令

divmod x, y 同一条指令产出一个商和一个余数——两个 IR 值,一条机器指令。树覆盖模型需要扩展为DAG 覆盖⁠(有向无环图,同一节点可被多棵树共享),此时贪心和 dp 都变复杂。

不定长指令集

x86-64 同一操作有多种编码:addl $1, %eax(3 字节) vs addl $1, (%esp)(4 字节)。指令选择不仅考虑"哪条指令",还考虑"用哪个变体"——寻址模式选择成为指令选择的一部分。

合法化(legalization)

有些 IR 指令组合,目标机不直接支持。在指令选择之前或期间,需要做合法化⁠:

IR:  store 64-bit value to address in reg
ARM64: 支持 64-bit store → 合法
16-bit MCU: 不支持 → 分解为两次 32-bit store (legalize)

LLVM 的 SelectionDAG 把合法化和指令选择交替做——LegalizeDAG pass 把不支持的操作分解为等价序列,SelectionDAG 再选指令。

Instruction Scheduling 与 Register Allocation 的干涉

指令选择之后,还有指令调度⁠(重排顺序降低流水线停顿)和寄存器分配⁠(IR 的虚拟寄存器→有限的物理寄存器)。这三者互相干涉:

指令选择: 选指令 → 定义了对寄存器的使用
指令调度: 重排顺序 → 改变了活跃区间
寄存器分配: 可能 spilling → 插入 load/store → 改变了指令序列

后两者在 寄存器分配 里展开。指令选择和寄存器分配之间有个相位排序问题:先分配寄存器再选指令(可能选了用不到该寄存器的指令),还是先选指令再分配(可能选完发现寄存器不够)。LLVM 的做法是:SelectionDAG 阶段隐式假设"虚拟寄存器无限"选指令,后由寄存器分配器处理 spilling。

参考

• Cooper/Torczon: "Engineering a Compiler", Chapter 11 (Instruction Selection)
• Cattell (1978): Formalization and Automatic Derivation of Code Generators (tree pattern matching 的早期工作)
• LLVM: lib/CodeGen/SelectionDAG/ — 工业级 dp-based 指令选择; lib/CodeGen/GlobalISel/ — 下一代 global 指令选择

Keywords: instruction selection, tree pattern matching, tiling, maximal munch, dynamic programming, BURS, macro expansion, legalization, lowering, SelectionDAG, GlobalISel, addressing mode, multi-output instruction, instruction scheduling interference