We present flow analysis models for dependence graph based algorithms for (a) computing program slices and (b) computing summary information needed for slicing. Our models benefits typical of declarative specification. First, they show that algorithms for solving flow analysis problems may be applied to computing slices and summary information. Second, they make it explicit that SDG-based algorithms presented in the literature are essentially instances of the well-known worklist algorithm for solving flow analysis problems. Third, the models, being declarative, concisely express what is being computed, instead of focussing on how it is being computed. The models are more concise than the algorithms and provide a formal foundation for comparing different algorithms for the same problem. Third, with the existence of tools to generate analyzers from flow models, our models remove the necessity to present algorithms. As a demonstration, we present flow analysis model for a new interprocedural slicing algorithm that combines the computation of summary information and the computation of slice. That the new algorithm is equivalent to previous algorithms can be demonstrated by showing that their flow models are isomorphic.
Keywords: Program slicing, flow analysis models, worklist algorithm,
system dependence graph.
Full paper