[tree-ssa] Temporary Expression Replacement in SSA->normal.

[Roger Sayle]

On Fri, 28 Nov 2003, Zack Weinberg wrote:
> >   T.624 = search.b_pawn;
> >   T.717 = FirstOne (T.624);
> >   T.650 = search.white_king;
> >   T.651 = (int)T.650;
> >   T.718 = T.651 & 7;
> >   T.638 = T.717 & 7;
> >   T.719 = T.718 - T.638;
> >   T.720 = T.719 - -1;
> >   T.721 = (unsigned int)T.720;
> >   if (T.721 <= 2)
> >
> > being turned into
> >
> >   T.717 = FirstOne (search.b_pawn);
> >   T.650 = search.white_king;
> >   T.638 = T.717 & 7;
> >   if ((unsigned int)(((int)T.650 & 7) - T.638 - -1) <= 2)
>
> ... which is going to get rewritten back to the original example, but
> with pseudos instead of temp variables, by the tree->rtl expander.  As
> such I think this patch is barking up the wrong tree.  Shouldn't we
> instead make the RTL expander expect and understand GIMPLE form?  This
> would save work, avoid the temporary-explosion problem, and allow the
> RTL expression expander to be made dramatically simpler.
>
> Synthesis of complex machine instructions, where available, is
> combine's job.

Unfortunately not.  There are a number of program optimizations that
only get performed during RTL expansion, and the larger the tree that
is passed to expand_expr the better the code that GCC generates.

A good example is synthetic multiplication and division by a constant.
Take the following code...

int foo(int x)
{
  int y = 3;
  return x*y;
}

where currently GCC mainline generates a multiplication instruction or a
call to libgcc.  Passing "x*3" to expand_expr generates significantly
better code.  Another example, is that "fold" canonicalizes many
expressions assuming that the results will be visible during RTL
expansion.  Yet more examples, include Sethi-Ullman numbering where the
evaluation order of operands can be choosen by expand_expr so as to
minimize the number of live pseudos.  No pass other than scheduling
reorders instructions, and even that doesn't currently consider
register pressure.  And all of tree-ssa's problems with the built-in
string functions just go away, if expand_builtin gets to see the
constant arguments at RTL expansion time.


And yet another example is "(bool) x & c" where c is a power of two.
If we're generating code for an assignment this is best expanded as
"(x >> c2) & 1" which saves conditional branches or setcc instructions.
However, if the same expression is being generated for a conditional
branch, "(x & c) != 0" is a much better implementation on most targets.
Here's it the context that an expression that appears in that decides
the best way to expand it.


There's also the advantages that associative/commutative simplifications
in constant folding benefit from having a larger tree to work with.

bool foo(bool x)
{
  bool y = ! x;
  return ! y;
}


In short, not only is Andrew's optimization doing a good thing, it
should both simplify tree-ssa and enable optimizations that can't
currently be performed on mainline.  This is probably why he's seeing
such a big performance win.

I'll agree that many of these things should be picked up by the RTL
passes, and I'm actively working on that.  But there are also the
performance considerations of generating a large amount of redundant
RTL only to be cleaned up by the later passes.  You'd expect tree-ssa
to have compilation time regression over mainline :>.

Even with improvements to RTL optimizers, "combine" only looks at a
maximum of three instructions at a time.  This is why my testcase
for gcc.c-torture/compile/20020720-1.c fails on so many platforms,
but is performed trivially by tree-ssa, if all the necessary bits
can be passed to the constant folder at the same time.  Another
example is "(((A + B) + C) + D) - A" where the RTL optimizers just
can't help.


Sorry for rambling...


Roger
--
Roger Sayle,                         E-mail: roger@eyesopen.com
OpenEye Scientific Software,         WWW: http://www.eyesopen.com/
Suite 1107, 3600 Cerrillos Road,     Tel: (+1) 505-473-7385
Santa Fe, New Mexico, 87507.         Fax: (+1) 505-473-0833