LLVM 指令选择深度工程：从 SelectionDAG 到 GlobalISel 的全链路剖析

指令选择（Instruction Selection）是编译器后端最核心的阶段之一——它把目标无关的中间表示（IR）转换为目标机器的原生指令。LLVM 历史上经历了 SelectionDAG ISel、Fast ISel、GlobalISel 三代架构，每一次演进都在解决前代的工程债务。本文深入拆解指令选择的完整流水线，重点分析 GlobalISel 的设计哲学、关键数据结构与实战调优手段。

一、为什么需要指令选择？

编译器后端的输入是 LLVM IR——一种带有无限寄存器的 SSA 形式中间表示。假设我们有如下 IR：

define i32 @addexample(i32 %a, i32 %b) {
entry:
  %sum = add i32 %a, %b
  %shl = shl i32 %sum, 2
  %result = add i32 %shl, 1
  ret i32 %result
}

在这个简单函数里，后端需要回答：这些 add、shl 操作分别映射到目标机器的哪条指令？需要几条？操作数如何分配到物理寄存器？是否可以用复杂指令（例如带位移的 ADD）合并多步操作？

指令选择本质上是一个覆盖（covering）问题：用目标指令的"模式"（pattern）去覆盖 IR 中的 DAG（有向无环图），同时满足寄存器约束、延迟约束和成本最优。

二、SelectionDAG：经典但充满历史包袱

2.1 数据流模型

SelectionDAG 是 LLVM 最成熟的指令选择框架。它的核心数据结构是 SelectionDAG——一个 DAG 节点图，每个节点是一个 SDNode，代表一条中间操作（如 add、load、store）。输入 IR 先被 SelectionDAGBuilder 转换为 SelectionDAG，然后经过以下阶段：

LLVM IR → Legalization → DAG Combine → Instruction Selection → Scheduling → RegAlloc

Legalization 把 IR 不支持的操作（如 64 位加法在 32 位目标上）拆分为目标支持的基本操作。DAG Combine 执行代数化简和强度消减（strength reduction），例如 x*4 优化为 x<<2。

2.2 模式匹配：TableGen 的 .td 文件

目标后端用 TableGen 语言（.td 文件）声明指令模式。以 ARM64 的 ADD 指令为例：

def : Pat<(add GPR32:$a, GPR32:$b), (ADDWrr GPR32:$a, GPR32:$b)>;
def : Pat<(add GPR32:$a, (shl GPR32:$b, (i32 imm:$shift))),
          (ADDWrs GPR32:$a, GPR32:$b, (i32 imm:$shift))>;

这些模式在编译为由 SelectionDAGISel 自动生成的 C++ 匹配代码时，会被转换成树模式匹配器（Tree Pattern Matcher），底层通过 SDNode 的 opcode 递归匹配。

2.3 SelectionDAG 的三大痛点

经过二十多年演进，SelectionDAG 的核心架构问题日益凸显：

1. 状态分叉的 DAG 节点：同一条 IR 指令在 Legalization 前后可能变成不同的 SDNode，维护状态一致性极其困难。
1. 非 SSA 形式：SelectionDAG 使用虚拟寄存器编号，但不是 SSA，导致后续需重新计算 SSA（通过 PHI 节点），增加了复杂度。
1. 缺乏增量性：指令选择是全函数一次性完成的，不支持多阶段渐进优化。

---

三、GlobalISel：面向未来的模块化架构

3.1 设计目标

GlobalISel（Global Instruction Selection）从 LLVM 11 开始逐步成熟，目标是解决 SelectionDAG 的架构问题。它的核心理念是长期保持 SSA 形式——IR 到机器指令的整个过程都在 SSA 上进行，避免反复转换。

GlobalISel 将指令选择分解为四个独立、可组合的 pass：

IRTranslator → Legalizer → RegBankSelect → Instruction Selector

每个 pass 都有明确的输入输出 pass，支持独立测试、调试和性能分析。

3.2 IRTranslator：IR 到 gMIR 的第一步

IRTranslator 将 LLVM IR 转换为通用 MIR（gMIR——Generic Machine IR）。IR 中的每条指令被映射为一个 MachineIROpcode：

LLVM IR	gMIR Opcode	说明
add	G_ADD	通用加法
load	G_LOAD	通用加载
store	G_STORE	通用存储
call	G_CALL	函数调用
phi	G_PHI	PHI 节点（保持 SSA）

