基于时序逻辑的编译优化测试用例生成方法

1、基于时序逻辑的编译优化测试用例生成方法 这篇基于时序逻辑的编译优化测试用例生成方法的关键词是编译优化,测试用例,时序逻辑,基本块,关键节点控制图,摘要：提出一种基于时序逻辑公式的关键节点控制图生成方法，生成的测试用例针对性强，容易扩展;并以该方法改进了一种编译优化自动化测试工具，在很大程度上消除了其测试冗余，提高了测试效率。关键词：编译优化; 测试用例; 时序逻辑; 基本块; 关键节点控制图0引言编译器是软件开发的基础支撑工具，其正确性直接影响到应用软件的可靠性。它需要通过充分测试以保证其质量。编译器测试用例生成方法可以分为针对前端语法语义的用例生成方法和针对后端优化算法的用例生成方法两大类1

2、。针对前端语法语义的测试用例生成方法的基本思想是基于语言文法生成测试用例，用于编译器前端翻译功能的测试2，3。随着编译技术的发展，优化技术逐渐成为编译技术研究的核心内容，出现了一些针对后端优化的测试用例生成方法，文献4介绍一种针对编译后端优化的基于文法生成代码的优化测试用例生成方法。首先基于文法生成标准的源程序，再根据具体的优化技术特点加入新的语句以满足特定优化条件。该方法仍属于基于文法的用例生成方法，针对性较弱，具有较大局限性。文献5，6对不同的优化类型进行建模，再将模型映射到程序文本作为测试用例。此方法有较好的针对性，但其建模过程和模型映射过程需要对不同的优化进行不同的定制，实现较为复杂。

3、由中国科学院软件所研制的JTT是一个面向编译优化的自动化测试工具，它用于嵌入式环境下的C+优化编译器的系统测试和回归测试7。JTT在自动生成程序控制结构的基础上，通过某些特定的随机策略添加计算赋值语句，从而生成完整的测试用例。它缺乏对特定优化精确的形式化描述，难以生成有针对性的优化测试用例，存在大量测试冗余。文献8使用基于时序逻辑的条件重写规则LHSRHS if精确刻画了编译优化。其中条件用时序逻辑公式描述。1基于时序逻辑的编译优化描述典型的优化变换能采用基于时序逻辑的条件重写规则LHSRHS if来作精确刻画9。变换由两部分组成，即变换的一系列动作和保证变换正确性的条件。变换动作通过程序控制

4、流图中节点和连接边的变化表示;有四种基本动作，即节点替代(Replace)、边删除(Remove_edge)、边添加(Add_edge)和边分裂(Split_edge)。如图1所示，节点替代是用一系列的节点替代控制流图中的某个节点;删除边和添加边分别是移除和添加控制流图中的连接边;分裂边是在相连接的两节点间插入中间节点。3讨论及应用上述算法分为两个阶段：公式规整化和节点生成。其中公式规整化阶段将每个条件的公式转换为标准形式，以便节点生成阶段的处理;节点生成阶段则生成关键节点及关键节点之间的控制流。该算法需要的内存空间与公式中所涉及到的节点数量成正比，需要的时间与条件数目以及节点数目成正比。因此

5、，算法一定可以在有限时间内结束。构造出一个基本块的关键节点控制图后，可以此为模板很方便地生成大量有针对性的测试用例;可以使用随机策略或启发式策略，在关键节点控制图的节点之间插入新的节点。插入的新节点需要满足插入点之前紧邻关键节点的前向属性，也需要满足插入点之后紧邻关键节点的后向属性。本文基于前面介绍的方法对JTT工具作了改进，用脚本描述了基于CTL的编译优化刻画公式，并在此基础上利用关键节点控制图生成算法生成了一个基本块的关键控制结构。对于图中的每一条虚边，使用随机策略(可以指定生成代码的并行程度及嵌套程度)生成实际路径来代替7，插入赋值语句、表达式、变量和常量定义等语句，生成完整的源程序文件

6、。通过改进后，使得JTT测试用例更具针对性，缩短了测试时间，提高了测试效率。在工业界的实践表明，改进后的JTT能够取得良好的测试质量。图5为JTT截图。4结束语传统的编译优化测试方法使用基于文法的方法生成测试用例，其针对性差、测试冗余较多。本文在文献8使用时序逻辑公式精确刻画编译优化方法的基础上，提出一种面向编译优化的测试用例自动生成方法，利用时序逻辑公式中出现的关键节点以及节点间的时序关系，构造一个或多个满足优化条件的基本块的关键节点及节点间的控制关系，并结合实例详细描述了该方法。该方法生成的测试用例针对性强，适用于多种编译优化的测试。本文由此改进了JTT，很大程度上消除了测试冗余，提高了测

7、试效率。下一步工作将集中在生成更为丰富的控制结构和数据流信息上。参考文献：1BOUJARWAH A S, SALEH K. Compiler test case generation me-thods: a survey and assessmentJ. Information and Software Technology, 1997,39(9):617-625.2PURDOM P. A sentence generator for testing parsersJ. BIT Numerical Mathematics, 1972,12(3):366-375.3JIANG Liyuan, H

8、UANG Guangjun. An automatic system of generating test cases for compilerJ. Journal of Northwestern Polytechnical University, 1992,10(2):153-158.4BURGESS C J, SAIDI M. The automatic generation of test cases for optimizing Fortran compilersJ. Information and Software Technology, 1996,38(2):111-119.5KU

9、LIAMIN V V, PETRENKO A K. Applying model based testing in different contextsEB/OL.2002(2004-12-28).http:/www.ispras.ru/groups/rv/downloads/Dagstuhl2004_Kuliamin.pdf.6KOSSATCHEV A, PETRENKO A, ZELENOV S, et al.Using model-based approach for automated testing of optimizing compilers: proc.of the Inter

10、national Workshop on Program UnderstandingC. Novosi-birsk, Russia:s.n., 2003:81-88.7朱丹枫.一种用于测试编译优化的程序控制结构生成算法D.北京:中国科学院软件研究所,2005.8LACEY D. Program transformation using temporal logic specificationD. Oxford: Oxford University Computing Laboratory, 2003.9CLARKE E M, EMERSON E A, SISTLA A P. Automatic

11、 verification of finite-state concurrent systems using temporal logic specificationsJ. ACM Transactions on Programming Languages and Systems, 1986,8(2):244-263.10EMERSON E A, HALPERN J Y. Decision procedures and expressiveness in the temporal logic of branching timeJ. Journal of Computer and System Sciences, 1985,30(1):1-24.11BEN A