ISSN 1009 -3044E-mail: xsjl@ccc.net.cnComputer Knowedge and Technology電脯知識(shí)與技術(shù)htp://www.dnzs.net.cnVol.5,No.24, August 2009, pp.7035- -7037Tel:+86- -551-5690963 5690964基于Tree--SSA優(yōu)化框架的高級(jí)循環(huán)優(yōu)化楊夏(湖南科技職業(yè)學(xué)院.湖南長(zhǎng)鈔410004)摘要:現(xiàn)代的計(jì)算機(jī)處理器和計(jì)算機(jī)系統(tǒng)實(shí)現(xiàn)了很多先進(jìn)技術(shù)，要利用這些技術(shù)更需要編譯器的支持以取得高性能。GCC中Tree SSA 優(yōu)化框架提供了一個(gè)功能強(qiáng)大的程序分析框架。增強(qiáng)的數(shù)據(jù)依賴分析信息允許編譯器變換一個(gè)算法以取得更大的局部性,提高資源的利用率以增大吞吐量,提高性能。該文對(duì)數(shù)據(jù)依賴、矩陣變換、循環(huán)變換進(jìn)行了研究,分析了它們的特點(diǎn),算法和性能,陳述了GCC中循環(huán)變換的現(xiàn)狀,對(duì)以后的研究做出了一定的展望。關(guān)鍵詞:敏據(jù)依賴;遞歸鏈;矩陣變換;循環(huán)依賴,循環(huán)變換,Tree SSA中圈分類號(hào):TP202文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):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é)計(jì)算和企業(yè)計(jì)算的挑戰(zhàn)，所以GCC也面臨同樣的挑戰(zhàn)?，F(xiàn)代的計(jì)算機(jī)處理器和計(jì)算機(jī)系統(tǒng)都實(shí)現(xiàn)了很多先進(jìn)技術(shù),要利用這些特點(diǎn)更需要編譯器的支持以取得高性能。許多之前已開發(fā)的用于向量和并行體系結(jié)構(gòu)的技術(shù)，在超標(biāo)量和超長(zhǎng)指令字計(jì)算機(jī)體系結(jié)構(gòu)Overview of LNO以及具有較大存儲(chǔ)延遲、更復(fù)雜功能部件流水線、多級(jí)cache的計(jì)算機(jī)系統(tǒng)中有了新的應(yīng)用。GCC中TreeSSA優(yōu)化框架提供了-個(gè)程序分析的功能強(qiáng)大的框架。增強(qiáng)的數(shù)據(jù)依賴分析信息允許編譯器變換- -個(gè)算法以取得更大的局部性,提高資源的利用皋以Laop Nest Opininer Rranch增大吞吐量,提高性能。GCC的循環(huán)嵌套優(yōu)化器將功能強(qiáng)大的循環(huán)嵌套分析器與矩Cm陣變換引擎相結(jié)合,提供了一個(gè)可擴(kuò)展的循環(huán)變換優(yōu)化器,循環(huán)變換優(yōu)化器進(jìn)行幺模(5-變換和編放操作(ecaling operations)。數(shù)據(jù)相關(guān)分析器是基于- -個(gè)新算法來跟蹤歸納變量而不局限于某一特定模式。矩陣變換功能使用一個(gè)類似積木的設(shè)計(jì).允許利用該血Analyer3 Optinizers矩陣變換功能去實(shí)現(xiàn)許多通用的優(yōu)化工具程序。某些專有的商業(yè)編譯器中使用了類似的矩陣變換工具。圖1 GCC的循環(huán)嵌套優(yōu)化器圖1數(shù)據(jù)依賴分析經(jīng)過genericiation和gimplfcation后，被編譯的語言循環(huán)結(jié)構(gòu)變成了與命令式語言相同的低級(jí)結(jié)構(gòu):三地址賦值語句.goto語句,標(biāo)號(hào)語句。為了從程序的GIMPIE表示形式中檢索傳統(tǒng)的循環(huán)表示,就要檢測(cè)自然循環(huán)(natualloop),然后基于對(duì)包含在循環(huán)體內(nèi)的語句的分析.檢測(cè)循環(huán)索引和循環(huán)邊界。通過分析循環(huán)中標(biāo)量變量的更新屬性,抽取循環(huán)的迭代次數(shù)和允許對(duì)于任一給定迭代次數(shù)可以快速計(jì)算變量的值的表示形式,有了這兩者后,可能將復(fù)制常量傳播遍擴(kuò)展到跨循環(huán)之后,消除冗余檢查。還可以進(jìn)行這樣的分析:抽取數(shù)組訪問對(duì)存儲(chǔ)空間的讀和寫的關(guān)系的表示，進(jìn)行傳統(tǒng)的數(shù)據(jù)相關(guān)分析。分析器提取的信息使用遞歸鏈來記錄。這種表示形式使用牛頓插值公式.允許快速計(jì)算一個(gè)函數(shù)在一個(gè)給定的整數(shù)點(diǎn)的值。我們介紹遞歸鏈的基于它們的表示的直觀描述.然后將遞歸鏈的記號(hào)與多項(xiàng)式函數(shù)聯(lián)系起來。遞歸鏈所表示的主要的屬性是一一個(gè)程序在存儲(chǔ)位置上的迭代執(zhí)行。每個(gè)存儲(chǔ)點(diǎn)包含有一個(gè)循環(huán)的人口點(diǎn)。在循環(huán)執(zhí)行期間,存儲(chǔ)的值隨著更新語句的操作而變化。更新表達(dá)式的描述嵌人在遞歸鏈的表示中,這樣就可能從遞歸鏈的表示中檢索到原來程序的表示形式。換句話說.僅選取感興趣的標(biāo)量屬性,不能確定的標(biāo)量屬性描述成未知元素。1.1遞歸鏈遞歸鏈- -中國(guó)煤化工收稿日期:2009-04-21YHCNMHG基金項(xiàng)目:國(guó)家863軟件專項(xiàng)資助(202AA1Z2101、2004AA1Z2210)作者簡(jiǎn)介:楊夏(1976-),女,湖南常德人,講師,碩士研究生,主要研究方向?yàn)槌绦蛟O(shè)計(jì)語言與編譯系統(tǒng)。本欄目責(zé)任編輯:邀媛媛....系統(tǒng)軟件與軟件工程..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初始化為遞歸鏈的系數(shù)。然后,這些寄存器的值在遞歸鏈指定的索引的循環(huán)中更新:圖1中的循環(huán)中,寄存器r2的值在循環(huán)中更新,它的演化由{1,*,2}1遞歸鏈描述。r1從它的初始值0開始累加r2的后繼值,因此r1由{.+{1,*,2]11}1遞歸鏈描述。遞歸鏈二中寄存器r6可以用多變量的標(biāo)量演化{7,8,+,9}2| 來描述。r6 的值在循環(huán)2中累加包含在循環(huán)1中變化的rS中的值遞歸鏈(..CJ在給定整數(shù)點(diǎn)x的計(jì)算通過下面的公式(其系數(shù)為整系數(shù)(...).來進(jìn)行(.+.+.C.}>=.2 a( )在線性遞歸鏈的特殊情況下,這個(gè)公式成為:{base,+,stepl(x)base+step*x。其中base和step是兩個(gè)整數(shù)常量。遞歸鏈可以處理符號(hào)系數(shù),但是在這種情況下，上面的計(jì)算公式不總是成立。1.2剝離遞歸鏈(peeled chres)我們提出了傳統(tǒng)遞歸鏈表示的另一個(gè)擴(kuò)展，以便可以表示對(duì)初始值在第-次迭代時(shí)就會(huì)被改寫的變量。由于剝離遞歸鏈的出現(xiàn),我們選擇了一種與SSA phi 結(jié)點(diǎn)相類似的語法,由于剝離遞歸鏈的符號(hào)就是循環(huán)phi結(jié)點(diǎn)自己。剝離鏈的語義如下所示:(a.bk=[a, 當(dāng)循環(huán)的第-次迭代時(shí)，lb,否則a和b是兩個(gè)可能是符號(hào)形式的遞歸鏈。只要循環(huán)phi結(jié)點(diǎn)沒有在SSA圖中定義--個(gè)強(qiáng)連通部件就構(gòu)建一個(gè)剝離遞歸鏈。2矩陣變換使用基矩陣變換而不是連續(xù)進(jìn)行幾次循環(huán)變換的原因很多。首先,能夠以一種簡(jiǎn)單得多的方法將多個(gè)變換組合為-一個(gè),這就使得基矩陣變換的功能很強(qiáng)。然而任何描述的變換能用--串簡(jiǎn)單的循環(huán)變換來表示,但是確定應(yīng)用這些簡(jiǎn)單循環(huán)變換的次序以取得所要求的變換不是- -件容易的事。盡管如此,利用一個(gè)變換矩陣,能夠直接生成所需要的變換。此外,確定一個(gè)給定變換的合法性是-一個(gè)簡(jiǎn)單的乘法操作。使用的算法也允許進(jìn)行部分變換。D01IJGCC使用的代碼生成算法是基于Li Wei的Lambda循環(huán)變換工具組件。它使用整數(shù)格作(:)為循環(huán)嵌套的模型并使用非平凡矩陣作為變換的模型。實(shí)現(xiàn)的算法支持任何邊界可能表示為BDDO一組線性表達(dá)式的循環(huán),其中每個(gè)線性表達(dá)式可能包括循環(huán)不變量通過應(yīng)用這些變換到圖27中的循環(huán)所產(chǎn)生的循環(huán)分別如8,9,10,11中所示。這組操作包含每個(gè)幺模運(yùn)算(交換,反向,和偏斜)與縮放。將縮放加到適用的變換表示任何非平凡矩陣都能應(yīng)用于循環(huán),因?yàn)樗鼈兌寄鼙贿€原為上述循環(huán)變換操作的組合?？s放在循環(huán)分片和分布存儲(chǔ)(6;)AC:V-Vn代碼生成的環(huán)境下是很有用處的。合法性測(cè)試簡(jiǎn)單地通過將循環(huán)的依賴向量乘上變換矩陣,并判斷所得到的結(jié)果依賴向量Fpntopcting是否是詞法序?yàn)檎?。這會(huì)保證數(shù)據(jù)依賴在生成的循環(huán)嵌套中不會(huì)被改變。完整的程序允許完成包含有該循環(huán)的某部分所需變換的變換矩陣，在某種程度上與整個(gè)循環(huán)的循環(huán)依賴相- -致。3實(shí)現(xiàn)與應(yīng)用.GCC的線性循環(huán)變換分為幾個(gè)部分:- -個(gè)矩陣數(shù)學(xué)引擎,一個(gè)變換引擎,和轉(zhuǎn)換器。矩陣數(shù)DOUU學(xué)引擎實(shí)現(xiàn)了執(zhí)行變換(反向,計(jì)算Hermite形式,乘法等等)所必需的各種向量和矩陣數(shù)學(xué)子(:)" o程序。變換引擎實(shí)現(xiàn)了合法性測(cè)試,重寫循環(huán)邊界.重寫循環(huán)體,以及完成部分變換。使用GCC來變換一個(gè)循環(huán)，首先需要將這個(gè)循環(huán)變換為一種代碼生成算法可用的形式。ripre 1位stendbop這是一一個(gè)簡(jiǎn)單的函數(shù),通過輸人一個(gè)GCC的循環(huán)結(jié)構(gòu)并產(chǎn)生一個(gè)變換中國(guó)煤化工(a-)構(gòu)。這個(gè)循環(huán)嵌套結(jié)構(gòu)由-組表示每個(gè)循環(huán)邊界的線性方程組成。下來我們已提供了一個(gè)函數(shù),輸入一個(gè)循環(huán)嵌套結(jié)構(gòu)和一個(gè)變換矩陣,如果HCNMHG處函數(shù)主要對(duì)于那些通過完整算法不能產(chǎn)生的變換有用,這是因?yàn)樵摻M件僅產(chǎn)生合法變換。第m1:Rnendbop三,利用前面描述的代碼生成算法重寫循環(huán)嵌套結(jié)構(gòu)的循環(huán)邊界。最后,我們把循環(huán)嵌套結(jié)構(gòu)困2循環(huán)變化圖.7036”系統(tǒng)軟件與軟件工程....本欄目責(zé)任編輯;謝嫗媛第5卷第24期(2009年 8月)Computer Knolege and Technolgy電腩知識(shí)與技術(shù)轉(zhuǎn)換為CIMPlE/Tree SSA代碼。這個(gè)子程序接受一個(gè)循環(huán)嵌套結(jié)構(gòu)并重寫與之匹配的10實(shí)際的循環(huán)嵌套代碼。這包含兩個(gè)步驟:首先生成新的迭代變量.循環(huán)邊界,和循環(huán)結(jié)束條件。其次將循環(huán)體轉(zhuǎn)換為消除了之前使用的迭代變量的形式。這個(gè)過程是直觀的:給定一個(gè)源迭代變量的向量Si和目標(biāo)迭代變量的向量Sj,以及一個(gè)變換矩陣T,這個(gè)函數(shù)使用方程.根據(jù)月標(biāo)迭代變量來計(jì)算源迭代變量。對(duì)循環(huán)中的每個(gè)語句都進(jìn)行這樣的計(jì)算,并且用新的語句代瞽舊的語句?；诰仃嚨难h(huán)變換能用來提高并行化和向量化(通過消除阻止代人的內(nèi)層循環(huán)rguar inerchenged依賴)的有效性。也能用于執(zhí)行優(yōu)化Cache重用的時(shí)間和空間局部性優(yōu)化。這些類型的優(yōu)困3矩陣循環(huán)變換有效性比較圍化有潛力顯普提高應(yīng)用程序和benchmark的分值。研究表明,依賴于應(yīng)用程序的特點(diǎn),與未修改的算法相比較，存儲(chǔ)局部性優(yōu)化能產(chǎn)生2到50的加速比。作為加速比的一個(gè)例子，我們將利用一個(gè)眾所周知的SPECTCPU2000benchmark,SWIM。SWIM將大部分時(shí)間消耗在單層循環(huán)上。通過簡(jiǎn)單地交換這個(gè)循環(huán).可能提高七倍的性能.如圖所示。新的數(shù)據(jù)依賴和矩陣變換功能允許GCC去實(shí)現(xiàn)循環(huán)嵌套優(yōu)化以顯著提升應(yīng)用程序的性能。這些優(yōu)化包括:循環(huán)交換,循環(huán)展開和合并.循環(huán)融臺(tái).循環(huán)分裂,循環(huán)反轉(zhuǎn),以及循環(huán)偏斜。循環(huán)交換交換循環(huán)的次序以更好地將循環(huán)操作數(shù)與系統(tǒng)特征匹配.比如,改善存儲(chǔ)層次訪問模式或者暴露沒有依賴的循環(huán)迭代以便允許向量化。當(dāng)變換后的執(zhí)行安全時(shí).優(yōu)化的循環(huán)次序依賴于目標(biāo)系統(tǒng)。依賴于所要的效果,交換能將最大相關(guān)性的循環(huán)交換到循環(huán)嵌套內(nèi)的較內(nèi)層的位置或者是較外層的位置。由于存在別名和數(shù)據(jù)依賴信息，優(yōu)化的作用是有限的。擴(kuò)展和合并變換展開一個(gè)外層循環(huán)的迭代并隨后融合內(nèi)層循環(huán)的拷貝以取得較大的重用價(jià)值和隱費(fèi)功能單元的延遲。優(yōu)化的展開因子取決于調(diào)度和寄存器壓力。優(yōu)化與循環(huán)交換和循環(huán)展開有關(guān),所以,類似地,它需要準(zhǔn)確的別名和數(shù)據(jù)依賴信息。4研究展望提出能利用初始循環(huán)變換框架實(shí)現(xiàn)的循環(huán)變換后,其功能將被擴(kuò)展為其他眾所周知的循環(huán)優(yōu)化,比如循環(huán)分片,循環(huán)交錯(cuò),外層擴(kuò)展,以及支持三角形和梯形訪問模式。高級(jí)循環(huán)變換的目標(biāo)兩數(shù)取決于目標(biāo)系統(tǒng)。將目標(biāo)系統(tǒng)的特征傳到GCC循環(huán)優(yōu)化器正在進(jìn)行研究中。GCC的高級(jí)循環(huán)優(yōu)化框架在第--個(gè)發(fā)行版本中不會(huì)實(shí)現(xiàn)全部乃至大部分的循環(huán)變換-正在進(jìn)展之中，但現(xiàn)在有了一個(gè)好的成長(zhǎng)的開始。將來對(duì)框架的改進(jìn)將向兩個(gè)方向擴(kuò)展其功能:實(shí)現(xiàn)其他優(yōu)化和減小現(xiàn)存優(yōu)化的限制。變換首先必須是對(duì)于明確定義的數(shù)值行為的應(yīng)用程序是安全的。改進(jìn)優(yōu)化以識(shí)別更多和各種類型的循環(huán),從而從這些技術(shù)中獲益并提高應(yīng)用程序的性能。CCC中有兩遍循環(huán)優(yōu)化,一遍是在Tree SSA.上做循環(huán)優(yōu)化,另-遍是在RTL級(jí)做循環(huán)優(yōu)化。RTU(寄存器轉(zhuǎn)換語聞)上的循環(huán)優(yōu)化1) lop -iv.c RTL級(jí)的財(cái)納變量分析2) lop urol.循環(huán)展開和循環(huán)刺離3) lop-unswitch.ce循環(huán)unswitch4) lop- dolop.e用特定的低開銷的循環(huán)指令來修改迭代次數(shù)確定的循環(huán)。Tree -SSA上的循環(huán)優(yōu)化:在Tree -SSA 緒構(gòu)上進(jìn)行的循環(huán)變換:1) tree -saloop- -ch.c tree上的循環(huán)頭結(jié)點(diǎn)復(fù)制2) tree saloop- im.c循環(huán)不變量的移動(dòng)3) tree -s-loop-ivcanon.c 歸納變量的標(biāo)準(zhǔn)化4) lree -s-loop- -ivopts.c歸納變量?jī)?yōu)化5) te-esa-loop-manip.c高級(jí)循環(huán)操作函數(shù)6) teessa-loop- prefetch.c數(shù)組預(yù)取7) tree 8sa-loop- unswitch.c循環(huán)unswitching80 tree -oop linear.c線性 循環(huán)變換優(yōu)化Tree SSA上循環(huán)優(yōu)化能進(jìn)行為了某些并行執(zhí)行的循環(huán)交換以及循環(huán)反轉(zhuǎn),但是沒有考慮cache局部性,對(duì)于訪問模式與ceache中數(shù)組的存儲(chǔ)方式不協(xié)調(diào)的嵌套循環(huán)不能變換。不能對(duì)非緊嵌套循環(huán)進(jìn)行循環(huán)變換以優(yōu)化性能。存在數(shù)據(jù)依賴分析不夠準(zhǔn)確、對(duì)于多歸納變量分析不準(zhǔn)確,不能進(jìn)行循環(huán)偏斜變換的問題。GNU計(jì)劃在CCC3.5中加入Tree SsA優(yōu)化框架，這就為在Tree SSA上的優(yōu)化提出了時(shí)間表?？梢钥紤]建立一個(gè)代價(jià)模型函數(shù),計(jì)算變換后的效益.以決定是否進(jìn)行某一特定的循環(huán)變換。 完善線性循環(huán)變換.使其能正確完成幺模變換。在以上基礎(chǔ)上,再探討其他收效較大的循環(huán)優(yōu)化變換(集中于Tree -SSA 上的循環(huán)優(yōu)化)。如循環(huán)分塊,循環(huán)剝離,循環(huán)分裂,以及循環(huán)融合等等。參考文獻(xià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中國(guó)煤化工[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.現(xiàn)代體系結(jié)構(gòu)的優(yōu)化編譯器[M].張兆慶，喬如良,澤北京:機(jī)械工業(yè)出版社2004.本欄目責(zé)任編輯.謝媛媛....系統(tǒng)軟件與軟件工程.* 7037