全局历史、折叠历史与恢复

历史管理是分支预测器最容易“平时正确、redirect 时偶发错误”的部分。历史既参与表索引，又在每次推测分支后变化，因此必须支持高速更新和精确恢复。

三种表示

先给结论：这里的“三种表示”不是三条可以各自随意更新的历史，而是同一串分支结果的三个层次：

表示	回答的问题	保存的信息	是否无损	主要用途
逻辑历史	“最近的分支依次是 taken 还是 not-taken？”	按新旧次序排列的完整历史位	是	定义正确语义、写 reference model
环形历史缓冲	“完整历史在硬件寄存器中怎样低成本保存？”	历史位数组 ghv + 指向逻辑边界的 CGHPtr	是	BPU 中实际保存和恢复长历史
折叠历史	“怎样快速得到 TAGE 所需的短索引/tag 输入？”	长历史经过 XOR 折叠后的短摘要	否	缩短索引关键路径

它们之间的关系是：

分支结果序列（语义）
        │
        ▼
ghv + CGHPtr（完整、可恢复的物理状态）
        │  旋转读取 getHist(ptr)
        ├──────────────────────────► 逻辑历史向量
        │
        └── 增量 XOR 压缩 ─────────► 多组 FoldedHistory
                                      （供不同 TAGE 表使用）

因此，恢复时首先要恢复的是历史的边界，也就是 CGHPtr 及预测器仍需使用的历史位；折叠历史必须与它重新保持一致。环形缓冲能保住这些旧位，依赖后文解释的容量条件。只保存折叠历史不能恢复完整历史，因为 XOR 压缩存在碰撞。

逻辑历史

逻辑历史是最适合人思考的形式。把最近若干个条件分支的结果排成位串，并约定 bit 0 是最新结果：

较老                                      较新
 ...  H[5]  H[4]  H[3]  H[2]  H[1]  H[0]
                                            ▲
                                         最新分支

源码中的 ShiftingGlobalHistory.predHist 描述了这种语义。加入 shift 个新分支后：

newHist = (oldHist << shift) | taken

这行代码容易误读。一次预测块里可以经过多个条件分支，但第一个 taken 分支之后的指令不会再沿当前顺序路径执行。因此：

• shift 是本块真正经过并应写入历史的分支数；
• 若这些分支全为 not-taken，新加入的低 shift 位全是 0；
• 若遇到 taken，它一定是此次推进中最后一个经过的分支，所以最低位写 1，此前经过的分支写 0。

例如，假设历史宽度仅为 6，旧历史为 101100。当前块先经过一个 not-taken，再遇到一个 taken，则 shift=2：

old              = 101100
(old << 2)       = 110000   // 只保留 6 位
写入 [N, T] = 01
new              = 110001

逻辑历史是规范语义，很适合作为软件 reference model；但若历史有数百位，每拍真的做宽移位，布线和时序代价都很高。当前 BPU.scala 的长期状态并不是靠这个类整体移位保存，而是使用下面的环形结构。

环形历史缓冲

环形表示改变的是存放方法，不改变历史的内容。BPU.scala 中：

• ghv 是固定不移动的 HistoryLength 位寄存器数组；
• CGHPtr 记录当前历史的逻辑边界；
• 加入若干结果时，只在指针附近写少数几个位置并移动指针，而不是搬动整个 ghv；
• 指针绕回时，flag 用来保持环形指针的完整年龄语义。

可以把它想成一圈带编号的格子：格子不动，表示“最新位置在哪里”的指针在动。

物理格子:  [0] [1] [2] [3] [4] [5] [6] [7]
                       ▲
                     CGHPtr

写入两个新结果：只改相邻两个格子，并把边界移动两格；
不会把其余六个历史位整体平移。

物理数组从地址 0 开始排列，并不等于逻辑上的“从旧到新”。需要完整逻辑历史时，getHist 把数组复制两份、按指针旋转，再截取一段：

