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"
58 #include "wide-int-print.h"
61 #define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
63 /* The maximum number of dominator BBs we search for conditions
64 of loop header copies we use for simplifying a conditional
66 #define MAX_DOMINATORS_TO_WALK 8
70 Analysis of number of iterations of an affine exit test.
74 /* Bounds on some value, BELOW <= X <= UP. */
82 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */
85 split_to_var_and_offset (tree expr
, tree
*var
, mpz_t offset
)
87 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 wi::to_mpz (op1
, offset
, SIGNED
);
112 mpz_neg (offset
, offset
);
116 *var
= build_int_cst_type (type
, 0);
117 wi::to_mpz (expr
, offset
, TYPE_SIGN (type
));
125 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
126 in TYPE to MIN and MAX. */
129 determine_value_range (struct loop
*loop
, tree type
, tree var
, mpz_t off
,
130 mpz_t min
, mpz_t max
)
133 enum value_range_type rtype
= VR_VARYING
;
135 /* If the expression is a constant, we know its value exactly. */
136 if (integer_zerop (var
))
143 get_type_static_bounds (type
, min
, max
);
145 /* See if we have some range info from VRP. */
146 if (TREE_CODE (var
) == SSA_NAME
&& INTEGRAL_TYPE_P (type
))
148 edge e
= loop_preheader_edge (loop
);
149 signop sgn
= TYPE_SIGN (type
);
150 gimple_stmt_iterator gsi
;
152 /* Either for VAR itself... */
153 rtype
= get_range_info (var
, &minv
, &maxv
);
154 /* Or for PHI results in loop->header where VAR is used as
155 PHI argument from the loop preheader edge. */
156 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
158 gimple phi
= gsi_stmt (gsi
);
160 if (PHI_ARG_DEF_FROM_EDGE (phi
, e
) == var
161 && (get_range_info (gimple_phi_result (phi
), &minc
, &maxc
)
164 if (rtype
!= VR_RANGE
)
172 minv
= wi::max (minv
, minc
, sgn
);
173 maxv
= wi::min (maxv
, maxc
, sgn
);
174 gcc_assert (wi::le_p (minv
, maxv
, sgn
));
178 if (rtype
== VR_RANGE
)
181 gcc_assert (wi::le_p (minv
, maxv
, sgn
));
184 wi::to_mpz (minv
, minm
, sgn
);
185 wi::to_mpz (maxv
, maxm
, sgn
);
186 mpz_add (minm
, minm
, off
);
187 mpz_add (maxm
, maxm
, off
);
188 /* If the computation may not wrap or off is zero, then this
189 is always fine. If off is negative and minv + off isn't
190 smaller than type's minimum, or off is positive and
191 maxv + off isn't bigger than type's maximum, use the more
192 precise range too. */
193 if (nowrap_type_p (type
)
194 || mpz_sgn (off
) == 0
195 || (mpz_sgn (off
) < 0 && mpz_cmp (minm
, min
) >= 0)
196 || (mpz_sgn (off
) > 0 && mpz_cmp (maxm
, max
) <= 0))
209 /* If the computation may wrap, we know nothing about the value, except for
210 the range of the type. */
211 if (!nowrap_type_p (type
))
214 /* Since the addition of OFF does not wrap, if OFF is positive, then we may
215 add it to MIN, otherwise to MAX. */
216 if (mpz_sgn (off
) < 0)
217 mpz_add (max
, max
, off
);
219 mpz_add (min
, min
, off
);
222 /* Stores the bounds on the difference of the values of the expressions
223 (var + X) and (var + Y), computed in TYPE, to BNDS. */
226 bound_difference_of_offsetted_base (tree type
, mpz_t x
, mpz_t y
,
229 int rel
= mpz_cmp (x
, y
);
230 bool may_wrap
= !nowrap_type_p (type
);
233 /* If X == Y, then the expressions are always equal.
234 If X > Y, there are the following possibilities:
235 a) neither of var + X and var + Y overflow or underflow, or both of
236 them do. Then their difference is X - Y.
237 b) var + X overflows, and var + Y does not. Then the values of the
238 expressions are var + X - M and var + Y, where M is the range of
239 the type, and their difference is X - Y - M.
240 c) var + Y underflows and var + X does not. Their difference again
242 Therefore, if the arithmetics in type does not overflow, then the
243 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
244 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
245 (X - Y, X - Y + M). */
249 mpz_set_ui (bnds
->below
, 0);
250 mpz_set_ui (bnds
->up
, 0);
255 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), m
, UNSIGNED
);
256 mpz_add_ui (m
, m
, 1);
257 mpz_sub (bnds
->up
, x
, y
);
258 mpz_set (bnds
->below
, bnds
->up
);
263 mpz_sub (bnds
->below
, bnds
->below
, m
);
265 mpz_add (bnds
->up
, bnds
->up
, m
);
271 /* From condition C0 CMP C1 derives information regarding the
272 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
273 and stores it to BNDS. */
276 refine_bounds_using_guard (tree type
, tree varx
, mpz_t offx
,
277 tree vary
, mpz_t offy
,
278 tree c0
, enum tree_code cmp
, tree c1
,
281 tree varc0
, varc1
, tmp
, ctype
;
282 mpz_t offc0
, offc1
, loffx
, loffy
, bnd
;
284 bool no_wrap
= nowrap_type_p (type
);
293 STRIP_SIGN_NOPS (c0
);
294 STRIP_SIGN_NOPS (c1
);
295 ctype
= TREE_TYPE (c0
);
296 if (!useless_type_conversion_p (ctype
, type
))
302 /* We could derive quite precise information from EQ_EXPR, however, such
303 a guard is unlikely to appear, so we do not bother with handling
308 /* NE_EXPR comparisons do not contain much of useful information, except for
309 special case of comparing with the bounds of the type. */
310 if (TREE_CODE (c1
) != INTEGER_CST
311 || !INTEGRAL_TYPE_P (type
))
314 /* Ensure that the condition speaks about an expression in the same type
316 ctype
= TREE_TYPE (c0
);
317 if (TYPE_PRECISION (ctype
) != TYPE_PRECISION (type
))
319 c0
= fold_convert (type
, c0
);
320 c1
= fold_convert (type
, c1
);
322 if (TYPE_MIN_VALUE (type
)
323 && operand_equal_p (c1
, TYPE_MIN_VALUE (type
), 0))
328 if (TYPE_MAX_VALUE (type
)
329 && operand_equal_p (c1
, TYPE_MAX_VALUE (type
), 0))
342 split_to_var_and_offset (expand_simple_operations (c0
), &varc0
, offc0
);
343 split_to_var_and_offset (expand_simple_operations (c1
), &varc1
, offc1
);
345 /* We are only interested in comparisons of expressions based on VARX and
346 VARY. TODO -- we might also be able to derive some bounds from
347 expressions containing just one of the variables. */
349 if (operand_equal_p (varx
, varc1
, 0))
351 tmp
= varc0
; varc0
= varc1
; varc1
= tmp
;
352 mpz_swap (offc0
, offc1
);
353 cmp
= swap_tree_comparison (cmp
);
356 if (!operand_equal_p (varx
, varc0
, 0)
357 || !operand_equal_p (vary
, varc1
, 0))
360 mpz_init_set (loffx
, offx
);
361 mpz_init_set (loffy
, offy
);
363 if (cmp
== GT_EXPR
|| cmp
== GE_EXPR
)
365 tmp
= varx
; varx
= vary
; vary
= tmp
;
366 mpz_swap (offc0
, offc1
);
367 mpz_swap (loffx
, loffy
);
368 cmp
= swap_tree_comparison (cmp
);
372 /* If there is no overflow, the condition implies that
374 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
376 The overflows and underflows may complicate things a bit; each
377 overflow decreases the appropriate offset by M, and underflow
378 increases it by M. The above inequality would not necessarily be
381 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
382 VARX + OFFC0 overflows, but VARX + OFFX does not.
383 This may only happen if OFFX < OFFC0.
384 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
385 VARY + OFFC1 underflows and VARY + OFFY does not.
386 This may only happen if OFFY > OFFC1. */
395 x_ok
= (integer_zerop (varx
)
396 || mpz_cmp (loffx
, offc0
) >= 0);
397 y_ok
= (integer_zerop (vary
)
398 || mpz_cmp (loffy
, offc1
) <= 0);
404 mpz_sub (bnd
, loffx
, loffy
);
405 mpz_add (bnd
, bnd
, offc1
);
406 mpz_sub (bnd
, bnd
, offc0
);
409 mpz_sub_ui (bnd
, bnd
, 1);
414 if (mpz_cmp (bnds
->below
, bnd
) < 0)
415 mpz_set (bnds
->below
, bnd
);
419 if (mpz_cmp (bnd
, bnds
->up
) < 0)
420 mpz_set (bnds
->up
, bnd
);
432 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
433 The subtraction is considered to be performed in arbitrary precision,
436 We do not attempt to be too clever regarding the value ranges of X and
437 Y; most of the time, they are just integers or ssa names offsetted by
438 integer. However, we try to use the information contained in the
439 comparisons before the loop (usually created by loop header copying). */
442 bound_difference (struct loop
*loop
, tree x
, tree y
, bounds
*bnds
)
444 tree type
= TREE_TYPE (x
);
447 mpz_t minx
, maxx
, miny
, maxy
;
455 /* Get rid of unnecessary casts, but preserve the value of
460 mpz_init (bnds
->below
);
464 split_to_var_and_offset (x
, &varx
, offx
);
465 split_to_var_and_offset (y
, &vary
, offy
);
467 if (!integer_zerop (varx
)
468 && operand_equal_p (varx
, vary
, 0))
470 /* Special case VARX == VARY -- we just need to compare the
471 offsets. The matters are a bit more complicated in the
472 case addition of offsets may wrap. */
473 bound_difference_of_offsetted_base (type
, offx
, offy
, bnds
);
477 /* Otherwise, use the value ranges to determine the initial
478 estimates on below and up. */
483 determine_value_range (loop
, type
, varx
, offx
, minx
, maxx
);
484 determine_value_range (loop
, type
, vary
, offy
, miny
, maxy
);
486 mpz_sub (bnds
->below
, minx
, maxy
);
487 mpz_sub (bnds
->up
, maxx
, miny
);
494 /* If both X and Y are constants, we cannot get any more precise. */
495 if (integer_zerop (varx
) && integer_zerop (vary
))
498 /* Now walk the dominators of the loop header and use the entry
499 guards to refine the estimates. */
500 for (bb
= loop
->header
;
501 bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && cnt
< MAX_DOMINATORS_TO_WALK
;
502 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
504 if (!single_pred_p (bb
))
506 e
= single_pred_edge (bb
);
508 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
511 cond
= last_stmt (e
->src
);
512 c0
= gimple_cond_lhs (cond
);
513 cmp
= gimple_cond_code (cond
);
514 c1
= gimple_cond_rhs (cond
);
516 if (e
->flags
& EDGE_FALSE_VALUE
)
517 cmp
= invert_tree_comparison (cmp
, false);
519 refine_bounds_using_guard (type
, varx
, offx
, vary
, offy
,
529 /* Update the bounds in BNDS that restrict the value of X to the bounds
530 that restrict the value of X + DELTA. X can be obtained as a
531 difference of two values in TYPE. */
534 bounds_add (bounds
*bnds
, const widest_int
&delta
, tree type
)
539 wi::to_mpz (delta
, mdelta
, SIGNED
);
542 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), max
, UNSIGNED
);
544 mpz_add (bnds
->up
, bnds
->up
, mdelta
);
545 mpz_add (bnds
->below
, bnds
->below
, mdelta
);
547 if (mpz_cmp (bnds
->up
, max
) > 0)
548 mpz_set (bnds
->up
, max
);
551 if (mpz_cmp (bnds
->below
, max
) < 0)
552 mpz_set (bnds
->below
, max
);
558 /* Update the bounds in BNDS that restrict the value of X to the bounds
559 that restrict the value of -X. */
562 bounds_negate (bounds
*bnds
)
566 mpz_init_set (tmp
, bnds
->up
);
567 mpz_neg (bnds
->up
, bnds
->below
);
568 mpz_neg (bnds
->below
, tmp
);
572 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
575 inverse (tree x
, tree mask
)
577 tree type
= TREE_TYPE (x
);
579 unsigned ctr
= tree_floor_log2 (mask
);
581 if (TYPE_PRECISION (type
) <= HOST_BITS_PER_WIDE_INT
)
583 unsigned HOST_WIDE_INT ix
;
584 unsigned HOST_WIDE_INT imask
;
585 unsigned HOST_WIDE_INT irslt
= 1;
587 gcc_assert (cst_and_fits_in_hwi (x
));
588 gcc_assert (cst_and_fits_in_hwi (mask
));
590 ix
= int_cst_value (x
);
591 imask
= int_cst_value (mask
);
600 rslt
= build_int_cst_type (type
, irslt
);
604 rslt
= build_int_cst (type
, 1);
607 rslt
= int_const_binop (MULT_EXPR
, rslt
, x
);
608 x
= int_const_binop (MULT_EXPR
, x
, x
);
610 rslt
= int_const_binop (BIT_AND_EXPR
, rslt
, mask
);
616 /* Derives the upper bound BND on the number of executions of loop with exit
617 condition S * i <> C. If NO_OVERFLOW is true, then the control variable of
618 the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed
619 that the loop ends through this exit, i.e., the induction variable ever
620 reaches the value of C.
622 The value C is equal to final - base, where final and base are the final and
623 initial value of the actual induction variable in the analysed loop. BNDS
624 bounds the value of this difference when computed in signed type with
625 unbounded range, while the computation of C is performed in an unsigned
626 type with the range matching the range of the type of the induction variable.
627 In particular, BNDS.up contains an upper bound on C in the following cases:
628 -- if the iv must reach its final value without overflow, i.e., if
629 NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
630 -- if final >= base, which we know to hold when BNDS.below >= 0. */
633 number_of_iterations_ne_max (mpz_t bnd
, bool no_overflow
, tree c
, tree s
,
634 bounds
*bnds
, bool exit_must_be_taken
)
638 tree type
= TREE_TYPE (c
);
639 bool bnds_u_valid
= ((no_overflow
&& exit_must_be_taken
)
640 || mpz_sgn (bnds
->below
) >= 0);
643 || (TREE_CODE (c
) == INTEGER_CST
644 && TREE_CODE (s
) == INTEGER_CST
645 && wi::mod_trunc (c
, s
, TYPE_SIGN (type
)) == 0)
646 || (TYPE_OVERFLOW_UNDEFINED (type
)
647 && multiple_of_p (type
, c
, s
)))
649 /* If C is an exact multiple of S, then its value will be reached before
650 the induction variable overflows (unless the loop is exited in some
651 other way before). Note that the actual induction variable in the
652 loop (which ranges from base to final instead of from 0 to C) may
653 overflow, in which case BNDS.up will not be giving a correct upper
654 bound on C; thus, BNDS_U_VALID had to be computed in advance. */
656 exit_must_be_taken
= true;
659 /* If the induction variable can overflow, the number of iterations is at
660 most the period of the control variable (or infinite, but in that case
661 the whole # of iterations analysis will fail). */
664 max
= wi::mask
<widest_int
> (TYPE_PRECISION (type
) - wi::ctz (s
), false);
665 wi::to_mpz (max
, bnd
, UNSIGNED
);
669 /* Now we know that the induction variable does not overflow, so the loop
670 iterates at most (range of type / S) times. */
671 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), bnd
, UNSIGNED
);
673 /* If the induction variable is guaranteed to reach the value of C before
675 if (exit_must_be_taken
)
677 /* ... then we can strengthen this to C / S, and possibly we can use
678 the upper bound on C given by BNDS. */
679 if (TREE_CODE (c
) == INTEGER_CST
)
680 wi::to_mpz (c
, bnd
, UNSIGNED
);
681 else if (bnds_u_valid
)
682 mpz_set (bnd
, bnds
->up
);
686 wi::to_mpz (s
, d
, UNSIGNED
);
687 mpz_fdiv_q (bnd
, bnd
, d
);
691 /* Determines number of iterations of loop whose ending condition
692 is IV <> FINAL. TYPE is the type of the iv. The number of
693 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
694 we know that the exit must be taken eventually, i.e., that the IV
695 ever reaches the value FINAL (we derived this earlier, and possibly set
696 NITER->assumptions to make sure this is the case). BNDS contains the
697 bounds on the difference FINAL - IV->base. */
700 number_of_iterations_ne (tree type
, affine_iv
*iv
, tree final
,
701 struct tree_niter_desc
*niter
, bool exit_must_be_taken
,
704 tree niter_type
= unsigned_type_for (type
);
705 tree s
, c
, d
, bits
, assumption
, tmp
, bound
;
708 niter
->control
= *iv
;
709 niter
->bound
= final
;
710 niter
->cmp
= NE_EXPR
;
712 /* Rearrange the terms so that we get inequality S * i <> C, with S
713 positive. Also cast everything to the unsigned type. If IV does
714 not overflow, BNDS bounds the value of C. Also, this is the
715 case if the computation |FINAL - IV->base| does not overflow, i.e.,
716 if BNDS->below in the result is nonnegative. */
717 if (tree_int_cst_sign_bit (iv
->step
))
719 s
= fold_convert (niter_type
,
720 fold_build1 (NEGATE_EXPR
, type
, iv
->step
));
721 c
= fold_build2 (MINUS_EXPR
, niter_type
,
722 fold_convert (niter_type
, iv
->base
),
723 fold_convert (niter_type
, final
));
724 bounds_negate (bnds
);
728 s
= fold_convert (niter_type
, iv
->step
);
729 c
= fold_build2 (MINUS_EXPR
, niter_type
,
730 fold_convert (niter_type
, final
),
731 fold_convert (niter_type
, iv
->base
));
735 number_of_iterations_ne_max (max
, iv
->no_overflow
, c
, s
, bnds
,
737 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, max
, false),
738 TYPE_SIGN (niter_type
));
741 /* First the trivial cases -- when the step is 1. */
742 if (integer_onep (s
))
748 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
749 is infinite. Otherwise, the number of iterations is
750 (inverse(s/d) * (c/d)) mod (size of mode/d). */
751 bits
= num_ending_zeros (s
);
752 bound
= build_low_bits_mask (niter_type
,
753 (TYPE_PRECISION (niter_type
)
754 - tree_to_uhwi (bits
)));
756 d
= fold_binary_to_constant (LSHIFT_EXPR
, niter_type
,
757 build_int_cst (niter_type
, 1), bits
);
758 s
= fold_binary_to_constant (RSHIFT_EXPR
, niter_type
, s
, bits
);
760 if (!exit_must_be_taken
)
762 /* If we cannot assume that the exit is taken eventually, record the
763 assumptions for divisibility of c. */
764 assumption
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, c
, d
);
765 assumption
= fold_build2 (EQ_EXPR
, boolean_type_node
,
766 assumption
, build_int_cst (niter_type
, 0));
767 if (!integer_nonzerop (assumption
))
768 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
769 niter
->assumptions
, assumption
);
772 c
= fold_build2 (EXACT_DIV_EXPR
, niter_type
, c
, d
);
773 tmp
= fold_build2 (MULT_EXPR
, niter_type
, c
, inverse (s
, bound
));
774 niter
->niter
= fold_build2 (BIT_AND_EXPR
, niter_type
, tmp
, bound
);
778 /* Checks whether we can determine the final value of the control variable
779 of the loop with ending condition IV0 < IV1 (computed in TYPE).
780 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
781 of the step. The assumptions necessary to ensure that the computation
782 of the final value does not overflow are recorded in NITER. If we
783 find the final value, we adjust DELTA and return TRUE. Otherwise
784 we return false. BNDS bounds the value of IV1->base - IV0->base,
785 and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
786 true if we know that the exit must be taken eventually. */
789 number_of_iterations_lt_to_ne (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
790 struct tree_niter_desc
*niter
,
791 tree
*delta
, tree step
,
792 bool exit_must_be_taken
, bounds
*bnds
)
794 tree niter_type
= TREE_TYPE (step
);
795 tree mod
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, *delta
, step
);
798 tree assumption
= boolean_true_node
, bound
, noloop
;
799 bool ret
= false, fv_comp_no_overflow
;
801 if (POINTER_TYPE_P (type
))
804 if (TREE_CODE (mod
) != INTEGER_CST
)
806 if (integer_nonzerop (mod
))
807 mod
= fold_build2 (MINUS_EXPR
, niter_type
, step
, mod
);
808 tmod
= fold_convert (type1
, mod
);
811 wi::to_mpz (mod
, mmod
, UNSIGNED
);
812 mpz_neg (mmod
, mmod
);
814 /* If the induction variable does not overflow and the exit is taken,
815 then the computation of the final value does not overflow. This is
816 also obviously the case if the new final value is equal to the
817 current one. Finally, we postulate this for pointer type variables,
818 as the code cannot rely on the object to that the pointer points being
819 placed at the end of the address space (and more pragmatically,
820 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
821 if (integer_zerop (mod
) || POINTER_TYPE_P (type
))
822 fv_comp_no_overflow
= true;
823 else if (!exit_must_be_taken
)
824 fv_comp_no_overflow
= false;
826 fv_comp_no_overflow
=
827 (iv0
->no_overflow
&& integer_nonzerop (iv0
->step
))
828 || (iv1
->no_overflow
&& integer_nonzerop (iv1
->step
));
830 if (integer_nonzerop (iv0
->step
))
832 /* The final value of the iv is iv1->base + MOD, assuming that this
833 computation does not overflow, and that
834 iv0->base <= iv1->base + MOD. */
835 if (!fv_comp_no_overflow
)
837 bound
= fold_build2 (MINUS_EXPR
, type1
,
838 TYPE_MAX_VALUE (type1
), tmod
);
839 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
841 if (integer_zerop (assumption
))
844 if (mpz_cmp (mmod
, bnds
->below
) < 0)
845 noloop
= boolean_false_node
;
846 else if (POINTER_TYPE_P (type
))
847 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
849 fold_build_pointer_plus (iv1
->base
, tmod
));
851 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
853 fold_build2 (PLUS_EXPR
, type1
,
858 /* The final value of the iv is iv0->base - MOD, assuming that this
859 computation does not overflow, and that
860 iv0->base - MOD <= iv1->base. */
861 if (!fv_comp_no_overflow
)
863 bound
= fold_build2 (PLUS_EXPR
, type1
,
864 TYPE_MIN_VALUE (type1
), tmod
);
865 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
867 if (integer_zerop (assumption
))
870 if (mpz_cmp (mmod
, bnds
->below
) < 0)
871 noloop
= boolean_false_node
;
872 else if (POINTER_TYPE_P (type
))
873 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
874 fold_build_pointer_plus (iv0
->base
,
875 fold_build1 (NEGATE_EXPR
,
879 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
880 fold_build2 (MINUS_EXPR
, type1
,
885 if (!integer_nonzerop (assumption
))
886 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
889 if (!integer_zerop (noloop
))
890 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
893 bounds_add (bnds
, wi::to_widest (mod
), type
);
894 *delta
= fold_build2 (PLUS_EXPR
, niter_type
, *delta
, mod
);
902 /* Add assertions to NITER that ensure that the control variable of the loop
903 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
904 are TYPE. Returns false if we can prove that there is an overflow, true
905 otherwise. STEP is the absolute value of the step. */
908 assert_no_overflow_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
909 struct tree_niter_desc
*niter
, tree step
)
911 tree bound
, d
, assumption
, diff
;
912 tree niter_type
= TREE_TYPE (step
);
914 if (integer_nonzerop (iv0
->step
))
916 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
917 if (iv0
->no_overflow
)
920 /* If iv0->base is a constant, we can determine the last value before
921 overflow precisely; otherwise we conservatively assume
924 if (TREE_CODE (iv0
->base
) == INTEGER_CST
)
926 d
= fold_build2 (MINUS_EXPR
, niter_type
,
927 fold_convert (niter_type
, TYPE_MAX_VALUE (type
)),
928 fold_convert (niter_type
, iv0
->base
));
929 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
932 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
933 build_int_cst (niter_type
, 1));
934 bound
= fold_build2 (MINUS_EXPR
, type
,
935 TYPE_MAX_VALUE (type
), fold_convert (type
, diff
));
936 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
941 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
942 if (iv1
->no_overflow
)
945 if (TREE_CODE (iv1
->base
) == INTEGER_CST
)
947 d
= fold_build2 (MINUS_EXPR
, niter_type
,
948 fold_convert (niter_type
, iv1
->base
),
949 fold_convert (niter_type
, TYPE_MIN_VALUE (type
)));
950 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
953 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
954 build_int_cst (niter_type
, 1));
955 bound
= fold_build2 (PLUS_EXPR
, type
,
956 TYPE_MIN_VALUE (type
), fold_convert (type
, diff
));
957 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
961 if (integer_zerop (assumption
))
963 if (!integer_nonzerop (assumption
))
964 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
965 niter
->assumptions
, assumption
);
967 iv0
->no_overflow
= true;
968 iv1
->no_overflow
= true;
972 /* Add an assumption to NITER that a loop whose ending condition
973 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
974 bounds the value of IV1->base - IV0->base. */
977 assert_loop_rolls_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
978 struct tree_niter_desc
*niter
, bounds
*bnds
)
980 tree assumption
= boolean_true_node
, bound
, diff
;
981 tree mbz
, mbzl
, mbzr
, type1
;
982 bool rolls_p
, no_overflow_p
;
986 /* We are going to compute the number of iterations as
987 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
988 variant of TYPE. This formula only works if
990 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
992 (where MAX is the maximum value of the unsigned variant of TYPE, and
993 the computations in this formula are performed in full precision,
994 i.e., without overflows).
996 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
997 we have a condition of the form iv0->base - step < iv1->base before the loop,
998 and for loops iv0->base < iv1->base - step * i the condition
999 iv0->base < iv1->base + step, due to loop header copying, which enable us
1000 to prove the lower bound.
1002 The upper bound is more complicated. Unless the expressions for initial
1003 and final value themselves contain enough information, we usually cannot
1004 derive it from the context. */
1006 /* First check whether the answer does not follow from the bounds we gathered
1008 if (integer_nonzerop (iv0
->step
))
1009 dstep
= wi::to_widest (iv0
->step
);
1012 dstep
= wi::sext (wi::to_widest (iv1
->step
), TYPE_PRECISION (type
));
1017 wi::to_mpz (dstep
, mstep
, UNSIGNED
);
1018 mpz_neg (mstep
, mstep
);
1019 mpz_add_ui (mstep
, mstep
, 1);
1021 rolls_p
= mpz_cmp (mstep
, bnds
->below
) <= 0;
1024 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), max
, UNSIGNED
);
1025 mpz_add (max
, max
, mstep
);
1026 no_overflow_p
= (mpz_cmp (bnds
->up
, max
) <= 0
1027 /* For pointers, only values lying inside a single object
1028 can be compared or manipulated by pointer arithmetics.
1029 Gcc in general does not allow or handle objects larger
1030 than half of the address space, hence the upper bound
1031 is satisfied for pointers. */
1032 || POINTER_TYPE_P (type
));
1036 if (rolls_p
&& no_overflow_p
)
1040 if (POINTER_TYPE_P (type
))
1043 /* Now the hard part; we must formulate the assumption(s) as expressions, and
1044 we must be careful not to introduce overflow. */
1046 if (integer_nonzerop (iv0
->step
))
1048 diff
= fold_build2 (MINUS_EXPR
, type1
,
1049 iv0
->step
, build_int_cst (type1
, 1));
1051 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
1052 0 address never belongs to any object, we can assume this for
1054 if (!POINTER_TYPE_P (type
))
1056 bound
= fold_build2 (PLUS_EXPR
, type1
,
1057 TYPE_MIN_VALUE (type
), diff
);
1058 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
1062 /* And then we can compute iv0->base - diff, and compare it with
1064 mbzl
= fold_build2 (MINUS_EXPR
, type1
,
1065 fold_convert (type1
, iv0
->base
), diff
);
1066 mbzr
= fold_convert (type1
, iv1
->base
);
1070 diff
= fold_build2 (PLUS_EXPR
, type1
,
1071 iv1
->step
, build_int_cst (type1
, 1));
1073 if (!POINTER_TYPE_P (type
))
1075 bound
= fold_build2 (PLUS_EXPR
, type1
,
1076 TYPE_MAX_VALUE (type
), diff
);
1077 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
1081 mbzl
= fold_convert (type1
, iv0
->base
);
1082 mbzr
= fold_build2 (MINUS_EXPR
, type1
,
1083 fold_convert (type1
, iv1
->base
), diff
);
1086 if (!integer_nonzerop (assumption
))
1087 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1088 niter
->assumptions
, assumption
);
1091 mbz
= fold_build2 (GT_EXPR
, boolean_type_node
, mbzl
, mbzr
);
1092 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1093 niter
->may_be_zero
, mbz
);
1097 /* Determines number of iterations of loop whose ending condition
1098 is IV0 < IV1. TYPE is the type of the iv. The number of
1099 iterations is stored to NITER. BNDS bounds the difference
1100 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
1101 that the exit must be taken eventually. */
1104 number_of_iterations_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1105 struct tree_niter_desc
*niter
,
1106 bool exit_must_be_taken
, bounds
*bnds
)
1108 tree niter_type
= unsigned_type_for (type
);
1109 tree delta
, step
, s
;
1112 if (integer_nonzerop (iv0
->step
))
1114 niter
->control
= *iv0
;
1115 niter
->cmp
= LT_EXPR
;
1116 niter
->bound
= iv1
->base
;
1120 niter
->control
= *iv1
;
1121 niter
->cmp
= GT_EXPR
;
1122 niter
->bound
= iv0
->base
;
1125 delta
= fold_build2 (MINUS_EXPR
, niter_type
,
1126 fold_convert (niter_type
, iv1
->base
),
1127 fold_convert (niter_type
, iv0
->base
));
1129 /* First handle the special case that the step is +-1. */
1130 if ((integer_onep (iv0
->step
) && integer_zerop (iv1
->step
))
1131 || (integer_all_onesp (iv1
->step
) && integer_zerop (iv0
->step
)))
1133 /* for (i = iv0->base; i < iv1->base; i++)
1137 for (i = iv1->base; i > iv0->base; i--).
1139 In both cases # of iterations is iv1->base - iv0->base, assuming that
1140 iv1->base >= iv0->base.
1142 First try to derive a lower bound on the value of
1143 iv1->base - iv0->base, computed in full precision. If the difference
1144 is nonnegative, we are done, otherwise we must record the
1147 if (mpz_sgn (bnds
->below
) < 0)
1148 niter
->may_be_zero
= fold_build2 (LT_EXPR
, boolean_type_node
,
1149 iv1
->base
, iv0
->base
);
1150 niter
->niter
= delta
;
1151 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, bnds
->up
, false),
1152 TYPE_SIGN (niter_type
));
1156 if (integer_nonzerop (iv0
->step
))
1157 step
= fold_convert (niter_type
, iv0
->step
);
1159 step
= fold_convert (niter_type
,
1160 fold_build1 (NEGATE_EXPR
, type
, iv1
->step
));
1162 /* If we can determine the final value of the control iv exactly, we can
1163 transform the condition to != comparison. In particular, this will be
1164 the case if DELTA is constant. */
1165 if (number_of_iterations_lt_to_ne (type
, iv0
, iv1
, niter
, &delta
, step
,
1166 exit_must_be_taken
, bnds
))
1170 zps
.base
= build_int_cst (niter_type
, 0);
1172 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1173 zps does not overflow. */
1174 zps
.no_overflow
= true;
1176 return number_of_iterations_ne (type
, &zps
, delta
, niter
, true, bnds
);
1179 /* Make sure that the control iv does not overflow. */
1180 if (!assert_no_overflow_lt (type
, iv0
, iv1
, niter
, step
))
1183 /* We determine the number of iterations as (delta + step - 1) / step. For
1184 this to work, we must know that iv1->base >= iv0->base - step + 1,
1185 otherwise the loop does not roll. */
1186 assert_loop_rolls_lt (type
, iv0
, iv1
, niter
, bnds
);
1188 s
= fold_build2 (MINUS_EXPR
, niter_type
,
1189 step
, build_int_cst (niter_type
, 1));
1190 delta
= fold_build2 (PLUS_EXPR
, niter_type
, delta
, s
);
1191 niter
->niter
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, delta
, step
);
1195 wi::to_mpz (step
, mstep
, UNSIGNED
);
1196 mpz_add (tmp
, bnds
->up
, mstep
);
1197 mpz_sub_ui (tmp
, tmp
, 1);
1198 mpz_fdiv_q (tmp
, tmp
, mstep
);
1199 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, tmp
, false),
1200 TYPE_SIGN (niter_type
));
1207 /* Determines number of iterations of loop whose ending condition
1208 is IV0 <= IV1. TYPE is the type of the iv. The number of
1209 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
1210 we know that this condition must eventually become false (we derived this
1211 earlier, and possibly set NITER->assumptions to make sure this
1212 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1215 number_of_iterations_le (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1216 struct tree_niter_desc
*niter
, bool exit_must_be_taken
,
1221 if (POINTER_TYPE_P (type
))
1224 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1225 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1226 value of the type. This we must know anyway, since if it is
1227 equal to this value, the loop rolls forever. We do not check
1228 this condition for pointer type ivs, as the code cannot rely on
1229 the object to that the pointer points being placed at the end of
1230 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1231 not defined for pointers). */
1233 if (!exit_must_be_taken
&& !POINTER_TYPE_P (type
))
1235 if (integer_nonzerop (iv0
->step
))
1236 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1237 iv1
->base
, TYPE_MAX_VALUE (type
));
1239 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1240 iv0
->base
, TYPE_MIN_VALUE (type
));
1242 if (integer_zerop (assumption
))
1244 if (!integer_nonzerop (assumption
))
1245 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1246 niter
->assumptions
, assumption
);
1249 if (integer_nonzerop (iv0
->step
))
1251 if (POINTER_TYPE_P (type
))
1252 iv1
->base
= fold_build_pointer_plus_hwi (iv1
->base
, 1);
1254 iv1
->base
= fold_build2 (PLUS_EXPR
, type1
, iv1
->base
,
1255 build_int_cst (type1
, 1));
1257 else if (POINTER_TYPE_P (type
))
1258 iv0
->base
= fold_build_pointer_plus_hwi (iv0
->base
, -1);
1260 iv0
->base
= fold_build2 (MINUS_EXPR
, type1
,
1261 iv0
->base
, build_int_cst (type1
, 1));
1263 bounds_add (bnds
, 1, type1
);
1265 return number_of_iterations_lt (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1269 /* Dumps description of affine induction variable IV to FILE. */
1272 dump_affine_iv (FILE *file
, affine_iv
*iv
)
1274 if (!integer_zerop (iv
->step
))
1275 fprintf (file
, "[");
1277 print_generic_expr (dump_file
, iv
->base
, TDF_SLIM
);
1279 if (!integer_zerop (iv
->step
))
1281 fprintf (file
, ", + , ");
1282 print_generic_expr (dump_file
, iv
->step
, TDF_SLIM
);
1283 fprintf (file
, "]%s", iv
->no_overflow
? "(no_overflow)" : "");
1287 /* Determine the number of iterations according to condition (for staying
1288 inside loop) which compares two induction variables using comparison
1289 operator CODE. The induction variable on left side of the comparison
1290 is IV0, the right-hand side is IV1. Both induction variables must have
1291 type TYPE, which must be an integer or pointer type. The steps of the
1292 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1294 LOOP is the loop whose number of iterations we are determining.
1296 ONLY_EXIT is true if we are sure this is the only way the loop could be
1297 exited (including possibly non-returning function calls, exceptions, etc.)
1298 -- in this case we can use the information whether the control induction
1299 variables can overflow or not in a more efficient way.
1301 if EVERY_ITERATION is true, we know the test is executed on every iteration.
1303 The results (number of iterations and assumptions as described in
1304 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
1305 Returns false if it fails to determine number of iterations, true if it
1306 was determined (possibly with some assumptions). */
1309 number_of_iterations_cond (struct loop
*loop
,
1310 tree type
, affine_iv
*iv0
, enum tree_code code
,
1311 affine_iv
*iv1
, struct tree_niter_desc
*niter
,
1312 bool only_exit
, bool every_iteration
)
1314 bool exit_must_be_taken
= false, ret
;
1317 /* If the test is not executed every iteration, wrapping may make the test
1319 TODO: the overflow case can be still used as unreliable estimate of upper
1320 bound. But we have no API to pass it down to number of iterations code
1321 and, at present, it will not use it anyway. */
1322 if (!every_iteration
1323 && (!iv0
->no_overflow
|| !iv1
->no_overflow
1324 || code
== NE_EXPR
|| code
== EQ_EXPR
))
1327 /* The meaning of these assumptions is this:
1329 then the rest of information does not have to be valid
1330 if may_be_zero then the loop does not roll, even if
1332 niter
->assumptions
= boolean_true_node
;
1333 niter
->may_be_zero
= boolean_false_node
;
1334 niter
->niter
= NULL_TREE
;
1336 niter
->bound
= NULL_TREE
;
1337 niter
->cmp
= ERROR_MARK
;
1339 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1340 the control variable is on lhs. */
1341 if (code
== GE_EXPR
|| code
== GT_EXPR
1342 || (code
== NE_EXPR
&& integer_zerop (iv0
->step
)))
1345 code
= swap_tree_comparison (code
);
1348 if (POINTER_TYPE_P (type
))
1350 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1351 to the same object. If they do, the control variable cannot wrap
1352 (as wrap around the bounds of memory will never return a pointer
1353 that would be guaranteed to point to the same object, even if we
1354 avoid undefined behavior by casting to size_t and back). */
1355 iv0
->no_overflow
= true;
1356 iv1
->no_overflow
= true;
1359 /* If the control induction variable does not overflow and the only exit
1360 from the loop is the one that we analyze, we know it must be taken
1364 if (!integer_zerop (iv0
->step
) && iv0
->no_overflow
)
1365 exit_must_be_taken
= true;
1366 else if (!integer_zerop (iv1
->step
) && iv1
->no_overflow
)
1367 exit_must_be_taken
= true;
1370 /* We can handle the case when neither of the sides of the comparison is
1371 invariant, provided that the test is NE_EXPR. This rarely occurs in
1372 practice, but it is simple enough to manage. */
1373 if (!integer_zerop (iv0
->step
) && !integer_zerop (iv1
->step
))
1375 tree step_type
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1376 if (code
!= NE_EXPR
)
1379 iv0
->step
= fold_binary_to_constant (MINUS_EXPR
, step_type
,
1380 iv0
->step
, iv1
->step
);
1381 iv0
->no_overflow
= false;
1382 iv1
->step
= build_int_cst (step_type
, 0);
1383 iv1
->no_overflow
= true;
1386 /* If the result of the comparison is a constant, the loop is weird. More
1387 precise handling would be possible, but the situation is not common enough
1388 to waste time on it. */
1389 if (integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
))
1392 /* Ignore loops of while (i-- < 10) type. */
1393 if (code
!= NE_EXPR
)
1395 if (iv0
->step
&& tree_int_cst_sign_bit (iv0
->step
))
1398 if (!integer_zerop (iv1
->step
) && !tree_int_cst_sign_bit (iv1
->step
))
1402 /* If the loop exits immediately, there is nothing to do. */
1403 tree tem
= fold_binary (code
, boolean_type_node
, iv0
->base
, iv1
->base
);
1404 if (tem
&& integer_zerop (tem
))
1406 niter
->niter
= build_int_cst (unsigned_type_for (type
), 0);
1411 /* OK, now we know we have a senseful loop. Handle several cases, depending
1412 on what comparison operator is used. */
1413 bound_difference (loop
, iv1
->base
, iv0
->base
, &bnds
);
1415 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1418 "Analyzing # of iterations of loop %d\n", loop
->num
);
1420 fprintf (dump_file
, " exit condition ");
1421 dump_affine_iv (dump_file
, iv0
);
1422 fprintf (dump_file
, " %s ",
1423 code
== NE_EXPR
? "!="
1424 : code
== LT_EXPR
? "<"
1426 dump_affine_iv (dump_file
, iv1
);
1427 fprintf (dump_file
, "\n");
1429 fprintf (dump_file
, " bounds on difference of bases: ");
1430 mpz_out_str (dump_file
, 10, bnds
.below
);
1431 fprintf (dump_file
, " ... ");
1432 mpz_out_str (dump_file
, 10, bnds
.up
);
1433 fprintf (dump_file
, "\n");
1439 gcc_assert (integer_zerop (iv1
->step
));
1440 ret
= number_of_iterations_ne (type
, iv0
, iv1
->base
, niter
,
1441 exit_must_be_taken
, &bnds
);
1445 ret
= number_of_iterations_lt (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1450 ret
= number_of_iterations_le (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1458 mpz_clear (bnds
.up
);
1459 mpz_clear (bnds
.below
);
1461 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1465 fprintf (dump_file
, " result:\n");
1466 if (!integer_nonzerop (niter
->assumptions
))
1468 fprintf (dump_file
, " under assumptions ");
1469 print_generic_expr (dump_file
, niter
->assumptions
, TDF_SLIM
);
1470 fprintf (dump_file
, "\n");
1473 if (!integer_zerop (niter
->may_be_zero
))
1475 fprintf (dump_file
, " zero if ");
1476 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
1477 fprintf (dump_file
, "\n");
1480 fprintf (dump_file
, " # of iterations ");
1481 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
1482 fprintf (dump_file
, ", bounded by ");
1483 print_decu (niter
->max
, dump_file
);
1484 fprintf (dump_file
, "\n");
1487 fprintf (dump_file
, " failed\n\n");
1492 /* Substitute NEW for OLD in EXPR and fold the result. */
1495 simplify_replace_tree (tree expr
, tree old
, tree new_tree
)
1498 tree ret
= NULL_TREE
, e
, se
;
1503 /* Do not bother to replace constants. */
1504 if (CONSTANT_CLASS_P (old
))
1508 || operand_equal_p (expr
, old
, 0))
1509 return unshare_expr (new_tree
);
1514 n
= TREE_OPERAND_LENGTH (expr
);
1515 for (i
= 0; i
< n
; i
++)
1517 e
= TREE_OPERAND (expr
, i
);
1518 se
= simplify_replace_tree (e
, old
, new_tree
);
1523 ret
= copy_node (expr
);
1525 TREE_OPERAND (ret
, i
) = se
;
1528 return (ret
? fold (ret
) : expr
);
1531 /* Expand definitions of ssa names in EXPR as long as they are simple
1532 enough, and return the new expression. */
1535 expand_simple_operations (tree expr
)
1538 tree ret
= NULL_TREE
, e
, ee
, e1
;
1539 enum tree_code code
;
1542 if (expr
== NULL_TREE
)
1545 if (is_gimple_min_invariant (expr
))
1548 code
= TREE_CODE (expr
);
1549 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
1551 n
= TREE_OPERAND_LENGTH (expr
);
1552 for (i
= 0; i
< n
; i
++)
1554 e
= TREE_OPERAND (expr
, i
);
1555 ee
= expand_simple_operations (e
);
1560 ret
= copy_node (expr
);
1562 TREE_OPERAND (ret
, i
) = ee
;
1568 fold_defer_overflow_warnings ();
1570 fold_undefer_and_ignore_overflow_warnings ();
1574 if (TREE_CODE (expr
) != SSA_NAME
)
1577 stmt
= SSA_NAME_DEF_STMT (expr
);
1578 if (gimple_code (stmt
) == GIMPLE_PHI
)
1580 basic_block src
, dest
;
1582 if (gimple_phi_num_args (stmt
) != 1)
1584 e
= PHI_ARG_DEF (stmt
, 0);
1586 /* Avoid propagating through loop exit phi nodes, which
1587 could break loop-closed SSA form restrictions. */
1588 dest
= gimple_bb (stmt
);
1589 src
= single_pred (dest
);
1590 if (TREE_CODE (e
) == SSA_NAME
1591 && src
->loop_father
!= dest
->loop_father
)
1594 return expand_simple_operations (e
);
1596 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1599 /* Avoid expanding to expressions that contain SSA names that need
1600 to take part in abnormal coalescing. */
1602 FOR_EACH_SSA_TREE_OPERAND (e
, stmt
, iter
, SSA_OP_USE
)
1603 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (e
))
1606 e
= gimple_assign_rhs1 (stmt
);
1607 code
= gimple_assign_rhs_code (stmt
);
1608 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1610 if (is_gimple_min_invariant (e
))
1613 if (code
== SSA_NAME
)
1614 return expand_simple_operations (e
);
1622 /* Casts are simple. */
1623 ee
= expand_simple_operations (e
);
1624 return fold_build1 (code
, TREE_TYPE (expr
), ee
);
1628 case POINTER_PLUS_EXPR
:
1629 /* And increments and decrements by a constant are simple. */
1630 e1
= gimple_assign_rhs2 (stmt
);
1631 if (!is_gimple_min_invariant (e1
))
1634 ee
= expand_simple_operations (e
);
1635 return fold_build2 (code
, TREE_TYPE (expr
), ee
, e1
);
1642 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1643 expression (or EXPR unchanged, if no simplification was possible). */
1646 tree_simplify_using_condition_1 (tree cond
, tree expr
)
1649 tree e
, te
, e0
, e1
, e2
, notcond
;
1650 enum tree_code code
= TREE_CODE (expr
);
1652 if (code
== INTEGER_CST
)
1655 if (code
== TRUTH_OR_EXPR
1656 || code
== TRUTH_AND_EXPR
1657 || code
== COND_EXPR
)
1661 e0
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 0));
1662 if (TREE_OPERAND (expr
, 0) != e0
)
1665 e1
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 1));
1666 if (TREE_OPERAND (expr
, 1) != e1
)
1669 if (code
== COND_EXPR
)
1671 e2
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 2));
1672 if (TREE_OPERAND (expr
, 2) != e2
)
1680 if (code
== COND_EXPR
)
1681 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1683 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1689 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
1690 propagation, and vice versa. Fold does not handle this, since it is
1691 considered too expensive. */
1692 if (TREE_CODE (cond
) == EQ_EXPR
)
1694 e0
= TREE_OPERAND (cond
, 0);
1695 e1
= TREE_OPERAND (cond
, 1);
1697 /* We know that e0 == e1. Check whether we cannot simplify expr
1699 e
= simplify_replace_tree (expr
, e0
, e1
);
1700 if (integer_zerop (e
) || integer_nonzerop (e
))
1703 e
= simplify_replace_tree (expr
, e1
, e0
);
1704 if (integer_zerop (e
) || integer_nonzerop (e
))
1707 if (TREE_CODE (expr
) == EQ_EXPR
)
1709 e0
= TREE_OPERAND (expr
, 0);
1710 e1
= TREE_OPERAND (expr
, 1);
1712 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
1713 e
= simplify_replace_tree (cond
, e0
, e1
);
1714 if (integer_zerop (e
))
1716 e
= simplify_replace_tree (cond
, e1
, e0
);
1717 if (integer_zerop (e
))
1720 if (TREE_CODE (expr
) == NE_EXPR
)
1722 e0
= TREE_OPERAND (expr
, 0);
1723 e1
= TREE_OPERAND (expr
, 1);
1725 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
1726 e
= simplify_replace_tree (cond
, e0
, e1
);
1727 if (integer_zerop (e
))
1728 return boolean_true_node
;
1729 e
= simplify_replace_tree (cond
, e1
, e0
);
1730 if (integer_zerop (e
))
1731 return boolean_true_node
;
1734 te
= expand_simple_operations (expr
);
1736 /* Check whether COND ==> EXPR. */
1737 notcond
= invert_truthvalue (cond
);
1738 e
= fold_binary (TRUTH_OR_EXPR
, boolean_type_node
, notcond
, te
);
1739 if (e
&& integer_nonzerop (e
))
1742 /* Check whether COND ==> not EXPR. */
1743 e
= fold_binary (TRUTH_AND_EXPR
, boolean_type_node
, cond
, te
);
1744 if (e
&& integer_zerop (e
))
1750 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1751 expression (or EXPR unchanged, if no simplification was possible).
1752 Wrapper around tree_simplify_using_condition_1 that ensures that chains
1753 of simple operations in definitions of ssa names in COND are expanded,
1754 so that things like casts or incrementing the value of the bound before
1755 the loop do not cause us to fail. */
1758 tree_simplify_using_condition (tree cond
, tree expr
)
1760 cond
= expand_simple_operations (cond
);
1762 return tree_simplify_using_condition_1 (cond
, expr
);
1765 /* Tries to simplify EXPR using the conditions on entry to LOOP.
1766 Returns the simplified expression (or EXPR unchanged, if no
1767 simplification was possible).*/
1770 simplify_using_initial_conditions (struct loop
*loop
, tree expr
)
1778 if (TREE_CODE (expr
) == INTEGER_CST
)
1781 /* Limit walking the dominators to avoid quadraticness in
1782 the number of BBs times the number of loops in degenerate
1784 for (bb
= loop
->header
;
1785 bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && cnt
< MAX_DOMINATORS_TO_WALK
;
1786 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1788 if (!single_pred_p (bb
))
1790 e
= single_pred_edge (bb
);
1792 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
1795 stmt
= last_stmt (e
->src
);
1796 cond
= fold_build2 (gimple_cond_code (stmt
),
1798 gimple_cond_lhs (stmt
),
1799 gimple_cond_rhs (stmt
));
1800 if (e
->flags
& EDGE_FALSE_VALUE
)
1801 cond
= invert_truthvalue (cond
);
1802 expr
= tree_simplify_using_condition (cond
, expr
);
1809 /* Tries to simplify EXPR using the evolutions of the loop invariants
1810 in the superloops of LOOP. Returns the simplified expression
1811 (or EXPR unchanged, if no simplification was possible). */
1814 simplify_using_outer_evolutions (struct loop
*loop
, tree expr
)
1816 enum tree_code code
= TREE_CODE (expr
);
1820 if (is_gimple_min_invariant (expr
))
1823 if (code
== TRUTH_OR_EXPR
1824 || code
== TRUTH_AND_EXPR
1825 || code
== COND_EXPR
)
1829 e0
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 0));
1830 if (TREE_OPERAND (expr
, 0) != e0
)
1833 e1
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 1));
1834 if (TREE_OPERAND (expr
, 1) != e1
)
1837 if (code
== COND_EXPR
)
1839 e2
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 2));
1840 if (TREE_OPERAND (expr
, 2) != e2
)
1848 if (code
== COND_EXPR
)
1849 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1851 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1857 e
= instantiate_parameters (loop
, expr
);
1858 if (is_gimple_min_invariant (e
))
1864 /* Returns true if EXIT is the only possible exit from LOOP. */
1867 loop_only_exit_p (const struct loop
*loop
, const_edge exit
)
1870 gimple_stmt_iterator bsi
;
1874 if (exit
!= single_exit (loop
))
1877 body
= get_loop_body (loop
);
1878 for (i
= 0; i
< loop
->num_nodes
; i
++)
1880 for (bsi
= gsi_start_bb (body
[i
]); !gsi_end_p (bsi
); gsi_next (&bsi
))
1882 call
= gsi_stmt (bsi
);
1883 if (gimple_code (call
) != GIMPLE_CALL
)
1886 if (gimple_has_side_effects (call
))
1898 /* Stores description of number of iterations of LOOP derived from
1899 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
1900 useful information could be derived (and fields of NITER has
1901 meaning described in comments at struct tree_niter_desc
1902 declaration), false otherwise. If WARN is true and
1903 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1904 potentially unsafe assumptions.
1905 When EVERY_ITERATION is true, only tests that are known to be executed
1906 every iteration are considered (i.e. only test that alone bounds the loop).
1910 number_of_iterations_exit (struct loop
*loop
, edge exit
,
1911 struct tree_niter_desc
*niter
,
1912 bool warn
, bool every_iteration
)
1917 enum tree_code code
;
1921 safe
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit
->src
);
1923 if (every_iteration
&& !safe
)
1926 niter
->assumptions
= boolean_false_node
;
1927 stmt
= last_stmt (exit
->src
);
1928 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1931 /* We want the condition for staying inside loop. */
1932 code
= gimple_cond_code (stmt
);
1933 if (exit
->flags
& EDGE_TRUE_VALUE
)
1934 code
= invert_tree_comparison (code
, false);
1949 op0
= gimple_cond_lhs (stmt
);
1950 op1
= gimple_cond_rhs (stmt
);
1951 type
= TREE_TYPE (op0
);
1953 if (TREE_CODE (type
) != INTEGER_TYPE
1954 && !POINTER_TYPE_P (type
))
1957 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, false))
1959 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, false))
1962 /* We don't want to see undefined signed overflow warnings while
1963 computing the number of iterations. */
1964 fold_defer_overflow_warnings ();
1966 iv0
.base
= expand_simple_operations (iv0
.base
);
1967 iv1
.base
= expand_simple_operations (iv1
.base
);
1968 if (!number_of_iterations_cond (loop
, type
, &iv0
, code
, &iv1
, niter
,
1969 loop_only_exit_p (loop
, exit
), safe
))
1971 fold_undefer_and_ignore_overflow_warnings ();
1977 niter
->assumptions
= simplify_using_outer_evolutions (loop
,
1978 niter
->assumptions
);
1979 niter
->may_be_zero
= simplify_using_outer_evolutions (loop
,
1980 niter
->may_be_zero
);
1981 niter
->niter
= simplify_using_outer_evolutions (loop
, niter
->niter
);
1985 = simplify_using_initial_conditions (loop
,
1986 niter
->assumptions
);
1988 = simplify_using_initial_conditions (loop
,
1989 niter
->may_be_zero
);
1991 fold_undefer_and_ignore_overflow_warnings ();
1993 /* If NITER has simplified into a constant, update MAX. */
1994 if (TREE_CODE (niter
->niter
) == INTEGER_CST
)
1995 niter
->max
= wi::to_widest (niter
->niter
);
1997 if (integer_onep (niter
->assumptions
))
2000 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
2001 But if we can prove that there is overflow or some other source of weird
2002 behavior, ignore the loop even with -funsafe-loop-optimizations. */
2003 if (integer_zerop (niter
->assumptions
) || !single_exit (loop
))
2006 if (flag_unsafe_loop_optimizations
)
2007 niter
->assumptions
= boolean_true_node
;
2011 const char *wording
;
2012 location_t loc
= gimple_location (stmt
);
2014 /* We can provide a more specific warning if one of the operator is
2015 constant and the other advances by +1 or -1. */
2016 if (!integer_zerop (iv1
.step
)
2017 ? (integer_zerop (iv0
.step
)
2018 && (integer_onep (iv1
.step
) || integer_all_onesp (iv1
.step
)))
2019 : (integer_onep (iv0
.step
) || integer_all_onesp (iv0
.step
)))
2021 flag_unsafe_loop_optimizations
2022 ? N_("assuming that the loop is not infinite")
2023 : N_("cannot optimize possibly infinite loops");
2026 flag_unsafe_loop_optimizations
2027 ? N_("assuming that the loop counter does not overflow")
2028 : N_("cannot optimize loop, the loop counter may overflow");
2030 warning_at ((LOCATION_LINE (loc
) > 0) ? loc
: input_location
,
2031 OPT_Wunsafe_loop_optimizations
, "%s", gettext (wording
));
2034 return flag_unsafe_loop_optimizations
;
2037 /* Try to determine the number of iterations of LOOP. If we succeed,
2038 expression giving number of iterations is returned and *EXIT is
2039 set to the edge from that the information is obtained. Otherwise
2040 chrec_dont_know is returned. */
2043 find_loop_niter (struct loop
*loop
, edge
*exit
)
2046 vec
<edge
> exits
= get_loop_exit_edges (loop
);
2048 tree niter
= NULL_TREE
, aniter
;
2049 struct tree_niter_desc desc
;
2052 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2054 if (!number_of_iterations_exit (loop
, ex
, &desc
, false))
2057 if (integer_nonzerop (desc
.may_be_zero
))
2059 /* We exit in the first iteration through this exit.
2060 We won't find anything better. */
2061 niter
= build_int_cst (unsigned_type_node
, 0);
2066 if (!integer_zerop (desc
.may_be_zero
))
2069 aniter
= desc
.niter
;
2073 /* Nothing recorded yet. */
2079 /* Prefer constants, the lower the better. */
2080 if (TREE_CODE (aniter
) != INTEGER_CST
)
2083 if (TREE_CODE (niter
) != INTEGER_CST
)
2090 if (tree_int_cst_lt (aniter
, niter
))
2099 return niter
? niter
: chrec_dont_know
;
2102 /* Return true if loop is known to have bounded number of iterations. */
2105 finite_loop_p (struct loop
*loop
)
2110 if (flag_unsafe_loop_optimizations
)
2112 flags
= flags_from_decl_or_type (current_function_decl
);
2113 if ((flags
& (ECF_CONST
|ECF_PURE
)) && !(flags
& ECF_LOOPING_CONST_OR_PURE
))
2115 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2116 fprintf (dump_file
, "Found loop %i to be finite: it is within pure or const function.\n",
2121 if (loop
->any_upper_bound
2122 || max_loop_iterations (loop
, &nit
))
2124 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2125 fprintf (dump_file
, "Found loop %i to be finite: upper bound found.\n",
2134 Analysis of a number of iterations of a loop by a brute-force evaluation.
2138 /* Bound on the number of iterations we try to evaluate. */
2140 #define MAX_ITERATIONS_TO_TRACK \
2141 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
2143 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
2144 result by a chain of operations such that all but exactly one of their
2145 operands are constants. */
2148 chain_of_csts_start (struct loop
*loop
, tree x
)
2150 gimple stmt
= SSA_NAME_DEF_STMT (x
);
2152 basic_block bb
= gimple_bb (stmt
);
2153 enum tree_code code
;
2156 || !flow_bb_inside_loop_p (loop
, bb
))
2159 if (gimple_code (stmt
) == GIMPLE_PHI
)
2161 if (bb
== loop
->header
)
2167 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2168 || gimple_assign_rhs_class (stmt
) == GIMPLE_TERNARY_RHS
)
2171 code
= gimple_assign_rhs_code (stmt
);
2172 if (gimple_references_memory_p (stmt
)
2173 || TREE_CODE_CLASS (code
) == tcc_reference
2174 || (code
== ADDR_EXPR
2175 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
2178 use
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
2179 if (use
== NULL_TREE
)
2182 return chain_of_csts_start (loop
, use
);
2185 /* Determines whether the expression X is derived from a result of a phi node
2186 in header of LOOP such that
2188 * the derivation of X consists only from operations with constants
2189 * the initial value of the phi node is constant
2190 * the value of the phi node in the next iteration can be derived from the
2191 value in the current iteration by a chain of operations with constants.
2193 If such phi node exists, it is returned, otherwise NULL is returned. */
2196 get_base_for (struct loop
*loop
, tree x
)
2201 if (is_gimple_min_invariant (x
))
2204 phi
= chain_of_csts_start (loop
, x
);
2208 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2209 next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2211 if (TREE_CODE (next
) != SSA_NAME
)
2214 if (!is_gimple_min_invariant (init
))
2217 if (chain_of_csts_start (loop
, next
) != phi
)
2223 /* Given an expression X, then
2225 * if X is NULL_TREE, we return the constant BASE.
2226 * otherwise X is a SSA name, whose value in the considered loop is derived
2227 by a chain of operations with constant from a result of a phi node in
2228 the header of the loop. Then we return value of X when the value of the
2229 result of this phi node is given by the constant BASE. */
2232 get_val_for (tree x
, tree base
)
2236 gcc_checking_assert (is_gimple_min_invariant (base
));
2241 stmt
= SSA_NAME_DEF_STMT (x
);
2242 if (gimple_code (stmt
) == GIMPLE_PHI
)
2245 gcc_checking_assert (is_gimple_assign (stmt
));
2247 /* STMT must be either an assignment of a single SSA name or an
2248 expression involving an SSA name and a constant. Try to fold that
2249 expression using the value for the SSA name. */
2250 if (gimple_assign_ssa_name_copy_p (stmt
))
2251 return get_val_for (gimple_assign_rhs1 (stmt
), base
);
2252 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_UNARY_RHS
2253 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
2255 return fold_build1 (gimple_assign_rhs_code (stmt
),
2256 gimple_expr_type (stmt
),
2257 get_val_for (gimple_assign_rhs1 (stmt
), base
));
2259 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_BINARY_RHS
)
2261 tree rhs1
= gimple_assign_rhs1 (stmt
);
2262 tree rhs2
= gimple_assign_rhs2 (stmt
);
2263 if (TREE_CODE (rhs1
) == SSA_NAME
)
2264 rhs1
= get_val_for (rhs1
, base
);
2265 else if (TREE_CODE (rhs2
) == SSA_NAME
)
2266 rhs2
= get_val_for (rhs2
, base
);
2269 return fold_build2 (gimple_assign_rhs_code (stmt
),
2270 gimple_expr_type (stmt
), rhs1
, rhs2
);
2277 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2278 by brute force -- i.e. by determining the value of the operands of the
2279 condition at EXIT in first few iterations of the loop (assuming that
2280 these values are constant) and determining the first one in that the
2281 condition is not satisfied. Returns the constant giving the number
2282 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
2285 loop_niter_by_eval (struct loop
*loop
, edge exit
)
2288 tree op
[2], val
[2], next
[2], aval
[2];
2293 cond
= last_stmt (exit
->src
);
2294 if (!cond
|| gimple_code (cond
) != GIMPLE_COND
)
2295 return chrec_dont_know
;
2297 cmp
= gimple_cond_code (cond
);
2298 if (exit
->flags
& EDGE_TRUE_VALUE
)
2299 cmp
= invert_tree_comparison (cmp
, false);
2309 op
[0] = gimple_cond_lhs (cond
);
2310 op
[1] = gimple_cond_rhs (cond
);
2314 return chrec_dont_know
;
2317 for (j
= 0; j
< 2; j
++)
2319 if (is_gimple_min_invariant (op
[j
]))
2322 next
[j
] = NULL_TREE
;
2327 phi
= get_base_for (loop
, op
[j
]);
2329 return chrec_dont_know
;
2330 val
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2331 next
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2335 /* Don't issue signed overflow warnings. */
2336 fold_defer_overflow_warnings ();
2338 for (i
= 0; i
< MAX_ITERATIONS_TO_TRACK
; i
++)
2340 for (j
= 0; j
< 2; j
++)
2341 aval
[j
] = get_val_for (op
[j
], val
[j
]);
2343 acnd
= fold_binary (cmp
, boolean_type_node
, aval
[0], aval
[1]);
2344 if (acnd
&& integer_zerop (acnd
))
2346 fold_undefer_and_ignore_overflow_warnings ();
2347 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2349 "Proved that loop %d iterates %d times using brute force.\n",
2351 return build_int_cst (unsigned_type_node
, i
);
2354 for (j
= 0; j
< 2; j
++)
2356 val
[j
] = get_val_for (next
[j
], val
[j
]);
2357 if (!is_gimple_min_invariant (val
[j
]))
2359 fold_undefer_and_ignore_overflow_warnings ();
2360 return chrec_dont_know
;
2365 fold_undefer_and_ignore_overflow_warnings ();
2367 return chrec_dont_know
;
2370 /* Finds the exit of the LOOP by that the loop exits after a constant
2371 number of iterations and stores the exit edge to *EXIT. The constant
2372 giving the number of iterations of LOOP is returned. The number of
2373 iterations is determined using loop_niter_by_eval (i.e. by brute force
2374 evaluation). If we are unable to find the exit for that loop_niter_by_eval
2375 determines the number of iterations, chrec_dont_know is returned. */
2378 find_loop_niter_by_eval (struct loop
*loop
, edge
*exit
)
2381 vec
<edge
> exits
= get_loop_exit_edges (loop
);
2383 tree niter
= NULL_TREE
, aniter
;
2387 /* Loops with multiple exits are expensive to handle and less important. */
2388 if (!flag_expensive_optimizations
2389 && exits
.length () > 1)
2392 return chrec_dont_know
;
2395 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2397 if (!just_once_each_iteration_p (loop
, ex
->src
))
2400 aniter
= loop_niter_by_eval (loop
, ex
);
2401 if (chrec_contains_undetermined (aniter
))
2405 && !tree_int_cst_lt (aniter
, niter
))
2413 return niter
? niter
: chrec_dont_know
;
2418 Analysis of upper bounds on number of iterations of a loop.
2422 static widest_int
derive_constant_upper_bound_ops (tree
, tree
,
2423 enum tree_code
, tree
);
2425 /* Returns a constant upper bound on the value of the right-hand side of
2426 an assignment statement STMT. */
2429 derive_constant_upper_bound_assign (gimple stmt
)
2431 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2432 tree op0
= gimple_assign_rhs1 (stmt
);
2433 tree op1
= gimple_assign_rhs2 (stmt
);
2435 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt
)),
2439 /* Returns a constant upper bound on the value of expression VAL. VAL
2440 is considered to be unsigned. If its type is signed, its value must
2444 derive_constant_upper_bound (tree val
)
2446 enum tree_code code
;
2449 extract_ops_from_tree (val
, &code
, &op0
, &op1
);
2450 return derive_constant_upper_bound_ops (TREE_TYPE (val
), op0
, code
, op1
);
2453 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
2454 whose type is TYPE. The expression is considered to be unsigned. If
2455 its type is signed, its value must be nonnegative. */
2458 derive_constant_upper_bound_ops (tree type
, tree op0
,
2459 enum tree_code code
, tree op1
)
2462 widest_int bnd
, max
, mmax
, cst
;
2465 if (INTEGRAL_TYPE_P (type
))
2466 maxt
= TYPE_MAX_VALUE (type
);
2468 maxt
= upper_bound_in_type (type
, type
);
2470 max
= wi::to_widest (maxt
);
2475 return wi::to_widest (op0
);
2478 subtype
= TREE_TYPE (op0
);
2479 if (!TYPE_UNSIGNED (subtype
)
2480 /* If TYPE is also signed, the fact that VAL is nonnegative implies
2481 that OP0 is nonnegative. */
2482 && TYPE_UNSIGNED (type
)
2483 && !tree_expr_nonnegative_p (op0
))
2485 /* If we cannot prove that the casted expression is nonnegative,
2486 we cannot establish more useful upper bound than the precision
2487 of the type gives us. */
2491 /* We now know that op0 is an nonnegative value. Try deriving an upper
2493 bnd
= derive_constant_upper_bound (op0
);
2495 /* If the bound does not fit in TYPE, max. value of TYPE could be
2497 if (wi::ltu_p (max
, bnd
))
2503 case POINTER_PLUS_EXPR
:
2505 if (TREE_CODE (op1
) != INTEGER_CST
2506 || !tree_expr_nonnegative_p (op0
))
2509 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
2510 choose the most logical way how to treat this constant regardless
2511 of the signedness of the type. */
2512 cst
= wi::sext (wi::to_widest (op1
), TYPE_PRECISION (type
));
2513 if (code
!= MINUS_EXPR
)
2516 bnd
= derive_constant_upper_bound (op0
);
2518 if (wi::neg_p (cst
))
2521 /* Avoid CST == 0x80000... */
2522 if (wi::neg_p (cst
))
2525 /* OP0 + CST. We need to check that
2526 BND <= MAX (type) - CST. */
2529 if (wi::ltu_p (bnd
, max
))
2536 /* OP0 - CST, where CST >= 0.
2538 If TYPE is signed, we have already verified that OP0 >= 0, and we
2539 know that the result is nonnegative. This implies that
2542 If TYPE is unsigned, we must additionally know that OP0 >= CST,
2543 otherwise the operation underflows.
2546 /* This should only happen if the type is unsigned; however, for
2547 buggy programs that use overflowing signed arithmetics even with
2548 -fno-wrapv, this condition may also be true for signed values. */
2549 if (wi::ltu_p (bnd
, cst
))
2552 if (TYPE_UNSIGNED (type
))
2554 tree tem
= fold_binary (GE_EXPR
, boolean_type_node
, op0
,
2555 wide_int_to_tree (type
, cst
));
2556 if (!tem
|| integer_nonzerop (tem
))
2565 case FLOOR_DIV_EXPR
:
2566 case EXACT_DIV_EXPR
:
2567 if (TREE_CODE (op1
) != INTEGER_CST
2568 || tree_int_cst_sign_bit (op1
))
2571 bnd
= derive_constant_upper_bound (op0
);
2572 return wi::udiv_floor (bnd
, wi::to_widest (op1
));
2575 if (TREE_CODE (op1
) != INTEGER_CST
2576 || tree_int_cst_sign_bit (op1
))
2578 return wi::to_widest (op1
);
2581 stmt
= SSA_NAME_DEF_STMT (op0
);
2582 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2583 || gimple_assign_lhs (stmt
) != op0
)
2585 return derive_constant_upper_bound_assign (stmt
);
2592 /* Emit a -Waggressive-loop-optimizations warning if needed. */
2595 do_warn_aggressive_loop_optimizations (struct loop
*loop
,
2596 widest_int i_bound
, gimple stmt
)
2598 /* Don't warn if the loop doesn't have known constant bound. */
2599 if (!loop
->nb_iterations
2600 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
2601 || !warn_aggressive_loop_optimizations
2602 /* To avoid warning multiple times for the same loop,
2603 only start warning when we preserve loops. */
2604 || (cfun
->curr_properties
& PROP_loops
) == 0
2605 /* Only warn once per loop. */
2606 || loop
->warned_aggressive_loop_optimizations
2607 /* Only warn if undefined behavior gives us lower estimate than the
2608 known constant bound. */
2609 || wi::cmpu (i_bound
, wi::to_widest (loop
->nb_iterations
)) >= 0
2610 /* And undefined behavior happens unconditionally. */
2611 || !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (stmt
)))
2614 edge e
= single_exit (loop
);
2618 gimple estmt
= last_stmt (e
->src
);
2619 if (warning_at (gimple_location (stmt
), OPT_Waggressive_loop_optimizations
,
2620 "iteration %E invokes undefined behavior",
2621 wide_int_to_tree (TREE_TYPE (loop
->nb_iterations
),
2623 inform (gimple_location (estmt
), "containing loop");
2624 loop
->warned_aggressive_loop_optimizations
= true;
2627 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
2628 is true if the loop is exited immediately after STMT, and this exit
2629 is taken at last when the STMT is executed BOUND + 1 times.
2630 REALISTIC is true if BOUND is expected to be close to the real number
2631 of iterations. UPPER is true if we are sure the loop iterates at most
2632 BOUND times. I_BOUND is a widest_int upper estimate on BOUND. */
2635 record_estimate (struct loop
*loop
, tree bound
, const widest_int
&i_bound
,
2636 gimple at_stmt
, bool is_exit
, bool realistic
, bool upper
)
2640 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2642 fprintf (dump_file
, "Statement %s", is_exit
? "(exit)" : "");
2643 print_gimple_stmt (dump_file
, at_stmt
, 0, TDF_SLIM
);
2644 fprintf (dump_file
, " is %sexecuted at most ",
2645 upper
? "" : "probably ");
2646 print_generic_expr (dump_file
, bound
, TDF_SLIM
);
2647 fprintf (dump_file
, " (bounded by ");
2648 print_decu (i_bound
, dump_file
);
2649 fprintf (dump_file
, ") + 1 times in loop %d.\n", loop
->num
);
2652 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
2653 real number of iterations. */
2654 if (TREE_CODE (bound
) != INTEGER_CST
)
2657 gcc_checking_assert (i_bound
== wi::to_widest (bound
));
2658 if (!upper
&& !realistic
)
2661 /* If we have a guaranteed upper bound, record it in the appropriate
2662 list, unless this is an !is_exit bound (i.e. undefined behavior in
2663 at_stmt) in a loop with known constant number of iterations. */
2666 || loop
->nb_iterations
== NULL_TREE
2667 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
))
2669 struct nb_iter_bound
*elt
= ggc_alloc_nb_iter_bound ();
2671 elt
->bound
= i_bound
;
2672 elt
->stmt
= at_stmt
;
2673 elt
->is_exit
= is_exit
;
2674 elt
->next
= loop
->bounds
;
2678 /* If statement is executed on every path to the loop latch, we can directly
2679 infer the upper bound on the # of iterations of the loop. */
2680 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (at_stmt
)))
2683 /* Update the number of iteration estimates according to the bound.
2684 If at_stmt is an exit then the loop latch is executed at most BOUND times,
2685 otherwise it can be executed BOUND + 1 times. We will lower the estimate
2686 later if such statement must be executed on last iteration */
2691 widest_int new_i_bound
= i_bound
+ delta
;
2693 /* If an overflow occurred, ignore the result. */
2694 if (wi::ltu_p (new_i_bound
, delta
))
2697 if (upper
&& !is_exit
)
2698 do_warn_aggressive_loop_optimizations (loop
, new_i_bound
, at_stmt
);
2699 record_niter_bound (loop
, new_i_bound
, realistic
, upper
);
2702 /* Record the estimate on number of iterations of LOOP based on the fact that
2703 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
2704 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
2705 estimated number of iterations is expected to be close to the real one.
2706 UPPER is true if we are sure the induction variable does not wrap. */
2709 record_nonwrapping_iv (struct loop
*loop
, tree base
, tree step
, gimple stmt
,
2710 tree low
, tree high
, bool realistic
, bool upper
)
2712 tree niter_bound
, extreme
, delta
;
2713 tree type
= TREE_TYPE (base
), unsigned_type
;
2715 if (TREE_CODE (step
) != INTEGER_CST
|| integer_zerop (step
))
2718 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2720 fprintf (dump_file
, "Induction variable (");
2721 print_generic_expr (dump_file
, TREE_TYPE (base
), TDF_SLIM
);
2722 fprintf (dump_file
, ") ");
2723 print_generic_expr (dump_file
, base
, TDF_SLIM
);
2724 fprintf (dump_file
, " + ");
2725 print_generic_expr (dump_file
, step
, TDF_SLIM
);
2726 fprintf (dump_file
, " * iteration does not wrap in statement ");
2727 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2728 fprintf (dump_file
, " in loop %d.\n", loop
->num
);
2731 unsigned_type
= unsigned_type_for (type
);
2732 base
= fold_convert (unsigned_type
, base
);
2733 step
= fold_convert (unsigned_type
, step
);
2735 if (tree_int_cst_sign_bit (step
))
2737 extreme
= fold_convert (unsigned_type
, low
);
2738 if (TREE_CODE (base
) != INTEGER_CST
)
2739 base
= fold_convert (unsigned_type
, high
);
2740 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
2741 step
= fold_build1 (NEGATE_EXPR
, unsigned_type
, step
);
2745 extreme
= fold_convert (unsigned_type
, high
);
2746 if (TREE_CODE (base
) != INTEGER_CST
)
2747 base
= fold_convert (unsigned_type
, low
);
2748 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
2751 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
2752 would get out of the range. */
2753 niter_bound
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step
);
2754 widest_int max
= derive_constant_upper_bound (niter_bound
);
2755 record_estimate (loop
, niter_bound
, max
, stmt
, false, realistic
, upper
);
2758 /* Determine information about number of iterations a LOOP from the index
2759 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
2760 guaranteed to be executed in every iteration of LOOP. Callback for
2770 idx_infer_loop_bounds (tree base
, tree
*idx
, void *dta
)
2772 struct ilb_data
*data
= (struct ilb_data
*) dta
;
2773 tree ev
, init
, step
;
2774 tree low
, high
, type
, next
;
2775 bool sign
, upper
= true, at_end
= false;
2776 struct loop
*loop
= data
->loop
;
2777 bool reliable
= true;
2779 if (TREE_CODE (base
) != ARRAY_REF
)
2782 /* For arrays at the end of the structure, we are not guaranteed that they
2783 do not really extend over their declared size. However, for arrays of
2784 size greater than one, this is unlikely to be intended. */
2785 if (array_at_struct_end_p (base
))
2791 struct loop
*dloop
= loop_containing_stmt (data
->stmt
);
2795 ev
= analyze_scalar_evolution (dloop
, *idx
);
2796 ev
= instantiate_parameters (loop
, ev
);
2797 init
= initial_condition (ev
);
2798 step
= evolution_part_in_loop_num (ev
, loop
->num
);
2802 || TREE_CODE (step
) != INTEGER_CST
2803 || integer_zerop (step
)
2804 || tree_contains_chrecs (init
, NULL
)
2805 || chrec_contains_symbols_defined_in_loop (init
, loop
->num
))
2808 low
= array_ref_low_bound (base
);
2809 high
= array_ref_up_bound (base
);
2811 /* The case of nonconstant bounds could be handled, but it would be
2813 if (TREE_CODE (low
) != INTEGER_CST
2815 || TREE_CODE (high
) != INTEGER_CST
)
2817 sign
= tree_int_cst_sign_bit (step
);
2818 type
= TREE_TYPE (step
);
2820 /* The array of length 1 at the end of a structure most likely extends
2821 beyond its bounds. */
2823 && operand_equal_p (low
, high
, 0))
2826 /* In case the relevant bound of the array does not fit in type, or
2827 it does, but bound + step (in type) still belongs into the range of the
2828 array, the index may wrap and still stay within the range of the array
2829 (consider e.g. if the array is indexed by the full range of
2832 To make things simpler, we require both bounds to fit into type, although
2833 there are cases where this would not be strictly necessary. */
2834 if (!int_fits_type_p (high
, type
)
2835 || !int_fits_type_p (low
, type
))
2837 low
= fold_convert (type
, low
);
2838 high
= fold_convert (type
, high
);
2841 next
= fold_binary (PLUS_EXPR
, type
, low
, step
);
2843 next
= fold_binary (PLUS_EXPR
, type
, high
, step
);
2845 if (tree_int_cst_compare (low
, next
) <= 0
2846 && tree_int_cst_compare (next
, high
) <= 0)
2849 /* If access is not executed on every iteration, we must ensure that overlow may
2850 not make the access valid later. */
2851 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (data
->stmt
))
2852 && scev_probably_wraps_p (initial_condition_in_loop_num (ev
, loop
->num
),
2853 step
, data
->stmt
, loop
, true))
2856 record_nonwrapping_iv (loop
, init
, step
, data
->stmt
, low
, high
, reliable
, upper
);
2860 /* Determine information about number of iterations a LOOP from the bounds
2861 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
2862 STMT is guaranteed to be executed in every iteration of LOOP.*/
2865 infer_loop_bounds_from_ref (struct loop
*loop
, gimple stmt
, tree ref
)
2867 struct ilb_data data
;
2871 for_each_index (&ref
, idx_infer_loop_bounds
, &data
);
2874 /* Determine information about number of iterations of a LOOP from the way
2875 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
2876 executed in every iteration of LOOP. */
2879 infer_loop_bounds_from_array (struct loop
*loop
, gimple stmt
)
2881 if (is_gimple_assign (stmt
))
2883 tree op0
= gimple_assign_lhs (stmt
);
2884 tree op1
= gimple_assign_rhs1 (stmt
);
2886 /* For each memory access, analyze its access function
2887 and record a bound on the loop iteration domain. */
2888 if (REFERENCE_CLASS_P (op0
))
2889 infer_loop_bounds_from_ref (loop
, stmt
, op0
);
2891 if (REFERENCE_CLASS_P (op1
))
2892 infer_loop_bounds_from_ref (loop
, stmt
, op1
);
2894 else if (is_gimple_call (stmt
))
2897 unsigned i
, n
= gimple_call_num_args (stmt
);
2899 lhs
= gimple_call_lhs (stmt
);
2900 if (lhs
&& REFERENCE_CLASS_P (lhs
))
2901 infer_loop_bounds_from_ref (loop
, stmt
, lhs
);
2903 for (i
= 0; i
< n
; i
++)
2905 arg
= gimple_call_arg (stmt
, i
);
2906 if (REFERENCE_CLASS_P (arg
))
2907 infer_loop_bounds_from_ref (loop
, stmt
, arg
);
2912 /* Determine information about number of iterations of a LOOP from the fact
2913 that pointer arithmetics in STMT does not overflow. */
2916 infer_loop_bounds_from_pointer_arith (struct loop
*loop
, gimple stmt
)
2918 tree def
, base
, step
, scev
, type
, low
, high
;
2921 if (!is_gimple_assign (stmt
)
2922 || gimple_assign_rhs_code (stmt
) != POINTER_PLUS_EXPR
)
2925 def
= gimple_assign_lhs (stmt
);
2926 if (TREE_CODE (def
) != SSA_NAME
)
2929 type
= TREE_TYPE (def
);
2930 if (!nowrap_type_p (type
))
2933 ptr
= gimple_assign_rhs1 (stmt
);
2934 if (!expr_invariant_in_loop_p (loop
, ptr
))
2937 var
= gimple_assign_rhs2 (stmt
);
2938 if (TYPE_PRECISION (type
) != TYPE_PRECISION (TREE_TYPE (var
)))
2941 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
2942 if (chrec_contains_undetermined (scev
))
2945 base
= initial_condition_in_loop_num (scev
, loop
->num
);
2946 step
= evolution_part_in_loop_num (scev
, loop
->num
);
2949 || TREE_CODE (step
) != INTEGER_CST
2950 || tree_contains_chrecs (base
, NULL
)
2951 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
2954 low
= lower_bound_in_type (type
, type
);
2955 high
= upper_bound_in_type (type
, type
);
2957 /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
2958 produce a NULL pointer. The contrary would mean NULL points to an object,
2959 while NULL is supposed to compare unequal with the address of all objects.
2960 Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
2961 NULL pointer since that would mean wrapping, which we assume here not to
2962 happen. So, we can exclude NULL from the valid range of pointer
2964 if (flag_delete_null_pointer_checks
&& int_cst_value (low
) == 0)
2965 low
= build_int_cstu (TREE_TYPE (low
), TYPE_ALIGN_UNIT (TREE_TYPE (type
)));
2967 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
2970 /* Determine information about number of iterations of a LOOP from the fact
2971 that signed arithmetics in STMT does not overflow. */
2974 infer_loop_bounds_from_signedness (struct loop
*loop
, gimple stmt
)
2976 tree def
, base
, step
, scev
, type
, low
, high
;
2978 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2981 def
= gimple_assign_lhs (stmt
);
2983 if (TREE_CODE (def
) != SSA_NAME
)
2986 type
= TREE_TYPE (def
);
2987 if (!INTEGRAL_TYPE_P (type
)
2988 || !TYPE_OVERFLOW_UNDEFINED (type
))
2991 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
2992 if (chrec_contains_undetermined (scev
))
2995 base
= initial_condition_in_loop_num (scev
, loop
->num
);
2996 step
= evolution_part_in_loop_num (scev
, loop
->num
);
2999 || TREE_CODE (step
) != INTEGER_CST
3000 || tree_contains_chrecs (base
, NULL
)
3001 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
3004 low
= lower_bound_in_type (type
, type
);
3005 high
= upper_bound_in_type (type
, type
);
3007 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
3010 /* The following analyzers are extracting informations on the bounds
3011 of LOOP from the following undefined behaviors:
3013 - data references should not access elements over the statically
3016 - signed variables should not overflow when flag_wrapv is not set.
3020 infer_loop_bounds_from_undefined (struct loop
*loop
)
3024 gimple_stmt_iterator bsi
;
3028 bbs
= get_loop_body (loop
);
3030 for (i
= 0; i
< loop
->num_nodes
; i
++)
3034 /* If BB is not executed in each iteration of the loop, we cannot
3035 use the operations in it to infer reliable upper bound on the
3036 # of iterations of the loop. However, we can use it as a guess.
3037 Reliable guesses come only from array bounds. */
3038 reliable
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
);
3040 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
3042 gimple stmt
= gsi_stmt (bsi
);
3044 infer_loop_bounds_from_array (loop
, stmt
);
3048 infer_loop_bounds_from_signedness (loop
, stmt
);
3049 infer_loop_bounds_from_pointer_arith (loop
, stmt
);
3058 /* Compare wide ints, callback for qsort. */
3061 wide_int_cmp (const void *p1
, const void *p2
)
3063 const widest_int
*d1
= (const widest_int
*) p1
;
3064 const widest_int
*d2
= (const widest_int
*) p2
;
3065 return wi::cmpu (*d1
, *d2
);
3068 /* Return index of BOUND in BOUNDS array sorted in increasing order.
3069 Lookup by binary search. */
3072 bound_index (vec
<widest_int
> bounds
, const widest_int
&bound
)
3074 unsigned int end
= bounds
.length ();
3075 unsigned int begin
= 0;
3077 /* Find a matching index by means of a binary search. */
3078 while (begin
!= end
)
3080 unsigned int middle
= (begin
+ end
) / 2;
3081 widest_int index
= bounds
[middle
];
3085 else if (wi::ltu_p (index
, bound
))
3093 /* We recorded loop bounds only for statements dominating loop latch (and thus
3094 executed each loop iteration). If there are any bounds on statements not
3095 dominating the loop latch we can improve the estimate by walking the loop
3096 body and seeing if every path from loop header to loop latch contains
3097 some bounded statement. */
3100 discover_iteration_bound_by_body_walk (struct loop
*loop
)
3102 pointer_map_t
*bb_bounds
;
3103 struct nb_iter_bound
*elt
;
3104 vec
<widest_int
> bounds
= vNULL
;
3105 vec
<vec
<basic_block
> > queues
= vNULL
;
3106 vec
<basic_block
> queue
= vNULL
;
3107 ptrdiff_t queue_index
;
3108 ptrdiff_t latch_index
= 0;
3109 pointer_map_t
*block_priority
;
3111 /* Discover what bounds may interest us. */
3112 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3114 widest_int bound
= elt
->bound
;
3116 /* Exit terminates loop at given iteration, while non-exits produce undefined
3117 effect on the next iteration. */
3121 /* If an overflow occurred, ignore the result. */
3126 if (!loop
->any_upper_bound
3127 || wi::ltu_p (bound
, loop
->nb_iterations_upper_bound
))
3128 bounds
.safe_push (bound
);
3131 /* Exit early if there is nothing to do. */
3132 if (!bounds
.exists ())
3135 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3136 fprintf (dump_file
, " Trying to walk loop body to reduce the bound.\n");
3138 /* Sort the bounds in decreasing order. */
3139 qsort (bounds
.address (), bounds
.length (),
3140 sizeof (widest_int
), wide_int_cmp
);
3142 /* For every basic block record the lowest bound that is guaranteed to
3143 terminate the loop. */
3145 bb_bounds
= pointer_map_create ();
3146 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3148 widest_int bound
= elt
->bound
;
3152 /* If an overflow occurred, ignore the result. */
3157 if (!loop
->any_upper_bound
3158 || wi::ltu_p (bound
, loop
->nb_iterations_upper_bound
))
3160 ptrdiff_t index
= bound_index (bounds
, bound
);
3161 void **entry
= pointer_map_contains (bb_bounds
,
3162 gimple_bb (elt
->stmt
));
3164 *pointer_map_insert (bb_bounds
,
3165 gimple_bb (elt
->stmt
)) = (void *)index
;
3166 else if ((ptrdiff_t)*entry
> index
)
3167 *entry
= (void *)index
;
3171 block_priority
= pointer_map_create ();
3173 /* Perform shortest path discovery loop->header ... loop->latch.
3175 The "distance" is given by the smallest loop bound of basic block
3176 present in the path and we look for path with largest smallest bound
3179 To avoid the need for fibonacci heap on double ints we simply compress
3180 double ints into indexes to BOUNDS array and then represent the queue
3181 as arrays of queues for every index.
3182 Index of BOUNDS.length() means that the execution of given BB has
3183 no bounds determined.
3185 VISITED is a pointer map translating basic block into smallest index
3186 it was inserted into the priority queue with. */
3189 /* Start walk in loop header with index set to infinite bound. */
3190 queue_index
= bounds
.length ();
3191 queues
.safe_grow_cleared (queue_index
+ 1);
3192 queue
.safe_push (loop
->header
);
3193 queues
[queue_index
] = queue
;
3194 *pointer_map_insert (block_priority
, loop
->header
) = (void *)queue_index
;
3196 for (; queue_index
>= 0; queue_index
--)
3198 if (latch_index
< queue_index
)
3200 while (queues
[queue_index
].length ())
3203 ptrdiff_t bound_index
= queue_index
;
3208 queue
= queues
[queue_index
];
3211 /* OK, we later inserted the BB with lower priority, skip it. */
3212 if ((ptrdiff_t)*pointer_map_contains (block_priority
, bb
) > queue_index
)
3215 /* See if we can improve the bound. */
3216 entry
= pointer_map_contains (bb_bounds
, bb
);
3217 if (entry
&& (ptrdiff_t)*entry
< bound_index
)
3218 bound_index
= (ptrdiff_t)*entry
;
3220 /* Insert succesors into the queue, watch for latch edge
3221 and record greatest index we saw. */
3222 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3224 bool insert
= false;
3227 if (loop_exit_edge_p (loop
, e
))
3230 if (e
== loop_latch_edge (loop
)
3231 && latch_index
< bound_index
)
3232 latch_index
= bound_index
;
3233 else if (!(entry
= pointer_map_contains (block_priority
, e
->dest
)))
3236 *pointer_map_insert (block_priority
, e
->dest
) = (void *)bound_index
;
3238 else if ((ptrdiff_t)*entry
< bound_index
)
3241 *entry
= (void *)bound_index
;
3245 queues
[bound_index
].safe_push (e
->dest
);
3249 queues
[queue_index
].release ();
3252 gcc_assert (latch_index
>= 0);
3253 if ((unsigned)latch_index
< bounds
.length ())
3255 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3257 fprintf (dump_file
, "Found better loop bound ");
3258 print_decu (bounds
[latch_index
], dump_file
);
3259 fprintf (dump_file
, "\n");
3261 record_niter_bound (loop
, bounds
[latch_index
], false, true);
3266 pointer_map_destroy (bb_bounds
);
3267 pointer_map_destroy (block_priority
);
3270 /* See if every path cross the loop goes through a statement that is known
3271 to not execute at the last iteration. In that case we can decrese iteration
3275 maybe_lower_iteration_bound (struct loop
*loop
)
3277 pointer_set_t
*not_executed_last_iteration
= NULL
;
3278 struct nb_iter_bound
*elt
;
3279 bool found_exit
= false;
3280 vec
<basic_block
> queue
= vNULL
;
3283 /* Collect all statements with interesting (i.e. lower than
3284 nb_iterations_upper_bound) bound on them.
3286 TODO: Due to the way record_estimate choose estimates to store, the bounds
3287 will be always nb_iterations_upper_bound-1. We can change this to record
3288 also statements not dominating the loop latch and update the walk bellow
3289 to the shortest path algorthm. */
3290 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3293 && wi::ltu_p (elt
->bound
, loop
->nb_iterations_upper_bound
))
3295 if (!not_executed_last_iteration
)
3296 not_executed_last_iteration
= pointer_set_create ();
3297 pointer_set_insert (not_executed_last_iteration
, elt
->stmt
);
3300 if (!not_executed_last_iteration
)
3303 /* Start DFS walk in the loop header and see if we can reach the
3304 loop latch or any of the exits (including statements with side
3305 effects that may terminate the loop otherwise) without visiting
3306 any of the statements known to have undefined effect on the last
3308 queue
.safe_push (loop
->header
);
3309 visited
= BITMAP_ALLOC (NULL
);
3310 bitmap_set_bit (visited
, loop
->header
->index
);
3315 basic_block bb
= queue
.pop ();
3316 gimple_stmt_iterator gsi
;
3317 bool stmt_found
= false;
3319 /* Loop for possible exits and statements bounding the execution. */
3320 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3322 gimple stmt
= gsi_stmt (gsi
);
3323 if (pointer_set_contains (not_executed_last_iteration
, stmt
))
3328 if (gimple_has_side_effects (stmt
))
3337 /* If no bounding statement is found, continue the walk. */
3343 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3345 if (loop_exit_edge_p (loop
, e
)
3346 || e
== loop_latch_edge (loop
))
3351 if (bitmap_set_bit (visited
, e
->dest
->index
))
3352 queue
.safe_push (e
->dest
);
3356 while (queue
.length () && !found_exit
);
3358 /* If every path through the loop reach bounding statement before exit,
3359 then we know the last iteration of the loop will have undefined effect
3360 and we can decrease number of iterations. */
3364 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3365 fprintf (dump_file
, "Reducing loop iteration estimate by 1; "
3366 "undefined statement must be executed at the last iteration.\n");
3367 record_niter_bound (loop
, loop
->nb_iterations_upper_bound
- 1,
3370 BITMAP_FREE (visited
);
3372 pointer_set_destroy (not_executed_last_iteration
);
3375 /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
3376 is true also use estimates derived from undefined behavior. */
3379 estimate_numbers_of_iterations_loop (struct loop
*loop
)
3384 struct tree_niter_desc niter_desc
;
3389 /* Give up if we already have tried to compute an estimation. */
3390 if (loop
->estimate_state
!= EST_NOT_COMPUTED
)
3393 loop
->estimate_state
= EST_AVAILABLE
;
3394 /* Force estimate compuation but leave any existing upper bound in place. */
3395 loop
->any_estimate
= false;
3397 /* Ensure that loop->nb_iterations is computed if possible. If it turns out
3398 to be constant, we avoid undefined behavior implied bounds and instead
3399 diagnose those loops with -Waggressive-loop-optimizations. */
3400 number_of_latch_executions (loop
);
3402 exits
= get_loop_exit_edges (loop
);
3403 likely_exit
= single_likely_exit (loop
);
3404 FOR_EACH_VEC_ELT (exits
, i
, ex
)
3406 if (!number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
3409 niter
= niter_desc
.niter
;
3410 type
= TREE_TYPE (niter
);
3411 if (TREE_CODE (niter_desc
.may_be_zero
) != INTEGER_CST
)
3412 niter
= build3 (COND_EXPR
, type
, niter_desc
.may_be_zero
,
3413 build_int_cst (type
, 0),
3415 record_estimate (loop
, niter
, niter_desc
.max
,
3416 last_stmt (ex
->src
),
3417 true, ex
== likely_exit
, true);
3421 if (flag_aggressive_loop_optimizations
)
3422 infer_loop_bounds_from_undefined (loop
);
3424 discover_iteration_bound_by_body_walk (loop
);
3426 maybe_lower_iteration_bound (loop
);
3428 /* If we have a measured profile, use it to estimate the number of
3430 if (loop
->header
->count
!= 0)
3432 gcov_type nit
= expected_loop_iterations_unbounded (loop
) + 1;
3433 bound
= gcov_type_to_wide_int (nit
);
3434 record_niter_bound (loop
, bound
, true, false);
3437 /* If we know the exact number of iterations of this loop, try to
3438 not break code with undefined behavior by not recording smaller
3439 maximum number of iterations. */
3440 if (loop
->nb_iterations
3441 && TREE_CODE (loop
->nb_iterations
) == INTEGER_CST
)
3443 loop
->any_upper_bound
= true;
3444 loop
->nb_iterations_upper_bound
= wi::to_widest (loop
->nb_iterations
);
3448 /* Sets NIT to the estimated number of executions of the latch of the
3449 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
3450 large as the number of iterations. If we have no reliable estimate,
3451 the function returns false, otherwise returns true. */
3454 estimated_loop_iterations (struct loop
*loop
, widest_int
*nit
)
3456 /* When SCEV information is available, try to update loop iterations
3457 estimate. Otherwise just return whatever we recorded earlier. */
3458 if (scev_initialized_p ())
3459 estimate_numbers_of_iterations_loop (loop
);
3461 return (get_estimated_loop_iterations (loop
, nit
));
3464 /* Similar to estimated_loop_iterations, but returns the estimate only
3465 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3466 on the number of iterations of LOOP could not be derived, returns -1. */
3469 estimated_loop_iterations_int (struct loop
*loop
)
3472 HOST_WIDE_INT hwi_nit
;
3474 if (!estimated_loop_iterations (loop
, &nit
))
3477 if (!wi::fits_shwi_p (nit
))
3479 hwi_nit
= nit
.to_shwi ();
3481 return hwi_nit
< 0 ? -1 : hwi_nit
;
3485 /* Sets NIT to an upper bound for the maximum number of executions of the
3486 latch of the LOOP. If we have no reliable estimate, the function returns
3487 false, otherwise returns true. */
3490 max_loop_iterations (struct loop
*loop
, widest_int
*nit
)
3492 /* When SCEV information is available, try to update loop iterations
3493 estimate. Otherwise just return whatever we recorded earlier. */
3494 if (scev_initialized_p ())
3495 estimate_numbers_of_iterations_loop (loop
);
3497 return get_max_loop_iterations (loop
, nit
);
3500 /* Similar to max_loop_iterations, but returns the estimate only
3501 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3502 on the number of iterations of LOOP could not be derived, returns -1. */
3505 max_loop_iterations_int (struct loop
*loop
)
3508 HOST_WIDE_INT hwi_nit
;
3510 if (!max_loop_iterations (loop
, &nit
))
3513 if (!wi::fits_shwi_p (nit
))
3515 hwi_nit
= nit
.to_shwi ();
3517 return hwi_nit
< 0 ? -1 : hwi_nit
;
3520 /* Returns an estimate for the number of executions of statements
3521 in the LOOP. For statements before the loop exit, this exceeds
3522 the number of execution of the latch by one. */
3525 estimated_stmt_executions_int (struct loop
*loop
)
3527 HOST_WIDE_INT nit
= estimated_loop_iterations_int (loop
);
3533 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
3535 /* If the computation overflows, return -1. */
3536 return snit
< 0 ? -1 : snit
;
3539 /* Sets NIT to the estimated maximum number of executions of the latch of the
3540 LOOP, plus one. If we have no reliable estimate, the function returns
3541 false, otherwise returns true. */
3544 max_stmt_executions (struct loop
*loop
, widest_int
*nit
)
3546 widest_int nit_minus_one
;
3548 if (!max_loop_iterations (loop
, nit
))
3551 nit_minus_one
= *nit
;
3555 return wi::gtu_p (*nit
, nit_minus_one
);
3558 /* Sets NIT to the estimated number of executions of the latch of the
3559 LOOP, plus one. If we have no reliable estimate, the function returns
3560 false, otherwise returns true. */
3563 estimated_stmt_executions (struct loop
*loop
, widest_int
*nit
)
3565 widest_int nit_minus_one
;
3567 if (!estimated_loop_iterations (loop
, nit
))
3570 nit_minus_one
= *nit
;
3574 return wi::gtu_p (*nit
, nit_minus_one
);
3577 /* Records estimates on numbers of iterations of loops. */
3580 estimate_numbers_of_iterations (void)
3584 /* We don't want to issue signed overflow warnings while getting
3585 loop iteration estimates. */
3586 fold_defer_overflow_warnings ();
3588 FOR_EACH_LOOP (loop
, 0)
3590 estimate_numbers_of_iterations_loop (loop
);
3593 fold_undefer_and_ignore_overflow_warnings ();
3596 /* Returns true if statement S1 dominates statement S2. */
3599 stmt_dominates_stmt_p (gimple s1
, gimple s2
)
3601 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
3609 gimple_stmt_iterator bsi
;
3611 if (gimple_code (s2
) == GIMPLE_PHI
)
3614 if (gimple_code (s1
) == GIMPLE_PHI
)
3617 for (bsi
= gsi_start_bb (bb1
); gsi_stmt (bsi
) != s2
; gsi_next (&bsi
))
3618 if (gsi_stmt (bsi
) == s1
)
3624 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
3627 /* Returns true when we can prove that the number of executions of
3628 STMT in the loop is at most NITER, according to the bound on
3629 the number of executions of the statement NITER_BOUND->stmt recorded in
3630 NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT.
3632 ??? This code can become quite a CPU hog - we can have many bounds,
3633 and large basic block forcing stmt_dominates_stmt_p to be queried
3634 many times on a large basic blocks, so the whole thing is O(n^2)
3635 for scev_probably_wraps_p invocation (that can be done n times).
3637 It would make more sense (and give better answers) to remember BB
3638 bounds computed by discover_iteration_bound_by_body_walk. */
3641 n_of_executions_at_most (gimple stmt
,
3642 struct nb_iter_bound
*niter_bound
,
3645 widest_int bound
= niter_bound
->bound
;
3646 tree nit_type
= TREE_TYPE (niter
), e
;
3649 gcc_assert (TYPE_UNSIGNED (nit_type
));
3651 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
3652 the number of iterations is small. */
3653 if (!wi::fits_to_tree_p (bound
, nit_type
))
3656 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3657 times. This means that:
3659 -- if NITER_BOUND->is_exit is true, then everything after
3660 it at most NITER_BOUND->bound times.
3662 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
3663 is executed, then NITER_BOUND->stmt is executed as well in the same
3664 iteration then STMT is executed at most NITER_BOUND->bound + 1 times.
3666 If we can determine that NITER_BOUND->stmt is always executed
3667 after STMT, then STMT is executed at most NITER_BOUND->bound + 2 times.
3668 We conclude that if both statements belong to the same
3669 basic block and STMT is before NITER_BOUND->stmt and there are no
3670 statements with side effects in between. */
3672 if (niter_bound
->is_exit
)
3674 if (stmt
== niter_bound
->stmt
3675 || !stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
3681 if (!stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
3683 gimple_stmt_iterator bsi
;
3684 if (gimple_bb (stmt
) != gimple_bb (niter_bound
->stmt
)
3685 || gimple_code (stmt
) == GIMPLE_PHI
3686 || gimple_code (niter_bound
->stmt
) == GIMPLE_PHI
)
3689 /* By stmt_dominates_stmt_p we already know that STMT appears
3690 before NITER_BOUND->STMT. Still need to test that the loop
3691 can not be terinated by a side effect in between. */
3692 for (bsi
= gsi_for_stmt (stmt
); gsi_stmt (bsi
) != niter_bound
->stmt
;
3694 if (gimple_has_side_effects (gsi_stmt (bsi
)))
3698 || !wi::fits_to_tree_p (bound
, nit_type
))
3704 e
= fold_binary (cmp
, boolean_type_node
,
3705 niter
, wide_int_to_tree (nit_type
, bound
));
3706 return e
&& integer_nonzerop (e
);
3709 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
3712 nowrap_type_p (tree type
)
3714 if (INTEGRAL_TYPE_P (type
)
3715 && TYPE_OVERFLOW_UNDEFINED (type
))
3718 if (POINTER_TYPE_P (type
))
3724 /* Return false only when the induction variable BASE + STEP * I is
3725 known to not overflow: i.e. when the number of iterations is small
3726 enough with respect to the step and initial condition in order to
3727 keep the evolution confined in TYPEs bounds. Return true when the
3728 iv is known to overflow or when the property is not computable.
3730 USE_OVERFLOW_SEMANTICS is true if this function should assume that
3731 the rules for overflow of the given language apply (e.g., that signed
3732 arithmetics in C does not overflow). */
3735 scev_probably_wraps_p (tree base
, tree step
,
3736 gimple at_stmt
, struct loop
*loop
,
3737 bool use_overflow_semantics
)
3739 tree delta
, step_abs
;
3740 tree unsigned_type
, valid_niter
;
3741 tree type
= TREE_TYPE (step
);
3744 struct nb_iter_bound
*bound
;
3746 /* FIXME: We really need something like
3747 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
3749 We used to test for the following situation that frequently appears
3750 during address arithmetics:
3752 D.1621_13 = (long unsigned intD.4) D.1620_12;
3753 D.1622_14 = D.1621_13 * 8;
3754 D.1623_15 = (doubleD.29 *) D.1622_14;
3756 And derived that the sequence corresponding to D_14
3757 can be proved to not wrap because it is used for computing a
3758 memory access; however, this is not really the case -- for example,
3759 if D_12 = (unsigned char) [254,+,1], then D_14 has values
3760 2032, 2040, 0, 8, ..., but the code is still legal. */
3762 if (chrec_contains_undetermined (base
)
3763 || chrec_contains_undetermined (step
))
3766 if (integer_zerop (step
))
3769 /* If we can use the fact that signed and pointer arithmetics does not
3770 wrap, we are done. */
3771 if (use_overflow_semantics
&& nowrap_type_p (TREE_TYPE (base
)))
3774 /* To be able to use estimates on number of iterations of the loop,
3775 we must have an upper bound on the absolute value of the step. */
3776 if (TREE_CODE (step
) != INTEGER_CST
)
3779 /* Don't issue signed overflow warnings. */
3780 fold_defer_overflow_warnings ();
3782 /* Otherwise, compute the number of iterations before we reach the
3783 bound of the type, and verify that the loop is exited before this
3785 unsigned_type
= unsigned_type_for (type
);
3786 base
= fold_convert (unsigned_type
, base
);
3788 if (tree_int_cst_sign_bit (step
))
3790 tree extreme
= fold_convert (unsigned_type
,
3791 lower_bound_in_type (type
, type
));
3792 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
3793 step_abs
= fold_build1 (NEGATE_EXPR
, unsigned_type
,
3794 fold_convert (unsigned_type
, step
));
3798 tree extreme
= fold_convert (unsigned_type
,
3799 upper_bound_in_type (type
, type
));
3800 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
3801 step_abs
= fold_convert (unsigned_type
, step
);
3804 valid_niter
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step_abs
);
3806 estimate_numbers_of_iterations_loop (loop
);
3808 if (max_loop_iterations (loop
, &niter
)
3809 && wi::fits_to_tree_p (niter
, TREE_TYPE (valid_niter
))
3810 && (e
= fold_binary (GT_EXPR
, boolean_type_node
, valid_niter
,
3811 wide_int_to_tree (TREE_TYPE (valid_niter
),
3813 && integer_nonzerop (e
))
3815 fold_undefer_and_ignore_overflow_warnings ();
3819 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
3821 if (n_of_executions_at_most (at_stmt
, bound
, valid_niter
))
3823 fold_undefer_and_ignore_overflow_warnings ();
3828 fold_undefer_and_ignore_overflow_warnings ();
3830 /* At this point we still don't have a proof that the iv does not
3831 overflow: give up. */
3835 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
3838 free_numbers_of_iterations_estimates_loop (struct loop
*loop
)
3840 struct nb_iter_bound
*bound
, *next
;
3842 loop
->nb_iterations
= NULL
;
3843 loop
->estimate_state
= EST_NOT_COMPUTED
;
3844 for (bound
= loop
->bounds
; bound
; bound
= next
)
3850 loop
->bounds
= NULL
;
3853 /* Frees the information on upper bounds on numbers of iterations of loops. */
3856 free_numbers_of_iterations_estimates (void)
3860 FOR_EACH_LOOP (loop
, 0)
3862 free_numbers_of_iterations_estimates_loop (loop
);
3866 /* Substitute value VAL for ssa name NAME inside expressions held
3870 substitute_in_loop_info (struct loop
*loop
, tree name
, tree val
)
3872 loop
->nb_iterations
= simplify_replace_tree (loop
->nb_iterations
, name
, val
);