Re: Compile-time garbage collection (was Re: Compiler writers

VBDis wrote:
>
> Dobes Vandermeer <dobes@dobesland.com> schreibt:
>
> >for each live possible referencor X of Y:
> > if Y is referenced by X, Y is still alive, otherwise Y can be freed.
> >
> >The problem lies in determination of the list of referencors.
>
> Not only in the list of referencors, but more annoying in the list of
> "live" referencors! You'll immediately end up in an infinite loop for
> circular references between X and Y.


I think that at runtime we'd want to avoid recursively making liveness
determinations. After any given use of a reference, that use is
either the last use of that reference (and the reference is dead) or
it is not. If the reference is dead, an implementation could set it
to NULL to indicate it's deadness.


If your list of possible references is a list of expressions
(following pointers from the root) then circular references between X
and Y can be handled because the circular reference becomes
inaccessible at the same instant as Y becomes garbage.


What I worry about, is if your object is possibly "somewhere" in a
given (possibly very large) array - you'd have to scan the entire
array in order to be sure it wasn't. Or even worse, if an object is
"somewhere" in a doubly-linked list, you'd need a way to avoid
searching head->next->prev->next->prev->next etc. which is the same
problem in a different part of the system.


> IMO this representation of the algorithm only describes the viepoint
> of the referenced object Y, whereas the implementation should use an
> different and non-recursive algorithm.


> In practice it must be possible
> to create a complete list of all referencors, regardless of their
> liveness, without recursion.


Consider applying a precise static alias analysis which can produce
"alias" and "may-alias" (alias is short for references the same object")
sets for a given reference. When the last use of a given reference is
reached, the "may-alias" set is the set of possible referencors to
scan. We can look to the alias analysis literature for efficient
implementations with varying degrees of precision, some of which may be
adapted to produce these sets.


> This list will be finite and can be
> constructed by a linear or at least delimited traversal of all
> involved memory areas (static, heap, stack, threads...). Note that in
> a delimited stack no unbounded recursion can occur, every recursive
> invocation of a subroutine adds 1 linear entry to the stack.


If you're talking about a traversal at runtime, then we're getting
further away from being compile-time GC.


Nevertheless, using the compiler to reduce the tracable/freeable set of
objects might be useful by itself in place of generations.


> In the following determination of the liveness state of every object
> recursion must be prevented. IMO it's obvious that it's easier to
> determine whether an object is certainly alive, than whether it's
> certainly dead. Then we can start with a number of certainly alive
> objects (from references in static variables or in the stack), and
> propagate that alive state to all referenced objects. Even if this
> propagation is recursive, an infinite recursion can be prevented when
> the state of an object is updated prior to the propagation into all
> it's referenced objects. Then a recursion can occur only for not yet
> marked objects, whose number is continuously decreasing. Without such
> an immediate state change infinite recursion can occur, when the state
> of the same referencors is evaluated over and over again, in case of
> circular references.


I think you're talking about a standard mark-sweep tracing collector --
or maybe you're making fun?


> There is only one question, which I cannot answer, but probably others
> can do:
>
> How to determine the existence of references in a stack, which are not
> bound to (local) variables?
>
> This can occur e.g. during the evaluation of f(a(), b()), where the
> results of a() and b() can reside in arbitrary locations in the stack,
> before f() is invoked.


As part of compiling, everything becomes identifiable directly .. but if
you want to translate from one source language to another, you could
move them into their own statement and store them in a uniquely-named
temporary variable.


CU
Dobes

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