def getHist(ptr: CGHPtr): UInt =
  (Cat(ghv_wire.asUInt, ghv_wire.asUInt) >> (ptr.value + 1.U))
    (HistoryLength - 1, 0)

复制两份是处理绕回的常用技巧：无论逻辑窗口是否跨过数组末端，它在双倍数组中总能变成一段连续切片。

在尚未被覆盖的有效历史窗口内，环形历史与逻辑历史的关系是：

getHist(CGHPtr) == 按“最新到最老”规范排列的逻辑历史

在这个窗口内，两者信息量相同，可以互相解释；区别只在于逻辑历史便于推理，环形历史便于硬件更新。getHist 虽然返回整整 HistoryLength 位，但这不表示其中每一位都有效、或都会参与预测。

为什么最长只用 119 位，却保存 256 位

这两个长度回答不同的问题：119 位是当前预测表要看的最长历史；256 位是允许前端继续推测、同时保住旧检查点历史的环形缓冲容量。 Parameters.scala 中的配置是：

val HistoryLength = allHistLens.max + numBr * FtqSize + 9
// 当前配置：119 + 2 × 64 + 9 = 256

allHistLens.max=119 来自当前 TAGE 等预测表的历史长度；numBr=2 表示每个预测块最多加入两个分支结果，FtqSize=64 是 FTQ 项数。因此 2×64=128 是按 FTQ 容量估算的在途历史位上界。再加的 9 是实现留下的额外容量余量；源码在这条公式旁没有把 9 逐项分解成哪些流水线写入，不要把它说成已经逐级证明过的固定拍数。

为什么需要这 137 位？假设最老的有效 FTQ 检查点仍要读取其之前的 119 位历史，前端却已从该检查点继续写入最多 137 个推测结果。环上必须同时容纳这两段：

仍需恢复的旧历史 119 位 │ 检查点之后最多写入 128 + 9 位
                       └────────── 物理 ghv 共 256 位 ──────────┘

否则写指针绕回时，可能先覆盖检查点需要的旧位。这里真正的安全条件是：在最老的有效检查点被消费或撤销前，从它出发的写入距离不能超过 256−119=137 位。64×2 解释了主要预算，剩余 9 位须覆盖 FTQ 之外尚在预测流水线中的推进等额外情况。单看容量公式不能证明所有边界时序都满足这个条件；若要严格验证，应把“最老有效检查点到写指针的距离 ≤137”及满队列背压行为列为断言或专项测试。

读取时，getHist(ptr) 为统一接口把环形数组复制两份、旋转，然后返回 256 位；这只是逻辑视图的宽度，不是说预测器真的使用 256 位。各预测表按自己的 histLen 取前若干位并折叠，当前最长取 119 位。高位可能包含旧的错误路径残留，不能把完整 256 位都当成有效历史。这也说明：读接口理论上可以缩窄，但不等于物理环形缓冲也能缩到 119 位。

折叠历史

折叠历史既不是完整历史的另一种存储布局，也不是可用于恢复的压缩文件；它是从完整历史计算出的短摘要缓存。

例如某张 TAGE 表可能使用 128 位历史，但表索引只有 10 位。概念上可以把相隔 10 位的历史位 XOR 到同一列：

128 位逻辑历史
   ├── 第 0、10、20、... 位 ── XOR ─► folded[0]
   ├── 第 1、11、21、... 位 ── XOR ─► folded[1]
   └── ...
                                      得到 10 位摘要

实际 FoldedHistory 还会结合循环位置处理，不应把上图当成逐行源码公式；它表达的是核心思想：许多长历史位汇聚到少量折叠位。

不同 TAGE 表使用不同历史长度和压缩宽度，因此硬件同时维护的是多组 (histLen, compLen) 折叠值，而不是唯一一个 folded history。每组值用于相应表的 index 或 tag 计算。

FoldedHistory.update 到底怎样更新

先从折叠值的定义出发。假设使用的历史长度为 L，压缩宽度为 C。可以把完整历史切成若干个宽度为 C 的小段，再把这些小段按位 XOR：

