Register Allocator projects summary

[Andrew MacLeod <amacleod at redhat dot com>]

Sorry Im late getting to this, but July was simply insane... 

There was a couple of discussions about register allocation at the GCC
summit, including a dinner hosted by IBM and a BOF afterward.  There may
have been more activity after that, but I wasn't around so I don't know
about it :-).   Someone else can add to this summary in that case.  

This note is just to document the directions that are being taken as a
result.  That way others know whats going on, can offer additional
ideas, or can  help out along the way.  I also don't want to forget what
we talked about :-)  Correct me if I misremember anything :-)

Generally speaking, we all know there are some serious problems with
GCC's register allocator. There have been previous attempts to rewrite
it, there is an ongoing attempt to rewrite it called YARA (makarov), and
I drafted a proposal last fall (RABLE :
http://gcc.gnu.org/ml/gcc/2005-11/msg00783.html) where I laid out what I
thought needed to be done were a new rewrite from scratch to be
attempted..

We came away with 4 primary action points/projects.

1 - Its just getting to the point where maybe we can see where Vlad's
complete rewrite of RA will take us. (branch: yara-branch).  It replaces
everything from regclass to reload, and I believe he is continuing down
the YARA path improving compile time, generated code, and adding
additional targets. I'm sure he would love help :-) 

I don't think anyone else is actually interested in investing the time
and effort into another new RA rewrite from scratch at this point. I
know I'm certainly not.

2 - Thats why I mutated RABLE into RABLET
(http://gcc.gnu.org/ml/gcc/2006-06/msg00736.html). Simply stated, it
attempts to unite the out-of-ssa pass and expand to choose insns with
appropriate register/memory patterns, and combine this with various
register pressure reduction techniques.  The idea is to relieve the
register allocator from having to deal with excessive levels of register
pressure. (ie, 100 registers live at a time).  We discussed what I was
attempting to do and my plan is to go forward with RABLET this fall. I
have cut a branch for some of the initial out-of-ssa rewriting work
(branch: out-of-ssa-the-sequel) and begun that initial work there.

3 - Peter Bergner has been doing some incremental improvements to the
existing RA code, getting it to use less memory, run faster, fixing
warts, and whatever else he sees in there that is fixable and/or
possibly useful by a major rewrite when/if it happens.  I think he also
cut a branch in the not too distant past. (branch: ra-improvements)

4 - It was also concluded that it might be possible to work around the
lack of early instruction selection by writing a pass which would choose
instruction alternatives early for insns.  The later passes would then
be able to see the chosen alternative, and make decisions based on that.
The hope is that this would a) help refine register choices in global
and local allocators and b) prevent reload from undoing a lot of
decisions as it does today.  All without having to undertake a major
rewrite of RA.  At the BOF, Michael Matz thought this sounded like
something he would like to try.  He has also created a branch I believe.
(branch: insn-select)

Those are the 4 actions/projects we left the summit with that I am aware
of.  With any luck at all, one or more of these will have a significant
impact on our register allocator.  Often projects like these proceed in
virtual silence until they are mostly done.  Perhaps I'll try to do a
follow up in a few months to check the progress and results (if any) on
the 4 projects, and post the results as a summary.  Down the road, there
may be some uniting of the work from the various projects, I can see
some potential there...

If anyone is interested in any of these projects, I've identified the
responsible parties above, and you can contact them. If there are any
other suggestions for a project which might also help, by all means let
me know and we can add it to the list.

That's all I remember!  Did I miss anything?

Andrew