Optimize n?rotate(x,n):x

On Mon, 3 Mar 2014, Richard Biener wrote:

> On Sat, Mar 1, 2014 at 3:33 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
>> Hello,
>>
>> again, a stage 1 patch that I will ping then, but early comments are
>> welcome.
>>
>> PR 59100 was asking to transform n?rotate(x,n):x to rotate(x,n) (because it
>> can be hard to write a strictly valid rotate in plain C). The operation is
>> really:
>> (x != neutral) ? x op y : y
>> where neutral is such that (neutral op y) is always y, so that's what I
>> implemented (and absorbing elements while I was at it).
>>
>> For some operations on some platforms, the transformation may not be such a
>> good idea, in particular if division is very slow and b is 1 most of the
>> time, then computing a/b may be slower than (b!=1)?a/b:a. The easiest might
>> be to comment out those operations in the switch for now. I think divisions
>> are the only ones slow enough to deserve this, though there certainly are
>> CPUs where multiplication is not so fast, and even for rotate it may not
>> always be a win if the processor doesn't have a rotate instruction and the
>> shift amount is almost always 0.
>
> You only handle integer operations, so checking for INTEGER_TYPE_P
> early on would make sense.

Ah, I wasn't planning on restricting this to integers but yes, indeed, 
since it ended up that way...

> Note that some archs may dispatch to libgcc for integer operations
> so it may make sense to check whether that is the case (you can
> query optabs to check that) - if the comparison also dispatches to
> libgcc then of course the transform would be a win again.

Ok. I am not sure about using cbranch_optab, other ideas for the 
comparison?

> Even on x86 TImode division uses libgcc.

This reminds me of PR 58897 (unrelated).

> Note also that value-profiling may have created this special case in the 
> first place! (gimple_divmod_fixed_value_transform)

Test coverage must be limited if I didn't break the testsuite :-(

value-profiling seems to set edge probabilities when it does the 
transformation, so I am checking only that.

> Otherwise I think this is a good transform.  Did you check if it triggers
> during GCC bootstrap?

It does, a few times. Java has the obvious:

     int padLength = blockSize;
     if (length % blockSize != 0)
       padLength = blockSize - length % blockSize;

sched-deps.c has (I didn't check if it was actually this piece of code 
that triggered or another one in the same file):

       if ((ds1 & t) && !(ds2 & t))
         ds |= ds1 & t;
       else if (!(ds1 & t) && (ds2 & t))
         ds |= ds2 & t;

and we end up seeing (phiopt3) if(a!=0)ds|=a.

And mostly bitmap.h where we see quite a bit of:

   if (_867 != 0)
     goto <bb 55>;
   else
     goto <bb 56>;

   <bb 55>:
   start_bit_869 = _867 * 128;

   <bb 56>:
   # start_bit_870 = PHI <0(54), start_bit_869(55)>


Bootstrap+testsuite on x86_64-linux-gnu (modulo a minor reformatting, I'm 
retesting anyway).

2014-04-14  Marc Glisse  <marc.glisse@inria.fr>

 	PR tree-optimization/59100
gcc/
 	* tree-ssa-phiopt.c (neutral_element_p, absorbing_element_p,
 	is_cheap_stmt): New functions.
 	(value_replacement): Handle conditional binary operations with a
 	neutral or absorbing element.
gcc/testsuite/
 	* gcc.dg/tree-ssa/phi-opt-12.c: New file.
 	* gcc.dg/tree-ssa/phi-opt-13.c: Likewise.

