Re: continuation enhanced arcs
[EMAIL PROTECTED] wrote: What this means is that care must be taken when you are writing code that you expects to be invoked multiple times. However, if you are a function that on your second invocation returns via the continuation from you first invocation, you should probably expect to be called again because it happened the first time! The contentious point is precisely that there is no way to tell at the compile time that you will be invoked multiple times. If something you pull from a library or a callback passed to you captures the continuation, you may notice that your return continuation had been promoted, but at that point it's already too late to kill all I/N/S register usage and to double-reference all PMCs. Of course, unless you keep the original AST and keep recompiling it to PIR. I'd argue that it's vastly more complex and error prone than Leo's solution he refered to in his post. It's also no better than refetching all lexicals. Also, note that return-continuation-restores semantics is simply a (possibly premature) optimisation in its own right. CPS is supposed to treat every continuation the same (which turned out to be inefficient), and then return continuations were added to simplify the most common case. So, while return continuation is unpromoted, it's perfectly okay for it to behave any way it wants. Once it does get promoted, I'd argue that it should behave like a normal continuation first because it's more practical (see above) and second because that way it doesn't break CPS semantics. Miro
Re: continuation enhanced arcs
Matt Fowles [EMAIL PROTECTED] wrote: ... This author may have to be a little wary about value vs reference semantics, but programmers are fairly used to that pitfall by now. Yes. But this still boils down to the question, if an author or compiler knows that a full continuation is involved and that I,S,N registers aren't usable for a piece of code. Matt leo
Re: continuation enhanced arcs
On Wed, Dec 08, 2004 at 04:04:31PM -0500, Matt Fowles wrote: I would disagree. Let me take the above example and work with it a little: $I0 = 10 loop: $P0 = shift array dec $I0 if $I0 goto loop We are (for the moment) assuming that shift array somehow causes a full continuations to be taken and then invoked it in a subsequent call. Then this code would infinite loop; however, so would this code Is shift a vtable method? IIRC Dan said that we're not going to be able to take continuations that cross PMC vtable invocation. Nicholas Clark
Re: continuation enhanced arcs
Piers Cawley [EMAIL PROTECTED] wrote: Leopold Toetsch [EMAIL PROTECTED] writes: ... While S registers hold pointers, they have value semantics. Is that guaranteed? Because it probably needs to be. It's the current implementation and tested. This would restore the register contents to the first state shown above. That is, not only I and N registers would be clobbered also S registers are involved. That's correct. What's the problem? Okay, you've created an infinite loop, but what you're describing is absolutely the correct behaviour for a continuation. Ok. It's a bit mind-twisting but OTOH it's the same as setjmp/longjmp with all implications on CPU registers. C has the volatile keyword to avoid clobbering of a register due to a longjmp. Above code could only use P registers. Or in other words: I, N, and S registers are almost[1] useless. No they're not. But you should expect them to be reset if you take a (full) continuation back to them. The problem I have is: do we know where registers may be reset? For example: $I0 = 10 loop: $P0 = shift array dec $I0 if $I0 goto loop What happens if the array PMC's Cshift get overloaded and does some fancy stuff with continuations. My gut feeling is that the loop might suddenly turn into an infinite loop, depending on some code behind the scenes ($I0 might be allocated into the preserved register range or not depending on allocation pressure). Second: if we don't have a notion that a continuation may capture and restore a register frame, a compiler can hardly use any I,S,N registers because some library code or external function might just restore these registers. Presumably if foo() doesn't store a full continuation, the restoration just reuses an existing register frame and, if foo has made a full continuation its return does a restore by copying? Yes, that should be a reasonable implementation. leo
Re: continuation enhanced arcs
Leopold Toetsch [EMAIL PROTECTED] writes: Piers Cawley [EMAIL PROTECTED] wrote: Leopold Toetsch [EMAIL PROTECTED] writes: ... While S registers hold pointers, they have value semantics. Is that guaranteed? Because it probably needs to be. It's the current implementation and tested. This would restore the register contents to the first state shown above. That is, not only I and N registers would be clobbered also S registers are involved. That's correct. What's the problem? Okay, you've created an infinite loop, but what you're describing is absolutely the correct behaviour for a continuation. Ok. It's a bit mind-twisting but OTOH it's the same as setjmp/longjmp with all implications on CPU registers. C has the volatile keyword to avoid clobbering of a register due to a longjmp. Above code could only use P registers. Or in other words: I, N, and S registers are almost[1] useless. No they're not. But you should expect them to be reset if you take a (full) continuation back to them. The problem I have is: do we know where registers may be reset? For example: $I0 = 10 loop: $P0 = shift array dec $I0 if $I0 goto loop What happens if the array PMC's Cshift get overloaded and does some fancy stuff with continuations. My gut feeling is that the loop might suddenly turn into an infinite loop, depending on some code behind the scenes ($I0 might be allocated into the preserved register range or not depending on allocation pressure). Second: if we don't have a notion that a continuation may capture and restore a register frame, a compiler can hardly use any I,S,N registers because some library code or external function might just restore these registers. This is, of course, why so many languages that have full continuations use reference types throughout, even for numbers. And immutable strings...
Re: continuation enhanced arcs
Piers Cawley [EMAIL PROTECTED] wrote: Leopold Toetsch [EMAIL PROTECTED] writes: The problem I have is: do we know where registers may be reset? For example: $I0 = 10 loop: $P0 = shift array dec $I0 if $I0 goto loop What happens if the array PMC's Cshift get overloaded and does some fancy stuff with continuations. My gut feeling is that the loop might suddenly turn into an infinite loop, depending on some code behind the scenes ($I0 might be allocated into the preserved register range or not depending on allocation pressure). Second: if we don't have a notion that a continuation may capture and restore a register frame, a compiler can hardly use any I,S,N registers because some library code or external function might just restore these registers. This is, of course, why so many languages that have full continuations use reference types throughout, even for numbers. And immutable strings... So my conclusion that (in combination with restoring registers to the values of continuation creation) I,S,N registers are almost unusable is correct? What about my proposal Lexicals, continuations, and register allocation? Would that provide proper semantics for continuations? leo
Re: continuation enhanced arcs
Leo~ On Wed, 8 Dec 2004 20:29:00 +0100, Leopold Toetsch [EMAIL PROTECTED] wrote: So my conclusion that (in combination with restoring registers to the values of continuation creation) I,S,N registers are almost unusable is correct? I would disagree. Let me take the above example and work with it a little: $I0 = 10 loop: $P0 = shift array dec $I0 if $I0 goto loop We are (for the moment) assuming that shift array somehow causes a full continuations to be taken and then invoked it in a subsequent call. Then this code would infinite loop; however, so would this code as the second call is returning through the first calls continuation. $P0 = shift array $P1 = shift array On the other hand, if every call to shift array took a full continuation, did some stuff, and eventually returned through its return continuation. Then neither would infinite loop, as every call to shift array would have its own return continuation. What this means is that care must be taken when you are writing code that you expects to be invoked multiple times. However, if you are a function that on your second invocation returns via the continuation from you first invocation, you should probably expect to be called again because it happened the first time! If you are expecting other behavior, it is probably because one person wrote the whole chain of calls and had some extra knowledge about the caller. This author may have to be a little wary about value vs reference semantics, but programmers are fairly used to that pitfall by now. Matt -- Computer Science is merely the post-Turing Decline of Formal Systems Theory. -???
Re: continuation enhanced arcs
Piers Cawley [EMAIL PROTECTED] wrote: Further to my last response. If you have things set up so that you can return multiple times from the same function invocation then the return continuation should have been replaced with a full continuation before the first return, so even the first return will use copying semantics, and the registers will always be restored to the state they were in when the function was first called, which is absolutely the right thing to do. Here is again the example I've brought recently. Please go through it and tell me what's wrong with my conclusion. $I0 = 42 # set I16, 42 42 $N0 = 2.5# set N16, 2.5..101... $S0 = a# set S16, a0x1004 - a $P0 = a# set P16, a0x2008 - a loop: foo()# set P0, ...; invokecc We have some temporary variables and a function call. Variables are used beyond that point, so the register allocator puts these in the preserved register range. The function Cfoo() might or might not capture the continuation created by the Cinvokecc opcode. Let's assume, it is captured, and stored into a global, if it wasn't already, i.e. the first time. According to Dan's plan, the function return restores the register contents to the state of the creation of the return continuation, which is shown in the right column. $I0 += 1 # add I16, 1 43 $N0 *= 2.0 # mul N16, 2.0.101 $S0 .= b # concat S16, b 0x1008 - ab inc $P0 # inc P16 0x2008 - b dec a# dec P17 0x200c - 1 if a goto loop # if P17, loop A note WRT strings: the concat might or might not assign a new string to S16. It depends on the capacity of the string buffer. But generally: string operations do create new string headers with a different memory address like shown here. While S registers hold pointers, they have value semantics. Now we loop once over the function call. This creates a new return continuation and on function return registers are restored to their new values (44, 10.0, abb, c). All fine till here. The loop counter a reaches zero. Now the next instruction is another function call. bar()# set P0, ... invokecc The bar() function extracts the return continuation captured in the first call to foo() from the global and invokes it. Control flow continues right after the invokecc opcode that called foo(). This would restore the register contents to the first state shown above. That is, not only I and N registers would be clobbered also S registers are involved. Above code could only use P registers. Or in other words: I, N, and S registers are almost[1] useless. leo
Re: continuation enhanced arcs
Leopold Toetsch [EMAIL PROTECTED] writes: Piers Cawley [EMAIL PROTECTED] wrote: Further to my last response. If you have things set up so that you can return multiple times from the same function invocation then the return continuation should have been replaced with a full continuation before the first return, so even the first return will use copying semantics, and the registers will always be restored to the state they were in when the function was first called, which is absolutely the right thing to do. Here is again the example I've brought recently. Please go through it and tell me what's wrong with my conclusion. $I0 = 42 # set I16, 42 42 $N0 = 2.5# set N16, 2.5..101... $S0 = a# set S16, a0x1004 - a $P0 = a# set P16, a0x2008 - a loop: foo()# set P0, ...; invokecc We have some temporary variables and a function call. Variables are used beyond that point, so the register allocator puts these in the preserved register range. The function Cfoo() might or might not capture the continuation created by the Cinvokecc opcode. Let's assume, it is captured, and stored into a global, if it wasn't already, i.e. the first time. According to Dan's plan, the function return restores the register contents to the state of the creation of the return continuation, which is shown in the right column. $I0 += 1 # add I16, 1 43 $N0 *= 2.0 # mul N16, 2.0.101 $S0 .= b # concat S16, b 0x1008 - ab inc $P0 # inc P16 0x2008 - b dec a# dec P17 0x200c - 1 if a goto loop # if P17, loop A note WRT strings: the concat might or might not assign a new string to S16. It depends on the capacity of the string buffer. But generally: string operations do create new string headers with a different memory address like shown here. While S registers hold pointers, they have value semantics. Is that guaranteed? Because it probably needs to be. Now we loop once over the function call. This creates a new return continuation and on function return registers are restored to their new values (44, 10.0, abb, c). All fine till here. The loop counter a reaches zero. Now the next instruction is another function call. bar()# set P0, ... invokecc The bar() function extracts the return continuation captured in the first call to foo() from the global and invokes it. Control flow continues right after the invokecc opcode that called foo(). This would restore the register contents to the first state shown above. That is, not only I and N registers would be clobbered also S registers are involved. That's correct. What's the problem? Okay, you've created an infinite loop, but what you're describing is absolutely the correct behaviour for a continuation. If you need any state to be 'protected' from taking the continuation then it needs to be in a lexical or a mutated PMC. This is just how continuations are supposed to work. Above code could only use P registers. Or in other words: I, N, and S registers are almost[1] useless. No they're not. But you should expect them to be reset if you take a (full) continuation back to them. Presumably if foo() doesn't store a full continuation, the restoration just reuses an existing register frame and, if foo has made a full continuation its return does a restore by copying?
Re: continuation enhanced arcs
Piers Cawley [EMAIL PROTECTED] wrote: Leopold Toetsch [EMAIL PROTECTED] writes: Matt Fowles [EMAIL PROTECTED] wrote: Thanks for the clear explanation. I did not realize that S registers could switch pointers, that does make things a little harder. I have a recommendation for a possible hybrid solution. Incur the cost of spilling I,S,N registers heavily. Restore the state of P register. My conclusion was that with the copying approach I,S,N registers are unusable. But you only need to copy when the frame you're restoring is a full continuation Yes. With the effect that semantics of I,S,N (i.e. value registers) suddenly changes. I'd submit that, in the vast majority of cases you're not going to be dealing with full continuations, and on the occasions when you are the programmer using them will be aware of the cost and will be willing to pay it. *If* the programmer is aware of the fact that a subroutine can return multiple times, he can annotate the source so that a correct CFG is created that prevents register reusing alltogether. The problem is gone in the first place. *If* that's not true, you'd get the effect that suddenly I,S,N registers restore to some older values which makes this registers de facto unusable. leo
Re: continuation enhanced arcs
Leopold Toetsch [EMAIL PROTECTED] writes: Piers Cawley [EMAIL PROTECTED] wrote: Leopold Toetsch [EMAIL PROTECTED] writes: Matt Fowles [EMAIL PROTECTED] wrote: Thanks for the clear explanation. I did not realize that S registers could switch pointers, that does make things a little harder. I have a recommendation for a possible hybrid solution. Incur the cost of spilling I,S,N registers heavily. Restore the state of P register. My conclusion was that with the copying approach I,S,N registers are unusable. But you only need to copy when the frame you're restoring is a full continuation Yes. With the effect that semantics of I,S,N (i.e. value registers) suddenly changes. I'd submit that, in the vast majority of cases you're not going to be dealing with full continuations, and on the occasions when you are the programmer using them will be aware of the cost and will be willing to pay it. *If* the programmer is aware of the fact that a subroutine can return multiple times, he can annotate the source so that a correct CFG is created that prevents register reusing alltogether. The problem is gone in the first place. *If* that's not true, you'd get the effect that suddenly I,S,N registers restore to some older values which makes this registers de facto unusable. But they're bloody value registers. They're *supposed* to restore to the state they were in when the function was originally called. Which is what copying semantics does.
Re: continuation enhanced arcs
Leopold Toetsch [EMAIL PROTECTED] writes: Piers Cawley [EMAIL PROTECTED] wrote: Leopold Toetsch [EMAIL PROTECTED] writes: Matt Fowles [EMAIL PROTECTED] wrote: Thanks for the clear explanation. I did not realize that S registers could switch pointers, that does make things a little harder. I have a recommendation for a possible hybrid solution. Incur the cost of spilling I,S,N registers heavily. Restore the state of P register. My conclusion was that with the copying approach I,S,N registers are unusable. But you only need to copy when the frame you're restoring is a full continuation Yes. With the effect that semantics of I,S,N (i.e. value registers) suddenly changes. I'd submit that, in the vast majority of cases you're not going to be dealing with full continuations, and on the occasions when you are the programmer using them will be aware of the cost and will be willing to pay it. *If* the programmer is aware of the fact that a subroutine can return multiple times, he can annotate the source so that a correct CFG is created that prevents register reusing alltogether. The problem is gone in the first place. *If* that's not true, you'd get the effect that suddenly I,S,N registers restore to some older values which makes this registers de facto unusable. Further to my last response. If you have things set up so that you can return multiple times from the same function invocation then the return continuation should have been replaced with a full continuation before the first return, so even the first return will use copying semantics, and the registers will always be restored to the state they were in when the function was first called, which is absolutely the right thing to do.
Re: continuation enhanced arcs
Leopold Toetsch [EMAIL PROTECTED] writes: Matt Fowles [EMAIL PROTECTED] wrote: Thanks for the clear explanation. I did not realize that S registers could switch pointers, that does make things a little harder. I have a recommendation for a possible hybrid solution. Incur the cost of spilling I,S,N registers heavily. Restore the state of P register. My conclusion was that with the copying approach I,S,N registers are unusable. But you only need to copy when the frame you're restoring is a full continuation (and, actually, if copy on write works at a per register level, copy on write might be the way to go). If it's a return continuation you can simply use the stored state. I'd submit that, in the vast majority of cases you're not going to be dealing with full continuations, and on the occasions when you are the programmer using them will be aware of the cost and will be willing to pay it.
Re: continuation enhanced arcs
Luke Palmer [EMAIL PROTECTED] writes: Piers Cawley writes: I'd submit that, in the vast majority of cases you're not going to be dealing with full continuations, and on the occasions when you are the programmer using them will be aware of the cost and will be willing to pay it. Yeah probably. Except the problem isn't the cost. The problem is the semantics. If you copy the registers, then when you invoke the continuation, their *values* restore to what they were when you made the continuation. These are not proper semantics, and would result in subtle, incorrect infinite loops. PMCs don't relocate, so the values you're restoring are simply the addresses of said PMCs. The Numeric registers are value registers anyway so no problem there (since there's no way of making a pointer to the contents of such a register AFAICT). I'm not sure about string registers. And anyway, copying is how it used to work, and work it did, albeit slowly.
Re: continuation enhanced arcs
Piers Cawley writes: I'd submit that, in the vast majority of cases you're not going to be dealing with full continuations, and on the occasions when you are the programmer using them will be aware of the cost and will be willing to pay it. Yeah probably. Except the problem isn't the cost. The problem is the semantics. If you copy the registers, then when you invoke the continuation, their *values* restore to what they were when you made the continuation. These are not proper semantics, and would result in subtle, incorrect infinite loops. Luke
Re: continuation enhanced arcs
Matt Fowles [EMAIL PROTECTED] wrote: Thanks for the clear explanation. I did not realize that S registers could switch pointers, that does make things a little harder. I have a recommendation for a possible hybrid solution. Incur the cost of spilling I,S,N registers heavily. Restore the state of P register. My conclusion was that with the copying approach I,S,N registers are unusable. I suggest this because it seems likely that P registers will have much greater pressure on them then the others. Who knows that (now)? Here is the register usage line Dan has posted some time ago: | registers needed:I3597, N0, S962, P6207 (these are of course virtual registers but 271 registers got spilled) It'll be ultimate fun to map registers to 16 preserved P over a call, BTW. Matt leo
Re: continuation enhanced arcs
Bill Coffman writes: I can see that there is true magic in the power of using references in this way. Nonetheless, how can the compiler figure out that it can't use an integer here? The compiler should use integers when it can, but it sounds like you are saying that when a variable crosses a sub call (which might invoke a continuation) it will then have to be a PMC or String to do the right thing. Yep. And that's something that the compiler will just have to know (or give IMCC enough information to do something about it). And, IIRC, an S register wouldn't work either, since strings are value types at the bytecode level. Luke Remember the PMC and string registers hold pointers to pmc/string structures, which is all we're preserving -- the *pointer* to the structure, not the contents of the structure. (Though that's an interesting thing to do for other reasons, like, say, transactions, we're not going to be doing that) The contents can change over and over without the register itself ever changing. # these two lines are main outer() $saved.call Bill JEff -- Dan
Re: continuation enhanced arcs
All, As with most technical problems, fully specifying them, is often half the battle. In this case, I think we're getting close to understanding the issues at least. [please treat all statements as possible questions] First, consider my original post in this thread: http://www.nntp.perl.org/group/perl.perl6.internals/27383 To summarize: Full continuations are powerful but expensive. They are like hidden goto's and add arcs to the control flow graph. This causes more registers to interfere. Proposed Solutions: - Accept the arcs and probable spilling. We still have the regions between sub calls. - Put labels on certain subs that denote they might call or be called by a continuation. - Pragmas indicating ranges where continuations won't be called (or will be). - Restore registers from lexicals somewhere, after each function call. - Accept incorrectness, as the current implementation does (discovered when new allocator failed 2 tests, and Leo saw the problem). Next, consider Dan's message, Lexicals, continuations, and register allocation: On Tue, 30 Nov 2004 10:22:29 -0500, Dan Sugalski [EMAIL PROTECTED] wrote: So far as I can tell there are two cases here: 1) A return continuation 2) A regular continuation [snip return contuations, which are far from solved, but likely a subset of the below] The second case, where code takes an arbitrary continuation that returns to location X, wherever X is. I'm missing the problem there, too. Assuming there's a way to note the destination to the register allocator (with those points being places where all registers must be assumed to be trash) I'm not seeing the problem either. There are only two cases here, where the destination is marked and where it isn't. If it's marked, the register allocator assumes things are dirty and loads everything, which is fine. If it's unmarked, the code has essentially shot itself and everything quietly goes to hell since you've lied to the register allocator and you shouldn't do that. Which is fine too. Don't Do That. If I read the above correctly, Dan is advocating the strongest restriction of all, which is to specify any arcs that might be added. That is, specify all sub_i - sub_j, where - means that a continuation saved in sub_j is invoked by sub_i. To reclassify the reasonable solutions: 1a. Concentrate on restoring registers after calling -- probably using the lexicals. 1b. Possibly increase the size of the register set, and/or try to use lexicals or globals (I think of this as a kind of improved spilling).. 2a. Insert all the arcs into the CFG, which will increase spilling, but 2b. Reduce the number of arcs in the CFG, by introducing various annotations on subs indicating when they do or do not save or invoke a continuation. Especially target library functions. Currently, I'm trying to work on 2a right now, but my day job is making that tough lately. Would like to see more attention payed to 2b, by those who care about the issue. In particular I'd like to see HLL designers say, Yeah, 2b looks like a great idea!, and maybe a few, yeah, let's specifically implement the following... Then, there are additional problems to contend with... On Wed, 1 Dec 2004 09:49:34 -0800, Jeff Clites [EMAIL PROTECTED] wrote: But so it sounds like I and N registers are a bit of a waste then, no? They won't really be used. Even in your my int @foo case, you could have an optimized backing store for the array, but you'd have to on-the-fly create a PMC to hold any values you pulled out of the array, e.g. for a subsequent x = @foo[1] (in Perl6 syntax)--x would have to hold a full PMC there, it seems, so nothing there would end up in an I register (except as in intermediate in immediately creating the PMC). [snippage of examples] If I understand right, PerlArray's would be used for my int @foo. If you want to use these values, you have to copy back and forth from I* registers, for the most part. The ISN registers can be used in the nether regions, between sub calls (even the lower half of the registers can be used there). Subs which are garanteed not to call or save continuations are safe (see 2b above), and ISN registers can be used while crossing those. However, we now know that only P registers can cross unsafe subs, unless ... well, there's probably certain cases where ISN's can be used. That question would take more thought. My sense is that we want to support continuations, but we don't want to be crushed under the heavy load. Perhaps we can adapt the policy that if one is brazen enough to use full continuations, then s/he should be expected to at least inform the compiler about it. Bill
Re: continuation enhanced arcs
On Tue, 30 Nov 2004 14:45:39 -0500, Dan Sugalski [EMAIL PROTECTED] wrote:
At 11:20 AM -0800 11/30/04, Jeff Clites wrote:
% cat continuation6.ruby
def strange
callcc {|continuation| $saved = continuation}
end
def outer
a = 0
strange()
a = a + 1
print a = , a, \n
end
Through the joys of reference types, a will continue to increase
forevermore, assuming the compiler hasn't incorrectly put a in an int
register. (Which'd be wrong)
I can see that there is true magic in the power of using references in
this way. Nonetheless, how can the compiler figure out that it can't
use an integer here? The compiler should use integers when it can,
but it sounds like you are saying that when a variable crosses a sub
call (which might invoke a continuation) it will then have to be a PMC
or String to do the right thing.
Remember the PMC and string registers
hold pointers to pmc/string structures, which is all we're preserving
-- the *pointer* to the structure, not the contents of the structure.
(Though that's an interesting thing to do for other reasons, like,
say, transactions, we're not going to be doing that) The contents can
change over and over without the register itself ever changing.
# these two lines are main
outer()
$saved.call
Bill
JEff
--
Dan
Re: continuation enhanced arcs
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. The problem isn't preservation across calls per se, it's the implicit loops. Continuations are basically gumming up tons of potential optimizations. JEff
Re: continuation enhanced arcs
Leopold Toetsch [EMAIL PROTECTED] writes: Piers Cawley [EMAIL PROTECTED] wrote: Leopold Toetsch [EMAIL PROTECTED] writes: We don't have a problem WRT register preservation, the problem arises due to register re-using. Ah! [a light goes on over Piers's head]. Or am I missing something fundamental? I don't know ;) I was. Hmm... bugger. So, unless we make the register allocator solve the halting problem, the rule becomes If you're playing silly beggars with continuations and you're expecting to get at something in a 'surprising' way, stuff it in a lexical or we guarantee that you will be anally violated by an enraged waterbuffalo that's just sick to death of non-determinism? This would make quite a fine explanation in the docs, except that's a bit unclear about stuff *it*. The waterbuffalo is concerned of preserved *temporary* variables too. 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. Condition 2 is something of a bugger if you have big compilation units, but register allocation is always going to be a pain when there are big compilation units around.
Re: continuation enhanced arcs
Piers Cawley [EMAIL PROTECTED] wrote: Leopold Toetsch [EMAIL PROTECTED] writes: We don't have a problem WRT register preservation, the problem arises due to register re-using. Ah! [a light goes on over Piers's head]. Or am I missing something fundamental? I don't know ;) I was. Hmm... bugger. So, unless we make the register allocator solve the halting problem, the rule becomes If you're playing silly beggars with continuations and you're expecting to get at something in a 'surprising' way, stuff it in a lexical or we guarantee that you will be anally violated by an enraged waterbuffalo that's just sick to death of non-determinism? This would make quite a fine explanation in the docs, except that's a bit unclear about stuff *it*. The waterbuffalo is concerned of preserved *temporary* variables too. leo
Re: continuation enhanced arcs
Leopold Toetsch [EMAIL PROTECTED] writes: Piers Cawley [EMAIL PROTECTED] wrote: Okay, I'm confused, I thought that the whole point of a caller saves, continuation passing regime was that the caller only saves what it's interested in using after the function returns. We don't have a problem WRT register preservation, the problem arises due to register re-using. ... Exactly *where* that return happens, and whether it happens more than once, is completely irrelevant from the point of view of the caller. The return can only happen, where the normal function call would have returned, but anyway. ... ISTM that the register allocator should work on the principle that anything it didn't save before it made the call will be toast afterwards. Yes. But - please remember your example Fun with nondeterministic searches. Here's the relevant piece of code from main: arr1=[1,3,5] arr2=[1,5,9] x = choose(arr1) y = choose(arr2) $P0 = find_lex fail $P0() You know, both choose calls capture the continuation and backtrack via fail (basically). But the register allocator isn't aware of that. The control flow graph (CFG) is linear top down, with new basic blocks starting after each function call. arr2 is obviously used around a call and allocated in the preserved (non-volatile) register area. This works fine. Now the register allocator assigns a register to $P0. It finds the register that arr2 had usable, because in a linear CFG, there's no way that arr2 might be used again. So that register is considered being available. Now if $P0 happens to get the register that arr2 had, backtracking through the call to fail() obviously fails, as arr2 is now the Closure PMC. And that was exactly the case. Ah! [a light goes on over Piers's head]. Or am I missing something fundamental? I don't know ;) I was. Hmm... bugger. So, unless we make the register allocator solve the halting problem, the rule becomes If you're playing silly beggars with continuations and you're expecting to get at something in a 'surprising' way, stuff it in a lexical or we guarantee that you will be anally violated by an enraged waterbuffalo that's just sick to death of non-determinism?
Re: continuation enhanced arcs
Okay, I'm confused, I thought that the whole point of a caller saves, continuation passing regime was that the caller only saves what it's interested in using after the function returns. Exactly *where* that return happens, and whether it happens more than once, is completely irrelevant from the point of view of the caller. ISTM that the register allocator should work on the principle that anything it didn't save before it made the call will be toast afterwards. Doing anything more sophisticated than optimizing register allocation on a sub by sub basis seems like a license for getting completely and utterly plaited. Or am I missing something fundamental?
Re: continuation enhanced arcs
Matt Fowles wrote: It is also possible for functions to jump forward to the return continuation of a function called later on Yes. But I can't see a problem with that. The opcode after an invoke opcode is already the begin of a new basic block. The forward branch would just be an additional edge in the CFG with no additional information. The (for the register allocator invisible) creation of loops is the PITA. Matt leo
continuation enhanced arcs
Hello all, I would like to address the problem of how continuations have affected the register allocator. This problem came to the public eye, when two tests that the new register allocator failed. Leo's analysis was essentially that the allocator was fine, but that our handling of continuations was incomplete, as far control flow and regiester allocation went. First, I think that it is important to acknowledge what is actually agreed upon. Exceptions are handled as a special case of continuations, and as such, this is a subproblem of the general continuations problem. Leo's proposed solution, below seems to have been accepted as workable, correct, and fast enough. Quoth [EMAIL PROTECTED]: 1a) for exceptions: set_eh handler, catch_label This is just a small adaption of the sequence of installing an exception handler. It depends a bit, if exception handlers are inline or nested closures or both. Second, is the larger, *unresolved* problem of continuations in general. Bear with me, as I am just barely beginning to understand continuations myself. Comments on my observations are more than welcome. Especially on my mistakes. Continuations are a kind of goto. When you invoke a continuation, it moves the program counter to where the continuation was taken, and restore most state (but not registers). This scheme has provided a wealth of power, with acceptable performance for a variety of circumstances. One neglected consideration, when implementing this strategy, is the effect on the control flow graph. sub1() ---+ -+ ... || sub2() +-+ | ...| | sub3() ---+-+ In the continuations enhanced control flow graph (the control flow graph (cfg), after one considers the effects of continuations), it is possible for any subroutine to jump back to the exit point of any previous subroutine. Leo has drawn the picture a few times, as above, showing the complex web of links from any sub to any sub. It is the control flow graph which provides the register allocator with the information it nees to determines which variables interfere. They interfere if they could be active at the same time. If they interfere, they must be assigned different registers. Now, consider a slightly different topic: According to recent decisions, the lower half of the registers (0-15) for all types, will not survive a subroutine call. This has created what we can call volatile, and non-volatile symbols (variables). Non-volatile symbols do not cross subroutine calls, and can therefore be put in the lower register half. Volatile symbols cross sub calls, and cannot be put in the lower half. (Think the volatile keyword from C, which means don't mess with this value, well it sort of means that.) Here's the funny thing -- in the new continuations enhanced flowgraph, every volatile symbol in a subroutine will interfere with every other volatile symbol. Here's an informal proof. Remember all those arcs that Leo drew? For instance, if v1 crosses sub1() and v2 crosses sub2(), there is an arc from sub2() back to sub1() [wolog, sub1 is first]. So v1 is live when v2 is live, and the two symbols interfere. All those arcs extend the life range of each symbol to that extent. Therefore, all volatile symbols in the sub will interfere. What this means is that if your subroutine has more than 16 volatile symbols of a given kind, there will be spilling. Here's a list of proposals I have seen to deal with that issue: 1) Let the above stand (I think I was the only one who said that, and that was before I had really thought about it). 2) Let the above stand, but allow for a pragma to turn off the arcs. Thus, I can create a range within the sub, that turns off all those pesky continuation enhanced arcs within that range. HLL compiler writers will be able to set this pragma, knowing that none of it's subs use continuations. (Larry Wall's suggestion.) 3) Specifically a label for each subroutine that *might* set a continuation. Others have said that continuations should not be the common case, if a continuation could be called, then labelling it as RESUMABLE, isn't such a bad idea. (Leo's idea.) 3a) The natural extension of that is to also have label, like INVOKEABLE, for subs that might invoke a continuation. 4) Fetch all from lexicals/globals after a function call. (Another of Leo's.) 4a) Use lexicals instead of registers. (Not sure who mentioned it, but it seems like just spilling everything, using a slightly different spilling scheme.) 4b) Conditionally fetch ... (Ben's suggestion is one that deserves some further thought. Leo doesn't think it could work, and he understands the problem better than I, but his answer is not a difinitive impossible, so that gives some hope.) 5) Let the symbols interfere. The chances are that the program will run correctly anyway. Let the register allocator do it's thing, and every
