Efficient Compile-Time Garbage Collection for Arbitrary Data Structures

Markus Mohnen

           This paper describes a \emph{compile-time garbage collection}
           (ctgc) method in the setting of a first-order functional
           language with data structures. The aim is to obtain
           information on positions in a program where certain heap
           cells will become obsolete during execution. Therefore we
           develop an abstract interpretation for the detection of
           {\em inheritance information\/} which allows us to detect
           whether the heap cells of an argument will be propagated to
           the result of a function call. The abstract interpretation
           itself is independent of the evaluation strategy of the
           underlying language.  However, since the actual deallocations
           take place after on termination of functions, the information
           obtained by the abstract interpretation can be only be applied
           in an eager context, which may be detected using strictness
           analysis in a lazy language. In order to increase efficiency
           we show how the number of recomputations can be decreased by
           using only parts of the abstract domains. The worst case time
           complexity is essentially quadratic in the size of the program.
           We illustrate the method developed in this paper with several
           examples and we demonstrate how to use the results in an eager
           implementation.  Correctness of the analysis is considered,
           using a modified denotational semantics as reference point. A
           main goal of our work is to keep both the run-time and the
           compile-time overhead as small as possible.