[gclist] Re: gclist-digest V3 #61

[William D Clinger]

David Chase wrote:
> It's been a while since I read that paper, but given the experience
> of recent years (building a compiler with stack maps and some
> optimization) how the heck did you ever convince yourself that
> you had it all right?

Disclaimer:  My experience has involved dynamically typed languages,
usually Scheme, in which the garbage collector relies on explicit tags
that are attached to most values.  My compilers generally do not use
optimizations that would place untagged values in rootable registers
or stack slots, and the stack maps are used only by exception handlers
and debugging tools.

The compiler can emit a pseudo-op wherever the stack layout changes.
This pseudo-op describes the layout of the registers and/or stack at
that point.  That layout can be derived in some straightforward way
from the compiler's own representation of the register and stack
allocation at that point.  The assembler can convert those pseudo-ops
into the format that is used by the runtime system.  There shouldn't
be too much that can go wrong here.

I'm not convinced that I have it right, but if it's wrong then there
is probably a bug in the compiler's register/stack allocator, and the
stack maps will make that bug more visible.  The stack maps are more
likely to improve the system's reliability than to degrade it.

> Especially, what do you do without safepoints?

I have always used safepoints, but one technique that has been used
by Lisp compilers is to partition the registers and stack slots into
three sets:  those that hold tagged values, those that hold untagged
pointers, and those that hold random bits.  The compiler then maintains
an invariant of the following form:

    Untagged pointers reside only in registers that hold untagged
    pointers.  If register r contains a live untagged pointer, then
    r points into an object whose tagged representation is contained
    in a register that is an element of the set f(r), where f is some
    fixed mapping from registers that hold untagged pointers to registers
    and stack slots that hold tagged values.

The disadvantages of this approach should be obvious, but it supports
precise moving gc without safepoints or stack maps.

Will