“编译原理专题训练”课程介绍

董 渊 王生原 张素琴

摘要:“编译原理专题训练”是清华大学为计算机科学与技术系本科生开设的实践类限选课,旨在提高学生的实践能力。课程首次将开放源代码软件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.