1 /* Functions to determine/estimate number of iterations of a loop.
2 Copyright (C) 2004-2013 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
26 #include "basic-block.h"
27 #include "gimple-pretty-print.h"
30 #include "gimple-ssa.h"
32 #include "tree-phinodes.h"
33 #include "ssa-iterators.h"
34 #include "tree-ssa-loop-ivopts.h"
35 #include "tree-ssa-loop-niter.h"
36 #include "tree-ssa-loop.h"
40 #include "tree-chrec.h"
41 #include "tree-scalar-evolution.h"
42 #include "tree-data-ref.h"
45 #include "diagnostic-core.h"
46 #include "tree-inline.h"
47 #include "tree-pass.h"
50 #define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
52 /* The maximum number of dominator BBs we search for conditions
53 of loop header copies we use for simplifying a conditional
55 #define MAX_DOMINATORS_TO_WALK 8
59 Analysis of number of iterations of an affine exit test.
63 /* Bounds on some value, BELOW <= X <= UP. */
71 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */
74 split_to_var_and_offset (tree expr
, tree
*var
, mpz_t offset
)
76 tree type
= TREE_TYPE (expr
);
82 mpz_set_ui (offset
, 0);
84 switch (TREE_CODE (expr
))
91 case POINTER_PLUS_EXPR
:
92 op0
= TREE_OPERAND (expr
, 0);
93 op1
= TREE_OPERAND (expr
, 1);
95 if (TREE_CODE (op1
) != INTEGER_CST
)
99 /* Always sign extend the offset. */
100 off
= tree_to_double_int (op1
);
101 off
= off
.sext (TYPE_PRECISION (type
));
102 mpz_set_double_int (offset
, off
, false);
104 mpz_neg (offset
, offset
);
108 *var
= build_int_cst_type (type
, 0);
109 off
= tree_to_double_int (expr
);
110 mpz_set_double_int (offset
, off
, TYPE_UNSIGNED (type
));
118 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
119 in TYPE to MIN and MAX. */
122 determine_value_range (tree type
, tree var
, mpz_t off
,
123 mpz_t min
, mpz_t max
)
125 /* If the expression is a constant, we know its value exactly. */
126 if (integer_zerop (var
))
133 /* If the computation may wrap, we know nothing about the value, except for
134 the range of the type. */
135 get_type_static_bounds (type
, min
, max
);
136 if (!nowrap_type_p (type
))
139 /* Since the addition of OFF does not wrap, if OFF is positive, then we may
140 add it to MIN, otherwise to MAX. */
141 if (mpz_sgn (off
) < 0)
142 mpz_add (max
, max
, off
);
144 mpz_add (min
, min
, off
);
147 /* Stores the bounds on the difference of the values of the expressions
148 (var + X) and (var + Y), computed in TYPE, to BNDS. */
151 bound_difference_of_offsetted_base (tree type
, mpz_t x
, mpz_t y
,
154 int rel
= mpz_cmp (x
, y
);
155 bool may_wrap
= !nowrap_type_p (type
);
158 /* If X == Y, then the expressions are always equal.
159 If X > Y, there are the following possibilities:
160 a) neither of var + X and var + Y overflow or underflow, or both of
161 them do. Then their difference is X - Y.
162 b) var + X overflows, and var + Y does not. Then the values of the
163 expressions are var + X - M and var + Y, where M is the range of
164 the type, and their difference is X - Y - M.
165 c) var + Y underflows and var + X does not. Their difference again
167 Therefore, if the arithmetics in type does not overflow, then the
168 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
169 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
170 (X - Y, X - Y + M). */
174 mpz_set_ui (bnds
->below
, 0);
175 mpz_set_ui (bnds
->up
, 0);
180 mpz_set_double_int (m
, double_int::mask (TYPE_PRECISION (type
)), true);
181 mpz_add_ui (m
, m
, 1);
182 mpz_sub (bnds
->up
, x
, y
);
183 mpz_set (bnds
->below
, bnds
->up
);
188 mpz_sub (bnds
->below
, bnds
->below
, m
);
190 mpz_add (bnds
->up
, bnds
->up
, m
);
196 /* From condition C0 CMP C1 derives information regarding the
197 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
198 and stores it to BNDS. */
201 refine_bounds_using_guard (tree type
, tree varx
, mpz_t offx
,
202 tree vary
, mpz_t offy
,
203 tree c0
, enum tree_code cmp
, tree c1
,
206 tree varc0
, varc1
, tmp
, ctype
;
207 mpz_t offc0
, offc1
, loffx
, loffy
, bnd
;
209 bool no_wrap
= nowrap_type_p (type
);
218 STRIP_SIGN_NOPS (c0
);
219 STRIP_SIGN_NOPS (c1
);
220 ctype
= TREE_TYPE (c0
);
221 if (!useless_type_conversion_p (ctype
, type
))
227 /* We could derive quite precise information from EQ_EXPR, however, such
228 a guard is unlikely to appear, so we do not bother with handling
233 /* NE_EXPR comparisons do not contain much of useful information, except for
234 special case of comparing with the bounds of the type. */
235 if (TREE_CODE (c1
) != INTEGER_CST
236 || !INTEGRAL_TYPE_P (type
))
239 /* Ensure that the condition speaks about an expression in the same type
241 ctype
= TREE_TYPE (c0
);
242 if (TYPE_PRECISION (ctype
) != TYPE_PRECISION (type
))
244 c0
= fold_convert (type
, c0
);
245 c1
= fold_convert (type
, c1
);
247 if (TYPE_MIN_VALUE (type
)
248 && operand_equal_p (c1
, TYPE_MIN_VALUE (type
), 0))
253 if (TYPE_MAX_VALUE (type
)
254 && operand_equal_p (c1
, TYPE_MAX_VALUE (type
), 0))
267 split_to_var_and_offset (expand_simple_operations (c0
), &varc0
, offc0
);
268 split_to_var_and_offset (expand_simple_operations (c1
), &varc1
, offc1
);
270 /* We are only interested in comparisons of expressions based on VARX and
271 VARY. TODO -- we might also be able to derive some bounds from
272 expressions containing just one of the variables. */
274 if (operand_equal_p (varx
, varc1
, 0))
276 tmp
= varc0
; varc0
= varc1
; varc1
= tmp
;
277 mpz_swap (offc0
, offc1
);
278 cmp
= swap_tree_comparison (cmp
);
281 if (!operand_equal_p (varx
, varc0
, 0)
282 || !operand_equal_p (vary
, varc1
, 0))
285 mpz_init_set (loffx
, offx
);
286 mpz_init_set (loffy
, offy
);
288 if (cmp
== GT_EXPR
|| cmp
== GE_EXPR
)
290 tmp
= varx
; varx
= vary
; vary
= tmp
;
291 mpz_swap (offc0
, offc1
);
292 mpz_swap (loffx
, loffy
);
293 cmp
= swap_tree_comparison (cmp
);
297 /* If there is no overflow, the condition implies that
299 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
301 The overflows and underflows may complicate things a bit; each
302 overflow decreases the appropriate offset by M, and underflow
303 increases it by M. The above inequality would not necessarily be
306 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
307 VARX + OFFC0 overflows, but VARX + OFFX does not.
308 This may only happen if OFFX < OFFC0.
309 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
310 VARY + OFFC1 underflows and VARY + OFFY does not.
311 This may only happen if OFFY > OFFC1. */
320 x_ok
= (integer_zerop (varx
)
321 || mpz_cmp (loffx
, offc0
) >= 0);
322 y_ok
= (integer_zerop (vary
)
323 || mpz_cmp (loffy
, offc1
) <= 0);
329 mpz_sub (bnd
, loffx
, loffy
);
330 mpz_add (bnd
, bnd
, offc1
);
331 mpz_sub (bnd
, bnd
, offc0
);
334 mpz_sub_ui (bnd
, bnd
, 1);
339 if (mpz_cmp (bnds
->below
, bnd
) < 0)
340 mpz_set (bnds
->below
, bnd
);
344 if (mpz_cmp (bnd
, bnds
->up
) < 0)
345 mpz_set (bnds
->up
, bnd
);
357 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
358 The subtraction is considered to be performed in arbitrary precision,
361 We do not attempt to be too clever regarding the value ranges of X and
362 Y; most of the time, they are just integers or ssa names offsetted by
363 integer. However, we try to use the information contained in the
364 comparisons before the loop (usually created by loop header copying). */
367 bound_difference (struct loop
*loop
, tree x
, tree y
, bounds
*bnds
)
369 tree type
= TREE_TYPE (x
);
372 mpz_t minx
, maxx
, miny
, maxy
;
380 /* Get rid of unnecessary casts, but preserve the value of
385 mpz_init (bnds
->below
);
389 split_to_var_and_offset (x
, &varx
, offx
);
390 split_to_var_and_offset (y
, &vary
, offy
);
392 if (!integer_zerop (varx
)
393 && operand_equal_p (varx
, vary
, 0))
395 /* Special case VARX == VARY -- we just need to compare the
396 offsets. The matters are a bit more complicated in the
397 case addition of offsets may wrap. */
398 bound_difference_of_offsetted_base (type
, offx
, offy
, bnds
);
402 /* Otherwise, use the value ranges to determine the initial
403 estimates on below and up. */
408 determine_value_range (type
, varx
, offx
, minx
, maxx
);
409 determine_value_range (type
, vary
, offy
, miny
, maxy
);
411 mpz_sub (bnds
->below
, minx
, maxy
);
412 mpz_sub (bnds
->up
, maxx
, miny
);
419 /* If both X and Y are constants, we cannot get any more precise. */
420 if (integer_zerop (varx
) && integer_zerop (vary
))
423 /* Now walk the dominators of the loop header and use the entry
424 guards to refine the estimates. */
425 for (bb
= loop
->header
;
426 bb
!= ENTRY_BLOCK_PTR
&& cnt
< MAX_DOMINATORS_TO_WALK
;
427 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
429 if (!single_pred_p (bb
))
431 e
= single_pred_edge (bb
);
433 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
436 cond
= last_stmt (e
->src
);
437 c0
= gimple_cond_lhs (cond
);
438 cmp
= gimple_cond_code (cond
);
439 c1
= gimple_cond_rhs (cond
);
441 if (e
->flags
& EDGE_FALSE_VALUE
)
442 cmp
= invert_tree_comparison (cmp
, false);
444 refine_bounds_using_guard (type
, varx
, offx
, vary
, offy
,
454 /* Update the bounds in BNDS that restrict the value of X to the bounds
455 that restrict the value of X + DELTA. X can be obtained as a
456 difference of two values in TYPE. */
459 bounds_add (bounds
*bnds
, double_int delta
, tree type
)
464 mpz_set_double_int (mdelta
, delta
, false);
467 mpz_set_double_int (max
, double_int::mask (TYPE_PRECISION (type
)), true);
469 mpz_add (bnds
->up
, bnds
->up
, mdelta
);
470 mpz_add (bnds
->below
, bnds
->below
, mdelta
);
472 if (mpz_cmp (bnds
->up
, max
) > 0)
473 mpz_set (bnds
->up
, max
);
476 if (mpz_cmp (bnds
->below
, max
) < 0)
477 mpz_set (bnds
->below
, max
);
483 /* Update the bounds in BNDS that restrict the value of X to the bounds
484 that restrict the value of -X. */
487 bounds_negate (bounds
*bnds
)
491 mpz_init_set (tmp
, bnds
->up
);
492 mpz_neg (bnds
->up
, bnds
->below
);
493 mpz_neg (bnds
->below
, tmp
);
497 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
500 inverse (tree x
, tree mask
)
502 tree type
= TREE_TYPE (x
);
504 unsigned ctr
= tree_floor_log2 (mask
);
506 if (TYPE_PRECISION (type
) <= HOST_BITS_PER_WIDE_INT
)
508 unsigned HOST_WIDE_INT ix
;
509 unsigned HOST_WIDE_INT imask
;
510 unsigned HOST_WIDE_INT irslt
= 1;
512 gcc_assert (cst_and_fits_in_hwi (x
));
513 gcc_assert (cst_and_fits_in_hwi (mask
));
515 ix
= int_cst_value (x
);
516 imask
= int_cst_value (mask
);
525 rslt
= build_int_cst_type (type
, irslt
);
529 rslt
= build_int_cst (type
, 1);
532 rslt
= int_const_binop (MULT_EXPR
, rslt
, x
);
533 x
= int_const_binop (MULT_EXPR
, x
, x
);
535 rslt
= int_const_binop (BIT_AND_EXPR
, rslt
, mask
);
541 /* Derives the upper bound BND on the number of executions of loop with exit
542 condition S * i <> C. If NO_OVERFLOW is true, then the control variable of
543 the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed
544 that the loop ends through this exit, i.e., the induction variable ever
545 reaches the value of C.
547 The value C is equal to final - base, where final and base are the final and
548 initial value of the actual induction variable in the analysed loop. BNDS
549 bounds the value of this difference when computed in signed type with
550 unbounded range, while the computation of C is performed in an unsigned
551 type with the range matching the range of the type of the induction variable.
552 In particular, BNDS.up contains an upper bound on C in the following cases:
553 -- if the iv must reach its final value without overflow, i.e., if
554 NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
555 -- if final >= base, which we know to hold when BNDS.below >= 0. */
558 number_of_iterations_ne_max (mpz_t bnd
, bool no_overflow
, tree c
, tree s
,
559 bounds
*bnds
, bool exit_must_be_taken
)
563 tree type
= TREE_TYPE (c
);
564 bool bnds_u_valid
= ((no_overflow
&& exit_must_be_taken
)
565 || mpz_sgn (bnds
->below
) >= 0);
568 || (TREE_CODE (c
) == INTEGER_CST
569 && TREE_CODE (s
) == INTEGER_CST
570 && tree_to_double_int (c
).mod (tree_to_double_int (s
),
571 TYPE_UNSIGNED (type
),
572 EXACT_DIV_EXPR
).is_zero ())
573 || (TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (c
))
574 && multiple_of_p (type
, c
, s
)))
576 /* If C is an exact multiple of S, then its value will be reached before
577 the induction variable overflows (unless the loop is exited in some
578 other way before). Note that the actual induction variable in the
579 loop (which ranges from base to final instead of from 0 to C) may
580 overflow, in which case BNDS.up will not be giving a correct upper
581 bound on C; thus, BNDS_U_VALID had to be computed in advance. */
583 exit_must_be_taken
= true;
586 /* If the induction variable can overflow, the number of iterations is at
587 most the period of the control variable (or infinite, but in that case
588 the whole # of iterations analysis will fail). */
591 max
= double_int::mask (TYPE_PRECISION (type
)
592 - tree_low_cst (num_ending_zeros (s
), 1));
593 mpz_set_double_int (bnd
, max
, true);
597 /* Now we know that the induction variable does not overflow, so the loop
598 iterates at most (range of type / S) times. */
599 mpz_set_double_int (bnd
, double_int::mask (TYPE_PRECISION (type
)), true);
601 /* If the induction variable is guaranteed to reach the value of C before
603 if (exit_must_be_taken
)
605 /* ... then we can strengthen this to C / S, and possibly we can use
606 the upper bound on C given by BNDS. */
607 if (TREE_CODE (c
) == INTEGER_CST
)
608 mpz_set_double_int (bnd
, tree_to_double_int (c
), true);
609 else if (bnds_u_valid
)
610 mpz_set (bnd
, bnds
->up
);
614 mpz_set_double_int (d
, tree_to_double_int (s
), true);
615 mpz_fdiv_q (bnd
, bnd
, d
);
619 /* Determines number of iterations of loop whose ending condition
620 is IV <> FINAL. TYPE is the type of the iv. The number of
621 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
622 we know that the exit must be taken eventually, i.e., that the IV
623 ever reaches the value FINAL (we derived this earlier, and possibly set
624 NITER->assumptions to make sure this is the case). BNDS contains the
625 bounds on the difference FINAL - IV->base. */
628 number_of_iterations_ne (tree type
, affine_iv
*iv
, tree final
,
629 struct tree_niter_desc
*niter
, bool exit_must_be_taken
,
632 tree niter_type
= unsigned_type_for (type
);
633 tree s
, c
, d
, bits
, assumption
, tmp
, bound
;
636 niter
->control
= *iv
;
637 niter
->bound
= final
;
638 niter
->cmp
= NE_EXPR
;
640 /* Rearrange the terms so that we get inequality S * i <> C, with S
641 positive. Also cast everything to the unsigned type. If IV does
642 not overflow, BNDS bounds the value of C. Also, this is the
643 case if the computation |FINAL - IV->base| does not overflow, i.e.,
644 if BNDS->below in the result is nonnegative. */
645 if (tree_int_cst_sign_bit (iv
->step
))
647 s
= fold_convert (niter_type
,
648 fold_build1 (NEGATE_EXPR
, type
, iv
->step
));
649 c
= fold_build2 (MINUS_EXPR
, niter_type
,
650 fold_convert (niter_type
, iv
->base
),
651 fold_convert (niter_type
, final
));
652 bounds_negate (bnds
);
656 s
= fold_convert (niter_type
, iv
->step
);
657 c
= fold_build2 (MINUS_EXPR
, niter_type
,
658 fold_convert (niter_type
, final
),
659 fold_convert (niter_type
, iv
->base
));
663 number_of_iterations_ne_max (max
, iv
->no_overflow
, c
, s
, bnds
,
665 niter
->max
= mpz_get_double_int (niter_type
, max
, false);
668 /* First the trivial cases -- when the step is 1. */
669 if (integer_onep (s
))
675 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
676 is infinite. Otherwise, the number of iterations is
677 (inverse(s/d) * (c/d)) mod (size of mode/d). */
678 bits
= num_ending_zeros (s
);
679 bound
= build_low_bits_mask (niter_type
,
680 (TYPE_PRECISION (niter_type
)
681 - tree_low_cst (bits
, 1)));
683 d
= fold_binary_to_constant (LSHIFT_EXPR
, niter_type
,
684 build_int_cst (niter_type
, 1), bits
);
685 s
= fold_binary_to_constant (RSHIFT_EXPR
, niter_type
, s
, bits
);
687 if (!exit_must_be_taken
)
689 /* If we cannot assume that the exit is taken eventually, record the
690 assumptions for divisibility of c. */
691 assumption
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, c
, d
);
692 assumption
= fold_build2 (EQ_EXPR
, boolean_type_node
,
693 assumption
, build_int_cst (niter_type
, 0));
694 if (!integer_nonzerop (assumption
))
695 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
696 niter
->assumptions
, assumption
);
699 c
= fold_build2 (EXACT_DIV_EXPR
, niter_type
, c
, d
);
700 tmp
= fold_build2 (MULT_EXPR
, niter_type
, c
, inverse (s
, bound
));
701 niter
->niter
= fold_build2 (BIT_AND_EXPR
, niter_type
, tmp
, bound
);
705 /* Checks whether we can determine the final value of the control variable
706 of the loop with ending condition IV0 < IV1 (computed in TYPE).
707 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
708 of the step. The assumptions necessary to ensure that the computation
709 of the final value does not overflow are recorded in NITER. If we
710 find the final value, we adjust DELTA and return TRUE. Otherwise
711 we return false. BNDS bounds the value of IV1->base - IV0->base,
712 and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
713 true if we know that the exit must be taken eventually. */
716 number_of_iterations_lt_to_ne (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
717 struct tree_niter_desc
*niter
,
718 tree
*delta
, tree step
,
719 bool exit_must_be_taken
, bounds
*bnds
)
721 tree niter_type
= TREE_TYPE (step
);
722 tree mod
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, *delta
, step
);
725 tree assumption
= boolean_true_node
, bound
, noloop
;
726 bool ret
= false, fv_comp_no_overflow
;
728 if (POINTER_TYPE_P (type
))
731 if (TREE_CODE (mod
) != INTEGER_CST
)
733 if (integer_nonzerop (mod
))
734 mod
= fold_build2 (MINUS_EXPR
, niter_type
, step
, mod
);
735 tmod
= fold_convert (type1
, mod
);
738 mpz_set_double_int (mmod
, tree_to_double_int (mod
), true);
739 mpz_neg (mmod
, mmod
);
741 /* If the induction variable does not overflow and the exit is taken,
742 then the computation of the final value does not overflow. This is
743 also obviously the case if the new final value is equal to the
744 current one. Finally, we postulate this for pointer type variables,
745 as the code cannot rely on the object to that the pointer points being
746 placed at the end of the address space (and more pragmatically,
747 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
748 if (integer_zerop (mod
) || POINTER_TYPE_P (type
))
749 fv_comp_no_overflow
= true;
750 else if (!exit_must_be_taken
)
751 fv_comp_no_overflow
= false;
753 fv_comp_no_overflow
=
754 (iv0
->no_overflow
&& integer_nonzerop (iv0
->step
))
755 || (iv1
->no_overflow
&& integer_nonzerop (iv1
->step
));
757 if (integer_nonzerop (iv0
->step
))
759 /* The final value of the iv is iv1->base + MOD, assuming that this
760 computation does not overflow, and that
761 iv0->base <= iv1->base + MOD. */
762 if (!fv_comp_no_overflow
)
764 bound
= fold_build2 (MINUS_EXPR
, type1
,
765 TYPE_MAX_VALUE (type1
), tmod
);
766 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
768 if (integer_zerop (assumption
))
771 if (mpz_cmp (mmod
, bnds
->below
) < 0)
772 noloop
= boolean_false_node
;
773 else if (POINTER_TYPE_P (type
))
774 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
776 fold_build_pointer_plus (iv1
->base
, tmod
));
778 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
780 fold_build2 (PLUS_EXPR
, type1
,
785 /* The final value of the iv is iv0->base - MOD, assuming that this
786 computation does not overflow, and that
787 iv0->base - MOD <= iv1->base. */
788 if (!fv_comp_no_overflow
)
790 bound
= fold_build2 (PLUS_EXPR
, type1
,
791 TYPE_MIN_VALUE (type1
), tmod
);
792 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
794 if (integer_zerop (assumption
))
797 if (mpz_cmp (mmod
, bnds
->below
) < 0)
798 noloop
= boolean_false_node
;
799 else if (POINTER_TYPE_P (type
))
800 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
801 fold_build_pointer_plus (iv0
->base
,
802 fold_build1 (NEGATE_EXPR
,
806 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
807 fold_build2 (MINUS_EXPR
, type1
,
812 if (!integer_nonzerop (assumption
))
813 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
816 if (!integer_zerop (noloop
))
817 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
820 bounds_add (bnds
, tree_to_double_int (mod
), type
);
821 *delta
= fold_build2 (PLUS_EXPR
, niter_type
, *delta
, mod
);
829 /* Add assertions to NITER that ensure that the control variable of the loop
830 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
831 are TYPE. Returns false if we can prove that there is an overflow, true
832 otherwise. STEP is the absolute value of the step. */
835 assert_no_overflow_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
836 struct tree_niter_desc
*niter
, tree step
)
838 tree bound
, d
, assumption
, diff
;
839 tree niter_type
= TREE_TYPE (step
);
841 if (integer_nonzerop (iv0
->step
))
843 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
844 if (iv0
->no_overflow
)
847 /* If iv0->base is a constant, we can determine the last value before
848 overflow precisely; otherwise we conservatively assume
851 if (TREE_CODE (iv0
->base
) == INTEGER_CST
)
853 d
= fold_build2 (MINUS_EXPR
, niter_type
,
854 fold_convert (niter_type
, TYPE_MAX_VALUE (type
)),
855 fold_convert (niter_type
, iv0
->base
));
856 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
859 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
860 build_int_cst (niter_type
, 1));
861 bound
= fold_build2 (MINUS_EXPR
, type
,
862 TYPE_MAX_VALUE (type
), fold_convert (type
, diff
));
863 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
868 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
869 if (iv1
->no_overflow
)
872 if (TREE_CODE (iv1
->base
) == INTEGER_CST
)
874 d
= fold_build2 (MINUS_EXPR
, niter_type
,
875 fold_convert (niter_type
, iv1
->base
),
876 fold_convert (niter_type
, TYPE_MIN_VALUE (type
)));
877 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
880 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
881 build_int_cst (niter_type
, 1));
882 bound
= fold_build2 (PLUS_EXPR
, type
,
883 TYPE_MIN_VALUE (type
), fold_convert (type
, diff
));
884 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
888 if (integer_zerop (assumption
))
890 if (!integer_nonzerop (assumption
))
891 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
892 niter
->assumptions
, assumption
);
894 iv0
->no_overflow
= true;
895 iv1
->no_overflow
= true;
899 /* Add an assumption to NITER that a loop whose ending condition
900 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
901 bounds the value of IV1->base - IV0->base. */
904 assert_loop_rolls_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
905 struct tree_niter_desc
*niter
, bounds
*bnds
)
907 tree assumption
= boolean_true_node
, bound
, diff
;
908 tree mbz
, mbzl
, mbzr
, type1
;
909 bool rolls_p
, no_overflow_p
;
913 /* We are going to compute the number of iterations as
914 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
915 variant of TYPE. This formula only works if
917 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
919 (where MAX is the maximum value of the unsigned variant of TYPE, and
920 the computations in this formula are performed in full precision,
921 i.e., without overflows).
923 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
924 we have a condition of the form iv0->base - step < iv1->base before the loop,
925 and for loops iv0->base < iv1->base - step * i the condition
926 iv0->base < iv1->base + step, due to loop header copying, which enable us
927 to prove the lower bound.
929 The upper bound is more complicated. Unless the expressions for initial
930 and final value themselves contain enough information, we usually cannot
931 derive it from the context. */
933 /* First check whether the answer does not follow from the bounds we gathered
935 if (integer_nonzerop (iv0
->step
))
936 dstep
= tree_to_double_int (iv0
->step
);
939 dstep
= tree_to_double_int (iv1
->step
).sext (TYPE_PRECISION (type
));
944 mpz_set_double_int (mstep
, dstep
, true);
945 mpz_neg (mstep
, mstep
);
946 mpz_add_ui (mstep
, mstep
, 1);
948 rolls_p
= mpz_cmp (mstep
, bnds
->below
) <= 0;
951 mpz_set_double_int (max
, double_int::mask (TYPE_PRECISION (type
)), true);
952 mpz_add (max
, max
, mstep
);
953 no_overflow_p
= (mpz_cmp (bnds
->up
, max
) <= 0
954 /* For pointers, only values lying inside a single object
955 can be compared or manipulated by pointer arithmetics.
956 Gcc in general does not allow or handle objects larger
957 than half of the address space, hence the upper bound
958 is satisfied for pointers. */
959 || POINTER_TYPE_P (type
));
963 if (rolls_p
&& no_overflow_p
)
967 if (POINTER_TYPE_P (type
))
970 /* Now the hard part; we must formulate the assumption(s) as expressions, and
971 we must be careful not to introduce overflow. */
973 if (integer_nonzerop (iv0
->step
))
975 diff
= fold_build2 (MINUS_EXPR
, type1
,
976 iv0
->step
, build_int_cst (type1
, 1));
978 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
979 0 address never belongs to any object, we can assume this for
981 if (!POINTER_TYPE_P (type
))
983 bound
= fold_build2 (PLUS_EXPR
, type1
,
984 TYPE_MIN_VALUE (type
), diff
);
985 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
989 /* And then we can compute iv0->base - diff, and compare it with
991 mbzl
= fold_build2 (MINUS_EXPR
, type1
,
992 fold_convert (type1
, iv0
->base
), diff
);
993 mbzr
= fold_convert (type1
, iv1
->base
);
997 diff
= fold_build2 (PLUS_EXPR
, type1
,
998 iv1
->step
, build_int_cst (type1
, 1));
1000 if (!POINTER_TYPE_P (type
))
1002 bound
= fold_build2 (PLUS_EXPR
, type1
,
1003 TYPE_MAX_VALUE (type
), diff
);
1004 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
1008 mbzl
= fold_convert (type1
, iv0
->base
);
1009 mbzr
= fold_build2 (MINUS_EXPR
, type1
,
1010 fold_convert (type1
, iv1
->base
), diff
);
1013 if (!integer_nonzerop (assumption
))
1014 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1015 niter
->assumptions
, assumption
);
1018 mbz
= fold_build2 (GT_EXPR
, boolean_type_node
, mbzl
, mbzr
);
1019 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1020 niter
->may_be_zero
, mbz
);
1024 /* Determines number of iterations of loop whose ending condition
1025 is IV0 < IV1. TYPE is the type of the iv. The number of
1026 iterations is stored to NITER. BNDS bounds the difference
1027 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
1028 that the exit must be taken eventually. */
1031 number_of_iterations_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1032 struct tree_niter_desc
*niter
,
1033 bool exit_must_be_taken
, bounds
*bnds
)
1035 tree niter_type
= unsigned_type_for (type
);
1036 tree delta
, step
, s
;
1039 if (integer_nonzerop (iv0
->step
))
1041 niter
->control
= *iv0
;
1042 niter
->cmp
= LT_EXPR
;
1043 niter
->bound
= iv1
->base
;
1047 niter
->control
= *iv1
;
1048 niter
->cmp
= GT_EXPR
;
1049 niter
->bound
= iv0
->base
;
1052 delta
= fold_build2 (MINUS_EXPR
, niter_type
,
1053 fold_convert (niter_type
, iv1
->base
),
1054 fold_convert (niter_type
, iv0
->base
));
1056 /* First handle the special case that the step is +-1. */
1057 if ((integer_onep (iv0
->step
) && integer_zerop (iv1
->step
))
1058 || (integer_all_onesp (iv1
->step
) && integer_zerop (iv0
->step
)))
1060 /* for (i = iv0->base; i < iv1->base; i++)
1064 for (i = iv1->base; i > iv0->base; i--).
1066 In both cases # of iterations is iv1->base - iv0->base, assuming that
1067 iv1->base >= iv0->base.
1069 First try to derive a lower bound on the value of
1070 iv1->base - iv0->base, computed in full precision. If the difference
1071 is nonnegative, we are done, otherwise we must record the
1074 if (mpz_sgn (bnds
->below
) < 0)
1075 niter
->may_be_zero
= fold_build2 (LT_EXPR
, boolean_type_node
,
1076 iv1
->base
, iv0
->base
);
1077 niter
->niter
= delta
;
1078 niter
->max
= mpz_get_double_int (niter_type
, bnds
->up
, false);
1082 if (integer_nonzerop (iv0
->step
))
1083 step
= fold_convert (niter_type
, iv0
->step
);
1085 step
= fold_convert (niter_type
,
1086 fold_build1 (NEGATE_EXPR
, type
, iv1
->step
));
1088 /* If we can determine the final value of the control iv exactly, we can
1089 transform the condition to != comparison. In particular, this will be
1090 the case if DELTA is constant. */
1091 if (number_of_iterations_lt_to_ne (type
, iv0
, iv1
, niter
, &delta
, step
,
1092 exit_must_be_taken
, bnds
))
1096 zps
.base
= build_int_cst (niter_type
, 0);
1098 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1099 zps does not overflow. */
1100 zps
.no_overflow
= true;
1102 return number_of_iterations_ne (type
, &zps
, delta
, niter
, true, bnds
);
1105 /* Make sure that the control iv does not overflow. */
1106 if (!assert_no_overflow_lt (type
, iv0
, iv1
, niter
, step
))
1109 /* We determine the number of iterations as (delta + step - 1) / step. For
1110 this to work, we must know that iv1->base >= iv0->base - step + 1,
1111 otherwise the loop does not roll. */
1112 assert_loop_rolls_lt (type
, iv0
, iv1
, niter
, bnds
);
1114 s
= fold_build2 (MINUS_EXPR
, niter_type
,
1115 step
, build_int_cst (niter_type
, 1));
1116 delta
= fold_build2 (PLUS_EXPR
, niter_type
, delta
, s
);
1117 niter
->niter
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, delta
, step
);
1121 mpz_set_double_int (mstep
, tree_to_double_int (step
), true);
1122 mpz_add (tmp
, bnds
->up
, mstep
);
1123 mpz_sub_ui (tmp
, tmp
, 1);
1124 mpz_fdiv_q (tmp
, tmp
, mstep
);
1125 niter
->max
= mpz_get_double_int (niter_type
, tmp
, false);
1132 /* Determines number of iterations of loop whose ending condition
1133 is IV0 <= IV1. TYPE is the type of the iv. The number of
1134 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
1135 we know that this condition must eventually become false (we derived this
1136 earlier, and possibly set NITER->assumptions to make sure this
1137 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1140 number_of_iterations_le (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1141 struct tree_niter_desc
*niter
, bool exit_must_be_taken
,
1146 if (POINTER_TYPE_P (type
))
1149 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1150 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1151 value of the type. This we must know anyway, since if it is
1152 equal to this value, the loop rolls forever. We do not check
1153 this condition for pointer type ivs, as the code cannot rely on
1154 the object to that the pointer points being placed at the end of
1155 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1156 not defined for pointers). */
1158 if (!exit_must_be_taken
&& !POINTER_TYPE_P (type
))
1160 if (integer_nonzerop (iv0
->step
))
1161 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1162 iv1
->base
, TYPE_MAX_VALUE (type
));
1164 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1165 iv0
->base
, TYPE_MIN_VALUE (type
));
1167 if (integer_zerop (assumption
))
1169 if (!integer_nonzerop (assumption
))
1170 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1171 niter
->assumptions
, assumption
);
1174 if (integer_nonzerop (iv0
->step
))
1176 if (POINTER_TYPE_P (type
))
1177 iv1
->base
= fold_build_pointer_plus_hwi (iv1
->base
, 1);
1179 iv1
->base
= fold_build2 (PLUS_EXPR
, type1
, iv1
->base
,
1180 build_int_cst (type1
, 1));
1182 else if (POINTER_TYPE_P (type
))
1183 iv0
->base
= fold_build_pointer_plus_hwi (iv0
->base
, -1);
1185 iv0
->base
= fold_build2 (MINUS_EXPR
, type1
,
1186 iv0
->base
, build_int_cst (type1
, 1));
1188 bounds_add (bnds
, double_int_one
, type1
);
1190 return number_of_iterations_lt (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1194 /* Dumps description of affine induction variable IV to FILE. */
1197 dump_affine_iv (FILE *file
, affine_iv
*iv
)
1199 if (!integer_zerop (iv
->step
))
1200 fprintf (file
, "[");
1202 print_generic_expr (dump_file
, iv
->base
, TDF_SLIM
);
1204 if (!integer_zerop (iv
->step
))
1206 fprintf (file
, ", + , ");
1207 print_generic_expr (dump_file
, iv
->step
, TDF_SLIM
);
1208 fprintf (file
, "]%s", iv
->no_overflow
? "(no_overflow)" : "");
1212 /* Determine the number of iterations according to condition (for staying
1213 inside loop) which compares two induction variables using comparison
1214 operator CODE. The induction variable on left side of the comparison
1215 is IV0, the right-hand side is IV1. Both induction variables must have
1216 type TYPE, which must be an integer or pointer type. The steps of the
1217 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1219 LOOP is the loop whose number of iterations we are determining.
1221 ONLY_EXIT is true if we are sure this is the only way the loop could be
1222 exited (including possibly non-returning function calls, exceptions, etc.)
1223 -- in this case we can use the information whether the control induction
1224 variables can overflow or not in a more efficient way.
1226 if EVERY_ITERATION is true, we know the test is executed on every iteration.
1228 The results (number of iterations and assumptions as described in
1229 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
1230 Returns false if it fails to determine number of iterations, true if it
1231 was determined (possibly with some assumptions). */
1234 number_of_iterations_cond (struct loop
*loop
,
1235 tree type
, affine_iv
*iv0
, enum tree_code code
,
1236 affine_iv
*iv1
, struct tree_niter_desc
*niter
,
1237 bool only_exit
, bool every_iteration
)
1239 bool exit_must_be_taken
= false, ret
;
1242 /* If the test is not executed every iteration, wrapping may make the test
1244 TODO: the overflow case can be still used as unreliable estimate of upper
1245 bound. But we have no API to pass it down to number of iterations code
1246 and, at present, it will not use it anyway. */
1247 if (!every_iteration
1248 && (!iv0
->no_overflow
|| !iv1
->no_overflow
1249 || code
== NE_EXPR
|| code
== EQ_EXPR
))
1252 /* The meaning of these assumptions is this:
1254 then the rest of information does not have to be valid
1255 if may_be_zero then the loop does not roll, even if
1257 niter
->assumptions
= boolean_true_node
;
1258 niter
->may_be_zero
= boolean_false_node
;
1259 niter
->niter
= NULL_TREE
;
1260 niter
->max
= double_int_zero
;
1262 niter
->bound
= NULL_TREE
;
1263 niter
->cmp
= ERROR_MARK
;
1265 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1266 the control variable is on lhs. */
1267 if (code
== GE_EXPR
|| code
== GT_EXPR
1268 || (code
== NE_EXPR
&& integer_zerop (iv0
->step
)))
1271 code
= swap_tree_comparison (code
);
1274 if (POINTER_TYPE_P (type
))
1276 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1277 to the same object. If they do, the control variable cannot wrap
1278 (as wrap around the bounds of memory will never return a pointer
1279 that would be guaranteed to point to the same object, even if we
1280 avoid undefined behavior by casting to size_t and back). */
1281 iv0
->no_overflow
= true;
1282 iv1
->no_overflow
= true;
1285 /* If the control induction variable does not overflow and the only exit
1286 from the loop is the one that we analyze, we know it must be taken
1290 if (!integer_zerop (iv0
->step
) && iv0
->no_overflow
)
1291 exit_must_be_taken
= true;
1292 else if (!integer_zerop (iv1
->step
) && iv1
->no_overflow
)
1293 exit_must_be_taken
= true;
1296 /* We can handle the case when neither of the sides of the comparison is
1297 invariant, provided that the test is NE_EXPR. This rarely occurs in
1298 practice, but it is simple enough to manage. */
1299 if (!integer_zerop (iv0
->step
) && !integer_zerop (iv1
->step
))
1301 tree step_type
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1302 if (code
!= NE_EXPR
)
1305 iv0
->step
= fold_binary_to_constant (MINUS_EXPR
, step_type
,
1306 iv0
->step
, iv1
->step
);
1307 iv0
->no_overflow
= false;
1308 iv1
->step
= build_int_cst (step_type
, 0);
1309 iv1
->no_overflow
= true;
1312 /* If the result of the comparison is a constant, the loop is weird. More
1313 precise handling would be possible, but the situation is not common enough
1314 to waste time on it. */
1315 if (integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
))
1318 /* Ignore loops of while (i-- < 10) type. */
1319 if (code
!= NE_EXPR
)
1321 if (iv0
->step
&& tree_int_cst_sign_bit (iv0
->step
))
1324 if (!integer_zerop (iv1
->step
) && !tree_int_cst_sign_bit (iv1
->step
))
1328 /* If the loop exits immediately, there is nothing to do. */
1329 tree tem
= fold_binary (code
, boolean_type_node
, iv0
->base
, iv1
->base
);
1330 if (tem
&& integer_zerop (tem
))
1332 niter
->niter
= build_int_cst (unsigned_type_for (type
), 0);
1333 niter
->max
= double_int_zero
;
1337 /* OK, now we know we have a senseful loop. Handle several cases, depending
1338 on what comparison operator is used. */
1339 bound_difference (loop
, iv1
->base
, iv0
->base
, &bnds
);
1341 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1344 "Analyzing # of iterations of loop %d\n", loop
->num
);
1346 fprintf (dump_file
, " exit condition ");
1347 dump_affine_iv (dump_file
, iv0
);
1348 fprintf (dump_file
, " %s ",
1349 code
== NE_EXPR
? "!="
1350 : code
== LT_EXPR
? "<"
1352 dump_affine_iv (dump_file
, iv1
);
1353 fprintf (dump_file
, "\n");
1355 fprintf (dump_file
, " bounds on difference of bases: ");
1356 mpz_out_str (dump_file
, 10, bnds
.below
);
1357 fprintf (dump_file
, " ... ");
1358 mpz_out_str (dump_file
, 10, bnds
.up
);
1359 fprintf (dump_file
, "\n");
1365 gcc_assert (integer_zerop (iv1
->step
));
1366 ret
= number_of_iterations_ne (type
, iv0
, iv1
->base
, niter
,
1367 exit_must_be_taken
, &bnds
);
1371 ret
= number_of_iterations_lt (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1376 ret
= number_of_iterations_le (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1384 mpz_clear (bnds
.up
);
1385 mpz_clear (bnds
.below
);
1387 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1391 fprintf (dump_file
, " result:\n");
1392 if (!integer_nonzerop (niter
->assumptions
))
1394 fprintf (dump_file
, " under assumptions ");
1395 print_generic_expr (dump_file
, niter
->assumptions
, TDF_SLIM
);
1396 fprintf (dump_file
, "\n");
1399 if (!integer_zerop (niter
->may_be_zero
))
1401 fprintf (dump_file
, " zero if ");
1402 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
1403 fprintf (dump_file
, "\n");
1406 fprintf (dump_file
, " # of iterations ");
1407 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
1408 fprintf (dump_file
, ", bounded by ");
1409 dump_double_int (dump_file
, niter
->max
, true);
1410 fprintf (dump_file
, "\n");
1413 fprintf (dump_file
, " failed\n\n");
1418 /* Substitute NEW for OLD in EXPR and fold the result. */
1421 simplify_replace_tree (tree expr
, tree old
, tree new_tree
)
1424 tree ret
= NULL_TREE
, e
, se
;
1429 /* Do not bother to replace constants. */
1430 if (CONSTANT_CLASS_P (old
))
1434 || operand_equal_p (expr
, old
, 0))
1435 return unshare_expr (new_tree
);
1440 n
= TREE_OPERAND_LENGTH (expr
);
1441 for (i
= 0; i
< n
; i
++)
1443 e
= TREE_OPERAND (expr
, i
);
1444 se
= simplify_replace_tree (e
, old
, new_tree
);
1449 ret
= copy_node (expr
);
1451 TREE_OPERAND (ret
, i
) = se
;
1454 return (ret
? fold (ret
) : expr
);
1457 /* Expand definitions of ssa names in EXPR as long as they are simple
1458 enough, and return the new expression. */
1461 expand_simple_operations (tree expr
)
1464 tree ret
= NULL_TREE
, e
, ee
, e1
;
1465 enum tree_code code
;
1468 if (expr
== NULL_TREE
)
1471 if (is_gimple_min_invariant (expr
))
1474 code
= TREE_CODE (expr
);
1475 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
1477 n
= TREE_OPERAND_LENGTH (expr
);
1478 for (i
= 0; i
< n
; i
++)
1480 e
= TREE_OPERAND (expr
, i
);
1481 ee
= expand_simple_operations (e
);
1486 ret
= copy_node (expr
);
1488 TREE_OPERAND (ret
, i
) = ee
;
1494 fold_defer_overflow_warnings ();
1496 fold_undefer_and_ignore_overflow_warnings ();
1500 if (TREE_CODE (expr
) != SSA_NAME
)
1503 stmt
= SSA_NAME_DEF_STMT (expr
);
1504 if (gimple_code (stmt
) == GIMPLE_PHI
)
1506 basic_block src
, dest
;
1508 if (gimple_phi_num_args (stmt
) != 1)
1510 e
= PHI_ARG_DEF (stmt
, 0);
1512 /* Avoid propagating through loop exit phi nodes, which
1513 could break loop-closed SSA form restrictions. */
1514 dest
= gimple_bb (stmt
);
1515 src
= single_pred (dest
);
1516 if (TREE_CODE (e
) == SSA_NAME
1517 && src
->loop_father
!= dest
->loop_father
)
1520 return expand_simple_operations (e
);
1522 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1525 /* Avoid expanding to expressions that contain SSA names that need
1526 to take part in abnormal coalescing. */
1528 FOR_EACH_SSA_TREE_OPERAND (e
, stmt
, iter
, SSA_OP_USE
)
1529 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (e
))
1532 e
= gimple_assign_rhs1 (stmt
);
1533 code
= gimple_assign_rhs_code (stmt
);
1534 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1536 if (is_gimple_min_invariant (e
))
1539 if (code
== SSA_NAME
)
1540 return expand_simple_operations (e
);
1548 /* Casts are simple. */
1549 ee
= expand_simple_operations (e
);
1550 return fold_build1 (code
, TREE_TYPE (expr
), ee
);
1554 case POINTER_PLUS_EXPR
:
1555 /* And increments and decrements by a constant are simple. */
1556 e1
= gimple_assign_rhs2 (stmt
);
1557 if (!is_gimple_min_invariant (e1
))
1560 ee
= expand_simple_operations (e
);
1561 return fold_build2 (code
, TREE_TYPE (expr
), ee
, e1
);
1568 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1569 expression (or EXPR unchanged, if no simplification was possible). */
1572 tree_simplify_using_condition_1 (tree cond
, tree expr
)
1575 tree e
, te
, e0
, e1
, e2
, notcond
;
1576 enum tree_code code
= TREE_CODE (expr
);
1578 if (code
== INTEGER_CST
)
1581 if (code
== TRUTH_OR_EXPR
1582 || code
== TRUTH_AND_EXPR
1583 || code
== COND_EXPR
)
1587 e0
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 0));
1588 if (TREE_OPERAND (expr
, 0) != e0
)
1591 e1
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 1));
1592 if (TREE_OPERAND (expr
, 1) != e1
)
1595 if (code
== COND_EXPR
)
1597 e2
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 2));
1598 if (TREE_OPERAND (expr
, 2) != e2
)
1606 if (code
== COND_EXPR
)
1607 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1609 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1615 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
1616 propagation, and vice versa. Fold does not handle this, since it is
1617 considered too expensive. */
1618 if (TREE_CODE (cond
) == EQ_EXPR
)
1620 e0
= TREE_OPERAND (cond
, 0);
1621 e1
= TREE_OPERAND (cond
, 1);
1623 /* We know that e0 == e1. Check whether we cannot simplify expr
1625 e
= simplify_replace_tree (expr
, e0
, e1
);
1626 if (integer_zerop (e
) || integer_nonzerop (e
))
1629 e
= simplify_replace_tree (expr
, e1
, e0
);
1630 if (integer_zerop (e
) || integer_nonzerop (e
))
1633 if (TREE_CODE (expr
) == EQ_EXPR
)
1635 e0
= TREE_OPERAND (expr
, 0);
1636 e1
= TREE_OPERAND (expr
, 1);
1638 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
1639 e
= simplify_replace_tree (cond
, e0
, e1
);
1640 if (integer_zerop (e
))
1642 e
= simplify_replace_tree (cond
, e1
, e0
);
1643 if (integer_zerop (e
))
1646 if (TREE_CODE (expr
) == NE_EXPR
)
1648 e0
= TREE_OPERAND (expr
, 0);
1649 e1
= TREE_OPERAND (expr
, 1);
1651 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
1652 e
= simplify_replace_tree (cond
, e0
, e1
);
1653 if (integer_zerop (e
))
1654 return boolean_true_node
;
1655 e
= simplify_replace_tree (cond
, e1
, e0
);
1656 if (integer_zerop (e
))
1657 return boolean_true_node
;
1660 te
= expand_simple_operations (expr
);
1662 /* Check whether COND ==> EXPR. */
1663 notcond
= invert_truthvalue (cond
);
1664 e
= fold_binary (TRUTH_OR_EXPR
, boolean_type_node
, notcond
, te
);
1665 if (e
&& integer_nonzerop (e
))
1668 /* Check whether COND ==> not EXPR. */
1669 e
= fold_binary (TRUTH_AND_EXPR
, boolean_type_node
, cond
, te
);
1670 if (e
&& integer_zerop (e
))
1676 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1677 expression (or EXPR unchanged, if no simplification was possible).
1678 Wrapper around tree_simplify_using_condition_1 that ensures that chains
1679 of simple operations in definitions of ssa names in COND are expanded,
1680 so that things like casts or incrementing the value of the bound before
1681 the loop do not cause us to fail. */
1684 tree_simplify_using_condition (tree cond
, tree expr
)
1686 cond
= expand_simple_operations (cond
);
1688 return tree_simplify_using_condition_1 (cond
, expr
);
1691 /* Tries to simplify EXPR using the conditions on entry to LOOP.
1692 Returns the simplified expression (or EXPR unchanged, if no
1693 simplification was possible).*/
1696 simplify_using_initial_conditions (struct loop
*loop
, tree expr
)
1704 if (TREE_CODE (expr
) == INTEGER_CST
)
1707 /* Limit walking the dominators to avoid quadraticness in
1708 the number of BBs times the number of loops in degenerate
1710 for (bb
= loop
->header
;
1711 bb
!= ENTRY_BLOCK_PTR
&& cnt
< MAX_DOMINATORS_TO_WALK
;
1712 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1714 if (!single_pred_p (bb
))
1716 e
= single_pred_edge (bb
);
1718 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
1721 stmt
= last_stmt (e
->src
);
1722 cond
= fold_build2 (gimple_cond_code (stmt
),
1724 gimple_cond_lhs (stmt
),
1725 gimple_cond_rhs (stmt
));
1726 if (e
->flags
& EDGE_FALSE_VALUE
)
1727 cond
= invert_truthvalue (cond
);
1728 expr
= tree_simplify_using_condition (cond
, expr
);
1735 /* Tries to simplify EXPR using the evolutions of the loop invariants
1736 in the superloops of LOOP. Returns the simplified expression
1737 (or EXPR unchanged, if no simplification was possible). */
1740 simplify_using_outer_evolutions (struct loop
*loop
, tree expr
)
1742 enum tree_code code
= TREE_CODE (expr
);
1746 if (is_gimple_min_invariant (expr
))
1749 if (code
== TRUTH_OR_EXPR
1750 || code
== TRUTH_AND_EXPR
1751 || code
== COND_EXPR
)
1755 e0
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 0));
1756 if (TREE_OPERAND (expr
, 0) != e0
)
1759 e1
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 1));
1760 if (TREE_OPERAND (expr
, 1) != e1
)
1763 if (code
== COND_EXPR
)
1765 e2
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 2));
1766 if (TREE_OPERAND (expr
, 2) != e2
)
1774 if (code
== COND_EXPR
)
1775 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1777 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1783 e
= instantiate_parameters (loop
, expr
);
1784 if (is_gimple_min_invariant (e
))
1790 /* Returns true if EXIT is the only possible exit from LOOP. */
1793 loop_only_exit_p (const struct loop
*loop
, const_edge exit
)
1796 gimple_stmt_iterator bsi
;
1800 if (exit
!= single_exit (loop
))
1803 body
= get_loop_body (loop
);
1804 for (i
= 0; i
< loop
->num_nodes
; i
++)
1806 for (bsi
= gsi_start_bb (body
[i
]); !gsi_end_p (bsi
); gsi_next (&bsi
))
1808 call
= gsi_stmt (bsi
);
1809 if (gimple_code (call
) != GIMPLE_CALL
)
1812 if (gimple_has_side_effects (call
))
1824 /* Stores description of number of iterations of LOOP derived from
1825 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
1826 useful information could be derived (and fields of NITER has
1827 meaning described in comments at struct tree_niter_desc
1828 declaration), false otherwise. If WARN is true and
1829 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1830 potentially unsafe assumptions.
1831 When EVERY_ITERATION is true, only tests that are known to be executed
1832 every iteration are considered (i.e. only test that alone bounds the loop).
1836 number_of_iterations_exit (struct loop
*loop
, edge exit
,
1837 struct tree_niter_desc
*niter
,
1838 bool warn
, bool every_iteration
)
1843 enum tree_code code
;
1847 safe
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit
->src
);
1849 if (every_iteration
&& !safe
)
1852 niter
->assumptions
= boolean_false_node
;
1853 stmt
= last_stmt (exit
->src
);
1854 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1857 /* We want the condition for staying inside loop. */
1858 code
= gimple_cond_code (stmt
);
1859 if (exit
->flags
& EDGE_TRUE_VALUE
)
1860 code
= invert_tree_comparison (code
, false);
1875 op0
= gimple_cond_lhs (stmt
);
1876 op1
= gimple_cond_rhs (stmt
);
1877 type
= TREE_TYPE (op0
);
1879 if (TREE_CODE (type
) != INTEGER_TYPE
1880 && !POINTER_TYPE_P (type
))
1883 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, false))
1885 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, false))
1888 /* We don't want to see undefined signed overflow warnings while
1889 computing the number of iterations. */
1890 fold_defer_overflow_warnings ();
1892 iv0
.base
= expand_simple_operations (iv0
.base
);
1893 iv1
.base
= expand_simple_operations (iv1
.base
);
1894 if (!number_of_iterations_cond (loop
, type
, &iv0
, code
, &iv1
, niter
,
1895 loop_only_exit_p (loop
, exit
), safe
))
1897 fold_undefer_and_ignore_overflow_warnings ();
1903 niter
->assumptions
= simplify_using_outer_evolutions (loop
,
1904 niter
->assumptions
);
1905 niter
->may_be_zero
= simplify_using_outer_evolutions (loop
,
1906 niter
->may_be_zero
);
1907 niter
->niter
= simplify_using_outer_evolutions (loop
, niter
->niter
);
1911 = simplify_using_initial_conditions (loop
,
1912 niter
->assumptions
);
1914 = simplify_using_initial_conditions (loop
,
1915 niter
->may_be_zero
);
1917 fold_undefer_and_ignore_overflow_warnings ();
1919 /* If NITER has simplified into a constant, update MAX. */
1920 if (TREE_CODE (niter
->niter
) == INTEGER_CST
)
1921 niter
->max
= tree_to_double_int (niter
->niter
);
1923 if (integer_onep (niter
->assumptions
))
1926 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1927 But if we can prove that there is overflow or some other source of weird
1928 behavior, ignore the loop even with -funsafe-loop-optimizations. */
1929 if (integer_zerop (niter
->assumptions
) || !single_exit (loop
))
1932 if (flag_unsafe_loop_optimizations
)
1933 niter
->assumptions
= boolean_true_node
;
1937 const char *wording
;
1938 location_t loc
= gimple_location (stmt
);
1940 /* We can provide a more specific warning if one of the operator is
1941 constant and the other advances by +1 or -1. */
1942 if (!integer_zerop (iv1
.step
)
1943 ? (integer_zerop (iv0
.step
)
1944 && (integer_onep (iv1
.step
) || integer_all_onesp (iv1
.step
)))
1945 : (integer_onep (iv0
.step
) || integer_all_onesp (iv0
.step
)))
1947 flag_unsafe_loop_optimizations
1948 ? N_("assuming that the loop is not infinite")
1949 : N_("cannot optimize possibly infinite loops");
1952 flag_unsafe_loop_optimizations
1953 ? N_("assuming that the loop counter does not overflow")
1954 : N_("cannot optimize loop, the loop counter may overflow");
1956 warning_at ((LOCATION_LINE (loc
) > 0) ? loc
: input_location
,
1957 OPT_Wunsafe_loop_optimizations
, "%s", gettext (wording
));
1960 return flag_unsafe_loop_optimizations
;
1963 /* Try to determine the number of iterations of LOOP. If we succeed,
1964 expression giving number of iterations is returned and *EXIT is
1965 set to the edge from that the information is obtained. Otherwise
1966 chrec_dont_know is returned. */
1969 find_loop_niter (struct loop
*loop
, edge
*exit
)
1972 vec
<edge
> exits
= get_loop_exit_edges (loop
);
1974 tree niter
= NULL_TREE
, aniter
;
1975 struct tree_niter_desc desc
;
1978 FOR_EACH_VEC_ELT (exits
, i
, ex
)
1980 if (!number_of_iterations_exit (loop
, ex
, &desc
, false))
1983 if (integer_nonzerop (desc
.may_be_zero
))
1985 /* We exit in the first iteration through this exit.
1986 We won't find anything better. */
1987 niter
= build_int_cst (unsigned_type_node
, 0);
1992 if (!integer_zerop (desc
.may_be_zero
))
1995 aniter
= desc
.niter
;
1999 /* Nothing recorded yet. */
2005 /* Prefer constants, the lower the better. */
2006 if (TREE_CODE (aniter
) != INTEGER_CST
)
2009 if (TREE_CODE (niter
) != INTEGER_CST
)
2016 if (tree_int_cst_lt (aniter
, niter
))
2025 return niter
? niter
: chrec_dont_know
;
2028 /* Return true if loop is known to have bounded number of iterations. */
2031 finite_loop_p (struct loop
*loop
)
2036 if (flag_unsafe_loop_optimizations
)
2038 flags
= flags_from_decl_or_type (current_function_decl
);
2039 if ((flags
& (ECF_CONST
|ECF_PURE
)) && !(flags
& ECF_LOOPING_CONST_OR_PURE
))
2041 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2042 fprintf (dump_file
, "Found loop %i to be finite: it is within pure or const function.\n",
2047 if (loop
->any_upper_bound
2048 || max_loop_iterations (loop
, &nit
))
2050 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2051 fprintf (dump_file
, "Found loop %i to be finite: upper bound found.\n",
2060 Analysis of a number of iterations of a loop by a brute-force evaluation.
2064 /* Bound on the number of iterations we try to evaluate. */
2066 #define MAX_ITERATIONS_TO_TRACK \
2067 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
2069 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
2070 result by a chain of operations such that all but exactly one of their
2071 operands are constants. */
2074 chain_of_csts_start (struct loop
*loop
, tree x
)
2076 gimple stmt
= SSA_NAME_DEF_STMT (x
);
2078 basic_block bb
= gimple_bb (stmt
);
2079 enum tree_code code
;
2082 || !flow_bb_inside_loop_p (loop
, bb
))
2085 if (gimple_code (stmt
) == GIMPLE_PHI
)
2087 if (bb
== loop
->header
)
2093 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2096 code
= gimple_assign_rhs_code (stmt
);
2097 if (gimple_references_memory_p (stmt
)
2098 || TREE_CODE_CLASS (code
) == tcc_reference
2099 || (code
== ADDR_EXPR
2100 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
2103 use
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
2104 if (use
== NULL_TREE
)
2107 return chain_of_csts_start (loop
, use
);
2110 /* Determines whether the expression X is derived from a result of a phi node
2111 in header of LOOP such that
2113 * the derivation of X consists only from operations with constants
2114 * the initial value of the phi node is constant
2115 * the value of the phi node in the next iteration can be derived from the
2116 value in the current iteration by a chain of operations with constants.
2118 If such phi node exists, it is returned, otherwise NULL is returned. */
2121 get_base_for (struct loop
*loop
, tree x
)
2126 if (is_gimple_min_invariant (x
))
2129 phi
= chain_of_csts_start (loop
, x
);
2133 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2134 next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2136 if (TREE_CODE (next
) != SSA_NAME
)
2139 if (!is_gimple_min_invariant (init
))
2142 if (chain_of_csts_start (loop
, next
) != phi
)
2148 /* Given an expression X, then
2150 * if X is NULL_TREE, we return the constant BASE.
2151 * otherwise X is a SSA name, whose value in the considered loop is derived
2152 by a chain of operations with constant from a result of a phi node in
2153 the header of the loop. Then we return value of X when the value of the
2154 result of this phi node is given by the constant BASE. */
2157 get_val_for (tree x
, tree base
)
2161 gcc_assert (is_gimple_min_invariant (base
));
2166 stmt
= SSA_NAME_DEF_STMT (x
);
2167 if (gimple_code (stmt
) == GIMPLE_PHI
)
2170 gcc_assert (is_gimple_assign (stmt
));
2172 /* STMT must be either an assignment of a single SSA name or an
2173 expression involving an SSA name and a constant. Try to fold that
2174 expression using the value for the SSA name. */
2175 if (gimple_assign_ssa_name_copy_p (stmt
))
2176 return get_val_for (gimple_assign_rhs1 (stmt
), base
);
2177 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_UNARY_RHS
2178 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
2180 return fold_build1 (gimple_assign_rhs_code (stmt
),
2181 gimple_expr_type (stmt
),
2182 get_val_for (gimple_assign_rhs1 (stmt
), base
));
2184 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_BINARY_RHS
)
2186 tree rhs1
= gimple_assign_rhs1 (stmt
);
2187 tree rhs2
= gimple_assign_rhs2 (stmt
);
2188 if (TREE_CODE (rhs1
) == SSA_NAME
)
2189 rhs1
= get_val_for (rhs1
, base
);
2190 else if (TREE_CODE (rhs2
) == SSA_NAME
)
2191 rhs2
= get_val_for (rhs2
, base
);
2194 return fold_build2 (gimple_assign_rhs_code (stmt
),
2195 gimple_expr_type (stmt
), rhs1
, rhs2
);
2202 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2203 by brute force -- i.e. by determining the value of the operands of the
2204 condition at EXIT in first few iterations of the loop (assuming that
2205 these values are constant) and determining the first one in that the
2206 condition is not satisfied. Returns the constant giving the number
2207 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
2210 loop_niter_by_eval (struct loop
*loop
, edge exit
)
2213 tree op
[2], val
[2], next
[2], aval
[2];
2218 cond
= last_stmt (exit
->src
);
2219 if (!cond
|| gimple_code (cond
) != GIMPLE_COND
)
2220 return chrec_dont_know
;
2222 cmp
= gimple_cond_code (cond
);
2223 if (exit
->flags
& EDGE_TRUE_VALUE
)
2224 cmp
= invert_tree_comparison (cmp
, false);
2234 op
[0] = gimple_cond_lhs (cond
);
2235 op
[1] = gimple_cond_rhs (cond
);
2239 return chrec_dont_know
;
2242 for (j
= 0; j
< 2; j
++)
2244 if (is_gimple_min_invariant (op
[j
]))
2247 next
[j
] = NULL_TREE
;
2252 phi
= get_base_for (loop
, op
[j
]);
2254 return chrec_dont_know
;
2255 val
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2256 next
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2260 /* Don't issue signed overflow warnings. */
2261 fold_defer_overflow_warnings ();
2263 for (i
= 0; i
< MAX_ITERATIONS_TO_TRACK
; i
++)
2265 for (j
= 0; j
< 2; j
++)
2266 aval
[j
] = get_val_for (op
[j
], val
[j
]);
2268 acnd
= fold_binary (cmp
, boolean_type_node
, aval
[0], aval
[1]);
2269 if (acnd
&& integer_zerop (acnd
))
2271 fold_undefer_and_ignore_overflow_warnings ();
2272 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2274 "Proved that loop %d iterates %d times using brute force.\n",
2276 return build_int_cst (unsigned_type_node
, i
);
2279 for (j
= 0; j
< 2; j
++)
2281 val
[j
] = get_val_for (next
[j
], val
[j
]);
2282 if (!is_gimple_min_invariant (val
[j
]))
2284 fold_undefer_and_ignore_overflow_warnings ();
2285 return chrec_dont_know
;
2290 fold_undefer_and_ignore_overflow_warnings ();
2292 return chrec_dont_know
;
2295 /* Finds the exit of the LOOP by that the loop exits after a constant
2296 number of iterations and stores the exit edge to *EXIT. The constant
2297 giving the number of iterations of LOOP is returned. The number of
2298 iterations is determined using loop_niter_by_eval (i.e. by brute force
2299 evaluation). If we are unable to find the exit for that loop_niter_by_eval
2300 determines the number of iterations, chrec_dont_know is returned. */
2303 find_loop_niter_by_eval (struct loop
*loop
, edge
*exit
)
2306 vec
<edge
> exits
= get_loop_exit_edges (loop
);
2308 tree niter
= NULL_TREE
, aniter
;
2312 /* Loops with multiple exits are expensive to handle and less important. */
2313 if (!flag_expensive_optimizations
2314 && exits
.length () > 1)
2317 return chrec_dont_know
;
2320 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2322 if (!just_once_each_iteration_p (loop
, ex
->src
))
2325 aniter
= loop_niter_by_eval (loop
, ex
);
2326 if (chrec_contains_undetermined (aniter
))
2330 && !tree_int_cst_lt (aniter
, niter
))
2338 return niter
? niter
: chrec_dont_know
;
2343 Analysis of upper bounds on number of iterations of a loop.
2347 static double_int
derive_constant_upper_bound_ops (tree
, tree
,
2348 enum tree_code
, tree
);
2350 /* Returns a constant upper bound on the value of the right-hand side of
2351 an assignment statement STMT. */
2354 derive_constant_upper_bound_assign (gimple stmt
)
2356 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2357 tree op0
= gimple_assign_rhs1 (stmt
);
2358 tree op1
= gimple_assign_rhs2 (stmt
);
2360 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt
)),
2364 /* Returns a constant upper bound on the value of expression VAL. VAL
2365 is considered to be unsigned. If its type is signed, its value must
2369 derive_constant_upper_bound (tree val
)
2371 enum tree_code code
;
2374 extract_ops_from_tree (val
, &code
, &op0
, &op1
);
2375 return derive_constant_upper_bound_ops (TREE_TYPE (val
), op0
, code
, op1
);
2378 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
2379 whose type is TYPE. The expression is considered to be unsigned. If
2380 its type is signed, its value must be nonnegative. */
2383 derive_constant_upper_bound_ops (tree type
, tree op0
,
2384 enum tree_code code
, tree op1
)
2387 double_int bnd
, max
, mmax
, cst
;
2390 if (INTEGRAL_TYPE_P (type
))
2391 maxt
= TYPE_MAX_VALUE (type
);
2393 maxt
= upper_bound_in_type (type
, type
);
2395 max
= tree_to_double_int (maxt
);
2400 return tree_to_double_int (op0
);
2403 subtype
= TREE_TYPE (op0
);
2404 if (!TYPE_UNSIGNED (subtype
)
2405 /* If TYPE is also signed, the fact that VAL is nonnegative implies
2406 that OP0 is nonnegative. */
2407 && TYPE_UNSIGNED (type
)
2408 && !tree_expr_nonnegative_p (op0
))
2410 /* If we cannot prove that the casted expression is nonnegative,
2411 we cannot establish more useful upper bound than the precision
2412 of the type gives us. */
2416 /* We now know that op0 is an nonnegative value. Try deriving an upper
2418 bnd
= derive_constant_upper_bound (op0
);
2420 /* If the bound does not fit in TYPE, max. value of TYPE could be
2428 case POINTER_PLUS_EXPR
:
2430 if (TREE_CODE (op1
) != INTEGER_CST
2431 || !tree_expr_nonnegative_p (op0
))
2434 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
2435 choose the most logical way how to treat this constant regardless
2436 of the signedness of the type. */
2437 cst
= tree_to_double_int (op1
);
2438 cst
= cst
.sext (TYPE_PRECISION (type
));
2439 if (code
!= MINUS_EXPR
)
2442 bnd
= derive_constant_upper_bound (op0
);
2444 if (cst
.is_negative ())
2447 /* Avoid CST == 0x80000... */
2448 if (cst
.is_negative ())
2451 /* OP0 + CST. We need to check that
2452 BND <= MAX (type) - CST. */
2462 /* OP0 - CST, where CST >= 0.
2464 If TYPE is signed, we have already verified that OP0 >= 0, and we
2465 know that the result is nonnegative. This implies that
2468 If TYPE is unsigned, we must additionally know that OP0 >= CST,
2469 otherwise the operation underflows.
2472 /* This should only happen if the type is unsigned; however, for
2473 buggy programs that use overflowing signed arithmetics even with
2474 -fno-wrapv, this condition may also be true for signed values. */
2478 if (TYPE_UNSIGNED (type
))
2480 tree tem
= fold_binary (GE_EXPR
, boolean_type_node
, op0
,
2481 double_int_to_tree (type
, cst
));
2482 if (!tem
|| integer_nonzerop (tem
))
2491 case FLOOR_DIV_EXPR
:
2492 case EXACT_DIV_EXPR
:
2493 if (TREE_CODE (op1
) != INTEGER_CST
2494 || tree_int_cst_sign_bit (op1
))
2497 bnd
= derive_constant_upper_bound (op0
);
2498 return bnd
.udiv (tree_to_double_int (op1
), FLOOR_DIV_EXPR
);
2501 if (TREE_CODE (op1
) != INTEGER_CST
2502 || tree_int_cst_sign_bit (op1
))
2504 return tree_to_double_int (op1
);
2507 stmt
= SSA_NAME_DEF_STMT (op0
);
2508 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2509 || gimple_assign_lhs (stmt
) != op0
)
2511 return derive_constant_upper_bound_assign (stmt
);
2518 /* Emit a -Waggressive-loop-optimizations warning if needed. */
2521 do_warn_aggressive_loop_optimizations (struct loop
*loop
,
2522 double_int i_bound
, gimple stmt
)
2524 /* Don't warn if the loop doesn't have known constant bound. */
2525 if (!loop
->nb_iterations
2526 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
2527 || !warn_aggressive_loop_optimizations
2528 /* To avoid warning multiple times for the same loop,
2529 only start warning when we preserve loops. */
2530 || (cfun
->curr_properties
& PROP_loops
) == 0
2531 /* Only warn once per loop. */
2532 || loop
->warned_aggressive_loop_optimizations
2533 /* Only warn if undefined behavior gives us lower estimate than the
2534 known constant bound. */
2535 || i_bound
.ucmp (tree_to_double_int (loop
->nb_iterations
)) >= 0
2536 /* And undefined behavior happens unconditionally. */
2537 || !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (stmt
)))
2540 edge e
= single_exit (loop
);
2544 gimple estmt
= last_stmt (e
->src
);
2545 if (warning_at (gimple_location (stmt
), OPT_Waggressive_loop_optimizations
,
2546 "iteration %E invokes undefined behavior",
2547 double_int_to_tree (TREE_TYPE (loop
->nb_iterations
),
2549 inform (gimple_location (estmt
), "containing loop");
2550 loop
->warned_aggressive_loop_optimizations
= true;
2553 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
2554 is true if the loop is exited immediately after STMT, and this exit
2555 is taken at last when the STMT is executed BOUND + 1 times.
2556 REALISTIC is true if BOUND is expected to be close to the real number
2557 of iterations. UPPER is true if we are sure the loop iterates at most
2558 BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */
2561 record_estimate (struct loop
*loop
, tree bound
, double_int i_bound
,
2562 gimple at_stmt
, bool is_exit
, bool realistic
, bool upper
)
2566 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2568 fprintf (dump_file
, "Statement %s", is_exit
? "(exit)" : "");
2569 print_gimple_stmt (dump_file
, at_stmt
, 0, TDF_SLIM
);
2570 fprintf (dump_file
, " is %sexecuted at most ",
2571 upper
? "" : "probably ");
2572 print_generic_expr (dump_file
, bound
, TDF_SLIM
);
2573 fprintf (dump_file
, " (bounded by ");
2574 dump_double_int (dump_file
, i_bound
, true);
2575 fprintf (dump_file
, ") + 1 times in loop %d.\n", loop
->num
);
2578 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
2579 real number of iterations. */
2580 if (TREE_CODE (bound
) != INTEGER_CST
)
2583 gcc_checking_assert (i_bound
== tree_to_double_int (bound
));
2584 if (!upper
&& !realistic
)
2587 /* If we have a guaranteed upper bound, record it in the appropriate
2588 list, unless this is an !is_exit bound (i.e. undefined behavior in
2589 at_stmt) in a loop with known constant number of iterations. */
2592 || loop
->nb_iterations
== NULL_TREE
2593 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
))
2595 struct nb_iter_bound
*elt
= ggc_alloc_nb_iter_bound ();
2597 elt
->bound
= i_bound
;
2598 elt
->stmt
= at_stmt
;
2599 elt
->is_exit
= is_exit
;
2600 elt
->next
= loop
->bounds
;
2604 /* If statement is executed on every path to the loop latch, we can directly
2605 infer the upper bound on the # of iterations of the loop. */
2606 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (at_stmt
)))
2609 /* Update the number of iteration estimates according to the bound.
2610 If at_stmt is an exit then the loop latch is executed at most BOUND times,
2611 otherwise it can be executed BOUND + 1 times. We will lower the estimate
2612 later if such statement must be executed on last iteration */
2614 delta
= double_int_zero
;
2616 delta
= double_int_one
;
2619 /* If an overflow occurred, ignore the result. */
2620 if (i_bound
.ult (delta
))
2623 if (upper
&& !is_exit
)
2624 do_warn_aggressive_loop_optimizations (loop
, i_bound
, at_stmt
);
2625 record_niter_bound (loop
, i_bound
, realistic
, upper
);
2628 /* Record the estimate on number of iterations of LOOP based on the fact that
2629 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
2630 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
2631 estimated number of iterations is expected to be close to the real one.
2632 UPPER is true if we are sure the induction variable does not wrap. */
2635 record_nonwrapping_iv (struct loop
*loop
, tree base
, tree step
, gimple stmt
,
2636 tree low
, tree high
, bool realistic
, bool upper
)
2638 tree niter_bound
, extreme
, delta
;
2639 tree type
= TREE_TYPE (base
), unsigned_type
;
2642 if (TREE_CODE (step
) != INTEGER_CST
|| integer_zerop (step
))
2645 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2647 fprintf (dump_file
, "Induction variable (");
2648 print_generic_expr (dump_file
, TREE_TYPE (base
), TDF_SLIM
);
2649 fprintf (dump_file
, ") ");
2650 print_generic_expr (dump_file
, base
, TDF_SLIM
);
2651 fprintf (dump_file
, " + ");
2652 print_generic_expr (dump_file
, step
, TDF_SLIM
);
2653 fprintf (dump_file
, " * iteration does not wrap in statement ");
2654 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2655 fprintf (dump_file
, " in loop %d.\n", loop
->num
);
2658 unsigned_type
= unsigned_type_for (type
);
2659 base
= fold_convert (unsigned_type
, base
);
2660 step
= fold_convert (unsigned_type
, step
);
2662 if (tree_int_cst_sign_bit (step
))
2664 extreme
= fold_convert (unsigned_type
, low
);
2665 if (TREE_CODE (base
) != INTEGER_CST
)
2666 base
= fold_convert (unsigned_type
, high
);
2667 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
2668 step
= fold_build1 (NEGATE_EXPR
, unsigned_type
, step
);
2672 extreme
= fold_convert (unsigned_type
, high
);
2673 if (TREE_CODE (base
) != INTEGER_CST
)
2674 base
= fold_convert (unsigned_type
, low
);
2675 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
2678 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
2679 would get out of the range. */
2680 niter_bound
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step
);
2681 max
= derive_constant_upper_bound (niter_bound
);
2682 record_estimate (loop
, niter_bound
, max
, stmt
, false, realistic
, upper
);
2685 /* Determine information about number of iterations a LOOP from the index
2686 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
2687 guaranteed to be executed in every iteration of LOOP. Callback for
2697 idx_infer_loop_bounds (tree base
, tree
*idx
, void *dta
)
2699 struct ilb_data
*data
= (struct ilb_data
*) dta
;
2700 tree ev
, init
, step
;
2701 tree low
, high
, type
, next
;
2702 bool sign
, upper
= true, at_end
= false;
2703 struct loop
*loop
= data
->loop
;
2704 bool reliable
= true;
2706 if (TREE_CODE (base
) != ARRAY_REF
)
2709 /* For arrays at the end of the structure, we are not guaranteed that they
2710 do not really extend over their declared size. However, for arrays of
2711 size greater than one, this is unlikely to be intended. */
2712 if (array_at_struct_end_p (base
))
2718 struct loop
*dloop
= loop_containing_stmt (data
->stmt
);
2722 ev
= analyze_scalar_evolution (dloop
, *idx
);
2723 ev
= instantiate_parameters (loop
, ev
);
2724 init
= initial_condition (ev
);
2725 step
= evolution_part_in_loop_num (ev
, loop
->num
);
2729 || TREE_CODE (step
) != INTEGER_CST
2730 || integer_zerop (step
)
2731 || tree_contains_chrecs (init
, NULL
)
2732 || chrec_contains_symbols_defined_in_loop (init
, loop
->num
))
2735 low
= array_ref_low_bound (base
);
2736 high
= array_ref_up_bound (base
);
2738 /* The case of nonconstant bounds could be handled, but it would be
2740 if (TREE_CODE (low
) != INTEGER_CST
2742 || TREE_CODE (high
) != INTEGER_CST
)
2744 sign
= tree_int_cst_sign_bit (step
);
2745 type
= TREE_TYPE (step
);
2747 /* The array of length 1 at the end of a structure most likely extends
2748 beyond its bounds. */
2750 && operand_equal_p (low
, high
, 0))
2753 /* In case the relevant bound of the array does not fit in type, or
2754 it does, but bound + step (in type) still belongs into the range of the
2755 array, the index may wrap and still stay within the range of the array
2756 (consider e.g. if the array is indexed by the full range of
2759 To make things simpler, we require both bounds to fit into type, although
2760 there are cases where this would not be strictly necessary. */
2761 if (!int_fits_type_p (high
, type
)
2762 || !int_fits_type_p (low
, type
))
2764 low
= fold_convert (type
, low
);
2765 high
= fold_convert (type
, high
);
2768 next
= fold_binary (PLUS_EXPR
, type
, low
, step
);
2770 next
= fold_binary (PLUS_EXPR
, type
, high
, step
);
2772 if (tree_int_cst_compare (low
, next
) <= 0
2773 && tree_int_cst_compare (next
, high
) <= 0)
2776 /* If access is not executed on every iteration, we must ensure that overlow may
2777 not make the access valid later. */
2778 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (data
->stmt
))
2779 && scev_probably_wraps_p (initial_condition_in_loop_num (ev
, loop
->num
),
2780 step
, data
->stmt
, loop
, true))
2783 record_nonwrapping_iv (loop
, init
, step
, data
->stmt
, low
, high
, reliable
, upper
);
2787 /* Determine information about number of iterations a LOOP from the bounds
2788 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
2789 STMT is guaranteed to be executed in every iteration of LOOP.*/
2792 infer_loop_bounds_from_ref (struct loop
*loop
, gimple stmt
, tree ref
)
2794 struct ilb_data data
;
2798 for_each_index (&ref
, idx_infer_loop_bounds
, &data
);
2801 /* Determine information about number of iterations of a LOOP from the way
2802 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
2803 executed in every iteration of LOOP. */
2806 infer_loop_bounds_from_array (struct loop
*loop
, gimple stmt
)
2808 if (is_gimple_assign (stmt
))
2810 tree op0
= gimple_assign_lhs (stmt
);
2811 tree op1
= gimple_assign_rhs1 (stmt
);
2813 /* For each memory access, analyze its access function
2814 and record a bound on the loop iteration domain. */
2815 if (REFERENCE_CLASS_P (op0
))
2816 infer_loop_bounds_from_ref (loop
, stmt
, op0
);
2818 if (REFERENCE_CLASS_P (op1
))
2819 infer_loop_bounds_from_ref (loop
, stmt
, op1
);
2821 else if (is_gimple_call (stmt
))
2824 unsigned i
, n
= gimple_call_num_args (stmt
);
2826 lhs
= gimple_call_lhs (stmt
);
2827 if (lhs
&& REFERENCE_CLASS_P (lhs
))
2828 infer_loop_bounds_from_ref (loop
, stmt
, lhs
);
2830 for (i
= 0; i
< n
; i
++)
2832 arg
= gimple_call_arg (stmt
, i
);
2833 if (REFERENCE_CLASS_P (arg
))
2834 infer_loop_bounds_from_ref (loop
, stmt
, arg
);
2839 /* Determine information about number of iterations of a LOOP from the fact
2840 that pointer arithmetics in STMT does not overflow. */
2843 infer_loop_bounds_from_pointer_arith (struct loop
*loop
, gimple stmt
)
2845 tree def
, base
, step
, scev
, type
, low
, high
;
2848 if (!is_gimple_assign (stmt
)
2849 || gimple_assign_rhs_code (stmt
) != POINTER_PLUS_EXPR
)
2852 def
= gimple_assign_lhs (stmt
);
2853 if (TREE_CODE (def
) != SSA_NAME
)
2856 type
= TREE_TYPE (def
);
2857 if (!nowrap_type_p (type
))
2860 ptr
= gimple_assign_rhs1 (stmt
);
2861 if (!expr_invariant_in_loop_p (loop
, ptr
))
2864 var
= gimple_assign_rhs2 (stmt
);
2865 if (TYPE_PRECISION (type
) != TYPE_PRECISION (TREE_TYPE (var
)))
2868 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
2869 if (chrec_contains_undetermined (scev
))
2872 base
= initial_condition_in_loop_num (scev
, loop
->num
);
2873 step
= evolution_part_in_loop_num (scev
, loop
->num
);
2876 || TREE_CODE (step
) != INTEGER_CST
2877 || tree_contains_chrecs (base
, NULL
)
2878 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
2881 low
= lower_bound_in_type (type
, type
);
2882 high
= upper_bound_in_type (type
, type
);
2884 /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
2885 produce a NULL pointer. The contrary would mean NULL points to an object,
2886 while NULL is supposed to compare unequal with the address of all objects.
2887 Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
2888 NULL pointer since that would mean wrapping, which we assume here not to
2889 happen. So, we can exclude NULL from the valid range of pointer
2891 if (flag_delete_null_pointer_checks
&& int_cst_value (low
) == 0)
2892 low
= build_int_cstu (TREE_TYPE (low
), TYPE_ALIGN_UNIT (TREE_TYPE (type
)));
2894 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
2897 /* Determine information about number of iterations of a LOOP from the fact
2898 that signed arithmetics in STMT does not overflow. */
2901 infer_loop_bounds_from_signedness (struct loop
*loop
, gimple stmt
)
2903 tree def
, base
, step
, scev
, type
, low
, high
;
2905 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2908 def
= gimple_assign_lhs (stmt
);
2910 if (TREE_CODE (def
) != SSA_NAME
)
2913 type
= TREE_TYPE (def
);
2914 if (!INTEGRAL_TYPE_P (type
)
2915 || !TYPE_OVERFLOW_UNDEFINED (type
))
2918 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
2919 if (chrec_contains_undetermined (scev
))
2922 base
= initial_condition_in_loop_num (scev
, loop
->num
);
2923 step
= evolution_part_in_loop_num (scev
, loop
->num
);
2926 || TREE_CODE (step
) != INTEGER_CST
2927 || tree_contains_chrecs (base
, NULL
)
2928 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
2931 low
= lower_bound_in_type (type
, type
);
2932 high
= upper_bound_in_type (type
, type
);
2934 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
2937 /* The following analyzers are extracting informations on the bounds
2938 of LOOP from the following undefined behaviors:
2940 - data references should not access elements over the statically
2943 - signed variables should not overflow when flag_wrapv is not set.
2947 infer_loop_bounds_from_undefined (struct loop
*loop
)
2951 gimple_stmt_iterator bsi
;
2955 bbs
= get_loop_body (loop
);
2957 for (i
= 0; i
< loop
->num_nodes
; i
++)
2961 /* If BB is not executed in each iteration of the loop, we cannot
2962 use the operations in it to infer reliable upper bound on the
2963 # of iterations of the loop. However, we can use it as a guess.
2964 Reliable guesses come only from array bounds. */
2965 reliable
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
);
2967 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2969 gimple stmt
= gsi_stmt (bsi
);
2971 infer_loop_bounds_from_array (loop
, stmt
);
2975 infer_loop_bounds_from_signedness (loop
, stmt
);
2976 infer_loop_bounds_from_pointer_arith (loop
, stmt
);
2987 /* Compare double ints, callback for qsort. */
2990 double_int_cmp (const void *p1
, const void *p2
)
2992 const double_int
*d1
= (const double_int
*)p1
;
2993 const double_int
*d2
= (const double_int
*)p2
;
3001 /* Return index of BOUND in BOUNDS array sorted in increasing order.
3002 Lookup by binary search. */
3005 bound_index (vec
<double_int
> bounds
, double_int bound
)
3007 unsigned int end
= bounds
.length ();
3008 unsigned int begin
= 0;
3010 /* Find a matching index by means of a binary search. */
3011 while (begin
!= end
)
3013 unsigned int middle
= (begin
+ end
) / 2;
3014 double_int index
= bounds
[middle
];
3018 else if (index
.ult (bound
))
3026 /* We recorded loop bounds only for statements dominating loop latch (and thus
3027 executed each loop iteration). If there are any bounds on statements not
3028 dominating the loop latch we can improve the estimate by walking the loop
3029 body and seeing if every path from loop header to loop latch contains
3030 some bounded statement. */
3033 discover_iteration_bound_by_body_walk (struct loop
*loop
)
3035 pointer_map_t
*bb_bounds
;
3036 struct nb_iter_bound
*elt
;
3037 vec
<double_int
> bounds
= vNULL
;
3038 vec
<vec
<basic_block
> > queues
= vNULL
;
3039 vec
<basic_block
> queue
= vNULL
;
3040 ptrdiff_t queue_index
;
3041 ptrdiff_t latch_index
= 0;
3042 pointer_map_t
*block_priority
;
3044 /* Discover what bounds may interest us. */
3045 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3047 double_int bound
= elt
->bound
;
3049 /* Exit terminates loop at given iteration, while non-exits produce undefined
3050 effect on the next iteration. */
3053 bound
+= double_int_one
;
3054 /* If an overflow occurred, ignore the result. */
3055 if (bound
.is_zero ())
3059 if (!loop
->any_upper_bound
3060 || bound
.ult (loop
->nb_iterations_upper_bound
))
3061 bounds
.safe_push (bound
);
3064 /* Exit early if there is nothing to do. */
3065 if (!bounds
.exists ())
3068 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3069 fprintf (dump_file
, " Trying to walk loop body to reduce the bound.\n");
3071 /* Sort the bounds in decreasing order. */
3072 qsort (bounds
.address (), bounds
.length (),
3073 sizeof (double_int
), double_int_cmp
);
3075 /* For every basic block record the lowest bound that is guaranteed to
3076 terminate the loop. */
3078 bb_bounds
= pointer_map_create ();
3079 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3081 double_int bound
= elt
->bound
;
3084 bound
+= double_int_one
;
3085 /* If an overflow occurred, ignore the result. */
3086 if (bound
.is_zero ())
3090 if (!loop
->any_upper_bound
3091 || bound
.ult (loop
->nb_iterations_upper_bound
))
3093 ptrdiff_t index
= bound_index (bounds
, bound
);
3094 void **entry
= pointer_map_contains (bb_bounds
,
3095 gimple_bb (elt
->stmt
));
3097 *pointer_map_insert (bb_bounds
,
3098 gimple_bb (elt
->stmt
)) = (void *)index
;
3099 else if ((ptrdiff_t)*entry
> index
)
3100 *entry
= (void *)index
;
3104 block_priority
= pointer_map_create ();
3106 /* Perform shortest path discovery loop->header ... loop->latch.
3108 The "distance" is given by the smallest loop bound of basic block
3109 present in the path and we look for path with largest smallest bound
3112 To avoid the need for fibonacci heap on double ints we simply compress
3113 double ints into indexes to BOUNDS array and then represent the queue
3114 as arrays of queues for every index.
3115 Index of BOUNDS.length() means that the execution of given BB has
3116 no bounds determined.
3118 VISITED is a pointer map translating basic block into smallest index
3119 it was inserted into the priority queue with. */
3122 /* Start walk in loop header with index set to infinite bound. */
3123 queue_index
= bounds
.length ();
3124 queues
.safe_grow_cleared (queue_index
+ 1);
3125 queue
.safe_push (loop
->header
);
3126 queues
[queue_index
] = queue
;
3127 *pointer_map_insert (block_priority
, loop
->header
) = (void *)queue_index
;
3129 for (; queue_index
>= 0; queue_index
--)
3131 if (latch_index
< queue_index
)
3133 while (queues
[queue_index
].length ())
3136 ptrdiff_t bound_index
= queue_index
;
3141 queue
= queues
[queue_index
];
3144 /* OK, we later inserted the BB with lower priority, skip it. */
3145 if ((ptrdiff_t)*pointer_map_contains (block_priority
, bb
) > queue_index
)
3148 /* See if we can improve the bound. */
3149 entry
= pointer_map_contains (bb_bounds
, bb
);
3150 if (entry
&& (ptrdiff_t)*entry
< bound_index
)
3151 bound_index
= (ptrdiff_t)*entry
;
3153 /* Insert succesors into the queue, watch for latch edge
3154 and record greatest index we saw. */
3155 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3157 bool insert
= false;
3160 if (loop_exit_edge_p (loop
, e
))
3163 if (e
== loop_latch_edge (loop
)
3164 && latch_index
< bound_index
)
3165 latch_index
= bound_index
;
3166 else if (!(entry
= pointer_map_contains (block_priority
, e
->dest
)))
3169 *pointer_map_insert (block_priority
, e
->dest
) = (void *)bound_index
;
3171 else if ((ptrdiff_t)*entry
< bound_index
)
3174 *entry
= (void *)bound_index
;
3178 queues
[bound_index
].safe_push (e
->dest
);
3182 queues
[queue_index
].release ();
3185 gcc_assert (latch_index
>= 0);
3186 if ((unsigned)latch_index
< bounds
.length ())
3188 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3190 fprintf (dump_file
, "Found better loop bound ");
3191 dump_double_int (dump_file
, bounds
[latch_index
], true);
3192 fprintf (dump_file
, "\n");
3194 record_niter_bound (loop
, bounds
[latch_index
], false, true);
3199 pointer_map_destroy (bb_bounds
);
3200 pointer_map_destroy (block_priority
);
3203 /* See if every path cross the loop goes through a statement that is known
3204 to not execute at the last iteration. In that case we can decrese iteration
3208 maybe_lower_iteration_bound (struct loop
*loop
)
3210 pointer_set_t
*not_executed_last_iteration
= NULL
;
3211 struct nb_iter_bound
*elt
;
3212 bool found_exit
= false;
3213 vec
<basic_block
> queue
= vNULL
;
3216 /* Collect all statements with interesting (i.e. lower than
3217 nb_iterations_upper_bound) bound on them.
3219 TODO: Due to the way record_estimate choose estimates to store, the bounds
3220 will be always nb_iterations_upper_bound-1. We can change this to record
3221 also statements not dominating the loop latch and update the walk bellow
3222 to the shortest path algorthm. */
3223 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3226 && elt
->bound
.ult (loop
->nb_iterations_upper_bound
))
3228 if (!not_executed_last_iteration
)
3229 not_executed_last_iteration
= pointer_set_create ();
3230 pointer_set_insert (not_executed_last_iteration
, elt
->stmt
);
3233 if (!not_executed_last_iteration
)
3236 /* Start DFS walk in the loop header and see if we can reach the
3237 loop latch or any of the exits (including statements with side
3238 effects that may terminate the loop otherwise) without visiting
3239 any of the statements known to have undefined effect on the last
3241 queue
.safe_push (loop
->header
);
3242 visited
= BITMAP_ALLOC (NULL
);
3243 bitmap_set_bit (visited
, loop
->header
->index
);
3248 basic_block bb
= queue
.pop ();
3249 gimple_stmt_iterator gsi
;
3250 bool stmt_found
= false;
3252 /* Loop for possible exits and statements bounding the execution. */
3253 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3255 gimple stmt
= gsi_stmt (gsi
);
3256 if (pointer_set_contains (not_executed_last_iteration
, stmt
))
3261 if (gimple_has_side_effects (stmt
))
3270 /* If no bounding statement is found, continue the walk. */
3276 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3278 if (loop_exit_edge_p (loop
, e
)
3279 || e
== loop_latch_edge (loop
))
3284 if (bitmap_set_bit (visited
, e
->dest
->index
))
3285 queue
.safe_push (e
->dest
);
3289 while (queue
.length () && !found_exit
);
3291 /* If every path through the loop reach bounding statement before exit,
3292 then we know the last iteration of the loop will have undefined effect
3293 and we can decrease number of iterations. */
3297 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3298 fprintf (dump_file
, "Reducing loop iteration estimate by 1; "
3299 "undefined statement must be executed at the last iteration.\n");
3300 record_niter_bound (loop
, loop
->nb_iterations_upper_bound
- double_int_one
,
3303 BITMAP_FREE (visited
);
3305 pointer_set_destroy (not_executed_last_iteration
);
3308 /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
3309 is true also use estimates derived from undefined behavior. */
3312 estimate_numbers_of_iterations_loop (struct loop
*loop
)
3317 struct tree_niter_desc niter_desc
;
3322 /* Give up if we already have tried to compute an estimation. */
3323 if (loop
->estimate_state
!= EST_NOT_COMPUTED
)
3326 loop
->estimate_state
= EST_AVAILABLE
;
3327 /* Force estimate compuation but leave any existing upper bound in place. */
3328 loop
->any_estimate
= false;
3330 /* Ensure that loop->nb_iterations is computed if possible. If it turns out
3331 to be constant, we avoid undefined behavior implied bounds and instead
3332 diagnose those loops with -Waggressive-loop-optimizations. */
3333 number_of_latch_executions (loop
);
3335 exits
= get_loop_exit_edges (loop
);
3336 likely_exit
= single_likely_exit (loop
);
3337 FOR_EACH_VEC_ELT (exits
, i
, ex
)
3339 if (!number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
3342 niter
= niter_desc
.niter
;
3343 type
= TREE_TYPE (niter
);
3344 if (TREE_CODE (niter_desc
.may_be_zero
) != INTEGER_CST
)
3345 niter
= build3 (COND_EXPR
, type
, niter_desc
.may_be_zero
,
3346 build_int_cst (type
, 0),
3348 record_estimate (loop
, niter
, niter_desc
.max
,
3349 last_stmt (ex
->src
),
3350 true, ex
== likely_exit
, true);
3354 if (flag_aggressive_loop_optimizations
)
3355 infer_loop_bounds_from_undefined (loop
);
3357 discover_iteration_bound_by_body_walk (loop
);
3359 maybe_lower_iteration_bound (loop
);
3361 /* If we have a measured profile, use it to estimate the number of
3363 if (loop
->header
->count
!= 0)
3365 gcov_type nit
= expected_loop_iterations_unbounded (loop
) + 1;
3366 bound
= gcov_type_to_double_int (nit
);
3367 record_niter_bound (loop
, bound
, true, false);
3370 /* If we know the exact number of iterations of this loop, try to
3371 not break code with undefined behavior by not recording smaller
3372 maximum number of iterations. */
3373 if (loop
->nb_iterations
3374 && TREE_CODE (loop
->nb_iterations
) == INTEGER_CST
)
3376 loop
->any_upper_bound
= true;
3377 loop
->nb_iterations_upper_bound
3378 = tree_to_double_int (loop
->nb_iterations
);
3382 /* Sets NIT to the estimated number of executions of the latch of the
3383 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
3384 large as the number of iterations. If we have no reliable estimate,
3385 the function returns false, otherwise returns true. */
3388 estimated_loop_iterations (struct loop
*loop
, double_int
*nit
)
3390 /* When SCEV information is available, try to update loop iterations
3391 estimate. Otherwise just return whatever we recorded earlier. */
3392 if (scev_initialized_p ())
3393 estimate_numbers_of_iterations_loop (loop
);
3395 return (get_estimated_loop_iterations (loop
, nit
));
3398 /* Similar to estimated_loop_iterations, but returns the estimate only
3399 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3400 on the number of iterations of LOOP could not be derived, returns -1. */
3403 estimated_loop_iterations_int (struct loop
*loop
)
3406 HOST_WIDE_INT hwi_nit
;
3408 if (!estimated_loop_iterations (loop
, &nit
))
3411 if (!nit
.fits_shwi ())
3413 hwi_nit
= nit
.to_shwi ();
3415 return hwi_nit
< 0 ? -1 : hwi_nit
;
3419 /* Sets NIT to an upper bound for the maximum number of executions of the
3420 latch of the LOOP. If we have no reliable estimate, the function returns
3421 false, otherwise returns true. */
3424 max_loop_iterations (struct loop
*loop
, double_int
*nit
)
3426 /* When SCEV information is available, try to update loop iterations
3427 estimate. Otherwise just return whatever we recorded earlier. */
3428 if (scev_initialized_p ())
3429 estimate_numbers_of_iterations_loop (loop
);
3431 return get_max_loop_iterations (loop
, nit
);
3434 /* Similar to max_loop_iterations, but returns the estimate only
3435 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3436 on the number of iterations of LOOP could not be derived, returns -1. */
3439 max_loop_iterations_int (struct loop
*loop
)
3442 HOST_WIDE_INT hwi_nit
;
3444 if (!max_loop_iterations (loop
, &nit
))
3447 if (!nit
.fits_shwi ())
3449 hwi_nit
= nit
.to_shwi ();
3451 return hwi_nit
< 0 ? -1 : hwi_nit
;
3454 /* Returns an estimate for the number of executions of statements
3455 in the LOOP. For statements before the loop exit, this exceeds
3456 the number of execution of the latch by one. */
3459 estimated_stmt_executions_int (struct loop
*loop
)
3461 HOST_WIDE_INT nit
= estimated_loop_iterations_int (loop
);
3467 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
3469 /* If the computation overflows, return -1. */
3470 return snit
< 0 ? -1 : snit
;
3473 /* Sets NIT to the estimated maximum number of executions of the latch of the
3474 LOOP, plus one. If we have no reliable estimate, the function returns
3475 false, otherwise returns true. */
3478 max_stmt_executions (struct loop
*loop
, double_int
*nit
)
3480 double_int nit_minus_one
;
3482 if (!max_loop_iterations (loop
, nit
))
3485 nit_minus_one
= *nit
;
3487 *nit
+= double_int_one
;
3489 return (*nit
).ugt (nit_minus_one
);
3492 /* Sets NIT to the estimated number of executions of the latch of the
3493 LOOP, plus one. If we have no reliable estimate, the function returns
3494 false, otherwise returns true. */
3497 estimated_stmt_executions (struct loop
*loop
, double_int
*nit
)
3499 double_int nit_minus_one
;
3501 if (!estimated_loop_iterations (loop
, nit
))
3504 nit_minus_one
= *nit
;
3506 *nit
+= double_int_one
;
3508 return (*nit
).ugt (nit_minus_one
);
3511 /* Records estimates on numbers of iterations of loops. */
3514 estimate_numbers_of_iterations (void)
3519 /* We don't want to issue signed overflow warnings while getting
3520 loop iteration estimates. */
3521 fold_defer_overflow_warnings ();
3523 FOR_EACH_LOOP (li
, loop
, 0)
3525 estimate_numbers_of_iterations_loop (loop
);
3528 fold_undefer_and_ignore_overflow_warnings ();
3531 /* Returns true if statement S1 dominates statement S2. */
3534 stmt_dominates_stmt_p (gimple s1
, gimple s2
)
3536 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
3544 gimple_stmt_iterator bsi
;
3546 if (gimple_code (s2
) == GIMPLE_PHI
)
3549 if (gimple_code (s1
) == GIMPLE_PHI
)
3552 for (bsi
= gsi_start_bb (bb1
); gsi_stmt (bsi
) != s2
; gsi_next (&bsi
))
3553 if (gsi_stmt (bsi
) == s1
)
3559 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
3562 /* Returns true when we can prove that the number of executions of
3563 STMT in the loop is at most NITER, according to the bound on
3564 the number of executions of the statement NITER_BOUND->stmt recorded in
3565 NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT.
3567 ??? This code can become quite a CPU hog - we can have many bounds,
3568 and large basic block forcing stmt_dominates_stmt_p to be queried
3569 many times on a large basic blocks, so the whole thing is O(n^2)
3570 for scev_probably_wraps_p invocation (that can be done n times).
3572 It would make more sense (and give better answers) to remember BB
3573 bounds computed by discover_iteration_bound_by_body_walk. */
3576 n_of_executions_at_most (gimple stmt
,
3577 struct nb_iter_bound
*niter_bound
,
3580 double_int bound
= niter_bound
->bound
;
3581 tree nit_type
= TREE_TYPE (niter
), e
;
3584 gcc_assert (TYPE_UNSIGNED (nit_type
));
3586 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
3587 the number of iterations is small. */
3588 if (!double_int_fits_to_tree_p (nit_type
, bound
))
3591 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3592 times. This means that:
3594 -- if NITER_BOUND->is_exit is true, then everything after
3595 it at most NITER_BOUND->bound times.
3597 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
3598 is executed, then NITER_BOUND->stmt is executed as well in the same
3599 iteration then STMT is executed at most NITER_BOUND->bound + 1 times.
3601 If we can determine that NITER_BOUND->stmt is always executed
3602 after STMT, then STMT is executed at most NITER_BOUND->bound + 2 times.
3603 We conclude that if both statements belong to the same
3604 basic block and STMT is before NITER_BOUND->stmt and there are no
3605 statements with side effects in between. */
3607 if (niter_bound
->is_exit
)
3609 if (stmt
== niter_bound
->stmt
3610 || !stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
3616 if (!stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
3618 gimple_stmt_iterator bsi
;
3619 if (gimple_bb (stmt
) != gimple_bb (niter_bound
->stmt
)
3620 || gimple_code (stmt
) == GIMPLE_PHI
3621 || gimple_code (niter_bound
->stmt
) == GIMPLE_PHI
)
3624 /* By stmt_dominates_stmt_p we already know that STMT appears
3625 before NITER_BOUND->STMT. Still need to test that the loop
3626 can not be terinated by a side effect in between. */
3627 for (bsi
= gsi_for_stmt (stmt
); gsi_stmt (bsi
) != niter_bound
->stmt
;
3629 if (gimple_has_side_effects (gsi_stmt (bsi
)))
3631 bound
+= double_int_one
;
3632 if (bound
.is_zero ()
3633 || !double_int_fits_to_tree_p (nit_type
, bound
))
3639 e
= fold_binary (cmp
, boolean_type_node
,
3640 niter
, double_int_to_tree (nit_type
, bound
));
3641 return e
&& integer_nonzerop (e
);
3644 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
3647 nowrap_type_p (tree type
)
3649 if (INTEGRAL_TYPE_P (type
)
3650 && TYPE_OVERFLOW_UNDEFINED (type
))
3653 if (POINTER_TYPE_P (type
))
3659 /* Return false only when the induction variable BASE + STEP * I is
3660 known to not overflow: i.e. when the number of iterations is small
3661 enough with respect to the step and initial condition in order to
3662 keep the evolution confined in TYPEs bounds. Return true when the
3663 iv is known to overflow or when the property is not computable.
3665 USE_OVERFLOW_SEMANTICS is true if this function should assume that
3666 the rules for overflow of the given language apply (e.g., that signed
3667 arithmetics in C does not overflow). */
3670 scev_probably_wraps_p (tree base
, tree step
,
3671 gimple at_stmt
, struct loop
*loop
,
3672 bool use_overflow_semantics
)
3674 tree delta
, step_abs
;
3675 tree unsigned_type
, valid_niter
;
3676 tree type
= TREE_TYPE (step
);
3679 struct nb_iter_bound
*bound
;
3681 /* FIXME: We really need something like
3682 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
3684 We used to test for the following situation that frequently appears
3685 during address arithmetics:
3687 D.1621_13 = (long unsigned intD.4) D.1620_12;
3688 D.1622_14 = D.1621_13 * 8;
3689 D.1623_15 = (doubleD.29 *) D.1622_14;
3691 And derived that the sequence corresponding to D_14
3692 can be proved to not wrap because it is used for computing a
3693 memory access; however, this is not really the case -- for example,
3694 if D_12 = (unsigned char) [254,+,1], then D_14 has values
3695 2032, 2040, 0, 8, ..., but the code is still legal. */
3697 if (chrec_contains_undetermined (base
)
3698 || chrec_contains_undetermined (step
))
3701 if (integer_zerop (step
))
3704 /* If we can use the fact that signed and pointer arithmetics does not
3705 wrap, we are done. */
3706 if (use_overflow_semantics
&& nowrap_type_p (TREE_TYPE (base
)))
3709 /* To be able to use estimates on number of iterations of the loop,
3710 we must have an upper bound on the absolute value of the step. */
3711 if (TREE_CODE (step
) != INTEGER_CST
)
3714 /* Don't issue signed overflow warnings. */
3715 fold_defer_overflow_warnings ();
3717 /* Otherwise, compute the number of iterations before we reach the
3718 bound of the type, and verify that the loop is exited before this
3720 unsigned_type
= unsigned_type_for (type
);
3721 base
= fold_convert (unsigned_type
, base
);
3723 if (tree_int_cst_sign_bit (step
))
3725 tree extreme
= fold_convert (unsigned_type
,
3726 lower_bound_in_type (type
, type
));
3727 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
3728 step_abs
= fold_build1 (NEGATE_EXPR
, unsigned_type
,
3729 fold_convert (unsigned_type
, step
));
3733 tree extreme
= fold_convert (unsigned_type
,
3734 upper_bound_in_type (type
, type
));
3735 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
3736 step_abs
= fold_convert (unsigned_type
, step
);
3739 valid_niter
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step_abs
);
3741 estimate_numbers_of_iterations_loop (loop
);
3743 if (max_loop_iterations (loop
, &niter
)
3744 && double_int_fits_to_tree_p (TREE_TYPE (valid_niter
), niter
)
3745 && (e
= fold_binary (GT_EXPR
, boolean_type_node
, valid_niter
,
3746 double_int_to_tree (TREE_TYPE (valid_niter
),
3748 && integer_nonzerop (e
))
3750 fold_undefer_and_ignore_overflow_warnings ();
3754 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
3756 if (n_of_executions_at_most (at_stmt
, bound
, valid_niter
))
3758 fold_undefer_and_ignore_overflow_warnings ();
3763 fold_undefer_and_ignore_overflow_warnings ();
3765 /* At this point we still don't have a proof that the iv does not
3766 overflow: give up. */
3770 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
3773 free_numbers_of_iterations_estimates_loop (struct loop
*loop
)
3775 struct nb_iter_bound
*bound
, *next
;
3777 loop
->nb_iterations
= NULL
;
3778 loop
->estimate_state
= EST_NOT_COMPUTED
;
3779 for (bound
= loop
->bounds
; bound
; bound
= next
)
3785 loop
->bounds
= NULL
;
3788 /* Frees the information on upper bounds on numbers of iterations of loops. */
3791 free_numbers_of_iterations_estimates (void)
3796 FOR_EACH_LOOP (li
, loop
, 0)
3798 free_numbers_of_iterations_estimates_loop (loop
);
3802 /* Substitute value VAL for ssa name NAME inside expressions held
3806 substitute_in_loop_info (struct loop
*loop
, tree name
, tree val
)
3808 loop
->nb_iterations
= simplify_replace_tree (loop
->nb_iterations
, name
, val
);