董 淵 王生原 張素琴

摘要:“編譯原理專(zhuān)題訓(xùn)練”是清華大學(xué)為計(jì)算機(jī)科學(xué)與技術(shù)系本科生開(kāi)設(shè)的實(shí)踐類(lèi)限選課,旨在提高學(xué)生的實(shí)踐能力。課程首次將開(kāi)放源代碼軟件GCC和Open64作為實(shí)驗(yàn)框架引入實(shí)踐教學(xué),引導(dǎo)學(xué)生參與大型開(kāi)源軟件開(kāi)發(fā)和維護(hù)活動(dòng),基于具有工業(yè)水準(zhǔn)的真實(shí)軟件開(kāi)展實(shí)踐。本文重點(diǎn)介紹了該課程在我校開(kāi)設(shè)的基本情況,以期給大家更多的啟示。

關(guān)鍵詞:編譯原理;實(shí)踐;開(kāi)源軟件;GCC

中圖分類(lèi)號(hào):G642 文獻(xiàn)標(biāo)識(shí)碼:B

實(shí)踐能力是計(jì)算機(jī)專(zhuān)業(yè)學(xué)生走向未來(lái)科研和工作崗位最為重要的專(zhuān)業(yè)技能之一。清華大學(xué)歷來(lái)重視實(shí)踐教學(xué),在學(xué)校“985工程”二期本科人才培養(yǎng)項(xiàng)目的統(tǒng)一規(guī)劃框架下,我校從2003級(jí)本科生開(kāi)始,為計(jì)算機(jī)科學(xué)與技術(shù)系本科生開(kāi)設(shè)了一系列實(shí)踐類(lèi)限選課,“編譯原理專(zhuān)題訓(xùn)練”便是其中重要的一門(mén)。課程的目的是加強(qiáng)學(xué)生對(duì)系統(tǒng)軟件的理解和把握,幫助學(xué)生通過(guò)實(shí)踐的方式鞏固理論知識(shí),提高學(xué)生的軟件開(kāi)發(fā)能力。

1課程特色

清華大學(xué)“編譯原理”課程面向計(jì)算機(jī)專(zhuān)業(yè)所有學(xué)生,培養(yǎng)學(xué)生學(xué)習(xí)掌握本專(zhuān)業(yè)必備的編程語(yǔ)言設(shè)計(jì)實(shí)現(xiàn)原理與技術(shù),強(qiáng)調(diào)常見(jiàn)語(yǔ)言特征的實(shí)現(xiàn)原理與技術(shù),而不講授實(shí)際深層次語(yǔ)言特征的實(shí)現(xiàn),也不涉及培養(yǎng)可勝任工業(yè)界實(shí)際編譯系統(tǒng)開(kāi)發(fā)人員的需求。

“編譯原理專(zhuān)題訓(xùn)練”是“編譯原理”的后續(xù)課程和有效補(bǔ)充,是一門(mén)限選課程,一方面體現(xiàn)某些高級(jí)編譯技術(shù)的特點(diǎn)(如強(qiáng)調(diào)優(yōu)化技術(shù)等),另一方面可以為有興趣從事工業(yè)界實(shí)際編譯系統(tǒng)開(kāi)發(fā)工作(包括嵌入式系統(tǒng)開(kāi)發(fā))的學(xué)生提供必要的知識(shí)和技能儲(chǔ)備(開(kāi)源編譯系統(tǒng),相關(guān)工具鏈,參與實(shí)際的研究課題)。

因此,“編譯原理專(zhuān)題訓(xùn)練”講解部分基于工業(yè)界廣泛采用的開(kāi)源軟件GCC,具體內(nèi)容可瀏覽http://gcc.gnu.org,以編程語(yǔ)言編譯系統(tǒng)框架為主線安排實(shí)驗(yàn)。實(shí)驗(yàn)平臺(tái)則率先采用開(kāi)源軟件GCC和Open64,具體內(nèi)容可瀏覽http://open64.net,通過(guò)實(shí)驗(yàn)掌握詞法分析、語(yǔ)法分析、中間表示、優(yōu)化和目標(biāo)代碼生成以及交叉編譯方面的基本技術(shù)和相關(guān)工具。

