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"
33 #include "tree-chrec.h"
34 #include "tree-scalar-evolution.h"
35 #include "tree-data-ref.h"
38 #include "diagnostic-core.h"
39 #include "tree-inline.h"
40 #include "tree-pass.h"
41 #include "wide-int-print.h"
44 #define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
46 /* The maximum number of dominator BBs we search for conditions
47 of loop header copies we use for simplifying a conditional
49 #define MAX_DOMINATORS_TO_WALK 8
53 Analysis of number of iterations of an affine exit test.
57 /* Bounds on some value, BELOW <= X <= UP. */
65 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */
68 split_to_var_and_offset (tree expr
, tree
*var
, mpz_t offset
)
70 tree type
= TREE_TYPE (expr
);
75 mpz_set_ui (offset
, 0);
77 switch (TREE_CODE (expr
))
84 case POINTER_PLUS_EXPR
:
85 op0
= TREE_OPERAND (expr
, 0);
86 op1
= TREE_OPERAND (expr
, 1);
88 if (TREE_CODE (op1
) != INTEGER_CST
)
92 /* Always sign extend the offset. */
93 wi::to_mpz (op1
, offset
, SIGNED
);
95 mpz_neg (offset
, offset
);
99 *var
= build_int_cst_type (type
, 0);
100 wi::to_mpz (expr
, offset
, TYPE_SIGN (type
));
108 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
109 in TYPE to MIN and MAX. */
112 determine_value_range (tree type
, tree var
, mpz_t off
,
113 mpz_t min
, mpz_t max
)
115 /* If the expression is a constant, we know its value exactly. */
116 if (integer_zerop (var
))
123 /* If the computation may wrap, we know nothing about the value, except for
124 the range of the type. */
125 get_type_static_bounds (type
, min
, max
);
126 if (!nowrap_type_p (type
))
129 /* Since the addition of OFF does not wrap, if OFF is positive, then we may
130 add it to MIN, otherwise to MAX. */
131 if (mpz_sgn (off
) < 0)
132 mpz_add (max
, max
, off
);
134 mpz_add (min
, min
, off
);
137 /* Stores the bounds on the difference of the values of the expressions
138 (var + X) and (var + Y), computed in TYPE, to BNDS. */
141 bound_difference_of_offsetted_base (tree type
, mpz_t x
, mpz_t y
,
144 int rel
= mpz_cmp (x
, y
);
145 bool may_wrap
= !nowrap_type_p (type
);
148 /* If X == Y, then the expressions are always equal.
149 If X > Y, there are the following possibilities:
150 a) neither of var + X and var + Y overflow or underflow, or both of
151 them do. Then their difference is X - Y.
152 b) var + X overflows, and var + Y does not. Then the values of the
153 expressions are var + X - M and var + Y, where M is the range of
154 the type, and their difference is X - Y - M.
155 c) var + Y underflows and var + X does not. Their difference again
157 Therefore, if the arithmetics in type does not overflow, then the
158 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
159 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
160 (X - Y, X - Y + M). */
164 mpz_set_ui (bnds
->below
, 0);
165 mpz_set_ui (bnds
->up
, 0);
170 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), m
, UNSIGNED
);
171 mpz_add_ui (m
, m
, 1);
172 mpz_sub (bnds
->up
, x
, y
);
173 mpz_set (bnds
->below
, bnds
->up
);
178 mpz_sub (bnds
->below
, bnds
->below
, m
);
180 mpz_add (bnds
->up
, bnds
->up
, m
);
186 /* From condition C0 CMP C1 derives information regarding the
187 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
188 and stores it to BNDS. */
191 refine_bounds_using_guard (tree type
, tree varx
, mpz_t offx
,
192 tree vary
, mpz_t offy
,
193 tree c0
, enum tree_code cmp
, tree c1
,
196 tree varc0
, varc1
, tmp
, ctype
;
197 mpz_t offc0
, offc1
, loffx
, loffy
, bnd
;
199 bool no_wrap
= nowrap_type_p (type
);
208 STRIP_SIGN_NOPS (c0
);
209 STRIP_SIGN_NOPS (c1
);
210 ctype
= TREE_TYPE (c0
);
211 if (!useless_type_conversion_p (ctype
, type
))
217 /* We could derive quite precise information from EQ_EXPR, however, such
218 a guard is unlikely to appear, so we do not bother with handling
223 /* NE_EXPR comparisons do not contain much of useful information, except for
224 special case of comparing with the bounds of the type. */
225 if (TREE_CODE (c1
) != INTEGER_CST
226 || !INTEGRAL_TYPE_P (type
))
229 /* Ensure that the condition speaks about an expression in the same type
231 ctype
= TREE_TYPE (c0
);
232 if (TYPE_PRECISION (ctype
) != TYPE_PRECISION (type
))
234 c0
= fold_convert (type
, c0
);
235 c1
= fold_convert (type
, c1
);
237 if (TYPE_MIN_VALUE (type
)
238 && operand_equal_p (c1
, TYPE_MIN_VALUE (type
), 0))
243 if (TYPE_MAX_VALUE (type
)
244 && operand_equal_p (c1
, TYPE_MAX_VALUE (type
), 0))
257 split_to_var_and_offset (expand_simple_operations (c0
), &varc0
, offc0
);
258 split_to_var_and_offset (expand_simple_operations (c1
), &varc1
, offc1
);
260 /* We are only interested in comparisons of expressions based on VARX and
261 VARY. TODO -- we might also be able to derive some bounds from
262 expressions containing just one of the variables. */
264 if (operand_equal_p (varx
, varc1
, 0))
266 tmp
= varc0
; varc0
= varc1
; varc1
= tmp
;
267 mpz_swap (offc0
, offc1
);
268 cmp
= swap_tree_comparison (cmp
);
271 if (!operand_equal_p (varx
, varc0
, 0)
272 || !operand_equal_p (vary
, varc1
, 0))
275 mpz_init_set (loffx
, offx
);
276 mpz_init_set (loffy
, offy
);
278 if (cmp
== GT_EXPR
|| cmp
== GE_EXPR
)
280 tmp
= varx
; varx
= vary
; vary
= tmp
;
281 mpz_swap (offc0
, offc1
);
282 mpz_swap (loffx
, loffy
);
283 cmp
= swap_tree_comparison (cmp
);
287 /* If there is no overflow, the condition implies that
289 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
291 The overflows and underflows may complicate things a bit; each
292 overflow decreases the appropriate offset by M, and underflow
293 increases it by M. The above inequality would not necessarily be
296 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
297 VARX + OFFC0 overflows, but VARX + OFFX does not.
298 This may only happen if OFFX < OFFC0.
299 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
300 VARY + OFFC1 underflows and VARY + OFFY does not.
301 This may only happen if OFFY > OFFC1. */
310 x_ok
= (integer_zerop (varx
)
311 || mpz_cmp (loffx
, offc0
) >= 0);
312 y_ok
= (integer_zerop (vary
)
313 || mpz_cmp (loffy
, offc1
) <= 0);
319 mpz_sub (bnd
, loffx
, loffy
);
320 mpz_add (bnd
, bnd
, offc1
);
321 mpz_sub (bnd
, bnd
, offc0
);
324 mpz_sub_ui (bnd
, bnd
, 1);
329 if (mpz_cmp (bnds
->below
, bnd
) < 0)
330 mpz_set (bnds
->below
, bnd
);
334 if (mpz_cmp (bnd
, bnds
->up
) < 0)
335 mpz_set (bnds
->up
, bnd
);
347 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
348 The subtraction is considered to be performed in arbitrary precision,
351 We do not attempt to be too clever regarding the value ranges of X and
352 Y; most of the time, they are just integers or ssa names offsetted by
353 integer. However, we try to use the information contained in the
354 comparisons before the loop (usually created by loop header copying). */
357 bound_difference (struct loop
*loop
, tree x
, tree y
, bounds
*bnds
)
359 tree type
= TREE_TYPE (x
);
362 mpz_t minx
, maxx
, miny
, maxy
;
370 /* Get rid of unnecessary casts, but preserve the value of
375 mpz_init (bnds
->below
);
379 split_to_var_and_offset (x
, &varx
, offx
);
380 split_to_var_and_offset (y
, &vary
, offy
);
382 if (!integer_zerop (varx
)
383 && operand_equal_p (varx
, vary
, 0))
385 /* Special case VARX == VARY -- we just need to compare the
386 offsets. The matters are a bit more complicated in the
387 case addition of offsets may wrap. */
388 bound_difference_of_offsetted_base (type
, offx
, offy
, bnds
);
392 /* Otherwise, use the value ranges to determine the initial
393 estimates on below and up. */
398 determine_value_range (type
, varx
, offx
, minx
, maxx
);
399 determine_value_range (type
, vary
, offy
, miny
, maxy
);
401 mpz_sub (bnds
->below
, minx
, maxy
);
402 mpz_sub (bnds
->up
, maxx
, miny
);
409 /* If both X and Y are constants, we cannot get any more precise. */
410 if (integer_zerop (varx
) && integer_zerop (vary
))
413 /* Now walk the dominators of the loop header and use the entry
414 guards to refine the estimates. */
415 for (bb
= loop
->header
;
416 bb
!= ENTRY_BLOCK_PTR
&& cnt
< MAX_DOMINATORS_TO_WALK
;
417 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
419 if (!single_pred_p (bb
))
421 e
= single_pred_edge (bb
);
423 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
426 cond
= last_stmt (e
->src
);
427 c0
= gimple_cond_lhs (cond
);
428 cmp
= gimple_cond_code (cond
);
429 c1
= gimple_cond_rhs (cond
);
431 if (e
->flags
& EDGE_FALSE_VALUE
)
432 cmp
= invert_tree_comparison (cmp
, false);
434 refine_bounds_using_guard (type
, varx
, offx
, vary
, offy
,
444 /* Update the bounds in BNDS that restrict the value of X to the bounds
445 that restrict the value of X + DELTA. X can be obtained as a
446 difference of two values in TYPE. */
449 bounds_add (bounds
*bnds
, widest_int delta
, tree type
)
454 wi::to_mpz (delta
, mdelta
, SIGNED
);
457 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), max
, UNSIGNED
);
459 mpz_add (bnds
->up
, bnds
->up
, mdelta
);
460 mpz_add (bnds
->below
, bnds
->below
, mdelta
);
462 if (mpz_cmp (bnds
->up
, max
) > 0)
463 mpz_set (bnds
->up
, max
);
466 if (mpz_cmp (bnds
->below
, max
) < 0)
467 mpz_set (bnds
->below
, max
);
473 /* Update the bounds in BNDS that restrict the value of X to the bounds
474 that restrict the value of -X. */
477 bounds_negate (bounds
*bnds
)
481 mpz_init_set (tmp
, bnds
->up
);
482 mpz_neg (bnds
->up
, bnds
->below
);
483 mpz_neg (bnds
->below
, tmp
);
487 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
490 inverse (tree x
, tree mask
)
492 tree type
= TREE_TYPE (x
);
494 unsigned ctr
= tree_floor_log2 (mask
);
496 if (TYPE_PRECISION (type
) <= HOST_BITS_PER_WIDE_INT
)
498 unsigned HOST_WIDE_INT ix
;
499 unsigned HOST_WIDE_INT imask
;
500 unsigned HOST_WIDE_INT irslt
= 1;
502 gcc_assert (cst_fits_shwi_p (x
));
503 gcc_assert (cst_fits_shwi_p (mask
));
505 ix
= int_cst_value (x
);
506 imask
= int_cst_value (mask
);
515 rslt
= build_int_cst_type (type
, irslt
);
519 rslt
= build_int_cst (type
, 1);
522 rslt
= int_const_binop (MULT_EXPR
, rslt
, x
);
523 x
= int_const_binop (MULT_EXPR
, x
, x
);
525 rslt
= int_const_binop (BIT_AND_EXPR
, rslt
, mask
);
531 /* Derives the upper bound BND on the number of executions of loop with exit
532 condition S * i <> C. If NO_OVERFLOW is true, then the control variable of
533 the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed
534 that the loop ends through this exit, i.e., the induction variable ever
535 reaches the value of C.
537 The value C is equal to final - base, where final and base are the final and
538 initial value of the actual induction variable in the analysed loop. BNDS
539 bounds the value of this difference when computed in signed type with
540 unbounded range, while the computation of C is performed in an unsigned
541 type with the range matching the range of the type of the induction variable.
542 In particular, BNDS.up contains an upper bound on C in the following cases:
543 -- if the iv must reach its final value without overflow, i.e., if
544 NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
545 -- if final >= base, which we know to hold when BNDS.below >= 0. */
548 number_of_iterations_ne_max (mpz_t bnd
, bool no_overflow
, tree c
, tree s
,
549 bounds
*bnds
, bool exit_must_be_taken
)
553 tree type
= TREE_TYPE (c
);
554 bool bnds_u_valid
= ((no_overflow
&& exit_must_be_taken
)
555 || mpz_sgn (bnds
->below
) >= 0);
558 || (TREE_CODE (c
) == INTEGER_CST
559 && TREE_CODE (s
) == INTEGER_CST
560 && wi::mod_trunc (c
, s
, TYPE_SIGN (type
)) == 0)
561 || (TYPE_OVERFLOW_UNDEFINED (type
)
562 && multiple_of_p (type
, c
, s
)))
564 /* If C is an exact multiple of S, then its value will be reached before
565 the induction variable overflows (unless the loop is exited in some
566 other way before). Note that the actual induction variable in the
567 loop (which ranges from base to final instead of from 0 to C) may
568 overflow, in which case BNDS.up will not be giving a correct upper
569 bound on C; thus, BNDS_U_VALID had to be computed in advance. */
571 exit_must_be_taken
= true;
574 /* If the induction variable can overflow, the number of iterations is at
575 most the period of the control variable (or infinite, but in that case
576 the whole # of iterations analysis will fail). */
579 max
= wi::mask
<widest_int
> (TYPE_PRECISION (type
) - wi::ctz (s
), false);
580 wi::to_mpz (max
, bnd
, UNSIGNED
);
584 /* Now we know that the induction variable does not overflow, so the loop
585 iterates at most (range of type / S) times. */
586 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), bnd
, UNSIGNED
);
588 /* If the induction variable is guaranteed to reach the value of C before
590 if (exit_must_be_taken
)
592 /* ... then we can strengthen this to C / S, and possibly we can use
593 the upper bound on C given by BNDS. */
594 if (TREE_CODE (c
) == INTEGER_CST
)
595 wi::to_mpz (c
, bnd
, UNSIGNED
);
596 else if (bnds_u_valid
)
597 mpz_set (bnd
, bnds
->up
);
601 wi::to_mpz (s
, d
, UNSIGNED
);
602 mpz_fdiv_q (bnd
, bnd
, d
);
606 /* Determines number of iterations of loop whose ending condition
607 is IV <> FINAL. TYPE is the type of the iv. The number of
608 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
609 we know that the exit must be taken eventually, i.e., that the IV
610 ever reaches the value FINAL (we derived this earlier, and possibly set
611 NITER->assumptions to make sure this is the case). BNDS contains the
612 bounds on the difference FINAL - IV->base. */
615 number_of_iterations_ne (tree type
, affine_iv
*iv
, tree final
,
616 struct tree_niter_desc
*niter
, bool exit_must_be_taken
,
619 tree niter_type
= unsigned_type_for (type
);
620 tree s
, c
, d
, bits
, assumption
, tmp
, bound
;
623 niter
->control
= *iv
;
624 niter
->bound
= final
;
625 niter
->cmp
= NE_EXPR
;
627 /* Rearrange the terms so that we get inequality S * i <> C, with S
628 positive. Also cast everything to the unsigned type. If IV does
629 not overflow, BNDS bounds the value of C. Also, this is the
630 case if the computation |FINAL - IV->base| does not overflow, i.e.,
631 if BNDS->below in the result is nonnegative. */
632 if (tree_int_cst_sign_bit (iv
->step
))
634 s
= fold_convert (niter_type
,
635 fold_build1 (NEGATE_EXPR
, type
, iv
->step
));
636 c
= fold_build2 (MINUS_EXPR
, niter_type
,
637 fold_convert (niter_type
, iv
->base
),
638 fold_convert (niter_type
, final
));
639 bounds_negate (bnds
);
643 s
= fold_convert (niter_type
, iv
->step
);
644 c
= fold_build2 (MINUS_EXPR
, niter_type
,
645 fold_convert (niter_type
, final
),
646 fold_convert (niter_type
, iv
->base
));
650 number_of_iterations_ne_max (max
, iv
->no_overflow
, c
, s
, bnds
,
652 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, max
, false),
653 TYPE_SIGN (niter_type
));
656 /* First the trivial cases -- when the step is 1. */
657 if (integer_onep (s
))
663 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
664 is infinite. Otherwise, the number of iterations is
665 (inverse(s/d) * (c/d)) mod (size of mode/d). */
666 bits
= num_ending_zeros (s
);
667 bound
= build_low_bits_mask (niter_type
,
668 (TYPE_PRECISION (niter_type
)
669 - tree_to_uhwi (bits
)));
671 d
= fold_binary_to_constant (LSHIFT_EXPR
, niter_type
,
672 build_int_cst (niter_type
, 1), bits
);
673 s
= fold_binary_to_constant (RSHIFT_EXPR
, niter_type
, s
, bits
);
675 if (!exit_must_be_taken
)
677 /* If we cannot assume that the exit is taken eventually, record the
678 assumptions for divisibility of c. */
679 assumption
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, c
, d
);
680 assumption
= fold_build2 (EQ_EXPR
, boolean_type_node
,
681 assumption
, build_int_cst (niter_type
, 0));
682 if (!integer_nonzerop (assumption
))
683 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
684 niter
->assumptions
, assumption
);
687 c
= fold_build2 (EXACT_DIV_EXPR
, niter_type
, c
, d
);
688 tmp
= fold_build2 (MULT_EXPR
, niter_type
, c
, inverse (s
, bound
));
689 niter
->niter
= fold_build2 (BIT_AND_EXPR
, niter_type
, tmp
, bound
);
693 /* Checks whether we can determine the final value of the control variable
694 of the loop with ending condition IV0 < IV1 (computed in TYPE).
695 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
696 of the step. The assumptions necessary to ensure that the computation
697 of the final value does not overflow are recorded in NITER. If we
698 find the final value, we adjust DELTA and return TRUE. Otherwise
699 we return false. BNDS bounds the value of IV1->base - IV0->base,
700 and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
701 true if we know that the exit must be taken eventually. */
704 number_of_iterations_lt_to_ne (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
705 struct tree_niter_desc
*niter
,
706 tree
*delta
, tree step
,
707 bool exit_must_be_taken
, bounds
*bnds
)
709 tree niter_type
= TREE_TYPE (step
);
710 tree mod
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, *delta
, step
);
713 tree assumption
= boolean_true_node
, bound
, noloop
;
714 bool ret
= false, fv_comp_no_overflow
;
716 if (POINTER_TYPE_P (type
))
719 if (TREE_CODE (mod
) != INTEGER_CST
)
721 if (integer_nonzerop (mod
))
722 mod
= fold_build2 (MINUS_EXPR
, niter_type
, step
, mod
);
723 tmod
= fold_convert (type1
, mod
);
726 wi::to_mpz (mod
, mmod
, UNSIGNED
);
727 mpz_neg (mmod
, mmod
);
729 /* If the induction variable does not overflow and the exit is taken,
730 then the computation of the final value does not overflow. This is
731 also obviously the case if the new final value is equal to the
732 current one. Finally, we postulate this for pointer type variables,
733 as the code cannot rely on the object to that the pointer points being
734 placed at the end of the address space (and more pragmatically,
735 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
736 if (integer_zerop (mod
) || POINTER_TYPE_P (type
))
737 fv_comp_no_overflow
= true;
738 else if (!exit_must_be_taken
)
739 fv_comp_no_overflow
= false;
741 fv_comp_no_overflow
=
742 (iv0
->no_overflow
&& integer_nonzerop (iv0
->step
))
743 || (iv1
->no_overflow
&& integer_nonzerop (iv1
->step
));
745 if (integer_nonzerop (iv0
->step
))
747 /* The final value of the iv is iv1->base + MOD, assuming that this
748 computation does not overflow, and that
749 iv0->base <= iv1->base + MOD. */
750 if (!fv_comp_no_overflow
)
752 bound
= fold_build2 (MINUS_EXPR
, type1
,
753 TYPE_MAX_VALUE (type1
), tmod
);
754 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
756 if (integer_zerop (assumption
))
759 if (mpz_cmp (mmod
, bnds
->below
) < 0)
760 noloop
= boolean_false_node
;
761 else if (POINTER_TYPE_P (type
))
762 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
764 fold_build_pointer_plus (iv1
->base
, tmod
));
766 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
768 fold_build2 (PLUS_EXPR
, type1
,
773 /* The final value of the iv is iv0->base - MOD, assuming that this
774 computation does not overflow, and that
775 iv0->base - MOD <= iv1->base. */
776 if (!fv_comp_no_overflow
)
778 bound
= fold_build2 (PLUS_EXPR
, type1
,
779 TYPE_MIN_VALUE (type1
), tmod
);
780 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
782 if (integer_zerop (assumption
))
785 if (mpz_cmp (mmod
, bnds
->below
) < 0)
786 noloop
= boolean_false_node
;
787 else if (POINTER_TYPE_P (type
))
788 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
789 fold_build_pointer_plus (iv0
->base
,
790 fold_build1 (NEGATE_EXPR
,
794 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
795 fold_build2 (MINUS_EXPR
, type1
,
800 if (!integer_nonzerop (assumption
))
801 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
804 if (!integer_zerop (noloop
))
805 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
808 bounds_add (bnds
, wi::to_widest (mod
), type
);
809 *delta
= fold_build2 (PLUS_EXPR
, niter_type
, *delta
, mod
);
817 /* Add assertions to NITER that ensure that the control variable of the loop
818 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
819 are TYPE. Returns false if we can prove that there is an overflow, true
820 otherwise. STEP is the absolute value of the step. */
823 assert_no_overflow_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
824 struct tree_niter_desc
*niter
, tree step
)
826 tree bound
, d
, assumption
, diff
;
827 tree niter_type
= TREE_TYPE (step
);
829 if (integer_nonzerop (iv0
->step
))
831 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
832 if (iv0
->no_overflow
)
835 /* If iv0->base is a constant, we can determine the last value before
836 overflow precisely; otherwise we conservatively assume
839 if (TREE_CODE (iv0
->base
) == INTEGER_CST
)
841 d
= fold_build2 (MINUS_EXPR
, niter_type
,
842 fold_convert (niter_type
, TYPE_MAX_VALUE (type
)),
843 fold_convert (niter_type
, iv0
->base
));
844 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
847 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
848 build_int_cst (niter_type
, 1));
849 bound
= fold_build2 (MINUS_EXPR
, type
,
850 TYPE_MAX_VALUE (type
), fold_convert (type
, diff
));
851 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
856 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
857 if (iv1
->no_overflow
)
860 if (TREE_CODE (iv1
->base
) == INTEGER_CST
)
862 d
= fold_build2 (MINUS_EXPR
, niter_type
,
863 fold_convert (niter_type
, iv1
->base
),
864 fold_convert (niter_type
, TYPE_MIN_VALUE (type
)));
865 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
868 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
869 build_int_cst (niter_type
, 1));
870 bound
= fold_build2 (PLUS_EXPR
, type
,
871 TYPE_MIN_VALUE (type
), fold_convert (type
, diff
));
872 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
876 if (integer_zerop (assumption
))
878 if (!integer_nonzerop (assumption
))
879 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
880 niter
->assumptions
, assumption
);
882 iv0
->no_overflow
= true;
883 iv1
->no_overflow
= true;
887 /* Add an assumption to NITER that a loop whose ending condition
888 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
889 bounds the value of IV1->base - IV0->base. */
892 assert_loop_rolls_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
893 struct tree_niter_desc
*niter
, bounds
*bnds
)
895 tree assumption
= boolean_true_node
, bound
, diff
;
896 tree mbz
, mbzl
, mbzr
, type1
;
897 bool rolls_p
, no_overflow_p
;
901 /* We are going to compute the number of iterations as
902 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
903 variant of TYPE. This formula only works if
905 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
907 (where MAX is the maximum value of the unsigned variant of TYPE, and
908 the computations in this formula are performed in full precision,
909 i.e., without overflows).
911 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
912 we have a condition of the form iv0->base - step < iv1->base before the loop,
913 and for loops iv0->base < iv1->base - step * i the condition
914 iv0->base < iv1->base + step, due to loop header copying, which enable us
915 to prove the lower bound.
917 The upper bound is more complicated. Unless the expressions for initial
918 and final value themselves contain enough information, we usually cannot
919 derive it from the context. */
921 /* First check whether the answer does not follow from the bounds we gathered
923 if (integer_nonzerop (iv0
->step
))
924 dstep
= wi::to_widest (iv0
->step
);
927 dstep
= wi::sext (wi::to_widest (iv1
->step
), TYPE_PRECISION (type
));
932 wi::to_mpz (dstep
, mstep
, UNSIGNED
);
933 mpz_neg (mstep
, mstep
);
934 mpz_add_ui (mstep
, mstep
, 1);
936 rolls_p
= mpz_cmp (mstep
, bnds
->below
) <= 0;
939 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), max
, UNSIGNED
);
940 mpz_add (max
, max
, mstep
);
941 no_overflow_p
= (mpz_cmp (bnds
->up
, max
) <= 0
942 /* For pointers, only values lying inside a single object
943 can be compared or manipulated by pointer arithmetics.
944 Gcc in general does not allow or handle objects larger
945 than half of the address space, hence the upper bound
946 is satisfied for pointers. */
947 || POINTER_TYPE_P (type
));
951 if (rolls_p
&& no_overflow_p
)
955 if (POINTER_TYPE_P (type
))
958 /* Now the hard part; we must formulate the assumption(s) as expressions, and
959 we must be careful not to introduce overflow. */
961 if (integer_nonzerop (iv0
->step
))
963 diff
= fold_build2 (MINUS_EXPR
, type1
,
964 iv0
->step
, build_int_cst (type1
, 1));
966 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
967 0 address never belongs to any object, we can assume this for
969 if (!POINTER_TYPE_P (type
))
971 bound
= fold_build2 (PLUS_EXPR
, type1
,
972 TYPE_MIN_VALUE (type
), diff
);
973 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
977 /* And then we can compute iv0->base - diff, and compare it with
979 mbzl
= fold_build2 (MINUS_EXPR
, type1
,
980 fold_convert (type1
, iv0
->base
), diff
);
981 mbzr
= fold_convert (type1
, iv1
->base
);
985 diff
= fold_build2 (PLUS_EXPR
, type1
,
986 iv1
->step
, build_int_cst (type1
, 1));
988 if (!POINTER_TYPE_P (type
))
990 bound
= fold_build2 (PLUS_EXPR
, type1
,
991 TYPE_MAX_VALUE (type
), diff
);
992 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
996 mbzl
= fold_convert (type1
, iv0
->base
);
997 mbzr
= fold_build2 (MINUS_EXPR
, type1
,
998 fold_convert (type1
, iv1
->base
), diff
);
1001 if (!integer_nonzerop (assumption
))
1002 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1003 niter
->assumptions
, assumption
);
1006 mbz
= fold_build2 (GT_EXPR
, boolean_type_node
, mbzl
, mbzr
);
1007 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1008 niter
->may_be_zero
, mbz
);
1012 /* Determines number of iterations of loop whose ending condition
1013 is IV0 < IV1. TYPE is the type of the iv. The number of
1014 iterations is stored to NITER. BNDS bounds the difference
1015 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
1016 that the exit must be taken eventually. */
1019 number_of_iterations_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1020 struct tree_niter_desc
*niter
,
1021 bool exit_must_be_taken
, bounds
*bnds
)
1023 tree niter_type
= unsigned_type_for (type
);
1024 tree delta
, step
, s
;
1027 if (integer_nonzerop (iv0
->step
))
1029 niter
->control
= *iv0
;
1030 niter
->cmp
= LT_EXPR
;
1031 niter
->bound
= iv1
->base
;
1035 niter
->control
= *iv1
;
1036 niter
->cmp
= GT_EXPR
;
1037 niter
->bound
= iv0
->base
;
1040 delta
= fold_build2 (MINUS_EXPR
, niter_type
,
1041 fold_convert (niter_type
, iv1
->base
),
1042 fold_convert (niter_type
, iv0
->base
));
1044 /* First handle the special case that the step is +-1. */
1045 if ((integer_onep (iv0
->step
) && integer_zerop (iv1
->step
))
1046 || (integer_all_onesp (iv1
->step
) && integer_zerop (iv0
->step
)))
1048 /* for (i = iv0->base; i < iv1->base; i++)
1052 for (i = iv1->base; i > iv0->base; i--).
1054 In both cases # of iterations is iv1->base - iv0->base, assuming that
1055 iv1->base >= iv0->base.
1057 First try to derive a lower bound on the value of
1058 iv1->base - iv0->base, computed in full precision. If the difference
1059 is nonnegative, we are done, otherwise we must record the
1062 if (mpz_sgn (bnds
->below
) < 0)
1063 niter
->may_be_zero
= fold_build2 (LT_EXPR
, boolean_type_node
,
1064 iv1
->base
, iv0
->base
);
1065 niter
->niter
= delta
;
1066 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, bnds
->up
, false),
1067 TYPE_SIGN (niter_type
));
1071 if (integer_nonzerop (iv0
->step
))
1072 step
= fold_convert (niter_type
, iv0
->step
);
1074 step
= fold_convert (niter_type
,
1075 fold_build1 (NEGATE_EXPR
, type
, iv1
->step
));
1077 /* If we can determine the final value of the control iv exactly, we can
1078 transform the condition to != comparison. In particular, this will be
1079 the case if DELTA is constant. */
1080 if (number_of_iterations_lt_to_ne (type
, iv0
, iv1
, niter
, &delta
, step
,
1081 exit_must_be_taken
, bnds
))
1085 zps
.base
= build_int_cst (niter_type
, 0);
1087 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1088 zps does not overflow. */
1089 zps
.no_overflow
= true;
1091 return number_of_iterations_ne (type
, &zps
, delta
, niter
, true, bnds
);
1094 /* Make sure that the control iv does not overflow. */
1095 if (!assert_no_overflow_lt (type
, iv0
, iv1
, niter
, step
))
1098 /* We determine the number of iterations as (delta + step - 1) / step. For
1099 this to work, we must know that iv1->base >= iv0->base - step + 1,
1100 otherwise the loop does not roll. */
1101 assert_loop_rolls_lt (type
, iv0
, iv1
, niter
, bnds
);
1103 s
= fold_build2 (MINUS_EXPR
, niter_type
,
1104 step
, build_int_cst (niter_type
, 1));
1105 delta
= fold_build2 (PLUS_EXPR
, niter_type
, delta
, s
);
1106 niter
->niter
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, delta
, step
);
1110 wi::to_mpz (step
, mstep
, UNSIGNED
);
1111 mpz_add (tmp
, bnds
->up
, mstep
);
1112 mpz_sub_ui (tmp
, tmp
, 1);
1113 mpz_fdiv_q (tmp
, tmp
, mstep
);
1114 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, tmp
, false),
1115 TYPE_SIGN (niter_type
));
1122 /* Determines number of iterations of loop whose ending condition
1123 is IV0 <= IV1. TYPE is the type of the iv. The number of
1124 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
1125 we know that this condition must eventually become false (we derived this
1126 earlier, and possibly set NITER->assumptions to make sure this
1127 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1130 number_of_iterations_le (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1131 struct tree_niter_desc
*niter
, bool exit_must_be_taken
,
1136 if (POINTER_TYPE_P (type
))
1139 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1140 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1141 value of the type. This we must know anyway, since if it is
1142 equal to this value, the loop rolls forever. We do not check
1143 this condition for pointer type ivs, as the code cannot rely on
1144 the object to that the pointer points being placed at the end of
1145 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1146 not defined for pointers). */
1148 if (!exit_must_be_taken
&& !POINTER_TYPE_P (type
))
1150 if (integer_nonzerop (iv0
->step
))
1151 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1152 iv1
->base
, TYPE_MAX_VALUE (type
));
1154 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1155 iv0
->base
, TYPE_MIN_VALUE (type
));
1157 if (integer_zerop (assumption
))
1159 if (!integer_nonzerop (assumption
))
1160 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1161 niter
->assumptions
, assumption
);
1164 if (integer_nonzerop (iv0
->step
))
1166 if (POINTER_TYPE_P (type
))
1167 iv1
->base
= fold_build_pointer_plus_hwi (iv1
->base
, 1);
1169 iv1
->base
= fold_build2 (PLUS_EXPR
, type1
, iv1
->base
,
1170 build_int_cst (type1
, 1));
1172 else if (POINTER_TYPE_P (type
))
1173 iv0
->base
= fold_build_pointer_plus_hwi (iv0
->base
, -1);
1175 iv0
->base
= fold_build2 (MINUS_EXPR
, type1
,
1176 iv0
->base
, build_int_cst (type1
, 1));
1178 bounds_add (bnds
, 1, type1
);
1180 return number_of_iterations_lt (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1184 /* Dumps description of affine induction variable IV to FILE. */
1187 dump_affine_iv (FILE *file
, affine_iv
*iv
)
1189 if (!integer_zerop (iv
->step
))
1190 fprintf (file
, "[");
1192 print_generic_expr (dump_file
, iv
->base
, TDF_SLIM
);
1194 if (!integer_zerop (iv
->step
))
1196 fprintf (file
, ", + , ");
1197 print_generic_expr (dump_file
, iv
->step
, TDF_SLIM
);
1198 fprintf (file
, "]%s", iv
->no_overflow
? "(no_overflow)" : "");
1202 /* Determine the number of iterations according to condition (for staying
1203 inside loop) which compares two induction variables using comparison
1204 operator CODE. The induction variable on left side of the comparison
1205 is IV0, the right-hand side is IV1. Both induction variables must have
1206 type TYPE, which must be an integer or pointer type. The steps of the
1207 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1209 LOOP is the loop whose number of iterations we are determining.
1211 ONLY_EXIT is true if we are sure this is the only way the loop could be
1212 exited (including possibly non-returning function calls, exceptions, etc.)
1213 -- in this case we can use the information whether the control induction
1214 variables can overflow or not in a more efficient way.
1216 if EVERY_ITERATION is true, we know the test is executed on every iteration.
1218 The results (number of iterations and assumptions as described in
1219 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
1220 Returns false if it fails to determine number of iterations, true if it
1221 was determined (possibly with some assumptions). */
1224 number_of_iterations_cond (struct loop
*loop
,
1225 tree type
, affine_iv
*iv0
, enum tree_code code
,
1226 affine_iv
*iv1
, struct tree_niter_desc
*niter
,
1227 bool only_exit
, bool every_iteration
)
1229 bool exit_must_be_taken
= false, ret
;
1232 /* If the test is not executed every iteration, wrapping may make the test
1234 TODO: the overflow case can be still used as unreliable estimate of upper
1235 bound. But we have no API to pass it down to number of iterations code
1236 and, at present, it will not use it anyway. */
1237 if (!every_iteration
1238 && (!iv0
->no_overflow
|| !iv1
->no_overflow
1239 || code
== NE_EXPR
|| code
== EQ_EXPR
))
1242 /* The meaning of these assumptions is this:
1244 then the rest of information does not have to be valid
1245 if may_be_zero then the loop does not roll, even if
1247 niter
->assumptions
= boolean_true_node
;
1248 niter
->may_be_zero
= boolean_false_node
;
1249 niter
->niter
= NULL_TREE
;
1251 niter
->bound
= NULL_TREE
;
1252 niter
->cmp
= ERROR_MARK
;
1254 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1255 the control variable is on lhs. */
1256 if (code
== GE_EXPR
|| code
== GT_EXPR
1257 || (code
== NE_EXPR
&& integer_zerop (iv0
->step
)))
1260 code
= swap_tree_comparison (code
);
1263 if (POINTER_TYPE_P (type
))
1265 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1266 to the same object. If they do, the control variable cannot wrap
1267 (as wrap around the bounds of memory will never return a pointer
1268 that would be guaranteed to point to the same object, even if we
1269 avoid undefined behavior by casting to size_t and back). */
1270 iv0
->no_overflow
= true;
1271 iv1
->no_overflow
= true;
1274 /* If the control induction variable does not overflow and the only exit
1275 from the loop is the one that we analyze, we know it must be taken
1279 if (!integer_zerop (iv0
->step
) && iv0
->no_overflow
)
1280 exit_must_be_taken
= true;
1281 else if (!integer_zerop (iv1
->step
) && iv1
->no_overflow
)
1282 exit_must_be_taken
= true;
1285 /* We can handle the case when neither of the sides of the comparison is
1286 invariant, provided that the test is NE_EXPR. This rarely occurs in
1287 practice, but it is simple enough to manage. */
1288 if (!integer_zerop (iv0
->step
) && !integer_zerop (iv1
->step
))
1290 tree step_type
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1291 if (code
!= NE_EXPR
)
1294 iv0
->step
= fold_binary_to_constant (MINUS_EXPR
, step_type
,
1295 iv0
->step
, iv1
->step
);
1296 iv0
->no_overflow
= false;
1297 iv1
->step
= build_int_cst (step_type
, 0);
1298 iv1
->no_overflow
= true;
1301 /* If the result of the comparison is a constant, the loop is weird. More
1302 precise handling would be possible, but the situation is not common enough
1303 to waste time on it. */
1304 if (integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
))
1307 /* Ignore loops of while (i-- < 10) type. */
1308 if (code
!= NE_EXPR
)
1310 if (iv0
->step
&& tree_int_cst_sign_bit (iv0
->step
))
1313 if (!integer_zerop (iv1
->step
) && !tree_int_cst_sign_bit (iv1
->step
))
1317 /* If the loop exits immediately, there is nothing to do. */
1318 tree tem
= fold_binary (code
, boolean_type_node
, iv0
->base
, iv1
->base
);
1319 if (tem
&& integer_zerop (tem
))
1321 niter
->niter
= build_int_cst (unsigned_type_for (type
), 0);
1326 /* OK, now we know we have a senseful loop. Handle several cases, depending
1327 on what comparison operator is used. */
1328 bound_difference (loop
, iv1
->base
, iv0
->base
, &bnds
);
1330 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1333 "Analyzing # of iterations of loop %d\n", loop
->num
);
1335 fprintf (dump_file
, " exit condition ");
1336 dump_affine_iv (dump_file
, iv0
);
1337 fprintf (dump_file
, " %s ",
1338 code
== NE_EXPR
? "!="
1339 : code
== LT_EXPR
? "<"
1341 dump_affine_iv (dump_file
, iv1
);
1342 fprintf (dump_file
, "\n");
1344 fprintf (dump_file
, " bounds on difference of bases: ");
1345 mpz_out_str (dump_file
, 10, bnds
.below
);
1346 fprintf (dump_file
, " ... ");
1347 mpz_out_str (dump_file
, 10, bnds
.up
);
1348 fprintf (dump_file
, "\n");
1354 gcc_assert (integer_zerop (iv1
->step
));
1355 ret
= number_of_iterations_ne (type
, iv0
, iv1
->base
, niter
,
1356 exit_must_be_taken
, &bnds
);
1360 ret
= number_of_iterations_lt (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1365 ret
= number_of_iterations_le (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1373 mpz_clear (bnds
.up
);
1374 mpz_clear (bnds
.below
);
1376 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1380 fprintf (dump_file
, " result:\n");
1381 if (!integer_nonzerop (niter
->assumptions
))
1383 fprintf (dump_file
, " under assumptions ");
1384 print_generic_expr (dump_file
, niter
->assumptions
, TDF_SLIM
);
1385 fprintf (dump_file
, "\n");
1388 if (!integer_zerop (niter
->may_be_zero
))
1390 fprintf (dump_file
, " zero if ");
1391 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
1392 fprintf (dump_file
, "\n");
1395 fprintf (dump_file
, " # of iterations ");
1396 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
1397 fprintf (dump_file
, ", bounded by ");
1398 print_decu (niter
->max
, dump_file
);
1399 fprintf (dump_file
, "\n");
1402 fprintf (dump_file
, " failed\n\n");
1407 /* Substitute NEW for OLD in EXPR and fold the result. */
1410 simplify_replace_tree (tree expr
, tree old
, tree new_tree
)
1413 tree ret
= NULL_TREE
, e
, se
;
1418 /* Do not bother to replace constants. */
1419 if (CONSTANT_CLASS_P (old
))
1423 || operand_equal_p (expr
, old
, 0))
1424 return unshare_expr (new_tree
);
1429 n
= TREE_OPERAND_LENGTH (expr
);
1430 for (i
= 0; i
< n
; i
++)
1432 e
= TREE_OPERAND (expr
, i
);
1433 se
= simplify_replace_tree (e
, old
, new_tree
);
1438 ret
= copy_node (expr
);
1440 TREE_OPERAND (ret
, i
) = se
;
1443 return (ret
? fold (ret
) : expr
);
1446 /* Expand definitions of ssa names in EXPR as long as they are simple
1447 enough, and return the new expression. */
1450 expand_simple_operations (tree expr
)
1453 tree ret
= NULL_TREE
, e
, ee
, e1
;
1454 enum tree_code code
;
1457 if (expr
== NULL_TREE
)
1460 if (is_gimple_min_invariant (expr
))
1463 code
= TREE_CODE (expr
);
1464 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
1466 n
= TREE_OPERAND_LENGTH (expr
);
1467 for (i
= 0; i
< n
; i
++)
1469 e
= TREE_OPERAND (expr
, i
);
1470 ee
= expand_simple_operations (e
);
1475 ret
= copy_node (expr
);
1477 TREE_OPERAND (ret
, i
) = ee
;
1483 fold_defer_overflow_warnings ();
1485 fold_undefer_and_ignore_overflow_warnings ();
1489 if (TREE_CODE (expr
) != SSA_NAME
)
1492 stmt
= SSA_NAME_DEF_STMT (expr
);
1493 if (gimple_code (stmt
) == GIMPLE_PHI
)
1495 basic_block src
, dest
;
1497 if (gimple_phi_num_args (stmt
) != 1)
1499 e
= PHI_ARG_DEF (stmt
, 0);
1501 /* Avoid propagating through loop exit phi nodes, which
1502 could break loop-closed SSA form restrictions. */
1503 dest
= gimple_bb (stmt
);
1504 src
= single_pred (dest
);
1505 if (TREE_CODE (e
) == SSA_NAME
1506 && src
->loop_father
!= dest
->loop_father
)
1509 return expand_simple_operations (e
);
1511 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1514 /* Avoid expanding to expressions that contain SSA names that need
1515 to take part in abnormal coalescing. */
1517 FOR_EACH_SSA_TREE_OPERAND (e
, stmt
, iter
, SSA_OP_USE
)
1518 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (e
))
1521 e
= gimple_assign_rhs1 (stmt
);
1522 code
= gimple_assign_rhs_code (stmt
);
1523 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1525 if (is_gimple_min_invariant (e
))
1528 if (code
== SSA_NAME
)
1529 return expand_simple_operations (e
);
1537 /* Casts are simple. */
1538 ee
= expand_simple_operations (e
);
1539 return fold_build1 (code
, TREE_TYPE (expr
), ee
);
1543 case POINTER_PLUS_EXPR
:
1544 /* And increments and decrements by a constant are simple. */
1545 e1
= gimple_assign_rhs2 (stmt
);
1546 if (!is_gimple_min_invariant (e1
))
1549 ee
= expand_simple_operations (e
);
1550 return fold_build2 (code
, TREE_TYPE (expr
), ee
, e1
);
1557 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1558 expression (or EXPR unchanged, if no simplification was possible). */
1561 tree_simplify_using_condition_1 (tree cond
, tree expr
)
1564 tree e
, te
, e0
, e1
, e2
, notcond
;
1565 enum tree_code code
= TREE_CODE (expr
);
1567 if (code
== INTEGER_CST
)
1570 if (code
== TRUTH_OR_EXPR
1571 || code
== TRUTH_AND_EXPR
1572 || code
== COND_EXPR
)
1576 e0
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 0));
1577 if (TREE_OPERAND (expr
, 0) != e0
)
1580 e1
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 1));
1581 if (TREE_OPERAND (expr
, 1) != e1
)
1584 if (code
== COND_EXPR
)
1586 e2
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 2));
1587 if (TREE_OPERAND (expr
, 2) != e2
)
1595 if (code
== COND_EXPR
)
1596 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1598 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1604 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
1605 propagation, and vice versa. Fold does not handle this, since it is
1606 considered too expensive. */
1607 if (TREE_CODE (cond
) == EQ_EXPR
)
1609 e0
= TREE_OPERAND (cond
, 0);
1610 e1
= TREE_OPERAND (cond
, 1);
1612 /* We know that e0 == e1. Check whether we cannot simplify expr
1614 e
= simplify_replace_tree (expr
, e0
, e1
);
1615 if (integer_zerop (e
) || integer_nonzerop (e
))
1618 e
= simplify_replace_tree (expr
, e1
, e0
);
1619 if (integer_zerop (e
) || integer_nonzerop (e
))
1622 if (TREE_CODE (expr
) == EQ_EXPR
)
1624 e0
= TREE_OPERAND (expr
, 0);
1625 e1
= TREE_OPERAND (expr
, 1);
1627 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
1628 e
= simplify_replace_tree (cond
, e0
, e1
);
1629 if (integer_zerop (e
))
1631 e
= simplify_replace_tree (cond
, e1
, e0
);
1632 if (integer_zerop (e
))
1635 if (TREE_CODE (expr
) == NE_EXPR
)
1637 e0
= TREE_OPERAND (expr
, 0);
1638 e1
= TREE_OPERAND (expr
, 1);
1640 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
1641 e
= simplify_replace_tree (cond
, e0
, e1
);
1642 if (integer_zerop (e
))
1643 return boolean_true_node
;
1644 e
= simplify_replace_tree (cond
, e1
, e0
);
1645 if (integer_zerop (e
))
1646 return boolean_true_node
;
1649 te
= expand_simple_operations (expr
);
1651 /* Check whether COND ==> EXPR. */
1652 notcond
= invert_truthvalue (cond
);
1653 e
= fold_binary (TRUTH_OR_EXPR
, boolean_type_node
, notcond
, te
);
1654 if (e
&& integer_nonzerop (e
))
1657 /* Check whether COND ==> not EXPR. */
1658 e
= fold_binary (TRUTH_AND_EXPR
, boolean_type_node
, cond
, te
);
1659 if (e
&& integer_zerop (e
))
1665 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1666 expression (or EXPR unchanged, if no simplification was possible).
1667 Wrapper around tree_simplify_using_condition_1 that ensures that chains
1668 of simple operations in definitions of ssa names in COND are expanded,
1669 so that things like casts or incrementing the value of the bound before
1670 the loop do not cause us to fail. */
1673 tree_simplify_using_condition (tree cond
, tree expr
)
1675 cond
= expand_simple_operations (cond
);
1677 return tree_simplify_using_condition_1 (cond
, expr
);
1680 /* Tries to simplify EXPR using the conditions on entry to LOOP.
1681 Returns the simplified expression (or EXPR unchanged, if no
1682 simplification was possible).*/
1685 simplify_using_initial_conditions (struct loop
*loop
, tree expr
)
1693 if (TREE_CODE (expr
) == INTEGER_CST
)
1696 /* Limit walking the dominators to avoid quadraticness in
1697 the number of BBs times the number of loops in degenerate
1699 for (bb
= loop
->header
;
1700 bb
!= ENTRY_BLOCK_PTR
&& cnt
< MAX_DOMINATORS_TO_WALK
;
1701 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1703 if (!single_pred_p (bb
))
1705 e
= single_pred_edge (bb
);
1707 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
1710 stmt
= last_stmt (e
->src
);
1711 cond
= fold_build2 (gimple_cond_code (stmt
),
1713 gimple_cond_lhs (stmt
),
1714 gimple_cond_rhs (stmt
));
1715 if (e
->flags
& EDGE_FALSE_VALUE
)
1716 cond
= invert_truthvalue (cond
);
1717 expr
= tree_simplify_using_condition (cond
, expr
);
1724 /* Tries to simplify EXPR using the evolutions of the loop invariants
1725 in the superloops of LOOP. Returns the simplified expression
1726 (or EXPR unchanged, if no simplification was possible). */
1729 simplify_using_outer_evolutions (struct loop
*loop
, tree expr
)
1731 enum tree_code code
= TREE_CODE (expr
);
1735 if (is_gimple_min_invariant (expr
))
1738 if (code
== TRUTH_OR_EXPR
1739 || code
== TRUTH_AND_EXPR
1740 || code
== COND_EXPR
)
1744 e0
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 0));
1745 if (TREE_OPERAND (expr
, 0) != e0
)
1748 e1
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 1));
1749 if (TREE_OPERAND (expr
, 1) != e1
)
1752 if (code
== COND_EXPR
)
1754 e2
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 2));
1755 if (TREE_OPERAND (expr
, 2) != e2
)
1763 if (code
== COND_EXPR
)
1764 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1766 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1772 e
= instantiate_parameters (loop
, expr
);
1773 if (is_gimple_min_invariant (e
))
1779 /* Returns true if EXIT is the only possible exit from LOOP. */
1782 loop_only_exit_p (const struct loop
*loop
, const_edge exit
)
1785 gimple_stmt_iterator bsi
;
1789 if (exit
!= single_exit (loop
))
1792 body
= get_loop_body (loop
);
1793 for (i
= 0; i
< loop
->num_nodes
; i
++)
1795 for (bsi
= gsi_start_bb (body
[i
]); !gsi_end_p (bsi
); gsi_next (&bsi
))
1797 call
= gsi_stmt (bsi
);
1798 if (gimple_code (call
) != GIMPLE_CALL
)
1801 if (gimple_has_side_effects (call
))
1813 /* Stores description of number of iterations of LOOP derived from
1814 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
1815 useful information could be derived (and fields of NITER has
1816 meaning described in comments at struct tree_niter_desc
1817 declaration), false otherwise. If WARN is true and
1818 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1819 potentially unsafe assumptions.
1820 When EVERY_ITERATION is true, only tests that are known to be executed
1821 every iteration are considered (i.e. only test that alone bounds the loop).
1825 number_of_iterations_exit (struct loop
*loop
, edge exit
,
1826 struct tree_niter_desc
*niter
,
1827 bool warn
, bool every_iteration
)
1832 enum tree_code code
;
1836 safe
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit
->src
);
1838 if (every_iteration
&& !safe
)
1841 niter
->assumptions
= boolean_false_node
;
1842 stmt
= last_stmt (exit
->src
);
1843 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1846 /* We want the condition for staying inside loop. */
1847 code
= gimple_cond_code (stmt
);
1848 if (exit
->flags
& EDGE_TRUE_VALUE
)
1849 code
= invert_tree_comparison (code
, false);
1864 op0
= gimple_cond_lhs (stmt
);
1865 op1
= gimple_cond_rhs (stmt
);
1866 type
= TREE_TYPE (op0
);
1868 if (TREE_CODE (type
) != INTEGER_TYPE
1869 && !POINTER_TYPE_P (type
))
1872 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, false))
1874 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, false))
1877 /* We don't want to see undefined signed overflow warnings while
1878 computing the number of iterations. */
1879 fold_defer_overflow_warnings ();
1881 iv0
.base
= expand_simple_operations (iv0
.base
);
1882 iv1
.base
= expand_simple_operations (iv1
.base
);
1883 if (!number_of_iterations_cond (loop
, type
, &iv0
, code
, &iv1
, niter
,
1884 loop_only_exit_p (loop
, exit
), safe
))
1886 fold_undefer_and_ignore_overflow_warnings ();
1892 niter
->assumptions
= simplify_using_outer_evolutions (loop
,
1893 niter
->assumptions
);
1894 niter
->may_be_zero
= simplify_using_outer_evolutions (loop
,
1895 niter
->may_be_zero
);
1896 niter
->niter
= simplify_using_outer_evolutions (loop
, niter
->niter
);
1900 = simplify_using_initial_conditions (loop
,
1901 niter
->assumptions
);
1903 = simplify_using_initial_conditions (loop
,
1904 niter
->may_be_zero
);
1906 fold_undefer_and_ignore_overflow_warnings ();
1908 /* If NITER has simplified into a constant, update MAX. */
1909 if (TREE_CODE (niter
->niter
) == INTEGER_CST
)
1910 niter
->max
= wi::to_widest (niter
->niter
);
1912 if (integer_onep (niter
->assumptions
))
1915 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1916 But if we can prove that there is overflow or some other source of weird
1917 behavior, ignore the loop even with -funsafe-loop-optimizations. */
1918 if (integer_zerop (niter
->assumptions
) || !single_exit (loop
))
1921 if (flag_unsafe_loop_optimizations
)
1922 niter
->assumptions
= boolean_true_node
;
1926 const char *wording
;
1927 location_t loc
= gimple_location (stmt
);
1929 /* We can provide a more specific warning if one of the operator is
1930 constant and the other advances by +1 or -1. */
1931 if (!integer_zerop (iv1
.step
)
1932 ? (integer_zerop (iv0
.step
)
1933 && (integer_onep (iv1
.step
) || integer_all_onesp (iv1
.step
)))
1934 : (integer_onep (iv0
.step
) || integer_all_onesp (iv0
.step
)))
1936 flag_unsafe_loop_optimizations
1937 ? N_("assuming that the loop is not infinite")
1938 : N_("cannot optimize possibly infinite loops");
1941 flag_unsafe_loop_optimizations
1942 ? N_("assuming that the loop counter does not overflow")
1943 : N_("cannot optimize loop, the loop counter may overflow");
1945 warning_at ((LOCATION_LINE (loc
) > 0) ? loc
: input_location
,
1946 OPT_Wunsafe_loop_optimizations
, "%s", gettext (wording
));
1949 return flag_unsafe_loop_optimizations
;
1952 /* Try to determine the number of iterations of LOOP. If we succeed,
1953 expression giving number of iterations is returned and *EXIT is
1954 set to the edge from that the information is obtained. Otherwise
1955 chrec_dont_know is returned. */
1958 find_loop_niter (struct loop
*loop
, edge
*exit
)
1961 vec
<edge
> exits
= get_loop_exit_edges (loop
);
1963 tree niter
= NULL_TREE
, aniter
;
1964 struct tree_niter_desc desc
;
1967 FOR_EACH_VEC_ELT (exits
, i
, ex
)
1969 if (!number_of_iterations_exit (loop
, ex
, &desc
, false))
1972 if (integer_nonzerop (desc
.may_be_zero
))
1974 /* We exit in the first iteration through this exit.
1975 We won't find anything better. */
1976 niter
= build_int_cst (unsigned_type_node
, 0);
1981 if (!integer_zerop (desc
.may_be_zero
))
1984 aniter
= desc
.niter
;
1988 /* Nothing recorded yet. */
1994 /* Prefer constants, the lower the better. */
1995 if (TREE_CODE (aniter
) != INTEGER_CST
)
1998 if (TREE_CODE (niter
) != INTEGER_CST
)
2005 if (tree_int_cst_lt (aniter
, niter
))
2014 return niter
? niter
: chrec_dont_know
;
2017 /* Return true if loop is known to have bounded number of iterations. */
2020 finite_loop_p (struct loop
*loop
)
2025 if (flag_unsafe_loop_optimizations
)
2027 flags
= flags_from_decl_or_type (current_function_decl
);
2028 if ((flags
& (ECF_CONST
|ECF_PURE
)) && !(flags
& ECF_LOOPING_CONST_OR_PURE
))
2030 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2031 fprintf (dump_file
, "Found loop %i to be finite: it is within pure or const function.\n",
2036 if (loop
->any_upper_bound
2037 || max_loop_iterations (loop
, &nit
))
2039 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2040 fprintf (dump_file
, "Found loop %i to be finite: upper bound found.\n",
2049 Analysis of a number of iterations of a loop by a brute-force evaluation.
2053 /* Bound on the number of iterations we try to evaluate. */
2055 #define MAX_ITERATIONS_TO_TRACK \
2056 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
2058 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
2059 result by a chain of operations such that all but exactly one of their
2060 operands are constants. */
2063 chain_of_csts_start (struct loop
*loop
, tree x
)
2065 gimple stmt
= SSA_NAME_DEF_STMT (x
);
2067 basic_block bb
= gimple_bb (stmt
);
2068 enum tree_code code
;
2071 || !flow_bb_inside_loop_p (loop
, bb
))
2074 if (gimple_code (stmt
) == GIMPLE_PHI
)
2076 if (bb
== loop
->header
)
2082 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2085 code
= gimple_assign_rhs_code (stmt
);
2086 if (gimple_references_memory_p (stmt
)
2087 || TREE_CODE_CLASS (code
) == tcc_reference
2088 || (code
== ADDR_EXPR
2089 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
2092 use
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
2093 if (use
== NULL_TREE
)
2096 return chain_of_csts_start (loop
, use
);
2099 /* Determines whether the expression X is derived from a result of a phi node
2100 in header of LOOP such that
2102 * the derivation of X consists only from operations with constants
2103 * the initial value of the phi node is constant
2104 * the value of the phi node in the next iteration can be derived from the
2105 value in the current iteration by a chain of operations with constants.
2107 If such phi node exists, it is returned, otherwise NULL is returned. */
2110 get_base_for (struct loop
*loop
, tree x
)
2115 if (is_gimple_min_invariant (x
))
2118 phi
= chain_of_csts_start (loop
, x
);
2122 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2123 next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2125 if (TREE_CODE (next
) != SSA_NAME
)
2128 if (!is_gimple_min_invariant (init
))
2131 if (chain_of_csts_start (loop
, next
) != phi
)
2137 /* Given an expression X, then
2139 * if X is NULL_TREE, we return the constant BASE.
2140 * otherwise X is a SSA name, whose value in the considered loop is derived
2141 by a chain of operations with constant from a result of a phi node in
2142 the header of the loop. Then we return value of X when the value of the
2143 result of this phi node is given by the constant BASE. */
2146 get_val_for (tree x
, tree base
)
2150 gcc_assert (is_gimple_min_invariant (base
));
2155 stmt
= SSA_NAME_DEF_STMT (x
);
2156 if (gimple_code (stmt
) == GIMPLE_PHI
)
2159 gcc_assert (is_gimple_assign (stmt
));
2161 /* STMT must be either an assignment of a single SSA name or an
2162 expression involving an SSA name and a constant. Try to fold that
2163 expression using the value for the SSA name. */
2164 if (gimple_assign_ssa_name_copy_p (stmt
))
2165 return get_val_for (gimple_assign_rhs1 (stmt
), base
);
2166 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_UNARY_RHS
2167 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
2169 return fold_build1 (gimple_assign_rhs_code (stmt
),
2170 gimple_expr_type (stmt
),
2171 get_val_for (gimple_assign_rhs1 (stmt
), base
));
2173 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_BINARY_RHS
)
2175 tree rhs1
= gimple_assign_rhs1 (stmt
);
2176 tree rhs2
= gimple_assign_rhs2 (stmt
);
2177 if (TREE_CODE (rhs1
) == SSA_NAME
)
2178 rhs1
= get_val_for (rhs1
, base
);
2179 else if (TREE_CODE (rhs2
) == SSA_NAME
)
2180 rhs2
= get_val_for (rhs2
, base
);
2183 return fold_build2 (gimple_assign_rhs_code (stmt
),
2184 gimple_expr_type (stmt
), rhs1
, rhs2
);
2191 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2192 by brute force -- i.e. by determining the value of the operands of the
2193 condition at EXIT in first few iterations of the loop (assuming that
2194 these values are constant) and determining the first one in that the
2195 condition is not satisfied. Returns the constant giving the number
2196 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
2199 loop_niter_by_eval (struct loop
*loop
, edge exit
)
2202 tree op
[2], val
[2], next
[2], aval
[2];
2207 cond
= last_stmt (exit
->src
);
2208 if (!cond
|| gimple_code (cond
) != GIMPLE_COND
)
2209 return chrec_dont_know
;
2211 cmp
= gimple_cond_code (cond
);
2212 if (exit
->flags
& EDGE_TRUE_VALUE
)
2213 cmp
= invert_tree_comparison (cmp
, false);
2223 op
[0] = gimple_cond_lhs (cond
);
2224 op
[1] = gimple_cond_rhs (cond
);
2228 return chrec_dont_know
;
2231 for (j
= 0; j
< 2; j
++)
2233 if (is_gimple_min_invariant (op
[j
]))
2236 next
[j
] = NULL_TREE
;
2241 phi
= get_base_for (loop
, op
[j
]);
2243 return chrec_dont_know
;
2244 val
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2245 next
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2249 /* Don't issue signed overflow warnings. */
2250 fold_defer_overflow_warnings ();
2252 for (i
= 0; i
< MAX_ITERATIONS_TO_TRACK
; i
++)
2254 for (j
= 0; j
< 2; j
++)
2255 aval
[j
] = get_val_for (op
[j
], val
[j
]);
2257 acnd
= fold_binary (cmp
, boolean_type_node
, aval
[0], aval
[1]);
2258 if (acnd
&& integer_zerop (acnd
))
2260 fold_undefer_and_ignore_overflow_warnings ();
2261 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2263 "Proved that loop %d iterates %d times using brute force.\n",
2265 return build_int_cst (unsigned_type_node
, i
);
2268 for (j
= 0; j
< 2; j
++)
2270 val
[j
] = get_val_for (next
[j
], val
[j
]);
2271 if (!is_gimple_min_invariant (val
[j
]))
2273 fold_undefer_and_ignore_overflow_warnings ();
2274 return chrec_dont_know
;
2279 fold_undefer_and_ignore_overflow_warnings ();
2281 return chrec_dont_know
;
2284 /* Finds the exit of the LOOP by that the loop exits after a constant
2285 number of iterations and stores the exit edge to *EXIT. The constant
2286 giving the number of iterations of LOOP is returned. The number of
2287 iterations is determined using loop_niter_by_eval (i.e. by brute force
2288 evaluation). If we are unable to find the exit for that loop_niter_by_eval
2289 determines the number of iterations, chrec_dont_know is returned. */
2292 find_loop_niter_by_eval (struct loop
*loop
, edge
*exit
)
2295 vec
<edge
> exits
= get_loop_exit_edges (loop
);
2297 tree niter
= NULL_TREE
, aniter
;
2301 /* Loops with multiple exits are expensive to handle and less important. */
2302 if (!flag_expensive_optimizations
2303 && exits
.length () > 1)
2306 return chrec_dont_know
;
2309 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2311 if (!just_once_each_iteration_p (loop
, ex
->src
))
2314 aniter
= loop_niter_by_eval (loop
, ex
);
2315 if (chrec_contains_undetermined (aniter
))
2319 && !tree_int_cst_lt (aniter
, niter
))
2327 return niter
? niter
: chrec_dont_know
;
2332 Analysis of upper bounds on number of iterations of a loop.
2336 static widest_int
derive_constant_upper_bound_ops (tree
, tree
,
2337 enum tree_code
, tree
);
2339 /* Returns a constant upper bound on the value of the right-hand side of
2340 an assignment statement STMT. */
2343 derive_constant_upper_bound_assign (gimple stmt
)
2345 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2346 tree op0
= gimple_assign_rhs1 (stmt
);
2347 tree op1
= gimple_assign_rhs2 (stmt
);
2349 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt
)),
2353 /* Returns a constant upper bound on the value of expression VAL. VAL
2354 is considered to be unsigned. If its type is signed, its value must
2358 derive_constant_upper_bound (tree val
)
2360 enum tree_code code
;
2363 extract_ops_from_tree (val
, &code
, &op0
, &op1
);
2364 return derive_constant_upper_bound_ops (TREE_TYPE (val
), op0
, code
, op1
);
2367 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
2368 whose type is TYPE. The expression is considered to be unsigned. If
2369 its type is signed, its value must be nonnegative. */
2372 derive_constant_upper_bound_ops (tree type
, tree op0
,
2373 enum tree_code code
, tree op1
)
2376 widest_int bnd
, max
, mmax
, cst
;
2379 if (INTEGRAL_TYPE_P (type
))
2380 maxt
= TYPE_MAX_VALUE (type
);
2382 maxt
= upper_bound_in_type (type
, type
);
2384 max
= wi::to_widest (maxt
);
2389 return wi::to_widest (op0
);
2392 subtype
= TREE_TYPE (op0
);
2393 if (!TYPE_UNSIGNED (subtype
)
2394 /* If TYPE is also signed, the fact that VAL is nonnegative implies
2395 that OP0 is nonnegative. */
2396 && TYPE_UNSIGNED (type
)
2397 && !tree_expr_nonnegative_p (op0
))
2399 /* If we cannot prove that the casted expression is nonnegative,
2400 we cannot establish more useful upper bound than the precision
2401 of the type gives us. */
2405 /* We now know that op0 is an nonnegative value. Try deriving an upper
2407 bnd
= derive_constant_upper_bound (op0
);
2409 /* If the bound does not fit in TYPE, max. value of TYPE could be
2411 if (wi::ltu_p (max
, bnd
))
2417 case POINTER_PLUS_EXPR
:
2419 if (TREE_CODE (op1
) != INTEGER_CST
2420 || !tree_expr_nonnegative_p (op0
))
2423 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
2424 choose the most logical way how to treat this constant regardless
2425 of the signedness of the type. */
2426 cst
= wi::sext (wi::to_widest (op1
), TYPE_PRECISION (type
));
2427 if (code
!= MINUS_EXPR
)
2430 bnd
= derive_constant_upper_bound (op0
);
2432 if (wi::neg_p (cst
))
2435 /* Avoid CST == 0x80000... */
2436 if (wi::neg_p (cst
))
2439 /* OP0 + CST. We need to check that
2440 BND <= MAX (type) - CST. */
2443 if (wi::ltu_p (bnd
, max
))
2450 /* OP0 - CST, where CST >= 0.
2452 If TYPE is signed, we have already verified that OP0 >= 0, and we
2453 know that the result is nonnegative. This implies that
2456 If TYPE is unsigned, we must additionally know that OP0 >= CST,
2457 otherwise the operation underflows.
2460 /* This should only happen if the type is unsigned; however, for
2461 buggy programs that use overflowing signed arithmetics even with
2462 -fno-wrapv, this condition may also be true for signed values. */
2463 if (wi::ltu_p (bnd
, cst
))
2466 if (TYPE_UNSIGNED (type
))
2468 tree tem
= fold_binary (GE_EXPR
, boolean_type_node
, op0
,
2469 wide_int_to_tree (type
, cst
));
2470 if (!tem
|| integer_nonzerop (tem
))
2479 case FLOOR_DIV_EXPR
:
2480 case EXACT_DIV_EXPR
:
2481 if (TREE_CODE (op1
) != INTEGER_CST
2482 || tree_int_cst_sign_bit (op1
))
2485 bnd
= derive_constant_upper_bound (op0
);
2486 return wi::udiv_floor (bnd
, wi::to_widest (op1
));
2489 if (TREE_CODE (op1
) != INTEGER_CST
2490 || tree_int_cst_sign_bit (op1
))
2492 return wi::to_widest (op1
);
2495 stmt
= SSA_NAME_DEF_STMT (op0
);
2496 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2497 || gimple_assign_lhs (stmt
) != op0
)
2499 return derive_constant_upper_bound_assign (stmt
);
2506 /* Emit a -Waggressive-loop-optimizations warning if needed. */
2509 do_warn_aggressive_loop_optimizations (struct loop
*loop
,
2510 widest_int i_bound
, gimple stmt
)
2512 /* Don't warn if the loop doesn't have known constant bound. */
2513 if (!loop
->nb_iterations
2514 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
2515 || !warn_aggressive_loop_optimizations
2516 /* To avoid warning multiple times for the same loop,
2517 only start warning when we preserve loops. */
2518 || (cfun
->curr_properties
& PROP_loops
) == 0
2519 /* Only warn once per loop. */
2520 || loop
->warned_aggressive_loop_optimizations
2521 /* Only warn if undefined behavior gives us lower estimate than the
2522 known constant bound. */
2523 || wi::cmpu (i_bound
, wi::to_widest (loop
->nb_iterations
)) >= 0
2524 /* And undefined behavior happens unconditionally. */
2525 || !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (stmt
)))
2528 edge e
= single_exit (loop
);
2532 gimple estmt
= last_stmt (e
->src
);
2533 if (warning_at (gimple_location (stmt
), OPT_Waggressive_loop_optimizations
,
2534 "iteration %E invokes undefined behavior",
2535 wide_int_to_tree (TREE_TYPE (loop
->nb_iterations
),
2537 inform (gimple_location (estmt
), "containing loop");
2538 loop
->warned_aggressive_loop_optimizations
= true;
2541 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
2542 is true if the loop is exited immediately after STMT, and this exit
2543 is taken at last when the STMT is executed BOUND + 1 times.
2544 REALISTIC is true if BOUND is expected to be close to the real number
2545 of iterations. UPPER is true if we are sure the loop iterates at most
2546 BOUND times. I_BOUND is an unsigned wide_int upper estimate on BOUND. */
2549 record_estimate (struct loop
*loop
, tree bound
, widest_int i_bound
,
2550 gimple at_stmt
, bool is_exit
, bool realistic
, bool upper
)
2554 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2556 fprintf (dump_file
, "Statement %s", is_exit
? "(exit)" : "");
2557 print_gimple_stmt (dump_file
, at_stmt
, 0, TDF_SLIM
);
2558 fprintf (dump_file
, " is %sexecuted at most ",
2559 upper
? "" : "probably ");
2560 print_generic_expr (dump_file
, bound
, TDF_SLIM
);
2561 fprintf (dump_file
, " (bounded by ");
2562 print_decu (i_bound
, dump_file
);
2563 fprintf (dump_file
, ") + 1 times in loop %d.\n", loop
->num
);
2566 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
2567 real number of iterations. */
2568 if (TREE_CODE (bound
) != INTEGER_CST
)
2571 gcc_checking_assert (i_bound
== wi::to_widest (bound
));
2572 if (!upper
&& !realistic
)
2575 /* If we have a guaranteed upper bound, record it in the appropriate
2576 list, unless this is an !is_exit bound (i.e. undefined behavior in
2577 at_stmt) in a loop with known constant number of iterations. */
2580 || loop
->nb_iterations
== NULL_TREE
2581 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
))
2583 struct nb_iter_bound
*elt
= ggc_alloc_nb_iter_bound ();
2585 elt
->bound
= i_bound
;
2586 elt
->stmt
= at_stmt
;
2587 elt
->is_exit
= is_exit
;
2588 elt
->next
= loop
->bounds
;
2592 /* If statement is executed on every path to the loop latch, we can directly
2593 infer the upper bound on the # of iterations of the loop. */
2594 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (at_stmt
)))
2597 /* Update the number of iteration estimates according to the bound.
2598 If at_stmt is an exit then the loop latch is executed at most BOUND times,
2599 otherwise it can be executed BOUND + 1 times. We will lower the estimate
2600 later if such statement must be executed on last iteration */
2607 /* If an overflow occurred, ignore the result. */
2608 if (wi::ltu_p (i_bound
, delta
))
2611 if (upper
&& !is_exit
)
2612 do_warn_aggressive_loop_optimizations (loop
, i_bound
, at_stmt
);
2613 record_niter_bound (loop
, i_bound
, realistic
, upper
);
2616 /* Record the estimate on number of iterations of LOOP based on the fact that
2617 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
2618 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
2619 estimated number of iterations is expected to be close to the real one.
2620 UPPER is true if we are sure the induction variable does not wrap. */
2623 record_nonwrapping_iv (struct loop
*loop
, tree base
, tree step
, gimple stmt
,
2624 tree low
, tree high
, bool realistic
, bool upper
)
2626 tree niter_bound
, extreme
, delta
;
2627 tree type
= TREE_TYPE (base
), unsigned_type
;
2629 if (TREE_CODE (step
) != INTEGER_CST
|| integer_zerop (step
))
2632 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2634 fprintf (dump_file
, "Induction variable (");
2635 print_generic_expr (dump_file
, TREE_TYPE (base
), TDF_SLIM
);
2636 fprintf (dump_file
, ") ");
2637 print_generic_expr (dump_file
, base
, TDF_SLIM
);
2638 fprintf (dump_file
, " + ");
2639 print_generic_expr (dump_file
, step
, TDF_SLIM
);
2640 fprintf (dump_file
, " * iteration does not wrap in statement ");
2641 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2642 fprintf (dump_file
, " in loop %d.\n", loop
->num
);
2645 unsigned_type
= unsigned_type_for (type
);
2646 base
= fold_convert (unsigned_type
, base
);
2647 step
= fold_convert (unsigned_type
, step
);
2649 if (tree_int_cst_sign_bit (step
))
2651 extreme
= fold_convert (unsigned_type
, low
);
2652 if (TREE_CODE (base
) != INTEGER_CST
)
2653 base
= fold_convert (unsigned_type
, high
);
2654 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
2655 step
= fold_build1 (NEGATE_EXPR
, unsigned_type
, step
);
2659 extreme
= fold_convert (unsigned_type
, high
);
2660 if (TREE_CODE (base
) != INTEGER_CST
)
2661 base
= fold_convert (unsigned_type
, low
);
2662 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
2665 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
2666 would get out of the range. */
2667 niter_bound
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step
);
2668 widest_int max
= derive_constant_upper_bound (niter_bound
);
2669 record_estimate (loop
, niter_bound
, max
, stmt
, false, realistic
, upper
);
2672 /* Determine information about number of iterations a LOOP from the index
2673 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
2674 guaranteed to be executed in every iteration of LOOP. Callback for
2684 idx_infer_loop_bounds (tree base
, tree
*idx
, void *dta
)
2686 struct ilb_data
*data
= (struct ilb_data
*) dta
;
2687 tree ev
, init
, step
;
2688 tree low
, high
, type
, next
;
2689 bool sign
, upper
= true, at_end
= false;
2690 struct loop
*loop
= data
->loop
;
2691 bool reliable
= true;
2693 if (TREE_CODE (base
) != ARRAY_REF
)
2696 /* For arrays at the end of the structure, we are not guaranteed that they
2697 do not really extend over their declared size. However, for arrays of
2698 size greater than one, this is unlikely to be intended. */
2699 if (array_at_struct_end_p (base
))
2705 struct loop
*dloop
= loop_containing_stmt (data
->stmt
);
2709 ev
= analyze_scalar_evolution (dloop
, *idx
);
2710 ev
= instantiate_parameters (loop
, ev
);
2711 init
= initial_condition (ev
);
2712 step
= evolution_part_in_loop_num (ev
, loop
->num
);
2716 || TREE_CODE (step
) != INTEGER_CST
2717 || integer_zerop (step
)
2718 || tree_contains_chrecs (init
, NULL
)
2719 || chrec_contains_symbols_defined_in_loop (init
, loop
->num
))
2722 low
= array_ref_low_bound (base
);
2723 high
= array_ref_up_bound (base
);
2725 /* The case of nonconstant bounds could be handled, but it would be
2727 if (TREE_CODE (low
) != INTEGER_CST
2729 || TREE_CODE (high
) != INTEGER_CST
)
2731 sign
= tree_int_cst_sign_bit (step
);
2732 type
= TREE_TYPE (step
);
2734 /* The array of length 1 at the end of a structure most likely extends
2735 beyond its bounds. */
2737 && operand_equal_p (low
, high
, 0))
2740 /* In case the relevant bound of the array does not fit in type, or
2741 it does, but bound + step (in type) still belongs into the range of the
2742 array, the index may wrap and still stay within the range of the array
2743 (consider e.g. if the array is indexed by the full range of
2746 To make things simpler, we require both bounds to fit into type, although
2747 there are cases where this would not be strictly necessary. */
2748 if (!int_fits_type_p (high
, type
)
2749 || !int_fits_type_p (low
, type
))
2751 low
= fold_convert (type
, low
);
2752 high
= fold_convert (type
, high
);
2755 next
= fold_binary (PLUS_EXPR
, type
, low
, step
);
2757 next
= fold_binary (PLUS_EXPR
, type
, high
, step
);
2759 if (tree_int_cst_compare (low
, next
) <= 0
2760 && tree_int_cst_compare (next
, high
) <= 0)
2763 /* If access is not executed on every iteration, we must ensure that overlow may
2764 not make the access valid later. */
2765 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (data
->stmt
))
2766 && scev_probably_wraps_p (initial_condition_in_loop_num (ev
, loop
->num
),
2767 step
, data
->stmt
, loop
, true))
2770 record_nonwrapping_iv (loop
, init
, step
, data
->stmt
, low
, high
, reliable
, upper
);
2774 /* Determine information about number of iterations a LOOP from the bounds
2775 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
2776 STMT is guaranteed to be executed in every iteration of LOOP.*/
2779 infer_loop_bounds_from_ref (struct loop
*loop
, gimple stmt
, tree ref
)
2781 struct ilb_data data
;
2785 for_each_index (&ref
, idx_infer_loop_bounds
, &data
);
2788 /* Determine information about number of iterations of a LOOP from the way
2789 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
2790 executed in every iteration of LOOP. */
2793 infer_loop_bounds_from_array (struct loop
*loop
, gimple stmt
)
2795 if (is_gimple_assign (stmt
))
2797 tree op0
= gimple_assign_lhs (stmt
);
2798 tree op1
= gimple_assign_rhs1 (stmt
);
2800 /* For each memory access, analyze its access function
2801 and record a bound on the loop iteration domain. */
2802 if (REFERENCE_CLASS_P (op0
))
2803 infer_loop_bounds_from_ref (loop
, stmt
, op0
);
2805 if (REFERENCE_CLASS_P (op1
))
2806 infer_loop_bounds_from_ref (loop
, stmt
, op1
);
2808 else if (is_gimple_call (stmt
))
2811 unsigned i
, n
= gimple_call_num_args (stmt
);
2813 lhs
= gimple_call_lhs (stmt
);
2814 if (lhs
&& REFERENCE_CLASS_P (lhs
))
2815 infer_loop_bounds_from_ref (loop
, stmt
, lhs
);
2817 for (i
= 0; i
< n
; i
++)
2819 arg
= gimple_call_arg (stmt
, i
);
2820 if (REFERENCE_CLASS_P (arg
))
2821 infer_loop_bounds_from_ref (loop
, stmt
, arg
);
2826 /* Determine information about number of iterations of a LOOP from the fact
2827 that pointer arithmetics in STMT does not overflow. */
2830 infer_loop_bounds_from_pointer_arith (struct loop
*loop
, gimple stmt
)
2832 tree def
, base
, step
, scev
, type
, low
, high
;
2835 if (!is_gimple_assign (stmt
)
2836 || gimple_assign_rhs_code (stmt
) != POINTER_PLUS_EXPR
)
2839 def
= gimple_assign_lhs (stmt
);
2840 if (TREE_CODE (def
) != SSA_NAME
)
2843 type
= TREE_TYPE (def
);
2844 if (!nowrap_type_p (type
))
2847 ptr
= gimple_assign_rhs1 (stmt
);
2848 if (!expr_invariant_in_loop_p (loop
, ptr
))
2851 var
= gimple_assign_rhs2 (stmt
);
2852 if (TYPE_PRECISION (type
) != TYPE_PRECISION (TREE_TYPE (var
)))
2855 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
2856 if (chrec_contains_undetermined (scev
))
2859 base
= initial_condition_in_loop_num (scev
, loop
->num
);
2860 step
= evolution_part_in_loop_num (scev
, loop
->num
);
2863 || TREE_CODE (step
) != INTEGER_CST
2864 || tree_contains_chrecs (base
, NULL
)
2865 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
2868 low
= lower_bound_in_type (type
, type
);
2869 high
= upper_bound_in_type (type
, type
);
2871 /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
2872 produce a NULL pointer. The contrary would mean NULL points to an object,
2873 while NULL is supposed to compare unequal with the address of all objects.
2874 Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
2875 NULL pointer since that would mean wrapping, which we assume here not to
2876 happen. So, we can exclude NULL from the valid range of pointer
2878 if (flag_delete_null_pointer_checks
&& int_cst_value (low
) == 0)
2879 low
= build_int_cstu (TREE_TYPE (low
), TYPE_ALIGN_UNIT (TREE_TYPE (type
)));
2881 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
2884 /* Determine information about number of iterations of a LOOP from the fact
2885 that signed arithmetics in STMT does not overflow. */
2888 infer_loop_bounds_from_signedness (struct loop
*loop
, gimple stmt
)
2890 tree def
, base
, step
, scev
, type
, low
, high
;
2892 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2895 def
= gimple_assign_lhs (stmt
);
2897 if (TREE_CODE (def
) != SSA_NAME
)
2900 type
= TREE_TYPE (def
);
2901 if (!INTEGRAL_TYPE_P (type
)
2902 || !TYPE_OVERFLOW_UNDEFINED (type
))
2905 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
2906 if (chrec_contains_undetermined (scev
))
2909 base
= initial_condition_in_loop_num (scev
, loop
->num
);
2910 step
= evolution_part_in_loop_num (scev
, loop
->num
);
2913 || TREE_CODE (step
) != INTEGER_CST
2914 || tree_contains_chrecs (base
, NULL
)
2915 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
2918 low
= lower_bound_in_type (type
, type
);
2919 high
= upper_bound_in_type (type
, type
);
2921 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
2924 /* The following analyzers are extracting informations on the bounds
2925 of LOOP from the following undefined behaviors:
2927 - data references should not access elements over the statically
2930 - signed variables should not overflow when flag_wrapv is not set.
2934 infer_loop_bounds_from_undefined (struct loop
*loop
)
2938 gimple_stmt_iterator bsi
;
2942 bbs
= get_loop_body (loop
);
2944 for (i
= 0; i
< loop
->num_nodes
; i
++)
2948 /* If BB is not executed in each iteration of the loop, we cannot
2949 use the operations in it to infer reliable upper bound on the
2950 # of iterations of the loop. However, we can use it as a guess.
2951 Reliable guesses come only from array bounds. */
2952 reliable
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
);
2954 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2956 gimple stmt
= gsi_stmt (bsi
);
2958 infer_loop_bounds_from_array (loop
, stmt
);
2962 infer_loop_bounds_from_signedness (loop
, stmt
);
2963 infer_loop_bounds_from_pointer_arith (loop
, stmt
);
2972 /* Compare wide ints, callback for qsort. */
2975 wide_int_cmp (const void *p1
, const void *p2
)
2977 const widest_int
*d1
= (const widest_int
*) p1
;
2978 const widest_int
*d2
= (const widest_int
*) p2
;
2979 return wi::cmpu (*d1
, *d2
);
2982 /* Return index of BOUND in BOUNDS array sorted in increasing order.
2983 Lookup by binary search. */
2986 bound_index (vec
<widest_int
> bounds
, const widest_int
&bound
)
2988 unsigned int end
= bounds
.length ();
2989 unsigned int begin
= 0;
2991 /* Find a matching index by means of a binary search. */
2992 while (begin
!= end
)
2994 unsigned int middle
= (begin
+ end
) / 2;
2995 widest_int index
= bounds
[middle
];
2999 else if (wi::ltu_p (index
, bound
))
3007 /* We recorded loop bounds only for statements dominating loop latch (and thus
3008 executed each loop iteration). If there are any bounds on statements not
3009 dominating the loop latch we can improve the estimate by walking the loop
3010 body and seeing if every path from loop header to loop latch contains
3011 some bounded statement. */
3014 discover_iteration_bound_by_body_walk (struct loop
*loop
)
3016 pointer_map_t
*bb_bounds
;
3017 struct nb_iter_bound
*elt
;
3018 vec
<widest_int
> bounds
= vNULL
;
3019 vec
<vec
<basic_block
> > queues
= vNULL
;
3020 vec
<basic_block
> queue
= vNULL
;
3021 ptrdiff_t queue_index
;
3022 ptrdiff_t latch_index
= 0;
3023 pointer_map_t
*block_priority
;
3025 /* Discover what bounds may interest us. */
3026 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3028 widest_int bound
= elt
->bound
;
3030 /* Exit terminates loop at given iteration, while non-exits produce undefined
3031 effect on the next iteration. */
3035 /* If an overflow occurred, ignore the result. */
3040 if (!loop
->any_upper_bound
3041 || wi::ltu_p (bound
, loop
->nb_iterations_upper_bound
))
3042 bounds
.safe_push (bound
);
3045 /* Exit early if there is nothing to do. */
3046 if (!bounds
.exists ())
3049 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3050 fprintf (dump_file
, " Trying to walk loop body to reduce the bound.\n");
3052 /* Sort the bounds in decreasing order. */
3053 qsort (bounds
.address (), bounds
.length (),
3054 sizeof (widest_int
), wide_int_cmp
);
3056 /* For every basic block record the lowest bound that is guaranteed to
3057 terminate the loop. */
3059 bb_bounds
= pointer_map_create ();
3060 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3062 widest_int bound
= elt
->bound
;
3066 /* If an overflow occurred, ignore the result. */
3071 if (!loop
->any_upper_bound
3072 || wi::ltu_p (bound
, loop
->nb_iterations_upper_bound
))
3074 ptrdiff_t index
= bound_index (bounds
, bound
);
3075 void **entry
= pointer_map_contains (bb_bounds
,
3076 gimple_bb (elt
->stmt
));
3078 *pointer_map_insert (bb_bounds
,
3079 gimple_bb (elt
->stmt
)) = (void *)index
;
3080 else if ((ptrdiff_t)*entry
> index
)
3081 *entry
= (void *)index
;
3085 block_priority
= pointer_map_create ();
3087 /* Perform shortest path discovery loop->header ... loop->latch.
3089 The "distance" is given by the smallest loop bound of basic block
3090 present in the path and we look for path with largest smallest bound
3093 To avoid the need for fibonacci heap on double ints we simply compress
3094 double ints into indexes to BOUNDS array and then represent the queue
3095 as arrays of queues for every index.
3096 Index of BOUNDS.length() means that the execution of given BB has
3097 no bounds determined.
3099 VISITED is a pointer map translating basic block into smallest index
3100 it was inserted into the priority queue with. */
3103 /* Start walk in loop header with index set to infinite bound. */
3104 queue_index
= bounds
.length ();
3105 queues
.safe_grow_cleared (queue_index
+ 1);
3106 queue
.safe_push (loop
->header
);
3107 queues
[queue_index
] = queue
;
3108 *pointer_map_insert (block_priority
, loop
->header
) = (void *)queue_index
;
3110 for (; queue_index
>= 0; queue_index
--)
3112 if (latch_index
< queue_index
)
3114 while (queues
[queue_index
].length ())
3117 ptrdiff_t bound_index
= queue_index
;
3122 queue
= queues
[queue_index
];
3125 /* OK, we later inserted the BB with lower priority, skip it. */
3126 if ((ptrdiff_t)*pointer_map_contains (block_priority
, bb
) > queue_index
)
3129 /* See if we can improve the bound. */
3130 entry
= pointer_map_contains (bb_bounds
, bb
);
3131 if (entry
&& (ptrdiff_t)*entry
< bound_index
)
3132 bound_index
= (ptrdiff_t)*entry
;
3134 /* Insert succesors into the queue, watch for latch edge
3135 and record greatest index we saw. */
3136 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3138 bool insert
= false;
3141 if (loop_exit_edge_p (loop
, e
))
3144 if (e
== loop_latch_edge (loop
)
3145 && latch_index
< bound_index
)
3146 latch_index
= bound_index
;
3147 else if (!(entry
= pointer_map_contains (block_priority
, e
->dest
)))
3150 *pointer_map_insert (block_priority
, e
->dest
) = (void *)bound_index
;
3152 else if ((ptrdiff_t)*entry
< bound_index
)
3155 *entry
= (void *)bound_index
;
3159 queues
[bound_index
].safe_push (e
->dest
);
3163 queues
[queue_index
].release ();
3166 gcc_assert (latch_index
>= 0);
3167 if ((unsigned)latch_index
< bounds
.length ())
3169 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3171 fprintf (dump_file
, "Found better loop bound ");
3172 print_decu (bounds
[latch_index
], dump_file
);
3173 fprintf (dump_file
, "\n");
3175 record_niter_bound (loop
, bounds
[latch_index
], false, true);
3180 pointer_map_destroy (bb_bounds
);
3181 pointer_map_destroy (block_priority
);
3184 /* See if every path cross the loop goes through a statement that is known
3185 to not execute at the last iteration. In that case we can decrese iteration
3189 maybe_lower_iteration_bound (struct loop
*loop
)
3191 pointer_set_t
*not_executed_last_iteration
= NULL
;
3192 struct nb_iter_bound
*elt
;
3193 bool found_exit
= false;
3194 vec
<basic_block
> queue
= vNULL
;
3197 /* Collect all statements with interesting (i.e. lower than
3198 nb_iterations_upper_bound) bound on them.
3200 TODO: Due to the way record_estimate choose estimates to store, the bounds
3201 will be always nb_iterations_upper_bound-1. We can change this to record
3202 also statements not dominating the loop latch and update the walk bellow
3203 to the shortest path algorthm. */
3204 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3207 && wi::ltu_p (elt
->bound
, loop
->nb_iterations_upper_bound
))
3209 if (!not_executed_last_iteration
)
3210 not_executed_last_iteration
= pointer_set_create ();
3211 pointer_set_insert (not_executed_last_iteration
, elt
->stmt
);
3214 if (!not_executed_last_iteration
)
3217 /* Start DFS walk in the loop header and see if we can reach the
3218 loop latch or any of the exits (including statements with side
3219 effects that may terminate the loop otherwise) without visiting
3220 any of the statements known to have undefined effect on the last
3222 queue
.safe_push (loop
->header
);
3223 visited
= BITMAP_ALLOC (NULL
);
3224 bitmap_set_bit (visited
, loop
->header
->index
);
3229 basic_block bb
= queue
.pop ();
3230 gimple_stmt_iterator gsi
;
3231 bool stmt_found
= false;
3233 /* Loop for possible exits and statements bounding the execution. */
3234 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3236 gimple stmt
= gsi_stmt (gsi
);
3237 if (pointer_set_contains (not_executed_last_iteration
, stmt
))
3242 if (gimple_has_side_effects (stmt
))
3251 /* If no bounding statement is found, continue the walk. */
3257 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3259 if (loop_exit_edge_p (loop
, e
)
3260 || e
== loop_latch_edge (loop
))
3265 if (bitmap_set_bit (visited
, e
->dest
->index
))
3266 queue
.safe_push (e
->dest
);
3270 while (queue
.length () && !found_exit
);
3272 /* If every path through the loop reach bounding statement before exit,
3273 then we know the last iteration of the loop will have undefined effect
3274 and we can decrease number of iterations. */
3278 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3279 fprintf (dump_file
, "Reducing loop iteration estimate by 1; "
3280 "undefined statement must be executed at the last iteration.\n");
3281 record_niter_bound (loop
, loop
->nb_iterations_upper_bound
- 1,
3284 BITMAP_FREE (visited
);
3286 pointer_set_destroy (not_executed_last_iteration
);
3289 /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
3290 is true also use estimates derived from undefined behavior. */
3293 estimate_numbers_of_iterations_loop (struct loop
*loop
)
3298 struct tree_niter_desc niter_desc
;
3303 /* Give up if we already have tried to compute an estimation. */
3304 if (loop
->estimate_state
!= EST_NOT_COMPUTED
)
3307 loop
->estimate_state
= EST_AVAILABLE
;
3308 /* Force estimate compuation but leave any existing upper bound in place. */
3309 loop
->any_estimate
= false;
3311 /* Ensure that loop->nb_iterations is computed if possible. If it turns out
3312 to be constant, we avoid undefined behavior implied bounds and instead
3313 diagnose those loops with -Waggressive-loop-optimizations. */
3314 number_of_latch_executions (loop
);
3316 exits
= get_loop_exit_edges (loop
);
3317 likely_exit
= single_likely_exit (loop
);
3318 FOR_EACH_VEC_ELT (exits
, i
, ex
)
3320 if (!number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
3323 niter
= niter_desc
.niter
;
3324 type
= TREE_TYPE (niter
);
3325 if (TREE_CODE (niter_desc
.may_be_zero
) != INTEGER_CST
)
3326 niter
= build3 (COND_EXPR
, type
, niter_desc
.may_be_zero
,
3327 build_int_cst (type
, 0),
3329 record_estimate (loop
, niter
, niter_desc
.max
,
3330 last_stmt (ex
->src
),
3331 true, ex
== likely_exit
, true);
3335 if (flag_aggressive_loop_optimizations
)
3336 infer_loop_bounds_from_undefined (loop
);
3338 discover_iteration_bound_by_body_walk (loop
);
3340 maybe_lower_iteration_bound (loop
);
3342 /* If we have a measured profile, use it to estimate the number of
3344 if (loop
->header
->count
!= 0)
3346 gcov_type nit
= expected_loop_iterations_unbounded (loop
) + 1;
3347 bound
= gcov_type_to_wide_int (nit
);
3348 record_niter_bound (loop
, bound
, true, false);
3351 /* If we know the exact number of iterations of this loop, try to
3352 not break code with undefined behavior by not recording smaller
3353 maximum number of iterations. */
3354 if (loop
->nb_iterations
3355 && TREE_CODE (loop
->nb_iterations
) == INTEGER_CST
)
3357 loop
->any_upper_bound
= true;
3358 loop
->nb_iterations_upper_bound
= wi::to_widest (loop
->nb_iterations
);
3362 /* Sets NIT to the estimated number of executions of the latch of the
3363 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
3364 large as the number of iterations. If we have no reliable estimate,
3365 the function returns false, otherwise returns true. */
3368 estimated_loop_iterations (struct loop
*loop
, widest_int
*nit
)
3370 /* When SCEV information is available, try to update loop iterations
3371 estimate. Otherwise just return whatever we recorded earlier. */
3372 if (scev_initialized_p ())
3373 estimate_numbers_of_iterations_loop (loop
);
3375 return (get_estimated_loop_iterations (loop
, nit
));
3378 /* Similar to estimated_loop_iterations, but returns the estimate only
3379 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3380 on the number of iterations of LOOP could not be derived, returns -1. */
3383 estimated_loop_iterations_int (struct loop
*loop
)
3386 HOST_WIDE_INT hwi_nit
;
3388 if (!estimated_loop_iterations (loop
, &nit
))
3391 if (!wi::fits_shwi_p (nit
))
3393 hwi_nit
= nit
.to_shwi ();
3395 return hwi_nit
< 0 ? -1 : hwi_nit
;
3399 /* Sets NIT to an upper bound for the maximum number of executions of the
3400 latch of the LOOP. If we have no reliable estimate, the function returns
3401 false, otherwise returns true. */
3404 max_loop_iterations (struct loop
*loop
, widest_int
*nit
)
3406 /* When SCEV information is available, try to update loop iterations
3407 estimate. Otherwise just return whatever we recorded earlier. */
3408 if (scev_initialized_p ())
3409 estimate_numbers_of_iterations_loop (loop
);
3411 return get_max_loop_iterations (loop
, nit
);
3414 /* Similar to max_loop_iterations, but returns the estimate only
3415 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3416 on the number of iterations of LOOP could not be derived, returns -1. */
3419 max_loop_iterations_int (struct loop
*loop
)
3422 HOST_WIDE_INT hwi_nit
;
3424 if (!max_loop_iterations (loop
, &nit
))
3427 if (!wi::fits_shwi_p (nit
))
3429 hwi_nit
= nit
.to_shwi ();
3431 return hwi_nit
< 0 ? -1 : hwi_nit
;
3434 /* Returns an estimate for the number of executions of statements
3435 in the LOOP. For statements before the loop exit, this exceeds
3436 the number of execution of the latch by one. */
3439 estimated_stmt_executions_int (struct loop
*loop
)
3441 HOST_WIDE_INT nit
= estimated_loop_iterations_int (loop
);
3447 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
3449 /* If the computation overflows, return -1. */
3450 return snit
< 0 ? -1 : snit
;
3453 /* Sets NIT to the estimated maximum number of executions of the latch of the
3454 LOOP, plus one. If we have no reliable estimate, the function returns
3455 false, otherwise returns true. */
3458 max_stmt_executions (struct loop
*loop
, widest_int
*nit
)
3460 widest_int nit_minus_one
;
3462 if (!max_loop_iterations (loop
, nit
))
3465 nit_minus_one
= *nit
;
3469 return wi::gtu_p (*nit
, nit_minus_one
);
3472 /* Sets NIT to the estimated number of executions of the latch of the
3473 LOOP, plus one. If we have no reliable estimate, the function returns
3474 false, otherwise returns true. */
3477 estimated_stmt_executions (struct loop
*loop
, widest_int
*nit
)
3479 widest_int nit_minus_one
;
3481 if (!estimated_loop_iterations (loop
, nit
))
3484 nit_minus_one
= *nit
;
3488 return wi::gtu_p (*nit
, nit_minus_one
);
3491 /* Records estimates on numbers of iterations of loops. */
3494 estimate_numbers_of_iterations (void)
3499 /* We don't want to issue signed overflow warnings while getting
3500 loop iteration estimates. */
3501 fold_defer_overflow_warnings ();
3503 FOR_EACH_LOOP (li
, loop
, 0)
3505 estimate_numbers_of_iterations_loop (loop
);
3508 fold_undefer_and_ignore_overflow_warnings ();
3511 /* Returns true if statement S1 dominates statement S2. */
3514 stmt_dominates_stmt_p (gimple s1
, gimple s2
)
3516 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
3524 gimple_stmt_iterator bsi
;
3526 if (gimple_code (s2
) == GIMPLE_PHI
)
3529 if (gimple_code (s1
) == GIMPLE_PHI
)
3532 for (bsi
= gsi_start_bb (bb1
); gsi_stmt (bsi
) != s2
; gsi_next (&bsi
))
3533 if (gsi_stmt (bsi
) == s1
)
3539 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
3542 /* Returns true when we can prove that the number of executions of
3543 STMT in the loop is at most NITER, according to the bound on
3544 the number of executions of the statement NITER_BOUND->stmt recorded in
3545 NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT.
3547 ??? This code can become quite a CPU hog - we can have many bounds,
3548 and large basic block forcing stmt_dominates_stmt_p to be queried
3549 many times on a large basic blocks, so the whole thing is O(n^2)
3550 for scev_probably_wraps_p invocation (that can be done n times).
3552 It would make more sense (and give better answers) to remember BB
3553 bounds computed by discover_iteration_bound_by_body_walk. */
3556 n_of_executions_at_most (gimple stmt
,
3557 struct nb_iter_bound
*niter_bound
,
3560 widest_int bound
= niter_bound
->bound
;
3561 tree nit_type
= TREE_TYPE (niter
), e
;
3564 gcc_assert (TYPE_UNSIGNED (nit_type
));
3566 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
3567 the number of iterations is small. */
3568 if (!wi::fits_to_tree_p (bound
, nit_type
))
3571 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3572 times. This means that:
3574 -- if NITER_BOUND->is_exit is true, then everything after
3575 it at most NITER_BOUND->bound times.
3577 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
3578 is executed, then NITER_BOUND->stmt is executed as well in the same
3579 iteration then STMT is executed at most NITER_BOUND->bound + 1 times.
3581 If we can determine that NITER_BOUND->stmt is always executed
3582 after STMT, then STMT is executed at most NITER_BOUND->bound + 2 times.
3583 We conclude that if both statements belong to the same
3584 basic block and STMT is before NITER_BOUND->stmt and there are no
3585 statements with side effects in between. */
3587 if (niter_bound
->is_exit
)
3589 if (stmt
== niter_bound
->stmt
3590 || !stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
3596 if (!stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
3598 gimple_stmt_iterator bsi
;
3599 if (gimple_bb (stmt
) != gimple_bb (niter_bound
->stmt
)
3600 || gimple_code (stmt
) == GIMPLE_PHI
3601 || gimple_code (niter_bound
->stmt
) == GIMPLE_PHI
)
3604 /* By stmt_dominates_stmt_p we already know that STMT appears
3605 before NITER_BOUND->STMT. Still need to test that the loop
3606 can not be terinated by a side effect in between. */
3607 for (bsi
= gsi_for_stmt (stmt
); gsi_stmt (bsi
) != niter_bound
->stmt
;
3609 if (gimple_has_side_effects (gsi_stmt (bsi
)))
3613 || !wi::fits_to_tree_p (bound
, nit_type
))
3619 e
= fold_binary (cmp
, boolean_type_node
,
3620 niter
, wide_int_to_tree (nit_type
, bound
));
3621 return e
&& integer_nonzerop (e
);
3624 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
3627 nowrap_type_p (tree type
)
3629 if (INTEGRAL_TYPE_P (type
)
3630 && TYPE_OVERFLOW_UNDEFINED (type
))
3633 if (POINTER_TYPE_P (type
))
3639 /* Return false only when the induction variable BASE + STEP * I is
3640 known to not overflow: i.e. when the number of iterations is small
3641 enough with respect to the step and initial condition in order to
3642 keep the evolution confined in TYPEs bounds. Return true when the
3643 iv is known to overflow or when the property is not computable.
3645 USE_OVERFLOW_SEMANTICS is true if this function should assume that
3646 the rules for overflow of the given language apply (e.g., that signed
3647 arithmetics in C does not overflow). */
3650 scev_probably_wraps_p (tree base
, tree step
,
3651 gimple at_stmt
, struct loop
*loop
,
3652 bool use_overflow_semantics
)
3654 tree delta
, step_abs
;
3655 tree unsigned_type
, valid_niter
;
3656 tree type
= TREE_TYPE (step
);
3659 struct nb_iter_bound
*bound
;
3661 /* FIXME: We really need something like
3662 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
3664 We used to test for the following situation that frequently appears
3665 during address arithmetics:
3667 D.1621_13 = (long unsigned intD.4) D.1620_12;
3668 D.1622_14 = D.1621_13 * 8;
3669 D.1623_15 = (doubleD.29 *) D.1622_14;
3671 And derived that the sequence corresponding to D_14
3672 can be proved to not wrap because it is used for computing a
3673 memory access; however, this is not really the case -- for example,
3674 if D_12 = (unsigned char) [254,+,1], then D_14 has values
3675 2032, 2040, 0, 8, ..., but the code is still legal. */
3677 if (chrec_contains_undetermined (base
)
3678 || chrec_contains_undetermined (step
))
3681 if (integer_zerop (step
))
3684 /* If we can use the fact that signed and pointer arithmetics does not
3685 wrap, we are done. */
3686 if (use_overflow_semantics
&& nowrap_type_p (TREE_TYPE (base
)))
3689 /* To be able to use estimates on number of iterations of the loop,
3690 we must have an upper bound on the absolute value of the step. */
3691 if (TREE_CODE (step
) != INTEGER_CST
)
3694 /* Don't issue signed overflow warnings. */
3695 fold_defer_overflow_warnings ();
3697 /* Otherwise, compute the number of iterations before we reach the
3698 bound of the type, and verify that the loop is exited before this
3700 unsigned_type
= unsigned_type_for (type
);
3701 base
= fold_convert (unsigned_type
, base
);
3703 if (tree_int_cst_sign_bit (step
))
3705 tree extreme
= fold_convert (unsigned_type
,
3706 lower_bound_in_type (type
, type
));
3707 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
3708 step_abs
= fold_build1 (NEGATE_EXPR
, unsigned_type
,
3709 fold_convert (unsigned_type
, step
));
3713 tree extreme
= fold_convert (unsigned_type
,
3714 upper_bound_in_type (type
, type
));
3715 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
3716 step_abs
= fold_convert (unsigned_type
, step
);
3719 valid_niter
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step_abs
);
3721 estimate_numbers_of_iterations_loop (loop
);
3723 if (max_loop_iterations (loop
, &niter
)
3724 && wi::fits_to_tree_p (niter
, TREE_TYPE (valid_niter
))
3725 && (e
= fold_binary (GT_EXPR
, boolean_type_node
, valid_niter
,
3726 wide_int_to_tree (TREE_TYPE (valid_niter
),
3728 && integer_nonzerop (e
))
3730 fold_undefer_and_ignore_overflow_warnings ();
3734 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
3736 if (n_of_executions_at_most (at_stmt
, bound
, valid_niter
))
3738 fold_undefer_and_ignore_overflow_warnings ();
3743 fold_undefer_and_ignore_overflow_warnings ();
3745 /* At this point we still don't have a proof that the iv does not
3746 overflow: give up. */
3750 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
3753 free_numbers_of_iterations_estimates_loop (struct loop
*loop
)
3755 struct nb_iter_bound
*bound
, *next
;
3757 loop
->nb_iterations
= NULL
;
3758 loop
->estimate_state
= EST_NOT_COMPUTED
;
3759 for (bound
= loop
->bounds
; bound
; bound
= next
)
3765 loop
->bounds
= NULL
;
3768 /* Frees the information on upper bounds on numbers of iterations of loops. */
3771 free_numbers_of_iterations_estimates (void)
3776 FOR_EACH_LOOP (li
, loop
, 0)
3778 free_numbers_of_iterations_estimates_loop (loop
);
3782 /* Substitute value VAL for ssa name NAME inside expressions held
3786 substitute_in_loop_info (struct loop
*loop
, tree name
, tree val
)
3788 loop
->nb_iterations
= simplify_replace_tree (loop
->nb_iterations
, name
, val
);