Method for determining reachable methods in object-oriented applications that use class libraries
First Claim
1. A method for determining reachable methods in an object-oriented program which includes virtual method calls and which uses a class library having an interface, the method comprising the steps of:
- identifying a first set containing initially reachable methods in the object-oriented program;
for a given method in the object-oriented program that is reachable, including any of the initially reachable methods contained in the first set, identifying a second set containing calls reachable in the given method, and identifying a third set containing classes instantiated in the given method;
for a given call in the second set, identifying a fourth set containing methods in the program reachable by a dynamic dispatch from the given call; and
for a given class in the object-oriented program that is instantiated and that comprises any methods that override a method in the class library, identifying a fifth set containing methods of the given class reachable by a dynamic dispatch within the class library based on the interface.
2 Assignments
0 Petitions
Accused Products
Abstract
The present invention analyzes an application A and computes a set 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.
-
Citations
29 Claims
-
1. A method for determining reachable methods in an object-oriented program which includes virtual method calls and which uses a class library having an interface, the method comprising the steps of:
-
identifying a first set containing initially reachable methods in the object-oriented program;
for a given method in the object-oriented program that is reachable, including any of the initially reachable methods contained in the first set, identifying a second set containing calls reachable in the given method, and identifying a third set containing classes instantiated in the given method;
for a given call in the second set, identifying a fourth set containing methods in the program reachable by a dynamic dispatch from the given call; and
for a given class in the object-oriented program that is instantiated and that comprises any methods that override a method in the class library, identifying a fifth set containing methods of the given class reachable by a dynamic dispatch within the class library based on the interface. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
determining superclasses of the given class; and
identifying the superclasses that are the library classes.
-
-
12. The method according to claim 11, wherein said step of identifying the superclasses that are the library classes comprises the steps of:
-
receiving a list of library classes;
comparing the determined superclasses to the list of library classes; and
identifying a superclass of the given class as a library class, when the superclass matches the library class in the list of library classes.
-
-
13. The method according to claim 1, further comprising the step of iteratively repeating said step of identifying the second set, the third set, the fourth set, and the fifth set, until all reachable calls, classes, and methods have been identified.
-
14. The method according to claim 1, further comprising the step of excluding any methods of the object oriented program not included in any of the first set, the second set, the third set, the fourth set, and the fifth set from a representation of the object oriented program.
-
15. A program storage device readable by machine, tangibly embodying a program of instructions readable by the machine to perform method steps for determining reachable methods in an object-oriented program which includes virtual method calls and which uses a class library having an interface, said method steps comprising:
-
identifying a first set containing initially reachable methods in the object-oriented program;
for a given method in the object-oriented program that is reachable, including any of the initially reachable methods contained in the first set, identifying a second set containing calls reachable in the given method, and identifying a third set containing classes instantiated in the given method;
for a given call in the second set, identifying a fourth set containing methods in the program reachable by a dynamic dispatch from the given call; and
for a given class in the object-oriented program that is instantiated and that comprises any methods that override a method in the class library, identifying a fifth set containing methods of the given class reachable by a dynamic dispatch within the class library based on the interface. - View Dependent Claims (16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28)
determining superclasses of the given class; and
identifying the superclasses that are the library classes.
-
-
26. The program storage device according to claim 25, wherein said step of identifying the superclasses that are the library classes comprises the steps of:
-
receiving a list of library classes;
comparing the determined superclasses to the list of library classes; and
identifying a superclass of the given class as a library class, when the superclass matches the library class in the list of library classes.
-
-
27. The program storage device according to claim 15, further comprising the step of iteratively repeating said step of identifying the second set, the third set, the fourth set, and the fifth set, until all reachable calls, classes, and methods have been identified.
-
28. The program storage device according to claim 15, further comprising the step of excluding any methods of the object oriented program not included in any of the first set, the second set, the third set, the fourth set, and the fifth set from a representation of the object oriented program.
-
29. A method for determining reachable methods in an object-oriented program which includes virtual method calls and which uses a class library having an interface, the method comprising the steps of:
-
identifying a first set containing initially reachable methods in the object-oriented program, the first set containing at least a main method of the object-oriented program and any initialization methods for statically scoped or globally scoped variables;
for a given method in the object-oriented program that is reachable, including any of the initially reachable methods contained in the first set, identifying a second set containing calls reachable in the given method, and identifying a third set containing classes instantiated in the given method;
for a given call in the second set, identifying a fourth set containing methods in the program reachable by a dynamic dispatch from the given call;
for a given class in the object-oriented program that is instantiated and that comprises any methods that override a method in the class library, identifying a fifth set containing methods of the given class reachable by a dynamic dispatch within the class library based on the interface; and
excluding any methods of the object oriented program not included in any of the first set, the second set, the third set, the fourth set, and the fifth set from a representation of the object oriented program.
-
Specification