软件学报  2017, Vol. 28 Issue (5): 1221-1232   PDF    
peC语言的部分求值器及在编译器测试中的应用
郭德贵1,2, 王冠成1, 吕帅1,2,3, 刘磊1,4     
1. 吉林大学 计算机科学与技术学院, 吉林 长春 130012;
2. 符号计算与知识工程教育部重点实验室 (吉林大学), 吉林 长春 130012;
3. 吉林大学 数学学院, 吉林 长春 130012;
4. 吉林大学 软件学院, 吉林 长春 130012
摘要: 部分求值技术在程序优化及软件自动生成等方面起着极为重要的作用.将部分求值技术应用到编译器测试中.为此,设计了一种C语言的子集peC语言,给出了该语言的部分求值策略的形式化描述,实现了peC语言的部分求值器,设计了基于部分求值技术的编译器测试框架.通过实验,该方法可以检测出大部分之前其他方法发现的GCC,LLVM编译器中的错误,此外还发现了其他方法不能发现的错误,这表明,将部分求值技术应用到编译器测试中是有效的.
关键词: 部分求值     剩余程序     测试用例     编译器测试     抽象语法树    
Partial Evaluator for peC and Its Application to Compiler Validation
GUO De-Gui1,2, WANG Guan-Cheng1, LÜ Shuai1,2,3, LIU Lei1,4     
1. College of Computer Science and Technology, Jilin University, Changchun 130012, China;
2. Key Laboratory of Symbolic Computation and Knowledge Engineering, Ministry of Education (Jilin University), Changchun 130012, China;
3. College of Mathematics, Jilin University, Changchun 130012, China;
4. College of Software, Jilin University, Changchun 130012, China
Foundation item: Key Program for Science and Technology Development of Jilin Province of China (20150101054JC, 20140520069JH, 20150520060JH); National Natural Science Foundation of China (61300049); Specialized Research Fund for the Doctoral Program of Higher Education of Ministry of Education of China (20120061120059); Graduate Innovation Fund of Jilin University (201681)
Abstract: Partial evaluation plays an important role in many areas such as program optimization and automatic software generation. This paper applies partial evaluation to validating compilers. The design of peC, which is a subset of C, and the formalized description of partial evaluation strategy for peC are presented. Furthermore, the implementation of a partial evaluator for peC, and a compiler testing framework based on partial evaluation are provided. Experiments show that this new approach can not only detect errors which can be detected by other methods in GCC and LLVM but also found some errors which are not detected by the other methods. In summary, the work by this paper demonstrates applying partial evaluation in testing compilers is effective.
Key words: partial evaluation     redundant program     test case     compiler testing     abstract syntax tree    

部分求值思想[1]自1976年被提出来以后, 经过不断补充和完善, Jones等人于1996年完整地描述了部分求值理论, 并提出了较为完善的程序例化思想[2].部分求值技术为研究程序设计语言的性质提供了更加便捷的途径, 在科学计算、逻辑推理、专家系统等领域中扮演着非常重要的角色.近年来, 部分求值技术在程序优化[3, 4]、程序自动生成[5]、程序分析[6]、软件开发[7]等领域得到了广泛应用.

编译器在软件开发中发挥了重要的作用.如果编译器本身存在问题, 那么它编译生成的可执行文件可能会出现严重的错误.由于编译器测试工作具有重大意义, 它已经成为计算机研究中较为热门的研究领域[8].蜕变测试, 即使用一对具有某种关系 (称为蜕变关系) 的测试用例对待测程序进行测试, 通过检查测试用例输出结果是否满足相应的关系得出测试结果[9].Tao等人提出了等价的程序转换策略, 由源程序生成与之等价的另一个源程序, 利用等价程序对编译器等开源软件进行测试[10].他们利用等价程序转换策略的编译器测试方法能够发现大部分人工植入到GCC, LLVM等编译器中的错误, 并检测出两个分别属于GCC-4.4.3和UCC-1.6的错误[10].Le等人提出了EMI (equivalence modulo inputs) 程序变体方法[8], 利用代码覆盖检测工具gcov[11]获得源程序在某一个特定输入下的执行路径, 通过对LLVM编译器生成的抽象语法树进行剪枝操作, 消除源程序中未执行的“死代码”的方法, 生成与源程序语义上等价的程序, 并利用它们组成的等价程序对进行编译器测试.他们利用EMI方法发现GCC, LLVM编译器对一些源程序和相应的EMI变体程序编译会生成错误的代码, 并导致编译器崩溃或运行结果错误[8], 发现的大部分错误已经被其他开发者提交或修复, 提交了对GCC, LLVM编译器少数开发者版本 (非正式发行版本) 检测出的错误, 并得到了官方开发人员的确认.Tao等人提出的利用等价的程序转换策略[10]和Le等人提出的EMI程序变体方法[8]构造测试用例对开源编译器进行测试, 本质上都是通过构造等价的蜕变关系, 利用蜕变测试对开源编译器进行测试的方法, 并且能够发现GCC, LLVM等编译器中的错误.部分求值技术本质上是一种程序例化技术.在给定的部分输入下输入程序与部分求值后, 得到的剩余程序是等价的.本文利用这种思想生成与输入程序互为等价的剩余程序, 并将部分求值技术应用到编译器测试中.现有C语言的部分求值器C-mix[12]和Tempo[13]在程序例化等领域具有较为广泛的运用, 为了便于将部分求值技术应用到编译器测试中, 本文设计了peC语言, 实现了peC的部分求值器, 设计了基于部分求值技术的编译器测试框架, 对GCC, LLVM编译器进行检测.

