# 间接分支预测（Indirect Branch Prediction）—— 虚函数、函数指针、跳转表为什么可能比你想象的慢

> [branch-prediction.md](/concepts/microarch/branch-prediction.md) 讲的是**直接分支**（`jcc`）的方向预测——CPU 只需要猜"跳还是不跳"。本篇聚焦**间接分支**（`call *%rax` / `jmp *%rax`）：CPU 不仅要猜方向，还要猜一个**任意的目标地址**。虚函数调用慢不慢？函数指针有没有额外开销？switch 为什么有时用跳转表、有时用 if-else 链？这些问题的答案都藏在间接分支预测器里。

> 前置：建议先读 [branch-prediction.md](/concepts/microarch/branch-prediction.md) 建立"分支预测 + 投机执行"的基本框架（BTB / 方向预测 / 流水线 flush），本篇不再重复这些基础概念。

> 它是微架构演进链的"⑤分支预测+投机"环节的**间接分支专题**——整条链的总纲见 [cpu-microarch-overview.md](/concepts/microarch/cpu-microarch-overview.md)。

### 术语速查

全文高频出现的缩写和术语，首次遇到时可回查此表：

| 缩写 | 全称 | 中文 | 一句话 |
|------|------|------|--------|
| **BTB** | Branch Target Buffer | 分支目标缓冲 | 用指令地址查"上次跳去哪"，直接/间接分支都用 |
| **BHT** | Branch History Table | 分支历史表 | 记录每条分支"上次走没走"，管 jcc 方向预测 |
| **ITTAGE** | Indirect Target TAGE | 间接目标TAGE预测器 | **本文核心**：IP + 全局历史联合索引，预测 call\*/jmp\* 的目标地址 |
| **RSB** | Return Stack Buffer | 返回栈缓冲 | 硬件 LIFO 栈，call 压入返回地址 / ret 弹出，≈100% 命中 |
| **GHR** | Global History Register | 全局分支历史寄存器 | 记录最近 N 条分支的 taken/not-taken 序列，给 ITTAGE 提供"路径上下文" |
| **IP** | Instruction Pointer | 指令指针 | 当前指令地址（x86 上叫 RIP），BTB/ITTAGE 的索引键之一 |
| **PMU** | Performance Monitoring Unit | 性能监控单元 | CPU 内置计数器，perf 事件的硬件来源 |
| **ROB** | Reorder Buffer | 重排序缓冲 | 乱序执行核心，暂存"已执行但未退休"的指令 |

| 缩写 | 全称 | 中文 | 一句话 |
|------|------|------|--------|
| **PGO** | Profile-Guided Optimization | 面向剖析的优化 | 根据实际运行 profile 辅助编译器去虚拟化 |
| **LTO** | Link-Time Optimization | 链接时优化 | 跨编译单元优化，可发现更多去虚拟化机会 |
| **CRTP** | Curiously Recurring Template Pattern | 奇异递归模板模式 | C++ 编译期多态技法，用模板替代虚函数 |

| 缩写 | 全称 | 中文 | 一句话 |
|------|------|------|--------|
| **BTI** | Branch Target Injection | 分支目标注入 | Spectre v2 攻击手段：污染间接分支预测器 |
| **IBRS** | Indirect Branch Restricted Speculation | 间接分支受限投机 | Spectre v2 缓解：限制间接分支投机执行 |
| **STIBP** | Single Thread Indirect Branch Predictors | 单线程间接分支预测器 | Spectre v2 缓解：隔离不同超线程的间接分支预测 |

## 前置知识：直接分支 vs 间接分支

直接分支（`jcc`）和间接分支在硬件眼里是两类不同的问题：

