寄存器分配問題？

01-12

最近想自己寫個編譯器，到了寄存器分配這一步，有很大的疑惑，不知能否後序遍歷表達式樹來分配寄存器？寄存器分配有沒有什麼可參考的簡單實現？

寄存器分配有很多做法。當然有可以通過後序遍歷表達式樹來分配寄存器。

引用University of Washington CSE401里關於寄存器分配的課件：

Varieties of register allocation

Register allocation may be performed at many levels:

Expression tree

Local (basic block)

Loop

Global (routine)

Interprocedural

Global optimization suggests global register allocation.

在表達式樹層面上做寄存器分配是其中比較簡單的一種，比local（在基本塊內做分配）更弱一些。

（這個回答的剩餘部分其實並不長，只是列舉了兩種簡易思路以及各自的小變種，文字很少，只是舉例用的代碼占篇幅多而已。請跟我一起默念三次「文章不長能讀下去」然後讀到底 &>_&<）

===================================================

正統的做法大多是global的，例如：

圖著色（graph coloring）；
線性掃描（linear-scan）；
以上兩者的一些變種，像是Graph Fusion，Graph Coloring over SSA，Linear-Scan over SSA，Extended Linear Scan，Greedy Linear Scan（LLVM的Greedy分配器）；
以及一些比較新奇或暫時還比較冷門的，例如PBQP、puzzle solving之類，這些都有實現在一些編譯器里。還有一些沒怎麼實現在編譯器里的，像是王垠大大提出的Model Transformer Semantics之類。

商用的編譯到native code的編譯器如果不好好做寄存器分配的話那都得是渣渣，不用找借口。

渣渣的例子之一是Dalvik VM的JIT編譯器：都什麼年代了還用奇怪的local heuristic來做分配；而且更搞笑的是採用local heuristic之前其實實現過linear-scan，但是發現效果不好所以在產品里沒啟用——因為實現得太糟糕了orz

Remove vestiges of code intended for linear scan register allocation in the trace compiler. New plan is to stick with local allocation for traces and build a new linear scan allocator for the method compiler.

========================================================

然後有一些從現在的角度看不那麼正統的、更為簡易的做法。

自己出於學習目的寫入門級編譯器時，先從簡單的做法開始未嘗不可。有不少教學用的入門級編譯器可以說是跳過了寄存器分配的這一環。

這裡讓我們先從看似簡單但不太現實的做法開始，逐步進化到簡單又現實的做法。

下面介紹的都是所謂「on-the-fly」寄存器分配的做法，因為它們不需要單獨遍歷一趟IR，而直接融合在代碼生成（code generation）階段就好了。

最簡單的就是：不分配！

把目標平台提供的通用寄存器都用作特殊用途，而把函數的局部變數和表達式臨時值都放在棧幀里。

就算目標平台的ABI要求的調用約定（calling convention）是通過寄存器來傳遞參數和返回值也沒關係：在函數入口的地方就把所有通過寄存器傳遞的參數都存到棧上，然後在臨返回之前把返回值讀到返回用的寄存器里。

用一個例子來說明這種做法的效果：

int foo(int a, int b, int c, int d) { int e = a * b + c * d; return e + d; }

這個函數有一個基本塊，其中有兩個語句，也就是說有兩棵表達式樹（每個語句有一棵）。

讓我們把後序遍歷表達式樹的過程表現為線性代碼，那麼對應的遍歷過程可以是：

// int e = a * b + c * d; _t0 = a * b _t1 = c * d e = _t0 + _t1 // return e + d; _t0 = e + d return _t0

其中_t開頭的是計算表達式所產生的臨時值。

語句之間可以復用臨時變數，因為臨時變數的生命期僅在一棵表達式樹內，而表達式樹不會跨越語句的邊界。所以上面例子提到的_t0、_t1這些臨時變數都可以復用。

如果我們把這個函數里出現的所有具名參數、局部變數，以及匿名的臨時值，都劃分到棧幀的固定位置上，那我們就可以得到這樣的棧幀：

（這裡偷個懶用固定8位元組寬的stack slot，無論是4位元組還是8位元組寬的值都佔用一個slot）

假定我們要遵循Linux x86-64的ABI（System V AMD64 ABI），那麼傳入的頭4個整型參數會從寄存器RDI、RSI、RDX、RCX傳入，而返回值會從RAX傳出。

那麼上述線性代碼就可以生成為下面的偽代碼：

