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

VBDis wrote:
> Joachim Durchholz <joachim.durchholz@web.de> schreibt:
>>The docs claim that a typical program will overlook less than 1% of dead
>>blocks in the latter case.
>
> Fine, but what about overlooking live references? ;-)


Live references are never overlooked. This is what the "conservative"
bit in the Boehm-Demers-Weiser documentation means: it prefers to err
on the conservative side and misidentify a nonpointer as a pointer
(rather than erring in the reverse direction).


There is one exception: if the application mangled pointers, the
garbage collector will indeed overlook live blocks. (For example,
there's a linear-list implementation where the forth and back pointers
are xor-ed together. Scanning through such a list means taking the
address of the first block, xoring it with its "link" field to get the
address of the next block, and so on - or, alternatively, start with
the last block and go back. However, *any* garbage collector will have
difficulties dealing with such constructions, and these aren't very
much in vogue anymore - you need this kind of trick only if you have
to squeeze serious data into a one-digit number of kilobytes.)


>>>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.
>
> And that's just a location which deserves detailed description. Consider that
> the stack can have any number of layouts (scopes), during execution of a
> subroutine. Every evaluation, which pushes intermediate references onto the
> stack, will deserve an according description of the current stack layout. The
> marker then will have to examine the current address within the subroutine
> code, and use it to fetch the according stack description from a list of all
> those descriptions.


Hmm... right, the intermediate result stack may have a mixture of
pointer and nonpointer data.
I'm not sure how this is handled. I could imagine various techniques,
like having bitmaps for every conceivable instruction pointer value, or
interleaving bitmaps and result values on the stack. Or reserving enough
space on the stack to store the bitmap for the maximum size of the
intermediate values stack (for a single expression, this is the maximum
nesting depth of the call as written in the source code, which is easy
to compute for a compiler). Or one could store pointer data on a
different stack than nonpointer data (with all the complications that a
two-stack scheme entails).


  > Those stack descriptions also will have to include the
> local variables,


For this case, the same techniques as for distinguishing pointers from
nonpointers in a heap block would apply.


  > which may be overlaid for parallel blocks of code.


The compiler could overlay pointers with pointers and nonpointers with
nonpointers, this would eliminate the problem.
If stack space is really at a premium, the compiler could insert
statements to switch stack layout indicators when entering a block that
uses a new layout. However, the machine instructions will most likely
take up more static code space than stack space saved; I could imagine
this in cases where a routine is known to be heavily recursive, or in an
embedded microprocessor with limited RAM and large ROM. On a desktop
CPU, I'd just use a single stack layout for each routine and ignore the
waste of space...


Regards,
Jo

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