1 /* Functions to determine/estimate number of iterations of a loop.
2 Copyright (C) 2004-2013 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"
28 #include "basic-block.h"
29 #include "gimple-pretty-print.h"
31 #include "pointer-set.h"
32 #include "tree-ssa-alias.h"
33 #include "internal-fn.h"
34 #include "gimple-expr.h"
38 #include "gimple-iterator.h"
39 #include "gimple-ssa.h"
41 #include "tree-phinodes.h"
42 #include "ssa-iterators.h"
43 #include "tree-ssa-loop-ivopts.h"
44 #include "tree-ssa-loop-niter.h"
45 #include "tree-ssa-loop.h"
48 #include "tree-chrec.h"
49 #include "tree-scalar-evolution.h"
50 #include "tree-data-ref.h"
53 #include "diagnostic-core.h"
54 #include "tree-inline.h"
55 #include "tree-pass.h"
56 #include "stringpool.h"
57 #include "tree-ssanames.h"
60 #define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
62 /* The maximum number of dominator BBs we search for conditions
63 of loop header copies we use for simplifying a conditional
65 #define MAX_DOMINATORS_TO_WALK 8
69 Analysis of number of iterations of an affine exit test.
73 /* Bounds on some value, BELOW <= X <= UP. */
81 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */
84 split_to_var_and_offset (tree expr
, tree
*var
, mpz_t offset
)
86 tree type
= TREE_TYPE (expr
);
92 mpz_set_ui (offset
, 0);
94 switch (TREE_CODE (expr
))
101 case POINTER_PLUS_EXPR
:
102 op0
= TREE_OPERAND (expr
, 0);
103 op1
= TREE_OPERAND (expr
, 1);
105 if (TREE_CODE (op1
) != INTEGER_CST
)
109 /* Always sign extend the offset. */
110 off
= tree_to_double_int (op1
);
111 off
= off
.sext (TYPE_PRECISION (type
));
112 mpz_set_double_int (offset
, off
, false);
114 mpz_neg (offset
, offset
);
118 *var
= build_int_cst_type (type
, 0);
119 off
= tree_to_double_int (expr
);
120 mpz_set_double_int (offset
, off
, TYPE_UNSIGNED (type
));
128 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
129 in TYPE to MIN and MAX. */
132 determine_value_range (struct loop
*loop
, tree type
, tree var
, mpz_t off
,
133 mpz_t min
, mpz_t max
)
135 double_int minv
, maxv
;
136 enum value_range_type rtype
= VR_VARYING
;
138 /* If the expression is a constant, we know its value exactly. */
139 if (integer_zerop (var
))
146 get_type_static_bounds (type
, min
, max
);
148 /* See if we have some range info from VRP. */
149 if (TREE_CODE (var
) == SSA_NAME
&& INTEGRAL_TYPE_P (type
))
151 edge e
= loop_preheader_edge (loop
);
152 gimple_stmt_iterator gsi
;
154 /* Either for VAR itself... */
155 rtype
= get_range_info (var
, &minv
, &maxv
);
156 /* Or for PHI results in loop->header where VAR is used as
157 PHI argument from the loop preheader edge. */
158 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
160 gimple phi
= gsi_stmt (gsi
);
161 double_int minc
, maxc
;
162 if (PHI_ARG_DEF_FROM_EDGE (phi
, e
) == var
163 && (get_range_info (gimple_phi_result (phi
), &minc
, &maxc
)
166 if (rtype
!= VR_RANGE
)
174 minv
= minv
.max (minc
, TYPE_UNSIGNED (type
));
175 maxv
= maxv
.min (maxc
, TYPE_UNSIGNED (type
));
176 gcc_assert (minv
.cmp (maxv
, TYPE_UNSIGNED (type
)) <= 0);
180 if (rtype
== VR_RANGE
)
183 gcc_assert (minv
.cmp (maxv
, TYPE_UNSIGNED (type
)) <= 0);
186 mpz_set_double_int (minm
, minv
, TYPE_UNSIGNED (type
));
187 mpz_set_double_int (maxm
, maxv
, TYPE_UNSIGNED (type
));
188 mpz_add (minm
, minm
, off
);
189 mpz_add (maxm
, maxm
, off
);
190 /* If the computation may not wrap or off is zero, then this
191 is always fine. If off is negative and minv + off isn't
192 smaller than type's minimum, or off is positive and
193 maxv + off isn't bigger than type's maximum, use the more
194 precise range too. */
195 if (nowrap_type_p (type
)
196 || mpz_sgn (off
) == 0
197 || (mpz_sgn (off
) < 0 && mpz_cmp (minm
, min
) >= 0)
198 || (mpz_sgn (off
) > 0 && mpz_cmp (maxm
, max
) <= 0))
211 /* If the computation may wrap, we know nothing about the value, except for
212 the range of the type. */
213 if (!nowrap_type_p (type
))
216 /* Since the addition of OFF does not wrap, if OFF is positive, then we may
217 add it to MIN, otherwise to MAX. */
218 if (mpz_sgn (off
) < 0)
219 mpz_add (max
, max
, off
);
221 mpz_add (min
, min
, off
);
224 /* Stores the bounds on the difference of the values of the expressions
225 (var + X) and (var + Y), computed in TYPE, to BNDS. */
228 bound_difference_of_offsetted_base (tree type
, mpz_t x
, mpz_t y
,
231 int rel
= mpz_cmp (x
, y
);
232 bool may_wrap
= !nowrap_type_p (type
);
235 /* If X == Y, then the expressions are always equal.
236 If X > Y, there are the following possibilities:
237 a) neither of var + X and var + Y overflow or underflow, or both of
238 them do. Then their difference is X - Y.
239 b) var + X overflows, and var + Y does not. Then the values of the
240 expressions are var + X - M and var + Y, where M is the range of
241 the type, and their difference is X - Y - M.
242 c) var + Y underflows and var + X does not. Their difference again
244 Therefore, if the arithmetics in type does not overflow, then the
245 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
246 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
247 (X - Y, X - Y + M). */
251 mpz_set_ui (bnds
->below
, 0);
252 mpz_set_ui (bnds
->up
, 0);
257 mpz_set_double_int (m
, double_int::mask (TYPE_PRECISION (type
)), true);
258 mpz_add_ui (m
, m
, 1);
259 mpz_sub (bnds
->up
, x
, y
);
260 mpz_set (bnds
->below
, bnds
->up
);
265 mpz_sub (bnds
->below
, bnds
->below
, m
);
267 mpz_add (bnds
->up
, bnds
->up
, m
);
273 /* From condition C0 CMP C1 derives information regarding the
274 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
275 and stores it to BNDS. */
278 refine_bounds_using_guard (tree type
, tree varx
, mpz_t offx
,
279 tree vary
, mpz_t offy
,
280 tree c0
, enum tree_code cmp
, tree c1
,
283 tree varc0
, varc1
, tmp
, ctype
;
284 mpz_t offc0
, offc1
, loffx
, loffy
, bnd
;
286 bool no_wrap
= nowrap_type_p (type
);
295 STRIP_SIGN_NOPS (c0
);
296 STRIP_SIGN_NOPS (c1
);
297 ctype
= TREE_TYPE (c0
);
298 if (!useless_type_conversion_p (ctype
, type
))
304 /* We could derive quite precise information from EQ_EXPR, however, such
305 a guard is unlikely to appear, so we do not bother with handling
310 /* NE_EXPR comparisons do not contain much of useful information, except for
311 special case of comparing with the bounds of the type. */
312 if (TREE_CODE (c1
) != INTEGER_CST
313 || !INTEGRAL_TYPE_P (type
))
316 /* Ensure that the condition speaks about an expression in the same type
318 ctype
= TREE_TYPE (c0
);
319 if (TYPE_PRECISION (ctype
) != TYPE_PRECISION (type
))
321 c0
= fold_convert (type
, c0
);
322 c1
= fold_convert (type
, c1
);
324 if (TYPE_MIN_VALUE (type
)
325 && operand_equal_p (c1
, TYPE_MIN_VALUE (type
), 0))
330 if (TYPE_MAX_VALUE (type
)
331 && operand_equal_p (c1
, TYPE_MAX_VALUE (type
), 0))
344 split_to_var_and_offset (expand_simple_operations (c0
), &varc0
, offc0
);
345 split_to_var_and_offset (expand_simple_operations (c1
), &varc1
, offc1
);
347 /* We are only interested in comparisons of expressions based on VARX and
348 VARY. TODO -- we might also be able to derive some bounds from
349 expressions containing just one of the variables. */
351 if (operand_equal_p (varx
, varc1
, 0))
353 tmp
= varc0
; varc0
= varc1
; varc1
= tmp
;
354 mpz_swap (offc0
, offc1
);
355 cmp
= swap_tree_comparison (cmp
);
358 if (!operand_equal_p (varx
, varc0
, 0)
359 || !operand_equal_p (vary
, varc1
, 0))
362 mpz_init_set (loffx
, offx
);
363 mpz_init_set (loffy
, offy
);
365 if (cmp
== GT_EXPR
|| cmp
== GE_EXPR
)
367 tmp
= varx
; varx
= vary
; vary
= tmp
;
368 mpz_swap (offc0
, offc1
);
369 mpz_swap (loffx
, loffy
);
370 cmp
= swap_tree_comparison (cmp
);
374 /* If there is no overflow, the condition implies that
376 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
378 The overflows and underflows may complicate things a bit; each
379 overflow decreases the appropriate offset by M, and underflow
380 increases it by M. The above inequality would not necessarily be
383 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
384 VARX + OFFC0 overflows, but VARX + OFFX does not.
385 This may only happen if OFFX < OFFC0.
386 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
387 VARY + OFFC1 underflows and VARY + OFFY does not.
388 This may only happen if OFFY > OFFC1. */
397 x_ok
= (integer_zerop (varx
)
398 || mpz_cmp (loffx
, offc0
) >= 0);
399 y_ok
= (integer_zerop (vary
)
400 || mpz_cmp (loffy
, offc1
) <= 0);
406 mpz_sub (bnd
, loffx
, loffy
);
407 mpz_add (bnd
, bnd
, offc1
);
408 mpz_sub (bnd
, bnd
, offc0
);
411 mpz_sub_ui (bnd
, bnd
, 1);
416 if (mpz_cmp (bnds
->below
, bnd
) < 0)
417 mpz_set (bnds
->below
, bnd
);
421 if (mpz_cmp (bnd
, bnds
->up
) < 0)
422 mpz_set (bnds
->up
, bnd
);
434 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
435 The subtraction is considered to be performed in arbitrary precision,
438 We do not attempt to be too clever regarding the value ranges of X and
439 Y; most of the time, they are just integers or ssa names offsetted by
440 integer. However, we try to use the information contained in the
441 comparisons before the loop (usually created by loop header copying). */
444 bound_difference (struct loop
*loop
, tree x
, tree y
, bounds
*bnds
)
446 tree type
= TREE_TYPE (x
);
449 mpz_t minx
, maxx
, miny
, maxy
;
457 /* Get rid of unnecessary casts, but preserve the value of
462 mpz_init (bnds
->below
);
466 split_to_var_and_offset (x
, &varx
, offx
);
467 split_to_var_and_offset (y
, &vary
, offy
);
469 if (!integer_zerop (varx
)
470 && operand_equal_p (varx
, vary
, 0))
472 /* Special case VARX == VARY -- we just need to compare the
473 offsets. The matters are a bit more complicated in the
474 case addition of offsets may wrap. */
475 bound_difference_of_offsetted_base (type
, offx
, offy
, bnds
);
479 /* Otherwise, use the value ranges to determine the initial
480 estimates on below and up. */
485 determine_value_range (loop
, type
, varx
, offx
, minx
, maxx
);
486 determine_value_range (loop
, type
, vary
, offy
, miny
, maxy
);
488 mpz_sub (bnds
->below
, minx
, maxy
);
489 mpz_sub (bnds
->up
, maxx
, miny
);
496 /* If both X and Y are constants, we cannot get any more precise. */
497 if (integer_zerop (varx
) && integer_zerop (vary
))
500 /* Now walk the dominators of the loop header and use the entry
501 guards to refine the estimates. */
502 for (bb
= loop
->header
;
503 bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && cnt
< MAX_DOMINATORS_TO_WALK
;
504 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
506 if (!single_pred_p (bb
))
508 e
= single_pred_edge (bb
);
510 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
513 cond
= last_stmt (e
->src
);
514 c0
= gimple_cond_lhs (cond
);
515 cmp
= gimple_cond_code (cond
);
516 c1
= gimple_cond_rhs (cond
);
518 if (e
->flags
& EDGE_FALSE_VALUE
)
519 cmp
= invert_tree_comparison (cmp
, false);
521 refine_bounds_using_guard (type
, varx
, offx
, vary
, offy
,
531 /* Update the bounds in BNDS that restrict the value of X to the bounds
532 that restrict the value of X + DELTA. X can be obtained as a
533 difference of two values in TYPE. */
536 bounds_add (bounds
*bnds
, double_int delta
, tree type
)
541 mpz_set_double_int (mdelta
, delta
, false);
544 mpz_set_double_int (max
, double_int::mask (TYPE_PRECISION (type
)), true);
546 mpz_add (bnds
->up
, bnds
->up
, mdelta
);
547 mpz_add (bnds
->below
, bnds
->below
, mdelta
);
549 if (mpz_cmp (bnds
->up
, max
) > 0)
550 mpz_set (bnds
->up
, max
);
553 if (mpz_cmp (bnds
->below
, max
) < 0)
554 mpz_set (bnds
->below
, max
);
560 /* Update the bounds in BNDS that restrict the value of X to the bounds
561 that restrict the value of -X. */
564 bounds_negate (bounds
*bnds
)
568 mpz_init_set (tmp
, bnds
->up
);
569 mpz_neg (bnds
->up
, bnds
->below
);
570 mpz_neg (bnds
->below
, tmp
);
574 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
577 inverse (tree x
, tree mask
)
579 tree type
= TREE_TYPE (x
);
581 unsigned ctr
= tree_floor_log2 (mask
);
583 if (TYPE_PRECISION (type
) <= HOST_BITS_PER_WIDE_INT
)
585 unsigned HOST_WIDE_INT ix
;
586 unsigned HOST_WIDE_INT imask
;
587 unsigned HOST_WIDE_INT irslt
= 1;
589 gcc_assert (cst_and_fits_in_hwi (x
));
590 gcc_assert (cst_and_fits_in_hwi (mask
));
592 ix
= int_cst_value (x
);
593 imask
= int_cst_value (mask
);
602 rslt
= build_int_cst_type (type
, irslt
);
606 rslt
= build_int_cst (type
, 1);
609 rslt
= int_const_binop (MULT_EXPR
, rslt
, x
);
610 x
= int_const_binop (MULT_EXPR
, x
, x
);
612 rslt
= int_const_binop (BIT_AND_EXPR
, rslt
, mask
);
618 /* Derives the upper bound BND on the number of executions of loop with exit
619 condition S * i <> C. If NO_OVERFLOW is true, then the control variable of
620 the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed
621 that the loop ends through this exit, i.e., the induction variable ever
622 reaches the value of C.
624 The value C is equal to final - base, where final and base are the final and
625 initial value of the actual induction variable in the analysed loop. BNDS
626 bounds the value of this difference when computed in signed type with
627 unbounded range, while the computation of C is performed in an unsigned
628 type with the range matching the range of the type of the induction variable.
629 In particular, BNDS.up contains an upper bound on C in the following cases:
630 -- if the iv must reach its final value without overflow, i.e., if
631 NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
632 -- if final >= base, which we know to hold when BNDS.below >= 0. */
635 number_of_iterations_ne_max (mpz_t bnd
, bool no_overflow
, tree c
, tree s
,
636 bounds
*bnds
, bool exit_must_be_taken
)
640 tree type
= TREE_TYPE (c
);
641 bool bnds_u_valid
= ((no_overflow
&& exit_must_be_taken
)
642 || mpz_sgn (bnds
->below
) >= 0);
645 || (TREE_CODE (c
) == INTEGER_CST
646 && TREE_CODE (s
) == INTEGER_CST
647 && tree_to_double_int (c
).mod (tree_to_double_int (s
),
648 TYPE_UNSIGNED (type
),
649 EXACT_DIV_EXPR
).is_zero ())
650 || (TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (c
))
651 && multiple_of_p (type
, c
, s
)))
653 /* If C is an exact multiple of S, then its value will be reached before
654 the induction variable overflows (unless the loop is exited in some
655 other way before). Note that the actual induction variable in the
656 loop (which ranges from base to final instead of from 0 to C) may
657 overflow, in which case BNDS.up will not be giving a correct upper
658 bound on C; thus, BNDS_U_VALID had to be computed in advance. */
660 exit_must_be_taken
= true;
663 /* If the induction variable can overflow, the number of iterations is at
664 most the period of the control variable (or infinite, but in that case
665 the whole # of iterations analysis will fail). */
668 max
= double_int::mask (TYPE_PRECISION (type
)
669 - tree_to_uhwi (num_ending_zeros (s
)));
670 mpz_set_double_int (bnd
, max
, true);
674 /* Now we know that the induction variable does not overflow, so the loop
675 iterates at most (range of type / S) times. */
676 mpz_set_double_int (bnd
, double_int::mask (TYPE_PRECISION (type
)), true);
678 /* If the induction variable is guaranteed to reach the value of C before
680 if (exit_must_be_taken
)
682 /* ... then we can strengthen this to C / S, and possibly we can use
683 the upper bound on C given by BNDS. */
684 if (TREE_CODE (c
) == INTEGER_CST
)
685 mpz_set_double_int (bnd
, tree_to_double_int (c
), true);
686 else if (bnds_u_valid
)
687 mpz_set (bnd
, bnds
->up
);
691 mpz_set_double_int (d
, tree_to_double_int (s
), true);
692 mpz_fdiv_q (bnd
, bnd
, d
);
696 /* Determines number of iterations of loop whose ending condition
697 is IV <> FINAL. TYPE is the type of the iv. The number of
698 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
699 we know that the exit must be taken eventually, i.e., that the IV
700 ever reaches the value FINAL (we derived this earlier, and possibly set
701 NITER->assumptions to make sure this is the case). BNDS contains the
702 bounds on the difference FINAL - IV->base. */
705 number_of_iterations_ne (tree type
, affine_iv
*iv
, tree final
,
706 struct tree_niter_desc
*niter
, bool exit_must_be_taken
,
709 tree niter_type
= unsigned_type_for (type
);
710 tree s
, c
, d
, bits
, assumption
, tmp
, bound
;
713 niter
->control
= *iv
;
714 niter
->bound
= final
;
715 niter
->cmp
= NE_EXPR
;
717 /* Rearrange the terms so that we get inequality S * i <> C, with S
718 positive. Also cast everything to the unsigned type. If IV does
719 not overflow, BNDS bounds the value of C. Also, this is the
720 case if the computation |FINAL - IV->base| does not overflow, i.e.,
721 if BNDS->below in the result is nonnegative. */
722 if (tree_int_cst_sign_bit (iv
->step
))
724 s
= fold_convert (niter_type
,
725 fold_build1 (NEGATE_EXPR
, type
, iv
->step
));
726 c
= fold_build2 (MINUS_EXPR
, niter_type
,
727 fold_convert (niter_type
, iv
->base
),
728 fold_convert (niter_type
, final
));
729 bounds_negate (bnds
);
733 s
= fold_convert (niter_type
, iv
->step
);
734 c
= fold_build2 (MINUS_EXPR
, niter_type
,
735 fold_convert (niter_type
, final
),
736 fold_convert (niter_type
, iv
->base
));
740 number_of_iterations_ne_max (max
, iv
->no_overflow
, c
, s
, bnds
,
742 niter
->max
= mpz_get_double_int (niter_type
, max
, false);
745 /* First the trivial cases -- when the step is 1. */
746 if (integer_onep (s
))
752 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
753 is infinite. Otherwise, the number of iterations is
754 (inverse(s/d) * (c/d)) mod (size of mode/d). */
755 bits
= num_ending_zeros (s
);
756 bound
= build_low_bits_mask (niter_type
,
757 (TYPE_PRECISION (niter_type
)
758 - tree_to_uhwi (bits
)));
760 d
= fold_binary_to_constant (LSHIFT_EXPR
, niter_type
,
761 build_int_cst (niter_type
, 1), bits
);
762 s
= fold_binary_to_constant (RSHIFT_EXPR
, niter_type
, s
, bits
);
764 if (!exit_must_be_taken
)
766 /* If we cannot assume that the exit is taken eventually, record the
767 assumptions for divisibility of c. */
768 assumption
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, c
, d
);
769 assumption
= fold_build2 (EQ_EXPR
, boolean_type_node
,
770 assumption
, build_int_cst (niter_type
, 0));
771 if (!integer_nonzerop (assumption
))
772 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
773 niter
->assumptions
, assumption
);
776 c
= fold_build2 (EXACT_DIV_EXPR
, niter_type
, c
, d
);
777 tmp
= fold_build2 (MULT_EXPR
, niter_type
, c
, inverse (s
, bound
));
778 niter
->niter
= fold_build2 (BIT_AND_EXPR
, niter_type
, tmp
, bound
);
782 /* Checks whether we can determine the final value of the control variable
783 of the loop with ending condition IV0 < IV1 (computed in TYPE).
784 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
785 of the step. The assumptions necessary to ensure that the computation
786 of the final value does not overflow are recorded in NITER. If we
787 find the final value, we adjust DELTA and return TRUE. Otherwise
788 we return false. BNDS bounds the value of IV1->base - IV0->base,
789 and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
790 true if we know that the exit must be taken eventually. */
793 number_of_iterations_lt_to_ne (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
794 struct tree_niter_desc
*niter
,
795 tree
*delta
, tree step
,
796 bool exit_must_be_taken
, bounds
*bnds
)
798 tree niter_type
= TREE_TYPE (step
);
799 tree mod
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, *delta
, step
);
802 tree assumption
= boolean_true_node
, bound
, noloop
;
803 bool ret
= false, fv_comp_no_overflow
;
805 if (POINTER_TYPE_P (type
))
808 if (TREE_CODE (mod
) != INTEGER_CST
)
810 if (integer_nonzerop (mod
))
811 mod
= fold_build2 (MINUS_EXPR
, niter_type
, step
, mod
);
812 tmod
= fold_convert (type1
, mod
);
815 mpz_set_double_int (mmod
, tree_to_double_int (mod
), true);
816 mpz_neg (mmod
, mmod
);
818 /* If the induction variable does not overflow and the exit is taken,
819 then the computation of the final value does not overflow. This is
820 also obviously the case if the new final value is equal to the
821 current one. Finally, we postulate this for pointer type variables,
822 as the code cannot rely on the object to that the pointer points being
823 placed at the end of the address space (and more pragmatically,
824 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
825 if (integer_zerop (mod
) || POINTER_TYPE_P (type
))
826 fv_comp_no_overflow
= true;
827 else if (!exit_must_be_taken
)
828 fv_comp_no_overflow
= false;
830 fv_comp_no_overflow
=
831 (iv0
->no_overflow
&& integer_nonzerop (iv0
->step
))
832 || (iv1
->no_overflow
&& integer_nonzerop (iv1
->step
));
834 if (integer_nonzerop (iv0
->step
))
836 /* The final value of the iv is iv1->base + MOD, assuming that this
837 computation does not overflow, and that
838 iv0->base <= iv1->base + MOD. */
839 if (!fv_comp_no_overflow
)
841 bound
= fold_build2 (MINUS_EXPR
, type1
,
842 TYPE_MAX_VALUE (type1
), tmod
);
843 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
845 if (integer_zerop (assumption
))
848 if (mpz_cmp (mmod
, bnds
->below
) < 0)
849 noloop
= boolean_false_node
;
850 else if (POINTER_TYPE_P (type
))
851 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
853 fold_build_pointer_plus (iv1
->base
, tmod
));
855 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
857 fold_build2 (PLUS_EXPR
, type1
,
862 /* The final value of the iv is iv0->base - MOD, assuming that this
863 computation does not overflow, and that
864 iv0->base - MOD <= iv1->base. */
865 if (!fv_comp_no_overflow
)
867 bound
= fold_build2 (PLUS_EXPR
, type1
,
868 TYPE_MIN_VALUE (type1
), tmod
);
869 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
871 if (integer_zerop (assumption
))
874 if (mpz_cmp (mmod
, bnds
->below
) < 0)
875 noloop
= boolean_false_node
;
876 else if (POINTER_TYPE_P (type
))
877 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
878 fold_build_pointer_plus (iv0
->base
,
879 fold_build1 (NEGATE_EXPR
,
883 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
884 fold_build2 (MINUS_EXPR
, type1
,
889 if (!integer_nonzerop (assumption
))
890 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
893 if (!integer_zerop (noloop
))
894 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
897 bounds_add (bnds
, tree_to_double_int (mod
), type
);
898 *delta
= fold_build2 (PLUS_EXPR
, niter_type
, *delta
, mod
);
906 /* Add assertions to NITER that ensure that the control variable of the loop
907 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
908 are TYPE. Returns false if we can prove that there is an overflow, true
909 otherwise. STEP is the absolute value of the step. */
912 assert_no_overflow_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
913 struct tree_niter_desc
*niter
, tree step
)
915 tree bound
, d
, assumption
, diff
;
916 tree niter_type
= TREE_TYPE (step
);
918 if (integer_nonzerop (iv0
->step
))
920 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
921 if (iv0
->no_overflow
)
924 /* If iv0->base is a constant, we can determine the last value before
925 overflow precisely; otherwise we conservatively assume
928 if (TREE_CODE (iv0
->base
) == INTEGER_CST
)
930 d
= fold_build2 (MINUS_EXPR
, niter_type
,
931 fold_convert (niter_type
, TYPE_MAX_VALUE (type
)),
932 fold_convert (niter_type
, iv0
->base
));
933 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
936 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
937 build_int_cst (niter_type
, 1));
938 bound
= fold_build2 (MINUS_EXPR
, type
,
939 TYPE_MAX_VALUE (type
), fold_convert (type
, diff
));
940 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
945 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
946 if (iv1
->no_overflow
)
949 if (TREE_CODE (iv1
->base
) == INTEGER_CST
)
951 d
= fold_build2 (MINUS_EXPR
, niter_type
,
952 fold_convert (niter_type
, iv1
->base
),
953 fold_convert (niter_type
, TYPE_MIN_VALUE (type
)));
954 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
957 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
958 build_int_cst (niter_type
, 1));
959 bound
= fold_build2 (PLUS_EXPR
, type
,
960 TYPE_MIN_VALUE (type
), fold_convert (type
, diff
));
961 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
965 if (integer_zerop (assumption
))
967 if (!integer_nonzerop (assumption
))
968 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
969 niter
->assumptions
, assumption
);
971 iv0
->no_overflow
= true;
972 iv1
->no_overflow
= true;
976 /* Add an assumption to NITER that a loop whose ending condition
977 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
978 bounds the value of IV1->base - IV0->base. */
981 assert_loop_rolls_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
982 struct tree_niter_desc
*niter
, bounds
*bnds
)
984 tree assumption
= boolean_true_node
, bound
, diff
;
985 tree mbz
, mbzl
, mbzr
, type1
;
986 bool rolls_p
, no_overflow_p
;
990 /* We are going to compute the number of iterations as
991 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
992 variant of TYPE. This formula only works if
994 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
996 (where MAX is the maximum value of the unsigned variant of TYPE, and
997 the computations in this formula are performed in full precision,
998 i.e., without overflows).
1000 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
1001 we have a condition of the form iv0->base - step < iv1->base before the loop,
1002 and for loops iv0->base < iv1->base - step * i the condition
1003 iv0->base < iv1->base + step, due to loop header copying, which enable us
1004 to prove the lower bound.
1006 The upper bound is more complicated. Unless the expressions for initial
1007 and final value themselves contain enough information, we usually cannot
1008 derive it from the context. */
1010 /* First check whether the answer does not follow from the bounds we gathered
1012 if (integer_nonzerop (iv0
->step
))
1013 dstep
= tree_to_double_int (iv0
->step
);
1016 dstep
= tree_to_double_int (iv1
->step
).sext (TYPE_PRECISION (type
));
1021 mpz_set_double_int (mstep
, dstep
, true);
1022 mpz_neg (mstep
, mstep
);
1023 mpz_add_ui (mstep
, mstep
, 1);
1025 rolls_p
= mpz_cmp (mstep
, bnds
->below
) <= 0;
1028 mpz_set_double_int (max
, double_int::mask (TYPE_PRECISION (type
)), true);
1029 mpz_add (max
, max
, mstep
);
1030 no_overflow_p
= (mpz_cmp (bnds
->up
, max
) <= 0
1031 /* For pointers, only values lying inside a single object
1032 can be compared or manipulated by pointer arithmetics.
1033 Gcc in general does not allow or handle objects larger
1034 than half of the address space, hence the upper bound
1035 is satisfied for pointers. */
1036 || POINTER_TYPE_P (type
));
1040 if (rolls_p
&& no_overflow_p
)
1044 if (POINTER_TYPE_P (type
))
1047 /* Now the hard part; we must formulate the assumption(s) as expressions, and
1048 we must be careful not to introduce overflow. */
1050 if (integer_nonzerop (iv0
->step
))
1052 diff
= fold_build2 (MINUS_EXPR
, type1
,
1053 iv0
->step
, build_int_cst (type1
, 1));
1055 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
1056 0 address never belongs to any object, we can assume this for
1058 if (!POINTER_TYPE_P (type
))
1060 bound
= fold_build2 (PLUS_EXPR
, type1
,
1061 TYPE_MIN_VALUE (type
), diff
);
1062 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
1066 /* And then we can compute iv0->base - diff, and compare it with
1068 mbzl
= fold_build2 (MINUS_EXPR
, type1
,
1069 fold_convert (type1
, iv0
->base
), diff
);
1070 mbzr
= fold_convert (type1
, iv1
->base
);
1074 diff
= fold_build2 (PLUS_EXPR
, type1
,
1075 iv1
->step
, build_int_cst (type1
, 1));
1077 if (!POINTER_TYPE_P (type
))
1079 bound
= fold_build2 (PLUS_EXPR
, type1
,
1080 TYPE_MAX_VALUE (type
), diff
);
1081 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
1085 mbzl
= fold_convert (type1
, iv0
->base
);
1086 mbzr
= fold_build2 (MINUS_EXPR
, type1
,
1087 fold_convert (type1
, iv1
->base
), diff
);
1090 if (!integer_nonzerop (assumption
))
1091 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1092 niter
->assumptions
, assumption
);
1095 mbz
= fold_build2 (GT_EXPR
, boolean_type_node
, mbzl
, mbzr
);
1096 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1097 niter
->may_be_zero
, mbz
);
1101 /* Determines number of iterations of loop whose ending condition
1102 is IV0 < IV1. TYPE is the type of the iv. The number of
1103 iterations is stored to NITER. BNDS bounds the difference
1104 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
1105 that the exit must be taken eventually. */
1108 number_of_iterations_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1109 struct tree_niter_desc
*niter
,
1110 bool exit_must_be_taken
, bounds
*bnds
)
1112 tree niter_type
= unsigned_type_for (type
);
1113 tree delta
, step
, s
;
1116 if (integer_nonzerop (iv0
->step
))
1118 niter
->control
= *iv0
;
1119 niter
->cmp
= LT_EXPR
;
1120 niter
->bound
= iv1
->base
;
1124 niter
->control
= *iv1
;
1125 niter
->cmp
= GT_EXPR
;
1126 niter
->bound
= iv0
->base
;
1129 delta
= fold_build2 (MINUS_EXPR
, niter_type
,
1130 fold_convert (niter_type
, iv1
->base
),
1131 fold_convert (niter_type
, iv0
->base
));
1133 /* First handle the special case that the step is +-1. */
1134 if ((integer_onep (iv0
->step
) && integer_zerop (iv1
->step
))
1135 || (integer_all_onesp (iv1
->step
) && integer_zerop (iv0
->step
)))
1137 /* for (i = iv0->base; i < iv1->base; i++)
1141 for (i = iv1->base; i > iv0->base; i--).
1143 In both cases # of iterations is iv1->base - iv0->base, assuming that
1144 iv1->base >= iv0->base.
1146 First try to derive a lower bound on the value of
1147 iv1->base - iv0->base, computed in full precision. If the difference
1148 is nonnegative, we are done, otherwise we must record the
1151 if (mpz_sgn (bnds
->below
) < 0)
1152 niter
->may_be_zero
= fold_build2 (LT_EXPR
, boolean_type_node
,
1153 iv1
->base
, iv0
->base
);
1154 niter
->niter
= delta
;
1155 niter
->max
= mpz_get_double_int (niter_type
, bnds
->up
, false);
1159 if (integer_nonzerop (iv0
->step
))
1160 step
= fold_convert (niter_type
, iv0
->step
);
1162 step
= fold_convert (niter_type
,
1163 fold_build1 (NEGATE_EXPR
, type
, iv1
->step
));
1165 /* If we can determine the final value of the control iv exactly, we can
1166 transform the condition to != comparison. In particular, this will be
1167 the case if DELTA is constant. */
1168 if (number_of_iterations_lt_to_ne (type
, iv0
, iv1
, niter
, &delta
, step
,
1169 exit_must_be_taken
, bnds
))
1173 zps
.base
= build_int_cst (niter_type
, 0);
1175 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1176 zps does not overflow. */
1177 zps
.no_overflow
= true;
1179 return number_of_iterations_ne (type
, &zps
, delta
, niter
, true, bnds
);
1182 /* Make sure that the control iv does not overflow. */
1183 if (!assert_no_overflow_lt (type
, iv0
, iv1
, niter
, step
))
1186 /* We determine the number of iterations as (delta + step - 1) / step. For
1187 this to work, we must know that iv1->base >= iv0->base - step + 1,
1188 otherwise the loop does not roll. */
1189 assert_loop_rolls_lt (type
, iv0
, iv1
, niter
, bnds
);
1191 s
= fold_build2 (MINUS_EXPR
, niter_type
,
1192 step
, build_int_cst (niter_type
, 1));
1193 delta
= fold_build2 (PLUS_EXPR
, niter_type
, delta
, s
);
1194 niter
->niter
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, delta
, step
);
1198 mpz_set_double_int (mstep
, tree_to_double_int (step
), true);
1199 mpz_add (tmp
, bnds
->up
, mstep
);
1200 mpz_sub_ui (tmp
, tmp
, 1);
1201 mpz_fdiv_q (tmp
, tmp
, mstep
);
1202 niter
->max
= mpz_get_double_int (niter_type
, tmp
, false);
1209 /* Determines number of iterations of loop whose ending condition
1210 is IV0 <= IV1. TYPE is the type of the iv. The number of
1211 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
1212 we know that this condition must eventually become false (we derived this
1213 earlier, and possibly set NITER->assumptions to make sure this
1214 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1217 number_of_iterations_le (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1218 struct tree_niter_desc
*niter
, bool exit_must_be_taken
,
1223 if (POINTER_TYPE_P (type
))
1226 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1227 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1228 value of the type. This we must know anyway, since if it is
1229 equal to this value, the loop rolls forever. We do not check
1230 this condition for pointer type ivs, as the code cannot rely on
1231 the object to that the pointer points being placed at the end of
1232 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1233 not defined for pointers). */
1235 if (!exit_must_be_taken
&& !POINTER_TYPE_P (type
))
1237 if (integer_nonzerop (iv0
->step
))
1238 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1239 iv1
->base
, TYPE_MAX_VALUE (type
));
1241 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1242 iv0
->base
, TYPE_MIN_VALUE (type
));
1244 if (integer_zerop (assumption
))
1246 if (!integer_nonzerop (assumption
))
1247 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1248 niter
->assumptions
, assumption
);
1251 if (integer_nonzerop (iv0
->step
))
1253 if (POINTER_TYPE_P (type
))
1254 iv1
->base
= fold_build_pointer_plus_hwi (iv1
->base
, 1);
1256 iv1
->base
= fold_build2 (PLUS_EXPR
, type1
, iv1
->base
,
1257 build_int_cst (type1
, 1));
1259 else if (POINTER_TYPE_P (type
))
1260 iv0
->base
= fold_build_pointer_plus_hwi (iv0
->base
, -1);
1262 iv0
->base
= fold_build2 (MINUS_EXPR
, type1
,
1263 iv0
->base
, build_int_cst (type1
, 1));
1265 bounds_add (bnds
, double_int_one
, type1
);
1267 return number_of_iterations_lt (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1271 /* Dumps description of affine induction variable IV to FILE. */
1274 dump_affine_iv (FILE *file
, affine_iv
*iv
)
1276 if (!integer_zerop (iv
->step
))
1277 fprintf (file
, "[");
1279 print_generic_expr (dump_file
, iv
->base
, TDF_SLIM
);
1281 if (!integer_zerop (iv
->step
))
1283 fprintf (file
, ", + , ");
1284 print_generic_expr (dump_file
, iv
->step
, TDF_SLIM
);
1285 fprintf (file
, "]%s", iv
->no_overflow
? "(no_overflow)" : "");
1289 /* Determine the number of iterations according to condition (for staying
1290 inside loop) which compares two induction variables using comparison
1291 operator CODE. The induction variable on left side of the comparison
1292 is IV0, the right-hand side is IV1. Both induction variables must have
1293 type TYPE, which must be an integer or pointer type. The steps of the
1294 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1296 LOOP is the loop whose number of iterations we are determining.
1298 ONLY_EXIT is true if we are sure this is the only way the loop could be
1299 exited (including possibly non-returning function calls, exceptions, etc.)
1300 -- in this case we can use the information whether the control induction
1301 variables can overflow or not in a more efficient way.
1303 if EVERY_ITERATION is true, we know the test is executed on every iteration.
1305 The results (number of iterations and assumptions as described in
1306 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
1307 Returns false if it fails to determine number of iterations, true if it
1308 was determined (possibly with some assumptions). */
1311 number_of_iterations_cond (struct loop
*loop
,
1312 tree type
, affine_iv
*iv0
, enum tree_code code
,
1313 affine_iv
*iv1
, struct tree_niter_desc
*niter
,
1314 bool only_exit
, bool every_iteration
)
1316 bool exit_must_be_taken
= false, ret
;
1319 /* If the test is not executed every iteration, wrapping may make the test
1321 TODO: the overflow case can be still used as unreliable estimate of upper
1322 bound. But we have no API to pass it down to number of iterations code
1323 and, at present, it will not use it anyway. */
1324 if (!every_iteration
1325 && (!iv0
->no_overflow
|| !iv1
->no_overflow
1326 || code
== NE_EXPR
|| code
== EQ_EXPR
))
1329 /* The meaning of these assumptions is this:
1331 then the rest of information does not have to be valid
1332 if may_be_zero then the loop does not roll, even if
1334 niter
->assumptions
= boolean_true_node
;
1335 niter
->may_be_zero
= boolean_false_node
;
1336 niter
->niter
= NULL_TREE
;
1337 niter
->max
= double_int_zero
;
1339 niter
->bound
= NULL_TREE
;
1340 niter
->cmp
= ERROR_MARK
;
1342 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1343 the control variable is on lhs. */
1344 if (code
== GE_EXPR
|| code
== GT_EXPR
1345 || (code
== NE_EXPR
&& integer_zerop (iv0
->step
)))
1348 code
= swap_tree_comparison (code
);
1351 if (POINTER_TYPE_P (type
))
1353 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1354 to the same object. If they do, the control variable cannot wrap
1355 (as wrap around the bounds of memory will never return a pointer
1356 that would be guaranteed to point to the same object, even if we
1357 avoid undefined behavior by casting to size_t and back). */
1358 iv0
->no_overflow
= true;
1359 iv1
->no_overflow
= true;
1362 /* If the control induction variable does not overflow and the only exit
1363 from the loop is the one that we analyze, we know it must be taken
1367 if (!integer_zerop (iv0
->step
) && iv0
->no_overflow
)
1368 exit_must_be_taken
= true;
1369 else if (!integer_zerop (iv1
->step
) && iv1
->no_overflow
)
1370 exit_must_be_taken
= true;
1373 /* We can handle the case when neither of the sides of the comparison is
1374 invariant, provided that the test is NE_EXPR. This rarely occurs in
1375 practice, but it is simple enough to manage. */
1376 if (!integer_zerop (iv0
->step
) && !integer_zerop (iv1
->step
))
1378 tree step_type
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1379 if (code
!= NE_EXPR
)
1382 iv0
->step
= fold_binary_to_constant (MINUS_EXPR
, step_type
,
1383 iv0
->step
, iv1
->step
);
1384 iv0
->no_overflow
= false;
1385 iv1
->step
= build_int_cst (step_type
, 0);
1386 iv1
->no_overflow
= true;
1389 /* If the result of the comparison is a constant, the loop is weird. More
1390 precise handling would be possible, but the situation is not common enough
1391 to waste time on it. */
1392 if (integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
))
1395 /* Ignore loops of while (i-- < 10) type. */
1396 if (code
!= NE_EXPR
)
1398 if (iv0
->step
&& tree_int_cst_sign_bit (iv0
->step
))
1401 if (!integer_zerop (iv1
->step
) && !tree_int_cst_sign_bit (iv1
->step
))
1405 /* If the loop exits immediately, there is nothing to do. */
1406 tree tem
= fold_binary (code
, boolean_type_node
, iv0
->base
, iv1
->base
);
1407 if (tem
&& integer_zerop (tem
))
1409 niter
->niter
= build_int_cst (unsigned_type_for (type
), 0);
1410 niter
->max
= double_int_zero
;
1414 /* OK, now we know we have a senseful loop. Handle several cases, depending
1415 on what comparison operator is used. */
1416 bound_difference (loop
, iv1
->base
, iv0
->base
, &bnds
);
1418 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1421 "Analyzing # of iterations of loop %d\n", loop
->num
);
1423 fprintf (dump_file
, " exit condition ");
1424 dump_affine_iv (dump_file
, iv0
);
1425 fprintf (dump_file
, " %s ",
1426 code
== NE_EXPR
? "!="
1427 : code
== LT_EXPR
? "<"
1429 dump_affine_iv (dump_file
, iv1
);
1430 fprintf (dump_file
, "\n");
1432 fprintf (dump_file
, " bounds on difference of bases: ");
1433 mpz_out_str (dump_file
, 10, bnds
.below
);
1434 fprintf (dump_file
, " ... ");
1435 mpz_out_str (dump_file
, 10, bnds
.up
);
1436 fprintf (dump_file
, "\n");
1442 gcc_assert (integer_zerop (iv1
->step
));
1443 ret
= number_of_iterations_ne (type
, iv0
, iv1
->base
, niter
,
1444 exit_must_be_taken
, &bnds
);
1448 ret
= number_of_iterations_lt (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1453 ret
= number_of_iterations_le (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1461 mpz_clear (bnds
.up
);
1462 mpz_clear (bnds
.below
);
1464 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1468 fprintf (dump_file
, " result:\n");
1469 if (!integer_nonzerop (niter
->assumptions
))
1471 fprintf (dump_file
, " under assumptions ");
1472 print_generic_expr (dump_file
, niter
->assumptions
, TDF_SLIM
);
1473 fprintf (dump_file
, "\n");
1476 if (!integer_zerop (niter
->may_be_zero
))
1478 fprintf (dump_file
, " zero if ");
1479 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
1480 fprintf (dump_file
, "\n");
1483 fprintf (dump_file
, " # of iterations ");
1484 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
1485 fprintf (dump_file
, ", bounded by ");
1486 dump_double_int (dump_file
, niter
->max
, true);
1487 fprintf (dump_file
, "\n");
1490 fprintf (dump_file
, " failed\n\n");
1495 /* Substitute NEW for OLD in EXPR and fold the result. */
1498 simplify_replace_tree (tree expr
, tree old
, tree new_tree
)
1501 tree ret
= NULL_TREE
, e
, se
;
1506 /* Do not bother to replace constants. */
1507 if (CONSTANT_CLASS_P (old
))
1511 || operand_equal_p (expr
, old
, 0))
1512 return unshare_expr (new_tree
);
1517 n
= TREE_OPERAND_LENGTH (expr
);
1518 for (i
= 0; i
< n
; i
++)
1520 e
= TREE_OPERAND (expr
, i
);
1521 se
= simplify_replace_tree (e
, old
, new_tree
);
1526 ret
= copy_node (expr
);
1528 TREE_OPERAND (ret
, i
) = se
;
1531 return (ret
? fold (ret
) : expr
);
1534 /* Expand definitions of ssa names in EXPR as long as they are simple
1535 enough, and return the new expression. */
1538 expand_simple_operations (tree expr
)
1541 tree ret
= NULL_TREE
, e
, ee
, e1
;
1542 enum tree_code code
;
1545 if (expr
== NULL_TREE
)
1548 if (is_gimple_min_invariant (expr
))
1551 code
= TREE_CODE (expr
);
1552 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
1554 n
= TREE_OPERAND_LENGTH (expr
);
1555 for (i
= 0; i
< n
; i
++)
1557 e
= TREE_OPERAND (expr
, i
);
1558 ee
= expand_simple_operations (e
);
1563 ret
= copy_node (expr
);
1565 TREE_OPERAND (ret
, i
) = ee
;
1571 fold_defer_overflow_warnings ();
1573 fold_undefer_and_ignore_overflow_warnings ();
1577 if (TREE_CODE (expr
) != SSA_NAME
)
1580 stmt
= SSA_NAME_DEF_STMT (expr
);
1581 if (gimple_code (stmt
) == GIMPLE_PHI
)
1583 basic_block src
, dest
;
1585 if (gimple_phi_num_args (stmt
) != 1)
1587 e
= PHI_ARG_DEF (stmt
, 0);
1589 /* Avoid propagating through loop exit phi nodes, which
1590 could break loop-closed SSA form restrictions. */
1591 dest
= gimple_bb (stmt
);
1592 src
= single_pred (dest
);
1593 if (TREE_CODE (e
) == SSA_NAME
1594 && src
->loop_father
!= dest
->loop_father
)
1597 return expand_simple_operations (e
);
1599 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1602 /* Avoid expanding to expressions that contain SSA names that need
1603 to take part in abnormal coalescing. */
1605 FOR_EACH_SSA_TREE_OPERAND (e
, stmt
, iter
, SSA_OP_USE
)
1606 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (e
))
1609 e
= gimple_assign_rhs1 (stmt
);
1610 code
= gimple_assign_rhs_code (stmt
);
1611 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1613 if (is_gimple_min_invariant (e
))
1616 if (code
== SSA_NAME
)
1617 return expand_simple_operations (e
);
1625 /* Casts are simple. */
1626 ee
= expand_simple_operations (e
);
1627 return fold_build1 (code
, TREE_TYPE (expr
), ee
);
1631 case POINTER_PLUS_EXPR
:
1632 /* And increments and decrements by a constant are simple. */
1633 e1
= gimple_assign_rhs2 (stmt
);
1634 if (!is_gimple_min_invariant (e1
))
1637 ee
= expand_simple_operations (e
);
1638 return fold_build2 (code
, TREE_TYPE (expr
), ee
, e1
);
1645 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1646 expression (or EXPR unchanged, if no simplification was possible). */
1649 tree_simplify_using_condition_1 (tree cond
, tree expr
)
1652 tree e
, te
, e0
, e1
, e2
, notcond
;
1653 enum tree_code code
= TREE_CODE (expr
);
1655 if (code
== INTEGER_CST
)
1658 if (code
== TRUTH_OR_EXPR
1659 || code
== TRUTH_AND_EXPR
1660 || code
== COND_EXPR
)
1664 e0
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 0));
1665 if (TREE_OPERAND (expr
, 0) != e0
)
1668 e1
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 1));
1669 if (TREE_OPERAND (expr
, 1) != e1
)
1672 if (code
== COND_EXPR
)
1674 e2
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 2));
1675 if (TREE_OPERAND (expr
, 2) != e2
)
1683 if (code
== COND_EXPR
)
1684 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1686 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1692 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
1693 propagation, and vice versa. Fold does not handle this, since it is
1694 considered too expensive. */
1695 if (TREE_CODE (cond
) == EQ_EXPR
)
1697 e0
= TREE_OPERAND (cond
, 0);
1698 e1
= TREE_OPERAND (cond
, 1);
1700 /* We know that e0 == e1. Check whether we cannot simplify expr
1702 e
= simplify_replace_tree (expr
, e0
, e1
);
1703 if (integer_zerop (e
) || integer_nonzerop (e
))
1706 e
= simplify_replace_tree (expr
, e1
, e0
);
1707 if (integer_zerop (e
) || integer_nonzerop (e
))
1710 if (TREE_CODE (expr
) == EQ_EXPR
)
1712 e0
= TREE_OPERAND (expr
, 0);
1713 e1
= TREE_OPERAND (expr
, 1);
1715 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
1716 e
= simplify_replace_tree (cond
, e0
, e1
);
1717 if (integer_zerop (e
))
1719 e
= simplify_replace_tree (cond
, e1
, e0
);
1720 if (integer_zerop (e
))
1723 if (TREE_CODE (expr
) == NE_EXPR
)
1725 e0
= TREE_OPERAND (expr
, 0);
1726 e1
= TREE_OPERAND (expr
, 1);
1728 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
1729 e
= simplify_replace_tree (cond
, e0
, e1
);
1730 if (integer_zerop (e
))
1731 return boolean_true_node
;
1732 e
= simplify_replace_tree (cond
, e1
, e0
);
1733 if (integer_zerop (e
))
1734 return boolean_true_node
;
1737 te
= expand_simple_operations (expr
);
1739 /* Check whether COND ==> EXPR. */
1740 notcond
= invert_truthvalue (cond
);
1741 e
= fold_binary (TRUTH_OR_EXPR
, boolean_type_node
, notcond
, te
);
1742 if (e
&& integer_nonzerop (e
))
1745 /* Check whether COND ==> not EXPR. */
1746 e
= fold_binary (TRUTH_AND_EXPR
, boolean_type_node
, cond
, te
);
1747 if (e
&& integer_zerop (e
))
1753 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1754 expression (or EXPR unchanged, if no simplification was possible).
1755 Wrapper around tree_simplify_using_condition_1 that ensures that chains
1756 of simple operations in definitions of ssa names in COND are expanded,
1757 so that things like casts or incrementing the value of the bound before
1758 the loop do not cause us to fail. */
1761 tree_simplify_using_condition (tree cond
, tree expr
)
1763 cond
= expand_simple_operations (cond
);
1765 return tree_simplify_using_condition_1 (cond
, expr
);
1768 /* Tries to simplify EXPR using the conditions on entry to LOOP.
1769 Returns the simplified expression (or EXPR unchanged, if no
1770 simplification was possible).*/
1773 simplify_using_initial_conditions (struct loop
*loop
, tree expr
)
1781 if (TREE_CODE (expr
) == INTEGER_CST
)
1784 /* Limit walking the dominators to avoid quadraticness in
1785 the number of BBs times the number of loops in degenerate
1787 for (bb
= loop
->header
;
1788 bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && cnt
< MAX_DOMINATORS_TO_WALK
;
1789 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1791 if (!single_pred_p (bb
))
1793 e
= single_pred_edge (bb
);
1795 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
1798 stmt
= last_stmt (e
->src
);
1799 cond
= fold_build2 (gimple_cond_code (stmt
),
1801 gimple_cond_lhs (stmt
),
1802 gimple_cond_rhs (stmt
));
1803 if (e
->flags
& EDGE_FALSE_VALUE
)
1804 cond
= invert_truthvalue (cond
);
1805 expr
= tree_simplify_using_condition (cond
, expr
);
1812 /* Tries to simplify EXPR using the evolutions of the loop invariants
1813 in the superloops of LOOP. Returns the simplified expression
1814 (or EXPR unchanged, if no simplification was possible). */
1817 simplify_using_outer_evolutions (struct loop
*loop
, tree expr
)
1819 enum tree_code code
= TREE_CODE (expr
);
1823 if (is_gimple_min_invariant (expr
))
1826 if (code
== TRUTH_OR_EXPR
1827 || code
== TRUTH_AND_EXPR
1828 || code
== COND_EXPR
)
1832 e0
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 0));
1833 if (TREE_OPERAND (expr
, 0) != e0
)
1836 e1
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 1));
1837 if (TREE_OPERAND (expr
, 1) != e1
)
1840 if (code
== COND_EXPR
)
1842 e2
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 2));
1843 if (TREE_OPERAND (expr
, 2) != e2
)
1851 if (code
== COND_EXPR
)
1852 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1854 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1860 e
= instantiate_parameters (loop
, expr
);
1861 if (is_gimple_min_invariant (e
))
1867 /* Returns true if EXIT is the only possible exit from LOOP. */
1870 loop_only_exit_p (const struct loop
*loop
, const_edge exit
)
1873 gimple_stmt_iterator bsi
;
1877 if (exit
!= single_exit (loop
))
1880 body
= get_loop_body (loop
);
1881 for (i
= 0; i
< loop
->num_nodes
; i
++)
1883 for (bsi
= gsi_start_bb (body
[i
]); !gsi_end_p (bsi
); gsi_next (&bsi
))
1885 call
= gsi_stmt (bsi
);
1886 if (gimple_code (call
) != GIMPLE_CALL
)
1889 if (gimple_has_side_effects (call
))
1901 /* Stores description of number of iterations of LOOP derived from
1902 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
1903 useful information could be derived (and fields of NITER has
1904 meaning described in comments at struct tree_niter_desc
1905 declaration), false otherwise. If WARN is true and
1906 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1907 potentially unsafe assumptions.
1908 When EVERY_ITERATION is true, only tests that are known to be executed
1909 every iteration are considered (i.e. only test that alone bounds the loop).
1913 number_of_iterations_exit (struct loop
*loop
, edge exit
,
1914 struct tree_niter_desc
*niter
,
1915 bool warn
, bool every_iteration
)
1920 enum tree_code code
;
1924 safe
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit
->src
);
1926 if (every_iteration
&& !safe
)
1929 niter
->assumptions
= boolean_false_node
;
1930 stmt
= last_stmt (exit
->src
);
1931 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1934 /* We want the condition for staying inside loop. */
1935 code
= gimple_cond_code (stmt
);
1936 if (exit
->flags
& EDGE_TRUE_VALUE
)
1937 code
= invert_tree_comparison (code
, false);
1952 op0
= gimple_cond_lhs (stmt
);
1953 op1
= gimple_cond_rhs (stmt
);
1954 type
= TREE_TYPE (op0
);
1956 if (TREE_CODE (type
) != INTEGER_TYPE
1957 && !POINTER_TYPE_P (type
))
1960 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, false))
1962 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, false))
1965 /* We don't want to see undefined signed overflow warnings while
1966 computing the number of iterations. */
1967 fold_defer_overflow_warnings ();
1969 iv0
.base
= expand_simple_operations (iv0
.base
);
1970 iv1
.base
= expand_simple_operations (iv1
.base
);
1971 if (!number_of_iterations_cond (loop
, type
, &iv0
, code
, &iv1
, niter
,
1972 loop_only_exit_p (loop
, exit
), safe
))
1974 fold_undefer_and_ignore_overflow_warnings ();
1980 niter
->assumptions
= simplify_using_outer_evolutions (loop
,
1981 niter
->assumptions
);
1982 niter
->may_be_zero
= simplify_using_outer_evolutions (loop
,
1983 niter
->may_be_zero
);
1984 niter
->niter
= simplify_using_outer_evolutions (loop
, niter
->niter
);
1988 = simplify_using_initial_conditions (loop
,
1989 niter
->assumptions
);
1991 = simplify_using_initial_conditions (loop
,
1992 niter
->may_be_zero
);
1994 fold_undefer_and_ignore_overflow_warnings ();
1996 /* If NITER has simplified into a constant, update MAX. */
1997 if (TREE_CODE (niter
->niter
) == INTEGER_CST
)
1998 niter
->max
= tree_to_double_int (niter
->niter
);
2000 if (integer_onep (niter
->assumptions
))
2003 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
2004 But if we can prove that there is overflow or some other source of weird
2005 behavior, ignore the loop even with -funsafe-loop-optimizations. */
2006 if (integer_zerop (niter
->assumptions
) || !single_exit (loop
))
2009 if (flag_unsafe_loop_optimizations
)
2010 niter
->assumptions
= boolean_true_node
;
2014 const char *wording
;
2015 location_t loc
= gimple_location (stmt
);
2017 /* We can provide a more specific warning if one of the operator is
2018 constant and the other advances by +1 or -1. */
2019 if (!integer_zerop (iv1
.step
)
2020 ? (integer_zerop (iv0
.step
)
2021 && (integer_onep (iv1
.step
) || integer_all_onesp (iv1
.step
)))
2022 : (integer_onep (iv0
.step
) || integer_all_onesp (iv0
.step
)))
2024 flag_unsafe_loop_optimizations
2025 ? N_("assuming that the loop is not infinite")
2026 : N_("cannot optimize possibly infinite loops");
2029 flag_unsafe_loop_optimizations
2030 ? N_("assuming that the loop counter does not overflow")
2031 : N_("cannot optimize loop, the loop counter may overflow");
2033 warning_at ((LOCATION_LINE (loc
) > 0) ? loc
: input_location
,
2034 OPT_Wunsafe_loop_optimizations
, "%s", gettext (wording
));
2037 return flag_unsafe_loop_optimizations
;
2040 /* Try to determine the number of iterations of LOOP. If we succeed,
2041 expression giving number of iterations is returned and *EXIT is
2042 set to the edge from that the information is obtained. Otherwise
2043 chrec_dont_know is returned. */
2046 find_loop_niter (struct loop
*loop
, edge
*exit
)
2049 vec
<edge
> exits
= get_loop_exit_edges (loop
);
2051 tree niter
= NULL_TREE
, aniter
;
2052 struct tree_niter_desc desc
;
2055 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2057 if (!number_of_iterations_exit (loop
, ex
, &desc
, false))
2060 if (integer_nonzerop (desc
.may_be_zero
))
2062 /* We exit in the first iteration through this exit.
2063 We won't find anything better. */
2064 niter
= build_int_cst (unsigned_type_node
, 0);
2069 if (!integer_zerop (desc
.may_be_zero
))
2072 aniter
= desc
.niter
;
2076 /* Nothing recorded yet. */
2082 /* Prefer constants, the lower the better. */
2083 if (TREE_CODE (aniter
) != INTEGER_CST
)
2086 if (TREE_CODE (niter
) != INTEGER_CST
)
2093 if (tree_int_cst_lt (aniter
, niter
))
2102 return niter
? niter
: chrec_dont_know
;
2105 /* Return true if loop is known to have bounded number of iterations. */
2108 finite_loop_p (struct loop
*loop
)
2113 if (flag_unsafe_loop_optimizations
)
2115 flags
= flags_from_decl_or_type (current_function_decl
);
2116 if ((flags
& (ECF_CONST
|ECF_PURE
)) && !(flags
& ECF_LOOPING_CONST_OR_PURE
))
2118 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2119 fprintf (dump_file
, "Found loop %i to be finite: it is within pure or const function.\n",
2124 if (loop
->any_upper_bound
2125 || max_loop_iterations (loop
, &nit
))
2127 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2128 fprintf (dump_file
, "Found loop %i to be finite: upper bound found.\n",
2137 Analysis of a number of iterations of a loop by a brute-force evaluation.
2141 /* Bound on the number of iterations we try to evaluate. */
2143 #define MAX_ITERATIONS_TO_TRACK \
2144 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
2146 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
2147 result by a chain of operations such that all but exactly one of their
2148 operands are constants. */
2151 chain_of_csts_start (struct loop
*loop
, tree x
)
2153 gimple stmt
= SSA_NAME_DEF_STMT (x
);
2155 basic_block bb
= gimple_bb (stmt
);
2156 enum tree_code code
;
2159 || !flow_bb_inside_loop_p (loop
, bb
))
2162 if (gimple_code (stmt
) == GIMPLE_PHI
)
2164 if (bb
== loop
->header
)
2170 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2171 || gimple_assign_rhs_class (stmt
) == GIMPLE_TERNARY_RHS
)
2174 code
= gimple_assign_rhs_code (stmt
);
2175 if (gimple_references_memory_p (stmt
)
2176 || TREE_CODE_CLASS (code
) == tcc_reference
2177 || (code
== ADDR_EXPR
2178 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
2181 use
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
2182 if (use
== NULL_TREE
)
2185 return chain_of_csts_start (loop
, use
);
2188 /* Determines whether the expression X is derived from a result of a phi node
2189 in header of LOOP such that
2191 * the derivation of X consists only from operations with constants
2192 * the initial value of the phi node is constant
2193 * the value of the phi node in the next iteration can be derived from the
2194 value in the current iteration by a chain of operations with constants.
2196 If such phi node exists, it is returned, otherwise NULL is returned. */
2199 get_base_for (struct loop
*loop
, tree x
)
2204 if (is_gimple_min_invariant (x
))
2207 phi
= chain_of_csts_start (loop
, x
);
2211 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2212 next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2214 if (TREE_CODE (next
) != SSA_NAME
)
2217 if (!is_gimple_min_invariant (init
))
2220 if (chain_of_csts_start (loop
, next
) != phi
)
2226 /* Given an expression X, then
2228 * if X is NULL_TREE, we return the constant BASE.
2229 * otherwise X is a SSA name, whose value in the considered loop is derived
2230 by a chain of operations with constant from a result of a phi node in
2231 the header of the loop. Then we return value of X when the value of the
2232 result of this phi node is given by the constant BASE. */
2235 get_val_for (tree x
, tree base
)
2239 gcc_checking_assert (is_gimple_min_invariant (base
));
2244 stmt
= SSA_NAME_DEF_STMT (x
);
2245 if (gimple_code (stmt
) == GIMPLE_PHI
)
2248 gcc_checking_assert (is_gimple_assign (stmt
));
2250 /* STMT must be either an assignment of a single SSA name or an
2251 expression involving an SSA name and a constant. Try to fold that
2252 expression using the value for the SSA name. */
2253 if (gimple_assign_ssa_name_copy_p (stmt
))
2254 return get_val_for (gimple_assign_rhs1 (stmt
), base
);
2255 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_UNARY_RHS
2256 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
2258 return fold_build1 (gimple_assign_rhs_code (stmt
),
2259 gimple_expr_type (stmt
),
2260 get_val_for (gimple_assign_rhs1 (stmt
), base
));
2262 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_BINARY_RHS
)
2264 tree rhs1
= gimple_assign_rhs1 (stmt
);
2265 tree rhs2
= gimple_assign_rhs2 (stmt
);
2266 if (TREE_CODE (rhs1
) == SSA_NAME
)
2267 rhs1
= get_val_for (rhs1
, base
);
2268 else if (TREE_CODE (rhs2
) == SSA_NAME
)
2269 rhs2
= get_val_for (rhs2
, base
);
2272 return fold_build2 (gimple_assign_rhs_code (stmt
),
2273 gimple_expr_type (stmt
), rhs1
, rhs2
);
2280 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2281 by brute force -- i.e. by determining the value of the operands of the
2282 condition at EXIT in first few iterations of the loop (assuming that
2283 these values are constant) and determining the first one in that the
2284 condition is not satisfied. Returns the constant giving the number
2285 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
2288 loop_niter_by_eval (struct loop
*loop
, edge exit
)
2291 tree op
[2], val
[2], next
[2], aval
[2];
2296 cond
= last_stmt (exit
->src
);
2297 if (!cond
|| gimple_code (cond
) != GIMPLE_COND
)
2298 return chrec_dont_know
;
2300 cmp
= gimple_cond_code (cond
);
2301 if (exit
->flags
& EDGE_TRUE_VALUE
)
2302 cmp
= invert_tree_comparison (cmp
, false);
2312 op
[0] = gimple_cond_lhs (cond
);
2313 op
[1] = gimple_cond_rhs (cond
);
2317 return chrec_dont_know
;
2320 for (j
= 0; j
< 2; j
++)
2322 if (is_gimple_min_invariant (op
[j
]))
2325 next
[j
] = NULL_TREE
;
2330 phi
= get_base_for (loop
, op
[j
]);
2332 return chrec_dont_know
;
2333 val
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2334 next
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2338 /* Don't issue signed overflow warnings. */
2339 fold_defer_overflow_warnings ();
2341 for (i
= 0; i
< MAX_ITERATIONS_TO_TRACK
; i
++)
2343 for (j
= 0; j
< 2; j
++)
2344 aval
[j
] = get_val_for (op
[j
], val
[j
]);
2346 acnd
= fold_binary (cmp
, boolean_type_node
, aval
[0], aval
[1]);
2347 if (acnd
&& integer_zerop (acnd
))
2349 fold_undefer_and_ignore_overflow_warnings ();
2350 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2352 "Proved that loop %d iterates %d times using brute force.\n",
2354 return build_int_cst (unsigned_type_node
, i
);
2357 for (j
= 0; j
< 2; j
++)
2359 val
[j
] = get_val_for (next
[j
], val
[j
]);
2360 if (!is_gimple_min_invariant (val
[j
]))
2362 fold_undefer_and_ignore_overflow_warnings ();
2363 return chrec_dont_know
;
2368 fold_undefer_and_ignore_overflow_warnings ();
2370 return chrec_dont_know
;
2373 /* Finds the exit of the LOOP by that the loop exits after a constant
2374 number of iterations and stores the exit edge to *EXIT. The constant
2375 giving the number of iterations of LOOP is returned. The number of
2376 iterations is determined using loop_niter_by_eval (i.e. by brute force
2377 evaluation). If we are unable to find the exit for that loop_niter_by_eval
2378 determines the number of iterations, chrec_dont_know is returned. */
2381 find_loop_niter_by_eval (struct loop
*loop
, edge
*exit
)
2384 vec
<edge
> exits
= get_loop_exit_edges (loop
);
2386 tree niter
= NULL_TREE
, aniter
;
2390 /* Loops with multiple exits are expensive to handle and less important. */
2391 if (!flag_expensive_optimizations
2392 && exits
.length () > 1)
2395 return chrec_dont_know
;
2398 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2400 if (!just_once_each_iteration_p (loop
, ex
->src
))
2403 aniter
= loop_niter_by_eval (loop
, ex
);
2404 if (chrec_contains_undetermined (aniter
))
2408 && !tree_int_cst_lt (aniter
, niter
))
2416 return niter
? niter
: chrec_dont_know
;
2421 Analysis of upper bounds on number of iterations of a loop.
2425 static double_int
derive_constant_upper_bound_ops (tree
, tree
,
2426 enum tree_code
, tree
);
2428 /* Returns a constant upper bound on the value of the right-hand side of
2429 an assignment statement STMT. */
2432 derive_constant_upper_bound_assign (gimple stmt
)
2434 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2435 tree op0
= gimple_assign_rhs1 (stmt
);
2436 tree op1
= gimple_assign_rhs2 (stmt
);
2438 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt
)),
2442 /* Returns a constant upper bound on the value of expression VAL. VAL
2443 is considered to be unsigned. If its type is signed, its value must
2447 derive_constant_upper_bound (tree val
)
2449 enum tree_code code
;
2452 extract_ops_from_tree (val
, &code
, &op0
, &op1
);
2453 return derive_constant_upper_bound_ops (TREE_TYPE (val
), op0
, code
, op1
);
2456 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
2457 whose type is TYPE. The expression is considered to be unsigned. If
2458 its type is signed, its value must be nonnegative. */
2461 derive_constant_upper_bound_ops (tree type
, tree op0
,
2462 enum tree_code code
, tree op1
)
2465 double_int bnd
, max
, mmax
, cst
;
2468 if (INTEGRAL_TYPE_P (type
))
2469 maxt
= TYPE_MAX_VALUE (type
);
2471 maxt
= upper_bound_in_type (type
, type
);
2473 max
= tree_to_double_int (maxt
);
2478 return tree_to_double_int (op0
);
2481 subtype
= TREE_TYPE (op0
);
2482 if (!TYPE_UNSIGNED (subtype
)
2483 /* If TYPE is also signed, the fact that VAL is nonnegative implies
2484 that OP0 is nonnegative. */
2485 && TYPE_UNSIGNED (type
)
2486 && !tree_expr_nonnegative_p (op0
))
2488 /* If we cannot prove that the casted expression is nonnegative,
2489 we cannot establish more useful upper bound than the precision
2490 of the type gives us. */
2494 /* We now know that op0 is an nonnegative value. Try deriving an upper
2496 bnd
= derive_constant_upper_bound (op0
);
2498 /* If the bound does not fit in TYPE, max. value of TYPE could be
2506 case POINTER_PLUS_EXPR
:
2508 if (TREE_CODE (op1
) != INTEGER_CST
2509 || !tree_expr_nonnegative_p (op0
))
2512 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
2513 choose the most logical way how to treat this constant regardless
2514 of the signedness of the type. */
2515 cst
= tree_to_double_int (op1
);
2516 cst
= cst
.sext (TYPE_PRECISION (type
));
2517 if (code
!= MINUS_EXPR
)
2520 bnd
= derive_constant_upper_bound (op0
);
2522 if (cst
.is_negative ())
2525 /* Avoid CST == 0x80000... */
2526 if (cst
.is_negative ())
2529 /* OP0 + CST. We need to check that
2530 BND <= MAX (type) - CST. */
2540 /* OP0 - CST, where CST >= 0.
2542 If TYPE is signed, we have already verified that OP0 >= 0, and we
2543 know that the result is nonnegative. This implies that
2546 If TYPE is unsigned, we must additionally know that OP0 >= CST,
2547 otherwise the operation underflows.
2550 /* This should only happen if the type is unsigned; however, for
2551 buggy programs that use overflowing signed arithmetics even with
2552 -fno-wrapv, this condition may also be true for signed values. */
2556 if (TYPE_UNSIGNED (type
))
2558 tree tem
= fold_binary (GE_EXPR
, boolean_type_node
, op0
,
2559 double_int_to_tree (type
, cst
));
2560 if (!tem
|| integer_nonzerop (tem
))
2569 case FLOOR_DIV_EXPR
:
2570 case EXACT_DIV_EXPR
:
2571 if (TREE_CODE (op1
) != INTEGER_CST
2572 || tree_int_cst_sign_bit (op1
))
2575 bnd
= derive_constant_upper_bound (op0
);
2576 return bnd
.udiv (tree_to_double_int (op1
), FLOOR_DIV_EXPR
);
2579 if (TREE_CODE (op1
) != INTEGER_CST
2580 || tree_int_cst_sign_bit (op1
))
2582 return tree_to_double_int (op1
);
2585 stmt
= SSA_NAME_DEF_STMT (op0
);
2586 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2587 || gimple_assign_lhs (stmt
) != op0
)
2589 return derive_constant_upper_bound_assign (stmt
);
2596 /* Emit a -Waggressive-loop-optimizations warning if needed. */
2599 do_warn_aggressive_loop_optimizations (struct loop
*loop
,
2600 double_int i_bound
, gimple stmt
)
2602 /* Don't warn if the loop doesn't have known constant bound. */
2603 if (!loop
->nb_iterations
2604 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
2605 || !warn_aggressive_loop_optimizations
2606 /* To avoid warning multiple times for the same loop,
2607 only start warning when we preserve loops. */
2608 || (cfun
->curr_properties
& PROP_loops
) == 0
2609 /* Only warn once per loop. */
2610 || loop
->warned_aggressive_loop_optimizations
2611 /* Only warn if undefined behavior gives us lower estimate than the
2612 known constant bound. */
2613 || i_bound
.ucmp (tree_to_double_int (loop
->nb_iterations
)) >= 0
2614 /* And undefined behavior happens unconditionally. */
2615 || !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (stmt
)))
2618 edge e
= single_exit (loop
);
2622 gimple estmt
= last_stmt (e
->src
);
2623 if (warning_at (gimple_location (stmt
), OPT_Waggressive_loop_optimizations
,
2624 "iteration %E invokes undefined behavior",
2625 double_int_to_tree (TREE_TYPE (loop
->nb_iterations
),
2627 inform (gimple_location (estmt
), "containing loop");
2628 loop
->warned_aggressive_loop_optimizations
= true;
2631 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
2632 is true if the loop is exited immediately after STMT, and this exit
2633 is taken at last when the STMT is executed BOUND + 1 times.
2634 REALISTIC is true if BOUND is expected to be close to the real number
2635 of iterations. UPPER is true if we are sure the loop iterates at most
2636 BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */
2639 record_estimate (struct loop
*loop
, tree bound
, double_int i_bound
,
2640 gimple at_stmt
, bool is_exit
, bool realistic
, bool upper
)
2644 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2646 fprintf (dump_file
, "Statement %s", is_exit
? "(exit)" : "");
2647 print_gimple_stmt (dump_file
, at_stmt
, 0, TDF_SLIM
);
2648 fprintf (dump_file
, " is %sexecuted at most ",
2649 upper
? "" : "probably ");
2650 print_generic_expr (dump_file
, bound
, TDF_SLIM
);
2651 fprintf (dump_file
, " (bounded by ");
2652 dump_double_int (dump_file
, i_bound
, true);
2653 fprintf (dump_file
, ") + 1 times in loop %d.\n", loop
->num
);
2656 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
2657 real number of iterations. */
2658 if (TREE_CODE (bound
) != INTEGER_CST
)
2661 gcc_checking_assert (i_bound
== tree_to_double_int (bound
));
2662 if (!upper
&& !realistic
)
2665 /* If we have a guaranteed upper bound, record it in the appropriate
2666 list, unless this is an !is_exit bound (i.e. undefined behavior in
2667 at_stmt) in a loop with known constant number of iterations. */
2670 || loop
->nb_iterations
== NULL_TREE
2671 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
))
2673 struct nb_iter_bound
*elt
= ggc_alloc_nb_iter_bound ();
2675 elt
->bound
= i_bound
;
2676 elt
->stmt
= at_stmt
;
2677 elt
->is_exit
= is_exit
;
2678 elt
->next
= loop
->bounds
;
2682 /* If statement is executed on every path to the loop latch, we can directly
2683 infer the upper bound on the # of iterations of the loop. */
2684 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (at_stmt
)))
2687 /* Update the number of iteration estimates according to the bound.
2688 If at_stmt is an exit then the loop latch is executed at most BOUND times,
2689 otherwise it can be executed BOUND + 1 times. We will lower the estimate
2690 later if such statement must be executed on last iteration */
2692 delta
= double_int_zero
;
2694 delta
= double_int_one
;
2697 /* If an overflow occurred, ignore the result. */
2698 if (i_bound
.ult (delta
))
2701 if (upper
&& !is_exit
)
2702 do_warn_aggressive_loop_optimizations (loop
, i_bound
, at_stmt
);
2703 record_niter_bound (loop
, i_bound
, realistic
, upper
);
2706 /* Record the estimate on number of iterations of LOOP based on the fact that
2707 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
2708 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
2709 estimated number of iterations is expected to be close to the real one.
2710 UPPER is true if we are sure the induction variable does not wrap. */
2713 record_nonwrapping_iv (struct loop
*loop
, tree base
, tree step
, gimple stmt
,
2714 tree low
, tree high
, bool realistic
, bool upper
)
2716 tree niter_bound
, extreme
, delta
;
2717 tree type
= TREE_TYPE (base
), unsigned_type
;
2720 if (TREE_CODE (step
) != INTEGER_CST
|| integer_zerop (step
))
2723 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2725 fprintf (dump_file
, "Induction variable (");
2726 print_generic_expr (dump_file
, TREE_TYPE (base
), TDF_SLIM
);
2727 fprintf (dump_file
, ") ");
2728 print_generic_expr (dump_file
, base
, TDF_SLIM
);
2729 fprintf (dump_file
, " + ");
2730 print_generic_expr (dump_file
, step
, TDF_SLIM
);
2731 fprintf (dump_file
, " * iteration does not wrap in statement ");
2732 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2733 fprintf (dump_file
, " in loop %d.\n", loop
->num
);
2736 unsigned_type
= unsigned_type_for (type
);
2737 base
= fold_convert (unsigned_type
, base
);
2738 step
= fold_convert (unsigned_type
, step
);
2740 if (tree_int_cst_sign_bit (step
))
2742 extreme
= fold_convert (unsigned_type
, low
);
2743 if (TREE_CODE (base
) != INTEGER_CST
)
2744 base
= fold_convert (unsigned_type
, high
);
2745 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
2746 step
= fold_build1 (NEGATE_EXPR
, unsigned_type
, step
);
2750 extreme
= fold_convert (unsigned_type
, high
);
2751 if (TREE_CODE (base
) != INTEGER_CST
)
2752 base
= fold_convert (unsigned_type
, low
);
2753 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
2756 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
2757 would get out of the range. */
2758 niter_bound
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step
);
2759 max
= derive_constant_upper_bound (niter_bound
);
2760 record_estimate (loop
, niter_bound
, max
, stmt
, false, realistic
, upper
);
2763 /* Determine information about number of iterations a LOOP from the index
2764 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
2765 guaranteed to be executed in every iteration of LOOP. Callback for
2775 idx_infer_loop_bounds (tree base
, tree
*idx
, void *dta
)
2777 struct ilb_data
*data
= (struct ilb_data
*) dta
;
2778 tree ev
, init
, step
;
2779 tree low
, high
, type
, next
;
2780 bool sign
, upper
= true, at_end
= false;
2781 struct loop
*loop
= data
->loop
;
2782 bool reliable
= true;
2784 if (TREE_CODE (base
) != ARRAY_REF
)
2787 /* For arrays at the end of the structure, we are not guaranteed that they
2788 do not really extend over their declared size. However, for arrays of
2789 size greater than one, this is unlikely to be intended. */
2790 if (array_at_struct_end_p (base
))
2796 struct loop
*dloop
= loop_containing_stmt (data
->stmt
);
2800 ev
= analyze_scalar_evolution (dloop
, *idx
);
2801 ev
= instantiate_parameters (loop
, ev
);
2802 init
= initial_condition (ev
);
2803 step
= evolution_part_in_loop_num (ev
, loop
->num
);
2807 || TREE_CODE (step
) != INTEGER_CST
2808 || integer_zerop (step
)
2809 || tree_contains_chrecs (init
, NULL
)
2810 || chrec_contains_symbols_defined_in_loop (init
, loop
->num
))
2813 low
= array_ref_low_bound (base
);
2814 high
= array_ref_up_bound (base
);
2816 /* The case of nonconstant bounds could be handled, but it would be
2818 if (TREE_CODE (low
) != INTEGER_CST
2820 || TREE_CODE (high
) != INTEGER_CST
)
2822 sign
= tree_int_cst_sign_bit (step
);
2823 type
= TREE_TYPE (step
);
2825 /* The array of length 1 at the end of a structure most likely extends
2826 beyond its bounds. */
2828 && operand_equal_p (low
, high
, 0))
2831 /* In case the relevant bound of the array does not fit in type, or
2832 it does, but bound + step (in type) still belongs into the range of the
2833 array, the index may wrap and still stay within the range of the array
2834 (consider e.g. if the array is indexed by the full range of
2837 To make things simpler, we require both bounds to fit into type, although
2838 there are cases where this would not be strictly necessary. */
2839 if (!int_fits_type_p (high
, type
)
2840 || !int_fits_type_p (low
, type
))
2842 low
= fold_convert (type
, low
);
2843 high
= fold_convert (type
, high
);
2846 next
= fold_binary (PLUS_EXPR
, type
, low
, step
);
2848 next
= fold_binary (PLUS_EXPR
, type
, high
, step
);
2850 if (tree_int_cst_compare (low
, next
) <= 0
2851 && tree_int_cst_compare (next
, high
) <= 0)
2854 /* If access is not executed on every iteration, we must ensure that overlow may
2855 not make the access valid later. */
2856 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (data
->stmt
))
2857 && scev_probably_wraps_p (initial_condition_in_loop_num (ev
, loop
->num
),
2858 step
, data
->stmt
, loop
, true))
2861 record_nonwrapping_iv (loop
, init
, step
, data
->stmt
, low
, high
, reliable
, upper
);
2865 /* Determine information about number of iterations a LOOP from the bounds
2866 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
2867 STMT is guaranteed to be executed in every iteration of LOOP.*/
2870 infer_loop_bounds_from_ref (struct loop
*loop
, gimple stmt
, tree ref
)
2872 struct ilb_data data
;
2876 for_each_index (&ref
, idx_infer_loop_bounds
, &data
);
2879 /* Determine information about number of iterations of a LOOP from the way
2880 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
2881 executed in every iteration of LOOP. */
2884 infer_loop_bounds_from_array (struct loop
*loop
, gimple stmt
)
2886 if (is_gimple_assign (stmt
))
2888 tree op0
= gimple_assign_lhs (stmt
);
2889 tree op1
= gimple_assign_rhs1 (stmt
);
2891 /* For each memory access, analyze its access function
2892 and record a bound on the loop iteration domain. */
2893 if (REFERENCE_CLASS_P (op0
))
2894 infer_loop_bounds_from_ref (loop
, stmt
, op0
);
2896 if (REFERENCE_CLASS_P (op1
))
2897 infer_loop_bounds_from_ref (loop
, stmt
, op1
);
2899 else if (is_gimple_call (stmt
))
2902 unsigned i
, n
= gimple_call_num_args (stmt
);
2904 lhs
= gimple_call_lhs (stmt
);
2905 if (lhs
&& REFERENCE_CLASS_P (lhs
))
2906 infer_loop_bounds_from_ref (loop
, stmt
, lhs
);
2908 for (i
= 0; i
< n
; i
++)
2910 arg
= gimple_call_arg (stmt
, i
);
2911 if (REFERENCE_CLASS_P (arg
))
2912 infer_loop_bounds_from_ref (loop
, stmt
, arg
);
2917 /* Determine information about number of iterations of a LOOP from the fact
2918 that pointer arithmetics in STMT does not overflow. */
2921 infer_loop_bounds_from_pointer_arith (struct loop
*loop
, gimple stmt
)
2923 tree def
, base
, step
, scev
, type
, low
, high
;
2926 if (!is_gimple_assign (stmt
)
2927 || gimple_assign_rhs_code (stmt
) != POINTER_PLUS_EXPR
)
2930 def
= gimple_assign_lhs (stmt
);
2931 if (TREE_CODE (def
) != SSA_NAME
)
2934 type
= TREE_TYPE (def
);
2935 if (!nowrap_type_p (type
))
2938 ptr
= gimple_assign_rhs1 (stmt
);
2939 if (!expr_invariant_in_loop_p (loop
, ptr
))
2942 var
= gimple_assign_rhs2 (stmt
);
2943 if (TYPE_PRECISION (type
) != TYPE_PRECISION (TREE_TYPE (var
)))
2946 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
2947 if (chrec_contains_undetermined (scev
))
2950 base
= initial_condition_in_loop_num (scev
, loop
->num
);
2951 step
= evolution_part_in_loop_num (scev
, loop
->num
);
2954 || TREE_CODE (step
) != INTEGER_CST
2955 || tree_contains_chrecs (base
, NULL
)
2956 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
2959 low
= lower_bound_in_type (type
, type
);
2960 high
= upper_bound_in_type (type
, type
);
2962 /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
2963 produce a NULL pointer. The contrary would mean NULL points to an object,
2964 while NULL is supposed to compare unequal with the address of all objects.
2965 Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
2966 NULL pointer since that would mean wrapping, which we assume here not to
2967 happen. So, we can exclude NULL from the valid range of pointer
2969 if (flag_delete_null_pointer_checks
&& int_cst_value (low
) == 0)
2970 low
= build_int_cstu (TREE_TYPE (low
), TYPE_ALIGN_UNIT (TREE_TYPE (type
)));
2972 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
2975 /* Determine information about number of iterations of a LOOP from the fact
2976 that signed arithmetics in STMT does not overflow. */
2979 infer_loop_bounds_from_signedness (struct loop
*loop
, gimple stmt
)
2981 tree def
, base
, step
, scev
, type
, low
, high
;
2983 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2986 def
= gimple_assign_lhs (stmt
);
2988 if (TREE_CODE (def
) != SSA_NAME
)
2991 type
= TREE_TYPE (def
);
2992 if (!INTEGRAL_TYPE_P (type
)
2993 || !TYPE_OVERFLOW_UNDEFINED (type
))
2996 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
2997 if (chrec_contains_undetermined (scev
))
3000 base
= initial_condition_in_loop_num (scev
, loop
->num
);
3001 step
= evolution_part_in_loop_num (scev
, loop
->num
);
3004 || TREE_CODE (step
) != INTEGER_CST
3005 || tree_contains_chrecs (base
, NULL
)
3006 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
3009 low
= lower_bound_in_type (type
, type
);
3010 high
= upper_bound_in_type (type
, type
);
3012 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
3015 /* The following analyzers are extracting informations on the bounds
3016 of LOOP from the following undefined behaviors:
3018 - data references should not access elements over the statically
3021 - signed variables should not overflow when flag_wrapv is not set.
3025 infer_loop_bounds_from_undefined (struct loop
*loop
)
3029 gimple_stmt_iterator bsi
;
3033 bbs
= get_loop_body (loop
);
3035 for (i
= 0; i
< loop
->num_nodes
; i
++)
3039 /* If BB is not executed in each iteration of the loop, we cannot
3040 use the operations in it to infer reliable upper bound on the
3041 # of iterations of the loop. However, we can use it as a guess.
3042 Reliable guesses come only from array bounds. */
3043 reliable
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
);
3045 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
3047 gimple stmt
= gsi_stmt (bsi
);
3049 infer_loop_bounds_from_array (loop
, stmt
);
3053 infer_loop_bounds_from_signedness (loop
, stmt
);
3054 infer_loop_bounds_from_pointer_arith (loop
, stmt
);
3065 /* Compare double ints, callback for qsort. */
3068 double_int_cmp (const void *p1
, const void *p2
)
3070 const double_int
*d1
= (const double_int
*)p1
;
3071 const double_int
*d2
= (const double_int
*)p2
;
3079 /* Return index of BOUND in BOUNDS array sorted in increasing order.
3080 Lookup by binary search. */
3083 bound_index (vec
<double_int
> bounds
, double_int bound
)
3085 unsigned int end
= bounds
.length ();
3086 unsigned int begin
= 0;
3088 /* Find a matching index by means of a binary search. */
3089 while (begin
!= end
)
3091 unsigned int middle
= (begin
+ end
) / 2;
3092 double_int index
= bounds
[middle
];
3096 else if (index
.ult (bound
))
3104 /* We recorded loop bounds only for statements dominating loop latch (and thus
3105 executed each loop iteration). If there are any bounds on statements not
3106 dominating the loop latch we can improve the estimate by walking the loop
3107 body and seeing if every path from loop header to loop latch contains
3108 some bounded statement. */
3111 discover_iteration_bound_by_body_walk (struct loop
*loop
)
3113 pointer_map_t
*bb_bounds
;
3114 struct nb_iter_bound
*elt
;
3115 vec
<double_int
> bounds
= vNULL
;
3116 vec
<vec
<basic_block
> > queues
= vNULL
;
3117 vec
<basic_block
> queue
= vNULL
;
3118 ptrdiff_t queue_index
;
3119 ptrdiff_t latch_index
= 0;
3120 pointer_map_t
*block_priority
;
3122 /* Discover what bounds may interest us. */
3123 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3125 double_int bound
= elt
->bound
;
3127 /* Exit terminates loop at given iteration, while non-exits produce undefined
3128 effect on the next iteration. */
3131 bound
+= double_int_one
;
3132 /* If an overflow occurred, ignore the result. */
3133 if (bound
.is_zero ())
3137 if (!loop
->any_upper_bound
3138 || bound
.ult (loop
->nb_iterations_upper_bound
))
3139 bounds
.safe_push (bound
);
3142 /* Exit early if there is nothing to do. */
3143 if (!bounds
.exists ())
3146 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3147 fprintf (dump_file
, " Trying to walk loop body to reduce the bound.\n");
3149 /* Sort the bounds in decreasing order. */
3150 qsort (bounds
.address (), bounds
.length (),
3151 sizeof (double_int
), double_int_cmp
);
3153 /* For every basic block record the lowest bound that is guaranteed to
3154 terminate the loop. */
3156 bb_bounds
= pointer_map_create ();
3157 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3159 double_int bound
= elt
->bound
;
3162 bound
+= double_int_one
;
3163 /* If an overflow occurred, ignore the result. */
3164 if (bound
.is_zero ())
3168 if (!loop
->any_upper_bound
3169 || bound
.ult (loop
->nb_iterations_upper_bound
))
3171 ptrdiff_t index
= bound_index (bounds
, bound
);
3172 void **entry
= pointer_map_contains (bb_bounds
,
3173 gimple_bb (elt
->stmt
));
3175 *pointer_map_insert (bb_bounds
,
3176 gimple_bb (elt
->stmt
)) = (void *)index
;
3177 else if ((ptrdiff_t)*entry
> index
)
3178 *entry
= (void *)index
;
3182 block_priority
= pointer_map_create ();
3184 /* Perform shortest path discovery loop->header ... loop->latch.
3186 The "distance" is given by the smallest loop bound of basic block
3187 present in the path and we look for path with largest smallest bound
3190 To avoid the need for fibonacci heap on double ints we simply compress
3191 double ints into indexes to BOUNDS array and then represent the queue
3192 as arrays of queues for every index.
3193 Index of BOUNDS.length() means that the execution of given BB has
3194 no bounds determined.
3196 VISITED is a pointer map translating basic block into smallest index
3197 it was inserted into the priority queue with. */
3200 /* Start walk in loop header with index set to infinite bound. */
3201 queue_index
= bounds
.length ();
3202 queues
.safe_grow_cleared (queue_index
+ 1);
3203 queue
.safe_push (loop
->header
);
3204 queues
[queue_index
] = queue
;
3205 *pointer_map_insert (block_priority
, loop
->header
) = (void *)queue_index
;
3207 for (; queue_index
>= 0; queue_index
--)
3209 if (latch_index
< queue_index
)
3211 while (queues
[queue_index
].length ())
3214 ptrdiff_t bound_index
= queue_index
;
3219 queue
= queues
[queue_index
];
3222 /* OK, we later inserted the BB with lower priority, skip it. */
3223 if ((ptrdiff_t)*pointer_map_contains (block_priority
, bb
) > queue_index
)
3226 /* See if we can improve the bound. */
3227 entry
= pointer_map_contains (bb_bounds
, bb
);
3228 if (entry
&& (ptrdiff_t)*entry
< bound_index
)
3229 bound_index
= (ptrdiff_t)*entry
;
3231 /* Insert succesors into the queue, watch for latch edge
3232 and record greatest index we saw. */
3233 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3235 bool insert
= false;
3238 if (loop_exit_edge_p (loop
, e
))
3241 if (e
== loop_latch_edge (loop
)
3242 && latch_index
< bound_index
)
3243 latch_index
= bound_index
;
3244 else if (!(entry
= pointer_map_contains (block_priority
, e
->dest
)))
3247 *pointer_map_insert (block_priority
, e
->dest
) = (void *)bound_index
;
3249 else if ((ptrdiff_t)*entry
< bound_index
)
3252 *entry
= (void *)bound_index
;
3256 queues
[bound_index
].safe_push (e
->dest
);
3260 queues
[queue_index
].release ();
3263 gcc_assert (latch_index
>= 0);
3264 if ((unsigned)latch_index
< bounds
.length ())
3266 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3268 fprintf (dump_file
, "Found better loop bound ");
3269 dump_double_int (dump_file
, bounds
[latch_index
], true);
3270 fprintf (dump_file
, "\n");
3272 record_niter_bound (loop
, bounds
[latch_index
], false, true);
3277 pointer_map_destroy (bb_bounds
);
3278 pointer_map_destroy (block_priority
);
3281 /* See if every path cross the loop goes through a statement that is known
3282 to not execute at the last iteration. In that case we can decrese iteration
3286 maybe_lower_iteration_bound (struct loop
*loop
)
3288 pointer_set_t
*not_executed_last_iteration
= NULL
;
3289 struct nb_iter_bound
*elt
;
3290 bool found_exit
= false;
3291 vec
<basic_block
> queue
= vNULL
;
3294 /* Collect all statements with interesting (i.e. lower than
3295 nb_iterations_upper_bound) bound on them.
3297 TODO: Due to the way record_estimate choose estimates to store, the bounds
3298 will be always nb_iterations_upper_bound-1. We can change this to record
3299 also statements not dominating the loop latch and update the walk bellow
3300 to the shortest path algorthm. */
3301 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3304 && elt
->bound
.ult (loop
->nb_iterations_upper_bound
))
3306 if (!not_executed_last_iteration
)
3307 not_executed_last_iteration
= pointer_set_create ();
3308 pointer_set_insert (not_executed_last_iteration
, elt
->stmt
);
3311 if (!not_executed_last_iteration
)
3314 /* Start DFS walk in the loop header and see if we can reach the
3315 loop latch or any of the exits (including statements with side
3316 effects that may terminate the loop otherwise) without visiting
3317 any of the statements known to have undefined effect on the last
3319 queue
.safe_push (loop
->header
);
3320 visited
= BITMAP_ALLOC (NULL
);
3321 bitmap_set_bit (visited
, loop
->header
->index
);
3326 basic_block bb
= queue
.pop ();
3327 gimple_stmt_iterator gsi
;
3328 bool stmt_found
= false;
3330 /* Loop for possible exits and statements bounding the execution. */
3331 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3333 gimple stmt
= gsi_stmt (gsi
);
3334 if (pointer_set_contains (not_executed_last_iteration
, stmt
))
3339 if (gimple_has_side_effects (stmt
))
3348 /* If no bounding statement is found, continue the walk. */
3354 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3356 if (loop_exit_edge_p (loop
, e
)
3357 || e
== loop_latch_edge (loop
))
3362 if (bitmap_set_bit (visited
, e
->dest
->index
))
3363 queue
.safe_push (e
->dest
);
3367 while (queue
.length () && !found_exit
);
3369 /* If every path through the loop reach bounding statement before exit,
3370 then we know the last iteration of the loop will have undefined effect
3371 and we can decrease number of iterations. */
3375 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3376 fprintf (dump_file
, "Reducing loop iteration estimate by 1; "
3377 "undefined statement must be executed at the last iteration.\n");
3378 record_niter_bound (loop
, loop
->nb_iterations_upper_bound
- double_int_one
,
3381 BITMAP_FREE (visited
);
3383 pointer_set_destroy (not_executed_last_iteration
);
3386 /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
3387 is true also use estimates derived from undefined behavior. */
3390 estimate_numbers_of_iterations_loop (struct loop
*loop
)
3395 struct tree_niter_desc niter_desc
;
3400 /* Give up if we already have tried to compute an estimation. */
3401 if (loop
->estimate_state
!= EST_NOT_COMPUTED
)
3404 loop
->estimate_state
= EST_AVAILABLE
;
3405 /* Force estimate compuation but leave any existing upper bound in place. */
3406 loop
->any_estimate
= false;
3408 /* Ensure that loop->nb_iterations is computed if possible. If it turns out
3409 to be constant, we avoid undefined behavior implied bounds and instead
3410 diagnose those loops with -Waggressive-loop-optimizations. */
3411 number_of_latch_executions (loop
);
3413 exits
= get_loop_exit_edges (loop
);
3414 likely_exit
= single_likely_exit (loop
);
3415 FOR_EACH_VEC_ELT (exits
, i
, ex
)
3417 if (!number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
3420 niter
= niter_desc
.niter
;
3421 type
= TREE_TYPE (niter
);
3422 if (TREE_CODE (niter_desc
.may_be_zero
) != INTEGER_CST
)
3423 niter
= build3 (COND_EXPR
, type
, niter_desc
.may_be_zero
,
3424 build_int_cst (type
, 0),
3426 record_estimate (loop
, niter
, niter_desc
.max
,
3427 last_stmt (ex
->src
),
3428 true, ex
== likely_exit
, true);
3432 if (flag_aggressive_loop_optimizations
)
3433 infer_loop_bounds_from_undefined (loop
);
3435 discover_iteration_bound_by_body_walk (loop
);
3437 maybe_lower_iteration_bound (loop
);
3439 /* If we have a measured profile, use it to estimate the number of
3441 if (loop
->header
->count
!= 0)
3443 gcov_type nit
= expected_loop_iterations_unbounded (loop
) + 1;
3444 bound
= gcov_type_to_double_int (nit
);
3445 record_niter_bound (loop
, bound
, true, false);
3448 /* If we know the exact number of iterations of this loop, try to
3449 not break code with undefined behavior by not recording smaller
3450 maximum number of iterations. */
3451 if (loop
->nb_iterations
3452 && TREE_CODE (loop
->nb_iterations
) == INTEGER_CST
)
3454 loop
->any_upper_bound
= true;
3455 loop
->nb_iterations_upper_bound
3456 = tree_to_double_int (loop
->nb_iterations
);
3460 /* Sets NIT to the estimated number of executions of the latch of the
3461 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
3462 large as the number of iterations. If we have no reliable estimate,
3463 the function returns false, otherwise returns true. */
3466 estimated_loop_iterations (struct loop
*loop
, double_int
*nit
)
3468 /* When SCEV information is available, try to update loop iterations
3469 estimate. Otherwise just return whatever we recorded earlier. */
3470 if (scev_initialized_p ())
3471 estimate_numbers_of_iterations_loop (loop
);
3473 return (get_estimated_loop_iterations (loop
, nit
));
3476 /* Similar to estimated_loop_iterations, but returns the estimate only
3477 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3478 on the number of iterations of LOOP could not be derived, returns -1. */
3481 estimated_loop_iterations_int (struct loop
*loop
)
3484 HOST_WIDE_INT hwi_nit
;
3486 if (!estimated_loop_iterations (loop
, &nit
))
3489 if (!nit
.fits_shwi ())
3491 hwi_nit
= nit
.to_shwi ();
3493 return hwi_nit
< 0 ? -1 : hwi_nit
;
3497 /* Sets NIT to an upper bound for the maximum number of executions of the
3498 latch of the LOOP. If we have no reliable estimate, the function returns
3499 false, otherwise returns true. */
3502 max_loop_iterations (struct loop
*loop
, double_int
*nit
)
3504 /* When SCEV information is available, try to update loop iterations
3505 estimate. Otherwise just return whatever we recorded earlier. */
3506 if (scev_initialized_p ())
3507 estimate_numbers_of_iterations_loop (loop
);
3509 return get_max_loop_iterations (loop
, nit
);
3512 /* Similar to max_loop_iterations, but returns the estimate only
3513 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3514 on the number of iterations of LOOP could not be derived, returns -1. */
3517 max_loop_iterations_int (struct loop
*loop
)
3520 HOST_WIDE_INT hwi_nit
;
3522 if (!max_loop_iterations (loop
, &nit
))
3525 if (!nit
.fits_shwi ())
3527 hwi_nit
= nit
.to_shwi ();
3529 return hwi_nit
< 0 ? -1 : hwi_nit
;
3532 /* Returns an estimate for the number of executions of statements
3533 in the LOOP. For statements before the loop exit, this exceeds
3534 the number of execution of the latch by one. */
3537 estimated_stmt_executions_int (struct loop
*loop
)
3539 HOST_WIDE_INT nit
= estimated_loop_iterations_int (loop
);
3545 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
3547 /* If the computation overflows, return -1. */
3548 return snit
< 0 ? -1 : snit
;
3551 /* Sets NIT to the estimated maximum number of executions of the latch of the
3552 LOOP, plus one. If we have no reliable estimate, the function returns
3553 false, otherwise returns true. */
3556 max_stmt_executions (struct loop
*loop
, double_int
*nit
)
3558 double_int nit_minus_one
;
3560 if (!max_loop_iterations (loop
, nit
))
3563 nit_minus_one
= *nit
;
3565 *nit
+= double_int_one
;
3567 return (*nit
).ugt (nit_minus_one
);
3570 /* Sets NIT to the estimated number of executions of the latch of the
3571 LOOP, plus one. If we have no reliable estimate, the function returns
3572 false, otherwise returns true. */
3575 estimated_stmt_executions (struct loop
*loop
, double_int
*nit
)
3577 double_int nit_minus_one
;
3579 if (!estimated_loop_iterations (loop
, nit
))
3582 nit_minus_one
= *nit
;
3584 *nit
+= double_int_one
;
3586 return (*nit
).ugt (nit_minus_one
);
3589 /* Records estimates on numbers of iterations of loops. */
3592 estimate_numbers_of_iterations (void)
3596 /* We don't want to issue signed overflow warnings while getting
3597 loop iteration estimates. */
3598 fold_defer_overflow_warnings ();
3600 FOR_EACH_LOOP (loop
, 0)
3602 estimate_numbers_of_iterations_loop (loop
);
3605 fold_undefer_and_ignore_overflow_warnings ();
3608 /* Returns true if statement S1 dominates statement S2. */
3611 stmt_dominates_stmt_p (gimple s1
, gimple s2
)
3613 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
3621 gimple_stmt_iterator bsi
;
3623 if (gimple_code (s2
) == GIMPLE_PHI
)
3626 if (gimple_code (s1
) == GIMPLE_PHI
)
3629 for (bsi
= gsi_start_bb (bb1
); gsi_stmt (bsi
) != s2
; gsi_next (&bsi
))
3630 if (gsi_stmt (bsi
) == s1
)
3636 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
3639 /* Returns true when we can prove that the number of executions of
3640 STMT in the loop is at most NITER, according to the bound on
3641 the number of executions of the statement NITER_BOUND->stmt recorded in
3642 NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT.
3644 ??? This code can become quite a CPU hog - we can have many bounds,
3645 and large basic block forcing stmt_dominates_stmt_p to be queried
3646 many times on a large basic blocks, so the whole thing is O(n^2)
3647 for scev_probably_wraps_p invocation (that can be done n times).
3649 It would make more sense (and give better answers) to remember BB
3650 bounds computed by discover_iteration_bound_by_body_walk. */
3653 n_of_executions_at_most (gimple stmt
,
3654 struct nb_iter_bound
*niter_bound
,
3657 double_int bound
= niter_bound
->bound
;
3658 tree nit_type
= TREE_TYPE (niter
), e
;
3661 gcc_assert (TYPE_UNSIGNED (nit_type
));
3663 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
3664 the number of iterations is small. */
3665 if (!double_int_fits_to_tree_p (nit_type
, bound
))
3668 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3669 times. This means that:
3671 -- if NITER_BOUND->is_exit is true, then everything after
3672 it at most NITER_BOUND->bound times.
3674 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
3675 is executed, then NITER_BOUND->stmt is executed as well in the same
3676 iteration then STMT is executed at most NITER_BOUND->bound + 1 times.
3678 If we can determine that NITER_BOUND->stmt is always executed
3679 after STMT, then STMT is executed at most NITER_BOUND->bound + 2 times.
3680 We conclude that if both statements belong to the same
3681 basic block and STMT is before NITER_BOUND->stmt and there are no
3682 statements with side effects in between. */
3684 if (niter_bound
->is_exit
)
3686 if (stmt
== niter_bound
->stmt
3687 || !stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
3693 if (!stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
3695 gimple_stmt_iterator bsi
;
3696 if (gimple_bb (stmt
) != gimple_bb (niter_bound
->stmt
)
3697 || gimple_code (stmt
) == GIMPLE_PHI
3698 || gimple_code (niter_bound
->stmt
) == GIMPLE_PHI
)
3701 /* By stmt_dominates_stmt_p we already know that STMT appears
3702 before NITER_BOUND->STMT. Still need to test that the loop
3703 can not be terinated by a side effect in between. */
3704 for (bsi
= gsi_for_stmt (stmt
); gsi_stmt (bsi
) != niter_bound
->stmt
;
3706 if (gimple_has_side_effects (gsi_stmt (bsi
)))
3708 bound
+= double_int_one
;
3709 if (bound
.is_zero ()
3710 || !double_int_fits_to_tree_p (nit_type
, bound
))
3716 e
= fold_binary (cmp
, boolean_type_node
,
3717 niter
, double_int_to_tree (nit_type
, bound
));
3718 return e
&& integer_nonzerop (e
);
3721 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
3724 nowrap_type_p (tree type
)
3726 if (INTEGRAL_TYPE_P (type
)
3727 && TYPE_OVERFLOW_UNDEFINED (type
))
3730 if (POINTER_TYPE_P (type
))
3736 /* Return false only when the induction variable BASE + STEP * I is
3737 known to not overflow: i.e. when the number of iterations is small
3738 enough with respect to the step and initial condition in order to
3739 keep the evolution confined in TYPEs bounds. Return true when the
3740 iv is known to overflow or when the property is not computable.
3742 USE_OVERFLOW_SEMANTICS is true if this function should assume that
3743 the rules for overflow of the given language apply (e.g., that signed
3744 arithmetics in C does not overflow). */
3747 scev_probably_wraps_p (tree base
, tree step
,
3748 gimple at_stmt
, struct loop
*loop
,
3749 bool use_overflow_semantics
)
3751 tree delta
, step_abs
;
3752 tree unsigned_type
, valid_niter
;
3753 tree type
= TREE_TYPE (step
);
3756 struct nb_iter_bound
*bound
;
3758 /* FIXME: We really need something like
3759 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
3761 We used to test for the following situation that frequently appears
3762 during address arithmetics:
3764 D.1621_13 = (long unsigned intD.4) D.1620_12;
3765 D.1622_14 = D.1621_13 * 8;
3766 D.1623_15 = (doubleD.29 *) D.1622_14;
3768 And derived that the sequence corresponding to D_14
3769 can be proved to not wrap because it is used for computing a
3770 memory access; however, this is not really the case -- for example,
3771 if D_12 = (unsigned char) [254,+,1], then D_14 has values
3772 2032, 2040, 0, 8, ..., but the code is still legal. */
3774 if (chrec_contains_undetermined (base
)
3775 || chrec_contains_undetermined (step
))
3778 if (integer_zerop (step
))
3781 /* If we can use the fact that signed and pointer arithmetics does not
3782 wrap, we are done. */
3783 if (use_overflow_semantics
&& nowrap_type_p (TREE_TYPE (base
)))
3786 /* To be able to use estimates on number of iterations of the loop,
3787 we must have an upper bound on the absolute value of the step. */
3788 if (TREE_CODE (step
) != INTEGER_CST
)
3791 /* Don't issue signed overflow warnings. */
3792 fold_defer_overflow_warnings ();
3794 /* Otherwise, compute the number of iterations before we reach the
3795 bound of the type, and verify that the loop is exited before this
3797 unsigned_type
= unsigned_type_for (type
);
3798 base
= fold_convert (unsigned_type
, base
);
3800 if (tree_int_cst_sign_bit (step
))
3802 tree extreme
= fold_convert (unsigned_type
,
3803 lower_bound_in_type (type
, type
));
3804 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
3805 step_abs
= fold_build1 (NEGATE_EXPR
, unsigned_type
,
3806 fold_convert (unsigned_type
, step
));
3810 tree extreme
= fold_convert (unsigned_type
,
3811 upper_bound_in_type (type
, type
));
3812 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
3813 step_abs
= fold_convert (unsigned_type
, step
);
3816 valid_niter
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step_abs
);
3818 estimate_numbers_of_iterations_loop (loop
);
3820 if (max_loop_iterations (loop
, &niter
)
3821 && double_int_fits_to_tree_p (TREE_TYPE (valid_niter
), niter
)
3822 && (e
= fold_binary (GT_EXPR
, boolean_type_node
, valid_niter
,
3823 double_int_to_tree (TREE_TYPE (valid_niter
),
3825 && integer_nonzerop (e
))
3827 fold_undefer_and_ignore_overflow_warnings ();
3831 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
3833 if (n_of_executions_at_most (at_stmt
, bound
, valid_niter
))
3835 fold_undefer_and_ignore_overflow_warnings ();
3840 fold_undefer_and_ignore_overflow_warnings ();
3842 /* At this point we still don't have a proof that the iv does not
3843 overflow: give up. */
3847 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
3850 free_numbers_of_iterations_estimates_loop (struct loop
*loop
)
3852 struct nb_iter_bound
*bound
, *next
;
3854 loop
->nb_iterations
= NULL
;
3855 loop
->estimate_state
= EST_NOT_COMPUTED
;
3856 for (bound
= loop
->bounds
; bound
; bound
= next
)
3862 loop
->bounds
= NULL
;
3865 /* Frees the information on upper bounds on numbers of iterations of loops. */
3868 free_numbers_of_iterations_estimates (void)
3872 FOR_EACH_LOOP (loop
, 0)
3874 free_numbers_of_iterations_estimates_loop (loop
);
3878 /* Substitute value VAL for ssa name NAME inside expressions held
3882 substitute_in_loop_info (struct loop
*loop
, tree name
, tree val
)
3884 loop
->nb_iterations
= simplify_replace_tree (loop
->nb_iterations
, name
, val
);