概念介紹

在介紹算法之前，我們回顧下基本概念：

• |X| ：X的度數(shù)，(無(wú)向圖中)節(jié)點(diǎn)的鄰居個(gè)數(shù)。
• CFG ：控制流圖。
• successor ：本文指CFG中基本塊的后繼。
• 四元式 ：(op,result,arg1,arg2)，比如常見的a=b+c就可以看作四元式(+,a,b,c)。
• SSA(Static Single Assignment) ：靜態(tài)單賦值。
• use/def ：舉個(gè)例子，對(duì)于指令n: c <- c+b來(lái)說(shuō) use[n]={c,b}，def[n]={c}。
• live-in ：當(dāng)以下任一條件滿足時(shí)，則稱變量a在節(jié)點(diǎn)n中是live-in的，寫作a∈in[n]。節(jié)點(diǎn)n本文中代表指令。

1. a∈use[n]；
2. 存在從節(jié)點(diǎn)n到其他節(jié)點(diǎn)的路徑使用了a且不包括a的def。

• live-out : 變量a在節(jié)點(diǎn)n的任一后繼的live-in集合中。寫作a∈out[n]
  
• 干涉 ：在某一時(shí)刻，兩個(gè)變量在同一live-in集合中。
• RIG(Register Interfere Graph) : 無(wú)向圖，其點(diǎn)集和邊集構(gòu)成如下：
• 節(jié)點(diǎn)：變量
• 邊：如果兩節(jié)點(diǎn)存在干涉，那么這兩節(jié)點(diǎn)之間就有一條干涉邊
• k-著色 ：給定無(wú)向圖G=(V,E)，其中V為頂點(diǎn)集合，E為邊集合。將V分為k個(gè)組，每組中沒有相鄰頂點(diǎn)，可稱該圖G是k著色的。當(dāng)然可著色前提下，k越小越好。

需要注意的是，我們后續(xù)的算法會(huì)作用在最普通的四元式上，而不是SSA。在介紹寄存器分配算法之前，我們需要活躍變量分析來(lái)構(gòu)建干涉圖。

活躍變量分析與圖著色算法

活躍變量分析

簡(jiǎn)單來(lái)說(shuō)，就是計(jì)算每個(gè)點(diǎn)上有哪些變量被使用。

算法描述如下[1]：

`input: CFG = (N, E, Entry, Exit)  
begin  
// init  
for each basic block B in CFG  
    in[B] = ?  
// iterate  
do{  
    for each basic block B other than Exit{  
        out[B] = ∪(in[s]),for all successors s of B  
        in[B] = use[B]∪(out[B]-def[B])  
    }  
}until all in[] do't change`

活躍變量分析還有孿生兄弟叫Reaching Definitions，不過(guò)實(shí)現(xiàn)功能類似，不再贅述。

舉個(gè)例子：對(duì)圖1的代碼進(jìn)行活躍變量分析

可以得到每個(gè)點(diǎn)的活躍變量如圖2所示：

過(guò)程呢？限于篇幅，僅僅計(jì)算第一輪指令1的結(jié)果，剩余部分讀者可自行計(jì)算。

可畫出RIG如圖3：

圖著色

經(jīng)過(guò)上文的活躍變量分析，我們得到了干涉圖，下一步對(duì)其進(jìn)行上色。

但是圖著色是一個(gè)NP問題，我們會(huì)采用啟發(fā)式算法對(duì)干涉圖進(jìn)行著色。基本思路是：

1. 找到度小于k的節(jié)點(diǎn);
2. 從圖中刪除;
3. 判斷是否為可著色的圖;
4. 迭代運(yùn)行前3步直到著色完成。

算法描述[3]：

`input: RIG, k  
// init  
stack = {}  
// iterate  
while RIG != {} {  
    t := pick a node with fewer than k neighbors from RIG // 這里RIG可以先按度數(shù)排序節(jié)點(diǎn)再返回  
    stack.push(t)  
    RIG.remove(t)  
}  
// coloring  
while stack != {} {  
    t := stack.pop()  
    t.color = a color different from t's assigned colored neighbors  
}`

