指令选择

指令选择把 IR 中的操作组织为目标指令。一个 IR 操作可能展开成多条指令，多项 IR 计算也可能合并到一条指令中。目标不仅是操作名称相同，还包括位宽、符号扩展、内存顺序、异常和寄存器约束都符合语义。

从地址折叠开始理解

假设要从 base + index*4 + 8 读取一个 32 位值，x86-64 的寻址模式可能直接容纳基址、比例索引与位移，从而不必先把整个地址算进一个临时寄存器。

这个模式是否可用取决于比例因子、位移范围和寄存器约束。若地址还要被多个后续操作复用，单独计算地址也可能更合适。LEA 可以计算某些地址形式，但不读取该地址处的内存；不能因两者都写出方括号就混为 load。

树覆盖：在一个受限模型里选择组合

把纯表达式暂时看成树，机器模式覆盖树中一组操作，留下需要由其他模式生成的输入。覆盖要实现全部所需操作，并满足各边界值的表示要求，不是仅要求每片叶子被覆盖一次。

例如 add(mul(x,4),y) 可以用移位加加法，也可能用一条合适的 LEA。为每种模式赋予成本，就得到一个组合优化问题。但成本可能指指令数、字节数、延迟或其他估计，它们不一定一致。

三类选择方法

动态规划状态通常需要包含结果类别，例如某子树生成寄存器值、立即数还是可折叠内存操作数。只用 cost[node] 一个数字，可能丢失父模式所需的不同形式。

可把递推理解为：

cost(node, result_kind) = min(模式成本 + 各输入所需形式的成本)。

计算完成本后回溯模式，再按依赖顺序生成代码。一个根优先匹配算法也不能因此先执行使用结果的机器指令，再执行产生输入的指令；匹配顺序与发射执行顺序需要分开。

BURS 等方法可预计算部分树重写匹配，使运行时选择更高效。这并不意味着任意工业 DAG 选择器都在求动态规划意义的全局最优。

给成本一个数值，才知道“大模式”是否值得

考虑 add(mul(x,4),y)，假设 x、y 已在寄存器中，结果也需要寄存器。教学目标机有四种合法模式：乘常数 MUL4、左移 SHL2、普通 ADD，以及能覆盖整个表达式的 LEA4。这里的成本是人为定义的相加权重，⁠不是任何型号 CPU 的周期表⁠。

def select(cost):
    # mul(x,4) 子树可以由两种模式实现；叶子已在寄存器，成本为 0。
    child_cost, child = min((cost[op], (op,)) for op in ("MUL4", "SHL2"))
    candidates = [
        (child_cost + cost["ADD"], child + ("ADD",)),
        (cost["LEA4"], ("LEA4",)),
    ]
    return min(candidates)


assert select({"MUL4": 3, "SHL2": 1, "ADD": 1, "LEA4": 3}) == (2, ("SHL2", "ADD"))
assert select({"MUL4": 3, "SHL2": 1, "ADD": 1, "LEA4": 1}) == (1, ("LEA4",))

# 用模 2^32 无符号语义验证两种覆盖的数值结果。
mask = (1 << 32) - 1
for x in (0, 1, 1 << 30, mask):
    for y in (0, 7, mask):
        separate = (((x << 2) & mask) + y) & mask
        combined = (x * 4 + y) & mask
        assert separate == combined

第一组成本下，覆盖节点最多的 LEA4 得到 3，而两条小模式合计只需 2。第二组只把 LEA4 成本改成 1，选择就反转。动态规划的“最优”必须带着模式集合和成本定义一起理解；这也说明不能先断言一条指令最快，再倒推选择器应当选它。

这个小模型只保留寄存器结果一种状态。若常量 4 既能作为立即数参与某模式，也能先装入寄存器，二者应分别记账。立即数形式的成本可能是 0，但一个只接受寄存器的父模式不能直接消费它；需要加上物化常量的指令，不能拿子树最低数字无条件相加。

覆盖得更大，就一定更便宜吗？

递推式需要比较满足同一种结果形式的完整候选。下面把叶子寄存器成本约定为零，只比较三条合法覆盖，避免把指令条数与 CPU 周期混为一谈。改变 LEA 成本时，树没有变，但最小方案可能变。更一般的选择器还需按 reg、imm、memory 等结果形式分别记账，不能无条件复用子树的最低数字。

$$C(n,r)=\underset{p\Rightarrow (n,r)}{\min }\left(w(p)+\sum _{(c,r_c)\in \mathrm{inputs}(p)}C(c,r_c)\right)$$