GCC是應(yīng)用最廣泛的開(kāi)源編譯系統(tǒng)。該系統(tǒng)是整個(gè)開(kāi)源社區(qū)的基石,具有多語(yǔ)言、多目標(biāo)支持能力,是所有Linux系統(tǒng)和部分Unix系統(tǒng)的默認(rèn)編譯工具,在4.0以上版本中采用GENERIC、GIMPLE和RTL等三層中間表示,GCC后端采用表驅(qū)動(dòng)方式,可以人工方式構(gòu)造特定語(yǔ)言目標(biāo)機(jī)的描述文件(轉(zhuǎn)換表格)實(shí)現(xiàn)重定向,支持市場(chǎng)上絕大多數(shù)處理器。

Open64是另一個(gè)開(kāi)源編譯系統(tǒng),前身是SGI 公司用于64 位MIPS的Pro64編譯器,其后采用了開(kāi)放授權(quán)方式,稱為Open Research Compiler,簡(jiǎn)稱ORC,目前定名為Open64,其前端和GCC 4兼容,支持多種高級(jí)語(yǔ)言,后端支持Intel X86、Intel IA64、AMD64、MIPS(含國(guó)產(chǎn)龍芯)、ARM、PowerPC等多種體系結(jié)構(gòu)。該系統(tǒng)最初定位是高性能計(jì)算,采用了五層中間表示,便于各種優(yōu)化算法的實(shí)現(xiàn),因此可以生成質(zhì)量非常高的代碼,在性能方面具有非常強(qiáng)的競(jìng)爭(zhēng)力,得到研究領(lǐng)域和工業(yè)界的普遍認(rèn)可,目前在嵌入領(lǐng)域也有大量應(yīng)用。我們的科研團(tuán)隊(duì)是Open64的主要開(kāi)發(fā)者之一,貢獻(xiàn)了GCC擴(kuò)展支持、PowerPC后端和C++異常處理相關(guān)的重要代碼。Open64設(shè)計(jì)結(jié)構(gòu)良好,分析優(yōu)化全面,是編譯器高級(jí)研究項(xiàng)目的理想平臺(tái)。

采用開(kāi)放的GCC和Open64軟件作為實(shí)驗(yàn)平臺(tái),引導(dǎo)學(xué)生積極參與大型開(kāi)源軟件開(kāi)發(fā)和維護(hù)活動(dòng),基于具有工業(yè)水準(zhǔn)的真實(shí)軟件進(jìn)行實(shí)踐活動(dòng),除編譯實(shí)踐之外,對(duì)于學(xué)生了解行業(yè)發(fā)展以及軟件工程素養(yǎng)的培養(yǎng)也具有很大價(jià)值。

2課程的重要性

編譯系統(tǒng)是信息行業(yè)不可或缺的重要工具軟件,同時(shí)也是計(jì)算機(jī)科學(xué)、技術(shù)和工程完美結(jié)合的一個(gè)典范。前端詞法、語(yǔ)法分析優(yōu)雅的數(shù)學(xué)基礎(chǔ)和相關(guān)自動(dòng)工具,編譯優(yōu)化精巧的算法和準(zhǔn)確高效的語(yǔ)義等價(jià)變換,以及中間表示獨(dú)立于語(yǔ)言和體系機(jī)構(gòu)的通用設(shè)計(jì),處處閃爍著智慧的光芒。因此,GCC和Open64這樣的開(kāi)源編譯系統(tǒng),既是編譯理論和技術(shù)的鮮活實(shí)例,也是軟件工程的成功范例。

從目前發(fā)展形勢(shì)來(lái)看,面向高性能計(jì)算的優(yōu)化和針對(duì)嵌入系統(tǒng)的工作是編譯發(fā)展的兩個(gè)重要方向。

