Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-07-16
2002-04-30
Chaki, Kakali (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000, C717S152000, C717S152000, C717S152000, C717S136000, C717S162000, C717S124000, C717S140000, C706S032000, C709S241000
Reexamination Certificate
active
06381738
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to computer programming and, more particularly, to a method and variant of the method for a compiler (either static or dynamic), programming development environment or tool, or programmer to enable transformation of a program or part of a program so as to reduce the overhead of allocating and deallocating objects, while strictly preserving the exact semantics of the program or parts of the program that existed before the transformation.
2. Background Description
Programming languages, for example, the Java™, C and C++ programming languages support heap allocation for data that is dynamically created at arbitrary points during program execution (see D. Gay and Aiken, “Memory Management with Explicit Regions,
Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation
, Montreal, Canada, June 1998). Variables representing data allocated in a program shall be referred to as objects, and variables that point to the objects will be referred to as pointers. In some languages like the C and C++ programming languages, the programmer is also given explicit control over deallocation of objects, using a free statement. However, the programmer has to be careful so as not to deallocate objects to which there is a pointer from any other variable referenced after the deallocation point. Otherwise the dangling pointer to an object that has already been deallocated can lead to an error during program execution. In order to free the programmers from the burden of determining when it is safe to deallocate objects, some languages like Java™ support garbage collection, where the run-time system assumes responsibility for determining when the storage for an object can safely be reclaimed. (Java is a trademark of Sun Microsystems, Inc.)
Every algorithm for garbage collection leads to some overhead being incurred at run-time while identifying the objects whose storage can be reclaimed. A compiler can bypass garbage collection of objects with known lifetimes. In particular, if the lifetime of an object is bounded by the lifetime of the stack frame associated with a procedure, the object can be allocated on the stack rather than the heap. The storage associated with the stack is automatically reclaimed when the procedure returns.
There are two different ways of allocating storage on the stack—dynamic allocation or static allocation. Dynamic stack allocation can be done by dynamically extending the size of the stack during execution. A well-known mechanism for such dynamic extension of the stack is via a system call named alloca on UNIX®-based systems. Static allocation of an object on the stack involves using a fixed location within the stack frame for that object. In order to use static allocation for an object determined to be stack-allocatable, the compiler has to further know the size of the object and check for one of the following two conditions: (i) either the original heap allocation does not take place inside a loop in the given procedure, or (ii) instances of the object allocated in different loop iterations should have non-overlapping lifetimes. (UNIX is a registered trademark of SCO.)
An alternate approach to stack allocation is to use a region in the heap for allocating objects whose lifetimes are bounded by the lifetime of the stack frame, and deallocating the entire region when the corresponding procedure returns. For simplicity of presentation, due to the conceptual similarity of these approaches, such a region-based approach shall be regarded as equivalent to performing stack allocation of data.
Many compilers use a representation called a call graph to analyze an entire program. A call graph has nodes representing procedures, and edges representing procedure calls. The term procedure is used to refer to subroutines, functions, and also methods in object-oriented languages. A direct procedure call, where the callee (called procedure) is known at the call site, is represented by a single edge in the call graph from the caller to the callee. A procedure call, where the callee is not known, such as a virtual method call in an object-oriented language or an indirect call through a pointer, is represented by edges from the caller to each possible callee. It is also possible that given a particular (callee) procedure, all callers of it may not be known. In that case, the call graph would conservatively put edges from all possible callers to that callee.
Within a procedure, many compilers use a representation called the control flow graph (CFG). Each node in a CFG represents a basic block and the edges represent the flow of control among the basic blocks. A basic block is a straight-line sequence of code that has a single entry (at the beginning) and a single exit (at the end). A statement with a procedure call does not disrupt a straight-line sequence of code. In the context of languages that support exceptions, such as the Java™ programming language, the definition of a basic block is relaxed to include statements which may throw an exception. In those cases, there is an implicit possible control flow from a statement throwing an exception to the block of code handling the exception. The basic block is not forced to end at each such statement, and instead, such a basic block bb is referred to as having a flag bb.outEdgeInMiddle set to true.
A topological sort order enumeration of nodes in a graph refers to an enumeration in which, if the graph contains an edge from node x to node y, then x appears before y. If a graph has cycles, then such an enumeration is not guaranteed for nodes involved in a cycle. A reverse topological sort order lists nodes in the reverse order of a topological sort.
Prior art for a similar goal of reducing the overhead of heap allocation and deallocation can be found in the following papers: A. Aiken, M. Fahndrich, and R. Levien, “Better Static Memory Management: Improving Region-Based Analysis of Higher-Order Languages”,
Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation
, San Diego, Calif., June 1995; L. Birkedal, M. Tofte, and M. Vejlstrup, “From Region Inference to von Neumann Machines via Region Representation Inference”,
Proceedings of
23
rd ACM Symposium on Principles of Programming Languages
, St. Petersburg, Fla., January 1996; B. Blanchet, “Escape Analysis: Correctness, Proof, Implementation and Experimental Results”,
Proceedings of
25
th ACM Symposium on Principles of Programming Languages
, January 1998; A. Deutsch, “On the Complexity of Escape Analysis”,
Proceedings of
24
th ACM Symposium on Principles of Programming Languages
, San Diego, January 1997; D. Gay and A. Aiken, “Memory Management with Explicit Regions”,
Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation
, Montreal, Canada, June 1998; J. Hannan, “A Type-Based Analysis for Stack Allocation in Functional Languages”,
Proceedings of
2
nd International Static Analysis Symposium
, September 1995; Y. G. Park and B. Goldberg, “Escape Analysis on Lists”,
Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation
, July 1992; and C. Ruggieri and T. P. Murtagh, “Lifetime Analysis of Dynamically Allocated Objects”
Proceedings of
15
th ACM Symposium on Principles of Programming Languages
, January 1988. Those methods do not handle programs with explicit constructs for multithreading and exceptions (e.g., the try-catch constructs in the Java™ programming language).
Prior art for replacing dynamic heap allocation of objects by stack allocation can be found in the paper by C. Ruggierie and T. P. Murtagh, supra. The analysis presented by C. Ruggierie and T. P. Murtagh is quite conservative. In particular, this method makes pessimistic assumptions about aliasing between different function parameters and variables accessed through the parameters.
Prior art for replacing dynamic heap allocation of objects by stack allocation for functional languages is pres
Choi Jong-Deok
Gupta Manish
Midkiff Samuel Pratt
Serrano Mauricio J.
Sreedhar Vugranam C.
Cameron Esq. Douglas W.
Chaki Kakali
Das Chameli C.
International Business Machines - Corporation
McGuireWoods LLP
LandOfFree
Method for optimizing creation and destruction of objects in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for optimizing creation and destruction of objects in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for optimizing creation and destruction of objects in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2930054