1 /* Functions to determine/estimate number of iterations of a loop.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation,
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"
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 { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
49 /* The maximum number of dominator BBs we search for conditions
50 of loop header copies we use for simplifying a conditional
52 #define MAX_DOMINATORS_TO_WALK 8
56 Analysis of number of iterations of an affine exit test.
60 /* Bounds on some value, BELOW <= X <= UP. */
68 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */
71 split_to_var_and_offset (tree expr, tree *var, mpz_t offset)
73 tree type = TREE_TYPE (expr);
79 mpz_set_ui (offset, 0);
81 switch (TREE_CODE (expr))
88 case POINTER_PLUS_EXPR:
89 op0 = TREE_OPERAND (expr, 0);
90 op1 = TREE_OPERAND (expr, 1);
92 if (TREE_CODE (op1) != INTEGER_CST)
96 /* Always sign extend the offset. */
97 off = double_int_sext (tree_to_double_int (op1),
98 TYPE_PRECISION (type));
99 mpz_set_double_int (offset, off, false);
103 *var = build_int_cst_type (type, 0);
104 off = tree_to_double_int (expr);
105 mpz_set_double_int (offset, off, TYPE_UNSIGNED (type));
113 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
114 in TYPE to MIN and MAX. */
117 determine_value_range (tree type, tree var, mpz_t off,
118 mpz_t min, mpz_t max)
120 /* If the expression is a constant, we know its value exactly. */
121 if (integer_zerop (var))
128 /* If the computation may wrap, we know nothing about the value, except for
129 the range of the type. */
130 get_type_static_bounds (type, min, max);
131 if (!nowrap_type_p (type))
134 /* Since the addition of OFF does not wrap, if OFF is positive, then we may
135 add it to MIN, otherwise to MAX. */
136 if (mpz_sgn (off) < 0)
137 mpz_add (max, max, off);
139 mpz_add (min, min, off);
142 /* Stores the bounds on the difference of the values of the expressions
143 (var + X) and (var + Y), computed in TYPE, to BNDS. */
146 bound_difference_of_offsetted_base (tree type, mpz_t x, mpz_t y,
149 int rel = mpz_cmp (x, y);
150 bool may_wrap = !nowrap_type_p (type);
153 /* If X == Y, then the expressions are always equal.
154 If X > Y, there are the following possibilities:
155 a) neither of var + X and var + Y overflow or underflow, or both of
156 them do. Then their difference is X - Y.
157 b) var + X overflows, and var + Y does not. Then the values of the
158 expressions are var + X - M and var + Y, where M is the range of
159 the type, and their difference is X - Y - M.
160 c) var + Y underflows and var + X does not. Their difference again
162 Therefore, if the arithmetics in type does not overflow, then the
163 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
164 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
165 (X - Y, X - Y + M). */
169 mpz_set_ui (bnds->below, 0);
170 mpz_set_ui (bnds->up, 0);
175 mpz_set_double_int (m, double_int_mask (TYPE_PRECISION (type)), true);
176 mpz_add_ui (m, m, 1);
177 mpz_sub (bnds->up, x, y);
178 mpz_set (bnds->below, bnds->up);
183 mpz_sub (bnds->below, bnds->below, m);
185 mpz_add (bnds->up, bnds->up, m);
191 /* From condition C0 CMP C1 derives information regarding the
192 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
193 and stores it to BNDS. */
196 refine_bounds_using_guard (tree type, tree varx, mpz_t offx,
197 tree vary, mpz_t offy,
198 tree c0, enum tree_code cmp, tree c1,
201 tree varc0, varc1, tmp, ctype;
202 mpz_t offc0, offc1, loffx, loffy, bnd;
204 bool no_wrap = nowrap_type_p (type);
213 STRIP_SIGN_NOPS (c0);
214 STRIP_SIGN_NOPS (c1);
215 ctype = TREE_TYPE (c0);
216 if (!useless_type_conversion_p (ctype, type))
222 /* We could derive quite precise information from EQ_EXPR, however, such
223 a guard is unlikely to appear, so we do not bother with handling
228 /* NE_EXPR comparisons do not contain much of useful information, except for
229 special case of comparing with the bounds of the type. */
230 if (TREE_CODE (c1) != INTEGER_CST
231 || !INTEGRAL_TYPE_P (type))
234 /* Ensure that the condition speaks about an expression in the same type
236 ctype = TREE_TYPE (c0);
237 if (TYPE_PRECISION (ctype) != TYPE_PRECISION (type))
239 c0 = fold_convert (type, c0);
240 c1 = fold_convert (type, c1);
242 if (TYPE_MIN_VALUE (type)
243 && operand_equal_p (c1, TYPE_MIN_VALUE (type), 0))
248 if (TYPE_MAX_VALUE (type)
249 && operand_equal_p (c1, TYPE_MAX_VALUE (type), 0))
262 split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0);
263 split_to_var_and_offset (expand_simple_operations (c1), &varc1, offc1);
265 /* We are only interested in comparisons of expressions based on VARX and
266 VARY. TODO -- we might also be able to derive some bounds from
267 expressions containing just one of the variables. */
269 if (operand_equal_p (varx, varc1, 0))
271 tmp = varc0; varc0 = varc1; varc1 = tmp;
272 mpz_swap (offc0, offc1);
273 cmp = swap_tree_comparison (cmp);
276 if (!operand_equal_p (varx, varc0, 0)
277 || !operand_equal_p (vary, varc1, 0))
280 mpz_init_set (loffx, offx);
281 mpz_init_set (loffy, offy);
283 if (cmp == GT_EXPR || cmp == GE_EXPR)
285 tmp = varx; varx = vary; vary = tmp;
286 mpz_swap (offc0, offc1);
287 mpz_swap (loffx, loffy);
288 cmp = swap_tree_comparison (cmp);
292 /* If there is no overflow, the condition implies that
294 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
296 The overflows and underflows may complicate things a bit; each
297 overflow decreases the appropriate offset by M, and underflow
298 increases it by M. The above inequality would not necessarily be
301 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
302 VARX + OFFC0 overflows, but VARX + OFFX does not.
303 This may only happen if OFFX < OFFC0.
304 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
305 VARY + OFFC1 underflows and VARY + OFFY does not.
306 This may only happen if OFFY > OFFC1. */
315 x_ok = (integer_zerop (varx)
316 || mpz_cmp (loffx, offc0) >= 0);
317 y_ok = (integer_zerop (vary)
318 || mpz_cmp (loffy, offc1) <= 0);
324 mpz_sub (bnd, loffx, loffy);
325 mpz_add (bnd, bnd, offc1);
326 mpz_sub (bnd, bnd, offc0);
329 mpz_sub_ui (bnd, bnd, 1);
334 if (mpz_cmp (bnds->below, bnd) < 0)
335 mpz_set (bnds->below, bnd);
339 if (mpz_cmp (bnd, bnds->up) < 0)
340 mpz_set (bnds->up, bnd);
352 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
353 The subtraction is considered to be performed in arbitrary precision,
356 We do not attempt to be too clever regarding the value ranges of X and
357 Y; most of the time, they are just integers or ssa names offsetted by
358 integer. However, we try to use the information contained in the
359 comparisons before the loop (usually created by loop header copying). */
362 bound_difference (struct loop *loop, tree x, tree y, bounds *bnds)
364 tree type = TREE_TYPE (x);
367 mpz_t minx, maxx, miny, maxy;
375 /* Get rid of unnecessary casts, but preserve the value of
380 mpz_init (bnds->below);
384 split_to_var_and_offset (x, &varx, offx);
385 split_to_var_and_offset (y, &vary, offy);
387 if (!integer_zerop (varx)
388 && operand_equal_p (varx, vary, 0))
390 /* Special case VARX == VARY -- we just need to compare the
391 offsets. The matters are a bit more complicated in the
392 case addition of offsets may wrap. */
393 bound_difference_of_offsetted_base (type, offx, offy, bnds);
397 /* Otherwise, use the value ranges to determine the initial
398 estimates on below and up. */
403 determine_value_range (type, varx, offx, minx, maxx);
404 determine_value_range (type, vary, offy, miny, maxy);
406 mpz_sub (bnds->below, minx, maxy);
407 mpz_sub (bnds->up, maxx, miny);
414 /* If both X and Y are constants, we cannot get any more precise. */
415 if (integer_zerop (varx) && integer_zerop (vary))
418 /* Now walk the dominators of the loop header and use the entry
419 guards to refine the estimates. */
420 for (bb = loop->header;
421 bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK;
422 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
424 if (!single_pred_p (bb))
426 e = single_pred_edge (bb);
428 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
431 cond = last_stmt (e->src);
432 c0 = gimple_cond_lhs (cond);
433 cmp = gimple_cond_code (cond);
434 c1 = gimple_cond_rhs (cond);
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 (POINTER_TYPE_P (type))
685 if (TREE_CODE (mod) != INTEGER_CST)
687 if (integer_nonzerop (mod))
688 mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
689 tmod = fold_convert (type1, mod);
692 mpz_set_double_int (mmod, tree_to_double_int (mod), true);
693 mpz_neg (mmod, mmod);
695 if (integer_nonzerop (iv0->step))
697 /* The final value of the iv is iv1->base + MOD, assuming that this
698 computation does not overflow, and that
699 iv0->base <= iv1->base + MOD. */
700 if (!iv0->no_overflow && !integer_zerop (mod))
702 bound = fold_build2 (MINUS_EXPR, type,
703 TYPE_MAX_VALUE (type1), tmod);
704 assumption = fold_build2 (LE_EXPR, boolean_type_node,
706 if (integer_zerop (assumption))
709 if (mpz_cmp (mmod, bnds->below) < 0)
710 noloop = boolean_false_node;
712 noloop = fold_build2 (GT_EXPR, boolean_type_node,
714 fold_build2 (PLUS_EXPR, type1,
719 /* The final value of the iv is iv0->base - MOD, assuming that this
720 computation does not overflow, and that
721 iv0->base - MOD <= iv1->base. */
722 if (!iv1->no_overflow && !integer_zerop (mod))
724 bound = fold_build2 (PLUS_EXPR, type1,
725 TYPE_MIN_VALUE (type1), tmod);
726 assumption = fold_build2 (GE_EXPR, boolean_type_node,
728 if (integer_zerop (assumption))
731 if (mpz_cmp (mmod, bnds->below) < 0)
732 noloop = boolean_false_node;
734 noloop = fold_build2 (GT_EXPR, boolean_type_node,
735 fold_build2 (MINUS_EXPR, type1,
740 if (!integer_nonzerop (assumption))
741 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
744 if (!integer_zerop (noloop))
745 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
748 bounds_add (bnds, tree_to_double_int (mod), type);
749 *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod);
757 /* Add assertions to NITER that ensure that the control variable of the loop
758 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
759 are TYPE. Returns false if we can prove that there is an overflow, true
760 otherwise. STEP is the absolute value of the step. */
763 assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
764 struct tree_niter_desc *niter, tree step)
766 tree bound, d, assumption, diff;
767 tree niter_type = TREE_TYPE (step);
769 if (integer_nonzerop (iv0->step))
771 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
772 if (iv0->no_overflow)
775 /* If iv0->base is a constant, we can determine the last value before
776 overflow precisely; otherwise we conservatively assume
779 if (TREE_CODE (iv0->base) == INTEGER_CST)
781 d = fold_build2 (MINUS_EXPR, niter_type,
782 fold_convert (niter_type, TYPE_MAX_VALUE (type)),
783 fold_convert (niter_type, iv0->base));
784 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
787 diff = fold_build2 (MINUS_EXPR, niter_type, step,
788 build_int_cst (niter_type, 1));
789 bound = fold_build2 (MINUS_EXPR, type,
790 TYPE_MAX_VALUE (type), fold_convert (type, diff));
791 assumption = fold_build2 (LE_EXPR, boolean_type_node,
796 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
797 if (iv1->no_overflow)
800 if (TREE_CODE (iv1->base) == INTEGER_CST)
802 d = fold_build2 (MINUS_EXPR, niter_type,
803 fold_convert (niter_type, iv1->base),
804 fold_convert (niter_type, TYPE_MIN_VALUE (type)));
805 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
808 diff = fold_build2 (MINUS_EXPR, niter_type, step,
809 build_int_cst (niter_type, 1));
810 bound = fold_build2 (PLUS_EXPR, type,
811 TYPE_MIN_VALUE (type), fold_convert (type, diff));
812 assumption = fold_build2 (GE_EXPR, boolean_type_node,
816 if (integer_zerop (assumption))
818 if (!integer_nonzerop (assumption))
819 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
820 niter->assumptions, assumption);
822 iv0->no_overflow = true;
823 iv1->no_overflow = true;
827 /* Add an assumption to NITER that a loop whose ending condition
828 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
829 bounds the value of IV1->base - IV0->base. */
832 assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
833 struct tree_niter_desc *niter, bounds *bnds)
835 tree assumption = boolean_true_node, bound, diff;
836 tree mbz, mbzl, mbzr, type1;
837 bool rolls_p, no_overflow_p;
841 /* We are going to compute the number of iterations as
842 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
843 variant of TYPE. This formula only works if
845 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
847 (where MAX is the maximum value of the unsigned variant of TYPE, and
848 the computations in this formula are performed in full precision
851 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
852 we have a condition of form iv0->base - step < iv1->base before the loop,
853 and for loops iv0->base < iv1->base - step * i the condition
854 iv0->base < iv1->base + step, due to loop header copying, which enable us
855 to prove the lower bound.
857 The upper bound is more complicated. Unless the expressions for initial
858 and final value themselves contain enough information, we usually cannot
859 derive it from the context. */
861 /* First check whether the answer does not follow from the bounds we gathered
863 if (integer_nonzerop (iv0->step))
864 dstep = tree_to_double_int (iv0->step);
867 dstep = double_int_sext (tree_to_double_int (iv1->step),
868 TYPE_PRECISION (type));
869 dstep = double_int_neg (dstep);
873 mpz_set_double_int (mstep, dstep, true);
874 mpz_neg (mstep, mstep);
875 mpz_add_ui (mstep, mstep, 1);
877 rolls_p = mpz_cmp (mstep, bnds->below) <= 0;
880 mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true);
881 mpz_add (max, max, mstep);
882 no_overflow_p = (mpz_cmp (bnds->up, max) <= 0
883 /* For pointers, only values lying inside a single object
884 can be compared or manipulated by pointer arithmetics.
885 Gcc in general does not allow or handle objects larger
886 than half of the address space, hence the upper bound
887 is satisfied for pointers. */
888 || POINTER_TYPE_P (type));
892 if (rolls_p && no_overflow_p)
896 if (POINTER_TYPE_P (type))
899 /* Now the hard part; we must formulate the assumption(s) as expressions, and
900 we must be careful not to introduce overflow. */
902 if (integer_nonzerop (iv0->step))
904 diff = fold_build2 (MINUS_EXPR, type1,
905 iv0->step, build_int_cst (type1, 1));
907 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
908 0 address never belongs to any object, we can assume this for
910 if (!POINTER_TYPE_P (type))
912 bound = fold_build2 (PLUS_EXPR, type1,
913 TYPE_MIN_VALUE (type), diff);
914 assumption = fold_build2 (GE_EXPR, boolean_type_node,
918 /* And then we can compute iv0->base - diff, and compare it with
920 mbzl = fold_build2 (MINUS_EXPR, type1,
921 fold_convert (type1, iv0->base), diff);
922 mbzr = fold_convert (type1, iv1->base);
926 diff = fold_build2 (PLUS_EXPR, type1,
927 iv1->step, build_int_cst (type1, 1));
929 if (!POINTER_TYPE_P (type))
931 bound = fold_build2 (PLUS_EXPR, type1,
932 TYPE_MAX_VALUE (type), diff);
933 assumption = fold_build2 (LE_EXPR, boolean_type_node,
937 mbzl = fold_convert (type1, iv0->base);
938 mbzr = fold_build2 (MINUS_EXPR, type1,
939 fold_convert (type1, iv1->base), diff);
942 if (!integer_nonzerop (assumption))
943 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
944 niter->assumptions, assumption);
947 mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr);
948 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
949 niter->may_be_zero, mbz);
953 /* Determines number of iterations of loop whose ending condition
954 is IV0 < IV1. TYPE is the type of the iv. The number of
955 iterations is stored to NITER. BNDS bounds the difference
956 IV1->base - IV0->base. */
959 number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
960 struct tree_niter_desc *niter,
961 bool never_infinite ATTRIBUTE_UNUSED,
964 tree niter_type = unsigned_type_for (type);
968 if (integer_nonzerop (iv0->step))
970 niter->control = *iv0;
971 niter->cmp = LT_EXPR;
972 niter->bound = iv1->base;
976 niter->control = *iv1;
977 niter->cmp = GT_EXPR;
978 niter->bound = iv0->base;
981 delta = fold_build2 (MINUS_EXPR, niter_type,
982 fold_convert (niter_type, iv1->base),
983 fold_convert (niter_type, iv0->base));
985 /* First handle the special case that the step is +-1. */
986 if ((integer_onep (iv0->step) && integer_zerop (iv1->step))
987 || (integer_all_onesp (iv1->step) && integer_zerop (iv0->step)))
989 /* for (i = iv0->base; i < iv1->base; i++)
993 for (i = iv1->base; i > iv0->base; i--).
995 In both cases # of iterations is iv1->base - iv0->base, assuming that
996 iv1->base >= iv0->base.
998 First try to derive a lower bound on the value of
999 iv1->base - iv0->base, computed in full precision. If the difference
1000 is nonnegative, we are done, otherwise we must record the
1003 if (mpz_sgn (bnds->below) < 0)
1004 niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
1005 iv1->base, iv0->base);
1006 niter->niter = delta;
1007 niter->max = mpz_get_double_int (niter_type, bnds->up, false);
1011 if (integer_nonzerop (iv0->step))
1012 step = fold_convert (niter_type, iv0->step);
1014 step = fold_convert (niter_type,
1015 fold_build1 (NEGATE_EXPR, type, iv1->step));
1017 /* If we can determine the final value of the control iv exactly, we can
1018 transform the condition to != comparison. In particular, this will be
1019 the case if DELTA is constant. */
1020 if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step,
1025 zps.base = build_int_cst (niter_type, 0);
1027 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1028 zps does not overflow. */
1029 zps.no_overflow = true;
1031 return number_of_iterations_ne (type, &zps, delta, niter, true, bnds);
1034 /* Make sure that the control iv does not overflow. */
1035 if (!assert_no_overflow_lt (type, iv0, iv1, niter, step))
1038 /* We determine the number of iterations as (delta + step - 1) / step. For
1039 this to work, we must know that iv1->base >= iv0->base - step + 1,
1040 otherwise the loop does not roll. */
1041 assert_loop_rolls_lt (type, iv0, iv1, niter, bnds);
1043 s = fold_build2 (MINUS_EXPR, niter_type,
1044 step, build_int_cst (niter_type, 1));
1045 delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
1046 niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
1050 mpz_set_double_int (mstep, tree_to_double_int (step), true);
1051 mpz_add (tmp, bnds->up, mstep);
1052 mpz_sub_ui (tmp, tmp, 1);
1053 mpz_fdiv_q (tmp, tmp, mstep);
1054 niter->max = mpz_get_double_int (niter_type, tmp, false);
1061 /* Determines number of iterations of loop whose ending condition
1062 is IV0 <= IV1. TYPE is the type of the iv. The number of
1063 iterations is stored to NITER. NEVER_INFINITE is true if
1064 we know that this condition must eventually become false (we derived this
1065 earlier, and possibly set NITER->assumptions to make sure this
1066 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1069 number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1,
1070 struct tree_niter_desc *niter, bool never_infinite,
1075 if (POINTER_TYPE_P (type))
1078 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1079 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1080 value of the type. This we must know anyway, since if it is
1081 equal to this value, the loop rolls forever. */
1083 if (!never_infinite)
1085 if (integer_nonzerop (iv0->step))
1086 assumption = fold_build2 (NE_EXPR, boolean_type_node,
1087 iv1->base, TYPE_MAX_VALUE (type1));
1089 assumption = fold_build2 (NE_EXPR, boolean_type_node,
1090 iv0->base, TYPE_MIN_VALUE (type1));
1092 if (integer_zerop (assumption))
1094 if (!integer_nonzerop (assumption))
1095 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1096 niter->assumptions, assumption);
1099 if (integer_nonzerop (iv0->step))
1100 iv1->base = fold_build2 (PLUS_EXPR, type1,
1101 iv1->base, build_int_cst (type1, 1));
1103 iv0->base = fold_build2 (MINUS_EXPR, type1,
1104 iv0->base, build_int_cst (type1, 1));
1106 bounds_add (bnds, double_int_one, type1);
1108 return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite, bnds);
1111 /* Dumps description of affine induction variable IV to FILE. */
1114 dump_affine_iv (FILE *file, affine_iv *iv)
1116 if (!integer_zerop (iv->step))
1117 fprintf (file, "[");
1119 print_generic_expr (dump_file, iv->base, TDF_SLIM);
1121 if (!integer_zerop (iv->step))
1123 fprintf (file, ", + , ");
1124 print_generic_expr (dump_file, iv->step, TDF_SLIM);
1125 fprintf (file, "]%s", iv->no_overflow ? "(no_overflow)" : "");
1129 /* Determine the number of iterations according to condition (for staying
1130 inside loop) which compares two induction variables using comparison
1131 operator CODE. The induction variable on left side of the comparison
1132 is IV0, the right-hand side is IV1. Both induction variables must have
1133 type TYPE, which must be an integer or pointer type. The steps of the
1134 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1136 LOOP is the loop whose number of iterations we are determining.
1138 ONLY_EXIT is true if we are sure this is the only way the loop could be
1139 exited (including possibly non-returning function calls, exceptions, etc.)
1140 -- in this case we can use the information whether the control induction
1141 variables can overflow or not in a more efficient way.
1143 The results (number of iterations and assumptions as described in
1144 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
1145 Returns false if it fails to determine number of iterations, true if it
1146 was determined (possibly with some assumptions). */
1149 number_of_iterations_cond (struct loop *loop,
1150 tree type, affine_iv *iv0, enum tree_code code,
1151 affine_iv *iv1, struct tree_niter_desc *niter,
1154 bool never_infinite, ret;
1157 /* The meaning of these assumptions is this:
1159 then the rest of information does not have to be valid
1160 if may_be_zero then the loop does not roll, even if
1162 niter->assumptions = boolean_true_node;
1163 niter->may_be_zero = boolean_false_node;
1164 niter->niter = NULL_TREE;
1165 niter->max = double_int_zero;
1167 niter->bound = NULL_TREE;
1168 niter->cmp = ERROR_MARK;
1170 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1171 the control variable is on lhs. */
1172 if (code == GE_EXPR || code == GT_EXPR
1173 || (code == NE_EXPR && integer_zerop (iv0->step)))
1176 code = swap_tree_comparison (code);
1181 /* If this is not the only possible exit from the loop, the information
1182 that the induction variables cannot overflow as derived from
1183 signedness analysis cannot be relied upon. We use them e.g. in the
1184 following way: given loop for (i = 0; i <= n; i++), if i is
1185 signed, it cannot overflow, thus this loop is equivalent to
1186 for (i = 0; i < n + 1; i++); however, if n == MAX, but the loop
1187 is exited in some other way before i overflows, this transformation
1188 is incorrect (the new loop exits immediately). */
1189 iv0->no_overflow = false;
1190 iv1->no_overflow = false;
1193 if (POINTER_TYPE_P (type))
1195 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1196 to the same object. If they do, the control variable cannot wrap
1197 (as wrap around the bounds of memory will never return a pointer
1198 that would be guaranteed to point to the same object, even if we
1199 avoid undefined behavior by casting to size_t and back). The
1200 restrictions on pointer arithmetics and comparisons of pointers
1201 ensure that using the no-overflow assumptions is correct in this
1202 case even if ONLY_EXIT is false. */
1203 iv0->no_overflow = true;
1204 iv1->no_overflow = true;
1207 /* If the control induction variable does not overflow, the loop obviously
1208 cannot be infinite. */
1209 if (!integer_zerop (iv0->step) && iv0->no_overflow)
1210 never_infinite = true;
1211 else if (!integer_zerop (iv1->step) && iv1->no_overflow)
1212 never_infinite = true;
1214 never_infinite = false;
1216 /* We can handle the case when neither of the sides of the comparison is
1217 invariant, provided that the test is NE_EXPR. This rarely occurs in
1218 practice, but it is simple enough to manage. */
1219 if (!integer_zerop (iv0->step) && !integer_zerop (iv1->step))
1221 if (code != NE_EXPR)
1224 iv0->step = fold_binary_to_constant (MINUS_EXPR, type,
1225 iv0->step, iv1->step);
1226 iv0->no_overflow = false;
1227 iv1->step = build_int_cst (type, 0);
1228 iv1->no_overflow = true;
1231 /* If the result of the comparison is a constant, the loop is weird. More
1232 precise handling would be possible, but the situation is not common enough
1233 to waste time on it. */
1234 if (integer_zerop (iv0->step) && integer_zerop (iv1->step))
1237 /* Ignore loops of while (i-- < 10) type. */
1238 if (code != NE_EXPR)
1240 if (iv0->step && tree_int_cst_sign_bit (iv0->step))
1243 if (!integer_zerop (iv1->step) && !tree_int_cst_sign_bit (iv1->step))
1247 /* If the loop exits immediately, there is nothing to do. */
1248 if (integer_zerop (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
1250 niter->niter = build_int_cst (unsigned_type_for (type), 0);
1251 niter->max = double_int_zero;
1255 /* OK, now we know we have a senseful loop. Handle several cases, depending
1256 on what comparison operator is used. */
1257 bound_difference (loop, iv1->base, iv0->base, &bnds);
1259 if (dump_file && (dump_flags & TDF_DETAILS))
1262 "Analyzing # of iterations of loop %d\n", loop->num);
1264 fprintf (dump_file, " exit condition ");
1265 dump_affine_iv (dump_file, iv0);
1266 fprintf (dump_file, " %s ",
1267 code == NE_EXPR ? "!="
1268 : code == LT_EXPR ? "<"
1270 dump_affine_iv (dump_file, iv1);
1271 fprintf (dump_file, "\n");
1273 fprintf (dump_file, " bounds on difference of bases: ");
1274 mpz_out_str (dump_file, 10, bnds.below);
1275 fprintf (dump_file, " ... ");
1276 mpz_out_str (dump_file, 10, bnds.up);
1277 fprintf (dump_file, "\n");
1283 gcc_assert (integer_zerop (iv1->step));
1284 ret = number_of_iterations_ne (type, iv0, iv1->base, niter,
1285 never_infinite, &bnds);
1289 ret = number_of_iterations_lt (type, iv0, iv1, niter, never_infinite,
1294 ret = number_of_iterations_le (type, iv0, iv1, niter, never_infinite,
1302 mpz_clear (bnds.up);
1303 mpz_clear (bnds.below);
1305 if (dump_file && (dump_flags & TDF_DETAILS))
1309 fprintf (dump_file, " result:\n");
1310 if (!integer_nonzerop (niter->assumptions))
1312 fprintf (dump_file, " under assumptions ");
1313 print_generic_expr (dump_file, niter->assumptions, TDF_SLIM);
1314 fprintf (dump_file, "\n");
1317 if (!integer_zerop (niter->may_be_zero))
1319 fprintf (dump_file, " zero if ");
1320 print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
1321 fprintf (dump_file, "\n");
1324 fprintf (dump_file, " # of iterations ");
1325 print_generic_expr (dump_file, niter->niter, TDF_SLIM);
1326 fprintf (dump_file, ", bounded by ");
1327 dump_double_int (dump_file, niter->max, true);
1328 fprintf (dump_file, "\n");
1331 fprintf (dump_file, " failed\n\n");
1336 /* Substitute NEW for OLD in EXPR and fold the result. */
1339 simplify_replace_tree (tree expr, tree old, tree new_tree)
1342 tree ret = NULL_TREE, e, se;
1348 || operand_equal_p (expr, old, 0))
1349 return unshare_expr (new_tree);
1354 n = TREE_OPERAND_LENGTH (expr);
1355 for (i = 0; i < n; i++)
1357 e = TREE_OPERAND (expr, i);
1358 se = simplify_replace_tree (e, old, new_tree);
1363 ret = copy_node (expr);
1365 TREE_OPERAND (ret, i) = se;
1368 return (ret ? fold (ret) : expr);
1371 /* Expand definitions of ssa names in EXPR as long as they are simple
1372 enough, and return the new expression. */
1375 expand_simple_operations (tree expr)
1378 tree ret = NULL_TREE, e, ee, e1;
1379 enum tree_code code;
1382 if (expr == NULL_TREE)
1385 if (is_gimple_min_invariant (expr))
1388 code = TREE_CODE (expr);
1389 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
1391 n = TREE_OPERAND_LENGTH (expr);
1392 for (i = 0; i < n; i++)
1394 e = TREE_OPERAND (expr, i);
1395 ee = expand_simple_operations (e);
1400 ret = copy_node (expr);
1402 TREE_OPERAND (ret, i) = ee;
1408 fold_defer_overflow_warnings ();
1410 fold_undefer_and_ignore_overflow_warnings ();
1414 if (TREE_CODE (expr) != SSA_NAME)
1417 stmt = SSA_NAME_DEF_STMT (expr);
1418 if (gimple_code (stmt) == GIMPLE_PHI)
1420 basic_block src, dest;
1422 if (gimple_phi_num_args (stmt) != 1)
1424 e = PHI_ARG_DEF (stmt, 0);
1426 /* Avoid propagating through loop exit phi nodes, which
1427 could break loop-closed SSA form restrictions. */
1428 dest = gimple_bb (stmt);
1429 src = single_pred (dest);
1430 if (TREE_CODE (e) == SSA_NAME
1431 && src->loop_father != dest->loop_father)
1434 return expand_simple_operations (e);
1436 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1439 e = gimple_assign_rhs1 (stmt);
1440 code = gimple_assign_rhs_code (stmt);
1441 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1443 if (is_gimple_min_invariant (e))
1446 if (code == SSA_NAME)
1447 return expand_simple_operations (e);
1456 /* Casts are simple. */
1457 ee = expand_simple_operations (e);
1458 return fold_build1 (code, TREE_TYPE (expr), ee);
1462 case POINTER_PLUS_EXPR:
1463 /* And increments and decrements by a constant are simple. */
1464 e1 = gimple_assign_rhs2 (stmt);
1465 if (!is_gimple_min_invariant (e1))
1468 ee = expand_simple_operations (e);
1469 return fold_build2 (code, TREE_TYPE (expr), ee, e1);
1476 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1477 expression (or EXPR unchanged, if no simplification was possible). */
1480 tree_simplify_using_condition_1 (tree cond, tree expr)
1483 tree e, te, e0, e1, e2, notcond;
1484 enum tree_code code = TREE_CODE (expr);
1486 if (code == INTEGER_CST)
1489 if (code == TRUTH_OR_EXPR
1490 || code == TRUTH_AND_EXPR
1491 || code == COND_EXPR)
1495 e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0));
1496 if (TREE_OPERAND (expr, 0) != e0)
1499 e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1));
1500 if (TREE_OPERAND (expr, 1) != e1)
1503 if (code == COND_EXPR)
1505 e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2));
1506 if (TREE_OPERAND (expr, 2) != e2)
1514 if (code == COND_EXPR)
1515 expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
1517 expr = fold_build2 (code, boolean_type_node, e0, e1);
1523 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
1524 propagation, and vice versa. Fold does not handle this, since it is
1525 considered too expensive. */
1526 if (TREE_CODE (cond) == EQ_EXPR)
1528 e0 = TREE_OPERAND (cond, 0);
1529 e1 = TREE_OPERAND (cond, 1);
1531 /* We know that e0 == e1. Check whether we cannot simplify expr
1533 e = simplify_replace_tree (expr, e0, e1);
1534 if (integer_zerop (e) || integer_nonzerop (e))
1537 e = simplify_replace_tree (expr, e1, e0);
1538 if (integer_zerop (e) || integer_nonzerop (e))
1541 if (TREE_CODE (expr) == EQ_EXPR)
1543 e0 = TREE_OPERAND (expr, 0);
1544 e1 = TREE_OPERAND (expr, 1);
1546 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
1547 e = simplify_replace_tree (cond, e0, e1);
1548 if (integer_zerop (e))
1550 e = simplify_replace_tree (cond, e1, e0);
1551 if (integer_zerop (e))
1554 if (TREE_CODE (expr) == NE_EXPR)
1556 e0 = TREE_OPERAND (expr, 0);
1557 e1 = TREE_OPERAND (expr, 1);
1559 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
1560 e = simplify_replace_tree (cond, e0, e1);
1561 if (integer_zerop (e))
1562 return boolean_true_node;
1563 e = simplify_replace_tree (cond, e1, e0);
1564 if (integer_zerop (e))
1565 return boolean_true_node;
1568 te = expand_simple_operations (expr);
1570 /* Check whether COND ==> EXPR. */
1571 notcond = invert_truthvalue (cond);
1572 e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te);
1573 if (e && integer_nonzerop (e))
1576 /* Check whether COND ==> not EXPR. */
1577 e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te);
1578 if (e && integer_zerop (e))
1584 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1585 expression (or EXPR unchanged, if no simplification was possible).
1586 Wrapper around tree_simplify_using_condition_1 that ensures that chains
1587 of simple operations in definitions of ssa names in COND are expanded,
1588 so that things like casts or incrementing the value of the bound before
1589 the loop do not cause us to fail. */
1592 tree_simplify_using_condition (tree cond, tree expr)
1594 cond = expand_simple_operations (cond);
1596 return tree_simplify_using_condition_1 (cond, expr);
1599 /* Tries to simplify EXPR using the conditions on entry to LOOP.
1600 Returns the simplified expression (or EXPR unchanged, if no
1601 simplification was possible).*/
1604 simplify_using_initial_conditions (struct loop *loop, tree expr)
1612 if (TREE_CODE (expr) == INTEGER_CST)
1615 /* Limit walking the dominators to avoid quadraticness in
1616 the number of BBs times the number of loops in degenerate
1618 for (bb = loop->header;
1619 bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK;
1620 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1622 if (!single_pred_p (bb))
1624 e = single_pred_edge (bb);
1626 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
1629 stmt = last_stmt (e->src);
1630 cond = fold_build2 (gimple_cond_code (stmt),
1632 gimple_cond_lhs (stmt),
1633 gimple_cond_rhs (stmt));
1634 if (e->flags & EDGE_FALSE_VALUE)
1635 cond = invert_truthvalue (cond);
1636 expr = tree_simplify_using_condition (cond, expr);
1643 /* Tries to simplify EXPR using the evolutions of the loop invariants
1644 in the superloops of LOOP. Returns the simplified expression
1645 (or EXPR unchanged, if no simplification was possible). */
1648 simplify_using_outer_evolutions (struct loop *loop, tree expr)
1650 enum tree_code code = TREE_CODE (expr);
1654 if (is_gimple_min_invariant (expr))
1657 if (code == TRUTH_OR_EXPR
1658 || code == TRUTH_AND_EXPR
1659 || code == COND_EXPR)
1663 e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
1664 if (TREE_OPERAND (expr, 0) != e0)
1667 e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
1668 if (TREE_OPERAND (expr, 1) != e1)
1671 if (code == COND_EXPR)
1673 e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
1674 if (TREE_OPERAND (expr, 2) != e2)
1682 if (code == COND_EXPR)
1683 expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
1685 expr = fold_build2 (code, boolean_type_node, e0, e1);
1691 e = instantiate_parameters (loop, expr);
1692 if (is_gimple_min_invariant (e))
1698 /* Returns true if EXIT is the only possible exit from LOOP. */
1701 loop_only_exit_p (const struct loop *loop, const_edge exit)
1704 gimple_stmt_iterator bsi;
1708 if (exit != single_exit (loop))
1711 body = get_loop_body (loop);
1712 for (i = 0; i < loop->num_nodes; i++)
1714 for (bsi = gsi_start_bb (body[i]); !gsi_end_p (bsi); gsi_next (&bsi))
1716 call = gsi_stmt (bsi);
1717 if (gimple_code (call) != GIMPLE_CALL)
1720 if (gimple_has_side_effects (call))
1732 /* Stores description of number of iterations of LOOP derived from
1733 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
1734 useful information could be derived (and fields of NITER has
1735 meaning described in comments at struct tree_niter_desc
1736 declaration), false otherwise. If WARN is true and
1737 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1738 potentially unsafe assumptions. */
1741 number_of_iterations_exit (struct loop *loop, edge exit,
1742 struct tree_niter_desc *niter,
1748 enum tree_code code;
1751 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
1754 niter->assumptions = boolean_false_node;
1755 stmt = last_stmt (exit->src);
1756 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
1759 /* We want the condition for staying inside loop. */
1760 code = gimple_cond_code (stmt);
1761 if (exit->flags & EDGE_TRUE_VALUE)
1762 code = invert_tree_comparison (code, false);
1777 op0 = gimple_cond_lhs (stmt);
1778 op1 = gimple_cond_rhs (stmt);
1779 type = TREE_TYPE (op0);
1781 if (TREE_CODE (type) != INTEGER_TYPE
1782 && !POINTER_TYPE_P (type))
1785 if (!simple_iv (loop, stmt, op0, &iv0, false))
1787 if (!simple_iv (loop, stmt, op1, &iv1, false))
1790 /* We don't want to see undefined signed overflow warnings while
1791 computing the number of iterations. */
1792 fold_defer_overflow_warnings ();
1794 iv0.base = expand_simple_operations (iv0.base);
1795 iv1.base = expand_simple_operations (iv1.base);
1796 if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter,
1797 loop_only_exit_p (loop, exit)))
1799 fold_undefer_and_ignore_overflow_warnings ();
1805 niter->assumptions = simplify_using_outer_evolutions (loop,
1806 niter->assumptions);
1807 niter->may_be_zero = simplify_using_outer_evolutions (loop,
1808 niter->may_be_zero);
1809 niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
1813 = simplify_using_initial_conditions (loop,
1814 niter->assumptions);
1816 = simplify_using_initial_conditions (loop,
1817 niter->may_be_zero);
1819 fold_undefer_and_ignore_overflow_warnings ();
1821 if (integer_onep (niter->assumptions))
1824 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1825 But if we can prove that there is overflow or some other source of weird
1826 behavior, ignore the loop even with -funsafe-loop-optimizations. */
1827 if (integer_zerop (niter->assumptions))
1830 if (flag_unsafe_loop_optimizations)
1831 niter->assumptions = boolean_true_node;
1835 const char *wording;
1836 location_t loc = gimple_location (stmt);
1838 /* We can provide a more specific warning if one of the operator is
1839 constant and the other advances by +1 or -1. */
1840 if (!integer_zerop (iv1.step)
1841 ? (integer_zerop (iv0.step)
1842 && (integer_onep (iv1.step) || integer_all_onesp (iv1.step)))
1843 : (integer_onep (iv0.step) || integer_all_onesp (iv0.step)))
1845 flag_unsafe_loop_optimizations
1846 ? N_("assuming that the loop is not infinite")
1847 : N_("cannot optimize possibly infinite loops");
1850 flag_unsafe_loop_optimizations
1851 ? N_("assuming that the loop counter does not overflow")
1852 : N_("cannot optimize loop, the loop counter may overflow");
1854 if (LOCATION_LINE (loc) > 0)
1855 warning (OPT_Wunsafe_loop_optimizations, "%H%s", &loc, gettext (wording));
1857 warning (OPT_Wunsafe_loop_optimizations, "%s", gettext (wording));
1860 return flag_unsafe_loop_optimizations;
1863 /* Try to determine the number of iterations of LOOP. If we succeed,
1864 expression giving number of iterations is returned and *EXIT is
1865 set to the edge from that the information is obtained. Otherwise
1866 chrec_dont_know is returned. */
1869 find_loop_niter (struct loop *loop, edge *exit)
1872 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1874 tree niter = NULL_TREE, aniter;
1875 struct tree_niter_desc desc;
1878 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
1880 if (!just_once_each_iteration_p (loop, ex->src))
1883 if (!number_of_iterations_exit (loop, ex, &desc, false))
1886 if (integer_nonzerop (desc.may_be_zero))
1888 /* We exit in the first iteration through this exit.
1889 We won't find anything better. */
1890 niter = build_int_cst (unsigned_type_node, 0);
1895 if (!integer_zerop (desc.may_be_zero))
1898 aniter = desc.niter;
1902 /* Nothing recorded yet. */
1908 /* Prefer constants, the lower the better. */
1909 if (TREE_CODE (aniter) != INTEGER_CST)
1912 if (TREE_CODE (niter) != INTEGER_CST)
1919 if (tree_int_cst_lt (aniter, niter))
1926 VEC_free (edge, heap, exits);
1928 return niter ? niter : chrec_dont_know;
1933 Analysis of a number of iterations of a loop by a brute-force evaluation.
1937 /* Bound on the number of iterations we try to evaluate. */
1939 #define MAX_ITERATIONS_TO_TRACK \
1940 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
1942 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
1943 result by a chain of operations such that all but exactly one of their
1944 operands are constants. */
1947 chain_of_csts_start (struct loop *loop, tree x)
1949 gimple stmt = SSA_NAME_DEF_STMT (x);
1951 basic_block bb = gimple_bb (stmt);
1952 enum tree_code code;
1955 || !flow_bb_inside_loop_p (loop, bb))
1958 if (gimple_code (stmt) == GIMPLE_PHI)
1960 if (bb == loop->header)
1966 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1969 code = gimple_assign_rhs_code (stmt);
1970 if (gimple_references_memory_p (stmt)
1971 /* Before alias information is computed, operand scanning marks
1972 statements that write memory volatile. However, the statements
1973 that only read memory are not marked, thus gimple_references_memory_p
1974 returns false for them. */
1975 || TREE_CODE_CLASS (code) == tcc_reference
1976 || TREE_CODE_CLASS (code) == tcc_declaration
1977 || SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF) == NULL_DEF_OPERAND_P)
1980 use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1981 if (use == NULL_USE_OPERAND_P)
1984 return chain_of_csts_start (loop, use);
1987 /* Determines whether the expression X is derived from a result of a phi node
1988 in header of LOOP such that
1990 * the derivation of X consists only from operations with constants
1991 * the initial value of the phi node is constant
1992 * the value of the phi node in the next iteration can be derived from the
1993 value in the current iteration by a chain of operations with constants.
1995 If such phi node exists, it is returned, otherwise NULL is returned. */
1998 get_base_for (struct loop *loop, tree x)
2003 if (is_gimple_min_invariant (x))
2006 phi = chain_of_csts_start (loop, x);
2010 init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
2011 next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
2013 if (TREE_CODE (next) != SSA_NAME)
2016 if (!is_gimple_min_invariant (init))
2019 if (chain_of_csts_start (loop, next) != phi)
2025 /* Given an expression X, then
2027 * if X is NULL_TREE, we return the constant BASE.
2028 * otherwise X is a SSA name, whose value in the considered loop is derived
2029 by a chain of operations with constant from a result of a phi node in
2030 the header of the loop. Then we return value of X when the value of the
2031 result of this phi node is given by the constant BASE. */
2034 get_val_for (tree x, tree base)
2037 tree nx, val, retval, rhs1, rhs2;
2039 gcc_assert (is_gimple_min_invariant (base));
2044 stmt = SSA_NAME_DEF_STMT (x);
2045 if (gimple_code (stmt) == GIMPLE_PHI)
2048 gcc_assert (is_gimple_assign (stmt));
2050 /* STMT must be either an assignment of a single SSA name or an
2051 expression involving an SSA name and a constant. Try to fold that
2052 expression using the value for the SSA name. */
2053 rhs1 = gimple_assign_rhs1 (stmt);
2054 rhs2 = gimple_assign_rhs2 (stmt);
2055 if (TREE_CODE (rhs1) == SSA_NAME)
2057 else if (rhs2 && TREE_CODE (rhs2) == SSA_NAME)
2062 /* NX is now the SSA name for which we want to discover the base value. */
2063 val = get_val_for (nx, base);
2066 /* If this is a binary expression, fold it. If folding is
2067 not possible, return a tree expression with the RHS of STMT. */
2068 rhs1 = (nx == rhs1) ? val : rhs1;
2069 rhs2 = (nx == rhs2) ? val : rhs2;
2070 retval = fold_binary (gimple_assign_rhs_code (stmt),
2071 gimple_expr_type (stmt), rhs1, rhs2);
2072 if (retval == NULL_TREE)
2073 retval= build2 (gimple_assign_rhs_code (stmt),
2074 gimple_expr_type (stmt), rhs1, rhs2);
2083 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2084 by brute force -- i.e. by determining the value of the operands of the
2085 condition at EXIT in first few iterations of the loop (assuming that
2086 these values are constant) and determining the first one in that the
2087 condition is not satisfied. Returns the constant giving the number
2088 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
2091 loop_niter_by_eval (struct loop *loop, edge exit)
2094 tree op[2], val[2], next[2], aval[2];
2099 cond = last_stmt (exit->src);
2100 if (!cond || gimple_code (cond) != GIMPLE_COND)
2101 return chrec_dont_know;
2103 cmp = gimple_cond_code (cond);
2104 if (exit->flags & EDGE_TRUE_VALUE)
2105 cmp = invert_tree_comparison (cmp, false);
2115 op[0] = gimple_cond_lhs (cond);
2116 op[1] = gimple_cond_rhs (cond);
2120 return chrec_dont_know;
2123 for (j = 0; j < 2; j++)
2125 if (is_gimple_min_invariant (op[j]))
2128 next[j] = NULL_TREE;
2133 phi = get_base_for (loop, op[j]);
2135 return chrec_dont_know;
2136 val[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
2137 next[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
2141 /* Don't issue signed overflow warnings. */
2142 fold_defer_overflow_warnings ();
2144 for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
2146 for (j = 0; j < 2; j++)
2147 aval[j] = get_val_for (op[j], val[j]);
2149 acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]);
2150 if (acnd && integer_zerop (acnd))
2152 fold_undefer_and_ignore_overflow_warnings ();
2153 if (dump_file && (dump_flags & TDF_DETAILS))
2155 "Proved that loop %d iterates %d times using brute force.\n",
2157 return build_int_cst (unsigned_type_node, i);
2160 for (j = 0; j < 2; j++)
2162 val[j] = get_val_for (next[j], val[j]);
2163 if (!is_gimple_min_invariant (val[j]))
2165 fold_undefer_and_ignore_overflow_warnings ();
2166 return chrec_dont_know;
2171 fold_undefer_and_ignore_overflow_warnings ();
2173 return chrec_dont_know;
2176 /* Finds the exit of the LOOP by that the loop exits after a constant
2177 number of iterations and stores the exit edge to *EXIT. The constant
2178 giving the number of iterations of LOOP is returned. The number of
2179 iterations is determined using loop_niter_by_eval (i.e. by brute force
2180 evaluation). If we are unable to find the exit for that loop_niter_by_eval
2181 determines the number of iterations, chrec_dont_know is returned. */
2184 find_loop_niter_by_eval (struct loop *loop, edge *exit)
2187 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
2189 tree niter = NULL_TREE, aniter;
2192 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
2194 if (!just_once_each_iteration_p (loop, ex->src))
2197 aniter = loop_niter_by_eval (loop, ex);
2198 if (chrec_contains_undetermined (aniter))
2202 && !tree_int_cst_lt (aniter, niter))
2208 VEC_free (edge, heap, exits);
2210 return niter ? niter : chrec_dont_know;
2215 Analysis of upper bounds on number of iterations of a loop.
2219 static double_int derive_constant_upper_bound_ops (tree, tree,
2220 enum tree_code, tree);
2222 /* Returns a constant upper bound on the value of the right-hand side of
2223 an assignment statement STMT. */
2226 derive_constant_upper_bound_assign (gimple stmt)
2228 enum tree_code code = gimple_assign_rhs_code (stmt);
2229 tree op0 = gimple_assign_rhs1 (stmt);
2230 tree op1 = gimple_assign_rhs2 (stmt);
2232 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt)),
2236 /* Returns a constant upper bound on the value of expression VAL. VAL
2237 is considered to be unsigned. If its type is signed, its value must
2241 derive_constant_upper_bound (tree val)
2243 enum tree_code code;
2246 extract_ops_from_tree (val, &code, &op0, &op1);
2247 return derive_constant_upper_bound_ops (TREE_TYPE (val), op0, code, op1);
2250 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
2251 whose type is TYPE. The expression is considered to be unsigned. If
2252 its type is signed, its value must be nonnegative. */
2255 derive_constant_upper_bound_ops (tree type, tree op0,
2256 enum tree_code code, tree op1)
2259 double_int bnd, max, mmax, cst;
2262 if (INTEGRAL_TYPE_P (type))
2263 maxt = TYPE_MAX_VALUE (type);
2265 maxt = upper_bound_in_type (type, type);
2267 max = tree_to_double_int (maxt);
2272 return tree_to_double_int (op0);
2275 subtype = TREE_TYPE (op0);
2276 if (!TYPE_UNSIGNED (subtype)
2277 /* If TYPE is also signed, the fact that VAL is nonnegative implies
2278 that OP0 is nonnegative. */
2279 && TYPE_UNSIGNED (type)
2280 && !tree_expr_nonnegative_p (op0))
2282 /* If we cannot prove that the casted expression is nonnegative,
2283 we cannot establish more useful upper bound than the precision
2284 of the type gives us. */
2288 /* We now know that op0 is an nonnegative value. Try deriving an upper
2290 bnd = derive_constant_upper_bound (op0);
2292 /* If the bound does not fit in TYPE, max. value of TYPE could be
2294 if (double_int_ucmp (max, bnd) < 0)
2300 case POINTER_PLUS_EXPR:
2302 if (TREE_CODE (op1) != INTEGER_CST
2303 || !tree_expr_nonnegative_p (op0))
2306 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
2307 choose the most logical way how to treat this constant regardless
2308 of the signedness of the type. */
2309 cst = tree_to_double_int (op1);
2310 cst = double_int_sext (cst, TYPE_PRECISION (type));
2311 if (code != MINUS_EXPR)
2312 cst = double_int_neg (cst);
2314 bnd = derive_constant_upper_bound (op0);
2316 if (double_int_negative_p (cst))
2318 cst = double_int_neg (cst);
2319 /* Avoid CST == 0x80000... */
2320 if (double_int_negative_p (cst))
2323 /* OP0 + CST. We need to check that
2324 BND <= MAX (type) - CST. */
2326 mmax = double_int_add (max, double_int_neg (cst));
2327 if (double_int_ucmp (bnd, mmax) > 0)
2330 return double_int_add (bnd, cst);
2334 /* OP0 - CST, where CST >= 0.
2336 If TYPE is signed, we have already verified that OP0 >= 0, and we
2337 know that the result is nonnegative. This implies that
2340 If TYPE is unsigned, we must additionally know that OP0 >= CST,
2341 otherwise the operation underflows.
2344 /* This should only happen if the type is unsigned; however, for
2345 buggy programs that use overflowing signed arithmetics even with
2346 -fno-wrapv, this condition may also be true for signed values. */
2347 if (double_int_ucmp (bnd, cst) < 0)
2350 if (TYPE_UNSIGNED (type))
2352 tree tem = fold_binary (GE_EXPR, boolean_type_node, op0,
2353 double_int_to_tree (type, cst));
2354 if (!tem || integer_nonzerop (tem))
2358 bnd = double_int_add (bnd, double_int_neg (cst));
2363 case FLOOR_DIV_EXPR:
2364 case EXACT_DIV_EXPR:
2365 if (TREE_CODE (op1) != INTEGER_CST
2366 || tree_int_cst_sign_bit (op1))
2369 bnd = derive_constant_upper_bound (op0);
2370 return double_int_udiv (bnd, tree_to_double_int (op1), FLOOR_DIV_EXPR);
2373 if (TREE_CODE (op1) != INTEGER_CST
2374 || tree_int_cst_sign_bit (op1))
2376 return tree_to_double_int (op1);
2379 stmt = SSA_NAME_DEF_STMT (op0);
2380 if (gimple_code (stmt) != GIMPLE_ASSIGN
2381 || gimple_assign_lhs (stmt) != op0)
2383 return derive_constant_upper_bound_assign (stmt);
2390 /* Records that every statement in LOOP is executed I_BOUND times.
2391 REALISTIC is true if I_BOUND is expected to be close to the real number
2392 of iterations. UPPER is true if we are sure the loop iterates at most
2396 record_niter_bound (struct loop *loop, double_int i_bound, bool realistic,
2399 /* Update the bounds only when there is no previous estimation, or when the current
2400 estimation is smaller. */
2402 && (!loop->any_upper_bound
2403 || double_int_ucmp (i_bound, loop->nb_iterations_upper_bound) < 0))
2405 loop->any_upper_bound = true;
2406 loop->nb_iterations_upper_bound = i_bound;
2409 && (!loop->any_estimate
2410 || double_int_ucmp (i_bound, loop->nb_iterations_estimate) < 0))
2412 loop->any_estimate = true;
2413 loop->nb_iterations_estimate = i_bound;
2417 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
2418 is true if the loop is exited immediately after STMT, and this exit
2419 is taken at last when the STMT is executed BOUND + 1 times.
2420 REALISTIC is true if BOUND is expected to be close to the real number
2421 of iterations. UPPER is true if we are sure the loop iterates at most
2422 BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */
2425 record_estimate (struct loop *loop, tree bound, double_int i_bound,
2426 gimple at_stmt, bool is_exit, bool realistic, bool upper)
2431 if (dump_file && (dump_flags & TDF_DETAILS))
2433 fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : "");
2434 print_gimple_stmt (dump_file, at_stmt, 0, TDF_SLIM);
2435 fprintf (dump_file, " is %sexecuted at most ",
2436 upper ? "" : "probably ");
2437 print_generic_expr (dump_file, bound, TDF_SLIM);
2438 fprintf (dump_file, " (bounded by ");
2439 dump_double_int (dump_file, i_bound, true);
2440 fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num);
2443 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
2444 real number of iterations. */
2445 if (TREE_CODE (bound) != INTEGER_CST)
2447 if (!upper && !realistic)
2450 /* If we have a guaranteed upper bound, record it in the appropriate
2454 struct nb_iter_bound *elt = GGC_NEW (struct nb_iter_bound);
2456 elt->bound = i_bound;
2457 elt->stmt = at_stmt;
2458 elt->is_exit = is_exit;
2459 elt->next = loop->bounds;
2463 /* Update the number of iteration estimates according to the bound.
2464 If at_stmt is an exit, then every statement in the loop is
2465 executed at most BOUND + 1 times. If it is not an exit, then
2466 some of the statements before it could be executed BOUND + 2
2467 times, if an exit of LOOP is before stmt. */
2468 exit = single_exit (loop);
2471 && dominated_by_p (CDI_DOMINATORS,
2472 exit->src, gimple_bb (at_stmt))))
2473 delta = double_int_one;
2475 delta = double_int_two;
2476 i_bound = double_int_add (i_bound, delta);
2478 /* If an overflow occurred, ignore the result. */
2479 if (double_int_ucmp (i_bound, delta) < 0)
2482 record_niter_bound (loop, i_bound, realistic, upper);
2485 /* Record the estimate on number of iterations of LOOP based on the fact that
2486 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
2487 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
2488 estimated number of iterations is expected to be close to the real one.
2489 UPPER is true if we are sure the induction variable does not wrap. */
2492 record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple stmt,
2493 tree low, tree high, bool realistic, bool upper)
2495 tree niter_bound, extreme, delta;
2496 tree type = TREE_TYPE (base), unsigned_type;
2499 if (TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
2502 if (dump_file && (dump_flags & TDF_DETAILS))
2504 fprintf (dump_file, "Induction variable (");
2505 print_generic_expr (dump_file, TREE_TYPE (base), TDF_SLIM);
2506 fprintf (dump_file, ") ");
2507 print_generic_expr (dump_file, base, TDF_SLIM);
2508 fprintf (dump_file, " + ");
2509 print_generic_expr (dump_file, step, TDF_SLIM);
2510 fprintf (dump_file, " * iteration does not wrap in statement ");
2511 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2512 fprintf (dump_file, " in loop %d.\n", loop->num);
2515 unsigned_type = unsigned_type_for (type);
2516 base = fold_convert (unsigned_type, base);
2517 step = fold_convert (unsigned_type, step);
2519 if (tree_int_cst_sign_bit (step))
2521 extreme = fold_convert (unsigned_type, low);
2522 if (TREE_CODE (base) != INTEGER_CST)
2523 base = fold_convert (unsigned_type, high);
2524 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
2525 step = fold_build1 (NEGATE_EXPR, unsigned_type, step);
2529 extreme = fold_convert (unsigned_type, high);
2530 if (TREE_CODE (base) != INTEGER_CST)
2531 base = fold_convert (unsigned_type, low);
2532 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
2535 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
2536 would get out of the range. */
2537 niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step);
2538 max = derive_constant_upper_bound (niter_bound);
2539 record_estimate (loop, niter_bound, max, stmt, false, realistic, upper);
2542 /* Returns true if REF is a reference to an array at the end of a dynamically
2543 allocated structure. If this is the case, the array may be allocated larger
2544 than its upper bound implies. */
2547 array_at_struct_end_p (tree ref)
2549 tree base = get_base_address (ref);
2552 /* Unless the reference is through a pointer, the size of the array matches
2554 if (!base || !INDIRECT_REF_P (base))
2557 for (;handled_component_p (ref); ref = parent)
2559 parent = TREE_OPERAND (ref, 0);
2561 if (TREE_CODE (ref) == COMPONENT_REF)
2563 /* All fields of a union are at its end. */
2564 if (TREE_CODE (TREE_TYPE (parent)) == UNION_TYPE)
2567 /* Unless the field is at the end of the struct, we are done. */
2568 field = TREE_OPERAND (ref, 1);
2569 if (TREE_CHAIN (field))
2573 /* The other options are ARRAY_REF, ARRAY_RANGE_REF, VIEW_CONVERT_EXPR.
2574 In all these cases, we might be accessing the last element, and
2575 although in practice this will probably never happen, it is legal for
2576 the indices of this last element to exceed the bounds of the array.
2577 Therefore, continue checking. */
2580 gcc_assert (INDIRECT_REF_P (ref));
2584 /* Determine information about number of iterations a LOOP from the index
2585 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
2586 guaranteed to be executed in every iteration of LOOP. Callback for
2597 idx_infer_loop_bounds (tree base, tree *idx, void *dta)
2599 struct ilb_data *data = (struct ilb_data *) dta;
2600 tree ev, init, step;
2601 tree low, high, type, next;
2602 bool sign, upper = data->reliable, at_end = false;
2603 struct loop *loop = data->loop;
2605 if (TREE_CODE (base) != ARRAY_REF)
2608 /* For arrays at the end of the structure, we are not guaranteed that they
2609 do not really extend over their declared size. However, for arrays of
2610 size greater than one, this is unlikely to be intended. */
2611 if (array_at_struct_end_p (base))
2617 ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx));
2618 init = initial_condition (ev);
2619 step = evolution_part_in_loop_num (ev, loop->num);
2623 || TREE_CODE (step) != INTEGER_CST
2624 || integer_zerop (step)
2625 || tree_contains_chrecs (init, NULL)
2626 || chrec_contains_symbols_defined_in_loop (init, loop->num))
2629 low = array_ref_low_bound (base);
2630 high = array_ref_up_bound (base);
2632 /* The case of nonconstant bounds could be handled, but it would be
2634 if (TREE_CODE (low) != INTEGER_CST
2636 || TREE_CODE (high) != INTEGER_CST)
2638 sign = tree_int_cst_sign_bit (step);
2639 type = TREE_TYPE (step);
2641 /* The array of length 1 at the end of a structure most likely extends
2642 beyond its bounds. */
2644 && operand_equal_p (low, high, 0))
2647 /* In case the relevant bound of the array does not fit in type, or
2648 it does, but bound + step (in type) still belongs into the range of the
2649 array, the index may wrap and still stay within the range of the array
2650 (consider e.g. if the array is indexed by the full range of
2653 To make things simpler, we require both bounds to fit into type, although
2654 there are cases where this would not be strictly necessary. */
2655 if (!int_fits_type_p (high, type)
2656 || !int_fits_type_p (low, type))
2658 low = fold_convert (type, low);
2659 high = fold_convert (type, high);
2662 next = fold_binary (PLUS_EXPR, type, low, step);
2664 next = fold_binary (PLUS_EXPR, type, high, step);
2666 if (tree_int_cst_compare (low, next) <= 0
2667 && tree_int_cst_compare (next, high) <= 0)
2670 record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true, upper);
2674 /* Determine information about number of iterations a LOOP from the bounds
2675 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
2676 STMT is guaranteed to be executed in every iteration of LOOP.*/
2679 infer_loop_bounds_from_ref (struct loop *loop, gimple stmt, tree ref,
2682 struct ilb_data data;
2686 data.reliable = reliable;
2687 for_each_index (&ref, idx_infer_loop_bounds, &data);
2690 /* Determine information about number of iterations of a LOOP from the way
2691 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
2692 executed in every iteration of LOOP. */
2695 infer_loop_bounds_from_array (struct loop *loop, gimple stmt, bool reliable)
2697 if (is_gimple_assign (stmt))
2699 tree op0 = gimple_assign_lhs (stmt);
2700 tree op1 = gimple_assign_rhs1 (stmt);
2702 /* For each memory access, analyze its access function
2703 and record a bound on the loop iteration domain. */
2704 if (REFERENCE_CLASS_P (op0))
2705 infer_loop_bounds_from_ref (loop, stmt, op0, reliable);
2707 if (REFERENCE_CLASS_P (op1))
2708 infer_loop_bounds_from_ref (loop, stmt, op1, reliable);
2710 else if (is_gimple_call (stmt))
2713 unsigned i, n = gimple_call_num_args (stmt);
2715 lhs = gimple_call_lhs (stmt);
2716 if (lhs && REFERENCE_CLASS_P (lhs))
2717 infer_loop_bounds_from_ref (loop, stmt, lhs, reliable);
2719 for (i = 0; i < n; i++)
2721 arg = gimple_call_arg (stmt, i);
2722 if (REFERENCE_CLASS_P (arg))
2723 infer_loop_bounds_from_ref (loop, stmt, arg, reliable);
2728 /* Determine information about number of iterations of a LOOP from the fact
2729 that signed arithmetics in STMT does not overflow. */
2732 infer_loop_bounds_from_signedness (struct loop *loop, gimple stmt)
2734 tree def, base, step, scev, type, low, high;
2736 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2739 def = gimple_assign_lhs (stmt);
2741 if (TREE_CODE (def) != SSA_NAME)
2744 type = TREE_TYPE (def);
2745 if (!INTEGRAL_TYPE_P (type)
2746 || !TYPE_OVERFLOW_UNDEFINED (type))
2749 scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
2750 if (chrec_contains_undetermined (scev))
2753 base = initial_condition_in_loop_num (scev, loop->num);
2754 step = evolution_part_in_loop_num (scev, loop->num);
2757 || TREE_CODE (step) != INTEGER_CST
2758 || tree_contains_chrecs (base, NULL)
2759 || chrec_contains_symbols_defined_in_loop (base, loop->num))
2762 low = lower_bound_in_type (type, type);
2763 high = upper_bound_in_type (type, type);
2765 record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
2768 /* The following analyzers are extracting informations on the bounds
2769 of LOOP from the following undefined behaviors:
2771 - data references should not access elements over the statically
2774 - signed variables should not overflow when flag_wrapv is not set.
2778 infer_loop_bounds_from_undefined (struct loop *loop)
2782 gimple_stmt_iterator bsi;
2786 bbs = get_loop_body (loop);
2788 for (i = 0; i < loop->num_nodes; i++)
2792 /* If BB is not executed in each iteration of the loop, we cannot
2793 use the operations in it to infer reliable upper bound on the
2794 # of iterations of the loop. However, we can use it as a guess. */
2795 reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb);
2797 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
2799 gimple stmt = gsi_stmt (bsi);
2801 infer_loop_bounds_from_array (loop, stmt, reliable);
2804 infer_loop_bounds_from_signedness (loop, stmt);
2812 /* Converts VAL to double_int. */
2815 gcov_type_to_double_int (gcov_type val)
2819 ret.low = (unsigned HOST_WIDE_INT) val;
2820 /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by
2821 the size of type. */
2822 val >>= HOST_BITS_PER_WIDE_INT - 1;
2824 ret.high = (unsigned HOST_WIDE_INT) val;
2829 /* Records estimates on numbers of iterations of LOOP. */
2832 estimate_numbers_of_iterations_loop (struct loop *loop)
2834 VEC (edge, heap) *exits;
2837 struct tree_niter_desc niter_desc;
2841 /* Give up if we already have tried to compute an estimation. */
2842 if (loop->estimate_state != EST_NOT_COMPUTED)
2844 loop->estimate_state = EST_AVAILABLE;
2845 loop->any_upper_bound = false;
2846 loop->any_estimate = false;
2848 exits = get_loop_exit_edges (loop);
2849 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
2851 if (!number_of_iterations_exit (loop, ex, &niter_desc, false))
2854 niter = niter_desc.niter;
2855 type = TREE_TYPE (niter);
2856 if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST)
2857 niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
2858 build_int_cst (type, 0),
2860 record_estimate (loop, niter, niter_desc.max,
2861 last_stmt (ex->src),
2864 VEC_free (edge, heap, exits);
2866 infer_loop_bounds_from_undefined (loop);
2868 /* If we have a measured profile, use it to estimate the number of
2870 if (loop->header->count != 0)
2872 gcov_type nit = expected_loop_iterations_unbounded (loop) + 1;
2873 bound = gcov_type_to_double_int (nit);
2874 record_niter_bound (loop, bound, true, false);
2877 /* If an upper bound is smaller than the realistic estimate of the
2878 number of iterations, use the upper bound instead. */
2879 if (loop->any_upper_bound
2880 && loop->any_estimate
2881 && double_int_ucmp (loop->nb_iterations_upper_bound,
2882 loop->nb_iterations_estimate) < 0)
2883 loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
2886 /* Records estimates on numbers of iterations of loops. */
2889 estimate_numbers_of_iterations (void)
2894 /* We don't want to issue signed overflow warnings while getting
2895 loop iteration estimates. */
2896 fold_defer_overflow_warnings ();
2898 FOR_EACH_LOOP (li, loop, 0)
2900 estimate_numbers_of_iterations_loop (loop);
2903 fold_undefer_and_ignore_overflow_warnings ();
2906 /* Returns true if statement S1 dominates statement S2. */
2909 stmt_dominates_stmt_p (gimple s1, gimple s2)
2911 basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
2919 gimple_stmt_iterator bsi;
2921 for (bsi = gsi_start_bb (bb1); gsi_stmt (bsi) != s2; gsi_next (&bsi))
2922 if (gsi_stmt (bsi) == s1)
2928 return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
2931 /* Returns true when we can prove that the number of executions of
2932 STMT in the loop is at most NITER, according to the bound on
2933 the number of executions of the statement NITER_BOUND->stmt recorded in
2934 NITER_BOUND. If STMT is NULL, we must prove this bound for all
2935 statements in the loop. */
2938 n_of_executions_at_most (gimple stmt,
2939 struct nb_iter_bound *niter_bound,
2942 double_int bound = niter_bound->bound;
2943 tree nit_type = TREE_TYPE (niter), e;
2946 gcc_assert (TYPE_UNSIGNED (nit_type));
2948 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
2949 the number of iterations is small. */
2950 if (!double_int_fits_to_tree_p (nit_type, bound))
2953 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
2954 times. This means that:
2956 -- if NITER_BOUND->is_exit is true, then everything before
2957 NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
2958 times, and everything after it at most NITER_BOUND->bound times.
2960 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
2961 is executed, then NITER_BOUND->stmt is executed as well in the same
2962 iteration (we conclude that if both statements belong to the same
2963 basic block, or if STMT is after NITER_BOUND->stmt), then STMT
2964 is executed at most NITER_BOUND->bound + 1 times. Otherwise STMT is
2965 executed at most NITER_BOUND->bound + 2 times. */
2967 if (niter_bound->is_exit)
2970 && stmt != niter_bound->stmt
2971 && stmt_dominates_stmt_p (niter_bound->stmt, stmt))
2979 || (gimple_bb (stmt) != gimple_bb (niter_bound->stmt)
2980 && !stmt_dominates_stmt_p (niter_bound->stmt, stmt)))
2982 bound = double_int_add (bound, double_int_one);
2983 if (double_int_zero_p (bound)
2984 || !double_int_fits_to_tree_p (nit_type, bound))
2990 e = fold_binary (cmp, boolean_type_node,
2991 niter, double_int_to_tree (nit_type, bound));
2992 return e && integer_nonzerop (e);
2995 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
2998 nowrap_type_p (tree type)
3000 if (INTEGRAL_TYPE_P (type)
3001 && TYPE_OVERFLOW_UNDEFINED (type))
3004 if (POINTER_TYPE_P (type))
3010 /* Return false only when the induction variable BASE + STEP * I is
3011 known to not overflow: i.e. when the number of iterations is small
3012 enough with respect to the step and initial condition in order to
3013 keep the evolution confined in TYPEs bounds. Return true when the
3014 iv is known to overflow or when the property is not computable.
3016 USE_OVERFLOW_SEMANTICS is true if this function should assume that
3017 the rules for overflow of the given language apply (e.g., that signed
3018 arithmetics in C does not overflow). */
3021 scev_probably_wraps_p (tree base, tree step,
3022 gimple at_stmt, struct loop *loop,
3023 bool use_overflow_semantics)
3025 struct nb_iter_bound *bound;
3026 tree delta, step_abs;
3027 tree unsigned_type, valid_niter;
3028 tree type = TREE_TYPE (step);
3030 /* FIXME: We really need something like
3031 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
3033 We used to test for the following situation that frequently appears
3034 during address arithmetics:
3036 D.1621_13 = (long unsigned intD.4) D.1620_12;
3037 D.1622_14 = D.1621_13 * 8;
3038 D.1623_15 = (doubleD.29 *) D.1622_14;
3040 And derived that the sequence corresponding to D_14
3041 can be proved to not wrap because it is used for computing a
3042 memory access; however, this is not really the case -- for example,
3043 if D_12 = (unsigned char) [254,+,1], then D_14 has values
3044 2032, 2040, 0, 8, ..., but the code is still legal. */
3046 if (chrec_contains_undetermined (base)
3047 || chrec_contains_undetermined (step))
3050 if (integer_zerop (step))
3053 /* If we can use the fact that signed and pointer arithmetics does not
3054 wrap, we are done. */
3055 if (use_overflow_semantics && nowrap_type_p (type))
3058 /* To be able to use estimates on number of iterations of the loop,
3059 we must have an upper bound on the absolute value of the step. */
3060 if (TREE_CODE (step) != INTEGER_CST)
3063 /* Don't issue signed overflow warnings. */
3064 fold_defer_overflow_warnings ();
3066 /* Otherwise, compute the number of iterations before we reach the
3067 bound of the type, and verify that the loop is exited before this
3069 unsigned_type = unsigned_type_for (type);
3070 base = fold_convert (unsigned_type, base);
3072 if (tree_int_cst_sign_bit (step))
3074 tree extreme = fold_convert (unsigned_type,
3075 lower_bound_in_type (type, type));
3076 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
3077 step_abs = fold_build1 (NEGATE_EXPR, unsigned_type,
3078 fold_convert (unsigned_type, step));
3082 tree extreme = fold_convert (unsigned_type,
3083 upper_bound_in_type (type, type));
3084 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
3085 step_abs = fold_convert (unsigned_type, step);
3088 valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
3090 estimate_numbers_of_iterations_loop (loop);
3091 for (bound = loop->bounds; bound; bound = bound->next)
3093 if (n_of_executions_at_most (at_stmt, bound, valid_niter))
3095 fold_undefer_and_ignore_overflow_warnings ();
3100 fold_undefer_and_ignore_overflow_warnings ();
3102 /* At this point we still don't have a proof that the iv does not
3103 overflow: give up. */
3107 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
3110 free_numbers_of_iterations_estimates_loop (struct loop *loop)
3112 struct nb_iter_bound *bound, *next;
3114 loop->nb_iterations = NULL;
3115 loop->estimate_state = EST_NOT_COMPUTED;
3116 for (bound = loop->bounds; bound; bound = next)
3122 loop->bounds = NULL;
3125 /* Frees the information on upper bounds on numbers of iterations of loops. */
3128 free_numbers_of_iterations_estimates (void)
3133 FOR_EACH_LOOP (li, loop, 0)
3135 free_numbers_of_iterations_estimates_loop (loop);
3139 /* Substitute value VAL for ssa name NAME inside expressions held
3143 substitute_in_loop_info (struct loop *loop, tree name, tree val)
3145 loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);