variable register frames (was: Register Allocation and Continuations problem definition)
Matt Fowles wrote: [ thanks for your summary ] Another summary can be found here: http://xrl.us/gban ... Discussions about specific solutions should and religion should have a seperate thread. I'll put together some more WRT: 4) variable sized register frames During the discussion of continuations I've posted this idea here: http://xrl.us/gbai + never have unused registers + no need for a register allocator This is simplified. We'd need a register allocator for temporary variables. But it's true that all the register allocation troubles we now have with long-ranged variables would be gone as well as the speed problems with Evil Subs and the need for spilling. + could correspond directly to scratchpad - more complicated Slightly but not much. - no register reuse No register reuse of registers persistent around a call, which is exactly the solution for the continuation problem. It's the same thing with setjmp(3)/longjmp(3). In the presence of continuations (longjmp()s) you can't reuse a register. Temporary registerers are of course reused as now. - large architectural change We now have Parrot 0.2.1 - what's the problem? Abandon a solution because we have to change internals is not the best idea. - more custom allocation (can't pool register sets) I've already proposed a scheme to allocate the register frames from 64KB chunks. But there are still more arguments, why this solution is by far the best one. Please read the thread of my analysis of the fib benchmark: http://xrl.us/gbaj This clearly shows that we can't keep the fixed-sized register frame in the long run. All the object getter and setter methods would suffer as badly as the plain function call from fib(). You might also try to run Ackermann(3, 9) if you've plenty of time ;-) | Python is running the code on the stack. It's | touching only SP(0) and SP(1) mostly. | Register usage analysis of fib shows that it could run on Parrot with | just *one* persistent register per kind. leo
Re: Register Allocation and Continuations problem definition
I hope that no one misunderstands when I say this. It is not meant to be a criticism, but rather it is my understanding of the problem, put very directly. I may be wrong, and in many ways, I hope am. There is a fundamental flaw in the Parrot architecture. In it's current form, continuations and register allocation cannot coexist. The solution is to do away with the register allocator, or to do away with continuations. This can be done, perhaps by saying that certain functions won't be subject to continuation snapshots or calls. Then register allocation can be done on those routines. Or compiling the whole program with a switch of on or off. When I say "do away with the register allocator", I mean that nearly all registers will interfere, so essentially each variable gets a register. The extensible register stack is the best way to implement this strategy. If there are long sections of code with lots of temporary variables, then register allocation might be of some use. But most variables will interfere. Implementing this would be an interesting project. It would be quite different from a standard register allocator. It might even be worth writing a paper on the techniques involved. Turning off full continuations, is a another matter. I don't know what impact that would have on parrot. It would be relatively straightforward to write the allocator with this approach. There are other issues involved, regarding how registers change when called. What is preserved, and how. Matt touched on some of these issues. My main concearn in attempting to implement the register allocator was to find the minimal control flow graph (cfg) which helps to provide the variable interference graph. This is my understanding of the problem. Matt wants this thread to be a problem definition, so these thoughts seem appropriate for this thread. I hope no one is offended by my bluntness, but if this problem is to be solved, it must be understood. Bill Coffman ps: a couple important threads on this issue were http://groups-beta.google.com/group/perl.perl6.internals/browse_frm/thread/3a61fe5e97d17389/0603ff13ca52f0ff?_done=%2Fgroup%2Fperl.perl6.internals%3F&_doneTitle=Back+to+topics&_doneTitle=Back&&d#0603ff13ca52f0ff http://groups-beta.google.com/group/perl.perl6.internals/browse_frm/thread/214157bf29879710/4c15aa4a1f56c20a?_done=%2Fgroup%2Fperl.perl6.internals%3F&_doneTitle=Back+to+topics&_doneTitle=Back&&d#4c15aa4a1f56c20a On 6/3/05, Matt Fowles <[EMAIL PROTECTED]> wrote: > > All~ > > On 6/3/05, Bill Coffman <[EMAIL PROTECTED]> wrote: > > > > There are several threads in the parrot mailing list that discuss the > > continuations problem. I hoped to be able to address parrot register > > allocator again, at some point, but it could be a while before I get to > > that. In the mean time, search the perl6-internals mailing list for > > continuations and register allocation. I'm sure you'll find it. > > I would actually very much like to see this issue moved on. In the > hopes of getting everything up to speed quickly I will try and > summarize all of the discussions and suggestions that have been made. > I am NOT trying to advocate any particular solution (yet), I just want > to make sure that everyone is on the same page. > > I propose that we use this thread to ensure that we are not talking > past each other. Discussions about specific solutions should and > religion should have a seperate thread. > > > PROBLEM: > > Continuations can be invoked repeatedly. Whenever a continuation is > reinvoked, the registers must be in a defined state or the code will > behave incorrectly. > > > BASIC ANALYSIS > > The actual state of the registers does not matter as long as it is > well defined. > > A) If the registers are defined to be garbage, then every continuation > will start by returning them to the state it expects. > > B) If the registers are defined to be preserved, then every > continuation merrily chugs along. > > Unfortunately these each have issues and as such much debate ensued. > > > SUGGESTED SOLUTIONS > > 1) Context includes registers > > + continuations don't have to preserve specifc registers > + register allocator can ignore continuations wrt spilling > - copying overheard > - value based registers (IN) return to "old" values > - pointer based registers (SP) cannot have their pointers moved or > require double indirection > > > 2) Return Continuations include registers, non don't > > + register allocator can remain mostly ignorant > + only non return continuations need to worry > - promoting a return continuation will force copying as plan (1) > > > 3) register are not restored > > + simple to explain > - register allocator must add many extra interference edges > - largely prevents reuse of register > > > 4) variable sized register frames > > + never have unused registers > + no need for a register allocator > + could correspond directly to scratchpad > - more complicated
Register Allocation and Continuations problem definition
All~ On 6/3/05, Bill Coffman <[EMAIL PROTECTED]> wrote: > > There are several threads in the parrot mailing list that discuss the > continuations problem. I hoped to be able to address parrot register > allocator again, at some point, but it could be a while before I get to > that. In the mean time, search the perl6-internals mailing list for > continuations and register allocation. I'm sure you'll find it. I would actually very much like to see this issue moved on. In the hopes of getting everything up to speed quickly I will try and summarize all of the discussions and suggestions that have been made. I am NOT trying to advocate any particular solution (yet), I just want to make sure that everyone is on the same page. I propose that we use this thread to ensure that we are not talking past each other. Discussions about specific solutions should and religion should have a seperate thread. PROBLEM: Continuations can be invoked repeatedly. Whenever a continuation is reinvoked, the registers must be in a defined state or the code will behave incorrectly. BASIC ANALYSIS The actual state of the registers does not matter as long as it is well defined. A) If the registers are defined to be garbage, then every continuation will start by returning them to the state it expects. B) If the registers are defined to be preserved, then every continuation merrily chugs along. Unfortunately these each have issues and as such much debate ensued. SUGGESTED SOLUTIONS 1) Context includes registers + continuations don't have to preserve specifc registers + register allocator can ignore continuations wrt spilling - copying overheard - value based registers (IN) return to "old" values - pointer based registers (SP) cannot have their pointers moved or require double indirection 2) Return Continuations include registers, non don't + register allocator can remain mostly ignorant + only non return continuations need to worry - promoting a return continuation will force copying as plan (1) 3) register are not restored + simple to explain - register allocator must add many extra interference edges - largely prevents reuse of register 4) variable sized register frames + never have unused registers + no need for a register allocator + could correspond directly to scratchpad - more complicated - no register reuse - large architectural change - more custom allocation (can't pool register sets) I believe the official spec calls for (2); however, I do not believe that it is currently implemented. Once again in this thread please try to remain objective and just summarize/correct. We can start a new thread to hash out the minutia of pro's/con's and new ideas, I just want everyone to be on the same page. Matt -- "Computer Science is merely the post-Turing Decline of Formal Systems Theory." -???
