Jeff~
On Tue, 30 Nov 2004 10:15:00 -0800, Jeff Clites <[EMAIL PROTECTED]> wrote: > > > > 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. We can handle this fairly easily by having the promotion swap in a new invoke vtable for the return continuation. The new invoke vtable will put into place a copy of its context (rather than the context itself). Thus promoted return continuations can be invoked repeatedly (at the cost of a memory copy), and non-promoted ones can be invoked once and then immediately added to the continuation free list (possibly by their invoke function). Matt -- "Computer Science is merely the post-Turing Decline of Formal Systems Theory." -???
