基于LLVM驅動程序的編譯原理實踐教學改革

徐 偉，劉 碩，張 昱

（中國科學技術大學 計算機科學與技術學院，安徽 合肥 230027）

0 引言

編譯原理是計算機學科的一門重要專業課，是列入國際ACM和IEEE計算機學科的主干課程，同時也是計算機專業課程中難度較大且非常挑戰學習能力的課程之一［1-4］。當前，國內大力發展自主可控的核心技術，學校也應相應地加強學生計算機系統能力培養，而學好學精編譯技術是培養大學生計算機系統能力的重要環節之一。編譯原理課程目標不僅讓學生對程序設計語言的理論和實現技術有深刻的理解，更重要的是結合課程實踐，使學生初步積累規模較大軟件的開發經驗，并能將課程討論的概念和技術運用到軟件設計、開發及科研工作中［5-9］。中國科學技術大學編譯原理課程教學所秉持的理念是遵循科教融合原則，將科學研究和教學研究中積累的經驗不斷融入課堂理論教學。實踐教學是課堂理論教學的試驗田，是訓練學生系統能力和創新能力的必然途徑，是“兩性一度”的最好體現［10-12］。

雖然編譯課程是中國科學技術大學計算機專業核心課程，但是從教學中發現學生的學習熱情并不高、系統能力和創新能力鍛煉不足。興趣缺失的原因包括教學內容的迭代更新不足，國內外教學普遍參考的《編譯原理》教材已經長達13年沒有更新，而編譯技術發展方興未艾，落后于新時代技術發展趨勢的教學內容，無法滿足新一代學生對新知識的渴望與訴求。對于系統能力和創新能力不足，課題組分析其原因主要在于，國內外普遍使用的簡易實驗體系無法體現系統復雜性，在工程量和挑戰度上沒有得到保證，導致學生們的能力鍛煉不足。為了讓學生更好地掌握現代編譯器設計原理，提高學習興趣，加強系統和創新能力培養，中國科學技術大學編譯原理課程組專門設計了一套項目型的教學實驗方案。該實驗方案適用于計算機專業的本科生、研究生，以及希望開展編譯學習的相關技術人員。需要注意的是，相較于傳統的編譯實驗，該實驗方案適合已經對編譯原理有初步了解的學生選修，而非作為學生的入門課程。實驗方案設計上將整個LLVM作為外部庫進行調用，通過自研的編譯驅動框架和程序分析示例，聚焦了技術發展方向，降低門檻并貼近業界前沿。通過實驗方案的使用，讓學生可以設計并實現出一個實際的編譯器，而不僅僅是“玩具型”的功能驗證。該實驗方案在2020年秋季學期編譯原理和技術課程中進行了首次教學實踐，學生在完成常規編譯實驗（詞法分析器實驗、語法分析器實驗、語義檢查實驗等）后，繼續進行這種進階實驗，取得了較好的實驗效果。實驗方案基于開源編譯器LLVM進行設計，LLVM編譯器［13］的特點是設計上高度模塊化、可復用、易擴展、開源，并且采取Apache許可方式，工業界可以自由地在其上進行相關開發。

1 LLVM編譯實驗的挑戰與解決思路

基于LLVM進行實驗方案設計，最主要的挑戰就是LLVM超高的技術門檻。LLVM作為具有千萬行代碼級別的C++項目，使用了很多C++新特性，且項目本身也在不斷的快速發展，目前大約每3個月就會更新一次版本［14］，LLVM的這些顯著特點導致其本身入手門檻很高［15-16］。為了解決學生在較短的課程實驗中掌握并運用LLVM進行編譯器設計，需要在實驗方案設計上，既考慮降低實驗門檻難度，又能兼顧現代編譯器設計特點的展示。課程組針對性地開發了LLVM驅動程序，該驅動程序通過使用Clang/LLVM應用編程接口，將LLVM相關模塊作為外部庫進行調用，實現對輸入的源程序文件的解析，產生AST、LLVM IR等中間表示，并在這些中間表示上開展程序分析和變換。

2 基于LLVM驅動程序的編譯課程實驗方案

2.1 實驗內容

實驗內容總體設計思路如圖1所示，實驗分為程序理解、示例代碼問答、代碼開發、擴展實驗4個層次，難度層層遞進，共同組成一個相對完整的系列實驗方案。通過以上4個層次的系列實驗，讓學生完成會、能、通3個理解層次的逐漸深入，從而理解領會現代編譯器的設計特點。

Fig.1 Overall design of the experimental content圖1 實驗內容總體設計思路

2.2 程序理解實驗

該類實驗要求學員學習并理解LLVM驅動程序框架；掌握調用LLVM相關模塊產生多種中間表示的過程；理解驅動框架多種中間表示分析遍的構建。自研的LLVM驅動程序框架如圖2所示，通過該驅動框架可以簡化LLVM應用編程接口，掌握不同層次的中間表示，并易于實現學生自定義的程序分析遍。

Fig.2 LLVM driver framework圖2 LLVM驅動程序框架

2.3 示例代碼問答實驗

