[科普中国]-寄存器分配程序

简介

在操作系统中，存储器管理的主要任务是为多道程序的运行提供良好的环境，方便用户使用存储器，提高存储器的利用率以及能从逻辑上扩充内存。寄存器的管理是存储器管理的重要内容。寄存器访问速度十分快，速度接近CPU运行速度，但寄存器的价格十分昂贵。为了充分利用寄存器资源，寄存器分配程序是指寄存器分配、回收等操作管理的程序。寄存器分配程序主要目的是使系统中在单位时间运行更多的作业，提高系统效率。

寄存器概述寄存器，是集成电路中非常重要的一种存储单元，通常由触发器组成。在集成电路设计中，寄存器可分为电路内部使用的寄存器和充当内外部接口的寄存器这两类。内部寄存器不能被外部电路或软件访问，只是为内部电路的实现存储功能或满足电路的时序要求。而接口寄存器可以同时被内部电路和外部电路或软件访问，CPU中的寄存器就是其中一种，作为软硬件的接口，为广泛的通用编程用户所熟知。

在计算机领域，寄存器是CPU内部的元件，包括通用寄存器、专用寄存器和控制寄存器。寄存器拥有非常高的读写速度，所以在寄存器之间的数据传送非常快。

寄存器的种类数据寄存器

用来存储整数数字（参考以下的浮点寄存器）。在某些简单（或旧）的CPU，特别的数据寄存器是累加器，作为数学计算之用。

地址寄存器

持有内存地址，以及用来访问内存。在某些简单/旧的CPU里，特别的地址寄存器是索引寄存器（可能出现一个或多个）。

通用目的寄存器

（GPRs）- 可以保存数据或地址两者，也就是说他们是结合 数据/地址 寄存器的功用。

浮点寄存器

（FPRs）- 用来存储浮点数字。

常数寄存器

用来持有只读的数值（例如0、1、圆周率等等）。

向量寄存器

用来存储由向量处理器运行SIMD指令所得到的数据。

特殊目的寄存器

存储CPU内部的数据，像是程序计数器（或称为指令指针），堆栈寄存器，以及状态寄存器（或称微处理器状态字组）。

指令寄存器 - 存储现在正在被运行的指令

变址寄存器 - 是在程序运行时用来更改运算对象地址之用。

寄存器分配步骤生成MOVE指令当目的寄存器和源寄存器应该相同时，生成MOVE指令，以满足双操作数指令的约束。

指令调度（The instruction scheduler）降低“寄存器压力”（即分配过程中硬寄存器短缺的现象）。

寻找寄存器类为每个待分配的伪寄存器找到首选的（preferred）和候选的（alternative）寄存器类。

暗中执行代码选择（code selection）。

扫描伪寄存器的一般信息（引用次数、赋值次数、引用伪寄存器的第一条和最后一条指令）。

局部分配对活跃在一个基本块内的伪寄存器分配硬寄存器。结果存到全局数组reg_renumber中。

执行一些寄存器拼接工作，例如，如果二个或更多个不冲突的伪寄存器被若干MOVE指令搅乱了，它们通常能够分配给相同的硬寄存器。执行简单的复制传播和常量传播。

全局分配对活跃于多个基本块内的伪寄存器分配硬寄存器。当它找到比局部分配更有利的硬寄存器时，它可能会改变局部分配的结果。为每个伪寄存器生成一个位向量，该向量包含与伪寄存器冲突的硬寄存器，为每个伪寄存器构建一个冲突图，并根据下面的优先权值对所有伪寄存器排序：
( log2(Nrefs) * Freq / Live_Length ) * Size
这里Nrefs是伪寄存器出现的次数，Freq是它使用的频率，Live_Length是伪寄存器在指令中活跃范围的长度，Size是它在硬寄存器中的大小。之后，全局分配器试图按由高到低的优先权顺序将硬寄存器分配给伪寄存器。
如果当前伪寄存器获得了一个硬寄存器，该硬寄存器被加入（与该伪寄存器冲突的所有伪寄存器的）硬寄存器冲突向量。通过将伪寄存器赋给硬寄存器，试图将MOVE指令中遇到的伪寄存器与硬寄存器接合起来。

reload阶段如果RTL中的操作数的不满足约束，那么就转换使其满足这些约束。这里的伪寄存器可能会被转换为硬寄存器、内存或常量。

reload遍跟在全局和局部分配之后，根据需要它可能会改变前二者的赋值。

例如：如果硬寄存器A分配给了伪寄存器V1，但引用V1的指令要求用其它寄存器类，则会生成

MOVE A to C

MOVE C to B

其中B是满足V1指令寄存器类的硬寄存器，而C可能是内存。如果B或C已被伪寄存器V2占用，则调用global.c中的retry_global函数为V2分配其它的硬寄存器，如果分配失败，则V2被放于程序的堆栈中。

消除虚拟的硬寄存器（如实参指针）、和实际的硬寄存器（如帧指针）。

对那些溢出的硬寄存器，以及最终未获得硬寄存器的伪寄存器，将堆栈槽赋给它们。

postreload阶段根据基本块上下文，删除reload阶段生成的多余的move, load, store等指令。