前者是計(jì)算機(jī)誕生以來(lái)一直持續(xù)發(fā)展的主題,對(duì)于每一個(gè)國(guó)家來(lái)說(shuō),高性能計(jì)算都是具有戰(zhàn)略意義的課題,高性能計(jì)算的優(yōu)化在未來(lái)十幾年甚至幾十年仍將持續(xù)發(fā)展。隨著多核、眾核技術(shù)的發(fā)展,與之相關(guān)的編程語(yǔ)言、編程模型和優(yōu)化技術(shù)將是極為重要的研究?jī)?nèi)容。從編譯器的角度來(lái)講,這將涉及前端的語(yǔ)言和編程模型、后端的系統(tǒng)結(jié)構(gòu)支持以及與之相關(guān)的優(yōu)化和調(diào)試支持。

后者是面向嵌入領(lǐng)域的編譯后端的設(shè)計(jì)與優(yōu)化,是一個(gè)新興領(lǐng)域。以手機(jī)為代表的嵌入式系統(tǒng)的高速發(fā)展帶動(dòng)了嵌入式領(lǐng)域的研發(fā)和設(shè)計(jì),其中最重要的內(nèi)容是針對(duì)特定應(yīng)用需求,對(duì)軟件、硬件甚至指令系統(tǒng)進(jìn)行優(yōu)化。為了符合通話需求,可能會(huì)對(duì)芯片的指令作調(diào)整,調(diào)整之后則需要相應(yīng)的編譯工具支持,將高級(jí)語(yǔ)言程序翻譯為芯片能夠識(shí)別的指令序列。這種需求對(duì)編譯器后端設(shè)計(jì)提出了新的要求,包括具備可重定向能力的編譯系統(tǒng),以及針對(duì)嵌入系統(tǒng)、以代碼體積和軟件功耗為目標(biāo)的編譯優(yōu)化技術(shù)等。

3教學(xué)目標(biāo)

針對(duì)上述現(xiàn)狀以及我們對(duì)行業(yè)情況的初步分析,本課程的主要教學(xué)目標(biāo)如下:

第一是鞏固編譯原理的知識(shí)。學(xué)生們?cè)诰幾g原理課程中學(xué)習(xí)了很多基本知識(shí)和原理,到底這些知識(shí)如何體現(xiàn)在實(shí)實(shí)在在的系統(tǒng)中?這是本課程的第一個(gè)目標(biāo)。

第二是了解真實(shí)的編譯流程。課程講解從高級(jí)語(yǔ)言源程序到可執(zhí)行代碼的翻譯過(guò)程,以及可執(zhí)行代碼加載到內(nèi)存的過(guò)程,同時(shí)也向?qū)W生介紹相關(guān)開(kāi)源工具,并指導(dǎo)學(xué)生利用這些工具分析和了解這一過(guò)程。

第三是以GCC為例,剖析編譯器的整體框架、編譯流程和主要活動(dòng)。有針對(duì)性地講解GCC中最關(guān)鍵的中間表示和翻譯步驟,幫助學(xué)生了解GCC從高級(jí)語(yǔ)言到匯編語(yǔ)言的翻譯方法,有針對(duì)性地改善編碼風(fēng)格。

第四是開(kāi)展編程實(shí)踐。真正深入到GCC和Open64編譯器內(nèi)部,對(duì)其進(jìn)行修改和擴(kuò)充,經(jīng)過(guò)這樣的鍛煉,學(xué)生將提高開(kāi)發(fā)和維護(hù)大型、特大型軟件的能力。

第五是通過(guò)開(kāi)源軟件,參與了解世界上影響廣泛的開(kāi)源項(xiàng)目及其背后的自由軟件開(kāi)發(fā)方法。該開(kāi)發(fā)方法支撐著世界軟件產(chǎn)業(yè)的半壁江山。從桌面系統(tǒng)、服務(wù)器系統(tǒng)到嵌入式系統(tǒng)等不同領(lǐng)域,都包含或使用自由軟件產(chǎn)品,Linux Kernel、GCC、Emacs和Apache Web Server等高質(zhì)量、高市場(chǎng)占有率但非營(yíng)利的軟件對(duì)整個(gè)世界產(chǎn)生很大的影響。通過(guò)了解和參與這些軟件來(lái)了解開(kāi)源現(xiàn)象,探討這一現(xiàn)象的存在原因、發(fā)展趨勢(shì)和應(yīng)用前景,激發(fā)學(xué)生的思考。

