[Bug tree-optimization/95771] New: Failure to optimize popcount idiom when argument is unsigned char

[Bug tree-optimization/95771] New: Failure to optimize popcount idiom when argument is unsigned char

[gabravier at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95771

            Bug ID: 95771
           Summary: Failure to optimize popcount idiom when argument is
                    unsigned char
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: gabravier at gmail dot com
  Target Milestone: ---

int f(unsigned char x)
{
    int i = 0;
    while (x)
    {
        x &= x - 1;
        ++i;
    }
    return i;
}

This can be optimized to __builtin_popcount(x). LLVM does this transformation,
but GCC does not.

PS : GCC does this optimization if x is int and a few other types. I've also
seen that GCC does not do this optimization for __int128 (which it could do
with adding a popcount of the low and high parts of x).

[Bug tree-optimization/95771] Failure to optimize popcount idiom when argument is unsigned char

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95771

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |jakub at gcc dot gnu.org
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2021-01-02

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 49868
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=49868&action=edit
gcc11-pr95771.patch

Untested fix.

[Bug tree-optimization/95771] Failure to optimize popcount idiom when argument is unsigned char

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95771

--- Comment #2 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jakub Jelinek <jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:24cd9afe617a39801d190418cf3fbab3bc3742a7

commit r11-6443-g24cd9afe617a39801d190418cf3fbab3bc3742a7
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Mon Jan 4 14:36:06 2021 +0100

    loop-niter: Recognize popcount idioms even with char, short and __int128
[PR95771]

    As the testcase shows, we punt unnecessarily on popcount loop idioms if
    the type is smaller than int or larger than long long.
    Smaller type than int can be handled by zero-extending the argument to
    unsigned int, and types twice as long as long long by doing
    __builtin_popcountll on both halves of the __int128.

    2020-01-04  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/95771
            * tree-ssa-loop-niter.c (number_of_iterations_popcount): Handle
types
            with precision smaller than int's precision and types with
precision
            twice as large as long long.  Formatting fixes.

            * gcc.target/i386/pr95771.c: New test.

[Bug tree-optimization/95771] Failure to optimize popcount idiom when argument is unsigned char

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95771

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Should be fixed now, except that for __uint128_t we aren't able to optimize
away the conditional in if (x) return __builtin_popcountll (x >> 64) +
__builtin_popcountll (x); else return 0; - the phiopt popcount/clz/ctz
conditional removal isn't able to deal with the two popcounts added + shift and
cast.