基于VLIW的機器相關優化編譯技術研究 摘要 VLIW體系結構性能的發揮在很大程度上依賴于其相應的編譯器。編譯優化主要包括兩個方面：一方面是傳統的編譯器優化技術；另一方面是針對具體機器平臺特定的優化技術。VLIW機器相關的編譯優化技術應該針對具體的機器平臺，基于超長指令字體系結構的特點，考慮如何充分利用機器提供的硬件資源，以達到軟件（編譯器）和硬件（CPU）的最大匹配，從而生成高效率高并行度的目標代碼。本文從超長指令字的特點出發，探討了在VLIW體系結構下與機器相關的編譯優化的實現方案，同時提出了幾點在具體進行與機器相關的優化編譯時的優化思路。關鍵詞 VLIW 超長指令字 機器相關 優化編譯 ILP 預測 Research on architecture-dependent compiler optimization technology based on VLIW Abstract The performance of VLIW architecture heavily depends on the quality of relevant compilers. The compiler optimization technology consists of two aspects: one is traditional optimization technology; the other is architecture-dependent optimization technology. Before implementing architecture-dependent optimization, we should adequately analyze the architecture characters of machine platform concerned, and consider how to make the best of the hardware resources. Software (compiler) and hardware (CPU) must match well to produce object codes with high efficiency and high ILP. After analyzing the general characters of VLIW architecture, this paper develops a design of architecture-dependent compiler optimization scheme based on VLIW, and brings forward some optimization points during the actual implementation.Key wordsVLIW, architecture-dependent, compiler optimization, ILP, predication引言 1983年美國教授J.Fisher1受水平微代碼思想的啟示，提出了VLIW（超長指令字）體系結構。VLIW由編譯器將多個可以同時并行執行的操作排在一條超長指令字中，在一個指令周期內由CPU并行發射，以減少對存儲器的訪問。與傳統結構相比，這種體系結構既可以提供較高的指令級并行度，同時又具有簡單的硬件譯碼和控制邏輯。在近二十年內，從著名的FPS AP-120B，Multiflow、Cydrome Cydra 5發展到E2K，以及Intel公司推出的下一代處理器IA-64，使得VLIW成為繼CISC、RISC后的又一重要的體系結構。 目前，國外針對VLIW結構的研究主要有Illinois大學可靠性與高性能計算中心研制的IMPACT系統、斯坦福大學研制的SUIF系統框架，俄羅斯開發的E2K芯片及其系統，以及Intel微處理器實驗室研制的IA-64編譯器等。我國在這方面的研究Page: 1起步較晚，目前還沒有相應的自主系統2。Page: 1太絕對VLIW體系結構性能的發揮在很大程度上依賴于其相應的編譯器，這對編譯器及其優化技術提出了新的需求。因此，如何針對具體VLIW機器平臺的特點，研究相應的機器相關優化技術，在整個VLIW編譯技術研究中占有重要地位，并對快速提高國產VLIW編譯器性能有著重要的意義。1 VLIW體系結構概述 VLIW體系結構是將水平微碼和超標量處理這兩種普遍采用的概念相結合的產物。從指令系統上講，VLIW指令系統的設計思想與水平微碼類似。VLIW機器具有較長的機器指令字，機器指令字具有固定的格式（一種或者多種），每條指令字中包含著多個獨立的字段，字段中的操作碼被送往不同的功能部件。為了與通常的指令區別，我們稱這種操作為算子（或者微操作）。通常，在編譯過程需要將算子拚裝成超長指令字，這是VLIW編譯系統實現過程中的一個重要任務。從結構上講，VLIW與超標量的RISC機類似，機器內部提供多個可以并發的功能部件， 所有功能部件共享使用大型寄存器堆，CPU在一個時鐘周期內可發射多條指令。與傳統的RISC技術不同的是VLIW采用靜態指令調度技術，它的流水線是非保護的，沒有用于防止資源沖突和隱藏流水線延時的硬件的互鎖機制，完全依賴編譯器靜態地分析程序中指令的依賴關系，來決定指令是否可以并行執行以及執行順序，而超標量機是在指令運行時由硬件來進行并行檢測和指令調度的。因此，VLIW并行性能的提高在很大程度上依賴于VLIW編譯系統的實現，支持此結構的編譯器應該在保證并行執行的操作不會超過機器提供的并行資源最大限度的前提下，盡可能的提高算子的并行度，這是系統實現的又一重要任務。 因此，綜上所述，VLIW體系結構的特點主要是：l 具有較長的機器指令字，一般為128位甚至上千位。機器指令字具有固定的格式，并且被劃分成多個控制字段，每個字段可以直接獨立的控制相應的功能部件。一條指令字可以填入多個獨立的并行操作，為了與通常的機器區別，我們稱這種操作為算子，把按照機器指令字格式將算子組成超長指令字的過程稱為拼裝2。超長指令字中的多個可并行執行的算子的調度和拼裝是由編譯器來完成的。l 含有大量的數據通路和多個可以并行的運算部件，由于數據相關和資源相關性是通過編譯器來進行處理，因此硬件本身具有較簡單的控制邏輯3。l 控制部件每個周期啟動一條機器指令，但同時發射其中的一條或多條算子。其并發操作主要是在流水的執行階段進行的。l 用大量的全局共享寄存器，存儲單元，寄存器堆來連接多個功能部件。2 VLIW體系結構下機器相關編譯優化的實現方案編譯優化的主要任務是使編譯出來的代碼能夠以更快的速度、使用更少的空間進行運行。代碼優化首先必須保持代碼原有的語義，其次必須能夠顯著的提高程序運行的速度，最后優化過程應當具有一定的效率。優化主要包括兩個方面：一方面是傳統的編譯器優化技術；另一方面是針對具體機器平臺特定的優化技術。 傳統的編譯優化技術包括三個部分：控制流分析，數據流分析和轉換。控制流和數據流分析是為轉換做準備的。轉換則是進行一定代碼的變更、替代、移動和重組。代碼優化的具體辦法很多，通常包括：公共子表達式的刪除，循環語句的優化，死代碼的刪除，代碼移動，減少變量和重復等。這部分優化主要集中在中間代碼上進行，而且一般與具體硬件平臺無關。傳統的優化技術國內外的研究已經很多，而且比較成熟，在現有的許多編譯系統中也都有相關的實現。機器相關的編譯優化技術則應該針對具體的機器平臺，基于超長指令字體系結構的特點，考慮如何充分利用機器提供的硬件資源（通用寄存器，寄存器堆，冗余運算部件等），以達到軟件（編譯器）和硬件（CPU）的最大匹配結合，從而生成高效率高并行度的目標代碼。如上節所述，VLIW指令系統上最小的單位是算子（即超長指令字里各個字段對應的微操作），由編譯器把算子拼裝起來完成通常匯編指令的功能。一條匯編指令既可以對應著單個的算子，也可以對應著多個算子。對于一些功能比較單一的運算類的匯編指令，一條匯編指令就對應著一個算子，只填入超長指令字的一個字段里；但是，對于功能比較復雜的指令，特別是一些系統指令，一條匯編指令就可以對應著多個算子，由多個算子聯合起來完成這一條匯編指令的功能，當然這就需要填入超長指令字的多個字段里。例如：最常用的PUSH REG 指令，就需要由下列三個算子聯合起來完成 修改堆棧指針算子 | 寫內存算子 | 數據來源選通算子 每個算子也就對應了在執行階段具體發射時機器的最小執行單元。編譯器拼裝起來放在一條超長指令字當中的多個算子，即可以聯合起來實現我們通常意義上的匯編指令，也可以互不相干，各自獨立。因此，在VLIW編譯系統里，如何通過優化來決定實現程序功能的最小數目算子集，以及如何將這最小數目的算子集最大可能的并行拼裝在一條超長指令字當中以生成最小數目的機器指令，是與機器相關的編譯優化工作的關鍵。鑒于VLIW體系結構指令系統的這種特點， 這里給出一種優化方案來實現與機器相關的編譯優化工作。我們的優化方案從兩個層次來展開。第一個層次是在匯編指令級，主要進行指令歸并，常數傳播，依賴和數據相關分析及消除，寄存器重命名等等優化的工作。上述這些具體優化的技術正是國內外現在研究的熱點，可以根據機器平臺的實際情況有選擇的采用和實現。通過這一層的優化，可產生最精簡的匯編程序，從而決定了最小數目的算子集合（微操作集合）。我們把經過這一層優化產生的匯編程序轉換成算子形式的程序（這一轉化必須要保證語義上的完全一致性），然后，再傳遞給第二個優化層次：算子級。這一層的優化工作主要是將上一層傳遞來的算子序列進行數據依賴及相關性分析，并做算子調度，從而進行優化拼裝和重排，要充分利用超長指令字以及硬件的并行資源，盡最大可能的在一條超長指令字里填入多個算子，減少超長指令字當中無效的位數，以提高超長指令字的利用效率，從而生成最小數目的機器指令，同時還必須保證邏輯以及時序上的正確性。整個方案的流程圖如圖1：總的來說，優化方案體現在時間和空間兩個方面。在時間上，應該最大可能的減少目標代碼的執行周期數，這是匯編指令層優化的重點。在空間上，應該最大可能的減少機器指令的條數，這是算子層優化的重點。當然，時間和空間總是交織在一起的，在兩個層次的優化工作里必然都會涉及到。 C程序匯編程序指令級優化模塊AS匯編翻譯模塊AS算子翻譯模塊 C compiler匯編到算子轉化模塊 算子級優化模塊 優化過的算子 助記符程序 算子 助記符程序 精簡 匯編程序不帶機器相關優化選項帶機器相關優化選項算子級調度，算子優化拼裝，重排指令歸并，依賴及數據相關分析常數傳播 二進制機器碼文件圖1： VLIW體系結構下機器相關編譯優化的實現方案3 在機器相關優化編譯具體實施時的幾點思路Page: 4方法 目前，國內外具體針對于VLIW體系結構的優化編譯技術研究大部分都集中在提高指令并行度（ILP）上，其基本出發點是利用硬件提供的各種并行資源，在一個周期內執行盡可能多的指令，從而提高程序運行效率。其中通常采用的優化技術有：循環優化，指令依賴檢測及刪除，指令調度，數據預讀，分支檢測與刪除，寄存器及功能部件的分配策略等等。VLIW體系結構為采用上述先進的優化編譯技術提供了可能，反過來說，只有采用這些先進的編譯優化技術，才能充分發揮VLIW體系結構的高性能5。上述這些優化技術在實施的時候，都需要預先分析大量的匯編程序實例，以決定在具體實施時該如何操作，并檢驗該種優化技術對當前的機器平臺是否能起到好的優化效果。本文在這里不對這些優化技術做具體探討，我們只是從實際開發或者移植一個VLIW編譯器的角度出發，針對與機器相關的優化，給出幾點在做具體工作時值得考慮的優化思路。3.1 最大可能的利用超長指令字的指令空間1) 延遲機制 VLIW體系結構通常支持128位或者更多位數的指令字，還提供了相應的指令格式，編譯器需要按照機器提供的機器指令格式來把指令（算子）進行合并拼裝，以生成128位的機器代碼。當不考慮優化，只考慮正確性時，編譯器當然可以孤立的對匯編程序中每條指令按前后順序依次生成只完成該指令功能的機器代碼，這樣避免了相關性的分析，可保證運行結果正確，但這顯然沒有體現VLIW結構的特點，造成了指令字極大的浪費。因此如何在拼裝生成機器代碼的過程當中充分利用超長指令字的位數資源，在優化工作中占有舉足輕重的地位。要想最大可能的利用超長指令字空間，其總的原則當然就是一條指令字中盡可能的多拼指令（算子）。VLIW通常是把在一個周期里可以并行執行的指令，即不存在依賴和相關性的指令，并排在一條超長指令字里，來同時發射，這種方式采用的最為廣泛，它的好處是邏輯上簡單易行，但是這種拼裝方式導致了一個限制，就是即使當前的超長指令字還可以繼續容納其他的指令，但如果后繼的指令由于相關性而都不能跟當前指令字中已經填入的指令并行執行時，編譯器只能浪費掉相應的指令字空間。因此，為了能夠更靈活的使用超長指令字的位數資源，我們除了前面提到的那種通常的并行拼裝方式以外，還可以考慮支持延遲的拼裝方式其做法可以是在指令正常的編碼里加入相應的延遲位，來表明該指令延遲執行的周期數。例如：對于常用的雙操作數運算指令，其編碼為指令功能控制域操作數來源一選通域操作數來源二選通域如果支持延遲的拼裝方式的話，如下：指令功能控制域操作數來源一選通域操作數來源二選通域延遲位（2位）這樣，當延遲位為00，表示該指令不延遲，01表示延遲1個周期執行，10表示延遲2個周期執行，11表示延遲3個周期執行。如果支持延遲的話，即使兩條指令存在相關性，也可以同時放入一條超長指令字中，這樣可以增加指令調度的靈活性，提高超長指令字的利用效率。當然，這種延遲的執行及拼裝方式需要硬件譯碼的支持。 2) 指令字的控制粒度超長指令字可控制的粒度會直接影響調度及優化的效果。一般來說，我們在匯編指令級采取各種優化技術，然后將指令并行排入超長指令字中，這時超長指令字控制的粒度較粗，更靠近高層的匯編指令。如本文前節所述，有些功能較復雜的指令在實現時，機器需要完成多個微操作，而這些微操作之間往往存在著相關性。如果超長指令字的控制粒度停留在指令級，功能復雜的指令所對應的多個微操作則必須看成一個整體，固定了必須要由同一條超長指令字來進行發射。當這種功能復雜的指令連續出現多條，而且彼此又有相關性時，超長指令字控制的粒度還停留在指令級就會大大限制我們的調度和優化的效果。事實上，對于VLIW體系結構，超長指令字控制的粒度越細，越靠近機器的功能部件，調度及優化的效果越好。同時，我們還應該打破一條匯編指令對應的微操作必須排在同一條超長指令字當中，由同一條超長指令字發射的思路，在把指令分拆成算子（微操作）之后，只考慮算子在執行上的邏輯性和時序性，將其最大限度的填入超長指令字當中，而不必拘泥于匯編指令和超長指令字之間的一一對應關系。 事實上，隨著VLIW體系結構繼續發展，有可能超長指令字的粒度會進一步細到電路微觀的層次上，由超長指令字直接對部件的控制邏輯進行編碼，這樣一來硬件中指令編碼的譯碼器數量會大大減少。硬件則完全開放給軟件，軟件和硬件的結合更為緊密，當然也會導致超長指令字的位數大大增加。3.2 匯編指令級部件不可見VLIW體系結構通常同時提供多個可同時發射的功能相同的運算部件，通過運算部件的冗余，可以在同一時刻并行的完成某些功能，從而提高程序的運行效率。因此相應的在匯編手冊中，可能會提供多套匯編指令來完成同樣的功能。例如，如果硬件提供兩個浮點運算部件，那么可能在匯編手冊中就有兩條指令FSADD和FSADD2，分別對應這兩個浮點運算部件，都來完成浮點加法運算，在同一時刻可以完成兩個浮點加法運算。但是，大多數編譯器在進行從高級程序到匯編程序的翻譯時，是很難實現這一想法的。事實上編譯器在生成匯編程序的時候，無法決定什么時候該使用哪一個運算部件對應的匯編指令。例如上述情況，即使有兩條指令來完成浮點加法，但在編譯器這一層次上無法決定什么時候該用FSADD，什么時候該用FSADD2。也就是說，在編譯器生成的匯編程序里，這些被多個運算部件支持的功能還是只能由同一套指令來完成，即只使用了其中的一個運算部件，其余的運算部件都空閑，這顯然沒有充分利用VLIW的硬件資源。針對這種現況，在我們進行優化工作時，必須要加以解決以充分利用硬件提供的硬件資源。如果上層編譯器的轉換機制不進行修改的話，可以考慮在匯編指令一級讓部件不可見，即在匯編指令級上看不出有多少個運算部件可以完成同樣的功能，將原來的多套指令都合并成為一套指令，這樣編譯器可以不進行改寫，而在匯編器內部來決定用哪一個運算部件來完成該指令的功能，這樣就可以充分的均等的利用支持這些功能的所有運算部件，從而提高并行性，達到優化的目的。例如：硬件有兩個浮點運算部件，完成浮點單精度加法有FSADD和FSADD2兩條指令， 現在我們可以將它們合并，即只提供一條指令FSADD來完成浮點單精度加法。這 樣每次遇到FSADD指令，編譯器內部具體為其生成機器碼的時候，就可以采用輪循 的方式，用不同的運算部件來完成這條FSADD指令。當同時需要并行執行兩個浮 點加法時，可以保證使用上兩個浮點運算部件，而在編譯器上層進行編譯轉換時就 無須考慮了。3.3 支持帶預測的匯編指令(predicated execution) 在匯編指令級的優化當中，消除分支是經常采用的技術，因為分支的存在會大大限制指令并行度，因此我們經常采用預測技術來進行分支的轉化和消除。盡管采用profile等靜態分析技術可以找出最常使用的分支以進行預測，但是錯誤的預測也是時有發生的。因此，對于那些很難預測該走哪些分支的程序，在消除分支時往往需要有帶預測的匯編指令（predicated execution）的支持。例如：如下有四個基本塊的程序，采用帶預測的匯編指令之后，可消除分支，轉換為一個 基本塊，這樣在一個基本塊中可以更容易的提高指令并行度。4Inst1Inst2Cmp a=b p1, p2Inst3 p1 | inst5 p2Inst4 p1 | inst6 p2Inst 7Inst 8b0: Inst3Inst4Br b3Inst1Inst2Br a=b, b2采用predicated executionb1:Inst5Inst6b2:Inst7Inst8b3:cmp執行之后將對p1和p2這兩個標識進行賦值，隨后再根據p1和p2的真假來決定是執行inst3, inst4還是inst5, inst6。 帶預測的匯編指令就是由一般的指令帶上標識位的判斷，根據對標識位的判斷結果來決定是否執行該指令。通常的RISC匯編指令集不提供帶預測的匯編指令，這滿足不了上述分支消除技術的要求。因此，VLIW編譯器應該支持帶預測的匯編指令Page: 7？，以便實現上述這種常用的分支消除技術。具體做法是：在匯編指令助記符寫法上，如同上例，只需要多加上一個標識，指明該指令在執行時依賴于對哪個標識的判斷即可；在硬件具體實現上，則可以有兩種做法，一種是在指令本身的編碼中就加入需要判斷的標識位，一種是由條件判斷算子配合指令一起完成。以常用的雙操作數運算指令為例：通常的雙操作數運算指令的編碼：指令功能控制域操作數來源一選通域操作數來源二選通域硬件實現方法一：將所需的標識直接放入指令的編碼，不使用時為通常的指令，使用 時即成為帶預測的匯編指令。指令功能控制域操作數來源一選通域操作數來源二選通域P1P2P3 標識IA64即采用這種方式來提供對預測的支持，但是這種方式會導致指令本身編碼位的增加，而且當機器提供標識較多的時候，這種方式有一定的局限。6硬件實現方法二：指令本身的編碼不做改變，硬件提供一個條件判斷算子，其編碼為真有效/假有效（1位）標識來源選通域（N位）由標識來源選通域來決定到底當前判斷哪個具體的標識( N = log2 機器標識個數 )這樣的話，一般指令的實現可不做變化，當需要支持預測時，用條件判斷算子加以配合，以決定指令是否需要執行。結束語 筆者所在的實驗室目前正在為一款我國自主設計的VLIW體系結構的新型CPU開發優化編譯器，本文提出的與機器相關的優化方案及相關思路，從