1 /* Functions to determine/estimate number of iterations of a loop.
2 Copyright (C) 2004, 2005, 2006, 2007 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 2, 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 COPYING. If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
23 #include "coretypes.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
31 #include "diagnostic.h"
33 #include "tree-flow.h"
34 #include "tree-dump.h"
36 #include "tree-pass.h"
38 #include "tree-chrec.h"
39 #include "tree-scalar-evolution.h"
40 #include "tree-data-ref.h"
44 #include "tree-inline.h"
47 #define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
49 /* The maximum number of dominator BBs we search for conditions
50 of loop header copies we use for simplifying a conditional
52 #define MAX_DOMINATORS_TO_WALK 8
56 Analysis of number of iterations of an affine exit test.
60 /* Bounds on some value, BELOW <= X <= UP. */
68 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */
71 split_to_var_and_offset (tree expr
, tree
*var
, mpz_t offset
)
73 tree type
= TREE_TYPE (expr
);
79 mpz_set_ui (offset
, 0);
81 switch (TREE_CODE (expr
))
88 case POINTER_PLUS_EXPR
:
89 op0
= TREE_OPERAND (expr
, 0);
90 op1
= TREE_OPERAND (expr
, 1);
92 if (TREE_CODE (op1
) != INTEGER_CST
)
96 /* Always sign extend the offset. */
97 off
= double_int_sext (tree_to_double_int (op1
),
98 TYPE_PRECISION (type
));
99 mpz_set_double_int (offset
, off
, false);
103 *var
= build_int_cst_type (type
, 0);
104 off
= tree_to_double_int (expr
);
105 mpz_set_double_int (offset
, off
, TYPE_UNSIGNED (type
));
113 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
114 in TYPE to MIN and MAX. */
117 determine_value_range (tree type
, tree var
, mpz_t off
,
118 mpz_t min
, mpz_t max
)
120 /* If the expression is a constant, we know its value exactly. */
121 if (integer_zerop (var
))
128 /* If the computation may wrap, we know nothing about the value, except for
129 the range of the type. */
130 get_type_static_bounds (type
, min
, max
);
131 if (!nowrap_type_p (type
))
134 /* Since the addition of OFF does not wrap, if OFF is positive, then we may
135 add it to MIN, otherwise to MAX. */
136 if (mpz_sgn (off
) < 0)
137 mpz_add (max
, max
, off
);
139 mpz_add (min
, min
, off
);
142 /* Stores the bounds on the difference of the values of the expressions
143 (var + X) and (var + Y), computed in TYPE, to BNDS. */
146 bound_difference_of_offsetted_base (tree type
, mpz_t x
, mpz_t y
,
149 int rel
= mpz_cmp (x
, y
);
150 bool may_wrap
= !nowrap_type_p (type
);
153 /* If X == Y, then the expressions are always equal.
154 If X > Y, there are the following possibilities:
155 a) neither of var + X and var + Y overflow or underflow, or both of
156 them do. Then their difference is X - Y.
157 b) var + X overflows, and var + Y does not. Then the values of the
158 expressions are var + X - M and var + Y, where M is the range of
159 the type, and their difference is X - Y - M.
160 c) var + Y underflows and var + X does not. Their difference again
162 Therefore, if the arithmetics in type does not overflow, then the
163 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
164 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
165 (X - Y, X - Y + M). */
169 mpz_set_ui (bnds
->below
, 0);
170 mpz_set_ui (bnds
->up
, 0);
175 mpz_set_double_int (m
, double_int_mask (TYPE_PRECISION (type
)), true);
176 mpz_add_ui (m
, m
, 1);
177 mpz_sub (bnds
->up
, x
, y
);
178 mpz_set (bnds
->below
, bnds
->up
);
183 mpz_sub (bnds
->below
, bnds
->below
, m
);
185 mpz_add (bnds
->up
, bnds
->up
, m
);
191 /* From condition C0 CMP C1 derives information regarding the
192 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
193 and stores it to BNDS. */
196 refine_bounds_using_guard (tree type
, tree varx
, mpz_t offx
,
197 tree vary
, mpz_t offy
,
198 tree c0
, enum tree_code cmp
, tree c1
,
201 tree varc0
, varc1
, tmp
, ctype
;
202 mpz_t offc0
, offc1
, loffx
, loffy
, bnd
;
204 bool no_wrap
= nowrap_type_p (type
);
213 STRIP_SIGN_NOPS (c0
);
214 STRIP_SIGN_NOPS (c1
);
215 ctype
= TREE_TYPE (c0
);
216 if (!useless_type_conversion_p (ctype
, type
))
222 /* We could derive quite precise information from EQ_EXPR, however, such
223 a guard is unlikely to appear, so we do not bother with handling
228 /* NE_EXPR comparisons do not contain much of useful information, except for
229 special case of comparing with the bounds of the type. */
230 if (TREE_CODE (c1
) != INTEGER_CST
231 || !INTEGRAL_TYPE_P (type
))
234 /* Ensure that the condition speaks about an expression in the same type
236 ctype
= TREE_TYPE (c0
);
237 if (TYPE_PRECISION (ctype
) != TYPE_PRECISION (type
))
239 c0
= fold_convert (type
, c0
);
240 c1
= fold_convert (type
, c1
);
242 if (TYPE_MIN_VALUE (type
)
243 && operand_equal_p (c1
, TYPE_MIN_VALUE (type
), 0))
248 if (TYPE_MAX_VALUE (type
)
249 && operand_equal_p (c1
, TYPE_MAX_VALUE (type
), 0))
262 split_to_var_and_offset (expand_simple_operations (c0
), &varc0
, offc0
);
263 split_to_var_and_offset (expand_simple_operations (c1
), &varc1
, offc1
);
265 /* We are only interested in comparisons of expressions based on VARX and
266 VARY. TODO -- we might also be able to derive some bounds from
267 expressions containing just one of the variables. */
269 if (operand_equal_p (varx
, varc1
, 0))
271 tmp
= varc0
; varc0
= varc1
; varc1
= tmp
;
272 mpz_swap (offc0
, offc1
);
273 cmp
= swap_tree_comparison (cmp
);
276 if (!operand_equal_p (varx
, varc0
, 0)
277 || !operand_equal_p (vary
, varc1
, 0))
280 mpz_init_set (loffx
, offx
);
281 mpz_init_set (loffy
, offy
);
283 if (cmp
== GT_EXPR
|| cmp
== GE_EXPR
)
285 tmp
= varx
; varx
= vary
; vary
= tmp
;
286 mpz_swap (offc0
, offc1
);
287 mpz_swap (loffx
, loffy
);
288 cmp
= swap_tree_comparison (cmp
);
292 /* If there is no overflow, the condition implies that
294 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
296 The overflows and underflows may complicate things a bit; each
297 overflow decreases the appropriate offset by M, and underflow
298 increases it by M. The above inequality would not necessarily be
301 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
302 VARX + OFFC0 overflows, but VARX + OFFX does not.
303 This may only happen if OFFX < OFFC0.
304 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
305 VARY + OFFC1 underflows and VARY + OFFY does not.
306 This may only happen if OFFY > OFFC1. */
315 x_ok
= (integer_zerop (varx
)
316 || mpz_cmp (loffx
, offc0
) >= 0);
317 y_ok
= (integer_zerop (vary
)
318 || mpz_cmp (loffy
, offc1
) <= 0);
324 mpz_sub (bnd
, loffx
, loffy
);
325 mpz_add (bnd
, bnd
, offc1
);
326 mpz_sub (bnd
, bnd
, offc0
);
329 mpz_sub_ui (bnd
, bnd
, 1);
334 if (mpz_cmp (bnds
->below
, bnd
) < 0)
335 mpz_set (bnds
->below
, bnd
);
339 if (mpz_cmp (bnd
, bnds
->up
) < 0)
340 mpz_set (bnds
->up
, bnd
);
352 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
353 The subtraction is considered to be performed in arbitrary precision,
356 We do not attempt to be too clever regarding the value ranges of X and
357 Y; most of the time, they are just integers or ssa names offsetted by
358 integer. However, we try to use the information contained in the
359 comparisons before the loop (usually created by loop header copying). */
362 bound_difference (struct loop
*loop
, tree x
, tree y
, bounds
*bnds
)
364 tree type
= TREE_TYPE (x
);
367 mpz_t minx
, maxx
, miny
, maxy
;
374 /* Get rid of unnecessary casts, but preserve the value of
379 mpz_init (bnds
->below
);
383 split_to_var_and_offset (x
, &varx
, offx
);
384 split_to_var_and_offset (y
, &vary
, offy
);
386 if (!integer_zerop (varx
)
387 && operand_equal_p (varx
, vary
, 0))
389 /* Special case VARX == VARY -- we just need to compare the
390 offsets. The matters are a bit more complicated in the
391 case addition of offsets may wrap. */
392 bound_difference_of_offsetted_base (type
, offx
, offy
, bnds
);
396 /* Otherwise, use the value ranges to determine the initial
397 estimates on below and up. */
402 determine_value_range (type
, varx
, offx
, minx
, maxx
);
403 determine_value_range (type
, vary
, offy
, miny
, maxy
);
405 mpz_sub (bnds
->below
, minx
, maxy
);
406 mpz_sub (bnds
->up
, maxx
, miny
);
413 /* If both X and Y are constants, we cannot get any more precise. */
414 if (integer_zerop (varx
) && integer_zerop (vary
))
417 /* Now walk the dominators of the loop header and use the entry
418 guards to refine the estimates. */
419 for (bb
= loop
->header
;
420 bb
!= ENTRY_BLOCK_PTR
&& cnt
< MAX_DOMINATORS_TO_WALK
;
421 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
423 if (!single_pred_p (bb
))
425 e
= single_pred_edge (bb
);
427 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
430 cond
= COND_EXPR_COND (last_stmt (e
->src
));
431 if (!COMPARISON_CLASS_P (cond
))
433 c0
= TREE_OPERAND (cond
, 0);
434 cmp
= TREE_CODE (cond
);
435 c1
= TREE_OPERAND (cond
, 1);
437 if (e
->flags
& EDGE_FALSE_VALUE
)
438 cmp
= invert_tree_comparison (cmp
, false);
440 refine_bounds_using_guard (type
, varx
, offx
, vary
, offy
,
450 /* Update the bounds in BNDS that restrict the value of X to the bounds
451 that restrict the value of X + DELTA. X can be obtained as a
452 difference of two values in TYPE. */
455 bounds_add (bounds
*bnds
, double_int delta
, tree type
)
460 mpz_set_double_int (mdelta
, delta
, false);
463 mpz_set_double_int (max
, double_int_mask (TYPE_PRECISION (type
)), true);
465 mpz_add (bnds
->up
, bnds
->up
, mdelta
);
466 mpz_add (bnds
->below
, bnds
->below
, mdelta
);
468 if (mpz_cmp (bnds
->up
, max
) > 0)
469 mpz_set (bnds
->up
, max
);
472 if (mpz_cmp (bnds
->below
, max
) < 0)
473 mpz_set (bnds
->below
, max
);
479 /* Update the bounds in BNDS that restrict the value of X to the bounds
480 that restrict the value of -X. */
483 bounds_negate (bounds
*bnds
)
487 mpz_init_set (tmp
, bnds
->up
);
488 mpz_neg (bnds
->up
, bnds
->below
);
489 mpz_neg (bnds
->below
, tmp
);
493 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
496 inverse (tree x
, tree mask
)
498 tree type
= TREE_TYPE (x
);
500 unsigned ctr
= tree_floor_log2 (mask
);
502 if (TYPE_PRECISION (type
) <= HOST_BITS_PER_WIDE_INT
)
504 unsigned HOST_WIDE_INT ix
;
505 unsigned HOST_WIDE_INT imask
;
506 unsigned HOST_WIDE_INT irslt
= 1;
508 gcc_assert (cst_and_fits_in_hwi (x
));
509 gcc_assert (cst_and_fits_in_hwi (mask
));
511 ix
= int_cst_value (x
);
512 imask
= int_cst_value (mask
);
521 rslt
= build_int_cst_type (type
, irslt
);
525 rslt
= build_int_cst (type
, 1);
528 rslt
= int_const_binop (MULT_EXPR
, rslt
, x
, 0);
529 x
= int_const_binop (MULT_EXPR
, x
, x
, 0);
531 rslt
= int_const_binop (BIT_AND_EXPR
, rslt
, mask
, 0);
537 /* Derives the upper bound BND on the number of executions of loop with exit
538 condition S * i <> C, assuming that the loop is not infinite. If
539 NO_OVERFLOW is true, then the control variable of the loop does not
540 overflow. If NO_OVERFLOW is true or BNDS.below >= 0, then BNDS.up
541 contains the upper bound on the value of C. */
544 number_of_iterations_ne_max (mpz_t bnd
, bool no_overflow
, tree c
, tree s
,
550 /* If the control variable does not overflow, the number of iterations is
551 at most c / s. Otherwise it is at most the period of the control
553 if (!no_overflow
&& !multiple_of_p (TREE_TYPE (c
), c
, s
))
555 max
= double_int_mask (TYPE_PRECISION (TREE_TYPE (c
))
556 - tree_low_cst (num_ending_zeros (s
), 1));
557 mpz_set_double_int (bnd
, max
, true);
561 /* Determine the upper bound on C. */
562 if (no_overflow
|| mpz_sgn (bnds
->below
) >= 0)
563 mpz_set (bnd
, bnds
->up
);
564 else if (TREE_CODE (c
) == INTEGER_CST
)
565 mpz_set_double_int (bnd
, tree_to_double_int (c
), true);
567 mpz_set_double_int (bnd
, double_int_mask (TYPE_PRECISION (TREE_TYPE (c
))),
571 mpz_set_double_int (d
, tree_to_double_int (s
), true);
572 mpz_fdiv_q (bnd
, bnd
, d
);
576 /* Determines number of iterations of loop whose ending condition
577 is IV <> FINAL. TYPE is the type of the iv. The number of
578 iterations is stored to NITER. NEVER_INFINITE is true if
579 we know that the exit must be taken eventually, i.e., that the IV
580 ever reaches the value FINAL (we derived this earlier, and possibly set
581 NITER->assumptions to make sure this is the case). BNDS contains the
582 bounds on the difference FINAL - IV->base. */
585 number_of_iterations_ne (tree type
, affine_iv
*iv
, tree final
,
586 struct tree_niter_desc
*niter
, bool never_infinite
,
589 tree niter_type
= unsigned_type_for (type
);
590 tree s
, c
, d
, bits
, assumption
, tmp
, bound
;
593 niter
->control
= *iv
;
594 niter
->bound
= final
;
595 niter
->cmp
= NE_EXPR
;
597 /* Rearrange the terms so that we get inequality S * i <> C, with S
598 positive. Also cast everything to the unsigned type. If IV does
599 not overflow, BNDS bounds the value of C. Also, this is the
600 case if the computation |FINAL - IV->base| does not overflow, i.e.,
601 if BNDS->below in the result is nonnegative. */
602 if (tree_int_cst_sign_bit (iv
->step
))
604 s
= fold_convert (niter_type
,
605 fold_build1 (NEGATE_EXPR
, type
, iv
->step
));
606 c
= fold_build2 (MINUS_EXPR
, niter_type
,
607 fold_convert (niter_type
, iv
->base
),
608 fold_convert (niter_type
, final
));
609 bounds_negate (bnds
);
613 s
= fold_convert (niter_type
, iv
->step
);
614 c
= fold_build2 (MINUS_EXPR
, niter_type
,
615 fold_convert (niter_type
, final
),
616 fold_convert (niter_type
, iv
->base
));
620 number_of_iterations_ne_max (max
, iv
->no_overflow
, c
, s
, bnds
);
621 niter
->max
= mpz_get_double_int (niter_type
, max
, false);
624 /* First the trivial cases -- when the step is 1. */
625 if (integer_onep (s
))
631 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
632 is infinite. Otherwise, the number of iterations is
633 (inverse(s/d) * (c/d)) mod (size of mode/d). */
634 bits
= num_ending_zeros (s
);
635 bound
= build_low_bits_mask (niter_type
,
636 (TYPE_PRECISION (niter_type
)
637 - tree_low_cst (bits
, 1)));
639 d
= fold_binary_to_constant (LSHIFT_EXPR
, niter_type
,
640 build_int_cst (niter_type
, 1), bits
);
641 s
= fold_binary_to_constant (RSHIFT_EXPR
, niter_type
, s
, bits
);
645 /* If we cannot assume that the loop is not infinite, record the
646 assumptions for divisibility of c. */
647 assumption
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, c
, d
);
648 assumption
= fold_build2 (EQ_EXPR
, boolean_type_node
,
649 assumption
, build_int_cst (niter_type
, 0));
650 if (!integer_nonzerop (assumption
))
651 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
652 niter
->assumptions
, assumption
);
655 c
= fold_build2 (EXACT_DIV_EXPR
, niter_type
, c
, d
);
656 tmp
= fold_build2 (MULT_EXPR
, niter_type
, c
, inverse (s
, bound
));
657 niter
->niter
= fold_build2 (BIT_AND_EXPR
, niter_type
, tmp
, bound
);
661 /* Checks whether we can determine the final value of the control variable
662 of the loop with ending condition IV0 < IV1 (computed in TYPE).
663 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
664 of the step. The assumptions necessary to ensure that the computation
665 of the final value does not overflow are recorded in NITER. If we
666 find the final value, we adjust DELTA and return TRUE. Otherwise
667 we return false. BNDS bounds the value of IV1->base - IV0->base,
668 and will be updated by the same amount as DELTA. */
671 number_of_iterations_lt_to_ne (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
672 struct tree_niter_desc
*niter
,
673 tree
*delta
, tree step
,
676 tree niter_type
= TREE_TYPE (step
);
677 tree mod
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, *delta
, step
);
680 tree assumption
= boolean_true_node
, bound
, noloop
;
683 if (POINTER_TYPE_P (type
))
686 if (TREE_CODE (mod
) != INTEGER_CST
)
688 if (integer_nonzerop (mod
))
689 mod
= fold_build2 (MINUS_EXPR
, niter_type
, step
, mod
);
690 tmod
= fold_convert (type1
, mod
);
693 mpz_set_double_int (mmod
, tree_to_double_int (mod
), true);
694 mpz_neg (mmod
, mmod
);
696 if (integer_nonzerop (iv0
->step
))
698 /* The final value of the iv is iv1->base + MOD, assuming that this
699 computation does not overflow, and that
700 iv0->base <= iv1->base + MOD. */
701 if (!iv1
->no_overflow
&& !integer_zerop (mod
))
703 bound
= fold_build2 (MINUS_EXPR
, type
,
704 TYPE_MAX_VALUE (type1
), tmod
);
705 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
707 if (integer_zerop (assumption
))
710 if (mpz_cmp (mmod
, bnds
->below
) < 0)
711 noloop
= boolean_false_node
;
713 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
715 fold_build2 (PLUS_EXPR
, type1
,
720 /* The final value of the iv is iv0->base - MOD, assuming that this
721 computation does not overflow, and that
722 iv0->base - MOD <= iv1->base. */
723 if (!iv0
->no_overflow
&& !integer_zerop (mod
))
725 bound
= fold_build2 (PLUS_EXPR
, type1
,
726 TYPE_MIN_VALUE (type1
), tmod
);
727 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
729 if (integer_zerop (assumption
))
732 if (mpz_cmp (mmod
, bnds
->below
) < 0)
733 noloop
= boolean_false_node
;
735 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
736 fold_build2 (MINUS_EXPR
, type1
,
741 if (!integer_nonzerop (assumption
))
742 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
745 if (!integer_zerop (noloop
))
746 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
749 bounds_add (bnds
, tree_to_double_int (mod
), type
);
750 *delta
= fold_build2 (PLUS_EXPR
, niter_type
, *delta
, mod
);
758 /* Add assertions to NITER that ensure that the control variable of the loop
759 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
760 are TYPE. Returns false if we can prove that there is an overflow, true
761 otherwise. STEP is the absolute value of the step. */
764 assert_no_overflow_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
765 struct tree_niter_desc
*niter
, tree step
)
767 tree bound
, d
, assumption
, diff
;
768 tree niter_type
= TREE_TYPE (step
);
770 if (integer_nonzerop (iv0
->step
))
772 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
773 if (iv0
->no_overflow
)
776 /* If iv0->base is a constant, we can determine the last value before
777 overflow precisely; otherwise we conservatively assume
780 if (TREE_CODE (iv0
->base
) == INTEGER_CST
)
782 d
= fold_build2 (MINUS_EXPR
, niter_type
,
783 fold_convert (niter_type
, TYPE_MAX_VALUE (type
)),
784 fold_convert (niter_type
, iv0
->base
));
785 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
788 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
789 build_int_cst (niter_type
, 1));
790 bound
= fold_build2 (MINUS_EXPR
, type
,
791 TYPE_MAX_VALUE (type
), fold_convert (type
, diff
));
792 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
797 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
798 if (iv1
->no_overflow
)
801 if (TREE_CODE (iv1
->base
) == INTEGER_CST
)
803 d
= fold_build2 (MINUS_EXPR
, niter_type
,
804 fold_convert (niter_type
, iv1
->base
),
805 fold_convert (niter_type
, TYPE_MIN_VALUE (type
)));
806 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
809 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
810 build_int_cst (niter_type
, 1));
811 bound
= fold_build2 (PLUS_EXPR
, type
,
812 TYPE_MIN_VALUE (type
), fold_convert (type
, diff
));
813 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
817 if (integer_zerop (assumption
))
819 if (!integer_nonzerop (assumption
))
820 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
821 niter
->assumptions
, assumption
);
823 iv0
->no_overflow
= true;
824 iv1
->no_overflow
= true;
828 /* Add an assumption to NITER that a loop whose ending condition
829 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
830 bounds the value of IV1->base - IV0->base. */
833 assert_loop_rolls_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
834 struct tree_niter_desc
*niter
, bounds
*bnds
)
836 tree assumption
= boolean_true_node
, bound
, diff
;
837 tree mbz
, mbzl
, mbzr
, type1
;
838 bool rolls_p
, no_overflow_p
;
842 /* We are going to compute the number of iterations as
843 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
844 variant of TYPE. This formula only works if
846 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
848 (where MAX is the maximum value of the unsigned variant of TYPE, and
849 the computations in this formula are performed in full precision
852 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
853 we have a condition of form iv0->base - step < iv1->base before the loop,
854 and for loops iv0->base < iv1->base - step * i the condition
855 iv0->base < iv1->base + step, due to loop header copying, which enable us
856 to prove the lower bound.
858 The upper bound is more complicated. Unless the expressions for initial
859 and final value themselves contain enough information, we usually cannot
860 derive it from the context. */
862 /* First check whether the answer does not follow from the bounds we gathered
864 if (integer_nonzerop (iv0
->step
))
865 dstep
= tree_to_double_int (iv0
->step
);
868 dstep
= double_int_sext (tree_to_double_int (iv1
->step
),
869 TYPE_PRECISION (type
));
870 dstep
= double_int_neg (dstep
);
874 mpz_set_double_int (mstep
, dstep
, true);
875 mpz_neg (mstep
, mstep
);
876 mpz_add_ui (mstep
, mstep
, 1);
878 rolls_p
= mpz_cmp (mstep
, bnds
->below
) <= 0;
881 mpz_set_double_int (max
, double_int_mask (TYPE_PRECISION (type
)), true);
882 mpz_add (max
, max
, mstep
);
883 no_overflow_p
= (mpz_cmp (bnds
->up
, max
) <= 0
884 /* For pointers, only values lying inside a single object
885 can be compared or manipulated by pointer arithmetics.
886 Gcc in general does not allow or handle objects larger
887 than half of the address space, hence the upper bound
888 is satisfied for pointers. */
889 || POINTER_TYPE_P (type
));
893 if (rolls_p
&& no_overflow_p
)
897 if (POINTER_TYPE_P (type
))
900 /* Now the hard part; we must formulate the assumption(s) as expressions, and
901 we must be careful not to introduce overflow. */
903 if (integer_nonzerop (iv0
->step
))
905 diff
= fold_build2 (MINUS_EXPR
, type1
,
906 iv0
->step
, build_int_cst (type1
, 1));
908 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
909 0 address never belongs to any object, we can assume this for
911 if (!POINTER_TYPE_P (type
))
913 bound
= fold_build2 (PLUS_EXPR
, type1
,
914 TYPE_MIN_VALUE (type
), diff
);
915 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
919 /* And then we can compute iv0->base - diff, and compare it with
921 mbzl
= fold_build2 (MINUS_EXPR
, type1
, iv0
->base
, diff
);
926 diff
= fold_build2 (PLUS_EXPR
, type1
,
927 iv1
->step
, build_int_cst (type1
, 1));
929 if (!POINTER_TYPE_P (type
))
931 bound
= fold_build2 (PLUS_EXPR
, type1
,
932 TYPE_MAX_VALUE (type
), diff
);
933 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
938 mbzr
= fold_build2 (MINUS_EXPR
, type1
, iv1
->base
, diff
);
941 if (!integer_nonzerop (assumption
))
942 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
943 niter
->assumptions
, assumption
);
946 mbz
= fold_build2 (GT_EXPR
, boolean_type_node
, mbzl
, mbzr
);
947 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
948 niter
->may_be_zero
, mbz
);
952 /* Determines number of iterations of loop whose ending condition
953 is IV0 < IV1. TYPE is the type of the iv. The number of
954 iterations is stored to NITER. BNDS bounds the difference
955 IV1->base - IV0->base. */
958 number_of_iterations_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
959 struct tree_niter_desc
*niter
,
960 bool never_infinite ATTRIBUTE_UNUSED
,
963 tree niter_type
= unsigned_type_for (type
);
967 if (integer_nonzerop (iv0
->step
))
969 niter
->control
= *iv0
;
970 niter
->cmp
= LT_EXPR
;
971 niter
->bound
= iv1
->base
;
975 niter
->control
= *iv1
;
976 niter
->cmp
= GT_EXPR
;
977 niter
->bound
= iv0
->base
;
980 delta
= fold_build2 (MINUS_EXPR
, niter_type
,
981 fold_convert (niter_type
, iv1
->base
),
982 fold_convert (niter_type
, iv0
->base
));
984 /* First handle the special case that the step is +-1. */
985 if ((integer_onep (iv0
->step
) && integer_zerop (iv1
->step
))
986 || (integer_all_onesp (iv1
->step
) && integer_zerop (iv0
->step
)))
988 /* for (i = iv0->base; i < iv1->base; i++)
992 for (i = iv1->base; i > iv0->base; i--).
994 In both cases # of iterations is iv1->base - iv0->base, assuming that
995 iv1->base >= iv0->base.
997 First try to derive a lower bound on the value of
998 iv1->base - iv0->base, computed in full precision. If the difference
999 is nonnegative, we are done, otherwise we must record the
1002 if (mpz_sgn (bnds
->below
) < 0)
1003 niter
->may_be_zero
= fold_build2 (LT_EXPR
, boolean_type_node
,
1004 iv1
->base
, iv0
->base
);
1005 niter
->niter
= delta
;
1006 niter
->max
= mpz_get_double_int (niter_type
, bnds
->up
, false);
1010 if (integer_nonzerop (iv0
->step
))
1011 step
= fold_convert (niter_type
, iv0
->step
);
1013 step
= fold_convert (niter_type
,
1014 fold_build1 (NEGATE_EXPR
, type
, iv1
->step
));
1016 /* If we can determine the final value of the control iv exactly, we can
1017 transform the condition to != comparison. In particular, this will be
1018 the case if DELTA is constant. */
1019 if (number_of_iterations_lt_to_ne (type
, iv0
, iv1
, niter
, &delta
, step
,
1024 zps
.base
= build_int_cst (niter_type
, 0);
1026 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1027 zps does not overflow. */
1028 zps
.no_overflow
= true;
1030 return number_of_iterations_ne (type
, &zps
, delta
, niter
, true, bnds
);
1033 /* Make sure that the control iv does not overflow. */
1034 if (!assert_no_overflow_lt (type
, iv0
, iv1
, niter
, step
))
1037 /* We determine the number of iterations as (delta + step - 1) / step. For
1038 this to work, we must know that iv1->base >= iv0->base - step + 1,
1039 otherwise the loop does not roll. */
1040 assert_loop_rolls_lt (type
, iv0
, iv1
, niter
, bnds
);
1042 s
= fold_build2 (MINUS_EXPR
, niter_type
,
1043 step
, build_int_cst (niter_type
, 1));
1044 delta
= fold_build2 (PLUS_EXPR
, niter_type
, delta
, s
);
1045 niter
->niter
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, delta
, step
);
1049 mpz_set_double_int (mstep
, tree_to_double_int (step
), true);
1050 mpz_add (tmp
, bnds
->up
, mstep
);
1051 mpz_sub_ui (tmp
, tmp
, 1);
1052 mpz_fdiv_q (tmp
, tmp
, mstep
);
1053 niter
->max
= mpz_get_double_int (niter_type
, tmp
, false);
1060 /* Determines number of iterations of loop whose ending condition
1061 is IV0 <= IV1. TYPE is the type of the iv. The number of
1062 iterations is stored to NITER. NEVER_INFINITE is true if
1063 we know that this condition must eventually become false (we derived this
1064 earlier, and possibly set NITER->assumptions to make sure this
1065 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1068 number_of_iterations_le (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1069 struct tree_niter_desc
*niter
, bool never_infinite
,
1074 if (POINTER_TYPE_P (type
))
1077 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1078 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1079 value of the type. This we must know anyway, since if it is
1080 equal to this value, the loop rolls forever. */
1082 if (!never_infinite
)
1084 if (integer_nonzerop (iv0
->step
))
1085 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1086 iv1
->base
, TYPE_MAX_VALUE (type1
));
1088 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1089 iv0
->base
, TYPE_MIN_VALUE (type1
));
1091 if (integer_zerop (assumption
))
1093 if (!integer_nonzerop (assumption
))
1094 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1095 niter
->assumptions
, assumption
);
1098 if (integer_nonzerop (iv0
->step
))
1099 iv1
->base
= fold_build2 (PLUS_EXPR
, type1
,
1100 iv1
->base
, build_int_cst (type1
, 1));
1102 iv0
->base
= fold_build2 (MINUS_EXPR
, type1
,
1103 iv0
->base
, build_int_cst (type1
, 1));
1105 bounds_add (bnds
, double_int_one
, type1
);
1107 return number_of_iterations_lt (type
, iv0
, iv1
, niter
, never_infinite
, bnds
);
1110 /* Dumps description of affine induction variable IV to FILE. */
1113 dump_affine_iv (FILE *file
, affine_iv
*iv
)
1115 if (!integer_zerop (iv
->step
))
1116 fprintf (file
, "[");
1118 print_generic_expr (dump_file
, iv
->base
, TDF_SLIM
);
1120 if (!integer_zerop (iv
->step
))
1122 fprintf (file
, ", + , ");
1123 print_generic_expr (dump_file
, iv
->step
, TDF_SLIM
);
1124 fprintf (file
, "]%s", iv
->no_overflow
? "(no_overflow)" : "");
1128 /* Determine the number of iterations according to condition (for staying
1129 inside loop) which compares two induction variables using comparison
1130 operator CODE. The induction variable on left side of the comparison
1131 is IV0, the right-hand side is IV1. Both induction variables must have
1132 type TYPE, which must be an integer or pointer type. The steps of the
1133 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1135 LOOP is the loop whose number of iterations we are determining.
1137 ONLY_EXIT is true if we are sure this is the only way the loop could be
1138 exited (including possibly non-returning function calls, exceptions, etc.)
1139 -- in this case we can use the information whether the control induction
1140 variables can overflow or not in a more efficient way.
1142 The results (number of iterations and assumptions as described in
1143 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
1144 Returns false if it fails to determine number of iterations, true if it
1145 was determined (possibly with some assumptions). */
1148 number_of_iterations_cond (struct loop
*loop
,
1149 tree type
, affine_iv
*iv0
, enum tree_code code
,
1150 affine_iv
*iv1
, struct tree_niter_desc
*niter
,
1153 bool never_infinite
, ret
;
1156 /* The meaning of these assumptions is this:
1158 then the rest of information does not have to be valid
1159 if may_be_zero then the loop does not roll, even if
1161 niter
->assumptions
= boolean_true_node
;
1162 niter
->may_be_zero
= boolean_false_node
;
1163 niter
->niter
= NULL_TREE
;
1164 niter
->max
= double_int_zero
;
1166 niter
->bound
= NULL_TREE
;
1167 niter
->cmp
= ERROR_MARK
;
1169 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1170 the control variable is on lhs. */
1171 if (code
== GE_EXPR
|| code
== GT_EXPR
1172 || (code
== NE_EXPR
&& integer_zerop (iv0
->step
)))
1175 code
= swap_tree_comparison (code
);
1180 /* If this is not the only possible exit from the loop, the information
1181 that the induction variables cannot overflow as derived from
1182 signedness analysis cannot be relied upon. We use them e.g. in the
1183 following way: given loop for (i = 0; i <= n; i++), if i is
1184 signed, it cannot overflow, thus this loop is equivalent to
1185 for (i = 0; i < n + 1; i++); however, if n == MAX, but the loop
1186 is exited in some other way before i overflows, this transformation
1187 is incorrect (the new loop exits immediately). */
1188 iv0
->no_overflow
= false;
1189 iv1
->no_overflow
= false;
1192 if (POINTER_TYPE_P (type
))
1194 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1195 to the same object. If they do, the control variable cannot wrap
1196 (as wrap around the bounds of memory will never return a pointer
1197 that would be guaranteed to point to the same object, even if we
1198 avoid undefined behavior by casting to size_t and back). The
1199 restrictions on pointer arithmetics and comparisons of pointers
1200 ensure that using the no-overflow assumptions is correct in this
1201 case even if ONLY_EXIT is false. */
1202 iv0
->no_overflow
= true;
1203 iv1
->no_overflow
= true;
1206 /* If the control induction variable does not overflow, the loop obviously
1207 cannot be infinite. */
1208 if (!integer_zerop (iv0
->step
) && iv0
->no_overflow
)
1209 never_infinite
= true;
1210 else if (!integer_zerop (iv1
->step
) && iv1
->no_overflow
)
1211 never_infinite
= true;
1213 never_infinite
= false;
1215 /* We can handle the case when neither of the sides of the comparison is
1216 invariant, provided that the test is NE_EXPR. This rarely occurs in
1217 practice, but it is simple enough to manage. */
1218 if (!integer_zerop (iv0
->step
) && !integer_zerop (iv1
->step
))
1220 if (code
!= NE_EXPR
)
1223 iv0
->step
= fold_binary_to_constant (MINUS_EXPR
, type
,
1224 iv0
->step
, iv1
->step
);
1225 iv0
->no_overflow
= false;
1226 iv1
->step
= build_int_cst (type
, 0);
1227 iv1
->no_overflow
= true;
1230 /* If the result of the comparison is a constant, the loop is weird. More
1231 precise handling would be possible, but the situation is not common enough
1232 to waste time on it. */
1233 if (integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
))
1236 /* Ignore loops of while (i-- < 10) type. */
1237 if (code
!= NE_EXPR
)
1239 if (iv0
->step
&& tree_int_cst_sign_bit (iv0
->step
))
1242 if (!integer_zerop (iv1
->step
) && !tree_int_cst_sign_bit (iv1
->step
))
1246 /* If the loop exits immediately, there is nothing to do. */
1247 if (integer_zerop (fold_build2 (code
, boolean_type_node
, iv0
->base
, iv1
->base
)))
1249 niter
->niter
= build_int_cst (unsigned_type_for (type
), 0);
1250 niter
->max
= double_int_zero
;
1254 /* OK, now we know we have a senseful loop. Handle several cases, depending
1255 on what comparison operator is used. */
1256 bound_difference (loop
, iv1
->base
, iv0
->base
, &bnds
);
1258 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1261 "Analyzing # of iterations of loop %d\n", loop
->num
);
1263 fprintf (dump_file
, " exit condition ");
1264 dump_affine_iv (dump_file
, iv0
);
1265 fprintf (dump_file
, " %s ",
1266 code
== NE_EXPR
? "!="
1267 : code
== LT_EXPR
? "<"
1269 dump_affine_iv (dump_file
, iv1
);
1270 fprintf (dump_file
, "\n");
1272 fprintf (dump_file
, " bounds on difference of bases: ");
1273 mpz_out_str (dump_file
, 10, bnds
.below
);
1274 fprintf (dump_file
, " ... ");
1275 mpz_out_str (dump_file
, 10, bnds
.up
);
1276 fprintf (dump_file
, "\n");
1282 gcc_assert (integer_zerop (iv1
->step
));
1283 ret
= number_of_iterations_ne (type
, iv0
, iv1
->base
, niter
,
1284 never_infinite
, &bnds
);
1288 ret
= number_of_iterations_lt (type
, iv0
, iv1
, niter
, never_infinite
,
1293 ret
= number_of_iterations_le (type
, iv0
, iv1
, niter
, never_infinite
,
1301 mpz_clear (bnds
.up
);
1302 mpz_clear (bnds
.below
);
1304 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1308 fprintf (dump_file
, " result:\n");
1309 if (!integer_nonzerop (niter
->assumptions
))
1311 fprintf (dump_file
, " under assumptions ");
1312 print_generic_expr (dump_file
, niter
->assumptions
, TDF_SLIM
);
1313 fprintf (dump_file
, "\n");
1316 if (!integer_zerop (niter
->may_be_zero
))
1318 fprintf (dump_file
, " zero if ");
1319 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
1320 fprintf (dump_file
, "\n");
1323 fprintf (dump_file
, " # of iterations ");
1324 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
1325 fprintf (dump_file
, ", bounded by ");
1326 dump_double_int (dump_file
, niter
->max
, true);
1327 fprintf (dump_file
, "\n");
1330 fprintf (dump_file
, " failed\n\n");
1335 /* Substitute NEW for OLD in EXPR and fold the result. */
1338 simplify_replace_tree (tree expr
, tree old
, tree new_tree
)
1341 tree ret
= NULL_TREE
, e
, se
;
1347 || operand_equal_p (expr
, old
, 0))
1348 return unshare_expr (new_tree
);
1350 if (!EXPR_P (expr
) && !GIMPLE_STMT_P (expr
))
1353 n
= TREE_OPERAND_LENGTH (expr
);
1354 for (i
= 0; i
< n
; i
++)
1356 e
= TREE_OPERAND (expr
, i
);
1357 se
= simplify_replace_tree (e
, old
, new_tree
);
1362 ret
= copy_node (expr
);
1364 TREE_OPERAND (ret
, i
) = se
;
1367 return (ret
? fold (ret
) : expr
);
1370 /* Expand definitions of ssa names in EXPR as long as they are simple
1371 enough, and return the new expression. */
1374 expand_simple_operations (tree expr
)
1377 tree ret
= NULL_TREE
, e
, ee
, stmt
;
1378 enum tree_code code
;
1380 if (expr
== NULL_TREE
)
1383 if (is_gimple_min_invariant (expr
))
1386 code
= TREE_CODE (expr
);
1387 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
1389 n
= TREE_OPERAND_LENGTH (expr
);
1390 for (i
= 0; i
< n
; i
++)
1392 e
= TREE_OPERAND (expr
, i
);
1393 ee
= expand_simple_operations (e
);
1398 ret
= copy_node (expr
);
1400 TREE_OPERAND (ret
, i
) = ee
;
1406 fold_defer_overflow_warnings ();
1408 fold_undefer_and_ignore_overflow_warnings ();
1412 if (TREE_CODE (expr
) != SSA_NAME
)
1415 stmt
= SSA_NAME_DEF_STMT (expr
);
1416 if (TREE_CODE (stmt
) == PHI_NODE
)
1418 basic_block src
, dest
;
1420 if (PHI_NUM_ARGS (stmt
) != 1)
1422 e
= PHI_ARG_DEF (stmt
, 0);
1424 /* Avoid propagating through loop exit phi nodes, which
1425 could break loop-closed SSA form restrictions. */
1426 dest
= bb_for_stmt (stmt
);
1427 src
= single_pred (dest
);
1428 if (TREE_CODE (e
) == SSA_NAME
1429 && src
->loop_father
!= dest
->loop_father
)
1432 return expand_simple_operations (e
);
1434 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
1437 e
= GIMPLE_STMT_OPERAND (stmt
, 1);
1438 if (/* Casts are simple. */
1439 TREE_CODE (e
) != NOP_EXPR
1440 && TREE_CODE (e
) != CONVERT_EXPR
1441 /* Copies are simple. */
1442 && TREE_CODE (e
) != SSA_NAME
1443 /* Assignments of invariants are simple. */
1444 && !is_gimple_min_invariant (e
)
1445 /* And increments and decrements by a constant are simple. */
1446 && !((TREE_CODE (e
) == PLUS_EXPR
1447 || TREE_CODE (e
) == MINUS_EXPR
1448 || TREE_CODE (e
) == POINTER_PLUS_EXPR
)
1449 && is_gimple_min_invariant (TREE_OPERAND (e
, 1))))
1452 return expand_simple_operations (e
);
1455 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1456 expression (or EXPR unchanged, if no simplification was possible). */
1459 tree_simplify_using_condition_1 (tree cond
, tree expr
)
1462 tree e
, te
, e0
, e1
, e2
, notcond
;
1463 enum tree_code code
= TREE_CODE (expr
);
1465 if (code
== INTEGER_CST
)
1468 if (code
== TRUTH_OR_EXPR
1469 || code
== TRUTH_AND_EXPR
1470 || code
== COND_EXPR
)
1474 e0
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 0));
1475 if (TREE_OPERAND (expr
, 0) != e0
)
1478 e1
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 1));
1479 if (TREE_OPERAND (expr
, 1) != e1
)
1482 if (code
== COND_EXPR
)
1484 e2
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 2));
1485 if (TREE_OPERAND (expr
, 2) != e2
)
1493 if (code
== COND_EXPR
)
1494 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1496 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1502 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
1503 propagation, and vice versa. Fold does not handle this, since it is
1504 considered too expensive. */
1505 if (TREE_CODE (cond
) == EQ_EXPR
)
1507 e0
= TREE_OPERAND (cond
, 0);
1508 e1
= TREE_OPERAND (cond
, 1);
1510 /* We know that e0 == e1. Check whether we cannot simplify expr
1512 e
= simplify_replace_tree (expr
, e0
, e1
);
1513 if (integer_zerop (e
) || integer_nonzerop (e
))
1516 e
= simplify_replace_tree (expr
, e1
, e0
);
1517 if (integer_zerop (e
) || integer_nonzerop (e
))
1520 if (TREE_CODE (expr
) == EQ_EXPR
)
1522 e0
= TREE_OPERAND (expr
, 0);
1523 e1
= TREE_OPERAND (expr
, 1);
1525 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
1526 e
= simplify_replace_tree (cond
, e0
, e1
);
1527 if (integer_zerop (e
))
1529 e
= simplify_replace_tree (cond
, e1
, e0
);
1530 if (integer_zerop (e
))
1533 if (TREE_CODE (expr
) == NE_EXPR
)
1535 e0
= TREE_OPERAND (expr
, 0);
1536 e1
= TREE_OPERAND (expr
, 1);
1538 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
1539 e
= simplify_replace_tree (cond
, e0
, e1
);
1540 if (integer_zerop (e
))
1541 return boolean_true_node
;
1542 e
= simplify_replace_tree (cond
, e1
, e0
);
1543 if (integer_zerop (e
))
1544 return boolean_true_node
;
1547 te
= expand_simple_operations (expr
);
1549 /* Check whether COND ==> EXPR. */
1550 notcond
= invert_truthvalue (cond
);
1551 e
= fold_binary (TRUTH_OR_EXPR
, boolean_type_node
, notcond
, te
);
1552 if (e
&& integer_nonzerop (e
))
1555 /* Check whether COND ==> not EXPR. */
1556 e
= fold_binary (TRUTH_AND_EXPR
, boolean_type_node
, cond
, te
);
1557 if (e
&& integer_zerop (e
))
1563 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1564 expression (or EXPR unchanged, if no simplification was possible).
1565 Wrapper around tree_simplify_using_condition_1 that ensures that chains
1566 of simple operations in definitions of ssa names in COND are expanded,
1567 so that things like casts or incrementing the value of the bound before
1568 the loop do not cause us to fail. */
1571 tree_simplify_using_condition (tree cond
, tree expr
)
1573 cond
= expand_simple_operations (cond
);
1575 return tree_simplify_using_condition_1 (cond
, expr
);
1578 /* Tries to simplify EXPR using the conditions on entry to LOOP.
1579 Returns the simplified expression (or EXPR unchanged, if no
1580 simplification was possible).*/
1583 simplify_using_initial_conditions (struct loop
*loop
, tree expr
)
1590 if (TREE_CODE (expr
) == INTEGER_CST
)
1593 /* Limit walking the dominators to avoid quadraticness in
1594 the number of BBs times the number of loops in degenerate
1596 for (bb
= loop
->header
;
1597 bb
!= ENTRY_BLOCK_PTR
&& cnt
< MAX_DOMINATORS_TO_WALK
;
1598 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1600 if (!single_pred_p (bb
))
1602 e
= single_pred_edge (bb
);
1604 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
1607 cond
= COND_EXPR_COND (last_stmt (e
->src
));
1608 if (e
->flags
& EDGE_FALSE_VALUE
)
1609 cond
= invert_truthvalue (cond
);
1610 expr
= tree_simplify_using_condition (cond
, expr
);
1617 /* Tries to simplify EXPR using the evolutions of the loop invariants
1618 in the superloops of LOOP. Returns the simplified expression
1619 (or EXPR unchanged, if no simplification was possible). */
1622 simplify_using_outer_evolutions (struct loop
*loop
, tree expr
)
1624 enum tree_code code
= TREE_CODE (expr
);
1628 if (is_gimple_min_invariant (expr
))
1631 if (code
== TRUTH_OR_EXPR
1632 || code
== TRUTH_AND_EXPR
1633 || code
== COND_EXPR
)
1637 e0
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 0));
1638 if (TREE_OPERAND (expr
, 0) != e0
)
1641 e1
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 1));
1642 if (TREE_OPERAND (expr
, 1) != e1
)
1645 if (code
== COND_EXPR
)
1647 e2
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 2));
1648 if (TREE_OPERAND (expr
, 2) != e2
)
1656 if (code
== COND_EXPR
)
1657 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1659 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1665 e
= instantiate_parameters (loop
, expr
);
1666 if (is_gimple_min_invariant (e
))
1672 /* Returns true if EXIT is the only possible exit from LOOP. */
1675 loop_only_exit_p (struct loop
*loop
, edge exit
)
1678 block_stmt_iterator bsi
;
1682 if (exit
!= single_exit (loop
))
1685 body
= get_loop_body (loop
);
1686 for (i
= 0; i
< loop
->num_nodes
; i
++)
1688 for (bsi
= bsi_start (body
[0]); !bsi_end_p (bsi
); bsi_next (&bsi
))
1690 call
= get_call_expr_in (bsi_stmt (bsi
));
1691 if (call
&& TREE_SIDE_EFFECTS (call
))
1703 /* Stores description of number of iterations of LOOP derived from
1704 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
1705 useful information could be derived (and fields of NITER has
1706 meaning described in comments at struct tree_niter_desc
1707 declaration), false otherwise. If WARN is true and
1708 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1709 potentially unsafe assumptions. */
1712 number_of_iterations_exit (struct loop
*loop
, edge exit
,
1713 struct tree_niter_desc
*niter
,
1716 tree stmt
, cond
, type
;
1718 enum tree_code code
;
1721 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit
->src
))
1724 niter
->assumptions
= boolean_false_node
;
1725 stmt
= last_stmt (exit
->src
);
1726 if (!stmt
|| TREE_CODE (stmt
) != COND_EXPR
)
1729 /* We want the condition for staying inside loop. */
1730 cond
= COND_EXPR_COND (stmt
);
1731 if (exit
->flags
& EDGE_TRUE_VALUE
)
1732 cond
= invert_truthvalue (cond
);
1734 code
= TREE_CODE (cond
);
1748 op0
= TREE_OPERAND (cond
, 0);
1749 op1
= TREE_OPERAND (cond
, 1);
1750 type
= TREE_TYPE (op0
);
1752 if (TREE_CODE (type
) != INTEGER_TYPE
1753 && !POINTER_TYPE_P (type
))
1756 if (!simple_iv (loop
, stmt
, op0
, &iv0
, false))
1758 if (!simple_iv (loop
, stmt
, op1
, &iv1
, false))
1761 /* We don't want to see undefined signed overflow warnings while
1762 computing the number of iterations. */
1763 fold_defer_overflow_warnings ();
1765 iv0
.base
= expand_simple_operations (iv0
.base
);
1766 iv1
.base
= expand_simple_operations (iv1
.base
);
1767 if (!number_of_iterations_cond (loop
, type
, &iv0
, code
, &iv1
, niter
,
1768 loop_only_exit_p (loop
, exit
)))
1770 fold_undefer_and_ignore_overflow_warnings ();
1776 niter
->assumptions
= simplify_using_outer_evolutions (loop
,
1777 niter
->assumptions
);
1778 niter
->may_be_zero
= simplify_using_outer_evolutions (loop
,
1779 niter
->may_be_zero
);
1780 niter
->niter
= simplify_using_outer_evolutions (loop
, niter
->niter
);
1784 = simplify_using_initial_conditions (loop
,
1785 niter
->assumptions
);
1787 = simplify_using_initial_conditions (loop
,
1788 niter
->may_be_zero
);
1790 fold_undefer_and_ignore_overflow_warnings ();
1792 if (integer_onep (niter
->assumptions
))
1795 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1796 But if we can prove that there is overflow or some other source of weird
1797 behavior, ignore the loop even with -funsafe-loop-optimizations. */
1798 if (integer_zerop (niter
->assumptions
))
1801 if (flag_unsafe_loop_optimizations
)
1802 niter
->assumptions
= boolean_true_node
;
1806 const char *wording
;
1807 location_t loc
= EXPR_LOCATION (stmt
);
1809 /* We can provide a more specific warning if one of the operator is
1810 constant and the other advances by +1 or -1. */
1811 if (!integer_zerop (iv1
.step
)
1812 ? (integer_zerop (iv0
.step
)
1813 && (integer_onep (iv1
.step
) || integer_all_onesp (iv1
.step
)))
1814 : (integer_onep (iv0
.step
) || integer_all_onesp (iv0
.step
)))
1816 flag_unsafe_loop_optimizations
1817 ? N_("assuming that the loop is not infinite")
1818 : N_("cannot optimize possibly infinite loops");
1821 flag_unsafe_loop_optimizations
1822 ? N_("assuming that the loop counter does not overflow")
1823 : N_("cannot optimize loop, the loop counter may overflow");
1825 if (LOCATION_LINE (loc
) > 0)
1826 warning (OPT_Wunsafe_loop_optimizations
, "%H%s", &loc
, gettext (wording
));
1828 warning (OPT_Wunsafe_loop_optimizations
, "%s", gettext (wording
));
1831 return flag_unsafe_loop_optimizations
;
1834 /* Try to determine the number of iterations of LOOP. If we succeed,
1835 expression giving number of iterations is returned and *EXIT is
1836 set to the edge from that the information is obtained. Otherwise
1837 chrec_dont_know is returned. */
1840 find_loop_niter (struct loop
*loop
, edge
*exit
)
1843 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
1845 tree niter
= NULL_TREE
, aniter
;
1846 struct tree_niter_desc desc
;
1849 for (i
= 0; VEC_iterate (edge
, exits
, i
, ex
); i
++)
1851 if (!just_once_each_iteration_p (loop
, ex
->src
))
1854 if (!number_of_iterations_exit (loop
, ex
, &desc
, false))
1857 if (integer_nonzerop (desc
.may_be_zero
))
1859 /* We exit in the first iteration through this exit.
1860 We won't find anything better. */
1861 niter
= build_int_cst (unsigned_type_node
, 0);
1866 if (!integer_zerop (desc
.may_be_zero
))
1869 aniter
= desc
.niter
;
1873 /* Nothing recorded yet. */
1879 /* Prefer constants, the lower the better. */
1880 if (TREE_CODE (aniter
) != INTEGER_CST
)
1883 if (TREE_CODE (niter
) != INTEGER_CST
)
1890 if (tree_int_cst_lt (aniter
, niter
))
1897 VEC_free (edge
, heap
, exits
);
1899 return niter
? niter
: chrec_dont_know
;
1904 Analysis of a number of iterations of a loop by a brute-force evaluation.
1908 /* Bound on the number of iterations we try to evaluate. */
1910 #define MAX_ITERATIONS_TO_TRACK \
1911 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
1913 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
1914 result by a chain of operations such that all but exactly one of their
1915 operands are constants. */
1918 chain_of_csts_start (struct loop
*loop
, tree x
)
1920 tree stmt
= SSA_NAME_DEF_STMT (x
);
1922 basic_block bb
= bb_for_stmt (stmt
);
1925 || !flow_bb_inside_loop_p (loop
, bb
))
1928 if (TREE_CODE (stmt
) == PHI_NODE
)
1930 if (bb
== loop
->header
)
1936 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
1939 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
1941 if (SINGLE_SSA_DEF_OPERAND (stmt
, SSA_OP_DEF
) == NULL_DEF_OPERAND_P
)
1944 use
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1945 if (use
== NULL_USE_OPERAND_P
)
1948 return chain_of_csts_start (loop
, use
);
1951 /* Determines whether the expression X is derived from a result of a phi node
1952 in header of LOOP such that
1954 * the derivation of X consists only from operations with constants
1955 * the initial value of the phi node is constant
1956 * the value of the phi node in the next iteration can be derived from the
1957 value in the current iteration by a chain of operations with constants.
1959 If such phi node exists, it is returned. If X is a constant, X is returned
1960 unchanged. Otherwise NULL_TREE is returned. */
1963 get_base_for (struct loop
*loop
, tree x
)
1965 tree phi
, init
, next
;
1967 if (is_gimple_min_invariant (x
))
1970 phi
= chain_of_csts_start (loop
, x
);
1974 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
1975 next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
1977 if (TREE_CODE (next
) != SSA_NAME
)
1980 if (!is_gimple_min_invariant (init
))
1983 if (chain_of_csts_start (loop
, next
) != phi
)
1989 /* Given an expression X, then
1991 * if X is NULL_TREE, we return the constant BASE.
1992 * otherwise X is a SSA name, whose value in the considered loop is derived
1993 by a chain of operations with constant from a result of a phi node in
1994 the header of the loop. Then we return value of X when the value of the
1995 result of this phi node is given by the constant BASE. */
1998 get_val_for (tree x
, tree base
)
2004 gcc_assert (is_gimple_min_invariant (base
));
2009 stmt
= SSA_NAME_DEF_STMT (x
);
2010 if (TREE_CODE (stmt
) == PHI_NODE
)
2013 FOR_EACH_SSA_USE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
2015 nx
= USE_FROM_PTR (op
);
2016 val
= get_val_for (nx
, base
);
2018 val
= fold (GIMPLE_STMT_OPERAND (stmt
, 1));
2020 /* only iterate loop once. */
2024 /* Should never reach here. */
2028 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2029 by brute force -- i.e. by determining the value of the operands of the
2030 condition at EXIT in first few iterations of the loop (assuming that
2031 these values are constant) and determining the first one in that the
2032 condition is not satisfied. Returns the constant giving the number
2033 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
2036 loop_niter_by_eval (struct loop
*loop
, edge exit
)
2038 tree cond
, cnd
, acnd
;
2039 tree op
[2], val
[2], next
[2], aval
[2], phi
[2];
2043 cond
= last_stmt (exit
->src
);
2044 if (!cond
|| TREE_CODE (cond
) != COND_EXPR
)
2045 return chrec_dont_know
;
2047 cnd
= COND_EXPR_COND (cond
);
2048 if (exit
->flags
& EDGE_TRUE_VALUE
)
2049 cnd
= invert_truthvalue (cnd
);
2051 cmp
= TREE_CODE (cnd
);
2060 for (j
= 0; j
< 2; j
++)
2061 op
[j
] = TREE_OPERAND (cnd
, j
);
2065 return chrec_dont_know
;
2068 for (j
= 0; j
< 2; j
++)
2070 phi
[j
] = get_base_for (loop
, op
[j
]);
2072 return chrec_dont_know
;
2075 for (j
= 0; j
< 2; j
++)
2077 if (TREE_CODE (phi
[j
]) == PHI_NODE
)
2079 val
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
[j
], loop_preheader_edge (loop
));
2080 next
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
[j
], loop_latch_edge (loop
));
2085 next
[j
] = NULL_TREE
;
2090 /* Don't issue signed overflow warnings. */
2091 fold_defer_overflow_warnings ();
2093 for (i
= 0; i
< MAX_ITERATIONS_TO_TRACK
; i
++)
2095 for (j
= 0; j
< 2; j
++)
2096 aval
[j
] = get_val_for (op
[j
], val
[j
]);
2098 acnd
= fold_binary (cmp
, boolean_type_node
, aval
[0], aval
[1]);
2099 if (acnd
&& integer_zerop (acnd
))
2101 fold_undefer_and_ignore_overflow_warnings ();
2102 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2104 "Proved that loop %d iterates %d times using brute force.\n",
2106 return build_int_cst (unsigned_type_node
, i
);
2109 for (j
= 0; j
< 2; j
++)
2111 val
[j
] = get_val_for (next
[j
], val
[j
]);
2112 if (!is_gimple_min_invariant (val
[j
]))
2114 fold_undefer_and_ignore_overflow_warnings ();
2115 return chrec_dont_know
;
2120 fold_undefer_and_ignore_overflow_warnings ();
2122 return chrec_dont_know
;
2125 /* Finds the exit of the LOOP by that the loop exits after a constant
2126 number of iterations and stores the exit edge to *EXIT. The constant
2127 giving the number of iterations of LOOP is returned. The number of
2128 iterations is determined using loop_niter_by_eval (i.e. by brute force
2129 evaluation). If we are unable to find the exit for that loop_niter_by_eval
2130 determines the number of iterations, chrec_dont_know is returned. */
2133 find_loop_niter_by_eval (struct loop
*loop
, edge
*exit
)
2136 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
2138 tree niter
= NULL_TREE
, aniter
;
2141 for (i
= 0; VEC_iterate (edge
, exits
, i
, ex
); i
++)
2143 if (!just_once_each_iteration_p (loop
, ex
->src
))
2146 aniter
= loop_niter_by_eval (loop
, ex
);
2147 if (chrec_contains_undetermined (aniter
))
2151 && !tree_int_cst_lt (aniter
, niter
))
2157 VEC_free (edge
, heap
, exits
);
2159 return niter
? niter
: chrec_dont_know
;
2164 Analysis of upper bounds on number of iterations of a loop.
2168 /* Returns a constant upper bound on the value of expression VAL. VAL
2169 is considered to be unsigned. If its type is signed, its value must
2173 derive_constant_upper_bound (tree val
)
2175 tree type
= TREE_TYPE (val
);
2176 tree op0
, op1
, subtype
, maxt
;
2177 double_int bnd
, max
, mmax
, cst
;
2180 if (INTEGRAL_TYPE_P (type
))
2181 maxt
= TYPE_MAX_VALUE (type
);
2183 maxt
= upper_bound_in_type (type
, type
);
2185 max
= tree_to_double_int (maxt
);
2187 switch (TREE_CODE (val
))
2190 return tree_to_double_int (val
);
2194 op0
= TREE_OPERAND (val
, 0);
2195 subtype
= TREE_TYPE (op0
);
2196 if (!TYPE_UNSIGNED (subtype
)
2197 /* If TYPE is also signed, the fact that VAL is nonnegative implies
2198 that OP0 is nonnegative. */
2199 && TYPE_UNSIGNED (type
)
2200 && !tree_expr_nonnegative_p (op0
))
2202 /* If we cannot prove that the casted expression is nonnegative,
2203 we cannot establish more useful upper bound than the precision
2204 of the type gives us. */
2208 /* We now know that op0 is an nonnegative value. Try deriving an upper
2210 bnd
= derive_constant_upper_bound (op0
);
2212 /* If the bound does not fit in TYPE, max. value of TYPE could be
2214 if (double_int_ucmp (max
, bnd
) < 0)
2220 case POINTER_PLUS_EXPR
:
2222 op0
= TREE_OPERAND (val
, 0);
2223 op1
= TREE_OPERAND (val
, 1);
2225 if (TREE_CODE (op1
) != INTEGER_CST
2226 || !tree_expr_nonnegative_p (op0
))
2229 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
2230 choose the most logical way how to treat this constant regardless
2231 of the signedness of the type. */
2232 cst
= tree_to_double_int (op1
);
2233 cst
= double_int_sext (cst
, TYPE_PRECISION (type
));
2234 if (TREE_CODE (val
) == PLUS_EXPR
)
2235 cst
= double_int_neg (cst
);
2237 bnd
= derive_constant_upper_bound (op0
);
2239 if (double_int_negative_p (cst
))
2241 cst
= double_int_neg (cst
);
2242 /* Avoid CST == 0x80000... */
2243 if (double_int_negative_p (cst
))
2246 /* OP0 + CST. We need to check that
2247 BND <= MAX (type) - CST. */
2249 mmax
= double_int_add (max
, double_int_neg (cst
));
2250 if (double_int_ucmp (bnd
, mmax
) > 0)
2253 return double_int_add (bnd
, cst
);
2257 /* OP0 - CST, where CST >= 0.
2259 If TYPE is signed, we have already verified that OP0 >= 0, and we
2260 know that the result is nonnegative. This implies that
2263 If TYPE is unsigned, we must additionally know that OP0 >= CST,
2264 otherwise the operation underflows.
2267 /* This should only happen if the type is unsigned; however, for
2268 buggy programs that use overflowing signed arithmetics even with
2269 -fno-wrapv, this condition may also be true for signed values. */
2270 if (double_int_ucmp (bnd
, cst
) < 0)
2273 if (TYPE_UNSIGNED (type
))
2275 tree tem
= fold_binary (GE_EXPR
, boolean_type_node
, op0
,
2276 double_int_to_tree (type
, cst
));
2277 if (!tem
|| integer_nonzerop (tem
))
2281 bnd
= double_int_add (bnd
, double_int_neg (cst
));
2286 case FLOOR_DIV_EXPR
:
2287 case EXACT_DIV_EXPR
:
2288 op0
= TREE_OPERAND (val
, 0);
2289 op1
= TREE_OPERAND (val
, 1);
2290 if (TREE_CODE (op1
) != INTEGER_CST
2291 || tree_int_cst_sign_bit (op1
))
2294 bnd
= derive_constant_upper_bound (op0
);
2295 return double_int_udiv (bnd
, tree_to_double_int (op1
), FLOOR_DIV_EXPR
);
2298 op1
= TREE_OPERAND (val
, 1);
2299 if (TREE_CODE (op1
) != INTEGER_CST
2300 || tree_int_cst_sign_bit (op1
))
2302 return tree_to_double_int (op1
);
2305 stmt
= SSA_NAME_DEF_STMT (val
);
2306 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
2307 || GIMPLE_STMT_OPERAND (stmt
, 0) != val
)
2309 return derive_constant_upper_bound (GIMPLE_STMT_OPERAND (stmt
, 1));
2316 /* Records that every statement in LOOP is executed I_BOUND times.
2317 REALISTIC is true if I_BOUND is expected to be close the the real number
2318 of iterations. UPPER is true if we are sure the loop iterates at most
2322 record_niter_bound (struct loop
*loop
, double_int i_bound
, bool realistic
,
2325 /* Update the bounds only when there is no previous estimation, or when the current
2326 estimation is smaller. */
2328 && (!loop
->any_upper_bound
2329 || double_int_ucmp (i_bound
, loop
->nb_iterations_upper_bound
) < 0))
2331 loop
->any_upper_bound
= true;
2332 loop
->nb_iterations_upper_bound
= i_bound
;
2335 && (!loop
->any_estimate
2336 || double_int_ucmp (i_bound
, loop
->nb_iterations_estimate
) < 0))
2338 loop
->any_estimate
= true;
2339 loop
->nb_iterations_estimate
= i_bound
;
2343 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
2344 is true if the loop is exited immediately after STMT, and this exit
2345 is taken at last when the STMT is executed BOUND + 1 times.
2346 REALISTIC is true if BOUND is expected to be close the the real number
2347 of iterations. UPPER is true if we are sure the loop iterates at most
2348 BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */
2351 record_estimate (struct loop
*loop
, tree bound
, double_int i_bound
,
2352 tree at_stmt
, bool is_exit
, bool realistic
, bool upper
)
2357 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2359 fprintf (dump_file
, "Statement %s", is_exit
? "(exit)" : "");
2360 print_generic_expr (dump_file
, at_stmt
, TDF_SLIM
);
2361 fprintf (dump_file
, " is %sexecuted at most ",
2362 upper
? "" : "probably ");
2363 print_generic_expr (dump_file
, bound
, TDF_SLIM
);
2364 fprintf (dump_file
, " (bounded by ");
2365 dump_double_int (dump_file
, i_bound
, true);
2366 fprintf (dump_file
, ") + 1 times in loop %d.\n", loop
->num
);
2369 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
2370 real number of iterations. */
2371 if (TREE_CODE (bound
) != INTEGER_CST
)
2373 if (!upper
&& !realistic
)
2376 /* If we have a guaranteed upper bound, record it in the appropriate
2380 struct nb_iter_bound
*elt
= GGC_NEW (struct nb_iter_bound
);
2382 elt
->bound
= i_bound
;
2383 elt
->stmt
= at_stmt
;
2384 elt
->is_exit
= is_exit
;
2385 elt
->next
= loop
->bounds
;
2389 /* Update the number of iteration estimates according to the bound.
2390 If at_stmt is an exit, then every statement in the loop is
2391 executed at most BOUND + 1 times. If it is not an exit, then
2392 some of the statements before it could be executed BOUND + 2
2393 times, if an exit of LOOP is before stmt. */
2394 exit
= single_exit (loop
);
2397 && dominated_by_p (CDI_DOMINATORS
,
2398 exit
->src
, bb_for_stmt (at_stmt
))))
2399 delta
= double_int_one
;
2401 delta
= double_int_two
;
2402 i_bound
= double_int_add (i_bound
, delta
);
2404 /* If an overflow occurred, ignore the result. */
2405 if (double_int_ucmp (i_bound
, delta
) < 0)
2408 record_niter_bound (loop
, i_bound
, realistic
, upper
);
2411 /* Record the estimate on number of iterations of LOOP based on the fact that
2412 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
2413 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
2414 estimated number of iterations is expected to be close to the real one.
2415 UPPER is true if we are sure the induction variable does not wrap. */
2418 record_nonwrapping_iv (struct loop
*loop
, tree base
, tree step
, tree stmt
,
2419 tree low
, tree high
, bool realistic
, bool upper
)
2421 tree niter_bound
, extreme
, delta
;
2422 tree type
= TREE_TYPE (base
), unsigned_type
;
2425 if (TREE_CODE (step
) != INTEGER_CST
|| integer_zerop (step
))
2428 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2430 fprintf (dump_file
, "Induction variable (");
2431 print_generic_expr (dump_file
, TREE_TYPE (base
), TDF_SLIM
);
2432 fprintf (dump_file
, ") ");
2433 print_generic_expr (dump_file
, base
, TDF_SLIM
);
2434 fprintf (dump_file
, " + ");
2435 print_generic_expr (dump_file
, step
, TDF_SLIM
);
2436 fprintf (dump_file
, " * iteration does not wrap in statement ");
2437 print_generic_expr (dump_file
, stmt
, TDF_SLIM
);
2438 fprintf (dump_file
, " in loop %d.\n", loop
->num
);
2441 unsigned_type
= unsigned_type_for (type
);
2442 base
= fold_convert (unsigned_type
, base
);
2443 step
= fold_convert (unsigned_type
, step
);
2445 if (tree_int_cst_sign_bit (step
))
2447 extreme
= fold_convert (unsigned_type
, low
);
2448 if (TREE_CODE (base
) != INTEGER_CST
)
2449 base
= fold_convert (unsigned_type
, high
);
2450 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
2451 step
= fold_build1 (NEGATE_EXPR
, unsigned_type
, step
);
2455 extreme
= fold_convert (unsigned_type
, high
);
2456 if (TREE_CODE (base
) != INTEGER_CST
)
2457 base
= fold_convert (unsigned_type
, low
);
2458 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
2461 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
2462 would get out of the range. */
2463 niter_bound
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step
);
2464 max
= derive_constant_upper_bound (niter_bound
);
2465 record_estimate (loop
, niter_bound
, max
, stmt
, false, realistic
, upper
);
2468 /* Returns true if REF is a reference to an array at the end of a dynamically
2469 allocated structure. If this is the case, the array may be allocated larger
2470 than its upper bound implies. */
2473 array_at_struct_end_p (tree ref
)
2475 tree base
= get_base_address (ref
);
2478 /* Unless the reference is through a pointer, the size of the array matches
2480 if (!base
|| !INDIRECT_REF_P (base
))
2483 for (;handled_component_p (ref
); ref
= parent
)
2485 parent
= TREE_OPERAND (ref
, 0);
2487 if (TREE_CODE (ref
) == COMPONENT_REF
)
2489 /* All fields of a union are at its end. */
2490 if (TREE_CODE (TREE_TYPE (parent
)) == UNION_TYPE
)
2493 /* Unless the field is at the end of the struct, we are done. */
2494 field
= TREE_OPERAND (ref
, 1);
2495 if (TREE_CHAIN (field
))
2499 /* The other options are ARRAY_REF, ARRAY_RANGE_REF, VIEW_CONVERT_EXPR.
2500 In all these cases, we might be accessing the last element, and
2501 although in practice this will probably never happen, it is legal for
2502 the indices of this last element to exceed the bounds of the array.
2503 Therefore, continue checking. */
2506 gcc_assert (INDIRECT_REF_P (ref
));
2510 /* Determine information about number of iterations a LOOP from the index
2511 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
2512 guaranteed to be executed in every iteration of LOOP. Callback for
2523 idx_infer_loop_bounds (tree base
, tree
*idx
, void *dta
)
2525 struct ilb_data
*data
= (struct ilb_data
*) dta
;
2526 tree ev
, init
, step
;
2527 tree low
, high
, type
, next
;
2528 bool sign
, upper
= data
->reliable
, at_end
= false;
2529 struct loop
*loop
= data
->loop
;
2531 if (TREE_CODE (base
) != ARRAY_REF
)
2534 /* For arrays at the end of the structure, we are not guaranteed that they
2535 do not really extend over their declared size. However, for arrays of
2536 size greater than one, this is unlikely to be intended. */
2537 if (array_at_struct_end_p (base
))
2543 ev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, *idx
));
2544 init
= initial_condition (ev
);
2545 step
= evolution_part_in_loop_num (ev
, loop
->num
);
2549 || TREE_CODE (step
) != INTEGER_CST
2550 || integer_zerop (step
)
2551 || tree_contains_chrecs (init
, NULL
)
2552 || chrec_contains_symbols_defined_in_loop (init
, loop
->num
))
2555 low
= array_ref_low_bound (base
);
2556 high
= array_ref_up_bound (base
);
2558 /* The case of nonconstant bounds could be handled, but it would be
2560 if (TREE_CODE (low
) != INTEGER_CST
2562 || TREE_CODE (high
) != INTEGER_CST
)
2564 sign
= tree_int_cst_sign_bit (step
);
2565 type
= TREE_TYPE (step
);
2567 /* The array of length 1 at the end of a structure most likely extends
2568 beyond its bounds. */
2570 && operand_equal_p (low
, high
, 0))
2573 /* In case the relevant bound of the array does not fit in type, or
2574 it does, but bound + step (in type) still belongs into the range of the
2575 array, the index may wrap and still stay within the range of the array
2576 (consider e.g. if the array is indexed by the full range of
2579 To make things simpler, we require both bounds to fit into type, although
2580 there are cases where this would not be strictly necessary. */
2581 if (!int_fits_type_p (high
, type
)
2582 || !int_fits_type_p (low
, type
))
2584 low
= fold_convert (type
, low
);
2585 high
= fold_convert (type
, high
);
2588 next
= fold_binary (PLUS_EXPR
, type
, low
, step
);
2590 next
= fold_binary (PLUS_EXPR
, type
, high
, step
);
2592 if (tree_int_cst_compare (low
, next
) <= 0
2593 && tree_int_cst_compare (next
, high
) <= 0)
2596 record_nonwrapping_iv (loop
, init
, step
, data
->stmt
, low
, high
, true, upper
);
2600 /* Determine information about number of iterations a LOOP from the bounds
2601 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
2602 STMT is guaranteed to be executed in every iteration of LOOP.*/
2605 infer_loop_bounds_from_ref (struct loop
*loop
, tree stmt
, tree ref
,
2608 struct ilb_data data
;
2612 data
.reliable
= reliable
;
2613 for_each_index (&ref
, idx_infer_loop_bounds
, &data
);
2616 /* Determine information about number of iterations of a LOOP from the way
2617 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
2618 executed in every iteration of LOOP. */
2621 infer_loop_bounds_from_array (struct loop
*loop
, tree stmt
, bool reliable
)
2625 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
2627 tree op0
= GIMPLE_STMT_OPERAND (stmt
, 0);
2628 tree op1
= GIMPLE_STMT_OPERAND (stmt
, 1);
2630 /* For each memory access, analyze its access function
2631 and record a bound on the loop iteration domain. */
2632 if (REFERENCE_CLASS_P (op0
))
2633 infer_loop_bounds_from_ref (loop
, stmt
, op0
, reliable
);
2635 if (REFERENCE_CLASS_P (op1
))
2636 infer_loop_bounds_from_ref (loop
, stmt
, op1
, reliable
);
2640 call
= get_call_expr_in (stmt
);
2644 call_expr_arg_iterator iter
;
2646 FOR_EACH_CALL_EXPR_ARG (arg
, iter
, call
)
2647 if (REFERENCE_CLASS_P (arg
))
2648 infer_loop_bounds_from_ref (loop
, stmt
, arg
, reliable
);
2652 /* Determine information about number of iterations of a LOOP from the fact
2653 that signed arithmetics in STMT does not overflow. */
2656 infer_loop_bounds_from_signedness (struct loop
*loop
, tree stmt
)
2658 tree def
, base
, step
, scev
, type
, low
, high
;
2660 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
2663 def
= GIMPLE_STMT_OPERAND (stmt
, 0);
2665 if (TREE_CODE (def
) != SSA_NAME
)
2668 type
= TREE_TYPE (def
);
2669 if (!INTEGRAL_TYPE_P (type
)
2670 || !TYPE_OVERFLOW_UNDEFINED (type
))
2673 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
2674 if (chrec_contains_undetermined (scev
))
2677 base
= initial_condition_in_loop_num (scev
, loop
->num
);
2678 step
= evolution_part_in_loop_num (scev
, loop
->num
);
2681 || TREE_CODE (step
) != INTEGER_CST
2682 || tree_contains_chrecs (base
, NULL
)
2683 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
2686 low
= lower_bound_in_type (type
, type
);
2687 high
= upper_bound_in_type (type
, type
);
2689 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
2692 /* The following analyzers are extracting informations on the bounds
2693 of LOOP from the following undefined behaviors:
2695 - data references should not access elements over the statically
2698 - signed variables should not overflow when flag_wrapv is not set.
2702 infer_loop_bounds_from_undefined (struct loop
*loop
)
2706 block_stmt_iterator bsi
;
2710 bbs
= get_loop_body (loop
);
2712 for (i
= 0; i
< loop
->num_nodes
; i
++)
2716 /* If BB is not executed in each iteration of the loop, we cannot
2717 use the operations in it to infer reliable upper bound on the
2718 # of iterations of the loop. However, we can use it as a guess. */
2719 reliable
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
);
2721 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
2723 tree stmt
= bsi_stmt (bsi
);
2725 infer_loop_bounds_from_array (loop
, stmt
, reliable
);
2728 infer_loop_bounds_from_signedness (loop
, stmt
);
2736 /* Converts VAL to double_int. */
2739 gcov_type_to_double_int (gcov_type val
)
2743 ret
.low
= (unsigned HOST_WIDE_INT
) val
;
2744 /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by
2745 the size of type. */
2746 val
>>= HOST_BITS_PER_WIDE_INT
- 1;
2748 ret
.high
= (unsigned HOST_WIDE_INT
) val
;
2753 /* Records estimates on numbers of iterations of LOOP. */
2756 estimate_numbers_of_iterations_loop (struct loop
*loop
)
2758 VEC (edge
, heap
) *exits
;
2761 struct tree_niter_desc niter_desc
;
2765 /* Give up if we already have tried to compute an estimation. */
2766 if (loop
->estimate_state
!= EST_NOT_COMPUTED
)
2768 loop
->estimate_state
= EST_AVAILABLE
;
2769 loop
->any_upper_bound
= false;
2770 loop
->any_estimate
= false;
2772 exits
= get_loop_exit_edges (loop
);
2773 for (i
= 0; VEC_iterate (edge
, exits
, i
, ex
); i
++)
2775 if (!number_of_iterations_exit (loop
, ex
, &niter_desc
, false))
2778 niter
= niter_desc
.niter
;
2779 type
= TREE_TYPE (niter
);
2780 if (TREE_CODE (niter_desc
.may_be_zero
) != INTEGER_CST
)
2781 niter
= build3 (COND_EXPR
, type
, niter_desc
.may_be_zero
,
2782 build_int_cst (type
, 0),
2784 record_estimate (loop
, niter
, niter_desc
.max
,
2785 last_stmt (ex
->src
),
2788 VEC_free (edge
, heap
, exits
);
2790 infer_loop_bounds_from_undefined (loop
);
2792 /* If we have a measured profile, use it to estimate the number of
2794 if (loop
->header
->count
!= 0)
2796 gcov_type nit
= expected_loop_iterations_unbounded (loop
) + 1;
2797 bound
= gcov_type_to_double_int (nit
);
2798 record_niter_bound (loop
, bound
, true, false);
2801 /* If an upper bound is smaller than the realistic estimate of the
2802 number of iterations, use the upper bound instead. */
2803 if (loop
->any_upper_bound
2804 && loop
->any_estimate
2805 && double_int_ucmp (loop
->nb_iterations_upper_bound
,
2806 loop
->nb_iterations_estimate
) < 0)
2807 loop
->nb_iterations_estimate
= loop
->nb_iterations_upper_bound
;
2810 /* Records estimates on numbers of iterations of loops. */
2813 estimate_numbers_of_iterations (void)
2818 /* We don't want to issue signed overflow warnings while getting
2819 loop iteration estimates. */
2820 fold_defer_overflow_warnings ();
2822 FOR_EACH_LOOP (li
, loop
, 0)
2824 estimate_numbers_of_iterations_loop (loop
);
2827 fold_undefer_and_ignore_overflow_warnings ();
2830 /* Returns true if statement S1 dominates statement S2. */
2833 stmt_dominates_stmt_p (tree s1
, tree s2
)
2835 basic_block bb1
= bb_for_stmt (s1
), bb2
= bb_for_stmt (s2
);
2843 block_stmt_iterator bsi
;
2845 for (bsi
= bsi_start (bb1
); bsi_stmt (bsi
) != s2
; bsi_next (&bsi
))
2846 if (bsi_stmt (bsi
) == s1
)
2852 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
2855 /* Returns true when we can prove that the number of executions of
2856 STMT in the loop is at most NITER, according to the bound on
2857 the number of executions of the statement NITER_BOUND->stmt recorded in
2858 NITER_BOUND. If STMT is NULL, we must prove this bound for all
2859 statements in the loop. */
2862 n_of_executions_at_most (tree stmt
,
2863 struct nb_iter_bound
*niter_bound
,
2866 double_int bound
= niter_bound
->bound
;
2867 tree nit_type
= TREE_TYPE (niter
), e
;
2870 gcc_assert (TYPE_UNSIGNED (nit_type
));
2872 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
2873 the number of iterations is small. */
2874 if (!double_int_fits_to_tree_p (nit_type
, bound
))
2877 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
2878 times. This means that:
2880 -- if NITER_BOUND->is_exit is true, then everything before
2881 NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
2882 times, and everything after it at most NITER_BOUND->bound times.
2884 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
2885 is executed, then NITER_BOUND->stmt is executed as well in the same
2886 iteration (we conclude that if both statements belong to the same
2887 basic block, or if STMT is after NITER_BOUND->stmt), then STMT
2888 is executed at most NITER_BOUND->bound + 1 times. Otherwise STMT is
2889 executed at most NITER_BOUND->bound + 2 times. */
2891 if (niter_bound
->is_exit
)
2894 && stmt
!= niter_bound
->stmt
2895 && stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
2903 || (bb_for_stmt (stmt
) != bb_for_stmt (niter_bound
->stmt
)
2904 && !stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
)))
2906 bound
= double_int_add (bound
, double_int_one
);
2907 if (double_int_zero_p (bound
)
2908 || !double_int_fits_to_tree_p (nit_type
, bound
))
2914 e
= fold_binary (cmp
, boolean_type_node
,
2915 niter
, double_int_to_tree (nit_type
, bound
));
2916 return e
&& integer_nonzerop (e
);
2919 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
2922 nowrap_type_p (tree type
)
2924 if (INTEGRAL_TYPE_P (type
)
2925 && TYPE_OVERFLOW_UNDEFINED (type
))
2928 if (POINTER_TYPE_P (type
))
2934 /* Return false only when the induction variable BASE + STEP * I is
2935 known to not overflow: i.e. when the number of iterations is small
2936 enough with respect to the step and initial condition in order to
2937 keep the evolution confined in TYPEs bounds. Return true when the
2938 iv is known to overflow or when the property is not computable.
2940 USE_OVERFLOW_SEMANTICS is true if this function should assume that
2941 the rules for overflow of the given language apply (e.g., that signed
2942 arithmetics in C does not overflow). */
2945 scev_probably_wraps_p (tree base
, tree step
,
2946 tree at_stmt
, struct loop
*loop
,
2947 bool use_overflow_semantics
)
2949 struct nb_iter_bound
*bound
;
2950 tree delta
, step_abs
;
2951 tree unsigned_type
, valid_niter
;
2952 tree type
= TREE_TYPE (step
);
2954 /* FIXME: We really need something like
2955 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
2957 We used to test for the following situation that frequently appears
2958 during address arithmetics:
2960 D.1621_13 = (long unsigned intD.4) D.1620_12;
2961 D.1622_14 = D.1621_13 * 8;
2962 D.1623_15 = (doubleD.29 *) D.1622_14;
2964 And derived that the sequence corresponding to D_14
2965 can be proved to not wrap because it is used for computing a
2966 memory access; however, this is not really the case -- for example,
2967 if D_12 = (unsigned char) [254,+,1], then D_14 has values
2968 2032, 2040, 0, 8, ..., but the code is still legal. */
2970 if (chrec_contains_undetermined (base
)
2971 || chrec_contains_undetermined (step
)
2972 || TREE_CODE (step
) != INTEGER_CST
)
2975 if (integer_zerop (step
))
2978 /* If we can use the fact that signed and pointer arithmetics does not
2979 wrap, we are done. */
2980 if (use_overflow_semantics
&& nowrap_type_p (type
))
2983 /* Don't issue signed overflow warnings. */
2984 fold_defer_overflow_warnings ();
2986 /* Otherwise, compute the number of iterations before we reach the
2987 bound of the type, and verify that the loop is exited before this
2989 unsigned_type
= unsigned_type_for (type
);
2990 base
= fold_convert (unsigned_type
, base
);
2992 if (tree_int_cst_sign_bit (step
))
2994 tree extreme
= fold_convert (unsigned_type
,
2995 lower_bound_in_type (type
, type
));
2996 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
2997 step_abs
= fold_build1 (NEGATE_EXPR
, unsigned_type
,
2998 fold_convert (unsigned_type
, step
));
3002 tree extreme
= fold_convert (unsigned_type
,
3003 upper_bound_in_type (type
, type
));
3004 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
3005 step_abs
= fold_convert (unsigned_type
, step
);
3008 valid_niter
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step_abs
);
3010 estimate_numbers_of_iterations_loop (loop
);
3011 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
3013 if (n_of_executions_at_most (at_stmt
, bound
, valid_niter
))
3015 fold_undefer_and_ignore_overflow_warnings ();
3020 fold_undefer_and_ignore_overflow_warnings ();
3022 /* At this point we still don't have a proof that the iv does not
3023 overflow: give up. */
3027 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
3030 free_numbers_of_iterations_estimates_loop (struct loop
*loop
)
3032 struct nb_iter_bound
*bound
, *next
;
3034 loop
->nb_iterations
= NULL
;
3035 loop
->estimate_state
= EST_NOT_COMPUTED
;
3036 for (bound
= loop
->bounds
; bound
; bound
= next
)
3042 loop
->bounds
= NULL
;
3045 /* Frees the information on upper bounds on numbers of iterations of loops. */
3048 free_numbers_of_iterations_estimates (void)
3053 FOR_EACH_LOOP (li
, loop
, 0)
3055 free_numbers_of_iterations_estimates_loop (loop
);
3059 /* Substitute value VAL for ssa name NAME inside expressions held
3063 substitute_in_loop_info (struct loop
*loop
, tree name
, tree val
)
3065 loop
->nb_iterations
= simplify_replace_tree (loop
->nb_iterations
, name
, val
);