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"
43 #include "tree-inline.h"
46 #define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
48 /* The maximum number of dominator BBs we search for conditions
49 of loop header copies we use for simplifying a conditional
51 #define MAX_DOMINATORS_TO_WALK 8
55 Analysis of number of iterations of an affine exit test.
59 /* Bounds on some value, BELOW <= X <= UP. */
67 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */
70 split_to_var_and_offset (tree expr, tree *var, mpz_t offset)
72 tree type = TREE_TYPE (expr);
78 mpz_set_ui (offset, 0);
80 switch (TREE_CODE (expr))
87 case POINTER_PLUS_EXPR:
88 op0 = TREE_OPERAND (expr, 0);
89 op1 = TREE_OPERAND (expr, 1);
91 if (TREE_CODE (op1) != INTEGER_CST)
95 /* Always sign extend the offset. */
96 off = tree_to_double_int (op1);
98 off = double_int_neg (off);
99 off = double_int_sext (off, TYPE_PRECISION (type));
100 mpz_set_double_int (offset, off, false);
104 *var = build_int_cst_type (type, 0);
105 off = tree_to_double_int (expr);
106 mpz_set_double_int (offset, off, TYPE_UNSIGNED (type));
114 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
115 in TYPE to MIN and MAX. */
118 determine_value_range (tree type, tree var, mpz_t off,
119 mpz_t min, mpz_t max)
121 /* If the expression is a constant, we know its value exactly. */
122 if (integer_zerop (var))
129 /* If the computation may wrap, we know nothing about the value, except for
130 the range of the type. */
131 get_type_static_bounds (type, min, max);
132 if (!nowrap_type_p (type))
135 /* Since the addition of OFF does not wrap, if OFF is positive, then we may
136 add it to MIN, otherwise to MAX. */
137 if (mpz_sgn (off) < 0)
138 mpz_add (max, max, off);
140 mpz_add (min, min, off);
143 /* Stores the bounds on the difference of the values of the expressions
144 (var + X) and (var + Y), computed in TYPE, to BNDS. */
147 bound_difference_of_offsetted_base (tree type, mpz_t x, mpz_t y,
150 int rel = mpz_cmp (x, y);
151 bool may_wrap = !nowrap_type_p (type);
154 /* If X == Y, then the expressions are always equal.
155 If X > Y, there are the following possibilities:
156 a) neither of var + X and var + Y overflow or underflow, or both of
157 them do. Then their difference is X - Y.
158 b) var + X overflows, and var + Y does not. Then the values of the
159 expressions are var + X - M and var + Y, where M is the range of
160 the type, and their difference is X - Y - M.
161 c) var + Y underflows and var + X does not. Their difference again
163 Therefore, if the arithmetics in type does not overflow, then the
164 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
165 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
166 (X - Y, X - Y + M). */
170 mpz_set_ui (bnds->below, 0);
171 mpz_set_ui (bnds->up, 0);
176 mpz_set_double_int (m, double_int_mask (TYPE_PRECISION (type)), true);
177 mpz_add_ui (m, m, 1);
178 mpz_sub (bnds->up, x, y);
179 mpz_set (bnds->below, bnds->up);
184 mpz_sub (bnds->below, bnds->below, m);
186 mpz_add (bnds->up, bnds->up, m);
192 /* From condition C0 CMP C1 derives information regarding the
193 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
194 and stores it to BNDS. */
197 refine_bounds_using_guard (tree type, tree varx, mpz_t offx,
198 tree vary, mpz_t offy,
199 tree c0, enum tree_code cmp, tree c1,
202 tree varc0, varc1, tmp, ctype;
203 mpz_t offc0, offc1, loffx, loffy, bnd;
205 bool no_wrap = nowrap_type_p (type);
214 STRIP_SIGN_NOPS (c0);
215 STRIP_SIGN_NOPS (c1);
216 ctype = TREE_TYPE (c0);
217 if (!useless_type_conversion_p (ctype, type))
223 /* We could derive quite precise information from EQ_EXPR, however, such
224 a guard is unlikely to appear, so we do not bother with handling
229 /* NE_EXPR comparisons do not contain much of useful information, except for
230 special case of comparing with the bounds of the type. */
231 if (TREE_CODE (c1) != INTEGER_CST
232 || !INTEGRAL_TYPE_P (type))
235 /* Ensure that the condition speaks about an expression in the same type
237 ctype = TREE_TYPE (c0);
238 if (TYPE_PRECISION (ctype) != TYPE_PRECISION (type))
240 c0 = fold_convert (type, c0);
241 c1 = fold_convert (type, c1);
243 if (TYPE_MIN_VALUE (type)
244 && operand_equal_p (c1, TYPE_MIN_VALUE (type), 0))
249 if (TYPE_MAX_VALUE (type)
250 && operand_equal_p (c1, TYPE_MAX_VALUE (type), 0))
263 split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0);
264 split_to_var_and_offset (expand_simple_operations (c1), &varc1, offc1);
266 /* We are only interested in comparisons of expressions based on VARX and
267 VARY. TODO -- we might also be able to derive some bounds from
268 expressions containing just one of the variables. */
270 if (operand_equal_p (varx, varc1, 0))
272 tmp = varc0; varc0 = varc1; varc1 = tmp;
273 mpz_swap (offc0, offc1);
274 cmp = swap_tree_comparison (cmp);
277 if (!operand_equal_p (varx, varc0, 0)
278 || !operand_equal_p (vary, varc1, 0))
281 mpz_init_set (loffx, offx);
282 mpz_init_set (loffy, offy);
284 if (cmp == GT_EXPR || cmp == GE_EXPR)
286 tmp = varx; varx = vary; vary = tmp;
287 mpz_swap (offc0, offc1);
288 mpz_swap (loffx, loffy);
289 cmp = swap_tree_comparison (cmp);
293 /* If there is no overflow, the condition implies that
295 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
297 The overflows and underflows may complicate things a bit; each
298 overflow decreases the appropriate offset by M, and underflow
299 increases it by M. The above inequality would not necessarily be
302 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
303 VARX + OFFC0 overflows, but VARX + OFFX does not.
304 This may only happen if OFFX < OFFC0.
305 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
306 VARY + OFFC1 underflows and VARY + OFFY does not.
307 This may only happen if OFFY > OFFC1. */
316 x_ok = (integer_zerop (varx)
317 || mpz_cmp (loffx, offc0) >= 0);
318 y_ok = (integer_zerop (vary)
319 || mpz_cmp (loffy, offc1) <= 0);
325 mpz_sub (bnd, loffx, loffy);
326 mpz_add (bnd, bnd, offc1);
327 mpz_sub (bnd, bnd, offc0);
330 mpz_sub_ui (bnd, bnd, 1);
335 if (mpz_cmp (bnds->below, bnd) < 0)
336 mpz_set (bnds->below, bnd);
340 if (mpz_cmp (bnd, bnds->up) < 0)
341 mpz_set (bnds->up, bnd);
353 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
354 The subtraction is considered to be performed in arbitrary precision,
357 We do not attempt to be too clever regarding the value ranges of X and
358 Y; most of the time, they are just integers or ssa names offsetted by
359 integer. However, we try to use the information contained in the
360 comparisons before the loop (usually created by loop header copying). */
363 bound_difference (struct loop *loop, tree x, tree y, bounds *bnds)
365 tree type = TREE_TYPE (x);
368 mpz_t minx, maxx, miny, maxy;
376 /* Get rid of unnecessary casts, but preserve the value of
381 mpz_init (bnds->below);
385 split_to_var_and_offset (x, &varx, offx);
386 split_to_var_and_offset (y, &vary, offy);
388 if (!integer_zerop (varx)
389 && operand_equal_p (varx, vary, 0))
391 /* Special case VARX == VARY -- we just need to compare the
392 offsets. The matters are a bit more complicated in the
393 case addition of offsets may wrap. */
394 bound_difference_of_offsetted_base (type, offx, offy, bnds);
398 /* Otherwise, use the value ranges to determine the initial
399 estimates on below and up. */
404 determine_value_range (type, varx, offx, minx, maxx);
405 determine_value_range (type, vary, offy, miny, maxy);
407 mpz_sub (bnds->below, minx, maxy);
408 mpz_sub (bnds->up, maxx, miny);
415 /* If both X and Y are constants, we cannot get any more precise. */
416 if (integer_zerop (varx) && integer_zerop (vary))
419 /* Now walk the dominators of the loop header and use the entry
420 guards to refine the estimates. */
421 for (bb = loop->header;
422 bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK;
423 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
425 if (!single_pred_p (bb))
427 e = single_pred_edge (bb);
429 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
432 cond = last_stmt (e->src);
433 c0 = gimple_cond_lhs (cond);
434 cmp = gimple_cond_code (cond);
435 c1 = gimple_cond_rhs (cond);
437 if (e->flags & EDGE_FALSE_VALUE)
438 cmp = invert_tree_comparison (cmp, false);
440 refine_bounds_using_guard (type, varx, offx, vary, offy,
450 /* Update the bounds in BNDS that restrict the value of X to the bounds
451 that restrict the value of X + DELTA. X can be obtained as a
452 difference of two values in TYPE. */
455 bounds_add (bounds *bnds, double_int delta, tree type)
460 mpz_set_double_int (mdelta, delta, false);
463 mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true);
465 mpz_add (bnds->up, bnds->up, mdelta);
466 mpz_add (bnds->below, bnds->below, mdelta);
468 if (mpz_cmp (bnds->up, max) > 0)
469 mpz_set (bnds->up, max);
472 if (mpz_cmp (bnds->below, max) < 0)
473 mpz_set (bnds->below, max);
479 /* Update the bounds in BNDS that restrict the value of X to the bounds
480 that restrict the value of -X. */
483 bounds_negate (bounds *bnds)
487 mpz_init_set (tmp, bnds->up);
488 mpz_neg (bnds->up, bnds->below);
489 mpz_neg (bnds->below, tmp);
493 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
496 inverse (tree x, tree mask)
498 tree type = TREE_TYPE (x);
500 unsigned ctr = tree_floor_log2 (mask);
502 if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT)
504 unsigned HOST_WIDE_INT ix;
505 unsigned HOST_WIDE_INT imask;
506 unsigned HOST_WIDE_INT irslt = 1;
508 gcc_assert (cst_and_fits_in_hwi (x));
509 gcc_assert (cst_and_fits_in_hwi (mask));
511 ix = int_cst_value (x);
512 imask = int_cst_value (mask);
521 rslt = build_int_cst_type (type, irslt);
525 rslt = build_int_cst (type, 1);
528 rslt = int_const_binop (MULT_EXPR, rslt, x, 0);
529 x = int_const_binop (MULT_EXPR, x, x, 0);
531 rslt = int_const_binop (BIT_AND_EXPR, rslt, mask, 0);
537 /* Derives the upper bound BND on the number of executions of loop with exit
538 condition S * i <> C, assuming that this exit is taken. If
539 NO_OVERFLOW is true, then the control variable of the loop does not
540 overflow. If NO_OVERFLOW is true or BNDS.below >= 0, then BNDS.up
541 contains the upper bound on the value of C. */
544 number_of_iterations_ne_max (mpz_t bnd, bool no_overflow, tree c, tree s,
550 /* If the control variable does not overflow, the number of iterations is
551 at most c / s. Otherwise it is at most the period of the control
553 if (!no_overflow && !multiple_of_p (TREE_TYPE (c), c, s))
555 max = double_int_mask (TYPE_PRECISION (TREE_TYPE (c))
556 - tree_low_cst (num_ending_zeros (s), 1));
557 mpz_set_double_int (bnd, max, true);
561 /* Determine the upper bound on C. */
562 if (no_overflow || mpz_sgn (bnds->below) >= 0)
563 mpz_set (bnd, bnds->up);
564 else if (TREE_CODE (c) == INTEGER_CST)
565 mpz_set_double_int (bnd, tree_to_double_int (c), true);
567 mpz_set_double_int (bnd, double_int_mask (TYPE_PRECISION (TREE_TYPE (c))),
571 mpz_set_double_int (d, tree_to_double_int (s), true);
572 mpz_fdiv_q (bnd, bnd, d);
576 /* Determines number of iterations of loop whose ending condition
577 is IV <> FINAL. TYPE is the type of the iv. The number of
578 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
579 we know that the exit must be taken eventually, i.e., that the IV
580 ever reaches the value FINAL (we derived this earlier, and possibly set
581 NITER->assumptions to make sure this is the case). BNDS contains the
582 bounds on the difference FINAL - IV->base. */
585 number_of_iterations_ne (tree type, affine_iv *iv, tree final,
586 struct tree_niter_desc *niter, bool exit_must_be_taken,
589 tree niter_type = unsigned_type_for (type);
590 tree s, c, d, bits, assumption, tmp, bound;
593 niter->control = *iv;
594 niter->bound = final;
595 niter->cmp = NE_EXPR;
597 /* Rearrange the terms so that we get inequality S * i <> C, with S
598 positive. Also cast everything to the unsigned type. If IV does
599 not overflow, BNDS bounds the value of C. Also, this is the
600 case if the computation |FINAL - IV->base| does not overflow, i.e.,
601 if BNDS->below in the result is nonnegative. */
602 if (tree_int_cst_sign_bit (iv->step))
604 s = fold_convert (niter_type,
605 fold_build1 (NEGATE_EXPR, type, iv->step));
606 c = fold_build2 (MINUS_EXPR, niter_type,
607 fold_convert (niter_type, iv->base),
608 fold_convert (niter_type, final));
609 bounds_negate (bnds);
613 s = fold_convert (niter_type, iv->step);
614 c = fold_build2 (MINUS_EXPR, niter_type,
615 fold_convert (niter_type, final),
616 fold_convert (niter_type, iv->base));
620 number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds);
621 niter->max = mpz_get_double_int (niter_type, max, false);
624 /* First the trivial cases -- when the step is 1. */
625 if (integer_onep (s))
631 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
632 is infinite. Otherwise, the number of iterations is
633 (inverse(s/d) * (c/d)) mod (size of mode/d). */
634 bits = num_ending_zeros (s);
635 bound = build_low_bits_mask (niter_type,
636 (TYPE_PRECISION (niter_type)
637 - tree_low_cst (bits, 1)));
639 d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
640 build_int_cst (niter_type, 1), bits);
641 s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
643 if (!exit_must_be_taken)
645 /* If we cannot assume that the exit is taken eventually, record the
646 assumptions for divisibility of c. */
647 assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d);
648 assumption = fold_build2 (EQ_EXPR, boolean_type_node,
649 assumption, build_int_cst (niter_type, 0));
650 if (!integer_nonzerop (assumption))
651 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
652 niter->assumptions, assumption);
655 c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d);
656 tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound));
657 niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound);
661 /* Checks whether we can determine the final value of the control variable
662 of the loop with ending condition IV0 < IV1 (computed in TYPE).
663 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
664 of the step. The assumptions necessary to ensure that the computation
665 of the final value does not overflow are recorded in NITER. If we
666 find the final value, we adjust DELTA and return TRUE. Otherwise
667 we return false. BNDS bounds the value of IV1->base - IV0->base,
668 and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
669 true if we know that the exit must be taken eventually. */
672 number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1,
673 struct tree_niter_desc *niter,
674 tree *delta, tree step,
675 bool exit_must_be_taken, bounds *bnds)
677 tree niter_type = TREE_TYPE (step);
678 tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step);
681 tree assumption = boolean_true_node, bound, noloop;
682 bool ret = false, fv_comp_no_overflow;
684 if (POINTER_TYPE_P (type))
687 if (TREE_CODE (mod) != INTEGER_CST)
689 if (integer_nonzerop (mod))
690 mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
691 tmod = fold_convert (type1, mod);
694 mpz_set_double_int (mmod, tree_to_double_int (mod), true);
695 mpz_neg (mmod, mmod);
697 /* If the induction variable does not overflow and the exit is taken,
698 then the computation of the final value does not overflow. This is
699 also obviously the case if the new final value is equal to the
700 current one. Finally, we postulate this for pointer type variables,
701 as the code cannot rely on the object to that the pointer points being
702 placed at the end of the address space (and more pragmatically,
703 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
704 if (integer_zerop (mod) || POINTER_TYPE_P (type))
705 fv_comp_no_overflow = true;
706 else if (!exit_must_be_taken)
707 fv_comp_no_overflow = false;
709 fv_comp_no_overflow =
710 (iv0->no_overflow && integer_nonzerop (iv0->step))
711 || (iv1->no_overflow && integer_nonzerop (iv1->step));
713 if (integer_nonzerop (iv0->step))
715 /* The final value of the iv is iv1->base + MOD, assuming that this
716 computation does not overflow, and that
717 iv0->base <= iv1->base + MOD. */
718 if (!fv_comp_no_overflow)
720 bound = fold_build2 (MINUS_EXPR, type1,
721 TYPE_MAX_VALUE (type1), tmod);
722 assumption = fold_build2 (LE_EXPR, boolean_type_node,
724 if (integer_zerop (assumption))
727 if (mpz_cmp (mmod, bnds->below) < 0)
728 noloop = boolean_false_node;
729 else if (POINTER_TYPE_P (type))
730 noloop = fold_build2 (GT_EXPR, boolean_type_node,
732 fold_build2 (POINTER_PLUS_EXPR, type,
735 noloop = fold_build2 (GT_EXPR, boolean_type_node,
737 fold_build2 (PLUS_EXPR, type1,
742 /* The final value of the iv is iv0->base - MOD, assuming that this
743 computation does not overflow, and that
744 iv0->base - MOD <= iv1->base. */
745 if (!fv_comp_no_overflow)
747 bound = fold_build2 (PLUS_EXPR, type1,
748 TYPE_MIN_VALUE (type1), tmod);
749 assumption = fold_build2 (GE_EXPR, boolean_type_node,
751 if (integer_zerop (assumption))
754 if (mpz_cmp (mmod, bnds->below) < 0)
755 noloop = boolean_false_node;
756 else if (POINTER_TYPE_P (type))
757 noloop = fold_build2 (GT_EXPR, boolean_type_node,
758 fold_build2 (POINTER_PLUS_EXPR, type,
760 fold_build1 (NEGATE_EXPR,
764 noloop = fold_build2 (GT_EXPR, boolean_type_node,
765 fold_build2 (MINUS_EXPR, type1,
770 if (!integer_nonzerop (assumption))
771 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
774 if (!integer_zerop (noloop))
775 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
778 bounds_add (bnds, tree_to_double_int (mod), type);
779 *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod);
787 /* Add assertions to NITER that ensure that the control variable of the loop
788 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
789 are TYPE. Returns false if we can prove that there is an overflow, true
790 otherwise. STEP is the absolute value of the step. */
793 assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
794 struct tree_niter_desc *niter, tree step)
796 tree bound, d, assumption, diff;
797 tree niter_type = TREE_TYPE (step);
799 if (integer_nonzerop (iv0->step))
801 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
802 if (iv0->no_overflow)
805 /* If iv0->base is a constant, we can determine the last value before
806 overflow precisely; otherwise we conservatively assume
809 if (TREE_CODE (iv0->base) == INTEGER_CST)
811 d = fold_build2 (MINUS_EXPR, niter_type,
812 fold_convert (niter_type, TYPE_MAX_VALUE (type)),
813 fold_convert (niter_type, iv0->base));
814 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
817 diff = fold_build2 (MINUS_EXPR, niter_type, step,
818 build_int_cst (niter_type, 1));
819 bound = fold_build2 (MINUS_EXPR, type,
820 TYPE_MAX_VALUE (type), fold_convert (type, diff));
821 assumption = fold_build2 (LE_EXPR, boolean_type_node,
826 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
827 if (iv1->no_overflow)
830 if (TREE_CODE (iv1->base) == INTEGER_CST)
832 d = fold_build2 (MINUS_EXPR, niter_type,
833 fold_convert (niter_type, iv1->base),
834 fold_convert (niter_type, TYPE_MIN_VALUE (type)));
835 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
838 diff = fold_build2 (MINUS_EXPR, niter_type, step,
839 build_int_cst (niter_type, 1));
840 bound = fold_build2 (PLUS_EXPR, type,
841 TYPE_MIN_VALUE (type), fold_convert (type, diff));
842 assumption = fold_build2 (GE_EXPR, boolean_type_node,
846 if (integer_zerop (assumption))
848 if (!integer_nonzerop (assumption))
849 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
850 niter->assumptions, assumption);
852 iv0->no_overflow = true;
853 iv1->no_overflow = true;
857 /* Add an assumption to NITER that a loop whose ending condition
858 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
859 bounds the value of IV1->base - IV0->base. */
862 assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
863 struct tree_niter_desc *niter, bounds *bnds)
865 tree assumption = boolean_true_node, bound, diff;
866 tree mbz, mbzl, mbzr, type1;
867 bool rolls_p, no_overflow_p;
871 /* We are going to compute the number of iterations as
872 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
873 variant of TYPE. This formula only works if
875 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
877 (where MAX is the maximum value of the unsigned variant of TYPE, and
878 the computations in this formula are performed in full precision
881 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
882 we have a condition of form iv0->base - step < iv1->base before the loop,
883 and for loops iv0->base < iv1->base - step * i the condition
884 iv0->base < iv1->base + step, due to loop header copying, which enable us
885 to prove the lower bound.
887 The upper bound is more complicated. Unless the expressions for initial
888 and final value themselves contain enough information, we usually cannot
889 derive it from the context. */
891 /* First check whether the answer does not follow from the bounds we gathered
893 if (integer_nonzerop (iv0->step))
894 dstep = tree_to_double_int (iv0->step);
897 dstep = double_int_sext (tree_to_double_int (iv1->step),
898 TYPE_PRECISION (type));
899 dstep = double_int_neg (dstep);
903 mpz_set_double_int (mstep, dstep, true);
904 mpz_neg (mstep, mstep);
905 mpz_add_ui (mstep, mstep, 1);
907 rolls_p = mpz_cmp (mstep, bnds->below) <= 0;
910 mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true);
911 mpz_add (max, max, mstep);
912 no_overflow_p = (mpz_cmp (bnds->up, max) <= 0
913 /* For pointers, only values lying inside a single object
914 can be compared or manipulated by pointer arithmetics.
915 Gcc in general does not allow or handle objects larger
916 than half of the address space, hence the upper bound
917 is satisfied for pointers. */
918 || POINTER_TYPE_P (type));
922 if (rolls_p && no_overflow_p)
926 if (POINTER_TYPE_P (type))
929 /* Now the hard part; we must formulate the assumption(s) as expressions, and
930 we must be careful not to introduce overflow. */
932 if (integer_nonzerop (iv0->step))
934 diff = fold_build2 (MINUS_EXPR, type1,
935 iv0->step, build_int_cst (type1, 1));
937 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
938 0 address never belongs to any object, we can assume this for
940 if (!POINTER_TYPE_P (type))
942 bound = fold_build2 (PLUS_EXPR, type1,
943 TYPE_MIN_VALUE (type), diff);
944 assumption = fold_build2 (GE_EXPR, boolean_type_node,
948 /* And then we can compute iv0->base - diff, and compare it with
950 mbzl = fold_build2 (MINUS_EXPR, type1,
951 fold_convert (type1, iv0->base), diff);
952 mbzr = fold_convert (type1, iv1->base);
956 diff = fold_build2 (PLUS_EXPR, type1,
957 iv1->step, build_int_cst (type1, 1));
959 if (!POINTER_TYPE_P (type))
961 bound = fold_build2 (PLUS_EXPR, type1,
962 TYPE_MAX_VALUE (type), diff);
963 assumption = fold_build2 (LE_EXPR, boolean_type_node,
967 mbzl = fold_convert (type1, iv0->base);
968 mbzr = fold_build2 (MINUS_EXPR, type1,
969 fold_convert (type1, iv1->base), diff);
972 if (!integer_nonzerop (assumption))
973 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
974 niter->assumptions, assumption);
977 mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr);
978 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
979 niter->may_be_zero, mbz);
983 /* Determines number of iterations of loop whose ending condition
984 is IV0 < IV1. TYPE is the type of the iv. The number of
985 iterations is stored to NITER. BNDS bounds the difference
986 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
987 that the exit must be taken eventually. */
990 number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
991 struct tree_niter_desc *niter,
992 bool exit_must_be_taken, bounds *bnds)
994 tree niter_type = unsigned_type_for (type);
998 if (integer_nonzerop (iv0->step))
1000 niter->control = *iv0;
1001 niter->cmp = LT_EXPR;
1002 niter->bound = iv1->base;
1006 niter->control = *iv1;
1007 niter->cmp = GT_EXPR;
1008 niter->bound = iv0->base;
1011 delta = fold_build2 (MINUS_EXPR, niter_type,
1012 fold_convert (niter_type, iv1->base),
1013 fold_convert (niter_type, iv0->base));
1015 /* First handle the special case that the step is +-1. */
1016 if ((integer_onep (iv0->step) && integer_zerop (iv1->step))
1017 || (integer_all_onesp (iv1->step) && integer_zerop (iv0->step)))
1019 /* for (i = iv0->base; i < iv1->base; i++)
1023 for (i = iv1->base; i > iv0->base; i--).
1025 In both cases # of iterations is iv1->base - iv0->base, assuming that
1026 iv1->base >= iv0->base.
1028 First try to derive a lower bound on the value of
1029 iv1->base - iv0->base, computed in full precision. If the difference
1030 is nonnegative, we are done, otherwise we must record the
1033 if (mpz_sgn (bnds->below) < 0)
1034 niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
1035 iv1->base, iv0->base);
1036 niter->niter = delta;
1037 niter->max = mpz_get_double_int (niter_type, bnds->up, false);
1041 if (integer_nonzerop (iv0->step))
1042 step = fold_convert (niter_type, iv0->step);
1044 step = fold_convert (niter_type,
1045 fold_build1 (NEGATE_EXPR, type, iv1->step));
1047 /* If we can determine the final value of the control iv exactly, we can
1048 transform the condition to != comparison. In particular, this will be
1049 the case if DELTA is constant. */
1050 if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step,
1051 exit_must_be_taken, bnds))
1055 zps.base = build_int_cst (niter_type, 0);
1057 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1058 zps does not overflow. */
1059 zps.no_overflow = true;
1061 return number_of_iterations_ne (type, &zps, delta, niter, true, bnds);
1064 /* Make sure that the control iv does not overflow. */
1065 if (!assert_no_overflow_lt (type, iv0, iv1, niter, step))
1068 /* We determine the number of iterations as (delta + step - 1) / step. For
1069 this to work, we must know that iv1->base >= iv0->base - step + 1,
1070 otherwise the loop does not roll. */
1071 assert_loop_rolls_lt (type, iv0, iv1, niter, bnds);
1073 s = fold_build2 (MINUS_EXPR, niter_type,
1074 step, build_int_cst (niter_type, 1));
1075 delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
1076 niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
1080 mpz_set_double_int (mstep, tree_to_double_int (step), true);
1081 mpz_add (tmp, bnds->up, mstep);
1082 mpz_sub_ui (tmp, tmp, 1);
1083 mpz_fdiv_q (tmp, tmp, mstep);
1084 niter->max = mpz_get_double_int (niter_type, tmp, false);
1091 /* Determines number of iterations of loop whose ending condition
1092 is IV0 <= IV1. TYPE is the type of the iv. The number of
1093 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
1094 we know that this condition must eventually become false (we derived this
1095 earlier, and possibly set NITER->assumptions to make sure this
1096 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1099 number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1,
1100 struct tree_niter_desc *niter, bool exit_must_be_taken,
1105 if (POINTER_TYPE_P (type))
1108 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1109 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1110 value of the type. This we must know anyway, since if it is
1111 equal to this value, the loop rolls forever. We do not check
1112 this condition for pointer type ivs, as the code cannot rely on
1113 the object to that the pointer points being placed at the end of
1114 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1115 not defined for pointers). */
1117 if (!exit_must_be_taken && !POINTER_TYPE_P (type))
1119 if (integer_nonzerop (iv0->step))
1120 assumption = fold_build2 (NE_EXPR, boolean_type_node,
1121 iv1->base, TYPE_MAX_VALUE (type));
1123 assumption = fold_build2 (NE_EXPR, boolean_type_node,
1124 iv0->base, TYPE_MIN_VALUE (type));
1126 if (integer_zerop (assumption))
1128 if (!integer_nonzerop (assumption))
1129 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1130 niter->assumptions, assumption);
1133 if (integer_nonzerop (iv0->step))
1135 if (POINTER_TYPE_P (type))
1136 iv1->base = fold_build2 (POINTER_PLUS_EXPR, type, iv1->base,
1137 build_int_cst (type1, 1));
1139 iv1->base = fold_build2 (PLUS_EXPR, type1, iv1->base,
1140 build_int_cst (type1, 1));
1142 else if (POINTER_TYPE_P (type))
1143 iv0->base = fold_build2 (POINTER_PLUS_EXPR, type, iv0->base,
1144 fold_build1 (NEGATE_EXPR, type1,
1145 build_int_cst (type1, 1)));
1147 iv0->base = fold_build2 (MINUS_EXPR, type1,
1148 iv0->base, build_int_cst (type1, 1));
1150 bounds_add (bnds, double_int_one, type1);
1152 return number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken,
1156 /* Dumps description of affine induction variable IV to FILE. */
1159 dump_affine_iv (FILE *file, affine_iv *iv)
1161 if (!integer_zerop (iv->step))
1162 fprintf (file, "[");
1164 print_generic_expr (dump_file, iv->base, TDF_SLIM);
1166 if (!integer_zerop (iv->step))
1168 fprintf (file, ", + , ");
1169 print_generic_expr (dump_file, iv->step, TDF_SLIM);
1170 fprintf (file, "]%s", iv->no_overflow ? "(no_overflow)" : "");
1174 /* Determine the number of iterations according to condition (for staying
1175 inside loop) which compares two induction variables using comparison
1176 operator CODE. The induction variable on left side of the comparison
1177 is IV0, the right-hand side is IV1. Both induction variables must have
1178 type TYPE, which must be an integer or pointer type. The steps of the
1179 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1181 LOOP is the loop whose number of iterations we are determining.
1183 ONLY_EXIT is true if we are sure this is the only way the loop could be
1184 exited (including possibly non-returning function calls, exceptions, etc.)
1185 -- in this case we can use the information whether the control induction
1186 variables can overflow or not in a more efficient way.
1188 The results (number of iterations and assumptions as described in
1189 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
1190 Returns false if it fails to determine number of iterations, true if it
1191 was determined (possibly with some assumptions). */
1194 number_of_iterations_cond (struct loop *loop,
1195 tree type, affine_iv *iv0, enum tree_code code,
1196 affine_iv *iv1, struct tree_niter_desc *niter,
1199 bool exit_must_be_taken = false, ret;
1202 /* The meaning of these assumptions is this:
1204 then the rest of information does not have to be valid
1205 if may_be_zero then the loop does not roll, even if
1207 niter->assumptions = boolean_true_node;
1208 niter->may_be_zero = boolean_false_node;
1209 niter->niter = NULL_TREE;
1210 niter->max = double_int_zero;
1212 niter->bound = NULL_TREE;
1213 niter->cmp = ERROR_MARK;
1215 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1216 the control variable is on lhs. */
1217 if (code == GE_EXPR || code == GT_EXPR
1218 || (code == NE_EXPR && integer_zerop (iv0->step)))
1221 code = swap_tree_comparison (code);
1224 if (POINTER_TYPE_P (type))
1226 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1227 to the same object. If they do, the control variable cannot wrap
1228 (as wrap around the bounds of memory will never return a pointer
1229 that would be guaranteed to point to the same object, even if we
1230 avoid undefined behavior by casting to size_t and back). */
1231 iv0->no_overflow = true;
1232 iv1->no_overflow = true;
1235 /* If the control induction variable does not overflow and the only exit
1236 from the loop is the one that we analyze, we know it must be taken
1240 if (!integer_zerop (iv0->step) && iv0->no_overflow)
1241 exit_must_be_taken = true;
1242 else if (!integer_zerop (iv1->step) && iv1->no_overflow)
1243 exit_must_be_taken = true;
1246 /* We can handle the case when neither of the sides of the comparison is
1247 invariant, provided that the test is NE_EXPR. This rarely occurs in
1248 practice, but it is simple enough to manage. */
1249 if (!integer_zerop (iv0->step) && !integer_zerop (iv1->step))
1251 if (code != NE_EXPR)
1254 iv0->step = fold_binary_to_constant (MINUS_EXPR, type,
1255 iv0->step, iv1->step);
1256 iv0->no_overflow = false;
1257 iv1->step = build_int_cst (type, 0);
1258 iv1->no_overflow = true;
1261 /* If the result of the comparison is a constant, the loop is weird. More
1262 precise handling would be possible, but the situation is not common enough
1263 to waste time on it. */
1264 if (integer_zerop (iv0->step) && integer_zerop (iv1->step))
1267 /* Ignore loops of while (i-- < 10) type. */
1268 if (code != NE_EXPR)
1270 if (iv0->step && tree_int_cst_sign_bit (iv0->step))
1273 if (!integer_zerop (iv1->step) && !tree_int_cst_sign_bit (iv1->step))
1277 /* If the loop exits immediately, there is nothing to do. */
1278 if (integer_zerop (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
1280 niter->niter = build_int_cst (unsigned_type_for (type), 0);
1281 niter->max = double_int_zero;
1285 /* OK, now we know we have a senseful loop. Handle several cases, depending
1286 on what comparison operator is used. */
1287 bound_difference (loop, iv1->base, iv0->base, &bnds);
1289 if (dump_file && (dump_flags & TDF_DETAILS))
1292 "Analyzing # of iterations of loop %d\n", loop->num);
1294 fprintf (dump_file, " exit condition ");
1295 dump_affine_iv (dump_file, iv0);
1296 fprintf (dump_file, " %s ",
1297 code == NE_EXPR ? "!="
1298 : code == LT_EXPR ? "<"
1300 dump_affine_iv (dump_file, iv1);
1301 fprintf (dump_file, "\n");
1303 fprintf (dump_file, " bounds on difference of bases: ");
1304 mpz_out_str (dump_file, 10, bnds.below);
1305 fprintf (dump_file, " ... ");
1306 mpz_out_str (dump_file, 10, bnds.up);
1307 fprintf (dump_file, "\n");
1313 gcc_assert (integer_zerop (iv1->step));
1314 ret = number_of_iterations_ne (type, iv0, iv1->base, niter,
1315 exit_must_be_taken, &bnds);
1319 ret = number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken,
1324 ret = number_of_iterations_le (type, iv0, iv1, niter, exit_must_be_taken,
1332 mpz_clear (bnds.up);
1333 mpz_clear (bnds.below);
1335 if (dump_file && (dump_flags & TDF_DETAILS))
1339 fprintf (dump_file, " result:\n");
1340 if (!integer_nonzerop (niter->assumptions))
1342 fprintf (dump_file, " under assumptions ");
1343 print_generic_expr (dump_file, niter->assumptions, TDF_SLIM);
1344 fprintf (dump_file, "\n");
1347 if (!integer_zerop (niter->may_be_zero))
1349 fprintf (dump_file, " zero if ");
1350 print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
1351 fprintf (dump_file, "\n");
1354 fprintf (dump_file, " # of iterations ");
1355 print_generic_expr (dump_file, niter->niter, TDF_SLIM);
1356 fprintf (dump_file, ", bounded by ");
1357 dump_double_int (dump_file, niter->max, true);
1358 fprintf (dump_file, "\n");
1361 fprintf (dump_file, " failed\n\n");
1366 /* Substitute NEW for OLD in EXPR and fold the result. */
1369 simplify_replace_tree (tree expr, tree old, tree new_tree)
1372 tree ret = NULL_TREE, e, se;
1378 || operand_equal_p (expr, old, 0))
1379 return unshare_expr (new_tree);
1384 n = TREE_OPERAND_LENGTH (expr);
1385 for (i = 0; i < n; i++)
1387 e = TREE_OPERAND (expr, i);
1388 se = simplify_replace_tree (e, old, new_tree);
1393 ret = copy_node (expr);
1395 TREE_OPERAND (ret, i) = se;
1398 return (ret ? fold (ret) : expr);
1401 /* Expand definitions of ssa names in EXPR as long as they are simple
1402 enough, and return the new expression. */
1405 expand_simple_operations (tree expr)
1408 tree ret = NULL_TREE, e, ee, e1;
1409 enum tree_code code;
1412 if (expr == NULL_TREE)
1415 if (is_gimple_min_invariant (expr))
1418 code = TREE_CODE (expr);
1419 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
1421 n = TREE_OPERAND_LENGTH (expr);
1422 for (i = 0; i < n; i++)
1424 e = TREE_OPERAND (expr, i);
1425 ee = expand_simple_operations (e);
1430 ret = copy_node (expr);
1432 TREE_OPERAND (ret, i) = ee;
1438 fold_defer_overflow_warnings ();
1440 fold_undefer_and_ignore_overflow_warnings ();
1444 if (TREE_CODE (expr) != SSA_NAME)
1447 stmt = SSA_NAME_DEF_STMT (expr);
1448 if (gimple_code (stmt) == GIMPLE_PHI)
1450 basic_block src, dest;
1452 if (gimple_phi_num_args (stmt) != 1)
1454 e = PHI_ARG_DEF (stmt, 0);
1456 /* Avoid propagating through loop exit phi nodes, which
1457 could break loop-closed SSA form restrictions. */
1458 dest = gimple_bb (stmt);
1459 src = single_pred (dest);
1460 if (TREE_CODE (e) == SSA_NAME
1461 && src->loop_father != dest->loop_father)
1464 return expand_simple_operations (e);
1466 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1469 e = gimple_assign_rhs1 (stmt);
1470 code = gimple_assign_rhs_code (stmt);
1471 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1473 if (is_gimple_min_invariant (e))
1476 if (code == SSA_NAME)
1477 return expand_simple_operations (e);
1485 /* Casts are simple. */
1486 ee = expand_simple_operations (e);
1487 return fold_build1 (code, TREE_TYPE (expr), ee);
1491 case POINTER_PLUS_EXPR:
1492 /* And increments and decrements by a constant are simple. */
1493 e1 = gimple_assign_rhs2 (stmt);
1494 if (!is_gimple_min_invariant (e1))
1497 ee = expand_simple_operations (e);
1498 return fold_build2 (code, TREE_TYPE (expr), ee, e1);
1505 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1506 expression (or EXPR unchanged, if no simplification was possible). */
1509 tree_simplify_using_condition_1 (tree cond, tree expr)
1512 tree e, te, e0, e1, e2, notcond;
1513 enum tree_code code = TREE_CODE (expr);
1515 if (code == INTEGER_CST)
1518 if (code == TRUTH_OR_EXPR
1519 || code == TRUTH_AND_EXPR
1520 || code == COND_EXPR)
1524 e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0));
1525 if (TREE_OPERAND (expr, 0) != e0)
1528 e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1));
1529 if (TREE_OPERAND (expr, 1) != e1)
1532 if (code == COND_EXPR)
1534 e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2));
1535 if (TREE_OPERAND (expr, 2) != e2)
1543 if (code == COND_EXPR)
1544 expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
1546 expr = fold_build2 (code, boolean_type_node, e0, e1);
1552 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
1553 propagation, and vice versa. Fold does not handle this, since it is
1554 considered too expensive. */
1555 if (TREE_CODE (cond) == EQ_EXPR)
1557 e0 = TREE_OPERAND (cond, 0);
1558 e1 = TREE_OPERAND (cond, 1);
1560 /* We know that e0 == e1. Check whether we cannot simplify expr
1562 e = simplify_replace_tree (expr, e0, e1);
1563 if (integer_zerop (e) || integer_nonzerop (e))
1566 e = simplify_replace_tree (expr, e1, e0);
1567 if (integer_zerop (e) || integer_nonzerop (e))
1570 if (TREE_CODE (expr) == EQ_EXPR)
1572 e0 = TREE_OPERAND (expr, 0);
1573 e1 = TREE_OPERAND (expr, 1);
1575 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
1576 e = simplify_replace_tree (cond, e0, e1);
1577 if (integer_zerop (e))
1579 e = simplify_replace_tree (cond, e1, e0);
1580 if (integer_zerop (e))
1583 if (TREE_CODE (expr) == NE_EXPR)
1585 e0 = TREE_OPERAND (expr, 0);
1586 e1 = TREE_OPERAND (expr, 1);
1588 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
1589 e = simplify_replace_tree (cond, e0, e1);
1590 if (integer_zerop (e))
1591 return boolean_true_node;
1592 e = simplify_replace_tree (cond, e1, e0);
1593 if (integer_zerop (e))
1594 return boolean_true_node;
1597 te = expand_simple_operations (expr);
1599 /* Check whether COND ==> EXPR. */
1600 notcond = invert_truthvalue (cond);
1601 e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te);
1602 if (e && integer_nonzerop (e))
1605 /* Check whether COND ==> not EXPR. */
1606 e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te);
1607 if (e && integer_zerop (e))
1613 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1614 expression (or EXPR unchanged, if no simplification was possible).
1615 Wrapper around tree_simplify_using_condition_1 that ensures that chains
1616 of simple operations in definitions of ssa names in COND are expanded,
1617 so that things like casts or incrementing the value of the bound before
1618 the loop do not cause us to fail. */
1621 tree_simplify_using_condition (tree cond, tree expr)
1623 cond = expand_simple_operations (cond);
1625 return tree_simplify_using_condition_1 (cond, expr);
1628 /* Tries to simplify EXPR using the conditions on entry to LOOP.
1629 Returns the simplified expression (or EXPR unchanged, if no
1630 simplification was possible).*/
1633 simplify_using_initial_conditions (struct loop *loop, tree expr)
1641 if (TREE_CODE (expr) == INTEGER_CST)
1644 /* Limit walking the dominators to avoid quadraticness in
1645 the number of BBs times the number of loops in degenerate
1647 for (bb = loop->header;
1648 bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK;
1649 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1651 if (!single_pred_p (bb))
1653 e = single_pred_edge (bb);
1655 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
1658 stmt = last_stmt (e->src);
1659 cond = fold_build2 (gimple_cond_code (stmt),
1661 gimple_cond_lhs (stmt),
1662 gimple_cond_rhs (stmt));
1663 if (e->flags & EDGE_FALSE_VALUE)
1664 cond = invert_truthvalue (cond);
1665 expr = tree_simplify_using_condition (cond, expr);
1672 /* Tries to simplify EXPR using the evolutions of the loop invariants
1673 in the superloops of LOOP. Returns the simplified expression
1674 (or EXPR unchanged, if no simplification was possible). */
1677 simplify_using_outer_evolutions (struct loop *loop, tree expr)
1679 enum tree_code code = TREE_CODE (expr);
1683 if (is_gimple_min_invariant (expr))
1686 if (code == TRUTH_OR_EXPR
1687 || code == TRUTH_AND_EXPR
1688 || code == COND_EXPR)
1692 e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
1693 if (TREE_OPERAND (expr, 0) != e0)
1696 e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
1697 if (TREE_OPERAND (expr, 1) != e1)
1700 if (code == COND_EXPR)
1702 e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
1703 if (TREE_OPERAND (expr, 2) != e2)
1711 if (code == COND_EXPR)
1712 expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
1714 expr = fold_build2 (code, boolean_type_node, e0, e1);
1720 e = instantiate_parameters (loop, expr);
1721 if (is_gimple_min_invariant (e))
1727 /* Returns true if EXIT is the only possible exit from LOOP. */
1730 loop_only_exit_p (const struct loop *loop, const_edge exit)
1733 gimple_stmt_iterator bsi;
1737 if (exit != single_exit (loop))
1740 body = get_loop_body (loop);
1741 for (i = 0; i < loop->num_nodes; i++)
1743 for (bsi = gsi_start_bb (body[i]); !gsi_end_p (bsi); gsi_next (&bsi))
1745 call = gsi_stmt (bsi);
1746 if (gimple_code (call) != GIMPLE_CALL)
1749 if (gimple_has_side_effects (call))
1761 /* Stores description of number of iterations of LOOP derived from
1762 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
1763 useful information could be derived (and fields of NITER has
1764 meaning described in comments at struct tree_niter_desc
1765 declaration), false otherwise. If WARN is true and
1766 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1767 potentially unsafe assumptions. */
1770 number_of_iterations_exit (struct loop *loop, edge exit,
1771 struct tree_niter_desc *niter,
1777 enum tree_code code;
1780 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
1783 niter->assumptions = boolean_false_node;
1784 stmt = last_stmt (exit->src);
1785 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
1788 /* We want the condition for staying inside loop. */
1789 code = gimple_cond_code (stmt);
1790 if (exit->flags & EDGE_TRUE_VALUE)
1791 code = invert_tree_comparison (code, false);
1806 op0 = gimple_cond_lhs (stmt);
1807 op1 = gimple_cond_rhs (stmt);
1808 type = TREE_TYPE (op0);
1810 if (TREE_CODE (type) != INTEGER_TYPE
1811 && !POINTER_TYPE_P (type))
1814 if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, false))
1816 if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, false))
1819 /* We don't want to see undefined signed overflow warnings while
1820 computing the number of iterations. */
1821 fold_defer_overflow_warnings ();
1823 iv0.base = expand_simple_operations (iv0.base);
1824 iv1.base = expand_simple_operations (iv1.base);
1825 if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter,
1826 loop_only_exit_p (loop, exit)))
1828 fold_undefer_and_ignore_overflow_warnings ();
1834 niter->assumptions = simplify_using_outer_evolutions (loop,
1835 niter->assumptions);
1836 niter->may_be_zero = simplify_using_outer_evolutions (loop,
1837 niter->may_be_zero);
1838 niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
1842 = simplify_using_initial_conditions (loop,
1843 niter->assumptions);
1845 = simplify_using_initial_conditions (loop,
1846 niter->may_be_zero);
1848 fold_undefer_and_ignore_overflow_warnings ();
1850 if (integer_onep (niter->assumptions))
1853 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1854 But if we can prove that there is overflow or some other source of weird
1855 behavior, ignore the loop even with -funsafe-loop-optimizations. */
1856 if (integer_zerop (niter->assumptions))
1859 if (flag_unsafe_loop_optimizations)
1860 niter->assumptions = boolean_true_node;
1864 const char *wording;
1865 location_t loc = gimple_location (stmt);
1867 /* We can provide a more specific warning if one of the operator is
1868 constant and the other advances by +1 or -1. */
1869 if (!integer_zerop (iv1.step)
1870 ? (integer_zerop (iv0.step)
1871 && (integer_onep (iv1.step) || integer_all_onesp (iv1.step)))
1872 : (integer_onep (iv0.step) || integer_all_onesp (iv0.step)))
1874 flag_unsafe_loop_optimizations
1875 ? N_("assuming that the loop is not infinite")
1876 : N_("cannot optimize possibly infinite loops");
1879 flag_unsafe_loop_optimizations
1880 ? N_("assuming that the loop counter does not overflow")
1881 : N_("cannot optimize loop, the loop counter may overflow");
1883 warning_at ((LOCATION_LINE (loc) > 0) ? loc : input_location,
1884 OPT_Wunsafe_loop_optimizations, "%s", gettext (wording));
1887 return flag_unsafe_loop_optimizations;
1890 /* Try to determine the number of iterations of LOOP. If we succeed,
1891 expression giving number of iterations is returned and *EXIT is
1892 set to the edge from that the information is obtained. Otherwise
1893 chrec_dont_know is returned. */
1896 find_loop_niter (struct loop *loop, edge *exit)
1899 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1901 tree niter = NULL_TREE, aniter;
1902 struct tree_niter_desc desc;
1905 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
1907 if (!just_once_each_iteration_p (loop, ex->src))
1910 if (!number_of_iterations_exit (loop, ex, &desc, false))
1913 if (integer_nonzerop (desc.may_be_zero))
1915 /* We exit in the first iteration through this exit.
1916 We won't find anything better. */
1917 niter = build_int_cst (unsigned_type_node, 0);
1922 if (!integer_zerop (desc.may_be_zero))
1925 aniter = desc.niter;
1929 /* Nothing recorded yet. */
1935 /* Prefer constants, the lower the better. */
1936 if (TREE_CODE (aniter) != INTEGER_CST)
1939 if (TREE_CODE (niter) != INTEGER_CST)
1946 if (tree_int_cst_lt (aniter, niter))
1953 VEC_free (edge, heap, exits);
1955 return niter ? niter : chrec_dont_know;
1958 /* Return true if loop is known to have bounded number of iterations. */
1961 finite_loop_p (struct loop *loop)
1964 VEC (edge, heap) *exits;
1966 struct tree_niter_desc desc;
1967 bool finite = false;
1969 if (flag_unsafe_loop_optimizations)
1971 if ((TREE_READONLY (current_function_decl)
1972 || DECL_PURE_P (current_function_decl))
1973 && !DECL_LOOPING_CONST_OR_PURE_P (current_function_decl))
1975 if (dump_file && (dump_flags & TDF_DETAILS))
1976 fprintf (dump_file, "Found loop %i to be finite: it is within pure or const function.\n",
1981 exits = get_loop_exit_edges (loop);
1982 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
1984 if (!just_once_each_iteration_p (loop, ex->src))
1987 if (number_of_iterations_exit (loop, ex, &desc, false))
1989 if (dump_file && (dump_flags & TDF_DETAILS))
1991 fprintf (dump_file, "Found loop %i to be finite: iterating ", loop->num);
1992 print_generic_expr (dump_file, desc.niter, TDF_SLIM);
1993 fprintf (dump_file, " times\n");
1999 VEC_free (edge, heap, exits);
2005 Analysis of a number of iterations of a loop by a brute-force evaluation.
2009 /* Bound on the number of iterations we try to evaluate. */
2011 #define MAX_ITERATIONS_TO_TRACK \
2012 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
2014 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
2015 result by a chain of operations such that all but exactly one of their
2016 operands are constants. */
2019 chain_of_csts_start (struct loop *loop, tree x)
2021 gimple stmt = SSA_NAME_DEF_STMT (x);
2023 basic_block bb = gimple_bb (stmt);
2024 enum tree_code code;
2027 || !flow_bb_inside_loop_p (loop, bb))
2030 if (gimple_code (stmt) == GIMPLE_PHI)
2032 if (bb == loop->header)
2038 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2041 code = gimple_assign_rhs_code (stmt);
2042 if (gimple_references_memory_p (stmt)
2043 || TREE_CODE_CLASS (code) == tcc_reference
2044 || (code == ADDR_EXPR
2045 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
2048 use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
2049 if (use == NULL_TREE)
2052 return chain_of_csts_start (loop, use);
2055 /* Determines whether the expression X is derived from a result of a phi node
2056 in header of LOOP such that
2058 * the derivation of X consists only from operations with constants
2059 * the initial value of the phi node is constant
2060 * the value of the phi node in the next iteration can be derived from the
2061 value in the current iteration by a chain of operations with constants.
2063 If such phi node exists, it is returned, otherwise NULL is returned. */
2066 get_base_for (struct loop *loop, tree x)
2071 if (is_gimple_min_invariant (x))
2074 phi = chain_of_csts_start (loop, x);
2078 init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
2079 next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
2081 if (TREE_CODE (next) != SSA_NAME)
2084 if (!is_gimple_min_invariant (init))
2087 if (chain_of_csts_start (loop, next) != phi)
2093 /* Given an expression X, then
2095 * if X is NULL_TREE, we return the constant BASE.
2096 * otherwise X is a SSA name, whose value in the considered loop is derived
2097 by a chain of operations with constant from a result of a phi node in
2098 the header of the loop. Then we return value of X when the value of the
2099 result of this phi node is given by the constant BASE. */
2102 get_val_for (tree x, tree base)
2106 gcc_assert (is_gimple_min_invariant (base));
2111 stmt = SSA_NAME_DEF_STMT (x);
2112 if (gimple_code (stmt) == GIMPLE_PHI)
2115 gcc_assert (is_gimple_assign (stmt));
2117 /* STMT must be either an assignment of a single SSA name or an
2118 expression involving an SSA name and a constant. Try to fold that
2119 expression using the value for the SSA name. */
2120 if (gimple_assign_ssa_name_copy_p (stmt))
2121 return get_val_for (gimple_assign_rhs1 (stmt), base);
2122 else if (gimple_assign_rhs_class (stmt) == GIMPLE_UNARY_RHS
2123 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
2125 return fold_build1 (gimple_assign_rhs_code (stmt),
2126 gimple_expr_type (stmt),
2127 get_val_for (gimple_assign_rhs1 (stmt), base));
2129 else if (gimple_assign_rhs_class (stmt) == GIMPLE_BINARY_RHS)
2131 tree rhs1 = gimple_assign_rhs1 (stmt);
2132 tree rhs2 = gimple_assign_rhs2 (stmt);
2133 if (TREE_CODE (rhs1) == SSA_NAME)
2134 rhs1 = get_val_for (rhs1, base);
2135 else if (TREE_CODE (rhs2) == SSA_NAME)
2136 rhs2 = get_val_for (rhs2, base);
2139 return fold_build2 (gimple_assign_rhs_code (stmt),
2140 gimple_expr_type (stmt), rhs1, rhs2);
2147 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2148 by brute force -- i.e. by determining the value of the operands of the
2149 condition at EXIT in first few iterations of the loop (assuming that
2150 these values are constant) and determining the first one in that the
2151 condition is not satisfied. Returns the constant giving the number
2152 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
2155 loop_niter_by_eval (struct loop *loop, edge exit)
2158 tree op[2], val[2], next[2], aval[2];
2163 cond = last_stmt (exit->src);
2164 if (!cond || gimple_code (cond) != GIMPLE_COND)
2165 return chrec_dont_know;
2167 cmp = gimple_cond_code (cond);
2168 if (exit->flags & EDGE_TRUE_VALUE)
2169 cmp = invert_tree_comparison (cmp, false);
2179 op[0] = gimple_cond_lhs (cond);
2180 op[1] = gimple_cond_rhs (cond);
2184 return chrec_dont_know;
2187 for (j = 0; j < 2; j++)
2189 if (is_gimple_min_invariant (op[j]))
2192 next[j] = NULL_TREE;
2197 phi = get_base_for (loop, op[j]);
2199 return chrec_dont_know;
2200 val[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
2201 next[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
2205 /* Don't issue signed overflow warnings. */
2206 fold_defer_overflow_warnings ();
2208 for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
2210 for (j = 0; j < 2; j++)
2211 aval[j] = get_val_for (op[j], val[j]);
2213 acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]);
2214 if (acnd && integer_zerop (acnd))
2216 fold_undefer_and_ignore_overflow_warnings ();
2217 if (dump_file && (dump_flags & TDF_DETAILS))
2219 "Proved that loop %d iterates %d times using brute force.\n",
2221 return build_int_cst (unsigned_type_node, i);
2224 for (j = 0; j < 2; j++)
2226 val[j] = get_val_for (next[j], val[j]);
2227 if (!is_gimple_min_invariant (val[j]))
2229 fold_undefer_and_ignore_overflow_warnings ();
2230 return chrec_dont_know;
2235 fold_undefer_and_ignore_overflow_warnings ();
2237 return chrec_dont_know;
2240 /* Finds the exit of the LOOP by that the loop exits after a constant
2241 number of iterations and stores the exit edge to *EXIT. The constant
2242 giving the number of iterations of LOOP is returned. The number of
2243 iterations is determined using loop_niter_by_eval (i.e. by brute force
2244 evaluation). If we are unable to find the exit for that loop_niter_by_eval
2245 determines the number of iterations, chrec_dont_know is returned. */
2248 find_loop_niter_by_eval (struct loop *loop, edge *exit)
2251 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
2253 tree niter = NULL_TREE, aniter;
2257 /* Loops with multiple exits are expensive to handle and less important. */
2258 if (!flag_expensive_optimizations
2259 && VEC_length (edge, exits) > 1)
2260 return chrec_dont_know;
2262 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
2264 if (!just_once_each_iteration_p (loop, ex->src))
2267 aniter = loop_niter_by_eval (loop, ex);
2268 if (chrec_contains_undetermined (aniter))
2272 && !tree_int_cst_lt (aniter, niter))
2278 VEC_free (edge, heap, exits);
2280 return niter ? niter : chrec_dont_know;
2285 Analysis of upper bounds on number of iterations of a loop.
2289 static double_int derive_constant_upper_bound_ops (tree, tree,
2290 enum tree_code, tree);
2292 /* Returns a constant upper bound on the value of the right-hand side of
2293 an assignment statement STMT. */
2296 derive_constant_upper_bound_assign (gimple stmt)
2298 enum tree_code code = gimple_assign_rhs_code (stmt);
2299 tree op0 = gimple_assign_rhs1 (stmt);
2300 tree op1 = gimple_assign_rhs2 (stmt);
2302 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt)),
2306 /* Returns a constant upper bound on the value of expression VAL. VAL
2307 is considered to be unsigned. If its type is signed, its value must
2311 derive_constant_upper_bound (tree val)
2313 enum tree_code code;
2316 extract_ops_from_tree (val, &code, &op0, &op1);
2317 return derive_constant_upper_bound_ops (TREE_TYPE (val), op0, code, op1);
2320 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
2321 whose type is TYPE. The expression is considered to be unsigned. If
2322 its type is signed, its value must be nonnegative. */
2325 derive_constant_upper_bound_ops (tree type, tree op0,
2326 enum tree_code code, tree op1)
2329 double_int bnd, max, mmax, cst;
2332 if (INTEGRAL_TYPE_P (type))
2333 maxt = TYPE_MAX_VALUE (type);
2335 maxt = upper_bound_in_type (type, type);
2337 max = tree_to_double_int (maxt);
2342 return tree_to_double_int (op0);
2345 subtype = TREE_TYPE (op0);
2346 if (!TYPE_UNSIGNED (subtype)
2347 /* If TYPE is also signed, the fact that VAL is nonnegative implies
2348 that OP0 is nonnegative. */
2349 && TYPE_UNSIGNED (type)
2350 && !tree_expr_nonnegative_p (op0))
2352 /* If we cannot prove that the casted expression is nonnegative,
2353 we cannot establish more useful upper bound than the precision
2354 of the type gives us. */
2358 /* We now know that op0 is an nonnegative value. Try deriving an upper
2360 bnd = derive_constant_upper_bound (op0);
2362 /* If the bound does not fit in TYPE, max. value of TYPE could be
2364 if (double_int_ucmp (max, bnd) < 0)
2370 case POINTER_PLUS_EXPR:
2372 if (TREE_CODE (op1) != INTEGER_CST
2373 || !tree_expr_nonnegative_p (op0))
2376 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
2377 choose the most logical way how to treat this constant regardless
2378 of the signedness of the type. */
2379 cst = tree_to_double_int (op1);
2380 cst = double_int_sext (cst, TYPE_PRECISION (type));
2381 if (code != MINUS_EXPR)
2382 cst = double_int_neg (cst);
2384 bnd = derive_constant_upper_bound (op0);
2386 if (double_int_negative_p (cst))
2388 cst = double_int_neg (cst);
2389 /* Avoid CST == 0x80000... */
2390 if (double_int_negative_p (cst))
2393 /* OP0 + CST. We need to check that
2394 BND <= MAX (type) - CST. */
2396 mmax = double_int_add (max, double_int_neg (cst));
2397 if (double_int_ucmp (bnd, mmax) > 0)
2400 return double_int_add (bnd, cst);
2404 /* OP0 - CST, where CST >= 0.
2406 If TYPE is signed, we have already verified that OP0 >= 0, and we
2407 know that the result is nonnegative. This implies that
2410 If TYPE is unsigned, we must additionally know that OP0 >= CST,
2411 otherwise the operation underflows.
2414 /* This should only happen if the type is unsigned; however, for
2415 buggy programs that use overflowing signed arithmetics even with
2416 -fno-wrapv, this condition may also be true for signed values. */
2417 if (double_int_ucmp (bnd, cst) < 0)
2420 if (TYPE_UNSIGNED (type))
2422 tree tem = fold_binary (GE_EXPR, boolean_type_node, op0,
2423 double_int_to_tree (type, cst));
2424 if (!tem || integer_nonzerop (tem))
2428 bnd = double_int_add (bnd, double_int_neg (cst));
2433 case FLOOR_DIV_EXPR:
2434 case EXACT_DIV_EXPR:
2435 if (TREE_CODE (op1) != INTEGER_CST
2436 || tree_int_cst_sign_bit (op1))
2439 bnd = derive_constant_upper_bound (op0);
2440 return double_int_udiv (bnd, tree_to_double_int (op1), FLOOR_DIV_EXPR);
2443 if (TREE_CODE (op1) != INTEGER_CST
2444 || tree_int_cst_sign_bit (op1))
2446 return tree_to_double_int (op1);
2449 stmt = SSA_NAME_DEF_STMT (op0);
2450 if (gimple_code (stmt) != GIMPLE_ASSIGN
2451 || gimple_assign_lhs (stmt) != op0)
2453 return derive_constant_upper_bound_assign (stmt);
2460 /* Records that every statement in LOOP is executed I_BOUND times.
2461 REALISTIC is true if I_BOUND is expected to be close to the real number
2462 of iterations. UPPER is true if we are sure the loop iterates at most
2466 record_niter_bound (struct loop *loop, double_int i_bound, bool realistic,
2469 /* Update the bounds only when there is no previous estimation, or when the current
2470 estimation is smaller. */
2472 && (!loop->any_upper_bound
2473 || double_int_ucmp (i_bound, loop->nb_iterations_upper_bound) < 0))
2475 loop->any_upper_bound = true;
2476 loop->nb_iterations_upper_bound = i_bound;
2479 && (!loop->any_estimate
2480 || double_int_ucmp (i_bound, loop->nb_iterations_estimate) < 0))
2482 loop->any_estimate = true;
2483 loop->nb_iterations_estimate = i_bound;
2487 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
2488 is true if the loop is exited immediately after STMT, and this exit
2489 is taken at last when the STMT is executed BOUND + 1 times.
2490 REALISTIC is true if BOUND is expected to be close to the real number
2491 of iterations. UPPER is true if we are sure the loop iterates at most
2492 BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */
2495 record_estimate (struct loop *loop, tree bound, double_int i_bound,
2496 gimple at_stmt, bool is_exit, bool realistic, bool upper)
2501 if (dump_file && (dump_flags & TDF_DETAILS))
2503 fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : "");
2504 print_gimple_stmt (dump_file, at_stmt, 0, TDF_SLIM);
2505 fprintf (dump_file, " is %sexecuted at most ",
2506 upper ? "" : "probably ");
2507 print_generic_expr (dump_file, bound, TDF_SLIM);
2508 fprintf (dump_file, " (bounded by ");
2509 dump_double_int (dump_file, i_bound, true);
2510 fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num);
2513 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
2514 real number of iterations. */
2515 if (TREE_CODE (bound) != INTEGER_CST)
2517 if (!upper && !realistic)
2520 /* If we have a guaranteed upper bound, record it in the appropriate
2524 struct nb_iter_bound *elt = ggc_alloc_nb_iter_bound ();
2526 elt->bound = i_bound;
2527 elt->stmt = at_stmt;
2528 elt->is_exit = is_exit;
2529 elt->next = loop->bounds;
2533 /* Update the number of iteration estimates according to the bound.
2534 If at_stmt is an exit, then every statement in the loop is
2535 executed at most BOUND + 1 times. If it is not an exit, then
2536 some of the statements before it could be executed BOUND + 2
2537 times, if an exit of LOOP is before stmt. */
2538 exit = single_exit (loop);
2541 && dominated_by_p (CDI_DOMINATORS,
2542 exit->src, gimple_bb (at_stmt))))
2543 delta = double_int_one;
2545 delta = double_int_two;
2546 i_bound = double_int_add (i_bound, delta);
2548 /* If an overflow occurred, ignore the result. */
2549 if (double_int_ucmp (i_bound, delta) < 0)
2552 record_niter_bound (loop, i_bound, realistic, upper);
2555 /* Record the estimate on number of iterations of LOOP based on the fact that
2556 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
2557 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
2558 estimated number of iterations is expected to be close to the real one.
2559 UPPER is true if we are sure the induction variable does not wrap. */
2562 record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple stmt,
2563 tree low, tree high, bool realistic, bool upper)
2565 tree niter_bound, extreme, delta;
2566 tree type = TREE_TYPE (base), unsigned_type;
2569 if (TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
2572 if (dump_file && (dump_flags & TDF_DETAILS))
2574 fprintf (dump_file, "Induction variable (");
2575 print_generic_expr (dump_file, TREE_TYPE (base), TDF_SLIM);
2576 fprintf (dump_file, ") ");
2577 print_generic_expr (dump_file, base, TDF_SLIM);
2578 fprintf (dump_file, " + ");
2579 print_generic_expr (dump_file, step, TDF_SLIM);
2580 fprintf (dump_file, " * iteration does not wrap in statement ");
2581 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2582 fprintf (dump_file, " in loop %d.\n", loop->num);
2585 unsigned_type = unsigned_type_for (type);
2586 base = fold_convert (unsigned_type, base);
2587 step = fold_convert (unsigned_type, step);
2589 if (tree_int_cst_sign_bit (step))
2591 extreme = fold_convert (unsigned_type, low);
2592 if (TREE_CODE (base) != INTEGER_CST)
2593 base = fold_convert (unsigned_type, high);
2594 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
2595 step = fold_build1 (NEGATE_EXPR, unsigned_type, step);
2599 extreme = fold_convert (unsigned_type, high);
2600 if (TREE_CODE (base) != INTEGER_CST)
2601 base = fold_convert (unsigned_type, low);
2602 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
2605 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
2606 would get out of the range. */
2607 niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step);
2608 max = derive_constant_upper_bound (niter_bound);
2609 record_estimate (loop, niter_bound, max, stmt, false, realistic, upper);
2612 /* Returns true if REF is a reference to an array at the end of a dynamically
2613 allocated structure. If this is the case, the array may be allocated larger
2614 than its upper bound implies. */
2617 array_at_struct_end_p (tree ref)
2619 tree base = get_base_address (ref);
2622 /* Unless the reference is through a pointer, the size of the array matches
2624 if (!base || !INDIRECT_REF_P (base))
2627 for (;handled_component_p (ref); ref = parent)
2629 parent = TREE_OPERAND (ref, 0);
2631 if (TREE_CODE (ref) == COMPONENT_REF)
2633 /* All fields of a union are at its end. */
2634 if (TREE_CODE (TREE_TYPE (parent)) == UNION_TYPE)
2637 /* Unless the field is at the end of the struct, we are done. */
2638 field = TREE_OPERAND (ref, 1);
2639 if (TREE_CHAIN (field))
2643 /* The other options are ARRAY_REF, ARRAY_RANGE_REF, VIEW_CONVERT_EXPR.
2644 In all these cases, we might be accessing the last element, and
2645 although in practice this will probably never happen, it is legal for
2646 the indices of this last element to exceed the bounds of the array.
2647 Therefore, continue checking. */
2650 gcc_assert (INDIRECT_REF_P (ref));
2654 /* Determine information about number of iterations a LOOP from the index
2655 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
2656 guaranteed to be executed in every iteration of LOOP. Callback for
2667 idx_infer_loop_bounds (tree base, tree *idx, void *dta)
2669 struct ilb_data *data = (struct ilb_data *) dta;
2670 tree ev, init, step;
2671 tree low, high, type, next;
2672 bool sign, upper = data->reliable, at_end = false;
2673 struct loop *loop = data->loop;
2675 if (TREE_CODE (base) != ARRAY_REF)
2678 /* For arrays at the end of the structure, we are not guaranteed that they
2679 do not really extend over their declared size. However, for arrays of
2680 size greater than one, this is unlikely to be intended. */
2681 if (array_at_struct_end_p (base))
2687 ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx));
2688 init = initial_condition (ev);
2689 step = evolution_part_in_loop_num (ev, loop->num);
2693 || TREE_CODE (step) != INTEGER_CST
2694 || integer_zerop (step)
2695 || tree_contains_chrecs (init, NULL)
2696 || chrec_contains_symbols_defined_in_loop (init, loop->num))
2699 low = array_ref_low_bound (base);
2700 high = array_ref_up_bound (base);
2702 /* The case of nonconstant bounds could be handled, but it would be
2704 if (TREE_CODE (low) != INTEGER_CST
2706 || TREE_CODE (high) != INTEGER_CST)
2708 sign = tree_int_cst_sign_bit (step);
2709 type = TREE_TYPE (step);
2711 /* The array of length 1 at the end of a structure most likely extends
2712 beyond its bounds. */
2714 && operand_equal_p (low, high, 0))
2717 /* In case the relevant bound of the array does not fit in type, or
2718 it does, but bound + step (in type) still belongs into the range of the
2719 array, the index may wrap and still stay within the range of the array
2720 (consider e.g. if the array is indexed by the full range of
2723 To make things simpler, we require both bounds to fit into type, although
2724 there are cases where this would not be strictly necessary. */
2725 if (!int_fits_type_p (high, type)
2726 || !int_fits_type_p (low, type))
2728 low = fold_convert (type, low);
2729 high = fold_convert (type, high);
2732 next = fold_binary (PLUS_EXPR, type, low, step);
2734 next = fold_binary (PLUS_EXPR, type, high, step);
2736 if (tree_int_cst_compare (low, next) <= 0
2737 && tree_int_cst_compare (next, high) <= 0)
2740 record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true, upper);
2744 /* Determine information about number of iterations a LOOP from the bounds
2745 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
2746 STMT is guaranteed to be executed in every iteration of LOOP.*/
2749 infer_loop_bounds_from_ref (struct loop *loop, gimple stmt, tree ref,
2752 struct ilb_data data;
2756 data.reliable = reliable;
2757 for_each_index (&ref, idx_infer_loop_bounds, &data);
2760 /* Determine information about number of iterations of a LOOP from the way
2761 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
2762 executed in every iteration of LOOP. */
2765 infer_loop_bounds_from_array (struct loop *loop, gimple stmt, bool reliable)
2767 if (is_gimple_assign (stmt))
2769 tree op0 = gimple_assign_lhs (stmt);
2770 tree op1 = gimple_assign_rhs1 (stmt);
2772 /* For each memory access, analyze its access function
2773 and record a bound on the loop iteration domain. */
2774 if (REFERENCE_CLASS_P (op0))
2775 infer_loop_bounds_from_ref (loop, stmt, op0, reliable);
2777 if (REFERENCE_CLASS_P (op1))
2778 infer_loop_bounds_from_ref (loop, stmt, op1, reliable);
2780 else if (is_gimple_call (stmt))
2783 unsigned i, n = gimple_call_num_args (stmt);
2785 lhs = gimple_call_lhs (stmt);
2786 if (lhs && REFERENCE_CLASS_P (lhs))
2787 infer_loop_bounds_from_ref (loop, stmt, lhs, reliable);
2789 for (i = 0; i < n; i++)
2791 arg = gimple_call_arg (stmt, i);
2792 if (REFERENCE_CLASS_P (arg))
2793 infer_loop_bounds_from_ref (loop, stmt, arg, reliable);
2798 /* Determine information about number of iterations of a LOOP from the fact
2799 that signed arithmetics in STMT does not overflow. */
2802 infer_loop_bounds_from_signedness (struct loop *loop, gimple stmt)
2804 tree def, base, step, scev, type, low, high;
2806 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2809 def = gimple_assign_lhs (stmt);
2811 if (TREE_CODE (def) != SSA_NAME)
2814 type = TREE_TYPE (def);
2815 if (!INTEGRAL_TYPE_P (type)
2816 || !TYPE_OVERFLOW_UNDEFINED (type))
2819 scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
2820 if (chrec_contains_undetermined (scev))
2823 base = initial_condition_in_loop_num (scev, loop->num);
2824 step = evolution_part_in_loop_num (scev, loop->num);
2827 || TREE_CODE (step) != INTEGER_CST
2828 || tree_contains_chrecs (base, NULL)
2829 || chrec_contains_symbols_defined_in_loop (base, loop->num))
2832 low = lower_bound_in_type (type, type);
2833 high = upper_bound_in_type (type, type);
2835 record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
2838 /* The following analyzers are extracting informations on the bounds
2839 of LOOP from the following undefined behaviors:
2841 - data references should not access elements over the statically
2844 - signed variables should not overflow when flag_wrapv is not set.
2848 infer_loop_bounds_from_undefined (struct loop *loop)
2852 gimple_stmt_iterator bsi;
2856 bbs = get_loop_body (loop);
2858 for (i = 0; i < loop->num_nodes; i++)
2862 /* If BB is not executed in each iteration of the loop, we cannot
2863 use the operations in it to infer reliable upper bound on the
2864 # of iterations of the loop. However, we can use it as a guess. */
2865 reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb);
2867 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
2869 gimple stmt = gsi_stmt (bsi);
2871 infer_loop_bounds_from_array (loop, stmt, reliable);
2874 infer_loop_bounds_from_signedness (loop, stmt);
2882 /* Converts VAL to double_int. */
2885 gcov_type_to_double_int (gcov_type val)
2889 ret.low = (unsigned HOST_WIDE_INT) val;
2890 /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by
2891 the size of type. */
2892 val >>= HOST_BITS_PER_WIDE_INT - 1;
2894 ret.high = (unsigned HOST_WIDE_INT) val;
2899 /* Records estimates on numbers of iterations of LOOP. */
2902 estimate_numbers_of_iterations_loop (struct loop *loop)
2904 VEC (edge, heap) *exits;
2907 struct tree_niter_desc niter_desc;
2911 /* Give up if we already have tried to compute an estimation. */
2912 if (loop->estimate_state != EST_NOT_COMPUTED)
2914 loop->estimate_state = EST_AVAILABLE;
2915 loop->any_upper_bound = false;
2916 loop->any_estimate = false;
2918 exits = get_loop_exit_edges (loop);
2919 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
2921 if (!number_of_iterations_exit (loop, ex, &niter_desc, false))
2924 niter = niter_desc.niter;
2925 type = TREE_TYPE (niter);
2926 if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST)
2927 niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
2928 build_int_cst (type, 0),
2930 record_estimate (loop, niter, niter_desc.max,
2931 last_stmt (ex->src),
2934 VEC_free (edge, heap, exits);
2936 infer_loop_bounds_from_undefined (loop);
2938 /* If we have a measured profile, use it to estimate the number of
2940 if (loop->header->count != 0)
2942 gcov_type nit = expected_loop_iterations_unbounded (loop) + 1;
2943 bound = gcov_type_to_double_int (nit);
2944 record_niter_bound (loop, bound, true, false);
2947 /* If an upper bound is smaller than the realistic estimate of the
2948 number of iterations, use the upper bound instead. */
2949 if (loop->any_upper_bound
2950 && loop->any_estimate
2951 && double_int_ucmp (loop->nb_iterations_upper_bound,
2952 loop->nb_iterations_estimate) < 0)
2953 loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
2956 /* Records estimates on numbers of iterations of loops. */
2959 estimate_numbers_of_iterations (void)
2964 /* We don't want to issue signed overflow warnings while getting
2965 loop iteration estimates. */
2966 fold_defer_overflow_warnings ();
2968 FOR_EACH_LOOP (li, loop, 0)
2970 estimate_numbers_of_iterations_loop (loop);
2973 fold_undefer_and_ignore_overflow_warnings ();
2976 /* Returns true if statement S1 dominates statement S2. */
2979 stmt_dominates_stmt_p (gimple s1, gimple s2)
2981 basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
2989 gimple_stmt_iterator bsi;
2991 if (gimple_code (s2) == GIMPLE_PHI)
2994 if (gimple_code (s1) == GIMPLE_PHI)
2997 for (bsi = gsi_start_bb (bb1); gsi_stmt (bsi) != s2; gsi_next (&bsi))
2998 if (gsi_stmt (bsi) == s1)
3004 return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
3007 /* Returns true when we can prove that the number of executions of
3008 STMT in the loop is at most NITER, according to the bound on
3009 the number of executions of the statement NITER_BOUND->stmt recorded in
3010 NITER_BOUND. If STMT is NULL, we must prove this bound for all
3011 statements in the loop. */
3014 n_of_executions_at_most (gimple stmt,
3015 struct nb_iter_bound *niter_bound,
3018 double_int bound = niter_bound->bound;
3019 tree nit_type = TREE_TYPE (niter), e;
3022 gcc_assert (TYPE_UNSIGNED (nit_type));
3024 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
3025 the number of iterations is small. */
3026 if (!double_int_fits_to_tree_p (nit_type, bound))
3029 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3030 times. This means that:
3032 -- if NITER_BOUND->is_exit is true, then everything before
3033 NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3034 times, and everything after it at most NITER_BOUND->bound times.
3036 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
3037 is executed, then NITER_BOUND->stmt is executed as well in the same
3038 iteration (we conclude that if both statements belong to the same
3039 basic block, or if STMT is after NITER_BOUND->stmt), then STMT
3040 is executed at most NITER_BOUND->bound + 1 times. Otherwise STMT is
3041 executed at most NITER_BOUND->bound + 2 times. */
3043 if (niter_bound->is_exit)
3046 && stmt != niter_bound->stmt
3047 && stmt_dominates_stmt_p (niter_bound->stmt, stmt))
3055 || (gimple_bb (stmt) != gimple_bb (niter_bound->stmt)
3056 && !stmt_dominates_stmt_p (niter_bound->stmt, stmt)))
3058 bound = double_int_add (bound, double_int_one);
3059 if (double_int_zero_p (bound)
3060 || !double_int_fits_to_tree_p (nit_type, bound))
3066 e = fold_binary (cmp, boolean_type_node,
3067 niter, double_int_to_tree (nit_type, bound));
3068 return e && integer_nonzerop (e);
3071 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
3074 nowrap_type_p (tree type)
3076 if (INTEGRAL_TYPE_P (type)
3077 && TYPE_OVERFLOW_UNDEFINED (type))
3080 if (POINTER_TYPE_P (type))
3086 /* Return false only when the induction variable BASE + STEP * I is
3087 known to not overflow: i.e. when the number of iterations is small
3088 enough with respect to the step and initial condition in order to
3089 keep the evolution confined in TYPEs bounds. Return true when the
3090 iv is known to overflow or when the property is not computable.
3092 USE_OVERFLOW_SEMANTICS is true if this function should assume that
3093 the rules for overflow of the given language apply (e.g., that signed
3094 arithmetics in C does not overflow). */
3097 scev_probably_wraps_p (tree base, tree step,
3098 gimple at_stmt, struct loop *loop,
3099 bool use_overflow_semantics)
3101 struct nb_iter_bound *bound;
3102 tree delta, step_abs;
3103 tree unsigned_type, valid_niter;
3104 tree type = TREE_TYPE (step);
3106 /* FIXME: We really need something like
3107 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
3109 We used to test for the following situation that frequently appears
3110 during address arithmetics:
3112 D.1621_13 = (long unsigned intD.4) D.1620_12;
3113 D.1622_14 = D.1621_13 * 8;
3114 D.1623_15 = (doubleD.29 *) D.1622_14;
3116 And derived that the sequence corresponding to D_14
3117 can be proved to not wrap because it is used for computing a
3118 memory access; however, this is not really the case -- for example,
3119 if D_12 = (unsigned char) [254,+,1], then D_14 has values
3120 2032, 2040, 0, 8, ..., but the code is still legal. */
3122 if (chrec_contains_undetermined (base)
3123 || chrec_contains_undetermined (step))
3126 if (integer_zerop (step))
3129 /* If we can use the fact that signed and pointer arithmetics does not
3130 wrap, we are done. */
3131 if (use_overflow_semantics && nowrap_type_p (TREE_TYPE (base)))
3134 /* To be able to use estimates on number of iterations of the loop,
3135 we must have an upper bound on the absolute value of the step. */
3136 if (TREE_CODE (step) != INTEGER_CST)
3139 /* Don't issue signed overflow warnings. */
3140 fold_defer_overflow_warnings ();
3142 /* Otherwise, compute the number of iterations before we reach the
3143 bound of the type, and verify that the loop is exited before this
3145 unsigned_type = unsigned_type_for (type);
3146 base = fold_convert (unsigned_type, base);
3148 if (tree_int_cst_sign_bit (step))
3150 tree extreme = fold_convert (unsigned_type,
3151 lower_bound_in_type (type, type));
3152 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
3153 step_abs = fold_build1 (NEGATE_EXPR, unsigned_type,
3154 fold_convert (unsigned_type, step));
3158 tree extreme = fold_convert (unsigned_type,
3159 upper_bound_in_type (type, type));
3160 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
3161 step_abs = fold_convert (unsigned_type, step);
3164 valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
3166 estimate_numbers_of_iterations_loop (loop);
3167 for (bound = loop->bounds; bound; bound = bound->next)
3169 if (n_of_executions_at_most (at_stmt, bound, valid_niter))
3171 fold_undefer_and_ignore_overflow_warnings ();
3176 fold_undefer_and_ignore_overflow_warnings ();
3178 /* At this point we still don't have a proof that the iv does not
3179 overflow: give up. */
3183 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
3186 free_numbers_of_iterations_estimates_loop (struct loop *loop)
3188 struct nb_iter_bound *bound, *next;
3190 loop->nb_iterations = NULL;
3191 loop->estimate_state = EST_NOT_COMPUTED;
3192 for (bound = loop->bounds; bound; bound = next)
3198 loop->bounds = NULL;
3201 /* Frees the information on upper bounds on numbers of iterations of loops. */
3204 free_numbers_of_iterations_estimates (void)
3209 FOR_EACH_LOOP (li, loop, 0)
3211 free_numbers_of_iterations_estimates_loop (loop);
3215 /* Substitute value VAL for ssa name NAME inside expressions held
3219 substitute_in_loop_info (struct loop *loop, tree name, tree val)
3221 loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);