gMIR 保留 SSA 形式，操作数类型为 LLT（Low-Level Type），它用 scalar(32)、s64、v4s32 等精确描述类型（包括向量和指针区分）。

// gMIR 片段示例
%0:_(s32) = G_ADD %1:_(s32), %2:_(s32)
%3:_(s32) = G_SHL %0:_(s32), 4:i32

3.3 Legalizer：类型合法化的艺术

Legalizer pass 将 gMIR 中没有目标直接对应指令的操作替换为目标支持的操作。例如，若目标不支持 64 位 XOR：

BEFORE: %0:_(s64) = G_XOR %1:_(s64), %2:_(s64)
AFTER:  %h:_(s32), %l:_(s32) = G_UNMERGE_VALUES %1
        %h2:_(s32) = G_XOR %h, %h3
        %l2:_(s32) = G_XOR %l, %l3
        %0:_(s64) = G_MERGE_VALUES %h2, %l2

Legalizer 使用 artifact 节点处理类型转换：G_ZEXT（零扩展）、G_SEXT（符号扩展）、G_TRUNC（截断）、G_MERGE_VALUES 和 G_UNMERGE_VALUES（合并/拆分）。这些 artifact 将在后续 pass 中被消除。

3.4 RegBankSelect：寄存器库分配

在指令选择之前，RegBankSelect 为每个虚拟寄存器指定寄存器库（Register Bank）。寄存器库是把逻辑类型映射到物理寄存器组的策略层——例如整数使用 GPR 库、浮点使用 FPR 库、向量使用 VECR 库。

RegBankSelect 本质是一个图着色变体：构建冲突图，给每个节点分配 bank，对冲突的节点插入 G_COPY 指令：

BEFORE: %0:_(s32) = G_FADD %1:_(s32), %2:_(s32)；%1,%2 在 FPR
AFTER:  %3:_(s32) = G_FADD %1, %2           ; %3 在 FPR bank
        %0:_(s32) = G_COPY %3              ; copy FPR→GPR

3.5 Instruction Selector：TableGen 的进化

GlobalISel 的指令选择器通过 TableGen 中的 GINodeMatcher 声明。与 SelectionDAG 的 Pat 不同，GlobalISel 的模式使用 C++ 谓词（predicate）实现复杂匹配：

def : GIPattern<
  (insn G_ADD, (operands GPR32Op:$src1, GPR32Op:$src2), (outs GPR32Op:$dst),
   (operands i64imm:$imm)),
  [(ADDWri $src1, $src2, $imm)]
>;

InstructionSelector 在 C++ 中递归遍历模式，支持：

• 立即数范围检查（inScope）
• 寄存器库过滤
• 复杂操作的组合匹配

---

四、实战：编写自定义组合（Combiner）

GlobalISel 最有力的工程工具是 Combiner——在指令选择后执行的特定模式优化 pass。Combiner 与 DAG Combine 类似，但运行在 gMIR 上，且直接操作目标指令。

4.1 识别冗余 COPY 的 Combiner

假设某个 pass 产生了多余的 G_COPY，我们可以用 Combiner 消除：

// MyCombiner.cpp (LLVM 源码树内)
class MyCombiner : public MachineFunctionPass {
public:
  bool runOnMachineFunction(MachineFunction &MF) override {
    MRI = &MF.getRegInfo();
    bool Changed = false;
    
    for (auto &MBB : MF) {
      for (auto &MI : MBB) {
        if (MI.getOpcode() == TargetOpcode::G_COPY) {
          if (MRI->hasOneUse(MI.getOperand(0).getReg()) &&
              !MRI->isReserved(MI.getOperand(1).getReg())) {
            // 替换目标为源寄存器，消除 copy
            MRI->replaceRegWith(MI.getOperand(0).getReg(),
                               MI.getOperand(1).getReg());
            MI.eraseFromParent();
            Changed = true;
          }
        }
      }
    }
    return Changed;
  }
};

4.2 利用 TableGen 声明组合

LLVM 支持在 TableGen 中声明 Pat 用于 GlobalISel 的内置 combiner GICombine：

// 合并 (G_ADD (G_ADD x, c1), c2) → (G_ADD x, (G_ADD c1, c2))
def pat_add_add_to_add : GICombinePat<
  (G_ADD (G_ADD GPR32:$x, i64imm:$c1), i64imm:$c2),
  (G_ADD GPR32:$x, (G_CONSTANT i64 imm:$combined))>;

