Re: [PATCH]: Improve ability of PRE to detect redundancies

[Roger Sayle <roger at eyesopen dot com>]

On Thu, 25 Nov 2004, Daniel Berlin wrote:
> On Thu, 2004-11-25 at 20:12 -0700, Roger Sayle wrote:
> > On Thu, 25 Nov 2004, Daniel Berlin wrote:
>
> > Why not just
> >
> > static tree
> > fully_constant_expression (tree t)
> > {
> >   tree folded = fold (t);
> >   if (folded != t && is_gimple_min_invariant (folded))
> >     return folded;
> >   return t;
> > }
>
> For the same reason ssa-ccp doesn't use fold.
> We don't need it's power in this instance :).
>
> > which may also simplify the task of teaching GNV-PRE that "x + 1"
> > is equivalent to "1 + x", or that "x + x" is equivalent to "x * 2",
> > etc..
> It wouldn't actually, because that stuff goes in a different place (the
> value number lookup routine, and in recursive folding of value handles
> during phi translation and and lookup).
> I once had some stuff to fold value handles in all the right places
> (which would make this patch unnecessary), but it required a lot of
> memory and time.
> Also, it already knows that 1 + x is equivalent to x + 1, because the
> hash function knows that :)

How about "x + 0", "x << 0" and "x * 1" being equivalent to "x"?

I only enquire as I expect that ultimately fold_binary_to_constant
will become functionally equivalent to a call to "fold" followed
by a CONSTANT_P test.  At that time the only benefit of the
fold_foo_to_constant APIs will be that unlike fold, it avoids
constructing a tree node just to test whether something can be
simplified.  In your example, you already have the tree constructed,
so fold is more appropriate.

You'll notice that in tree-ssa-cpp.c there are far more calls to
fold() than there are to fold_foo_to_constant() which are only
used when a tree hasn't yet been constructed, which avoids the
potential garbage generation of "fold (buildN (...))".


Of course, there's nothing incorrect with your patch, I'm just
trying to describe some "rules of thumb" for which of fold-const.c's
interfaces is most appropriate and to discover whether this case
is a valid exception.  Things will likely become even more confusing
for 4.x with the probable addition of fold_unary, fold_binary and
fold_ternary, and their siblings fold_build1, fold_build2 and
fold_build3.


> As for SPEC, I just ran the numbers, i never did real analysis of why it
> wasn't improving them.  I only did this because there was other real
> code out there that this should improve. :)

To support Dan's and Steve's request that this at least be considered
for 4.0, this patch allows GCC to perform a class of optimization that
competing commercial compilers have done for years but until now has
been impossible for GCC.  The description of this patch as fixing a
known deficiency in GCC GVN-PRE, i.e. a potential bug fix, and his
submission before the thanksgiving deadline, means that its not
"obviously" inappropriate for the current stage of 4.0, and certainly
within the release manager's discretion.

Perhaps bootstrap and regression testing on a few more platforms
wouldn't hurt?

Roger
--