概念介紹

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

• |X|：X的度數(shù)，(無向圖中)節(jié)點的鄰居個數(shù)。

• CFG：控制流圖。

• successor：本文指CFG中基本塊的后繼。

• 四元式：(op,result,arg1,arg2)，比如常見的a=b+c就可以看作四元式(+,a,b,c)。

• SSA(Static Single Assignment)：靜態(tài)單賦值。

• use/def：舉個例子，對于指令n: c <- c+b來說 use[n]={c,b}，def[n]={c}。

• live-in：當以下任一條件滿足時，則稱變量a在節(jié)點n中是live-in的，寫作a∈in[n]。節(jié)點n本文中代表指令。

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

• live-out: 變量a在節(jié)點n的任一后繼的live-in集合中。寫作a∈out[n]

• 干涉：在某一時刻，兩個變量在同一live-in集合中。

• RIG(Register Interfere Graph): 無向圖，其點集和邊集構成如下：

• 節(jié)點：變量
• 邊：如果兩節(jié)點存在干涉，那么這兩節(jié)點之間就有一條干涉邊

• k-著色：給定無向圖G=(V,E)，其中V為頂點集合，E為邊集合。將V分為k個組，每組中沒有相鄰頂點，可稱該圖G是k著色的。當然可著色前提下，k越小越好。

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

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

活躍變量分析

簡單來說，就是計算每個點上有哪些變量被使用。

算法描述如下[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，不過實現(xiàn)功能類似，不再贅述。

舉個例子：對圖1的代碼進行活躍變量分析

圖1[2]

可以得到每個點的活躍變量如圖2所示：

過程呢？限于篇幅，僅僅計算第一輪指令1的結果，剩余部分讀者可自行計算。

可畫出RIG如圖3：

圖3

圖著色

經過上文的活躍變量分析，我們得到了干涉圖，下一步對其進行上色。

但是圖著色是一個NP問題，我們會采用啟發(fā)式算法對干涉圖進行著色?；舅悸肥牵?/p>

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

算法描述[3]：

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

對于例子1，假設有4個寄存器r1、r2、r3、r4可供分配。

步驟	stack	RIG
0	{}
1	{a}
2	{d,a}
3	{c,d,a}
4	{b,c,d,a}
5	{e,b,c,d,a}
6	{f,e,b,c,d,a}

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

沒關系，我們還有大容量的內存，雖然速度慢了那么一點點。著色失敗就把變量放在內存里，用的時候再取出來。

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

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

圖4 溢出后的IR

圖5 溢出后的RIG

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

圖6著色后的圖5

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

至此，圖著色算法基本介紹完畢。不過，如果代碼中的復制指令，應該怎么處理呢？

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

比如：代碼段1中，我們可以合并Y和X。但是代碼段2中Copy Propagation就無能為力了，因為分支會導致不同的Y值。

// 代碼段1
X = ...
A = 10
Y = X
Z = Y + A
return Z

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

所以，寄存器分配算法也需要對復制指令進行處理。如何處理？給復制指令的源和目標分配同一寄存器。

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

• 相同節(jié)點？可以擴展RIG：新增虛線邊，代表合并候選人。

• 成為合并候選人的條件是：如果X和Y的生命周期不重合，那么對于Y=X指令中的X和Y是可合并的。

• 為了保證合并合法且不造成溢出：合并后局部的度數(shù)

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

• 簡單算法
• Brigg's 算法
• George's 算法

1. 簡單算法：(|X|+|Y|)，很保守的算法但是可能會錯過一些場景

   比如k=2時，圖7應用簡單算法是沒辦法合并的

   

   圖7[3]

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

   

   圖8[3]

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

3. George's算法：X和Y可合并，如果對Y的每個鄰居T，|T|

   ?比如k=2時，圖9就可以合并X和Y。

   

   圖9[3]

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

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

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

voidRegAllocBase::allocatePhysRegs(){
//1.virtualreg其實就是變量
while(LiveInterval*VirtReg=dequeue()){

//2.selectOrSplit會返回一個可用的物理寄存器然后返回新的liveintervals列表
usingVirtRegVec=SmallVector4>;
VirtRegVecSplitVRegs;
MCRegisterAvailablePhysReg=selectOrSplit(*VirtReg,SplitVRegs);
//3.分配失敗檢查
if(AvailablePhysReg==~0u){
...
}
//4.正式分配
if(AvailablePhysReg)
Matrix->assign(*VirtReg,AvailablePhysReg);

for(RegisterReg:SplitVRegs){
//5.入隊分割后的liverinterval
LiveInterval*SplitVirtReg=&LIS->getInterval(Reg);
enqueue(SplitVirtReg);
}
}
}