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. */
+ 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],
--
2.54.0 (Apple Git-157)
