1 /* Functions to determine/estimate number of iterations of a loop.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
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"
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);
97 off = double_int_sext (off, TYPE_PRECISION (type));
98 mpz_set_double_int (offset, off, false);
100 mpz_neg (offset, offset);
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);
529 x = int_const_binop (MULT_EXPR, x, x);
531 rslt = int_const_binop (BIT_AND_EXPR, rslt, mask);
537 /* Derives the upper bound BND on the number of executions of loop with exit
538 condition S * i <> C. If NO_OVERFLOW is true, then the control variable of
539 the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed
540 that the loop ends through this exit, i.e., the induction variable ever
541 reaches the value of C.
543 The value C is equal to final - base, where final and base are the final and
544 initial value of the actual induction variable in the analysed loop. BNDS
545 bounds the value of this difference when computed in signed type with
546 unbounded range, while the computation of C is performed in an unsigned
547 type with the range matching the range of the type of the induction variable.
548 In particular, BNDS.up contains an upper bound on C in the following cases:
549 -- if the iv must reach its final value without overflow, i.e., if
550 NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
551 -- if final >= base, which we know to hold when BNDS.below >= 0. */
554 number_of_iterations_ne_max (mpz_t bnd, bool no_overflow, tree c, tree s,
555 bounds *bnds, bool exit_must_be_taken)
559 bool bnds_u_valid = ((no_overflow && exit_must_be_taken)
560 || mpz_sgn (bnds->below) >= 0);
562 if (multiple_of_p (TREE_TYPE (c), c, s))
564 /* If C is an exact multiple of S, then its value will be reached before
565 the induction variable overflows (unless the loop is exited in some
566 other way before). Note that the actual induction variable in the
567 loop (which ranges from base to final instead of from 0 to C) may
568 overflow, in which case BNDS.up will not be giving a correct upper
569 bound on C; thus, BNDS_U_VALID had to be computed in advance. */
571 exit_must_be_taken = true;
574 /* If the induction variable can overflow, the number of iterations is at
575 most the period of the control variable (or infinite, but in that case
576 the whole # of iterations analysis will fail). */
579 max = double_int_mask (TYPE_PRECISION (TREE_TYPE (c))
580 - tree_low_cst (num_ending_zeros (s), 1));
581 mpz_set_double_int (bnd, max, true);
585 /* Now we know that the induction variable does not overflow, so the loop
586 iterates at most (range of type / S) times. */
587 mpz_set_double_int (bnd, double_int_mask (TYPE_PRECISION (TREE_TYPE (c))),
590 /* If the induction variable is guaranteed to reach the value of C before
592 if (exit_must_be_taken)
594 /* ... then we can strenghten this to C / S, and possibly we can use
595 the upper bound on C given by BNDS. */
596 if (TREE_CODE (c) == INTEGER_CST)
597 mpz_set_double_int (bnd, tree_to_double_int (c), true);
598 else if (bnds_u_valid)
599 mpz_set (bnd, bnds->up);
603 mpz_set_double_int (d, tree_to_double_int (s), true);
604 mpz_fdiv_q (bnd, bnd, d);
608 /* Determines number of iterations of loop whose ending condition
609 is IV <> FINAL. TYPE is the type of the iv. The number of
610 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
611 we know that the exit must be taken eventually, i.e., that the IV
612 ever reaches the value FINAL (we derived this earlier, and possibly set
613 NITER->assumptions to make sure this is the case). BNDS contains the
614 bounds on the difference FINAL - IV->base. */
617 number_of_iterations_ne (tree type, affine_iv *iv, tree final,
618 struct tree_niter_desc *niter, bool exit_must_be_taken,
621 tree niter_type = unsigned_type_for (type);
622 tree s, c, d, bits, assumption, tmp, bound;
625 niter->control = *iv;
626 niter->bound = final;
627 niter->cmp = NE_EXPR;
629 /* Rearrange the terms so that we get inequality S * i <> C, with S
630 positive. Also cast everything to the unsigned type. If IV does
631 not overflow, BNDS bounds the value of C. Also, this is the
632 case if the computation |FINAL - IV->base| does not overflow, i.e.,
633 if BNDS->below in the result is nonnegative. */
634 if (tree_int_cst_sign_bit (iv->step))
636 s = fold_convert (niter_type,
637 fold_build1 (NEGATE_EXPR, type, iv->step));
638 c = fold_build2 (MINUS_EXPR, niter_type,
639 fold_convert (niter_type, iv->base),
640 fold_convert (niter_type, final));
641 bounds_negate (bnds);
645 s = fold_convert (niter_type, iv->step);
646 c = fold_build2 (MINUS_EXPR, niter_type,
647 fold_convert (niter_type, final),
648 fold_convert (niter_type, iv->base));
652 number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds,
654 niter->max = mpz_get_double_int (niter_type, max, false);
657 /* First the trivial cases -- when the step is 1. */
658 if (integer_onep (s))
664 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
665 is infinite. Otherwise, the number of iterations is
666 (inverse(s/d) * (c/d)) mod (size of mode/d). */
667 bits = num_ending_zeros (s);
668 bound = build_low_bits_mask (niter_type,
669 (TYPE_PRECISION (niter_type)
670 - tree_low_cst (bits, 1)));
672 d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
673 build_int_cst (niter_type, 1), bits);
674 s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
676 if (!exit_must_be_taken)
678 /* If we cannot assume that the exit is taken eventually, record the
679 assumptions for divisibility of c. */
680 assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d);
681 assumption = fold_build2 (EQ_EXPR, boolean_type_node,
682 assumption, build_int_cst (niter_type, 0));
683 if (!integer_nonzerop (assumption))
684 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
685 niter->assumptions, assumption);
688 c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d);
689 tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound));
690 niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound);
694 /* Checks whether we can determine the final value of the control variable
695 of the loop with ending condition IV0 < IV1 (computed in TYPE).
696 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
697 of the step. The assumptions necessary to ensure that the computation
698 of the final value does not overflow are recorded in NITER. If we
699 find the final value, we adjust DELTA and return TRUE. Otherwise
700 we return false. BNDS bounds the value of IV1->base - IV0->base,
701 and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
702 true if we know that the exit must be taken eventually. */
705 number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1,
706 struct tree_niter_desc *niter,
707 tree *delta, tree step,
708 bool exit_must_be_taken, bounds *bnds)
710 tree niter_type = TREE_TYPE (step);
711 tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step);
714 tree assumption = boolean_true_node, bound, noloop;
715 bool ret = false, fv_comp_no_overflow;
717 if (POINTER_TYPE_P (type))
720 if (TREE_CODE (mod) != INTEGER_CST)
722 if (integer_nonzerop (mod))
723 mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
724 tmod = fold_convert (type1, mod);
727 mpz_set_double_int (mmod, tree_to_double_int (mod), true);
728 mpz_neg (mmod, mmod);
730 /* If the induction variable does not overflow and the exit is taken,
731 then the computation of the final value does not overflow. This is
732 also obviously the case if the new final value is equal to the
733 current one. Finally, we postulate this for pointer type variables,
734 as the code cannot rely on the object to that the pointer points being
735 placed at the end of the address space (and more pragmatically,
736 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
737 if (integer_zerop (mod) || POINTER_TYPE_P (type))
738 fv_comp_no_overflow = true;
739 else if (!exit_must_be_taken)
740 fv_comp_no_overflow = false;
742 fv_comp_no_overflow =
743 (iv0->no_overflow && integer_nonzerop (iv0->step))
744 || (iv1->no_overflow && integer_nonzerop (iv1->step));
746 if (integer_nonzerop (iv0->step))
748 /* The final value of the iv is iv1->base + MOD, assuming that this
749 computation does not overflow, and that
750 iv0->base <= iv1->base + MOD. */
751 if (!fv_comp_no_overflow)
753 bound = fold_build2 (MINUS_EXPR, type1,
754 TYPE_MAX_VALUE (type1), tmod);
755 assumption = fold_build2 (LE_EXPR, boolean_type_node,
757 if (integer_zerop (assumption))
760 if (mpz_cmp (mmod, bnds->below) < 0)
761 noloop = boolean_false_node;
762 else if (POINTER_TYPE_P (type))
763 noloop = fold_build2 (GT_EXPR, boolean_type_node,
765 fold_build_pointer_plus (iv1->base, tmod));
767 noloop = fold_build2 (GT_EXPR, boolean_type_node,
769 fold_build2 (PLUS_EXPR, type1,
774 /* The final value of the iv is iv0->base - MOD, assuming that this
775 computation does not overflow, and that
776 iv0->base - MOD <= iv1->base. */
777 if (!fv_comp_no_overflow)
779 bound = fold_build2 (PLUS_EXPR, type1,
780 TYPE_MIN_VALUE (type1), tmod);
781 assumption = fold_build2 (GE_EXPR, boolean_type_node,
783 if (integer_zerop (assumption))
786 if (mpz_cmp (mmod, bnds->below) < 0)
787 noloop = boolean_false_node;
788 else if (POINTER_TYPE_P (type))
789 noloop = fold_build2 (GT_EXPR, boolean_type_node,
790 fold_build_pointer_plus (iv0->base,
791 fold_build1 (NEGATE_EXPR,
795 noloop = fold_build2 (GT_EXPR, boolean_type_node,
796 fold_build2 (MINUS_EXPR, type1,
801 if (!integer_nonzerop (assumption))
802 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
805 if (!integer_zerop (noloop))
806 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
809 bounds_add (bnds, tree_to_double_int (mod), type);
810 *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod);
818 /* Add assertions to NITER that ensure that the control variable of the loop
819 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
820 are TYPE. Returns false if we can prove that there is an overflow, true
821 otherwise. STEP is the absolute value of the step. */
824 assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
825 struct tree_niter_desc *niter, tree step)
827 tree bound, d, assumption, diff;
828 tree niter_type = TREE_TYPE (step);
830 if (integer_nonzerop (iv0->step))
832 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
833 if (iv0->no_overflow)
836 /* If iv0->base is a constant, we can determine the last value before
837 overflow precisely; otherwise we conservatively assume
840 if (TREE_CODE (iv0->base) == INTEGER_CST)
842 d = fold_build2 (MINUS_EXPR, niter_type,
843 fold_convert (niter_type, TYPE_MAX_VALUE (type)),
844 fold_convert (niter_type, iv0->base));
845 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
848 diff = fold_build2 (MINUS_EXPR, niter_type, step,
849 build_int_cst (niter_type, 1));
850 bound = fold_build2 (MINUS_EXPR, type,
851 TYPE_MAX_VALUE (type), fold_convert (type, diff));
852 assumption = fold_build2 (LE_EXPR, boolean_type_node,
857 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
858 if (iv1->no_overflow)
861 if (TREE_CODE (iv1->base) == INTEGER_CST)
863 d = fold_build2 (MINUS_EXPR, niter_type,
864 fold_convert (niter_type, iv1->base),
865 fold_convert (niter_type, TYPE_MIN_VALUE (type)));
866 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
869 diff = fold_build2 (MINUS_EXPR, niter_type, step,
870 build_int_cst (niter_type, 1));
871 bound = fold_build2 (PLUS_EXPR, type,
872 TYPE_MIN_VALUE (type), fold_convert (type, diff));
873 assumption = fold_build2 (GE_EXPR, boolean_type_node,
877 if (integer_zerop (assumption))
879 if (!integer_nonzerop (assumption))
880 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
881 niter->assumptions, assumption);
883 iv0->no_overflow = true;
884 iv1->no_overflow = true;
888 /* Add an assumption to NITER that a loop whose ending condition
889 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
890 bounds the value of IV1->base - IV0->base. */
893 assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
894 struct tree_niter_desc *niter, bounds *bnds)
896 tree assumption = boolean_true_node, bound, diff;
897 tree mbz, mbzl, mbzr, type1;
898 bool rolls_p, no_overflow_p;
902 /* We are going to compute the number of iterations as
903 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
904 variant of TYPE. This formula only works if
906 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
908 (where MAX is the maximum value of the unsigned variant of TYPE, and
909 the computations in this formula are performed in full precision,
910 i.e., without overflows).
912 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
913 we have a condition of the form iv0->base - step < iv1->base before the loop,
914 and for loops iv0->base < iv1->base - step * i the condition
915 iv0->base < iv1->base + step, due to loop header copying, which enable us
916 to prove the lower bound.
918 The upper bound is more complicated. Unless the expressions for initial
919 and final value themselves contain enough information, we usually cannot
920 derive it from the context. */
922 /* First check whether the answer does not follow from the bounds we gathered
924 if (integer_nonzerop (iv0->step))
925 dstep = tree_to_double_int (iv0->step);
928 dstep = double_int_sext (tree_to_double_int (iv1->step),
929 TYPE_PRECISION (type));
930 dstep = double_int_neg (dstep);
934 mpz_set_double_int (mstep, dstep, true);
935 mpz_neg (mstep, mstep);
936 mpz_add_ui (mstep, mstep, 1);
938 rolls_p = mpz_cmp (mstep, bnds->below) <= 0;
941 mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true);
942 mpz_add (max, max, mstep);
943 no_overflow_p = (mpz_cmp (bnds->up, max) <= 0
944 /* For pointers, only values lying inside a single object
945 can be compared or manipulated by pointer arithmetics.
946 Gcc in general does not allow or handle objects larger
947 than half of the address space, hence the upper bound
948 is satisfied for pointers. */
949 || POINTER_TYPE_P (type));
953 if (rolls_p && no_overflow_p)
957 if (POINTER_TYPE_P (type))
960 /* Now the hard part; we must formulate the assumption(s) as expressions, and
961 we must be careful not to introduce overflow. */
963 if (integer_nonzerop (iv0->step))
965 diff = fold_build2 (MINUS_EXPR, type1,
966 iv0->step, build_int_cst (type1, 1));
968 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
969 0 address never belongs to any object, we can assume this for
971 if (!POINTER_TYPE_P (type))
973 bound = fold_build2 (PLUS_EXPR, type1,
974 TYPE_MIN_VALUE (type), diff);
975 assumption = fold_build2 (GE_EXPR, boolean_type_node,
979 /* And then we can compute iv0->base - diff, and compare it with
981 mbzl = fold_build2 (MINUS_EXPR, type1,
982 fold_convert (type1, iv0->base), diff);
983 mbzr = fold_convert (type1, iv1->base);
987 diff = fold_build2 (PLUS_EXPR, type1,
988 iv1->step, build_int_cst (type1, 1));
990 if (!POINTER_TYPE_P (type))
992 bound = fold_build2 (PLUS_EXPR, type1,
993 TYPE_MAX_VALUE (type), diff);
994 assumption = fold_build2 (LE_EXPR, boolean_type_node,
998 mbzl = fold_convert (type1, iv0->base);
999 mbzr = fold_build2 (MINUS_EXPR, type1,
1000 fold_convert (type1, iv1->base), diff);
1003 if (!integer_nonzerop (assumption))
1004 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1005 niter->assumptions, assumption);
1008 mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr);
1009 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
1010 niter->may_be_zero, mbz);
1014 /* Determines number of iterations of loop whose ending condition
1015 is IV0 < IV1. TYPE is the type of the iv. The number of
1016 iterations is stored to NITER. BNDS bounds the difference
1017 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
1018 that the exit must be taken eventually. */
1021 number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
1022 struct tree_niter_desc *niter,
1023 bool exit_must_be_taken, bounds *bnds)
1025 tree niter_type = unsigned_type_for (type);
1026 tree delta, step, s;
1029 if (integer_nonzerop (iv0->step))
1031 niter->control = *iv0;
1032 niter->cmp = LT_EXPR;
1033 niter->bound = iv1->base;
1037 niter->control = *iv1;
1038 niter->cmp = GT_EXPR;
1039 niter->bound = iv0->base;
1042 delta = fold_build2 (MINUS_EXPR, niter_type,
1043 fold_convert (niter_type, iv1->base),
1044 fold_convert (niter_type, iv0->base));
1046 /* First handle the special case that the step is +-1. */
1047 if ((integer_onep (iv0->step) && integer_zerop (iv1->step))
1048 || (integer_all_onesp (iv1->step) && integer_zerop (iv0->step)))
1050 /* for (i = iv0->base; i < iv1->base; i++)
1054 for (i = iv1->base; i > iv0->base; i--).
1056 In both cases # of iterations is iv1->base - iv0->base, assuming that
1057 iv1->base >= iv0->base.
1059 First try to derive a lower bound on the value of
1060 iv1->base - iv0->base, computed in full precision. If the difference
1061 is nonnegative, we are done, otherwise we must record the
1064 if (mpz_sgn (bnds->below) < 0)
1065 niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
1066 iv1->base, iv0->base);
1067 niter->niter = delta;
1068 niter->max = mpz_get_double_int (niter_type, bnds->up, false);
1072 if (integer_nonzerop (iv0->step))
1073 step = fold_convert (niter_type, iv0->step);
1075 step = fold_convert (niter_type,
1076 fold_build1 (NEGATE_EXPR, type, iv1->step));
1078 /* If we can determine the final value of the control iv exactly, we can
1079 transform the condition to != comparison. In particular, this will be
1080 the case if DELTA is constant. */
1081 if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step,
1082 exit_must_be_taken, bnds))
1086 zps.base = build_int_cst (niter_type, 0);
1088 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1089 zps does not overflow. */
1090 zps.no_overflow = true;
1092 return number_of_iterations_ne (type, &zps, delta, niter, true, bnds);
1095 /* Make sure that the control iv does not overflow. */
1096 if (!assert_no_overflow_lt (type, iv0, iv1, niter, step))
1099 /* We determine the number of iterations as (delta + step - 1) / step. For
1100 this to work, we must know that iv1->base >= iv0->base - step + 1,
1101 otherwise the loop does not roll. */
1102 assert_loop_rolls_lt (type, iv0, iv1, niter, bnds);
1104 s = fold_build2 (MINUS_EXPR, niter_type,
1105 step, build_int_cst (niter_type, 1));
1106 delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
1107 niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
1111 mpz_set_double_int (mstep, tree_to_double_int (step), true);
1112 mpz_add (tmp, bnds->up, mstep);
1113 mpz_sub_ui (tmp, tmp, 1);
1114 mpz_fdiv_q (tmp, tmp, mstep);
1115 niter->max = mpz_get_double_int (niter_type, tmp, false);
1122 /* Determines number of iterations of loop whose ending condition
1123 is IV0 <= IV1. TYPE is the type of the iv. The number of
1124 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
1125 we know that this condition must eventually become false (we derived this
1126 earlier, and possibly set NITER->assumptions to make sure this
1127 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1130 number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1,
1131 struct tree_niter_desc *niter, bool exit_must_be_taken,
1136 if (POINTER_TYPE_P (type))
1139 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1140 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1141 value of the type. This we must know anyway, since if it is
1142 equal to this value, the loop rolls forever. We do not check
1143 this condition for pointer type ivs, as the code cannot rely on
1144 the object to that the pointer points being placed at the end of
1145 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1146 not defined for pointers). */
1148 if (!exit_must_be_taken && !POINTER_TYPE_P (type))
1150 if (integer_nonzerop (iv0->step))
1151 assumption = fold_build2 (NE_EXPR, boolean_type_node,
1152 iv1->base, TYPE_MAX_VALUE (type));
1154 assumption = fold_build2 (NE_EXPR, boolean_type_node,
1155 iv0->base, TYPE_MIN_VALUE (type));
1157 if (integer_zerop (assumption))
1159 if (!integer_nonzerop (assumption))
1160 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1161 niter->assumptions, assumption);
1164 if (integer_nonzerop (iv0->step))
1166 if (POINTER_TYPE_P (type))
1167 iv1->base = fold_build_pointer_plus_hwi (iv1->base, 1);
1169 iv1->base = fold_build2 (PLUS_EXPR, type1, iv1->base,
1170 build_int_cst (type1, 1));
1172 else if (POINTER_TYPE_P (type))
1173 iv0->base = fold_build_pointer_plus_hwi (iv0->base, -1);
1175 iv0->base = fold_build2 (MINUS_EXPR, type1,
1176 iv0->base, build_int_cst (type1, 1));
1178 bounds_add (bnds, double_int_one, type1);
1180 return number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken,
1184 /* Dumps description of affine induction variable IV to FILE. */
1187 dump_affine_iv (FILE *file, affine_iv *iv)
1189 if (!integer_zerop (iv->step))
1190 fprintf (file, "[");
1192 print_generic_expr (dump_file, iv->base, TDF_SLIM);
1194 if (!integer_zerop (iv->step))
1196 fprintf (file, ", + , ");
1197 print_generic_expr (dump_file, iv->step, TDF_SLIM);
1198 fprintf (file, "]%s", iv->no_overflow ? "(no_overflow)" : "");
1202 /* Determine the number of iterations according to condition (for staying
1203 inside loop) which compares two induction variables using comparison
1204 operator CODE. The induction variable on left side of the comparison
1205 is IV0, the right-hand side is IV1. Both induction variables must have
1206 type TYPE, which must be an integer or pointer type. The steps of the
1207 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1209 LOOP is the loop whose number of iterations we are determining.
1211 ONLY_EXIT is true if we are sure this is the only way the loop could be
1212 exited (including possibly non-returning function calls, exceptions, etc.)
1213 -- in this case we can use the information whether the control induction
1214 variables can overflow or not in a more efficient way.
1216 The results (number of iterations and assumptions as described in
1217 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
1218 Returns false if it fails to determine number of iterations, true if it
1219 was determined (possibly with some assumptions). */
1222 number_of_iterations_cond (struct loop *loop,
1223 tree type, affine_iv *iv0, enum tree_code code,
1224 affine_iv *iv1, struct tree_niter_desc *niter,
1227 bool exit_must_be_taken = false, ret;
1230 /* The meaning of these assumptions is this:
1232 then the rest of information does not have to be valid
1233 if may_be_zero then the loop does not roll, even if
1235 niter->assumptions = boolean_true_node;
1236 niter->may_be_zero = boolean_false_node;
1237 niter->niter = NULL_TREE;
1238 niter->max = double_int_zero;
1240 niter->bound = NULL_TREE;
1241 niter->cmp = ERROR_MARK;
1243 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1244 the control variable is on lhs. */
1245 if (code == GE_EXPR || code == GT_EXPR
1246 || (code == NE_EXPR && integer_zerop (iv0->step)))
1249 code = swap_tree_comparison (code);
1252 if (POINTER_TYPE_P (type))
1254 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1255 to the same object. If they do, the control variable cannot wrap
1256 (as wrap around the bounds of memory will never return a pointer
1257 that would be guaranteed to point to the same object, even if we
1258 avoid undefined behavior by casting to size_t and back). */
1259 iv0->no_overflow = true;
1260 iv1->no_overflow = true;
1263 /* If the control induction variable does not overflow and the only exit
1264 from the loop is the one that we analyze, we know it must be taken
1268 if (!integer_zerop (iv0->step) && iv0->no_overflow)
1269 exit_must_be_taken = true;
1270 else if (!integer_zerop (iv1->step) && iv1->no_overflow)
1271 exit_must_be_taken = true;
1274 /* We can handle the case when neither of the sides of the comparison is
1275 invariant, provided that the test is NE_EXPR. This rarely occurs in
1276 practice, but it is simple enough to manage. */
1277 if (!integer_zerop (iv0->step) && !integer_zerop (iv1->step))
1279 tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
1280 if (code != NE_EXPR)
1283 iv0->step = fold_binary_to_constant (MINUS_EXPR, step_type,
1284 iv0->step, iv1->step);
1285 iv0->no_overflow = false;
1286 iv1->step = build_int_cst (step_type, 0);
1287 iv1->no_overflow = true;
1290 /* If the result of the comparison is a constant, the loop is weird. More
1291 precise handling would be possible, but the situation is not common enough
1292 to waste time on it. */
1293 if (integer_zerop (iv0->step) && integer_zerop (iv1->step))
1296 /* Ignore loops of while (i-- < 10) type. */
1297 if (code != NE_EXPR)
1299 if (iv0->step && tree_int_cst_sign_bit (iv0->step))
1302 if (!integer_zerop (iv1->step) && !tree_int_cst_sign_bit (iv1->step))
1306 /* If the loop exits immediately, there is nothing to do. */
1307 if (integer_zerop (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
1309 niter->niter = build_int_cst (unsigned_type_for (type), 0);
1310 niter->max = double_int_zero;
1314 /* OK, now we know we have a senseful loop. Handle several cases, depending
1315 on what comparison operator is used. */
1316 bound_difference (loop, iv1->base, iv0->base, &bnds);
1318 if (dump_file && (dump_flags & TDF_DETAILS))
1321 "Analyzing # of iterations of loop %d\n", loop->num);
1323 fprintf (dump_file, " exit condition ");
1324 dump_affine_iv (dump_file, iv0);
1325 fprintf (dump_file, " %s ",
1326 code == NE_EXPR ? "!="
1327 : code == LT_EXPR ? "<"
1329 dump_affine_iv (dump_file, iv1);
1330 fprintf (dump_file, "\n");
1332 fprintf (dump_file, " bounds on difference of bases: ");
1333 mpz_out_str (dump_file, 10, bnds.below);
1334 fprintf (dump_file, " ... ");
1335 mpz_out_str (dump_file, 10, bnds.up);
1336 fprintf (dump_file, "\n");
1342 gcc_assert (integer_zerop (iv1->step));
1343 ret = number_of_iterations_ne (type, iv0, iv1->base, niter,
1344 exit_must_be_taken, &bnds);
1348 ret = number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken,
1353 ret = number_of_iterations_le (type, iv0, iv1, niter, exit_must_be_taken,
1361 mpz_clear (bnds.up);
1362 mpz_clear (bnds.below);
1364 if (dump_file && (dump_flags & TDF_DETAILS))
1368 fprintf (dump_file, " result:\n");
1369 if (!integer_nonzerop (niter->assumptions))
1371 fprintf (dump_file, " under assumptions ");
1372 print_generic_expr (dump_file, niter->assumptions, TDF_SLIM);
1373 fprintf (dump_file, "\n");
1376 if (!integer_zerop (niter->may_be_zero))
1378 fprintf (dump_file, " zero if ");
1379 print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
1380 fprintf (dump_file, "\n");
1383 fprintf (dump_file, " # of iterations ");
1384 print_generic_expr (dump_file, niter->niter, TDF_SLIM);
1385 fprintf (dump_file, ", bounded by ");
1386 dump_double_int (dump_file, niter->max, true);
1387 fprintf (dump_file, "\n");
1390 fprintf (dump_file, " failed\n\n");
1395 /* Substitute NEW for OLD in EXPR and fold the result. */
1398 simplify_replace_tree (tree expr, tree old, tree new_tree)
1401 tree ret = NULL_TREE, e, se;
1406 /* Do not bother to replace constants. */
1407 if (CONSTANT_CLASS_P (old))
1411 || operand_equal_p (expr, old, 0))
1412 return unshare_expr (new_tree);
1417 n = TREE_OPERAND_LENGTH (expr);
1418 for (i = 0; i < n; i++)
1420 e = TREE_OPERAND (expr, i);
1421 se = simplify_replace_tree (e, old, new_tree);
1426 ret = copy_node (expr);
1428 TREE_OPERAND (ret, i) = se;
1431 return (ret ? fold (ret) : expr);
1434 /* Expand definitions of ssa names in EXPR as long as they are simple
1435 enough, and return the new expression. */
1438 expand_simple_operations (tree expr)
1441 tree ret = NULL_TREE, e, ee, e1;
1442 enum tree_code code;
1445 if (expr == NULL_TREE)
1448 if (is_gimple_min_invariant (expr))
1451 code = TREE_CODE (expr);
1452 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
1454 n = TREE_OPERAND_LENGTH (expr);
1455 for (i = 0; i < n; i++)
1457 e = TREE_OPERAND (expr, i);
1458 ee = expand_simple_operations (e);
1463 ret = copy_node (expr);
1465 TREE_OPERAND (ret, i) = ee;
1471 fold_defer_overflow_warnings ();
1473 fold_undefer_and_ignore_overflow_warnings ();
1477 if (TREE_CODE (expr) != SSA_NAME)
1480 stmt = SSA_NAME_DEF_STMT (expr);
1481 if (gimple_code (stmt) == GIMPLE_PHI)
1483 basic_block src, dest;
1485 if (gimple_phi_num_args (stmt) != 1)
1487 e = PHI_ARG_DEF (stmt, 0);
1489 /* Avoid propagating through loop exit phi nodes, which
1490 could break loop-closed SSA form restrictions. */
1491 dest = gimple_bb (stmt);
1492 src = single_pred (dest);
1493 if (TREE_CODE (e) == SSA_NAME
1494 && src->loop_father != dest->loop_father)
1497 return expand_simple_operations (e);
1499 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1502 e = gimple_assign_rhs1 (stmt);
1503 code = gimple_assign_rhs_code (stmt);
1504 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1506 if (is_gimple_min_invariant (e))
1509 if (code == SSA_NAME)
1510 return expand_simple_operations (e);
1518 /* Casts are simple. */
1519 ee = expand_simple_operations (e);
1520 return fold_build1 (code, TREE_TYPE (expr), ee);
1524 case POINTER_PLUS_EXPR:
1525 /* And increments and decrements by a constant are simple. */
1526 e1 = gimple_assign_rhs2 (stmt);
1527 if (!is_gimple_min_invariant (e1))
1530 ee = expand_simple_operations (e);
1531 return fold_build2 (code, TREE_TYPE (expr), ee, e1);
1538 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1539 expression (or EXPR unchanged, if no simplification was possible). */
1542 tree_simplify_using_condition_1 (tree cond, tree expr)
1545 tree e, te, e0, e1, e2, notcond;
1546 enum tree_code code = TREE_CODE (expr);
1548 if (code == INTEGER_CST)
1551 if (code == TRUTH_OR_EXPR
1552 || code == TRUTH_AND_EXPR
1553 || code == COND_EXPR)
1557 e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0));
1558 if (TREE_OPERAND (expr, 0) != e0)
1561 e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1));
1562 if (TREE_OPERAND (expr, 1) != e1)
1565 if (code == COND_EXPR)
1567 e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2));
1568 if (TREE_OPERAND (expr, 2) != e2)
1576 if (code == COND_EXPR)
1577 expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
1579 expr = fold_build2 (code, boolean_type_node, e0, e1);
1585 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
1586 propagation, and vice versa. Fold does not handle this, since it is
1587 considered too expensive. */
1588 if (TREE_CODE (cond) == EQ_EXPR)
1590 e0 = TREE_OPERAND (cond, 0);
1591 e1 = TREE_OPERAND (cond, 1);
1593 /* We know that e0 == e1. Check whether we cannot simplify expr
1595 e = simplify_replace_tree (expr, e0, e1);
1596 if (integer_zerop (e) || integer_nonzerop (e))
1599 e = simplify_replace_tree (expr, e1, e0);
1600 if (integer_zerop (e) || integer_nonzerop (e))
1603 if (TREE_CODE (expr) == EQ_EXPR)
1605 e0 = TREE_OPERAND (expr, 0);
1606 e1 = TREE_OPERAND (expr, 1);
1608 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
1609 e = simplify_replace_tree (cond, e0, e1);
1610 if (integer_zerop (e))
1612 e = simplify_replace_tree (cond, e1, e0);
1613 if (integer_zerop (e))
1616 if (TREE_CODE (expr) == NE_EXPR)
1618 e0 = TREE_OPERAND (expr, 0);
1619 e1 = TREE_OPERAND (expr, 1);
1621 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
1622 e = simplify_replace_tree (cond, e0, e1);
1623 if (integer_zerop (e))
1624 return boolean_true_node;
1625 e = simplify_replace_tree (cond, e1, e0);
1626 if (integer_zerop (e))
1627 return boolean_true_node;
1630 te = expand_simple_operations (expr);
1632 /* Check whether COND ==> EXPR. */
1633 notcond = invert_truthvalue (cond);
1634 e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te);
1635 if (e && integer_nonzerop (e))
1638 /* Check whether COND ==> not EXPR. */
1639 e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te);
1640 if (e && integer_zerop (e))
1646 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1647 expression (or EXPR unchanged, if no simplification was possible).
1648 Wrapper around tree_simplify_using_condition_1 that ensures that chains
1649 of simple operations in definitions of ssa names in COND are expanded,
1650 so that things like casts or incrementing the value of the bound before
1651 the loop do not cause us to fail. */
1654 tree_simplify_using_condition (tree cond, tree expr)
1656 cond = expand_simple_operations (cond);
1658 return tree_simplify_using_condition_1 (cond, expr);
1661 /* Tries to simplify EXPR using the conditions on entry to LOOP.
1662 Returns the simplified expression (or EXPR unchanged, if no
1663 simplification was possible).*/
1666 simplify_using_initial_conditions (struct loop *loop, tree expr)
1674 if (TREE_CODE (expr) == INTEGER_CST)
1677 /* Limit walking the dominators to avoid quadraticness in
1678 the number of BBs times the number of loops in degenerate
1680 for (bb = loop->header;
1681 bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK;
1682 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1684 if (!single_pred_p (bb))
1686 e = single_pred_edge (bb);
1688 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
1691 stmt = last_stmt (e->src);
1692 cond = fold_build2 (gimple_cond_code (stmt),
1694 gimple_cond_lhs (stmt),
1695 gimple_cond_rhs (stmt));
1696 if (e->flags & EDGE_FALSE_VALUE)
1697 cond = invert_truthvalue (cond);
1698 expr = tree_simplify_using_condition (cond, expr);
1705 /* Tries to simplify EXPR using the evolutions of the loop invariants
1706 in the superloops of LOOP. Returns the simplified expression
1707 (or EXPR unchanged, if no simplification was possible). */
1710 simplify_using_outer_evolutions (struct loop *loop, tree expr)
1712 enum tree_code code = TREE_CODE (expr);
1716 if (is_gimple_min_invariant (expr))
1719 if (code == TRUTH_OR_EXPR
1720 || code == TRUTH_AND_EXPR
1721 || code == COND_EXPR)
1725 e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
1726 if (TREE_OPERAND (expr, 0) != e0)
1729 e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
1730 if (TREE_OPERAND (expr, 1) != e1)
1733 if (code == COND_EXPR)
1735 e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
1736 if (TREE_OPERAND (expr, 2) != e2)
1744 if (code == COND_EXPR)
1745 expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
1747 expr = fold_build2 (code, boolean_type_node, e0, e1);
1753 e = instantiate_parameters (loop, expr);
1754 if (is_gimple_min_invariant (e))
1760 /* Returns true if EXIT is the only possible exit from LOOP. */
1763 loop_only_exit_p (const struct loop *loop, const_edge exit)
1766 gimple_stmt_iterator bsi;
1770 if (exit != single_exit (loop))
1773 body = get_loop_body (loop);
1774 for (i = 0; i < loop->num_nodes; i++)
1776 for (bsi = gsi_start_bb (body[i]); !gsi_end_p (bsi); gsi_next (&bsi))
1778 call = gsi_stmt (bsi);
1779 if (gimple_code (call) != GIMPLE_CALL)
1782 if (gimple_has_side_effects (call))
1794 /* Stores description of number of iterations of LOOP derived from
1795 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
1796 useful information could be derived (and fields of NITER has
1797 meaning described in comments at struct tree_niter_desc
1798 declaration), false otherwise. If WARN is true and
1799 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1800 potentially unsafe assumptions. */
1803 number_of_iterations_exit (struct loop *loop, edge exit,
1804 struct tree_niter_desc *niter,
1810 enum tree_code code;
1813 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
1816 niter->assumptions = boolean_false_node;
1817 stmt = last_stmt (exit->src);
1818 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
1821 /* We want the condition for staying inside loop. */
1822 code = gimple_cond_code (stmt);
1823 if (exit->flags & EDGE_TRUE_VALUE)
1824 code = invert_tree_comparison (code, false);
1839 op0 = gimple_cond_lhs (stmt);
1840 op1 = gimple_cond_rhs (stmt);
1841 type = TREE_TYPE (op0);
1843 if (TREE_CODE (type) != INTEGER_TYPE
1844 && !POINTER_TYPE_P (type))
1847 if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, false))
1849 if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, false))
1852 /* We don't want to see undefined signed overflow warnings while
1853 computing the number of iterations. */
1854 fold_defer_overflow_warnings ();
1856 iv0.base = expand_simple_operations (iv0.base);
1857 iv1.base = expand_simple_operations (iv1.base);
1858 if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter,
1859 loop_only_exit_p (loop, exit)))
1861 fold_undefer_and_ignore_overflow_warnings ();
1867 niter->assumptions = simplify_using_outer_evolutions (loop,
1868 niter->assumptions);
1869 niter->may_be_zero = simplify_using_outer_evolutions (loop,
1870 niter->may_be_zero);
1871 niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
1875 = simplify_using_initial_conditions (loop,
1876 niter->assumptions);
1878 = simplify_using_initial_conditions (loop,
1879 niter->may_be_zero);
1881 fold_undefer_and_ignore_overflow_warnings ();
1883 if (integer_onep (niter->assumptions))
1886 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1887 But if we can prove that there is overflow or some other source of weird
1888 behavior, ignore the loop even with -funsafe-loop-optimizations. */
1889 if (integer_zerop (niter->assumptions) || !single_exit (loop))
1892 if (flag_unsafe_loop_optimizations)
1893 niter->assumptions = boolean_true_node;
1897 const char *wording;
1898 location_t loc = gimple_location (stmt);
1900 /* We can provide a more specific warning if one of the operator is
1901 constant and the other advances by +1 or -1. */
1902 if (!integer_zerop (iv1.step)
1903 ? (integer_zerop (iv0.step)
1904 && (integer_onep (iv1.step) || integer_all_onesp (iv1.step)))
1905 : (integer_onep (iv0.step) || integer_all_onesp (iv0.step)))
1907 flag_unsafe_loop_optimizations
1908 ? N_("assuming that the loop is not infinite")
1909 : N_("cannot optimize possibly infinite loops");
1912 flag_unsafe_loop_optimizations
1913 ? N_("assuming that the loop counter does not overflow")
1914 : N_("cannot optimize loop, the loop counter may overflow");
1916 warning_at ((LOCATION_LINE (loc) > 0) ? loc : input_location,
1917 OPT_Wunsafe_loop_optimizations, "%s", gettext (wording));
1920 return flag_unsafe_loop_optimizations;
1923 /* Try to determine the number of iterations of LOOP. If we succeed,
1924 expression giving number of iterations is returned and *EXIT is
1925 set to the edge from that the information is obtained. Otherwise
1926 chrec_dont_know is returned. */
1929 find_loop_niter (struct loop *loop, edge *exit)
1932 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1934 tree niter = NULL_TREE, aniter;
1935 struct tree_niter_desc desc;
1938 FOR_EACH_VEC_ELT (edge, exits, i, ex)
1940 if (!just_once_each_iteration_p (loop, ex->src))
1943 if (!number_of_iterations_exit (loop, ex, &desc, false))
1946 if (integer_nonzerop (desc.may_be_zero))
1948 /* We exit in the first iteration through this exit.
1949 We won't find anything better. */
1950 niter = build_int_cst (unsigned_type_node, 0);
1955 if (!integer_zerop (desc.may_be_zero))
1958 aniter = desc.niter;
1962 /* Nothing recorded yet. */
1968 /* Prefer constants, the lower the better. */
1969 if (TREE_CODE (aniter) != INTEGER_CST)
1972 if (TREE_CODE (niter) != INTEGER_CST)
1979 if (tree_int_cst_lt (aniter, niter))
1986 VEC_free (edge, heap, exits);
1988 return niter ? niter : chrec_dont_know;
1991 /* Return true if loop is known to have bounded number of iterations. */
1994 finite_loop_p (struct loop *loop)
1997 VEC (edge, heap) *exits;
1999 struct tree_niter_desc desc;
2000 bool finite = false;
2003 if (flag_unsafe_loop_optimizations)
2005 flags = flags_from_decl_or_type (current_function_decl);
2006 if ((flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE))
2008 if (dump_file && (dump_flags & TDF_DETAILS))
2009 fprintf (dump_file, "Found loop %i to be finite: it is within pure or const function.\n",
2014 exits = get_loop_exit_edges (loop);
2015 FOR_EACH_VEC_ELT (edge, exits, i, ex)
2017 if (!just_once_each_iteration_p (loop, ex->src))
2020 if (number_of_iterations_exit (loop, ex, &desc, false))
2022 if (dump_file && (dump_flags & TDF_DETAILS))
2024 fprintf (dump_file, "Found loop %i to be finite: iterating ", loop->num);
2025 print_generic_expr (dump_file, desc.niter, TDF_SLIM);
2026 fprintf (dump_file, " times\n");
2032 VEC_free (edge, heap, exits);
2038 Analysis of a number of iterations of a loop by a brute-force evaluation.
2042 /* Bound on the number of iterations we try to evaluate. */
2044 #define MAX_ITERATIONS_TO_TRACK \
2045 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
2047 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
2048 result by a chain of operations such that all but exactly one of their
2049 operands are constants. */
2052 chain_of_csts_start (struct loop *loop, tree x)
2054 gimple stmt = SSA_NAME_DEF_STMT (x);
2056 basic_block bb = gimple_bb (stmt);
2057 enum tree_code code;
2060 || !flow_bb_inside_loop_p (loop, bb))
2063 if (gimple_code (stmt) == GIMPLE_PHI)
2065 if (bb == loop->header)
2071 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2074 code = gimple_assign_rhs_code (stmt);
2075 if (gimple_references_memory_p (stmt)
2076 || TREE_CODE_CLASS (code) == tcc_reference
2077 || (code == ADDR_EXPR
2078 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
2081 use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
2082 if (use == NULL_TREE)
2085 return chain_of_csts_start (loop, use);
2088 /* Determines whether the expression X is derived from a result of a phi node
2089 in header of LOOP such that
2091 * the derivation of X consists only from operations with constants
2092 * the initial value of the phi node is constant
2093 * the value of the phi node in the next iteration can be derived from the
2094 value in the current iteration by a chain of operations with constants.
2096 If such phi node exists, it is returned, otherwise NULL is returned. */
2099 get_base_for (struct loop *loop, tree x)
2104 if (is_gimple_min_invariant (x))
2107 phi = chain_of_csts_start (loop, x);
2111 init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
2112 next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
2114 if (TREE_CODE (next) != SSA_NAME)
2117 if (!is_gimple_min_invariant (init))
2120 if (chain_of_csts_start (loop, next) != phi)
2126 /* Given an expression X, then
2128 * if X is NULL_TREE, we return the constant BASE.
2129 * otherwise X is a SSA name, whose value in the considered loop is derived
2130 by a chain of operations with constant from a result of a phi node in
2131 the header of the loop. Then we return value of X when the value of the
2132 result of this phi node is given by the constant BASE. */
2135 get_val_for (tree x, tree base)
2139 gcc_assert (is_gimple_min_invariant (base));
2144 stmt = SSA_NAME_DEF_STMT (x);
2145 if (gimple_code (stmt) == GIMPLE_PHI)
2148 gcc_assert (is_gimple_assign (stmt));
2150 /* STMT must be either an assignment of a single SSA name or an
2151 expression involving an SSA name and a constant. Try to fold that
2152 expression using the value for the SSA name. */
2153 if (gimple_assign_ssa_name_copy_p (stmt))
2154 return get_val_for (gimple_assign_rhs1 (stmt), base);
2155 else if (gimple_assign_rhs_class (stmt) == GIMPLE_UNARY_RHS
2156 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
2158 return fold_build1 (gimple_assign_rhs_code (stmt),
2159 gimple_expr_type (stmt),
2160 get_val_for (gimple_assign_rhs1 (stmt), base));
2162 else if (gimple_assign_rhs_class (stmt) == GIMPLE_BINARY_RHS)
2164 tree rhs1 = gimple_assign_rhs1 (stmt);
2165 tree rhs2 = gimple_assign_rhs2 (stmt);
2166 if (TREE_CODE (rhs1) == SSA_NAME)
2167 rhs1 = get_val_for (rhs1, base);
2168 else if (TREE_CODE (rhs2) == SSA_NAME)
2169 rhs2 = get_val_for (rhs2, base);
2172 return fold_build2 (gimple_assign_rhs_code (stmt),
2173 gimple_expr_type (stmt), rhs1, rhs2);
2180 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2181 by brute force -- i.e. by determining the value of the operands of the
2182 condition at EXIT in first few iterations of the loop (assuming that
2183 these values are constant) and determining the first one in that the
2184 condition is not satisfied. Returns the constant giving the number
2185 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
2188 loop_niter_by_eval (struct loop *loop, edge exit)
2191 tree op[2], val[2], next[2], aval[2];
2196 cond = last_stmt (exit->src);
2197 if (!cond || gimple_code (cond) != GIMPLE_COND)
2198 return chrec_dont_know;
2200 cmp = gimple_cond_code (cond);
2201 if (exit->flags & EDGE_TRUE_VALUE)
2202 cmp = invert_tree_comparison (cmp, false);
2212 op[0] = gimple_cond_lhs (cond);
2213 op[1] = gimple_cond_rhs (cond);
2217 return chrec_dont_know;
2220 for (j = 0; j < 2; j++)
2222 if (is_gimple_min_invariant (op[j]))
2225 next[j] = NULL_TREE;
2230 phi = get_base_for (loop, op[j]);
2232 return chrec_dont_know;
2233 val[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
2234 next[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
2238 /* Don't issue signed overflow warnings. */
2239 fold_defer_overflow_warnings ();
2241 for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
2243 for (j = 0; j < 2; j++)
2244 aval[j] = get_val_for (op[j], val[j]);
2246 acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]);
2247 if (acnd && integer_zerop (acnd))
2249 fold_undefer_and_ignore_overflow_warnings ();
2250 if (dump_file && (dump_flags & TDF_DETAILS))
2252 "Proved that loop %d iterates %d times using brute force.\n",
2254 return build_int_cst (unsigned_type_node, i);
2257 for (j = 0; j < 2; j++)
2259 val[j] = get_val_for (next[j], val[j]);
2260 if (!is_gimple_min_invariant (val[j]))
2262 fold_undefer_and_ignore_overflow_warnings ();
2263 return chrec_dont_know;
2268 fold_undefer_and_ignore_overflow_warnings ();
2270 return chrec_dont_know;
2273 /* Finds the exit of the LOOP by that the loop exits after a constant
2274 number of iterations and stores the exit edge to *EXIT. The constant
2275 giving the number of iterations of LOOP is returned. The number of
2276 iterations is determined using loop_niter_by_eval (i.e. by brute force
2277 evaluation). If we are unable to find the exit for that loop_niter_by_eval
2278 determines the number of iterations, chrec_dont_know is returned. */
2281 find_loop_niter_by_eval (struct loop *loop, edge *exit)
2284 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
2286 tree niter = NULL_TREE, aniter;
2290 /* Loops with multiple exits are expensive to handle and less important. */
2291 if (!flag_expensive_optimizations
2292 && VEC_length (edge, exits) > 1)
2293 return chrec_dont_know;
2295 FOR_EACH_VEC_ELT (edge, exits, i, ex)
2297 if (!just_once_each_iteration_p (loop, ex->src))
2300 aniter = loop_niter_by_eval (loop, ex);
2301 if (chrec_contains_undetermined (aniter))
2305 && !tree_int_cst_lt (aniter, niter))
2311 VEC_free (edge, heap, exits);
2313 return niter ? niter : chrec_dont_know;
2318 Analysis of upper bounds on number of iterations of a loop.
2322 static double_int derive_constant_upper_bound_ops (tree, tree,
2323 enum tree_code, tree);
2325 /* Returns a constant upper bound on the value of the right-hand side of
2326 an assignment statement STMT. */
2329 derive_constant_upper_bound_assign (gimple stmt)
2331 enum tree_code code = gimple_assign_rhs_code (stmt);
2332 tree op0 = gimple_assign_rhs1 (stmt);
2333 tree op1 = gimple_assign_rhs2 (stmt);
2335 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt)),
2339 /* Returns a constant upper bound on the value of expression VAL. VAL
2340 is considered to be unsigned. If its type is signed, its value must
2344 derive_constant_upper_bound (tree val)
2346 enum tree_code code;
2349 extract_ops_from_tree (val, &code, &op0, &op1);
2350 return derive_constant_upper_bound_ops (TREE_TYPE (val), op0, code, op1);
2353 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
2354 whose type is TYPE. The expression is considered to be unsigned. If
2355 its type is signed, its value must be nonnegative. */
2358 derive_constant_upper_bound_ops (tree type, tree op0,
2359 enum tree_code code, tree op1)
2362 double_int bnd, max, mmax, cst;
2365 if (INTEGRAL_TYPE_P (type))
2366 maxt = TYPE_MAX_VALUE (type);
2368 maxt = upper_bound_in_type (type, type);
2370 max = tree_to_double_int (maxt);
2375 return tree_to_double_int (op0);
2378 subtype = TREE_TYPE (op0);
2379 if (!TYPE_UNSIGNED (subtype)
2380 /* If TYPE is also signed, the fact that VAL is nonnegative implies
2381 that OP0 is nonnegative. */
2382 && TYPE_UNSIGNED (type)
2383 && !tree_expr_nonnegative_p (op0))
2385 /* If we cannot prove that the casted expression is nonnegative,
2386 we cannot establish more useful upper bound than the precision
2387 of the type gives us. */
2391 /* We now know that op0 is an nonnegative value. Try deriving an upper
2393 bnd = derive_constant_upper_bound (op0);
2395 /* If the bound does not fit in TYPE, max. value of TYPE could be
2397 if (double_int_ucmp (max, bnd) < 0)
2403 case POINTER_PLUS_EXPR:
2405 if (TREE_CODE (op1) != INTEGER_CST
2406 || !tree_expr_nonnegative_p (op0))
2409 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
2410 choose the most logical way how to treat this constant regardless
2411 of the signedness of the type. */
2412 cst = tree_to_double_int (op1);
2413 cst = double_int_sext (cst, TYPE_PRECISION (type));
2414 if (code != MINUS_EXPR)
2415 cst = double_int_neg (cst);
2417 bnd = derive_constant_upper_bound (op0);
2419 if (double_int_negative_p (cst))
2421 cst = double_int_neg (cst);
2422 /* Avoid CST == 0x80000... */
2423 if (double_int_negative_p (cst))
2426 /* OP0 + CST. We need to check that
2427 BND <= MAX (type) - CST. */
2429 mmax = double_int_sub (max, cst);
2430 if (double_int_ucmp (bnd, mmax) > 0)
2433 return double_int_add (bnd, cst);
2437 /* OP0 - CST, where CST >= 0.
2439 If TYPE is signed, we have already verified that OP0 >= 0, and we
2440 know that the result is nonnegative. This implies that
2443 If TYPE is unsigned, we must additionally know that OP0 >= CST,
2444 otherwise the operation underflows.
2447 /* This should only happen if the type is unsigned; however, for
2448 buggy programs that use overflowing signed arithmetics even with
2449 -fno-wrapv, this condition may also be true for signed values. */
2450 if (double_int_ucmp (bnd, cst) < 0)
2453 if (TYPE_UNSIGNED (type))
2455 tree tem = fold_binary (GE_EXPR, boolean_type_node, op0,
2456 double_int_to_tree (type, cst));
2457 if (!tem || integer_nonzerop (tem))
2461 bnd = double_int_sub (bnd, cst);
2466 case FLOOR_DIV_EXPR:
2467 case EXACT_DIV_EXPR:
2468 if (TREE_CODE (op1) != INTEGER_CST
2469 || tree_int_cst_sign_bit (op1))
2472 bnd = derive_constant_upper_bound (op0);
2473 return double_int_udiv (bnd, tree_to_double_int (op1), FLOOR_DIV_EXPR);
2476 if (TREE_CODE (op1) != INTEGER_CST
2477 || tree_int_cst_sign_bit (op1))
2479 return tree_to_double_int (op1);
2482 stmt = SSA_NAME_DEF_STMT (op0);
2483 if (gimple_code (stmt) != GIMPLE_ASSIGN
2484 || gimple_assign_lhs (stmt) != op0)
2486 return derive_constant_upper_bound_assign (stmt);
2493 /* Records that every statement in LOOP is executed I_BOUND times.
2494 REALISTIC is true if I_BOUND is expected to be close to the real number
2495 of iterations. UPPER is true if we are sure the loop iterates at most
2499 record_niter_bound (struct loop *loop, double_int i_bound, bool realistic,
2502 /* Update the bounds only when there is no previous estimation, or when the current
2503 estimation is smaller. */
2505 && (!loop->any_upper_bound
2506 || double_int_ucmp (i_bound, loop->nb_iterations_upper_bound) < 0))
2508 loop->any_upper_bound = true;
2509 loop->nb_iterations_upper_bound = i_bound;
2512 && (!loop->any_estimate
2513 || double_int_ucmp (i_bound, loop->nb_iterations_estimate) < 0))
2515 loop->any_estimate = true;
2516 loop->nb_iterations_estimate = i_bound;
2520 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
2521 is true if the loop is exited immediately after STMT, and this exit
2522 is taken at last when the STMT is executed BOUND + 1 times.
2523 REALISTIC is true if BOUND is expected to be close to the real number
2524 of iterations. UPPER is true if we are sure the loop iterates at most
2525 BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */
2528 record_estimate (struct loop *loop, tree bound, double_int i_bound,
2529 gimple at_stmt, bool is_exit, bool realistic, bool upper)
2534 if (dump_file && (dump_flags & TDF_DETAILS))
2536 fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : "");
2537 print_gimple_stmt (dump_file, at_stmt, 0, TDF_SLIM);
2538 fprintf (dump_file, " is %sexecuted at most ",
2539 upper ? "" : "probably ");
2540 print_generic_expr (dump_file, bound, TDF_SLIM);
2541 fprintf (dump_file, " (bounded by ");
2542 dump_double_int (dump_file, i_bound, true);
2543 fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num);
2546 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
2547 real number of iterations. */
2548 if (TREE_CODE (bound) != INTEGER_CST)
2550 if (!upper && !realistic)
2553 /* If we have a guaranteed upper bound, record it in the appropriate
2557 struct nb_iter_bound *elt = ggc_alloc_nb_iter_bound ();
2559 elt->bound = i_bound;
2560 elt->stmt = at_stmt;
2561 elt->is_exit = is_exit;
2562 elt->next = loop->bounds;
2566 /* Update the number of iteration estimates according to the bound.
2567 If at_stmt is an exit or dominates the single exit from the loop,
2568 then the loop latch is executed at most BOUND times, otherwise
2569 it can be executed BOUND + 1 times. */
2570 exit = single_exit (loop);
2573 && dominated_by_p (CDI_DOMINATORS,
2574 exit->src, gimple_bb (at_stmt))))
2575 delta = double_int_zero;
2577 delta = double_int_one;
2578 i_bound = double_int_add (i_bound, delta);
2580 /* If an overflow occurred, ignore the result. */
2581 if (double_int_ucmp (i_bound, delta) < 0)
2584 record_niter_bound (loop, i_bound, realistic, upper);
2587 /* Record the estimate on number of iterations of LOOP based on the fact that
2588 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
2589 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
2590 estimated number of iterations is expected to be close to the real one.
2591 UPPER is true if we are sure the induction variable does not wrap. */
2594 record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple stmt,
2595 tree low, tree high, bool realistic, bool upper)
2597 tree niter_bound, extreme, delta;
2598 tree type = TREE_TYPE (base), unsigned_type;
2601 if (TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
2604 if (dump_file && (dump_flags & TDF_DETAILS))
2606 fprintf (dump_file, "Induction variable (");
2607 print_generic_expr (dump_file, TREE_TYPE (base), TDF_SLIM);
2608 fprintf (dump_file, ") ");
2609 print_generic_expr (dump_file, base, TDF_SLIM);
2610 fprintf (dump_file, " + ");
2611 print_generic_expr (dump_file, step, TDF_SLIM);
2612 fprintf (dump_file, " * iteration does not wrap in statement ");
2613 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2614 fprintf (dump_file, " in loop %d.\n", loop->num);
2617 unsigned_type = unsigned_type_for (type);
2618 base = fold_convert (unsigned_type, base);
2619 step = fold_convert (unsigned_type, step);
2621 if (tree_int_cst_sign_bit (step))
2623 extreme = fold_convert (unsigned_type, low);
2624 if (TREE_CODE (base) != INTEGER_CST)
2625 base = fold_convert (unsigned_type, high);
2626 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
2627 step = fold_build1 (NEGATE_EXPR, unsigned_type, step);
2631 extreme = fold_convert (unsigned_type, high);
2632 if (TREE_CODE (base) != INTEGER_CST)
2633 base = fold_convert (unsigned_type, low);
2634 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
2637 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
2638 would get out of the range. */
2639 niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step);
2640 max = derive_constant_upper_bound (niter_bound);
2641 record_estimate (loop, niter_bound, max, stmt, false, realistic, upper);
2644 /* Returns true if REF is a reference to an array at the end of a dynamically
2645 allocated structure. If this is the case, the array may be allocated larger
2646 than its upper bound implies. */
2649 array_at_struct_end_p (tree ref)
2651 tree base = get_base_address (ref);
2654 /* Unless the reference is through a pointer, the size of the array matches
2656 if (!base || (!INDIRECT_REF_P (base) && TREE_CODE (base) != MEM_REF))
2659 for (;handled_component_p (ref); ref = parent)
2661 parent = TREE_OPERAND (ref, 0);
2663 if (TREE_CODE (ref) == COMPONENT_REF)
2665 /* All fields of a union are at its end. */
2666 if (TREE_CODE (TREE_TYPE (parent)) == UNION_TYPE)
2669 /* Unless the field is at the end of the struct, we are done. */
2670 field = TREE_OPERAND (ref, 1);
2671 if (DECL_CHAIN (field))
2675 /* The other options are ARRAY_REF, ARRAY_RANGE_REF, VIEW_CONVERT_EXPR.
2676 In all these cases, we might be accessing the last element, and
2677 although in practice this will probably never happen, it is legal for
2678 the indices of this last element to exceed the bounds of the array.
2679 Therefore, continue checking. */
2685 /* Determine information about number of iterations a LOOP from the index
2686 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
2687 guaranteed to be executed in every iteration of LOOP. Callback for
2698 idx_infer_loop_bounds (tree base, tree *idx, void *dta)
2700 struct ilb_data *data = (struct ilb_data *) dta;
2701 tree ev, init, step;
2702 tree low, high, type, next;
2703 bool sign, upper = data->reliable, at_end = false;
2704 struct loop *loop = data->loop;
2706 if (TREE_CODE (base) != ARRAY_REF)
2709 /* For arrays at the end of the structure, we are not guaranteed that they
2710 do not really extend over their declared size. However, for arrays of
2711 size greater than one, this is unlikely to be intended. */
2712 if (array_at_struct_end_p (base))
2718 ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx));
2719 init = initial_condition (ev);
2720 step = evolution_part_in_loop_num (ev, loop->num);
2724 || TREE_CODE (step) != INTEGER_CST
2725 || integer_zerop (step)
2726 || tree_contains_chrecs (init, NULL)
2727 || chrec_contains_symbols_defined_in_loop (init, loop->num))
2730 low = array_ref_low_bound (base);
2731 high = array_ref_up_bound (base);
2733 /* The case of nonconstant bounds could be handled, but it would be
2735 if (TREE_CODE (low) != INTEGER_CST
2737 || TREE_CODE (high) != INTEGER_CST)
2739 sign = tree_int_cst_sign_bit (step);
2740 type = TREE_TYPE (step);
2742 /* The array of length 1 at the end of a structure most likely extends
2743 beyond its bounds. */
2745 && operand_equal_p (low, high, 0))
2748 /* In case the relevant bound of the array does not fit in type, or
2749 it does, but bound + step (in type) still belongs into the range of the
2750 array, the index may wrap and still stay within the range of the array
2751 (consider e.g. if the array is indexed by the full range of
2754 To make things simpler, we require both bounds to fit into type, although
2755 there are cases where this would not be strictly necessary. */
2756 if (!int_fits_type_p (high, type)
2757 || !int_fits_type_p (low, type))
2759 low = fold_convert (type, low);
2760 high = fold_convert (type, high);
2763 next = fold_binary (PLUS_EXPR, type, low, step);
2765 next = fold_binary (PLUS_EXPR, type, high, step);
2767 if (tree_int_cst_compare (low, next) <= 0
2768 && tree_int_cst_compare (next, high) <= 0)
2771 record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true, upper);
2775 /* Determine information about number of iterations a LOOP from the bounds
2776 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
2777 STMT is guaranteed to be executed in every iteration of LOOP.*/
2780 infer_loop_bounds_from_ref (struct loop *loop, gimple stmt, tree ref,
2783 struct ilb_data data;
2787 data.reliable = reliable;
2788 for_each_index (&ref, idx_infer_loop_bounds, &data);
2791 /* Determine information about number of iterations of a LOOP from the way
2792 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
2793 executed in every iteration of LOOP. */
2796 infer_loop_bounds_from_array (struct loop *loop, gimple stmt, bool reliable)
2798 if (is_gimple_assign (stmt))
2800 tree op0 = gimple_assign_lhs (stmt);
2801 tree op1 = gimple_assign_rhs1 (stmt);
2803 /* For each memory access, analyze its access function
2804 and record a bound on the loop iteration domain. */
2805 if (REFERENCE_CLASS_P (op0))
2806 infer_loop_bounds_from_ref (loop, stmt, op0, reliable);
2808 if (REFERENCE_CLASS_P (op1))
2809 infer_loop_bounds_from_ref (loop, stmt, op1, reliable);
2811 else if (is_gimple_call (stmt))
2814 unsigned i, n = gimple_call_num_args (stmt);
2816 lhs = gimple_call_lhs (stmt);
2817 if (lhs && REFERENCE_CLASS_P (lhs))
2818 infer_loop_bounds_from_ref (loop, stmt, lhs, reliable);
2820 for (i = 0; i < n; i++)
2822 arg = gimple_call_arg (stmt, i);
2823 if (REFERENCE_CLASS_P (arg))
2824 infer_loop_bounds_from_ref (loop, stmt, arg, reliable);
2829 /* Determine information about number of iterations of a LOOP from the fact
2830 that pointer arithmetics in STMT does not overflow. */
2833 infer_loop_bounds_from_pointer_arith (struct loop *loop, gimple stmt)
2835 tree def, base, step, scev, type, low, high;
2838 if (!is_gimple_assign (stmt)
2839 || gimple_assign_rhs_code (stmt) != POINTER_PLUS_EXPR)
2842 def = gimple_assign_lhs (stmt);
2843 if (TREE_CODE (def) != SSA_NAME)
2846 type = TREE_TYPE (def);
2847 if (!nowrap_type_p (type))
2850 ptr = gimple_assign_rhs1 (stmt);
2851 if (!expr_invariant_in_loop_p (loop, ptr))
2854 var = gimple_assign_rhs2 (stmt);
2855 if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (var)))
2858 scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
2859 if (chrec_contains_undetermined (scev))
2862 base = initial_condition_in_loop_num (scev, loop->num);
2863 step = evolution_part_in_loop_num (scev, loop->num);
2866 || TREE_CODE (step) != INTEGER_CST
2867 || tree_contains_chrecs (base, NULL)
2868 || chrec_contains_symbols_defined_in_loop (base, loop->num))
2871 low = lower_bound_in_type (type, type);
2872 high = upper_bound_in_type (type, type);
2874 /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
2875 produce a NULL pointer. The contrary would mean NULL points to an object,
2876 while NULL is supposed to compare unequal with the address of all objects.
2877 Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
2878 NULL pointer since that would mean wrapping, which we assume here not to
2879 happen. So, we can exclude NULL from the valid range of pointer
2881 if (flag_delete_null_pointer_checks && int_cst_value (low) == 0)
2882 low = build_int_cstu (TREE_TYPE (low), TYPE_ALIGN_UNIT (TREE_TYPE (type)));
2884 record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
2887 /* Determine information about number of iterations of a LOOP from the fact
2888 that signed arithmetics in STMT does not overflow. */
2891 infer_loop_bounds_from_signedness (struct loop *loop, gimple stmt)
2893 tree def, base, step, scev, type, low, high;
2895 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2898 def = gimple_assign_lhs (stmt);
2900 if (TREE_CODE (def) != SSA_NAME)
2903 type = TREE_TYPE (def);
2904 if (!INTEGRAL_TYPE_P (type)
2905 || !TYPE_OVERFLOW_UNDEFINED (type))
2908 scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
2909 if (chrec_contains_undetermined (scev))
2912 base = initial_condition_in_loop_num (scev, loop->num);
2913 step = evolution_part_in_loop_num (scev, loop->num);
2916 || TREE_CODE (step) != INTEGER_CST
2917 || tree_contains_chrecs (base, NULL)
2918 || chrec_contains_symbols_defined_in_loop (base, loop->num))
2921 low = lower_bound_in_type (type, type);
2922 high = upper_bound_in_type (type, type);
2924 record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
2927 /* The following analyzers are extracting informations on the bounds
2928 of LOOP from the following undefined behaviors:
2930 - data references should not access elements over the statically
2933 - signed variables should not overflow when flag_wrapv is not set.
2937 infer_loop_bounds_from_undefined (struct loop *loop)
2941 gimple_stmt_iterator bsi;
2945 bbs = get_loop_body (loop);
2947 for (i = 0; i < loop->num_nodes; i++)
2951 /* If BB is not executed in each iteration of the loop, we cannot
2952 use the operations in it to infer reliable upper bound on the
2953 # of iterations of the loop. However, we can use it as a guess. */
2954 reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb);
2956 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
2958 gimple stmt = gsi_stmt (bsi);
2960 infer_loop_bounds_from_array (loop, stmt, reliable);
2964 infer_loop_bounds_from_signedness (loop, stmt);
2965 infer_loop_bounds_from_pointer_arith (loop, stmt);
2974 /* Converts VAL to double_int. */
2977 gcov_type_to_double_int (gcov_type val)
2981 ret.low = (unsigned HOST_WIDE_INT) val;
2982 /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by
2983 the size of type. */
2984 val >>= HOST_BITS_PER_WIDE_INT - 1;
2986 ret.high = (unsigned HOST_WIDE_INT) val;
2991 /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
2992 is true also use estimates derived from undefined behavior. */
2995 estimate_numbers_of_iterations_loop (struct loop *loop, bool use_undefined_p)
2997 VEC (edge, heap) *exits;
3000 struct tree_niter_desc niter_desc;
3004 /* Give up if we already have tried to compute an estimation. */
3005 if (loop->estimate_state != EST_NOT_COMPUTED)
3007 loop->estimate_state = EST_AVAILABLE;
3008 loop->any_upper_bound = false;
3009 loop->any_estimate = false;
3011 exits = get_loop_exit_edges (loop);
3012 FOR_EACH_VEC_ELT (edge, exits, i, ex)
3014 if (!number_of_iterations_exit (loop, ex, &niter_desc, false))
3017 niter = niter_desc.niter;
3018 type = TREE_TYPE (niter);
3019 if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST)
3020 niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
3021 build_int_cst (type, 0),
3023 record_estimate (loop, niter, niter_desc.max,
3024 last_stmt (ex->src),
3027 VEC_free (edge, heap, exits);
3029 if (use_undefined_p)
3030 infer_loop_bounds_from_undefined (loop);
3032 /* If we have a measured profile, use it to estimate the number of
3034 if (loop->header->count != 0)
3036 gcov_type nit = expected_loop_iterations_unbounded (loop) + 1;
3037 bound = gcov_type_to_double_int (nit);
3038 record_niter_bound (loop, bound, true, false);
3041 /* If an upper bound is smaller than the realistic estimate of the
3042 number of iterations, use the upper bound instead. */
3043 if (loop->any_upper_bound
3044 && loop->any_estimate
3045 && double_int_ucmp (loop->nb_iterations_upper_bound,
3046 loop->nb_iterations_estimate) < 0)
3047 loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
3050 /* Sets NIT to the estimated number of executions of the latch of the
3051 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
3052 large as the number of iterations. If we have no reliable estimate,
3053 the function returns false, otherwise returns true. */
3056 estimated_loop_iterations (struct loop *loop, bool conservative,
3059 estimate_numbers_of_iterations_loop (loop, true);
3062 if (!loop->any_upper_bound)
3065 *nit = loop->nb_iterations_upper_bound;
3069 if (!loop->any_estimate)
3072 *nit = loop->nb_iterations_estimate;
3078 /* Similar to estimated_loop_iterations, but returns the estimate only
3079 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3080 on the number of iterations of LOOP could not be derived, returns -1. */
3083 estimated_loop_iterations_int (struct loop *loop, bool conservative)
3086 HOST_WIDE_INT hwi_nit;
3088 if (!estimated_loop_iterations (loop, conservative, &nit))
3091 if (!double_int_fits_in_shwi_p (nit))
3093 hwi_nit = double_int_to_shwi (nit);
3095 return hwi_nit < 0 ? -1 : hwi_nit;
3098 /* Returns an upper bound on the number of executions of statements
3099 in the LOOP. For statements before the loop exit, this exceeds
3100 the number of execution of the latch by one. */
3103 max_stmt_executions_int (struct loop *loop, bool conservative)
3105 HOST_WIDE_INT nit = estimated_loop_iterations_int (loop, conservative);
3111 snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
3113 /* If the computation overflows, return -1. */
3114 return snit < 0 ? -1 : snit;
3117 /* Sets NIT to the estimated number of executions of the latch of the
3118 LOOP, plus one. If CONSERVATIVE is true, we must be sure that NIT is at
3119 least as large as the number of iterations. If we have no reliable
3120 estimate, the function returns false, otherwise returns true. */
3123 max_stmt_executions (struct loop *loop, bool conservative, double_int *nit)
3125 double_int nit_minus_one;
3127 if (!estimated_loop_iterations (loop, conservative, nit))
3130 nit_minus_one = *nit;
3132 *nit = double_int_add (*nit, double_int_one);
3134 return double_int_ucmp (*nit, nit_minus_one) > 0;
3137 /* Records estimates on numbers of iterations of loops. */
3140 estimate_numbers_of_iterations (bool use_undefined_p)
3145 /* We don't want to issue signed overflow warnings while getting
3146 loop iteration estimates. */
3147 fold_defer_overflow_warnings ();
3149 FOR_EACH_LOOP (li, loop, 0)
3151 estimate_numbers_of_iterations_loop (loop, use_undefined_p);
3154 fold_undefer_and_ignore_overflow_warnings ();
3157 /* Returns true if statement S1 dominates statement S2. */
3160 stmt_dominates_stmt_p (gimple s1, gimple s2)
3162 basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
3170 gimple_stmt_iterator bsi;
3172 if (gimple_code (s2) == GIMPLE_PHI)
3175 if (gimple_code (s1) == GIMPLE_PHI)
3178 for (bsi = gsi_start_bb (bb1); gsi_stmt (bsi) != s2; gsi_next (&bsi))
3179 if (gsi_stmt (bsi) == s1)
3185 return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
3188 /* Returns true when we can prove that the number of executions of
3189 STMT in the loop is at most NITER, according to the bound on
3190 the number of executions of the statement NITER_BOUND->stmt recorded in
3191 NITER_BOUND. If STMT is NULL, we must prove this bound for all
3192 statements in the loop. */
3195 n_of_executions_at_most (gimple stmt,
3196 struct nb_iter_bound *niter_bound,
3199 double_int bound = niter_bound->bound;
3200 tree nit_type = TREE_TYPE (niter), e;
3203 gcc_assert (TYPE_UNSIGNED (nit_type));
3205 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
3206 the number of iterations is small. */
3207 if (!double_int_fits_to_tree_p (nit_type, bound))
3210 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3211 times. This means that:
3213 -- if NITER_BOUND->is_exit is true, then everything before
3214 NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3215 times, and everything after it at most NITER_BOUND->bound times.
3217 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
3218 is executed, then NITER_BOUND->stmt is executed as well in the same
3219 iteration (we conclude that if both statements belong to the same
3220 basic block, or if STMT is after NITER_BOUND->stmt), then STMT
3221 is executed at most NITER_BOUND->bound + 1 times. Otherwise STMT is
3222 executed at most NITER_BOUND->bound + 2 times. */
3224 if (niter_bound->is_exit)
3227 && stmt != niter_bound->stmt
3228 && stmt_dominates_stmt_p (niter_bound->stmt, stmt))
3236 || (gimple_bb (stmt) != gimple_bb (niter_bound->stmt)
3237 && !stmt_dominates_stmt_p (niter_bound->stmt, stmt)))
3239 bound = double_int_add (bound, double_int_one);
3240 if (double_int_zero_p (bound)
3241 || !double_int_fits_to_tree_p (nit_type, bound))
3247 e = fold_binary (cmp, boolean_type_node,
3248 niter, double_int_to_tree (nit_type, bound));
3249 return e && integer_nonzerop (e);
3252 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
3255 nowrap_type_p (tree type)
3257 if (INTEGRAL_TYPE_P (type)
3258 && TYPE_OVERFLOW_UNDEFINED (type))
3261 if (POINTER_TYPE_P (type))
3267 /* Return false only when the induction variable BASE + STEP * I is
3268 known to not overflow: i.e. when the number of iterations is small
3269 enough with respect to the step and initial condition in order to
3270 keep the evolution confined in TYPEs bounds. Return true when the
3271 iv is known to overflow or when the property is not computable.
3273 USE_OVERFLOW_SEMANTICS is true if this function should assume that
3274 the rules for overflow of the given language apply (e.g., that signed
3275 arithmetics in C does not overflow). */
3278 scev_probably_wraps_p (tree base, tree step,
3279 gimple at_stmt, struct loop *loop,
3280 bool use_overflow_semantics)
3282 struct nb_iter_bound *bound;
3283 tree delta, step_abs;
3284 tree unsigned_type, valid_niter;
3285 tree type = TREE_TYPE (step);
3287 /* FIXME: We really need something like
3288 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
3290 We used to test for the following situation that frequently appears
3291 during address arithmetics:
3293 D.1621_13 = (long unsigned intD.4) D.1620_12;
3294 D.1622_14 = D.1621_13 * 8;
3295 D.1623_15 = (doubleD.29 *) D.1622_14;
3297 And derived that the sequence corresponding to D_14
3298 can be proved to not wrap because it is used for computing a
3299 memory access; however, this is not really the case -- for example,
3300 if D_12 = (unsigned char) [254,+,1], then D_14 has values
3301 2032, 2040, 0, 8, ..., but the code is still legal. */
3303 if (chrec_contains_undetermined (base)
3304 || chrec_contains_undetermined (step))
3307 if (integer_zerop (step))
3310 /* If we can use the fact that signed and pointer arithmetics does not
3311 wrap, we are done. */
3312 if (use_overflow_semantics && nowrap_type_p (TREE_TYPE (base)))
3315 /* To be able to use estimates on number of iterations of the loop,
3316 we must have an upper bound on the absolute value of the step. */
3317 if (TREE_CODE (step) != INTEGER_CST)
3320 /* Don't issue signed overflow warnings. */
3321 fold_defer_overflow_warnings ();
3323 /* Otherwise, compute the number of iterations before we reach the
3324 bound of the type, and verify that the loop is exited before this
3326 unsigned_type = unsigned_type_for (type);
3327 base = fold_convert (unsigned_type, base);
3329 if (tree_int_cst_sign_bit (step))
3331 tree extreme = fold_convert (unsigned_type,
3332 lower_bound_in_type (type, type));
3333 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
3334 step_abs = fold_build1 (NEGATE_EXPR, unsigned_type,
3335 fold_convert (unsigned_type, step));
3339 tree extreme = fold_convert (unsigned_type,
3340 upper_bound_in_type (type, type));
3341 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
3342 step_abs = fold_convert (unsigned_type, step);
3345 valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
3347 estimate_numbers_of_iterations_loop (loop, true);
3348 for (bound = loop->bounds; bound; bound = bound->next)
3350 if (n_of_executions_at_most (at_stmt, bound, valid_niter))
3352 fold_undefer_and_ignore_overflow_warnings ();
3357 fold_undefer_and_ignore_overflow_warnings ();
3359 /* At this point we still don't have a proof that the iv does not
3360 overflow: give up. */
3364 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
3367 free_numbers_of_iterations_estimates_loop (struct loop *loop)
3369 struct nb_iter_bound *bound, *next;
3371 loop->nb_iterations = NULL;
3372 loop->estimate_state = EST_NOT_COMPUTED;
3373 for (bound = loop->bounds; bound; bound = next)
3379 loop->bounds = NULL;
3382 /* Frees the information on upper bounds on numbers of iterations of loops. */
3385 free_numbers_of_iterations_estimates (void)
3390 FOR_EACH_LOOP (li, loop, 0)
3392 free_numbers_of_iterations_estimates_loop (loop);
3396 /* Substitute value VAL for ssa name NAME inside expressions held
3400 substitute_in_loop_info (struct loop *loop, tree name, tree val)
3402 loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);