On Sun, Apr 13, 2014 at 10:58 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
> On Mon, 3 Mar 2014, Richard Biener wrote:
>
>> On Sat, Mar 1, 2014 at 3:33 PM, Marc Glisse <marc.glisse@inria.fr> wrote:
>>>
>>> Hello,
>>>
>>> again, a stage 1 patch that I will ping then, but early comments are
>>> welcome.
>>>
>>> PR 59100 was asking to transform n?rotate(x,n):x to rotate(x,n) (because
>>> it
>>> can be hard to write a strictly valid rotate in plain C). The operation
>>> is
>>> really:
>>> (x != neutral) ? x op y : y
>>> where neutral is such that (neutral op y) is always y, so that's what I
>>> implemented (and absorbing elements while I was at it).
>>>
>>> For some operations on some platforms, the transformation may not be such
>>> a
>>> good idea, in particular if division is very slow and b is 1 most of the
>>> time, then computing a/b may be slower than (b!=1)?a/b:a. The easiest
>>> might
>>> be to comment out those operations in the switch for now. I think
>>> divisions
>>> are the only ones slow enough to deserve this, though there certainly are
>>> CPUs where multiplication is not so fast, and even for rotate it may not
>>> always be a win if the processor doesn't have a rotate instruction and
>>> the
>>> shift amount is almost always 0.
>>
>>
>> You only handle integer operations, so checking for INTEGER_TYPE_P
>> early on would make sense.
>
>
> Ah, I wasn't planning on restricting this to integers but yes, indeed, since
> it ended up that way...
>
>
>> Note that some archs may dispatch to libgcc for integer operations
>> so it may make sense to check whether that is the case (you can
>> query optabs to check that) - if the comparison also dispatches to
>> libgcc then of course the transform would be a win again.
>
>
> Ok. I am not sure about using cbranch_optab, other ideas for the comparison?
>
>
>> Even on x86 TImode division uses libgcc.
>
>
> This reminds me of PR 58897 (unrelated).
>
>
>> Note also that value-profiling may have created this special case in the
>> first place! (gimple_divmod_fixed_value_transform)
>
>
> Test coverage must be limited if I didn't break the testsuite :-(
>
> value-profiling seems to set edge probabilities when it does the
> transformation, so I am checking only that.
>
>
>> Otherwise I think this is a good transform.  Did you check if it triggers
>> during GCC bootstrap?
>
>
> It does, a few times. Java has the obvious:
>
>     int padLength = blockSize;
>     if (length % blockSize != 0)
>       padLength = blockSize - length % blockSize;
>
> sched-deps.c has (I didn't check if it was actually this piece of code that
> triggered or another one in the same file):
>
>       if ((ds1 & t) && !(ds2 & t))
>         ds |= ds1 & t;
>       else if (!(ds1 & t) && (ds2 & t))
>         ds |= ds2 & t;
>
> and we end up seeing (phiopt3) if(a!=0)ds|=a.
>
> And mostly bitmap.h where we see quite a bit of:
>
>   if (_867 != 0)
>     goto <bb 55>;
>   else
>     goto <bb 56>;
>
>   <bb 55>:
>   start_bit_869 = _867 * 128;
>
>   <bb 56>:
>   # start_bit_870 = PHI <0(54), start_bit_869(55)>
>
>
> Bootstrap+testsuite on x86_64-linux-gnu (modulo a minor reformatting, I'm
> retesting anyway).

Few comments below

> 2014-04-14  Marc Glisse  <marc.glisse@inria.fr>
>
>         PR tree-optimization/59100
> gcc/
>         * tree-ssa-phiopt.c (neutral_element_p, absorbing_element_p,
>         is_cheap_stmt): New functions.
>
>         (value_replacement): Handle conditional binary operations with a
>         neutral or absorbing element.
> gcc/testsuite/
>         * gcc.dg/tree-ssa/phi-opt-12.c: New file.
>         * gcc.dg/tree-ssa/phi-opt-13.c: Likewise.
>
> --
> Marc Glisse
> Index: gcc/testsuite/gcc.dg/tree-ssa/phi-opt-12.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/tree-ssa/phi-opt-12.c  (revision 0)
> +++ gcc/testsuite/gcc.dg/tree-ssa/phi-opt-12.c  (working copy)
> @@ -0,0 +1,23 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O -fdump-tree-phiopt1" } */
> +
> +int f(int a, int b, int c) {
> +  if (c > 5) return c;
> +  if (a == 0) return b;
> +  return a + b;
> +}
> +
> +unsigned rot(unsigned x, int n) {
> +  const int bits = __CHAR_BIT__ * __SIZEOF_INT__;
> +  return (n == 0) ? x : ((x << n) | (x >> (bits - n)));
> +}
> +
> +unsigned m(unsigned a, unsigned b) {
> +  if (a == 0)
> +    return 0;
> +  else
> +    return a & b;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "goto" 2 "phiopt1" } } */
> +/* { dg-final { cleanup-tree-dump "phiopt1" } } */
>
> Property changes on: gcc/testsuite/gcc.dg/tree-ssa/phi-opt-12.c
> ___________________________________________________________________
> Added: svn:keywords
> ## -0,0 +1 ##
> +Author Date Id Revision URL
> \ No newline at end of property
> Added: svn:eol-style
> ## -0,0 +1 ##
> +native
> \ No newline at end of property

