Re: What to do with new-ra for GCC 4.0

[Steven Bosscher <stevenb at suse dot de>]

On Jan 04, 2005 11:54 AM, Jan Vroonhof <jvlists@ntlworld.com> wrote:

> > Bingo.
> > Heck, i helped write it and i agree.
> > new-ra has failed, long live a new new-ra
> 
> Is there a discussion somewhere of what went wrong so any "new new-ra"
> can learn form them?

Of course such discussions have taken place, but many of them are
probably not archived.  I've summarized my impression of them below.

> IIRC "new-ra" uses/used all the sexy modern ra
> algorithms

That is part of the problem: it didn't choose one set of algorithms
but just implemented them all.  Actually that's not so hard to fix,
but someone would have to do it and it hasn't happened.

Some other problems I've heard mentioning:

1) It tries *really* hard to do well for subregs, which is kinda
   nice, but it causes an immense amount of cruft in the register   
   allocator, throughout.  The proper fix would be to try and
   avoid subregs as much as possible, and leave it to reload to
   fix up that mess.

2) The version on mainline finds itself overruled by reload too
   often.  The fix on the new-regalloc branch is pre-reload, which
   is an excelent idea IMHO, except that pre-reload.c is just a
   stripped version of reload{,1}.c, which is exactly what new-ra
   was supposed to get rid of.  Too fight evil, you have to become
   evil...

3) It does not include enough information in the conflict graph.
   The point of graph coloring is that the conflict graph tells
   you what can and what cannot share a register.  In new-ra it
   is not that easy.  The general rule should be "avoid reloads"
   but new efforts should probably make an exception for subregs.

4) It just iterates, and iterates, and iterates...  Appel&George,
   who dragged graph coloring into the sewer ;-)  New-ra can also
   do Chaitin/Briggs, and on the new-regalloc branch apparently
   that works quite well.

Of course the worst problem is just bitrot.  Even on the branch
nothing has happened in a while.  The last merge from mainline to
the branch was on 2003-10-09, and the last checkin was 2004-04-02
so you can pretty much say that branch is dead.  The last merge
from the branch to mainline was on 2002-07-15, which also isn't
exactly yesterday.

There really are at least three good ideas on the new-regalloc branch
that are IMHO must-haves for a graph coloring register allocator for
GCC:
- web class, to replace regclass and choose register classes for
  webs instead of pseudos.  This also includes splitting webs if
  a register in a web really wants to be in two different classes
  to satisfy constraints in two different insns.  Right now, as
  far as I understand, regclass just picks one and lets reload
  figure out how to fix up that mistake.
- A semi-strict RTL mode.  Right now there is just strict and
  non-strict.  On the branch there is a semi-strict mode which is
  the same as strict RTL except that pseudo-registers are still
  allowed.
- pre-reload (which is related to web class) to make sure as many
  insn constraints as possible are satisfied before the register
  allocator goes to work.  Basically, after pre-reload the insns
  stream should be in semi-strict RTL form.

Basically these ideas mean that GCC selects an insn alternative
*before* RA, rather than after it in reload like we do now.  Having
more constraints satisfied means that you don't have as many reloads
and your near-perfect register allocation isn't messed up by lots of
reloads.
And of course, if the goal is to make reload simpler, having fewer
reloads is a good start.


> and even had the AFAIK unprecedented waiver of relevant 
> patents ...

Yup.

(Most of these patents have expired by now, I think (???)).

Gr.
Steven