gnu/gcc/a20f4528f3ab84afc2568ea1e208f33fe59bec66 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.
3 files changed