[tree-ssa-branch] Optimizing non-SIMPLE trees

[tree-ssa-branch] Optimizing non-SIMPLE trees

[Diego Novillo]

I ran into this problem with constant propagation and builtins.
In string-opt-8.c we have something like this:

  const char *const s1 = "hello world";
  const char *s2;
  s2 = s1;
  if (strncmp (++s2, "", 1) <= 0)
    abort ();

The simplifier refuses to simplify the call to strncmp() because
it contains at least one constant argument.  It does this to
avoid tricking the code generator into not outputting a builtin
call when all the arguments are constant.

Clearly, the simplifier could be a bit smarter in this case, but
the point remains that we will many times refuse to simplify a
builtin or other special trees.  The question is now, how do we
tell the optimizers to keep their hands off these trees?  In this
case, constant propagation is generating this:

  s2 = (const char * const)(char *)"hello world";
  T.1 = strncmp ( ++(const char * const)(char *)"hello world", (const char *)(char *)"", 1);
  if (T.1 <= 0)
    {
      abort (); 
    }

Oops.  CCP didn't realize that ++s2 had side-effects.  It didn't
have to, of course.  All the data flow information was correct,
s2 is first used and then defined in that expression, so the
reaching definition from the previous assignment could be
replaced in that expression.  However, the expression wasn't in
SIMPLE form.

An easy way out in this case would be for CCP to ask each
expression whether it's in SIMPLE form or not.  This is a problem
because the SIMPLE grammar is not context free w.r.t. expressions
(a valid RHS cannot be used as a predicate inside an if() node,
for instance).

One idea is for the simplifier to flag these trees and make them
clobber all the symbols that they reference.  I'm not quite sure
how this would affect other optimizers, though.


Diego.

Re: [tree-ssa-branch] Optimizing non-SIMPLE trees

[Daniel Berlin]

On Fri, 9 Aug 2002, Diego Novillo wrote:

> I ran into this problem with constant propagation and builtins.
> In string-opt-8.c we have something like this:
> 
>   const char *const s1 = "hello world";
>   const char *s2;
>   s2 = s1;
>   if (strncmp (++s2, "", 1) <= 0)
>     abort ();
> 
> The simplifier refuses to simplify the call to strncmp() because
> it contains at least one constant argument.  It does this to
> avoid tricking the code generator into not outputting a builtin
> call when all the arguments are constant.
> 
> Clearly, the simplifier could be a bit smarter in this case, but
> the point remains that we will many times refuse to simplify a
> builtin or other special trees.  The question is now, how do we
> tell the optimizers to keep their hands off these trees?

Easy.
Turn them all into tree operands of the same type of tree, then ignore 
that type of tree.

IE Introduce  NON_SIMPLE_EXPR/NON_SIMPLE_STMT nodes, with just 1 operand 
each.
All non-simplified trees become sub-trees of them.

Remove them after tree optimization (so we don't have to teach anything 
else about them).

The alternative is to add a flag to the tree_common structure, but that 
takes up space in *all* trees.

>  In this
> case, constant propagation is generating this:
> 
>   s2 = (const char * const)(char *)"hello world";
>   T.1 = strncmp ( ++(const char * const)(char *)"hello world", (const char *)(char *)"", 1);
>   if (T.1 <= 0)
>     {
>       abort (); 
>     }
> 
> Oops.  CCP didn't realize that ++s2 had side-effects.  It didn't
> have to, of course.  All the data flow information was correct,
> s2 is first used and then defined in that expression, so the
> reaching definition from the previous assignment could be
> replaced in that expression.  However, the expression wasn't in
> SIMPLE form.
> 
> An easy way out in this case would be for CCP to ask each
> expression whether it's in SIMPLE form or not.  This is a problem
> because the SIMPLE grammar is not context free w.r.t. expressions
> (a valid RHS cannot be used as a predicate inside an if() node,
> for instance).
> 
> One idea is for the simplifier to flag these trees and make them
> clobber all the symbols that they reference.  I'm not quite sure
> how this would affect other optimizers, though.

The optimizers that move things or whatnot have to track this kind of 
thing anyway. There are always things that clobber things (calls, etc).

> 
> 
> Diego.
> 
> 

Re: [tree-ssa-branch] Optimizing non-SIMPLE trees

[Richard Henderson]

On Fri, Aug 09, 2002 at 10:09:37AM -0400, Diego Novillo wrote:
> The simplifier refuses to simplify the call to strncmp() because
> it contains at least one constant argument.  It does this to
> avoid tricking the code generator into not outputting a builtin
> call when all the arguments are constant.

This is bogus.