4課程內(nèi)容

課程安排遵循科研工作的一般活動(dòng)規(guī)律。首先安排學(xué)生搜集查閱相關(guān)的文獻(xiàn)資料,了解相關(guān)國(guó)際會(huì)議的新進(jìn)展;隨后教師講解和小型實(shí)驗(yàn)熟悉工作的工具和對(duì)象,如GCC、Open64和Binary Utility二進(jìn)制工具等;接著引導(dǎo)學(xué)生提出問(wèn)題和項(xiàng)目初步意向,規(guī)劃相應(yīng)方案和計(jì)劃進(jìn)度并進(jìn)行評(píng)估,以確定課程大作業(yè);然后是提出問(wèn)題和方案后的實(shí)際研究和開(kāi)發(fā),根據(jù)完成結(jié)果的評(píng)測(cè)來(lái)改進(jìn)方案、繼續(xù)優(yōu)化。有些實(shí)驗(yàn)可以按照計(jì)劃完成,有些做到一定程度之后會(huì)發(fā)現(xiàn)更多、更難的問(wèn)題,這時(shí)需要引導(dǎo)學(xué)生正確對(duì)待并做深入分析,給出合適的評(píng)價(jià);最后是總結(jié)和報(bào)告。

4.1課堂講解

課程中針對(duì)GCC的講解內(nèi)容包括:

第一講通用編譯系統(tǒng)介紹。以GCC為例了解其工作步驟,通過(guò)解剖“helloworld.c”程序從源代碼到可執(zhí)行文件的過(guò)程,了解編譯各個(gè)階段的功能和輸入輸出,熟悉Binary Utilities工具的使用。

第二講Linker and Loader。介紹Link和定位的概念,了解可執(zhí)行文件的加載以及相關(guān)工具的使用。

第三講GCC框架。深入探索GCC,了解其發(fā)展歷程、GPL和自由軟件的發(fā)展、GCC的組織結(jié)構(gòu)(其前后端松散的結(jié)構(gòu),前端支持多種語(yǔ)言,后端支持多種體系結(jié)構(gòu))等。

第四講GCC Tree。Tree和前端是緊密聯(lián)結(jié)在一起的,它支持包括C、C++、Java、Ada在內(nèi)的多種語(yǔ)言。

第五講GCC中間RTL。講解RTL基本知識(shí)、GCC中間優(yōu)化的組織方式和特點(diǎn)。

第六講GCC后端。了解基于模式匹配的后端構(gòu)造方法。

4.2實(shí)踐安排

課程初期,基于自愿組合的原則,學(xué)生分為2～4人的小組,兩次書(shū)面作業(yè)和一次課程實(shí)踐大作業(yè)均以小組為單位完成。

書(shū)面作業(yè)一:與編譯相關(guān)的學(xué)術(shù)會(huì)議調(diào)研。利用互聯(lián)網(wǎng)資源,以小組為單位搜集POPL/PLDI/CC/CGO/LCTES等與編譯相關(guān)的最近3年的國(guó)際會(huì)議資料,每個(gè)小組針對(duì)某一次會(huì)議寫(xiě)出包括研究方向特點(diǎn)、人員和內(nèi)容分布、發(fā)展趨勢(shì)評(píng)價(jià)的調(diào)研資料,深入閱讀該會(huì)議中的某一篇論文,撰寫(xiě)對(duì)該論文的閱讀評(píng)價(jià),3 000～5 000字,會(huì)議名稱、年份、選讀論文不允許完全重復(fù)。

