On Thu, May 17, 2018 at 2:39 AM, Kugan Vivekanandarajah
<kugan.vivekanandara...@linaro.org> wrote:
> Hi Richard,
>
> On 6 March 2018 at 02:24, Richard Biener <richard.guent...@gmail.com> wrote:
>> On Thu, Feb 8, 2018 at 1:41 AM, Kugan Vivekanandarajah
>> <kugan.vivekanandara...@linaro.org> wrote:
>>> Hi Richard,
>>>
>>> On 1 February 2018 at 23:21, Richard Biener <richard.guent...@gmail.com>
>>> wrote:
>>>> On Thu, Feb 1, 2018 at 5:07 AM, Kugan Vivekanandarajah
>>>> <kugan.vivekanandara...@linaro.org> wrote:
>>>>> Hi Richard,
>>>>>
>>>>> On 31 January 2018 at 21:39, Richard Biener <richard.guent...@gmail.com>
>>>>> wrote:
>>>>>> On Wed, Jan 31, 2018 at 11:28 AM, Kugan Vivekanandarajah
>>>>>> <kugan.vivekanandara...@linaro.org> wrote:
>>>>>>> Hi Richard,
>>>>>>>
>>>>>>> Thanks for the review.
>>>>>>> On 25 January 2018 at 20:04, Richard Biener
>>>>>>> <richard.guent...@gmail.com> wrote:
>>>>>>>> On Wed, Jan 24, 2018 at 10:56 PM, Kugan Vivekanandarajah
>>>>>>>> <kugan.vivekanandara...@linaro.org> wrote:
>>>>>>>>> Hi All,
>>>>>>>>>
>>>>>>>>> Here is a patch for popcount builtin detection similar to LLVM. I
>>>>>>>>> would like to queue this for review for next stage 1.
>>>>>>>>>
>>>>>>>>> 1. This is done part of loop-distribution and effective for -O3 and
>>>>>>>>> above.
>>>>>>>>> 2. This does not distribute loop to detect popcount (like
>>>>>>>>> memcpy/memmove). I dont think that happens in practice. Please correct
>>>>>>>>> me if I am wrong.
>>>>>>>>
>>>>>>>> But then it has no business inside loop distribution but instead is
>>>>>>>> doing final value
>>>>>>>> replacement, right? You are pattern-matching the whole loop after
>>>>>>>> all. I think
>>>>>>>> final value replacement would already do the correct thing if you
>>>>>>>> teached number of
>>>>>>>> iteration analysis that niter for
>>>>>>>>
>>>>>>>> <bb 3> [local count: 955630224]:
>>>>>>>> # b_11 = PHI <b_5(5), b_8(6)>
>>>>>>>> _1 = b_11 + -1;
>>>>>>>> b_8 = _1 & b_11;
>>>>>>>> if (b_8 != 0)
>>>>>>>> goto <bb 6>; [89.00%]
>>>>>>>> else
>>>>>>>> goto <bb 8>; [11.00%]
>>>>>>>>
>>>>>>>> <bb 6> [local count: 850510900]:
>>>>>>>> goto <bb 3>; [100.00%]
>>>>>>>
>>>>>>> I am looking into this approach. What should be the scalar evolution
>>>>>>> for b_8 (i.e. b & (b -1) in a loop) should be? This is not clear to me
>>>>>>> and can this be represented with the scev?
>>>>>>
>>>>>> No, it's not affine and thus cannot be represented. You only need the
>>>>>> scalar evolution of the counting IV which is already handled and
>>>>>> the number of iteration analysis needs to handle the above IV - this
>>>>>> is the missing part.
>>>>> Thanks for the clarification. I am now matching this loop pattern in
>>>>> number_of_iterations_exit when number_of_iterations_exit_assumptions
>>>>> fails. If the pattern matches, I am inserting the _builtin_popcount in
>>>>> the loop preheater and setting the loop niter with this. This will be
>>>>> used by the final value replacement. Is this what you wanted?
>>>>
>>>> No, you shouldn't insert a popcount stmt but instead the niter
>>>> GENERIC tree should be a CALL_EXPR to popcount with the
>>>> appropriate argument.
>>>
>>> Thats what I tried earlier but ran into some ICEs. I wasn't sure if
>>> niter in tree_niter_desc can take such.
>>>
>>> Attached patch now does this. Also had to add support for CALL_EXPR in
>>> few places to handle niter with CALL_EXPR. Does this look OK?
>>
>> Overall this looks ok - the patch includes changes in places that I don't
>> think
>> need changes such as chrec_convert_1 or extract_ops_from_tree.
>> The expression_expensive_p change should be more specific than making
>> all calls inexpensive as well.
>
> Changed it.
>
>>
>> The verify_ssa change looks bogus, you do
>>
>> + dest = gimple_phi_result (count_phi);
>> + tree var = make_ssa_name (TREE_TYPE (dest), NULL);
>> + tree fn = builtin_decl_implicit (BUILT_IN_POPCOUNT);
>> +
>> + var = build_call_expr (fn, 1, src);
>> + *niter = fold_build2 (MINUS_EXPR, TREE_TYPE (dest), var,
>> + build_int_cst (TREE_TYPE (dest), 1));
>>
>> why do you allocate a new SSA name here? It seems unused
>> as you overwrive 'var' with the CALL_EXPR immediately.
> Changed now.
>
>>
>> I didn't review the pattern matching thoroughly nor the exact place you
>> call it. But
>>
>> + if (check_popcount_pattern (loop, &count))
>> + {
>> + niter->assumptions = boolean_false_node;
>> + niter->control.base = NULL_TREE;
>> + niter->control.step = NULL_TREE;
>> + niter->control.no_overflow = false;
>> + niter->niter = count;
>> + niter->assumptions = boolean_true_node;
>> + niter->may_be_zero = boolean_false_node;
>> + niter->max = -1;
>> + niter->bound = NULL_TREE;
>> + niter->cmp = ERROR_MARK;
>> + return true;
>> + }
>>
>> simply setting may_be_zero to false looks fishy.
> Should I set this to (argument to popcount == zero)?
No, I think that's unnecessary. The number of iterations is computed
as: may_be_zero ? 0 : niter;
Here niter is ZERO even when may_be_zero is set to false, and niters
is computed correctly.
I think the point is that may_be_zero is false doesn't imply that
niters is non-zero.
>
>> Try with -fno-tree-loop-ch.
> I changed the pattern matching to handle loop without header copying
> too. Looks a bit complicated checking all the conditions. Wondering if
> this can be done in a simpler and easier to read way.
>
>> Also max should not be negative,
>> it should be the number of bits in the IV type?
>
> Changed this too.
>>
>> A related testcase could be that we can completely peel
>> a loop like the following which iterates at most 8 times:
>>
>> int a[8];
>> void foo (unsigned char ctrl)
>> {
>> int c = 0;
>> while (ctrl)
>> {
>> ctrl = ctrl & (ctrl - 1);
>> a[c++] = ctrl;
>> }
>> }
>
> Hmm, this is an interesting test case but as I am now trying to match
> a loop which does popcount, this is not handled.
>
>
> Attaching the current version for review.
Here are some comments.
> diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
> index 7a54c5f..f390321 100644
> --- a/gcc/tree-ssa-loop-niter.c
> +++ b/gcc/tree-ssa-loop-niter.c
> @@ -2430,6 +2430,134 @@ number_of_iterations_exit_assumptions (struct loop
> *loop, edge exit,
> return (!integer_zerop (niter->assumptions));
> }
>
> +/* See if LOOP is a popcout implementation of the form
> +
> + int c = 0;
> + while (b) {
> + b = b & (b - 1);
> + c++;
> + }
> +
> + If so, Set NITER to __builtin_popcount (b) - 1
> + return true if we did, false otherwise. */
> +
> +static bool
> +check_popcount_pattern (loop_p loop, tree *niter, HOST_WIDE_INT *max)
> +{
> + tree lhs, rhs;
> + tree dest;
> + gimple *and_minus_one;
> + gimple *phi;
> + int count = 0;
> + gimple *count_stmt = NULL;
> + bool adjust = true;
> +
> + if (!single_exit (loop))
> + return false;
> +
> + /* Check loop terminating branch is like
> + if (b != 0). */
> + gimple *stmt = last_stmt (loop->header);
> + if (!stmt
> + || gimple_code (stmt) != GIMPLE_COND
> + || !zerop (gimple_cond_rhs (stmt)))
The check doesn't fully match the comment. NE is not checked here.
Also can move below "(TREE_CODE (lhs) != SSA_NAME)" check up to this
point, making simple checks earlier.
> + return false;
> +
> + /* Check the loop closed SSA definition for just the variable c defined in
> + loop. */
> + basic_block bb = single_exit (loop)->dest;
single_exit is repeatedly called various times, call it once and use
the returning edge instead? I am not sure GCC is smart enough
removing repeated call instances. Same to loop_latch_edge.
> + for (gphi_iterator gpi = gsi_start_phis (bb);
> + !gsi_end_p (gpi); gsi_next (&gpi))
> + {
> + phi = gpi.phi ();
> + count++;
> + }
> +
> + if (count != 1)
> + return false;
> +
> + rhs = gimple_phi_arg_def (phi, single_exit (loop)->dest_idx);
> + if (TREE_CODE (rhs) != SSA_NAME)
> + return false;
> + count_stmt = SSA_NAME_DEF_STMT (rhs);
> + lhs = gimple_cond_lhs (stmt);
> + if (TREE_CODE (lhs) != SSA_NAME)
> + return false;
> + gimple *and_stmt = SSA_NAME_DEF_STMT (lhs);
> +
> + /* Depending on copy-header is performed, feeding PHI stmts might be in
> + the loop header or loop exit, handle this. */
> + if (gimple_code (count_stmt) == GIMPLE_PHI)
> + {
> + tree t;
> + if (gimple_code (and_stmt) != GIMPLE_PHI
> + || gimple_bb (and_stmt) != single_exit (loop)->src
> + || gimple_bb (count_stmt) != single_exit (loop)->src)
> + return false;
> + t = gimple_phi_arg_def (count_stmt, loop_latch_edge (loop)->dest_idx);
> + if (TREE_CODE (t) != SSA_NAME)
> + return false;
> + count_stmt = SSA_NAME_DEF_STMT (t);
> + t = gimple_phi_arg_def (and_stmt, loop_latch_edge (loop)->dest_idx);
> + if (TREE_CODE (t) != SSA_NAME)
> + return false;
> + and_stmt = SSA_NAME_DEF_STMT (t);
> + adjust = false;
> + }
> +
> + /* Make sure we have a count by one. */
> + if (!is_gimple_assign (count_stmt)
> + || (gimple_assign_rhs_code (count_stmt) != PLUS_EXPR)
> + || !integer_onep (gimple_assign_rhs2 (count_stmt)))
> + return false;
> +
> + /* Cheeck "b = b & (b - 1)" is calculated. */
Typo.
> + if (!is_gimple_assign (and_stmt)
> + || gimple_assign_rhs_code (and_stmt) != BIT_AND_EXPR)
> + return false;
> +
> + lhs = gimple_assign_rhs1 (and_stmt);
> + rhs = gimple_assign_rhs2 (and_stmt);
> + if (TREE_CODE (lhs) == SSA_NAME
> + && (and_minus_one = SSA_NAME_DEF_STMT (lhs))
> + && is_gimple_assign (and_minus_one)
> + && (gimple_assign_rhs_code (and_minus_one) == PLUS_EXPR)
> + && integer_minus_onep (gimple_assign_rhs2 (and_minus_one)))
> + lhs = rhs;
> + else if (TREE_CODE (rhs) == SSA_NAME
> + && (and_minus_one = SSA_NAME_DEF_STMT (rhs))
> + && is_gimple_assign (and_minus_one)
> + && (gimple_assign_rhs_code (and_minus_one) == PLUS_EXPR)
> + && integer_minus_onep (gimple_assign_rhs2 (and_minus_one)))
Could you avoid duplication by factoring the condition into an inline
function? They are exactly the same for lhs/rhs.
> + ;
> + else
> + return false;
> +
> + if ((gimple_assign_rhs1 (and_stmt) != gimple_assign_rhs1 (and_minus_one))
> + && (gimple_assign_rhs2 (and_stmt) != gimple_assign_rhs1
> (and_minus_one)))
Here you already got lhs correctly, so don't need to check on and_stmt
rhs directly. You can even merge this check into above one.
> + return false;
> +
> + /* Check the recurrence. */
> + phi = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (and_minus_one));
> + gimple *src_phi = SSA_NAME_DEF_STMT (lhs);
> + if (gimple_code (phi) != GIMPLE_PHI
> + || gimple_code (src_phi) != GIMPLE_PHI)
I think this is redundant since you have lhs equals to
gimple_assign_rhs1 (and_minus_one). So phi == src_phi is always true?
> + return false;
> +
> + dest = gimple_assign_lhs (count_stmt);
> + tree fn = builtin_decl_implicit (BUILT_IN_POPCOUNT);
> + tree src = gimple_phi_arg_def (src_phi, loop_preheader_edge
> (loop)->dest_idx);
> + if (adjust)
> + *niter = fold_build2 (MINUS_EXPR, TREE_TYPE (dest),
> + build_call_expr (fn, 1, src),
> + build_int_cst (TREE_TYPE (dest), 1));
> + else
> + *niter = build_call_expr (fn, 1, src);
> + *max = int_cst_value (TYPE_MAX_VALUE (TREE_TYPE (dest)));
> + return true;
> +}
> +
> +
> /* Like number_of_iterations_exit_assumptions, but return TRUE only if
> the niter information holds unconditionally. */
>
> @@ -2441,7 +2569,25 @@ number_of_iterations_exit (struct loop *loop, edge
> exit,
> gcond *stmt;
> if (!number_of_iterations_exit_assumptions (loop, exit, niter,
> &stmt, every_iteration))
> - return false;
> + {
> + tree count;
> + HOST_WIDE_INT max;
> + if (check_popcount_pattern (loop, &count, &max))
> + {
> + niter->assumptions = boolean_false_node;
> + niter->control.base = NULL_TREE;
> + niter->control.step = NULL_TREE;
> + niter->control.no_overflow = false;
> + niter->niter = count;
> + niter->assumptions = boolean_true_node;
> + niter->may_be_zero = boolean_false_node;
> + niter->max = max;
> + niter->bound = NULL_TREE;
> + niter->cmp = ERROR_MARK;
> + return true;
> + }
Better to merge these compound statement into check_popcount_pattern
and rename it into something like number_of_iterations_popcount.
I wondered if the more inefficient version popcount should be checked, like:
int count = 0;
while (x)
{
count += x & 1;
x = x >> 1;
}
Thanks,
bin
> + return false;
> + }
>
> if (integer_nonzerop (niter->assumptions))
> return true;
> --
> 2.7.4
>
