1 /* Functions to determine/estimate number of iterations of a loop.
2 Copyright (C) 2004-2014 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 3, 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 COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
33 #include "hard-reg-set.h"
36 #include "dominance.h"
38 #include "basic-block.h"
39 #include "gimple-pretty-print.h"
41 #include "tree-ssa-alias.h"
42 #include "internal-fn.h"
43 #include "gimple-expr.h"
47 #include "gimple-iterator.h"
48 #include "gimple-ssa.h"
50 #include "tree-phinodes.h"
51 #include "ssa-iterators.h"
52 #include "tree-ssa-loop-ivopts.h"
53 #include "tree-ssa-loop-niter.h"
54 #include "tree-ssa-loop.h"
57 #include "tree-chrec.h"
58 #include "tree-scalar-evolution.h"
59 #include "tree-data-ref.h"
62 #include "diagnostic-core.h"
63 #include "tree-inline.h"
64 #include "tree-pass.h"
65 #include "stringpool.h"
66 #include "tree-ssanames.h"
67 #include "wide-int-print.h"
70 #define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
72 /* The maximum number of dominator BBs we search for conditions
73 of loop header copies we use for simplifying a conditional
75 #define MAX_DOMINATORS_TO_WALK 8
79 Analysis of number of iterations of an affine exit test.
83 /* Bounds on some value, BELOW <= X <= UP. */
91 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */
94 split_to_var_and_offset (tree expr
, tree
*var
, mpz_t offset
)
96 tree type
= TREE_TYPE (expr
);
101 mpz_set_ui (offset
, 0);
103 switch (TREE_CODE (expr
))
110 case POINTER_PLUS_EXPR
:
111 op0
= TREE_OPERAND (expr
, 0);
112 op1
= TREE_OPERAND (expr
, 1);
114 if (TREE_CODE (op1
) != INTEGER_CST
)
118 /* Always sign extend the offset. */
119 wi::to_mpz (op1
, offset
, SIGNED
);
121 mpz_neg (offset
, offset
);
125 *var
= build_int_cst_type (type
, 0);
126 wi::to_mpz (expr
, offset
, TYPE_SIGN (type
));
134 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
135 in TYPE to MIN and MAX. */
138 determine_value_range (struct loop
*loop
, tree type
, tree var
, mpz_t off
,
139 mpz_t min
, mpz_t max
)
142 enum value_range_type rtype
= VR_VARYING
;
144 /* If the expression is a constant, we know its value exactly. */
145 if (integer_zerop (var
))
152 get_type_static_bounds (type
, min
, max
);
154 /* See if we have some range info from VRP. */
155 if (TREE_CODE (var
) == SSA_NAME
&& INTEGRAL_TYPE_P (type
))
157 edge e
= loop_preheader_edge (loop
);
158 signop sgn
= TYPE_SIGN (type
);
161 /* Either for VAR itself... */
162 rtype
= get_range_info (var
, &minv
, &maxv
);
163 /* Or for PHI results in loop->header where VAR is used as
164 PHI argument from the loop preheader edge. */
165 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
167 gphi
*phi
= gsi
.phi ();
169 if (PHI_ARG_DEF_FROM_EDGE (phi
, e
) == var
170 && (get_range_info (gimple_phi_result (phi
), &minc
, &maxc
)
173 if (rtype
!= VR_RANGE
)
181 minv
= wi::max (minv
, minc
, sgn
);
182 maxv
= wi::min (maxv
, maxc
, sgn
);
183 /* If the PHI result range are inconsistent with
184 the VAR range, give up on looking at the PHI
185 results. This can happen if VR_UNDEFINED is
187 if (wi::gt_p (minv
, maxv
, sgn
))
189 rtype
= get_range_info (var
, &minv
, &maxv
);
195 if (rtype
== VR_RANGE
)
198 gcc_assert (wi::le_p (minv
, maxv
, sgn
));
201 wi::to_mpz (minv
, minm
, sgn
);
202 wi::to_mpz (maxv
, maxm
, sgn
);
203 mpz_add (minm
, minm
, off
);
204 mpz_add (maxm
, maxm
, off
);
205 /* If the computation may not wrap or off is zero, then this
206 is always fine. If off is negative and minv + off isn't
207 smaller than type's minimum, or off is positive and
208 maxv + off isn't bigger than type's maximum, use the more
209 precise range too. */
210 if (nowrap_type_p (type
)
211 || mpz_sgn (off
) == 0
212 || (mpz_sgn (off
) < 0 && mpz_cmp (minm
, min
) >= 0)
213 || (mpz_sgn (off
) > 0 && mpz_cmp (maxm
, max
) <= 0))
226 /* If the computation may wrap, we know nothing about the value, except for
227 the range of the type. */
228 if (!nowrap_type_p (type
))
231 /* Since the addition of OFF does not wrap, if OFF is positive, then we may
232 add it to MIN, otherwise to MAX. */
233 if (mpz_sgn (off
) < 0)
234 mpz_add (max
, max
, off
);
236 mpz_add (min
, min
, off
);
239 /* Stores the bounds on the difference of the values of the expressions
240 (var + X) and (var + Y), computed in TYPE, to BNDS. */
243 bound_difference_of_offsetted_base (tree type
, mpz_t x
, mpz_t y
,
246 int rel
= mpz_cmp (x
, y
);
247 bool may_wrap
= !nowrap_type_p (type
);
250 /* If X == Y, then the expressions are always equal.
251 If X > Y, there are the following possibilities:
252 a) neither of var + X and var + Y overflow or underflow, or both of
253 them do. Then their difference is X - Y.
254 b) var + X overflows, and var + Y does not. Then the values of the
255 expressions are var + X - M and var + Y, where M is the range of
256 the type, and their difference is X - Y - M.
257 c) var + Y underflows and var + X does not. Their difference again
259 Therefore, if the arithmetics in type does not overflow, then the
260 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
261 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
262 (X - Y, X - Y + M). */
266 mpz_set_ui (bnds
->below
, 0);
267 mpz_set_ui (bnds
->up
, 0);
272 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), m
, UNSIGNED
);
273 mpz_add_ui (m
, m
, 1);
274 mpz_sub (bnds
->up
, x
, y
);
275 mpz_set (bnds
->below
, bnds
->up
);
280 mpz_sub (bnds
->below
, bnds
->below
, m
);
282 mpz_add (bnds
->up
, bnds
->up
, m
);
288 /* From condition C0 CMP C1 derives information regarding the
289 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
290 and stores it to BNDS. */
293 refine_bounds_using_guard (tree type
, tree varx
, mpz_t offx
,
294 tree vary
, mpz_t offy
,
295 tree c0
, enum tree_code cmp
, tree c1
,
298 tree varc0
, varc1
, tmp
, ctype
;
299 mpz_t offc0
, offc1
, loffx
, loffy
, bnd
;
301 bool no_wrap
= nowrap_type_p (type
);
310 STRIP_SIGN_NOPS (c0
);
311 STRIP_SIGN_NOPS (c1
);
312 ctype
= TREE_TYPE (c0
);
313 if (!useless_type_conversion_p (ctype
, type
))
319 /* We could derive quite precise information from EQ_EXPR, however, such
320 a guard is unlikely to appear, so we do not bother with handling
325 /* NE_EXPR comparisons do not contain much of useful information, except for
326 special case of comparing with the bounds of the type. */
327 if (TREE_CODE (c1
) != INTEGER_CST
328 || !INTEGRAL_TYPE_P (type
))
331 /* Ensure that the condition speaks about an expression in the same type
333 ctype
= TREE_TYPE (c0
);
334 if (TYPE_PRECISION (ctype
) != TYPE_PRECISION (type
))
336 c0
= fold_convert (type
, c0
);
337 c1
= fold_convert (type
, c1
);
339 if (TYPE_MIN_VALUE (type
)
340 && operand_equal_p (c1
, TYPE_MIN_VALUE (type
), 0))
345 if (TYPE_MAX_VALUE (type
)
346 && operand_equal_p (c1
, TYPE_MAX_VALUE (type
), 0))
359 split_to_var_and_offset (expand_simple_operations (c0
), &varc0
, offc0
);
360 split_to_var_and_offset (expand_simple_operations (c1
), &varc1
, offc1
);
362 /* We are only interested in comparisons of expressions based on VARX and
363 VARY. TODO -- we might also be able to derive some bounds from
364 expressions containing just one of the variables. */
366 if (operand_equal_p (varx
, varc1
, 0))
368 tmp
= varc0
; varc0
= varc1
; varc1
= tmp
;
369 mpz_swap (offc0
, offc1
);
370 cmp
= swap_tree_comparison (cmp
);
373 if (!operand_equal_p (varx
, varc0
, 0)
374 || !operand_equal_p (vary
, varc1
, 0))
377 mpz_init_set (loffx
, offx
);
378 mpz_init_set (loffy
, offy
);
380 if (cmp
== GT_EXPR
|| cmp
== GE_EXPR
)
382 tmp
= varx
; varx
= vary
; vary
= tmp
;
383 mpz_swap (offc0
, offc1
);
384 mpz_swap (loffx
, loffy
);
385 cmp
= swap_tree_comparison (cmp
);
389 /* If there is no overflow, the condition implies that
391 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
393 The overflows and underflows may complicate things a bit; each
394 overflow decreases the appropriate offset by M, and underflow
395 increases it by M. The above inequality would not necessarily be
398 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
399 VARX + OFFC0 overflows, but VARX + OFFX does not.
400 This may only happen if OFFX < OFFC0.
401 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
402 VARY + OFFC1 underflows and VARY + OFFY does not.
403 This may only happen if OFFY > OFFC1. */
412 x_ok
= (integer_zerop (varx
)
413 || mpz_cmp (loffx
, offc0
) >= 0);
414 y_ok
= (integer_zerop (vary
)
415 || mpz_cmp (loffy
, offc1
) <= 0);
421 mpz_sub (bnd
, loffx
, loffy
);
422 mpz_add (bnd
, bnd
, offc1
);
423 mpz_sub (bnd
, bnd
, offc0
);
426 mpz_sub_ui (bnd
, bnd
, 1);
431 if (mpz_cmp (bnds
->below
, bnd
) < 0)
432 mpz_set (bnds
->below
, bnd
);
436 if (mpz_cmp (bnd
, bnds
->up
) < 0)
437 mpz_set (bnds
->up
, bnd
);
449 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
450 The subtraction is considered to be performed in arbitrary precision,
453 We do not attempt to be too clever regarding the value ranges of X and
454 Y; most of the time, they are just integers or ssa names offsetted by
455 integer. However, we try to use the information contained in the
456 comparisons before the loop (usually created by loop header copying). */
459 bound_difference (struct loop
*loop
, tree x
, tree y
, bounds
*bnds
)
461 tree type
= TREE_TYPE (x
);
464 mpz_t minx
, maxx
, miny
, maxy
;
472 /* Get rid of unnecessary casts, but preserve the value of
477 mpz_init (bnds
->below
);
481 split_to_var_and_offset (x
, &varx
, offx
);
482 split_to_var_and_offset (y
, &vary
, offy
);
484 if (!integer_zerop (varx
)
485 && operand_equal_p (varx
, vary
, 0))
487 /* Special case VARX == VARY -- we just need to compare the
488 offsets. The matters are a bit more complicated in the
489 case addition of offsets may wrap. */
490 bound_difference_of_offsetted_base (type
, offx
, offy
, bnds
);
494 /* Otherwise, use the value ranges to determine the initial
495 estimates on below and up. */
500 determine_value_range (loop
, type
, varx
, offx
, minx
, maxx
);
501 determine_value_range (loop
, type
, vary
, offy
, miny
, maxy
);
503 mpz_sub (bnds
->below
, minx
, maxy
);
504 mpz_sub (bnds
->up
, maxx
, miny
);
511 /* If both X and Y are constants, we cannot get any more precise. */
512 if (integer_zerop (varx
) && integer_zerop (vary
))
515 /* Now walk the dominators of the loop header and use the entry
516 guards to refine the estimates. */
517 for (bb
= loop
->header
;
518 bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && cnt
< MAX_DOMINATORS_TO_WALK
;
519 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
521 if (!single_pred_p (bb
))
523 e
= single_pred_edge (bb
);
525 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
528 cond
= last_stmt (e
->src
);
529 c0
= gimple_cond_lhs (cond
);
530 cmp
= gimple_cond_code (cond
);
531 c1
= gimple_cond_rhs (cond
);
533 if (e
->flags
& EDGE_FALSE_VALUE
)
534 cmp
= invert_tree_comparison (cmp
, false);
536 refine_bounds_using_guard (type
, varx
, offx
, vary
, offy
,
546 /* Update the bounds in BNDS that restrict the value of X to the bounds
547 that restrict the value of X + DELTA. X can be obtained as a
548 difference of two values in TYPE. */
551 bounds_add (bounds
*bnds
, const widest_int
&delta
, tree type
)
556 wi::to_mpz (delta
, mdelta
, SIGNED
);
559 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), max
, UNSIGNED
);
561 mpz_add (bnds
->up
, bnds
->up
, mdelta
);
562 mpz_add (bnds
->below
, bnds
->below
, mdelta
);
564 if (mpz_cmp (bnds
->up
, max
) > 0)
565 mpz_set (bnds
->up
, max
);
568 if (mpz_cmp (bnds
->below
, max
) < 0)
569 mpz_set (bnds
->below
, max
);
575 /* Update the bounds in BNDS that restrict the value of X to the bounds
576 that restrict the value of -X. */
579 bounds_negate (bounds
*bnds
)
583 mpz_init_set (tmp
, bnds
->up
);
584 mpz_neg (bnds
->up
, bnds
->below
);
585 mpz_neg (bnds
->below
, tmp
);
589 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
592 inverse (tree x
, tree mask
)
594 tree type
= TREE_TYPE (x
);
596 unsigned ctr
= tree_floor_log2 (mask
);
598 if (TYPE_PRECISION (type
) <= HOST_BITS_PER_WIDE_INT
)
600 unsigned HOST_WIDE_INT ix
;
601 unsigned HOST_WIDE_INT imask
;
602 unsigned HOST_WIDE_INT irslt
= 1;
604 gcc_assert (cst_and_fits_in_hwi (x
));
605 gcc_assert (cst_and_fits_in_hwi (mask
));
607 ix
= int_cst_value (x
);
608 imask
= int_cst_value (mask
);
617 rslt
= build_int_cst_type (type
, irslt
);
621 rslt
= build_int_cst (type
, 1);
624 rslt
= int_const_binop (MULT_EXPR
, rslt
, x
);
625 x
= int_const_binop (MULT_EXPR
, x
, x
);
627 rslt
= int_const_binop (BIT_AND_EXPR
, rslt
, mask
);
633 /* Derives the upper bound BND on the number of executions of loop with exit
634 condition S * i <> C. If NO_OVERFLOW is true, then the control variable of
635 the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed
636 that the loop ends through this exit, i.e., the induction variable ever
637 reaches the value of C.
639 The value C is equal to final - base, where final and base are the final and
640 initial value of the actual induction variable in the analysed loop. BNDS
641 bounds the value of this difference when computed in signed type with
642 unbounded range, while the computation of C is performed in an unsigned
643 type with the range matching the range of the type of the induction variable.
644 In particular, BNDS.up contains an upper bound on C in the following cases:
645 -- if the iv must reach its final value without overflow, i.e., if
646 NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
647 -- if final >= base, which we know to hold when BNDS.below >= 0. */
650 number_of_iterations_ne_max (mpz_t bnd
, bool no_overflow
, tree c
, tree s
,
651 bounds
*bnds
, bool exit_must_be_taken
)
655 tree type
= TREE_TYPE (c
);
656 bool bnds_u_valid
= ((no_overflow
&& exit_must_be_taken
)
657 || mpz_sgn (bnds
->below
) >= 0);
660 || (TREE_CODE (c
) == INTEGER_CST
661 && TREE_CODE (s
) == INTEGER_CST
662 && wi::mod_trunc (c
, s
, TYPE_SIGN (type
)) == 0)
663 || (TYPE_OVERFLOW_UNDEFINED (type
)
664 && multiple_of_p (type
, c
, s
)))
666 /* If C is an exact multiple of S, then its value will be reached before
667 the induction variable overflows (unless the loop is exited in some
668 other way before). Note that the actual induction variable in the
669 loop (which ranges from base to final instead of from 0 to C) may
670 overflow, in which case BNDS.up will not be giving a correct upper
671 bound on C; thus, BNDS_U_VALID had to be computed in advance. */
673 exit_must_be_taken
= true;
676 /* If the induction variable can overflow, the number of iterations is at
677 most the period of the control variable (or infinite, but in that case
678 the whole # of iterations analysis will fail). */
681 max
= wi::mask
<widest_int
> (TYPE_PRECISION (type
) - wi::ctz (s
), false);
682 wi::to_mpz (max
, bnd
, UNSIGNED
);
686 /* Now we know that the induction variable does not overflow, so the loop
687 iterates at most (range of type / S) times. */
688 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), bnd
, UNSIGNED
);
690 /* If the induction variable is guaranteed to reach the value of C before
692 if (exit_must_be_taken
)
694 /* ... then we can strengthen this to C / S, and possibly we can use
695 the upper bound on C given by BNDS. */
696 if (TREE_CODE (c
) == INTEGER_CST
)
697 wi::to_mpz (c
, bnd
, UNSIGNED
);
698 else if (bnds_u_valid
)
699 mpz_set (bnd
, bnds
->up
);
703 wi::to_mpz (s
, d
, UNSIGNED
);
704 mpz_fdiv_q (bnd
, bnd
, d
);
708 /* Determines number of iterations of loop whose ending condition
709 is IV <> FINAL. TYPE is the type of the iv. The number of
710 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
711 we know that the exit must be taken eventually, i.e., that the IV
712 ever reaches the value FINAL (we derived this earlier, and possibly set
713 NITER->assumptions to make sure this is the case). BNDS contains the
714 bounds on the difference FINAL - IV->base. */
717 number_of_iterations_ne (tree type
, affine_iv
*iv
, tree final
,
718 struct tree_niter_desc
*niter
, bool exit_must_be_taken
,
721 tree niter_type
= unsigned_type_for (type
);
722 tree s
, c
, d
, bits
, assumption
, tmp
, bound
;
725 niter
->control
= *iv
;
726 niter
->bound
= final
;
727 niter
->cmp
= NE_EXPR
;
729 /* Rearrange the terms so that we get inequality S * i <> C, with S
730 positive. Also cast everything to the unsigned type. If IV does
731 not overflow, BNDS bounds the value of C. Also, this is the
732 case if the computation |FINAL - IV->base| does not overflow, i.e.,
733 if BNDS->below in the result is nonnegative. */
734 if (tree_int_cst_sign_bit (iv
->step
))
736 s
= fold_convert (niter_type
,
737 fold_build1 (NEGATE_EXPR
, type
, iv
->step
));
738 c
= fold_build2 (MINUS_EXPR
, niter_type
,
739 fold_convert (niter_type
, iv
->base
),
740 fold_convert (niter_type
, final
));
741 bounds_negate (bnds
);
745 s
= fold_convert (niter_type
, iv
->step
);
746 c
= fold_build2 (MINUS_EXPR
, niter_type
,
747 fold_convert (niter_type
, final
),
748 fold_convert (niter_type
, iv
->base
));
752 number_of_iterations_ne_max (max
, iv
->no_overflow
, c
, s
, bnds
,
754 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, max
, false),
755 TYPE_SIGN (niter_type
));
758 /* First the trivial cases -- when the step is 1. */
759 if (integer_onep (s
))
765 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
766 is infinite. Otherwise, the number of iterations is
767 (inverse(s/d) * (c/d)) mod (size of mode/d). */
768 bits
= num_ending_zeros (s
);
769 bound
= build_low_bits_mask (niter_type
,
770 (TYPE_PRECISION (niter_type
)
771 - tree_to_uhwi (bits
)));
773 d
= fold_binary_to_constant (LSHIFT_EXPR
, niter_type
,
774 build_int_cst (niter_type
, 1), bits
);
775 s
= fold_binary_to_constant (RSHIFT_EXPR
, niter_type
, s
, bits
);
777 if (!exit_must_be_taken
)
779 /* If we cannot assume that the exit is taken eventually, record the
780 assumptions for divisibility of c. */
781 assumption
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, c
, d
);
782 assumption
= fold_build2 (EQ_EXPR
, boolean_type_node
,
783 assumption
, build_int_cst (niter_type
, 0));
784 if (!integer_nonzerop (assumption
))
785 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
786 niter
->assumptions
, assumption
);
789 c
= fold_build2 (EXACT_DIV_EXPR
, niter_type
, c
, d
);
790 tmp
= fold_build2 (MULT_EXPR
, niter_type
, c
, inverse (s
, bound
));
791 niter
->niter
= fold_build2 (BIT_AND_EXPR
, niter_type
, tmp
, bound
);
795 /* Checks whether we can determine the final value of the control variable
796 of the loop with ending condition IV0 < IV1 (computed in TYPE).
797 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
798 of the step. The assumptions necessary to ensure that the computation
799 of the final value does not overflow are recorded in NITER. If we
800 find the final value, we adjust DELTA and return TRUE. Otherwise
801 we return false. BNDS bounds the value of IV1->base - IV0->base,
802 and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
803 true if we know that the exit must be taken eventually. */
806 number_of_iterations_lt_to_ne (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
807 struct tree_niter_desc
*niter
,
808 tree
*delta
, tree step
,
809 bool exit_must_be_taken
, bounds
*bnds
)
811 tree niter_type
= TREE_TYPE (step
);
812 tree mod
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, *delta
, step
);
815 tree assumption
= boolean_true_node
, bound
, noloop
;
816 bool ret
= false, fv_comp_no_overflow
;
818 if (POINTER_TYPE_P (type
))
821 if (TREE_CODE (mod
) != INTEGER_CST
)
823 if (integer_nonzerop (mod
))
824 mod
= fold_build2 (MINUS_EXPR
, niter_type
, step
, mod
);
825 tmod
= fold_convert (type1
, mod
);
828 wi::to_mpz (mod
, mmod
, UNSIGNED
);
829 mpz_neg (mmod
, mmod
);
831 /* If the induction variable does not overflow and the exit is taken,
832 then the computation of the final value does not overflow. This is
833 also obviously the case if the new final value is equal to the
834 current one. Finally, we postulate this for pointer type variables,
835 as the code cannot rely on the object to that the pointer points being
836 placed at the end of the address space (and more pragmatically,
837 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
838 if (integer_zerop (mod
) || POINTER_TYPE_P (type
))
839 fv_comp_no_overflow
= true;
840 else if (!exit_must_be_taken
)
841 fv_comp_no_overflow
= false;
843 fv_comp_no_overflow
=
844 (iv0
->no_overflow
&& integer_nonzerop (iv0
->step
))
845 || (iv1
->no_overflow
&& integer_nonzerop (iv1
->step
));
847 if (integer_nonzerop (iv0
->step
))
849 /* The final value of the iv is iv1->base + MOD, assuming that this
850 computation does not overflow, and that
851 iv0->base <= iv1->base + MOD. */
852 if (!fv_comp_no_overflow
)
854 bound
= fold_build2 (MINUS_EXPR
, type1
,
855 TYPE_MAX_VALUE (type1
), tmod
);
856 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
858 if (integer_zerop (assumption
))
861 if (mpz_cmp (mmod
, bnds
->below
) < 0)
862 noloop
= boolean_false_node
;
863 else if (POINTER_TYPE_P (type
))
864 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
866 fold_build_pointer_plus (iv1
->base
, tmod
));
868 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
870 fold_build2 (PLUS_EXPR
, type1
,
875 /* The final value of the iv is iv0->base - MOD, assuming that this
876 computation does not overflow, and that
877 iv0->base - MOD <= iv1->base. */
878 if (!fv_comp_no_overflow
)
880 bound
= fold_build2 (PLUS_EXPR
, type1
,
881 TYPE_MIN_VALUE (type1
), tmod
);
882 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
884 if (integer_zerop (assumption
))
887 if (mpz_cmp (mmod
, bnds
->below
) < 0)
888 noloop
= boolean_false_node
;
889 else if (POINTER_TYPE_P (type
))
890 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
891 fold_build_pointer_plus (iv0
->base
,
892 fold_build1 (NEGATE_EXPR
,
896 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
897 fold_build2 (MINUS_EXPR
, type1
,
902 if (!integer_nonzerop (assumption
))
903 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
906 if (!integer_zerop (noloop
))
907 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
910 bounds_add (bnds
, wi::to_widest (mod
), type
);
911 *delta
= fold_build2 (PLUS_EXPR
, niter_type
, *delta
, mod
);
919 /* Add assertions to NITER that ensure that the control variable of the loop
920 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
921 are TYPE. Returns false if we can prove that there is an overflow, true
922 otherwise. STEP is the absolute value of the step. */
925 assert_no_overflow_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
926 struct tree_niter_desc
*niter
, tree step
)
928 tree bound
, d
, assumption
, diff
;
929 tree niter_type
= TREE_TYPE (step
);
931 if (integer_nonzerop (iv0
->step
))
933 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
934 if (iv0
->no_overflow
)
937 /* If iv0->base is a constant, we can determine the last value before
938 overflow precisely; otherwise we conservatively assume
941 if (TREE_CODE (iv0
->base
) == INTEGER_CST
)
943 d
= fold_build2 (MINUS_EXPR
, niter_type
,
944 fold_convert (niter_type
, TYPE_MAX_VALUE (type
)),
945 fold_convert (niter_type
, iv0
->base
));
946 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
949 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
950 build_int_cst (niter_type
, 1));
951 bound
= fold_build2 (MINUS_EXPR
, type
,
952 TYPE_MAX_VALUE (type
), fold_convert (type
, diff
));
953 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
958 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
959 if (iv1
->no_overflow
)
962 if (TREE_CODE (iv1
->base
) == INTEGER_CST
)
964 d
= fold_build2 (MINUS_EXPR
, niter_type
,
965 fold_convert (niter_type
, iv1
->base
),
966 fold_convert (niter_type
, TYPE_MIN_VALUE (type
)));
967 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
970 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
971 build_int_cst (niter_type
, 1));
972 bound
= fold_build2 (PLUS_EXPR
, type
,
973 TYPE_MIN_VALUE (type
), fold_convert (type
, diff
));
974 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
978 if (integer_zerop (assumption
))
980 if (!integer_nonzerop (assumption
))
981 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
982 niter
->assumptions
, assumption
);
984 iv0
->no_overflow
= true;
985 iv1
->no_overflow
= true;
989 /* Add an assumption to NITER that a loop whose ending condition
990 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
991 bounds the value of IV1->base - IV0->base. */
994 assert_loop_rolls_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
995 struct tree_niter_desc
*niter
, bounds
*bnds
)
997 tree assumption
= boolean_true_node
, bound
, diff
;
998 tree mbz
, mbzl
, mbzr
, type1
;
999 bool rolls_p
, no_overflow_p
;
1003 /* We are going to compute the number of iterations as
1004 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
1005 variant of TYPE. This formula only works if
1007 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
1009 (where MAX is the maximum value of the unsigned variant of TYPE, and
1010 the computations in this formula are performed in full precision,
1011 i.e., without overflows).
1013 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
1014 we have a condition of the form iv0->base - step < iv1->base before the loop,
1015 and for loops iv0->base < iv1->base - step * i the condition
1016 iv0->base < iv1->base + step, due to loop header copying, which enable us
1017 to prove the lower bound.
1019 The upper bound is more complicated. Unless the expressions for initial
1020 and final value themselves contain enough information, we usually cannot
1021 derive it from the context. */
1023 /* First check whether the answer does not follow from the bounds we gathered
1025 if (integer_nonzerop (iv0
->step
))
1026 dstep
= wi::to_widest (iv0
->step
);
1029 dstep
= wi::sext (wi::to_widest (iv1
->step
), TYPE_PRECISION (type
));
1034 wi::to_mpz (dstep
, mstep
, UNSIGNED
);
1035 mpz_neg (mstep
, mstep
);
1036 mpz_add_ui (mstep
, mstep
, 1);
1038 rolls_p
= mpz_cmp (mstep
, bnds
->below
) <= 0;
1041 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), max
, UNSIGNED
);
1042 mpz_add (max
, max
, mstep
);
1043 no_overflow_p
= (mpz_cmp (bnds
->up
, max
) <= 0
1044 /* For pointers, only values lying inside a single object
1045 can be compared or manipulated by pointer arithmetics.
1046 Gcc in general does not allow or handle objects larger
1047 than half of the address space, hence the upper bound
1048 is satisfied for pointers. */
1049 || POINTER_TYPE_P (type
));
1053 if (rolls_p
&& no_overflow_p
)
1057 if (POINTER_TYPE_P (type
))
1060 /* Now the hard part; we must formulate the assumption(s) as expressions, and
1061 we must be careful not to introduce overflow. */
1063 if (integer_nonzerop (iv0
->step
))
1065 diff
= fold_build2 (MINUS_EXPR
, type1
,
1066 iv0
->step
, build_int_cst (type1
, 1));
1068 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
1069 0 address never belongs to any object, we can assume this for
1071 if (!POINTER_TYPE_P (type
))
1073 bound
= fold_build2 (PLUS_EXPR
, type1
,
1074 TYPE_MIN_VALUE (type
), diff
);
1075 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
1079 /* And then we can compute iv0->base - diff, and compare it with
1081 mbzl
= fold_build2 (MINUS_EXPR
, type1
,
1082 fold_convert (type1
, iv0
->base
), diff
);
1083 mbzr
= fold_convert (type1
, iv1
->base
);
1087 diff
= fold_build2 (PLUS_EXPR
, type1
,
1088 iv1
->step
, build_int_cst (type1
, 1));
1090 if (!POINTER_TYPE_P (type
))
1092 bound
= fold_build2 (PLUS_EXPR
, type1
,
1093 TYPE_MAX_VALUE (type
), diff
);
1094 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
1098 mbzl
= fold_convert (type1
, iv0
->base
);
1099 mbzr
= fold_build2 (MINUS_EXPR
, type1
,
1100 fold_convert (type1
, iv1
->base
), diff
);
1103 if (!integer_nonzerop (assumption
))
1104 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1105 niter
->assumptions
, assumption
);
1108 mbz
= fold_build2 (GT_EXPR
, boolean_type_node
, mbzl
, mbzr
);
1109 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1110 niter
->may_be_zero
, mbz
);
1114 /* Determines number of iterations of loop whose ending condition
1115 is IV0 < IV1. TYPE is the type of the iv. The number of
1116 iterations is stored to NITER. BNDS bounds the difference
1117 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
1118 that the exit must be taken eventually. */
1121 number_of_iterations_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1122 struct tree_niter_desc
*niter
,
1123 bool exit_must_be_taken
, bounds
*bnds
)
1125 tree niter_type
= unsigned_type_for (type
);
1126 tree delta
, step
, s
;
1129 if (integer_nonzerop (iv0
->step
))
1131 niter
->control
= *iv0
;
1132 niter
->cmp
= LT_EXPR
;
1133 niter
->bound
= iv1
->base
;
1137 niter
->control
= *iv1
;
1138 niter
->cmp
= GT_EXPR
;
1139 niter
->bound
= iv0
->base
;
1142 delta
= fold_build2 (MINUS_EXPR
, niter_type
,
1143 fold_convert (niter_type
, iv1
->base
),
1144 fold_convert (niter_type
, iv0
->base
));
1146 /* First handle the special case that the step is +-1. */
1147 if ((integer_onep (iv0
->step
) && integer_zerop (iv1
->step
))
1148 || (integer_all_onesp (iv1
->step
) && integer_zerop (iv0
->step
)))
1150 /* for (i = iv0->base; i < iv1->base; i++)
1154 for (i = iv1->base; i > iv0->base; i--).
1156 In both cases # of iterations is iv1->base - iv0->base, assuming that
1157 iv1->base >= iv0->base.
1159 First try to derive a lower bound on the value of
1160 iv1->base - iv0->base, computed in full precision. If the difference
1161 is nonnegative, we are done, otherwise we must record the
1164 if (mpz_sgn (bnds
->below
) < 0)
1165 niter
->may_be_zero
= fold_build2 (LT_EXPR
, boolean_type_node
,
1166 iv1
->base
, iv0
->base
);
1167 niter
->niter
= delta
;
1168 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, bnds
->up
, false),
1169 TYPE_SIGN (niter_type
));
1173 if (integer_nonzerop (iv0
->step
))
1174 step
= fold_convert (niter_type
, iv0
->step
);
1176 step
= fold_convert (niter_type
,
1177 fold_build1 (NEGATE_EXPR
, type
, iv1
->step
));
1179 /* If we can determine the final value of the control iv exactly, we can
1180 transform the condition to != comparison. In particular, this will be
1181 the case if DELTA is constant. */
1182 if (number_of_iterations_lt_to_ne (type
, iv0
, iv1
, niter
, &delta
, step
,
1183 exit_must_be_taken
, bnds
))
1187 zps
.base
= build_int_cst (niter_type
, 0);
1189 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1190 zps does not overflow. */
1191 zps
.no_overflow
= true;
1193 return number_of_iterations_ne (type
, &zps
, delta
, niter
, true, bnds
);
1196 /* Make sure that the control iv does not overflow. */
1197 if (!assert_no_overflow_lt (type
, iv0
, iv1
, niter
, step
))
1200 /* We determine the number of iterations as (delta + step - 1) / step. For
1201 this to work, we must know that iv1->base >= iv0->base - step + 1,
1202 otherwise the loop does not roll. */
1203 assert_loop_rolls_lt (type
, iv0
, iv1
, niter
, bnds
);
1205 s
= fold_build2 (MINUS_EXPR
, niter_type
,
1206 step
, build_int_cst (niter_type
, 1));
1207 delta
= fold_build2 (PLUS_EXPR
, niter_type
, delta
, s
);
1208 niter
->niter
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, delta
, step
);
1212 wi::to_mpz (step
, mstep
, UNSIGNED
);
1213 mpz_add (tmp
, bnds
->up
, mstep
);
1214 mpz_sub_ui (tmp
, tmp
, 1);
1215 mpz_fdiv_q (tmp
, tmp
, mstep
);
1216 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, tmp
, false),
1217 TYPE_SIGN (niter_type
));
1224 /* Determines number of iterations of loop whose ending condition
1225 is IV0 <= IV1. TYPE is the type of the iv. The number of
1226 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
1227 we know that this condition must eventually become false (we derived this
1228 earlier, and possibly set NITER->assumptions to make sure this
1229 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1232 number_of_iterations_le (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1233 struct tree_niter_desc
*niter
, bool exit_must_be_taken
,
1238 if (POINTER_TYPE_P (type
))
1241 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1242 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1243 value of the type. This we must know anyway, since if it is
1244 equal to this value, the loop rolls forever. We do not check
1245 this condition for pointer type ivs, as the code cannot rely on
1246 the object to that the pointer points being placed at the end of
1247 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1248 not defined for pointers). */
1250 if (!exit_must_be_taken
&& !POINTER_TYPE_P (type
))
1252 if (integer_nonzerop (iv0
->step
))
1253 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1254 iv1
->base
, TYPE_MAX_VALUE (type
));
1256 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1257 iv0
->base
, TYPE_MIN_VALUE (type
));
1259 if (integer_zerop (assumption
))
1261 if (!integer_nonzerop (assumption
))
1262 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1263 niter
->assumptions
, assumption
);
1266 if (integer_nonzerop (iv0
->step
))
1268 if (POINTER_TYPE_P (type
))
1269 iv1
->base
= fold_build_pointer_plus_hwi (iv1
->base
, 1);
1271 iv1
->base
= fold_build2 (PLUS_EXPR
, type1
, iv1
->base
,
1272 build_int_cst (type1
, 1));
1274 else if (POINTER_TYPE_P (type
))
1275 iv0
->base
= fold_build_pointer_plus_hwi (iv0
->base
, -1);
1277 iv0
->base
= fold_build2 (MINUS_EXPR
, type1
,
1278 iv0
->base
, build_int_cst (type1
, 1));
1280 bounds_add (bnds
, 1, type1
);
1282 return number_of_iterations_lt (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1286 /* Dumps description of affine induction variable IV to FILE. */
1289 dump_affine_iv (FILE *file
, affine_iv
*iv
)
1291 if (!integer_zerop (iv
->step
))
1292 fprintf (file
, "[");
1294 print_generic_expr (dump_file
, iv
->base
, TDF_SLIM
);
1296 if (!integer_zerop (iv
->step
))
1298 fprintf (file
, ", + , ");
1299 print_generic_expr (dump_file
, iv
->step
, TDF_SLIM
);
1300 fprintf (file
, "]%s", iv
->no_overflow
? "(no_overflow)" : "");
1304 /* Determine the number of iterations according to condition (for staying
1305 inside loop) which compares two induction variables using comparison
1306 operator CODE. The induction variable on left side of the comparison
1307 is IV0, the right-hand side is IV1. Both induction variables must have
1308 type TYPE, which must be an integer or pointer type. The steps of the
1309 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1311 LOOP is the loop whose number of iterations we are determining.
1313 ONLY_EXIT is true if we are sure this is the only way the loop could be
1314 exited (including possibly non-returning function calls, exceptions, etc.)
1315 -- in this case we can use the information whether the control induction
1316 variables can overflow or not in a more efficient way.
1318 if EVERY_ITERATION is true, we know the test is executed on every iteration.
1320 The results (number of iterations and assumptions as described in
1321 comments at struct tree_niter_desc in tree-ssa-loop.h) are stored to NITER.
1322 Returns false if it fails to determine number of iterations, true if it
1323 was determined (possibly with some assumptions). */
1326 number_of_iterations_cond (struct loop
*loop
,
1327 tree type
, affine_iv
*iv0
, enum tree_code code
,
1328 affine_iv
*iv1
, struct tree_niter_desc
*niter
,
1329 bool only_exit
, bool every_iteration
)
1331 bool exit_must_be_taken
= false, ret
;
1334 /* If the test is not executed every iteration, wrapping may make the test
1336 TODO: the overflow case can be still used as unreliable estimate of upper
1337 bound. But we have no API to pass it down to number of iterations code
1338 and, at present, it will not use it anyway. */
1339 if (!every_iteration
1340 && (!iv0
->no_overflow
|| !iv1
->no_overflow
1341 || code
== NE_EXPR
|| code
== EQ_EXPR
))
1344 /* The meaning of these assumptions is this:
1346 then the rest of information does not have to be valid
1347 if may_be_zero then the loop does not roll, even if
1349 niter
->assumptions
= boolean_true_node
;
1350 niter
->may_be_zero
= boolean_false_node
;
1351 niter
->niter
= NULL_TREE
;
1353 niter
->bound
= NULL_TREE
;
1354 niter
->cmp
= ERROR_MARK
;
1356 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1357 the control variable is on lhs. */
1358 if (code
== GE_EXPR
|| code
== GT_EXPR
1359 || (code
== NE_EXPR
&& integer_zerop (iv0
->step
)))
1362 code
= swap_tree_comparison (code
);
1365 if (POINTER_TYPE_P (type
))
1367 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1368 to the same object. If they do, the control variable cannot wrap
1369 (as wrap around the bounds of memory will never return a pointer
1370 that would be guaranteed to point to the same object, even if we
1371 avoid undefined behavior by casting to size_t and back). */
1372 iv0
->no_overflow
= true;
1373 iv1
->no_overflow
= true;
1376 /* If the control induction variable does not overflow and the only exit
1377 from the loop is the one that we analyze, we know it must be taken
1381 if (!integer_zerop (iv0
->step
) && iv0
->no_overflow
)
1382 exit_must_be_taken
= true;
1383 else if (!integer_zerop (iv1
->step
) && iv1
->no_overflow
)
1384 exit_must_be_taken
= true;
1387 /* We can handle the case when neither of the sides of the comparison is
1388 invariant, provided that the test is NE_EXPR. This rarely occurs in
1389 practice, but it is simple enough to manage. */
1390 if (!integer_zerop (iv0
->step
) && !integer_zerop (iv1
->step
))
1392 tree step_type
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1393 if (code
!= NE_EXPR
)
1396 iv0
->step
= fold_binary_to_constant (MINUS_EXPR
, step_type
,
1397 iv0
->step
, iv1
->step
);
1398 iv0
->no_overflow
= false;
1399 iv1
->step
= build_int_cst (step_type
, 0);
1400 iv1
->no_overflow
= true;
1403 /* If the result of the comparison is a constant, the loop is weird. More
1404 precise handling would be possible, but the situation is not common enough
1405 to waste time on it. */
1406 if (integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
))
1409 /* Ignore loops of while (i-- < 10) type. */
1410 if (code
!= NE_EXPR
)
1412 if (iv0
->step
&& tree_int_cst_sign_bit (iv0
->step
))
1415 if (!integer_zerop (iv1
->step
) && !tree_int_cst_sign_bit (iv1
->step
))
1419 /* If the loop exits immediately, there is nothing to do. */
1420 tree tem
= fold_binary (code
, boolean_type_node
, iv0
->base
, iv1
->base
);
1421 if (tem
&& integer_zerop (tem
))
1423 niter
->niter
= build_int_cst (unsigned_type_for (type
), 0);
1428 /* OK, now we know we have a senseful loop. Handle several cases, depending
1429 on what comparison operator is used. */
1430 bound_difference (loop
, iv1
->base
, iv0
->base
, &bnds
);
1432 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1435 "Analyzing # of iterations of loop %d\n", loop
->num
);
1437 fprintf (dump_file
, " exit condition ");
1438 dump_affine_iv (dump_file
, iv0
);
1439 fprintf (dump_file
, " %s ",
1440 code
== NE_EXPR
? "!="
1441 : code
== LT_EXPR
? "<"
1443 dump_affine_iv (dump_file
, iv1
);
1444 fprintf (dump_file
, "\n");
1446 fprintf (dump_file
, " bounds on difference of bases: ");
1447 mpz_out_str (dump_file
, 10, bnds
.below
);
1448 fprintf (dump_file
, " ... ");
1449 mpz_out_str (dump_file
, 10, bnds
.up
);
1450 fprintf (dump_file
, "\n");
1456 gcc_assert (integer_zerop (iv1
->step
));
1457 ret
= number_of_iterations_ne (type
, iv0
, iv1
->base
, niter
,
1458 exit_must_be_taken
, &bnds
);
1462 ret
= number_of_iterations_lt (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1467 ret
= number_of_iterations_le (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1475 mpz_clear (bnds
.up
);
1476 mpz_clear (bnds
.below
);
1478 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1482 fprintf (dump_file
, " result:\n");
1483 if (!integer_nonzerop (niter
->assumptions
))
1485 fprintf (dump_file
, " under assumptions ");
1486 print_generic_expr (dump_file
, niter
->assumptions
, TDF_SLIM
);
1487 fprintf (dump_file
, "\n");
1490 if (!integer_zerop (niter
->may_be_zero
))
1492 fprintf (dump_file
, " zero if ");
1493 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
1494 fprintf (dump_file
, "\n");
1497 fprintf (dump_file
, " # of iterations ");
1498 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
1499 fprintf (dump_file
, ", bounded by ");
1500 print_decu (niter
->max
, dump_file
);
1501 fprintf (dump_file
, "\n");
1504 fprintf (dump_file
, " failed\n\n");
1509 /* Substitute NEW for OLD in EXPR and fold the result. */
1512 simplify_replace_tree (tree expr
, tree old
, tree new_tree
)
1515 tree ret
= NULL_TREE
, e
, se
;
1520 /* Do not bother to replace constants. */
1521 if (CONSTANT_CLASS_P (old
))
1525 || operand_equal_p (expr
, old
, 0))
1526 return unshare_expr (new_tree
);
1531 n
= TREE_OPERAND_LENGTH (expr
);
1532 for (i
= 0; i
< n
; i
++)
1534 e
= TREE_OPERAND (expr
, i
);
1535 se
= simplify_replace_tree (e
, old
, new_tree
);
1540 ret
= copy_node (expr
);
1542 TREE_OPERAND (ret
, i
) = se
;
1545 return (ret
? fold (ret
) : expr
);
1548 /* Expand definitions of ssa names in EXPR as long as they are simple
1549 enough, and return the new expression. */
1552 expand_simple_operations (tree expr
)
1555 tree ret
= NULL_TREE
, e
, ee
, e1
;
1556 enum tree_code code
;
1559 if (expr
== NULL_TREE
)
1562 if (is_gimple_min_invariant (expr
))
1565 code
= TREE_CODE (expr
);
1566 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
1568 n
= TREE_OPERAND_LENGTH (expr
);
1569 for (i
= 0; i
< n
; i
++)
1571 e
= TREE_OPERAND (expr
, i
);
1572 ee
= expand_simple_operations (e
);
1577 ret
= copy_node (expr
);
1579 TREE_OPERAND (ret
, i
) = ee
;
1585 fold_defer_overflow_warnings ();
1587 fold_undefer_and_ignore_overflow_warnings ();
1591 if (TREE_CODE (expr
) != SSA_NAME
)
1594 stmt
= SSA_NAME_DEF_STMT (expr
);
1595 if (gimple_code (stmt
) == GIMPLE_PHI
)
1597 basic_block src
, dest
;
1599 if (gimple_phi_num_args (stmt
) != 1)
1601 e
= PHI_ARG_DEF (stmt
, 0);
1603 /* Avoid propagating through loop exit phi nodes, which
1604 could break loop-closed SSA form restrictions. */
1605 dest
= gimple_bb (stmt
);
1606 src
= single_pred (dest
);
1607 if (TREE_CODE (e
) == SSA_NAME
1608 && src
->loop_father
!= dest
->loop_father
)
1611 return expand_simple_operations (e
);
1613 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1616 /* Avoid expanding to expressions that contain SSA names that need
1617 to take part in abnormal coalescing. */
1619 FOR_EACH_SSA_TREE_OPERAND (e
, stmt
, iter
, SSA_OP_USE
)
1620 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (e
))
1623 e
= gimple_assign_rhs1 (stmt
);
1624 code
= gimple_assign_rhs_code (stmt
);
1625 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1627 if (is_gimple_min_invariant (e
))
1630 if (code
== SSA_NAME
)
1631 return expand_simple_operations (e
);
1639 /* Casts are simple. */
1640 ee
= expand_simple_operations (e
);
1641 return fold_build1 (code
, TREE_TYPE (expr
), ee
);
1645 if (TYPE_OVERFLOW_TRAPS (TREE_TYPE (expr
)))
1648 case POINTER_PLUS_EXPR
:
1649 /* And increments and decrements by a constant are simple. */
1650 e1
= gimple_assign_rhs2 (stmt
);
1651 if (!is_gimple_min_invariant (e1
))
1654 ee
= expand_simple_operations (e
);
1655 return fold_build2 (code
, TREE_TYPE (expr
), ee
, e1
);
1662 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1663 expression (or EXPR unchanged, if no simplification was possible). */
1666 tree_simplify_using_condition_1 (tree cond
, tree expr
)
1669 tree e
, te
, e0
, e1
, e2
, notcond
;
1670 enum tree_code code
= TREE_CODE (expr
);
1672 if (code
== INTEGER_CST
)
1675 if (code
== TRUTH_OR_EXPR
1676 || code
== TRUTH_AND_EXPR
1677 || code
== COND_EXPR
)
1681 e0
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 0));
1682 if (TREE_OPERAND (expr
, 0) != e0
)
1685 e1
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 1));
1686 if (TREE_OPERAND (expr
, 1) != e1
)
1689 if (code
== COND_EXPR
)
1691 e2
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 2));
1692 if (TREE_OPERAND (expr
, 2) != e2
)
1700 if (code
== COND_EXPR
)
1701 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1703 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1709 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
1710 propagation, and vice versa. Fold does not handle this, since it is
1711 considered too expensive. */
1712 if (TREE_CODE (cond
) == EQ_EXPR
)
1714 e0
= TREE_OPERAND (cond
, 0);
1715 e1
= TREE_OPERAND (cond
, 1);
1717 /* We know that e0 == e1. Check whether we cannot simplify expr
1719 e
= simplify_replace_tree (expr
, e0
, e1
);
1720 if (integer_zerop (e
) || integer_nonzerop (e
))
1723 e
= simplify_replace_tree (expr
, e1
, e0
);
1724 if (integer_zerop (e
) || integer_nonzerop (e
))
1727 if (TREE_CODE (expr
) == EQ_EXPR
)
1729 e0
= TREE_OPERAND (expr
, 0);
1730 e1
= TREE_OPERAND (expr
, 1);
1732 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
1733 e
= simplify_replace_tree (cond
, e0
, e1
);
1734 if (integer_zerop (e
))
1736 e
= simplify_replace_tree (cond
, e1
, e0
);
1737 if (integer_zerop (e
))
1740 if (TREE_CODE (expr
) == NE_EXPR
)
1742 e0
= TREE_OPERAND (expr
, 0);
1743 e1
= TREE_OPERAND (expr
, 1);
1745 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
1746 e
= simplify_replace_tree (cond
, e0
, e1
);
1747 if (integer_zerop (e
))
1748 return boolean_true_node
;
1749 e
= simplify_replace_tree (cond
, e1
, e0
);
1750 if (integer_zerop (e
))
1751 return boolean_true_node
;
1754 te
= expand_simple_operations (expr
);
1756 /* Check whether COND ==> EXPR. */
1757 notcond
= invert_truthvalue (cond
);
1758 e
= fold_binary (TRUTH_OR_EXPR
, boolean_type_node
, notcond
, te
);
1759 if (e
&& integer_nonzerop (e
))
1762 /* Check whether COND ==> not EXPR. */
1763 e
= fold_binary (TRUTH_AND_EXPR
, boolean_type_node
, cond
, te
);
1764 if (e
&& integer_zerop (e
))
1770 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1771 expression (or EXPR unchanged, if no simplification was possible).
1772 Wrapper around tree_simplify_using_condition_1 that ensures that chains
1773 of simple operations in definitions of ssa names in COND are expanded,
1774 so that things like casts or incrementing the value of the bound before
1775 the loop do not cause us to fail. */
1778 tree_simplify_using_condition (tree cond
, tree expr
)
1780 cond
= expand_simple_operations (cond
);
1782 return tree_simplify_using_condition_1 (cond
, expr
);
1785 /* Tries to simplify EXPR using the conditions on entry to LOOP.
1786 Returns the simplified expression (or EXPR unchanged, if no
1787 simplification was possible).*/
1790 simplify_using_initial_conditions (struct loop
*loop
, tree expr
)
1798 if (TREE_CODE (expr
) == INTEGER_CST
)
1801 /* Limit walking the dominators to avoid quadraticness in
1802 the number of BBs times the number of loops in degenerate
1804 for (bb
= loop
->header
;
1805 bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && cnt
< MAX_DOMINATORS_TO_WALK
;
1806 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1808 if (!single_pred_p (bb
))
1810 e
= single_pred_edge (bb
);
1812 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
1815 stmt
= last_stmt (e
->src
);
1816 cond
= fold_build2 (gimple_cond_code (stmt
),
1818 gimple_cond_lhs (stmt
),
1819 gimple_cond_rhs (stmt
));
1820 if (e
->flags
& EDGE_FALSE_VALUE
)
1821 cond
= invert_truthvalue (cond
);
1822 expr
= tree_simplify_using_condition (cond
, expr
);
1829 /* Tries to simplify EXPR using the evolutions of the loop invariants
1830 in the superloops of LOOP. Returns the simplified expression
1831 (or EXPR unchanged, if no simplification was possible). */
1834 simplify_using_outer_evolutions (struct loop
*loop
, tree expr
)
1836 enum tree_code code
= TREE_CODE (expr
);
1840 if (is_gimple_min_invariant (expr
))
1843 if (code
== TRUTH_OR_EXPR
1844 || code
== TRUTH_AND_EXPR
1845 || code
== COND_EXPR
)
1849 e0
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 0));
1850 if (TREE_OPERAND (expr
, 0) != e0
)
1853 e1
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 1));
1854 if (TREE_OPERAND (expr
, 1) != e1
)
1857 if (code
== COND_EXPR
)
1859 e2
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 2));
1860 if (TREE_OPERAND (expr
, 2) != e2
)
1868 if (code
== COND_EXPR
)
1869 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1871 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1877 e
= instantiate_parameters (loop
, expr
);
1878 if (is_gimple_min_invariant (e
))
1884 /* Returns true if EXIT is the only possible exit from LOOP. */
1887 loop_only_exit_p (const struct loop
*loop
, const_edge exit
)
1890 gimple_stmt_iterator bsi
;
1894 if (exit
!= single_exit (loop
))
1897 body
= get_loop_body (loop
);
1898 for (i
= 0; i
< loop
->num_nodes
; i
++)
1900 for (bsi
= gsi_start_bb (body
[i
]); !gsi_end_p (bsi
); gsi_next (&bsi
))
1902 call
= gsi_stmt (bsi
);
1903 if (gimple_code (call
) != GIMPLE_CALL
)
1906 if (gimple_has_side_effects (call
))
1918 /* Stores description of number of iterations of LOOP derived from
1919 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
1920 useful information could be derived (and fields of NITER has
1921 meaning described in comments at struct tree_niter_desc
1922 declaration), false otherwise. If WARN is true and
1923 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1924 potentially unsafe assumptions.
1925 When EVERY_ITERATION is true, only tests that are known to be executed
1926 every iteration are considered (i.e. only test that alone bounds the loop).
1930 number_of_iterations_exit (struct loop
*loop
, edge exit
,
1931 struct tree_niter_desc
*niter
,
1932 bool warn
, bool every_iteration
)
1938 enum tree_code code
;
1942 safe
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit
->src
);
1944 if (every_iteration
&& !safe
)
1947 niter
->assumptions
= boolean_false_node
;
1948 last
= last_stmt (exit
->src
);
1951 stmt
= dyn_cast
<gcond
*> (last
);
1955 /* We want the condition for staying inside loop. */
1956 code
= gimple_cond_code (stmt
);
1957 if (exit
->flags
& EDGE_TRUE_VALUE
)
1958 code
= invert_tree_comparison (code
, false);
1973 op0
= gimple_cond_lhs (stmt
);
1974 op1
= gimple_cond_rhs (stmt
);
1975 type
= TREE_TYPE (op0
);
1977 if (TREE_CODE (type
) != INTEGER_TYPE
1978 && !POINTER_TYPE_P (type
))
1981 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, false))
1983 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, false))
1986 /* We don't want to see undefined signed overflow warnings while
1987 computing the number of iterations. */
1988 fold_defer_overflow_warnings ();
1990 iv0
.base
= expand_simple_operations (iv0
.base
);
1991 iv1
.base
= expand_simple_operations (iv1
.base
);
1992 if (!number_of_iterations_cond (loop
, type
, &iv0
, code
, &iv1
, niter
,
1993 loop_only_exit_p (loop
, exit
), safe
))
1995 fold_undefer_and_ignore_overflow_warnings ();
2001 niter
->assumptions
= simplify_using_outer_evolutions (loop
,
2002 niter
->assumptions
);
2003 niter
->may_be_zero
= simplify_using_outer_evolutions (loop
,
2004 niter
->may_be_zero
);
2005 niter
->niter
= simplify_using_outer_evolutions (loop
, niter
->niter
);
2009 = simplify_using_initial_conditions (loop
,
2010 niter
->assumptions
);
2012 = simplify_using_initial_conditions (loop
,
2013 niter
->may_be_zero
);
2015 fold_undefer_and_ignore_overflow_warnings ();
2017 /* If NITER has simplified into a constant, update MAX. */
2018 if (TREE_CODE (niter
->niter
) == INTEGER_CST
)
2019 niter
->max
= wi::to_widest (niter
->niter
);
2021 if (integer_onep (niter
->assumptions
))
2024 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
2025 But if we can prove that there is overflow or some other source of weird
2026 behavior, ignore the loop even with -funsafe-loop-optimizations. */
2027 if (integer_zerop (niter
->assumptions
) || !single_exit (loop
))
2030 if (flag_unsafe_loop_optimizations
)
2031 niter
->assumptions
= boolean_true_node
;
2035 const char *wording
;
2036 location_t loc
= gimple_location (stmt
);
2038 /* We can provide a more specific warning if one of the operator is
2039 constant and the other advances by +1 or -1. */
2040 if (!integer_zerop (iv1
.step
)
2041 ? (integer_zerop (iv0
.step
)
2042 && (integer_onep (iv1
.step
) || integer_all_onesp (iv1
.step
)))
2043 : (integer_onep (iv0
.step
) || integer_all_onesp (iv0
.step
)))
2045 flag_unsafe_loop_optimizations
2046 ? N_("assuming that the loop is not infinite")
2047 : N_("cannot optimize possibly infinite loops");
2050 flag_unsafe_loop_optimizations
2051 ? N_("assuming that the loop counter does not overflow")
2052 : N_("cannot optimize loop, the loop counter may overflow");
2054 warning_at ((LOCATION_LINE (loc
) > 0) ? loc
: input_location
,
2055 OPT_Wunsafe_loop_optimizations
, "%s", gettext (wording
));
2058 return flag_unsafe_loop_optimizations
;
2061 /* Try to determine the number of iterations of LOOP. If we succeed,
2062 expression giving number of iterations is returned and *EXIT is
2063 set to the edge from that the information is obtained. Otherwise
2064 chrec_dont_know is returned. */
2067 find_loop_niter (struct loop
*loop
, edge
*exit
)
2070 vec
<edge
> exits
= get_loop_exit_edges (loop
);
2072 tree niter
= NULL_TREE
, aniter
;
2073 struct tree_niter_desc desc
;
2076 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2078 if (!number_of_iterations_exit (loop
, ex
, &desc
, false))
2081 if (integer_nonzerop (desc
.may_be_zero
))
2083 /* We exit in the first iteration through this exit.
2084 We won't find anything better. */
2085 niter
= build_int_cst (unsigned_type_node
, 0);
2090 if (!integer_zerop (desc
.may_be_zero
))
2093 aniter
= desc
.niter
;
2097 /* Nothing recorded yet. */
2103 /* Prefer constants, the lower the better. */
2104 if (TREE_CODE (aniter
) != INTEGER_CST
)
2107 if (TREE_CODE (niter
) != INTEGER_CST
)
2114 if (tree_int_cst_lt (aniter
, niter
))
2123 return niter
? niter
: chrec_dont_know
;
2126 /* Return true if loop is known to have bounded number of iterations. */
2129 finite_loop_p (struct loop
*loop
)
2134 if (flag_unsafe_loop_optimizations
)
2136 flags
= flags_from_decl_or_type (current_function_decl
);
2137 if ((flags
& (ECF_CONST
|ECF_PURE
)) && !(flags
& ECF_LOOPING_CONST_OR_PURE
))
2139 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2140 fprintf (dump_file
, "Found loop %i to be finite: it is within pure or const function.\n",
2145 if (loop
->any_upper_bound
2146 || max_loop_iterations (loop
, &nit
))
2148 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2149 fprintf (dump_file
, "Found loop %i to be finite: upper bound found.\n",
2158 Analysis of a number of iterations of a loop by a brute-force evaluation.
2162 /* Bound on the number of iterations we try to evaluate. */
2164 #define MAX_ITERATIONS_TO_TRACK \
2165 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
2167 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
2168 result by a chain of operations such that all but exactly one of their
2169 operands are constants. */
2172 chain_of_csts_start (struct loop
*loop
, tree x
)
2174 gimple stmt
= SSA_NAME_DEF_STMT (x
);
2176 basic_block bb
= gimple_bb (stmt
);
2177 enum tree_code code
;
2180 || !flow_bb_inside_loop_p (loop
, bb
))
2183 if (gimple_code (stmt
) == GIMPLE_PHI
)
2185 if (bb
== loop
->header
)
2186 return as_a
<gphi
*> (stmt
);
2191 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2192 || gimple_assign_rhs_class (stmt
) == GIMPLE_TERNARY_RHS
)
2195 code
= gimple_assign_rhs_code (stmt
);
2196 if (gimple_references_memory_p (stmt
)
2197 || TREE_CODE_CLASS (code
) == tcc_reference
2198 || (code
== ADDR_EXPR
2199 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
2202 use
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
2203 if (use
== NULL_TREE
)
2206 return chain_of_csts_start (loop
, use
);
2209 /* Determines whether the expression X is derived from a result of a phi node
2210 in header of LOOP such that
2212 * the derivation of X consists only from operations with constants
2213 * the initial value of the phi node is constant
2214 * the value of the phi node in the next iteration can be derived from the
2215 value in the current iteration by a chain of operations with constants.
2217 If such phi node exists, it is returned, otherwise NULL is returned. */
2220 get_base_for (struct loop
*loop
, tree x
)
2225 if (is_gimple_min_invariant (x
))
2228 phi
= chain_of_csts_start (loop
, x
);
2232 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2233 next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2235 if (TREE_CODE (next
) != SSA_NAME
)
2238 if (!is_gimple_min_invariant (init
))
2241 if (chain_of_csts_start (loop
, next
) != phi
)
2247 /* Given an expression X, then
2249 * if X is NULL_TREE, we return the constant BASE.
2250 * otherwise X is a SSA name, whose value in the considered loop is derived
2251 by a chain of operations with constant from a result of a phi node in
2252 the header of the loop. Then we return value of X when the value of the
2253 result of this phi node is given by the constant BASE. */
2256 get_val_for (tree x
, tree base
)
2260 gcc_checking_assert (is_gimple_min_invariant (base
));
2265 stmt
= SSA_NAME_DEF_STMT (x
);
2266 if (gimple_code (stmt
) == GIMPLE_PHI
)
2269 gcc_checking_assert (is_gimple_assign (stmt
));
2271 /* STMT must be either an assignment of a single SSA name or an
2272 expression involving an SSA name and a constant. Try to fold that
2273 expression using the value for the SSA name. */
2274 if (gimple_assign_ssa_name_copy_p (stmt
))
2275 return get_val_for (gimple_assign_rhs1 (stmt
), base
);
2276 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_UNARY_RHS
2277 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
2279 return fold_build1 (gimple_assign_rhs_code (stmt
),
2280 gimple_expr_type (stmt
),
2281 get_val_for (gimple_assign_rhs1 (stmt
), base
));
2283 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_BINARY_RHS
)
2285 tree rhs1
= gimple_assign_rhs1 (stmt
);
2286 tree rhs2
= gimple_assign_rhs2 (stmt
);
2287 if (TREE_CODE (rhs1
) == SSA_NAME
)
2288 rhs1
= get_val_for (rhs1
, base
);
2289 else if (TREE_CODE (rhs2
) == SSA_NAME
)
2290 rhs2
= get_val_for (rhs2
, base
);
2293 return fold_build2 (gimple_assign_rhs_code (stmt
),
2294 gimple_expr_type (stmt
), rhs1
, rhs2
);
2301 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2302 by brute force -- i.e. by determining the value of the operands of the
2303 condition at EXIT in first few iterations of the loop (assuming that
2304 these values are constant) and determining the first one in that the
2305 condition is not satisfied. Returns the constant giving the number
2306 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
2309 loop_niter_by_eval (struct loop
*loop
, edge exit
)
2312 tree op
[2], val
[2], next
[2], aval
[2];
2318 cond
= last_stmt (exit
->src
);
2319 if (!cond
|| gimple_code (cond
) != GIMPLE_COND
)
2320 return chrec_dont_know
;
2322 cmp
= gimple_cond_code (cond
);
2323 if (exit
->flags
& EDGE_TRUE_VALUE
)
2324 cmp
= invert_tree_comparison (cmp
, false);
2334 op
[0] = gimple_cond_lhs (cond
);
2335 op
[1] = gimple_cond_rhs (cond
);
2339 return chrec_dont_know
;
2342 for (j
= 0; j
< 2; j
++)
2344 if (is_gimple_min_invariant (op
[j
]))
2347 next
[j
] = NULL_TREE
;
2352 phi
= get_base_for (loop
, op
[j
]);
2354 return chrec_dont_know
;
2355 val
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2356 next
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2360 /* Don't issue signed overflow warnings. */
2361 fold_defer_overflow_warnings ();
2363 for (i
= 0; i
< MAX_ITERATIONS_TO_TRACK
; i
++)
2365 for (j
= 0; j
< 2; j
++)
2366 aval
[j
] = get_val_for (op
[j
], val
[j
]);
2368 acnd
= fold_binary (cmp
, boolean_type_node
, aval
[0], aval
[1]);
2369 if (acnd
&& integer_zerop (acnd
))
2371 fold_undefer_and_ignore_overflow_warnings ();
2372 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2374 "Proved that loop %d iterates %d times using brute force.\n",
2376 return build_int_cst (unsigned_type_node
, i
);
2379 for (j
= 0; j
< 2; j
++)
2381 val
[j
] = get_val_for (next
[j
], val
[j
]);
2382 if (!is_gimple_min_invariant (val
[j
]))
2384 fold_undefer_and_ignore_overflow_warnings ();
2385 return chrec_dont_know
;
2390 fold_undefer_and_ignore_overflow_warnings ();
2392 return chrec_dont_know
;
2395 /* Finds the exit of the LOOP by that the loop exits after a constant
2396 number of iterations and stores the exit edge to *EXIT. The constant
2397 giving the number of iterations of LOOP is returned. The number of
2398 iterations is determined using loop_niter_by_eval (i.e. by brute force
2399 evaluation). If we are unable to find the exit for that loop_niter_by_eval
2400 determines the number of iterations, chrec_dont_know is returned. */
2403 find_loop_niter_by_eval (struct loop
*loop
, edge
*exit
)
2406 vec
<edge
> exits
= get_loop_exit_edges (loop
);
2408 tree niter
= NULL_TREE
, aniter
;
2412 /* Loops with multiple exits are expensive to handle and less important. */
2413 if (!flag_expensive_optimizations
2414 && exits
.length () > 1)
2417 return chrec_dont_know
;
2420 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2422 if (!just_once_each_iteration_p (loop
, ex
->src
))
2425 aniter
= loop_niter_by_eval (loop
, ex
);
2426 if (chrec_contains_undetermined (aniter
))
2430 && !tree_int_cst_lt (aniter
, niter
))
2438 return niter
? niter
: chrec_dont_know
;
2443 Analysis of upper bounds on number of iterations of a loop.
2447 static widest_int
derive_constant_upper_bound_ops (tree
, tree
,
2448 enum tree_code
, tree
);
2450 /* Returns a constant upper bound on the value of the right-hand side of
2451 an assignment statement STMT. */
2454 derive_constant_upper_bound_assign (gimple stmt
)
2456 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2457 tree op0
= gimple_assign_rhs1 (stmt
);
2458 tree op1
= gimple_assign_rhs2 (stmt
);
2460 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt
)),
2464 /* Returns a constant upper bound on the value of expression VAL. VAL
2465 is considered to be unsigned. If its type is signed, its value must
2469 derive_constant_upper_bound (tree val
)
2471 enum tree_code code
;
2474 extract_ops_from_tree (val
, &code
, &op0
, &op1
);
2475 return derive_constant_upper_bound_ops (TREE_TYPE (val
), op0
, code
, op1
);
2478 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
2479 whose type is TYPE. The expression is considered to be unsigned. If
2480 its type is signed, its value must be nonnegative. */
2483 derive_constant_upper_bound_ops (tree type
, tree op0
,
2484 enum tree_code code
, tree op1
)
2487 widest_int bnd
, max
, mmax
, cst
;
2490 if (INTEGRAL_TYPE_P (type
))
2491 maxt
= TYPE_MAX_VALUE (type
);
2493 maxt
= upper_bound_in_type (type
, type
);
2495 max
= wi::to_widest (maxt
);
2500 return wi::to_widest (op0
);
2503 subtype
= TREE_TYPE (op0
);
2504 if (!TYPE_UNSIGNED (subtype
)
2505 /* If TYPE is also signed, the fact that VAL is nonnegative implies
2506 that OP0 is nonnegative. */
2507 && TYPE_UNSIGNED (type
)
2508 && !tree_expr_nonnegative_p (op0
))
2510 /* If we cannot prove that the casted expression is nonnegative,
2511 we cannot establish more useful upper bound than the precision
2512 of the type gives us. */
2516 /* We now know that op0 is an nonnegative value. Try deriving an upper
2518 bnd
= derive_constant_upper_bound (op0
);
2520 /* If the bound does not fit in TYPE, max. value of TYPE could be
2522 if (wi::ltu_p (max
, bnd
))
2528 case POINTER_PLUS_EXPR
:
2530 if (TREE_CODE (op1
) != INTEGER_CST
2531 || !tree_expr_nonnegative_p (op0
))
2534 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
2535 choose the most logical way how to treat this constant regardless
2536 of the signedness of the type. */
2537 cst
= wi::sext (wi::to_widest (op1
), TYPE_PRECISION (type
));
2538 if (code
!= MINUS_EXPR
)
2541 bnd
= derive_constant_upper_bound (op0
);
2543 if (wi::neg_p (cst
))
2546 /* Avoid CST == 0x80000... */
2547 if (wi::neg_p (cst
))
2550 /* OP0 + CST. We need to check that
2551 BND <= MAX (type) - CST. */
2554 if (wi::ltu_p (bnd
, max
))
2561 /* OP0 - CST, where CST >= 0.
2563 If TYPE is signed, we have already verified that OP0 >= 0, and we
2564 know that the result is nonnegative. This implies that
2567 If TYPE is unsigned, we must additionally know that OP0 >= CST,
2568 otherwise the operation underflows.
2571 /* This should only happen if the type is unsigned; however, for
2572 buggy programs that use overflowing signed arithmetics even with
2573 -fno-wrapv, this condition may also be true for signed values. */
2574 if (wi::ltu_p (bnd
, cst
))
2577 if (TYPE_UNSIGNED (type
))
2579 tree tem
= fold_binary (GE_EXPR
, boolean_type_node
, op0
,
2580 wide_int_to_tree (type
, cst
));
2581 if (!tem
|| integer_nonzerop (tem
))
2590 case FLOOR_DIV_EXPR
:
2591 case EXACT_DIV_EXPR
:
2592 if (TREE_CODE (op1
) != INTEGER_CST
2593 || tree_int_cst_sign_bit (op1
))
2596 bnd
= derive_constant_upper_bound (op0
);
2597 return wi::udiv_floor (bnd
, wi::to_widest (op1
));
2600 if (TREE_CODE (op1
) != INTEGER_CST
2601 || tree_int_cst_sign_bit (op1
))
2603 return wi::to_widest (op1
);
2606 stmt
= SSA_NAME_DEF_STMT (op0
);
2607 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2608 || gimple_assign_lhs (stmt
) != op0
)
2610 return derive_constant_upper_bound_assign (stmt
);
2617 /* Emit a -Waggressive-loop-optimizations warning if needed. */
2620 do_warn_aggressive_loop_optimizations (struct loop
*loop
,
2621 widest_int i_bound
, gimple stmt
)
2623 /* Don't warn if the loop doesn't have known constant bound. */
2624 if (!loop
->nb_iterations
2625 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
2626 || !warn_aggressive_loop_optimizations
2627 /* To avoid warning multiple times for the same loop,
2628 only start warning when we preserve loops. */
2629 || (cfun
->curr_properties
& PROP_loops
) == 0
2630 /* Only warn once per loop. */
2631 || loop
->warned_aggressive_loop_optimizations
2632 /* Only warn if undefined behavior gives us lower estimate than the
2633 known constant bound. */
2634 || wi::cmpu (i_bound
, wi::to_widest (loop
->nb_iterations
)) >= 0
2635 /* And undefined behavior happens unconditionally. */
2636 || !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (stmt
)))
2639 edge e
= single_exit (loop
);
2643 gimple estmt
= last_stmt (e
->src
);
2644 if (warning_at (gimple_location (stmt
), OPT_Waggressive_loop_optimizations
,
2645 "iteration %E invokes undefined behavior",
2646 wide_int_to_tree (TREE_TYPE (loop
->nb_iterations
),
2648 inform (gimple_location (estmt
), "containing loop");
2649 loop
->warned_aggressive_loop_optimizations
= true;
2652 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
2653 is true if the loop is exited immediately after STMT, and this exit
2654 is taken at last when the STMT is executed BOUND + 1 times.
2655 REALISTIC is true if BOUND is expected to be close to the real number
2656 of iterations. UPPER is true if we are sure the loop iterates at most
2657 BOUND times. I_BOUND is a widest_int upper estimate on BOUND. */
2660 record_estimate (struct loop
*loop
, tree bound
, const widest_int
&i_bound
,
2661 gimple at_stmt
, bool is_exit
, bool realistic
, bool upper
)
2665 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2667 fprintf (dump_file
, "Statement %s", is_exit
? "(exit)" : "");
2668 print_gimple_stmt (dump_file
, at_stmt
, 0, TDF_SLIM
);
2669 fprintf (dump_file
, " is %sexecuted at most ",
2670 upper
? "" : "probably ");
2671 print_generic_expr (dump_file
, bound
, TDF_SLIM
);
2672 fprintf (dump_file
, " (bounded by ");
2673 print_decu (i_bound
, dump_file
);
2674 fprintf (dump_file
, ") + 1 times in loop %d.\n", loop
->num
);
2677 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
2678 real number of iterations. */
2679 if (TREE_CODE (bound
) != INTEGER_CST
)
2682 gcc_checking_assert (i_bound
== wi::to_widest (bound
));
2683 if (!upper
&& !realistic
)
2686 /* If we have a guaranteed upper bound, record it in the appropriate
2687 list, unless this is an !is_exit bound (i.e. undefined behavior in
2688 at_stmt) in a loop with known constant number of iterations. */
2691 || loop
->nb_iterations
== NULL_TREE
2692 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
))
2694 struct nb_iter_bound
*elt
= ggc_alloc
<nb_iter_bound
> ();
2696 elt
->bound
= i_bound
;
2697 elt
->stmt
= at_stmt
;
2698 elt
->is_exit
= is_exit
;
2699 elt
->next
= loop
->bounds
;
2703 /* If statement is executed on every path to the loop latch, we can directly
2704 infer the upper bound on the # of iterations of the loop. */
2705 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (at_stmt
)))
2708 /* Update the number of iteration estimates according to the bound.
2709 If at_stmt is an exit then the loop latch is executed at most BOUND times,
2710 otherwise it can be executed BOUND + 1 times. We will lower the estimate
2711 later if such statement must be executed on last iteration */
2716 widest_int new_i_bound
= i_bound
+ delta
;
2718 /* If an overflow occurred, ignore the result. */
2719 if (wi::ltu_p (new_i_bound
, delta
))
2722 if (upper
&& !is_exit
)
2723 do_warn_aggressive_loop_optimizations (loop
, new_i_bound
, at_stmt
);
2724 record_niter_bound (loop
, new_i_bound
, realistic
, upper
);
2727 /* Record the estimate on number of iterations of LOOP based on the fact that
2728 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
2729 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
2730 estimated number of iterations is expected to be close to the real one.
2731 UPPER is true if we are sure the induction variable does not wrap. */
2734 record_nonwrapping_iv (struct loop
*loop
, tree base
, tree step
, gimple stmt
,
2735 tree low
, tree high
, bool realistic
, bool upper
)
2737 tree niter_bound
, extreme
, delta
;
2738 tree type
= TREE_TYPE (base
), unsigned_type
;
2740 if (TREE_CODE (step
) != INTEGER_CST
|| integer_zerop (step
))
2743 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2745 fprintf (dump_file
, "Induction variable (");
2746 print_generic_expr (dump_file
, TREE_TYPE (base
), TDF_SLIM
);
2747 fprintf (dump_file
, ") ");
2748 print_generic_expr (dump_file
, base
, TDF_SLIM
);
2749 fprintf (dump_file
, " + ");
2750 print_generic_expr (dump_file
, step
, TDF_SLIM
);
2751 fprintf (dump_file
, " * iteration does not wrap in statement ");
2752 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2753 fprintf (dump_file
, " in loop %d.\n", loop
->num
);
2756 unsigned_type
= unsigned_type_for (type
);
2757 base
= fold_convert (unsigned_type
, base
);
2758 step
= fold_convert (unsigned_type
, step
);
2760 if (tree_int_cst_sign_bit (step
))
2762 extreme
= fold_convert (unsigned_type
, low
);
2763 if (TREE_CODE (base
) != INTEGER_CST
)
2764 base
= fold_convert (unsigned_type
, high
);
2765 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
2766 step
= fold_build1 (NEGATE_EXPR
, unsigned_type
, step
);
2770 extreme
= fold_convert (unsigned_type
, high
);
2771 if (TREE_CODE (base
) != INTEGER_CST
)
2772 base
= fold_convert (unsigned_type
, low
);
2773 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
2776 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
2777 would get out of the range. */
2778 niter_bound
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step
);
2779 widest_int max
= derive_constant_upper_bound (niter_bound
);
2780 record_estimate (loop
, niter_bound
, max
, stmt
, false, realistic
, upper
);
2783 /* Determine information about number of iterations a LOOP from the index
2784 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
2785 guaranteed to be executed in every iteration of LOOP. Callback for
2795 idx_infer_loop_bounds (tree base
, tree
*idx
, void *dta
)
2797 struct ilb_data
*data
= (struct ilb_data
*) dta
;
2798 tree ev
, init
, step
;
2799 tree low
, high
, type
, next
;
2800 bool sign
, upper
= true, at_end
= false;
2801 struct loop
*loop
= data
->loop
;
2802 bool reliable
= true;
2804 if (TREE_CODE (base
) != ARRAY_REF
)
2807 /* For arrays at the end of the structure, we are not guaranteed that they
2808 do not really extend over their declared size. However, for arrays of
2809 size greater than one, this is unlikely to be intended. */
2810 if (array_at_struct_end_p (base
))
2816 struct loop
*dloop
= loop_containing_stmt (data
->stmt
);
2820 ev
= analyze_scalar_evolution (dloop
, *idx
);
2821 ev
= instantiate_parameters (loop
, ev
);
2822 init
= initial_condition (ev
);
2823 step
= evolution_part_in_loop_num (ev
, loop
->num
);
2827 || TREE_CODE (step
) != INTEGER_CST
2828 || integer_zerop (step
)
2829 || tree_contains_chrecs (init
, NULL
)
2830 || chrec_contains_symbols_defined_in_loop (init
, loop
->num
))
2833 low
= array_ref_low_bound (base
);
2834 high
= array_ref_up_bound (base
);
2836 /* The case of nonconstant bounds could be handled, but it would be
2838 if (TREE_CODE (low
) != INTEGER_CST
2840 || TREE_CODE (high
) != INTEGER_CST
)
2842 sign
= tree_int_cst_sign_bit (step
);
2843 type
= TREE_TYPE (step
);
2845 /* The array of length 1 at the end of a structure most likely extends
2846 beyond its bounds. */
2848 && operand_equal_p (low
, high
, 0))
2851 /* In case the relevant bound of the array does not fit in type, or
2852 it does, but bound + step (in type) still belongs into the range of the
2853 array, the index may wrap and still stay within the range of the array
2854 (consider e.g. if the array is indexed by the full range of
2857 To make things simpler, we require both bounds to fit into type, although
2858 there are cases where this would not be strictly necessary. */
2859 if (!int_fits_type_p (high
, type
)
2860 || !int_fits_type_p (low
, type
))
2862 low
= fold_convert (type
, low
);
2863 high
= fold_convert (type
, high
);
2866 next
= fold_binary (PLUS_EXPR
, type
, low
, step
);
2868 next
= fold_binary (PLUS_EXPR
, type
, high
, step
);
2870 if (tree_int_cst_compare (low
, next
) <= 0
2871 && tree_int_cst_compare (next
, high
) <= 0)
2874 /* If access is not executed on every iteration, we must ensure that overlow may
2875 not make the access valid later. */
2876 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (data
->stmt
))
2877 && scev_probably_wraps_p (initial_condition_in_loop_num (ev
, loop
->num
),
2878 step
, data
->stmt
, loop
, true))
2881 record_nonwrapping_iv (loop
, init
, step
, data
->stmt
, low
, high
, reliable
, upper
);
2885 /* Determine information about number of iterations a LOOP from the bounds
2886 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
2887 STMT is guaranteed to be executed in every iteration of LOOP.*/
2890 infer_loop_bounds_from_ref (struct loop
*loop
, gimple stmt
, tree ref
)
2892 struct ilb_data data
;
2896 for_each_index (&ref
, idx_infer_loop_bounds
, &data
);
2899 /* Determine information about number of iterations of a LOOP from the way
2900 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
2901 executed in every iteration of LOOP. */
2904 infer_loop_bounds_from_array (struct loop
*loop
, gimple stmt
)
2906 if (is_gimple_assign (stmt
))
2908 tree op0
= gimple_assign_lhs (stmt
);
2909 tree op1
= gimple_assign_rhs1 (stmt
);
2911 /* For each memory access, analyze its access function
2912 and record a bound on the loop iteration domain. */
2913 if (REFERENCE_CLASS_P (op0
))
2914 infer_loop_bounds_from_ref (loop
, stmt
, op0
);
2916 if (REFERENCE_CLASS_P (op1
))
2917 infer_loop_bounds_from_ref (loop
, stmt
, op1
);
2919 else if (is_gimple_call (stmt
))
2922 unsigned i
, n
= gimple_call_num_args (stmt
);
2924 lhs
= gimple_call_lhs (stmt
);
2925 if (lhs
&& REFERENCE_CLASS_P (lhs
))
2926 infer_loop_bounds_from_ref (loop
, stmt
, lhs
);
2928 for (i
= 0; i
< n
; i
++)
2930 arg
= gimple_call_arg (stmt
, i
);
2931 if (REFERENCE_CLASS_P (arg
))
2932 infer_loop_bounds_from_ref (loop
, stmt
, arg
);
2937 /* Determine information about number of iterations of a LOOP from the fact
2938 that pointer arithmetics in STMT does not overflow. */
2941 infer_loop_bounds_from_pointer_arith (struct loop
*loop
, gimple stmt
)
2943 tree def
, base
, step
, scev
, type
, low
, high
;
2946 if (!is_gimple_assign (stmt
)
2947 || gimple_assign_rhs_code (stmt
) != POINTER_PLUS_EXPR
)
2950 def
= gimple_assign_lhs (stmt
);
2951 if (TREE_CODE (def
) != SSA_NAME
)
2954 type
= TREE_TYPE (def
);
2955 if (!nowrap_type_p (type
))
2958 ptr
= gimple_assign_rhs1 (stmt
);
2959 if (!expr_invariant_in_loop_p (loop
, ptr
))
2962 var
= gimple_assign_rhs2 (stmt
);
2963 if (TYPE_PRECISION (type
) != TYPE_PRECISION (TREE_TYPE (var
)))
2966 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
2967 if (chrec_contains_undetermined (scev
))
2970 base
= initial_condition_in_loop_num (scev
, loop
->num
);
2971 step
= evolution_part_in_loop_num (scev
, loop
->num
);
2974 || TREE_CODE (step
) != INTEGER_CST
2975 || tree_contains_chrecs (base
, NULL
)
2976 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
2979 low
= lower_bound_in_type (type
, type
);
2980 high
= upper_bound_in_type (type
, type
);
2982 /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
2983 produce a NULL pointer. The contrary would mean NULL points to an object,
2984 while NULL is supposed to compare unequal with the address of all objects.
2985 Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
2986 NULL pointer since that would mean wrapping, which we assume here not to
2987 happen. So, we can exclude NULL from the valid range of pointer
2989 if (flag_delete_null_pointer_checks
&& int_cst_value (low
) == 0)
2990 low
= build_int_cstu (TREE_TYPE (low
), TYPE_ALIGN_UNIT (TREE_TYPE (type
)));
2992 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
2995 /* Determine information about number of iterations of a LOOP from the fact
2996 that signed arithmetics in STMT does not overflow. */
2999 infer_loop_bounds_from_signedness (struct loop
*loop
, gimple stmt
)
3001 tree def
, base
, step
, scev
, type
, low
, high
;
3003 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
3006 def
= gimple_assign_lhs (stmt
);
3008 if (TREE_CODE (def
) != SSA_NAME
)
3011 type
= TREE_TYPE (def
);
3012 if (!INTEGRAL_TYPE_P (type
)
3013 || !TYPE_OVERFLOW_UNDEFINED (type
))
3016 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
3017 if (chrec_contains_undetermined (scev
))
3020 base
= initial_condition_in_loop_num (scev
, loop
->num
);
3021 step
= evolution_part_in_loop_num (scev
, loop
->num
);
3024 || TREE_CODE (step
) != INTEGER_CST
3025 || tree_contains_chrecs (base
, NULL
)
3026 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
3029 low
= lower_bound_in_type (type
, type
);
3030 high
= upper_bound_in_type (type
, type
);
3032 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
3035 /* The following analyzers are extracting informations on the bounds
3036 of LOOP from the following undefined behaviors:
3038 - data references should not access elements over the statically
3041 - signed variables should not overflow when flag_wrapv is not set.
3045 infer_loop_bounds_from_undefined (struct loop
*loop
)
3049 gimple_stmt_iterator bsi
;
3053 bbs
= get_loop_body (loop
);
3055 for (i
= 0; i
< loop
->num_nodes
; i
++)
3059 /* If BB is not executed in each iteration of the loop, we cannot
3060 use the operations in it to infer reliable upper bound on the
3061 # of iterations of the loop. However, we can use it as a guess.
3062 Reliable guesses come only from array bounds. */
3063 reliable
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
);
3065 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
3067 gimple stmt
= gsi_stmt (bsi
);
3069 infer_loop_bounds_from_array (loop
, stmt
);
3073 infer_loop_bounds_from_signedness (loop
, stmt
);
3074 infer_loop_bounds_from_pointer_arith (loop
, stmt
);
3083 /* Compare wide ints, callback for qsort. */
3086 wide_int_cmp (const void *p1
, const void *p2
)
3088 const widest_int
*d1
= (const widest_int
*) p1
;
3089 const widest_int
*d2
= (const widest_int
*) p2
;
3090 return wi::cmpu (*d1
, *d2
);
3093 /* Return index of BOUND in BOUNDS array sorted in increasing order.
3094 Lookup by binary search. */
3097 bound_index (vec
<widest_int
> bounds
, const widest_int
&bound
)
3099 unsigned int end
= bounds
.length ();
3100 unsigned int begin
= 0;
3102 /* Find a matching index by means of a binary search. */
3103 while (begin
!= end
)
3105 unsigned int middle
= (begin
+ end
) / 2;
3106 widest_int index
= bounds
[middle
];
3110 else if (wi::ltu_p (index
, bound
))
3118 /* We recorded loop bounds only for statements dominating loop latch (and thus
3119 executed each loop iteration). If there are any bounds on statements not
3120 dominating the loop latch we can improve the estimate by walking the loop
3121 body and seeing if every path from loop header to loop latch contains
3122 some bounded statement. */
3125 discover_iteration_bound_by_body_walk (struct loop
*loop
)
3127 struct nb_iter_bound
*elt
;
3128 vec
<widest_int
> bounds
= vNULL
;
3129 vec
<vec
<basic_block
> > queues
= vNULL
;
3130 vec
<basic_block
> queue
= vNULL
;
3131 ptrdiff_t queue_index
;
3132 ptrdiff_t latch_index
= 0;
3134 /* Discover what bounds may interest us. */
3135 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3137 widest_int bound
= elt
->bound
;
3139 /* Exit terminates loop at given iteration, while non-exits produce undefined
3140 effect on the next iteration. */
3144 /* If an overflow occurred, ignore the result. */
3149 if (!loop
->any_upper_bound
3150 || wi::ltu_p (bound
, loop
->nb_iterations_upper_bound
))
3151 bounds
.safe_push (bound
);
3154 /* Exit early if there is nothing to do. */
3155 if (!bounds
.exists ())
3158 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3159 fprintf (dump_file
, " Trying to walk loop body to reduce the bound.\n");
3161 /* Sort the bounds in decreasing order. */
3162 bounds
.qsort (wide_int_cmp
);
3164 /* For every basic block record the lowest bound that is guaranteed to
3165 terminate the loop. */
3167 hash_map
<basic_block
, ptrdiff_t> bb_bounds
;
3168 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3170 widest_int bound
= elt
->bound
;
3174 /* If an overflow occurred, ignore the result. */
3179 if (!loop
->any_upper_bound
3180 || wi::ltu_p (bound
, loop
->nb_iterations_upper_bound
))
3182 ptrdiff_t index
= bound_index (bounds
, bound
);
3183 ptrdiff_t *entry
= bb_bounds
.get (gimple_bb (elt
->stmt
));
3185 bb_bounds
.put (gimple_bb (elt
->stmt
), index
);
3186 else if ((ptrdiff_t)*entry
> index
)
3191 hash_map
<basic_block
, ptrdiff_t> block_priority
;
3193 /* Perform shortest path discovery loop->header ... loop->latch.
3195 The "distance" is given by the smallest loop bound of basic block
3196 present in the path and we look for path with largest smallest bound
3199 To avoid the need for fibonacci heap on double ints we simply compress
3200 double ints into indexes to BOUNDS array and then represent the queue
3201 as arrays of queues for every index.
3202 Index of BOUNDS.length() means that the execution of given BB has
3203 no bounds determined.
3205 VISITED is a pointer map translating basic block into smallest index
3206 it was inserted into the priority queue with. */
3209 /* Start walk in loop header with index set to infinite bound. */
3210 queue_index
= bounds
.length ();
3211 queues
.safe_grow_cleared (queue_index
+ 1);
3212 queue
.safe_push (loop
->header
);
3213 queues
[queue_index
] = queue
;
3214 block_priority
.put (loop
->header
, queue_index
);
3216 for (; queue_index
>= 0; queue_index
--)
3218 if (latch_index
< queue_index
)
3220 while (queues
[queue_index
].length ())
3223 ptrdiff_t bound_index
= queue_index
;
3227 queue
= queues
[queue_index
];
3230 /* OK, we later inserted the BB with lower priority, skip it. */
3231 if (*block_priority
.get (bb
) > queue_index
)
3234 /* See if we can improve the bound. */
3235 ptrdiff_t *entry
= bb_bounds
.get (bb
);
3236 if (entry
&& *entry
< bound_index
)
3237 bound_index
= *entry
;
3239 /* Insert succesors into the queue, watch for latch edge
3240 and record greatest index we saw. */
3241 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3243 bool insert
= false;
3245 if (loop_exit_edge_p (loop
, e
))
3248 if (e
== loop_latch_edge (loop
)
3249 && latch_index
< bound_index
)
3250 latch_index
= bound_index
;
3251 else if (!(entry
= block_priority
.get (e
->dest
)))
3254 block_priority
.put (e
->dest
, bound_index
);
3256 else if (*entry
< bound_index
)
3259 *entry
= bound_index
;
3263 queues
[bound_index
].safe_push (e
->dest
);
3267 queues
[queue_index
].release ();
3270 gcc_assert (latch_index
>= 0);
3271 if ((unsigned)latch_index
< bounds
.length ())
3273 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3275 fprintf (dump_file
, "Found better loop bound ");
3276 print_decu (bounds
[latch_index
], dump_file
);
3277 fprintf (dump_file
, "\n");
3279 record_niter_bound (loop
, bounds
[latch_index
], false, true);
3286 /* See if every path cross the loop goes through a statement that is known
3287 to not execute at the last iteration. In that case we can decrese iteration
3291 maybe_lower_iteration_bound (struct loop
*loop
)
3293 hash_set
<gimple
> *not_executed_last_iteration
= NULL
;
3294 struct nb_iter_bound
*elt
;
3295 bool found_exit
= false;
3296 vec
<basic_block
> queue
= vNULL
;
3297 vec
<gimple
> problem_stmts
= vNULL
;
3300 /* Collect all statements with interesting (i.e. lower than
3301 nb_iterations_upper_bound) bound on them.
3303 TODO: Due to the way record_estimate choose estimates to store, the bounds
3304 will be always nb_iterations_upper_bound-1. We can change this to record
3305 also statements not dominating the loop latch and update the walk bellow
3306 to the shortest path algorthm. */
3307 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3310 && wi::ltu_p (elt
->bound
, loop
->nb_iterations_upper_bound
))
3312 if (!not_executed_last_iteration
)
3313 not_executed_last_iteration
= new hash_set
<gimple
>;
3314 not_executed_last_iteration
->add (elt
->stmt
);
3317 if (!not_executed_last_iteration
)
3320 /* Start DFS walk in the loop header and see if we can reach the
3321 loop latch or any of the exits (including statements with side
3322 effects that may terminate the loop otherwise) without visiting
3323 any of the statements known to have undefined effect on the last
3325 queue
.safe_push (loop
->header
);
3326 visited
= BITMAP_ALLOC (NULL
);
3327 bitmap_set_bit (visited
, loop
->header
->index
);
3332 basic_block bb
= queue
.pop ();
3333 gimple_stmt_iterator gsi
;
3334 bool stmt_found
= false;
3336 /* Loop for possible exits and statements bounding the execution. */
3337 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3339 gimple stmt
= gsi_stmt (gsi
);
3340 if (not_executed_last_iteration
->contains (stmt
))
3343 problem_stmts
.safe_push (stmt
);
3346 if (gimple_has_side_effects (stmt
))
3355 /* If no bounding statement is found, continue the walk. */
3361 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3363 if (loop_exit_edge_p (loop
, e
)
3364 || e
== loop_latch_edge (loop
))
3369 if (bitmap_set_bit (visited
, e
->dest
->index
))
3370 queue
.safe_push (e
->dest
);
3374 while (queue
.length () && !found_exit
);
3376 /* If every path through the loop reach bounding statement before exit,
3377 then we know the last iteration of the loop will have undefined effect
3378 and we can decrease number of iterations. */
3382 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3383 fprintf (dump_file
, "Reducing loop iteration estimate by 1; "
3384 "undefined statement must be executed at the last iteration.\n");
3385 record_niter_bound (loop
, loop
->nb_iterations_upper_bound
- 1,
3388 if (warn_aggressive_loop_optimizations
)
3390 bool exit_warned
= false;
3391 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3394 && wi::gtu_p (elt
->bound
, loop
->nb_iterations_upper_bound
))
3396 basic_block bb
= gimple_bb (elt
->stmt
);
3397 edge exit_edge
= EDGE_SUCC (bb
, 0);
3398 struct tree_niter_desc niter
;
3400 if (!loop_exit_edge_p (loop
, exit_edge
))
3401 exit_edge
= EDGE_SUCC (bb
, 1);
3403 if(number_of_iterations_exit (loop
, exit_edge
,
3404 &niter
, false, false)
3405 && integer_onep (niter
.assumptions
)
3406 && integer_zerop (niter
.may_be_zero
)
3408 && TREE_CODE (niter
.niter
) == INTEGER_CST
3409 && wi::ltu_p (loop
->nb_iterations_upper_bound
,
3410 wi::to_widest (niter
.niter
)))
3412 if (warning_at (gimple_location (elt
->stmt
),
3413 OPT_Waggressive_loop_optimizations
,
3414 "loop exit may only be reached after undefined behavior"))
3420 if (exit_warned
&& !problem_stmts
.empty ())
3424 FOR_EACH_VEC_ELT (problem_stmts
, index
, stmt
)
3425 inform (gimple_location (stmt
),
3426 "possible undefined statement is here");
3431 BITMAP_FREE (visited
);
3433 problem_stmts
.release ();
3434 delete not_executed_last_iteration
;
3437 /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
3438 is true also use estimates derived from undefined behavior. */
3441 estimate_numbers_of_iterations_loop (struct loop
*loop
)
3446 struct tree_niter_desc niter_desc
;
3451 /* Give up if we already have tried to compute an estimation. */
3452 if (loop
->estimate_state
!= EST_NOT_COMPUTED
)
3455 loop
->estimate_state
= EST_AVAILABLE
;
3456 /* Force estimate compuation but leave any existing upper bound in place. */
3457 loop
->any_estimate
= false;
3459 /* Ensure that loop->nb_iterations is computed if possible. If it turns out
3460 to be constant, we avoid undefined behavior implied bounds and instead
3461 diagnose those loops with -Waggressive-loop-optimizations. */
3462 number_of_latch_executions (loop
);
3464 exits
= get_loop_exit_edges (loop
);
3465 likely_exit
= single_likely_exit (loop
);
3466 FOR_EACH_VEC_ELT (exits
, i
, ex
)
3468 if (!number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
3471 niter
= niter_desc
.niter
;
3472 type
= TREE_TYPE (niter
);
3473 if (TREE_CODE (niter_desc
.may_be_zero
) != INTEGER_CST
)
3474 niter
= build3 (COND_EXPR
, type
, niter_desc
.may_be_zero
,
3475 build_int_cst (type
, 0),
3477 record_estimate (loop
, niter
, niter_desc
.max
,
3478 last_stmt (ex
->src
),
3479 true, ex
== likely_exit
, true);
3483 if (flag_aggressive_loop_optimizations
)
3484 infer_loop_bounds_from_undefined (loop
);
3486 discover_iteration_bound_by_body_walk (loop
);
3488 maybe_lower_iteration_bound (loop
);
3490 /* If we have a measured profile, use it to estimate the number of
3492 if (loop
->header
->count
!= 0)
3494 gcov_type nit
= expected_loop_iterations_unbounded (loop
) + 1;
3495 bound
= gcov_type_to_wide_int (nit
);
3496 record_niter_bound (loop
, bound
, true, false);
3499 /* If we know the exact number of iterations of this loop, try to
3500 not break code with undefined behavior by not recording smaller
3501 maximum number of iterations. */
3502 if (loop
->nb_iterations
3503 && TREE_CODE (loop
->nb_iterations
) == INTEGER_CST
)
3505 loop
->any_upper_bound
= true;
3506 loop
->nb_iterations_upper_bound
= wi::to_widest (loop
->nb_iterations
);
3510 /* Sets NIT to the estimated number of executions of the latch of the
3511 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
3512 large as the number of iterations. If we have no reliable estimate,
3513 the function returns false, otherwise returns true. */
3516 estimated_loop_iterations (struct loop
*loop
, widest_int
*nit
)
3518 /* When SCEV information is available, try to update loop iterations
3519 estimate. Otherwise just return whatever we recorded earlier. */
3520 if (scev_initialized_p ())
3521 estimate_numbers_of_iterations_loop (loop
);
3523 return (get_estimated_loop_iterations (loop
, nit
));
3526 /* Similar to estimated_loop_iterations, but returns the estimate only
3527 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3528 on the number of iterations of LOOP could not be derived, returns -1. */
3531 estimated_loop_iterations_int (struct loop
*loop
)
3534 HOST_WIDE_INT hwi_nit
;
3536 if (!estimated_loop_iterations (loop
, &nit
))
3539 if (!wi::fits_shwi_p (nit
))
3541 hwi_nit
= nit
.to_shwi ();
3543 return hwi_nit
< 0 ? -1 : hwi_nit
;
3547 /* Sets NIT to an upper bound for the maximum number of executions of the
3548 latch of the LOOP. If we have no reliable estimate, the function returns
3549 false, otherwise returns true. */
3552 max_loop_iterations (struct loop
*loop
, widest_int
*nit
)
3554 /* When SCEV information is available, try to update loop iterations
3555 estimate. Otherwise just return whatever we recorded earlier. */
3556 if (scev_initialized_p ())
3557 estimate_numbers_of_iterations_loop (loop
);
3559 return get_max_loop_iterations (loop
, nit
);
3562 /* Similar to max_loop_iterations, but returns the estimate only
3563 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3564 on the number of iterations of LOOP could not be derived, returns -1. */
3567 max_loop_iterations_int (struct loop
*loop
)
3570 HOST_WIDE_INT hwi_nit
;
3572 if (!max_loop_iterations (loop
, &nit
))
3575 if (!wi::fits_shwi_p (nit
))
3577 hwi_nit
= nit
.to_shwi ();
3579 return hwi_nit
< 0 ? -1 : hwi_nit
;
3582 /* Returns an estimate for the number of executions of statements
3583 in the LOOP. For statements before the loop exit, this exceeds
3584 the number of execution of the latch by one. */
3587 estimated_stmt_executions_int (struct loop
*loop
)
3589 HOST_WIDE_INT nit
= estimated_loop_iterations_int (loop
);
3595 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
3597 /* If the computation overflows, return -1. */
3598 return snit
< 0 ? -1 : snit
;
3601 /* Sets NIT to the estimated maximum number of executions of the latch of the
3602 LOOP, plus one. If we have no reliable estimate, the function returns
3603 false, otherwise returns true. */
3606 max_stmt_executions (struct loop
*loop
, widest_int
*nit
)
3608 widest_int nit_minus_one
;
3610 if (!max_loop_iterations (loop
, nit
))
3613 nit_minus_one
= *nit
;
3617 return wi::gtu_p (*nit
, nit_minus_one
);
3620 /* Sets NIT to the estimated number of executions of the latch of the
3621 LOOP, plus one. If we have no reliable estimate, the function returns
3622 false, otherwise returns true. */
3625 estimated_stmt_executions (struct loop
*loop
, widest_int
*nit
)
3627 widest_int nit_minus_one
;
3629 if (!estimated_loop_iterations (loop
, nit
))
3632 nit_minus_one
= *nit
;
3636 return wi::gtu_p (*nit
, nit_minus_one
);
3639 /* Records estimates on numbers of iterations of loops. */
3642 estimate_numbers_of_iterations (void)
3646 /* We don't want to issue signed overflow warnings while getting
3647 loop iteration estimates. */
3648 fold_defer_overflow_warnings ();
3650 FOR_EACH_LOOP (loop
, 0)
3652 estimate_numbers_of_iterations_loop (loop
);
3655 fold_undefer_and_ignore_overflow_warnings ();
3658 /* Returns true if statement S1 dominates statement S2. */
3661 stmt_dominates_stmt_p (gimple s1
, gimple s2
)
3663 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
3671 gimple_stmt_iterator bsi
;
3673 if (gimple_code (s2
) == GIMPLE_PHI
)
3676 if (gimple_code (s1
) == GIMPLE_PHI
)
3679 for (bsi
= gsi_start_bb (bb1
); gsi_stmt (bsi
) != s2
; gsi_next (&bsi
))
3680 if (gsi_stmt (bsi
) == s1
)
3686 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
3689 /* Returns true when we can prove that the number of executions of
3690 STMT in the loop is at most NITER, according to the bound on
3691 the number of executions of the statement NITER_BOUND->stmt recorded in
3692 NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT.
3694 ??? This code can become quite a CPU hog - we can have many bounds,
3695 and large basic block forcing stmt_dominates_stmt_p to be queried
3696 many times on a large basic blocks, so the whole thing is O(n^2)
3697 for scev_probably_wraps_p invocation (that can be done n times).
3699 It would make more sense (and give better answers) to remember BB
3700 bounds computed by discover_iteration_bound_by_body_walk. */
3703 n_of_executions_at_most (gimple stmt
,
3704 struct nb_iter_bound
*niter_bound
,
3707 widest_int bound
= niter_bound
->bound
;
3708 tree nit_type
= TREE_TYPE (niter
), e
;
3711 gcc_assert (TYPE_UNSIGNED (nit_type
));
3713 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
3714 the number of iterations is small. */
3715 if (!wi::fits_to_tree_p (bound
, nit_type
))
3718 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3719 times. This means that:
3721 -- if NITER_BOUND->is_exit is true, then everything after
3722 it at most NITER_BOUND->bound times.
3724 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
3725 is executed, then NITER_BOUND->stmt is executed as well in the same
3726 iteration then STMT is executed at most NITER_BOUND->bound + 1 times.
3728 If we can determine that NITER_BOUND->stmt is always executed
3729 after STMT, then STMT is executed at most NITER_BOUND->bound + 2 times.
3730 We conclude that if both statements belong to the same
3731 basic block and STMT is before NITER_BOUND->stmt and there are no
3732 statements with side effects in between. */
3734 if (niter_bound
->is_exit
)
3736 if (stmt
== niter_bound
->stmt
3737 || !stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
3743 if (!stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
3745 gimple_stmt_iterator bsi
;
3746 if (gimple_bb (stmt
) != gimple_bb (niter_bound
->stmt
)
3747 || gimple_code (stmt
) == GIMPLE_PHI
3748 || gimple_code (niter_bound
->stmt
) == GIMPLE_PHI
)
3751 /* By stmt_dominates_stmt_p we already know that STMT appears
3752 before NITER_BOUND->STMT. Still need to test that the loop
3753 can not be terinated by a side effect in between. */
3754 for (bsi
= gsi_for_stmt (stmt
); gsi_stmt (bsi
) != niter_bound
->stmt
;
3756 if (gimple_has_side_effects (gsi_stmt (bsi
)))
3760 || !wi::fits_to_tree_p (bound
, nit_type
))
3766 e
= fold_binary (cmp
, boolean_type_node
,
3767 niter
, wide_int_to_tree (nit_type
, bound
));
3768 return e
&& integer_nonzerop (e
);
3771 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
3774 nowrap_type_p (tree type
)
3776 if (INTEGRAL_TYPE_P (type
)
3777 && TYPE_OVERFLOW_UNDEFINED (type
))
3780 if (POINTER_TYPE_P (type
))
3786 /* Return false only when the induction variable BASE + STEP * I is
3787 known to not overflow: i.e. when the number of iterations is small
3788 enough with respect to the step and initial condition in order to
3789 keep the evolution confined in TYPEs bounds. Return true when the
3790 iv is known to overflow or when the property is not computable.
3792 USE_OVERFLOW_SEMANTICS is true if this function should assume that
3793 the rules for overflow of the given language apply (e.g., that signed
3794 arithmetics in C does not overflow). */
3797 scev_probably_wraps_p (tree base
, tree step
,
3798 gimple at_stmt
, struct loop
*loop
,
3799 bool use_overflow_semantics
)
3801 tree delta
, step_abs
;
3802 tree unsigned_type
, valid_niter
;
3803 tree type
= TREE_TYPE (step
);
3806 struct nb_iter_bound
*bound
;
3808 /* FIXME: We really need something like
3809 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
3811 We used to test for the following situation that frequently appears
3812 during address arithmetics:
3814 D.1621_13 = (long unsigned intD.4) D.1620_12;
3815 D.1622_14 = D.1621_13 * 8;
3816 D.1623_15 = (doubleD.29 *) D.1622_14;
3818 And derived that the sequence corresponding to D_14
3819 can be proved to not wrap because it is used for computing a
3820 memory access; however, this is not really the case -- for example,
3821 if D_12 = (unsigned char) [254,+,1], then D_14 has values
3822 2032, 2040, 0, 8, ..., but the code is still legal. */
3824 if (chrec_contains_undetermined (base
)
3825 || chrec_contains_undetermined (step
))
3828 if (integer_zerop (step
))
3831 /* If we can use the fact that signed and pointer arithmetics does not
3832 wrap, we are done. */
3833 if (use_overflow_semantics
&& nowrap_type_p (TREE_TYPE (base
)))
3836 /* To be able to use estimates on number of iterations of the loop,
3837 we must have an upper bound on the absolute value of the step. */
3838 if (TREE_CODE (step
) != INTEGER_CST
)
3841 /* Don't issue signed overflow warnings. */
3842 fold_defer_overflow_warnings ();
3844 /* Otherwise, compute the number of iterations before we reach the
3845 bound of the type, and verify that the loop is exited before this
3847 unsigned_type
= unsigned_type_for (type
);
3848 base
= fold_convert (unsigned_type
, base
);
3850 if (tree_int_cst_sign_bit (step
))
3852 tree extreme
= fold_convert (unsigned_type
,
3853 lower_bound_in_type (type
, type
));
3854 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
3855 step_abs
= fold_build1 (NEGATE_EXPR
, unsigned_type
,
3856 fold_convert (unsigned_type
, step
));
3860 tree extreme
= fold_convert (unsigned_type
,
3861 upper_bound_in_type (type
, type
));
3862 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
3863 step_abs
= fold_convert (unsigned_type
, step
);
3866 valid_niter
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step_abs
);
3868 estimate_numbers_of_iterations_loop (loop
);
3870 if (max_loop_iterations (loop
, &niter
)
3871 && wi::fits_to_tree_p (niter
, TREE_TYPE (valid_niter
))
3872 && (e
= fold_binary (GT_EXPR
, boolean_type_node
, valid_niter
,
3873 wide_int_to_tree (TREE_TYPE (valid_niter
),
3875 && integer_nonzerop (e
))
3877 fold_undefer_and_ignore_overflow_warnings ();
3881 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
3883 if (n_of_executions_at_most (at_stmt
, bound
, valid_niter
))
3885 fold_undefer_and_ignore_overflow_warnings ();
3890 fold_undefer_and_ignore_overflow_warnings ();
3892 /* At this point we still don't have a proof that the iv does not
3893 overflow: give up. */
3897 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
3900 free_numbers_of_iterations_estimates_loop (struct loop
*loop
)
3902 struct nb_iter_bound
*bound
, *next
;
3904 loop
->nb_iterations
= NULL
;
3905 loop
->estimate_state
= EST_NOT_COMPUTED
;
3906 for (bound
= loop
->bounds
; bound
; bound
= next
)
3912 loop
->bounds
= NULL
;
3915 /* Frees the information on upper bounds on numbers of iterations of loops. */
3918 free_numbers_of_iterations_estimates (void)
3922 FOR_EACH_LOOP (loop
, 0)
3924 free_numbers_of_iterations_estimates_loop (loop
);
3928 /* Substitute value VAL for ssa name NAME inside expressions held
3932 substitute_in_loop_info (struct loop
*loop
, tree name
, tree val
)
3934 loop
->nb_iterations
= simplify_replace_tree (loop
->nb_iterations
, name
, val
);