線性掃描寄存器分配

• 論文地址：

Linear Scan Register Allocation

? 我們描述了一種稱為線性掃描的快速全局寄存器分配的新算法。該算法不基于圖形著色，而是在變量生存范圍的單個線性時間掃描中將寄存器分配給變量。線性掃描算法比基于圖形著色的算法要快得多，并且易于實現，并且生成的代碼幾乎與使用基于圖形著色的更復雜且耗時的寄存器分配器獲得的代碼一樣高效。該算法適用于關注編譯時間的應用程序，例如動態編譯系統、“即時”編譯器和交互式開發環境。

不使用圖著色算法的根本原因是它要先構造好完整的干涉圖，才能在圖上著色，而干涉圖的構造代價太過高昂。應該說，圖著色過程中的大部分開銷都集中于干涉圖的構造階段。因此，雖然圖著色生成的代碼質量很高，但是對于講究編譯效率的現代編譯器來說，其時間成本是不可忽視的。對于對編譯時間更加敏感的 JIT 編譯器來說，則更是如此。除此之外，在實際的編譯工作中，人們發現了另外一個問題。由于在目前所有的硬件架構中，寄存器的數目都是有限的，故對于大型程序來說，寄存器不夠用可以說是必然存在的情況。換句話說，大型程序一定會產生大量溢出。問題就出現在這里，因為圖著色算法把重點放在解決“如何把所有的程序變量盡可能地分配到寄存器中”，如果程序一定會大量產生溢出，那么，關注“如何高效地溢出”比關注“如何盡量減少溢出”更有價值。

spill：溢出，是指目前的寄存器不夠使用，該部分數據需要借助sram或者堆棧區域的空間進行緩存協調的行為。

寄存器的數量是有限的，因此當程序中使用了過多的變量或產生了大量的臨時計算結果時，編譯器可能會出現寄存器不足的情況，導致寄存器溢出。這可能會導致編譯器將某些變量或數據存儲在內存中，而不是寄存器中，從而降低了程序的執行效率。

1. 算法介紹

線性掃描寄存器分配算法是一種用于在編譯器中分配寄存器的算法，旨在將程序中的變量映射到計算機的寄存器，以提高程序的執行效率。該算法通常用于編譯器的代碼生成階段，用于生成目標代碼。

線性掃描寄存器分配算法的基本思想是，通過一次線性掃描來分配寄存器，從而在程序的不同位置為變量分配寄存器。該算法不需要進行復雜的數據流分析，因此相對較快且簡單。以下是線性掃描寄存器分配算法的主要步驟：

1. 構建活躍變量區間（Live Range）：首先，通過數據流分析計算每個變量的活躍區間，即變量在程序中被使用的區間。活躍區間通常是變量在程序中的生命周期。
2. 排序活躍變量區間：將所有活躍變量區間按照其結束位置從小到大進行排序。
3. 遍歷活躍變量區間：從排好序的活躍變量區間列表中，按順序遍歷每個區間。在遍歷過程中，為每個區間分配一個可用的寄存器，并在需要時將之前分配的寄存器釋放。
4. 確定溢出：如果某個區間沒有足夠的可用寄存器，即產生溢出，算法會嘗試將某個寄存器的值移出到內存中，以騰出空間來分配給新的變量。

線性掃描寄存器分配算法的優點在于簡單易實現，適用于中等規模的代碼生成。然而，它可能不如其他更復雜的寄存器分配算法（如圖著色法）在某些情況下能夠達到更高的性能。不同的編譯器可能會使用不同的寄存器分配算法，以根據特定的需求和目標平臺進行優化。

2. 相關概念

live interval：生命間隔
live range：生命周期

interference：相交（conflict）

active list：已經分配物理內存的節點集合

3. 算法的實現

3.1 偽代碼

3.2 圖示

參考文獻

[1] Register Allocation in LLVM 3.0
[2] Hacker News - Register Allocation
[3] Linear Scan Register Allocation
[4] Register Allocation
[5] 博客圓-線性掃描寄存器分配