結合的指令調度與寄存器分配技術

摘要：提出了很多結合技術使得指令調度與寄存器分配之間進行一些信息交互，在沒有引入過多溢出代碼的情況下提高了指令級并行度，從而提高了性能。按照算法的特征分類介紹了幾種影響力較大的算法，同時作了簡單的評價和效果比較，最后介紹了有關指令調度和寄存器分配結合的一些新方向。

關鍵詞：指令調度； 寄存器分配； 寄存器壓力； 寄存器溢出

中圖分類號：TP31文獻標志碼：A

文章編號：1001－3695(2008)04－0979－04

在編譯器中，指令調度和寄存器分配是兩個重要的階段。指令調度是一種指令級并行技術，它通過調整指令的順序來提高在一拍內能夠執行的指令數目（IPC）。按照調度階段是否出現在寄存器分配的前面，調度算法可分為前遍調度和后遍調度。按照調度范圍是否超過基本塊的邊界，調度算法可以分為局部調度[1，2]和全局調度[3，4]。全局調度按照調度范圍是否跨越循環迭代的邊界，可以劃分為有環全局調度和無環全局調度。寄存器分配決定哪些變量的值存放在寄存器中和放在哪個寄存器中，并盡量減少溢出代碼。按照分配的變量范圍，寄存器分配算法可以分為局部的[5]、全局的[6，7]和過程間的[8]，分別對應基本塊范圍、過程內跨越基本塊的范圍、跨越過程邊界的范圍。指令調度與寄存器分配關系是十分密切的。如果先進行寄存器分配，會給指令調度引入假依賴從而降低程序的并行性，減少了指令調度重排指令的機會；反之，先進行指令調度會使得過多的變量相互干涉，增加了寄存器壓力，增加了寄存器分配時的溢出代碼。盡管如此，受兩種優化的復雜度所限，在工程上實現兩者的同時進行是十分困難的，因而出現了很多研究兩者結合的技術，這些技術通過在此兩種優化之間增加一些信息交互獲得更好的性能。雖然有環全局調度亦不乏與寄存器分配結合的工作，但本文并不包括這些。

1寄存器分配敏感的調度算法

在調度算法中，除了考慮開發指令級并行度之外，兼顧考慮寄存器分配的需求，避免引入過多的溢出代碼。此類調度算法統稱為寄存器分配敏感的調度算法。

1．1設置閾值控制調度

當寄存器需求超過機器提供的數量時，會造成寄存器不夠分配，生成溢出代碼并且性能下降。此類方法通過設置閾值——可用的寄存器個數，區別寄存器需求超過/不超過閾值的情況采取不同的調度策略。

1．1．1結合的前遍調度（IPS）

文獻[9]最早提出結合指令調度和寄存器分配的算法。該文獻中，Goodman和Hsu提出了在大基本塊上進行的結合前遍調度（IPS）算法，提供兩種調度策略——CSP（code scheduling for pipelined processors）和CSR（code scheduling to minimize register usage）。它們的目標分別是提高指令級并行和減少使用寄存器。動態維護一個值AVLREG，表示當前可用寄存器的數目，控制采用哪種調度策略。主要步驟如下：在調度一個基本塊之前，由編譯器可分配的寄存器總數減去live－on－entry的寄存器個數得到AVLREG的初值；調度過程中有新的變量產生和變量死亡，相應地改變AVLREG；判斷AVLREG是否大于設定的閾值，大于則采用CSP策略，否則采用CSR策略；直到AVLREG恢復至閾值才繼續采用CSP策略調度。Bradlee等人[10]作了IPS的改進，增加了考慮全局變量的寄存器需求，性能更好。

IPS算法的實現簡單，增加的編譯開銷也小，可以很容易地應用到全局調度上。缺點在于寄存器壓力的描述過于簡單，沒有考慮溢出代碼的影響；而且簡單以可用寄存器數量為限來選擇調度策略，缺乏整體的考慮，可能使得寄存器充裕時激進的調度決定影響到后繼的調度。

1．1．2寄存器分配敏感的region調度（RASER）

RASER[11]算法基于一種全局調度算法，即region調度算法[3]，以region作為指令調度的范圍。Region指的是PDG圖上的節點，表示直接依賴于相同控制條件（謂詞）的一組代碼。RASER主要步驟如下：

