分支目标地址预测

在C++程序中，间接分支（虚函数调用、switch-case跳转表）约占所有分支指令的10%$\sim$15%。如果处理器无法预测间接分支的目标地址，每次间接调用将产生10$\sim$20周期的流水线气泡——对于一个IPC为4$\sim$5的处理器，这意味着仅因间接分支就损失5%$\sim$10%的性能。

从本书的统一视角来看，间接跳转预测是对控制流目标的“投机”——与第 14.0 章和第 15.0 章中讨论的方向预测（投机分支是否跳转）形成互补。方向预测是对1位信息的投机，而目标预测是对48位地址的投机，复杂度高出数个数量级。ITTAGE将第 15.0 章中TAGE预测器的“几何级数历史长度”方法论从方向预测扩展到目标预测，是目前已知最精确的间接目标预测方案。RAS（Return Address Stack）则利用call/ret的LIFO性质，以极小的硬件代价实现了97%以上的返回地址预测精度。在安全层面，BTB和ITTAGE在2018年Spectre变体2漏洞中成为攻击目标（详见第 17.0 章中的系统级集成讨论），推动了分支预测器安全隔离的新设计需求。

读完本章，你将理解BTB、ITTAGE、RAS三大目标预测组件的完整设计，掌握它们在取指流水线中的协同工作方式。

从本书的统一视角来看——处理器设计的本质是在有限的晶体管预算和功耗约束下，通过投机和并行的层层叠加来逼近指令吞吐率的理论上限——目标地址预测将“投机”的复杂度推到了一个全新的层次。第 14.0 章和第 15.0 章中的方向预测是对1位二值信息的投机，预测器只需要在taken和not-taken之间做选择；而目标地址预测是对一个48位地址的投机，搜索空间大了$2^{47}$倍。面对这一指数级增长的不确定性，ITTAGE的策略是将TAGE的多尺度历史方法论从1位扩展到48位——表项存储目标地址（或其紧凑编码）而非饱和计数器——但代价是每项存储开销增大约10倍。RAS则采用了完全不同的投机策略：利用call/ret配对的确定性结构（LIFO），将48位地址的投机问题转化为一个简单的栈操作，以极低的硬件代价实现了$>$97%的精度。这两种方案分别代表了“通用统计投机”和“利用程序结构的确定性投机”——后者的精度远高于前者，但适用范围受限于特定的指令模式。

分支预测的任务不仅仅是判断一条分支指令是否跳转（方向预测），还必须给出跳转的目标地址（target address）。在第 14.0 章和第 15.0 章中，我们系统地讨论了分支方向预测的各种算法。然而，方向预测正确但目标地址预测错误，结果与方向预测失败完全相同——流水线必须被刷新并从正确地址重新取指。在一个20级以上的深流水线处理器中，每次目标地址预测错误都会带来15$\sim$20个周期的惩罚。

目标地址预测的核心挑战在于：取指阶段尚未完成指令译码，处理器甚至不知道当前取指块中哪些指令是分支指令，更不知道它们的目标地址。这意味着目标地址预测必须仅依赖PC值在1个周期内完成——这正是分支目标缓冲（Branch Target Buffer, BTB）的核心功能。

不同类型的分支指令对目标地址预测提出了截然不同的要求：直接跳转的目标地址在指令编码中已经确定，属于PC加偏移量的简单计算；间接跳转的目标地址来自寄存器，每次执行可能不同，需要更复杂的预测机制；函数返回指令的目标地址虽然也来自寄存器（链接寄存器或栈），但遵循严格的后进先出模式，可以通过专门的硬件栈来高效预测。本章将逐一讨论这些问题。

BTB

分支目标缓冲（BTB）是一个由PC索引的硬件Cache结构，存储最近执行过的分支指令的目标地址和类型信息。取指阶段使用当前PC查询BTB：如果命中，说明当前PC处存在一条分支指令，BTB直接提供其目标地址和类型；如果未命中，取指单元按顺序取指继续执行。BTB的查询必须与I-Cache访问并行进行，且在1个周期内返回结果，这样分支预测器才能在下一个周期将预测的目标地址送入取指流水线。

BTB的基本结构

BTB的基本组织与普通的Cache类似，采用组相联结构。每一项（entry）包含三个核心字段：Tag、Target和Type。图图 16.1展示了一个4路组相联BTB的基本结构。

4路组相联BTB的基本结构

各字段的含义如下：

（1）Valid位（V）。标记该表项是否有效。处理器复位时所有Valid位清零。当一条新的分支指令被记录到BTB中时，对应表项的Valid位被置1。

（2）Tag字段。存储分支指令PC的高位部分，用于在BTB命中时进行精确匹配。Tag的宽度决定了别名冲突（aliasing）的概率——更宽的Tag可以减少别名，但增加存储开销。在一个48位虚拟地址空间中，如果BTB有1024个Set、4路组相联，则Index占10位，低2位（字节对齐）不参与索引，Tag需要$48 - 10 - 2 = 36$位来避免所有别名。实际设计中通常只使用部分Tag（如12$\sim$16位），接受极低概率的别名冲突以换取存储节省。

（3）Target字段。存储分支指令的预测目标地址。对于直接跳转，这是PC加偏移量计算的结果；对于间接跳转，这是上次执行时的实际目标地址。Target字段的宽度通常等于完整的虚拟地址宽度（48$\sim$64位），但可以通过后文讨论的紧凑编码技术来压缩。

（4）Type字段。编码分支指令的类型，通常需要2$\sim$3位：

• 条件分支（conditional branch）

• 无条件直接跳转（unconditional direct jump）

• 间接跳转（indirect jump）

• 函数调用（call）

• 函数返回（return）

分支类型信息对后续的预测流水线至关重要。如果BTB报告当前指令是一条函数返回指令，预测器将从返回地址栈（RAS）获取目标地址而非使用BTB中存储的目标地址；如果是条件分支，预测器需要查询方向预测器（如TAGE）来决定是否跳转；如果是无条件跳转，则始终跳转到BTB中存储的目标地址。

设计提示

BTB的核心设计原则是"快速给出足够好的预测"。在取指的关键路径上，BTB必须在1个周期内完成Index解码、Tag比较、结果选择三个步骤。这意味着BTB的容量不能太大——在5 nm工艺下，一个4096项4路组相联的BTB的访问延迟约为1个周期（250 ps$\sim$300 ps），但如果增加到16384项，延迟可能增加到2个周期，需要引入多级BTB的设计。

BTB的索引方式

BTB的索引方式决定了如何将PC映射到BTB的某个Set。最直接的方式是使用PC的低位作为索引，但这可能导致特定的访问模式下产生大量冲突。

PC低位直接索引

最简单的索引方式是截取PC的一段低位作为索引。对于一个有$S$个Set的BTB，Index = PC[$\log_2 S + 1$ : 2]（假设指令最小对齐为4字节）。这种方式的硬件开销最小，无需任何额外的逻辑。

然而，PC低位索引存在系统性冲突（systematic conflict）的问题。许多程序的代码布局具有特定的模式——例如，编译器生成的函数入口地址通常按特定对齐方式排列，循环体的分支指令在地址空间中可能以固定步长分布。这些模式会导致大量不相关的分支指令映射到BTB的同一个Set，引起频繁的替换。

哈希索引

为了缓解系统性冲突，可以对PC进行哈希变换后再用作BTB的索引。常见的哈希方式包括：

（1）XOR折叠。将PC的高位部分与低位部分进行异或（XOR）运算。例如，对于一个1024-Set的BTB，Index = PC[11:2] $\oplus$ PC[21:12]。这种方式将高位地址信息混入索引中，使得地址空间中间隔较远的分支指令更不容易映射到同一个Set。

（2）位重排。对PC的各位进行重新排列（bit permutation），打乱PC的低位模式。例如，将PC[2]与PC[8]交换、PC[3]与PC[10]交换等。这种方式在某些特定的代码布局模式下比XOR折叠更有效。

（3）GHR混入。在BTB索引中混入全局历史寄存器（GHR）的部分位，使得同一条分支指令在不同的执行上下文中可以映射到BTB的不同位置。这种方式与GShare预测器的思路类似，但应用在目标地址预测上。这一技术在ITTAGE等高级间接跳转预测器中被广泛使用（详见16.4.2 节）。

在实际的处理器设计中，XOR折叠是最常用的BTB索引哈希方式，因为它只需要一层XOR门的延迟（约20 ps$\sim$30 ps），几乎不影响BTB的访问延迟。

BTB的查找时序分析

BTB的查找必须在取指流水线的最早阶段完成，其时序约束比I-Cache更为严格——I-Cache可以有2个周期的延迟（在下一个流水级才提供数据），但BTB必须在1个周期内返回预测结果，以便前端在下一个周期就能使用预测的目标地址启动取指。

一个4路组相联BTB的查找时序可以分解为以下步骤：

1. 索引解码（Index Decode）。将PC的Index位段送入Set解码器，选中一个Set中的所有Way。对于1024个Set的BTB，解码器为10:1024译码器，延迟约40 ps$\sim$60 ps。

2. 字线驱动与位线读出（Wordline & Bitline）。选中的字线激活，SRAM单元将数据驱动到位线上。位线的充放电延迟取决于SRAM阵列的物理高度（即每一列的单元数），对于1024-Set $\times$ 4-Way的BTB，每Way的SRAM阵列有1024行，位线延迟约80 ps$\sim$100 ps。

3. 灵敏放大器（Sense Amplifier）。检测位线上的微小电压差并放大为数字信号。延迟约20 ps$\sim$30 ps。

4. Tag比较（Tag Comparison）。将4个Way读出的Tag与PC的高位Tag进行并行比较。每个比较器为12$\sim$16位的相等比较器，延迟约25 ps$\sim$35 ps。

5. 命中选择（Hit Mux）。根据4个Way的比较结果选择命中Way的Target和Type输出。一个4:1多路选择器的延迟约15 ps$\sim$25 ps。

总延迟$\approx 50 + 90 + 25 + 30 + 20 = 215\,\text{ps}$。在4 GHz（周期250 ps）下可以单周期完成，但在5 GHz（周期200 ps）下已经非常紧张。这就是为什么高频率处理器的L1 BTB容量被严格限制在32$\sim$128项——更大的BTB意味着更长的位线延迟和更宽的解码器，无法在单周期内完成查找。

设计提示

BTB的时序优化是处理器前端设计中最关键的挑战之一。以下是常用的时序优化技术：

Tag和Data并行读取。在传统的Cache设计中，可以先读Tag、确认命中后再读Data，以节省无效读取的功耗。但对于BTB，Tag和Data（Target+Type）必须同时读出——因为没有时间在Tag比较后再去读Data。这意味着BTB的每次访问都会读出所有Way的全部数据，功耗高于“先Tag后Data”的设计。

预测地址旁路。当BTB命中且分支被预测为taken时，BTB输出的Target地址需要作为下一个周期的PC送入BTB自身（形成循环依赖）。为了减少这个循环路径的延迟，Target地址可以直接从BTB的数据输出旁路（bypass）到BTB的索引输入，跳过中间的PC寄存器——但这需要在时序上仔细平衡。

Way预测。对于组相联BTB，可以使用一个小型的Way预测器来预测命中的Way编号，然后只读取预测的那一个Way的数据。如果Way预测正确，延迟减少约25%（省去了4:1 Mux和并行Tag比较的延迟）；如果Way预测错误，需要1个额外周期重新读取正确的Way。Way预测的准确率通常在90%$\sim$95%之间。

块级BTB索引

在超标量处理器中，一次取指操作可能取出4$\sim$8条指令。如果BTB按单条指令索引——即每条指令的PC分别查询BTB——那么每周期需要进行4$\sim$8次并行BTB查询，这要求BTB具有多个读端口或多个并行的Tag比较器阵列，硬件开销巨大。

一种更高效的方式是块级索引（block-level indexing）：以取指块的起始地址（而非单条指令的PC）索引BTB。一个BTB表项对应一个取指块，记录该取指块中第一条taken分支的偏移量和目标地址。取指单元根据这个偏移量截断取指块（丢弃分支之后的无效指令），并将目标地址作为下一次取指的PC。

块级索引大幅减少了BTB所需的端口数和比较器数量——每周期只需一次BTB查询。代价是一个取指块中如果包含多条分支指令（且第一条not-taken、第二条taken），块级BTB无法记录第二条分支的信息。解决方案是在BTB表项中记录多条分支的信息——每项包含2$\sim$3个（偏移量, 目标地址, 类型）三元组，分别对应取指块中前几条分支指令。方向预测器配合工作：依次判断每条分支的方向，第一条预测为taken的分支决定实际的跳转目标。

FTB：Fetch Target Buffer

FTB（Fetch Target Buffer）是块级BTB的一种改进形式，由RISC-V香山处理器团队提出并实现。FTB的核心改进是将BTB的组织单元从“单条分支指令”转变为“一个取指块（fetch block）”，每个FTB条目描述一个取指块的完整分支布局。

一个FTB条目包含以下字段：

字段	位宽	说明
tag	12$\sim$16位	取指块地址的部分Tag
slot[0]	20$\sim$24位	第一条分支的信息：偏移量(4位) + 目标地址(13$\sim$16位) + 类型(3位)
slot[1]	20$\sim$24位	第二条分支的信息（可选，仅当块中有第二条分支时有效）
tailSlot	16$\sim$20位	尾部无条件跳转的信息（如jal/j指令）
carry	1位	标记取指块是否跨越Cache line边界
always_taken	2位	标记两条分支是否“总是taken”（用于简化方向预测器的工作）

FTB的设计有几个优势：

1. 每周期只需一次查询。以取指块地址索引FTB，一次查询就获得块内所有分支的信息，无需为每条分支单独查询。

2. 高效的多分支处理。一个FTB条目最多记录2条条件分支和1条无条件跳转，覆盖了绝大多数取指块的分支布局。方向预测器为这2条条件分支分别提供方向预测，取指单元根据第一条taken分支截断取指块。

3. 与预解码信息互补。FTB提供分支的目标地址和类型信息，预解码标记提供指令边界信息，两者配合可以在取指阶段完全确定取指块中的有效指令范围。

FTB的存储格式比传统BTB更紧凑——传统BTB的每项只记录一条分支的信息，而FTB的每项记录一个取指块的完整信息。对于一个包含2条分支的取指块，FTB只需1项，而传统BTB需要2项。这使得FTB在相同的存储预算下可以覆盖更多的取指块。

设计提示

FTB的设计体现了一个重要的原则：预测器的组织粒度应该与取指单元的操作粒度匹配。取指单元以取指块为单位操作（每周期取一个块），因此预测器也应该以取指块为单位提供预测信息。这种匹配简化了预测器与取指单元之间的接口，减少了控制逻辑的复杂度。

传统的“按指令粒度”BTB需要在一个周期内处理取指块中多条指令的预测请求——要么使用多端口BTB（面积大），要么串行查找多条指令（延迟高）。FTB通过“按块粒度”组织彻底避免了这个问题。

多粒度BTB

一些高端处理器使用多粒度BTB（Multi-granularity BTB）来同时支持块级和指令级的目标预测：

• L1 BTB使用块级（FTB风格）组织，每项记录一个取指块的分支布局。L1 BTB容量小（64$\sim$128项），但查询速度快（1周期）。

• L2 BTB使用指令级组织，每项记录一条分支指令的详细信息（包括完整目标地址、类型等）。L2 BTB容量大（4096$\sim$12288项），但查询需要2$\sim$3个周期。

• 当L1 BTB缺失时，从L2 BTB中搜索与当前取指块地址范围匹配的分支条目，组装成一个FTB格式的条目填入L1 BTB。

这种多粒度设计结合了两种组织方式的优点：L1 BTB的块级组织保证了快速的多分支预测，L2 BTB的指令级组织保证了精确的目标地址存储和高覆盖率。

BTB的容量选择

BTB的容量（项数）是性能与面积/功耗之间的核心权衡参数。容量越大，BTB能记录的分支指令越多，命中率越高；但容量增大意味着更大的SRAM面积、更高的访问延迟和更多的功耗。

BTB命中率与容量的关系

BTB命中率受两个因素限制：容量缺失（capacity miss）和冲突缺失（conflict miss）。容量缺失发生在程序的分支指令工作集超过BTB容量时——BTB无法同时记住所有活跃的分支指令。冲突缺失发生在多条分支指令映射到同一个Set、导致相互驱逐时。

表表 16.1给出了不同BTB容量下的典型命中率数据（基于SPEC CPU 2017的测量）。

BTB容量	相联度	命中率(%)	SRAM面积	访问延迟
256项	4路	87$\sim$90	$\sim$3 KB	1周期
512项	4路	91$\sim$93	$\sim$6 KB	1周期
1024项	4路	93$\sim$95	$\sim$12 KB	1周期
2048项	4路	95$\sim$97	$\sim$24 KB	1$\sim$2周期
4096项	4路	97$\sim$98	$\sim$48 KB	2周期
8192项	8路	98$\sim$99	$\sim$112 KB	2$\sim$3周期