// register usage: // rbp: frame pointer // rsp: stack pointer // arguments: rdi, rsi, rdx, rcx // temporary register: rax // return: rax


  // function prologue: frame setup

  push rbp          // save old fp

  rbp = rsp         // set up new fp

  rsp -= 56         // allocate new stack frame: 7 slots * 8 bytes per slot

  // spill incoming arguments from registers to stack

  [rbp - 8]  = rdi  // spill a

  [rbp - 16] = rsi  // spill b

  [rbp - 24] = rdx  // spill c

  [rbp - 32] = rcx  // spill d
  // expression tree for:

  //  int e = a * b + c * d;
  // _t0 = a * b

  eax = [rbp - 8]   // load a into temp register

  eax *= [rbp - 16] // load b and multiply to temp register

  [rbp - 48] = eax  // store temp to stack _t0
  // _t1 = c * d

  eax = [rbp - 24]  // load c into temp register

  eax *= [rbp - 32] // load d and multiply to temp register

  [rbp - 56] = eax  // store temp to stack: _t1
  // e = _t0 + _t1

  eax = [rbp - 48]  // load _t0 into temp register

  eax += [rbp - 56] // load _t1 and add to temp register

  [rbp - 40] = eax  // store temp to stack: e
  // expression tree for:

  //   return e + d;
  // _t0 = e + d

  eax = [rbp - 40]  // load e into temp register

  eax += [rbp - 32] // load d and add to temp register

  [rbp - 48] = eax  // store temp to stack: _t0
  // return _t0

  eax = [rbp - 48]  // load _t0 into return register

// function epilogue: tear down frame rsp = rbp // deallocate stack frame pop rbp // restore old frame pointer return

這樣我們就可以完全不關心寄存器分配的問題，只要計算好棧幀布局，把參數、局部變數和臨時值都放進去，就完事了。

當然，上面生成的代碼有些冗餘，其中部分可以通過窺孔優化（peephole optimization）來消除。

例如說我們特意選擇使用RAX作為臨時寄存器，而它同時也是返回值寄存器。所以在return _t0的時候，我們知道RAX其實還持有_t0的值，所以最後返回前的那個拷貝（eax = _t0）就可以消除掉。

上面例子所使用的思路可以概括為「基於虛擬寄存器」：每個變數（包括參數、局部變數和臨時值）都看作一個「虛擬寄存器」。

虛擬寄存器映射到實際寄存器最簡單的辦法就是「不映射」——而是把每個虛擬寄存器都分配到棧幀上的一個slot里。外加把一個或多個實際寄存器固定分配為「臨時寄存器」，在做實際運算時把虛擬寄存器的內容從棧幀的stack slot里讀到臨時寄存器，在臨時寄存器上完成運算，然後再把結果保存回到棧幀上的虛擬寄存器里，代碼生成完成了。

========================================================

自然的，既然我們都用上「虛擬寄存器」這個詞了，為何不把它們（至少其中一些）映射到實際寄存器上呢？

這就衍生出一種非常簡單的寄存器分配策略：把臨時變數分配到實際寄存器上。這裡的假設是：表達式求值是頻繁的操作，其中間結果應該盡量停留在實際寄存器里，這樣就已經能提升代碼性能了。

上文已經提到，從表達式樹生成出來的臨時變數的生命期僅限於表達式樹內；它們可以在語句間復用。所以這種分配思路就是一種在表達式樹層面上做的寄存器分配。

這種思路下最簡單的分配策略就是挑選若干個實際寄存器，把臨時變數的頭幾個固定映射到這些寄存器上。

假如我們用以下的固定映射：

_t0 =&> rcx _t1 =&> rdi _t2 =&> rsi ...

並且還是保留RAX作為臨時寄存器，那麼前面例子中的int e = a * b + c * d;就可以生成為：

// _t0 = a * b eax = [rbp - 8] // load a into temp register eax *= [rbp - 16] // load b and multiply to temp register ecx = eax // move temp to _t0


  // _t1 = c * d

  eax = [rbp - 24]  // load c into temp register

  eax *= [rbp - 32] // load d and multiply to temp register

  edi = eax         // move temp to _t1

// e = _t0 + _t1 eax = ecx // move _t0 into temp register eax += edi // add _t1 to temp register [rbp - 40] = eax // store temp to stack: e

可以看到：

之前把虛擬寄存器完全映射到棧上時，這棵表達式樹有6次內存讀，3次內存寫，0次寄存器間移動（register shuffling）；
而把臨時變數映射到固定寄存器上之後，就只有4次內存讀，1次內存寫，3次寄存器間移動了。

這樣性能就已經比把虛擬寄存器完全映射到棧幀上要好了。

把上面的foo()例子交給GCC 4.9.2做-O0編譯，得到的代碼是（Intel語法）：

// stack frame layout: // -32 [ spilled d ] // -28 [ spilled c ] // -24 [ spilled b ] // -20 [ spilled a ] // ... // -4 [ local e ] // fp -&> +0 [ old fp ] // +8 [ return address]


