15.2 分支预测、超标量与乱序执行

地心引擎的五级流水线已经能让多条指令重叠，但前方一遇到分支、cache miss 或长延迟除法，整条队伍仍会停顿。现代高性能 CPU 会猜测下一段控制流、同时取入多条指令，并让已经具备 operand 的操作先去占用执行单元；最后再按程序顺序提交可见结果。

这不是让指令在机舱里毫无规则地乱跑。分支预测、超标量、乱序执行与顺序 retirement 各守一段边界：

• 分支预测决定接下来从哪里取指；
• 超标量表示一个周期能处理多项工作；
• 乱序执行让后面的独立操作越过尚未就绪的操作；
• 顺序 retirement 维持精确异常和架构可见顺序。

1. 分支预测不只猜“跳不跳”

取指前端需要尽早回答：

1. 当前指令是不是分支？
2. 条件分支会不会跳？
3. 若跳转，目标地址是什么？
4. 若是函数返回，应回到哪个调用点？

不同结构分别帮助回答这些问题：

• direction predictor 预测 taken/not taken；
• branch target buffer（BTB）缓存分支位置与目标；
• return address stack（RAS）预测成对 call/return 的返回地址；
• 间接分支预测器处理一个位置可能跳向多个目标的情况。

方向猜对但目标没准备好，前端仍可能出现气泡。BTB 命中也不是“跳转零成本”的绝对保证，取指带宽、cache、对齐和后端资源都会影响结果。

2. 两位饱和计数器

最小动态预测器可以为一个分支保存两位状态：

0 strongly not taken
1 weakly not taken
2 weakly taken
3 strongly taken

状态 0/1 预测不跳，2/3 预测跳。实际跳转就加一，不跳就减一，并在 0 和 3 饱和。一次偶然反转不会立刻把“强”预测翻到另一方向。

下面用代码观察不同模式：

class TwoBitPredictor:
    def __init__(self):
        self.counter = 1  # weakly not taken

    def predict(self):
        return self.counter >= 2

    def update(self, taken):
        if taken:
            self.counter = min(3, self.counter + 1)
        else:
            self.counter = max(0, self.counter - 1)


def mispredictions(pattern):
    predictor = TwoBitPredictor()
    misses = 0
    for outcome in pattern:
        if predictor.predict() != outcome:
            misses += 1
        predictor.update(outcome)
    return misses


mostly_taken = [True] * 100
alternating = [True, False] * 50
loop_exit = ([True] * 9 + [False]) * 10

assert mispredictions(mostly_taken) == 1
assert mispredictions(alternating) == 100
print(mispredictions(loop_exit))

这只是一个分支、一个计数器。真实处理器会按分支地址索引许多预测项，并利用局部或全局历史、路径信息以及多种预测器组合。交替模式把最小计数器难住，不代表所有现代预测器都会错 100 次。

3. 预测失败时撤销的是推测工作

预测分支后，CPU 可以沿猜测路径取指、译码甚至执行。分支条件解析后：

• 预测正确，相关结果继续等待提交；
• 预测错误，错误路径上的年轻操作被 squash，rename map 与前端从检查点恢复，再从正确 PC 取指。

错误路径不能把寄存器或内存的架构结果正式提交。但它可能已经改变 cache、TLB、预测器和执行端口占用等微架构状态。Spectre 类攻击正是利用“架构结果被撤销，微架构痕迹仍可观察”的差距。

因此，分支预测既是性能机制，也是安全边界的一部分。避免把秘密用于影响可观测索引、地址或控制流，需要语言、编译器与平台提供的特定缓解方案，不是简单关闭一处预测。

4. 超标量：一个周期不只处理一条

superscalar 处理器在前端与后端配置多条并行通道。例如一个周期可能译码多个操作，并把它们送到整数 ALU、load/store 单元和向量单元。

fetch/decode width
        ↓
rename and allocate
        ↓
issue queues
   ┌────┼────────┐
 integer   load/store   vector

“宽度为 4”不等于 IPC 永远是 4。吞吐会受分支、依赖、cache miss、执行端口、队列容量和前端供给限制。某些指令还可能分解成多个内部操作，ISA 指令数与内部工作数并非一一对应。

顺序超标量可以同周期发射多条相邻且独立的指令；乱序执行则允许从更大的窗口里选择已就绪工作。两者可以组合，也不是同一个概念。

5. Register renaming 消除假依赖

程序只有有限的架构寄存器名，循环中会反复使用它们：

mul r1, r2, r3
add r4, r1, r5
sub r1, r6, r7

第二条对第一条的 r1 是 RAW 真依赖，必须等待。第三条写 r1 形成 WAW 名字冲突，但它的计算并不依赖第一条结果。

rename 阶段把两次 r1 写入映射到不同物理寄存器：

mul writes physical P20
add reads  physical P20
sub writes physical P31

这样 sub 可以提前执行，同时保留程序顺序下“最后一次 r1 写入”的语义。WAR 也能通过重命名消除，RAW 不能，因为它表达真实数据流。

重命名资源有限。物理寄存器、ROB 或 load/store queue 用尽时，前端会停下，直到旧操作退休并释放资源。

6. 乱序调度：就绪的先做

