Changes for if-convert to recognize simple conditional reduction.

Changes for if-convert to recognize simple conditional reduction.

[Yuri Rumyantsev]

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

Hi All,

We implemented enhancement for if-convert phase to recognize the
simplest conditional reduction and to transform it vectorizable form,
e.g. statement
    if (A[i] != 0) num+= 1; will be recognized.
A new test-case is also provided.

Bootstrapping and regression testing did not show any new failures.

Is it OK for trunk?

gcc/ChangeLog:
2014-04-17  Yuri Rumyantsev  <ysrumyan@gmail.com>

* tree-if-conv.c (is_cond_scalar_reduction): New function.
(convert_scalar_cond_reduction): Likewise.
(predicate_scalar_phi): Add recognition and transformation
of simple conditioanl reduction to be vectorizable.

gcc/testsuite/ChangeLog:
2014-04-17  Yuri Rumyantsev  <ysrumyan@gmail.com>

* gcc.dg/cond-reduc.c: New test.

[-- Attachment #2: if-conv-cond-reduc.patch --]
[-- Type: application/octet-stream, Size: 5709 bytes --]

diff --git a/gcc/testsuite/gcc.dg/vect/cond-reduc.c b/gcc/testsuite/gcc.dg/vect/cond-reduc.c
new file mode 100755
index 0000000..981f6b0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/cond-reduc.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_int } */
+
+#define N 512
+int a[N];
+int foo()
+{
+  int i, res = 0;
+  for (i=0; i<N; i++)
+  {
+    if (a[i] != 0)
+      res += 1;
+  }
+  return res;
+}
+
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" } } */
+/* { dg-final { cleanup-tree-dump "vect" } } */
+
diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c
old mode 100644
new mode 100755
index 7ff2132..c33c406
--- a/gcc/tree-if-conv.c
+++ b/gcc/tree-if-conv.c
@@ -1386,6 +1386,125 @@ find_phi_replacement_condition (basic_block bb, tree *cond,
   return first_edge->src;
 }
 
+/* Returns true if def-stmt for phi argument ARG is simple increment/decrement
+   with constant which is in predicated basic block.
+   REDUC, OP0 and OP1 contain reduction stmt, its var and const
+   operands respectively.  */
+
+static bool
+is_cond_scalar_reduction (tree arg, gimple *reduc, tree *op0, tree *op1)
+{
+  tree lhs, r_op1, r_op2;
+  gimple stmt;
+  gimple use_stmt;
+  use_operand_p use;
+  basic_block bb;
+  enum tree_code reduction_op;
+
+  if (TREE_CODE (arg) != SSA_NAME)
+    return false;
+  stmt = SSA_NAME_DEF_STMT (arg);
+  if (gimple_code (stmt) != GIMPLE_ASSIGN)
+    return false;
+
+  /* Consider only conditional reduction.  */
+  bb = gimple_bb (stmt);
+  if (!bb_has_predicate (bb))
+    return false;
+  if (is_true_predicate (bb_predicate (bb)))
+    return false;
+
+  lhs = gimple_assign_lhs (stmt);
+  if (TREE_CODE (lhs) != SSA_NAME)
+    return false;
+  if (SSA_NAME_VAR (lhs) == NULL)
+    return false;
+  if (!single_imm_use (lhs, &use, &use_stmt))
+    return false;
+  if (gimple_code (use_stmt) != GIMPLE_PHI)
+    return false;
+
+  reduction_op = gimple_assign_rhs_code (stmt);
+  if (reduction_op != PLUS_EXPR && reduction_op != MINUS_EXPR)
+    return false;
+  r_op1 = gimple_assign_rhs1 (stmt);
+  r_op2 = gimple_assign_rhs2 (stmt);
+  if (reduction_op == PLUS_EXPR &&
+      TREE_CODE (r_op2) == SSA_NAME)
+    {
+      tree tmp = r_op2;
+      r_op2 = r_op1;
+      r_op1 = tmp;
+    }
+  if (gimple_code (SSA_NAME_DEF_STMT (r_op1)) != GIMPLE_PHI)
+    return false;
+  if (TREE_CODE (r_op2) != INTEGER_CST && TREE_CODE (r_op2) != REAL_CST)
+    return false;
+  /* Right operand is constant, check that left operand is equal to lhs.  */
+  if (SSA_NAME_VAR (lhs) !=  SSA_NAME_VAR (r_op1))
+    return false;
+  *op0 = r_op1; *op1 = r_op2;
+  *reduc = stmt;
+  return true;
+}
+
+/* Converts conditional scalar reduction into unconditional form, e.g.
+     bb_4
+       if (_5 != 0) goto bb_5 else goto bb_6
+     end_bb_4
+     bb_5
+       res_6 = res_13 + 1;
+     end_bb_5
+     bb_6
+       # res_2 = PHI <res_13(4), res_6(5)>
+     end_bb_6
+
+   will be converted into sequence
+    _ifc__1 = _5 != 0 ? 1 : 0;
+    res_2 = res_13 + _ifc__1;
+  Argument SWAP tells that arguments of conditional expression should be
+  swapped.
+  Returns rhs of resulting PHI assignment.  */
+
+static tree
+convert_scalar_cond_reduction (gimple reduc, gimple_stmt_iterator *gsi,
+			       tree cond, tree op0, tree op1, bool swap)
+{
+  gimple_stmt_iterator stmt_it;
+  gimple new_assign;
+  tree rhs;
+  tree rhs1 = gimple_assign_rhs1 (reduc);
+  tree tmp = make_temp_ssa_name (TREE_TYPE (rhs1), NULL, "_ifc_");
+  tree c;
+  tree zero = build_zero_cst (TREE_TYPE (rhs1));
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Found cond scalar reduction");
+      print_gimple_stmt (dump_file, reduc, 0, TDF_SLIM);
+    }
+
+  /* Build cond expression using COND and constant operand
+     of reduction rhs.  */
+  c = fold_build_cond_expr (TREE_TYPE (rhs1),
+			    unshare_expr (cond),
+			    swap? zero: op1,
+			    swap? op1: zero);
+
+  /* Create assignment stmt and insert it at GSI.  */
+  new_assign = gimple_build_assign (tmp, c);
+  gsi_insert_before (gsi, new_assign, GSI_SAME_STMT);
+  update_stmt (new_assign);
+  /* Build rhs for unconditional increment/decrement.  */
+  rhs = build2 (gimple_assign_rhs_code (reduc), TREE_TYPE (rhs1), op0, tmp);
+
+  /* Delete original reduction stmt.  */
+  stmt_it = gsi_for_stmt (reduc);
+  gsi_remove (&stmt_it, true);
+  release_defs (reduc);
+  return rhs;
+}
+
 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
    This routine does not handle PHI nodes with more than two
    arguments.
@@ -1428,6 +1547,8 @@ predicate_scalar_phi (gimple phi, tree cond,
   else
     {
       tree arg_0, arg_1;
+      tree op0, op1;
+      gimple reduc;
       /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr.  */
       if (EDGE_PRED (bb, 1)->src == true_bb)
 	{
@@ -1439,10 +1560,15 @@ predicate_scalar_phi (gimple phi, tree cond,
 	  arg_0 = gimple_phi_arg_def (phi, 0);
 	  arg_1 = gimple_phi_arg_def (phi, 1);
 	}
-
-      /* Build new RHS using selected condition and arguments.  */
-      rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
-				  arg_0, arg_1);
+      if (!(is_cond_scalar_reduction (arg_0, &reduc, &op0, &op1)
+	    || is_cond_scalar_reduction (arg_1, &reduc, &op0, &op1)))
+	/* Build new RHS using selected condition and arguments.  */
+	rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
+				    arg_0, arg_1);
+      else
+	/* Convert reduction stmt into vectorizable form.  */
+	rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
+					     true_bb != gimple_bb (reduc));
     }
 
   new_stmt = gimple_build_assign (res, rhs);

Re: Changes for if-convert to recognize simple conditional reduction.

[Richard Biener]

On Thu, Apr 17, 2014 at 3:09 PM, Yuri Rumyantsev <ysrumyan@gmail.com> wrote:
> Hi All,
>
> We implemented enhancement for if-convert phase to recognize the
> simplest conditional reduction and to transform it vectorizable form,
> e.g. statement
>     if (A[i] != 0) num+= 1; will be recognized.
> A new test-case is also provided.
>
> Bootstrapping and regression testing did not show any new failures.

Clever.  Can you add a testcase with a non-constant but invariant
reduction value and one with a variable reduction value as well?

+      if (!(is_cond_scalar_reduction (arg_0, &reduc, &op0, &op1)
+           || is_cond_scalar_reduction (arg_1, &reduc, &op0, &op1)))

Actually one of the args should be defined by a PHI node in the
loop header and the PHI result should be the PHI arg on the
latch edge, so I'd pass both PHI args to the predicate and do
the decision on what the reduction op is there (you do that
anyway).  The pattern matching is somewhat awkward

