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

董 淵 王生原 張素琴

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

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

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

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

1課程特色

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

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

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

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

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

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

2課程的重要性

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

從目前發展形勢來看,面向高性能計算的優化和針對嵌入系統的工作是編譯發展的兩個重要方向。

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

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

3教學目標

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

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

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

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

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

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

4課程內容

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

4.1課堂講解

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

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

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

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

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

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

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

4.2實踐安排

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

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

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

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

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

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

4.3課時安排

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

4.4實例介紹

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

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

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

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

5考核方式

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

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

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

6總結

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

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

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

參考文獻:

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

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