| | 直接分支 (`jcc`) | 间接分支 (`call *`/`jmp *`) | 返回 (`ret`) |
|---|:---:|:---:|:---:|
| **典型指令** | `je` / `jne` / `jg` / `jle` | `call *%rax` / `jmp *(%rdi)` | `ret` |
| **C/C++ 对应** | `if` / `for` / `while` | 虚函数、函数指针、`switch` 跳转表 | 函数调用返回 |
| **目标地址** | 编码在指令里（立即数偏移） | **运行时从寄存器/内存取** | 栈顶 |
| **要猜什么** | 只猜方向 (taken/not-taken) | 方向 **+ 目标地址** | 只猜目标地址 |
| **负责部件** | 方向预测器 (BHT/TAGE) | **间接分支预测器 (ITTAGE)** | RSB |
| **perf 事件** | `branches` / `branch-misses` | `branch-loads` / `branch-load-misses` | — |
| **误预测惩罚** | ~15~20 拍 | **更重**：猜错地址还要冲刷流水线重新取指 | ~10 拍（RSB 命中率高） |

```plantuml
@startuml
top to bottom direction
skinparam shadowing false
title 三种分支的"跳转到哪里"难度对比

rectangle "直接分支 jcc" as DIR {
  rectangle "目标固定\n(编码在指令里)" as D1 #C8E6C9
  rectangle "只猜方向" as D2 #C8E6C9
}

rectangle "间接分支 call */jmp *" as IND {
  rectangle "目标由 reg/mem 决定\n(可能每次不同)" as I1 #FFCDD2
  rectangle "猜方向 + 猜哪个地址" as I2 #FFCDD2
}

rectangle "返回 ret" as RET {
  rectangle "目标来自调用时压栈的地址" as R1 #FFF9C4
  rectangle "用 RSB (硬件栈) 猜到" as R2 #FFF9C4
}

DIR -right-> IND : 难度升级
IND -right-> RET : 返回有专门的硬件辅助
@enduml
```

下面用一张序列图把三种分支在 CPU 前端流水线里的处理流程展开对比——同样是从 Fetch 开始，三种指令走过的路径差异巨大：

```plantuml
@startuml
skinparam shadowing false
title 三种分支在 CPU 前端流水线中的处理路径对比

participant "取指\nFetch" as Fetch
participant "解码\nDecode" as Decode
participant "分支预测器\nPredictor" as Pred
participant "BTB\n(分支目标缓冲)" as BTB #C8E6C9
participant "BHT\n(方向历史)" as BHT #C8E6C9
participant "ITTAGE\n(间接目标预测)" as ITTAGE #FFCDD2
participant "RSB\n(返回栈缓冲)" as RSB #BBDEFB

== 直接分支 jcc（最简单：目标地址在指令里，只猜方向） ==

Fetch -> Decode: je 0x401000
Decode -> Pred: IP=0x1000，这条 jcc 走不走？
Pred -> BTB: 查 BTB[0x1000]
BTB --> Pred: 上次目标=0x401000（从指令编码就能知道）
Pred -> BHT: 查方向历史
BHT --> Pred: 上次 Taken
Pred --> Fetch: 从 0x401000 取指（只多查一次 BTB）
note right of Pred #C8E6C9: **jcc：只猜方向**\n目标地址是硬编码的\nCPU 只需确认"走不走"

== 间接分支 call */jmp *（最复杂：要猜一个随机的目标地址） ==

Fetch -> Decode: call *%rax
Decode -> Pred: IP=0x2000，%rax 等于什么？
Pred -> BTB: 查 BTB[0x2000]
BTB --> Pred: 历史目标很多：A / B / C
Pred -[#FFCDD2]-> ITTAGE: ★ 关键差异：IP + 全局历史联合索引
ITTAGE -[#FFCDD2]-> Pred: 根据路径历史，这次大概率是 B
Pred --> Fetch: 预测目标=B，从 B 取指\n但要等 %rax 真正算出来才能验证
note right of Pred #FFCDD2: **call */jmp *：多一维**\nBTB 不够用，额外需要 ITTAGE\n用 IP + 全局历史联合索引\n猜错代价远大于直接分支

== 返回 ret（有专用硬件 RSB，最简单） ==

Fetch -> Decode: ret
Decode -> Pred: ret，目标在哪？
Pred -[#BBDEFB]-> RSB: Pop RSB（硬件 LIFO 栈）
RSB -[#BBDEFB]-> Pred: 返回地址=0x403000（call 时压入的）
Pred --> Fetch: 从 0x403000 取指
note right of Pred #BBDEFB: **ret：硬件辅助**\nRSB 是专用 LIFO 栈\ncall 压入 / ret 弹出\n只要栈完整，≈100% 命中

@enduml
```

