Re: Static Garbage Collection

Matthias-Christian Ott <ott@mirix.org> writes:




> Suppose we have a goto-free, pointer-less, static strongly typed
> programming language without any binary libraries (so all source code
> is available at compile time).
>
> Then we could construct the control flow graph for the entire programme.
>
> Couldn't we than statically (of course depending on conditions during
> runtime) determine the locations for the appropriate malloc() and free()
> calls, depending on if a referenced object is no longer used?
>
> The result would be same as if you manually managed you memory, so you
> would have no runtime overhead garbage collection, just for the tests of
> the user input, because we can predict everything that does not depend
> on user input at compile time.


You can approximate this, but not predict exactly when an object is no
longer needed (the halting problem John mentioned). I think the most
ambitious attempt at static analysis for memory deallocation is region
analysis
(http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.5498), but
even this allows some space leaks unless you code carefully.


Another approach is to limit allocation to stack allocation and
disallow objects to be exported out of the scope in which they are
allocated. In the simplest form (as used in Pascal), you can not
return _any_ reference to a stack allocated object, regardless of
where this is allocated. You can, however, make a fairly simple type
inference that allows return of references but (conservatively)
detects cases where an object might be exported out of its scope and
refuse compilation of such programs. This is called "escape
analysis".


This is not as general as region analysis, since region analysis
allows allocation in a non-local scope: It finds (conservatively) the
closest enclosing scope outside of which the object is known to be
dead and allocates the object in this scope. This means that a normal
stack can no longer be used, as this allows only ToS allocation. So a
stack of extensible regions is used instead.


There have also been various other attempts at "compile-time GC",
where part of the deallocation is done outside the GC. Escape
analysis can be used to detect some allocation that can be made on the
stack, but rather than rejecting programs where not all allocations
can be on the stack, the remaining allocations are done in the heap
and GC'ed normally. Linear types have also been used to reduce GC: If
an object can be determined to be used at most once, its space can be
re-used immediately after it is read.


Linear types have also been used to check manual
allocations/deallocations: All heap-allocated objects have a
linearly-typed "handle". This must be used _exactly_ once, so all
operations on the object consume the handle and return a new handle.
Deallocation consumes a handle but does not produce a new one. This
severely limits how you use heap-allocated objects, though, but it has
been used for embedded systems with shared memory
(http://www.cl.cam.ac.uk/~am21/papers/esop04.pdf).


Torben

Return to the comp.compilers page.
Search the comp.compilers archives again.