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

[Richard Biener <richard dot guenther at gmail dot 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.