推测分支预测状态的恢复

方向预测完，分支的实际结果往往还没回来。若下一条分支必须等它，历史就不能及时反映正在经过的路径；若马上把猜测写进历史，猜错后的年轻分支又会继续写入更多错误状态。问题不再是一个计数器怎样增减，而是：哪些修改暂时可信，发现错误时回到哪一版，哪些结果有资格留下来训练表。

形式陈述

明确这是一份事件协议

输入事件为 begin(pc,kind)、resolve(ticket,actual,target)、commit()和 flush()。PC与目标采用32位、4字节对齐、固定指令长4的模型，顺序后继为 $s(p)=(p+4)\bmod2^{32}$ 。种类只能是条件分支C、无条件跳转J、CALL或RET；调用方在预测前已经正确识别种类。

实际方向与目标由可信的执行一侧提供，参考器只核验类型、范围和事件次序，不执行ISA，也不能识破一个调用者编造的实际结果。C允许方向0或1；另外三类实际方向必须为1。方向0时target必须为 None，方向1时必须提供合法地址。错误输入在修改任何状态之前拒绝；布尔值不当作整数接受。

状态包括：

一张gshare方向表， $2^m$ 个二位饱和计数器；推测历史H与已提交历史Hc，均为h位， $0\le h\le m\le12$
一张BTB，仅接受已提交taken记录的目标训练
当前推测RAS与已提交RAS，均采用完整内容可恢复的有界返回栈
按预测顺序排列、最多Q项的在途记录队列，以及不会复用的递增序号

这里借用重排序缓冲的按序退休原则：年轻记录可以先解析，但只有最老且已解析的记录才能提交。队列保存的是预测记录，不是假装已经包含寄存器映射、指令执行与异常状态的完整ROB。

预测时保存什么

begin先验证PC和种类。队列已满时返回不可用 None，不改状态或日志。否则，条件分支按查询前H计算

j=((p\mathbin{\gg}2)\bmod2^m)\mathbin{\oplus}(H\mathbin{\ll}(m-h)),\qquad \widehat a=[counter[j]\ge2].

非条件种类取 $\widehat a=1$ 。预测不跳用 $s(p)$ ；taken的RET优先读RAS顶；否则用BTB命中目标；两种目标来源均不可用时，回退到 $s(p)$ 并记录缺目标。

返回的不可变ticket保存序号、PC、种类、查询前H、查询索引j、当时计数器、预测方向、预测nextPC、目标来源和预测前完整RAS快照。随后把记录加入队尾：只有C把预测位移入H，CALL压入 $s(p)$ ，RET弹出一项，J不修改H或RAS。

实现用ticket对象身份确认调用者拿的是这次真实查询返回的凭据。复制出一个字段完全相同的新对象也不接受；已提交、已取消、来自别的预测器或已解析的凭据不能重新解析。递增序号用于可读日志，不是让调用方自行构造凭据的授权。

乱序解析和后缀恢复

resolve可选择任意仍在队列中、尚未解析的ticket。记实际方向为a，实际nextPC为 $p'=target$ （a=1）或 $s(p)$ （a=0）。错误条件是

a\ne\widehat a\quad\text{或}\quad p'\ne\widehat p'.

若两者都相同，只标记此记录的实际结果，不改H、RAS、方向表或BTB。若任一不同，保留这条记录和全部更老记录，取消所有更年轻记录，无论它们是否已经解析；然后把H和RAS恢复到本ticket保存的预测前状态，再应用这条分支的实际作用：C移入a，CALL压入继续地址，RET弹出。

恢复后不重新应用已取消记录。它们的凭据立即失效；调用方若要沿新路径继续，必须重新begin，拿新凭据。若将来又发现一个更老记录猜错，它可以再次覆盖当前恢复状态，并取消刚才那个已经解析过的年轻记录。[1]

方向错但数值nextPC恰巧相同，仍须修复历史并取消年轻记录。这是本协议的保守规则。方向对但目标错，也需要恢复，因为年轻记录可能来自另一个控制流后缀。

提交和整段flush

commit()只看队首。空队列或队首未解析时返回 None；否则移除这项。若为C，在保存的查询索引j处读取此刻计数器值，向实际方向作一次饱和增减；不能重算j，也不能从ticket保存的旧计数器覆盖写回。若实际taken，训练BTB的PC和实际目标。

随后将这条实际分支作用应用到Hc和已提交RAS。推测H/RAS保持不变，因为它们在此前已经包含此记录及更年轻记录的作用。仅解析还没有资格训练；被取消的记录永远不会走到这一步。[2]