書(shū)面作業(yè)二:GCC重要文檔整理翻譯。包括The use of the GNU compilers和The internals of the GNU compilers。每個(gè)小組負(fù)責(zé)其中一部分,不允許重復(fù)。

課程實(shí)踐大作業(yè):采用開(kāi)放題目,即教師和助教不設(shè)定參考答案,全部交由學(xué)生自行探索研究。其來(lái)源有三:(1)學(xué)生自己設(shè)計(jì),或者其他課程中的和編譯相關(guān)的任務(wù);(2)參加自由軟件開(kāi)發(fā),完成某編譯系統(tǒng)的一個(gè)新功能或者特性;(3)教師結(jié)合科研和課程情況,專(zhuān)門(mén)設(shè)計(jì)任務(wù)。

大致進(jìn)度安排為:由同學(xué)在第1周開(kāi)始自行提出選題,并經(jīng)過(guò)和教師討論確定。第7周為開(kāi)題報(bào)告,每個(gè)小組提交一份報(bào)告并進(jìn)行口頭匯報(bào),每?jī)芍軈R報(bào)和討論進(jìn)展情況,最后三周進(jìn)行項(xiàng)目匯報(bào)。

要求分組獨(dú)立完成實(shí)驗(yàn)題目并給出測(cè)試方案,提交源代碼和實(shí)驗(yàn)報(bào)告,并能夠演示編程結(jié)果,做10～15分鐘的簡(jiǎn)要報(bào)告。所完成代碼和文檔均采用GPL發(fā)布。

4.3課時(shí)安排

本課程的課內(nèi)學(xué)時(shí)為2學(xué)時(shí),課外學(xué)時(shí)至少為2學(xué)時(shí)。本課程是一門(mén)實(shí)踐性很強(qiáng)的實(shí)驗(yàn)課程,學(xué)生以小組為單位,要搜集整理大量文獻(xiàn)資料,閱讀大量代碼并進(jìn)行代碼編寫(xiě)和修改,因此課程的理論講解內(nèi)容和實(shí)踐工作要適當(dāng)穿插進(jìn)行,通常安排單周講解,雙周安排實(shí)驗(yàn)和答疑,以便讓學(xué)生完成實(shí)驗(yàn)工作,并在第14～16周之間進(jìn)行實(shí)驗(yàn)檢查。

4.4實(shí)例介紹

課程實(shí)踐大作業(yè)選題的關(guān)鍵是和課程內(nèi)容相關(guān),能夠給學(xué)生以鍛煉,工作量適中,并具有較好的可操作性。

如在2008年,本課程的一個(gè)題目為“利用高性能Open64編譯器為X86處理器編譯Linux Kernel”,任務(wù)是利用當(dāng)時(shí)Open64的最新代碼,編譯當(dāng)時(shí)最新穩(wěn)定的Linux發(fā)布版本,內(nèi)核編譯配置為X86默認(rèn)配置。如大家所知,為方便代碼書(shū)寫(xiě)并提高效率,Linux Kernel中大量使用內(nèi)嵌匯編等GCC擴(kuò)展特性,內(nèi)核中諸如原子操作等關(guān)鍵代碼片段都采用內(nèi)嵌匯編來(lái)書(shū)寫(xiě),但是這些擴(kuò)展特性遠(yuǎn)遠(yuǎn)超出標(biāo)準(zhǔn)C規(guī)范,因此造成幾乎只能使用GCC來(lái)編譯Linux Kernel的局面。

這個(gè)題目看似簡(jiǎn)單,實(shí)際難度很大。涉及到內(nèi)嵌匯編這一C語(yǔ)言擴(kuò)展支持和內(nèi)核關(guān)鍵代碼,加之實(shí)驗(yàn)之前Open64對(duì)于內(nèi)嵌匯編只有一些初步支持,如果完成Kernel編譯所需要的內(nèi)嵌匯編特性,需要Open64從前端內(nèi)嵌匯編解析開(kāi)始直到后端寄存器等比較深入的工作。

