On Nov 30, 2004, at 5:28 AM, Dan Sugalski wrote:

At 1:45 AM -0800 11/29/04, Jeff Clites wrote:
On Nov 28, 2004, at 2:48 AM, Piers Cawley wrote:

I just thought of a heuristic that might help with register
preservation:

A variable/register should be preserved over a function call if either of the
following is true:


1. The variable is referred to again (lexically) after the function has
returned.
2. The variable is used as the argument of a function call within the
current compilation unit.

That doesn't solve it, though you'd think it would. Here's the counter-example:


        x = 1
        foo()
        print x
        y = 2
        return y

You'd think that x and y could use the same memory location (register, variable--whatever), since ostensibly their lifetimes don't overlap. But continuation re-invocation can cause foo() to return multiple times, and each time it should print "1", but it won't if x and y use the same "slot" (it would print "2" each time after the first). In truth, their lifetimes do overlap, due to the hidden (potential) loops created by continuations.

Except... we've already declared that return continuations are special, and preserve the registers in the 16-31 range. So when we return from foo, regardless of how or how many times, the pointer to x's PMC will be in a register if it was in there before the call to foo, if it's in the preserved range. So in this case there's no problem. Things'll look like:


x = 1 # new P16, .Integer; P16 = 1 # P16 has pointer value 0x04
foo() # foo invocation
print x # P16 still has pointer value 0x04
y = 2 # new P16, .Integer; P16 = 2 # P16 now has pointer value 0x08
return y # Passes back 0x08


With more or less clarity.

But the problem isn't preservation per se. When a continuation (originally captured inside of foo) is invoked, the frame will be restored with the register contents it had when it last executed, so P16 in your annotations will have pointer value 0x08 after the "first" time that continuation is invoked (because "y = 2" will have executed and changed the register contents). That will result in "print x" printing the value "2", which is wrong from the perspective of the code (that line should always print "1"). To do-the-right-thing, the register allocator either has to use a separate register to hold y, or needs to do some other preservation dance (instead of relying on preserved registers). And again, I think the reason for this is that the lifetimes of x and y overlap, so you can't just use the same register to store them. The only surprising part of all of this is that their lifetimes in fact overlap--they only overlap due to continuations, and wouldn't otherwise. It's the implicit branch from the "return" to the op-after-the-call-to-foo that's causing them to overlap.


None of this should have anything to do with return continuations specifically, since this is the case where the body of foo (or something called from it) creates a "real" continuation, which as I understand it is supposed to promote the return continuations to "real" continuations all the way up the stack.

JEff



Reply via email to