a）估算各個region的指令級并行度。

b）進行一遍IPS調度[9]，有利于得到較準確的任意指令處的活躍變量個數。

c）計算各條指令處的活躍變量個數，取region內最大者作為region的活躍變量個數。

d）對各個活躍變量個數過多（超過可用寄存器數目）的region作優化減少活躍變量，即考慮哪些活躍變量可以將其定義直接移動到每個使用點之前。

e）對各個并行度小的region作寄存器分配敏感的region調度變形。與標準的region調度變形不同的是，它禁止可能導致region活躍變量個數超過可用寄存器數目的代碼移動。

重復上述過程，直到不存在并行度低于某個上限（此上限依賴于目標處理機的并行能力）的region，也不存在活躍變量個數超過可用寄存器數目的region，或者沒有進一步調度的機會。

RASER算法增加了IPS調度和減少活躍變量的優化，相當于增加了兩遍調度，相應增加的開銷是很大的。而且，該調度算法需要循環執行上述過程，直到各個region并行度充足而且活躍變量個數沒有過多或者沒有進一步調度的機會才終止，很難確定循環的時間開銷上界，文獻[3]中也沒有報告RASER的調度時間。

1．2利用調度本身的特點

一般而言，指令調度的目標是盡可能開發指令級并行度，縮短關鍵路徑的長度。但另一方面，過分激進的調度會拉長變量生存期、增大寄存器壓力，而且其中不乏并不能縮短關鍵路徑長度的調度。因此可以區別地調度在關鍵路徑上的指令和不在關鍵路徑上的指令，盡可能維持關鍵路徑長度不變的同時，縮短變量的生存期。

Chen Gang等人[12]提出的方案是在全局指令調度和寄存器分配之間增加一個指令重排過程以緩解寄存器壓力。具體的方法是首先進行一遍標準的指令調度，盡可能開發指令級并行度；然后進行指令重排，盡可能維持關鍵路徑長度不變，同時取消過度激進調度的影響，緩解寄存器壓力。大部分的調度算法都是自頂向下(top－down，TD)進行的，習慣性盡可能早地發射指令。指令重排本質上是作一次自底向上（bottom－up，BU）的調度，在關鍵路徑上的指令不移動，不在關鍵路徑上的指令盡可能晚地發射；另外，重排過程中的資源沖突檢查會更加嚴格，檢查準備發射的指令是否與已發射的指令、甚至未發射的指令之間存在功能部件的沖突，避免因重排帶來的資源沖突引起關鍵路徑的增長。簡單的TD－BU方法能縮短一些變量的生存期，但也使得一些指令匯聚在較晚的cycle發射，促使這些cycle的寄存器壓力過大。所以Chen Gang結合IPS方法進行了改進——TD－BU－CSR方法，在重排過程中設置可用寄存器的個數限制過度重排。

文獻[12]中，實驗表明兩種TD－BU的方法都比IPS方法高效。另外，BU調度過程中代碼會向下移動，向下移動在遇到結合節點時需要硬件的謂詞支持。Chen Gang的調度算法是以不包含結合節點的超級基本塊（superblock）[4]作為全局調度的范圍，實現BU調度很方便，但若應用到調度范圍包含結合節點的調度算法中，實現會更困難。

文獻[13]介紹的是寄存器壓力敏感的指令調度配合線性寄存器分配[14]。其指令調度的思想與TD－BU很類似，即在保證不影響關鍵路徑長度的前提下指令盡量晚地調度。

2調度敏感的寄存器分配算法

在寄存器分配算法中，除了考慮如何減少寄存器溢出及其帶來的訪存代價之外，兼顧考慮減少由重用寄存器而給調度引入的假依賴。此類分配算法統稱為調度敏感的寄存器分配算法。

2．1基于干涉圖的改進

寄存器分配大都基于圖著色的方法，利用干涉圖描述當前指令順序下變量之間的干涉關系。此類方法在干涉圖上增加調度的信息，使得寄存器分配考慮到調度的需求。

2．1．1并行干涉圖