> Clearly, the simplifier could be a bit smarter in this case, but
> the point remains that we will many times refuse to simplify a
> builtin or other special trees.  The question is now, how do we
> tell the optimizers to keep their hands off these trees?

No, this is not clear.  You'd be complicating the optimizers for
no reason whatsoever.

The correct solution here is to expand builtin functions *after*
constant propagation.  Then we get nice builtin expansion when
the user hasn't written something convenient up front.

Of course afterwards you get to re-do the propagation, since we
may well have generated new constants.



r~

Re: [tree-ssa-branch] Optimizing non-SIMPLE trees

[Diego Novillo]

On Fri, 09 Aug 2002, Richard Henderson wrote:

> On Fri, Aug 09, 2002 at 10:09:37AM -0400, Diego Novillo wrote:
> > The simplifier refuses to simplify the call to strncmp() because
> > it contains at least one constant argument.  It does this to
> > avoid tricking the code generator into not outputting a builtin
> > call when all the arguments are constant.
> 
> This is bogus.
> 
string-opt-8.c fails for this exact reason.  If we simplify calls
to strncmp, whatever code that converts strncmp into a builtin
call fails to match the builtin and then a libcall is generated.


> > Clearly, the simplifier could be a bit smarter in this case, but
> > the point remains that we will many times refuse to simplify a
> > builtin or other special trees.  The question is now, how do we
> > tell the optimizers to keep their hands off these trees?
> 
> No, this is not clear.  You'd be complicating the optimizers for
> no reason whatsoever.
> 
Just the other day we were talking about trees that would need to
be passed unsimplified.  You have to tell the optimizers that
they cannot look *into* those trees.  MD builtins have this
problem as well, we can't really simplify those trees as we don't
know what the backend might expect.

> The correct solution here is to expand builtin functions *after*
> constant propagation.  Then we get nice builtin expansion when
> the user hasn't written something convenient up front.
> 
Builtin functions are always expanded after constant propagation.
Aren't builtins expanded as part of the tree->RTL expansion?
That's after tree CCP.

> Of course afterwards you get to re-do the propagation, since we
> may well have generated new constants.
> 
Will fold() deal with __builtin_strncmp if all its arguments are
constants?


Diego.

Re: [tree-ssa-branch] Optimizing non-SIMPLE trees

[Richard Henderson]

On Sat, Aug 10, 2002 at 02:15:12AM -0400, Diego Novillo wrote:
> Just the other day we were talking about trees that would need to
> be passed unsimplified.

I didn't buy it then either.

> You have to tell the optimizers that they cannot look *into* those
> trees.  MD builtins have this problem as well, we can't really
> simplify those trees as we don't know what the backend might expect.

You won't be incorrect if you treat them like a regular
function call.

> Builtin functions are always expanded after constant propagation.
> Aren't builtins expanded as part of the tree->RTL expansion?

Not all of them.  See fold_builtin.

> Will fold() deal with __builtin_strncmp if all its arguments are
> constants?

Apparently not, though it ought to.


r~

Re: [tree-ssa-branch] Optimizing non-SIMPLE trees

[Diego Novillo]

On Sat, 2002-08-10 at 17:31, Richard Henderson wrote:

> > You have to tell the optimizers that they cannot look *into* those
> > trees.  MD builtins have this problem as well, we can't really
> > simplify those trees as we don't know what the backend might expect.
> 
> You won't be incorrect if you treat them like a regular
> function call.
> 
That's exactly what we're doing now.  Trees that cannot be simplified
are flagged TF_NOT_SIMPLE.  This causes the reference finder to create
definitions for all the symbols referenced by the expression.  Safe and
easy.

> > Builtin functions are always expanded after constant propagation.
> > Aren't builtins expanded as part of the tree->RTL expansion?
> 
> Not all of them.  See fold_builtin.
> 
Thanks.

> > Will fold() deal with __builtin_strncmp if all its arguments are
> > constants?
> 
> Apparently not, though it ought to.
> 
OK.  Will look into this.


Diego.

Re: [tree-ssa-branch] Optimizing non-SIMPLE trees

[Jan Hubicka]

> On Sat, 2002-08-10 at 17:31, Richard Henderson wrote:
> 
> > > You have to tell the optimizers that they cannot look *into* those
> > > trees.  MD builtins have this problem as well, we can't really
> > > simplify those trees as we don't know what the backend might expect.
> > 
> > You won't be incorrect if you treat them like a regular
> > function call.
> > 
> That's exactly what we're doing now.  Trees that cannot be simplified
> are flagged TF_NOT_SIMPLE.  This causes the reference finder to create
> definitions for all the symbols referenced by the expression.  Safe and
> easy.
Is this necesary?  The builtins behave like real C functions, so they
don't modify their arguments.
I would believe that it is wortwhile to invest energy into simplifying
everything around to avoid creating of tons of special cases like we
have in RTL.

