基于LLVM驱动程序的编译原理实践教学改革

徐 伟，刘 硕，张 昱

（中国科学技术大学 计算机科学与技术学院，安徽 合肥 230027）

编译原理是计算机学科的一门重要专业课，是列入国际ACM和IEEE计算机学科的主干课程，同时也是计算机专业课程中难度较大且非常挑战学习能力的课程之一［1-4］。当前，国内大力发展自主可控的核心技术，学校也应相应地加强学生计算机系统能力培养，而学好学精编译技术是培养大学生计算机系统能力的重要环节之一。编译原理课程目标不仅让学生对程序设计语言的理论和实现技术有深刻的理解，更重要的是结合课程实践，使学生初步积累规模较大软件的开发经验，并能将课程讨论的概念和技术运用到软件设计、开发及科研工作中［5-9］。中国科学技术大学编译原理课程教学所秉持的理念是遵循科教融合原则，将科学研究和教学研究中积累的经验不断融入课堂理论教学。实践教学是课堂理论教学的试验田，是训练学生系统能力和创新能力的必然途径，是“两性一度”的最好体现［10-12］。

虽然编译课程是中国科学技术大学计算机专业核心课程，但是从教学中发现学生的学习热情并不高、系统能力和创新能力锻炼不足。兴趣缺失的原因包括教学内容的迭代更新不足，国内外教学普遍参考的《编译原理》教材已经长达13年没有更新，而编译技术发展方兴未艾，落后于新时代技术发展趋势的教学内容，无法满足新一代学生对新知识的渴望与诉求。对于系统能力和创新能力不足，课题组分析其原因主要在于，国内外普遍使用的简易实验体系无法体现系统复杂性，在工程量和挑战度上没有得到保证，导致学生们的能力锻炼不足。为了让学生更好地掌握现代编译器设计原理，提高学习兴趣，加强系统和创新能力培养，中国科学技术大学编译原理课程组专门设计了一套项目型的教学实验方案。该实验方案适用于计算机专业的本科生、研究生，以及希望开展编译学习的相关技术人员。需要注意的是，相较于传统的编译实验，该实验方案适合已经对编译原理有初步了解的学生选修，而非作为学生的入门课程。实验方案设计上将整个LLVM作为外部库进行调用，通过自研的编译驱动框架和程序分析示例，聚焦了技术发展方向，降低门槛并贴近业界前沿。通过实验方案的使用，让学生可以设计并实现出一个实际的编译器，而不仅仅是“玩具型”的功能验证。该实验方案在2020年秋季学期编译原理和技术课程中进行了首次教学实践，学生在完成常规编译实验（词法分析器实验、语法分析器实验、语义检查实验等）后，继续进行这种进阶实验，取得了较好的实验效果。实验方案基于开源编译器LLVM进行设计，LLVM编译器［13］的特点是设计上高度模块化、可复用、易扩展、开源，并且采取Apache许可方式，工业界可以自由地在其上进行相关开发。

基于LLVM进行实验方案设计，最主要的挑战就是LLVM超高的技术门槛。LLVM作为具有千万行代码级别的C++项目，使用了很多C++新特性，且项目本身也在不断的快速发展，目前大约每3个月就会更新一次版本［14］，LLVM的这些显著特点导致其本身入手门槛很高［15-16］。为了解决学生在较短的课程实验中掌握并运用LLVM进行编译器设计，需要在实验方案设计上，既考虑降低实验门槛难度，又能兼顾现代编译器设计特点的展示。课程组针对性地开发了LLVM驱动程序，该驱动程序通过使用Clang/LLVM应用编程接口，将LLVM相关模块作为外部库进行调用，实现对输入的源程序文件的解析，产生AST、LLVM IR等中间表示，并在这些中间表示上开展程序分析和变换。

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.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框架的不熟悉，编写专门的示例说明程序和相关技术文档，提高学生自学效率。

本文在编译实践教学中引入正在革新演变中的新兴编译器LLVM，将其作为课堂理论教学的重要补充，并形成较为完整的实践方案。在传统编译实验的基础上，增加新的实践方案，培养学生调研及掌握新开发工具的能力，激发学生学习的热情，加强其创新能力培养。通过实验的实施有效促进了学生对于相关软件工具的学习掌握。在实验过程中，学生需要掌握软件工程方法和工具（如Git版本管理、构建工具make或cmake、互联网代码仓库GitHub和文档仓库GitBook等共享和协同工具）以及C/C++等语言的新特性和编程库［20］。此外，学生基于LLVM驱动程序进行实验，更有效地利用了实验时间，减少在词法分析、语法分析等基础性实验的时间投入，直接集中精力进行AST、LLVM IR的分析与优化，通过优化编译器实验，更好地理解现代编译器的发展方向。并且，LLVM驱动框架程序给了学生学习LLVM的切入点，驱动框架程序可以像一把钥匙让学生更有针对性开展实验，提高了学生对LLVM源代码的阅读和调试效率，有助于他们更好地理解现代编译器的架构和特点。课程组已将相关实验架构、答辩录像等材料在网络上进行公开，方便有需要的教师参考和交流。2021年，CCF中国软件大会举办的软件工程教学案例交流与竞赛中，本实验方案荣获一等奖，得到众多专家好评。课程组后续将根据教学反馈，持续优化实践方案，促进编译原理教学质量的进一步提升。

猜你喜欢编译器驱动程序选题基于相异编译器的安全计算机平台交叉编译环境设计铁道通信信号(2020年7期)2020-02-06本刊诚征“独唱团”选题时代邮刊(2019年24期)2019-12-17谈诗词的选题中华诗词(2019年1期)2019-08-23本刊诚征“独唱团”选题时代邮刊(2019年16期)2019-07-30本刊诚征“独唱团”选题时代邮刊(2019年18期)2019-07-29计算机硬件设备驱动程序分析电子制作(2018年17期)2018-09-28通用NC代码编译器的设计与实现组合机床与自动化加工技术(2014年10期)2014-03-01基于MPC8280的CPU单元与内部总线驱动程序设计电子设计工程(2014年19期)2014-02-27编译器无关性编码在微控制器中的优势单片机与嵌入式系统应用(2010年2期)2010-07-02基于ＡＲＭ嵌入式平台的ｘ８６译码ＳＯＣ架构设计现代电子技术(2009年8期)2009-06-25