線性掃描

接下來介紹一種不同思路的算法：線性掃描。算法描述如下[4]：

LinearScanRegisterAllocation:
	active := {}
	for i in live interval in order of increasing start point
		ExpireOldIntervals(i)
		if length(avtive) == R
			SpillAtInterval(i)
		else
			register[i] := a regsiter removed from pool of free registers
			add i to active, sorted by increasing end point
ExpireOldInterval(i)
	for interval j in active, in order of increaing end point
		if endpoint[j] >= startpoint[i]
			return
		remove j from active
		add register[j] to pool of free registers
SpillAtInterval(i)
	spill := last interval in active
	if endpoint[spill] > endpoint[i]
		register[i] := register[spill]
		location[spill] := new stack location
		remove spill from active
		add i to active, sorted by increasing end point
	else
		location[i] := new stack location

live interval其實就是變量的生命期，用活躍變量分析可以算出來。不過需要標(biāo)識第一次出現(xiàn)和最后一次出現(xiàn)的時間點。

舉個例子：

圖10

llvm中實現(xiàn)

在上文中介紹的算法都是作用在最普通的四元式上，但LLVM-IR是SSA形式，有PHI節(jié)點，但PHI節(jié)點沒有機(jī)器指令表示，所以在寄存器分配前需要把PHI節(jié)點干掉，消除PHI節(jié)點的算法限于篇幅不展開，如感興趣的話請后臺留言。

llvm作為工業(yè)級編譯器，有多種分配算法，可以通過llc的命令行選項-regalloc=pbqp|greedy|basic|fast來手動控制分配算法。

不同優(yōu)化等級默認(rèn)使用算法也不同：O2和O3默認(rèn)使用greedy，其他默認(rèn)使用fast。

fast算法的策略很簡單，掃描代碼并為出現(xiàn)的變量分配寄存器，寄存器不夠用就溢出到內(nèi)存。用途主要是 調(diào)試 。

basic算法以linearscan為基礎(chǔ)并對life interval設(shè)置了溢出權(quán)重而且用優(yōu)先隊列來存儲life interval。

greedy算法也使用優(yōu)先隊列，但特點是先為生命期長的變量分配寄存器，而短生命期的變量可以放在間隙中，詳情可以參考[5]。

pbqp算法全稱是Partitioned Boolean Quadratic Programming，限于篇幅，感興趣的讀者請查閱[6]。

至于具體實現(xiàn)，自頂向下依次是：

• TargetPassConfig::addMachinePasses含有寄存器分配和其他優(yōu)化
• addOptimizedRegAlloc中是與寄存器分配密切相關(guān)的pass，比如上文提到的消除PHI節(jié)點
• addRegAssignAndRewriteOptimized是實際的寄存器分配算法
• 寄存器分配相關(guān)文件在lib/CodeGen下的RegAllocBase.cpp、RegAllocGreedy.cpp、RegAllocFast.cpp、RegAllocBasic.cpp和RegAllocPBQP.cpp等。
• RegAllocBase類定義了一系列接口，重點是selectOrSplit和enqueue/dequeue方法，數(shù)據(jù)結(jié)構(gòu)的重點是priority queue。selectOrSplit方法可以類比上文中提到的SpillAtInterval。priority queue類比active list。簡要代碼如下：

void RegAllocBase::allocatePhysRegs() {
  // 1. virtual reg其實就是變量
  while (LiveInterval *VirtReg = dequeue()) {

    // 2.selectOrSplit 會返回一個可用的物理寄存器然后返回新的live intervals列表
    using VirtRegVec = SmallVector4>;
    VirtRegVec SplitVRegs;
    MCRegister AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs);
 // 3.分配失敗檢查
    if (AvailablePhysReg == ~0u) {
     ...
    }
 // 4.正式分配
    if (AvailablePhysReg)
      Matrix->assign(*VirtReg, AvailablePhysReg);
 
    for (Register Reg : SplitVRegs) {
      // 5.入隊分割后的liver interval
      LiveInterval *SplitVirtReg = &LIS->getInterval(Reg);
      enqueue(SplitVirtReg);
    }
  }
}

至于這四種算法的性能對比，我們主要考慮三個指標(biāo)：運行時間、編譯時間和溢出次數(shù)。

圖11 各算法的運行時間，圖源[6]

橫坐標(biāo)是測試集，縱坐標(biāo)是以秒為單位的運行時間

圖12 各算法的編譯時間，圖源[6]

橫坐標(biāo)是測試集，縱坐標(biāo)是編譯時間

圖13 各算法的溢出次數(shù)，圖源[6]

從這三幅圖可以看出greedy算法在大多數(shù)測試集上都優(yōu)于其他算法，因此greedy作為默認(rèn)分配器是可行的。

小結(jié)

我們通過一個例子介紹了活躍變量分析和圖著色算法。借助活躍變量分析，我們知道了變量的生命期，有了變量生命期建立干涉圖，對干涉圖進(jìn)行著色。如果著色失敗，可以選擇某個變量溢出到內(nèi)存中。之后在RIG的基礎(chǔ)上介紹了寄存器合并這一變換。

然后我們簡單介紹了不同思路的寄存器分配算法：linearscan。最后介紹了llvm12中算法的實現(xiàn)并對比了llvm中四種算法的性能差異。

參考

1. http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15745-s18/www/lectures/L5-Intro-to-Dataflow-pre-class.pdf
2. http://web.cecs.pdx.edu/~mperkows/temp/register-allocation.pdf
3. http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15745-s18/www/lectures/L12-Register-Allocation.pdf http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15745-s18/www/lectures/L13-Register-Coalescing.pdf
4. http://web.cs.ucla.edu/~palsberg/course/cs132/linearscan.pdf
5. http://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html
6. T. C. d. S. Xavier, G. S. Oliveira, E. D. d. Lima and A. F. d. Silva, "A Detailed Analysis of the LLVM's Register Allocators," 2012 31st International Conference of the Chilean Computer Science Society, 2012, pp. 190-198, doi: 10.1109/SCCC.2012.29.