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. */
67 /* Sets RESULT to VAL, taken unsigned if UNS is true and as signed
71 mpz_set_double_int (mpz_t result, double_int val, bool uns)
74 unsigned HOST_WIDE_INT vp[2];
76 if (!uns && double_int_negative_p (val))
79 val = double_int_neg (val);
83 vp[1] = (unsigned HOST_WIDE_INT) val.high;
84 mpz_import (result, 2, -1, sizeof (HOST_WIDE_INT), 0, 0, vp);
87 mpz_neg (result, result);
90 /* Stores bounds of TYPE to MIN and MAX. */
93 get_type_bounds (tree type, mpz_t min, mpz_t max)
95 if (TYPE_UNSIGNED (type))
98 mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true);
104 mx = double_int_mask (TYPE_PRECISION (type) - 1);
105 mn = double_int_sext (double_int_add (mx, double_int_one),
106 TYPE_PRECISION (type));
107 mpz_set_double_int (max, mx, true);
108 mpz_set_double_int (min, mn, false);
112 /* Returns VAL converted to TYPE. If VAL does not fit in TYPE,
113 the minimum or maximum value of the type is returned instead. */
116 mpz_to_double_int (tree type, mpz_t val)
119 unsigned HOST_WIDE_INT vp[2];
126 get_type_bounds (type, min, max);
128 if (mpz_cmp (val, min) < 0)
130 else if (mpz_cmp (val, max) > 0)
133 if (mpz_sgn (val) < 0)
138 mpz_export (vp, &count, -1, sizeof (HOST_WIDE_INT), 0, 0, val);
139 gcc_assert (count <= 2);
145 res.high = (HOST_WIDE_INT) vp[1];
147 res = double_int_ext (res, TYPE_PRECISION (type), TYPE_UNSIGNED (type));
149 res = double_int_neg (res);
154 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */
157 split_to_var_and_offset (tree expr, tree *var, mpz_t offset)
159 tree type = TREE_TYPE (expr);
165 mpz_set_ui (offset, 0);
167 switch (TREE_CODE (expr))
174 op0 = TREE_OPERAND (expr, 0);
175 op1 = TREE_OPERAND (expr, 1);
177 if (TREE_CODE (op1) != INTEGER_CST)
181 /* Always sign extend the offset. */
182 off = double_int_sext (tree_to_double_int (op1),
183 TYPE_PRECISION (type));
184 mpz_set_double_int (offset, off, false);
188 *var = build_int_cst_type (type, 0);
189 off = tree_to_double_int (expr);
190 mpz_set_double_int (offset, off, TYPE_UNSIGNED (type));
198 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
199 in TYPE to MIN and MAX. */
202 determine_value_range (tree type, tree var, mpz_t off,
203 mpz_t min, mpz_t max)
205 /* If the expression is a constant, we know its value exactly. */
206 if (integer_zerop (var))
213 /* If the computation may wrap, we know nothing about the value, except for
214 the range of the type. */
215 get_type_bounds (type, min, max);
216 if (!nowrap_type_p (type))
219 /* Since the addition of OFF does not wrap, if OFF is positive, then we may
220 add it to MIN, otherwise to MAX. */
221 if (mpz_sgn (off) < 0)
222 mpz_add (max, max, off);
224 mpz_add (min, min, off);
227 /* Stores the bounds on the difference of the values of the expressions
228 (var + X) and (var + Y), computed in TYPE, to BNDS. */
231 bound_difference_of_offsetted_base (tree type, mpz_t x, mpz_t y,
234 int rel = mpz_cmp (x, y);
235 bool may_wrap = !nowrap_type_p (type);
238 /* If X == Y, then the expressions are always equal.
239 If X > Y, there are the following possibilities:
240 a) neither of var + X and var + Y overflow or underflow, or both of
241 them do. Then their difference is X - Y.
242 b) var + X overflows, and var + Y does not. Then the values of the
243 expressions are var + X - M and var + Y, where M is the range of
244 the type, and their difference is X - Y - M.
245 c) var + Y underflows and var + X does not. Their difference again
247 Therefore, if the arithmetics in type does not overflow, then the
248 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
249 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
250 (X - Y, X - Y + M). */
254 mpz_set_ui (bnds->below, 0);
255 mpz_set_ui (bnds->up, 0);
260 mpz_set_double_int (m, double_int_mask (TYPE_PRECISION (type)), true);
261 mpz_add_ui (m, m, 1);
262 mpz_sub (bnds->up, x, y);
263 mpz_set (bnds->below, bnds->up);
268 mpz_sub (bnds->below, bnds->below, m);
270 mpz_add (bnds->up, bnds->up, m);
276 /* From condition C0 CMP C1 derives information regarding the
277 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
278 and stores it to BNDS. */
281 refine_bounds_using_guard (tree type, tree varx, mpz_t offx,
282 tree vary, mpz_t offy,
283 tree c0, enum tree_code cmp, tree c1,
286 tree varc0, varc1, tmp, ctype;
287 mpz_t offc0, offc1, loffx, loffy, bnd;
289 bool no_wrap = nowrap_type_p (type);
298 STRIP_SIGN_NOPS (c0);
299 STRIP_SIGN_NOPS (c1);
300 ctype = TREE_TYPE (c0);
301 if (!tree_ssa_useless_type_conversion_1 (ctype, type))
307 /* We could derive quite precise information from EQ_EXPR, however, such
308 a guard is unlikely to appear, so we do not bother with handling
313 /* NE_EXPR comparisons do not contain much of useful information, except for
314 special case of comparing with the bounds of the type. */
315 if (TREE_CODE (c1) != INTEGER_CST
316 || !INTEGRAL_TYPE_P (type))
319 /* Ensure that the condition speaks about an expression in the same type
321 ctype = TREE_TYPE (c0);
322 if (TYPE_PRECISION (ctype) != TYPE_PRECISION (type))
324 c0 = fold_convert (type, c0);
325 c1 = fold_convert (type, c1);
327 if (TYPE_MIN_VALUE (type)
328 && operand_equal_p (c1, TYPE_MIN_VALUE (type), 0))
333 if (TYPE_MAX_VALUE (type)
334 && operand_equal_p (c1, TYPE_MAX_VALUE (type), 0))
347 split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0);
348 split_to_var_and_offset (expand_simple_operations (c1), &varc1, offc1);
350 /* We are only interested in comparisons of expressions based on VARX and
351 VARY. TODO -- we might also be able to derive some bounds from
352 expressions containing just one of the variables. */
354 if (operand_equal_p (varx, varc1, 0))
356 tmp = varc0; varc0 = varc1; varc1 = tmp;
357 mpz_swap (offc0, offc1);
358 cmp = swap_tree_comparison (cmp);
361 if (!operand_equal_p (varx, varc0, 0)
362 || !operand_equal_p (vary, varc1, 0))
365 mpz_init_set (loffx, offx);
366 mpz_init_set (loffy, offy);
368 if (cmp == GT_EXPR || cmp == GE_EXPR)
370 tmp = varx; varx = vary; vary = tmp;
371 mpz_swap (offc0, offc1);
372 mpz_swap (loffx, loffy);
373 cmp = swap_tree_comparison (cmp);
377 /* If there is no overflow, the condition implies that
379 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
381 The overflows and underflows may complicate things a bit; each
382 overflow decreases the appropriate offset by M, and underflow
383 increases it by M. The above inequality would not necessarily be
386 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
387 VARX + OFFC0 overflows, but VARX + OFFX does not.
388 This may only happen if OFFX < OFFC0.
389 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
390 VARY + OFFC1 underflows and VARY + OFFY does not.
391 This may only happen if OFFY > OFFC1. */
400 x_ok = (integer_zerop (varx)
401 || mpz_cmp (loffx, offc0) >= 0);
402 y_ok = (integer_zerop (vary)
403 || mpz_cmp (loffy, offc1) <= 0);
409 mpz_sub (bnd, loffx, loffy);
410 mpz_add (bnd, bnd, offc1);
411 mpz_sub (bnd, bnd, offc0);
414 mpz_sub_ui (bnd, bnd, 1);
419 if (mpz_cmp (bnds->below, bnd) < 0)
420 mpz_set (bnds->below, bnd);
424 if (mpz_cmp (bnd, bnds->up) < 0)
425 mpz_set (bnds->up, bnd);
437 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
438 The subtraction is considered to be performed in arbitrary precision,
441 We do not attempt to be too clever regarding the value ranges of X and
442 Y; most of the time, they are just integers or ssa names offsetted by
443 integer. However, we try to use the information contained in the
444 comparisons before the loop (usually created by loop header copying). */
447 bound_difference (struct loop *loop, tree x, tree y, bounds *bnds)
449 tree type = TREE_TYPE (x);
452 mpz_t minx, maxx, miny, maxy;
459 /* Get rid of unnecessary casts, but preserve the value of
464 mpz_init (bnds->below);
468 split_to_var_and_offset (x, &varx, offx);
469 split_to_var_and_offset (y, &vary, offy);
471 if (!integer_zerop (varx)
472 && operand_equal_p (varx, vary, 0))
474 /* Special case VARX == VARY -- we just need to compare the
475 offsets. The matters are a bit more complicated in the
476 case addition of offsets may wrap. */
477 bound_difference_of_offsetted_base (type, offx, offy, bnds);
481 /* Otherwise, use the value ranges to determine the initial
482 estimates on below and up. */
487 determine_value_range (type, varx, offx, minx, maxx);
488 determine_value_range (type, vary, offy, miny, maxy);
490 mpz_sub (bnds->below, minx, maxy);
491 mpz_sub (bnds->up, maxx, miny);
498 /* If both X and Y are constants, we cannot get any more precise. */
499 if (integer_zerop (varx) && integer_zerop (vary))
502 /* Now walk the dominators of the loop header and use the entry
503 guards to refine the estimates. */
504 for (bb = loop->header;
505 bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK;
506 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
508 if (!single_pred_p (bb))
510 e = single_pred_edge (bb);
512 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
515 cond = COND_EXPR_COND (last_stmt (e->src));
516 if (!COMPARISON_CLASS_P (cond))
518 c0 = TREE_OPERAND (cond, 0);
519 cmp = TREE_CODE (cond);
520 c1 = TREE_OPERAND (cond, 1);
522 if (e->flags & EDGE_FALSE_VALUE)
523 cmp = invert_tree_comparison (cmp, false);
525 refine_bounds_using_guard (type, varx, offx, vary, offy,
535 /* Update the bounds in BNDS that restrict the value of X to the bounds
536 that restrict the value of X + DELTA. X can be obtained as a
537 difference of two values in TYPE. */
540 bounds_add (bounds *bnds, double_int delta, tree type)
545 mpz_set_double_int (mdelta, delta, false);
548 mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true);
550 mpz_add (bnds->up, bnds->up, mdelta);
551 mpz_add (bnds->below, bnds->below, mdelta);
553 if (mpz_cmp (bnds->up, max) > 0)
554 mpz_set (bnds->up, max);
557 if (mpz_cmp (bnds->below, max) < 0)
558 mpz_set (bnds->below, max);
564 /* Update the bounds in BNDS that restrict the value of X to the bounds
565 that restrict the value of -X. */
568 bounds_negate (bounds *bnds)
572 mpz_init_set (tmp, bnds->up);
573 mpz_neg (bnds->up, bnds->below);
574 mpz_neg (bnds->below, tmp);
578 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
581 inverse (tree x, tree mask)
583 tree type = TREE_TYPE (x);
585 unsigned ctr = tree_floor_log2 (mask);
587 if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT)
589 unsigned HOST_WIDE_INT ix;
590 unsigned HOST_WIDE_INT imask;
591 unsigned HOST_WIDE_INT irslt = 1;
593 gcc_assert (cst_and_fits_in_hwi (x));
594 gcc_assert (cst_and_fits_in_hwi (mask));
596 ix = int_cst_value (x);
597 imask = int_cst_value (mask);
606 rslt = build_int_cst_type (type, irslt);
610 rslt = build_int_cst (type, 1);
613 rslt = int_const_binop (MULT_EXPR, rslt, x, 0);
614 x = int_const_binop (MULT_EXPR, x, x, 0);
616 rslt = int_const_binop (BIT_AND_EXPR, rslt, mask, 0);
622 /* Derives the upper bound BND on the number of executions of loop with exit
623 condition S * i <> C, assuming that the loop is not infinite. If
624 NO_OVERFLOW is true, then the control variable of the loop does not
625 overflow. If NO_OVERFLOW is true or BNDS.below >= 0, then BNDS.up
626 contains the upper bound on the value of C. */
629 number_of_iterations_ne_max (mpz_t bnd, bool no_overflow, tree c, tree s,
635 /* If the control variable does not overflow, the number of iterations is
636 at most c / s. Otherwise it is at most the period of the control
638 if (!no_overflow && !multiple_of_p (TREE_TYPE (c), c, s))
640 max = double_int_mask (TYPE_PRECISION (TREE_TYPE (c))
641 - tree_low_cst (num_ending_zeros (s), 1));
642 mpz_set_double_int (bnd, max, true);
646 /* Determine the upper bound on C. */
647 if (no_overflow || mpz_sgn (bnds->below) >= 0)
648 mpz_set (bnd, bnds->up);
649 else if (TREE_CODE (c) == INTEGER_CST)
650 mpz_set_double_int (bnd, tree_to_double_int (c), true);
652 mpz_set_double_int (bnd, double_int_mask (TYPE_PRECISION (TREE_TYPE (c))),
656 mpz_set_double_int (d, tree_to_double_int (s), true);
657 mpz_fdiv_q (bnd, bnd, d);
661 /* Determines number of iterations of loop whose ending condition
662 is IV <> FINAL. TYPE is the type of the iv. The number of
663 iterations is stored to NITER. NEVER_INFINITE is true if
664 we know that the exit must be taken eventually, i.e., that the IV
665 ever reaches the value FINAL (we derived this earlier, and possibly set
666 NITER->assumptions to make sure this is the case). BNDS contains the
667 bounds on the difference FINAL - IV->base. */
670 number_of_iterations_ne (tree type, affine_iv *iv, tree final,
671 struct tree_niter_desc *niter, bool never_infinite,
674 tree niter_type = unsigned_type_for (type);
675 tree s, c, d, bits, assumption, tmp, bound;
678 niter->control = *iv;
679 niter->bound = final;
680 niter->cmp = NE_EXPR;
682 /* Rearrange the terms so that we get inequality S * i <> C, with S
683 positive. Also cast everything to the unsigned type. If IV does
684 not overflow, BNDS bounds the value of C. Also, this is the
685 case if the computation |FINAL - IV->base| does not overflow, i.e.,
686 if BNDS->below in the result is nonnegative. */
687 if (tree_int_cst_sign_bit (iv->step))
689 s = fold_convert (niter_type,
690 fold_build1 (NEGATE_EXPR, type, iv->step));
691 c = fold_build2 (MINUS_EXPR, niter_type,
692 fold_convert (niter_type, iv->base),
693 fold_convert (niter_type, final));
694 bounds_negate (bnds);
698 s = fold_convert (niter_type, iv->step);
699 c = fold_build2 (MINUS_EXPR, niter_type,
700 fold_convert (niter_type, final),
701 fold_convert (niter_type, iv->base));
705 number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds);
706 niter->max = mpz_to_double_int (niter_type, max);
709 /* First the trivial cases -- when the step is 1. */
710 if (integer_onep (s))
716 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
717 is infinite. Otherwise, the number of iterations is
718 (inverse(s/d) * (c/d)) mod (size of mode/d). */
719 bits = num_ending_zeros (s);
720 bound = build_low_bits_mask (niter_type,
721 (TYPE_PRECISION (niter_type)
722 - tree_low_cst (bits, 1)));
724 d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
725 build_int_cst (niter_type, 1), bits);
726 s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
730 /* If we cannot assume that the loop is not infinite, record the
731 assumptions for divisibility of c. */
732 assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d);
733 assumption = fold_build2 (EQ_EXPR, boolean_type_node,
734 assumption, build_int_cst (niter_type, 0));
735 if (!integer_nonzerop (assumption))
736 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
737 niter->assumptions, assumption);
740 c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d);
741 tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound));
742 niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound);
746 /* Checks whether we can determine the final value of the control variable
747 of the loop with ending condition IV0 < IV1 (computed in TYPE).
748 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
749 of the step. The assumptions necessary to ensure that the computation
750 of the final value does not overflow are recorded in NITER. If we
751 find the final value, we adjust DELTA and return TRUE. Otherwise
752 we return false. BNDS bounds the value of IV1->base - IV0->base,
753 and will be updated by the same amount as DELTA. */
756 number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1,
757 struct tree_niter_desc *niter,
758 tree *delta, tree step,
761 tree niter_type = TREE_TYPE (step);
762 tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step);
765 tree assumption = boolean_true_node, bound, noloop;
768 if (TREE_CODE (mod) != INTEGER_CST)
770 if (integer_nonzerop (mod))
771 mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
772 tmod = fold_convert (type, mod);
775 mpz_set_double_int (mmod, tree_to_double_int (mod), true);
776 mpz_neg (mmod, mmod);
778 if (integer_nonzerop (iv0->step))
780 /* The final value of the iv is iv1->base + MOD, assuming that this
781 computation does not overflow, and that
782 iv0->base <= iv1->base + MOD. */
783 if (!iv1->no_overflow && !integer_zerop (mod))
785 bound = fold_build2 (MINUS_EXPR, type,
786 TYPE_MAX_VALUE (type), tmod);
787 assumption = fold_build2 (LE_EXPR, boolean_type_node,
789 if (integer_zerop (assumption))
792 if (mpz_cmp (mmod, bnds->below) < 0)
793 noloop = boolean_false_node;
795 noloop = fold_build2 (GT_EXPR, boolean_type_node,
797 fold_build2 (PLUS_EXPR, type,
802 /* The final value of the iv is iv0->base - MOD, assuming that this
803 computation does not overflow, and that
804 iv0->base - MOD <= iv1->base. */
805 if (!iv0->no_overflow && !integer_zerop (mod))
807 bound = fold_build2 (PLUS_EXPR, type,
808 TYPE_MIN_VALUE (type), tmod);
809 assumption = fold_build2 (GE_EXPR, boolean_type_node,
811 if (integer_zerop (assumption))
814 if (mpz_cmp (mmod, bnds->below) < 0)
815 noloop = boolean_false_node;
817 noloop = fold_build2 (GT_EXPR, boolean_type_node,
818 fold_build2 (MINUS_EXPR, type,
823 if (!integer_nonzerop (assumption))
824 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
827 if (!integer_zerop (noloop))
828 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
831 bounds_add (bnds, tree_to_double_int (mod), type);
832 *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod);
840 /* Add assertions to NITER that ensure that the control variable of the loop
841 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
842 are TYPE. Returns false if we can prove that there is an overflow, true
843 otherwise. STEP is the absolute value of the step. */
846 assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
847 struct tree_niter_desc *niter, tree step)
849 tree bound, d, assumption, diff;
850 tree niter_type = TREE_TYPE (step);
852 if (integer_nonzerop (iv0->step))
854 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
855 if (iv0->no_overflow)
858 /* If iv0->base is a constant, we can determine the last value before
859 overflow precisely; otherwise we conservatively assume
862 if (TREE_CODE (iv0->base) == INTEGER_CST)
864 d = fold_build2 (MINUS_EXPR, niter_type,
865 fold_convert (niter_type, TYPE_MAX_VALUE (type)),
866 fold_convert (niter_type, iv0->base));
867 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
870 diff = fold_build2 (MINUS_EXPR, niter_type, step,
871 build_int_cst (niter_type, 1));
872 bound = fold_build2 (MINUS_EXPR, type,
873 TYPE_MAX_VALUE (type), fold_convert (type, diff));
874 assumption = fold_build2 (LE_EXPR, boolean_type_node,
879 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
880 if (iv1->no_overflow)
883 if (TREE_CODE (iv1->base) == INTEGER_CST)
885 d = fold_build2 (MINUS_EXPR, niter_type,
886 fold_convert (niter_type, iv1->base),
887 fold_convert (niter_type, TYPE_MIN_VALUE (type)));
888 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
891 diff = fold_build2 (MINUS_EXPR, niter_type, step,
892 build_int_cst (niter_type, 1));
893 bound = fold_build2 (PLUS_EXPR, type,
894 TYPE_MIN_VALUE (type), fold_convert (type, diff));
895 assumption = fold_build2 (GE_EXPR, boolean_type_node,
899 if (integer_zerop (assumption))
901 if (!integer_nonzerop (assumption))
902 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
903 niter->assumptions, assumption);
905 iv0->no_overflow = true;
906 iv1->no_overflow = true;
910 /* Add an assumption to NITER that a loop whose ending condition
911 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
912 bounds the value of IV1->base - IV0->base. */
915 assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
916 struct tree_niter_desc *niter, bounds *bnds)
918 tree assumption = boolean_true_node, bound, diff;
919 tree mbz, mbzl, mbzr;
920 bool rolls_p, no_overflow_p;
924 /* We are going to compute the number of iterations as
925 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
926 variant of TYPE. This formula only works if
928 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
930 (where MAX is the maximum value of the unsigned variant of TYPE, and
931 the computations in this formula are performed in full precision
934 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
935 we have a condition of form iv0->base - step < iv1->base before the loop,
936 and for loops iv0->base < iv1->base - step * i the condition
937 iv0->base < iv1->base + step, due to loop header copying, which enable us
938 to prove the lower bound.
940 The upper bound is more complicated. Unless the expressions for initial
941 and final value themselves contain enough information, we usually cannot
942 derive it from the context. */
944 /* First check whether the answer does not follow from the bounds we gathered
946 if (integer_nonzerop (iv0->step))
947 dstep = tree_to_double_int (iv0->step);
950 dstep = double_int_sext (tree_to_double_int (iv1->step),
951 TYPE_PRECISION (type));
952 dstep = double_int_neg (dstep);
956 mpz_set_double_int (mstep, dstep, true);
957 mpz_neg (mstep, mstep);
958 mpz_add_ui (mstep, mstep, 1);
960 rolls_p = mpz_cmp (mstep, bnds->below) <= 0;
963 mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true);
964 mpz_add (max, max, mstep);
965 no_overflow_p = (mpz_cmp (bnds->up, max) <= 0
966 /* For pointers, only values lying inside a single object
967 can be compared or manipulated by pointer arithmetics.
968 Gcc in general does not allow or handle objects larger
969 than half of the address space, hence the upper bound
970 is satisfied for pointers. */
971 || POINTER_TYPE_P (type));
975 if (rolls_p && no_overflow_p)
978 /* Now the hard part; we must formulate the assumption(s) as expressions, and
979 we must be careful not to introduce overflow. */
981 if (integer_nonzerop (iv0->step))
983 diff = fold_build2 (MINUS_EXPR, type,
984 iv0->step, build_int_cst (type, 1));
986 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
987 0 address never belongs to any object, we can assume this for
989 if (!POINTER_TYPE_P (type))
991 bound = fold_build2 (PLUS_EXPR, type,
992 TYPE_MIN_VALUE (type), diff);
993 assumption = fold_build2 (GE_EXPR, boolean_type_node,
997 /* And then we can compute iv0->base - diff, and compare it with
999 mbzl = fold_build2 (MINUS_EXPR, type, iv0->base, diff);
1004 diff = fold_build2 (PLUS_EXPR, type,
1005 iv1->step, build_int_cst (type, 1));
1007 if (!POINTER_TYPE_P (type))
1009 bound = fold_build2 (PLUS_EXPR, type,
1010 TYPE_MAX_VALUE (type), diff);
1011 assumption = fold_build2 (LE_EXPR, boolean_type_node,
1016 mbzr = fold_build2 (MINUS_EXPR, type, iv1->base, diff);
1019 if (!integer_nonzerop (assumption))
1020 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1021 niter->assumptions, assumption);
1024 mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr);
1025 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
1026 niter->may_be_zero, mbz);
1030 /* Determines number of iterations of loop whose ending condition
1031 is IV0 < IV1. TYPE is the type of the iv. The number of
1032 iterations is stored to NITER. BNDS bounds the difference
1033 IV1->base - IV0->base. */
1036 number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
1037 struct tree_niter_desc *niter,
1038 bool never_infinite ATTRIBUTE_UNUSED,
1041 tree niter_type = unsigned_type_for (type);
1042 tree delta, step, s;
1045 if (integer_nonzerop (iv0->step))
1047 niter->control = *iv0;
1048 niter->cmp = LT_EXPR;
1049 niter->bound = iv1->base;
1053 niter->control = *iv1;
1054 niter->cmp = GT_EXPR;
1055 niter->bound = iv0->base;
1058 delta = fold_build2 (MINUS_EXPR, niter_type,
1059 fold_convert (niter_type, iv1->base),
1060 fold_convert (niter_type, iv0->base));
1062 /* First handle the special case that the step is +-1. */
1063 if ((integer_onep (iv0->step) && integer_zerop (iv1->step))
1064 || (integer_all_onesp (iv1->step) && integer_zerop (iv0->step)))
1066 /* for (i = iv0->base; i < iv1->base; i++)
1070 for (i = iv1->base; i > iv0->base; i--).
1072 In both cases # of iterations is iv1->base - iv0->base, assuming that
1073 iv1->base >= iv0->base.
1075 First try to derive a lower bound on the value of
1076 iv1->base - iv0->base, computed in full precision. If the difference
1077 is nonnegative, we are done, otherwise we must record the
1080 if (mpz_sgn (bnds->below) < 0)
1081 niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
1082 iv1->base, iv0->base);
1083 niter->niter = delta;
1084 niter->max = mpz_to_double_int (niter_type, bnds->up);
1088 if (integer_nonzerop (iv0->step))
1089 step = fold_convert (niter_type, iv0->step);
1091 step = fold_convert (niter_type,
1092 fold_build1 (NEGATE_EXPR, type, iv1->step));
1094 /* If we can determine the final value of the control iv exactly, we can
1095 transform the condition to != comparison. In particular, this will be
1096 the case if DELTA is constant. */
1097 if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step,
1102 zps.base = build_int_cst (niter_type, 0);
1104 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1105 zps does not overflow. */
1106 zps.no_overflow = true;
1108 return number_of_iterations_ne (type, &zps, delta, niter, true, bnds);
1111 /* Make sure that the control iv does not overflow. */
1112 if (!assert_no_overflow_lt (type, iv0, iv1, niter, step))
1115 /* We determine the number of iterations as (delta + step - 1) / step. For
1116 this to work, we must know that iv1->base >= iv0->base - step + 1,
1117 otherwise the loop does not roll. */
1118 assert_loop_rolls_lt (type, iv0, iv1, niter, bnds);
1120 s = fold_build2 (MINUS_EXPR, niter_type,
1121 step, build_int_cst (niter_type, 1));
1122 delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
1123 niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
1127 mpz_set_double_int (mstep, tree_to_double_int (step), true);
1128 mpz_add (tmp, bnds->up, mstep);
1129 mpz_sub_ui (tmp, tmp, 1);
1130 mpz_fdiv_q (tmp, tmp, mstep);
1131 niter->max = mpz_to_double_int (niter_type, tmp);
1138 /* Determines number of iterations of loop whose ending condition
1139 is IV0 <= IV1. TYPE is the type of the iv. The number of
1140 iterations is stored to NITER. NEVER_INFINITE is true if
1141 we know that this condition must eventually become false (we derived this
1142 earlier, and possibly set NITER->assumptions to make sure this
1143 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1146 number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1,
1147 struct tree_niter_desc *niter, bool never_infinite,
1152 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1153 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1154 value of the type. This we must know anyway, since if it is
1155 equal to this value, the loop rolls forever. */
1157 if (!never_infinite)
1159 if (integer_nonzerop (iv0->step))
1160 assumption = fold_build2 (NE_EXPR, boolean_type_node,
1161 iv1->base, TYPE_MAX_VALUE (type));
1163 assumption = fold_build2 (NE_EXPR, boolean_type_node,
1164 iv0->base, TYPE_MIN_VALUE (type));
1166 if (integer_zerop (assumption))
1168 if (!integer_nonzerop (assumption))
1169 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1170 niter->assumptions, assumption);
1173 if (integer_nonzerop (iv0->step))
1174 iv1->base = fold_build2 (PLUS_EXPR, type,
1175 iv1->base, build_int_cst (type, 1));
1177 iv0->base = fold_build2 (MINUS_EXPR, type,
1178 iv0->base, build_int_cst (type, 1));
1180 bounds_add (bnds, double_int_one, type);
1182 return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite, bnds);
1185 /* Dumps description of affine induction variable IV to FILE. */
1188 dump_affine_iv (FILE *file, affine_iv *iv)
1190 if (!integer_zerop (iv->step))
1191 fprintf (file, "[");
1193 print_generic_expr (dump_file, iv->base, TDF_SLIM);
1195 if (!integer_zerop (iv->step))
1197 fprintf (file, ", + , ");
1198 print_generic_expr (dump_file, iv->step, TDF_SLIM);
1199 fprintf (file, "]%s", iv->no_overflow ? "(no_overflow)" : "");
1203 /* Determine the number of iterations according to condition (for staying
1204 inside loop) which compares two induction variables using comparison
1205 operator CODE. The induction variable on left side of the comparison
1206 is IV0, the right-hand side is IV1. Both induction variables must have
1207 type TYPE, which must be an integer or pointer type. The steps of the
1208 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1210 LOOP is the loop whose number of iterations we are determining.
1212 ONLY_EXIT is true if we are sure this is the only way the loop could be
1213 exited (including possibly non-returning function calls, exceptions, etc.)
1214 -- in this case we can use the information whether the control induction
1215 variables can overflow or not in a more efficient way.
1217 The results (number of iterations and assumptions as described in
1218 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
1219 Returns false if it fails to determine number of iterations, true if it
1220 was determined (possibly with some assumptions). */
1223 number_of_iterations_cond (struct loop *loop,
1224 tree type, affine_iv *iv0, enum tree_code code,
1225 affine_iv *iv1, struct tree_niter_desc *niter,
1228 bool never_infinite, ret;
1231 /* The meaning of these assumptions is this:
1233 then the rest of information does not have to be valid
1234 if may_be_zero then the loop does not roll, even if
1236 niter->assumptions = boolean_true_node;
1237 niter->may_be_zero = boolean_false_node;
1238 niter->niter = NULL_TREE;
1239 niter->max = double_int_zero;
1241 niter->bound = NULL_TREE;
1242 niter->cmp = ERROR_MARK;
1244 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1245 the control variable is on lhs. */
1246 if (code == GE_EXPR || code == GT_EXPR
1247 || (code == NE_EXPR && integer_zerop (iv0->step)))
1250 code = swap_tree_comparison (code);
1255 /* If this is not the only possible exit from the loop, the information
1256 that the induction variables cannot overflow as derived from
1257 signedness analysis cannot be relied upon. We use them e.g. in the
1258 following way: given loop for (i = 0; i <= n; i++), if i is
1259 signed, it cannot overflow, thus this loop is equivalent to
1260 for (i = 0; i < n + 1; i++); however, if n == MAX, but the loop
1261 is exited in some other way before i overflows, this transformation
1262 is incorrect (the new loop exits immediately). */
1263 iv0->no_overflow = false;
1264 iv1->no_overflow = false;
1267 if (POINTER_TYPE_P (type))
1269 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1270 to the same object. If they do, the control variable cannot wrap
1271 (as wrap around the bounds of memory will never return a pointer
1272 that would be guaranteed to point to the same object, even if we
1273 avoid undefined behavior by casting to size_t and back). The
1274 restrictions on pointer arithmetics and comparisons of pointers
1275 ensure that using the no-overflow assumptions is correct in this
1276 case even if ONLY_EXIT is false. */
1277 iv0->no_overflow = true;
1278 iv1->no_overflow = true;
1281 /* If the control induction variable does not overflow, the loop obviously
1282 cannot be infinite. */
1283 if (!integer_zerop (iv0->step) && iv0->no_overflow)
1284 never_infinite = true;
1285 else if (!integer_zerop (iv1->step) && iv1->no_overflow)
1286 never_infinite = true;
1288 never_infinite = false;
1290 /* We can handle the case when neither of the sides of the comparison is
1291 invariant, provided that the test is NE_EXPR. This rarely occurs in
1292 practice, but it is simple enough to manage. */
1293 if (!integer_zerop (iv0->step) && !integer_zerop (iv1->step))
1295 if (code != NE_EXPR)
1298 iv0->step = fold_binary_to_constant (MINUS_EXPR, type,
1299 iv0->step, iv1->step);
1300 iv0->no_overflow = false;
1301 iv1->step = build_int_cst (type, 0);
1302 iv1->no_overflow = true;
1305 /* If the result of the comparison is a constant, the loop is weird. More
1306 precise handling would be possible, but the situation is not common enough
1307 to waste time on it. */
1308 if (integer_zerop (iv0->step) && integer_zerop (iv1->step))
1311 /* Ignore loops of while (i-- < 10) type. */
1312 if (code != NE_EXPR)
1314 if (iv0->step && tree_int_cst_sign_bit (iv0->step))
1317 if (!integer_zerop (iv1->step) && !tree_int_cst_sign_bit (iv1->step))
1321 /* If the loop exits immediately, there is nothing to do. */
1322 if (integer_zerop (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
1324 niter->niter = build_int_cst (unsigned_type_for (type), 0);
1325 niter->max = double_int_zero;
1329 /* OK, now we know we have a senseful loop. Handle several cases, depending
1330 on what comparison operator is used. */
1331 bound_difference (loop, iv1->base, iv0->base, &bnds);
1333 if (dump_file && (dump_flags & TDF_DETAILS))
1336 "Analysing # of iterations of loop %d\n", loop->num);
1338 fprintf (dump_file, " exit condition ");
1339 dump_affine_iv (dump_file, iv0);
1340 fprintf (dump_file, " %s ",
1341 code == NE_EXPR ? "!="
1342 : code == LT_EXPR ? "<"
1344 dump_affine_iv (dump_file, iv1);
1345 fprintf (dump_file, "\n");
1347 fprintf (dump_file, " bounds on difference of bases: ");
1348 mpz_out_str (dump_file, 10, bnds.below);
1349 fprintf (dump_file, " ... ");
1350 mpz_out_str (dump_file, 10, bnds.up);
1351 fprintf (dump_file, "\n");
1357 gcc_assert (integer_zerop (iv1->step));
1358 ret = number_of_iterations_ne (type, iv0, iv1->base, niter,
1359 never_infinite, &bnds);
1363 ret = number_of_iterations_lt (type, iv0, iv1, niter, never_infinite,
1368 ret = number_of_iterations_le (type, iv0, iv1, niter, never_infinite,
1376 mpz_clear (bnds.up);
1377 mpz_clear (bnds.below);
1379 if (dump_file && (dump_flags & TDF_DETAILS))
1383 fprintf (dump_file, " result:\n");
1384 if (!integer_nonzerop (niter->assumptions))
1386 fprintf (dump_file, " under assumptions ");
1387 print_generic_expr (dump_file, niter->assumptions, TDF_SLIM);
1388 fprintf (dump_file, "\n");
1391 if (!integer_zerop (niter->may_be_zero))
1393 fprintf (dump_file, " zero if ");
1394 print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
1395 fprintf (dump_file, "\n");
1398 fprintf (dump_file, " # of iterations ");
1399 print_generic_expr (dump_file, niter->niter, TDF_SLIM);
1400 fprintf (dump_file, ", bounded by ");
1401 dump_double_int (dump_file, niter->max, true);
1402 fprintf (dump_file, "\n");
1405 fprintf (dump_file, " failed\n\n");
1410 /* Substitute NEW for OLD in EXPR and fold the result. */
1413 simplify_replace_tree (tree expr, tree old, tree new)
1416 tree ret = NULL_TREE, e, se;
1422 || operand_equal_p (expr, old, 0))
1423 return unshare_expr (new);
1425 if (!EXPR_P (expr) && !GIMPLE_STMT_P (expr))
1428 n = TREE_OPERAND_LENGTH (expr);
1429 for (i = 0; i < n; i++)
1431 e = TREE_OPERAND (expr, i);
1432 se = simplify_replace_tree (e, old, new);
1437 ret = copy_node (expr);
1439 TREE_OPERAND (ret, i) = se;
1442 return (ret ? fold (ret) : expr);
1445 /* Expand definitions of ssa names in EXPR as long as they are simple
1446 enough, and return the new expression. */
1449 expand_simple_operations (tree expr)
1452 tree ret = NULL_TREE, e, ee, stmt;
1453 enum tree_code code;
1455 if (expr == NULL_TREE)
1458 if (is_gimple_min_invariant (expr))
1461 code = TREE_CODE (expr);
1462 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
1464 n = TREE_OPERAND_LENGTH (expr);
1465 for (i = 0; i < n; i++)
1467 e = TREE_OPERAND (expr, i);
1468 ee = expand_simple_operations (e);
1473 ret = copy_node (expr);
1475 TREE_OPERAND (ret, i) = ee;
1481 fold_defer_overflow_warnings ();
1483 fold_undefer_and_ignore_overflow_warnings ();
1487 if (TREE_CODE (expr) != SSA_NAME)
1490 stmt = SSA_NAME_DEF_STMT (expr);
1491 if (TREE_CODE (stmt) == PHI_NODE)
1493 basic_block src, dest;
1495 if (PHI_NUM_ARGS (stmt) != 1)
1497 e = PHI_ARG_DEF (stmt, 0);
1499 /* Avoid propagating through loop exit phi nodes, which
1500 could break loop-closed SSA form restrictions. */
1501 dest = bb_for_stmt (stmt);
1502 src = single_pred (dest);
1503 if (TREE_CODE (e) == SSA_NAME
1504 && src->loop_father != dest->loop_father)
1507 return expand_simple_operations (e);
1509 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
1512 e = GIMPLE_STMT_OPERAND (stmt, 1);
1513 if (/* Casts are simple. */
1514 TREE_CODE (e) != NOP_EXPR
1515 && TREE_CODE (e) != CONVERT_EXPR
1516 /* Copies are simple. */
1517 && TREE_CODE (e) != SSA_NAME
1518 /* Assignments of invariants are simple. */
1519 && !is_gimple_min_invariant (e)
1520 /* And increments and decrements by a constant are simple. */
1521 && !((TREE_CODE (e) == PLUS_EXPR
1522 || TREE_CODE (e) == MINUS_EXPR)
1523 && is_gimple_min_invariant (TREE_OPERAND (e, 1))))
1526 return expand_simple_operations (e);
1529 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1530 expression (or EXPR unchanged, if no simplification was possible). */
1533 tree_simplify_using_condition_1 (tree cond, tree expr)
1536 tree e, te, e0, e1, e2, notcond;
1537 enum tree_code code = TREE_CODE (expr);
1539 if (code == INTEGER_CST)
1542 if (code == TRUTH_OR_EXPR
1543 || code == TRUTH_AND_EXPR
1544 || code == COND_EXPR)
1548 e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0));
1549 if (TREE_OPERAND (expr, 0) != e0)
1552 e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1));
1553 if (TREE_OPERAND (expr, 1) != e1)
1556 if (code == COND_EXPR)
1558 e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2));
1559 if (TREE_OPERAND (expr, 2) != e2)
1567 if (code == COND_EXPR)
1568 expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
1570 expr = fold_build2 (code, boolean_type_node, e0, e1);
1576 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
1577 propagation, and vice versa. Fold does not handle this, since it is
1578 considered too expensive. */
1579 if (TREE_CODE (cond) == EQ_EXPR)
1581 e0 = TREE_OPERAND (cond, 0);
1582 e1 = TREE_OPERAND (cond, 1);
1584 /* We know that e0 == e1. Check whether we cannot simplify expr
1586 e = simplify_replace_tree (expr, e0, e1);
1587 if (integer_zerop (e) || integer_nonzerop (e))
1590 e = simplify_replace_tree (expr, e1, e0);
1591 if (integer_zerop (e) || integer_nonzerop (e))
1594 if (TREE_CODE (expr) == EQ_EXPR)
1596 e0 = TREE_OPERAND (expr, 0);
1597 e1 = TREE_OPERAND (expr, 1);
1599 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
1600 e = simplify_replace_tree (cond, e0, e1);
1601 if (integer_zerop (e))
1603 e = simplify_replace_tree (cond, e1, e0);
1604 if (integer_zerop (e))
1607 if (TREE_CODE (expr) == NE_EXPR)
1609 e0 = TREE_OPERAND (expr, 0);
1610 e1 = TREE_OPERAND (expr, 1);
1612 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
1613 e = simplify_replace_tree (cond, e0, e1);
1614 if (integer_zerop (e))
1615 return boolean_true_node;
1616 e = simplify_replace_tree (cond, e1, e0);
1617 if (integer_zerop (e))
1618 return boolean_true_node;
1621 te = expand_simple_operations (expr);
1623 /* Check whether COND ==> EXPR. */
1624 notcond = invert_truthvalue (cond);
1625 e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te);
1626 if (e && integer_nonzerop (e))
1629 /* Check whether COND ==> not EXPR. */
1630 e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te);
1631 if (e && integer_zerop (e))
1637 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1638 expression (or EXPR unchanged, if no simplification was possible).
1639 Wrapper around tree_simplify_using_condition_1 that ensures that chains
1640 of simple operations in definitions of ssa names in COND are expanded,
1641 so that things like casts or incrementing the value of the bound before
1642 the loop do not cause us to fail. */
1645 tree_simplify_using_condition (tree cond, tree expr)
1647 cond = expand_simple_operations (cond);
1649 return tree_simplify_using_condition_1 (cond, expr);
1652 /* Tries to simplify EXPR using the conditions on entry to LOOP.
1653 Returns the simplified expression (or EXPR unchanged, if no
1654 simplification was possible).*/
1657 simplify_using_initial_conditions (struct loop *loop, tree expr)
1664 if (TREE_CODE (expr) == INTEGER_CST)
1667 /* Limit walking the dominators to avoid quadraticness in
1668 the number of BBs times the number of loops in degenerate
1670 for (bb = loop->header;
1671 bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK;
1672 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1674 if (!single_pred_p (bb))
1676 e = single_pred_edge (bb);
1678 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
1681 cond = COND_EXPR_COND (last_stmt (e->src));
1682 if (e->flags & EDGE_FALSE_VALUE)
1683 cond = invert_truthvalue (cond);
1684 expr = tree_simplify_using_condition (cond, expr);
1691 /* Tries to simplify EXPR using the evolutions of the loop invariants
1692 in the superloops of LOOP. Returns the simplified expression
1693 (or EXPR unchanged, if no simplification was possible). */
1696 simplify_using_outer_evolutions (struct loop *loop, tree expr)
1698 enum tree_code code = TREE_CODE (expr);
1702 if (is_gimple_min_invariant (expr))
1705 if (code == TRUTH_OR_EXPR
1706 || code == TRUTH_AND_EXPR
1707 || code == COND_EXPR)
1711 e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
1712 if (TREE_OPERAND (expr, 0) != e0)
1715 e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
1716 if (TREE_OPERAND (expr, 1) != e1)
1719 if (code == COND_EXPR)
1721 e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
1722 if (TREE_OPERAND (expr, 2) != e2)
1730 if (code == COND_EXPR)
1731 expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
1733 expr = fold_build2 (code, boolean_type_node, e0, e1);
1739 e = instantiate_parameters (loop, expr);
1740 if (is_gimple_min_invariant (e))
1746 /* Returns true if EXIT is the only possible exit from LOOP. */
1749 loop_only_exit_p (struct loop *loop, edge exit)
1752 block_stmt_iterator bsi;
1756 if (exit != single_exit (loop))
1759 body = get_loop_body (loop);
1760 for (i = 0; i < loop->num_nodes; i++)
1762 for (bsi = bsi_start (body[0]); !bsi_end_p (bsi); bsi_next (&bsi))
1764 call = get_call_expr_in (bsi_stmt (bsi));
1765 if (call && TREE_SIDE_EFFECTS (call))
1777 /* Stores description of number of iterations of LOOP derived from
1778 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
1779 useful information could be derived (and fields of NITER has
1780 meaning described in comments at struct tree_niter_desc
1781 declaration), false otherwise. If WARN is true and
1782 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1783 potentially unsafe assumptions. */
1786 number_of_iterations_exit (struct loop *loop, edge exit,
1787 struct tree_niter_desc *niter,
1790 tree stmt, cond, type;
1792 enum tree_code code;
1795 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
1798 niter->assumptions = boolean_false_node;
1799 stmt = last_stmt (exit->src);
1800 if (!stmt || TREE_CODE (stmt) != COND_EXPR)
1803 /* We want the condition for staying inside loop. */
1804 cond = COND_EXPR_COND (stmt);
1805 if (exit->flags & EDGE_TRUE_VALUE)
1806 cond = invert_truthvalue (cond);
1808 code = TREE_CODE (cond);
1822 op0 = TREE_OPERAND (cond, 0);
1823 op1 = TREE_OPERAND (cond, 1);
1824 type = TREE_TYPE (op0);
1826 if (TREE_CODE (type) != INTEGER_TYPE
1827 && !POINTER_TYPE_P (type))
1830 if (!simple_iv (loop, stmt, op0, &iv0, false))
1832 if (!simple_iv (loop, stmt, op1, &iv1, false))
1835 /* We don't want to see undefined signed overflow warnings while
1836 computing the number of iterations. */
1837 fold_defer_overflow_warnings ();
1839 iv0.base = expand_simple_operations (iv0.base);
1840 iv1.base = expand_simple_operations (iv1.base);
1841 if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter,
1842 loop_only_exit_p (loop, exit)))
1844 fold_undefer_and_ignore_overflow_warnings ();
1850 niter->assumptions = simplify_using_outer_evolutions (loop,
1851 niter->assumptions);
1852 niter->may_be_zero = simplify_using_outer_evolutions (loop,
1853 niter->may_be_zero);
1854 niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
1858 = simplify_using_initial_conditions (loop,
1859 niter->assumptions);
1861 = simplify_using_initial_conditions (loop,
1862 niter->may_be_zero);
1864 fold_undefer_and_ignore_overflow_warnings ();
1866 if (integer_onep (niter->assumptions))
1869 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1870 But if we can prove that there is overflow or some other source of weird
1871 behavior, ignore the loop even with -funsafe-loop-optimizations. */
1872 if (integer_zerop (niter->assumptions))
1875 if (flag_unsafe_loop_optimizations)
1876 niter->assumptions = boolean_true_node;
1880 const char *wording;
1881 location_t loc = EXPR_LOCATION (stmt);
1883 /* We can provide a more specific warning if one of the operator is
1884 constant and the other advances by +1 or -1. */
1885 if (!integer_zerop (iv1.step)
1886 ? (integer_zerop (iv0.step)
1887 && (integer_onep (iv1.step) || integer_all_onesp (iv1.step)))
1888 : (integer_onep (iv0.step) || integer_all_onesp (iv0.step)))
1890 flag_unsafe_loop_optimizations
1891 ? N_("assuming that the loop is not infinite")
1892 : N_("cannot optimize possibly infinite loops");
1895 flag_unsafe_loop_optimizations
1896 ? N_("assuming that the loop counter does not overflow")
1897 : N_("cannot optimize loop, the loop counter may overflow");
1899 if (LOCATION_LINE (loc) > 0)
1900 warning (OPT_Wunsafe_loop_optimizations, "%H%s", &loc, gettext (wording));
1902 warning (OPT_Wunsafe_loop_optimizations, "%s", gettext (wording));
1905 return flag_unsafe_loop_optimizations;
1908 /* Try to determine the number of iterations of LOOP. If we succeed,
1909 expression giving number of iterations is returned and *EXIT is
1910 set to the edge from that the information is obtained. Otherwise
1911 chrec_dont_know is returned. */
1914 find_loop_niter (struct loop *loop, edge *exit)
1917 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1919 tree niter = NULL_TREE, aniter;
1920 struct tree_niter_desc desc;
1923 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
1925 if (!just_once_each_iteration_p (loop, ex->src))
1928 if (!number_of_iterations_exit (loop, ex, &desc, false))
1931 if (integer_nonzerop (desc.may_be_zero))
1933 /* We exit in the first iteration through this exit.
1934 We won't find anything better. */
1935 niter = build_int_cst (unsigned_type_node, 0);
1940 if (!integer_zerop (desc.may_be_zero))
1943 aniter = desc.niter;
1947 /* Nothing recorded yet. */
1953 /* Prefer constants, the lower the better. */
1954 if (TREE_CODE (aniter) != INTEGER_CST)
1957 if (TREE_CODE (niter) != INTEGER_CST)
1964 if (tree_int_cst_lt (aniter, niter))
1971 VEC_free (edge, heap, exits);
1973 return niter ? niter : chrec_dont_know;
1978 Analysis of a number of iterations of a loop by a brute-force evaluation.
1982 /* Bound on the number of iterations we try to evaluate. */
1984 #define MAX_ITERATIONS_TO_TRACK \
1985 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
1987 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
1988 result by a chain of operations such that all but exactly one of their
1989 operands are constants. */
1992 chain_of_csts_start (struct loop *loop, tree x)
1994 tree stmt = SSA_NAME_DEF_STMT (x);
1996 basic_block bb = bb_for_stmt (stmt);
1999 || !flow_bb_inside_loop_p (loop, bb))
2002 if (TREE_CODE (stmt) == PHI_NODE)
2004 if (bb == loop->header)
2010 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
2013 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
2015 if (SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF) == NULL_DEF_OPERAND_P)
2018 use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
2019 if (use == NULL_USE_OPERAND_P)
2022 return chain_of_csts_start (loop, use);
2025 /* Determines whether the expression X is derived from a result of a phi node
2026 in header of LOOP such that
2028 * the derivation of X consists only from operations with constants
2029 * the initial value of the phi node is constant
2030 * the value of the phi node in the next iteration can be derived from the
2031 value in the current iteration by a chain of operations with constants.
2033 If such phi node exists, it is returned. If X is a constant, X is returned
2034 unchanged. Otherwise NULL_TREE is returned. */
2037 get_base_for (struct loop *loop, tree x)
2039 tree phi, init, next;
2041 if (is_gimple_min_invariant (x))
2044 phi = chain_of_csts_start (loop, x);
2048 init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
2049 next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
2051 if (TREE_CODE (next) != SSA_NAME)
2054 if (!is_gimple_min_invariant (init))
2057 if (chain_of_csts_start (loop, next) != phi)
2063 /* Given an expression X, then
2065 * if X is NULL_TREE, we return the constant BASE.
2066 * otherwise X is a SSA name, whose value in the considered loop is derived
2067 by a chain of operations with constant from a result of a phi node in
2068 the header of the loop. Then we return value of X when the value of the
2069 result of this phi node is given by the constant BASE. */
2072 get_val_for (tree x, tree base)
2078 gcc_assert (is_gimple_min_invariant (base));
2083 stmt = SSA_NAME_DEF_STMT (x);
2084 if (TREE_CODE (stmt) == PHI_NODE)
2087 FOR_EACH_SSA_USE_OPERAND (op, stmt, iter, SSA_OP_USE)
2089 nx = USE_FROM_PTR (op);
2090 val = get_val_for (nx, base);
2092 val = fold (GIMPLE_STMT_OPERAND (stmt, 1));
2094 /* only iterate loop once. */
2098 /* Should never reach here. */
2102 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2103 by brute force -- i.e. by determining the value of the operands of the
2104 condition at EXIT in first few iterations of the loop (assuming that
2105 these values are constant) and determining the first one in that the
2106 condition is not satisfied. Returns the constant giving the number
2107 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
2110 loop_niter_by_eval (struct loop *loop, edge exit)
2112 tree cond, cnd, acnd;
2113 tree op[2], val[2], next[2], aval[2], phi[2];
2117 cond = last_stmt (exit->src);
2118 if (!cond || TREE_CODE (cond) != COND_EXPR)
2119 return chrec_dont_know;
2121 cnd = COND_EXPR_COND (cond);
2122 if (exit->flags & EDGE_TRUE_VALUE)
2123 cnd = invert_truthvalue (cnd);
2125 cmp = TREE_CODE (cnd);
2134 for (j = 0; j < 2; j++)
2135 op[j] = TREE_OPERAND (cnd, j);
2139 return chrec_dont_know;
2142 for (j = 0; j < 2; j++)
2144 phi[j] = get_base_for (loop, op[j]);
2146 return chrec_dont_know;
2149 for (j = 0; j < 2; j++)
2151 if (TREE_CODE (phi[j]) == PHI_NODE)
2153 val[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_preheader_edge (loop));
2154 next[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_latch_edge (loop));
2159 next[j] = NULL_TREE;
2164 /* Don't issue signed overflow warnings. */
2165 fold_defer_overflow_warnings ();
2167 for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
2169 for (j = 0; j < 2; j++)
2170 aval[j] = get_val_for (op[j], val[j]);
2172 acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]);
2173 if (acnd && integer_zerop (acnd))
2175 fold_undefer_and_ignore_overflow_warnings ();
2176 if (dump_file && (dump_flags & TDF_DETAILS))
2178 "Proved that loop %d iterates %d times using brute force.\n",
2180 return build_int_cst (unsigned_type_node, i);
2183 for (j = 0; j < 2; j++)
2185 val[j] = get_val_for (next[j], val[j]);
2186 if (!is_gimple_min_invariant (val[j]))
2188 fold_undefer_and_ignore_overflow_warnings ();
2189 return chrec_dont_know;
2194 fold_undefer_and_ignore_overflow_warnings ();
2196 return chrec_dont_know;
2199 /* Finds the exit of the LOOP by that the loop exits after a constant
2200 number of iterations and stores the exit edge to *EXIT. The constant
2201 giving the number of iterations of LOOP is returned. The number of
2202 iterations is determined using loop_niter_by_eval (i.e. by brute force
2203 evaluation). If we are unable to find the exit for that loop_niter_by_eval
2204 determines the number of iterations, chrec_dont_know is returned. */
2207 find_loop_niter_by_eval (struct loop *loop, edge *exit)
2210 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
2212 tree niter = NULL_TREE, aniter;
2215 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
2217 if (!just_once_each_iteration_p (loop, ex->src))
2220 aniter = loop_niter_by_eval (loop, ex);
2221 if (chrec_contains_undetermined (aniter))
2225 && !tree_int_cst_lt (aniter, niter))
2231 VEC_free (edge, heap, exits);
2233 return niter ? niter : chrec_dont_know;
2238 Analysis of upper bounds on number of iterations of a loop.
2242 /* Returns a constant upper bound on the value of expression VAL. VAL
2243 is considered to be unsigned. If its type is signed, its value must
2247 derive_constant_upper_bound (tree val)
2249 tree type = TREE_TYPE (val);
2250 tree op0, op1, subtype, maxt;
2251 double_int bnd, max, mmax, cst;
2254 if (INTEGRAL_TYPE_P (type))
2255 maxt = TYPE_MAX_VALUE (type);
2257 maxt = upper_bound_in_type (type, type);
2259 max = tree_to_double_int (maxt);
2261 switch (TREE_CODE (val))
2264 return tree_to_double_int (val);
2268 op0 = TREE_OPERAND (val, 0);
2269 subtype = TREE_TYPE (op0);
2270 if (!TYPE_UNSIGNED (subtype)
2271 /* If TYPE is also signed, the fact that VAL is nonnegative implies
2272 that OP0 is nonnegative. */
2273 && TYPE_UNSIGNED (type)
2274 && !tree_expr_nonnegative_p (op0))
2276 /* If we cannot prove that the casted expression is nonnegative,
2277 we cannot establish more useful upper bound than the precision
2278 of the type gives us. */
2282 /* We now know that op0 is an nonnegative value. Try deriving an upper
2284 bnd = derive_constant_upper_bound (op0);
2286 /* If the bound does not fit in TYPE, max. value of TYPE could be
2288 if (double_int_ucmp (max, bnd) < 0)
2295 op0 = TREE_OPERAND (val, 0);
2296 op1 = TREE_OPERAND (val, 1);
2298 if (TREE_CODE (op1) != INTEGER_CST
2299 || !tree_expr_nonnegative_p (op0))
2302 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
2303 choose the most logical way how to treat this constant regardless
2304 of the signedness of the type. */
2305 cst = tree_to_double_int (op1);
2306 cst = double_int_sext (cst, TYPE_PRECISION (type));
2307 if (TREE_CODE (val) == PLUS_EXPR)
2308 cst = double_int_neg (cst);
2310 bnd = derive_constant_upper_bound (op0);
2312 if (double_int_negative_p (cst))
2314 cst = double_int_neg (cst);
2315 /* Avoid CST == 0x80000... */
2316 if (double_int_negative_p (cst))
2319 /* OP0 + CST. We need to check that
2320 BND <= MAX (type) - CST. */
2322 mmax = double_int_add (max, double_int_neg (cst));
2323 if (double_int_ucmp (bnd, mmax) > 0)
2326 return double_int_add (bnd, cst);
2330 /* OP0 - CST, where CST >= 0.
2332 If TYPE is signed, we have already verified that OP0 >= 0, and we
2333 know that the result is nonnegative. This implies that
2336 If TYPE is unsigned, we must additionally know that OP0 >= CST,
2337 otherwise the operation underflows.
2340 /* This should only happen if the type is unsigned; however, for
2341 buggy programs that use overflowing signed arithmetics even with
2342 -fno-wrapv, this condition may also be true for signed values. */
2343 if (double_int_ucmp (bnd, cst) < 0)
2346 if (TYPE_UNSIGNED (type))
2348 tree tem = fold_binary (GE_EXPR, boolean_type_node, op0,
2349 double_int_to_tree (type, cst));
2350 if (!tem || integer_nonzerop (tem))
2354 bnd = double_int_add (bnd, double_int_neg (cst));
2359 case FLOOR_DIV_EXPR:
2360 case EXACT_DIV_EXPR:
2361 op0 = TREE_OPERAND (val, 0);
2362 op1 = TREE_OPERAND (val, 1);
2363 if (TREE_CODE (op1) != INTEGER_CST
2364 || tree_int_cst_sign_bit (op1))
2367 bnd = derive_constant_upper_bound (op0);
2368 return double_int_udiv (bnd, tree_to_double_int (op1), FLOOR_DIV_EXPR);
2371 op1 = TREE_OPERAND (val, 1);
2372 if (TREE_CODE (op1) != INTEGER_CST
2373 || tree_int_cst_sign_bit (op1))
2375 return tree_to_double_int (op1);
2378 stmt = SSA_NAME_DEF_STMT (val);
2379 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT
2380 || GIMPLE_STMT_OPERAND (stmt, 0) != val)
2382 return derive_constant_upper_bound (GIMPLE_STMT_OPERAND (stmt, 1));
2389 /* Records that every statement in LOOP is executed I_BOUND times.
2390 REALISTIC is true if I_BOUND is expected to be close the the real number
2391 of iterations. UPPER is true if we are sure the loop iterates at most
2395 record_niter_bound (struct loop *loop, double_int i_bound, bool realistic,
2398 /* Update the bounds only when there is no previous estimation, or when the current
2399 estimation is smaller. */
2401 && (!loop->any_upper_bound
2402 || double_int_ucmp (i_bound, loop->nb_iterations_upper_bound) < 0))
2404 loop->any_upper_bound = true;
2405 loop->nb_iterations_upper_bound = i_bound;
2408 && (!loop->any_estimate
2409 || double_int_ucmp (i_bound, loop->nb_iterations_estimate) < 0))
2411 loop->any_estimate = true;
2412 loop->nb_iterations_estimate = i_bound;
2416 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
2417 is true if the loop is exited immediately after STMT, and this exit
2418 is taken at last when the STMT is executed BOUND + 1 times.
2419 REALISTIC is true if BOUND is expected to be close the the real number
2420 of iterations. UPPER is true if we are sure the loop iterates at most
2421 BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */
2424 record_estimate (struct loop *loop, tree bound, double_int i_bound,
2425 tree at_stmt, bool is_exit, bool realistic, bool upper)
2430 if (dump_file && (dump_flags & TDF_DETAILS))
2432 fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : "");
2433 print_generic_expr (dump_file, at_stmt, TDF_SLIM);
2434 fprintf (dump_file, " is %sexecuted at most ",
2435 upper ? "" : "probably ");
2436 print_generic_expr (dump_file, bound, TDF_SLIM);
2437 fprintf (dump_file, " (bounded by ");
2438 dump_double_int (dump_file, i_bound, true);
2439 fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num);
2442 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
2443 real number of iterations. */
2444 if (TREE_CODE (bound) != INTEGER_CST)
2446 if (!upper && !realistic)
2449 /* If we have a guaranteed upper bound, record it in the appropriate
2453 struct nb_iter_bound *elt = XNEW (struct nb_iter_bound);
2455 elt->bound = i_bound;
2456 elt->stmt = at_stmt;
2457 elt->is_exit = is_exit;
2458 elt->next = loop->bounds;
2462 /* Update the number of iteration estimates according to the bound.
2463 If at_stmt is an exit, then every statement in the loop is
2464 executed at most BOUND + 1 times. If it is not an exit, then
2465 some of the statements before it could be executed BOUND + 2
2466 times, if an exit of LOOP is before stmt. */
2467 exit = single_exit (loop);
2470 && dominated_by_p (CDI_DOMINATORS,
2471 exit->src, bb_for_stmt (at_stmt))))
2472 delta = double_int_one;
2474 delta = double_int_two;
2475 i_bound = double_int_add (i_bound, delta);
2477 /* If an overflow occured, ignore the result. */
2478 if (double_int_ucmp (i_bound, delta) < 0)
2481 record_niter_bound (loop, i_bound, realistic, upper);
2484 /* Record the estimate on number of iterations of LOOP based on the fact that
2485 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
2486 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
2487 estimated number of iterations is expected to be close to the real one.
2488 UPPER is true if we are sure the induction variable does not wrap. */
2491 record_nonwrapping_iv (struct loop *loop, tree base, tree step, tree stmt,
2492 tree low, tree high, bool realistic, bool upper)
2494 tree niter_bound, extreme, delta;
2495 tree type = TREE_TYPE (base), unsigned_type;
2498 if (TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
2501 if (dump_file && (dump_flags & TDF_DETAILS))
2503 fprintf (dump_file, "Induction variable (");
2504 print_generic_expr (dump_file, TREE_TYPE (base), TDF_SLIM);
2505 fprintf (dump_file, ") ");
2506 print_generic_expr (dump_file, base, TDF_SLIM);
2507 fprintf (dump_file, " + ");
2508 print_generic_expr (dump_file, step, TDF_SLIM);
2509 fprintf (dump_file, " * iteration does not wrap in statement ");
2510 print_generic_expr (dump_file, stmt, TDF_SLIM);
2511 fprintf (dump_file, " in loop %d.\n", loop->num);
2514 unsigned_type = unsigned_type_for (type);
2515 base = fold_convert (unsigned_type, base);
2516 step = fold_convert (unsigned_type, step);
2518 if (tree_int_cst_sign_bit (step))
2520 extreme = fold_convert (unsigned_type, low);
2521 if (TREE_CODE (base) != INTEGER_CST)
2522 base = fold_convert (unsigned_type, high);
2523 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
2524 step = fold_build1 (NEGATE_EXPR, unsigned_type, step);
2528 extreme = fold_convert (unsigned_type, high);
2529 if (TREE_CODE (base) != INTEGER_CST)
2530 base = fold_convert (unsigned_type, low);
2531 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
2534 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
2535 would get out of the range. */
2536 niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step);
2537 max = derive_constant_upper_bound (niter_bound);
2538 record_estimate (loop, niter_bound, max, stmt, false, realistic, upper);
2541 /* Returns true if REF is a reference to an array at the end of a dynamically
2542 allocated structure. If this is the case, the array may be allocated larger
2543 than its upper bound implies. */
2546 array_at_struct_end_p (tree ref)
2548 tree base = get_base_address (ref);
2551 /* Unless the reference is through a pointer, the size of the array matches
2553 if (!base || !INDIRECT_REF_P (base))
2556 for (;handled_component_p (ref); ref = parent)
2558 parent = TREE_OPERAND (ref, 0);
2560 if (TREE_CODE (ref) == COMPONENT_REF)
2562 /* All fields of a union are at its end. */
2563 if (TREE_CODE (TREE_TYPE (parent)) == UNION_TYPE)
2566 /* Unless the field is at the end of the struct, we are done. */
2567 field = TREE_OPERAND (ref, 1);
2568 if (TREE_CHAIN (field))
2572 /* The other options are ARRAY_REF, ARRAY_RANGE_REF, VIEW_CONVERT_EXPR.
2573 In all these cases, we might be accessing the last element, and
2574 although in practice this will probably never happen, it is legal for
2575 the indices of this last element to exceed the bounds of the array.
2576 Therefore, continue checking. */
2579 gcc_assert (INDIRECT_REF_P (ref));
2583 /* Determine information about number of iterations a LOOP from the index
2584 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
2585 guaranteed to be executed in every iteration of LOOP. Callback for
2596 idx_infer_loop_bounds (tree base, tree *idx, void *dta)
2598 struct ilb_data *data = dta;
2599 tree ev, init, step;
2600 tree low, high, type, next;
2601 bool sign, upper = data->reliable, at_end = false;
2602 struct loop *loop = data->loop;
2604 if (TREE_CODE (base) != ARRAY_REF)
2607 /* For arrays at the end of the structure, we are not guaranteed that they
2608 do not really extend over their declared size. However, for arrays of
2609 size greater than one, this is unlikely to be intended. */
2610 if (array_at_struct_end_p (base))
2616 ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx));
2617 init = initial_condition (ev);
2618 step = evolution_part_in_loop_num (ev, loop->num);
2622 || TREE_CODE (step) != INTEGER_CST
2623 || integer_zerop (step)
2624 || tree_contains_chrecs (init, NULL)
2625 || chrec_contains_symbols_defined_in_loop (init, loop->num))
2628 low = array_ref_low_bound (base);
2629 high = array_ref_up_bound (base);
2631 /* The case of nonconstant bounds could be handled, but it would be
2633 if (TREE_CODE (low) != INTEGER_CST
2635 || TREE_CODE (high) != INTEGER_CST)
2637 sign = tree_int_cst_sign_bit (step);
2638 type = TREE_TYPE (step);
2640 /* The array of length 1 at the end of a structure most likely extends
2641 beyond its bounds. */
2643 && operand_equal_p (low, high, 0))
2646 /* In case the relevant bound of the array does not fit in type, or
2647 it does, but bound + step (in type) still belongs into the range of the
2648 array, the index may wrap and still stay within the range of the array
2649 (consider e.g. if the array is indexed by the full range of
2652 To make things simpler, we require both bounds to fit into type, although
2653 there are cases where this would not be strictly necessary. */
2654 if (!int_fits_type_p (high, type)
2655 || !int_fits_type_p (low, type))
2657 low = fold_convert (type, low);
2658 high = fold_convert (type, high);
2661 next = fold_binary (PLUS_EXPR, type, low, step);
2663 next = fold_binary (PLUS_EXPR, type, high, step);
2665 if (tree_int_cst_compare (low, next) <= 0
2666 && tree_int_cst_compare (next, high) <= 0)
2669 record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true, upper);
2673 /* Determine information about number of iterations a LOOP from the bounds
2674 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
2675 STMT is guaranteed to be executed in every iteration of LOOP.*/
2678 infer_loop_bounds_from_ref (struct loop *loop, tree stmt, tree ref,
2681 struct ilb_data data;
2685 data.reliable = reliable;
2686 for_each_index (&ref, idx_infer_loop_bounds, &data);
2689 /* Determine information about number of iterations of a LOOP from the way
2690 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
2691 executed in every iteration of LOOP. */
2694 infer_loop_bounds_from_array (struct loop *loop, tree stmt, bool reliable)
2698 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
2700 tree op0 = GIMPLE_STMT_OPERAND (stmt, 0);
2701 tree op1 = GIMPLE_STMT_OPERAND (stmt, 1);
2703 /* For each memory access, analyze its access function
2704 and record a bound on the loop iteration domain. */
2705 if (REFERENCE_CLASS_P (op0))
2706 infer_loop_bounds_from_ref (loop, stmt, op0, reliable);
2708 if (REFERENCE_CLASS_P (op1))
2709 infer_loop_bounds_from_ref (loop, stmt, op1, reliable);
2713 call = get_call_expr_in (stmt);
2717 call_expr_arg_iterator iter;
2719 FOR_EACH_CALL_EXPR_ARG (arg, iter, call)
2720 if (REFERENCE_CLASS_P (arg))
2721 infer_loop_bounds_from_ref (loop, stmt, arg, reliable);
2725 /* Determine information about number of iterations of a LOOP from the fact
2726 that signed arithmetics in STMT does not overflow. */
2729 infer_loop_bounds_from_signedness (struct loop *loop, tree stmt)
2731 tree def, base, step, scev, type, low, high;
2733 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
2736 def = GIMPLE_STMT_OPERAND (stmt, 0);
2738 if (TREE_CODE (def) != SSA_NAME)
2741 type = TREE_TYPE (def);
2742 if (!INTEGRAL_TYPE_P (type)
2743 || !TYPE_OVERFLOW_UNDEFINED (type))
2746 scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
2747 if (chrec_contains_undetermined (scev))
2750 base = initial_condition_in_loop_num (scev, loop->num);
2751 step = evolution_part_in_loop_num (scev, loop->num);
2754 || TREE_CODE (step) != INTEGER_CST
2755 || tree_contains_chrecs (base, NULL)
2756 || chrec_contains_symbols_defined_in_loop (base, loop->num))
2759 low = lower_bound_in_type (type, type);
2760 high = upper_bound_in_type (type, type);
2762 record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
2765 /* The following analyzers are extracting informations on the bounds
2766 of LOOP from the following undefined behaviors:
2768 - data references should not access elements over the statically
2771 - signed variables should not overflow when flag_wrapv is not set.
2775 infer_loop_bounds_from_undefined (struct loop *loop)
2779 block_stmt_iterator bsi;
2783 bbs = get_loop_body (loop);
2785 for (i = 0; i < loop->num_nodes; i++)
2789 /* If BB is not executed in each iteration of the loop, we cannot
2790 use the operations in it to infer reliable upper bound on the
2791 # of iterations of the loop. However, we can use it as a guess. */
2792 reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb);
2794 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
2796 tree stmt = bsi_stmt (bsi);
2798 infer_loop_bounds_from_array (loop, stmt, reliable);
2801 infer_loop_bounds_from_signedness (loop, stmt);
2809 /* Converts VAL to double_int. */
2812 gcov_type_to_double_int (gcov_type val)
2816 ret.low = (unsigned HOST_WIDE_INT) val;
2817 /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by
2818 the size of type. */
2819 val >>= HOST_BITS_PER_WIDE_INT - 1;
2821 ret.high = (unsigned HOST_WIDE_INT) val;
2826 /* Records estimates on numbers of iterations of LOOP. */
2829 estimate_numbers_of_iterations_loop (struct loop *loop)
2831 VEC (edge, heap) *exits;
2834 struct tree_niter_desc niter_desc;
2838 /* Give up if we already have tried to compute an estimation. */
2839 if (loop->estimate_state != EST_NOT_COMPUTED)
2841 loop->estimate_state = EST_AVAILABLE;
2842 loop->any_upper_bound = false;
2843 loop->any_estimate = false;
2845 exits = get_loop_exit_edges (loop);
2846 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
2848 if (!number_of_iterations_exit (loop, ex, &niter_desc, false))
2851 niter = niter_desc.niter;
2852 type = TREE_TYPE (niter);
2853 if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST)
2854 niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
2855 build_int_cst (type, 0),
2857 record_estimate (loop, niter, niter_desc.max,
2858 last_stmt (ex->src),
2861 VEC_free (edge, heap, exits);
2863 infer_loop_bounds_from_undefined (loop);
2865 /* If we have a measured profile, use it to estimate the number of
2867 if (loop->header->count != 0)
2869 gcov_type nit = expected_loop_iterations_unbounded (loop) + 1;
2870 bound = gcov_type_to_double_int (nit);
2871 record_niter_bound (loop, bound, true, false);
2874 /* If an upper bound is smaller than the realistic estimate of the
2875 number of iterations, use the upper bound instead. */
2876 if (loop->any_upper_bound
2877 && loop->any_estimate
2878 && double_int_ucmp (loop->nb_iterations_upper_bound,
2879 loop->nb_iterations_estimate) < 0)
2880 loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
2883 /* Records estimates on numbers of iterations of loops. */
2886 estimate_numbers_of_iterations (void)
2891 /* We don't want to issue signed overflow warnings while getting
2892 loop iteration estimates. */
2893 fold_defer_overflow_warnings ();
2895 FOR_EACH_LOOP (li, loop, 0)
2897 estimate_numbers_of_iterations_loop (loop);
2900 fold_undefer_and_ignore_overflow_warnings ();
2903 /* Returns true if statement S1 dominates statement S2. */
2906 stmt_dominates_stmt_p (tree s1, tree s2)
2908 basic_block bb1 = bb_for_stmt (s1), bb2 = bb_for_stmt (s2);
2916 block_stmt_iterator bsi;
2918 for (bsi = bsi_start (bb1); bsi_stmt (bsi) != s2; bsi_next (&bsi))
2919 if (bsi_stmt (bsi) == s1)
2925 return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
2928 /* Returns true when we can prove that the number of executions of
2929 STMT in the loop is at most NITER, according to the bound on
2930 the number of executions of the statement NITER_BOUND->stmt recorded in
2931 NITER_BOUND. If STMT is NULL, we must prove this bound for all
2932 statements in the loop. */
2935 n_of_executions_at_most (tree stmt,
2936 struct nb_iter_bound *niter_bound,
2939 double_int bound = niter_bound->bound;
2940 tree nit_type = TREE_TYPE (niter), e;
2943 gcc_assert (TYPE_UNSIGNED (nit_type));
2945 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
2946 the number of iterations is small. */
2947 if (!double_int_fits_to_tree_p (nit_type, bound))
2950 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
2951 times. This means that:
2953 -- if NITER_BOUND->is_exit is true, then everything before
2954 NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
2955 times, and everything after it at most NITER_BOUND->bound times.
2957 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
2958 is executed, then NITER_BOUND->stmt is executed as well in the same
2959 iteration (we conclude that if both statements belong to the same
2960 basic block, or if STMT is after NITER_BOUND->stmt), then STMT
2961 is executed at most NITER_BOUND->bound + 1 times. Otherwise STMT is
2962 executed at most NITER_BOUND->bound + 2 times. */
2964 if (niter_bound->is_exit)
2967 && stmt != niter_bound->stmt
2968 && stmt_dominates_stmt_p (niter_bound->stmt, stmt))
2976 || (bb_for_stmt (stmt) != bb_for_stmt (niter_bound->stmt)
2977 && !stmt_dominates_stmt_p (niter_bound->stmt, stmt)))
2979 bound = double_int_add (bound, double_int_one);
2980 if (double_int_zero_p (bound)
2981 || !double_int_fits_to_tree_p (nit_type, bound))
2987 e = fold_binary (cmp, boolean_type_node,
2988 niter, double_int_to_tree (nit_type, bound));
2989 return e && integer_nonzerop (e);
2992 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
2995 nowrap_type_p (tree type)
2997 if (INTEGRAL_TYPE_P (type)
2998 && TYPE_OVERFLOW_UNDEFINED (type))
3001 if (POINTER_TYPE_P (type))
3007 /* Return false only when the induction variable BASE + STEP * I is
3008 known to not overflow: i.e. when the number of iterations is small
3009 enough with respect to the step and initial condition in order to
3010 keep the evolution confined in TYPEs bounds. Return true when the
3011 iv is known to overflow or when the property is not computable.
3013 USE_OVERFLOW_SEMANTICS is true if this function should assume that
3014 the rules for overflow of the given language apply (e.g., that signed
3015 arithmetics in C does not overflow). */
3018 scev_probably_wraps_p (tree base, tree step,
3019 tree at_stmt, struct loop *loop,
3020 bool use_overflow_semantics)
3022 struct nb_iter_bound *bound;
3023 tree delta, step_abs;
3024 tree unsigned_type, valid_niter;
3025 tree type = TREE_TYPE (step);
3027 /* FIXME: We really need something like
3028 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
3030 We used to test for the following situation that frequently appears
3031 during address arithmetics:
3033 D.1621_13 = (long unsigned intD.4) D.1620_12;
3034 D.1622_14 = D.1621_13 * 8;
3035 D.1623_15 = (doubleD.29 *) D.1622_14;
3037 And derived that the sequence corresponding to D_14
3038 can be proved to not wrap because it is used for computing a
3039 memory access; however, this is not really the case -- for example,
3040 if D_12 = (unsigned char) [254,+,1], then D_14 has values
3041 2032, 2040, 0, 8, ..., but the code is still legal. */
3043 if (chrec_contains_undetermined (base)
3044 || chrec_contains_undetermined (step)
3045 || TREE_CODE (step) != INTEGER_CST)
3048 if (integer_zerop (step))
3051 /* If we can use the fact that signed and pointer arithmetics does not
3052 wrap, we are done. */
3053 if (use_overflow_semantics && nowrap_type_p (type))
3056 /* Don't issue signed overflow warnings. */
3057 fold_defer_overflow_warnings ();
3059 /* Otherwise, compute the number of iterations before we reach the
3060 bound of the type, and verify that the loop is exited before this
3062 unsigned_type = unsigned_type_for (type);
3063 base = fold_convert (unsigned_type, base);
3065 if (tree_int_cst_sign_bit (step))
3067 tree extreme = fold_convert (unsigned_type,
3068 lower_bound_in_type (type, type));
3069 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
3070 step_abs = fold_build1 (NEGATE_EXPR, unsigned_type,
3071 fold_convert (unsigned_type, step));
3075 tree extreme = fold_convert (unsigned_type,
3076 upper_bound_in_type (type, type));
3077 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
3078 step_abs = fold_convert (unsigned_type, step);
3081 valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
3083 estimate_numbers_of_iterations_loop (loop);
3084 for (bound = loop->bounds; bound; bound = bound->next)
3086 if (n_of_executions_at_most (at_stmt, bound, valid_niter))
3088 fold_undefer_and_ignore_overflow_warnings ();
3093 fold_undefer_and_ignore_overflow_warnings ();
3095 /* At this point we still don't have a proof that the iv does not
3096 overflow: give up. */
3100 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
3103 free_numbers_of_iterations_estimates_loop (struct loop *loop)
3105 struct nb_iter_bound *bound, *next;
3107 loop->nb_iterations = NULL;
3108 loop->estimate_state = EST_NOT_COMPUTED;
3109 for (bound = loop->bounds; bound; bound = next)
3115 loop->bounds = NULL;
3118 /* Frees the information on upper bounds on numbers of iterations of loops. */
3121 free_numbers_of_iterations_estimates (void)
3126 FOR_EACH_LOOP (li, loop, 0)
3128 free_numbers_of_iterations_estimates_loop (loop);
3132 /* Substitute value VAL for ssa name NAME inside expressions held
3136 substitute_in_loop_info (struct loop *loop, tree name, tree val)
3138 loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);