rename 后的操作进入调度结构，等待源操作数和执行单元：

older load: cache miss ───────────────┐
dependent add: waits for load        │
independent multiply: ready → execute│
independent branch: ready → execute  │
                                      ▼
                              results complete

后面的独立操作可以越过 miss，利用本来会空闲的单元。这只能隐藏有限延迟：

• 指令窗口必须容得下足够多的后续工作；
• 后续工作要真正独立；
• 执行单元和内存请求槽要有余量；
• 分支预测要继续提供正确路径；
• 最老的停顿最终可能堵住 retirement。

pointer chasing 往往形成 load → address → next load 的依赖链，难以并行。多个独立数组流则更容易形成 memory-level parallelism。

7. 内存顺序比寄存器更难

CPU 很早就能从指令编码看出寄存器名，却可能要等地址计算后才知道：

store [p] = 1
load  r = [q]

其中 p 与 q 是否相同。load/store queue 跟踪在途访存，执行 memory disambiguation，并在证明或预测安全时让 load 越过较老的 store。

若后来发现地址冲突，错误的 load 结果和依赖操作需要重放。store 通常不能在指令退休前不可撤销地更新 cache 中的架构可见状态，否则异常或误预测难以恢复。

这些内部规则不等于语言线程内存模型。另一个核心上的线程何时能观察到写入，还涉及 cache coherence、memory ordering 与同步操作，第 16 章会继续讨论。

8. 引擎可以提前完工，账本必须按顺序入账

后面的 independent operation 可以先在执行单元完成，但不能随意把结果写进 architecture state。Reorder buffer 像一册按 program order 排好的账本：只有前面的 instruction 可以安全提交时，后面的结果才依次变得可见。

Reorder buffer（ROB）按程序顺序跟踪在途操作。执行可以乱序完成，retirement/commit 则从最老操作开始：

program order:  A  B  C  D
finish order:   C  A  D  B
retire order:   A  B  C  D

如果 B 发生页故障：

• A 可以表现为已经完成；
• B 报告异常；
• C、D 即使算完，也不能留下架构可见结果；
• 保存的 B 对应状态足以让系统处理异常。

这就是 precise exception 的核心。ROB 的具体字段、结果存放位置与 free-list 设计随微架构变化，不能把一张教科书结构图当作所有 CPU 的电路图。

9. 分支与数据的实际优化顺序

看到 if 不要立即加 __builtin_expect。更可靠的顺序是：

1. 确认热点与输入分布；
2. 查看优化后的汇编，确认分支是否仍存在；
3. 检查编译器是否已经使用条件移动或向量化；
4. 测量 branch、branch miss、cycles、instructions 和 cache 事件；
5. 改变数据布局或算法后重新测量正确性与性能；
6. 在不同目标 CPU 上复核。

编译器 hint 主要影响代码布局和优化判断，不会直接把一条命令写进硬件预测器。错误 hint 可能让常见路径布局变差。

Linux perf 可以访问部分硬件计数器，但事件名、权限与可用性随 CPU 和环境变化。先用 perf list 查看本机，再决定事件组合；虚拟机或容器可能只暴露有限计数器。

10. 一个完整分析例子

int classify_and_sum(const int *values, int length) {
    int sum = 0;
    for (int i = 0; i < length; ++i) {
        int value = values[i];
        if (value >= 0) {
            sum += value;
        } else {
            sum -= value;
        }
    }
    return sum;
}

分析时应提出而不是预设：

• 编译器会保留 branch，还是变成条件移动/绝对值/vector 指令？
• sum 的循环携带依赖会限制多少并行？
• 数据是否连续，能否命中 cache 和触发预取？
• signed int 溢出是否可能，使源程序本身出现未定义行为？
• 正负分布是否有稳定历史，预测器能否学习？

若要做基准，先用不会溢出的数据或更宽类型定义正确语义，再阻止编译器删除结果。否则测到的可能是未定义行为或空循环。

11. 常见误解

“乱序执行改变程序结果顺序。” 内部执行可以越序，架构状态通常按顺序退休，并受 ISA memory-ordering 规则约束。

“ROB 让所有线程看到顺序一致。” ROB 主要解决单核内部 retirement 与异常；跨核可见性需要 cache coherence 和内存模型。

“分支预测只影响控制流。” 错误路径也会占用 cache、TLB 和执行资源，并带来侧信道风险。

“无分支一定更快。” branchless 版本可能执行更多指令、增加依赖或阻碍向量化，必须测量。

“高 IPC 就代表程序更快。” IPC 可能因做了更多无用指令而上升。最终要结合总 instructions、cycles、时间和业务吞吐。

12. 小结

现代 CPU 通过预测与动态调度扩大并行窗口：

• direction predictor、BTB 与 RAS 共同维持取指；
• superscalar 提供同周期多项处理能力；
• register renaming 消除 WAR/WAW 假依赖；
• issue queue 选择已经就绪的操作；
• load/store queue 处理尚未完全确定的内存依赖；
• ROB 让乱序完成最终按程序顺序退休；
• 误预测会撤销架构结果，却可能留下微架构痕迹。

下一章进入C 与内存模型，把单核内部的推测执行与多线程程序允许观察到的顺序明确分开。