1 /* Functions to determine/estimate number of iterations of a loop.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
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 "gimple-pretty-print.h"
30 #include "tree-flow.h"
34 #include "tree-chrec.h"
35 #include "tree-scalar-evolution.h"
36 #include "tree-data-ref.h"
39 #include "diagnostic-core.h"
40 #include "tree-inline.h"
43 #define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
45 /* The maximum number of dominator BBs we search for conditions
46 of loop header copies we use for simplifying a conditional
48 #define MAX_DOMINATORS_TO_WALK 8
52 Analysis of number of iterations of an affine exit test.
56 /* Bounds on some value, BELOW <= X <= UP. */
64 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */
67 split_to_var_and_offset (tree expr
, tree
*var
, mpz_t offset
)
69 tree type
= TREE_TYPE (expr
);
75 mpz_set_ui (offset
, 0);
77 switch (TREE_CODE (expr
))
84 case POINTER_PLUS_EXPR
:
85 op0
= TREE_OPERAND (expr
, 0);
86 op1
= TREE_OPERAND (expr
, 1);
88 if (TREE_CODE (op1
) != INTEGER_CST
)
92 /* Always sign extend the offset. */
93 off
= tree_to_double_int (op1
);
94 off
= off
.sext (TYPE_PRECISION (type
));
95 mpz_set_double_int (offset
, off
, false);
97 mpz_neg (offset
, offset
);
101 *var
= build_int_cst_type (type
, 0);
102 off
= tree_to_double_int (expr
);
103 mpz_set_double_int (offset
, off
, TYPE_UNSIGNED (type
));
111 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
112 in TYPE to MIN and MAX. */
115 determine_value_range (tree type
, tree var
, mpz_t off
,
116 mpz_t min
, mpz_t max
)
118 /* If the expression is a constant, we know its value exactly. */
119 if (integer_zerop (var
))
126 /* If the computation may wrap, we know nothing about the value, except for
127 the range of the type. */
128 get_type_static_bounds (type
, min
, max
);
129 if (!nowrap_type_p (type
))
132 /* Since the addition of OFF does not wrap, if OFF is positive, then we may
133 add it to MIN, otherwise to MAX. */
134 if (mpz_sgn (off
) < 0)
135 mpz_add (max
, max
, off
);
137 mpz_add (min
, min
, off
);
140 /* Stores the bounds on the difference of the values of the expressions
141 (var + X) and (var + Y), computed in TYPE, to BNDS. */
144 bound_difference_of_offsetted_base (tree type
, mpz_t x
, mpz_t y
,
147 int rel
= mpz_cmp (x
, y
);
148 bool may_wrap
= !nowrap_type_p (type
);
151 /* If X == Y, then the expressions are always equal.
152 If X > Y, there are the following possibilities:
153 a) neither of var + X and var + Y overflow or underflow, or both of
154 them do. Then their difference is X - Y.
155 b) var + X overflows, and var + Y does not. Then the values of the
156 expressions are var + X - M and var + Y, where M is the range of
157 the type, and their difference is X - Y - M.
158 c) var + Y underflows and var + X does not. Their difference again
160 Therefore, if the arithmetics in type does not overflow, then the
161 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
162 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
163 (X - Y, X - Y + M). */
167 mpz_set_ui (bnds
->below
, 0);
168 mpz_set_ui (bnds
->up
, 0);
173 mpz_set_double_int (m
, double_int::mask (TYPE_PRECISION (type
)), true);
174 mpz_add_ui (m
, m
, 1);
175 mpz_sub (bnds
->up
, x
, y
);
176 mpz_set (bnds
->below
, bnds
->up
);
181 mpz_sub (bnds
->below
, bnds
->below
, m
);
183 mpz_add (bnds
->up
, bnds
->up
, m
);
189 /* From condition C0 CMP C1 derives information regarding the
190 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
191 and stores it to BNDS. */
194 refine_bounds_using_guard (tree type
, tree varx
, mpz_t offx
,
195 tree vary
, mpz_t offy
,
196 tree c0
, enum tree_code cmp
, tree c1
,
199 tree varc0
, varc1
, tmp
, ctype
;
200 mpz_t offc0
, offc1
, loffx
, loffy
, bnd
;
202 bool no_wrap
= nowrap_type_p (type
);
211 STRIP_SIGN_NOPS (c0
);
212 STRIP_SIGN_NOPS (c1
);
213 ctype
= TREE_TYPE (c0
);
214 if (!useless_type_conversion_p (ctype
, type
))
220 /* We could derive quite precise information from EQ_EXPR, however, such
221 a guard is unlikely to appear, so we do not bother with handling
226 /* NE_EXPR comparisons do not contain much of useful information, except for
227 special case of comparing with the bounds of the type. */
228 if (TREE_CODE (c1
) != INTEGER_CST
229 || !INTEGRAL_TYPE_P (type
))
232 /* Ensure that the condition speaks about an expression in the same type
234 ctype
= TREE_TYPE (c0
);
235 if (TYPE_PRECISION (ctype
) != TYPE_PRECISION (type
))
237 c0
= fold_convert (type
, c0
);
238 c1
= fold_convert (type
, c1
);
240 if (TYPE_MIN_VALUE (type
)
241 && operand_equal_p (c1
, TYPE_MIN_VALUE (type
), 0))
246 if (TYPE_MAX_VALUE (type
)
247 && operand_equal_p (c1
, TYPE_MAX_VALUE (type
), 0))
260 split_to_var_and_offset (expand_simple_operations (c0
), &varc0
, offc0
);
261 split_to_var_and_offset (expand_simple_operations (c1
), &varc1
, offc1
);
263 /* We are only interested in comparisons of expressions based on VARX and
264 VARY. TODO -- we might also be able to derive some bounds from
265 expressions containing just one of the variables. */
267 if (operand_equal_p (varx
, varc1
, 0))
269 tmp
= varc0
; varc0
= varc1
; varc1
= tmp
;
270 mpz_swap (offc0
, offc1
);
271 cmp
= swap_tree_comparison (cmp
);
274 if (!operand_equal_p (varx
, varc0
, 0)
275 || !operand_equal_p (vary
, varc1
, 0))
278 mpz_init_set (loffx
, offx
);
279 mpz_init_set (loffy
, offy
);
281 if (cmp
== GT_EXPR
|| cmp
== GE_EXPR
)
283 tmp
= varx
; varx
= vary
; vary
= tmp
;
284 mpz_swap (offc0
, offc1
);
285 mpz_swap (loffx
, loffy
);
286 cmp
= swap_tree_comparison (cmp
);
290 /* If there is no overflow, the condition implies that
292 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
294 The overflows and underflows may complicate things a bit; each
295 overflow decreases the appropriate offset by M, and underflow
296 increases it by M. The above inequality would not necessarily be
299 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
300 VARX + OFFC0 overflows, but VARX + OFFX does not.
301 This may only happen if OFFX < OFFC0.
302 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
303 VARY + OFFC1 underflows and VARY + OFFY does not.
304 This may only happen if OFFY > OFFC1. */
313 x_ok
= (integer_zerop (varx
)
314 || mpz_cmp (loffx
, offc0
) >= 0);
315 y_ok
= (integer_zerop (vary
)
316 || mpz_cmp (loffy
, offc1
) <= 0);
322 mpz_sub (bnd
, loffx
, loffy
);
323 mpz_add (bnd
, bnd
, offc1
);
324 mpz_sub (bnd
, bnd
, offc0
);
327 mpz_sub_ui (bnd
, bnd
, 1);
332 if (mpz_cmp (bnds
->below
, bnd
) < 0)
333 mpz_set (bnds
->below
, bnd
);
337 if (mpz_cmp (bnd
, bnds
->up
) < 0)
338 mpz_set (bnds
->up
, bnd
);
350 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
351 The subtraction is considered to be performed in arbitrary precision,
354 We do not attempt to be too clever regarding the value ranges of X and
355 Y; most of the time, they are just integers or ssa names offsetted by
356 integer. However, we try to use the information contained in the
357 comparisons before the loop (usually created by loop header copying). */
360 bound_difference (struct loop
*loop
, tree x
, tree y
, bounds
*bnds
)
362 tree type
= TREE_TYPE (x
);
365 mpz_t minx
, maxx
, miny
, maxy
;
373 /* Get rid of unnecessary casts, but preserve the value of
378 mpz_init (bnds
->below
);
382 split_to_var_and_offset (x
, &varx
, offx
);
383 split_to_var_and_offset (y
, &vary
, offy
);
385 if (!integer_zerop (varx
)
386 && operand_equal_p (varx
, vary
, 0))
388 /* Special case VARX == VARY -- we just need to compare the
389 offsets. The matters are a bit more complicated in the
390 case addition of offsets may wrap. */
391 bound_difference_of_offsetted_base (type
, offx
, offy
, bnds
);
395 /* Otherwise, use the value ranges to determine the initial
396 estimates on below and up. */
401 determine_value_range (type
, varx
, offx
, minx
, maxx
);
402 determine_value_range (type
, vary
, offy
, miny
, maxy
);
404 mpz_sub (bnds
->below
, minx
, maxy
);
405 mpz_sub (bnds
->up
, maxx
, miny
);
412 /* If both X and Y are constants, we cannot get any more precise. */
413 if (integer_zerop (varx
) && integer_zerop (vary
))
416 /* Now walk the dominators of the loop header and use the entry
417 guards to refine the estimates. */
418 for (bb
= loop
->header
;
419 bb
!= ENTRY_BLOCK_PTR
&& cnt
< MAX_DOMINATORS_TO_WALK
;
420 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
422 if (!single_pred_p (bb
))
424 e
= single_pred_edge (bb
);
426 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
429 cond
= last_stmt (e
->src
);
430 c0
= gimple_cond_lhs (cond
);
431 cmp
= gimple_cond_code (cond
);
432 c1
= gimple_cond_rhs (cond
);
434 if (e
->flags
& EDGE_FALSE_VALUE
)
435 cmp
= invert_tree_comparison (cmp
, false);
437 refine_bounds_using_guard (type
, varx
, offx
, vary
, offy
,
447 /* Update the bounds in BNDS that restrict the value of X to the bounds
448 that restrict the value of X + DELTA. X can be obtained as a
449 difference of two values in TYPE. */
452 bounds_add (bounds
*bnds
, double_int delta
, tree type
)
457 mpz_set_double_int (mdelta
, delta
, false);
460 mpz_set_double_int (max
, double_int::mask (TYPE_PRECISION (type
)), true);
462 mpz_add (bnds
->up
, bnds
->up
, mdelta
);
463 mpz_add (bnds
->below
, bnds
->below
, mdelta
);
465 if (mpz_cmp (bnds
->up
, max
) > 0)
466 mpz_set (bnds
->up
, max
);
469 if (mpz_cmp (bnds
->below
, max
) < 0)
470 mpz_set (bnds
->below
, max
);
476 /* Update the bounds in BNDS that restrict the value of X to the bounds
477 that restrict the value of -X. */
480 bounds_negate (bounds
*bnds
)
484 mpz_init_set (tmp
, bnds
->up
);
485 mpz_neg (bnds
->up
, bnds
->below
);
486 mpz_neg (bnds
->below
, tmp
);
490 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
493 inverse (tree x
, tree mask
)
495 tree type
= TREE_TYPE (x
);
497 unsigned ctr
= tree_floor_log2 (mask
);
499 if (TYPE_PRECISION (type
) <= HOST_BITS_PER_WIDE_INT
)
501 unsigned HOST_WIDE_INT ix
;
502 unsigned HOST_WIDE_INT imask
;
503 unsigned HOST_WIDE_INT irslt
= 1;
505 gcc_assert (cst_and_fits_in_hwi (x
));
506 gcc_assert (cst_and_fits_in_hwi (mask
));
508 ix
= int_cst_value (x
);
509 imask
= int_cst_value (mask
);
518 rslt
= build_int_cst_type (type
, irslt
);
522 rslt
= build_int_cst (type
, 1);
525 rslt
= int_const_binop (MULT_EXPR
, rslt
, x
);
526 x
= int_const_binop (MULT_EXPR
, x
, x
);
528 rslt
= int_const_binop (BIT_AND_EXPR
, rslt
, mask
);
534 /* Derives the upper bound BND on the number of executions of loop with exit
535 condition S * i <> C. If NO_OVERFLOW is true, then the control variable of
536 the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed
537 that the loop ends through this exit, i.e., the induction variable ever
538 reaches the value of C.
540 The value C is equal to final - base, where final and base are the final and
541 initial value of the actual induction variable in the analysed loop. BNDS
542 bounds the value of this difference when computed in signed type with
543 unbounded range, while the computation of C is performed in an unsigned
544 type with the range matching the range of the type of the induction variable.
545 In particular, BNDS.up contains an upper bound on C in the following cases:
546 -- if the iv must reach its final value without overflow, i.e., if
547 NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
548 -- if final >= base, which we know to hold when BNDS.below >= 0. */
551 number_of_iterations_ne_max (mpz_t bnd
, bool no_overflow
, tree c
, tree s
,
552 bounds
*bnds
, bool exit_must_be_taken
)
556 bool bnds_u_valid
= ((no_overflow
&& exit_must_be_taken
)
557 || mpz_sgn (bnds
->below
) >= 0);
559 if (multiple_of_p (TREE_TYPE (c
), c
, s
))
561 /* If C is an exact multiple of S, then its value will be reached before
562 the induction variable overflows (unless the loop is exited in some
563 other way before). Note that the actual induction variable in the
564 loop (which ranges from base to final instead of from 0 to C) may
565 overflow, in which case BNDS.up will not be giving a correct upper
566 bound on C; thus, BNDS_U_VALID had to be computed in advance. */
568 exit_must_be_taken
= true;
571 /* If the induction variable can overflow, the number of iterations is at
572 most the period of the control variable (or infinite, but in that case
573 the whole # of iterations analysis will fail). */
576 max
= double_int::mask (TYPE_PRECISION (TREE_TYPE (c
))
577 - tree_low_cst (num_ending_zeros (s
), 1));
578 mpz_set_double_int (bnd
, max
, true);
582 /* Now we know that the induction variable does not overflow, so the loop
583 iterates at most (range of type / S) times. */
584 mpz_set_double_int (bnd
, double_int::mask (TYPE_PRECISION (TREE_TYPE (c
))),
587 /* If the induction variable is guaranteed to reach the value of C before
589 if (exit_must_be_taken
)
591 /* ... then we can strengthen this to C / S, and possibly we can use
592 the upper bound on C given by BNDS. */
593 if (TREE_CODE (c
) == INTEGER_CST
)
594 mpz_set_double_int (bnd
, tree_to_double_int (c
), true);
595 else if (bnds_u_valid
)
596 mpz_set (bnd
, bnds
->up
);
600 mpz_set_double_int (d
, tree_to_double_int (s
), true);
601 mpz_fdiv_q (bnd
, bnd
, d
);
605 /* Determines number of iterations of loop whose ending condition
606 is IV <> FINAL. TYPE is the type of the iv. The number of
607 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
608 we know that the exit must be taken eventually, i.e., that the IV
609 ever reaches the value FINAL (we derived this earlier, and possibly set
610 NITER->assumptions to make sure this is the case). BNDS contains the
611 bounds on the difference FINAL - IV->base. */
614 number_of_iterations_ne (tree type
, affine_iv
*iv
, tree final
,
615 struct tree_niter_desc
*niter
, bool exit_must_be_taken
,
618 tree niter_type
= unsigned_type_for (type
);
619 tree s
, c
, d
, bits
, assumption
, tmp
, bound
;
622 niter
->control
= *iv
;
623 niter
->bound
= final
;
624 niter
->cmp
= NE_EXPR
;
626 /* Rearrange the terms so that we get inequality S * i <> C, with S
627 positive. Also cast everything to the unsigned type. If IV does
628 not overflow, BNDS bounds the value of C. Also, this is the
629 case if the computation |FINAL - IV->base| does not overflow, i.e.,
630 if BNDS->below in the result is nonnegative. */
631 if (tree_int_cst_sign_bit (iv
->step
))
633 s
= fold_convert (niter_type
,
634 fold_build1 (NEGATE_EXPR
, type
, iv
->step
));
635 c
= fold_build2 (MINUS_EXPR
, niter_type
,
636 fold_convert (niter_type
, iv
->base
),
637 fold_convert (niter_type
, final
));
638 bounds_negate (bnds
);
642 s
= fold_convert (niter_type
, iv
->step
);
643 c
= fold_build2 (MINUS_EXPR
, niter_type
,
644 fold_convert (niter_type
, final
),
645 fold_convert (niter_type
, iv
->base
));
649 number_of_iterations_ne_max (max
, iv
->no_overflow
, c
, s
, bnds
,
651 niter
->max
= mpz_get_double_int (niter_type
, max
, false);
654 /* First the trivial cases -- when the step is 1. */
655 if (integer_onep (s
))
661 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
662 is infinite. Otherwise, the number of iterations is
663 (inverse(s/d) * (c/d)) mod (size of mode/d). */
664 bits
= num_ending_zeros (s
);
665 bound
= build_low_bits_mask (niter_type
,
666 (TYPE_PRECISION (niter_type
)
667 - tree_low_cst (bits
, 1)));
669 d
= fold_binary_to_constant (LSHIFT_EXPR
, niter_type
,
670 build_int_cst (niter_type
, 1), bits
);
671 s
= fold_binary_to_constant (RSHIFT_EXPR
, niter_type
, s
, bits
);
673 if (!exit_must_be_taken
)
675 /* If we cannot assume that the exit is taken eventually, record the
676 assumptions for divisibility of c. */
677 assumption
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, c
, d
);
678 assumption
= fold_build2 (EQ_EXPR
, boolean_type_node
,
679 assumption
, build_int_cst (niter_type
, 0));
680 if (!integer_nonzerop (assumption
))
681 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
682 niter
->assumptions
, assumption
);
685 c
= fold_build2 (EXACT_DIV_EXPR
, niter_type
, c
, d
);
686 tmp
= fold_build2 (MULT_EXPR
, niter_type
, c
, inverse (s
, bound
));
687 niter
->niter
= fold_build2 (BIT_AND_EXPR
, niter_type
, tmp
, bound
);
691 /* Checks whether we can determine the final value of the control variable
692 of the loop with ending condition IV0 < IV1 (computed in TYPE).
693 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
694 of the step. The assumptions necessary to ensure that the computation
695 of the final value does not overflow are recorded in NITER. If we
696 find the final value, we adjust DELTA and return TRUE. Otherwise
697 we return false. BNDS bounds the value of IV1->base - IV0->base,
698 and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
699 true if we know that the exit must be taken eventually. */
702 number_of_iterations_lt_to_ne (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
703 struct tree_niter_desc
*niter
,
704 tree
*delta
, tree step
,
705 bool exit_must_be_taken
, bounds
*bnds
)
707 tree niter_type
= TREE_TYPE (step
);
708 tree mod
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, *delta
, step
);
711 tree assumption
= boolean_true_node
, bound
, noloop
;
712 bool ret
= false, fv_comp_no_overflow
;
714 if (POINTER_TYPE_P (type
))
717 if (TREE_CODE (mod
) != INTEGER_CST
)
719 if (integer_nonzerop (mod
))
720 mod
= fold_build2 (MINUS_EXPR
, niter_type
, step
, mod
);
721 tmod
= fold_convert (type1
, mod
);
724 mpz_set_double_int (mmod
, tree_to_double_int (mod
), true);
725 mpz_neg (mmod
, mmod
);
727 /* If the induction variable does not overflow and the exit is taken,
728 then the computation of the final value does not overflow. This is
729 also obviously the case if the new final value is equal to the
730 current one. Finally, we postulate this for pointer type variables,
731 as the code cannot rely on the object to that the pointer points being
732 placed at the end of the address space (and more pragmatically,
733 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
734 if (integer_zerop (mod
) || POINTER_TYPE_P (type
))
735 fv_comp_no_overflow
= true;
736 else if (!exit_must_be_taken
)
737 fv_comp_no_overflow
= false;
739 fv_comp_no_overflow
=
740 (iv0
->no_overflow
&& integer_nonzerop (iv0
->step
))
741 || (iv1
->no_overflow
&& integer_nonzerop (iv1
->step
));
743 if (integer_nonzerop (iv0
->step
))
745 /* The final value of the iv is iv1->base + MOD, assuming that this
746 computation does not overflow, and that
747 iv0->base <= iv1->base + MOD. */
748 if (!fv_comp_no_overflow
)
750 bound
= fold_build2 (MINUS_EXPR
, type1
,
751 TYPE_MAX_VALUE (type1
), tmod
);
752 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
754 if (integer_zerop (assumption
))
757 if (mpz_cmp (mmod
, bnds
->below
) < 0)
758 noloop
= boolean_false_node
;
759 else if (POINTER_TYPE_P (type
))
760 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
762 fold_build_pointer_plus (iv1
->base
, tmod
));
764 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
766 fold_build2 (PLUS_EXPR
, type1
,
771 /* The final value of the iv is iv0->base - MOD, assuming that this
772 computation does not overflow, and that
773 iv0->base - MOD <= iv1->base. */
774 if (!fv_comp_no_overflow
)
776 bound
= fold_build2 (PLUS_EXPR
, type1
,
777 TYPE_MIN_VALUE (type1
), tmod
);
778 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
780 if (integer_zerop (assumption
))
783 if (mpz_cmp (mmod
, bnds
->below
) < 0)
784 noloop
= boolean_false_node
;
785 else if (POINTER_TYPE_P (type
))
786 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
787 fold_build_pointer_plus (iv0
->base
,
788 fold_build1 (NEGATE_EXPR
,
792 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
793 fold_build2 (MINUS_EXPR
, type1
,
798 if (!integer_nonzerop (assumption
))
799 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
802 if (!integer_zerop (noloop
))
803 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
806 bounds_add (bnds
, tree_to_double_int (mod
), type
);
807 *delta
= fold_build2 (PLUS_EXPR
, niter_type
, *delta
, mod
);
815 /* Add assertions to NITER that ensure that the control variable of the loop
816 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
817 are TYPE. Returns false if we can prove that there is an overflow, true
818 otherwise. STEP is the absolute value of the step. */
821 assert_no_overflow_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
822 struct tree_niter_desc
*niter
, tree step
)
824 tree bound
, d
, assumption
, diff
;
825 tree niter_type
= TREE_TYPE (step
);
827 if (integer_nonzerop (iv0
->step
))
829 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
830 if (iv0
->no_overflow
)
833 /* If iv0->base is a constant, we can determine the last value before
834 overflow precisely; otherwise we conservatively assume
837 if (TREE_CODE (iv0
->base
) == INTEGER_CST
)
839 d
= fold_build2 (MINUS_EXPR
, niter_type
,
840 fold_convert (niter_type
, TYPE_MAX_VALUE (type
)),
841 fold_convert (niter_type
, iv0
->base
));
842 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
845 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
846 build_int_cst (niter_type
, 1));
847 bound
= fold_build2 (MINUS_EXPR
, type
,
848 TYPE_MAX_VALUE (type
), fold_convert (type
, diff
));
849 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
854 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
855 if (iv1
->no_overflow
)
858 if (TREE_CODE (iv1
->base
) == INTEGER_CST
)
860 d
= fold_build2 (MINUS_EXPR
, niter_type
,
861 fold_convert (niter_type
, iv1
->base
),
862 fold_convert (niter_type
, TYPE_MIN_VALUE (type
)));
863 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
866 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
867 build_int_cst (niter_type
, 1));
868 bound
= fold_build2 (PLUS_EXPR
, type
,
869 TYPE_MIN_VALUE (type
), fold_convert (type
, diff
));
870 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
874 if (integer_zerop (assumption
))
876 if (!integer_nonzerop (assumption
))
877 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
878 niter
->assumptions
, assumption
);
880 iv0
->no_overflow
= true;
881 iv1
->no_overflow
= true;
885 /* Add an assumption to NITER that a loop whose ending condition
886 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
887 bounds the value of IV1->base - IV0->base. */
890 assert_loop_rolls_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
891 struct tree_niter_desc
*niter
, bounds
*bnds
)
893 tree assumption
= boolean_true_node
, bound
, diff
;
894 tree mbz
, mbzl
, mbzr
, type1
;
895 bool rolls_p
, no_overflow_p
;
899 /* We are going to compute the number of iterations as
900 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
901 variant of TYPE. This formula only works if
903 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
905 (where MAX is the maximum value of the unsigned variant of TYPE, and
906 the computations in this formula are performed in full precision,
907 i.e., without overflows).
909 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
910 we have a condition of the form iv0->base - step < iv1->base before the loop,
911 and for loops iv0->base < iv1->base - step * i the condition
912 iv0->base < iv1->base + step, due to loop header copying, which enable us
913 to prove the lower bound.
915 The upper bound is more complicated. Unless the expressions for initial
916 and final value themselves contain enough information, we usually cannot
917 derive it from the context. */
919 /* First check whether the answer does not follow from the bounds we gathered
921 if (integer_nonzerop (iv0
->step
))
922 dstep
= tree_to_double_int (iv0
->step
);
925 dstep
= tree_to_double_int (iv1
->step
).sext (TYPE_PRECISION (type
));
930 mpz_set_double_int (mstep
, dstep
, true);
931 mpz_neg (mstep
, mstep
);
932 mpz_add_ui (mstep
, mstep
, 1);
934 rolls_p
= mpz_cmp (mstep
, bnds
->below
) <= 0;
937 mpz_set_double_int (max
, double_int::mask (TYPE_PRECISION (type
)), true);
938 mpz_add (max
, max
, mstep
);
939 no_overflow_p
= (mpz_cmp (bnds
->up
, max
) <= 0
940 /* For pointers, only values lying inside a single object
941 can be compared or manipulated by pointer arithmetics.
942 Gcc in general does not allow or handle objects larger
943 than half of the address space, hence the upper bound
944 is satisfied for pointers. */
945 || POINTER_TYPE_P (type
));
949 if (rolls_p
&& no_overflow_p
)
953 if (POINTER_TYPE_P (type
))
956 /* Now the hard part; we must formulate the assumption(s) as expressions, and
957 we must be careful not to introduce overflow. */
959 if (integer_nonzerop (iv0
->step
))
961 diff
= fold_build2 (MINUS_EXPR
, type1
,
962 iv0
->step
, build_int_cst (type1
, 1));
964 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
965 0 address never belongs to any object, we can assume this for
967 if (!POINTER_TYPE_P (type
))
969 bound
= fold_build2 (PLUS_EXPR
, type1
,
970 TYPE_MIN_VALUE (type
), diff
);
971 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
975 /* And then we can compute iv0->base - diff, and compare it with
977 mbzl
= fold_build2 (MINUS_EXPR
, type1
,
978 fold_convert (type1
, iv0
->base
), diff
);
979 mbzr
= fold_convert (type1
, iv1
->base
);
983 diff
= fold_build2 (PLUS_EXPR
, type1
,
984 iv1
->step
, build_int_cst (type1
, 1));
986 if (!POINTER_TYPE_P (type
))
988 bound
= fold_build2 (PLUS_EXPR
, type1
,
989 TYPE_MAX_VALUE (type
), diff
);
990 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
994 mbzl
= fold_convert (type1
, iv0
->base
);
995 mbzr
= fold_build2 (MINUS_EXPR
, type1
,
996 fold_convert (type1
, iv1
->base
), diff
);
999 if (!integer_nonzerop (assumption
))
1000 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1001 niter
->assumptions
, assumption
);
1004 mbz
= fold_build2 (GT_EXPR
, boolean_type_node
, mbzl
, mbzr
);
1005 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1006 niter
->may_be_zero
, mbz
);
1010 /* Determines number of iterations of loop whose ending condition
1011 is IV0 < IV1. TYPE is the type of the iv. The number of
1012 iterations is stored to NITER. BNDS bounds the difference
1013 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
1014 that the exit must be taken eventually. */
1017 number_of_iterations_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1018 struct tree_niter_desc
*niter
,
1019 bool exit_must_be_taken
, bounds
*bnds
)
1021 tree niter_type
= unsigned_type_for (type
);
1022 tree delta
, step
, s
;
1025 if (integer_nonzerop (iv0
->step
))
1027 niter
->control
= *iv0
;
1028 niter
->cmp
= LT_EXPR
;
1029 niter
->bound
= iv1
->base
;
1033 niter
->control
= *iv1
;
1034 niter
->cmp
= GT_EXPR
;
1035 niter
->bound
= iv0
->base
;
1038 delta
= fold_build2 (MINUS_EXPR
, niter_type
,
1039 fold_convert (niter_type
, iv1
->base
),
1040 fold_convert (niter_type
, iv0
->base
));
1042 /* First handle the special case that the step is +-1. */
1043 if ((integer_onep (iv0
->step
) && integer_zerop (iv1
->step
))
1044 || (integer_all_onesp (iv1
->step
) && integer_zerop (iv0
->step
)))
1046 /* for (i = iv0->base; i < iv1->base; i++)
1050 for (i = iv1->base; i > iv0->base; i--).
1052 In both cases # of iterations is iv1->base - iv0->base, assuming that
1053 iv1->base >= iv0->base.
1055 First try to derive a lower bound on the value of
1056 iv1->base - iv0->base, computed in full precision. If the difference
1057 is nonnegative, we are done, otherwise we must record the
1060 if (mpz_sgn (bnds
->below
) < 0)
1061 niter
->may_be_zero
= fold_build2 (LT_EXPR
, boolean_type_node
,
1062 iv1
->base
, iv0
->base
);
1063 niter
->niter
= delta
;
1064 niter
->max
= mpz_get_double_int (niter_type
, bnds
->up
, false);
1068 if (integer_nonzerop (iv0
->step
))
1069 step
= fold_convert (niter_type
, iv0
->step
);
1071 step
= fold_convert (niter_type
,
1072 fold_build1 (NEGATE_EXPR
, type
, iv1
->step
));
1074 /* If we can determine the final value of the control iv exactly, we can
1075 transform the condition to != comparison. In particular, this will be
1076 the case if DELTA is constant. */
1077 if (number_of_iterations_lt_to_ne (type
, iv0
, iv1
, niter
, &delta
, step
,
1078 exit_must_be_taken
, bnds
))
1082 zps
.base
= build_int_cst (niter_type
, 0);
1084 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1085 zps does not overflow. */
1086 zps
.no_overflow
= true;
1088 return number_of_iterations_ne (type
, &zps
, delta
, niter
, true, bnds
);
1091 /* Make sure that the control iv does not overflow. */
1092 if (!assert_no_overflow_lt (type
, iv0
, iv1
, niter
, step
))
1095 /* We determine the number of iterations as (delta + step - 1) / step. For
1096 this to work, we must know that iv1->base >= iv0->base - step + 1,
1097 otherwise the loop does not roll. */
1098 assert_loop_rolls_lt (type
, iv0
, iv1
, niter
, bnds
);
1100 s
= fold_build2 (MINUS_EXPR
, niter_type
,
1101 step
, build_int_cst (niter_type
, 1));
1102 delta
= fold_build2 (PLUS_EXPR
, niter_type
, delta
, s
);
1103 niter
->niter
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, delta
, step
);
1107 mpz_set_double_int (mstep
, tree_to_double_int (step
), true);
1108 mpz_add (tmp
, bnds
->up
, mstep
);
1109 mpz_sub_ui (tmp
, tmp
, 1);
1110 mpz_fdiv_q (tmp
, tmp
, mstep
);
1111 niter
->max
= mpz_get_double_int (niter_type
, tmp
, false);
1118 /* Determines number of iterations of loop whose ending condition
1119 is IV0 <= IV1. TYPE is the type of the iv. The number of
1120 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
1121 we know that this condition must eventually become false (we derived this
1122 earlier, and possibly set NITER->assumptions to make sure this
1123 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1126 number_of_iterations_le (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1127 struct tree_niter_desc
*niter
, bool exit_must_be_taken
,
1132 if (POINTER_TYPE_P (type
))
1135 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1136 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1137 value of the type. This we must know anyway, since if it is
1138 equal to this value, the loop rolls forever. We do not check
1139 this condition for pointer type ivs, as the code cannot rely on
1140 the object to that the pointer points being placed at the end of
1141 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1142 not defined for pointers). */
1144 if (!exit_must_be_taken
&& !POINTER_TYPE_P (type
))
1146 if (integer_nonzerop (iv0
->step
))
1147 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1148 iv1
->base
, TYPE_MAX_VALUE (type
));
1150 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1151 iv0
->base
, TYPE_MIN_VALUE (type
));
1153 if (integer_zerop (assumption
))
1155 if (!integer_nonzerop (assumption
))
1156 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1157 niter
->assumptions
, assumption
);
1160 if (integer_nonzerop (iv0
->step
))
1162 if (POINTER_TYPE_P (type
))
1163 iv1
->base
= fold_build_pointer_plus_hwi (iv1
->base
, 1);
1165 iv1
->base
= fold_build2 (PLUS_EXPR
, type1
, iv1
->base
,
1166 build_int_cst (type1
, 1));
1168 else if (POINTER_TYPE_P (type
))
1169 iv0
->base
= fold_build_pointer_plus_hwi (iv0
->base
, -1);
1171 iv0
->base
= fold_build2 (MINUS_EXPR
, type1
,
1172 iv0
->base
, build_int_cst (type1
, 1));
1174 bounds_add (bnds
, double_int_one
, type1
);
1176 return number_of_iterations_lt (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1180 /* Dumps description of affine induction variable IV to FILE. */
1183 dump_affine_iv (FILE *file
, affine_iv
*iv
)
1185 if (!integer_zerop (iv
->step
))
1186 fprintf (file
, "[");
1188 print_generic_expr (dump_file
, iv
->base
, TDF_SLIM
);
1190 if (!integer_zerop (iv
->step
))
1192 fprintf (file
, ", + , ");
1193 print_generic_expr (dump_file
, iv
->step
, TDF_SLIM
);
1194 fprintf (file
, "]%s", iv
->no_overflow
? "(no_overflow)" : "");
1198 /* Determine the number of iterations according to condition (for staying
1199 inside loop) which compares two induction variables using comparison
1200 operator CODE. The induction variable on left side of the comparison
1201 is IV0, the right-hand side is IV1. Both induction variables must have
1202 type TYPE, which must be an integer or pointer type. The steps of the
1203 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1205 LOOP is the loop whose number of iterations we are determining.
1207 ONLY_EXIT is true if we are sure this is the only way the loop could be
1208 exited (including possibly non-returning function calls, exceptions, etc.)
1209 -- in this case we can use the information whether the control induction
1210 variables can overflow or not in a more efficient way.
1212 The results (number of iterations and assumptions as described in
1213 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
1214 Returns false if it fails to determine number of iterations, true if it
1215 was determined (possibly with some assumptions). */
1218 number_of_iterations_cond (struct loop
*loop
,
1219 tree type
, affine_iv
*iv0
, enum tree_code code
,
1220 affine_iv
*iv1
, struct tree_niter_desc
*niter
,
1223 bool exit_must_be_taken
= false, ret
;
1226 /* The meaning of these assumptions is this:
1228 then the rest of information does not have to be valid
1229 if may_be_zero then the loop does not roll, even if
1231 niter
->assumptions
= boolean_true_node
;
1232 niter
->may_be_zero
= boolean_false_node
;
1233 niter
->niter
= NULL_TREE
;
1234 niter
->max
= double_int_zero
;
1236 niter
->bound
= NULL_TREE
;
1237 niter
->cmp
= ERROR_MARK
;
1239 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1240 the control variable is on lhs. */
1241 if (code
== GE_EXPR
|| code
== GT_EXPR
1242 || (code
== NE_EXPR
&& integer_zerop (iv0
->step
)))
1245 code
= swap_tree_comparison (code
);
1248 if (POINTER_TYPE_P (type
))
1250 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1251 to the same object. If they do, the control variable cannot wrap
1252 (as wrap around the bounds of memory will never return a pointer
1253 that would be guaranteed to point to the same object, even if we
1254 avoid undefined behavior by casting to size_t and back). */
1255 iv0
->no_overflow
= true;
1256 iv1
->no_overflow
= true;
1259 /* If the control induction variable does not overflow and the only exit
1260 from the loop is the one that we analyze, we know it must be taken
1264 if (!integer_zerop (iv0
->step
) && iv0
->no_overflow
)
1265 exit_must_be_taken
= true;
1266 else if (!integer_zerop (iv1
->step
) && iv1
->no_overflow
)
1267 exit_must_be_taken
= true;
1270 /* We can handle the case when neither of the sides of the comparison is
1271 invariant, provided that the test is NE_EXPR. This rarely occurs in
1272 practice, but it is simple enough to manage. */
1273 if (!integer_zerop (iv0
->step
) && !integer_zerop (iv1
->step
))
1275 tree step_type
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1276 if (code
!= NE_EXPR
)
1279 iv0
->step
= fold_binary_to_constant (MINUS_EXPR
, step_type
,
1280 iv0
->step
, iv1
->step
);
1281 iv0
->no_overflow
= false;
1282 iv1
->step
= build_int_cst (step_type
, 0);
1283 iv1
->no_overflow
= true;
1286 /* If the result of the comparison is a constant, the loop is weird. More
1287 precise handling would be possible, but the situation is not common enough
1288 to waste time on it. */
1289 if (integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
))
1292 /* Ignore loops of while (i-- < 10) type. */
1293 if (code
!= NE_EXPR
)
1295 if (iv0
->step
&& tree_int_cst_sign_bit (iv0
->step
))
1298 if (!integer_zerop (iv1
->step
) && !tree_int_cst_sign_bit (iv1
->step
))
1302 /* If the loop exits immediately, there is nothing to do. */
1303 if (integer_zerop (fold_build2 (code
, boolean_type_node
, iv0
->base
, iv1
->base
)))
1305 niter
->niter
= build_int_cst (unsigned_type_for (type
), 0);
1306 niter
->max
= double_int_zero
;
1310 /* OK, now we know we have a senseful loop. Handle several cases, depending
1311 on what comparison operator is used. */
1312 bound_difference (loop
, iv1
->base
, iv0
->base
, &bnds
);
1314 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1317 "Analyzing # of iterations of loop %d\n", loop
->num
);
1319 fprintf (dump_file
, " exit condition ");
1320 dump_affine_iv (dump_file
, iv0
);
1321 fprintf (dump_file
, " %s ",
1322 code
== NE_EXPR
? "!="
1323 : code
== LT_EXPR
? "<"
1325 dump_affine_iv (dump_file
, iv1
);
1326 fprintf (dump_file
, "\n");
1328 fprintf (dump_file
, " bounds on difference of bases: ");
1329 mpz_out_str (dump_file
, 10, bnds
.below
);
1330 fprintf (dump_file
, " ... ");
1331 mpz_out_str (dump_file
, 10, bnds
.up
);
1332 fprintf (dump_file
, "\n");
1338 gcc_assert (integer_zerop (iv1
->step
));
1339 ret
= number_of_iterations_ne (type
, iv0
, iv1
->base
, niter
,
1340 exit_must_be_taken
, &bnds
);
1344 ret
= number_of_iterations_lt (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1349 ret
= number_of_iterations_le (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1357 mpz_clear (bnds
.up
);
1358 mpz_clear (bnds
.below
);
1360 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1364 fprintf (dump_file
, " result:\n");
1365 if (!integer_nonzerop (niter
->assumptions
))
1367 fprintf (dump_file
, " under assumptions ");
1368 print_generic_expr (dump_file
, niter
->assumptions
, TDF_SLIM
);
1369 fprintf (dump_file
, "\n");
1372 if (!integer_zerop (niter
->may_be_zero
))
1374 fprintf (dump_file
, " zero if ");
1375 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
1376 fprintf (dump_file
, "\n");
1379 fprintf (dump_file
, " # of iterations ");
1380 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
1381 fprintf (dump_file
, ", bounded by ");
1382 dump_double_int (dump_file
, niter
->max
, true);
1383 fprintf (dump_file
, "\n");
1386 fprintf (dump_file
, " failed\n\n");
1391 /* Substitute NEW for OLD in EXPR and fold the result. */
1394 simplify_replace_tree (tree expr
, tree old
, tree new_tree
)
1397 tree ret
= NULL_TREE
, e
, se
;
1402 /* Do not bother to replace constants. */
1403 if (CONSTANT_CLASS_P (old
))
1407 || operand_equal_p (expr
, old
, 0))
1408 return unshare_expr (new_tree
);
1413 n
= TREE_OPERAND_LENGTH (expr
);
1414 for (i
= 0; i
< n
; i
++)
1416 e
= TREE_OPERAND (expr
, i
);
1417 se
= simplify_replace_tree (e
, old
, new_tree
);
1422 ret
= copy_node (expr
);
1424 TREE_OPERAND (ret
, i
) = se
;
1427 return (ret
? fold (ret
) : expr
);
1430 /* Expand definitions of ssa names in EXPR as long as they are simple
1431 enough, and return the new expression. */
1434 expand_simple_operations (tree expr
)
1437 tree ret
= NULL_TREE
, e
, ee
, e1
;
1438 enum tree_code code
;
1441 if (expr
== NULL_TREE
)
1444 if (is_gimple_min_invariant (expr
))
1447 code
= TREE_CODE (expr
);
1448 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
1450 n
= TREE_OPERAND_LENGTH (expr
);
1451 for (i
= 0; i
< n
; i
++)
1453 e
= TREE_OPERAND (expr
, i
);
1454 ee
= expand_simple_operations (e
);
1459 ret
= copy_node (expr
);
1461 TREE_OPERAND (ret
, i
) = ee
;
1467 fold_defer_overflow_warnings ();
1469 fold_undefer_and_ignore_overflow_warnings ();
1473 if (TREE_CODE (expr
) != SSA_NAME
)
1476 stmt
= SSA_NAME_DEF_STMT (expr
);
1477 if (gimple_code (stmt
) == GIMPLE_PHI
)
1479 basic_block src
, dest
;
1481 if (gimple_phi_num_args (stmt
) != 1)
1483 e
= PHI_ARG_DEF (stmt
, 0);
1485 /* Avoid propagating through loop exit phi nodes, which
1486 could break loop-closed SSA form restrictions. */
1487 dest
= gimple_bb (stmt
);
1488 src
= single_pred (dest
);
1489 if (TREE_CODE (e
) == SSA_NAME
1490 && src
->loop_father
!= dest
->loop_father
)
1493 return expand_simple_operations (e
);
1495 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1498 e
= gimple_assign_rhs1 (stmt
);
1499 code
= gimple_assign_rhs_code (stmt
);
1500 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1502 if (is_gimple_min_invariant (e
))
1505 if (code
== SSA_NAME
)
1506 return expand_simple_operations (e
);
1514 /* Casts are simple. */
1515 ee
= expand_simple_operations (e
);
1516 return fold_build1 (code
, TREE_TYPE (expr
), ee
);
1520 case POINTER_PLUS_EXPR
:
1521 /* And increments and decrements by a constant are simple. */
1522 e1
= gimple_assign_rhs2 (stmt
);
1523 if (!is_gimple_min_invariant (e1
))
1526 ee
= expand_simple_operations (e
);
1527 return fold_build2 (code
, TREE_TYPE (expr
), ee
, e1
);
1534 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1535 expression (or EXPR unchanged, if no simplification was possible). */
1538 tree_simplify_using_condition_1 (tree cond
, tree expr
)
1541 tree e
, te
, e0
, e1
, e2
, notcond
;
1542 enum tree_code code
= TREE_CODE (expr
);
1544 if (code
== INTEGER_CST
)
1547 if (code
== TRUTH_OR_EXPR
1548 || code
== TRUTH_AND_EXPR
1549 || code
== COND_EXPR
)
1553 e0
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 0));
1554 if (TREE_OPERAND (expr
, 0) != e0
)
1557 e1
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 1));
1558 if (TREE_OPERAND (expr
, 1) != e1
)
1561 if (code
== COND_EXPR
)
1563 e2
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 2));
1564 if (TREE_OPERAND (expr
, 2) != e2
)
1572 if (code
== COND_EXPR
)
1573 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1575 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1581 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
1582 propagation, and vice versa. Fold does not handle this, since it is
1583 considered too expensive. */
1584 if (TREE_CODE (cond
) == EQ_EXPR
)
1586 e0
= TREE_OPERAND (cond
, 0);
1587 e1
= TREE_OPERAND (cond
, 1);
1589 /* We know that e0 == e1. Check whether we cannot simplify expr
1591 e
= simplify_replace_tree (expr
, e0
, e1
);
1592 if (integer_zerop (e
) || integer_nonzerop (e
))
1595 e
= simplify_replace_tree (expr
, e1
, e0
);
1596 if (integer_zerop (e
) || integer_nonzerop (e
))
1599 if (TREE_CODE (expr
) == EQ_EXPR
)
1601 e0
= TREE_OPERAND (expr
, 0);
1602 e1
= TREE_OPERAND (expr
, 1);
1604 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
1605 e
= simplify_replace_tree (cond
, e0
, e1
);
1606 if (integer_zerop (e
))
1608 e
= simplify_replace_tree (cond
, e1
, e0
);
1609 if (integer_zerop (e
))
1612 if (TREE_CODE (expr
) == NE_EXPR
)
1614 e0
= TREE_OPERAND (expr
, 0);
1615 e1
= TREE_OPERAND (expr
, 1);
1617 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
1618 e
= simplify_replace_tree (cond
, e0
, e1
);
1619 if (integer_zerop (e
))
1620 return boolean_true_node
;
1621 e
= simplify_replace_tree (cond
, e1
, e0
);
1622 if (integer_zerop (e
))
1623 return boolean_true_node
;
1626 te
= expand_simple_operations (expr
);
1628 /* Check whether COND ==> EXPR. */
1629 notcond
= invert_truthvalue (cond
);
1630 e
= fold_binary (TRUTH_OR_EXPR
, boolean_type_node
, notcond
, te
);
1631 if (e
&& integer_nonzerop (e
))
1634 /* Check whether COND ==> not EXPR. */
1635 e
= fold_binary (TRUTH_AND_EXPR
, boolean_type_node
, cond
, te
);
1636 if (e
&& integer_zerop (e
))
1642 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1643 expression (or EXPR unchanged, if no simplification was possible).
1644 Wrapper around tree_simplify_using_condition_1 that ensures that chains
1645 of simple operations in definitions of ssa names in COND are expanded,
1646 so that things like casts or incrementing the value of the bound before
1647 the loop do not cause us to fail. */
1650 tree_simplify_using_condition (tree cond
, tree expr
)
1652 cond
= expand_simple_operations (cond
);
1654 return tree_simplify_using_condition_1 (cond
, expr
);
1657 /* Tries to simplify EXPR using the conditions on entry to LOOP.
1658 Returns the simplified expression (or EXPR unchanged, if no
1659 simplification was possible).*/
1662 simplify_using_initial_conditions (struct loop
*loop
, tree expr
)
1670 if (TREE_CODE (expr
) == INTEGER_CST
)
1673 /* Limit walking the dominators to avoid quadraticness in
1674 the number of BBs times the number of loops in degenerate
1676 for (bb
= loop
->header
;
1677 bb
!= ENTRY_BLOCK_PTR
&& cnt
< MAX_DOMINATORS_TO_WALK
;
1678 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1680 if (!single_pred_p (bb
))
1682 e
= single_pred_edge (bb
);
1684 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
1687 stmt
= last_stmt (e
->src
);
1688 cond
= fold_build2 (gimple_cond_code (stmt
),
1690 gimple_cond_lhs (stmt
),
1691 gimple_cond_rhs (stmt
));
1692 if (e
->flags
& EDGE_FALSE_VALUE
)
1693 cond
= invert_truthvalue (cond
);
1694 expr
= tree_simplify_using_condition (cond
, expr
);
1701 /* Tries to simplify EXPR using the evolutions of the loop invariants
1702 in the superloops of LOOP. Returns the simplified expression
1703 (or EXPR unchanged, if no simplification was possible). */
1706 simplify_using_outer_evolutions (struct loop
*loop
, tree expr
)
1708 enum tree_code code
= TREE_CODE (expr
);
1712 if (is_gimple_min_invariant (expr
))
1715 if (code
== TRUTH_OR_EXPR
1716 || code
== TRUTH_AND_EXPR
1717 || code
== COND_EXPR
)
1721 e0
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 0));
1722 if (TREE_OPERAND (expr
, 0) != e0
)
1725 e1
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 1));
1726 if (TREE_OPERAND (expr
, 1) != e1
)
1729 if (code
== COND_EXPR
)
1731 e2
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 2));
1732 if (TREE_OPERAND (expr
, 2) != e2
)
1740 if (code
== COND_EXPR
)
1741 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1743 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1749 e
= instantiate_parameters (loop
, expr
);
1750 if (is_gimple_min_invariant (e
))
1756 /* Returns true if EXIT is the only possible exit from LOOP. */
1759 loop_only_exit_p (const struct loop
*loop
, const_edge exit
)
1762 gimple_stmt_iterator bsi
;
1766 if (exit
!= single_exit (loop
))
1769 body
= get_loop_body (loop
);
1770 for (i
= 0; i
< loop
->num_nodes
; i
++)
1772 for (bsi
= gsi_start_bb (body
[i
]); !gsi_end_p (bsi
); gsi_next (&bsi
))
1774 call
= gsi_stmt (bsi
);
1775 if (gimple_code (call
) != GIMPLE_CALL
)
1778 if (gimple_has_side_effects (call
))
1790 /* Stores description of number of iterations of LOOP derived from
1791 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
1792 useful information could be derived (and fields of NITER has
1793 meaning described in comments at struct tree_niter_desc
1794 declaration), false otherwise. If WARN is true and
1795 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1796 potentially unsafe assumptions.
1797 When EVERY_ITERATION is true, only tests that are known to be executed
1798 every iteration are considered (i.e. only test that alone bounds the loop).
1802 number_of_iterations_exit (struct loop
*loop
, edge exit
,
1803 struct tree_niter_desc
*niter
,
1804 bool warn
, bool every_iteration
)
1809 enum tree_code code
;
1813 && !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit
->src
))
1816 niter
->assumptions
= boolean_false_node
;
1817 stmt
= last_stmt (exit
->src
);
1818 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1821 /* We want the condition for staying inside loop. */
1822 code
= gimple_cond_code (stmt
);
1823 if (exit
->flags
& EDGE_TRUE_VALUE
)
1824 code
= invert_tree_comparison (code
, false);
1839 op0
= gimple_cond_lhs (stmt
);
1840 op1
= gimple_cond_rhs (stmt
);
1841 type
= TREE_TYPE (op0
);
1843 if (TREE_CODE (type
) != INTEGER_TYPE
1844 && !POINTER_TYPE_P (type
))
1847 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, false))
1849 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, false))
1852 /* We don't want to see undefined signed overflow warnings while
1853 computing the number of iterations. */
1854 fold_defer_overflow_warnings ();
1856 iv0
.base
= expand_simple_operations (iv0
.base
);
1857 iv1
.base
= expand_simple_operations (iv1
.base
);
1858 if (!number_of_iterations_cond (loop
, type
, &iv0
, code
, &iv1
, niter
,
1859 loop_only_exit_p (loop
, exit
)))
1861 fold_undefer_and_ignore_overflow_warnings ();
1867 niter
->assumptions
= simplify_using_outer_evolutions (loop
,
1868 niter
->assumptions
);
1869 niter
->may_be_zero
= simplify_using_outer_evolutions (loop
,
1870 niter
->may_be_zero
);
1871 niter
->niter
= simplify_using_outer_evolutions (loop
, niter
->niter
);
1875 = simplify_using_initial_conditions (loop
,
1876 niter
->assumptions
);
1878 = simplify_using_initial_conditions (loop
,
1879 niter
->may_be_zero
);
1881 fold_undefer_and_ignore_overflow_warnings ();
1883 /* If NITER has simplified into a constant, update MAX. */
1884 if (TREE_CODE (niter
->niter
) == INTEGER_CST
)
1885 niter
->max
= tree_to_double_int (niter
->niter
);
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)
2298 VEC_free (edge
, heap
, exits
);
2299 return chrec_dont_know
;
2302 FOR_EACH_VEC_ELT (edge
, exits
, i
, ex
)
2304 if (!just_once_each_iteration_p (loop
, ex
->src
))
2307 aniter
= loop_niter_by_eval (loop
, ex
);
2308 if (chrec_contains_undetermined (aniter
))
2312 && !tree_int_cst_lt (aniter
, niter
))
2318 VEC_free (edge
, heap
, exits
);
2320 return niter
? niter
: chrec_dont_know
;
2325 Analysis of upper bounds on number of iterations of a loop.
2329 static double_int
derive_constant_upper_bound_ops (tree
, tree
,
2330 enum tree_code
, tree
);
2332 /* Returns a constant upper bound on the value of the right-hand side of
2333 an assignment statement STMT. */
2336 derive_constant_upper_bound_assign (gimple stmt
)
2338 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2339 tree op0
= gimple_assign_rhs1 (stmt
);
2340 tree op1
= gimple_assign_rhs2 (stmt
);
2342 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt
)),
2346 /* Returns a constant upper bound on the value of expression VAL. VAL
2347 is considered to be unsigned. If its type is signed, its value must
2351 derive_constant_upper_bound (tree val
)
2353 enum tree_code code
;
2356 extract_ops_from_tree (val
, &code
, &op0
, &op1
);
2357 return derive_constant_upper_bound_ops (TREE_TYPE (val
), op0
, code
, op1
);
2360 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
2361 whose type is TYPE. The expression is considered to be unsigned. If
2362 its type is signed, its value must be nonnegative. */
2365 derive_constant_upper_bound_ops (tree type
, tree op0
,
2366 enum tree_code code
, tree op1
)
2369 double_int bnd
, max
, mmax
, cst
;
2372 if (INTEGRAL_TYPE_P (type
))
2373 maxt
= TYPE_MAX_VALUE (type
);
2375 maxt
= upper_bound_in_type (type
, type
);
2377 max
= tree_to_double_int (maxt
);
2382 return tree_to_double_int (op0
);
2385 subtype
= TREE_TYPE (op0
);
2386 if (!TYPE_UNSIGNED (subtype
)
2387 /* If TYPE is also signed, the fact that VAL is nonnegative implies
2388 that OP0 is nonnegative. */
2389 && TYPE_UNSIGNED (type
)
2390 && !tree_expr_nonnegative_p (op0
))
2392 /* If we cannot prove that the casted expression is nonnegative,
2393 we cannot establish more useful upper bound than the precision
2394 of the type gives us. */
2398 /* We now know that op0 is an nonnegative value. Try deriving an upper
2400 bnd
= derive_constant_upper_bound (op0
);
2402 /* If the bound does not fit in TYPE, max. value of TYPE could be
2410 case POINTER_PLUS_EXPR
:
2412 if (TREE_CODE (op1
) != INTEGER_CST
2413 || !tree_expr_nonnegative_p (op0
))
2416 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
2417 choose the most logical way how to treat this constant regardless
2418 of the signedness of the type. */
2419 cst
= tree_to_double_int (op1
);
2420 cst
= cst
.sext (TYPE_PRECISION (type
));
2421 if (code
!= MINUS_EXPR
)
2424 bnd
= derive_constant_upper_bound (op0
);
2426 if (cst
.is_negative ())
2429 /* Avoid CST == 0x80000... */
2430 if (cst
.is_negative ())
2433 /* OP0 + CST. We need to check that
2434 BND <= MAX (type) - CST. */
2444 /* OP0 - CST, where CST >= 0.
2446 If TYPE is signed, we have already verified that OP0 >= 0, and we
2447 know that the result is nonnegative. This implies that
2450 If TYPE is unsigned, we must additionally know that OP0 >= CST,
2451 otherwise the operation underflows.
2454 /* This should only happen if the type is unsigned; however, for
2455 buggy programs that use overflowing signed arithmetics even with
2456 -fno-wrapv, this condition may also be true for signed values. */
2460 if (TYPE_UNSIGNED (type
))
2462 tree tem
= fold_binary (GE_EXPR
, boolean_type_node
, op0
,
2463 double_int_to_tree (type
, cst
));
2464 if (!tem
|| integer_nonzerop (tem
))
2473 case FLOOR_DIV_EXPR
:
2474 case EXACT_DIV_EXPR
:
2475 if (TREE_CODE (op1
) != INTEGER_CST
2476 || tree_int_cst_sign_bit (op1
))
2479 bnd
= derive_constant_upper_bound (op0
);
2480 return bnd
.udiv (tree_to_double_int (op1
), FLOOR_DIV_EXPR
);
2483 if (TREE_CODE (op1
) != INTEGER_CST
2484 || tree_int_cst_sign_bit (op1
))
2486 return tree_to_double_int (op1
);
2489 stmt
= SSA_NAME_DEF_STMT (op0
);
2490 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2491 || gimple_assign_lhs (stmt
) != op0
)
2493 return derive_constant_upper_bound_assign (stmt
);
2500 /* Records that every statement in LOOP is executed I_BOUND times.
2501 REALISTIC is true if I_BOUND is expected to be close to the real number
2502 of iterations. UPPER is true if we are sure the loop iterates at most
2506 record_niter_bound (struct loop
*loop
, double_int i_bound
, bool realistic
,
2509 /* Update the bounds only when there is no previous estimation, or when the
2510 current estimation is smaller. */
2512 && (!loop
->any_upper_bound
2513 || i_bound
.ult (loop
->nb_iterations_upper_bound
)))
2515 loop
->any_upper_bound
= true;
2516 loop
->nb_iterations_upper_bound
= i_bound
;
2519 && (!loop
->any_estimate
2520 || i_bound
.ult (loop
->nb_iterations_estimate
)))
2522 loop
->any_estimate
= true;
2523 loop
->nb_iterations_estimate
= i_bound
;
2526 /* If an upper bound is smaller than the realistic estimate of the
2527 number of iterations, use the upper bound instead. */
2528 if (loop
->any_upper_bound
2529 && loop
->any_estimate
2530 && loop
->nb_iterations_upper_bound
.ult (loop
->nb_iterations_estimate
))
2531 loop
->nb_iterations_estimate
= loop
->nb_iterations_upper_bound
;
2534 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
2535 is true if the loop is exited immediately after STMT, and this exit
2536 is taken at last when the STMT is executed BOUND + 1 times.
2537 REALISTIC is true if BOUND is expected to be close to the real number
2538 of iterations. UPPER is true if we are sure the loop iterates at most
2539 BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */
2542 record_estimate (struct loop
*loop
, tree bound
, double_int i_bound
,
2543 gimple at_stmt
, bool is_exit
, bool realistic
, bool upper
)
2547 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2549 fprintf (dump_file
, "Statement %s", is_exit
? "(exit)" : "");
2550 print_gimple_stmt (dump_file
, at_stmt
, 0, TDF_SLIM
);
2551 fprintf (dump_file
, " is %sexecuted at most ",
2552 upper
? "" : "probably ");
2553 print_generic_expr (dump_file
, bound
, TDF_SLIM
);
2554 fprintf (dump_file
, " (bounded by ");
2555 dump_double_int (dump_file
, i_bound
, true);
2556 fprintf (dump_file
, ") + 1 times in loop %d.\n", loop
->num
);
2559 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
2560 real number of iterations. */
2561 if (TREE_CODE (bound
) != INTEGER_CST
)
2564 gcc_checking_assert (i_bound
== tree_to_double_int (bound
));
2565 if (!upper
&& !realistic
)
2568 /* If we have a guaranteed upper bound, record it in the appropriate
2572 struct nb_iter_bound
*elt
= ggc_alloc_nb_iter_bound ();
2574 elt
->bound
= i_bound
;
2575 elt
->stmt
= at_stmt
;
2576 elt
->is_exit
= is_exit
;
2577 elt
->next
= loop
->bounds
;
2581 /* If statement is executed on every path to the loop latch, we can directly
2582 infer the upper bound on the # of iterations of the loop. */
2583 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (at_stmt
)))
2586 /* Update the number of iteration estimates according to the bound.
2587 If at_stmt is an exit then the loop latch is executed at most BOUND times,
2588 otherwise it can be executed BOUND + 1 times. We will lower the estimate
2589 later if such statement must be executed on last iteration */
2591 delta
= double_int_zero
;
2593 delta
= double_int_one
;
2596 /* If an overflow occurred, ignore the result. */
2597 if (i_bound
.ult (delta
))
2600 record_niter_bound (loop
, i_bound
, realistic
, upper
);
2603 /* Record the estimate on number of iterations of LOOP based on the fact that
2604 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
2605 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
2606 estimated number of iterations is expected to be close to the real one.
2607 UPPER is true if we are sure the induction variable does not wrap. */
2610 record_nonwrapping_iv (struct loop
*loop
, tree base
, tree step
, gimple stmt
,
2611 tree low
, tree high
, bool realistic
, bool upper
)
2613 tree niter_bound
, extreme
, delta
;
2614 tree type
= TREE_TYPE (base
), unsigned_type
;
2617 if (TREE_CODE (step
) != INTEGER_CST
|| integer_zerop (step
))
2620 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2622 fprintf (dump_file
, "Induction variable (");
2623 print_generic_expr (dump_file
, TREE_TYPE (base
), TDF_SLIM
);
2624 fprintf (dump_file
, ") ");
2625 print_generic_expr (dump_file
, base
, TDF_SLIM
);
2626 fprintf (dump_file
, " + ");
2627 print_generic_expr (dump_file
, step
, TDF_SLIM
);
2628 fprintf (dump_file
, " * iteration does not wrap in statement ");
2629 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2630 fprintf (dump_file
, " in loop %d.\n", loop
->num
);
2633 unsigned_type
= unsigned_type_for (type
);
2634 base
= fold_convert (unsigned_type
, base
);
2635 step
= fold_convert (unsigned_type
, step
);
2637 if (tree_int_cst_sign_bit (step
))
2639 extreme
= fold_convert (unsigned_type
, low
);
2640 if (TREE_CODE (base
) != INTEGER_CST
)
2641 base
= fold_convert (unsigned_type
, high
);
2642 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
2643 step
= fold_build1 (NEGATE_EXPR
, unsigned_type
, step
);
2647 extreme
= fold_convert (unsigned_type
, high
);
2648 if (TREE_CODE (base
) != INTEGER_CST
)
2649 base
= fold_convert (unsigned_type
, low
);
2650 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
2653 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
2654 would get out of the range. */
2655 niter_bound
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step
);
2656 max
= derive_constant_upper_bound (niter_bound
);
2657 record_estimate (loop
, niter_bound
, max
, stmt
, false, realistic
, upper
);
2660 /* Determine information about number of iterations a LOOP from the index
2661 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
2662 guaranteed to be executed in every iteration of LOOP. Callback for
2672 idx_infer_loop_bounds (tree base
, tree
*idx
, void *dta
)
2674 struct ilb_data
*data
= (struct ilb_data
*) dta
;
2675 tree ev
, init
, step
;
2676 tree low
, high
, type
, next
;
2677 bool sign
, upper
= true, at_end
= false;
2678 struct loop
*loop
= data
->loop
;
2680 if (TREE_CODE (base
) != ARRAY_REF
)
2683 /* For arrays at the end of the structure, we are not guaranteed that they
2684 do not really extend over their declared size. However, for arrays of
2685 size greater than one, this is unlikely to be intended. */
2686 if (array_at_struct_end_p (base
))
2692 ev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, *idx
));
2693 init
= initial_condition (ev
);
2694 step
= evolution_part_in_loop_num (ev
, loop
->num
);
2698 || TREE_CODE (step
) != INTEGER_CST
2699 || integer_zerop (step
)
2700 || tree_contains_chrecs (init
, NULL
)
2701 || chrec_contains_symbols_defined_in_loop (init
, loop
->num
))
2704 low
= array_ref_low_bound (base
);
2705 high
= array_ref_up_bound (base
);
2707 /* The case of nonconstant bounds could be handled, but it would be
2709 if (TREE_CODE (low
) != INTEGER_CST
2711 || TREE_CODE (high
) != INTEGER_CST
)
2713 sign
= tree_int_cst_sign_bit (step
);
2714 type
= TREE_TYPE (step
);
2716 /* The array of length 1 at the end of a structure most likely extends
2717 beyond its bounds. */
2719 && operand_equal_p (low
, high
, 0))
2722 /* In case the relevant bound of the array does not fit in type, or
2723 it does, but bound + step (in type) still belongs into the range of the
2724 array, the index may wrap and still stay within the range of the array
2725 (consider e.g. if the array is indexed by the full range of
2728 To make things simpler, we require both bounds to fit into type, although
2729 there are cases where this would not be strictly necessary. */
2730 if (!int_fits_type_p (high
, type
)
2731 || !int_fits_type_p (low
, type
))
2733 low
= fold_convert (type
, low
);
2734 high
= fold_convert (type
, high
);
2737 next
= fold_binary (PLUS_EXPR
, type
, low
, step
);
2739 next
= fold_binary (PLUS_EXPR
, type
, high
, step
);
2741 if (tree_int_cst_compare (low
, next
) <= 0
2742 && tree_int_cst_compare (next
, high
) <= 0)
2745 record_nonwrapping_iv (loop
, init
, step
, data
->stmt
, low
, high
, true, upper
);
2749 /* Determine information about number of iterations a LOOP from the bounds
2750 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
2751 STMT is guaranteed to be executed in every iteration of LOOP.*/
2754 infer_loop_bounds_from_ref (struct loop
*loop
, gimple stmt
, tree ref
)
2756 struct ilb_data data
;
2760 for_each_index (&ref
, idx_infer_loop_bounds
, &data
);
2763 /* Determine information about number of iterations of a LOOP from the way
2764 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
2765 executed in every iteration of LOOP. */
2768 infer_loop_bounds_from_array (struct loop
*loop
, gimple stmt
)
2770 if (is_gimple_assign (stmt
))
2772 tree op0
= gimple_assign_lhs (stmt
);
2773 tree op1
= gimple_assign_rhs1 (stmt
);
2775 /* For each memory access, analyze its access function
2776 and record a bound on the loop iteration domain. */
2777 if (REFERENCE_CLASS_P (op0
))
2778 infer_loop_bounds_from_ref (loop
, stmt
, op0
);
2780 if (REFERENCE_CLASS_P (op1
))
2781 infer_loop_bounds_from_ref (loop
, stmt
, op1
);
2783 else if (is_gimple_call (stmt
))
2786 unsigned i
, n
= gimple_call_num_args (stmt
);
2788 lhs
= gimple_call_lhs (stmt
);
2789 if (lhs
&& REFERENCE_CLASS_P (lhs
))
2790 infer_loop_bounds_from_ref (loop
, stmt
, lhs
);
2792 for (i
= 0; i
< n
; i
++)
2794 arg
= gimple_call_arg (stmt
, i
);
2795 if (REFERENCE_CLASS_P (arg
))
2796 infer_loop_bounds_from_ref (loop
, stmt
, arg
);
2801 /* Determine information about number of iterations of a LOOP from the fact
2802 that pointer arithmetics in STMT does not overflow. */
2805 infer_loop_bounds_from_pointer_arith (struct loop
*loop
, gimple stmt
)
2807 tree def
, base
, step
, scev
, type
, low
, high
;
2810 if (!is_gimple_assign (stmt
)
2811 || gimple_assign_rhs_code (stmt
) != POINTER_PLUS_EXPR
)
2814 def
= gimple_assign_lhs (stmt
);
2815 if (TREE_CODE (def
) != SSA_NAME
)
2818 type
= TREE_TYPE (def
);
2819 if (!nowrap_type_p (type
))
2822 ptr
= gimple_assign_rhs1 (stmt
);
2823 if (!expr_invariant_in_loop_p (loop
, ptr
))
2826 var
= gimple_assign_rhs2 (stmt
);
2827 if (TYPE_PRECISION (type
) != TYPE_PRECISION (TREE_TYPE (var
)))
2830 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
2831 if (chrec_contains_undetermined (scev
))
2834 base
= initial_condition_in_loop_num (scev
, loop
->num
);
2835 step
= evolution_part_in_loop_num (scev
, loop
->num
);
2838 || TREE_CODE (step
) != INTEGER_CST
2839 || tree_contains_chrecs (base
, NULL
)
2840 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
2843 low
= lower_bound_in_type (type
, type
);
2844 high
= upper_bound_in_type (type
, type
);
2846 /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
2847 produce a NULL pointer. The contrary would mean NULL points to an object,
2848 while NULL is supposed to compare unequal with the address of all objects.
2849 Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
2850 NULL pointer since that would mean wrapping, which we assume here not to
2851 happen. So, we can exclude NULL from the valid range of pointer
2853 if (flag_delete_null_pointer_checks
&& int_cst_value (low
) == 0)
2854 low
= build_int_cstu (TREE_TYPE (low
), TYPE_ALIGN_UNIT (TREE_TYPE (type
)));
2856 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
2859 /* Determine information about number of iterations of a LOOP from the fact
2860 that signed arithmetics in STMT does not overflow. */
2863 infer_loop_bounds_from_signedness (struct loop
*loop
, gimple stmt
)
2865 tree def
, base
, step
, scev
, type
, low
, high
;
2867 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2870 def
= gimple_assign_lhs (stmt
);
2872 if (TREE_CODE (def
) != SSA_NAME
)
2875 type
= TREE_TYPE (def
);
2876 if (!INTEGRAL_TYPE_P (type
)
2877 || !TYPE_OVERFLOW_UNDEFINED (type
))
2880 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
2881 if (chrec_contains_undetermined (scev
))
2884 base
= initial_condition_in_loop_num (scev
, loop
->num
);
2885 step
= evolution_part_in_loop_num (scev
, loop
->num
);
2888 || TREE_CODE (step
) != INTEGER_CST
2889 || tree_contains_chrecs (base
, NULL
)
2890 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
2893 low
= lower_bound_in_type (type
, type
);
2894 high
= upper_bound_in_type (type
, type
);
2896 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
2899 /* The following analyzers are extracting informations on the bounds
2900 of LOOP from the following undefined behaviors:
2902 - data references should not access elements over the statically
2905 - signed variables should not overflow when flag_wrapv is not set.
2909 infer_loop_bounds_from_undefined (struct loop
*loop
)
2913 gimple_stmt_iterator bsi
;
2917 bbs
= get_loop_body (loop
);
2919 for (i
= 0; i
< loop
->num_nodes
; i
++)
2923 /* If BB is not executed in each iteration of the loop, we cannot
2924 use the operations in it to infer reliable upper bound on the
2925 # of iterations of the loop. However, we can use it as a guess.
2926 Reliable guesses come only from array bounds. */
2927 reliable
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
);
2929 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2931 gimple stmt
= gsi_stmt (bsi
);
2933 infer_loop_bounds_from_array (loop
, stmt
);
2937 infer_loop_bounds_from_signedness (loop
, stmt
);
2938 infer_loop_bounds_from_pointer_arith (loop
, stmt
);
2947 /* Converts VAL to double_int. */
2950 gcov_type_to_double_int (gcov_type val
)
2954 ret
.low
= (unsigned HOST_WIDE_INT
) val
;
2955 /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by
2956 the size of type. */
2957 val
>>= HOST_BITS_PER_WIDE_INT
- 1;
2959 ret
.high
= (unsigned HOST_WIDE_INT
) val
;
2964 /* Compare double ints, callback for qsort. */
2967 double_int_cmp (const void *p1
, const void *p2
)
2969 const double_int
*d1
= (const double_int
*)p1
;
2970 const double_int
*d2
= (const double_int
*)p2
;
2978 /* Return index of BOUND in BOUNDS array sorted in increasing order.
2979 Lookup by binary search. */
2982 bound_index (VEC (double_int
, heap
) *bounds
, double_int bound
)
2984 unsigned int end
= VEC_length (double_int
, bounds
);
2985 unsigned int begin
= 0;
2987 /* Find a matching index by means of a binary search. */
2988 while (begin
!= end
)
2990 unsigned int middle
= (begin
+ end
) / 2;
2991 double_int index
= VEC_index (double_int
, bounds
, middle
);
2995 else if (index
.ult (bound
))
3003 /* Used to hold vector of queues of basic blocks bellow. */
3004 typedef VEC (basic_block
, heap
) *bb_queue
;
3005 DEF_VEC_P(bb_queue
);
3006 DEF_VEC_ALLOC_P(bb_queue
,heap
);
3008 /* We recorded loop bounds only for statements dominating loop latch (and thus
3009 executed each loop iteration). If there are any bounds on statements not
3010 dominating the loop latch we can improve the estimate by walking the loop
3011 body and seeing if every path from loop header to loop latch contains
3012 some bounded statement. */
3015 discover_iteration_bound_by_body_walk (struct loop
*loop
)
3017 pointer_map_t
*bb_bounds
;
3018 struct nb_iter_bound
*elt
;
3019 VEC (double_int
, heap
) *bounds
= NULL
;
3020 VEC (bb_queue
, heap
) *queues
= NULL
;
3021 bb_queue queue
= NULL
;
3022 ptrdiff_t queue_index
;
3023 ptrdiff_t latch_index
= 0;
3024 pointer_map_t
*block_priority
;
3026 /* Discover what bounds may interest us. */
3027 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3029 double_int bound
= elt
->bound
;
3031 /* Exit terminates loop at given iteration, while non-exits produce undefined
3032 effect on the next iteration. */
3034 bound
+= double_int_one
;
3036 if (!loop
->any_upper_bound
3037 || bound
.ult (loop
->nb_iterations_upper_bound
))
3038 VEC_safe_push (double_int
, heap
, bounds
, bound
);
3041 /* Exit early if there is nothing to do. */
3045 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3046 fprintf (dump_file
, " Trying to walk loop body to reduce the bound.\n");
3048 /* Sort the bounds in decreasing order. */
3049 qsort (VEC_address (double_int
, bounds
), VEC_length (double_int
, bounds
),
3050 sizeof (double_int
), double_int_cmp
);
3052 /* For every basic block record the lowest bound that is guaranteed to
3053 terminate the loop. */
3055 bb_bounds
= pointer_map_create ();
3056 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3058 double_int bound
= elt
->bound
;
3060 bound
+= double_int_one
;
3062 if (!loop
->any_upper_bound
3063 || bound
.ult (loop
->nb_iterations_upper_bound
))
3065 ptrdiff_t index
= bound_index (bounds
, bound
);
3066 void **entry
= pointer_map_contains (bb_bounds
,
3067 gimple_bb (elt
->stmt
));
3069 *pointer_map_insert (bb_bounds
,
3070 gimple_bb (elt
->stmt
)) = (void *)index
;
3071 else if ((ptrdiff_t)*entry
> index
)
3072 *entry
= (void *)index
;
3076 block_priority
= pointer_map_create ();
3078 /* Perform shortest path discovery loop->header ... loop->latch.
3080 The "distance" is given by the smallest loop bound of basic block
3081 present in the path and we look for path with largest smallest bound
3084 To avoid the need for fibonaci heap on double ints we simply compress
3085 double ints into indexes to BOUNDS array and then represent the queue
3086 as arrays of queues for every index.
3087 Index of VEC_length (BOUNDS) means that the execution of given BB has
3088 no bounds determined.
3090 VISITED is a pointer map translating basic block into smallest index
3091 it was inserted into the priority queue with. */
3094 /* Start walk in loop header with index set to infinite bound. */
3095 queue_index
= VEC_length (double_int
, bounds
);
3096 VEC_safe_grow_cleared (bb_queue
, heap
, queues
, queue_index
+ 1);
3097 VEC_safe_push (basic_block
, heap
, queue
, loop
->header
);
3098 VEC_replace (bb_queue
, queues
, queue_index
, queue
);
3099 *pointer_map_insert (block_priority
, loop
->header
) = (void *)queue_index
;
3101 for (; queue_index
>= 0; queue_index
--)
3103 if (latch_index
< queue_index
)
3105 while (VEC_length (basic_block
,
3106 VEC_index (bb_queue
, queues
, queue_index
)))
3109 ptrdiff_t bound_index
= queue_index
;
3114 queue
= VEC_index (bb_queue
, queues
, queue_index
);
3115 bb
= VEC_pop (basic_block
, queue
);
3117 /* OK, we later inserted the BB with lower priority, skip it. */
3118 if ((ptrdiff_t)*pointer_map_contains (block_priority
, bb
) > queue_index
)
3121 /* See if we can improve the bound. */
3122 entry
= pointer_map_contains (bb_bounds
, bb
);
3123 if (entry
&& (ptrdiff_t)*entry
< bound_index
)
3124 bound_index
= (ptrdiff_t)*entry
;
3126 /* Insert succesors into the queue, watch for latch edge
3127 and record greatest index we saw. */
3128 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3130 bool insert
= false;
3133 if (loop_exit_edge_p (loop
, e
))
3136 if (e
== loop_latch_edge (loop
)
3137 && latch_index
< bound_index
)
3138 latch_index
= bound_index
;
3139 else if (!(entry
= pointer_map_contains (block_priority
, e
->dest
)))
3142 *pointer_map_insert (block_priority
, e
->dest
) = (void *)bound_index
;
3144 else if ((ptrdiff_t)*entry
< bound_index
)
3147 *entry
= (void *)bound_index
;
3152 bb_queue queue2
= VEC_index (bb_queue
, queues
, bound_index
);
3153 VEC_safe_push (basic_block
, heap
, queue2
, e
->dest
);
3154 VEC_replace (bb_queue
, queues
, bound_index
, queue2
);
3160 VEC_free (basic_block
, heap
, VEC_index (bb_queue
, queues
, queue_index
));
3163 gcc_assert (latch_index
>= 0);
3164 if ((unsigned)latch_index
< VEC_length (double_int
, bounds
))
3166 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3168 fprintf (dump_file
, "Found better loop bound ");
3169 dump_double_int (dump_file
,
3170 VEC_index (double_int
, bounds
, latch_index
), true);
3171 fprintf (dump_file
, "\n");
3173 record_niter_bound (loop
, VEC_index (double_int
, bounds
, latch_index
),
3177 VEC_free (bb_queue
, heap
, queues
);
3178 pointer_map_destroy (bb_bounds
);
3179 pointer_map_destroy (block_priority
);
3182 /* See if every path cross the loop goes through a statement that is known
3183 to not execute at the last iteration. In that case we can decrese iteration
3187 maybe_lower_iteration_bound (struct loop
*loop
)
3189 pointer_set_t
*not_executed_last_iteration
= pointer_set_create ();
3190 struct nb_iter_bound
*elt
;
3191 bool found_exit
= false;
3192 VEC (basic_block
, heap
) *queue
= NULL
;
3195 /* Collect all statements with interesting (i.e. lower than
3196 nb_iterations_upper_bound) bound on them.
3198 TODO: Due to the way record_estimate choose estimates to store, the bounds
3199 will be always nb_iterations_upper_bound-1. We can change this to record
3200 also statements not dominating the loop latch and update the walk bellow
3201 to the shortest path algorthm. */
3202 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3205 && elt
->bound
.ult (loop
->nb_iterations_upper_bound
))
3207 if (!not_executed_last_iteration
)
3208 not_executed_last_iteration
= pointer_set_create ();
3209 pointer_set_insert (not_executed_last_iteration
, elt
->stmt
);
3212 if (!not_executed_last_iteration
)
3215 /* Start DFS walk in the loop header and see if we can reach the
3216 loop latch or any of the exits (including statements with side
3217 effects that may terminate the loop otherwise) without visiting
3218 any of the statements known to have undefined effect on the last
3220 VEC_safe_push (basic_block
, heap
, queue
, loop
->header
);
3221 visited
= BITMAP_ALLOC (NULL
);
3222 bitmap_set_bit (visited
, loop
->header
->index
);
3227 basic_block bb
= VEC_pop (basic_block
, queue
);
3228 gimple_stmt_iterator gsi
;
3229 bool stmt_found
= false;
3231 /* Loop for possible exits and statements bounding the execution. */
3232 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3234 gimple stmt
= gsi_stmt (gsi
);
3235 if (pointer_set_contains (not_executed_last_iteration
, stmt
))
3240 if (gimple_has_side_effects (stmt
))
3249 /* If no bounding statement is found, continue the walk. */
3255 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3257 if (loop_exit_edge_p (loop
, e
)
3258 || e
== loop_latch_edge (loop
))
3263 if (bitmap_set_bit (visited
, e
->dest
->index
))
3264 VEC_safe_push (basic_block
, heap
, queue
, e
->dest
);
3268 while (VEC_length (basic_block
, queue
) && !found_exit
);
3270 /* If every path through the loop reach bounding statement before exit,
3271 then we know the last iteration of the loop will have undefined effect
3272 and we can decrease number of iterations. */
3276 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3277 fprintf (dump_file
, "Reducing loop iteration estimate by 1; "
3278 "undefined statement must be executed at the last iteration.\n");
3279 record_niter_bound (loop
, loop
->nb_iterations_upper_bound
- double_int_one
,
3282 BITMAP_FREE (visited
);
3283 VEC_free (basic_block
, heap
, queue
);
3286 /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
3287 is true also use estimates derived from undefined behavior. */
3290 estimate_numbers_of_iterations_loop (struct loop
*loop
)
3292 VEC (edge
, heap
) *exits
;
3295 struct tree_niter_desc niter_desc
;
3300 /* Give up if we already have tried to compute an estimation. */
3301 if (loop
->estimate_state
!= EST_NOT_COMPUTED
)
3304 loop
->estimate_state
= EST_AVAILABLE
;
3305 /* Force estimate compuation but leave any existing upper bound in place. */
3306 loop
->any_estimate
= false;
3308 exits
= get_loop_exit_edges (loop
);
3309 likely_exit
= single_likely_exit (loop
);
3310 FOR_EACH_VEC_ELT (edge
, exits
, i
, ex
)
3312 if (!number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
3315 niter
= niter_desc
.niter
;
3316 type
= TREE_TYPE (niter
);
3317 if (TREE_CODE (niter_desc
.may_be_zero
) != INTEGER_CST
)
3318 niter
= build3 (COND_EXPR
, type
, niter_desc
.may_be_zero
,
3319 build_int_cst (type
, 0),
3321 record_estimate (loop
, niter
, niter_desc
.max
,
3322 last_stmt (ex
->src
),
3323 true, ex
== likely_exit
, true);
3325 VEC_free (edge
, heap
, exits
);
3327 infer_loop_bounds_from_undefined (loop
);
3329 discover_iteration_bound_by_body_walk (loop
);
3331 maybe_lower_iteration_bound (loop
);
3333 /* If we have a measured profile, use it to estimate the number of
3335 if (loop
->header
->count
!= 0)
3337 gcov_type nit
= expected_loop_iterations_unbounded (loop
) + 1;
3338 bound
= gcov_type_to_double_int (nit
);
3339 record_niter_bound (loop
, bound
, true, false);
3343 /* Sets NIT to the estimated number of executions of the latch of the
3344 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
3345 large as the number of iterations. If we have no reliable estimate,
3346 the function returns false, otherwise returns true. */
3349 estimated_loop_iterations (struct loop
*loop
, double_int
*nit
)
3351 /* When SCEV information is available, try to update loop iterations
3352 estimate. Otherwise just return whatever we recorded earlier. */
3353 if (scev_initialized_p ())
3354 estimate_numbers_of_iterations_loop (loop
);
3356 /* Even if the bound is not recorded, possibly we can derrive one from
3358 if (!loop
->any_estimate
)
3360 if (loop
->header
->count
)
3362 *nit
= gcov_type_to_double_int
3363 (expected_loop_iterations_unbounded (loop
) + 1);
3369 *nit
= loop
->nb_iterations_estimate
;
3373 /* Sets NIT to an upper bound for the maximum number of executions of the
3374 latch of the LOOP. If we have no reliable estimate, the function returns
3375 false, otherwise returns true. */
3378 max_loop_iterations (struct loop
*loop
, double_int
*nit
)
3380 /* When SCEV information is available, try to update loop iterations
3381 estimate. Otherwise just return whatever we recorded earlier. */
3382 if (scev_initialized_p ())
3383 estimate_numbers_of_iterations_loop (loop
);
3384 if (!loop
->any_upper_bound
)
3387 *nit
= loop
->nb_iterations_upper_bound
;
3391 /* Similar to estimated_loop_iterations, but returns the estimate only
3392 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3393 on the number of iterations of LOOP could not be derived, returns -1. */
3396 estimated_loop_iterations_int (struct loop
*loop
)
3399 HOST_WIDE_INT hwi_nit
;
3401 if (!estimated_loop_iterations (loop
, &nit
))
3404 if (!nit
.fits_shwi ())
3406 hwi_nit
= nit
.to_shwi ();
3408 return hwi_nit
< 0 ? -1 : hwi_nit
;
3411 /* Similar to max_loop_iterations, but returns the estimate only
3412 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3413 on the number of iterations of LOOP could not be derived, returns -1. */
3416 max_loop_iterations_int (struct loop
*loop
)
3419 HOST_WIDE_INT hwi_nit
;
3421 if (!max_loop_iterations (loop
, &nit
))
3424 if (!nit
.fits_shwi ())
3426 hwi_nit
= nit
.to_shwi ();
3428 return hwi_nit
< 0 ? -1 : hwi_nit
;
3431 /* Returns an upper bound on the number of executions of statements
3432 in the LOOP. For statements before the loop exit, this exceeds
3433 the number of execution of the latch by one. */
3436 max_stmt_executions_int (struct loop
*loop
)
3438 HOST_WIDE_INT nit
= max_loop_iterations_int (loop
);
3444 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
3446 /* If the computation overflows, return -1. */
3447 return snit
< 0 ? -1 : snit
;
3450 /* Returns an estimate for the number of executions of statements
3451 in the LOOP. For statements before the loop exit, this exceeds
3452 the number of execution of the latch by one. */
3455 estimated_stmt_executions_int (struct loop
*loop
)
3457 HOST_WIDE_INT nit
= estimated_loop_iterations_int (loop
);
3463 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
3465 /* If the computation overflows, return -1. */
3466 return snit
< 0 ? -1 : snit
;
3469 /* Sets NIT to the estimated maximum number of executions of the latch of the
3470 LOOP, plus one. If we have no reliable estimate, the function returns
3471 false, otherwise returns true. */
3474 max_stmt_executions (struct loop
*loop
, double_int
*nit
)
3476 double_int nit_minus_one
;
3478 if (!max_loop_iterations (loop
, nit
))
3481 nit_minus_one
= *nit
;
3483 *nit
+= double_int_one
;
3485 return (*nit
).ugt (nit_minus_one
);
3488 /* Sets NIT to the estimated number of executions of the latch of the
3489 LOOP, plus one. If we have no reliable estimate, the function returns
3490 false, otherwise returns true. */
3493 estimated_stmt_executions (struct loop
*loop
, double_int
*nit
)
3495 double_int nit_minus_one
;
3497 if (!estimated_loop_iterations (loop
, nit
))
3500 nit_minus_one
= *nit
;
3502 *nit
+= double_int_one
;
3504 return (*nit
).ugt (nit_minus_one
);
3507 /* Records estimates on numbers of iterations of loops. */
3510 estimate_numbers_of_iterations (void)
3515 /* We don't want to issue signed overflow warnings while getting
3516 loop iteration estimates. */
3517 fold_defer_overflow_warnings ();
3519 FOR_EACH_LOOP (li
, loop
, 0)
3521 estimate_numbers_of_iterations_loop (loop
);
3524 fold_undefer_and_ignore_overflow_warnings ();
3527 /* Returns true if statement S1 dominates statement S2. */
3530 stmt_dominates_stmt_p (gimple s1
, gimple s2
)
3532 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
3540 gimple_stmt_iterator bsi
;
3542 if (gimple_code (s2
) == GIMPLE_PHI
)
3545 if (gimple_code (s1
) == GIMPLE_PHI
)
3548 for (bsi
= gsi_start_bb (bb1
); gsi_stmt (bsi
) != s2
; gsi_next (&bsi
))
3549 if (gsi_stmt (bsi
) == s1
)
3555 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
3558 /* Returns true when we can prove that the number of executions of
3559 STMT in the loop is at most NITER, according to the bound on
3560 the number of executions of the statement NITER_BOUND->stmt recorded in
3561 NITER_BOUND. If STMT is NULL, we must prove this bound for all
3562 statements in the loop. */
3565 n_of_executions_at_most (gimple stmt
,
3566 struct nb_iter_bound
*niter_bound
,
3569 double_int bound
= niter_bound
->bound
;
3570 tree nit_type
= TREE_TYPE (niter
), e
;
3573 gcc_assert (TYPE_UNSIGNED (nit_type
));
3575 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
3576 the number of iterations is small. */
3577 if (!double_int_fits_to_tree_p (nit_type
, bound
))
3580 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3581 times. This means that:
3583 -- if NITER_BOUND->is_exit is true, then everything before
3584 NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3585 times, and everything after it at most NITER_BOUND->bound times.
3587 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
3588 is executed, then NITER_BOUND->stmt is executed as well in the same
3589 iteration (we conclude that if both statements belong to the same
3590 basic block, or if STMT is after NITER_BOUND->stmt), then STMT
3591 is executed at most NITER_BOUND->bound + 1 times. Otherwise STMT is
3592 executed at most NITER_BOUND->bound + 2 times. */
3594 if (niter_bound
->is_exit
)
3597 && stmt
!= niter_bound
->stmt
3598 && stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
3606 || (gimple_bb (stmt
) != gimple_bb (niter_bound
->stmt
)
3607 && !stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
)))
3609 bound
+= double_int_one
;
3610 if (bound
.is_zero ()
3611 || !double_int_fits_to_tree_p (nit_type
, bound
))
3617 e
= fold_binary (cmp
, boolean_type_node
,
3618 niter
, double_int_to_tree (nit_type
, bound
));
3619 return e
&& integer_nonzerop (e
);
3622 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
3625 nowrap_type_p (tree type
)
3627 if (INTEGRAL_TYPE_P (type
)
3628 && TYPE_OVERFLOW_UNDEFINED (type
))
3631 if (POINTER_TYPE_P (type
))
3637 /* Return false only when the induction variable BASE + STEP * I is
3638 known to not overflow: i.e. when the number of iterations is small
3639 enough with respect to the step and initial condition in order to
3640 keep the evolution confined in TYPEs bounds. Return true when the
3641 iv is known to overflow or when the property is not computable.
3643 USE_OVERFLOW_SEMANTICS is true if this function should assume that
3644 the rules for overflow of the given language apply (e.g., that signed
3645 arithmetics in C does not overflow). */
3648 scev_probably_wraps_p (tree base
, tree step
,
3649 gimple at_stmt
, struct loop
*loop
,
3650 bool use_overflow_semantics
)
3652 struct nb_iter_bound
*bound
;
3653 tree delta
, step_abs
;
3654 tree unsigned_type
, valid_niter
;
3655 tree type
= TREE_TYPE (step
);
3657 /* FIXME: We really need something like
3658 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
3660 We used to test for the following situation that frequently appears
3661 during address arithmetics:
3663 D.1621_13 = (long unsigned intD.4) D.1620_12;
3664 D.1622_14 = D.1621_13 * 8;
3665 D.1623_15 = (doubleD.29 *) D.1622_14;
3667 And derived that the sequence corresponding to D_14
3668 can be proved to not wrap because it is used for computing a
3669 memory access; however, this is not really the case -- for example,
3670 if D_12 = (unsigned char) [254,+,1], then D_14 has values
3671 2032, 2040, 0, 8, ..., but the code is still legal. */
3673 if (chrec_contains_undetermined (base
)
3674 || chrec_contains_undetermined (step
))
3677 if (integer_zerop (step
))
3680 /* If we can use the fact that signed and pointer arithmetics does not
3681 wrap, we are done. */
3682 if (use_overflow_semantics
&& nowrap_type_p (TREE_TYPE (base
)))
3685 /* To be able to use estimates on number of iterations of the loop,
3686 we must have an upper bound on the absolute value of the step. */
3687 if (TREE_CODE (step
) != INTEGER_CST
)
3690 /* Don't issue signed overflow warnings. */
3691 fold_defer_overflow_warnings ();
3693 /* Otherwise, compute the number of iterations before we reach the
3694 bound of the type, and verify that the loop is exited before this
3696 unsigned_type
= unsigned_type_for (type
);
3697 base
= fold_convert (unsigned_type
, base
);
3699 if (tree_int_cst_sign_bit (step
))
3701 tree extreme
= fold_convert (unsigned_type
,
3702 lower_bound_in_type (type
, type
));
3703 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
3704 step_abs
= fold_build1 (NEGATE_EXPR
, unsigned_type
,
3705 fold_convert (unsigned_type
, step
));
3709 tree extreme
= fold_convert (unsigned_type
,
3710 upper_bound_in_type (type
, type
));
3711 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
3712 step_abs
= fold_convert (unsigned_type
, step
);
3715 valid_niter
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step_abs
);
3717 estimate_numbers_of_iterations_loop (loop
);
3718 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
3720 if (n_of_executions_at_most (at_stmt
, bound
, valid_niter
))
3722 fold_undefer_and_ignore_overflow_warnings ();
3727 fold_undefer_and_ignore_overflow_warnings ();
3729 /* At this point we still don't have a proof that the iv does not
3730 overflow: give up. */
3734 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
3737 free_numbers_of_iterations_estimates_loop (struct loop
*loop
)
3739 struct nb_iter_bound
*bound
, *next
;
3741 loop
->nb_iterations
= NULL
;
3742 loop
->estimate_state
= EST_NOT_COMPUTED
;
3743 for (bound
= loop
->bounds
; bound
; bound
= next
)
3749 loop
->bounds
= NULL
;
3752 /* Frees the information on upper bounds on numbers of iterations of loops. */
3755 free_numbers_of_iterations_estimates (void)
3760 FOR_EACH_LOOP (li
, loop
, 0)
3762 free_numbers_of_iterations_estimates_loop (loop
);
3766 /* Substitute value VAL for ssa name NAME inside expressions held
3770 substitute_in_loop_info (struct loop
*loop
, tree name
, tree val
)
3772 loop
->nb_iterations
= simplify_replace_tree (loop
->nb_iterations
, name
, val
);