基于时序逻辑的编译优化测试用例生成方法摘要：提出一种基于时序逻辑公式的关键节点控制图生成方法，生成的测试用例针对性强，容易扩展；并以该方法改进了一种编译优化自动化测试工具，在很大程度上消除了其测试冗余，提高了测试效率。关键词：编译优化；测试用例；时序逻辑；基本块；关键节点控制图中图分类号：TP301文献标志码：A文章编号：1001－3695(2007)07－0046－030引言??编译器是软件开发的基础支撑工具，其正确性直接影响到应用软件的可靠性。它需要通过充分测试以保证其质量。编译器测试用例生成方法可以分为针对前端语法语义的用例生成方法和针对后端优化算法的用例生成方法两大类[1]。??针对前端语法语义的测试用例生成方法的基本思想是基于语言文法生成测试用例，用于编译器前端翻译功能的测试[2，3]。随着编译技术的发展，优化技术逐渐成为编译技术研究的核心内容，出现了一些针对后端优化的测试用例生成方法，文献[4]介绍一种针对编译后端优化的基于文法生成代码的优化测试用例生成方法。首先基于文法生成标准的源程序，再根据具体的优化技术特点加入新的语句以满足特定优化条件。该方法仍属于基于文法的用例生成方法，针对性较弱，具有较大局限性。文献[5，6]对不同的优化类型进行建模，再将模型映射到程序文本作为测试用例。此方法有较好的针对性，但其建模过程和模型映射过程需要对不同的优化进行不同的定制，实现较为复杂。由中国科学院软件所研制的JTT是一个面向编译优化的自动化测试工具，它用于嵌入式环境下的C++优化编译器的系统测试和回归测试[7]。JTT在自动生成程序控制结构的基础上，通过某些特定的随机策略添加计算赋值语句，从而生成完整的测试用例。它缺乏对特定优化精确的形式化描述，难以生成有针对性的优化测试用例，存在大量测试冗余。文献[8]使用基于时序逻辑的条件重写规则LHS→RHSifΦ精确刻画了编译优化。其中条件Φ用时序逻辑公式描述。??1基于时序逻辑的编译优化描述??典型的优化变换能采用基于时序逻辑的条件重写规则LHS→RHSifΦ来作精确刻画[9]。变换由两部分组成，即变换的一系列动作和保证变换正确性的条件。变换动作通过程序控制流图中节点和连接边的变化表示；有四种基本动作，即节点替代(Replace)、边删除(Remove_edge)、边添加(Add_edge)和边分裂(Split_edge)。如图1所示，节点替代是用一系列的节点替代控制流图中的某个节点；删除边和添加边分别是移除和添加控制流图中的连接边；分裂边是在相连接的两节点间插入中间节点。??3讨论及应用??上述算法分为两个阶段：公式规整化和节点生成。其中公式规整化阶段将每个条件的公式转换为标准形式，以便节点生成阶段的处理；节点生成阶段则生成关键节点及关键节点之间的控制流。该算法需要的内存空间与公式中所涉及到的节点数量成正比，需要的时间与条件数目以及节点数目成正比。因此，算法一定可以在有限时间内结束。??构造出一个基本块的关键节点控制图后，可以此为模板很方便地生成大量有针对性的测试用例；可以使用随机策略或启发式策略，在关键节点控制图的节点之间插入新的节点。插入的新节点需要满足插入点之前紧邻关键节点的前向属性，也需要满足插入点之后紧邻关键节点的后向属性。??本文基于前面介绍的方法对JTT工具作了改进，用脚本描述了基于CTL的编译优化刻画公式，并在此基础上利用关键节点控制图生成算法生成了一个基本块的关键控制结构。对于图中的每一条虚边，使用随机策略（可以指定生成代码的并行程度及嵌套程度）生成实际路径来代替[7]，插入赋值语句、表达式、变量和常量定义等语句，生成完整的源程序文件。通过改进后，使得JTT测试用例更具针对性，缩短了测试时间，提高了测试效率。在工业界的实践表明，改进后的JTT能够取得良好的测试质量。图5为JTT截图。??4结束语??传统的编译优化测试方法使用基于文法的方法生成测试用例，其针对性差、测试冗余较多。本文在文献[8]使用时序逻辑公式精确刻画编译优化方法的基础上，提出一种面向编译优化的测试用例自动生成方法，利用时序逻辑公式中出现的关键节点以及节点间的时序关系，构造一个或多个满足优化条件的基本块的...