From 5126ae0c6eafd2bba09fc60a23cd9c0b292846c4 Mon Sep 17 00:00:00 2001 From: Kugan Vivekanandarajah Date: Sat, 16 Jun 2018 21:39:31 +0000 Subject: [PATCH] re PR middle-end/82479 (missing popcount builtin detection) gcc/ChangeLog: 2018-06-16 Kugan Vivekanandarajah PR middle-end/82479 * ipa-fnsummary.c (will_be_nonconstant_expr_predicate): Handle CALL_EXPR. * tree-scalar-evolution.c (interpret_expr): Likewise. (expression_expensive_p): Likewise. * tree-ssa-loop-ivopts.c (contains_abnormal_ssa_name_p): Likewise. * tree-ssa-loop-niter.c (number_of_iterations_popcount): New. (number_of_iterations_exit_assumptions): Use number_of_iterations_popcount. (ssa_defined_by_minus_one_stmt_p): New. gcc/testsuite/ChangeLog: 2018-06-16 Kugan Vivekanandarajah PR middle-end/82479 * gcc.dg/tree-ssa/popcount.c: New test. * gcc.dg/tree-ssa/popcount2.c: New test. From-SVN: r261682 --- gcc/ChangeLog | 11 ++ gcc/ipa-fnsummary.c | 2 + gcc/testsuite/ChangeLog | 6 + gcc/testsuite/gcc.dg/tree-ssa/popcount.c | 41 +++++ gcc/testsuite/gcc.dg/tree-ssa/popcount2.c | 28 ++++ gcc/tree-scalar-evolution.c | 15 ++ gcc/tree-ssa-loop-ivopts.c | 10 ++ gcc/tree-ssa-loop-niter.c | 176 +++++++++++++++++++++- 8 files changed, 288 insertions(+), 1 deletion(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/popcount.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/popcount2.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index fe24ad300db..792200974e0 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,14 @@ +2018-06-16 Kugan Vivekanandarajah + + PR middle-end/82479 + * ipa-fnsummary.c (will_be_nonconstant_expr_predicate): Handle CALL_EXPR. + * tree-scalar-evolution.c (interpret_expr): Likewise. + (expression_expensive_p): Likewise. + * tree-ssa-loop-ivopts.c (contains_abnormal_ssa_name_p): Likewise. + * tree-ssa-loop-niter.c (number_of_iterations_popcount): New. + (number_of_iterations_exit_assumptions): Use number_of_iterations_popcount. + (ssa_defined_by_minus_one_stmt_p): New. + 2018-06-16 Kugan Vivekanandarajah PR middle-end/64946 diff --git a/gcc/ipa-fnsummary.c b/gcc/ipa-fnsummary.c index e40b537bf61..504a2d1ce55 100644 --- a/gcc/ipa-fnsummary.c +++ b/gcc/ipa-fnsummary.c @@ -1487,6 +1487,8 @@ will_be_nonconstant_expr_predicate (struct ipa_node_params *info, nonconstant_names); return p2.or_with (summary->conds, p1); } + else if (TREE_CODE (expr) == CALL_EXPR) + return true; else { debug_tree (expr); diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index af7d3d8bb1b..1b6e062db50 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,9 @@ +2018-06-16 Kugan Vivekanandarajah + + PR middle-end/82479 + * gcc.dg/tree-ssa/popcount.c: New test. + * gcc.dg/tree-ssa/popcount2.c: New test. + 2018-06-16 Kugan Vivekanandarajah PR middle-end/64946 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/popcount.c b/gcc/testsuite/gcc.dg/tree-ssa/popcount.c new file mode 100644 index 00000000000..a5ec3b34f96 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/popcount.c @@ -0,0 +1,41 @@ +/* { dg-do compile } */ +/* { dg-options "-O3 -fdump-tree-optimized -fno-tree-ch" } */ + +extern int foo (int); + +int PopCount (long b) { + int c = 0; + b++; + + while (b) { + b &= b - 1; + c++; + } + return c; +} +int PopCount2 (long b) { + int c = 0; + + while (b) { + b &= b - 1; + c++; + } + foo (c); + return foo (c); +} + +void PopCount3 (long b1) { + + for (long i = 0; i < b1; ++i) + { + long b = i; + int c = 0; + while (b) { + b &= b - 1; + c++; + } + foo (c); + } +} + +/* { dg-final { scan-tree-dump-times "__builtin_popcount" 3 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/popcount2.c b/gcc/testsuite/gcc.dg/tree-ssa/popcount2.c new file mode 100644 index 00000000000..9096c6bee04 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/popcount2.c @@ -0,0 +1,28 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fno-tree-ch -fdump-tree-optimized" } */ + +int +__attribute__ ((noinline, noclone)) +foo (long b) +{ + int c = 0; + + while (b) { + b &= b - 1; + c++; + } + return c; +} + +int main() +{ + if (foo (7) != 3) + __builtin_abort (); + if (foo (0) != 0) + __builtin_abort (); + if (foo (0xff) != 8) + __builtin_abort (); + return 0; +} + +/* { dg-final { scan-tree-dump-times "__builtin_popcount" 1 "optimized" } } */ diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index fefc9de96af..4b0ec02b4de 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -281,6 +281,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-ssa-propagate.h" #include "gimple-fold.h" #include "tree-into-ssa.h" +#include "builtins.h" static tree analyze_scalar_evolution_1 (struct loop *, tree); static tree analyze_scalar_evolution_for_address_of (struct loop *loop, @@ -1984,6 +1985,7 @@ interpret_expr (struct loop *loop, gimple *at_stmt, tree expr) return expr; if (TREE_CODE (expr) == POLYNOMIAL_CHREC + || TREE_CODE (expr) == CALL_EXPR || get_gimple_rhs_class (TREE_CODE (expr)) == GIMPLE_TERNARY_RHS) return chrec_dont_know; @@ -3493,6 +3495,19 @@ expression_expensive_p (tree expr) return true; } + if (code == CALL_EXPR) + { + tree arg; + call_expr_arg_iterator iter; + + if (!is_inexpensive_builtin (get_callee_fndecl (expr))) + return true; + FOR_EACH_CALL_EXPR_ARG (arg, iter, expr) + if (expression_expensive_p (arg)) + return true; + return false; + } + switch (TREE_CODE_CLASS (code)) { case tcc_binary: diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c index b3135717f22..519649a3a97 100644 --- a/gcc/tree-ssa-loop-ivopts.c +++ b/gcc/tree-ssa-loop-ivopts.c @@ -985,6 +985,16 @@ contains_abnormal_ssa_name_p (tree expr) code = TREE_CODE (expr); codeclass = TREE_CODE_CLASS (code); + if (code == CALL_EXPR) + { + tree arg; + call_expr_arg_iterator iter; + FOR_EACH_CALL_EXPR_ARG (arg, iter, expr) + if (contains_abnormal_ssa_name_p (arg)) + return true; + return false; + } + if (code == SSA_NAME) return SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr) != 0; diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index 7a54c5f1e62..936591502d0 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -63,6 +63,10 @@ struct bounds mpz_t below, up; }; +static bool number_of_iterations_popcount (loop_p loop, edge exit, + enum tree_code code, + struct tree_niter_desc *niter); + /* Splits expression EXPR to a variable part VAR and constant OFFSET. */ @@ -2357,7 +2361,7 @@ number_of_iterations_exit_assumptions (struct loop *loop, edge exit, tree iv0_niters = NULL_TREE; if (!simple_iv_with_niters (loop, loop_containing_stmt (stmt), op0, &iv0, safe ? &iv0_niters : NULL, false)) - return false; + return number_of_iterations_popcount (loop, exit, code, niter); tree iv1_niters = NULL_TREE; if (!simple_iv_with_niters (loop, loop_containing_stmt (stmt), op1, &iv1, safe ? &iv1_niters : NULL, false)) @@ -2430,6 +2434,176 @@ number_of_iterations_exit_assumptions (struct loop *loop, edge exit, return (!integer_zerop (niter->assumptions)); } + +/* Utility function to check if OP is defined by a stmt + that is a val - 1. */ + +static bool +ssa_defined_by_minus_one_stmt_p (tree op, tree val) +{ + gimple *stmt; + return (TREE_CODE (op) == SSA_NAME + && (stmt = SSA_NAME_DEF_STMT (op)) + && is_gimple_assign (stmt) + && (gimple_assign_rhs_code (stmt) == PLUS_EXPR) + && val == gimple_assign_rhs1 (stmt) + && integer_minus_onep (gimple_assign_rhs2 (stmt))); +} + + +/* See if LOOP is a popcout implementation, determine NITER for the loop + + We match: + + goto + + + _1 = b_11 + -1 + b_6 = _1 & b_11 + + + b_11 = PHI + + exit block + if (b_11 != 0) + goto + else + goto + + OR we match copy-header version: + if (b_5 != 0) + goto + else + goto + + + b_11 = PHI + _1 = b_11 + -1 + b_6 = _1 & b_11 + + exit block + if (b_6 != 0) + goto + else + goto + + If popcount pattern, update NITER accordingly. + i.e., set NITER to __builtin_popcount (b) + return true if we did, false otherwise. + + */ + +static bool +number_of_iterations_popcount (loop_p loop, edge exit, + enum tree_code code, + struct tree_niter_desc *niter) +{ + bool adjust = true; + tree iter; + HOST_WIDE_INT max; + adjust = true; + tree fn = NULL_TREE; + + /* Check loop terminating branch is like + if (b != 0). */ + gimple *stmt = last_stmt (exit->src); + if (!stmt + || gimple_code (stmt) != GIMPLE_COND + || code != NE_EXPR + || !integer_zerop (gimple_cond_rhs (stmt)) + || TREE_CODE (gimple_cond_lhs (stmt)) != SSA_NAME) + return false; + + gimple *and_stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt)); + + /* Depending on copy-header is performed, feeding PHI stmts might be in + the loop header or loop latch, handle this. */ + if (gimple_code (and_stmt) == GIMPLE_PHI + && gimple_bb (and_stmt) == loop->header + && gimple_phi_num_args (and_stmt) == 2 + && (TREE_CODE (gimple_phi_arg_def (and_stmt, + loop_latch_edge (loop)->dest_idx)) + == SSA_NAME)) + { + /* SSA used in exit condition is defined by PHI stmt + b_11 = PHI + from the PHI stmt, get the and_stmt + b_6 = _1 & b_11. */ + tree t = gimple_phi_arg_def (and_stmt, loop_latch_edge (loop)->dest_idx); + and_stmt = SSA_NAME_DEF_STMT (t); + adjust = false; + } + + /* Make sure it is indeed an and stmt (b_6 = _1 & b_11). */ + if (!is_gimple_assign (and_stmt) + || gimple_assign_rhs_code (and_stmt) != BIT_AND_EXPR) + return false; + + tree b_11 = gimple_assign_rhs1 (and_stmt); + tree _1 = gimple_assign_rhs2 (and_stmt); + + /* Check that _1 is defined by _b11 + -1 (_1 = b_11 + -1). + Also make sure that b_11 is the same in and_stmt and _1 defining stmt. + Also canonicalize if _1 and _b11 are revrsed. */ + if (ssa_defined_by_minus_one_stmt_p (b_11, _1)) + std::swap (b_11, _1); + else if (ssa_defined_by_minus_one_stmt_p (_1, b_11)) + ; + else + return false; + /* Check the recurrence: + ... = PHI . */ + gimple *phi = SSA_NAME_DEF_STMT (b_11); + if (gimple_code (phi) != GIMPLE_PHI + || (gimple_assign_lhs (and_stmt) + != gimple_phi_arg_def (phi, loop_latch_edge (loop)->dest_idx))) + return false; + + /* We found a match. Get the corresponding popcount builtin. */ + tree src = gimple_phi_arg_def (phi, loop_preheader_edge (loop)->dest_idx); + if (TYPE_PRECISION (TREE_TYPE (src)) == TYPE_PRECISION (integer_type_node)) + fn = builtin_decl_implicit (BUILT_IN_POPCOUNT); + else if (TYPE_PRECISION (TREE_TYPE (src)) == TYPE_PRECISION + (long_integer_type_node)) + fn = builtin_decl_implicit (BUILT_IN_POPCOUNTL); + else if (TYPE_PRECISION (TREE_TYPE (src)) == TYPE_PRECISION + (long_long_integer_type_node)) + fn = builtin_decl_implicit (BUILT_IN_POPCOUNTLL); + + /* ??? Support promoting char/short to int. */ + if (!fn) + return false; + + /* Update NITER params accordingly */ + max = TYPE_PRECISION (TREE_TYPE (src)); + if (adjust) + max = max - 1; + tree utype = unsigned_type_for (TREE_TYPE (src)); + src = fold_convert (utype, src); + tree call = fold_convert (utype, build_call_expr (fn, 1, src)); + if (adjust) + iter = fold_build2 (MINUS_EXPR, utype, + call, + build_int_cst (utype, 1)); + else + iter = call; + + niter->niter = iter; + niter->assumptions = boolean_true_node; + if (adjust) + niter->may_be_zero = fold_build2 (EQ_EXPR, boolean_type_node, src, + build_zero_cst + (TREE_TYPE (src))); + else + niter->may_be_zero = boolean_false_node; + + niter->max = max; + niter->bound = NULL_TREE; + niter->cmp = ERROR_MARK; + return true; +} + + /* Like number_of_iterations_exit_assumptions, but return TRUE only if the niter information holds unconditionally. */ -- 2.30.2