共有兩個(gè)小組選擇了這一題目作為大作業(yè)項(xiàng)目。經(jīng)過(guò)努力,兩個(gè)小組共找到內(nèi)嵌匯編過(guò)程中的5個(gè)編譯錯(cuò)誤,提煉出5個(gè)測(cè)試用例,修正其中部分錯(cuò)誤并向Open64社區(qū)報(bào)告,并通過(guò)Kernel內(nèi)核代碼語(yǔ)義等價(jià)修改的方式解決其他問(wèn)題,成功編譯X86默認(rèn)配置下所有源代碼文件,之后還發(fā)現(xiàn)一個(gè)內(nèi)嵌匯編相關(guān)的連接錯(cuò)誤,圓滿完成任務(wù)。

5考核方式

課程采用公開(kāi)的方式進(jìn)行考核。為此,我們專(zhuān)門(mén)建立了課程網(wǎng)站,網(wǎng)址為http://soft.cs.tsinghua.edu.cn/blog/?q=course,所有課程相關(guān)的資料都通過(guò)該網(wǎng)站公布,目前已經(jīng)匯集了從課程準(zhǔn)備開(kāi)始到現(xiàn)在的所有資料,包括2006年開(kāi)課以來(lái)所有學(xué)生的作業(yè)和源代碼,面向全球公開(kāi)。

本課程也很重視學(xué)生講解和自我展示能力的培養(yǎng),專(zhuān)門(mén)提供機(jī)會(huì)讓學(xué)生主講,每人每次5～8分鐘,計(jì)入個(gè)人課堂成績(jī),分別進(jìn)行兩次小作業(yè)匯報(bào)及最終的大作業(yè)答辯和演示。

課程的成績(jī)分布為:個(gè)人課堂成績(jī)占40%,要求同學(xué)參加課堂討論,提出自己的觀點(diǎn)、實(shí)驗(yàn)題目等;兩次書(shū)面作業(yè)占20%,小組成績(jī),考察書(shū)面材料的完整性和準(zhǔn)確性;大作業(yè)占40%,小組成績(jī)。

6總結(jié)

本文簡(jiǎn)要介紹了清華大學(xué)計(jì)算機(jī)系“編譯原理專(zhuān)題訓(xùn)

練”課程的基本情況,本課程著眼于程序語(yǔ)言編譯原理、技術(shù)和實(shí)踐的結(jié)合,注重學(xué)生動(dòng)手能力的培養(yǎng),同時(shí)通過(guò)學(xué)生提出自選實(shí)驗(yàn)題目來(lái)培養(yǎng)他們的創(chuàng)新精神。此外,本課程也關(guān)注操作系統(tǒng)、系統(tǒng)結(jié)構(gòu)和程序設(shè)計(jì)語(yǔ)言等多學(xué)科、多課程內(nèi)容的交叉,幫助學(xué)生更為系統(tǒng)、完整地掌握計(jì)算機(jī)知識(shí)。

致謝:本課程得到清華大學(xué)“985工程”本科人才培養(yǎng)項(xiàng)目支持,本課程教材編寫(xiě)得到國(guó)家“十一五”規(guī)劃教材支持。感謝助教張宇宙、張楊、虞振樣、林明、李鑫、朱允敏、張鐸、曹震、王博等人的辛勤工作。

參考文獻(xiàn):

[1] 顧秉林. 論中國(guó)研究型大學(xué)的科研——關(guān)于清華大學(xué)科研工作新發(fā)展的思路[J]. 清華大學(xué)教育研究,2008,29(3):1-7.

[2] 李向榮,李蔚,段遠(yuǎn)源. 研究型大學(xué)人才培養(yǎng)體系建設(shè)的新探索——清華大學(xué)“985工程”二期本科人才培養(yǎng)項(xiàng)目規(guī)劃及建設(shè)成效[J]. 清華大學(xué)教育研究,2008,29(3):40-43.

[3]Mary Hall, David Padua, Keshav Pingali. Compiler Research: The Next 50 Years[J]. Communications of the ACM, 2009,52(2): 60-67.