Let tree-ssa-sink also sink pure calls

Hello,

As-is, tree-ssa-sink.c can only sink GIMPLE_ASSIGN statements. This
patch lets tree-ssa-sink.c sink pure calls also.

This allows the pass to sink the call to use in the following test
case (new test case, ssa-sink-10.c to be):

---------------------- 8< ----------------
/* { dg-do compile } */
/* { dg-options "-O -fdump-tree-sink" } */

__attribute__((__noinline__,__noclone__,__pure__,__const__))
int use (int b)
{
  return b * 2 + 4;
}

int foo (int b, int c, int d)
{
  int res, r = 0;
  res = use (b);
  if (c)
    r = res;
  return r;
}

/* use(b) should be sunk below the if(c).  */
/* { dg-final { scan-tree-dump-times "Sinking.*use" 1 "sink" } } */
/* { dg-final { cleanup-tree-dump "sink" } } */
---------------------- 8< ----------------

so that the optimized code (.092t.sink dump) looks like this:

;; Function foo (foo, funcdef_no=1, decl_uid=2008, cgraph_uid=1)
...
Sinking r_3 = use (b_2(D));
 from bb 2 to bb 3
foo (int b, int c, int d)
{
  int r;
  <bb 2>:
  if (c_4(D) != 0)
    goto <bb 3>;
  else
    goto <bb 5>;
  <bb 5>:
  goto <bb 4>;
  <bb 3>:
  r_3 = use (b_2(D));
  <bb 4>:
  # r_1 = PHI <0(5), r_3(3)>
  return r_1;

}

The patch allows the sinking of a number of functions in GCC itself
(mostly simple predicates e.g. from gimple.h) to be sunk in an LTO
bootstrap.

The patch is a bit larger than necessary because I cleaned up the
comments a bit. The only real changes are these three bits:

   /* We only can sink assignments.  */
-  if (!is_gimple_assign (stmt))
+  stmt_lhs = gimple_get_lhs (stmt);
+  if (stmt_lhs == NULL_TREE)
     return false;

and

-         && TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt))) == BLKmode))
+         && TYPE_MODE (TREE_TYPE (stmt_lhs)) == BLKmode))

and

-             && operand_equal_p (gimple_assign_lhs (stmt),
-                                 gimple_assign_lhs (use_stmt), 0))
+             && operand_equal_p (stmt_lhs, gimple_assign_lhs (use_stmt), 0))
            continue;

Bootstrapped&tested on powerpc64-unknown-linux-gnu.
OK for GCC 4.9 stage1?

Ciao!
Steven


gcc/
        * tree-ssa-sink.c (statement_sink_location): Handle pure calls.

testsuite/
        * gcc.dg/tree-ssa/ssa-sink-10.c: New test.

On Mon, 7 Jan 2013, Steven Bosscher wrote:

> Hello,
> 
> As-is, tree-ssa-sink.c can only sink GIMPLE_ASSIGN statements. This
> patch lets tree-ssa-sink.c sink pure calls also.
> 
> This allows the pass to sink the call to use in the following test
> case (new test case, ssa-sink-10.c to be):
> 
> ---------------------- 8< ----------------
> /* { dg-do compile } */
> /* { dg-options "-O -fdump-tree-sink" } */
> 
> __attribute__((__noinline__,__noclone__,__pure__,__const__))
> int use (int b)
> {
>   return b * 2 + 4;
> }
> 
> int foo (int b, int c, int d)
> {
>   int res, r = 0;
>   res = use (b);
>   if (c)
>     r = res;
>   return r;
> }
> 
> /* use(b) should be sunk below the if(c).  */
> /* { dg-final { scan-tree-dump-times "Sinking.*use" 1 "sink" } } */
> /* { dg-final { cleanup-tree-dump "sink" } } */
> ---------------------- 8< ----------------
> 
> so that the optimized code (.092t.sink dump) looks like this:
> 
> ;; Function foo (foo, funcdef_no=1, decl_uid=2008, cgraph_uid=1)
> ...
> Sinking r_3 = use (b_2(D));
>  from bb 2 to bb 3
> foo (int b, int c, int d)
> {
>   int r;
>   <bb 2>:
>   if (c_4(D) != 0)
>     goto <bb 3>;
>   else
>     goto <bb 5>;
>   <bb 5>:
>   goto <bb 4>;
>   <bb 3>:
>   r_3 = use (b_2(D));
>   <bb 4>:
>   # r_1 = PHI <0(5), r_3(3)>
>   return r_1;
> 
> }
> 
> The patch allows the sinking of a number of functions in GCC itself
> (mostly simple predicates e.g. from gimple.h) to be sunk in an LTO
> bootstrap.
> 
> The patch is a bit larger than necessary because I cleaned up the
> comments a bit. The only real changes are these three bits:
> 
>    /* We only can sink assignments.  */
> -  if (!is_gimple_assign (stmt))
> +  stmt_lhs = gimple_get_lhs (stmt);
> +  if (stmt_lhs == NULL_TREE)
>      return false;
> 
> and
> 
> -         && TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt))) == BLKmode))
> +         && TYPE_MODE (TREE_TYPE (stmt_lhs)) == BLKmode))
> 
> and
> 
> -             && operand_equal_p (gimple_assign_lhs (stmt),
> -                                 gimple_assign_lhs (use_stmt), 0))
> +             && operand_equal_p (stmt_lhs, gimple_assign_lhs (use_stmt), 0))
>             continue;
> 
> Bootstrapped&tested on powerpc64-unknown-linux-gnu.
> OK for GCC 4.9 stage1?