Pinter提出了并行干涉圖的方法[15]，在干涉圖上加入調度的限制。并行干涉圖的構建過程如下：a)分別為程序建立描述指令依賴關系的調度圖和描述變量干涉關系的干涉圖；b)生成擴展調度圖，即生成調度圖的傳遞閉包、消除邊的方向、增加結構相關的邊，它表示了指令間所有的并行限制；c)求擴展調度圖的補集，表示程序可開發的并行度；d)把該補集中存在而干涉圖上不存在的邊（即并行邊）都加到干涉圖上，則得到最后的并行干涉圖。Pinter提出并證明了定理，即并行干涉圖的每一種最優著色都提供了一種沒有溢出代碼的寄存器分配方案，它相應的調度圖也不存在假依賴。寄存器分配時采用并行干涉圖。當遇到寄存器不夠分配的情況，需要通過權衡并行度和寄存器溢出的收益/代價來決定刪去圖中的并行邊或者干涉邊。

該方法應用于基本塊的范圍，Pinter提出了應用到全局范圍的一些討論。該方法在一張圖上直觀地表示出寄存器分配的沖突和指令調度的限制，而且在可著色的情況下可以得到不會為調度引入假依賴的寄存器分配。但是，在應用于大基本塊或者全局范圍時，并行干涉圖可能過大、過于復雜，將極大地增加寄存器分配的復雜度和寄存器的需求數量，增加編譯器的時空開銷。另外，不可著色的情況下權衡考慮作寄存器溢出或者犧牲指令級并行度也很復雜。

2．1．2調度敏感的全局寄存器分配（SSG）

Norris等人[16]提出的局部調度敏感的全局寄存器分配的方法（SSG），目的是使得全局寄存器分配器只加入不影響局部指令調度的依賴。SSG基于Briggs等人[17]提出的樂觀的圖著色分配算法，在build階段，借助基本塊的數據依賴圖，干涉圖包括所有合法調度下變量間可能的干涉關系。當寄存器不夠分配時，可以通過寄存器溢出或者增加數據依賴圖的邊（限制指令調度）來減少干涉關系。SSG方法需要同時利用干涉圖和數據依賴圖。SSG方法與并行干涉圖一樣，在著色失敗時需要選擇作寄存器溢出還是限制并行度，Norris和Pollock通過實驗方法比較了幾種選擇策略的效果并從中擇優。

2．2 基于DAG圖的改進

DAG圖是指令調度常用的一種表示依賴關系的形式，從中可以發現指令間部分的確定順序和并行度。此類方法利用DAG圖上的這些信息指導資源的分配。

2．2．1DAG圖驅動寄存器分配方法

文獻[1]提出了一種結合的局部寄存器分配方法——DAG圖驅動寄存器分配方法。它采用DAG圖來指導寄存器分配以減少重用寄存器帶來的依賴。包括兩種策略：釋放讀后寫依賴和平衡DAG圖的生長。前者是指由于重用寄存器而引入的新依賴主要是WAR（write－after－read）依賴，分配時盡量使當前指令占用的死寄存器在該指令的依賴路徑上；后者是指在分配時結合考慮指令的最早開始時間EIT和最早結束時間EFT，需要重用寄存器時盡量避免分別具有大的EIT和大的EFT的指令重用一個寄存器，造成關鍵路徑的增長。

2．2．2統一資源分配方法（URSA）

Berson等人[18]提出的URSA方法在VLIW機器上采用統一的資源分配器分配寄存器和功能部件。主要步驟如下：首先依據程序trace建立依賴圖DAG；為功能部件和寄存器各自建立重用DAG圖，并依據此圖確定各個資源的最大需求量以及資源需求超過機器提供的區域；通過變形來減少資源需求，直至減少到機器提供的數量；分配寄存器和功能部件；生成代碼。以依賴DAG圖為基礎，建立重用DAG圖，表示指令之間的資源重用關系。資源的最大需求是任何合法調度下需求該資源的最大數目，以重用DAG圖的最小分解中分配鏈的數目表示。減少資源的需求可以采用增加序列邊或者寄存器溢出的方法，兩種方法之間的選擇需要結合考慮最小的關鍵路徑長度和減少過度需求這兩個因素。其后，Berson對URSA方法進行了改進[19]，即減少資源需求時采用增加序列邊或者生存期分裂的方法。URSA方法需要求出重用DAG圖的最小分解來計算資源需求，并且同時分配兩種資源，因而實現的復雜度很高。

