Method for optimizing creation and destruction of objects in computer programs

• US 6,381,738 B1
• Filed: 07/16/1999
• Issued: 04/30/2002
• Est. Priority Date: 07/16/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gupta, Manish, Serrano, Mauricio J., Choi, Jong-Deok, Sreedhar, Vugranam C., Midkiff, Samuel Pratt
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Das, Chameli C.
• Application Number:
  US09/354,140
• Time in Patent Office: 1,019 Days
• Field of Search: 717/5, 717/8, 717/9, 717/7, 717/4, 717/151, 717/136, 717/162, 717/124, 707/206, 711/170, 709/196
• US Class Current: 717/140
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

Information is computed about the reachability relationships among objects and pointers to enable transformation of a computer program for optimizing the creation and destruction of objects, while strictly performing the semantics of the original program. An interprocedural analysis is used to determine whether an object that is allocated on the heap during the execution of a procedure is not reachable from any global variable, parameter, or the return value of the procedure after it returns. If so, that object can be allocated on the stack frame of the procedure in which it is otherwise heap-allocated. This simplifies the memory allocation and deallocation operations, as allocation on the stack can be done more efficiently than allocation on the heap, and objects allocated on the stack frame of a procedure are automatically deallocated when the procedure returns, without incurring the overhead of garbage collection. This, in turn, leads to faster programs which use fewer computer processor resources to execute. The interprocedural analysis of the program summarizes the effect of a procedure call succinctly for different calling contexts of the procedure using a single summary representation. The method handles exceptions in the programming language, while taking advantage of the information about the visibility of variables in the exception handler. Variants of the method show how one or several of the features of the method may be performed.

Claims

1. A method to analyze and transform a computer program so that the information can be used to reduce the overhead of allocation and deallocation of objects in the program, said method comprising the step of identifying those objects allocated on a heap that can instead be allocated on a stack frame of a procedure, without changing the semantics of a computer program by performing an interprocedural analysis of said computer program, wherein said identifying step further comprises the steps of:

identifying for each procedure analyzed, reachability relationships among different objects, fields of objects, and pointers referenced in each said procedure; and

identifying an object as stack-allocatable for each object allocated in a procedure, if at the end of said procedure, it is not reachable from any global variable, parameter of said procedure, or return value of said procedure.

2. A method as recited in claim 1, further comprising the steps of:

using stack allocation for a stack-allocatable object in place of heap allocation in later passes of a compiler; and

reclaiming automatically storage for said identified objects when said procedure, on whose stack frame said identified objects were allocated, returns.

3. A method as recited in claim 1, wherein said interprocedural analysis further comprises the steps of:

performing a bottom-up traversal over a call graph of said computer program; and

computing summary reachability information for a callee procedure, updating said reachability information for actual parameters, return value and variables reachable from those parameters and return values at a call site within said caller procedure.

4. A method as recited in claim 3, wherein the step of performing a bottom-up traversal over a call graph with cycles is done iteratively until a fixed point solution is obtained.

5. A method as recited in claim 3, wherein an upper limit on iterations is imposed on the step of performing a bottom-up traversal over a call graph with cycles, allowing said interprocedural analysis to complete prior to obtaining a fixed point solution.

6. A method as recited in claim 3, wherein the step of computing summary reachability relationships among variables correctly handles exceptions in said computer program by selectively modifying information about previous reachability relationships among program variables.

7. A method as recited in claim 3, wherein the step of computing summary reachability relationships among variables interprocedurally for said computer program summarizes effects of a procedure invocation for different calling contexts using a single summary representation.

8. A method as recited in claim 1, wherein said interprocedural analysis skips the analysis of at least one procedure.

9. A method as recited in claim 8, wherein type information about program variables is used to improve the quality of information about reachability relationships among objects visible to said at least one procedure that is not analyzed.

10. A method as recited in claim 1, wherein said computer program is written in an imperative language that allows destructive updates of variables.

11. A method as recited in claim 1, wherein said computer program is written in a language with constructs that support multithreading.

12. A machine readable medium containing code to analyze and transform a computer program so that the information can be used to reduce the overhead of allocation and deallocation of objects in the program, the code implementing the step of identifying those objects allocated on a heap that can instead be allocated on a stack frame of a procedure, without changing the semantics of a computer program by performing an interprocedural analysis of said computer program, wherein said identifying step further comprises the steps of:

identifying for each procedure analyzed, reachability relationships among different objects, fields of objects, and pointers referenced in each said procedure; and

identifying an object as stack-allocatable for each object allocated in a procedure, if at the end of said procedure, it is not reachable from any global variable, parameter of said procedure, or return value of said procedure.

13. A machine readable medium containing code to analyze and transform a computer program, as recited in claim 12, the code further implementing the steps of:

using stack allocation for a stack-allocatable object in place of heap allocation in later passes of a compiler; and

reclaiming automatically storage for said identified objects when said procedure, on whose stack frame said identified objects were allocated, returns.