F[j] = H[j] XOR H[j+C] XOR H[j+2C] XOR ...

其中：

• H[0] 是最新历史位；
• H[L-1] 是这个长度为 L 的窗口中最老的历史位；
• F 是宽度为 C 的 folded history。

当历史一次推进 n 位时，新的窗口等价于：

旧窗口移走最老的 n 位
       +
在最新端加入 n 个新位

最直观但很慢的做法，是先产生新的 H，再把全部 L 位重新 XOR。昆明湖采用增量算法，只修改短短的 C 位摘要。源码中的顺序是：

1. 从旧折叠值 folded_hist 开始；
2. XOR 掉这次离开窗口的 n 个 oldest bits；
3. XOR 进这次加入窗口的 n 个 newest bits；
4. 将结果循环左移 n 位，使所有仍留在窗口中的历史位到达新位置。

严格对应实现时，离开位有两种消除方式：曾经绕回并与其他段 XOR 在一起的位，通过 oldest_bits_set 再 XOR 一次来抵消；没有绕回的边界位，则由 original_bits_masked 在移位前直接屏蔽。两者在语义上都是“从折叠窗口删除 oldest bit”。

对应 FoldedHistory.update(ob, num, taken) 中的变量：

源码变量	含义
num	本次历史推进的位数 n
ob(i)	第 i 个将离开窗口的 oldest bit，即旧历史的 H[L-1-i]
oldest_bit_pos_in_folded(i)	该 oldest bit 原来贡献到哪个折叠位：(L-1-i) % C
newest_bits_masked	本次加入的 n 个新历史位
xored	旧摘要 XOR 离开位 XOR 加入位后的中间结果
circular_shift_left(xored, num)	产生最终的新折叠值

这里的“XOR 掉”并不需要减法：同一个 bit 再 XOR 一次就会抵消，因为 x XOR x = 0。

为什么源码只有一个 taken，却能一次加入 n 位？因为一个顺序取指块在第一个 taken 分支处就离开当前路径。本次加入的历史只能是：

[N, N, ..., N]       // 没有 taken
或
[N, N, ..., T]       // 最后一个经过的分支 taken

所以新增的 n 位最多只有一位为 1。源码把这个 1 放在推进前中间向量的 C-1-(n-1) 位置，经过最后的循环左移后，它到达新历史的 H[0] 所对应的折叠位置。

手算例子：8 位历史折成 4 位

设：

L = 8
C = 4
旧逻辑历史 H[7:0] = 10110110

先从完整历史重新计算一次旧折叠值：

F[3] = H[3] XOR H[7] = 0 XOR 1 = 1
F[2] = H[2] XOR H[6] = 1 XOR 0 = 1
F[1] = H[1] XOR H[5] = 1 XOR 1 = 0
F[0] = H[0] XOR H[4] = 0 XOR 1 = 1

所以旧 F[3:0] = 1101

现在当前预测块经过 [N, T]，因此 num=2、taken=1。完整逻辑历史会变成：

H' = (10110110 << 2) | 01
   = 11011001

增量折叠不重新扫描这 8 位，而执行下面四步：

① 旧折叠值                              1101

② 移出的最老两位是 H[7]=1、H[6]=0
   H[7] 原来贡献到 F[3]，再 XOR 一次： 0101
   H[6] 原来贡献到 F[2]，但它是 0：    0101

③ 加入 [N,T]；有效的 1 在旋转前放到 bit 2
   0101 XOR 0100 =                       0001

④ 循环左移 num=2
   ROL4(0001, 2) =                       0100

再用新完整历史 H'=11011001 从头验证：

F'[3] = H'[3] XOR H'[7] = 1 XOR 1 = 0
F'[2] = H'[2] XOR H'[6] = 0 XOR 1 = 1
F'[1] = H'[1] XOR H'[5] = 0 XOR 0 = 0
F'[0] = H'[0] XOR H'[4] = 1 XOR 1 = 0