該類實驗要求學員學習使用LLVM驅動程序框架，并理解其中針對AST的查找回邊分析遍和針對LLVM IR的除零檢查分析遍。掌握兩種不同分析遍的組織形式、調用方式、處理過程，并完成相關問答。該類實驗的意義在于通過問答實驗，讓學生理解不同中間表示的特點和應用范圍，讓學生逐步通過使用懂得并能對相應問題進行回答和解決。

2.4 代碼開發實驗

該類實驗是在上述基礎上進一步提高，讓學生完成指定功能的設計與代碼開發。

實驗第一步，要求學生理解在現代編譯器中控制流分析的相關知識（支配、支配關系），以及利用支配關系尋找循環等基礎知識。由于技術的不斷進步，現代編譯器往往不會簡單使用書本介紹的算法，而是采用更加高效的算法完成相關控制流分析。例如在支配樹計算中，實驗內容會涉及LLVM在2017年以前的Lengauer-Tarjan算法［17］，以及2017年之后的Semi-NCA算法［18］。通過相關算法介紹，讓學生學會識別相應的循環，并感受到技術進步帶來的改變，激發學生的科研興趣。

第二步要求學生圍繞上述知識點，實現統計循環分析功能。學生可以根據LLVM提供的接口創建程序的控制流圖，生成支配樹和回邊信息，通過回邊信息快速識別循環。傳統的循環識別使用Tarjan算法查找強連通分量，在該步驟通過實際現狀對比，讓學生理解到傳統Tarjan算法的優劣點。

為了讓學生可以更好地進行功能調用，驅動框架代碼已經對常用接口完成了包裝。通過引導學生使用LLVM的相應接口，讓學生了解到循環識別過程，同時可以讓學生接觸到業界前沿的產品級編譯器的具體實現方式。

2.5 擴展實驗

擴展實驗屬于第4個層次實驗，通過讓學生按照小組自行選擇相應的題目，包括Clang靜態分析器閱讀實驗、基于LLVM IR的更多數據流分析和優化實驗，也可以讓學生在此基礎上進行自由發揮。

3 實驗組織實施

3.1 實驗環境與工具

本實驗基于LLVM 11.0.0版本進行設計，具體軟件實驗環境如表1所示，實驗框架已共享在https：//gitee.com/s4plus/llvm-ustc-proj/tree/master/my-llvm-driver，學生代碼也基于Gitee等開源倉庫進行管理和共享［19］。實驗涉及到對LLVM源碼的Debug調試，由于LLVM調試版本資源消耗巨大，超過一般計算機配置，課程組提供在線的LLVM調試服務器（lenovo System X 3650 M5），并為每個學生分配了在線賬號，學生可以通過在線方式，遠程完成代碼調試。在實驗進行過程中提供在線討論平臺，學生在線進行實驗問答和討論。

Table 1 Experiment environment表1 實驗環境

3.2 實驗組織與考核方式

實驗組織上一般3～4人分為一組，由組長協調各組員進行資料查詢、工程實踐和實驗匯報等工作。通過分組完成系統設計與實現，培養團隊協作開發和項目管理能力，在分工、設計、實現、報告等環節訓練協調配合能力。通過組內討論、調研報告、驗收報告等方式培養專業相關的表達能力。

考核方式包括實驗效果考核、小組答辯兩部分。實驗效果考核由助教對各組的實驗效果進行確認，判斷是否通過本次實驗；小組答辯包括各組對實驗的匯報答辯，評委由學生、助教和教師組成。評委對答辯人進行提問，并分別完成各組的答辯排名，最終答辯成績由各組的答辯排名和教師評分共同確定。

3.3 實驗效果與分析

在2020年秋季學期，學生們組成9支隊伍合作完成必做和選做部分。在選題環節，有4支隊伍選擇了“Clang靜態分析的理解與實踐”題目，有兩只隊伍選擇了“數據流分析”題目，還有另外3支隊伍選擇了“MLIR Toy的理解與實踐”這一基于更高層次的編譯系統框架-MLIR的題目。9支隊伍的學生們緊密合作，最后都實現了必做部分對于識別程序循環嵌套深度的要求，也都基本完成了選做題目的要求，并且部分隊伍主動深入LLVM框架內部，在對LLVM源碼進行大量閱讀的基礎上，實現了高效的分析優化或語義檢查功能模塊。實驗結束環節，各小組進行了公開答辯，其答辯視頻共享在https：//space.bilibili.com/273391839/。

在評分環節，對各小組進行內容完整度、答辯現場表現和參與度打分，評分由學生、教師和助教分別給出，最后按照權值合并。對于必做部分，有兩個小組的算法完整度、識別準確度更高，獲得滿分；選做部分有6個小組獲得優秀，3個小組獲得良好，總體完成效果良好。課后對學生進行了相關調研，學生反映該實驗方案難度逐層遞進，有助于他們了解了現代編譯器的發展方向，對系統能力和創新能力培養有積極效果。

