From ba6557e2686306942b157c3350e7497e551afb80 Mon Sep 17 00:00:00 2001 From: Roger Sayle Date: Thu, 24 May 2018 20:47:03 +0000 Subject: [PATCH] fold-const.c (tree_nonzero_bits): New function. * fold-const.c (tree_nonzero_bits): New function. * fold-const.h (tree_nonzero_bits): Likewise. * match.pd (POPCOUNT): New patterns to fold BUILTIN_POPCOUNT and friends. POPCOUNT(x&1) => x&1, POPCOUNT(x)==0 => x==0, etc. * gcc.dg/fold-popcount-1.c: New testcase. * gcc.dg/fold-popcount-2.c: New testcase. * gcc.dg/fold-popcount-3.c: New testcase. * gcc.dg/fold-popcount-4.c: New testcase. From-SVN: r260689 --- gcc/ChangeLog | 7 +++ gcc/fold-const.c | 68 ++++++++++++++++++++++++++ gcc/fold-const.h | 1 + gcc/match.pd | 20 ++++++++ gcc/testsuite/ChangeLog | 7 +++ gcc/testsuite/gcc.dg/fold-popcount-1.c | 35 +++++++++++++ gcc/testsuite/gcc.dg/fold-popcount-2.c | 35 +++++++++++++ gcc/testsuite/gcc.dg/fold-popcount-3.c | 10 ++++ gcc/testsuite/gcc.dg/fold-popcount-4.c | 50 +++++++++++++++++++ 9 files changed, 233 insertions(+) create mode 100644 gcc/testsuite/gcc.dg/fold-popcount-1.c create mode 100644 gcc/testsuite/gcc.dg/fold-popcount-2.c create mode 100644 gcc/testsuite/gcc.dg/fold-popcount-3.c create mode 100644 gcc/testsuite/gcc.dg/fold-popcount-4.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 1ae5e34e460..b2ce6864e1d 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,10 @@ +2018-05-24 Roger Sayle + + * fold-const.c (tree_nonzero_bits): New function. + * fold-const.h (tree_nonzero_bits): Likewise. + * match.pd (POPCOUNT): New patterns to fold BUILTIN_POPCOUNT and + friends. POPCOUNT(x&1) => x&1, POPCOUNT(x)==0 => x==0, etc. + 2018-05-24 H.J. Lu PR target/85900 diff --git a/gcc/fold-const.c b/gcc/fold-const.c index dc277440aa9..0f57f078199 100644 --- a/gcc/fold-const.c +++ b/gcc/fold-const.c @@ -14571,6 +14571,74 @@ c_getstr (tree src, unsigned HOST_WIDE_INT *strlen) return string + offset; } +/* Given a tree T, compute which bits in T may be nonzero. */ + +wide_int +tree_nonzero_bits (const_tree t) +{ + switch (TREE_CODE (t)) + { + case INTEGER_CST: + return wi::to_wide (t); + case SSA_NAME: + return get_nonzero_bits (t); + case NON_LVALUE_EXPR: + case SAVE_EXPR: + return tree_nonzero_bits (TREE_OPERAND (t, 0)); + case BIT_AND_EXPR: + return wi::bit_and (tree_nonzero_bits (TREE_OPERAND (t, 0)), + tree_nonzero_bits (TREE_OPERAND (t, 1))); + case BIT_IOR_EXPR: + case BIT_XOR_EXPR: + return wi::bit_or (tree_nonzero_bits (TREE_OPERAND (t, 0)), + tree_nonzero_bits (TREE_OPERAND (t, 1))); + case COND_EXPR: + return wi::bit_or (tree_nonzero_bits (TREE_OPERAND (t, 1)), + tree_nonzero_bits (TREE_OPERAND (t, 2))); + CASE_CONVERT: + return wide_int::from (tree_nonzero_bits (TREE_OPERAND (t, 0)), + TYPE_PRECISION (TREE_TYPE (t)), + TYPE_SIGN (TREE_TYPE (TREE_OPERAND (t, 0)))); + case PLUS_EXPR: + if (INTEGRAL_TYPE_P (TREE_TYPE (t))) + { + wide_int nzbits1 = tree_nonzero_bits (TREE_OPERAND (t, 0)); + wide_int nzbits2 = tree_nonzero_bits (TREE_OPERAND (t, 1)); + if (wi::bit_and (nzbits1, nzbits2) == 0) + return wi::bit_or (nzbits1, nzbits2); + } + break; + case LSHIFT_EXPR: + if (TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST) + { + tree type = TREE_TYPE (t); + wide_int nzbits = tree_nonzero_bits (TREE_OPERAND (t, 0)); + wide_int arg1 = wi::to_wide (TREE_OPERAND (t, 1), + TYPE_PRECISION (type)); + return wi::neg_p (arg1) + ? wi::rshift (nzbits, -arg1, TYPE_SIGN (type)) + : wi::lshift (nzbits, arg1); + } + break; + case RSHIFT_EXPR: + if (TREE_CODE (TREE_OPERAND (t, 1)) == INTEGER_CST) + { + tree type = TREE_TYPE (t); + wide_int nzbits = tree_nonzero_bits (TREE_OPERAND (t, 0)); + wide_int arg1 = wi::to_wide (TREE_OPERAND (t, 1), + TYPE_PRECISION (type)); + return wi::neg_p (arg1) + ? wi::lshift (nzbits, -arg1) + : wi::rshift (nzbits, arg1, TYPE_SIGN (type)); + } + break; + default: + break; + } + + return wi::shwi (-1, TYPE_PRECISION (TREE_TYPE (t))); +} + #if CHECKING_P namespace selftest { diff --git a/gcc/fold-const.h b/gcc/fold-const.h index 8e3ad512a0b..337818a3319 100644 --- a/gcc/fold-const.h +++ b/gcc/fold-const.h @@ -181,6 +181,7 @@ extern tree const_unop (enum tree_code, tree, tree); extern tree const_binop (enum tree_code, tree, tree, tree); extern bool negate_mathfn_p (combined_fn); extern const char *c_getstr (tree, unsigned HOST_WIDE_INT *strlen = NULL); +extern wide_int tree_nonzero_bits (const_tree); /* Return OFF converted to a pointer offset type suitable as offset for POINTER_PLUS_EXPR. Use location LOC for this conversion. */ diff --git a/gcc/match.pd b/gcc/match.pd index 50f4c882e5e..8a71141eac9 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -4760,3 +4760,23 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (negate (IFN_FNMS@3 @0 @1 @2)) (if (single_use (@3)) (IFN_FMA @0 @1 @2)))) + +/* POPCOUNT simplifications. */ +(for popcount (BUILT_IN_POPCOUNT BUILT_IN_POPCOUNTL BUILT_IN_POPCOUNTLL + BUILT_IN_POPCOUNTIMAX) + /* popcount(X&1) is nop_expr(X&1). */ + (simplify + (popcount @0) + (if (tree_nonzero_bits (@0) == 1) + (convert @0))) + /* popcount(X) + popcount(Y) is popcount(X|Y) when X&Y must be zero. */ + (simplify + (plus (popcount:s @0) (popcount:s @1)) + (if (wi::bit_and (tree_nonzero_bits (@0), tree_nonzero_bits (@1)) == 0) + (popcount (bit_ior @0 @1)))) + /* popcount(X) == 0 is X == 0, and related (in)equalities. */ + (for cmp (le eq ne gt) + rep (eq eq ne ne) + (simplify + (cmp (popcount @0) integer_zerop) + (rep @0 { build_zero_cst (TREE_TYPE (@0)); })))) diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 8a6fe202296..f7d0c3a4fb4 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,10 @@ +2018-05-24 Roger Sayle + + * gcc.dg/fold-popcount-1.c: New testcase. + * gcc.dg/fold-popcount-2.c: New testcase. + * gcc.dg/fold-popcount-3.c: New testcase. + * gcc.dg/fold-popcount-4.c: New testcase. + 2018-05-24 Marek Polacek PR c++/85847 diff --git a/gcc/testsuite/gcc.dg/fold-popcount-1.c b/gcc/testsuite/gcc.dg/fold-popcount-1.c new file mode 100644 index 00000000000..32bb7e2a321 --- /dev/null +++ b/gcc/testsuite/gcc.dg/fold-popcount-1.c @@ -0,0 +1,35 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-original" } */ + +int test_eqzero(unsigned int a) +{ + return __builtin_popcount(a) == 0; +} + +int test_eqzerol(unsigned long b) +{ + return __builtin_popcountl(b) == 0; +} + +int test_eqzeroll(unsigned long long c) +{ + return __builtin_popcountll(c) == 0; +} + +int test_nezero(unsigned int d) +{ + return __builtin_popcount(d) != 0; +} + +int test_nezerol(unsigned long e) +{ + return __builtin_popcountl(e) != 0; +} + +int test_nezeroll(unsigned long long f) +{ + return __builtin_popcountll(f) != 0; +} + +/* { dg-final { scan-tree-dump-times "popcount" 0 "original" } } */ + diff --git a/gcc/testsuite/gcc.dg/fold-popcount-2.c b/gcc/testsuite/gcc.dg/fold-popcount-2.c new file mode 100644 index 00000000000..27557da7cb1 --- /dev/null +++ b/gcc/testsuite/gcc.dg/fold-popcount-2.c @@ -0,0 +1,35 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-cddce1" } */ + +int test_andone(unsigned int a) +{ + return __builtin_popcount(a&1); +} + +int test_andonel(unsigned long b) +{ + return __builtin_popcountl(b&1); +} + +int test_andonell(unsigned long long c) +{ + return __builtin_popcountll(c&1); +} + +int test_oneand(unsigned int d) +{ + return __builtin_popcount(1&d); +} + +int test_oneandl(unsigned long e) +{ + return __builtin_popcountl(1&e); +} + +int test_oneandll(unsigned long long f) +{ + return __builtin_popcountll(1&f); +} + +/* { dg-final { scan-tree-dump-times "popcount" 0 "cddce1" } } */ + diff --git a/gcc/testsuite/gcc.dg/fold-popcount-3.c b/gcc/testsuite/gcc.dg/fold-popcount-3.c new file mode 100644 index 00000000000..eda007796bd --- /dev/null +++ b/gcc/testsuite/gcc.dg/fold-popcount-3.c @@ -0,0 +1,10 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-cddce1" } */ + +int test_combine(unsigned int a, unsigned int b) +{ + return __builtin_popcount(a&8) + __builtin_popcount(b&2); +} + +/* { dg-final { scan-tree-dump-times "popcount" 1 "cddce1" } } */ + diff --git a/gcc/testsuite/gcc.dg/fold-popcount-4.c b/gcc/testsuite/gcc.dg/fold-popcount-4.c new file mode 100644 index 00000000000..424c3d86692 --- /dev/null +++ b/gcc/testsuite/gcc.dg/fold-popcount-4.c @@ -0,0 +1,50 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-cddce1" } */ + +int test_shiftmax(unsigned int a) +{ + return __builtin_popcount(a>>(8*sizeof(a)-1)); +} + +int test_shiftmaxl(unsigned long b) +{ + return __builtin_popcountl(b>>(8*sizeof(b)-1)); +} + +int test_shiftmaxll(unsigned long long c) +{ + return __builtin_popcountll(c>>(8*sizeof(c)-1)); +} + +int test_shift7(unsigned char d) +{ + return __builtin_popcount(d>>7); +} + +int test_shift7l(unsigned char e) +{ + return __builtin_popcountl(e>>7); +} + +int test_shift7ll(unsigned char f) +{ + return __builtin_popcountll(f>>7); +} + +int test_shift15(unsigned short g) +{ + return __builtin_popcount(g>>15); +} + +int test_shift15l(unsigned short h) +{ + return __builtin_popcountl(h>>15); +} + +int test_shift15ll(unsigned short i) +{ + return __builtin_popcountll(i>>15); +} + +/* { dg-final { scan-tree-dump-times "popcount" 0 "cddce1" } } */ + -- 2.30.2