DAG 与副作用：树模型之外的工作

真实 IR 常有共享值。若 x 被两个表达式使用，把 DAG 复制成两棵树可能重复计算；若重复的是内存访问或可能产生异常的操作，合法性还取决于语义。多结果指令也需要同时对应多个 IR 结果。

Load、store、volatile、atomic 和调用之间存在不能任意改变的依赖。把一个普通 load 折叠进算术指令，需要保证访问次数、执行路径和内存语义仍合法。Atomic 操作尤其不能因为目标缺少某位宽指令，就拆成几次普通读写。

合法化：先让操作能由目标支持的能力表达

目标不支持某种整数宽度、向量类型或算术操作时，可以扩展、拆分、降低为其他操作，或调用运行时辅助函数。比如宽整数加法可拆成低位相加与进位传播；内存拆分还要考虑大小端、对齐与原子性。

类型合法化和操作合法化可能互相产生新的机会或需求，后端因此常有多次合并与降低阶段。LLVM 的 SelectionDAG 与 GlobalISel 提供不同的表示和阶段组织，不应把 SelectionDAG 统称为“工业级全局最优 DP”。LLVM 代码生成、GlobalISel

宽整数拆分：不能只把高低两半各加一次

用两个 32 位 word 表示一个 64 位无符号整数：低位 a_lo 与高位 a_hi。低位和超过 32 位时产生进位，它必须进入高位计算。以下模型选择模 2^64 加法语义；若源语言要求溢出检查，还必须额外产生并处理最终进位或相应溢出条件。

mask32, mask64 = (1 << 32) - 1, (1 << 64) - 1


def add64_split(a, b):
    low_sum = (a & mask32) + (b & mask32)
    low, carry = low_sum & mask32, low_sum >> 32
    high = ((a >> 32) + (b >> 32) + carry) & mask32
    return (high << 32) | low


values = (0, 1, mask32, 1 << 32, mask64)
for a in values:
    for b in values:
        assert add64_split(a, b) == (a + b) & mask64
assert add64_split(mask32, 1) == 1 << 32

最后一个断言是最容易漏掉的边界：低半部分从全 1 变成 0，高半部分必须加 1。在支持进位链的目标上可以选择 ADD/ADC 一类指令；其他目标可能通过比较生成进位再相加。合法化给出了所需语义，具体指令序列仍由目标能力决定。

这里拆分的是纯寄存器算术，不代表可以把 64 位原子加法实现成两个普通 32 位存储。后一种操作还承担其他线程可观察的原子性，通常需要目标原子序列或运行时支持。LLVM Legalizer

把宽加法拆成两半，进位该从哪里过去？

低位和可以唯一分成“留下的低位”与“送到高位的进位”。把位宽缩小到两段 8 位后，这个分解能直接在数值表中核对。故意省掉低位进位的列用于构造反例，并不是第二种合法实现。最终高位进位是否可丢弃，则由本模型明确选定的模 2¹⁶ 语义决定。

$$a_l+b_l=2^{8}c+l,0\le l<2^8,h=(a_h+b_h+c)\mathrm{mod}{2}^8$$

与寄存器分配、调度共同决定结果

x86 的某些操作具有输入输出绑定，除法等指令还会使用隐式固定寄存器。选指令时即使使用虚拟寄存器，也不能忽略这些硬约束。

选一条复杂指令可能减少指令数，却增加关键路径延迟；提早计算能隐藏延迟，却延长值的活跃范围并导致 spill。后续寄存器分配插入的 load/store 又会改变最终性能。因此局部模式成本只是估计，不是对实际处理器时间的完整证明。

一个可观察的编译实验

unsigned load_element(const unsigned *a, unsigned long i) {
    return a[i + 2];
}

clang -O2 -S -masm=intel load_element.c -o load_element.s

在采用常见数据布局的 x86-64 Linux 目标上，可以观察地址中的比例 4 和位移 8 是否合并进加载指令。改变元素类型、访问形式或目标架构，比较生成结果，能看出选择与目标能力的关系。汇编具体样式随版本和选项变化，不应硬编码为唯一答案。

速查

检查一个选择是否合理，依次确认语义等价、编码合法、输入输出寄存器约束、共享值与副作用、成本目标，以及寄存器分配后的最终结果。

相关章节：寄存器分配、目标代码与 ABI。

参考

• LLVM Target-Independent Code Generator。
• LLVM GlobalISel。

Keywords: instruction selection, tree covering, DAG, maximal munch, BURS, legalization, addressing mode, cost model