Honza

Re: [tree-ssa-branch] Optimizing non-SIMPLE trees

[Diego Novillo]

On Sat, 2002-08-10 at 18:12, Jan Hubicka wrote:
> > On Sat, 2002-08-10 at 17:31, Richard Henderson wrote:
> > 
> > > > You have to tell the optimizers that they cannot look *into* those
> > > > trees.  MD builtins have this problem as well, we can't really
> > > > simplify those trees as we don't know what the backend might expect.
> > > 
> > > You won't be incorrect if you treat them like a regular
> > > function call.
> > > 
> > That's exactly what we're doing now.  Trees that cannot be simplified
> > are flagged TF_NOT_SIMPLE.  This causes the reference finder to create
> > definitions for all the symbols referenced by the expression.  Safe and
> > easy.
> Is this necesary?  The builtins behave like real C functions, so they
> don't modify their arguments.
>
No.  It started being a cheap way out, but it's becoming to be a
horrendous idea (serves me right for going down this path).  It all
started when the simplifier had problems with __builtin_stdarg_start
(which expects its argument to be the last parameter to the current
function).

But then, we also ran into problems when the simplifier replaced
arguments to some of the __builtin_str* functions.  When simplified, the
compiler would stop matching the builtin and emit a libcall.  IIRC,
builtins defined in .md files had similar problems.


> I would believe that it is wortwhile to invest energy into simplifying
> everything around to avoid creating of tons of special cases like we
> have in RTL.
> 
Yes.  I should do the right thing and see why simplification confuses
some builtins.  The question is, what about target-defined builtins? 
Should the simplifier leave them alone?


Diego.

Re: [tree-ssa-branch] Optimizing non-SIMPLE trees

[Diego Novillo]

On Fri, 2002-08-09 at 14:30, Daniel Berlin wrote:

> Easy.
> Turn them all into tree operands of the same type of tree, then ignore 
> that type of tree.
> 
The problem with the wrapping approach is that we have to undo it after
we're done and (maybe) every time we need to call the regular tree
functions from the optimizers.

> The alternative is to add a flag to the tree_common structure, but that 
> takes up space in *all* trees.
> 
Nope.  We use the aux field.  It's just a new bit in tree.aux.flags.  We
only set it for trees we can't simplify and don't need to reset it
afterwards.

However, all this is moot.  We should really strive for doing the right
thing and convert everything into SIMPLE.  Special cases like this are
best avoided.


Diego.

Re: [tree-ssa-branch] Optimizing non-SIMPLE trees

[Richard Henderson]

On Sat, Aug 10, 2002 at 07:00:28PM -0400, Diego Novillo wrote:
> The question is, what about target-defined builtins? 
> Should the simplifier leave them alone?

No.  Never.  Simplify and optimize as ususal.


r~

Re: [tree-ssa-branch] Optimizing non-SIMPLE trees

[Jan Hubicka]

> No.  It started being a cheap way out, but it's becoming to be a
> horrendous idea (serves me right for going down this path).  It all
> started when the simplifier had problems with __builtin_stdarg_start
> (which expects its argument to be the last parameter to the current
> function).
> 
> But then, we also ran into problems when the simplifier replaced
> arguments to some of the __builtin_str* functions.  When simplified, the
> compiler would stop matching the builtin and emit a libcall.  IIRC,
> builtins defined in .md files had similar problems.

I see. Some of the md expanders do clever things when operands are known
to be constants.  This is not only the case of string functions but also
other stuff (like shifting, double word arithmetics etc.)
In the case simplifier loads constants to temporaries first, you lose
the performance.  I guess it is a must to constant propagate just before
RTL generation, that should fix the problem.

Similary I think it is neccesary to put in the memories when used
exactly once, that should solve builtin_stdarg.
> 
> 
> > I would believe that it is wortwhile to invest energy into simplifying
> > everything around to avoid creating of tons of special cases like we
> > have in RTL.
> > 
> Yes.  I should do the right thing and see why simplification confuses
> some builtins.  The question is, what about target-defined builtins? 
> Should the simplifier leave them alone?
I don't think we have some mighty builtins, like stdarg_start in target
specific way, so it is safe to handle them as function in all cases I am
aware of.  If we start doing so, we won't introduce the nasty stuff and
over with better design I believe.

Honza
> 
> 
> Diego.

Re: [tree-ssa-branch] Optimizing non-SIMPLE trees