本文的主要贡献如下:(1) 针对C语言子集peC, 形式化地描述了其部分求值策略.(2) 基于部分求值策略的形式化描述, 利用LLVM编译器的前端Clang, 实现了peC语言的部分求值器.(3) 设计了基于部分求值技术的编译器测试框架, 对编译器进行测试, 检测出了大部分之前其他方法发现的GCC, LLVM编译器中的错误; 此外, 还发现了其他方法不能发现的错误.

1 peC语言的部分求值技术 1.1 部分求值的基本定义

部分求值技术是一种源程序到源程序的转换技术, 它重点强调的是程序的完全自动化的转换, 转换后的源程序是优化的源程序, 所以说它是一种程序优化技术, 或者更确切地叫做程序例化技术[1].

为了给出剩余程序和部分求值器的定义, 首先对程序功能函数$\left[\kern-0.15em\left[ \_ \right]\kern-0.15em\right]$进行如下描述:

$output = \left[\kern-0.15em\left[ p \right]\kern-0.15em\right][{x_0}, \ldots ,{x_n}_{ - 1}],$

其中, outputp在输入x0, …, xn-1(n≥1) 下的结果.

定义 1. 设源程序pr, 对于p来说, 若给定其部分输入in1={d0, …, dn-1}, 对任意剩余输入in2={dn, …, dm}, 有:

$\left[\kern-0.15em\left[ p \right]\kern-0.15em\right]\left[ {in1,in2} \right] = \left[\kern-0.15em\left[ r \right]\kern-0.15em\right]\left[ {in2} \right],$

则称rp关于in1={d0, …, dn-1}的剩余程序.

定义 2. 设源程序pr, 若对于p的部分输入in1={d0, …, dn-1}和任意的剩余输入in2={dn, …, dm}, 有:

$\left[\kern-0.15em\left[ p \right]\kern-0.15em\right]\left[ {in1,in2} \right] = \left[\kern-0.15em\left[ {\left[\kern-0.15em\left[ {mix} \right]\kern-0.15em\right]\left[ {p,in1} \right]} \right]\kern-0.15em\right]\left[ {in2} \right] = \left[\kern-0.15em\left[ r \right]\kern-0.15em\right]\left[ {in2} \right],$

则称mix是部分求值器.

图 1为部分求值器mix的示意图.例化过程就是执行程序p仅依赖于部分输入in1的计算部分, 并生成代码pin1, 而pin1是仅依赖于那些仍未知的输入in2的计算.

Fig. 1 Partial evaluator mix 图 1 部分求值器mix

1.2 C语言子集peC

现有的C语言部分求值器开发时间较早且没有开源, 找不到可以使用的版本.由于C语言的数据类型和语句结构等非常丰富, 为了便于将部分求值技术应用到编译器测试中, 本文设计了C语言子集peC语言.peC语言保留了过程式语言的基本特征, 其文法描述如图 2所示.

Fig. 2 Grammar description of peC 图 2 peC语言的文法描述

1.3 部分求值策略

由于过程式程序中的变量在程序执行的过程中, 其值是在不断地动态变化的, 采用动态的部分求值技术对过程式语言进行部分求值更为实际和方便[14].我们定义了转换域、预定义函数和转换函数, 形式化地描述了peC语言的部分求值策略.

1) 转换域

Prog=P

RProg=P

Stm=S

RStm=S

DStm=Dec

RDStm=Dec

StmL=SL

RStmL=SL

Block=B

RBlock=B

Exp=E

RExp=E

ρState=IDEVALUE

σStack=State*

VALUE=INT+BOOL+⊥

πΠ=⊥+$ \top $

其中, Stack是变量状态栈, 即由各个程序块的变量状态形成的栈, 随着部分求值的过程动态变化.变量的状

态包含未知 (⊥) 和已知的值.表达式状态包含已知 ($ \top $) 和未知 (⊥).

2) 预定义函数

update: StackValueIDEStack

update[] _ _=error

update ρ:σ val v=(vdom(ρ)→ρ[val/v]:σ, ρ:update σ val v)

comb: StateStateState

comb[][]=[]

comb xv1: ρ1 xv2: ρ2=(v1=v2→(xv1: comb ρ1 ρ2), (x→⊥: comb ρ1 ρ2))

⊕: StackStackStack

[·]⊕[·]=[·]

ρ1:σ1ρ2:σ2=comb(ρ1 σ2):(σ1σ2)

∔: StateStackStack

ρ∔[]=[ρ]

ρρ1:σ=(ρ1ρ):σ

find: StackIDEVALUE

find[] _=error

find ρ: σ v=(vdom(ρ)→ρ(v), ρ:find σ v)