flush()取消全部在途记录，把H设为Hc，把RAS恢复为已提交RAS的完整状态。它不撤销已经提交的方向表或BTB训练，也不把递增序号退回。没有某一条分支快照可用的整体清空，因此仍有确定的恢复基点。

直觉

可以把状态分成“已经结算的账”和“沿当前猜测暂记的账”。预测要用最新的暂记账，提交只把最老一笔结算；发现错误时，删除这一笔之后的全部暂记，再把这笔本身按真实结果重记。

保存索引与保存计数器的用途不同。索引回答“当时问的是哪个格子”，必须保留；旧计数器说明当时为什么那样预测，可以作为证据，却不能覆盖后来已经结算的训练。这就像保留收款账户，不等于以后都从旧余额重新算账。

例子与边界

一个年轻正确结果，仍会被更老错误取消

取m=h=2、四个计数器全为1、RAS容量3、队列容量6。先通过真实begin/resolve/commit提交CALL0x100→0x200与CALL0x200→0x300，得到Hc=0，已提交RAS为 [0x104,0x204]。下面按事件顺序发生；表中的RAS从底到顶显示。

事件	结果或队列变化	H	推测RAS
begin A：C，PC0x300	j=0，预测N，nextPC0x304	0	104，204
begin B：CALL，PC0x304	目标MISS，猜0x308，压入0x308	0	104，204，308
begin C：RET，PC0x400	从RAS预测0x308并弹出	0	104，204
resolve C：实际0x308	正确，但A未解析，不能提交	0	104，204
resolve B：实际0x500	仅目标错，取消C，恢复后重压B	0	104，204，308
resolve A：实际taken到0x600	取消B，恢复A之前并移入1	1	104，204
commit A	counter[0]由1变2，Hc变1	1	104，204

RAS栏的104等均为十六进制简写。B和C都曾拿到真实结果，C甚至完全猜对，但它们仍位于A的错误路径后缀中，因此不能训练方向表或目标表。A提交后的BTB槽0属于PC0x300，目标0x600；原先的两个CALL也占这个槽，已按直接映射规则被替换。

先解析年轻返回，再由调用目标错误与更老条件错误逐层取消；恢复到保存的前状态，只有最老已解析记录提交训练 — 正确解析不等于有资格提交

方向与nextPC的两个独立错法

PC0x100的条件分支预测N，顺序nextPC为0x104。如果真实结果是taken，而真实目标也恰好0x104，那么地址比较没有变化，历史位却应从0改成1。只检查nextPC的版本会留下错误H。本接口明确报告 direction_wrong=True、next_pc_wrong=False，仍触发后缀恢复。

另一次先让BTB记住PC0x100的目标0x300，方向计数器初始为2。它预测T到0x300，而真实结果是T到0x400。这次方向没有错，目标错了；仍需取消年轻后缀。BTB命中和方向正确都不能免除nextPC核对。

两个查询读过同一个旧计数器

取m=h=0，方向表只有一个格子，初值1。先预测A为N，再解析A为T，但暂不提交；此时A已修复历史，表仍为1。随后预测B也读到1，解析B为N。队列中A、B都已解析，且B是在A恢复后才开始，不会被那次恢复取消。

依次提交A、B，应得到 $1\to2\to1$ 。若每次都从ticket的旧值1计算，A写2之后B会写0，丢掉A的训练。若改成提交时重新计算gshare索引，又会在h>0的例子中更新另一个格子。两种错误解决的是不同问题，参考器分别用外部错误版本击穿。

清空不是把一切归零

先提交一次CALL和一次taken条件分支，Hc=1、已提交RAS为 [0x104]。随后推测RET把栈弹空，又预测一条条件分支；即使年轻条件分支先解析正确，整体flush也取消这两项。恢复结果应为H=1、RAS [0x104]，而不是H=0或空栈；表中已提交训练仍保留。两个旧ticket此后都拒绝解析。

推论与应用

可重放的不变量

令C为已提交记录序列，Q为当前在途记录序列。给每条记录定义一个状态变换：C类移入实际位（已解析）或预测位（未解析），CALL作push，RET作pop，J不动。对C只使用实际结果。

不变量一：Hc与已提交RAS等于从初始状态按顺序重放C的结果。不变量二：推测H/RAS等于重放C后，再按顺序重放Q的结果。不变量三：每个仍存活ticket的检查点等于其自身之前那个前缀的状态。不变量四：方向表与BTB等于只按C的提交顺序训练所得，方向训练使用各自保存的查询索引和当时当前值。

