If you're willing to jump through some hoops, you don't have to spill. You can r...

If you're willing to jump through some hoops, you don't have to spill. You can recover the pointers on the stack by making all function calls return a flag indicating whether it's a normal return or a stack scan for GC. If a function returns the stack scan flag, you register the local variables in the current stack frame to the GC, and then you return the stack scan flag from that function. This way it unrolls the entire stack and you scan everything.

Of course you've now destroyed the stack, so either you have to copy the stack before this process starts and later restore it, or you introduce stack restoring functions as a source to source transformation. The former is probably simpler and faster, but the latter is neat because it doesn't use any hacks like copying the stack, and because it allows you to restore only part of the stack and keep part of it in the heap and restore it lazily, which is important for GC pause times if you have very deep stacks.

The disadvantage of this approach compared to the ideal is that now all function returns get slower, because they have to check the flag. However it's probably better than spilling everything, especially if you inline enough so that function calls are infrequent.

Example:

    def f(...):
       var x;
       var y;
       ...
       z = g(...)
       ...

becomes:

    def f(...):
       var x;
       var y;
       ...
       z = g(...)
       if STACKSCAN:
         register_gc_root(x)
         register_gc_root(y)
         return // scan parent stack frame
       ....