不同BTB容量下的命中率（SPEC CPU 2017平均）

从表表 16.1可以看出：BTB命中率与容量的关系呈现明显的边际递减效应。从256项增加到1024项时，命中率提升约5$\sim$6个百分点；但从4096项增加到8192项，命中率仅提升约1个百分点。对于SPEC CPU这类代码足迹相对较小的基准测试来说，2048$\sim$4096项的BTB通常已经足够。但对于大型服务器工作负载（如数据库、Web服务器），代码足迹可达数十MB，分支指令的工作集轻松超过10000条，此时即使8192项的BTB也会出现显著的容量缺失。

面积开销的估算

BTB每项的存储开销取决于Tag、Target和Type字段的宽度：

$$\text{每项位数} = 1_{\text{V}} + W_{\text{Tag}} + W_{\text{Target}} + W_{\text{Type}}$$

以一个典型的配置为例：Tag = 16位，Target = 48位（完整虚拟地址），Type = 3位，加上1位Valid，每项共68位。一个4096项4路组相联的BTB总存储量为$4096 \times 68 = 278528$位$\approx$34 KB。这在处理器核心中已经是一个不小的结构——约为32 KB L1 I-Cache面积的40%$\sim$50%。

性能分析 1 — BTB容量的性能影响

BTB缺失对性能的影响可以用如下公式估算。设分支指令的频率为$f_b$（每条指令中分支指令的比例，典型值0.15$\sim$0.20），BTB缺失率为$m_{\text{BTB}}$，BTB缺失惩罚为$p_{\text{miss}}$周期（通常等于取指到BTB查询结果可用的延迟，约$p_{\text{miss}} = 2\sim 5$周期，因为BTB缺失意味着本周期没有预测到分支，需要等到指令译码后才能识别分支并计算目标地址），则BTB缺失造成的CPI损失为：

$$\Delta\mathrm{CPI}_{\text{BTB}} = f_b \times m_{\text{BTB}} \times p_{\text{miss}}$$

对于$f_b = 0.18$，$m_{\text{BTB}} = 0.05$（5%缺失率），$p_{\text{miss}} = 3$周期，$\Delta\mathrm{CPI}_{\text{BTB}} = 0.027$。看似不大，但对于一个目标IPC为5$\sim$6的高性能处理器来说，0.027的CPI增加意味着约2.5%的IPC损失。如果BTB缺失率增加到10%，IPC损失将达到约5%。

典型处理器的BTB容量

工业界的高性能处理器普遍采用较大的BTB容量：

• Intel Golden Cove（Alder Lake P-core，2021）：L1 BTB 128项，L2 BTB 12288项。

• AMD Zen 4（2022）：L1 BTB 1024项，L2 BTB 7168项。

• Apple Everest（M2 P-core，2022）：BTB总计超过12000项（多级结构）。

• ARM Cortex-X4（2023）：L1 BTB 96项（全相联），L2 BTB 8192项。

从这些数据可以观察到一个共同的趋势：现代处理器普遍采用多级BTB结构——一个小而快的L1 BTB保证1周期的预测延迟，一个大而慢的L2 BTB提供更高的覆盖率。这种层次化设计与Cache层次结构的理念完全一致，将在16.2 节中详细讨论。

BTB容量的工作负载敏感性分析

BTB的容量需求因工作负载类型而异。不同工作负载的分支指令工作集大小差异巨大：

• SPEC CPU整数基准测试。代码足迹中等（约100 KB$\sim$2 MB的热点代码），活跃分支指令数量约1000$\sim$5000条。4096项的BTB通常可以达到97%以上的命中率。

• SPEC CPU浮点基准测试。代码足迹通常较小（以紧密循环为主），活跃分支指令数量约500$\sim$2000条。即使1024项的BTB也能达到96%以上的命中率。

• 数据库查询引擎（如MySQL, PostgreSQL）。代码足迹很大（数MB的热点代码），大量的B+树遍历和查询优化器逻辑包含数以万计的分支指令。即使8192项的BTB命中率也可能低于90%。

• Web服务器（如nginx, Apache）。代码足迹大且分散（网络协议栈、HTTP解析、动态内容生成等多个模块），活跃分支指令数量可达10000$\sim$30000条。

• JIT编译的语言运行时（如V8, HotSpot JVM）。JIT编译产生的代码分布在堆内存的多个不连续区域，代码局部性差，BTB缺失率通常较高。

对于数据中心工作负载（后三类），BTB容量不足是前端性能的主要瓶颈之一。Google在2019年的分析报告中指出，其数据中心工作负载中约30%的前端暂停周期与BTB缺失或I-Cache缺失有关。这促使了Intel在Golden Cove及后续微架构中大幅增加L2 BTB的容量（从5000+项增加到12000+项）。

BTB容量的最优设计方法论

BTB容量的选择需要在面积、功耗、延迟和命中率之间取得平衡。一种系统化的方法是工作负载驱动的容量优化：

1. 使用目标工作负载集合（如SPEC CPU + 服务器工作负载的混合）进行trace驱动仿真。

2. 对每个容量配置（256项到16384项），测量BTB命中率和对应的IPC。

3. 计算每种配置的边际IPC/面积比率——即增加一单位面积带来的IPC提升。

4. 选择边际比率开始显著下降的容量作为设计点。

在5 nm工艺下，一个4路组相联BTB表项（含Tag 12位、Target 24位（紧凑编码）、Type 3位、Valid 1位 = 40位/项）的SRAM面积约为：

$$A_{\text{entry}} = \frac{40}{25 \times 10^6} \approx 1.6 \times 10^{-6} \text{ mm}^2$$

一个4096项BTB的SRAM面积约为$4096 \times 1.6 \times 10^{-6} \approx 0.0065$ mm$^2$，加上外围电路（解码器、比较器、多路选择器）约为SRAM面积的1.5$\sim$2倍，总面积约0.01$\sim$0.013 mm$^2$。在一个5$\sim$10 mm$^2$的高性能核心中，这仅占0.1%$\sim$0.3%——BTB的面积开销非常小，这解释了为什么现代处理器倾向于使用较大的BTB。

BTB的更新策略

BTB的更新操作——即何时向BTB中添加或修改表项——是一个重要的设计决策。更新策略主要考虑以下几个问题：

（1）何时分配新表项。最简单的策略是在每条分支指令退休（retire/commit）时，如果该分支不在BTB中则分配新表项。但这种"全部分配"策略可能导致BTB被大量冷分支（只执行一次的分支指令）占据。一种优化是只在分支预测为taken时才分配——对于not-taken的分支，顺序取指即可获得正确的下一个PC，无需BTB提供目标地址。这种策略可以将BTB的有效容量提升10%$\sim$15%，因为避免了为not-taken分支浪费BTB空间。

（2）推测更新 vs. 退休更新。推测更新在分支执行阶段（尚未退休）就写入BTB，延迟低但可能写入错误路径上的分支信息。退休更新在分支指令确认退休后才写入BTB，保证写入的信息一定正确，但延迟较高——从分支执行到退休可能有10$\sim$20个周期的延迟，在此期间同一条分支的后续实例仍然会BTB缺失。在实际处理器中，通常采用推测更新 + 错误恢复的策略：分支执行阶段立即更新BTB，如果后来发现该分支在错误路径上，则撤销更新（或接受偶尔的BTB污染，因为错误路径上的分支信息通常会被后续的正确路径执行所覆盖）。

（3）替换策略。BTB的替换策略与Cache类似。常见的替换策略包括LRU（Least Recently Used）、随机替换和NRU（Not Recently Used）。对于组相联BTB，LRU是最常用的策略。对于全相联的L1 BTB，精确LRU的硬件开销（$O(N^2)$个比较器用于维护LRU序列）在32$\sim$64项时仍可接受。

紧凑BTB编码

如前所述，BTB中Target字段是存储开销的最大来源——一个完整的48位虚拟地址占了整个表项的60%$\sim$70%。如果能压缩Target字段的宽度，就能在相同的面积预算下容纳更多的BTB项，从而提高命中率。

部分目标地址存储

许多分支指令的目标地址与其自身PC之间只有低位不同——高位部分完全相同。这是因为大多数分支跳转的距离相对较短，尤其是条件分支和函数内的直接跳转。利用这一特征，可以只在BTB中存储目标地址与PC之间的差异位（differing bits）。

具体来说，如果一条分支指令位于地址0x0040_1234，其目标地址为0x0040_1300，两者的高20位（0x00401）完全相同，只有低12位不同。此时BTB只需存储12位的低位差异即可——查询时将存储的低位与PC的高位拼接得到完整目标地址。

这种方案需要一个额外的区域标记位（region bit），用于指示存储的低位宽度是否足够覆盖实际的跳转距离。如果一条分支指令的目标地址距离PC非常远（跨越了低位覆盖的范围），则需要回退到存储完整目标地址或使用其他机制。

偏移量编码

另一种紧凑编码方式是直接存储从分支指令PC到目标地址的有符号偏移量（signed offset）：

$$\text{offset} = \text{Target} - \text{PC}$$

由于大多数条件分支的跳转距离在$\pm$4 KB以内，一个13位的有符号偏移量就可以覆盖绝大多数情况。对于跳转距离更远的分支（如跨函数的直接跳转），可以使用更宽的偏移量字段或回退到完整地址存储。

具体来说，可以将BTB表项设计为两种格式：

• 短格式：存储一个$N$位有符号偏移量（如$N = 13$），覆盖$\pm$4 KB的跳转范围。一个额外的位标记当前项使用短格式。

• 长格式：存储完整的目标地址（如48位）。使用长格式的表项需要更多存储空间，但可以精确记录任意距离的跳转目标。

在实际的程序中，约85%$\sim$90%的分支指令的跳转距离在$\pm$4 KB以内，因此短格式可以覆盖绝大多数情况。混合使用短格式和长格式，平均每项的Target字段宽度可以从48位降低到约18$\sim$22位，节省约50%的存储空间。

案例研究 1 — AMD Zen系列的紧凑BTB编码

AMD Zen系列处理器的L2 BTB采用了紧凑编码来最大化容量。根据公开的微架构分析，Zen 4的L2 BTB拥有7168项，但其每项的存储位宽远小于"Tag + 完整48位Target"的朴素方案。Zen 4使用了区域编码（region encoding）技术：将虚拟地址空间划分为多个区域（region），每个区域有一个共享的高位基地址。BTB表项只存储区域索引（几位）加上区域内的偏移量，而区域基地址存储在一个小型的区域表（Region Table）中。查询时，先从BTB获取区域索引和偏移量，再从区域表读取基地址并拼接，即可恢复完整的目标地址。

这种设计利用了代码的空间局部性——活跃的分支指令通常集中在少数几个代码区域内。一个16项的区域表就可以覆盖当前活跃的大部分代码区域。每个BTB项的区域索引只需4位，区域内偏移量只需16$\sim$20位，加上Tag和Type字段，每项约40$\sim$45位——比朴素方案节省了30%$\sim$40%的存储。这种节省使得Zen 4能够在有限的面积预算下将L2 BTB扩展到7168项。

压缩Tag

除了压缩Target，Tag字段同样可以压缩。使用完整的36位Tag可以完全消除别名，但代价高昂。实践中通常只使用部分Tag（如8$\sim$16位），以极低的别名概率换取显著的存储节省。对于一个12位的部分Tag，别名概率约为$1/2^{12} \approx 0.024\%$——每4000次BTB访问中约有1次别名冲突，在大多数工作负载下影响可以忽略。

进一步，可以对Tag进行哈希压缩——将完整的PC高位通过一个哈希函数压缩为更短的Tag。例如，将36位的PC高位通过CRC-12压缩为12位的Tag。哈希压缩产生的Tag具有更好的随机性，比简单截断高位的方案具有更低的系统性别名概率。

紧凑编码的综合效果

表表 16.2总结了各种紧凑编码技术对BTB每项存储宽度的影响。

编码方案	V	Tag	Target	Type	总宽度
朴素方案	1位	36位	48位	3位	88位
部分Tag	1位	12位	48位	3位	64位
部分Tag+偏移量	1位	12位	13位	3位	29位$^\dagger$
区域编码	1位	12位	18位	3位	34位

紧凑编码对BTB表项宽度的影响

$^\dagger$需额外1位标记短/长格式，长格式回退到48位Target。加权平均约35$\sim$38位。

从88位的朴素方案到34位的区域编码方案，每项的存储宽度降低了约60%。这意味着在相同的面积预算下，紧凑编码可以使BTB容量扩大到朴素方案的2.5倍——例如从3000项扩展到7500项。考虑到BTB命中率在3000$\sim$8000项范围内的边际收益（见表表 16.1），这一容量扩展可以带来2$\sim$3个百分点的命中率提升，直接转化为可观的IPC改善。

多级BTB

与Cache层次结构的动机类似，单一的BTB在容量和延迟之间面临两难：小BTB可以保证1周期的访问延迟，但覆盖率不足；大BTB可以提供高命中率，但访问延迟增加到2$\sim$3个周期，在取指的关键路径上引入额外的气泡。多级BTB（Multi-level BTB）通过层次化设计来解决这一矛盾。

图图 16.2展示了一个典型的多级BTB组织及其与取指流水线的交互。

多级BTB与取指流水线的交互

小而快的L1 BTB

L1 BTB是多级BTB层次中最快的一级，其设计目标是在1个时钟周期内完成查询并返回预测结果。为了满足这一严格的时序约束，L1 BTB通常具有以下特征：

（1）极小的容量。L1 BTB通常只有32$\sim$128项。在5 nm工艺下，32$\sim$64项的全相联结构或128项的4路组相联结构可以在一个约250 ps的时钟周期内完成访问。

（2）全相联或高相联度。由于L1 BTB的容量很小，冲突缺失的影响非常大。全相联组织可以完全消除冲突缺失，最大化有限容量的利用率。32$\sim$64项的全相联BTB的比较器数量仍在可接受的范围内——每个比较器只需比较12$\sim$16位的Tag，32个并行比较器的面积和功耗开销相当于一个小型CAM。

（3）LRU或近似LRU替换。全相联的L1 BTB通常使用精确LRU或tree-PLRU替换策略，确保最近使用的分支指令始终保留在L1 BTB中。

Intel Golden Cove的L1 BTB是一个典型案例：它只有128项，但通过高效的替换策略，在大多数工作负载下仍能达到85%$\sim$90%的命中率。这128项覆盖了最"热"的分支指令——在典型的程序中，90%以上的分支执行集中在少数几十条分支指令上（分支执行的帕累托分布）。

ARM Cortex-X4的L1 BTB更为激进：仅96项全相联。ARM的设计理念是L1 BTB只需覆盖最内层循环和最频繁执行的分支指令。只要这些"超热"分支在L1 BTB中命中，其余分支的1$\sim$2周期延迟（L2 BTB查询）对整体性能的影响有限。

L1 BTB的预填充策略

L1 BTB的容量小意味着它的内容变化频繁——热分支指令频繁地被填入和替换。一种优化L1 BTB命中率的策略是预填充（prefill）：当分支预测器（通过L2 BTB或FTQ）预测到即将执行的取指块中包含分支指令时，提前将该分支的信息从L2 BTB填充到L1 BTB中。

预填充的时机可以与FDIP（取指导向的指令预取，见第 17.0 章）配合：当FDIP发出I-Cache预取请求时，同时检查L2 BTB中对应地址的分支信息，并将命中的分支表项填充到L1 BTB。这样当取指单元实际到达该地址时，L1 BTB已经包含了所需的分支信息，避免了L1 BTB冷缺失。

预填充的代价是L2 BTB需要额外的读带宽（用于预填充读取），以及L1 BTB需要额外的写带宽（用于接收预填充的表项）。在L2 BTB的读端口空闲时（如当前取指未发生L1 BTB缺失），预填充读取可以复用这个空闲端口，不增加额外的硬件。

L1 BTB与NLP的关系

在某些处理器设计中，L1 BTB被简化为一个Next-Line Predictor（NLP）——每个取指块地址对应一个“下一个取指块地址”。NLP不存储分支的类型、偏移量等详细信息，只简单地记录“上次从这个取指块跳转到了哪里”。NLP的优势是极低的延迟（因为不需要Tag比较——使用直接映射，PC的部分位直接索引一个SRAM项读取目标地址）和极小的面积。

NLP的劣势是精度有限：（1）直接映射导致别名冲突频繁；（2）同一个取指块中如果有多条分支且方向在运行时交替变化，NLP无法跟踪——它只记住上一次的方向。

