Re: MIPS: 2'nd pass of ira, causes weird register allocation for 2-op mult

[Vladimir Makarov <vmakarov at redhat dot com>]

On 05/29/2012 02:33 AM, Richard Sandiford wrote:
> Hi Vlad,
>
> Thanks for the answer.
>
> Vladimir Makarov<vmakarov@redhat.com>  writes:
> > On 05/28/2012 03:09 PM, Richard Sandiford wrote:
> > >     Or is it a conceptual part of the algorithm?
> > No.
> > >     More generally,
> > > what kind of situations does the second pass help with?
> > I can not show such situations right now but I did some benchmarking
> > long ago on the old RA and the second pass is really important for
> > better code generation.  That time I even thought about 3rd pass for
> > -O3.  I don't think the situation is now different.
> >
> > Cost pass is a complicated part.  It is impossible to find some good
> > literature which could help.  The problem is in GCC compiler specifics
> > when code selection is not done (at least fully) before RA and we don't
> > know until reload end what  alternative will be used.  So some code
> > selection is done in combiner, some in IRA (including cost pass by
> > defining allocation classes for pseudos) and final code selection is
> > done in reload.
> Understood.  But I wasn't sure what the second pass was actually trying
> to do, or more specifically, how it was expected to give different
> results from the first pass.  Most other parts of IRA are well commented
> and describe what the code is trying to do (with as you say the usual
> caveat that this is always going to be a heuristic, and may not be taken
> directly from the literature).  But I couldn't see a similar comment
> describing how the second pass worked and what it was trying to do.
>
> I'd be happy to add one myself, but I haven't worked it out yet :-)
Here is an extract from my article from GCC Summit 2004 proceedings.

  It is interesting to note that the pass also implicitly does code
selection.  Regclass works in two passes.  On the first pass, it
defines the preferred and alternative classes without taking the
possible classes of other operands into account.  For example, an
instruction with two operand pseudo-registers exists in two variants;
one accepting classes {\em A} and {\em B}, and other one accepting
{\em C} and {\em D}.  On the first pass, the algorithm does not see
that the variant with classes {\em A} and {\em D} will be more costly
because it will require the generation of additional move
instructions.  On the second pass, the algorithm will take it into
account. As a result the preferred or alternative class of a
pseudo-register could change.  This means two passes are not enough to
find the preferred and alternative classes accurately; but it is a
good approximation.

I just run SPECInt2000 on x86 (-O2) without and with 2nd pass for today 
trunk.
2nd pass permits to reduce code size 1.36% in average, requires 0.2% 
more compilation time, and
improves performance by 2.6%.