■郭靜

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

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

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

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

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

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

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

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

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

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

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

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

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

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

三、結(jié)語(yǔ)

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

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

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

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

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

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