基于LLVM驅(qū)動程序的編譯原理實踐教學(xué)改革

徐 偉，劉 碩，張 昱

（中國科學(xué)技術(shù)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230027）

0 引言

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

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

1 LLVM編譯實驗的挑戰(zhàn)與解決思路

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

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

2.1 實驗內(nèi)容

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

Fig.1 Overall design of the experimental content圖1 實驗內(nèi)容總體設(shè)計思路

2.2 程序理解實驗

該類實驗要求學(xué)員學(xué)習(xí)并理解LLVM驅(qū)動程序框架；掌握調(diào)用LLVM相關(guān)模塊產(chǎn)生多種中間表示的過程；理解驅(qū)動框架多種中間表示分析遍的構(gòu)建。自研的LLVM驅(qū)動程序框架如圖2所示，通過該驅(qū)動框架可以簡化LLVM應(yīng)用編程接口，掌握不同層次的中間表示，并易于實現(xiàn)學(xué)生自定義的程序分析遍。

Fig.2 LLVM driver framework圖2 LLVM驅(qū)動程序框架

2.3 示例代碼問答實驗

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

2.4 代碼開發(fā)實驗

該類實驗是在上述基礎(chǔ)上進(jìn)一步提高，讓學(xué)生完成指定功能的設(shè)計與代碼開發(fā)。

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

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

為了讓學(xué)生可以更好地進(jìn)行功能調(diào)用，驅(qū)動框架代碼已經(jīng)對常用接口完成了包裝。通過引導(dǎo)學(xué)生使用LLVM的相應(yīng)接口，讓學(xué)生了解到循環(huán)識別過程，同時可以讓學(xué)生接觸到業(yè)界前沿的產(chǎn)品級編譯器的具體實現(xiàn)方式。

2.5 擴(kuò)展實驗

擴(kuò)展實驗屬于第4個層次實驗，通過讓學(xué)生按照小組自行選擇相應(yīng)的題目，包括Clang靜態(tài)分析器閱讀實驗、基于LLVM IR的更多數(shù)據(jù)流分析和優(yōu)化實驗，也可以讓學(xué)生在此基礎(chǔ)上進(jìn)行自由發(fā)揮。

3 實驗組織實施

3.1 實驗環(huán)境與工具

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

Table 1 Experiment environment表1 實驗環(huán)境

3.2 實驗組織與考核方式

實驗組織上一般3～4人分為一組，由組長協(xié)調(diào)各組員進(jìn)行資料查詢、工程實踐和實驗匯報等工作。通過分組完成系統(tǒng)設(shè)計與實現(xiàn)，培養(yǎng)團(tuán)隊協(xié)作開發(fā)和項目管理能力，在分工、設(shè)計、實現(xiàn)、報告等環(huán)節(jié)訓(xùn)練協(xié)調(diào)配合能力。通過組內(nèi)討論、調(diào)研報告、驗收報告等方式培養(yǎng)專業(yè)相關(guān)的表達(dá)能力。

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

3.3 實驗效果與分析

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

在評分環(huán)節(jié)，對各小組進(jìn)行內(nèi)容完整度、答辯現(xiàn)場表現(xiàn)和參與度打分，評分由學(xué)生、教師和助教分別給出，最后按照權(quán)值合并。對于必做部分，有兩個小組的算法完整度、識別準(zhǔn)確度更高，獲得滿分；選做部分有6個小組獲得優(yōu)秀，3個小組獲得良好，總體完成效果良好。課后對學(xué)生進(jìn)行了相關(guān)調(diào)研，學(xué)生反映該實驗方案難度逐層遞進(jìn)，有助于他們了解了現(xiàn)代編譯器的發(fā)展方向，對系統(tǒng)能力和創(chuàng)新能力培養(yǎng)有積極效果。

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

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

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

3.4 實驗改進(jìn)方向

針對上述教學(xué)反饋，課程組認(rèn)為后續(xù)在實驗組織上可以進(jìn)行如下改進(jìn)：

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

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

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

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

4 結(jié)語

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