在覆盖式预测的框架下，NLP作为L0预测器工作，其精度不足由L1预测器（基于L2 BTB + TAGE）来弥补。NLP的存在使得在大多数情况下（NLP正确时，约85%$\sim$90%）前端不产生预测气泡，只有NLP错误时（约10%$\sim$15%）产生1$\sim$2周期的气泡（L1覆盖）。

L1 BTB的流水线位置

L1 BTB在取指流水线中的位置至关重要。在最理想的设计中，L1 BTB的查询与PC的生成在同一个周期内完成——当前周期的PC用于查询L1 BTB，BTB在同一周期末返回预测结果（命中/缺失、目标地址、分支类型），取指单元在下一个周期使用预测的目标地址（如果预测为taken）或PC+取指宽度（如果预测为not-taken或缺失）作为新的PC。

这种"零气泡"的流水线组织要求L1 BTB的访问延迟严格控制在一个时钟周期之内。在高频率设计（$>$ 4 GHz）中，这意味着L1 BTB的关键路径——从PC输入到预测结果输出——不能超过约250 ps。这一严格的时序约束是L1 BTB容量被限制在32$\sim$128项的根本原因。

当L1 BTB缺失但L2 BTB命中时，取指流水线会出现1$\sim$2个周期的预测气泡（prediction bubble）。在这些气泡周期中，取指单元按顺序取指（假设no-branch），直到L2 BTB的结果可用后才修正取指方向。如果L2 BTB的结果表明存在一条taken分支，取指单元需要丢弃气泡周期中错误取出的指令并从正确地址重新取指——效果类似于一次小规模的流水线刷新。

大而慢的L2 BTB

L2 BTB的设计目标是提供高覆盖率，容忍2$\sim$3个周期的访问延迟。L1 BTB缺失时，查询结果从L2 BTB获取，但会引入1$\sim$2个周期的取指气泡。

L2 BTB通常具有以下特征：

（1）大容量。L2 BTB的容量通常为4096$\sim$12288项，足以覆盖大型工作负载中大部分活跃的分支指令。

（2）组相联组织。由于容量较大，全相联组织不再可行。L2 BTB通常采用4$\sim$8路组相联，Set数量为512$\sim$2048。

（3）紧凑编码。L2 BTB是存储预算的大头，紧凑编码（部分目标地址、偏移量编码、区域编码等）在L2 BTB上的收益最为显著。通过紧凑编码将每项从68位压缩到40$\sim$45位，8192项的L2 BTB从68 KB降低到41 KB$\sim$45 KB。

（4）访问延迟。在5 nm工艺下，一个8192项8路组相联的L2 BTB的访问延迟约为2$\sim$3个时钟周期。

L2 BTB的流水线化访问

L2 BTB的多周期访问延迟需要在取指流水线中仔细安排。一种常见的设计是将L2 BTB的查询与L1 BTB的查询并行启动——不等待L1 BTB缺失再查询L2 BTB。这种“并行查询”策略的优势是在L1 BTB缺失时，L2 BTB的结果可以更快可用（因为L2 BTB的查询已经在L1 BTB查询的同时启动了）。代价是L2 BTB在每个周期都被读取，即使L1 BTB命中（此时L2 BTB的结果被丢弃），增加了功耗。

另一种策略是序列化查询——先查询L1 BTB，只有在L1缺失时才查询L2 BTB。这种策略节省了L2 BTB在L1命中时的功耗，但在L1缺失时引入了额外的延迟（L2 BTB的查询在L1缺失确认后才启动）。

在实践中，对于低功耗处理器（如移动端）通常采用序列化策略，对于高性能处理器通常采用并行策略。一种折衷方案是预测性并行：使用一个简单的L1命中概率预测器来决定是否并行启动L2 BTB查询——当预测L1可能缺失时（如当前PC从未命中过L1 BTB），并行启动L2查询；当预测L1可能命中时，不启动L2查询。

L2 BTB的替换策略

L2 BTB的替换策略对其有效覆盖率有重要影响。常见的策略包括：

LRU（Least Recently Used）。替换同一Set中最近最少使用的条目。LRU是最直观的策略，在大多数工作负载下表现良好。但精确LRU对于8路或更高相联度的L2 BTB需要大量的状态位（每Set需要$\log_2(8!) \approx 16$位来维护完整的LRU序列）。

BIP（Bimodal Insertion Policy）。新填入的条目以较低的优先级插入（插入到LRU位置而非MRU位置），只有在该条目再次被访问时才提升到MRU位置。BIP可以抵御“扫描”模式的BTB污染——当程序顺序遍历大量分支指令时，BIP防止这些只执行一次的分支指令驱逐BTB中的热条目。

RRIP（Re-Reference Interval Prediction）。为每个条目维护一个2$\sim$3位的预测计数器，预测该条目下次被引用的时间间隔。新插入的条目根据其来源（BTB预取 vs. 实际缺失）设置不同的初始RRIP值。RRIP比LRU更灵活，能够更好地区分不同频率的分支指令。

L1 BTB和L2 BTB之间的交互方式通常有两种：

• 包含式（inclusive）。L1 BTB的内容是L2 BTB的子集。L1 BTB缺失但L2 BTB命中时，命中的表项被同时写入L1 BTB（替换L1 BTB中最近最少使用的表项）。这种方式实现简单，但L1 BTB的替换可能导致被替换的表项在L2 BTB中被标记为"最近使用"，影响L2 BTB的替换决策。

• 排他式（exclusive）。L1 BTB和L2 BTB互不包含。L1 BTB缺失但L2 BTB命中时，命中的表项从L2 BTB移动到L1 BTB；被L1 BTB替换的表项写回到L2 BTB。排他式设计使得L1 BTB和L2 BTB的有效容量更大（总容量 = L1 + L2），但实现更复杂。

设计权衡 1 — L2 BTB的容量与延迟权衡

L2 BTB的容量选择取决于目标工作负载。对于SPEC CPU等代码足迹较小的桌面/HPC工作负载，4096$\sim$8192项的L2 BTB通常已经足够，命中率可达97%$\sim$99%。但对于云计算和服务器工作负载——如数据库查询引擎（MySQL、PostgreSQL）、Web服务器（nginx）、JIT编译的Java/JavaScript程序——代码足迹可达数十MB，活跃分支指令数量可达数万条。此时即使12288项的L2 BTB命中率也可能低于90%。

针对这一挑战，一种方案是引入L3 BTB——一个容量更大（如32768$\sim$65536项）但延迟更高（4$\sim$6周期）的第三级BTB。另一种方案是使用区域BTB等技术来有效扩展覆盖范围（见16.2.3 节）。

区域BTB

区域BTB（Region BTB）是一种利用代码空间局部性来扩展BTB有效覆盖范围的技术。其核心观察是：程序的代码段通常集中在虚拟地址空间的少数几个区域（region）内，每个区域对应一个函数、一个编译单元或一个共享库。

区域BTB的工作原理如下：

（1）将虚拟地址空间划分为固定大小的区域（如每个区域4 KB$\sim$64 KB）。

（2）维护一个小型的区域表（Region Table），每项记录一个活跃区域的高位基地址和区域元数据（如该区域内分支指令的密度）。

（3）BTB表项不再存储完整的Target地址，而是存储一个区域ID（Region Table的索引，通常3$\sim$5位）加上区域内的偏移量。查询时，通过区域ID从Region Table读取基地址，与偏移量拼接得到完整目标地址。

这种设计有两个显著优势：

• 存储压缩。区域ID只需3$\sim$5位，区域内偏移量取决于区域大小（对于16 KB的区域，偏移量为14位），两者之和远小于完整的48位虚拟地址。

• 预取提示。区域表可以记录每个区域内的分支指令分布信息，帮助BTB预取即将需要的分支信息。当程序从一个区域跳转到另一个区域时（如函数调用），区域表可以提示BTB预加载新区域内的分支条目。

区域BTB的主要限制是：如果程序同时活跃在大量不同的代码区域中（如微服务框架调用大量不同库的函数），区域表可能频繁替换，导致性能下降。区域表的大小通常为8$\sim$32项，在大多数工作负载下足以覆盖活跃的代码区域。

区域BTB的实现细节

区域BTB的实现涉及以下微架构细节：

区域大小的选择。区域大小（即每个区域覆盖的地址范围）决定了区域内偏移量的位宽。区域越大，偏移量越宽，但区域的数量越少（在相同的活跃代码范围下需要更少的区域表项）。典型的区域大小选择如下：

区域大小	偏移量位宽	16 MB代码所需区域数	适用场景
4 KB	12位	4096	不适用（区域太多）
16 KB	14位	1024	嵌入式处理器
64 KB	16位	256	桌面/HPC处理器
256 KB	18位	64	服务器处理器
1 MB	20位	16	大代码足迹服务器

对于服务器工作负载（代码足迹16$\sim$64 MB），选择256 KB或1 MB的区域大小使得区域表只需16$\sim$64项就能覆盖所有活跃代码。但较大的区域意味着较宽的偏移量字段（18$\sim$20位），减少了紧凑编码的节省量。

区域表的更新策略。当一条分支指令的目标地址落在一个新区域中（该区域不在区域表中）时，需要在区域表中分配一个新条目。如果区域表已满，使用LRU策略替换最近最少使用的区域——被替换区域中所有BTB条目的区域索引变得无效（因为对应的基地址已被覆盖），这些条目在后续查询时会因为地址不匹配而被视为无效。

这种“级联失效”是区域BTB的一个潜在问题——替换一个区域表条目可能导致数十到数百个BTB条目同时失效。缓解方法包括：（1）增大区域表的容量（从16项增加到32项），降低替换频率；（2）在替换区域时主动清除受影响的BTB条目（标记为无效），避免后续的假命中。

案例研究 2 — Samsung Exynos处理器的区域BTB

Samsung Exynos系列处理器（基于自研Mongoose/M系列核心）在分支预测前端中使用了区域BTB技术。根据公开的专利文献，其设计将代码空间划分为32 KB的区域，使用一个16项的全相联区域表。区域表的每项除了基地址外，还包含一个4位的"分支密度"字段——记录该区域内分支指令的平均密度。当取指进入一个高分支密度的区域时，BTB预取逻辑会主动加载该区域附近的分支表项到L1 BTB中，减少后续的L1 BTB缺失。

在SPECint 2017的gcc和perlbench等大代码足迹工作负载上，这种区域感知的BTB预取使得L1 BTB的等效命中率提升了5$\sim$8个百分点，同时L2 BTB的面积预算减少了约20%。

区域BTB与ASLR的交互

地址空间布局随机化（Address Space Layout Randomization, ASLR）是现代操作系统的标准安全特性，它在每次程序启动时随机化代码段的加载地址。ASLR对区域BTB产生直接影响：由于基地址在每次运行时不同，上一次运行中积累的区域信息在下一次运行中完全无效。

然而，ASLR通常只改变地址的高位（页号部分），同一区域内各分支指令的相对位置（区域内偏移量）保持不变。因此，区域BTB可以在ASLR下正常工作——每次程序启动后，区域表会在前几千条分支指令的执行过程中重新被填充。热身期（warm-up period）通常在微秒量级，对长期运行的工作负载几乎没有影响。

区域BTB在共享库场景中的表现

区域BTB在动态链接的程序中特别有效。一个典型的Linux应用程序可能链接了数十个共享库（libc, libm, libpthread, libssl等），每个共享库被加载到虚拟地址空间的不同区域。区域BTB自然地为每个共享库分配一个区域表条目，使得跨库的分支跳转可以通过区域索引高效地恢复完整的目标地址。

一个有趣的现象是：同一个共享库在不同进程中可能被加载到不同的虚拟地址（由ASLR决定），但库内的分支布局是相同的。如果BTB使用虚拟地址索引（而非物理地址），不同进程中同一个库的分支信息无法共享。一种理论上的优化是使用库内偏移量（library-relative offset）来索引BTB——但这需要硬件知道每个虚拟地址所属的共享库及其加载基地址，实现复杂度很高。

案例研究 3 — Apple M系列处理器的BTB设计

Apple的M系列处理器（基于Firestorm/Everest高性能核心）在分支预测前端方面表现出色——微基准测试显示其BTB容量和分支预测精度均处于业界领先水平。根据公开的逆向工程分析，Apple的BTB设计有以下特点：

• 超大容量L2 BTB。Apple M2的高性能核心据推测拥有超过12000项的L2 BTB，比同代的Intel和AMD处理器更大。这使得Apple的处理器在大代码足迹工作负载上具有更高的BTB命中率。

• 高效的紧凑编码。Apple可能使用了多级区域编码，将每项的存储宽度压缩到约30$\sim$35位，从而在有限的面积中容纳了更多的条目。

• 激进的预取。Apple的前端据推测使用了类似FDIP的技术，利用分支预测器的预测结果驱动I-Cache预取，在大代码足迹工作负载上显著降低了前端暂停。

• 深度解耦。Apple的前端采用了深度解耦设计（分支预测器与取指单元之间有大容量的FTQ），使得预测器可以在I-Cache缺失期间继续运行，积累大量的取指地址缓冲。

Apple处理器的前端优势在“代码密集型”工作负载（如Web浏览器的JavaScript引擎、编译器）上表现得最为明显——这些工作负载的代码足迹大、函数调用频繁，前端性能是整体IPC的关键瓶颈。

BTB与虚拟/物理地址

BTB的索引和Tag使用虚拟地址还是物理地址是一个重要的设计决策，与L1 Cache的虚实地址选择类似。

虚拟地址索引（VIPT/VIVT）

大多数BTB使用虚拟地址索引和虚拟地址Tag（VIVT）。原因如下：

• BTB必须在取指流水线的最早阶段工作——此时TLB查询可能尚未完成（特别是在I-TLB缺失的情况下），物理地址不可用。使用虚拟地址可以让BTB查询与TLB查询并行进行。

• BTB的主要目的是快速提供下一个PC值，而PC本身就是虚拟地址——使用虚拟地址索引的BTB与PC选择逻辑之间不需要任何地址转换。

VIVT BTB的潜在问题包括：

同义词（Synonym）。不同的虚拟地址可能映射到同一个物理地址（如共享内存映射）。在同义词情况下，同一条分支指令可能以不同的虚拟地址出现在BTB中，浪费了BTB容量。但对于I-Cache和BTB来说，同义词问题通常不如D-Cache严重——因为代码段很少被多次映射到不同的虚拟地址。

同形字（Homonym）。相同的虚拟地址在不同的进程中映射到不同的物理地址。如果不同进程共享BTB（不清空），进程A的分支信息可能被进程B错误地使用。ASID标记可以解决同形字问题——BTB条目中的ASID字段确保不同进程的条目不会相互命中。

物理地址索引（PIPT）

一些处理器（如某些ARM核心）使用物理地址索引BTB，以避免同形字问题。物理地址BTB的优势是：

• 不需要ASID标记——物理地址在所有进程中唯一。

• 共享代码（如共享库）的分支信息可以被所有使用该库的进程共享，提高了BTB的有效利用率。

物理地址BTB的劣势是：BTB查询必须等待TLB完成地址转换，增加了BTB的有效访问延迟。在高频率处理器中，TLB的访问延迟通常为1$\sim$2个周期，这会将BTB的有效延迟从1个周期增加到2$\sim$3个周期——对于L1 BTB来说这是不可接受的。

一种折衷方案是VIPT（虚拟地址索引、物理地址Tag）：使用虚拟地址的低位作为BTB索引（不需要TLB转换），使用物理地址的高位作为Tag（需要TLB转换）。这使得BTB索引可以在TLB查询之前开始，但Tag比较需要等待TLB完成。在典型的流水线设计中，BTB索引和SRAM读取在第1个周期完成（使用虚拟地址），Tag比较在第2个周期完成（使用TLB转换后的物理地址），总延迟为2个周期。

直接跳转类型的目标预测

直接跳转（direct jump/branch）指的是目标地址在指令编码中以立即数形式给出的分支指令。在RISC-V中，beq、bne、blt、bge等条件分支指令以及jal无条件跳转指令都属于直接跳转——它们的目标地址是PC加上一个有符号偏移量的结果。直接跳转的目标地址是确定的（由指令编码唯一确定），不随执行上下文变化。

偏移量的编码

对于直接跳转，目标地址的计算非常简单：

$$\text{Target} = \text{PC} + \text{sign\_extend}(\text{offset})$$

其中offset是指令编码中的立即数字段。在RISC-V的B型指令格式中，offset字段为12位（实际编码13位偏移量，最低位隐含为0），覆盖$\pm$4 KB的跳转范围。在J型指令格式中，offset字段为20位（实际编码21位偏移量），覆盖$\pm$1 MB的跳转范围。

然而，这个简单的加法计算存在一个关键问题：在取指阶段，指令尚未被译码，处理器不知道取指块中哪些字节构成了分支指令，更不知道offset字段的值。要在取指阶段完成目标地址计算，必须先完成至少部分的指令译码——这引入了额外的流水线延迟。

