CPU的分支预测

一、基础介绍

1.1 概念

分支预测（Branch Prediction）是现代CPU中用于优化指令流水线性能的关键技术，旨在解决条件分支指令（如 if-else、循环等）导致的流水线停顿问题。

1.2 为什么需要分支预测

• 流水线技术：现代CPU通过流水线（Pipeline）并行处理指令，每个时钟周期完成一条指令的不同阶段（取指、解码、执行等）。
• 分支带来的问题：当遇到条件分支（如 if (x > 0)）时，CPU需要等待条件结果（x是否大于0）才能决定下一条指令的位置。这会导致流水线停顿（Pipeline Stall），浪费多个时钟周期。
• 预测的必要性：为了不阻塞流水线，CPU会预测分支的方向（跳转或不跳转），并提前执行预测路径的指令。如果预测正确，性能无损；若错误，则需回滚（惩罚周期）。

1.3 分支预测的分类

1.3.1 静态分支预测

原理：无需历史信息，仅根据指令类型或编译器提示预测。

常见策略：

• 总预测不跳转：假设分支条件不满足，继续执行下一条指令。
• 反向跳转预测跳转：常用于循环（如 for 循环末尾的跳转指令）。
• 编译器提示：通过指令（如Intel的likely/unlikely宏）标记分支概率。

1.3.2 动态分支预测

原理：根据分支指令的历史行为动态调整预测策略。

关键结构：分支历史表（Branch History Table, BHT），记录每条分支指令的近期执行结果。

目前的 CPU 基本都采用的是动态分支预测，动态分支预测能够应对更多的执行情况，而且更容易产生正确的预测。

二、关键数据结构及作用

2.1 分支目标缓冲(Branch Target Buffer, BTB)

• 功能：存储分支指令的 地址（PC） 及其 目标地址（Target PC），实现快速跳转。
• 结构：
  • 类Cache结构：通常为组相联（Set-Associative），通过分支指令的PC哈希到特定组。
  • 条目内容：分支PC、目标PC、预测状态（如饱和计数器）、有效位等。
• 工作流程：
  • 取指时查询BTB：若当前PC命中BTB，则预测跳转并直接获取目标PC。
  • 执行后更新BTB：若实际分支方向或目标地址与预测不符，更新BTB条目。

2.2 返回地址栈(Return Stack Buffer, RSB)

• 功能：专门预测 函数返回（ret指令） 的目标地址，解决嵌套调用导致的预测难题。
• 结构：
  • 硬件栈：通常是先进后出（LIFO）的栈结构，深度有限（如Intel Skylake的RSB深度为16）。
  • 条目内容：函数调用（call）时压入的返回地址。
• 工作流程：
  • call指令：执行时将下一条指令地址（返回地址）压入RSB。
  • ret指令：预测时从RSB弹出栈顶地址作为目标PC。
  • 栈溢出/欠载处理：若RSB空，退化为BTB预测；若溢出，丢弃最旧条目。

2.3 分支历史表(Branch History Table, BHT)

• 功能：记录分支指令的历史行为（跳转/不跳转），用于动态预测方向。
• 结构：
  • 2位饱和计数器：每个分支指令对应一个状态机（如00-强不跳转，11-强跳转）。
  • 索引方式：通过分支PC哈希或结合全局历史（GHR）索引。
• 更新规则：实际分支结果若跳转，则状态+1（上限11）；否则-1（下限00）。

2.4 全局历史寄存器(Global History Register, GHR)

• 功能：记录近期所有分支指令的结果（跳转=1，不跳转=0），用于关联预测。
• 结构：
  • 移位寄存器：长度固定（如10位），每次分支后左移并入最新结果。
  • 与PC哈希：结合当前分支PC和GHR值索引BHT（如gshare算法）。

2.5 总结

数据结构	预测阶段作用	更新阶段操作
BTB	快速判断分支类型及目标地址	新增/更新分支条目及目标地址
BHT/PHT	提供分支方向预测（局部/全局历史）	调整饱和计数器状态
GHR	记录全局分支历史，用于关联预测	左移并入最新分支结果
RSB	专用于ret指令的目标地址预测	call压栈，ret弹栈

三、预测流程

3.1 预测阶段的操作流程

当CPU需要预测一个分支指令时，按以下顺序操作四个表：

步骤1：取指阶段（Fetch Stage）

• 输入：当前指令地址（PC）。
• 操作：
  1. 查询BTB：
     • 用当前PC的哈希值查询BTB，判断是否是已记录的分支指令。
     • 命中BTB：获取分支类型（条件分支/函数调用/返回等）和目标地址。
     • 未命中：默认为非分支指令，继续顺序取指。
  2. 分支类型判定：
     • 条件分支（jcc）：进入BHT/GHR预测流程。
     • 函数调用（`call）**：记录返回地址到RSB。
     • 函数返回（ret）：从RSB弹出目标地址。

步骤2：分支方向预测（条件分支专用）

• 输入：分支指令的PC、全局历史（GHR）。
• 操作：
  1. 索引BHT/PHT：
     • 局部预测：仅用分支PC哈希索引BHT，获取2位饱和计数器状态。
     • 关联预测（如gshare）：将分支PC与GHR异或生成索引，查询PHT。
  2. 生成预测结果：
     • 根据BHT/PHT中的状态（如11=强跳转）预测方向（跳转/不跳转）。

步骤3：目标地址预测

• 条件分支：通过BTB获取目标地址（已提前存储）。
• 函数返回（`ret）：从RSB栈顶弹出目标地址。
• 函数调用（call）：目标地址直接由指令给出，同时将下一条指令地址（返回地址）压入RSB。

步骤4：预取指令

• 根据预测方向和目标地址，从预测路径（跳转目标或顺序下一条）预取指令到流水线。

3.2 执行阶段验证与更新

当分支指令实际执行后，验证预测是否正确，并更新相关数据结构：

步骤1：验证结果

• 实际跳转方向：比较预测方向与实际结果（跳转/不跳转）。
• 实际目标地址：比较预测目标地址与实际地址（如间接跳转地址变化）。

步骤2：更新数据结构

1. BHT/PHT更新：
   • 若预测错误，根据实际结果调整饱和计数器（例如实际跳转则+1，否则-1）。
   • 在关联预测中，更新GHR（将实际结果左移并入全局历史）。
2. BTB更新：
   • 若分支指令未记录在BTB中，新增条目（PC→目标地址）。
   • 若目标地址变化（如间接跳转），更新BTB中的目标地址。
3. RSB维护：
   • call执行时：将返回地址压入RSB。
   • ret执行时：若RSB未空，弹出栈顶地址；若栈空则通过BTB或顺序地址回退。
4. GHR更新：
   • 将实际分支结果（1=跳转，0=不跳转）左移并入GHR寄存器。
   • 例如：GHR原为 0b1011，实际跳转→更新为 0b10111（保留固定长度）。

四、总结

分支预测通过 BTB（目标地址）、BHT/PHT（方向预测）、GHR（全局历史）、RSB（函数返回） 四个表的协同操作，在取指阶段快速预测分支行为，最大化流水线吞吐量。预测错误时，通过更新机制动态修正表的记录，逐步提升预测准确率。理解这一流程有助于在代码中规避分支密集或模式随机的逻辑，从而减少预测错误带来的性能损失。