返回地址栈预测 | Codeboy's Blog

同一个函数可以由很多地方调用，返回指令的PC却可能只有一个。只记“这条返回上次去了哪里”容易把不同调用者混在一起。返回地址栈利用另一条信息：正常嵌套调用最后进入的函数，应当最先回到它的调用者。预测器保存的是这段调用历史。

形式陈述

保存返回地址，不保存程序的全部栈帧

本页借用调用与返回约定中“调用后继续执行的位置”，把它交给一个硬件风格的小预测器。它不代替内存里的程序栈，不保存局部变量或寄存器现场，也不决定一条返回在体系结构上是否正确。调用方已经识别出CALL或RET；实际返回目标仍由执行一侧提供并核对。

底层是后进先出的栈，但容量固定为 $D\ge1$ 。参考器允许 $D\le4096$ ，地址统一采用32位、4字节对齐、固定指令长4的模型。解码CALL位于PC $p$ 时，把 $s(p)=(p+4)\bmod2^{32}$ 压入；解码RET先读栈顶作预测，再弹出。普通条件分支或跳转不改变这个栈。[1][2]

独立 ReturnStack 提供 push(address)、peek()、pop()。空栈peek与pop都返回 None，pop保持原状；目标0是有效地址，不与空栈混淆。栈满再push时丢弃最旧、也就是最底部的一个地址。这个溢出规则保留最近的 $D$ 次未配对调用，却不保证以后每次返回都可预测。

环形表示与逻辑顺序

状态由 $D$ 个槽 cells、下一次写入位置 $t$ 和有效项数 $c$ 组成， $0\le t<D$ 、 $0\le c\le D$ 。按从底到顶读出的逻辑栈是

cells[(t-c)\bmod D],\ldots,cells[(t-1)\bmod D].

push把地址写入 cells[t]，令 $t\leftarrow(t+1)\bmod D$ 、 $c\leftarrow\min(c+1,D)$ 。非空pop先令 $t\leftarrow(t-1)\bmod D$ 、 $c\leftarrow c-1$ ，返回 cells[t]。pop不会擦除槽中的旧字节；计数负责说明哪些槽当前有效。因而“指针与计数又回到原值”不意味着内容也回到了原值。

这些操作分别实现普通逻辑栈的追加、删除最后一项；满栈push再删去逻辑第一项。以操作次数归纳即可得到表示不变量。每个活跃槽始终含合法地址。

一个可以完整恢复的接口

snapshot()返回不可变的全部槽内容、指针和计数。restore(state)先检查类型、容量、指针、计数、每个非空槽的地址，以及活跃槽不能为 None，全部通过后再复制状态。它是经过验证的状态导入；相同容量的另一个栈也可以产生可接受快照。它不是不可伪造的分支身份凭据。

若保存状态为 $S$ ，期间经过任意合法push/pop得到 $S'$ ，再恢复那份未改动快照，则物理状态和逻辑状态都精确回到 $S$ 。随后对相同操作序列给出的所有peek/pop结果，也与从未执行中间那段操作时相同。这是本页完整内容检查点的确定性恢复合同。

直觉

返回地址栈像按进入顺序留下的回程地址。若A调用B、B再调用C，C先回来，应该读B留下的地址；B随后回来，才读A留下的地址。返回指令PC相同也没有关系，因为当前栈顶记录了这一次嵌套的调用者。

困难出现在走错路径以后。错误路径可能已经压入几个新地址，也可能先弹出再压入。取消那些指令只是在说“它们不该执行”，不会自动把已被覆写的槽内容变回来。检查点必须保存足以恢复的状态，而不只是恢复一个看似正确的高度。

例子与边界

两次返回来自同一个PC

先遇到CALL0x100，真正跳到0x120，压入0x104。再遇到CALL0x120，真正跳到0x400，压入0x124。此时逻辑栈从底到顶为 [0x104,0x124]。

第一次RET0x400预测0x124并弹出；第二次也遇到RET0x400，预测0x104并弹出。若BTB在第一次返回提交时只记下“PC0x400去了0x124”，第二次它仍会给0x124，而RAS给出当前调用历史对应的0x104。这个事件例子省略了中间不相关指令，不是对某个二进制程序控制流的模拟。

两次覆写，让指针恢复失效

容量 $D=3$ ，初始物理槽为 [0x104,0x204,0x304]，下一写位置0、计数3。保存完整快照后，错误路径依次push0x404、0x504，槽内容变为 [0x404,0x504,0x304]。