部分求值策略中的转换函数中包含了5个辅助操作:update函数用val更新某个变量v在变量状态栈中的状态; comb函数对经过不同例化过程的同一变量对应的变量状态表进行合并, 即一旦该变量的状态在两个表中不同, 就将该变量的状态置为未知; ⊕函数合并程序块经过不同例化过程后产生的变量状态栈; 当部分求值分析过程在某一作用域中遇到变量的声明时, ∔函数将声明的变量对应的映射添加到变量状态栈中该变量所在作用域对应的变量状态表的表尾, 声明的变量的初始状态可以在全局变量状态表中查到; find函数在变量状态栈中从栈顶到栈底查找变量v的状态.

3) 转换函数

KP: Prog→[StateRProg]

KB: Block→[StateStackRBlockxStatexStack]

KSL: StmL→[StateStackRStmLxStatexStack]

KS: Stm→[StateStackRStmxStatexStack]

KD: DStm→[StateStackRDStmxStatexStack]

KE: Exp→[StackRexpxP]

Kp$\left[\kern-0.15em\left[ B \right]\kern-0.15em\right]$=λρ.let(" rb" , ρ1, σ1)=KB$\left[\kern-0.15em\left[ B \right]\kern-0.15em\right]$ρ[] in " rb"

KB$\left[\kern-0.15em\left[ S \right]\kern-0.15em\right]$=λρσ.let(" rs" , ρ1, ρ2:σ1)=KS$\left[\kern-0.15em\left[ S \right]\kern-0.15em\right]$ρ[] σ in (" rs" , ρ1, σ1)

KB$\left[\kern-0.15em\left[ {\left\{ {SL} \right\}} \right]\kern-0.15em\right]$=λρσ.let(" rsl" , ρ1, ρ2:σ1)=KSL$\left[\kern-0.15em\left[ {SL} \right]\kern-0.15em\right]$ρ[] σ in (" rsl" , ρ1, σ1)

部分求值过程从函数KP开始, 通过调用KP$\left[\kern-0.15em\left[ B \right]\kern-0.15em\right]$ρ0计算peC程序B的剩余程序rb.其中, ρ0是全局变量状态, 即程序中变量的已知的值或未知 (⊥) 状态.函数KB对程序块B进行部分求值.当某一程序块开始其部分求值过程时, 需要新建一个变量状态表维护当前程序块中的局部变量和其状态的映射关系.某一程序块的部分求值过程结束后, 该作用域的局部变量被释放, 从变量状态栈中删除该程序块对应的变量状态表.

$\begin{array}{l} {K_{SL}}\left[\kern-0.15em\left[ S \right]\kern-0.15em\right] = \lambda \rho \sigma .let\left( {"rs",{\rho _1},{\sigma _1}} \right) = {K_S}\left[\kern-0.15em\left[ S \right]\kern-0.15em\right]{\rho _1}[]\;{\rm{in}}\left( {"rs",{\rho _1},{\sigma _1}} \right)\\ {K_{SL}}\left[\kern-0.15em\left[ {S;SL} \right]\kern-0.15em\right] = \lambda \rho \sigma .let\left( {"rs",{\rho _1},{\sigma _1}} \right) = {K_S}\left[\kern-0.15em\left[ S \right]\kern-0.15em\right]\rho \sigma \;{\rm{in}}\;let\left( {"rsl",{\rho _2},{\sigma _2}} \right) = {K_{SL}}\left[\kern-0.15em\left[ {SL} \right]\kern-0.15em\right]\\ {\rho _1}{\sigma _1}\;{\rm{in}}\left( {"rs;rsl",{\rho _2},{\sigma _2}} \right)\\ {K_S}\left[\kern-0.15em\left[ {SKIP} \right]\kern-0.15em\right] = \lambda \rho \sigma .\left( {\varepsilon ,\rho ,\sigma } \right)\\ {K_S} [\kern-0.15em[ v = E ]\kern-0.15em] = \lambda \rho \sigma .let("re",\pi ) = {K_E} [\kern-0.15em[ E ]\kern-0.15em] \sigma \;{\rm{in}}\\ \quad \quad \quad \quad \quad {\rm{ }}\left( \begin{array}{l} \pi = \top \to let\;val = \varphi (re){\rm{ in }}("v = val",\rho ,update(\sigma ,val,v)),\\ \pi = \bot \to ("v = re",\rho ,update(\sigma , \bot ,v)) \end{array} \right)\\ {K_S} [\kern-0.15em[ {\rm{if}}(E){\rm{ }}B ]\kern-0.15em] = \lambda \rho \sigma .let("re",\pi ) = {K_E} [\kern-0.15em[ E ]\kern-0.15em] \sigma {\rm{ in}}\;let("rb",{\rho _1},{\sigma _1}) = {K_B} [\kern-0.15em[ B ]\kern-0.15em] \rho \sigma \;{\rm{in}}\\ \quad \quad \quad \quad \quad \quad \left( \begin{array}{l} \pi = \top \& \varphi (re) \to ("rb",{\rho _1},{\sigma _1}),\pi = \top \& !\varphi (re) \to (\varepsilon ,{\rho _1},\sigma ),\\ \pi = \bot \to ("{\rm{if }}(re){\rm{ }}rb",{\rho _1},\sigma \oplus {\sigma _1}) \end{array} \right)\\ {K_S} [\kern-0.15em[ {\rm{if}}(E){\rm{ }}{B_1}{\rm{ else }}{B_2} ]\kern-0.15em] = \lambda \rho \sigma .let("re",\pi ) = {K_E} [\kern-0.15em[ E ]\kern-0.15em] \sigma \;{\rm{in}}\\ \quad \quad \quad \quad \quad \quad \quad \quad let("r{b_1}",{\rho _1},{\sigma _1}) = {K_B} [\kern-0.15em[ {B_1} ]\kern-0.15em] \rho \sigma \;{\rm{in}}\;let("r{b_2}",{\rho _2},{\sigma _2}) = {K_B} [\kern-0.15em[ {B_2} ]\kern-0.15em] {\rho _1}\sigma \;{\rm{in}}\\ \quad \quad \quad \quad \quad \quad \quad \quad \left( \begin{array}{l} \pi = \top \& \varphi (re) \to ("r{b_1}",{\rho _2},{\sigma _1}),\pi = \top \& !\varphi (re) \to ("r{b_{\rm{2}}}",{\rho _2},{\sigma _2}),\\ \pi = \bot \to ("{\rm{if }}(re){\rm{ }}r{b_1}\;{\rm{else}}\;r{b_2}",{\rho _2},{\sigma _1} \oplus {\sigma _2}) \end{array} \right) \end{array}$

