基于Ｔｒｅｅ－ＳＳＡ優化框架的高級循環優化

摘要:現代的計算機處理器和計算機系統實現了很多先進技術，要利用這些技術更需要編譯器的支持以取得高性能。 GCC中Tree-SSA優化框架提供了一個功能強大的程序分析框架。增強的數據依賴分析信息允許編譯器變換一個算法以取得更大的局部性，提高資源的利用率以增大吞吐量，提高性能。該文對數據依賴、矩陣變換、循環變換進行了研究，分析了它們的特點，算法和性能，陳述了GCC中循環變換的現狀，對以后的研究做出了一定的展望。

關鍵詞:數據依賴;遞歸鏈;矩陣變換;循環依賴，循環變換，Tree-SSA

中圖分類號:TP202文獻標識碼:A文章編號:1009-3044(2009)24-7035-03

High Loop Optimization of the Tree-SSA Optimization Infrastructure

YANG Xia

(Science and Technology Occupation College of Hunan， Changsha 410004， China)

Abstract: Modern compute processors and systems have put many technologies into practice， while compliers make high-performance possible when these technologies are used.The Tree-SSA Optimization Infrastructure in GCC supplies a powerful program analysis framework.The enhanced data dependence analysisinformation allows compliers to change the algorithm for widen locality .Whereby the utilization ratio of the resources can be improved which leads to increasing throughput and higher performance.The study focuses on data dependence， matrix transform and cyclic transformation by analyzing their features，algorithm and performance and stating the status quo of GCC cyclic transformation whereby outlook of the study has been made.

Key words: data dependence; recursive chain; matrix transform; cyclic transformation; Tree-SSA

由于GNU/Linux面臨高性能科學計算和企業計算的挑戰，所以GCC也面臨同樣的挑戰。現代的計算機處理器和計算機系統都實現了很多先進技術，要利用這些特點更需要編譯器的支持以取得高性能。許多之前已開發的用于向量和并行體系結構的技術，在超標量和超長指令字計算機體系結構以及具有較大存儲延遲、更復雜功能部件流水線、多級cache的計算機系統中有了新的應用。

GCC中TreeSSA優化框架提供了一個程序分析的功能強大的框架。增強的數據依賴分析信息允許編譯器變換一個算法以取得更大的局部性，提高資源的利用率以增大吞吐量，提高性能。GCC的循環嵌套優化器將功能強大的循環嵌套分析器與矩陣變換引擎相結合，提供了一個可擴展的循環變換優化器，循環變換優化器進行幺模變換和縮放操作(scaling operations)。數據相關分析器是基于一個新算法來跟蹤歸納變量而不局限于某一特定模式。矩陣變換功能使用一個類似積木的設計，允許利用該矩陣變換功能去實現許多通用的優化工具程序。某些專有的商業編譯器中使用了類似的矩陣變換工具。

1 數據依賴分析

經過genericiation和gimplification后，被編譯的語言循環結構變成了與命令式語言相同的低級結構:三地址賦值語句，goto語句，標號語句。為了從程序的GIMPLE表示形式中檢索傳統的循環表示，就要檢測自然循環(natual loop)，然后基于對包含在循環體內的語句的分析，檢測循環索引和循環邊界。通過分析循環中標量變量的更新屬性，抽取循環的迭代次數和允許對于任一給定迭代次數可以快速計算變量的值的表示形式，有了這兩者后，可能將復制常量傳播遍擴展到跨循環之后，消除冗余檢查。還可以進行這樣的分析:抽取數組訪問對存儲空間的讀和寫的關系的表示，進行傳統的數據相關分析。

分析器提取的信息使用遞歸鏈來記錄。這種表示形式使用牛頓插值公式，允許快速計算一個函數在一個給定的整數點的值。我們介紹遞歸鏈的基于它們的表示的直觀描述，然后將遞歸鏈的記號與多項式函數聯系起來。

遞歸鏈所表示的主要的屬性是一個程序在存儲位置上的迭代執行。每個存儲點包含有一個循環的入口點。在循環執行期間，存儲的值隨著更新語句的操作而變化。更新表達式的描述嵌入在遞歸鏈的表示中，這樣就可能從遞歸鏈的表示中檢索到原來程序的表示形式。換句話說，僅選取感興趣的標量屬性，不能確定的標量屬性描述成未知元素。

1.1 遞歸鏈

遞歸鏈一

r1 = 0

r2 = 1

r3 = 2

loop

r1 += r2

r2 *= r3

endl:

遞歸鏈二

r4 = 9

r5 = 8

r6 = 7

Loop(1)

loop(2)

r6 += r5

end2

r5 += r4

end1

