CbC/CbC_gcc: gcc/tree-ssa-loop-niter.c comparison

comparison gcc/tree-ssa-loop-niter.c @ 132:d34655255c78

update gcc-8.2

author	mir3636
date	Thu, 25 Oct 2018 10:21:07 +0900
parents	84e7813d76e9
children	1830386684a0

comparison

equal deleted inserted replaced

-:e108057fa461
+:d34655255c78
 /* Functions to determine/estimate number of iterations of a loop.
-Copyright (C) 2004-2017 Free Software Foundation, Inc.
+Copyright (C) 2004-2018 Free Software Foundation, Inc.
 This file is part of GCC.
 GCC is free software; you can redistribute it and/or modify it
 under the terms of the GNU General Public License as published by the
 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.  */
 static void
 split_to_var_and_offset (tree expr, tree *var, mpz_t offset)
 {
 int cnt = 0;
 mpz_t minm, maxm;
 basic_block bb;
 wide_int minv, maxv;
-enum value_range_type rtype = VR_VARYING;
+enum value_range_kind rtype = VR_VARYING;
 /* If the expression is a constant, we know its value exactly.  */
 if (integer_zerop (var))
 {
 mpz_set (min, off);
 if (code == SSA_NAME)
 	return expand_simple_operations (e, stop);
 else if (code == ADDR_EXPR)
 	{
-	  HOST_WIDE_INT offset;
+	  poly_int64 offset;
 	  tree base = get_addr_base_and_unit_offset (TREE_OPERAND (e, 0),
 						     &offset);
 	  if (base
 	      && TREE_CODE (base) == MEM_REF)
 	    {
 && !POINTER_TYPE_P (type))
 return false;
 tree iv0_niters = NULL_TREE;
 if (!simple_iv_with_niters (loop, loop_containing_stmt (stmt),
-			      op0, &iv0, &iv0_niters, false))
+			      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, &iv1_niters, false))
+			      op1, &iv1, safe ? &iv1_niters : NULL, false))
 return false;
 /* Give up on complicated case.  */
 if (iv0_niters && iv1_niters)
 return false;
 *at_stmt = stmt;
 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:
+<bb 2>
+goto <bb 4>
+<bb 3>
+_1 = b_11 + -1
+b_6 = _1 & b_11
+<bb 4>
+b_11 = PHI <b_5(D)(2), b_6(3)>
+exit block
+if (b_11 != 0)
+	goto <bb 3>
+else
+	goto <bb 5>
+OR we match copy-header version:
+if (b_5 != 0)
+	goto <bb 3>
+else
+	goto <bb 4>
+<bb 3>
+b_11 = PHI <b_5(2), b_6(3)>
+_1 = b_11 + -1
+b_6 = _1 & b_11
+exit block
+if (b_6 != 0)
+	goto <bb 3>
+else
+	goto <bb 4>
+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 <b_5(D)(2), b_6(3)>
+	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 <b_5(2), b_6(3)>.  */
+gimple *phi = SSA_NAME_DEF_STMT (b_11);
+if (gimple_code (phi) != GIMPLE_PHI
+|| (gimple_bb (phi) != loop_latch_edge (loop)->dest)
+|| (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  */
+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;
+if (TREE_CODE (call) == INTEGER_CST)
+max = tree_to_uhwi (call);
+else
+{
+max = TYPE_PRECISION (TREE_TYPE (src));
+if (adjust)
+	max = max - 1;
+}
+niter->niter = iter;
+niter->assumptions = boolean_true_node;
+if (adjust)
+{
+tree may_be_zero = fold_build2 (EQ_EXPR, boolean_type_node, src,
+				      build_zero_cst
+				      (TREE_TYPE (src)));
+niter->may_be_zero =
+	simplify_using_initial_conditions (loop, may_be_zero);
+}
+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.  */
 bool
 number_of_iterations_exit (struct loop *loop, edge exit,
 if (integer_nonzerop (niter->assumptions))
 return true;
 if (warn)
-dump_printf_loc (MSG_MISSED_OPTIMIZATION, gimple_location_safe (stmt),
+dump_printf_loc (MSG_MISSED_OPTIMIZATION, stmt,
 		     "missed loop optimization: niters analysis ends up "
 		     "with assumptions.\n");
 return false;
 }
 gimple *estmt = last_stmt (e->src);
 char buf[WIDE_INT_PRINT_BUFFER_SIZE];
 print_dec (i_bound, buf, TYPE_UNSIGNED (TREE_TYPE (loop->nb_iterations))
 	     ? UNSIGNED : SIGNED);
+auto_diagnostic_group d;
 if (warning_at (gimple_location (stmt), OPT_Waggressive_loop_optimizations,
 		  "iteration %s invokes undefined behavior", buf))
 inform (gimple_location (estmt), "within this loop");
 loop->warned_aggressive_loop_optimizations = true;
 }
 || chrec_contains_symbols_defined_in_loop (base, loop->num))
 return;
 low = lower_bound_in_type (type, type);
 high = upper_bound_in_type (type, type);
+wide_int minv, maxv;
+if (get_range_info (def, &minv, &maxv) == VR_RANGE)
+{
+low = wide_int_to_tree (type, minv);
+high = wide_int_to_tree (type, maxv);
+}
 record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
 }
 /* The following analyzers are extracting informations on the bounds
 Do not recompute already recorded bounds - we ought to be better on
 updating iteration bounds than updating profile in general and thus
 recomputing iteration bounds later in the compilation process will just
 introduce random roundoff errors.  */
 if (!loop->any_estimate
-&& loop->header->count > 0)
+&& loop->header->count.reliable_p ())
 {
 gcov_type nit = expected_loop_iterations_unbounded (loop);
 bound = gcov_type_to_wide_int (nit);
 record_niter_bound (loop, bound, true, false);
 }
 static bool
 scev_var_range_cant_overflow (tree var, tree step, struct loop *loop)
 {
 tree type;
 wide_int minv, maxv, diff, step_wi;
-enum value_range_type rtype;
+enum value_range_kind rtype;
 if (TREE_CODE (step) != INTEGER_CST || !INTEGRAL_TYPE_P (TREE_TYPE (var)))
 return false;
 /* Check if VAR evaluates in every loop iteration.  It's not the case

Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-ssa-loop-niter.c @ 132:d34655255c78