Christoph Steindl's Abstract

Intermodular Slicing of Object-Oriented Programs

University Linz
Altenbergerstraße 69 A - 4040 Linz
tel: ++43-732/2468-7134
fax: ++43-732/2468-7138
steindl@ssw.uni-linz.ac.at

Keywords:

slicing program analysis dynamic binding intermodular interprocedural

Abstract:

We describe a program slicing tool for object-oriented programs. Program slicing [Wei84] uses control flow and data flow information to visualise dependences and assist the programmer in debugging and in program understanding. Object-oriented programs exploit features like dynamic binding which complicate interprocedural alias analysis. Two distinctive features of our Slicerare the support for intermodular slicing and the usage of user-feedback during the computation of data flow information. To cope with the problem of alias analysis in the presence offunction pointers (which is NP-hard [ZhR94]), we decided to first use a conservative approach leading to less precise data flow information, but then use the user's expertise to restrict the effects of dynamic binding at polymorphic call sites to get more precise solutions which should still be safe.

Overview:

We implemented a program slicing tool for static forward slicing of object-oriented programs written in the programming language Oberon-2 [MöWi91] (for a technical description see [Ste98a, Ste98b]). We did not restrict the language in any kind which means that we had to cope with structured types (records and arrays), global variables of any type, objects on the heap, side-effects of function calls, nested procedures, recursion, dynamic binding due to type-bound procedures (methods) and procedure variables (function pointers), and modules.
Weiser [Wei84] originally defined a slice with respect to a program point pand a subset of the program variables Vto consist of all statements in the program that may affect the values of the variables in Vat point p. He presented algorithms which use data flow analysis on control flow graphs to compute intraprocedural and interprocedural slices. The underlying data structures of our Slicerare the abstract syntax tree (AST)and the symbol table constructed by the front-end of the Oberon compiler [Cre90]. Additional information (such as control and data dependences) is added to the nodes of this syntax tree during the computation. We define a slice with respect to anode of the AST (starting node). The nodes of the AST represent the program at a fine granularity (see Fig. 1), i.e. one statement can consist of many nodes (function calls, operators, variable usages, variable definitions, etc.). The target and origin of control and data dependences are nodes of the AST, not whole statements. This allows for fine-grained slicing (cf. [Ern94]), therefore we call our slicing method expression-orientedin contrast to statement-orientedslicing or even procedure-oriented slicing. Our slicing algorithm is based on the two-pass slicing algorithm of Horwitz et al. [HRB90] where slicing is seen as a graph-reachability problem (this algorithm uses summary information at call sites to account for the calling context of procedures) and on the algorithm of Livadas et al. [LivC94, LivJ95] for the computation of transitive dependences of parameters of procedures. In order to slice the program with respect to the starting node, the graph representation of the program is traversed backwards from the starting node along control and data dependence edges. All nodes that could be reached belong to the slice because they potentially affect the starting node.
We extended the notion of interproceduralslicing to intermodularslicing. Information that has been computed once is reused when slicing other modules that import previously sliced modules. Furthermore, we support object-oriented features such as inheritance, type extension, polymorphism, and dynamic binding. Since the construction of summary information at call sites is the most costly computation, it is worthwhile to cache this information in a repository and reuse as much information as possible from previous computations.
Zhang and Ryder showed that aliasing analysis in the presence of function pointers is NP-hard in most cases [ZhR94]. This justifies to use safe approximations since exact algorithms would be prohibitive for an interactive slicing tool where the maximum response time must be in the order of seconds. Our approach to reach satisfying results is to use feedback from the user during the computation of data flow information. The user can for example restrict the dynamic type of polymorphic variables and thereby disable specific destinationsat polymorphic call sites.

Bibliography :

[Cre90]  Régis Crelier, OP2: A Portable Oberon Compiler. Technical report 125, ETH Zürich, February 1990.
[Ern94]  Michael D. Ernst: Practical fine-grained static slicing of optimized code. Technical report MSR-TR-94-14, Microsoft Research.
[HRB90]  Susan Horwitz, Thomas Reps, David Binkley: Interprocedural Slicing Using Dependence Graphs. ACM TOPLAS vol. 12, no. 1, Jan. 1990.
[LivJ95]  Panos E. Livadas, Theodore Johnson: An Optimal Algorithm for the Construction of the System Dependence Graph. Technical report, Computer and Information Sciences Department, University of Florida, 1995,
ftp://ftp.cis.ufl.edu/cis/tech-reports/tr95/tr95-011.ps.Z
[MöWi91]  Hanspeter Mössenböck, Niklaus Wirth: The Programming Language Oberon-2, Structured Programming, vol. 12, no. 4, 1991.
[Ste98a]  Christoph Steindl: Program Slicing (1) - Data Structures and Computation of Control Flow Information. Technical report 11, Institut für Praktische Informatik, JKU Linz, 1998.
[Ste98b]  Christoph Steindl: Program Slicing (2) - Computation of Data Flow Information. Technical report 12, Institut für Praktische Informatik, JKU Linz, 1997.
[Wei84]  Mark Weiser: Program Slicing. IEEE Trans. Software Engineering, vol. SE-10, no. 4, July 1984.
[ZhR94]  Sean Zhang, Barbara G. Ryder: Complexity of Single Level Function Pointer Aliasing Analysis.

The PhD work started: Feb 1996