---

五、性能调优与调试

5.1 编译时间对比

GlobalISel 的目标之一是降低编译时间。以下是 LLVM 16 的实验数据（编译 LLVM 测试套件）：

架构	SelectionDAG 时间(s)	GlobalISel 时间(s)	降幅
AArch64	185.3	142.7	-23%
X86-64	162.1	138.9	-14%
RISC-V	78.4	61.2	-22%

数据来源于 LLVM 社区基准测试，使用 -O2 优化级别

GlobalISel 的 pass 模型允许编译器跳过不必要的阶段（如当所有操作都已合法时跳过 Legalizer），这是性能提升的主要原因。

5.2 关键调试手段

遇到指令选择失败或结果异常时，以下工具是工程师的核心武器：

1. 调试打印

llc -march=aarch64 -debug-only=isel -o out.s input.ll 2>isel.log

2. 分层 dump

# 查看 IRTranslator 输出
llc -march=aarch64 -stop-after=ir-translator -o - input.ll

# 查看 Legalizer 后的 gMIR
llc -march=aarch64 -stop-after=legalizer -o - input.ll

# 查看完整流水线每个 pass 输出
llc -march=aarch64 -print-after-all -o /dev/null input.ll 2>&1 | less

3. 失败报错解读

当 GlobalISel 无法处理某个操作时，会报错：

LLVM ERROR: cannot select `...

 G_XOR ...

`: 

此时需要在后端的 XXXLegalizerInfo.cpp 中声明该操作合法，或在 XXXInstructionSelector.cpp 中添加模式。

5.3 常见合法化策略

// MyTargetLegalizerInfo.cpp
using namespace LegalizeActions;

MyTargetLegalizerInfo::MyTargetLegalizerInfo() {
  getActionDefinitionsBuilder({G_XOR, LLT::scalar(64)})
    .legalFor({LLT::scalar(32)})  // 32-bit 操作合法
    .widenScalarToNextPow2(0)     // 否则扩展到下一个2的幂
    .maxScalar(0, LLT::scalar(32))// 限制最大宽度
    .lower();                     // 降级为多个 narrow ops

  // 浮点乘法用库调用实现
  getActionDefinitionsBuilder({G_FMUL, LLT::scalar(128)})
    .libcall();

  // 向量操作逐元素展开
  getActionDefinitionsBuilder(G_SELECT)
    .lowerIf(typeIs(1, LLT::fixed_vector(4, s32)));
}

---

六、生产化考量

6.1 GlobalISel 与 SelectionDAG 的协同

LLVM 16 起 GlobalISel 仍是"可选"编译器后端，多数生产项目通过 -global-isel 标志切换。切换时需注意：

1. 调试信息：GlobalISel 的 DWARF 生成仍在完善阶段，如果对 debug info 质量要求极高，SelectionDAG 仍是稳妥选择。
1. 复杂指令模式：某些 VLIW 架构（如 DSP）的复杂并行模式，SelectionDAG 的 DAG-to-DAG 匹配可能更直观。
1. 移植成本：已有后端重度依赖 SelectionDAG，迁移需要重写 .td 文件和测试用例。

6.2 增量采用策略

对于需要自定义指令的新后端，合理的采用路径是：

Phase 1: GlobalISel 完成核心整数指令选择（覆盖率 > 80%）
Phase 2: SelectionDAG 回退处理复杂模式（通过 -global-isel -isel-abort-on-fail 开关）
Phase 3: 逐步将 SelectionDAG 模式迁移到 GlobalISel
Phase 4: 禁用 SelectionDAG，全量 GlobalISel

---

七、总结

LLVM 指令选择的三代架构体现了编译器工程的核心张力：抽象能力 vs 编译速度 vs 代码可维护性。SelectionDAG 提供了强大的模式表达力，但二十年积累使其架构僵化；GlobalISel 用模块化的 pass 设计换取了更清晰的数据流和更好的可测试性。

对于后端工程师而言，理解这两套系统是不可或缺的核心技能——而掌握 GlobalISel 的艺术，意味着你站在了 LLVM 未来十年的技术路线上。选择合适的时机将自己的后端迁移到 GlobalISel，既是工程决策，也是投资未来。

---

参考：LLVM 官方文档、GlobalISel 设计文档、AArch64 GlobalISel 实战