The effectiveness of garbage collectors and leak detectors in identifying dead objects depends on the “accuracy” of their
reachability traversal. Accuracy has two orthogonal dimensions: (i) whether the reachability traversal can distinguish between
pointers and non-pointers (type accuracy), and (ii) whether the reachability traversal can identify memory locations that
will be dereferenced in the future (liveness accuracy). While prior work has investigated the importance of type accuracy,
there has been little work investigating the importance of liveness accuracy for garbage collection or leak detection. This
paper presents an experimental study of the importance of liveness on the accuracy of the reachability traversal. We show
that while liveness can significantly improve the effectiveness of a garbage collector or leak detector, the simpler liveness
schemes are largely ineffective. One must analyze globals using an interprocedural analysis to get significant benefit.0
This work was supported by NSF ITR grant CCR-0085792. Any opinions, findings and conclusions or recommendations expressed
in this material are the authors’ and do not necessarily reflect those of the sponsors.