在最简单的设计中（如5级流水线的教学处理器），目标地址的计算在译码阶段（ID）完成：译码器识别出分支指令，提取offset字段，通过加法器计算PC + offset。但对于超标量处理器，这意味着目标地址在译码阶段才可用，从取指到目标地址可用有2$\sim$3个周期的延迟——这几个周期内取指阶段按顺序取出的指令可能全部无效。

BTB正是为解决这一问题而设计的：它在取指阶段直接给出预测的目标地址，无需等待译码和计算。对于直接跳转，BTB中存储的目标地址在第一次执行时被记录，此后每次BTB命中都直接使用这个预先计算好的地址。由于直接跳转的目标地址不变，BTB中记录的地址始终正确——只要BTB命中，目标预测就一定正确。

设计提示

直接跳转的目标预测在原理上是"简单"的——一旦BTB记录了正确的目标地址，就永远不会预测错误（只要BTB命中）。目标预测的唯一失败来源是BTB缺失。这意味着对于直接跳转，增大BTB容量就是提高目标预测精度的最直接手段。

直接跳转的目标验证

虽然BTB命中时直接跳转的目标预测“理论上”一定正确，但在实际系统中存在一些使BTB中存储的目标地址变得无效的场景：

自修改代码（Self-Modifying Code）。程序在运行时修改了自己的代码——例如，JIT编译器生成新代码覆盖了旧代码区域，或动态补丁（dynamic patching）修改了函数入口。此时BTB中缓存的旧目标地址不再正确。

代码段卸载。在动态链接的程序中，共享库可能在运行时被卸载和重新加载到不同的地址。BTB中基于旧地址的目标信息变得无效。

ITLB失效。如果I-TLB中的映射关系被修改（如操作系统更新了页表），虚拟地址到物理地址的映射可能改变，使得BTB中基于虚拟地址的目标信息对应到错误的物理代码。

处理这些场景的标准方法是在代码段被修改时清空BTB——这通常通过一条专门的指令（如ARM的IC IVAU指令集维护操作，或RISC-V的FENCE.I指令）来触发。FENCE.I指令要求处理器确保在该指令之后的取指操作能够看到之前所有的存储操作——这隐含了清空BTB、I-Cache和前端流水线的需求。

FENCE.I的性能代价可能很高：清空整个BTB意味着随后需要完整的冷启动热身。对于频繁进行JIT编译的应用（如JavaScript引擎），FENCE.I可能每秒执行数千次，每次都触发BTB冷启动。一种优化是部分清空——只清空与被修改代码地址范围对应的BTB条目，而非清空整个BTB。但这需要硬件支持按地址范围清空BTB的操作，增加了实现复杂度。

目标地址的缓存

除了BTB之外，一些处理器还使用专门的目标地址缓存（Target Address Cache）来加速直接跳转的目标计算。

预计算目标地址

一种优化是在指令填入I-Cache时就预先计算所有直接跳转的目标地址，并将结果存储在I-Cache的辅助字段中。具体来说：

（1）当一个Cache行从L2 Cache填入L1 I-Cache时，硬件扫描Cache行中的所有指令，识别其中的直接分支指令。

（2）对于每条直接分支指令，使用其PC和offset字段计算目标地址。

（3）将计算结果存储在I-Cache行的附加数据域中——每条可能的分支指令对应一个预计算的目标地址。

当取指阶段从I-Cache读取一个取指块时，同时获得该取指块中所有直接分支指令的预计算目标地址。配合预译码信息（识别哪些指令是分支指令），取指单元可以在不查询BTB的情况下直接获得直接分支的目标地址。

这种方案的代价是I-Cache需要额外的存储空间来保存预计算的目标地址。对于一个64 B的Cache行（最多包含16条32位指令），假设平均有2$\sim$3条分支指令，每个目标地址48位，额外存储约$3 \times 48 = 144$位$\approx$18 B——约为Cache行数据的28%。这一开销并不小，但可以通过紧凑编码（只存储偏移量而非完整地址）来显著降低。

与BTB的协同

预计算目标地址和BTB可以协同工作：BTB负责在取指最早期（甚至在I-Cache访问之前）给出"第一次预测"，而预计算的目标地址在I-Cache访问完成后提供"验证"。如果两者结果不一致，说明BTB中的信息可能已经过时（如代码被修改），此时以I-Cache的预计算结果为准并更新BTB。

这种双重机制在自修改代码（self-modifying code）和JIT编译场景中特别有价值——JIT编译器动态生成的代码可能覆盖已有代码区域，此时BTB中缓存的旧目标地址失效，而I-Cache在重新填充时会重新计算正确的目标地址。

预计算目标地址的存储优化

预计算目标地址的I-Cache附加存储可以通过以下技术来优化：

差分编码。不存储完整的目标地址，而是存储目标地址与分支指令PC之间的差值（偏移量）。由于直接分支的偏移量在指令编码中已经给出，预计算实际上不需要额外存储——只需要标记哪些指令是分支指令（1位/指令）。这使得预计算目标地址的额外存储降低到仅每指令1位的分支标记。

共享目标缓存。将一个cacheline中多条分支指令的预计算目标地址存储在一个共享的小型缓存中，而非为每条指令预留固定的目标地址字段。由于大多数cacheline中只包含0$\sim$2条分支指令，共享缓存只需要2$\sim$3个目标地址槽就能覆盖绝大多数情况。

惰性计算。不在I-Cache填充时立即计算目标地址，而是在取指阶段按需计算。具体来说，当取指块从I-Cache读出后，一个简单的偏移量提取和加法电路在取指流水线的下一级计算目标地址。这种方案不需要额外的I-Cache存储，但目标地址比BTB查找延迟了1个周期。

Decode-time Target Computation

在某些处理器设计中，直接跳转的目标地址不在取指阶段计算，而是推迟到解码阶段完成。这简化了取指阶段的硬件，但意味着目标地址在解码后才可用——对于BTB未命中的直接跳转，需要等待解码完成后才能纠正取指方向。

解码阶段的目标计算延迟通常为2$\sim$3个周期（从取指到解码完成）。在这段时间内，取指单元假设没有分支，按顺序取指。当解码器发现一条直接跳转指令且其目标地址与当前取指方向不同时，触发一次“解码级重定向”——取消顺序取出的指令，从正确的目标地址重新取指。解码级重定向的代价（2$\sim$3个周期的气泡）小于执行级重定向（15$\sim$20个周期），但仍然不如BTB命中时的0周期气泡。

这种设计策略适用于面积和功耗受限的中低端处理器核心——BTB的面积预算较小，不能覆盖所有分支指令，因此需要解码级目标计算作为BTB缺失时的后备机制。

BTB冷启动问题

当程序刚开始执行时，BTB中没有任何分支信息——所有的BTB查询都会缺失。这就是冷启动（cold start）问题。冷启动阶段的分支目标预测准确率接近零（对于直接跳转），因为取指单元不知道取指块中是否存在分支指令，只能按顺序取指。

冷启动的影响范围取决于程序的分支工作集大小。对于一个分支工作集为2000条分支指令的程序，如果每条分支平均需要执行2次才能被BTB记录（第一次缺失，第二次命中），那么BTB的热身需要约4000条分支指令的执行——对应约2万$\sim$3万条指令的执行。在一个4 GHz的处理器上，这只需要不到$10\,\mu$s。对于长时间运行的工作负载，冷启动的影响可以忽略。

然而，在上下文切换频繁的场景下（如操作系统调度频率为1 ms），冷启动问题更加显著。每次上下文切换后，新进程/线程的BTB工作集需要重新热身。一些处理器通过在上下文切换时不清空BTB来缓解这一问题——不同进程的分支信息共存于BTB中，依赖Tag匹配来区分。但这引入了安全隐患：恶意进程可能通过BTB侧信道推断其他进程的代码布局（类似Spectre-BTB攻击）。

BTB预热加速技术

BTB预取（BTB Prefetch）是一种加速BTB热身的技术。当程序首次执行一段代码时，I-Cache会从L2 Cache填充指令数据。在这个填充过程中，硬件可以对填充的指令进行预解码，识别其中的分支指令，并将分支信息预填充到BTB中——即使这些分支指令尚未被执行。

BTB预取的实现流程如下：

1. I-Cache行从L2填充时，预解码逻辑扫描Cache行中的所有指令。

2. 对于识别为直接分支的指令，计算其目标地址（PC + offset），并在BTB中分配一个表项。

3. 对于识别为间接分支的指令（如jalr），只记录分支的位置和类型（目标地址尚不可知，需要实际执行后才能填充）。

4. 对于识别为call指令的分支，标记类型为call，以便取指阶段遇到时正确操作RAS。

BTB预取可以将直接分支的BTB冷启动缺失完全消除——只要指令已经在I-Cache中，其分支信息就已经在BTB中。对于间接分支，BTB预取可以提前记录分支的存在和类型，虽然目标地址仍需等待首次执行后填充。

BTB预取的代价包括：（1）预解码逻辑需要额外的硬件面积（约等于一个简单的指令译码器）；（2）BTB需要额外的写带宽来处理预取填充的写入（与正常的BTB更新竞争写端口）；（3）预取填充的BTB条目可能替换掉更有价值的已有条目。

跨上下文BTB保留是另一种策略。在上下文切换时不清空BTB，而是通过ASID（Address Space ID）来隔离不同进程的BTB条目。每个BTB条目存储一个额外的ASID字段（通常4$\sim$8位），查询时只匹配ASID相同的条目。这使得不同进程的BTB条目可以在BTB中共存而不相互干扰。

ASID隔离的BTB在频繁上下文切换的场景中特别有效——进程A被切换出去后，其BTB条目仍然保留在BTB中；当进程A被切换回来时，其BTB条目仍然有效，无需重新热身。代价是每个BTB条目增加了ASID字段的存储开销（4$\sim$8位/项），以及查询时需要额外比较ASID（增加少量延迟）。

性能分析 2 — BTB冷启动的IPC影响

以SPEC CPU 2017的gcc基准测试为例，分析BTB冷启动的IPC影响。gcc的代码足迹约1.5 MB，活跃分支指令约4000条。

在一个4096项L2 BTB + 128项L1 BTB的配置下：

• 完全冷启动。BTB从空开始，需要约8000条分支指令的执行（每条分支平均2次执行：首次缺失 + 首次命中）来填满BTB。假设每10条指令一条分支，8000条分支对应约80000条指令。在热身期间，BTB缺失率从100%逐渐下降到$\sim$5%。平均BTB缺失率约50%，每次缺失惩罚3个周期。额外的CPI损失$\approx 0.18 \times 0.5 \times 3 = 0.27$。对于目标IPC=5的处理器，这导致约5%的IPC损失——在80000条指令（约$20\,\mu$s）的热身窗口内。

• BTB预取。由于gcc的代码在执行前已经被I-Cache预取填充，BTB预取机制可以在分支首次执行前就填充BTB。直接分支的BTB缺失率降低到$\sim$0%，只有间接分支和call/ret的首次目标需要等到执行后填充。总的BTB冷启动IPC损失降低到$<1\%$。

• ASID隔离。如果gcc之前已经运行过并被切换出去，BTB中仍保留其分支信息。切换回来时BTB命中率立即恢复到热态水平。冷启动IPC损失为0%。

间接跳转类型的目标预测

间接跳转（indirect jump/branch）指的是目标地址来自寄存器而非指令编码的分支指令。在RISC-V中，jalr指令属于间接跳转——其目标地址为$\texttt{rs1} + \text{offset}$，取决于寄存器rs1的运行时值。间接跳转的目标地址可能在每次执行时不同，这使得目标预测变得极其困难。

间接跳转在实际程序中的典型来源包括：

• 虚函数调用。C++/Java中的虚函数调用通过虚函数表（vtable）间接跳转到目标方法。同一个虚调用点可能跳转到不同类的不同方法实现。

• switch-case语句。编译器通常将大型switch-case语句编译为跳转表（jump table），通过间接跳转实现O(1)的分发。

• 函数指针调用。C语言中的函数指针、回调函数等通过间接跳转实现。

• 解释器分发。解释型语言（如Python、JavaScript解释器、JVM）的字节码分发循环使用间接跳转来跳转到每个字节码的处理程序。

间接跳转的频率因程序类型而异。在C程序中，间接跳转约占所有分支指令的3%$\sim$5%；在面向对象的C++/Java程序中，这一比例可达10%$\sim$15%；在解释器密集的工作负载中可达20%$\sim$30%。虽然频率不高，但间接跳转的预测失败率通常远高于条件分支——BTB只记录上一次的目标地址，如果目标频繁变化，BTB的命中率会急剧下降。

性能分析 3 — 间接跳转对性能的影响

间接跳转虽然频率低，但其预测失败的代价极高。以一个典型的服务器工作负载为例：假设间接跳转频率$f_{\text{ind}} = 0.02$（每100条指令中有2条间接跳转，不含ret），BTB的间接跳转命中率为70%（即30%的间接跳转BTB缺失或目标错误），每次预测失败的流水线惩罚为18周期，则间接跳转造成的CPI损失为：

$$\Delta\mathrm{CPI}_{\text{indirect}} = f_{\text{ind}} \times (1 - \text{accuracy}) \times p_{\text{penalty}} = 0.02 \times 0.30 \times 18 = 0.108$$

这0.108的CPI损失对于目标IPC为5$\sim$6的处理器来说意味着约10%的性能下降——仅仅因为2%的间接跳转指令。如果使用ITTAGE将准确率从70%提升到90%，CPI损失降低到0.036，性能恢复约7%。这解释了为什么现代处理器愿意投入可观的硬件预算来改善间接跳转预测。

间接分支目标缓冲

间接分支目标缓冲（Indirect Branch Target Buffer, IBTB）是专门用于间接跳转目标预测的硬件结构。与通用BTB不同，IBTB利用执行历史信息来区分同一条间接跳转指令在不同上下文中的不同目标。

最简单的IBTB使用PC + 全局历史来索引：

$$\text{IBTB\_Index} = h(\text{PC}, \text{GHR})$$

其中$h$是一个哈希函数（通常为XOR或某种折叠哈希），GHR是全局历史寄存器。不同的执行路径会产生不同的GHR值，从而在IBTB中映射到不同的表项。如果一条间接跳转指令在路径A执行时总是跳转到目标$T_A$，在路径B执行时总是跳转到目标$T_B$，那么IBTB可以通过不同的GHR值将这两种情况分别存储，实现上下文相关的目标预测。

IBTB的每一项包含：

• Tag：用于验证匹配的标签（通常是PC和GHR的哈希值的一部分）。

• Target：在该上下文中的预测目标地址。

IBTB的容量通常为256$\sim$2048项。容量的选择取决于程序中间接跳转的上下文多样性——对于一个有$N$条间接跳转指令、每条平均有$K$个不同目标的程序，IBTB至少需要$N \times K$项来避免容量缺失。在典型的SPEC CPU工作负载中，$N \times K$通常在几百到几千的量级。

IBTB的局限性

简单IBTB的主要局限在于它是一个无层次的平面结构——所有的（PC, GHR）映射到一个全局的表，不同历史长度的相关性无法被有效区分。某些间接跳转的目标可能只与最近2$\sim$3条分支的历史相关，而另一些可能需要20$\sim$30条分支的历史才能精确预测。简单IBTB使用固定长度的GHR，无法同时适应这两种情况。

这一局限性促使了ITTAGE预测器的诞生——它将TAGE预测器的核心思想（几何级数历史长度、标签匹配）应用到间接跳转目标预测上，实现了目前已知最精确的间接目标预测。

IBTB的容量与相联度

IBTB的组织通常采用组相联结构，与通用BTB分开实现。分开的原因在于：通用BTB需要覆盖所有类型的分支指令（条件分支、直接跳转、call/ret），而IBTB只服务于间接跳转——将两者分离可以为各自优化存储格式和索引方式。IBTB中的每项需要存储完整的目标地址（因为间接跳转的目标可能跨越很大的地址范围，偏移量编码的覆盖率较低），但不需要存储分支类型（因为所有表项都是间接跳转）。

典型的IBTB容量配置为512$\sim$2048项、4$\sim$8路组相联。索引使用PC和GHR的XOR哈希。GHR的参与长度（即哈希中使用多少位GHR）是一个关键的调优参数——太短（如4位）无法区分足够多的上下文，太长（如64位）可能引入过多的别名冲突。实践中通常使用8$\sim$16位的GHR参与长度。

IBTB的上下文编码技术

为了提高IBTB区分不同执行上下文的能力，可以在索引哈希中使用更丰富的上下文信息：

