基于代码优化的“编译原理”课程实践教学研究

王峰 阎娟 张浩军

关键词：编译原理；代码优化；实践教学

1引言

“编译原理”是一门重要的计算机专业课程，通过该课程的学习和实践，既可加深学生对程序设计语言的设计与实现等知识的综合理解，又可多角度地提高实践动手能力及综合应用能力[1-3]。特别是，“编译原理”课程与计算思维具有紧密的联系，为培养学生的计算思维能力提供了一个良好的平台[4]。但“编译原理”具有内容多、概念多、理论性强、高度抽象等特点，被普遍认为是一门既难教又难学的课程。

该课程中的代码优化主要是针对编译器，但大部分由编译器执行的优化仅涉及控制流程的简化和变量的访问方式等，并且由于大部分学生毕业后并不会从事编译器的设计工作，因此很多学生会觉得相关理论知识的作用不大。同时，随着计算机硬件技术的飞速发展，计算机的计算能力日益增强，因此学生在学习程序设计语言的时候将更多的精力放在了程序逻辑的实现上，而忽略了代码优化，从而导致学生对优化相关知识的重要性认识不足。实际上，代码优化在软件开发过程中，特别是在嵌入式等对实时性要求较高的系统开发中的作用是非常大的。本文针对工程型和应用型人才培养的目标，以图像处理中将RGB格式的彩色图像转换为灰度图像为例，探讨编译原理中代码优化相关技术在实际工程中的应用，以加深学生对编译理论知识的理解，建立理论和实际的联系，强化实践动手能力，从而提高学生的编程能力和综合素质。

2代码优化概述

代码优化是编译程序中的一个重要环节，其实质是对代码进行等价变换，目的是提高由编译程序生成的目标程序的质量，即加快目标程序的运行速度或减少目标程序所占的存储空间，或两者兼具[5-7]。

代码优化是为了编写出更高效的代码，故在进行代码优化时须遵循三个原则：（1）等价原则，即优化不能改变程序的运行结果；（2）有效原则，即优化后的代码应比未优化代码具有更高的时空效率；（3）盈利或合算原则，即优化带来的利益应大于优化工作所付出的代价。

按照与机器的关系，代码优化可分为与机器无关的优化和与机器相关的优化，二者在编译程序中所处的阶段是不一样的，前者是在源程序或中间代码上进行优化：后者是在目标代码上进行优化。在与机器无关的优化中，根据它所涉及的程序范围可分为局部优化、循环优化和全局优化三个不同的级别。局部优化是在基本块内的优化，循环优化是对循环中的代码进行优化，而全局优化则是在整个程序范围内的优化。优化方法包括数据流分析、控制流分析和程序变换等。代码优化的不同分类及相关优化技术如表1所列。

3代码优化实践教学

“编译原理”课程中的代码优化都是针对编译程序的中间代码和目标代码进行的，而学生平常接触更多的是源代码，并且将来也更多的是从事源代码的开发工作。因此，学生对相关理论知识在实际工程中的应用缺乏了解，从而对相关优化知识的掌握不够深入，也较难将相关优化知识应用于实际编程中。实际上，在嵌入式系统等实时性要求较高的应用中，代码优化是一个非常重要的环节。本节以图像处理中最基本的彩色图像转换为灰度图像为例，讨论相关编译优化知识在实际工程中的应用，以增进学生对编译优化知识的了解，提高学生的编程能力。

3.1问题描述

在图像模式识别工程中，为了便于处理和识别，经常需要将RGB格式的彩色图像转换为灰度图像，图像转换公式[8]为：

其中，R，G，B分别代表每个像素在RGB颜色空间中的红、绿和蓝三个颜色分量，Y为变换后所得灰度图像中像素的灰度级，其取值均为[0，255]的整数。本节中图像大小为720*576*24bit。

3.2优化实践

为实现上述功能，首先，定义如下数据结构：

步骤1：变换循环控制条件

上述代码是按照“先列后行”的顺序来对二维数组进行遍历的，而在C语言中，一个二维数组在计算机中存储时，是按照“先行后列”的顺序依次存储的。因此，“先列后行”遍历发生的页面交换次数要比“先行后列”多，且cache命中率相对较低。所以，通过调整语句顺序，变换循环控制条件，可以将上述函数修改为：

步骤2：数据结构优化

因图像为二维数据，故直接采用二维数组来存储图像数据，代码较直观、可读性强。但编译器处理二维数组的效率低于一维数组，因此可改用一维数组来存储图像数据，即将变量定义为：

经上述优化后，函数的运行时间下降为9.80ms。

步骤3：合并已知量，删除无用代码

上述代码循环内存在无用赋值的情况，删除多余变量和对应的赋值语句，合并已知量，即得：优化后函数的运行时间变为9.06ms。

步骤4：代数变换

上述代码中最主要的运算在于对每个像素点利用公式（1）进行的浮点数运算。显然，计算机对整数的运算速度要快于浮点运算，因此应用代数变换可将此操作改为整数运算，经此优化后，函数的运行日寸间进一步缩短为3.37ms。

步骤5：强度削弱（移位实现除法）

由于计算机的移位操作速度快于除法，因此可以利用移位操作来实现上述除法运算，从而降低运算强度，即将上述代码改为：经此优化后，函数的运行时间进一步减少为2.82ms。

步骤6：强度削弱（查表）

在上述代码中，每个像素的R，G和B值都需要进行乘法运算，由于这三个变量的取值范围均为[0，255]，因此可以通过在外定义查找表的方法来减少计算量，即将此范围内的值分别乘以306、601和1 17并进行移位操作，然后将计算得到的值用三个数组分别加以存储．即：

在此基础上，循环内的每个像素不须计算便可直接通过查找表的方法快速实现灰度转换

显然，这也是一种以牺牲内存为代价节省计算时间的方法，经过此优化后，函数运行时间进一步降低为1.93ms。

步骤7：循环展开

在上述代码的循环体内，因各像素的转换是独立进行的，不存在数据依赖，故可以进行循环展开，减少循环迭代次数，有利于CPU的流水线工作，从而提高运行速度。比如，将函数改为：

上文各步骤优化后的函数运行时间变化如图1所示。从图1可以看出，经过上述各步骤的优化后，函数运行时间从优化前的21.96ms下降为1.63ms，优化效果非常明显。

上述优化实例中包含局部优化、循环优化、与机器无关的优化和与机器相关的优化等知识。同时，为进一步增强学生的工程应用能力，在教学中还补充了对相关程序分析工具的介绍。在大型实际开发项目中，可以利用GProf和dotTrace等工具来发现程序中的瓶頸，并有针对性地进行代码优化，从而提高系统的运行效率。

4结束语

针对“编译原理”课程教学中的代码优化，本文在简要介绍其原理和相关优化技术的基础上，重点从实践教学的角度，以图像模式识别工程中的图像格式转换为例，探讨了相关编译优化技术在实际工程中的应用。通过面向实际应用的优化实践教学，有助于提高学生对课程的重视程度，调动学生的积极性和主动性，培养学生的实践创新能力，帮助学生在深入了解编译器工作原理和优化技术的基础上，提高代码编写的质量。同时，也能将编译原理和程序设计语言、操作系统等课程的相关知识联系起来，从而可以从多角度提高学生的综合应用能力，切实有效地提高学生的专业素质，并在实践中取得较好的教学效果。