This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
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.