寄存器分配是编译器的一个重要优化技术,它的主要作用是将程序中使用的变量分配到有限的寄存器中,以减少内存访问和提高执行效率。
寄存器分配的基本过程:
- 构建程序的控制流图:将程序分割成基本块,分析程序控制流关系。
- 数据流分析:分析每个变量的定义和使用,判断变量的存活范围。
- 寄存器需求分析:统计每个基本块内同时存活的变量数量,得到寄存器需求。
- 分配寄存器:根据目标机器的寄存器数量和特征,为每个变量分配寄存器或内存位置。
- 寄存器溢出处理:当寄存器不够时,使用内存栈保存多余变量。
- 访问插入:在源代码中插入加载和存储指令,完成变量和寄存器的映射。
寄存器分配算法有图着色算法、线性扫描算法等。优化的寄存器分配可以减少 spill 和 reload,提高代码执行效率。寄存器分配是编译器优化的关键技术之一。
寄存器分配的安全性考虑
如果消除的内存访问在所考虑的代码之外具有一些重要的副作用或可见性，则注册变量是不安全的。不应注册的变量示例包括：
- 多个函数或模块之间共享的全局变量。
- 用作并发线程之间通信的变量。
- 由中断处理程序异步访问的变量。
- 用作内存映射I/O 区域的变量。
全局共享变量是编译器已知的，但其他三种情况（通常）没有反映在语言本身中。在 C 语言中，可以使用 volatile 关键字来标记变量，以表明该变量可能会被编译器未知的某种方法更改，该变量的每次操作，都必须从内存进行读写，因此不应进行巧妙的优化。操作系统或并行程序中的低级代码通常在编译时没有进行此类优化，以避免这些问题。
寄存器分配的优先级
对于一个小函数来说，也许可以注册所有的变量，这样就根本不使用内存。但即使对于中等复杂的函数（或可用寄存器很少的 CPU），编译器也可能必须选择有限数量的变量进行注册。
在开发自动寄存器分配之前，程序员负责手动识别此类变量。例如，在早期的 C 编译器中，可以将 register 关键字添加到变量声明中，强制将其存储在寄存器中。这通常是针对最内层循环的索引变量完成的。当然，程序员可能不会选择最好的变量，或者他们可能会选择太多的寄存器变量，而留给临时变量的变量太少。如今，register 关键字基本上被 C 编译器忽略，而 C 编译器能够做出明智的决定。
使用什么策略来自动选择变量进行注册？当然，那些在程序运行时经历最多数量的加载和存储的。人们可以分析程序的执行情况，计算每个变量的内存访问次数，然后返回并选择前 n 个变量。当然，对于优化程序来说，这将是一个非常缓慢且昂贵的过程，但可以想象，对于性能非常关键的程序来说，可能会采用这种方法。
更合理的方法是通过静态分析和一些简单的启发式方法对变量进行评分。在线性代码序列中，每个变量都可以根据其执行的加载和存储次数直接评分：得分最高的变量是最佳候选变量。然而，出现在循环内的变量访问可能具有更高的访问计数。我们不能说有多大，但我们可以假设一个循环（以及循环的每个嵌套）将变量的重要性乘以一个大常数。多重嵌套循环以同样的方式增加重要性。
变量之间的冲突
并非每个变量都需要一个不同的寄存器。如果两个变量的用途不冲突，则可以将它们分配给同一个寄存器。为了确定这一点，我们必须首先计算每个变量的生存范围，然后构建冲突图。在线性 IR 的基本块中，变量从其第一次定义到最终使用都是活动的。 （如果相同的代码以 SSA 形式表示，则可以独立处理变量的每个版本，并具有自己的生存范围。）
具有重叠范围的每个变量不能共享相同的寄存器，因为它们必须独立存在。相反，可以将没有重叠生存范围的两个变量分配给同一个寄存器。我们可以构建一个冲突图，其中图中的每个节点代表一个变量，然后在生存范围重叠的节点之间添加边。下图给出了冲突图的示例：
寄存器分配现在成为图形着色问题的一个实例。目标是为图中的每个节点分配不同的颜色（寄存器），以便没有两个相邻节点具有相同的颜色。
找到所需的最小颜色数的一般问题是 NP 完全问题，但有许多更简单的启发式方法在实践中有效。
一种常见的方法是按边数（冲突）对图的节点进行排序，然后首先将寄存器分配给边最多的节点。然后，沿着列表向下进行，为每个节点分配一个尚未被相邻节点占用的寄存器。如果在任何时候，可用寄存器的数量已耗尽，则将该节点标记为未注册变量，并继续，因为仍然可以将寄存器分配给冲突较少的节点。
全局寄存器分配
上述过程描述了对各个基本块的临时变量和寄存器分配的分析。然而，如果每个基本块是独立分配的，则组合基本块将非常困难，因为变量将被分配到不同的寄存器，或者根本不分配。有必要在每个基本块之间引入代码，以在寄存器之间或内存之间移动变量或从内存中移动变量，这可能首先会抵消分配的好处。
为了在整个函数体中执行全局寄存器分配，我们必须以保持分配一致的方式进行，无论控制流通向何处。为此，我们首先构建该函数的控制流图。对于图中的每个变量定义，跟踪该变量的使用的可能的前向路径，同时考虑循环和分支可能产生的多个路径。如果存在从定义到使用的路径，则该路径中的所有基本块都是该变量的活动基本块集合的成员。最后，可以基于活跃块集合构建冲突图：每个节点代表一个变量及其活跃基本块集合；每条边代表其活动集相交的两个变量之间的冲突。 （如上所述，可以以 SSA 形式执行相同的分析，以获得更细粒度的寄存器分配。）下图给出了一个简单代码片段的分析示例。
优化陷阱
注意优化的正确性。对于所有可能的输入，给定的代码片段在优化之前和之后必须产生相同的结果。我们必须特别小心给定代码段的边界条件，其中输入特别大或特别小，或者遇到机器的基本限制。这些问题需要仔细注意。
编译器优化陷阱指的是编译器在进行代码优化时,可能会改变代码的原始语义,从而导致意料之外的行为。
主要的编译器优化陷阱有:
- 变量的未初始化 - 编译器可能会假定变量已经被初始化,从而导致使用未初始化的变量。
- 死代码删除 - 编译器可能会删除认为无法执行的代码,但实际上那些代码可能会被执行。
- 代码重新排序 - 编译器可能会对代码进行重新排序,改变代码原始的执行顺序。
- 常量折叠 - 编译器可能会把计算KNOWN结果的代码折叠为直接使用结果的常量。
- 访问越界 - 编译器可能会对数组访问进行优化,但如果不正确可能会导致越界访问。
- 并行执行 - 编译器可能会对无依赖的代码进行并行优化,可能影响代码原始的执行顺序。
要避免这些陷阱,建议:
- 尽量初始化所有变量
- 避免依赖代码执行顺序的非确定性行为
- 加入内存屏障来避免指令重排序
- 用 volatile 说明易变变量
- 通过测试校验编译器优化后的代码行为