寄存器重命名

寄存器重命名是计算机CPU的微体系结构（Microarchitecture）中的一种技术，避免了机器指令或者微操作不必要的顺序化执行，从而提高了处理器的指令级并行的能力。

问题定义

计算机的CPU往往用寄存器来保存指令的操作数与结果。x86 指令集体系结构有8个整数寄存器，x86-64指令级体系结构有16个整数寄存器，许多RISC体系结构有32个整数寄存器，IA-64有128个整数寄存器. 在小型处理器，这些指令集体系结构寄存器直接对应于寄存器堆中的物理寄存器。

不同的指令可以有不同的执行时间，特别是CISC指令集体系结构上更为明显。例如，一条读内存的指令的执行时间，足够执行几百条其它指令。因此，在允许多条指令并行执行的情况下，那些指令地址顺序靠后的指令，比读取内存指令更早完成，这就形成了指令执行顺序不同于其在程序中的顺序。这种乱序执行是高性能CPU提高运算速度的关键办法之一。

考虑下述代码片段在乱序执行CPU上的运行：

1. R1=M[1024]
2. R1=R1+2
3. M[1032]=R1
4. R1=M[2048]
5. R1=R1+4
6. M[2056]=R1

第4、第5、第6条指令在功能上是不依赖于第1、第2、第3条指令的。但是处理器却不能在第3条指令完成前去完成第4条指令（在指令流水线上，不能在第3条指令完成前，就提交第4条指令的结果），因为这可能会导致第3条指令把错误的数据写入内存。

通过改变一些寄存器的名字，可以使上例中指令并行执行所受的限制：

1. R1=M[1024]	4. R2=M[2048]
2. R1=R1+2	5. R2=R2+4
3. M[1032]=R1	6. M[2056]=R2

现在，4、5、6号指令可以与1、2、3号指令并行执行，二者没有依赖问题。这使得程序可以用更短时间完成。

编译器会尽力检测出类似这样的问题，并把不同的寄存器分配给不同的指令使用。但是，受指令集体系结构的限制，汇编程序可以使用的寄存器名字的数量是有限的。很多高性能CPU的实现—微体系结构—有很多物理寄存器，可以在处理器指令流水线执行时把这些指令集体系结构寄存器映射为不同的物理寄存器，从而在硬件级提供了额外的并行能力。

数据冲突

如果多条指令使用了同一个存储位置，这些指令如果不按程序地址顺序执行可能会导致3种数据冲突（data hazard）:

先写后读（Read-after-write，RAW）:从寄存器或者内存中读取的数据，必然是之前的指令存入此处的。直接数据相关（true data dependency）
先写后写（Write-after-write，WAW）：连续写入特定的寄存器或内存，那么该存储位置最终只包含第二次写的数据。这可以取消或者废除第一次写入操作。WAW相关也被说成是“输出相关”（output dependencies）。
先读后写（Write-after-read，WAR）：读操作获得的数据是此前写入的，而不是此后写操作的结果。因此并行和乱序时无法改善的资源冲突（antidependency）。WAW和WAR可以通过寄存器重命名解决（register renaming），不必等待所有读操作完成后再执行写操作，可以保持这个存储位置的两份副本：老值与新值。读老值的操作可以继续进行，无需考虑那些写新值甚至写新值之后的读新值的操作。产生了额外的乱序执行机会。当所有读老值操作被满足后，老值所使用的寄存器既可以释放。这是寄存器重命名的实质。

任何被读或写的存储都是可以被重名。最常考虑的是通用整数寄存器与浮点寄存器。标志寄存器、状态寄存器甚至单个状态位也是常见的重命名的对象。

内存位置也可以被重命名，虽然这么做不太常见。全美达的Crusoe处理器的gated store buffer是一种内存重命名。

如果程序没有立即重用寄存器，它就不需要寄存器重命名这种机制。例如IA-64指令集体系结构提供了128个通用寄存器，就是出于此考虑。但这种努力也遇到了困难：

编译器很难完全避免在不导致程序尺寸大增的同时避免重用寄存器。程序的循环的连续迭代执行就需要复制循环体的代码以使用不同的寄存器，这种技术叫做循环展开。
大量的寄存器，需要在指令的操作数中用很多位去指出，导致程序尺寸变大。
很多指令集在历史上就使用了很少的寄存器，出于兼容原因现在也很难改变。

程序的代码尺寸增加，会导致指令高速缓存的未命中（cache miss）增加，处理器执行停顿等待从低级存储中读入代码。这对运算性能的影响是致命的。

体系结构寄存器与物理寄存器

编译器或者汇编器生成的机器语言程序读写有限数量的指令集体系结构（ISA）寄存器。例如，Alpha ISA使用32个64位宽整数寄存器，32个64位宽浮点寄存器。这些体系结构寄存器，是程序可以直接访问的逻辑上的寄存器。如果程序员在调试器中把这个程序暂停，可以观察到这64个寄存器与一些状态寄存器当前存储的值。