foo(int, int, int, int):

  // function prologue: setup frame

  push	rbp

  mov	rbp, rsp

  // spill incoming arguments onto stack

  mov	DWORD PTR [rbp-20], edi // a

  mov	DWORD PTR [rbp-24], esi // b

  mov	DWORD PTR [rbp-28], edx // c

  mov	DWORD PTR [rbp-32], ecx // d
  // expression tree for:

  //  int e = a * b + c * d;
  // _t0 = a * b

  mov	eax, DWORD PTR [rbp-20]

  imul	eax, DWORD PTR [rbp-24]

  mov	edx, eax
  // _t1 = c * d

  mov	eax, DWORD PTR [rbp-28]

  imul	eax, DWORD PTR [rbp-32]
  // e = _t0 + _t1

  add	eax, edx

  mov	DWORD PTR [rbp-4], eax
  // expression tree for:

  //   return e + d;
  // _t0 = e + d

  mov	edx, DWORD PTR [rbp-4]  // e

  mov	eax, DWORD PTR [rbp-32] // d

  add	eax, edx

// function epilogue: tear down frame pop rbp ret

跟上述的簡單映射方式得到的代碼質量也差不多了。

只看int e = a * b + c * d;的部分，GCC在-O0生成的代碼用了4次內存讀，1次內存寫，1次寄存器間移動，略好於上面的簡單映射法。

讀到這裡，如果再去看另一個問題應該就不會覺得陌生了：Visual C++ 6以debug模式編譯很拙笨，為何要做無用功？ - RednaxelaFX 的回答

========================================================

在「基於虛擬寄存器」+「固定映射臨時變數」的基礎上，還可以進一步做一些改進：

儘可能把可用的實際寄存器都映射給臨時變數；
如果在一個基本塊里，臨時變數並沒有消耗完所有可用的實際寄存器，那麼可以把一些局部變數也映射到寄存器上。映射策略可以用「先到先得、輪詢分配」，也可以用「使用頻度高者優先」，等等；
上一點可以進一步擴展到整個函數里；
…

再要往上提高性能，如果繼續沿著這種小補小改的做法走下去就可能會代碼越來越混亂，夾雜著各種隨意（ad-hoc）的局部小優化。所以再要繼續下去還是轉用本文開頭說的那些正統演算法比較好。

========================================================

既然提到了「基於虛擬寄存器」的思路，接下來就該說說與其相對的另一種思路：「基於（表達式）棧」。

所謂「表達式棧」就是用來存放表達式臨時值的地方。「基於虛擬寄存器」的做法是給每個臨時值都賦予一個「臨時變數」的名字；而「基於表達式棧」則不賦予「臨時變數」的名，總是通過棧來隱式操作臨時值。

在這種思路下，我們還是可以把參數和局部變數都固定放在棧幀上，然後在棧幀里找塊地方當作「表達式棧」來用。

JVM以及不少高級語言虛擬機的位元組碼設計就是照這個思路走的。

以JVM位元組碼為例，它就是把局部變數和表達式臨時值都放在棧幀里；其中局部變數放在棧幀的局部變數區（local variable area）里，而表達式臨時值則放在棧幀的「操作數棧」（operand stack）或者叫「表達式棧」（expression stack）里。

要看圖解的話，請參考我之前做的一份講義，從第76頁開始的部分。

關於Java源碼與JVM位元組碼的對應關係，我在另一個回答里舉過些例子：如何理解ByteCode、IL、彙編等底層語言與上層語言的對應關係？ - RednaxelaFX 的回答

繼續用前面的代碼來舉例，我們可以看看這種思路的最基本實現是怎樣的。

首先，把後序遍歷表達式樹的結果從下面的線性代碼來表示。這其實就是逆波蘭記法（Reverse-Polish Notation）。

注釋里是完成該語句後表達式棧里的內容，右邊表示棧頂：

// expression stack: // [ ]


// int e = a * b + c * d;
load a             // [ a ]

load b             // [ a, b ]

mul                // [ _t0 ]      // _t0 = a * b
load c             // [ _t0, c ]

load d             // [ _t0, c, d ]

mul                // [ _t0, _t1 ] // _t1 = c * d
add                // [ _t2 ]      // _t2 = _t0 + _t1
store e            // [ ]          // e = _t2
// return e + d;

load e // [ e ] load d // [ e, d ] add // [ _t0 ] // _t0 = e + d return // [ ] // return _t0

清楚可見語句之間表達式棧會是空的。這個例子里表達式棧最大深度為3。

表達式棧比起虛擬寄存器有個有趣的好處：前者明確的表達了臨時值的生命期有多長——還在表達式棧上的臨時值就是活的，離開了表達式棧就死掉了；後者則沒有把這種信息直接表達出來，如果要知道臨時值的生命期還得另外計算和記錄。