+  /* Consider only conditional reduction.  */
+  bb = gimple_bb (stmt);
+  if (!bb_has_predicate (bb))
+    return false;
+  if (is_true_predicate (bb_predicate (bb)))
+    return false;

should be replaced by matching the PHI structure

loop-header:
  reduc_1 = PHI <..., reduc_2>
  ...
  if (..)
    reduc_3 = ...
  reduc_2 = PHI <reduc_1, reduc_3>

+  lhs = gimple_assign_lhs (stmt);
+  if (TREE_CODE (lhs) != SSA_NAME)
+    return false;

always true, in fact lhs == arg.

+  if (SSA_NAME_VAR (lhs) == NULL)
+    return false;

no need to check that (or later verify SSA_NAME_VAR equivalency), not
sure why you think you need that.

+  if (!single_imm_use (lhs, &use, &use_stmt))
+    return false;
+  if (gimple_code (use_stmt) != GIMPLE_PHI)
+    return false;

checking has_single_use (arg) is enough.  The above is error-prone
wrt debug statements.

+  if (reduction_op == PLUS_EXPR &&
+      TREE_CODE (r_op2) == SSA_NAME)

&& goes to the next line

+  if (TREE_CODE (r_op2) != INTEGER_CST && TREE_CODE (r_op2) != REAL_CST)
+    return false;

any reason for this check?  The vectorizer can cope with
loop invariant non-constant values as well (at least).

+  /* Right operand is constant, check that left operand is equal to lhs.  */
+  if (SSA_NAME_VAR (lhs) !=  SSA_NAME_VAR (r_op1))
+    return false;

see above - that looks weird.

Note that I think you may introduce undefined overflow in
unconditionally executing the increment.  So you need to
make sure to re-write the increment in unsigned arithmetic
(for integral types, that is).

Thanks,
Richard.



> Is it OK for trunk?
>
> gcc/ChangeLog:
> 2014-04-17  Yuri Rumyantsev  <ysrumyan@gmail.com>
>
> * tree-if-conv.c (is_cond_scalar_reduction): New function.
> (convert_scalar_cond_reduction): Likewise.
> (predicate_scalar_phi): Add recognition and transformation
> of simple conditioanl reduction to be vectorizable.
>
> gcc/testsuite/ChangeLog:
> 2014-04-17  Yuri Rumyantsev  <ysrumyan@gmail.com>
>
> * gcc.dg/cond-reduc.c: New test.

Re: Changes for if-convert to recognize simple conditional reduction.

[Richard Henderson]

On 04/17/2014 06:09 AM, Yuri Rumyantsev wrote:
> +  /* Build cond expression using COND and constant operand
> +     of reduction rhs.  */
> +  c = fold_build_cond_expr (TREE_TYPE (rhs1),
> +			    unshare_expr (cond),
> +			    swap? zero: op1,
> +			    swap? op1: zero);

Do we recognize somewhere the canonical value for the comparison is -1, and
simplify this further?

E.g.

  if (A[i] != 0) num += 1;

  _vec_cmp = (_vec_A != _vec_ZERO);
  _vec_num -= _vec_cmp;


  if (A[i] != 0) num += x;

  _vec_cmp = (_vec_A != _vec_ZERO);
  _vec_cmp *= _vec_x;
  _vec_num -= _vec_cmp;



r~

Re: Changes for if-convert to recognize simple conditional reduction.

[Richard Biener]

On Mon, Apr 28, 2014 at 10:05 PM, Richard Henderson <rth@redhat.com> wrote:
> On 04/17/2014 06:09 AM, Yuri Rumyantsev wrote:
>> +  /* Build cond expression using COND and constant operand
>> +     of reduction rhs.  */
>> +  c = fold_build_cond_expr (TREE_TYPE (rhs1),
>> +                         unshare_expr (cond),
>> +                         swap? zero: op1,
>> +                         swap? op1: zero);
>
> Do we recognize somewhere the canonical value for the comparison is -1, and
> simplify this further?
>
> E.g.
>
>   if (A[i] != 0) num += 1;
>
>   _vec_cmp = (_vec_A != _vec_ZERO);
>   _vec_num -= _vec_cmp;
>
>
>   if (A[i] != 0) num += x;
>
>   _vec_cmp = (_vec_A != _vec_ZERO);
>   _vec_cmp *= _vec_x;
>   _vec_num -= _vec_cmp;

While the middle-end knows that vector comparisons result in
{0,0...} or {-1,-1,...} I doubt that anyone implemented the above
transform.

Note that it depends on the target on whether the transform
would be profitable - a target may only implement
a vector conditional move for example (the XOP vcond one).
So the correct place for the optimization would be the
expander or combine (unless we apply some canonicalization
rule on GIMPLE - but the back-transform is certainly more
complicated than optimally expanding vec_A != vec_ZERO ? 0 : 1)

Richard.

>
>
> r~

Re: Changes for if-convert to recognize simple conditional reduction.

[Yuri Rumyantsev]

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

2014-04-28 16:16 GMT+04:00 Richard Biener <richard.guenther@gmail.com>:
> On Thu, Apr 17, 2014 at 3:09 PM, Yuri Rumyantsev <ysrumyan@gmail.com> wrote:
>> Hi All,
>>
>> We implemented enhancement for if-convert phase to recognize the
>> simplest conditional reduction and to transform it vectorizable form,
>> e.g. statement
>>     if (A[i] != 0) num+= 1; will be recognized.
>> A new test-case is also provided.
>>
>> Bootstrapping and regression testing did not show any new failures.
>
> Clever.  Can you add a testcase with a non-constant but invariant
> reduction value and one with a variable reduction value as well?
>
[Yuri]
I added another testcase to demonstrate ability of new algorithm, i.e.
it transforms   if (a[i] != 0)   sum += a[i];
to unconditional form without check on zero. Note also that any checks
on non-reduction operand were deleted.

> +      if (!(is_cond_scalar_reduction (arg_0, &reduc, &op0, &op1)
> +           || is_cond_scalar_reduction (arg_1, &reduc, &op0, &op1)))
>
> Actually one of the args should be defined by a PHI node in the
> loop header and the PHI result should be the PHI arg on the
> latch edge, so I'd pass both PHI args to the predicate and do
> the decision on what the reduction op is there (you do that
> anyway).  The pattern matching is somewhat awkward
>
[Yuri]
I changed prototype of 'is_cond_scalar_reduction'  and now we have
only one call:
+      if (!is_cond_scalar_reduction (phi, &reduc, &op0, &op1))

> +  /* Consider only conditional reduction.  */
> +  bb = gimple_bb (stmt);
> +  if (!bb_has_predicate (bb))
> +    return false;
> +  if (is_true_predicate (bb_predicate (bb)))
> +    return false;
>
> should be replaced by matching the PHI structure
>
> loop-header:
>   reduc_1 = PHI <..., reduc_2>
>   ...
>   if (..)
>     reduc_3 = ...
>   reduc_2 = PHI <reduc_1, reduc_3>
>
[Yuri]
   In fact, I re-wrote this function completely as you proposed using
PHI structure matching.

> +  lhs = gimple_assign_lhs (stmt);
> +  if (TREE_CODE (lhs) != SSA_NAME)
> +    return false;
>
> always true, in fact lhs == arg.
>
[Yuri]
Fixed.

> +  if (SSA_NAME_VAR (lhs) == NULL)
> +    return false;
>
[Yuri]
Deleted.
> no need to check that (or later verify SSA_NAME_VAR equivalency), not
> sure why you think you need that.
>
> +  if (!single_imm_use (lhs, &use, &use_stmt))
> +    return false;
> +  if (gimple_code (use_stmt) != GIMPLE_PHI)
> +    return false;
>
> checking has_single_use (arg) is enough.  The above is error-prone
> wrt debug statements.
>
[Yuri] Only proposed check is used:
+  if (!has_single_use (lhs))
+    return false;

> +  if (reduction_op == PLUS_EXPR &&
> +      TREE_CODE (r_op2) == SSA_NAME)
>
> && goes to the next line
>
[Yuri]
Fixed.

> +  if (TREE_CODE (r_op2) != INTEGER_CST && TREE_CODE (r_op2) != REAL_CST)
> +    return false;
>
> any reason for this check?  The vectorizer can cope with
> loop invariant non-constant values as well (at least).
>
[Yuri]
This checks were deleted, i.e. any operand is acceptable.

> +  /* Right operand is constant, check that left operand is equal to lhs.  */
> +  if (SSA_NAME_VAR (lhs) !=  SSA_NAME_VAR (r_op1))
> +    return false;
>
> see above - that looks weird.
>
[Yuri]
This code was deleted.
> Note that I think you may introduce undefined overflow in
> unconditionally executing the increment.  So you need to
> make sure to re-write the increment in unsigned arithmetic
> (for integral types, that is).
[Yuri]
I did not catch your point: if we have
    if (cond) s += val;
