Automatic customization of classes

• US 8,132,150 B2
• Filed: 02/20/2008
• Issued: 03/06/2012
• Est. Priority Date: 09/29/2003
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: De Sutter, Bjorn, Dolby, Julian, Tip, Frank
• Primary Examiner(s): Dam, Tuan
• Assistant Examiner(s): Wei, Zheng
• Application Number:
  US12/034,359
• Publication Number:
  US 20080189696A1
• Time in Patent Office: 1,476 Days
• Field of Search: None
• US Class Current: 717/108
• CPC Class Codes: G06F 8/36 Software reuse
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

A method and computer readable medium for automatic replacement of object classes in a library with custom classes to improve program efficiency. The method begins with static analysis preformed on a program containing a plurality of objects in order to determine type-correctness constraints and to detect unused functionality in one or more of the objects to be replaced. The plurality of objects is instrumented to detect usage patterns of functionality in one or more objects. Customized classes are generated based upon the static analysis and usage patterns detected. Bytecode is rewritten which is used for generating classes. The present invention provides transparency in the replacement of the objects.

Claims

1. A method on an information processing system for automatic replacement of object classes, comprising:

performing static analysis on a program containing a plurality of objects in order to determine constraints on transformations that can be applied and to detect unused functionality in one or more of the objects to be replaced;

analyzing the plurality of objects to detect usage patterns of functionality in the one or more objects replaced;

and

generating customized classes based upon the static analysis and the usage patterns detected;

wherein generating customized classes based upon the usage patterns detected includes;

identifying a customizable container class C with superclass B;

creating a class CustomC which contains methods and fields that are identical to those in class C, wherein if B is not customizable, then CustomC'"'"'s superclass is B, otherwise CustomC'"'"'s superclass is CustomB;

introducing a type C^T, and making both C and CustomC a subtype of C^T and wherein type C^T contains declarations of all methods in C that are not declared in any superclass of C; and

introducing a type C^⊥

, and making C^⊥

a subclass of both C and CustomC, wherein type C^⊥

contains no methods, and wherein C^T and C^⊥

are intermediate types not provided as output during the generating of custom classes; and

determining at least one equivalence class E of declaration elements and expressions that must have a same type.

2. The method according to claim 1, wherein the performing static analysis on a program containing a plurality of objects in order to determine constraints includes determining constraints which are type constraints.

3. The method according to claim 1, wherein the plurality of objects is a plurality of container objects.

4. The method according to claim 1, wherein the analyzing the plurality of objects includes instrumenting the plurality of objects to detect usage patterns of functionality in the one or more objects replaced.

5. The method according to claim 1, further comprising rewriting bytecode of an application to use the generated classes while providing transparency in the program'"'"'s observable behavior during the replacement of the objects.

6. The method according to claim 1, wherein the performing static analysis further comprises performing static analysis to determine constraints by determining if the type of one or more objects to be replaced is a supertype of a type referenced in a cast expression.

7. The method according to claim 1, wherein the performing static analysis further comprises performing static analysis to determine type-correctness constraints by determining if the type of one or more objects to be replaced is a supertype of a type referenced in a cast expression.

8. The method according to claim 1, wherein the performing static analysis further comprises performing static analysis to determine interface-compatibility constraints in one or more of the objects to be replaced.

9. The method according to claim 1, wherein the performing static analysis further comprises performing static analysis to preserve run-time behavior for casts and instanceof operations for one or more of the objects to be replaced.

10. The method according to claim 1, wherein the performing static analysis includes using points-to analysis to determine where references to classes in allocation sites, declarations, casts and instanceof-expressions are modifiable to refer to one or more of the objects to be replaced.

11. The method according to claim 1, wherein the performing static analysis includes using points-to analysis to determine where references to container classes in allocation sites, declarations, casts and instanceof-expressions are modifiable to refer to one or more of the objects to be replaced.

12. The method according to claim 1, wherein the generating customized classes does not require a programmer to supply any additional types and additional external declarations for the customized classes.

13. The method according to claim 1, further comprising:

analyzing at least one execution of the program to collect profile information for the one or more objects; and

using the profile data, which has been collected, to perform at least one of;

refining usage patterns and unused functionality in the plurality of objects; and

assessing a profitability of customization.

14. The method according to claim 1, wherein the generation of customized classes based upon the usage patterns detected includes:

computing a set of possible types for equivalence class E using an optimistic algorithm, wherein this algorithm associates a set S_E of types with equivalence class E, which is initialized as follows;

associating a set S_E with the equivalence class E containing the types C and CustomC if E contains an allocation site expression new C; and

associating a set S_E with the equivalence class E containing all types except auxiliary types C^T and C^⊥

, wherein C^T and C^⊥

are intermediate types not provided as output during the generation of custom classes if E does not contain any allocation site expressions.

15. The method according to claim 14, further comprising:

identifying sets S_D and S_E for each pair of equivalence classes D, E such that there exists a type constraint D≦

E;

removing from set S_D any type that is not a subtype of a type that occurs in S_E; and

removing from set S_E any type that is not a supertype of a type that occurs in S_D;

wherein the removing of S_D and S_E is performed repeatedly until a fixed point is reached.

16. A computer readable storage medium containing programming instructions for automatic replacement of object classes, the programming instructions comprising:

performing static analysis on a program containing a plurality of objects in order to determine constraints on transformations that can be applied and to detect unused functionality in one or more of the objects to be replaced;

analyzing the plurality of objects to detect usage patterns of functionality in the one or more objects replaced;

and

generating customized classes based upon the static analysis and the usage patterns detected;

wherein generating customized classes based upon the usage patterns detected includes;

identifying a customizable container class C with superclass B;

creating a class CustomC which contains methods and fields that are identical to those in class C, wherein if B is not customizable, then CustomC'"'"'s superclass is B, otherwise CustomC'"'"'s superclass is CustomB;

introducing a type C^T, and making both C and CustomC a subtype of C^T and wherein type C^T contains declarations of all methods in C that are not declared in any superclass of C; and

introducing a type C^⊥

, and making C^⊥

a subclass of both C and CustomC, wherein type C^⊥

contains no methods, and wherein C^T and C^⊥

are intermediate types not provided as output during the generating of custom classes; and

determining at least one equivalence class E of declaration elements and expressions that must have a same type.

17. The computer readable storage medium according to claim 16, wherein the performing static analysis on a program containing a plurality of objects in order to determine constraints includes determining constraints which are type constraints.

18. The computer readable storage medium according to claim 16, wherein the plurality of objects is a plurality of container objects.

19. The computer readable storage medium according to claim 16, wherein the analyzing the plurality of objects includes instrumenting the plurality of objects to detect usage patterns of functionality in the one or more objects replaced.

20. The computer readable storage medium according to claim 16, further comprising rewriting bytecode of an application to use the generated classes while providing transparency in the program during the replacement of the objects.