然後讓我們用最簡單的方式生成代碼。先是計算棧幀布局，跟之前的做法類似：

// 4 spill slots, 1 local slot, max operand stack depth 3

然後用RAX和RDX作為固定的臨時寄存器，按照Linux x86-64 ABI生成出來的代碼就是（偽代碼）：

// register usage: // rbp: frame pointer // rsp: stack pointer // arguments: rdi, rsi, rdx, rcx // temporary register: rax, rdx // return: rax


  // function prologue: frame setup

  push rbp          // save old fp

  rbp = rsp         // set up new fp

  rsp -= 40         // allocate new stack frame: 5 slots * 8 bytes per slot

  // spill incoming arguments from registers to stack

  [rbp - 8]  = rdi  // spill a

  [rbp - 16] = rsi  // spill b

  [rbp - 24] = rdx  // spill c

  [rbp - 32] = rcx  // spill d
  // expression tree for:

  //  int e = a * b + c * d;
  // load a

  push [rbp - 8]    // push a onto expression stack
  // load b

  push [rbp - 16]   // push b onto expression stack
  // mul

  pop rdx           // pop rhs to temp register rdx

  pop rax           // pop lhs to temp register rax

  eax *= edx        // do mul

  push rax          // push result onto expression stack
  // load c

  push [rbp - 24]   // push c onto expression stack
  // load d

  push [rbp - 32]   // push d onto expression stack
  // mul

  pop rdx           // pop rhs to temp register rdx

  pop rax           // pop lhs to temp register rax

  eax *= edx        // do mul

  push rax          // push result onto expression stack
  // add

  pop rdx           // pop rhs to temp register rdx

  pop rax           // pop lhs to temp register rax

  eax += edx        // do add

  push rax          // push result onto expression stack
  // store e

  pop [rbp - 40]    // pop top of expression stack to e
  // expression tree for:

  //   return e + d;
  // load e

  push [rbp - 24]   // push c onto expression stack
  // load d

  push [rbp - 32]   // push d onto expression stack
  // add

  pop rdx           // pop rhs to temp register rdx

  pop rax           // pop lhs to temp register rax

  eax *= edx        // do add

  push rax          // push result onto expression stack
  // return

  pop rax           // pop top of expression stack to return register

// function epilogue: tear down frame rsp = rbp // deallocate stack frame pop rbp // restore old frame pointer return

如果只看int e = a * b + c * d;的部分，這種做法用了10次內存讀，8次內存寫，0次寄存器間移動。push mem是1讀1寫，push reg是1寫，pop mem是1讀1寫，pop reg是1讀。

…看起來有點糟糕？比之前「基於虛擬寄存器」的做法糟糕多了？

這裡顯得很糟糕是因為x86的運算指令本質上還是傾向於使用寄存器的，不接受兩個操作數都是內存操作數的形式，更沒有內建的指令能直接把棧頂兩個數彈出-&>做運算-&>壓回棧頂，所以這裡需要用臨時寄存器來模擬一下，看起來就「糟糕」了。

另外我上面生成的代碼嚴格保持了操作數的順序。如果應用上整數的加法和乘法滿足交換律，就可以把運算部分的代碼略微簡化。例如add的部分就可以變成：

// add pop rax // pop rhs to temp register rax [rsp + 0] += eax // load lhs, do add, and store back to stack top

但是從內存讀寫次數看這跟原先的版本沒任何區別。

別著急，接下來稍做改進就好了。

========================================================

在最原始的「基於表達式棧」的基礎上有兩個變種，都是利用「棧頂緩存」（top-of-stack caching，簡稱stack-caching，或者TOSCA——Top-Of-Stack-CAching）的思路：

單狀態棧頂緩存（1-top-of-stack caching，簡稱1-TOSCA）
多狀態棧頂緩存（n-top-of-stack caching，簡稱n-TOSCA）

先看單狀態棧頂緩存。這個思路是：總是把表達式棧的棧頂值放在一個實際寄存器里；如果表達式棧有多於一個值，則其餘部分分配在棧幀上。

假如把RAX用作緩存表達式棧頂值的寄存器，那麼上面的例子可以變成：（只看第一個語句的部分）

// expression tree for: // int e = a * b + c * d;


  // load a

  eax = [rbp - 8]   // push a onto expression stack
  // load b

  push rax

  eax = [rbp - 16]  // push b onto expression stack
  // mul

  pop rdx           // pop lhs to temp register rdx

  eax *= edx        // do mul
  // load c

  push rax

  eax = [rbp - 24]  // push c onto expression stack
  // load d

  push rax

  eax = [rbp - 32]  // push d onto expression stack
  // mul

  pop rdx           // pop lhs to temp register rdx

  eax *= edx        // do mul
  // add

  pop rdx           // pop lhs to temp register rdx

  eax += edx        // do add

