PPR: Pairwise Program Reduction

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.