On Tue, 13 Oct 2026, [email protected] wrote: > From: Kyrylo Tkachov <[email protected]> > > 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, > which overflows for a long long entry of 0x80000000. > > Do not replace the table lookup in these cases. An entry that is only > truncated to a type that is not wider than int, such as 0xffffffff in > an unsigned int CTZ table, is still handled. > > Bootstrapped and tested on aarch64-none-linux-gnu and x86_64-linux. > > gcc/ChangeLog: > > * tree-ssa-forwprop.cc (simplify_count_zeroes): Fail if the > value at zero does not survive the computation in int. > > gcc/testsuite/ChangeLog: > > * gcc.dg/torture/clz-ctz-table-2.c: New test. > > Signed-off-by: Kyrylo Tkachov <[email protected]> > --- > .../gcc.dg/torture/clz-ctz-table-2.c | 64 +++++++++++++++++++ > gcc/tree-ssa-forwprop.cc | 11 ++++ > 2 files changed, 75 insertions(+) > create mode 100644 gcc/testsuite/gcc.dg/torture/clz-ctz-table-2.c > > 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 00000000000..7921b6cb7c5 > --- /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. */ > + > +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, but the conversion back to > + unsigned restores it. */ > + > +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/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc > index fba4387f503..4698839c62e 100644 > --- a/gcc/tree-ssa-forwprop.cc > +++ b/gcc/tree-ssa-forwprop.cc > @@ -3528,6 +3528,10 @@ 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; > + /* The sequence below computes the value at zero in int, as > + INPUT_BITS - 1 minus the value that it selects for zero. */
I don't quite understand why we cannot compute the "correct" zero_val from the table element. The tab2 the correct zero value is 0x80000000LL, so instead of emitting _16 = .CLZ (x_8(D), 32); _17 = x_8(D) == 0; _18 = _17 ? -2147483617 : _16; _19 = 31 - _18; _15 = (long long int) _19; we can emit _15 = _17 ? 0x80000000LL : (long long int) _19; ? > + if (!wi::fits_to_tree_p (zero_val, integer_type_node)) > + return false; > zero_val = input_bits - 1 - zero_val; > } > int nargs = 2; > @@ -3546,6 +3550,13 @@ simplify_count_zeroes (gimple_stmt_iterator *gsi) > nargs = 1; > } > > + /* The sequence below computes the value at zero in int and converts it > + to TYPE, which keeps it for a CTZ if TYPE is not wider than int. */ > + if (!wi::fits_to_tree_p (zero_val, integer_type_node) > + && (fn == IFN_CLZ > + || TYPE_PRECISION (type) > TYPE_PRECISION (integer_type_node))) > + return false; > + > gimple_seq seq = NULL; > gimple *g; > gcall *call = gimple_build_call_internal (fn, nargs, res_ops[0], > -- Richard Biener <[email protected]> SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg, Germany; GF: Stefan Gaiser, Jochen Jaser, Abhinav Puri; (HRB 36809, AG Nuernberg)