F'[3:0] = 0100

它与增量算法得到的 0100 完全一致。增量更新只操作 C=4 位以及本拍进出的少数历史位，而不必重新读取和 XOR 全部 L=8 位。真实设计中 L 可远大于 C，节省会更加明显。

源码还处理了两个边界情况：

• 当 L <= C、历史短到不会发生多段折叠时，直接使用 ((folded_hist << num) | taken)；
• 当一次推进多个分支时，AllAheadFoldedHistoryOldestBits 预读多组可能离开的位，等 num 确定后选择正确一组，避免在关键路径上临时访问长 ghv。

这样，更新成本主要随 C 和每拍最大分支数增长，而不是随完整历史长度 L 增长。

折叠是有损的。例如两段不同的长历史可能得到同一个 10 位值，这就是 alias。因此：

• 它可以帮助快速查 TAGE；
• 它不能判断两段完整历史一定相同；
• 它不能单独用来恢复 redirect 前的历史；
• 恢复后的折叠值必须与恢复后的 ghv + CGHPtr 对应。

用同一个例子串起三者

假设当前逻辑历史为 101100，本块实际经过 [N, T]：

步骤	逻辑表示	环形表示	折叠表示
更新前	101100	ghv 中保存相同 6 位，指针指出边界	保存该历史的短 XOR 摘要
加入 [N,T]	语义上左移 2 位并写入 01	在指针附近写 0、1，指针移动 2 格	加入新位，同时 XOR 掉窗口移出的旧位
更新后	110001	getHist(newPtr) 必须读出 110001	得到 110001 对应的新摘要
误预测恢复	回到旧快照，再写真实结果	恢复旧指针/历史边界并覆盖错误路径位	从恢复状态重新得到一致的折叠值

最重要的不变量不是三者寄存器逐位相等，而是：把环形状态解释成逻辑顺序后，它必须等于规范历史；每组折叠历史又必须等于该规范历史在相应参数下的折叠结果。

为什么要预读 oldest bits

增量折叠不仅要加入新分支结果，还要移除滑动窗口最老的历史位。AllAheadFoldedHistoryOldestBits 提前获得可能需要移出的位，避免关键路径临时从长历史中动态读取。

推测更新与恢复

为什么不能等分支执行后再更新

第 A 个取指块尚未执行时，前端已经要预测 A 后面的 B、C、D。为了让 B 的预测看到 A 的预测结果，BPU 会立即把 A 中预测经过的分支写进全局历史。这叫推测更新：

块 A 预测 ──► 推测更新历史 ──► 用新历史预测块 B
                                  │
                                  └──► 再预测 C、D……

如果 A 的方向后来证明正确，这些推测写入自然成为正确历史；如果 A 错了，A 后面的 B、C、D 都属于错误路径，它们写入的历史必须被丢弃。

恢复不是“清零”，而是“回到快照后重放真实结果”

一次 redirect 的恢复可以拆成两个动作：

恢复后的历史
    = redirect 所在取指块开始前的正确历史
    + 该块中直到 redirect 分支为止真正发生的分支结果

也就是：

1. rollback：回到这个 FTQ 项预测前的历史边界；
2. repair/replay：根据真实执行结果，把该块中仍然有效的分支重新加入历史。

不能直接清零，因为 redirect 之前的大量老分支仍然有效；也不能只把当前 taken 位翻转，因为错误路径上可能已经推测更新了多个后续取指块。

预测时保存了什么

当 BPU 把预测块送入 FTQ 时，会把该块所对应的推测状态一起保存。当前源码中：

io.bpu_to_ftq.resp.bits.last_stage_spec_info.histPtr :=
  s3_ghist_ptr_dup(2)

Ftq_Redirect_SRAMEntry 继承 SpeculativeInfo，主要保存：

字段	恢复用途
histPtr	找回该取指块开始处的完整全局历史
ssp、sctr	恢复 RAS 的推测栈状态
TOSW、TOSR、NOS、topAddr	恢复新 RAS 的栈顶及环形栈指针关系