Try to avoid this

> Index: gcc/testsuite/gcc.dg/tree-ssa/phi-opt-13.c
> ===================================================================
> --- gcc/testsuite/gcc.dg/tree-ssa/phi-opt-13.c  (revision 0)
> +++ gcc/testsuite/gcc.dg/tree-ssa/phi-opt-13.c  (working copy)
> @@ -0,0 +1,19 @@
> +/* { dg-do compile { target x86_64-*-* } } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +int f(int a, int b) {
> +  if (__builtin_expect(a == 0, 1)) return b;
> +  return a + b;
> +}
> +
> +// optab_handler can handle if(b==1) but not a/b
> +// so we consider a/b too expensive.
> +unsigned __int128 g(unsigned __int128 a, unsigned __int128 b) {
> +  if (b == 1)
> +    return a;
> +  else
> +    return a / b;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "goto " 4 "optimized" } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
>
> Property changes on: gcc/testsuite/gcc.dg/tree-ssa/phi-opt-13.c
> ___________________________________________________________________
> Added: svn:keywords
> ## -0,0 +1 ##
> +Author Date Id Revision URL
> \ No newline at end of property
> Added: svn:eol-style
> ## -0,0 +1 ##
> +native
> \ No newline at end of property
> Index: gcc/tree-ssa-phiopt.c
> ===================================================================
> --- gcc/tree-ssa-phiopt.c       (revision 209347)
> +++ gcc/tree-ssa-phiopt.c       (working copy)
> @@ -140,20 +140,37 @@ static bool gate_hoist_loads (void);
>         x = PHI (CONST, a)
>
>     Gets replaced with:
>       bb0:
>       bb2:
>         t1 = a == CONST;
>         t2 = b > c;
>         t3 = t1 & t2;
>         x = a;
>
> +
> +   It also replaces
> +
> +     bb0:
> +       if (a != 0) goto bb1; else goto bb2;
> +     bb1:
> +       c = a + b;
> +     bb2:
> +       x = PHI <c (bb1), b (bb0), ...>;
> +
> +   with
> +
> +     bb0:
> +       c = a + b;
> +     bb2:
> +       x = PHI <c (bb0), ...>;
> +
>     ABS Replacement
>     ---------------
>
>     This transformation, implemented in abs_replacement, replaces
>
>       bb0:
>         if (a >= 0) goto bb2; else goto bb1;
>       bb1:
>         x = -a;
>       bb2:
> @@ -809,20 +826,104 @@ operand_equal_for_value_replacement (con
>    if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp))
>      return true;
>
>    tmp = gimple_assign_rhs2 (def);
>    if (rhs_is_fed_for_value_replacement (arg0, arg1, code, tmp))
>      return true;
>
>    return false;
>  }
>
> +/* Returns true if ARG is a neutral element for operation CODE
> +   on the RIGHT side.  */
> +
> +static bool
> +neutral_element_p (tree_code code, tree arg, bool right)
> +{
> +  switch (code)
> +    {
> +    case PLUS_EXPR:
> +    case BIT_IOR_EXPR:
> +    case BIT_XOR_EXPR:
> +      return integer_zerop (arg);
> +
> +    case LROTATE_EXPR:
> +    case RROTATE_EXPR:
> +    case LSHIFT_EXPR:
> +    case RSHIFT_EXPR:
> +    case MINUS_EXPR:
> +    case POINTER_PLUS_EXPR:
> +      return right && integer_zerop (arg);
> +
> +    case MULT_EXPR:
> +      return integer_onep (arg);
> +
> +    // Are those too expensive? Should we check edge probabilities?

Comment obsolete now

> +    case TRUNC_DIV_EXPR:
> +    case CEIL_DIV_EXPR:
> +    case FLOOR_DIV_EXPR:
> +    case ROUND_DIV_EXPR:
> +    case EXACT_DIV_EXPR:
> +      return right && integer_onep (arg);
> +
> +    case BIT_AND_EXPR:
> +      return integer_all_onesp (arg);
> +
> +    default:
> +      return false;
> +    }
> +}
> +
> +/* Returns true if ARG is an absorbing element for operation CODE.  */
> +
> +static bool
> +absorbing_element_p (tree_code code, tree arg)
> +{
> +  switch (code)
> +    {
> +    case BIT_IOR_EXPR:
> +      return integer_all_onesp (arg);
> +
> +    case MULT_EXPR:
> +    case BIT_AND_EXPR:
> +      return integer_zerop (arg);
> +
> +    default:
> +      return false;
> +    }
> +}
> +
> +/* Returns true if the statement is cheap. The simple heuristic used here
> +   is that anything the optab knows is cheap.  */
> +
> +static bool
> +is_cheap_stmt (gimple stmt)
> +{
> +  tree type;
> +  optab op;
> +  if (is_gimple_assign (stmt))
> +    {
> +      type = TREE_TYPE (gimple_assign_rhs1 (stmt));
> +      enum tree_code code = gimple_assign_rhs_code (stmt);
> +      op = optab_for_tree_code (code, type, optab_scalar);
> +    }
> +  else if (gimple_code (stmt) == GIMPLE_COND)
> +    {
> +      type = TREE_TYPE (gimple_cond_lhs (stmt));
> +      op = cbranch_optab;

Hum.  cmp_optab/ucmp_optab?  But it seems those are only used
to query libfunc names ...  Maybe try using can_compare_p instead
with ccp_jump, that looks like a suitable abstraction for is_cheap_stmt.

> +    }
> +  else
> +    gcc_unreachable ();
> +  return (op != unknown_optab
> +         && optab_handler (op, TYPE_MODE (type)) != CODE_FOR_nothing);
> +}
> +
>  /*  The function value_replacement does the main work of doing the value
>      replacement.  Return non-zero if the replacement is done.  Otherwise
> return
>      0.  If we remove the middle basic block, return 2.
>      BB is the basic block where the replacement is going to be done on.
> ARG0
>      is argument 0 from the PHI.  Likewise for ARG1.  */
>
>  static int
>  value_replacement (basic_block cond_bb, basic_block middle_bb,
>                    edge e0, edge e1, gimple phi,
>                    tree arg0, tree arg1)
> @@ -833,23 +934,21 @@ value_replacement (basic_block cond_bb,
>    enum tree_code code;
>    bool emtpy_or_with_defined_p = true;
>
>    /* If the type says honor signed zeros we cannot do this
>       optimization.  */
>    if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (arg1))))
>      return 0;
>
>    /* If there is a statement in MIDDLE_BB that defines one of the PHI
>       arguments, then adjust arg0 or arg1.  */
> -  gsi = gsi_after_labels (middle_bb);
> -  if (!gsi_end_p (gsi) && is_gimple_debug (gsi_stmt (gsi)))
> -    gsi_next_nondebug (&gsi);
> +  gsi = gsi_start_nondebug_after_labels_bb (middle_bb);
>    while (!gsi_end_p (gsi))
>      {
>        gimple stmt = gsi_stmt (gsi);
>        tree lhs;
>        gsi_next_nondebug (&gsi);
>        if (!is_gimple_assign (stmt))
>         {
>           emtpy_or_with_defined_p = false;
>           continue;
>         }
> @@ -931,20 +1030,66 @@ value_replacement (basic_block cond_bb,
>               print_generic_expr (dump_file, gimple_phi_result (phi), 0);
>               fprintf (dump_file, " reduced for COND_EXPR in block %d to ",
>                        cond_bb->index);
>               print_generic_expr (dump_file, arg, 0);
>               fprintf (dump_file, ".\n");
>              }
>            return 1;
>         }
>
>      }
> +
> +  /* Now optimize (x != 0) ? x + y : y to just y.
> +     The following condition is too restrictive, there can easily be
> another
> +     stmt in middle_bb, for instance a CONVERT_EXPR for the second
> argument.  */
> +  gimple assign = last_and_only_stmt (middle_bb);
> +  if (!assign || gimple_code (assign) != GIMPLE_ASSIGN
> +      || gimple_assign_rhs_class (assign) != GIMPLE_BINARY_RHS
> +      || !INTEGRAL_TYPE_P (TREE_TYPE (arg0)))

