1 /* Functions to determine/estimate number of iterations of a loop.
2 Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
23 #include "coretypes.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
31 #include "diagnostic.h"
33 #include "tree-flow.h"
34 #include "tree-dump.h"
36 #include "tree-pass.h"
38 #include "tree-chrec.h"
39 #include "tree-scalar-evolution.h"
40 #include "tree-data-ref.h"
44 #include "tree-inline.h"
47 #define SWAP(X, Y) do { void *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 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 = double_int_sext (tree_to_double_int (op1),
97 TYPE_PRECISION (type));
98 mpz_set_double_int (offset, off, false);
102 *var = build_int_cst_type (type, 0);
103 off = tree_to_double_int (expr);
104 mpz_set_double_int (offset, off, TYPE_UNSIGNED (type));
112 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
113 in TYPE to MIN and MAX. */
116 determine_value_range (tree type, tree var, mpz_t off,
117 mpz_t min, mpz_t max)
119 /* If the expression is a constant, we know its value exactly. */
120 if (integer_zerop (var))
127 /* If the computation may wrap, we know nothing about the value, except for
128 the range of the type. */
129 get_type_static_bounds (type, min, max);
130 if (!nowrap_type_p (type))
133 /* Since the addition of OFF does not wrap, if OFF is positive, then we may
134 add it to MIN, otherwise to MAX. */
135 if (mpz_sgn (off) < 0)
136 mpz_add (max, max, off);
138 mpz_add (min, min, off);
141 /* Stores the bounds on the difference of the values of the expressions
142 (var + X) and (var + Y), computed in TYPE, to BNDS. */
145 bound_difference_of_offsetted_base (tree type, mpz_t x, mpz_t y,
148 int rel = mpz_cmp (x, y);
149 bool may_wrap = !nowrap_type_p (type);
152 /* If X == Y, then the expressions are always equal.
153 If X > Y, there are the following possibilities:
154 a) neither of var + X and var + Y overflow or underflow, or both of
155 them do. Then their difference is X - Y.
156 b) var + X overflows, and var + Y does not. Then the values of the
157 expressions are var + X - M and var + Y, where M is the range of
158 the type, and their difference is X - Y - M.
159 c) var + Y underflows and var + X does not. Their difference again
161 Therefore, if the arithmetics in type does not overflow, then the
162 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
163 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
164 (X - Y, X - Y + M). */
168 mpz_set_ui (bnds->below, 0);
169 mpz_set_ui (bnds->up, 0);
174 mpz_set_double_int (m, double_int_mask (TYPE_PRECISION (type)), true);
175 mpz_add_ui (m, m, 1);
176 mpz_sub (bnds->up, x, y);
177 mpz_set (bnds->below, bnds->up);
182 mpz_sub (bnds->below, bnds->below, m);
184 mpz_add (bnds->up, bnds->up, m);
190 /* From condition C0 CMP C1 derives information regarding the
191 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
192 and stores it to BNDS. */
195 refine_bounds_using_guard (tree type, tree varx, mpz_t offx,
196 tree vary, mpz_t offy,
197 tree c0, enum tree_code cmp, tree c1,
200 tree varc0, varc1, tmp, ctype;
201 mpz_t offc0, offc1, loffx, loffy, bnd;
203 bool no_wrap = nowrap_type_p (type);
212 STRIP_SIGN_NOPS (c0);
213 STRIP_SIGN_NOPS (c1);
214 ctype = TREE_TYPE (c0);
215 if (!tree_ssa_useless_type_conversion_1 (ctype, type))
221 /* We could derive quite precise information from EQ_EXPR, however, such
222 a guard is unlikely to appear, so we do not bother with handling
227 /* NE_EXPR comparisons do not contain much of useful information, except for
228 special case of comparing with the bounds of the type. */
229 if (TREE_CODE (c1) != INTEGER_CST
230 || !INTEGRAL_TYPE_P (type))
233 /* Ensure that the condition speaks about an expression in the same type
235 ctype = TREE_TYPE (c0);
236 if (TYPE_PRECISION (ctype) != TYPE_PRECISION (type))
238 c0 = fold_convert (type, c0);
239 c1 = fold_convert (type, c1);
241 if (TYPE_MIN_VALUE (type)
242 && operand_equal_p (c1, TYPE_MIN_VALUE (type), 0))
247 if (TYPE_MAX_VALUE (type)
248 && operand_equal_p (c1, TYPE_MAX_VALUE (type), 0))
261 split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0);
262 split_to_var_and_offset (expand_simple_operations (c1), &varc1, offc1);
264 /* We are only interested in comparisons of expressions based on VARX and
265 VARY. TODO -- we might also be able to derive some bounds from
266 expressions containing just one of the variables. */
268 if (operand_equal_p (varx, varc1, 0))
270 tmp = varc0; varc0 = varc1; varc1 = tmp;
271 mpz_swap (offc0, offc1);
272 cmp = swap_tree_comparison (cmp);
275 if (!operand_equal_p (varx, varc0, 0)
276 || !operand_equal_p (vary, varc1, 0))
279 mpz_init_set (loffx, offx);
280 mpz_init_set (loffy, offy);
282 if (cmp == GT_EXPR || cmp == GE_EXPR)
284 tmp = varx; varx = vary; vary = tmp;
285 mpz_swap (offc0, offc1);
286 mpz_swap (loffx, loffy);
287 cmp = swap_tree_comparison (cmp);
291 /* If there is no overflow, the condition implies that
293 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
295 The overflows and underflows may complicate things a bit; each
296 overflow decreases the appropriate offset by M, and underflow
297 increases it by M. The above inequality would not necessarily be
300 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
301 VARX + OFFC0 overflows, but VARX + OFFX does not.
302 This may only happen if OFFX < OFFC0.
303 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
304 VARY + OFFC1 underflows and VARY + OFFY does not.
305 This may only happen if OFFY > OFFC1. */
314 x_ok = (integer_zerop (varx)
315 || mpz_cmp (loffx, offc0) >= 0);
316 y_ok = (integer_zerop (vary)
317 || mpz_cmp (loffy, offc1) <= 0);
323 mpz_sub (bnd, loffx, loffy);
324 mpz_add (bnd, bnd, offc1);
325 mpz_sub (bnd, bnd, offc0);
328 mpz_sub_ui (bnd, bnd, 1);
333 if (mpz_cmp (bnds->below, bnd) < 0)
334 mpz_set (bnds->below, bnd);
338 if (mpz_cmp (bnd, bnds->up) < 0)
339 mpz_set (bnds->up, bnd);
351 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
352 The subtraction is considered to be performed in arbitrary precision,
355 We do not attempt to be too clever regarding the value ranges of X and
356 Y; most of the time, they are just integers or ssa names offsetted by
357 integer. However, we try to use the information contained in the
358 comparisons before the loop (usually created by loop header copying). */
361 bound_difference (struct loop *loop, tree x, tree y, bounds *bnds)
363 tree type = TREE_TYPE (x);
366 mpz_t minx, maxx, miny, maxy;
373 /* Get rid of unnecessary casts, but preserve the value of
378 mpz_init (bnds->below);
382 split_to_var_and_offset (x, &varx, offx);
383 split_to_var_and_offset (y, &vary, offy);
385 if (!integer_zerop (varx)
386 && operand_equal_p (varx, vary, 0))
388 /* Special case VARX == VARY -- we just need to compare the
389 offsets. The matters are a bit more complicated in the
390 case addition of offsets may wrap. */
391 bound_difference_of_offsetted_base (type, offx, offy, bnds);
395 /* Otherwise, use the value ranges to determine the initial
396 estimates on below and up. */
401 determine_value_range (type, varx, offx, minx, maxx);
402 determine_value_range (type, vary, offy, miny, maxy);
404 mpz_sub (bnds->below, minx, maxy);
405 mpz_sub (bnds->up, maxx, miny);
412 /* If both X and Y are constants, we cannot get any more precise. */
413 if (integer_zerop (varx) && integer_zerop (vary))
416 /* Now walk the dominators of the loop header and use the entry
417 guards to refine the estimates. */
418 for (bb = loop->header;
419 bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK;
420 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
422 if (!single_pred_p (bb))
424 e = single_pred_edge (bb);
426 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
429 cond = COND_EXPR_COND (last_stmt (e->src));
430 if (!COMPARISON_CLASS_P (cond))
432 c0 = TREE_OPERAND (cond, 0);
433 cmp = TREE_CODE (cond);
434 c1 = TREE_OPERAND (cond, 1);
436 if (e->flags & EDGE_FALSE_VALUE)
437 cmp = invert_tree_comparison (cmp, false);
439 refine_bounds_using_guard (type, varx, offx, vary, offy,
449 /* Update the bounds in BNDS that restrict the value of X to the bounds
450 that restrict the value of X + DELTA. X can be obtained as a
451 difference of two values in TYPE. */
454 bounds_add (bounds *bnds, double_int delta, tree type)
459 mpz_set_double_int (mdelta, delta, false);
462 mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true);
464 mpz_add (bnds->up, bnds->up, mdelta);
465 mpz_add (bnds->below, bnds->below, mdelta);
467 if (mpz_cmp (bnds->up, max) > 0)
468 mpz_set (bnds->up, max);
471 if (mpz_cmp (bnds->below, max) < 0)
472 mpz_set (bnds->below, max);
478 /* Update the bounds in BNDS that restrict the value of X to the bounds
479 that restrict the value of -X. */
482 bounds_negate (bounds *bnds)
486 mpz_init_set (tmp, bnds->up);
487 mpz_neg (bnds->up, bnds->below);
488 mpz_neg (bnds->below, tmp);
492 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
495 inverse (tree x, tree mask)
497 tree type = TREE_TYPE (x);
499 unsigned ctr = tree_floor_log2 (mask);
501 if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT)
503 unsigned HOST_WIDE_INT ix;
504 unsigned HOST_WIDE_INT imask;
505 unsigned HOST_WIDE_INT irslt = 1;
507 gcc_assert (cst_and_fits_in_hwi (x));
508 gcc_assert (cst_and_fits_in_hwi (mask));
510 ix = int_cst_value (x);
511 imask = int_cst_value (mask);
520 rslt = build_int_cst_type (type, irslt);
524 rslt = build_int_cst (type, 1);
527 rslt = int_const_binop (MULT_EXPR, rslt, x, 0);
528 x = int_const_binop (MULT_EXPR, x, x, 0);
530 rslt = int_const_binop (BIT_AND_EXPR, rslt, mask, 0);
536 /* Derives the upper bound BND on the number of executions of loop with exit
537 condition S * i <> C, assuming that the loop is not infinite. If
538 NO_OVERFLOW is true, then the control variable of the loop does not
539 overflow. If NO_OVERFLOW is true or BNDS.below >= 0, then BNDS.up
540 contains the upper bound on the value of C. */
543 number_of_iterations_ne_max (mpz_t bnd, bool no_overflow, tree c, tree s,
549 /* If the control variable does not overflow, the number of iterations is
550 at most c / s. Otherwise it is at most the period of the control
552 if (!no_overflow && !multiple_of_p (TREE_TYPE (c), c, s))
554 max = double_int_mask (TYPE_PRECISION (TREE_TYPE (c))
555 - tree_low_cst (num_ending_zeros (s), 1));
556 mpz_set_double_int (bnd, max, true);
560 /* Determine the upper bound on C. */
561 if (no_overflow || mpz_sgn (bnds->below) >= 0)
562 mpz_set (bnd, bnds->up);
563 else if (TREE_CODE (c) == INTEGER_CST)
564 mpz_set_double_int (bnd, tree_to_double_int (c), true);
566 mpz_set_double_int (bnd, double_int_mask (TYPE_PRECISION (TREE_TYPE (c))),
570 mpz_set_double_int (d, tree_to_double_int (s), true);
571 mpz_fdiv_q (bnd, bnd, d);
575 /* Determines number of iterations of loop whose ending condition
576 is IV <> FINAL. TYPE is the type of the iv. The number of
577 iterations is stored to NITER. NEVER_INFINITE is true if
578 we know that the exit must be taken eventually, i.e., that the IV
579 ever reaches the value FINAL (we derived this earlier, and possibly set
580 NITER->assumptions to make sure this is the case). BNDS contains the
581 bounds on the difference FINAL - IV->base. */
584 number_of_iterations_ne (tree type, affine_iv *iv, tree final,
585 struct tree_niter_desc *niter, bool never_infinite,
588 tree niter_type = unsigned_type_for (type);
589 tree s, c, d, bits, assumption, tmp, bound;
592 niter->control = *iv;
593 niter->bound = final;
594 niter->cmp = NE_EXPR;
596 /* Rearrange the terms so that we get inequality S * i <> C, with S
597 positive. Also cast everything to the unsigned type. If IV does
598 not overflow, BNDS bounds the value of C. Also, this is the
599 case if the computation |FINAL - IV->base| does not overflow, i.e.,
600 if BNDS->below in the result is nonnegative. */
601 if (tree_int_cst_sign_bit (iv->step))
603 s = fold_convert (niter_type,
604 fold_build1 (NEGATE_EXPR, type, iv->step));
605 c = fold_build2 (MINUS_EXPR, niter_type,
606 fold_convert (niter_type, iv->base),
607 fold_convert (niter_type, final));
608 bounds_negate (bnds);
612 s = fold_convert (niter_type, iv->step);
613 c = fold_build2 (MINUS_EXPR, niter_type,
614 fold_convert (niter_type, final),
615 fold_convert (niter_type, iv->base));
619 number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds);
620 niter->max = mpz_get_double_int (niter_type, max, false);
623 /* First the trivial cases -- when the step is 1. */
624 if (integer_onep (s))
630 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
631 is infinite. Otherwise, the number of iterations is
632 (inverse(s/d) * (c/d)) mod (size of mode/d). */
633 bits = num_ending_zeros (s);
634 bound = build_low_bits_mask (niter_type,
635 (TYPE_PRECISION (niter_type)
636 - tree_low_cst (bits, 1)));
638 d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
639 build_int_cst (niter_type, 1), bits);
640 s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
644 /* If we cannot assume that the loop is not infinite, record the
645 assumptions for divisibility of c. */
646 assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d);
647 assumption = fold_build2 (EQ_EXPR, boolean_type_node,
648 assumption, build_int_cst (niter_type, 0));
649 if (!integer_nonzerop (assumption))
650 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
651 niter->assumptions, assumption);
654 c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d);
655 tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound));
656 niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound);
660 /* Checks whether we can determine the final value of the control variable
661 of the loop with ending condition IV0 < IV1 (computed in TYPE).
662 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
663 of the step. The assumptions necessary to ensure that the computation
664 of the final value does not overflow are recorded in NITER. If we
665 find the final value, we adjust DELTA and return TRUE. Otherwise
666 we return false. BNDS bounds the value of IV1->base - IV0->base,
667 and will be updated by the same amount as DELTA. */
670 number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1,
671 struct tree_niter_desc *niter,
672 tree *delta, tree step,
675 tree niter_type = TREE_TYPE (step);
676 tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step);
679 tree assumption = boolean_true_node, bound, noloop;
682 if (TREE_CODE (mod) != INTEGER_CST)
684 if (integer_nonzerop (mod))
685 mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
686 tmod = fold_convert (type, mod);
689 mpz_set_double_int (mmod, tree_to_double_int (mod), true);
690 mpz_neg (mmod, mmod);
692 if (integer_nonzerop (iv0->step))
694 /* The final value of the iv is iv1->base + MOD, assuming that this
695 computation does not overflow, and that
696 iv0->base <= iv1->base + MOD. */
697 if (!iv1->no_overflow && !integer_zerop (mod))
699 bound = fold_build2 (MINUS_EXPR, type,
700 TYPE_MAX_VALUE (type), tmod);
701 assumption = fold_build2 (LE_EXPR, boolean_type_node,
703 if (integer_zerop (assumption))
706 if (mpz_cmp (mmod, bnds->below) < 0)
707 noloop = boolean_false_node;
709 noloop = fold_build2 (GT_EXPR, boolean_type_node,
711 fold_build2 (PLUS_EXPR, type,
716 /* The final value of the iv is iv0->base - MOD, assuming that this
717 computation does not overflow, and that
718 iv0->base - MOD <= iv1->base. */
719 if (!iv0->no_overflow && !integer_zerop (mod))
721 bound = fold_build2 (PLUS_EXPR, type,
722 TYPE_MIN_VALUE (type), tmod);
723 assumption = fold_build2 (GE_EXPR, boolean_type_node,
725 if (integer_zerop (assumption))
728 if (mpz_cmp (mmod, bnds->below) < 0)
729 noloop = boolean_false_node;
731 noloop = fold_build2 (GT_EXPR, boolean_type_node,
732 fold_build2 (MINUS_EXPR, type,
737 if (!integer_nonzerop (assumption))
738 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
741 if (!integer_zerop (noloop))
742 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
745 bounds_add (bnds, tree_to_double_int (mod), type);
746 *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod);
754 /* Add assertions to NITER that ensure that the control variable of the loop
755 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
756 are TYPE. Returns false if we can prove that there is an overflow, true
757 otherwise. STEP is the absolute value of the step. */
760 assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
761 struct tree_niter_desc *niter, tree step)
763 tree bound, d, assumption, diff;
764 tree niter_type = TREE_TYPE (step);
766 if (integer_nonzerop (iv0->step))
768 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
769 if (iv0->no_overflow)
772 /* If iv0->base is a constant, we can determine the last value before
773 overflow precisely; otherwise we conservatively assume
776 if (TREE_CODE (iv0->base) == INTEGER_CST)
778 d = fold_build2 (MINUS_EXPR, niter_type,
779 fold_convert (niter_type, TYPE_MAX_VALUE (type)),
780 fold_convert (niter_type, iv0->base));
781 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
784 diff = fold_build2 (MINUS_EXPR, niter_type, step,
785 build_int_cst (niter_type, 1));
786 bound = fold_build2 (MINUS_EXPR, type,
787 TYPE_MAX_VALUE (type), fold_convert (type, diff));
788 assumption = fold_build2 (LE_EXPR, boolean_type_node,
793 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
794 if (iv1->no_overflow)
797 if (TREE_CODE (iv1->base) == INTEGER_CST)
799 d = fold_build2 (MINUS_EXPR, niter_type,
800 fold_convert (niter_type, iv1->base),
801 fold_convert (niter_type, TYPE_MIN_VALUE (type)));
802 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
805 diff = fold_build2 (MINUS_EXPR, niter_type, step,
806 build_int_cst (niter_type, 1));
807 bound = fold_build2 (PLUS_EXPR, type,
808 TYPE_MIN_VALUE (type), fold_convert (type, diff));
809 assumption = fold_build2 (GE_EXPR, boolean_type_node,
813 if (integer_zerop (assumption))
815 if (!integer_nonzerop (assumption))
816 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
817 niter->assumptions, assumption);
819 iv0->no_overflow = true;
820 iv1->no_overflow = true;
824 /* Add an assumption to NITER that a loop whose ending condition
825 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
826 bounds the value of IV1->base - IV0->base. */
829 assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
830 struct tree_niter_desc *niter, bounds *bnds)
832 tree assumption = boolean_true_node, bound, diff;
833 tree mbz, mbzl, mbzr;
834 bool rolls_p, no_overflow_p;
838 /* We are going to compute the number of iterations as
839 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
840 variant of TYPE. This formula only works if
842 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
844 (where MAX is the maximum value of the unsigned variant of TYPE, and
845 the computations in this formula are performed in full precision
848 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
849 we have a condition of form iv0->base - step < iv1->base before the loop,
850 and for loops iv0->base < iv1->base - step * i the condition
851 iv0->base < iv1->base + step, due to loop header copying, which enable us
852 to prove the lower bound.
854 The upper bound is more complicated. Unless the expressions for initial
855 and final value themselves contain enough information, we usually cannot
856 derive it from the context. */
858 /* First check whether the answer does not follow from the bounds we gathered
860 if (integer_nonzerop (iv0->step))
861 dstep = tree_to_double_int (iv0->step);
864 dstep = double_int_sext (tree_to_double_int (iv1->step),
865 TYPE_PRECISION (type));
866 dstep = double_int_neg (dstep);
870 mpz_set_double_int (mstep, dstep, true);
871 mpz_neg (mstep, mstep);
872 mpz_add_ui (mstep, mstep, 1);
874 rolls_p = mpz_cmp (mstep, bnds->below) <= 0;
877 mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true);
878 mpz_add (max, max, mstep);
879 no_overflow_p = (mpz_cmp (bnds->up, max) <= 0
880 /* For pointers, only values lying inside a single object
881 can be compared or manipulated by pointer arithmetics.
882 Gcc in general does not allow or handle objects larger
883 than half of the address space, hence the upper bound
884 is satisfied for pointers. */
885 || POINTER_TYPE_P (type));
889 if (rolls_p && no_overflow_p)
892 /* Now the hard part; we must formulate the assumption(s) as expressions, and
893 we must be careful not to introduce overflow. */
895 if (integer_nonzerop (iv0->step))
897 diff = fold_build2 (MINUS_EXPR, type,
898 iv0->step, build_int_cst (type, 1));
900 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
901 0 address never belongs to any object, we can assume this for
903 if (!POINTER_TYPE_P (type))
905 bound = fold_build2 (PLUS_EXPR, type,
906 TYPE_MIN_VALUE (type), diff);
907 assumption = fold_build2 (GE_EXPR, boolean_type_node,
911 /* And then we can compute iv0->base - diff, and compare it with
913 mbzl = fold_build2 (MINUS_EXPR, type, iv0->base, diff);
918 diff = fold_build2 (PLUS_EXPR, type,
919 iv1->step, build_int_cst (type, 1));
921 if (!POINTER_TYPE_P (type))
923 bound = fold_build2 (PLUS_EXPR, type,
924 TYPE_MAX_VALUE (type), diff);
925 assumption = fold_build2 (LE_EXPR, boolean_type_node,
930 mbzr = fold_build2 (MINUS_EXPR, type, iv1->base, diff);
933 if (!integer_nonzerop (assumption))
934 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
935 niter->assumptions, assumption);
938 mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr);
939 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
940 niter->may_be_zero, mbz);
944 /* Determines number of iterations of loop whose ending condition
945 is IV0 < IV1. TYPE is the type of the iv. The number of
946 iterations is stored to NITER. BNDS bounds the difference
947 IV1->base - IV0->base. */
950 number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
951 struct tree_niter_desc *niter,
952 bool never_infinite ATTRIBUTE_UNUSED,
955 tree niter_type = unsigned_type_for (type);
959 if (integer_nonzerop (iv0->step))
961 niter->control = *iv0;
962 niter->cmp = LT_EXPR;
963 niter->bound = iv1->base;
967 niter->control = *iv1;
968 niter->cmp = GT_EXPR;
969 niter->bound = iv0->base;
972 delta = fold_build2 (MINUS_EXPR, niter_type,
973 fold_convert (niter_type, iv1->base),
974 fold_convert (niter_type, iv0->base));
976 /* First handle the special case that the step is +-1. */
977 if ((integer_onep (iv0->step) && integer_zerop (iv1->step))
978 || (integer_all_onesp (iv1->step) && integer_zerop (iv0->step)))
980 /* for (i = iv0->base; i < iv1->base; i++)
984 for (i = iv1->base; i > iv0->base; i--).
986 In both cases # of iterations is iv1->base - iv0->base, assuming that
987 iv1->base >= iv0->base.
989 First try to derive a lower bound on the value of
990 iv1->base - iv0->base, computed in full precision. If the difference
991 is nonnegative, we are done, otherwise we must record the
994 if (mpz_sgn (bnds->below) < 0)
995 niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
996 iv1->base, iv0->base);
997 niter->niter = delta;
998 niter->max = mpz_get_double_int (niter_type, bnds->up, false);
1002 if (integer_nonzerop (iv0->step))
1003 step = fold_convert (niter_type, iv0->step);
1005 step = fold_convert (niter_type,
1006 fold_build1 (NEGATE_EXPR, type, iv1->step));
1008 /* If we can determine the final value of the control iv exactly, we can
1009 transform the condition to != comparison. In particular, this will be
1010 the case if DELTA is constant. */
1011 if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step,
1016 zps.base = build_int_cst (niter_type, 0);
1018 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1019 zps does not overflow. */
1020 zps.no_overflow = true;
1022 return number_of_iterations_ne (type, &zps, delta, niter, true, bnds);
1025 /* Make sure that the control iv does not overflow. */
1026 if (!assert_no_overflow_lt (type, iv0, iv1, niter, step))
1029 /* We determine the number of iterations as (delta + step - 1) / step. For
1030 this to work, we must know that iv1->base >= iv0->base - step + 1,
1031 otherwise the loop does not roll. */
1032 assert_loop_rolls_lt (type, iv0, iv1, niter, bnds);
1034 s = fold_build2 (MINUS_EXPR, niter_type,
1035 step, build_int_cst (niter_type, 1));
1036 delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
1037 niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
1041 mpz_set_double_int (mstep, tree_to_double_int (step), true);
1042 mpz_add (tmp, bnds->up, mstep);
1043 mpz_sub_ui (tmp, tmp, 1);
1044 mpz_fdiv_q (tmp, tmp, mstep);
1045 niter->max = mpz_get_double_int (niter_type, tmp, false);
1052 /* Determines number of iterations of loop whose ending condition
1053 is IV0 <= IV1. TYPE is the type of the iv. The number of
1054 iterations is stored to NITER. NEVER_INFINITE is true if
1055 we know that this condition must eventually become false (we derived this
1056 earlier, and possibly set NITER->assumptions to make sure this
1057 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1060 number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1,
1061 struct tree_niter_desc *niter, bool never_infinite,
1066 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1067 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1068 value of the type. This we must know anyway, since if it is
1069 equal to this value, the loop rolls forever. */
1071 if (!never_infinite)
1073 if (integer_nonzerop (iv0->step))
1074 assumption = fold_build2 (NE_EXPR, boolean_type_node,
1075 iv1->base, TYPE_MAX_VALUE (type));
1077 assumption = fold_build2 (NE_EXPR, boolean_type_node,
1078 iv0->base, TYPE_MIN_VALUE (type));
1080 if (integer_zerop (assumption))
1082 if (!integer_nonzerop (assumption))
1083 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1084 niter->assumptions, assumption);
1087 if (integer_nonzerop (iv0->step))
1088 iv1->base = fold_build2 (PLUS_EXPR, type,
1089 iv1->base, build_int_cst (type, 1));
1091 iv0->base = fold_build2 (MINUS_EXPR, type,
1092 iv0->base, build_int_cst (type, 1));
1094 bounds_add (bnds, double_int_one, type);
1096 return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite, bnds);
1099 /* Dumps description of affine induction variable IV to FILE. */
1102 dump_affine_iv (FILE *file, affine_iv *iv)
1104 if (!integer_zerop (iv->step))
1105 fprintf (file, "[");
1107 print_generic_expr (dump_file, iv->base, TDF_SLIM);
1109 if (!integer_zerop (iv->step))
1111 fprintf (file, ", + , ");
1112 print_generic_expr (dump_file, iv->step, TDF_SLIM);
1113 fprintf (file, "]%s", iv->no_overflow ? "(no_overflow)" : "");
1117 /* Determine the number of iterations according to condition (for staying
1118 inside loop) which compares two induction variables using comparison
1119 operator CODE. The induction variable on left side of the comparison
1120 is IV0, the right-hand side is IV1. Both induction variables must have
1121 type TYPE, which must be an integer or pointer type. The steps of the
1122 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1124 LOOP is the loop whose number of iterations we are determining.
1126 ONLY_EXIT is true if we are sure this is the only way the loop could be
1127 exited (including possibly non-returning function calls, exceptions, etc.)
1128 -- in this case we can use the information whether the control induction
1129 variables can overflow or not in a more efficient way.
1131 The results (number of iterations and assumptions as described in
1132 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
1133 Returns false if it fails to determine number of iterations, true if it
1134 was determined (possibly with some assumptions). */
1137 number_of_iterations_cond (struct loop *loop,
1138 tree type, affine_iv *iv0, enum tree_code code,
1139 affine_iv *iv1, struct tree_niter_desc *niter,
1142 bool never_infinite, ret;
1145 /* The meaning of these assumptions is this:
1147 then the rest of information does not have to be valid
1148 if may_be_zero then the loop does not roll, even if
1150 niter->assumptions = boolean_true_node;
1151 niter->may_be_zero = boolean_false_node;
1152 niter->niter = NULL_TREE;
1153 niter->max = double_int_zero;
1155 niter->bound = NULL_TREE;
1156 niter->cmp = ERROR_MARK;
1158 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1159 the control variable is on lhs. */
1160 if (code == GE_EXPR || code == GT_EXPR
1161 || (code == NE_EXPR && integer_zerop (iv0->step)))
1164 code = swap_tree_comparison (code);
1169 /* If this is not the only possible exit from the loop, the information
1170 that the induction variables cannot overflow as derived from
1171 signedness analysis cannot be relied upon. We use them e.g. in the
1172 following way: given loop for (i = 0; i <= n; i++), if i is
1173 signed, it cannot overflow, thus this loop is equivalent to
1174 for (i = 0; i < n + 1; i++); however, if n == MAX, but the loop
1175 is exited in some other way before i overflows, this transformation
1176 is incorrect (the new loop exits immediately). */
1177 iv0->no_overflow = false;
1178 iv1->no_overflow = false;
1181 if (POINTER_TYPE_P (type))
1183 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1184 to the same object. If they do, the control variable cannot wrap
1185 (as wrap around the bounds of memory will never return a pointer
1186 that would be guaranteed to point to the same object, even if we
1187 avoid undefined behavior by casting to size_t and back). The
1188 restrictions on pointer arithmetics and comparisons of pointers
1189 ensure that using the no-overflow assumptions is correct in this
1190 case even if ONLY_EXIT is false. */
1191 iv0->no_overflow = true;
1192 iv1->no_overflow = true;
1195 /* If the control induction variable does not overflow, the loop obviously
1196 cannot be infinite. */
1197 if (!integer_zerop (iv0->step) && iv0->no_overflow)
1198 never_infinite = true;
1199 else if (!integer_zerop (iv1->step) && iv1->no_overflow)
1200 never_infinite = true;
1202 never_infinite = false;
1204 /* We can handle the case when neither of the sides of the comparison is
1205 invariant, provided that the test is NE_EXPR. This rarely occurs in
1206 practice, but it is simple enough to manage. */
1207 if (!integer_zerop (iv0->step) && !integer_zerop (iv1->step))
1209 if (code != NE_EXPR)
1212 iv0->step = fold_binary_to_constant (MINUS_EXPR, type,
1213 iv0->step, iv1->step);
1214 iv0->no_overflow = false;
1215 iv1->step = build_int_cst (type, 0);
1216 iv1->no_overflow = true;
1219 /* If the result of the comparison is a constant, the loop is weird. More
1220 precise handling would be possible, but the situation is not common enough
1221 to waste time on it. */
1222 if (integer_zerop (iv0->step) && integer_zerop (iv1->step))
1225 /* Ignore loops of while (i-- < 10) type. */
1226 if (code != NE_EXPR)
1228 if (iv0->step && tree_int_cst_sign_bit (iv0->step))
1231 if (!integer_zerop (iv1->step) && !tree_int_cst_sign_bit (iv1->step))
1235 /* If the loop exits immediately, there is nothing to do. */
1236 if (integer_zerop (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
1238 niter->niter = build_int_cst (unsigned_type_for (type), 0);
1239 niter->max = double_int_zero;
1243 /* OK, now we know we have a senseful loop. Handle several cases, depending
1244 on what comparison operator is used. */
1245 bound_difference (loop, iv1->base, iv0->base, &bnds);
1247 if (dump_file && (dump_flags & TDF_DETAILS))
1250 "Analyzing # of iterations of loop %d\n", loop->num);
1252 fprintf (dump_file, " exit condition ");
1253 dump_affine_iv (dump_file, iv0);
1254 fprintf (dump_file, " %s ",
1255 code == NE_EXPR ? "!="
1256 : code == LT_EXPR ? "<"
1258 dump_affine_iv (dump_file, iv1);
1259 fprintf (dump_file, "\n");
1261 fprintf (dump_file, " bounds on difference of bases: ");
1262 mpz_out_str (dump_file, 10, bnds.below);
1263 fprintf (dump_file, " ... ");
1264 mpz_out_str (dump_file, 10, bnds.up);
1265 fprintf (dump_file, "\n");
1271 gcc_assert (integer_zerop (iv1->step));
1272 ret = number_of_iterations_ne (type, iv0, iv1->base, niter,
1273 never_infinite, &bnds);
1277 ret = number_of_iterations_lt (type, iv0, iv1, niter, never_infinite,
1282 ret = number_of_iterations_le (type, iv0, iv1, niter, never_infinite,
1290 mpz_clear (bnds.up);
1291 mpz_clear (bnds.below);
1293 if (dump_file && (dump_flags & TDF_DETAILS))
1297 fprintf (dump_file, " result:\n");
1298 if (!integer_nonzerop (niter->assumptions))
1300 fprintf (dump_file, " under assumptions ");
1301 print_generic_expr (dump_file, niter->assumptions, TDF_SLIM);
1302 fprintf (dump_file, "\n");
1305 if (!integer_zerop (niter->may_be_zero))
1307 fprintf (dump_file, " zero if ");
1308 print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
1309 fprintf (dump_file, "\n");
1312 fprintf (dump_file, " # of iterations ");
1313 print_generic_expr (dump_file, niter->niter, TDF_SLIM);
1314 fprintf (dump_file, ", bounded by ");
1315 dump_double_int (dump_file, niter->max, true);
1316 fprintf (dump_file, "\n");
1319 fprintf (dump_file, " failed\n\n");
1324 /* Substitute NEW for OLD in EXPR and fold the result. */
1327 simplify_replace_tree (tree expr, tree old, tree new)
1330 tree ret = NULL_TREE, e, se;
1336 || operand_equal_p (expr, old, 0))
1337 return unshare_expr (new);
1339 if (!EXPR_P (expr) && !GIMPLE_STMT_P (expr))
1342 n = TREE_OPERAND_LENGTH (expr);
1343 for (i = 0; i < n; i++)
1345 e = TREE_OPERAND (expr, i);
1346 se = simplify_replace_tree (e, old, new);
1351 ret = copy_node (expr);
1353 TREE_OPERAND (ret, i) = se;
1356 return (ret ? fold (ret) : expr);
1359 /* Expand definitions of ssa names in EXPR as long as they are simple
1360 enough, and return the new expression. */
1363 expand_simple_operations (tree expr)
1366 tree ret = NULL_TREE, e, ee, stmt;
1367 enum tree_code code;
1369 if (expr == NULL_TREE)
1372 if (is_gimple_min_invariant (expr))
1375 code = TREE_CODE (expr);
1376 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
1378 n = TREE_OPERAND_LENGTH (expr);
1379 for (i = 0; i < n; i++)
1381 e = TREE_OPERAND (expr, i);
1382 ee = expand_simple_operations (e);
1387 ret = copy_node (expr);
1389 TREE_OPERAND (ret, i) = ee;
1395 fold_defer_overflow_warnings ();
1397 fold_undefer_and_ignore_overflow_warnings ();
1401 if (TREE_CODE (expr) != SSA_NAME)
1404 stmt = SSA_NAME_DEF_STMT (expr);
1405 if (TREE_CODE (stmt) == PHI_NODE)
1407 basic_block src, dest;
1409 if (PHI_NUM_ARGS (stmt) != 1)
1411 e = PHI_ARG_DEF (stmt, 0);
1413 /* Avoid propagating through loop exit phi nodes, which
1414 could break loop-closed SSA form restrictions. */
1415 dest = bb_for_stmt (stmt);
1416 src = single_pred (dest);
1417 if (TREE_CODE (e) == SSA_NAME
1418 && src->loop_father != dest->loop_father)
1421 return expand_simple_operations (e);
1423 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
1426 e = GIMPLE_STMT_OPERAND (stmt, 1);
1427 if (/* Casts are simple. */
1428 TREE_CODE (e) != NOP_EXPR
1429 && TREE_CODE (e) != CONVERT_EXPR
1430 /* Copies are simple. */
1431 && TREE_CODE (e) != SSA_NAME
1432 /* Assignments of invariants are simple. */
1433 && !is_gimple_min_invariant (e)
1434 /* And increments and decrements by a constant are simple. */
1435 && !((TREE_CODE (e) == PLUS_EXPR
1436 || TREE_CODE (e) == MINUS_EXPR)
1437 && is_gimple_min_invariant (TREE_OPERAND (e, 1))))
1440 return expand_simple_operations (e);
1443 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1444 expression (or EXPR unchanged, if no simplification was possible). */
1447 tree_simplify_using_condition_1 (tree cond, tree expr)
1450 tree e, te, e0, e1, e2, notcond;
1451 enum tree_code code = TREE_CODE (expr);
1453 if (code == INTEGER_CST)
1456 if (code == TRUTH_OR_EXPR
1457 || code == TRUTH_AND_EXPR
1458 || code == COND_EXPR)
1462 e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0));
1463 if (TREE_OPERAND (expr, 0) != e0)
1466 e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1));
1467 if (TREE_OPERAND (expr, 1) != e1)
1470 if (code == COND_EXPR)
1472 e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2));
1473 if (TREE_OPERAND (expr, 2) != e2)
1481 if (code == COND_EXPR)
1482 expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
1484 expr = fold_build2 (code, boolean_type_node, e0, e1);
1490 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
1491 propagation, and vice versa. Fold does not handle this, since it is
1492 considered too expensive. */
1493 if (TREE_CODE (cond) == EQ_EXPR)
1495 e0 = TREE_OPERAND (cond, 0);
1496 e1 = TREE_OPERAND (cond, 1);
1498 /* We know that e0 == e1. Check whether we cannot simplify expr
1500 e = simplify_replace_tree (expr, e0, e1);
1501 if (integer_zerop (e) || integer_nonzerop (e))
1504 e = simplify_replace_tree (expr, e1, e0);
1505 if (integer_zerop (e) || integer_nonzerop (e))
1508 if (TREE_CODE (expr) == EQ_EXPR)
1510 e0 = TREE_OPERAND (expr, 0);
1511 e1 = TREE_OPERAND (expr, 1);
1513 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
1514 e = simplify_replace_tree (cond, e0, e1);
1515 if (integer_zerop (e))
1517 e = simplify_replace_tree (cond, e1, e0);
1518 if (integer_zerop (e))
1521 if (TREE_CODE (expr) == NE_EXPR)
1523 e0 = TREE_OPERAND (expr, 0);
1524 e1 = TREE_OPERAND (expr, 1);
1526 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
1527 e = simplify_replace_tree (cond, e0, e1);
1528 if (integer_zerop (e))
1529 return boolean_true_node;
1530 e = simplify_replace_tree (cond, e1, e0);
1531 if (integer_zerop (e))
1532 return boolean_true_node;
1535 te = expand_simple_operations (expr);
1537 /* Check whether COND ==> EXPR. */
1538 notcond = invert_truthvalue (cond);
1539 e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te);
1540 if (e && integer_nonzerop (e))
1543 /* Check whether COND ==> not EXPR. */
1544 e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te);
1545 if (e && integer_zerop (e))
1551 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1552 expression (or EXPR unchanged, if no simplification was possible).
1553 Wrapper around tree_simplify_using_condition_1 that ensures that chains
1554 of simple operations in definitions of ssa names in COND are expanded,
1555 so that things like casts or incrementing the value of the bound before
1556 the loop do not cause us to fail. */
1559 tree_simplify_using_condition (tree cond, tree expr)
1561 cond = expand_simple_operations (cond);
1563 return tree_simplify_using_condition_1 (cond, expr);
1566 /* Tries to simplify EXPR using the conditions on entry to LOOP.
1567 Returns the simplified expression (or EXPR unchanged, if no
1568 simplification was possible).*/
1571 simplify_using_initial_conditions (struct loop *loop, tree expr)
1578 if (TREE_CODE (expr) == INTEGER_CST)
1581 /* Limit walking the dominators to avoid quadraticness in
1582 the number of BBs times the number of loops in degenerate
1584 for (bb = loop->header;
1585 bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK;
1586 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1588 if (!single_pred_p (bb))
1590 e = single_pred_edge (bb);
1592 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
1595 cond = COND_EXPR_COND (last_stmt (e->src));
1596 if (e->flags & EDGE_FALSE_VALUE)
1597 cond = invert_truthvalue (cond);
1598 expr = tree_simplify_using_condition (cond, expr);
1605 /* Tries to simplify EXPR using the evolutions of the loop invariants
1606 in the superloops of LOOP. Returns the simplified expression
1607 (or EXPR unchanged, if no simplification was possible). */
1610 simplify_using_outer_evolutions (struct loop *loop, tree expr)
1612 enum tree_code code = TREE_CODE (expr);
1616 if (is_gimple_min_invariant (expr))
1619 if (code == TRUTH_OR_EXPR
1620 || code == TRUTH_AND_EXPR
1621 || code == COND_EXPR)
1625 e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
1626 if (TREE_OPERAND (expr, 0) != e0)
1629 e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
1630 if (TREE_OPERAND (expr, 1) != e1)
1633 if (code == COND_EXPR)
1635 e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
1636 if (TREE_OPERAND (expr, 2) != e2)
1644 if (code == COND_EXPR)
1645 expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
1647 expr = fold_build2 (code, boolean_type_node, e0, e1);
1653 e = instantiate_parameters (loop, expr);
1654 if (is_gimple_min_invariant (e))
1660 /* Returns true if EXIT is the only possible exit from LOOP. */
1663 loop_only_exit_p (struct loop *loop, edge exit)
1666 block_stmt_iterator bsi;
1670 if (exit != single_exit (loop))
1673 body = get_loop_body (loop);
1674 for (i = 0; i < loop->num_nodes; i++)
1676 for (bsi = bsi_start (body[0]); !bsi_end_p (bsi); bsi_next (&bsi))
1678 call = get_call_expr_in (bsi_stmt (bsi));
1679 if (call && TREE_SIDE_EFFECTS (call))
1691 /* Stores description of number of iterations of LOOP derived from
1692 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
1693 useful information could be derived (and fields of NITER has
1694 meaning described in comments at struct tree_niter_desc
1695 declaration), false otherwise. If WARN is true and
1696 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1697 potentially unsafe assumptions. */
1700 number_of_iterations_exit (struct loop *loop, edge exit,
1701 struct tree_niter_desc *niter,
1704 tree stmt, cond, type;
1706 enum tree_code code;
1709 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
1712 niter->assumptions = boolean_false_node;
1713 stmt = last_stmt (exit->src);
1714 if (!stmt || TREE_CODE (stmt) != COND_EXPR)
1717 /* We want the condition for staying inside loop. */
1718 cond = COND_EXPR_COND (stmt);
1719 if (exit->flags & EDGE_TRUE_VALUE)
1720 cond = invert_truthvalue (cond);
1722 code = TREE_CODE (cond);
1736 op0 = TREE_OPERAND (cond, 0);
1737 op1 = TREE_OPERAND (cond, 1);
1738 type = TREE_TYPE (op0);
1740 if (TREE_CODE (type) != INTEGER_TYPE
1741 && !POINTER_TYPE_P (type))
1744 if (!simple_iv (loop, stmt, op0, &iv0, false))
1746 if (!simple_iv (loop, stmt, op1, &iv1, false))
1749 /* We don't want to see undefined signed overflow warnings while
1750 computing the number of iterations. */
1751 fold_defer_overflow_warnings ();
1753 iv0.base = expand_simple_operations (iv0.base);
1754 iv1.base = expand_simple_operations (iv1.base);
1755 if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter,
1756 loop_only_exit_p (loop, exit)))
1758 fold_undefer_and_ignore_overflow_warnings ();
1764 niter->assumptions = simplify_using_outer_evolutions (loop,
1765 niter->assumptions);
1766 niter->may_be_zero = simplify_using_outer_evolutions (loop,
1767 niter->may_be_zero);
1768 niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
1772 = simplify_using_initial_conditions (loop,
1773 niter->assumptions);
1775 = simplify_using_initial_conditions (loop,
1776 niter->may_be_zero);
1778 fold_undefer_and_ignore_overflow_warnings ();
1780 if (integer_onep (niter->assumptions))
1783 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1784 But if we can prove that there is overflow or some other source of weird
1785 behavior, ignore the loop even with -funsafe-loop-optimizations. */
1786 if (integer_zerop (niter->assumptions))
1789 if (flag_unsafe_loop_optimizations)
1790 niter->assumptions = boolean_true_node;
1794 const char *wording;
1795 location_t loc = EXPR_LOCATION (stmt);
1797 /* We can provide a more specific warning if one of the operator is
1798 constant and the other advances by +1 or -1. */
1799 if (!integer_zerop (iv1.step)
1800 ? (integer_zerop (iv0.step)
1801 && (integer_onep (iv1.step) || integer_all_onesp (iv1.step)))
1802 : (integer_onep (iv0.step) || integer_all_onesp (iv0.step)))
1804 flag_unsafe_loop_optimizations
1805 ? N_("assuming that the loop is not infinite")
1806 : N_("cannot optimize possibly infinite loops");
1809 flag_unsafe_loop_optimizations
1810 ? N_("assuming that the loop counter does not overflow")
1811 : N_("cannot optimize loop, the loop counter may overflow");
1813 if (LOCATION_LINE (loc) > 0)
1814 warning (OPT_Wunsafe_loop_optimizations, "%H%s", &loc, gettext (wording));
1816 warning (OPT_Wunsafe_loop_optimizations, "%s", gettext (wording));
1819 return flag_unsafe_loop_optimizations;
1822 /* Try to determine the number of iterations of LOOP. If we succeed,
1823 expression giving number of iterations is returned and *EXIT is
1824 set to the edge from that the information is obtained. Otherwise
1825 chrec_dont_know is returned. */
1828 find_loop_niter (struct loop *loop, edge *exit)
1831 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1833 tree niter = NULL_TREE, aniter;
1834 struct tree_niter_desc desc;
1837 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
1839 if (!just_once_each_iteration_p (loop, ex->src))
1842 if (!number_of_iterations_exit (loop, ex, &desc, false))
1845 if (integer_nonzerop (desc.may_be_zero))
1847 /* We exit in the first iteration through this exit.
1848 We won't find anything better. */
1849 niter = build_int_cst (unsigned_type_node, 0);
1854 if (!integer_zerop (desc.may_be_zero))
1857 aniter = desc.niter;
1861 /* Nothing recorded yet. */
1867 /* Prefer constants, the lower the better. */
1868 if (TREE_CODE (aniter) != INTEGER_CST)
1871 if (TREE_CODE (niter) != INTEGER_CST)
1878 if (tree_int_cst_lt (aniter, niter))
1885 VEC_free (edge, heap, exits);
1887 return niter ? niter : chrec_dont_know;
1892 Analysis of a number of iterations of a loop by a brute-force evaluation.
1896 /* Bound on the number of iterations we try to evaluate. */
1898 #define MAX_ITERATIONS_TO_TRACK \
1899 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
1901 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
1902 result by a chain of operations such that all but exactly one of their
1903 operands are constants. */
1906 chain_of_csts_start (struct loop *loop, tree x)
1908 tree stmt = SSA_NAME_DEF_STMT (x);
1910 basic_block bb = bb_for_stmt (stmt);
1913 || !flow_bb_inside_loop_p (loop, bb))
1916 if (TREE_CODE (stmt) == PHI_NODE)
1918 if (bb == loop->header)
1924 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
1927 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
1929 if (SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF) == NULL_DEF_OPERAND_P)
1932 use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1933 if (use == NULL_USE_OPERAND_P)
1936 return chain_of_csts_start (loop, use);
1939 /* Determines whether the expression X is derived from a result of a phi node
1940 in header of LOOP such that
1942 * the derivation of X consists only from operations with constants
1943 * the initial value of the phi node is constant
1944 * the value of the phi node in the next iteration can be derived from the
1945 value in the current iteration by a chain of operations with constants.
1947 If such phi node exists, it is returned. If X is a constant, X is returned
1948 unchanged. Otherwise NULL_TREE is returned. */
1951 get_base_for (struct loop *loop, tree x)
1953 tree phi, init, next;
1955 if (is_gimple_min_invariant (x))
1958 phi = chain_of_csts_start (loop, x);
1962 init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1963 next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
1965 if (TREE_CODE (next) != SSA_NAME)
1968 if (!is_gimple_min_invariant (init))
1971 if (chain_of_csts_start (loop, next) != phi)
1977 /* Given an expression X, then
1979 * if X is NULL_TREE, we return the constant BASE.
1980 * otherwise X is a SSA name, whose value in the considered loop is derived
1981 by a chain of operations with constant from a result of a phi node in
1982 the header of the loop. Then we return value of X when the value of the
1983 result of this phi node is given by the constant BASE. */
1986 get_val_for (tree x, tree base)
1992 gcc_assert (is_gimple_min_invariant (base));
1997 stmt = SSA_NAME_DEF_STMT (x);
1998 if (TREE_CODE (stmt) == PHI_NODE)
2001 FOR_EACH_SSA_USE_OPERAND (op, stmt, iter, SSA_OP_USE)
2003 nx = USE_FROM_PTR (op);
2004 val = get_val_for (nx, base);
2006 val = fold (GIMPLE_STMT_OPERAND (stmt, 1));
2008 /* only iterate loop once. */
2012 /* Should never reach here. */
2016 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2017 by brute force -- i.e. by determining the value of the operands of the
2018 condition at EXIT in first few iterations of the loop (assuming that
2019 these values are constant) and determining the first one in that the
2020 condition is not satisfied. Returns the constant giving the number
2021 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
2024 loop_niter_by_eval (struct loop *loop, edge exit)
2026 tree cond, cnd, acnd;
2027 tree op[2], val[2], next[2], aval[2], phi[2];
2031 cond = last_stmt (exit->src);
2032 if (!cond || TREE_CODE (cond) != COND_EXPR)
2033 return chrec_dont_know;
2035 cnd = COND_EXPR_COND (cond);
2036 if (exit->flags & EDGE_TRUE_VALUE)
2037 cnd = invert_truthvalue (cnd);
2039 cmp = TREE_CODE (cnd);
2048 for (j = 0; j < 2; j++)
2049 op[j] = TREE_OPERAND (cnd, j);
2053 return chrec_dont_know;
2056 for (j = 0; j < 2; j++)
2058 phi[j] = get_base_for (loop, op[j]);
2060 return chrec_dont_know;
2063 for (j = 0; j < 2; j++)
2065 if (TREE_CODE (phi[j]) == PHI_NODE)
2067 val[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_preheader_edge (loop));
2068 next[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_latch_edge (loop));
2073 next[j] = NULL_TREE;
2078 /* Don't issue signed overflow warnings. */
2079 fold_defer_overflow_warnings ();
2081 for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
2083 for (j = 0; j < 2; j++)
2084 aval[j] = get_val_for (op[j], val[j]);
2086 acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]);
2087 if (acnd && integer_zerop (acnd))
2089 fold_undefer_and_ignore_overflow_warnings ();
2090 if (dump_file && (dump_flags & TDF_DETAILS))
2092 "Proved that loop %d iterates %d times using brute force.\n",
2094 return build_int_cst (unsigned_type_node, i);
2097 for (j = 0; j < 2; j++)
2099 val[j] = get_val_for (next[j], val[j]);
2100 if (!is_gimple_min_invariant (val[j]))
2102 fold_undefer_and_ignore_overflow_warnings ();
2103 return chrec_dont_know;
2108 fold_undefer_and_ignore_overflow_warnings ();
2110 return chrec_dont_know;
2113 /* Finds the exit of the LOOP by that the loop exits after a constant
2114 number of iterations and stores the exit edge to *EXIT. The constant
2115 giving the number of iterations of LOOP is returned. The number of
2116 iterations is determined using loop_niter_by_eval (i.e. by brute force
2117 evaluation). If we are unable to find the exit for that loop_niter_by_eval
2118 determines the number of iterations, chrec_dont_know is returned. */
2121 find_loop_niter_by_eval (struct loop *loop, edge *exit)
2124 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
2126 tree niter = NULL_TREE, aniter;
2129 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
2131 if (!just_once_each_iteration_p (loop, ex->src))
2134 aniter = loop_niter_by_eval (loop, ex);
2135 if (chrec_contains_undetermined (aniter))
2139 && !tree_int_cst_lt (aniter, niter))
2145 VEC_free (edge, heap, exits);
2147 return niter ? niter : chrec_dont_know;
2152 Analysis of upper bounds on number of iterations of a loop.
2156 /* Returns a constant upper bound on the value of expression VAL. VAL
2157 is considered to be unsigned. If its type is signed, its value must
2161 derive_constant_upper_bound (tree val)
2163 tree type = TREE_TYPE (val);
2164 tree op0, op1, subtype, maxt;
2165 double_int bnd, max, mmax, cst;
2168 if (INTEGRAL_TYPE_P (type))
2169 maxt = TYPE_MAX_VALUE (type);
2171 maxt = upper_bound_in_type (type, type);
2173 max = tree_to_double_int (maxt);
2175 switch (TREE_CODE (val))
2178 return tree_to_double_int (val);
2182 op0 = TREE_OPERAND (val, 0);
2183 subtype = TREE_TYPE (op0);
2184 if (!TYPE_UNSIGNED (subtype)
2185 /* If TYPE is also signed, the fact that VAL is nonnegative implies
2186 that OP0 is nonnegative. */
2187 && TYPE_UNSIGNED (type)
2188 && !tree_expr_nonnegative_p (op0))
2190 /* If we cannot prove that the casted expression is nonnegative,
2191 we cannot establish more useful upper bound than the precision
2192 of the type gives us. */
2196 /* We now know that op0 is an nonnegative value. Try deriving an upper
2198 bnd = derive_constant_upper_bound (op0);
2200 /* If the bound does not fit in TYPE, max. value of TYPE could be
2202 if (double_int_ucmp (max, bnd) < 0)
2209 op0 = TREE_OPERAND (val, 0);
2210 op1 = TREE_OPERAND (val, 1);
2212 if (TREE_CODE (op1) != INTEGER_CST
2213 || !tree_expr_nonnegative_p (op0))
2216 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
2217 choose the most logical way how to treat this constant regardless
2218 of the signedness of the type. */
2219 cst = tree_to_double_int (op1);
2220 cst = double_int_sext (cst, TYPE_PRECISION (type));
2221 if (TREE_CODE (val) == PLUS_EXPR)
2222 cst = double_int_neg (cst);
2224 bnd = derive_constant_upper_bound (op0);
2226 if (double_int_negative_p (cst))
2228 cst = double_int_neg (cst);
2229 /* Avoid CST == 0x80000... */
2230 if (double_int_negative_p (cst))
2233 /* OP0 + CST. We need to check that
2234 BND <= MAX (type) - CST. */
2236 mmax = double_int_add (max, double_int_neg (cst));
2237 if (double_int_ucmp (bnd, mmax) > 0)
2240 return double_int_add (bnd, cst);
2244 /* OP0 - CST, where CST >= 0.
2246 If TYPE is signed, we have already verified that OP0 >= 0, and we
2247 know that the result is nonnegative. This implies that
2250 If TYPE is unsigned, we must additionally know that OP0 >= CST,
2251 otherwise the operation underflows.
2254 /* This should only happen if the type is unsigned; however, for
2255 buggy programs that use overflowing signed arithmetics even with
2256 -fno-wrapv, this condition may also be true for signed values. */
2257 if (double_int_ucmp (bnd, cst) < 0)
2260 if (TYPE_UNSIGNED (type))
2262 tree tem = fold_binary (GE_EXPR, boolean_type_node, op0,
2263 double_int_to_tree (type, cst));
2264 if (!tem || integer_nonzerop (tem))
2268 bnd = double_int_add (bnd, double_int_neg (cst));
2273 case FLOOR_DIV_EXPR:
2274 case EXACT_DIV_EXPR:
2275 op0 = TREE_OPERAND (val, 0);
2276 op1 = TREE_OPERAND (val, 1);
2277 if (TREE_CODE (op1) != INTEGER_CST
2278 || tree_int_cst_sign_bit (op1))
2281 bnd = derive_constant_upper_bound (op0);
2282 return double_int_udiv (bnd, tree_to_double_int (op1), FLOOR_DIV_EXPR);
2285 op1 = TREE_OPERAND (val, 1);
2286 if (TREE_CODE (op1) != INTEGER_CST
2287 || tree_int_cst_sign_bit (op1))
2289 return tree_to_double_int (op1);
2292 stmt = SSA_NAME_DEF_STMT (val);
2293 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT
2294 || GIMPLE_STMT_OPERAND (stmt, 0) != val)
2296 return derive_constant_upper_bound (GIMPLE_STMT_OPERAND (stmt, 1));
2303 /* Records that every statement in LOOP is executed I_BOUND times.
2304 REALISTIC is true if I_BOUND is expected to be close the the real number
2305 of iterations. UPPER is true if we are sure the loop iterates at most
2309 record_niter_bound (struct loop *loop, double_int i_bound, bool realistic,
2312 /* Update the bounds only when there is no previous estimation, or when the current
2313 estimation is smaller. */
2315 && (!loop->any_upper_bound
2316 || double_int_ucmp (i_bound, loop->nb_iterations_upper_bound) < 0))
2318 loop->any_upper_bound = true;
2319 loop->nb_iterations_upper_bound = i_bound;
2322 && (!loop->any_estimate
2323 || double_int_ucmp (i_bound, loop->nb_iterations_estimate) < 0))
2325 loop->any_estimate = true;
2326 loop->nb_iterations_estimate = i_bound;
2330 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
2331 is true if the loop is exited immediately after STMT, and this exit
2332 is taken at last when the STMT is executed BOUND + 1 times.
2333 REALISTIC is true if BOUND is expected to be close the the real number
2334 of iterations. UPPER is true if we are sure the loop iterates at most
2335 BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */
2338 record_estimate (struct loop *loop, tree bound, double_int i_bound,
2339 tree at_stmt, bool is_exit, bool realistic, bool upper)
2344 if (dump_file && (dump_flags & TDF_DETAILS))
2346 fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : "");
2347 print_generic_expr (dump_file, at_stmt, TDF_SLIM);
2348 fprintf (dump_file, " is %sexecuted at most ",
2349 upper ? "" : "probably ");
2350 print_generic_expr (dump_file, bound, TDF_SLIM);
2351 fprintf (dump_file, " (bounded by ");
2352 dump_double_int (dump_file, i_bound, true);
2353 fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num);
2356 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
2357 real number of iterations. */
2358 if (TREE_CODE (bound) != INTEGER_CST)
2360 if (!upper && !realistic)
2363 /* If we have a guaranteed upper bound, record it in the appropriate
2367 struct nb_iter_bound *elt = GGC_NEW (struct nb_iter_bound);
2369 elt->bound = i_bound;
2370 elt->stmt = at_stmt;
2371 elt->is_exit = is_exit;
2372 elt->next = loop->bounds;
2376 /* Update the number of iteration estimates according to the bound.
2377 If at_stmt is an exit, then every statement in the loop is
2378 executed at most BOUND + 1 times. If it is not an exit, then
2379 some of the statements before it could be executed BOUND + 2
2380 times, if an exit of LOOP is before stmt. */
2381 exit = single_exit (loop);
2384 && dominated_by_p (CDI_DOMINATORS,
2385 exit->src, bb_for_stmt (at_stmt))))
2386 delta = double_int_one;
2388 delta = double_int_two;
2389 i_bound = double_int_add (i_bound, delta);
2391 /* If an overflow occurred, ignore the result. */
2392 if (double_int_ucmp (i_bound, delta) < 0)
2395 record_niter_bound (loop, i_bound, realistic, upper);
2398 /* Record the estimate on number of iterations of LOOP based on the fact that
2399 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
2400 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
2401 estimated number of iterations is expected to be close to the real one.
2402 UPPER is true if we are sure the induction variable does not wrap. */
2405 record_nonwrapping_iv (struct loop *loop, tree base, tree step, tree stmt,
2406 tree low, tree high, bool realistic, bool upper)
2408 tree niter_bound, extreme, delta;
2409 tree type = TREE_TYPE (base), unsigned_type;
2412 if (TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
2415 if (dump_file && (dump_flags & TDF_DETAILS))
2417 fprintf (dump_file, "Induction variable (");
2418 print_generic_expr (dump_file, TREE_TYPE (base), TDF_SLIM);
2419 fprintf (dump_file, ") ");
2420 print_generic_expr (dump_file, base, TDF_SLIM);
2421 fprintf (dump_file, " + ");
2422 print_generic_expr (dump_file, step, TDF_SLIM);
2423 fprintf (dump_file, " * iteration does not wrap in statement ");
2424 print_generic_expr (dump_file, stmt, TDF_SLIM);
2425 fprintf (dump_file, " in loop %d.\n", loop->num);
2428 unsigned_type = unsigned_type_for (type);
2429 base = fold_convert (unsigned_type, base);
2430 step = fold_convert (unsigned_type, step);
2432 if (tree_int_cst_sign_bit (step))
2434 extreme = fold_convert (unsigned_type, low);
2435 if (TREE_CODE (base) != INTEGER_CST)
2436 base = fold_convert (unsigned_type, high);
2437 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
2438 step = fold_build1 (NEGATE_EXPR, unsigned_type, step);
2442 extreme = fold_convert (unsigned_type, high);
2443 if (TREE_CODE (base) != INTEGER_CST)
2444 base = fold_convert (unsigned_type, low);
2445 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
2448 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
2449 would get out of the range. */
2450 niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step);
2451 max = derive_constant_upper_bound (niter_bound);
2452 record_estimate (loop, niter_bound, max, stmt, false, realistic, upper);
2455 /* Returns true if REF is a reference to an array at the end of a dynamically
2456 allocated structure. If this is the case, the array may be allocated larger
2457 than its upper bound implies. */
2460 array_at_struct_end_p (tree ref)
2462 tree base = get_base_address (ref);
2465 /* Unless the reference is through a pointer, the size of the array matches
2467 if (!base || !INDIRECT_REF_P (base))
2470 for (;handled_component_p (ref); ref = parent)
2472 parent = TREE_OPERAND (ref, 0);
2474 if (TREE_CODE (ref) == COMPONENT_REF)
2476 /* All fields of a union are at its end. */
2477 if (TREE_CODE (TREE_TYPE (parent)) == UNION_TYPE)
2480 /* Unless the field is at the end of the struct, we are done. */
2481 field = TREE_OPERAND (ref, 1);
2482 if (TREE_CHAIN (field))
2486 /* The other options are ARRAY_REF, ARRAY_RANGE_REF, VIEW_CONVERT_EXPR.
2487 In all these cases, we might be accessing the last element, and
2488 although in practice this will probably never happen, it is legal for
2489 the indices of this last element to exceed the bounds of the array.
2490 Therefore, continue checking. */
2493 gcc_assert (INDIRECT_REF_P (ref));
2497 /* Determine information about number of iterations a LOOP from the index
2498 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
2499 guaranteed to be executed in every iteration of LOOP. Callback for
2510 idx_infer_loop_bounds (tree base, tree *idx, void *dta)
2512 struct ilb_data *data = dta;
2513 tree ev, init, step;
2514 tree low, high, type, next;
2515 bool sign, upper = data->reliable, at_end = false;
2516 struct loop *loop = data->loop;
2518 if (TREE_CODE (base) != ARRAY_REF)
2521 /* For arrays at the end of the structure, we are not guaranteed that they
2522 do not really extend over their declared size. However, for arrays of
2523 size greater than one, this is unlikely to be intended. */
2524 if (array_at_struct_end_p (base))
2530 ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx));
2531 init = initial_condition (ev);
2532 step = evolution_part_in_loop_num (ev, loop->num);
2536 || TREE_CODE (step) != INTEGER_CST
2537 || integer_zerop (step)
2538 || tree_contains_chrecs (init, NULL)
2539 || chrec_contains_symbols_defined_in_loop (init, loop->num))
2542 low = array_ref_low_bound (base);
2543 high = array_ref_up_bound (base);
2545 /* The case of nonconstant bounds could be handled, but it would be
2547 if (TREE_CODE (low) != INTEGER_CST
2549 || TREE_CODE (high) != INTEGER_CST)
2551 sign = tree_int_cst_sign_bit (step);
2552 type = TREE_TYPE (step);
2554 /* The array of length 1 at the end of a structure most likely extends
2555 beyond its bounds. */
2557 && operand_equal_p (low, high, 0))
2560 /* In case the relevant bound of the array does not fit in type, or
2561 it does, but bound + step (in type) still belongs into the range of the
2562 array, the index may wrap and still stay within the range of the array
2563 (consider e.g. if the array is indexed by the full range of
2566 To make things simpler, we require both bounds to fit into type, although
2567 there are cases where this would not be strictly necessary. */
2568 if (!int_fits_type_p (high, type)
2569 || !int_fits_type_p (low, type))
2571 low = fold_convert (type, low);
2572 high = fold_convert (type, high);
2575 next = fold_binary (PLUS_EXPR, type, low, step);
2577 next = fold_binary (PLUS_EXPR, type, high, step);
2579 if (tree_int_cst_compare (low, next) <= 0
2580 && tree_int_cst_compare (next, high) <= 0)
2583 record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true, upper);
2587 /* Determine information about number of iterations a LOOP from the bounds
2588 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
2589 STMT is guaranteed to be executed in every iteration of LOOP.*/
2592 infer_loop_bounds_from_ref (struct loop *loop, tree stmt, tree ref,
2595 struct ilb_data data;
2599 data.reliable = reliable;
2600 for_each_index (&ref, idx_infer_loop_bounds, &data);
2603 /* Determine information about number of iterations of a LOOP from the way
2604 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
2605 executed in every iteration of LOOP. */
2608 infer_loop_bounds_from_array (struct loop *loop, tree stmt, bool reliable)
2612 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
2614 tree op0 = GIMPLE_STMT_OPERAND (stmt, 0);
2615 tree op1 = GIMPLE_STMT_OPERAND (stmt, 1);
2617 /* For each memory access, analyze its access function
2618 and record a bound on the loop iteration domain. */
2619 if (REFERENCE_CLASS_P (op0))
2620 infer_loop_bounds_from_ref (loop, stmt, op0, reliable);
2622 if (REFERENCE_CLASS_P (op1))
2623 infer_loop_bounds_from_ref (loop, stmt, op1, reliable);
2627 call = get_call_expr_in (stmt);
2631 call_expr_arg_iterator iter;
2633 FOR_EACH_CALL_EXPR_ARG (arg, iter, call)
2634 if (REFERENCE_CLASS_P (arg))
2635 infer_loop_bounds_from_ref (loop, stmt, arg, reliable);
2639 /* Determine information about number of iterations of a LOOP from the fact
2640 that signed arithmetics in STMT does not overflow. */
2643 infer_loop_bounds_from_signedness (struct loop *loop, tree stmt)
2645 tree def, base, step, scev, type, low, high;
2647 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
2650 def = GIMPLE_STMT_OPERAND (stmt, 0);
2652 if (TREE_CODE (def) != SSA_NAME)
2655 type = TREE_TYPE (def);
2656 if (!INTEGRAL_TYPE_P (type)
2657 || !TYPE_OVERFLOW_UNDEFINED (type))
2660 scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
2661 if (chrec_contains_undetermined (scev))
2664 base = initial_condition_in_loop_num (scev, loop->num);
2665 step = evolution_part_in_loop_num (scev, loop->num);
2668 || TREE_CODE (step) != INTEGER_CST
2669 || tree_contains_chrecs (base, NULL)
2670 || chrec_contains_symbols_defined_in_loop (base, loop->num))
2673 low = lower_bound_in_type (type, type);
2674 high = upper_bound_in_type (type, type);
2676 record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
2679 /* The following analyzers are extracting informations on the bounds
2680 of LOOP from the following undefined behaviors:
2682 - data references should not access elements over the statically
2685 - signed variables should not overflow when flag_wrapv is not set.
2689 infer_loop_bounds_from_undefined (struct loop *loop)
2693 block_stmt_iterator bsi;
2697 bbs = get_loop_body (loop);
2699 for (i = 0; i < loop->num_nodes; i++)
2703 /* If BB is not executed in each iteration of the loop, we cannot
2704 use the operations in it to infer reliable upper bound on the
2705 # of iterations of the loop. However, we can use it as a guess. */
2706 reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb);
2708 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
2710 tree stmt = bsi_stmt (bsi);
2712 infer_loop_bounds_from_array (loop, stmt, reliable);
2715 infer_loop_bounds_from_signedness (loop, stmt);
2723 /* Converts VAL to double_int. */
2726 gcov_type_to_double_int (gcov_type val)
2730 ret.low = (unsigned HOST_WIDE_INT) val;
2731 /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by
2732 the size of type. */
2733 val >>= HOST_BITS_PER_WIDE_INT - 1;
2735 ret.high = (unsigned HOST_WIDE_INT) val;
2740 /* Records estimates on numbers of iterations of LOOP. */
2743 estimate_numbers_of_iterations_loop (struct loop *loop)
2745 VEC (edge, heap) *exits;
2748 struct tree_niter_desc niter_desc;
2752 /* Give up if we already have tried to compute an estimation. */
2753 if (loop->estimate_state != EST_NOT_COMPUTED)
2755 loop->estimate_state = EST_AVAILABLE;
2756 loop->any_upper_bound = false;
2757 loop->any_estimate = false;
2759 exits = get_loop_exit_edges (loop);
2760 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
2762 if (!number_of_iterations_exit (loop, ex, &niter_desc, false))
2765 niter = niter_desc.niter;
2766 type = TREE_TYPE (niter);
2767 if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST)
2768 niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
2769 build_int_cst (type, 0),
2771 record_estimate (loop, niter, niter_desc.max,
2772 last_stmt (ex->src),
2775 VEC_free (edge, heap, exits);
2777 infer_loop_bounds_from_undefined (loop);
2779 /* If we have a measured profile, use it to estimate the number of
2781 if (loop->header->count != 0)
2783 gcov_type nit = expected_loop_iterations_unbounded (loop) + 1;
2784 bound = gcov_type_to_double_int (nit);
2785 record_niter_bound (loop, bound, true, false);
2788 /* If an upper bound is smaller than the realistic estimate of the
2789 number of iterations, use the upper bound instead. */
2790 if (loop->any_upper_bound
2791 && loop->any_estimate
2792 && double_int_ucmp (loop->nb_iterations_upper_bound,
2793 loop->nb_iterations_estimate) < 0)
2794 loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
2797 /* Records estimates on numbers of iterations of loops. */
2800 estimate_numbers_of_iterations (void)
2805 /* We don't want to issue signed overflow warnings while getting
2806 loop iteration estimates. */
2807 fold_defer_overflow_warnings ();
2809 FOR_EACH_LOOP (li, loop, 0)
2811 estimate_numbers_of_iterations_loop (loop);
2814 fold_undefer_and_ignore_overflow_warnings ();
2817 /* Returns true if statement S1 dominates statement S2. */
2820 stmt_dominates_stmt_p (tree s1, tree s2)
2822 basic_block bb1 = bb_for_stmt (s1), bb2 = bb_for_stmt (s2);
2830 block_stmt_iterator bsi;
2832 for (bsi = bsi_start (bb1); bsi_stmt (bsi) != s2; bsi_next (&bsi))
2833 if (bsi_stmt (bsi) == s1)
2839 return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
2842 /* Returns true when we can prove that the number of executions of
2843 STMT in the loop is at most NITER, according to the bound on
2844 the number of executions of the statement NITER_BOUND->stmt recorded in
2845 NITER_BOUND. If STMT is NULL, we must prove this bound for all
2846 statements in the loop. */
2849 n_of_executions_at_most (tree stmt,
2850 struct nb_iter_bound *niter_bound,
2853 double_int bound = niter_bound->bound;
2854 tree nit_type = TREE_TYPE (niter), e;
2857 gcc_assert (TYPE_UNSIGNED (nit_type));
2859 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
2860 the number of iterations is small. */
2861 if (!double_int_fits_to_tree_p (nit_type, bound))
2864 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
2865 times. This means that:
2867 -- if NITER_BOUND->is_exit is true, then everything before
2868 NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
2869 times, and everything after it at most NITER_BOUND->bound times.
2871 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
2872 is executed, then NITER_BOUND->stmt is executed as well in the same
2873 iteration (we conclude that if both statements belong to the same
2874 basic block, or if STMT is after NITER_BOUND->stmt), then STMT
2875 is executed at most NITER_BOUND->bound + 1 times. Otherwise STMT is
2876 executed at most NITER_BOUND->bound + 2 times. */
2878 if (niter_bound->is_exit)
2881 && stmt != niter_bound->stmt
2882 && stmt_dominates_stmt_p (niter_bound->stmt, stmt))
2890 || (bb_for_stmt (stmt) != bb_for_stmt (niter_bound->stmt)
2891 && !stmt_dominates_stmt_p (niter_bound->stmt, stmt)))
2893 bound = double_int_add (bound, double_int_one);
2894 if (double_int_zero_p (bound)
2895 || !double_int_fits_to_tree_p (nit_type, bound))
2901 e = fold_binary (cmp, boolean_type_node,
2902 niter, double_int_to_tree (nit_type, bound));
2903 return e && integer_nonzerop (e);
2906 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
2909 nowrap_type_p (tree type)
2911 if (INTEGRAL_TYPE_P (type)
2912 && TYPE_OVERFLOW_UNDEFINED (type))
2915 if (POINTER_TYPE_P (type))
2921 /* Return false only when the induction variable BASE + STEP * I is
2922 known to not overflow: i.e. when the number of iterations is small
2923 enough with respect to the step and initial condition in order to
2924 keep the evolution confined in TYPEs bounds. Return true when the
2925 iv is known to overflow or when the property is not computable.
2927 USE_OVERFLOW_SEMANTICS is true if this function should assume that
2928 the rules for overflow of the given language apply (e.g., that signed
2929 arithmetics in C does not overflow). */
2932 scev_probably_wraps_p (tree base, tree step,
2933 tree at_stmt, struct loop *loop,
2934 bool use_overflow_semantics)
2936 struct nb_iter_bound *bound;
2937 tree delta, step_abs;
2938 tree unsigned_type, valid_niter;
2939 tree type = TREE_TYPE (step);
2941 /* FIXME: We really need something like
2942 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
2944 We used to test for the following situation that frequently appears
2945 during address arithmetics:
2947 D.1621_13 = (long unsigned intD.4) D.1620_12;
2948 D.1622_14 = D.1621_13 * 8;
2949 D.1623_15 = (doubleD.29 *) D.1622_14;
2951 And derived that the sequence corresponding to D_14
2952 can be proved to not wrap because it is used for computing a
2953 memory access; however, this is not really the case -- for example,
2954 if D_12 = (unsigned char) [254,+,1], then D_14 has values
2955 2032, 2040, 0, 8, ..., but the code is still legal. */
2957 if (chrec_contains_undetermined (base)
2958 || chrec_contains_undetermined (step)
2959 || TREE_CODE (step) != INTEGER_CST)
2962 if (integer_zerop (step))
2965 /* If we can use the fact that signed and pointer arithmetics does not
2966 wrap, we are done. */
2967 if (use_overflow_semantics && nowrap_type_p (type))
2970 /* Don't issue signed overflow warnings. */
2971 fold_defer_overflow_warnings ();
2973 /* Otherwise, compute the number of iterations before we reach the
2974 bound of the type, and verify that the loop is exited before this
2976 unsigned_type = unsigned_type_for (type);
2977 base = fold_convert (unsigned_type, base);
2979 if (tree_int_cst_sign_bit (step))
2981 tree extreme = fold_convert (unsigned_type,
2982 lower_bound_in_type (type, type));
2983 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
2984 step_abs = fold_build1 (NEGATE_EXPR, unsigned_type,
2985 fold_convert (unsigned_type, step));
2989 tree extreme = fold_convert (unsigned_type,
2990 upper_bound_in_type (type, type));
2991 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
2992 step_abs = fold_convert (unsigned_type, step);
2995 valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
2997 estimate_numbers_of_iterations_loop (loop);
2998 for (bound = loop->bounds; bound; bound = bound->next)
3000 if (n_of_executions_at_most (at_stmt, bound, valid_niter))
3002 fold_undefer_and_ignore_overflow_warnings ();
3007 fold_undefer_and_ignore_overflow_warnings ();
3009 /* At this point we still don't have a proof that the iv does not
3010 overflow: give up. */
3014 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
3017 free_numbers_of_iterations_estimates_loop (struct loop *loop)
3019 struct nb_iter_bound *bound, *next;
3021 loop->nb_iterations = NULL;
3022 loop->estimate_state = EST_NOT_COMPUTED;
3023 for (bound = loop->bounds; bound; bound = next)
3029 loop->bounds = NULL;
3032 /* Frees the information on upper bounds on numbers of iterations of loops. */
3035 free_numbers_of_iterations_estimates (void)
3040 FOR_EACH_LOOP (li, loop, 0)
3042 free_numbers_of_iterations_estimates_loop (loop);
3046 /* Substitute value VAL for ssa name NAME inside expressions held
3050 substitute_in_loop_info (struct loop *loop, tree name, tree val)
3052 loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);