結(jié)合的指令調(diào)度與寄存器分配技術(shù)

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

關(guān)鍵詞：指令調(diào)度； 寄存器分配； 寄存器壓力； 寄存器溢出

中圖分類號(hào)：TP31文獻(xiàn)標(biāo)志碼：A

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

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

1寄存器分配敏感的調(diào)度算法

在調(diào)度算法中，除了考慮開(kāi)發(fā)指令級(jí)并行度之外，兼顧考慮寄存器分配的需求，避免引入過(guò)多的溢出代碼。此類調(diào)度算法統(tǒng)稱為寄存器分配敏感的調(diào)度算法。

1．1設(shè)置閾值控制調(diào)度

當(dāng)寄存器需求超過(guò)機(jī)器提供的數(shù)量時(shí)，會(huì)造成寄存器不夠分配，生成溢出代碼并且性能下降。此類方法通過(guò)設(shè)置閾值——可用的寄存器個(gè)數(shù)，區(qū)別寄存器需求超過(guò)/不超過(guò)閾值的情況采取不同的調(diào)度策略。

1．1．1結(jié)合的前遍調(diào)度（IPS）

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

IPS算法的實(shí)現(xiàn)簡(jiǎn)單，增加的編譯開(kāi)銷也小，可以很容易地應(yīng)用到全局調(diào)度上。缺點(diǎn)在于寄存器壓力的描述過(guò)于簡(jiǎn)單，沒(méi)有考慮溢出代碼的影響；而且簡(jiǎn)單以可用寄存器數(shù)量為限來(lái)選擇調(diào)度策略，缺乏整體的考慮，可能使得寄存器充裕時(shí)激進(jìn)的調(diào)度決定影響到后繼的調(diào)度。

1．1．2寄存器分配敏感的region調(diào)度（RASER）

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

a）估算各個(gè)region的指令級(jí)并行度。

b）進(jìn)行一遍IPS調(diào)度[9]，有利于得到較準(zhǔn)確的任意指令處的活躍變量個(gè)數(shù)。

c）計(jì)算各條指令處的活躍變量個(gè)數(shù)，取region內(nèi)最大者作為region的活躍變量個(gè)數(shù)。

d）對(duì)各個(gè)活躍變量個(gè)數(shù)過(guò)多（超過(guò)可用寄存器數(shù)目）的region作優(yōu)化減少活躍變量，即考慮哪些活躍變量可以將其定義直接移動(dòng)到每個(gè)使用點(diǎn)之前。

e）對(duì)各個(gè)并行度小的region作寄存器分配敏感的region調(diào)度變形。與標(biāo)準(zhǔn)的region調(diào)度變形不同的是，它禁止可能導(dǎo)致region活躍變量個(gè)數(shù)超過(guò)可用寄存器數(shù)目的代碼移動(dòng)。

重復(fù)上述過(guò)程，直到不存在并行度低于某個(gè)上限（此上限依賴于目標(biāo)處理機(jī)的并行能力）的region，也不存在活躍變量個(gè)數(shù)超過(guò)可用寄存器數(shù)目的region，或者沒(méi)有進(jìn)一步調(diào)度的機(jī)會(huì)。

RASER算法增加了IPS調(diào)度和減少活躍變量的優(yōu)化，相當(dāng)于增加了兩遍調(diào)度，相應(yīng)增加的開(kāi)銷是很大的。而且，該調(diào)度算法需要循環(huán)執(zhí)行上述過(guò)程，直到各個(gè)region并行度充足而且活躍變量個(gè)數(shù)沒(méi)有過(guò)多或者沒(méi)有進(jìn)一步調(diào)度的機(jī)會(huì)才終止，很難確定循環(huán)的時(shí)間開(kāi)銷上界，文獻(xiàn)[3]中也沒(méi)有報(bào)告RASER的調(diào)度時(shí)間。

1．2利用調(diào)度本身的特點(diǎn)

一般而言，指令調(diào)度的目標(biāo)是盡可能開(kāi)發(fā)指令級(jí)并行度，縮短關(guān)鍵路徑的長(zhǎng)度。但另一方面，過(guò)分激進(jìn)的調(diào)度會(huì)拉長(zhǎng)變量生存期、增大寄存器壓力，而且其中不乏并不能縮短關(guān)鍵路徑長(zhǎng)度的調(diào)度。因此可以區(qū)別地調(diào)度在關(guān)鍵路徑上的指令和不在關(guān)鍵路徑上的指令，盡可能維持關(guān)鍵路徑長(zhǎng)度不變的同時(shí)，縮短變量的生存期。

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

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

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

2調(diào)度敏感的寄存器分配算法

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

2．1基于干涉圖的改進(jìn)

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

2．1．1并行干涉圖

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

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

2．1．2調(diào)度敏感的全局寄存器分配（SSG）

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

2．2 基于DAG圖的改進(jìn)

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

2．2．1DAG圖驅(qū)動(dòng)寄存器分配方法

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

2．2．2統(tǒng)一資源分配方法（URSA）

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

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

3評(píng)價(jià)和其他結(jié)合算法

除了前面介紹的幾種結(jié)合寄存器分配和指令調(diào)度的技術(shù)研究之外，也有一些研究工作是關(guān)于前遍和后遍調(diào)度的方法與結(jié)合技術(shù)的比較的。

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

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

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

大部分結(jié)合技術(shù)的研究都是在按序或者VLIW的機(jī)器上進(jìn)行的，也有少量的利用機(jī)器亂序特征來(lái)做寄存器分配和指令調(diào)度結(jié)合的工作。文獻(xiàn)[26]利用亂序機(jī)器上指令窗[27]內(nèi)的指令可以同時(shí)發(fā)射的特征，在傳統(tǒng)局部指令調(diào)度器生成的指令序列上利用寄存器壓力敏感的線性化方法得到一個(gè)新的指令序列。它不會(huì)降低運(yùn)行時(shí)的指令級(jí)并行度，卻減少了溢出代碼獲得性能的提高。

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

4結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[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]楊書(shū)鑫，張兆慶.全局指令調(diào)度綜述[J].計(jì)算機(jī)工程與應(yīng)用，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.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”