Refined Program Slicing Based on Online Redundancy Removal

Program slicing is widely used in software engineering to support program comprehension, debugging, and testing. Most existing slicing techniques generate slices through reachability analysis over dependence graphs. However, such approaches do not distinguish between essential dependences and redundant dependences, causing many statements that do not actually affect the slicing criterion to be included in the slice. This phenomenon leads to slice bloat and makes it difficult for developers to identify the code that truly affects the slicing criterion. To address this problem, this paper introduces the concept of Redundant Code for a Slice (RCS), which refers to statements that appear in a slice due to dependence propagation but do not contribute to the values computed at the slicing criterion. We further identify six common types of RCS in real-world programs and propose a Marked System Dependence Graph (MSDG) to explicitly represent redundant and non-redundant dependences in the dependence graph. Based on MSDG, we present a refined program slicing algorithm, called RPS, which removes RCS online during dependence traversal and produces more concise slices that preserve the semantics of the slicing criterion. We evaluate RPS against traditional two-phase slicing, type slicing, and dynamic slicing on 20 open-source projects. The results show that RPS can reduce slice size by 49%, 45%, and 11% compared with the three baselines, respectively. In addition, we apply RPS to bug localization on the Defects4J benchmark. The results show that RPS can assist in locating 79% of bugs while reducing 20% of the slice size compared with type slicing.