線性掃描

接下來(lái)介紹一種不同思路的算法：線性掃描。算法描述如下[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其實(shí)就是變量的生命期，用活躍變量分析可以算出來(lái)。不過(guò)需要標(biāo)識(shí)第一次出現(xiàn)和最后一次出現(xiàn)的時(shí)間點(diǎn)。

舉個(gè)例子：

圖10

llvm中實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

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

    // 2.selectOrSplit 會(huì)返回一個(gè)可用的物理寄存器然后返回新的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.入隊(duì)分割后的liver interval
      LiveInterval *SplitVirtReg = &LIS->getInterval(Reg);
      enqueue(SplitVirtReg);
    }
  }
}

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

圖11 各算法的運(yùn)行時(shí)間，圖源[6]

橫坐標(biāo)是測(cè)試集，縱坐標(biāo)是以秒為單位的運(yùn)行時(shí)間

圖12 各算法的編譯時(shí)間，圖源[6]

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

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

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

小結(jié)

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

然后我們簡(jiǎn)單介紹了不同思路的寄存器分配算法：linearscan。最后介紹了llvm12中算法的實(shí)現(xiàn)并對(duì)比了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.