Slicing Object-Oriented Software1

Loren D. Larsen2 and Mary Jean Harrold
Department of Computer Science
Clemson University
Clemson, SC 29634-1906
fllarsen, [email protected]

Abstract
We describe the construction of system dependence graphs for object-oriented software on which efficient slicing algorithms can be applied. We construct these system dependence graphs for individual classes, groups of interacting classes, and complete object-oriented programs. These system dependence graphs consist of a class dependence graph for each class in the system and a procedure dependence graph that represents a calling program. For an incomplete system consisting of a single class or a number of interacting classes, we construct a procedure dependence graph that simulates all possible calls to public methods in the class. For a complete system, we construct a procedure dependence graph from the main program in the system. Using these system dependence graphs, we show how to compute slices for the individual classes, groups of interacting classes or complete programs. Our slicing algorithm is based on an interprocedural slicing algorithm that utilizes graph reachability. One advantage of our approach is that the system dependence graphs can be constructed incrementally because representations of classes can be reused many times. Another advantage of our approach is that slices can be computed for incomplete object-oriented programs such as classes or class libraries. We present our results for C++, but our techniques apply to other statically typed object-oriented languages such as Ada-95.

1 Introduction

Program slicing has many applications such as debugging, code understanding, program testing, reverse engineering, software metrics and automatic parallelization [7, 8, 9, 15, 18, 20, 26, 32]. Weiser [36] defined a slice with respect to a slicing criterion that consists of a program point p and a subset of program variables V . His slices were executable programs that were constructed by removing zero or more statements from the original program. He presented algorithms, which use dataflow analysis on control flow graphs, to compute intraprocedural and interprocedural slices. Ottenstein and Ottenstein [27] defined a slicing criterion to consist of a program point p and a variable v, which is defined or used at p. They compute a slice, using a graph reachability algorithm on a program dependence graph, consisting of all statements and predicates of the program that may affect the value of v at p. Horwitz, Reps and Binkley [19] also use dependence graphs to compute slices. They developed an interprocedural program representation, the system dependence graph, and a two-pass graph reachability slicing algorithm that uses the system dependence graph. Their two-pass algorithm computes more precise interprocedural slices than previous algorithms because it uses summary information at call sites to account for the calling context of called procedures. Researchers have considered ways to extend language features represented by system dependence graphs. These language features include arrays [3, 17, 24, 27], reference parameters [19], pointers [11, 17, 21] and non-structured control flow [2, 4, 12]. Researchers have also proposed variations of dependence graphs that facilitate finer-grained slices [20, 23], and have developed techniques to perform slicing on optimized code [13].3

1This work was partially supported by grants from Microsoft, Inc. and Data General Corp., and by NSF under Grants CCR-9109531 and CCR-9357811 to Clemson University.
2Current address: IBM Corporation, Research Triangle Park, North Carolina.
3For a survey of program slicing techniques see reference [34].