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-ssa.h"
32 #include "tree-phinodes.h"
33 #include "ssa-iterators.h"
34 #include "tree-ssa-loop-ivopts.h"
35 #include "tree-ssa-loop-niter.h"
36 #include "tree-ssa-loop.h"
40 #include "tree-chrec.h"
41 #include "tree-scalar-evolution.h"
42 #include "tree-data-ref.h"
45 #include "diagnostic-core.h"
46 #include "tree-inline.h"
47 #include "tree-pass.h"
48 #include "tree-ssanames.h"
51 #define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
53 /* The maximum number of dominator BBs we search for conditions
54 of loop header copies we use for simplifying a conditional
56 #define MAX_DOMINATORS_TO_WALK 8
60 Analysis of number of iterations of an affine exit test.
64 /* Bounds on some value, BELOW <= X <= UP. */
72 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */
75 split_to_var_and_offset (tree expr
, tree
*var
, mpz_t offset
)
77 tree type
= TREE_TYPE (expr
);
83 mpz_set_ui (offset
, 0);
85 switch (TREE_CODE (expr
))
92 case POINTER_PLUS_EXPR
:
93 op0
= TREE_OPERAND (expr
, 0);
94 op1
= TREE_OPERAND (expr
, 1);
96 if (TREE_CODE (op1
) != INTEGER_CST
)
100 /* Always sign extend the offset. */
101 off
= tree_to_double_int (op1
);
102 off
= off
.sext (TYPE_PRECISION (type
));
103 mpz_set_double_int (offset
, off
, false);
105 mpz_neg (offset
, offset
);
109 *var
= build_int_cst_type (type
, 0);
110 off
= tree_to_double_int (expr
);
111 mpz_set_double_int (offset
, off
, TYPE_UNSIGNED (type
));
119 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
120 in TYPE to MIN and MAX. */
123 determine_value_range (struct loop
*loop
, tree type
, tree var
, mpz_t off
,
124 mpz_t min
, mpz_t max
)
126 double_int minv
, maxv
;
127 enum value_range_type rtype
= VR_VARYING
;
129 /* If the expression is a constant, we know its value exactly. */
130 if (integer_zerop (var
))
137 get_type_static_bounds (type
, min
, max
);
139 /* See if we have some range info from VRP. */
140 if (TREE_CODE (var
) == SSA_NAME
&& INTEGRAL_TYPE_P (type
))
142 edge e
= loop_preheader_edge (loop
);
143 gimple_stmt_iterator gsi
;
145 /* Either for VAR itself... */
146 rtype
= get_range_info (var
, &minv
, &maxv
);
147 /* Or for PHI results in loop->header where VAR is used as
148 PHI argument from the loop preheader edge. */
149 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
151 gimple phi
= gsi_stmt (gsi
);
152 double_int minc
, maxc
;
153 if (PHI_ARG_DEF_FROM_EDGE (phi
, e
) == var
154 && (get_range_info (gimple_phi_result (phi
), &minc
, &maxc
)
157 if (rtype
!= VR_RANGE
)
165 minv
= minv
.max (minc
, TYPE_UNSIGNED (type
));
166 maxv
= maxv
.min (maxc
, TYPE_UNSIGNED (type
));
167 gcc_assert (minv
.cmp (maxv
, TYPE_UNSIGNED (type
)) <= 0);
171 if (rtype
== VR_RANGE
)
174 gcc_assert (minv
.cmp (maxv
, TYPE_UNSIGNED (type
)) <= 0);
177 mpz_set_double_int (minm
, minv
, TYPE_UNSIGNED (type
));
178 mpz_set_double_int (maxm
, maxv
, TYPE_UNSIGNED (type
));
179 mpz_add (minm
, minm
, off
);
180 mpz_add (maxm
, maxm
, off
);
181 /* If the computation may not wrap or off is zero, then this
182 is always fine. If off is negative and minv + off isn't
183 smaller than type's minimum, or off is positive and
184 maxv + off isn't bigger than type's maximum, use the more
185 precise range too. */
186 if (nowrap_type_p (type
)
187 || mpz_sgn (off
) == 0
188 || (mpz_sgn (off
) < 0 && mpz_cmp (minm
, min
) >= 0)
189 || (mpz_sgn (off
) > 0 && mpz_cmp (maxm
, max
) <= 0))
202 /* If the computation may wrap, we know nothing about the value, except for
203 the range of the type. */
204 if (!nowrap_type_p (type
))
207 /* Since the addition of OFF does not wrap, if OFF is positive, then we may
208 add it to MIN, otherwise to MAX. */
209 if (mpz_sgn (off
) < 0)
210 mpz_add (max
, max
, off
);
212 mpz_add (min
, min
, off
);
215 /* Stores the bounds on the difference of the values of the expressions
216 (var + X) and (var + Y), computed in TYPE, to BNDS. */
219 bound_difference_of_offsetted_base (tree type
, mpz_t x
, mpz_t y
,
222 int rel
= mpz_cmp (x
, y
);
223 bool may_wrap
= !nowrap_type_p (type
);
226 /* If X == Y, then the expressions are always equal.
227 If X > Y, there are the following possibilities:
228 a) neither of var + X and var + Y overflow or underflow, or both of
229 them do. Then their difference is X - Y.
230 b) var + X overflows, and var + Y does not. Then the values of the
231 expressions are var + X - M and var + Y, where M is the range of
232 the type, and their difference is X - Y - M.
233 c) var + Y underflows and var + X does not. Their difference again
235 Therefore, if the arithmetics in type does not overflow, then the
236 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
237 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
238 (X - Y, X - Y + M). */
242 mpz_set_ui (bnds
->below
, 0);
243 mpz_set_ui (bnds
->up
, 0);
248 mpz_set_double_int (m
, double_int::mask (TYPE_PRECISION (type
)), true);
249 mpz_add_ui (m
, m
, 1);
250 mpz_sub (bnds
->up
, x
, y
);
251 mpz_set (bnds
->below
, bnds
->up
);
256 mpz_sub (bnds
->below
, bnds
->below
, m
);
258 mpz_add (bnds
->up
, bnds
->up
, m
);
264 /* From condition C0 CMP C1 derives information regarding the
265 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
266 and stores it to BNDS. */
269 refine_bounds_using_guard (tree type
, tree varx
, mpz_t offx
,
270 tree vary
, mpz_t offy
,
271 tree c0
, enum tree_code cmp
, tree c1
,
274 tree varc0
, varc1
, tmp
, ctype
;
275 mpz_t offc0
, offc1
, loffx
, loffy
, bnd
;
277 bool no_wrap
= nowrap_type_p (type
);
286 STRIP_SIGN_NOPS (c0
);
287 STRIP_SIGN_NOPS (c1
);
288 ctype
= TREE_TYPE (c0
);
289 if (!useless_type_conversion_p (ctype
, type
))
295 /* We could derive quite precise information from EQ_EXPR, however, such
296 a guard is unlikely to appear, so we do not bother with handling
301 /* NE_EXPR comparisons do not contain much of useful information, except for
302 special case of comparing with the bounds of the type. */
303 if (TREE_CODE (c1
) != INTEGER_CST
304 || !INTEGRAL_TYPE_P (type
))
307 /* Ensure that the condition speaks about an expression in the same type
309 ctype
= TREE_TYPE (c0
);
310 if (TYPE_PRECISION (ctype
) != TYPE_PRECISION (type
))
312 c0
= fold_convert (type
, c0
);
313 c1
= fold_convert (type
, c1
);
315 if (TYPE_MIN_VALUE (type
)
316 && operand_equal_p (c1
, TYPE_MIN_VALUE (type
), 0))
321 if (TYPE_MAX_VALUE (type
)
322 && operand_equal_p (c1
, TYPE_MAX_VALUE (type
), 0))
335 split_to_var_and_offset (expand_simple_operations (c0
), &varc0
, offc0
);
336 split_to_var_and_offset (expand_simple_operations (c1
), &varc1
, offc1
);
338 /* We are only interested in comparisons of expressions based on VARX and
339 VARY. TODO -- we might also be able to derive some bounds from
340 expressions containing just one of the variables. */
342 if (operand_equal_p (varx
, varc1
, 0))
344 tmp
= varc0
; varc0
= varc1
; varc1
= tmp
;
345 mpz_swap (offc0
, offc1
);
346 cmp
= swap_tree_comparison (cmp
);
349 if (!operand_equal_p (varx
, varc0
, 0)
350 || !operand_equal_p (vary
, varc1
, 0))
353 mpz_init_set (loffx
, offx
);
354 mpz_init_set (loffy
, offy
);
356 if (cmp
== GT_EXPR
|| cmp
== GE_EXPR
)
358 tmp
= varx
; varx
= vary
; vary
= tmp
;
359 mpz_swap (offc0
, offc1
);
360 mpz_swap (loffx
, loffy
);
361 cmp
= swap_tree_comparison (cmp
);
365 /* If there is no overflow, the condition implies that
367 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
369 The overflows and underflows may complicate things a bit; each
370 overflow decreases the appropriate offset by M, and underflow
371 increases it by M. The above inequality would not necessarily be
374 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
375 VARX + OFFC0 overflows, but VARX + OFFX does not.
376 This may only happen if OFFX < OFFC0.
377 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
378 VARY + OFFC1 underflows and VARY + OFFY does not.
379 This may only happen if OFFY > OFFC1. */
388 x_ok
= (integer_zerop (varx
)
389 || mpz_cmp (loffx
, offc0
) >= 0);
390 y_ok
= (integer_zerop (vary
)
391 || mpz_cmp (loffy
, offc1
) <= 0);
397 mpz_sub (bnd
, loffx
, loffy
);
398 mpz_add (bnd
, bnd
, offc1
);
399 mpz_sub (bnd
, bnd
, offc0
);
402 mpz_sub_ui (bnd
, bnd
, 1);
407 if (mpz_cmp (bnds
->below
, bnd
) < 0)
408 mpz_set (bnds
->below
, bnd
);
412 if (mpz_cmp (bnd
, bnds
->up
) < 0)
413 mpz_set (bnds
->up
, bnd
);
425 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
426 The subtraction is considered to be performed in arbitrary precision,
429 We do not attempt to be too clever regarding the value ranges of X and
430 Y; most of the time, they are just integers or ssa names offsetted by
431 integer. However, we try to use the information contained in the
432 comparisons before the loop (usually created by loop header copying). */
435 bound_difference (struct loop
*loop
, tree x
, tree y
, bounds
*bnds
)
437 tree type
= TREE_TYPE (x
);
440 mpz_t minx
, maxx
, miny
, maxy
;
448 /* Get rid of unnecessary casts, but preserve the value of
453 mpz_init (bnds
->below
);
457 split_to_var_and_offset (x
, &varx
, offx
);
458 split_to_var_and_offset (y
, &vary
, offy
);
460 if (!integer_zerop (varx
)
461 && operand_equal_p (varx
, vary
, 0))
463 /* Special case VARX == VARY -- we just need to compare the
464 offsets. The matters are a bit more complicated in the
465 case addition of offsets may wrap. */
466 bound_difference_of_offsetted_base (type
, offx
, offy
, bnds
);
470 /* Otherwise, use the value ranges to determine the initial
471 estimates on below and up. */
476 determine_value_range (loop
, type
, varx
, offx
, minx
, maxx
);
477 determine_value_range (loop
, type
, vary
, offy
, miny
, maxy
);
479 mpz_sub (bnds
->below
, minx
, maxy
);
480 mpz_sub (bnds
->up
, maxx
, miny
);
487 /* If both X and Y are constants, we cannot get any more precise. */
488 if (integer_zerop (varx
) && integer_zerop (vary
))
491 /* Now walk the dominators of the loop header and use the entry
492 guards to refine the estimates. */
493 for (bb
= loop
->header
;
494 bb
!= ENTRY_BLOCK_PTR
&& cnt
< MAX_DOMINATORS_TO_WALK
;
495 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
497 if (!single_pred_p (bb
))
499 e
= single_pred_edge (bb
);
501 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
504 cond
= last_stmt (e
->src
);
505 c0
= gimple_cond_lhs (cond
);
506 cmp
= gimple_cond_code (cond
);
507 c1
= gimple_cond_rhs (cond
);
509 if (e
->flags
& EDGE_FALSE_VALUE
)
510 cmp
= invert_tree_comparison (cmp
, false);
512 refine_bounds_using_guard (type
, varx
, offx
, vary
, offy
,
522 /* Update the bounds in BNDS that restrict the value of X to the bounds
523 that restrict the value of X + DELTA. X can be obtained as a
524 difference of two values in TYPE. */
527 bounds_add (bounds
*bnds
, double_int delta
, tree type
)
532 mpz_set_double_int (mdelta
, delta
, false);
535 mpz_set_double_int (max
, double_int::mask (TYPE_PRECISION (type
)), true);
537 mpz_add (bnds
->up
, bnds
->up
, mdelta
);
538 mpz_add (bnds
->below
, bnds
->below
, mdelta
);
540 if (mpz_cmp (bnds
->up
, max
) > 0)
541 mpz_set (bnds
->up
, max
);
544 if (mpz_cmp (bnds
->below
, max
) < 0)
545 mpz_set (bnds
->below
, max
);
551 /* Update the bounds in BNDS that restrict the value of X to the bounds
552 that restrict the value of -X. */
555 bounds_negate (bounds
*bnds
)
559 mpz_init_set (tmp
, bnds
->up
);
560 mpz_neg (bnds
->up
, bnds
->below
);
561 mpz_neg (bnds
->below
, tmp
);
565 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
568 inverse (tree x
, tree mask
)
570 tree type
= TREE_TYPE (x
);
572 unsigned ctr
= tree_floor_log2 (mask
);
574 if (TYPE_PRECISION (type
) <= HOST_BITS_PER_WIDE_INT
)
576 unsigned HOST_WIDE_INT ix
;
577 unsigned HOST_WIDE_INT imask
;
578 unsigned HOST_WIDE_INT irslt
= 1;
580 gcc_assert (cst_and_fits_in_hwi (x
));
581 gcc_assert (cst_and_fits_in_hwi (mask
));
583 ix
= int_cst_value (x
);
584 imask
= int_cst_value (mask
);
593 rslt
= build_int_cst_type (type
, irslt
);
597 rslt
= build_int_cst (type
, 1);
600 rslt
= int_const_binop (MULT_EXPR
, rslt
, x
);
601 x
= int_const_binop (MULT_EXPR
, x
, x
);
603 rslt
= int_const_binop (BIT_AND_EXPR
, rslt
, mask
);
609 /* Derives the upper bound BND on the number of executions of loop with exit
610 condition S * i <> C. If NO_OVERFLOW is true, then the control variable of
611 the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed
612 that the loop ends through this exit, i.e., the induction variable ever
613 reaches the value of C.
615 The value C is equal to final - base, where final and base are the final and
616 initial value of the actual induction variable in the analysed loop. BNDS
617 bounds the value of this difference when computed in signed type with
618 unbounded range, while the computation of C is performed in an unsigned
619 type with the range matching the range of the type of the induction variable.
620 In particular, BNDS.up contains an upper bound on C in the following cases:
621 -- if the iv must reach its final value without overflow, i.e., if
622 NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
623 -- if final >= base, which we know to hold when BNDS.below >= 0. */
626 number_of_iterations_ne_max (mpz_t bnd
, bool no_overflow
, tree c
, tree s
,
627 bounds
*bnds
, bool exit_must_be_taken
)
631 tree type
= TREE_TYPE (c
);
632 bool bnds_u_valid
= ((no_overflow
&& exit_must_be_taken
)
633 || mpz_sgn (bnds
->below
) >= 0);
636 || (TREE_CODE (c
) == INTEGER_CST
637 && TREE_CODE (s
) == INTEGER_CST
638 && tree_to_double_int (c
).mod (tree_to_double_int (s
),
639 TYPE_UNSIGNED (type
),
640 EXACT_DIV_EXPR
).is_zero ())
641 || (TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (c
))
642 && multiple_of_p (type
, c
, s
)))
644 /* If C is an exact multiple of S, then its value will be reached before
645 the induction variable overflows (unless the loop is exited in some
646 other way before). Note that the actual induction variable in the
647 loop (which ranges from base to final instead of from 0 to C) may
648 overflow, in which case BNDS.up will not be giving a correct upper
649 bound on C; thus, BNDS_U_VALID had to be computed in advance. */
651 exit_must_be_taken
= true;
654 /* If the induction variable can overflow, the number of iterations is at
655 most the period of the control variable (or infinite, but in that case
656 the whole # of iterations analysis will fail). */
659 max
= double_int::mask (TYPE_PRECISION (type
)
660 - tree_low_cst (num_ending_zeros (s
), 1));
661 mpz_set_double_int (bnd
, max
, true);
665 /* Now we know that the induction variable does not overflow, so the loop
666 iterates at most (range of type / S) times. */
667 mpz_set_double_int (bnd
, double_int::mask (TYPE_PRECISION (type
)), true);
669 /* If the induction variable is guaranteed to reach the value of C before
671 if (exit_must_be_taken
)
673 /* ... then we can strengthen this to C / S, and possibly we can use
674 the upper bound on C given by BNDS. */
675 if (TREE_CODE (c
) == INTEGER_CST
)
676 mpz_set_double_int (bnd
, tree_to_double_int (c
), true);
677 else if (bnds_u_valid
)
678 mpz_set (bnd
, bnds
->up
);
682 mpz_set_double_int (d
, tree_to_double_int (s
), true);
683 mpz_fdiv_q (bnd
, bnd
, d
);
687 /* Determines number of iterations of loop whose ending condition
688 is IV <> FINAL. TYPE is the type of the iv. The number of
689 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
690 we know that the exit must be taken eventually, i.e., that the IV
691 ever reaches the value FINAL (we derived this earlier, and possibly set
692 NITER->assumptions to make sure this is the case). BNDS contains the
693 bounds on the difference FINAL - IV->base. */
696 number_of_iterations_ne (tree type
, affine_iv
*iv
, tree final
,
697 struct tree_niter_desc
*niter
, bool exit_must_be_taken
,
700 tree niter_type
= unsigned_type_for (type
);
701 tree s
, c
, d
, bits
, assumption
, tmp
, bound
;
704 niter
->control
= *iv
;
705 niter
->bound
= final
;
706 niter
->cmp
= NE_EXPR
;
708 /* Rearrange the terms so that we get inequality S * i <> C, with S
709 positive. Also cast everything to the unsigned type. If IV does
710 not overflow, BNDS bounds the value of C. Also, this is the
711 case if the computation |FINAL - IV->base| does not overflow, i.e.,
712 if BNDS->below in the result is nonnegative. */
713 if (tree_int_cst_sign_bit (iv
->step
))
715 s
= fold_convert (niter_type
,
716 fold_build1 (NEGATE_EXPR
, type
, iv
->step
));
717 c
= fold_build2 (MINUS_EXPR
, niter_type
,
718 fold_convert (niter_type
, iv
->base
),
719 fold_convert (niter_type
, final
));
720 bounds_negate (bnds
);
724 s
= fold_convert (niter_type
, iv
->step
);
725 c
= fold_build2 (MINUS_EXPR
, niter_type
,
726 fold_convert (niter_type
, final
),
727 fold_convert (niter_type
, iv
->base
));
731 number_of_iterations_ne_max (max
, iv
->no_overflow
, c
, s
, bnds
,
733 niter
->max
= mpz_get_double_int (niter_type
, max
, false);
736 /* First the trivial cases -- when the step is 1. */
737 if (integer_onep (s
))
743 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
744 is infinite. Otherwise, the number of iterations is
745 (inverse(s/d) * (c/d)) mod (size of mode/d). */
746 bits
= num_ending_zeros (s
);
747 bound
= build_low_bits_mask (niter_type
,
748 (TYPE_PRECISION (niter_type
)
749 - tree_low_cst (bits
, 1)));
751 d
= fold_binary_to_constant (LSHIFT_EXPR
, niter_type
,
752 build_int_cst (niter_type
, 1), bits
);
753 s
= fold_binary_to_constant (RSHIFT_EXPR
, niter_type
, s
, bits
);
755 if (!exit_must_be_taken
)
757 /* If we cannot assume that the exit is taken eventually, record the
758 assumptions for divisibility of c. */
759 assumption
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, c
, d
);
760 assumption
= fold_build2 (EQ_EXPR
, boolean_type_node
,
761 assumption
, build_int_cst (niter_type
, 0));
762 if (!integer_nonzerop (assumption
))
763 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
764 niter
->assumptions
, assumption
);
767 c
= fold_build2 (EXACT_DIV_EXPR
, niter_type
, c
, d
);
768 tmp
= fold_build2 (MULT_EXPR
, niter_type
, c
, inverse (s
, bound
));
769 niter
->niter
= fold_build2 (BIT_AND_EXPR
, niter_type
, tmp
, bound
);
773 /* Checks whether we can determine the final value of the control variable
774 of the loop with ending condition IV0 < IV1 (computed in TYPE).
775 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
776 of the step. The assumptions necessary to ensure that the computation
777 of the final value does not overflow are recorded in NITER. If we
778 find the final value, we adjust DELTA and return TRUE. Otherwise
779 we return false. BNDS bounds the value of IV1->base - IV0->base,
780 and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
781 true if we know that the exit must be taken eventually. */
784 number_of_iterations_lt_to_ne (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
785 struct tree_niter_desc
*niter
,
786 tree
*delta
, tree step
,
787 bool exit_must_be_taken
, bounds
*bnds
)
789 tree niter_type
= TREE_TYPE (step
);
790 tree mod
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, *delta
, step
);
793 tree assumption
= boolean_true_node
, bound
, noloop
;
794 bool ret
= false, fv_comp_no_overflow
;
796 if (POINTER_TYPE_P (type
))
799 if (TREE_CODE (mod
) != INTEGER_CST
)
801 if (integer_nonzerop (mod
))
802 mod
= fold_build2 (MINUS_EXPR
, niter_type
, step
, mod
);
803 tmod
= fold_convert (type1
, mod
);
806 mpz_set_double_int (mmod
, tree_to_double_int (mod
), true);
807 mpz_neg (mmod
, mmod
);
809 /* If the induction variable does not overflow and the exit is taken,
810 then the computation of the final value does not overflow. This is
811 also obviously the case if the new final value is equal to the
812 current one. Finally, we postulate this for pointer type variables,
813 as the code cannot rely on the object to that the pointer points being
814 placed at the end of the address space (and more pragmatically,
815 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
816 if (integer_zerop (mod
) || POINTER_TYPE_P (type
))
817 fv_comp_no_overflow
= true;
818 else if (!exit_must_be_taken
)
819 fv_comp_no_overflow
= false;
821 fv_comp_no_overflow
=
822 (iv0
->no_overflow
&& integer_nonzerop (iv0
->step
))
823 || (iv1
->no_overflow
&& integer_nonzerop (iv1
->step
));
825 if (integer_nonzerop (iv0
->step
))
827 /* The final value of the iv is iv1->base + MOD, assuming that this
828 computation does not overflow, and that
829 iv0->base <= iv1->base + MOD. */
830 if (!fv_comp_no_overflow
)
832 bound
= fold_build2 (MINUS_EXPR
, type1
,
833 TYPE_MAX_VALUE (type1
), tmod
);
834 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
836 if (integer_zerop (assumption
))
839 if (mpz_cmp (mmod
, bnds
->below
) < 0)
840 noloop
= boolean_false_node
;
841 else if (POINTER_TYPE_P (type
))
842 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
844 fold_build_pointer_plus (iv1
->base
, tmod
));
846 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
848 fold_build2 (PLUS_EXPR
, type1
,
853 /* The final value of the iv is iv0->base - MOD, assuming that this
854 computation does not overflow, and that
855 iv0->base - MOD <= iv1->base. */
856 if (!fv_comp_no_overflow
)
858 bound
= fold_build2 (PLUS_EXPR
, type1
,
859 TYPE_MIN_VALUE (type1
), tmod
);
860 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
862 if (integer_zerop (assumption
))
865 if (mpz_cmp (mmod
, bnds
->below
) < 0)
866 noloop
= boolean_false_node
;
867 else if (POINTER_TYPE_P (type
))
868 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
869 fold_build_pointer_plus (iv0
->base
,
870 fold_build1 (NEGATE_EXPR
,
874 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
875 fold_build2 (MINUS_EXPR
, type1
,
880 if (!integer_nonzerop (assumption
))
881 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
884 if (!integer_zerop (noloop
))
885 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
888 bounds_add (bnds
, tree_to_double_int (mod
), type
);
889 *delta
= fold_build2 (PLUS_EXPR
, niter_type
, *delta
, mod
);
897 /* Add assertions to NITER that ensure that the control variable of the loop
898 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
899 are TYPE. Returns false if we can prove that there is an overflow, true
900 otherwise. STEP is the absolute value of the step. */
903 assert_no_overflow_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
904 struct tree_niter_desc
*niter
, tree step
)
906 tree bound
, d
, assumption
, diff
;
907 tree niter_type
= TREE_TYPE (step
);
909 if (integer_nonzerop (iv0
->step
))
911 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
912 if (iv0
->no_overflow
)
915 /* If iv0->base is a constant, we can determine the last value before
916 overflow precisely; otherwise we conservatively assume
919 if (TREE_CODE (iv0
->base
) == INTEGER_CST
)
921 d
= fold_build2 (MINUS_EXPR
, niter_type
,
922 fold_convert (niter_type
, TYPE_MAX_VALUE (type
)),
923 fold_convert (niter_type
, iv0
->base
));
924 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
927 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
928 build_int_cst (niter_type
, 1));
929 bound
= fold_build2 (MINUS_EXPR
, type
,
930 TYPE_MAX_VALUE (type
), fold_convert (type
, diff
));
931 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
936 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
937 if (iv1
->no_overflow
)
940 if (TREE_CODE (iv1
->base
) == INTEGER_CST
)
942 d
= fold_build2 (MINUS_EXPR
, niter_type
,
943 fold_convert (niter_type
, iv1
->base
),
944 fold_convert (niter_type
, TYPE_MIN_VALUE (type
)));
945 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
948 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
949 build_int_cst (niter_type
, 1));
950 bound
= fold_build2 (PLUS_EXPR
, type
,
951 TYPE_MIN_VALUE (type
), fold_convert (type
, diff
));
952 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
956 if (integer_zerop (assumption
))
958 if (!integer_nonzerop (assumption
))
959 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
960 niter
->assumptions
, assumption
);
962 iv0
->no_overflow
= true;
963 iv1
->no_overflow
= true;
967 /* Add an assumption to NITER that a loop whose ending condition
968 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
969 bounds the value of IV1->base - IV0->base. */
972 assert_loop_rolls_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
973 struct tree_niter_desc
*niter
, bounds
*bnds
)
975 tree assumption
= boolean_true_node
, bound
, diff
;
976 tree mbz
, mbzl
, mbzr
, type1
;
977 bool rolls_p
, no_overflow_p
;
981 /* We are going to compute the number of iterations as
982 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
983 variant of TYPE. This formula only works if
985 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
987 (where MAX is the maximum value of the unsigned variant of TYPE, and
988 the computations in this formula are performed in full precision,
989 i.e., without overflows).
991 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
992 we have a condition of the form iv0->base - step < iv1->base before the loop,
993 and for loops iv0->base < iv1->base - step * i the condition
994 iv0->base < iv1->base + step, due to loop header copying, which enable us
995 to prove the lower bound.
997 The upper bound is more complicated. Unless the expressions for initial
998 and final value themselves contain enough information, we usually cannot
999 derive it from the context. */
1001 /* First check whether the answer does not follow from the bounds we gathered
1003 if (integer_nonzerop (iv0
->step
))
1004 dstep
= tree_to_double_int (iv0
->step
);
1007 dstep
= tree_to_double_int (iv1
->step
).sext (TYPE_PRECISION (type
));
1012 mpz_set_double_int (mstep
, dstep
, true);
1013 mpz_neg (mstep
, mstep
);
1014 mpz_add_ui (mstep
, mstep
, 1);
1016 rolls_p
= mpz_cmp (mstep
, bnds
->below
) <= 0;
1019 mpz_set_double_int (max
, double_int::mask (TYPE_PRECISION (type
)), true);
1020 mpz_add (max
, max
, mstep
);
1021 no_overflow_p
= (mpz_cmp (bnds
->up
, max
) <= 0
1022 /* For pointers, only values lying inside a single object
1023 can be compared or manipulated by pointer arithmetics.
1024 Gcc in general does not allow or handle objects larger
1025 than half of the address space, hence the upper bound
1026 is satisfied for pointers. */
1027 || POINTER_TYPE_P (type
));
1031 if (rolls_p
&& no_overflow_p
)
1035 if (POINTER_TYPE_P (type
))
1038 /* Now the hard part; we must formulate the assumption(s) as expressions, and
1039 we must be careful not to introduce overflow. */
1041 if (integer_nonzerop (iv0
->step
))
1043 diff
= fold_build2 (MINUS_EXPR
, type1
,
1044 iv0
->step
, build_int_cst (type1
, 1));
1046 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
1047 0 address never belongs to any object, we can assume this for
1049 if (!POINTER_TYPE_P (type
))
1051 bound
= fold_build2 (PLUS_EXPR
, type1
,
1052 TYPE_MIN_VALUE (type
), diff
);
1053 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
1057 /* And then we can compute iv0->base - diff, and compare it with
1059 mbzl
= fold_build2 (MINUS_EXPR
, type1
,
1060 fold_convert (type1
, iv0
->base
), diff
);
1061 mbzr
= fold_convert (type1
, iv1
->base
);
1065 diff
= fold_build2 (PLUS_EXPR
, type1
,
1066 iv1
->step
, build_int_cst (type1
, 1));
1068 if (!POINTER_TYPE_P (type
))
1070 bound
= fold_build2 (PLUS_EXPR
, type1
,
1071 TYPE_MAX_VALUE (type
), diff
);
1072 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
1076 mbzl
= fold_convert (type1
, iv0
->base
);
1077 mbzr
= fold_build2 (MINUS_EXPR
, type1
,
1078 fold_convert (type1
, iv1
->base
), diff
);
1081 if (!integer_nonzerop (assumption
))
1082 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1083 niter
->assumptions
, assumption
);
1086 mbz
= fold_build2 (GT_EXPR
, boolean_type_node
, mbzl
, mbzr
);
1087 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1088 niter
->may_be_zero
, mbz
);
1092 /* Determines number of iterations of loop whose ending condition
1093 is IV0 < IV1. TYPE is the type of the iv. The number of
1094 iterations is stored to NITER. BNDS bounds the difference
1095 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
1096 that the exit must be taken eventually. */
1099 number_of_iterations_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1100 struct tree_niter_desc
*niter
,
1101 bool exit_must_be_taken
, bounds
*bnds
)
1103 tree niter_type
= unsigned_type_for (type
);
1104 tree delta
, step
, s
;
1107 if (integer_nonzerop (iv0
->step
))
1109 niter
->control
= *iv0
;
1110 niter
->cmp
= LT_EXPR
;
1111 niter
->bound
= iv1
->base
;
1115 niter
->control
= *iv1
;
1116 niter
->cmp
= GT_EXPR
;
1117 niter
->bound
= iv0
->base
;
1120 delta
= fold_build2 (MINUS_EXPR
, niter_type
,
1121 fold_convert (niter_type
, iv1
->base
),
1122 fold_convert (niter_type
, iv0
->base
));
1124 /* First handle the special case that the step is +-1. */
1125 if ((integer_onep (iv0
->step
) && integer_zerop (iv1
->step
))
1126 || (integer_all_onesp (iv1
->step
) && integer_zerop (iv0
->step
)))
1128 /* for (i = iv0->base; i < iv1->base; i++)
1132 for (i = iv1->base; i > iv0->base; i--).
1134 In both cases # of iterations is iv1->base - iv0->base, assuming that
1135 iv1->base >= iv0->base.
1137 First try to derive a lower bound on the value of
1138 iv1->base - iv0->base, computed in full precision. If the difference
1139 is nonnegative, we are done, otherwise we must record the
1142 if (mpz_sgn (bnds
->below
) < 0)
1143 niter
->may_be_zero
= fold_build2 (LT_EXPR
, boolean_type_node
,
1144 iv1
->base
, iv0
->base
);
1145 niter
->niter
= delta
;
1146 niter
->max
= mpz_get_double_int (niter_type
, bnds
->up
, false);
1150 if (integer_nonzerop (iv0
->step
))
1151 step
= fold_convert (niter_type
, iv0
->step
);
1153 step
= fold_convert (niter_type
,
1154 fold_build1 (NEGATE_EXPR
, type
, iv1
->step
));
1156 /* If we can determine the final value of the control iv exactly, we can
1157 transform the condition to != comparison. In particular, this will be
1158 the case if DELTA is constant. */
1159 if (number_of_iterations_lt_to_ne (type
, iv0
, iv1
, niter
, &delta
, step
,
1160 exit_must_be_taken
, bnds
))
1164 zps
.base
= build_int_cst (niter_type
, 0);
1166 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1167 zps does not overflow. */
1168 zps
.no_overflow
= true;
1170 return number_of_iterations_ne (type
, &zps
, delta
, niter
, true, bnds
);
1173 /* Make sure that the control iv does not overflow. */
1174 if (!assert_no_overflow_lt (type
, iv0
, iv1
, niter
, step
))
1177 /* We determine the number of iterations as (delta + step - 1) / step. For
1178 this to work, we must know that iv1->base >= iv0->base - step + 1,
1179 otherwise the loop does not roll. */
1180 assert_loop_rolls_lt (type
, iv0
, iv1
, niter
, bnds
);
1182 s
= fold_build2 (MINUS_EXPR
, niter_type
,
1183 step
, build_int_cst (niter_type
, 1));
1184 delta
= fold_build2 (PLUS_EXPR
, niter_type
, delta
, s
);
1185 niter
->niter
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, delta
, step
);
1189 mpz_set_double_int (mstep
, tree_to_double_int (step
), true);
1190 mpz_add (tmp
, bnds
->up
, mstep
);
1191 mpz_sub_ui (tmp
, tmp
, 1);
1192 mpz_fdiv_q (tmp
, tmp
, mstep
);
1193 niter
->max
= mpz_get_double_int (niter_type
, tmp
, false);
1200 /* Determines number of iterations of loop whose ending condition
1201 is IV0 <= IV1. TYPE is the type of the iv. The number of
1202 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
1203 we know that this condition must eventually become false (we derived this
1204 earlier, and possibly set NITER->assumptions to make sure this
1205 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1208 number_of_iterations_le (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1209 struct tree_niter_desc
*niter
, bool exit_must_be_taken
,
1214 if (POINTER_TYPE_P (type
))
1217 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1218 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1219 value of the type. This we must know anyway, since if it is
1220 equal to this value, the loop rolls forever. We do not check
1221 this condition for pointer type ivs, as the code cannot rely on
1222 the object to that the pointer points being placed at the end of
1223 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1224 not defined for pointers). */
1226 if (!exit_must_be_taken
&& !POINTER_TYPE_P (type
))
1228 if (integer_nonzerop (iv0
->step
))
1229 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1230 iv1
->base
, TYPE_MAX_VALUE (type
));
1232 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1233 iv0
->base
, TYPE_MIN_VALUE (type
));
1235 if (integer_zerop (assumption
))
1237 if (!integer_nonzerop (assumption
))
1238 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1239 niter
->assumptions
, assumption
);
1242 if (integer_nonzerop (iv0
->step
))
1244 if (POINTER_TYPE_P (type
))
1245 iv1
->base
= fold_build_pointer_plus_hwi (iv1
->base
, 1);
1247 iv1
->base
= fold_build2 (PLUS_EXPR
, type1
, iv1
->base
,
1248 build_int_cst (type1
, 1));
1250 else if (POINTER_TYPE_P (type
))
1251 iv0
->base
= fold_build_pointer_plus_hwi (iv0
->base
, -1);
1253 iv0
->base
= fold_build2 (MINUS_EXPR
, type1
,
1254 iv0
->base
, build_int_cst (type1
, 1));
1256 bounds_add (bnds
, double_int_one
, type1
);
1258 return number_of_iterations_lt (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1262 /* Dumps description of affine induction variable IV to FILE. */
1265 dump_affine_iv (FILE *file
, affine_iv
*iv
)
1267 if (!integer_zerop (iv
->step
))
1268 fprintf (file
, "[");
1270 print_generic_expr (dump_file
, iv
->base
, TDF_SLIM
);
1272 if (!integer_zerop (iv
->step
))
1274 fprintf (file
, ", + , ");
1275 print_generic_expr (dump_file
, iv
->step
, TDF_SLIM
);
1276 fprintf (file
, "]%s", iv
->no_overflow
? "(no_overflow)" : "");
1280 /* Determine the number of iterations according to condition (for staying
1281 inside loop) which compares two induction variables using comparison
1282 operator CODE. The induction variable on left side of the comparison
1283 is IV0, the right-hand side is IV1. Both induction variables must have
1284 type TYPE, which must be an integer or pointer type. The steps of the
1285 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1287 LOOP is the loop whose number of iterations we are determining.
1289 ONLY_EXIT is true if we are sure this is the only way the loop could be
1290 exited (including possibly non-returning function calls, exceptions, etc.)
1291 -- in this case we can use the information whether the control induction
1292 variables can overflow or not in a more efficient way.
1294 if EVERY_ITERATION is true, we know the test is executed on every iteration.
1296 The results (number of iterations and assumptions as described in
1297 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
1298 Returns false if it fails to determine number of iterations, true if it
1299 was determined (possibly with some assumptions). */
1302 number_of_iterations_cond (struct loop
*loop
,
1303 tree type
, affine_iv
*iv0
, enum tree_code code
,
1304 affine_iv
*iv1
, struct tree_niter_desc
*niter
,
1305 bool only_exit
, bool every_iteration
)
1307 bool exit_must_be_taken
= false, ret
;
1310 /* If the test is not executed every iteration, wrapping may make the test
1312 TODO: the overflow case can be still used as unreliable estimate of upper
1313 bound. But we have no API to pass it down to number of iterations code
1314 and, at present, it will not use it anyway. */
1315 if (!every_iteration
1316 && (!iv0
->no_overflow
|| !iv1
->no_overflow
1317 || code
== NE_EXPR
|| code
== EQ_EXPR
))
1320 /* The meaning of these assumptions is this:
1322 then the rest of information does not have to be valid
1323 if may_be_zero then the loop does not roll, even if
1325 niter
->assumptions
= boolean_true_node
;
1326 niter
->may_be_zero
= boolean_false_node
;
1327 niter
->niter
= NULL_TREE
;
1328 niter
->max
= double_int_zero
;
1330 niter
->bound
= NULL_TREE
;
1331 niter
->cmp
= ERROR_MARK
;
1333 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1334 the control variable is on lhs. */
1335 if (code
== GE_EXPR
|| code
== GT_EXPR
1336 || (code
== NE_EXPR
&& integer_zerop (iv0
->step
)))
1339 code
= swap_tree_comparison (code
);
1342 if (POINTER_TYPE_P (type
))
1344 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1345 to the same object. If they do, the control variable cannot wrap
1346 (as wrap around the bounds of memory will never return a pointer
1347 that would be guaranteed to point to the same object, even if we
1348 avoid undefined behavior by casting to size_t and back). */
1349 iv0
->no_overflow
= true;
1350 iv1
->no_overflow
= true;
1353 /* If the control induction variable does not overflow and the only exit
1354 from the loop is the one that we analyze, we know it must be taken
1358 if (!integer_zerop (iv0
->step
) && iv0
->no_overflow
)
1359 exit_must_be_taken
= true;
1360 else if (!integer_zerop (iv1
->step
) && iv1
->no_overflow
)
1361 exit_must_be_taken
= true;
1364 /* We can handle the case when neither of the sides of the comparison is
1365 invariant, provided that the test is NE_EXPR. This rarely occurs in
1366 practice, but it is simple enough to manage. */
1367 if (!integer_zerop (iv0
->step
) && !integer_zerop (iv1
->step
))
1369 tree step_type
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1370 if (code
!= NE_EXPR
)
1373 iv0
->step
= fold_binary_to_constant (MINUS_EXPR
, step_type
,
1374 iv0
->step
, iv1
->step
);
1375 iv0
->no_overflow
= false;
1376 iv1
->step
= build_int_cst (step_type
, 0);
1377 iv1
->no_overflow
= true;
1380 /* If the result of the comparison is a constant, the loop is weird. More
1381 precise handling would be possible, but the situation is not common enough
1382 to waste time on it. */
1383 if (integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
))
1386 /* Ignore loops of while (i-- < 10) type. */
1387 if (code
!= NE_EXPR
)
1389 if (iv0
->step
&& tree_int_cst_sign_bit (iv0
->step
))
1392 if (!integer_zerop (iv1
->step
) && !tree_int_cst_sign_bit (iv1
->step
))
1396 /* If the loop exits immediately, there is nothing to do. */
1397 tree tem
= fold_binary (code
, boolean_type_node
, iv0
->base
, iv1
->base
);
1398 if (tem
&& integer_zerop (tem
))
1400 niter
->niter
= build_int_cst (unsigned_type_for (type
), 0);
1401 niter
->max
= double_int_zero
;
1405 /* OK, now we know we have a senseful loop. Handle several cases, depending
1406 on what comparison operator is used. */
1407 bound_difference (loop
, iv1
->base
, iv0
->base
, &bnds
);
1409 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1412 "Analyzing # of iterations of loop %d\n", loop
->num
);
1414 fprintf (dump_file
, " exit condition ");
1415 dump_affine_iv (dump_file
, iv0
);
1416 fprintf (dump_file
, " %s ",
1417 code
== NE_EXPR
? "!="
1418 : code
== LT_EXPR
? "<"
1420 dump_affine_iv (dump_file
, iv1
);
1421 fprintf (dump_file
, "\n");
1423 fprintf (dump_file
, " bounds on difference of bases: ");
1424 mpz_out_str (dump_file
, 10, bnds
.below
);
1425 fprintf (dump_file
, " ... ");
1426 mpz_out_str (dump_file
, 10, bnds
.up
);
1427 fprintf (dump_file
, "\n");
1433 gcc_assert (integer_zerop (iv1
->step
));
1434 ret
= number_of_iterations_ne (type
, iv0
, iv1
->base
, niter
,
1435 exit_must_be_taken
, &bnds
);
1439 ret
= number_of_iterations_lt (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1444 ret
= number_of_iterations_le (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1452 mpz_clear (bnds
.up
);
1453 mpz_clear (bnds
.below
);
1455 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1459 fprintf (dump_file
, " result:\n");
1460 if (!integer_nonzerop (niter
->assumptions
))
1462 fprintf (dump_file
, " under assumptions ");
1463 print_generic_expr (dump_file
, niter
->assumptions
, TDF_SLIM
);
1464 fprintf (dump_file
, "\n");
1467 if (!integer_zerop (niter
->may_be_zero
))
1469 fprintf (dump_file
, " zero if ");
1470 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
1471 fprintf (dump_file
, "\n");
1474 fprintf (dump_file
, " # of iterations ");
1475 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
1476 fprintf (dump_file
, ", bounded by ");
1477 dump_double_int (dump_file
, niter
->max
, true);
1478 fprintf (dump_file
, "\n");
1481 fprintf (dump_file
, " failed\n\n");
1486 /* Substitute NEW for OLD in EXPR and fold the result. */
1489 simplify_replace_tree (tree expr
, tree old
, tree new_tree
)
1492 tree ret
= NULL_TREE
, e
, se
;
1497 /* Do not bother to replace constants. */
1498 if (CONSTANT_CLASS_P (old
))
1502 || operand_equal_p (expr
, old
, 0))
1503 return unshare_expr (new_tree
);
1508 n
= TREE_OPERAND_LENGTH (expr
);
1509 for (i
= 0; i
< n
; i
++)
1511 e
= TREE_OPERAND (expr
, i
);
1512 se
= simplify_replace_tree (e
, old
, new_tree
);
1517 ret
= copy_node (expr
);
1519 TREE_OPERAND (ret
, i
) = se
;
1522 return (ret
? fold (ret
) : expr
);
1525 /* Expand definitions of ssa names in EXPR as long as they are simple
1526 enough, and return the new expression. */
1529 expand_simple_operations (tree expr
)
1532 tree ret
= NULL_TREE
, e
, ee
, e1
;
1533 enum tree_code code
;
1536 if (expr
== NULL_TREE
)
1539 if (is_gimple_min_invariant (expr
))
1542 code
= TREE_CODE (expr
);
1543 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
1545 n
= TREE_OPERAND_LENGTH (expr
);
1546 for (i
= 0; i
< n
; i
++)
1548 e
= TREE_OPERAND (expr
, i
);
1549 ee
= expand_simple_operations (e
);
1554 ret
= copy_node (expr
);
1556 TREE_OPERAND (ret
, i
) = ee
;
1562 fold_defer_overflow_warnings ();
1564 fold_undefer_and_ignore_overflow_warnings ();
1568 if (TREE_CODE (expr
) != SSA_NAME
)
1571 stmt
= SSA_NAME_DEF_STMT (expr
);
1572 if (gimple_code (stmt
) == GIMPLE_PHI
)
1574 basic_block src
, dest
;
1576 if (gimple_phi_num_args (stmt
) != 1)
1578 e
= PHI_ARG_DEF (stmt
, 0);
1580 /* Avoid propagating through loop exit phi nodes, which
1581 could break loop-closed SSA form restrictions. */
1582 dest
= gimple_bb (stmt
);
1583 src
= single_pred (dest
);
1584 if (TREE_CODE (e
) == SSA_NAME
1585 && src
->loop_father
!= dest
->loop_father
)
1588 return expand_simple_operations (e
);
1590 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1593 /* Avoid expanding to expressions that contain SSA names that need
1594 to take part in abnormal coalescing. */
1596 FOR_EACH_SSA_TREE_OPERAND (e
, stmt
, iter
, SSA_OP_USE
)
1597 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (e
))
1600 e
= gimple_assign_rhs1 (stmt
);
1601 code
= gimple_assign_rhs_code (stmt
);
1602 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1604 if (is_gimple_min_invariant (e
))
1607 if (code
== SSA_NAME
)
1608 return expand_simple_operations (e
);
1616 /* Casts are simple. */
1617 ee
= expand_simple_operations (e
);
1618 return fold_build1 (code
, TREE_TYPE (expr
), ee
);
1622 case POINTER_PLUS_EXPR
:
1623 /* And increments and decrements by a constant are simple. */
1624 e1
= gimple_assign_rhs2 (stmt
);
1625 if (!is_gimple_min_invariant (e1
))
1628 ee
= expand_simple_operations (e
);
1629 return fold_build2 (code
, TREE_TYPE (expr
), ee
, e1
);
1636 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1637 expression (or EXPR unchanged, if no simplification was possible). */
1640 tree_simplify_using_condition_1 (tree cond
, tree expr
)
1643 tree e
, te
, e0
, e1
, e2
, notcond
;
1644 enum tree_code code
= TREE_CODE (expr
);
1646 if (code
== INTEGER_CST
)
1649 if (code
== TRUTH_OR_EXPR
1650 || code
== TRUTH_AND_EXPR
1651 || code
== COND_EXPR
)
1655 e0
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 0));
1656 if (TREE_OPERAND (expr
, 0) != e0
)
1659 e1
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 1));
1660 if (TREE_OPERAND (expr
, 1) != e1
)
1663 if (code
== COND_EXPR
)
1665 e2
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 2));
1666 if (TREE_OPERAND (expr
, 2) != e2
)
1674 if (code
== COND_EXPR
)
1675 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1677 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1683 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
1684 propagation, and vice versa. Fold does not handle this, since it is
1685 considered too expensive. */
1686 if (TREE_CODE (cond
) == EQ_EXPR
)
1688 e0
= TREE_OPERAND (cond
, 0);
1689 e1
= TREE_OPERAND (cond
, 1);
1691 /* We know that e0 == e1. Check whether we cannot simplify expr
1693 e
= simplify_replace_tree (expr
, e0
, e1
);
1694 if (integer_zerop (e
) || integer_nonzerop (e
))
1697 e
= simplify_replace_tree (expr
, e1
, e0
);
1698 if (integer_zerop (e
) || integer_nonzerop (e
))
1701 if (TREE_CODE (expr
) == EQ_EXPR
)
1703 e0
= TREE_OPERAND (expr
, 0);
1704 e1
= TREE_OPERAND (expr
, 1);
1706 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
1707 e
= simplify_replace_tree (cond
, e0
, e1
);
1708 if (integer_zerop (e
))
1710 e
= simplify_replace_tree (cond
, e1
, e0
);
1711 if (integer_zerop (e
))
1714 if (TREE_CODE (expr
) == NE_EXPR
)
1716 e0
= TREE_OPERAND (expr
, 0);
1717 e1
= TREE_OPERAND (expr
, 1);
1719 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
1720 e
= simplify_replace_tree (cond
, e0
, e1
);
1721 if (integer_zerop (e
))
1722 return boolean_true_node
;
1723 e
= simplify_replace_tree (cond
, e1
, e0
);
1724 if (integer_zerop (e
))
1725 return boolean_true_node
;
1728 te
= expand_simple_operations (expr
);
1730 /* Check whether COND ==> EXPR. */
1731 notcond
= invert_truthvalue (cond
);
1732 e
= fold_binary (TRUTH_OR_EXPR
, boolean_type_node
, notcond
, te
);
1733 if (e
&& integer_nonzerop (e
))
1736 /* Check whether COND ==> not EXPR. */
1737 e
= fold_binary (TRUTH_AND_EXPR
, boolean_type_node
, cond
, te
);
1738 if (e
&& integer_zerop (e
))
1744 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1745 expression (or EXPR unchanged, if no simplification was possible).
1746 Wrapper around tree_simplify_using_condition_1 that ensures that chains
1747 of simple operations in definitions of ssa names in COND are expanded,
1748 so that things like casts or incrementing the value of the bound before
1749 the loop do not cause us to fail. */
1752 tree_simplify_using_condition (tree cond
, tree expr
)
1754 cond
= expand_simple_operations (cond
);
1756 return tree_simplify_using_condition_1 (cond
, expr
);
1759 /* Tries to simplify EXPR using the conditions on entry to LOOP.
1760 Returns the simplified expression (or EXPR unchanged, if no
1761 simplification was possible).*/
1764 simplify_using_initial_conditions (struct loop
*loop
, tree expr
)
1772 if (TREE_CODE (expr
) == INTEGER_CST
)
1775 /* Limit walking the dominators to avoid quadraticness in
1776 the number of BBs times the number of loops in degenerate
1778 for (bb
= loop
->header
;
1779 bb
!= ENTRY_BLOCK_PTR
&& cnt
< MAX_DOMINATORS_TO_WALK
;
1780 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1782 if (!single_pred_p (bb
))
1784 e
= single_pred_edge (bb
);
1786 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
1789 stmt
= last_stmt (e
->src
);
1790 cond
= fold_build2 (gimple_cond_code (stmt
),
1792 gimple_cond_lhs (stmt
),
1793 gimple_cond_rhs (stmt
));
1794 if (e
->flags
& EDGE_FALSE_VALUE
)
1795 cond
= invert_truthvalue (cond
);
1796 expr
= tree_simplify_using_condition (cond
, expr
);
1803 /* Tries to simplify EXPR using the evolutions of the loop invariants
1804 in the superloops of LOOP. Returns the simplified expression
1805 (or EXPR unchanged, if no simplification was possible). */
1808 simplify_using_outer_evolutions (struct loop
*loop
, tree expr
)
1810 enum tree_code code
= TREE_CODE (expr
);
1814 if (is_gimple_min_invariant (expr
))
1817 if (code
== TRUTH_OR_EXPR
1818 || code
== TRUTH_AND_EXPR
1819 || code
== COND_EXPR
)
1823 e0
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 0));
1824 if (TREE_OPERAND (expr
, 0) != e0
)
1827 e1
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 1));
1828 if (TREE_OPERAND (expr
, 1) != e1
)
1831 if (code
== COND_EXPR
)
1833 e2
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 2));
1834 if (TREE_OPERAND (expr
, 2) != e2
)
1842 if (code
== COND_EXPR
)
1843 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1845 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1851 e
= instantiate_parameters (loop
, expr
);
1852 if (is_gimple_min_invariant (e
))
1858 /* Returns true if EXIT is the only possible exit from LOOP. */
1861 loop_only_exit_p (const struct loop
*loop
, const_edge exit
)
1864 gimple_stmt_iterator bsi
;
1868 if (exit
!= single_exit (loop
))
1871 body
= get_loop_body (loop
);
1872 for (i
= 0; i
< loop
->num_nodes
; i
++)
1874 for (bsi
= gsi_start_bb (body
[i
]); !gsi_end_p (bsi
); gsi_next (&bsi
))
1876 call
= gsi_stmt (bsi
);
1877 if (gimple_code (call
) != GIMPLE_CALL
)
1880 if (gimple_has_side_effects (call
))
1892 /* Stores description of number of iterations of LOOP derived from
1893 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
1894 useful information could be derived (and fields of NITER has
1895 meaning described in comments at struct tree_niter_desc
1896 declaration), false otherwise. If WARN is true and
1897 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1898 potentially unsafe assumptions.
1899 When EVERY_ITERATION is true, only tests that are known to be executed
1900 every iteration are considered (i.e. only test that alone bounds the loop).
1904 number_of_iterations_exit (struct loop
*loop
, edge exit
,
1905 struct tree_niter_desc
*niter
,
1906 bool warn
, bool every_iteration
)
1911 enum tree_code code
;
1915 safe
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit
->src
);
1917 if (every_iteration
&& !safe
)
1920 niter
->assumptions
= boolean_false_node
;
1921 stmt
= last_stmt (exit
->src
);
1922 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1925 /* We want the condition for staying inside loop. */
1926 code
= gimple_cond_code (stmt
);
1927 if (exit
->flags
& EDGE_TRUE_VALUE
)
1928 code
= invert_tree_comparison (code
, false);
1943 op0
= gimple_cond_lhs (stmt
);
1944 op1
= gimple_cond_rhs (stmt
);
1945 type
= TREE_TYPE (op0
);
1947 if (TREE_CODE (type
) != INTEGER_TYPE
1948 && !POINTER_TYPE_P (type
))
1951 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, false))
1953 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, false))
1956 /* We don't want to see undefined signed overflow warnings while
1957 computing the number of iterations. */
1958 fold_defer_overflow_warnings ();
1960 iv0
.base
= expand_simple_operations (iv0
.base
);
1961 iv1
.base
= expand_simple_operations (iv1
.base
);
1962 if (!number_of_iterations_cond (loop
, type
, &iv0
, code
, &iv1
, niter
,
1963 loop_only_exit_p (loop
, exit
), safe
))
1965 fold_undefer_and_ignore_overflow_warnings ();
1971 niter
->assumptions
= simplify_using_outer_evolutions (loop
,
1972 niter
->assumptions
);
1973 niter
->may_be_zero
= simplify_using_outer_evolutions (loop
,
1974 niter
->may_be_zero
);
1975 niter
->niter
= simplify_using_outer_evolutions (loop
, niter
->niter
);
1979 = simplify_using_initial_conditions (loop
,
1980 niter
->assumptions
);
1982 = simplify_using_initial_conditions (loop
,
1983 niter
->may_be_zero
);
1985 fold_undefer_and_ignore_overflow_warnings ();
1987 /* If NITER has simplified into a constant, update MAX. */
1988 if (TREE_CODE (niter
->niter
) == INTEGER_CST
)
1989 niter
->max
= tree_to_double_int (niter
->niter
);
1991 if (integer_onep (niter
->assumptions
))
1994 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1995 But if we can prove that there is overflow or some other source of weird
1996 behavior, ignore the loop even with -funsafe-loop-optimizations. */
1997 if (integer_zerop (niter
->assumptions
) || !single_exit (loop
))
2000 if (flag_unsafe_loop_optimizations
)
2001 niter
->assumptions
= boolean_true_node
;
2005 const char *wording
;
2006 location_t loc
= gimple_location (stmt
);
2008 /* We can provide a more specific warning if one of the operator is
2009 constant and the other advances by +1 or -1. */
2010 if (!integer_zerop (iv1
.step
)
2011 ? (integer_zerop (iv0
.step
)
2012 && (integer_onep (iv1
.step
) || integer_all_onesp (iv1
.step
)))
2013 : (integer_onep (iv0
.step
) || integer_all_onesp (iv0
.step
)))
2015 flag_unsafe_loop_optimizations
2016 ? N_("assuming that the loop is not infinite")
2017 : N_("cannot optimize possibly infinite loops");
2020 flag_unsafe_loop_optimizations
2021 ? N_("assuming that the loop counter does not overflow")
2022 : N_("cannot optimize loop, the loop counter may overflow");
2024 warning_at ((LOCATION_LINE (loc
) > 0) ? loc
: input_location
,
2025 OPT_Wunsafe_loop_optimizations
, "%s", gettext (wording
));
2028 return flag_unsafe_loop_optimizations
;
2031 /* Try to determine the number of iterations of LOOP. If we succeed,
2032 expression giving number of iterations is returned and *EXIT is
2033 set to the edge from that the information is obtained. Otherwise
2034 chrec_dont_know is returned. */
2037 find_loop_niter (struct loop
*loop
, edge
*exit
)
2040 vec
<edge
> exits
= get_loop_exit_edges (loop
);
2042 tree niter
= NULL_TREE
, aniter
;
2043 struct tree_niter_desc desc
;
2046 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2048 if (!number_of_iterations_exit (loop
, ex
, &desc
, false))
2051 if (integer_nonzerop (desc
.may_be_zero
))
2053 /* We exit in the first iteration through this exit.
2054 We won't find anything better. */
2055 niter
= build_int_cst (unsigned_type_node
, 0);
2060 if (!integer_zerop (desc
.may_be_zero
))
2063 aniter
= desc
.niter
;
2067 /* Nothing recorded yet. */
2073 /* Prefer constants, the lower the better. */
2074 if (TREE_CODE (aniter
) != INTEGER_CST
)
2077 if (TREE_CODE (niter
) != INTEGER_CST
)
2084 if (tree_int_cst_lt (aniter
, niter
))
2093 return niter
? niter
: chrec_dont_know
;
2096 /* Return true if loop is known to have bounded number of iterations. */
2099 finite_loop_p (struct loop
*loop
)
2104 if (flag_unsafe_loop_optimizations
)
2106 flags
= flags_from_decl_or_type (current_function_decl
);
2107 if ((flags
& (ECF_CONST
|ECF_PURE
)) && !(flags
& ECF_LOOPING_CONST_OR_PURE
))
2109 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2110 fprintf (dump_file
, "Found loop %i to be finite: it is within pure or const function.\n",
2115 if (loop
->any_upper_bound
2116 || max_loop_iterations (loop
, &nit
))
2118 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2119 fprintf (dump_file
, "Found loop %i to be finite: upper bound found.\n",
2128 Analysis of a number of iterations of a loop by a brute-force evaluation.
2132 /* Bound on the number of iterations we try to evaluate. */
2134 #define MAX_ITERATIONS_TO_TRACK \
2135 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
2137 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
2138 result by a chain of operations such that all but exactly one of their
2139 operands are constants. */
2142 chain_of_csts_start (struct loop
*loop
, tree x
)
2144 gimple stmt
= SSA_NAME_DEF_STMT (x
);
2146 basic_block bb
= gimple_bb (stmt
);
2147 enum tree_code code
;
2150 || !flow_bb_inside_loop_p (loop
, bb
))
2153 if (gimple_code (stmt
) == GIMPLE_PHI
)
2155 if (bb
== loop
->header
)
2161 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2164 code
= gimple_assign_rhs_code (stmt
);
2165 if (gimple_references_memory_p (stmt
)
2166 || TREE_CODE_CLASS (code
) == tcc_reference
2167 || (code
== ADDR_EXPR
2168 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
2171 use
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
2172 if (use
== NULL_TREE
)
2175 return chain_of_csts_start (loop
, use
);
2178 /* Determines whether the expression X is derived from a result of a phi node
2179 in header of LOOP such that
2181 * the derivation of X consists only from operations with constants
2182 * the initial value of the phi node is constant
2183 * the value of the phi node in the next iteration can be derived from the
2184 value in the current iteration by a chain of operations with constants.
2186 If such phi node exists, it is returned, otherwise NULL is returned. */
2189 get_base_for (struct loop
*loop
, tree x
)
2194 if (is_gimple_min_invariant (x
))
2197 phi
= chain_of_csts_start (loop
, x
);
2201 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2202 next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2204 if (TREE_CODE (next
) != SSA_NAME
)
2207 if (!is_gimple_min_invariant (init
))
2210 if (chain_of_csts_start (loop
, next
) != phi
)
2216 /* Given an expression X, then
2218 * if X is NULL_TREE, we return the constant BASE.
2219 * otherwise X is a SSA name, whose value in the considered loop is derived
2220 by a chain of operations with constant from a result of a phi node in
2221 the header of the loop. Then we return value of X when the value of the
2222 result of this phi node is given by the constant BASE. */
2225 get_val_for (tree x
, tree base
)
2229 gcc_assert (is_gimple_min_invariant (base
));
2234 stmt
= SSA_NAME_DEF_STMT (x
);
2235 if (gimple_code (stmt
) == GIMPLE_PHI
)
2238 gcc_assert (is_gimple_assign (stmt
));
2240 /* STMT must be either an assignment of a single SSA name or an
2241 expression involving an SSA name and a constant. Try to fold that
2242 expression using the value for the SSA name. */
2243 if (gimple_assign_ssa_name_copy_p (stmt
))
2244 return get_val_for (gimple_assign_rhs1 (stmt
), base
);
2245 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_UNARY_RHS
2246 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
2248 return fold_build1 (gimple_assign_rhs_code (stmt
),
2249 gimple_expr_type (stmt
),
2250 get_val_for (gimple_assign_rhs1 (stmt
), base
));
2252 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_BINARY_RHS
)
2254 tree rhs1
= gimple_assign_rhs1 (stmt
);
2255 tree rhs2
= gimple_assign_rhs2 (stmt
);
2256 if (TREE_CODE (rhs1
) == SSA_NAME
)
2257 rhs1
= get_val_for (rhs1
, base
);
2258 else if (TREE_CODE (rhs2
) == SSA_NAME
)
2259 rhs2
= get_val_for (rhs2
, base
);
2262 return fold_build2 (gimple_assign_rhs_code (stmt
),
2263 gimple_expr_type (stmt
), rhs1
, rhs2
);
2270 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2271 by brute force -- i.e. by determining the value of the operands of the
2272 condition at EXIT in first few iterations of the loop (assuming that
2273 these values are constant) and determining the first one in that the
2274 condition is not satisfied. Returns the constant giving the number
2275 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
2278 loop_niter_by_eval (struct loop
*loop
, edge exit
)
2281 tree op
[2], val
[2], next
[2], aval
[2];
2286 cond
= last_stmt (exit
->src
);
2287 if (!cond
|| gimple_code (cond
) != GIMPLE_COND
)
2288 return chrec_dont_know
;
2290 cmp
= gimple_cond_code (cond
);
2291 if (exit
->flags
& EDGE_TRUE_VALUE
)
2292 cmp
= invert_tree_comparison (cmp
, false);
2302 op
[0] = gimple_cond_lhs (cond
);
2303 op
[1] = gimple_cond_rhs (cond
);
2307 return chrec_dont_know
;
2310 for (j
= 0; j
< 2; j
++)
2312 if (is_gimple_min_invariant (op
[j
]))
2315 next
[j
] = NULL_TREE
;
2320 phi
= get_base_for (loop
, op
[j
]);
2322 return chrec_dont_know
;
2323 val
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2324 next
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2328 /* Don't issue signed overflow warnings. */
2329 fold_defer_overflow_warnings ();
2331 for (i
= 0; i
< MAX_ITERATIONS_TO_TRACK
; i
++)
2333 for (j
= 0; j
< 2; j
++)
2334 aval
[j
] = get_val_for (op
[j
], val
[j
]);
2336 acnd
= fold_binary (cmp
, boolean_type_node
, aval
[0], aval
[1]);
2337 if (acnd
&& integer_zerop (acnd
))
2339 fold_undefer_and_ignore_overflow_warnings ();
2340 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2342 "Proved that loop %d iterates %d times using brute force.\n",
2344 return build_int_cst (unsigned_type_node
, i
);
2347 for (j
= 0; j
< 2; j
++)
2349 val
[j
] = get_val_for (next
[j
], val
[j
]);
2350 if (!is_gimple_min_invariant (val
[j
]))
2352 fold_undefer_and_ignore_overflow_warnings ();
2353 return chrec_dont_know
;
2358 fold_undefer_and_ignore_overflow_warnings ();
2360 return chrec_dont_know
;
2363 /* Finds the exit of the LOOP by that the loop exits after a constant
2364 number of iterations and stores the exit edge to *EXIT. The constant
2365 giving the number of iterations of LOOP is returned. The number of
2366 iterations is determined using loop_niter_by_eval (i.e. by brute force
2367 evaluation). If we are unable to find the exit for that loop_niter_by_eval
2368 determines the number of iterations, chrec_dont_know is returned. */
2371 find_loop_niter_by_eval (struct loop
*loop
, edge
*exit
)
2374 vec
<edge
> exits
= get_loop_exit_edges (loop
);
2376 tree niter
= NULL_TREE
, aniter
;
2380 /* Loops with multiple exits are expensive to handle and less important. */
2381 if (!flag_expensive_optimizations
2382 && exits
.length () > 1)
2385 return chrec_dont_know
;
2388 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2390 if (!just_once_each_iteration_p (loop
, ex
->src
))
2393 aniter
= loop_niter_by_eval (loop
, ex
);
2394 if (chrec_contains_undetermined (aniter
))
2398 && !tree_int_cst_lt (aniter
, niter
))
2406 return niter
? niter
: chrec_dont_know
;
2411 Analysis of upper bounds on number of iterations of a loop.
2415 static double_int
derive_constant_upper_bound_ops (tree
, tree
,
2416 enum tree_code
, tree
);
2418 /* Returns a constant upper bound on the value of the right-hand side of
2419 an assignment statement STMT. */
2422 derive_constant_upper_bound_assign (gimple stmt
)
2424 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2425 tree op0
= gimple_assign_rhs1 (stmt
);
2426 tree op1
= gimple_assign_rhs2 (stmt
);
2428 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt
)),
2432 /* Returns a constant upper bound on the value of expression VAL. VAL
2433 is considered to be unsigned. If its type is signed, its value must
2437 derive_constant_upper_bound (tree val
)
2439 enum tree_code code
;
2442 extract_ops_from_tree (val
, &code
, &op0
, &op1
);
2443 return derive_constant_upper_bound_ops (TREE_TYPE (val
), op0
, code
, op1
);
2446 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
2447 whose type is TYPE. The expression is considered to be unsigned. If
2448 its type is signed, its value must be nonnegative. */
2451 derive_constant_upper_bound_ops (tree type
, tree op0
,
2452 enum tree_code code
, tree op1
)
2455 double_int bnd
, max
, mmax
, cst
;
2458 if (INTEGRAL_TYPE_P (type
))
2459 maxt
= TYPE_MAX_VALUE (type
);
2461 maxt
= upper_bound_in_type (type
, type
);
2463 max
= tree_to_double_int (maxt
);
2468 return tree_to_double_int (op0
);
2471 subtype
= TREE_TYPE (op0
);
2472 if (!TYPE_UNSIGNED (subtype
)
2473 /* If TYPE is also signed, the fact that VAL is nonnegative implies
2474 that OP0 is nonnegative. */
2475 && TYPE_UNSIGNED (type
)
2476 && !tree_expr_nonnegative_p (op0
))
2478 /* If we cannot prove that the casted expression is nonnegative,
2479 we cannot establish more useful upper bound than the precision
2480 of the type gives us. */
2484 /* We now know that op0 is an nonnegative value. Try deriving an upper
2486 bnd
= derive_constant_upper_bound (op0
);
2488 /* If the bound does not fit in TYPE, max. value of TYPE could be
2496 case POINTER_PLUS_EXPR
:
2498 if (TREE_CODE (op1
) != INTEGER_CST
2499 || !tree_expr_nonnegative_p (op0
))
2502 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
2503 choose the most logical way how to treat this constant regardless
2504 of the signedness of the type. */
2505 cst
= tree_to_double_int (op1
);
2506 cst
= cst
.sext (TYPE_PRECISION (type
));
2507 if (code
!= MINUS_EXPR
)
2510 bnd
= derive_constant_upper_bound (op0
);
2512 if (cst
.is_negative ())
2515 /* Avoid CST == 0x80000... */
2516 if (cst
.is_negative ())
2519 /* OP0 + CST. We need to check that
2520 BND <= MAX (type) - CST. */
2530 /* OP0 - CST, where CST >= 0.
2532 If TYPE is signed, we have already verified that OP0 >= 0, and we
2533 know that the result is nonnegative. This implies that
2536 If TYPE is unsigned, we must additionally know that OP0 >= CST,
2537 otherwise the operation underflows.
2540 /* This should only happen if the type is unsigned; however, for
2541 buggy programs that use overflowing signed arithmetics even with
2542 -fno-wrapv, this condition may also be true for signed values. */
2546 if (TYPE_UNSIGNED (type
))
2548 tree tem
= fold_binary (GE_EXPR
, boolean_type_node
, op0
,
2549 double_int_to_tree (type
, cst
));
2550 if (!tem
|| integer_nonzerop (tem
))
2559 case FLOOR_DIV_EXPR
:
2560 case EXACT_DIV_EXPR
:
2561 if (TREE_CODE (op1
) != INTEGER_CST
2562 || tree_int_cst_sign_bit (op1
))
2565 bnd
= derive_constant_upper_bound (op0
);
2566 return bnd
.udiv (tree_to_double_int (op1
), FLOOR_DIV_EXPR
);
2569 if (TREE_CODE (op1
) != INTEGER_CST
2570 || tree_int_cst_sign_bit (op1
))
2572 return tree_to_double_int (op1
);
2575 stmt
= SSA_NAME_DEF_STMT (op0
);
2576 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2577 || gimple_assign_lhs (stmt
) != op0
)
2579 return derive_constant_upper_bound_assign (stmt
);
2586 /* Emit a -Waggressive-loop-optimizations warning if needed. */
2589 do_warn_aggressive_loop_optimizations (struct loop
*loop
,
2590 double_int i_bound
, gimple stmt
)
2592 /* Don't warn if the loop doesn't have known constant bound. */
2593 if (!loop
->nb_iterations
2594 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
2595 || !warn_aggressive_loop_optimizations
2596 /* To avoid warning multiple times for the same loop,
2597 only start warning when we preserve loops. */
2598 || (cfun
->curr_properties
& PROP_loops
) == 0
2599 /* Only warn once per loop. */
2600 || loop
->warned_aggressive_loop_optimizations
2601 /* Only warn if undefined behavior gives us lower estimate than the
2602 known constant bound. */
2603 || i_bound
.ucmp (tree_to_double_int (loop
->nb_iterations
)) >= 0
2604 /* And undefined behavior happens unconditionally. */
2605 || !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (stmt
)))
2608 edge e
= single_exit (loop
);
2612 gimple estmt
= last_stmt (e
->src
);
2613 if (warning_at (gimple_location (stmt
), OPT_Waggressive_loop_optimizations
,
2614 "iteration %E invokes undefined behavior",
2615 double_int_to_tree (TREE_TYPE (loop
->nb_iterations
),
2617 inform (gimple_location (estmt
), "containing loop");
2618 loop
->warned_aggressive_loop_optimizations
= true;
2621 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
2622 is true if the loop is exited immediately after STMT, and this exit
2623 is taken at last when the STMT is executed BOUND + 1 times.
2624 REALISTIC is true if BOUND is expected to be close to the real number
2625 of iterations. UPPER is true if we are sure the loop iterates at most
2626 BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */
2629 record_estimate (struct loop
*loop
, tree bound
, double_int i_bound
,
2630 gimple at_stmt
, bool is_exit
, bool realistic
, bool upper
)
2634 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2636 fprintf (dump_file
, "Statement %s", is_exit
? "(exit)" : "");
2637 print_gimple_stmt (dump_file
, at_stmt
, 0, TDF_SLIM
);
2638 fprintf (dump_file
, " is %sexecuted at most ",
2639 upper
? "" : "probably ");
2640 print_generic_expr (dump_file
, bound
, TDF_SLIM
);
2641 fprintf (dump_file
, " (bounded by ");
2642 dump_double_int (dump_file
, i_bound
, true);
2643 fprintf (dump_file
, ") + 1 times in loop %d.\n", loop
->num
);
2646 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
2647 real number of iterations. */
2648 if (TREE_CODE (bound
) != INTEGER_CST
)
2651 gcc_checking_assert (i_bound
== tree_to_double_int (bound
));
2652 if (!upper
&& !realistic
)
2655 /* If we have a guaranteed upper bound, record it in the appropriate
2656 list, unless this is an !is_exit bound (i.e. undefined behavior in
2657 at_stmt) in a loop with known constant number of iterations. */
2660 || loop
->nb_iterations
== NULL_TREE
2661 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
))
2663 struct nb_iter_bound
*elt
= ggc_alloc_nb_iter_bound ();
2665 elt
->bound
= i_bound
;
2666 elt
->stmt
= at_stmt
;
2667 elt
->is_exit
= is_exit
;
2668 elt
->next
= loop
->bounds
;
2672 /* If statement is executed on every path to the loop latch, we can directly
2673 infer the upper bound on the # of iterations of the loop. */
2674 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (at_stmt
)))
2677 /* Update the number of iteration estimates according to the bound.
2678 If at_stmt is an exit then the loop latch is executed at most BOUND times,
2679 otherwise it can be executed BOUND + 1 times. We will lower the estimate
2680 later if such statement must be executed on last iteration */
2682 delta
= double_int_zero
;
2684 delta
= double_int_one
;
2687 /* If an overflow occurred, ignore the result. */
2688 if (i_bound
.ult (delta
))
2691 if (upper
&& !is_exit
)
2692 do_warn_aggressive_loop_optimizations (loop
, i_bound
, at_stmt
);
2693 record_niter_bound (loop
, i_bound
, realistic
, upper
);
2696 /* Record the estimate on number of iterations of LOOP based on the fact that
2697 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
2698 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
2699 estimated number of iterations is expected to be close to the real one.
2700 UPPER is true if we are sure the induction variable does not wrap. */
2703 record_nonwrapping_iv (struct loop
*loop
, tree base
, tree step
, gimple stmt
,
2704 tree low
, tree high
, bool realistic
, bool upper
)
2706 tree niter_bound
, extreme
, delta
;
2707 tree type
= TREE_TYPE (base
), unsigned_type
;
2710 if (TREE_CODE (step
) != INTEGER_CST
|| integer_zerop (step
))
2713 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2715 fprintf (dump_file
, "Induction variable (");
2716 print_generic_expr (dump_file
, TREE_TYPE (base
), TDF_SLIM
);
2717 fprintf (dump_file
, ") ");
2718 print_generic_expr (dump_file
, base
, TDF_SLIM
);
2719 fprintf (dump_file
, " + ");
2720 print_generic_expr (dump_file
, step
, TDF_SLIM
);
2721 fprintf (dump_file
, " * iteration does not wrap in statement ");
2722 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2723 fprintf (dump_file
, " in loop %d.\n", loop
->num
);
2726 unsigned_type
= unsigned_type_for (type
);
2727 base
= fold_convert (unsigned_type
, base
);
2728 step
= fold_convert (unsigned_type
, step
);
2730 if (tree_int_cst_sign_bit (step
))
2732 extreme
= fold_convert (unsigned_type
, low
);
2733 if (TREE_CODE (base
) != INTEGER_CST
)
2734 base
= fold_convert (unsigned_type
, high
);
2735 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
2736 step
= fold_build1 (NEGATE_EXPR
, unsigned_type
, step
);
2740 extreme
= fold_convert (unsigned_type
, high
);
2741 if (TREE_CODE (base
) != INTEGER_CST
)
2742 base
= fold_convert (unsigned_type
, low
);
2743 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
2746 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
2747 would get out of the range. */
2748 niter_bound
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step
);
2749 max
= derive_constant_upper_bound (niter_bound
);
2750 record_estimate (loop
, niter_bound
, max
, stmt
, false, realistic
, upper
);
2753 /* Determine information about number of iterations a LOOP from the index
2754 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
2755 guaranteed to be executed in every iteration of LOOP. Callback for
2765 idx_infer_loop_bounds (tree base
, tree
*idx
, void *dta
)
2767 struct ilb_data
*data
= (struct ilb_data
*) dta
;
2768 tree ev
, init
, step
;
2769 tree low
, high
, type
, next
;
2770 bool sign
, upper
= true, at_end
= false;
2771 struct loop
*loop
= data
->loop
;
2772 bool reliable
= true;
2774 if (TREE_CODE (base
) != ARRAY_REF
)
2777 /* For arrays at the end of the structure, we are not guaranteed that they
2778 do not really extend over their declared size. However, for arrays of
2779 size greater than one, this is unlikely to be intended. */
2780 if (array_at_struct_end_p (base
))
2786 struct loop
*dloop
= loop_containing_stmt (data
->stmt
);
2790 ev
= analyze_scalar_evolution (dloop
, *idx
);
2791 ev
= instantiate_parameters (loop
, ev
);
2792 init
= initial_condition (ev
);
2793 step
= evolution_part_in_loop_num (ev
, loop
->num
);
2797 || TREE_CODE (step
) != INTEGER_CST
2798 || integer_zerop (step
)
2799 || tree_contains_chrecs (init
, NULL
)
2800 || chrec_contains_symbols_defined_in_loop (init
, loop
->num
))
2803 low
= array_ref_low_bound (base
);
2804 high
= array_ref_up_bound (base
);
2806 /* The case of nonconstant bounds could be handled, but it would be
2808 if (TREE_CODE (low
) != INTEGER_CST
2810 || TREE_CODE (high
) != INTEGER_CST
)
2812 sign
= tree_int_cst_sign_bit (step
);
2813 type
= TREE_TYPE (step
);
2815 /* The array of length 1 at the end of a structure most likely extends
2816 beyond its bounds. */
2818 && operand_equal_p (low
, high
, 0))
2821 /* In case the relevant bound of the array does not fit in type, or
2822 it does, but bound + step (in type) still belongs into the range of the
2823 array, the index may wrap and still stay within the range of the array
2824 (consider e.g. if the array is indexed by the full range of
2827 To make things simpler, we require both bounds to fit into type, although
2828 there are cases where this would not be strictly necessary. */
2829 if (!int_fits_type_p (high
, type
)
2830 || !int_fits_type_p (low
, type
))
2832 low
= fold_convert (type
, low
);
2833 high
= fold_convert (type
, high
);
2836 next
= fold_binary (PLUS_EXPR
, type
, low
, step
);
2838 next
= fold_binary (PLUS_EXPR
, type
, high
, step
);
2840 if (tree_int_cst_compare (low
, next
) <= 0
2841 && tree_int_cst_compare (next
, high
) <= 0)
2844 /* If access is not executed on every iteration, we must ensure that overlow may
2845 not make the access valid later. */
2846 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (data
->stmt
))
2847 && scev_probably_wraps_p (initial_condition_in_loop_num (ev
, loop
->num
),
2848 step
, data
->stmt
, loop
, true))
2851 record_nonwrapping_iv (loop
, init
, step
, data
->stmt
, low
, high
, reliable
, upper
);
2855 /* Determine information about number of iterations a LOOP from the bounds
2856 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
2857 STMT is guaranteed to be executed in every iteration of LOOP.*/
2860 infer_loop_bounds_from_ref (struct loop
*loop
, gimple stmt
, tree ref
)
2862 struct ilb_data data
;
2866 for_each_index (&ref
, idx_infer_loop_bounds
, &data
);
2869 /* Determine information about number of iterations of a LOOP from the way
2870 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
2871 executed in every iteration of LOOP. */
2874 infer_loop_bounds_from_array (struct loop
*loop
, gimple stmt
)
2876 if (is_gimple_assign (stmt
))
2878 tree op0
= gimple_assign_lhs (stmt
);
2879 tree op1
= gimple_assign_rhs1 (stmt
);
2881 /* For each memory access, analyze its access function
2882 and record a bound on the loop iteration domain. */
2883 if (REFERENCE_CLASS_P (op0
))
2884 infer_loop_bounds_from_ref (loop
, stmt
, op0
);
2886 if (REFERENCE_CLASS_P (op1
))
2887 infer_loop_bounds_from_ref (loop
, stmt
, op1
);
2889 else if (is_gimple_call (stmt
))
2892 unsigned i
, n
= gimple_call_num_args (stmt
);
2894 lhs
= gimple_call_lhs (stmt
);
2895 if (lhs
&& REFERENCE_CLASS_P (lhs
))
2896 infer_loop_bounds_from_ref (loop
, stmt
, lhs
);
2898 for (i
= 0; i
< n
; i
++)
2900 arg
= gimple_call_arg (stmt
, i
);
2901 if (REFERENCE_CLASS_P (arg
))
2902 infer_loop_bounds_from_ref (loop
, stmt
, arg
);
2907 /* Determine information about number of iterations of a LOOP from the fact
2908 that pointer arithmetics in STMT does not overflow. */
2911 infer_loop_bounds_from_pointer_arith (struct loop
*loop
, gimple stmt
)
2913 tree def
, base
, step
, scev
, type
, low
, high
;
2916 if (!is_gimple_assign (stmt
)
2917 || gimple_assign_rhs_code (stmt
) != POINTER_PLUS_EXPR
)
2920 def
= gimple_assign_lhs (stmt
);
2921 if (TREE_CODE (def
) != SSA_NAME
)
2924 type
= TREE_TYPE (def
);
2925 if (!nowrap_type_p (type
))
2928 ptr
= gimple_assign_rhs1 (stmt
);
2929 if (!expr_invariant_in_loop_p (loop
, ptr
))
2932 var
= gimple_assign_rhs2 (stmt
);
2933 if (TYPE_PRECISION (type
) != TYPE_PRECISION (TREE_TYPE (var
)))
2936 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
2937 if (chrec_contains_undetermined (scev
))
2940 base
= initial_condition_in_loop_num (scev
, loop
->num
);
2941 step
= evolution_part_in_loop_num (scev
, loop
->num
);
2944 || TREE_CODE (step
) != INTEGER_CST
2945 || tree_contains_chrecs (base
, NULL
)
2946 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
2949 low
= lower_bound_in_type (type
, type
);
2950 high
= upper_bound_in_type (type
, type
);
2952 /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
2953 produce a NULL pointer. The contrary would mean NULL points to an object,
2954 while NULL is supposed to compare unequal with the address of all objects.
2955 Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
2956 NULL pointer since that would mean wrapping, which we assume here not to
2957 happen. So, we can exclude NULL from the valid range of pointer
2959 if (flag_delete_null_pointer_checks
&& int_cst_value (low
) == 0)
2960 low
= build_int_cstu (TREE_TYPE (low
), TYPE_ALIGN_UNIT (TREE_TYPE (type
)));
2962 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
2965 /* Determine information about number of iterations of a LOOP from the fact
2966 that signed arithmetics in STMT does not overflow. */
2969 infer_loop_bounds_from_signedness (struct loop
*loop
, gimple stmt
)
2971 tree def
, base
, step
, scev
, type
, low
, high
;
2973 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2976 def
= gimple_assign_lhs (stmt
);
2978 if (TREE_CODE (def
) != SSA_NAME
)
2981 type
= TREE_TYPE (def
);
2982 if (!INTEGRAL_TYPE_P (type
)
2983 || !TYPE_OVERFLOW_UNDEFINED (type
))
2986 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
2987 if (chrec_contains_undetermined (scev
))
2990 base
= initial_condition_in_loop_num (scev
, loop
->num
);
2991 step
= evolution_part_in_loop_num (scev
, loop
->num
);
2994 || TREE_CODE (step
) != INTEGER_CST
2995 || tree_contains_chrecs (base
, NULL
)
2996 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
2999 low
= lower_bound_in_type (type
, type
);
3000 high
= upper_bound_in_type (type
, type
);
3002 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
3005 /* The following analyzers are extracting informations on the bounds
3006 of LOOP from the following undefined behaviors:
3008 - data references should not access elements over the statically
3011 - signed variables should not overflow when flag_wrapv is not set.
3015 infer_loop_bounds_from_undefined (struct loop
*loop
)
3019 gimple_stmt_iterator bsi
;
3023 bbs
= get_loop_body (loop
);
3025 for (i
= 0; i
< loop
->num_nodes
; i
++)
3029 /* If BB is not executed in each iteration of the loop, we cannot
3030 use the operations in it to infer reliable upper bound on the
3031 # of iterations of the loop. However, we can use it as a guess.
3032 Reliable guesses come only from array bounds. */
3033 reliable
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
);
3035 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
3037 gimple stmt
= gsi_stmt (bsi
);
3039 infer_loop_bounds_from_array (loop
, stmt
);
3043 infer_loop_bounds_from_signedness (loop
, stmt
);
3044 infer_loop_bounds_from_pointer_arith (loop
, stmt
);
3055 /* Compare double ints, callback for qsort. */
3058 double_int_cmp (const void *p1
, const void *p2
)
3060 const double_int
*d1
= (const double_int
*)p1
;
3061 const double_int
*d2
= (const double_int
*)p2
;
3069 /* Return index of BOUND in BOUNDS array sorted in increasing order.
3070 Lookup by binary search. */
3073 bound_index (vec
<double_int
> bounds
, double_int bound
)
3075 unsigned int end
= bounds
.length ();
3076 unsigned int begin
= 0;
3078 /* Find a matching index by means of a binary search. */
3079 while (begin
!= end
)
3081 unsigned int middle
= (begin
+ end
) / 2;
3082 double_int index
= bounds
[middle
];
3086 else if (index
.ult (bound
))
3094 /* We recorded loop bounds only for statements dominating loop latch (and thus
3095 executed each loop iteration). If there are any bounds on statements not
3096 dominating the loop latch we can improve the estimate by walking the loop
3097 body and seeing if every path from loop header to loop latch contains
3098 some bounded statement. */
3101 discover_iteration_bound_by_body_walk (struct loop
*loop
)
3103 pointer_map_t
*bb_bounds
;
3104 struct nb_iter_bound
*elt
;
3105 vec
<double_int
> bounds
= vNULL
;
3106 vec
<vec
<basic_block
> > queues
= vNULL
;
3107 vec
<basic_block
> queue
= vNULL
;
3108 ptrdiff_t queue_index
;
3109 ptrdiff_t latch_index
= 0;
3110 pointer_map_t
*block_priority
;
3112 /* Discover what bounds may interest us. */
3113 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3115 double_int bound
= elt
->bound
;
3117 /* Exit terminates loop at given iteration, while non-exits produce undefined
3118 effect on the next iteration. */
3121 bound
+= double_int_one
;
3122 /* If an overflow occurred, ignore the result. */
3123 if (bound
.is_zero ())
3127 if (!loop
->any_upper_bound
3128 || bound
.ult (loop
->nb_iterations_upper_bound
))
3129 bounds
.safe_push (bound
);
3132 /* Exit early if there is nothing to do. */
3133 if (!bounds
.exists ())
3136 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3137 fprintf (dump_file
, " Trying to walk loop body to reduce the bound.\n");
3139 /* Sort the bounds in decreasing order. */
3140 qsort (bounds
.address (), bounds
.length (),
3141 sizeof (double_int
), double_int_cmp
);
3143 /* For every basic block record the lowest bound that is guaranteed to
3144 terminate the loop. */
3146 bb_bounds
= pointer_map_create ();
3147 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3149 double_int bound
= elt
->bound
;
3152 bound
+= double_int_one
;
3153 /* If an overflow occurred, ignore the result. */
3154 if (bound
.is_zero ())
3158 if (!loop
->any_upper_bound
3159 || bound
.ult (loop
->nb_iterations_upper_bound
))
3161 ptrdiff_t index
= bound_index (bounds
, bound
);
3162 void **entry
= pointer_map_contains (bb_bounds
,
3163 gimple_bb (elt
->stmt
));
3165 *pointer_map_insert (bb_bounds
,
3166 gimple_bb (elt
->stmt
)) = (void *)index
;
3167 else if ((ptrdiff_t)*entry
> index
)
3168 *entry
= (void *)index
;
3172 block_priority
= pointer_map_create ();
3174 /* Perform shortest path discovery loop->header ... loop->latch.
3176 The "distance" is given by the smallest loop bound of basic block
3177 present in the path and we look for path with largest smallest bound
3180 To avoid the need for fibonacci heap on double ints we simply compress
3181 double ints into indexes to BOUNDS array and then represent the queue
3182 as arrays of queues for every index.
3183 Index of BOUNDS.length() means that the execution of given BB has
3184 no bounds determined.
3186 VISITED is a pointer map translating basic block into smallest index
3187 it was inserted into the priority queue with. */
3190 /* Start walk in loop header with index set to infinite bound. */
3191 queue_index
= bounds
.length ();
3192 queues
.safe_grow_cleared (queue_index
+ 1);
3193 queue
.safe_push (loop
->header
);
3194 queues
[queue_index
] = queue
;
3195 *pointer_map_insert (block_priority
, loop
->header
) = (void *)queue_index
;
3197 for (; queue_index
>= 0; queue_index
--)
3199 if (latch_index
< queue_index
)
3201 while (queues
[queue_index
].length ())
3204 ptrdiff_t bound_index
= queue_index
;
3209 queue
= queues
[queue_index
];
3212 /* OK, we later inserted the BB with lower priority, skip it. */
3213 if ((ptrdiff_t)*pointer_map_contains (block_priority
, bb
) > queue_index
)
3216 /* See if we can improve the bound. */
3217 entry
= pointer_map_contains (bb_bounds
, bb
);
3218 if (entry
&& (ptrdiff_t)*entry
< bound_index
)
3219 bound_index
= (ptrdiff_t)*entry
;
3221 /* Insert succesors into the queue, watch for latch edge
3222 and record greatest index we saw. */
3223 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3225 bool insert
= false;
3228 if (loop_exit_edge_p (loop
, e
))
3231 if (e
== loop_latch_edge (loop
)
3232 && latch_index
< bound_index
)
3233 latch_index
= bound_index
;
3234 else if (!(entry
= pointer_map_contains (block_priority
, e
->dest
)))
3237 *pointer_map_insert (block_priority
, e
->dest
) = (void *)bound_index
;
3239 else if ((ptrdiff_t)*entry
< bound_index
)
3242 *entry
= (void *)bound_index
;
3246 queues
[bound_index
].safe_push (e
->dest
);
3250 queues
[queue_index
].release ();
3253 gcc_assert (latch_index
>= 0);
3254 if ((unsigned)latch_index
< bounds
.length ())
3256 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3258 fprintf (dump_file
, "Found better loop bound ");
3259 dump_double_int (dump_file
, bounds
[latch_index
], true);
3260 fprintf (dump_file
, "\n");
3262 record_niter_bound (loop
, bounds
[latch_index
], false, true);
3267 pointer_map_destroy (bb_bounds
);
3268 pointer_map_destroy (block_priority
);
3271 /* See if every path cross the loop goes through a statement that is known
3272 to not execute at the last iteration. In that case we can decrese iteration
3276 maybe_lower_iteration_bound (struct loop
*loop
)
3278 pointer_set_t
*not_executed_last_iteration
= NULL
;
3279 struct nb_iter_bound
*elt
;
3280 bool found_exit
= false;
3281 vec
<basic_block
> queue
= vNULL
;
3284 /* Collect all statements with interesting (i.e. lower than
3285 nb_iterations_upper_bound) bound on them.
3287 TODO: Due to the way record_estimate choose estimates to store, the bounds
3288 will be always nb_iterations_upper_bound-1. We can change this to record
3289 also statements not dominating the loop latch and update the walk bellow
3290 to the shortest path algorthm. */
3291 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3294 && elt
->bound
.ult (loop
->nb_iterations_upper_bound
))
3296 if (!not_executed_last_iteration
)
3297 not_executed_last_iteration
= pointer_set_create ();
3298 pointer_set_insert (not_executed_last_iteration
, elt
->stmt
);
3301 if (!not_executed_last_iteration
)
3304 /* Start DFS walk in the loop header and see if we can reach the
3305 loop latch or any of the exits (including statements with side
3306 effects that may terminate the loop otherwise) without visiting
3307 any of the statements known to have undefined effect on the last
3309 queue
.safe_push (loop
->header
);
3310 visited
= BITMAP_ALLOC (NULL
);
3311 bitmap_set_bit (visited
, loop
->header
->index
);
3316 basic_block bb
= queue
.pop ();
3317 gimple_stmt_iterator gsi
;
3318 bool stmt_found
= false;
3320 /* Loop for possible exits and statements bounding the execution. */
3321 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3323 gimple stmt
= gsi_stmt (gsi
);
3324 if (pointer_set_contains (not_executed_last_iteration
, stmt
))
3329 if (gimple_has_side_effects (stmt
))
3338 /* If no bounding statement is found, continue the walk. */
3344 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3346 if (loop_exit_edge_p (loop
, e
)
3347 || e
== loop_latch_edge (loop
))
3352 if (bitmap_set_bit (visited
, e
->dest
->index
))
3353 queue
.safe_push (e
->dest
);
3357 while (queue
.length () && !found_exit
);
3359 /* If every path through the loop reach bounding statement before exit,
3360 then we know the last iteration of the loop will have undefined effect
3361 and we can decrease number of iterations. */
3365 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3366 fprintf (dump_file
, "Reducing loop iteration estimate by 1; "
3367 "undefined statement must be executed at the last iteration.\n");
3368 record_niter_bound (loop
, loop
->nb_iterations_upper_bound
- double_int_one
,
3371 BITMAP_FREE (visited
);
3373 pointer_set_destroy (not_executed_last_iteration
);
3376 /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
3377 is true also use estimates derived from undefined behavior. */
3380 estimate_numbers_of_iterations_loop (struct loop
*loop
)
3385 struct tree_niter_desc niter_desc
;
3390 /* Give up if we already have tried to compute an estimation. */
3391 if (loop
->estimate_state
!= EST_NOT_COMPUTED
)
3394 loop
->estimate_state
= EST_AVAILABLE
;
3395 /* Force estimate compuation but leave any existing upper bound in place. */
3396 loop
->any_estimate
= false;
3398 /* Ensure that loop->nb_iterations is computed if possible. If it turns out
3399 to be constant, we avoid undefined behavior implied bounds and instead
3400 diagnose those loops with -Waggressive-loop-optimizations. */
3401 number_of_latch_executions (loop
);
3403 exits
= get_loop_exit_edges (loop
);
3404 likely_exit
= single_likely_exit (loop
);
3405 FOR_EACH_VEC_ELT (exits
, i
, ex
)
3407 if (!number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
3410 niter
= niter_desc
.niter
;
3411 type
= TREE_TYPE (niter
);
3412 if (TREE_CODE (niter_desc
.may_be_zero
) != INTEGER_CST
)
3413 niter
= build3 (COND_EXPR
, type
, niter_desc
.may_be_zero
,
3414 build_int_cst (type
, 0),
3416 record_estimate (loop
, niter
, niter_desc
.max
,
3417 last_stmt (ex
->src
),
3418 true, ex
== likely_exit
, true);
3422 if (flag_aggressive_loop_optimizations
)
3423 infer_loop_bounds_from_undefined (loop
);
3425 discover_iteration_bound_by_body_walk (loop
);
3427 maybe_lower_iteration_bound (loop
);
3429 /* If we have a measured profile, use it to estimate the number of
3431 if (loop
->header
->count
!= 0)
3433 gcov_type nit
= expected_loop_iterations_unbounded (loop
) + 1;
3434 bound
= gcov_type_to_double_int (nit
);
3435 record_niter_bound (loop
, bound
, true, false);
3438 /* If we know the exact number of iterations of this loop, try to
3439 not break code with undefined behavior by not recording smaller
3440 maximum number of iterations. */
3441 if (loop
->nb_iterations
3442 && TREE_CODE (loop
->nb_iterations
) == INTEGER_CST
)
3444 loop
->any_upper_bound
= true;
3445 loop
->nb_iterations_upper_bound
3446 = tree_to_double_int (loop
->nb_iterations
);
3450 /* Sets NIT to the estimated number of executions of the latch of the
3451 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
3452 large as the number of iterations. If we have no reliable estimate,
3453 the function returns false, otherwise returns true. */
3456 estimated_loop_iterations (struct loop
*loop
, double_int
*nit
)
3458 /* When SCEV information is available, try to update loop iterations
3459 estimate. Otherwise just return whatever we recorded earlier. */
3460 if (scev_initialized_p ())
3461 estimate_numbers_of_iterations_loop (loop
);
3463 return (get_estimated_loop_iterations (loop
, nit
));
3466 /* Similar to estimated_loop_iterations, but returns the estimate only
3467 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3468 on the number of iterations of LOOP could not be derived, returns -1. */
3471 estimated_loop_iterations_int (struct loop
*loop
)
3474 HOST_WIDE_INT hwi_nit
;
3476 if (!estimated_loop_iterations (loop
, &nit
))
3479 if (!nit
.fits_shwi ())
3481 hwi_nit
= nit
.to_shwi ();
3483 return hwi_nit
< 0 ? -1 : hwi_nit
;
3487 /* Sets NIT to an upper bound for the maximum number of executions of the
3488 latch of the LOOP. If we have no reliable estimate, the function returns
3489 false, otherwise returns true. */
3492 max_loop_iterations (struct loop
*loop
, double_int
*nit
)
3494 /* When SCEV information is available, try to update loop iterations
3495 estimate. Otherwise just return whatever we recorded earlier. */
3496 if (scev_initialized_p ())
3497 estimate_numbers_of_iterations_loop (loop
);
3499 return get_max_loop_iterations (loop
, nit
);
3502 /* Similar to max_loop_iterations, but returns the estimate only
3503 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3504 on the number of iterations of LOOP could not be derived, returns -1. */
3507 max_loop_iterations_int (struct loop
*loop
)
3510 HOST_WIDE_INT hwi_nit
;
3512 if (!max_loop_iterations (loop
, &nit
))
3515 if (!nit
.fits_shwi ())
3517 hwi_nit
= nit
.to_shwi ();
3519 return hwi_nit
< 0 ? -1 : hwi_nit
;
3522 /* Returns an estimate for the number of executions of statements
3523 in the LOOP. For statements before the loop exit, this exceeds
3524 the number of execution of the latch by one. */
3527 estimated_stmt_executions_int (struct loop
*loop
)
3529 HOST_WIDE_INT nit
= estimated_loop_iterations_int (loop
);
3535 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
3537 /* If the computation overflows, return -1. */
3538 return snit
< 0 ? -1 : snit
;
3541 /* Sets NIT to the estimated maximum number of executions of the latch of the
3542 LOOP, plus one. If we have no reliable estimate, the function returns
3543 false, otherwise returns true. */
3546 max_stmt_executions (struct loop
*loop
, double_int
*nit
)
3548 double_int nit_minus_one
;
3550 if (!max_loop_iterations (loop
, nit
))
3553 nit_minus_one
= *nit
;
3555 *nit
+= double_int_one
;
3557 return (*nit
).ugt (nit_minus_one
);
3560 /* Sets NIT to the estimated number of executions of the latch of the
3561 LOOP, plus one. If we have no reliable estimate, the function returns
3562 false, otherwise returns true. */
3565 estimated_stmt_executions (struct loop
*loop
, double_int
*nit
)
3567 double_int nit_minus_one
;
3569 if (!estimated_loop_iterations (loop
, nit
))
3572 nit_minus_one
= *nit
;
3574 *nit
+= double_int_one
;
3576 return (*nit
).ugt (nit_minus_one
);
3579 /* Records estimates on numbers of iterations of loops. */
3582 estimate_numbers_of_iterations (void)
3587 /* We don't want to issue signed overflow warnings while getting
3588 loop iteration estimates. */
3589 fold_defer_overflow_warnings ();
3591 FOR_EACH_LOOP (li
, loop
, 0)
3593 estimate_numbers_of_iterations_loop (loop
);
3596 fold_undefer_and_ignore_overflow_warnings ();
3599 /* Returns true if statement S1 dominates statement S2. */
3602 stmt_dominates_stmt_p (gimple s1
, gimple s2
)
3604 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
3612 gimple_stmt_iterator bsi
;
3614 if (gimple_code (s2
) == GIMPLE_PHI
)
3617 if (gimple_code (s1
) == GIMPLE_PHI
)
3620 for (bsi
= gsi_start_bb (bb1
); gsi_stmt (bsi
) != s2
; gsi_next (&bsi
))
3621 if (gsi_stmt (bsi
) == s1
)
3627 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
3630 /* Returns true when we can prove that the number of executions of
3631 STMT in the loop is at most NITER, according to the bound on
3632 the number of executions of the statement NITER_BOUND->stmt recorded in
3633 NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT.
3635 ??? This code can become quite a CPU hog - we can have many bounds,
3636 and large basic block forcing stmt_dominates_stmt_p to be queried
3637 many times on a large basic blocks, so the whole thing is O(n^2)
3638 for scev_probably_wraps_p invocation (that can be done n times).
3640 It would make more sense (and give better answers) to remember BB
3641 bounds computed by discover_iteration_bound_by_body_walk. */
3644 n_of_executions_at_most (gimple stmt
,
3645 struct nb_iter_bound
*niter_bound
,
3648 double_int bound
= niter_bound
->bound
;
3649 tree nit_type
= TREE_TYPE (niter
), e
;
3652 gcc_assert (TYPE_UNSIGNED (nit_type
));
3654 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
3655 the number of iterations is small. */
3656 if (!double_int_fits_to_tree_p (nit_type
, bound
))
3659 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3660 times. This means that:
3662 -- if NITER_BOUND->is_exit is true, then everything after
3663 it at most NITER_BOUND->bound times.
3665 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
3666 is executed, then NITER_BOUND->stmt is executed as well in the same
3667 iteration then STMT is executed at most NITER_BOUND->bound + 1 times.
3669 If we can determine that NITER_BOUND->stmt is always executed
3670 after STMT, then STMT is executed at most NITER_BOUND->bound + 2 times.
3671 We conclude that if both statements belong to the same
3672 basic block and STMT is before NITER_BOUND->stmt and there are no
3673 statements with side effects in between. */
3675 if (niter_bound
->is_exit
)
3677 if (stmt
== niter_bound
->stmt
3678 || !stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
3684 if (!stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
3686 gimple_stmt_iterator bsi
;
3687 if (gimple_bb (stmt
) != gimple_bb (niter_bound
->stmt
)
3688 || gimple_code (stmt
) == GIMPLE_PHI
3689 || gimple_code (niter_bound
->stmt
) == GIMPLE_PHI
)
3692 /* By stmt_dominates_stmt_p we already know that STMT appears
3693 before NITER_BOUND->STMT. Still need to test that the loop
3694 can not be terinated by a side effect in between. */
3695 for (bsi
= gsi_for_stmt (stmt
); gsi_stmt (bsi
) != niter_bound
->stmt
;
3697 if (gimple_has_side_effects (gsi_stmt (bsi
)))
3699 bound
+= double_int_one
;
3700 if (bound
.is_zero ()
3701 || !double_int_fits_to_tree_p (nit_type
, bound
))
3707 e
= fold_binary (cmp
, boolean_type_node
,
3708 niter
, double_int_to_tree (nit_type
, bound
));
3709 return e
&& integer_nonzerop (e
);
3712 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
3715 nowrap_type_p (tree type
)
3717 if (INTEGRAL_TYPE_P (type
)
3718 && TYPE_OVERFLOW_UNDEFINED (type
))
3721 if (POINTER_TYPE_P (type
))
3727 /* Return false only when the induction variable BASE + STEP * I is
3728 known to not overflow: i.e. when the number of iterations is small
3729 enough with respect to the step and initial condition in order to
3730 keep the evolution confined in TYPEs bounds. Return true when the
3731 iv is known to overflow or when the property is not computable.
3733 USE_OVERFLOW_SEMANTICS is true if this function should assume that
3734 the rules for overflow of the given language apply (e.g., that signed
3735 arithmetics in C does not overflow). */
3738 scev_probably_wraps_p (tree base
, tree step
,
3739 gimple at_stmt
, struct loop
*loop
,
3740 bool use_overflow_semantics
)
3742 tree delta
, step_abs
;
3743 tree unsigned_type
, valid_niter
;
3744 tree type
= TREE_TYPE (step
);
3747 struct nb_iter_bound
*bound
;
3749 /* FIXME: We really need something like
3750 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
3752 We used to test for the following situation that frequently appears
3753 during address arithmetics:
3755 D.1621_13 = (long unsigned intD.4) D.1620_12;
3756 D.1622_14 = D.1621_13 * 8;
3757 D.1623_15 = (doubleD.29 *) D.1622_14;
3759 And derived that the sequence corresponding to D_14
3760 can be proved to not wrap because it is used for computing a
3761 memory access; however, this is not really the case -- for example,
3762 if D_12 = (unsigned char) [254,+,1], then D_14 has values
3763 2032, 2040, 0, 8, ..., but the code is still legal. */
3765 if (chrec_contains_undetermined (base
)
3766 || chrec_contains_undetermined (step
))
3769 if (integer_zerop (step
))
3772 /* If we can use the fact that signed and pointer arithmetics does not
3773 wrap, we are done. */
3774 if (use_overflow_semantics
&& nowrap_type_p (TREE_TYPE (base
)))
3777 /* To be able to use estimates on number of iterations of the loop,
3778 we must have an upper bound on the absolute value of the step. */
3779 if (TREE_CODE (step
) != INTEGER_CST
)
3782 /* Don't issue signed overflow warnings. */
3783 fold_defer_overflow_warnings ();
3785 /* Otherwise, compute the number of iterations before we reach the
3786 bound of the type, and verify that the loop is exited before this
3788 unsigned_type
= unsigned_type_for (type
);
3789 base
= fold_convert (unsigned_type
, base
);
3791 if (tree_int_cst_sign_bit (step
))
3793 tree extreme
= fold_convert (unsigned_type
,
3794 lower_bound_in_type (type
, type
));
3795 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
3796 step_abs
= fold_build1 (NEGATE_EXPR
, unsigned_type
,
3797 fold_convert (unsigned_type
, step
));
3801 tree extreme
= fold_convert (unsigned_type
,
3802 upper_bound_in_type (type
, type
));
3803 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
3804 step_abs
= fold_convert (unsigned_type
, step
);
3807 valid_niter
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step_abs
);
3809 estimate_numbers_of_iterations_loop (loop
);
3811 if (max_loop_iterations (loop
, &niter
)
3812 && double_int_fits_to_tree_p (TREE_TYPE (valid_niter
), niter
)
3813 && (e
= fold_binary (GT_EXPR
, boolean_type_node
, valid_niter
,
3814 double_int_to_tree (TREE_TYPE (valid_niter
),
3816 && integer_nonzerop (e
))
3818 fold_undefer_and_ignore_overflow_warnings ();
3822 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
3824 if (n_of_executions_at_most (at_stmt
, bound
, valid_niter
))
3826 fold_undefer_and_ignore_overflow_warnings ();
3831 fold_undefer_and_ignore_overflow_warnings ();
3833 /* At this point we still don't have a proof that the iv does not
3834 overflow: give up. */
3838 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
3841 free_numbers_of_iterations_estimates_loop (struct loop
*loop
)
3843 struct nb_iter_bound
*bound
, *next
;
3845 loop
->nb_iterations
= NULL
;
3846 loop
->estimate_state
= EST_NOT_COMPUTED
;
3847 for (bound
= loop
->bounds
; bound
; bound
= next
)
3853 loop
->bounds
= NULL
;
3856 /* Frees the information on upper bounds on numbers of iterations of loops. */
3859 free_numbers_of_iterations_estimates (void)
3864 FOR_EACH_LOOP (li
, loop
, 0)
3866 free_numbers_of_iterations_estimates_loop (loop
);
3870 /* Substitute value VAL for ssa name NAME inside expressions held
3874 substitute_in_loop_info (struct loop
*loop
, tree name
, tree val
)
3876 loop
->nb_iterations
= simplify_replace_tree (loop
->nb_iterations
, name
, val
);