除了URSA方法之外，還有一些其他工作也是基于DAG圖計算資源需求的。Touati證明了URSA方法計算最大寄存器需求并不充分[20，21]，他利用數據依賴圖DDG，理論地研究了代碼所有合法調度的精確寄存器需求上限，獨立于功能部件的限制。該上限稱為寄存器飽和[22]。從減少寄存器溢出考慮，Govindarajan等人[23]論述了最小寄存器需求的指令序列問題（MRIS），提出了基于重疊的生存期鏈的啟發式解決方法。其中的生存期鏈與URSA使用的重用DAG圖上的分配鏈相類似，也描述了資源的重用關系并由鏈計算資源的需求。

3評價和其他結合算法

除了前面介紹的幾種結合寄存器分配和指令調度的技術研究之外，也有一些研究工作是關于前遍和后遍調度的方法與結合技術的比較的。

Norris等人[24]通過實驗方法評價他們提出的全局指令調度和寄存器分配的結合技術（RASER）[11]、寄存器分配和局部指令調度的結合技術（SSG）[16]在不同實現框架中的效果以及與后遍調度算法的對比。實驗結果表明，采用這兩種結合的技術在絕大多數情況下生成的代碼都優于完全非結合的技術；在五種實現框架中，獲得最大加速比的是RASSG、REGSSG，即先進行結合或者不結合的全局調度，再進行局部調度敏感的寄存器分配，最后進行標準的局部調度。

Berson等人[19]將他們提出的URSA方法配合生存期分裂技術與前人提出的兩種結合技術——IPS和SSG及其改進作了比較。在六發射的超長指令字（VLIW）的體系結構上進行的實驗表明，在編譯時間和代碼性能上，URSA都是其中最好的；結合技術對于高寄存器壓力的程序更加重要；采用重用DAG圖比干涉圖計算過度集更準確，生成的代碼性能更好；生存期分裂技術比溢出技術更有效；在大多數情況下IPS生成的代碼比SSG的性能更好。

Valluri等人[25]通過實驗的方法比較了幾種局部調度技術在亂序機器上的表現，包括后遍表調度、前遍表調度、并行干涉圖[15]（類后遍調度）和結合的前遍調度IPS[9]（類前遍調度）。實驗表明，結合的技術相比非結合調度算法并沒有帶來顯著的性能提高。在亂序執行的機器上，前遍方法性能甚至比不進行編譯器指令調度的情況更差；而后遍方法性能比前遍方法更好，尤其對于高寄存器壓力的程序。由此，該文獻指出，亂序機器上編譯器更應該關注的是減少溢出代碼。不過，該文獻只比較了局部調度，而沒有進行全局調度算法的比較。

大部分結合技術的研究都是在按序或者VLIW的機器上進行的，也有少量的利用機器亂序特征來做寄存器分配和指令調度結合的工作。文獻[26]利用亂序機器上指令窗[27]內的指令可以同時發射的特征，在傳統局部指令調度器生成的指令序列上利用寄存器壓力敏感的線性化方法得到一個新的指令序列。它不會降低運行時的指令級并行度，卻減少了溢出代碼獲得性能的提高。

由于指令調度和寄存器分配都是NP復雜的，一般采用啟發式的方法，當然也有采用其他方法的。其中一種是數學建模的方法[32~34]。文獻[32]采用整數線性規劃方法，將指令調度和寄存器分配都統一表示成一組作為條件的不等式和一個目標函數，以此實現兩種優化的結合。文獻[34]采用動態規劃的方法，同時執行指令選擇、指令調度和寄存器分配。數學建模方法雖然可以找到最優，但它的編譯時間開銷往往很高昂，遠非一個產品編譯器所能接受，所以通常只能用于較小的DSP應用。另外，近幾年興起的運用人工智能方法來解決編譯技術中的問題，也是編譯研究中的一個新方向，主要是利用人工智能的方法來調整編譯優化的選項組合、優化的順序、調整代價模型。相關指令調度與寄存器分配結合的如文獻[35，36]等。文獻[35]考慮到寄存器分配和指令調度之間的強依賴性，采用遺傳算法來同時指導寄存器分配和指令調度。種群中的個體由寄存器分配的一個個體（即一種分配方案）和指令調度的一個個體（即一種調度方案）組成，適應度采用生成代碼的實際運行時間。文獻[36]描述的調度是一個基于公用接口的多遍過程，通過利用機器學習的方法自動獲得好的調度遍的順序。這些相互獨立的遍每個實施一種調度的啟發式規則，包括關鍵路徑、依賴關系、功能部件、寄存器壓力等。

