在现代计算机体系结构中，CPU 通常采用流水线方式执行指令以提升效率。然而，分支指令的存在会导致流水线停滞：CPU 无法提前知晓分支结果，因而难以预先获取并执行分支路径上正确的后续指令。
为解决这一问题，现代处理器普遍采用分支预测技术。当前主流的分支预测方法分为两类：
静态分支预测
静态分支预测基于固定的规则预测分支结果。例如，总是预测分支跳转，或根据目标地址方向预测（目标地址向前预测为不跳转等）。其优势在于实现简单、硬件开销低；缺点是在复杂程序中预测成功率较低。
动态分支预测
动态分支预测的核心思想是利用分支指令的执行历史来预测其未来行为。这种方法有效的前提是分支行为具有重复性和可预测性。
基础动态预测（1-bit PHT）
最简单的动态预测基于分支指令最近一次的执行结果进行预测。它使用一个分支模式历史表（Pattern History Table, PHT）来记录结果。PHT 是一个 1 位表项的表，1 表示跳转（Taken），0 表示不跳转（Not Taken）。预测时，使用分支指令的 PC 地址索引 PHT，获取其上一次的分支结果。
这种方法在分支行为稳定时（如边界固定的长循环）效果较好：
for (int i = 0; i < m; i++) {// do sth.
}
其预测准确率约为 \((m-2)/m\)。但在分支条件频繁变化的场景下表现很差，例如：
if (flag) {// do sth.
}
flag = !flag;
此时预测准确率会降至 0。
基于饱和计数器的分支预测（2-bit PHT）
为了应对分支条件频繁变换的场景，现代处理器通常采用饱和计数器进行优化，即将原有的 PHT 表项扩展为 2 位，其状态定义为：
00: 强不跳转 (Strongly Not Taken)；01: 弱不跳转 (Weakly Not Taken)；10: 弱跳转 (Weakly Taken)；11: 强跳转 (Strongly Taken)。
通常选取 00 作为初始状态。状态转换规则是：预测正确时向“更强”状态移动（如 01 -> 00，10->11），预测错误时向“更弱”或相反状态移动（如 11 -> 10，10 -> 01）。在之前的循环例子中，采用 2-bit 计数器后，第二次进入循环即可达到约 \((m-1)/m\) 的准确率；在条件翻转的例子中，准确率能提升至 50%。
对于绝大多数的程序来说，使用两位的饱和计数器就可以获得较高的正确率。如果增加计数器的位宽，会引起复杂度的上升、更长的 warm-up 过程、更多的存储空间需求。这些额外的开销带来的负面影响可能会大于预测精度提升带来的收益。因此主流的处理器都是基于两位饱和计数器进行分支预测的。
与 1-bit 基础动态预测类似，这里使用 PHT 保存分支指令对应的饱和计数器状态，并使用分支指令 PC 的哈希值作为索引。
基于局部历史的分支预测（BHT+PHT）
仅靠计数器难以匹配更复杂的分支模式。为此，现代处理器中引入了分支历史寄存器（Branch History Register, BHR）。一个 n 位的 BHR 以移位寄存器方式记录该分支指令过去 n 次的跳转结果（最新结果移入最低位）。预测时，使用 BHR 的值（代表该分支的局部历史模式）索引 PHT，获取对应的饱和计数器状态进行预测。
对于之前的条件翻转例子，其分支历史会呈现 01-10-01-10-... 的交替。如果 BHR 长度为 2，PHT 中 01 对应状态可能为 00（强不跳转），10 对应 11（强跳转），总体预测正确率接近 100%。
一个 n 位的 BHR 需要使用 2*2^n 位的 PHT 存储所有饱和计数器的值。在实际系统中，分支指令数量庞大，无法位每条指令分配专用的 BHR 与 PHT。因此，现代处理器使用固定大小的分支历史表（Branch History Table，BHT）来存储 BHR 项，并通过一定的映射关系来索引固定大小的 PHT。这一过程为：
- 使用分支指令的 PC 地址来索引 BHT，获取对应 BHR；
- 将 PC 与 BHR 值进行拼接或异或（目的是减少不同 PC 索引到相同 PHT 项的冲突）；
- 用步骤 2 的结果索引 PHT，得到饱和计数器状态进行预测。
基于全局历史的分支预测（GHR+PHT）
有时，一条分支指令的跳转依赖于其他分支指令的结果（相关性），这是局部历史无法捕捉的。因此，现代处理器引入了全局历史寄存器（Global History Register, GHR），用以捕捉全局分支历史信息。
与 BHR 类似， GHR 也是一个 n 位移位寄存器，记录处理器最近执行的所有分支指令（不区分 PC）的结果（最新结果移入最低位）。对应的 PHT（称为全局 PHT）大小为 2*2^n 位。
预测时，同样使用 PC 与 GHR 拼接/异或的结果索引全局 PHT。
竞争的分支预测
到目前为止，我们已经拥有了两套预测方法：基于局部历史的分支预测方法和基于全局历史的分支预测方法。如何判断当前的分支指令应该使用哪种预测方法呢？Alpha 21264 采用了一种称为竞争的分支预测方法，可以根据分支指令的执行情况自动选择这两种分支预测方法。
这种竞争方法新增了一个 PHT 来对两种预测方法进行选择：当一种方法预测成功率高于另一种方法时，更倾向于采用成功率高的方法。饱和计数器状态机更新规则如下：
- 当 P1 预测正确、P2 预测错误（1/0）时，计数器减 1；
- 当 P1 预测错误、P2 预测正确（0/1）时，计数器加 1；
- 当 P1 与 P2 预测结果一样（1/1 或 0/0）时，计数器保持不变。
动态分支预测的更新时机
理想的分支预测流程是：取指时根据 PC 进行预测 -> 使用预测结果取指 -> 分支指令实际结果计算完成 -> 更新预测器相关结构。
预测器中需要更新的内容主要包括两个部分：
- 饱和计数器：PHT 中分支指令对应的饱和计数器；
- 历史寄存器：GHR 或 BHR。
一般情况下，饱和计数器一般在一条指令退休时进行更新，因为这样设计较为简单，而且不会对分支预测结果产生很大的负面影响：当一条分支指令比较有规律时，其对应的饱和计数器总是处于饱和状态。
而历史寄存器则不同，虽然在一条分支指令退休时再更新历史寄存器虽然是最安全的，但考虑到现代处理器每周期要同时执行多条指令，并且拥有很深的流水线，当一条分支指令退休时，该指令后面的很多条指令都已经进入到流水线中，如果这些指令中存在分支指令，那么他们在进行分支预测时，并没有享受到前面分支指令的结果。
对于 GHR，更新一般在取指阶段进行，即使用分支预测的结果更新 GHR。这里可能会有疑问：如果预测的结果是错误的，那么 GHR 也就保存了错误的内容，是否会对后续的预测产生影响？首先，如果这条分支指令预测错误，那么后面的指令从流水线中被清除，那么他们使用了错误的 GHR 内容也没有关系。其次，处理器中会在提交阶段对 GHR 进行修复。在取指阶段，使用预测结果更新的 GHR 称为 Speculative GHR；在提交阶段，这条分支指令退休时，更新得到的 GHR 称为 Retired GHR，其中保存的内容是正确的。如果分支预测失败，则将后端的 Retired GHR 覆写到 Speculative GHR 中，完成更新。
对于 BHR，更新一般在分支指令退休后进行，因为 BHR 通常与特定的分支指令绑定，在退休时更新也相对安全。
分支地址的预测
分支指令的目标地址分为两种，即直接跳转与间接跳转。在直接跳转分支指令中，由于其偏移值是以立即数的形式在指令中直接给出，所以其目标地址也是固定的，只要记录下这条分支指令的目标地址就可以了；对于间接跳转的分支指令来说，由于目标地址来自于通用寄存器，因此预测不是很容易的事情。
直接跳转类型的分支地址预测（BTB）
对于一条特定的直接跳转类型的分支指令来说，由于其目标地址不会随着程序的执行而变化，因此对目标地址进行预测是很容易的，只需要使用一个表格记下每条直接跳转类型的分支指令对应的目标地址，当再次对这条分支指令进行预测时，只需要查找这个表格就可以得到预测的目标地址了。
由于分支预测是基于 PC 值进行的，不可能为每个 PC 值记录下它的目标地址，所以一般使用组相联 Cache 的形式，储存 PC 到目标地址的映射，这个结构称为分支目标缓存（Branch Target BUffer，BTB）。
如果预测分支指令跳转，而且访问 BTB 时缺失，一般继续使用顺序 PC 地址继续取指，尽管这个地址有很大可能性是错误的。在译码阶段，分支指令的目标地址计算完成，如果与之前取指的地址不一致，则清除流水线。
间接跳转类型的分支地址预测（BTB+RAS）
对于间接跳转类型的分支指令来说，它的目标地址来自于通用寄存器，其内容可能是经常变化的，使用 BTB 无法对其进行准确的预测。不过，大部分的间接跳转分支指令来自于子程序调用的 Call/Ret 指令，它们是有规律的。
在一般的程序中，Call 指令一般用于调用子程序，使得流水线从子程序中开始取指令执行。在子程序中，Ret 指令一般是最后一条指令，它将使流水线从子程序中退出，返回到主程序中的 Call 指令之后，继续执行。对于很多的 RISC 处理器来说，Call/Ret 指令都是伪指令，比如，在 RISC-V 中是这样实现的：
call offset -> auipc x1,offset[31:12]+offset[11]; jalr x1,offset[11:0](x1)ret -> jalr x0,0(x1)
对于程序中固定的一条 Call 指令来说，它每次跳转的目标地址都是固定的，因此可以使用 BTB 对 Call 指令的目标地址进行预测。
对于 Callee 程序中的 Ret 指令而言，它每次跳转的目标地址都不是固定的，但是能与 Caller 程序中的 Call 指令相对应。在嵌套调用过程中，Ret 指令的调用顺序与对应 Call 指令的调用顺序形成 LIFO 的模式。这让我们很容易想到使用栈这种数据结构来维护这一关系。在现代处理器中，相应的硬件结构被称为返回地址堆栈（Return Address Stack，RAS）。每当一条 Call 指令进入流水线，就往 RAS 中写入对应的 PC+4 的值（Call 指令的下一条指令的地址），执行 Ret 指令时就可以在 RAS 的顶部取得对应的返回地址。
在实现中还需要注意两点：（1）如果需要往 RAS 中压入地址，则需要知道当前指令是 Call 指令，然而这个操作一般是在译码阶段完成的。在超标量处理器中，如果 Call 指令在译码阶段才能被识别，而且后面跟着的多条指令包含 Ret 指令时（短的子函数），那么这条 Ret 指令就不能获得 RAS 的收益，造成分支预测失败。这时就需要借助 BTB，在 BTB 中增加一项用来表示分支指令的类型（Call、Ret、其他分支），这样就可以在取指阶段识别出 Call 指令，从而及时地将返回地址保存到 RAS 中。（2）需要增加选择器来选择从 BTB 与 RAS 输出的目标地址。如果从 BTB 中识别出的分支指令为 Ret 指令，那么选择 RAS 的输出作为目标地址。
你可能也会注意到：如果程序的嵌套层数超过了 RAS 的深度应该怎么办？一般有两种做法：（1）当栈满时，放弃记录后续的返回地址。这样，栈中只会记录前几次调用的返回地址，后续的 Ret 指令分支预测都会失败。（2）使用地址循环，将新增的返回地址覆写到栈底。这样，栈中保存的是最新的几次返回地址。由于最旧的返回地址已经被覆盖，最旧的分支指令预测会失败。现代处理器中一般采用第二种方法，因为带来的可能收益会更高。
此外，在递归调用情况下，RAS 都会被同一个返回地址填充，其实这样做是比较低效的。我们可以为 RAS 的每一项添加一个计数器，用来记录连续相同的 Call 指令执行次数，当需要预测 Ret 指令返回地址时，计数器减一或者地址出栈。