|
前兩天又大概看了一下經(jīng)典的寄存器分配。 在編譯器的后端，指令選擇之后，需要進行寄存器的分配。經(jīng)典的寄存器分配算法是圖染色算法。這個算法大概是這樣的：首先，需要分析程序中的符號寄存器/值的活躍期；對于每一個值/活躍期都對應(yīng)與圖中的一個結(jié)點。在圖中，兩個結(jié)點之間存在邊表示這兩個結(jié)點代表的活躍期是有沖突的。也就是說，這兩個結(jié)點對應(yīng)的值在某些時刻是同時存在的。一個更加精確的定義是：如果結(jié)點A代表的活躍期被定義的時候，結(jié)點B代表的活躍期還沒有結(jié)束，那么A和B之間存在沖突。以上兩個定義事實上并不等價，定義二更加精確，定義一會引入一些本來不會沖突的“沖突”。 上面構(gòu)造的這個圖叫做沖突圖。下面，就是用K種顏色給這個沖突圖進行圖染色。如果K等于目標機器的物理寄存器的數(shù)目，并且這個圖可以被K種顏色染色，那么，我們將每一種顏色對應(yīng)一個物理寄存器，就得到了一個寄存器分配方案。 然而，圖染色問題是NP難的。 第一個用圖染色算法實現(xiàn)了全局寄存器分配的人是Chaintin，好像是IBM的一個家伙（呵呵，當年的IBM好牛呀）。他給出了一個算法。對于圖G，如果其中存在一個結(jié)點v，v的度小于k，那么，圖G可以被k染色，當且僅當G-v可以被k染色。這個定理很容易證明。 根據(jù)這個定理，首先在G中找一個度數(shù)小于k的結(jié)點v，將它從圖中刪去，同時刪去它的邊。不斷地重復這個過程。直到圖變成空圖或者圖中所有的結(jié)點的度數(shù)都大于k。 如果圖變成了空圖，我們就找到了一種G的k染色。只要按照刪除結(jié)點的相反的順序依次將結(jié)點染色就行了，染色的時候要保證，每一個結(jié)點的顏色和它的鄰居都不同（這一點可以做到，因為每一個被添加結(jié)點的度數(shù)都小于k，所以一定存在給它的顏色）。 如果圖沒有變成空圖，那么這個圖可能可以被K染色，可能不可以。一半采取的辦法就是，從圖中選擇一個活躍期，表記將要將它轉(zhuǎn)存到主存，并將它對應(yīng)的結(jié)點從圖中刪除。然后繼續(xù)下去。直到圖變成空圖。 如果在染色的時候發(fā)現(xiàn)，某個被表記的結(jié)點的確不能被染色，那就只好生成一些spill code將它存到主存了。選擇這種結(jié)點的啟發(fā)式規(guī)則一般是“spill代價/度數(shù)”最小的結(jié)點。也就是說，我們希望表記的結(jié)點spill時代價盡量小，同時刪掉它時，可以刪掉更多的邊。 最簡單的spill算法是這樣的：對于某個被選擇spill的活躍期，在其每一個定義之后插入一條store指令，在其每一個使用之前插入一個load指令。顯然，這個算法會插入大量的冗余的store和load。 Spilling的時候，Chaintin給出的一些啟發(fā)式規(guī)則來減少插入的代碼： 1、如果某個活躍期的使用，該活躍期對應(yīng)的值很容易計算，那么使用時就重新計算，而不要從主存載入； 2、如果一個活躍期的某個使用和其對應(yīng)的定義很“近”，那么這個使用不應(yīng)該從主存載入； 3、如果某個活躍期的相鄰兩個使用的距離很“近”，那么第二個使用不應(yīng)該重新載入； 4、如果某個活躍期的所有的使用都離定義很近，那么這個活躍期不應(yīng)該被spill。 其中，“近”的意思是指，同一活躍期的兩次引用之間沒有其它活躍期的終止。也就是說，兩次引用之間，沒有由于其它活躍期的終止而引入的額外的寄存器資源（這樣有些spill就不應(yīng)該進行，否則會引起進一步的spill）。 事實上，這些啟發(fā)式規(guī)則的確減少了一些冗余代碼，但還是有很多沒有被刪掉。 于是，就有人提出了interference region spill的概念。他指出，在原來的Spill方法中，一個生存期要么完全沒有spill，要么完全spill了。而事實上，對于沖突的生存期，只要spill沖突的那一部分就行了。例如，A和B沖突，A覆蓋的范圍是1到5,B覆蓋的范圍是3到7,并且我們選擇spill B。事實上，沒有必要給B的每一個定義之后插入store，每一個使用之前插入load。真正沖突的區(qū)域只有3到5.對于B的定義，如果該定義可以大刀3-5的區(qū)域內(nèi)，才需要插入store，否則不用，并且，對于B的使用，如果在3-5的區(qū)域內(nèi)，之前才用插入一條load，如果在5之后，我們只要在5之后的某個地方插入一條load，將B重新load回寄存器，后面所有的使用，都不必再插入load了。當然，并不是所有的情況下，IR都要比完全spill的效果好。所以，實現(xiàn)的時候，通常會看看這兩種策略那個更好，就采用那個。這樣實現(xiàn)的spill動態(tài)spill code會平均降低33.6%，最多的降低了70%多。 另外一個為了降低spill代價的策略是Split Live Range。就是將一個大的活躍期分裂成若干個小的活躍期。期望這些小的活躍期可以被分配到寄存器中。在這個策略中，作者首先討論了在什么情況下做這樣做會得到好處，從而引入了包含圖的概念。其實，在上面一種區(qū)域Spill的策略中，就是把一個大的活躍期分成若干個小的活躍期，沒有沖突的部分被當成一個活躍期分配到寄存器中。這里的作者指出，并不是所有的沖突都可以用這種方法得到好處的。有些沖突，即使將大的活躍區(qū)分裂了，得到的小的活躍期仍然會和原來沖突的活躍期沖突。如果，一個活躍期的使用或定義處，和它沖突的活躍期有效，那么，即便將前者分成了小的活躍期，包含那個使用或定義的小活躍期仍然和原來的活躍期沖突。如果這個時候寄存器是不夠的，那么寄存器仍然不夠。所以作者通過包含圖引入了完全包含的概念。A完全包含B，是指A的每一個定義都在B的每一個定義之前，A的活躍期長于B的活躍期，并且，在B的活躍期中沒有對A的使用。這樣，A就可以被分裂成兩個活躍期，一個在B之前，一個在B之后。具體的方法是，在A的每一個定義之后，B的定義之前插入一條store，在B的生存期結(jié)束之后插入一個load。同樣，并不是每一種情況使用split都有利。它的實現(xiàn)可以達到的效果和IR類似。 在優(yōu)化編譯器中，寄存器分配應(yīng)該是一個比較重要的部分。但是，圖染色是NP難的問題，我們就需要一些啟發(fā)式的規(guī)則來解這個問題。而當圖染色不能成功的時候，spill的策略就至關(guān)重要了。好的spill策略和壞的spill策略效果會差很多（程序的性能大概會差10%-18%左右吧）。 |
|
|
來自： univasity > 《編程開發(fā)》