**核心区别**：直接分支（`jcc`）的目标地址是**指令自带的立即数**——编译器把它硬编码在机器码里，BTB 只需确认"上次跳到哪里"，真正的预测任务是方向（走或不走）。而 `call *%rax` / `jmp *%rax` 的目标地址**完全来自寄存器或内存**——每次执行时 `%rax` 可能指向不同函数，BTB 只能记录"这条指令历史上去过哪些地址"，却无法从指令本身知道"这次是哪个"。所以 CPU 必须引入**ITTAGE（间接分支目标预测器）**，用 IP + 全局分支历史联合索引——本质上是在做"根据过去走到这里的路径模式，猜这次调的是哪个函数"。至于 `ret`，CPU 有专门的 RSB 硬件栈，`call` 时压入返回地址、`ret` 时弹出，是一个简单可靠的 LIFO 结构，几乎不需要"猜"。

> **一句话**：间接分支比直接分支多一个维度——不仅要猜"走不走这条路"，还要猜"这条路通到哪个地址"。直接分支查一张表（BHT），间接分支查两张表（BTB + ITTAGE），`ret` 最简单（RSB 是专用硬件栈）。这就是为什么虚函数和函数指针可能成为热点：目标地址猜不中。

## 一、间接分支的硬件：ITTAGE 多级目标预测器

### 1.1 BTB 管直接分支，间接分支预测器管 `call *` / `jmp *`

回顾 branch-prediction.md：**BTB**（Branch Target Buffer）用 IP（指令地址）索引，查到"这条 jcc 上次跳到了地址 A"——但这对间接分支不够用，因为**同一个 `call *%rax` 指令，`%rax` 可能指向五个不同的函数**。

现代 CPU 有**独立的间接分支预测器**（Intel 上叫 ITTAGE，AMD 上机制类似），专门处理"同一个 IP 有多个目标"的情况：

```plantuml
@startuml
skinparam shadowing false
title 间接分支预测器：用 IP + 全局历史 一起索引

rectangle "IP（指令地址）" as IP
rectangle "全局分支历史寄存器" as GHR
rectangle "ITTAGE 预测表多个不同长度的历史索引的多张表" as TAB
rectangle "预测结果：目标地址" as RES #C8E6C9

IP -down-> TAB : 这是哪条 call * 指令
GHR -down-> TAB : 前面走过什么路径到这里的
TAB -down-> RES : 输出最可能的目标地址

note right of GHR
  同一 IP + 不同历史
  可以映射到不同目标
  比如：从 A 调过来是 OpAdd
  从 B 调过来是 OpSub
end note
@enduml
```

**关键洞察**：ITTAGE 不仅看 IP，还看"全局分支历史"——即"走到这条 `call *%rax` 之前，经过了哪些分支"。这让它能区分**同一 IP 在不同调用上下文下的不同目标**。

### 1.2 单态 vs 多态 vs 巨态：预测器怎么学

对间接分支预测器来说，目标地址的数量和规律决定了准确率：

| 态 | 目标数 | 举例 | 预测器行为 | 开销 |
|---|:---:|------|---------|:---:|
| **单态** (monomorphic) | 1 | 90%+ 虚函数调用实际是同一种子类 | 第一次 miss 后学到，之后几乎零开销 | ~5% vs 直接调用 |
| **双态** (bimorphic) | 2 | 两种策略交替调用 | 学交替模式（类似两位计数器学 TNTN） | ~10% vs 直接调用 |
| **三态** | 3 | 三种实现轮转 | 可能学会（取决于预测表容量） | ~20% vs 直接调用 |
| **巨态** (megamorphic) | 4+ 随机 | 插件系统、回调注册表 | **无法学习，每次都是赌** | **50%+ vs 直接调用** |

```plantuml
@startuml
top to bottom direction
skinparam shadowing false
title 虚函数调用在汇编层面是什么

rectangle "C++ 源代码\n  ops[i]->compute(x);" as CPP

rectangle "实际执行的三步" as ASM {
  component "① 从对象指针取 vtable 地址\nmov (%rdi), %rax" as S1
  component "② 从 vtable 取函数指针\nmov 0x8(%rax), %rdx" as S2
  component "③ 间接调用\ncall *%rdx" as S3
}

CPP -down-> ASM

note right of ASM
  ★ 第三步的 call *%rdx\n就是间接分支\nCPU 必须预测 %rdx 的值
end note
@enduml
```

