为什么要寄存器重命名
指令序列里指令之间存在寄存器依赖的问题，大概分为WAW/WAR/RAW三种类型的寄存器依赖，
1 | add r0, r1, r2 add r0, r1, r2 add r3, r0, r2 |
如上是三种寄存器依赖的示意，如果编译器产生出这样的指令序列，上下两条add指令是不能
乱序执行的，因为如果乱序执行就会改变程序的逻辑。上述三种依赖中，只有RAW是真正的依赖，
其它两个依赖都可以重新选择第二条add指令的输出寄存器把依赖解除掉。比如：
1 | add r0, r1, r2 add r3, r0, r2 |
我们可以把第二条add指令的输出分别变成r6和r7, 这样它们各自两条add指令相互之间就没有
依赖，就可以在处理器内部乱序执行(可以假设处理器内部有多个加法器，这样就可以真正的
并发执行)。编译器在分配寄存器的时候是可以做这些优化的，但是寄存器资源是有限的，
最后编译器生成的指令序列难免会有WAW/WAR依赖存起。
所谓寄存器重命名其中一个目的就是为了解决如上问题。处理器内部还有一组内部寄存器，
一般把程序员可见的寄存器成为架构寄存器，把处理器内部寄存器叫做物理寄存器，物理寄
存器的个数远大于构架寄存器，寄存器重命名需要把构架寄存器和物理寄存器对应起来，
对于WAW/WAR依赖的情况，就可以把后面指令的输出映射到不同的物理寄存器上。比如:
1 | add r0, r1, r2 rename add R0, R1, R2 |
这样CPU内部计算时，指令之间就可以乱序进行，在指令执行完再把物理寄存器里的指令输出
结果提交到架构寄存器。
超标量处理器内部使用物理寄存器的另一个原因是投机执行，其实在当前PC时刻，处理器内部
早就提前投机了很多指令，如果这些指令输出是寄存器，当指令投机执行得到输出值时，只能
先保存在物理寄存器，等到指令提交的时候，才能把物理寄存器的值提交到构架寄存器。
1 | +-------+ +----+ |
怎么样做重命名
重命名需要把执行的指令流中使用的架构寄存器换成物理寄存器，直观上看需要解决的问题
有：1. 需要有一种转换的方法; 2. 需要考虑什么时候释放物理寄存器；3. 当投机执行失败
时，对于已经分配的物理寄存器以及相关资源，需要有办法回退到投机执行失败点之前。
我们下面一个一个问题考虑下。
指令其实就和软件上的函数类似，总有指令的输入和输出，指令使用输入参数做一定操作后，
通过输出寄存器输出结果(部分指令比如store没有输出寄存器)。所以，我们只要针对输出
寄存器做重命名，即给指令的输出寄存器分配物理寄存器，并把分配导致的构架寄存器和物
理寄存器的映射关系保存起来，输入寄存器通过查表就可以得到对应的物理寄存器。
但是，对于一个执行指令流，不同位置的相同构架寄存器对应的物理寄存器必然是不一样的，
其实重命名的作用就是造成这种不同，看起来构架寄存器和物理寄存器的映射表(map)似乎不
是一一映射的。实际上，map是一个动态的映射，在指令执行流的每个指令上是不断变动的，
map的存在是为了在顺序做rename的时候，为后续指令的输入寄存器提供映射到的物理寄存器:
1 | A: ld a0, [a1] map: a0->p0, a1->p1, ... |
顺着指令执行流，map不断变化。对应单条指令，map表示这一时刻，系统上，构架寄存器和
物理寄存器的映射关系。
《超标量处理器设计》这本书上介绍了三种rename的实现方式，分为使用ROB实现，构架寄存
器扩展实现，以及完全使用物理寄存器实现，我们这里只看下最后一种。顾名思义完全使用
物理寄存器的实现方式下，构架寄存器和物理寄存器的物理实现只有一组寄存器，我们这里
就叫这组寄存器是物理寄存器，而所谓构架寄存器，只是物理寄存器的映射(别名)。
1 | add a5, a0, a6 mov a0, a4 add a2, a0, a3 ld a0, [a1] |
上面第一幅图A/B/C/D四条指令都处于投机执行阶段，对应的p0-p7是一定不会映射到架构寄
存器上的。第二幅图中，A/B指令被提交，硬件用另一个映射表(a_to_p map)表示架构寄存器
实际对应的物理寄存器，可见只要在指令提交的时候，更新输出寄存器在a_to_p map上的映射
就好，根据a_to_p map，访问a0/a2架构寄存器实际访问的是物理寄存器p0/p2。第三幅图里，
C/D指令提交(我们假设一拍提交两条指令)，C指令的输出寄存器a0被重新映射为p4，同时p0
被释放。
如上已经提到了物理寄存器释放的问题。理论上讲，当一个物理寄存器不再有后续指令使用
时，这个物理寄存器就可以释放了，实践上一般把这个条件放松为，当物理寄存器对应的架构
寄存器更新时，就可以把之前的物理寄存器释放掉。
我们具体考虑硬件实现时的“数据结构”，上面已经知道我们需要两个映射表，一个记录构架
寄存器和物理寄存器的映射关系(map)，另一个记录构架寄存器访问时实际访问的物理寄存器
(a_to_p map)，前者是处理器内部寄存器重命名时使用，后者是在处理器外部访问构架寄存
器时使用。指令的构架寄存器被rename成物理寄存器后，相关的信息应该保存在指令流中每个
指令对应的ROB内(注意，ROB对应的是指令流，而不是二进制文件中的每条指令，比如一个
几条指令组成的循环，执行的时候会在ROB里被“展开”)。为了释放物理寄存器，每个ROB里
还要保存对应指令的输出架构寄存器映射的上一个物理寄存器，这样才能在这个指令退休时
释放相关物理寄存器，相关的信息在rename的时候拿到并保存到对应的ROB里，这样在map里
就应该增加相关信息的维护，就是map里不但记录构架寄存器到物理寄存器的映射，它还记录
构架寄存器上次是映射到哪个物理寄存器上的。
如下图，map是value有两个值，下面只写出了我们专注的值，可以看到C指令的p4,p0表示a0
上次是map到p0的。
1 | A: ld a0, [a1] map: a0->p0,p?, a1->p1, ... |
ROB里相关的数据结构示意如下：
1 | add a5, a0, a6 mov a0, a4 add a2, a0, a3 ld a0, [a1] |
超标量处理器要考虑的问题
我们下考虑标量处理器的情况，就是一拍rename一条指令。考虑一个两输入一输出的指令，
硬件在这一拍需要做的事有：1. 根据输入构架寄存器，在map表里找到对应的物理寄存器，
然后更新对应指令ROB里的映射信息; 2. 对于输出寄存器，需要在物理寄存器空闲列表(free list)
里找一个空闲的物理寄存器，然后把输出构架寄存器到物理寄存器的映射写入map，同时还要
更新该指令对应ROB里的输出寄存器的映射信息; 3. 硬件需要从map表里读到输出寄存器上次
映射的物理寄存器，并把这个信息更新到该指令对应ROB的映射信息里。
如上的分析中，对应map表，需要3个读口和一个写口，ROB也需要出相关的接口用于映射信息
更新。这里的读口和写口可以理解为，硬件读写特定信息时的专门接口，因为硬件上各个读写
操作是并行执行的，所以对于特定信息的特定操作需要专门接口。作为软件人员，我们先姑且
这样理解硬件，目前并不确定如上操作2和操作3中对同一位置的读写操作是否可以在一拍内
完成。
可以看到如上都是直接对map表的读写，但是，在超标量处理下，一拍需要rename多条指令，
比如一拍rename四条指令，我们考虑这个时候硬件实现的方式，可以看出来上面的处理方式
已经无法使用，我们从RAW/WAW/WAR三种依赖的rename以及构架寄存器的前次物理寄存器的映
射更新逻辑分析每种情况对应的处理办法。
1 | 1: add r0, r1, r2 rename add p0, p4, p5 |
超标量处理器需要在一拍内把如上的四条指令重命名为右边所示的情况, 并且更新map表的
相关内容。如果这四条指令相互之间没有依赖，如上的分析结果还是成立的，只不过之前是
对一条指令操作，现在是并行对四条指令操作。
但是如果这四条指令之间有依赖，情况就会不一样。如上，第一条指令和第二条指令存起RAW
和WAW的依赖，我们先看RAW依赖。因为第一条指令的输出物理寄存器是这一拍才从free list
里拿到的，所以第二条指令的输入寄存器r0所对应的物理寄存器显然应该使用直接从free list
里拿到的p0，而不是从map表里读取。
对于输出寄存器的rename，只要一拍同时在free list里取出四个空闲的物理寄存器，把四个
输出构架寄存器和物理寄存器做映射，结果分别写入四条指令对应的ROB里。但是，map里的
信息要怎么更新？如果没有WAW依赖，直接把四个不同的架构寄存器和物理寄存器的映射写入
map表就好。但是，如果存在WAW依赖，这四条指令里会有相同的输出架构寄存器，而map表里
每个架构寄存器一个时刻只对应一个物理寄存器。map表的作用是在rename阶段为后续指令的
输入寄存器提供对应物理寄存器的查找，所以map表里的内容是针对每条指令动态变化的，如
果WAW依赖之间有指令的输出来自WAW依赖指令的输出，那么这就又构成了一个RAW的依赖，正
如上面提到的，RAW依赖中的后一条指令的输入寄存器重命名不应该从map表里读，而是直接
使用被依赖的指令从free list里拿到的物理寄存器，所以，当存在WAW依赖时，只要直接把
最后WAW依赖里最后一条指令的rename信息写入map表就好。以分组的视角看这个问题，把一
拍执行的四条指令看成一组指令，这种情况下，map表的作用是以组为粒度给后续组中的指令
提供输入寄存器重命名的信息。
WAR依赖并不影响rename的逻辑, 对于第一条指令中的输入寄存器，如果没有RAW，就从map表
里读rename信息，如果存在RAW，就按照上面RAW的方式处理，对于后一条指令里的输出寄存器，
也是看和其它指令之间有没有WAW，完全按照上面的逻辑处理就可以。
在rename的时候，还要从map表里读到输出构架寄存器上次映射的物理寄存器，然后把这个信
息写入对应指令的ROB。没有WAW依赖时，这个信息还是读map表获取，WAW依赖存在时，直接
按照依赖关系拿到这个信息。
重命名恢复
超标量处理存在投机执行，投机执行的指令按照上面讲的进行rename，rename过程中会占据
各种资源，当处理器可以确认投机失败时，就需要丢弃投机执行的指令，并且释放相关的资
源，我们看下rename相关的资源要如何释放。
1 | out of order execute |
上面是ROB的一个示意图，硬件取指令后从input_insn的位置不断把指令放入ROB，j表示一条
跳转指令，放进ROB的指令都已经完成了rename，处理器内部可能有很多指令在并发乱序执行，
有的指令可能已经执行完处于完成状态(completed)，有的指令已经提交处于退休状态(retired)。
当一个时刻处理器发现j这个跳转指令分支预测做错了，就是input_insn和j指令之间投机执
行的指令取错了，处理器应该停止继续fetch指令，并丢弃j指令之前的指令，map表应该恢复
到j指令rename时的状态，然后从正确的跳转地址继续取指令执行。
如上所示的是用checkpoint做map恢复的方式，这种方式很直白，对于每个跳转指令，在其
rename的时候都把当时的map表保存到checkpoint里，遇到需要回退的时候就直接用保存起来
的checkpoint恢复map。
1 | +-------------------------------------------------------------------------+ |
如上所示还有一种walk的方法，就是按照ROB里保存的“前一个映射的物理寄存器”这个信息
反向的一步一步回退到jump时的map。当前的map表是map3, 从jump指令到D指令，每个指令
rename的过程，就是修改map表上，当前指令输出架构寄存器到物理寄存器的映射的过程，
只要根据ROB里的信息，把map3一步一步改回map即可。比如，D指令ROB a5->p6,p1表示D指令
rename的结果是把a5映射到物理寄存器p6，但是a5之前是被映射到p1上的，那么，就在map3
的基础上把a5改映射到p1，同理把a0映射到p3，a2映射到p5，就得到了jump rename后的map表。
书中还介绍了利用a_to_p map表还原map表的方法。当检测到分支预测失败的时候，继续执行
分支指令前的指令，直到到出错的分支指令，这时a_to_p map表的值和分支指令对应的map
表的值是完全一样的，直接把a_to_map的值拷贝到map就可以完成恢复。
