https://gcc.gnu.org/g:a20f4528f3ab84afc2568ea1e208f33fe59bec66
commit r17-2131-ga20f4528f3ab84afc2568ea1e208f33fe59bec66 Author: Philipp Tomsich <[email protected]> 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. Diff: --- gcc/match.pd | 14 +++++++++++ gcc/testsuite/gcc.dg/tree-ssa/pr122569-3.c | 38 ++++++++++++++++++++++++++++++ gcc/tree-ssa-forwprop.cc | 32 +++++++++++++++++++++---- 3 files changed, 80 insertions(+), 4 deletions(-) diff --git a/gcc/match.pd b/gcc/match.pd index 7983211a7930..7da15cc4cdc2 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -12027,6 +12027,20 @@ and, (match (clz_table_index @1 @2 @3) (rshift (mult (msb_or_cascade_64 @1) INTEGER_CST@2) INTEGER_CST@3)) +/* Match count leading zeros for simplify_count_zeroes in forwprop, + variant that isolates the MSB as a power of two via (s - (s >> 1)) + after the OR-cascade. For s = 2^(k+1) - 1 (the cascade output), + (s - (s >> 1)) equals 2^k, so the subsequent DeBruijn + multiply-and-shift is a CTZ-style lookup on the isolated MSB. The + table has to satisfy the direct CTZ DeBruijn property (validated by + the CTZ checkfn in simplify_count_zeroes). + PR tree-optimization/122569. */ +(match (clz_msb_iso_table_index @1 @2 @3) + (rshift (mult + (minus (msb_or_cascade_64@f @1) (rshift @f INTEGER_CST@sub1)) + INTEGER_CST@2) INTEGER_CST@3) + (if (compare_tree_int (@sub1, 1) == 0))) + /* Floatint point/integer comparison and integer->integer or floating point -> float point conversion. */ (match (cond_expr_convert_p @0 @2 @3 @6) diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr122569-3.c b/gcc/testsuite/gcc.dg/tree-ssa/pr122569-3.c new file mode 100644 index 000000000000..51145ed75196 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr122569-3.c @@ -0,0 +1,38 @@ +/* PR tree-optimization/122569 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-forwprop1-details" } */ + +/* Test that the forwprop DeBruijn CLZ matcher recognizes the variant + idiom that isolates the MSB as a power of two via (s - (s >> 1)) + after the OR-cascade. This pattern uses a CTZ-style DeBruijn magic + applied to 2^MSB, not to the all-bits-below value directly. + Reported on PR 122569 as a second reproducer. + + The table element type here is unsigned long (64-bit on LP64 targets) + rather than int, which exercises the relaxed element-type check. */ + +typedef unsigned long long uint64_t; + +void +get_msb_index (unsigned long *result, uint64_t value) +{ + static const unsigned long deBruijnTable64[64] = { + 63, 0, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54, + 33, 42, 3, 61, 51, 37, 40, 49, 18, 28, 20, 55, 30, + 34, 11, 43, 14, 22, 4, 62, 57, 46, 52, 38, 26, 32, + 41, 50, 36, 17, 19, 29, 10, 13, 21, 56, 45, 25, 31, + 35, 16, 9, 12, 44, 24, 15, 8, 23, 7, 6, 5 + }; + + value |= value >> 1; + value |= value >> 2; + value |= value >> 4; + value |= value >> 8; + value |= value >> 16; + value |= value >> 32; + + *result = deBruijnTable64[((value - (value >> 1)) + * (uint64_t) 0x07EDD5E59A4E28C2ULL) >> 58]; +} + +/* { dg-final { scan-tree-dump "__builtin_clz|\\.CLZ" "forwprop1" { target { clzll && { lp64 || llp64 } } } } } */ diff --git a/gcc/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc index 9bb001d2f63b..12c07c99c9bd 100644 --- a/gcc/tree-ssa-forwprop.cc +++ b/gcc/tree-ssa-forwprop.cc @@ -3374,6 +3374,7 @@ check_table (tree ctor, tree type, HOST_WIDE_INT &zero_val, unsigned bits, /* Match.pd function to match the ctz expression. */ extern bool gimple_ctz_table_index (tree, tree *, tree (*)(tree)); extern bool gimple_clz_table_index (tree, tree *, tree (*)(tree)); +extern bool gimple_clz_msb_iso_table_index (tree, tree *, tree (*)(tree)); /* Recognize count leading and trailing zeroes idioms. The canonical form is array[((x & -x) * C) >> SHIFT] where C is a magic @@ -3393,6 +3394,12 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi) gcc_checking_assert (TREE_CODE (array_ref) == ARRAY_REF); internal_fn fn = IFN_LAST; + /* When true, the matched idiom is a CLZ using DeBruijn CTZ on the + isolated MSB -- see clz_msb_iso_table_index in match.pd. The + table stores MSB positions and must satisfy the direct CTZ + DeBruijn property, so we validate it with the CTZ checkfn even + though we emit IFN_CLZ code. */ + bool clz_via_ctz = false; /* For CTZ we recognize ((x & -x) * C) >> SHIFT where the array data represents the number of trailing zeros. */ if (gimple_ctz_table_index (TREE_OPERAND (array_ref, 1), &res_ops[0], NULL)) @@ -3408,6 +3415,17 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi) else if (gimple_clz_table_index (TREE_OPERAND (array_ref, 1), &res_ops[0], NULL)) fn = IFN_CLZ; + /* Variant CLZ idiom: after the OR-cascade sets all bits from 0 to + the original MSB, (value - (value >> 1)) isolates the MSB as a + power of two (2^k), and the subsequent DeBruijn multiply-and-shift + is a CTZ-style lookup on 2^k. The table stores MSB positions + directly. */ + else if (gimple_clz_msb_iso_table_index (TREE_OPERAND (array_ref, 1), + &res_ops[0], NULL)) + { + fn = IFN_CLZ; + clz_via_ctz = true; + } else return false; @@ -3417,9 +3435,13 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi) tree input_type = TREE_TYPE (res_ops[0]); unsigned input_bits = tree_to_shwi (TYPE_SIZE (input_type)); - /* Check the array element type is not wider than 32 bits and the input is - an unsigned 32-bit or 64-bit type. */ - if (TYPE_PRECISION (type) > 32 || !TYPE_UNSIGNED (input_type)) + /* Check the array element type is integral and not wider than 64 bits, + and the input is an unsigned 32-bit or 64-bit type. The table values + are bit positions in [0, input_bits - 1], so any integer element type + with at least 6 bits of precision suffices; the cap is just to keep + the transformation simple. */ + if (!INTEGRAL_TYPE_P (type) || TYPE_PRECISION (type) > 64 + || !TYPE_UNSIGNED (input_type)) return false; if (input_bits != 32 && input_bits != 64) return false; @@ -3441,7 +3463,9 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi) if (!ctor) return false; unsigned HOST_WIDE_INT mulval = tree_to_uhwi (res_ops[1]); - if (fn == IFN_CTZ) + /* CTZ and the MSB-isolation CLZ variant both use the direct CTZ + DeBruijn check (table[(magic << data) >> shift] == data). */ + if (fn == IFN_CTZ || clz_via_ctz) { auto checkfn = [&](unsigned data, unsigned i) -> bool {
