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

VBDis wrote:
> 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.


You have just accurately described the "mark" phase of a mark-and-sweep
collector :-)


In a nutshell, the mark phase is like this:
1. Start with a set of "root" objects. (Usually, these will be all
objects referenced from memory registers, from local variables on the
stack, and a "global" object that keeps references to all global data
that's permanently available). Put these objects on a "todo" list.
2. While the "todo" list is not empty:
        2a. Mark the first object as "alive" and remove it from the list.
        2b. Put all referenced-to objects on the "todo" list,
                unless they are already marked "alive" or already on the
                "todo" list.


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


Traditionally, compilers provide enough information to the garbage
collector to identify pointers on the stack. Additionally, they
provide the same information for memory blocks on the heap.


Collectors like Boehm-Demers-Weiser don't get that information and work
with heuristics: if some bit pattern looks like it could be a pointer,
the block that may be referenced by that object is considered alive.
This works well if the virtual address space is larger than the actual
heap size in use, since the probability of misinterpreting an arbitrary
integer as a pointer is low.
If you know that the program doesn't use pointers "into" a memory block,
the collector can identify pointers even more precisely.
The docs claim that a typical program will overlook less than 1% of dead
blocks in the latter case.


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


It's not an arbitrary location, it's the slots for intermediate
results. These are usually found between the local variables of the
current routine and top-of-stack.


Regards,
Jo

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