Re: Compile-time garbage collection (was Re: Compiler writers will love this ...

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.


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. 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.


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.




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.


DoDi

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