其中, φ函数将剩余表达式转换成数值, ε表示空串.

$\begin{array}{l} {K_S} [\kern-0.15em[ {\rm{while}}\;(E)\;B ]\kern-0.15em] = \lambda \rho \sigma .let("re",\pi ) = {K_E} [\kern-0.15em[ E ]\kern-0.15em] \sigma \;{\rm{in}}\\ \quad \quad \quad \quad \quad \quad \quad \quad let("rb",{\rho _1},{\sigma _1}) = {K_B} [\kern-0.15em[ B ]\kern-0.15em] \rho \sigma \;{\rm{in}}\\ \quad \quad \quad \quad \quad \quad \quad \quad \left( \begin{array}{l} \pi = \top \& !\varphi (re) \to (\varepsilon ,{\rho _1},\sigma ),\\ \pi = \top \& \varphi (re) \to let("r{s_1}",{\rho _2},{\sigma _2}) = {K_S} [\kern-0.15em[ {\rm{while}}\;(E)\;B ]\kern-0.15em] \rho {\sigma _1}\;{\rm{in}}\;("rb;r{s_1}",{\rho _2},{\sigma _2}),\\ \pi = \bot \to let("r{s_2}",{\rho _3},{\sigma _3}) = {K_S} [\kern-0.15em[ {\rm{while}}\;(E)\;B ]\kern-0.15em] \rho {\sigma _1}\;{\rm{in}}\;("{\rm{if }}(re)\;\{ rb;r{s_2}\} ",{\rho _3},{\sigma _3}) \end{array} \right)\\ {K_S} [\kern-0.15em[ {\rm{do}}\;B\;{\rm{while}}\;(E) ]\kern-0.15em] = \lambda \rho \sigma .{\rm{ }}let("rb",{\rho _1},{\sigma _1}) = {K_B} [\kern-0.15em[ B ]\kern-0.15em] \rho \sigma \;{\rm{in}}\\ \quad \quad \quad \quad \quad \quad \quad \quad \quad let("re",\pi ) = {K_E} [\kern-0.15em[ E ]\kern-0.15em] {\sigma _1}\;{\rm{in}}\\ \quad \quad \quad \quad \quad \quad \quad \quad \quad \left( \begin{array}{l} \pi = \top \& \varphi (re) \to let("rs",{\rho _2},{\sigma _2}) = {K_S} [\kern-0.15em[ {\rm{do}}\;B\;{\rm{while}}\;(E) ]\kern-0.15em] \rho {\sigma _1}\;{\rm{in}}\;("rb;rs",{\rho _2},{\sigma _2}),\\ \pi = \top \& !\varphi (re) \to ("rb",{\rho _1},{\sigma _1}),\\ \pi = \bot \to let("r{s_1}",{\rho _3},{\sigma _3}) = {K_S} [\kern-0.15em[ {\rm{while }}(E){\rm{ }}B ]\kern-0.15em] \rho {\sigma _1}\;{\rm{in}}\;("rb;r{s_1}",{\rho _3},{\sigma _3}) \end{array} \right) \end{array}$

当循环语句的条件表达式为真时, 由于循环体可能被执行多次, 而其中的局部变量仅在全局变量状态ρ中定义了1次, 所以循环体中的局部变量至多会根据ρ被初始化1次.

$\begin{array}{l} {K_S} [\kern-0.15em[ Dec ]\kern-0.15em] = \lambda \rho \sigma .let("rds",{\rho _1},{\sigma _1}) = {K_D} [\kern-0.15em[ Dec ]\kern-0.15em] \rho \sigma \;{\rm{in}}\;("rds",{\rho _1},{\sigma _1})\\ {K_D} [\kern-0.15em[ {\rm{int}}\;v ]\kern-0.15em] = \lambda \rho \sigma .let\;al = \rho (v){\rm{ in }}let{\rm{ }}{\sigma _1} = [v \to val] \buildrel\textstyle.\over+ \sigma \;{\rm{in}}\;("{\rm{int}}\;v",\rho /v,{\sigma _1})\\ {K_D} [\kern-0.15em[ {\rm{int}}\;v = E ]\kern-0.15em] = \lambda \rho \sigma .let("re",\pi ) = {K_E} [\kern-0.15em[ E ]\kern-0.15em] \sigma \;{\rm{in }}\\ \quad \quad \quad \quad \quad \quad \quad \left( \begin{array}{l} \pi = \top \to ("{\rm{int}}\;v = re",\rho /v,[v \to \varphi (re)] \buildrel\textstyle.\over+ \sigma ),\\ \pi = \bot \to ("{\rm{int}}\;v = re",\rho /v,[v \to \bot ] \buildrel\textstyle.\over+ \sigma ) \end{array} \right) \end{array}$

