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"
29 #include "tree-pretty-print.h"
30 #include "gimple-pretty-print.h"
32 #include "tree-flow.h"
33 #include "tree-dump.h"
35 #include "tree-pass.h"
37 #include "tree-chrec.h"
38 #include "tree-scalar-evolution.h"
39 #include "tree-data-ref.h"
42 #include "diagnostic-core.h"
43 #include "tree-inline.h"
46 #define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
48 /* The maximum number of dominator BBs we search for conditions
49 of loop header copies we use for simplifying a conditional
51 #define MAX_DOMINATORS_TO_WALK 8
55 Analysis of number of iterations of an affine exit test.
59 /* Bounds on some value, BELOW <= X <= UP. */
67 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */
70 split_to_var_and_offset (tree expr
, tree
*var
, mpz_t offset
)
72 tree type
= TREE_TYPE (expr
);
78 mpz_set_ui (offset
, 0);
80 switch (TREE_CODE (expr
))
87 case POINTER_PLUS_EXPR
:
88 op0
= TREE_OPERAND (expr
, 0);
89 op1
= TREE_OPERAND (expr
, 1);
91 if (TREE_CODE (op1
) != INTEGER_CST
)
95 /* Always sign extend the offset. */
96 off
= tree_to_double_int (op1
);
97 off
= double_int_sext (off
, TYPE_PRECISION (type
));
98 mpz_set_double_int (offset
, off
, false);
100 mpz_neg (offset
, offset
);
104 *var
= build_int_cst_type (type
, 0);
105 off
= tree_to_double_int (expr
);
106 mpz_set_double_int (offset
, off
, TYPE_UNSIGNED (type
));
114 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
115 in TYPE to MIN and MAX. */
118 determine_value_range (tree type
, tree var
, mpz_t off
,
119 mpz_t min
, mpz_t max
)
121 /* If the expression is a constant, we know its value exactly. */
122 if (integer_zerop (var
))
129 /* If the computation may wrap, we know nothing about the value, except for
130 the range of the type. */
131 get_type_static_bounds (type
, min
, max
);
132 if (!nowrap_type_p (type
))
135 /* Since the addition of OFF does not wrap, if OFF is positive, then we may
136 add it to MIN, otherwise to MAX. */
137 if (mpz_sgn (off
) < 0)
138 mpz_add (max
, max
, off
);
140 mpz_add (min
, min
, off
);
143 /* Stores the bounds on the difference of the values of the expressions
144 (var + X) and (var + Y), computed in TYPE, to BNDS. */
147 bound_difference_of_offsetted_base (tree type
, mpz_t x
, mpz_t y
,
150 int rel
= mpz_cmp (x
, y
);
151 bool may_wrap
= !nowrap_type_p (type
);
154 /* If X == Y, then the expressions are always equal.
155 If X > Y, there are the following possibilities:
156 a) neither of var + X and var + Y overflow or underflow, or both of
157 them do. Then their difference is X - Y.
158 b) var + X overflows, and var + Y does not. Then the values of the
159 expressions are var + X - M and var + Y, where M is the range of
160 the type, and their difference is X - Y - M.
161 c) var + Y underflows and var + X does not. Their difference again
163 Therefore, if the arithmetics in type does not overflow, then the
164 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
165 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
166 (X - Y, X - Y + M). */
170 mpz_set_ui (bnds
->below
, 0);
171 mpz_set_ui (bnds
->up
, 0);
176 mpz_set_double_int (m
, double_int_mask (TYPE_PRECISION (type
)), true);
177 mpz_add_ui (m
, m
, 1);
178 mpz_sub (bnds
->up
, x
, y
);
179 mpz_set (bnds
->below
, bnds
->up
);
184 mpz_sub (bnds
->below
, bnds
->below
, m
);
186 mpz_add (bnds
->up
, bnds
->up
, m
);
192 /* From condition C0 CMP C1 derives information regarding the
193 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
194 and stores it to BNDS. */
197 refine_bounds_using_guard (tree type
, tree varx
, mpz_t offx
,
198 tree vary
, mpz_t offy
,
199 tree c0
, enum tree_code cmp
, tree c1
,
202 tree varc0
, varc1
, tmp
, ctype
;
203 mpz_t offc0
, offc1
, loffx
, loffy
, bnd
;
205 bool no_wrap
= nowrap_type_p (type
);
214 STRIP_SIGN_NOPS (c0
);
215 STRIP_SIGN_NOPS (c1
);
216 ctype
= TREE_TYPE (c0
);
217 if (!useless_type_conversion_p (ctype
, type
))
223 /* We could derive quite precise information from EQ_EXPR, however, such
224 a guard is unlikely to appear, so we do not bother with handling
229 /* NE_EXPR comparisons do not contain much of useful information, except for
230 special case of comparing with the bounds of the type. */
231 if (TREE_CODE (c1
) != INTEGER_CST
232 || !INTEGRAL_TYPE_P (type
))
235 /* Ensure that the condition speaks about an expression in the same type
237 ctype
= TREE_TYPE (c0
);
238 if (TYPE_PRECISION (ctype
) != TYPE_PRECISION (type
))
240 c0
= fold_convert (type
, c0
);
241 c1
= fold_convert (type
, c1
);
243 if (TYPE_MIN_VALUE (type
)
244 && operand_equal_p (c1
, TYPE_MIN_VALUE (type
), 0))
249 if (TYPE_MAX_VALUE (type
)
250 && operand_equal_p (c1
, TYPE_MAX_VALUE (type
), 0))
263 split_to_var_and_offset (expand_simple_operations (c0
), &varc0
, offc0
);
264 split_to_var_and_offset (expand_simple_operations (c1
), &varc1
, offc1
);
266 /* We are only interested in comparisons of expressions based on VARX and
267 VARY. TODO -- we might also be able to derive some bounds from
268 expressions containing just one of the variables. */
270 if (operand_equal_p (varx
, varc1
, 0))
272 tmp
= varc0
; varc0
= varc1
; varc1
= tmp
;
273 mpz_swap (offc0
, offc1
);
274 cmp
= swap_tree_comparison (cmp
);
277 if (!operand_equal_p (varx
, varc0
, 0)
278 || !operand_equal_p (vary
, varc1
, 0))
281 mpz_init_set (loffx
, offx
);
282 mpz_init_set (loffy
, offy
);
284 if (cmp
== GT_EXPR
|| cmp
== GE_EXPR
)
286 tmp
= varx
; varx
= vary
; vary
= tmp
;
287 mpz_swap (offc0
, offc1
);
288 mpz_swap (loffx
, loffy
);
289 cmp
= swap_tree_comparison (cmp
);
293 /* If there is no overflow, the condition implies that
295 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
297 The overflows and underflows may complicate things a bit; each
298 overflow decreases the appropriate offset by M, and underflow
299 increases it by M. The above inequality would not necessarily be
302 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
303 VARX + OFFC0 overflows, but VARX + OFFX does not.
304 This may only happen if OFFX < OFFC0.
305 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
306 VARY + OFFC1 underflows and VARY + OFFY does not.
307 This may only happen if OFFY > OFFC1. */
316 x_ok
= (integer_zerop (varx
)
317 || mpz_cmp (loffx
, offc0
) >= 0);
318 y_ok
= (integer_zerop (vary
)
319 || mpz_cmp (loffy
, offc1
) <= 0);
325 mpz_sub (bnd
, loffx
, loffy
);
326 mpz_add (bnd
, bnd
, offc1
);
327 mpz_sub (bnd
, bnd
, offc0
);
330 mpz_sub_ui (bnd
, bnd
, 1);
335 if (mpz_cmp (bnds
->below
, bnd
) < 0)
336 mpz_set (bnds
->below
, bnd
);
340 if (mpz_cmp (bnd
, bnds
->up
) < 0)
341 mpz_set (bnds
->up
, bnd
);
353 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
354 The subtraction is considered to be performed in arbitrary precision,
357 We do not attempt to be too clever regarding the value ranges of X and
358 Y; most of the time, they are just integers or ssa names offsetted by
359 integer. However, we try to use the information contained in the
360 comparisons before the loop (usually created by loop header copying). */
363 bound_difference (struct loop
*loop
, tree x
, tree y
, bounds
*bnds
)
365 tree type
= TREE_TYPE (x
);
368 mpz_t minx
, maxx
, miny
, maxy
;
376 /* Get rid of unnecessary casts, but preserve the value of
381 mpz_init (bnds
->below
);
385 split_to_var_and_offset (x
, &varx
, offx
);
386 split_to_var_and_offset (y
, &vary
, offy
);
388 if (!integer_zerop (varx
)
389 && operand_equal_p (varx
, vary
, 0))
391 /* Special case VARX == VARY -- we just need to compare the
392 offsets. The matters are a bit more complicated in the
393 case addition of offsets may wrap. */
394 bound_difference_of_offsetted_base (type
, offx
, offy
, bnds
);
398 /* Otherwise, use the value ranges to determine the initial
399 estimates on below and up. */
404 determine_value_range (type
, varx
, offx
, minx
, maxx
);
405 determine_value_range (type
, vary
, offy
, miny
, maxy
);
407 mpz_sub (bnds
->below
, minx
, maxy
);
408 mpz_sub (bnds
->up
, maxx
, miny
);
415 /* If both X and Y are constants, we cannot get any more precise. */
416 if (integer_zerop (varx
) && integer_zerop (vary
))
419 /* Now walk the dominators of the loop header and use the entry
420 guards to refine the estimates. */
421 for (bb
= loop
->header
;
422 bb
!= ENTRY_BLOCK_PTR
&& cnt
< MAX_DOMINATORS_TO_WALK
;
423 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
425 if (!single_pred_p (bb
))
427 e
= single_pred_edge (bb
);
429 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
432 cond
= last_stmt (e
->src
);
433 c0
= gimple_cond_lhs (cond
);
434 cmp
= gimple_cond_code (cond
);
435 c1
= gimple_cond_rhs (cond
);
437 if (e
->flags
& EDGE_FALSE_VALUE
)
438 cmp
= invert_tree_comparison (cmp
, false);
440 refine_bounds_using_guard (type
, varx
, offx
, vary
, offy
,
450 /* Update the bounds in BNDS that restrict the value of X to the bounds
451 that restrict the value of X + DELTA. X can be obtained as a
452 difference of two values in TYPE. */
455 bounds_add (bounds
*bnds
, double_int delta
, tree type
)
460 mpz_set_double_int (mdelta
, delta
, false);
463 mpz_set_double_int (max
, double_int_mask (TYPE_PRECISION (type
)), true);
465 mpz_add (bnds
->up
, bnds
->up
, mdelta
);
466 mpz_add (bnds
->below
, bnds
->below
, mdelta
);
468 if (mpz_cmp (bnds
->up
, max
) > 0)
469 mpz_set (bnds
->up
, max
);
472 if (mpz_cmp (bnds
->below
, max
) < 0)
473 mpz_set (bnds
->below
, max
);
479 /* Update the bounds in BNDS that restrict the value of X to the bounds
480 that restrict the value of -X. */
483 bounds_negate (bounds
*bnds
)
487 mpz_init_set (tmp
, bnds
->up
);
488 mpz_neg (bnds
->up
, bnds
->below
);
489 mpz_neg (bnds
->below
, tmp
);
493 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
496 inverse (tree x
, tree mask
)
498 tree type
= TREE_TYPE (x
);
500 unsigned ctr
= tree_floor_log2 (mask
);
502 if (TYPE_PRECISION (type
) <= HOST_BITS_PER_WIDE_INT
)
504 unsigned HOST_WIDE_INT ix
;
505 unsigned HOST_WIDE_INT imask
;
506 unsigned HOST_WIDE_INT irslt
= 1;
508 gcc_assert (cst_and_fits_in_hwi (x
));
509 gcc_assert (cst_and_fits_in_hwi (mask
));
511 ix
= int_cst_value (x
);
512 imask
= int_cst_value (mask
);
521 rslt
= build_int_cst_type (type
, irslt
);
525 rslt
= build_int_cst (type
, 1);
528 rslt
= int_const_binop (MULT_EXPR
, rslt
, x
);
529 x
= int_const_binop (MULT_EXPR
, x
, x
);
531 rslt
= int_const_binop (BIT_AND_EXPR
, rslt
, mask
);
537 /* Derives the upper bound BND on the number of executions of loop with exit
538 condition S * i <> C. If NO_OVERFLOW is true, then the control variable of
539 the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed
540 that the loop ends through this exit, i.e., the induction variable ever
541 reaches the value of C.
543 The value C is equal to final - base, where final and base are the final and
544 initial value of the actual induction variable in the analysed loop. BNDS
545 bounds the value of this difference when computed in signed type with
546 unbounded range, while the computation of C is performed in an unsigned
547 type with the range matching the range of the type of the induction variable.
548 In particular, BNDS.up contains an upper bound on C in the following cases:
549 -- if the iv must reach its final value without overflow, i.e., if
550 NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
551 -- if final >= base, which we know to hold when BNDS.below >= 0. */
554 number_of_iterations_ne_max (mpz_t bnd
, bool no_overflow
, tree c
, tree s
,
555 bounds
*bnds
, bool exit_must_be_taken
)
559 bool bnds_u_valid
= ((no_overflow
&& exit_must_be_taken
)
560 || mpz_sgn (bnds
->below
) >= 0);
562 if (multiple_of_p (TREE_TYPE (c
), 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
= double_int_mask (TYPE_PRECISION (TREE_TYPE (c
))
580 - tree_low_cst (num_ending_zeros (s
), 1));
581 mpz_set_double_int (bnd
, max
, true);
585 /* Now we know that the induction variable does not overflow, so the loop
586 iterates at most (range of type / S) times. */
587 mpz_set_double_int (bnd
, double_int_mask (TYPE_PRECISION (TREE_TYPE (c
))),
590 /* If the induction variable is guaranteed to reach the value of C before
592 if (exit_must_be_taken
)
594 /* ... then we can strenghten this to C / S, and possibly we can use
595 the upper bound on C given by BNDS. */
596 if (TREE_CODE (c
) == INTEGER_CST
)
597 mpz_set_double_int (bnd
, tree_to_double_int (c
), true);
598 else if (bnds_u_valid
)
599 mpz_set (bnd
, bnds
->up
);
603 mpz_set_double_int (d
, tree_to_double_int (s
), true);
604 mpz_fdiv_q (bnd
, bnd
, d
);
608 /* Determines number of iterations of loop whose ending condition
609 is IV <> FINAL. TYPE is the type of the iv. The number of
610 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
611 we know that the exit must be taken eventually, i.e., that the IV
612 ever reaches the value FINAL (we derived this earlier, and possibly set
613 NITER->assumptions to make sure this is the case). BNDS contains the
614 bounds on the difference FINAL - IV->base. */
617 number_of_iterations_ne (tree type
, affine_iv
*iv
, tree final
,
618 struct tree_niter_desc
*niter
, bool exit_must_be_taken
,
621 tree niter_type
= unsigned_type_for (type
);
622 tree s
, c
, d
, bits
, assumption
, tmp
, bound
;
625 niter
->control
= *iv
;
626 niter
->bound
= final
;
627 niter
->cmp
= NE_EXPR
;
629 /* Rearrange the terms so that we get inequality S * i <> C, with S
630 positive. Also cast everything to the unsigned type. If IV does
631 not overflow, BNDS bounds the value of C. Also, this is the
632 case if the computation |FINAL - IV->base| does not overflow, i.e.,
633 if BNDS->below in the result is nonnegative. */
634 if (tree_int_cst_sign_bit (iv
->step
))
636 s
= fold_convert (niter_type
,
637 fold_build1 (NEGATE_EXPR
, type
, iv
->step
));
638 c
= fold_build2 (MINUS_EXPR
, niter_type
,
639 fold_convert (niter_type
, iv
->base
),
640 fold_convert (niter_type
, final
));
641 bounds_negate (bnds
);
645 s
= fold_convert (niter_type
, iv
->step
);
646 c
= fold_build2 (MINUS_EXPR
, niter_type
,
647 fold_convert (niter_type
, final
),
648 fold_convert (niter_type
, iv
->base
));
652 number_of_iterations_ne_max (max
, iv
->no_overflow
, c
, s
, bnds
,
654 niter
->max
= mpz_get_double_int (niter_type
, max
, false);
657 /* First the trivial cases -- when the step is 1. */
658 if (integer_onep (s
))
664 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
665 is infinite. Otherwise, the number of iterations is
666 (inverse(s/d) * (c/d)) mod (size of mode/d). */
667 bits
= num_ending_zeros (s
);
668 bound
= build_low_bits_mask (niter_type
,
669 (TYPE_PRECISION (niter_type
)
670 - tree_low_cst (bits
, 1)));
672 d
= fold_binary_to_constant (LSHIFT_EXPR
, niter_type
,
673 build_int_cst (niter_type
, 1), bits
);
674 s
= fold_binary_to_constant (RSHIFT_EXPR
, niter_type
, s
, bits
);
676 if (!exit_must_be_taken
)
678 /* If we cannot assume that the exit is taken eventually, record the
679 assumptions for divisibility of c. */
680 assumption
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, c
, d
);
681 assumption
= fold_build2 (EQ_EXPR
, boolean_type_node
,
682 assumption
, build_int_cst (niter_type
, 0));
683 if (!integer_nonzerop (assumption
))
684 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
685 niter
->assumptions
, assumption
);
688 c
= fold_build2 (EXACT_DIV_EXPR
, niter_type
, c
, d
);
689 tmp
= fold_build2 (MULT_EXPR
, niter_type
, c
, inverse (s
, bound
));
690 niter
->niter
= fold_build2 (BIT_AND_EXPR
, niter_type
, tmp
, bound
);
694 /* Checks whether we can determine the final value of the control variable
695 of the loop with ending condition IV0 < IV1 (computed in TYPE).
696 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
697 of the step. The assumptions necessary to ensure that the computation
698 of the final value does not overflow are recorded in NITER. If we
699 find the final value, we adjust DELTA and return TRUE. Otherwise
700 we return false. BNDS bounds the value of IV1->base - IV0->base,
701 and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
702 true if we know that the exit must be taken eventually. */
705 number_of_iterations_lt_to_ne (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
706 struct tree_niter_desc
*niter
,
707 tree
*delta
, tree step
,
708 bool exit_must_be_taken
, bounds
*bnds
)
710 tree niter_type
= TREE_TYPE (step
);
711 tree mod
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, *delta
, step
);
714 tree assumption
= boolean_true_node
, bound
, noloop
;
715 bool ret
= false, fv_comp_no_overflow
;
717 if (POINTER_TYPE_P (type
))
720 if (TREE_CODE (mod
) != INTEGER_CST
)
722 if (integer_nonzerop (mod
))
723 mod
= fold_build2 (MINUS_EXPR
, niter_type
, step
, mod
);
724 tmod
= fold_convert (type1
, mod
);
727 mpz_set_double_int (mmod
, tree_to_double_int (mod
), true);
728 mpz_neg (mmod
, mmod
);
730 /* If the induction variable does not overflow and the exit is taken,
731 then the computation of the final value does not overflow. This is
732 also obviously the case if the new final value is equal to the
733 current one. Finally, we postulate this for pointer type variables,
734 as the code cannot rely on the object to that the pointer points being
735 placed at the end of the address space (and more pragmatically,
736 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
737 if (integer_zerop (mod
) || POINTER_TYPE_P (type
))
738 fv_comp_no_overflow
= true;
739 else if (!exit_must_be_taken
)
740 fv_comp_no_overflow
= false;
742 fv_comp_no_overflow
=
743 (iv0
->no_overflow
&& integer_nonzerop (iv0
->step
))
744 || (iv1
->no_overflow
&& integer_nonzerop (iv1
->step
));
746 if (integer_nonzerop (iv0
->step
))
748 /* The final value of the iv is iv1->base + MOD, assuming that this
749 computation does not overflow, and that
750 iv0->base <= iv1->base + MOD. */
751 if (!fv_comp_no_overflow
)
753 bound
= fold_build2 (MINUS_EXPR
, type1
,
754 TYPE_MAX_VALUE (type1
), tmod
);
755 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
757 if (integer_zerop (assumption
))
760 if (mpz_cmp (mmod
, bnds
->below
) < 0)
761 noloop
= boolean_false_node
;
762 else if (POINTER_TYPE_P (type
))
763 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
765 fold_build2 (POINTER_PLUS_EXPR
, type
,
768 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
770 fold_build2 (PLUS_EXPR
, type1
,
775 /* The final value of the iv is iv0->base - MOD, assuming that this
776 computation does not overflow, and that
777 iv0->base - MOD <= iv1->base. */
778 if (!fv_comp_no_overflow
)
780 bound
= fold_build2 (PLUS_EXPR
, type1
,
781 TYPE_MIN_VALUE (type1
), tmod
);
782 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
784 if (integer_zerop (assumption
))
787 if (mpz_cmp (mmod
, bnds
->below
) < 0)
788 noloop
= boolean_false_node
;
789 else if (POINTER_TYPE_P (type
))
790 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
791 fold_build2 (POINTER_PLUS_EXPR
, type
,
793 fold_build1 (NEGATE_EXPR
,
797 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
798 fold_build2 (MINUS_EXPR
, type1
,
803 if (!integer_nonzerop (assumption
))
804 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
807 if (!integer_zerop (noloop
))
808 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
811 bounds_add (bnds
, tree_to_double_int (mod
), type
);
812 *delta
= fold_build2 (PLUS_EXPR
, niter_type
, *delta
, mod
);
820 /* Add assertions to NITER that ensure that the control variable of the loop
821 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
822 are TYPE. Returns false if we can prove that there is an overflow, true
823 otherwise. STEP is the absolute value of the step. */
826 assert_no_overflow_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
827 struct tree_niter_desc
*niter
, tree step
)
829 tree bound
, d
, assumption
, diff
;
830 tree niter_type
= TREE_TYPE (step
);
832 if (integer_nonzerop (iv0
->step
))
834 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
835 if (iv0
->no_overflow
)
838 /* If iv0->base is a constant, we can determine the last value before
839 overflow precisely; otherwise we conservatively assume
842 if (TREE_CODE (iv0
->base
) == INTEGER_CST
)
844 d
= fold_build2 (MINUS_EXPR
, niter_type
,
845 fold_convert (niter_type
, TYPE_MAX_VALUE (type
)),
846 fold_convert (niter_type
, iv0
->base
));
847 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
850 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
851 build_int_cst (niter_type
, 1));
852 bound
= fold_build2 (MINUS_EXPR
, type
,
853 TYPE_MAX_VALUE (type
), fold_convert (type
, diff
));
854 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
859 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
860 if (iv1
->no_overflow
)
863 if (TREE_CODE (iv1
->base
) == INTEGER_CST
)
865 d
= fold_build2 (MINUS_EXPR
, niter_type
,
866 fold_convert (niter_type
, iv1
->base
),
867 fold_convert (niter_type
, TYPE_MIN_VALUE (type
)));
868 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
871 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
872 build_int_cst (niter_type
, 1));
873 bound
= fold_build2 (PLUS_EXPR
, type
,
874 TYPE_MIN_VALUE (type
), fold_convert (type
, diff
));
875 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
879 if (integer_zerop (assumption
))
881 if (!integer_nonzerop (assumption
))
882 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
883 niter
->assumptions
, assumption
);
885 iv0
->no_overflow
= true;
886 iv1
->no_overflow
= true;
890 /* Add an assumption to NITER that a loop whose ending condition
891 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
892 bounds the value of IV1->base - IV0->base. */
895 assert_loop_rolls_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
896 struct tree_niter_desc
*niter
, bounds
*bnds
)
898 tree assumption
= boolean_true_node
, bound
, diff
;
899 tree mbz
, mbzl
, mbzr
, type1
;
900 bool rolls_p
, no_overflow_p
;
904 /* We are going to compute the number of iterations as
905 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
906 variant of TYPE. This formula only works if
908 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
910 (where MAX is the maximum value of the unsigned variant of TYPE, and
911 the computations in this formula are performed in full precision,
912 i.e., without overflows).
914 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
915 we have a condition of the form iv0->base - step < iv1->base before the loop,
916 and for loops iv0->base < iv1->base - step * i the condition
917 iv0->base < iv1->base + step, due to loop header copying, which enable us
918 to prove the lower bound.
920 The upper bound is more complicated. Unless the expressions for initial
921 and final value themselves contain enough information, we usually cannot
922 derive it from the context. */
924 /* First check whether the answer does not follow from the bounds we gathered
926 if (integer_nonzerop (iv0
->step
))
927 dstep
= tree_to_double_int (iv0
->step
);
930 dstep
= double_int_sext (tree_to_double_int (iv1
->step
),
931 TYPE_PRECISION (type
));
932 dstep
= double_int_neg (dstep
);
936 mpz_set_double_int (mstep
, dstep
, true);
937 mpz_neg (mstep
, mstep
);
938 mpz_add_ui (mstep
, mstep
, 1);
940 rolls_p
= mpz_cmp (mstep
, bnds
->below
) <= 0;
943 mpz_set_double_int (max
, double_int_mask (TYPE_PRECISION (type
)), true);
944 mpz_add (max
, max
, mstep
);
945 no_overflow_p
= (mpz_cmp (bnds
->up
, max
) <= 0
946 /* For pointers, only values lying inside a single object
947 can be compared or manipulated by pointer arithmetics.
948 Gcc in general does not allow or handle objects larger
949 than half of the address space, hence the upper bound
950 is satisfied for pointers. */
951 || POINTER_TYPE_P (type
));
955 if (rolls_p
&& no_overflow_p
)
959 if (POINTER_TYPE_P (type
))
962 /* Now the hard part; we must formulate the assumption(s) as expressions, and
963 we must be careful not to introduce overflow. */
965 if (integer_nonzerop (iv0
->step
))
967 diff
= fold_build2 (MINUS_EXPR
, type1
,
968 iv0
->step
, build_int_cst (type1
, 1));
970 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
971 0 address never belongs to any object, we can assume this for
973 if (!POINTER_TYPE_P (type
))
975 bound
= fold_build2 (PLUS_EXPR
, type1
,
976 TYPE_MIN_VALUE (type
), diff
);
977 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
981 /* And then we can compute iv0->base - diff, and compare it with
983 mbzl
= fold_build2 (MINUS_EXPR
, type1
,
984 fold_convert (type1
, iv0
->base
), diff
);
985 mbzr
= fold_convert (type1
, iv1
->base
);
989 diff
= fold_build2 (PLUS_EXPR
, type1
,
990 iv1
->step
, build_int_cst (type1
, 1));
992 if (!POINTER_TYPE_P (type
))
994 bound
= fold_build2 (PLUS_EXPR
, type1
,
995 TYPE_MAX_VALUE (type
), diff
);
996 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
1000 mbzl
= fold_convert (type1
, iv0
->base
);
1001 mbzr
= fold_build2 (MINUS_EXPR
, type1
,
1002 fold_convert (type1
, iv1
->base
), diff
);
1005 if (!integer_nonzerop (assumption
))
1006 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1007 niter
->assumptions
, assumption
);
1010 mbz
= fold_build2 (GT_EXPR
, boolean_type_node
, mbzl
, mbzr
);
1011 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1012 niter
->may_be_zero
, mbz
);
1016 /* Determines number of iterations of loop whose ending condition
1017 is IV0 < IV1. TYPE is the type of the iv. The number of
1018 iterations is stored to NITER. BNDS bounds the difference
1019 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
1020 that the exit must be taken eventually. */
1023 number_of_iterations_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1024 struct tree_niter_desc
*niter
,
1025 bool exit_must_be_taken
, bounds
*bnds
)
1027 tree niter_type
= unsigned_type_for (type
);
1028 tree delta
, step
, s
;
1031 if (integer_nonzerop (iv0
->step
))
1033 niter
->control
= *iv0
;
1034 niter
->cmp
= LT_EXPR
;
1035 niter
->bound
= iv1
->base
;
1039 niter
->control
= *iv1
;
1040 niter
->cmp
= GT_EXPR
;
1041 niter
->bound
= iv0
->base
;
1044 delta
= fold_build2 (MINUS_EXPR
, niter_type
,
1045 fold_convert (niter_type
, iv1
->base
),
1046 fold_convert (niter_type
, iv0
->base
));
1048 /* First handle the special case that the step is +-1. */
1049 if ((integer_onep (iv0
->step
) && integer_zerop (iv1
->step
))
1050 || (integer_all_onesp (iv1
->step
) && integer_zerop (iv0
->step
)))
1052 /* for (i = iv0->base; i < iv1->base; i++)
1056 for (i = iv1->base; i > iv0->base; i--).
1058 In both cases # of iterations is iv1->base - iv0->base, assuming that
1059 iv1->base >= iv0->base.
1061 First try to derive a lower bound on the value of
1062 iv1->base - iv0->base, computed in full precision. If the difference
1063 is nonnegative, we are done, otherwise we must record the
1066 if (mpz_sgn (bnds
->below
) < 0)
1067 niter
->may_be_zero
= fold_build2 (LT_EXPR
, boolean_type_node
,
1068 iv1
->base
, iv0
->base
);
1069 niter
->niter
= delta
;
1070 niter
->max
= mpz_get_double_int (niter_type
, bnds
->up
, false);
1074 if (integer_nonzerop (iv0
->step
))
1075 step
= fold_convert (niter_type
, iv0
->step
);
1077 step
= fold_convert (niter_type
,
1078 fold_build1 (NEGATE_EXPR
, type
, iv1
->step
));
1080 /* If we can determine the final value of the control iv exactly, we can
1081 transform the condition to != comparison. In particular, this will be
1082 the case if DELTA is constant. */
1083 if (number_of_iterations_lt_to_ne (type
, iv0
, iv1
, niter
, &delta
, step
,
1084 exit_must_be_taken
, bnds
))
1088 zps
.base
= build_int_cst (niter_type
, 0);
1090 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1091 zps does not overflow. */
1092 zps
.no_overflow
= true;
1094 return number_of_iterations_ne (type
, &zps
, delta
, niter
, true, bnds
);
1097 /* Make sure that the control iv does not overflow. */
1098 if (!assert_no_overflow_lt (type
, iv0
, iv1
, niter
, step
))
1101 /* We determine the number of iterations as (delta + step - 1) / step. For
1102 this to work, we must know that iv1->base >= iv0->base - step + 1,
1103 otherwise the loop does not roll. */
1104 assert_loop_rolls_lt (type
, iv0
, iv1
, niter
, bnds
);
1106 s
= fold_build2 (MINUS_EXPR
, niter_type
,
1107 step
, build_int_cst (niter_type
, 1));
1108 delta
= fold_build2 (PLUS_EXPR
, niter_type
, delta
, s
);
1109 niter
->niter
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, delta
, step
);
1113 mpz_set_double_int (mstep
, tree_to_double_int (step
), true);
1114 mpz_add (tmp
, bnds
->up
, mstep
);
1115 mpz_sub_ui (tmp
, tmp
, 1);
1116 mpz_fdiv_q (tmp
, tmp
, mstep
);
1117 niter
->max
= mpz_get_double_int (niter_type
, tmp
, false);
1124 /* Determines number of iterations of loop whose ending condition
1125 is IV0 <= IV1. TYPE is the type of the iv. The number of
1126 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
1127 we know that this condition must eventually become false (we derived this
1128 earlier, and possibly set NITER->assumptions to make sure this
1129 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1132 number_of_iterations_le (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1133 struct tree_niter_desc
*niter
, bool exit_must_be_taken
,
1138 if (POINTER_TYPE_P (type
))
1141 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1142 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1143 value of the type. This we must know anyway, since if it is
1144 equal to this value, the loop rolls forever. We do not check
1145 this condition for pointer type ivs, as the code cannot rely on
1146 the object to that the pointer points being placed at the end of
1147 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1148 not defined for pointers). */
1150 if (!exit_must_be_taken
&& !POINTER_TYPE_P (type
))
1152 if (integer_nonzerop (iv0
->step
))
1153 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1154 iv1
->base
, TYPE_MAX_VALUE (type
));
1156 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1157 iv0
->base
, TYPE_MIN_VALUE (type
));
1159 if (integer_zerop (assumption
))
1161 if (!integer_nonzerop (assumption
))
1162 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1163 niter
->assumptions
, assumption
);
1166 if (integer_nonzerop (iv0
->step
))
1168 if (POINTER_TYPE_P (type
))
1169 iv1
->base
= fold_build2 (POINTER_PLUS_EXPR
, type
, iv1
->base
,
1170 build_int_cst (type1
, 1));
1172 iv1
->base
= fold_build2 (PLUS_EXPR
, type1
, iv1
->base
,
1173 build_int_cst (type1
, 1));
1175 else if (POINTER_TYPE_P (type
))
1176 iv0
->base
= fold_build2 (POINTER_PLUS_EXPR
, type
, iv0
->base
,
1177 fold_build1 (NEGATE_EXPR
, type1
,
1178 build_int_cst (type1
, 1)));
1180 iv0
->base
= fold_build2 (MINUS_EXPR
, type1
,
1181 iv0
->base
, build_int_cst (type1
, 1));
1183 bounds_add (bnds
, double_int_one
, type1
);
1185 return number_of_iterations_lt (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1189 /* Dumps description of affine induction variable IV to FILE. */
1192 dump_affine_iv (FILE *file
, affine_iv
*iv
)
1194 if (!integer_zerop (iv
->step
))
1195 fprintf (file
, "[");
1197 print_generic_expr (dump_file
, iv
->base
, TDF_SLIM
);
1199 if (!integer_zerop (iv
->step
))
1201 fprintf (file
, ", + , ");
1202 print_generic_expr (dump_file
, iv
->step
, TDF_SLIM
);
1203 fprintf (file
, "]%s", iv
->no_overflow
? "(no_overflow)" : "");
1207 /* Determine the number of iterations according to condition (for staying
1208 inside loop) which compares two induction variables using comparison
1209 operator CODE. The induction variable on left side of the comparison
1210 is IV0, the right-hand side is IV1. Both induction variables must have
1211 type TYPE, which must be an integer or pointer type. The steps of the
1212 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1214 LOOP is the loop whose number of iterations we are determining.
1216 ONLY_EXIT is true if we are sure this is the only way the loop could be
1217 exited (including possibly non-returning function calls, exceptions, etc.)
1218 -- in this case we can use the information whether the control induction
1219 variables can overflow or not in a more efficient way.
1221 The results (number of iterations and assumptions as described in
1222 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
1223 Returns false if it fails to determine number of iterations, true if it
1224 was determined (possibly with some assumptions). */
1227 number_of_iterations_cond (struct loop
*loop
,
1228 tree type
, affine_iv
*iv0
, enum tree_code code
,
1229 affine_iv
*iv1
, struct tree_niter_desc
*niter
,
1232 bool exit_must_be_taken
= false, ret
;
1235 /* The meaning of these assumptions is this:
1237 then the rest of information does not have to be valid
1238 if may_be_zero then the loop does not roll, even if
1240 niter
->assumptions
= boolean_true_node
;
1241 niter
->may_be_zero
= boolean_false_node
;
1242 niter
->niter
= NULL_TREE
;
1243 niter
->max
= double_int_zero
;
1245 niter
->bound
= NULL_TREE
;
1246 niter
->cmp
= ERROR_MARK
;
1248 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1249 the control variable is on lhs. */
1250 if (code
== GE_EXPR
|| code
== GT_EXPR
1251 || (code
== NE_EXPR
&& integer_zerop (iv0
->step
)))
1254 code
= swap_tree_comparison (code
);
1257 if (POINTER_TYPE_P (type
))
1259 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1260 to the same object. If they do, the control variable cannot wrap
1261 (as wrap around the bounds of memory will never return a pointer
1262 that would be guaranteed to point to the same object, even if we
1263 avoid undefined behavior by casting to size_t and back). */
1264 iv0
->no_overflow
= true;
1265 iv1
->no_overflow
= true;
1268 /* If the control induction variable does not overflow and the only exit
1269 from the loop is the one that we analyze, we know it must be taken
1273 if (!integer_zerop (iv0
->step
) && iv0
->no_overflow
)
1274 exit_must_be_taken
= true;
1275 else if (!integer_zerop (iv1
->step
) && iv1
->no_overflow
)
1276 exit_must_be_taken
= true;
1279 /* We can handle the case when neither of the sides of the comparison is
1280 invariant, provided that the test is NE_EXPR. This rarely occurs in
1281 practice, but it is simple enough to manage. */
1282 if (!integer_zerop (iv0
->step
) && !integer_zerop (iv1
->step
))
1284 if (code
!= NE_EXPR
)
1287 iv0
->step
= fold_binary_to_constant (MINUS_EXPR
, type
,
1288 iv0
->step
, iv1
->step
);
1289 iv0
->no_overflow
= false;
1290 iv1
->step
= build_int_cst (type
, 0);
1291 iv1
->no_overflow
= true;
1294 /* If the result of the comparison is a constant, the loop is weird. More
1295 precise handling would be possible, but the situation is not common enough
1296 to waste time on it. */
1297 if (integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
))
1300 /* Ignore loops of while (i-- < 10) type. */
1301 if (code
!= NE_EXPR
)
1303 if (iv0
->step
&& tree_int_cst_sign_bit (iv0
->step
))
1306 if (!integer_zerop (iv1
->step
) && !tree_int_cst_sign_bit (iv1
->step
))
1310 /* If the loop exits immediately, there is nothing to do. */
1311 if (integer_zerop (fold_build2 (code
, boolean_type_node
, iv0
->base
, iv1
->base
)))
1313 niter
->niter
= build_int_cst (unsigned_type_for (type
), 0);
1314 niter
->max
= double_int_zero
;
1318 /* OK, now we know we have a senseful loop. Handle several cases, depending
1319 on what comparison operator is used. */
1320 bound_difference (loop
, iv1
->base
, iv0
->base
, &bnds
);
1322 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1325 "Analyzing # of iterations of loop %d\n", loop
->num
);
1327 fprintf (dump_file
, " exit condition ");
1328 dump_affine_iv (dump_file
, iv0
);
1329 fprintf (dump_file
, " %s ",
1330 code
== NE_EXPR
? "!="
1331 : code
== LT_EXPR
? "<"
1333 dump_affine_iv (dump_file
, iv1
);
1334 fprintf (dump_file
, "\n");
1336 fprintf (dump_file
, " bounds on difference of bases: ");
1337 mpz_out_str (dump_file
, 10, bnds
.below
);
1338 fprintf (dump_file
, " ... ");
1339 mpz_out_str (dump_file
, 10, bnds
.up
);
1340 fprintf (dump_file
, "\n");
1346 gcc_assert (integer_zerop (iv1
->step
));
1347 ret
= number_of_iterations_ne (type
, iv0
, iv1
->base
, niter
,
1348 exit_must_be_taken
, &bnds
);
1352 ret
= number_of_iterations_lt (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1357 ret
= number_of_iterations_le (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1365 mpz_clear (bnds
.up
);
1366 mpz_clear (bnds
.below
);
1368 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1372 fprintf (dump_file
, " result:\n");
1373 if (!integer_nonzerop (niter
->assumptions
))
1375 fprintf (dump_file
, " under assumptions ");
1376 print_generic_expr (dump_file
, niter
->assumptions
, TDF_SLIM
);
1377 fprintf (dump_file
, "\n");
1380 if (!integer_zerop (niter
->may_be_zero
))
1382 fprintf (dump_file
, " zero if ");
1383 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
1384 fprintf (dump_file
, "\n");
1387 fprintf (dump_file
, " # of iterations ");
1388 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
1389 fprintf (dump_file
, ", bounded by ");
1390 dump_double_int (dump_file
, niter
->max
, true);
1391 fprintf (dump_file
, "\n");
1394 fprintf (dump_file
, " failed\n\n");
1399 /* Substitute NEW for OLD in EXPR and fold the result. */
1402 simplify_replace_tree (tree expr
, tree old
, tree new_tree
)
1405 tree ret
= NULL_TREE
, e
, se
;
1410 /* Do not bother to replace constants. */
1411 if (CONSTANT_CLASS_P (old
))
1415 || operand_equal_p (expr
, old
, 0))
1416 return unshare_expr (new_tree
);
1421 n
= TREE_OPERAND_LENGTH (expr
);
1422 for (i
= 0; i
< n
; i
++)
1424 e
= TREE_OPERAND (expr
, i
);
1425 se
= simplify_replace_tree (e
, old
, new_tree
);
1430 ret
= copy_node (expr
);
1432 TREE_OPERAND (ret
, i
) = se
;
1435 return (ret
? fold (ret
) : expr
);
1438 /* Expand definitions of ssa names in EXPR as long as they are simple
1439 enough, and return the new expression. */
1442 expand_simple_operations (tree expr
)
1445 tree ret
= NULL_TREE
, e
, ee
, e1
;
1446 enum tree_code code
;
1449 if (expr
== NULL_TREE
)
1452 if (is_gimple_min_invariant (expr
))
1455 code
= TREE_CODE (expr
);
1456 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
1458 n
= TREE_OPERAND_LENGTH (expr
);
1459 for (i
= 0; i
< n
; i
++)
1461 e
= TREE_OPERAND (expr
, i
);
1462 ee
= expand_simple_operations (e
);
1467 ret
= copy_node (expr
);
1469 TREE_OPERAND (ret
, i
) = ee
;
1475 fold_defer_overflow_warnings ();
1477 fold_undefer_and_ignore_overflow_warnings ();
1481 if (TREE_CODE (expr
) != SSA_NAME
)
1484 stmt
= SSA_NAME_DEF_STMT (expr
);
1485 if (gimple_code (stmt
) == GIMPLE_PHI
)
1487 basic_block src
, dest
;
1489 if (gimple_phi_num_args (stmt
) != 1)
1491 e
= PHI_ARG_DEF (stmt
, 0);
1493 /* Avoid propagating through loop exit phi nodes, which
1494 could break loop-closed SSA form restrictions. */
1495 dest
= gimple_bb (stmt
);
1496 src
= single_pred (dest
);
1497 if (TREE_CODE (e
) == SSA_NAME
1498 && src
->loop_father
!= dest
->loop_father
)
1501 return expand_simple_operations (e
);
1503 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1506 e
= gimple_assign_rhs1 (stmt
);
1507 code
= gimple_assign_rhs_code (stmt
);
1508 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1510 if (is_gimple_min_invariant (e
))
1513 if (code
== SSA_NAME
)
1514 return expand_simple_operations (e
);
1522 /* Casts are simple. */
1523 ee
= expand_simple_operations (e
);
1524 return fold_build1 (code
, TREE_TYPE (expr
), ee
);
1528 case POINTER_PLUS_EXPR
:
1529 /* And increments and decrements by a constant are simple. */
1530 e1
= gimple_assign_rhs2 (stmt
);
1531 if (!is_gimple_min_invariant (e1
))
1534 ee
= expand_simple_operations (e
);
1535 return fold_build2 (code
, TREE_TYPE (expr
), ee
, e1
);
1542 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1543 expression (or EXPR unchanged, if no simplification was possible). */
1546 tree_simplify_using_condition_1 (tree cond
, tree expr
)
1549 tree e
, te
, e0
, e1
, e2
, notcond
;
1550 enum tree_code code
= TREE_CODE (expr
);
1552 if (code
== INTEGER_CST
)
1555 if (code
== TRUTH_OR_EXPR
1556 || code
== TRUTH_AND_EXPR
1557 || code
== COND_EXPR
)
1561 e0
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 0));
1562 if (TREE_OPERAND (expr
, 0) != e0
)
1565 e1
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 1));
1566 if (TREE_OPERAND (expr
, 1) != e1
)
1569 if (code
== COND_EXPR
)
1571 e2
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 2));
1572 if (TREE_OPERAND (expr
, 2) != e2
)
1580 if (code
== COND_EXPR
)
1581 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1583 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1589 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
1590 propagation, and vice versa. Fold does not handle this, since it is
1591 considered too expensive. */
1592 if (TREE_CODE (cond
) == EQ_EXPR
)
1594 e0
= TREE_OPERAND (cond
, 0);
1595 e1
= TREE_OPERAND (cond
, 1);
1597 /* We know that e0 == e1. Check whether we cannot simplify expr
1599 e
= simplify_replace_tree (expr
, e0
, e1
);
1600 if (integer_zerop (e
) || integer_nonzerop (e
))
1603 e
= simplify_replace_tree (expr
, e1
, e0
);
1604 if (integer_zerop (e
) || integer_nonzerop (e
))
1607 if (TREE_CODE (expr
) == EQ_EXPR
)
1609 e0
= TREE_OPERAND (expr
, 0);
1610 e1
= TREE_OPERAND (expr
, 1);
1612 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
1613 e
= simplify_replace_tree (cond
, e0
, e1
);
1614 if (integer_zerop (e
))
1616 e
= simplify_replace_tree (cond
, e1
, e0
);
1617 if (integer_zerop (e
))
1620 if (TREE_CODE (expr
) == NE_EXPR
)
1622 e0
= TREE_OPERAND (expr
, 0);
1623 e1
= TREE_OPERAND (expr
, 1);
1625 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
1626 e
= simplify_replace_tree (cond
, e0
, e1
);
1627 if (integer_zerop (e
))
1628 return boolean_true_node
;
1629 e
= simplify_replace_tree (cond
, e1
, e0
);
1630 if (integer_zerop (e
))
1631 return boolean_true_node
;
1634 te
= expand_simple_operations (expr
);
1636 /* Check whether COND ==> EXPR. */
1637 notcond
= invert_truthvalue (cond
);
1638 e
= fold_binary (TRUTH_OR_EXPR
, boolean_type_node
, notcond
, te
);
1639 if (e
&& integer_nonzerop (e
))
1642 /* Check whether COND ==> not EXPR. */
1643 e
= fold_binary (TRUTH_AND_EXPR
, boolean_type_node
, cond
, te
);
1644 if (e
&& integer_zerop (e
))
1650 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1651 expression (or EXPR unchanged, if no simplification was possible).
1652 Wrapper around tree_simplify_using_condition_1 that ensures that chains
1653 of simple operations in definitions of ssa names in COND are expanded,
1654 so that things like casts or incrementing the value of the bound before
1655 the loop do not cause us to fail. */
1658 tree_simplify_using_condition (tree cond
, tree expr
)
1660 cond
= expand_simple_operations (cond
);
1662 return tree_simplify_using_condition_1 (cond
, expr
);
1665 /* Tries to simplify EXPR using the conditions on entry to LOOP.
1666 Returns the simplified expression (or EXPR unchanged, if no
1667 simplification was possible).*/
1670 simplify_using_initial_conditions (struct loop
*loop
, tree expr
)
1678 if (TREE_CODE (expr
) == INTEGER_CST
)
1681 /* Limit walking the dominators to avoid quadraticness in
1682 the number of BBs times the number of loops in degenerate
1684 for (bb
= loop
->header
;
1685 bb
!= ENTRY_BLOCK_PTR
&& cnt
< MAX_DOMINATORS_TO_WALK
;
1686 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1688 if (!single_pred_p (bb
))
1690 e
= single_pred_edge (bb
);
1692 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
1695 stmt
= last_stmt (e
->src
);
1696 cond
= fold_build2 (gimple_cond_code (stmt
),
1698 gimple_cond_lhs (stmt
),
1699 gimple_cond_rhs (stmt
));
1700 if (e
->flags
& EDGE_FALSE_VALUE
)
1701 cond
= invert_truthvalue (cond
);
1702 expr
= tree_simplify_using_condition (cond
, expr
);
1709 /* Tries to simplify EXPR using the evolutions of the loop invariants
1710 in the superloops of LOOP. Returns the simplified expression
1711 (or EXPR unchanged, if no simplification was possible). */
1714 simplify_using_outer_evolutions (struct loop
*loop
, tree expr
)
1716 enum tree_code code
= TREE_CODE (expr
);
1720 if (is_gimple_min_invariant (expr
))
1723 if (code
== TRUTH_OR_EXPR
1724 || code
== TRUTH_AND_EXPR
1725 || code
== COND_EXPR
)
1729 e0
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 0));
1730 if (TREE_OPERAND (expr
, 0) != e0
)
1733 e1
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 1));
1734 if (TREE_OPERAND (expr
, 1) != e1
)
1737 if (code
== COND_EXPR
)
1739 e2
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 2));
1740 if (TREE_OPERAND (expr
, 2) != e2
)
1748 if (code
== COND_EXPR
)
1749 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1751 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1757 e
= instantiate_parameters (loop
, expr
);
1758 if (is_gimple_min_invariant (e
))
1764 /* Returns true if EXIT is the only possible exit from LOOP. */
1767 loop_only_exit_p (const struct loop
*loop
, const_edge exit
)
1770 gimple_stmt_iterator bsi
;
1774 if (exit
!= single_exit (loop
))
1777 body
= get_loop_body (loop
);
1778 for (i
= 0; i
< loop
->num_nodes
; i
++)
1780 for (bsi
= gsi_start_bb (body
[i
]); !gsi_end_p (bsi
); gsi_next (&bsi
))
1782 call
= gsi_stmt (bsi
);
1783 if (gimple_code (call
) != GIMPLE_CALL
)
1786 if (gimple_has_side_effects (call
))
1798 /* Stores description of number of iterations of LOOP derived from
1799 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
1800 useful information could be derived (and fields of NITER has
1801 meaning described in comments at struct tree_niter_desc
1802 declaration), false otherwise. If WARN is true and
1803 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1804 potentially unsafe assumptions. */
1807 number_of_iterations_exit (struct loop
*loop
, edge exit
,
1808 struct tree_niter_desc
*niter
,
1814 enum tree_code code
;
1817 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit
->src
))
1820 niter
->assumptions
= boolean_false_node
;
1821 stmt
= last_stmt (exit
->src
);
1822 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1825 /* We want the condition for staying inside loop. */
1826 code
= gimple_cond_code (stmt
);
1827 if (exit
->flags
& EDGE_TRUE_VALUE
)
1828 code
= invert_tree_comparison (code
, false);
1843 op0
= gimple_cond_lhs (stmt
);
1844 op1
= gimple_cond_rhs (stmt
);
1845 type
= TREE_TYPE (op0
);
1847 if (TREE_CODE (type
) != INTEGER_TYPE
1848 && !POINTER_TYPE_P (type
))
1851 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, false))
1853 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, false))
1856 /* We don't want to see undefined signed overflow warnings while
1857 computing the number of iterations. */
1858 fold_defer_overflow_warnings ();
1860 iv0
.base
= expand_simple_operations (iv0
.base
);
1861 iv1
.base
= expand_simple_operations (iv1
.base
);
1862 if (!number_of_iterations_cond (loop
, type
, &iv0
, code
, &iv1
, niter
,
1863 loop_only_exit_p (loop
, exit
)))
1865 fold_undefer_and_ignore_overflow_warnings ();
1871 niter
->assumptions
= simplify_using_outer_evolutions (loop
,
1872 niter
->assumptions
);
1873 niter
->may_be_zero
= simplify_using_outer_evolutions (loop
,
1874 niter
->may_be_zero
);
1875 niter
->niter
= simplify_using_outer_evolutions (loop
, niter
->niter
);
1879 = simplify_using_initial_conditions (loop
,
1880 niter
->assumptions
);
1882 = simplify_using_initial_conditions (loop
,
1883 niter
->may_be_zero
);
1885 fold_undefer_and_ignore_overflow_warnings ();
1887 if (integer_onep (niter
->assumptions
))
1890 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1891 But if we can prove that there is overflow or some other source of weird
1892 behavior, ignore the loop even with -funsafe-loop-optimizations. */
1893 if (integer_zerop (niter
->assumptions
) || !single_exit (loop
))
1896 if (flag_unsafe_loop_optimizations
)
1897 niter
->assumptions
= boolean_true_node
;
1901 const char *wording
;
1902 location_t loc
= gimple_location (stmt
);
1904 /* We can provide a more specific warning if one of the operator is
1905 constant and the other advances by +1 or -1. */
1906 if (!integer_zerop (iv1
.step
)
1907 ? (integer_zerop (iv0
.step
)
1908 && (integer_onep (iv1
.step
) || integer_all_onesp (iv1
.step
)))
1909 : (integer_onep (iv0
.step
) || integer_all_onesp (iv0
.step
)))
1911 flag_unsafe_loop_optimizations
1912 ? N_("assuming that the loop is not infinite")
1913 : N_("cannot optimize possibly infinite loops");
1916 flag_unsafe_loop_optimizations
1917 ? N_("assuming that the loop counter does not overflow")
1918 : N_("cannot optimize loop, the loop counter may overflow");
1920 warning_at ((LOCATION_LINE (loc
) > 0) ? loc
: input_location
,
1921 OPT_Wunsafe_loop_optimizations
, "%s", gettext (wording
));
1924 return flag_unsafe_loop_optimizations
;
1927 /* Try to determine the number of iterations of LOOP. If we succeed,
1928 expression giving number of iterations is returned and *EXIT is
1929 set to the edge from that the information is obtained. Otherwise
1930 chrec_dont_know is returned. */
1933 find_loop_niter (struct loop
*loop
, edge
*exit
)
1936 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
1938 tree niter
= NULL_TREE
, aniter
;
1939 struct tree_niter_desc desc
;
1942 FOR_EACH_VEC_ELT (edge
, exits
, i
, ex
)
1944 if (!just_once_each_iteration_p (loop
, ex
->src
))
1947 if (!number_of_iterations_exit (loop
, ex
, &desc
, false))
1950 if (integer_nonzerop (desc
.may_be_zero
))
1952 /* We exit in the first iteration through this exit.
1953 We won't find anything better. */
1954 niter
= build_int_cst (unsigned_type_node
, 0);
1959 if (!integer_zerop (desc
.may_be_zero
))
1962 aniter
= desc
.niter
;
1966 /* Nothing recorded yet. */
1972 /* Prefer constants, the lower the better. */
1973 if (TREE_CODE (aniter
) != INTEGER_CST
)
1976 if (TREE_CODE (niter
) != INTEGER_CST
)
1983 if (tree_int_cst_lt (aniter
, niter
))
1990 VEC_free (edge
, heap
, exits
);
1992 return niter
? niter
: chrec_dont_know
;
1995 /* Return true if loop is known to have bounded number of iterations. */
1998 finite_loop_p (struct loop
*loop
)
2001 VEC (edge
, heap
) *exits
;
2003 struct tree_niter_desc desc
;
2004 bool finite
= false;
2007 if (flag_unsafe_loop_optimizations
)
2009 flags
= flags_from_decl_or_type (current_function_decl
);
2010 if ((flags
& (ECF_CONST
|ECF_PURE
)) && !(flags
& ECF_LOOPING_CONST_OR_PURE
))
2012 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2013 fprintf (dump_file
, "Found loop %i to be finite: it is within pure or const function.\n",
2018 exits
= get_loop_exit_edges (loop
);
2019 FOR_EACH_VEC_ELT (edge
, exits
, i
, ex
)
2021 if (!just_once_each_iteration_p (loop
, ex
->src
))
2024 if (number_of_iterations_exit (loop
, ex
, &desc
, false))
2026 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2028 fprintf (dump_file
, "Found loop %i to be finite: iterating ", loop
->num
);
2029 print_generic_expr (dump_file
, desc
.niter
, TDF_SLIM
);
2030 fprintf (dump_file
, " times\n");
2036 VEC_free (edge
, heap
, exits
);
2042 Analysis of a number of iterations of a loop by a brute-force evaluation.
2046 /* Bound on the number of iterations we try to evaluate. */
2048 #define MAX_ITERATIONS_TO_TRACK \
2049 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
2051 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
2052 result by a chain of operations such that all but exactly one of their
2053 operands are constants. */
2056 chain_of_csts_start (struct loop
*loop
, tree x
)
2058 gimple stmt
= SSA_NAME_DEF_STMT (x
);
2060 basic_block bb
= gimple_bb (stmt
);
2061 enum tree_code code
;
2064 || !flow_bb_inside_loop_p (loop
, bb
))
2067 if (gimple_code (stmt
) == GIMPLE_PHI
)
2069 if (bb
== loop
->header
)
2075 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2078 code
= gimple_assign_rhs_code (stmt
);
2079 if (gimple_references_memory_p (stmt
)
2080 || TREE_CODE_CLASS (code
) == tcc_reference
2081 || (code
== ADDR_EXPR
2082 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
2085 use
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
2086 if (use
== NULL_TREE
)
2089 return chain_of_csts_start (loop
, use
);
2092 /* Determines whether the expression X is derived from a result of a phi node
2093 in header of LOOP such that
2095 * the derivation of X consists only from operations with constants
2096 * the initial value of the phi node is constant
2097 * the value of the phi node in the next iteration can be derived from the
2098 value in the current iteration by a chain of operations with constants.
2100 If such phi node exists, it is returned, otherwise NULL is returned. */
2103 get_base_for (struct loop
*loop
, tree x
)
2108 if (is_gimple_min_invariant (x
))
2111 phi
= chain_of_csts_start (loop
, x
);
2115 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2116 next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2118 if (TREE_CODE (next
) != SSA_NAME
)
2121 if (!is_gimple_min_invariant (init
))
2124 if (chain_of_csts_start (loop
, next
) != phi
)
2130 /* Given an expression X, then
2132 * if X is NULL_TREE, we return the constant BASE.
2133 * otherwise X is a SSA name, whose value in the considered loop is derived
2134 by a chain of operations with constant from a result of a phi node in
2135 the header of the loop. Then we return value of X when the value of the
2136 result of this phi node is given by the constant BASE. */
2139 get_val_for (tree x
, tree base
)
2143 gcc_assert (is_gimple_min_invariant (base
));
2148 stmt
= SSA_NAME_DEF_STMT (x
);
2149 if (gimple_code (stmt
) == GIMPLE_PHI
)
2152 gcc_assert (is_gimple_assign (stmt
));
2154 /* STMT must be either an assignment of a single SSA name or an
2155 expression involving an SSA name and a constant. Try to fold that
2156 expression using the value for the SSA name. */
2157 if (gimple_assign_ssa_name_copy_p (stmt
))
2158 return get_val_for (gimple_assign_rhs1 (stmt
), base
);
2159 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_UNARY_RHS
2160 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
2162 return fold_build1 (gimple_assign_rhs_code (stmt
),
2163 gimple_expr_type (stmt
),
2164 get_val_for (gimple_assign_rhs1 (stmt
), base
));
2166 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_BINARY_RHS
)
2168 tree rhs1
= gimple_assign_rhs1 (stmt
);
2169 tree rhs2
= gimple_assign_rhs2 (stmt
);
2170 if (TREE_CODE (rhs1
) == SSA_NAME
)
2171 rhs1
= get_val_for (rhs1
, base
);
2172 else if (TREE_CODE (rhs2
) == SSA_NAME
)
2173 rhs2
= get_val_for (rhs2
, base
);
2176 return fold_build2 (gimple_assign_rhs_code (stmt
),
2177 gimple_expr_type (stmt
), rhs1
, rhs2
);
2184 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2185 by brute force -- i.e. by determining the value of the operands of the
2186 condition at EXIT in first few iterations of the loop (assuming that
2187 these values are constant) and determining the first one in that the
2188 condition is not satisfied. Returns the constant giving the number
2189 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
2192 loop_niter_by_eval (struct loop
*loop
, edge exit
)
2195 tree op
[2], val
[2], next
[2], aval
[2];
2200 cond
= last_stmt (exit
->src
);
2201 if (!cond
|| gimple_code (cond
) != GIMPLE_COND
)
2202 return chrec_dont_know
;
2204 cmp
= gimple_cond_code (cond
);
2205 if (exit
->flags
& EDGE_TRUE_VALUE
)
2206 cmp
= invert_tree_comparison (cmp
, false);
2216 op
[0] = gimple_cond_lhs (cond
);
2217 op
[1] = gimple_cond_rhs (cond
);
2221 return chrec_dont_know
;
2224 for (j
= 0; j
< 2; j
++)
2226 if (is_gimple_min_invariant (op
[j
]))
2229 next
[j
] = NULL_TREE
;
2234 phi
= get_base_for (loop
, op
[j
]);
2236 return chrec_dont_know
;
2237 val
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2238 next
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2242 /* Don't issue signed overflow warnings. */
2243 fold_defer_overflow_warnings ();
2245 for (i
= 0; i
< MAX_ITERATIONS_TO_TRACK
; i
++)
2247 for (j
= 0; j
< 2; j
++)
2248 aval
[j
] = get_val_for (op
[j
], val
[j
]);
2250 acnd
= fold_binary (cmp
, boolean_type_node
, aval
[0], aval
[1]);
2251 if (acnd
&& integer_zerop (acnd
))
2253 fold_undefer_and_ignore_overflow_warnings ();
2254 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2256 "Proved that loop %d iterates %d times using brute force.\n",
2258 return build_int_cst (unsigned_type_node
, i
);
2261 for (j
= 0; j
< 2; j
++)
2263 val
[j
] = get_val_for (next
[j
], val
[j
]);
2264 if (!is_gimple_min_invariant (val
[j
]))
2266 fold_undefer_and_ignore_overflow_warnings ();
2267 return chrec_dont_know
;
2272 fold_undefer_and_ignore_overflow_warnings ();
2274 return chrec_dont_know
;
2277 /* Finds the exit of the LOOP by that the loop exits after a constant
2278 number of iterations and stores the exit edge to *EXIT. The constant
2279 giving the number of iterations of LOOP is returned. The number of
2280 iterations is determined using loop_niter_by_eval (i.e. by brute force
2281 evaluation). If we are unable to find the exit for that loop_niter_by_eval
2282 determines the number of iterations, chrec_dont_know is returned. */
2285 find_loop_niter_by_eval (struct loop
*loop
, edge
*exit
)
2288 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
2290 tree niter
= NULL_TREE
, aniter
;
2294 /* Loops with multiple exits are expensive to handle and less important. */
2295 if (!flag_expensive_optimizations
2296 && VEC_length (edge
, exits
) > 1)
2297 return chrec_dont_know
;
2299 FOR_EACH_VEC_ELT (edge
, exits
, i
, ex
)
2301 if (!just_once_each_iteration_p (loop
, ex
->src
))
2304 aniter
= loop_niter_by_eval (loop
, ex
);
2305 if (chrec_contains_undetermined (aniter
))
2309 && !tree_int_cst_lt (aniter
, niter
))
2315 VEC_free (edge
, heap
, exits
);
2317 return niter
? niter
: chrec_dont_know
;
2322 Analysis of upper bounds on number of iterations of a loop.
2326 static double_int
derive_constant_upper_bound_ops (tree
, tree
,
2327 enum tree_code
, tree
);
2329 /* Returns a constant upper bound on the value of the right-hand side of
2330 an assignment statement STMT. */
2333 derive_constant_upper_bound_assign (gimple stmt
)
2335 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2336 tree op0
= gimple_assign_rhs1 (stmt
);
2337 tree op1
= gimple_assign_rhs2 (stmt
);
2339 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt
)),
2343 /* Returns a constant upper bound on the value of expression VAL. VAL
2344 is considered to be unsigned. If its type is signed, its value must
2348 derive_constant_upper_bound (tree val
)
2350 enum tree_code code
;
2353 extract_ops_from_tree (val
, &code
, &op0
, &op1
);
2354 return derive_constant_upper_bound_ops (TREE_TYPE (val
), op0
, code
, op1
);
2357 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
2358 whose type is TYPE. The expression is considered to be unsigned. If
2359 its type is signed, its value must be nonnegative. */
2362 derive_constant_upper_bound_ops (tree type
, tree op0
,
2363 enum tree_code code
, tree op1
)
2366 double_int bnd
, max
, mmax
, cst
;
2369 if (INTEGRAL_TYPE_P (type
))
2370 maxt
= TYPE_MAX_VALUE (type
);
2372 maxt
= upper_bound_in_type (type
, type
);
2374 max
= tree_to_double_int (maxt
);
2379 return tree_to_double_int (op0
);
2382 subtype
= TREE_TYPE (op0
);
2383 if (!TYPE_UNSIGNED (subtype
)
2384 /* If TYPE is also signed, the fact that VAL is nonnegative implies
2385 that OP0 is nonnegative. */
2386 && TYPE_UNSIGNED (type
)
2387 && !tree_expr_nonnegative_p (op0
))
2389 /* If we cannot prove that the casted expression is nonnegative,
2390 we cannot establish more useful upper bound than the precision
2391 of the type gives us. */
2395 /* We now know that op0 is an nonnegative value. Try deriving an upper
2397 bnd
= derive_constant_upper_bound (op0
);
2399 /* If the bound does not fit in TYPE, max. value of TYPE could be
2401 if (double_int_ucmp (max
, bnd
) < 0)
2407 case POINTER_PLUS_EXPR
:
2409 if (TREE_CODE (op1
) != INTEGER_CST
2410 || !tree_expr_nonnegative_p (op0
))
2413 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
2414 choose the most logical way how to treat this constant regardless
2415 of the signedness of the type. */
2416 cst
= tree_to_double_int (op1
);
2417 cst
= double_int_sext (cst
, TYPE_PRECISION (type
));
2418 if (code
!= MINUS_EXPR
)
2419 cst
= double_int_neg (cst
);
2421 bnd
= derive_constant_upper_bound (op0
);
2423 if (double_int_negative_p (cst
))
2425 cst
= double_int_neg (cst
);
2426 /* Avoid CST == 0x80000... */
2427 if (double_int_negative_p (cst
))
2430 /* OP0 + CST. We need to check that
2431 BND <= MAX (type) - CST. */
2433 mmax
= double_int_sub (max
, cst
);
2434 if (double_int_ucmp (bnd
, mmax
) > 0)
2437 return double_int_add (bnd
, cst
);
2441 /* OP0 - CST, where CST >= 0.
2443 If TYPE is signed, we have already verified that OP0 >= 0, and we
2444 know that the result is nonnegative. This implies that
2447 If TYPE is unsigned, we must additionally know that OP0 >= CST,
2448 otherwise the operation underflows.
2451 /* This should only happen if the type is unsigned; however, for
2452 buggy programs that use overflowing signed arithmetics even with
2453 -fno-wrapv, this condition may also be true for signed values. */
2454 if (double_int_ucmp (bnd
, cst
) < 0)
2457 if (TYPE_UNSIGNED (type
))
2459 tree tem
= fold_binary (GE_EXPR
, boolean_type_node
, op0
,
2460 double_int_to_tree (type
, cst
));
2461 if (!tem
|| integer_nonzerop (tem
))
2465 bnd
= double_int_sub (bnd
, cst
);
2470 case FLOOR_DIV_EXPR
:
2471 case EXACT_DIV_EXPR
:
2472 if (TREE_CODE (op1
) != INTEGER_CST
2473 || tree_int_cst_sign_bit (op1
))
2476 bnd
= derive_constant_upper_bound (op0
);
2477 return double_int_udiv (bnd
, tree_to_double_int (op1
), FLOOR_DIV_EXPR
);
2480 if (TREE_CODE (op1
) != INTEGER_CST
2481 || tree_int_cst_sign_bit (op1
))
2483 return tree_to_double_int (op1
);
2486 stmt
= SSA_NAME_DEF_STMT (op0
);
2487 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2488 || gimple_assign_lhs (stmt
) != op0
)
2490 return derive_constant_upper_bound_assign (stmt
);
2497 /* Records that every statement in LOOP is executed I_BOUND times.
2498 REALISTIC is true if I_BOUND is expected to be close to the real number
2499 of iterations. UPPER is true if we are sure the loop iterates at most
2503 record_niter_bound (struct loop
*loop
, double_int i_bound
, bool realistic
,
2506 /* Update the bounds only when there is no previous estimation, or when the current
2507 estimation is smaller. */
2509 && (!loop
->any_upper_bound
2510 || double_int_ucmp (i_bound
, loop
->nb_iterations_upper_bound
) < 0))
2512 loop
->any_upper_bound
= true;
2513 loop
->nb_iterations_upper_bound
= i_bound
;
2516 && (!loop
->any_estimate
2517 || double_int_ucmp (i_bound
, loop
->nb_iterations_estimate
) < 0))
2519 loop
->any_estimate
= true;
2520 loop
->nb_iterations_estimate
= i_bound
;
2524 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
2525 is true if the loop is exited immediately after STMT, and this exit
2526 is taken at last when the STMT is executed BOUND + 1 times.
2527 REALISTIC is true if BOUND is expected to be close to the real number
2528 of iterations. UPPER is true if we are sure the loop iterates at most
2529 BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */
2532 record_estimate (struct loop
*loop
, tree bound
, double_int i_bound
,
2533 gimple at_stmt
, bool is_exit
, bool realistic
, bool upper
)
2538 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2540 fprintf (dump_file
, "Statement %s", is_exit
? "(exit)" : "");
2541 print_gimple_stmt (dump_file
, at_stmt
, 0, TDF_SLIM
);
2542 fprintf (dump_file
, " is %sexecuted at most ",
2543 upper
? "" : "probably ");
2544 print_generic_expr (dump_file
, bound
, TDF_SLIM
);
2545 fprintf (dump_file
, " (bounded by ");
2546 dump_double_int (dump_file
, i_bound
, true);
2547 fprintf (dump_file
, ") + 1 times in loop %d.\n", loop
->num
);
2550 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
2551 real number of iterations. */
2552 if (TREE_CODE (bound
) != INTEGER_CST
)
2554 if (!upper
&& !realistic
)
2557 /* If we have a guaranteed upper bound, record it in the appropriate
2561 struct nb_iter_bound
*elt
= ggc_alloc_nb_iter_bound ();
2563 elt
->bound
= i_bound
;
2564 elt
->stmt
= at_stmt
;
2565 elt
->is_exit
= is_exit
;
2566 elt
->next
= loop
->bounds
;
2570 /* Update the number of iteration estimates according to the bound.
2571 If at_stmt is an exit or dominates the single exit from the loop,
2572 then the loop latch is executed at most BOUND times, otherwise
2573 it can be executed BOUND + 1 times. */
2574 exit
= single_exit (loop
);
2577 && dominated_by_p (CDI_DOMINATORS
,
2578 exit
->src
, gimple_bb (at_stmt
))))
2579 delta
= double_int_zero
;
2581 delta
= double_int_one
;
2582 i_bound
= double_int_add (i_bound
, delta
);
2584 /* If an overflow occurred, ignore the result. */
2585 if (double_int_ucmp (i_bound
, delta
) < 0)
2588 record_niter_bound (loop
, i_bound
, realistic
, upper
);
2591 /* Record the estimate on number of iterations of LOOP based on the fact that
2592 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
2593 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
2594 estimated number of iterations is expected to be close to the real one.
2595 UPPER is true if we are sure the induction variable does not wrap. */
2598 record_nonwrapping_iv (struct loop
*loop
, tree base
, tree step
, gimple stmt
,
2599 tree low
, tree high
, bool realistic
, bool upper
)
2601 tree niter_bound
, extreme
, delta
;
2602 tree type
= TREE_TYPE (base
), unsigned_type
;
2605 if (TREE_CODE (step
) != INTEGER_CST
|| integer_zerop (step
))
2608 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2610 fprintf (dump_file
, "Induction variable (");
2611 print_generic_expr (dump_file
, TREE_TYPE (base
), TDF_SLIM
);
2612 fprintf (dump_file
, ") ");
2613 print_generic_expr (dump_file
, base
, TDF_SLIM
);
2614 fprintf (dump_file
, " + ");
2615 print_generic_expr (dump_file
, step
, TDF_SLIM
);
2616 fprintf (dump_file
, " * iteration does not wrap in statement ");
2617 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2618 fprintf (dump_file
, " in loop %d.\n", loop
->num
);
2621 unsigned_type
= unsigned_type_for (type
);
2622 base
= fold_convert (unsigned_type
, base
);
2623 step
= fold_convert (unsigned_type
, step
);
2625 if (tree_int_cst_sign_bit (step
))
2627 extreme
= fold_convert (unsigned_type
, low
);
2628 if (TREE_CODE (base
) != INTEGER_CST
)
2629 base
= fold_convert (unsigned_type
, high
);
2630 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
2631 step
= fold_build1 (NEGATE_EXPR
, unsigned_type
, step
);
2635 extreme
= fold_convert (unsigned_type
, high
);
2636 if (TREE_CODE (base
) != INTEGER_CST
)
2637 base
= fold_convert (unsigned_type
, low
);
2638 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
2641 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
2642 would get out of the range. */
2643 niter_bound
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step
);
2644 max
= derive_constant_upper_bound (niter_bound
);
2645 record_estimate (loop
, niter_bound
, max
, stmt
, false, realistic
, upper
);
2648 /* Returns true if REF is a reference to an array at the end of a dynamically
2649 allocated structure. If this is the case, the array may be allocated larger
2650 than its upper bound implies. */
2653 array_at_struct_end_p (tree ref
)
2655 tree base
= get_base_address (ref
);
2658 /* Unless the reference is through a pointer, the size of the array matches
2660 if (!base
|| (!INDIRECT_REF_P (base
) && TREE_CODE (base
) != MEM_REF
))
2663 for (;handled_component_p (ref
); ref
= parent
)
2665 parent
= TREE_OPERAND (ref
, 0);
2667 if (TREE_CODE (ref
) == COMPONENT_REF
)
2669 /* All fields of a union are at its end. */
2670 if (TREE_CODE (TREE_TYPE (parent
)) == UNION_TYPE
)
2673 /* Unless the field is at the end of the struct, we are done. */
2674 field
= TREE_OPERAND (ref
, 1);
2675 if (DECL_CHAIN (field
))
2679 /* The other options are ARRAY_REF, ARRAY_RANGE_REF, VIEW_CONVERT_EXPR.
2680 In all these cases, we might be accessing the last element, and
2681 although in practice this will probably never happen, it is legal for
2682 the indices of this last element to exceed the bounds of the array.
2683 Therefore, continue checking. */
2689 /* Determine information about number of iterations a LOOP from the index
2690 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
2691 guaranteed to be executed in every iteration of LOOP. Callback for
2702 idx_infer_loop_bounds (tree base
, tree
*idx
, void *dta
)
2704 struct ilb_data
*data
= (struct ilb_data
*) dta
;
2705 tree ev
, init
, step
;
2706 tree low
, high
, type
, next
;
2707 bool sign
, upper
= data
->reliable
, at_end
= false;
2708 struct loop
*loop
= data
->loop
;
2710 if (TREE_CODE (base
) != ARRAY_REF
)
2713 /* For arrays at the end of the structure, we are not guaranteed that they
2714 do not really extend over their declared size. However, for arrays of
2715 size greater than one, this is unlikely to be intended. */
2716 if (array_at_struct_end_p (base
))
2722 ev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, *idx
));
2723 init
= initial_condition (ev
);
2724 step
= evolution_part_in_loop_num (ev
, loop
->num
);
2728 || TREE_CODE (step
) != INTEGER_CST
2729 || integer_zerop (step
)
2730 || tree_contains_chrecs (init
, NULL
)
2731 || chrec_contains_symbols_defined_in_loop (init
, loop
->num
))
2734 low
= array_ref_low_bound (base
);
2735 high
= array_ref_up_bound (base
);
2737 /* The case of nonconstant bounds could be handled, but it would be
2739 if (TREE_CODE (low
) != INTEGER_CST
2741 || TREE_CODE (high
) != INTEGER_CST
)
2743 sign
= tree_int_cst_sign_bit (step
);
2744 type
= TREE_TYPE (step
);
2746 /* The array of length 1 at the end of a structure most likely extends
2747 beyond its bounds. */
2749 && operand_equal_p (low
, high
, 0))
2752 /* In case the relevant bound of the array does not fit in type, or
2753 it does, but bound + step (in type) still belongs into the range of the
2754 array, the index may wrap and still stay within the range of the array
2755 (consider e.g. if the array is indexed by the full range of
2758 To make things simpler, we require both bounds to fit into type, although
2759 there are cases where this would not be strictly necessary. */
2760 if (!int_fits_type_p (high
, type
)
2761 || !int_fits_type_p (low
, type
))
2763 low
= fold_convert (type
, low
);
2764 high
= fold_convert (type
, high
);
2767 next
= fold_binary (PLUS_EXPR
, type
, low
, step
);
2769 next
= fold_binary (PLUS_EXPR
, type
, high
, step
);
2771 if (tree_int_cst_compare (low
, next
) <= 0
2772 && tree_int_cst_compare (next
, high
) <= 0)
2775 record_nonwrapping_iv (loop
, init
, step
, data
->stmt
, low
, high
, true, upper
);
2779 /* Determine information about number of iterations a LOOP from the bounds
2780 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
2781 STMT is guaranteed to be executed in every iteration of LOOP.*/
2784 infer_loop_bounds_from_ref (struct loop
*loop
, gimple stmt
, tree ref
,
2787 struct ilb_data data
;
2791 data
.reliable
= reliable
;
2792 for_each_index (&ref
, idx_infer_loop_bounds
, &data
);
2795 /* Determine information about number of iterations of a LOOP from the way
2796 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
2797 executed in every iteration of LOOP. */
2800 infer_loop_bounds_from_array (struct loop
*loop
, gimple stmt
, bool reliable
)
2802 if (is_gimple_assign (stmt
))
2804 tree op0
= gimple_assign_lhs (stmt
);
2805 tree op1
= gimple_assign_rhs1 (stmt
);
2807 /* For each memory access, analyze its access function
2808 and record a bound on the loop iteration domain. */
2809 if (REFERENCE_CLASS_P (op0
))
2810 infer_loop_bounds_from_ref (loop
, stmt
, op0
, reliable
);
2812 if (REFERENCE_CLASS_P (op1
))
2813 infer_loop_bounds_from_ref (loop
, stmt
, op1
, reliable
);
2815 else if (is_gimple_call (stmt
))
2818 unsigned i
, n
= gimple_call_num_args (stmt
);
2820 lhs
= gimple_call_lhs (stmt
);
2821 if (lhs
&& REFERENCE_CLASS_P (lhs
))
2822 infer_loop_bounds_from_ref (loop
, stmt
, lhs
, reliable
);
2824 for (i
= 0; i
< n
; i
++)
2826 arg
= gimple_call_arg (stmt
, i
);
2827 if (REFERENCE_CLASS_P (arg
))
2828 infer_loop_bounds_from_ref (loop
, stmt
, arg
, reliable
);
2833 /* Determine information about number of iterations of a LOOP from the fact
2834 that pointer arithmetics in STMT does not overflow. */
2837 infer_loop_bounds_from_pointer_arith (struct loop
*loop
, gimple stmt
)
2839 tree def
, base
, step
, scev
, type
, low
, high
;
2842 if (!is_gimple_assign (stmt
)
2843 || gimple_assign_rhs_code (stmt
) != POINTER_PLUS_EXPR
)
2846 def
= gimple_assign_lhs (stmt
);
2847 if (TREE_CODE (def
) != SSA_NAME
)
2850 type
= TREE_TYPE (def
);
2851 if (!nowrap_type_p (type
))
2854 ptr
= gimple_assign_rhs1 (stmt
);
2855 if (!expr_invariant_in_loop_p (loop
, ptr
))
2858 var
= gimple_assign_rhs2 (stmt
);
2859 if (TYPE_PRECISION (type
) != TYPE_PRECISION (TREE_TYPE (var
)))
2862 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
2863 if (chrec_contains_undetermined (scev
))
2866 base
= initial_condition_in_loop_num (scev
, loop
->num
);
2867 step
= evolution_part_in_loop_num (scev
, loop
->num
);
2870 || TREE_CODE (step
) != INTEGER_CST
2871 || tree_contains_chrecs (base
, NULL
)
2872 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
2875 low
= lower_bound_in_type (type
, type
);
2876 high
= upper_bound_in_type (type
, type
);
2878 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
2881 /* Determine information about number of iterations of a LOOP from the fact
2882 that signed arithmetics in STMT does not overflow. */
2885 infer_loop_bounds_from_signedness (struct loop
*loop
, gimple stmt
)
2887 tree def
, base
, step
, scev
, type
, low
, high
;
2889 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2892 def
= gimple_assign_lhs (stmt
);
2894 if (TREE_CODE (def
) != SSA_NAME
)
2897 type
= TREE_TYPE (def
);
2898 if (!INTEGRAL_TYPE_P (type
)
2899 || !TYPE_OVERFLOW_UNDEFINED (type
))
2902 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
2903 if (chrec_contains_undetermined (scev
))
2906 base
= initial_condition_in_loop_num (scev
, loop
->num
);
2907 step
= evolution_part_in_loop_num (scev
, loop
->num
);
2910 || TREE_CODE (step
) != INTEGER_CST
2911 || tree_contains_chrecs (base
, NULL
)
2912 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
2915 low
= lower_bound_in_type (type
, type
);
2916 high
= upper_bound_in_type (type
, type
);
2918 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
2921 /* The following analyzers are extracting informations on the bounds
2922 of LOOP from the following undefined behaviors:
2924 - data references should not access elements over the statically
2927 - signed variables should not overflow when flag_wrapv is not set.
2931 infer_loop_bounds_from_undefined (struct loop
*loop
)
2935 gimple_stmt_iterator bsi
;
2939 bbs
= get_loop_body (loop
);
2941 for (i
= 0; i
< loop
->num_nodes
; i
++)
2945 /* If BB is not executed in each iteration of the loop, we cannot
2946 use the operations in it to infer reliable upper bound on the
2947 # of iterations of the loop. However, we can use it as a guess. */
2948 reliable
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
);
2950 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2952 gimple stmt
= gsi_stmt (bsi
);
2954 infer_loop_bounds_from_array (loop
, stmt
, reliable
);
2958 infer_loop_bounds_from_signedness (loop
, stmt
);
2959 infer_loop_bounds_from_pointer_arith (loop
, stmt
);
2968 /* Converts VAL to double_int. */
2971 gcov_type_to_double_int (gcov_type val
)
2975 ret
.low
= (unsigned HOST_WIDE_INT
) val
;
2976 /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by
2977 the size of type. */
2978 val
>>= HOST_BITS_PER_WIDE_INT
- 1;
2980 ret
.high
= (unsigned HOST_WIDE_INT
) val
;
2985 /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
2986 is true also use estimates derived from undefined behavior. */
2989 estimate_numbers_of_iterations_loop (struct loop
*loop
, bool use_undefined_p
)
2991 VEC (edge
, heap
) *exits
;
2994 struct tree_niter_desc niter_desc
;
2998 /* Give up if we already have tried to compute an estimation. */
2999 if (loop
->estimate_state
!= EST_NOT_COMPUTED
)
3001 loop
->estimate_state
= EST_AVAILABLE
;
3002 loop
->any_upper_bound
= false;
3003 loop
->any_estimate
= false;
3005 exits
= get_loop_exit_edges (loop
);
3006 FOR_EACH_VEC_ELT (edge
, exits
, i
, ex
)
3008 if (!number_of_iterations_exit (loop
, ex
, &niter_desc
, false))
3011 niter
= niter_desc
.niter
;
3012 type
= TREE_TYPE (niter
);
3013 if (TREE_CODE (niter_desc
.may_be_zero
) != INTEGER_CST
)
3014 niter
= build3 (COND_EXPR
, type
, niter_desc
.may_be_zero
,
3015 build_int_cst (type
, 0),
3017 record_estimate (loop
, niter
, niter_desc
.max
,
3018 last_stmt (ex
->src
),
3021 VEC_free (edge
, heap
, exits
);
3023 if (use_undefined_p
)
3024 infer_loop_bounds_from_undefined (loop
);
3026 /* If we have a measured profile, use it to estimate the number of
3028 if (loop
->header
->count
!= 0)
3030 gcov_type nit
= expected_loop_iterations_unbounded (loop
) + 1;
3031 bound
= gcov_type_to_double_int (nit
);
3032 record_niter_bound (loop
, bound
, true, false);
3035 /* If an upper bound is smaller than the realistic estimate of the
3036 number of iterations, use the upper bound instead. */
3037 if (loop
->any_upper_bound
3038 && loop
->any_estimate
3039 && double_int_ucmp (loop
->nb_iterations_upper_bound
,
3040 loop
->nb_iterations_estimate
) < 0)
3041 loop
->nb_iterations_estimate
= loop
->nb_iterations_upper_bound
;
3044 /* Sets NIT to the estimated number of executions of the latch of the
3045 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
3046 large as the number of iterations. If we have no reliable estimate,
3047 the function returns false, otherwise returns true. */
3050 estimated_loop_iterations (struct loop
*loop
, bool conservative
,
3053 estimate_numbers_of_iterations_loop (loop
, true);
3056 if (!loop
->any_upper_bound
)
3059 *nit
= loop
->nb_iterations_upper_bound
;
3063 if (!loop
->any_estimate
)
3066 *nit
= loop
->nb_iterations_estimate
;
3072 /* Similar to estimated_loop_iterations, but returns the estimate only
3073 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3074 on the number of iterations of LOOP could not be derived, returns -1. */
3077 estimated_loop_iterations_int (struct loop
*loop
, bool conservative
)
3080 HOST_WIDE_INT hwi_nit
;
3082 if (!estimated_loop_iterations (loop
, conservative
, &nit
))
3085 if (!double_int_fits_in_shwi_p (nit
))
3087 hwi_nit
= double_int_to_shwi (nit
);
3089 return hwi_nit
< 0 ? -1 : hwi_nit
;
3092 /* Returns an upper bound on the number of executions of statements
3093 in the LOOP. For statements before the loop exit, this exceeds
3094 the number of execution of the latch by one. */
3097 max_stmt_executions_int (struct loop
*loop
, bool conservative
)
3099 HOST_WIDE_INT nit
= estimated_loop_iterations_int (loop
, conservative
);
3105 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
3107 /* If the computation overflows, return -1. */
3108 return snit
< 0 ? -1 : snit
;
3111 /* Sets NIT to the estimated number of executions of the latch of the
3112 LOOP, plus one. If CONSERVATIVE is true, we must be sure that NIT is at
3113 least as large as the number of iterations. If we have no reliable
3114 estimate, the function returns false, otherwise returns true. */
3117 max_stmt_executions (struct loop
*loop
, bool conservative
, double_int
*nit
)
3119 double_int nit_minus_one
;
3121 if (!estimated_loop_iterations (loop
, conservative
, nit
))
3124 nit_minus_one
= *nit
;
3126 *nit
= double_int_add (*nit
, double_int_one
);
3128 return double_int_ucmp (*nit
, nit_minus_one
) > 0;
3131 /* Records estimates on numbers of iterations of loops. */
3134 estimate_numbers_of_iterations (bool use_undefined_p
)
3139 /* We don't want to issue signed overflow warnings while getting
3140 loop iteration estimates. */
3141 fold_defer_overflow_warnings ();
3143 FOR_EACH_LOOP (li
, loop
, 0)
3145 estimate_numbers_of_iterations_loop (loop
, use_undefined_p
);
3148 fold_undefer_and_ignore_overflow_warnings ();
3151 /* Returns true if statement S1 dominates statement S2. */
3154 stmt_dominates_stmt_p (gimple s1
, gimple s2
)
3156 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
3164 gimple_stmt_iterator bsi
;
3166 if (gimple_code (s2
) == GIMPLE_PHI
)
3169 if (gimple_code (s1
) == GIMPLE_PHI
)
3172 for (bsi
= gsi_start_bb (bb1
); gsi_stmt (bsi
) != s2
; gsi_next (&bsi
))
3173 if (gsi_stmt (bsi
) == s1
)
3179 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
3182 /* Returns true when we can prove that the number of executions of
3183 STMT in the loop is at most NITER, according to the bound on
3184 the number of executions of the statement NITER_BOUND->stmt recorded in
3185 NITER_BOUND. If STMT is NULL, we must prove this bound for all
3186 statements in the loop. */
3189 n_of_executions_at_most (gimple stmt
,
3190 struct nb_iter_bound
*niter_bound
,
3193 double_int bound
= niter_bound
->bound
;
3194 tree nit_type
= TREE_TYPE (niter
), e
;
3197 gcc_assert (TYPE_UNSIGNED (nit_type
));
3199 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
3200 the number of iterations is small. */
3201 if (!double_int_fits_to_tree_p (nit_type
, bound
))
3204 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3205 times. This means that:
3207 -- if NITER_BOUND->is_exit is true, then everything before
3208 NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3209 times, and everything after it at most NITER_BOUND->bound times.
3211 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
3212 is executed, then NITER_BOUND->stmt is executed as well in the same
3213 iteration (we conclude that if both statements belong to the same
3214 basic block, or if STMT is after NITER_BOUND->stmt), then STMT
3215 is executed at most NITER_BOUND->bound + 1 times. Otherwise STMT is
3216 executed at most NITER_BOUND->bound + 2 times. */
3218 if (niter_bound
->is_exit
)
3221 && stmt
!= niter_bound
->stmt
3222 && stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
3230 || (gimple_bb (stmt
) != gimple_bb (niter_bound
->stmt
)
3231 && !stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
)))
3233 bound
= double_int_add (bound
, double_int_one
);
3234 if (double_int_zero_p (bound
)
3235 || !double_int_fits_to_tree_p (nit_type
, bound
))
3241 e
= fold_binary (cmp
, boolean_type_node
,
3242 niter
, double_int_to_tree (nit_type
, bound
));
3243 return e
&& integer_nonzerop (e
);
3246 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
3249 nowrap_type_p (tree type
)
3251 if (INTEGRAL_TYPE_P (type
)
3252 && TYPE_OVERFLOW_UNDEFINED (type
))
3255 if (POINTER_TYPE_P (type
))
3261 /* Return false only when the induction variable BASE + STEP * I is
3262 known to not overflow: i.e. when the number of iterations is small
3263 enough with respect to the step and initial condition in order to
3264 keep the evolution confined in TYPEs bounds. Return true when the
3265 iv is known to overflow or when the property is not computable.
3267 USE_OVERFLOW_SEMANTICS is true if this function should assume that
3268 the rules for overflow of the given language apply (e.g., that signed
3269 arithmetics in C does not overflow). */
3272 scev_probably_wraps_p (tree base
, tree step
,
3273 gimple at_stmt
, struct loop
*loop
,
3274 bool use_overflow_semantics
)
3276 struct nb_iter_bound
*bound
;
3277 tree delta
, step_abs
;
3278 tree unsigned_type
, valid_niter
;
3279 tree type
= TREE_TYPE (step
);
3281 /* FIXME: We really need something like
3282 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
3284 We used to test for the following situation that frequently appears
3285 during address arithmetics:
3287 D.1621_13 = (long unsigned intD.4) D.1620_12;
3288 D.1622_14 = D.1621_13 * 8;
3289 D.1623_15 = (doubleD.29 *) D.1622_14;
3291 And derived that the sequence corresponding to D_14
3292 can be proved to not wrap because it is used for computing a
3293 memory access; however, this is not really the case -- for example,
3294 if D_12 = (unsigned char) [254,+,1], then D_14 has values
3295 2032, 2040, 0, 8, ..., but the code is still legal. */
3297 if (chrec_contains_undetermined (base
)
3298 || chrec_contains_undetermined (step
))
3301 if (integer_zerop (step
))
3304 /* If we can use the fact that signed and pointer arithmetics does not
3305 wrap, we are done. */
3306 if (use_overflow_semantics
&& nowrap_type_p (TREE_TYPE (base
)))
3309 /* To be able to use estimates on number of iterations of the loop,
3310 we must have an upper bound on the absolute value of the step. */
3311 if (TREE_CODE (step
) != INTEGER_CST
)
3314 /* Don't issue signed overflow warnings. */
3315 fold_defer_overflow_warnings ();
3317 /* Otherwise, compute the number of iterations before we reach the
3318 bound of the type, and verify that the loop is exited before this
3320 unsigned_type
= unsigned_type_for (type
);
3321 base
= fold_convert (unsigned_type
, base
);
3323 if (tree_int_cst_sign_bit (step
))
3325 tree extreme
= fold_convert (unsigned_type
,
3326 lower_bound_in_type (type
, type
));
3327 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
3328 step_abs
= fold_build1 (NEGATE_EXPR
, unsigned_type
,
3329 fold_convert (unsigned_type
, step
));
3333 tree extreme
= fold_convert (unsigned_type
,
3334 upper_bound_in_type (type
, type
));
3335 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
3336 step_abs
= fold_convert (unsigned_type
, step
);
3339 valid_niter
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step_abs
);
3341 estimate_numbers_of_iterations_loop (loop
, true);
3342 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
3344 if (n_of_executions_at_most (at_stmt
, bound
, valid_niter
))
3346 fold_undefer_and_ignore_overflow_warnings ();
3351 fold_undefer_and_ignore_overflow_warnings ();
3353 /* At this point we still don't have a proof that the iv does not
3354 overflow: give up. */
3358 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
3361 free_numbers_of_iterations_estimates_loop (struct loop
*loop
)
3363 struct nb_iter_bound
*bound
, *next
;
3365 loop
->nb_iterations
= NULL
;
3366 loop
->estimate_state
= EST_NOT_COMPUTED
;
3367 for (bound
= loop
->bounds
; bound
; bound
= next
)
3373 loop
->bounds
= NULL
;
3376 /* Frees the information on upper bounds on numbers of iterations of loops. */
3379 free_numbers_of_iterations_estimates (void)
3384 FOR_EACH_LOOP (li
, loop
, 0)
3386 free_numbers_of_iterations_estimates_loop (loop
);
3390 /* Substitute value VAL for ssa name NAME inside expressions held
3394 substitute_in_loop_info (struct loop
*loop
, tree name
, tree val
)
3396 loop
->nb_iterations
= simplify_replace_tree (loop
->nb_iterations
, name
, val
);