### 1.3 RSB：专门优化 `ret` 的硬件栈

`call` 时 CPU 把返回地址压入 RSB（Return Stack Buffer，一个 16~32 项的硬件栈），`ret` 时弹出预测。这是一个**专用的后进先出结构**，和 BTB / ITTAGE 完全独立。只要调用和返回正确配对（没有 `longjmp`、协程切换等破坏栈平衡的操作），RSB 预测准确率接近 100%。

但 Spectre v2 攻击者会故意用间接跳转让 RSB 溢出或被污染，这是另一回事——见第七节。

## 二、虚函数：OOP 的性能暗面

### 2.1 多态的内存布局：vptr 与 vtable

在讨论"虚函数为什么会变成间接分支"之前，先看清楚编译器在内存里到底放了哪些东西。C++ 的多态依赖两张表、一个指针、一条寻址链：

```plantuml
@startuml
top to bottom direction
skinparam shadowing false
title C++ 虚函数调用的内存布局与运行时寻址链

package "内存中的对象实例" as HEAP #E3F2FD {
  rectangle "class Derived 的一个对象" as OBJ {
    rectangle " **vptr** = 0x5000" as VPTR #FFF9C4
    rectangle " int  x = 42;" as F1
    rectangle " double y = 3.14;" as F2
  }
}

note right of VPTR #FFF9C4
  **vptr (virtual pointer)**
  编译器自动插入的隐藏成员
  位于对象头部 (offset 0)
  指向所属类的 vtable 首地址
end note

package "vtable (只读数据段 .rodata)" as RODATA #E8F5E9 {
  rectangle "vtable for Derived\n(地址 0x5000)" as VTABLE {
    rectangle " [0] &type_info for Derived" as V0 #C8E6C9
    rectangle " [1] &Derived::~Derived()" as V1 #C8E6C9
    rectangle " [2] &Derived::foo()" as V2 #FFCDD2
    rectangle " [3] &Derived::bar()" as V3 #C8E6C9
  }
}

note right of VTABLE #E8F5E9
  **vtable (virtual function table)**
  每个多态类编译后各有一张
  同一类的所有实例共享同一张 vtable
  槽位偏移在编译期确定
  (foo 固定在 [2] 号槽)
end note

package "代码段 (.text)" as CODE #FFF3E0 {
  rectangle "Derived::foo():\n  push rbp\n  ...\n  ret" as FOO_CODE #FFCDD2
  rectangle "Derived::bar():\n  ..." as BAR_CODE #C8E6C9
}

VPTR --> VTABLE : vptr 指向本类 vtable
V2 --> FOO_CODE : 函数指针指向实际代码
@enduml
```

**三张表/段，一条寻址链**：

| 层次 | 所在内存区域 | 内容 | 谁管 |
|------|------------|------|------|
| **对象实例** | 栈或堆 | 头部一个隐藏 `vptr` + 成员变量 | 每个对象一份 |
| **vtable** | 只读数据段 `.rodata` | 函数指针数组 `[&foo, &bar, ...]` | 每个类一张，所有实例共享 |
| **函数代码** | 代码段 `.text` | 实际的机器指令 | 全局唯一 |

运行时分发 `ptr->foo()` 的过程就是顺着这条链走三步：

| 步骤 | 汇编 | 在做什么 | 访存次数 |
|:---:|------|------|:---:|
| ① 取 vptr | `mov (%rdi), %rax` | 从对象首地址读出 vtable 地址 | 1 次 |
| ② 取函数指针 | `mov 0x10(%rax), %rdx` | vtable[2] → 拿到 foo 的入口地址 | 1 次 |
| ③ 间接调用 | `call *%rdx` | **跳转到 %rdx 指向的代码** | 0 次（只是跳转） |

**关键点**：

