1 /* Functions to determine/estimate number of iterations of a loop.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
27 #include "basic-block.h"
28 #include "tree-pretty-print.h"
29 #include "gimple-pretty-print.h"
31 #include "tree-flow.h"
32 #include "tree-dump.h"
34 #include "tree-pass.h"
36 #include "tree-chrec.h"
37 #include "tree-scalar-evolution.h"
38 #include "tree-data-ref.h"
41 #include "diagnostic-core.h"
42 #include "tree-inline.h"
45 #define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
47 /* The maximum number of dominator BBs we search for conditions
48 of loop header copies we use for simplifying a conditional
50 #define MAX_DOMINATORS_TO_WALK 8
54 Analysis of number of iterations of an affine exit test.
58 /* Bounds on some value, BELOW <= X <= UP. */
66 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */
69 split_to_var_and_offset (tree expr
, tree
*var
, mpz_t offset
)
71 tree type
= TREE_TYPE (expr
);
77 mpz_set_ui (offset
, 0);
79 switch (TREE_CODE (expr
))
86 case POINTER_PLUS_EXPR
:
87 op0
= TREE_OPERAND (expr
, 0);
88 op1
= TREE_OPERAND (expr
, 1);
90 if (TREE_CODE (op1
) != INTEGER_CST
)
94 /* Always sign extend the offset. */
95 off
= tree_to_double_int (op1
);
96 off
= double_int_sext (off
, TYPE_PRECISION (type
));
97 mpz_set_double_int (offset
, off
, false);
99 mpz_neg (offset
, offset
);
103 *var
= build_int_cst_type (type
, 0);
104 off
= tree_to_double_int (expr
);
105 mpz_set_double_int (offset
, off
, TYPE_UNSIGNED (type
));
113 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
114 in TYPE to MIN and MAX. */
117 determine_value_range (tree type
, tree var
, mpz_t off
,
118 mpz_t min
, mpz_t max
)
120 /* If the expression is a constant, we know its value exactly. */
121 if (integer_zerop (var
))
128 /* If the computation may wrap, we know nothing about the value, except for
129 the range of the type. */
130 get_type_static_bounds (type
, min
, max
);
131 if (!nowrap_type_p (type
))
134 /* Since the addition of OFF does not wrap, if OFF is positive, then we may
135 add it to MIN, otherwise to MAX. */
136 if (mpz_sgn (off
) < 0)
137 mpz_add (max
, max
, off
);
139 mpz_add (min
, min
, off
);
142 /* Stores the bounds on the difference of the values of the expressions
143 (var + X) and (var + Y), computed in TYPE, to BNDS. */
146 bound_difference_of_offsetted_base (tree type
, mpz_t x
, mpz_t y
,
149 int rel
= mpz_cmp (x
, y
);
150 bool may_wrap
= !nowrap_type_p (type
);
153 /* If X == Y, then the expressions are always equal.
154 If X > Y, there are the following possibilities:
155 a) neither of var + X and var + Y overflow or underflow, or both of
156 them do. Then their difference is X - Y.
157 b) var + X overflows, and var + Y does not. Then the values of the
158 expressions are var + X - M and var + Y, where M is the range of
159 the type, and their difference is X - Y - M.
160 c) var + Y underflows and var + X does not. Their difference again
162 Therefore, if the arithmetics in type does not overflow, then the
163 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
164 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
165 (X - Y, X - Y + M). */
169 mpz_set_ui (bnds
->below
, 0);
170 mpz_set_ui (bnds
->up
, 0);
175 mpz_set_double_int (m
, double_int_mask (TYPE_PRECISION (type
)), true);
176 mpz_add_ui (m
, m
, 1);
177 mpz_sub (bnds
->up
, x
, y
);
178 mpz_set (bnds
->below
, bnds
->up
);
183 mpz_sub (bnds
->below
, bnds
->below
, m
);
185 mpz_add (bnds
->up
, bnds
->up
, m
);
191 /* From condition C0 CMP C1 derives information regarding the
192 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
193 and stores it to BNDS. */
196 refine_bounds_using_guard (tree type
, tree varx
, mpz_t offx
,
197 tree vary
, mpz_t offy
,
198 tree c0
, enum tree_code cmp
, tree c1
,
201 tree varc0
, varc1
, tmp
, ctype
;
202 mpz_t offc0
, offc1
, loffx
, loffy
, bnd
;
204 bool no_wrap
= nowrap_type_p (type
);
213 STRIP_SIGN_NOPS (c0
);
214 STRIP_SIGN_NOPS (c1
);
215 ctype
= TREE_TYPE (c0
);
216 if (!useless_type_conversion_p (ctype
, type
))
222 /* We could derive quite precise information from EQ_EXPR, however, such
223 a guard is unlikely to appear, so we do not bother with handling
228 /* NE_EXPR comparisons do not contain much of useful information, except for
229 special case of comparing with the bounds of the type. */
230 if (TREE_CODE (c1
) != INTEGER_CST
231 || !INTEGRAL_TYPE_P (type
))
234 /* Ensure that the condition speaks about an expression in the same type
236 ctype
= TREE_TYPE (c0
);
237 if (TYPE_PRECISION (ctype
) != TYPE_PRECISION (type
))
239 c0
= fold_convert (type
, c0
);
240 c1
= fold_convert (type
, c1
);
242 if (TYPE_MIN_VALUE (type
)
243 && operand_equal_p (c1
, TYPE_MIN_VALUE (type
), 0))
248 if (TYPE_MAX_VALUE (type
)
249 && operand_equal_p (c1
, TYPE_MAX_VALUE (type
), 0))
262 split_to_var_and_offset (expand_simple_operations (c0
), &varc0
, offc0
);
263 split_to_var_and_offset (expand_simple_operations (c1
), &varc1
, offc1
);
265 /* We are only interested in comparisons of expressions based on VARX and
266 VARY. TODO -- we might also be able to derive some bounds from
267 expressions containing just one of the variables. */
269 if (operand_equal_p (varx
, varc1
, 0))
271 tmp
= varc0
; varc0
= varc1
; varc1
= tmp
;
272 mpz_swap (offc0
, offc1
);
273 cmp
= swap_tree_comparison (cmp
);
276 if (!operand_equal_p (varx
, varc0
, 0)
277 || !operand_equal_p (vary
, varc1
, 0))
280 mpz_init_set (loffx
, offx
);
281 mpz_init_set (loffy
, offy
);
283 if (cmp
== GT_EXPR
|| cmp
== GE_EXPR
)
285 tmp
= varx
; varx
= vary
; vary
= tmp
;
286 mpz_swap (offc0
, offc1
);
287 mpz_swap (loffx
, loffy
);
288 cmp
= swap_tree_comparison (cmp
);
292 /* If there is no overflow, the condition implies that
294 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
296 The overflows and underflows may complicate things a bit; each
297 overflow decreases the appropriate offset by M, and underflow
298 increases it by M. The above inequality would not necessarily be
301 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
302 VARX + OFFC0 overflows, but VARX + OFFX does not.
303 This may only happen if OFFX < OFFC0.
304 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
305 VARY + OFFC1 underflows and VARY + OFFY does not.
306 This may only happen if OFFY > OFFC1. */
315 x_ok
= (integer_zerop (varx
)
316 || mpz_cmp (loffx
, offc0
) >= 0);
317 y_ok
= (integer_zerop (vary
)
318 || mpz_cmp (loffy
, offc1
) <= 0);
324 mpz_sub (bnd
, loffx
, loffy
);
325 mpz_add (bnd
, bnd
, offc1
);
326 mpz_sub (bnd
, bnd
, offc0
);
329 mpz_sub_ui (bnd
, bnd
, 1);
334 if (mpz_cmp (bnds
->below
, bnd
) < 0)
335 mpz_set (bnds
->below
, bnd
);
339 if (mpz_cmp (bnd
, bnds
->up
) < 0)
340 mpz_set (bnds
->up
, bnd
);
352 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
353 The subtraction is considered to be performed in arbitrary precision,
356 We do not attempt to be too clever regarding the value ranges of X and
357 Y; most of the time, they are just integers or ssa names offsetted by
358 integer. However, we try to use the information contained in the
359 comparisons before the loop (usually created by loop header copying). */
362 bound_difference (struct loop
*loop
, tree x
, tree y
, bounds
*bnds
)
364 tree type
= TREE_TYPE (x
);
367 mpz_t minx
, maxx
, miny
, maxy
;
375 /* Get rid of unnecessary casts, but preserve the value of
380 mpz_init (bnds
->below
);
384 split_to_var_and_offset (x
, &varx
, offx
);
385 split_to_var_and_offset (y
, &vary
, offy
);
387 if (!integer_zerop (varx
)
388 && operand_equal_p (varx
, vary
, 0))
390 /* Special case VARX == VARY -- we just need to compare the
391 offsets. The matters are a bit more complicated in the
392 case addition of offsets may wrap. */
393 bound_difference_of_offsetted_base (type
, offx
, offy
, bnds
);
397 /* Otherwise, use the value ranges to determine the initial
398 estimates on below and up. */
403 determine_value_range (type
, varx
, offx
, minx
, maxx
);
404 determine_value_range (type
, vary
, offy
, miny
, maxy
);
406 mpz_sub (bnds
->below
, minx
, maxy
);
407 mpz_sub (bnds
->up
, maxx
, miny
);
414 /* If both X and Y are constants, we cannot get any more precise. */
415 if (integer_zerop (varx
) && integer_zerop (vary
))
418 /* Now walk the dominators of the loop header and use the entry
419 guards to refine the estimates. */
420 for (bb
= loop
->header
;
421 bb
!= ENTRY_BLOCK_PTR
&& cnt
< MAX_DOMINATORS_TO_WALK
;
422 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
424 if (!single_pred_p (bb
))
426 e
= single_pred_edge (bb
);
428 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
431 cond
= last_stmt (e
->src
);
432 c0
= gimple_cond_lhs (cond
);
433 cmp
= gimple_cond_code (cond
);
434 c1
= gimple_cond_rhs (cond
);
436 if (e
->flags
& EDGE_FALSE_VALUE
)
437 cmp
= invert_tree_comparison (cmp
, false);
439 refine_bounds_using_guard (type
, varx
, offx
, vary
, offy
,
449 /* Update the bounds in BNDS that restrict the value of X to the bounds
450 that restrict the value of X + DELTA. X can be obtained as a
451 difference of two values in TYPE. */
454 bounds_add (bounds
*bnds
, double_int delta
, tree type
)
459 mpz_set_double_int (mdelta
, delta
, false);
462 mpz_set_double_int (max
, double_int_mask (TYPE_PRECISION (type
)), true);
464 mpz_add (bnds
->up
, bnds
->up
, mdelta
);
465 mpz_add (bnds
->below
, bnds
->below
, mdelta
);
467 if (mpz_cmp (bnds
->up
, max
) > 0)
468 mpz_set (bnds
->up
, max
);
471 if (mpz_cmp (bnds
->below
, max
) < 0)
472 mpz_set (bnds
->below
, max
);
478 /* Update the bounds in BNDS that restrict the value of X to the bounds
479 that restrict the value of -X. */
482 bounds_negate (bounds
*bnds
)
486 mpz_init_set (tmp
, bnds
->up
);
487 mpz_neg (bnds
->up
, bnds
->below
);
488 mpz_neg (bnds
->below
, tmp
);
492 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
495 inverse (tree x
, tree mask
)
497 tree type
= TREE_TYPE (x
);
499 unsigned ctr
= tree_floor_log2 (mask
);
501 if (TYPE_PRECISION (type
) <= HOST_BITS_PER_WIDE_INT
)
503 unsigned HOST_WIDE_INT ix
;
504 unsigned HOST_WIDE_INT imask
;
505 unsigned HOST_WIDE_INT irslt
= 1;
507 gcc_assert (cst_and_fits_in_hwi (x
));
508 gcc_assert (cst_and_fits_in_hwi (mask
));
510 ix
= int_cst_value (x
);
511 imask
= int_cst_value (mask
);
520 rslt
= build_int_cst_type (type
, irslt
);
524 rslt
= build_int_cst (type
, 1);
527 rslt
= int_const_binop (MULT_EXPR
, rslt
, x
);
528 x
= int_const_binop (MULT_EXPR
, x
, x
);
530 rslt
= int_const_binop (BIT_AND_EXPR
, rslt
, mask
);
536 /* Derives the upper bound BND on the number of executions of loop with exit
537 condition S * i <> C. If NO_OVERFLOW is true, then the control variable of
538 the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed
539 that the loop ends through this exit, i.e., the induction variable ever
540 reaches the value of C.
542 The value C is equal to final - base, where final and base are the final and
543 initial value of the actual induction variable in the analysed loop. BNDS
544 bounds the value of this difference when computed in signed type with
545 unbounded range, while the computation of C is performed in an unsigned
546 type with the range matching the range of the type of the induction variable.
547 In particular, BNDS.up contains an upper bound on C in the following cases:
548 -- if the iv must reach its final value without overflow, i.e., if
549 NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
550 -- if final >= base, which we know to hold when BNDS.below >= 0. */
553 number_of_iterations_ne_max (mpz_t bnd
, bool no_overflow
, tree c
, tree s
,
554 bounds
*bnds
, bool exit_must_be_taken
)
558 bool bnds_u_valid
= ((no_overflow
&& exit_must_be_taken
)
559 || mpz_sgn (bnds
->below
) >= 0);
561 if (multiple_of_p (TREE_TYPE (c
), c
, s
))
563 /* If C is an exact multiple of S, then its value will be reached before
564 the induction variable overflows (unless the loop is exited in some
565 other way before). Note that the actual induction variable in the
566 loop (which ranges from base to final instead of from 0 to C) may
567 overflow, in which case BNDS.up will not be giving a correct upper
568 bound on C; thus, BNDS_U_VALID had to be computed in advance. */
570 exit_must_be_taken
= true;
573 /* If the induction variable can overflow, the number of iterations is at
574 most the period of the control variable (or infinite, but in that case
575 the whole # of iterations analysis will fail). */
578 max
= double_int_mask (TYPE_PRECISION (TREE_TYPE (c
))
579 - tree_low_cst (num_ending_zeros (s
), 1));
580 mpz_set_double_int (bnd
, max
, true);
584 /* Now we know that the induction variable does not overflow, so the loop
585 iterates at most (range of type / S) times. */
586 mpz_set_double_int (bnd
, double_int_mask (TYPE_PRECISION (TREE_TYPE (c
))),
589 /* If the induction variable is guaranteed to reach the value of C before
591 if (exit_must_be_taken
)
593 /* ... then we can strengthen this to C / S, and possibly we can use
594 the upper bound on C given by BNDS. */
595 if (TREE_CODE (c
) == INTEGER_CST
)
596 mpz_set_double_int (bnd
, tree_to_double_int (c
), true);
597 else if (bnds_u_valid
)
598 mpz_set (bnd
, bnds
->up
);
602 mpz_set_double_int (d
, tree_to_double_int (s
), true);
603 mpz_fdiv_q (bnd
, bnd
, d
);
607 /* Determines number of iterations of loop whose ending condition
608 is IV <> FINAL. TYPE is the type of the iv. The number of
609 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
610 we know that the exit must be taken eventually, i.e., that the IV
611 ever reaches the value FINAL (we derived this earlier, and possibly set
612 NITER->assumptions to make sure this is the case). BNDS contains the
613 bounds on the difference FINAL - IV->base. */
616 number_of_iterations_ne (tree type
, affine_iv
*iv
, tree final
,
617 struct tree_niter_desc
*niter
, bool exit_must_be_taken
,
620 tree niter_type
= unsigned_type_for (type
);
621 tree s
, c
, d
, bits
, assumption
, tmp
, bound
;
624 niter
->control
= *iv
;
625 niter
->bound
= final
;
626 niter
->cmp
= NE_EXPR
;
628 /* Rearrange the terms so that we get inequality S * i <> C, with S
629 positive. Also cast everything to the unsigned type. If IV does
630 not overflow, BNDS bounds the value of C. Also, this is the
631 case if the computation |FINAL - IV->base| does not overflow, i.e.,
632 if BNDS->below in the result is nonnegative. */
633 if (tree_int_cst_sign_bit (iv
->step
))
635 s
= fold_convert (niter_type
,
636 fold_build1 (NEGATE_EXPR
, type
, iv
->step
));
637 c
= fold_build2 (MINUS_EXPR
, niter_type
,
638 fold_convert (niter_type
, iv
->base
),
639 fold_convert (niter_type
, final
));
640 bounds_negate (bnds
);
644 s
= fold_convert (niter_type
, iv
->step
);
645 c
= fold_build2 (MINUS_EXPR
, niter_type
,
646 fold_convert (niter_type
, final
),
647 fold_convert (niter_type
, iv
->base
));
651 number_of_iterations_ne_max (max
, iv
->no_overflow
, c
, s
, bnds
,
653 niter
->max
= mpz_get_double_int (niter_type
, max
, false);
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_low_cst (bits
, 1)));
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 mpz_set_double_int (mmod
, tree_to_double_int (mod
), true);
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
, tree_to_double_int (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
= tree_to_double_int (iv0
->step
);
927 dstep
= double_int_sext (tree_to_double_int (iv1
->step
),
928 TYPE_PRECISION (type
));
929 dstep
= double_int_neg (dstep
);
933 mpz_set_double_int (mstep
, dstep
, true);
934 mpz_neg (mstep
, mstep
);
935 mpz_add_ui (mstep
, mstep
, 1);
937 rolls_p
= mpz_cmp (mstep
, bnds
->below
) <= 0;
940 mpz_set_double_int (max
, double_int_mask (TYPE_PRECISION (type
)), true);
941 mpz_add (max
, max
, mstep
);
942 no_overflow_p
= (mpz_cmp (bnds
->up
, max
) <= 0
943 /* For pointers, only values lying inside a single object
944 can be compared or manipulated by pointer arithmetics.
945 Gcc in general does not allow or handle objects larger
946 than half of the address space, hence the upper bound
947 is satisfied for pointers. */
948 || POINTER_TYPE_P (type
));
952 if (rolls_p
&& no_overflow_p
)
956 if (POINTER_TYPE_P (type
))
959 /* Now the hard part; we must formulate the assumption(s) as expressions, and
960 we must be careful not to introduce overflow. */
962 if (integer_nonzerop (iv0
->step
))
964 diff
= fold_build2 (MINUS_EXPR
, type1
,
965 iv0
->step
, build_int_cst (type1
, 1));
967 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
968 0 address never belongs to any object, we can assume this for
970 if (!POINTER_TYPE_P (type
))
972 bound
= fold_build2 (PLUS_EXPR
, type1
,
973 TYPE_MIN_VALUE (type
), diff
);
974 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
978 /* And then we can compute iv0->base - diff, and compare it with
980 mbzl
= fold_build2 (MINUS_EXPR
, type1
,
981 fold_convert (type1
, iv0
->base
), diff
);
982 mbzr
= fold_convert (type1
, iv1
->base
);
986 diff
= fold_build2 (PLUS_EXPR
, type1
,
987 iv1
->step
, build_int_cst (type1
, 1));
989 if (!POINTER_TYPE_P (type
))
991 bound
= fold_build2 (PLUS_EXPR
, type1
,
992 TYPE_MAX_VALUE (type
), diff
);
993 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
997 mbzl
= fold_convert (type1
, iv0
->base
);
998 mbzr
= fold_build2 (MINUS_EXPR
, type1
,
999 fold_convert (type1
, iv1
->base
), diff
);
1002 if (!integer_nonzerop (assumption
))
1003 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1004 niter
->assumptions
, assumption
);
1007 mbz
= fold_build2 (GT_EXPR
, boolean_type_node
, mbzl
, mbzr
);
1008 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1009 niter
->may_be_zero
, mbz
);
1013 /* Determines number of iterations of loop whose ending condition
1014 is IV0 < IV1. TYPE is the type of the iv. The number of
1015 iterations is stored to NITER. BNDS bounds the difference
1016 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
1017 that the exit must be taken eventually. */
1020 number_of_iterations_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1021 struct tree_niter_desc
*niter
,
1022 bool exit_must_be_taken
, bounds
*bnds
)
1024 tree niter_type
= unsigned_type_for (type
);
1025 tree delta
, step
, s
;
1028 if (integer_nonzerop (iv0
->step
))
1030 niter
->control
= *iv0
;
1031 niter
->cmp
= LT_EXPR
;
1032 niter
->bound
= iv1
->base
;
1036 niter
->control
= *iv1
;
1037 niter
->cmp
= GT_EXPR
;
1038 niter
->bound
= iv0
->base
;
1041 delta
= fold_build2 (MINUS_EXPR
, niter_type
,
1042 fold_convert (niter_type
, iv1
->base
),
1043 fold_convert (niter_type
, iv0
->base
));
1045 /* First handle the special case that the step is +-1. */
1046 if ((integer_onep (iv0
->step
) && integer_zerop (iv1
->step
))
1047 || (integer_all_onesp (iv1
->step
) && integer_zerop (iv0
->step
)))
1049 /* for (i = iv0->base; i < iv1->base; i++)
1053 for (i = iv1->base; i > iv0->base; i--).
1055 In both cases # of iterations is iv1->base - iv0->base, assuming that
1056 iv1->base >= iv0->base.
1058 First try to derive a lower bound on the value of
1059 iv1->base - iv0->base, computed in full precision. If the difference
1060 is nonnegative, we are done, otherwise we must record the
1063 if (mpz_sgn (bnds
->below
) < 0)
1064 niter
->may_be_zero
= fold_build2 (LT_EXPR
, boolean_type_node
,
1065 iv1
->base
, iv0
->base
);
1066 niter
->niter
= delta
;
1067 niter
->max
= mpz_get_double_int (niter_type
, bnds
->up
, false);
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 mpz_set_double_int (mstep
, tree_to_double_int (step
), true);
1111 mpz_add (tmp
, bnds
->up
, mstep
);
1112 mpz_sub_ui (tmp
, tmp
, 1);
1113 mpz_fdiv_q (tmp
, tmp
, mstep
);
1114 niter
->max
= mpz_get_double_int (niter_type
, tmp
, false);
1121 /* Determines number of iterations of loop whose ending condition
1122 is IV0 <= IV1. TYPE is the type of the iv. The number of
1123 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
1124 we know that this condition must eventually become false (we derived this
1125 earlier, and possibly set NITER->assumptions to make sure this
1126 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1129 number_of_iterations_le (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1130 struct tree_niter_desc
*niter
, bool exit_must_be_taken
,
1135 if (POINTER_TYPE_P (type
))
1138 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1139 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1140 value of the type. This we must know anyway, since if it is
1141 equal to this value, the loop rolls forever. We do not check
1142 this condition for pointer type ivs, as the code cannot rely on
1143 the object to that the pointer points being placed at the end of
1144 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1145 not defined for pointers). */
1147 if (!exit_must_be_taken
&& !POINTER_TYPE_P (type
))
1149 if (integer_nonzerop (iv0
->step
))
1150 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1151 iv1
->base
, TYPE_MAX_VALUE (type
));
1153 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1154 iv0
->base
, TYPE_MIN_VALUE (type
));
1156 if (integer_zerop (assumption
))
1158 if (!integer_nonzerop (assumption
))
1159 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1160 niter
->assumptions
, assumption
);
1163 if (integer_nonzerop (iv0
->step
))
1165 if (POINTER_TYPE_P (type
))
1166 iv1
->base
= fold_build_pointer_plus_hwi (iv1
->base
, 1);
1168 iv1
->base
= fold_build2 (PLUS_EXPR
, type1
, iv1
->base
,
1169 build_int_cst (type1
, 1));
1171 else if (POINTER_TYPE_P (type
))
1172 iv0
->base
= fold_build_pointer_plus_hwi (iv0
->base
, -1);
1174 iv0
->base
= fold_build2 (MINUS_EXPR
, type1
,
1175 iv0
->base
, build_int_cst (type1
, 1));
1177 bounds_add (bnds
, double_int_one
, type1
);
1179 return number_of_iterations_lt (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1183 /* Dumps description of affine induction variable IV to FILE. */
1186 dump_affine_iv (FILE *file
, affine_iv
*iv
)
1188 if (!integer_zerop (iv
->step
))
1189 fprintf (file
, "[");
1191 print_generic_expr (dump_file
, iv
->base
, TDF_SLIM
);
1193 if (!integer_zerop (iv
->step
))
1195 fprintf (file
, ", + , ");
1196 print_generic_expr (dump_file
, iv
->step
, TDF_SLIM
);
1197 fprintf (file
, "]%s", iv
->no_overflow
? "(no_overflow)" : "");
1201 /* Determine the number of iterations according to condition (for staying
1202 inside loop) which compares two induction variables using comparison
1203 operator CODE. The induction variable on left side of the comparison
1204 is IV0, the right-hand side is IV1. Both induction variables must have
1205 type TYPE, which must be an integer or pointer type. The steps of the
1206 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1208 LOOP is the loop whose number of iterations we are determining.
1210 ONLY_EXIT is true if we are sure this is the only way the loop could be
1211 exited (including possibly non-returning function calls, exceptions, etc.)
1212 -- in this case we can use the information whether the control induction
1213 variables can overflow or not in a more efficient way.
1215 The results (number of iterations and assumptions as described in
1216 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
1217 Returns false if it fails to determine number of iterations, true if it
1218 was determined (possibly with some assumptions). */
1221 number_of_iterations_cond (struct loop
*loop
,
1222 tree type
, affine_iv
*iv0
, enum tree_code code
,
1223 affine_iv
*iv1
, struct tree_niter_desc
*niter
,
1226 bool exit_must_be_taken
= false, ret
;
1229 /* The meaning of these assumptions is this:
1231 then the rest of information does not have to be valid
1232 if may_be_zero then the loop does not roll, even if
1234 niter
->assumptions
= boolean_true_node
;
1235 niter
->may_be_zero
= boolean_false_node
;
1236 niter
->niter
= NULL_TREE
;
1237 niter
->max
= double_int_zero
;
1239 niter
->bound
= NULL_TREE
;
1240 niter
->cmp
= ERROR_MARK
;
1242 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1243 the control variable is on lhs. */
1244 if (code
== GE_EXPR
|| code
== GT_EXPR
1245 || (code
== NE_EXPR
&& integer_zerop (iv0
->step
)))
1248 code
= swap_tree_comparison (code
);
1251 if (POINTER_TYPE_P (type
))
1253 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1254 to the same object. If they do, the control variable cannot wrap
1255 (as wrap around the bounds of memory will never return a pointer
1256 that would be guaranteed to point to the same object, even if we
1257 avoid undefined behavior by casting to size_t and back). */
1258 iv0
->no_overflow
= true;
1259 iv1
->no_overflow
= true;
1262 /* If the control induction variable does not overflow and the only exit
1263 from the loop is the one that we analyze, we know it must be taken
1267 if (!integer_zerop (iv0
->step
) && iv0
->no_overflow
)
1268 exit_must_be_taken
= true;
1269 else if (!integer_zerop (iv1
->step
) && iv1
->no_overflow
)
1270 exit_must_be_taken
= true;
1273 /* We can handle the case when neither of the sides of the comparison is
1274 invariant, provided that the test is NE_EXPR. This rarely occurs in
1275 practice, but it is simple enough to manage. */
1276 if (!integer_zerop (iv0
->step
) && !integer_zerop (iv1
->step
))
1278 tree step_type
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1279 if (code
!= NE_EXPR
)
1282 iv0
->step
= fold_binary_to_constant (MINUS_EXPR
, step_type
,
1283 iv0
->step
, iv1
->step
);
1284 iv0
->no_overflow
= false;
1285 iv1
->step
= build_int_cst (step_type
, 0);
1286 iv1
->no_overflow
= true;
1289 /* If the result of the comparison is a constant, the loop is weird. More
1290 precise handling would be possible, but the situation is not common enough
1291 to waste time on it. */
1292 if (integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
))
1295 /* Ignore loops of while (i-- < 10) type. */
1296 if (code
!= NE_EXPR
)
1298 if (iv0
->step
&& tree_int_cst_sign_bit (iv0
->step
))
1301 if (!integer_zerop (iv1
->step
) && !tree_int_cst_sign_bit (iv1
->step
))
1305 /* If the loop exits immediately, there is nothing to do. */
1306 if (integer_zerop (fold_build2 (code
, boolean_type_node
, iv0
->base
, iv1
->base
)))
1308 niter
->niter
= build_int_cst (unsigned_type_for (type
), 0);
1309 niter
->max
= double_int_zero
;
1313 /* OK, now we know we have a senseful loop. Handle several cases, depending
1314 on what comparison operator is used. */
1315 bound_difference (loop
, iv1
->base
, iv0
->base
, &bnds
);
1317 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1320 "Analyzing # of iterations of loop %d\n", loop
->num
);
1322 fprintf (dump_file
, " exit condition ");
1323 dump_affine_iv (dump_file
, iv0
);
1324 fprintf (dump_file
, " %s ",
1325 code
== NE_EXPR
? "!="
1326 : code
== LT_EXPR
? "<"
1328 dump_affine_iv (dump_file
, iv1
);
1329 fprintf (dump_file
, "\n");
1331 fprintf (dump_file
, " bounds on difference of bases: ");
1332 mpz_out_str (dump_file
, 10, bnds
.below
);
1333 fprintf (dump_file
, " ... ");
1334 mpz_out_str (dump_file
, 10, bnds
.up
);
1335 fprintf (dump_file
, "\n");
1341 gcc_assert (integer_zerop (iv1
->step
));
1342 ret
= number_of_iterations_ne (type
, iv0
, iv1
->base
, niter
,
1343 exit_must_be_taken
, &bnds
);
1347 ret
= number_of_iterations_lt (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1352 ret
= number_of_iterations_le (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1360 mpz_clear (bnds
.up
);
1361 mpz_clear (bnds
.below
);
1363 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1367 fprintf (dump_file
, " result:\n");
1368 if (!integer_nonzerop (niter
->assumptions
))
1370 fprintf (dump_file
, " under assumptions ");
1371 print_generic_expr (dump_file
, niter
->assumptions
, TDF_SLIM
);
1372 fprintf (dump_file
, "\n");
1375 if (!integer_zerop (niter
->may_be_zero
))
1377 fprintf (dump_file
, " zero if ");
1378 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
1379 fprintf (dump_file
, "\n");
1382 fprintf (dump_file
, " # of iterations ");
1383 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
1384 fprintf (dump_file
, ", bounded by ");
1385 dump_double_int (dump_file
, niter
->max
, true);
1386 fprintf (dump_file
, "\n");
1389 fprintf (dump_file
, " failed\n\n");
1394 /* Substitute NEW for OLD in EXPR and fold the result. */
1397 simplify_replace_tree (tree expr
, tree old
, tree new_tree
)
1400 tree ret
= NULL_TREE
, e
, se
;
1405 /* Do not bother to replace constants. */
1406 if (CONSTANT_CLASS_P (old
))
1410 || operand_equal_p (expr
, old
, 0))
1411 return unshare_expr (new_tree
);
1416 n
= TREE_OPERAND_LENGTH (expr
);
1417 for (i
= 0; i
< n
; i
++)
1419 e
= TREE_OPERAND (expr
, i
);
1420 se
= simplify_replace_tree (e
, old
, new_tree
);
1425 ret
= copy_node (expr
);
1427 TREE_OPERAND (ret
, i
) = se
;
1430 return (ret
? fold (ret
) : expr
);
1433 /* Expand definitions of ssa names in EXPR as long as they are simple
1434 enough, and return the new expression. */
1437 expand_simple_operations (tree expr
)
1440 tree ret
= NULL_TREE
, e
, ee
, e1
;
1441 enum tree_code code
;
1444 if (expr
== NULL_TREE
)
1447 if (is_gimple_min_invariant (expr
))
1450 code
= TREE_CODE (expr
);
1451 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
1453 n
= TREE_OPERAND_LENGTH (expr
);
1454 for (i
= 0; i
< n
; i
++)
1456 e
= TREE_OPERAND (expr
, i
);
1457 ee
= expand_simple_operations (e
);
1462 ret
= copy_node (expr
);
1464 TREE_OPERAND (ret
, i
) = ee
;
1470 fold_defer_overflow_warnings ();
1472 fold_undefer_and_ignore_overflow_warnings ();
1476 if (TREE_CODE (expr
) != SSA_NAME
)
1479 stmt
= SSA_NAME_DEF_STMT (expr
);
1480 if (gimple_code (stmt
) == GIMPLE_PHI
)
1482 basic_block src
, dest
;
1484 if (gimple_phi_num_args (stmt
) != 1)
1486 e
= PHI_ARG_DEF (stmt
, 0);
1488 /* Avoid propagating through loop exit phi nodes, which
1489 could break loop-closed SSA form restrictions. */
1490 dest
= gimple_bb (stmt
);
1491 src
= single_pred (dest
);
1492 if (TREE_CODE (e
) == SSA_NAME
1493 && src
->loop_father
!= dest
->loop_father
)
1496 return expand_simple_operations (e
);
1498 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1501 e
= gimple_assign_rhs1 (stmt
);
1502 code
= gimple_assign_rhs_code (stmt
);
1503 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1505 if (is_gimple_min_invariant (e
))
1508 if (code
== SSA_NAME
)
1509 return expand_simple_operations (e
);
1517 /* Casts are simple. */
1518 ee
= expand_simple_operations (e
);
1519 return fold_build1 (code
, TREE_TYPE (expr
), ee
);
1523 case POINTER_PLUS_EXPR
:
1524 /* And increments and decrements by a constant are simple. */
1525 e1
= gimple_assign_rhs2 (stmt
);
1526 if (!is_gimple_min_invariant (e1
))
1529 ee
= expand_simple_operations (e
);
1530 return fold_build2 (code
, TREE_TYPE (expr
), ee
, e1
);
1537 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1538 expression (or EXPR unchanged, if no simplification was possible). */
1541 tree_simplify_using_condition_1 (tree cond
, tree expr
)
1544 tree e
, te
, e0
, e1
, e2
, notcond
;
1545 enum tree_code code
= TREE_CODE (expr
);
1547 if (code
== INTEGER_CST
)
1550 if (code
== TRUTH_OR_EXPR
1551 || code
== TRUTH_AND_EXPR
1552 || code
== COND_EXPR
)
1556 e0
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 0));
1557 if (TREE_OPERAND (expr
, 0) != e0
)
1560 e1
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 1));
1561 if (TREE_OPERAND (expr
, 1) != e1
)
1564 if (code
== COND_EXPR
)
1566 e2
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 2));
1567 if (TREE_OPERAND (expr
, 2) != e2
)
1575 if (code
== COND_EXPR
)
1576 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1578 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1584 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
1585 propagation, and vice versa. Fold does not handle this, since it is
1586 considered too expensive. */
1587 if (TREE_CODE (cond
) == EQ_EXPR
)
1589 e0
= TREE_OPERAND (cond
, 0);
1590 e1
= TREE_OPERAND (cond
, 1);
1592 /* We know that e0 == e1. Check whether we cannot simplify expr
1594 e
= simplify_replace_tree (expr
, e0
, e1
);
1595 if (integer_zerop (e
) || integer_nonzerop (e
))
1598 e
= simplify_replace_tree (expr
, e1
, e0
);
1599 if (integer_zerop (e
) || integer_nonzerop (e
))
1602 if (TREE_CODE (expr
) == EQ_EXPR
)
1604 e0
= TREE_OPERAND (expr
, 0);
1605 e1
= TREE_OPERAND (expr
, 1);
1607 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
1608 e
= simplify_replace_tree (cond
, e0
, e1
);
1609 if (integer_zerop (e
))
1611 e
= simplify_replace_tree (cond
, e1
, e0
);
1612 if (integer_zerop (e
))
1615 if (TREE_CODE (expr
) == NE_EXPR
)
1617 e0
= TREE_OPERAND (expr
, 0);
1618 e1
= TREE_OPERAND (expr
, 1);
1620 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
1621 e
= simplify_replace_tree (cond
, e0
, e1
);
1622 if (integer_zerop (e
))
1623 return boolean_true_node
;
1624 e
= simplify_replace_tree (cond
, e1
, e0
);
1625 if (integer_zerop (e
))
1626 return boolean_true_node
;
1629 te
= expand_simple_operations (expr
);
1631 /* Check whether COND ==> EXPR. */
1632 notcond
= invert_truthvalue (cond
);
1633 e
= fold_binary (TRUTH_OR_EXPR
, boolean_type_node
, notcond
, te
);
1634 if (e
&& integer_nonzerop (e
))
1637 /* Check whether COND ==> not EXPR. */
1638 e
= fold_binary (TRUTH_AND_EXPR
, boolean_type_node
, cond
, te
);
1639 if (e
&& integer_zerop (e
))
1645 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1646 expression (or EXPR unchanged, if no simplification was possible).
1647 Wrapper around tree_simplify_using_condition_1 that ensures that chains
1648 of simple operations in definitions of ssa names in COND are expanded,
1649 so that things like casts or incrementing the value of the bound before
1650 the loop do not cause us to fail. */
1653 tree_simplify_using_condition (tree cond
, tree expr
)
1655 cond
= expand_simple_operations (cond
);
1657 return tree_simplify_using_condition_1 (cond
, expr
);
1660 /* Tries to simplify EXPR using the conditions on entry to LOOP.
1661 Returns the simplified expression (or EXPR unchanged, if no
1662 simplification was possible).*/
1665 simplify_using_initial_conditions (struct loop
*loop
, tree expr
)
1673 if (TREE_CODE (expr
) == INTEGER_CST
)
1676 /* Limit walking the dominators to avoid quadraticness in
1677 the number of BBs times the number of loops in degenerate
1679 for (bb
= loop
->header
;
1680 bb
!= ENTRY_BLOCK_PTR
&& cnt
< MAX_DOMINATORS_TO_WALK
;
1681 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1683 if (!single_pred_p (bb
))
1685 e
= single_pred_edge (bb
);
1687 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
1690 stmt
= last_stmt (e
->src
);
1691 cond
= fold_build2 (gimple_cond_code (stmt
),
1693 gimple_cond_lhs (stmt
),
1694 gimple_cond_rhs (stmt
));
1695 if (e
->flags
& EDGE_FALSE_VALUE
)
1696 cond
= invert_truthvalue (cond
);
1697 expr
= tree_simplify_using_condition (cond
, expr
);
1704 /* Tries to simplify EXPR using the evolutions of the loop invariants
1705 in the superloops of LOOP. Returns the simplified expression
1706 (or EXPR unchanged, if no simplification was possible). */
1709 simplify_using_outer_evolutions (struct loop
*loop
, tree expr
)
1711 enum tree_code code
= TREE_CODE (expr
);
1715 if (is_gimple_min_invariant (expr
))
1718 if (code
== TRUTH_OR_EXPR
1719 || code
== TRUTH_AND_EXPR
1720 || code
== COND_EXPR
)
1724 e0
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 0));
1725 if (TREE_OPERAND (expr
, 0) != e0
)
1728 e1
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 1));
1729 if (TREE_OPERAND (expr
, 1) != e1
)
1732 if (code
== COND_EXPR
)
1734 e2
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 2));
1735 if (TREE_OPERAND (expr
, 2) != e2
)
1743 if (code
== COND_EXPR
)
1744 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1746 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1752 e
= instantiate_parameters (loop
, expr
);
1753 if (is_gimple_min_invariant (e
))
1759 /* Returns true if EXIT is the only possible exit from LOOP. */
1762 loop_only_exit_p (const struct loop
*loop
, const_edge exit
)
1765 gimple_stmt_iterator bsi
;
1769 if (exit
!= single_exit (loop
))
1772 body
= get_loop_body (loop
);
1773 for (i
= 0; i
< loop
->num_nodes
; i
++)
1775 for (bsi
= gsi_start_bb (body
[i
]); !gsi_end_p (bsi
); gsi_next (&bsi
))
1777 call
= gsi_stmt (bsi
);
1778 if (gimple_code (call
) != GIMPLE_CALL
)
1781 if (gimple_has_side_effects (call
))
1793 /* Stores description of number of iterations of LOOP derived from
1794 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
1795 useful information could be derived (and fields of NITER has
1796 meaning described in comments at struct tree_niter_desc
1797 declaration), false otherwise. If WARN is true and
1798 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1799 potentially unsafe assumptions. */
1802 number_of_iterations_exit (struct loop
*loop
, edge exit
,
1803 struct tree_niter_desc
*niter
,
1809 enum tree_code code
;
1812 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit
->src
))
1815 niter
->assumptions
= boolean_false_node
;
1816 stmt
= last_stmt (exit
->src
);
1817 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1820 /* We want the condition for staying inside loop. */
1821 code
= gimple_cond_code (stmt
);
1822 if (exit
->flags
& EDGE_TRUE_VALUE
)
1823 code
= invert_tree_comparison (code
, false);
1838 op0
= gimple_cond_lhs (stmt
);
1839 op1
= gimple_cond_rhs (stmt
);
1840 type
= TREE_TYPE (op0
);
1842 if (TREE_CODE (type
) != INTEGER_TYPE
1843 && !POINTER_TYPE_P (type
))
1846 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, false))
1848 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, false))
1851 /* We don't want to see undefined signed overflow warnings while
1852 computing the number of iterations. */
1853 fold_defer_overflow_warnings ();
1855 iv0
.base
= expand_simple_operations (iv0
.base
);
1856 iv1
.base
= expand_simple_operations (iv1
.base
);
1857 if (!number_of_iterations_cond (loop
, type
, &iv0
, code
, &iv1
, niter
,
1858 loop_only_exit_p (loop
, exit
)))
1860 fold_undefer_and_ignore_overflow_warnings ();
1866 niter
->assumptions
= simplify_using_outer_evolutions (loop
,
1867 niter
->assumptions
);
1868 niter
->may_be_zero
= simplify_using_outer_evolutions (loop
,
1869 niter
->may_be_zero
);
1870 niter
->niter
= simplify_using_outer_evolutions (loop
, niter
->niter
);
1874 = simplify_using_initial_conditions (loop
,
1875 niter
->assumptions
);
1877 = simplify_using_initial_conditions (loop
,
1878 niter
->may_be_zero
);
1880 fold_undefer_and_ignore_overflow_warnings ();
1882 if (integer_onep (niter
->assumptions
))
1885 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1886 But if we can prove that there is overflow or some other source of weird
1887 behavior, ignore the loop even with -funsafe-loop-optimizations. */
1888 if (integer_zerop (niter
->assumptions
) || !single_exit (loop
))
1891 if (flag_unsafe_loop_optimizations
)
1892 niter
->assumptions
= boolean_true_node
;
1896 const char *wording
;
1897 location_t loc
= gimple_location (stmt
);
1899 /* We can provide a more specific warning if one of the operator is
1900 constant and the other advances by +1 or -1. */
1901 if (!integer_zerop (iv1
.step
)
1902 ? (integer_zerop (iv0
.step
)
1903 && (integer_onep (iv1
.step
) || integer_all_onesp (iv1
.step
)))
1904 : (integer_onep (iv0
.step
) || integer_all_onesp (iv0
.step
)))
1906 flag_unsafe_loop_optimizations
1907 ? N_("assuming that the loop is not infinite")
1908 : N_("cannot optimize possibly infinite loops");
1911 flag_unsafe_loop_optimizations
1912 ? N_("assuming that the loop counter does not overflow")
1913 : N_("cannot optimize loop, the loop counter may overflow");
1915 warning_at ((LOCATION_LINE (loc
) > 0) ? loc
: input_location
,
1916 OPT_Wunsafe_loop_optimizations
, "%s", gettext (wording
));
1919 return flag_unsafe_loop_optimizations
;
1922 /* Try to determine the number of iterations of LOOP. If we succeed,
1923 expression giving number of iterations is returned and *EXIT is
1924 set to the edge from that the information is obtained. Otherwise
1925 chrec_dont_know is returned. */
1928 find_loop_niter (struct loop
*loop
, edge
*exit
)
1931 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
1933 tree niter
= NULL_TREE
, aniter
;
1934 struct tree_niter_desc desc
;
1937 FOR_EACH_VEC_ELT (edge
, exits
, i
, ex
)
1939 if (!just_once_each_iteration_p (loop
, ex
->src
))
1942 if (!number_of_iterations_exit (loop
, ex
, &desc
, false))
1945 if (integer_nonzerop (desc
.may_be_zero
))
1947 /* We exit in the first iteration through this exit.
1948 We won't find anything better. */
1949 niter
= build_int_cst (unsigned_type_node
, 0);
1954 if (!integer_zerop (desc
.may_be_zero
))
1957 aniter
= desc
.niter
;
1961 /* Nothing recorded yet. */
1967 /* Prefer constants, the lower the better. */
1968 if (TREE_CODE (aniter
) != INTEGER_CST
)
1971 if (TREE_CODE (niter
) != INTEGER_CST
)
1978 if (tree_int_cst_lt (aniter
, niter
))
1985 VEC_free (edge
, heap
, exits
);
1987 return niter
? niter
: chrec_dont_know
;
1990 /* Return true if loop is known to have bounded number of iterations. */
1993 finite_loop_p (struct loop
*loop
)
1996 VEC (edge
, heap
) *exits
;
1998 struct tree_niter_desc desc
;
1999 bool finite
= false;
2002 if (flag_unsafe_loop_optimizations
)
2004 flags
= flags_from_decl_or_type (current_function_decl
);
2005 if ((flags
& (ECF_CONST
|ECF_PURE
)) && !(flags
& ECF_LOOPING_CONST_OR_PURE
))
2007 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2008 fprintf (dump_file
, "Found loop %i to be finite: it is within pure or const function.\n",
2013 exits
= get_loop_exit_edges (loop
);
2014 FOR_EACH_VEC_ELT (edge
, exits
, i
, ex
)
2016 if (!just_once_each_iteration_p (loop
, ex
->src
))
2019 if (number_of_iterations_exit (loop
, ex
, &desc
, false))
2021 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2023 fprintf (dump_file
, "Found loop %i to be finite: iterating ", loop
->num
);
2024 print_generic_expr (dump_file
, desc
.niter
, TDF_SLIM
);
2025 fprintf (dump_file
, " times\n");
2031 VEC_free (edge
, heap
, exits
);
2037 Analysis of a number of iterations of a loop by a brute-force evaluation.
2041 /* Bound on the number of iterations we try to evaluate. */
2043 #define MAX_ITERATIONS_TO_TRACK \
2044 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
2046 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
2047 result by a chain of operations such that all but exactly one of their
2048 operands are constants. */
2051 chain_of_csts_start (struct loop
*loop
, tree x
)
2053 gimple stmt
= SSA_NAME_DEF_STMT (x
);
2055 basic_block bb
= gimple_bb (stmt
);
2056 enum tree_code code
;
2059 || !flow_bb_inside_loop_p (loop
, bb
))
2062 if (gimple_code (stmt
) == GIMPLE_PHI
)
2064 if (bb
== loop
->header
)
2070 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2073 code
= gimple_assign_rhs_code (stmt
);
2074 if (gimple_references_memory_p (stmt
)
2075 || TREE_CODE_CLASS (code
) == tcc_reference
2076 || (code
== ADDR_EXPR
2077 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
2080 use
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
2081 if (use
== NULL_TREE
)
2084 return chain_of_csts_start (loop
, use
);
2087 /* Determines whether the expression X is derived from a result of a phi node
2088 in header of LOOP such that
2090 * the derivation of X consists only from operations with constants
2091 * the initial value of the phi node is constant
2092 * the value of the phi node in the next iteration can be derived from the
2093 value in the current iteration by a chain of operations with constants.
2095 If such phi node exists, it is returned, otherwise NULL is returned. */
2098 get_base_for (struct loop
*loop
, tree x
)
2103 if (is_gimple_min_invariant (x
))
2106 phi
= chain_of_csts_start (loop
, x
);
2110 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2111 next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2113 if (TREE_CODE (next
) != SSA_NAME
)
2116 if (!is_gimple_min_invariant (init
))
2119 if (chain_of_csts_start (loop
, next
) != phi
)
2125 /* Given an expression X, then
2127 * if X is NULL_TREE, we return the constant BASE.
2128 * otherwise X is a SSA name, whose value in the considered loop is derived
2129 by a chain of operations with constant from a result of a phi node in
2130 the header of the loop. Then we return value of X when the value of the
2131 result of this phi node is given by the constant BASE. */
2134 get_val_for (tree x
, tree base
)
2138 gcc_assert (is_gimple_min_invariant (base
));
2143 stmt
= SSA_NAME_DEF_STMT (x
);
2144 if (gimple_code (stmt
) == GIMPLE_PHI
)
2147 gcc_assert (is_gimple_assign (stmt
));
2149 /* STMT must be either an assignment of a single SSA name or an
2150 expression involving an SSA name and a constant. Try to fold that
2151 expression using the value for the SSA name. */
2152 if (gimple_assign_ssa_name_copy_p (stmt
))
2153 return get_val_for (gimple_assign_rhs1 (stmt
), base
);
2154 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_UNARY_RHS
2155 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
2157 return fold_build1 (gimple_assign_rhs_code (stmt
),
2158 gimple_expr_type (stmt
),
2159 get_val_for (gimple_assign_rhs1 (stmt
), base
));
2161 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_BINARY_RHS
)
2163 tree rhs1
= gimple_assign_rhs1 (stmt
);
2164 tree rhs2
= gimple_assign_rhs2 (stmt
);
2165 if (TREE_CODE (rhs1
) == SSA_NAME
)
2166 rhs1
= get_val_for (rhs1
, base
);
2167 else if (TREE_CODE (rhs2
) == SSA_NAME
)
2168 rhs2
= get_val_for (rhs2
, base
);
2171 return fold_build2 (gimple_assign_rhs_code (stmt
),
2172 gimple_expr_type (stmt
), rhs1
, rhs2
);
2179 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2180 by brute force -- i.e. by determining the value of the operands of the
2181 condition at EXIT in first few iterations of the loop (assuming that
2182 these values are constant) and determining the first one in that the
2183 condition is not satisfied. Returns the constant giving the number
2184 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
2187 loop_niter_by_eval (struct loop
*loop
, edge exit
)
2190 tree op
[2], val
[2], next
[2], aval
[2];
2195 cond
= last_stmt (exit
->src
);
2196 if (!cond
|| gimple_code (cond
) != GIMPLE_COND
)
2197 return chrec_dont_know
;
2199 cmp
= gimple_cond_code (cond
);
2200 if (exit
->flags
& EDGE_TRUE_VALUE
)
2201 cmp
= invert_tree_comparison (cmp
, false);
2211 op
[0] = gimple_cond_lhs (cond
);
2212 op
[1] = gimple_cond_rhs (cond
);
2216 return chrec_dont_know
;
2219 for (j
= 0; j
< 2; j
++)
2221 if (is_gimple_min_invariant (op
[j
]))
2224 next
[j
] = NULL_TREE
;
2229 phi
= get_base_for (loop
, op
[j
]);
2231 return chrec_dont_know
;
2232 val
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2233 next
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2237 /* Don't issue signed overflow warnings. */
2238 fold_defer_overflow_warnings ();
2240 for (i
= 0; i
< MAX_ITERATIONS_TO_TRACK
; i
++)
2242 for (j
= 0; j
< 2; j
++)
2243 aval
[j
] = get_val_for (op
[j
], val
[j
]);
2245 acnd
= fold_binary (cmp
, boolean_type_node
, aval
[0], aval
[1]);
2246 if (acnd
&& integer_zerop (acnd
))
2248 fold_undefer_and_ignore_overflow_warnings ();
2249 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2251 "Proved that loop %d iterates %d times using brute force.\n",
2253 return build_int_cst (unsigned_type_node
, i
);
2256 for (j
= 0; j
< 2; j
++)
2258 val
[j
] = get_val_for (next
[j
], val
[j
]);
2259 if (!is_gimple_min_invariant (val
[j
]))
2261 fold_undefer_and_ignore_overflow_warnings ();
2262 return chrec_dont_know
;
2267 fold_undefer_and_ignore_overflow_warnings ();
2269 return chrec_dont_know
;
2272 /* Finds the exit of the LOOP by that the loop exits after a constant
2273 number of iterations and stores the exit edge to *EXIT. The constant
2274 giving the number of iterations of LOOP is returned. The number of
2275 iterations is determined using loop_niter_by_eval (i.e. by brute force
2276 evaluation). If we are unable to find the exit for that loop_niter_by_eval
2277 determines the number of iterations, chrec_dont_know is returned. */
2280 find_loop_niter_by_eval (struct loop
*loop
, edge
*exit
)
2283 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
2285 tree niter
= NULL_TREE
, aniter
;
2289 /* Loops with multiple exits are expensive to handle and less important. */
2290 if (!flag_expensive_optimizations
2291 && VEC_length (edge
, exits
) > 1)
2292 return chrec_dont_know
;
2294 FOR_EACH_VEC_ELT (edge
, exits
, i
, ex
)
2296 if (!just_once_each_iteration_p (loop
, ex
->src
))
2299 aniter
= loop_niter_by_eval (loop
, ex
);
2300 if (chrec_contains_undetermined (aniter
))
2304 && !tree_int_cst_lt (aniter
, niter
))
2310 VEC_free (edge
, heap
, exits
);
2312 return niter
? niter
: chrec_dont_know
;
2317 Analysis of upper bounds on number of iterations of a loop.
2321 static double_int
derive_constant_upper_bound_ops (tree
, tree
,
2322 enum tree_code
, tree
);
2324 /* Returns a constant upper bound on the value of the right-hand side of
2325 an assignment statement STMT. */
2328 derive_constant_upper_bound_assign (gimple stmt
)
2330 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2331 tree op0
= gimple_assign_rhs1 (stmt
);
2332 tree op1
= gimple_assign_rhs2 (stmt
);
2334 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt
)),
2338 /* Returns a constant upper bound on the value of expression VAL. VAL
2339 is considered to be unsigned. If its type is signed, its value must
2343 derive_constant_upper_bound (tree val
)
2345 enum tree_code code
;
2348 extract_ops_from_tree (val
, &code
, &op0
, &op1
);
2349 return derive_constant_upper_bound_ops (TREE_TYPE (val
), op0
, code
, op1
);
2352 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
2353 whose type is TYPE. The expression is considered to be unsigned. If
2354 its type is signed, its value must be nonnegative. */
2357 derive_constant_upper_bound_ops (tree type
, tree op0
,
2358 enum tree_code code
, tree op1
)
2361 double_int bnd
, max
, mmax
, cst
;
2364 if (INTEGRAL_TYPE_P (type
))
2365 maxt
= TYPE_MAX_VALUE (type
);
2367 maxt
= upper_bound_in_type (type
, type
);
2369 max
= tree_to_double_int (maxt
);
2374 return tree_to_double_int (op0
);
2377 subtype
= TREE_TYPE (op0
);
2378 if (!TYPE_UNSIGNED (subtype
)
2379 /* If TYPE is also signed, the fact that VAL is nonnegative implies
2380 that OP0 is nonnegative. */
2381 && TYPE_UNSIGNED (type
)
2382 && !tree_expr_nonnegative_p (op0
))
2384 /* If we cannot prove that the casted expression is nonnegative,
2385 we cannot establish more useful upper bound than the precision
2386 of the type gives us. */
2390 /* We now know that op0 is an nonnegative value. Try deriving an upper
2392 bnd
= derive_constant_upper_bound (op0
);
2394 /* If the bound does not fit in TYPE, max. value of TYPE could be
2396 if (double_int_ucmp (max
, bnd
) < 0)
2402 case POINTER_PLUS_EXPR
:
2404 if (TREE_CODE (op1
) != INTEGER_CST
2405 || !tree_expr_nonnegative_p (op0
))
2408 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
2409 choose the most logical way how to treat this constant regardless
2410 of the signedness of the type. */
2411 cst
= tree_to_double_int (op1
);
2412 cst
= double_int_sext (cst
, TYPE_PRECISION (type
));
2413 if (code
!= MINUS_EXPR
)
2414 cst
= double_int_neg (cst
);
2416 bnd
= derive_constant_upper_bound (op0
);
2418 if (double_int_negative_p (cst
))
2420 cst
= double_int_neg (cst
);
2421 /* Avoid CST == 0x80000... */
2422 if (double_int_negative_p (cst
))
2425 /* OP0 + CST. We need to check that
2426 BND <= MAX (type) - CST. */
2428 mmax
= double_int_sub (max
, cst
);
2429 if (double_int_ucmp (bnd
, mmax
) > 0)
2432 return double_int_add (bnd
, cst
);
2436 /* OP0 - CST, where CST >= 0.
2438 If TYPE is signed, we have already verified that OP0 >= 0, and we
2439 know that the result is nonnegative. This implies that
2442 If TYPE is unsigned, we must additionally know that OP0 >= CST,
2443 otherwise the operation underflows.
2446 /* This should only happen if the type is unsigned; however, for
2447 buggy programs that use overflowing signed arithmetics even with
2448 -fno-wrapv, this condition may also be true for signed values. */
2449 if (double_int_ucmp (bnd
, cst
) < 0)
2452 if (TYPE_UNSIGNED (type
))
2454 tree tem
= fold_binary (GE_EXPR
, boolean_type_node
, op0
,
2455 double_int_to_tree (type
, cst
));
2456 if (!tem
|| integer_nonzerop (tem
))
2460 bnd
= double_int_sub (bnd
, cst
);
2465 case FLOOR_DIV_EXPR
:
2466 case EXACT_DIV_EXPR
:
2467 if (TREE_CODE (op1
) != INTEGER_CST
2468 || tree_int_cst_sign_bit (op1
))
2471 bnd
= derive_constant_upper_bound (op0
);
2472 return double_int_udiv (bnd
, tree_to_double_int (op1
), FLOOR_DIV_EXPR
);
2475 if (TREE_CODE (op1
) != INTEGER_CST
2476 || tree_int_cst_sign_bit (op1
))
2478 return tree_to_double_int (op1
);
2481 stmt
= SSA_NAME_DEF_STMT (op0
);
2482 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2483 || gimple_assign_lhs (stmt
) != op0
)
2485 return derive_constant_upper_bound_assign (stmt
);
2492 /* Records that every statement in LOOP is executed I_BOUND times.
2493 REALISTIC is true if I_BOUND is expected to be close to the real number
2494 of iterations. UPPER is true if we are sure the loop iterates at most
2498 record_niter_bound (struct loop
*loop
, double_int i_bound
, bool realistic
,
2501 /* Update the bounds only when there is no previous estimation, or when the
2502 current estimation is smaller. */
2504 && (!loop
->any_upper_bound
2505 || double_int_ucmp (i_bound
, loop
->nb_iterations_upper_bound
) < 0))
2507 loop
->any_upper_bound
= true;
2508 loop
->nb_iterations_upper_bound
= i_bound
;
2511 && (!loop
->any_estimate
2512 || double_int_ucmp (i_bound
, loop
->nb_iterations_estimate
) < 0))
2514 loop
->any_estimate
= true;
2515 loop
->nb_iterations_estimate
= i_bound
;
2518 /* If an upper bound is smaller than the realistic estimate of the
2519 number of iterations, use the upper bound instead. */
2520 if (loop
->any_upper_bound
2521 && loop
->any_estimate
2522 && double_int_ucmp (loop
->nb_iterations_upper_bound
,
2523 loop
->nb_iterations_estimate
) < 0)
2524 loop
->nb_iterations_estimate
= loop
->nb_iterations_upper_bound
;
2527 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
2528 is true if the loop is exited immediately after STMT, and this exit
2529 is taken at last when the STMT is executed BOUND + 1 times.
2530 REALISTIC is true if BOUND is expected to be close to the real number
2531 of iterations. UPPER is true if we are sure the loop iterates at most
2532 BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */
2535 record_estimate (struct loop
*loop
, tree bound
, double_int i_bound
,
2536 gimple at_stmt
, bool is_exit
, bool realistic
, bool upper
)
2541 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2543 fprintf (dump_file
, "Statement %s", is_exit
? "(exit)" : "");
2544 print_gimple_stmt (dump_file
, at_stmt
, 0, TDF_SLIM
);
2545 fprintf (dump_file
, " is %sexecuted at most ",
2546 upper
? "" : "probably ");
2547 print_generic_expr (dump_file
, bound
, TDF_SLIM
);
2548 fprintf (dump_file
, " (bounded by ");
2549 dump_double_int (dump_file
, i_bound
, true);
2550 fprintf (dump_file
, ") + 1 times in loop %d.\n", loop
->num
);
2553 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
2554 real number of iterations. */
2555 if (TREE_CODE (bound
) != INTEGER_CST
)
2557 if (!upper
&& !realistic
)
2560 /* If we have a guaranteed upper bound, record it in the appropriate
2564 struct nb_iter_bound
*elt
= ggc_alloc_nb_iter_bound ();
2566 elt
->bound
= i_bound
;
2567 elt
->stmt
= at_stmt
;
2568 elt
->is_exit
= is_exit
;
2569 elt
->next
= loop
->bounds
;
2573 /* Update the number of iteration estimates according to the bound.
2574 If at_stmt is an exit or dominates the single exit from the loop,
2575 then the loop latch is executed at most BOUND times, otherwise
2576 it can be executed BOUND + 1 times. */
2577 exit
= single_exit (loop
);
2580 && dominated_by_p (CDI_DOMINATORS
,
2581 exit
->src
, gimple_bb (at_stmt
))))
2582 delta
= double_int_zero
;
2584 delta
= double_int_one
;
2585 i_bound
= double_int_add (i_bound
, delta
);
2587 /* If an overflow occurred, ignore the result. */
2588 if (double_int_ucmp (i_bound
, delta
) < 0)
2591 record_niter_bound (loop
, i_bound
, realistic
, upper
);
2594 /* Record the estimate on number of iterations of LOOP based on the fact that
2595 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
2596 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
2597 estimated number of iterations is expected to be close to the real one.
2598 UPPER is true if we are sure the induction variable does not wrap. */
2601 record_nonwrapping_iv (struct loop
*loop
, tree base
, tree step
, gimple stmt
,
2602 tree low
, tree high
, bool realistic
, bool upper
)
2604 tree niter_bound
, extreme
, delta
;
2605 tree type
= TREE_TYPE (base
), unsigned_type
;
2608 if (TREE_CODE (step
) != INTEGER_CST
|| integer_zerop (step
))
2611 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2613 fprintf (dump_file
, "Induction variable (");
2614 print_generic_expr (dump_file
, TREE_TYPE (base
), TDF_SLIM
);
2615 fprintf (dump_file
, ") ");
2616 print_generic_expr (dump_file
, base
, TDF_SLIM
);
2617 fprintf (dump_file
, " + ");
2618 print_generic_expr (dump_file
, step
, TDF_SLIM
);
2619 fprintf (dump_file
, " * iteration does not wrap in statement ");
2620 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2621 fprintf (dump_file
, " in loop %d.\n", loop
->num
);
2624 unsigned_type
= unsigned_type_for (type
);
2625 base
= fold_convert (unsigned_type
, base
);
2626 step
= fold_convert (unsigned_type
, step
);
2628 if (tree_int_cst_sign_bit (step
))
2630 extreme
= fold_convert (unsigned_type
, low
);
2631 if (TREE_CODE (base
) != INTEGER_CST
)
2632 base
= fold_convert (unsigned_type
, high
);
2633 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
2634 step
= fold_build1 (NEGATE_EXPR
, unsigned_type
, step
);
2638 extreme
= fold_convert (unsigned_type
, high
);
2639 if (TREE_CODE (base
) != INTEGER_CST
)
2640 base
= fold_convert (unsigned_type
, low
);
2641 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
2644 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
2645 would get out of the range. */
2646 niter_bound
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step
);
2647 max
= derive_constant_upper_bound (niter_bound
);
2648 record_estimate (loop
, niter_bound
, max
, stmt
, false, realistic
, upper
);
2651 /* Determine information about number of iterations a LOOP from the index
2652 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
2653 guaranteed to be executed in every iteration of LOOP. Callback for
2664 idx_infer_loop_bounds (tree base
, tree
*idx
, void *dta
)
2666 struct ilb_data
*data
= (struct ilb_data
*) dta
;
2667 tree ev
, init
, step
;
2668 tree low
, high
, type
, next
;
2669 bool sign
, upper
= data
->reliable
, at_end
= false;
2670 struct loop
*loop
= data
->loop
;
2672 if (TREE_CODE (base
) != ARRAY_REF
)
2675 /* For arrays at the end of the structure, we are not guaranteed that they
2676 do not really extend over their declared size. However, for arrays of
2677 size greater than one, this is unlikely to be intended. */
2678 if (array_at_struct_end_p (base
))
2684 ev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, *idx
));
2685 init
= initial_condition (ev
);
2686 step
= evolution_part_in_loop_num (ev
, loop
->num
);
2690 || TREE_CODE (step
) != INTEGER_CST
2691 || integer_zerop (step
)
2692 || tree_contains_chrecs (init
, NULL
)
2693 || chrec_contains_symbols_defined_in_loop (init
, loop
->num
))
2696 low
= array_ref_low_bound (base
);
2697 high
= array_ref_up_bound (base
);
2699 /* The case of nonconstant bounds could be handled, but it would be
2701 if (TREE_CODE (low
) != INTEGER_CST
2703 || TREE_CODE (high
) != INTEGER_CST
)
2705 sign
= tree_int_cst_sign_bit (step
);
2706 type
= TREE_TYPE (step
);
2708 /* The array of length 1 at the end of a structure most likely extends
2709 beyond its bounds. */
2711 && operand_equal_p (low
, high
, 0))
2714 /* In case the relevant bound of the array does not fit in type, or
2715 it does, but bound + step (in type) still belongs into the range of the
2716 array, the index may wrap and still stay within the range of the array
2717 (consider e.g. if the array is indexed by the full range of
2720 To make things simpler, we require both bounds to fit into type, although
2721 there are cases where this would not be strictly necessary. */
2722 if (!int_fits_type_p (high
, type
)
2723 || !int_fits_type_p (low
, type
))
2725 low
= fold_convert (type
, low
);
2726 high
= fold_convert (type
, high
);
2729 next
= fold_binary (PLUS_EXPR
, type
, low
, step
);
2731 next
= fold_binary (PLUS_EXPR
, type
, high
, step
);
2733 if (tree_int_cst_compare (low
, next
) <= 0
2734 && tree_int_cst_compare (next
, high
) <= 0)
2737 record_nonwrapping_iv (loop
, init
, step
, data
->stmt
, low
, high
, true, upper
);
2741 /* Determine information about number of iterations a LOOP from the bounds
2742 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
2743 STMT is guaranteed to be executed in every iteration of LOOP.*/
2746 infer_loop_bounds_from_ref (struct loop
*loop
, gimple stmt
, tree ref
,
2749 struct ilb_data data
;
2753 data
.reliable
= reliable
;
2754 for_each_index (&ref
, idx_infer_loop_bounds
, &data
);
2757 /* Determine information about number of iterations of a LOOP from the way
2758 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
2759 executed in every iteration of LOOP. */
2762 infer_loop_bounds_from_array (struct loop
*loop
, gimple stmt
, bool reliable
)
2764 if (is_gimple_assign (stmt
))
2766 tree op0
= gimple_assign_lhs (stmt
);
2767 tree op1
= gimple_assign_rhs1 (stmt
);
2769 /* For each memory access, analyze its access function
2770 and record a bound on the loop iteration domain. */
2771 if (REFERENCE_CLASS_P (op0
))
2772 infer_loop_bounds_from_ref (loop
, stmt
, op0
, reliable
);
2774 if (REFERENCE_CLASS_P (op1
))
2775 infer_loop_bounds_from_ref (loop
, stmt
, op1
, reliable
);
2777 else if (is_gimple_call (stmt
))
2780 unsigned i
, n
= gimple_call_num_args (stmt
);
2782 lhs
= gimple_call_lhs (stmt
);
2783 if (lhs
&& REFERENCE_CLASS_P (lhs
))
2784 infer_loop_bounds_from_ref (loop
, stmt
, lhs
, reliable
);
2786 for (i
= 0; i
< n
; i
++)
2788 arg
= gimple_call_arg (stmt
, i
);
2789 if (REFERENCE_CLASS_P (arg
))
2790 infer_loop_bounds_from_ref (loop
, stmt
, arg
, reliable
);
2795 /* Determine information about number of iterations of a LOOP from the fact
2796 that pointer arithmetics in STMT does not overflow. */
2799 infer_loop_bounds_from_pointer_arith (struct loop
*loop
, gimple stmt
)
2801 tree def
, base
, step
, scev
, type
, low
, high
;
2804 if (!is_gimple_assign (stmt
)
2805 || gimple_assign_rhs_code (stmt
) != POINTER_PLUS_EXPR
)
2808 def
= gimple_assign_lhs (stmt
);
2809 if (TREE_CODE (def
) != SSA_NAME
)
2812 type
= TREE_TYPE (def
);
2813 if (!nowrap_type_p (type
))
2816 ptr
= gimple_assign_rhs1 (stmt
);
2817 if (!expr_invariant_in_loop_p (loop
, ptr
))
2820 var
= gimple_assign_rhs2 (stmt
);
2821 if (TYPE_PRECISION (type
) != TYPE_PRECISION (TREE_TYPE (var
)))
2824 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
2825 if (chrec_contains_undetermined (scev
))
2828 base
= initial_condition_in_loop_num (scev
, loop
->num
);
2829 step
= evolution_part_in_loop_num (scev
, loop
->num
);
2832 || TREE_CODE (step
) != INTEGER_CST
2833 || tree_contains_chrecs (base
, NULL
)
2834 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
2837 low
= lower_bound_in_type (type
, type
);
2838 high
= upper_bound_in_type (type
, type
);
2840 /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
2841 produce a NULL pointer. The contrary would mean NULL points to an object,
2842 while NULL is supposed to compare unequal with the address of all objects.
2843 Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
2844 NULL pointer since that would mean wrapping, which we assume here not to
2845 happen. So, we can exclude NULL from the valid range of pointer
2847 if (flag_delete_null_pointer_checks
&& int_cst_value (low
) == 0)
2848 low
= build_int_cstu (TREE_TYPE (low
), TYPE_ALIGN_UNIT (TREE_TYPE (type
)));
2850 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
2853 /* Determine information about number of iterations of a LOOP from the fact
2854 that signed arithmetics in STMT does not overflow. */
2857 infer_loop_bounds_from_signedness (struct loop
*loop
, gimple stmt
)
2859 tree def
, base
, step
, scev
, type
, low
, high
;
2861 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2864 def
= gimple_assign_lhs (stmt
);
2866 if (TREE_CODE (def
) != SSA_NAME
)
2869 type
= TREE_TYPE (def
);
2870 if (!INTEGRAL_TYPE_P (type
)
2871 || !TYPE_OVERFLOW_UNDEFINED (type
))
2874 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
2875 if (chrec_contains_undetermined (scev
))
2878 base
= initial_condition_in_loop_num (scev
, loop
->num
);
2879 step
= evolution_part_in_loop_num (scev
, loop
->num
);
2882 || TREE_CODE (step
) != INTEGER_CST
2883 || tree_contains_chrecs (base
, NULL
)
2884 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
2887 low
= lower_bound_in_type (type
, type
);
2888 high
= upper_bound_in_type (type
, type
);
2890 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
2893 /* The following analyzers are extracting informations on the bounds
2894 of LOOP from the following undefined behaviors:
2896 - data references should not access elements over the statically
2899 - signed variables should not overflow when flag_wrapv is not set.
2903 infer_loop_bounds_from_undefined (struct loop
*loop
)
2907 gimple_stmt_iterator bsi
;
2911 bbs
= get_loop_body (loop
);
2913 for (i
= 0; i
< loop
->num_nodes
; i
++)
2917 /* If BB is not executed in each iteration of the loop, we cannot
2918 use the operations in it to infer reliable upper bound on the
2919 # of iterations of the loop. However, we can use it as a guess. */
2920 reliable
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
);
2922 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2924 gimple stmt
= gsi_stmt (bsi
);
2926 infer_loop_bounds_from_array (loop
, stmt
, reliable
);
2930 infer_loop_bounds_from_signedness (loop
, stmt
);
2931 infer_loop_bounds_from_pointer_arith (loop
, stmt
);
2940 /* Converts VAL to double_int. */
2943 gcov_type_to_double_int (gcov_type val
)
2947 ret
.low
= (unsigned HOST_WIDE_INT
) val
;
2948 /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by
2949 the size of type. */
2950 val
>>= HOST_BITS_PER_WIDE_INT
- 1;
2952 ret
.high
= (unsigned HOST_WIDE_INT
) val
;
2957 /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
2958 is true also use estimates derived from undefined behavior. */
2961 estimate_numbers_of_iterations_loop (struct loop
*loop
)
2963 VEC (edge
, heap
) *exits
;
2966 struct tree_niter_desc niter_desc
;
2970 /* Give up if we already have tried to compute an estimation. */
2971 if (loop
->estimate_state
!= EST_NOT_COMPUTED
)
2974 loop
->estimate_state
= EST_AVAILABLE
;
2975 /* Force estimate compuation but leave any existing upper bound in place. */
2976 loop
->any_estimate
= false;
2978 exits
= get_loop_exit_edges (loop
);
2979 FOR_EACH_VEC_ELT (edge
, exits
, i
, ex
)
2981 if (!number_of_iterations_exit (loop
, ex
, &niter_desc
, false))
2984 niter
= niter_desc
.niter
;
2985 type
= TREE_TYPE (niter
);
2986 if (TREE_CODE (niter_desc
.may_be_zero
) != INTEGER_CST
)
2987 niter
= build3 (COND_EXPR
, type
, niter_desc
.may_be_zero
,
2988 build_int_cst (type
, 0),
2990 record_estimate (loop
, niter
, niter_desc
.max
,
2991 last_stmt (ex
->src
),
2994 VEC_free (edge
, heap
, exits
);
2996 infer_loop_bounds_from_undefined (loop
);
2998 /* If we have a measured profile, use it to estimate the number of
3000 if (loop
->header
->count
!= 0)
3002 gcov_type nit
= expected_loop_iterations_unbounded (loop
) + 1;
3003 bound
= gcov_type_to_double_int (nit
);
3004 record_niter_bound (loop
, bound
, true, false);
3008 /* Sets NIT to the estimated number of executions of the latch of the
3009 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
3010 large as the number of iterations. If we have no reliable estimate,
3011 the function returns false, otherwise returns true. */
3014 estimated_loop_iterations (struct loop
*loop
, double_int
*nit
)
3016 estimate_numbers_of_iterations_loop (loop
);
3017 if (!loop
->any_estimate
)
3020 *nit
= loop
->nb_iterations_estimate
;
3024 /* Sets NIT to an upper bound for the maximum number of executions of the
3025 latch of the LOOP. If we have no reliable estimate, the function returns
3026 false, otherwise returns true. */
3029 max_loop_iterations (struct loop
*loop
, double_int
*nit
)
3031 estimate_numbers_of_iterations_loop (loop
);
3032 if (!loop
->any_upper_bound
)
3035 *nit
= loop
->nb_iterations_upper_bound
;
3039 /* Similar to estimated_loop_iterations, but returns the estimate only
3040 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3041 on the number of iterations of LOOP could not be derived, returns -1. */
3044 estimated_loop_iterations_int (struct loop
*loop
)
3047 HOST_WIDE_INT hwi_nit
;
3049 if (!estimated_loop_iterations (loop
, &nit
))
3052 if (!double_int_fits_in_shwi_p (nit
))
3054 hwi_nit
= double_int_to_shwi (nit
);
3056 return hwi_nit
< 0 ? -1 : hwi_nit
;
3059 /* Similar to max_loop_iterations, but returns the estimate only
3060 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3061 on the number of iterations of LOOP could not be derived, returns -1. */
3064 max_loop_iterations_int (struct loop
*loop
)
3067 HOST_WIDE_INT hwi_nit
;
3069 if (!max_loop_iterations (loop
, &nit
))
3072 if (!double_int_fits_in_shwi_p (nit
))
3074 hwi_nit
= double_int_to_shwi (nit
);
3076 return hwi_nit
< 0 ? -1 : hwi_nit
;
3079 /* Returns an upper bound on the number of executions of statements
3080 in the LOOP. For statements before the loop exit, this exceeds
3081 the number of execution of the latch by one. */
3084 max_stmt_executions_int (struct loop
*loop
)
3086 HOST_WIDE_INT nit
= max_loop_iterations_int (loop
);
3092 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
3094 /* If the computation overflows, return -1. */
3095 return snit
< 0 ? -1 : snit
;
3098 /* Returns an estimate for the number of executions of statements
3099 in the LOOP. For statements before the loop exit, this exceeds
3100 the number of execution of the latch by one. */
3103 estimated_stmt_executions_int (struct loop
*loop
)
3105 HOST_WIDE_INT nit
= estimated_loop_iterations_int (loop
);
3111 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
3113 /* If the computation overflows, return -1. */
3114 return snit
< 0 ? -1 : snit
;
3117 /* Sets NIT to the estimated maximum number of executions of the latch of the
3118 LOOP, plus one. If we have no reliable estimate, the function returns
3119 false, otherwise returns true. */
3122 max_stmt_executions (struct loop
*loop
, double_int
*nit
)
3124 double_int nit_minus_one
;
3126 if (!max_loop_iterations (loop
, nit
))
3129 nit_minus_one
= *nit
;
3131 *nit
= double_int_add (*nit
, double_int_one
);
3133 return double_int_ucmp (*nit
, nit_minus_one
) > 0;
3136 /* Sets NIT to the estimated number of executions of the latch of the
3137 LOOP, plus one. If we have no reliable estimate, the function returns
3138 false, otherwise returns true. */
3141 estimated_stmt_executions (struct loop
*loop
, double_int
*nit
)
3143 double_int nit_minus_one
;
3145 if (!estimated_loop_iterations (loop
, nit
))
3148 nit_minus_one
= *nit
;
3150 *nit
= double_int_add (*nit
, double_int_one
);
3152 return double_int_ucmp (*nit
, nit_minus_one
) > 0;
3155 /* Records estimates on numbers of iterations of loops. */
3158 estimate_numbers_of_iterations (void)
3163 /* We don't want to issue signed overflow warnings while getting
3164 loop iteration estimates. */
3165 fold_defer_overflow_warnings ();
3167 FOR_EACH_LOOP (li
, loop
, 0)
3169 estimate_numbers_of_iterations_loop (loop
);
3172 fold_undefer_and_ignore_overflow_warnings ();
3175 /* Returns true if statement S1 dominates statement S2. */
3178 stmt_dominates_stmt_p (gimple s1
, gimple s2
)
3180 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
3188 gimple_stmt_iterator bsi
;
3190 if (gimple_code (s2
) == GIMPLE_PHI
)
3193 if (gimple_code (s1
) == GIMPLE_PHI
)
3196 for (bsi
= gsi_start_bb (bb1
); gsi_stmt (bsi
) != s2
; gsi_next (&bsi
))
3197 if (gsi_stmt (bsi
) == s1
)
3203 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
3206 /* Returns true when we can prove that the number of executions of
3207 STMT in the loop is at most NITER, according to the bound on
3208 the number of executions of the statement NITER_BOUND->stmt recorded in
3209 NITER_BOUND. If STMT is NULL, we must prove this bound for all
3210 statements in the loop. */
3213 n_of_executions_at_most (gimple stmt
,
3214 struct nb_iter_bound
*niter_bound
,
3217 double_int bound
= niter_bound
->bound
;
3218 tree nit_type
= TREE_TYPE (niter
), e
;
3221 gcc_assert (TYPE_UNSIGNED (nit_type
));
3223 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
3224 the number of iterations is small. */
3225 if (!double_int_fits_to_tree_p (nit_type
, bound
))
3228 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3229 times. This means that:
3231 -- if NITER_BOUND->is_exit is true, then everything before
3232 NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3233 times, and everything after it at most NITER_BOUND->bound times.
3235 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
3236 is executed, then NITER_BOUND->stmt is executed as well in the same
3237 iteration (we conclude that if both statements belong to the same
3238 basic block, or if STMT is after NITER_BOUND->stmt), then STMT
3239 is executed at most NITER_BOUND->bound + 1 times. Otherwise STMT is
3240 executed at most NITER_BOUND->bound + 2 times. */
3242 if (niter_bound
->is_exit
)
3245 && stmt
!= niter_bound
->stmt
3246 && stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
3254 || (gimple_bb (stmt
) != gimple_bb (niter_bound
->stmt
)
3255 && !stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
)))
3257 bound
= double_int_add (bound
, double_int_one
);
3258 if (double_int_zero_p (bound
)
3259 || !double_int_fits_to_tree_p (nit_type
, bound
))
3265 e
= fold_binary (cmp
, boolean_type_node
,
3266 niter
, double_int_to_tree (nit_type
, bound
));
3267 return e
&& integer_nonzerop (e
);
3270 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
3273 nowrap_type_p (tree type
)
3275 if (INTEGRAL_TYPE_P (type
)
3276 && TYPE_OVERFLOW_UNDEFINED (type
))
3279 if (POINTER_TYPE_P (type
))
3285 /* Return false only when the induction variable BASE + STEP * I is
3286 known to not overflow: i.e. when the number of iterations is small
3287 enough with respect to the step and initial condition in order to
3288 keep the evolution confined in TYPEs bounds. Return true when the
3289 iv is known to overflow or when the property is not computable.
3291 USE_OVERFLOW_SEMANTICS is true if this function should assume that
3292 the rules for overflow of the given language apply (e.g., that signed
3293 arithmetics in C does not overflow). */
3296 scev_probably_wraps_p (tree base
, tree step
,
3297 gimple at_stmt
, struct loop
*loop
,
3298 bool use_overflow_semantics
)
3300 struct nb_iter_bound
*bound
;
3301 tree delta
, step_abs
;
3302 tree unsigned_type
, valid_niter
;
3303 tree type
= TREE_TYPE (step
);
3305 /* FIXME: We really need something like
3306 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
3308 We used to test for the following situation that frequently appears
3309 during address arithmetics:
3311 D.1621_13 = (long unsigned intD.4) D.1620_12;
3312 D.1622_14 = D.1621_13 * 8;
3313 D.1623_15 = (doubleD.29 *) D.1622_14;
3315 And derived that the sequence corresponding to D_14
3316 can be proved to not wrap because it is used for computing a
3317 memory access; however, this is not really the case -- for example,
3318 if D_12 = (unsigned char) [254,+,1], then D_14 has values
3319 2032, 2040, 0, 8, ..., but the code is still legal. */
3321 if (chrec_contains_undetermined (base
)
3322 || chrec_contains_undetermined (step
))
3325 if (integer_zerop (step
))
3328 /* If we can use the fact that signed and pointer arithmetics does not
3329 wrap, we are done. */
3330 if (use_overflow_semantics
&& nowrap_type_p (TREE_TYPE (base
)))
3333 /* To be able to use estimates on number of iterations of the loop,
3334 we must have an upper bound on the absolute value of the step. */
3335 if (TREE_CODE (step
) != INTEGER_CST
)
3338 /* Don't issue signed overflow warnings. */
3339 fold_defer_overflow_warnings ();
3341 /* Otherwise, compute the number of iterations before we reach the
3342 bound of the type, and verify that the loop is exited before this
3344 unsigned_type
= unsigned_type_for (type
);
3345 base
= fold_convert (unsigned_type
, base
);
3347 if (tree_int_cst_sign_bit (step
))
3349 tree extreme
= fold_convert (unsigned_type
,
3350 lower_bound_in_type (type
, type
));
3351 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
3352 step_abs
= fold_build1 (NEGATE_EXPR
, unsigned_type
,
3353 fold_convert (unsigned_type
, step
));
3357 tree extreme
= fold_convert (unsigned_type
,
3358 upper_bound_in_type (type
, type
));
3359 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
3360 step_abs
= fold_convert (unsigned_type
, step
);
3363 valid_niter
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step_abs
);
3365 estimate_numbers_of_iterations_loop (loop
);
3366 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
3368 if (n_of_executions_at_most (at_stmt
, bound
, valid_niter
))
3370 fold_undefer_and_ignore_overflow_warnings ();
3375 fold_undefer_and_ignore_overflow_warnings ();
3377 /* At this point we still don't have a proof that the iv does not
3378 overflow: give up. */
3382 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
3385 free_numbers_of_iterations_estimates_loop (struct loop
*loop
)
3387 struct nb_iter_bound
*bound
, *next
;
3389 loop
->nb_iterations
= NULL
;
3390 loop
->estimate_state
= EST_NOT_COMPUTED
;
3391 for (bound
= loop
->bounds
; bound
; bound
= next
)
3397 loop
->bounds
= NULL
;
3400 /* Frees the information on upper bounds on numbers of iterations of loops. */
3403 free_numbers_of_iterations_estimates (void)
3408 FOR_EACH_LOOP (li
, loop
, 0)
3410 free_numbers_of_iterations_estimates_loop (loop
);
3414 /* Substitute value VAL for ssa name NAME inside expressions held
3418 substitute_in_loop_info (struct loop
*loop
, tree name
, tree val
)
3420 loop
->nb_iterations
= simplify_replace_tree (loop
->nb_iterations
, name
, val
);