Comments below

> Ciao!
> Steven
> 
> 
> gcc/
>         * tree-ssa-sink.c (statement_sink_location): Handle pure calls.
> 
> testsuite/
>         * gcc.dg/tree-ssa/ssa-sink-10.c: New test.
> 
> Index: tree-ssa-sink.c
> ===================================================================
> --- tree-ssa-sink.c     (revision 194924)
> +++ tree-ssa-sink.c     (working copy)
> @@ -264,56 +264,48 @@ statement_sink_location (gimple stmt, basic_block
>    def_operand_p def_p;
>    ssa_op_iter iter;
>    imm_use_iterator imm_iter;
> +  tree stmt_lhs;
> 
>    /* We only can sink assignments.  */
> -  if (!is_gimple_assign (stmt))
> +  stmt_lhs = gimple_get_lhs (stmt);
> +  if (stmt_lhs == NULL_TREE)
>      return false;

Instead of this ...

> -  /* We only can sink stmts with a single definition.  */
> +  /* We only can sink stmts with a single definition.
> +     We don't want to sink dead code, so anything with 0 immediate uses
> +     is not sunk.  */
>    def_p = single_ssa_def_operand (stmt, SSA_OP_ALL_DEFS);
> -  if (def_p == NULL_DEF_OPERAND_P)
> +  if (def_p == NULL_DEF_OPERAND_P
> +      || has_zero_uses (DEF_FROM_PTR (def_p)))
>      return false;

... do

     stmt_lhs = DEF_FROM_PTR (def_p);

which then also handles sinking single-def GIMPLE_ASMs ;)

> -  /* Return if there are no immediate uses of this stmt.  */
> -  if (has_zero_uses (DEF_FROM_PTR (def_p)))
> -    return false;
> -
>    /* There are a few classes of things we can't or don't move, some because we
>       don't have code to handle it, some because it's not profitable and some
> -     because it's not legal.
> +     because it's not legal.  */
> 
> -     We can't sink things that may be global stores, at least not without
> -     calculating a lot more information, because we may cause it to no longer
> -     be seen by an external routine that needs it depending on where it gets
> -     moved to.
> -
> -     We don't want to sink loads from memory.
> -
> -     We can't sink statements that end basic blocks without splitting the
> -     incoming edge for the sink location to place it there.
> -
> -     We can't sink statements that have volatile operands.
> -
> -     We don't want to sink dead code, so anything with 0 immediate uses is not
> -     sunk.
> -
> -     Don't sink BLKmode assignments if current function has any local explicit
> -     register variables, as BLKmode assignments may involve memcpy or memset
> -     calls or, on some targets, inline expansion thereof that sometimes need
> -     to use specific hard registers.
> -
> -  */
> -  if (stmt_ends_bb_p (stmt)
> +  if (/* We can't sink statements that end basic blocks without splitting
> +        the incoming edge for the sink location to place it there.  */
> +      stmt_ends_bb_p (stmt)
> +      /* We can't sink statements with side effects, e.g. statements that
> +        have volatile operands, or non-pure calls.  */
>        || gimple_has_side_effects (stmt)
> -      || gimple_has_volatile_ops (stmt)
> +      /* We don't want to sink loads from memory.
> +        We can't sink things that may be global stores, at least not
> +        without calculating a lot more information, because we may cause
> +        it to no longer be seen by an external routine that needs it
> +        depending on where it gets moved to.  */
>        || (gimple_vuse (stmt) && !gimple_vdef (stmt))
> +      /* Don't sink BLKmode assignments if current function has any local
> +        explicit register variables, as BLKmode assignments may involve
> +        memcpy or memset calls or, on some targets, inline expansion
> +        thereof that sometimes need to use specific hard registers.  */
>        || (cfun->has_local_explicit_reg_vars
> -         && TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt))) == BLKmode))
> +         && TYPE_MODE (TREE_TYPE (stmt_lhs)) == BLKmode))
>      return false;
> 
> +  /* We can't sink across abnormal PHIs.  */
>    if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (DEF_FROM_PTR (def_p)))
>      return false;
> -
>    FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
>      {
>        tree use = USE_FROM_PTR (use_p);
> @@ -334,8 +326,7 @@ statement_sink_location (gimple stmt, basic_block
>           /* A killing definition is not a use.  */
>           if (gimple_assign_single_p (use_stmt)
>               && gimple_vdef (use_stmt)
> -             && operand_equal_p (gimple_assign_lhs (stmt),
> -                                 gimple_assign_lhs (use_stmt), 0))
> +             && operand_equal_p (stmt_lhs, gimple_assign_lhs (use_stmt), 0))

I suppose this also needs to handle

  stmt_lhs = call ();

or the equivalent asm.  Without handling asms thus adjust it to
gimple_get_lhs as you did above, with handling asms instead use
walk_stmt_load_store_addr_ops to walk all stores in the stmt.

Thanks,
Richard.