调用栈签名（Call Stack Signature）。维护一个$k$位的哈希值，每次call指令执行时将call地址的低位折叠异或到签名中，每次ret执行时将对应的call地址折出。调用栈签名编码了当前的函数调用上下文——在不同的调用路径下，签名值不同，使得同一条间接跳转在不同调用路径下映射到IBTB的不同位置。

数据依赖特征（Data-dependent Feature）。某些间接跳转的目标地址与其源寄存器的值直接相关。例如，虚函数调用的目标取决于对象的vtable指针，而vtable指针的值取决于对象的实际类型。如果处理器能够在预测阶段获取源寄存器的值（或其部分位），就可以将其用作IBTB的索引特征。但这需要执行阶段的数据前馈到预测阶段——在乱序处理器中，分支指令的源操作数值在预测阶段通常不可用（还在等待之前的指令产生结果），因此数据依赖特征在实际硬件中很难使用。一种替代方案是使用上次目标地址作为间接索引——即IBTB的索引中混入“上一次该间接跳转的实际目标地址”，利用目标地址的时间相关性来提高预测精度。

ITTAGE间接目标预测器

ITTAGE（Indirect Target TAGE）将TAGE预测器（见第 15.0 章）的架构扩展到间接跳转目标预测。其核心思想是：维护多个以不同历史长度索引的目标地址表，查询时选择匹配的最长历史表中的目标地址作为预测结果。

图图 16.3展示了ITTAGE的整体结构。ITTAGE的结构与TAGE高度相似，包含以下组件：

（1）基础表（Base Table, $T_0$）。只用PC索引（不使用历史），每项存储一个默认目标地址。容量通常为256$\sim$1024项。

（2）标签索引表（Tagged Tables, $T_1, T_2, \ldots, T_M$）。共$M$个表（通常$M = 4\sim 6$），每个表使用不同长度的全局历史进行索引。历史长度呈几何级数增长，例如$L_1 = 4, L_2 = 8, L_3 = 16, L_4 = 32, L_5 = 64, L_6 = 128$。每个表的每项包含Tag字段和Target字段。

（3）查询逻辑。并行查询所有$M+1$个表。在所有Tag匹配的表中，选择使用最长历史的那个表的Target作为预测结果。直觉是：如果一个目标地址与较长的历史相关，那么它的预测置信度更高。

（4）有用位（Useful Counter, $u$）。每个标签索引表项包含一个1$\sim$2位的"有用"计数器，用于分配新表项时的替换决策。当一个新的间接跳转需要被记录但所有相关的Set都已被占满时，有用计数器为0的表项被优先替换。

ITTAGE间接目标预测器的结构

ITTAGE与方向预测的TAGE的关键区别在于：TAGE表项存储的是1位的方向预测（taken/not-taken）加一个2$\sim$3位的置信度计数器，而ITTAGE表项存储的是一个完整的目标地址（48位或经过紧凑编码的20$\sim$30位）。这使得ITTAGE的每项存储开销远大于TAGE，通常ITTAGE的总容量只有TAGE的1/3$\sim$1/5。

图图 16.4进一步展示了ITTAGE多表架构的内部细节，包括各表的表项结构和几何级数历史长度的索引方式。

ITTAGE多表架构的内部详细结构。基础表$T_0$不使用历史，只用PC索引；标签索引表$T_1\sim T_5$使用几何级数增长的历史长度，每项包含Tag、Target和useful字段。所有表并行查询，选择匹配的最长历史表的Target作为预测输出。

ITTAGE的紧凑目标编码

为了在有限的存储预算下最大化ITTAGE的表项数量，目标地址的紧凑编码至关重要。ITTAGE可以使用与BTB类似的编码技术：

相对偏移量编码。存储目标地址相对于分支指令PC的有符号偏移量。对于虚函数调用，目标方法通常与调用点位于同一个共享库或可执行文件中，偏移量通常在$\pm 2$ MB以内（21位有符号偏移量可以覆盖）。但对于跨库调用（如调用libc中的函数），偏移量可能很大。

目标地址压缩。将48位虚拟地址压缩为24$\sim$30位的部分地址，恢复时使用分支PC的高位补全。这种方案假设目标地址与分支PC位于同一个高地址区域——对于大多数程序，这一假设是成立的（因为代码段通常连续分布在虚拟地址空间的一个区域内）。

区域编码。与BTB的区域编码类似，ITTAGE可以使用共享的区域表来存储目标地址的高位部分。每个ITTAGE条目只存储区域索引（4位）和区域内偏移量（16$\sim$20位），总共20$\sim$24位——远小于完整的48位地址。

使用紧凑编码后，ITTAGE的每项存储可以从约62位（12位Tag + 48位Target + 2位useful）降低到约38位（12位Tag + 24位紧凑Target + 2位useful），存储效率提高约40%。在相同的总预算下，ITTAGE可以容纳约60%更多的表项。

ITTAGE的流水线化

ITTAGE的查询需要与TAGE方向预测器并行进行。在时序设计上，ITTAGE面临与TAGE类似的挑战：

• BP0阶段：计算各表的索引和标签哈希，启动SRAM读取。

• BP1阶段：SRAM数据读出，标签比较，最长匹配选择，输出预测目标地址。

ITTAGE的关键路径与TAGE基本相同（索引哈希$\to$SRAM读取$\to$Tag比较$\to$优先级选择），因此ITTAGE可以与TAGE共享相同的流水线阶段划分。在BP1阶段结束时，TAGE输出预测方向，ITTAGE输出预测目标地址，两者结合形成完整的预测结果（方向+目标）。

如果当前分支不是间接跳转（由BTB的类型字段判断），ITTAGE的查询结果被忽略——这种情况下ITTAGE的SRAM读取是"无用"的，浪费了功耗。一种功耗优化是在BTB返回结果后再决定是否激活ITTAGE的SRAM——但这需要BTB结果在ITTAGE SRAM读取之前可用，时序上可能不允许。另一种方案是使用时钟门控（clock gating）：当BTB缺失时，不激活ITTAGE的SRAM（因为BTB缺失意味着当前地址没有分支信息，ITTAGE也无需查询）。

性能分析 4 — ITTAGE的预测精度

在CBP（Championship Branch Prediction）竞赛中，ITTAGE在间接跳转目标预测上展现了卓越的精度。以SPEC CPU 2006的perlbench为例——这是一个Perl解释器，包含大量的间接跳转（字节码分发循环）。简单BTB对间接跳转的预测准确率约为55%$\sim$65%，简单IBTB（1024项，固定16位历史）可达75%$\sim$80%，而ITTAGE（6个表，总计4096项，历史长度4$\sim$128）可达88%$\sim$92%。

类似的改善在虚函数密集的C++工作负载（如xalancbmk、omnetpp）中也可以观察到。ITTAGE的优势来自于它能够自动适应不同间接跳转指令所需的历史长度——某些switch语句只需4位历史就能精确预测，而某些解释器分发循环需要64位或更长的历史。

ITTAGE的存储预算

ITTAGE的存储预算是其设计中的核心约束。假设一个典型配置：

• 基础表$T_0$：512项，每项 = 48位Target = 512 $\times$ 48 = 24576位

• 标签索引表$T_1 \sim T_5$：每表512项，每项 = 12位Tag + 48位Target + 2位Useful = 62位，5个表共$5 \times 512 \times 62 = 158720$位

• 总计：$24576 + 158720 = 183296$位$\approx$22.4 KB

如果使用紧凑编码将Target压缩到24位（偏移量编码），总存储降低到约12.5 KB——这是一个在高性能处理器核心中可接受的预算。

ITTAGE的表项分配与更新

ITTAGE的表项分配策略直接影响预测精度。当一次间接跳转预测失败（预测目标$\neq$实际目标）时，需要在某个标签索引表中分配一个新表项来记录正确的（PC, 历史, 目标）关联。分配策略如下：

（1）从命中表的下一级（使用更长历史的表）开始，寻找一个可以分配的位置。如果该位置的有用计数器$u = 0$（表示当前表项无用），则替换该表项。

（2）如果连续多个表中都没有$u = 0$的位置，则全局递减所有表项的$u$计数器（"老化"操作），为后续的分配创造机会。

（3）新分配的表项将Tag设置为当前（PC, 历史）的哈希值，Target设置为实际目标地址，$u$计数器初始化为0。

更新策略方面，当一次预测成功（预测目标 = 实际目标）时，命中表项的$u$计数器递增（表示该表项被证明有用）。当预测失败时，命中表项的$u$计数器递减。

这种分配和更新机制使得ITTAGE能够自适应地利用不同长度的历史：对于只需短历史就能准确预测的间接跳转，短历史表中的表项会积累较高的$u$值，阻止被替换；对于需要长历史的间接跳转，长历史表中的表项会被分配并逐渐变得"有用"。

ITTAGE的路径历史增强

ITTAGE的预测精度可以通过在索引哈希中混入路径历史（Path History）来进一步提升。路径历史不仅记录分支的方向（taken/not-taken），还记录最近若干条分支指令的PC地址信息。对于间接跳转预测来说，路径信息特别有价值——同一条间接跳转指令在不同的调用路径下可能跳转到不同的目标，路径历史可以帮助区分这些不同的上下文。

在ITTAGE中集成路径历史的方式是：将路径历史寄存器（PHR）与全局方向历史（GHR）一起参与各标签索引表的哈希计算。具体而言，表$T_i$的索引变为：

$$\text{index}_i = h(\text{PC}, \text{GHR}[L_i{-}1:0], \text{PHR}[P_i{-}1:0])$$

其中$P_i$为表$T_i$使用的路径历史长度。路径历史长度也可以采用几何级数配置，与方向历史长度配合。

路径历史增强的ITTAGE在虚函数调用密集的C++工作负载上可以将间接跳转预测准确率提高3$\sim$5个百分点。代价是PHR需要推测更新和恢复，增加了检查点的存储开销。

ITTAGE与BTB的协同

ITTAGE通常与通用BTB分开实现，作为一个专门的间接跳转预测器。两者的协同工作流程如下：

1. 取指阶段查询BTB。如果BTB命中且分支类型为“间接跳转”，同时查询ITTAGE。

2. 如果ITTAGE命中（即某个标签索引表命中），使用ITTAGE的预测目标地址替代BTB中存储的目标地址。

3. 如果ITTAGE未命中（所有标签索引表都不匹配），使用ITTAGE基础表（或BTB）中的默认目标地址。

4. 当间接跳转在执行阶段被解析后，如果实际目标与预测目标不同，同时更新BTB和ITTAGE。

这种协同设计使得简单的间接跳转（如只有一个目标的单态调用点）由BTB处理（无需ITTAGE的复杂查询），而复杂的多目标间接跳转由ITTAGE提供上下文相关的精确预测。

硬件描述 1 — ITTAGE的完整预测与更新流程

以一个5表ITTAGE（$T_0\sim T_5$，历史长度$L = \{0, 4, 8, 16, 32, 64\}$）为例，其预测和更新流程如下：

预测：

1. 使用PC索引基础表$T_0$，获取默认目标地址$\text{target}_0$。

2. 并行地，使用PC和不同长度的GHR索引$T_1\sim T_5$，读取各表项的Tag和Target。

3. 将读出的Tag与计算的Tag进行比较。设$T_3$和$T_5$命中。

4. 选择匹配的最长历史表$T_5$的Target作为预测目标。

5. 记录预测元数据：命中表号=5，备选表号=3，备选目标=$T_3$.Target。

更新（当间接跳转在执行阶段被解析后）：

1. 如果预测正确（$T_5$.Target = 实际目标）：$T_5$.u递增。

2. 如果预测错误（$T_5$.Target $\neq$ 实际目标）：

   • 将$T_5$.Target更新为实际目标（如果$T_5$.u > 0则$T_5$.u递减而不更新Target）。

   • 在$T_5$之后的更长历史表中（如果有的话）尝试分配新表项。

   • 如果分配失败（所有候选位置的u $> 0$），全局aging：所有候选位置的u递减。

ITTAGE与方向TAGE的核心差异

ITTAGE从第 15.0 章的方向TAGE继承了几何级数历史长度和最长匹配优先的架构方法论，但两者在多个关键维度上存在本质差异。表表 16.3总结了这些区别。

维度	方向TAGE（第 15.0 章）	ITTAGE（目标预测）
表项核心字段	2$\sim$3位饱和计数器（ctr）	24$\sim$48位目标地址（或紧凑编码）
每项存储	$\sim$16位（tag + ctr + u）	$\sim$38$\sim$62位（tag + target + u）
典型表数量	10$\sim$12张	4$\sim$6张（受存储预算限制）
最长历史	1000$\sim$2000位	64$\sim$256位
更新机制	计数器饱和递增/递减	目标地址直接替换
别名容忍度	高（计数器可纠偏）	低（目标地址替换是破坏性的）
应用分支类型	所有条件分支	仅间接跳转（3%$\sim$15%的分支）

最关键的差异在于别名容忍度。方向TAGE的饱和计数器具有天然的抗别名能力——即使两条行为相反的分支映射到同一表项，计数器会在0/1附近震荡，仍有约50%的机会给出正确预测。而ITTAGE中，如果两条间接跳转映射到同一表项且目标不同，表项的Target字段只能存储一个地址——被“挤出”的那条跳转将100%预测错误。这一特性决定了ITTAGE对标签匹配的依赖比方向TAGE更强：ITTAGE通常使用12$\sim$16位的Tag（方向TAGE只用8$\sim$12位），以降低破坏性别名的概率。

另一个重要差异是存储优化的空间。方向TAGE的表项固定为ctr + tag + u，几乎没有压缩空间。ITTAGE的目标地址字段（名义上48位）则有大量压缩空间：多数间接跳转的目标与PC位于同一个4 MB区域内，只需存储低22位偏移量；结合区域编码技术（与16.1.4 节中BTB紧凑编码相同的方法），可以进一步压缩到16$\sim$20位。这使得ITTAGE在实际实现中的每项存储可以从62位压缩到约34$\sim$38位，在有限预算下容纳几乎翻倍的表项。

设计提示

ITTAGE的设计揭示了一个通用的架构原则：当同一架构方法论（TAGE）被应用于不同的预测问题时，存储格式和预算分配需要根据问题特征重新优化。方向预测的1位输出使得TAGE可以使用极小的表项（16位/项），支持10$\sim$12张表和超过1000位的历史长度。目标预测的48位输出迫使ITTAGE使用大得多的表项，将表数减少到4$\sim$6张，历史长度缩短到64$\sim$256位。但这并不意味着ITTAGE的覆盖范围更窄——间接跳转的“有效历史深度”通常比条件分支短（虚函数调用的目标通常只与最近的几条分支路径相关），4$\sim$6张表已足以覆盖绝大多数间接跳转的历史需求。

虚函数调用的模式

虚函数调用（virtual dispatch）是间接跳转在面向对象程序中最重要的来源。理解虚函数调用的运行时模式对于设计高效的间接目标预测器至关重要。

在C++中，一个虚函数调用的编译结果通常如下：

# obj指针在a0中
  ld    t0, 0(a0)        # 从对象头部加载vtable指针
  ld    t1, 16(t0)       # 从vtable中加载目标方法地址
  jalr  ra, t1, 0        # 间接调用目标方法

从分支预测的角度看，关键在于最后一条jalr指令的目标地址t1的值——它取决于对象的实际类型（即vtable的内容）。根据运行时行为的不同，虚函数调用点可以分为三种模式：

（1）单态（Monomorphic）。该调用点在运行时始终调用同一个类的方法——t1的值始终相同。这种情况下，BTB就可以完美预测（命中即正确）。约60%$\sim$70%的虚函数调用点是单态的。

（2）少态（Oligomorphic/Megamorphic with few targets）。该调用点在运行时调用2$\sim$4个不同类的方法——t1有少量不同的取值。IBTB或ITTAGE可以通过历史上下文区分不同目标，预测精度取决于不同目标之间是否存在可利用的模式。约20%$\sim$25%的虚函数调用点属于这一类。

（3）多态（Megamorphic）。该调用点在运行时调用大量不同类的方法——t1的取值可能有数十甚至上百种。这是最难预测的情况，即使ITTAGE也难以有效处理。约5%$\sim$15%的虚函数调用点属于这一类。

Dominant Target优化。一个关键的经验观察是：即使对于少态和部分多态的调用点，通常也存在一个主导目标（dominant target），其出现概率远高于其他目标。实测表明，约80%的间接调用site具有一个出现概率超过90%的dominant target。这一观察催生了一种分层预测策略：BTB缓存每个间接跳转site的dominant target（即最近最频繁出现的目标地址），大多数情况下BTB命中即可正确预测；只有当BTB预测错误（即实际目标不是dominant target）时，才查询ITTAGE获取基于历史上下文的精确预测。这种分层策略将ITTAGE的查询频率降低了约80%，显著节省了ITTAGE的动态功耗——因为ITTAGE的多表SRAM读取是高功耗操作（6张表并行读取约消耗0.5$\sim$1 mW/查询），而BTB查询已经是取指流水线的必要操作，无额外功耗开销。

