優(yōu)化編譯器的設(shè)計

■郭靜

編譯器的研究綜合了計算機科學(xué)中的操作系統(tǒng)、計算機系統(tǒng)結(jié)構(gòu)、圖算法、人工智能等眾多領(lǐng)域，因此對編譯器的研究要求研究者在各方面都有很深的理解。編譯器的研究可以追溯到上世紀50年代。從Fortran語言出現(xiàn)的那天起，研究者們就在不斷地探索怎樣使高級語言編譯后能夠和機器語言編寫的程序具有相當(dāng)?shù)男省ortran語言的成功很大程度上得益于它從一開始就有很好的編譯器。隨著越來越多的高級語言的出現(xiàn)，計算機的應(yīng)用領(lǐng)域越來越廣泛，編譯器所扮演的角色顯得越來越重要。

隨著現(xiàn)代先進的計算機系統(tǒng)結(jié)構(gòu)（Computer Architecture）的出現(xiàn)，現(xiàn)代化編譯器（Optimizing Compiler）的能力也越來越強大，編譯出的程序的效率也越來越高。最初的編譯器已經(jīng)遠遠不能和現(xiàn)代先進的編譯器相提并論了，但是今天編譯器仍有許多可以改進的地方，這就需要我們進行更深入的研究。

一、編譯器的結(jié)構(gòu)

編譯器的結(jié)構(gòu)包括詞法分析器(Lexical Analyzer)，語法分析器（Syntax Parser），語言分析器（Semantic Analyzer）,中間代碼生成器（Intermediate Code Generator），代碼優(yōu)化器（Code Optimizer），符號表（Symbol Table）,錯誤處理器（Error Handler）。詞法分析器直到中間代碼生成器又稱為前端（Front End），代碼優(yōu)化器到代碼生成器又稱后端（Back End）。這個界限并不是嚴格的，而且有些研究者喜歡把優(yōu)化過程獨立提出來討論。這樣的分層是很有工程價值的，在大型的多語言的編譯系統(tǒng)中，任何語言的編譯器都共用一個后端，因為后端與高級語言之間幾乎沒有聯(lián)系，大多與機器相關(guān)；如果有開發(fā)者想在某編譯系統(tǒng)中添加一種語言的編譯功能，只需編寫該語言的前端即可；如果需要將已有的編譯器移植到新機器上，只需重新編寫一個與機器相關(guān)的后端即可，前端可以不加修改或者稍作修改后重復(fù)使用。以前要編在m種機器上運行，能編譯n種語言的編譯系統(tǒng)，需要編寫n*m個不同的編譯器；而按照這種工程分層，則只需編寫n個前端以及m個后端即可。著名的編譯系統(tǒng)GCC(GNU Compiler Collection)就是按照這種工程分層方式開發(fā)的。

詞法分析器的實現(xiàn)主要依靠有窮自動機（Finiter Automata）理論。有窮自動機可以識別正則表達式，而NFA可由查表程序模擬來識別高級語言中的“詞”，然后生成一個符號表，并將源文件里的每個“詞”用一個詞素標(biāo)記（Token）來代替。語法分析器的實現(xiàn)則依靠上下文無關(guān)文法（context-Free Grammar）理論以及下推式自動機（Pushdown Automata）理論。由于現(xiàn)代高級語言的語法定義都是以BNF范式給出的，因此用上下文無關(guān)文法理論可以很好的解決編譯中語法分析這一環(huán)節(jié)。語法分析主要有LL(1)分析，LR(1)分析，LALR(1)分析等，這正體現(xiàn)出人們在編譯器這一領(lǐng)域中的研究成果?，F(xiàn)代大部分高級語言編譯器使用的是LALR(1)分析。

以上兩個過程若手寫程序?qū)崿F(xiàn)很機械也很容易出錯，因此人們想到了用計算機自動生成詞法分析器和語法分析器的代碼。有兩個很著名的工具Lex和Yacc以及它們的現(xiàn)代加強版本Flex和Bison就是分別用來自動生成詞法分析器和語法分析器的代碼的。語言分析主要是檢查語法分析生成的語法數(shù)結(jié)構(gòu)中是否有錯，同時為進一步地生成中間代碼做準(zhǔn)備。

中間代碼生成和優(yōu)化實際上是一個可以循環(huán)執(zhí)行的過程。每次優(yōu)化都生成中間代碼，而每次優(yōu)化都有不同的目的，并且這些不同次的優(yōu)化是互不影響的，不同的優(yōu)化方面的先后順序不同，對最終的結(jié)果也是有影響的。后文將重點結(jié)合現(xiàn)代計算機系統(tǒng)結(jié)構(gòu)來討論一起優(yōu)化過程中可能遇到的問題，以及需要注意的一些事項。由于這個話題范圍相當(dāng)廣，況且優(yōu)化這一塊不象前端那樣有堅實的理論基礎(chǔ)且都有固定的優(yōu)秀算法，其中某些問題甚至是NPC類問題，只有用近似的圖論算法或者啟發(fā)式搜索來得到一個較優(yōu)化結(jié)果；有些優(yōu)化甚至是無法在編譯時刻確定最優(yōu)情況的，必須在運行時進行優(yōu)化，這類問題編譯器是無法解決的。而解釋性的語言如Java,Lisp，Python的解釋器有可能做到這一層優(yōu)化，但目前還沒有這方面的有效實現(xiàn)。因此本論文全部的論題是不現(xiàn)實的，只能討論到其中很小的一部分。

二、編譯器如何優(yōu)化

