[gclist] Stack scanning & callee-save registers

[Jan-Willem Maessen]

David Chase <chase@naturalbridge.com> writes:
[On identifying callee-save roots in one pass]
> Yes, this is possible.  At the youngest frame, spill the
> registers, and initialize an array of pointers to register spill
> memory to point to that.  As you unwind the stack, update the elements
> of that array to refer to the (callee's) spill locations for the
> spilled registers.  References to "register X" in a given frame
> look up the address into which X was spilled and use that to locate,
> and potentially update, register X.

I think I absorbed this technique as part of the "Garbage Collection
Folklore"---which points to one big flaw in the GC literature from an
implementor's standpoint.  There's a good deal written on how to
chase objects around on the heap, but comparatively little on the
miraculous stage where roots are identified and updated.  This is
possibly the most daunting aspect of GC implementation, actually, as
it is otherwise very easy to implement a simple collector and then
incrementally improve upon it.  I'll bet good money that, eg, most
generational copying collectors start life as two-space collectors
which are debugged and functional before generations are added.

That being said, one can also trace the stack in the opposite
direction.  Starting from the oldest stack frame, keep track of which
callee-saves registers contain pointers.  When a callee spills one such
register, the map is checked and the spill location is collected if
needed. 

It's a bit easier to see how to adapt this technique to polymorphic
languages where parameters may be either pointers or scalars---simply
track parameter registers as well, and discard entries which are no
longer live.

-Jan-Willem Maessen