15.2 分支预测、超标量与乱序执行
五级流水线能让多条指令重叠，但一遇到分支、cache miss 或长延迟除法，整条流水线仍可能停顿。现代高性能 CPU 会预测下一段控制流、同时取入多条指令，并让 operand 已就绪的操作先占用执行单元；最后再按程序顺序提交可见结果。
这不是让指令毫无规则地乱跑。分支预测、超标量、乱序执行与顺序 retirement 各守一段边界：
- 分支预测决定接下来从哪里取指；
- 超标量表示一个周期能处理多项工作；
- 乱序执行让后面的独立操作越过尚未就绪的操作；
- 顺序 retirement 维持精确异常和架构可见顺序。
1. 分支预测不只猜“跳不跳”
取指前端需要尽早回答：
- 当前指令是不是分支？
- 条件分支会不会跳？
- 若跳转，目标地址是什么？
- 若是函数返回，应回到哪个调用点？
不同结构分别帮助回答这些问题：
- 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 type(taken) is not bool:
raise ValueError("outcome must be bool")
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
assert mispredictions(loop_exit) == 11
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. 执行可以提前完成，结果必须按顺序提交
后面的独立操作可以先完成，但不能随意更新架构状态。ROB 像按程序顺序排好的账本，先到的指令尚未过账，后面的结果就先等着。
Reorder buffer（ROB）按程序顺序跟踪在途操作。执行可以乱序完成，retirement/commit 则从最老操作开始。store 可以退休后仍留在 store buffer 中，尚未对其他核心可见；本线程的提交顺序不是所有线程共享的一张时间表：
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。更可靠的顺序是：
- 确认热点与输入分布；
- 查看优化后的汇编，确认分支是否仍存在；
- 检查编译器是否已经使用条件移动或向量化；
- 测量 branch、branch miss、cycles、instructions 和 cache 事件；
- 改变数据布局或算法后重新测量正确性与性能；
- 在不同目标 CPU 上复核。
编译器 hint 主要影响代码布局和优化判断，不会直接把一条命令写进硬件预测器。错误 hint 可能让常见路径布局变差。
Linux perf 可以访问部分硬件计数器，但事件名、权限与可用性随 CPU 和环境变化。先用 perf list 查看本机，再决定事件组合；虚拟机或容器可能只暴露有限计数器。
10. 一个完整分析例子
下面故意保留 signed int 溢出问题，先诊断正确性，再讨论分支：
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溢出是否可能，使源程序本身出现未定义行为？ - 正负分布是否有稳定历史，预测器能否学习？
例如，单个 INT_MIN 就可能使 sum -= value 溢出；多个普通正数也可能使总和溢出。若改用 int32_t 输入，可先转 int64_t 再取负得到幅度；用 uint64_t 累加时仍应检查 magnitude > UINT64_MAX - sum。更宽不是无限宽。基准需要先确定输入上限和溢出策略，再确保结果会被使用。否则测到的可能是未定义行为或空循环。
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 与内存模型，把单核内部的推测执行与多线程程序允许观察到的顺序明确分开。