it will be transformed to
    s += (cond? val: 0)
which looks like completely equivalent to original stmt.

>
> Thanks,
> Richard.
>
>
>
>> Is it OK for trunk?
>>
>> gcc/ChangeLog:
>> 2014-04-17  Yuri Rumyantsev  <ysrumyan@gmail.com>
>>
>> * tree-if-conv.c (is_cond_scalar_reduction): New function.
>> (convert_scalar_cond_reduction): Likewise.
>> (predicate_scalar_phi): Add recognition and transformation
>> of simple conditioanl reduction to be vectorizable.
>>
>> gcc/testsuite/ChangeLog:
>> 2014-04-17  Yuri Rumyantsev  <ysrumyan@gmail.com>
>>
>> * gcc.dg/cond-reduc.c: New test.

New patch is added which includes also new test to detect
vectorization of conditional reduction with non-invariant operand. All
remarks found by Richard were fixed.

Bootstrap and regression testing did not show any new failures.
Is it OK for trunk?

gcc/ChangeLog
2014-04-29  Yuri Rumyantsev  <ysrumyan@gmail.com>

* tree-if-conv.c (is_cond_scalar_reduction): New function.
(convert_scalar_cond_reduction): Likewise.
(predicate_scalar_phi): Add recognition and transformation
of simple conditioanl reduction to be vectorizable.

gcc/testsuite/ChangeLog:
* gcc.dg/cond-reduc-1.c: New test.
* gcc.dg/cond-reduc-2.c: Likewise.

[-- Attachment #2: cond-reduc.patch.2 --]
[-- Type: application/octet-stream, Size: 6589 bytes --]

diff --git a/gcc/testsuite/gcc.dg/vect/cond-reduc-1.c b/gcc/testsuite/gcc.dg/vect/cond-reduc-1.c
new file mode 100755
index 0000000..981f6b0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/cond-reduc-1.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_int } */
+
+#define N 512
+int a[N];
+int foo()
+{
+  int i, res = 0;
+  for (i=0; i<N; i++)
+  {
+    if (a[i] != 0)
+      res += 1;
+  }
+  return res;
+}
+
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" } } */
+/* { dg-final { cleanup-tree-dump "vect" } } */
+
diff --git a/gcc/testsuite/gcc.dg/vect/cond-reduc-2.c b/gcc/testsuite/gcc.dg/vect/cond-reduc-2.c
new file mode 100755
index 0000000..c329861
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/cond-reduc-2.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_int } */
+
+#define N 512
+int a[N], b[N];
+void foo(int k)
+{
+  int i, res = 0;
+  for (i=0; i<N; i++)
+  {
+    if (b[i] != 0)
+      res += b[i];
+  }
+  a[k] = sum;
+}
+
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" } } */
+/* { dg-final { cleanup-tree-dump "vect" } } */
+
diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c
old mode 100644
new mode 100755
index 7ff2132..5a0f909
--- a/gcc/tree-if-conv.c
+++ b/gcc/tree-if-conv.c
@@ -1386,6 +1386,144 @@ find_phi_replacement_condition (basic_block bb, tree *cond,
   return first_edge->src;
 }
 
+/* Returns true if def-stmt for phi argument ARG is simple increment/decrement
+   which is in predicated basic block.
+   In fact, the following PHI pattern is searching:
+      loop-header:
+	reduc_1 = PHI <..., reduc_2>
+      ...
+	if (...)
+	  reduc_3 = ...
+	reduc_2 = PHI <reduc_1, reduc_3>
+
+   REDUC, OP0 and OP1 contain reduction stmt and its operands.  */
+
+static bool
+is_cond_scalar_reduction (gimple phi, gimple *reduc,
+			  tree *op0, tree *op1)
+{
+  tree lhs, r_op1, r_op2;
+  tree arg_0, arg_1;
+  gimple stmt;
+  gimple header_phi = NULL;
+  enum tree_code reduction_op;
+  struct loop *loop = (gimple_bb (phi))->loop_father;
+  edge latch_e = loop_latch_edge (loop);
+
+  arg_0 = PHI_ARG_DEF (phi, 0);
+  arg_1 = PHI_ARG_DEF (phi, 1);
+  if (TREE_CODE (arg_0) != SSA_NAME || TREE_CODE (arg_1) != SSA_NAME)
+    return false;
+
+  if (gimple_code (SSA_NAME_DEF_STMT (arg_0)) == GIMPLE_PHI)
+    {
+      lhs = arg_1;
+      header_phi = SSA_NAME_DEF_STMT (arg_0);
+      stmt = SSA_NAME_DEF_STMT (arg_1);
+    }
+  else if (gimple_code (SSA_NAME_DEF_STMT (arg_1)) == GIMPLE_PHI)
+    {
+      lhs = arg_0;
+      header_phi = SSA_NAME_DEF_STMT (arg_1);
+      stmt = SSA_NAME_DEF_STMT (arg_0);
+    }
+  else
+    return false;
+  if (gimple_bb (header_phi) != loop->header)
+    return false;
+
+  if (PHI_ARG_DEF_FROM_EDGE (header_phi, latch_e) != PHI_RESULT (phi))
+    return false;
+
+  if (gimple_code (stmt) != GIMPLE_ASSIGN
+      || gimple_has_volatile_ops (stmt))
+    return false;
+
+  if (!is_predicated (gimple_bb (stmt)))
+    return false;
+
+  if (!has_single_use (lhs))
+    return false;
+
+  reduction_op = gimple_assign_rhs_code (stmt);
+  if (reduction_op != PLUS_EXPR && reduction_op != MINUS_EXPR)
+    return false;
+  r_op1 = gimple_assign_rhs1 (stmt);
+  r_op2 = gimple_assign_rhs2 (stmt);
+
+  /* Make R_OP1 to hold reduction variable.  */
+  if (r_op2 == PHI_RESULT (header_phi)
+      && reduction_op == PLUS_EXPR)
+    {
+      tree tmp = r_op1;
+      r_op1 = r_op2;
+      r_op2 = tmp;
+    }
+  else if (r_op1 !=  PHI_RESULT (header_phi))
+    return false;
+
+  *op0 = r_op1; *op1 = r_op2;
+  *reduc = stmt;
+  return true;
+}
+
+/* Converts conditional scalar reduction into unconditional form, e.g.
+     bb_4
+       if (_5 != 0) goto bb_5 else goto bb_6
+     end_bb_4
+     bb_5
+       res_6 = res_13 + 1;
+     end_bb_5
+     bb_6
+       # res_2 = PHI <res_13(4), res_6(5)>
+     end_bb_6
+
+   will be converted into sequence
+    _ifc__1 = _5 != 0 ? 1 : 0;
+    res_2 = res_13 + _ifc__1;
+  Argument SWAP tells that arguments of conditional expression should be
+  swapped.
+  Returns rhs of resulting PHI assignment.  */
+
+static tree
+convert_scalar_cond_reduction (gimple reduc, gimple_stmt_iterator *gsi,
+			       tree cond, tree op0, tree op1, bool swap)
+{
+  gimple_stmt_iterator stmt_it;
+  gimple new_assign;
+  tree rhs;
+  tree rhs1 = gimple_assign_rhs1 (reduc);
+  tree tmp = make_temp_ssa_name (TREE_TYPE (rhs1), NULL, "_ifc_");
+  tree c;
+  tree zero = build_zero_cst (TREE_TYPE (rhs1));
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Found cond scalar reduction.\n");
+      print_gimple_stmt (dump_file, reduc, 0, TDF_SLIM);
+    }
+
+  /* Build cond expression using COND and constant operand
+     of reduction rhs.  */
+  c = fold_build_cond_expr (TREE_TYPE (rhs1),
+			    unshare_expr (cond),
+			    swap? zero: op1,
+			    swap? op1: zero);
+
+  /* Create assignment stmt and insert it at GSI.  */
+  new_assign = gimple_build_assign (tmp, c);
+  gsi_insert_before (gsi, new_assign, GSI_SAME_STMT);
+  update_stmt (new_assign);
+  /* Build rhs for unconditional increment/decrement.  */
+  rhs = build2 (gimple_assign_rhs_code (reduc), TREE_TYPE (rhs1), op0, tmp);
+
+  /* Delete original reduction stmt.  */
+  stmt_it = gsi_for_stmt (reduc);
+  gsi_remove (&stmt_it, true);
+  release_defs (reduc);
+  return rhs;
+}
+
 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
    This routine does not handle PHI nodes with more than two
    arguments.