恢复方法	连续三次pop
仅把指针和计数恢复为0、3	0x304，0x504，0x404
另外恢复旧栈顶0x304	0x304，0x504，0x404
恢复完整快照	0x304，0x204，0x104

第一个返回看似正确，后两个却已经错了。保存旧栈顶仍不够，因为这里受损的是更深两项。这个反例按本页允许满栈覆写的精确规则构造；不声称所有只存指针的实现都采用相同溢出或保护机制。文献也区分指针、指针加数据与完整状态等修复方案。[2]

三槽返回预测器被错误路径覆写两个深层地址，恢复指针或指针加栈顶仍读错，完整快照恢复原三次返回 — 内容恢复不能由栈高度代替

容量损失和不规则返回

容量2时依次push0x104、0x204、0x304，之后pop得到0x304、0x204、None。最早的0x104已被正式丢弃，恢复当前指针无法找回它。空栈返回可以改用BTB或另一个目标来源，但这不等于RAS自己预测成功。

异常展开、长跳转、尾调用与跨上下文交错可能不符合“一CALL对应一RET”的序列。需要另设更新、隔离或失效规则，不能用下面的嵌套性定理自动覆盖。本页只讨论单个明确事件流，不给跨线程或安全隔离结论。

推论与应用

嵌套正确性需要哪些条件

设观察的是实际正确路径上的调用/返回序列；每个返回都匹配最近一次尚未返回的调用，调用后的继续地址确为本页 $s(p)$ ，初始栈为空，整个序列的未返回调用深度从不超过 $D$ ，也没有未建模的异常展开或上下文切换。

对事件前缀归纳，RAS的逻辑栈恰是尚未返回调用的继续地址序列。CALL把一个新地址追加到末尾；RET按假设对应最后一项，因此peek就是实际目标，pop又留下其余未返回调用。深度上限排除了丢弃最底项。由此每次合法返回都预测正确。去掉任何相关前提，结论都需要重新检查；“栈是LIFO”本身没有证明任意程序的返回准确率。

推测状态如何进入这个保证

多在途分支恢复在每次预测前保存本页的完整快照。一旦某条分支发现方向或nextPC错误，就先恢复它之前的栈，再应用这条仍保留分支自己的CALL/RET作用，取消全部年轻记录。另存一份仅由已提交记录更新的栈，可以在整机式flush时恢复。

这里的作用由已知种类决定：CALL无论猜中了哪个目标，都应压入自己的继续地址；RET无论猜中与否，都对应一次pop。若种类本身也需要预测或会被后端纠正，必须扩充恢复协议。本页没有假装一份目标表能提供可信的解码种类。

为完整快照支付成本

固定字长下push、peek、pop各需 $O(1)$ 时间；栈占 $O(D)$ 个字。完整snapshot和restore都需 $O(D)$ 时间与复制空间，验证也逐项扫描。若最多保存 $Q$ 条在途记录，每条一份独立内容快照，快照总空间为 $O(QD)$ ，另有当前栈和已提交栈。这个成本不能写成“每条分支只保存一个指针”。

可以设计持久结构、撤销日志或保护旧槽的专门机制来降低某些成本，但它们需要各自的容量与回收证明。本页选择完整快照，是为了交出一份能够直接检查物理内容的恢复合同；不把它当作所有处理器的最省实现。

共享终点会实际执行上述两次返回、三种修复和容量损失，再以普通列表对照环形表示的全部可达小状态。有限测试之外，环形表示归纳和快照的逐字段相等给出本模型的证明。

参考资料

[1] RISCV-BOOM，The Next-Line Predictor，Return Address Stack部分：解码调用入栈、返回出栈及目标选择
[2] Kevin Skadron、Pritpal S. Ahuja、Margaret Martonosi、Douglas W. Clark，Improving Prediction for Procedure Returns with Return-Address-Stack Repair Mechanisms，MICRO1998，§§2.1–2.2，印刷页260–263：环形返回栈、推测覆写与不同修复范围。本页用显式计数让空栈返回不可用，与文中允许读出已弹旧值的模型不同；未借用其性能数字

形式陈述 ​

保存返回地址，不保存程序的全部栈帧 ​

环形表示与逻辑顺序 ​

一个可以完整恢复的接口 ​

两次返回来自同一个PC ​

两次覆写，让指针恢复失效 ​

容量损失和不规则返回 ​

嵌套正确性需要哪些条件 ​

推测状态如何进入这个保证 ​

为完整快照支付成本 ​

反向链接