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 this exit is taken. 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. EXIT_MUST_BE_TAKEN 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 exit_must_be_taken
,
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
);
642 if (!exit_must_be_taken
)
644 /* If we cannot assume that the exit is taken eventually, 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. EXIT_MUST_BE_TAKEN is
668 true if we know that the exit must be taken eventually. */
671 number_of_iterations_lt_to_ne (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
672 struct tree_niter_desc
*niter
,
673 tree
*delta
, tree step
,
674 bool exit_must_be_taken
, bounds
*bnds
)
676 tree niter_type
= TREE_TYPE (step
);
677 tree mod
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, *delta
, step
);
680 tree assumption
= boolean_true_node
, bound
, noloop
;
681 bool ret
= false, fv_comp_no_overflow
;
683 if (POINTER_TYPE_P (type
))
686 if (TREE_CODE (mod
) != INTEGER_CST
)
688 if (integer_nonzerop (mod
))
689 mod
= fold_build2 (MINUS_EXPR
, niter_type
, step
, mod
);
690 tmod
= fold_convert (type1
, mod
);
693 mpz_set_double_int (mmod
, tree_to_double_int (mod
), true);
694 mpz_neg (mmod
, mmod
);
696 /* If the induction variable does not overflow and the exit is taken,
697 then the computation of the final value does not overflow. This is
698 also obviously the case if the new final value is equal to the
699 current one. Finally, we postulate this for pointer type variables,
700 as the code cannot rely on the object to that the pointer points being
701 placed at the end of the address space (and more pragmatically,
702 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
703 if (integer_zerop (mod
) || POINTER_TYPE_P (type
))
704 fv_comp_no_overflow
= true;
705 else if (!exit_must_be_taken
)
706 fv_comp_no_overflow
= false;
708 fv_comp_no_overflow
=
709 (iv0
->no_overflow
&& integer_nonzerop (iv0
->step
))
710 || (iv1
->no_overflow
&& integer_nonzerop (iv1
->step
));
712 if (integer_nonzerop (iv0
->step
))
714 /* The final value of the iv is iv1->base + MOD, assuming that this
715 computation does not overflow, and that
716 iv0->base <= iv1->base + MOD. */
717 if (!fv_comp_no_overflow
)
719 bound
= fold_build2 (MINUS_EXPR
, type1
,
720 TYPE_MAX_VALUE (type1
), tmod
);
721 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
723 if (integer_zerop (assumption
))
726 if (mpz_cmp (mmod
, bnds
->below
) < 0)
727 noloop
= boolean_false_node
;
728 else if (POINTER_TYPE_P (type
))
729 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
731 fold_build2 (POINTER_PLUS_EXPR
, type
,
734 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
736 fold_build2 (PLUS_EXPR
, type1
,
741 /* The final value of the iv is iv0->base - MOD, assuming that this
742 computation does not overflow, and that
743 iv0->base - MOD <= iv1->base. */
744 if (!fv_comp_no_overflow
)
746 bound
= fold_build2 (PLUS_EXPR
, type1
,
747 TYPE_MIN_VALUE (type1
), tmod
);
748 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
750 if (integer_zerop (assumption
))
753 if (mpz_cmp (mmod
, bnds
->below
) < 0)
754 noloop
= boolean_false_node
;
755 else if (POINTER_TYPE_P (type
))
756 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
757 fold_build2 (POINTER_PLUS_EXPR
, type
,
759 fold_build1 (NEGATE_EXPR
,
763 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
764 fold_build2 (MINUS_EXPR
, type1
,
769 if (!integer_nonzerop (assumption
))
770 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
773 if (!integer_zerop (noloop
))
774 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
777 bounds_add (bnds
, tree_to_double_int (mod
), type
);
778 *delta
= fold_build2 (PLUS_EXPR
, niter_type
, *delta
, mod
);
786 /* Add assertions to NITER that ensure that the control variable of the loop
787 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
788 are TYPE. Returns false if we can prove that there is an overflow, true
789 otherwise. STEP is the absolute value of the step. */
792 assert_no_overflow_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
793 struct tree_niter_desc
*niter
, tree step
)
795 tree bound
, d
, assumption
, diff
;
796 tree niter_type
= TREE_TYPE (step
);
798 if (integer_nonzerop (iv0
->step
))
800 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
801 if (iv0
->no_overflow
)
804 /* If iv0->base is a constant, we can determine the last value before
805 overflow precisely; otherwise we conservatively assume
808 if (TREE_CODE (iv0
->base
) == INTEGER_CST
)
810 d
= fold_build2 (MINUS_EXPR
, niter_type
,
811 fold_convert (niter_type
, TYPE_MAX_VALUE (type
)),
812 fold_convert (niter_type
, iv0
->base
));
813 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
816 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
817 build_int_cst (niter_type
, 1));
818 bound
= fold_build2 (MINUS_EXPR
, type
,
819 TYPE_MAX_VALUE (type
), fold_convert (type
, diff
));
820 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
825 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
826 if (iv1
->no_overflow
)
829 if (TREE_CODE (iv1
->base
) == INTEGER_CST
)
831 d
= fold_build2 (MINUS_EXPR
, niter_type
,
832 fold_convert (niter_type
, iv1
->base
),
833 fold_convert (niter_type
, TYPE_MIN_VALUE (type
)));
834 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
837 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
838 build_int_cst (niter_type
, 1));
839 bound
= fold_build2 (PLUS_EXPR
, type
,
840 TYPE_MIN_VALUE (type
), fold_convert (type
, diff
));
841 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
845 if (integer_zerop (assumption
))
847 if (!integer_nonzerop (assumption
))
848 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
849 niter
->assumptions
, assumption
);
851 iv0
->no_overflow
= true;
852 iv1
->no_overflow
= true;
856 /* Add an assumption to NITER that a loop whose ending condition
857 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
858 bounds the value of IV1->base - IV0->base. */
861 assert_loop_rolls_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
862 struct tree_niter_desc
*niter
, bounds
*bnds
)
864 tree assumption
= boolean_true_node
, bound
, diff
;
865 tree mbz
, mbzl
, mbzr
, type1
;
866 bool rolls_p
, no_overflow_p
;
870 /* We are going to compute the number of iterations as
871 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
872 variant of TYPE. This formula only works if
874 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
876 (where MAX is the maximum value of the unsigned variant of TYPE, and
877 the computations in this formula are performed in full precision
880 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
881 we have a condition of form iv0->base - step < iv1->base before the loop,
882 and for loops iv0->base < iv1->base - step * i the condition
883 iv0->base < iv1->base + step, due to loop header copying, which enable us
884 to prove the lower bound.
886 The upper bound is more complicated. Unless the expressions for initial
887 and final value themselves contain enough information, we usually cannot
888 derive it from the context. */
890 /* First check whether the answer does not follow from the bounds we gathered
892 if (integer_nonzerop (iv0
->step
))
893 dstep
= tree_to_double_int (iv0
->step
);
896 dstep
= double_int_sext (tree_to_double_int (iv1
->step
),
897 TYPE_PRECISION (type
));
898 dstep
= double_int_neg (dstep
);
902 mpz_set_double_int (mstep
, dstep
, true);
903 mpz_neg (mstep
, mstep
);
904 mpz_add_ui (mstep
, mstep
, 1);
906 rolls_p
= mpz_cmp (mstep
, bnds
->below
) <= 0;
909 mpz_set_double_int (max
, double_int_mask (TYPE_PRECISION (type
)), true);
910 mpz_add (max
, max
, mstep
);
911 no_overflow_p
= (mpz_cmp (bnds
->up
, max
) <= 0
912 /* For pointers, only values lying inside a single object
913 can be compared or manipulated by pointer arithmetics.
914 Gcc in general does not allow or handle objects larger
915 than half of the address space, hence the upper bound
916 is satisfied for pointers. */
917 || POINTER_TYPE_P (type
));
921 if (rolls_p
&& no_overflow_p
)
925 if (POINTER_TYPE_P (type
))
928 /* Now the hard part; we must formulate the assumption(s) as expressions, and
929 we must be careful not to introduce overflow. */
931 if (integer_nonzerop (iv0
->step
))
933 diff
= fold_build2 (MINUS_EXPR
, type1
,
934 iv0
->step
, build_int_cst (type1
, 1));
936 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
937 0 address never belongs to any object, we can assume this for
939 if (!POINTER_TYPE_P (type
))
941 bound
= fold_build2 (PLUS_EXPR
, type1
,
942 TYPE_MIN_VALUE (type
), diff
);
943 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
947 /* And then we can compute iv0->base - diff, and compare it with
949 mbzl
= fold_build2 (MINUS_EXPR
, type1
,
950 fold_convert (type1
, iv0
->base
), diff
);
951 mbzr
= fold_convert (type1
, iv1
->base
);
955 diff
= fold_build2 (PLUS_EXPR
, type1
,
956 iv1
->step
, build_int_cst (type1
, 1));
958 if (!POINTER_TYPE_P (type
))
960 bound
= fold_build2 (PLUS_EXPR
, type1
,
961 TYPE_MAX_VALUE (type
), diff
);
962 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
966 mbzl
= fold_convert (type1
, iv0
->base
);
967 mbzr
= fold_build2 (MINUS_EXPR
, type1
,
968 fold_convert (type1
, iv1
->base
), diff
);
971 if (!integer_nonzerop (assumption
))
972 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
973 niter
->assumptions
, assumption
);
976 mbz
= fold_build2 (GT_EXPR
, boolean_type_node
, mbzl
, mbzr
);
977 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
978 niter
->may_be_zero
, mbz
);
982 /* Determines number of iterations of loop whose ending condition
983 is IV0 < IV1. TYPE is the type of the iv. The number of
984 iterations is stored to NITER. BNDS bounds the difference
985 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
986 that the exit must be taken eventually. */
989 number_of_iterations_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
990 struct tree_niter_desc
*niter
,
991 bool exit_must_be_taken
, bounds
*bnds
)
993 tree niter_type
= unsigned_type_for (type
);
997 if (integer_nonzerop (iv0
->step
))
999 niter
->control
= *iv0
;
1000 niter
->cmp
= LT_EXPR
;
1001 niter
->bound
= iv1
->base
;
1005 niter
->control
= *iv1
;
1006 niter
->cmp
= GT_EXPR
;
1007 niter
->bound
= iv0
->base
;
1010 delta
= fold_build2 (MINUS_EXPR
, niter_type
,
1011 fold_convert (niter_type
, iv1
->base
),
1012 fold_convert (niter_type
, iv0
->base
));
1014 /* First handle the special case that the step is +-1. */
1015 if ((integer_onep (iv0
->step
) && integer_zerop (iv1
->step
))
1016 || (integer_all_onesp (iv1
->step
) && integer_zerop (iv0
->step
)))
1018 /* for (i = iv0->base; i < iv1->base; i++)
1022 for (i = iv1->base; i > iv0->base; i--).
1024 In both cases # of iterations is iv1->base - iv0->base, assuming that
1025 iv1->base >= iv0->base.
1027 First try to derive a lower bound on the value of
1028 iv1->base - iv0->base, computed in full precision. If the difference
1029 is nonnegative, we are done, otherwise we must record the
1032 if (mpz_sgn (bnds
->below
) < 0)
1033 niter
->may_be_zero
= fold_build2 (LT_EXPR
, boolean_type_node
,
1034 iv1
->base
, iv0
->base
);
1035 niter
->niter
= delta
;
1036 niter
->max
= mpz_get_double_int (niter_type
, bnds
->up
, false);
1040 if (integer_nonzerop (iv0
->step
))
1041 step
= fold_convert (niter_type
, iv0
->step
);
1043 step
= fold_convert (niter_type
,
1044 fold_build1 (NEGATE_EXPR
, type
, iv1
->step
));
1046 /* If we can determine the final value of the control iv exactly, we can
1047 transform the condition to != comparison. In particular, this will be
1048 the case if DELTA is constant. */
1049 if (number_of_iterations_lt_to_ne (type
, iv0
, iv1
, niter
, &delta
, step
,
1050 exit_must_be_taken
, bnds
))
1054 zps
.base
= build_int_cst (niter_type
, 0);
1056 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1057 zps does not overflow. */
1058 zps
.no_overflow
= true;
1060 return number_of_iterations_ne (type
, &zps
, delta
, niter
, true, bnds
);
1063 /* Make sure that the control iv does not overflow. */
1064 if (!assert_no_overflow_lt (type
, iv0
, iv1
, niter
, step
))
1067 /* We determine the number of iterations as (delta + step - 1) / step. For
1068 this to work, we must know that iv1->base >= iv0->base - step + 1,
1069 otherwise the loop does not roll. */
1070 assert_loop_rolls_lt (type
, iv0
, iv1
, niter
, bnds
);
1072 s
= fold_build2 (MINUS_EXPR
, niter_type
,
1073 step
, build_int_cst (niter_type
, 1));
1074 delta
= fold_build2 (PLUS_EXPR
, niter_type
, delta
, s
);
1075 niter
->niter
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, delta
, step
);
1079 mpz_set_double_int (mstep
, tree_to_double_int (step
), true);
1080 mpz_add (tmp
, bnds
->up
, mstep
);
1081 mpz_sub_ui (tmp
, tmp
, 1);
1082 mpz_fdiv_q (tmp
, tmp
, mstep
);
1083 niter
->max
= mpz_get_double_int (niter_type
, tmp
, false);
1090 /* Determines number of iterations of loop whose ending condition
1091 is IV0 <= IV1. TYPE is the type of the iv. The number of
1092 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
1093 we know that this condition must eventually become false (we derived this
1094 earlier, and possibly set NITER->assumptions to make sure this
1095 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1098 number_of_iterations_le (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1099 struct tree_niter_desc
*niter
, bool exit_must_be_taken
,
1104 if (POINTER_TYPE_P (type
))
1107 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1108 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1109 value of the type. This we must know anyway, since if it is
1110 equal to this value, the loop rolls forever. We do not check
1111 this condition for pointer type ivs, as the code cannot rely on
1112 the object to that the pointer points being placed at the end of
1113 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1114 not defined for pointers). */
1116 if (!exit_must_be_taken
&& !POINTER_TYPE_P (type
))
1118 if (integer_nonzerop (iv0
->step
))
1119 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1120 iv1
->base
, TYPE_MAX_VALUE (type
));
1122 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1123 iv0
->base
, TYPE_MIN_VALUE (type
));
1125 if (integer_zerop (assumption
))
1127 if (!integer_nonzerop (assumption
))
1128 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1129 niter
->assumptions
, assumption
);
1132 if (integer_nonzerop (iv0
->step
))
1134 if (POINTER_TYPE_P (type
))
1135 iv1
->base
= fold_build2 (POINTER_PLUS_EXPR
, type
, iv1
->base
,
1136 build_int_cst (type1
, 1));
1138 iv1
->base
= fold_build2 (PLUS_EXPR
, type1
, iv1
->base
,
1139 build_int_cst (type1
, 1));
1141 else if (POINTER_TYPE_P (type
))
1142 iv0
->base
= fold_build2 (POINTER_PLUS_EXPR
, type
, iv0
->base
,
1143 fold_build1 (NEGATE_EXPR
, type1
,
1144 build_int_cst (type1
, 1)));
1146 iv0
->base
= fold_build2 (MINUS_EXPR
, type1
,
1147 iv0
->base
, build_int_cst (type1
, 1));
1149 bounds_add (bnds
, double_int_one
, type1
);
1151 return number_of_iterations_lt (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1155 /* Dumps description of affine induction variable IV to FILE. */
1158 dump_affine_iv (FILE *file
, affine_iv
*iv
)
1160 if (!integer_zerop (iv
->step
))
1161 fprintf (file
, "[");
1163 print_generic_expr (dump_file
, iv
->base
, TDF_SLIM
);
1165 if (!integer_zerop (iv
->step
))
1167 fprintf (file
, ", + , ");
1168 print_generic_expr (dump_file
, iv
->step
, TDF_SLIM
);
1169 fprintf (file
, "]%s", iv
->no_overflow
? "(no_overflow)" : "");
1173 /* Determine the number of iterations according to condition (for staying
1174 inside loop) which compares two induction variables using comparison
1175 operator CODE. The induction variable on left side of the comparison
1176 is IV0, the right-hand side is IV1. Both induction variables must have
1177 type TYPE, which must be an integer or pointer type. The steps of the
1178 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1180 LOOP is the loop whose number of iterations we are determining.
1182 ONLY_EXIT is true if we are sure this is the only way the loop could be
1183 exited (including possibly non-returning function calls, exceptions, etc.)
1184 -- in this case we can use the information whether the control induction
1185 variables can overflow or not in a more efficient way.
1187 The results (number of iterations and assumptions as described in
1188 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
1189 Returns false if it fails to determine number of iterations, true if it
1190 was determined (possibly with some assumptions). */
1193 number_of_iterations_cond (struct loop
*loop
,
1194 tree type
, affine_iv
*iv0
, enum tree_code code
,
1195 affine_iv
*iv1
, struct tree_niter_desc
*niter
,
1198 bool exit_must_be_taken
= false, ret
;
1201 /* The meaning of these assumptions is this:
1203 then the rest of information does not have to be valid
1204 if may_be_zero then the loop does not roll, even if
1206 niter
->assumptions
= boolean_true_node
;
1207 niter
->may_be_zero
= boolean_false_node
;
1208 niter
->niter
= NULL_TREE
;
1209 niter
->max
= double_int_zero
;
1211 niter
->bound
= NULL_TREE
;
1212 niter
->cmp
= ERROR_MARK
;
1214 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1215 the control variable is on lhs. */
1216 if (code
== GE_EXPR
|| code
== GT_EXPR
1217 || (code
== NE_EXPR
&& integer_zerop (iv0
->step
)))
1220 code
= swap_tree_comparison (code
);
1223 if (POINTER_TYPE_P (type
))
1225 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1226 to the same object. If they do, the control variable cannot wrap
1227 (as wrap around the bounds of memory will never return a pointer
1228 that would be guaranteed to point to the same object, even if we
1229 avoid undefined behavior by casting to size_t and back). */
1230 iv0
->no_overflow
= true;
1231 iv1
->no_overflow
= true;
1234 /* If the control induction variable does not overflow and the only exit
1235 from the loop is the one that we analyze, we know it must be taken
1239 if (!integer_zerop (iv0
->step
) && iv0
->no_overflow
)
1240 exit_must_be_taken
= true;
1241 else if (!integer_zerop (iv1
->step
) && iv1
->no_overflow
)
1242 exit_must_be_taken
= true;
1245 /* We can handle the case when neither of the sides of the comparison is
1246 invariant, provided that the test is NE_EXPR. This rarely occurs in
1247 practice, but it is simple enough to manage. */
1248 if (!integer_zerop (iv0
->step
) && !integer_zerop (iv1
->step
))
1250 if (code
!= NE_EXPR
)
1253 iv0
->step
= fold_binary_to_constant (MINUS_EXPR
, type
,
1254 iv0
->step
, iv1
->step
);
1255 iv0
->no_overflow
= false;
1256 iv1
->step
= build_int_cst (type
, 0);
1257 iv1
->no_overflow
= true;
1260 /* If the result of the comparison is a constant, the loop is weird. More
1261 precise handling would be possible, but the situation is not common enough
1262 to waste time on it. */
1263 if (integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
))
1266 /* Ignore loops of while (i-- < 10) type. */
1267 if (code
!= NE_EXPR
)
1269 if (iv0
->step
&& tree_int_cst_sign_bit (iv0
->step
))
1272 if (!integer_zerop (iv1
->step
) && !tree_int_cst_sign_bit (iv1
->step
))
1276 /* If the loop exits immediately, there is nothing to do. */
1277 if (integer_zerop (fold_build2 (code
, boolean_type_node
, iv0
->base
, iv1
->base
)))
1279 niter
->niter
= build_int_cst (unsigned_type_for (type
), 0);
1280 niter
->max
= double_int_zero
;
1284 /* OK, now we know we have a senseful loop. Handle several cases, depending
1285 on what comparison operator is used. */
1286 bound_difference (loop
, iv1
->base
, iv0
->base
, &bnds
);
1288 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1291 "Analyzing # of iterations of loop %d\n", loop
->num
);
1293 fprintf (dump_file
, " exit condition ");
1294 dump_affine_iv (dump_file
, iv0
);
1295 fprintf (dump_file
, " %s ",
1296 code
== NE_EXPR
? "!="
1297 : code
== LT_EXPR
? "<"
1299 dump_affine_iv (dump_file
, iv1
);
1300 fprintf (dump_file
, "\n");
1302 fprintf (dump_file
, " bounds on difference of bases: ");
1303 mpz_out_str (dump_file
, 10, bnds
.below
);
1304 fprintf (dump_file
, " ... ");
1305 mpz_out_str (dump_file
, 10, bnds
.up
);
1306 fprintf (dump_file
, "\n");
1312 gcc_assert (integer_zerop (iv1
->step
));
1313 ret
= number_of_iterations_ne (type
, iv0
, iv1
->base
, niter
,
1314 exit_must_be_taken
, &bnds
);
1318 ret
= number_of_iterations_lt (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1323 ret
= number_of_iterations_le (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1331 mpz_clear (bnds
.up
);
1332 mpz_clear (bnds
.below
);
1334 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1338 fprintf (dump_file
, " result:\n");
1339 if (!integer_nonzerop (niter
->assumptions
))
1341 fprintf (dump_file
, " under assumptions ");
1342 print_generic_expr (dump_file
, niter
->assumptions
, TDF_SLIM
);
1343 fprintf (dump_file
, "\n");
1346 if (!integer_zerop (niter
->may_be_zero
))
1348 fprintf (dump_file
, " zero if ");
1349 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
1350 fprintf (dump_file
, "\n");
1353 fprintf (dump_file
, " # of iterations ");
1354 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
1355 fprintf (dump_file
, ", bounded by ");
1356 dump_double_int (dump_file
, niter
->max
, true);
1357 fprintf (dump_file
, "\n");
1360 fprintf (dump_file
, " failed\n\n");
1365 /* Substitute NEW for OLD in EXPR and fold the result. */
1368 simplify_replace_tree (tree expr
, tree old
, tree new_tree
)
1371 tree ret
= NULL_TREE
, e
, se
;
1377 || operand_equal_p (expr
, old
, 0))
1378 return unshare_expr (new_tree
);
1383 n
= TREE_OPERAND_LENGTH (expr
);
1384 for (i
= 0; i
< n
; i
++)
1386 e
= TREE_OPERAND (expr
, i
);
1387 se
= simplify_replace_tree (e
, old
, new_tree
);
1392 ret
= copy_node (expr
);
1394 TREE_OPERAND (ret
, i
) = se
;
1397 return (ret
? fold (ret
) : expr
);
1400 /* Expand definitions of ssa names in EXPR as long as they are simple
1401 enough, and return the new expression. */
1404 expand_simple_operations (tree expr
)
1407 tree ret
= NULL_TREE
, e
, ee
, e1
;
1408 enum tree_code code
;
1411 if (expr
== NULL_TREE
)
1414 if (is_gimple_min_invariant (expr
))
1417 code
= TREE_CODE (expr
);
1418 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
1420 n
= TREE_OPERAND_LENGTH (expr
);
1421 for (i
= 0; i
< n
; i
++)
1423 e
= TREE_OPERAND (expr
, i
);
1424 ee
= expand_simple_operations (e
);
1429 ret
= copy_node (expr
);
1431 TREE_OPERAND (ret
, i
) = ee
;
1437 fold_defer_overflow_warnings ();
1439 fold_undefer_and_ignore_overflow_warnings ();
1443 if (TREE_CODE (expr
) != SSA_NAME
)
1446 stmt
= SSA_NAME_DEF_STMT (expr
);
1447 if (gimple_code (stmt
) == GIMPLE_PHI
)
1449 basic_block src
, dest
;
1451 if (gimple_phi_num_args (stmt
) != 1)
1453 e
= PHI_ARG_DEF (stmt
, 0);
1455 /* Avoid propagating through loop exit phi nodes, which
1456 could break loop-closed SSA form restrictions. */
1457 dest
= gimple_bb (stmt
);
1458 src
= single_pred (dest
);
1459 if (TREE_CODE (e
) == SSA_NAME
1460 && src
->loop_father
!= dest
->loop_father
)
1463 return expand_simple_operations (e
);
1465 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1468 e
= gimple_assign_rhs1 (stmt
);
1469 code
= gimple_assign_rhs_code (stmt
);
1470 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1472 if (is_gimple_min_invariant (e
))
1475 if (code
== SSA_NAME
)
1476 return expand_simple_operations (e
);
1484 /* Casts are simple. */
1485 ee
= expand_simple_operations (e
);
1486 return fold_build1 (code
, TREE_TYPE (expr
), ee
);
1490 case POINTER_PLUS_EXPR
:
1491 /* And increments and decrements by a constant are simple. */
1492 e1
= gimple_assign_rhs2 (stmt
);
1493 if (!is_gimple_min_invariant (e1
))
1496 ee
= expand_simple_operations (e
);
1497 return fold_build2 (code
, TREE_TYPE (expr
), ee
, e1
);
1504 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1505 expression (or EXPR unchanged, if no simplification was possible). */
1508 tree_simplify_using_condition_1 (tree cond
, tree expr
)
1511 tree e
, te
, e0
, e1
, e2
, notcond
;
1512 enum tree_code code
= TREE_CODE (expr
);
1514 if (code
== INTEGER_CST
)
1517 if (code
== TRUTH_OR_EXPR
1518 || code
== TRUTH_AND_EXPR
1519 || code
== COND_EXPR
)
1523 e0
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 0));
1524 if (TREE_OPERAND (expr
, 0) != e0
)
1527 e1
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 1));
1528 if (TREE_OPERAND (expr
, 1) != e1
)
1531 if (code
== COND_EXPR
)
1533 e2
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 2));
1534 if (TREE_OPERAND (expr
, 2) != e2
)
1542 if (code
== COND_EXPR
)
1543 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1545 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1551 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
1552 propagation, and vice versa. Fold does not handle this, since it is
1553 considered too expensive. */
1554 if (TREE_CODE (cond
) == EQ_EXPR
)
1556 e0
= TREE_OPERAND (cond
, 0);
1557 e1
= TREE_OPERAND (cond
, 1);
1559 /* We know that e0 == e1. Check whether we cannot simplify expr
1561 e
= simplify_replace_tree (expr
, e0
, e1
);
1562 if (integer_zerop (e
) || integer_nonzerop (e
))
1565 e
= simplify_replace_tree (expr
, e1
, e0
);
1566 if (integer_zerop (e
) || integer_nonzerop (e
))
1569 if (TREE_CODE (expr
) == EQ_EXPR
)
1571 e0
= TREE_OPERAND (expr
, 0);
1572 e1
= TREE_OPERAND (expr
, 1);
1574 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
1575 e
= simplify_replace_tree (cond
, e0
, e1
);
1576 if (integer_zerop (e
))
1578 e
= simplify_replace_tree (cond
, e1
, e0
);
1579 if (integer_zerop (e
))
1582 if (TREE_CODE (expr
) == NE_EXPR
)
1584 e0
= TREE_OPERAND (expr
, 0);
1585 e1
= TREE_OPERAND (expr
, 1);
1587 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
1588 e
= simplify_replace_tree (cond
, e0
, e1
);
1589 if (integer_zerop (e
))
1590 return boolean_true_node
;
1591 e
= simplify_replace_tree (cond
, e1
, e0
);
1592 if (integer_zerop (e
))
1593 return boolean_true_node
;
1596 te
= expand_simple_operations (expr
);
1598 /* Check whether COND ==> EXPR. */
1599 notcond
= invert_truthvalue (cond
);
1600 e
= fold_binary (TRUTH_OR_EXPR
, boolean_type_node
, notcond
, te
);
1601 if (e
&& integer_nonzerop (e
))
1604 /* Check whether COND ==> not EXPR. */
1605 e
= fold_binary (TRUTH_AND_EXPR
, boolean_type_node
, cond
, te
);
1606 if (e
&& integer_zerop (e
))
1612 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1613 expression (or EXPR unchanged, if no simplification was possible).
1614 Wrapper around tree_simplify_using_condition_1 that ensures that chains
1615 of simple operations in definitions of ssa names in COND are expanded,
1616 so that things like casts or incrementing the value of the bound before
1617 the loop do not cause us to fail. */
1620 tree_simplify_using_condition (tree cond
, tree expr
)
1622 cond
= expand_simple_operations (cond
);
1624 return tree_simplify_using_condition_1 (cond
, expr
);
1627 /* Tries to simplify EXPR using the conditions on entry to LOOP.
1628 Returns the simplified expression (or EXPR unchanged, if no
1629 simplification was possible).*/
1632 simplify_using_initial_conditions (struct loop
*loop
, tree expr
)
1640 if (TREE_CODE (expr
) == INTEGER_CST
)
1643 /* Limit walking the dominators to avoid quadraticness in
1644 the number of BBs times the number of loops in degenerate
1646 for (bb
= loop
->header
;
1647 bb
!= ENTRY_BLOCK_PTR
&& cnt
< MAX_DOMINATORS_TO_WALK
;
1648 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1650 if (!single_pred_p (bb
))
1652 e
= single_pred_edge (bb
);
1654 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
1657 stmt
= last_stmt (e
->src
);
1658 cond
= fold_build2 (gimple_cond_code (stmt
),
1660 gimple_cond_lhs (stmt
),
1661 gimple_cond_rhs (stmt
));
1662 if (e
->flags
& EDGE_FALSE_VALUE
)
1663 cond
= invert_truthvalue (cond
);
1664 expr
= tree_simplify_using_condition (cond
, expr
);
1671 /* Tries to simplify EXPR using the evolutions of the loop invariants
1672 in the superloops of LOOP. Returns the simplified expression
1673 (or EXPR unchanged, if no simplification was possible). */
1676 simplify_using_outer_evolutions (struct loop
*loop
, tree expr
)
1678 enum tree_code code
= TREE_CODE (expr
);
1682 if (is_gimple_min_invariant (expr
))
1685 if (code
== TRUTH_OR_EXPR
1686 || code
== TRUTH_AND_EXPR
1687 || code
== COND_EXPR
)
1691 e0
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 0));
1692 if (TREE_OPERAND (expr
, 0) != e0
)
1695 e1
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 1));
1696 if (TREE_OPERAND (expr
, 1) != e1
)
1699 if (code
== COND_EXPR
)
1701 e2
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 2));
1702 if (TREE_OPERAND (expr
, 2) != e2
)
1710 if (code
== COND_EXPR
)
1711 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1713 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1719 e
= instantiate_parameters (loop
, expr
);
1720 if (is_gimple_min_invariant (e
))
1726 /* Returns true if EXIT is the only possible exit from LOOP. */
1729 loop_only_exit_p (const struct loop
*loop
, const_edge exit
)
1732 gimple_stmt_iterator bsi
;
1736 if (exit
!= single_exit (loop
))
1739 body
= get_loop_body (loop
);
1740 for (i
= 0; i
< loop
->num_nodes
; i
++)
1742 for (bsi
= gsi_start_bb (body
[i
]); !gsi_end_p (bsi
); gsi_next (&bsi
))
1744 call
= gsi_stmt (bsi
);
1745 if (gimple_code (call
) != GIMPLE_CALL
)
1748 if (gimple_has_side_effects (call
))
1760 /* Stores description of number of iterations of LOOP derived from
1761 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
1762 useful information could be derived (and fields of NITER has
1763 meaning described in comments at struct tree_niter_desc
1764 declaration), false otherwise. If WARN is true and
1765 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1766 potentially unsafe assumptions. */
1769 number_of_iterations_exit (struct loop
*loop
, edge exit
,
1770 struct tree_niter_desc
*niter
,
1776 enum tree_code code
;
1779 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit
->src
))
1782 niter
->assumptions
= boolean_false_node
;
1783 stmt
= last_stmt (exit
->src
);
1784 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1787 /* We want the condition for staying inside loop. */
1788 code
= gimple_cond_code (stmt
);
1789 if (exit
->flags
& EDGE_TRUE_VALUE
)
1790 code
= invert_tree_comparison (code
, false);
1805 op0
= gimple_cond_lhs (stmt
);
1806 op1
= gimple_cond_rhs (stmt
);
1807 type
= TREE_TYPE (op0
);
1809 if (TREE_CODE (type
) != INTEGER_TYPE
1810 && !POINTER_TYPE_P (type
))
1813 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, false))
1815 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, false))
1818 /* We don't want to see undefined signed overflow warnings while
1819 computing the number of iterations. */
1820 fold_defer_overflow_warnings ();
1822 iv0
.base
= expand_simple_operations (iv0
.base
);
1823 iv1
.base
= expand_simple_operations (iv1
.base
);
1824 if (!number_of_iterations_cond (loop
, type
, &iv0
, code
, &iv1
, niter
,
1825 loop_only_exit_p (loop
, exit
)))
1827 fold_undefer_and_ignore_overflow_warnings ();
1833 niter
->assumptions
= simplify_using_outer_evolutions (loop
,
1834 niter
->assumptions
);
1835 niter
->may_be_zero
= simplify_using_outer_evolutions (loop
,
1836 niter
->may_be_zero
);
1837 niter
->niter
= simplify_using_outer_evolutions (loop
, niter
->niter
);
1841 = simplify_using_initial_conditions (loop
,
1842 niter
->assumptions
);
1844 = simplify_using_initial_conditions (loop
,
1845 niter
->may_be_zero
);
1847 fold_undefer_and_ignore_overflow_warnings ();
1849 if (integer_onep (niter
->assumptions
))
1852 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1853 But if we can prove that there is overflow or some other source of weird
1854 behavior, ignore the loop even with -funsafe-loop-optimizations. */
1855 if (integer_zerop (niter
->assumptions
))
1858 if (flag_unsafe_loop_optimizations
)
1859 niter
->assumptions
= boolean_true_node
;
1863 const char *wording
;
1864 location_t loc
= gimple_location (stmt
);
1866 /* We can provide a more specific warning if one of the operator is
1867 constant and the other advances by +1 or -1. */
1868 if (!integer_zerop (iv1
.step
)
1869 ? (integer_zerop (iv0
.step
)
1870 && (integer_onep (iv1
.step
) || integer_all_onesp (iv1
.step
)))
1871 : (integer_onep (iv0
.step
) || integer_all_onesp (iv0
.step
)))
1873 flag_unsafe_loop_optimizations
1874 ? N_("assuming that the loop is not infinite")
1875 : N_("cannot optimize possibly infinite loops");
1878 flag_unsafe_loop_optimizations
1879 ? N_("assuming that the loop counter does not overflow")
1880 : N_("cannot optimize loop, the loop counter may overflow");
1882 if (LOCATION_LINE (loc
) > 0)
1883 warning (OPT_Wunsafe_loop_optimizations
, "%H%s", &loc
, gettext (wording
));
1885 warning (OPT_Wunsafe_loop_optimizations
, "%s", gettext (wording
));
1888 return flag_unsafe_loop_optimizations
;
1891 /* Try to determine the number of iterations of LOOP. If we succeed,
1892 expression giving number of iterations is returned and *EXIT is
1893 set to the edge from that the information is obtained. Otherwise
1894 chrec_dont_know is returned. */
1897 find_loop_niter (struct loop
*loop
, edge
*exit
)
1900 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
1902 tree niter
= NULL_TREE
, aniter
;
1903 struct tree_niter_desc desc
;
1906 for (i
= 0; VEC_iterate (edge
, exits
, i
, ex
); i
++)
1908 if (!just_once_each_iteration_p (loop
, ex
->src
))
1911 if (!number_of_iterations_exit (loop
, ex
, &desc
, false))
1914 if (integer_nonzerop (desc
.may_be_zero
))
1916 /* We exit in the first iteration through this exit.
1917 We won't find anything better. */
1918 niter
= build_int_cst (unsigned_type_node
, 0);
1923 if (!integer_zerop (desc
.may_be_zero
))
1926 aniter
= desc
.niter
;
1930 /* Nothing recorded yet. */
1936 /* Prefer constants, the lower the better. */
1937 if (TREE_CODE (aniter
) != INTEGER_CST
)
1940 if (TREE_CODE (niter
) != INTEGER_CST
)
1947 if (tree_int_cst_lt (aniter
, niter
))
1954 VEC_free (edge
, heap
, exits
);
1956 return niter
? niter
: chrec_dont_know
;
1959 /* Return true if loop is known to have bounded number of iterations. */
1962 finite_loop_p (struct loop
*loop
)
1965 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
1967 struct tree_niter_desc desc
;
1968 bool finite
= false;
1970 if (flag_unsafe_loop_optimizations
)
1972 if ((TREE_READONLY (current_function_decl
)
1973 || DECL_PURE_P (current_function_decl
))
1974 && !DECL_LOOPING_CONST_OR_PURE_P (current_function_decl
))
1976 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1977 fprintf (dump_file
, "Found loop %i to be finite: it is within pure or const function.\n",
1982 exits
= get_loop_exit_edges (loop
);
1983 for (i
= 0; VEC_iterate (edge
, exits
, i
, ex
); i
++)
1985 if (!just_once_each_iteration_p (loop
, ex
->src
))
1988 if (number_of_iterations_exit (loop
, ex
, &desc
, false))
1990 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1992 fprintf (dump_file
, "Found loop %i to be finite: iterating ", loop
->num
);
1993 print_generic_expr (dump_file
, desc
.niter
, TDF_SLIM
);
1994 fprintf (dump_file
, " times\n");
2000 VEC_free (edge
, heap
, exits
);
2006 Analysis of a number of iterations of a loop by a brute-force evaluation.
2010 /* Bound on the number of iterations we try to evaluate. */
2012 #define MAX_ITERATIONS_TO_TRACK \
2013 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
2015 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
2016 result by a chain of operations such that all but exactly one of their
2017 operands are constants. */
2020 chain_of_csts_start (struct loop
*loop
, tree x
)
2022 gimple stmt
= SSA_NAME_DEF_STMT (x
);
2024 basic_block bb
= gimple_bb (stmt
);
2025 enum tree_code code
;
2028 || !flow_bb_inside_loop_p (loop
, bb
))
2031 if (gimple_code (stmt
) == GIMPLE_PHI
)
2033 if (bb
== loop
->header
)
2039 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2042 code
= gimple_assign_rhs_code (stmt
);
2043 if (gimple_references_memory_p (stmt
)
2044 || TREE_CODE_CLASS (code
) == tcc_reference
2045 || (code
== ADDR_EXPR
2046 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
2049 use
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
2050 if (use
== NULL_TREE
)
2053 return chain_of_csts_start (loop
, use
);
2056 /* Determines whether the expression X is derived from a result of a phi node
2057 in header of LOOP such that
2059 * the derivation of X consists only from operations with constants
2060 * the initial value of the phi node is constant
2061 * the value of the phi node in the next iteration can be derived from the
2062 value in the current iteration by a chain of operations with constants.
2064 If such phi node exists, it is returned, otherwise NULL is returned. */
2067 get_base_for (struct loop
*loop
, tree x
)
2072 if (is_gimple_min_invariant (x
))
2075 phi
= chain_of_csts_start (loop
, x
);
2079 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2080 next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2082 if (TREE_CODE (next
) != SSA_NAME
)
2085 if (!is_gimple_min_invariant (init
))
2088 if (chain_of_csts_start (loop
, next
) != phi
)
2094 /* Given an expression X, then
2096 * if X is NULL_TREE, we return the constant BASE.
2097 * otherwise X is a SSA name, whose value in the considered loop is derived
2098 by a chain of operations with constant from a result of a phi node in
2099 the header of the loop. Then we return value of X when the value of the
2100 result of this phi node is given by the constant BASE. */
2103 get_val_for (tree x
, tree base
)
2107 gcc_assert (is_gimple_min_invariant (base
));
2112 stmt
= SSA_NAME_DEF_STMT (x
);
2113 if (gimple_code (stmt
) == GIMPLE_PHI
)
2116 gcc_assert (is_gimple_assign (stmt
));
2118 /* STMT must be either an assignment of a single SSA name or an
2119 expression involving an SSA name and a constant. Try to fold that
2120 expression using the value for the SSA name. */
2121 if (gimple_assign_ssa_name_copy_p (stmt
))
2122 return get_val_for (gimple_assign_rhs1 (stmt
), base
);
2123 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_UNARY_RHS
2124 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
2126 return fold_build1 (gimple_assign_rhs_code (stmt
),
2127 gimple_expr_type (stmt
),
2128 get_val_for (gimple_assign_rhs1 (stmt
), base
));
2130 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_BINARY_RHS
)
2132 tree rhs1
= gimple_assign_rhs1 (stmt
);
2133 tree rhs2
= gimple_assign_rhs2 (stmt
);
2134 if (TREE_CODE (rhs1
) == SSA_NAME
)
2135 rhs1
= get_val_for (rhs1
, base
);
2136 else if (TREE_CODE (rhs2
) == SSA_NAME
)
2137 rhs2
= get_val_for (rhs2
, base
);
2140 return fold_build2 (gimple_assign_rhs_code (stmt
),
2141 gimple_expr_type (stmt
), rhs1
, rhs2
);
2148 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2149 by brute force -- i.e. by determining the value of the operands of the
2150 condition at EXIT in first few iterations of the loop (assuming that
2151 these values are constant) and determining the first one in that the
2152 condition is not satisfied. Returns the constant giving the number
2153 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
2156 loop_niter_by_eval (struct loop
*loop
, edge exit
)
2159 tree op
[2], val
[2], next
[2], aval
[2];
2164 cond
= last_stmt (exit
->src
);
2165 if (!cond
|| gimple_code (cond
) != GIMPLE_COND
)
2166 return chrec_dont_know
;
2168 cmp
= gimple_cond_code (cond
);
2169 if (exit
->flags
& EDGE_TRUE_VALUE
)
2170 cmp
= invert_tree_comparison (cmp
, false);
2180 op
[0] = gimple_cond_lhs (cond
);
2181 op
[1] = gimple_cond_rhs (cond
);
2185 return chrec_dont_know
;
2188 for (j
= 0; j
< 2; j
++)
2190 if (is_gimple_min_invariant (op
[j
]))
2193 next
[j
] = NULL_TREE
;
2198 phi
= get_base_for (loop
, op
[j
]);
2200 return chrec_dont_know
;
2201 val
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2202 next
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2206 /* Don't issue signed overflow warnings. */
2207 fold_defer_overflow_warnings ();
2209 for (i
= 0; i
< MAX_ITERATIONS_TO_TRACK
; i
++)
2211 for (j
= 0; j
< 2; j
++)
2212 aval
[j
] = get_val_for (op
[j
], val
[j
]);
2214 acnd
= fold_binary (cmp
, boolean_type_node
, aval
[0], aval
[1]);
2215 if (acnd
&& integer_zerop (acnd
))
2217 fold_undefer_and_ignore_overflow_warnings ();
2218 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2220 "Proved that loop %d iterates %d times using brute force.\n",
2222 return build_int_cst (unsigned_type_node
, i
);
2225 for (j
= 0; j
< 2; j
++)
2227 val
[j
] = get_val_for (next
[j
], val
[j
]);
2228 if (!is_gimple_min_invariant (val
[j
]))
2230 fold_undefer_and_ignore_overflow_warnings ();
2231 return chrec_dont_know
;
2236 fold_undefer_and_ignore_overflow_warnings ();
2238 return chrec_dont_know
;
2241 /* Finds the exit of the LOOP by that the loop exits after a constant
2242 number of iterations and stores the exit edge to *EXIT. The constant
2243 giving the number of iterations of LOOP is returned. The number of
2244 iterations is determined using loop_niter_by_eval (i.e. by brute force
2245 evaluation). If we are unable to find the exit for that loop_niter_by_eval
2246 determines the number of iterations, chrec_dont_know is returned. */
2249 find_loop_niter_by_eval (struct loop
*loop
, edge
*exit
)
2252 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
2254 tree niter
= NULL_TREE
, aniter
;
2258 /* Loops with multiple exits are expensive to handle and less important. */
2259 if (!flag_expensive_optimizations
2260 && VEC_length (edge
, exits
) > 1)
2261 return chrec_dont_know
;
2263 for (i
= 0; VEC_iterate (edge
, exits
, i
, ex
); i
++)
2265 if (!just_once_each_iteration_p (loop
, ex
->src
))
2268 aniter
= loop_niter_by_eval (loop
, ex
);
2269 if (chrec_contains_undetermined (aniter
))
2273 && !tree_int_cst_lt (aniter
, niter
))
2279 VEC_free (edge
, heap
, exits
);
2281 return niter
? niter
: chrec_dont_know
;
2286 Analysis of upper bounds on number of iterations of a loop.
2290 static double_int
derive_constant_upper_bound_ops (tree
, tree
,
2291 enum tree_code
, tree
);
2293 /* Returns a constant upper bound on the value of the right-hand side of
2294 an assignment statement STMT. */
2297 derive_constant_upper_bound_assign (gimple stmt
)
2299 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2300 tree op0
= gimple_assign_rhs1 (stmt
);
2301 tree op1
= gimple_assign_rhs2 (stmt
);
2303 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt
)),
2307 /* Returns a constant upper bound on the value of expression VAL. VAL
2308 is considered to be unsigned. If its type is signed, its value must
2312 derive_constant_upper_bound (tree val
)
2314 enum tree_code code
;
2317 extract_ops_from_tree (val
, &code
, &op0
, &op1
);
2318 return derive_constant_upper_bound_ops (TREE_TYPE (val
), op0
, code
, op1
);
2321 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
2322 whose type is TYPE. The expression is considered to be unsigned. If
2323 its type is signed, its value must be nonnegative. */
2326 derive_constant_upper_bound_ops (tree type
, tree op0
,
2327 enum tree_code code
, tree op1
)
2330 double_int bnd
, max
, mmax
, cst
;
2333 if (INTEGRAL_TYPE_P (type
))
2334 maxt
= TYPE_MAX_VALUE (type
);
2336 maxt
= upper_bound_in_type (type
, type
);
2338 max
= tree_to_double_int (maxt
);
2343 return tree_to_double_int (op0
);
2346 subtype
= TREE_TYPE (op0
);
2347 if (!TYPE_UNSIGNED (subtype
)
2348 /* If TYPE is also signed, the fact that VAL is nonnegative implies
2349 that OP0 is nonnegative. */
2350 && TYPE_UNSIGNED (type
)
2351 && !tree_expr_nonnegative_p (op0
))
2353 /* If we cannot prove that the casted expression is nonnegative,
2354 we cannot establish more useful upper bound than the precision
2355 of the type gives us. */
2359 /* We now know that op0 is an nonnegative value. Try deriving an upper
2361 bnd
= derive_constant_upper_bound (op0
);
2363 /* If the bound does not fit in TYPE, max. value of TYPE could be
2365 if (double_int_ucmp (max
, bnd
) < 0)
2371 case POINTER_PLUS_EXPR
:
2373 if (TREE_CODE (op1
) != INTEGER_CST
2374 || !tree_expr_nonnegative_p (op0
))
2377 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
2378 choose the most logical way how to treat this constant regardless
2379 of the signedness of the type. */
2380 cst
= tree_to_double_int (op1
);
2381 cst
= double_int_sext (cst
, TYPE_PRECISION (type
));
2382 if (code
!= MINUS_EXPR
)
2383 cst
= double_int_neg (cst
);
2385 bnd
= derive_constant_upper_bound (op0
);
2387 if (double_int_negative_p (cst
))
2389 cst
= double_int_neg (cst
);
2390 /* Avoid CST == 0x80000... */
2391 if (double_int_negative_p (cst
))
2394 /* OP0 + CST. We need to check that
2395 BND <= MAX (type) - CST. */
2397 mmax
= double_int_add (max
, double_int_neg (cst
));
2398 if (double_int_ucmp (bnd
, mmax
) > 0)
2401 return double_int_add (bnd
, cst
);
2405 /* OP0 - CST, where CST >= 0.
2407 If TYPE is signed, we have already verified that OP0 >= 0, and we
2408 know that the result is nonnegative. This implies that
2411 If TYPE is unsigned, we must additionally know that OP0 >= CST,
2412 otherwise the operation underflows.
2415 /* This should only happen if the type is unsigned; however, for
2416 buggy programs that use overflowing signed arithmetics even with
2417 -fno-wrapv, this condition may also be true for signed values. */
2418 if (double_int_ucmp (bnd
, cst
) < 0)
2421 if (TYPE_UNSIGNED (type
))
2423 tree tem
= fold_binary (GE_EXPR
, boolean_type_node
, op0
,
2424 double_int_to_tree (type
, cst
));
2425 if (!tem
|| integer_nonzerop (tem
))
2429 bnd
= double_int_add (bnd
, double_int_neg (cst
));
2434 case FLOOR_DIV_EXPR
:
2435 case EXACT_DIV_EXPR
:
2436 if (TREE_CODE (op1
) != INTEGER_CST
2437 || tree_int_cst_sign_bit (op1
))
2440 bnd
= derive_constant_upper_bound (op0
);
2441 return double_int_udiv (bnd
, tree_to_double_int (op1
), FLOOR_DIV_EXPR
);
2444 if (TREE_CODE (op1
) != INTEGER_CST
2445 || tree_int_cst_sign_bit (op1
))
2447 return tree_to_double_int (op1
);
2450 stmt
= SSA_NAME_DEF_STMT (op0
);
2451 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2452 || gimple_assign_lhs (stmt
) != op0
)
2454 return derive_constant_upper_bound_assign (stmt
);
2461 /* Records that every statement in LOOP is executed I_BOUND times.
2462 REALISTIC is true if I_BOUND is expected to be close to the real number
2463 of iterations. UPPER is true if we are sure the loop iterates at most
2467 record_niter_bound (struct loop
*loop
, double_int i_bound
, bool realistic
,
2470 /* Update the bounds only when there is no previous estimation, or when the current
2471 estimation is smaller. */
2473 && (!loop
->any_upper_bound
2474 || double_int_ucmp (i_bound
, loop
->nb_iterations_upper_bound
) < 0))
2476 loop
->any_upper_bound
= true;
2477 loop
->nb_iterations_upper_bound
= i_bound
;
2480 && (!loop
->any_estimate
2481 || double_int_ucmp (i_bound
, loop
->nb_iterations_estimate
) < 0))
2483 loop
->any_estimate
= true;
2484 loop
->nb_iterations_estimate
= i_bound
;
2488 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
2489 is true if the loop is exited immediately after STMT, and this exit
2490 is taken at last when the STMT is executed BOUND + 1 times.
2491 REALISTIC is true if BOUND is expected to be close to the real number
2492 of iterations. UPPER is true if we are sure the loop iterates at most
2493 BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */
2496 record_estimate (struct loop
*loop
, tree bound
, double_int i_bound
,
2497 gimple at_stmt
, bool is_exit
, bool realistic
, bool upper
)
2502 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2504 fprintf (dump_file
, "Statement %s", is_exit
? "(exit)" : "");
2505 print_gimple_stmt (dump_file
, at_stmt
, 0, TDF_SLIM
);
2506 fprintf (dump_file
, " is %sexecuted at most ",
2507 upper
? "" : "probably ");
2508 print_generic_expr (dump_file
, bound
, TDF_SLIM
);
2509 fprintf (dump_file
, " (bounded by ");
2510 dump_double_int (dump_file
, i_bound
, true);
2511 fprintf (dump_file
, ") + 1 times in loop %d.\n", loop
->num
);
2514 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
2515 real number of iterations. */
2516 if (TREE_CODE (bound
) != INTEGER_CST
)
2518 if (!upper
&& !realistic
)
2521 /* If we have a guaranteed upper bound, record it in the appropriate
2525 struct nb_iter_bound
*elt
= GGC_NEW (struct nb_iter_bound
);
2527 elt
->bound
= i_bound
;
2528 elt
->stmt
= at_stmt
;
2529 elt
->is_exit
= is_exit
;
2530 elt
->next
= loop
->bounds
;
2534 /* Update the number of iteration estimates according to the bound.
2535 If at_stmt is an exit, then every statement in the loop is
2536 executed at most BOUND + 1 times. If it is not an exit, then
2537 some of the statements before it could be executed BOUND + 2
2538 times, if an exit of LOOP is before stmt. */
2539 exit
= single_exit (loop
);
2542 && dominated_by_p (CDI_DOMINATORS
,
2543 exit
->src
, gimple_bb (at_stmt
))))
2544 delta
= double_int_one
;
2546 delta
= double_int_two
;
2547 i_bound
= double_int_add (i_bound
, delta
);
2549 /* If an overflow occurred, ignore the result. */
2550 if (double_int_ucmp (i_bound
, delta
) < 0)
2553 record_niter_bound (loop
, i_bound
, realistic
, upper
);
2556 /* Record the estimate on number of iterations of LOOP based on the fact that
2557 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
2558 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
2559 estimated number of iterations is expected to be close to the real one.
2560 UPPER is true if we are sure the induction variable does not wrap. */
2563 record_nonwrapping_iv (struct loop
*loop
, tree base
, tree step
, gimple stmt
,
2564 tree low
, tree high
, bool realistic
, bool upper
)
2566 tree niter_bound
, extreme
, delta
;
2567 tree type
= TREE_TYPE (base
), unsigned_type
;
2570 if (TREE_CODE (step
) != INTEGER_CST
|| integer_zerop (step
))
2573 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2575 fprintf (dump_file
, "Induction variable (");
2576 print_generic_expr (dump_file
, TREE_TYPE (base
), TDF_SLIM
);
2577 fprintf (dump_file
, ") ");
2578 print_generic_expr (dump_file
, base
, TDF_SLIM
);
2579 fprintf (dump_file
, " + ");
2580 print_generic_expr (dump_file
, step
, TDF_SLIM
);
2581 fprintf (dump_file
, " * iteration does not wrap in statement ");
2582 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2583 fprintf (dump_file
, " in loop %d.\n", loop
->num
);
2586 unsigned_type
= unsigned_type_for (type
);
2587 base
= fold_convert (unsigned_type
, base
);
2588 step
= fold_convert (unsigned_type
, step
);
2590 if (tree_int_cst_sign_bit (step
))
2592 extreme
= fold_convert (unsigned_type
, low
);
2593 if (TREE_CODE (base
) != INTEGER_CST
)
2594 base
= fold_convert (unsigned_type
, high
);
2595 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
2596 step
= fold_build1 (NEGATE_EXPR
, unsigned_type
, step
);
2600 extreme
= fold_convert (unsigned_type
, high
);
2601 if (TREE_CODE (base
) != INTEGER_CST
)
2602 base
= fold_convert (unsigned_type
, low
);
2603 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
2606 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
2607 would get out of the range. */
2608 niter_bound
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step
);
2609 max
= derive_constant_upper_bound (niter_bound
);
2610 record_estimate (loop
, niter_bound
, max
, stmt
, false, realistic
, upper
);
2613 /* Returns true if REF is a reference to an array at the end of a dynamically
2614 allocated structure. If this is the case, the array may be allocated larger
2615 than its upper bound implies. */
2618 array_at_struct_end_p (tree ref
)
2620 tree base
= get_base_address (ref
);
2623 /* Unless the reference is through a pointer, the size of the array matches
2625 if (!base
|| !INDIRECT_REF_P (base
))
2628 for (;handled_component_p (ref
); ref
= parent
)
2630 parent
= TREE_OPERAND (ref
, 0);
2632 if (TREE_CODE (ref
) == COMPONENT_REF
)
2634 /* All fields of a union are at its end. */
2635 if (TREE_CODE (TREE_TYPE (parent
)) == UNION_TYPE
)
2638 /* Unless the field is at the end of the struct, we are done. */
2639 field
= TREE_OPERAND (ref
, 1);
2640 if (TREE_CHAIN (field
))
2644 /* The other options are ARRAY_REF, ARRAY_RANGE_REF, VIEW_CONVERT_EXPR.
2645 In all these cases, we might be accessing the last element, and
2646 although in practice this will probably never happen, it is legal for
2647 the indices of this last element to exceed the bounds of the array.
2648 Therefore, continue checking. */
2651 gcc_assert (INDIRECT_REF_P (ref
));
2655 /* Determine information about number of iterations a LOOP from the index
2656 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
2657 guaranteed to be executed in every iteration of LOOP. Callback for
2668 idx_infer_loop_bounds (tree base
, tree
*idx
, void *dta
)
2670 struct ilb_data
*data
= (struct ilb_data
*) dta
;
2671 tree ev
, init
, step
;
2672 tree low
, high
, type
, next
;
2673 bool sign
, upper
= data
->reliable
, at_end
= false;
2674 struct loop
*loop
= data
->loop
;
2676 if (TREE_CODE (base
) != ARRAY_REF
)
2679 /* For arrays at the end of the structure, we are not guaranteed that they
2680 do not really extend over their declared size. However, for arrays of
2681 size greater than one, this is unlikely to be intended. */
2682 if (array_at_struct_end_p (base
))
2688 ev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, *idx
));
2689 init
= initial_condition (ev
);
2690 step
= evolution_part_in_loop_num (ev
, loop
->num
);
2694 || TREE_CODE (step
) != INTEGER_CST
2695 || integer_zerop (step
)
2696 || tree_contains_chrecs (init
, NULL
)
2697 || chrec_contains_symbols_defined_in_loop (init
, loop
->num
))
2700 low
= array_ref_low_bound (base
);
2701 high
= array_ref_up_bound (base
);
2703 /* The case of nonconstant bounds could be handled, but it would be
2705 if (TREE_CODE (low
) != INTEGER_CST
2707 || TREE_CODE (high
) != INTEGER_CST
)
2709 sign
= tree_int_cst_sign_bit (step
);
2710 type
= TREE_TYPE (step
);
2712 /* The array of length 1 at the end of a structure most likely extends
2713 beyond its bounds. */
2715 && operand_equal_p (low
, high
, 0))
2718 /* In case the relevant bound of the array does not fit in type, or
2719 it does, but bound + step (in type) still belongs into the range of the
2720 array, the index may wrap and still stay within the range of the array
2721 (consider e.g. if the array is indexed by the full range of
2724 To make things simpler, we require both bounds to fit into type, although
2725 there are cases where this would not be strictly necessary. */
2726 if (!int_fits_type_p (high
, type
)
2727 || !int_fits_type_p (low
, type
))
2729 low
= fold_convert (type
, low
);
2730 high
= fold_convert (type
, high
);
2733 next
= fold_binary (PLUS_EXPR
, type
, low
, step
);
2735 next
= fold_binary (PLUS_EXPR
, type
, high
, step
);
2737 if (tree_int_cst_compare (low
, next
) <= 0
2738 && tree_int_cst_compare (next
, high
) <= 0)
2741 record_nonwrapping_iv (loop
, init
, step
, data
->stmt
, low
, high
, true, upper
);
2745 /* Determine information about number of iterations a LOOP from the bounds
2746 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
2747 STMT is guaranteed to be executed in every iteration of LOOP.*/
2750 infer_loop_bounds_from_ref (struct loop
*loop
, gimple stmt
, tree ref
,
2753 struct ilb_data data
;
2757 data
.reliable
= reliable
;
2758 for_each_index (&ref
, idx_infer_loop_bounds
, &data
);
2761 /* Determine information about number of iterations of a LOOP from the way
2762 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
2763 executed in every iteration of LOOP. */
2766 infer_loop_bounds_from_array (struct loop
*loop
, gimple stmt
, bool reliable
)
2768 if (is_gimple_assign (stmt
))
2770 tree op0
= gimple_assign_lhs (stmt
);
2771 tree op1
= gimple_assign_rhs1 (stmt
);
2773 /* For each memory access, analyze its access function
2774 and record a bound on the loop iteration domain. */
2775 if (REFERENCE_CLASS_P (op0
))
2776 infer_loop_bounds_from_ref (loop
, stmt
, op0
, reliable
);
2778 if (REFERENCE_CLASS_P (op1
))
2779 infer_loop_bounds_from_ref (loop
, stmt
, op1
, reliable
);
2781 else if (is_gimple_call (stmt
))
2784 unsigned i
, n
= gimple_call_num_args (stmt
);
2786 lhs
= gimple_call_lhs (stmt
);
2787 if (lhs
&& REFERENCE_CLASS_P (lhs
))
2788 infer_loop_bounds_from_ref (loop
, stmt
, lhs
, reliable
);
2790 for (i
= 0; i
< n
; i
++)
2792 arg
= gimple_call_arg (stmt
, i
);
2793 if (REFERENCE_CLASS_P (arg
))
2794 infer_loop_bounds_from_ref (loop
, stmt
, arg
, reliable
);
2799 /* Determine information about number of iterations of a LOOP from the fact
2800 that signed arithmetics in STMT does not overflow. */
2803 infer_loop_bounds_from_signedness (struct loop
*loop
, gimple stmt
)
2805 tree def
, base
, step
, scev
, type
, low
, high
;
2807 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2810 def
= gimple_assign_lhs (stmt
);
2812 if (TREE_CODE (def
) != SSA_NAME
)
2815 type
= TREE_TYPE (def
);
2816 if (!INTEGRAL_TYPE_P (type
)
2817 || !TYPE_OVERFLOW_UNDEFINED (type
))
2820 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
2821 if (chrec_contains_undetermined (scev
))
2824 base
= initial_condition_in_loop_num (scev
, loop
->num
);
2825 step
= evolution_part_in_loop_num (scev
, loop
->num
);
2828 || TREE_CODE (step
) != INTEGER_CST
2829 || tree_contains_chrecs (base
, NULL
)
2830 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
2833 low
= lower_bound_in_type (type
, type
);
2834 high
= upper_bound_in_type (type
, type
);
2836 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
2839 /* The following analyzers are extracting informations on the bounds
2840 of LOOP from the following undefined behaviors:
2842 - data references should not access elements over the statically
2845 - signed variables should not overflow when flag_wrapv is not set.
2849 infer_loop_bounds_from_undefined (struct loop
*loop
)
2853 gimple_stmt_iterator bsi
;
2857 bbs
= get_loop_body (loop
);
2859 for (i
= 0; i
< loop
->num_nodes
; i
++)
2863 /* If BB is not executed in each iteration of the loop, we cannot
2864 use the operations in it to infer reliable upper bound on the
2865 # of iterations of the loop. However, we can use it as a guess. */
2866 reliable
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
);
2868 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2870 gimple stmt
= gsi_stmt (bsi
);
2872 infer_loop_bounds_from_array (loop
, stmt
, reliable
);
2875 infer_loop_bounds_from_signedness (loop
, stmt
);
2883 /* Converts VAL to double_int. */
2886 gcov_type_to_double_int (gcov_type val
)
2890 ret
.low
= (unsigned HOST_WIDE_INT
) val
;
2891 /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by
2892 the size of type. */
2893 val
>>= HOST_BITS_PER_WIDE_INT
- 1;
2895 ret
.high
= (unsigned HOST_WIDE_INT
) val
;
2900 /* Records estimates on numbers of iterations of LOOP. */
2903 estimate_numbers_of_iterations_loop (struct loop
*loop
)
2905 VEC (edge
, heap
) *exits
;
2908 struct tree_niter_desc niter_desc
;
2912 /* Give up if we already have tried to compute an estimation. */
2913 if (loop
->estimate_state
!= EST_NOT_COMPUTED
)
2915 loop
->estimate_state
= EST_AVAILABLE
;
2916 loop
->any_upper_bound
= false;
2917 loop
->any_estimate
= false;
2919 exits
= get_loop_exit_edges (loop
);
2920 for (i
= 0; VEC_iterate (edge
, exits
, i
, ex
); i
++)
2922 if (!number_of_iterations_exit (loop
, ex
, &niter_desc
, false))
2925 niter
= niter_desc
.niter
;
2926 type
= TREE_TYPE (niter
);
2927 if (TREE_CODE (niter_desc
.may_be_zero
) != INTEGER_CST
)
2928 niter
= build3 (COND_EXPR
, type
, niter_desc
.may_be_zero
,
2929 build_int_cst (type
, 0),
2931 record_estimate (loop
, niter
, niter_desc
.max
,
2932 last_stmt (ex
->src
),
2935 VEC_free (edge
, heap
, exits
);
2937 infer_loop_bounds_from_undefined (loop
);
2939 /* If we have a measured profile, use it to estimate the number of
2941 if (loop
->header
->count
!= 0)
2943 gcov_type nit
= expected_loop_iterations_unbounded (loop
) + 1;
2944 bound
= gcov_type_to_double_int (nit
);
2945 record_niter_bound (loop
, bound
, true, false);
2948 /* If an upper bound is smaller than the realistic estimate of the
2949 number of iterations, use the upper bound instead. */
2950 if (loop
->any_upper_bound
2951 && loop
->any_estimate
2952 && double_int_ucmp (loop
->nb_iterations_upper_bound
,
2953 loop
->nb_iterations_estimate
) < 0)
2954 loop
->nb_iterations_estimate
= loop
->nb_iterations_upper_bound
;
2957 /* Records estimates on numbers of iterations of loops. */
2960 estimate_numbers_of_iterations (void)
2965 /* We don't want to issue signed overflow warnings while getting
2966 loop iteration estimates. */
2967 fold_defer_overflow_warnings ();
2969 FOR_EACH_LOOP (li
, loop
, 0)
2971 estimate_numbers_of_iterations_loop (loop
);
2974 fold_undefer_and_ignore_overflow_warnings ();
2977 /* Returns true if statement S1 dominates statement S2. */
2980 stmt_dominates_stmt_p (gimple s1
, gimple s2
)
2982 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
2990 gimple_stmt_iterator bsi
;
2992 if (gimple_code (s2
) == GIMPLE_PHI
)
2995 if (gimple_code (s1
) == GIMPLE_PHI
)
2998 for (bsi
= gsi_start_bb (bb1
); gsi_stmt (bsi
) != s2
; gsi_next (&bsi
))
2999 if (gsi_stmt (bsi
) == s1
)
3005 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
3008 /* Returns true when we can prove that the number of executions of
3009 STMT in the loop is at most NITER, according to the bound on
3010 the number of executions of the statement NITER_BOUND->stmt recorded in
3011 NITER_BOUND. If STMT is NULL, we must prove this bound for all
3012 statements in the loop. */
3015 n_of_executions_at_most (gimple stmt
,
3016 struct nb_iter_bound
*niter_bound
,
3019 double_int bound
= niter_bound
->bound
;
3020 tree nit_type
= TREE_TYPE (niter
), e
;
3023 gcc_assert (TYPE_UNSIGNED (nit_type
));
3025 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
3026 the number of iterations is small. */
3027 if (!double_int_fits_to_tree_p (nit_type
, bound
))
3030 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3031 times. This means that:
3033 -- if NITER_BOUND->is_exit is true, then everything before
3034 NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3035 times, and everything after it at most NITER_BOUND->bound times.
3037 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
3038 is executed, then NITER_BOUND->stmt is executed as well in the same
3039 iteration (we conclude that if both statements belong to the same
3040 basic block, or if STMT is after NITER_BOUND->stmt), then STMT
3041 is executed at most NITER_BOUND->bound + 1 times. Otherwise STMT is
3042 executed at most NITER_BOUND->bound + 2 times. */
3044 if (niter_bound
->is_exit
)
3047 && stmt
!= niter_bound
->stmt
3048 && stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
3056 || (gimple_bb (stmt
) != gimple_bb (niter_bound
->stmt
)
3057 && !stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
)))
3059 bound
= double_int_add (bound
, double_int_one
);
3060 if (double_int_zero_p (bound
)
3061 || !double_int_fits_to_tree_p (nit_type
, bound
))
3067 e
= fold_binary (cmp
, boolean_type_node
,
3068 niter
, double_int_to_tree (nit_type
, bound
));
3069 return e
&& integer_nonzerop (e
);
3072 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
3075 nowrap_type_p (tree type
)
3077 if (INTEGRAL_TYPE_P (type
)
3078 && TYPE_OVERFLOW_UNDEFINED (type
))
3081 if (POINTER_TYPE_P (type
))
3087 /* Return false only when the induction variable BASE + STEP * I is
3088 known to not overflow: i.e. when the number of iterations is small
3089 enough with respect to the step and initial condition in order to
3090 keep the evolution confined in TYPEs bounds. Return true when the
3091 iv is known to overflow or when the property is not computable.
3093 USE_OVERFLOW_SEMANTICS is true if this function should assume that
3094 the rules for overflow of the given language apply (e.g., that signed
3095 arithmetics in C does not overflow). */
3098 scev_probably_wraps_p (tree base
, tree step
,
3099 gimple at_stmt
, struct loop
*loop
,
3100 bool use_overflow_semantics
)
3102 struct nb_iter_bound
*bound
;
3103 tree delta
, step_abs
;
3104 tree unsigned_type
, valid_niter
;
3105 tree type
= TREE_TYPE (step
);
3107 /* FIXME: We really need something like
3108 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
3110 We used to test for the following situation that frequently appears
3111 during address arithmetics:
3113 D.1621_13 = (long unsigned intD.4) D.1620_12;
3114 D.1622_14 = D.1621_13 * 8;
3115 D.1623_15 = (doubleD.29 *) D.1622_14;
3117 And derived that the sequence corresponding to D_14
3118 can be proved to not wrap because it is used for computing a
3119 memory access; however, this is not really the case -- for example,
3120 if D_12 = (unsigned char) [254,+,1], then D_14 has values
3121 2032, 2040, 0, 8, ..., but the code is still legal. */
3123 if (chrec_contains_undetermined (base
)
3124 || chrec_contains_undetermined (step
))
3127 if (integer_zerop (step
))
3130 /* If we can use the fact that signed and pointer arithmetics does not
3131 wrap, we are done. */
3132 if (use_overflow_semantics
&& nowrap_type_p (TREE_TYPE (base
)))
3135 /* To be able to use estimates on number of iterations of the loop,
3136 we must have an upper bound on the absolute value of the step. */
3137 if (TREE_CODE (step
) != INTEGER_CST
)
3140 /* Don't issue signed overflow warnings. */
3141 fold_defer_overflow_warnings ();
3143 /* Otherwise, compute the number of iterations before we reach the
3144 bound of the type, and verify that the loop is exited before this
3146 unsigned_type
= unsigned_type_for (type
);
3147 base
= fold_convert (unsigned_type
, base
);
3149 if (tree_int_cst_sign_bit (step
))
3151 tree extreme
= fold_convert (unsigned_type
,
3152 lower_bound_in_type (type
, type
));
3153 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
3154 step_abs
= fold_build1 (NEGATE_EXPR
, unsigned_type
,
3155 fold_convert (unsigned_type
, step
));
3159 tree extreme
= fold_convert (unsigned_type
,
3160 upper_bound_in_type (type
, type
));
3161 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
3162 step_abs
= fold_convert (unsigned_type
, step
);
3165 valid_niter
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step_abs
);
3167 estimate_numbers_of_iterations_loop (loop
);
3168 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
3170 if (n_of_executions_at_most (at_stmt
, bound
, valid_niter
))
3172 fold_undefer_and_ignore_overflow_warnings ();
3177 fold_undefer_and_ignore_overflow_warnings ();
3179 /* At this point we still don't have a proof that the iv does not
3180 overflow: give up. */
3184 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
3187 free_numbers_of_iterations_estimates_loop (struct loop
*loop
)
3189 struct nb_iter_bound
*bound
, *next
;
3191 loop
->nb_iterations
= NULL
;
3192 loop
->estimate_state
= EST_NOT_COMPUTED
;
3193 for (bound
= loop
->bounds
; bound
; bound
= next
)
3199 loop
->bounds
= NULL
;
3202 /* Frees the information on upper bounds on numbers of iterations of loops. */
3205 free_numbers_of_iterations_estimates (void)
3210 FOR_EACH_LOOP (li
, loop
, 0)
3212 free_numbers_of_iterations_estimates_loop (loop
);
3216 /* Substitute value VAL for ssa name NAME inside expressions held
3220 substitute_in_loop_info (struct loop
*loop
, tree name
, tree val
)
3222 loop
->nb_iterations
= simplify_replace_tree (loop
->nb_iterations
, name
, val
);