Method for determining reachable methods in object-oriented applications that use class libraries

• US 6,463,581 B1
• Filed: 12/14/1998
• Issued: 10/08/2002
• Est. Priority Date: 10/03/1996
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bacon, David Francis, Tip, Frank, Laffra, Johannes C., Sweeney, Peter Francis
• Primary Examiner(s): Morse, Gregory
• Assistant Examiner(s): NGUYEN BA, HOANG VU A
• Application Number:
  US09/211,177
• Time in Patent Office: 1,394 Days
• Field of Search: 717/1, 717/9, 717/4, 717/8, 717/10, 717/5, 717/100, 717/106, 717/108, 717/116, 717/124, 717/143, 717/146, 717/151-161, 717/162-167, 717/136-142, 707/3, 707/103, 707/103.R, 709/315
• US Class Current: 717/154
• CPC Class Codes: G06F 8/4434 Reducing the memory space required by the program code
• CPC Class Codes: G06F 9/4491 Optimising based on receiver type

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.

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.

2. The method according to claim 1, wherein said step of identifying the first set comprises the step of identifying a main method of the object-oriented program.

3. The method according to claim 1, wherein said step of identifying the first set comprises the steps of identifying initialization methods for at least one of statically scoped variables and globally scoped variables.

4. The method according to claim 1, wherein said step of identifying the second set comprises the step of identifying all calls in the given method as reachable, when the given method is reachable by a static call or a dynamic call.

5. The method according to claim 1, wherein said step of identifying the second set comprises the step of analyzing data flow to or from calls in the given method.

6. The method according to claim 1, wherein said step of identifying the second set comprises the step of excluding calls in methods corresponding to a library class from the second set.

7. The method according to claim 1, wherein said step of identifying the third set comprises the step of identifying all classes instantiated in the given method as reachable, when the given method is reachable by a static call or a dynamic call.

8. The method according to claim 1, wherein said step of identifying the third set comprises the step of excluding classes in methods corresponding to a library class from the third set.

9. The method according to claim 1, wherein said step of identifying the fifth set further comprises the step of identifying methods of base classes corresponding to the given class reachable by the dynamic dispatch within the library based on the interface.

10. The method according to claim 1, wherein said step of identifying the fifth set comprises the step of determining library classes from which the given class inherits.

11. The method according to claim 10, wherein said step of determining the library classes from which the given class inherits comprises the steps of:

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.

16. The program storage device according to claim 15, wherein said step of identifying the first set comprises the step of identifying a main method of the object-oriented program.

17. The program storage device according to claim 15, wherein said step of identifying the first set comprises the steps of identifying initialization methods for at least one of statically scoped variables and globally scoped variables.

18. The program storage device according to claim 15, wherein said step of identifying the second set comprises the step of identifying all calls in the given method as reachable, when the given method is reachable by a static call or a dynamic call.

19. The program storage device according to claim 15, wherein said step of identifying the second set comprises the step of analyzing data flow to or from calls in the given method.

20. The program storage device according to claim 15, wherein said step of identifying the second set comprises the step of excluding calls in methods corresponding to a library class from the second set.

21. The program storage device according to claim 15, wherein said step of identifying the third set comprises the step of identifying all classes instantiated in the given method as reachable, when the given method is reachable by a static call or a dynamic call.

22. The program storage device according to claim 15, wherein said step of identifying the third set comprises the step of excluding classes in methods corresponding to a library class from the third set.

23. The program storage device according to claim 15, wherein said step of identifying the fifth set further comprises the step of identifying methods of base classes corresponding to the given class reachable by the dynamic dispatch within the library based on the interface.

24. The program storage device according to claim 15, wherein said step of identifying the fifth set comprises the step of determining library classes from which the given class inherits.

25. The program storage device according to claim 24, wherein said step of determining the library classes from which the given class inherits comprises the steps of:

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.