4結束語

寄存器分配和指令調度是編譯器中兩個重要的階段，由于兩者在目標上有沖突，它們的交互對生成代碼的質量有重大影響，尤其在細粒度并行的體系結構的編譯器中。結合的寄存器分配和指令調度大都需要提供機制識別出過度的寄存器需求和減少寄存器需求，要考慮如何在寄存器壓力和指令級并行度之間進行權衡。本文按照算法的特征分類介紹了一些有代表性的結合寄存器分配和指令調度的方法，并比較它們的效果。這兩種優化的結合大都基于按序的機器，采用啟發式方法，也有一些工作采用其他方法，包括數學建模、人工智能等。這些新方法便于建立更通用、更易移植且效果不錯的編譯器，以適應快速發展的硬件架構要求，也給結合技術提供了新的思路。

參考文獻：

[1]HENNESY J， GROSS T. Postpass code optimization of pipeline constraints[J]. ACM Trans on Programming Languages and Systems， 1983，5(3):422－448.

[2]ABRAHAM S， PADMANABHAN K. Instruction reorganization for variable－length pipelined microprocessor[C]//Proc of IEEE International Conference on Computer Design. Rye Brook:[s.n.]， 1988:96－101.

[3]GUPTA R， SOFFA M L. Region scheduling: an approach for detecting and redistributing parallelism[J]. IEEE Trans on Software Engineering， 1990，16(4):421－431.

[4]HWU W， MAHLKE S A， CHEN W Y， et al. The superblock: an effective technique for VLIW and superscalar compilation[J]. Journal of Supercomputing， 1993，7(1/2):229－248.

[5]HSU W C， FISHER C N， GOODMAN J R. On the minimization of loads/stores in local register allocation[J]. IEEE Trans on Software Engineering， 1989，15(10):1252－1260.

[6]CHOW F， HENNESSY J. The priority－based coloring approach to register allocation[J]. ACM Trans on Programming Languages and Systems， 1990，12(4):501－536.

[7]KOLTE P， HARROLD M J. Load/store range analysis for global re－gister allocation[C]//Proc of ACM SIGPLAN Conference on Programming Language Design and Implementation. New York: ACM Press， 1993.

[8]WALL D W. Global register allocation at link time[C]//Proc of SIGPLAN Symposium on Compiler Construction. New York: ACM Press， 1986:264－275.

[9]GOODMAN J R， HSU W C. Code scheduling and register allocation in large basic blocks[C]//Proc of the 2nd International Conference on Supercomputing. New York: ACM Press， 1988:442－452.

[10]BRADLEE D G， EGGERS S J， HENRY R R. Integrating register allocation and instruction scheduling for RISCs[C]//Proc of the 4th International Conference on Architectural Support for Programming Languages and Operating Systems. New York: ACM Press， 1991:122－131.

[11]NORRIS C， POLLOCK L. Register allocation sensitive region scheduling[C]//Proc of IFIP WG10.3 Working Conference on Parallel Architectures and Compilation Techniques. Manchester: IFIP Working Group on Algol， 1995:1－10.

[12]CHEN Gang， SMITH M D. Reorganizing global schedules for register allocation[C]//Proc of International Conference on Supercomputing. 1999:408－416.

[13]WIN K K K， WONG W F. Cooperative instruction scheduling with linear scan register allocation[C]//Proc of the 12th Annual IEEE International Conference on High Performance Computing， Lecture Notes of Computer Science. 2005:528－537.

[14]POLETTO M， SARKAR V. Linear scan register allocation[J]. ACM Trans on Programming Languages and Systems， 1999，21(5):895－913.

[15]PINTER S S. Register allocation with instruction scheduling: a new approach[C]//Proc of ACM SIGPLAN Conference on Programming Language Design and Implementation. New York: ACM Press， 1993:248－257.

[16]NORRIS C， POLLOCK L. A scheduler－sensitive global register allocator[C]//Proc of Conference on Supercomputing. 1993:804－813.