- 步骤①②是**确定性的**：编译器知道 `foo` 在 vtable 的第几个槽（比如 `[2]`），所以偏移 `0x10` 是编译期常量。这两步只是"顺着固定路径读两次内存"，没有分支。
- 步骤③才是**不确定性的来源**：`call *%rdx` 的 `%rdx` 值取决于**运行时的对象类型**。如果 `ptr` 实际指向 `Derived`，`%rdx` = `&Derived::foo`；如果指向 `AnotherDerived`，`%rdx` = `&AnotherDerived::foo`。CPU 必须预测 `%rdx` 会是什么——这就是间接分支预测要解决的问题。
- 注意 vtable 是**编译期静态生成**的，存放在只读段，不是运行时动态构造的。程序的"多态"就体现在：不同对象实例的 `vptr` 指向**不同的 vtable**，而 `call *vtable[2]` 这条指令是固定的——同一指令，不同目标。

> **多继承的情形**：如果 `Derived` 继承了多个基类，对象里会有**多个 vptr**（每个基类子对象一个），每个基类的 vtable 槽位对应的函数指针可能指向一个 **thunk**（调整 this 指针的小段代码），再跳转到真正的函数。但对 CPU 来说，最终都是 `call *%reg`，本质不变。本文以单继承为例，多继承的间接分支行为完全同理。

### 2.2 为什么是间接分支

虚函数调用的本质是**两次间接寻址 + 一次间接 call**：

```asm
; C++: base->foo()
; 
; 第一步：从对象取 vtable 指针
    mov    (%rdi), %rax          ; vtable_ptr = *this
; 第二步：从 vtable 取函数指针（偏移由编译器确定）  
    mov    0x10(%rax), %rdx      ; func_ptr = vtable_ptr[2]  (foo 在 vtable 的第三个槽位)
; 第三步：间接调用
    call   *%rdx                  ; ★ 间接分支！
```

大多数 OOP 代码中，虚函数调用是**单态的**——虽然语法上 `base->foo()` 可以指向任何子类，但运行时 90%+ 都是同一种类型。间接分支预测器学会"这个 IP 永远跳向同一个目标"后，`call *%rdx` 几乎和直接 `call` 一样快。

### 2.3 单态不慢，巨态才是瓶颈

```plantuml
@startuml
left to right direction
skinparam shadowing false
title 虚函数"态"的数量 vs 间接分支预测准确率

rectangle "单态\n(一种子类)" as M1 #C8E6C9
rectangle "双态\n(两种交替)" as M2 #C8E6C9
rectangle "三态\n(三种轮转)" as M3 #FFF9C4
rectangle "巨态\n(随机四种+)" as M4 #FFCDD2

M1 -right-> M2 : 预测准确率略降
M2 -right-> M3 : 预测器开始吃力
M3 -right-> M4 : 预测器抓瞎

note bottom of M1
  ~99% 准确率
  ~5% 开销
end note
note bottom of M4
  ~50% 准确率
  ~50%+ 开销
end note
@enduml
```

**日常 OOP 代码中绝大多数虚函数调用是单态的**——不必谈虚函数色变。但当你的设计走向插件系统、回调注册表、`std::function` 容器时，一个 `call *` 指令可能面对数十个目标，间接分支预测器就完全失效了。

## 三、函数指针：本质相同

```c
typedef int (*op_t)(int);
op_t ops[] = { add, sub, mul, shl };

for (int i = 0; i < N; i++)
    sum += ops[i](x);      // call *%rax —— 间接分支
```

函数指针 `call *%rax` 和虚函数 `call *(%rdx)` 在 CPU 眼里**完全一样**——都是间接分支，都走 ITTAGE 预测器。区别仅在前面的寻址方式（虚函数多了取 vtable 的步骤），但间接分支本身的开销相同。

> **结论**：函数指针的性能瓶颈**不是"指针本身"，而是间接分支预测**。一个始终指向同一函数的函数指针，和直接调用一样快；一个在四个函数间随机的函数指针，和巨态虚函数一样慢。

## 四、switch 跳转表：编译器帮你转成了间接跳转

### 4.1 编译器如何决定：跳转表 vs if-else 链

```c
switch (x) {
    case 0: f0(); break;
    case 1: f1(); break;
    case 2: f2(); break;
    case 3: f3(); break;
    case 4: f4(); break;
}
```

