Fast Recovery：现代乱序处理器如何快速从分支预测失败中恢复
发布于 • 作者: Ethan
在现代乱序执行（Out-of-Order Execution）处理器中，分支预测错误（branch misprediction） 是性能的重要瓶颈之一。 Fast Branch Recovery 的目标是：在分支预测错误时，用最短时间恢复处理器状态，并重新开始正确路径的执行。
本文从原理、关键数据结构、计算方式（尤其是 b-mask）、以及完整恢复流程四个层面进行系统讲解。
一、问题背景：为什么需要 Fast Recovery
当分支预测错误时，处理器必须完成三件事：
- 清除错误路径上的指令（squash）
- 恢复处理器状态（寄存器映射、ROB、LSQ 等）
- 从正确的 PC 重新取指
如果恢复过程较慢（例如逐条扫描 ROB 修复状态），会导致：
- 分支错误惩罚（misprediction penalty）显著增加
- 整体 IPC（Instructions Per Cycle）下降
Fast Recovery 的核心目标是： 将恢复过程变成“常数时间 + 位运算”的操作，而不是线性扫描。
二、核心思想（Key Idea）
Fast Recovery 的核心是：
为每个未决分支（in-flight branch）保存一份完整的恢复快照（checkpoint）
当分支预测错误时：
- 直接恢复 checkpoint
- 通过位运算快速识别并清除错误路径指令
三、关键数据结构
1. Branch Stack（分支栈）
每个未解析的分支都会占用一个 entry，存储：
- Recovery PC（恢复用的 PC）
- ROB tail 指针
- LSQ tail 指针
- Register Map Table（寄存器重命名表）
- Free List（空闲物理寄存器列表）
- 分支预测器修复信息（可选）
2. b-mask（分支依赖掩码）
这是 Fast Recovery 的核心机制。
定义
每条在飞指令都携带一个 bitmask：
$$ \text{bmask} = \text{所有比它更老但尚未 resolve 的分支集合} $$
例如（4-bit）：
bmask = 1010
表示这条指令依赖两个未决分支（bit1 和 bit3）。
3. 全局 b-mask register
维护当前所有未决分支：
$$ \text{global_bmask} $$
所有新发射的指令都会复制这个值。
四、b-mask 的“计算方式”
这是理解 Fast Recovery 的关键。
1. 指令的 b-mask 如何计算
对于普通指令：
$$ \text{instr.bmask} \leftarrow \text{global_bmask} $$
也就是说：
直接复制当前系统中所有未决分支的集合
2. 分支指令如何分配 bit
假设有 N 个 branch stack entry，对应 N 个 bit。
当一个新分支 dispatch 时：
- 分配一个空闲 entry（例如 bit2）
- 更新全局 bmask：
$$ \text{global_bmask} \leftarrow \text{global_bmask} \mathbin{|} (1 \ll 2) $$
- 保存 checkpoint
3. 分支预测正确时的计算
当某个分支（例如 bit = k）被确认正确：
$$ \text{global_bmask} \leftarrow \operatorname{bitand}(\text{global_bmask}, \sim(1 \ll k)) $$
等价于：
- 清除该 bit
- 表示这个分支不再是 speculative
4. 分支预测错误时：如何判断哪些指令要被清除
关键判断条件：
$$ \operatorname{bitand}(\text{instr.bmask}, \text{branch_bit}) \neq 0 $$
若成立，则：
该指令在错误分支之后 → 必须 squash
五、完整流程（Process）
5.1 Dispatch 阶段（遇到分支）
当一个 branch 被发射：
对 branch
-
分配 branch stack entry
-
分配一个 bit
-
保存 checkpoint：
- Map Table
- Free List
- ROB tail
- LSQ tail
- Recovery PC
-
更新 global bmask
对所有同时发射的指令
$$ \text{instr.bmask} \leftarrow \text{global_bmask} $$
5.2 分支预测正确（Correct Prediction）
当分支 resolve 且预测正确：
- 清除该分支的 bit：
$$ \text{global_bmask} \leftarrow \operatorname{bitand}(\text{global_bmask}, \sim \text{branch_bit}) $$
- 释放 branch stack entry
- 不需要恢复任何状态
5.3 分支预测错误（Misprediction）
这是 Fast Recovery 的核心。
步骤 1：恢复 ROB 和 LSQ
$$ ROB.tail \leftarrow checkpoint.ROB.tail $$
$$ LSQ.tail \leftarrow checkpoint.LSQ.tail $$
效果：
- 删除所有年轻指令（逻辑上）
步骤 2：恢复寄存器重命名状态
$$ MapTable \leftarrow checkpoint.MapTable $$
$$ FreeList \leftarrow checkpoint.FreeList $$
效果：
- 撤销错误路径上的所有寄存器分配
步骤 3：清除执行中错误路径指令
对于所有 RS / FU pipeline 中的指令：
$$ \text{if } \operatorname{bitand}(\text{instr.bmask}, \text{branch_bit}) \neq 0 \Rightarrow \text{squash} $$
步骤 4：清理分支状态
- 清除该分支 bit
- 释放 branch stack entry
步骤 5：恢复执行流
$$ PC \leftarrow \text{correct target} $$
重新开始 fetch
六、一个简单示例
假设最多支持 4 个未决分支（4-bit）：
状态演化
| 时刻 | 操作 | global bmask |
|---|---|---|
| 初始 | 无分支 | 0000 |
| 分支 A | 分配 bit3 | 1000 |
| 分支 B | 分配 bit2 | 1100 |
| 分支 C | 分配 bit1 | 1110 |
指令 bmask 示例
| 指令 | bmask |
|---|---|
| I1（在 A 后） | 1000 |
| I2（在 B 后） | 1100 |
| I3（在 C 后） | 1110 |
如果分支 B 错误（bit2）
检查：
$$ \operatorname{bitand}(\text{instr.bmask}, 0100) $$
结果：
| 指令 | 是否被 squash |
|---|---|
| I1 (1000) | ❌ |
| I2 (1100) | ✅ |
| I3 (1110) | ✅ |
七、为什么 Fast Recovery 快
1. 状态恢复是“整体回滚”
不是逐条修复，而是：
- 指针回退（ROB / LSQ）
- 表恢复（Map Table / Free List）
接近 O(1)
2. 指令筛选是位运算
$$ \operatorname{bitand}(\text{bmask}, \text{branch_bit}) $$
无需比较年龄、无需遍历复杂结构
3. 支持嵌套分支
每个分支：
- 独立 checkpoint
- 独立 bit
可以同时处理多个未决分支
八、总结
Fast Branch Recovery 的本质可以概括为三点：
1. Checkpoint 机制
- 每个分支保存完整恢复状态
2. b-mask 依赖跟踪
- 每条指令记录其依赖的未决分支集合
3. 位运算驱动恢复
- 恢复状态：直接回滚 checkpoint
- 清除指令：按位判断
核心一句话
$$ \text{Fast Recovery} = \text{Checkpoint Restore} + \text{Bitmask-based Squash} $$
它之所以快，不在于减少错误，而在于：
一旦错误发生，可以用极低开销恢复整个处理器状态。