That will make POINTER_PLUS_EXPR unhandled (pointer arg0).
BIT_AND_EXPR also is valid for pointers (both arguments are pointer type).

> +    return 0;
> +
> +  /* assign may call a libgcc routine, which is slow.  */
> +  if (!is_cheap_stmt (assign) && is_cheap_stmt (cond))
> +    return 0;
> +
> +  /* If the special case has a high probability, keep it.  */
> +  if (EDGE_PRED (middle_bb, 0)->probability < PROB_EVEN)

I suppose Honza has a comment on how to test this properly
(not sure if ->probability or ->frequency is always initialized properly).
for example single_likely_edge tests profile_status_for_fn !=
PROFILE_ABSENT (and uses a fixed probability value ...).
Anyway, the comparison looks backwards to me, but maybe I'm
missing sth - I'd use >= PROB_LIKELY ;)

Otherwise the patch looks ok to me.

Thanks,
Richard.

> +    return 0;
> +
> +  tree lhs = gimple_assign_lhs (assign);
> +  tree rhs1 = gimple_assign_rhs1 (assign);
> +  tree rhs2 = gimple_assign_rhs2 (assign);
> +  enum tree_code code_def = gimple_assign_rhs_code (assign);
> +  tree cond_lhs = gimple_cond_lhs (cond);
> +  tree cond_rhs = gimple_cond_rhs (cond);
> +
> +  if (((code == NE_EXPR && e1 == false_edge)
> +       || (code == EQ_EXPR && e1 == true_edge))
> +      && arg0 == lhs
> +      && ((arg1 == rhs1
> +          && operand_equal_for_phi_arg_p (rhs2, cond_lhs)
> +          && neutral_element_p (code_def, cond_rhs, true))
> +         || (arg1 == rhs2
> +             && operand_equal_for_phi_arg_p (rhs1, cond_lhs)
> +             && neutral_element_p (code_def, cond_rhs, false))
> +         || (operand_equal_for_phi_arg_p (arg1, cond_rhs)
> +             && (operand_equal_for_phi_arg_p (rhs2, cond_lhs)
> +                 || operand_equal_for_phi_arg_p (rhs1, cond_lhs))
> +             && absorbing_element_p (code_def, cond_rhs))))
> +    {
> +      gsi = gsi_for_stmt (cond);
> +      gimple_stmt_iterator gsi_from = gsi_for_stmt (assign);
> +      gsi_move_before (&gsi_from, &gsi);
> +      replace_phi_edge_with_variable (cond_bb, e1, phi, lhs);
> +      return 2;
> +    }
> +
>    return 0;
>  }
>
>  /*  The function minmax_replacement does the main work of doing the minmax
>      replacement.  Return true if the replacement is done.  Otherwise return
>      false.
>      BB is the basic block where the replacement is going to be done on.
> ARG0
>      is argument 0 from the PHI.  Likewise for ARG1.  */
>
>  static bool
>