遞歸鏈一中寄存器r1，r2，r3初始化為遞歸鏈的系數。然后，這些寄存器的值在遞歸鏈指定的索引的循環中更新:圖1中的循環中，寄存器r2的值在循環中更新，它的演化由{1，*，2｝1遞歸鏈描述。r1從它的初始值0開始累加r2的后繼值，因此r1由{0，+{1，*，2}1}1遞歸鏈描述。

遞歸鏈二中寄存器r6可以用多變量的標量演化{7，{8，+，9}2｝1 來描述。r6的值在循環2中累加包含在循環1中變化的r5中的值。

遞歸鏈{C0，+，...，CK}在給定整數點x的計算通過下面的公式(其系數為整系數(C0，...，CK)) 來進行:{C0，+，...，CK}(x)=Cixi在線性遞歸鏈的特殊情況下，這個公式成為:{base，+，step}(x)+base+step*x。 其中base和step是兩個整數常量。遞歸鏈可以處理符號系數，但是在這種情況下，上面的計算公式不總是成立。

1.2 剝離遞歸鏈(peeled chres)

我們提出了傳統遞歸鏈表示的另一個擴展，以便可以表示對初始值在第一次迭代時就會被改寫的變量。由于剝離遞歸鏈的出現，我們選擇了一種與SSAphi結點相類似的語法，由于剝離遞歸鏈的符號就是循環 phi結點自己。剝離鏈的語義如下所示:

a和b是兩個可能是符號形式的遞歸鏈。只要循環phi結點沒有在SSA圖中定義一個強連通部件就構建一個剝離遞歸鏈。

2 矩陣變換

使用基矩陣變換而不是連續進行幾次循環變換的原因很多。首先，能夠以一種簡單得多的方法將多個變換組合為一個，這就使得基矩陣變換的功能很強。然而任何描述的變換能用一串簡單的循環變換來表示，但是確定應用這些簡單循環變換的次序以取得所要求的變換不是一件容易的事。盡管如此，利用一個變換矩陣，能夠直接生成所需要的變換。此外，確定一個給定變換的合法性是一個簡單的乘法操作。使用的算法也允許進行部分變換。

GCC使用的代碼生成算法是基于Li Wei的Lambda 循環變換工具組件。它使用整數格作為循環嵌套的模型并使用非平凡矩陣作為變換的模型。實現的算法支持任何邊界可能表示為一組線性表達式的循環，其中每個線性表達式可能包括循環不變量

通過應用這些變換到圖2 7中的循環所產生的循環分別如8，9，10，11中所示。這組操作包含每個幺模運算(交換，反向，和偏斜)與縮放。將縮放加到適用的變換表示任何非平凡矩陣都能應用于循環，因為它們都能被還原為上述循環變換操作的組合。縮放在循環分片和分布存儲代碼生成的環境下是很有用處的。

合法性測試簡單地通過將循環的依賴向量乘上變換矩陣，并判斷所得到的結果依賴向量是否是詞法序為正的。這會保證數據依賴在生成的循環嵌套中不會被改變。

完整的程序允許完成包含有該循環的某部分所需變換的變換矩陣，在某種程度上與整個循環的循環依賴相一致。

3 實現與應用

GCC的線性循環變換分為幾個部分:一個矩陣數學引擎，一個變換引擎，和轉換器。矩陣數學引擎實現了執行變換(反向，計算Hermite形式，乘法等等)所必需的各種向量和矩陣數學子程序。變換引擎實現了合法性測試，重寫循環邊界，重寫循環體，以及完成部分變換。

使用GCC來變換一個循環，首先需要將這個循環變換為一種代碼生成算法可用的形式。這是一個簡單的函數，通過輸入一個GCC的循環結構并產生一個變換引擎可用的循環嵌套結構。這個循環嵌套結構由一組表示每個循環邊界的線性方程組成。下來，我們進行合法性測試。我們已提供了一個函數，輸入一個循環嵌套結構和一個變換矩陣，如果變換合法則返回true。這處函數主要對于那些通過完整算法不能產生的變換有用，這是因為該組件僅產生合法變換。第三，利用前面描述的代碼生成算法重寫循環嵌套結構的循環邊界。最后，我們把循環嵌套結構轉換為GIMPLE/Tree-SSA代碼。這個子程序接受一個循環嵌套結構并重寫與之匹配的實際的循環嵌套代碼。這包含兩個步驟:首先生成新的迭代變量，循環邊界，和循環結束條件。其次將循環體轉換為消除了之前使用的迭代變量的形式。這個過程是直觀的:給定一個源迭代變量的向量Si和目標迭代變量的向量Sj，以及一個變換矩陣T，這個函數使用方程，根據目標迭代變量來計算源迭代變量。對循環中的每個語句都進行這樣的計算，并且用新的語句代替舊的語句。

基于矩陣的循環變換能用來提高并行化和向量化(通過消除阻止代入的內層循環依賴)的有效性。也能用于執行優化Cache重用的時間和空間局部性優化。這些類型的優化有潛力顯著提高應用程序和benchmark的分值。研究表明，依賴于應用程序的特點，與未修改的算法相比較，存儲局部性優化能產生2到50的加速比。作為加速比的一個例子，我們將利用一個眾所周知的SPECT CPU2000 benchmark，SWIM。SWIM將大部分時間消耗在單層循環上。通過簡單地交換這個循環，可能提高七倍的性能，如圖所示。

新的數據依賴和矩陣變換功能允許GCC去實現循環嵌套優化以顯著提升應用程序的性能。這些優化包括:循環交換，循環展開和合并，循環融合，循環分裂，循環反轉，以及循環偏斜。循環交換交換循環的次序以更好地將循環操作數與系統特征匹配，比如，改善存儲層次訪問模式或者暴露沒有依賴的循環迭代以便允許向量化。當變換后的執行安全時，優化的循環次序依賴于目標系統。依賴于所要的效果，交換能將最大相關性的循環交換到循環嵌套內的較內層的位置或者是較外層的位置。由于存在別名和數據依賴信息，優化的作用是有限的。 擴展和合并變換展開一個外層循環的迭代并隨后融合內層循環的拷貝以取得較大的重用價值和隱藏功能單元的延遲。優化的展開因子取決于調度和寄存器壓力。優化與循環交換和循環展開有關，所以，類似地，它需要準確的別名和數據依賴信息。

4 研究展望

提出能利用初始循環變換框架實現的循環變換后，其功能將被擴展為其他眾所周知的循環優化，比如循環分片，循環交錯，外層擴展，以及支持三角形和梯形訪問模式。

高級循環變換的目標函數取決于目標系統。將目標系統的特征傳到GCC循環優化器正在進行研究中。

GCC的高級循環優化框架在第一個發行版本中不會實現全部乃至大部分的循環變換-正在進展之中，但現在有了一個好的成長的開始。將來對框架的改進將向兩個方向擴展其功能:實現其他優化和減小現存優化的限制。變換首先必須是對于明確定義的數值行為的應用程序是安全的。改進優化以識別更多和各種類型的循環，從而從這些技術中獲益并提高應用程序的性能。

GCC中有兩遍循環優化，一遍是在Tree-SSA上做循環優化，另一遍是在RTL級做循環優化。

RTL(寄存器轉換語言)上的循環優化

1) loop-iv.c RTL級的歸納變量分析

2) loop-unroll.c 循環展開和循環剝離

