论文部分内容阅读
摘要：该文介绍了编译器优化技术、软件测试及编译器优化测试方法。对编译器优化测试方法进行了探究。
关键词：编译器；软件测试；编译器优化测试
中图分类号：TP311文献标识码：A文章编号：1009-3044(2011)24-6065-02
1 编译器优化
编译器产生于20世纪60年代，是开发计算机应用系统不可缺少的重要工具，在计算机科学技术的发展历史中发挥着巨大的作用。通常所说的编译器是指,它能够把某种高级语言程序(源语言程序)转换为另一种低级语言程序(目标程序)，而前者与后者在逻辑上是等价的。
优化的方法大多是缩减目标程序的代码规模或通过对程序的功能进行等价转换来提高目标程序的执行性能。编译器优化的目的是为了在时间和空间上使目标代码的效率低。优化可以在编译的不同阶段进行，可以在中间代码生成阶段，在进行语法分析和语义分析，在目标代码生成阶段进行优化。在同一阶段或在同一范围内，也可以进行多种优化。有在基本块内的局部优化，也有在全局范围内基于控制流程和数据流程分析的全局优化等。同时优化所完成的工作，既有与目标机器无关的对中间代码序列中一些代码进行移动、删除和修改，又有与目标机器有关的寄存器分配和对某些机器指的选择和使用等等。
从不同的角度来看，优化技术可分为多种类型。从源程序的角度，可分为局部优化和全局优化。局部优化是指在只有一个入口一个出口的本块内的优化。全局优化是指对程序整体范围内的优化。而从具体计算机的角度，可以分为与机器有关的优化和与机器无关的优化。与机器无关的优化指改进目标代码时不用考虑目标机器的任何特性。在编译优化的发展过程中出现了很多机器无关的优化算法，如：公共子表达式、复制传播、代码外提、无用代码删除等等。与机器有关的优化指的是依赖于目标机器的任何特性，如：寄存器分配、自动向量化、指令调度等等。
2 软件测试的概念
软件测试是通过有目的的运行软件程序来发现其缺陷的过程。软件测试的目的还在于发现错误;一个好的测试用例能发现从前未发现过的错误;一个成功的测试是指发现了从前未发现过的错误的测试。软件测试的本质是针对要测试的内容确定一组测试用例。所谓测试用例就是一个文挡，它是为特定的目标开发的测试输入、执行条件和预期结果的集合。测试用例按测试目的的不同可分为：需求测试用例，设计测试用例和代码测试用例。
3 编译器优化测试
3.1 编译器优化测试
一个编译器正确性应该包括以下内容：
1）词法、语法、语义检查的正确性
编译器在输入阶段能够正确识别源程序中的词法、语法或者语义错误，能接受词法、语法、语义正确的源程序。
2）目標程序合法性
经过编译器编译后生成的目标程序是正确合法的，能在目标机器上运行。
3）功能语义保持一致性
经过编译后的目标程序的功能语义和源程序应保持一致。
4）性能优化正确
编译优化测试指的是针对编译过程中的优化功能及效果进行测试。检测的内容包括：编译优化算法对代码的变换是否保持了程序的功能语义以及编译优化算法对代码的变换是否达到性能改进的目标。
3.2 编译器优化的测试方法
一般意义上的编译测试所指的是编译器的系统测试，也就是说，要对整个编译器的功能与性能进行测试。从测试方法上看，白盒测试方法基于测试部分源码实现的具体信息，所以一般用于针对编译器内部模块实现来进行测试。编译器系统测试一般使用黑盒测试方法，不考虑编译器内部具体的实现细节，仅基于功能性描述和编译器自身的规格说明。
在本文中研究的则是编译器优化测试，是对编译器系统功能的一种测试，此种测试不考虑单元测试和集成测试。编译器优化测试通常使用动态测试方法，有别于不利用计算机运行待测程序的静态方法，需要对具体的源程序进行动态的编译运行来分析编译系统的正确性以及目标程序的优化性能，即通过运行被测试软件来达到目的。编译优化测试的输入信息是用源语言（如高级语言）编写的程序，在经过编译器的编译之后得到目标代码，再经过汇编和链接转换成可执行文件，并在模拟机器上运行，测试的输出是源程序的运行信息，包括输出结果，运行时间和空间消耗，出错信息等。
3.3 编译优化测试主要内容
编译优化测试的主要活动和其它软件的测试活动一样，利用测试用例按照测试方案和流程进行功能和性能测试，包括测试用例的生成、测试用例选取以及测试结果判定等多个方面。
1) 生成测试用例
测试用例生成是测试活动中非常关键的一个内容。测试用例是指对一项特定的软件产品进行测试任务的描述，体现测试方案、方法、技术和策略。内容包括测试目标、测试环境、输入数据、测试步骤、预期结果、测试脚本等，并形成文档，简单地说，就是指程序运行的输入及相应的期望的运行结果，而期望的运行结果是很难有明确具体说明的，通常用隐式方法来描述所设计测试的判断方法的正确性，若与标准正确程序对照的结果正确，则可以说明本次测试期望的运行结果正确。所以，在一般情况下，测试用例仅仅就是指输入的程序。在编译器测试中，一个测试用例主要包括源程序、编译选项及编译配置。在这三个方面中编译选项和编译配置有有限数量的参数，故关注的重点是三个方面中的源程序。和普通的软件测试中的测试用例不同，编译测试的测试用例是一个完整的高级语言程序，组成成分相对复杂、结构独特，而不是一组简单的数据。为说明简便，本文中同样把测试用例仅理解为程序的输入，文中提到的编译器的测试用例仅指输入编译器的源语言程序。
生成编译测试的测试用例是测试工作中最基础的任务。如果使用黑盒纯随机方法，即随机编写一个任意的源程序，那么生成合法源程序的概率极低，不仅对于测试编译后端处理毫无意义，而且对于前端测试的效率也很低，属于最弱的方法。为了强化测试编译的前端功能检查，通常均使用常见的基于源语言的文法生成源文件的方法，也就是利用文法指导的思想生成一些不合法的或者合法的源程序，这种方法还可以在源语言文法的指导下进行自动化。当需要针对后端优化处理进行测试的时候，还需要面向具体的编译优化方法，在测试用例中体现具体的优化成分。
2) 选取测试用例
测试用例的完成并非是一劳永逸的，因为测试用例是来源于测试需求，而测试需求的来源包括了软件需求、系统设计、详细设计，甚至包括了软件发布后，在软件产品生命周期结束前发现的所有软件缺陷。在实际测试中，穷举测试工作量太大，实践上行不通，这就注定了一切实际测试都是不彻底的，也就不能够保证被测试程序中不存在遗留的错误。测试不足意味着让用户承担隐藏错误带来的危险。来源的多元化注定了测试需求是非常容易发生变化的。一旦测试需求发生变化，则测试用例必须重新维护，过度测试则会浪费许多宝贵的资源。测试用例选取关注如何在生成的测试用例中选取一个测试用例集合用于测试，这样的一个测试用例集合可以用尽可能少的代价发现尽可能多的错误，本质上而言是考虑一个成本代价与测试覆盖之间的平衡。可以对测试用例的设计采用软件开发的迭代方法，最终的结果是将逐渐拥有越来越全面细致的测试需求和测试用例库，减少测试人员的精力，可以将重点集中到对测试过程的考虑和测试用例的选择方面。
在编译器测试中，一般来说，因为编译器软件有较大的规模，软件产品内部的程序执行路径会呈几何级数形式增加，使用白盒方法进行穷举路径测试就变成了一件不可能的事情；同时编译器的输入信息可能是任何使用源语言编写的程序，所以使用黑盒方法进行穷举输入测试也不可行。一般测试用例选择策略都基于对源语言语法语义的测试覆盖，高质量的测试用例是既有高覆盖性又有高可执行性，当两者不可兼得时，进行有效的平衡，测试用例的选择原则是用尽可能少的用例保证对源语言的语法语义规则的覆盖。
3) 判定測试结果
测试结果判定的主要目标集中于怎样比较测试输出和期望输出，以确定测试结果的正确性。最简单的判定方法是直接检查并对目标程序与源程序的内部语义进行比较。这个方法的优点是可以检查“正确性”的不同层面，包括对“性能优化”的分析与检查。缺点是难以自动进行功能语义的分析及等价性判断，对人力的耗费巨大。通常的解决办法是寻找一个功能己有的相同编译器作为参照。随着语言和编译技术的发展，各种流行的源语言经过研究人员的开发都有了成熟稳定的编译器，可以利用他们编译相同源文件来对目标程序的运行结果进行比较，通过判定是否等价来评估被测编译器的正确性。对于优化编译测试而言，比较的内容还包括程序的时间复杂度、缓存命中率等信息，来检查优化的结果。
4 结论
编译优化测试也是编译器的系统测试的一种，它的特点是动态地进行并且不考虑开发过程中的单元测试和集成测试。另外，编译测试的输入数据是用源语言编写的程序是编译系统测试的一个特殊性。针对编译的优化特性，更要求测试用例能够尽可能覆盖可被“优化”的成分，为兼顾测试质量，也需进行折中处理，以便让被测编译去进行优化编译。考虑到测试的目的和过程，编译优化测试的测试用例生成方法一般都使用黑盒测试方法，并不关注编译器自身的具体内部实现细节，仅基于功能性描述和编译器自身的规格说明。
编译器测试的测试用例生成方法可以分为针对前端语法语义测试的方法和针对后端优化算法测试的方法两大类。现有的编译优化测试用例生成方法一般都是基于模型的的测试方法，面向具体的优化技术，需要制定测试覆盖准则，通用性较差，用例的生成过程比较复杂，并且成本高、耗费时间。依据形式化的软件需求，需要运用新技术生成测试用例充分对软件中的状态转移进行测试。通过不断的改进，进行进一步完善方法，扩大适用范围，以达到软件测试的通用性。因此，设计一种简单直观且易扩展的测试用例自动生成框架，使它可以用于为多种常见编译优化技术生成有效的测试用例，有待于进一步探究。
参考文献：
[1] 古乐,史九林.软件测试技术概论[M].北京:清华大学出版社,2004.
[2] Steven S. Muchnick. 编译器设计与实现[M].北京:机械工业出版社,2000.
[3] Michael D. Smith, Norman Ramsey et al.A Generalized Algorithm for Graph Coloring Register Allocation.Proceedings of the ACM SIGPLAN’04 Conference on Programming Language Design and Implementation, 2004.
关键词：编译器；软件测试；编译器优化测试
中图分类号：TP311文献标识码：A文章编号：1009-3044(2011)24-6065-02
1 编译器优化
编译器产生于20世纪60年代，是开发计算机应用系统不可缺少的重要工具，在计算机科学技术的发展历史中发挥着巨大的作用。通常所说的编译器是指,它能够把某种高级语言程序(源语言程序)转换为另一种低级语言程序(目标程序)，而前者与后者在逻辑上是等价的。
优化的方法大多是缩减目标程序的代码规模或通过对程序的功能进行等价转换来提高目标程序的执行性能。编译器优化的目的是为了在时间和空间上使目标代码的效率低。优化可以在编译的不同阶段进行，可以在中间代码生成阶段，在进行语法分析和语义分析，在目标代码生成阶段进行优化。在同一阶段或在同一范围内，也可以进行多种优化。有在基本块内的局部优化，也有在全局范围内基于控制流程和数据流程分析的全局优化等。同时优化所完成的工作，既有与目标机器无关的对中间代码序列中一些代码进行移动、删除和修改，又有与目标机器有关的寄存器分配和对某些机器指的选择和使用等等。
从不同的角度来看，优化技术可分为多种类型。从源程序的角度，可分为局部优化和全局优化。局部优化是指在只有一个入口一个出口的本块内的优化。全局优化是指对程序整体范围内的优化。而从具体计算机的角度，可以分为与机器有关的优化和与机器无关的优化。与机器无关的优化指改进目标代码时不用考虑目标机器的任何特性。在编译优化的发展过程中出现了很多机器无关的优化算法，如：公共子表达式、复制传播、代码外提、无用代码删除等等。与机器有关的优化指的是依赖于目标机器的任何特性，如：寄存器分配、自动向量化、指令调度等等。
2 软件测试的概念
软件测试是通过有目的的运行软件程序来发现其缺陷的过程。软件测试的目的还在于发现错误;一个好的测试用例能发现从前未发现过的错误;一个成功的测试是指发现了从前未发现过的错误的测试。软件测试的本质是针对要测试的内容确定一组测试用例。所谓测试用例就是一个文挡，它是为特定的目标开发的测试输入、执行条件和预期结果的集合。测试用例按测试目的的不同可分为：需求测试用例，设计测试用例和代码测试用例。
3 编译器优化测试
3.1 编译器优化测试
一个编译器正确性应该包括以下内容：
1）词法、语法、语义检查的正确性
编译器在输入阶段能够正确识别源程序中的词法、语法或者语义错误，能接受词法、语法、语义正确的源程序。
2）目標程序合法性
经过编译器编译后生成的目标程序是正确合法的，能在目标机器上运行。
3）功能语义保持一致性
经过编译后的目标程序的功能语义和源程序应保持一致。
4）性能优化正确
编译优化测试指的是针对编译过程中的优化功能及效果进行测试。检测的内容包括：编译优化算法对代码的变换是否保持了程序的功能语义以及编译优化算法对代码的变换是否达到性能改进的目标。
3.2 编译器优化的测试方法
一般意义上的编译测试所指的是编译器的系统测试，也就是说，要对整个编译器的功能与性能进行测试。从测试方法上看，白盒测试方法基于测试部分源码实现的具体信息，所以一般用于针对编译器内部模块实现来进行测试。编译器系统测试一般使用黑盒测试方法，不考虑编译器内部具体的实现细节，仅基于功能性描述和编译器自身的规格说明。
在本文中研究的则是编译器优化测试，是对编译器系统功能的一种测试，此种测试不考虑单元测试和集成测试。编译器优化测试通常使用动态测试方法，有别于不利用计算机运行待测程序的静态方法，需要对具体的源程序进行动态的编译运行来分析编译系统的正确性以及目标程序的优化性能，即通过运行被测试软件来达到目的。编译优化测试的输入信息是用源语言（如高级语言）编写的程序，在经过编译器的编译之后得到目标代码，再经过汇编和链接转换成可执行文件，并在模拟机器上运行，测试的输出是源程序的运行信息，包括输出结果，运行时间和空间消耗，出错信息等。
3.3 编译优化测试主要内容
编译优化测试的主要活动和其它软件的测试活动一样，利用测试用例按照测试方案和流程进行功能和性能测试，包括测试用例的生成、测试用例选取以及测试结果判定等多个方面。
1) 生成测试用例
测试用例生成是测试活动中非常关键的一个内容。测试用例是指对一项特定的软件产品进行测试任务的描述，体现测试方案、方法、技术和策略。内容包括测试目标、测试环境、输入数据、测试步骤、预期结果、测试脚本等，并形成文档，简单地说，就是指程序运行的输入及相应的期望的运行结果，而期望的运行结果是很难有明确具体说明的，通常用隐式方法来描述所设计测试的判断方法的正确性，若与标准正确程序对照的结果正确，则可以说明本次测试期望的运行结果正确。所以，在一般情况下，测试用例仅仅就是指输入的程序。在编译器测试中，一个测试用例主要包括源程序、编译选项及编译配置。在这三个方面中编译选项和编译配置有有限数量的参数，故关注的重点是三个方面中的源程序。和普通的软件测试中的测试用例不同，编译测试的测试用例是一个完整的高级语言程序，组成成分相对复杂、结构独特，而不是一组简单的数据。为说明简便，本文中同样把测试用例仅理解为程序的输入，文中提到的编译器的测试用例仅指输入编译器的源语言程序。
生成编译测试的测试用例是测试工作中最基础的任务。如果使用黑盒纯随机方法，即随机编写一个任意的源程序，那么生成合法源程序的概率极低，不仅对于测试编译后端处理毫无意义，而且对于前端测试的效率也很低，属于最弱的方法。为了强化测试编译的前端功能检查，通常均使用常见的基于源语言的文法生成源文件的方法，也就是利用文法指导的思想生成一些不合法的或者合法的源程序，这种方法还可以在源语言文法的指导下进行自动化。当需要针对后端优化处理进行测试的时候，还需要面向具体的编译优化方法，在测试用例中体现具体的优化成分。
2) 选取测试用例
测试用例的完成并非是一劳永逸的，因为测试用例是来源于测试需求，而测试需求的来源包括了软件需求、系统设计、详细设计，甚至包括了软件发布后，在软件产品生命周期结束前发现的所有软件缺陷。在实际测试中，穷举测试工作量太大，实践上行不通，这就注定了一切实际测试都是不彻底的，也就不能够保证被测试程序中不存在遗留的错误。测试不足意味着让用户承担隐藏错误带来的危险。来源的多元化注定了测试需求是非常容易发生变化的。一旦测试需求发生变化，则测试用例必须重新维护，过度测试则会浪费许多宝贵的资源。测试用例选取关注如何在生成的测试用例中选取一个测试用例集合用于测试，这样的一个测试用例集合可以用尽可能少的代价发现尽可能多的错误，本质上而言是考虑一个成本代价与测试覆盖之间的平衡。可以对测试用例的设计采用软件开发的迭代方法，最终的结果是将逐渐拥有越来越全面细致的测试需求和测试用例库，减少测试人员的精力，可以将重点集中到对测试过程的考虑和测试用例的选择方面。
在编译器测试中，一般来说，因为编译器软件有较大的规模，软件产品内部的程序执行路径会呈几何级数形式增加，使用白盒方法进行穷举路径测试就变成了一件不可能的事情；同时编译器的输入信息可能是任何使用源语言编写的程序，所以使用黑盒方法进行穷举输入测试也不可行。一般测试用例选择策略都基于对源语言语法语义的测试覆盖，高质量的测试用例是既有高覆盖性又有高可执行性，当两者不可兼得时，进行有效的平衡，测试用例的选择原则是用尽可能少的用例保证对源语言的语法语义规则的覆盖。
3) 判定測试结果
测试结果判定的主要目标集中于怎样比较测试输出和期望输出，以确定测试结果的正确性。最简单的判定方法是直接检查并对目标程序与源程序的内部语义进行比较。这个方法的优点是可以检查“正确性”的不同层面，包括对“性能优化”的分析与检查。缺点是难以自动进行功能语义的分析及等价性判断，对人力的耗费巨大。通常的解决办法是寻找一个功能己有的相同编译器作为参照。随着语言和编译技术的发展，各种流行的源语言经过研究人员的开发都有了成熟稳定的编译器，可以利用他们编译相同源文件来对目标程序的运行结果进行比较，通过判定是否等价来评估被测编译器的正确性。对于优化编译测试而言，比较的内容还包括程序的时间复杂度、缓存命中率等信息，来检查优化的结果。
4 结论
编译优化测试也是编译器的系统测试的一种，它的特点是动态地进行并且不考虑开发过程中的单元测试和集成测试。另外，编译测试的输入数据是用源语言编写的程序是编译系统测试的一个特殊性。针对编译的优化特性，更要求测试用例能够尽可能覆盖可被“优化”的成分，为兼顾测试质量，也需进行折中处理，以便让被测编译去进行优化编译。考虑到测试的目的和过程，编译优化测试的测试用例生成方法一般都使用黑盒测试方法，并不关注编译器自身的具体内部实现细节，仅基于功能性描述和编译器自身的规格说明。
编译器测试的测试用例生成方法可以分为针对前端语法语义测试的方法和针对后端优化算法测试的方法两大类。现有的编译优化测试用例生成方法一般都是基于模型的的测试方法，面向具体的优化技术，需要制定测试覆盖准则，通用性较差，用例的生成过程比较复杂，并且成本高、耗费时间。依据形式化的软件需求，需要运用新技术生成测试用例充分对软件中的状态转移进行测试。通过不断的改进，进行进一步完善方法，扩大适用范围，以达到软件测试的通用性。因此，设计一种简单直观且易扩展的测试用例自动生成框架，使它可以用于为多种常见编译优化技术生成有效的测试用例，有待于进一步探究。
参考文献：
[1] 古乐,史九林.软件测试技术概论[M].北京:清华大学出版社,2004.
[2] Steven S. Muchnick. 编译器设计与实现[M].北京:机械工业出版社,2000.
[3] Michael D. Smith, Norman Ramsey et al.A Generalized Algorithm for Graph Coloring Register Allocation.Proceedings of the ACM SIGPLAN’04 Conference on Programming Language Design and Implementation, 2004.