基于Tree-SSA優(yōu)化框架的高級循環(huán)優(yōu)化

ISSN 1009 -3044E-mail: xsjl@ccc.net.cnComputer Knowedge and Technology電脯知識與技術(shù)htp://www.dnzs.net.cnVol.5,No.24, August 2009, pp.7035- -7037Tel:+86- -551-5690963 5690964基于Tree--SSA優(yōu)化框架的高級循環(huán)優(yōu)化楊夏(湖南科技職業(yè)學(xué)院.湖南長(cháng)鈔410004)摘要:現代的計算機處理器和計算機系統實(shí)現了很多先進(jìn)技術(shù)，要利用這些技術(shù)更需要編譯器的支持以取得高性能。GCC中Tree SSA 優(yōu)化框架提供了一個(gè)功能強大的程序分析框架。增強的數據依賴(lài)分析信息允許編譯器變換一個(gè)算法以取得更大的局部性,提高資源的利用率以增大吞吐量,提高性能。該文對數據依賴(lài)、矩陣變換、循環(huán)變換進(jìn)行了研究,分析了它們的特點(diǎn),算法和性能,陳述了GCC中循環(huán)變換的現狀,對以后的研究做出了一定的展望。關(guān)鍵詞:敏據依賴(lài);遞歸鏈;矩陣變換;循環(huán)依賴(lài),循環(huán)變換,Tree SSA中圈分類(lèi)號:TP202文獻標識碼:A文章編號:1009- -3044(2009)24 -7035- -03High Loop Optimization of the Tree SSA Optimization InfrastructureYANG Xia(Science and Technology Occupaion College of Hunan, Changsha 410004, China)Abstract: Modem compute processos and systemns have put many technologies into practice, while compliers make highpossible when these technologies are used.The Tree- SSA Optimization Infiastructure in GCC suppies a powerful program analysis frame-work.The enhanced data dependence analysis information allows complicrs to change the algorithm for widen locality .Whereby the uti-lizaton ratio of the tesources can be improved which leads to increasing throughput and higher performance.The study focuses on data de-pendence, matrix transform and cyclic ransformation by analyzing their features,lgorithm and performance and stating the staus quo ofGCC cyclic transfornation whereby outlook of the study has been made.Key words: data dependence; recursive chain; matix transform; cyclic transformation; Tree SSA由于GNU/Linux面臨高性能科學(xué)計算和企業(yè)計算的挑戰，所以GCC也面臨同樣的挑戰?，F代的計算機處理器和計算機系統都實(shí)現了很多先進(jìn)技術(shù),要利用這些特點(diǎn)更需要編譯器的支持以取得高性能。許多之前已開(kāi)發(fā)的用于向量和并行體系結構的技術(shù)，在超標量和超長(cháng)指令字計算機體系結構Overview of LNO以及具有較大存儲延遲、更復雜功能部件流水線(xiàn)、多級cache的計算機系統中有了新的應用。GCC中TreeSSA優(yōu)化框架提供了-個(gè)程序分析的功能強大的框架。增強的數據依賴(lài)分析信息允許編譯器變換- -個(gè)算法以取得更大的局部性,提高資源的利用皋以L(fǎng)aop Nest Opininer Rranch增大吞吐量,提高性能。GCC的循環(huán)嵌套優(yōu)化器將功能強大的循環(huán)嵌套分析器與矩Cm陣變換引擎相結合,提供了一個(gè)可擴展的循環(huán)變換優(yōu)化器,循環(huán)變換優(yōu)化器進(jìn)行幺模(5-變換和編放操作(ecaling operations)。數據相關(guān)分析器是基于- -個(gè)新算法來(lái)跟蹤歸納變量而不局限于某一特定模式。矩陣變換功能使用一個(gè)類(lèi)似積木的設計.允許利用該血Analyer3 Optinizers矩陣變換功能去實(shí)現許多通用的優(yōu)化工具程序。某些專(zhuān)有的商業(yè)編譯器中使用了類(lèi)似的矩陣變換工具。圖1 GCC的循環(huán)嵌套優(yōu)化器圖1數據依賴(lài)分析經(jīng)過(guò)genericiation和gimplfcation后，被編譯的語(yǔ)言循環(huán)結構變成了與命令式語(yǔ)言相同的低級結構:三地址賦值語(yǔ)句.goto語(yǔ)句,標號語(yǔ)句。為了從程序的GIMPIE表示形式中檢索傳統的循環(huán)表示,就要檢測自然循環(huán)(natualloop),然后基于對包含在循環(huán)體內的語(yǔ)句的分析.檢測循環(huán)索引和循環(huán)邊界。通過(guò)分析循環(huán)中標量變量的更新屬性,抽取循環(huán)的迭代次數和允許對于任一給定迭代次數可以快速計算變量的值的表示形式,有了這兩者后,可能將復制常量傳播遍擴展到跨循環(huán)之后,消除冗余檢查。還可以進(jìn)行這樣的分析:抽取數組訪(fǎng)問(wèn)對存儲空間的讀和寫(xiě)的關(guān)系的表示，進(jìn)行傳統的數據相關(guān)分析。分析器提取的信息使用遞歸鏈來(lái)記錄。這種表示形式使用牛頓插值公式.允許快速計算一個(gè)函數在一個(gè)給定的整數點(diǎn)的值。我們介紹遞歸鏈的基于它們的表示的直觀(guān)描述.然后將遞歸鏈的記號與多項式函數聯(lián)系起來(lái)。遞歸鏈所表示的主要的屬性是一一個(gè)程序在存儲位置上的迭代執行。每個(gè)存儲點(diǎn)包含有一個(gè)循環(huán)的人口點(diǎn)。在循環(huán)執行期間,存儲的值隨著(zhù)更新語(yǔ)句的操作而變化。更新表達式的描述嵌人在遞歸鏈的表示中,這樣就可能從遞歸鏈的表示中檢索到原來(lái)程序的表示形式。換句話(huà)說(shuō).僅選取感興趣的標量屬性,不能確定的標量屬性描述成未知元素。1.1遞歸鏈遞歸鏈- -中國煤化工收稿日期:2009-04-21YHCNMHG基金項目:國家863軟件專(zhuān)項資助(202AA1Z2101、2004AA1Z2210)作者簡(jiǎn)介:楊夏(1976-),女,湖南常德人,講師,碩士研究生,主要研究方向為程序設計語(yǔ)言與編譯系統。本欄目責任編輯:邀媛媛....系統軟件與軟件工程..7035Computer Knowledge and Technloy電脯知諷與技術(shù)第5卷第24期(2009年8月)r1=0r2=1r3=2loor2*=r3endl:遞歸鏈二r4= 9Loop(1)loop(2)r6 += r5end25 +=r4end1遞歸鏈一中寄存器r1,r2,t3初始化為遞歸鏈的系數。然后,這些寄存器的值在遞歸鏈指定的索引的循環(huán)中更新:圖1中的循環(huán)中,寄存器r2的值在循環(huán)中更新,它的演化由{1,*,2}1遞歸鏈描述。r1從它的初始值0開(kāi)始累加r2的后繼值,因此r1由{.+{1,*,2]11}1遞歸鏈描述。遞歸鏈二中寄存器r6可以用多變量的標量演化{7,8,+,9}2| 來(lái)描述。r6 的值在循環(huán)2中累加包含在循環(huán)1中變化的rS中的值遞歸鏈(..CJ在給定整數點(diǎn)x的計算通過(guò)下面的公式(其系數為整系數(...).來(lái)進(jìn)行(.+.+.C.}>=.2 a( )在線(xiàn)性遞歸鏈的特殊情況下,這個(gè)公式成為:{base,+,stepl(x)base+step*x。其中base和step是兩個(gè)整數常量。遞歸鏈可以處理符號系數,但是在這種情況下，上面的計算公式不總是成立。1.2剝離遞歸鏈(peeled chres)我們提出了傳統遞歸鏈表示的另一個(gè)擴展，以便可以表示對初始值在第-次迭代時(shí)就會(huì )被改寫(xiě)的變量。由于剝離遞歸鏈的出現,我們選擇了一種與SSA phi 結點(diǎn)相類(lèi)似的語(yǔ)法,由于剝離遞歸鏈的符號就是循環(huán)phi結點(diǎn)自己。剝離鏈的語(yǔ)義如下所示:(a.bk=[a, 當循環(huán)的第-次迭代時(shí)，lb,否則a和b是兩個(gè)可能是符號形式的遞歸鏈。只要循環(huán)phi結點(diǎn)沒(méi)有在SSA圖中定義--個(gè)強連通部件就構建一個(gè)剝離遞歸鏈。2矩陣變換使用基矩陣變換而不是連續進(jìn)行幾次循環(huán)變換的原因很多。首先,能夠以一種簡(jiǎn)單得多的方法將多個(gè)變換組合為-一個(gè),這就使得基矩陣變換的功能很強。然而任何描述的變換能用--串簡(jiǎn)單的循環(huán)變換來(lái)表示,但是確定應用這些簡(jiǎn)單循環(huán)變換的次序以取得所要求的變換不是- -件容易的事。盡管如此,利用一個(gè)變換矩陣,能夠直接生成所需要的變換。此外,確定一個(gè)給定變換的合法性是-一個(gè)簡(jiǎn)單的乘法操作。使用的算法也允許進(jìn)行部分變換。D01IJGCC使用的代碼生成算法是基于Li Wei的Lambda循環(huán)變換工具組件。它使用整數格作(:)為循環(huán)嵌套的模型并使用非平凡矩陣作為變換的模型。實(shí)現的算法支持任何邊界可能表示為BDDO一組線(xiàn)性表達式的循環(huán),其中每個(gè)線(xiàn)性表達式可能包括循環(huán)不變量通過(guò)應用這些變換到圖27中的循環(huán)所產(chǎn)生的循環(huán)分別如8,9,10,11中所示。這組操作包含每個(gè)幺模運算(交換,反向,和偏斜)與縮放。將縮放加到適用的變換表示任何非平凡矩陣都能應用于循環(huán),因為它們都能被還原為上述循環(huán)變換操作的組合?？s放在循環(huán)分片和分布存儲(6;)AC:V-Vn代碼生成的環(huán)境下是很有用處的。合法性測試簡(jiǎn)單地通過(guò)將循環(huán)的依賴(lài)向量乘上變換矩陣,并判斷所得到的結果依賴(lài)向量Fpntopcting是否是詞法序為正的。這會(huì )保證數據依賴(lài)在生成的循環(huán)嵌套中不會(huì )被改變。完整的程序允許完成包含有該循環(huán)的某部分所需變換的變換矩陣，在某種程度上與整個(gè)循環(huán)的循環(huán)依賴(lài)相- -致。3實(shí)現與應用.GCC的線(xiàn)性循環(huán)變換分為幾個(gè)部分:- -個(gè)矩陣數學(xué)引擎,一個(gè)變換引擎,和轉換器。矩陣數DOUU學(xué)引擎實(shí)現了執行變換(反向,計算Hermite形式,乘法等等)所必需的各種向量和矩陣數學(xué)子(:)" o程序。變換引擎實(shí)現了合法性測試,重寫(xiě)循環(huán)邊界.重寫(xiě)循環(huán)體,以及完成部分變換。使用GCC來(lái)變換一個(gè)循環(huán)，首先需要將這個(gè)循環(huán)變換為一種代碼生成算法可用的形式。ripre 1位stendbop這是一一個(gè)簡(jiǎn)單的函數,通過(guò)輸人一個(gè)GCC的循環(huán)結構并產(chǎn)生一個(gè)變換中國煤化工(a-)構。這個(gè)循環(huán)嵌套結構由-組表示每個(gè)循環(huán)邊界的線(xiàn)性方程組成。下來(lái)我們已提供了一個(gè)函數,輸入一個(gè)循環(huán)嵌套結構和一個(gè)變換矩陣,如果HCNMHG處函數主要對于那些通過(guò)完整算法不能產(chǎn)生的變換有用,這是因為該組件僅產(chǎn)生合法變換。第m1:Rnendbop三,利用前面描述的代碼生成算法重寫(xiě)循環(huán)嵌套結構的循環(huán)邊界。最后,我們把循環(huán)嵌套結構困2循環(huán)變化圖.7036”系統軟件與軟件工程....本欄目責任編輯;謝嫗媛第5卷第24期(2009年 8月)Computer Knolege and Technolgy電腩知識與技術(shù)轉換為CIMPlE/Tree SSA代碼。這個(gè)子程序接受一個(gè)循環(huán)嵌套結構并重寫(xiě)與之匹配的10實(shí)際的循環(huán)嵌套代碼。這包含兩個(gè)步驟:首先生成新的迭代變量.循環(huán)邊界,和循環(huán)結束條件。其次將循環(huán)體轉換為消除了之前使用的迭代變量的形式。這個(gè)過(guò)程是直觀(guān)的:給定一個(gè)源迭代變量的向量Si和目標迭代變量的向量Sj,以及一個(gè)變換矩陣T,這個(gè)函數使用方程.根據月標迭代變量來(lái)計算源迭代變量。對循環(huán)中的每個(gè)語(yǔ)句都進(jìn)行這樣的計算,并且用新的語(yǔ)句代瞽舊的語(yǔ)句?；诰仃嚨难h(huán)變換能用來(lái)提高并行化和向量化(通過(guò)消除阻止代人的內層循環(huán)rguar inerchenged依賴(lài))的有效性。也能用于執行優(yōu)化Cache重用的時(shí)間和空間局部性?xún)?yōu)化。這些類(lèi)型的優(yōu)困3矩陣循環(huán)變換有效性比較圍化有潛力顯普提高應用程序和benchmark的分值。研究表明,依賴(lài)于應用程序的特點(diǎn),與未修改的算法相比較，存儲局部性?xún)?yōu)化能產(chǎn)生2到50的加速比。作為加速比的一個(gè)例子，我們將利用一個(gè)眾所周知的SPECTCPU2000benchmark,SWIM。SWIM將大部分時(shí)間消耗在單層循環(huán)上。通過(guò)簡(jiǎn)單地交換這個(gè)循環(huán).可能提高七倍的性能.如圖所示。新的數據依賴(lài)和矩陣變換功能允許GCC去實(shí)現循環(huán)嵌套優(yōu)化以顯著(zhù)提升應用程序的性能。這些優(yōu)化包括:循環(huán)交換,循環(huán)展開(kāi)和合并.循環(huán)融臺.循環(huán)分裂,循環(huán)反轉,以及循環(huán)偏斜。循環(huán)交換交換循環(huán)的次序以更好地將循環(huán)操作數與系統特征匹配.比如,改善存儲層次訪(fǎng)問(wèn)模式或者暴露沒(méi)有依賴(lài)的循環(huán)迭代以便允許向量化。當變換后的執行安全時(shí).優(yōu)化的循環(huán)次序依賴(lài)于目標系統。依賴(lài)于所要的效果,交換能將最大相關(guān)性的循環(huán)交換到循環(huán)嵌套內的較內層的位置或者是較外層的位置。由于存在別名和數據依賴(lài)信息，優(yōu)化的作用是有限的。擴展和合并變換展開(kāi)一個(gè)外層循環(huán)的迭代并隨后融合內層循環(huán)的拷貝以取得較大的重用價(jià)值和隱費功能單元的延遲。優(yōu)化的展開(kāi)因子取決于調度和寄存器壓力。優(yōu)化與循環(huán)交換和循環(huán)展開(kāi)有關(guān),所以,類(lèi)似地,它需要準確的別名和數據依賴(lài)信息。4研究展望提出能利用初始循環(huán)變換框架實(shí)現的循環(huán)變換后,其功能將被擴展為其他眾所周知的循環(huán)優(yōu)化,比如循環(huán)分片,循環(huán)交錯,外層擴展,以及支持三角形和梯形訪(fǎng)問(wèn)模式。高級循環(huán)變換的目標兩數取決于目標系統。將目標系統的特征傳到GCC循環(huán)優(yōu)化器正在進(jìn)行研究中。GCC的高級循環(huán)優(yōu)化框架在第--個(gè)發(fā)行版本中不會(huì )實(shí)現全部乃至大部分的循環(huán)變換-正在進(jìn)展之中，但現在有了一個(gè)好的成長(cháng)的開(kāi)始。將來(lái)對框架的改進(jìn)將向兩個(gè)方向擴展其功能:實(shí)現其他優(yōu)化和減小現存優(yōu)化的限制。變換首先必須是對于明確定義的數值行為的應用程序是安全的。改進(jìn)優(yōu)化以識別更多和各種類(lèi)型的循環(huán),從而從這些技術(shù)中獲益并提高應用程序的性能。CCC中有兩遍循環(huán)優(yōu)化,一遍是在Tree SSA.上做循環(huán)優(yōu)化,另-遍是在RTL級做循環(huán)優(yōu)化。RTU(寄存器轉換語(yǔ)聞)上的循環(huán)優(yōu)化1) lop -iv.c RTL級的財納變量分析2) lop urol.循環(huán)展開(kāi)和循環(huán)刺離3) lop-unswitch.ce循環(huán)unswitch4) lop- dolop.e用特定的低開(kāi)銷(xiāo)的循環(huán)指令來(lái)修改迭代次數確定的循環(huán)。Tree -SSA上的循環(huán)優(yōu)化:在Tree -SSA 緒構上進(jìn)行的循環(huán)變換:1) tree -saloop- -ch.c tree上的循環(huán)頭結點(diǎn)復制2) tree saloop- im.c循環(huán)不變量的移動(dòng)3) tree -s-loop-ivcanon.c 歸納變量的標準化4) lree -s-loop- -ivopts.c歸納變量?jì)?yōu)化5) te-esa-loop-manip.c高級循環(huán)操作函數6) teessa-loop- prefetch.c數組預取7) tree 8sa-loop- unswitch.c循環(huán)unswitching80 tree -oop linear.c線(xiàn)性 循環(huán)變換優(yōu)化Tree SSA上循環(huán)優(yōu)化能進(jìn)行為了某些并行執行的循環(huán)交換以及循環(huán)反轉,但是沒(méi)有考慮cache局部性,對于訪(fǎng)問(wèn)模式與ceache中數組的存儲方式不協(xié)調的嵌套循環(huán)不能變換。不能對非緊嵌套循環(huán)進(jìn)行循環(huán)變換以?xún)?yōu)化性能。存在數據依賴(lài)分析不夠準確、對于多歸納變量分析不準確,不能進(jìn)行循環(huán)偏斜變換的問(wèn)題。GNU計劃在CCC3.5中加入Tree SsA優(yōu)化框架，這就為在Tree SSA上的優(yōu)化提出了時(shí)間表?？梢钥紤]建立一個(gè)代價(jià)模型函數,計算變換后的效益.以決定是否進(jìn)行某一特定的循環(huán)變換。 完善線(xiàn)性循環(huán)變換.使其能正確完成幺模變換。在以上基礎上,再探討其他收效較大的循環(huán)優(yōu)化變換(集中于Tree -SSA 上的循環(huán)優(yōu)化)。如循環(huán)分塊,循環(huán)剝離,循環(huán)分裂,以及循環(huán)融合等等。參考文獻:[1] Novillo D,Red Hat Canada, Ld Tree ssa.A New Opimization Ifrastucture for GCC [C_.tawaCaproccedings of the 2003 CCCSummit,2003.[2] Meril J.GENERIC and GIMPLE:A New Tree Representation for Entire Functions [C.tawa,Cana:proceedings of the 2003 CCC[3] Eigler F Ch.MudIlap:Pointer Use Checking for C++.C0tawa:Proceedin中國煤化工[4]} The GNU Compiler olleltion[EB//Tt://gcc.gnu.org.[5] Robert A, van Engelen,Birch J.Kyle A Callivan Aray Data Dependence:MYHC N M H Gices Agebra[J.W ashington,DC,USA:IEEE Computer Society,2004.[6] Alen R,Kennedy K.現代體系結構的優(yōu)化編譯器[M].張兆慶，喬如良,澤北京:機械工業(yè)出版社2004.本欄目責任編輯.謝媛媛....系統軟件與軟件工程.* 7037