由于綜合實驗文檔齊全，相關步驟列舉也比較詳細，學生們對于這一部分的反饋整體而言較為積極。根據后期收集的問卷，對該實驗給出肯定評價的原因主要包括如下幾點：①很多學生認為該實驗引入了LLVM Driver、LLVM IR等LLVM中的重要核心類，對于他們深入理解LLVM的相關機制起到了很大的幫助作用；②本實驗設計的重點是在LLVM IR上優化分析Pass，省去了從抽象語法樹構造LLVM IR的龐大工作量，使得學生們可以集中精力專注于實現代碼的優化；③選題內容不設限制，學生們可以根據自己的興趣完成不同的內容，并且配備了足夠多的助教（3名），助教有足夠的時間和能力給予指導。

通過問卷調查，也有學生反映存在以下問題待改進：①最終答辯環節，選題不同的組之間對于彼此的題目互相了解較少，匯報前對于其他選題的內容要補充閱讀相關文檔才能了解其他人的內容，最后答辯時的提問和討論有些局限，難以展開；②個別組之間的選題有重疊部分，沒有充分擴展到各細分領域內，如選擇“數據流分析”的組不約而同都去實現基于循環的代碼變化，而對于過程間優化、并行優化等均未涉及。

實驗過程中，課程組還觀察到學生們容易存在調研不充分、對LLVM框架及其相關接口掌握不完全、對實際代碼中可能存在的計算或漏洞模式不甚了解、對于編譯技術領域的分析技術缺少認識等問題，進而可能會導致開發進度緩慢、重復造輪子、難以實現有效的優化或檢查等問題。有的學生在分析課題時，由于對過程間調用分析、函數簽名等高階的程序分析相關概念并不了解，感覺到難以入手，始終無法確定合適的分析方法。最后，該課程組學生主動聯系教師和助教，利用一個下午的時間補充足夠的背景知識，確定了實現的技術路線，在程序的過程調用圖上，利用函數簽名和數據流分析相關技術，傳播文件指針狀態，最終達到了檢查文件指針安全性的目的。

3.4 實驗改進方向

針對上述教學反饋，課程組認為后續在實驗組織上可以進行如下改進：

（1）設計合理的實驗時間。由于編譯實驗的工作量一般都較大，需要教師和助教合理安排各實驗的截止時間節點，避免實驗的集中發布與提交，也避免實驗發布時間與本課程或其他課程的重要時間節點沖突。通過這種方式，適當減輕該實驗給學生帶來的課程壓力。

（2）提高答辯討論的效果。每一個被選擇的選題，可以根據各組中期提交情況，采取擇優挑選或者自愿報名的方式選出一個組，提前介紹該組的課題背景及調研結果，學生們可以單就選題背景等相關問題在本次交流中進行討論。這樣既有利于最終答辯報告的充分展開，又給各組學生以充分的思考和理解時間，對最后的討論交流起到較好幫助。此外，答辯組還需要介紹各自組內工作分工和工作內容比例，以此防止出現“抱大腿”情況。

（3）增加選題方向的獨特性。選題結束后，助教可以根據各組選題情況，讓各組的學生及時更新和修正本組的優化方向，避免方向上重合度較高的研究內容。

在驅動框架本身，課程組后續也有以下改進方向：①目前驅動框架可以完成將源文件解析為LLVM IR Module，并完成分析Pass的顯示，后續可增加后端處理（代碼生成）等方面的功能，進一步豐富驅動框架覆蓋的實驗范圍；②對驅動框架可以解析的輸入源文件的數量由現有的單個文件提升到多個文件，讓驅動框架適應于對于較大工程文件的解析和分析；③針對學生對于LLVM框架的不熟悉，編寫專門的示例說明程序和相關技術文檔，提高學生自學效率。

4 結語

本文在編譯實踐教學中引入正在革新演變中的新興編譯器LLVM，將其作為課堂理論教學的重要補充，并形成較為完整的實踐方案。在傳統編譯實驗的基礎上，增加新的實踐方案，培養學生調研及掌握新開發工具的能力，激發學生學習的熱情，加強其創新能力培養。通過實驗的實施有效促進了學生對于相關軟件工具的學習掌握。在實驗過程中，學生需要掌握軟件工程方法和工具（如Git版本管理、構建工具make或cmake、互聯網代碼倉庫GitHub和文檔倉庫GitBook等共享和協同工具）以及C/C++等語言的新特性和編程庫［20］。此外，學生基于LLVM驅動程序進行實驗，更有效地利用了實驗時間，減少在詞法分析、語法分析等基礎性實驗的時間投入，直接集中精力進行AST、LLVM IR的分析與優化，通過優化編譯器實驗，更好地理解現代編譯器的發展方向。并且，LLVM驅動框架程序給了學生學習LLVM的切入點，驅動框架程序可以像一把鑰匙讓學生更有針對性開展實驗，提高了學生對LLVM源代碼的閱讀和調試效率，有助于他們更好地理解現代編譯器的架構和特點。課程組已將相關實驗架構、答辯錄像等材料在網絡上進行公開，方便有需要的教師參考和交流。2021年，CCF中國軟件大會舉辦的軟件工程教學案例交流與競賽中，本實驗方案榮獲一等獎，得到眾多專家好評。課程組后續將根據教學反饋，持續優化實踐方案，促進編譯原理教學質量的進一步提升。