[RFC][PR82479] missing popcount builtin detection

[Kugan Vivekanandarajah]

Hi Richard,

Thanks for the review.
On 25 January 2018 at 20:04, Richard Biener <richard.guenther@gmail.com> wrote:
> On Wed, Jan 24, 2018 at 10:56 PM, Kugan Vivekanandarajah
> <kugan.vivekanandarajah@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?

Thanks,
Kugan
>
> is related to popcount (b_5).
>
> Richard.
>
>> Bootstrapped and regression tested on aarch64-linux-gnu with no new regressions.
>>
>> Thanks,
>> Kugan
>>
>> gcc/ChangeLog:
>>
>> 2018-01-25  Kugan Vivekanandarajah  <kuganv@linaro.org>
>>
>>     PR middle-end/82479
>>     * tree-loop-distribution.c (handle_popcount): New.
>>     (pass_loop_distribution::execute): Use handle_popcount.
>>
>> gcc/testsuite/ChangeLog:
>>
>> 2018-01-25  Kugan Vivekanandarajah  <kuganv@linaro.org>
>>
>>     PR middle-end/82479
>>     * gcc.dg/tree-ssa/popcount.c: New test.