一款特定的处理器，实现了这种处理器体系结构。例如Alpha 21264有80个整数寄存器、72个浮点寄存器，作为处理器内物理实现的寄存器。也就是说，Alpha 21264处理器有80个物理存在的位置存储整数运算的结果，72个位置存放浮点运算的结果。实际上，该款处理器有更多的物理存在的存储位置，但与寄存器重名关系不大。

下面介绍两种寄存器重命名方法，区别于为执行单元准备数据的电路。处理器把指令流使用的体系结构寄存器改为用若干位表示的tags所索引的物理寄存器。

tag索引的寄存器堆（tag-indexed register file）是一个很大的寄存器堆，当一条指令发射（issue）给执行单元，源操作数的寄存器tags将发送给物理寄存器堆，其中该tags所对应的物理寄存器的内容被发送给该执行单元。

保留站（reservation station）方法，存在多个小型相关的寄存器堆，通常是每个执行单元的输入口都有一个物理寄存器堆。发射队列中的每条指令的每个操作数对应着这个物理寄存器堆的一个存储位置。当一条指令发射给某个执行单元，执行单元对应的寄存器堆的相应条目被读出发送给执行单元。

体系结构寄存器堆（Architectural Register File）或者引退寄存器堆（Retirement Register File，RRF）：存储了被提交的体系寄存器的状态。通过逻辑寄存器的号来查询这个寄存器堆。重排序缓冲区（reorder buffer）中的引退（retired）或者说提交（committed）指令，把结果写入这个寄存器堆。
远期寄存器堆（Future File）：处理器对分支做投机执行的寄存器的状态保存于此。使用逻辑寄存器号来索引访问。在Intel P6微体系结构，称之为Active Register File。
历史缓冲区（History Buffer）：用于保存分支时的逻辑寄存器状态。如果分支预测失败，将使用历史缓冲区的数据来恢复执行状态。
重排缓冲区（Reorder Buffer，ROB）：为了实现指令的顺序提交，处理器内部使用了一个Buffer。如果在该缓冲区中排在一条指令之前的所有都已经提交，没有处于未提交状态的（称作in flight），则该指令也被提交（即确认执行完毕）。因此重排缓冲区是在远期寄存器堆之后，体系结构寄存器堆之前。提交的指令的结果写入体系寄存器堆。

重排缓冲区分为data-less与data-ful两种。

Willamette's ROB，其条目指向物理寄存器堆（PRF）中的寄存器。此外还包括一些簙记数据。这是第一种乱序执行设计，由Andy Glew在Illinois用HaRRM完成。

Intel P6的ROB，条目包含了数据。没有单独的物理寄存器堆。来自ROB的数据在指令提交后将复制到引退寄存器堆（RRF）。

细节：tag索引寄存器堆

这种重命名模式用于MIPS R10000、Alpha 21264，以及AMD Athlon的浮点部分。

在重命名阶段，每个被引用的体系结构寄存器（不论是读还是写）按其体系结构索引号到重命名文件（remap file）中查找，取出一个tag与一个ready位。如果一个排队在前的写操作要把数据写入该寄存器，但该写操作尚未执行完，则这个tag是未就绪的（non-ready）。

对于寄存器读，这个tag替换了体系结构寄存器，即这种先写后读的寄存器数据相关必须恪守，该读操作只有在该ready位是就绪之后才可以被分派执行。
对于寄存器写，从一个空闲tag先进先出队列（free tag FIFO）取出一个新的tag，且这项新的映射条目写入重命名文件，未来的读取该体系结构寄存器的指令将指向这个新的tag，即“写后写”是一种寄存器数据伪相关，用这种重命名就可去去掉伪相关。这个tag被标记为未就绪，因为写操作尚未执行。以前为该体系结构寄存器分配的物理寄存器被保存在指令的重排缓冲区（reorder buffer）中；即：以前为该体系结构寄存器分配的物理寄存器可以从重排缓冲区中查到。重排缓冲区是一个先进先出队列，依照指令解码的顺序（即指令在程序中的先后顺序）安排指令引退的顺序。

操作数寄存器被重命名后的指令将被放入不同的发射队列（issue queues）。这些指令等待所需的各种资源（如源操作数对应的物理寄存器）就绪。

当指令执行完，其结果的tags将被公告，发射队列中用这些公告的tags匹配那些未就绪的tags。一个匹配就意味着该操作数就绪了。重命名文件也去匹配这些公告的tags，从而标记哪些对应的物理寄存器是就绪的。

当发射队列中的某条指令的所有操作数是就绪的，这条指令就是发射就绪。在每个周期，发射队列捡出一些就绪指令，发送到功能单元。未就绪指令仍然留在发射队列中。这种从发射队列中无序删除指令，使得发射队列的电路实现占用面积大、功耗高。

被发射的指令读取源操作数的tag索引在物理寄存器堆中对应的物理寄存器（忽略掉刚刚公告过的操作数），然后开始执行指令。

指令执行结果写入目的操作数的tag索引在物理寄存器堆对应的物理寄存器，同时公告给每个功能单元输入端的旁路网络（bypass network，即把执行结果“直通”给流水线各个步骤的中间缓冲）。

