This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


Steven Bosscher <stevenb@suse.de> writes:

> 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,

New-ra select right alternatives *inside* RA.
Even more alternatives can be changed from one RA pass to another.

Denis.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]