[patch] Perform anonymous constant propagation during inlining

[patch] Perform anonymous constant propagation during inlining

[Eric Botcazou]

[-- Attachment #1: Type: text/plain, Size: 1135 bytes --]

Historically the pragma Inline_Always of GNAT had been implemented in the FE 
because the RTL inliner and then the Tree inliner weren't invoked at -O0 or 
powerful enough to inline some constructs.  But this approach had drawbacks, 
especially wrt debug info.  These restrictions were gradually lifted and now 
the pragma is entirely piggybacked on the Tree inliner.

This went mostly OK, except for a few cases where intrisinc operations that 
used to be reasonably handled at -O0 now generate awful code, the typical 
example being a modulus or division instrinsic by a power-of-2 generating a 
fully-fledged modulus or division instruction instead of a simple shift.

Therefore the attached patch implements anonymous constant propagation in the 
inliner to fix the code quality regression.

Tested on x86_64-suse-linux, OK for the mainline?


2015-04-29  Eric Botcazou  <ebotcazou@adacore.com>

	* tree-inline.c (remap_gimple_op_r): Do anonymous constant propagation.
	(copy_bb): Fold conversions of constants immediately.


2015-04-29  Eric Botcazou  <ebotcazou@adacore.com>

	* gnat.dg/inline12.adb: New test.


-- 
Eric Botcazou

[-- Attachment #2: inline12.adb --]
[-- Type: text/x-adasrc, Size: 348 bytes --]

-- { dg-do compile }

with System.Storage_Elements; use System, System.Storage_Elements;

function Inline12 return Natural is
   A : Address := Inline12'Code_Address;
begin
   while A mod Address'Alignment /= 0 loop
      A := A + 1;
   end loop;
   return Natural (A - Inline12'Code_Address);
end;

-- { dg-final { scan-assembler-not "mod|div" } }

[-- Attachment #3: p.diff --]
[-- Type: text/x-patch, Size: 1910 bytes --]

Index: tree-inline.c
===================================================================
--- tree-inline.c	(revision 222439)
+++ tree-inline.c	(working copy)
@@ -898,7 +898,19 @@ remap_gimple_op_r (tree *tp, int *walk_s
 
   if (TREE_CODE (*tp) == SSA_NAME)
     {
-      *tp = remap_ssa_name (*tp, id);
+      tree t = remap_ssa_name (*tp, id);
+      /* Perform anonymous constant propagation, this makes it possible to
+         generate reasonable code even at -O0 for operators implemented as
+         inline functions.  */
+      if (TREE_CODE (t) == SSA_NAME
+	  && SSA_NAME_DEF_STMT (t)
+	  && (!SSA_NAME_VAR (t) || DECL_IGNORED_P (SSA_NAME_VAR (t)))
+	  && gimple_assign_copy_p (SSA_NAME_DEF_STMT (t))
+	  && is_gimple_min_invariant
+	     (gimple_assign_rhs1 (SSA_NAME_DEF_STMT (t))))
+	*tp = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (t));
+      else
+	*tp = t;
       *walk_subtrees = 0;
       return NULL;
     }
@@ -1965,7 +1977,7 @@ copy_bb (copy_body_data *id, basic_block
 
 	  /* Statements produced by inlining can be unfolded, especially
 	     when we constant propagated some operands.  We can't fold
-	     them right now for two reasons:
+	     them right now in the general case for two reasons:
 	     1) folding require SSA_NAME_DEF_STMTs to be correct
 	     2) we can't change function calls to builtins.
 	     So we just mark statement for later folding.  We mark
@@ -1974,7 +1986,10 @@ copy_bb (copy_body_data *id, basic_block
 	     foldable indirectly are updated.  If this turns out to be
 	     expensive, copy_body can be told to watch for nontrivial
 	     changes.  */
-	  if (id->statements_to_fold)
+	  if (gimple_assign_cast_p (stmt)
+	      && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
+	    fold_stmt (&copy_gsi);
+	  else if (id->statements_to_fold)
 	    id->statements_to_fold->add (stmt);
 
 	  /* We're duplicating a CALL_EXPR.  Find any corresponding

Re: [patch] Perform anonymous constant propagation during inlining

[Richard Biener]

On Wed, Apr 29, 2015 at 11:50 AM, Eric Botcazou <ebotcazou@adacore.com> wrote:
> Historically the pragma Inline_Always of GNAT had been implemented in the FE
> because the RTL inliner and then the Tree inliner weren't invoked at -O0 or
> powerful enough to inline some constructs.  But this approach had drawbacks,
> especially wrt debug info.  These restrictions were gradually lifted and now
> the pragma is entirely piggybacked on the Tree inliner.
>
> This went mostly OK, except for a few cases where intrisinc operations that
> used to be reasonably handled at -O0 now generate awful code, the typical
> example being a modulus or division instrinsic by a power-of-2 generating a
> fully-fledged modulus or division instruction instead of a simple shift.
>
> Therefore the attached patch implements anonymous constant propagation in the
> inliner to fix the code quality regression.
>
> Tested on x86_64-suse-linux, OK for the mainline?

Hmm, special-casing this in the inliner looks odd to me.  ISTR the inliner
already propagates constant parameters to immediate uses, so I guess
you run into the casting case you handle specially.

But then if any constant propagation is ok at -O0 why not perform full-fledged
constant propagation (with !DECL_IGNORED_P vars as a propagation barrier)
as a regular SSA pass?  That is, if you'd had a Inline_Always function like

int foo (int i)
{
  return (i + 1) / i;
}

you'd not get the desired result as the i + 1 stmt wouldn't be folded
and thus the (i + 1) / i stmt wouldn't either.

That said - why does RTL optimization not save you here anyway?
After all, it is responsible for turning divisions into shifts.

Soo - if you use the existing CCP pass and make surely_varying_stmt_p
return true for defs of !DECL_IGNORED_P stmts at -O0 (strictly needed to make
setting vars in gdb possible) and somehow arrange for ccp to run at -O0...

It might help other obscure cases with inline-asms to behave consistently
with -O0 vs. -On as well.

Richard.

> 2015-04-29  Eric Botcazou  <ebotcazou@adacore.com>
>
>         * tree-inline.c (remap_gimple_op_r): Do anonymous constant propagation.
>         (copy_bb): Fold conversions of constants immediately.
>
>
> 2015-04-29  Eric Botcazou  <ebotcazou@adacore.com>
>
>         * gnat.dg/inline12.adb: New test.
>
>
> --
> Eric Botcazou

Re: [patch] Perform anonymous constant propagation during inlining

[Jan Hubicka]

> Historically the pragma Inline_Always of GNAT had been implemented in the FE 
> because the RTL inliner and then the Tree inliner weren't invoked at -O0 or 
> powerful enough to inline some constructs.  But this approach had drawbacks, 
> especially wrt debug info.  These restrictions were gradually lifted and now 
> the pragma is entirely piggybacked on the Tree inliner.
> 
> This went mostly OK, except for a few cases where intrisinc operations that 
> used to be reasonably handled at -O0 now generate awful code, the typical 
> example being a modulus or division instrinsic by a power-of-2 generating a 
> fully-fledged modulus or division instruction instead of a simple shift.
> 
> Therefore the attached patch implements anonymous constant propagation in the 
> inliner to fix the code quality regression.
> 
> Tested on x86_64-suse-linux, OK for the mainline?
> 
>    if (TREE_CODE (*tp) == SSA_NAME)
>      {
> -      *tp = remap_ssa_name (*tp, id);
> +      tree t = remap_ssa_name (*tp, id);
> +      /* Perform anonymous constant propagation, this makes it possible to
> +         generate reasonable code even at -O0 for operators implemented as
> +         inline functions.  */
> +      if (TREE_CODE (t) == SSA_NAME
> +	  && SSA_NAME_DEF_STMT (t)
> +	  && (!SSA_NAME_VAR (t) || DECL_IGNORED_P (SSA_NAME_VAR (t)))
> +	  && gimple_assign_copy_p (SSA_NAME_DEF_STMT (t))
> +	  && is_gimple_min_invariant
> +	     (gimple_assign_rhs1 (SSA_NAME_DEF_STMT (t))))
> +	*tp = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (t));
> +      else
> +	*tp = t;

This looks like a good idea to me (though i can't approve it).  We may want to
lift the (!SSA_NAME_VAR (t) || DECL_IGNORED_P (SSA_NAME_VAR (t))) when optimize
is set - the amount of garbage inliner produce is large and killing it early is
better than killing it later.  This has chance to help early opts where
ordering between ccp and einline is quite hard.
>        *walk_subtrees = 0;
>        return NULL;
>      }
> @@ -1965,7 +1977,7 @@ copy_bb (copy_body_data *id, basic_block
>  
>  	  /* Statements produced by inlining can be unfolded, especially
>  	     when we constant propagated some operands.  We can't fold
> -	     them right now for two reasons:
> +	     them right now in the general case for two reasons:
>  	     1) folding require SSA_NAME_DEF_STMTs to be correct
>  	     2) we can't change function calls to builtins.
>  	     So we just mark statement for later folding.  We mark
> @@ -1974,7 +1986,10 @@ copy_bb (copy_body_data *id, basic_block
>  	     foldable indirectly are updated.  If this turns out to be
>  	     expensive, copy_body can be told to watch for nontrivial
>  	     changes.  */
> -	  if (id->statements_to_fold)
> +	  if (gimple_assign_cast_p (stmt)
> +	      && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
> +	    fold_stmt (&copy_gsi);
> +	  else if (id->statements_to_fold)

Why this is needed? Is it just an optimization because we know that folding of
casts will not do crazy stuff like SSA graph walking (that was original reason
for delaying the folidng) or just an optimization to reudce the size of the list?

Honza
>  	    id->statements_to_fold->add (stmt);
>  
>  	  /* We're duplicating a CALL_EXPR.  Find any corresponding

Re: [patch] Perform anonymous constant propagation during inlining

[Richard Biener]

On Wed, Apr 29, 2015 at 3:23 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> Historically the pragma Inline_Always of GNAT had been implemented in the FE
>> because the RTL inliner and then the Tree inliner weren't invoked at -O0 or
>> powerful enough to inline some constructs.  But this approach had drawbacks,
>> especially wrt debug info.  These restrictions were gradually lifted and now
>> the pragma is entirely piggybacked on the Tree inliner.
>>
>> This went mostly OK, except for a few cases where intrisinc operations that
>> used to be reasonably handled at -O0 now generate awful code, the typical
>> example being a modulus or division instrinsic by a power-of-2 generating a
>> fully-fledged modulus or division instruction instead of a simple shift.
>>
>> Therefore the attached patch implements anonymous constant propagation in the
>> inliner to fix the code quality regression.
>>
>> Tested on x86_64-suse-linux, OK for the mainline?
>>
>>    if (TREE_CODE (*tp) == SSA_NAME)
>>      {
>> -      *tp = remap_ssa_name (*tp, id);
>> +      tree t = remap_ssa_name (*tp, id);
>> +      /* Perform anonymous constant propagation, this makes it possible to
>> +         generate reasonable code even at -O0 for operators implemented as
>> +         inline functions.  */
>> +      if (TREE_CODE (t) == SSA_NAME
>> +       && SSA_NAME_DEF_STMT (t)
>> +       && (!SSA_NAME_VAR (t) || DECL_IGNORED_P (SSA_NAME_VAR (t)))
>> +       && gimple_assign_copy_p (SSA_NAME_DEF_STMT (t))
>> +       && is_gimple_min_invariant
>> +          (gimple_assign_rhs1 (SSA_NAME_DEF_STMT (t))))
>> +     *tp = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (t));
>> +      else
>> +     *tp = t;
>
> This looks like a good idea to me (though i can't approve it).  We may want to
> lift the (!SSA_NAME_VAR (t) || DECL_IGNORED_P (SSA_NAME_VAR (t))) when optimize
> is set - the amount of garbage inliner produce is large and killing it early is
> better than killing it later.  This has chance to help early opts where
> ordering between ccp and einline is quite hard.

Early opts run CCP as pretty much the first pass, so I don't see what
you are refering to here.

>>        *walk_subtrees = 0;
>>        return NULL;
>>      }
>> @@ -1965,7 +1977,7 @@ copy_bb (copy_body_data *id, basic_block
>>
>>         /* Statements produced by inlining can be unfolded, especially
>>            when we constant propagated some operands.  We can't fold
>> -          them right now for two reasons:
>> +          them right now in the general case for two reasons:
>>            1) folding require SSA_NAME_DEF_STMTs to be correct
>>            2) we can't change function calls to builtins.
>>            So we just mark statement for later folding.  We mark
>> @@ -1974,7 +1986,10 @@ copy_bb (copy_body_data *id, basic_block
>>            foldable indirectly are updated.  If this turns out to be
>>            expensive, copy_body can be told to watch for nontrivial
>>            changes.  */
>> -       if (id->statements_to_fold)
>> +       if (gimple_assign_cast_p (stmt)
>> +           && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
>> +         fold_stmt (&copy_gsi);
>> +       else if (id->statements_to_fold)
>
> Why this is needed? Is it just an optimization because we know that folding of
> casts will not do crazy stuff like SSA graph walking (that was original reason
> for delaying the folidng) or just an optimization to reudce the size of the list?

Beause this folding turns the cast into sth the above hunk handles...

It's basically a hack ;)

A better approach might be to simply fold stmts we copy during the
stmt copy itself by using gimple_build intead of gimple_copy + fold_stmt.
Note that the match-and-simplify machinery does not perform constant
propgation but relies on a valueization hook.

Richard.

> Honza
>>           id->statements_to_fold->add (stmt);
>>
>>         /* We're duplicating a CALL_EXPR.  Find any corresponding

Re: [patch] Perform anonymous constant propagation during inlining

[Jan Hubicka]

> On Wed, Apr 29, 2015 at 3:23 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
> >> Historically the pragma Inline_Always of GNAT had been implemented in the FE
> >> because the RTL inliner and then the Tree inliner weren't invoked at -O0 or
> >> powerful enough to inline some constructs.  But this approach had drawbacks,
> >> especially wrt debug info.  These restrictions were gradually lifted and now
> >> the pragma is entirely piggybacked on the Tree inliner.
> >>
> >> This went mostly OK, except for a few cases where intrisinc operations that
> >> used to be reasonably handled at -O0 now generate awful code, the typical
> >> example being a modulus or division instrinsic by a power-of-2 generating a
> >> fully-fledged modulus or division instruction instead of a simple shift.
> >>
> >> Therefore the attached patch implements anonymous constant propagation in the
> >> inliner to fix the code quality regression.
> >>
> >> Tested on x86_64-suse-linux, OK for the mainline?
> >>
> >>    if (TREE_CODE (*tp) == SSA_NAME)
> >>      {
> >> -      *tp = remap_ssa_name (*tp, id);
> >> +      tree t = remap_ssa_name (*tp, id);
> >> +      /* Perform anonymous constant propagation, this makes it possible to
> >> +         generate reasonable code even at -O0 for operators implemented as
> >> +         inline functions.  */
> >> +      if (TREE_CODE (t) == SSA_NAME
> >> +       && SSA_NAME_DEF_STMT (t)
> >> +       && (!SSA_NAME_VAR (t) || DECL_IGNORED_P (SSA_NAME_VAR (t)))
> >> +       && gimple_assign_copy_p (SSA_NAME_DEF_STMT (t))
> >> +       && is_gimple_min_invariant
> >> +          (gimple_assign_rhs1 (SSA_NAME_DEF_STMT (t))))
> >> +     *tp = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (t));
> >> +      else
> >> +     *tp = t;
> >
> > This looks like a good idea to me (though i can't approve it).  We may want to
> > lift the (!SSA_NAME_VAR (t) || DECL_IGNORED_P (SSA_NAME_VAR (t))) when optimize
> > is set - the amount of garbage inliner produce is large and killing it early is
> > better than killing it later.  This has chance to help early opts where
> > ordering between ccp and einline is quite hard.
> 
> Early opts run CCP as pretty much the first pass, so I don't see what
> you are refering to here.

Hmm, you are right. I remember playing with similar patch but that was before
we turned off iteration in early inliner and it was motivated to do more
of indirect  call promotion.

Since ipa-prop is no longer complete joke on propagating devirutalization info
perhaps this is no longer too important.

honza

Re: [patch] Perform anonymous constant propagation during inlining

[Eric Botcazou]

> Hmm, special-casing this in the inliner looks odd to me.  ISTR the inliner
> already propagates constant parameters to immediate uses, so I guess
> you run into the casting case you handle specially.

Right on both counts, the original GIMPLE looks like:

  right.3 = (system__storage_elements__integer_address) right;
  D.4203 = D.4201 % right.3;
  D.4200 = (system__storage_elements__storage_offset) D.4203;
  return D.4200;

and setup_one_parameter has:

  /* If there is no setup required and we are in SSA, take the easy route
     replacing all SSA names representing the function parameter by the
     SSA name passed to function.

     We need to construct map for the variable anyway as it might be used
     in different SSA names when parameter is set in function.

     Do replacement at -O0 for const arguments replaced by constant.
     This is important for builtin_constant_p and other construct requiring
     constant argument to be visible in inlined function body.  */
  if (gimple_in_ssa_p (cfun) && rhs && def && is_gimple_reg (p)
      && (optimize
          || (TREE_READONLY (p)
	      && is_gimple_min_invariant (rhs)))
      && (TREE_CODE (rhs) == SSA_NAME
	  || is_gimple_min_invariant (rhs))
      && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
    {
      insert_decl_map (id, def, rhs);
      return insert_init_debug_bind (id, bb, var, rhs, NULL);
    }

and here is the GIMPLE after inlining:

  _17 = _16;
  _18 = _17;
  right.3_19 = 8;
  _20 = _18 % right.3_19;
  _21 = (system__storage_elements__storage_offset) _20;

so the constant replacement is done for right.3_19 by the above block.

> But then if any constant propagation is ok at -O0 why not perform
> full-fledged constant propagation (with !DECL_IGNORED_P vars as a
> propagation barrier) as a regular SSA pass?  That is, if you'd had a
> Inline_Always function like
> 
> int foo (int i)
> {
>   return (i + 1) / i;
> }
> 
> you'd not get the desired result as the i + 1 stmt wouldn't be folded
> and thus the (i + 1) / i stmt wouldn't either.

That's OK, only the trivial cases need to be dealt with since it's -O0 so 
running a fully-fledged constant propagation seems overkill.

> That said - why does RTL optimization not save you here anyway?
> After all, it is responsible for turning divisions into shifts.

You mean the RTL expander?  Because the SSA name isn't replaced with the RHS 
of its defining statement in:

      /* For EXPAND_INITIALIZER try harder to get something simpler.  */
      if (g == NULL
	  && modifier == EXPAND_INITIALIZER
	  && !SSA_NAME_IS_DEFAULT_DEF (exp)
	  && (optimize || DECL_IGNORED_P (SSA_NAME_VAR (exp)))
	  && stmt_is_replaceable_p (SSA_NAME_DEF_STMT (exp)))
	g = SSA_NAME_DEF_STMT (exp);

since modifier is EXPAND_NORMAL.  Do you think it would be OK to be a little 
more aggressive here?  Something like:

      /* If we aren't on the LHS, look into the defining statement.  */
      if (g == NULL
	  && modifier != EXPAND_WRITE
	  && !SSA_NAME_IS_DEFAULT_DEF (exp)
	  && (optimize || DECL_IGNORED_P (SSA_NAME_VAR (exp)))
	  && stmt_is_replaceable_p (SSA_NAME_DEF_STMT (exp)))
	 {
	    g = SSA_NAME_DEF_STMT (exp);
	    /* For EXPAND_INITIALIZER substitute in all cases, otherwise do
	       it only for constants.  */
	    if (modifier != EXPAND_INITIALIZER
		&& (!gimple_assign_copy_p (g)
		    || !is_gimple_min_invariant (gimple_assign_rhs1 (g))))
	      g = NULL;
	 }

That's certainly sufficient here.

-- 
Eric Botcazou

Re: [patch] Perform anonymous constant propagation during inlining

[Richard Biener]

On May 1, 2015 12:27:17 PM GMT+02:00, Eric Botcazou <ebotcazou@adacore.com> wrote:
>> Hmm, special-casing this in the inliner looks odd to me.  ISTR the
>inliner
>> already propagates constant parameters to immediate uses, so I guess
>> you run into the casting case you handle specially.
>
>Right on both counts, the original GIMPLE looks like:
>
>  right.3 = (system__storage_elements__integer_address) right;
>  D.4203 = D.4201 % right.3;
>  D.4200 = (system__storage_elements__storage_offset) D.4203;
>  return D.4200;
>
>and setup_one_parameter has:
>
>/* If there is no setup required and we are in SSA, take the easy route
>     replacing all SSA names representing the function parameter by the
>     SSA name passed to function.
>
>   We need to construct map for the variable anyway as it might be used
>     in different SSA names when parameter is set in function.
>
>     Do replacement at -O0 for const arguments replaced by constant.
> This is important for builtin_constant_p and other construct requiring
>     constant argument to be visible in inlined function body.  */
>  if (gimple_in_ssa_p (cfun) && rhs && def && is_gimple_reg (p)
>      && (optimize
>          || (TREE_READONLY (p)
>	      && is_gimple_min_invariant (rhs)))
>      && (TREE_CODE (rhs) == SSA_NAME
>	  || is_gimple_min_invariant (rhs))
>      && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
>    {
>      insert_decl_map (id, def, rhs);
>      return insert_init_debug_bind (id, bb, var, rhs, NULL);
>    }
>
>and here is the GIMPLE after inlining:
>
>  _17 = _16;
>  _18 = _17;
>  right.3_19 = 8;
>  _20 = _18 % right.3_19;
>  _21 = (system__storage_elements__storage_offset) _20;
>
>so the constant replacement is done for right.3_19 by the above block.
>
>> But then if any constant propagation is ok at -O0 why not perform
>> full-fledged constant propagation (with !DECL_IGNORED_P vars as a
>> propagation barrier) as a regular SSA pass?  That is, if you'd had a
>> Inline_Always function like
>> 
>> int foo (int i)
>> {
>>   return (i + 1) / i;
>> }
>> 
>> you'd not get the desired result as the i + 1 stmt wouldn't be folded
>> and thus the (i + 1) / i stmt wouldn't either.
>
>That's OK, only the trivial cases need to be dealt with since it's -O0
>so 
>running a fully-fledged constant propagation seems overkill.
>
>> That said - why does RTL optimization not save you here anyway?
>> After all, it is responsible for turning divisions into shifts.
>
>You mean the RTL expander?  Because the SSA name isn't replaced with
>the RHS 
>of its defining statement in:
>
>     /* For EXPAND_INITIALIZER try harder to get something simpler.  */
>      if (g == NULL
>	  && modifier == EXPAND_INITIALIZER
>	  && !SSA_NAME_IS_DEFAULT_DEF (exp)
>	  && (optimize || DECL_IGNORED_P (SSA_NAME_VAR (exp)))
>	  && stmt_is_replaceable_p (SSA_NAME_DEF_STMT (exp)))
>	g = SSA_NAME_DEF_STMT (exp);
>
>since modifier is EXPAND_NORMAL.  Do you think it would be OK to be a
>little 
>more aggressive here?  Something like:
>
>      /* If we aren't on the LHS, look into the defining statement.  */
>      if (g == NULL
>	  && modifier != EXPAND_WRITE
>	  && !SSA_NAME_IS_DEFAULT_DEF (exp)
>	  && (optimize || DECL_IGNORED_P (SSA_NAME_VAR (exp)))
>	  && stmt_is_replaceable_p (SSA_NAME_DEF_STMT (exp)))
>	 {
>	    g = SSA_NAME_DEF_STMT (exp);
>	    /* For EXPAND_INITIALIZER substitute in all cases, otherwise do
>	       it only for constants.  */
>	    if (modifier != EXPAND_INITIALIZER
>		&& (!gimple_assign_copy_p (g)
>		    || !is_gimple_min_invariant (gimple_assign_rhs1 (g))))
>	      g = NULL;
>	 }
>
>That's certainly sufficient here.

Yeah, I think that's a way better place for the hack.

Richard.

Re: [patch] Perform anonymous constant propagation during inlining

[Eric Botcazou]

> Yeah, I think that's a way better place for the hack.

OK, how aggressive then?  We could as well do the substitution for all copies:

      /* For EXPAND_INITIALIZER try harder to get something simpler.
	 Otherwise, substitute copies on the RHS, this can propagate
	 constants at -O0 and thus simplify arithmetic operations.  */
      if (g == NULL
	  && !SSA_NAME_IS_DEFAULT_DEF (exp)
	  && (optimize || DECL_IGNORED_P (SSA_NAME_VAR (exp)))
	  && (modifier == EXPAND_INITIALIZER
	      || (modifier != EXPAND_WRITE
		  && gimple_assign_copy_p (SSA_NAME_DEF_STMT (exp))))
	  && stmt_is_replaceable_p (SSA_NAME_DEF_STMT (exp)))
	g = SSA_NAME_DEF_STMT (exp);

-- 
Eric Botcazou

Re: [patch] Perform anonymous constant propagation during inlining

[Eric Botcazou]

[-- Attachment #1: Type: text/plain, Size: 1132 bytes --]

> OK, how aggressive then?  We could as well do the substitution for all
> copies:
> 
>       /* For EXPAND_INITIALIZER try harder to get something simpler.
> 	 Otherwise, substitute copies on the RHS, this can propagate
> 	 constants at -O0 and thus simplify arithmetic operations.  */
>       if (g == NULL
> 	  && !SSA_NAME_IS_DEFAULT_DEF (exp)
> 	  && (optimize || DECL_IGNORED_P (SSA_NAME_VAR (exp)))
> 	  && (modifier == EXPAND_INITIALIZER
> 
> 	      || (modifier != EXPAND_WRITE
> 
> 		  && gimple_assign_copy_p (SSA_NAME_DEF_STMT (exp))))
> 	  && stmt_is_replaceable_p (SSA_NAME_DEF_STMT (exp)))
> 	g = SSA_NAME_DEF_STMT (exp);

This doesn't work (this generates wrong code because this creates overlapping 
live ranges for SSA_NAMEs with the same base variable).  Here's the latest 
working version, all the predicates and accessors used are inlined.

Tested on x86_64-suse-linux, OK for the mainline?


2015-05-01  Eric Botcazou  <ebotcazou@adacore.com>

	* expr.c (expand_expr_real_1) <SSA_NAME>: Try to substitute constants
	on the RHS of expressions.
	* gimple-expr.h (is_gimple_constant): Reorder.


-- 
Eric Botcazou

[-- Attachment #2: p.diff --]
[-- Type: text/x-patch, Size: 1388 bytes --]

Index: expr.c
===================================================================
--- expr.c	(revision 222673)
+++ expr.c	(working copy)
@@ -9511,11 +9511,17 @@ expand_expr_real_1 (tree exp, rtx target
 	}
 
       g = get_gimple_for_ssa_name (exp);
-      /* For EXPAND_INITIALIZER try harder to get something simpler.  */
+      /* For EXPAND_INITIALIZER try harder to get something simpler.
+	 Otherwise, substitute constants on the RHS, this can make
+	 it possible to simplify arithmetic operations at -O0.  */
       if (g == NULL
-	  && modifier == EXPAND_INITIALIZER
 	  && !SSA_NAME_IS_DEFAULT_DEF (exp)
 	  && (optimize || DECL_IGNORED_P (SSA_NAME_VAR (exp)))
+	  && (modifier == EXPAND_INITIALIZER
+	      || (modifier != EXPAND_WRITE
+		  && gimple_assign_single_p (SSA_NAME_DEF_STMT (exp))
+		  && is_gimple_constant
+		     (gimple_assign_rhs1 (SSA_NAME_DEF_STMT (exp)))))
 	  && stmt_is_replaceable_p (SSA_NAME_DEF_STMT (exp)))
 	g = SSA_NAME_DEF_STMT (exp);
       if (g)
Index: gimple-expr.h
===================================================================
--- gimple-expr.h	(revision 222673)
+++ gimple-expr.h	(working copy)
@@ -136,9 +136,9 @@ is_gimple_constant (const_tree t)
     case INTEGER_CST:
     case REAL_CST:
     case FIXED_CST:
-    case STRING_CST:
     case COMPLEX_CST:
     case VECTOR_CST:
+    case STRING_CST:
       return true;
 
     default:

Re: [patch] Perform anonymous constant propagation during inlining

[Richard Biener]

On Fri, May 1, 2015 at 8:09 PM, Eric Botcazou <ebotcazou@adacore.com> wrote:
>> OK, how aggressive then?  We could as well do the substitution for all
>> copies:
>>
>>       /* For EXPAND_INITIALIZER try harder to get something simpler.
>>        Otherwise, substitute copies on the RHS, this can propagate
>>        constants at -O0 and thus simplify arithmetic operations.  */
>>       if (g == NULL
>>         && !SSA_NAME_IS_DEFAULT_DEF (exp)
>>         && (optimize || DECL_IGNORED_P (SSA_NAME_VAR (exp)))
>>         && (modifier == EXPAND_INITIALIZER
>>
>>             || (modifier != EXPAND_WRITE
>>
>>                 && gimple_assign_copy_p (SSA_NAME_DEF_STMT (exp))))
>>         && stmt_is_replaceable_p (SSA_NAME_DEF_STMT (exp)))
>>       g = SSA_NAME_DEF_STMT (exp);
>
> This doesn't work (this generates wrong code because this creates overlapping
> live ranges for SSA_NAMEs with the same base variable).  Here's the latest
> working version, all the predicates and accessors used are inlined.

Hum, the fact that your earlier version created wrong code
(get_gimple_for_ssa_name
already returned false here) points at some issues with
EXPAND_INITIALIZER as well, no...?

That said, the path you add is certainly safe (though maybe we want to change
get_gimple_for_ssa_name to return tcc_constant single-use defs even if
TER is disabled
(thus at -O0 - and only at -O0, otherwise it shouldn't happen).  That
would cover
more cases of get_gimple_for_ssa_name uses (I can see
optimize_bitfield_expansion
for example...)

So, your patch is ok for trunk unless you want to explore the
get_gimple_for_ssa_name
improvement suggestion.

I also wonder about EXPAND_INITIALIZER creating overlapping
life-ranges (or moving
loads across stores).

Thanks,
Richard.

> Tested on x86_64-suse-linux, OK for the mainline?
>
>
> 2015-05-01  Eric Botcazou  <ebotcazou@adacore.com>
>
>         * expr.c (expand_expr_real_1) <SSA_NAME>: Try to substitute constants
>         on the RHS of expressions.
>         * gimple-expr.h (is_gimple_constant): Reorder.
>
>
> --
> Eric Botcazou

Re: [patch] Perform anonymous constant propagation during inlining

[Eric Botcazou]

> Hum, the fact that your earlier version created wrong code
> (get_gimple_for_ssa_name
> already returned false here) points at some issues with
> EXPAND_INITIALIZER as well, no...?

Theoritically yes but, in practice, EXPAND_INITIALIZER is used in varasm.c and 
for debugging stuff only, so I don't think that's a real concern.

> That said, the path you add is certainly safe (though maybe we want to
> change get_gimple_for_ssa_name to return tcc_constant single-use defs even
> if TER is disabled
> (thus at -O0 - and only at -O0, otherwise it shouldn't happen).  That
> would cover
> more cases of get_gimple_for_ssa_name uses (I can see
> optimize_bitfield_expansion
> for example...)

optimize_bitfield_assignment_op is only interested in loads from bitfields 
though.  The get_gimple_for_ssa_name route would be interesting to bypass the 
stmt_is_replaceable_p test, i.e. to bypass the single-use test, but this could 
be counter-productive at -O0 so I'm not sure it's worth the trouble.

-- 
Eric Botcazou

Re: [patch] Perform anonymous constant propagation during inlining

[Eric Botcazou]

> 2015-05-01  Eric Botcazou  <ebotcazou@adacore.com>
> 
> 	* expr.c (expand_expr_real_1) <SSA_NAME>: Try to substitute constants
> 	on the RHS of expressions.
> 	* gimple-expr.h (is_gimple_constant): Reorder.

Bummer.  This breaks C++ debugging:

+FAIL: gdb.cp/class2.exp: print alpha at marker return 0
+FAIL: gdb.cp/class2.exp: print beta at marker return 0
+FAIL: gdb.cp/class2.exp: print * aap at marker return 0
+FAIL: gdb.cp/class2.exp: print * bbp at marker return 0
+FAIL: gdb.cp/class2.exp: print * abp at marker return 0, s-p-o off
+FAIL: gdb.cp/class2.exp: print * (B *) abp at marker return 0
+FAIL: gdb.cp/class2.exp: p acp
+FAIL: gdb.cp/class2.exp: p acp->c1
+FAIL: gdb.cp/class2.exp: p acp->c2

because C++ is apparently relying on the assignment to the anonymous return 
object to preserve the debug info attached to a return statement.

Would you be OK with a slight variation of your earlier idea, i.e. calling 
fold_stmt with a specific valueizer from fold_marked_statements instead of the 
implicit no_follow_ssa_edges in the inliner?  Something like:

tree
follow_anonymous_single_use_edges (tree val)
{
  if (TREE_CODE (val) == SSA_NAME
      && (!SSA_NAME_VAR (val) || DECL_IGNORED_P (SSA_NAME_VAR (var)))
      && has_single_use (val))
    return val
  return NULL_TREE;
}

-- 
Eric Botcazou

Re: [patch] Perform anonymous constant propagation during inlining

[Richard Biener]

On May 4, 2015 11:38:42 PM GMT+02:00, Eric Botcazou <ebotcazou@adacore.com> wrote:
>> 2015-05-01  Eric Botcazou  <ebotcazou@adacore.com>
>> 
>> 	* expr.c (expand_expr_real_1) <SSA_NAME>: Try to substitute
>constants
>> 	on the RHS of expressions.
>> 	* gimple-expr.h (is_gimple_constant): Reorder.
>
>Bummer.  This breaks C++ debugging:
>
>+FAIL: gdb.cp/class2.exp: print alpha at marker return 0
>+FAIL: gdb.cp/class2.exp: print beta at marker return 0
>+FAIL: gdb.cp/class2.exp: print * aap at marker return 0
>+FAIL: gdb.cp/class2.exp: print * bbp at marker return 0
>+FAIL: gdb.cp/class2.exp: print * abp at marker return 0, s-p-o off
>+FAIL: gdb.cp/class2.exp: print * (B *) abp at marker return 0
>+FAIL: gdb.cp/class2.exp: p acp
>+FAIL: gdb.cp/class2.exp: p acp->c1
>+FAIL: gdb.cp/class2.exp: p acp->c2
>
>because C++ is apparently relying on the assignment to the anonymous
>return 
>object to preserve the debug info attached to a return statement.
>
>Would you be OK with a slight variation of your earlier idea, i.e.
>calling 
>fold_stmt with a specific valueizer from fold_marked_statements instead
>of the 
>implicit no_follow_ssa_edges in the inliner?  Something like:
>
>tree
>follow_anonymous_single_use_edges (tree val)
>{
>  if (TREE_CODE (val) == SSA_NAME
>      && (!SSA_NAME_VAR (val) || DECL_IGNORED_P (SSA_NAME_VAR (var)))
>      && has_single_use (val))
>    return val
>  return NULL_TREE;
>}

Yes, that works for me as well.

Richard.

Re: [patch] Perform anonymous constant propagation during inlining

[Eric Botcazou]

[-- Attachment #1: Type: text/plain, Size: 1465 bytes --]

> >Would you be OK with a slight variation of your earlier idea, i.e.
> >calling fold_stmt with a specific valueizer from fold_marked_statements
> >instead of the implicit no_follow_ssa_edges in the inliner?  Something
> >like:
> >
> >tree
> >follow_anonymous_single_use_edges (tree val)
> >{
> >
> >  if (TREE_CODE (val) == SSA_NAME
> >  
> >      && (!SSA_NAME_VAR (val) || DECL_IGNORED_P (SSA_NAME_VAR
> >      (var)))
> >      && has_single_use (val))
> >    
> >    return val
> >  
> >  return NULL_TREE;
> >
> >}
> 
> Yes, that works for me as well.

But not for GCC. :-)  The propagation per se works but, since the statement is 
not folded in the end, no replacement is made at all...

So we're back to square one and anonymous constant propagation seems to be the 
only way out at -O0.  The attached patch implements it in a less hackish way 
(and enables it unconditionally when optimizing as suggested by Jan) by doing 
it just before invoking fold_stmt on the marked statements so this should make 
folding more effective in the process. 

Tested (compiler only) on x86_64-suse-linux, OK for the mainline?


2015-05-11  Eric Botcazou  <ebotcazou@adacore.com>

	* tree-inline.c: Include tree-ssa-propagate.h.
	(replace_constant_uses_in): New function.
	(fold_marked_statements): Call it before folding the statement.

	* gimple-expr.h (is_gimple_constant): Reorder.
	* tree-ssa-propagate.c (before_dom_children): Use inline accessor.


-- 
Eric Botcazou

[-- Attachment #2: p.diff --]
[-- Type: text/x-patch, Size: 3854 bytes --]

Index: tree-ssa-propagate.c
===================================================================
--- tree-ssa-propagate.c	(revision 222673)
+++ tree-ssa-propagate.c	(working copy)
@@ -1246,9 +1246,7 @@ substitute_and_fold_dom_walker::before_d
 	      && gimple_call_noreturn_p (stmt))
 	    stmts_to_fixup.safe_push (stmt);
 
-	  if (is_gimple_assign (stmt)
-	      && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
-		  == GIMPLE_SINGLE_RHS))
+	  if (gimple_assign_single_p (stmt))
 	    {
 	      tree rhs = gimple_assign_rhs1 (stmt);
 
Index: tree-inline.c
===================================================================
--- tree-inline.c	(revision 222673)
+++ tree-inline.c	(working copy)
@@ -82,6 +82,7 @@ along with GCC; see the file COPYING3.
 #include "expr.h"
 #include "tree-dfa.h"
 #include "tree-ssa.h"
+#include "tree-ssa-propagate.h"
 #include "tree-pretty-print.h"
 #include "except.h"
 #include "debug.h"
@@ -4801,6 +4802,54 @@ gimple_expand_calls_inline (basic_block
   return inlined;
 }
 
+/* Replace USE references in statement STMT with constant values.  Return
+   true if at least one reference was replaced.
+
+   We do it at -O0 for anonymous SSA names or SSA names of anonymous decls,
+   this makes it possible to generate reasonable code for operators that are
+   implemented as functions and inlined on constants.  */
+
+static bool
+replace_constant_uses_in (gimple stmt)
+{
+  bool replaced = false;
+  use_operand_p use;
+  ssa_op_iter iter;
+
+  FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
+    {
+      tree tuse = USE_FROM_PTR (use);
+
+      if (TREE_CODE (tuse) != SSA_NAME || SSA_NAME_IS_DEFAULT_DEF (tuse))
+	continue;
+
+      if (!optimize
+	  && SSA_NAME_VAR (tuse)
+	  && !DECL_IGNORED_P (SSA_NAME_VAR (tuse)))
+	continue;
+
+      if (!gimple_assign_single_p (SSA_NAME_DEF_STMT (tuse)))
+	continue;
+
+      tree rhs = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (tuse));
+      if (!is_gimple_constant (rhs))
+	continue;
+
+      propagate_value (use, rhs);
+
+      replaced = true;
+    }
+
+  if (replaced && gimple_assign_single_p (stmt))
+    {
+      tree rhs = gimple_assign_rhs1 (stmt);
+
+      if (TREE_CODE (rhs) == ADDR_EXPR)
+	recompute_tree_invariant_for_addr_expr (rhs);
+    }
+
+  return replaced;
+}
 
 /* Walk all basic blocks created after FIRST and try to fold every statement
    in the STATEMENTS pointer set.  */
@@ -4819,7 +4868,10 @@ fold_marked_statements (int first, hash_
 	  if (statements->contains (gsi_stmt (gsi)))
 	    {
 	      gimple old_stmt = gsi_stmt (gsi);
-	      tree old_decl = is_gimple_call (old_stmt) ? gimple_call_fndecl (old_stmt) : 0;
+	      tree old_decl
+		= is_gimple_call (old_stmt)
+		  ? gimple_call_fndecl (old_stmt) : NULL_TREE;
+	      bool replaced = replace_constant_uses_in (old_stmt);
 
 	      if (old_decl && DECL_BUILT_IN (old_decl))
 		{
@@ -4827,7 +4879,7 @@ fold_marked_statements (int first, hash_
 		     we need to look at all of them.  */
 		  gimple_stmt_iterator i2 = gsi;
 		  gsi_prev (&i2);
-		  if (fold_stmt (&gsi))
+		  if (fold_stmt (&gsi) || replaced)
 		    {
 		      gimple new_stmt;
 		      /* If a builtin at the end of a bb folded into nothing,
@@ -4871,7 +4923,7 @@ fold_marked_statements (int first, hash_
 			}
 		    }
 		}
-	      else if (fold_stmt (&gsi))
+	      else if (fold_stmt (&gsi) || replaced)
 		{
 		  /* Re-read the statement from GSI as fold_stmt() may
 		     have changed it.  */
Index: gimple-expr.h
===================================================================
--- gimple-expr.h	(revision 222673)
+++ gimple-expr.h	(working copy)
@@ -136,9 +136,9 @@ is_gimple_constant (const_tree t)
     case INTEGER_CST:
     case REAL_CST:
     case FIXED_CST:
-    case STRING_CST:
     case COMPLEX_CST:
     case VECTOR_CST:
+    case STRING_CST:
       return true;
 
     default:

Re: [patch] Perform anonymous constant propagation during inlining

[Richard Biener]

On Mon, May 11, 2015 at 4:05 PM, Eric Botcazou <ebotcazou@adacore.com> wrote:
>> >Would you be OK with a slight variation of your earlier idea, i.e.
>> >calling fold_stmt with a specific valueizer from fold_marked_statements
>> >instead of the implicit no_follow_ssa_edges in the inliner?  Something
>> >like:
>> >
>> >tree
>> >follow_anonymous_single_use_edges (tree val)
>> >{
>> >
>> >  if (TREE_CODE (val) == SSA_NAME
>> >
>> >      && (!SSA_NAME_VAR (val) || DECL_IGNORED_P (SSA_NAME_VAR
>> >      (var)))
>> >      && has_single_use (val))
>> >
>> >    return val
>> >
>> >  return NULL_TREE;
>> >
>> >}
>>
>> Yes, that works for me as well.
>
> But not for GCC. :-)  The propagation per se works but, since the statement is
> not folded in the end, no replacement is made at all...
>
> So we're back to square one and anonymous constant propagation seems to be the
> only way out at -O0.  The attached patch implements it in a less hackish way
> (and enables it unconditionally when optimizing as suggested by Jan) by doing
> it just before invoking fold_stmt on the marked statements so this should make
> folding more effective in the process.
>
> Tested (compiler only) on x86_64-suse-linux, OK for the mainline?

+  if (replaced && gimple_assign_single_p (stmt))
+    {
+      tree rhs = gimple_assign_rhs1 (stmt);
+
+      if (TREE_CODE (rhs) == ADDR_EXPR)
+       recompute_tree_invariant_for_addr_expr (rhs);
+    }

this needs to handle all non-PHI stmt kinds (asms and calls), see
tree-cfg.c:replace_uses_by
(maybe factor out a recompute_tree_invariant_for_gimple_ops).

Looking at the whole thing I think it might be better to

 a) _not_ propagate parameter values during the stmt copies
 b) _not_ mark any stmts for folding
 c) at fold_marked_stmts time instead treat the incoming parameter
     mappings (which param setup "inlined" as param_1 = value1; etc...)
     as a seed for the worklist of a simple SSA propagator doing sth like

 while (!bitmap_empty (worklist))
   {
     tree name = ssa_name (bitmap_first_bit (worklist));
     gimple stmt = SSA_NAME_DEF_STMT (name);
     gcc_assert (gimple_assign_single_p (stmt)
                   && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)));
     FOR_EACH_IMM_USE_STMT (name)
        {
         FOR_EACH_IMM_USE_ON_STMT (..)
            SET_USE (...)
         fold_stmt (use_stmt);
           if (gimple_assing_single_p (use_stmt)
               && is_gimple_min_invariant (gimple_assign_rhs1 (use_stmt)))
            bitmap_set_bit (worklist, SSA_NAME_VERSION
(gimple_assign_lhs (use_stmt)));
        }
     bitmap_clear_bit (SSA_NAME_VERSION (name));
     /* remove 'stmt' if we replaced all uses - properly generating
debug stmts  */
   }

appropriately restricted for !optimize and eventually also propagating
copies for !optimize.

This should make sure we keep all stmts properly folded after inlining
and it should more
reliably propagate constants exposed by inlining (it should be cheaper
than a full SSA CCP
pass because we likely visit less stmts by just taking constant
parameters as propagation
sources).

Richard.

>
> 2015-05-11  Eric Botcazou  <ebotcazou@adacore.com>
>
>         * tree-inline.c: Include tree-ssa-propagate.h.
>         (replace_constant_uses_in): New function.
>         (fold_marked_statements): Call it before folding the statement.
>
>         * gimple-expr.h (is_gimple_constant): Reorder.
>         * tree-ssa-propagate.c (before_dom_children): Use inline accessor.
>
>
> --
> Eric Botcazou