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

于恒彪 等: 面向编译优化结果不一致的代码高效定位 5393

C 1 和 C 2 在编译程序 P 时记录每个函数的浮点指令序列 (第 3, 4 行). 需要说明的是本文通过静态扫描函数指令序
列的方式来获取函数的浮点指令序列, 并非在运行时检查记录浮点指令. 因为包含循环体的程序动态执行时会产
生大量浮点指令, 极大增加浮点指令序列差异性系数的计算开销. 接着, Diff 函数会计算每个待搜索函数在不同编
译优化选项下的浮点指令序列差异性系数, 并作为该函数的优先级评分 (第 5 行). 差异性为 0 表示该函数在不同
编译优化选项下浮点计算行为未发生改变, 直接过滤掉 (第 6, 7 行). 最后 sort(list, score_dict) 会按照差异性系数的
降序对列表 list 进行排序 (第 9 行). 函数的差异性系数高意味着该函数的浮点计算行为受高级别编译优化改变的
程度大, 将这些函数放置在待定位函数列表的前部, 会被 Delta-Debugging 优先探索定位.
算法 1. 基于浮点指令序列差异性的函数过滤和排序 FilterSort(P, flist, C 1 , C 2 ).

输入: 目标程序 P、函数列表 flist、编译优化选项 C 1 和 C 2 ;
输出: 过滤排序后的待搜索定位函数列表 list.
FilterSort(P, flist, C 1 , C 2 )
1. list = [], score_dict = {}
2. for func in flist do
3. tf 1 ← compileRecord(P, func, C 1 )
4. tf 2 ← compileRecord(P, func, C 2 )
5. score_dict[func] = Diff(tf 1 , tf 2 )
6. if score_dict[func] ≠ 0 then
7. list.add(func)
8. end for
9. sort(list, score_dict)
10. return list

下面详细介绍浮点指令差异性系数计算函数 Diff. 给定两个浮点指令序列 tf 1 和 tf 2 , 函数 Ratio(tf 1 , tf 2 ) 会计算
两个浮点指令序列的相似值; Diff(tf 1 , tf 2 )=1.0–Ratio(tf 1 , tf 2 ). Ratio(tf 1 , tf 2 ) 计算基于经典的最长匹配迭代计算策略
(https://docs.python.org/3/library/difflib.html#sequencematcher-objects), 具体步骤如下.
(1) 队列 QS 包含待计算相似值的序列对, 初始为{(tf 1 , tf 2 )}. 队列 MS 存放计算得出的匹配序列, 初始为空队
列. 执行步骤 2.
(2) 判定 QS 是否为空, 若为空则跳转执行步骤 4; 否则, 从 QS 中取出一个待匹配指令序列对 (t 1 , t 2 ),
Match(t 1 ,t 2 ) 会获取 t 1 和 t 2 中的最长匹配序列, 记为 ms, 并将 ms 加入到 MS 中. 执行步骤 3.
(3) ExcludeL(t 1 , t 2 , ms) 计算序列 t 1 和 t 2 排除掉 ms 后得到的左侧指令序列, 记录为 t 和 , 若果 t 和 t 均不为
l
l
t
l
l
1
2
1
2
l
l
空, 则将 (t , t ) 加入到 QS 中. 类似的, ExcludeR(t 1 , t 2 , ms) 计算序列 t 1 和 t 2 排除掉 ms 后得到的右侧指令序列, 记录
1 2
r
r
r r r r (t , t ) 加入到 中. 跳转至步骤
t
为 t 和 , 若果 t 和 t 均不为空, 则将 QS 2.
1 2 1 2 1 2
(4) 计算 MS 中所有指令序列的长度和, 记为 M. 计算 tf 1 和 tf 2 的指令长度和, 记为 T; Ratio(tf 1 , tf 2 )=2×M/T.
假定存在两个浮点指令序列 tf 1 =<fsub, fadd, fma, fmov, fdiv, fmul>, tf 2 =<fadd, fma, fdiv, fmul>. 首先计算得出最
长匹配序列为<fadd, fma>加入到 MS 中, 此时 t =<fsub>, t =<>, t =<fmov, fdiv, fmul>, t =<fdiv, fmul>. 因为 t 和 t 均
r
r
l
r
r
l
1 2 1 2 1 2
(t , t ) 加入到 QS 中; 接着从 QS 取出待计算匹配对 (<fmov, fdiv, fmul>, <fdiv, fmul>), 得出最长匹配对
r
r
非空, 故将 1 2
<fdiv, fmul>, 将其加入到 MS 中, 此时 t =<fmov>, t =<>, t =<>, t =<>, 因此 QS 不会再加入新的待计算匹配对并变
r
r
l
l
1 2 1 2
为空. 最终 MS={<fadd, fma>, <fdiv, fmul>}, 其所有序列的长度和 M 为 4, tf 1 和 tf 2 的指令长度和为 10, 因此
Ratio(tf 1 , tf 2 )=2×4/10=0.8. 计算得到相似值 Ratio 后, 差异值 Diff(tf 1 , tf 2 )=1.0–Ratio(tf 1 , tf 2 )=0.2.
3.3 基于 Delta-Debugging 的编译优化结果不一致性搜索定位
Delta-Debugging [11] 由 Zeller 教授提出, 用于在软件迭代开发过程中精确定位导致测试用例测试失效的代码改