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 "wide-int-print.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
);
82 mpz_set_ui (offset
, 0);
84 switch (TREE_CODE (expr
))
91 case POINTER_PLUS_EXPR
:
92 op0
= TREE_OPERAND (expr
, 0);
93 op1
= TREE_OPERAND (expr
, 1);
95 if (TREE_CODE (op1
) != INTEGER_CST
)
99 /* Always sign extend the offset. */
100 wi::to_mpz (op1
, offset
, SIGNED
);
102 mpz_neg (offset
, offset
);
106 *var
= build_int_cst_type (type
, 0);
107 wi::to_mpz (expr
, offset
, TYPE_SIGN (type
));
115 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
116 in TYPE to MIN and MAX. */
119 determine_value_range (tree type
, tree var
, mpz_t off
,
120 mpz_t min
, mpz_t max
)
122 /* If the expression is a constant, we know its value exactly. */
123 if (integer_zerop (var
))
130 /* If the computation may wrap, we know nothing about the value, except for
131 the range of the type. */
132 get_type_static_bounds (type
, min
, max
);
133 if (!nowrap_type_p (type
))
136 /* Since the addition of OFF does not wrap, if OFF is positive, then we may
137 add it to MIN, otherwise to MAX. */
138 if (mpz_sgn (off
) < 0)
139 mpz_add (max
, max
, off
);
141 mpz_add (min
, min
, off
);
144 /* Stores the bounds on the difference of the values of the expressions
145 (var + X) and (var + Y), computed in TYPE, to BNDS. */
148 bound_difference_of_offsetted_base (tree type
, mpz_t x
, mpz_t y
,
151 int rel
= mpz_cmp (x
, y
);
152 bool may_wrap
= !nowrap_type_p (type
);
155 /* If X == Y, then the expressions are always equal.
156 If X > Y, there are the following possibilities:
157 a) neither of var + X and var + Y overflow or underflow, or both of
158 them do. Then their difference is X - Y.
159 b) var + X overflows, and var + Y does not. Then the values of the
160 expressions are var + X - M and var + Y, where M is the range of
161 the type, and their difference is X - Y - M.
162 c) var + Y underflows and var + X does not. Their difference again
164 Therefore, if the arithmetics in type does not overflow, then the
165 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
166 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
167 (X - Y, X - Y + M). */
171 mpz_set_ui (bnds
->below
, 0);
172 mpz_set_ui (bnds
->up
, 0);
177 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), m
, UNSIGNED
);
178 mpz_add_ui (m
, m
, 1);
179 mpz_sub (bnds
->up
, x
, y
);
180 mpz_set (bnds
->below
, bnds
->up
);
185 mpz_sub (bnds
->below
, bnds
->below
, m
);
187 mpz_add (bnds
->up
, bnds
->up
, m
);
193 /* From condition C0 CMP C1 derives information regarding the
194 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
195 and stores it to BNDS. */
198 refine_bounds_using_guard (tree type
, tree varx
, mpz_t offx
,
199 tree vary
, mpz_t offy
,
200 tree c0
, enum tree_code cmp
, tree c1
,
203 tree varc0
, varc1
, tmp
, ctype
;
204 mpz_t offc0
, offc1
, loffx
, loffy
, bnd
;
206 bool no_wrap
= nowrap_type_p (type
);
215 STRIP_SIGN_NOPS (c0
);
216 STRIP_SIGN_NOPS (c1
);
217 ctype
= TREE_TYPE (c0
);
218 if (!useless_type_conversion_p (ctype
, type
))
224 /* We could derive quite precise information from EQ_EXPR, however, such
225 a guard is unlikely to appear, so we do not bother with handling
230 /* NE_EXPR comparisons do not contain much of useful information, except for
231 special case of comparing with the bounds of the type. */
232 if (TREE_CODE (c1
) != INTEGER_CST
233 || !INTEGRAL_TYPE_P (type
))
236 /* Ensure that the condition speaks about an expression in the same type
238 ctype
= TREE_TYPE (c0
);
239 if (TYPE_PRECISION (ctype
) != TYPE_PRECISION (type
))
241 c0
= fold_convert (type
, c0
);
242 c1
= fold_convert (type
, c1
);
244 if (TYPE_MIN_VALUE (type
)
245 && operand_equal_p (c1
, TYPE_MIN_VALUE (type
), 0))
250 if (TYPE_MAX_VALUE (type
)
251 && operand_equal_p (c1
, TYPE_MAX_VALUE (type
), 0))
264 split_to_var_and_offset (expand_simple_operations (c0
), &varc0
, offc0
);
265 split_to_var_and_offset (expand_simple_operations (c1
), &varc1
, offc1
);
267 /* We are only interested in comparisons of expressions based on VARX and
268 VARY. TODO -- we might also be able to derive some bounds from
269 expressions containing just one of the variables. */
271 if (operand_equal_p (varx
, varc1
, 0))
273 tmp
= varc0
; varc0
= varc1
; varc1
= tmp
;
274 mpz_swap (offc0
, offc1
);
275 cmp
= swap_tree_comparison (cmp
);
278 if (!operand_equal_p (varx
, varc0
, 0)
279 || !operand_equal_p (vary
, varc1
, 0))
282 mpz_init_set (loffx
, offx
);
283 mpz_init_set (loffy
, offy
);
285 if (cmp
== GT_EXPR
|| cmp
== GE_EXPR
)
287 tmp
= varx
; varx
= vary
; vary
= tmp
;
288 mpz_swap (offc0
, offc1
);
289 mpz_swap (loffx
, loffy
);
290 cmp
= swap_tree_comparison (cmp
);
294 /* If there is no overflow, the condition implies that
296 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
298 The overflows and underflows may complicate things a bit; each
299 overflow decreases the appropriate offset by M, and underflow
300 increases it by M. The above inequality would not necessarily be
303 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
304 VARX + OFFC0 overflows, but VARX + OFFX does not.
305 This may only happen if OFFX < OFFC0.
306 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
307 VARY + OFFC1 underflows and VARY + OFFY does not.
308 This may only happen if OFFY > OFFC1. */
317 x_ok
= (integer_zerop (varx
)
318 || mpz_cmp (loffx
, offc0
) >= 0);
319 y_ok
= (integer_zerop (vary
)
320 || mpz_cmp (loffy
, offc1
) <= 0);
326 mpz_sub (bnd
, loffx
, loffy
);
327 mpz_add (bnd
, bnd
, offc1
);
328 mpz_sub (bnd
, bnd
, offc0
);
331 mpz_sub_ui (bnd
, bnd
, 1);
336 if (mpz_cmp (bnds
->below
, bnd
) < 0)
337 mpz_set (bnds
->below
, bnd
);
341 if (mpz_cmp (bnd
, bnds
->up
) < 0)
342 mpz_set (bnds
->up
, bnd
);
354 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
355 The subtraction is considered to be performed in arbitrary precision,
358 We do not attempt to be too clever regarding the value ranges of X and
359 Y; most of the time, they are just integers or ssa names offsetted by
360 integer. However, we try to use the information contained in the
361 comparisons before the loop (usually created by loop header copying). */
364 bound_difference (struct loop
*loop
, tree x
, tree y
, bounds
*bnds
)
366 tree type
= TREE_TYPE (x
);
369 mpz_t minx
, maxx
, miny
, maxy
;
377 /* Get rid of unnecessary casts, but preserve the value of
382 mpz_init (bnds
->below
);
386 split_to_var_and_offset (x
, &varx
, offx
);
387 split_to_var_and_offset (y
, &vary
, offy
);
389 if (!integer_zerop (varx
)
390 && operand_equal_p (varx
, vary
, 0))
392 /* Special case VARX == VARY -- we just need to compare the
393 offsets. The matters are a bit more complicated in the
394 case addition of offsets may wrap. */
395 bound_difference_of_offsetted_base (type
, offx
, offy
, bnds
);
399 /* Otherwise, use the value ranges to determine the initial
400 estimates on below and up. */
405 determine_value_range (type
, varx
, offx
, minx
, maxx
);
406 determine_value_range (type
, vary
, offy
, miny
, maxy
);
408 mpz_sub (bnds
->below
, minx
, maxy
);
409 mpz_sub (bnds
->up
, maxx
, miny
);
416 /* If both X and Y are constants, we cannot get any more precise. */
417 if (integer_zerop (varx
) && integer_zerop (vary
))
420 /* Now walk the dominators of the loop header and use the entry
421 guards to refine the estimates. */
422 for (bb
= loop
->header
;
423 bb
!= ENTRY_BLOCK_PTR
&& cnt
< MAX_DOMINATORS_TO_WALK
;
424 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
426 if (!single_pred_p (bb
))
428 e
= single_pred_edge (bb
);
430 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
433 cond
= last_stmt (e
->src
);
434 c0
= gimple_cond_lhs (cond
);
435 cmp
= gimple_cond_code (cond
);
436 c1
= gimple_cond_rhs (cond
);
438 if (e
->flags
& EDGE_FALSE_VALUE
)
439 cmp
= invert_tree_comparison (cmp
, false);
441 refine_bounds_using_guard (type
, varx
, offx
, vary
, offy
,
451 /* Update the bounds in BNDS that restrict the value of X to the bounds
452 that restrict the value of X + DELTA. X can be obtained as a
453 difference of two values in TYPE. */
456 bounds_add (bounds
*bnds
, widest_int delta
, tree type
)
461 wi::to_mpz (delta
, mdelta
, SIGNED
);
464 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), max
, UNSIGNED
);
466 mpz_add (bnds
->up
, bnds
->up
, mdelta
);
467 mpz_add (bnds
->below
, bnds
->below
, mdelta
);
469 if (mpz_cmp (bnds
->up
, max
) > 0)
470 mpz_set (bnds
->up
, max
);
473 if (mpz_cmp (bnds
->below
, max
) < 0)
474 mpz_set (bnds
->below
, max
);
480 /* Update the bounds in BNDS that restrict the value of X to the bounds
481 that restrict the value of -X. */
484 bounds_negate (bounds
*bnds
)
488 mpz_init_set (tmp
, bnds
->up
);
489 mpz_neg (bnds
->up
, bnds
->below
);
490 mpz_neg (bnds
->below
, tmp
);
494 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
497 inverse (tree x
, tree mask
)
499 tree type
= TREE_TYPE (x
);
501 unsigned ctr
= tree_floor_log2 (mask
);
503 if (TYPE_PRECISION (type
) <= HOST_BITS_PER_WIDE_INT
)
505 unsigned HOST_WIDE_INT ix
;
506 unsigned HOST_WIDE_INT imask
;
507 unsigned HOST_WIDE_INT irslt
= 1;
509 gcc_assert (cst_fits_shwi_p (x
));
510 gcc_assert (cst_fits_shwi_p (mask
));
512 ix
= int_cst_value (x
);
513 imask
= int_cst_value (mask
);
522 rslt
= build_int_cst_type (type
, irslt
);
526 rslt
= build_int_cst (type
, 1);
529 rslt
= int_const_binop (MULT_EXPR
, rslt
, x
);
530 x
= int_const_binop (MULT_EXPR
, x
, x
);
532 rslt
= int_const_binop (BIT_AND_EXPR
, rslt
, mask
);
538 /* Derives the upper bound BND on the number of executions of loop with exit
539 condition S * i <> C. If NO_OVERFLOW is true, then the control variable of
540 the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed
541 that the loop ends through this exit, i.e., the induction variable ever
542 reaches the value of C.
544 The value C is equal to final - base, where final and base are the final and
545 initial value of the actual induction variable in the analysed loop. BNDS
546 bounds the value of this difference when computed in signed type with
547 unbounded range, while the computation of C is performed in an unsigned
548 type with the range matching the range of the type of the induction variable.
549 In particular, BNDS.up contains an upper bound on C in the following cases:
550 -- if the iv must reach its final value without overflow, i.e., if
551 NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
552 -- if final >= base, which we know to hold when BNDS.below >= 0. */
555 number_of_iterations_ne_max (mpz_t bnd
, bool no_overflow
, tree c
, tree s
,
556 bounds
*bnds
, bool exit_must_be_taken
)
560 tree type
= TREE_TYPE (c
);
561 bool bnds_u_valid
= ((no_overflow
&& exit_must_be_taken
)
562 || mpz_sgn (bnds
->below
) >= 0);
565 || (TREE_CODE (c
) == INTEGER_CST
566 && TREE_CODE (s
) == INTEGER_CST
567 && wi::mod_trunc (c
, s
, TYPE_SIGN (type
)) == 0)
568 || (TYPE_OVERFLOW_UNDEFINED (type
)
569 && multiple_of_p (type
, c
, s
)))
571 /* If C is an exact multiple of S, then its value will be reached before
572 the induction variable overflows (unless the loop is exited in some
573 other way before). Note that the actual induction variable in the
574 loop (which ranges from base to final instead of from 0 to C) may
575 overflow, in which case BNDS.up will not be giving a correct upper
576 bound on C; thus, BNDS_U_VALID had to be computed in advance. */
578 exit_must_be_taken
= true;
581 /* If the induction variable can overflow, the number of iterations is at
582 most the period of the control variable (or infinite, but in that case
583 the whole # of iterations analysis will fail). */
586 max
= wi::mask
<widest_int
> (TYPE_PRECISION (type
) - wi::ctz (s
), false);
587 wi::to_mpz (max
, bnd
, UNSIGNED
);
591 /* Now we know that the induction variable does not overflow, so the loop
592 iterates at most (range of type / S) times. */
593 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), bnd
, UNSIGNED
);
595 /* If the induction variable is guaranteed to reach the value of C before
597 if (exit_must_be_taken
)
599 /* ... then we can strengthen this to C / S, and possibly we can use
600 the upper bound on C given by BNDS. */
601 if (TREE_CODE (c
) == INTEGER_CST
)
602 wi::to_mpz (c
, bnd
, UNSIGNED
);
603 else if (bnds_u_valid
)
604 mpz_set (bnd
, bnds
->up
);
608 wi::to_mpz (s
, d
, UNSIGNED
);
609 mpz_fdiv_q (bnd
, bnd
, d
);
613 /* Determines number of iterations of loop whose ending condition
614 is IV <> FINAL. TYPE is the type of the iv. The number of
615 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
616 we know that the exit must be taken eventually, i.e., that the IV
617 ever reaches the value FINAL (we derived this earlier, and possibly set
618 NITER->assumptions to make sure this is the case). BNDS contains the
619 bounds on the difference FINAL - IV->base. */
622 number_of_iterations_ne (tree type
, affine_iv
*iv
, tree final
,
623 struct tree_niter_desc
*niter
, bool exit_must_be_taken
,
626 tree niter_type
= unsigned_type_for (type
);
627 tree s
, c
, d
, bits
, assumption
, tmp
, bound
;
630 niter
->control
= *iv
;
631 niter
->bound
= final
;
632 niter
->cmp
= NE_EXPR
;
634 /* Rearrange the terms so that we get inequality S * i <> C, with S
635 positive. Also cast everything to the unsigned type. If IV does
636 not overflow, BNDS bounds the value of C. Also, this is the
637 case if the computation |FINAL - IV->base| does not overflow, i.e.,
638 if BNDS->below in the result is nonnegative. */
639 if (tree_int_cst_sign_bit (iv
->step
))
641 s
= fold_convert (niter_type
,
642 fold_build1 (NEGATE_EXPR
, type
, iv
->step
));
643 c
= fold_build2 (MINUS_EXPR
, niter_type
,
644 fold_convert (niter_type
, iv
->base
),
645 fold_convert (niter_type
, final
));
646 bounds_negate (bnds
);
650 s
= fold_convert (niter_type
, iv
->step
);
651 c
= fold_build2 (MINUS_EXPR
, niter_type
,
652 fold_convert (niter_type
, final
),
653 fold_convert (niter_type
, iv
->base
));
657 number_of_iterations_ne_max (max
, iv
->no_overflow
, c
, s
, bnds
,
659 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, max
, false),
660 TYPE_SIGN (niter_type
));
663 /* First the trivial cases -- when the step is 1. */
664 if (integer_onep (s
))
670 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
671 is infinite. Otherwise, the number of iterations is
672 (inverse(s/d) * (c/d)) mod (size of mode/d). */
673 bits
= num_ending_zeros (s
);
674 bound
= build_low_bits_mask (niter_type
,
675 (TYPE_PRECISION (niter_type
)
676 - tree_to_uhwi (bits
)));
678 d
= fold_binary_to_constant (LSHIFT_EXPR
, niter_type
,
679 build_int_cst (niter_type
, 1), bits
);
680 s
= fold_binary_to_constant (RSHIFT_EXPR
, niter_type
, s
, bits
);
682 if (!exit_must_be_taken
)
684 /* If we cannot assume that the exit is taken eventually, record the
685 assumptions for divisibility of c. */
686 assumption
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, c
, d
);
687 assumption
= fold_build2 (EQ_EXPR
, boolean_type_node
,
688 assumption
, build_int_cst (niter_type
, 0));
689 if (!integer_nonzerop (assumption
))
690 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
691 niter
->assumptions
, assumption
);
694 c
= fold_build2 (EXACT_DIV_EXPR
, niter_type
, c
, d
);
695 tmp
= fold_build2 (MULT_EXPR
, niter_type
, c
, inverse (s
, bound
));
696 niter
->niter
= fold_build2 (BIT_AND_EXPR
, niter_type
, tmp
, bound
);
700 /* Checks whether we can determine the final value of the control variable
701 of the loop with ending condition IV0 < IV1 (computed in TYPE).
702 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
703 of the step. The assumptions necessary to ensure that the computation
704 of the final value does not overflow are recorded in NITER. If we
705 find the final value, we adjust DELTA and return TRUE. Otherwise
706 we return false. BNDS bounds the value of IV1->base - IV0->base,
707 and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
708 true if we know that the exit must be taken eventually. */
711 number_of_iterations_lt_to_ne (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
712 struct tree_niter_desc
*niter
,
713 tree
*delta
, tree step
,
714 bool exit_must_be_taken
, bounds
*bnds
)
716 tree niter_type
= TREE_TYPE (step
);
717 tree mod
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, *delta
, step
);
720 tree assumption
= boolean_true_node
, bound
, noloop
;
721 bool ret
= false, fv_comp_no_overflow
;
723 if (POINTER_TYPE_P (type
))
726 if (TREE_CODE (mod
) != INTEGER_CST
)
728 if (integer_nonzerop (mod
))
729 mod
= fold_build2 (MINUS_EXPR
, niter_type
, step
, mod
);
730 tmod
= fold_convert (type1
, mod
);
733 wi::to_mpz (mod
, mmod
, UNSIGNED
);
734 mpz_neg (mmod
, mmod
);
736 /* If the induction variable does not overflow and the exit is taken,
737 then the computation of the final value does not overflow. This is
738 also obviously the case if the new final value is equal to the
739 current one. Finally, we postulate this for pointer type variables,
740 as the code cannot rely on the object to that the pointer points being
741 placed at the end of the address space (and more pragmatically,
742 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
743 if (integer_zerop (mod
) || POINTER_TYPE_P (type
))
744 fv_comp_no_overflow
= true;
745 else if (!exit_must_be_taken
)
746 fv_comp_no_overflow
= false;
748 fv_comp_no_overflow
=
749 (iv0
->no_overflow
&& integer_nonzerop (iv0
->step
))
750 || (iv1
->no_overflow
&& integer_nonzerop (iv1
->step
));
752 if (integer_nonzerop (iv0
->step
))
754 /* The final value of the iv is iv1->base + MOD, assuming that this
755 computation does not overflow, and that
756 iv0->base <= iv1->base + MOD. */
757 if (!fv_comp_no_overflow
)
759 bound
= fold_build2 (MINUS_EXPR
, type1
,
760 TYPE_MAX_VALUE (type1
), tmod
);
761 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
763 if (integer_zerop (assumption
))
766 if (mpz_cmp (mmod
, bnds
->below
) < 0)
767 noloop
= boolean_false_node
;
768 else if (POINTER_TYPE_P (type
))
769 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
771 fold_build_pointer_plus (iv1
->base
, tmod
));
773 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
775 fold_build2 (PLUS_EXPR
, type1
,
780 /* The final value of the iv is iv0->base - MOD, assuming that this
781 computation does not overflow, and that
782 iv0->base - MOD <= iv1->base. */
783 if (!fv_comp_no_overflow
)
785 bound
= fold_build2 (PLUS_EXPR
, type1
,
786 TYPE_MIN_VALUE (type1
), tmod
);
787 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
789 if (integer_zerop (assumption
))
792 if (mpz_cmp (mmod
, bnds
->below
) < 0)
793 noloop
= boolean_false_node
;
794 else if (POINTER_TYPE_P (type
))
795 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
796 fold_build_pointer_plus (iv0
->base
,
797 fold_build1 (NEGATE_EXPR
,
801 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
802 fold_build2 (MINUS_EXPR
, type1
,
807 if (!integer_nonzerop (assumption
))
808 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
811 if (!integer_zerop (noloop
))
812 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
815 bounds_add (bnds
, wi::to_widest (mod
), type
);
816 *delta
= fold_build2 (PLUS_EXPR
, niter_type
, *delta
, mod
);
824 /* Add assertions to NITER that ensure that the control variable of the loop
825 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
826 are TYPE. Returns false if we can prove that there is an overflow, true
827 otherwise. STEP is the absolute value of the step. */
830 assert_no_overflow_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
831 struct tree_niter_desc
*niter
, tree step
)
833 tree bound
, d
, assumption
, diff
;
834 tree niter_type
= TREE_TYPE (step
);
836 if (integer_nonzerop (iv0
->step
))
838 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
839 if (iv0
->no_overflow
)
842 /* If iv0->base is a constant, we can determine the last value before
843 overflow precisely; otherwise we conservatively assume
846 if (TREE_CODE (iv0
->base
) == INTEGER_CST
)
848 d
= fold_build2 (MINUS_EXPR
, niter_type
,
849 fold_convert (niter_type
, TYPE_MAX_VALUE (type
)),
850 fold_convert (niter_type
, iv0
->base
));
851 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
854 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
855 build_int_cst (niter_type
, 1));
856 bound
= fold_build2 (MINUS_EXPR
, type
,
857 TYPE_MAX_VALUE (type
), fold_convert (type
, diff
));
858 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
863 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
864 if (iv1
->no_overflow
)
867 if (TREE_CODE (iv1
->base
) == INTEGER_CST
)
869 d
= fold_build2 (MINUS_EXPR
, niter_type
,
870 fold_convert (niter_type
, iv1
->base
),
871 fold_convert (niter_type
, TYPE_MIN_VALUE (type
)));
872 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
875 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
876 build_int_cst (niter_type
, 1));
877 bound
= fold_build2 (PLUS_EXPR
, type
,
878 TYPE_MIN_VALUE (type
), fold_convert (type
, diff
));
879 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
883 if (integer_zerop (assumption
))
885 if (!integer_nonzerop (assumption
))
886 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
887 niter
->assumptions
, assumption
);
889 iv0
->no_overflow
= true;
890 iv1
->no_overflow
= true;
894 /* Add an assumption to NITER that a loop whose ending condition
895 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
896 bounds the value of IV1->base - IV0->base. */
899 assert_loop_rolls_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
900 struct tree_niter_desc
*niter
, bounds
*bnds
)
902 tree assumption
= boolean_true_node
, bound
, diff
;
903 tree mbz
, mbzl
, mbzr
, type1
;
904 bool rolls_p
, no_overflow_p
;
908 /* We are going to compute the number of iterations as
909 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
910 variant of TYPE. This formula only works if
912 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
914 (where MAX is the maximum value of the unsigned variant of TYPE, and
915 the computations in this formula are performed in full precision,
916 i.e., without overflows).
918 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
919 we have a condition of the form iv0->base - step < iv1->base before the loop,
920 and for loops iv0->base < iv1->base - step * i the condition
921 iv0->base < iv1->base + step, due to loop header copying, which enable us
922 to prove the lower bound.
924 The upper bound is more complicated. Unless the expressions for initial
925 and final value themselves contain enough information, we usually cannot
926 derive it from the context. */
928 /* First check whether the answer does not follow from the bounds we gathered
930 if (integer_nonzerop (iv0
->step
))
931 dstep
= wi::to_widest (iv0
->step
);
934 dstep
= wi::sext (wi::to_widest (iv1
->step
), TYPE_PRECISION (type
));
939 wi::to_mpz (dstep
, mstep
, UNSIGNED
);
940 mpz_neg (mstep
, mstep
);
941 mpz_add_ui (mstep
, mstep
, 1);
943 rolls_p
= mpz_cmp (mstep
, bnds
->below
) <= 0;
946 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), max
, UNSIGNED
);
947 mpz_add (max
, max
, mstep
);
948 no_overflow_p
= (mpz_cmp (bnds
->up
, max
) <= 0
949 /* For pointers, only values lying inside a single object
950 can be compared or manipulated by pointer arithmetics.
951 Gcc in general does not allow or handle objects larger
952 than half of the address space, hence the upper bound
953 is satisfied for pointers. */
954 || POINTER_TYPE_P (type
));
958 if (rolls_p
&& no_overflow_p
)
962 if (POINTER_TYPE_P (type
))
965 /* Now the hard part; we must formulate the assumption(s) as expressions, and
966 we must be careful not to introduce overflow. */
968 if (integer_nonzerop (iv0
->step
))
970 diff
= fold_build2 (MINUS_EXPR
, type1
,
971 iv0
->step
, build_int_cst (type1
, 1));
973 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
974 0 address never belongs to any object, we can assume this for
976 if (!POINTER_TYPE_P (type
))
978 bound
= fold_build2 (PLUS_EXPR
, type1
,
979 TYPE_MIN_VALUE (type
), diff
);
980 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
984 /* And then we can compute iv0->base - diff, and compare it with
986 mbzl
= fold_build2 (MINUS_EXPR
, type1
,
987 fold_convert (type1
, iv0
->base
), diff
);
988 mbzr
= fold_convert (type1
, iv1
->base
);
992 diff
= fold_build2 (PLUS_EXPR
, type1
,
993 iv1
->step
, build_int_cst (type1
, 1));
995 if (!POINTER_TYPE_P (type
))
997 bound
= fold_build2 (PLUS_EXPR
, type1
,
998 TYPE_MAX_VALUE (type
), diff
);
999 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
1003 mbzl
= fold_convert (type1
, iv0
->base
);
1004 mbzr
= fold_build2 (MINUS_EXPR
, type1
,
1005 fold_convert (type1
, iv1
->base
), diff
);
1008 if (!integer_nonzerop (assumption
))
1009 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1010 niter
->assumptions
, assumption
);
1013 mbz
= fold_build2 (GT_EXPR
, boolean_type_node
, mbzl
, mbzr
);
1014 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1015 niter
->may_be_zero
, mbz
);
1019 /* Determines number of iterations of loop whose ending condition
1020 is IV0 < IV1. TYPE is the type of the iv. The number of
1021 iterations is stored to NITER. BNDS bounds the difference
1022 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
1023 that the exit must be taken eventually. */
1026 number_of_iterations_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1027 struct tree_niter_desc
*niter
,
1028 bool exit_must_be_taken
, bounds
*bnds
)
1030 tree niter_type
= unsigned_type_for (type
);
1031 tree delta
, step
, s
;
1034 if (integer_nonzerop (iv0
->step
))
1036 niter
->control
= *iv0
;
1037 niter
->cmp
= LT_EXPR
;
1038 niter
->bound
= iv1
->base
;
1042 niter
->control
= *iv1
;
1043 niter
->cmp
= GT_EXPR
;
1044 niter
->bound
= iv0
->base
;
1047 delta
= fold_build2 (MINUS_EXPR
, niter_type
,
1048 fold_convert (niter_type
, iv1
->base
),
1049 fold_convert (niter_type
, iv0
->base
));
1051 /* First handle the special case that the step is +-1. */
1052 if ((integer_onep (iv0
->step
) && integer_zerop (iv1
->step
))
1053 || (integer_all_onesp (iv1
->step
) && integer_zerop (iv0
->step
)))
1055 /* for (i = iv0->base; i < iv1->base; i++)
1059 for (i = iv1->base; i > iv0->base; i--).
1061 In both cases # of iterations is iv1->base - iv0->base, assuming that
1062 iv1->base >= iv0->base.
1064 First try to derive a lower bound on the value of
1065 iv1->base - iv0->base, computed in full precision. If the difference
1066 is nonnegative, we are done, otherwise we must record the
1069 if (mpz_sgn (bnds
->below
) < 0)
1070 niter
->may_be_zero
= fold_build2 (LT_EXPR
, boolean_type_node
,
1071 iv1
->base
, iv0
->base
);
1072 niter
->niter
= delta
;
1073 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, bnds
->up
, false),
1074 TYPE_SIGN (niter_type
));
1078 if (integer_nonzerop (iv0
->step
))
1079 step
= fold_convert (niter_type
, iv0
->step
);
1081 step
= fold_convert (niter_type
,
1082 fold_build1 (NEGATE_EXPR
, type
, iv1
->step
));
1084 /* If we can determine the final value of the control iv exactly, we can
1085 transform the condition to != comparison. In particular, this will be
1086 the case if DELTA is constant. */
1087 if (number_of_iterations_lt_to_ne (type
, iv0
, iv1
, niter
, &delta
, step
,
1088 exit_must_be_taken
, bnds
))
1092 zps
.base
= build_int_cst (niter_type
, 0);
1094 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1095 zps does not overflow. */
1096 zps
.no_overflow
= true;
1098 return number_of_iterations_ne (type
, &zps
, delta
, niter
, true, bnds
);
1101 /* Make sure that the control iv does not overflow. */
1102 if (!assert_no_overflow_lt (type
, iv0
, iv1
, niter
, step
))
1105 /* We determine the number of iterations as (delta + step - 1) / step. For
1106 this to work, we must know that iv1->base >= iv0->base - step + 1,
1107 otherwise the loop does not roll. */
1108 assert_loop_rolls_lt (type
, iv0
, iv1
, niter
, bnds
);
1110 s
= fold_build2 (MINUS_EXPR
, niter_type
,
1111 step
, build_int_cst (niter_type
, 1));
1112 delta
= fold_build2 (PLUS_EXPR
, niter_type
, delta
, s
);
1113 niter
->niter
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, delta
, step
);
1117 wi::to_mpz (step
, mstep
, UNSIGNED
);
1118 mpz_add (tmp
, bnds
->up
, mstep
);
1119 mpz_sub_ui (tmp
, tmp
, 1);
1120 mpz_fdiv_q (tmp
, tmp
, mstep
);
1121 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, tmp
, false),
1122 TYPE_SIGN (niter_type
));
1129 /* Determines number of iterations of loop whose ending condition
1130 is IV0 <= IV1. TYPE is the type of the iv. The number of
1131 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
1132 we know that this condition must eventually become false (we derived this
1133 earlier, and possibly set NITER->assumptions to make sure this
1134 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1137 number_of_iterations_le (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1138 struct tree_niter_desc
*niter
, bool exit_must_be_taken
,
1143 if (POINTER_TYPE_P (type
))
1146 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1147 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1148 value of the type. This we must know anyway, since if it is
1149 equal to this value, the loop rolls forever. We do not check
1150 this condition for pointer type ivs, as the code cannot rely on
1151 the object to that the pointer points being placed at the end of
1152 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1153 not defined for pointers). */
1155 if (!exit_must_be_taken
&& !POINTER_TYPE_P (type
))
1157 if (integer_nonzerop (iv0
->step
))
1158 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1159 iv1
->base
, TYPE_MAX_VALUE (type
));
1161 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1162 iv0
->base
, TYPE_MIN_VALUE (type
));
1164 if (integer_zerop (assumption
))
1166 if (!integer_nonzerop (assumption
))
1167 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1168 niter
->assumptions
, assumption
);
1171 if (integer_nonzerop (iv0
->step
))
1173 if (POINTER_TYPE_P (type
))
1174 iv1
->base
= fold_build_pointer_plus_hwi (iv1
->base
, 1);
1176 iv1
->base
= fold_build2 (PLUS_EXPR
, type1
, iv1
->base
,
1177 build_int_cst (type1
, 1));
1179 else if (POINTER_TYPE_P (type
))
1180 iv0
->base
= fold_build_pointer_plus_hwi (iv0
->base
, -1);
1182 iv0
->base
= fold_build2 (MINUS_EXPR
, type1
,
1183 iv0
->base
, build_int_cst (type1
, 1));
1185 bounds_add (bnds
, 1, type1
);
1187 return number_of_iterations_lt (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1191 /* Dumps description of affine induction variable IV to FILE. */
1194 dump_affine_iv (FILE *file
, affine_iv
*iv
)
1196 if (!integer_zerop (iv
->step
))
1197 fprintf (file
, "[");
1199 print_generic_expr (dump_file
, iv
->base
, TDF_SLIM
);
1201 if (!integer_zerop (iv
->step
))
1203 fprintf (file
, ", + , ");
1204 print_generic_expr (dump_file
, iv
->step
, TDF_SLIM
);
1205 fprintf (file
, "]%s", iv
->no_overflow
? "(no_overflow)" : "");
1209 /* Determine the number of iterations according to condition (for staying
1210 inside loop) which compares two induction variables using comparison
1211 operator CODE. The induction variable on left side of the comparison
1212 is IV0, the right-hand side is IV1. Both induction variables must have
1213 type TYPE, which must be an integer or pointer type. The steps of the
1214 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1216 LOOP is the loop whose number of iterations we are determining.
1218 ONLY_EXIT is true if we are sure this is the only way the loop could be
1219 exited (including possibly non-returning function calls, exceptions, etc.)
1220 -- in this case we can use the information whether the control induction
1221 variables can overflow or not in a more efficient way.
1223 if EVERY_ITERATION is true, we know the test is executed on every iteration.
1225 The results (number of iterations and assumptions as described in
1226 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
1227 Returns false if it fails to determine number of iterations, true if it
1228 was determined (possibly with some assumptions). */
1231 number_of_iterations_cond (struct loop
*loop
,
1232 tree type
, affine_iv
*iv0
, enum tree_code code
,
1233 affine_iv
*iv1
, struct tree_niter_desc
*niter
,
1234 bool only_exit
, bool every_iteration
)
1236 bool exit_must_be_taken
= false, ret
;
1239 /* If the test is not executed every iteration, wrapping may make the test
1241 TODO: the overflow case can be still used as unreliable estimate of upper
1242 bound. But we have no API to pass it down to number of iterations code
1243 and, at present, it will not use it anyway. */
1244 if (!every_iteration
1245 && (!iv0
->no_overflow
|| !iv1
->no_overflow
1246 || code
== NE_EXPR
|| code
== EQ_EXPR
))
1249 /* The meaning of these assumptions is this:
1251 then the rest of information does not have to be valid
1252 if may_be_zero then the loop does not roll, even if
1254 niter
->assumptions
= boolean_true_node
;
1255 niter
->may_be_zero
= boolean_false_node
;
1256 niter
->niter
= NULL_TREE
;
1258 niter
->bound
= NULL_TREE
;
1259 niter
->cmp
= ERROR_MARK
;
1261 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1262 the control variable is on lhs. */
1263 if (code
== GE_EXPR
|| code
== GT_EXPR
1264 || (code
== NE_EXPR
&& integer_zerop (iv0
->step
)))
1267 code
= swap_tree_comparison (code
);
1270 if (POINTER_TYPE_P (type
))
1272 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1273 to the same object. If they do, the control variable cannot wrap
1274 (as wrap around the bounds of memory will never return a pointer
1275 that would be guaranteed to point to the same object, even if we
1276 avoid undefined behavior by casting to size_t and back). */
1277 iv0
->no_overflow
= true;
1278 iv1
->no_overflow
= true;
1281 /* If the control induction variable does not overflow and the only exit
1282 from the loop is the one that we analyze, we know it must be taken
1286 if (!integer_zerop (iv0
->step
) && iv0
->no_overflow
)
1287 exit_must_be_taken
= true;
1288 else if (!integer_zerop (iv1
->step
) && iv1
->no_overflow
)
1289 exit_must_be_taken
= true;
1292 /* We can handle the case when neither of the sides of the comparison is
1293 invariant, provided that the test is NE_EXPR. This rarely occurs in
1294 practice, but it is simple enough to manage. */
1295 if (!integer_zerop (iv0
->step
) && !integer_zerop (iv1
->step
))
1297 tree step_type
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1298 if (code
!= NE_EXPR
)
1301 iv0
->step
= fold_binary_to_constant (MINUS_EXPR
, step_type
,
1302 iv0
->step
, iv1
->step
);
1303 iv0
->no_overflow
= false;
1304 iv1
->step
= build_int_cst (step_type
, 0);
1305 iv1
->no_overflow
= true;
1308 /* If the result of the comparison is a constant, the loop is weird. More
1309 precise handling would be possible, but the situation is not common enough
1310 to waste time on it. */
1311 if (integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
))
1314 /* Ignore loops of while (i-- < 10) type. */
1315 if (code
!= NE_EXPR
)
1317 if (iv0
->step
&& tree_int_cst_sign_bit (iv0
->step
))
1320 if (!integer_zerop (iv1
->step
) && !tree_int_cst_sign_bit (iv1
->step
))
1324 /* If the loop exits immediately, there is nothing to do. */
1325 tree tem
= fold_binary (code
, boolean_type_node
, iv0
->base
, iv1
->base
);
1326 if (tem
&& integer_zerop (tem
))
1328 niter
->niter
= build_int_cst (unsigned_type_for (type
), 0);
1333 /* OK, now we know we have a senseful loop. Handle several cases, depending
1334 on what comparison operator is used. */
1335 bound_difference (loop
, iv1
->base
, iv0
->base
, &bnds
);
1337 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1340 "Analyzing # of iterations of loop %d\n", loop
->num
);
1342 fprintf (dump_file
, " exit condition ");
1343 dump_affine_iv (dump_file
, iv0
);
1344 fprintf (dump_file
, " %s ",
1345 code
== NE_EXPR
? "!="
1346 : code
== LT_EXPR
? "<"
1348 dump_affine_iv (dump_file
, iv1
);
1349 fprintf (dump_file
, "\n");
1351 fprintf (dump_file
, " bounds on difference of bases: ");
1352 mpz_out_str (dump_file
, 10, bnds
.below
);
1353 fprintf (dump_file
, " ... ");
1354 mpz_out_str (dump_file
, 10, bnds
.up
);
1355 fprintf (dump_file
, "\n");
1361 gcc_assert (integer_zerop (iv1
->step
));
1362 ret
= number_of_iterations_ne (type
, iv0
, iv1
->base
, niter
,
1363 exit_must_be_taken
, &bnds
);
1367 ret
= number_of_iterations_lt (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1372 ret
= number_of_iterations_le (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1380 mpz_clear (bnds
.up
);
1381 mpz_clear (bnds
.below
);
1383 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1387 fprintf (dump_file
, " result:\n");
1388 if (!integer_nonzerop (niter
->assumptions
))
1390 fprintf (dump_file
, " under assumptions ");
1391 print_generic_expr (dump_file
, niter
->assumptions
, TDF_SLIM
);
1392 fprintf (dump_file
, "\n");
1395 if (!integer_zerop (niter
->may_be_zero
))
1397 fprintf (dump_file
, " zero if ");
1398 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
1399 fprintf (dump_file
, "\n");
1402 fprintf (dump_file
, " # of iterations ");
1403 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
1404 fprintf (dump_file
, ", bounded by ");
1405 print_decu (niter
->max
, dump_file
);
1406 fprintf (dump_file
, "\n");
1409 fprintf (dump_file
, " failed\n\n");
1414 /* Substitute NEW for OLD in EXPR and fold the result. */
1417 simplify_replace_tree (tree expr
, tree old
, tree new_tree
)
1420 tree ret
= NULL_TREE
, e
, se
;
1425 /* Do not bother to replace constants. */
1426 if (CONSTANT_CLASS_P (old
))
1430 || operand_equal_p (expr
, old
, 0))
1431 return unshare_expr (new_tree
);
1436 n
= TREE_OPERAND_LENGTH (expr
);
1437 for (i
= 0; i
< n
; i
++)
1439 e
= TREE_OPERAND (expr
, i
);
1440 se
= simplify_replace_tree (e
, old
, new_tree
);
1445 ret
= copy_node (expr
);
1447 TREE_OPERAND (ret
, i
) = se
;
1450 return (ret
? fold (ret
) : expr
);
1453 /* Expand definitions of ssa names in EXPR as long as they are simple
1454 enough, and return the new expression. */
1457 expand_simple_operations (tree expr
)
1460 tree ret
= NULL_TREE
, e
, ee
, e1
;
1461 enum tree_code code
;
1464 if (expr
== NULL_TREE
)
1467 if (is_gimple_min_invariant (expr
))
1470 code
= TREE_CODE (expr
);
1471 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
1473 n
= TREE_OPERAND_LENGTH (expr
);
1474 for (i
= 0; i
< n
; i
++)
1476 e
= TREE_OPERAND (expr
, i
);
1477 ee
= expand_simple_operations (e
);
1482 ret
= copy_node (expr
);
1484 TREE_OPERAND (ret
, i
) = ee
;
1490 fold_defer_overflow_warnings ();
1492 fold_undefer_and_ignore_overflow_warnings ();
1496 if (TREE_CODE (expr
) != SSA_NAME
)
1499 stmt
= SSA_NAME_DEF_STMT (expr
);
1500 if (gimple_code (stmt
) == GIMPLE_PHI
)
1502 basic_block src
, dest
;
1504 if (gimple_phi_num_args (stmt
) != 1)
1506 e
= PHI_ARG_DEF (stmt
, 0);
1508 /* Avoid propagating through loop exit phi nodes, which
1509 could break loop-closed SSA form restrictions. */
1510 dest
= gimple_bb (stmt
);
1511 src
= single_pred (dest
);
1512 if (TREE_CODE (e
) == SSA_NAME
1513 && src
->loop_father
!= dest
->loop_father
)
1516 return expand_simple_operations (e
);
1518 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1521 /* Avoid expanding to expressions that contain SSA names that need
1522 to take part in abnormal coalescing. */
1524 FOR_EACH_SSA_TREE_OPERAND (e
, stmt
, iter
, SSA_OP_USE
)
1525 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (e
))
1528 e
= gimple_assign_rhs1 (stmt
);
1529 code
= gimple_assign_rhs_code (stmt
);
1530 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1532 if (is_gimple_min_invariant (e
))
1535 if (code
== SSA_NAME
)
1536 return expand_simple_operations (e
);
1544 /* Casts are simple. */
1545 ee
= expand_simple_operations (e
);
1546 return fold_build1 (code
, TREE_TYPE (expr
), ee
);
1550 case POINTER_PLUS_EXPR
:
1551 /* And increments and decrements by a constant are simple. */
1552 e1
= gimple_assign_rhs2 (stmt
);
1553 if (!is_gimple_min_invariant (e1
))
1556 ee
= expand_simple_operations (e
);
1557 return fold_build2 (code
, TREE_TYPE (expr
), ee
, e1
);
1564 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1565 expression (or EXPR unchanged, if no simplification was possible). */
1568 tree_simplify_using_condition_1 (tree cond
, tree expr
)
1571 tree e
, te
, e0
, e1
, e2
, notcond
;
1572 enum tree_code code
= TREE_CODE (expr
);
1574 if (code
== INTEGER_CST
)
1577 if (code
== TRUTH_OR_EXPR
1578 || code
== TRUTH_AND_EXPR
1579 || code
== COND_EXPR
)
1583 e0
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 0));
1584 if (TREE_OPERAND (expr
, 0) != e0
)
1587 e1
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 1));
1588 if (TREE_OPERAND (expr
, 1) != e1
)
1591 if (code
== COND_EXPR
)
1593 e2
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 2));
1594 if (TREE_OPERAND (expr
, 2) != e2
)
1602 if (code
== COND_EXPR
)
1603 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1605 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1611 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
1612 propagation, and vice versa. Fold does not handle this, since it is
1613 considered too expensive. */
1614 if (TREE_CODE (cond
) == EQ_EXPR
)
1616 e0
= TREE_OPERAND (cond
, 0);
1617 e1
= TREE_OPERAND (cond
, 1);
1619 /* We know that e0 == e1. Check whether we cannot simplify expr
1621 e
= simplify_replace_tree (expr
, e0
, e1
);
1622 if (integer_zerop (e
) || integer_nonzerop (e
))
1625 e
= simplify_replace_tree (expr
, e1
, e0
);
1626 if (integer_zerop (e
) || integer_nonzerop (e
))
1629 if (TREE_CODE (expr
) == EQ_EXPR
)
1631 e0
= TREE_OPERAND (expr
, 0);
1632 e1
= TREE_OPERAND (expr
, 1);
1634 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
1635 e
= simplify_replace_tree (cond
, e0
, e1
);
1636 if (integer_zerop (e
))
1638 e
= simplify_replace_tree (cond
, e1
, e0
);
1639 if (integer_zerop (e
))
1642 if (TREE_CODE (expr
) == NE_EXPR
)
1644 e0
= TREE_OPERAND (expr
, 0);
1645 e1
= TREE_OPERAND (expr
, 1);
1647 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
1648 e
= simplify_replace_tree (cond
, e0
, e1
);
1649 if (integer_zerop (e
))
1650 return boolean_true_node
;
1651 e
= simplify_replace_tree (cond
, e1
, e0
);
1652 if (integer_zerop (e
))
1653 return boolean_true_node
;
1656 te
= expand_simple_operations (expr
);
1658 /* Check whether COND ==> EXPR. */
1659 notcond
= invert_truthvalue (cond
);
1660 e
= fold_binary (TRUTH_OR_EXPR
, boolean_type_node
, notcond
, te
);
1661 if (e
&& integer_nonzerop (e
))
1664 /* Check whether COND ==> not EXPR. */
1665 e
= fold_binary (TRUTH_AND_EXPR
, boolean_type_node
, cond
, te
);
1666 if (e
&& integer_zerop (e
))
1672 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1673 expression (or EXPR unchanged, if no simplification was possible).
1674 Wrapper around tree_simplify_using_condition_1 that ensures that chains
1675 of simple operations in definitions of ssa names in COND are expanded,
1676 so that things like casts or incrementing the value of the bound before
1677 the loop do not cause us to fail. */
1680 tree_simplify_using_condition (tree cond
, tree expr
)
1682 cond
= expand_simple_operations (cond
);
1684 return tree_simplify_using_condition_1 (cond
, expr
);
1687 /* Tries to simplify EXPR using the conditions on entry to LOOP.
1688 Returns the simplified expression (or EXPR unchanged, if no
1689 simplification was possible).*/
1692 simplify_using_initial_conditions (struct loop
*loop
, tree expr
)
1700 if (TREE_CODE (expr
) == INTEGER_CST
)
1703 /* Limit walking the dominators to avoid quadraticness in
1704 the number of BBs times the number of loops in degenerate
1706 for (bb
= loop
->header
;
1707 bb
!= ENTRY_BLOCK_PTR
&& cnt
< MAX_DOMINATORS_TO_WALK
;
1708 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1710 if (!single_pred_p (bb
))
1712 e
= single_pred_edge (bb
);
1714 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
1717 stmt
= last_stmt (e
->src
);
1718 cond
= fold_build2 (gimple_cond_code (stmt
),
1720 gimple_cond_lhs (stmt
),
1721 gimple_cond_rhs (stmt
));
1722 if (e
->flags
& EDGE_FALSE_VALUE
)
1723 cond
= invert_truthvalue (cond
);
1724 expr
= tree_simplify_using_condition (cond
, expr
);
1731 /* Tries to simplify EXPR using the evolutions of the loop invariants
1732 in the superloops of LOOP. Returns the simplified expression
1733 (or EXPR unchanged, if no simplification was possible). */
1736 simplify_using_outer_evolutions (struct loop
*loop
, tree expr
)
1738 enum tree_code code
= TREE_CODE (expr
);
1742 if (is_gimple_min_invariant (expr
))
1745 if (code
== TRUTH_OR_EXPR
1746 || code
== TRUTH_AND_EXPR
1747 || code
== COND_EXPR
)
1751 e0
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 0));
1752 if (TREE_OPERAND (expr
, 0) != e0
)
1755 e1
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 1));
1756 if (TREE_OPERAND (expr
, 1) != e1
)
1759 if (code
== COND_EXPR
)
1761 e2
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 2));
1762 if (TREE_OPERAND (expr
, 2) != e2
)
1770 if (code
== COND_EXPR
)
1771 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1773 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1779 e
= instantiate_parameters (loop
, expr
);
1780 if (is_gimple_min_invariant (e
))
1786 /* Returns true if EXIT is the only possible exit from LOOP. */
1789 loop_only_exit_p (const struct loop
*loop
, const_edge exit
)
1792 gimple_stmt_iterator bsi
;
1796 if (exit
!= single_exit (loop
))
1799 body
= get_loop_body (loop
);
1800 for (i
= 0; i
< loop
->num_nodes
; i
++)
1802 for (bsi
= gsi_start_bb (body
[i
]); !gsi_end_p (bsi
); gsi_next (&bsi
))
1804 call
= gsi_stmt (bsi
);
1805 if (gimple_code (call
) != GIMPLE_CALL
)
1808 if (gimple_has_side_effects (call
))
1820 /* Stores description of number of iterations of LOOP derived from
1821 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
1822 useful information could be derived (and fields of NITER has
1823 meaning described in comments at struct tree_niter_desc
1824 declaration), false otherwise. If WARN is true and
1825 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1826 potentially unsafe assumptions.
1827 When EVERY_ITERATION is true, only tests that are known to be executed
1828 every iteration are considered (i.e. only test that alone bounds the loop).
1832 number_of_iterations_exit (struct loop
*loop
, edge exit
,
1833 struct tree_niter_desc
*niter
,
1834 bool warn
, bool every_iteration
)
1839 enum tree_code code
;
1843 safe
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit
->src
);
1845 if (every_iteration
&& !safe
)
1848 niter
->assumptions
= boolean_false_node
;
1849 stmt
= last_stmt (exit
->src
);
1850 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1853 /* We want the condition for staying inside loop. */
1854 code
= gimple_cond_code (stmt
);
1855 if (exit
->flags
& EDGE_TRUE_VALUE
)
1856 code
= invert_tree_comparison (code
, false);
1871 op0
= gimple_cond_lhs (stmt
);
1872 op1
= gimple_cond_rhs (stmt
);
1873 type
= TREE_TYPE (op0
);
1875 if (TREE_CODE (type
) != INTEGER_TYPE
1876 && !POINTER_TYPE_P (type
))
1879 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, false))
1881 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, false))
1884 /* We don't want to see undefined signed overflow warnings while
1885 computing the number of iterations. */
1886 fold_defer_overflow_warnings ();
1888 iv0
.base
= expand_simple_operations (iv0
.base
);
1889 iv1
.base
= expand_simple_operations (iv1
.base
);
1890 if (!number_of_iterations_cond (loop
, type
, &iv0
, code
, &iv1
, niter
,
1891 loop_only_exit_p (loop
, exit
), safe
))
1893 fold_undefer_and_ignore_overflow_warnings ();
1899 niter
->assumptions
= simplify_using_outer_evolutions (loop
,
1900 niter
->assumptions
);
1901 niter
->may_be_zero
= simplify_using_outer_evolutions (loop
,
1902 niter
->may_be_zero
);
1903 niter
->niter
= simplify_using_outer_evolutions (loop
, niter
->niter
);
1907 = simplify_using_initial_conditions (loop
,
1908 niter
->assumptions
);
1910 = simplify_using_initial_conditions (loop
,
1911 niter
->may_be_zero
);
1913 fold_undefer_and_ignore_overflow_warnings ();
1915 /* If NITER has simplified into a constant, update MAX. */
1916 if (TREE_CODE (niter
->niter
) == INTEGER_CST
)
1917 niter
->max
= wi::to_widest (niter
->niter
);
1919 if (integer_onep (niter
->assumptions
))
1922 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1923 But if we can prove that there is overflow or some other source of weird
1924 behavior, ignore the loop even with -funsafe-loop-optimizations. */
1925 if (integer_zerop (niter
->assumptions
) || !single_exit (loop
))
1928 if (flag_unsafe_loop_optimizations
)
1929 niter
->assumptions
= boolean_true_node
;
1933 const char *wording
;
1934 location_t loc
= gimple_location (stmt
);
1936 /* We can provide a more specific warning if one of the operator is
1937 constant and the other advances by +1 or -1. */
1938 if (!integer_zerop (iv1
.step
)
1939 ? (integer_zerop (iv0
.step
)
1940 && (integer_onep (iv1
.step
) || integer_all_onesp (iv1
.step
)))
1941 : (integer_onep (iv0
.step
) || integer_all_onesp (iv0
.step
)))
1943 flag_unsafe_loop_optimizations
1944 ? N_("assuming that the loop is not infinite")
1945 : N_("cannot optimize possibly infinite loops");
1948 flag_unsafe_loop_optimizations
1949 ? N_("assuming that the loop counter does not overflow")
1950 : N_("cannot optimize loop, the loop counter may overflow");
1952 warning_at ((LOCATION_LINE (loc
) > 0) ? loc
: input_location
,
1953 OPT_Wunsafe_loop_optimizations
, "%s", gettext (wording
));
1956 return flag_unsafe_loop_optimizations
;
1959 /* Try to determine the number of iterations of LOOP. If we succeed,
1960 expression giving number of iterations is returned and *EXIT is
1961 set to the edge from that the information is obtained. Otherwise
1962 chrec_dont_know is returned. */
1965 find_loop_niter (struct loop
*loop
, edge
*exit
)
1968 vec
<edge
> exits
= get_loop_exit_edges (loop
);
1970 tree niter
= NULL_TREE
, aniter
;
1971 struct tree_niter_desc desc
;
1974 FOR_EACH_VEC_ELT (exits
, i
, ex
)
1976 if (!number_of_iterations_exit (loop
, ex
, &desc
, false))
1979 if (integer_nonzerop (desc
.may_be_zero
))
1981 /* We exit in the first iteration through this exit.
1982 We won't find anything better. */
1983 niter
= build_int_cst (unsigned_type_node
, 0);
1988 if (!integer_zerop (desc
.may_be_zero
))
1991 aniter
= desc
.niter
;
1995 /* Nothing recorded yet. */
2001 /* Prefer constants, the lower the better. */
2002 if (TREE_CODE (aniter
) != INTEGER_CST
)
2005 if (TREE_CODE (niter
) != INTEGER_CST
)
2012 if (tree_int_cst_lt (aniter
, niter
))
2021 return niter
? niter
: chrec_dont_know
;
2024 /* Return true if loop is known to have bounded number of iterations. */
2027 finite_loop_p (struct loop
*loop
)
2032 if (flag_unsafe_loop_optimizations
)
2034 flags
= flags_from_decl_or_type (current_function_decl
);
2035 if ((flags
& (ECF_CONST
|ECF_PURE
)) && !(flags
& ECF_LOOPING_CONST_OR_PURE
))
2037 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2038 fprintf (dump_file
, "Found loop %i to be finite: it is within pure or const function.\n",
2043 if (loop
->any_upper_bound
2044 || max_loop_iterations (loop
, &nit
))
2046 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2047 fprintf (dump_file
, "Found loop %i to be finite: upper bound found.\n",
2056 Analysis of a number of iterations of a loop by a brute-force evaluation.
2060 /* Bound on the number of iterations we try to evaluate. */
2062 #define MAX_ITERATIONS_TO_TRACK \
2063 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
2065 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
2066 result by a chain of operations such that all but exactly one of their
2067 operands are constants. */
2070 chain_of_csts_start (struct loop
*loop
, tree x
)
2072 gimple stmt
= SSA_NAME_DEF_STMT (x
);
2074 basic_block bb
= gimple_bb (stmt
);
2075 enum tree_code code
;
2078 || !flow_bb_inside_loop_p (loop
, bb
))
2081 if (gimple_code (stmt
) == GIMPLE_PHI
)
2083 if (bb
== loop
->header
)
2089 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2092 code
= gimple_assign_rhs_code (stmt
);
2093 if (gimple_references_memory_p (stmt
)
2094 || TREE_CODE_CLASS (code
) == tcc_reference
2095 || (code
== ADDR_EXPR
2096 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
2099 use
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
2100 if (use
== NULL_TREE
)
2103 return chain_of_csts_start (loop
, use
);
2106 /* Determines whether the expression X is derived from a result of a phi node
2107 in header of LOOP such that
2109 * the derivation of X consists only from operations with constants
2110 * the initial value of the phi node is constant
2111 * the value of the phi node in the next iteration can be derived from the
2112 value in the current iteration by a chain of operations with constants.
2114 If such phi node exists, it is returned, otherwise NULL is returned. */
2117 get_base_for (struct loop
*loop
, tree x
)
2122 if (is_gimple_min_invariant (x
))
2125 phi
= chain_of_csts_start (loop
, x
);
2129 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2130 next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2132 if (TREE_CODE (next
) != SSA_NAME
)
2135 if (!is_gimple_min_invariant (init
))
2138 if (chain_of_csts_start (loop
, next
) != phi
)
2144 /* Given an expression X, then
2146 * if X is NULL_TREE, we return the constant BASE.
2147 * otherwise X is a SSA name, whose value in the considered loop is derived
2148 by a chain of operations with constant from a result of a phi node in
2149 the header of the loop. Then we return value of X when the value of the
2150 result of this phi node is given by the constant BASE. */
2153 get_val_for (tree x
, tree base
)
2157 gcc_assert (is_gimple_min_invariant (base
));
2162 stmt
= SSA_NAME_DEF_STMT (x
);
2163 if (gimple_code (stmt
) == GIMPLE_PHI
)
2166 gcc_assert (is_gimple_assign (stmt
));
2168 /* STMT must be either an assignment of a single SSA name or an
2169 expression involving an SSA name and a constant. Try to fold that
2170 expression using the value for the SSA name. */
2171 if (gimple_assign_ssa_name_copy_p (stmt
))
2172 return get_val_for (gimple_assign_rhs1 (stmt
), base
);
2173 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_UNARY_RHS
2174 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
2176 return fold_build1 (gimple_assign_rhs_code (stmt
),
2177 gimple_expr_type (stmt
),
2178 get_val_for (gimple_assign_rhs1 (stmt
), base
));
2180 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_BINARY_RHS
)
2182 tree rhs1
= gimple_assign_rhs1 (stmt
);
2183 tree rhs2
= gimple_assign_rhs2 (stmt
);
2184 if (TREE_CODE (rhs1
) == SSA_NAME
)
2185 rhs1
= get_val_for (rhs1
, base
);
2186 else if (TREE_CODE (rhs2
) == SSA_NAME
)
2187 rhs2
= get_val_for (rhs2
, base
);
2190 return fold_build2 (gimple_assign_rhs_code (stmt
),
2191 gimple_expr_type (stmt
), rhs1
, rhs2
);
2198 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2199 by brute force -- i.e. by determining the value of the operands of the
2200 condition at EXIT in first few iterations of the loop (assuming that
2201 these values are constant) and determining the first one in that the
2202 condition is not satisfied. Returns the constant giving the number
2203 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
2206 loop_niter_by_eval (struct loop
*loop
, edge exit
)
2209 tree op
[2], val
[2], next
[2], aval
[2];
2214 cond
= last_stmt (exit
->src
);
2215 if (!cond
|| gimple_code (cond
) != GIMPLE_COND
)
2216 return chrec_dont_know
;
2218 cmp
= gimple_cond_code (cond
);
2219 if (exit
->flags
& EDGE_TRUE_VALUE
)
2220 cmp
= invert_tree_comparison (cmp
, false);
2230 op
[0] = gimple_cond_lhs (cond
);
2231 op
[1] = gimple_cond_rhs (cond
);
2235 return chrec_dont_know
;
2238 for (j
= 0; j
< 2; j
++)
2240 if (is_gimple_min_invariant (op
[j
]))
2243 next
[j
] = NULL_TREE
;
2248 phi
= get_base_for (loop
, op
[j
]);
2250 return chrec_dont_know
;
2251 val
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2252 next
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2256 /* Don't issue signed overflow warnings. */
2257 fold_defer_overflow_warnings ();
2259 for (i
= 0; i
< MAX_ITERATIONS_TO_TRACK
; i
++)
2261 for (j
= 0; j
< 2; j
++)
2262 aval
[j
] = get_val_for (op
[j
], val
[j
]);
2264 acnd
= fold_binary (cmp
, boolean_type_node
, aval
[0], aval
[1]);
2265 if (acnd
&& integer_zerop (acnd
))
2267 fold_undefer_and_ignore_overflow_warnings ();
2268 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2270 "Proved that loop %d iterates %d times using brute force.\n",
2272 return build_int_cst (unsigned_type_node
, i
);
2275 for (j
= 0; j
< 2; j
++)
2277 val
[j
] = get_val_for (next
[j
], val
[j
]);
2278 if (!is_gimple_min_invariant (val
[j
]))
2280 fold_undefer_and_ignore_overflow_warnings ();
2281 return chrec_dont_know
;
2286 fold_undefer_and_ignore_overflow_warnings ();
2288 return chrec_dont_know
;
2291 /* Finds the exit of the LOOP by that the loop exits after a constant
2292 number of iterations and stores the exit edge to *EXIT. The constant
2293 giving the number of iterations of LOOP is returned. The number of
2294 iterations is determined using loop_niter_by_eval (i.e. by brute force
2295 evaluation). If we are unable to find the exit for that loop_niter_by_eval
2296 determines the number of iterations, chrec_dont_know is returned. */
2299 find_loop_niter_by_eval (struct loop
*loop
, edge
*exit
)
2302 vec
<edge
> exits
= get_loop_exit_edges (loop
);
2304 tree niter
= NULL_TREE
, aniter
;
2308 /* Loops with multiple exits are expensive to handle and less important. */
2309 if (!flag_expensive_optimizations
2310 && exits
.length () > 1)
2313 return chrec_dont_know
;
2316 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2318 if (!just_once_each_iteration_p (loop
, ex
->src
))
2321 aniter
= loop_niter_by_eval (loop
, ex
);
2322 if (chrec_contains_undetermined (aniter
))
2326 && !tree_int_cst_lt (aniter
, niter
))
2334 return niter
? niter
: chrec_dont_know
;
2339 Analysis of upper bounds on number of iterations of a loop.
2343 static widest_int
derive_constant_upper_bound_ops (tree
, tree
,
2344 enum tree_code
, tree
);
2346 /* Returns a constant upper bound on the value of the right-hand side of
2347 an assignment statement STMT. */
2350 derive_constant_upper_bound_assign (gimple stmt
)
2352 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2353 tree op0
= gimple_assign_rhs1 (stmt
);
2354 tree op1
= gimple_assign_rhs2 (stmt
);
2356 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt
)),
2360 /* Returns a constant upper bound on the value of expression VAL. VAL
2361 is considered to be unsigned. If its type is signed, its value must
2365 derive_constant_upper_bound (tree val
)
2367 enum tree_code code
;
2370 extract_ops_from_tree (val
, &code
, &op0
, &op1
);
2371 return derive_constant_upper_bound_ops (TREE_TYPE (val
), op0
, code
, op1
);
2374 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
2375 whose type is TYPE. The expression is considered to be unsigned. If
2376 its type is signed, its value must be nonnegative. */
2379 derive_constant_upper_bound_ops (tree type
, tree op0
,
2380 enum tree_code code
, tree op1
)
2383 widest_int bnd
, max
, mmax
, cst
;
2386 if (INTEGRAL_TYPE_P (type
))
2387 maxt
= TYPE_MAX_VALUE (type
);
2389 maxt
= upper_bound_in_type (type
, type
);
2391 max
= wi::to_widest (maxt
);
2396 return wi::to_widest (op0
);
2399 subtype
= TREE_TYPE (op0
);
2400 if (!TYPE_UNSIGNED (subtype
)
2401 /* If TYPE is also signed, the fact that VAL is nonnegative implies
2402 that OP0 is nonnegative. */
2403 && TYPE_UNSIGNED (type
)
2404 && !tree_expr_nonnegative_p (op0
))
2406 /* If we cannot prove that the casted expression is nonnegative,
2407 we cannot establish more useful upper bound than the precision
2408 of the type gives us. */
2412 /* We now know that op0 is an nonnegative value. Try deriving an upper
2414 bnd
= derive_constant_upper_bound (op0
);
2416 /* If the bound does not fit in TYPE, max. value of TYPE could be
2418 if (wi::ltu_p (max
, bnd
))
2424 case POINTER_PLUS_EXPR
:
2426 if (TREE_CODE (op1
) != INTEGER_CST
2427 || !tree_expr_nonnegative_p (op0
))
2430 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
2431 choose the most logical way how to treat this constant regardless
2432 of the signedness of the type. */
2433 cst
= wi::sext (wi::to_widest (op1
), TYPE_PRECISION (type
));
2434 if (code
!= MINUS_EXPR
)
2437 bnd
= derive_constant_upper_bound (op0
);
2439 if (wi::neg_p (cst
))
2442 /* Avoid CST == 0x80000... */
2443 if (wi::neg_p (cst
))
2446 /* OP0 + CST. We need to check that
2447 BND <= MAX (type) - CST. */
2450 if (wi::ltu_p (bnd
, max
))
2457 /* OP0 - CST, where CST >= 0.
2459 If TYPE is signed, we have already verified that OP0 >= 0, and we
2460 know that the result is nonnegative. This implies that
2463 If TYPE is unsigned, we must additionally know that OP0 >= CST,
2464 otherwise the operation underflows.
2467 /* This should only happen if the type is unsigned; however, for
2468 buggy programs that use overflowing signed arithmetics even with
2469 -fno-wrapv, this condition may also be true for signed values. */
2470 if (wi::ltu_p (bnd
, cst
))
2473 if (TYPE_UNSIGNED (type
))
2475 tree tem
= fold_binary (GE_EXPR
, boolean_type_node
, op0
,
2476 wide_int_to_tree (type
, cst
));
2477 if (!tem
|| integer_nonzerop (tem
))
2486 case FLOOR_DIV_EXPR
:
2487 case EXACT_DIV_EXPR
:
2488 if (TREE_CODE (op1
) != INTEGER_CST
2489 || tree_int_cst_sign_bit (op1
))
2492 bnd
= derive_constant_upper_bound (op0
);
2493 return wi::udiv_floor (bnd
, wi::to_widest (op1
));
2496 if (TREE_CODE (op1
) != INTEGER_CST
2497 || tree_int_cst_sign_bit (op1
))
2499 return wi::to_widest (op1
);
2502 stmt
= SSA_NAME_DEF_STMT (op0
);
2503 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2504 || gimple_assign_lhs (stmt
) != op0
)
2506 return derive_constant_upper_bound_assign (stmt
);
2513 /* Emit a -Waggressive-loop-optimizations warning if needed. */
2516 do_warn_aggressive_loop_optimizations (struct loop
*loop
,
2517 widest_int i_bound
, gimple stmt
)
2519 /* Don't warn if the loop doesn't have known constant bound. */
2520 if (!loop
->nb_iterations
2521 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
2522 || !warn_aggressive_loop_optimizations
2523 /* To avoid warning multiple times for the same loop,
2524 only start warning when we preserve loops. */
2525 || (cfun
->curr_properties
& PROP_loops
) == 0
2526 /* Only warn once per loop. */
2527 || loop
->warned_aggressive_loop_optimizations
2528 /* Only warn if undefined behavior gives us lower estimate than the
2529 known constant bound. */
2530 || wi::cmpu (i_bound
, wi::to_widest (loop
->nb_iterations
)) >= 0
2531 /* And undefined behavior happens unconditionally. */
2532 || !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (stmt
)))
2535 edge e
= single_exit (loop
);
2539 gimple estmt
= last_stmt (e
->src
);
2540 if (warning_at (gimple_location (stmt
), OPT_Waggressive_loop_optimizations
,
2541 "iteration %E invokes undefined behavior",
2542 wide_int_to_tree (TREE_TYPE (loop
->nb_iterations
),
2544 inform (gimple_location (estmt
), "containing loop");
2545 loop
->warned_aggressive_loop_optimizations
= true;
2548 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
2549 is true if the loop is exited immediately after STMT, and this exit
2550 is taken at last when the STMT is executed BOUND + 1 times.
2551 REALISTIC is true if BOUND is expected to be close to the real number
2552 of iterations. UPPER is true if we are sure the loop iterates at most
2553 BOUND times. I_BOUND is an unsigned wide_int upper estimate on BOUND. */
2556 record_estimate (struct loop
*loop
, tree bound
, widest_int i_bound
,
2557 gimple at_stmt
, bool is_exit
, bool realistic
, bool upper
)
2561 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2563 fprintf (dump_file
, "Statement %s", is_exit
? "(exit)" : "");
2564 print_gimple_stmt (dump_file
, at_stmt
, 0, TDF_SLIM
);
2565 fprintf (dump_file
, " is %sexecuted at most ",
2566 upper
? "" : "probably ");
2567 print_generic_expr (dump_file
, bound
, TDF_SLIM
);
2568 fprintf (dump_file
, " (bounded by ");
2569 print_decu (i_bound
, dump_file
);
2570 fprintf (dump_file
, ") + 1 times in loop %d.\n", loop
->num
);
2573 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
2574 real number of iterations. */
2575 if (TREE_CODE (bound
) != INTEGER_CST
)
2578 gcc_checking_assert (i_bound
== wi::to_widest (bound
));
2579 if (!upper
&& !realistic
)
2582 /* If we have a guaranteed upper bound, record it in the appropriate
2583 list, unless this is an !is_exit bound (i.e. undefined behavior in
2584 at_stmt) in a loop with known constant number of iterations. */
2587 || loop
->nb_iterations
== NULL_TREE
2588 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
))
2590 struct nb_iter_bound
*elt
= ggc_alloc_nb_iter_bound ();
2592 elt
->bound
= i_bound
;
2593 elt
->stmt
= at_stmt
;
2594 elt
->is_exit
= is_exit
;
2595 elt
->next
= loop
->bounds
;
2599 /* If statement is executed on every path to the loop latch, we can directly
2600 infer the upper bound on the # of iterations of the loop. */
2601 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (at_stmt
)))
2604 /* Update the number of iteration estimates according to the bound.
2605 If at_stmt is an exit then the loop latch is executed at most BOUND times,
2606 otherwise it can be executed BOUND + 1 times. We will lower the estimate
2607 later if such statement must be executed on last iteration */
2614 /* If an overflow occurred, ignore the result. */
2615 if (wi::ltu_p (i_bound
, delta
))
2618 if (upper
&& !is_exit
)
2619 do_warn_aggressive_loop_optimizations (loop
, i_bound
, at_stmt
);
2620 record_niter_bound (loop
, i_bound
, realistic
, upper
);
2623 /* Record the estimate on number of iterations of LOOP based on the fact that
2624 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
2625 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
2626 estimated number of iterations is expected to be close to the real one.
2627 UPPER is true if we are sure the induction variable does not wrap. */
2630 record_nonwrapping_iv (struct loop
*loop
, tree base
, tree step
, gimple stmt
,
2631 tree low
, tree high
, bool realistic
, bool upper
)
2633 tree niter_bound
, extreme
, delta
;
2634 tree type
= TREE_TYPE (base
), unsigned_type
;
2636 if (TREE_CODE (step
) != INTEGER_CST
|| integer_zerop (step
))
2639 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2641 fprintf (dump_file
, "Induction variable (");
2642 print_generic_expr (dump_file
, TREE_TYPE (base
), TDF_SLIM
);
2643 fprintf (dump_file
, ") ");
2644 print_generic_expr (dump_file
, base
, TDF_SLIM
);
2645 fprintf (dump_file
, " + ");
2646 print_generic_expr (dump_file
, step
, TDF_SLIM
);
2647 fprintf (dump_file
, " * iteration does not wrap in statement ");
2648 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2649 fprintf (dump_file
, " in loop %d.\n", loop
->num
);
2652 unsigned_type
= unsigned_type_for (type
);
2653 base
= fold_convert (unsigned_type
, base
);
2654 step
= fold_convert (unsigned_type
, step
);
2656 if (tree_int_cst_sign_bit (step
))
2658 extreme
= fold_convert (unsigned_type
, low
);
2659 if (TREE_CODE (base
) != INTEGER_CST
)
2660 base
= fold_convert (unsigned_type
, high
);
2661 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
2662 step
= fold_build1 (NEGATE_EXPR
, unsigned_type
, step
);
2666 extreme
= fold_convert (unsigned_type
, high
);
2667 if (TREE_CODE (base
) != INTEGER_CST
)
2668 base
= fold_convert (unsigned_type
, low
);
2669 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
2672 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
2673 would get out of the range. */
2674 niter_bound
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step
);
2675 widest_int max
= derive_constant_upper_bound (niter_bound
);
2676 record_estimate (loop
, niter_bound
, max
, stmt
, false, realistic
, upper
);
2679 /* Determine information about number of iterations a LOOP from the index
2680 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
2681 guaranteed to be executed in every iteration of LOOP. Callback for
2691 idx_infer_loop_bounds (tree base
, tree
*idx
, void *dta
)
2693 struct ilb_data
*data
= (struct ilb_data
*) dta
;
2694 tree ev
, init
, step
;
2695 tree low
, high
, type
, next
;
2696 bool sign
, upper
= true, at_end
= false;
2697 struct loop
*loop
= data
->loop
;
2698 bool reliable
= true;
2700 if (TREE_CODE (base
) != ARRAY_REF
)
2703 /* For arrays at the end of the structure, we are not guaranteed that they
2704 do not really extend over their declared size. However, for arrays of
2705 size greater than one, this is unlikely to be intended. */
2706 if (array_at_struct_end_p (base
))
2712 struct loop
*dloop
= loop_containing_stmt (data
->stmt
);
2716 ev
= analyze_scalar_evolution (dloop
, *idx
);
2717 ev
= instantiate_parameters (loop
, ev
);
2718 init
= initial_condition (ev
);
2719 step
= evolution_part_in_loop_num (ev
, loop
->num
);
2723 || TREE_CODE (step
) != INTEGER_CST
2724 || integer_zerop (step
)
2725 || tree_contains_chrecs (init
, NULL
)
2726 || chrec_contains_symbols_defined_in_loop (init
, loop
->num
))
2729 low
= array_ref_low_bound (base
);
2730 high
= array_ref_up_bound (base
);
2732 /* The case of nonconstant bounds could be handled, but it would be
2734 if (TREE_CODE (low
) != INTEGER_CST
2736 || TREE_CODE (high
) != INTEGER_CST
)
2738 sign
= tree_int_cst_sign_bit (step
);
2739 type
= TREE_TYPE (step
);
2741 /* The array of length 1 at the end of a structure most likely extends
2742 beyond its bounds. */
2744 && operand_equal_p (low
, high
, 0))
2747 /* In case the relevant bound of the array does not fit in type, or
2748 it does, but bound + step (in type) still belongs into the range of the
2749 array, the index may wrap and still stay within the range of the array
2750 (consider e.g. if the array is indexed by the full range of
2753 To make things simpler, we require both bounds to fit into type, although
2754 there are cases where this would not be strictly necessary. */
2755 if (!int_fits_type_p (high
, type
)
2756 || !int_fits_type_p (low
, type
))
2758 low
= fold_convert (type
, low
);
2759 high
= fold_convert (type
, high
);
2762 next
= fold_binary (PLUS_EXPR
, type
, low
, step
);
2764 next
= fold_binary (PLUS_EXPR
, type
, high
, step
);
2766 if (tree_int_cst_compare (low
, next
) <= 0
2767 && tree_int_cst_compare (next
, high
) <= 0)
2770 /* If access is not executed on every iteration, we must ensure that overlow may
2771 not make the access valid later. */
2772 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (data
->stmt
))
2773 && scev_probably_wraps_p (initial_condition_in_loop_num (ev
, loop
->num
),
2774 step
, data
->stmt
, loop
, true))
2777 record_nonwrapping_iv (loop
, init
, step
, data
->stmt
, low
, high
, reliable
, upper
);
2781 /* Determine information about number of iterations a LOOP from the bounds
2782 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
2783 STMT is guaranteed to be executed in every iteration of LOOP.*/
2786 infer_loop_bounds_from_ref (struct loop
*loop
, gimple stmt
, tree ref
)
2788 struct ilb_data data
;
2792 for_each_index (&ref
, idx_infer_loop_bounds
, &data
);
2795 /* Determine information about number of iterations of a LOOP from the way
2796 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
2797 executed in every iteration of LOOP. */
2800 infer_loop_bounds_from_array (struct loop
*loop
, gimple stmt
)
2802 if (is_gimple_assign (stmt
))
2804 tree op0
= gimple_assign_lhs (stmt
);
2805 tree op1
= gimple_assign_rhs1 (stmt
);
2807 /* For each memory access, analyze its access function
2808 and record a bound on the loop iteration domain. */
2809 if (REFERENCE_CLASS_P (op0
))
2810 infer_loop_bounds_from_ref (loop
, stmt
, op0
);
2812 if (REFERENCE_CLASS_P (op1
))
2813 infer_loop_bounds_from_ref (loop
, stmt
, op1
);
2815 else if (is_gimple_call (stmt
))
2818 unsigned i
, n
= gimple_call_num_args (stmt
);
2820 lhs
= gimple_call_lhs (stmt
);
2821 if (lhs
&& REFERENCE_CLASS_P (lhs
))
2822 infer_loop_bounds_from_ref (loop
, stmt
, lhs
);
2824 for (i
= 0; i
< n
; i
++)
2826 arg
= gimple_call_arg (stmt
, i
);
2827 if (REFERENCE_CLASS_P (arg
))
2828 infer_loop_bounds_from_ref (loop
, stmt
, arg
);
2833 /* Determine information about number of iterations of a LOOP from the fact
2834 that pointer arithmetics in STMT does not overflow. */
2837 infer_loop_bounds_from_pointer_arith (struct loop
*loop
, gimple stmt
)
2839 tree def
, base
, step
, scev
, type
, low
, high
;
2842 if (!is_gimple_assign (stmt
)
2843 || gimple_assign_rhs_code (stmt
) != POINTER_PLUS_EXPR
)
2846 def
= gimple_assign_lhs (stmt
);
2847 if (TREE_CODE (def
) != SSA_NAME
)
2850 type
= TREE_TYPE (def
);
2851 if (!nowrap_type_p (type
))
2854 ptr
= gimple_assign_rhs1 (stmt
);
2855 if (!expr_invariant_in_loop_p (loop
, ptr
))
2858 var
= gimple_assign_rhs2 (stmt
);
2859 if (TYPE_PRECISION (type
) != TYPE_PRECISION (TREE_TYPE (var
)))
2862 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
2863 if (chrec_contains_undetermined (scev
))
2866 base
= initial_condition_in_loop_num (scev
, loop
->num
);
2867 step
= evolution_part_in_loop_num (scev
, loop
->num
);
2870 || TREE_CODE (step
) != INTEGER_CST
2871 || tree_contains_chrecs (base
, NULL
)
2872 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
2875 low
= lower_bound_in_type (type
, type
);
2876 high
= upper_bound_in_type (type
, type
);
2878 /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
2879 produce a NULL pointer. The contrary would mean NULL points to an object,
2880 while NULL is supposed to compare unequal with the address of all objects.
2881 Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
2882 NULL pointer since that would mean wrapping, which we assume here not to
2883 happen. So, we can exclude NULL from the valid range of pointer
2885 if (flag_delete_null_pointer_checks
&& int_cst_value (low
) == 0)
2886 low
= build_int_cstu (TREE_TYPE (low
), TYPE_ALIGN_UNIT (TREE_TYPE (type
)));
2888 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
2891 /* Determine information about number of iterations of a LOOP from the fact
2892 that signed arithmetics in STMT does not overflow. */
2895 infer_loop_bounds_from_signedness (struct loop
*loop
, gimple stmt
)
2897 tree def
, base
, step
, scev
, type
, low
, high
;
2899 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2902 def
= gimple_assign_lhs (stmt
);
2904 if (TREE_CODE (def
) != SSA_NAME
)
2907 type
= TREE_TYPE (def
);
2908 if (!INTEGRAL_TYPE_P (type
)
2909 || !TYPE_OVERFLOW_UNDEFINED (type
))
2912 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
2913 if (chrec_contains_undetermined (scev
))
2916 base
= initial_condition_in_loop_num (scev
, loop
->num
);
2917 step
= evolution_part_in_loop_num (scev
, loop
->num
);
2920 || TREE_CODE (step
) != INTEGER_CST
2921 || tree_contains_chrecs (base
, NULL
)
2922 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
2925 low
= lower_bound_in_type (type
, type
);
2926 high
= upper_bound_in_type (type
, type
);
2928 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
2931 /* The following analyzers are extracting informations on the bounds
2932 of LOOP from the following undefined behaviors:
2934 - data references should not access elements over the statically
2937 - signed variables should not overflow when flag_wrapv is not set.
2941 infer_loop_bounds_from_undefined (struct loop
*loop
)
2945 gimple_stmt_iterator bsi
;
2949 bbs
= get_loop_body (loop
);
2951 for (i
= 0; i
< loop
->num_nodes
; i
++)
2955 /* If BB is not executed in each iteration of the loop, we cannot
2956 use the operations in it to infer reliable upper bound on the
2957 # of iterations of the loop. However, we can use it as a guess.
2958 Reliable guesses come only from array bounds. */
2959 reliable
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
);
2961 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2963 gimple stmt
= gsi_stmt (bsi
);
2965 infer_loop_bounds_from_array (loop
, stmt
);
2969 infer_loop_bounds_from_signedness (loop
, stmt
);
2970 infer_loop_bounds_from_pointer_arith (loop
, stmt
);
2979 /* Compare wide ints, callback for qsort. */
2982 wide_int_cmp (const void *p1
, const void *p2
)
2984 const widest_int
*d1
= (const widest_int
*) p1
;
2985 const widest_int
*d2
= (const widest_int
*) p2
;
2986 return wi::cmpu (*d1
, *d2
);
2989 /* Return index of BOUND in BOUNDS array sorted in increasing order.
2990 Lookup by binary search. */
2993 bound_index (vec
<widest_int
> bounds
, const widest_int
&bound
)
2995 unsigned int end
= bounds
.length ();
2996 unsigned int begin
= 0;
2998 /* Find a matching index by means of a binary search. */
2999 while (begin
!= end
)
3001 unsigned int middle
= (begin
+ end
) / 2;
3002 widest_int index
= bounds
[middle
];
3006 else if (wi::ltu_p (index
, bound
))
3014 /* We recorded loop bounds only for statements dominating loop latch (and thus
3015 executed each loop iteration). If there are any bounds on statements not
3016 dominating the loop latch we can improve the estimate by walking the loop
3017 body and seeing if every path from loop header to loop latch contains
3018 some bounded statement. */
3021 discover_iteration_bound_by_body_walk (struct loop
*loop
)
3023 pointer_map_t
*bb_bounds
;
3024 struct nb_iter_bound
*elt
;
3025 vec
<widest_int
> bounds
= vNULL
;
3026 vec
<vec
<basic_block
> > queues
= vNULL
;
3027 vec
<basic_block
> queue
= vNULL
;
3028 ptrdiff_t queue_index
;
3029 ptrdiff_t latch_index
= 0;
3030 pointer_map_t
*block_priority
;
3032 /* Discover what bounds may interest us. */
3033 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3035 widest_int bound
= elt
->bound
;
3037 /* Exit terminates loop at given iteration, while non-exits produce undefined
3038 effect on the next iteration. */
3042 /* If an overflow occurred, ignore the result. */
3047 if (!loop
->any_upper_bound
3048 || wi::ltu_p (bound
, loop
->nb_iterations_upper_bound
))
3049 bounds
.safe_push (bound
);
3052 /* Exit early if there is nothing to do. */
3053 if (!bounds
.exists ())
3056 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3057 fprintf (dump_file
, " Trying to walk loop body to reduce the bound.\n");
3059 /* Sort the bounds in decreasing order. */
3060 qsort (bounds
.address (), bounds
.length (),
3061 sizeof (widest_int
), wide_int_cmp
);
3063 /* For every basic block record the lowest bound that is guaranteed to
3064 terminate the loop. */
3066 bb_bounds
= pointer_map_create ();
3067 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3069 widest_int bound
= elt
->bound
;
3073 /* If an overflow occurred, ignore the result. */
3078 if (!loop
->any_upper_bound
3079 || wi::ltu_p (bound
, loop
->nb_iterations_upper_bound
))
3081 ptrdiff_t index
= bound_index (bounds
, bound
);
3082 void **entry
= pointer_map_contains (bb_bounds
,
3083 gimple_bb (elt
->stmt
));
3085 *pointer_map_insert (bb_bounds
,
3086 gimple_bb (elt
->stmt
)) = (void *)index
;
3087 else if ((ptrdiff_t)*entry
> index
)
3088 *entry
= (void *)index
;
3092 block_priority
= pointer_map_create ();
3094 /* Perform shortest path discovery loop->header ... loop->latch.
3096 The "distance" is given by the smallest loop bound of basic block
3097 present in the path and we look for path with largest smallest bound
3100 To avoid the need for fibonacci heap on double ints we simply compress
3101 double ints into indexes to BOUNDS array and then represent the queue
3102 as arrays of queues for every index.
3103 Index of BOUNDS.length() means that the execution of given BB has
3104 no bounds determined.
3106 VISITED is a pointer map translating basic block into smallest index
3107 it was inserted into the priority queue with. */
3110 /* Start walk in loop header with index set to infinite bound. */
3111 queue_index
= bounds
.length ();
3112 queues
.safe_grow_cleared (queue_index
+ 1);
3113 queue
.safe_push (loop
->header
);
3114 queues
[queue_index
] = queue
;
3115 *pointer_map_insert (block_priority
, loop
->header
) = (void *)queue_index
;
3117 for (; queue_index
>= 0; queue_index
--)
3119 if (latch_index
< queue_index
)
3121 while (queues
[queue_index
].length ())
3124 ptrdiff_t bound_index
= queue_index
;
3129 queue
= queues
[queue_index
];
3132 /* OK, we later inserted the BB with lower priority, skip it. */
3133 if ((ptrdiff_t)*pointer_map_contains (block_priority
, bb
) > queue_index
)
3136 /* See if we can improve the bound. */
3137 entry
= pointer_map_contains (bb_bounds
, bb
);
3138 if (entry
&& (ptrdiff_t)*entry
< bound_index
)
3139 bound_index
= (ptrdiff_t)*entry
;
3141 /* Insert succesors into the queue, watch for latch edge
3142 and record greatest index we saw. */
3143 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3145 bool insert
= false;
3148 if (loop_exit_edge_p (loop
, e
))
3151 if (e
== loop_latch_edge (loop
)
3152 && latch_index
< bound_index
)
3153 latch_index
= bound_index
;
3154 else if (!(entry
= pointer_map_contains (block_priority
, e
->dest
)))
3157 *pointer_map_insert (block_priority
, e
->dest
) = (void *)bound_index
;
3159 else if ((ptrdiff_t)*entry
< bound_index
)
3162 *entry
= (void *)bound_index
;
3166 queues
[bound_index
].safe_push (e
->dest
);
3170 queues
[queue_index
].release ();
3173 gcc_assert (latch_index
>= 0);
3174 if ((unsigned)latch_index
< bounds
.length ())
3176 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3178 fprintf (dump_file
, "Found better loop bound ");
3179 print_decu (bounds
[latch_index
], dump_file
);
3180 fprintf (dump_file
, "\n");
3182 record_niter_bound (loop
, bounds
[latch_index
], false, true);
3187 pointer_map_destroy (bb_bounds
);
3188 pointer_map_destroy (block_priority
);
3191 /* See if every path cross the loop goes through a statement that is known
3192 to not execute at the last iteration. In that case we can decrese iteration
3196 maybe_lower_iteration_bound (struct loop
*loop
)
3198 pointer_set_t
*not_executed_last_iteration
= NULL
;
3199 struct nb_iter_bound
*elt
;
3200 bool found_exit
= false;
3201 vec
<basic_block
> queue
= vNULL
;
3204 /* Collect all statements with interesting (i.e. lower than
3205 nb_iterations_upper_bound) bound on them.
3207 TODO: Due to the way record_estimate choose estimates to store, the bounds
3208 will be always nb_iterations_upper_bound-1. We can change this to record
3209 also statements not dominating the loop latch and update the walk bellow
3210 to the shortest path algorthm. */
3211 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3214 && wi::ltu_p (elt
->bound
, loop
->nb_iterations_upper_bound
))
3216 if (!not_executed_last_iteration
)
3217 not_executed_last_iteration
= pointer_set_create ();
3218 pointer_set_insert (not_executed_last_iteration
, elt
->stmt
);
3221 if (!not_executed_last_iteration
)
3224 /* Start DFS walk in the loop header and see if we can reach the
3225 loop latch or any of the exits (including statements with side
3226 effects that may terminate the loop otherwise) without visiting
3227 any of the statements known to have undefined effect on the last
3229 queue
.safe_push (loop
->header
);
3230 visited
= BITMAP_ALLOC (NULL
);
3231 bitmap_set_bit (visited
, loop
->header
->index
);
3236 basic_block bb
= queue
.pop ();
3237 gimple_stmt_iterator gsi
;
3238 bool stmt_found
= false;
3240 /* Loop for possible exits and statements bounding the execution. */
3241 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3243 gimple stmt
= gsi_stmt (gsi
);
3244 if (pointer_set_contains (not_executed_last_iteration
, stmt
))
3249 if (gimple_has_side_effects (stmt
))
3258 /* If no bounding statement is found, continue the walk. */
3264 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3266 if (loop_exit_edge_p (loop
, e
)
3267 || e
== loop_latch_edge (loop
))
3272 if (bitmap_set_bit (visited
, e
->dest
->index
))
3273 queue
.safe_push (e
->dest
);
3277 while (queue
.length () && !found_exit
);
3279 /* If every path through the loop reach bounding statement before exit,
3280 then we know the last iteration of the loop will have undefined effect
3281 and we can decrease number of iterations. */
3285 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3286 fprintf (dump_file
, "Reducing loop iteration estimate by 1; "
3287 "undefined statement must be executed at the last iteration.\n");
3288 record_niter_bound (loop
, loop
->nb_iterations_upper_bound
- 1,
3291 BITMAP_FREE (visited
);
3293 pointer_set_destroy (not_executed_last_iteration
);
3296 /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
3297 is true also use estimates derived from undefined behavior. */
3300 estimate_numbers_of_iterations_loop (struct loop
*loop
)
3305 struct tree_niter_desc niter_desc
;
3310 /* Give up if we already have tried to compute an estimation. */
3311 if (loop
->estimate_state
!= EST_NOT_COMPUTED
)
3314 loop
->estimate_state
= EST_AVAILABLE
;
3315 /* Force estimate compuation but leave any existing upper bound in place. */
3316 loop
->any_estimate
= false;
3318 /* Ensure that loop->nb_iterations is computed if possible. If it turns out
3319 to be constant, we avoid undefined behavior implied bounds and instead
3320 diagnose those loops with -Waggressive-loop-optimizations. */
3321 number_of_latch_executions (loop
);
3323 exits
= get_loop_exit_edges (loop
);
3324 likely_exit
= single_likely_exit (loop
);
3325 FOR_EACH_VEC_ELT (exits
, i
, ex
)
3327 if (!number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
3330 niter
= niter_desc
.niter
;
3331 type
= TREE_TYPE (niter
);
3332 if (TREE_CODE (niter_desc
.may_be_zero
) != INTEGER_CST
)
3333 niter
= build3 (COND_EXPR
, type
, niter_desc
.may_be_zero
,
3334 build_int_cst (type
, 0),
3336 record_estimate (loop
, niter
, niter_desc
.max
,
3337 last_stmt (ex
->src
),
3338 true, ex
== likely_exit
, true);
3342 if (flag_aggressive_loop_optimizations
)
3343 infer_loop_bounds_from_undefined (loop
);
3345 discover_iteration_bound_by_body_walk (loop
);
3347 maybe_lower_iteration_bound (loop
);
3349 /* If we have a measured profile, use it to estimate the number of
3351 if (loop
->header
->count
!= 0)
3353 gcov_type nit
= expected_loop_iterations_unbounded (loop
) + 1;
3354 bound
= gcov_type_to_wide_int (nit
);
3355 record_niter_bound (loop
, bound
, true, false);
3358 /* If we know the exact number of iterations of this loop, try to
3359 not break code with undefined behavior by not recording smaller
3360 maximum number of iterations. */
3361 if (loop
->nb_iterations
3362 && TREE_CODE (loop
->nb_iterations
) == INTEGER_CST
)
3364 loop
->any_upper_bound
= true;
3365 loop
->nb_iterations_upper_bound
= wi::to_widest (loop
->nb_iterations
);
3369 /* Sets NIT to the estimated number of executions of the latch of the
3370 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
3371 large as the number of iterations. If we have no reliable estimate,
3372 the function returns false, otherwise returns true. */
3375 estimated_loop_iterations (struct loop
*loop
, widest_int
*nit
)
3377 /* When SCEV information is available, try to update loop iterations
3378 estimate. Otherwise just return whatever we recorded earlier. */
3379 if (scev_initialized_p ())
3380 estimate_numbers_of_iterations_loop (loop
);
3382 return (get_estimated_loop_iterations (loop
, nit
));
3385 /* Similar to estimated_loop_iterations, but returns the estimate only
3386 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3387 on the number of iterations of LOOP could not be derived, returns -1. */
3390 estimated_loop_iterations_int (struct loop
*loop
)
3393 HOST_WIDE_INT hwi_nit
;
3395 if (!estimated_loop_iterations (loop
, &nit
))
3398 if (!wi::fits_shwi_p (nit
))
3400 hwi_nit
= nit
.to_shwi ();
3402 return hwi_nit
< 0 ? -1 : hwi_nit
;
3406 /* Sets NIT to an upper bound for the maximum number of executions of the
3407 latch of the LOOP. If we have no reliable estimate, the function returns
3408 false, otherwise returns true. */
3411 max_loop_iterations (struct loop
*loop
, widest_int
*nit
)
3413 /* When SCEV information is available, try to update loop iterations
3414 estimate. Otherwise just return whatever we recorded earlier. */
3415 if (scev_initialized_p ())
3416 estimate_numbers_of_iterations_loop (loop
);
3418 return get_max_loop_iterations (loop
, nit
);
3421 /* Similar to max_loop_iterations, but returns the estimate only
3422 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3423 on the number of iterations of LOOP could not be derived, returns -1. */
3426 max_loop_iterations_int (struct loop
*loop
)
3429 HOST_WIDE_INT hwi_nit
;
3431 if (!max_loop_iterations (loop
, &nit
))
3434 if (!wi::fits_shwi_p (nit
))
3436 hwi_nit
= nit
.to_shwi ();
3438 return hwi_nit
< 0 ? -1 : hwi_nit
;
3441 /* Returns an estimate for the number of executions of statements
3442 in the LOOP. For statements before the loop exit, this exceeds
3443 the number of execution of the latch by one. */
3446 estimated_stmt_executions_int (struct loop
*loop
)
3448 HOST_WIDE_INT nit
= estimated_loop_iterations_int (loop
);
3454 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
3456 /* If the computation overflows, return -1. */
3457 return snit
< 0 ? -1 : snit
;
3460 /* Sets NIT to the estimated maximum number of executions of the latch of the
3461 LOOP, plus one. If we have no reliable estimate, the function returns
3462 false, otherwise returns true. */
3465 max_stmt_executions (struct loop
*loop
, widest_int
*nit
)
3467 widest_int nit_minus_one
;
3469 if (!max_loop_iterations (loop
, nit
))
3472 nit_minus_one
= *nit
;
3476 return wi::gtu_p (*nit
, nit_minus_one
);
3479 /* Sets NIT to the estimated number of executions of the latch of the
3480 LOOP, plus one. If we have no reliable estimate, the function returns
3481 false, otherwise returns true. */
3484 estimated_stmt_executions (struct loop
*loop
, widest_int
*nit
)
3486 widest_int nit_minus_one
;
3488 if (!estimated_loop_iterations (loop
, nit
))
3491 nit_minus_one
= *nit
;
3495 return wi::gtu_p (*nit
, nit_minus_one
);
3498 /* Records estimates on numbers of iterations of loops. */
3501 estimate_numbers_of_iterations (void)
3506 /* We don't want to issue signed overflow warnings while getting
3507 loop iteration estimates. */
3508 fold_defer_overflow_warnings ();
3510 FOR_EACH_LOOP (li
, loop
, 0)
3512 estimate_numbers_of_iterations_loop (loop
);
3515 fold_undefer_and_ignore_overflow_warnings ();
3518 /* Returns true if statement S1 dominates statement S2. */
3521 stmt_dominates_stmt_p (gimple s1
, gimple s2
)
3523 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
3531 gimple_stmt_iterator bsi
;
3533 if (gimple_code (s2
) == GIMPLE_PHI
)
3536 if (gimple_code (s1
) == GIMPLE_PHI
)
3539 for (bsi
= gsi_start_bb (bb1
); gsi_stmt (bsi
) != s2
; gsi_next (&bsi
))
3540 if (gsi_stmt (bsi
) == s1
)
3546 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
3549 /* Returns true when we can prove that the number of executions of
3550 STMT in the loop is at most NITER, according to the bound on
3551 the number of executions of the statement NITER_BOUND->stmt recorded in
3552 NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT.
3554 ??? This code can become quite a CPU hog - we can have many bounds,
3555 and large basic block forcing stmt_dominates_stmt_p to be queried
3556 many times on a large basic blocks, so the whole thing is O(n^2)
3557 for scev_probably_wraps_p invocation (that can be done n times).
3559 It would make more sense (and give better answers) to remember BB
3560 bounds computed by discover_iteration_bound_by_body_walk. */
3563 n_of_executions_at_most (gimple stmt
,
3564 struct nb_iter_bound
*niter_bound
,
3567 widest_int bound
= niter_bound
->bound
;
3568 tree nit_type
= TREE_TYPE (niter
), e
;
3571 gcc_assert (TYPE_UNSIGNED (nit_type
));
3573 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
3574 the number of iterations is small. */
3575 if (!wi::fits_to_tree_p (bound
, nit_type
))
3578 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3579 times. This means that:
3581 -- if NITER_BOUND->is_exit is true, then everything after
3582 it at most NITER_BOUND->bound times.
3584 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
3585 is executed, then NITER_BOUND->stmt is executed as well in the same
3586 iteration then STMT is executed at most NITER_BOUND->bound + 1 times.
3588 If we can determine that NITER_BOUND->stmt is always executed
3589 after STMT, then STMT is executed at most NITER_BOUND->bound + 2 times.
3590 We conclude that if both statements belong to the same
3591 basic block and STMT is before NITER_BOUND->stmt and there are no
3592 statements with side effects in between. */
3594 if (niter_bound
->is_exit
)
3596 if (stmt
== niter_bound
->stmt
3597 || !stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
3603 if (!stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
3605 gimple_stmt_iterator bsi
;
3606 if (gimple_bb (stmt
) != gimple_bb (niter_bound
->stmt
)
3607 || gimple_code (stmt
) == GIMPLE_PHI
3608 || gimple_code (niter_bound
->stmt
) == GIMPLE_PHI
)
3611 /* By stmt_dominates_stmt_p we already know that STMT appears
3612 before NITER_BOUND->STMT. Still need to test that the loop
3613 can not be terinated by a side effect in between. */
3614 for (bsi
= gsi_for_stmt (stmt
); gsi_stmt (bsi
) != niter_bound
->stmt
;
3616 if (gimple_has_side_effects (gsi_stmt (bsi
)))
3620 || !wi::fits_to_tree_p (bound
, nit_type
))
3626 e
= fold_binary (cmp
, boolean_type_node
,
3627 niter
, wide_int_to_tree (nit_type
, bound
));
3628 return e
&& integer_nonzerop (e
);
3631 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
3634 nowrap_type_p (tree type
)
3636 if (INTEGRAL_TYPE_P (type
)
3637 && TYPE_OVERFLOW_UNDEFINED (type
))
3640 if (POINTER_TYPE_P (type
))
3646 /* Return false only when the induction variable BASE + STEP * I is
3647 known to not overflow: i.e. when the number of iterations is small
3648 enough with respect to the step and initial condition in order to
3649 keep the evolution confined in TYPEs bounds. Return true when the
3650 iv is known to overflow or when the property is not computable.
3652 USE_OVERFLOW_SEMANTICS is true if this function should assume that
3653 the rules for overflow of the given language apply (e.g., that signed
3654 arithmetics in C does not overflow). */
3657 scev_probably_wraps_p (tree base
, tree step
,
3658 gimple at_stmt
, struct loop
*loop
,
3659 bool use_overflow_semantics
)
3661 tree delta
, step_abs
;
3662 tree unsigned_type
, valid_niter
;
3663 tree type
= TREE_TYPE (step
);
3666 struct nb_iter_bound
*bound
;
3668 /* FIXME: We really need something like
3669 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
3671 We used to test for the following situation that frequently appears
3672 during address arithmetics:
3674 D.1621_13 = (long unsigned intD.4) D.1620_12;
3675 D.1622_14 = D.1621_13 * 8;
3676 D.1623_15 = (doubleD.29 *) D.1622_14;
3678 And derived that the sequence corresponding to D_14
3679 can be proved to not wrap because it is used for computing a
3680 memory access; however, this is not really the case -- for example,
3681 if D_12 = (unsigned char) [254,+,1], then D_14 has values
3682 2032, 2040, 0, 8, ..., but the code is still legal. */
3684 if (chrec_contains_undetermined (base
)
3685 || chrec_contains_undetermined (step
))
3688 if (integer_zerop (step
))
3691 /* If we can use the fact that signed and pointer arithmetics does not
3692 wrap, we are done. */
3693 if (use_overflow_semantics
&& nowrap_type_p (TREE_TYPE (base
)))
3696 /* To be able to use estimates on number of iterations of the loop,
3697 we must have an upper bound on the absolute value of the step. */
3698 if (TREE_CODE (step
) != INTEGER_CST
)
3701 /* Don't issue signed overflow warnings. */
3702 fold_defer_overflow_warnings ();
3704 /* Otherwise, compute the number of iterations before we reach the
3705 bound of the type, and verify that the loop is exited before this
3707 unsigned_type
= unsigned_type_for (type
);
3708 base
= fold_convert (unsigned_type
, base
);
3710 if (tree_int_cst_sign_bit (step
))
3712 tree extreme
= fold_convert (unsigned_type
,
3713 lower_bound_in_type (type
, type
));
3714 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
3715 step_abs
= fold_build1 (NEGATE_EXPR
, unsigned_type
,
3716 fold_convert (unsigned_type
, step
));
3720 tree extreme
= fold_convert (unsigned_type
,
3721 upper_bound_in_type (type
, type
));
3722 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
3723 step_abs
= fold_convert (unsigned_type
, step
);
3726 valid_niter
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step_abs
);
3728 estimate_numbers_of_iterations_loop (loop
);
3730 if (max_loop_iterations (loop
, &niter
)
3731 && wi::fits_to_tree_p (niter
, TREE_TYPE (valid_niter
))
3732 && (e
= fold_binary (GT_EXPR
, boolean_type_node
, valid_niter
,
3733 wide_int_to_tree (TREE_TYPE (valid_niter
),
3735 && integer_nonzerop (e
))
3737 fold_undefer_and_ignore_overflow_warnings ();
3741 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
3743 if (n_of_executions_at_most (at_stmt
, bound
, valid_niter
))
3745 fold_undefer_and_ignore_overflow_warnings ();
3750 fold_undefer_and_ignore_overflow_warnings ();
3752 /* At this point we still don't have a proof that the iv does not
3753 overflow: give up. */
3757 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
3760 free_numbers_of_iterations_estimates_loop (struct loop
*loop
)
3762 struct nb_iter_bound
*bound
, *next
;
3764 loop
->nb_iterations
= NULL
;
3765 loop
->estimate_state
= EST_NOT_COMPUTED
;
3766 for (bound
= loop
->bounds
; bound
; bound
= next
)
3772 loop
->bounds
= NULL
;
3775 /* Frees the information on upper bounds on numbers of iterations of loops. */
3778 free_numbers_of_iterations_estimates (void)
3783 FOR_EACH_LOOP (li
, loop
, 0)
3785 free_numbers_of_iterations_estimates_loop (loop
);
3789 /* Substitute value VAL for ssa name NAME inside expressions held
3793 substitute_in_loop_info (struct loop
*loop
, tree name
, tree val
)
3795 loop
->nb_iterations
= simplify_replace_tree (loop
->nb_iterations
, name
, val
);