在工程实现中，BTB可以为间接跳转表项附加一个1位的“confidence”标志：当连续$N$次（如$N = 8$）间接跳转的目标与BTB中记录的目标一致时，confidence置1；此后只要confidence为1，就不激活ITTAGE查询。一旦BTB预测错误，confidence清零，后续查询将同时激活BTB和ITTAGE。这种自适应激活机制在dominant target占比高的工作负载上可以将ITTAGE的动态功耗降低70%$\sim$80%，而对预测精度的影响不到0.5%的MPKI。

案例研究 4 — Java虚函数调用的预测挑战

Java的虚函数调用模式对间接跳转预测器构成了特别大的挑战。在Java中，所有非static、非final的方法调用都是虚调用——即使在运行时只有一个实现类。这意味着Java程序中间接跳转的频率远高于C++程序。

以SPECjvm2008中的scimark.lu基准测试为例，虚函数调用约占所有分支指令的12%。在没有JIT优化的情况下，约40%的虚调用点是单态的，30%是少态的，30%是多态的。JIT编译器（如HotSpot C2）会对单态和少态调用点进行内联缓存（Inline Cache）优化——在调用点直接嵌入类型检查和目标地址，将间接跳转转换为条件直接跳转。经过JIT优化后，残留的间接跳转大多是多态调用点，对硬件间接目标预测器的压力反而更大。

这揭示了一个重要的软硬件协同效应：JIT编译器"吃掉"了容易预测的间接跳转，留下了硬预测的部分给硬件。因此，间接目标预测器的设计应该关注多态调用点的预测，而不仅仅是优化平均准确率。

switch-case与跳转表

编译器在处理大型switch-case语句（如超过8个case分支）时，通常会生成跳转表（jump table）。跳转表是一个地址数组，switch变量的值被用作数组索引，通过间接跳转跳到对应的case处理代码。

# switch(x)，x在a0中，0 <= x <= 7
  slli  t0, a0, 3        # t0 = x * 8（每个地址8字节）
  la    t1, jump_table    # t1 = 跳转表基地址
  add   t0, t1, t0        # t0 = &jump_table[x]
  ld    t0, 0(t0)         # t0 = jump_table[x]（目标地址）
  jalr  x0, t0, 0         # 间接跳转到目标

跳转表产生的间接跳转具有独特的预测特征：同一条jalr指令的目标地址取决于switch变量的运行时值，可能有多达数十个不同的目标。然而，跳转表的目标地址集合是固定的（由编译时确定），且switch变量的分布通常具有可利用的模式（如某些case比其他case更频繁）。ITTAGE可以利用历史信息来预测当前执行最可能的case——如果switch变量与之前几条分支的结果存在相关性，ITTAGE可以通过全局历史来区分不同的case。

间接跳转目标集合的利用

一个重要的优化思路是利用间接跳转的目标集合（target set）信息。对于跳转表实现的switch-case，所有可能的目标地址在编译时已经确定——它们就是跳转表中的条目。如果预测器知道一条间接跳转的可能目标集合，就可以将预测问题从“预测一个48位地址”简化为“在$K$个已知目标中选择一个”——后者只需要$\lceil\log_2 K\rceil$位的预测信息，存储和计算效率大幅提高。

这种优化的实现需要硬件能够学习间接跳转的目标集合。一种方法是在ITTAGE中为每条间接跳转维护一个目标集合表（Target Set Table）——当一条间接跳转被解析时，如果其实际目标不在目标集合表中，将其添加到表中。目标集合表的容量有限（如每条间接跳转最多记录8个目标），当容量已满时使用LRU替换。

预测时，ITTAGE的标签索引表存储的不再是完整的目标地址，而是目标集合表中的索引（3位可以索引8个目标），从而将每项的Target字段从48位压缩到3位——存储效率提高了16倍。

这种设计的局限性在于：（1）需要额外的目标集合表存储；（2）如果间接跳转的实际目标不在目标集合表中（新出现的目标），需要回退到使用BTB的默认预测；（3）对于多态虚函数调用（目标数量可能超过8个），目标集合表可能溢出。

解释器字节码分发的特殊优化

在解释器（如CPython、Lua、JVM解释模式）中，字节码分发循环是间接跳转预测的最大挑战之一。典型的字节码分发循环如下：

while (1) {
    opcode = *pc++;           // 读取字节码
    goto dispatch_table[opcode]; // 间接跳转到对应处理程序
}

这条goto编译为一条间接跳转指令，其目标地址取决于当前字节码的值。由于不同的字节码值可能有数十到数百种，且相邻两次分发之间的字节码值可能完全无关，传统的BTB（只记录上一次的目标）预测精度极低。

ITTAGE通过使用全局历史来关联相邻的字节码序列，可以显著提升分发循环的预测精度。直觉是：某些字节码序列是有规律的（如“LOAD, ADD, STORE”总是出现在一起），ITTAGE可以学习“在LOAD和ADD之后，下一个分发大概率跳转到STORE的处理程序”。历史长度越长，能够捕获的字节码序列模式越深，预测精度越高。

一种针对解释器的专门优化是threaded dispatch——将每个字节码处理程序的末尾直接跳转到下一个字节码的处理程序（而非回到分发循环的头部），使得每个字节码处理程序有独立的PC，从而在BTB和ITTAGE中形成独立的预测条目。这种优化在软件层面实现，但显著改善了硬件预测器的效果——不同字节码处理程序之间的间接跳转因为有不同的PC而在BTB/ITTAGE中不会相互干扰。

案例研究 5 — CPython 3.12的间接跳转优化

CPython 3.12引入了specialized adaptive interpreter，使用复制分发（copy dispatch）技术为每条字节码创建独立的分发代码副本。这使得每次字节码分发都来自一个唯一的PC地址，极大地改善了硬件间接跳转预测器的效果。

在Intel Golden Cove处理器上的测试表明，CPython 3.12的字节码分发间接跳转预测准确率从3.11版本的约60%提升到约80%——单纯通过软件层面的优化就实现了20个百分点的提升。这个案例深刻地说明了软硬件协同对分支预测性能的重要性。

案例研究 6 — Chrome V8引擎的虚函数预测分析

Google Chrome的V8 JavaScript引擎是研究间接跳转预测的绝佳案例，因为它同时包含了解释器分发（Ignition字节码解释器）和JIT编译代码（TurboFan/Maglev编译器）两种执行模式。

在Ignition解释器中，字节码分发循环是间接跳转最密集的场景。V8的优化策略是将分发表嵌入每个字节码处理程序的尾部（类似threaded dispatch），使每个处理程序拥有独立的PC。在Intel Golden Cove上的profiling数据表明：

• 解释器分发的间接跳转约占V8总分支指令的8%$\sim$12%。

• 使用ITTAGE后，分发循环的预测精度从BTB单独的$\sim$55%提升到$\sim$78%。

• 约80%的字节码分发site具有dominant target（概率$>$60%），BTB缓存dominant target效果良好。

• 剩余20%的多态分发site（如property access、method call）需要ITTAGE的长历史才能有效预测。

在TurboFan JIT编译的代码中，残留的间接跳转主要来自两个来源：（1）未被内联的虚函数调用（通常是多态度$>$4的callsite），（2）IC（Inline Cache）的fallback路径（类型检查失败时跳转到通用处理程序）。这些间接跳转的预测精度通常低于50%，是V8在CPU密集型基准（如Octane）上的主要性能瓶颈之一。

这一分析揭示了硬件间接目标预测器设计的一个重要启示：在现代JavaScript引擎中，“容易预测”的间接跳转已经被JIT编译器通过内联缓存和类型特化消除，留给硬件的是“最难预测”的子集。因此，ITTAGE等高级预测器的价值不在于提高平均准确率，而在于覆盖这些传统方法无法处理的“最后一英里”。

性能分析 5 — ITTAGE vs. 简单IBTB的MPKI对比

以SPEC CPU2017的xalancbmk（XML解析器，大量虚函数调用）为例，对比ITTAGE和简单IBTB在间接跳转目标预测上的精度差异。

步骤1：工作负载特征。xalancbmk的间接跳转频率约为每100条指令1.8条（不含ret），其中约65%来自虚函数调用，25%来自switch-case跳转表，10%来自函数指针调用。间接跳转的平均目标数约为3.2个不同目标/site。

步骤2：简单IBTB的性能。1024项IBTB，使用16位GHR参与索引。间接跳转MPKI约为4.2（每千条指令4.2次目标预测错误）。主要错误来源：（1）多态虚函数调用site目标频繁变化（贡献MPKI $\sim$2.5），（2）GHR长度不足以区分某些上下文（贡献MPKI $\sim$1.0），（3）IBTB容量不足导致的别名冲突（贡献MPKI $\sim$0.7）。

步骤3：ITTAGE的性能。6张表（历史长度4/8/16/32/64/128），总计4096项。间接跳转MPKI降至约1.8。改善来源：（1）多历史长度自动匹配不同site的需求——简单switch用短历史，解释器分发用长历史。（2）标签匹配消除了大部分别名冲突。（3）短历史表覆盖了单态/少态site，长历史表覆盖了多态site。

步骤4：IPC影响。每次间接跳转误预测的惩罚约为18周期。IBTB：$\Delta$CPI $= 0.018 \times 4.2 \times 18 / 1000 = 0.0014$（换算为IPC损失约3.4%）。ITTAGE：$\Delta$CPI $= 0.018 \times 1.8 \times 18 / 1000 = 0.0006$（换算为IPC损失约1.4%）。ITTAGE相比IBTB恢复了约2%的IPC。

步骤5：存储开销。简单IBTB：1024 $\times$ (12位Tag + 48位Target) = 7.5 KB。ITTAGE：4096 $\times$ (12位Tag + 24位紧凑Target + 2位useful) $\approx$ 19.5 KB。ITTAGE的存储开销约为IBTB的2.6$\times$，换取了2.3$\times$的MPKI改善和2%的IPC提升。在间接跳转密集的工作负载中，这一投资回报率是合理的。

返回地址预测

函数返回指令（如RISC-V的ret，即jalr x0, ra, 0）是一种特殊的间接跳转——其目标地址来自链接寄存器ra或栈中保存的返回地址。与一般间接跳转不同，函数返回的目标地址遵循严格的后进先出（LIFO）规律：最后调用的函数最先返回，返回地址恰好是最近一次call指令的下一条指令地址。

这一LIFO性质使得函数返回的目标地址可以通过一个硬件栈来高精度预测——这就是返回地址栈（Return Address Stack, RAS）。RAS是现代处理器中最古老也最有效的间接跳转预测机制之一，从1990年代起就被广泛采用。

返回地址栈的结构

RAS是一个硬件LIFO栈，由以下操作驱动：

• Push：当BTB识别到一条call指令时，将call的下一条指令地址（即返回地址）推入RAS栈顶。

• Pop：当BTB识别到一条ret指令时，从RAS栈顶弹出一个地址，作为预测的返回目标地址。

图图 16.5展示了RAS的基本结构和操作过程。

返回地址栈（RAS）的基本结构

RAS的关键设计参数是栈深度——即RAS能同时记录多少层嵌套调用。典型的RAS深度为16$\sim$64项：

• 16项：可以覆盖大多数普通程序的调用深度。在SPEC CPU工作负载中，95%以上的调用链深度不超过16层。

• 32$\sim$64项：覆盖递归调用和深层嵌套的场景。某些递归算法（如快速排序、树遍历）的调用深度可达数十层。

• 超过64项：边际收益极小。即使在最深的递归程序中，活跃的调用深度（从最内层到最外层的当前嵌套深度）也极少超过64层。

RAS的预测精度极高——在调用/返回严格配对的程序中，RAS的预测准确率可达97%$\sim$99%。这使得函数返回成为所有间接跳转类型中最容易预测的一种。

RAS的硬件实现

从硬件实现的角度看，RAS是一个带有TOS（Top-of-Stack）指针的寄存器文件。每一项存储一个完整的返回地址（48$\sim$64位虚拟地址）。TOS指针是一个$\lceil\log_2 N\rceil$位的计数器（$N$为RAS深度），支持递增（push）和递减（pop）操作。

以一个32项RAS为例，其硬件开销为：

• 存储阵列：$32 \times 48 = 1536$位$=$192 B

• TOS指针：5位寄存器

• 写端口：1个（push写入）

• 读端口：1个（pop读出）

• 总面积：约为一个128项BTB的1/10——RAS是分支预测中硬件性价比最高的组件

识别call和ret指令

RAS的正确工作依赖于BTB准确识别call和ret指令的类型。在BTB的Type字段中，call和ret各有独立的编码。BTB在取指阶段告诉取指单元"当前PC处有一条call指令"或"当前PC处有一条ret指令"，取指单元据此执行RAS的push或pop操作。

在RISC-V中，call和ret的识别稍有复杂性。RISC-V没有专门的call和ret指令——它们都是jal或jalr指令的特定使用模式：

• call：jal ra, offset或jalr ra, rs1, offset（目标寄存器为ra或x5）

• ret：jalr x0, ra, 0（目标寄存器为x0，源寄存器为ra）

RISC-V规范为此定义了明确的提示规则：如果jal或jalr的目标寄存器rd是x1或x5，该指令应被视为call（push RAS）；如果jalr的源寄存器rs1是x1或x5且rd不是x1或x5，该指令应被视为ret（pop RAS）。这些提示使得硬件可以在指令译码阶段之前（通过BTB的Type字段）正确驱动RAS操作。

RAS的推测操作

在超标量乱序处理器中，RAS的push和pop操作是在取指阶段——即推测性执行路径上——进行的。这意味着如果分支预测错误，取指阶段在错误路径上执行的call和ret指令会错误地修改RAS的状态（错误的push或pop），导致后续正确路径上的返回地址预测也出错。

推测push的问题

假设取指阶段在投机路径上遇到了一条call指令并将返回地址推入RAS。如果这条call指令所在的投机路径后来被发现是错误的（之前的一条条件分支被预测错了），那么RAS中多了一个不应存在的表项。此后正确路径上的ret指令将弹出这个错误的地址，导致连锁的预测失败。

推测pop的问题

类似地，如果取指阶段在投机路径上遇到了一条ret指令并从RAS弹出了一个地址，而该ret指令后来被取消（因为之前的分支预测错误），那么RAS丢失了一个本应保留的返回地址。此后正确路径上的ret指令将弹出错误的地址。

推测操作对RAS精度的影响是严重的。研究表明，在没有任何修复机制的情况下，推测错误导致的RAS污染可使返回地址预测准确率从99%降低到93%$\sim$95%——额外的4$\sim$6个百分点的预测失败，在深流水线处理器中对应显著的IPC损失。

推测损坏的具体示例

考虑以下执行序列来理解推测损坏如何发生。假设RAS当前状态为[A, B, C]（TOS指向A），其中A、B、C是三个返回地址：

（1）取指阶段遇到一条条件分支$br_1$，方向预测器预测为taken，取指跳转到目标地址。

（2）在目标地址处遇到一条call指令，取指阶段将返回地址D推入RAS。RAS变为[D, A, B, C]。

（3）继续取指，遇到ret指令，从RAS弹出D。RAS恢复为[A, B, C]。

（4）此时$br_1$被解析，发现方向预测错误——$br_1$实际上是not-taken。流水线刷新，从$br_1$的顺序后继地址重新取指。

在这个例子中，步骤(2)的push和步骤(3)的pop恰好"抵消"了——RAS状态没有净变化，因此不需要修复。但如果步骤(3)没有发生（即错误路径上只有call没有ret），RAS中就多了一个不应存在的D——后续所有ret指令的预测都会偏移一个位置，产生连锁错误。

解决推测操作问题的关键是RAS修复机制，将在16.5.4 节中详细讨论。

推测损坏的量化分析

推测损坏对RAS精度的影响取决于以下因素：

1. 方向预测器的精度。方向预测精度越高，进入错误路径的概率越低，RAS被推测损坏的概率也越低。以TAGE-SC-L的97%$\sim$98%精度为例，约2%$\sim$3%的分支会导致错误路径执行。

2. 错误路径上的call/ret密度。如果错误路径上恰好包含call或ret指令，就会推测性地修改RAS状态。对于典型的代码，约15%$\sim$20%的指令是分支指令，其中约5%是call，约5%是ret。在一个20周期的流水线中，错误路径上平均执行约100条指令（假设IPC=5），其中约5条是call、5条是ret。

3. call/ret的净偏差。如果错误路径上call和ret的数量相等，它们的push/pop在RAS上相互抵消，净影响为零。但如果不相等（如错误路径上只有call没有ret），RAS会发生“推移”。

