Page 13 - 《软件学报》2025年第12期

5394 软件学报 2025 年第 36 卷第 12 期

动位置. 搜索配置是一组代码改动位置的集合, Delta-Debugging 假定搜索配置满足单调性 (若配置 c 导致了测试
失效则任何包含 c 的配置都会导致测试失效)、无歧义性 (若配置 c 1 和 c 2 均能导致测试失效则 c 1 ∧ c 2 也能导致失
效, 即要求产生失效的改动集是唯一的) 和一致性 (任何配置的测试结果是确定的, 即通过或失效).
给定原始程序 P 和对 P 进行代码改动的位置集合{l 1 , l 2 ,…, l n }更新后测试失效. Delta-Debugging 调试 DD(P,
{l 1 , l 1 ,…, l n }) 会返回导致测试失效的最小代码改动位置集合. 如果 n=1 则返回 l 1 . 否则令 P 1 ← P⊕{l 1 ,…, l n/2 },
P 1 测试失效返回 P 2 测试失效返回
P 2 ←P⊕{l n/2+1 ,…, l n }, 其中⊕表示代码合并. 如果 DD(P, {l 1 ,…, l n/2 }), 如果
DD(P, {l n/2+1 ,…, l n }), 否则返回 DD( P 2 , {l 1 ,…, l n/2 })∪DD( P 1 , {l n/2+1 ,…, l n }). Delta-Debugging 本质是一种带回溯的
分治搜索过程.
本文将 Delta-Debugging 思想移植应用到导致编译优化结果差异性的问题代码定位上. 搜索过程仍然是沿用
PLiner 的分层搜索, 即先定位问题文件、函数列表, 再依次定位函数内部的循环、基本块和语句. 为了简洁性, 本
文以函数级的 Delta-Debugging 搜索为例进行说明.
算法 2 展示了基于 Delta-Debugging 的函数级代码定位过程. 算法输入包括程序 P、函数列表 flist 和触发结
果不一致性的不同编译选项 C 1 和 C 2 , 这里假定 C 2 为高级别编译优化选项, 输出包括定位是否成功标识和触发编
译优化结果不一致性的问题函数列表. 给定函数列表 list 1 和 list 2 , list 1 ∪list 2 表示将两个列表中的函数序列求并集
后生成的函数列表. 函数 transform(P, list) 会将程序 P 中在列表 list 里的函数都提升为高精度, 生成精度提升版程
序. 如果在高级别编译优化选项 C 2 下执行所有函数都精度增强后的程序仍然存在结果不一致性则返回定位失败
和 flist (第 2, 3 行), 否则基于 Delta-Debugging 来搜索定位 flist 中触发结果不一致性的函数.
DDFuncLoc 定位是一个递归分治过程. 首先, 如果当前成功修复结果不一致性问题的增强函数列表 flist 只包
含一个函数, 则直接返回 true 和该列表 (第 4, 5 行). 接着, 函数 partition(flist) 会将 flist 中的函数均分成 left 和
right. 如果增强 left 中的函数精度能解决结果不一致性, 则递归调用 DDFuncLoc(P, left, C 1 , C 2 ) 来对 left 列表继续
精化搜索 (第 7–10 行). 类似的, 如果增强 right 中的函数精度能解决结果不一致性, 则递归调用 DDFuncLoc(P,
right, C 1 , C 2 ) 来对 right 列表继续精化搜索 (第 11–14 行). 当列表 left 和 right 单独增强精度都不能解决结果不一致
性时, 按照 Delta-Debugging 思路通过回溯递归来搜索定位. 具体而言, 将 P 中 left 列表所包含的函数精度增强得
到新的代码基准 P left , 递归调用 DDFuncLoc(P left , right, C 1 , C 2 ) 来搜索 right 列表中导致结果不一致性的函数 (第
16 行). 类似的, 将 P 中 right 列表所包含的函数精度增强得到新的代码基准 P right , 递归调用 DDFuncLoc(P right , left,
C 1 , C 2 ) 来搜索 left 列表中导致结果不一致性的函数 (第 17 行). 最后, 定位成功情况为左右两侧定位情况的逻辑与
flag 1 ∧flag 2 , 定位结果为左右两侧定位结果的并集 list 1 ∪list 2 (第 18–20 行).

算法 2. 基于 Delta-Debugging 的函数级搜索定位算法 DDFuncLoc.

输入: 目标程序 P、函数列表 flist、编译优化选项 C 1 和 C 2 ;
输出: 定位是否成功标识、触发编译优化结果差异性的问题函数列表.
DDFuncLoc(P, flist, C 1 , C 2 )
1. P enhanced ← transform(P, flist)
2. if Execute(P enhanced , C 2 ) ≠ Execute(P, C 1 ) then
3. return false, flist
4. if size(flist)==1 then
5. return true, flist
6. left, right ← partition(flist)
7. P left ← transform(P, left)
8. if Execute(P left , C 2 ) == Execute(P, C 1 ) then
9. flag, list = DDFuncLoc(P, left, C 1 , C 2 )