+ or
+
+ for (i = iv1->base; i > iv0->base; i--).
+
+ In both cases # of iterations is iv1->base - iv0->base, assuming that
+ iv1->base >= iv0->base.
+
+ First try to derive a lower bound on the value of
+ iv1->base - iv0->base, computed in full precision. If the difference
+ is nonnegative, we are done, otherwise we must record the
+ condition. */
+
+ if (mpz_sgn (bnds->below) < 0)
+ niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
+ iv1->base, iv0->base);
+ niter->niter = delta;
+ niter->max = mpz_to_double_int (niter_type, bnds->up);
+ return true;
+ }
+
+ if (integer_nonzerop (iv0->step))
+ step = fold_convert (niter_type, iv0->step);
+ else
+ step = fold_convert (niter_type,
+ fold_build1 (NEGATE_EXPR, type, iv1->step));
+
+ /* If we can determine the final value of the control iv exactly, we can
+ transform the condition to != comparison. In particular, this will be
+ the case if DELTA is constant. */
+ if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step,
+ bnds))
+ {
+ affine_iv zps;
+
+ zps.base = build_int_cst (niter_type, 0);
+ zps.step = step;
+ /* number_of_iterations_lt_to_ne will add assumptions that ensure that
+ zps does not overflow. */
+ zps.no_overflow = true;
+
+ return number_of_iterations_ne (type, &zps, delta, niter, true, bnds);
+ }
+
+ /* Make sure that the control iv does not overflow. */
+ if (!assert_no_overflow_lt (type, iv0, iv1, niter, step))
+ return false;
+
+ /* We determine the number of iterations as (delta + step - 1) / step. For
+ this to work, we must know that iv1->base >= iv0->base - step + 1,
+ otherwise the loop does not roll. */
+ assert_loop_rolls_lt (type, iv0, iv1, niter, bnds);
+
+ s = fold_build2 (MINUS_EXPR, niter_type,
+ step, build_int_cst (niter_type, 1));
+ delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
+ niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
+
+ mpz_init (mstep);
+ mpz_init (tmp);
+ mpz_set_double_int (mstep, tree_to_double_int (step), true);
+ mpz_add (tmp, bnds->up, mstep);
+ mpz_sub_ui (tmp, tmp, 1);
+ mpz_fdiv_q (tmp, tmp, mstep);
+ niter->max = mpz_to_double_int (niter_type, tmp);
+ mpz_clear (mstep);
+ mpz_clear (tmp);
+
+ return true;
+}
+
+/* Determines number of iterations of loop whose ending condition
+ is IV0 <= IV1. TYPE is the type of the iv. The number of
+ iterations is stored to NITER. NEVER_INFINITE is true if
+ we know that this condition must eventually become false (we derived this
+ earlier, and possibly set NITER->assumptions to make sure this
+ is the case). BNDS bounds the difference IV1->base - IV0->base. */
+
+static bool
+number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1,
+ struct tree_niter_desc *niter, bool never_infinite,
+ bounds *bnds)
+{
+ tree assumption;
+
+ /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
+ IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
+ value of the type. This we must know anyway, since if it is
+ equal to this value, the loop rolls forever. */
+
+ if (!never_infinite)
+ {
+ if (integer_nonzerop (iv0->step))
+ assumption = fold_build2 (NE_EXPR, boolean_type_node,
+ iv1->base, TYPE_MAX_VALUE (type));
+ else
+ assumption = fold_build2 (NE_EXPR, boolean_type_node,
+ iv0->base, TYPE_MIN_VALUE (type));
+
+ if (integer_zerop (assumption))
+ return false;
+ if (!integer_nonzerop (assumption))
+ niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
+ niter->assumptions, assumption);
+ }
+
+ if (integer_nonzerop (iv0->step))
+ iv1->base = fold_build2 (PLUS_EXPR, type,
+ iv1->base, build_int_cst (type, 1));
+ else
+ iv0->base = fold_build2 (MINUS_EXPR, type,
+ iv0->base, build_int_cst (type, 1));
+
+ bounds_add (bnds, double_int_one, type);
+
+ return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite, bnds);
+}
+
+/* Dumps description of affine induction variable IV to FILE. */
+
+static void
+dump_affine_iv (FILE *file, affine_iv *iv)
+{
+ if (!integer_zerop (iv->step))
+ fprintf (file, "[");
+
+ print_generic_expr (dump_file, iv->base, TDF_SLIM);
+
+ if (!integer_zerop (iv->step))
+ {
+ fprintf (file, ", + , ");
+ print_generic_expr (dump_file, iv->step, TDF_SLIM);
+ fprintf (file, "]%s", iv->no_overflow ? "(no_overflow)" : "");
+ }
+}
+
+/* Determine the number of iterations according to condition (for staying
+ inside loop) which compares two induction variables using comparison
+ operator CODE. The induction variable on left side of the comparison
+ is IV0, the right-hand side is IV1. Both induction variables must have
+ type TYPE, which must be an integer or pointer type. The steps of the
+ ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
+
+ LOOP is the loop whose number of iterations we are determining.
+
+ ONLY_EXIT is true if we are sure this is the only way the loop could be
+ exited (including possibly non-returning function calls, exceptions, etc.)
+ -- in this case we can use the information whether the control induction
+ variables can overflow or not in a more efficient way.
+
+ The results (number of iterations and assumptions as described in
+ comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
+ Returns false if it fails to determine number of iterations, true if it
+ was determined (possibly with some assumptions). */
+
+static bool
+number_of_iterations_cond (struct loop *loop,
+ tree type, affine_iv *iv0, enum tree_code code,
+ affine_iv *iv1, struct tree_niter_desc *niter,
+ bool only_exit)
+{
+ bool never_infinite, ret;
+ bounds bnds;
+
+ /* The meaning of these assumptions is this:
+ if !assumptions
+ then the rest of information does not have to be valid
+ if may_be_zero then the loop does not roll, even if
+ niter != 0. */
+ niter->assumptions = boolean_true_node;
+ niter->may_be_zero = boolean_false_node;
+ niter->niter = NULL_TREE;
+ niter->max = double_int_zero;
+
+ niter->bound = NULL_TREE;
+ niter->cmp = ERROR_MARK;
+
+ /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
+ the control variable is on lhs. */
+ if (code == GE_EXPR || code == GT_EXPR
+ || (code == NE_EXPR && integer_zerop (iv0->step)))
+ {
+ SWAP (iv0, iv1);
+ code = swap_tree_comparison (code);
+ }
+
+ if (!only_exit)
+ {
+ /* If this is not the only possible exit from the loop, the information
+ that the induction variables cannot overflow as derived from
+ signedness analysis cannot be relied upon. We use them e.g. in the
+ following way: given loop for (i = 0; i <= n; i++), if i is
+ signed, it cannot overflow, thus this loop is equivalent to
+ for (i = 0; i < n + 1; i++); however, if n == MAX, but the loop
+ is exited in some other way before i overflows, this transformation
+ is incorrect (the new loop exits immediately). */
+ iv0->no_overflow = false;
+ iv1->no_overflow = false;
+ }
+
+ if (POINTER_TYPE_P (type))
+ {
+ /* Comparison of pointers is undefined unless both iv0 and iv1 point
+ to the same object. If they do, the control variable cannot wrap
+ (as wrap around the bounds of memory will never return a pointer
+ that would be guaranteed to point to the same object, even if we
+ avoid undefined behavior by casting to size_t and back). The
+ restrictions on pointer arithmetics and comparisons of pointers
+ ensure that using the no-overflow assumptions is correct in this
+ case even if ONLY_EXIT is false. */
+ iv0->no_overflow = true;
+ iv1->no_overflow = true;
+ }
+
+ /* If the control induction variable does not overflow, the loop obviously
+ cannot be infinite. */
+ if (!integer_zerop (iv0->step) && iv0->no_overflow)
+ never_infinite = true;
+ else if (!integer_zerop (iv1->step) && iv1->no_overflow)
+ never_infinite = true;
+ else
+ never_infinite = false;
+
+ /* We can handle the case when neither of the sides of the comparison is
+ invariant, provided that the test is NE_EXPR. This rarely occurs in
+ practice, but it is simple enough to manage. */
+ if (!integer_zerop (iv0->step) && !integer_zerop (iv1->step))
+ {
+ if (code != NE_EXPR)
+ return false;
+
+ iv0->step = fold_binary_to_constant (MINUS_EXPR, type,
+ iv0->step, iv1->step);
+ iv0->no_overflow = false;
+ iv1->step = build_int_cst (type, 0);
+ iv1->no_overflow = true;
+ }
+
+ /* If the result of the comparison is a constant, the loop is weird. More
+ precise handling would be possible, but the situation is not common enough
+ to waste time on it. */
+ if (integer_zerop (iv0->step) && integer_zerop (iv1->step))
+ return false;
+
+ /* Ignore loops of while (i-- < 10) type. */
+ if (code != NE_EXPR)
+ {
+ if (iv0->step && tree_int_cst_sign_bit (iv0->step))
+ return false;
+
+ if (!integer_zerop (iv1->step) && !tree_int_cst_sign_bit (iv1->step))
+ return false;
+ }
+
+ /* If the loop exits immediately, there is nothing to do. */
+ if (integer_zerop (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
+ {
+ niter->niter = build_int_cst (unsigned_type_for (type), 0);
+ niter->max = double_int_zero;
+ return true;
+ }
+
+ /* OK, now we know we have a senseful loop. Handle several cases, depending
+ on what comparison operator is used. */
+ bound_difference (loop, iv1->base, iv0->base, &bnds);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file,
+ "Analysing # of iterations of loop %d\n", loop->num);
+
+ fprintf (dump_file, " exit condition ");
+ dump_affine_iv (dump_file, iv0);
+ fprintf (dump_file, " %s ",
+ code == NE_EXPR ? "!="
+ : code == LT_EXPR ? "<"
+ : "<=");
+ dump_affine_iv (dump_file, iv1);
+ fprintf (dump_file, "\n");
+
+ fprintf (dump_file, " bounds on difference of bases: ");
+ mpz_out_str (dump_file, 10, bnds.below);
+ fprintf (dump_file, " ... ");
+ mpz_out_str (dump_file, 10, bnds.up);
+ fprintf (dump_file, "\n");
+ }
+
+ switch (code)
+ {
+ case NE_EXPR:
+ gcc_assert (integer_zerop (iv1->step));
+ ret = number_of_iterations_ne (type, iv0, iv1->base, niter,
+ never_infinite, &bnds);
+ break;
+
+ case LT_EXPR:
+ ret = number_of_iterations_lt (type, iv0, iv1, niter, never_infinite,
+ &bnds);
+ break;
+
+ case LE_EXPR:
+ ret = number_of_iterations_le (type, iv0, iv1, niter, never_infinite,
+ &bnds);
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+
+ mpz_clear (bnds.up);
+ mpz_clear (bnds.below);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ if (ret)
+ {
+ fprintf (dump_file, " result:\n");
+ if (!integer_nonzerop (niter->assumptions))
+ {
+ fprintf (dump_file, " under assumptions ");
+ print_generic_expr (dump_file, niter->assumptions, TDF_SLIM);
+ fprintf (dump_file, "\n");
+ }
+
+ if (!integer_zerop (niter->may_be_zero))
+ {
+ fprintf (dump_file, " zero if ");
+ print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
+ fprintf (dump_file, "\n");
+ }
+
+ fprintf (dump_file, " # of iterations ");
+ print_generic_expr (dump_file, niter->niter, TDF_SLIM);
+ fprintf (dump_file, ", bounded by ");
+ dump_double_int (dump_file, niter->max, true);
+ fprintf (dump_file, "\n");
+ }
+ else
+ fprintf (dump_file, " failed\n\n");
+ }
+ return ret;
+}
+
+/* Substitute NEW for OLD in EXPR and fold the result. */
+
+static tree
+simplify_replace_tree (tree expr, tree old, tree new)
+{
+ unsigned i, n;
+ tree ret = NULL_TREE, e, se;
+
+ if (!expr)
+ return NULL_TREE;
+
+ if (expr == old
+ || operand_equal_p (expr, old, 0))
+ return unshare_expr (new);
+
+ if (!EXPR_P (expr) && !GIMPLE_STMT_P (expr))
+ return expr;
+
+ n = TREE_OPERAND_LENGTH (expr);
+ for (i = 0; i < n; i++)
+ {
+ e = TREE_OPERAND (expr, i);
+ se = simplify_replace_tree (e, old, new);
+ if (e == se)
+ continue;
+
+ if (!ret)
+ ret = copy_node (expr);
+
+ TREE_OPERAND (ret, i) = se;
+ }
+
+ return (ret ? fold (ret) : expr);
+}
+
+/* Expand definitions of ssa names in EXPR as long as they are simple
+ enough, and return the new expression. */
+
+tree
+expand_simple_operations (tree expr)
+{
+ unsigned i, n;
+ tree ret = NULL_TREE, e, ee, stmt;
+ enum tree_code code;
+
+ if (expr == NULL_TREE)
+ return expr;
+
+ if (is_gimple_min_invariant (expr))
+ return expr;
+
+ code = TREE_CODE (expr);
+ if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
+ {
+ n = TREE_OPERAND_LENGTH (expr);
+ for (i = 0; i < n; i++)
+ {
+ e = TREE_OPERAND (expr, i);
+ ee = expand_simple_operations (e);
+ if (e == ee)
+ continue;
+
+ if (!ret)
+ ret = copy_node (expr);
+
+ TREE_OPERAND (ret, i) = ee;
+ }
+
+ if (!ret)
+ return expr;
+
+ fold_defer_overflow_warnings ();
+ ret = fold (ret);
+ fold_undefer_and_ignore_overflow_warnings ();
+ return ret;
+ }
+
+ if (TREE_CODE (expr) != SSA_NAME)
+ return expr;
+
+ stmt = SSA_NAME_DEF_STMT (expr);
+ if (TREE_CODE (stmt) == PHI_NODE)
+ {
+ basic_block src, dest;
+
+ if (PHI_NUM_ARGS (stmt) != 1)
+ return expr;
+ e = PHI_ARG_DEF (stmt, 0);
+
+ /* Avoid propagating through loop exit phi nodes, which
+ could break loop-closed SSA form restrictions. */
+ dest = bb_for_stmt (stmt);
+ src = single_pred (dest);
+ if (TREE_CODE (e) == SSA_NAME
+ && src->loop_father != dest->loop_father)
+ return expr;
+
+ return expand_simple_operations (e);
+ }
+ if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
+ return expr;
+
+ e = GIMPLE_STMT_OPERAND (stmt, 1);
+ if (/* Casts are simple. */
+ TREE_CODE (e) != NOP_EXPR
+ && TREE_CODE (e) != CONVERT_EXPR
+ /* Copies are simple. */
+ && TREE_CODE (e) != SSA_NAME
+ /* Assignments of invariants are simple. */
+ && !is_gimple_min_invariant (e)
+ /* And increments and decrements by a constant are simple. */
+ && !((TREE_CODE (e) == PLUS_EXPR
+ || TREE_CODE (e) == MINUS_EXPR)
+ && is_gimple_min_invariant (TREE_OPERAND (e, 1))))
+ return expr;
+
+ return expand_simple_operations (e);
+}
+
+/* Tries to simplify EXPR using the condition COND. Returns the simplified
+ expression (or EXPR unchanged, if no simplification was possible). */
+
+static tree
+tree_simplify_using_condition_1 (tree cond, tree expr)
+{
+ bool changed;
+ tree e, te, e0, e1, e2, notcond;
+ enum tree_code code = TREE_CODE (expr);
+
+ if (code == INTEGER_CST)
+ return expr;
+
+ if (code == TRUTH_OR_EXPR
+ || code == TRUTH_AND_EXPR
+ || code == COND_EXPR)
+ {
+ changed = false;
+
+ e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0));