// store e [rbp - 40] = eax // pop top of expression stack to stack: e

有沒有比原始版清爽多了？這個1-TOSCA版的int e = a * b * c * d;用了7次內存讀，4次內存寫，0次寄存器間移動，比原始版略有改進。

仔細看上面這段代碼，可以發現在原始版里每次要把一個值壓入表達式棧都是直接用push指令，而在這個版本里則是第一次（當表達式棧還是空的時候）壓入時直接move到RAX里，等到要壓入下一個值時才用push指令把當前在RAX里的值壓到在棧幀里的表達式棧，然後下一個值move到RAX里。這就是棧頂緩存的體現。

有不少簡單的編譯器都會選用這種設計，因為它簡單實用：基於表達式棧的代碼生成方式與表達式樹的後序遍歷可以輕鬆結合起來，實現簡單；而通過棧頂緩存又可以讓實際生成的代碼利用上（少量）寄存器，還算實用。

青木峰郎的編譯器書「ふつうのコンパイラをつくろう」所講述的C?（讀作C-flat）編譯器用的就是這種1-TOSCA設計。

斯坦福的編譯器入門課（CS143）教的入門編譯器也是用1-TOSCA的設計。關於這個課請參考我另一個回答：斯坦福大學編譯原理課程質量怎麼樣？ - RednaxelaFX 的回答

這兩者都把緩存棧頂值的寄存器稱為「累加器」（accumulator）。在斯坦福編譯器課Coursera版的11-06第7頁開始的地方提到了top-of-stack caching，並提到1-TOSCA的那個緩存用寄存器叫做累加器。

歷史上確實存在過「累加器計算機」，這裡說的「累加器」可以說是從那種老式機器傳承下來的叫法。有趣的是，x86家族裡AX系列寄存器（AX / EAX / RAX）的「A」就是累加器的意思，暗示著這個寄存器原本的設計用途。

我的一個老帖里提到過累加器式的指令集與基於寄存器/基於棧的指令集之間的關係：虛擬機隨談（一）：解釋器，樹遍歷解釋器，基於棧與基於寄存器，大雜燴

微軟為研究目的公開的Shared Source Common Language Infrastructure（SSCLI）裡帶的JIT編譯器，FJIT，也使用這種代碼生成方式。關於FJIT的血緣，請參考：JIT編譯器雜談#1：JIT編譯器的血緣（一） - 編程語言與高級語言虛擬機雜談（仮） - 知乎專欄

TOSCA在許多解釋器中也相當流行。HotSpot VM、Strongtalk VM家族都是用1-TOSCA的。

我在這裡之所以用「TOSCA」這種縮寫方式就是因為HotSpot VM的源碼里是這麼寫的。

以前寫過一個筆記對比了HotSpot VM與Dalvik VM的解釋器，前者是用1-TOSCA方式實現基於表達式棧的指令集（JVM位元組碼），後者是用全部映射到棧幀上的方式實現基於虛擬寄存器的指令集（Dalvik位元組碼），如果拋去解釋器的固有開銷（fetch-dispatch），只看執行邏輯的話，其實兩者差不了多少：A code snippet to show some relationship between JVM/HotSpot"s and Dalvik"s interpreter

========================================================

多狀態棧頂緩存有幾種不同的做法。讓我們就前面的例子看看3-TOSCA的版本可以是怎樣的。

假設我們用的變種是這樣的：

表達式棧深度為0時：壓棧 =&> 移至RAX，到達深度為1狀態

表達式棧深度為1時：壓棧 =&> 移至RDX，到達深度為2狀態

表達式棧深度為2時：壓棧 =&> 移至RCX，到達深度為3狀態

後面的狀態因為例子用不到所以留給大家作為課後作業 &>_&<

使用這種代碼生成策略，再來看int e = a * b + c * d;的例子：

// expression tree for: // int e = a * b + c * d;


  // load a

  eax = [rbp - 8]   // push a onto expression stack
  // load b

  edx = [rbp - 16]  // push b onto expression stack
  // mul

  eax *= edx        // do mul
  // load c

  edx = [rbp - 24]  // push c onto expression stack
  // load d

  ecx = [rbp - 32]  // push d onto expression stack
  // mul

  edx *= ecx        // do mul
  // add

  eax += edx        // do add

// store e [rbp - 40] = eax // pop top of expression stack to stack: e

這樣就只有4次內存讀，1次內存寫，0次寄存器間移動，效果就跟GCC -O0差不多了，比上文提到的「基於虛擬寄存器」+「固定映射臨時變數」還要好。

