An Extensible Program Representation

for
Object-Oriented Software1

Brian A. Malloy
John D. McGregor
Anand Krishnaswamy
Murali Medikonda
Dept. of Computer Science
Clemson University
Clemson, SC 29634-1906

Abstract

An extensible representation for object-oriented programs is presented. It is based on the concept of a program dependency graph and elaborated to include both control flow and data flow information. The representation takes advantage of the basic incremental philosophy of the object-oriented approach to develop a more compact representation that is useful with practical programs. The basic approach reported here provides a static view of an object-oriented program. The approach can be expanded to provide dynamic information for tools such as interactive debuggers and other runtime tools. The outline of this extension is also presented.

1 Introduction

A number of software support tools and program analysis tools have been constructed using a program dependency graph (PDG) as the underlying representation for the program being analyzed. In this work we adapt the basic concept of a PDG to a representation for object-oriented software.

This paper presents several contributions. Most important is a representation of dynamically bound messages. Inclusion polymorphism is widely used in object-oriented design and dynamic binding of messages to methods is an important aspect of the implementation of that type of polymorphism. No realistic program representation can be developed for object-oriented software without support for dynamic binding.

A second contribution is the incremental approach used in building the representation. A class can be defined in terms of other classes using the inheritance feature of an object-oriented language. Our representation follows this same incremental strategy. The representation for a class is built from the representation of its parent classes. This allows a more compact representation that in turn permits the representation of real programs of significant size.

A third is that the program representation is built in layers that differentiate between the static, compiletime semantics of the program and the dynamic, execution time behavior of the program. This allows tools, that perform static analysis, to use a simple representation and be compactly written. The representation easily expands to support the needs of runtime tools.
The representation described in this paper has been developed with several objectives in mind. The representation should be:

ffl sufficiently expressive to support a range of program analysis activities.

ffl layered so that only the portion of the representation needed for a particular task is built.

ffl extensible so that additional types of nodes and edges may be added to adapt to the special characteristics of a specific language.

In the next section we provide the background needed to understand the representation. This includes a brief description of the basic concepts of object-oriented systems and the definitions and terminology of

1This research was partially supported by a grant from COMSOFT, IBM and BNR.