Better Static Memory Management: Improving Region-Based Analysis of Higher-Order Languages

Alexander Aiken, Manuel Fahndrich and Raph Levien

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-95-866
April 1995

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/CSD-95-866.pdf

Static memory management replaces runtime garbage collection with compile-time annotations that makeall memory allocation and deallocations explicit in a program. We improve upon the Tofte/Talpin region-based scheme for compile-time memory management. In the Tofte/Talpin approach, all values, including closures, are stored in regions. Region lifetimes coincide with lexical scope, thus forming a runtime stack of regions and eliminating the need for garbage collection. We relax the requirement that region lifetimes be lexical. Rather, regions are allocated late and deallocated as early as possible by explicit memory operations. The placement of allocation and deallocation annotations is determined by solving a system of constraints that expresses all possible annotations. Experiments show that our approach reduces memory requirements significantly, in some cases asymptotically.


BibTeX citation:

@techreport{Aiken:CSD-95-866,
    Author = {Aiken, Alexander and Fahndrich, Manuel and Levien, Raph},
    Title = {Better Static Memory Management: Improving Region-Based Analysis of Higher-Order Languages},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1995},
    Month = {Apr},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/5202.html},
    Number = {UCB/CSD-95-866},
    Abstract = {Static memory management replaces runtime garbage collection with compile-time annotations that makeall memory allocation and deallocations explicit in a program. We improve upon the Tofte/Talpin region-based scheme for compile-time memory management. In the Tofte/Talpin approach, all values, including closures, are stored in regions. Region lifetimes coincide with lexical scope, thus forming a runtime stack of regions and eliminating the need for garbage collection. We relax the requirement that region lifetimes be lexical. Rather, regions are allocated late and deallocated as early as possible by explicit memory operations. The placement of allocation and deallocation annotations is determined by solving a system of constraints that expresses all possible annotations. Experiments show that our approach reduces memory requirements significantly, in some cases asymptotically.}
}

EndNote citation:

%0 Report
%A Aiken, Alexander
%A Fahndrich, Manuel
%A Levien, Raph
%T Better Static Memory Management: Improving Region-Based Analysis of Higher-Order Languages
%I EECS Department, University of California, Berkeley
%D 1995
%@ UCB/CSD-95-866
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1995/5202.html
%F Aiken:CSD-95-866