可見，通過利用寄存器做棧頂緩存，從一個原本「基於表達式棧」的中間表示完全可以直接生成出利用實際寄存器的代碼。上面的3-TOSCA例子生成的代碼完全沒用到x86的push/pop指令，純利用寄存器就完成了運算。

n-TOSCA其實就是一種非常簡單實用的、適用於後序遍歷表達式樹的寄存器分配思路。

像是說早期的JVM JIT編譯器之一，shuJIT就用了n-TOSCA的思路來分配寄存器。

Jikes RVM、Harmony里也有應用。

V8的初級編譯器full code generator採用的寄存器分配策略也是衍生自n-TOSCA。

關於棧頂緩存，放個傳送門：關於虛擬機里的stack caching（棧頂緩存）的隨筆

========================================================

（…待續…）

Strahler number

Sethi–Ullman演算法

如R大所說，基於局部的分配加上很多細小的啟發式改進，最終得到的性能並不會很高，而且更重要的是代碼結構很混亂。

一、概述

目前主流的編譯器，如：HotSpot VM 的C1，C2編譯器，llvm，gcc等，主要應用的就是3種全局式的分配演算法，或多種思想的融合，而不是單純的某種演算法。

圖著色（http://www.ics.uci.edu/~guoqingx/courses/142b/winter13/resource/register_allocation_via_coloring.pdf和改進版本http://web.eecs.umich.edu/~mahlke/courses/583f12/reading/chaitin82.pdf）。
線性掃描（https://www.seas.gwu.edu/~hchoi/teaching/cs160d/linearscan.pdf）。
Second chance binpacking演算法（http://www.eecs.harvard.edu/machsuif/publications/otraub-thesis.pdf），該演算法也是一種線性掃描的思想，主要思想就是對活躍區間(Interval)進行分割，一部分在寄存器中，另外一部分在棧槽(Stack slot)中。這種改進能夠有效的提高面向CISC指令集的CPU的寄存器分配。

我對圖著色演算法不怎麼熟悉，就僅僅介紹基本的線性掃描演算法及其改進。

二、起源

學術界從上世紀60年代就開始研究寄存器分配的問題了，在線性掃描寄存器分配之前，都是圖著色演算法(graph coloring)的天下。由該演算法生成的代碼的質量非常的高，有一個問題就是，它是迭代式的，下面是它的流程

從上面可以看出來，為了達到高質量的生成代碼的目的，是一種循環的處理方式，這是一個非常耗費時間的過程。但是，在現代虛擬機的即時編譯器(Just in Time Compiler)中，需要在較短的時間內生成相對質量高的代碼。所以，我們只能投向於線性掃描了，從名字上面可以看出來，它是一種線性的演算法，單趟遍歷每個活躍區間(Interval)，為其分配物理寄存器。所以，時間複雜度低的多（相對於圖著色的 $O(n^{4} )$ ），並且生成代碼的質量也也能接受。三、線性掃描寄存器分配

原始的Poletto等人的論文中，是對變數（虛擬寄存器VR）的活躍區間(Interval)為單位進行分配的，每個活躍區間表示某個VR在代碼中的使用範圍[a, b]，表示該VR在這個區間中使用了。所以，該演算法的第一步就是為每個VR計算出它的Interval。詳細演算法如下：

將控制流圖CFG線性化並對每條指令編號。利用的演算法可以見Wimmer的Linear Scan Register Allocation
for the Java HotSpot? Client Compiler （http://www.ssw.uni-linz.ac.at/Research/Papers/Wimmer04Master/Wimmer04Master.pdf）。
遍歷上述得到的線性化的基本塊列表，為每個VR計算活躍區間。當然，這一步使用了傳統的數據流演算法——Liveness analysis計算得到每個基本塊的LiveIn和LiveOut。演算法如下：
然後，在使用迭代式的Liveness analysis演算法最終計算出每個基本塊的LiveOut和LiveIn。
從後往前遍歷第1步建立的線性鏈表，計算Interval。注意，下面的圖是我從Linear Scan Register Allocation for the Java HotSpot? Client Compiler 論文中截圖過來的，所以肯定比原始的論文細緻，更具體化，放在此處只是為了說明原理。找不到其他好的圖了～_～。
根據第3步建立的interval列表，我們就可以進行寄存器分配了。注意：此處引入了兩個集合，用於寄存器分配，1個是unhandled List，表示還未被分配寄存器的活躍區間，其中的interval都按照開始位置遞增的方式進行排序；2是active list表示已經分配了寄存器的活躍區間的集合，其中的interval都按照結束位置遞增的方式進行排序。配圖來自於論文https://www.seas.gwu.edu/~hchoi/teaching/cs160d/linearscan.pdf。
首先遍歷unhandled 列表中的interval，依次為其分配寄存器。首先，一次遍歷active列表，判斷在當前interval的開始位置是否存在已經結束了的Interval，如果有，則將其逐出，將分配給它的寄存器回收，用於後續的分配。然後，判斷當前可用的寄存器數目是否為0，如果沒有的話，執行splitAtInterval(i)方法，從active列表的最後一個interval和當前interval選擇一個interval，將其溢出到stack slot中，選擇的方法就是看誰的結束位置更遲，該場景下也就是誰的結束位置更大。如果是當前interval被逐出，只需要為其分配一個stack slot即可；否則把分配給active列表中的Interval的寄存器分配給current interval，並溢出其至stack slot。

