This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


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: cond-reduc.patch.2
Description: Binary data


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]