Book contents
- Frontmatter
- Contents
- Preface
- Part I Fundamentals of Compilation
- Part II Advanced Topics
- 13 Garbage Collection
- 14 Object-Oriented Languages
- 15 Functional Programming Languages
- 16 Polymorphic Types
- 17 Dataflow Analysis
- 18 Loop Optimizations
- 19 Static Single-Assignment Form
- 20 Pipelining and Scheduling
- 21 The Memory Hierarchy
- Appendix: MiniJava Language Reference Manual
- Bibliography
- Index
13 - Garbage Collection
from Part II - Advanced Topics
Published online by Cambridge University Press: 05 June 2012
- Frontmatter
- Contents
- Preface
- Part I Fundamentals of Compilation
- Part II Advanced Topics
- 13 Garbage Collection
- 14 Object-Oriented Languages
- 15 Functional Programming Languages
- 16 Polymorphic Types
- 17 Dataflow Analysis
- 18 Loop Optimizations
- 19 Static Single-Assignment Form
- 20 Pipelining and Scheduling
- 21 The Memory Hierarchy
- Appendix: MiniJava Language Reference Manual
- Bibliography
- Index
Summary
gar-bage: unwanted or useless material
Webster's DictionaryHeap-allocated records that are not reachable by any chain of pointers from program variables are garbage. The memory occupied by garbage should be reclaimed for use in allocating new records. This process is called garbage collection, and is performed not by the compiler but by the runtime system (the support programs linked with the compiled code).
Ideally, we would say that any record that is not dynamically live (will not be used in the future of the computation) is garbage. But, as Section 10.1 explains, it is not always possible to know whether a variable is live. So we will use a conservative approximation: We will require the compiler to guarantee that any live record is reachable; we will ask the compiler to minimize the number of reachable records that are not live; and we will preserve all reachable records, even if some of them might not be live.
Figure 13.1 shows a Java program ready to undergo garbage collection (at the point marked garbage-collect here). There are only three program variables in scope: p, q, and r.
MARK-AND-SWEEP COLLECTION
Program variables and heap-allocated records form a directed graph. The variables are roots of this graph. A node n is reachable if there is a path of directed edges r → … → n starting at some root r. A graph-search algorithm such as depth-first search (Algorithm 13.2) can mark all the reachable nodes.
- Type
- Chapter
- Information
- Modern Compiler Implementation in Java , pp. 257 - 282Publisher: Cambridge University PressPrint publication year: 2002