写寄存器的指令在引退时，把被写的目的操作数寄存器使用过的上一个tag放入“空闲tag队列”中，使得它可以被其它被解码的指令重用。而该指令的目的操作数寄存器当前对应的tag仍然被占用，因为后面可能还有指令需要读取当前tag对应的物理寄存器的内容。

一个异常（将导致中断）或者分支预测失败导致了重命名文件退回到最后一条有效的指令的重命名状态，通过组合状态的快照（在历史缓冲区）与重排缓冲区中等待顺序引退的指令的以前用过的tags。这种机制可以实现恢复任意时刻的重命名状态。

细节：保留站

这种重命名模式用于AMD K7与K8的整数寄存器设计。

在重命名阶段，作为源操作数的体系结构寄存器在远期寄存器堆与重命名文件中查找对应的物理寄存器。如果没有写指令还没有完成写入该物理寄存器，则说明这个源操作数已经就绪。当这条指令被放入发射队列，从远期寄存器堆相应的物理寄存器读出内容放入保留站中对应的条目。指令对目的寄存器的写入，在重命名文件中的产生了一个新的、未就绪的tag。tag数通常是按照指令的顺序分配，因此不需要空闲tag先进先出队列。

如同tag索引模式，发射队列中的未就绪操作数等待匹配的tag公告。但不同于tag索引模式，tag的匹配导致对应的内容数据写入发射队列对应的保留站的条目。

被发射的指令从保留站读取它的操作数，忽略掉那些刚刚公告过的操作数，然后开始执行。保留站寄存器堆通常很小，可能只有8个条目。

指令执行结果写入重排缓冲区，以及保留站（如果发射队列有匹配的tags），以及远期寄存器堆。

指令引退时，复制重排序缓冲区中的值到体系结构寄存器堆。体系结构寄存器堆用于从异常或者分支预测失败时恢复。

在指令引退时可以识别出异常与分支预测失败，引起体系结构寄存器堆覆盖掉远期寄存器堆的内容，并标记重命名文件中所有寄存器都是就绪。通常，没有办法为一条处于解码与引退之间的指令恢复远期寄存器堆，因此通常没有办法在更早期为分支预测失败做恢复工作。

比较两种模式

在两种模式下，指令被顺序送入发射队列，但从发射队列移出是乱序的。

保留站具有更好的延迟（latency）性能。因为重命名阶段直接获得寄存器内容，而不是获得物理寄存器号，再用这个号去获得内容值。

保留站具有更好的从指令发射到执行的延迟性能。因为每个本地寄存器堆远小于那种大型的用tag索引的中央寄存器堆。tag产生与异常处理也更为简单。

与tag索引的简单的寄存器堆相比，保留站的物理寄存器堆的总规模更大，功耗更大，更为复杂。更糟糕的是，每个保留站的每个条目可以被每条结果总线写入。例如，每个功能单元具有8条发射队列条目的处理器，相比于tag索引的模式有9倍的旁路网络，结果直通（forwarding）需要更大的功耗与面积。

保留站模式在4个位置（远期寄存器堆，保留站，重排序区、系统结构寄存器堆）保存结果值。而tag索引模式只需要在物理寄存器堆保存结果值。由于结果值来自功能单元，保留站模式必须公告结果到许多存储位置，用掉了非常多的功耗、面积、时间。如果处理器具有非常精确的分支预测、非常关注执行延迟，保留站也是个很好的选择。

历史

IBM System 360 Model 91是早期支持乱序执行的计算机。它使用Tomasulo算法用到了寄存器重命名。

1990，POWER1是第一种使用了寄存器重命名与乱序执行的微处理。

最初的R10000设计既没有发射队列压偏（collapsing），也没有可变优先权编码，因此遇到了寄存器资源饿死（starvation）—最老的指令在队列中一直没有被发射，直到解码指令因为缺乏可重命名的物理寄存器而完全停顿，而所有就绪指令都已经发射了。后来修改设计的R12000使用了部分可变优先级编码来克服此问题。

早期乱序执行处理器并不区分重命名与重排序缓冲区/物理寄存器堆的功能。因此，某些最早期的产品，如Sohi的RUU，Metaflow DCAF，组合了调度、重命名，存储在一个结构中。

大多数现代处理器的重命名使用了一个映射表，用逻辑寄存器号去索引。例如Intel P6微体系结构。远期寄存器堆也是如此，并在此存放数据。

但是，更早的处理器使用内容寻址存储技术实现重命名，例如HPSM RAT，以及存储器别名表（Register Alias Table）。

某种程度上，乱序执行的微体系结构的故事就是这些内容寻址存储如何逐步被清除。

Intel P6微体系结构是Intel处理器中第一种乱序执行、寄存器重命名。P6发展出了Pentium Pro、Pentium II、Pentium III、Pentium M、Core、Core 2等处理器系列。

参考文献

Smith, J. E.; Pleszkun, A. R. Implementation of precise interrupts in pipelined processors (PDF). Proceeding ISCA '85 Proceedings of the 12th annual international symposium on Computer architecture. 1985 [2012-09-08]. doi:10.1145/327010.327125. （原始内容 (PDF)存档于2007-04-11）.