@@ -1428,6 +1566,9 @@ predicate_scalar_phi (gimple phi, tree cond,
   else
     {
       tree arg_0, arg_1;
+      tree op0, op1;
+      gimple reduc;
+
       /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr.  */
       if (EDGE_PRED (bb, 1)->src == true_bb)
 	{
@@ -1439,10 +1580,14 @@ predicate_scalar_phi (gimple phi, tree cond,
 	  arg_0 = gimple_phi_arg_def (phi, 0);
 	  arg_1 = gimple_phi_arg_def (phi, 1);
 	}
-
-      /* Build new RHS using selected condition and arguments.  */
-      rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
-				  arg_0, arg_1);
+      if (!is_cond_scalar_reduction (phi, &reduc, &op0, &op1))
+	/* Build new RHS using selected condition and arguments.  */
+	rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
+				    arg_0, arg_1);
+      else
+	/* Convert reduction stmt into vectorizable form.  */
+	rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
+					     true_bb != gimple_bb (reduc));
     }
 
   new_stmt = gimple_build_assign (res, rhs);

Re: Changes for if-convert to recognize simple conditional reduction.

[Richard Biener]

On Tue, Apr 29, 2014 at 4:29 PM, Yuri Rumyantsev <ysrumyan@gmail.com> wrote:
> 2014-04-28 16:16 GMT+04:00 Richard Biener <richard.guenther@gmail.com>:
>> On Thu, Apr 17, 2014 at 3:09 PM, Yuri Rumyantsev <ysrumyan@gmail.com> wrote:
>>> Hi All,
>>>
>>> We implemented enhancement for if-convert phase to recognize the
>>> simplest conditional reduction and to transform it vectorizable form,
>>> e.g. statement
>>>     if (A[i] != 0) num+= 1; will be recognized.
>>> A new test-case is also provided.
>>>
>>> Bootstrapping and regression testing did not show any new failures.
>>
>> Clever.  Can you add a testcase with a non-constant but invariant
>> reduction value and one with a variable reduction value as well?
>>
> [Yuri]
> I added another testcase to demonstrate ability of new algorithm, i.e.
> it transforms   if (a[i] != 0)   sum += a[i];
> to unconditional form without check on zero. Note also that any checks
> on non-reduction operand were deleted.
>
>> +      if (!(is_cond_scalar_reduction (arg_0, &reduc, &op0, &op1)
>> +           || is_cond_scalar_reduction (arg_1, &reduc, &op0, &op1)))
>>
>> Actually one of the args should be defined by a PHI node in the
>> loop header and the PHI result should be the PHI arg on the
>> latch edge, so I'd pass both PHI args to the predicate and do
>> the decision on what the reduction op is there (you do that
>> anyway).  The pattern matching is somewhat awkward
>>
> [Yuri]
> I changed prototype of 'is_cond_scalar_reduction'  and now we have
> only one call:
> +      if (!is_cond_scalar_reduction (phi, &reduc, &op0, &op1))
>
>> +  /* Consider only conditional reduction.  */
>> +  bb = gimple_bb (stmt);
>> +  if (!bb_has_predicate (bb))
>> +    return false;
>> +  if (is_true_predicate (bb_predicate (bb)))
>> +    return false;
>>
>> should be replaced by matching the PHI structure
>>
>> loop-header:
>>   reduc_1 = PHI <..., reduc_2>
>>   ...
>>   if (..)
>>     reduc_3 = ...
>>   reduc_2 = PHI <reduc_1, reduc_3>
>>
> [Yuri]
>    In fact, I re-wrote this function completely as you proposed using
> PHI structure matching.
>
>> +  lhs = gimple_assign_lhs (stmt);
>> +  if (TREE_CODE (lhs) != SSA_NAME)
>> +    return false;
>>
>> always true, in fact lhs == arg.
>>
> [Yuri]
> Fixed.
>
>> +  if (SSA_NAME_VAR (lhs) == NULL)
>> +    return false;
>>
> [Yuri]
> Deleted.
>> no need to check that (or later verify SSA_NAME_VAR equivalency), not
>> sure why you think you need that.
>>
>> +  if (!single_imm_use (lhs, &use, &use_stmt))
>> +    return false;
>> +  if (gimple_code (use_stmt) != GIMPLE_PHI)
>> +    return false;
>>
>> checking has_single_use (arg) is enough.  The above is error-prone
>> wrt debug statements.
>>
> [Yuri] Only proposed check is used:
> +  if (!has_single_use (lhs))
> +    return false;
>
>> +  if (reduction_op == PLUS_EXPR &&
>> +      TREE_CODE (r_op2) == SSA_NAME)
>>
>> && goes to the next line
>>
> [Yuri]
> Fixed.
>
>> +  if (TREE_CODE (r_op2) != INTEGER_CST && TREE_CODE (r_op2) != REAL_CST)
>> +    return false;
>>
>> any reason for this check?  The vectorizer can cope with
>> loop invariant non-constant values as well (at least).
>>
> [Yuri]
> This checks were deleted, i.e. any operand is acceptable.
>
>> +  /* Right operand is constant, check that left operand is equal to lhs.  */
>> +  if (SSA_NAME_VAR (lhs) !=  SSA_NAME_VAR (r_op1))
>> +    return false;
>>
>> see above - that looks weird.
>>
> [Yuri]
> This code was deleted.
>> Note that I think you may introduce undefined overflow in
>> unconditionally executing the increment.  So you need to
>> make sure to re-write the increment in unsigned arithmetic
>> (for integral types, that is).
> [Yuri]
> I did not catch your point: if we have
>     if (cond) s += val;
> it will be transformed to
>     s += (cond? val: 0)
> which looks like completely equivalent to original stmt.

Ah indeed.

>>
>> Thanks,
>> Richard.
>>
>>
>>
>>> Is it OK for trunk?
>>>
>>> gcc/ChangeLog:
>>> 2014-04-17  Yuri Rumyantsev  <ysrumyan@gmail.com>
>>>
>>> * tree-if-conv.c (is_cond_scalar_reduction): New function.
>>> (convert_scalar_cond_reduction): Likewise.
>>> (predicate_scalar_phi): Add recognition and transformation
>>> of simple conditioanl reduction to be vectorizable.
>>>
>>> gcc/testsuite/ChangeLog:
>>> 2014-04-17  Yuri Rumyantsev  <ysrumyan@gmail.com>
>>>
>>> * gcc.dg/cond-reduc.c: New test.
>
> New patch is added which includes also new test to detect
> vectorization of conditional reduction with non-invariant operand. All
> remarks found by Richard were fixed.
>
> Bootstrap and regression testing did not show any new failures.
> Is it OK for trunk?

Ok with minor stylistic changes:

+  struct loop *loop = (gimple_bb (phi))->loop_father;

no () around the gimple_bb call.

+  else if (r_op1 !=  PHI_RESULT (header_phi))
+    return false;

too many spaces after =

+  c = fold_build_cond_expr (TREE_TYPE (rhs1),
+                           unshare_expr (cond),
+                           swap? zero: op1,
+                           swap? op1: zero);

a space missing before ?

+  gsi_insert_before (gsi, new_assign, GSI_SAME_STMT);
+  update_stmt (new_assign);

gsi_insert_before already calls update_stmt on new_assign, no
reason to do it again.

+  /* Build rhs for unconditional increment/decrement.  */
+  rhs = build2 (gimple_assign_rhs_code (reduc), TREE_TYPE (rhs1), op0, tmp);

always use fold_build2, not build2.

+      if (!is_cond_scalar_reduction (phi, &reduc, &op0, &op1))
+       /* Build new RHS using selected condition and arguments.  */
+       rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
+                                   arg_0, arg_1);
+      else
+       /* Convert reduction stmt into vectorizable form.  */
+       rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
+                                            true_bb != gimple_bb (reduc));

now that it's a very simple check please use a positive form, thus

   if (is_cond_scalar_reduction ...)
     * Convert reduction stmt into vectorizable form.  */
....
   else

Ok with these changes.

Thanks,
Richard.

> gcc/ChangeLog
> 2014-04-29  Yuri Rumyantsev  <ysrumyan@gmail.com>
>
> * tree-if-conv.c (is_cond_scalar_reduction): New function.
> (convert_scalar_cond_reduction): Likewise.
> (predicate_scalar_phi): Add recognition and transformation
> of simple conditioanl reduction to be vectorizable.
>
> gcc/testsuite/ChangeLog:
> * gcc.dg/cond-reduc-1.c: New test.
> * gcc.dg/cond-reduc-2.c: Likewise.

Re: Changes for if-convert to recognize simple conditional reduction.

[Yuri Rumyantsev]

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

Thanks a lot Richard for you review.
I did all proposed changes, checked that bootstrap and regression
testing did not show new failures.
Updated patch is attached.

Best regards.
Yuri.

