我们将假设源程序的机器无关中间表示形式使用了无限多个伪寄存器（pseudoregister)。 这些伪寄存器代表了可以分配到寄存器的变量。这些变量包括源程序中不能通过任何其他名字访问的标量，也包括由编译器生成的用于存放表达式的部分结果的临时变量。和内存位置不同，寄存器的命名是唯一的。因此可以很容易地为寄存器访问生成精确的数据依赖约束。

在中间表示形式中使用的无限多个伪寄存器最终必须被映射到在目标机器上可用的少量物理寄存器。把几个伪寄存器映射为同一个物理寄存器有一个副作用。这种映射会生成人为的存储依赖，这限制了指令级的并行性。反过来，并行执行指令产生了更多的存储需求，以便存放同时计算出来的值。因此，尽量降低寄存器使用数量的目标和最大化指令级并行性的目标直接冲突。

硬件寄存器重命名

指令级并行性首先是作为一种加快普通的顺序机器代码执行速度的手段在计算机体系结构中使用的。当时的编译器还不知道机器上的指令级并行性，其目标是优化寄存器的使用。它们仔细地重新排列指令以使所用的寄存器数目最少，但同时也使可用的并行性的数量减到最少。说明的是在表达式树的计算过程中最小化寄存器使用的同时也限制了它的并行性。

在顺序代码中的并行性太少了,计算机体系结构设计师不得不发明了硬件寄存器重命名(hardware register renaming)的概念，试图通过寄存器重命名来撤销寄存器优化所带来的影响。硬件寄存器重命名在程序运行时动态地改变寄存器的指派。它对机器代码进行解释，把本来存放在同一个寄存器中的值存放在不同的内部寄存器中，并把对这些值的使用修正到相应的内部寄存器。

因为人为的寄存器依赖约束首先是由编译器引人的，如果使用了一个认识到指令级并行性的寄存器分配算法,这些约束就可以被消除。当一个机器的指令集只能引用少量寄存器时，硬件寄存器重命名机制仍然是有用的。这种能力使得我们可以给出这个指令集体系结构的更好的实现，把代码中的由指令集体系结构规定的少量寄存器动态地映射到多得多的内部寄存器上。

如果已知所有被访问的内存位置都互不相同，那么上面的复制过程可以并行进行。但是，如果为了尽量降低所用寄存器的数量而把tl和t2赋给同一个寄存器，那么复制过程就只能顺序进行了。

寄存器分配阶段和代码调度阶段之间的顺序

如果在代码调度之前进行寄存器分配，那么得到的代码往往会有很多存储依赖，而这会限制代码调度。另一方面，如果在寄存器分配之前先进行代码调度，那么得到的代码调度方案可能需要太多的寄存器，以至于寄存器溢出（spilling)会抵消指令级并行性所带来的好处。所谓寄存器溢出是指把一个寄存器中的内容保存到一个内存位置上，使得该寄存器可以用于其他目的。一 个编译器应该首先分配寄存器然后再进行代码调度吗？还是应该按照相反顺序处理？或者我们同时解决这两个问题？

为了回答上面的问题，我们必须考虑被编译程序的特性。很多非数值应用没有那么多可用的并行性。把少量的寄存器专门用于保存表达式的临时结果就足够了。我们可以首先应用着色算法，为所有非临时变量分配寄存器，然后进行代码调度，最后为临时变量分配寄存器。

这个方法对于数值应用的效果就不太好（数值应用中有很多大型表达式）。我们可以使用层次化的方法来处理。代码优化首先从最内层循环开始，按照从内向外的顺序进行。首先进行指令调度，此时假设可以给每个伪寄存器分配一个独占的物理寄存器。然后进行寄存器分配，并在需要的地方加入处理寄存器溢出的代码，然后再次对代码进行调度。然后我们对较外层的循环重复这个过程。当把同一个外层循环中的多个内层循环一起考虑时，同一个变量可能在不同内层循环中被分配到不同的寄存器中。我们可以改变寄存器的分配方案，以避免把值从一个寄存器复制到另一个寄存器。我们将在特定调度算法的上下文环境下进一步讨论寄存器分配和指令调度之间的关系。