On Dec 1, 2004, at 10:27 PM, Bill Coffman wrote:
...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:
- 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).
...Next, consider Dan's message, "Lexicals, continuations, and register allocation": On Tue, 30 Nov 2004 10:22:29 -0500, Dan Sugalski <[EMAIL PROTECTED]> wrote:
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:...
2a. Insert all the arcs into the CFG, which will increase spilling, but...
...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..."
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.
Above I've left just the parts relevant to "explicitly label somehow function calls which might capture full continuations". I've not been able to tell if the intention is that the user would have some special syntax to use in the HLL, or if the HLL compiler is expected to put in the indications at compile-time. The problem with the former approach is that existing languages which use continuations (Scheme, Ruby) don't have this--we can't change the languages in such a fundamental way. The problem with the latter approach is that the HLL itself doesn't know--it would need to label any function call which could call anything which could call something which would capture a real continuation. In practice that would end up meaning that the HLL compiler would have to mark all function call sites this way, so you'd still end up with the maximal set of arcs--just with the HLL compiler doing the work, rather than the register allocator. It doesn't really help the issue, just moves the work around.
I think Leo originally brought up the "labeling" idea, and seemed to think that the HLL always had enough info to label all of the call sites which could be affected by continuations. Here's my Ruby example again, and an explanation of why I think the HLL compiler can't do the necessary labeling:
def strange
callcc {|continuation| $saved = continuation}
enddef outer
a = 0
strange()
a = a + 1
print "a = ", a, "\n"
end# these two lines are "main" outer() $saved.call
This program prints out an ever-increasing sequence of numbers.
Now, "outer" could have been defined in its own compilation unit. The HLL compiler has no way of knowing that the call to strange() might capture a continuation--there's no syntactic indication inside of the definition of "outer", or at the site of the call to "outer" from the main program flow. The most an HLL compiler for Ruby could do would be to assume that all function calls might capture a continuation, and that puts us back in the same boat we're already in--we get all of the arcs.
I think we have basically 3 choices: support continuations such that they work correctly in all HLL situations and accept likely poor performance, or support only escape continuations, or devise a strategy whereby Parrot itself doesn't provide continuations, but allows them to exist at the HLL level somehow. I don't know of a way the third approach could work (though maybe someone has a clever idea), and the first two both carry significant down sides.
JEff
