物理寄存器重命名

先给值编号，再允许计算换次序 ​

考虑三条相邻指令：

I0: r1 ← r2 × r3
I1: r4 ← r1 + r2
I2: r1 ← 7

I1需要的是I0将产生的r1，并不需要I2的7。若把它们重命名成

I0: p6 ← p2 × p3
I1: p7 ← p6 + p2
I2: p8 ← 7

I2先算好也没有关系：7进p8，不会碰I1等待的p6。逻辑名字r1被多次使用，但每个动态写入都获得不同身份。

这消除了两个位置冲突：I0与I2的WAW，即两个写者共用名字；I1与I2的WAR，即读者要先取旧值、后面的写才可覆盖名字。I0到I1的RAW仍在，I1必须等p6真正就绪。给数据改了名，没有让乘法提前完成。

五条指令的实际版本表 ​

初始寄存器为 [0,2,3,4,0,9]，使用11个物理位置，内存槽0为31。程序为：

I0: MUL   r1,r2,r3
I1: ADD   r4,r1,r2
I2: CONST r1,7
I3: ADD   r5,r1,r3
I4: STORE [0],r4

从最小空闲编号分配，得到：

当I2已经算出7而I0尚未完成时，$S[r1]=p8$，$C[r1]=p1$。前者说下一条新来的r1读者应跟随谁，后者说当前架构r1仍是初值2。I1两者都不再查询，它已经保存了自己的源p6。

按后续页面的周期规则理路标签就绪与动态发射Tagged ready instruction issue · Age-ordered ready issue · 标签就绪发射根据固定源标签、操作数就绪和执行单元可用性选择最老候选，逐周期区分运算延迟、结果端口仲裁与顺序退休。，I2在周期5发布7，I0到周期8才发布12。I1读取12与3，得到15；I3读取7与4，得到11。最终r1=7、r4=15、r5=11，STORE写15。若I1临执行才去读“当前r1映射”，它会读到7，错误得到10；参考器实际运行了这个破坏版本，并观察到内存也随之变成10。

自引用指令必须先读源 ​

初始r0=3，执行 r0 ← r0+r0。先读源得到两个旧标签p0，再分配p1，计算得到6。若先把 $S[r0]$ 改成p1，再读源，会得到 p1 ← p1+p1：p1尚未就绪，却要等自身产生结果。后端再空闲也解不开这条自环。

参考器以两个物理位置连续执行两次自加，最终得到12。这个最小例同时检验同源重复读取、源目的同名，以及退休释放后物理位置复用。

完成时释放旧版本为什么太早 ​

上表中I2保存的旧标签是p6。I2在周期5已经完成，但I0仍在计算p6，I1也仍等着读它。若此时把p6释放，新指令就可能占用这个仍有生产者和消费者的位置。参考器提前把p6放入F，立即触发源生命周期检查。

正确释放点是I2退休。顺序退休保证I0、I1已经退休；I1已经读完p6。主例在周期11才释放p6，而不是周期5。旧标签指“这次覆盖写之前的版本”，不是“本条指令自己的新目的”，更不是随便一个旧物理编号。

最近较老写者的不变量 ​

对已经重命名的前k条指令归纳。初态每个名字映到自己的初值。下一条读取r时，归纳假设保证 $S[r]$ 是前k条中最后一次写r的版本；没有这种写时就是初始版本。先复制源标签，使这次读取不再受后续映射变化影响。随后为本条目的分配新版本，恰好让S满足加入本条后的同一条件。

因此每个源依赖要么指向初值，要么指向严格较老的指令。依赖图无环。只要执行器在源ready后才读值，且每个版本在最后所需读取前不被回收，乱序执行仍使用顺序语义规定的操作数。

这里的生命周期由顺序退休完成。设指令J写r并保存旧标签o。所有使用o的指令都在J之前，或者就是J自己的源；J之后重命名的r读者会得到J的新标签或更新版本。J退休时所有较老指令已退休，J也已完成执行，所以没有未完成读取仍需要o。即使更年轻指令已经再次覆盖r，释放o也安全。

完整分配账与异常恢复 ​

在本页不做复制消除、不共享物理目的的模型中，物理位置可精确分为三类：

点号表示互不相交。初态成立；重命名从F移一项到未退休目的；退休把新目的移进C、把被替代旧项移回F。这个不变量同时发现重复分配和寄存器泄漏。

若异常到达退休队首理路重排序缓冲与顺序退休Reorder buffer retirement · ROB in-order retirement · 重排序缓冲区让结果乱序准备而架构效果只按队首退休，以已提交映射、延迟store与完成记录取消维持可精确恢复的指令前缀。，先取消全部未退休指令及其尚未发布的完成记录，再令 $S=C$，把C像集之外的物理位置全部回收。顺序提交状态仍在原位置，无需把年轻值逐项反向算回去。取消结果记录必须先于编号复用；否则一个迟到的旧结果可能写进重新分配的位置。本实现只有本地执行记录，并在恢复时真正清空它们；外部不可取消的执行单元还需要额外身份或隔离协议。

资源、成本与相邻概念 ​

至少一份额外物理位置允许机器退化成逐条计算、退休、复用；没有余量且下一条要写寄存器时，前端无法分配。多个余量主要扩大可同时在途的版本数，并不改变程序结果。给正常片段只留一个额外位置、ROB容量8，实际需19周期；11物理位置时为13周期。

直接数组映射使至多两个源和一个目的的读取为常数操作；参考器为确定选最小编号而执行 min(F)，最坏需 $O(P)$，没有把这一步报成常数。两张映射及物理值/ready占 $O(L+P)$ 项，未退休记录另按数量计。异常全量重建空闲集合需 $O(L+P)$ 工作；硬件的并行电路可以采用不同时间/面积权衡。整数数据和身份超过一个机器字时，另计位成本。

编译器的寄存器分配理路经验证的寄存器分配Verified register allocation · Certified register allocation · 寄存器分配验证以活跃值位置一致关系、干涉约束、溢出重写和调用约定检查证明临时量到寄存器与栈槽的映射保持语义。把程序临时量放入架构可用的寄存器与栈槽；本页则在运行时把已经选定的架构寄存器名字扩成物理版本。两者都要保护值的生命周期，但输入、资源和发生时机不同。内存地址间的RAW/WAR/WAW也不会因寄存器重命名自动消失，本单元干脆排除了load，以免省略存储依赖后仍声称完整乱序机器正确。