A principled approach to nondeferred referencecounting garbage collection

Nondeferred reference-counting (RC) garbage collection is among the oldest mem-ory-management methods. Despite offering unique advantages, little attention has been paid on how to correctly implement it for modern programming languages. This paper revisits this collection method and describes how to implement it for a modern object-oriented language in an optimizing compiler. The main contribution is a general algorithm that realizes one form of nondeferred RC collection for an object-oriented language having features such as exceptions, interior pointers, and object pinning. The algorithm abstracts the pertinent characteristics of instructions using concepts from data-flow analysis, such as def/use information, so that instruc-tions are handled in a uniform manner, instead of in an ad hoc or special-case way. The abstracted information is used to systematically compute what increments and decrements to do, even in the presence of subtle conditions such as exceptional con-trol flow. These techniques enabled us to compile a large suite of programs to use nondeferred RC collection. The paper also discusses the modifications that were necessary in the compiler for supporting the inserted RC operations, and reports measurements from a reference implementation