一个简化的分析模型如下。设方向预测错误概率为$p_{\text{mis}}$，每次错误路径上call的期望净增量为$\Delta_{\text{call}}$（可以是正数或负数），则每条分支导致的RAS推移量的期望值为$p_{\text{mis}} \times \Delta_{\text{call}}$。对于$p_{\text{mis}} = 0.03$、$\Delta_{\text{call}} = 0.5$，每条分支的平均RAS推移为0.015——看似很小，但在1000条分支中累积的推移量为15，足以严重损坏RAS的所有表项。

这就是为什么即使方向预测精度很高（97%+），RAS仍然需要修复机制——少量的推测损坏通过累积效应会导致显著的精度下降。

推测修改的时序问题

RAS的推测push/pop操作发生在取指流水线的最早阶段（当BTB识别出call/ret指令时）。但RAS的恢复（当分支预测错误被检测到时）发生在执行阶段——两者之间有15$\sim$20个周期的延迟。在这段延迟期间，RAS可能已经被多次推测修改，恢复操作需要撤销所有这些修改。

一种优化是提前恢复（early recovery）：当L1预测器覆盖L0预测器时（见覆盖式预测），如果覆盖操作改变了取指方向，可以立即恢复RAS状态到覆盖点——而不需要等到执行阶段。这种提前恢复将RAS损坏的窗口从15$\sim$20个周期缩短到2$\sim$3个周期（L1覆盖延迟），显著降低了推测损坏的影响。

RAS溢出与损坏的处理

RAS的深度是有限的（通常16$\sim$64项），当调用链深度超过RAS容量时就会发生溢出（overflow）。此外，某些程序行为会损坏（corrupt）RAS的内容，导致call/ret不配对。

RAS溢出

当RAS已满时，新的call指令的push操作有两种处理方式：

（1）丢弃。简单地忽略push操作，不向RAS写入任何内容。这意味着最深层的返回地址被丢失——当执行最终到达这些深层返回时，RAS中没有对应的地址，预测失败。这种方式实现最简单但精度最差。

（2）环形覆盖（Wrap Around）。将RAS实现为环形缓冲区（circular buffer）——TOS指针到达栈底后回绕到栈顶，覆盖最旧的表项。这种方式下，最近的$N$个返回地址始终可用（$N$为RAS深度），只有最早（最外层）的返回地址被覆盖。由于程序的调用/返回模式通常是"深入后返回"——最内层的ret最先执行，被覆盖的最外层地址最后才会被用到——环形覆盖方案在大多数情况下不会造成预测失败。

对于递归函数来说，环形覆盖方案的行为需要特别关注。考虑一个递归深度为100的函数调用：前$N$个call的返回地址被推入RAS后，第$N+1$个call会覆盖最早（最外层）的返回地址。当递归开始返回时，最内层的$N$个ret可以正确预测（它们的返回地址在RAS中），但第$N+1$个ret开始就会预测错误（对应的返回地址已被覆盖）。对于一个32项的RAS和100层递归，约68%的返回指令将预测失败。幸运的是，如此深的递归在实际程序中极为罕见——SPEC CPU 2017中最深的递归调用链通常不超过30$\sim$40层。

RAS溢出的性能影响量化

RAS溢出的性能影响可以通过以下分析来量化。设程序的调用链深度分布为$P(d)$（$d$为调用链深度），RAS深度为$N$。当调用链深度$d > N$时，最深的$d - N$层返回地址将因RAS溢出而无法正确预测。

对于SPEC CPU 2017的典型分布：

• 约70%的调用链深度$\leq 8$。

• 约90%的调用链深度$\leq 16$。

• 约97%的调用链深度$\leq 32$。

• 约99%的调用链深度$\leq 48$。

因此，16项RAS可以覆盖90%的调用链，RAS溢出导致的预测错误率约为$10\% \times 20\% = 2\%$（10%的调用链溢出，其中约20%的溢出层返回会实际执行）。32项RAS将溢出率降低到约3%，对应的预测错误率约0.6%。64项RAS的溢出率不到1%，预测错误率可以忽略。

这一分析表明，从16项增加到32项RAS可以将RAS相关的预测错误率降低约70%——这是一个非常有效的投资（仅增加$16 \times 48 = 768$位$\approx 96$字节的存储）。但从32项增加到64项的额外收益就很小了。

环形缓冲区是现代处理器中最常用的RAS实现方式。其工作原理如下：

• RAS有$N$个存储项，TOS指针为一个$\lceil\log_2 N\rceil$位的计数器。

• push操作：TOS = (TOS + 1) mod $N$，将返回地址写入RAS[TOS]。

• pop操作：读取RAS[TOS]的值作为预测目标地址，TOS = (TOS $-$ 1) mod $N$。

• 当调用深度超过$N$时，新的push会覆盖RAS中最旧的表项。当对应的ret执行时，该项已被覆盖，预测错误。

call/ret不配对

在正常的结构化编程中，每个call都有一个对应的ret，RAS的push/pop自然配对。但某些代码模式会破坏这一配对关系：

（1）longjmp/setjmp。C语言的longjmp可以跨越多个函数栈帧直接返回到之前setjmp的位置，跳过了中间函数的ret指令。这使得RAS中积累了多个永远不会被pop的条目。

（2）异常处理。C++的异常抛出（throw）会展开（unwind）多个栈帧，跳过中间函数的ret指令。效果与longjmp类似。

（3）尾调用优化（Tail Call Optimization）。当一个函数的最后一个操作是调用另一个函数时，编译器可能将call+ret优化为一个简单的jmp（不保存返回地址）。这使得被调用函数的ret实际上返回到更外层的调用者。对于RAS来说，jmp不触发push，但最终的ret仍然触发pop——pop弹出的地址恰好是正确的（来自更早的call），因此尾调用优化通常不会破坏RAS的正确性。

（4）协程切换。协程（coroutine）的yield和resume操作可能不遵循传统的call/ret模式。

对于longjmp和异常处理造成的RAS损坏，简单的解决方案是在检测到分支预测错误或异常处理时清空RAS——丢弃所有可能受污染的条目，从零开始重建。这种方案虽然粗暴，但对于这些相对罕见的事件来说是可以接受的。

call/ret不配对的检测

处理器可以通过监控RAS的push/pop比率来检测call/ret不配对的情况。具体方法包括：

推测/架构TOS比较。维护一个架构TOS指针（只在指令退休时更新）和一个推测TOS指针（在预测时更新）。正常情况下，当所有飞行中的分支都已退休时，两个TOS应该指向相同的位置。如果架构TOS与推测TOS之间的偏差超过一个阈值（如$>4$），可能说明发生了严重的call/ret不配对，触发RAS的“软重置”——将推测TOS重置为架构TOS的值。

溢出计数器。维护一个计数器记录RAS的净push深度（push时+1，pop时$-$1）。当净深度超过RAS容量$N$时，最外层的返回地址已经被覆盖，后续对应的ret将预测错误。处理器可以利用这个信息来跳过RAS预测，改用ITTAGE或BTB进行预测。

RAS与尾调用优化的交互

尾调用优化（Tail Call Optimization, TCO）将函数末尾的“call + ret”序列替换为一个简单的“jmp”。从RAS的角度看，TCO的效果取决于编译器的具体实现：

• 如果TCO将call target; ret替换为jmp target：jmp不触发push，函数$B$最终返回时的ret会直接pop到调用者$A$的返回地址（而非中间的调用者$C$的返回地址）。这是正确的行为——$B$应该返回到$A$，因为$C$只是$A$和$B$之间的“中间人”。RAS在这种情况下工作正确。

• 如果TCO将call target替换为jmp target但不消除当前函数的ret（因为当前函数还有其他退出路径）：RAS中当前函数对应的条目保持不变，被调用函数的ret会正确返回。

总之，编译器正确实现的TCO通常不会破坏RAS的正确性。但如果编译器将jmp误标记为call（或BTB将jmp误识别为call），就会导致虚假的push操作，污染RAS。

RAS修复机制

RAS修复机制的目标是在分支预测错误被检测到后，将RAS恢复到预测错误发生前的正确状态。这是保证RAS在推测执行环境下高精度工作的关键。

Checkpoint方案

最直接的修复方案是检查点（checkpoint）：在每条条件分支指令被预测时，保存当前RAS的TOS指针值作为检查点。当该分支被解析为预测错误时，使用保存的检查点恢复TOS指针。

Checkpoint方案有两种实现粒度：

（1）TOS指针检查点。只保存TOS指针值（$\lceil\log_2 N\rceil$位），不保存RAS的数据内容。恢复时将TOS指针恢复到检查点值——如果错误路径上只有pop操作（没有push覆盖数据），那么数据仍然在RAS中，TOS指针恢复就足够了。但如果错误路径上有push操作覆盖了数据，则被覆盖的数据无法恢复。

TOS指针检查点的存储开销极小——每条分支指令只需保存一个6位（对于64项RAS）的TOS指针值。在一个128项的分支检查点表中，总共只需$128 \times 6 = 768$位$<$0.1 KB。

（2）完整RAS检查点。在每条分支指令处保存整个RAS的内容（所有$N$项$\times$每项48位）。恢复时用检查点数据覆盖整个RAS。这种方案保证了完美的恢复，但存储开销巨大——对于一个32项的RAS和128条分支检查点，需要$128 \times 32 \times 48 = 196608$位$=$24 KB。这在面积和功耗上都不可接受。

实际的高性能处理器通常采用TOS指针检查点加上一些额外的保护机制。

计数器方案

另一种轻量级的修复方案是影子计数器（shadow counter）方案。其思想是：为每条处于飞行中的（in-flight）分支指令维护一个call/ret计数器，记录从该分支指令到当前时刻之间执行了多少次push和pop操作。当分支预测错误时，根据计数器值逆向执行相应数量的push/pop操作来恢复RAS状态。

具体来说：

• 每条条件分支指令被预测时，记录当前的RAS push/pop净计数为0。

• 在该分支之后每执行一次push（call），计数器+1；每执行一次pop（ret），计数器$-$1。

• 当该分支被解析为预测错误时，如果计数器值为$+k$（多push了$k$次），则将TOS指针减$k$（撤销多余的push）；如果计数器值为$-k$（多pop了$k$次），则需要重新push $k$个被弹出的地址（但这些地址可能已经丢失）。

计数器方案可以正确处理错误路径上纯call或纯ret的情况，但对于错误路径上call和ret交替出现的情况，仅靠净计数器无法完美恢复——被覆盖的数据无法找回。

拷贝栈方案

拷贝栈（Copy Stack）方案结合了TOS检查点和数据保护的优点：

（1）RAS本体使用环形缓冲区实现。

（2）push操作将返回地址写入RAS的同时，也将被覆盖的旧数据保存到一个辅助的恢复缓冲区（Recovery Buffer）中。

（3）当需要恢复时，从恢复缓冲区中取回被覆盖的数据，写回RAS中对应的位置，并恢复TOS指针。

这种方案的存储开销介于TOS检查点和完整RAS检查点之间——恢复缓冲区只需存储被覆盖的数据（通常远少于完整RAS的数据量），且只在实际发生覆盖时才占用空间。

案例研究 7 — Intel和ARM处理器的RAS实现

Intel Golden Cove的RAS深度约为32$\sim$36项，采用TOS指针检查点配合环形缓冲区实现。每条分支指令在进入ROB时保存当前的TOS指针值。分支预测错误恢复时，将TOS指针恢复到检查点值。对于错误路径上push覆盖数据的情况，Golden Cove依赖"在大多数情况下错误路径很短、覆盖概率低"的统计特性来容忍偶尔的预测失败。

ARM Cortex-X4的RAS深度为52项，采用了更精细的拷贝栈机制来确保推测恢复的正确性。X4的RAS在每次push时记录被覆盖的旧数据，分支预测错误恢复时不仅恢复TOS指针，还恢复被覆盖的数据。这种方案的预测准确率接近完美RAS，但增加了约15%$\sim$20%的RAS硬件面积。

AMD Zen 4的RAS深度约为32项。Zen 4使用了一种称为"影子RAS"（Shadow RAS）的技术——维护两份RAS拷贝，一份由推测执行更新（推测RAS），一份只由退休的指令更新（架构RAS）。当分支预测错误需要恢复时，直接用架构RAS的状态覆盖推测RAS。这种方案的恢复延迟较长（需要等待架构RAS反映所有已退休指令的状态），但恢复的正确性有保证。代价是需要两份完整的RAS存储。

RAS的call/ret计数压缩

一种高级的RAS优化技术是call/ret计数压缩（Call/Return Counter Compression）。在某些递归程序中，同一个函数可能被递归调用数十次，每次调用都向RAS push相同的返回地址。如果RAS深度为32，而递归深度为50，RAS中大部分条目存储的都是同一个返回地址——这是极大的浪费。

计数压缩的思想是：当连续多次push相同的返回地址时，不分配新的RAS条目，而是递增当前栈顶条目的计数器。类似地，pop操作先递减计数器，只有当计数器归零时才真正移动TOS指针。

每个RAS条目的结构变为：

字段	位宽	说明
return_addr	48位	返回地址
count	6$\sim$8位	连续相同地址的push次数

使用计数压缩后，一个32项的RAS可以有效地支持$32 \times 2^8 = 8192$层的递归调用（假设8位计数器），远超任何实际程序的递归深度。对于非递归程序，计数器始终为1，计数压缩不产生任何开销也不提供任何收益。

计数压缩的检测逻辑只需在push时比较新的返回地址与当前栈顶的返回地址——如果相同则递增计数器，如果不同则分配新条目。这个比较操作可以与push操作并行进行，不增加关键路径延迟。

RAS修复机制的综合比较

表表 16.4总结了各种RAS修复机制的权衡。

方案	恢复精度	存储开销	恢复延迟	典型应用
TOS指针检查点	高（不完美）	极低	1周期	Intel Golden Cove
完整RAS检查点	完美	极高	1周期	学术研究
计数器方案	中等	低	1$\sim$2周期	早期处理器
拷贝栈	接近完美	中等	1$\sim$2周期	ARM Cortex-X4
影子RAS	完美	高（$2\times$）	多周期	AMD Zen 4

RAS修复机制的比较

TOS指针检查点的实现细节

TOS指针检查点是最常用的RAS修复方案。其实现涉及以下微架构细节：

检查点分配。每条分支指令在通过取指/预测阶段时，当前RAS的TOS指针值被记录到一个检查点寄存器中。检查点可以存储在以下位置之一：

• ROB的分支条目中。每个ROB条目留出$\lceil\log_2 N\rceil$位（$N$为RAS深度）用于保存TOS指针。这不需要单独的检查点存储，但增加了ROB每项的宽度。

• 独立的检查点表中。一个以分支序列号索引的小型表，每项存储一个TOS指针值。当分支退休时，释放其检查点表项。

恢复操作。当分支$B$在执行阶段被解析为预测错误时，RAS的恢复分为两个步骤：

1. 将TOS指针恢复到$B$的检查点值。

2. 如果$B$的实际方向需要对RAS进行操作（例如$B$实际上不是分支指令、或者$B$的类型与BTB记录的不同），执行正确的RAS操作。

恢复操作只需1个周期——将检查点值写入TOS寄存器。但恢复的正确性取决于错误路径上的push操作是否覆盖了RAS中的有效数据。如果错误路径上没有push操作（只有pop），则TOS恢复就足以完美恢复RAS状态——因为pop操作只移动了TOS指针，数据仍然在RAS中。但如果错误路径上有push操作覆盖了某个RAS项的数据，则恢复TOS指针后该项的数据是被覆盖后的新数据而非原始数据，导致后续pop读到错误的返回地址。

覆盖概率分析。设RAS深度为$N$，错误路径上执行了$k$次push操作。则被覆盖的RAS项数等于$\min(k, N)$。对于$N = 32$和$k$的期望值约为2$\sim$3（典型的错误路径上call指令数），被覆盖的概率约为$k/N \approx 6\%\sim 9\%$。也就是说，约90%以上的恢复操作可以通过TOS指针恢复完美完成，只有约10%的情况需要更精细的数据恢复。

在实际的处理器设计中，RAS修复机制的选择取决于以下因素：

• 分支预测错误率。如果方向预测器的精度足够高（如TAGE-SC-L达到99%以上），则推测路径导致的RAS损坏概率很低，简单的TOS指针检查点就已足够。

• 流水线深度。更深的流水线意味着错误路径上可能执行更多的call/ret，RAS损坏的程度更严重，需要更精确的修复机制。

• 面积和功耗预算。完美修复（完整检查点或影子RAS）的存储开销通常占RAS总面积的50%$\sim$100%。在面积受限的设计中（如移动端处理器），TOS指针检查点是更务实的选择。

设计提示