声明语句声明新的变量, 需要从全局变量状态中查找该变量对应的状态进行初始化.若声明语句中没有对变量进行初始化, 则函数${K_D} = \left[\kern-0.15em\left[ {{\mathop{\rm int}} \;v} \right]\kern-0.15em\right]$从全局变量状态中删除变量v; 若声明语句中对变量进行初始化, 则函数${K_D} = \left[\kern-0.15em\left[ {{\mathop{\rm int}} \;v = E} \right]\kern-0.15em\right]$从全局变量状态中删除变量v, 并在变量状态栈中更新v的状态.

$\begin{array}{l} {K_E} [\kern-0.15em[ N ]\kern-0.15em] = \lambda \sigma .(n, \top )\\ {K_E} [\kern-0.15em[ v ]\kern-0.15em] = \lambda \sigma .let\;val = find(\sigma ,v)\;{\rm{in }}(val = \bot \to ("v", \bot ),("val", \top ))\\ {K_E} [\kern-0.15em[ {E_1}\;\omega \;{E_2} ]\kern-0.15em] = \lambda \sigma .let("r{e_1}",{\pi _1}) = {K_E} [\kern-0.15em[ {E_1} ]\kern-0.15em] \sigma \;{\rm{in}}\\ \quad \quad \quad \quad \quad \quad \quad let("r{e_2}",{\pi _2}) = {K_E} [\kern-0.15em[ {E_2} ]\kern-0.15em] \sigma \;{\rm{in}}\\ \quad \quad \quad \quad \quad \quad \quad ({\pi _1} = \top \& {\pi _2} = \top \to ("\varphi (r{e_1})\;\vec \omega \;\varphi (r{e_2})", \top ),("r{e_1}\;\omega \;r{e_2}", \bot )) \end{array}$

其中, $\vec \omega $表示对两个整数进行加、减、乘、除等操作.

2 部分求值器的实现

本文实现的部分求值器利用LLVM的LibTooling库[15]将peC语言源程序通过语法分析转换为抽象语法树 (abstract syntax tree, 简称AST), 基于部分求值策略修改AST, 最终生成剩余程序.

图 3为本文实现的peC语言部分求值器的基本结构.peC语言部分求值器主要由3个部分构成.

Fig. 3 Partial evaluator of peC 图 3 peC语言部分求值器

1) partialeval是部分求值器的基本环境.

2) 部分求值过程是基于部分求值策略对peC程序的AST结点进行删除、替换等操作的过程, 在这个过程中, 需要建立动态环境维护中间信息.动态环境由全局变量状态ρ0、变量状态栈σ和语句分析栈StmtEnv构成, 其中, ρ0包含了程序p的部分输入in1.

3) 部分求值过程结束后, 输入程序p, 经过剩余程序代码生成阶段, 最终得到剩余程序.

2.1 LLVM基本环境设置

为了实现部分求值过程, 在LLVM编译器的前端Clang中添加了命令选项“-partialeval”, 并添加相应的入口.当使用该选项时, 触发部分求值任务, 对输入源程序进行基于部分求值策略的程序转换, 最终得到剩余程序.

2.2 peC程序的中间表示

LLVM编译器通过语法分析生成peC程序的中间表示AST.通过访问AST的结点, 可以得到与源程序相关的信息.

例1:如图 4所示的源程序包含了声明语句、if条件语句等, 其对应的AST如图 5所示.为了便于理解, 在图 5的AST中保留了AST中的一些特征信息, 如操作符类型、变量类型、变量名等.

Fig. 4 Simple source code 图 4 简单的源程序

Fig. 5 Example of Clang AST 图 5 Clang AST样例

其中, DeclStmt是变量声明语句对应的AST结点类型, 访问该结点可以获取到声明的变量名、初始化情况等信息; IfStmt是if条件语句对应的AST结点类型, 访问该结点可以获取到与条件表达式、then分支、else分支对应的子树等信息; DeclRefExpr是函数调用、变量引用等操作对应的AST结点类型, 变量引用的结点类型中可以获取到变量类型、变量名等信息.

2.3 动态环境维护

部分求值过程的动态环境是指语句分析栈StmtEnv、全局变量状态ρ0和变量状态栈σ.根据部分求值策略, 对它们的维护过程如下.

1) 语句分析栈StmtEnv的每个栈元素是一个语句分析表, 保存了一个作用域中的待分析语句.当部分求值过程分析到一个新的程序块Block时, 将一个空的语句分析表压入StmtEnv, 并将该程序块中的语句依次保存到表中.在对某条语句部分求值后, 将该语句从其对应的语句分析表中删除.

2) 全局变量状态ρ0根据程序的部分输入集合收集了输入程序中所有的变量及其初始状态的映射, 变量在表中出现的次序和它们在输入程序中出现的顺序是一致的.在部分求值过程中, 每当遇到一个变量的声明, 从ρ0中获取它的初始状态, 并删除该变量在ρ0中对应的映射.