編譯器的優(yōu)化步驟在整個編譯器中是最重要的，也是最難的。它重要是因為一個編譯器的好壞主要就是看這個編譯器優(yōu)化的效果是否良好。如果一個編譯器的優(yōu)化效果很差，那么由該編譯器編譯出與用機器語言編寫的程序?qū)ο到y(tǒng)資源的開銷是相當(dāng)大的，而程序設(shè)計語言的設(shè)計者往往希望編譯器能夠編譯出與用機器語言編寫的程序效率相當(dāng)?shù)某绦?；它難是因為優(yōu)化中的眾多問題都沒有定型的好算法。有些優(yōu)化問題的求解甚至是不可計算的?，F(xiàn)代系統(tǒng)結(jié)構(gòu)中流水線，超標(biāo)量以及多核處理器的出現(xiàn)無疑給編譯器的設(shè)計實現(xiàn)者加重了任務(wù)。

優(yōu)化的正確性原則是優(yōu)化前后的代碼對于任何輸入（合法或者非法），都應(yīng)給出相同的結(jié)果。這條原則是顯然的，但并不是總那么容易做到。曾經(jīng)有一段時間，GCC在Intel的機器上對浮點數(shù)的存取優(yōu)化就沒能做到這一點。優(yōu)化代碼的提供者沒有考慮到Intel的FPU是擴展的80位的，因此對于float,double類型在寄存器中的數(shù)據(jù)和存在內(nèi)存中的數(shù)據(jù)是不一樣的，即使邏輯上相等的數(shù)據(jù)拿寄存器中的與內(nèi)存中的比較也會得到不相等的結(jié)果，優(yōu)化者期望通過將臨時變量存在寄存器中以獲取效率，但導(dǎo)致了與未優(yōu)化的代碼產(chǎn)生不同輸出的結(jié)果。

普通優(yōu)化一般都會經(jīng)過以下幾個過程：常量轉(zhuǎn)換，將源文件中的常量變量及常量表達式都用其真實值來代替，這將可以節(jié)省一定的時間和空間；公共子表達式求值，將多次出現(xiàn)的子表達式預(yù)先求值，并存入臨時變量，這樣可以避免重復(fù)求值，但必須保證子表達式的值在任何地方都不會改變；冗余代碼的刪除，將那些并不會用到的代碼刪除；優(yōu)化存儲器，將頻繁使用的臨時變量放入寄存器中；表達式求值優(yōu)化，改變表達式求值順序，有時可能達到優(yōu)化目的；函數(shù)過程在線展開，將自程序代碼內(nèi)嵌到調(diào)用代碼中，這樣可以避免函數(shù)調(diào)用的開銷。普通優(yōu)化還有很多，此處只是試舉幾例。

針對流水線的優(yōu)化尤其需要注意代碼的順序以避免各種流水線冒險：結(jié)構(gòu)冒險，當(dāng)硬件知指令重疊執(zhí)行中不能支持指令所有可能的組合時發(fā)生的資源冒險；數(shù)據(jù)冒險，在同時執(zhí)行的幾條指令中，一條指令依賴于前一條指令的數(shù)據(jù)卻得不到時發(fā)生的冒險；控制冒險，流水線中的轉(zhuǎn)移指令或其他改寫程序計數(shù)器的指令造成的冒險。現(xiàn)在的指令集系統(tǒng)和CPU設(shè)計一般不會出現(xiàn)結(jié)構(gòu)冒險了。

數(shù)據(jù)冒險一般出在算術(shù)指令中，這是編譯器最好解決的一種冒險。出現(xiàn)這種冒險，最顯然的處理辦法是加上一條nop；但是這種處理方式既浪費了時間，又浪費了能量，如果編譯器能有效地調(diào)整指令順序，是有可能避免這兩種冒險的。如在MIPS的五段流水線中：

在此出現(xiàn)了數(shù)據(jù)冒險，如果沒有發(fā)生中斷，sub訪問r1時add還沒有及時更新r1中的內(nèi)容，因此sub會訪問到錯誤的數(shù)據(jù)。但如果編譯器將后面的一些不會干擾到這塊代碼、也不依賴于這塊代碼的指令加在這兩條指令中間，就可以避免這個數(shù)據(jù)冒險了。本節(jié)對一般的優(yōu)化方法和常見的問題做了簡單的介紹，還有很多深入的話題有待研究。

三、結(jié)語

優(yōu)化編譯器的設(shè)計是個既廣又深的話題，它不僅要應(yīng)用計算機系統(tǒng)結(jié)構(gòu)、人工智能等領(lǐng)域的前沿成果，還要求設(shè)計在軟件工程上給予足夠的考慮。尤其在現(xiàn)今還未能解決的諸多優(yōu)化問題中，編譯器設(shè)計還需要和眾多學(xué)科共同發(fā)展，以求找到可行高效的解決方案。

[1]楊思敏.出具證明編譯器中證明生成的研究[D].中國科學(xué)技術(shù)大學(xué),2010(01).

[2]袁麗娜.即時編譯器輔助的對象回收和空間復(fù)用[D].中國科學(xué)技術(shù)大學(xué),2010(07).

[3]項煒.微型編譯器的實現(xiàn)及優(yōu)化討論[D].電子科技大學(xué),2007(03).

[4]杜靜.流體系結(jié)構(gòu)的編譯技術(shù)研究[D].國防科學(xué)技術(shù)大學(xué),2010(05).

[5]何炎祥,劉陶,吳偉.可信編譯器關(guān)鍵技術(shù)研究[J].計算機工程與科學(xué),2010(08).