当 case 值**密集连续**时，编译器生成跳转表：

```asm
    ; x 在 %rax 中
    jmp    *.L4(,%rax,8)     ; ★ 间接跳转！jmp *disp(base, index, scale)
    
.L4:
    .quad  .L0               ; case 0 → 地址 0
    .quad  .L1               ; case 1 → 地址 1  
    .quad  .L2               ; case 2 → 地址 2
    .quad  .L3               ; case 3 → 地址 3
    .quad  .L4               ; case 4 → 地址 4
```

| case 特征 | 编译器选择 | 分支类型 | 分支预测 |
|----------|-----------|---------|---------|
| 密集连续值 (0,1,2,3,4) | **跳转表** `jmp *disp(,%rax,8)` | **间接跳转** | 走间接分支预测器 |
| 稀疏值 (1, 100, 500) | if-else 链 `cmp/je` | 直接分支 | 走方向预测器 |
| 少量值 (2~3 个) | if-else 链 | 直接分支 | 走方向预测器 |

### 4.2 跳转表的目标地址有特殊性

跳转表的目标地址与间接调用有微妙区别：

- **虚函数**：目标地址分散在各个子类的代码段，地址值相差可能很大
- **跳转表**：所有目标地址**连续排列在同一张表里**，地址值相近

现代间接分支预测器可能利用目标地址的连续性做预测，因此 switch 跳转表对随机 case 值的容忍度通常**好于**巨态虚函数。

## 五、去虚化：怎么让间接分支变成直接分支

目标是消除 `call *%reg`，变成 `call <fixed_addr>`——省掉间接分支预测这个环节。

### 5.1 手段一览

| 手段 | 原理 | 运行时开销 | 适用场景 |
|------|------|:---:|------|
| `final` 关键字 | 告诉编译器这个类不再被继承 → 直接 `call` | 零 | 叶子类 |
| CRTP | 编译期多态替代运行时多态 | 零 | 可模板化的接口 |
| PGO | 编译器根据热点数据，对单态虚函数投机去虚化：`if (vptr == &OpAdd::vtable) call OpAdd::compute; else call *vtable[2]` | 极低 | 有 profile 数据的构建 |
| `std::variant` + `visit` | 用 switch 跳转表替代虚函数表 | 低 | 有限类型集合 |
| 分支打散 | 把巨态分发拆成多层双态分发 | 低 | 目标多但有层次结构 |
| LTO (Link-Time Optimization) | 跨编译单元发现"这个虚函数实际只有一个实现" → 直接调用 | 零 | 整个程序构建 |
| 手写分派表 | 用显式的 switch/if-else 替代虚函数 | 零 | 热路径、已知类型全集 |

### 5.2 PGO 投机去虚化原理（最巧妙的方案）

```cpp
// 原始虚函数调用
obj->compute(x);

// PGO 优化后编译器生成
if (obj->_vptr == &OpAdd::vtable)        // 投机：先检查是不是单态
    OpAdd::compute(obj, x);              // 是 → 直接调用，零间接分支开销
else
    obj->_vptr[2](obj, x);               // 不是 → 走虚函数表（间接分支）
```

PGO 收集热点数据，发现 `obj->compute()` 在 99% 的情况下调用的是 `OpAdd::compute`，于是在调用前插入一个 vtable 指针比较——命中了走快速路径（直接 call），没命中走慢速路径（间接 call）。快速路径是直接分支（`cmp + jne`），比间接分支好预测得多。

### 5.3 什么时候需要去虚化

| 场景 | 决策 |
|------|------|
| 虚函数调用在非热路径上 | **不管**——不热就不用优化 |
| 热路径 + 单态（perf 显示 branch-load-misses 低） | **不管**——预测器已经学会了 |
| 热路径 + 巨态（perf 显示 branch-load-misses >10%） | **动手**——按上表选择合适的手段 |
| 模板化接口可行 | **CRTP**——零开销，最彻底的方案 |
| 有限类型集合 | **`std::variant` + `visit`**——无需继承，语义清晰 |

> **口诀**：先 `perf stat -e branch-loads,branch-load-misses`，单态不管，巨态去虚化。