3) 变量状态栈c在部分求值过程中维护变量及其状态的映射.每当一个新的作用域开始其部分求值过程时, 一个空的变量状态表就被压入σ, 在该作用域内, 按照变量声明顺序将其添加到该作用域对应的变量状态映射表中, 并依据ρ0初始化其在映射表中的状态.在部分求值过程中, 当一个变量的值发生变化时, 需要修改其在σ中相应的状态.一个作用域的部分求值过程结束后, 其对应的变量状态映射表被删除, 但当程序的部分求值过程结束后, 变量状态栈σ将保存最终的状态.

例2:如图 6所示的输入源程序和部分求值过程中动态环境的变化 (根据部分求值策略, 部分求值过程对输入源程序中的赋值语句、if条件语句进行分析).

Fig. 6 Example of dynamic environment maintenance in partial evaluation 图 6 部分求值中动态环境维护示例

·在状态① 中, 全局变量状态ρ0按照变量在输入程序中的声明顺序保存其与状态的映射.当main函数开始进行部分求值过程时, 语句分析栈StmtEnv中保存待分析语句:声明语句DeclStmt和条件语句IfStmt, 并在变量状态栈σ中压入空的变量状态表σ1.

·在状态② 中, 声明语句DeclStmt结束了其部分求值过程, 将a, b, c这3个变量保存进变量状态表σ1中, 根据全局变量状态ρ0进行初始化, 并从语句分析栈StmtEnv中删除DeclStmt.

·在状态③ 中, 条件语句IfStmt开始部分求值过程.由于IfStmt对应一个新的程序块Block, 在变量状态栈中压入空的变量状态表σ2.因为条件表达式已知为真, 条件语句IfStmt将执行then分支, else分支不会进行部分求值过程.语句分析栈StmtEnv收集条件语句中then分支的待分析语句.

·在状态④ 中, 条件表达式中的声明语句结束了其部分求值过程, 将变量local保存进变量状态表σ2中, 根据全局变量状态ρ0进行初始化, 并从语句分析栈StmtEnv中删除DeclStmt.

·在状态⑤ 中, 条件表达式中的赋值语句BinaryOperator结束了其部分求值过程.由于赋值语句改变了变量a的状态, 需要在变量状态表σ1中更新它的状态.随着赋值语句的部分求值过程的结束, 条件语句IfStmt结束了其部分求值过程.由于条件语句是语句分析栈StmtEnv中的最后一条待分析语句, 语句分析栈StmtEnv置为空, 变量状态表σ1中保存最终的变量状态的映射.

2.4 语义等价变换

本文利用AST获取部分求值过程中所需要的信息, peC语言的部分求值过程其实是修改AST和维护动态环境的过程.在修改AST的过程中, 根据部分求值策略, 对AST进行了替换、删除和转换操作.规则如下.

1) 表达式规则 (图 7①):若表达式operand1 ω operand2的值可以被计算, 其在AST中的子树会被PECodeFrag结点替换.其中, PECodeFrag结点是AST中新增的自定义结点, 保存表达式的值和值类型等信息.

Fig. 7 Transformation of AST 图 7 AST的变换

2) 分支规则 (图 7②图 7③):当if语句的条件表达式E的值已知时, 采用分支规则对if语句的子树进行变换.在图 7②中, 当条件表达式为假时, if语句执行else分支, 在AST中, 用else分支的子树替换if语句的子树; 在图 7③中, 当条件表达式为真时, if语句执行then分支, 在AST中, 用then分支的子树替换if语句的子树.

3) 循环规则 (图 7④~图 7⑥, 图 7以while语句对应的子树转换为例对循环规则具体说明):根据部分求值策略, while循环语句对应的子树变换规则如下.

a) 在图 7④中, 当条件表达式E的值为未知时, 循环展开一次, 其中, S'为部分求值后的循环体对应的子树.

b) 在图 7⑤中, 当条件表达式E的值为真时, 循环展开一次, 其中, S'为部分求值后的循环体对应的子树.

c) 在图 7⑥中, 当表达式E的值为假时, 整个while语句不会被执行, 在AST中, 用空结点替换while语句对应的子树.

2.5 剩余程序源代码生成

在本文实现的部分求值器中, 部分求值过程是在AST上进行的, 部分求值后的剩余程序是AST的形式, 需要将其转换为源程序文本.

输入程序被peC语言的部分求值器读入后, 其文本会被保存在内存中, 利用AST中的信息, 对内存中的输入程序文本自动地进行修改, 最终生成剩余程序的文本.

3 编译器测试框架及实验 3.1 编译器测试框架

设有输入源程序p, 若已知有部分输入in1={d0, …, dn-1}和剩余输入in2={dn, …, dm}, 则其剩余程序为$r = \left[\kern-0.15em\left[ {mix} \right]\kern-0.15em\right]\left[ {p,in1} \right]$.理论上, 在部分输入in1确定的情况下, pr是等价的.用相同的编译器和编译选项对pr编译并在剩余输入in2下运行, 其结果应相同.若出现不同的情况, 则一定是该编译器中存在错误.基于以上分析, 给出如图 8所示的编译器测试框架.