3) loop-unswitch.c 循環unswitch

4) loop-doloop.c 用特定的低開銷的循環指令來修改迭代次數確定的循環。

Tree-SSA上的循環優化:在Tree-SSA結構上進行的循環變換:

1) tree-ssa-loop-ch.c tree上的循環頭結點復制

2) tree-ssa-loop-im.c 循環不變量的移動

3) tree-ssa-loop-ivcanon.c 歸納變量的標準化

4) tree-ssa-loop-ivopts.c歸納變量優化

5) tree-ssa-loop-manip.c 高級循環操作函數

6) tree-ssa-loop-prefetch.c數組預取

7) tree-ssa-loop-unswitch.c 循環unswitching

80 tree-loop-linear.c線性循環變換優化

Tree-SSA上循環優化能進行為了某些并行執行的循環交換以及循環反轉，但是沒有考慮cache局部性，對于訪問模式與cache中數組的存儲方式不協調的嵌套循環不能變換。不能對非緊嵌套循環進行循環變換以優化性能。存在數據依賴分析不夠準確、對于多歸納變量分析不準確、不能進行循環偏斜變換的問題。

GNU 計劃在GCC3.5中加入Tree-SSA優化框架，這就為在Tree-SSA上的優化提出了時間表。可以考慮建立一個代價模型函數，計算變換后的效益，以決定是否進行某一特定的循環變換。完善線性循環變換，使其能正確完成幺模變換。在以上基礎上，再探討其他收效較大的循環優化變換(集中于Tree-SSA上的循環優化)，如循環分塊，循環剝離，循環分裂，以及循環融合等等。

參考文獻:

[1] Novillo D，Red Hat Canada， Ltd Tree ssa.A New Optimization Infrastructure for GCC[C].Ottawa，Canada:proceedings of the 2003 GCC Summit，2003.

[2] Merrill J.GENERIC and GIMPLE:A New Tree Representation for Entire Functions[C].Ottawa，Canada:proceedings of the 2003 GCC Summit，2003.

[3] Eigler F Ch.Mudflap:Pointer Use Checking for C/C++.[C].Ottawa:Proceedings of the 2003 GCC Summit，2003.

[4] The GNU Compiler Collection[EB/OL].http://gcc.gnu.org.

[5] Robert A， van Engelen，Birch J.Kyle A Gallivan Array Data Dependence Testing with the Chains of Recurrences Algebra[J].Washington，DC，USA:IEEE Computer Society，2004.

[6] Allen R，Kennedy K.現代體系結構的優化編譯器[M].張兆慶，喬如良，譯.北京:機械工業出版社，2004.