## 六、间接分支误预测的代价

间接分支猜错的惩罚比直接分支**更重**：

| | 直接分支 (jcc) 误预测 | 间接分支误预测 |
|---|:---:|:---:|
| 猜错什么 | 方向 | 目标地址 |
| 后果 | 从错误方向取指 → 重定向 | 从**完全不相关的地址**取指 → 重定向 |
| I-cache 影响 | 可能命中（相邻代码） | **几乎必 miss**（跳到了完全不相干的地方） |
| iTLB 影响 | 通常同页 | **高概率换页 → iTLB miss** |
| 惩罚 | ~15~20 拍 | **~20~30 拍**（连锁 I-cache miss + iTLB miss） |

```plantuml
@startuml
top to bottom direction
skinparam shadowing false
title 间接分支误预测的链式惩罚

(*) --> "间接分支猜错目标地址" as MISS
MISS --> "重定向到完全不相干的代码段"
--> "那条代码大概率不在 I-cache" as ICACHE
ICACHE --> "L1-icache-load-miss ↑\n→ 从 L2/L3 取指令"
--> "I-cache miss 期间流水线空转"

MISS --> "新地址可能在不同页" as ITLB
ITLB --> "iTLB-load-miss ↑\n→ page walk (4 次内存访问)"
--> "iTLB miss 期间流水线空转"

ICACHE --> "最终惩罚: 20~30 拍"
ITLB --> "最终惩罚: 20~30 拍"

@enduml
```

**这就是为什么巨态虚函数慢得那么明显**：不仅间接分支预测器猜不中目标地址，猜错后还要付 I-cache miss + iTLB miss 的连锁账单。

## 七、Spectre v2 (BTI)：间接分支的安全暗面

[branch-prediction.md](/concepts/microarch/branch-prediction.md) 第七节讲了 **Spectre v1**（边界检查绕过，利用 jcc 方向预测的投机执行）。**Spectre v2**（Branch Target Injection，BTI）攻击的是**间接分支预测器**：

- 攻击者训练间接分支预测器，让 `call *%rax` 或 `jmp *%rax` 在投机执行时跳转到攻击者选择的**gadget**（如 `speculation gadget`）
- 这个 gadget 在投机窗口内泄露数据到缓存 → 侧信道读出

**缓解手段**：

| 手段 | 原理 | 性能代价 |
|------|------|:---:|
| **retpoline** | 把 `call *%rax` 改写成 `call retpoline_thunk; ... retpoline_thunk: call .L1; .L1: pause; lfence; jmp .L2; .L2: mov %rax, (%rsp); ret` —— 用 `ret`（RSB 预测）代替间接 call（ITTAGE 预测），因为 RSB 不被 Spectre v2 污染 | 中 |
| **IBRS** (Indirect Branch Restricted Speculation) | 内核态设置 MSR 标志，限制间接分支的投机行为 | 中~高 |
| **STIBP** (Single Thread Indirect Branch Predictors) | 防止超线程间共享间接分支预测器状态 | 低~中 |
| **eIBRS** (Enhanced IBRS) | 硬件辅助的 IBRS，性能代价更低 | 低 |

> retpoline 是最著名的手段：它把间接分支预测交给了 RSB（返回栈），而 RSB 是一个硬件栈（不是通过历史学习），不受 Spectre v2 训练攻击的影响。代价是每次间接调用多几条指令。

## 八、怎么观测

### 8.1 直接看间接分支预测

```bash
# 间接分支总数 vs 误预测数
perf stat -e branch-loads,branch-load-misses ./app

# 同时看直接和间接分支
perf stat -e cycles,instructions,\
branch-instructions,branch-misses,\
branch-loads,branch-load-misses ./app
```

**注意 PMU 事件的两组对应关系**：

| PMU 事件 | 统计对象 | 含义 |
|---------|---------|------|
| `branch-instructions` | 直接分支 (jcc) | 条件/无条件直接跳转总数 |
| `branch-misses` | 直接分支 (jcc) | 直接分支预测失败数 |
| `branch-loads` | **间接分支** (call\*/jmp\*) | 间接调用/跳转总数 |
| `branch-load-misses` | **间接分支** (call\*/jmp\*) | **间接分支预测失败数** |

