LLVM 后端是将中间表示（IR）转换为特定目标架构机器码的复杂系统。本章深入探讨 LLVM 后端的架构设计、关键组件及其演化历程，理解从平台无关的 IR 到高度优化的机器码的转换过程。我们将重点关注 TableGen 的声明式设计、不同指令选择框架的权衡、寄存器分配算法的演进，以及机器级优化的实现策略。
在 LLVM 项目早期（2003年），Chris Lattner 面临一个关键问题：如何高效地描述目标架构的指令集、寄存器、调用约定等信息。传统方法需要手写大量重复的 C++ 代码，不仅容易出错，而且难以维护。
TableGen 的核心思想是声明式编程：用简洁的领域特定语言（DSL）描述目标架构的特性，然后自动生成相应的 C++ 代码。这种方法带来了几个关键优势：
TableGen 使用类似面向对象的语法，但本质上是一个模板展开系统：
// 定义寄存器类
class Register<string n> {
string Name = n;
list<string> Aliases = [];
}
// 定义具体寄存器
def RAX : Register<"rax"> {
let Aliases = ["rax", "eax", "ax", "al"];
}
// 定义指令格式
class Instruction<dag outs, dag ins, string asm> {
dag OutOperandList = outs;
dag InOperandList = ins;
string AsmString = asm;
}
TableGen 中的指令描述采用多层继承结构，从抽象到具体：
Instruction (基类)
↓
X86Inst (架构特定基类)
↓
BinaryOpRR (二元寄存器操作)
↓
ADD64rr (具体指令)
这种层次结构允许：
TableGen 最强大的功能之一是描述 IR 到机器指令的映射模式：
// 将 IR 的 add 操作映射到 ADD64rr 指令
def : Pat<(add i64:$src1, i64:$src2),
(ADD64rr $src1, $src2)>;
// 复杂模式：带立即数的加法
def : Pat<(add i64:$src, (i64 imm:$imm)),
(ADD64ri $src, $imm)>;
这些模式在编译时被处理成高效的匹配表，运行时用于指令选择。
从 2003 年至今，TableGen 经历了多次重要演进：
2003-2005：基础阶段
2006-2010：功能扩展
2011-2015：性能优化
2016-2023：现代化改进
优势：
局限：
SelectionDAG（选择有向无环图）是 LLVM 后端的核心组件，负责将 LLVM IR 转换为目标机器指令。Evan Cheng 在 2005-2008 年期间对其进行了重大改进，使其成为工业级的指令选择框架。
核心设计原则：
LLVM IR
↓
[构建初始 DAG]
↓
[类型合法化]
↓
[操作合法化]
↓
[DAG 组合优化]
↓
[指令选择]
↓
[调度和生成]
↓
MachineInstr
类型合法化处理目标架构不直接支持的数据类型：
类型提升（Promotion）：
类型拆分（Splitting）：
操作展开（Expansion）：
在指令选择前，SelectionDAG 执行多种优化：
这些优化利用 DAG 的全局视图，找到 IR 级别难以发现的优化机会。
SelectionDAG 使用基于模式匹配的指令选择：
示例 DAG：
(add)
/ \
(load) (mul)
/ \
(reg) (const)
可能的匹配：
- add + load → 带内存操作数的加法指令
- mul + const → 带立即数的乘法指令
优点：
缺点：
2015 年，Quentin Colombet 领导的团队开始开发 GlobalISel，目标是解决 SelectionDAG 的根本性问题：
GlobalISel 的设计目标：
GlobalISel 采用基于 MIR（Machine IR）的流水线架构：
LLVM IR
↓
[IRTranslator]
↓
Generic MIR
↓
[Legalizer]
↓
Legal Generic MIR
↓
[RegBankSelect]
↓
RegBank-assigned MIR
↓
[InstructionSelect]
↓
Target MIR
IRTranslator 直接将 LLVM IR 转换为通用机器指令（Generic MIR）：
; LLVM IR:
%result = add i32 %a, %b
; Generic MIR:
%result:_(s32) = G_ADD %a:_(s32), %b:_(s32)
关键特性：
Legalizer 负责将通用操作转换为目标支持的形式：
// 合法化动作定义
getActionDefinitionsBuilder(G_ADD)
.legalFor({s32, s64}) // 32 和 64 位加法合法
.widenScalarToNextPow2() // 其他宽度扩展到 2 的幂
.clampScalar(0, s32, s64); // 限制在 32-64 位范围
合法化策略：
这是 GlobalISel 的创新之处，在指令选择前决定值存储在哪类寄存器中：
; 分配前：
%val:_(s32) = G_LOAD %ptr:_(p0)
; 分配后：
%val:gpr(s32) = G_LOAD %ptr:gpr(p0) ; 通用寄存器
; 或
%val:fpr(s32) = G_LOAD %ptr:gpr(p0) ; 浮点寄存器
优势：
基于 TableGen 生成的匹配表选择目标指令：
// TableGen 模式
def : GINodeEquiv<G_ADD, add>;
def : Pat<(add GPR32:$src1, GPR32:$src2),
(ADDWrr GPR32:$src1, GPR32:$src2)>;
与 SelectionDAG 的区别：
GlobalISel 提供了新的优化点：
编译速度（2023 年数据）：
采用现状：
寄存器分配是编译器后端最关键的优化之一。它需要将无限的虚拟寄存器映射到有限的物理寄存器，同时最小化内存访问（spill/reload）。这是一个 NP 完全问题，实践中需要在编译时间和代码质量间权衡。
LLVM 的寄存器分配器演化：
早期 LLVM 使用的线性扫描算法基于 Poletto 和 Sarkar 的工作（1999）：
算法流程：
1. 计算每个虚拟寄存器的活跃区间（Live Interval）
2. 按起始点排序活跃区间
3. 线性扫描，为每个区间分配寄存器
4. 冲突时选择溢出代价最小的寄存器
优点：
缺点：
2010 年，Jakob Stoklund Olesen 设计了全新的 Greedy 分配器，至今仍是 LLVM 的默认选择：
核心思想：
// 简化的分配流程
while (!Queue.empty()) {
VirtReg = Queue.pop();
if (PhysReg = tryAssign(VirtReg))
assign(VirtReg, PhysReg);
else if (canEvict(VirtReg))
evictAndAssign(VirtReg);
else
splitAndEnqueue(VirtReg);
}
活跃区间是寄存器分配的基础数据结构：
虚拟寄存器 %1 的活跃区间：
[16, 32) [48, 64) [80, 96)
↑ ↑ ↑
定义点 使用点 最后使用
物理寄存器压力图：
时间 →
R0: ████____████____
R1: __████████______
R2: ______████████__
关键概念：
当寄存器不足时，需要将值溢出到内存：
; 溢出前：
add %r1, %r2, %r3
mul %r4, %r1, %r5
; 溢出 %r1 后：
add %r1, %r2, %r3
str %r1, [sp, #8] ; spill
... 其他代码 ...
ldr %r1, [sp, #8] ; reload
mul %r4, %r1, %r5
溢出决策因素：
现代架构有复杂的寄存器约束：
// X86 的寄存器类定义
def GR32 : RegisterClass<[i32], 32, [EAX, ECX, EDX, ...]>;
def FR32 : RegisterClass<[f32], 32, [XMM0, XMM1, ...]>;
// 特殊约束
def : Constraint<"$src = $dst">; // two-address 约束
分配器必须处理：
PBQP（Partitioned Boolean Quadratic Programming）是一种基于图的分配方法：
构建 PBQP 图：
- 节点：虚拟寄存器
- 边：寄存器间的干扰
- 权重：分配代价
求解过程：
1. 图简化（移除度数小的节点）
2. 启发式选择
3. 回溯优化
优势：
劣势：
寄存器分配对性能的影响巨大：
基准测试结果（SPEC CPU2017）：
优秀的分配 vs 差的分配：
- 性能差异：10-30%
- 代码大小：15-25% 差异
- 能耗：相应增加
关键指标：
最新研究探索使用机器学习改进寄存器分配：
Google 的 MLGO 项目已经展示了初步成果，在某些场景下超越传统启发式算法。
机器级优化发生在指令选择之后、代码发射之前，直接操作目标机器指令。这个阶段的优化对性能至关重要，因为它们了解具体的硬件特性：
LLVM 支持多种调度策略：
1. 列表调度（List Scheduling）
基本算法：
1. 构建依赖图（DAG）
2. 计算每个指令的优先级
3. 维护就绪队列
4. 贪心选择下一条指令
2. 调度区域
TableGen 描述目标的调度模型：
// 定义处理器模型
def CortexA57Model : SchedMachineModel {
let IssueWidth = 3; // 每周期可发射3条指令
let MicroOpBufferSize = 128; // 微操作缓冲区大小
let LoadLatency = 4; // Load 指令延迟
let MispredictPenalty = 16; // 分支预测错误代价
}
// 定义指令调度类
def : WriteRes<WriteALU, [A57UnitI]> {
let Latency = 1; // ALU 操作延迟1周期
}
调度器识别并优化关键路径：
原始序列：
1: load r1, [r0] ; 4 cycles
2: load r2, [r0+4] ; 4 cycles
3: add r3, r1, #1 ; 1 cycle (依赖1)
4: add r4, r2, #2 ; 1 cycle (依赖2)
5: mul r5, r3, r4 ; 3 cycles (依赖3,4)
总延迟：4 + 1 + 3 = 8 cycles
优化后（指令重排）：
1: load r1, [r0] ; 4 cycles
2: load r2, [r0+4] ; 4 cycles (并行)
3: add r3, r1, #1 ; 1 cycle
4: add r4, r2, #2 ; 1 cycle (并行)
5: mul r5, r3, r4 ; 3 cycles
总延迟：max(4+1, 4+1) + 3 = 8 cycles
但利用了并行执行单元
平衡指令级并行和寄存器压力：
// 调度策略选择
enum SchedulingStrategy {
ILP, // 最大化指令级并行
RegPress, // 最小化寄存器压力
Hybrid // 混合策略
};
// 根据区域特征选择策略
if (RegisterPressure > Threshold)
Strategy = RegPress; // 降低压力，避免溢出
else
Strategy = ILP; // 提高并行度
识别并优化局部指令模式：
; 优化前：
mov r1, #0
cmp r1, #0
beq label
; 优化后：
mov r1, #0
b label ; 无条件跳转，因为比较结果已知
; 另一个例子 - 合并 load/store：
; 优化前：
ldr r1, [r0]
ldr r2, [r0+4]
; 优化后（如果目标支持）：
ldp r1, r2, [r0] ; 加载对
现代处理器支持指令融合：
; 比较和分支融合（ARM64）
cmp x0, x1
b.eq label
; 处理器可能将这两条指令作为一个微操作执行
; 地址计算融合（x86）
lea rax, [rbx + rcx*4 + 8]
; 复杂地址计算在一个周期内完成
LLVM 的 MacroFusion pass 识别这些机会：
// MacroFusion 的模式识别
if (isCompareInstr(First) && isCondBranch(Second)) {
if (canFuseInstructions(First, Second))
markAsFused(First, Second);
}
某些架构（如 MIPS、SPARC）有延迟槽：
; MIPS 的延迟槽
beq $t0, $t1, label
add $t2, $t3, $t4 ; 延迟槽，总是执行
; 填充策略：
; 1. 从前面移动无关指令
; 2. 从目标块移动安全指令
; 3. 插入 NOP（最后选择）
寄存器分配后的再调度，利用确定的寄存器信息：
// PostRA 调度器
class PostRAScheduler {
void schedule() {
// 已知物理寄存器，可以精确建模：
// - 寄存器依赖
// - 反依赖（WAR）
// - 输出依赖（WAW）
buildDependencies();
computeSchedule();
applySchedule();
}
};
优势：
机器级的分支优化：
1. 分支消除
; 条件移动替代分支
; 优化前：
cmp r0, #0
beq skip
mov r1, #1
skip:
; 优化后：
cmp r0, #0
movne r1, #1 ; 条件执行
2. 分支对齐
; 对齐热点分支目标到缓存行边界
.align 64
hot_loop:
; 循环体
3. 尾调用优化
; 优化前：
call function
ret
; 优化后：
jmp function ; 尾调用
优化基本块布局以改善分支预测和缓存行为：
原始 CFG：
BB1
/ \
BB2 BB3
\ /
BB4
优化后（基于 profile）：
BB1 → BB3 → BB4 → BB2
（将热路径排成直线）
策略：
三种指令选择框架的机器级优化能力对比：
FastISel
SelectionDAG
GlobalISel
本章深入探讨了 LLVM 后端架构的核心组件和演化历程。我们学习了：
关键洞察：
未来趋势：
练习 6.1 TableGen 的核心价值是什么？列举三个 TableGen 自动生成的组件。
练习 6.2 解释 SelectionDAG 中”类型合法化”和”操作合法化”的区别，各举一个例子。
练习 6.3 在 GlobalISel 框架中，为什么要在指令选择之前进行 RegBankSelect？这带来什么优势？
练习 6.4 比较线性扫描和 Greedy 寄存器分配算法的时间复杂度和代码质量。
练习 6.5 设计一个简单的 TableGen 描述，定义一个假想架构的 ADD 指令（包括寄存器-寄存器和寄存器-立即数两种形式）。说明你的设计考虑。
练习 6.6 给定以下指令序列和延迟信息，手工进行指令调度以最小化总执行时间。假设有两个执行单元可以并行执行独立指令。
1: load r1, [r0] // 3 cycles
2: load r2, [r0+4] // 3 cycles
3: add r3, r1, #1 // 1 cycle, depends on 1
4: mul r4, r2, r1 // 2 cycles, depends on 1,2
5: store r3, [r0+8] // 2 cycles, depends on 3
6: store r4, [r0+12] // 2 cycles, depends on 4
练习 6.7 分析 GlobalISel 和 SelectionDAG 在编译以下 IR 时的主要差异：
define i32 @foo(i32 %a, i32 %b) {
%1 = add i32 %a, %b
%2 = mul i32 %1, 2
ret i32 %2
}
练习 6.8 设计一个寄存器分配场景，展示 Greedy 算法相比线性扫描的优势。说明两种算法的不同决策。
陷阱：过度使用 TableGen，将复杂逻辑塞入 .td 文件
// 错误：复杂计算不适合 TableGen
def ComplexPattern : Pat<...> {
let Predicate = [{
// 100 行 C++ 代码
}];
}
解决：复杂逻辑应该在 C++ 中实现，TableGen 只做声明
陷阱：忽视寄存器压力导致过度溢出
// 在循环中创建太多临时变量
for (...) {
int t1 = ..., t2 = ..., t3 = ..., t4 = ...;
// 寄存器压力过高
}
解决：使用寄存器压力跟踪，必要时调整优化策略
陷阱：模式匹配顺序错误
// 错误：通用模式在特殊模式前
def : Pat<(add i32:$a, i32:$b), (ADD32rr $a, $b)>;
def : Pat<(add i32:$a, 1), (INC32r $a)>; // 永远不会匹配
解决：特殊模式应该有更高优先级
陷阱：忽视内存依赖
store [addr], r1
load r2, [addr] ; 必须在 store 后执行
解决：正确建模内存依赖，使用别名分析
陷阱：假设 GlobalISel 总是更快
// GlobalISel 可能在某些模式上更慢
-mllvm -global-isel=1 // 盲目启用
解决：基准测试，根据具体场景选择