[Bug tree-optimization/122569] Fails to pattern match ctz/clz from DeBruijn

[cvs-commit at gcc dot gnu.org]

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

--- Comment #11 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Philipp Tomsich <ptomsich@gcc.gnu.org>:

https://gcc.gnu.org/g:a20f4528f3ab84afc2568ea1e208f33fe59bec66

commit r17-2131-ga20f4528f3ab84afc2568ea1e208f33fe59bec66
Author: Philipp Tomsich <philipp.tomsich@vrull.eu>
Date:   Fri May 8 19:24:58 2026 +0200

    tree-optimization/122569 - recognize CLZ via isolated MSB DeBruijn lookup

    Recognize a CLZ idiom where the OR-cascade is followed by
    (value - (value >> 1)) to isolate the MSB as a power of two (2^k), then
    a DeBruijn multiply-and-shift maps 2^k back to k:

      value |= value >> 1;
      ...
      value |= value >> 32;
      result = table[((value - (value >> 1)) * MAGIC) >> 58];

    After the cascade value is 2^(k+1) - 1, so (value - (value >> 1)) is 2^k
    and the multiply-and-shift is a CTZ-style DeBruijn lookup whose table
    satisfies table[(magic << k) >> shift] == k.

    Add match.pd pattern clz_msb_iso_table_index on top of the
    msb_or_cascade_64 helper, so it only spells out the (s - (s >> 1))
    isolation and the DeBruijn shape.  simplify_count_zeroes validates the
    table with the existing CTZ checkfn (the direct-form check) but emits
    IFN_CLZ; both forms store MSB positions, so the CLZ path including
    zero_val pre-compensation is unchanged.

    Relax the element-type check from "precision <= 32" to "integral and
    precision <= 64" so tables declared as unsigned long (64-bit on LP64)
    are accepted; the values are bit positions and fit any integer type.

    Only a 64-bit variant is added; all known uses (Stockfish, zstd,
    cpython, the PR122569 comment 3 reproducer) are 64-bit.

    gcc/ChangeLog:

            PR tree-optimization/122569
            * match.pd (clz_msb_iso_table_index): New match pattern.
            * tree-ssa-forwprop.cc (gimple_clz_msb_iso_table_index): Declare.
            (simplify_count_zeroes): Recognize the new pattern; route its
            table validation through the CTZ checkfn.  Relax the element
            type check to accept integer types up to 64 bits.

    gcc/testsuite/ChangeLog:

            PR tree-optimization/122569
            * gcc.dg/tree-ssa/pr122569-3.c: New test.