### 8.2 诊断流程

```plantuml
@startuml
skinparam shadowing false
skinparam activity {
  BackgroundColor #E3F2FD
  BorderColor #1976D2
  DiamondBackgroundColor #FFF9C4
  DiamondBorderColor #F9A825
}

start
:perf stat -e branch-loads,branch-load-misses ./app;

if (branch-loads > 0?) then (有间接分支)
  if (branch-load-misses / branch-loads > 5%?) then (高失败率)
    :perf record -e branch-load-misses:pp -g ./app\nperf report → 定位具体函数;
    
    if (是虚函数?) then (是)
      if (目标数 1~2 个?) then (单/双态)
        :预测器应能学会，检查是否alias冲突\n考虑调整虚函数表布局;
      else (巨态)
        :**去虚化**：final / CRTP / PGO / variant;
      endif
    elseif (是 switch 跳转表?) then (是)
      if (case 值可排序/分组?) then (是)
        :预排序数据让 case 值连续;
      else (否)
        :考虑手动 if-else 链（少量 case）;
      endif
    else (函数指针)
      :同虚函数处理;
    endif
  else (低失败率)
    :间接分支预测正常，开销可忽略;
  endif
else (无间接分支)
  :程序没有虚函数/函数指针/跳转表;
endif

stop
@enduml
```

### 8.3 perf 命令速查

| 我想知道... | 用这个 |
|------------|--------|
| 间接分支预测失败率 | `perf stat -e branch-loads,branch-load-misses ./app` |
| 哪个函数在间接 miss | `perf record -e branch-load-misses:pp -g ./app && perf report` |
| 哪条 call* 指令在 miss | `perf annotate`（在 report 中进入热点函数后） |
| 间接 + 直接分支一起看 | `perf stat -e branches,branch-misses,branch-loads,branch-load-misses ./app` |
| 间接miss 是否连带 I-cache miss | `perf stat -e branch-load-misses,L1-icache-load-misses,iTLB-load-misses ./app` |

> **实验代码**：[indirect-branch demo](/demos/indirect-branch/main.cpp)——对比直接调用 vs 单态/双态/巨态虚函数、函数指针、switch 跳转表的间接分支预测行为。`make perf-branch-loads` 直接看数据。

## 九、和本仓库其他文档的关系

- **前置**：[branch-prediction.md](/concepts/microarch/branch-prediction.md)——直接分支预测（jcc 方向预测），BTB/BHT/TAGE/两位计数器的基础概念，流水线 flush 机制。本篇是它的**间接分支专题深入**。
- **同层微架构**：[cpu-out-of-order.md](/concepts/microarch/cpu-out-of-order.md)——乱序执行 + 投机执行机制；[rob.md](/concepts/microarch/rob.md)——ROB 清空时的具体行为；[uop-pipeline-walkthrough.md](/concepts/microarch/uop-pipeline-walkthrough.md)——µop 级流水线走读。
- **观测**：[../code/perf.md](/tools/code/perf.md)——`branch-loads` / `branch-load-misses` 等 PMU 事件详解。
- **实验**：[indirect-branch demo](/demos/indirect-branch/README.md)——六种场景可跑对比。

## 十、一句话总结

> **间接分支（`call *%rax` / `jmp *%rax`）比直接分支（`jcc`）多一个维度——不仅要猜"跳不跳"，还要猜一个任意的目标地址。单态/少态时间接分支预测器（ITTAGE）学会目标后几乎零开销（日常 OOP 虚函数就是这样，不用谈虚函数色变）；巨态（四个以上目标随机）时预测器完全抓瞎，误判率 50%+，还连累 I-cache 和 iTLB 一起 miss，惩罚比直接分支误预测更重（20~30 拍 vs 15~20 拍）。优化手段是去虚化（final / CRTP / PGO / variant），但前提是先用 `perf stat -e branch-loads,branch-load-misses` 确认瓶颈确实在这里。Spectre v2 专门攻击间接分支预测器，retpoline 的缓解方案正是用 RSB（返回栈）替代 ITTAGE——侧面印证了"间接分支预测是个更难的问题"。**