優化編譯器的設計

■郭靜

編譯器的研究綜合了計算機科學中的操作系統、計算機系統結構、圖算法、人工智能等眾多領域，因此對編譯器的研究要求研究者在各方面都有很深的理解。編譯器的研究可以追溯到上世紀50年代。從Fortran語言出現的那天起，研究者們就在不斷地探索怎樣使高級語言編譯后能夠和機器語言編寫的程序具有相當的效率。Fortran語言的成功很大程度上得益于它從一開始就有很好的編譯器。隨著越來越多的高級語言的出現，計算機的應用領域越來越廣泛，編譯器所扮演的角色顯得越來越重要。

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

一、編譯器的結構

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

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

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

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

二、編譯器如何優化

編譯器的優化步驟在整個編譯器中是最重要的，也是最難的。它重要是因為一個編譯器的好壞主要就是看這個編譯器優化的效果是否良好。如果一個編譯器的優化效果很差，那么由該編譯器編譯出與用機器語言編寫的程序對系統資源的開銷是相當大的，而程序設計語言的設計者往往希望編譯器能夠編譯出與用機器語言編寫的程序效率相當的程序；它難是因為優化中的眾多問題都沒有定型的好算法。有些優化問題的求解甚至是不可計算的。現代系統結構中流水線，超標量以及多核處理器的出現無疑給編譯器的設計實現者加重了任務。

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

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

針對流水線的優化尤其需要注意代碼的順序以避免各種流水線冒險：結構冒險，當硬件知指令重疊執行中不能支持指令所有可能的組合時發生的資源冒險；數據冒險，在同時執行的幾條指令中，一條指令依賴于前一條指令的數據卻得不到時發生的冒險；控制冒險，流水線中的轉移指令或其他改寫程序計數器的指令造成的冒險?，F在的指令集系統和CPU設計一般不會出現結構冒險了。

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

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

三、結語

優化編譯器的設計是個既廣又深的話題，它不僅要應用計算機系統結構、人工智能等領域的前沿成果，還要求設計在軟件工程上給予足夠的考慮。尤其在現今還未能解決的諸多優化問題中，編譯器設計還需要和眾多學科共同發展，以求找到可行高效的解決方案。

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

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

[3]項煒.微型編譯器的實現及優化討論[D].電子科技大學,2007(03).

[4]杜靜.流體系結構的編譯技術研究[D].國防科學技術大學,2010(05).

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