Reference escape analysis

Abstract

In reference counting schemes for automatically reclaiming storage, each time a reference to an object is created or destroyed, the reference count of the object needs to be updated. This may involve expensive inter-processor message exchanges in distributed environments. This overhead can be reduced by analyzing the lifetimes of references to avoid unnecessary updatings. This paper describes a technique for reducing the runtime reference counting overhead through compile-time optimization. We present a compile-time analysis called re~erence escape analysis for higher-order functional languages that determines whether the lifetime of a reference ezceeds the lifetime of the environment in which the reference was created. Using this statically inferred information, a method for optimizing reference counting schemes is described. Our method can be applied to reference counting schemes in both uniprocessor and multiprocessor environments. The major overhead that is incurred in reference counting schemes are as follows: Space overhead for maintaining a reference count in each object. Time and code overhead for updating reference counts when references are created or destroyed. Communication overhead for manipulating a remote reference and for synchronizing the operations on reference counts in distributed memory environments. In this paper, we describe a method for reducing the time, code, and communication overhead of reference counting in both uniprocessor and multiprocessor environments by compile-time program analysis. Our approach is based on the observation that such overheads can be reduced by avoiding unnecessary reference count updates using statically inferred information about the