四、例子

如下圖片都來自於論文Linear Scan Register Allocation on SSA Form（http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.162.2590rep=rep1type=pdf），原始論文中並沒有好的例子，該論文是基於HotSpot C1編譯器的，利用了lifetime hole技術，是原始論文的改進版，有些複雜，但並不影響理解原始論文中的思想。

利用上面的演算法建立的interval圖為（目前可以忽略每個interval之間的空隙，比如：i12中的32~36，原始的論文中沒有採用lifetime hole技術，所以得到的一定是沒有空隙的活躍區間[20, ~)）：

然後，我就可以依次未他們分配寄存器了。假設當前只有三個寄存器，R1，R2，R3。

i10可以分配為R1， i11分配為R2，i12分配為R3，然後，i13可以重複使用i11的寄存器——R2了，因為i11已經結束。

此時，處理i14，active = {i10, i12, i13}。unhandled = {i14, i15}， current = i14。因為目前沒有在i14開始位置之前已經結束的interval。所以，採用溢出演算法，選擇i10溢出到stack slot，將i10佔有的R1寄存器分配給i14。

此時，active = {i12, i13, i14}, current = i15, unhandled = {i15}。和處理i14的時候一樣，溢出i12到stack slot，重新分配R3給i15。

分配結束。

五、利用活躍區間中的間隙的改進

重新考慮第四節中的處理過程，在原始的論文中，我們溢出了兩次i10和i12，那麼相應的就有4次store和load處理，也就是訪存，這會極大的影響代碼的質量。

如果我們能夠充分利用單個活躍區間中的lifetime hole，那麼我能有效的減少溢出次數，也就是降低訪存次數。

重新考慮下圖：

假設還是只有三個寄存器R1, R2, R3。

開始的時候，unhandled = {i10, i11, i12, i13, i14, i15}。active = {}。

current = i10：分配R1給它， unhandled = {i11, i12, i13, i14, i15}, active = {i10}；

current = i11：分配R2給它， unhandled = {i12, i13, i14, i15}, active = {i10, i11}；

current = i12：分配R3給它，unhandled = {i13, i14, i15}, active = {i10, i11, i12}；

current = i13：此時，i11已經結束了，可以把R2回收，並分配給i13，unhandled = { i14, i15}, active = {i10，i12， i13}；

current = i14： i14可以放在i12的空隙中，則i14可以分配為R3；

current = i15： i15可以分配在i13的空隙中，則i15可以分配為R2；

至此，分配結束，我們可以看出來，充分利用lifetime hole可以有效的降低活躍區間溢出和訪存操作。

六、利用區間分割的改進