2014-04-30 16:40 GMT+04:00 Richard Biener <richard.guenther@gmail.com>:
> On Tue, Apr 29, 2014 at 4:29 PM, Yuri Rumyantsev <ysrumyan@gmail.com> wrote:
>> 2014-04-28 16:16 GMT+04:00 Richard Biener <richard.guenther@gmail.com>:
>>> On Thu, Apr 17, 2014 at 3:09 PM, Yuri Rumyantsev <ysrumyan@gmail.com> wrote:
>>>> Hi All,
>>>>
>>>> We implemented enhancement for if-convert phase to recognize the
>>>> simplest conditional reduction and to transform it vectorizable form,
>>>> e.g. statement
>>>>     if (A[i] != 0) num+= 1; will be recognized.
>>>> A new test-case is also provided.
>>>>
>>>> Bootstrapping and regression testing did not show any new failures.
>>>
>>> Clever.  Can you add a testcase with a non-constant but invariant
>>> reduction value and one with a variable reduction value as well?
>>>
>> [Yuri]
>> I added another testcase to demonstrate ability of new algorithm, i.e.
>> it transforms   if (a[i] != 0)   sum += a[i];
>> to unconditional form without check on zero. Note also that any checks
>> on non-reduction operand were deleted.
>>
>>> +      if (!(is_cond_scalar_reduction (arg_0, &reduc, &op0, &op1)
>>> +           || is_cond_scalar_reduction (arg_1, &reduc, &op0, &op1)))
>>>
>>> Actually one of the args should be defined by a PHI node in the
>>> loop header and the PHI result should be the PHI arg on the
>>> latch edge, so I'd pass both PHI args to the predicate and do
>>> the decision on what the reduction op is there (you do that
>>> anyway).  The pattern matching is somewhat awkward
>>>
>> [Yuri]
>> I changed prototype of 'is_cond_scalar_reduction'  and now we have
>> only one call:
>> +      if (!is_cond_scalar_reduction (phi, &reduc, &op0, &op1))
>>
>>> +  /* Consider only conditional reduction.  */
>>> +  bb = gimple_bb (stmt);
>>> +  if (!bb_has_predicate (bb))
>>> +    return false;
>>> +  if (is_true_predicate (bb_predicate (bb)))
>>> +    return false;
>>>
>>> should be replaced by matching the PHI structure
>>>
>>> loop-header:
>>>   reduc_1 = PHI <..., reduc_2>
>>>   ...
>>>   if (..)
>>>     reduc_3 = ...
>>>   reduc_2 = PHI <reduc_1, reduc_3>
>>>
>> [Yuri]
>>    In fact, I re-wrote this function completely as you proposed using
>> PHI structure matching.
>>
>>> +  lhs = gimple_assign_lhs (stmt);
>>> +  if (TREE_CODE (lhs) != SSA_NAME)
>>> +    return false;
>>>
>>> always true, in fact lhs == arg.
>>>
>> [Yuri]
>> Fixed.
>>
>>> +  if (SSA_NAME_VAR (lhs) == NULL)
>>> +    return false;
>>>
>> [Yuri]
>> Deleted.
>>> no need to check that (or later verify SSA_NAME_VAR equivalency), not
>>> sure why you think you need that.
>>>
>>> +  if (!single_imm_use (lhs, &use, &use_stmt))
>>> +    return false;
>>> +  if (gimple_code (use_stmt) != GIMPLE_PHI)
>>> +    return false;
>>>
>>> checking has_single_use (arg) is enough.  The above is error-prone
>>> wrt debug statements.
>>>
>> [Yuri] Only proposed check is used:
>> +  if (!has_single_use (lhs))
>> +    return false;
>>
>>> +  if (reduction_op == PLUS_EXPR &&
>>> +      TREE_CODE (r_op2) == SSA_NAME)
>>>
>>> && goes to the next line
>>>
>> [Yuri]
>> Fixed.
>>
>>> +  if (TREE_CODE (r_op2) != INTEGER_CST && TREE_CODE (r_op2) != REAL_CST)
>>> +    return false;
>>>
>>> any reason for this check?  The vectorizer can cope with
>>> loop invariant non-constant values as well (at least).
>>>
>> [Yuri]
>> This checks were deleted, i.e. any operand is acceptable.
>>
>>> +  /* Right operand is constant, check that left operand is equal to lhs.  */
>>> +  if (SSA_NAME_VAR (lhs) !=  SSA_NAME_VAR (r_op1))
>>> +    return false;
>>>
>>> see above - that looks weird.
>>>
>> [Yuri]
>> This code was deleted.
>>> Note that I think you may introduce undefined overflow in
>>> unconditionally executing the increment.  So you need to
>>> make sure to re-write the increment in unsigned arithmetic
>>> (for integral types, that is).
>> [Yuri]
>> I did not catch your point: if we have
>>     if (cond) s += val;
>> it will be transformed to
>>     s += (cond? val: 0)
>> which looks like completely equivalent to original stmt.
>
> Ah indeed.
>
>>>
>>> Thanks,
>>> Richard.
>>>
>>>
>>>
>>>> Is it OK for trunk?
>>>>
>>>> gcc/ChangeLog:
>>>> 2014-04-17  Yuri Rumyantsev  <ysrumyan@gmail.com>
>>>>
>>>> * tree-if-conv.c (is_cond_scalar_reduction): New function.
>>>> (convert_scalar_cond_reduction): Likewise.
>>>> (predicate_scalar_phi): Add recognition and transformation
>>>> of simple conditioanl reduction to be vectorizable.
>>>>
>>>> gcc/testsuite/ChangeLog:
>>>> 2014-04-17  Yuri Rumyantsev  <ysrumyan@gmail.com>
>>>>
>>>> * gcc.dg/cond-reduc.c: New test.
>>
>> New patch is added which includes also new test to detect
>> vectorization of conditional reduction with non-invariant operand. All
>> remarks found by Richard were fixed.
>>
>> Bootstrap and regression testing did not show any new failures.
>> Is it OK for trunk?
>
> Ok with minor stylistic changes:
>
> +  struct loop *loop = (gimple_bb (phi))->loop_father;
>
> no () around the gimple_bb call.
>
> +  else if (r_op1 !=  PHI_RESULT (header_phi))
> +    return false;
>
> too many spaces after =
>
> +  c = fold_build_cond_expr (TREE_TYPE (rhs1),
> +                           unshare_expr (cond),
> +                           swap? zero: op1,
> +                           swap? op1: zero);
>
> a space missing before ?
>
> +  gsi_insert_before (gsi, new_assign, GSI_SAME_STMT);
> +  update_stmt (new_assign);
>
> gsi_insert_before already calls update_stmt on new_assign, no
> reason to do it again.
>
> +  /* Build rhs for unconditional increment/decrement.  */
> +  rhs = build2 (gimple_assign_rhs_code (reduc), TREE_TYPE (rhs1), op0, tmp);
>
> always use fold_build2, not build2.
>
> +      if (!is_cond_scalar_reduction (phi, &reduc, &op0, &op1))
> +       /* Build new RHS using selected condition and arguments.  */
> +       rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
> +                                   arg_0, arg_1);
> +      else
> +       /* Convert reduction stmt into vectorizable form.  */
> +       rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
> +                                            true_bb != gimple_bb (reduc));
>
> now that it's a very simple check please use a positive form, thus
>
>    if (is_cond_scalar_reduction ...)
>      * Convert reduction stmt into vectorizable form.  */
> ....
>    else
>
> Ok with these changes.
>
> Thanks,
> Richard.
>
>> gcc/ChangeLog
>> 2014-04-29  Yuri Rumyantsev  <ysrumyan@gmail.com>
>>
>> * tree-if-conv.c (is_cond_scalar_reduction): New function.
>> (convert_scalar_cond_reduction): Likewise.
>> (predicate_scalar_phi): Add recognition and transformation
>> of simple conditioanl reduction to be vectorizable.
>>
>> gcc/testsuite/ChangeLog:
>> * gcc.dg/cond-reduc-1.c: New test.
>> * gcc.dg/cond-reduc-2.c: Likewise.

[-- Attachment #2: cond-reduc.patch.3 --]
[-- Type: application/octet-stream, Size: 6573 bytes --]

diff --git a/gcc/testsuite/gcc.dg/vect/cond-reduc-1.c b/gcc/testsuite/gcc.dg/vect/cond-reduc-1.c
new file mode 100755
index 0000000..981f6b0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/cond-reduc-1.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_int } */
+
+#define N 512
+int a[N];
+int foo()
+{
+  int i, res = 0;
+  for (i=0; i<N; i++)
+  {
+    if (a[i] != 0)
+      res += 1;
+  }
+  return res;
+}
+
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" } } */
+/* { dg-final { cleanup-tree-dump "vect" } } */
+
diff --git a/gcc/testsuite/gcc.dg/vect/cond-reduc-2.c b/gcc/testsuite/gcc.dg/vect/cond-reduc-2.c
new file mode 100755
index 0000000..c329861
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/cond-reduc-2.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-require-effective-target vect_int } */
+
+#define N 512
+int a[N], b[N];
+void foo(int k)
+{
+  int i, res = 0;
+  for (i=0; i<N; i++)
+  {
+    if (b[i] != 0)
+      res += b[i];
+  }
+  a[k] = sum;
+}
+
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" } } */
+/* { dg-final { cleanup-tree-dump "vect" } } */
+
diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c
old mode 100644
new mode 100755
index 7ff2132..7a39f13
--- a/gcc/tree-if-conv.c
+++ b/gcc/tree-if-conv.c
@@ -1386,6 +1386,144 @@ find_phi_replacement_condition (basic_block bb, tree *cond,
   return first_edge->src;
 }
 
