编译器是将高级语言源程序翻译转换成低级语言目标程序的系统软件,是软件开发的一种基础支撑工具,它的正确性直接影响到应用软件的可靠性,因此需要通过大量的测试工作来保障编译器的质量。优化是编译过程中的重要阶段,它主要通过对程序进行功能等价的转换来提高目标程序的性能。编译优化问题多是NP问题,算法复杂度高,需要进行针对性的测试。编译优化测试是针对编译器优化功能的测试,检查经过编译优化后得到的目标程序的功能是否正确、执行性能是否得到改善。 编译器测试的主要流程和通常的软件测试一样,包括了测试用例生成、测试用例执行以及测试结果判定等活动。编译器测试中的测试用例是高级语言源程序,手工生成方式工作量大,而且难以保证充分的覆盖度,为了提高效率,需要有自动化的测试用例生成方法。传统的编译器自动测试方法大多从源语言的文法出发生成测试用例,能够很好地测试编译器的“翻译”功能,但是对编译器后端优化功能的测试缺乏针对性。在编译优化测试中,测试用例除了需要满足文法的约束之外,更重要的是需要具有“可被优化的”特征,因此需要能够生成可被优化的测试用例的方法,用于编译优化测试。 编译优化算法的执行通常以程序分析为基础,对具有特定控制结构及数据流内容的程序进行转换。根据这一特点我们提出了一种基于控制结构扩充数据流成分的测试用例自动生成方法。控制结构是一个程序的结构框架,数据流成分则依附于一定的控制结构之上。该方法将测试用例的生成分为控制结构生成和数据流生成两部分。生成测试用例时,首先根据程序控制结构生成算法生成测试用例的控制结构:然后针对不同的优化技术在生成的控制结构上使用相应的数据流生成算法,得到完整的测试用例。这种方法直观、简单,能够方便地描述测试用例中可优化成分的组成,并控制它们的生成,可以有针对性地测试多种编译优化技术。 本文的研究重点是该方法的基础:程序控制结构生成算法。该算法使用平行和嵌套两种特征参数来定义程序中基本控制结构之间的关系,以此描述程序的整体结构特征。在自动生成程序控制结构的时候,先根据指定的参数值构建完全树,然后按照一定的裁剪和恢复规则对构建的完全树进行剪枝,并依据判定条件得到所有满足结构特征要求的树结构集合,最后将这些树结构转换成对应的程序控制结构,作为下一步扩充数据流成分、从而最终生成完整测试用例的基础。 上述方法已在一个优化编译器自动测试工具中成功实现。该工具基于本文所介绍的测试用例自动生成方法,使用两级脚本解析技术,能够自动生成具有满足测试需要的控制结构和数据流成分的测试用例。目前此工具已成功的应用于一种嵌入式优化编译器的测试,取得了良好的使用效果。