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 > - 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." > -??? > -- -Bill