这里不需要为每个 FTQ 项复制整条数百位 ghv。ghv 本身是环形存储；只要检查点需要的旧位尚未被环形写指针覆盖，保存一个 histPtr 就能重新解释出当时需要的逻辑历史：

oldHistory = getHist(savedHistPtr)

这类似在环形日志中保存一个 checkpoint 游标，而不是复制整份日志。

redirect 到来时，信息怎样回来

后端发现误预测后，redirect 至少带回：

• 哪个 FTQ 项：ftqIdx；
• 块内哪条指令：ftqOffset；
• 实际方向：taken；
• 正确目标：target；
• 该指令是否为条件分支：pd.isBr。

FTQ 用 ftqIdx 读取当初保存的 Ftq_Redirect_SRAMEntry，把其中的 histPtr 和 RAS 状态放进 cfiUpdate。同时结合该 FTQ 项的 FTB entry 与 ftqOffset，计算两个关键量：

信号	含义
shift	从块开始到 redirect CFI 为止，有多少个分支结果应保留进历史
addIntoHist	redirect CFI 本身是否应作为条件分支结果加入历史

例如 redirect CFI 前面已经经过两个 not-taken 条件分支，redirect CFI 自己是第三个条件分支，则 shift=3。若 redirect 是 JAL/JALR，它改变 PC，但本身不是条件方向历史，addIntoHist 会阻止把它当成 taken/not-taken 位加入。

环形历史怎样恢复

BPU 收到 redirect 后，先取回块前指针：

oldPtr     = redirect.cfiUpdate.histPtr
updatedPtr = oldPtr - shift

之所以是减，是因为当前 CGHPtr 的推进方向就是 ptr - numberOfNewBits。随后硬件在 oldPtr 附近写入 shift 个正确结果：

• redirect CFI 前经过的条件分支写 0，因为如果它们此前 taken，就不会走到当前 redirect CFI；
• 若 redirect CFI 是条件分支且实际 taken，最后加入的最新位写 1；
• 若实际 not-taken，写入位保持 0；
• addIntoHist=false 时，不把非条件 CFI 当成方向位。

关键点是：**错误路径写过的 ghv 位不必整片擦除。**恢复后的 updatedPtr 把最新历史的边界指回正确位置；错误路径的残留位可能仍出现在 getHist 返回的高位中，但不会进入当前预测表实际消费的历史窗口。将来写指针继续前进，这些残留位会被新结果覆盖。这个结论依赖上面的容量条件，而不只是“指针退回”四个字。

用一个缩小的例子看得更清楚。假设环只有 8 格、预测器只用最近 3 位。块 A 预测前保存 oldPtr=5；getHist(5) 从新到旧读 ghv[6]、ghv[7]、ghv[0]……。A 错误地预测 taken，写 ghv[5]=1、指针到 4；错误路径块 B 又写 ghv[4]=1、指针到 3。后来 A 的真实结果是 not-taken：

恢复 oldPtr=5；把真实的 A 写成 ghv[5]=0；新指针为 4。

getHist(4) 从新到旧：ghv[5], ghv[6], ghv[7], …, ghv[4]
                       └──── 预测器所需的最近 3 位 ────┘     ▲
                                                  B 的错误残留位在高位

此时 ghv[4] 没有被清零，完整的 8 位读取仍能看到它；但它不在预测器使用的最近 3 位内。正确路径下一次要写入的位置正是 ghv[4]，会先覆盖 B 的残留，再把它纳入新的有效历史。如果写指针推进得太远，以至于提前覆盖了 ghv[6]、ghv[7] 这样的旧有效位，这套恢复方法就会失效——这正是 256 位容量预算要防的情况。

折叠历史怎样恢复

折叠历史不能仅靠“指针回退”恢复，因为它是有损摘要。当前 BPU.scala 的 redirect 路径采用可靠但相对重一些的方法：