對(duì)于例子1，假設(shè)有4個(gè)寄存器r1、r2、r3、r4可供分配。

寄存器分配

所以圖3中的RIG是4-著色的。但如果只有三種顏色可用，怎么辦呢？

沒關(guān)系，我們還有大容量的內(nèi)存，雖然速度慢了那么一點(diǎn)點(diǎn)。著色失敗就把變量放在內(nèi)存里，用的時(shí)候再取出來(lái)。

依然是上例，但是k=3，只有三個(gè)顏色。

如果f的鄰居是2-著色的就好了，但不是。那就只能選一個(gè)變量存入內(nèi)存了。這里我們選擇將變量f溢出至內(nèi)存。溢出后的IR和RIG如圖：

所以，溢出其實(shí)是分割了變量的生命周期以降低被溢出節(jié)點(diǎn)的鄰居數(shù)量。溢出后的著色圖如圖6：

這里溢出變量f并不是明智的選擇，關(guān)于如何優(yōu)化溢出變量讀者可自行查閱資料。

至此，圖著色算法基本介紹完畢。不過(guò)，如果代碼中的復(fù)制指令，應(yīng)該怎么處理呢？

寄存器分配之前會(huì)有Copy Propagation和Dead Code Elimination優(yōu)化掉部分復(fù)制指令，但是兩者并不是全能的。

比如：代碼段1中，我們可以合并Y和X。但是代碼段2中Copy Propagation就無(wú)能為力了，因?yàn)榉种?huì)導(dǎo)致不同的Y值。

`// 代碼段1  
X = ...  
A = 10  
Y = X  
Z = Y + A  
return Z  
  
// 代碼段2  
X= A + B  
Y = C  
if (...) {Y = X}  
Z = Y + 4`

所以，寄存器分配算法也需要對(duì)復(fù)制指令進(jìn)行處理。如何處理？給復(fù)制指令的源和目標(biāo)分配同一寄存器。

那么如何在RIG中表示呢？如果把復(fù)制指令的源和目標(biāo)看作 RIG中相同的節(jié)點(diǎn) ，自然會(huì)分配同一寄存器。

• 相同節(jié)點(diǎn)？可以擴(kuò)展RIG：新增虛線邊，代表合并候選人。
• 成為合并候選人的條件是：如果X和Y的生命周期不重合，那么對(duì)于Y=X指令中的X和Y是可合并的。
• 為了保證合并合法且不造成溢出：合并后局部的度數(shù)

那么如何計(jì)算局部的度數(shù)？介紹三種算法：

• 簡(jiǎn)單算法
• Brigg's 算法
• George's 算法

1. 簡(jiǎn)單算法：(|X|+|Y|)，很保守的算法但是可能會(huì)錯(cuò)過(guò)一些場(chǎng)景
比如k=2時(shí)，圖7應(yīng)用簡(jiǎn)單算法是沒辦法合并的
   

`

圖7\\[3\\]

但明顯圖7可以合并成圖8：


圖8\\[3\\]

2. Brigg's 算法：X和Y可合并，如果X和Y中度數(shù)≥k的鄰居個(gè)數(shù)＜k。但是如果X的度數(shù)很大，算法效率就不高

3. George's算法：X和Y可合并，如果對(duì)Y的每個(gè)鄰居T，|T| ?比如k=2時(shí)，圖9就可以合并X和Y。或者t和x沖突。
   

相對(duì)于Brigg算法、George算法不用遍歷節(jié)點(diǎn)的鄰居。注意，圖著色時(shí)可以按節(jié)點(diǎn)度數(shù)從小到大依次訪問。

到此，圖著色算法介紹完畢。

線性掃描

接下來(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è)例子：

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

在上文中介紹的算法都是作用在最普通的四元式上，但LLVM-IR是SSA形式，有PHI節(jié)點(diǎn)，但PHI節(jié)點(diǎn)沒有機(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ù)。

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

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

從這三幅圖可以看出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中四種算法的性能差異。