[17]BRIGGS P， COOPER K D， TOREAON L. Rematerialization[C]//Proc of ACM SIGPLAN Conference on Programming Language Design and Implementation. New York: ACM Press， 1992:311－321.

[18]BERSON D， GUPTA R， SOFFA M L. URSA: a unified resource allocator for registers and functional units in VLIW architectures[C]//Proc of IFIP WG10.3 Working Conference on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism. Manchester: IFIP Working Group on Algol， 1993:243－254.

[19]BERSON D， GUPTA R， SOFFA M L. Integrated instruction scheduling and register allocation techniques[C]//Proc of the 11th International Workshop on Languages and Compilers for Parallel Computing. London: Springer－Verlag， 1998:247－262.

[20]TOUATI S A A. Maximizing for reducing register need in acyclic schedules[C]//Proc of the 5th International Workshop on Software and Compilers for Embedded Systems. 2001.

[21]TOUATI S A A， THOMASSET F. Register saturation in data depen－dence graphs， RR－3978[R].[S.l.]: INRIA， 2000.

[22]TOUATI S A A. Register saturation in superscalar and VLIW codes[C]//Proc of the 10th International Conference on Compiler Construction. London: Springer－Verlag， 2001:213－228.

[23]GOVINDARAJAN R， YANG Hong－bo， AMARAL J N. Minimum register instruction sequencing to reduce register spills in out－of－order issue superscalar architectures[J]. IEEE Trans on Computers， 2003， 52(1):4－20.

[24]NORRIS C， POLLOCK L. An experimental study of serveral cooperative register allocation and instruction scheduling strategies[C]//Proc of the 28th Annual International Symposium on Microarchitecture. Los Alamitos: IEEE Computer Society Press， 1995:169－179.

[25]VALLURI M G， GOVINDARAJAN R. Evaluating register allocation and instruction scheduling techniques in out－of－order issue processors[C]//Proc of International Conference on Parallel Architectures and Compilation Techniques. Washington DC: IEEE Computer Society， 1999:78－83.

[26]SILVERA R， WANG Jian， GAO G R， et al. A register pressure sentive instruction scheduler for dynamic issue processors[C]//Proc of Conference on Parallel Architectures and Compilation Techniques. Washington DC: IEEE Computer Society， 1997:78－89.

[27]JOHNSON M. Superscalar microprocessor design[M]. New Jersey: Prentice－Hall， 1991.

[28]MOTWANI R， PALEM K V， SARKAR V， et al. Combined instruction scheduling and register allocation， TR1995－698[R]. New York: New York University， 1995.

[29]SRIKANT Y N， SHANKAR P. The compiler design handbook: optimizations machine code generation[M].[S.l.]: CRC Press， 2002.

[30]FREUDENBERGER S M， RUTTENBERG J. Phase ordering of register allocation and instruction scheduling[C]//Proc of the Interna－tional Workshop on Code Generation —— Concepts， Tools， Techniques. New York: Springer－Verlag， 1992:146－172.

[31]楊書鑫，張兆慶.全局指令調度綜述[J].計算機工程與應用，2004，40(21):44－48，89.

[32]BRUGGEN T， ROPERS A. Optimized code generation for digital signal processors[R]. Aachen， Germany: Institute for Integrated Signal Processing Systems， 1999.

[33]BHATTACHARYYA S S， LEUPERS R， MARWEDEL P. Software synthesis and code generation for signal processing systems[J]. IEEE Trans on Circuits and Systems－Ⅱ: Analog and Digital Singal Processing， 2000，47(9):849－875.

[34]KESSLER C， BEDNARSKI A. Optimal integrated code generation for clustered VLIW architectures[C]//Proc of Joint Conference on Languages， Compilers and Tools for Embedded Systems. 2002:102－111.

[35]KRI F， FEELEY M. Genetic instruction scheduling and register allocation[C]//Proc of the 1st International Conference of Quantative Evaluation of Systems. Washington DC: IEEE Computer Society， 2004:76－83.

[36]PUPPIN D， STEPHENSON M， AMARASINGHE S， et al. Adapting convergent scheduling using machine learning[C]//Proc of ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. New York: ACM Press， 2003.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”