1. 用保存的 oldPtr 调用 getHist(oldPtr)，取回块前完整逻辑历史；
2. 对每组 (histLen, compLen) 调用 computeFoldedHist，重新计算块前 folded history；
3. 再用上一节讲的 FoldedHistory.update，加入这次 redirect 对应的 shift 个真实结果；
4. 把得到的 updated_fh 送回预测流水线的 S0 状态。

源码骨架是：

val oldPtr     = redirect.cfiUpdate.histPtr
val updatedPtr = oldPtr - shift

oldFh = computeFoldedHist(getHist(oldPtr))
updatedFh = oldFh.update(ghv, oldPtr, shift,
                         taken && addIntoHist)

s0_ghist_ptr := updatedPtr
s0_folded_gh := updatedFh

因此 redirect 后用于下一次预测的两份状态仍然一致：

getHist(updatedPtr)
        │
        └──按每组参数折叠──► updatedFh

一个完整的误预测例子

仍使用 6 位逻辑历史。某 FTQ 块开始前：

H_before = 101100

预测器认为该块的前两个条件分支结果为 [N,T]，于是推测历史变为：

H_spec = (101100 << 2) | 01 = 110001

前端随后沿 taken 目标继续预测了错误路径块 W1、W2，它们又向环形缓冲写了一些推测位。稍后后端执行发现第二个分支实际为 not-taken，于是发出 redirect：

saved histPtr ──► 对应 H_before = 101100
shift          = 2
taken          = 0
addIntoHist    = 1

BPU 不从当前已经污染的 H_spec + W1 + W2 试图倒推，而是直接使用 FTQ 快照：

① 回到块前历史：      101100
② 重放真实 [N,N]：   (101100 << 2) | 00
③ 正确恢复结果：      110000

环形实现对应为：恢复 oldPtr，在它附近覆盖写入 0、0，令新指针为 oldPtr-2。W1、W2 的残留位仍可能存在于物理数组中，但在容量条件成立时，不进入当前预测表使用的有效历史范围；折叠历史则从 oldPtr 对应的历史重新折叠，再增量加入 [N,N]。

最后，BPU 同时把下一取指 PC 设为 redirect 的正确 target，并 flush 预测流水线中仍属于错误路径的 S1/S2/S3 项。这样“PC 恢复”和“历史恢复”在同一次 redirect 中对齐。

前端内部改判与后端 redirect

昆明湖 BPU 内部的 S1、S2、S3 预测结果也可能逐级修正。例如 S2 发现 S1 的方向或目标不对，会产生内部 redirect。它使用同样的基本原则：

• 选择较晚级给出的分支数与方向；
• 更新 ghv、CGHPtr、folded history 和 next PC；
• flush 更早预测但已经错误的流水状态。

后端 redirect 的区别是延迟更长，错误路径可能已经走得更远，所以必须依靠 FTQ 保存的 histPtr/RAS checkpoint 回到较老的可靠状态。

不要把训练更新与恢复混在一起：

• 恢复解决“下一拍该使用什么历史和 PC”；
• 训练解决“预测器表项以后应该学到什么”。

两者可能由同一条已执行分支触发，但状态对象和时序目的不同。

正确性不变量

1. 正常推进后，环形表示解码出的逻辑历史等于逐位移位模型；
2. redirect 恢复后，历史等于所有已保留分支的真实结果序列；
3. 被 flush 的分支结果不能残留在后续索引中；
4. 同一取指块多分支时，只把真正经过的分支加入历史；
5. 指针绕回不改变年龄和逻辑顺序。
6. 最老有效检查点需要的历史位，在检查点被消费或撤销前不能被新推测写入覆盖；当前配置对应的容量预算是 119+128+9=256，但 +9 的流水线最坏情况仍需专门验证。

验证练习

写一个软件 reference model，只维护 List[Bool] 历史。随机生成每块 0～numBr 个分支、taken 位置与随机 redirect，将 RTL 环形历史展开后逐拍比较。重点覆盖指针绕回、连续 redirect 和 backpressure 下历史不前进。