還有一種改進的思想來源於論文quality and speed in linear scan register allocation (http://www.eecs.harvard.edu/machsuif/publications/otraub-thesis.pdf)，該方法的思想就是，儘可能的把interval放在寄存器中，哪怕是interval的一部分也可以。即一部分放在寄存器，另外一部分放在stack slot中，具體的演算法細節請看Linear Scan Register Allocation
for the Java HotSpot? Client Compiler(http://www.ssw.uni-linz.ac.at/Research/Papers/Wimmer04Master/Wimmer04Master.pdf)，Optimized Interval Splitting
in a Linear Scan Register Allocator（https://www.usenix.org/legacy/events/vee05/full_papers/p132-wimmer.pdf）。

七、面向SSA形式的線性掃描寄存器分配

該演算法是目前編譯器應用的熱點，很多研究用的編譯器項目在嘗試將linear scan 應用到SSA形式(Static single assignment form)的IR。

SSA形式的線性掃描的主體與上述類似，SSA帶來的優點就是能有效的降低單個interval的長度，這在CISC指令集計算機中會非常有效。同時，充分利用SSA形式的IR的稀疏特性，避免迭代式的liveness analysis。有效的降低時間複雜度。

見論文Linear Scan Register Allocation on SSA Form（http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.162.2590rep=rep1type=pdf）。

------------未完待續--------------------

Poletto 的 Linear Scan 是較為簡單有效的：http://www.cs.ucla.edu/~palsberg/course/cs132/linearscan.pdf

我有一個玩具編譯器用的是這個方法。overminder/YAC · GitHub

Chaitin / Briggs 的 Graph Coloring 效果較好，不過編譯速度較慢：（Chaitin 那篇要錢，而我已經不是學生了..）http://www.cs.utexas.edu/users/mckinley/380C/lecs/briggs-thesis-1992.pdf

我的另一個玩具編譯器用的是這個方法。overminder/CaLang · GitHub

總之就是硬著頭皮實現就是，難道還能難過鄭紹榮的演算法課嗎

最簡單的不考慮性能的話，可以參考llvm的fast分配

即需要寄存器就分配一個不夠就溢出

有一定性能需求可以考慮linear scan

再然後可以考慮graph coloring

趁著這個問題來發一段看垠神的Register Allocation By Model Transformer
Semantics的筆記。用的例子是R大( @RednaxelaFX )回答里的例子。

一、 backward markdeath f(a,b,c,d){ t0 = a * b; {a,b} t1 = c * d; {c} e = t0 + t1; {t1} t0 = e + d; {e,d} return t0; {t0} }


二、

forward generate
model = (frame,regs)

frame = [rbp - 8n] ...

regs = eax : 空 , ecx : 空 , edx : 空 ...
f(a,b,c,d){

/*

[rbp - 8] ：a

[rbp - 16] : b

[rbp - 24] : c

[rbp - 32] : d

 eax : 空 , ecx : 空 , edx ：空 ...

*/

//論文里是先把a,b,c,d load到寄存器里，不過好像是在frame上就行

	t0 = a * b;  {a,b}

	/*

	1,find oprand in regs,if it fails,find them in frame and load to available regs

	//genCode(eax = [rbp - 8]) 	//load eax a

	//genCode(ebx = [rbp - 16]) 	//load eax b
	model after step 1

[rbp - 8] ：a

[rbp - 16] : b

[rbp - 24] : c

[rbp - 32] : d

 eax : a , ecx : b , edx ：空 ...

	2,allocate right hand side : a*b becomes eax * ebx

	3,Kill dead varables {a,b} ,wipe them in both frame and regs

[rbp - 8] ：空

[rbp - 16] : 空

[rbp - 24] : c

[rbp - 32] : d

eax : 空 , ecx : 空 , edx ：空 ...

	4，allocate left hand side eax : t0

	//genCode(eax = eax * ebx)

[rbp - 8] ：空

[rbp - 16] : 空

[rbp - 24] : c

[rbp - 32] : d

eax : t0 , ecx : 空 , edx ：空 ...
以下同理

	*/
	t1 = c * d;  {c}

	/*

	//looking up c and d in regs

	//not found in regs

	////looking up c and d in frame

	//genCode(ecx = [rbp - 24]) 	//load ecx c

	//genCode(edx = [rbp - 32]) 	//load edx d

	// c is killed here,ecx is available again

	// t1 reside in ecx now

	//genCode(ecx = ecx * edx)
[rbp - 8] ：空

[rbp - 16] : 空

[rbp - 24] : 空

[rbp - 32] : d

eax : t0 , ecx : t1 , edx ：d ...

	*/
	e = t0 + t1; {t1}

	/*

	//looking up t0 and t1

	// t1 is killed here,ecx is available again

	// e reside in ecx now

	//genCode(ecx = eax * edx)
[rbp - 8] ：空

[rbp - 16] : 空

[rbp - 24] : 空

[rbp - 32] : d

eax : t0 , ecx : e , edx ：d ...

	*/
	t0 = e + d;  {e,d}

	/*

	//looking up e and d

	//calculate ecx + edx which is e+d

	// e,d is killed here,ecx and edx are available again

	// t0 is at eax

	//genCode(eax = ecx + edx)
[rbp - 8] ：空

[rbp - 16] : 空

[rbp - 24] : 空

[rbp - 32] : 空

eax : t0 , ecx : 空 , edx ：空 ...

	*/

return t0; {t0} //return怎麼處理我不會 }

感覺垠神這個方法確實很犀利啊，另外這個方法用於if分支可能會出現寄存器分配不一致的問題，這時需要進行置換操作。保證在if分支之外。看到的分配一致。更多細節請看論文吧

http://arxiv.org/ftp/arxiv/papers/1202/1202.5539.pdf

這個例子看起來效果跟n-棧頂緩存類似，是因為我用了R大的例子。變數生存期正好是那個樣子。大家可以試試別的例子。

另外寄存器用完的話就把最不常用的占著寄存器的變數store到frame里，空個位置。再分配。

相當於把frame當作regs的緩存。挑選最不常用變數的方法是維護一個reg操作的LRU隊列。

就跟把內存頁換到硬碟swap區是一個道理。

跟表達式沒啥關係吧，應該是依賴圖的問題吧