PPR: Pairwise Program Reduction

Abstract

Program reduction is a practical technique widely used for debugging compilers. To report a compiler bug with a bug-triggering program, one needs to minimize the program by removing bugirrelevant program elements first. Though existing program reduction techniques, such as C-Reduce and Perses, can reduce a bug-triggering program as a whole, they overlook the fact that the degree of relevance of each remaining token to the bug varies. To this end, we propose Pairwise Program Reduction (PPR), a new program reduction technique for minimizing a pair of programs w.r.t. certain properties. Given a seed program 𝑃𝑠 , a variant 𝑃𝑣 derived from 𝑃𝑠 , and the properties 𝑃𝑠 and 𝑃𝑣 exhibit separately (e.g., 𝑃𝑣 crashes a compiler whereas 𝑃𝑠 does not), PPR not only reduces the sizes of 𝑃𝑠 and 𝑃𝑣 , but also minimizes the differences between 𝑃𝑠 and 𝑃𝑣 . The final result of PPR is a pair of minimized programs that still preserve the properties, but the minimized differences between the pair highlight the critical program elements that are highly related to the bug. To thoroughly evaluate PPR, we manually constructed the first pairwise benchmark suite from real-world compiler bugs (20 bugs in GCC and LLVM, 9 bugs in Rustc and 9 bugs in JerryScript). The evaluation results show that PPR significantly outperforms the baseline: DD, a variant of Delta Debugging. Specifically, on large and complex programs, PPR’s reduction results are only 0.6% of those by DD w.r.t. program size. The sizes of the minimized variants (i.e., 𝑃𝑣 ) by PPR are also comparable to those by Perses and C-Reduce; but PPR offers more for debugging by highlighting the critical, bug-inducing changes via the minimized differences. Evaluation on Rust and JavaScript demonstrates PPR’s strong generality to other languages.