New Foundation for Control-Dependence and Slicing for Modern Program Structures

摘要

The notion of control dependence underlies many program analysis and transformation techniques used in numerous applications. Despite wide application, existing definitions and approaches to calculating control dependence are difficult to apply seamlessly to modern program structures. Such program structures make substantial use of exception processing and increasingly support reactive systems designed to run indefinitely. This paper revisits foundational issues surrounding control dependence and develops definitions and algorithms for computing control dependence that can be directly applied to modern program structures. In the context of slicing reactive systems, the paper proposes a notion of slicing correctness based on weak bisimulation and proves that the definition of control dependence generates slices that conform to this notion of correctness. Finally, a variety of properties show that the new definitions conservatively extend classic definitions. These new definitions and algorithms for control dependence form the basis of a publicly available program slicer that has been implemented for full Java.