“編譯原理專題訓練”課程介紹

董 淵 王生原 張素琴

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

關鍵詞:編譯原理;實踐;開源軟件;GCC

中圖分類號:G642 文獻標識碼:B

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

1課程特色

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

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

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

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

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

采用開放的GCC和Open64軟件作為實驗平臺,引導學生積極參與大型開源軟件開發(fā)和維護活動,基于具有工業(yè)水準的真實軟件進行實踐活動,除編譯實踐之外,對于學生了解行業(yè)發(fā)展以及軟件工程素養(yǎng)的培養(yǎng)也具有很大價值。

2課程的重要性

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

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

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

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

3教學目標

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

第一是鞏固編譯原理的知識。學生們在編譯原理課程中學習了很多基本知識和原理,到底這些知識如何體現(xiàn)在實實在在的系統(tǒng)中?這是本課程的第一個目標。

第二是了解真實的編譯流程。課程講解從高級語言源程序到可執(zhí)行代碼的翻譯過程,以及可執(zhí)行代碼加載到內存的過程,同時也向學生介紹相關開源工具,并指導學生利用這些工具分析和了解這一過程。

第三是以GCC為例,剖析編譯器的整體框架、編譯流程和主要活動。有針對性地講解GCC中最關鍵的中間表示和翻譯步驟,幫助學生了解GCC從高級語言到匯編語言的翻譯方法,有針對性地改善編碼風格。

第四是開展編程實踐。真正深入到GCC和Open64編譯器內部,對其進行修改和擴充,經過這樣的鍛煉,學生將提高開發(fā)和維護大型、特大型軟件的能力。

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

4課程內容

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

4.1課堂講解

課程中針對GCC的講解內容包括:

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

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

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

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

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

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

4.2實踐安排

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

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

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

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

大致進度安排為:由同學在第1周開始自行提出選題,并經過和教師討論確定。第7周為開題報告,每個小組提交一份報告并進行口頭匯報,每兩周匯報和討論進展情況,最后三周進行項目匯報。

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

4.3課時安排

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

4.4實例介紹

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

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

這個題目看似簡單,實際難度很大。涉及到內嵌匯編這一C語言擴展支持和內核關鍵代碼,加之實驗之前Open64對于內嵌匯編只有一些初步支持,如果完成Kernel編譯所需要的內嵌匯編特性,需要Open64從前端內嵌匯編解析開始直到后端寄存器等比較深入的工作。

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

5考核方式

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

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

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

6總結

本文簡要介紹了清華大學計算機系“編譯原理專題訓

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

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

參考文獻:

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

[2] 李向榮,李蔚,段遠源. 研究型大學人才培養(yǎng)體系建設的新探索——清華大學“985工程”二期本科人才培養(yǎng)項目規(guī)劃及建設成效[J]. 清華大學教育研究,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.