Removal of unreachable methods in object-oriented applications based on program interface analysis

• US 6,654,951 B1
• Filed: 12/14/1998
• Issued: 11/25/2003
• Est. Priority Date: 12/14/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bacon, David Francis, Laffra, Johannes C., Tip, Frank, Sweeney, Peter Francis
• Primary Examiner(s): INGBERG, TODD D
• Application Number:
  US09/211,176
• Time in Patent Office: 1,807 Days
• Field of Search: 717/151, 717/153, 717/159
• US Class Current: 717/154
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis
• CPC Class Codes: G06F 9/449 Object-oriented method invocation or resolution

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.

Claims

1. A method for generating a representation of an object-oriented program P which uses an interface I of a class library L, the method comprising the steps of:

identifying a first set of classes C in the P that may be instantiated;

for a given class cl in the P, such that said given class cl is instantiated and overrides a method f declared in the L, identifying a set S of methods reachable by a dynamic dispatch within the L based upon said interface I;

identifying methods in the set S as reachable; and

excluding methods of the P that are not in the S from said representation of said program P.

2. The method of claim 1, further comprising the steps of:

identifying a second set containing initially reachable methods within the P;

identifying the methods of the second set as reachable; and

excluding methods of the P that are not reachable from said representation of said program P.

3. The method of claim 1, further comprising the steps of:

for a given method m in the P, identifying a third set containing call sites reachable within the m;

identifying the call sites of the third set as reachable; and

excluding call sites of the P that are not reachable from said representation of the P.

4. The method of claim 1, further comprising the steps of:

for a given method m in the P, identifying a fourth set containing class instantiation sites reachable within the m;

identifying the class instantiation sites of the fourth set as reachable; and

excluding class instantiation sites of the P that are not reachable from said representation of the P.

5. The method of claim 1, further comprising the steps of:

for a given call site c in the P, identifying a fifth set containing methods in the P reachable from the c;

identifying the methods of the fifth set as reachable; and

excluding methods of the P that are not reachable from said representation of the P.

6. A method for generating a representation of an object-oriented program which uses an interface of a class library, the method comprising the steps of:

identifying a first set containing initially reachable methods in the program;

for a given method in the program, 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 program, identifying a fourth set containing methods in the program reachable by a dynamic dispatch from the given call;

determining a set of class library methods overridden by the program based on the interface, wherein the set of class library methods can be executed as a result of a dynamic dispatch from executable code of the class library;

identifying the calls of the second set, the classes of the third set, and the methods of the first, third, and fourth sets, and the library method sets as reachable; and

excluding calls, classes, and methods of the program that are not reachable from the representation of the program.

7. The method according to claim 6, wherein said step of identifying the first set comprises the step of identifying a main method of the program.

8. The method according to claim 6, 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.

9. The method according to claim 6, 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.

10. The method according to claim 6, wherein said step of identifying the second set comprises the step of analyzing data flow one of to and from calls in the given method.

11. The method according to claim 6, 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.

12. The method according to claim 6, 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.

13. The method according to claim 6, 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.

14. The method according to claim 6, wherein said step of determining the set of class library methods further comprises the step of identifying methods of superclasses corresponding to the given class reachable by the dynamic dispatch within the class library based on the interface.

15. The method according to claim 6, wherein said step of determining the set of class library methods comprises the step of determining library classes from which the given class inherits.

16. The method according to claim 15, 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.

17. The method according to claim 16, 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.

18. The method according to claim 6, 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.

19. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for generating a representation of an object-oriented program which uses an interface of a class library, said method steps comprising:

identifying a first set containing classes in the program that may be instantiated;

for a given class in the program that is instantiated and overrides a method in the class library, identifying a second set containing methods of the given class reachable by a dynamic dispatch within the class library based on the interface;

identifying the methods in the second set as reachable; and

excluding methods of the program that are not in the second set from the representation of the program.