+/* Returns true if def-stmt for phi argument ARG is simple increment/decrement
+   which is in predicated basic block.
+   In fact, the following PHI pattern is searching:
+      loop-header:
+	reduc_1 = PHI <..., reduc_2>
+      ...
+	if (...)
+	  reduc_3 = ...
+	reduc_2 = PHI <reduc_1, reduc_3>
+
+   REDUC, OP0 and OP1 contain reduction stmt and its operands.  */
+
+static bool
+is_cond_scalar_reduction (gimple phi, gimple *reduc,
+			  tree *op0, tree *op1)
+{
+  tree lhs, r_op1, r_op2;
+  tree arg_0, arg_1;
+  gimple stmt;
+  gimple header_phi = NULL;
+  enum tree_code reduction_op;
+  struct loop *loop = gimple_bb (phi)->loop_father;
+  edge latch_e = loop_latch_edge (loop);
+
+  arg_0 = PHI_ARG_DEF (phi, 0);
+  arg_1 = PHI_ARG_DEF (phi, 1);
+  if (TREE_CODE (arg_0) != SSA_NAME || TREE_CODE (arg_1) != SSA_NAME)
+    return false;
+
+  if (gimple_code (SSA_NAME_DEF_STMT (arg_0)) == GIMPLE_PHI)
+    {
+      lhs = arg_1;
+      header_phi = SSA_NAME_DEF_STMT (arg_0);
+      stmt = SSA_NAME_DEF_STMT (arg_1);
+    }
+  else if (gimple_code (SSA_NAME_DEF_STMT (arg_1)) == GIMPLE_PHI)
+    {
+      lhs = arg_0;
+      header_phi = SSA_NAME_DEF_STMT (arg_1);
+      stmt = SSA_NAME_DEF_STMT (arg_0);
+    }
+  else
+    return false;
+  if (gimple_bb (header_phi) != loop->header)
+    return false;
+
+  if (PHI_ARG_DEF_FROM_EDGE (header_phi, latch_e) != PHI_RESULT (phi))
+    return false;
+
+  if (gimple_code (stmt) != GIMPLE_ASSIGN
+      || gimple_has_volatile_ops (stmt))
+    return false;
+
+  if (!is_predicated (gimple_bb (stmt)))
+    return false;
+
+  if (!has_single_use (lhs))
+    return false;
+
+  reduction_op = gimple_assign_rhs_code (stmt);
+  if (reduction_op != PLUS_EXPR && reduction_op != MINUS_EXPR)
+    return false;
+  r_op1 = gimple_assign_rhs1 (stmt);
+  r_op2 = gimple_assign_rhs2 (stmt);
+
+  /* Make R_OP1 to hold reduction variable.  */
+  if (r_op2 == PHI_RESULT (header_phi)
+      && reduction_op == PLUS_EXPR)
+    {
+      tree tmp = r_op1;
+      r_op1 = r_op2;
+      r_op2 = tmp;
+    }
+  else if (r_op1 != PHI_RESULT (header_phi))
+    return false;
+
+  *op0 = r_op1; *op1 = r_op2;
+  *reduc = stmt;
+  return true;
+}
+
+/* Converts conditional scalar reduction into unconditional form, e.g.
+     bb_4
+       if (_5 != 0) goto bb_5 else goto bb_6
+     end_bb_4
+     bb_5
+       res_6 = res_13 + 1;
+     end_bb_5
+     bb_6
+       # res_2 = PHI <res_13(4), res_6(5)>
+     end_bb_6
+
+   will be converted into sequence
+    _ifc__1 = _5 != 0 ? 1 : 0;
+    res_2 = res_13 + _ifc__1;
+  Argument SWAP tells that arguments of conditional expression should be
+  swapped.
+  Returns rhs of resulting PHI assignment.  */
+
+static tree
+convert_scalar_cond_reduction (gimple reduc, gimple_stmt_iterator *gsi,
+			       tree cond, tree op0, tree op1, bool swap)
+{
+  gimple_stmt_iterator stmt_it;
+  gimple new_assign;
+  tree rhs;
+  tree rhs1 = gimple_assign_rhs1 (reduc);
+  tree tmp = make_temp_ssa_name (TREE_TYPE (rhs1), NULL, "_ifc_");
+  tree c;
+  tree zero = build_zero_cst (TREE_TYPE (rhs1));
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Found cond scalar reduction.\n");
+      print_gimple_stmt (dump_file, reduc, 0, TDF_SLIM);
+    }
+
+  /* Build cond expression using COND and constant operand
+     of reduction rhs.  */
+  c = fold_build_cond_expr (TREE_TYPE (rhs1),
+			    unshare_expr (cond),
+			    swap ? zero : op1,
+			    swap ? op1 : zero);
+
+  /* Create assignment stmt and insert it at GSI.  */
+  new_assign = gimple_build_assign (tmp, c);
+  gsi_insert_before (gsi, new_assign, GSI_SAME_STMT);
+  /* Build rhs for unconditional increment/decrement.  */
+  rhs = fold_build2 (gimple_assign_rhs_code (reduc),
+		     TREE_TYPE (rhs1), op0, tmp);
+
+  /* Delete original reduction stmt.  */
+  stmt_it = gsi_for_stmt (reduc);
+  gsi_remove (&stmt_it, true);
+  release_defs (reduc);
+  return rhs;
+}
+
 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
    This routine does not handle PHI nodes with more than two
    arguments.
@@ -1428,6 +1566,9 @@ predicate_scalar_phi (gimple phi, tree cond,
   else
     {
       tree arg_0, arg_1;
+      tree op0, op1;
+      gimple reduc;
+
       /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr.  */
       if (EDGE_PRED (bb, 1)->src == true_bb)
 	{
@@ -1439,10 +1580,14 @@ predicate_scalar_phi (gimple phi, tree cond,
 	  arg_0 = gimple_phi_arg_def (phi, 0);
 	  arg_1 = gimple_phi_arg_def (phi, 1);
 	}
-
-      /* Build new RHS using selected condition and arguments.  */
-      rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
-				  arg_0, arg_1);
+      if (is_cond_scalar_reduction (phi, &reduc, &op0, &op1))
+	/* Convert reduction stmt into vectorizable form.  */
+	rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
+					     true_bb != gimple_bb (reduc));
+      else
+	/* Build new RHS using selected condition and arguments.  */
+	rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
+				    arg_0, arg_1);
     }
 
   new_stmt = gimple_build_assign (res, rhs);

Re: Changes for if-convert to recognize simple conditional reduction.

[H.J. Lu]

On Wed, Apr 30, 2014 at 8:50 AM, Yuri Rumyantsev <ysrumyan@gmail.com> wrote:
> Thanks a lot Richard for you review.
> I did all proposed changes, checked that bootstrap and regression
> testing did not show new failures.
> Updated patch is attached.
>

Does this help

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21998

-- 
H.J.

Re: Changes for if-convert to recognize simple conditional reduction.

[Richard Biener]

On Wed, Apr 30, 2014 at 5:50 PM, Yuri Rumyantsev <ysrumyan@gmail.com> wrote:
> Thanks a lot Richard for you review.
> I did all proposed changes, checked that bootstrap and regression
> testing did not show new failures.
> Updated patch is attached.

As said, this is ok for checkin.

Thanks,
Richard.

