1. Field of the Invention
The present invention generally relates to object-oriented programming (OOP), and in particular to OOP systems supporting the C++ and Java programming languages.
2. Background Description
Object-oriented programming languages provide a number of features such as classes, inheritance, multiple inheritance, and virtual inheritance. These object-oriented features have several advantages. Most importantly, they enable the creation of class libraries that can be reused in many different applications. Class libraries are typically shipped independently from applications that use them. Libraries are commonly shipped as a combination of the executable (object) code, in combination with the library""s interface. In order to use a library, a client application calls functions specified in the library""s interface, and includes (links) the library""s object code. This model has the advantage that a library has to be shipped and installed only once, even when multiple applications use it. An additional benefit of this approach is that the library""s source code need not be exposed: Only the library""s external interface needs to be visible.
However, the unavailability of a library""s source code complicates so-called whole-program analysis of its client applications, which rely on the availability of the complete source code of an application. In particular, the unavailability of a library""s source code complicates the problem of determining which methods in the client application are xe2x80x9clivexe2x80x9d (i.e., possibly reached in some execution of the application, which is referred to below as being xe2x80x9creachablexe2x80x9d) or xe2x80x9cdeadxe2x80x9d (i.e., never reached in any execution of the application). The source for this problem is related to the fact that certain methods in the application code may be called indirectly from within the (unavailable) library code by way of a virtual method dispatch.
The prior art has focused on the elimination of unused methods for programs that do not use class libraries. An example of such prior art is Srivastava, xe2x80x9cUnreachable procedures in object oriented programmingxe2x80x9d, ACM Letters on Programming Languages and Systems, 1(4), pp. 355-364, December 1992.
Therefore, there is a need in the art to provide a mechanism for identifying unused methods for programs that use class libraries without requiring access to the source code for such class libraries.
The problems presented above and the related problems of the prior art are solved by the present invention, method and apparatus for finding reachable methods in applications that use class libraries. The present invention analyzes an application A and computes a set of reachable methods in A by determining the methods in A that may be called from another reachable method in A, or from within a class library L used by A without analyzing the classes in L.
The invention may be used as an optimization to reduce application size by eliminating unreachable methods. In the alternative, the invention may be used as a basis for optimizations that reduce execution time (e.g., by means of call devirtualization), and as a basis for tools for program understanding and debugging.