[Richard Henderson]

On Sun, Aug 11, 2002 at 11:06:49AM +0200, Jan Hubicka wrote:
> I guess it is a must to constant propagate just before
> RTL generation, that should fix the problem.

Well, just before builtin expansion anyway.  In many cases we
would be better off expanding to trees instead of rtl.  Some 
of them don't make sense to do that but...

> Similary I think it is neccesary to put in the memories when used
> exactly once, that should solve builtin_stdarg.

Making the last parameter of stdarg a reference parameter might
solve it.  Alternately, is the last parameter even used other 
than for checking that it is in fact the last parameter?  If not,
then the front end could do the error check and expand that
builtin right away.



r~

Re: [tree-ssa-branch] Optimizing non-SIMPLE trees

[Jan Hubicka]

> On Sun, Aug 11, 2002 at 11:06:49AM +0200, Jan Hubicka wrote:
> > I guess it is a must to constant propagate just before
> > RTL generation, that should fix the problem.
> 
> Well, just before builtin expansion anyway.  In many cases we
> would be better off expanding to trees instead of rtl.  Some 
> of them don't make sense to do that but...
> 
> > Similary I think it is neccesary to put in the memories when used
> > exactly once, that should solve builtin_stdarg.
> 
> Making the last parameter of stdarg a reference parameter might
> solve it.  Alternately, is the last parameter even used other 
> than for checking that it is in fact the last parameter?  If not,
> then the front end could do the error check and expand that
> builtin right away.

Yes. At least with current RTL generation scheme probably propagating
memoryies is bad idea.  Our current RTL generator hides memories as well
to help CSE when optimizing.  I remember seeing few cases in i386
backend where knowing whether the operand is memory or not would help
but these are rare. Definitly much more rare than the builtin expansion
case.

Honza
> 
> 
> 
> r~

Re: [tree-ssa-branch] Optimizing non-SIMPLE trees

[Jason Merrill]

The problem seems to come down to this: the builtin expanders want args
like '(char*)"foo"', and that's not a valid SIMPLE value, so we copy it
into a temporary pointer.  Doing the reverse substitution in CCP isn't a
solution, as it would produce something not SIMPLE.

Possible solutions are
 1) Change SIMPLE so that 'val' allows ADDR_EXPR->STRING_CST (and whatever
    other tree patterns various builtins want).
 2) Enhance the builtin expanders to use dataflow information.

I prefer #2.

Jason

Re: [tree-ssa-branch] Optimizing non-SIMPLE trees

[Jan Hubicka]

> The problem seems to come down to this: the builtin expanders want args
> like '(char*)"foo"', and that's not a valid SIMPLE value, so we copy it
> into a temporary pointer.  Doing the reverse substitution in CCP isn't a
> solution, as it would produce something not SIMPLE.
> 
> Possible solutions are
>  1) Change SIMPLE so that 'val' allows ADDR_EXPR->STRING_CST (and whatever
>     other tree patterns various builtins want).
>  2) Enhance the builtin expanders to use dataflow information.
> 
> I prefer #2.
Yes, #2 should be easy and convenient way to do so.  There are not that
many expanders around so this is task doable in a day I expect.

Alternate still can be to convert SIMPLE into non-SIMPLE (with complex
operands) by CCP just before RTL expansion, but it is getting, well,
ugly.

Problem may be the standard RTL lowering process that commonly asks
whether given operand is an constant.  Perhaps it can be done by
teaching code to expand registers to ask dataflow whether register is
known to be constant and use the constant instead...

Honza
> 
> Jason

Re: [tree-ssa-branch] Optimizing non-SIMPLE trees

[Richard Henderson]

On Fri, Aug 23, 2002 at 11:23:35AM +0100, Jason Merrill wrote:
>  1) Change SIMPLE so that 'val' allows ADDR_EXPR->STRING_CST (and whatever
>     other tree patterns various builtins want).

Why is this not a constant like ADDR_EXPR->VAR_DECL is?


r~

Re: [tree-ssa-branch] Optimizing non-SIMPLE trees

[Jason Merrill]

On Fri, 23 Aug 2002 10:32:56 -0700, Richard Henderson <rth@redhat.com> wrote:

> On Fri, Aug 23, 2002 at 11:23:35AM +0100, Jason Merrill wrote:
>>  1) Change SIMPLE so that 'val' allows ADDR_EXPR->STRING_CST (and whatever
>>     other tree patterns various builtins want).
>
> Why is this not a constant like ADDR_EXPR->VAR_DECL is?

My mistake, it is.  The problem probably comes from a NOP_EXPR.

Jason