> Best regards.
> Yuri.
>
> 2014-04-30 16:40 GMT+04:00 Richard Biener <richard.guenther@gmail.com>:
>> On Tue, Apr 29, 2014 at 4:29 PM, Yuri Rumyantsev <ysrumyan@gmail.com> wrote:
>>> 2014-04-28 16:16 GMT+04:00 Richard Biener <richard.guenther@gmail.com>:
>>>> On Thu, Apr 17, 2014 at 3:09 PM, Yuri Rumyantsev <ysrumyan@gmail.com> wrote:
>>>>> Hi All,
>>>>>
>>>>> We implemented enhancement for if-convert phase to recognize the
>>>>> simplest conditional reduction and to transform it vectorizable form,
>>>>> e.g. statement
>>>>>     if (A[i] != 0) num+= 1; will be recognized.
>>>>> A new test-case is also provided.
>>>>>
>>>>> Bootstrapping and regression testing did not show any new failures.
>>>>
>>>> Clever.  Can you add a testcase with a non-constant but invariant
>>>> reduction value and one with a variable reduction value as well?
>>>>
>>> [Yuri]
>>> I added another testcase to demonstrate ability of new algorithm, i.e.
>>> it transforms   if (a[i] != 0)   sum += a[i];
>>> to unconditional form without check on zero. Note also that any checks
>>> on non-reduction operand were deleted.
>>>
>>>> +      if (!(is_cond_scalar_reduction (arg_0, &reduc, &op0, &op1)
>>>> +           || is_cond_scalar_reduction (arg_1, &reduc, &op0, &op1)))
>>>>
>>>> Actually one of the args should be defined by a PHI node in the
>>>> loop header and the PHI result should be the PHI arg on the
>>>> latch edge, so I'd pass both PHI args to the predicate and do
>>>> the decision on what the reduction op is there (you do that
>>>> anyway).  The pattern matching is somewhat awkward
>>>>
>>> [Yuri]
>>> I changed prototype of 'is_cond_scalar_reduction'  and now we have
>>> only one call:
>>> +      if (!is_cond_scalar_reduction (phi, &reduc, &op0, &op1))
>>>
>>>> +  /* Consider only conditional reduction.  */
>>>> +  bb = gimple_bb (stmt);
>>>> +  if (!bb_has_predicate (bb))
>>>> +    return false;
>>>> +  if (is_true_predicate (bb_predicate (bb)))
>>>> +    return false;
>>>>
>>>> should be replaced by matching the PHI structure
>>>>
>>>> loop-header:
>>>>   reduc_1 = PHI <..., reduc_2>
>>>>   ...
>>>>   if (..)
>>>>     reduc_3 = ...
>>>>   reduc_2 = PHI <reduc_1, reduc_3>
>>>>
>>> [Yuri]
>>>    In fact, I re-wrote this function completely as you proposed using
>>> PHI structure matching.
>>>
>>>> +  lhs = gimple_assign_lhs (stmt);
>>>> +  if (TREE_CODE (lhs) != SSA_NAME)
>>>> +    return false;
>>>>
>>>> always true, in fact lhs == arg.
>>>>
>>> [Yuri]
>>> Fixed.
>>>
>>>> +  if (SSA_NAME_VAR (lhs) == NULL)
>>>> +    return false;
>>>>
>>> [Yuri]
>>> Deleted.
>>>> no need to check that (or later verify SSA_NAME_VAR equivalency), not
>>>> sure why you think you need that.
>>>>
>>>> +  if (!single_imm_use (lhs, &use, &use_stmt))
>>>> +    return false;
>>>> +  if (gimple_code (use_stmt) != GIMPLE_PHI)
>>>> +    return false;
>>>>
>>>> checking has_single_use (arg) is enough.  The above is error-prone
>>>> wrt debug statements.
>>>>
>>> [Yuri] Only proposed check is used:
>>> +  if (!has_single_use (lhs))
>>> +    return false;
>>>
>>>> +  if (reduction_op == PLUS_EXPR &&
>>>> +      TREE_CODE (r_op2) == SSA_NAME)
>>>>
>>>> && goes to the next line
>>>>
>>> [Yuri]
>>> Fixed.
>>>
>>>> +  if (TREE_CODE (r_op2) != INTEGER_CST && TREE_CODE (r_op2) != REAL_CST)
>>>> +    return false;
>>>>
>>>> any reason for this check?  The vectorizer can cope with
>>>> loop invariant non-constant values as well (at least).
>>>>
>>> [Yuri]
>>> This checks were deleted, i.e. any operand is acceptable.
>>>
>>>> +  /* Right operand is constant, check that left operand is equal to lhs.  */
>>>> +  if (SSA_NAME_VAR (lhs) !=  SSA_NAME_VAR (r_op1))
>>>> +    return false;
>>>>
>>>> see above - that looks weird.
>>>>
>>> [Yuri]
>>> This code was deleted.
>>>> Note that I think you may introduce undefined overflow in
>>>> unconditionally executing the increment.  So you need to
>>>> make sure to re-write the increment in unsigned arithmetic
>>>> (for integral types, that is).
>>> [Yuri]
>>> I did not catch your point: if we have
>>>     if (cond) s += val;
>>> it will be transformed to
>>>     s += (cond? val: 0)
>>> which looks like completely equivalent to original stmt.
>>
>> Ah indeed.
>>
>>>>
>>>> Thanks,
>>>> Richard.
>>>>
>>>>
>>>>
>>>>> Is it OK for trunk?
>>>>>
>>>>> gcc/ChangeLog:
>>>>> 2014-04-17  Yuri Rumyantsev  <ysrumyan@gmail.com>
>>>>>
>>>>> * tree-if-conv.c (is_cond_scalar_reduction): New function.
>>>>> (convert_scalar_cond_reduction): Likewise.
>>>>> (predicate_scalar_phi): Add recognition and transformation
>>>>> of simple conditioanl reduction to be vectorizable.
>>>>>
>>>>> gcc/testsuite/ChangeLog:
>>>>> 2014-04-17  Yuri Rumyantsev  <ysrumyan@gmail.com>
>>>>>
>>>>> * gcc.dg/cond-reduc.c: New test.
>>>
>>> New patch is added which includes also new test to detect
>>> vectorization of conditional reduction with non-invariant operand. All
>>> remarks found by Richard were fixed.
>>>
>>> Bootstrap and regression testing did not show any new failures.
>>> Is it OK for trunk?
>>
>> Ok with minor stylistic changes:
>>
>> +  struct loop *loop = (gimple_bb (phi))->loop_father;
>>
>> no () around the gimple_bb call.
>>
>> +  else if (r_op1 !=  PHI_RESULT (header_phi))
>> +    return false;
>>
>> too many spaces after =
>>
>> +  c = fold_build_cond_expr (TREE_TYPE (rhs1),
>> +                           unshare_expr (cond),
>> +                           swap? zero: op1,
>> +                           swap? op1: zero);
>>
>> a space missing before ?
>>
>> +  gsi_insert_before (gsi, new_assign, GSI_SAME_STMT);
>> +  update_stmt (new_assign);
>>
>> gsi_insert_before already calls update_stmt on new_assign, no
>> reason to do it again.
>>
>> +  /* Build rhs for unconditional increment/decrement.  */
>> +  rhs = build2 (gimple_assign_rhs_code (reduc), TREE_TYPE (rhs1), op0, tmp);
>>
>> always use fold_build2, not build2.
>>
>> +      if (!is_cond_scalar_reduction (phi, &reduc, &op0, &op1))
>> +       /* Build new RHS using selected condition and arguments.  */
>> +       rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
>> +                                   arg_0, arg_1);
>> +      else
>> +       /* Convert reduction stmt into vectorizable form.  */
>> +       rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
>> +                                            true_bb != gimple_bb (reduc));
>>
>> now that it's a very simple check please use a positive form, thus
>>
>>    if (is_cond_scalar_reduction ...)
>>      * Convert reduction stmt into vectorizable form.  */
>> ....
>>    else
>>
>> Ok with these changes.
>>
>> Thanks,
>> Richard.
>>
>>> gcc/ChangeLog
>>> 2014-04-29  Yuri Rumyantsev  <ysrumyan@gmail.com>
>>>
>>> * tree-if-conv.c (is_cond_scalar_reduction): New function.
>>> (convert_scalar_cond_reduction): Likewise.
>>> (predicate_scalar_phi): Add recognition and transformation
>>> of simple conditioanl reduction to be vectorizable.
>>>
>>> gcc/testsuite/ChangeLog:
>>> * gcc.dg/cond-reduc-1.c: New test.
>>> * gcc.dg/cond-reduc-2.c: Likewise.

Re: Changes for if-convert to recognize simple conditional reduction.

[Yuri Rumyantsev]

No, this is quite different issue related to safety of load/stores
which are on branched paths, i.e. not always executed and may trap.
Note that we don't have such  issue for HSW which have masked
load/stores.

Yuri.

