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"
26 #include "basic-block.h"
27 #include "gimple-pretty-print.h"
30 #include "gimple-iterator.h"
31 #include "gimple-ssa.h"
33 #include "tree-phinodes.h"
34 #include "ssa-iterators.h"
35 #include "tree-ssa-loop-ivopts.h"
36 #include "tree-ssa-loop-niter.h"
37 #include "tree-ssa-loop.h"
41 #include "tree-chrec.h"
42 #include "tree-scalar-evolution.h"
43 #include "tree-data-ref.h"
46 #include "diagnostic-core.h"
47 #include "tree-inline.h"
48 #include "tree-pass.h"
49 #include "tree-ssanames.h"
52 #define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
54 /* The maximum number of dominator BBs we search for conditions
55 of loop header copies we use for simplifying a conditional
57 #define MAX_DOMINATORS_TO_WALK 8
61 Analysis of number of iterations of an affine exit test.
65 /* Bounds on some value, BELOW <= X <= UP. */
73 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */
76 split_to_var_and_offset (tree expr
, tree
*var
, mpz_t offset
)
78 tree type
= TREE_TYPE (expr
);
84 mpz_set_ui (offset
, 0);
86 switch (TREE_CODE (expr
))
93 case POINTER_PLUS_EXPR
:
94 op0
= TREE_OPERAND (expr
, 0);
95 op1
= TREE_OPERAND (expr
, 1);
97 if (TREE_CODE (op1
) != INTEGER_CST
)
101 /* Always sign extend the offset. */
102 off
= tree_to_double_int (op1
);
103 off
= off
.sext (TYPE_PRECISION (type
));
104 mpz_set_double_int (offset
, off
, false);
106 mpz_neg (offset
, offset
);
110 *var
= build_int_cst_type (type
, 0);
111 off
= tree_to_double_int (expr
);
112 mpz_set_double_int (offset
, off
, TYPE_UNSIGNED (type
));
120 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
121 in TYPE to MIN and MAX. */
124 determine_value_range (struct loop
*loop
, tree type
, tree var
, mpz_t off
,
125 mpz_t min
, mpz_t max
)
127 double_int minv
, maxv
;
128 enum value_range_type rtype
= VR_VARYING
;
130 /* If the expression is a constant, we know its value exactly. */
131 if (integer_zerop (var
))
138 get_type_static_bounds (type
, min
, max
);
140 /* See if we have some range info from VRP. */
141 if (TREE_CODE (var
) == SSA_NAME
&& INTEGRAL_TYPE_P (type
))
143 edge e
= loop_preheader_edge (loop
);
144 gimple_stmt_iterator gsi
;
146 /* Either for VAR itself... */
147 rtype
= get_range_info (var
, &minv
, &maxv
);
148 /* Or for PHI results in loop->header where VAR is used as
149 PHI argument from the loop preheader edge. */
150 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
152 gimple phi
= gsi_stmt (gsi
);
153 double_int minc
, maxc
;
154 if (PHI_ARG_DEF_FROM_EDGE (phi
, e
) == var
155 && (get_range_info (gimple_phi_result (phi
), &minc
, &maxc
)
158 if (rtype
!= VR_RANGE
)
166 minv
= minv
.max (minc
, TYPE_UNSIGNED (type
));
167 maxv
= maxv
.min (maxc
, TYPE_UNSIGNED (type
));
168 gcc_assert (minv
.cmp (maxv
, TYPE_UNSIGNED (type
)) <= 0);
172 if (rtype
== VR_RANGE
)
175 gcc_assert (minv
.cmp (maxv
, TYPE_UNSIGNED (type
)) <= 0);
178 mpz_set_double_int (minm
, minv
, TYPE_UNSIGNED (type
));
179 mpz_set_double_int (maxm
, maxv
, TYPE_UNSIGNED (type
));
180 mpz_add (minm
, minm
, off
);
181 mpz_add (maxm
, maxm
, off
);
182 /* If the computation may not wrap or off is zero, then this
183 is always fine. If off is negative and minv + off isn't
184 smaller than type's minimum, or off is positive and
185 maxv + off isn't bigger than type's maximum, use the more
186 precise range too. */
187 if (nowrap_type_p (type
)
188 || mpz_sgn (off
) == 0
189 || (mpz_sgn (off
) < 0 && mpz_cmp (minm
, min
) >= 0)
190 || (mpz_sgn (off
) > 0 && mpz_cmp (maxm
, max
) <= 0))
203 /* If the computation may wrap, we know nothing about the value, except for
204 the range of the type. */
205 if (!nowrap_type_p (type
))
208 /* Since the addition of OFF does not wrap, if OFF is positive, then we may
209 add it to MIN, otherwise to MAX. */
210 if (mpz_sgn (off
) < 0)
211 mpz_add (max
, max
, off
);
213 mpz_add (min
, min
, off
);
216 /* Stores the bounds on the difference of the values of the expressions
217 (var + X) and (var + Y), computed in TYPE, to BNDS. */
220 bound_difference_of_offsetted_base (tree type
, mpz_t x
, mpz_t y
,
223 int rel
= mpz_cmp (x
, y
);
224 bool may_wrap
= !nowrap_type_p (type
);
227 /* If X == Y, then the expressions are always equal.
228 If X > Y, there are the following possibilities:
229 a) neither of var + X and var + Y overflow or underflow, or both of
230 them do. Then their difference is X - Y.
231 b) var + X overflows, and var + Y does not. Then the values of the
232 expressions are var + X - M and var + Y, where M is the range of
233 the type, and their difference is X - Y - M.
234 c) var + Y underflows and var + X does not. Their difference again
236 Therefore, if the arithmetics in type does not overflow, then the
237 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
238 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
239 (X - Y, X - Y + M). */
243 mpz_set_ui (bnds
->below
, 0);
244 mpz_set_ui (bnds
->up
, 0);
249 mpz_set_double_int (m
, double_int::mask (TYPE_PRECISION (type
)), true);
250 mpz_add_ui (m
, m
, 1);
251 mpz_sub (bnds
->up
, x
, y
);
252 mpz_set (bnds
->below
, bnds
->up
);
257 mpz_sub (bnds
->below
, bnds
->below
, m
);
259 mpz_add (bnds
->up
, bnds
->up
, m
);
265 /* From condition C0 CMP C1 derives information regarding the
266 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
267 and stores it to BNDS. */
270 refine_bounds_using_guard (tree type
, tree varx
, mpz_t offx
,
271 tree vary
, mpz_t offy
,
272 tree c0
, enum tree_code cmp
, tree c1
,
275 tree varc0
, varc1
, tmp
, ctype
;
276 mpz_t offc0
, offc1
, loffx
, loffy
, bnd
;
278 bool no_wrap
= nowrap_type_p (type
);
287 STRIP_SIGN_NOPS (c0
);
288 STRIP_SIGN_NOPS (c1
);
289 ctype
= TREE_TYPE (c0
);
290 if (!useless_type_conversion_p (ctype
, type
))
296 /* We could derive quite precise information from EQ_EXPR, however, such
297 a guard is unlikely to appear, so we do not bother with handling
302 /* NE_EXPR comparisons do not contain much of useful information, except for
303 special case of comparing with the bounds of the type. */
304 if (TREE_CODE (c1
) != INTEGER_CST
305 || !INTEGRAL_TYPE_P (type
))
308 /* Ensure that the condition speaks about an expression in the same type
310 ctype
= TREE_TYPE (c0
);
311 if (TYPE_PRECISION (ctype
) != TYPE_PRECISION (type
))
313 c0
= fold_convert (type
, c0
);
314 c1
= fold_convert (type
, c1
);
316 if (TYPE_MIN_VALUE (type
)
317 && operand_equal_p (c1
, TYPE_MIN_VALUE (type
), 0))
322 if (TYPE_MAX_VALUE (type
)
323 && operand_equal_p (c1
, TYPE_MAX_VALUE (type
), 0))
336 split_to_var_and_offset (expand_simple_operations (c0
), &varc0
, offc0
);
337 split_to_var_and_offset (expand_simple_operations (c1
), &varc1
, offc1
);
339 /* We are only interested in comparisons of expressions based on VARX and
340 VARY. TODO -- we might also be able to derive some bounds from
341 expressions containing just one of the variables. */
343 if (operand_equal_p (varx
, varc1
, 0))
345 tmp
= varc0
; varc0
= varc1
; varc1
= tmp
;
346 mpz_swap (offc0
, offc1
);
347 cmp
= swap_tree_comparison (cmp
);
350 if (!operand_equal_p (varx
, varc0
, 0)
351 || !operand_equal_p (vary
, varc1
, 0))
354 mpz_init_set (loffx
, offx
);
355 mpz_init_set (loffy
, offy
);
357 if (cmp
== GT_EXPR
|| cmp
== GE_EXPR
)
359 tmp
= varx
; varx
= vary
; vary
= tmp
;
360 mpz_swap (offc0
, offc1
);
361 mpz_swap (loffx
, loffy
);
362 cmp
= swap_tree_comparison (cmp
);
366 /* If there is no overflow, the condition implies that
368 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
370 The overflows and underflows may complicate things a bit; each
371 overflow decreases the appropriate offset by M, and underflow
372 increases it by M. The above inequality would not necessarily be
375 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
376 VARX + OFFC0 overflows, but VARX + OFFX does not.
377 This may only happen if OFFX < OFFC0.
378 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
379 VARY + OFFC1 underflows and VARY + OFFY does not.
380 This may only happen if OFFY > OFFC1. */
389 x_ok
= (integer_zerop (varx
)
390 || mpz_cmp (loffx
, offc0
) >= 0);
391 y_ok
= (integer_zerop (vary
)
392 || mpz_cmp (loffy
, offc1
) <= 0);
398 mpz_sub (bnd
, loffx
, loffy
);
399 mpz_add (bnd
, bnd
, offc1
);
400 mpz_sub (bnd
, bnd
, offc0
);
403 mpz_sub_ui (bnd
, bnd
, 1);
408 if (mpz_cmp (bnds
->below
, bnd
) < 0)
409 mpz_set (bnds
->below
, bnd
);
413 if (mpz_cmp (bnd
, bnds
->up
) < 0)
414 mpz_set (bnds
->up
, bnd
);
426 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
427 The subtraction is considered to be performed in arbitrary precision,
430 We do not attempt to be too clever regarding the value ranges of X and
431 Y; most of the time, they are just integers or ssa names offsetted by
432 integer. However, we try to use the information contained in the
433 comparisons before the loop (usually created by loop header copying). */
436 bound_difference (struct loop
*loop
, tree x
, tree y
, bounds
*bnds
)
438 tree type
= TREE_TYPE (x
);
441 mpz_t minx
, maxx
, miny
, maxy
;
449 /* Get rid of unnecessary casts, but preserve the value of
454 mpz_init (bnds
->below
);
458 split_to_var_and_offset (x
, &varx
, offx
);
459 split_to_var_and_offset (y
, &vary
, offy
);
461 if (!integer_zerop (varx
)
462 && operand_equal_p (varx
, vary
, 0))
464 /* Special case VARX == VARY -- we just need to compare the
465 offsets. The matters are a bit more complicated in the
466 case addition of offsets may wrap. */
467 bound_difference_of_offsetted_base (type
, offx
, offy
, bnds
);
471 /* Otherwise, use the value ranges to determine the initial
472 estimates on below and up. */
477 determine_value_range (loop
, type
, varx
, offx
, minx
, maxx
);
478 determine_value_range (loop
, type
, vary
, offy
, miny
, maxy
);
480 mpz_sub (bnds
->below
, minx
, maxy
);
481 mpz_sub (bnds
->up
, maxx
, miny
);
488 /* If both X and Y are constants, we cannot get any more precise. */
489 if (integer_zerop (varx
) && integer_zerop (vary
))
492 /* Now walk the dominators of the loop header and use the entry
493 guards to refine the estimates. */
494 for (bb
= loop
->header
;
495 bb
!= ENTRY_BLOCK_PTR
&& cnt
< MAX_DOMINATORS_TO_WALK
;
496 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
498 if (!single_pred_p (bb
))
500 e
= single_pred_edge (bb
);
502 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
505 cond
= last_stmt (e
->src
);
506 c0
= gimple_cond_lhs (cond
);
507 cmp
= gimple_cond_code (cond
);
508 c1
= gimple_cond_rhs (cond
);
510 if (e
->flags
& EDGE_FALSE_VALUE
)
511 cmp
= invert_tree_comparison (cmp
, false);
513 refine_bounds_using_guard (type
, varx
, offx
, vary
, offy
,
523 /* Update the bounds in BNDS that restrict the value of X to the bounds
524 that restrict the value of X + DELTA. X can be obtained as a
525 difference of two values in TYPE. */
528 bounds_add (bounds
*bnds
, double_int delta
, tree type
)
533 mpz_set_double_int (mdelta
, delta
, false);
536 mpz_set_double_int (max
, double_int::mask (TYPE_PRECISION (type
)), true);
538 mpz_add (bnds
->up
, bnds
->up
, mdelta
);
539 mpz_add (bnds
->below
, bnds
->below
, mdelta
);
541 if (mpz_cmp (bnds
->up
, max
) > 0)
542 mpz_set (bnds
->up
, max
);
545 if (mpz_cmp (bnds
->below
, max
) < 0)
546 mpz_set (bnds
->below
, max
);
552 /* Update the bounds in BNDS that restrict the value of X to the bounds
553 that restrict the value of -X. */
556 bounds_negate (bounds
*bnds
)
560 mpz_init_set (tmp
, bnds
->up
);
561 mpz_neg (bnds
->up
, bnds
->below
);
562 mpz_neg (bnds
->below
, tmp
);
566 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
569 inverse (tree x
, tree mask
)
571 tree type
= TREE_TYPE (x
);
573 unsigned ctr
= tree_floor_log2 (mask
);
575 if (TYPE_PRECISION (type
) <= HOST_BITS_PER_WIDE_INT
)
577 unsigned HOST_WIDE_INT ix
;
578 unsigned HOST_WIDE_INT imask
;
579 unsigned HOST_WIDE_INT irslt
= 1;
581 gcc_assert (cst_and_fits_in_hwi (x
));
582 gcc_assert (cst_and_fits_in_hwi (mask
));
584 ix
= int_cst_value (x
);
585 imask
= int_cst_value (mask
);
594 rslt
= build_int_cst_type (type
, irslt
);
598 rslt
= build_int_cst (type
, 1);
601 rslt
= int_const_binop (MULT_EXPR
, rslt
, x
);
602 x
= int_const_binop (MULT_EXPR
, x
, x
);
604 rslt
= int_const_binop (BIT_AND_EXPR
, rslt
, mask
);
610 /* Derives the upper bound BND on the number of executions of loop with exit
611 condition S * i <> C. If NO_OVERFLOW is true, then the control variable of
612 the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed
613 that the loop ends through this exit, i.e., the induction variable ever
614 reaches the value of C.
616 The value C is equal to final - base, where final and base are the final and
617 initial value of the actual induction variable in the analysed loop. BNDS
618 bounds the value of this difference when computed in signed type with
619 unbounded range, while the computation of C is performed in an unsigned
620 type with the range matching the range of the type of the induction variable.
621 In particular, BNDS.up contains an upper bound on C in the following cases:
622 -- if the iv must reach its final value without overflow, i.e., if
623 NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
624 -- if final >= base, which we know to hold when BNDS.below >= 0. */
627 number_of_iterations_ne_max (mpz_t bnd
, bool no_overflow
, tree c
, tree s
,
628 bounds
*bnds
, bool exit_must_be_taken
)
632 tree type
= TREE_TYPE (c
);
633 bool bnds_u_valid
= ((no_overflow
&& exit_must_be_taken
)
634 || mpz_sgn (bnds
->below
) >= 0);
637 || (TREE_CODE (c
) == INTEGER_CST
638 && TREE_CODE (s
) == INTEGER_CST
639 && tree_to_double_int (c
).mod (tree_to_double_int (s
),
640 TYPE_UNSIGNED (type
),
641 EXACT_DIV_EXPR
).is_zero ())
642 || (TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (c
))
643 && multiple_of_p (type
, c
, s
)))
645 /* If C is an exact multiple of S, then its value will be reached before
646 the induction variable overflows (unless the loop is exited in some
647 other way before). Note that the actual induction variable in the
648 loop (which ranges from base to final instead of from 0 to C) may
649 overflow, in which case BNDS.up will not be giving a correct upper
650 bound on C; thus, BNDS_U_VALID had to be computed in advance. */
652 exit_must_be_taken
= true;
655 /* If the induction variable can overflow, the number of iterations is at
656 most the period of the control variable (or infinite, but in that case
657 the whole # of iterations analysis will fail). */
660 max
= double_int::mask (TYPE_PRECISION (type
)
661 - tree_low_cst (num_ending_zeros (s
), 1));
662 mpz_set_double_int (bnd
, max
, true);
666 /* Now we know that the induction variable does not overflow, so the loop
667 iterates at most (range of type / S) times. */
668 mpz_set_double_int (bnd
, double_int::mask (TYPE_PRECISION (type
)), true);
670 /* If the induction variable is guaranteed to reach the value of C before
672 if (exit_must_be_taken
)
674 /* ... then we can strengthen this to C / S, and possibly we can use
675 the upper bound on C given by BNDS. */
676 if (TREE_CODE (c
) == INTEGER_CST
)
677 mpz_set_double_int (bnd
, tree_to_double_int (c
), true);
678 else if (bnds_u_valid
)
679 mpz_set (bnd
, bnds
->up
);
683 mpz_set_double_int (d
, tree_to_double_int (s
), true);
684 mpz_fdiv_q (bnd
, bnd
, d
);
688 /* Determines number of iterations of loop whose ending condition
689 is IV <> FINAL. TYPE is the type of the iv. The number of
690 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
691 we know that the exit must be taken eventually, i.e., that the IV
692 ever reaches the value FINAL (we derived this earlier, and possibly set
693 NITER->assumptions to make sure this is the case). BNDS contains the
694 bounds on the difference FINAL - IV->base. */
697 number_of_iterations_ne (tree type
, affine_iv
*iv
, tree final
,
698 struct tree_niter_desc
*niter
, bool exit_must_be_taken
,
701 tree niter_type
= unsigned_type_for (type
);
702 tree s
, c
, d
, bits
, assumption
, tmp
, bound
;
705 niter
->control
= *iv
;
706 niter
->bound
= final
;
707 niter
->cmp
= NE_EXPR
;
709 /* Rearrange the terms so that we get inequality S * i <> C, with S
710 positive. Also cast everything to the unsigned type. If IV does
711 not overflow, BNDS bounds the value of C. Also, this is the
712 case if the computation |FINAL - IV->base| does not overflow, i.e.,
713 if BNDS->below in the result is nonnegative. */
714 if (tree_int_cst_sign_bit (iv
->step
))
716 s
= fold_convert (niter_type
,
717 fold_build1 (NEGATE_EXPR
, type
, iv
->step
));
718 c
= fold_build2 (MINUS_EXPR
, niter_type
,
719 fold_convert (niter_type
, iv
->base
),
720 fold_convert (niter_type
, final
));
721 bounds_negate (bnds
);
725 s
= fold_convert (niter_type
, iv
->step
);
726 c
= fold_build2 (MINUS_EXPR
, niter_type
,
727 fold_convert (niter_type
, final
),
728 fold_convert (niter_type
, iv
->base
));
732 number_of_iterations_ne_max (max
, iv
->no_overflow
, c
, s
, bnds
,
734 niter
->max
= mpz_get_double_int (niter_type
, max
, false);
737 /* First the trivial cases -- when the step is 1. */
738 if (integer_onep (s
))
744 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
745 is infinite. Otherwise, the number of iterations is
746 (inverse(s/d) * (c/d)) mod (size of mode/d). */
747 bits
= num_ending_zeros (s
);
748 bound
= build_low_bits_mask (niter_type
,
749 (TYPE_PRECISION (niter_type
)
750 - tree_low_cst (bits
, 1)));
752 d
= fold_binary_to_constant (LSHIFT_EXPR
, niter_type
,
753 build_int_cst (niter_type
, 1), bits
);
754 s
= fold_binary_to_constant (RSHIFT_EXPR
, niter_type
, s
, bits
);
756 if (!exit_must_be_taken
)
758 /* If we cannot assume that the exit is taken eventually, record the
759 assumptions for divisibility of c. */
760 assumption
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, c
, d
);
761 assumption
= fold_build2 (EQ_EXPR
, boolean_type_node
,
762 assumption
, build_int_cst (niter_type
, 0));
763 if (!integer_nonzerop (assumption
))
764 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
765 niter
->assumptions
, assumption
);
768 c
= fold_build2 (EXACT_DIV_EXPR
, niter_type
, c
, d
);
769 tmp
= fold_build2 (MULT_EXPR
, niter_type
, c
, inverse (s
, bound
));
770 niter
->niter
= fold_build2 (BIT_AND_EXPR
, niter_type
, tmp
, bound
);
774 /* Checks whether we can determine the final value of the control variable
775 of the loop with ending condition IV0 < IV1 (computed in TYPE).
776 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
777 of the step. The assumptions necessary to ensure that the computation
778 of the final value does not overflow are recorded in NITER. If we
779 find the final value, we adjust DELTA and return TRUE. Otherwise
780 we return false. BNDS bounds the value of IV1->base - IV0->base,
781 and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
782 true if we know that the exit must be taken eventually. */
785 number_of_iterations_lt_to_ne (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
786 struct tree_niter_desc
*niter
,
787 tree
*delta
, tree step
,
788 bool exit_must_be_taken
, bounds
*bnds
)
790 tree niter_type
= TREE_TYPE (step
);
791 tree mod
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, *delta
, step
);
794 tree assumption
= boolean_true_node
, bound
, noloop
;
795 bool ret
= false, fv_comp_no_overflow
;
797 if (POINTER_TYPE_P (type
))
800 if (TREE_CODE (mod
) != INTEGER_CST
)
802 if (integer_nonzerop (mod
))
803 mod
= fold_build2 (MINUS_EXPR
, niter_type
, step
, mod
);
804 tmod
= fold_convert (type1
, mod
);
807 mpz_set_double_int (mmod
, tree_to_double_int (mod
), true);
808 mpz_neg (mmod
, mmod
);
810 /* If the induction variable does not overflow and the exit is taken,
811 then the computation of the final value does not overflow. This is
812 also obviously the case if the new final value is equal to the
813 current one. Finally, we postulate this for pointer type variables,
814 as the code cannot rely on the object to that the pointer points being
815 placed at the end of the address space (and more pragmatically,
816 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
817 if (integer_zerop (mod
) || POINTER_TYPE_P (type
))
818 fv_comp_no_overflow
= true;
819 else if (!exit_must_be_taken
)
820 fv_comp_no_overflow
= false;
822 fv_comp_no_overflow
=
823 (iv0
->no_overflow
&& integer_nonzerop (iv0
->step
))
824 || (iv1
->no_overflow
&& integer_nonzerop (iv1
->step
));
826 if (integer_nonzerop (iv0
->step
))
828 /* The final value of the iv is iv1->base + MOD, assuming that this
829 computation does not overflow, and that
830 iv0->base <= iv1->base + MOD. */
831 if (!fv_comp_no_overflow
)
833 bound
= fold_build2 (MINUS_EXPR
, type1
,
834 TYPE_MAX_VALUE (type1
), tmod
);
835 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
837 if (integer_zerop (assumption
))
840 if (mpz_cmp (mmod
, bnds
->below
) < 0)
841 noloop
= boolean_false_node
;
842 else if (POINTER_TYPE_P (type
))
843 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
845 fold_build_pointer_plus (iv1
->base
, tmod
));
847 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
849 fold_build2 (PLUS_EXPR
, type1
,
854 /* The final value of the iv is iv0->base - MOD, assuming that this
855 computation does not overflow, and that
856 iv0->base - MOD <= iv1->base. */
857 if (!fv_comp_no_overflow
)
859 bound
= fold_build2 (PLUS_EXPR
, type1
,
860 TYPE_MIN_VALUE (type1
), tmod
);
861 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
863 if (integer_zerop (assumption
))
866 if (mpz_cmp (mmod
, bnds
->below
) < 0)
867 noloop
= boolean_false_node
;
868 else if (POINTER_TYPE_P (type
))
869 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
870 fold_build_pointer_plus (iv0
->base
,
871 fold_build1 (NEGATE_EXPR
,
875 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
876 fold_build2 (MINUS_EXPR
, type1
,
881 if (!integer_nonzerop (assumption
))
882 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
885 if (!integer_zerop (noloop
))
886 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
889 bounds_add (bnds
, tree_to_double_int (mod
), type
);
890 *delta
= fold_build2 (PLUS_EXPR
, niter_type
, *delta
, mod
);
898 /* Add assertions to NITER that ensure that the control variable of the loop
899 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
900 are TYPE. Returns false if we can prove that there is an overflow, true
901 otherwise. STEP is the absolute value of the step. */
904 assert_no_overflow_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
905 struct tree_niter_desc
*niter
, tree step
)
907 tree bound
, d
, assumption
, diff
;
908 tree niter_type
= TREE_TYPE (step
);
910 if (integer_nonzerop (iv0
->step
))
912 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
913 if (iv0
->no_overflow
)
916 /* If iv0->base is a constant, we can determine the last value before
917 overflow precisely; otherwise we conservatively assume
920 if (TREE_CODE (iv0
->base
) == INTEGER_CST
)
922 d
= fold_build2 (MINUS_EXPR
, niter_type
,
923 fold_convert (niter_type
, TYPE_MAX_VALUE (type
)),
924 fold_convert (niter_type
, iv0
->base
));
925 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
928 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
929 build_int_cst (niter_type
, 1));
930 bound
= fold_build2 (MINUS_EXPR
, type
,
931 TYPE_MAX_VALUE (type
), fold_convert (type
, diff
));
932 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
937 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
938 if (iv1
->no_overflow
)
941 if (TREE_CODE (iv1
->base
) == INTEGER_CST
)
943 d
= fold_build2 (MINUS_EXPR
, niter_type
,
944 fold_convert (niter_type
, iv1
->base
),
945 fold_convert (niter_type
, TYPE_MIN_VALUE (type
)));
946 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
949 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
950 build_int_cst (niter_type
, 1));
951 bound
= fold_build2 (PLUS_EXPR
, type
,
952 TYPE_MIN_VALUE (type
), fold_convert (type
, diff
));
953 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
957 if (integer_zerop (assumption
))
959 if (!integer_nonzerop (assumption
))
960 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
961 niter
->assumptions
, assumption
);
963 iv0
->no_overflow
= true;
964 iv1
->no_overflow
= true;
968 /* Add an assumption to NITER that a loop whose ending condition
969 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
970 bounds the value of IV1->base - IV0->base. */
973 assert_loop_rolls_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
974 struct tree_niter_desc
*niter
, bounds
*bnds
)
976 tree assumption
= boolean_true_node
, bound
, diff
;
977 tree mbz
, mbzl
, mbzr
, type1
;
978 bool rolls_p
, no_overflow_p
;
982 /* We are going to compute the number of iterations as
983 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
984 variant of TYPE. This formula only works if
986 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
988 (where MAX is the maximum value of the unsigned variant of TYPE, and
989 the computations in this formula are performed in full precision,
990 i.e., without overflows).
992 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
993 we have a condition of the form iv0->base - step < iv1->base before the loop,
994 and for loops iv0->base < iv1->base - step * i the condition
995 iv0->base < iv1->base + step, due to loop header copying, which enable us
996 to prove the lower bound.
998 The upper bound is more complicated. Unless the expressions for initial
999 and final value themselves contain enough information, we usually cannot
1000 derive it from the context. */
1002 /* First check whether the answer does not follow from the bounds we gathered
1004 if (integer_nonzerop (iv0
->step
))
1005 dstep
= tree_to_double_int (iv0
->step
);
1008 dstep
= tree_to_double_int (iv1
->step
).sext (TYPE_PRECISION (type
));
1013 mpz_set_double_int (mstep
, dstep
, true);
1014 mpz_neg (mstep
, mstep
);
1015 mpz_add_ui (mstep
, mstep
, 1);
1017 rolls_p
= mpz_cmp (mstep
, bnds
->below
) <= 0;
1020 mpz_set_double_int (max
, double_int::mask (TYPE_PRECISION (type
)), true);
1021 mpz_add (max
, max
, mstep
);
1022 no_overflow_p
= (mpz_cmp (bnds
->up
, max
) <= 0
1023 /* For pointers, only values lying inside a single object
1024 can be compared or manipulated by pointer arithmetics.
1025 Gcc in general does not allow or handle objects larger
1026 than half of the address space, hence the upper bound
1027 is satisfied for pointers. */
1028 || POINTER_TYPE_P (type
));
1032 if (rolls_p
&& no_overflow_p
)
1036 if (POINTER_TYPE_P (type
))
1039 /* Now the hard part; we must formulate the assumption(s) as expressions, and
1040 we must be careful not to introduce overflow. */
1042 if (integer_nonzerop (iv0
->step
))
1044 diff
= fold_build2 (MINUS_EXPR
, type1
,
1045 iv0
->step
, build_int_cst (type1
, 1));
1047 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
1048 0 address never belongs to any object, we can assume this for
1050 if (!POINTER_TYPE_P (type
))
1052 bound
= fold_build2 (PLUS_EXPR
, type1
,
1053 TYPE_MIN_VALUE (type
), diff
);
1054 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
1058 /* And then we can compute iv0->base - diff, and compare it with
1060 mbzl
= fold_build2 (MINUS_EXPR
, type1
,
1061 fold_convert (type1
, iv0
->base
), diff
);
1062 mbzr
= fold_convert (type1
, iv1
->base
);
1066 diff
= fold_build2 (PLUS_EXPR
, type1
,
1067 iv1
->step
, build_int_cst (type1
, 1));
1069 if (!POINTER_TYPE_P (type
))
1071 bound
= fold_build2 (PLUS_EXPR
, type1
,
1072 TYPE_MAX_VALUE (type
), diff
);
1073 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
1077 mbzl
= fold_convert (type1
, iv0
->base
);
1078 mbzr
= fold_build2 (MINUS_EXPR
, type1
,
1079 fold_convert (type1
, iv1
->base
), diff
);
1082 if (!integer_nonzerop (assumption
))
1083 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1084 niter
->assumptions
, assumption
);
1087 mbz
= fold_build2 (GT_EXPR
, boolean_type_node
, mbzl
, mbzr
);
1088 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1089 niter
->may_be_zero
, mbz
);
1093 /* Determines number of iterations of loop whose ending condition
1094 is IV0 < IV1. TYPE is the type of the iv. The number of
1095 iterations is stored to NITER. BNDS bounds the difference
1096 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
1097 that the exit must be taken eventually. */
1100 number_of_iterations_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1101 struct tree_niter_desc
*niter
,
1102 bool exit_must_be_taken
, bounds
*bnds
)
1104 tree niter_type
= unsigned_type_for (type
);
1105 tree delta
, step
, s
;
1108 if (integer_nonzerop (iv0
->step
))
1110 niter
->control
= *iv0
;
1111 niter
->cmp
= LT_EXPR
;
1112 niter
->bound
= iv1
->base
;
1116 niter
->control
= *iv1
;
1117 niter
->cmp
= GT_EXPR
;
1118 niter
->bound
= iv0
->base
;
1121 delta
= fold_build2 (MINUS_EXPR
, niter_type
,
1122 fold_convert (niter_type
, iv1
->base
),
1123 fold_convert (niter_type
, iv0
->base
));
1125 /* First handle the special case that the step is +-1. */
1126 if ((integer_onep (iv0
->step
) && integer_zerop (iv1
->step
))
1127 || (integer_all_onesp (iv1
->step
) && integer_zerop (iv0
->step
)))
1129 /* for (i = iv0->base; i < iv1->base; i++)
1133 for (i = iv1->base; i > iv0->base; i--).
1135 In both cases # of iterations is iv1->base - iv0->base, assuming that
1136 iv1->base >= iv0->base.
1138 First try to derive a lower bound on the value of
1139 iv1->base - iv0->base, computed in full precision. If the difference
1140 is nonnegative, we are done, otherwise we must record the
1143 if (mpz_sgn (bnds
->below
) < 0)
1144 niter
->may_be_zero
= fold_build2 (LT_EXPR
, boolean_type_node
,
1145 iv1
->base
, iv0
->base
);
1146 niter
->niter
= delta
;
1147 niter
->max
= mpz_get_double_int (niter_type
, bnds
->up
, false);
1151 if (integer_nonzerop (iv0
->step
))
1152 step
= fold_convert (niter_type
, iv0
->step
);
1154 step
= fold_convert (niter_type
,
1155 fold_build1 (NEGATE_EXPR
, type
, iv1
->step
));
1157 /* If we can determine the final value of the control iv exactly, we can
1158 transform the condition to != comparison. In particular, this will be
1159 the case if DELTA is constant. */
1160 if (number_of_iterations_lt_to_ne (type
, iv0
, iv1
, niter
, &delta
, step
,
1161 exit_must_be_taken
, bnds
))
1165 zps
.base
= build_int_cst (niter_type
, 0);
1167 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1168 zps does not overflow. */
1169 zps
.no_overflow
= true;
1171 return number_of_iterations_ne (type
, &zps
, delta
, niter
, true, bnds
);
1174 /* Make sure that the control iv does not overflow. */
1175 if (!assert_no_overflow_lt (type
, iv0
, iv1
, niter
, step
))
1178 /* We determine the number of iterations as (delta + step - 1) / step. For
1179 this to work, we must know that iv1->base >= iv0->base - step + 1,
1180 otherwise the loop does not roll. */
1181 assert_loop_rolls_lt (type
, iv0
, iv1
, niter
, bnds
);
1183 s
= fold_build2 (MINUS_EXPR
, niter_type
,
1184 step
, build_int_cst (niter_type
, 1));
1185 delta
= fold_build2 (PLUS_EXPR
, niter_type
, delta
, s
);
1186 niter
->niter
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, delta
, step
);
1190 mpz_set_double_int (mstep
, tree_to_double_int (step
), true);
1191 mpz_add (tmp
, bnds
->up
, mstep
);
1192 mpz_sub_ui (tmp
, tmp
, 1);
1193 mpz_fdiv_q (tmp
, tmp
, mstep
);
1194 niter
->max
= mpz_get_double_int (niter_type
, tmp
, false);
1201 /* Determines number of iterations of loop whose ending condition
1202 is IV0 <= IV1. TYPE is the type of the iv. The number of
1203 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
1204 we know that this condition must eventually become false (we derived this
1205 earlier, and possibly set NITER->assumptions to make sure this
1206 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1209 number_of_iterations_le (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1210 struct tree_niter_desc
*niter
, bool exit_must_be_taken
,
1215 if (POINTER_TYPE_P (type
))
1218 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1219 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1220 value of the type. This we must know anyway, since if it is
1221 equal to this value, the loop rolls forever. We do not check
1222 this condition for pointer type ivs, as the code cannot rely on
1223 the object to that the pointer points being placed at the end of
1224 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1225 not defined for pointers). */
1227 if (!exit_must_be_taken
&& !POINTER_TYPE_P (type
))
1229 if (integer_nonzerop (iv0
->step
))
1230 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1231 iv1
->base
, TYPE_MAX_VALUE (type
));
1233 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1234 iv0
->base
, TYPE_MIN_VALUE (type
));
1236 if (integer_zerop (assumption
))
1238 if (!integer_nonzerop (assumption
))
1239 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1240 niter
->assumptions
, assumption
);
1243 if (integer_nonzerop (iv0
->step
))
1245 if (POINTER_TYPE_P (type
))
1246 iv1
->base
= fold_build_pointer_plus_hwi (iv1
->base
, 1);
1248 iv1
->base
= fold_build2 (PLUS_EXPR
, type1
, iv1
->base
,
1249 build_int_cst (type1
, 1));
1251 else if (POINTER_TYPE_P (type
))
1252 iv0
->base
= fold_build_pointer_plus_hwi (iv0
->base
, -1);
1254 iv0
->base
= fold_build2 (MINUS_EXPR
, type1
,
1255 iv0
->base
, build_int_cst (type1
, 1));
1257 bounds_add (bnds
, double_int_one
, type1
);
1259 return number_of_iterations_lt (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1263 /* Dumps description of affine induction variable IV to FILE. */
1266 dump_affine_iv (FILE *file
, affine_iv
*iv
)
1268 if (!integer_zerop (iv
->step
))
1269 fprintf (file
, "[");
1271 print_generic_expr (dump_file
, iv
->base
, TDF_SLIM
);
1273 if (!integer_zerop (iv
->step
))
1275 fprintf (file
, ", + , ");
1276 print_generic_expr (dump_file
, iv
->step
, TDF_SLIM
);
1277 fprintf (file
, "]%s", iv
->no_overflow
? "(no_overflow)" : "");
1281 /* Determine the number of iterations according to condition (for staying
1282 inside loop) which compares two induction variables using comparison
1283 operator CODE. The induction variable on left side of the comparison
1284 is IV0, the right-hand side is IV1. Both induction variables must have
1285 type TYPE, which must be an integer or pointer type. The steps of the
1286 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1288 LOOP is the loop whose number of iterations we are determining.
1290 ONLY_EXIT is true if we are sure this is the only way the loop could be
1291 exited (including possibly non-returning function calls, exceptions, etc.)
1292 -- in this case we can use the information whether the control induction
1293 variables can overflow or not in a more efficient way.
1295 if EVERY_ITERATION is true, we know the test is executed on every iteration.
1297 The results (number of iterations and assumptions as described in
1298 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
1299 Returns false if it fails to determine number of iterations, true if it
1300 was determined (possibly with some assumptions). */
1303 number_of_iterations_cond (struct loop
*loop
,
1304 tree type
, affine_iv
*iv0
, enum tree_code code
,
1305 affine_iv
*iv1
, struct tree_niter_desc
*niter
,
1306 bool only_exit
, bool every_iteration
)
1308 bool exit_must_be_taken
= false, ret
;
1311 /* If the test is not executed every iteration, wrapping may make the test
1313 TODO: the overflow case can be still used as unreliable estimate of upper
1314 bound. But we have no API to pass it down to number of iterations code
1315 and, at present, it will not use it anyway. */
1316 if (!every_iteration
1317 && (!iv0
->no_overflow
|| !iv1
->no_overflow
1318 || code
== NE_EXPR
|| code
== EQ_EXPR
))
1321 /* The meaning of these assumptions is this:
1323 then the rest of information does not have to be valid
1324 if may_be_zero then the loop does not roll, even if
1326 niter
->assumptions
= boolean_true_node
;
1327 niter
->may_be_zero
= boolean_false_node
;
1328 niter
->niter
= NULL_TREE
;
1329 niter
->max
= double_int_zero
;
1331 niter
->bound
= NULL_TREE
;
1332 niter
->cmp
= ERROR_MARK
;
1334 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1335 the control variable is on lhs. */
1336 if (code
== GE_EXPR
|| code
== GT_EXPR
1337 || (code
== NE_EXPR
&& integer_zerop (iv0
->step
)))
1340 code
= swap_tree_comparison (code
);
1343 if (POINTER_TYPE_P (type
))
1345 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1346 to the same object. If they do, the control variable cannot wrap
1347 (as wrap around the bounds of memory will never return a pointer
1348 that would be guaranteed to point to the same object, even if we
1349 avoid undefined behavior by casting to size_t and back). */
1350 iv0
->no_overflow
= true;
1351 iv1
->no_overflow
= true;
1354 /* If the control induction variable does not overflow and the only exit
1355 from the loop is the one that we analyze, we know it must be taken
1359 if (!integer_zerop (iv0
->step
) && iv0
->no_overflow
)
1360 exit_must_be_taken
= true;
1361 else if (!integer_zerop (iv1
->step
) && iv1
->no_overflow
)
1362 exit_must_be_taken
= true;
1365 /* We can handle the case when neither of the sides of the comparison is
1366 invariant, provided that the test is NE_EXPR. This rarely occurs in
1367 practice, but it is simple enough to manage. */
1368 if (!integer_zerop (iv0
->step
) && !integer_zerop (iv1
->step
))
1370 tree step_type
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1371 if (code
!= NE_EXPR
)
1374 iv0
->step
= fold_binary_to_constant (MINUS_EXPR
, step_type
,
1375 iv0
->step
, iv1
->step
);
1376 iv0
->no_overflow
= false;
1377 iv1
->step
= build_int_cst (step_type
, 0);
1378 iv1
->no_overflow
= true;
1381 /* If the result of the comparison is a constant, the loop is weird. More
1382 precise handling would be possible, but the situation is not common enough
1383 to waste time on it. */
1384 if (integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
))
1387 /* Ignore loops of while (i-- < 10) type. */
1388 if (code
!= NE_EXPR
)
1390 if (iv0
->step
&& tree_int_cst_sign_bit (iv0
->step
))
1393 if (!integer_zerop (iv1
->step
) && !tree_int_cst_sign_bit (iv1
->step
))
1397 /* If the loop exits immediately, there is nothing to do. */
1398 tree tem
= fold_binary (code
, boolean_type_node
, iv0
->base
, iv1
->base
);
1399 if (tem
&& integer_zerop (tem
))
1401 niter
->niter
= build_int_cst (unsigned_type_for (type
), 0);
1402 niter
->max
= double_int_zero
;
1406 /* OK, now we know we have a senseful loop. Handle several cases, depending
1407 on what comparison operator is used. */
1408 bound_difference (loop
, iv1
->base
, iv0
->base
, &bnds
);
1410 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1413 "Analyzing # of iterations of loop %d\n", loop
->num
);
1415 fprintf (dump_file
, " exit condition ");
1416 dump_affine_iv (dump_file
, iv0
);
1417 fprintf (dump_file
, " %s ",
1418 code
== NE_EXPR
? "!="
1419 : code
== LT_EXPR
? "<"
1421 dump_affine_iv (dump_file
, iv1
);
1422 fprintf (dump_file
, "\n");
1424 fprintf (dump_file
, " bounds on difference of bases: ");
1425 mpz_out_str (dump_file
, 10, bnds
.below
);
1426 fprintf (dump_file
, " ... ");
1427 mpz_out_str (dump_file
, 10, bnds
.up
);
1428 fprintf (dump_file
, "\n");
1434 gcc_assert (integer_zerop (iv1
->step
));
1435 ret
= number_of_iterations_ne (type
, iv0
, iv1
->base
, niter
,
1436 exit_must_be_taken
, &bnds
);
1440 ret
= number_of_iterations_lt (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1445 ret
= number_of_iterations_le (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1453 mpz_clear (bnds
.up
);
1454 mpz_clear (bnds
.below
);
1456 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1460 fprintf (dump_file
, " result:\n");
1461 if (!integer_nonzerop (niter
->assumptions
))
1463 fprintf (dump_file
, " under assumptions ");
1464 print_generic_expr (dump_file
, niter
->assumptions
, TDF_SLIM
);
1465 fprintf (dump_file
, "\n");
1468 if (!integer_zerop (niter
->may_be_zero
))
1470 fprintf (dump_file
, " zero if ");
1471 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
1472 fprintf (dump_file
, "\n");
1475 fprintf (dump_file
, " # of iterations ");
1476 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
1477 fprintf (dump_file
, ", bounded by ");
1478 dump_double_int (dump_file
, niter
->max
, true);
1479 fprintf (dump_file
, "\n");
1482 fprintf (dump_file
, " failed\n\n");
1487 /* Substitute NEW for OLD in EXPR and fold the result. */
1490 simplify_replace_tree (tree expr
, tree old
, tree new_tree
)
1493 tree ret
= NULL_TREE
, e
, se
;
1498 /* Do not bother to replace constants. */
1499 if (CONSTANT_CLASS_P (old
))
1503 || operand_equal_p (expr
, old
, 0))
1504 return unshare_expr (new_tree
);
1509 n
= TREE_OPERAND_LENGTH (expr
);
1510 for (i
= 0; i
< n
; i
++)
1512 e
= TREE_OPERAND (expr
, i
);
1513 se
= simplify_replace_tree (e
, old
, new_tree
);
1518 ret
= copy_node (expr
);
1520 TREE_OPERAND (ret
, i
) = se
;
1523 return (ret
? fold (ret
) : expr
);
1526 /* Expand definitions of ssa names in EXPR as long as they are simple
1527 enough, and return the new expression. */
1530 expand_simple_operations (tree expr
)
1533 tree ret
= NULL_TREE
, e
, ee
, e1
;
1534 enum tree_code code
;
1537 if (expr
== NULL_TREE
)
1540 if (is_gimple_min_invariant (expr
))
1543 code
= TREE_CODE (expr
);
1544 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
1546 n
= TREE_OPERAND_LENGTH (expr
);
1547 for (i
= 0; i
< n
; i
++)
1549 e
= TREE_OPERAND (expr
, i
);
1550 ee
= expand_simple_operations (e
);
1555 ret
= copy_node (expr
);
1557 TREE_OPERAND (ret
, i
) = ee
;
1563 fold_defer_overflow_warnings ();
1565 fold_undefer_and_ignore_overflow_warnings ();
1569 if (TREE_CODE (expr
) != SSA_NAME
)
1572 stmt
= SSA_NAME_DEF_STMT (expr
);
1573 if (gimple_code (stmt
) == GIMPLE_PHI
)
1575 basic_block src
, dest
;
1577 if (gimple_phi_num_args (stmt
) != 1)
1579 e
= PHI_ARG_DEF (stmt
, 0);
1581 /* Avoid propagating through loop exit phi nodes, which
1582 could break loop-closed SSA form restrictions. */
1583 dest
= gimple_bb (stmt
);
1584 src
= single_pred (dest
);
1585 if (TREE_CODE (e
) == SSA_NAME
1586 && src
->loop_father
!= dest
->loop_father
)
1589 return expand_simple_operations (e
);
1591 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1594 /* Avoid expanding to expressions that contain SSA names that need
1595 to take part in abnormal coalescing. */
1597 FOR_EACH_SSA_TREE_OPERAND (e
, stmt
, iter
, SSA_OP_USE
)
1598 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (e
))
1601 e
= gimple_assign_rhs1 (stmt
);
1602 code
= gimple_assign_rhs_code (stmt
);
1603 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1605 if (is_gimple_min_invariant (e
))
1608 if (code
== SSA_NAME
)
1609 return expand_simple_operations (e
);
1617 /* Casts are simple. */
1618 ee
= expand_simple_operations (e
);
1619 return fold_build1 (code
, TREE_TYPE (expr
), ee
);
1623 case POINTER_PLUS_EXPR
:
1624 /* And increments and decrements by a constant are simple. */
1625 e1
= gimple_assign_rhs2 (stmt
);
1626 if (!is_gimple_min_invariant (e1
))
1629 ee
= expand_simple_operations (e
);
1630 return fold_build2 (code
, TREE_TYPE (expr
), ee
, e1
);
1637 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1638 expression (or EXPR unchanged, if no simplification was possible). */
1641 tree_simplify_using_condition_1 (tree cond
, tree expr
)
1644 tree e
, te
, e0
, e1
, e2
, notcond
;
1645 enum tree_code code
= TREE_CODE (expr
);
1647 if (code
== INTEGER_CST
)
1650 if (code
== TRUTH_OR_EXPR
1651 || code
== TRUTH_AND_EXPR
1652 || code
== COND_EXPR
)
1656 e0
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 0));
1657 if (TREE_OPERAND (expr
, 0) != e0
)
1660 e1
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 1));
1661 if (TREE_OPERAND (expr
, 1) != e1
)
1664 if (code
== COND_EXPR
)
1666 e2
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 2));
1667 if (TREE_OPERAND (expr
, 2) != e2
)
1675 if (code
== COND_EXPR
)
1676 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1678 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1684 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
1685 propagation, and vice versa. Fold does not handle this, since it is
1686 considered too expensive. */
1687 if (TREE_CODE (cond
) == EQ_EXPR
)
1689 e0
= TREE_OPERAND (cond
, 0);
1690 e1
= TREE_OPERAND (cond
, 1);
1692 /* We know that e0 == e1. Check whether we cannot simplify expr
1694 e
= simplify_replace_tree (expr
, e0
, e1
);
1695 if (integer_zerop (e
) || integer_nonzerop (e
))
1698 e
= simplify_replace_tree (expr
, e1
, e0
);
1699 if (integer_zerop (e
) || integer_nonzerop (e
))
1702 if (TREE_CODE (expr
) == EQ_EXPR
)
1704 e0
= TREE_OPERAND (expr
, 0);
1705 e1
= TREE_OPERAND (expr
, 1);
1707 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
1708 e
= simplify_replace_tree (cond
, e0
, e1
);
1709 if (integer_zerop (e
))
1711 e
= simplify_replace_tree (cond
, e1
, e0
);
1712 if (integer_zerop (e
))
1715 if (TREE_CODE (expr
) == NE_EXPR
)
1717 e0
= TREE_OPERAND (expr
, 0);
1718 e1
= TREE_OPERAND (expr
, 1);
1720 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
1721 e
= simplify_replace_tree (cond
, e0
, e1
);
1722 if (integer_zerop (e
))
1723 return boolean_true_node
;
1724 e
= simplify_replace_tree (cond
, e1
, e0
);
1725 if (integer_zerop (e
))
1726 return boolean_true_node
;
1729 te
= expand_simple_operations (expr
);
1731 /* Check whether COND ==> EXPR. */
1732 notcond
= invert_truthvalue (cond
);
1733 e
= fold_binary (TRUTH_OR_EXPR
, boolean_type_node
, notcond
, te
);
1734 if (e
&& integer_nonzerop (e
))
1737 /* Check whether COND ==> not EXPR. */
1738 e
= fold_binary (TRUTH_AND_EXPR
, boolean_type_node
, cond
, te
);
1739 if (e
&& integer_zerop (e
))
1745 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1746 expression (or EXPR unchanged, if no simplification was possible).
1747 Wrapper around tree_simplify_using_condition_1 that ensures that chains
1748 of simple operations in definitions of ssa names in COND are expanded,
1749 so that things like casts or incrementing the value of the bound before
1750 the loop do not cause us to fail. */
1753 tree_simplify_using_condition (tree cond
, tree expr
)
1755 cond
= expand_simple_operations (cond
);
1757 return tree_simplify_using_condition_1 (cond
, expr
);
1760 /* Tries to simplify EXPR using the conditions on entry to LOOP.
1761 Returns the simplified expression (or EXPR unchanged, if no
1762 simplification was possible).*/
1765 simplify_using_initial_conditions (struct loop
*loop
, tree expr
)
1773 if (TREE_CODE (expr
) == INTEGER_CST
)
1776 /* Limit walking the dominators to avoid quadraticness in
1777 the number of BBs times the number of loops in degenerate
1779 for (bb
= loop
->header
;
1780 bb
!= ENTRY_BLOCK_PTR
&& cnt
< MAX_DOMINATORS_TO_WALK
;
1781 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1783 if (!single_pred_p (bb
))
1785 e
= single_pred_edge (bb
);
1787 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
1790 stmt
= last_stmt (e
->src
);
1791 cond
= fold_build2 (gimple_cond_code (stmt
),
1793 gimple_cond_lhs (stmt
),
1794 gimple_cond_rhs (stmt
));
1795 if (e
->flags
& EDGE_FALSE_VALUE
)
1796 cond
= invert_truthvalue (cond
);
1797 expr
= tree_simplify_using_condition (cond
, expr
);
1804 /* Tries to simplify EXPR using the evolutions of the loop invariants
1805 in the superloops of LOOP. Returns the simplified expression
1806 (or EXPR unchanged, if no simplification was possible). */
1809 simplify_using_outer_evolutions (struct loop
*loop
, tree expr
)
1811 enum tree_code code
= TREE_CODE (expr
);
1815 if (is_gimple_min_invariant (expr
))
1818 if (code
== TRUTH_OR_EXPR
1819 || code
== TRUTH_AND_EXPR
1820 || code
== COND_EXPR
)
1824 e0
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 0));
1825 if (TREE_OPERAND (expr
, 0) != e0
)
1828 e1
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 1));
1829 if (TREE_OPERAND (expr
, 1) != e1
)
1832 if (code
== COND_EXPR
)
1834 e2
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 2));
1835 if (TREE_OPERAND (expr
, 2) != e2
)
1843 if (code
== COND_EXPR
)
1844 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1846 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1852 e
= instantiate_parameters (loop
, expr
);
1853 if (is_gimple_min_invariant (e
))
1859 /* Returns true if EXIT is the only possible exit from LOOP. */
1862 loop_only_exit_p (const struct loop
*loop
, const_edge exit
)
1865 gimple_stmt_iterator bsi
;
1869 if (exit
!= single_exit (loop
))
1872 body
= get_loop_body (loop
);
1873 for (i
= 0; i
< loop
->num_nodes
; i
++)
1875 for (bsi
= gsi_start_bb (body
[i
]); !gsi_end_p (bsi
); gsi_next (&bsi
))
1877 call
= gsi_stmt (bsi
);
1878 if (gimple_code (call
) != GIMPLE_CALL
)
1881 if (gimple_has_side_effects (call
))
1893 /* Stores description of number of iterations of LOOP derived from
1894 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
1895 useful information could be derived (and fields of NITER has
1896 meaning described in comments at struct tree_niter_desc
1897 declaration), false otherwise. If WARN is true and
1898 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1899 potentially unsafe assumptions.
1900 When EVERY_ITERATION is true, only tests that are known to be executed
1901 every iteration are considered (i.e. only test that alone bounds the loop).
1905 number_of_iterations_exit (struct loop
*loop
, edge exit
,
1906 struct tree_niter_desc
*niter
,
1907 bool warn
, bool every_iteration
)
1912 enum tree_code code
;
1916 safe
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit
->src
);
1918 if (every_iteration
&& !safe
)
1921 niter
->assumptions
= boolean_false_node
;
1922 stmt
= last_stmt (exit
->src
);
1923 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1926 /* We want the condition for staying inside loop. */
1927 code
= gimple_cond_code (stmt
);
1928 if (exit
->flags
& EDGE_TRUE_VALUE
)
1929 code
= invert_tree_comparison (code
, false);
1944 op0
= gimple_cond_lhs (stmt
);
1945 op1
= gimple_cond_rhs (stmt
);
1946 type
= TREE_TYPE (op0
);
1948 if (TREE_CODE (type
) != INTEGER_TYPE
1949 && !POINTER_TYPE_P (type
))
1952 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, false))
1954 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, false))
1957 /* We don't want to see undefined signed overflow warnings while
1958 computing the number of iterations. */
1959 fold_defer_overflow_warnings ();
1961 iv0
.base
= expand_simple_operations (iv0
.base
);
1962 iv1
.base
= expand_simple_operations (iv1
.base
);
1963 if (!number_of_iterations_cond (loop
, type
, &iv0
, code
, &iv1
, niter
,
1964 loop_only_exit_p (loop
, exit
), safe
))
1966 fold_undefer_and_ignore_overflow_warnings ();
1972 niter
->assumptions
= simplify_using_outer_evolutions (loop
,
1973 niter
->assumptions
);
1974 niter
->may_be_zero
= simplify_using_outer_evolutions (loop
,
1975 niter
->may_be_zero
);
1976 niter
->niter
= simplify_using_outer_evolutions (loop
, niter
->niter
);
1980 = simplify_using_initial_conditions (loop
,
1981 niter
->assumptions
);
1983 = simplify_using_initial_conditions (loop
,
1984 niter
->may_be_zero
);
1986 fold_undefer_and_ignore_overflow_warnings ();
1988 /* If NITER has simplified into a constant, update MAX. */
1989 if (TREE_CODE (niter
->niter
) == INTEGER_CST
)
1990 niter
->max
= tree_to_double_int (niter
->niter
);
1992 if (integer_onep (niter
->assumptions
))
1995 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1996 But if we can prove that there is overflow or some other source of weird
1997 behavior, ignore the loop even with -funsafe-loop-optimizations. */
1998 if (integer_zerop (niter
->assumptions
) || !single_exit (loop
))
2001 if (flag_unsafe_loop_optimizations
)
2002 niter
->assumptions
= boolean_true_node
;
2006 const char *wording
;
2007 location_t loc
= gimple_location (stmt
);
2009 /* We can provide a more specific warning if one of the operator is
2010 constant and the other advances by +1 or -1. */
2011 if (!integer_zerop (iv1
.step
)
2012 ? (integer_zerop (iv0
.step
)
2013 && (integer_onep (iv1
.step
) || integer_all_onesp (iv1
.step
)))
2014 : (integer_onep (iv0
.step
) || integer_all_onesp (iv0
.step
)))
2016 flag_unsafe_loop_optimizations
2017 ? N_("assuming that the loop is not infinite")
2018 : N_("cannot optimize possibly infinite loops");
2021 flag_unsafe_loop_optimizations
2022 ? N_("assuming that the loop counter does not overflow")
2023 : N_("cannot optimize loop, the loop counter may overflow");
2025 warning_at ((LOCATION_LINE (loc
) > 0) ? loc
: input_location
,
2026 OPT_Wunsafe_loop_optimizations
, "%s", gettext (wording
));
2029 return flag_unsafe_loop_optimizations
;
2032 /* Try to determine the number of iterations of LOOP. If we succeed,
2033 expression giving number of iterations is returned and *EXIT is
2034 set to the edge from that the information is obtained. Otherwise
2035 chrec_dont_know is returned. */
2038 find_loop_niter (struct loop
*loop
, edge
*exit
)
2041 vec
<edge
> exits
= get_loop_exit_edges (loop
);
2043 tree niter
= NULL_TREE
, aniter
;
2044 struct tree_niter_desc desc
;
2047 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2049 if (!number_of_iterations_exit (loop
, ex
, &desc
, false))
2052 if (integer_nonzerop (desc
.may_be_zero
))
2054 /* We exit in the first iteration through this exit.
2055 We won't find anything better. */
2056 niter
= build_int_cst (unsigned_type_node
, 0);
2061 if (!integer_zerop (desc
.may_be_zero
))
2064 aniter
= desc
.niter
;
2068 /* Nothing recorded yet. */
2074 /* Prefer constants, the lower the better. */
2075 if (TREE_CODE (aniter
) != INTEGER_CST
)
2078 if (TREE_CODE (niter
) != INTEGER_CST
)
2085 if (tree_int_cst_lt (aniter
, niter
))
2094 return niter
? niter
: chrec_dont_know
;
2097 /* Return true if loop is known to have bounded number of iterations. */
2100 finite_loop_p (struct loop
*loop
)
2105 if (flag_unsafe_loop_optimizations
)
2107 flags
= flags_from_decl_or_type (current_function_decl
);
2108 if ((flags
& (ECF_CONST
|ECF_PURE
)) && !(flags
& ECF_LOOPING_CONST_OR_PURE
))
2110 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2111 fprintf (dump_file
, "Found loop %i to be finite: it is within pure or const function.\n",
2116 if (loop
->any_upper_bound
2117 || max_loop_iterations (loop
, &nit
))
2119 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2120 fprintf (dump_file
, "Found loop %i to be finite: upper bound found.\n",
2129 Analysis of a number of iterations of a loop by a brute-force evaluation.
2133 /* Bound on the number of iterations we try to evaluate. */
2135 #define MAX_ITERATIONS_TO_TRACK \
2136 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
2138 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
2139 result by a chain of operations such that all but exactly one of their
2140 operands are constants. */
2143 chain_of_csts_start (struct loop
*loop
, tree x
)
2145 gimple stmt
= SSA_NAME_DEF_STMT (x
);
2147 basic_block bb
= gimple_bb (stmt
);
2148 enum tree_code code
;
2151 || !flow_bb_inside_loop_p (loop
, bb
))
2154 if (gimple_code (stmt
) == GIMPLE_PHI
)
2156 if (bb
== loop
->header
)
2162 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2165 code
= gimple_assign_rhs_code (stmt
);
2166 if (gimple_references_memory_p (stmt
)
2167 || TREE_CODE_CLASS (code
) == tcc_reference
2168 || (code
== ADDR_EXPR
2169 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
2172 use
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
2173 if (use
== NULL_TREE
)
2176 return chain_of_csts_start (loop
, use
);
2179 /* Determines whether the expression X is derived from a result of a phi node
2180 in header of LOOP such that
2182 * the derivation of X consists only from operations with constants
2183 * the initial value of the phi node is constant
2184 * the value of the phi node in the next iteration can be derived from the
2185 value in the current iteration by a chain of operations with constants.
2187 If such phi node exists, it is returned, otherwise NULL is returned. */
2190 get_base_for (struct loop
*loop
, tree x
)
2195 if (is_gimple_min_invariant (x
))
2198 phi
= chain_of_csts_start (loop
, x
);
2202 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2203 next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2205 if (TREE_CODE (next
) != SSA_NAME
)
2208 if (!is_gimple_min_invariant (init
))
2211 if (chain_of_csts_start (loop
, next
) != phi
)
2217 /* Given an expression X, then
2219 * if X is NULL_TREE, we return the constant BASE.
2220 * otherwise X is a SSA name, whose value in the considered loop is derived
2221 by a chain of operations with constant from a result of a phi node in
2222 the header of the loop. Then we return value of X when the value of the
2223 result of this phi node is given by the constant BASE. */
2226 get_val_for (tree x
, tree base
)
2230 gcc_assert (is_gimple_min_invariant (base
));
2235 stmt
= SSA_NAME_DEF_STMT (x
);
2236 if (gimple_code (stmt
) == GIMPLE_PHI
)
2239 gcc_assert (is_gimple_assign (stmt
));
2241 /* STMT must be either an assignment of a single SSA name or an
2242 expression involving an SSA name and a constant. Try to fold that
2243 expression using the value for the SSA name. */
2244 if (gimple_assign_ssa_name_copy_p (stmt
))
2245 return get_val_for (gimple_assign_rhs1 (stmt
), base
);
2246 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_UNARY_RHS
2247 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
2249 return fold_build1 (gimple_assign_rhs_code (stmt
),
2250 gimple_expr_type (stmt
),
2251 get_val_for (gimple_assign_rhs1 (stmt
), base
));
2253 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_BINARY_RHS
)
2255 tree rhs1
= gimple_assign_rhs1 (stmt
);
2256 tree rhs2
= gimple_assign_rhs2 (stmt
);
2257 if (TREE_CODE (rhs1
) == SSA_NAME
)
2258 rhs1
= get_val_for (rhs1
, base
);
2259 else if (TREE_CODE (rhs2
) == SSA_NAME
)
2260 rhs2
= get_val_for (rhs2
, base
);
2263 return fold_build2 (gimple_assign_rhs_code (stmt
),
2264 gimple_expr_type (stmt
), rhs1
, rhs2
);
2271 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2272 by brute force -- i.e. by determining the value of the operands of the
2273 condition at EXIT in first few iterations of the loop (assuming that
2274 these values are constant) and determining the first one in that the
2275 condition is not satisfied. Returns the constant giving the number
2276 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
2279 loop_niter_by_eval (struct loop
*loop
, edge exit
)
2282 tree op
[2], val
[2], next
[2], aval
[2];
2287 cond
= last_stmt (exit
->src
);
2288 if (!cond
|| gimple_code (cond
) != GIMPLE_COND
)
2289 return chrec_dont_know
;
2291 cmp
= gimple_cond_code (cond
);
2292 if (exit
->flags
& EDGE_TRUE_VALUE
)
2293 cmp
= invert_tree_comparison (cmp
, false);
2303 op
[0] = gimple_cond_lhs (cond
);
2304 op
[1] = gimple_cond_rhs (cond
);
2308 return chrec_dont_know
;
2311 for (j
= 0; j
< 2; j
++)
2313 if (is_gimple_min_invariant (op
[j
]))
2316 next
[j
] = NULL_TREE
;
2321 phi
= get_base_for (loop
, op
[j
]);
2323 return chrec_dont_know
;
2324 val
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2325 next
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2329 /* Don't issue signed overflow warnings. */
2330 fold_defer_overflow_warnings ();
2332 for (i
= 0; i
< MAX_ITERATIONS_TO_TRACK
; i
++)
2334 for (j
= 0; j
< 2; j
++)
2335 aval
[j
] = get_val_for (op
[j
], val
[j
]);
2337 acnd
= fold_binary (cmp
, boolean_type_node
, aval
[0], aval
[1]);
2338 if (acnd
&& integer_zerop (acnd
))
2340 fold_undefer_and_ignore_overflow_warnings ();
2341 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2343 "Proved that loop %d iterates %d times using brute force.\n",
2345 return build_int_cst (unsigned_type_node
, i
);
2348 for (j
= 0; j
< 2; j
++)
2350 val
[j
] = get_val_for (next
[j
], val
[j
]);
2351 if (!is_gimple_min_invariant (val
[j
]))
2353 fold_undefer_and_ignore_overflow_warnings ();
2354 return chrec_dont_know
;
2359 fold_undefer_and_ignore_overflow_warnings ();
2361 return chrec_dont_know
;
2364 /* Finds the exit of the LOOP by that the loop exits after a constant
2365 number of iterations and stores the exit edge to *EXIT. The constant
2366 giving the number of iterations of LOOP is returned. The number of
2367 iterations is determined using loop_niter_by_eval (i.e. by brute force
2368 evaluation). If we are unable to find the exit for that loop_niter_by_eval
2369 determines the number of iterations, chrec_dont_know is returned. */
2372 find_loop_niter_by_eval (struct loop
*loop
, edge
*exit
)
2375 vec
<edge
> exits
= get_loop_exit_edges (loop
);
2377 tree niter
= NULL_TREE
, aniter
;
2381 /* Loops with multiple exits are expensive to handle and less important. */
2382 if (!flag_expensive_optimizations
2383 && exits
.length () > 1)
2386 return chrec_dont_know
;
2389 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2391 if (!just_once_each_iteration_p (loop
, ex
->src
))
2394 aniter
= loop_niter_by_eval (loop
, ex
);
2395 if (chrec_contains_undetermined (aniter
))
2399 && !tree_int_cst_lt (aniter
, niter
))
2407 return niter
? niter
: chrec_dont_know
;
2412 Analysis of upper bounds on number of iterations of a loop.
2416 static double_int
derive_constant_upper_bound_ops (tree
, tree
,
2417 enum tree_code
, tree
);
2419 /* Returns a constant upper bound on the value of the right-hand side of
2420 an assignment statement STMT. */
2423 derive_constant_upper_bound_assign (gimple stmt
)
2425 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2426 tree op0
= gimple_assign_rhs1 (stmt
);
2427 tree op1
= gimple_assign_rhs2 (stmt
);
2429 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt
)),
2433 /* Returns a constant upper bound on the value of expression VAL. VAL
2434 is considered to be unsigned. If its type is signed, its value must
2438 derive_constant_upper_bound (tree val
)
2440 enum tree_code code
;
2443 extract_ops_from_tree (val
, &code
, &op0
, &op1
);
2444 return derive_constant_upper_bound_ops (TREE_TYPE (val
), op0
, code
, op1
);
2447 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
2448 whose type is TYPE. The expression is considered to be unsigned. If
2449 its type is signed, its value must be nonnegative. */
2452 derive_constant_upper_bound_ops (tree type
, tree op0
,
2453 enum tree_code code
, tree op1
)
2456 double_int bnd
, max
, mmax
, cst
;
2459 if (INTEGRAL_TYPE_P (type
))
2460 maxt
= TYPE_MAX_VALUE (type
);
2462 maxt
= upper_bound_in_type (type
, type
);
2464 max
= tree_to_double_int (maxt
);
2469 return tree_to_double_int (op0
);
2472 subtype
= TREE_TYPE (op0
);
2473 if (!TYPE_UNSIGNED (subtype
)
2474 /* If TYPE is also signed, the fact that VAL is nonnegative implies
2475 that OP0 is nonnegative. */
2476 && TYPE_UNSIGNED (type
)
2477 && !tree_expr_nonnegative_p (op0
))
2479 /* If we cannot prove that the casted expression is nonnegative,
2480 we cannot establish more useful upper bound than the precision
2481 of the type gives us. */
2485 /* We now know that op0 is an nonnegative value. Try deriving an upper
2487 bnd
= derive_constant_upper_bound (op0
);
2489 /* If the bound does not fit in TYPE, max. value of TYPE could be
2497 case POINTER_PLUS_EXPR
:
2499 if (TREE_CODE (op1
) != INTEGER_CST
2500 || !tree_expr_nonnegative_p (op0
))
2503 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
2504 choose the most logical way how to treat this constant regardless
2505 of the signedness of the type. */
2506 cst
= tree_to_double_int (op1
);
2507 cst
= cst
.sext (TYPE_PRECISION (type
));
2508 if (code
!= MINUS_EXPR
)
2511 bnd
= derive_constant_upper_bound (op0
);
2513 if (cst
.is_negative ())
2516 /* Avoid CST == 0x80000... */
2517 if (cst
.is_negative ())
2520 /* OP0 + CST. We need to check that
2521 BND <= MAX (type) - CST. */
2531 /* OP0 - CST, where CST >= 0.
2533 If TYPE is signed, we have already verified that OP0 >= 0, and we
2534 know that the result is nonnegative. This implies that
2537 If TYPE is unsigned, we must additionally know that OP0 >= CST,
2538 otherwise the operation underflows.
2541 /* This should only happen if the type is unsigned; however, for
2542 buggy programs that use overflowing signed arithmetics even with
2543 -fno-wrapv, this condition may also be true for signed values. */
2547 if (TYPE_UNSIGNED (type
))
2549 tree tem
= fold_binary (GE_EXPR
, boolean_type_node
, op0
,
2550 double_int_to_tree (type
, cst
));
2551 if (!tem
|| integer_nonzerop (tem
))
2560 case FLOOR_DIV_EXPR
:
2561 case EXACT_DIV_EXPR
:
2562 if (TREE_CODE (op1
) != INTEGER_CST
2563 || tree_int_cst_sign_bit (op1
))
2566 bnd
= derive_constant_upper_bound (op0
);
2567 return bnd
.udiv (tree_to_double_int (op1
), FLOOR_DIV_EXPR
);
2570 if (TREE_CODE (op1
) != INTEGER_CST
2571 || tree_int_cst_sign_bit (op1
))
2573 return tree_to_double_int (op1
);
2576 stmt
= SSA_NAME_DEF_STMT (op0
);
2577 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2578 || gimple_assign_lhs (stmt
) != op0
)
2580 return derive_constant_upper_bound_assign (stmt
);
2587 /* Emit a -Waggressive-loop-optimizations warning if needed. */
2590 do_warn_aggressive_loop_optimizations (struct loop
*loop
,
2591 double_int i_bound
, gimple stmt
)
2593 /* Don't warn if the loop doesn't have known constant bound. */
2594 if (!loop
->nb_iterations
2595 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
2596 || !warn_aggressive_loop_optimizations
2597 /* To avoid warning multiple times for the same loop,
2598 only start warning when we preserve loops. */
2599 || (cfun
->curr_properties
& PROP_loops
) == 0
2600 /* Only warn once per loop. */
2601 || loop
->warned_aggressive_loop_optimizations
2602 /* Only warn if undefined behavior gives us lower estimate than the
2603 known constant bound. */
2604 || i_bound
.ucmp (tree_to_double_int (loop
->nb_iterations
)) >= 0
2605 /* And undefined behavior happens unconditionally. */
2606 || !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (stmt
)))
2609 edge e
= single_exit (loop
);
2613 gimple estmt
= last_stmt (e
->src
);
2614 if (warning_at (gimple_location (stmt
), OPT_Waggressive_loop_optimizations
,
2615 "iteration %E invokes undefined behavior",
2616 double_int_to_tree (TREE_TYPE (loop
->nb_iterations
),
2618 inform (gimple_location (estmt
), "containing loop");
2619 loop
->warned_aggressive_loop_optimizations
= true;
2622 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
2623 is true if the loop is exited immediately after STMT, and this exit
2624 is taken at last when the STMT is executed BOUND + 1 times.
2625 REALISTIC is true if BOUND is expected to be close to the real number
2626 of iterations. UPPER is true if we are sure the loop iterates at most
2627 BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */
2630 record_estimate (struct loop
*loop
, tree bound
, double_int i_bound
,
2631 gimple at_stmt
, bool is_exit
, bool realistic
, bool upper
)
2635 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2637 fprintf (dump_file
, "Statement %s", is_exit
? "(exit)" : "");
2638 print_gimple_stmt (dump_file
, at_stmt
, 0, TDF_SLIM
);
2639 fprintf (dump_file
, " is %sexecuted at most ",
2640 upper
? "" : "probably ");
2641 print_generic_expr (dump_file
, bound
, TDF_SLIM
);
2642 fprintf (dump_file
, " (bounded by ");
2643 dump_double_int (dump_file
, i_bound
, true);
2644 fprintf (dump_file
, ") + 1 times in loop %d.\n", loop
->num
);
2647 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
2648 real number of iterations. */
2649 if (TREE_CODE (bound
) != INTEGER_CST
)
2652 gcc_checking_assert (i_bound
== tree_to_double_int (bound
));
2653 if (!upper
&& !realistic
)
2656 /* If we have a guaranteed upper bound, record it in the appropriate
2657 list, unless this is an !is_exit bound (i.e. undefined behavior in
2658 at_stmt) in a loop with known constant number of iterations. */
2661 || loop
->nb_iterations
== NULL_TREE
2662 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
))
2664 struct nb_iter_bound
*elt
= ggc_alloc_nb_iter_bound ();
2666 elt
->bound
= i_bound
;
2667 elt
->stmt
= at_stmt
;
2668 elt
->is_exit
= is_exit
;
2669 elt
->next
= loop
->bounds
;
2673 /* If statement is executed on every path to the loop latch, we can directly
2674 infer the upper bound on the # of iterations of the loop. */
2675 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (at_stmt
)))
2678 /* Update the number of iteration estimates according to the bound.
2679 If at_stmt is an exit then the loop latch is executed at most BOUND times,
2680 otherwise it can be executed BOUND + 1 times. We will lower the estimate
2681 later if such statement must be executed on last iteration */
2683 delta
= double_int_zero
;
2685 delta
= double_int_one
;
2688 /* If an overflow occurred, ignore the result. */
2689 if (i_bound
.ult (delta
))
2692 if (upper
&& !is_exit
)
2693 do_warn_aggressive_loop_optimizations (loop
, i_bound
, at_stmt
);
2694 record_niter_bound (loop
, i_bound
, realistic
, upper
);
2697 /* Record the estimate on number of iterations of LOOP based on the fact that
2698 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
2699 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
2700 estimated number of iterations is expected to be close to the real one.
2701 UPPER is true if we are sure the induction variable does not wrap. */
2704 record_nonwrapping_iv (struct loop
*loop
, tree base
, tree step
, gimple stmt
,
2705 tree low
, tree high
, bool realistic
, bool upper
)
2707 tree niter_bound
, extreme
, delta
;
2708 tree type
= TREE_TYPE (base
), unsigned_type
;
2711 if (TREE_CODE (step
) != INTEGER_CST
|| integer_zerop (step
))
2714 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2716 fprintf (dump_file
, "Induction variable (");
2717 print_generic_expr (dump_file
, TREE_TYPE (base
), TDF_SLIM
);
2718 fprintf (dump_file
, ") ");
2719 print_generic_expr (dump_file
, base
, TDF_SLIM
);
2720 fprintf (dump_file
, " + ");
2721 print_generic_expr (dump_file
, step
, TDF_SLIM
);
2722 fprintf (dump_file
, " * iteration does not wrap in statement ");
2723 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2724 fprintf (dump_file
, " in loop %d.\n", loop
->num
);
2727 unsigned_type
= unsigned_type_for (type
);
2728 base
= fold_convert (unsigned_type
, base
);
2729 step
= fold_convert (unsigned_type
, step
);
2731 if (tree_int_cst_sign_bit (step
))
2733 extreme
= fold_convert (unsigned_type
, low
);
2734 if (TREE_CODE (base
) != INTEGER_CST
)
2735 base
= fold_convert (unsigned_type
, high
);
2736 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
2737 step
= fold_build1 (NEGATE_EXPR
, unsigned_type
, step
);
2741 extreme
= fold_convert (unsigned_type
, high
);
2742 if (TREE_CODE (base
) != INTEGER_CST
)
2743 base
= fold_convert (unsigned_type
, low
);
2744 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
2747 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
2748 would get out of the range. */
2749 niter_bound
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step
);
2750 max
= derive_constant_upper_bound (niter_bound
);
2751 record_estimate (loop
, niter_bound
, max
, stmt
, false, realistic
, upper
);
2754 /* Determine information about number of iterations a LOOP from the index
2755 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
2756 guaranteed to be executed in every iteration of LOOP. Callback for
2766 idx_infer_loop_bounds (tree base
, tree
*idx
, void *dta
)
2768 struct ilb_data
*data
= (struct ilb_data
*) dta
;
2769 tree ev
, init
, step
;
2770 tree low
, high
, type
, next
;
2771 bool sign
, upper
= true, at_end
= false;
2772 struct loop
*loop
= data
->loop
;
2773 bool reliable
= true;
2775 if (TREE_CODE (base
) != ARRAY_REF
)
2778 /* For arrays at the end of the structure, we are not guaranteed that they
2779 do not really extend over their declared size. However, for arrays of
2780 size greater than one, this is unlikely to be intended. */
2781 if (array_at_struct_end_p (base
))
2787 struct loop
*dloop
= loop_containing_stmt (data
->stmt
);
2791 ev
= analyze_scalar_evolution (dloop
, *idx
);
2792 ev
= instantiate_parameters (loop
, ev
);
2793 init
= initial_condition (ev
);
2794 step
= evolution_part_in_loop_num (ev
, loop
->num
);
2798 || TREE_CODE (step
) != INTEGER_CST
2799 || integer_zerop (step
)
2800 || tree_contains_chrecs (init
, NULL
)
2801 || chrec_contains_symbols_defined_in_loop (init
, loop
->num
))
2804 low
= array_ref_low_bound (base
);
2805 high
= array_ref_up_bound (base
);
2807 /* The case of nonconstant bounds could be handled, but it would be
2809 if (TREE_CODE (low
) != INTEGER_CST
2811 || TREE_CODE (high
) != INTEGER_CST
)
2813 sign
= tree_int_cst_sign_bit (step
);
2814 type
= TREE_TYPE (step
);
2816 /* The array of length 1 at the end of a structure most likely extends
2817 beyond its bounds. */
2819 && operand_equal_p (low
, high
, 0))
2822 /* In case the relevant bound of the array does not fit in type, or
2823 it does, but bound + step (in type) still belongs into the range of the
2824 array, the index may wrap and still stay within the range of the array
2825 (consider e.g. if the array is indexed by the full range of
2828 To make things simpler, we require both bounds to fit into type, although
2829 there are cases where this would not be strictly necessary. */
2830 if (!int_fits_type_p (high
, type
)
2831 || !int_fits_type_p (low
, type
))
2833 low
= fold_convert (type
, low
);
2834 high
= fold_convert (type
, high
);
2837 next
= fold_binary (PLUS_EXPR
, type
, low
, step
);
2839 next
= fold_binary (PLUS_EXPR
, type
, high
, step
);
2841 if (tree_int_cst_compare (low
, next
) <= 0
2842 && tree_int_cst_compare (next
, high
) <= 0)
2845 /* If access is not executed on every iteration, we must ensure that overlow may
2846 not make the access valid later. */
2847 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (data
->stmt
))
2848 && scev_probably_wraps_p (initial_condition_in_loop_num (ev
, loop
->num
),
2849 step
, data
->stmt
, loop
, true))
2852 record_nonwrapping_iv (loop
, init
, step
, data
->stmt
, low
, high
, reliable
, upper
);
2856 /* Determine information about number of iterations a LOOP from the bounds
2857 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
2858 STMT is guaranteed to be executed in every iteration of LOOP.*/
2861 infer_loop_bounds_from_ref (struct loop
*loop
, gimple stmt
, tree ref
)
2863 struct ilb_data data
;
2867 for_each_index (&ref
, idx_infer_loop_bounds
, &data
);
2870 /* Determine information about number of iterations of a LOOP from the way
2871 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
2872 executed in every iteration of LOOP. */
2875 infer_loop_bounds_from_array (struct loop
*loop
, gimple stmt
)
2877 if (is_gimple_assign (stmt
))
2879 tree op0
= gimple_assign_lhs (stmt
);
2880 tree op1
= gimple_assign_rhs1 (stmt
);
2882 /* For each memory access, analyze its access function
2883 and record a bound on the loop iteration domain. */
2884 if (REFERENCE_CLASS_P (op0
))
2885 infer_loop_bounds_from_ref (loop
, stmt
, op0
);
2887 if (REFERENCE_CLASS_P (op1
))
2888 infer_loop_bounds_from_ref (loop
, stmt
, op1
);
2890 else if (is_gimple_call (stmt
))
2893 unsigned i
, n
= gimple_call_num_args (stmt
);
2895 lhs
= gimple_call_lhs (stmt
);
2896 if (lhs
&& REFERENCE_CLASS_P (lhs
))
2897 infer_loop_bounds_from_ref (loop
, stmt
, lhs
);
2899 for (i
= 0; i
< n
; i
++)
2901 arg
= gimple_call_arg (stmt
, i
);
2902 if (REFERENCE_CLASS_P (arg
))
2903 infer_loop_bounds_from_ref (loop
, stmt
, arg
);
2908 /* Determine information about number of iterations of a LOOP from the fact
2909 that pointer arithmetics in STMT does not overflow. */
2912 infer_loop_bounds_from_pointer_arith (struct loop
*loop
, gimple stmt
)
2914 tree def
, base
, step
, scev
, type
, low
, high
;
2917 if (!is_gimple_assign (stmt
)
2918 || gimple_assign_rhs_code (stmt
) != POINTER_PLUS_EXPR
)
2921 def
= gimple_assign_lhs (stmt
);
2922 if (TREE_CODE (def
) != SSA_NAME
)
2925 type
= TREE_TYPE (def
);
2926 if (!nowrap_type_p (type
))
2929 ptr
= gimple_assign_rhs1 (stmt
);
2930 if (!expr_invariant_in_loop_p (loop
, ptr
))
2933 var
= gimple_assign_rhs2 (stmt
);
2934 if (TYPE_PRECISION (type
) != TYPE_PRECISION (TREE_TYPE (var
)))
2937 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
2938 if (chrec_contains_undetermined (scev
))
2941 base
= initial_condition_in_loop_num (scev
, loop
->num
);
2942 step
= evolution_part_in_loop_num (scev
, loop
->num
);
2945 || TREE_CODE (step
) != INTEGER_CST
2946 || tree_contains_chrecs (base
, NULL
)
2947 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
2950 low
= lower_bound_in_type (type
, type
);
2951 high
= upper_bound_in_type (type
, type
);
2953 /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
2954 produce a NULL pointer. The contrary would mean NULL points to an object,
2955 while NULL is supposed to compare unequal with the address of all objects.
2956 Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
2957 NULL pointer since that would mean wrapping, which we assume here not to
2958 happen. So, we can exclude NULL from the valid range of pointer
2960 if (flag_delete_null_pointer_checks
&& int_cst_value (low
) == 0)
2961 low
= build_int_cstu (TREE_TYPE (low
), TYPE_ALIGN_UNIT (TREE_TYPE (type
)));
2963 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
2966 /* Determine information about number of iterations of a LOOP from the fact
2967 that signed arithmetics in STMT does not overflow. */
2970 infer_loop_bounds_from_signedness (struct loop
*loop
, gimple stmt
)
2972 tree def
, base
, step
, scev
, type
, low
, high
;
2974 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2977 def
= gimple_assign_lhs (stmt
);
2979 if (TREE_CODE (def
) != SSA_NAME
)
2982 type
= TREE_TYPE (def
);
2983 if (!INTEGRAL_TYPE_P (type
)
2984 || !TYPE_OVERFLOW_UNDEFINED (type
))
2987 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
2988 if (chrec_contains_undetermined (scev
))
2991 base
= initial_condition_in_loop_num (scev
, loop
->num
);
2992 step
= evolution_part_in_loop_num (scev
, loop
->num
);
2995 || TREE_CODE (step
) != INTEGER_CST
2996 || tree_contains_chrecs (base
, NULL
)
2997 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
3000 low
= lower_bound_in_type (type
, type
);
3001 high
= upper_bound_in_type (type
, type
);
3003 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
3006 /* The following analyzers are extracting informations on the bounds
3007 of LOOP from the following undefined behaviors:
3009 - data references should not access elements over the statically
3012 - signed variables should not overflow when flag_wrapv is not set.
3016 infer_loop_bounds_from_undefined (struct loop
*loop
)
3020 gimple_stmt_iterator bsi
;
3024 bbs
= get_loop_body (loop
);
3026 for (i
= 0; i
< loop
->num_nodes
; i
++)
3030 /* If BB is not executed in each iteration of the loop, we cannot
3031 use the operations in it to infer reliable upper bound on the
3032 # of iterations of the loop. However, we can use it as a guess.
3033 Reliable guesses come only from array bounds. */
3034 reliable
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
);
3036 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
3038 gimple stmt
= gsi_stmt (bsi
);
3040 infer_loop_bounds_from_array (loop
, stmt
);
3044 infer_loop_bounds_from_signedness (loop
, stmt
);
3045 infer_loop_bounds_from_pointer_arith (loop
, stmt
);
3056 /* Compare double ints, callback for qsort. */
3059 double_int_cmp (const void *p1
, const void *p2
)
3061 const double_int
*d1
= (const double_int
*)p1
;
3062 const double_int
*d2
= (const double_int
*)p2
;
3070 /* Return index of BOUND in BOUNDS array sorted in increasing order.
3071 Lookup by binary search. */
3074 bound_index (vec
<double_int
> bounds
, double_int bound
)
3076 unsigned int end
= bounds
.length ();
3077 unsigned int begin
= 0;
3079 /* Find a matching index by means of a binary search. */
3080 while (begin
!= end
)
3082 unsigned int middle
= (begin
+ end
) / 2;
3083 double_int index
= bounds
[middle
];
3087 else if (index
.ult (bound
))
3095 /* We recorded loop bounds only for statements dominating loop latch (and thus
3096 executed each loop iteration). If there are any bounds on statements not
3097 dominating the loop latch we can improve the estimate by walking the loop
3098 body and seeing if every path from loop header to loop latch contains
3099 some bounded statement. */
3102 discover_iteration_bound_by_body_walk (struct loop
*loop
)
3104 pointer_map_t
*bb_bounds
;
3105 struct nb_iter_bound
*elt
;
3106 vec
<double_int
> bounds
= vNULL
;
3107 vec
<vec
<basic_block
> > queues
= vNULL
;
3108 vec
<basic_block
> queue
= vNULL
;
3109 ptrdiff_t queue_index
;
3110 ptrdiff_t latch_index
= 0;
3111 pointer_map_t
*block_priority
;
3113 /* Discover what bounds may interest us. */
3114 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3116 double_int bound
= elt
->bound
;
3118 /* Exit terminates loop at given iteration, while non-exits produce undefined
3119 effect on the next iteration. */
3122 bound
+= double_int_one
;
3123 /* If an overflow occurred, ignore the result. */
3124 if (bound
.is_zero ())
3128 if (!loop
->any_upper_bound
3129 || bound
.ult (loop
->nb_iterations_upper_bound
))
3130 bounds
.safe_push (bound
);
3133 /* Exit early if there is nothing to do. */
3134 if (!bounds
.exists ())
3137 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3138 fprintf (dump_file
, " Trying to walk loop body to reduce the bound.\n");
3140 /* Sort the bounds in decreasing order. */
3141 qsort (bounds
.address (), bounds
.length (),
3142 sizeof (double_int
), double_int_cmp
);
3144 /* For every basic block record the lowest bound that is guaranteed to
3145 terminate the loop. */
3147 bb_bounds
= pointer_map_create ();
3148 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3150 double_int bound
= elt
->bound
;
3153 bound
+= double_int_one
;
3154 /* If an overflow occurred, ignore the result. */
3155 if (bound
.is_zero ())
3159 if (!loop
->any_upper_bound
3160 || bound
.ult (loop
->nb_iterations_upper_bound
))
3162 ptrdiff_t index
= bound_index (bounds
, bound
);
3163 void **entry
= pointer_map_contains (bb_bounds
,
3164 gimple_bb (elt
->stmt
));
3166 *pointer_map_insert (bb_bounds
,
3167 gimple_bb (elt
->stmt
)) = (void *)index
;
3168 else if ((ptrdiff_t)*entry
> index
)
3169 *entry
= (void *)index
;
3173 block_priority
= pointer_map_create ();
3175 /* Perform shortest path discovery loop->header ... loop->latch.
3177 The "distance" is given by the smallest loop bound of basic block
3178 present in the path and we look for path with largest smallest bound
3181 To avoid the need for fibonacci heap on double ints we simply compress
3182 double ints into indexes to BOUNDS array and then represent the queue
3183 as arrays of queues for every index.
3184 Index of BOUNDS.length() means that the execution of given BB has
3185 no bounds determined.
3187 VISITED is a pointer map translating basic block into smallest index
3188 it was inserted into the priority queue with. */
3191 /* Start walk in loop header with index set to infinite bound. */
3192 queue_index
= bounds
.length ();
3193 queues
.safe_grow_cleared (queue_index
+ 1);
3194 queue
.safe_push (loop
->header
);
3195 queues
[queue_index
] = queue
;
3196 *pointer_map_insert (block_priority
, loop
->header
) = (void *)queue_index
;
3198 for (; queue_index
>= 0; queue_index
--)
3200 if (latch_index
< queue_index
)
3202 while (queues
[queue_index
].length ())
3205 ptrdiff_t bound_index
= queue_index
;
3210 queue
= queues
[queue_index
];
3213 /* OK, we later inserted the BB with lower priority, skip it. */
3214 if ((ptrdiff_t)*pointer_map_contains (block_priority
, bb
) > queue_index
)
3217 /* See if we can improve the bound. */
3218 entry
= pointer_map_contains (bb_bounds
, bb
);
3219 if (entry
&& (ptrdiff_t)*entry
< bound_index
)
3220 bound_index
= (ptrdiff_t)*entry
;
3222 /* Insert succesors into the queue, watch for latch edge
3223 and record greatest index we saw. */
3224 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3226 bool insert
= false;
3229 if (loop_exit_edge_p (loop
, e
))
3232 if (e
== loop_latch_edge (loop
)
3233 && latch_index
< bound_index
)
3234 latch_index
= bound_index
;
3235 else if (!(entry
= pointer_map_contains (block_priority
, e
->dest
)))
3238 *pointer_map_insert (block_priority
, e
->dest
) = (void *)bound_index
;
3240 else if ((ptrdiff_t)*entry
< bound_index
)
3243 *entry
= (void *)bound_index
;
3247 queues
[bound_index
].safe_push (e
->dest
);
3251 queues
[queue_index
].release ();
3254 gcc_assert (latch_index
>= 0);
3255 if ((unsigned)latch_index
< bounds
.length ())
3257 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3259 fprintf (dump_file
, "Found better loop bound ");
3260 dump_double_int (dump_file
, bounds
[latch_index
], true);
3261 fprintf (dump_file
, "\n");
3263 record_niter_bound (loop
, bounds
[latch_index
], false, true);
3268 pointer_map_destroy (bb_bounds
);
3269 pointer_map_destroy (block_priority
);
3272 /* See if every path cross the loop goes through a statement that is known
3273 to not execute at the last iteration. In that case we can decrese iteration
3277 maybe_lower_iteration_bound (struct loop
*loop
)
3279 pointer_set_t
*not_executed_last_iteration
= NULL
;
3280 struct nb_iter_bound
*elt
;
3281 bool found_exit
= false;
3282 vec
<basic_block
> queue
= vNULL
;
3285 /* Collect all statements with interesting (i.e. lower than
3286 nb_iterations_upper_bound) bound on them.
3288 TODO: Due to the way record_estimate choose estimates to store, the bounds
3289 will be always nb_iterations_upper_bound-1. We can change this to record
3290 also statements not dominating the loop latch and update the walk bellow
3291 to the shortest path algorthm. */
3292 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3295 && elt
->bound
.ult (loop
->nb_iterations_upper_bound
))
3297 if (!not_executed_last_iteration
)
3298 not_executed_last_iteration
= pointer_set_create ();
3299 pointer_set_insert (not_executed_last_iteration
, elt
->stmt
);
3302 if (!not_executed_last_iteration
)
3305 /* Start DFS walk in the loop header and see if we can reach the
3306 loop latch or any of the exits (including statements with side
3307 effects that may terminate the loop otherwise) without visiting
3308 any of the statements known to have undefined effect on the last
3310 queue
.safe_push (loop
->header
);
3311 visited
= BITMAP_ALLOC (NULL
);
3312 bitmap_set_bit (visited
, loop
->header
->index
);
3317 basic_block bb
= queue
.pop ();
3318 gimple_stmt_iterator gsi
;
3319 bool stmt_found
= false;
3321 /* Loop for possible exits and statements bounding the execution. */
3322 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3324 gimple stmt
= gsi_stmt (gsi
);
3325 if (pointer_set_contains (not_executed_last_iteration
, stmt
))
3330 if (gimple_has_side_effects (stmt
))
3339 /* If no bounding statement is found, continue the walk. */
3345 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3347 if (loop_exit_edge_p (loop
, e
)
3348 || e
== loop_latch_edge (loop
))
3353 if (bitmap_set_bit (visited
, e
->dest
->index
))
3354 queue
.safe_push (e
->dest
);
3358 while (queue
.length () && !found_exit
);
3360 /* If every path through the loop reach bounding statement before exit,
3361 then we know the last iteration of the loop will have undefined effect
3362 and we can decrease number of iterations. */
3366 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3367 fprintf (dump_file
, "Reducing loop iteration estimate by 1; "
3368 "undefined statement must be executed at the last iteration.\n");
3369 record_niter_bound (loop
, loop
->nb_iterations_upper_bound
- double_int_one
,
3372 BITMAP_FREE (visited
);
3374 pointer_set_destroy (not_executed_last_iteration
);
3377 /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
3378 is true also use estimates derived from undefined behavior. */
3381 estimate_numbers_of_iterations_loop (struct loop
*loop
)
3386 struct tree_niter_desc niter_desc
;
3391 /* Give up if we already have tried to compute an estimation. */
3392 if (loop
->estimate_state
!= EST_NOT_COMPUTED
)
3395 loop
->estimate_state
= EST_AVAILABLE
;
3396 /* Force estimate compuation but leave any existing upper bound in place. */
3397 loop
->any_estimate
= false;
3399 /* Ensure that loop->nb_iterations is computed if possible. If it turns out
3400 to be constant, we avoid undefined behavior implied bounds and instead
3401 diagnose those loops with -Waggressive-loop-optimizations. */
3402 number_of_latch_executions (loop
);
3404 exits
= get_loop_exit_edges (loop
);
3405 likely_exit
= single_likely_exit (loop
);
3406 FOR_EACH_VEC_ELT (exits
, i
, ex
)
3408 if (!number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
3411 niter
= niter_desc
.niter
;
3412 type
= TREE_TYPE (niter
);
3413 if (TREE_CODE (niter_desc
.may_be_zero
) != INTEGER_CST
)
3414 niter
= build3 (COND_EXPR
, type
, niter_desc
.may_be_zero
,
3415 build_int_cst (type
, 0),
3417 record_estimate (loop
, niter
, niter_desc
.max
,
3418 last_stmt (ex
->src
),
3419 true, ex
== likely_exit
, true);
3423 if (flag_aggressive_loop_optimizations
)
3424 infer_loop_bounds_from_undefined (loop
);
3426 discover_iteration_bound_by_body_walk (loop
);
3428 maybe_lower_iteration_bound (loop
);
3430 /* If we have a measured profile, use it to estimate the number of
3432 if (loop
->header
->count
!= 0)
3434 gcov_type nit
= expected_loop_iterations_unbounded (loop
) + 1;
3435 bound
= gcov_type_to_double_int (nit
);
3436 record_niter_bound (loop
, bound
, true, false);
3439 /* If we know the exact number of iterations of this loop, try to
3440 not break code with undefined behavior by not recording smaller
3441 maximum number of iterations. */
3442 if (loop
->nb_iterations
3443 && TREE_CODE (loop
->nb_iterations
) == INTEGER_CST
)
3445 loop
->any_upper_bound
= true;
3446 loop
->nb_iterations_upper_bound
3447 = tree_to_double_int (loop
->nb_iterations
);
3451 /* Sets NIT to the estimated number of executions of the latch of the
3452 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
3453 large as the number of iterations. If we have no reliable estimate,
3454 the function returns false, otherwise returns true. */
3457 estimated_loop_iterations (struct loop
*loop
, double_int
*nit
)
3459 /* When SCEV information is available, try to update loop iterations
3460 estimate. Otherwise just return whatever we recorded earlier. */
3461 if (scev_initialized_p ())
3462 estimate_numbers_of_iterations_loop (loop
);
3464 return (get_estimated_loop_iterations (loop
, nit
));
3467 /* Similar to estimated_loop_iterations, but returns the estimate only
3468 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3469 on the number of iterations of LOOP could not be derived, returns -1. */
3472 estimated_loop_iterations_int (struct loop
*loop
)
3475 HOST_WIDE_INT hwi_nit
;
3477 if (!estimated_loop_iterations (loop
, &nit
))
3480 if (!nit
.fits_shwi ())
3482 hwi_nit
= nit
.to_shwi ();
3484 return hwi_nit
< 0 ? -1 : hwi_nit
;
3488 /* Sets NIT to an upper bound for the maximum number of executions of the
3489 latch of the LOOP. If we have no reliable estimate, the function returns
3490 false, otherwise returns true. */
3493 max_loop_iterations (struct loop
*loop
, double_int
*nit
)
3495 /* When SCEV information is available, try to update loop iterations
3496 estimate. Otherwise just return whatever we recorded earlier. */
3497 if (scev_initialized_p ())
3498 estimate_numbers_of_iterations_loop (loop
);
3500 return get_max_loop_iterations (loop
, nit
);
3503 /* Similar to max_loop_iterations, but returns the estimate only
3504 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3505 on the number of iterations of LOOP could not be derived, returns -1. */
3508 max_loop_iterations_int (struct loop
*loop
)
3511 HOST_WIDE_INT hwi_nit
;
3513 if (!max_loop_iterations (loop
, &nit
))
3516 if (!nit
.fits_shwi ())
3518 hwi_nit
= nit
.to_shwi ();
3520 return hwi_nit
< 0 ? -1 : hwi_nit
;
3523 /* Returns an estimate for the number of executions of statements
3524 in the LOOP. For statements before the loop exit, this exceeds
3525 the number of execution of the latch by one. */
3528 estimated_stmt_executions_int (struct loop
*loop
)
3530 HOST_WIDE_INT nit
= estimated_loop_iterations_int (loop
);
3536 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
3538 /* If the computation overflows, return -1. */
3539 return snit
< 0 ? -1 : snit
;
3542 /* Sets NIT to the estimated maximum number of executions of the latch of the
3543 LOOP, plus one. If we have no reliable estimate, the function returns
3544 false, otherwise returns true. */
3547 max_stmt_executions (struct loop
*loop
, double_int
*nit
)
3549 double_int nit_minus_one
;
3551 if (!max_loop_iterations (loop
, nit
))
3554 nit_minus_one
= *nit
;
3556 *nit
+= double_int_one
;
3558 return (*nit
).ugt (nit_minus_one
);
3561 /* Sets NIT to the estimated number of executions of the latch of the
3562 LOOP, plus one. If we have no reliable estimate, the function returns
3563 false, otherwise returns true. */
3566 estimated_stmt_executions (struct loop
*loop
, double_int
*nit
)
3568 double_int nit_minus_one
;
3570 if (!estimated_loop_iterations (loop
, nit
))
3573 nit_minus_one
= *nit
;
3575 *nit
+= double_int_one
;
3577 return (*nit
).ugt (nit_minus_one
);
3580 /* Records estimates on numbers of iterations of loops. */
3583 estimate_numbers_of_iterations (void)
3588 /* We don't want to issue signed overflow warnings while getting
3589 loop iteration estimates. */
3590 fold_defer_overflow_warnings ();
3592 FOR_EACH_LOOP (li
, loop
, 0)
3594 estimate_numbers_of_iterations_loop (loop
);
3597 fold_undefer_and_ignore_overflow_warnings ();
3600 /* Returns true if statement S1 dominates statement S2. */
3603 stmt_dominates_stmt_p (gimple s1
, gimple s2
)
3605 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
3613 gimple_stmt_iterator bsi
;
3615 if (gimple_code (s2
) == GIMPLE_PHI
)
3618 if (gimple_code (s1
) == GIMPLE_PHI
)
3621 for (bsi
= gsi_start_bb (bb1
); gsi_stmt (bsi
) != s2
; gsi_next (&bsi
))
3622 if (gsi_stmt (bsi
) == s1
)
3628 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
3631 /* Returns true when we can prove that the number of executions of
3632 STMT in the loop is at most NITER, according to the bound on
3633 the number of executions of the statement NITER_BOUND->stmt recorded in
3634 NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT.
3636 ??? This code can become quite a CPU hog - we can have many bounds,
3637 and large basic block forcing stmt_dominates_stmt_p to be queried
3638 many times on a large basic blocks, so the whole thing is O(n^2)
3639 for scev_probably_wraps_p invocation (that can be done n times).
3641 It would make more sense (and give better answers) to remember BB
3642 bounds computed by discover_iteration_bound_by_body_walk. */
3645 n_of_executions_at_most (gimple stmt
,
3646 struct nb_iter_bound
*niter_bound
,
3649 double_int bound
= niter_bound
->bound
;
3650 tree nit_type
= TREE_TYPE (niter
), e
;
3653 gcc_assert (TYPE_UNSIGNED (nit_type
));
3655 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
3656 the number of iterations is small. */
3657 if (!double_int_fits_to_tree_p (nit_type
, bound
))
3660 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3661 times. This means that:
3663 -- if NITER_BOUND->is_exit is true, then everything after
3664 it at most NITER_BOUND->bound times.
3666 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
3667 is executed, then NITER_BOUND->stmt is executed as well in the same
3668 iteration then STMT is executed at most NITER_BOUND->bound + 1 times.
3670 If we can determine that NITER_BOUND->stmt is always executed
3671 after STMT, then STMT is executed at most NITER_BOUND->bound + 2 times.
3672 We conclude that if both statements belong to the same
3673 basic block and STMT is before NITER_BOUND->stmt and there are no
3674 statements with side effects in between. */
3676 if (niter_bound
->is_exit
)
3678 if (stmt
== niter_bound
->stmt
3679 || !stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
3685 if (!stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
3687 gimple_stmt_iterator bsi
;
3688 if (gimple_bb (stmt
) != gimple_bb (niter_bound
->stmt
)
3689 || gimple_code (stmt
) == GIMPLE_PHI
3690 || gimple_code (niter_bound
->stmt
) == GIMPLE_PHI
)
3693 /* By stmt_dominates_stmt_p we already know that STMT appears
3694 before NITER_BOUND->STMT. Still need to test that the loop
3695 can not be terinated by a side effect in between. */
3696 for (bsi
= gsi_for_stmt (stmt
); gsi_stmt (bsi
) != niter_bound
->stmt
;
3698 if (gimple_has_side_effects (gsi_stmt (bsi
)))
3700 bound
+= double_int_one
;
3701 if (bound
.is_zero ()
3702 || !double_int_fits_to_tree_p (nit_type
, bound
))
3708 e
= fold_binary (cmp
, boolean_type_node
,
3709 niter
, double_int_to_tree (nit_type
, bound
));
3710 return e
&& integer_nonzerop (e
);
3713 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
3716 nowrap_type_p (tree type
)
3718 if (INTEGRAL_TYPE_P (type
)
3719 && TYPE_OVERFLOW_UNDEFINED (type
))
3722 if (POINTER_TYPE_P (type
))
3728 /* Return false only when the induction variable BASE + STEP * I is
3729 known to not overflow: i.e. when the number of iterations is small
3730 enough with respect to the step and initial condition in order to
3731 keep the evolution confined in TYPEs bounds. Return true when the
3732 iv is known to overflow or when the property is not computable.
3734 USE_OVERFLOW_SEMANTICS is true if this function should assume that
3735 the rules for overflow of the given language apply (e.g., that signed
3736 arithmetics in C does not overflow). */
3739 scev_probably_wraps_p (tree base
, tree step
,
3740 gimple at_stmt
, struct loop
*loop
,
3741 bool use_overflow_semantics
)
3743 tree delta
, step_abs
;
3744 tree unsigned_type
, valid_niter
;
3745 tree type
= TREE_TYPE (step
);
3748 struct nb_iter_bound
*bound
;
3750 /* FIXME: We really need something like
3751 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
3753 We used to test for the following situation that frequently appears
3754 during address arithmetics:
3756 D.1621_13 = (long unsigned intD.4) D.1620_12;
3757 D.1622_14 = D.1621_13 * 8;
3758 D.1623_15 = (doubleD.29 *) D.1622_14;
3760 And derived that the sequence corresponding to D_14
3761 can be proved to not wrap because it is used for computing a
3762 memory access; however, this is not really the case -- for example,
3763 if D_12 = (unsigned char) [254,+,1], then D_14 has values
3764 2032, 2040, 0, 8, ..., but the code is still legal. */
3766 if (chrec_contains_undetermined (base
)
3767 || chrec_contains_undetermined (step
))
3770 if (integer_zerop (step
))
3773 /* If we can use the fact that signed and pointer arithmetics does not
3774 wrap, we are done. */
3775 if (use_overflow_semantics
&& nowrap_type_p (TREE_TYPE (base
)))
3778 /* To be able to use estimates on number of iterations of the loop,
3779 we must have an upper bound on the absolute value of the step. */
3780 if (TREE_CODE (step
) != INTEGER_CST
)
3783 /* Don't issue signed overflow warnings. */
3784 fold_defer_overflow_warnings ();
3786 /* Otherwise, compute the number of iterations before we reach the
3787 bound of the type, and verify that the loop is exited before this
3789 unsigned_type
= unsigned_type_for (type
);
3790 base
= fold_convert (unsigned_type
, base
);
3792 if (tree_int_cst_sign_bit (step
))
3794 tree extreme
= fold_convert (unsigned_type
,
3795 lower_bound_in_type (type
, type
));
3796 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
3797 step_abs
= fold_build1 (NEGATE_EXPR
, unsigned_type
,
3798 fold_convert (unsigned_type
, step
));
3802 tree extreme
= fold_convert (unsigned_type
,
3803 upper_bound_in_type (type
, type
));
3804 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
3805 step_abs
= fold_convert (unsigned_type
, step
);
3808 valid_niter
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step_abs
);
3810 estimate_numbers_of_iterations_loop (loop
);
3812 if (max_loop_iterations (loop
, &niter
)
3813 && double_int_fits_to_tree_p (TREE_TYPE (valid_niter
), niter
)
3814 && (e
= fold_binary (GT_EXPR
, boolean_type_node
, valid_niter
,
3815 double_int_to_tree (TREE_TYPE (valid_niter
),
3817 && integer_nonzerop (e
))
3819 fold_undefer_and_ignore_overflow_warnings ();
3823 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
3825 if (n_of_executions_at_most (at_stmt
, bound
, valid_niter
))
3827 fold_undefer_and_ignore_overflow_warnings ();
3832 fold_undefer_and_ignore_overflow_warnings ();
3834 /* At this point we still don't have a proof that the iv does not
3835 overflow: give up. */
3839 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
3842 free_numbers_of_iterations_estimates_loop (struct loop
*loop
)
3844 struct nb_iter_bound
*bound
, *next
;
3846 loop
->nb_iterations
= NULL
;
3847 loop
->estimate_state
= EST_NOT_COMPUTED
;
3848 for (bound
= loop
->bounds
; bound
; bound
= next
)
3854 loop
->bounds
= NULL
;
3857 /* Frees the information on upper bounds on numbers of iterations of loops. */
3860 free_numbers_of_iterations_estimates (void)
3865 FOR_EACH_LOOP (li
, loop
, 0)
3867 free_numbers_of_iterations_estimates_loop (loop
);
3871 /* Substitute value VAL for ssa name NAME inside expressions held
3875 substitute_in_loop_info (struct loop
*loop
, tree name
, tree val
)
3877 loop
->nb_iterations
= simplify_replace_tree (loop
->nb_iterations
, name
, val
);