Fig. 8 Compiler testing framework 图 8 编译器测试框架

3.2 实验与分析

本文的实验基于x86-linux平台, 操作系统为Ubuntu12.04(x86_64).对于GCC和LLVM编译器, 本文使用-O0, -O1, -O2, -O3, -Os等编译选项对它们的若干个发行版本进行了大量的测试.基于图 8所示的框架, 本文做了如下两个方面的实验.

1) 在开源编译器框架LLVM中植入大量错误, 利用本文的方法能够发现绝大部分错误.如例3中源程序p和剩余程序r, 利用相同的编译选项分别对pr编译、运行, 运行结果不一致, 触发了LLVM编译器中人工植入的错误.

2) 利用不同的部分输入和现有的编译器测试用例[10, 16, 17]对GCC, LLVM编译器进行测试.如例4~例6中源程序p和剩余程序r, 利用相同的编译选项分别对pr编译或运行, 编译或运行结果不一致, 触发了GCC或LLVM编译器中不同的错误.

例3:如图 9输入程序p图 10在部分输入[b→1]时的剩余程序r.在版本为3.4 r182207的LLVM编译器前端Clang中, 分别使用“-O0”, “-O1”, “-O2”, “-O3”和“-Os”编译优化选项对程序p编译并运行, 程序输出结果为-1.同样条件下, 对程序r进行编译并运行, 程序输出结果为1.显然, 它们的运行结果是不一致的, 说明了该版本的LLVM编译器中存在错误.通过实验结果分析可知, 该例中的测试用例触发了LLVM编译器中人工植入的错误.

Fig. 9 Input program 1 图 9 输入程序1

Fig. 10 Residual program 1 图 10 剩余程序1

例4:如图 11输入程序p图 12在部分输入[c→0]时的剩余程序r.在版本为4.9.0 20131014的GCC编译器中, 使用“-O3”编译优化选项对程序p编译并运行, p对应的可执行文件在运行时无法退出.在同样条件下, 对r编译和运行, r对应的可执行文件在运行时立刻退出.显然, 它们的运行结果是不一致的.说明了该版本的GCC编译器中存在错误.通过实验结果分析可知:使用“-O3”编译优化后, 优化后的程序p对应的可执行文件执行第3个while循环语句, 进入无限循环, 导致无法退出的情况.

Fig. 11 Input program 2[16] 图 11 输入程序2[16]

Fig. 12 Residual program 2 图 12 剩余程序2

例5:同例4中的pr.在版本为4.8的GCC编译器中, 使用“-O2”编译优化选项对程序p进行编译时, 发生“未定义行为”的警告信息.在同样的条件下对r进行编译, 没有出现警告信息.显然, 它们的编译结果是不一致的.这说明该版本的GCC编译器中可能存在错误.通过实验结果分析可知, 在使用“-O2”编译优化选项对程序p进行优化时, 循环不变式“$d = a < 214748364\tilde 7b$; ”被外提, 当b为-1时, 该循环不变式触发了“未定义行为”的警告.实际上, 在该程序中, 由于不可能进入到第3层循环, 不会出现未定义行为的情况.

例6:图 13所示输入程序p图 14所示在部分输入[a→0]时的剩余程序r.在版本为3.4 r182207的LLVM编译器前端Clang中, 分别使用“-O2”和“-O3”编译优化选项对程序p编译, 导致Clang崩溃.在同样条件下, 对程序r进行编译, 没有出现警告或者错误信息.显然, 它们的编译结果是不一致的.这说明该版本的LLVM编译器中可能存在错误.值得一提的是, 该错误虽然是由开发者向官方提交的错误, 但是利用本文的方法能够检测出该错误, 且并没有被EMI方法等编译器测试方法发现.通过实验结果的分析可知, 编译器在对程序p进行编译时, 在LLVM IR中生成了过长的乘法链, 导致编译器崩溃.

Fig. 13 Input program 3[17] 图 13 输入程序3[17]

Fig. 14 Residual program 3 图 14 剩余程序3

基于上述实验, 利用本文实现的peC语言的部分求值器, 可以检测出GCC, LLVM编译器中关于循环不变式外提、死代码消除等错误, 复现了上述两项工作中提及的大量错误.此外还发现了其他方法没有发现的错误, 说明了将部分求值技术应用到编译器测试中是有效的.

EMI方法通过消除“死代码”的方法生成变体程序, 本质上是构造了一对具有等价蜕变关系的程序对.EMI方法在特定输入下执行源程序, 再利用代码覆盖检测工具获取每条代码的执行信息, 本质上是动态生成变体程序的方法.本文的方法通过对LLVM编译器生成的抽象语法树剪枝的方法能够方便地对源代码进行修改, 降低了在修改过程中造成变体程序语义错误的可能性.在大部分情况下, 消除“死代码”仅仅是对源程序的局部进行修改, 生成的变体程序和源程序之间的差别较小.本文提出的基于部分求值技术的编译器测试框架根据不同的部分输入, 一个源程序不需要被执行, 可以静态地得到多个语义等价的变体程序, 组成多对等价测试用例, 由于是基于部分求值技术的程序转换策略, 得到的变体程序与源程序差异较大, 更容易检测出编译器中的问题.本文通过修改LLVM编译器生成的抽象语法树的方法对源程序进行部分求值, 相对于原先基于源程序文本标记的部分求值方法, 获得的语义信息更加丰富, 变体程序出现语义错误的可能性更小.

