Slicing Object-Oriented Software1

Loren D. Larsen and Mary Jean Harrold
Department of Computer Science
Clemson University
Clemson, SC 29634-1906
Contact: Mary Jean Harrold
TEL: (803) 656-0809
FAX: (803) 656-0145
E-Mail: fllarsen, [email protected]

Abstract
We describe the construction of system dependence graphs for object-oriented software on which efficient slicing algorithms can be applied. 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 each class C in the system, we construct a class dependence graph, and reuse it in the construction of classes that are derived from C and classes that interact with C. 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. We use these system dependence graphs to perform slicing for individual classes, derived classes, interacting classes or complete object-oriented systems. This slicing information is useful in a number of applications, including debugging, code understanding, software metrics and testing. Our approach to representing incomplete systems permits computation of slices for individual classes or objects. Our techniques focus on efficiency in construction and storage by reusing previously computed components whenever possible. We present our results for C++ but our techniques apply to any object-oriented programming language.

Keywords: program slicing, program analysis, object-oriented, system dependence graph, reuse, class

1 Introduction

Program slicing has many important applications such as debugging, code understanding, program testing, software metrics and automatic parallelization [4, 5, 6, 9, 12, 16, 20]. Weiser [22] originally defined a slice with respect to a program point p and a subset of program variables V to consist of all statements in the program that may affect the values of variables in V at point p. He also presented algorithms to compute intraprocedural and interprocedural slices. Horwitz, Reps and Binkley [13] modified Weiser's definition of a slice so that it is defined with respect to a program point p and a variable x that is defined or used at p. They also developed a program representation, the system dependence graph, and an efficient two-pass 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. The major factor in the cost of constructing a system dependence graph is the computation of this summary information at call sites. Recently an algorithm was presented that improves this cost asymptotically [18].

Although system dependence graphs have been constructed for many different programming languages, currently no techniques exist that adequately define system dependence graphs for the full range of object1This 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.