1. 后端的两站路：先选指令，再排顺序
一句话总结： 指令选择决定「用哪条机器指令」，指令调度决定「这些指令按什么顺序发射」。
中端优化把 IR 打磨得越来越抽象（SSA、phi 节点、无副作用的纯函数调用），但 CPU 只认具体的机器指令。后端要完成两次语义坍缩：第一次是把 IR 节点替换成目标 ISA 的指令模板，这一步叫指令选择（Instruction Selection）；第二次是在保持数据依赖不变的前提下重排指令顺序，以隐藏访存与运算延迟、压低寄存器压力，这一步叫指令调度（Instruction Scheduling）。
这两步紧耦合：选择阶段倾向于把多个 IR 操作合并成一条复杂指令（例如 x86 的 lea 一条搞定「乘加+取址」），但复杂指令往往有更长的延迟，调度阶段又想把它们拆散以填满流水线。理解这条张力线，就理解了后端一半的工程取舍。
IR (SSA) 指令选择 指令调度
t1 = a * 4 → lea rax,[rdi*4] → lea rax,[rdi*4]
t2 = t1 + b → add rax,rsi → mov rcx,[rsp+8] # 提前发射
t3 = load [t2] → mov rax,[rax] → add rax,rsi
ret t3 → ret → mov rax,[rax]
ret
2. 指令选择的理论骨架：树覆盖与 DAG 覆盖
经典的指令选择问题可以形式化为树覆盖（Tree Covering）：把 IR 的表达式树用一组「指令模式」（pattern）恰好覆盖一次，使得总代价最小。每条指令模式是一棵小树，代价可以是延迟、字节数或功耗。
考虑一个只有 add、mul、shl、lea 的目标。对表达式 (a + b * 4)：
- 拆开覆盖：
t = b << 2; r = a + t，两条指令； - 整体覆盖：
lea r, [a + b*4]，一条指令。
代价模型给 lea 记 1，于是最优覆盖选后者。这就是动态规划覆盖的核心：对每个节点，枚举所有能覆盖它的模式，取子树代价之和最小的方案。
# 极简的动态规划树覆盖
def cover(node, rules):
best = None
for r in rules: # r: (root_op, pattern, cost)
if r.root_op != node.op:
continue
# 检查模式能否匹配 node 这棵子树
if not match(r.pattern, node):
continue
cost = r.cost + sum(cover(kid, rules).cost for kid in node.kids)
if best is None or cost < best.cost:
best = Rule(node, r, cost)
return best
工程上的实现叫 BURS（Bottom-Up Rewrite System）：把模式编译成状态机，自底向上在线性时间里完成覆盖，LLVM 早期的 SelectionDAG 与 GCC 的 genrecog 都借鉴了这套思路。
2.1 模式从哪里来：TableGen 与机器描述
手工为每个目标写模式匹配器不现实。主流做法是用领域特定语言（DSL） 描述指令，再自动生成匹配代码。LLVM 用 TableGen：
// X86InstrArithmetic.td 节选：把 add 的内存操作数形式描述成模式
def ADD32rm : ... {
let Pattern = [(set GR32:$dst,
(add GR32:$src1, (load addr:$src2)))];
}
TableGen 把每条指令的 Pattern 编译成匹配器，同时生成寄存器类、指令编码与调度模型。-gen-dag-isel 生成 SelectionDAG 的匹配代码，-gen-global-isel 生成 GlobalISel 的匹配器。这样「指令选择算法」与「指令集合」解耦：换一个 .td 文件就换一套目标。
# 打印某目标的全部指令模式
llvm-tblgen -print-records -I $LLVM/include \
$LLVM/include/llvm/Target/X86/X86.td | head -60
2.2 合法化：把 IR 拽到目标能表达的范围
选择之前有一道合法化（Legalization） 关卡。IR 里可能出现目标根本不支持的类型或操作，例如在只有 32 位整数运算的目标上出现 i64 乘法，或在没有 ctpop 指令的目标上出现 @llvm.ctpop.i32。合法化把这类操作降级成目标支持的形式：
| 非法项 | 降级方式 |
|---|---|
i64 乘法（仅 32 位机） | 拆成 32 位乘法 + 进位组合 |
i1/i3 等非幂次位宽 | 扩展到最近的合法位宽再截断 |
f80 长双精度（不支持） | 软件库调用或降为 f64 |
ctpop/bswap（无指令） | 展开成位运算序列 |
select（无 cmov） | 降为分支 + phi |
合法化分类型合法化与操作合法化两阶段，顺序不能反：先把类型调到合法宽度，再判断操作是否有对应指令。
2.3 DAG 覆盖的启发式
真实 IR 不是树而是 DAG，因为有公共子表达式：x = a * b 被用两次时，DAG 里 a*b 只有一个节点、两条出边。DAG 覆盖是 NP-hard 的，所以实际编译器用启发式：
| 策略 | 做法 | 代价 |
|---|---|---|
| 树化 | 按使用次数把 DAG 拆回森林，重复子树各覆盖一次 | 可能重复计算 |
| 共享节点 | 允许一个节点被多个父节点共享，公共子表达式只算一次 | 需要额外的值复制 |
| 延迟树化 | 仅在寄存器压力允许时才共享 | 实现复杂 |
LLVM 的 SelectionDAG 就是典型：它先把 IR 转成 DAG，做合法化（legalize，把目标不支持的宽类型与操作拆成支持的），再用模式匹配生成机器节点，最后对 DAG 做**线性化（scheduling）**得到机器指令序列。
# 观察 LLVM 的指令选择过程
llc -debug-only=isel input.ll 2>&1 | head -40
# 或者打印选择后的 SelectionDAG
llc -view-dag-combine1-dags input.ll
2.4 全局指令选择：不是逐表达式，而是整函数
逐节点的贪心覆盖会漏掉跨基本块的模式。例如循环里的 x[i] = x[i] + 1 可以被 x86 的 inc [rdi+rax*4] 一条指令表达，但树覆盖只看单个表达式树，看不到「内存操作数可以内联进算术指令」这一点。
全局指令选择（Global Instruction Selection） 用**有向图覆盖（DAG/DAG-cover）**在整函数级别求最优，代表实现是 LLVM 的 GlobalISel。它把机器指令编码成带操作数约束的图，用贪心+回溯的图匹配器覆盖整个函数：
IR: %0 = load i32, ptr %p
%1 = add i32 %0, 1
store i32 %1, ptr %p
GlobalISel 匹配到 G_LOAD + G_ADD + G_STORE
→ 折叠为一条 x86 INC 内存操作数指令
全局选择的代价是编译时间与实现复杂度，因此 LLVM 长期以 SelectionDAG 为主、GlobalISel 在 AArch64/AMDGPU 等目标上逐步替换。
3. 指令调度：列表调度与关键路径
选完指令后，得到的是一个依赖图（DAG）：节点是指令，边是数据依赖（RAW/WAR/WAW）与控制依赖。调度的目标是在满足依赖的前提下，找到一个线性顺序，使得流水线尽可能不空转。
最经典的算法是列表调度（List Scheduling）：
- 计算每个节点的关键路径长度（critical path / height），即从该节点到出口的最长延迟链；
- 维护一个就绪队列（所有前驱已调度的节点）；
- 每次从就绪队列中挑优先级最高的节点发射，优先级通常是关键路径长度；
- 重复直到 DAG 排空。
def list_schedule(dag, latency):
for n in reversed(topo_order(dag)):
n.height = latency[n] + max((s.height for s in n.succ), default=0)
ready = [n for n in dag if not n.pred]
seq = []
while ready:
n = max(ready, key=lambda x: x.height) # 贪心取关键路径最长者
seq.append(n)
ready.remove(n)
for s in n.succ:
s.pred.discard(n)
if not s.pred:
ready.append(s)
return seq
关键路径上的指令（height 最大）优先发射，能让最长的依赖链尽早开始。但纯关键路径优先有个副作用：它会把同一时刻活跃的值堆到最多，推高寄存器压力（Register Pressure），反过来逼出溢出。
3.1 寄存器压力感知调度
LLVM 的调度器把寄存器压力作为一等公民。它跟踪每个调度点上的活跃值集合（live set），当某个时刻活跃值数量逼近可用物理寄存器时，降低那些「会延长某值寿命」的节点的优先级：
# 伪代码：压力感知的优先级
priority(n) = height(n) * w_h
- max(0, pressure(n) - limit) * w_p # 超压惩罚
- excess(n) * w_e # 新增活跃值惩罚
三种典型启发式：
- Top-down 调度：从入口向出口走，优先发射关键路径，但主动控制活跃值增长；
- Bottom-up 调度：从出口反推，适合生成便于寄存器分配的顺序；
- Hybrid 调度：先 top-down 得到初序，再局部调整以削峰。
在 LLVM 里这些通过 -pre-RA-sched 选择：
llc -pre-RA-sched=source input.ll # 源序，最少重排
llc -pre-RA-sched=list-hybrid input.ll
llc -pre-RA-sched=list-ilp input.ll # ILP 优先，可能压高压力
3.2 依赖图的构建：内存依赖与控制依赖
列表调度的输入是依赖 DAG，而构建正确的 DAG 比调度本身更难。依赖分三类：
- 数据依赖：寄存器层面的 RAW/WAR/WAW。SSA 下 WAR/WAW 天然消失，只剩 RAW，DAG 直接对应 def-use 链。
- 内存依赖：两条访存指令是否可能访问同一地址，编译器往往无法判定，只能保守地串起来。
alias analysis给出NoAlias时才能解耦。 - 控制依赖：分支、异常、volatile 访存不能跨边界重排。
store [p], 1 # 写
load r, [q] # 读
# 若 p 与 q 可能别名 → load 必须排在 store 之后（WAR/RAW 混淆）
# 若 alias analysis 判定 NoAlias → 可自由重排
调度器为了提效会做投机（speculation）：把一条指令提前到它原本所在的块之前，前提是「即使该路径不执行这条指令也无害」。纯计算指令可以投机，可能除零或访存越界的指令不能。x86 上的 cmov 与 AArch64 的条件执行正是为「无分支投机」准备的指令选择目标。
4. 全局调度与软件流水
局部列表调度只看单个基本块，跨块的重排能力有限。全局调度（Global Scheduling） 允许指令跨越基本块边界移动，代价是要处理补偿代码（compensation code）：如果一条指令从块 A 提到块 B，那么从别的路径进入 A 时也必须执行它。
更激进的是软件流水（Software Pipelining），尤其是模调度（Modulo Scheduling）。它把循环的多次迭代重叠执行：一个迭代的「加载」与上一个迭代的「计算」并行，流水线被填满。
原始循环: 模调度后（II = 启动间隔）:
load a[i] prolog: load a[0]; load a[1]
mul a[i] * c kernel: load a[i+2] | mul a[i] | store a[i-2]
store a[i] epilog: mul a[n-1]; store a[n-2]
模调度的核心约束是启动间隔（Initiation Interval, II）：
II >= max(RecMII, ResMII)
RecMII: 由循环携带依赖（recurrence）决定，= 依赖环延迟 / 环上迭代距离
ResMII: 由资源冲突决定，= 每迭代使用的某资源数 / 该资源可用份数
II 越小流水线越满。II=1 意味着每周期发射一次迭代，需要足够的并行资源。这套技术在 Itanium、DSP 与 GPU（如 NVIDIA 的 PTX 后调度）上价值极高。
4.1 补偿代码与谓词执行
全局调度把指令跨块移动时，必须保证所有进入路径都满足语义。两种处理：
- 补偿代码：在某条边（edge）上插入复制指令，把「该路径下本应执行的操作」补齐。边越关键、补偿越贵，调度器越保守。
- 谓词执行（Predication）：把控制依赖转成数据依赖，用谓词寄存器把指令「条件化」，于是跨块移动不再需要补偿代码。ARM 的
cond字段、Itanium 的(p1)谓词、RISC-V 的Zicond都是这一路。
# 有分支: # 谓词化后:
cmp a, b cmp a, b
jle L p = setle(a, b)
mov r, 1 r = select(p, 1, 0) # 无分支
L: ...
谓词化消除了分支预测失败的开销，但代价是「两条路径都要取指」，只有在两条路径都很短时才划算。
5. 工程实践：x86-64 与 AArch64 的取舍
不同 ISA 让同一套算法呈现截然不同的形态。
x86-64 是变长、CISC、双操作数的。它的内存操作数允许算术指令直接读内存，所以指令选择倾向于「少而重」的指令；但双操作数意味着 a = b + c 可能要先 mov a, b 再 add a, c，这多出来的 mov 又给调度器制造了消冗余的工作。
AArch64 是定长、RISC、三操作数的。它的每条算术指令都带一个可选的移位操作数（add x0, x1, x2, lsl #3），指令选择时把移位内联进来能省一条 lsl；同时 AArch64 的乱序执行窗口大，调度器可以更保守，把压力留给硬件。
| 维度 | x86-64 | AArch64 |
|---|---|---|
| 指令长度 | 变长 1~15 字节 | 定长 4 字节 |
| 操作数 | 双操作数，可含内存 | 三操作数，含移位 |
| 选择倾向 | 合并成复杂指令 | 拆分，靠乱序执行 |
| 调度倾向 | 显式重排收益大 | 硬件窗口吸收 |
| 典型坑 | mov 消冗余、lea 滥用 | 条件执行与 flag 依赖 |
5.1 观测工具
# 看 LLVM 在 x86-64 上选了哪些指令
llc -march=x86-64 -O2 -print-after=isel input.ll
# 看调度后的机器指令序
llc -march=aarch64 -O2 -print-after=machine-scheduler input.ll
# 对比是否把移位内联进了算术指令
llvm-mca -march=znver3 -iterations=100 kernel.s # 机器码吞吐分析
llvm-mca 是验证调度质量的好工具：它按目标微架构的端口与延迟模型模拟指令流，直接给出吞吐（IPC）与瓶颈端口。
5.2 常见陷阱
lea滥用：x86 上lea能在一条指令里做「乘 2/4/8 + 加」，但它占用 AGU 端口，密集使用时反而挤占真正的访存。选择器若无脑合并，可能拖慢循环。- 调度破坏寄存器分配：激进重排拉长某些值的寿命，寄存器分配器被迫溢出，净收益为负。现代流水线在寄存器分配前后各跑一次调度（pre-RA 与 post-RA），并把压力反馈回调度。
mov消冗余时机：x86 的双操作数形式会生成大量mov，过早消除会锁死后续选择空间，通常交给寄存器分配后的peephole处理。- 调度模型滞后：调度依赖目标微架构的端口/延迟表，新 CPU 发布后旧模型会给出错误优先级，需要及时更新
llvm/lib/Target/*/SchedModel.td。
一句话：指令选择与调度都不是「求一次最优」的静态问题，而是与寄存器分配、目标微架构模型反复拉扯的协同优化过程。
延伸阅读
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。