https://gcc.gnu.org/g:5b15a757b8e8e10366e8068e0cd000baa7b7315e
commit r17-5397-g5b15a757b8e8e10366e8068e0cd000baa7b7315e Author: Kyrylo Tkachov <[email protected]> Date: Wed Oct 7 01:38:42 2026 -0700 forwprop: Select a table zero entry outside int in the table type simplify_count_zeroes accepts table elements of up to 64 bits, but computes the value for a zero input in int. A table entry outside the int range is truncated: with a long long table whose entry for a zero input is 0x100000005, the recognized count returns 5 for a zero input. For a CLZ table the value is also subtracted from 31 or 63 in int. For a long long entry of 0x80000000 forwprop1 emits _4 = .CLZ (x_1(D), 32); _5 = x_1(D) == 0; _6 = _5 ? -2147483617 : _4; _7 = 31 - _6; _3 = (long long int) _7; where 31 - _6 overflows for a zero X. If the entry does not survive the computation in int, select it after the conversion to the type of the table, as Richard Biener suggested: _4 = .CLZ (x_1(D), 32); _5 = 31 - _4; _6 = (long long int) _5; _7 = x_1(D) == 0; _3 = _7 ? 2147483648 : _6; Bootstrapped and tested on aarch64-none-linux-gnu and x86_64-linux. gcc/ChangeLog: * tree-ssa-forwprop.cc (simplify_count_zeroes): If the table entry for zero does not survive the computation in int, select it in the type of the table after the conversion. gcc/testsuite/ChangeLog: * gcc.dg/torture/clz-ctz-table-2.c: New test. * gcc.dg/tree-ssa/clz-ctz-table-3.c: New test. Signed-off-by: Kyrylo Tkachov <[email protected]> Diff: --- gcc/testsuite/gcc.dg/torture/clz-ctz-table-2.c | 64 +++++++++++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/clz-ctz-table-3.c | 56 ++++++++++++++++++++++ gcc/tree-ssa-forwprop.cc | 33 +++++++++++-- 3 files changed, 150 insertions(+), 3 deletions(-) diff --git a/gcc/testsuite/gcc.dg/torture/clz-ctz-table-2.c b/gcc/testsuite/gcc.dg/torture/clz-ctz-table-2.c new file mode 100644 index 000000000000..09d27c55666d --- /dev/null +++ b/gcc/testsuite/gcc.dg/torture/clz-ctz-table-2.c @@ -0,0 +1,64 @@ +/* { dg-do run } */ +/* { dg-require-effective-target int32plus } */ + +/* The table entries for a zero input do not survive the computation of + the recognized counts in int. They are selected in the type of the + table. */ + +static const long long tab[64] = { + 0x100000005LL, 0, 0, 0, 3, 0, 0, 20, 0, 4, 0, 11, 7, 0, 0, 21, + 30, 1, 0, 5, 28, 0, 12, 0, 17, 8, 0, 14, 0, 0, 0, 22, + 31, 0, 2, 19, 0, 10, 6, 0, 29, 0, 27, 0, 16, 13, 0, 0, + 0, 18, 9, 0, 0, 26, 15, 0, 0, 0, 25, 0, 0, 24, 23, 0 }; + +__attribute__((noipa)) long long +f (unsigned v) +{ + return tab[((unsigned) ((v & -v) * 0x2265b1f5U)) >> 26]; +} + +/* The CLZ table entry fits int only after it is subtracted from 31. */ + +static const long long tab2[64] = { + 0x80000000LL, 29, 0, 6, 0, 12, 0, 0, 2, 0, 5, 0, 1, 0, 0, 0, + 0, 31, 0, 0, 25, 0, 16, 26, 0, 22, 0, 17, 8, 27, 0, 0, + 0, 23, 14, 20, 0, 18, 0, 9, 0, 28, 0, 11, 0, 4, 0, 0, + 0, 30, 24, 15, 0, 21, 7, 0, 0, 13, 19, 0, 0, 0, 10, 3 }; + +__attribute__((noipa)) long long +g (unsigned x) +{ + x |= x >> 1; + x |= x >> 2; + x |= x >> 4; + x |= x >> 8; + x |= x >> 16; + return tab2[(x * 0xbb968a43U) >> 26]; +} + +/* The unsigned entry does not fit int. */ + +static const unsigned tab3[64] = { + 0xffffffffU, 0, 0, 0, 3, 0, 0, 20, 0, 4, 0, 11, 7, 0, 0, 21, + 30, 1, 0, 5, 28, 0, 12, 0, 17, 8, 0, 14, 0, 0, 0, 22, + 31, 0, 2, 19, 0, 10, 6, 0, 29, 0, 27, 0, 16, 13, 0, 0, + 0, 18, 9, 0, 0, 26, 15, 0, 0, 0, 25, 0, 0, 24, 23, 0 }; + +__attribute__((noipa)) unsigned +h (unsigned v) +{ + return tab3[((unsigned) ((v & -v) * 0x2265b1f5U)) >> 26]; +} + +int +main (void) +{ + if (f (0) != 0x100000005LL || f (1) != 0 || f (0x80000000U) != 31) + __builtin_abort (); + if (g (0) != 0x80000000LL || g (1) != 0 || g (0x80000000U) != 31 + || g (0x1234) != 12) + __builtin_abort (); + if (h (0) != 0xffffffffU || h (1) != 0 || h (0x80000000U) != 31) + __builtin_abort (); + return 0; +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/clz-ctz-table-3.c b/gcc/testsuite/gcc.dg/tree-ssa/clz-ctz-table-3.c new file mode 100644 index 000000000000..4205b495a054 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/clz-ctz-table-3.c @@ -0,0 +1,56 @@ +/* { dg-do compile } */ +/* { dg-require-effective-target int32 } */ +/* { dg-require-effective-target clzsi } */ +/* { dg-require-effective-target ctzsi } */ +/* { dg-options "-O2 -fdump-tree-forwprop1" } */ + +/* The table entries for a zero input do not fit the counts in int. The + lookups still become counts. */ + +static const long long tab[64] = { + 0x100000005LL, 0, 0, 0, 3, 0, 0, 20, 0, 4, 0, 11, 7, 0, 0, 21, + 30, 1, 0, 5, 28, 0, 12, 0, 17, 8, 0, 14, 0, 0, 0, 22, + 31, 0, 2, 19, 0, 10, 6, 0, 29, 0, 27, 0, 16, 13, 0, 0, + 0, 18, 9, 0, 0, 26, 15, 0, 0, 0, 25, 0, 0, 24, 23, 0 }; + +__attribute__((noipa)) long long +f (unsigned v) +{ + return tab[((unsigned) ((v & -v) * 0x2265b1f5U)) >> 26]; +} + +/* The CLZ table entry fits int only after it is subtracted from 31. */ + +static const long long tab2[64] = { + 0x80000000LL, 29, 0, 6, 0, 12, 0, 0, 2, 0, 5, 0, 1, 0, 0, 0, + 0, 31, 0, 0, 25, 0, 16, 26, 0, 22, 0, 17, 8, 27, 0, 0, + 0, 23, 14, 20, 0, 18, 0, 9, 0, 28, 0, 11, 0, 4, 0, 0, + 0, 30, 24, 15, 0, 21, 7, 0, 0, 13, 19, 0, 0, 0, 10, 3 }; + +__attribute__((noipa)) long long +g (unsigned x) +{ + x |= x >> 1; + x |= x >> 2; + x |= x >> 4; + x |= x >> 8; + x |= x >> 16; + return tab2[(x * 0xbb968a43U) >> 26]; +} + +/* The unsigned entry does not fit int. */ + +static const unsigned tab3[64] = { + 0xffffffffU, 0, 0, 0, 3, 0, 0, 20, 0, 4, 0, 11, 7, 0, 0, 21, + 30, 1, 0, 5, 28, 0, 12, 0, 17, 8, 0, 14, 0, 0, 0, 22, + 31, 0, 2, 19, 0, 10, 6, 0, 29, 0, 27, 0, 16, 13, 0, 0, + 0, 18, 9, 0, 0, 26, 15, 0, 0, 0, 25, 0, 0, 24, 23, 0 }; + +__attribute__((noipa)) unsigned +h (unsigned v) +{ + return tab3[((unsigned) ((v & -v) * 0x2265b1f5U)) >> 26]; +} + +/* { dg-final { scan-tree-dump-times {\.CTZ \(} 2 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times {\.CLZ \(} 1 "forwprop1" } } */ diff --git a/gcc/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc index d840a68a00c5..88f69e12ed19 100644 --- a/gcc/tree-ssa-forwprop.cc +++ b/gcc/tree-ssa-forwprop.cc @@ -3515,6 +3515,16 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi) return false; } + /* The sequence below computes the result in int, for a CLZ as + INPUT_BITS - 1 minus the count. If the table entry for zero does not + survive that, select it in TYPE after the conversion instead. */ + HOST_WIDE_INT table_zero = zero_val; + bool late_select + = (!wi::fits_to_tree_p (zero_val, integer_type_node) + || (fn == IFN_CLZ + && !wi::fits_to_tree_p (input_bits - 1 - zero_val, + integer_type_node))); + HOST_WIDE_INT ctz_val = -1; bool zero_ok; if (fn == IFN_CTZ) @@ -3528,7 +3538,8 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi) ctz_val = 32; zero_ok = CLZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (input_type), ctz_val) == 2; - zero_val = input_bits - 1 - zero_val; + if (!late_select) + zero_val = input_bits - 1 - zero_val; } /* Pass the value at zero only if the target defines it; otherwise the COND_EXPR below supplies the result for zero. */ @@ -3546,6 +3557,7 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi) zero_val = 0; ctz_val = 0; nargs = 1; + late_select = false; } gimple_seq seq = NULL; @@ -3560,7 +3572,7 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi) tree prev_lhs = gimple_call_lhs (call); - if (zero_ok && zero_val == ctz_val) + if (late_select || (zero_ok && zero_val == ctz_val)) ; /* Emit ctz (x) & 31 if ctz (0) is 32 but we need to return 0. */ else if (zero_ok && zero_val == 0 && ctz_val == input_bits) @@ -3602,7 +3614,22 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi) prev_lhs = gimple_assign_lhs (g); } - g = gimple_build_assign (gimple_assign_lhs (stmt), NOP_EXPR, prev_lhs); + if (late_select) + { + g = gimple_build_assign (make_ssa_name (type), NOP_EXPR, prev_lhs); + gimple_set_location (g, gimple_location (stmt)); + gimple_seq_add_stmt (&seq, g); + prev_lhs = gimple_assign_lhs (g); + g = gimple_build_assign (make_ssa_name (boolean_type_node), EQ_EXPR, + res_ops[0], build_zero_cst (input_type)); + gimple_set_location (g, gimple_location (stmt)); + gimple_seq_add_stmt (&seq, g); + g = gimple_build_assign (gimple_assign_lhs (stmt), COND_EXPR, + gimple_assign_lhs (g), + build_int_cst (type, table_zero), prev_lhs); + } + else + g = gimple_build_assign (gimple_assign_lhs (stmt), NOP_EXPR, prev_lhs); gimple_seq_add_stmt (&seq, g); gsi_replace_with_seq (gsi, seq, true); return true;