4 总结

本文形式化描述了C语言子集peC的部分求值策略, 并基于该策略利用LLVM编译器实现了peC语言的部分求值器.在给定部分输入的情况下, 输入程序经该部分求值器转换后生成与之等价的剩余程序.利用该性质, 设计了基于部分求值技术的编译器测试框架.实验结果表明, 利用这种等价程序对, 可以检测出大部分之前其他方法发现的GCC, LLVM编译器中的错误; 此外还发现了其他方法不能发现的错误, 表明将部分求值技术应用到编译器测试中是有效的.

本文将部分求值技术应用到编译器测试中, 为编译器测试领域提供了测试用例生成的新思路.由于编译器是十分庞大的软件, 由大量的开发者共同维护, 使用现有的测试用例生成的等价程序对已经很难测试出新的编译器错误, 利用peC的部分求值器对其进行检测必然存在一定的局限性.鉴于使用现有的测试用例生成的等价程序对已经很难测试出新的编译器错误这一问题, 我们正尝试构造大量新的有效测试用例.由于peC语言是C语言的一部分且本文实现的部分求值策略并不完整, 基于部分求值技术的编译器测试方法还有很大的提升空间, 本课题组希望对peC语言进行扩展, 描述并实现对应的部分求值策略, 并在下一步工作中针对该问题进行重点研究, 以期望其在编译器测试中产生较好的效果.

参考文献
[1] Beckman L, Haraldson A, Oskarsson Ö, Sandewall E. A partial evaluator, and its use as a programming tool. Artificial Intelligence, 1976, 7(4): 319–357 . [doi:10.1016/0004-3702(76)90011-4]
[2] Jones ND. An introduction to partial evaluation. ACM Computing Surveys, 1996, 28(3): 480–503 . [doi:10.1145/243439.243447]
[3] Adams MD, Farmer A, Magalhães JP. Optimizing SYB is easy! In: Proc. of the ACM SIGPLAN 2014 Workshop on Partial Evaluation and Program Manipulation. 2014. 71-82. [doi:10.1145/2543728.2543730]
[4] Brady EC, Hammond K. Scrapping your inefficient engine: Using partial evaluation to improve domain-specific language implementation. ACM SIGPLAN Notices, 2010, 45(9): 297–308 . [doi:10.1145/1932681.1863587]
[5] Birken K. Building code generators for DSLs using a partial evaluator for the Xtend language. In: Tiziana M, ed. Proc. of the Leveraging Applications of Formal Methods, Verification and Validation. New York: Springer-Verlag, 2014. 407-424. [doi:10.1007/978-3-662-45234-9_29]
[6] Tripp O, Ferrara P, Pistoia M. Hybrid security analysis of Web javascript code via dynamic partial evaluation. In: Proc. of the 2014 Int'l Symp. on Software Testing and Analysis. 2014. 49-59. [doi:10.1145/2610384.2610385]
[7] Razavi A, Kontogiannis K. Partial evaluation of model transformations. In: Proc. of the 34th Int'l Conf. on Software Engineering. New York: ACM Press, 2012. 562-572.
[8] Le V, Afshari M, Su Z. Compiler validation via equivalence modulo inputs. In: Proc. of the 35th ACM SIGPLAN Conf. on Programming Language Design and Implementation. New York: ACM Press, 2014. 216-226.
[9] Chen TY, Cheung SC, Yiu SM. Metamorphic testing: A new approach for generating next test cases. Technical Report, HKUST-CS98-01, 1998.
[10] Tao Q, Wu W, Zhao C, Shen W. An automatic testing approach for compiler based on metamorphic testing technique. In: Proc. of the 17th Asia Pacific Software Engineering Conf. IEEE, 2010. 270-279. [doi:10.1109/apsec.2010.39]
[11] GNU compiler collection: gcov. https://gcc.gnu.org/onlinedocs/gcc/Gcov.html
[12] Glenstrup A, Makholm H, Secher JP. C-Mix-Specialization of C programs. In: Proc. of the Partial Evaluation. 1998. 108-154.
[13] Consel C, Hornof L, Lawall J, Marlet R, Muller G, Noyé J, Thibault S, Volanschi EN, Tempo: Specializing systems applications and beyond. In: Proc. of the ACM Computing Surveys, Symp. on Partial Evaluation. 1998. 19-23. [doi: 10.1145/289121.289140]
[14] Liu L, Zhen HJ, Jin CZ. The partial evaluation technique based on information flow analysis. Ruan Jian Xue Bao/Journal of Software, 1995, 6(8): 509–513 (in Chinese with English abstract). http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=19950810&journal_id=jos
[15] The Clang Team. Clang documentation: LibTooling. http://clang.llvm.org/docs/LibTooling.html
[16] GCC bug. https://gcc.gnu.org/bugzilla/show_bug.cgi?id=58731
[17] LLVM bug. https://llvm.org/bugs/show_bug.cgi?id=16067
[14] 刘磊, 郑红军, 金成植. 基于信息流分析的部分求值技术. 软件学报, 1995, 6(8): 509–513. http://www.jos.org.cn/ch/reader/view_abstract.aspx?flag=1&file_no=19950810&journal_id=jos