1 /* Functions to determine/estimate number of iterations of a loop.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
27 #include "basic-block.h"
29 #include "tree-pretty-print.h"
30 #include "gimple-pretty-print.h"
32 #include "tree-flow.h"
33 #include "tree-dump.h"
35 #include "tree-pass.h"
37 #include "tree-chrec.h"
38 #include "tree-scalar-evolution.h"
39 #include "tree-data-ref.h"
42 #include "diagnostic-core.h"
44 #include "tree-inline.h"
47 #define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
49 /* The maximum number of dominator BBs we search for conditions
50 of loop header copies we use for simplifying a conditional
52 #define MAX_DOMINATORS_TO_WALK 8
56 Analysis of number of iterations of an affine exit test.
60 /* Bounds on some value, BELOW <= X <= UP. */
68 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */
71 split_to_var_and_offset (tree expr, tree *var, mpz_t offset)
73 tree type = TREE_TYPE (expr);
79 mpz_set_ui (offset, 0);
81 switch (TREE_CODE (expr))
88 case POINTER_PLUS_EXPR:
89 op0 = TREE_OPERAND (expr, 0);
90 op1 = TREE_OPERAND (expr, 1);
92 if (TREE_CODE (op1) != INTEGER_CST)
96 /* Always sign extend the offset. */
97 off = tree_to_double_int (op1);
99 off = double_int_neg (off);
100 off = double_int_sext (off, TYPE_PRECISION (type));
101 mpz_set_double_int (offset, off, false);
105 *var = build_int_cst_type (type, 0);
106 off = tree_to_double_int (expr);
107 mpz_set_double_int (offset, off, TYPE_UNSIGNED (type));
115 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
116 in TYPE to MIN and MAX. */
119 determine_value_range (tree type, tree var, mpz_t off,
120 mpz_t min, mpz_t max)
122 /* If the expression is a constant, we know its value exactly. */
123 if (integer_zerop (var))
130 /* If the computation may wrap, we know nothing about the value, except for
131 the range of the type. */
132 get_type_static_bounds (type, min, max);
133 if (!nowrap_type_p (type))
136 /* Since the addition of OFF does not wrap, if OFF is positive, then we may
137 add it to MIN, otherwise to MAX. */
138 if (mpz_sgn (off) < 0)
139 mpz_add (max, max, off);
141 mpz_add (min, min, off);
144 /* Stores the bounds on the difference of the values of the expressions
145 (var + X) and (var + Y), computed in TYPE, to BNDS. */
148 bound_difference_of_offsetted_base (tree type, mpz_t x, mpz_t y,
151 int rel = mpz_cmp (x, y);
152 bool may_wrap = !nowrap_type_p (type);
155 /* If X == Y, then the expressions are always equal.
156 If X > Y, there are the following possibilities:
157 a) neither of var + X and var + Y overflow or underflow, or both of
158 them do. Then their difference is X - Y.
159 b) var + X overflows, and var + Y does not. Then the values of the
160 expressions are var + X - M and var + Y, where M is the range of
161 the type, and their difference is X - Y - M.
162 c) var + Y underflows and var + X does not. Their difference again
164 Therefore, if the arithmetics in type does not overflow, then the
165 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
166 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
167 (X - Y, X - Y + M). */
171 mpz_set_ui (bnds->below, 0);
172 mpz_set_ui (bnds->up, 0);
177 mpz_set_double_int (m, double_int_mask (TYPE_PRECISION (type)), true);
178 mpz_add_ui (m, m, 1);
179 mpz_sub (bnds->up, x, y);
180 mpz_set (bnds->below, bnds->up);
185 mpz_sub (bnds->below, bnds->below, m);
187 mpz_add (bnds->up, bnds->up, m);
193 /* From condition C0 CMP C1 derives information regarding the
194 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
195 and stores it to BNDS. */
198 refine_bounds_using_guard (tree type, tree varx, mpz_t offx,
199 tree vary, mpz_t offy,
200 tree c0, enum tree_code cmp, tree c1,
203 tree varc0, varc1, tmp, ctype;
204 mpz_t offc0, offc1, loffx, loffy, bnd;
206 bool no_wrap = nowrap_type_p (type);
215 STRIP_SIGN_NOPS (c0);
216 STRIP_SIGN_NOPS (c1);
217 ctype = TREE_TYPE (c0);
218 if (!useless_type_conversion_p (ctype, type))
224 /* We could derive quite precise information from EQ_EXPR, however, such
225 a guard is unlikely to appear, so we do not bother with handling
230 /* NE_EXPR comparisons do not contain much of useful information, except for
231 special case of comparing with the bounds of the type. */
232 if (TREE_CODE (c1) != INTEGER_CST
233 || !INTEGRAL_TYPE_P (type))
236 /* Ensure that the condition speaks about an expression in the same type
238 ctype = TREE_TYPE (c0);
239 if (TYPE_PRECISION (ctype) != TYPE_PRECISION (type))
241 c0 = fold_convert (type, c0);
242 c1 = fold_convert (type, c1);
244 if (TYPE_MIN_VALUE (type)
245 && operand_equal_p (c1, TYPE_MIN_VALUE (type), 0))
250 if (TYPE_MAX_VALUE (type)
251 && operand_equal_p (c1, TYPE_MAX_VALUE (type), 0))
264 split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0);
265 split_to_var_and_offset (expand_simple_operations (c1), &varc1, offc1);
267 /* We are only interested in comparisons of expressions based on VARX and
268 VARY. TODO -- we might also be able to derive some bounds from
269 expressions containing just one of the variables. */
271 if (operand_equal_p (varx, varc1, 0))
273 tmp = varc0; varc0 = varc1; varc1 = tmp;
274 mpz_swap (offc0, offc1);
275 cmp = swap_tree_comparison (cmp);
278 if (!operand_equal_p (varx, varc0, 0)
279 || !operand_equal_p (vary, varc1, 0))
282 mpz_init_set (loffx, offx);
283 mpz_init_set (loffy, offy);
285 if (cmp == GT_EXPR || cmp == GE_EXPR)
287 tmp = varx; varx = vary; vary = tmp;
288 mpz_swap (offc0, offc1);
289 mpz_swap (loffx, loffy);
290 cmp = swap_tree_comparison (cmp);
294 /* If there is no overflow, the condition implies that
296 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
298 The overflows and underflows may complicate things a bit; each
299 overflow decreases the appropriate offset by M, and underflow
300 increases it by M. The above inequality would not necessarily be
303 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
304 VARX + OFFC0 overflows, but VARX + OFFX does not.
305 This may only happen if OFFX < OFFC0.
306 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
307 VARY + OFFC1 underflows and VARY + OFFY does not.
308 This may only happen if OFFY > OFFC1. */
317 x_ok = (integer_zerop (varx)
318 || mpz_cmp (loffx, offc0) >= 0);
319 y_ok = (integer_zerop (vary)
320 || mpz_cmp (loffy, offc1) <= 0);
326 mpz_sub (bnd, loffx, loffy);
327 mpz_add (bnd, bnd, offc1);
328 mpz_sub (bnd, bnd, offc0);
331 mpz_sub_ui (bnd, bnd, 1);
336 if (mpz_cmp (bnds->below, bnd) < 0)
337 mpz_set (bnds->below, bnd);
341 if (mpz_cmp (bnd, bnds->up) < 0)
342 mpz_set (bnds->up, bnd);
354 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
355 The subtraction is considered to be performed in arbitrary precision,
358 We do not attempt to be too clever regarding the value ranges of X and
359 Y; most of the time, they are just integers or ssa names offsetted by
360 integer. However, we try to use the information contained in the
361 comparisons before the loop (usually created by loop header copying). */
364 bound_difference (struct loop *loop, tree x, tree y, bounds *bnds)
366 tree type = TREE_TYPE (x);
369 mpz_t minx, maxx, miny, maxy;
377 /* Get rid of unnecessary casts, but preserve the value of
382 mpz_init (bnds->below);
386 split_to_var_and_offset (x, &varx, offx);
387 split_to_var_and_offset (y, &vary, offy);
389 if (!integer_zerop (varx)
390 && operand_equal_p (varx, vary, 0))
392 /* Special case VARX == VARY -- we just need to compare the
393 offsets. The matters are a bit more complicated in the
394 case addition of offsets may wrap. */
395 bound_difference_of_offsetted_base (type, offx, offy, bnds);
399 /* Otherwise, use the value ranges to determine the initial
400 estimates on below and up. */
405 determine_value_range (type, varx, offx, minx, maxx);
406 determine_value_range (type, vary, offy, miny, maxy);
408 mpz_sub (bnds->below, minx, maxy);
409 mpz_sub (bnds->up, maxx, miny);
416 /* If both X and Y are constants, we cannot get any more precise. */
417 if (integer_zerop (varx) && integer_zerop (vary))
420 /* Now walk the dominators of the loop header and use the entry
421 guards to refine the estimates. */
422 for (bb = loop->header;
423 bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK;
424 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
426 if (!single_pred_p (bb))
428 e = single_pred_edge (bb);
430 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
433 cond = last_stmt (e->src);
434 c0 = gimple_cond_lhs (cond);
435 cmp = gimple_cond_code (cond);
436 c1 = gimple_cond_rhs (cond);
438 if (e->flags & EDGE_FALSE_VALUE)
439 cmp = invert_tree_comparison (cmp, false);
441 refine_bounds_using_guard (type, varx, offx, vary, offy,
451 /* Update the bounds in BNDS that restrict the value of X to the bounds
452 that restrict the value of X + DELTA. X can be obtained as a
453 difference of two values in TYPE. */
456 bounds_add (bounds *bnds, double_int delta, tree type)
461 mpz_set_double_int (mdelta, delta, false);
464 mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true);
466 mpz_add (bnds->up, bnds->up, mdelta);
467 mpz_add (bnds->below, bnds->below, mdelta);
469 if (mpz_cmp (bnds->up, max) > 0)
470 mpz_set (bnds->up, max);
473 if (mpz_cmp (bnds->below, max) < 0)
474 mpz_set (bnds->below, max);
480 /* Update the bounds in BNDS that restrict the value of X to the bounds
481 that restrict the value of -X. */
484 bounds_negate (bounds *bnds)
488 mpz_init_set (tmp, bnds->up);
489 mpz_neg (bnds->up, bnds->below);
490 mpz_neg (bnds->below, tmp);
494 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
497 inverse (tree x, tree mask)
499 tree type = TREE_TYPE (x);
501 unsigned ctr = tree_floor_log2 (mask);
503 if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT)
505 unsigned HOST_WIDE_INT ix;
506 unsigned HOST_WIDE_INT imask;
507 unsigned HOST_WIDE_INT irslt = 1;
509 gcc_assert (cst_and_fits_in_hwi (x));
510 gcc_assert (cst_and_fits_in_hwi (mask));
512 ix = int_cst_value (x);
513 imask = int_cst_value (mask);
522 rslt = build_int_cst_type (type, irslt);
526 rslt = build_int_cst (type, 1);
529 rslt = int_const_binop (MULT_EXPR, rslt, x, 0);
530 x = int_const_binop (MULT_EXPR, x, x, 0);
532 rslt = int_const_binop (BIT_AND_EXPR, rslt, mask, 0);
538 /* Derives the upper bound BND on the number of executions of loop with exit
539 condition S * i <> C, assuming that this exit is taken. If
540 NO_OVERFLOW is true, then the control variable of the loop does not
541 overflow. If NO_OVERFLOW is true or BNDS.below >= 0, then BNDS.up
542 contains the upper bound on the value of C. */
545 number_of_iterations_ne_max (mpz_t bnd, bool no_overflow, tree c, tree s,
551 /* If the control variable does not overflow, the number of iterations is
552 at most c / s. Otherwise it is at most the period of the control
554 if (!no_overflow && !multiple_of_p (TREE_TYPE (c), c, s))
556 max = double_int_mask (TYPE_PRECISION (TREE_TYPE (c))
557 - tree_low_cst (num_ending_zeros (s), 1));
558 mpz_set_double_int (bnd, max, true);
562 /* Determine the upper bound on C. */
563 if (no_overflow || mpz_sgn (bnds->below) >= 0)
564 mpz_set (bnd, bnds->up);
565 else if (TREE_CODE (c) == INTEGER_CST)
566 mpz_set_double_int (bnd, tree_to_double_int (c), true);
568 mpz_set_double_int (bnd, double_int_mask (TYPE_PRECISION (TREE_TYPE (c))),
572 mpz_set_double_int (d, tree_to_double_int (s), true);
573 mpz_fdiv_q (bnd, bnd, d);
577 /* Determines number of iterations of loop whose ending condition
578 is IV <> FINAL. TYPE is the type of the iv. The number of
579 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
580 we know that the exit must be taken eventually, i.e., that the IV
581 ever reaches the value FINAL (we derived this earlier, and possibly set
582 NITER->assumptions to make sure this is the case). BNDS contains the
583 bounds on the difference FINAL - IV->base. */
586 number_of_iterations_ne (tree type, affine_iv *iv, tree final,
587 struct tree_niter_desc *niter, bool exit_must_be_taken,
590 tree niter_type = unsigned_type_for (type);
591 tree s, c, d, bits, assumption, tmp, bound;
594 niter->control = *iv;
595 niter->bound = final;
596 niter->cmp = NE_EXPR;
598 /* Rearrange the terms so that we get inequality S * i <> C, with S
599 positive. Also cast everything to the unsigned type. If IV does
600 not overflow, BNDS bounds the value of C. Also, this is the
601 case if the computation |FINAL - IV->base| does not overflow, i.e.,
602 if BNDS->below in the result is nonnegative. */
603 if (tree_int_cst_sign_bit (iv->step))
605 s = fold_convert (niter_type,
606 fold_build1 (NEGATE_EXPR, type, iv->step));
607 c = fold_build2 (MINUS_EXPR, niter_type,
608 fold_convert (niter_type, iv->base),
609 fold_convert (niter_type, final));
610 bounds_negate (bnds);
614 s = fold_convert (niter_type, iv->step);
615 c = fold_build2 (MINUS_EXPR, niter_type,
616 fold_convert (niter_type, final),
617 fold_convert (niter_type, iv->base));
621 number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds);
622 niter->max = mpz_get_double_int (niter_type, max, false);
625 /* First the trivial cases -- when the step is 1. */
626 if (integer_onep (s))
632 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
633 is infinite. Otherwise, the number of iterations is
634 (inverse(s/d) * (c/d)) mod (size of mode/d). */
635 bits = num_ending_zeros (s);
636 bound = build_low_bits_mask (niter_type,
637 (TYPE_PRECISION (niter_type)
638 - tree_low_cst (bits, 1)));
640 d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
641 build_int_cst (niter_type, 1), bits);
642 s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
644 if (!exit_must_be_taken)
646 /* If we cannot assume that the exit is taken eventually, record the
647 assumptions for divisibility of c. */
648 assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d);
649 assumption = fold_build2 (EQ_EXPR, boolean_type_node,
650 assumption, build_int_cst (niter_type, 0));
651 if (!integer_nonzerop (assumption))
652 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
653 niter->assumptions, assumption);
656 c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d);
657 tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound));
658 niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound);
662 /* Checks whether we can determine the final value of the control variable
663 of the loop with ending condition IV0 < IV1 (computed in TYPE).
664 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
665 of the step. The assumptions necessary to ensure that the computation
666 of the final value does not overflow are recorded in NITER. If we
667 find the final value, we adjust DELTA and return TRUE. Otherwise
668 we return false. BNDS bounds the value of IV1->base - IV0->base,
669 and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
670 true if we know that the exit must be taken eventually. */
673 number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1,
674 struct tree_niter_desc *niter,
675 tree *delta, tree step,
676 bool exit_must_be_taken, bounds *bnds)
678 tree niter_type = TREE_TYPE (step);
679 tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step);
682 tree assumption = boolean_true_node, bound, noloop;
683 bool ret = false, fv_comp_no_overflow;
685 if (POINTER_TYPE_P (type))
688 if (TREE_CODE (mod) != INTEGER_CST)
690 if (integer_nonzerop (mod))
691 mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
692 tmod = fold_convert (type1, mod);
695 mpz_set_double_int (mmod, tree_to_double_int (mod), true);
696 mpz_neg (mmod, mmod);
698 /* If the induction variable does not overflow and the exit is taken,
699 then the computation of the final value does not overflow. This is
700 also obviously the case if the new final value is equal to the
701 current one. Finally, we postulate this for pointer type variables,
702 as the code cannot rely on the object to that the pointer points being
703 placed at the end of the address space (and more pragmatically,
704 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
705 if (integer_zerop (mod) || POINTER_TYPE_P (type))
706 fv_comp_no_overflow = true;
707 else if (!exit_must_be_taken)
708 fv_comp_no_overflow = false;
710 fv_comp_no_overflow =
711 (iv0->no_overflow && integer_nonzerop (iv0->step))
712 || (iv1->no_overflow && integer_nonzerop (iv1->step));
714 if (integer_nonzerop (iv0->step))
716 /* The final value of the iv is iv1->base + MOD, assuming that this
717 computation does not overflow, and that
718 iv0->base <= iv1->base + MOD. */
719 if (!fv_comp_no_overflow)
721 bound = fold_build2 (MINUS_EXPR, type1,
722 TYPE_MAX_VALUE (type1), tmod);
723 assumption = fold_build2 (LE_EXPR, boolean_type_node,
725 if (integer_zerop (assumption))
728 if (mpz_cmp (mmod, bnds->below) < 0)
729 noloop = boolean_false_node;
730 else if (POINTER_TYPE_P (type))
731 noloop = fold_build2 (GT_EXPR, boolean_type_node,
733 fold_build2 (POINTER_PLUS_EXPR, type,
736 noloop = fold_build2 (GT_EXPR, boolean_type_node,
738 fold_build2 (PLUS_EXPR, type1,
743 /* The final value of the iv is iv0->base - MOD, assuming that this
744 computation does not overflow, and that
745 iv0->base - MOD <= iv1->base. */
746 if (!fv_comp_no_overflow)
748 bound = fold_build2 (PLUS_EXPR, type1,
749 TYPE_MIN_VALUE (type1), tmod);
750 assumption = fold_build2 (GE_EXPR, boolean_type_node,
752 if (integer_zerop (assumption))
755 if (mpz_cmp (mmod, bnds->below) < 0)
756 noloop = boolean_false_node;
757 else if (POINTER_TYPE_P (type))
758 noloop = fold_build2 (GT_EXPR, boolean_type_node,
759 fold_build2 (POINTER_PLUS_EXPR, type,
761 fold_build1 (NEGATE_EXPR,
765 noloop = fold_build2 (GT_EXPR, boolean_type_node,
766 fold_build2 (MINUS_EXPR, type1,
771 if (!integer_nonzerop (assumption))
772 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
775 if (!integer_zerop (noloop))
776 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
779 bounds_add (bnds, tree_to_double_int (mod), type);
780 *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod);
788 /* Add assertions to NITER that ensure that the control variable of the loop
789 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
790 are TYPE. Returns false if we can prove that there is an overflow, true
791 otherwise. STEP is the absolute value of the step. */
794 assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
795 struct tree_niter_desc *niter, tree step)
797 tree bound, d, assumption, diff;
798 tree niter_type = TREE_TYPE (step);
800 if (integer_nonzerop (iv0->step))
802 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
803 if (iv0->no_overflow)
806 /* If iv0->base is a constant, we can determine the last value before
807 overflow precisely; otherwise we conservatively assume
810 if (TREE_CODE (iv0->base) == INTEGER_CST)
812 d = fold_build2 (MINUS_EXPR, niter_type,
813 fold_convert (niter_type, TYPE_MAX_VALUE (type)),
814 fold_convert (niter_type, iv0->base));
815 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
818 diff = fold_build2 (MINUS_EXPR, niter_type, step,
819 build_int_cst (niter_type, 1));
820 bound = fold_build2 (MINUS_EXPR, type,
821 TYPE_MAX_VALUE (type), fold_convert (type, diff));
822 assumption = fold_build2 (LE_EXPR, boolean_type_node,
827 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
828 if (iv1->no_overflow)
831 if (TREE_CODE (iv1->base) == INTEGER_CST)
833 d = fold_build2 (MINUS_EXPR, niter_type,
834 fold_convert (niter_type, iv1->base),
835 fold_convert (niter_type, TYPE_MIN_VALUE (type)));
836 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
839 diff = fold_build2 (MINUS_EXPR, niter_type, step,
840 build_int_cst (niter_type, 1));
841 bound = fold_build2 (PLUS_EXPR, type,
842 TYPE_MIN_VALUE (type), fold_convert (type, diff));
843 assumption = fold_build2 (GE_EXPR, boolean_type_node,
847 if (integer_zerop (assumption))
849 if (!integer_nonzerop (assumption))
850 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
851 niter->assumptions, assumption);
853 iv0->no_overflow = true;
854 iv1->no_overflow = true;
858 /* Add an assumption to NITER that a loop whose ending condition
859 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
860 bounds the value of IV1->base - IV0->base. */
863 assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
864 struct tree_niter_desc *niter, bounds *bnds)
866 tree assumption = boolean_true_node, bound, diff;
867 tree mbz, mbzl, mbzr, type1;
868 bool rolls_p, no_overflow_p;
872 /* We are going to compute the number of iterations as
873 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
874 variant of TYPE. This formula only works if
876 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
878 (where MAX is the maximum value of the unsigned variant of TYPE, and
879 the computations in this formula are performed in full precision,
880 i.e., without overflows).
882 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
883 we have a condition of the form iv0->base - step < iv1->base before the loop,
884 and for loops iv0->base < iv1->base - step * i the condition
885 iv0->base < iv1->base + step, due to loop header copying, which enable us
886 to prove the lower bound.
888 The upper bound is more complicated. Unless the expressions for initial
889 and final value themselves contain enough information, we usually cannot
890 derive it from the context. */
892 /* First check whether the answer does not follow from the bounds we gathered
894 if (integer_nonzerop (iv0->step))
895 dstep = tree_to_double_int (iv0->step);
898 dstep = double_int_sext (tree_to_double_int (iv1->step),
899 TYPE_PRECISION (type));
900 dstep = double_int_neg (dstep);
904 mpz_set_double_int (mstep, dstep, true);
905 mpz_neg (mstep, mstep);
906 mpz_add_ui (mstep, mstep, 1);
908 rolls_p = mpz_cmp (mstep, bnds->below) <= 0;
911 mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true);
912 mpz_add (max, max, mstep);
913 no_overflow_p = (mpz_cmp (bnds->up, max) <= 0
914 /* For pointers, only values lying inside a single object
915 can be compared or manipulated by pointer arithmetics.
916 Gcc in general does not allow or handle objects larger
917 than half of the address space, hence the upper bound
918 is satisfied for pointers. */
919 || POINTER_TYPE_P (type));
923 if (rolls_p && no_overflow_p)
927 if (POINTER_TYPE_P (type))
930 /* Now the hard part; we must formulate the assumption(s) as expressions, and
931 we must be careful not to introduce overflow. */
933 if (integer_nonzerop (iv0->step))
935 diff = fold_build2 (MINUS_EXPR, type1,
936 iv0->step, build_int_cst (type1, 1));
938 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
939 0 address never belongs to any object, we can assume this for
941 if (!POINTER_TYPE_P (type))
943 bound = fold_build2 (PLUS_EXPR, type1,
944 TYPE_MIN_VALUE (type), diff);
945 assumption = fold_build2 (GE_EXPR, boolean_type_node,
949 /* And then we can compute iv0->base - diff, and compare it with
951 mbzl = fold_build2 (MINUS_EXPR, type1,
952 fold_convert (type1, iv0->base), diff);
953 mbzr = fold_convert (type1, iv1->base);
957 diff = fold_build2 (PLUS_EXPR, type1,
958 iv1->step, build_int_cst (type1, 1));
960 if (!POINTER_TYPE_P (type))
962 bound = fold_build2 (PLUS_EXPR, type1,
963 TYPE_MAX_VALUE (type), diff);
964 assumption = fold_build2 (LE_EXPR, boolean_type_node,
968 mbzl = fold_convert (type1, iv0->base);
969 mbzr = fold_build2 (MINUS_EXPR, type1,
970 fold_convert (type1, iv1->base), diff);
973 if (!integer_nonzerop (assumption))
974 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
975 niter->assumptions, assumption);
978 mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr);
979 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
980 niter->may_be_zero, mbz);
984 /* Determines number of iterations of loop whose ending condition
985 is IV0 < IV1. TYPE is the type of the iv. The number of
986 iterations is stored to NITER. BNDS bounds the difference
987 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
988 that the exit must be taken eventually. */
991 number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
992 struct tree_niter_desc *niter,
993 bool exit_must_be_taken, bounds *bnds)
995 tree niter_type = unsigned_type_for (type);
999 if (integer_nonzerop (iv0->step))
1001 niter->control = *iv0;
1002 niter->cmp = LT_EXPR;
1003 niter->bound = iv1->base;
1007 niter->control = *iv1;
1008 niter->cmp = GT_EXPR;
1009 niter->bound = iv0->base;
1012 delta = fold_build2 (MINUS_EXPR, niter_type,
1013 fold_convert (niter_type, iv1->base),
1014 fold_convert (niter_type, iv0->base));
1016 /* First handle the special case that the step is +-1. */
1017 if ((integer_onep (iv0->step) && integer_zerop (iv1->step))
1018 || (integer_all_onesp (iv1->step) && integer_zerop (iv0->step)))
1020 /* for (i = iv0->base; i < iv1->base; i++)
1024 for (i = iv1->base; i > iv0->base; i--).
1026 In both cases # of iterations is iv1->base - iv0->base, assuming that
1027 iv1->base >= iv0->base.
1029 First try to derive a lower bound on the value of
1030 iv1->base - iv0->base, computed in full precision. If the difference
1031 is nonnegative, we are done, otherwise we must record the
1034 if (mpz_sgn (bnds->below) < 0)
1035 niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
1036 iv1->base, iv0->base);
1037 niter->niter = delta;
1038 niter->max = mpz_get_double_int (niter_type, bnds->up, false);
1042 if (integer_nonzerop (iv0->step))
1043 step = fold_convert (niter_type, iv0->step);
1045 step = fold_convert (niter_type,
1046 fold_build1 (NEGATE_EXPR, type, iv1->step));
1048 /* If we can determine the final value of the control iv exactly, we can
1049 transform the condition to != comparison. In particular, this will be
1050 the case if DELTA is constant. */
1051 if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step,
1052 exit_must_be_taken, bnds))
1056 zps.base = build_int_cst (niter_type, 0);
1058 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1059 zps does not overflow. */
1060 zps.no_overflow = true;
1062 return number_of_iterations_ne (type, &zps, delta, niter, true, bnds);
1065 /* Make sure that the control iv does not overflow. */
1066 if (!assert_no_overflow_lt (type, iv0, iv1, niter, step))
1069 /* We determine the number of iterations as (delta + step - 1) / step. For
1070 this to work, we must know that iv1->base >= iv0->base - step + 1,
1071 otherwise the loop does not roll. */
1072 assert_loop_rolls_lt (type, iv0, iv1, niter, bnds);
1074 s = fold_build2 (MINUS_EXPR, niter_type,
1075 step, build_int_cst (niter_type, 1));
1076 delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
1077 niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
1081 mpz_set_double_int (mstep, tree_to_double_int (step), true);
1082 mpz_add (tmp, bnds->up, mstep);
1083 mpz_sub_ui (tmp, tmp, 1);
1084 mpz_fdiv_q (tmp, tmp, mstep);
1085 niter->max = mpz_get_double_int (niter_type, tmp, false);
1092 /* Determines number of iterations of loop whose ending condition
1093 is IV0 <= IV1. TYPE is the type of the iv. The number of
1094 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
1095 we know that this condition must eventually become false (we derived this
1096 earlier, and possibly set NITER->assumptions to make sure this
1097 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1100 number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1,
1101 struct tree_niter_desc *niter, bool exit_must_be_taken,
1106 if (POINTER_TYPE_P (type))
1109 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1110 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1111 value of the type. This we must know anyway, since if it is
1112 equal to this value, the loop rolls forever. We do not check
1113 this condition for pointer type ivs, as the code cannot rely on
1114 the object to that the pointer points being placed at the end of
1115 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1116 not defined for pointers). */
1118 if (!exit_must_be_taken && !POINTER_TYPE_P (type))
1120 if (integer_nonzerop (iv0->step))
1121 assumption = fold_build2 (NE_EXPR, boolean_type_node,
1122 iv1->base, TYPE_MAX_VALUE (type));
1124 assumption = fold_build2 (NE_EXPR, boolean_type_node,
1125 iv0->base, TYPE_MIN_VALUE (type));
1127 if (integer_zerop (assumption))
1129 if (!integer_nonzerop (assumption))
1130 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1131 niter->assumptions, assumption);
1134 if (integer_nonzerop (iv0->step))
1136 if (POINTER_TYPE_P (type))
1137 iv1->base = fold_build2 (POINTER_PLUS_EXPR, type, iv1->base,
1138 build_int_cst (type1, 1));
1140 iv1->base = fold_build2 (PLUS_EXPR, type1, iv1->base,
1141 build_int_cst (type1, 1));
1143 else if (POINTER_TYPE_P (type))
1144 iv0->base = fold_build2 (POINTER_PLUS_EXPR, type, iv0->base,
1145 fold_build1 (NEGATE_EXPR, type1,
1146 build_int_cst (type1, 1)));
1148 iv0->base = fold_build2 (MINUS_EXPR, type1,
1149 iv0->base, build_int_cst (type1, 1));
1151 bounds_add (bnds, double_int_one, type1);
1153 return number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken,
1157 /* Dumps description of affine induction variable IV to FILE. */
1160 dump_affine_iv (FILE *file, affine_iv *iv)
1162 if (!integer_zerop (iv->step))
1163 fprintf (file, "[");
1165 print_generic_expr (dump_file, iv->base, TDF_SLIM);
1167 if (!integer_zerop (iv->step))
1169 fprintf (file, ", + , ");
1170 print_generic_expr (dump_file, iv->step, TDF_SLIM);
1171 fprintf (file, "]%s", iv->no_overflow ? "(no_overflow)" : "");
1175 /* Determine the number of iterations according to condition (for staying
1176 inside loop) which compares two induction variables using comparison
1177 operator CODE. The induction variable on left side of the comparison
1178 is IV0, the right-hand side is IV1. Both induction variables must have
1179 type TYPE, which must be an integer or pointer type. The steps of the
1180 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1182 LOOP is the loop whose number of iterations we are determining.
1184 ONLY_EXIT is true if we are sure this is the only way the loop could be
1185 exited (including possibly non-returning function calls, exceptions, etc.)
1186 -- in this case we can use the information whether the control induction
1187 variables can overflow or not in a more efficient way.
1189 The results (number of iterations and assumptions as described in
1190 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
1191 Returns false if it fails to determine number of iterations, true if it
1192 was determined (possibly with some assumptions). */
1195 number_of_iterations_cond (struct loop *loop,
1196 tree type, affine_iv *iv0, enum tree_code code,
1197 affine_iv *iv1, struct tree_niter_desc *niter,
1200 bool exit_must_be_taken = false, ret;
1203 /* The meaning of these assumptions is this:
1205 then the rest of information does not have to be valid
1206 if may_be_zero then the loop does not roll, even if
1208 niter->assumptions = boolean_true_node;
1209 niter->may_be_zero = boolean_false_node;
1210 niter->niter = NULL_TREE;
1211 niter->max = double_int_zero;
1213 niter->bound = NULL_TREE;
1214 niter->cmp = ERROR_MARK;
1216 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1217 the control variable is on lhs. */
1218 if (code == GE_EXPR || code == GT_EXPR
1219 || (code == NE_EXPR && integer_zerop (iv0->step)))
1222 code = swap_tree_comparison (code);
1225 if (POINTER_TYPE_P (type))
1227 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1228 to the same object. If they do, the control variable cannot wrap
1229 (as wrap around the bounds of memory will never return a pointer
1230 that would be guaranteed to point to the same object, even if we
1231 avoid undefined behavior by casting to size_t and back). */
1232 iv0->no_overflow = true;
1233 iv1->no_overflow = true;
1236 /* If the control induction variable does not overflow and the only exit
1237 from the loop is the one that we analyze, we know it must be taken
1241 if (!integer_zerop (iv0->step) && iv0->no_overflow)
1242 exit_must_be_taken = true;
1243 else if (!integer_zerop (iv1->step) && iv1->no_overflow)
1244 exit_must_be_taken = true;
1247 /* We can handle the case when neither of the sides of the comparison is
1248 invariant, provided that the test is NE_EXPR. This rarely occurs in
1249 practice, but it is simple enough to manage. */
1250 if (!integer_zerop (iv0->step) && !integer_zerop (iv1->step))
1252 if (code != NE_EXPR)
1255 iv0->step = fold_binary_to_constant (MINUS_EXPR, type,
1256 iv0->step, iv1->step);
1257 iv0->no_overflow = false;
1258 iv1->step = build_int_cst (type, 0);
1259 iv1->no_overflow = true;
1262 /* If the result of the comparison is a constant, the loop is weird. More
1263 precise handling would be possible, but the situation is not common enough
1264 to waste time on it. */
1265 if (integer_zerop (iv0->step) && integer_zerop (iv1->step))
1268 /* Ignore loops of while (i-- < 10) type. */
1269 if (code != NE_EXPR)
1271 if (iv0->step && tree_int_cst_sign_bit (iv0->step))
1274 if (!integer_zerop (iv1->step) && !tree_int_cst_sign_bit (iv1->step))
1278 /* If the loop exits immediately, there is nothing to do. */
1279 if (integer_zerop (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
1281 niter->niter = build_int_cst (unsigned_type_for (type), 0);
1282 niter->max = double_int_zero;
1286 /* OK, now we know we have a senseful loop. Handle several cases, depending
1287 on what comparison operator is used. */
1288 bound_difference (loop, iv1->base, iv0->base, &bnds);
1290 if (dump_file && (dump_flags & TDF_DETAILS))
1293 "Analyzing # of iterations of loop %d\n", loop->num);
1295 fprintf (dump_file, " exit condition ");
1296 dump_affine_iv (dump_file, iv0);
1297 fprintf (dump_file, " %s ",
1298 code == NE_EXPR ? "!="
1299 : code == LT_EXPR ? "<"
1301 dump_affine_iv (dump_file, iv1);
1302 fprintf (dump_file, "\n");
1304 fprintf (dump_file, " bounds on difference of bases: ");
1305 mpz_out_str (dump_file, 10, bnds.below);
1306 fprintf (dump_file, " ... ");
1307 mpz_out_str (dump_file, 10, bnds.up);
1308 fprintf (dump_file, "\n");
1314 gcc_assert (integer_zerop (iv1->step));
1315 ret = number_of_iterations_ne (type, iv0, iv1->base, niter,
1316 exit_must_be_taken, &bnds);
1320 ret = number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken,
1325 ret = number_of_iterations_le (type, iv0, iv1, niter, exit_must_be_taken,
1333 mpz_clear (bnds.up);
1334 mpz_clear (bnds.below);
1336 if (dump_file && (dump_flags & TDF_DETAILS))
1340 fprintf (dump_file, " result:\n");
1341 if (!integer_nonzerop (niter->assumptions))
1343 fprintf (dump_file, " under assumptions ");
1344 print_generic_expr (dump_file, niter->assumptions, TDF_SLIM);
1345 fprintf (dump_file, "\n");
1348 if (!integer_zerop (niter->may_be_zero))
1350 fprintf (dump_file, " zero if ");
1351 print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
1352 fprintf (dump_file, "\n");
1355 fprintf (dump_file, " # of iterations ");
1356 print_generic_expr (dump_file, niter->niter, TDF_SLIM);
1357 fprintf (dump_file, ", bounded by ");
1358 dump_double_int (dump_file, niter->max, true);
1359 fprintf (dump_file, "\n");
1362 fprintf (dump_file, " failed\n\n");
1367 /* Substitute NEW for OLD in EXPR and fold the result. */
1370 simplify_replace_tree (tree expr, tree old, tree new_tree)
1373 tree ret = NULL_TREE, e, se;
1378 /* Do not bother to replace constants. */
1379 if (CONSTANT_CLASS_P (old))
1383 || operand_equal_p (expr, old, 0))
1384 return unshare_expr (new_tree);
1389 n = TREE_OPERAND_LENGTH (expr);
1390 for (i = 0; i < n; i++)
1392 e = TREE_OPERAND (expr, i);
1393 se = simplify_replace_tree (e, old, new_tree);
1398 ret = copy_node (expr);
1400 TREE_OPERAND (ret, i) = se;
1403 return (ret ? fold (ret) : expr);
1406 /* Expand definitions of ssa names in EXPR as long as they are simple
1407 enough, and return the new expression. */
1410 expand_simple_operations (tree expr)
1413 tree ret = NULL_TREE, e, ee, e1;
1414 enum tree_code code;
1417 if (expr == NULL_TREE)
1420 if (is_gimple_min_invariant (expr))
1423 code = TREE_CODE (expr);
1424 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
1426 n = TREE_OPERAND_LENGTH (expr);
1427 for (i = 0; i < n; i++)
1429 e = TREE_OPERAND (expr, i);
1430 ee = expand_simple_operations (e);
1435 ret = copy_node (expr);
1437 TREE_OPERAND (ret, i) = ee;
1443 fold_defer_overflow_warnings ();
1445 fold_undefer_and_ignore_overflow_warnings ();
1449 if (TREE_CODE (expr) != SSA_NAME)
1452 stmt = SSA_NAME_DEF_STMT (expr);
1453 if (gimple_code (stmt) == GIMPLE_PHI)
1455 basic_block src, dest;
1457 if (gimple_phi_num_args (stmt) != 1)
1459 e = PHI_ARG_DEF (stmt, 0);
1461 /* Avoid propagating through loop exit phi nodes, which
1462 could break loop-closed SSA form restrictions. */
1463 dest = gimple_bb (stmt);
1464 src = single_pred (dest);
1465 if (TREE_CODE (e) == SSA_NAME
1466 && src->loop_father != dest->loop_father)
1469 return expand_simple_operations (e);
1471 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1474 e = gimple_assign_rhs1 (stmt);
1475 code = gimple_assign_rhs_code (stmt);
1476 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1478 if (is_gimple_min_invariant (e))
1481 if (code == SSA_NAME)
1482 return expand_simple_operations (e);
1490 /* Casts are simple. */
1491 ee = expand_simple_operations (e);
1492 return fold_build1 (code, TREE_TYPE (expr), ee);
1496 case POINTER_PLUS_EXPR:
1497 /* And increments and decrements by a constant are simple. */
1498 e1 = gimple_assign_rhs2 (stmt);
1499 if (!is_gimple_min_invariant (e1))
1502 ee = expand_simple_operations (e);
1503 return fold_build2 (code, TREE_TYPE (expr), ee, e1);
1510 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1511 expression (or EXPR unchanged, if no simplification was possible). */
1514 tree_simplify_using_condition_1 (tree cond, tree expr)
1517 tree e, te, e0, e1, e2, notcond;
1518 enum tree_code code = TREE_CODE (expr);
1520 if (code == INTEGER_CST)
1523 if (code == TRUTH_OR_EXPR
1524 || code == TRUTH_AND_EXPR
1525 || code == COND_EXPR)
1529 e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0));
1530 if (TREE_OPERAND (expr, 0) != e0)
1533 e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1));
1534 if (TREE_OPERAND (expr, 1) != e1)
1537 if (code == COND_EXPR)
1539 e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2));
1540 if (TREE_OPERAND (expr, 2) != e2)
1548 if (code == COND_EXPR)
1549 expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
1551 expr = fold_build2 (code, boolean_type_node, e0, e1);
1557 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
1558 propagation, and vice versa. Fold does not handle this, since it is
1559 considered too expensive. */
1560 if (TREE_CODE (cond) == EQ_EXPR)
1562 e0 = TREE_OPERAND (cond, 0);
1563 e1 = TREE_OPERAND (cond, 1);
1565 /* We know that e0 == e1. Check whether we cannot simplify expr
1567 e = simplify_replace_tree (expr, e0, e1);
1568 if (integer_zerop (e) || integer_nonzerop (e))
1571 e = simplify_replace_tree (expr, e1, e0);
1572 if (integer_zerop (e) || integer_nonzerop (e))
1575 if (TREE_CODE (expr) == EQ_EXPR)
1577 e0 = TREE_OPERAND (expr, 0);
1578 e1 = TREE_OPERAND (expr, 1);
1580 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
1581 e = simplify_replace_tree (cond, e0, e1);
1582 if (integer_zerop (e))
1584 e = simplify_replace_tree (cond, e1, e0);
1585 if (integer_zerop (e))
1588 if (TREE_CODE (expr) == NE_EXPR)
1590 e0 = TREE_OPERAND (expr, 0);
1591 e1 = TREE_OPERAND (expr, 1);
1593 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
1594 e = simplify_replace_tree (cond, e0, e1);
1595 if (integer_zerop (e))
1596 return boolean_true_node;
1597 e = simplify_replace_tree (cond, e1, e0);
1598 if (integer_zerop (e))
1599 return boolean_true_node;
1602 te = expand_simple_operations (expr);
1604 /* Check whether COND ==> EXPR. */
1605 notcond = invert_truthvalue (cond);
1606 e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te);
1607 if (e && integer_nonzerop (e))
1610 /* Check whether COND ==> not EXPR. */
1611 e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te);
1612 if (e && integer_zerop (e))
1618 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1619 expression (or EXPR unchanged, if no simplification was possible).
1620 Wrapper around tree_simplify_using_condition_1 that ensures that chains
1621 of simple operations in definitions of ssa names in COND are expanded,
1622 so that things like casts or incrementing the value of the bound before
1623 the loop do not cause us to fail. */
1626 tree_simplify_using_condition (tree cond, tree expr)
1628 cond = expand_simple_operations (cond);
1630 return tree_simplify_using_condition_1 (cond, expr);
1633 /* Tries to simplify EXPR using the conditions on entry to LOOP.
1634 Returns the simplified expression (or EXPR unchanged, if no
1635 simplification was possible).*/
1638 simplify_using_initial_conditions (struct loop *loop, tree expr)
1646 if (TREE_CODE (expr) == INTEGER_CST)
1649 /* Limit walking the dominators to avoid quadraticness in
1650 the number of BBs times the number of loops in degenerate
1652 for (bb = loop->header;
1653 bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK;
1654 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1656 if (!single_pred_p (bb))
1658 e = single_pred_edge (bb);
1660 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
1663 stmt = last_stmt (e->src);
1664 cond = fold_build2 (gimple_cond_code (stmt),
1666 gimple_cond_lhs (stmt),
1667 gimple_cond_rhs (stmt));
1668 if (e->flags & EDGE_FALSE_VALUE)
1669 cond = invert_truthvalue (cond);
1670 expr = tree_simplify_using_condition (cond, expr);
1677 /* Tries to simplify EXPR using the evolutions of the loop invariants
1678 in the superloops of LOOP. Returns the simplified expression
1679 (or EXPR unchanged, if no simplification was possible). */
1682 simplify_using_outer_evolutions (struct loop *loop, tree expr)
1684 enum tree_code code = TREE_CODE (expr);
1688 if (is_gimple_min_invariant (expr))
1691 if (code == TRUTH_OR_EXPR
1692 || code == TRUTH_AND_EXPR
1693 || code == COND_EXPR)
1697 e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
1698 if (TREE_OPERAND (expr, 0) != e0)
1701 e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
1702 if (TREE_OPERAND (expr, 1) != e1)
1705 if (code == COND_EXPR)
1707 e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
1708 if (TREE_OPERAND (expr, 2) != e2)
1716 if (code == COND_EXPR)
1717 expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
1719 expr = fold_build2 (code, boolean_type_node, e0, e1);
1725 e = instantiate_parameters (loop, expr);
1726 if (is_gimple_min_invariant (e))
1732 /* Returns true if EXIT is the only possible exit from LOOP. */
1735 loop_only_exit_p (const struct loop *loop, const_edge exit)
1738 gimple_stmt_iterator bsi;
1742 if (exit != single_exit (loop))
1745 body = get_loop_body (loop);
1746 for (i = 0; i < loop->num_nodes; i++)
1748 for (bsi = gsi_start_bb (body[i]); !gsi_end_p (bsi); gsi_next (&bsi))
1750 call = gsi_stmt (bsi);
1751 if (gimple_code (call) != GIMPLE_CALL)
1754 if (gimple_has_side_effects (call))
1766 /* Stores description of number of iterations of LOOP derived from
1767 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
1768 useful information could be derived (and fields of NITER has
1769 meaning described in comments at struct tree_niter_desc
1770 declaration), false otherwise. If WARN is true and
1771 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1772 potentially unsafe assumptions. */
1775 number_of_iterations_exit (struct loop *loop, edge exit,
1776 struct tree_niter_desc *niter,
1782 enum tree_code code;
1785 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
1788 niter->assumptions = boolean_false_node;
1789 stmt = last_stmt (exit->src);
1790 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
1793 /* We want the condition for staying inside loop. */
1794 code = gimple_cond_code (stmt);
1795 if (exit->flags & EDGE_TRUE_VALUE)
1796 code = invert_tree_comparison (code, false);
1811 op0 = gimple_cond_lhs (stmt);
1812 op1 = gimple_cond_rhs (stmt);
1813 type = TREE_TYPE (op0);
1815 if (TREE_CODE (type) != INTEGER_TYPE
1816 && !POINTER_TYPE_P (type))
1819 if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, false))
1821 if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, false))
1824 /* We don't want to see undefined signed overflow warnings while
1825 computing the number of iterations. */
1826 fold_defer_overflow_warnings ();
1828 iv0.base = expand_simple_operations (iv0.base);
1829 iv1.base = expand_simple_operations (iv1.base);
1830 if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter,
1831 loop_only_exit_p (loop, exit)))
1833 fold_undefer_and_ignore_overflow_warnings ();
1839 niter->assumptions = simplify_using_outer_evolutions (loop,
1840 niter->assumptions);
1841 niter->may_be_zero = simplify_using_outer_evolutions (loop,
1842 niter->may_be_zero);
1843 niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
1847 = simplify_using_initial_conditions (loop,
1848 niter->assumptions);
1850 = simplify_using_initial_conditions (loop,
1851 niter->may_be_zero);
1853 fold_undefer_and_ignore_overflow_warnings ();
1855 if (integer_onep (niter->assumptions))
1858 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1859 But if we can prove that there is overflow or some other source of weird
1860 behavior, ignore the loop even with -funsafe-loop-optimizations. */
1861 if (integer_zerop (niter->assumptions))
1864 if (flag_unsafe_loop_optimizations)
1865 niter->assumptions = boolean_true_node;
1869 const char *wording;
1870 location_t loc = gimple_location (stmt);
1872 /* We can provide a more specific warning if one of the operator is
1873 constant and the other advances by +1 or -1. */
1874 if (!integer_zerop (iv1.step)
1875 ? (integer_zerop (iv0.step)
1876 && (integer_onep (iv1.step) || integer_all_onesp (iv1.step)))
1877 : (integer_onep (iv0.step) || integer_all_onesp (iv0.step)))
1879 flag_unsafe_loop_optimizations
1880 ? N_("assuming that the loop is not infinite")
1881 : N_("cannot optimize possibly infinite loops");
1884 flag_unsafe_loop_optimizations
1885 ? N_("assuming that the loop counter does not overflow")
1886 : N_("cannot optimize loop, the loop counter may overflow");
1888 warning_at ((LOCATION_LINE (loc) > 0) ? loc : input_location,
1889 OPT_Wunsafe_loop_optimizations, "%s", gettext (wording));
1892 return flag_unsafe_loop_optimizations;
1895 /* Try to determine the number of iterations of LOOP. If we succeed,
1896 expression giving number of iterations is returned and *EXIT is
1897 set to the edge from that the information is obtained. Otherwise
1898 chrec_dont_know is returned. */
1901 find_loop_niter (struct loop *loop, edge *exit)
1904 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1906 tree niter = NULL_TREE, aniter;
1907 struct tree_niter_desc desc;
1910 FOR_EACH_VEC_ELT (edge, exits, i, ex)
1912 if (!just_once_each_iteration_p (loop, ex->src))
1915 if (!number_of_iterations_exit (loop, ex, &desc, false))
1918 if (integer_nonzerop (desc.may_be_zero))
1920 /* We exit in the first iteration through this exit.
1921 We won't find anything better. */
1922 niter = build_int_cst (unsigned_type_node, 0);
1927 if (!integer_zerop (desc.may_be_zero))
1930 aniter = desc.niter;
1934 /* Nothing recorded yet. */
1940 /* Prefer constants, the lower the better. */
1941 if (TREE_CODE (aniter) != INTEGER_CST)
1944 if (TREE_CODE (niter) != INTEGER_CST)
1951 if (tree_int_cst_lt (aniter, niter))
1958 VEC_free (edge, heap, exits);
1960 return niter ? niter : chrec_dont_know;
1963 /* Return true if loop is known to have bounded number of iterations. */
1966 finite_loop_p (struct loop *loop)
1969 VEC (edge, heap) *exits;
1971 struct tree_niter_desc desc;
1972 bool finite = false;
1974 if (flag_unsafe_loop_optimizations)
1976 if ((TREE_READONLY (current_function_decl)
1977 || DECL_PURE_P (current_function_decl))
1978 && !DECL_LOOPING_CONST_OR_PURE_P (current_function_decl))
1980 if (dump_file && (dump_flags & TDF_DETAILS))
1981 fprintf (dump_file, "Found loop %i to be finite: it is within pure or const function.\n",
1986 exits = get_loop_exit_edges (loop);
1987 FOR_EACH_VEC_ELT (edge, exits, i, ex)
1989 if (!just_once_each_iteration_p (loop, ex->src))
1992 if (number_of_iterations_exit (loop, ex, &desc, false))
1994 if (dump_file && (dump_flags & TDF_DETAILS))
1996 fprintf (dump_file, "Found loop %i to be finite: iterating ", loop->num);
1997 print_generic_expr (dump_file, desc.niter, TDF_SLIM);
1998 fprintf (dump_file, " times\n");
2004 VEC_free (edge, heap, exits);
2010 Analysis of a number of iterations of a loop by a brute-force evaluation.
2014 /* Bound on the number of iterations we try to evaluate. */
2016 #define MAX_ITERATIONS_TO_TRACK \
2017 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
2019 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
2020 result by a chain of operations such that all but exactly one of their
2021 operands are constants. */
2024 chain_of_csts_start (struct loop *loop, tree x)
2026 gimple stmt = SSA_NAME_DEF_STMT (x);
2028 basic_block bb = gimple_bb (stmt);
2029 enum tree_code code;
2032 || !flow_bb_inside_loop_p (loop, bb))
2035 if (gimple_code (stmt) == GIMPLE_PHI)
2037 if (bb == loop->header)
2043 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2046 code = gimple_assign_rhs_code (stmt);
2047 if (gimple_references_memory_p (stmt)
2048 || TREE_CODE_CLASS (code) == tcc_reference
2049 || (code == ADDR_EXPR
2050 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
2053 use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
2054 if (use == NULL_TREE)
2057 return chain_of_csts_start (loop, use);
2060 /* Determines whether the expression X is derived from a result of a phi node
2061 in header of LOOP such that
2063 * the derivation of X consists only from operations with constants
2064 * the initial value of the phi node is constant
2065 * the value of the phi node in the next iteration can be derived from the
2066 value in the current iteration by a chain of operations with constants.
2068 If such phi node exists, it is returned, otherwise NULL is returned. */
2071 get_base_for (struct loop *loop, tree x)
2076 if (is_gimple_min_invariant (x))
2079 phi = chain_of_csts_start (loop, x);
2083 init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
2084 next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
2086 if (TREE_CODE (next) != SSA_NAME)
2089 if (!is_gimple_min_invariant (init))
2092 if (chain_of_csts_start (loop, next) != phi)
2098 /* Given an expression X, then
2100 * if X is NULL_TREE, we return the constant BASE.
2101 * otherwise X is a SSA name, whose value in the considered loop is derived
2102 by a chain of operations with constant from a result of a phi node in
2103 the header of the loop. Then we return value of X when the value of the
2104 result of this phi node is given by the constant BASE. */
2107 get_val_for (tree x, tree base)
2111 gcc_assert (is_gimple_min_invariant (base));
2116 stmt = SSA_NAME_DEF_STMT (x);
2117 if (gimple_code (stmt) == GIMPLE_PHI)
2120 gcc_assert (is_gimple_assign (stmt));
2122 /* STMT must be either an assignment of a single SSA name or an
2123 expression involving an SSA name and a constant. Try to fold that
2124 expression using the value for the SSA name. */
2125 if (gimple_assign_ssa_name_copy_p (stmt))
2126 return get_val_for (gimple_assign_rhs1 (stmt), base);
2127 else if (gimple_assign_rhs_class (stmt) == GIMPLE_UNARY_RHS
2128 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
2130 return fold_build1 (gimple_assign_rhs_code (stmt),
2131 gimple_expr_type (stmt),
2132 get_val_for (gimple_assign_rhs1 (stmt), base));
2134 else if (gimple_assign_rhs_class (stmt) == GIMPLE_BINARY_RHS)
2136 tree rhs1 = gimple_assign_rhs1 (stmt);
2137 tree rhs2 = gimple_assign_rhs2 (stmt);
2138 if (TREE_CODE (rhs1) == SSA_NAME)
2139 rhs1 = get_val_for (rhs1, base);
2140 else if (TREE_CODE (rhs2) == SSA_NAME)
2141 rhs2 = get_val_for (rhs2, base);
2144 return fold_build2 (gimple_assign_rhs_code (stmt),
2145 gimple_expr_type (stmt), rhs1, rhs2);
2152 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2153 by brute force -- i.e. by determining the value of the operands of the
2154 condition at EXIT in first few iterations of the loop (assuming that
2155 these values are constant) and determining the first one in that the
2156 condition is not satisfied. Returns the constant giving the number
2157 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
2160 loop_niter_by_eval (struct loop *loop, edge exit)
2163 tree op[2], val[2], next[2], aval[2];
2168 cond = last_stmt (exit->src);
2169 if (!cond || gimple_code (cond) != GIMPLE_COND)
2170 return chrec_dont_know;
2172 cmp = gimple_cond_code (cond);
2173 if (exit->flags & EDGE_TRUE_VALUE)
2174 cmp = invert_tree_comparison (cmp, false);
2184 op[0] = gimple_cond_lhs (cond);
2185 op[1] = gimple_cond_rhs (cond);
2189 return chrec_dont_know;
2192 for (j = 0; j < 2; j++)
2194 if (is_gimple_min_invariant (op[j]))
2197 next[j] = NULL_TREE;
2202 phi = get_base_for (loop, op[j]);
2204 return chrec_dont_know;
2205 val[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
2206 next[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
2210 /* Don't issue signed overflow warnings. */
2211 fold_defer_overflow_warnings ();
2213 for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
2215 for (j = 0; j < 2; j++)
2216 aval[j] = get_val_for (op[j], val[j]);
2218 acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]);
2219 if (acnd && integer_zerop (acnd))
2221 fold_undefer_and_ignore_overflow_warnings ();
2222 if (dump_file && (dump_flags & TDF_DETAILS))
2224 "Proved that loop %d iterates %d times using brute force.\n",
2226 return build_int_cst (unsigned_type_node, i);
2229 for (j = 0; j < 2; j++)
2231 val[j] = get_val_for (next[j], val[j]);
2232 if (!is_gimple_min_invariant (val[j]))
2234 fold_undefer_and_ignore_overflow_warnings ();
2235 return chrec_dont_know;
2240 fold_undefer_and_ignore_overflow_warnings ();
2242 return chrec_dont_know;
2245 /* Finds the exit of the LOOP by that the loop exits after a constant
2246 number of iterations and stores the exit edge to *EXIT. The constant
2247 giving the number of iterations of LOOP is returned. The number of
2248 iterations is determined using loop_niter_by_eval (i.e. by brute force
2249 evaluation). If we are unable to find the exit for that loop_niter_by_eval
2250 determines the number of iterations, chrec_dont_know is returned. */
2253 find_loop_niter_by_eval (struct loop *loop, edge *exit)
2256 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
2258 tree niter = NULL_TREE, aniter;
2262 /* Loops with multiple exits are expensive to handle and less important. */
2263 if (!flag_expensive_optimizations
2264 && VEC_length (edge, exits) > 1)
2265 return chrec_dont_know;
2267 FOR_EACH_VEC_ELT (edge, exits, i, ex)
2269 if (!just_once_each_iteration_p (loop, ex->src))
2272 aniter = loop_niter_by_eval (loop, ex);
2273 if (chrec_contains_undetermined (aniter))
2277 && !tree_int_cst_lt (aniter, niter))
2283 VEC_free (edge, heap, exits);
2285 return niter ? niter : chrec_dont_know;
2290 Analysis of upper bounds on number of iterations of a loop.
2294 static double_int derive_constant_upper_bound_ops (tree, tree,
2295 enum tree_code, tree);
2297 /* Returns a constant upper bound on the value of the right-hand side of
2298 an assignment statement STMT. */
2301 derive_constant_upper_bound_assign (gimple stmt)
2303 enum tree_code code = gimple_assign_rhs_code (stmt);
2304 tree op0 = gimple_assign_rhs1 (stmt);
2305 tree op1 = gimple_assign_rhs2 (stmt);
2307 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt)),
2311 /* Returns a constant upper bound on the value of expression VAL. VAL
2312 is considered to be unsigned. If its type is signed, its value must
2316 derive_constant_upper_bound (tree val)
2318 enum tree_code code;
2321 extract_ops_from_tree (val, &code, &op0, &op1);
2322 return derive_constant_upper_bound_ops (TREE_TYPE (val), op0, code, op1);
2325 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
2326 whose type is TYPE. The expression is considered to be unsigned. If
2327 its type is signed, its value must be nonnegative. */
2330 derive_constant_upper_bound_ops (tree type, tree op0,
2331 enum tree_code code, tree op1)
2334 double_int bnd, max, mmax, cst;
2337 if (INTEGRAL_TYPE_P (type))
2338 maxt = TYPE_MAX_VALUE (type);
2340 maxt = upper_bound_in_type (type, type);
2342 max = tree_to_double_int (maxt);
2347 return tree_to_double_int (op0);
2350 subtype = TREE_TYPE (op0);
2351 if (!TYPE_UNSIGNED (subtype)
2352 /* If TYPE is also signed, the fact that VAL is nonnegative implies
2353 that OP0 is nonnegative. */
2354 && TYPE_UNSIGNED (type)
2355 && !tree_expr_nonnegative_p (op0))
2357 /* If we cannot prove that the casted expression is nonnegative,
2358 we cannot establish more useful upper bound than the precision
2359 of the type gives us. */
2363 /* We now know that op0 is an nonnegative value. Try deriving an upper
2365 bnd = derive_constant_upper_bound (op0);
2367 /* If the bound does not fit in TYPE, max. value of TYPE could be
2369 if (double_int_ucmp (max, bnd) < 0)
2375 case POINTER_PLUS_EXPR:
2377 if (TREE_CODE (op1) != INTEGER_CST
2378 || !tree_expr_nonnegative_p (op0))
2381 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
2382 choose the most logical way how to treat this constant regardless
2383 of the signedness of the type. */
2384 cst = tree_to_double_int (op1);
2385 cst = double_int_sext (cst, TYPE_PRECISION (type));
2386 if (code != MINUS_EXPR)
2387 cst = double_int_neg (cst);
2389 bnd = derive_constant_upper_bound (op0);
2391 if (double_int_negative_p (cst))
2393 cst = double_int_neg (cst);
2394 /* Avoid CST == 0x80000... */
2395 if (double_int_negative_p (cst))
2398 /* OP0 + CST. We need to check that
2399 BND <= MAX (type) - CST. */
2401 mmax = double_int_sub (max, cst);
2402 if (double_int_ucmp (bnd, mmax) > 0)
2405 return double_int_add (bnd, cst);
2409 /* OP0 - CST, where CST >= 0.
2411 If TYPE is signed, we have already verified that OP0 >= 0, and we
2412 know that the result is nonnegative. This implies that
2415 If TYPE is unsigned, we must additionally know that OP0 >= CST,
2416 otherwise the operation underflows.
2419 /* This should only happen if the type is unsigned; however, for
2420 buggy programs that use overflowing signed arithmetics even with
2421 -fno-wrapv, this condition may also be true for signed values. */
2422 if (double_int_ucmp (bnd, cst) < 0)
2425 if (TYPE_UNSIGNED (type))
2427 tree tem = fold_binary (GE_EXPR, boolean_type_node, op0,
2428 double_int_to_tree (type, cst));
2429 if (!tem || integer_nonzerop (tem))
2433 bnd = double_int_sub (bnd, cst);
2438 case FLOOR_DIV_EXPR:
2439 case EXACT_DIV_EXPR:
2440 if (TREE_CODE (op1) != INTEGER_CST
2441 || tree_int_cst_sign_bit (op1))
2444 bnd = derive_constant_upper_bound (op0);
2445 return double_int_udiv (bnd, tree_to_double_int (op1), FLOOR_DIV_EXPR);
2448 if (TREE_CODE (op1) != INTEGER_CST
2449 || tree_int_cst_sign_bit (op1))
2451 return tree_to_double_int (op1);
2454 stmt = SSA_NAME_DEF_STMT (op0);
2455 if (gimple_code (stmt) != GIMPLE_ASSIGN
2456 || gimple_assign_lhs (stmt) != op0)
2458 return derive_constant_upper_bound_assign (stmt);
2465 /* Records that every statement in LOOP is executed I_BOUND times.
2466 REALISTIC is true if I_BOUND is expected to be close to the real number
2467 of iterations. UPPER is true if we are sure the loop iterates at most
2471 record_niter_bound (struct loop *loop, double_int i_bound, bool realistic,
2474 /* Update the bounds only when there is no previous estimation, or when the current
2475 estimation is smaller. */
2477 && (!loop->any_upper_bound
2478 || double_int_ucmp (i_bound, loop->nb_iterations_upper_bound) < 0))
2480 loop->any_upper_bound = true;
2481 loop->nb_iterations_upper_bound = i_bound;
2484 && (!loop->any_estimate
2485 || double_int_ucmp (i_bound, loop->nb_iterations_estimate) < 0))
2487 loop->any_estimate = true;
2488 loop->nb_iterations_estimate = i_bound;
2492 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
2493 is true if the loop is exited immediately after STMT, and this exit
2494 is taken at last when the STMT is executed BOUND + 1 times.
2495 REALISTIC is true if BOUND is expected to be close to the real number
2496 of iterations. UPPER is true if we are sure the loop iterates at most
2497 BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */
2500 record_estimate (struct loop *loop, tree bound, double_int i_bound,
2501 gimple at_stmt, bool is_exit, bool realistic, bool upper)
2506 if (dump_file && (dump_flags & TDF_DETAILS))
2508 fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : "");
2509 print_gimple_stmt (dump_file, at_stmt, 0, TDF_SLIM);
2510 fprintf (dump_file, " is %sexecuted at most ",
2511 upper ? "" : "probably ");
2512 print_generic_expr (dump_file, bound, TDF_SLIM);
2513 fprintf (dump_file, " (bounded by ");
2514 dump_double_int (dump_file, i_bound, true);
2515 fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num);
2518 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
2519 real number of iterations. */
2520 if (TREE_CODE (bound) != INTEGER_CST)
2522 if (!upper && !realistic)
2525 /* If we have a guaranteed upper bound, record it in the appropriate
2529 struct nb_iter_bound *elt = ggc_alloc_nb_iter_bound ();
2531 elt->bound = i_bound;
2532 elt->stmt = at_stmt;
2533 elt->is_exit = is_exit;
2534 elt->next = loop->bounds;
2538 /* Update the number of iteration estimates according to the bound.
2539 If at_stmt is an exit, then every statement in the loop is
2540 executed at most BOUND + 1 times. If it is not an exit, then
2541 some of the statements before it could be executed BOUND + 2
2542 times, if an exit of LOOP is before stmt. */
2543 exit = single_exit (loop);
2546 && dominated_by_p (CDI_DOMINATORS,
2547 exit->src, gimple_bb (at_stmt))))
2548 delta = double_int_one;
2550 delta = double_int_two;
2551 i_bound = double_int_add (i_bound, delta);
2553 /* If an overflow occurred, ignore the result. */
2554 if (double_int_ucmp (i_bound, delta) < 0)
2557 record_niter_bound (loop, i_bound, realistic, upper);
2560 /* Record the estimate on number of iterations of LOOP based on the fact that
2561 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
2562 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
2563 estimated number of iterations is expected to be close to the real one.
2564 UPPER is true if we are sure the induction variable does not wrap. */
2567 record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple stmt,
2568 tree low, tree high, bool realistic, bool upper)
2570 tree niter_bound, extreme, delta;
2571 tree type = TREE_TYPE (base), unsigned_type;
2574 if (TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
2577 if (dump_file && (dump_flags & TDF_DETAILS))
2579 fprintf (dump_file, "Induction variable (");
2580 print_generic_expr (dump_file, TREE_TYPE (base), TDF_SLIM);
2581 fprintf (dump_file, ") ");
2582 print_generic_expr (dump_file, base, TDF_SLIM);
2583 fprintf (dump_file, " + ");
2584 print_generic_expr (dump_file, step, TDF_SLIM);
2585 fprintf (dump_file, " * iteration does not wrap in statement ");
2586 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2587 fprintf (dump_file, " in loop %d.\n", loop->num);
2590 unsigned_type = unsigned_type_for (type);
2591 base = fold_convert (unsigned_type, base);
2592 step = fold_convert (unsigned_type, step);
2594 if (tree_int_cst_sign_bit (step))
2596 extreme = fold_convert (unsigned_type, low);
2597 if (TREE_CODE (base) != INTEGER_CST)
2598 base = fold_convert (unsigned_type, high);
2599 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
2600 step = fold_build1 (NEGATE_EXPR, unsigned_type, step);
2604 extreme = fold_convert (unsigned_type, high);
2605 if (TREE_CODE (base) != INTEGER_CST)
2606 base = fold_convert (unsigned_type, low);
2607 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
2610 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
2611 would get out of the range. */
2612 niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step);
2613 max = derive_constant_upper_bound (niter_bound);
2614 record_estimate (loop, niter_bound, max, stmt, false, realistic, upper);
2617 /* Returns true if REF is a reference to an array at the end of a dynamically
2618 allocated structure. If this is the case, the array may be allocated larger
2619 than its upper bound implies. */
2622 array_at_struct_end_p (tree ref)
2624 tree base = get_base_address (ref);
2627 /* Unless the reference is through a pointer, the size of the array matches
2629 if (!base || (!INDIRECT_REF_P (base) && TREE_CODE (base) != MEM_REF))
2632 for (;handled_component_p (ref); ref = parent)
2634 parent = TREE_OPERAND (ref, 0);
2636 if (TREE_CODE (ref) == COMPONENT_REF)
2638 /* All fields of a union are at its end. */
2639 if (TREE_CODE (TREE_TYPE (parent)) == UNION_TYPE)
2642 /* Unless the field is at the end of the struct, we are done. */
2643 field = TREE_OPERAND (ref, 1);
2644 if (DECL_CHAIN (field))
2648 /* The other options are ARRAY_REF, ARRAY_RANGE_REF, VIEW_CONVERT_EXPR.
2649 In all these cases, we might be accessing the last element, and
2650 although in practice this will probably never happen, it is legal for
2651 the indices of this last element to exceed the bounds of the array.
2652 Therefore, continue checking. */
2658 /* Determine information about number of iterations a LOOP from the index
2659 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
2660 guaranteed to be executed in every iteration of LOOP. Callback for
2671 idx_infer_loop_bounds (tree base, tree *idx, void *dta)
2673 struct ilb_data *data = (struct ilb_data *) dta;
2674 tree ev, init, step;
2675 tree low, high, type, next;
2676 bool sign, upper = data->reliable, at_end = false;
2677 struct loop *loop = data->loop;
2679 if (TREE_CODE (base) != ARRAY_REF)
2682 /* For arrays at the end of the structure, we are not guaranteed that they
2683 do not really extend over their declared size. However, for arrays of
2684 size greater than one, this is unlikely to be intended. */
2685 if (array_at_struct_end_p (base))
2691 ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx));
2692 init = initial_condition (ev);
2693 step = evolution_part_in_loop_num (ev, loop->num);
2697 || TREE_CODE (step) != INTEGER_CST
2698 || integer_zerop (step)
2699 || tree_contains_chrecs (init, NULL)
2700 || chrec_contains_symbols_defined_in_loop (init, loop->num))
2703 low = array_ref_low_bound (base);
2704 high = array_ref_up_bound (base);
2706 /* The case of nonconstant bounds could be handled, but it would be
2708 if (TREE_CODE (low) != INTEGER_CST
2710 || TREE_CODE (high) != INTEGER_CST)
2712 sign = tree_int_cst_sign_bit (step);
2713 type = TREE_TYPE (step);
2715 /* The array of length 1 at the end of a structure most likely extends
2716 beyond its bounds. */
2718 && operand_equal_p (low, high, 0))
2721 /* In case the relevant bound of the array does not fit in type, or
2722 it does, but bound + step (in type) still belongs into the range of the
2723 array, the index may wrap and still stay within the range of the array
2724 (consider e.g. if the array is indexed by the full range of
2727 To make things simpler, we require both bounds to fit into type, although
2728 there are cases where this would not be strictly necessary. */
2729 if (!int_fits_type_p (high, type)
2730 || !int_fits_type_p (low, type))
2732 low = fold_convert (type, low);
2733 high = fold_convert (type, high);
2736 next = fold_binary (PLUS_EXPR, type, low, step);
2738 next = fold_binary (PLUS_EXPR, type, high, step);
2740 if (tree_int_cst_compare (low, next) <= 0
2741 && tree_int_cst_compare (next, high) <= 0)
2744 record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true, upper);
2748 /* Determine information about number of iterations a LOOP from the bounds
2749 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
2750 STMT is guaranteed to be executed in every iteration of LOOP.*/
2753 infer_loop_bounds_from_ref (struct loop *loop, gimple stmt, tree ref,
2756 struct ilb_data data;
2760 data.reliable = reliable;
2761 for_each_index (&ref, idx_infer_loop_bounds, &data);
2764 /* Determine information about number of iterations of a LOOP from the way
2765 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
2766 executed in every iteration of LOOP. */
2769 infer_loop_bounds_from_array (struct loop *loop, gimple stmt, bool reliable)
2771 if (is_gimple_assign (stmt))
2773 tree op0 = gimple_assign_lhs (stmt);
2774 tree op1 = gimple_assign_rhs1 (stmt);
2776 /* For each memory access, analyze its access function
2777 and record a bound on the loop iteration domain. */
2778 if (REFERENCE_CLASS_P (op0))
2779 infer_loop_bounds_from_ref (loop, stmt, op0, reliable);
2781 if (REFERENCE_CLASS_P (op1))
2782 infer_loop_bounds_from_ref (loop, stmt, op1, reliable);
2784 else if (is_gimple_call (stmt))
2787 unsigned i, n = gimple_call_num_args (stmt);
2789 lhs = gimple_call_lhs (stmt);
2790 if (lhs && REFERENCE_CLASS_P (lhs))
2791 infer_loop_bounds_from_ref (loop, stmt, lhs, reliable);
2793 for (i = 0; i < n; i++)
2795 arg = gimple_call_arg (stmt, i);
2796 if (REFERENCE_CLASS_P (arg))
2797 infer_loop_bounds_from_ref (loop, stmt, arg, reliable);
2802 /* Determine information about number of iterations of a LOOP from the fact
2803 that signed arithmetics in STMT does not overflow. */
2806 infer_loop_bounds_from_signedness (struct loop *loop, gimple stmt)
2808 tree def, base, step, scev, type, low, high;
2810 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2813 def = gimple_assign_lhs (stmt);
2815 if (TREE_CODE (def) != SSA_NAME)
2818 type = TREE_TYPE (def);
2819 if (!INTEGRAL_TYPE_P (type)
2820 || !TYPE_OVERFLOW_UNDEFINED (type))
2823 scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
2824 if (chrec_contains_undetermined (scev))
2827 base = initial_condition_in_loop_num (scev, loop->num);
2828 step = evolution_part_in_loop_num (scev, loop->num);
2831 || TREE_CODE (step) != INTEGER_CST
2832 || tree_contains_chrecs (base, NULL)
2833 || chrec_contains_symbols_defined_in_loop (base, loop->num))
2836 low = lower_bound_in_type (type, type);
2837 high = upper_bound_in_type (type, type);
2839 record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
2842 /* The following analyzers are extracting informations on the bounds
2843 of LOOP from the following undefined behaviors:
2845 - data references should not access elements over the statically
2848 - signed variables should not overflow when flag_wrapv is not set.
2852 infer_loop_bounds_from_undefined (struct loop *loop)
2856 gimple_stmt_iterator bsi;
2860 bbs = get_loop_body (loop);
2862 for (i = 0; i < loop->num_nodes; i++)
2866 /* If BB is not executed in each iteration of the loop, we cannot
2867 use the operations in it to infer reliable upper bound on the
2868 # of iterations of the loop. However, we can use it as a guess. */
2869 reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb);
2871 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
2873 gimple stmt = gsi_stmt (bsi);
2875 infer_loop_bounds_from_array (loop, stmt, reliable);
2878 infer_loop_bounds_from_signedness (loop, stmt);
2886 /* Converts VAL to double_int. */
2889 gcov_type_to_double_int (gcov_type val)
2893 ret.low = (unsigned HOST_WIDE_INT) val;
2894 /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by
2895 the size of type. */
2896 val >>= HOST_BITS_PER_WIDE_INT - 1;
2898 ret.high = (unsigned HOST_WIDE_INT) val;
2903 /* Records estimates on numbers of iterations of LOOP. */
2906 estimate_numbers_of_iterations_loop (struct loop *loop)
2908 VEC (edge, heap) *exits;
2911 struct tree_niter_desc niter_desc;
2915 /* Give up if we already have tried to compute an estimation. */
2916 if (loop->estimate_state != EST_NOT_COMPUTED)
2918 loop->estimate_state = EST_AVAILABLE;
2919 loop->any_upper_bound = false;
2920 loop->any_estimate = false;
2922 exits = get_loop_exit_edges (loop);
2923 FOR_EACH_VEC_ELT (edge, exits, i, ex)
2925 if (!number_of_iterations_exit (loop, ex, &niter_desc, false))
2928 niter = niter_desc.niter;
2929 type = TREE_TYPE (niter);
2930 if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST)
2931 niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
2932 build_int_cst (type, 0),
2934 record_estimate (loop, niter, niter_desc.max,
2935 last_stmt (ex->src),
2938 VEC_free (edge, heap, exits);
2940 infer_loop_bounds_from_undefined (loop);
2942 /* If we have a measured profile, use it to estimate the number of
2944 if (loop->header->count != 0)
2946 gcov_type nit = expected_loop_iterations_unbounded (loop) + 1;
2947 bound = gcov_type_to_double_int (nit);
2948 record_niter_bound (loop, bound, true, false);
2951 /* If an upper bound is smaller than the realistic estimate of the
2952 number of iterations, use the upper bound instead. */
2953 if (loop->any_upper_bound
2954 && loop->any_estimate
2955 && double_int_ucmp (loop->nb_iterations_upper_bound,
2956 loop->nb_iterations_estimate) < 0)
2957 loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
2960 /* Records estimates on numbers of iterations of loops. */
2963 estimate_numbers_of_iterations (void)
2968 /* We don't want to issue signed overflow warnings while getting
2969 loop iteration estimates. */
2970 fold_defer_overflow_warnings ();
2972 FOR_EACH_LOOP (li, loop, 0)
2974 estimate_numbers_of_iterations_loop (loop);
2977 fold_undefer_and_ignore_overflow_warnings ();
2980 /* Returns true if statement S1 dominates statement S2. */
2983 stmt_dominates_stmt_p (gimple s1, gimple s2)
2985 basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
2993 gimple_stmt_iterator bsi;
2995 if (gimple_code (s2) == GIMPLE_PHI)
2998 if (gimple_code (s1) == GIMPLE_PHI)
3001 for (bsi = gsi_start_bb (bb1); gsi_stmt (bsi) != s2; gsi_next (&bsi))
3002 if (gsi_stmt (bsi) == s1)
3008 return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
3011 /* Returns true when we can prove that the number of executions of
3012 STMT in the loop is at most NITER, according to the bound on
3013 the number of executions of the statement NITER_BOUND->stmt recorded in
3014 NITER_BOUND. If STMT is NULL, we must prove this bound for all
3015 statements in the loop. */
3018 n_of_executions_at_most (gimple stmt,
3019 struct nb_iter_bound *niter_bound,
3022 double_int bound = niter_bound->bound;
3023 tree nit_type = TREE_TYPE (niter), e;
3026 gcc_assert (TYPE_UNSIGNED (nit_type));
3028 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
3029 the number of iterations is small. */
3030 if (!double_int_fits_to_tree_p (nit_type, bound))
3033 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3034 times. This means that:
3036 -- if NITER_BOUND->is_exit is true, then everything before
3037 NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3038 times, and everything after it at most NITER_BOUND->bound times.
3040 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
3041 is executed, then NITER_BOUND->stmt is executed as well in the same
3042 iteration (we conclude that if both statements belong to the same
3043 basic block, or if STMT is after NITER_BOUND->stmt), then STMT
3044 is executed at most NITER_BOUND->bound + 1 times. Otherwise STMT is
3045 executed at most NITER_BOUND->bound + 2 times. */
3047 if (niter_bound->is_exit)
3050 && stmt != niter_bound->stmt
3051 && stmt_dominates_stmt_p (niter_bound->stmt, stmt))
3059 || (gimple_bb (stmt) != gimple_bb (niter_bound->stmt)
3060 && !stmt_dominates_stmt_p (niter_bound->stmt, stmt)))
3062 bound = double_int_add (bound, double_int_one);
3063 if (double_int_zero_p (bound)
3064 || !double_int_fits_to_tree_p (nit_type, bound))
3070 e = fold_binary (cmp, boolean_type_node,
3071 niter, double_int_to_tree (nit_type, bound));
3072 return e && integer_nonzerop (e);
3075 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
3078 nowrap_type_p (tree type)
3080 if (INTEGRAL_TYPE_P (type)
3081 && TYPE_OVERFLOW_UNDEFINED (type))
3084 if (POINTER_TYPE_P (type))
3090 /* Return false only when the induction variable BASE + STEP * I is
3091 known to not overflow: i.e. when the number of iterations is small
3092 enough with respect to the step and initial condition in order to
3093 keep the evolution confined in TYPEs bounds. Return true when the
3094 iv is known to overflow or when the property is not computable.
3096 USE_OVERFLOW_SEMANTICS is true if this function should assume that
3097 the rules for overflow of the given language apply (e.g., that signed
3098 arithmetics in C does not overflow). */
3101 scev_probably_wraps_p (tree base, tree step,
3102 gimple at_stmt, struct loop *loop,
3103 bool use_overflow_semantics)
3105 struct nb_iter_bound *bound;
3106 tree delta, step_abs;
3107 tree unsigned_type, valid_niter;
3108 tree type = TREE_TYPE (step);
3110 /* FIXME: We really need something like
3111 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
3113 We used to test for the following situation that frequently appears
3114 during address arithmetics:
3116 D.1621_13 = (long unsigned intD.4) D.1620_12;
3117 D.1622_14 = D.1621_13 * 8;
3118 D.1623_15 = (doubleD.29 *) D.1622_14;
3120 And derived that the sequence corresponding to D_14
3121 can be proved to not wrap because it is used for computing a
3122 memory access; however, this is not really the case -- for example,
3123 if D_12 = (unsigned char) [254,+,1], then D_14 has values
3124 2032, 2040, 0, 8, ..., but the code is still legal. */
3126 if (chrec_contains_undetermined (base)
3127 || chrec_contains_undetermined (step))
3130 if (integer_zerop (step))
3133 /* If we can use the fact that signed and pointer arithmetics does not
3134 wrap, we are done. */
3135 if (use_overflow_semantics && nowrap_type_p (TREE_TYPE (base)))
3138 /* To be able to use estimates on number of iterations of the loop,
3139 we must have an upper bound on the absolute value of the step. */
3140 if (TREE_CODE (step) != INTEGER_CST)
3143 /* Don't issue signed overflow warnings. */
3144 fold_defer_overflow_warnings ();
3146 /* Otherwise, compute the number of iterations before we reach the
3147 bound of the type, and verify that the loop is exited before this
3149 unsigned_type = unsigned_type_for (type);
3150 base = fold_convert (unsigned_type, base);
3152 if (tree_int_cst_sign_bit (step))
3154 tree extreme = fold_convert (unsigned_type,
3155 lower_bound_in_type (type, type));
3156 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
3157 step_abs = fold_build1 (NEGATE_EXPR, unsigned_type,
3158 fold_convert (unsigned_type, step));
3162 tree extreme = fold_convert (unsigned_type,
3163 upper_bound_in_type (type, type));
3164 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
3165 step_abs = fold_convert (unsigned_type, step);
3168 valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
3170 estimate_numbers_of_iterations_loop (loop);
3171 for (bound = loop->bounds; bound; bound = bound->next)
3173 if (n_of_executions_at_most (at_stmt, bound, valid_niter))
3175 fold_undefer_and_ignore_overflow_warnings ();
3180 fold_undefer_and_ignore_overflow_warnings ();
3182 /* At this point we still don't have a proof that the iv does not
3183 overflow: give up. */
3187 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
3190 free_numbers_of_iterations_estimates_loop (struct loop *loop)
3192 struct nb_iter_bound *bound, *next;
3194 loop->nb_iterations = NULL;
3195 loop->estimate_state = EST_NOT_COMPUTED;
3196 for (bound = loop->bounds; bound; bound = next)
3202 loop->bounds = NULL;
3205 /* Frees the information on upper bounds on numbers of iterations of loops. */
3208 free_numbers_of_iterations_estimates (void)
3213 FOR_EACH_LOOP (li, loop, 0)
3215 free_numbers_of_iterations_estimates_loop (loop);
3219 /* Substitute value VAL for ssa name NAME inside expressions held
3223 substitute_in_loop_info (struct loop *loop, tree name, tree val)
3225 loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);