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 once in a while, parrot will behave incorrectly -- but only if one is audacious enough to use continuations. So let the bugs fly!! 5a) Write the allocator to minimize the number of bugs generated. COMMENTS: * (2,3) If you think about it, suggestions 2 and 3 are essentially equivalent. They both seem like good ideas. Disadvantages: forcing compiler writer to have to think about when continuations will be taken. Advantages: minimize spilling, but retain correctness. * Suggestion 1 has the advantage of correctness, and not forcing anyone to think about when continuations are invoked. The disadvantage will only be evident when there are more than 16 volatile symbols in subroutine. It's not clear how often that will be, though it is fairly reasonable to assume that this will be a significant performance hit in a significant number of cases. Experimentation might be interesting. I also have some ideas to minimize the impact, by snipping ranges of these variables, similar to 4. * Suggestion 4 is really just another kind of spilling [1]. Spilling that is done by copying old values of otherwise dead variables, so that if they are resurrected by a continuation, they can be restored. This might not be too bad a performance hit. Advantages: correctness and compiler writers don't have to think about it. Disadvantages: 4b is unknown if possible or not, but is possible, would be an interesting path to explore. There is likely a performance hit though, which Larry and others have indicated is not really acceptable in the general case. This suggestion probably bears further examination. * I sincerely hope that no one finds suggestion 5 acceptable. A lack of correctness is really just not acceptable. Among other really bad things, this could make parrot vulnerable to security threats, and unpredictable failure, when continuatinos are used. Btw, suggestion 5a is currently implemented. The old register allocator is so bad, that there is little interference with different variables. That is why it passes those tests that the new allocator fails. I have considered writing a version of the allocator to be even less efficient. This approaches suggestion 1. -- Since this issue, is to a great extent, blocking my ability to work on the register alloctor, I would like to see it resolved. Pending that, I'd like to at least see agreement on the problem. Thanks for your perserverence in reading this, Bill [1] Spilling is currently done by designating register P31 as a PerlArray, and letting each spilled symbol occupy a position in the array. These values are accessed by copying back and forth from/to temporary registers.
