Fine-grained Graph Representation for Program Slicing

Abstract

The system dependence graph (SDG) is the standard program representation used for program slicing, a technique that computes the SDG from the source code to explore the parts of a program that affect or are affected by an arbitrarily selected program point called slicing criterion. This paper shows how the representation provided by the SDG is imprecise when representing some program structures, demanding modifications to accurately apply program slicing over them, and we introduce an extension of the SDG to deal with all these representation problems in a natural way. This extension is called the expression dependence graph (EDG). The EDG extends the SDG by changing the granularity of its nodes to abstract syntax tree (AST) nodes. The new decomposed program representation leads to the definition of new program dependences that appear when breaking down statements into multiple nodes, and provides the potential of selecting any program (sub)expression as the slicing criterion.