初始四者显然成立。begin保存当前前缀再追加预测作用，保留它们。正确resolve的实际方向和预测方向相同，CALL/RET种类也不变，所以只把一个暂定作用换成相同的实际作用。错误resolve取消年轻后缀，恢复有效的前缀快照，再施加当前实际作用，恰得到缩短后的重放结果。它也解释了为什么更老错误出现时必须取消先前恢复过的年轻分支。

commit把Q首项移到C末尾；两段串接的作用序列没有改变，故推测状态不需再执行一次该作用。已提交副本与两张表只执行这一次实际更新，四条不变量继续成立。flush把Q变空并恢复C的副本，也正好满足定义。返回栈的物理槽一并保存，使这里不仅恢复高度，也恢复以后会读到的内容。

上述证明说明协议内部的预测状态和训练生命周期一致。它不说明预测一定正确，也不能代替完整处理器的寄存器、内存、异常及体系结构提交证明。若实际结果或解码种类不可信，重放的也只是调用者给出的事件。

成本与推进条件

令方向表项数为P、目标表项数为N、RAS容量为D、在途上限为Q。关闭日志时，两张表、两个当前栈和在途完整快照共需 $O(P+N+D+QD+Q)$ 个字。一次begin因复制RAS及追加队列，摊还需 $O(D)$ ；若单次Python列表扩容需要搬移Q项，该次最坏为 $O(D+Q)$ 。身份查找为 $O(Q)$ ，错误resolve再复制D项并移除年轻后缀，故为 $O(Q+D)$ 。参考器用Python列表弹出队首，commit仍有 $O(Q)$ 的搬移成本，尽管单次计数器和BTB训练都是常数操作。commit返回被移除的ticket，因此调用返回时它的完整快照仍有引用；若调用方随后丢弃这个返回值，最终释放其D个槽引用还需 $O(D)$ ，这部分不能凭空忽略。

flush移除在途记录并复制已提交栈。若把各快照引用释放所需工作也计入，最坏为 $O(QD+D)$ ；取消后缀释放k份快照也可能需要 $O(kD)$ ，因此包含对象回收的resolve上界应写成 $O(Q+D+kD)$ 。这些是这份完整快照实现的费用，不把硬件并行恢复当作常数时间Python操作。调用方若长期保留已取消或已提交的ticket，其快照空间也须另外计入。开启事件日志还会保存栈内容、完整ticket及提交时的两表快照；其大小与事件数相关，不能并入固定在途空间界。重放测试oracle与JSON显示另计。

每个单次调用都终止。若停止加入新记录，调用方最终给每个剩余队首提供合法结果，并持续调用commit，则有限队列会被提交或取消至空。若外部不断提供新分支或永远不解析队首，本接口没有保证自动前进；也没有根据事件数推导IPC或真实周期数。

BOOM文档与原论文说明推测历史、分支检查点、提交副本及训练时机的必要区分。[1][2] 本页组合的是显式教学变体：逐分支记录、直接映射BTB、普通二位饱和FSM、完整RAS快照。它不是BOOM取指包队列、其特殊计数器状态机或具体恢复端口的逐行复刻。

可执行终点要求交出事件顺序、取消身份、两个历史版本、每次实际训练位置、完整栈恢复和错误版本的失败证据，再用不依赖检查点的列表重放器逐事件核对这些不变量。

参考资料

[1] Kevin Skadron、Margaret Martonosi、Douglas W. Clark，Speculative Updates of Local and Global Branch History: A Quantitative Analysis，JILP2，2000，§§3.1、3.3：推测全局历史、恢复误预测之前状态再移入实际位、更老误预测覆盖年轻修复；本文独立证明所列事件协议
[2] RISCV-BOOM，The Backing Predictor，Managing the Global History Register、Updating the Backing Predictor、The Fetch Target Queue：推测GHR、分支与已提交副本，以及保存预测信息和按提交训练。硬件组织与本文不同，未移用性能数字或具体流水时序

形式陈述 ​

明确这是一份事件协议 ​

预测时保存什么 ​

乱序解析和后缀恢复 ​

提交和整段flush ​

一个年轻正确结果，仍会被更老错误取消 ​

方向与nextPC的两个独立错法 ​

两个查询读过同一个旧计数器 ​

清空不是把一切归零 ​

可重放的不变量 ​

成本与推进条件 ​

反向链接