On Tue, Apr 29, 2014 at 4:29 PM, Yuri Rumyantsev <ysrum...@gmail.com> wrote:
> 2014-04-28 16:16 GMT+04:00 Richard Biener <richard.guent...@gmail.com>:
>> On Thu, Apr 17, 2014 at 3:09 PM, Yuri Rumyantsev <ysrum...@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 <ysrum...@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 <ysrum...@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 <ysrum...@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.
