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. If NO_OVERFLOW is true, then the control variable of
540 the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed
541 that the loop ends through this exit, i.e., the induction variable ever
542 reaches the value of C.
544 The value C is equal to final - base, where final and base are the final and
545 initial value of the actual induction variable in the analysed loop. BNDS
546 bounds the value of this difference when computed in signed type with
547 unbounded range, while the computation of C is performed in an unsigned
548 type with the range matching the range of the type of the induction variable.
549 In particular, BNDS.up contains an upper bound on C in the following cases:
550 -- if the iv must reach its final value without overflow, i.e., if
551 NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
552 -- if final >= base, which we know to hold when BNDS.below >= 0. */
555 number_of_iterations_ne_max (mpz_t bnd, bool no_overflow, tree c, tree s,
556 bounds *bnds, bool exit_must_be_taken)
560 bool bnds_u_valid = ((no_overflow && exit_must_be_taken)
561 || mpz_sgn (bnds->below) >= 0);
563 if (multiple_of_p (TREE_TYPE (c), c, s))
565 /* If C is an exact multiple of S, then its value will be reached before
566 the induction variable overflows (unless the loop is exited in some
567 other way before). Note that the actual induction variable in the
568 loop (which ranges from base to final instead of from 0 to C) may
569 overflow, in which case BNDS.up will not be giving a correct upper
570 bound on C; thus, BNDS_U_VALID had to be computed in advance. */
572 exit_must_be_taken = true;
575 /* If the induction variable can overflow, the number of iterations is at
576 most the period of the control variable (or infinite, but in that case
577 the whole # of iterations analysis will fail). */
580 max = double_int_mask (TYPE_PRECISION (TREE_TYPE (c))
581 - tree_low_cst (num_ending_zeros (s), 1));
582 mpz_set_double_int (bnd, max, true);
586 /* Now we know that the induction variable does not overflow, so the loop
587 iterates at most (range of type / S) times. */
588 mpz_set_double_int (bnd, double_int_mask (TYPE_PRECISION (TREE_TYPE (c))),
591 /* If the induction variable is guaranteed to reach the value of C before
593 if (exit_must_be_taken)
595 /* ... then we can strenghten this to C / S, and possibly we can use
596 the upper bound on C given by BNDS. */
597 if (TREE_CODE (c) == INTEGER_CST)
598 mpz_set_double_int (bnd, tree_to_double_int (c), true);
599 else if (bnds_u_valid)
600 mpz_set (bnd, bnds->up);
604 mpz_set_double_int (d, tree_to_double_int (s), true);
605 mpz_fdiv_q (bnd, bnd, d);
609 /* Determines number of iterations of loop whose ending condition
610 is IV <> FINAL. TYPE is the type of the iv. The number of
611 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
612 we know that the exit must be taken eventually, i.e., that the IV
613 ever reaches the value FINAL (we derived this earlier, and possibly set
614 NITER->assumptions to make sure this is the case). BNDS contains the
615 bounds on the difference FINAL - IV->base. */
618 number_of_iterations_ne (tree type, affine_iv *iv, tree final,
619 struct tree_niter_desc *niter, bool exit_must_be_taken,
622 tree niter_type = unsigned_type_for (type);
623 tree s, c, d, bits, assumption, tmp, bound;
626 niter->control = *iv;
627 niter->bound = final;
628 niter->cmp = NE_EXPR;
630 /* Rearrange the terms so that we get inequality S * i <> C, with S
631 positive. Also cast everything to the unsigned type. If IV does
632 not overflow, BNDS bounds the value of C. Also, this is the
633 case if the computation |FINAL - IV->base| does not overflow, i.e.,
634 if BNDS->below in the result is nonnegative. */
635 if (tree_int_cst_sign_bit (iv->step))
637 s = fold_convert (niter_type,
638 fold_build1 (NEGATE_EXPR, type, iv->step));
639 c = fold_build2 (MINUS_EXPR, niter_type,
640 fold_convert (niter_type, iv->base),
641 fold_convert (niter_type, final));
642 bounds_negate (bnds);
646 s = fold_convert (niter_type, iv->step);
647 c = fold_build2 (MINUS_EXPR, niter_type,
648 fold_convert (niter_type, final),
649 fold_convert (niter_type, iv->base));
653 number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds,
655 niter->max = mpz_get_double_int (niter_type, max, false);
658 /* First the trivial cases -- when the step is 1. */
659 if (integer_onep (s))
665 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
666 is infinite. Otherwise, the number of iterations is
667 (inverse(s/d) * (c/d)) mod (size of mode/d). */
668 bits = num_ending_zeros (s);
669 bound = build_low_bits_mask (niter_type,
670 (TYPE_PRECISION (niter_type)
671 - tree_low_cst (bits, 1)));
673 d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
674 build_int_cst (niter_type, 1), bits);
675 s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
677 if (!exit_must_be_taken)
679 /* If we cannot assume that the exit is taken eventually, record the
680 assumptions for divisibility of c. */
681 assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d);
682 assumption = fold_build2 (EQ_EXPR, boolean_type_node,
683 assumption, build_int_cst (niter_type, 0));
684 if (!integer_nonzerop (assumption))
685 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
686 niter->assumptions, assumption);
689 c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d);
690 tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound));
691 niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound);
695 /* Checks whether we can determine the final value of the control variable
696 of the loop with ending condition IV0 < IV1 (computed in TYPE).
697 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
698 of the step. The assumptions necessary to ensure that the computation
699 of the final value does not overflow are recorded in NITER. If we
700 find the final value, we adjust DELTA and return TRUE. Otherwise
701 we return false. BNDS bounds the value of IV1->base - IV0->base,
702 and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
703 true if we know that the exit must be taken eventually. */
706 number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1,
707 struct tree_niter_desc *niter,
708 tree *delta, tree step,
709 bool exit_must_be_taken, bounds *bnds)
711 tree niter_type = TREE_TYPE (step);
712 tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step);
715 tree assumption = boolean_true_node, bound, noloop;
716 bool ret = false, fv_comp_no_overflow;
718 if (POINTER_TYPE_P (type))
721 if (TREE_CODE (mod) != INTEGER_CST)
723 if (integer_nonzerop (mod))
724 mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
725 tmod = fold_convert (type1, mod);
728 mpz_set_double_int (mmod, tree_to_double_int (mod), true);
729 mpz_neg (mmod, mmod);
731 /* If the induction variable does not overflow and the exit is taken,
732 then the computation of the final value does not overflow. This is
733 also obviously the case if the new final value is equal to the
734 current one. Finally, we postulate this for pointer type variables,
735 as the code cannot rely on the object to that the pointer points being
736 placed at the end of the address space (and more pragmatically,
737 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
738 if (integer_zerop (mod) || POINTER_TYPE_P (type))
739 fv_comp_no_overflow = true;
740 else if (!exit_must_be_taken)
741 fv_comp_no_overflow = false;
743 fv_comp_no_overflow =
744 (iv0->no_overflow && integer_nonzerop (iv0->step))
745 || (iv1->no_overflow && integer_nonzerop (iv1->step));
747 if (integer_nonzerop (iv0->step))
749 /* The final value of the iv is iv1->base + MOD, assuming that this
750 computation does not overflow, and that
751 iv0->base <= iv1->base + MOD. */
752 if (!fv_comp_no_overflow)
754 bound = fold_build2 (MINUS_EXPR, type1,
755 TYPE_MAX_VALUE (type1), tmod);
756 assumption = fold_build2 (LE_EXPR, boolean_type_node,
758 if (integer_zerop (assumption))
761 if (mpz_cmp (mmod, bnds->below) < 0)
762 noloop = boolean_false_node;
763 else if (POINTER_TYPE_P (type))
764 noloop = fold_build2 (GT_EXPR, boolean_type_node,
766 fold_build2 (POINTER_PLUS_EXPR, type,
769 noloop = fold_build2 (GT_EXPR, boolean_type_node,
771 fold_build2 (PLUS_EXPR, type1,
776 /* The final value of the iv is iv0->base - MOD, assuming that this
777 computation does not overflow, and that
778 iv0->base - MOD <= iv1->base. */
779 if (!fv_comp_no_overflow)
781 bound = fold_build2 (PLUS_EXPR, type1,
782 TYPE_MIN_VALUE (type1), tmod);
783 assumption = fold_build2 (GE_EXPR, boolean_type_node,
785 if (integer_zerop (assumption))
788 if (mpz_cmp (mmod, bnds->below) < 0)
789 noloop = boolean_false_node;
790 else if (POINTER_TYPE_P (type))
791 noloop = fold_build2 (GT_EXPR, boolean_type_node,
792 fold_build2 (POINTER_PLUS_EXPR, type,
794 fold_build1 (NEGATE_EXPR,
798 noloop = fold_build2 (GT_EXPR, boolean_type_node,
799 fold_build2 (MINUS_EXPR, type1,
804 if (!integer_nonzerop (assumption))
805 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
808 if (!integer_zerop (noloop))
809 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
812 bounds_add (bnds, tree_to_double_int (mod), type);
813 *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod);
821 /* Add assertions to NITER that ensure that the control variable of the loop
822 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
823 are TYPE. Returns false if we can prove that there is an overflow, true
824 otherwise. STEP is the absolute value of the step. */
827 assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
828 struct tree_niter_desc *niter, tree step)
830 tree bound, d, assumption, diff;
831 tree niter_type = TREE_TYPE (step);
833 if (integer_nonzerop (iv0->step))
835 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
836 if (iv0->no_overflow)
839 /* If iv0->base is a constant, we can determine the last value before
840 overflow precisely; otherwise we conservatively assume
843 if (TREE_CODE (iv0->base) == INTEGER_CST)
845 d = fold_build2 (MINUS_EXPR, niter_type,
846 fold_convert (niter_type, TYPE_MAX_VALUE (type)),
847 fold_convert (niter_type, iv0->base));
848 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
851 diff = fold_build2 (MINUS_EXPR, niter_type, step,
852 build_int_cst (niter_type, 1));
853 bound = fold_build2 (MINUS_EXPR, type,
854 TYPE_MAX_VALUE (type), fold_convert (type, diff));
855 assumption = fold_build2 (LE_EXPR, boolean_type_node,
860 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
861 if (iv1->no_overflow)
864 if (TREE_CODE (iv1->base) == INTEGER_CST)
866 d = fold_build2 (MINUS_EXPR, niter_type,
867 fold_convert (niter_type, iv1->base),
868 fold_convert (niter_type, TYPE_MIN_VALUE (type)));
869 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
872 diff = fold_build2 (MINUS_EXPR, niter_type, step,
873 build_int_cst (niter_type, 1));
874 bound = fold_build2 (PLUS_EXPR, type,
875 TYPE_MIN_VALUE (type), fold_convert (type, diff));
876 assumption = fold_build2 (GE_EXPR, boolean_type_node,
880 if (integer_zerop (assumption))
882 if (!integer_nonzerop (assumption))
883 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
884 niter->assumptions, assumption);
886 iv0->no_overflow = true;
887 iv1->no_overflow = true;
891 /* Add an assumption to NITER that a loop whose ending condition
892 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
893 bounds the value of IV1->base - IV0->base. */
896 assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
897 struct tree_niter_desc *niter, bounds *bnds)
899 tree assumption = boolean_true_node, bound, diff;
900 tree mbz, mbzl, mbzr, type1;
901 bool rolls_p, no_overflow_p;
905 /* We are going to compute the number of iterations as
906 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
907 variant of TYPE. This formula only works if
909 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
911 (where MAX is the maximum value of the unsigned variant of TYPE, and
912 the computations in this formula are performed in full precision,
913 i.e., without overflows).
915 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
916 we have a condition of the form iv0->base - step < iv1->base before the loop,
917 and for loops iv0->base < iv1->base - step * i the condition
918 iv0->base < iv1->base + step, due to loop header copying, which enable us
919 to prove the lower bound.
921 The upper bound is more complicated. Unless the expressions for initial
922 and final value themselves contain enough information, we usually cannot
923 derive it from the context. */
925 /* First check whether the answer does not follow from the bounds we gathered
927 if (integer_nonzerop (iv0->step))
928 dstep = tree_to_double_int (iv0->step);
931 dstep = double_int_sext (tree_to_double_int (iv1->step),
932 TYPE_PRECISION (type));
933 dstep = double_int_neg (dstep);
937 mpz_set_double_int (mstep, dstep, true);
938 mpz_neg (mstep, mstep);
939 mpz_add_ui (mstep, mstep, 1);
941 rolls_p = mpz_cmp (mstep, bnds->below) <= 0;
944 mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true);
945 mpz_add (max, max, mstep);
946 no_overflow_p = (mpz_cmp (bnds->up, max) <= 0
947 /* For pointers, only values lying inside a single object
948 can be compared or manipulated by pointer arithmetics.
949 Gcc in general does not allow or handle objects larger
950 than half of the address space, hence the upper bound
951 is satisfied for pointers. */
952 || POINTER_TYPE_P (type));
956 if (rolls_p && no_overflow_p)
960 if (POINTER_TYPE_P (type))
963 /* Now the hard part; we must formulate the assumption(s) as expressions, and
964 we must be careful not to introduce overflow. */
966 if (integer_nonzerop (iv0->step))
968 diff = fold_build2 (MINUS_EXPR, type1,
969 iv0->step, build_int_cst (type1, 1));
971 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
972 0 address never belongs to any object, we can assume this for
974 if (!POINTER_TYPE_P (type))
976 bound = fold_build2 (PLUS_EXPR, type1,
977 TYPE_MIN_VALUE (type), diff);
978 assumption = fold_build2 (GE_EXPR, boolean_type_node,
982 /* And then we can compute iv0->base - diff, and compare it with
984 mbzl = fold_build2 (MINUS_EXPR, type1,
985 fold_convert (type1, iv0->base), diff);
986 mbzr = fold_convert (type1, iv1->base);
990 diff = fold_build2 (PLUS_EXPR, type1,
991 iv1->step, build_int_cst (type1, 1));
993 if (!POINTER_TYPE_P (type))
995 bound = fold_build2 (PLUS_EXPR, type1,
996 TYPE_MAX_VALUE (type), diff);
997 assumption = fold_build2 (LE_EXPR, boolean_type_node,
1001 mbzl = fold_convert (type1, iv0->base);
1002 mbzr = fold_build2 (MINUS_EXPR, type1,
1003 fold_convert (type1, iv1->base), diff);
1006 if (!integer_nonzerop (assumption))
1007 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1008 niter->assumptions, assumption);
1011 mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr);
1012 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
1013 niter->may_be_zero, mbz);
1017 /* Determines number of iterations of loop whose ending condition
1018 is IV0 < IV1. TYPE is the type of the iv. The number of
1019 iterations is stored to NITER. BNDS bounds the difference
1020 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
1021 that the exit must be taken eventually. */
1024 number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
1025 struct tree_niter_desc *niter,
1026 bool exit_must_be_taken, bounds *bnds)
1028 tree niter_type = unsigned_type_for (type);
1029 tree delta, step, s;
1032 if (integer_nonzerop (iv0->step))
1034 niter->control = *iv0;
1035 niter->cmp = LT_EXPR;
1036 niter->bound = iv1->base;
1040 niter->control = *iv1;
1041 niter->cmp = GT_EXPR;
1042 niter->bound = iv0->base;
1045 delta = fold_build2 (MINUS_EXPR, niter_type,
1046 fold_convert (niter_type, iv1->base),
1047 fold_convert (niter_type, iv0->base));
1049 /* First handle the special case that the step is +-1. */
1050 if ((integer_onep (iv0->step) && integer_zerop (iv1->step))
1051 || (integer_all_onesp (iv1->step) && integer_zerop (iv0->step)))
1053 /* for (i = iv0->base; i < iv1->base; i++)
1057 for (i = iv1->base; i > iv0->base; i--).
1059 In both cases # of iterations is iv1->base - iv0->base, assuming that
1060 iv1->base >= iv0->base.
1062 First try to derive a lower bound on the value of
1063 iv1->base - iv0->base, computed in full precision. If the difference
1064 is nonnegative, we are done, otherwise we must record the
1067 if (mpz_sgn (bnds->below) < 0)
1068 niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
1069 iv1->base, iv0->base);
1070 niter->niter = delta;
1071 niter->max = mpz_get_double_int (niter_type, bnds->up, false);
1075 if (integer_nonzerop (iv0->step))
1076 step = fold_convert (niter_type, iv0->step);
1078 step = fold_convert (niter_type,
1079 fold_build1 (NEGATE_EXPR, type, iv1->step));
1081 /* If we can determine the final value of the control iv exactly, we can
1082 transform the condition to != comparison. In particular, this will be
1083 the case if DELTA is constant. */
1084 if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step,
1085 exit_must_be_taken, bnds))
1089 zps.base = build_int_cst (niter_type, 0);
1091 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1092 zps does not overflow. */
1093 zps.no_overflow = true;
1095 return number_of_iterations_ne (type, &zps, delta, niter, true, bnds);
1098 /* Make sure that the control iv does not overflow. */
1099 if (!assert_no_overflow_lt (type, iv0, iv1, niter, step))
1102 /* We determine the number of iterations as (delta + step - 1) / step. For
1103 this to work, we must know that iv1->base >= iv0->base - step + 1,
1104 otherwise the loop does not roll. */
1105 assert_loop_rolls_lt (type, iv0, iv1, niter, bnds);
1107 s = fold_build2 (MINUS_EXPR, niter_type,
1108 step, build_int_cst (niter_type, 1));
1109 delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
1110 niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
1114 mpz_set_double_int (mstep, tree_to_double_int (step), true);
1115 mpz_add (tmp, bnds->up, mstep);
1116 mpz_sub_ui (tmp, tmp, 1);
1117 mpz_fdiv_q (tmp, tmp, mstep);
1118 niter->max = mpz_get_double_int (niter_type, tmp, false);
1125 /* Determines number of iterations of loop whose ending condition
1126 is IV0 <= IV1. TYPE is the type of the iv. The number of
1127 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
1128 we know that this condition must eventually become false (we derived this
1129 earlier, and possibly set NITER->assumptions to make sure this
1130 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1133 number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1,
1134 struct tree_niter_desc *niter, bool exit_must_be_taken,
1139 if (POINTER_TYPE_P (type))
1142 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1143 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1144 value of the type. This we must know anyway, since if it is
1145 equal to this value, the loop rolls forever. We do not check
1146 this condition for pointer type ivs, as the code cannot rely on
1147 the object to that the pointer points being placed at the end of
1148 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1149 not defined for pointers). */
1151 if (!exit_must_be_taken && !POINTER_TYPE_P (type))
1153 if (integer_nonzerop (iv0->step))
1154 assumption = fold_build2 (NE_EXPR, boolean_type_node,
1155 iv1->base, TYPE_MAX_VALUE (type));
1157 assumption = fold_build2 (NE_EXPR, boolean_type_node,
1158 iv0->base, TYPE_MIN_VALUE (type));
1160 if (integer_zerop (assumption))
1162 if (!integer_nonzerop (assumption))
1163 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1164 niter->assumptions, assumption);
1167 if (integer_nonzerop (iv0->step))
1169 if (POINTER_TYPE_P (type))
1170 iv1->base = fold_build2 (POINTER_PLUS_EXPR, type, iv1->base,
1171 build_int_cst (type1, 1));
1173 iv1->base = fold_build2 (PLUS_EXPR, type1, iv1->base,
1174 build_int_cst (type1, 1));
1176 else if (POINTER_TYPE_P (type))
1177 iv0->base = fold_build2 (POINTER_PLUS_EXPR, type, iv0->base,
1178 fold_build1 (NEGATE_EXPR, type1,
1179 build_int_cst (type1, 1)));
1181 iv0->base = fold_build2 (MINUS_EXPR, type1,
1182 iv0->base, build_int_cst (type1, 1));
1184 bounds_add (bnds, double_int_one, type1);
1186 return number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken,
1190 /* Dumps description of affine induction variable IV to FILE. */
1193 dump_affine_iv (FILE *file, affine_iv *iv)
1195 if (!integer_zerop (iv->step))
1196 fprintf (file, "[");
1198 print_generic_expr (dump_file, iv->base, TDF_SLIM);
1200 if (!integer_zerop (iv->step))
1202 fprintf (file, ", + , ");
1203 print_generic_expr (dump_file, iv->step, TDF_SLIM);
1204 fprintf (file, "]%s", iv->no_overflow ? "(no_overflow)" : "");
1208 /* Determine the number of iterations according to condition (for staying
1209 inside loop) which compares two induction variables using comparison
1210 operator CODE. The induction variable on left side of the comparison
1211 is IV0, the right-hand side is IV1. Both induction variables must have
1212 type TYPE, which must be an integer or pointer type. The steps of the
1213 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1215 LOOP is the loop whose number of iterations we are determining.
1217 ONLY_EXIT is true if we are sure this is the only way the loop could be
1218 exited (including possibly non-returning function calls, exceptions, etc.)
1219 -- in this case we can use the information whether the control induction
1220 variables can overflow or not in a more efficient way.
1222 The results (number of iterations and assumptions as described in
1223 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
1224 Returns false if it fails to determine number of iterations, true if it
1225 was determined (possibly with some assumptions). */
1228 number_of_iterations_cond (struct loop *loop,
1229 tree type, affine_iv *iv0, enum tree_code code,
1230 affine_iv *iv1, struct tree_niter_desc *niter,
1233 bool exit_must_be_taken = false, ret;
1236 /* The meaning of these assumptions is this:
1238 then the rest of information does not have to be valid
1239 if may_be_zero then the loop does not roll, even if
1241 niter->assumptions = boolean_true_node;
1242 niter->may_be_zero = boolean_false_node;
1243 niter->niter = NULL_TREE;
1244 niter->max = double_int_zero;
1246 niter->bound = NULL_TREE;
1247 niter->cmp = ERROR_MARK;
1249 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1250 the control variable is on lhs. */
1251 if (code == GE_EXPR || code == GT_EXPR
1252 || (code == NE_EXPR && integer_zerop (iv0->step)))
1255 code = swap_tree_comparison (code);
1258 if (POINTER_TYPE_P (type))
1260 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1261 to the same object. If they do, the control variable cannot wrap
1262 (as wrap around the bounds of memory will never return a pointer
1263 that would be guaranteed to point to the same object, even if we
1264 avoid undefined behavior by casting to size_t and back). */
1265 iv0->no_overflow = true;
1266 iv1->no_overflow = true;
1269 /* If the control induction variable does not overflow and the only exit
1270 from the loop is the one that we analyze, we know it must be taken
1274 if (!integer_zerop (iv0->step) && iv0->no_overflow)
1275 exit_must_be_taken = true;
1276 else if (!integer_zerop (iv1->step) && iv1->no_overflow)
1277 exit_must_be_taken = true;
1280 /* We can handle the case when neither of the sides of the comparison is
1281 invariant, provided that the test is NE_EXPR. This rarely occurs in
1282 practice, but it is simple enough to manage. */
1283 if (!integer_zerop (iv0->step) && !integer_zerop (iv1->step))
1285 if (code != NE_EXPR)
1288 iv0->step = fold_binary_to_constant (MINUS_EXPR, type,
1289 iv0->step, iv1->step);
1290 iv0->no_overflow = false;
1291 iv1->step = build_int_cst (type, 0);
1292 iv1->no_overflow = true;
1295 /* If the result of the comparison is a constant, the loop is weird. More
1296 precise handling would be possible, but the situation is not common enough
1297 to waste time on it. */
1298 if (integer_zerop (iv0->step) && integer_zerop (iv1->step))
1301 /* Ignore loops of while (i-- < 10) type. */
1302 if (code != NE_EXPR)
1304 if (iv0->step && tree_int_cst_sign_bit (iv0->step))
1307 if (!integer_zerop (iv1->step) && !tree_int_cst_sign_bit (iv1->step))
1311 /* If the loop exits immediately, there is nothing to do. */
1312 if (integer_zerop (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
1314 niter->niter = build_int_cst (unsigned_type_for (type), 0);
1315 niter->max = double_int_zero;
1319 /* OK, now we know we have a senseful loop. Handle several cases, depending
1320 on what comparison operator is used. */
1321 bound_difference (loop, iv1->base, iv0->base, &bnds);
1323 if (dump_file && (dump_flags & TDF_DETAILS))
1326 "Analyzing # of iterations of loop %d\n", loop->num);
1328 fprintf (dump_file, " exit condition ");
1329 dump_affine_iv (dump_file, iv0);
1330 fprintf (dump_file, " %s ",
1331 code == NE_EXPR ? "!="
1332 : code == LT_EXPR ? "<"
1334 dump_affine_iv (dump_file, iv1);
1335 fprintf (dump_file, "\n");
1337 fprintf (dump_file, " bounds on difference of bases: ");
1338 mpz_out_str (dump_file, 10, bnds.below);
1339 fprintf (dump_file, " ... ");
1340 mpz_out_str (dump_file, 10, bnds.up);
1341 fprintf (dump_file, "\n");
1347 gcc_assert (integer_zerop (iv1->step));
1348 ret = number_of_iterations_ne (type, iv0, iv1->base, niter,
1349 exit_must_be_taken, &bnds);
1353 ret = number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken,
1358 ret = number_of_iterations_le (type, iv0, iv1, niter, exit_must_be_taken,
1366 mpz_clear (bnds.up);
1367 mpz_clear (bnds.below);
1369 if (dump_file && (dump_flags & TDF_DETAILS))
1373 fprintf (dump_file, " result:\n");
1374 if (!integer_nonzerop (niter->assumptions))
1376 fprintf (dump_file, " under assumptions ");
1377 print_generic_expr (dump_file, niter->assumptions, TDF_SLIM);
1378 fprintf (dump_file, "\n");
1381 if (!integer_zerop (niter->may_be_zero))
1383 fprintf (dump_file, " zero if ");
1384 print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
1385 fprintf (dump_file, "\n");
1388 fprintf (dump_file, " # of iterations ");
1389 print_generic_expr (dump_file, niter->niter, TDF_SLIM);
1390 fprintf (dump_file, ", bounded by ");
1391 dump_double_int (dump_file, niter->max, true);
1392 fprintf (dump_file, "\n");
1395 fprintf (dump_file, " failed\n\n");
1400 /* Substitute NEW for OLD in EXPR and fold the result. */
1403 simplify_replace_tree (tree expr, tree old, tree new_tree)
1406 tree ret = NULL_TREE, e, se;
1411 /* Do not bother to replace constants. */
1412 if (CONSTANT_CLASS_P (old))
1416 || operand_equal_p (expr, old, 0))
1417 return unshare_expr (new_tree);
1422 n = TREE_OPERAND_LENGTH (expr);
1423 for (i = 0; i < n; i++)
1425 e = TREE_OPERAND (expr, i);
1426 se = simplify_replace_tree (e, old, new_tree);
1431 ret = copy_node (expr);
1433 TREE_OPERAND (ret, i) = se;
1436 return (ret ? fold (ret) : expr);
1439 /* Expand definitions of ssa names in EXPR as long as they are simple
1440 enough, and return the new expression. */
1443 expand_simple_operations (tree expr)
1446 tree ret = NULL_TREE, e, ee, e1;
1447 enum tree_code code;
1450 if (expr == NULL_TREE)
1453 if (is_gimple_min_invariant (expr))
1456 code = TREE_CODE (expr);
1457 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
1459 n = TREE_OPERAND_LENGTH (expr);
1460 for (i = 0; i < n; i++)
1462 e = TREE_OPERAND (expr, i);
1463 ee = expand_simple_operations (e);
1468 ret = copy_node (expr);
1470 TREE_OPERAND (ret, i) = ee;
1476 fold_defer_overflow_warnings ();
1478 fold_undefer_and_ignore_overflow_warnings ();
1482 if (TREE_CODE (expr) != SSA_NAME)
1485 stmt = SSA_NAME_DEF_STMT (expr);
1486 if (gimple_code (stmt) == GIMPLE_PHI)
1488 basic_block src, dest;
1490 if (gimple_phi_num_args (stmt) != 1)
1492 e = PHI_ARG_DEF (stmt, 0);
1494 /* Avoid propagating through loop exit phi nodes, which
1495 could break loop-closed SSA form restrictions. */
1496 dest = gimple_bb (stmt);
1497 src = single_pred (dest);
1498 if (TREE_CODE (e) == SSA_NAME
1499 && src->loop_father != dest->loop_father)
1502 return expand_simple_operations (e);
1504 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1507 e = gimple_assign_rhs1 (stmt);
1508 code = gimple_assign_rhs_code (stmt);
1509 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1511 if (is_gimple_min_invariant (e))
1514 if (code == SSA_NAME)
1515 return expand_simple_operations (e);
1523 /* Casts are simple. */
1524 ee = expand_simple_operations (e);
1525 return fold_build1 (code, TREE_TYPE (expr), ee);
1529 case POINTER_PLUS_EXPR:
1530 /* And increments and decrements by a constant are simple. */
1531 e1 = gimple_assign_rhs2 (stmt);
1532 if (!is_gimple_min_invariant (e1))
1535 ee = expand_simple_operations (e);
1536 return fold_build2 (code, TREE_TYPE (expr), ee, e1);
1543 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1544 expression (or EXPR unchanged, if no simplification was possible). */
1547 tree_simplify_using_condition_1 (tree cond, tree expr)
1550 tree e, te, e0, e1, e2, notcond;
1551 enum tree_code code = TREE_CODE (expr);
1553 if (code == INTEGER_CST)
1556 if (code == TRUTH_OR_EXPR
1557 || code == TRUTH_AND_EXPR
1558 || code == COND_EXPR)
1562 e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0));
1563 if (TREE_OPERAND (expr, 0) != e0)
1566 e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1));
1567 if (TREE_OPERAND (expr, 1) != e1)
1570 if (code == COND_EXPR)
1572 e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2));
1573 if (TREE_OPERAND (expr, 2) != e2)
1581 if (code == COND_EXPR)
1582 expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
1584 expr = fold_build2 (code, boolean_type_node, e0, e1);
1590 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
1591 propagation, and vice versa. Fold does not handle this, since it is
1592 considered too expensive. */
1593 if (TREE_CODE (cond) == EQ_EXPR)
1595 e0 = TREE_OPERAND (cond, 0);
1596 e1 = TREE_OPERAND (cond, 1);
1598 /* We know that e0 == e1. Check whether we cannot simplify expr
1600 e = simplify_replace_tree (expr, e0, e1);
1601 if (integer_zerop (e) || integer_nonzerop (e))
1604 e = simplify_replace_tree (expr, e1, e0);
1605 if (integer_zerop (e) || integer_nonzerop (e))
1608 if (TREE_CODE (expr) == EQ_EXPR)
1610 e0 = TREE_OPERAND (expr, 0);
1611 e1 = TREE_OPERAND (expr, 1);
1613 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
1614 e = simplify_replace_tree (cond, e0, e1);
1615 if (integer_zerop (e))
1617 e = simplify_replace_tree (cond, e1, e0);
1618 if (integer_zerop (e))
1621 if (TREE_CODE (expr) == NE_EXPR)
1623 e0 = TREE_OPERAND (expr, 0);
1624 e1 = TREE_OPERAND (expr, 1);
1626 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
1627 e = simplify_replace_tree (cond, e0, e1);
1628 if (integer_zerop (e))
1629 return boolean_true_node;
1630 e = simplify_replace_tree (cond, e1, e0);
1631 if (integer_zerop (e))
1632 return boolean_true_node;
1635 te = expand_simple_operations (expr);
1637 /* Check whether COND ==> EXPR. */
1638 notcond = invert_truthvalue (cond);
1639 e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te);
1640 if (e && integer_nonzerop (e))
1643 /* Check whether COND ==> not EXPR. */
1644 e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te);
1645 if (e && integer_zerop (e))
1651 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1652 expression (or EXPR unchanged, if no simplification was possible).
1653 Wrapper around tree_simplify_using_condition_1 that ensures that chains
1654 of simple operations in definitions of ssa names in COND are expanded,
1655 so that things like casts or incrementing the value of the bound before
1656 the loop do not cause us to fail. */
1659 tree_simplify_using_condition (tree cond, tree expr)
1661 cond = expand_simple_operations (cond);
1663 return tree_simplify_using_condition_1 (cond, expr);
1666 /* Tries to simplify EXPR using the conditions on entry to LOOP.
1667 Returns the simplified expression (or EXPR unchanged, if no
1668 simplification was possible).*/
1671 simplify_using_initial_conditions (struct loop *loop, tree expr)
1679 if (TREE_CODE (expr) == INTEGER_CST)
1682 /* Limit walking the dominators to avoid quadraticness in
1683 the number of BBs times the number of loops in degenerate
1685 for (bb = loop->header;
1686 bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK;
1687 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1689 if (!single_pred_p (bb))
1691 e = single_pred_edge (bb);
1693 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
1696 stmt = last_stmt (e->src);
1697 cond = fold_build2 (gimple_cond_code (stmt),
1699 gimple_cond_lhs (stmt),
1700 gimple_cond_rhs (stmt));
1701 if (e->flags & EDGE_FALSE_VALUE)
1702 cond = invert_truthvalue (cond);
1703 expr = tree_simplify_using_condition (cond, expr);
1710 /* Tries to simplify EXPR using the evolutions of the loop invariants
1711 in the superloops of LOOP. Returns the simplified expression
1712 (or EXPR unchanged, if no simplification was possible). */
1715 simplify_using_outer_evolutions (struct loop *loop, tree expr)
1717 enum tree_code code = TREE_CODE (expr);
1721 if (is_gimple_min_invariant (expr))
1724 if (code == TRUTH_OR_EXPR
1725 || code == TRUTH_AND_EXPR
1726 || code == COND_EXPR)
1730 e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
1731 if (TREE_OPERAND (expr, 0) != e0)
1734 e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
1735 if (TREE_OPERAND (expr, 1) != e1)
1738 if (code == COND_EXPR)
1740 e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
1741 if (TREE_OPERAND (expr, 2) != e2)
1749 if (code == COND_EXPR)
1750 expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
1752 expr = fold_build2 (code, boolean_type_node, e0, e1);
1758 e = instantiate_parameters (loop, expr);
1759 if (is_gimple_min_invariant (e))
1765 /* Returns true if EXIT is the only possible exit from LOOP. */
1768 loop_only_exit_p (const struct loop *loop, const_edge exit)
1771 gimple_stmt_iterator bsi;
1775 if (exit != single_exit (loop))
1778 body = get_loop_body (loop);
1779 for (i = 0; i < loop->num_nodes; i++)
1781 for (bsi = gsi_start_bb (body[i]); !gsi_end_p (bsi); gsi_next (&bsi))
1783 call = gsi_stmt (bsi);
1784 if (gimple_code (call) != GIMPLE_CALL)
1787 if (gimple_has_side_effects (call))
1799 /* Stores description of number of iterations of LOOP derived from
1800 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
1801 useful information could be derived (and fields of NITER has
1802 meaning described in comments at struct tree_niter_desc
1803 declaration), false otherwise. If WARN is true and
1804 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1805 potentially unsafe assumptions. */
1808 number_of_iterations_exit (struct loop *loop, edge exit,
1809 struct tree_niter_desc *niter,
1815 enum tree_code code;
1818 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
1821 niter->assumptions = boolean_false_node;
1822 stmt = last_stmt (exit->src);
1823 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
1826 /* We want the condition for staying inside loop. */
1827 code = gimple_cond_code (stmt);
1828 if (exit->flags & EDGE_TRUE_VALUE)
1829 code = invert_tree_comparison (code, false);
1844 op0 = gimple_cond_lhs (stmt);
1845 op1 = gimple_cond_rhs (stmt);
1846 type = TREE_TYPE (op0);
1848 if (TREE_CODE (type) != INTEGER_TYPE
1849 && !POINTER_TYPE_P (type))
1852 if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, false))
1854 if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, false))
1857 /* We don't want to see undefined signed overflow warnings while
1858 computing the number of iterations. */
1859 fold_defer_overflow_warnings ();
1861 iv0.base = expand_simple_operations (iv0.base);
1862 iv1.base = expand_simple_operations (iv1.base);
1863 if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter,
1864 loop_only_exit_p (loop, exit)))
1866 fold_undefer_and_ignore_overflow_warnings ();
1872 niter->assumptions = simplify_using_outer_evolutions (loop,
1873 niter->assumptions);
1874 niter->may_be_zero = simplify_using_outer_evolutions (loop,
1875 niter->may_be_zero);
1876 niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
1880 = simplify_using_initial_conditions (loop,
1881 niter->assumptions);
1883 = simplify_using_initial_conditions (loop,
1884 niter->may_be_zero);
1886 fold_undefer_and_ignore_overflow_warnings ();
1888 if (integer_onep (niter->assumptions))
1891 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1892 But if we can prove that there is overflow or some other source of weird
1893 behavior, ignore the loop even with -funsafe-loop-optimizations. */
1894 if (integer_zerop (niter->assumptions))
1897 if (flag_unsafe_loop_optimizations)
1898 niter->assumptions = boolean_true_node;
1902 const char *wording;
1903 location_t loc = gimple_location (stmt);
1905 /* We can provide a more specific warning if one of the operator is
1906 constant and the other advances by +1 or -1. */
1907 if (!integer_zerop (iv1.step)
1908 ? (integer_zerop (iv0.step)
1909 && (integer_onep (iv1.step) || integer_all_onesp (iv1.step)))
1910 : (integer_onep (iv0.step) || integer_all_onesp (iv0.step)))
1912 flag_unsafe_loop_optimizations
1913 ? N_("assuming that the loop is not infinite")
1914 : N_("cannot optimize possibly infinite loops");
1917 flag_unsafe_loop_optimizations
1918 ? N_("assuming that the loop counter does not overflow")
1919 : N_("cannot optimize loop, the loop counter may overflow");
1921 warning_at ((LOCATION_LINE (loc) > 0) ? loc : input_location,
1922 OPT_Wunsafe_loop_optimizations, "%s", gettext (wording));
1925 return flag_unsafe_loop_optimizations;
1928 /* Try to determine the number of iterations of LOOP. If we succeed,
1929 expression giving number of iterations is returned and *EXIT is
1930 set to the edge from that the information is obtained. Otherwise
1931 chrec_dont_know is returned. */
1934 find_loop_niter (struct loop *loop, edge *exit)
1937 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1939 tree niter = NULL_TREE, aniter;
1940 struct tree_niter_desc desc;
1943 FOR_EACH_VEC_ELT (edge, exits, i, ex)
1945 if (!just_once_each_iteration_p (loop, ex->src))
1948 if (!number_of_iterations_exit (loop, ex, &desc, false))
1951 if (integer_nonzerop (desc.may_be_zero))
1953 /* We exit in the first iteration through this exit.
1954 We won't find anything better. */
1955 niter = build_int_cst (unsigned_type_node, 0);
1960 if (!integer_zerop (desc.may_be_zero))
1963 aniter = desc.niter;
1967 /* Nothing recorded yet. */
1973 /* Prefer constants, the lower the better. */
1974 if (TREE_CODE (aniter) != INTEGER_CST)
1977 if (TREE_CODE (niter) != INTEGER_CST)
1984 if (tree_int_cst_lt (aniter, niter))
1991 VEC_free (edge, heap, exits);
1993 return niter ? niter : chrec_dont_know;
1996 /* Return true if loop is known to have bounded number of iterations. */
1999 finite_loop_p (struct loop *loop)
2002 VEC (edge, heap) *exits;
2004 struct tree_niter_desc desc;
2005 bool finite = false;
2008 if (flag_unsafe_loop_optimizations)
2010 flags = flags_from_decl_or_type (current_function_decl);
2011 if ((flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE))
2013 if (dump_file && (dump_flags & TDF_DETAILS))
2014 fprintf (dump_file, "Found loop %i to be finite: it is within pure or const function.\n",
2019 exits = get_loop_exit_edges (loop);
2020 FOR_EACH_VEC_ELT (edge, exits, i, ex)
2022 if (!just_once_each_iteration_p (loop, ex->src))
2025 if (number_of_iterations_exit (loop, ex, &desc, false))
2027 if (dump_file && (dump_flags & TDF_DETAILS))
2029 fprintf (dump_file, "Found loop %i to be finite: iterating ", loop->num);
2030 print_generic_expr (dump_file, desc.niter, TDF_SLIM);
2031 fprintf (dump_file, " times\n");
2037 VEC_free (edge, heap, exits);
2043 Analysis of a number of iterations of a loop by a brute-force evaluation.
2047 /* Bound on the number of iterations we try to evaluate. */
2049 #define MAX_ITERATIONS_TO_TRACK \
2050 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
2052 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
2053 result by a chain of operations such that all but exactly one of their
2054 operands are constants. */
2057 chain_of_csts_start (struct loop *loop, tree x)
2059 gimple stmt = SSA_NAME_DEF_STMT (x);
2061 basic_block bb = gimple_bb (stmt);
2062 enum tree_code code;
2065 || !flow_bb_inside_loop_p (loop, bb))
2068 if (gimple_code (stmt) == GIMPLE_PHI)
2070 if (bb == loop->header)
2076 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2079 code = gimple_assign_rhs_code (stmt);
2080 if (gimple_references_memory_p (stmt)
2081 || TREE_CODE_CLASS (code) == tcc_reference
2082 || (code == ADDR_EXPR
2083 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
2086 use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
2087 if (use == NULL_TREE)
2090 return chain_of_csts_start (loop, use);
2093 /* Determines whether the expression X is derived from a result of a phi node
2094 in header of LOOP such that
2096 * the derivation of X consists only from operations with constants
2097 * the initial value of the phi node is constant
2098 * the value of the phi node in the next iteration can be derived from the
2099 value in the current iteration by a chain of operations with constants.
2101 If such phi node exists, it is returned, otherwise NULL is returned. */
2104 get_base_for (struct loop *loop, tree x)
2109 if (is_gimple_min_invariant (x))
2112 phi = chain_of_csts_start (loop, x);
2116 init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
2117 next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
2119 if (TREE_CODE (next) != SSA_NAME)
2122 if (!is_gimple_min_invariant (init))
2125 if (chain_of_csts_start (loop, next) != phi)
2131 /* Given an expression X, then
2133 * if X is NULL_TREE, we return the constant BASE.
2134 * otherwise X is a SSA name, whose value in the considered loop is derived
2135 by a chain of operations with constant from a result of a phi node in
2136 the header of the loop. Then we return value of X when the value of the
2137 result of this phi node is given by the constant BASE. */
2140 get_val_for (tree x, tree base)
2144 gcc_assert (is_gimple_min_invariant (base));
2149 stmt = SSA_NAME_DEF_STMT (x);
2150 if (gimple_code (stmt) == GIMPLE_PHI)
2153 gcc_assert (is_gimple_assign (stmt));
2155 /* STMT must be either an assignment of a single SSA name or an
2156 expression involving an SSA name and a constant. Try to fold that
2157 expression using the value for the SSA name. */
2158 if (gimple_assign_ssa_name_copy_p (stmt))
2159 return get_val_for (gimple_assign_rhs1 (stmt), base);
2160 else if (gimple_assign_rhs_class (stmt) == GIMPLE_UNARY_RHS
2161 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
2163 return fold_build1 (gimple_assign_rhs_code (stmt),
2164 gimple_expr_type (stmt),
2165 get_val_for (gimple_assign_rhs1 (stmt), base));
2167 else if (gimple_assign_rhs_class (stmt) == GIMPLE_BINARY_RHS)
2169 tree rhs1 = gimple_assign_rhs1 (stmt);
2170 tree rhs2 = gimple_assign_rhs2 (stmt);
2171 if (TREE_CODE (rhs1) == SSA_NAME)
2172 rhs1 = get_val_for (rhs1, base);
2173 else if (TREE_CODE (rhs2) == SSA_NAME)
2174 rhs2 = get_val_for (rhs2, base);
2177 return fold_build2 (gimple_assign_rhs_code (stmt),
2178 gimple_expr_type (stmt), rhs1, rhs2);
2185 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2186 by brute force -- i.e. by determining the value of the operands of the
2187 condition at EXIT in first few iterations of the loop (assuming that
2188 these values are constant) and determining the first one in that the
2189 condition is not satisfied. Returns the constant giving the number
2190 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
2193 loop_niter_by_eval (struct loop *loop, edge exit)
2196 tree op[2], val[2], next[2], aval[2];
2201 cond = last_stmt (exit->src);
2202 if (!cond || gimple_code (cond) != GIMPLE_COND)
2203 return chrec_dont_know;
2205 cmp = gimple_cond_code (cond);
2206 if (exit->flags & EDGE_TRUE_VALUE)
2207 cmp = invert_tree_comparison (cmp, false);
2217 op[0] = gimple_cond_lhs (cond);
2218 op[1] = gimple_cond_rhs (cond);
2222 return chrec_dont_know;
2225 for (j = 0; j < 2; j++)
2227 if (is_gimple_min_invariant (op[j]))
2230 next[j] = NULL_TREE;
2235 phi = get_base_for (loop, op[j]);
2237 return chrec_dont_know;
2238 val[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
2239 next[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
2243 /* Don't issue signed overflow warnings. */
2244 fold_defer_overflow_warnings ();
2246 for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
2248 for (j = 0; j < 2; j++)
2249 aval[j] = get_val_for (op[j], val[j]);
2251 acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]);
2252 if (acnd && integer_zerop (acnd))
2254 fold_undefer_and_ignore_overflow_warnings ();
2255 if (dump_file && (dump_flags & TDF_DETAILS))
2257 "Proved that loop %d iterates %d times using brute force.\n",
2259 return build_int_cst (unsigned_type_node, i);
2262 for (j = 0; j < 2; j++)
2264 val[j] = get_val_for (next[j], val[j]);
2265 if (!is_gimple_min_invariant (val[j]))
2267 fold_undefer_and_ignore_overflow_warnings ();
2268 return chrec_dont_know;
2273 fold_undefer_and_ignore_overflow_warnings ();
2275 return chrec_dont_know;
2278 /* Finds the exit of the LOOP by that the loop exits after a constant
2279 number of iterations and stores the exit edge to *EXIT. The constant
2280 giving the number of iterations of LOOP is returned. The number of
2281 iterations is determined using loop_niter_by_eval (i.e. by brute force
2282 evaluation). If we are unable to find the exit for that loop_niter_by_eval
2283 determines the number of iterations, chrec_dont_know is returned. */
2286 find_loop_niter_by_eval (struct loop *loop, edge *exit)
2289 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
2291 tree niter = NULL_TREE, aniter;
2295 /* Loops with multiple exits are expensive to handle and less important. */
2296 if (!flag_expensive_optimizations
2297 && VEC_length (edge, exits) > 1)
2298 return chrec_dont_know;
2300 FOR_EACH_VEC_ELT (edge, exits, i, ex)
2302 if (!just_once_each_iteration_p (loop, ex->src))
2305 aniter = loop_niter_by_eval (loop, ex);
2306 if (chrec_contains_undetermined (aniter))
2310 && !tree_int_cst_lt (aniter, niter))
2316 VEC_free (edge, heap, exits);
2318 return niter ? niter : chrec_dont_know;
2323 Analysis of upper bounds on number of iterations of a loop.
2327 static double_int derive_constant_upper_bound_ops (tree, tree,
2328 enum tree_code, tree);
2330 /* Returns a constant upper bound on the value of the right-hand side of
2331 an assignment statement STMT. */
2334 derive_constant_upper_bound_assign (gimple stmt)
2336 enum tree_code code = gimple_assign_rhs_code (stmt);
2337 tree op0 = gimple_assign_rhs1 (stmt);
2338 tree op1 = gimple_assign_rhs2 (stmt);
2340 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt)),
2344 /* Returns a constant upper bound on the value of expression VAL. VAL
2345 is considered to be unsigned. If its type is signed, its value must
2349 derive_constant_upper_bound (tree val)
2351 enum tree_code code;
2354 extract_ops_from_tree (val, &code, &op0, &op1);
2355 return derive_constant_upper_bound_ops (TREE_TYPE (val), op0, code, op1);
2358 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
2359 whose type is TYPE. The expression is considered to be unsigned. If
2360 its type is signed, its value must be nonnegative. */
2363 derive_constant_upper_bound_ops (tree type, tree op0,
2364 enum tree_code code, tree op1)
2367 double_int bnd, max, mmax, cst;
2370 if (INTEGRAL_TYPE_P (type))
2371 maxt = TYPE_MAX_VALUE (type);
2373 maxt = upper_bound_in_type (type, type);
2375 max = tree_to_double_int (maxt);
2380 return tree_to_double_int (op0);
2383 subtype = TREE_TYPE (op0);
2384 if (!TYPE_UNSIGNED (subtype)
2385 /* If TYPE is also signed, the fact that VAL is nonnegative implies
2386 that OP0 is nonnegative. */
2387 && TYPE_UNSIGNED (type)
2388 && !tree_expr_nonnegative_p (op0))
2390 /* If we cannot prove that the casted expression is nonnegative,
2391 we cannot establish more useful upper bound than the precision
2392 of the type gives us. */
2396 /* We now know that op0 is an nonnegative value. Try deriving an upper
2398 bnd = derive_constant_upper_bound (op0);
2400 /* If the bound does not fit in TYPE, max. value of TYPE could be
2402 if (double_int_ucmp (max, bnd) < 0)
2408 case POINTER_PLUS_EXPR:
2410 if (TREE_CODE (op1) != INTEGER_CST
2411 || !tree_expr_nonnegative_p (op0))
2414 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
2415 choose the most logical way how to treat this constant regardless
2416 of the signedness of the type. */
2417 cst = tree_to_double_int (op1);
2418 cst = double_int_sext (cst, TYPE_PRECISION (type));
2419 if (code != MINUS_EXPR)
2420 cst = double_int_neg (cst);
2422 bnd = derive_constant_upper_bound (op0);
2424 if (double_int_negative_p (cst))
2426 cst = double_int_neg (cst);
2427 /* Avoid CST == 0x80000... */
2428 if (double_int_negative_p (cst))
2431 /* OP0 + CST. We need to check that
2432 BND <= MAX (type) - CST. */
2434 mmax = double_int_sub (max, cst);
2435 if (double_int_ucmp (bnd, mmax) > 0)
2438 return double_int_add (bnd, cst);
2442 /* OP0 - CST, where CST >= 0.
2444 If TYPE is signed, we have already verified that OP0 >= 0, and we
2445 know that the result is nonnegative. This implies that
2448 If TYPE is unsigned, we must additionally know that OP0 >= CST,
2449 otherwise the operation underflows.
2452 /* This should only happen if the type is unsigned; however, for
2453 buggy programs that use overflowing signed arithmetics even with
2454 -fno-wrapv, this condition may also be true for signed values. */
2455 if (double_int_ucmp (bnd, cst) < 0)
2458 if (TYPE_UNSIGNED (type))
2460 tree tem = fold_binary (GE_EXPR, boolean_type_node, op0,
2461 double_int_to_tree (type, cst));
2462 if (!tem || integer_nonzerop (tem))
2466 bnd = double_int_sub (bnd, cst);
2471 case FLOOR_DIV_EXPR:
2472 case EXACT_DIV_EXPR:
2473 if (TREE_CODE (op1) != INTEGER_CST
2474 || tree_int_cst_sign_bit (op1))
2477 bnd = derive_constant_upper_bound (op0);
2478 return double_int_udiv (bnd, tree_to_double_int (op1), FLOOR_DIV_EXPR);
2481 if (TREE_CODE (op1) != INTEGER_CST
2482 || tree_int_cst_sign_bit (op1))
2484 return tree_to_double_int (op1);
2487 stmt = SSA_NAME_DEF_STMT (op0);
2488 if (gimple_code (stmt) != GIMPLE_ASSIGN
2489 || gimple_assign_lhs (stmt) != op0)
2491 return derive_constant_upper_bound_assign (stmt);
2498 /* Records that every statement in LOOP is executed I_BOUND times.
2499 REALISTIC is true if I_BOUND is expected to be close to the real number
2500 of iterations. UPPER is true if we are sure the loop iterates at most
2504 record_niter_bound (struct loop *loop, double_int i_bound, bool realistic,
2507 /* Update the bounds only when there is no previous estimation, or when the current
2508 estimation is smaller. */
2510 && (!loop->any_upper_bound
2511 || double_int_ucmp (i_bound, loop->nb_iterations_upper_bound) < 0))
2513 loop->any_upper_bound = true;
2514 loop->nb_iterations_upper_bound = i_bound;
2517 && (!loop->any_estimate
2518 || double_int_ucmp (i_bound, loop->nb_iterations_estimate) < 0))
2520 loop->any_estimate = true;
2521 loop->nb_iterations_estimate = i_bound;
2525 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
2526 is true if the loop is exited immediately after STMT, and this exit
2527 is taken at last when the STMT is executed BOUND + 1 times.
2528 REALISTIC is true if BOUND is expected to be close to the real number
2529 of iterations. UPPER is true if we are sure the loop iterates at most
2530 BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */
2533 record_estimate (struct loop *loop, tree bound, double_int i_bound,
2534 gimple at_stmt, bool is_exit, bool realistic, bool upper)
2539 if (dump_file && (dump_flags & TDF_DETAILS))
2541 fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : "");
2542 print_gimple_stmt (dump_file, at_stmt, 0, TDF_SLIM);
2543 fprintf (dump_file, " is %sexecuted at most ",
2544 upper ? "" : "probably ");
2545 print_generic_expr (dump_file, bound, TDF_SLIM);
2546 fprintf (dump_file, " (bounded by ");
2547 dump_double_int (dump_file, i_bound, true);
2548 fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num);
2551 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
2552 real number of iterations. */
2553 if (TREE_CODE (bound) != INTEGER_CST)
2555 if (!upper && !realistic)
2558 /* If we have a guaranteed upper bound, record it in the appropriate
2562 struct nb_iter_bound *elt = ggc_alloc_nb_iter_bound ();
2564 elt->bound = i_bound;
2565 elt->stmt = at_stmt;
2566 elt->is_exit = is_exit;
2567 elt->next = loop->bounds;
2571 /* Update the number of iteration estimates according to the bound.
2572 If at_stmt is an exit, then every statement in the loop is
2573 executed at most BOUND + 1 times. If it is not an exit, then
2574 some of the statements before it could be executed BOUND + 2
2575 times, if an exit of LOOP is before stmt. */
2576 exit = single_exit (loop);
2579 && dominated_by_p (CDI_DOMINATORS,
2580 exit->src, gimple_bb (at_stmt))))
2581 delta = double_int_one;
2583 delta = double_int_two;
2584 i_bound = double_int_add (i_bound, delta);
2586 /* If an overflow occurred, ignore the result. */
2587 if (double_int_ucmp (i_bound, delta) < 0)
2590 record_niter_bound (loop, i_bound, realistic, upper);
2593 /* Record the estimate on number of iterations of LOOP based on the fact that
2594 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
2595 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
2596 estimated number of iterations is expected to be close to the real one.
2597 UPPER is true if we are sure the induction variable does not wrap. */
2600 record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple stmt,
2601 tree low, tree high, bool realistic, bool upper)
2603 tree niter_bound, extreme, delta;
2604 tree type = TREE_TYPE (base), unsigned_type;
2607 if (TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
2610 if (dump_file && (dump_flags & TDF_DETAILS))
2612 fprintf (dump_file, "Induction variable (");
2613 print_generic_expr (dump_file, TREE_TYPE (base), TDF_SLIM);
2614 fprintf (dump_file, ") ");
2615 print_generic_expr (dump_file, base, TDF_SLIM);
2616 fprintf (dump_file, " + ");
2617 print_generic_expr (dump_file, step, TDF_SLIM);
2618 fprintf (dump_file, " * iteration does not wrap in statement ");
2619 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2620 fprintf (dump_file, " in loop %d.\n", loop->num);
2623 unsigned_type = unsigned_type_for (type);
2624 base = fold_convert (unsigned_type, base);
2625 step = fold_convert (unsigned_type, step);
2627 if (tree_int_cst_sign_bit (step))
2629 extreme = fold_convert (unsigned_type, low);
2630 if (TREE_CODE (base) != INTEGER_CST)
2631 base = fold_convert (unsigned_type, high);
2632 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
2633 step = fold_build1 (NEGATE_EXPR, unsigned_type, step);
2637 extreme = fold_convert (unsigned_type, high);
2638 if (TREE_CODE (base) != INTEGER_CST)
2639 base = fold_convert (unsigned_type, low);
2640 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
2643 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
2644 would get out of the range. */
2645 niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step);
2646 max = derive_constant_upper_bound (niter_bound);
2647 record_estimate (loop, niter_bound, max, stmt, false, realistic, upper);
2650 /* Returns true if REF is a reference to an array at the end of a dynamically
2651 allocated structure. If this is the case, the array may be allocated larger
2652 than its upper bound implies. */
2655 array_at_struct_end_p (tree ref)
2657 tree base = get_base_address (ref);
2660 /* Unless the reference is through a pointer, the size of the array matches
2662 if (!base || (!INDIRECT_REF_P (base) && TREE_CODE (base) != MEM_REF))
2665 for (;handled_component_p (ref); ref = parent)
2667 parent = TREE_OPERAND (ref, 0);
2669 if (TREE_CODE (ref) == COMPONENT_REF)
2671 /* All fields of a union are at its end. */
2672 if (TREE_CODE (TREE_TYPE (parent)) == UNION_TYPE)
2675 /* Unless the field is at the end of the struct, we are done. */
2676 field = TREE_OPERAND (ref, 1);
2677 if (DECL_CHAIN (field))
2681 /* The other options are ARRAY_REF, ARRAY_RANGE_REF, VIEW_CONVERT_EXPR.
2682 In all these cases, we might be accessing the last element, and
2683 although in practice this will probably never happen, it is legal for
2684 the indices of this last element to exceed the bounds of the array.
2685 Therefore, continue checking. */
2691 /* Determine information about number of iterations a LOOP from the index
2692 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
2693 guaranteed to be executed in every iteration of LOOP. Callback for
2704 idx_infer_loop_bounds (tree base, tree *idx, void *dta)
2706 struct ilb_data *data = (struct ilb_data *) dta;
2707 tree ev, init, step;
2708 tree low, high, type, next;
2709 bool sign, upper = data->reliable, at_end = false;
2710 struct loop *loop = data->loop;
2712 if (TREE_CODE (base) != ARRAY_REF)
2715 /* For arrays at the end of the structure, we are not guaranteed that they
2716 do not really extend over their declared size. However, for arrays of
2717 size greater than one, this is unlikely to be intended. */
2718 if (array_at_struct_end_p (base))
2724 ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx));
2725 init = initial_condition (ev);
2726 step = evolution_part_in_loop_num (ev, loop->num);
2730 || TREE_CODE (step) != INTEGER_CST
2731 || integer_zerop (step)
2732 || tree_contains_chrecs (init, NULL)
2733 || chrec_contains_symbols_defined_in_loop (init, loop->num))
2736 low = array_ref_low_bound (base);
2737 high = array_ref_up_bound (base);
2739 /* The case of nonconstant bounds could be handled, but it would be
2741 if (TREE_CODE (low) != INTEGER_CST
2743 || TREE_CODE (high) != INTEGER_CST)
2745 sign = tree_int_cst_sign_bit (step);
2746 type = TREE_TYPE (step);
2748 /* The array of length 1 at the end of a structure most likely extends
2749 beyond its bounds. */
2751 && operand_equal_p (low, high, 0))
2754 /* In case the relevant bound of the array does not fit in type, or
2755 it does, but bound + step (in type) still belongs into the range of the
2756 array, the index may wrap and still stay within the range of the array
2757 (consider e.g. if the array is indexed by the full range of
2760 To make things simpler, we require both bounds to fit into type, although
2761 there are cases where this would not be strictly necessary. */
2762 if (!int_fits_type_p (high, type)
2763 || !int_fits_type_p (low, type))
2765 low = fold_convert (type, low);
2766 high = fold_convert (type, high);
2769 next = fold_binary (PLUS_EXPR, type, low, step);
2771 next = fold_binary (PLUS_EXPR, type, high, step);
2773 if (tree_int_cst_compare (low, next) <= 0
2774 && tree_int_cst_compare (next, high) <= 0)
2777 record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true, upper);
2781 /* Determine information about number of iterations a LOOP from the bounds
2782 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
2783 STMT is guaranteed to be executed in every iteration of LOOP.*/
2786 infer_loop_bounds_from_ref (struct loop *loop, gimple stmt, tree ref,
2789 struct ilb_data data;
2793 data.reliable = reliable;
2794 for_each_index (&ref, idx_infer_loop_bounds, &data);
2797 /* Determine information about number of iterations of a LOOP from the way
2798 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
2799 executed in every iteration of LOOP. */
2802 infer_loop_bounds_from_array (struct loop *loop, gimple stmt, bool reliable)
2804 if (is_gimple_assign (stmt))
2806 tree op0 = gimple_assign_lhs (stmt);
2807 tree op1 = gimple_assign_rhs1 (stmt);
2809 /* For each memory access, analyze its access function
2810 and record a bound on the loop iteration domain. */
2811 if (REFERENCE_CLASS_P (op0))
2812 infer_loop_bounds_from_ref (loop, stmt, op0, reliable);
2814 if (REFERENCE_CLASS_P (op1))
2815 infer_loop_bounds_from_ref (loop, stmt, op1, reliable);
2817 else if (is_gimple_call (stmt))
2820 unsigned i, n = gimple_call_num_args (stmt);
2822 lhs = gimple_call_lhs (stmt);
2823 if (lhs && REFERENCE_CLASS_P (lhs))
2824 infer_loop_bounds_from_ref (loop, stmt, lhs, reliable);
2826 for (i = 0; i < n; i++)
2828 arg = gimple_call_arg (stmt, i);
2829 if (REFERENCE_CLASS_P (arg))
2830 infer_loop_bounds_from_ref (loop, stmt, arg, reliable);
2835 /* Determine information about number of iterations of a LOOP from the fact
2836 that signed arithmetics in STMT does not overflow. */
2839 infer_loop_bounds_from_signedness (struct loop *loop, gimple stmt)
2841 tree def, base, step, scev, type, low, high;
2843 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2846 def = gimple_assign_lhs (stmt);
2848 if (TREE_CODE (def) != SSA_NAME)
2851 type = TREE_TYPE (def);
2852 if (!INTEGRAL_TYPE_P (type)
2853 || !TYPE_OVERFLOW_UNDEFINED (type))
2856 scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
2857 if (chrec_contains_undetermined (scev))
2860 base = initial_condition_in_loop_num (scev, loop->num);
2861 step = evolution_part_in_loop_num (scev, loop->num);
2864 || TREE_CODE (step) != INTEGER_CST
2865 || tree_contains_chrecs (base, NULL)
2866 || chrec_contains_symbols_defined_in_loop (base, loop->num))
2869 low = lower_bound_in_type (type, type);
2870 high = upper_bound_in_type (type, type);
2872 record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
2875 /* The following analyzers are extracting informations on the bounds
2876 of LOOP from the following undefined behaviors:
2878 - data references should not access elements over the statically
2881 - signed variables should not overflow when flag_wrapv is not set.
2885 infer_loop_bounds_from_undefined (struct loop *loop)
2889 gimple_stmt_iterator bsi;
2893 bbs = get_loop_body (loop);
2895 for (i = 0; i < loop->num_nodes; i++)
2899 /* If BB is not executed in each iteration of the loop, we cannot
2900 use the operations in it to infer reliable upper bound on the
2901 # of iterations of the loop. However, we can use it as a guess. */
2902 reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb);
2904 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
2906 gimple stmt = gsi_stmt (bsi);
2908 infer_loop_bounds_from_array (loop, stmt, reliable);
2911 infer_loop_bounds_from_signedness (loop, stmt);
2919 /* Converts VAL to double_int. */
2922 gcov_type_to_double_int (gcov_type val)
2926 ret.low = (unsigned HOST_WIDE_INT) val;
2927 /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by
2928 the size of type. */
2929 val >>= HOST_BITS_PER_WIDE_INT - 1;
2931 ret.high = (unsigned HOST_WIDE_INT) val;
2936 /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
2937 is true also use estimates derived from undefined behavior. */
2940 estimate_numbers_of_iterations_loop (struct loop *loop, bool use_undefined_p)
2942 VEC (edge, heap) *exits;
2945 struct tree_niter_desc niter_desc;
2949 /* Give up if we already have tried to compute an estimation. */
2950 if (loop->estimate_state != EST_NOT_COMPUTED)
2952 loop->estimate_state = EST_AVAILABLE;
2953 loop->any_upper_bound = false;
2954 loop->any_estimate = false;
2956 exits = get_loop_exit_edges (loop);
2957 FOR_EACH_VEC_ELT (edge, exits, i, ex)
2959 if (!number_of_iterations_exit (loop, ex, &niter_desc, false))
2962 niter = niter_desc.niter;
2963 type = TREE_TYPE (niter);
2964 if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST)
2965 niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
2966 build_int_cst (type, 0),
2968 record_estimate (loop, niter, niter_desc.max,
2969 last_stmt (ex->src),
2972 VEC_free (edge, heap, exits);
2974 if (use_undefined_p)
2975 infer_loop_bounds_from_undefined (loop);
2977 /* If we have a measured profile, use it to estimate the number of
2979 if (loop->header->count != 0)
2981 gcov_type nit = expected_loop_iterations_unbounded (loop) + 1;
2982 bound = gcov_type_to_double_int (nit);
2983 record_niter_bound (loop, bound, true, false);
2986 /* If an upper bound is smaller than the realistic estimate of the
2987 number of iterations, use the upper bound instead. */
2988 if (loop->any_upper_bound
2989 && loop->any_estimate
2990 && double_int_ucmp (loop->nb_iterations_upper_bound,
2991 loop->nb_iterations_estimate) < 0)
2992 loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
2995 /* Records estimates on numbers of iterations of loops. */
2998 estimate_numbers_of_iterations (bool use_undefined_p)
3003 /* We don't want to issue signed overflow warnings while getting
3004 loop iteration estimates. */
3005 fold_defer_overflow_warnings ();
3007 FOR_EACH_LOOP (li, loop, 0)
3009 estimate_numbers_of_iterations_loop (loop, use_undefined_p);
3012 fold_undefer_and_ignore_overflow_warnings ();
3015 /* Returns true if statement S1 dominates statement S2. */
3018 stmt_dominates_stmt_p (gimple s1, gimple s2)
3020 basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
3028 gimple_stmt_iterator bsi;
3030 if (gimple_code (s2) == GIMPLE_PHI)
3033 if (gimple_code (s1) == GIMPLE_PHI)
3036 for (bsi = gsi_start_bb (bb1); gsi_stmt (bsi) != s2; gsi_next (&bsi))
3037 if (gsi_stmt (bsi) == s1)
3043 return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
3046 /* Returns true when we can prove that the number of executions of
3047 STMT in the loop is at most NITER, according to the bound on
3048 the number of executions of the statement NITER_BOUND->stmt recorded in
3049 NITER_BOUND. If STMT is NULL, we must prove this bound for all
3050 statements in the loop. */
3053 n_of_executions_at_most (gimple stmt,
3054 struct nb_iter_bound *niter_bound,
3057 double_int bound = niter_bound->bound;
3058 tree nit_type = TREE_TYPE (niter), e;
3061 gcc_assert (TYPE_UNSIGNED (nit_type));
3063 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
3064 the number of iterations is small. */
3065 if (!double_int_fits_to_tree_p (nit_type, bound))
3068 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3069 times. This means that:
3071 -- if NITER_BOUND->is_exit is true, then everything before
3072 NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3073 times, and everything after it at most NITER_BOUND->bound times.
3075 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
3076 is executed, then NITER_BOUND->stmt is executed as well in the same
3077 iteration (we conclude that if both statements belong to the same
3078 basic block, or if STMT is after NITER_BOUND->stmt), then STMT
3079 is executed at most NITER_BOUND->bound + 1 times. Otherwise STMT is
3080 executed at most NITER_BOUND->bound + 2 times. */
3082 if (niter_bound->is_exit)
3085 && stmt != niter_bound->stmt
3086 && stmt_dominates_stmt_p (niter_bound->stmt, stmt))
3094 || (gimple_bb (stmt) != gimple_bb (niter_bound->stmt)
3095 && !stmt_dominates_stmt_p (niter_bound->stmt, stmt)))
3097 bound = double_int_add (bound, double_int_one);
3098 if (double_int_zero_p (bound)
3099 || !double_int_fits_to_tree_p (nit_type, bound))
3105 e = fold_binary (cmp, boolean_type_node,
3106 niter, double_int_to_tree (nit_type, bound));
3107 return e && integer_nonzerop (e);
3110 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
3113 nowrap_type_p (tree type)
3115 if (INTEGRAL_TYPE_P (type)
3116 && TYPE_OVERFLOW_UNDEFINED (type))
3119 if (POINTER_TYPE_P (type))
3125 /* Return false only when the induction variable BASE + STEP * I is
3126 known to not overflow: i.e. when the number of iterations is small
3127 enough with respect to the step and initial condition in order to
3128 keep the evolution confined in TYPEs bounds. Return true when the
3129 iv is known to overflow or when the property is not computable.
3131 USE_OVERFLOW_SEMANTICS is true if this function should assume that
3132 the rules for overflow of the given language apply (e.g., that signed
3133 arithmetics in C does not overflow). */
3136 scev_probably_wraps_p (tree base, tree step,
3137 gimple at_stmt, struct loop *loop,
3138 bool use_overflow_semantics)
3140 struct nb_iter_bound *bound;
3141 tree delta, step_abs;
3142 tree unsigned_type, valid_niter;
3143 tree type = TREE_TYPE (step);
3145 /* FIXME: We really need something like
3146 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
3148 We used to test for the following situation that frequently appears
3149 during address arithmetics:
3151 D.1621_13 = (long unsigned intD.4) D.1620_12;
3152 D.1622_14 = D.1621_13 * 8;
3153 D.1623_15 = (doubleD.29 *) D.1622_14;
3155 And derived that the sequence corresponding to D_14
3156 can be proved to not wrap because it is used for computing a
3157 memory access; however, this is not really the case -- for example,
3158 if D_12 = (unsigned char) [254,+,1], then D_14 has values
3159 2032, 2040, 0, 8, ..., but the code is still legal. */
3161 if (chrec_contains_undetermined (base)
3162 || chrec_contains_undetermined (step))
3165 if (integer_zerop (step))
3168 /* If we can use the fact that signed and pointer arithmetics does not
3169 wrap, we are done. */
3170 if (use_overflow_semantics && nowrap_type_p (TREE_TYPE (base)))
3173 /* To be able to use estimates on number of iterations of the loop,
3174 we must have an upper bound on the absolute value of the step. */
3175 if (TREE_CODE (step) != INTEGER_CST)
3178 /* Don't issue signed overflow warnings. */
3179 fold_defer_overflow_warnings ();
3181 /* Otherwise, compute the number of iterations before we reach the
3182 bound of the type, and verify that the loop is exited before this
3184 unsigned_type = unsigned_type_for (type);
3185 base = fold_convert (unsigned_type, base);
3187 if (tree_int_cst_sign_bit (step))
3189 tree extreme = fold_convert (unsigned_type,
3190 lower_bound_in_type (type, type));
3191 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
3192 step_abs = fold_build1 (NEGATE_EXPR, unsigned_type,
3193 fold_convert (unsigned_type, step));
3197 tree extreme = fold_convert (unsigned_type,
3198 upper_bound_in_type (type, type));
3199 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
3200 step_abs = fold_convert (unsigned_type, step);
3203 valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
3205 estimate_numbers_of_iterations_loop (loop, true);
3206 for (bound = loop->bounds; bound; bound = bound->next)
3208 if (n_of_executions_at_most (at_stmt, bound, valid_niter))
3210 fold_undefer_and_ignore_overflow_warnings ();
3215 fold_undefer_and_ignore_overflow_warnings ();
3217 /* At this point we still don't have a proof that the iv does not
3218 overflow: give up. */
3222 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
3225 free_numbers_of_iterations_estimates_loop (struct loop *loop)
3227 struct nb_iter_bound *bound, *next;
3229 loop->nb_iterations = NULL;
3230 loop->estimate_state = EST_NOT_COMPUTED;
3231 for (bound = loop->bounds; bound; bound = next)
3237 loop->bounds = NULL;
3240 /* Frees the information on upper bounds on numbers of iterations of loops. */
3243 free_numbers_of_iterations_estimates (void)
3248 FOR_EACH_LOOP (li, loop, 0)
3250 free_numbers_of_iterations_estimates_loop (loop);
3254 /* Substitute value VAL for ssa name NAME inside expressions held
3258 substitute_in_loop_info (struct loop *loop, tree name, tree val)
3260 loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);