[Bug tree-optimization/112566] New: Some ctz/popcount/parity/ffs optimizations

[Bug tree-optimization/112566] New: Some ctz/popcount/parity/ffs optimizations

[jakub at gcc dot gnu.org]

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

            Bug ID: 112566
           Summary: Some ctz/popcount/parity/ffs optimizations
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: jakub at gcc dot gnu.org
  Target Milestone: ---

I believe
ctz(ext(x)) == ctz(x) if UB on zero,
popcount(zext(x)) == popcount(x),
parity(zext(x)) == parity(x),
parity(sext(x)) == parity(x) if the extension is by even number of bits and
ffs(ext(x)) == ffs(x).

So, e.g. with x86 -O2 -m32 -mbmi2 -mlzcnt -mpopcnt
int foo (unsigned int x) { return __builtin_ctzll (x); }
int bar (unsigned int x) { return __builtin_popcountll (x); }
int baz (unsigned int x) { return __builtin_parityll (x); }
int qux (int x) { return __builtin_ffsll (x); }
int corge (int x) { return __builtin_ctzll (x); }
int garply (int x) { return __builtin_parityll (x); }
int fred (unsigned int x) { return __builtin_ffsll (x); }
shouldn't use any double-word bit query, or similarly
int foo (unsigned _BitInt(256) x) { return __builtin_ctzg ((unsigned
_BitInt(512)) x); }
int bar (unsigned _BitInt(256) x) { return __builtin_popcountg ((unsigned
_BitInt(512)) x); }
int baz (unsigned _BitInt(256) x) { return __builtin_parityg ((unsigned
_BitInt(512)) x); }
int qux (_BitInt(256) x) { return __builtin_ffsg ((_BitInt(512)) x); }
int corge (_BitInt(256) x) { return __builtin_ctzg ((unsigned _BitInt(512)) x);
}
int garply (_BitInt(256) x) { return __builtin_parityg ((unsigned _BitInt(512))
x); }
int fred (unsigned _BitInt(256) x) { return __builtin_ffsg ((_BitInt(512)) x);
}
Of course, we shouldn't do this if we deoptimize some supported precision into
an unsupported narrower one.

For clz(zext(x)) = clz(x)+difference_in_precision, but at that point it might
not be a win.

[Bug tree-optimization/112566] Some ctz/popcount/parity/ffs optimizations

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jsm28 at gcc dot gnu.org

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
The idea came from looking at Joseph's stdbit.h proposed implementation, which
sometimes in the type-generic macros just uses the long long version
unconditionally.

[Bug tree-optimization/112566] Some ctz/popcount/parity/ffs optimizations

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2023-11-16
             Status|UNCONFIRMED                 |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |jakub at gcc dot gnu.org

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 56605
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=56605&action=edit
gcc14-pr112566.patch

Untested implementation.

[Bug tree-optimization/112566] Some ctz/popcount/parity/ffs optimizations

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=83171

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
>popcount(zext(x)) == popcount(x),
That is PR 83171 .

[Bug tree-optimization/112566] Some ctz/popcount/parity/ffs optimizations

[joseph at codesourcery dot com]

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

--- Comment #4 from joseph at codesourcery dot com <joseph at codesourcery dot com> ---
On Thu, 16 Nov 2023, jakub at gcc dot gnu.org via Gcc-bugs wrote:

> ctz(ext(x)) == ctz(x) if UB on zero,

In one direction, this should also be true for a narrowing conversion 
(changing ctz(narrow(x)) to ctz(x) might remove UB if x is nonzero but 
narrows to zero, but won't introduce UB, or change the result if narrow(x) 
is nonzero).

[Bug tree-optimization/112566] Some ctz/popcount/parity/ffs optimizations

[cvs-commit at gcc dot gnu.org]

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

--- Comment #5 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:6dd4c703be17fa5dd56136d067e7fdc4a61584b3

commit r14-5557-g6dd4c703be17fa5dd56136d067e7fdc4a61584b3
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Fri Nov 17 15:10:51 2023 +0100

    match.pd: Optimize ctz/popcount/parity/ffs on extended argument [PR112566]

    ctz(ext(X)) is the same as ctz(X) in the UB on zero case (or could be also
    in the 2 argument case on large BITINT_TYPE by preserving the argument, not
    implemented in this patch),
    popcount(zext(X)) is the same as popcount(X),
    parity(zext(X)) is the same as parity(X),
    parity(sext(X)) is the same as parity(X) provided the bit difference
between
    the extended and unextended types is even,
    ffs(ext(X)) is the same as ffs(X).

    The following patch optimizes those in match.pd if those are beneficial
    (always in the large BITINT_TYPE case, or if the narrower type has optab
    and the wider doesn't, or the wider is larger than word and narrower is
    one of the standard argument sizes (tested just int and long long, as
    long is on most targets same bitsize as one of those two).

    Joseph in the PR mentioned that ctz(narrow(X)) is the same as ctz(X)
    if UB on 0, but that can be handled incrementally (and would need different
    decisions when it is profitable).
    And clz(zext(X)) is clz(X) + bit_difference, but not sure we want to change
    that in match.pd at all, perhaps during insn selection?

    2023-11-17  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/112566
            PR tree-optimization/83171
            * match.pd (ctz(ext(X)) -> ctz(X), popcount(zext(X)) ->
popcount(X),
            parity(ext(X)) -> parity(X), ffs(ext(X)) -> ffs(X)): New
            simplifications.
            ( __builtin_ffs (X) == 0 -> X == 0): Use FFS rather than
            BUILT_IN_FFS BUILT_IN_FFSL BUILT_IN_FFSLL BUILT_IN_FFSIMAX.

            * gcc.dg/pr112566-1.c: New test.
            * gcc.dg/pr112566-2.c: New test.
            * gcc.target/i386/pr78057.c (foo): Pass another long long argument
            and use it in __builtin_ia32_*zcnt_u64 instead of the int one.