Hello, I worked on the parrot register allocation problem a few months ago. The problem I encountered was that of continuations based dependencies. There were architectural issues about continuations, and Leo proposed changes that would fix this, but Dan said it was too late for architectral changes. Basically the existence of continuations adds a lot of dependencies that don't want to go away, defeating most of the benefit that one can get from register alloction.
I am referring to parrot's use of "full continuations", which allow a snap shot of the current runtime stack. Any function can take a snapshot or restore the stack to a previous snap shot. This makes traditional register allocation problematic. As far as I can tell, the continuations depency problem was not solved, and in fact the existing register allocator is also in conflict with the continuations based dependencies. (Unless something has been done in the last few weeks.) The resolutions seems to be not to add tests that break things. Thus, continuations based tests are few, and unstable. Changing the way the registers allocate, even though they still don't violate the interference graph, will break some tests. 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. The above not withstanding, I think there are still quite a few things that can be done to improve register allocation in parrot. If anyone is interested, I'm sure I could dig up my code. Bill Coffman On 6/3/05, Curtis Rawls <[EMAIL PROTECTED]> wrote: > > On 6/3/05, Leopold Toetsch <[EMAIL PROTECTED]> wrote: > > Dheeraj Kumar Arora wrote: > > > I m interseted in one of LLVM project > > > "Implement well-known optimizations in PIR compiler (SSA -> register > > > allocation)" > > > > [ I have answerd this ] > > > > Parrot is a register based virtual machine with 32*4 registers. There > > are a lot of studies WRT optimizations and register allocations for > > compilers and hardware CPUs but probably all these things can be applied > > to Parrot too. See also imcc/cfg.c and imcc/reg_alloc.c for existing > code. > > > > I'm not a computer scientist nor am I able to follow most of the papers > > regarding various optimization techniques or the needed infrastructure > > to implement it > > > > Anyway, there are folks on our mailing list like Curtis Rawls, who could > > probably better summarize what's needed and what should be done. > > > > > Can Any send me the details? > > > > Yes please, folks. > > > > leo > > Wow, thanks for the link to the Summer of Code, that looks like fun! > (I know I'll be thinking about my proposal all day at work : ). > > I don't have my TODO list with me, I will try to post it later today. > > I have been working and thinking about improvements to the Parrot/IMCC > optimizer for a while now. Implementing SSA is definitely at the top > of my list, because it simplifies a lot of optimizations and makes > some others possible. The biggest challenge is to graft such a big > change onto a working system, with small changes at a time. > > The reference to LLVM is interesting, since it has similar goals to > Parrot, but is research-oriented. I bet there are some good > techniques that could be learned (and borrowed : ) from LLVM. > > -Curtis Rawls > -- -Bill