2014-05-05 11:44 GMT+04:00 Richard Biener <richard.guenther@gmail.com>:
> On Wed, Apr 30, 2014 at 5:50 PM, Yuri Rumyantsev <ysrumyan@gmail.com> wrote:
>> Thanks a lot Richard for you review.
>> I did all proposed changes, checked that bootstrap and regression
>> testing did not show new failures.
>> Updated patch is attached.
>
> As said, this is ok for checkin.
>
> Thanks,
> Richard.
>
>> Best regards.
>> Yuri.
>>
>> 2014-04-30 16:40 GMT+04:00 Richard Biener <richard.guenther@gmail.com>:
>>> On Tue, Apr 29, 2014 at 4:29 PM, Yuri Rumyantsev <ysrumyan@gmail.com> wrote:
>>>> 2014-04-28 16:16 GMT+04:00 Richard Biener <richard.guenther@gmail.com>:
>>>>> On Thu, Apr 17, 2014 at 3:09 PM, Yuri Rumyantsev <ysrumyan@gmail.com> wrote:
>>>>>> Hi All,
>>>>>>
>>>>>> We implemented enhancement for if-convert phase to recognize the
>>>>>> simplest conditional reduction and to transform it vectorizable form,
>>>>>> e.g. statement
>>>>>>     if (A[i] != 0) num+= 1; will be recognized.
>>>>>> A new test-case is also provided.
>>>>>>
>>>>>> Bootstrapping and regression testing did not show any new failures.
>>>>>
>>>>> Clever.  Can you add a testcase with a non-constant but invariant
>>>>> reduction value and one with a variable reduction value as well?
>>>>>
>>>> [Yuri]
>>>> I added another testcase to demonstrate ability of new algorithm, i.e.
>>>> it transforms   if (a[i] != 0)   sum += a[i];
>>>> to unconditional form without check on zero. Note also that any checks
>>>> on non-reduction operand were deleted.
>>>>
>>>>> +      if (!(is_cond_scalar_reduction (arg_0, &reduc, &op0, &op1)
>>>>> +           || is_cond_scalar_reduction (arg_1, &reduc, &op0, &op1)))
>>>>>
>>>>> Actually one of the args should be defined by a PHI node in the
>>>>> loop header and the PHI result should be the PHI arg on the
>>>>> latch edge, so I'd pass both PHI args to the predicate and do
>>>>> the decision on what the reduction op is there (you do that
>>>>> anyway).  The pattern matching is somewhat awkward
>>>>>
>>>> [Yuri]
>>>> I changed prototype of 'is_cond_scalar_reduction'  and now we have
>>>> only one call:
>>>> +      if (!is_cond_scalar_reduction (phi, &reduc, &op0, &op1))
>>>>
>>>>> +  /* Consider only conditional reduction.  */
>>>>> +  bb = gimple_bb (stmt);
>>>>> +  if (!bb_has_predicate (bb))
>>>>> +    return false;
>>>>> +  if (is_true_predicate (bb_predicate (bb)))
>>>>> +    return false;
>>>>>
>>>>> should be replaced by matching the PHI structure
>>>>>
>>>>> loop-header:
>>>>>   reduc_1 = PHI <..., reduc_2>
>>>>>   ...
>>>>>   if (..)
>>>>>     reduc_3 = ...
>>>>>   reduc_2 = PHI <reduc_1, reduc_3>
>>>>>
>>>> [Yuri]
>>>>    In fact, I re-wrote this function completely as you proposed using
>>>> PHI structure matching.
>>>>
>>>>> +  lhs = gimple_assign_lhs (stmt);
>>>>> +  if (TREE_CODE (lhs) != SSA_NAME)
>>>>> +    return false;
>>>>>
>>>>> always true, in fact lhs == arg.
>>>>>
>>>> [Yuri]
>>>> Fixed.
>>>>
>>>>> +  if (SSA_NAME_VAR (lhs) == NULL)
>>>>> +    return false;
>>>>>
>>>> [Yuri]
>>>> Deleted.
>>>>> no need to check that (or later verify SSA_NAME_VAR equivalency), not
>>>>> sure why you think you need that.
>>>>>
>>>>> +  if (!single_imm_use (lhs, &use, &use_stmt))
>>>>> +    return false;
>>>>> +  if (gimple_code (use_stmt) != GIMPLE_PHI)
>>>>> +    return false;
>>>>>
>>>>> checking has_single_use (arg) is enough.  The above is error-prone
>>>>> wrt debug statements.
>>>>>
>>>> [Yuri] Only proposed check is used:
>>>> +  if (!has_single_use (lhs))
>>>> +    return false;
>>>>
>>>>> +  if (reduction_op == PLUS_EXPR &&
>>>>> +      TREE_CODE (r_op2) == SSA_NAME)
>>>>>
>>>>> && goes to the next line
>>>>>
>>>> [Yuri]
>>>> Fixed.
>>>>
>>>>> +  if (TREE_CODE (r_op2) != INTEGER_CST && TREE_CODE (r_op2) != REAL_CST)
>>>>> +    return false;
>>>>>
>>>>> any reason for this check?  The vectorizer can cope with
>>>>> loop invariant non-constant values as well (at least).
>>>>>
>>>> [Yuri]
>>>> This checks were deleted, i.e. any operand is acceptable.
>>>>
>>>>> +  /* Right operand is constant, check that left operand is equal to lhs.  */
>>>>> +  if (SSA_NAME_VAR (lhs) !=  SSA_NAME_VAR (r_op1))
>>>>> +    return false;
>>>>>
>>>>> see above - that looks weird.
>>>>>
>>>> [Yuri]
>>>> This code was deleted.
>>>>> Note that I think you may introduce undefined overflow in
>>>>> unconditionally executing the increment.  So you need to
>>>>> make sure to re-write the increment in unsigned arithmetic
>>>>> (for integral types, that is).
>>>> [Yuri]
>>>> I did not catch your point: if we have
>>>>     if (cond) s += val;
>>>> it will be transformed to
>>>>     s += (cond? val: 0)
>>>> which looks like completely equivalent to original stmt.
>>>
>>> Ah indeed.
>>>
>>>>>
>>>>> Thanks,
>>>>> Richard.
>>>>>
>>>>>
>>>>>
>>>>>> Is it OK for trunk?
>>>>>>
>>>>>> gcc/ChangeLog:
>>>>>> 2014-04-17  Yuri Rumyantsev  <ysrumyan@gmail.com>
>>>>>>
>>>>>> * tree-if-conv.c (is_cond_scalar_reduction): New function.
>>>>>> (convert_scalar_cond_reduction): Likewise.
>>>>>> (predicate_scalar_phi): Add recognition and transformation
>>>>>> of simple conditioanl reduction to be vectorizable.
>>>>>>
>>>>>> gcc/testsuite/ChangeLog:
>>>>>> 2014-04-17  Yuri Rumyantsev  <ysrumyan@gmail.com>
>>>>>>
>>>>>> * gcc.dg/cond-reduc.c: New test.
>>>>
>>>> New patch is added which includes also new test to detect
>>>> vectorization of conditional reduction with non-invariant operand. All
>>>> remarks found by Richard were fixed.
>>>>
>>>> Bootstrap and regression testing did not show any new failures.
>>>> Is it OK for trunk?
>>>
>>> Ok with minor stylistic changes:
>>>
>>> +  struct loop *loop = (gimple_bb (phi))->loop_father;
>>>
>>> no () around the gimple_bb call.
>>>
>>> +  else if (r_op1 !=  PHI_RESULT (header_phi))
>>> +    return false;
>>>
>>> too many spaces after =
>>>
>>> +  c = fold_build_cond_expr (TREE_TYPE (rhs1),
>>> +                           unshare_expr (cond),
>>> +                           swap? zero: op1,
>>> +                           swap? op1: zero);
>>>
>>> a space missing before ?
>>>
>>> +  gsi_insert_before (gsi, new_assign, GSI_SAME_STMT);
>>> +  update_stmt (new_assign);
>>>
>>> gsi_insert_before already calls update_stmt on new_assign, no
>>> reason to do it again.
>>>
>>> +  /* Build rhs for unconditional increment/decrement.  */
>>> +  rhs = build2 (gimple_assign_rhs_code (reduc), TREE_TYPE (rhs1), op0, tmp);
>>>
>>> always use fold_build2, not build2.
>>>
>>> +      if (!is_cond_scalar_reduction (phi, &reduc, &op0, &op1))
>>> +       /* Build new RHS using selected condition and arguments.  */
>>> +       rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
>>> +                                   arg_0, arg_1);
>>> +      else
>>> +       /* Convert reduction stmt into vectorizable form.  */
>>> +       rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
>>> +                                            true_bb != gimple_bb (reduc));
>>>
>>> now that it's a very simple check please use a positive form, thus
>>>
>>>    if (is_cond_scalar_reduction ...)
>>>      * Convert reduction stmt into vectorizable form.  */
>>> ....
>>>    else
>>>
>>> Ok with these changes.
>>>
>>> Thanks,
>>> Richard.
>>>
>>>> gcc/ChangeLog
>>>> 2014-04-29  Yuri Rumyantsev  <ysrumyan@gmail.com>
>>>>
>>>> * tree-if-conv.c (is_cond_scalar_reduction): New function.
>>>> (convert_scalar_cond_reduction): Likewise.
>>>> (predicate_scalar_phi): Add recognition and transformation
>>>> of simple conditioanl reduction to be vectorizable.
>>>>
>>>> gcc/testsuite/ChangeLog:
>>>> * gcc.dg/cond-reduc-1.c: New test.
>>>> * gcc.dg/cond-reduc-2.c: Likewise.