返回地址预测是分支预测中性价比最高的组件。一个简单的16$\sim$32项环形RAS配合TOS指针检查点，存储开销不到1 KB，就可以将函数返回的预测准确率提升到97%以上。相比之下，要将条件分支的预测准确率从95%提升到97%，可能需要将TAGE预测器的存储预算翻倍。因此，在有限的硬件预算下，RAS应该被优先实现和优化。

目标预测与安全性

分支目标预测机制在2018年Spectre漏洞披露后成为了安全研究的焦点。Spectre变体2（Branch Target Injection，BTI）利用了BTB的跨进程共享特性：攻击者在自己的进程中训练BTB，使得目标进程的某条间接跳转指令在BTB中命中攻击者注入的目标地址，从而将目标进程的推测执行引导到一个精心选择的"gadget"代码片段，通过侧信道泄露敏感数据。

攻击原理

BTB通常由所有进程和特权级共享——用户态和内核态的分支指令共存于同一个BTB中。攻击者可以执行大量精心构造的分支指令来"训练"BTB：使得某个特定的PC哈希值对应一个攻击者指定的目标地址。当内核在该PC处执行间接跳转时，BTB命中攻击者训练的表项，推测性地跳转到攻击者指定的gadget地址。虽然推测执行最终会被撤销（因为实际目标地址不是gadget），但推测执行过程中的内存访问已经在Cache中留下了痕迹——攻击者可以通过Cache侧信道（如Flush+Reload）推断出被访问的内存地址，从而泄露内核数据。

硬件缓解措施

针对BTB侧信道攻击，处理器厂商引入了多种硬件缓解措施：

• IBRS/STIBP（Intel）。间接分支限制推测（Indirect Branch Restricted Speculation）在特权级切换或进程切换时刷新或隔离BTB状态，防止低特权级训练的BTB表项影响高特权级的推测执行。

• BTB隔离。一些处理器在BTB表项中加入ASID（Address Space ID）或特权级标记，只有ASID和特权级完全匹配的表项才能命中。这种方案完全消除了跨进程/跨特权级的BTB污染，但增加了BTB每项的存储开销（需要额外的ASID和特权级位）。

• Retpoline（软件方案）。将间接跳转替换为一个"返回蹦床"（return trampoline）——先将目标地址push到RAS，然后通过ret指令跳转。由于ret使用RAS而非BTB，攻击者无法通过BTB注入控制RAS的内容。Retpoline的性能代价约为5%$\sim$10%（额外的指令和分支预测延迟）。

BTB安全性与性能之间的权衡是一个持续演进的课题。完全隔离BTB可以消除安全风险，但降低了BTB的有效容量（同一个Set中属于其他进程的表项无法被当前进程使用）。现代处理器通常在安全关键场景（如内核态）启用严格的BTB隔离，在用户态允许有限的共享以保持性能。

BHI与BTB安全性的最新进展

2022年披露的BHI（Branch History Injection）攻击进一步揭示了分支预测器的安全风险。BHI攻击不是直接向BTB注入恶意目标地址，而是通过精心构造的分支执行序列来操纵分支历史寄存器（BHR/GHR），使得受害者进程中的间接分支在ITTAGE等历史相关预测器中命中攻击者训练的表项。

BHI攻击的关键洞察是：即使BTB被ASID或特权级隔离（防止了直接的BTB毒化），攻击者仍然可以通过影响GHR/PHR来间接控制ITTAGE的预测结果——因为GHR/PHR是跨安全域共享的。

针对BHI的防御措施包括：

• BHR清空。在安全域切换时清空分支历史寄存器，防止一个安全域的历史影响另一个域的预测。代价是清空后的历史需要重新积累，导致短暂的精度下降。

• BHR隔离。为不同的安全域维护独立的GHR/PHR副本。切换安全域时同时切换GHR/PHR。这需要额外的寄存器存储（每个安全域一份GHR/PHR）和切换逻辑。

• eIBRS（Enhanced IBRS）。Intel在较新的处理器中引入了增强的IBRS机制，不仅隔离BTB表项，还隔离分支历史的影响，全面阻止跨安全域的分支预测注入。

RAS的安全性问题

RAS同样面临安全威胁。Spectre-RSB（Return Stack Buffer variant）攻击利用了RAS的跨安全域共享：攻击者通过执行大量的call指令来“填充”RAS，然后等待受害者进程执行ret指令——受害者的ret可能从RAS中读取攻击者push的返回地址，推测性地跳转到攻击者指定的gadget。

防御Spectre-RSB的方法包括：在安全域切换时使用RSB stuffing（Intel术语）——向RAS中push一系列指向安全区域的地址，覆盖攻击者可能注入的恶意地址。RSB stuffing需要执行$N$条call指令（$N$为RAS深度），代价约为$N$个周期，对于$N = 32$的RAS，这在每次安全域切换时增加约32个周期的开销。

目标预测的综合设计

本节综合前面各节的讨论，从系统设计的角度分析目标预测子系统的整体架构。

目标预测器的完整流水线

一个完整的目标预测子系统包含BTB、ITTAGE和RAS三个核心组件，它们在取指流水线中的交互如下：

1. BP0阶段。当前PC送入L1 BTB和ITTAGE的索引计算逻辑。L1 BTB查询并行启动。

2. BP0末/BP1初。L1 BTB返回结果：

   • 如果命中，获取分支类型和目标地址。如果类型为call，向RAS push返回地址。如果类型为ret，从RAS pop返回地址作为预测目标。如果类型为间接跳转，等待ITTAGE结果（需要多1个周期）。

   • 如果未命中，假设无分支，PC顺序递增。同时启动L2 BTB查询。

3. BP1阶段。方向预测器（TAGE）返回预测方向。如果L1 BTB命中条件分支：

   • TAGE预测taken：使用BTB提供的目标地址。

   • TAGE预测not-taken：使用PC+取指块大小作为下一个PC。

4. BP1末/BP2初。ITTAGE返回间接跳转的预测目标。如果L2 BTB命中（L1缺失时），发出覆盖信号。

5. BP2阶段。SC校正决策完成。最终预测地址确定，送入I-Cache。

各组件的存储预算分配

在一个高性能处理器核心中，目标预测子系统的总存储预算通常为80$\sim$150 KB。表表 16.5给出了一个典型的预算分配方案。

组件	容量	每项位数	存储（KB）
L1 BTB	128项, 全相联	40位	0.6
L2 BTB	8192项, 8路	40位（紧凑编码）	40.0
区域表	16项	36位	0.07
TAGE方向预测器	12张表	见第 15.0 章	38.0
SC（统计校正器）	6张表	6位/项	4.1
循环预测器	64项	56位	0.4
ITTAGE	5张表, 2048项/表	36位（紧凑目标）	36.0
RAS	32项	48位	0.2
FTQ	32项	160位	0.6
预测元数据/检查点	64项	200位	1.6
总计			$\approx$121.6

目标预测子系统的典型存储预算分配

从存储预算的分配可以看出：L2 BTB和TAGE方向预测器是最大的两个组件，合计占总预算的约65%。ITTAGE占约30%。RAS、循环预测器等辅助组件的存储开销极小（总计不到2%）。

这一分配反映了分支预测中的帕累托原则：大部分存储预算用于覆盖最常见的分支类型（条件直接分支——需要大BTB和TAGE），少量预算用于优化特殊的分支类型（间接跳转——ITTAGE，函数返回——RAS，循环——Loop Predictor）。

目标预测与安全性的系统设计

从系统安全的角度，现代处理器需要对目标预测子系统的所有组件实施安全隔离。表表 16.6总结了各组件面临的安全威胁和对应的防御措施。

组件	攻击变体	防御措施	性能代价
BTB	Spectre-v2/BTI	IBRS, BTB隔离	2%$\sim$5%
ITTAGE	BHI	BHR清空/隔离, eIBRS	1%$\sim$3%
RAS	Spectre-RSB	RSB stuffing	$<1\%$
方向预测器	Spectre-v1辅助	推测屏障	5%$\sim$10%

目标预测各组件的安全威胁与防御

安全防御的总性能代价约为5%$\sim$15%，主要来自推测屏障和BTB隔离的开销。在安全性要求较低的场景中（如嵌入式系统、单用户桌面），可以关闭部分或全部安全防御以获得最高性能。

本章小结

本章系统地讨论了分支目标地址预测的各种技术。BTB作为目标预测的核心结构，通过Cache式的PC索引查找来在取指阶段提供预测的目标地址。多级BTB通过层次化设计平衡了延迟和覆盖率的矛盾——小而快的L1 BTB保证关键路径上的1周期预测延迟，大容量的L2 BTB提供高覆盖率。紧凑编码技术（偏移量编码、区域编码、压缩Tag）使得有限面积下可以容纳更多的BTB项。

对于不同类型的分支指令，目标预测的策略各不相同：直接跳转的目标地址是确定的，BTB命中即正确；间接跳转需要上下文相关的预测，ITTAGE通过多长度历史索引实现了高精度的间接目标预测；函数返回遵循LIFO模式，硬件RAS以极低的存储开销实现了极高的预测精度。

表表 16.7总结了各类目标预测机制的关键特性。

分支类型	预测机制	典型精度	存储开销	关键挑战
条件直接分支	BTB	$>$99%（命中时）	中等	BTB容量不足
无条件直接跳转	BTB	100%（命中时）	中等	BTB缺失
间接跳转	IBTB/ITTAGE	85%$\sim$92%	大	多态调用点
函数返回	RAS	97%$\sim$99%	小	推测损坏与溢出

目标地址预测机制总结

目标地址预测与方向预测共同构成了完整的分支预测体系。从设计方法论的角度看，目标预测的优化应遵循以下优先级：首先确保RAS正确工作（实现简单、收益最高），然后增大BTB容量以提高直接跳转的覆盖率，最后投入ITTAGE等复杂机制来改善间接跳转预测。在安全性方面，BTB隔离和RAS保护已成为现代处理器的标准配置，在不牺牲过多性能的前提下抵御Spectre等推测执行攻击。

从工程实现的角度，本章的核心设计经验可以总结为以下几点：

设计提示

BTB设计的第一原则：BTB的时序优先于容量。一个128项但能在1周期内返回结果的L1 BTB，对前端性能的贡献远大于一个8192项但需要3个周期的大BTB。多级BTB架构是解决时序与容量矛盾的标准方法。

紧凑编码的投资回报率极高。从朴素的88位/项编码切换到区域编码的34位/项，可以在不增加任何面积的情况下将BTB容量扩大2.5倍。这等价于免费获得了2.5倍的BTB容量增长——在面积受限的设计中，紧凑编码应该被优先考虑。

RAS是最值得投资的组件。一个32项的RAS仅占不到200字节的存储，却可以将函数返回的预测精度提升到97%以上。相比之下，将ITTAGE的存储翻倍可能只将间接跳转的预测精度从88%提升到92%。在有限的硬件预算下，RAS应该被第一个实现和优化。

FTB是超标量前端的最优BTB组织。对于每周期处理一个取指块的超标量处理器，以取指块为粒度组织BTB（FTB风格）比以指令为粒度组织BTB更高效——它简化了预测器与取指单元的接口，减少了BTB的查询次数，并自然地支持了取指块中多条分支的处理。

设计权衡 2 — 目标预测子系统的面积与性能

考虑一个5 nm工艺下的高性能处理器核心（面积约7 mm$^2$），分析不同目标预测配置的面积开销和性能收益：

配置	L2 BTB	ITTAGE	面积(mm$^2$)	IPC提升
基线	2048项	无	0.015	—
中等	4096项	1024项	0.035	+3%$\sim$5%
高端	8192项	2048项	0.065	+5%$\sim$8%
极致	12288项	4096项	0.095	+6%$\sim$10%

从“极致”配置的面积（0.095 mm$^2$）来看，即使是最大配置也仅占核心总面积的1.4%，但提供了6%$\sim$10%的IPC提升。这表明，在高端处理器核心中，目标预测子系统的面积预算几乎不构成限制——限制性能的主要因素是算法精度和实现时序。

性能分析 6 — RAS在不同工作负载中的重要性

RAS的重要性因工作负载类型而异。函数调用密集的程序从RAS中获益最大：

工作负载	ret占比	RAS精度	无RAS MPKI	有RAS MPKI
编译器（gcc）	3.5%	98.5%	8.2	4.1
解释器（perl）	5.2%	97.8%	12.5	6.3
数据库（mysql）	4.1%	97.2%	9.8	5.5
科学计算（lbm）	0.8%	99.5%	2.1	1.9
多媒体（x264）	2.3%	98.9%	3.5	2.8

从上表可以看到，RAS对函数调用密集的工作负载（编译器、解释器、数据库）的MPKI改善超过40%，而对函数调用稀少的工作负载（科学计算）的影响很小（约10%）。这再次印证了RAS是分支预测中性价比最高的组件。

BTB与I-TLB的协同设计

BTB和I-TLB在取指流水线中紧邻工作，两者的协同设计可以带来额外的优化机会。

BTB预取驱动的I-TLB预热

当FTQ中的预测地址对应一个尚未在I-TLB中的页面时，取指单元会遇到I-TLB缺失——需要进行页表查找（Page Table Walk），延迟可达数百个周期。BTB的预测信息可以用来预热I-TLB：当BTB预测到一个跨页的跳转目标时，提前发出I-TLB的预取请求，将目标页面的映射关系加载到I-TLB中。

这种BTB驱动的I-TLB预取在代码足迹跨越大量页面的工作负载中特别有效。Google的数据中心分析表明，I-TLB缺失在某些服务器工作负载中贡献了约5%$\sim$10%的CPI损失——BTB驱动的I-TLB预取可以将这一损失降低约30%$\sim$50%。

统一地址空间的优化

在某些嵌入式处理器中，指令和数据共享同一个TLB（Unified TLB）。此时BTB的目标地址查找可以与Unified TLB的指令翻译共享硬件——BTB的目标地址翻译不需要额外的TLB端口。但在高性能处理器中，I-TLB和D-TLB通常是分离的（Split TLB），以避免端口竞争。

BTB与分支方向预测器的一致性

BTB和方向预测器（如TAGE）在设计上需要保持一致性——两者对同一条分支指令的判断不能产生逻辑矛盾。以下是几种可能的不一致场景：

BTB命中但方向预测器预测not-taken。对于条件分支，BTB命中只表示“这里有一条分支指令”，不代表它一定跳转。方向预测器的not-taken预测是合理的——取指单元忽略BTB提供的目标地址，继续顺序取指。

BTB缺失但方向预测器预测taken。这种情况在BTB容量不足时可能发生——一条频繁执行的分支指令因BTB容量限制被驱逐，但方向预测器中仍保留着其训练数据。此时方向预测器预测taken，但没有目标地址可用。解决方案是：等待解码阶段识别出该分支指令并计算其目标地址，然后重新填充BTB。在等待期间，取指单元按顺序取指，产生“解码级气泡”。

BTB类型与实际指令类型不匹配。如果BTB记录一条指令为“条件分支”，但实际上该地址的指令已经被修改为一条普通的ALU指令（自修改代码），BTB会错误地触发分支预测操作。这种不一致通过代码修改时的BTB清空（FENCE.I）来解决。

设计提示

BTB和方向预测器之间的一致性管理是前端设计中一个容易被忽视但重要的问题。关键原则是：BTB负责“是否存在分支”的判断，方向预测器负责“分支往哪里跳”的判断，两者各司其职。BTB缺失不应该阻止方向预测器的正常工作（TAGE仍然需要更新全局历史），方向预测器的结果也不应该影响BTB的更新策略（BTB记录所有执行过的分支，不论其方向预测是否正确）。

本章讨论了BTB、ITTAGE和RAS三个独立的目标预测组件。但在实际处理器中，这些组件必须与第 15.0 章中讨论的方向预测器（TAGE-SC-L）以及取指流水线紧密集成。下一章（第 17.0 章）将讨论前端流水线中分支预测器的整体组织和集成方式，包括预测宽度、取指目标队列（FTQ）、解耦前端等高级话题——这些是将BTB、方向预测器、RAS等组件整合为一个高效的预测系统所必须解决的工程问题。从第 14.0 章的基础方法到本章的目标预测，我们已经建立了分支预测器所有核心组件的独立设计知识；第 17.0 章将把它们融合为一个完整的系统。

回调线索。ITTAGE的几何级数历史长度方法论直接继承自第 15.0 章中TAGE的设计哲学——在对数空间中均匀覆盖不同的历史深度需求。BTB的多级组织（L1/L2 BTB）与第 14.0 章中讨论的多级预测流水线（快速预测+精确预测）遵循相同的层次化设计原则。本章的ITTAGE与BTB协同设计将在第 17.0 章的系统集成中以完整的预测流水线图示呈现——BTB提供第一级快速目标预测，ITTAGE在第二级覆盖多态间接跳转，两者通过FTQ解耦。