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 { void *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. */
67 /* Sets RESULT to VAL, taken unsigned if UNS is true and as signed
71 mpz_set_double_int (mpz_t result
, double_int val
, bool uns
)
74 unsigned HOST_WIDE_INT vp
[2];
76 if (!uns
&& double_int_negative_p (val
))
79 val
= double_int_neg (val
);
83 vp
[1] = (unsigned HOST_WIDE_INT
) val
.high
;
84 mpz_import (result
, 2, -1, sizeof (HOST_WIDE_INT
), 0, 0, vp
);
87 mpz_neg (result
, result
);
90 /* Stores bounds of TYPE to MIN and MAX. */
93 get_type_bounds (tree type
, mpz_t min
, mpz_t max
)
95 if (TYPE_UNSIGNED (type
))
98 mpz_set_double_int (max
, double_int_mask (TYPE_PRECISION (type
)), true);
104 mx
= double_int_mask (TYPE_PRECISION (type
) - 1);
105 mn
= double_int_sext (double_int_add (mx
, double_int_one
),
106 TYPE_PRECISION (type
));
107 mpz_set_double_int (max
, mx
, true);
108 mpz_set_double_int (min
, mn
, false);
112 /* Returns VAL converted to TYPE. If VAL does not fit in TYPE,
113 the minimum or maximum value of the type is returned instead. */
116 mpz_to_double_int (tree type
, mpz_t val
)
119 unsigned HOST_WIDE_INT vp
[2];
126 get_type_bounds (type
, min
, max
);
128 if (mpz_cmp (val
, min
) < 0)
130 else if (mpz_cmp (val
, max
) > 0)
133 if (mpz_sgn (val
) < 0)
138 mpz_export (vp
, &count
, -1, sizeof (HOST_WIDE_INT
), 0, 0, val
);
139 gcc_assert (count
<= 2);
145 res
.high
= (HOST_WIDE_INT
) vp
[1];
147 res
= double_int_ext (res
, TYPE_PRECISION (type
), TYPE_UNSIGNED (type
));
149 res
= double_int_neg (res
);
154 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */
157 split_to_var_and_offset (tree expr
, tree
*var
, mpz_t offset
)
159 tree type
= TREE_TYPE (expr
);
165 mpz_set_ui (offset
, 0);
167 switch (TREE_CODE (expr
))
174 op0
= TREE_OPERAND (expr
, 0);
175 op1
= TREE_OPERAND (expr
, 1);
177 if (TREE_CODE (op1
) != INTEGER_CST
)
181 /* Always sign extend the offset. */
182 off
= double_int_sext (tree_to_double_int (op1
),
183 TYPE_PRECISION (type
));
184 mpz_set_double_int (offset
, off
, false);
188 *var
= build_int_cst_type (type
, 0);
189 off
= tree_to_double_int (expr
);
190 mpz_set_double_int (offset
, off
, TYPE_UNSIGNED (type
));
198 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
199 in TYPE to MIN and MAX. */
202 determine_value_range (tree type
, tree var
, mpz_t off
,
203 mpz_t min
, mpz_t max
)
205 /* If the expression is a constant, we know its value exactly. */
206 if (integer_zerop (var
))
213 /* If the computation may wrap, we know nothing about the value, except for
214 the range of the type. */
215 get_type_bounds (type
, min
, max
);
216 if (!nowrap_type_p (type
))
219 /* Since the addition of OFF does not wrap, if OFF is positive, then we may
220 add it to MIN, otherwise to MAX. */
221 if (mpz_sgn (off
) < 0)
222 mpz_add (max
, max
, off
);
224 mpz_add (min
, min
, off
);
227 /* Stores the bounds on the difference of the values of the expressions
228 (var + X) and (var + Y), computed in TYPE, to BNDS. */
231 bound_difference_of_offsetted_base (tree type
, mpz_t x
, mpz_t y
,
234 int rel
= mpz_cmp (x
, y
);
235 bool may_wrap
= !nowrap_type_p (type
);
238 /* If X == Y, then the expressions are always equal.
239 If X > Y, there are the following possibilities:
240 a) neither of var + X and var + Y overflow or underflow, or both of
241 them do. Then their difference is X - Y.
242 b) var + X overflows, and var + Y does not. Then the values of the
243 expressions are var + X - M and var + Y, where M is the range of
244 the type, and their difference is X - Y - M.
245 c) var + Y underflows and var + X does not. Their difference again
247 Therefore, if the arithmetics in type does not overflow, then the
248 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
249 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
250 (X - Y, X - Y + M). */
254 mpz_set_ui (bnds
->below
, 0);
255 mpz_set_ui (bnds
->up
, 0);
260 mpz_set_double_int (m
, double_int_mask (TYPE_PRECISION (type
)), true);
261 mpz_add_ui (m
, m
, 1);
262 mpz_sub (bnds
->up
, x
, y
);
263 mpz_set (bnds
->below
, bnds
->up
);
268 mpz_sub (bnds
->below
, bnds
->below
, m
);
270 mpz_add (bnds
->up
, bnds
->up
, m
);
276 /* From condition C0 CMP C1 derives information regarding the
277 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
278 and stores it to BNDS. */
281 refine_bounds_using_guard (tree type
, tree varx
, mpz_t offx
,
282 tree vary
, mpz_t offy
,
283 tree c0
, enum tree_code cmp
, tree c1
,
286 tree varc0
, varc1
, tmp
;
287 mpz_t offc0
, offc1
, loffx
, loffy
, bnd
;
289 bool no_wrap
= nowrap_type_p (type
);
301 /* We could derive quite precise information from EQ_EXPR, however, such
302 a guard is unlikely to appear, so we do not bother with handling it.
307 /* NE_EXPR comparisons do not contain much of useful information (except for
308 special cases like comparing with the bounds of the type, TODO). */
316 split_to_var_and_offset (expand_simple_operations (c0
), &varc0
, offc0
);
317 split_to_var_and_offset (expand_simple_operations (c1
), &varc1
, offc1
);
319 /* We are only interested in comparisons of expressions based on VARX and
320 VARY. TODO -- we might also be able to derive some bounds from
321 expressions containing just one of the variables. */
323 if (operand_equal_p (varx
, varc1
, 0))
325 tmp
= varc0
; varc0
= varc1
; varc1
= tmp
;
326 mpz_swap (offc0
, offc1
);
327 cmp
= swap_tree_comparison (cmp
);
330 if (!operand_equal_p (varx
, varc0
, 0)
331 || !operand_equal_p (vary
, varc1
, 0))
334 mpz_init_set (loffx
, offx
);
335 mpz_init_set (loffy
, offy
);
337 if (cmp
== GT_EXPR
|| cmp
== GE_EXPR
)
339 tmp
= varx
; varx
= vary
; vary
= tmp
;
340 mpz_swap (offc0
, offc1
);
341 mpz_swap (loffx
, loffy
);
342 cmp
= swap_tree_comparison (cmp
);
346 /* If there is no overflow, the condition implies that
348 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
350 The overflows and underflows may complicate things a bit; each
351 overflow decreases the appropriate offset by M, and underflow
352 increases it by M. The above inequality would not necessarily be
355 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
356 VARX + OFFC0 overflows, but VARX + OFFX does not.
357 This may only happen if OFFX < OFFC0.
358 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
359 VARY + OFFC1 underflows and VARY + OFFY does not.
360 This may only happen if OFFY > OFFC1. */
369 x_ok
= (integer_zerop (varx
)
370 || mpz_cmp (loffx
, offc0
) >= 0);
371 y_ok
= (integer_zerop (vary
)
372 || mpz_cmp (loffy
, offc1
) <= 0);
378 mpz_sub (bnd
, loffx
, loffy
);
379 mpz_add (bnd
, bnd
, offc1
);
380 mpz_sub (bnd
, bnd
, offc0
);
383 mpz_sub_ui (bnd
, bnd
, 1);
388 if (mpz_cmp (bnds
->below
, bnd
) < 0)
389 mpz_set (bnds
->below
, bnd
);
393 if (mpz_cmp (bnd
, bnds
->up
) < 0)
394 mpz_set (bnds
->up
, bnd
);
406 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
407 The subtraction is considered to be performed in arbitrary precision,
410 We do not attempt to be too clever regarding the value ranges of X and
411 Y; most of the time, they are just integers or ssa names offsetted by
412 integer. However, we try to use the information contained in the
413 comparisons before the loop (usually created by loop header copying). */
416 bound_difference (struct loop
*loop
, tree x
, tree y
, bounds
*bnds
)
418 tree type
= TREE_TYPE (x
);
421 mpz_t minx
, maxx
, miny
, maxy
;
425 tree cond
, c0
, c1
, ctype
;
428 mpz_init (bnds
->below
);
432 split_to_var_and_offset (x
, &varx
, offx
);
433 split_to_var_and_offset (y
, &vary
, offy
);
435 if (!integer_zerop (varx
)
436 && operand_equal_p (varx
, vary
, 0))
438 /* Special case VARX == VARY -- we just need to compare the
439 offsets. The matters are a bit more complicated in the
440 case addition of offsets may wrap. */
441 bound_difference_of_offsetted_base (type
, offx
, offy
, bnds
);
445 /* Otherwise, use the value ranges to determine the initial
446 estimates on below and up. */
451 determine_value_range (type
, varx
, offx
, minx
, maxx
);
452 determine_value_range (type
, vary
, offy
, miny
, maxy
);
454 mpz_sub (bnds
->below
, minx
, maxy
);
455 mpz_sub (bnds
->up
, maxx
, miny
);
462 /* If both X and Y are constants, we cannot get any more precise. */
463 if (integer_zerop (varx
) && integer_zerop (vary
))
466 /* Now walk the dominators of the loop header and use the entry
467 guards to refine the estimates. */
468 for (bb
= loop
->header
;
469 bb
!= ENTRY_BLOCK_PTR
&& cnt
< MAX_DOMINATORS_TO_WALK
;
470 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
472 if (!single_pred_p (bb
))
474 e
= single_pred_edge (bb
);
476 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
479 cond
= COND_EXPR_COND (last_stmt (e
->src
));
480 if (!COMPARISON_CLASS_P (cond
))
482 c0
= TREE_OPERAND (cond
, 0);
483 cmp
= TREE_CODE (cond
);
484 c1
= TREE_OPERAND (cond
, 1);
485 ctype
= TREE_TYPE (c0
);
487 if (!tree_ssa_useless_type_conversion_1 (ctype
, type
))
490 if (e
->flags
& EDGE_FALSE_VALUE
)
491 cmp
= invert_tree_comparison (cmp
, false);
493 refine_bounds_using_guard (type
, varx
, offx
, vary
, offy
,
503 /* Update the bounds in BNDS that restrict the value of X to the bounds
504 that restrict the value of X + DELTA. X can be obtained as a
505 difference of two values in TYPE. */
508 bounds_add (bounds
*bnds
, double_int delta
, tree type
)
513 mpz_set_double_int (mdelta
, delta
, false);
516 mpz_set_double_int (max
, double_int_mask (TYPE_PRECISION (type
)), true);
518 mpz_add (bnds
->up
, bnds
->up
, mdelta
);
519 mpz_add (bnds
->below
, bnds
->below
, mdelta
);
521 if (mpz_cmp (bnds
->up
, max
) > 0)
522 mpz_set (bnds
->up
, max
);
525 if (mpz_cmp (bnds
->below
, max
) < 0)
526 mpz_set (bnds
->below
, max
);
532 /* Update the bounds in BNDS that restrict the value of X to the bounds
533 that restrict the value of -X. */
536 bounds_negate (bounds
*bnds
)
540 mpz_init_set (tmp
, bnds
->up
);
541 mpz_neg (bnds
->up
, bnds
->below
);
542 mpz_neg (bnds
->below
, tmp
);
546 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
549 inverse (tree x
, tree mask
)
551 tree type
= TREE_TYPE (x
);
553 unsigned ctr
= tree_floor_log2 (mask
);
555 if (TYPE_PRECISION (type
) <= HOST_BITS_PER_WIDE_INT
)
557 unsigned HOST_WIDE_INT ix
;
558 unsigned HOST_WIDE_INT imask
;
559 unsigned HOST_WIDE_INT irslt
= 1;
561 gcc_assert (cst_and_fits_in_hwi (x
));
562 gcc_assert (cst_and_fits_in_hwi (mask
));
564 ix
= int_cst_value (x
);
565 imask
= int_cst_value (mask
);
574 rslt
= build_int_cst_type (type
, irslt
);
578 rslt
= build_int_cst (type
, 1);
581 rslt
= int_const_binop (MULT_EXPR
, rslt
, x
, 0);
582 x
= int_const_binop (MULT_EXPR
, x
, x
, 0);
584 rslt
= int_const_binop (BIT_AND_EXPR
, rslt
, mask
, 0);
590 /* Derives the upper bound BND on the number of executions of loop with exit
591 condition S * i <> C, assuming that the loop is not infinite. If
592 NO_OVERFLOW is true, then the control variable of the loop does not
593 overflow. If NO_OVERFLOW is true or BNDS.below >= 0, then BNDS.up
594 contains the upper bound on the value of C. */
597 number_of_iterations_ne_max (mpz_t bnd
, bool no_overflow
, tree c
, tree s
,
603 /* If the control variable does not overflow, the number of iterations is
604 at most c / s. Otherwise it is at most the period of the control
606 if (!no_overflow
&& !multiple_of_p (TREE_TYPE (c
), c
, s
))
608 max
= double_int_mask (TYPE_PRECISION (TREE_TYPE (c
))
609 - tree_low_cst (num_ending_zeros (s
), 1));
610 mpz_set_double_int (bnd
, max
, true);
614 /* Determine the upper bound on C. */
615 if (no_overflow
|| mpz_sgn (bnds
->below
) >= 0)
616 mpz_set (bnd
, bnds
->up
);
617 else if (TREE_CODE (c
) == INTEGER_CST
)
618 mpz_set_double_int (bnd
, tree_to_double_int (c
), true);
620 mpz_set_double_int (bnd
, double_int_mask (TYPE_PRECISION (TREE_TYPE (c
))),
624 mpz_set_double_int (d
, tree_to_double_int (s
), true);
625 mpz_fdiv_q (bnd
, bnd
, d
);
629 /* Determines number of iterations of loop whose ending condition
630 is IV <> FINAL. TYPE is the type of the iv. The number of
631 iterations is stored to NITER. NEVER_INFINITE is true if
632 we know that the exit must be taken eventually, i.e., that the IV
633 ever reaches the value FINAL (we derived this earlier, and possibly set
634 NITER->assumptions to make sure this is the case). BNDS contains the
635 bounds on the difference FINAL - IV->base. */
638 number_of_iterations_ne (tree type
, affine_iv
*iv
, tree final
,
639 struct tree_niter_desc
*niter
, bool never_infinite
,
642 tree niter_type
= unsigned_type_for (type
);
643 tree s
, c
, d
, bits
, assumption
, tmp
, bound
;
646 niter
->control
= *iv
;
647 niter
->bound
= final
;
648 niter
->cmp
= NE_EXPR
;
650 /* Rearrange the terms so that we get inequality S * i <> C, with S
651 positive. Also cast everything to the unsigned type. If IV does
652 not overflow, BNDS bounds the value of C. Also, this is the
653 case if the computation |FINAL - IV->base| does not overflow, i.e.,
654 if BNDS->below in the result is nonnegative. */
655 if (tree_int_cst_sign_bit (iv
->step
))
657 s
= fold_convert (niter_type
,
658 fold_build1 (NEGATE_EXPR
, type
, iv
->step
));
659 c
= fold_build2 (MINUS_EXPR
, niter_type
,
660 fold_convert (niter_type
, iv
->base
),
661 fold_convert (niter_type
, final
));
662 bounds_negate (bnds
);
666 s
= fold_convert (niter_type
, iv
->step
);
667 c
= fold_build2 (MINUS_EXPR
, niter_type
,
668 fold_convert (niter_type
, final
),
669 fold_convert (niter_type
, iv
->base
));
673 number_of_iterations_ne_max (max
, iv
->no_overflow
, c
, s
, bnds
);
674 niter
->max
= mpz_to_double_int (niter_type
, max
);
677 /* First the trivial cases -- when the step is 1. */
678 if (integer_onep (s
))
684 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
685 is infinite. Otherwise, the number of iterations is
686 (inverse(s/d) * (c/d)) mod (size of mode/d). */
687 bits
= num_ending_zeros (s
);
688 bound
= build_low_bits_mask (niter_type
,
689 (TYPE_PRECISION (niter_type
)
690 - tree_low_cst (bits
, 1)));
692 d
= fold_binary_to_constant (LSHIFT_EXPR
, niter_type
,
693 build_int_cst (niter_type
, 1), bits
);
694 s
= fold_binary_to_constant (RSHIFT_EXPR
, niter_type
, s
, bits
);
698 /* If we cannot assume that the loop is not infinite, record the
699 assumptions for divisibility of c. */
700 assumption
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, c
, d
);
701 assumption
= fold_build2 (EQ_EXPR
, boolean_type_node
,
702 assumption
, build_int_cst (niter_type
, 0));
703 if (!integer_nonzerop (assumption
))
704 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
705 niter
->assumptions
, assumption
);
708 c
= fold_build2 (EXACT_DIV_EXPR
, niter_type
, c
, d
);
709 tmp
= fold_build2 (MULT_EXPR
, niter_type
, c
, inverse (s
, bound
));
710 niter
->niter
= fold_build2 (BIT_AND_EXPR
, niter_type
, tmp
, bound
);
714 /* Checks whether we can determine the final value of the control variable
715 of the loop with ending condition IV0 < IV1 (computed in TYPE).
716 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
717 of the step. The assumptions necessary to ensure that the computation
718 of the final value does not overflow are recorded in NITER. If we
719 find the final value, we adjust DELTA and return TRUE. Otherwise
720 we return false. BNDS bounds the value of IV1->base - IV0->base,
721 and will be updated by the same amount as DELTA. */
724 number_of_iterations_lt_to_ne (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
725 struct tree_niter_desc
*niter
,
726 tree
*delta
, tree step
,
729 tree niter_type
= TREE_TYPE (step
);
730 tree mod
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, *delta
, step
);
733 tree assumption
= boolean_true_node
, bound
, noloop
;
736 if (TREE_CODE (mod
) != INTEGER_CST
)
738 if (integer_nonzerop (mod
))
739 mod
= fold_build2 (MINUS_EXPR
, niter_type
, step
, mod
);
740 tmod
= fold_convert (type
, mod
);
743 mpz_set_double_int (mmod
, tree_to_double_int (mod
), true);
744 mpz_neg (mmod
, mmod
);
746 if (integer_nonzerop (iv0
->step
))
748 /* The final value of the iv is iv1->base + MOD, assuming that this
749 computation does not overflow, and that
750 iv0->base <= iv1->base + MOD. */
751 if (!iv1
->no_overflow
&& !integer_zerop (mod
))
753 bound
= fold_build2 (MINUS_EXPR
, type
,
754 TYPE_MAX_VALUE (type
), tmod
);
755 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
757 if (integer_zerop (assumption
))
760 if (mpz_cmp (mmod
, bnds
->below
) < 0)
761 noloop
= boolean_false_node
;
763 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
765 fold_build2 (PLUS_EXPR
, type
,
770 /* The final value of the iv is iv0->base - MOD, assuming that this
771 computation does not overflow, and that
772 iv0->base - MOD <= iv1->base. */
773 if (!iv0
->no_overflow
&& !integer_zerop (mod
))
775 bound
= fold_build2 (PLUS_EXPR
, type
,
776 TYPE_MIN_VALUE (type
), tmod
);
777 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
779 if (integer_zerop (assumption
))
782 if (mpz_cmp (mmod
, bnds
->below
) < 0)
783 noloop
= boolean_false_node
;
785 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
786 fold_build2 (MINUS_EXPR
, type
,
791 if (!integer_nonzerop (assumption
))
792 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
795 if (!integer_zerop (noloop
))
796 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
799 bounds_add (bnds
, tree_to_double_int (mod
), type
);
800 *delta
= fold_build2 (PLUS_EXPR
, niter_type
, *delta
, mod
);
808 /* Add assertions to NITER that ensure that the control variable of the loop
809 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
810 are TYPE. Returns false if we can prove that there is an overflow, true
811 otherwise. STEP is the absolute value of the step. */
814 assert_no_overflow_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
815 struct tree_niter_desc
*niter
, tree step
)
817 tree bound
, d
, assumption
, diff
;
818 tree niter_type
= TREE_TYPE (step
);
820 if (integer_nonzerop (iv0
->step
))
822 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
823 if (iv0
->no_overflow
)
826 /* If iv0->base is a constant, we can determine the last value before
827 overflow precisely; otherwise we conservatively assume
830 if (TREE_CODE (iv0
->base
) == INTEGER_CST
)
832 d
= fold_build2 (MINUS_EXPR
, niter_type
,
833 fold_convert (niter_type
, TYPE_MAX_VALUE (type
)),
834 fold_convert (niter_type
, iv0
->base
));
835 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
838 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
839 build_int_cst (niter_type
, 1));
840 bound
= fold_build2 (MINUS_EXPR
, type
,
841 TYPE_MAX_VALUE (type
), fold_convert (type
, diff
));
842 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
847 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
848 if (iv1
->no_overflow
)
851 if (TREE_CODE (iv1
->base
) == INTEGER_CST
)
853 d
= fold_build2 (MINUS_EXPR
, niter_type
,
854 fold_convert (niter_type
, iv1
->base
),
855 fold_convert (niter_type
, TYPE_MIN_VALUE (type
)));
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 (PLUS_EXPR
, type
,
862 TYPE_MIN_VALUE (type
), fold_convert (type
, diff
));
863 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
867 if (integer_zerop (assumption
))
869 if (!integer_nonzerop (assumption
))
870 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
871 niter
->assumptions
, assumption
);
873 iv0
->no_overflow
= true;
874 iv1
->no_overflow
= true;
878 /* Add an assumption to NITER that a loop whose ending condition
879 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
880 bounds the value of IV1->base - IV0->base. */
883 assert_loop_rolls_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
884 struct tree_niter_desc
*niter
, bounds
*bnds
)
886 tree assumption
= boolean_true_node
, bound
, diff
;
887 tree mbz
, mbzl
, mbzr
;
888 bool rolls_p
, no_overflow_p
;
892 /* We are going to compute the number of iterations as
893 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
894 variant of TYPE. This formula only works if
896 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
898 (where MAX is the maximum value of the unsigned variant of TYPE, and
899 the computations in this formula are performed in full precision
902 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
903 we have a condition of form iv0->base - step < iv1->base before the loop,
904 and for loops iv0->base < iv1->base - step * i the condition
905 iv0->base < iv1->base + step, due to loop header copying, which enable us
906 to prove the lower bound.
908 The upper bound is more complicated. Unless the expressions for initial
909 and final value themselves contain enough information, we usually cannot
910 derive it from the context. */
912 /* First check whether the answer does not follow from the bounds we gathered
914 if (integer_nonzerop (iv0
->step
))
915 dstep
= tree_to_double_int (iv0
->step
);
918 dstep
= double_int_sext (tree_to_double_int (iv1
->step
),
919 TYPE_PRECISION (type
));
920 dstep
= double_int_neg (dstep
);
924 mpz_set_double_int (mstep
, dstep
, true);
925 mpz_neg (mstep
, mstep
);
926 mpz_add_ui (mstep
, mstep
, 1);
928 rolls_p
= mpz_cmp (mstep
, bnds
->below
) <= 0;
931 mpz_set_double_int (max
, double_int_mask (TYPE_PRECISION (type
)), true);
932 mpz_add (max
, max
, mstep
);
933 no_overflow_p
= (mpz_cmp (bnds
->up
, max
) <= 0
934 /* For pointers, only values lying inside a single object
935 can be compared or manipulated by pointer arithmetics.
936 Gcc in general does not allow or handle objects larger
937 than half of the address space, hence the upper bound
938 is satisfied for pointers. */
939 || POINTER_TYPE_P (type
));
943 if (rolls_p
&& no_overflow_p
)
946 /* Now the hard part; we must formulate the assumption(s) as expressions, and
947 we must be careful not to introduce overflow. */
949 if (integer_nonzerop (iv0
->step
))
951 diff
= fold_build2 (MINUS_EXPR
, type
,
952 iv0
->step
, build_int_cst (type
, 1));
954 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
955 0 address never belongs to any object, we can assume this for
957 if (!POINTER_TYPE_P (type
))
959 bound
= fold_build2 (PLUS_EXPR
, type
,
960 TYPE_MIN_VALUE (type
), diff
);
961 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
965 /* And then we can compute iv0->base - diff, and compare it with
967 mbzl
= fold_build2 (MINUS_EXPR
, type
, iv0
->base
, diff
);
972 diff
= fold_build2 (PLUS_EXPR
, type
,
973 iv1
->step
, build_int_cst (type
, 1));
975 if (!POINTER_TYPE_P (type
))
977 bound
= fold_build2 (PLUS_EXPR
, type
,
978 TYPE_MAX_VALUE (type
), diff
);
979 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
984 mbzr
= fold_build2 (MINUS_EXPR
, type
, iv1
->base
, diff
);
987 if (!integer_nonzerop (assumption
))
988 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
989 niter
->assumptions
, assumption
);
992 mbz
= fold_build2 (GT_EXPR
, boolean_type_node
, mbzl
, mbzr
);
993 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
994 niter
->may_be_zero
, mbz
);
998 /* Determines number of iterations of loop whose ending condition
999 is IV0 < IV1. TYPE is the type of the iv. The number of
1000 iterations is stored to NITER. BNDS bounds the difference
1001 IV1->base - IV0->base. */
1004 number_of_iterations_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1005 struct tree_niter_desc
*niter
,
1006 bool never_infinite ATTRIBUTE_UNUSED
,
1009 tree niter_type
= unsigned_type_for (type
);
1010 tree delta
, step
, s
;
1013 if (integer_nonzerop (iv0
->step
))
1015 niter
->control
= *iv0
;
1016 niter
->cmp
= LT_EXPR
;
1017 niter
->bound
= iv1
->base
;
1021 niter
->control
= *iv1
;
1022 niter
->cmp
= GT_EXPR
;
1023 niter
->bound
= iv0
->base
;
1026 delta
= fold_build2 (MINUS_EXPR
, niter_type
,
1027 fold_convert (niter_type
, iv1
->base
),
1028 fold_convert (niter_type
, iv0
->base
));
1030 /* First handle the special case that the step is +-1. */
1031 if ((integer_onep (iv0
->step
) && integer_zerop (iv1
->step
))
1032 || (integer_all_onesp (iv1
->step
) && integer_zerop (iv0
->step
)))
1034 /* for (i = iv0->base; i < iv1->base; i++)
1038 for (i = iv1->base; i > iv0->base; i--).
1040 In both cases # of iterations is iv1->base - iv0->base, assuming that
1041 iv1->base >= iv0->base.
1043 First try to derive a lower bound on the value of
1044 iv1->base - iv0->base, computed in full precision. If the difference
1045 is nonnegative, we are done, otherwise we must record the
1048 if (mpz_sgn (bnds
->below
) < 0)
1049 niter
->may_be_zero
= fold_build2 (LT_EXPR
, boolean_type_node
,
1050 iv1
->base
, iv0
->base
);
1051 niter
->niter
= delta
;
1052 niter
->max
= mpz_to_double_int (niter_type
, bnds
->up
);
1056 if (integer_nonzerop (iv0
->step
))
1057 step
= fold_convert (niter_type
, iv0
->step
);
1059 step
= fold_convert (niter_type
,
1060 fold_build1 (NEGATE_EXPR
, type
, iv1
->step
));
1062 /* If we can determine the final value of the control iv exactly, we can
1063 transform the condition to != comparison. In particular, this will be
1064 the case if DELTA is constant. */
1065 if (number_of_iterations_lt_to_ne (type
, iv0
, iv1
, niter
, &delta
, step
,
1070 zps
.base
= build_int_cst (niter_type
, 0);
1072 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1073 zps does not overflow. */
1074 zps
.no_overflow
= true;
1076 return number_of_iterations_ne (type
, &zps
, delta
, niter
, true, bnds
);
1079 /* Make sure that the control iv does not overflow. */
1080 if (!assert_no_overflow_lt (type
, iv0
, iv1
, niter
, step
))
1083 /* We determine the number of iterations as (delta + step - 1) / step. For
1084 this to work, we must know that iv1->base >= iv0->base - step + 1,
1085 otherwise the loop does not roll. */
1086 assert_loop_rolls_lt (type
, iv0
, iv1
, niter
, bnds
);
1088 s
= fold_build2 (MINUS_EXPR
, niter_type
,
1089 step
, build_int_cst (niter_type
, 1));
1090 delta
= fold_build2 (PLUS_EXPR
, niter_type
, delta
, s
);
1091 niter
->niter
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, delta
, step
);
1095 mpz_set_double_int (mstep
, tree_to_double_int (step
), true);
1096 mpz_add (tmp
, bnds
->up
, mstep
);
1097 mpz_sub_ui (tmp
, tmp
, 1);
1098 mpz_fdiv_q (tmp
, tmp
, mstep
);
1099 niter
->max
= mpz_to_double_int (niter_type
, tmp
);
1106 /* Determines number of iterations of loop whose ending condition
1107 is IV0 <= IV1. TYPE is the type of the iv. The number of
1108 iterations is stored to NITER. NEVER_INFINITE is true if
1109 we know that this condition must eventually become false (we derived this
1110 earlier, and possibly set NITER->assumptions to make sure this
1111 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1114 number_of_iterations_le (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1115 struct tree_niter_desc
*niter
, bool never_infinite
,
1120 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1121 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1122 value of the type. This we must know anyway, since if it is
1123 equal to this value, the loop rolls forever. */
1125 if (!never_infinite
)
1127 if (integer_nonzerop (iv0
->step
))
1128 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1129 iv1
->base
, TYPE_MAX_VALUE (type
));
1131 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1132 iv0
->base
, TYPE_MIN_VALUE (type
));
1134 if (integer_zerop (assumption
))
1136 if (!integer_nonzerop (assumption
))
1137 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1138 niter
->assumptions
, assumption
);
1141 if (integer_nonzerop (iv0
->step
))
1142 iv1
->base
= fold_build2 (PLUS_EXPR
, type
,
1143 iv1
->base
, build_int_cst (type
, 1));
1145 iv0
->base
= fold_build2 (MINUS_EXPR
, type
,
1146 iv0
->base
, build_int_cst (type
, 1));
1148 bounds_add (bnds
, double_int_one
, type
);
1150 return number_of_iterations_lt (type
, iv0
, iv1
, niter
, never_infinite
, bnds
);
1153 /* Dumps description of affine induction variable IV to FILE. */
1156 dump_affine_iv (FILE *file
, affine_iv
*iv
)
1158 if (!integer_zerop (iv
->step
))
1159 fprintf (file
, "[");
1161 print_generic_expr (dump_file
, iv
->base
, TDF_SLIM
);
1163 if (!integer_zerop (iv
->step
))
1165 fprintf (file
, ", + , ");
1166 print_generic_expr (dump_file
, iv
->step
, TDF_SLIM
);
1167 fprintf (file
, "]%s", iv
->no_overflow
? "(no_overflow)" : "");
1171 /* Determine the number of iterations according to condition (for staying
1172 inside loop) which compares two induction variables using comparison
1173 operator CODE. The induction variable on left side of the comparison
1174 is IV0, the right-hand side is IV1. Both induction variables must have
1175 type TYPE, which must be an integer or pointer type. The steps of the
1176 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1178 LOOP is the loop whose number of iterations we are determining.
1180 ONLY_EXIT is true if we are sure this is the only way the loop could be
1181 exited (including possibly non-returning function calls, exceptions, etc.)
1182 -- in this case we can use the information whether the control induction
1183 variables can overflow or not in a more efficient way.
1185 The results (number of iterations and assumptions as described in
1186 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
1187 Returns false if it fails to determine number of iterations, true if it
1188 was determined (possibly with some assumptions). */
1191 number_of_iterations_cond (struct loop
*loop
,
1192 tree type
, affine_iv
*iv0
, enum tree_code code
,
1193 affine_iv
*iv1
, struct tree_niter_desc
*niter
,
1196 bool never_infinite
, ret
;
1199 /* The meaning of these assumptions is this:
1201 then the rest of information does not have to be valid
1202 if may_be_zero then the loop does not roll, even if
1204 niter
->assumptions
= boolean_true_node
;
1205 niter
->may_be_zero
= boolean_false_node
;
1206 niter
->niter
= NULL_TREE
;
1207 niter
->max
= double_int_zero
;
1209 niter
->bound
= NULL_TREE
;
1210 niter
->cmp
= ERROR_MARK
;
1212 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1213 the control variable is on lhs. */
1214 if (code
== GE_EXPR
|| code
== GT_EXPR
1215 || (code
== NE_EXPR
&& integer_zerop (iv0
->step
)))
1218 code
= swap_tree_comparison (code
);
1223 /* If this is not the only possible exit from the loop, the information
1224 that the induction variables cannot overflow as derived from
1225 signedness analysis cannot be relied upon. We use them e.g. in the
1226 following way: given loop for (i = 0; i <= n; i++), if i is
1227 signed, it cannot overflow, thus this loop is equivalent to
1228 for (i = 0; i < n + 1; i++); however, if n == MAX, but the loop
1229 is exited in some other way before i overflows, this transformation
1230 is incorrect (the new loop exits immediately). */
1231 iv0
->no_overflow
= false;
1232 iv1
->no_overflow
= false;
1235 if (POINTER_TYPE_P (type
))
1237 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1238 to the same object. If they do, the control variable cannot wrap
1239 (as wrap around the bounds of memory will never return a pointer
1240 that would be guaranteed to point to the same object, even if we
1241 avoid undefined behavior by casting to size_t and back). The
1242 restrictions on pointer arithmetics and comparisons of pointers
1243 ensure that using the no-overflow assumptions is correct in this
1244 case even if ONLY_EXIT is false. */
1245 iv0
->no_overflow
= true;
1246 iv1
->no_overflow
= true;
1249 /* If the control induction variable does not overflow, the loop obviously
1250 cannot be infinite. */
1251 if (!integer_zerop (iv0
->step
) && iv0
->no_overflow
)
1252 never_infinite
= true;
1253 else if (!integer_zerop (iv1
->step
) && iv1
->no_overflow
)
1254 never_infinite
= true;
1256 never_infinite
= false;
1258 /* We can handle the case when neither of the sides of the comparison is
1259 invariant, provided that the test is NE_EXPR. This rarely occurs in
1260 practice, but it is simple enough to manage. */
1261 if (!integer_zerop (iv0
->step
) && !integer_zerop (iv1
->step
))
1263 if (code
!= NE_EXPR
)
1266 iv0
->step
= fold_binary_to_constant (MINUS_EXPR
, type
,
1267 iv0
->step
, iv1
->step
);
1268 iv0
->no_overflow
= false;
1269 iv1
->step
= build_int_cst (type
, 0);
1270 iv1
->no_overflow
= true;
1273 /* If the result of the comparison is a constant, the loop is weird. More
1274 precise handling would be possible, but the situation is not common enough
1275 to waste time on it. */
1276 if (integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
))
1279 /* Ignore loops of while (i-- < 10) type. */
1280 if (code
!= NE_EXPR
)
1282 if (iv0
->step
&& tree_int_cst_sign_bit (iv0
->step
))
1285 if (!integer_zerop (iv1
->step
) && !tree_int_cst_sign_bit (iv1
->step
))
1289 /* If the loop exits immediately, there is nothing to do. */
1290 if (integer_zerop (fold_build2 (code
, boolean_type_node
, iv0
->base
, iv1
->base
)))
1292 niter
->niter
= build_int_cst (unsigned_type_for (type
), 0);
1293 niter
->max
= double_int_zero
;
1297 /* OK, now we know we have a senseful loop. Handle several cases, depending
1298 on what comparison operator is used. */
1299 bound_difference (loop
, iv1
->base
, iv0
->base
, &bnds
);
1301 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1304 "Analysing # of iterations of loop %d\n", loop
->num
);
1306 fprintf (dump_file
, " exit condition ");
1307 dump_affine_iv (dump_file
, iv0
);
1308 fprintf (dump_file
, " %s ",
1309 code
== NE_EXPR
? "!="
1310 : code
== LT_EXPR
? "<"
1312 dump_affine_iv (dump_file
, iv1
);
1313 fprintf (dump_file
, "\n");
1315 fprintf (dump_file
, " bounds on difference of bases: ");
1316 mpz_out_str (dump_file
, 10, bnds
.below
);
1317 fprintf (dump_file
, " ... ");
1318 mpz_out_str (dump_file
, 10, bnds
.up
);
1319 fprintf (dump_file
, "\n");
1325 gcc_assert (integer_zerop (iv1
->step
));
1326 ret
= number_of_iterations_ne (type
, iv0
, iv1
->base
, niter
,
1327 never_infinite
, &bnds
);
1331 ret
= number_of_iterations_lt (type
, iv0
, iv1
, niter
, never_infinite
,
1336 ret
= number_of_iterations_le (type
, iv0
, iv1
, niter
, never_infinite
,
1344 mpz_clear (bnds
.up
);
1345 mpz_clear (bnds
.below
);
1347 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1351 fprintf (dump_file
, " result:\n");
1352 if (!integer_nonzerop (niter
->assumptions
))
1354 fprintf (dump_file
, " under assumptions ");
1355 print_generic_expr (dump_file
, niter
->assumptions
, TDF_SLIM
);
1356 fprintf (dump_file
, "\n");
1359 if (!integer_zerop (niter
->may_be_zero
))
1361 fprintf (dump_file
, " zero if ");
1362 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
1363 fprintf (dump_file
, "\n");
1366 fprintf (dump_file
, " # of iterations ");
1367 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
1368 fprintf (dump_file
, ", bounded by ");
1369 dump_double_int (dump_file
, niter
->max
, true);
1370 fprintf (dump_file
, "\n");
1373 fprintf (dump_file
, " failed\n\n");
1378 /* Substitute NEW for OLD in EXPR and fold the result. */
1381 simplify_replace_tree (tree expr
, tree old
, tree
new)
1384 tree ret
= NULL_TREE
, e
, se
;
1390 || operand_equal_p (expr
, old
, 0))
1391 return unshare_expr (new);
1393 if (!EXPR_P (expr
) && !GIMPLE_STMT_P (expr
))
1396 n
= TREE_OPERAND_LENGTH (expr
);
1397 for (i
= 0; i
< n
; i
++)
1399 e
= TREE_OPERAND (expr
, i
);
1400 se
= simplify_replace_tree (e
, old
, new);
1405 ret
= copy_node (expr
);
1407 TREE_OPERAND (ret
, i
) = se
;
1410 return (ret
? fold (ret
) : expr
);
1413 /* Expand definitions of ssa names in EXPR as long as they are simple
1414 enough, and return the new expression. */
1417 expand_simple_operations (tree expr
)
1420 tree ret
= NULL_TREE
, e
, ee
, stmt
;
1421 enum tree_code code
;
1423 if (expr
== NULL_TREE
)
1426 if (is_gimple_min_invariant (expr
))
1429 code
= TREE_CODE (expr
);
1430 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
1432 n
= TREE_OPERAND_LENGTH (expr
);
1433 for (i
= 0; i
< n
; i
++)
1435 e
= TREE_OPERAND (expr
, i
);
1436 ee
= expand_simple_operations (e
);
1441 ret
= copy_node (expr
);
1443 TREE_OPERAND (ret
, i
) = ee
;
1449 fold_defer_overflow_warnings ();
1451 fold_undefer_and_ignore_overflow_warnings ();
1455 if (TREE_CODE (expr
) != SSA_NAME
)
1458 stmt
= SSA_NAME_DEF_STMT (expr
);
1459 if (TREE_CODE (stmt
) == PHI_NODE
)
1461 basic_block src
, dest
;
1463 if (PHI_NUM_ARGS (stmt
) != 1)
1465 e
= PHI_ARG_DEF (stmt
, 0);
1467 /* Avoid propagating through loop exit phi nodes, which
1468 could break loop-closed SSA form restrictions. */
1469 dest
= bb_for_stmt (stmt
);
1470 src
= single_pred (dest
);
1471 if (TREE_CODE (e
) == SSA_NAME
1472 && src
->loop_father
!= dest
->loop_father
)
1475 return expand_simple_operations (e
);
1477 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
1480 e
= GIMPLE_STMT_OPERAND (stmt
, 1);
1481 if (/* Casts are simple. */
1482 TREE_CODE (e
) != NOP_EXPR
1483 && TREE_CODE (e
) != CONVERT_EXPR
1484 /* Copies are simple. */
1485 && TREE_CODE (e
) != SSA_NAME
1486 /* Assignments of invariants are simple. */
1487 && !is_gimple_min_invariant (e
)
1488 /* And increments and decrements by a constant are simple. */
1489 && !((TREE_CODE (e
) == PLUS_EXPR
1490 || TREE_CODE (e
) == MINUS_EXPR
)
1491 && is_gimple_min_invariant (TREE_OPERAND (e
, 1))))
1494 return expand_simple_operations (e
);
1497 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1498 expression (or EXPR unchanged, if no simplification was possible). */
1501 tree_simplify_using_condition_1 (tree cond
, tree expr
)
1504 tree e
, te
, e0
, e1
, e2
, notcond
;
1505 enum tree_code code
= TREE_CODE (expr
);
1507 if (code
== INTEGER_CST
)
1510 if (code
== TRUTH_OR_EXPR
1511 || code
== TRUTH_AND_EXPR
1512 || code
== COND_EXPR
)
1516 e0
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 0));
1517 if (TREE_OPERAND (expr
, 0) != e0
)
1520 e1
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 1));
1521 if (TREE_OPERAND (expr
, 1) != e1
)
1524 if (code
== COND_EXPR
)
1526 e2
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 2));
1527 if (TREE_OPERAND (expr
, 2) != e2
)
1535 if (code
== COND_EXPR
)
1536 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1538 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1544 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
1545 propagation, and vice versa. Fold does not handle this, since it is
1546 considered too expensive. */
1547 if (TREE_CODE (cond
) == EQ_EXPR
)
1549 e0
= TREE_OPERAND (cond
, 0);
1550 e1
= TREE_OPERAND (cond
, 1);
1552 /* We know that e0 == e1. Check whether we cannot simplify expr
1554 e
= simplify_replace_tree (expr
, e0
, e1
);
1555 if (integer_zerop (e
) || integer_nonzerop (e
))
1558 e
= simplify_replace_tree (expr
, e1
, e0
);
1559 if (integer_zerop (e
) || integer_nonzerop (e
))
1562 if (TREE_CODE (expr
) == EQ_EXPR
)
1564 e0
= TREE_OPERAND (expr
, 0);
1565 e1
= TREE_OPERAND (expr
, 1);
1567 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
1568 e
= simplify_replace_tree (cond
, e0
, e1
);
1569 if (integer_zerop (e
))
1571 e
= simplify_replace_tree (cond
, e1
, e0
);
1572 if (integer_zerop (e
))
1575 if (TREE_CODE (expr
) == NE_EXPR
)
1577 e0
= TREE_OPERAND (expr
, 0);
1578 e1
= TREE_OPERAND (expr
, 1);
1580 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
1581 e
= simplify_replace_tree (cond
, e0
, e1
);
1582 if (integer_zerop (e
))
1583 return boolean_true_node
;
1584 e
= simplify_replace_tree (cond
, e1
, e0
);
1585 if (integer_zerop (e
))
1586 return boolean_true_node
;
1589 te
= expand_simple_operations (expr
);
1591 /* Check whether COND ==> EXPR. */
1592 notcond
= invert_truthvalue (cond
);
1593 e
= fold_binary (TRUTH_OR_EXPR
, boolean_type_node
, notcond
, te
);
1594 if (e
&& integer_nonzerop (e
))
1597 /* Check whether COND ==> not EXPR. */
1598 e
= fold_binary (TRUTH_AND_EXPR
, boolean_type_node
, cond
, te
);
1599 if (e
&& integer_zerop (e
))
1605 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1606 expression (or EXPR unchanged, if no simplification was possible).
1607 Wrapper around tree_simplify_using_condition_1 that ensures that chains
1608 of simple operations in definitions of ssa names in COND are expanded,
1609 so that things like casts or incrementing the value of the bound before
1610 the loop do not cause us to fail. */
1613 tree_simplify_using_condition (tree cond
, tree expr
)
1615 cond
= expand_simple_operations (cond
);
1617 return tree_simplify_using_condition_1 (cond
, expr
);
1620 /* Tries to simplify EXPR using the conditions on entry to LOOP.
1621 Returns the simplified expression (or EXPR unchanged, if no
1622 simplification was possible).*/
1625 simplify_using_initial_conditions (struct loop
*loop
, tree expr
)
1632 if (TREE_CODE (expr
) == INTEGER_CST
)
1635 /* Limit walking the dominators to avoid quadraticness in
1636 the number of BBs times the number of loops in degenerate
1638 for (bb
= loop
->header
;
1639 bb
!= ENTRY_BLOCK_PTR
&& cnt
< MAX_DOMINATORS_TO_WALK
;
1640 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1642 if (!single_pred_p (bb
))
1644 e
= single_pred_edge (bb
);
1646 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
1649 cond
= COND_EXPR_COND (last_stmt (e
->src
));
1650 if (e
->flags
& EDGE_FALSE_VALUE
)
1651 cond
= invert_truthvalue (cond
);
1652 expr
= tree_simplify_using_condition (cond
, expr
);
1659 /* Tries to simplify EXPR using the evolutions of the loop invariants
1660 in the superloops of LOOP. Returns the simplified expression
1661 (or EXPR unchanged, if no simplification was possible). */
1664 simplify_using_outer_evolutions (struct loop
*loop
, tree expr
)
1666 enum tree_code code
= TREE_CODE (expr
);
1670 if (is_gimple_min_invariant (expr
))
1673 if (code
== TRUTH_OR_EXPR
1674 || code
== TRUTH_AND_EXPR
1675 || code
== COND_EXPR
)
1679 e0
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 0));
1680 if (TREE_OPERAND (expr
, 0) != e0
)
1683 e1
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 1));
1684 if (TREE_OPERAND (expr
, 1) != e1
)
1687 if (code
== COND_EXPR
)
1689 e2
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 2));
1690 if (TREE_OPERAND (expr
, 2) != e2
)
1698 if (code
== COND_EXPR
)
1699 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1701 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1707 e
= instantiate_parameters (loop
, expr
);
1708 if (is_gimple_min_invariant (e
))
1714 /* Returns true if EXIT is the only possible exit from LOOP. */
1717 loop_only_exit_p (struct loop
*loop
, edge exit
)
1720 block_stmt_iterator bsi
;
1724 if (exit
!= single_exit (loop
))
1727 body
= get_loop_body (loop
);
1728 for (i
= 0; i
< loop
->num_nodes
; i
++)
1730 for (bsi
= bsi_start (body
[0]); !bsi_end_p (bsi
); bsi_next (&bsi
))
1732 call
= get_call_expr_in (bsi_stmt (bsi
));
1733 if (call
&& TREE_SIDE_EFFECTS (call
))
1745 /* Stores description of number of iterations of LOOP derived from
1746 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
1747 useful information could be derived (and fields of NITER has
1748 meaning described in comments at struct tree_niter_desc
1749 declaration), false otherwise. If WARN is true and
1750 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1751 potentially unsafe assumptions. */
1754 number_of_iterations_exit (struct loop
*loop
, edge exit
,
1755 struct tree_niter_desc
*niter
,
1758 tree stmt
, cond
, type
;
1760 enum tree_code code
;
1763 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit
->src
))
1766 niter
->assumptions
= boolean_false_node
;
1767 stmt
= last_stmt (exit
->src
);
1768 if (!stmt
|| TREE_CODE (stmt
) != COND_EXPR
)
1771 /* We want the condition for staying inside loop. */
1772 cond
= COND_EXPR_COND (stmt
);
1773 if (exit
->flags
& EDGE_TRUE_VALUE
)
1774 cond
= invert_truthvalue (cond
);
1776 code
= TREE_CODE (cond
);
1790 op0
= TREE_OPERAND (cond
, 0);
1791 op1
= TREE_OPERAND (cond
, 1);
1792 type
= TREE_TYPE (op0
);
1794 if (TREE_CODE (type
) != INTEGER_TYPE
1795 && !POINTER_TYPE_P (type
))
1798 if (!simple_iv (loop
, stmt
, op0
, &iv0
, false))
1800 if (!simple_iv (loop
, stmt
, op1
, &iv1
, false))
1803 /* We don't want to see undefined signed overflow warnings while
1804 computing the number of iterations. */
1805 fold_defer_overflow_warnings ();
1807 iv0
.base
= expand_simple_operations (iv0
.base
);
1808 iv1
.base
= expand_simple_operations (iv1
.base
);
1809 if (!number_of_iterations_cond (loop
, type
, &iv0
, code
, &iv1
, niter
,
1810 loop_only_exit_p (loop
, exit
)))
1812 fold_undefer_and_ignore_overflow_warnings ();
1818 niter
->assumptions
= simplify_using_outer_evolutions (loop
,
1819 niter
->assumptions
);
1820 niter
->may_be_zero
= simplify_using_outer_evolutions (loop
,
1821 niter
->may_be_zero
);
1822 niter
->niter
= simplify_using_outer_evolutions (loop
, niter
->niter
);
1826 = simplify_using_initial_conditions (loop
,
1827 niter
->assumptions
);
1829 = simplify_using_initial_conditions (loop
,
1830 niter
->may_be_zero
);
1832 fold_undefer_and_ignore_overflow_warnings ();
1834 if (integer_onep (niter
->assumptions
))
1837 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1838 But if we can prove that there is overflow or some other source of weird
1839 behavior, ignore the loop even with -funsafe-loop-optimizations. */
1840 if (integer_zerop (niter
->assumptions
))
1843 if (flag_unsafe_loop_optimizations
)
1844 niter
->assumptions
= boolean_true_node
;
1848 const char *wording
;
1849 location_t loc
= EXPR_LOCATION (stmt
);
1851 /* We can provide a more specific warning if one of the operator is
1852 constant and the other advances by +1 or -1. */
1853 if (!integer_zerop (iv1
.step
)
1854 ? (integer_zerop (iv0
.step
)
1855 && (integer_onep (iv1
.step
) || integer_all_onesp (iv1
.step
)))
1856 : (integer_onep (iv0
.step
) || integer_all_onesp (iv0
.step
)))
1858 flag_unsafe_loop_optimizations
1859 ? N_("assuming that the loop is not infinite")
1860 : N_("cannot optimize possibly infinite loops");
1863 flag_unsafe_loop_optimizations
1864 ? N_("assuming that the loop counter does not overflow")
1865 : N_("cannot optimize loop, the loop counter may overflow");
1867 if (LOCATION_LINE (loc
) > 0)
1868 warning (OPT_Wunsafe_loop_optimizations
, "%H%s", &loc
, gettext (wording
));
1870 warning (OPT_Wunsafe_loop_optimizations
, "%s", gettext (wording
));
1873 return flag_unsafe_loop_optimizations
;
1876 /* Try to determine the number of iterations of LOOP. If we succeed,
1877 expression giving number of iterations is returned and *EXIT is
1878 set to the edge from that the information is obtained. Otherwise
1879 chrec_dont_know is returned. */
1882 find_loop_niter (struct loop
*loop
, edge
*exit
)
1885 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
1887 tree niter
= NULL_TREE
, aniter
;
1888 struct tree_niter_desc desc
;
1891 for (i
= 0; VEC_iterate (edge
, exits
, i
, ex
); i
++)
1893 if (!just_once_each_iteration_p (loop
, ex
->src
))
1896 if (!number_of_iterations_exit (loop
, ex
, &desc
, false))
1899 if (integer_nonzerop (desc
.may_be_zero
))
1901 /* We exit in the first iteration through this exit.
1902 We won't find anything better. */
1903 niter
= build_int_cst (unsigned_type_node
, 0);
1908 if (!integer_zerop (desc
.may_be_zero
))
1911 aniter
= desc
.niter
;
1915 /* Nothing recorded yet. */
1921 /* Prefer constants, the lower the better. */
1922 if (TREE_CODE (aniter
) != INTEGER_CST
)
1925 if (TREE_CODE (niter
) != INTEGER_CST
)
1932 if (tree_int_cst_lt (aniter
, niter
))
1939 VEC_free (edge
, heap
, exits
);
1941 return niter
? niter
: chrec_dont_know
;
1946 Analysis of a number of iterations of a loop by a brute-force evaluation.
1950 /* Bound on the number of iterations we try to evaluate. */
1952 #define MAX_ITERATIONS_TO_TRACK \
1953 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
1955 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
1956 result by a chain of operations such that all but exactly one of their
1957 operands are constants. */
1960 chain_of_csts_start (struct loop
*loop
, tree x
)
1962 tree stmt
= SSA_NAME_DEF_STMT (x
);
1964 basic_block bb
= bb_for_stmt (stmt
);
1967 || !flow_bb_inside_loop_p (loop
, bb
))
1970 if (TREE_CODE (stmt
) == PHI_NODE
)
1972 if (bb
== loop
->header
)
1978 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
1981 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
1983 if (SINGLE_SSA_DEF_OPERAND (stmt
, SSA_OP_DEF
) == NULL_DEF_OPERAND_P
)
1986 use
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1987 if (use
== NULL_USE_OPERAND_P
)
1990 return chain_of_csts_start (loop
, use
);
1993 /* Determines whether the expression X is derived from a result of a phi node
1994 in header of LOOP such that
1996 * the derivation of X consists only from operations with constants
1997 * the initial value of the phi node is constant
1998 * the value of the phi node in the next iteration can be derived from the
1999 value in the current iteration by a chain of operations with constants.
2001 If such phi node exists, it is returned. If X is a constant, X is returned
2002 unchanged. Otherwise NULL_TREE is returned. */
2005 get_base_for (struct loop
*loop
, tree x
)
2007 tree phi
, init
, next
;
2009 if (is_gimple_min_invariant (x
))
2012 phi
= chain_of_csts_start (loop
, x
);
2016 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2017 next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2019 if (TREE_CODE (next
) != SSA_NAME
)
2022 if (!is_gimple_min_invariant (init
))
2025 if (chain_of_csts_start (loop
, next
) != phi
)
2031 /* Given an expression X, then
2033 * if X is NULL_TREE, we return the constant BASE.
2034 * otherwise X is a SSA name, whose value in the considered loop is derived
2035 by a chain of operations with constant from a result of a phi node in
2036 the header of the loop. Then we return value of X when the value of the
2037 result of this phi node is given by the constant BASE. */
2040 get_val_for (tree x
, tree base
)
2046 gcc_assert (is_gimple_min_invariant (base
));
2051 stmt
= SSA_NAME_DEF_STMT (x
);
2052 if (TREE_CODE (stmt
) == PHI_NODE
)
2055 FOR_EACH_SSA_USE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
2057 nx
= USE_FROM_PTR (op
);
2058 val
= get_val_for (nx
, base
);
2060 val
= fold (GIMPLE_STMT_OPERAND (stmt
, 1));
2062 /* only iterate loop once. */
2066 /* Should never reach here. */
2070 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2071 by brute force -- i.e. by determining the value of the operands of the
2072 condition at EXIT in first few iterations of the loop (assuming that
2073 these values are constant) and determining the first one in that the
2074 condition is not satisfied. Returns the constant giving the number
2075 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
2078 loop_niter_by_eval (struct loop
*loop
, edge exit
)
2080 tree cond
, cnd
, acnd
;
2081 tree op
[2], val
[2], next
[2], aval
[2], phi
[2];
2085 cond
= last_stmt (exit
->src
);
2086 if (!cond
|| TREE_CODE (cond
) != COND_EXPR
)
2087 return chrec_dont_know
;
2089 cnd
= COND_EXPR_COND (cond
);
2090 if (exit
->flags
& EDGE_TRUE_VALUE
)
2091 cnd
= invert_truthvalue (cnd
);
2093 cmp
= TREE_CODE (cnd
);
2102 for (j
= 0; j
< 2; j
++)
2103 op
[j
] = TREE_OPERAND (cnd
, j
);
2107 return chrec_dont_know
;
2110 for (j
= 0; j
< 2; j
++)
2112 phi
[j
] = get_base_for (loop
, op
[j
]);
2114 return chrec_dont_know
;
2117 for (j
= 0; j
< 2; j
++)
2119 if (TREE_CODE (phi
[j
]) == PHI_NODE
)
2121 val
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
[j
], loop_preheader_edge (loop
));
2122 next
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
[j
], loop_latch_edge (loop
));
2127 next
[j
] = NULL_TREE
;
2132 /* Don't issue signed overflow warnings. */
2133 fold_defer_overflow_warnings ();
2135 for (i
= 0; i
< MAX_ITERATIONS_TO_TRACK
; i
++)
2137 for (j
= 0; j
< 2; j
++)
2138 aval
[j
] = get_val_for (op
[j
], val
[j
]);
2140 acnd
= fold_binary (cmp
, boolean_type_node
, aval
[0], aval
[1]);
2141 if (acnd
&& integer_zerop (acnd
))
2143 fold_undefer_and_ignore_overflow_warnings ();
2144 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2146 "Proved that loop %d iterates %d times using brute force.\n",
2148 return build_int_cst (unsigned_type_node
, i
);
2151 for (j
= 0; j
< 2; j
++)
2153 val
[j
] = get_val_for (next
[j
], val
[j
]);
2154 if (!is_gimple_min_invariant (val
[j
]))
2156 fold_undefer_and_ignore_overflow_warnings ();
2157 return chrec_dont_know
;
2162 fold_undefer_and_ignore_overflow_warnings ();
2164 return chrec_dont_know
;
2167 /* Finds the exit of the LOOP by that the loop exits after a constant
2168 number of iterations and stores the exit edge to *EXIT. The constant
2169 giving the number of iterations of LOOP is returned. The number of
2170 iterations is determined using loop_niter_by_eval (i.e. by brute force
2171 evaluation). If we are unable to find the exit for that loop_niter_by_eval
2172 determines the number of iterations, chrec_dont_know is returned. */
2175 find_loop_niter_by_eval (struct loop
*loop
, edge
*exit
)
2178 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
2180 tree niter
= NULL_TREE
, aniter
;
2183 for (i
= 0; VEC_iterate (edge
, exits
, i
, ex
); i
++)
2185 if (!just_once_each_iteration_p (loop
, ex
->src
))
2188 aniter
= loop_niter_by_eval (loop
, ex
);
2189 if (chrec_contains_undetermined (aniter
))
2193 && !tree_int_cst_lt (aniter
, niter
))
2199 VEC_free (edge
, heap
, exits
);
2201 return niter
? niter
: chrec_dont_know
;
2206 Analysis of upper bounds on number of iterations of a loop.
2210 /* Returns a constant upper bound on the value of expression VAL. VAL
2211 is considered to be unsigned. If its type is signed, its value must
2215 derive_constant_upper_bound (tree val
)
2217 tree type
= TREE_TYPE (val
);
2218 tree op0
, op1
, subtype
, maxt
;
2219 double_int bnd
, max
, mmax
, cst
;
2222 if (INTEGRAL_TYPE_P (type
))
2223 maxt
= TYPE_MAX_VALUE (type
);
2225 maxt
= upper_bound_in_type (type
, type
);
2227 max
= tree_to_double_int (maxt
);
2229 switch (TREE_CODE (val
))
2232 return tree_to_double_int (val
);
2236 op0
= TREE_OPERAND (val
, 0);
2237 subtype
= TREE_TYPE (op0
);
2238 if (!TYPE_UNSIGNED (subtype
)
2239 /* If TYPE is also signed, the fact that VAL is nonnegative implies
2240 that OP0 is nonnegative. */
2241 && TYPE_UNSIGNED (type
)
2242 && !tree_expr_nonnegative_p (op0
))
2244 /* If we cannot prove that the casted expression is nonnegative,
2245 we cannot establish more useful upper bound than the precision
2246 of the type gives us. */
2250 /* We now know that op0 is an nonnegative value. Try deriving an upper
2252 bnd
= derive_constant_upper_bound (op0
);
2254 /* If the bound does not fit in TYPE, max. value of TYPE could be
2256 if (double_int_ucmp (max
, bnd
) < 0)
2263 op0
= TREE_OPERAND (val
, 0);
2264 op1
= TREE_OPERAND (val
, 1);
2266 if (TREE_CODE (op1
) != INTEGER_CST
2267 || !tree_expr_nonnegative_p (op0
))
2270 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
2271 choose the most logical way how to treat this constant regardless
2272 of the signedness of the type. */
2273 cst
= tree_to_double_int (op1
);
2274 cst
= double_int_sext (cst
, TYPE_PRECISION (type
));
2275 if (TREE_CODE (val
) == PLUS_EXPR
)
2276 cst
= double_int_neg (cst
);
2278 bnd
= derive_constant_upper_bound (op0
);
2280 if (double_int_negative_p (cst
))
2282 cst
= double_int_neg (cst
);
2283 /* Avoid CST == 0x80000... */
2284 if (double_int_negative_p (cst
))
2287 /* OP0 + CST. We need to check that
2288 BND <= MAX (type) - CST. */
2290 mmax
= double_int_add (max
, double_int_neg (cst
));
2291 if (double_int_ucmp (bnd
, mmax
) > 0)
2294 return double_int_add (bnd
, cst
);
2298 /* OP0 - CST, where CST >= 0.
2300 If TYPE is signed, we have already verified that OP0 >= 0, and we
2301 know that the result is nonnegative. This implies that
2304 If TYPE is unsigned, we must additionally know that OP0 >= CST,
2305 otherwise the operation underflows.
2308 /* This should only happen if the type is unsigned; however, for
2309 buggy programs that use overflowing signed arithmetics even with
2310 -fno-wrapv, this condition may also be true for signed values. */
2311 if (double_int_ucmp (bnd
, cst
) < 0)
2314 if (TYPE_UNSIGNED (type
))
2316 tree tem
= fold_binary (GE_EXPR
, boolean_type_node
, op0
,
2317 double_int_to_tree (type
, cst
));
2318 if (!tem
|| integer_nonzerop (tem
))
2322 bnd
= double_int_add (bnd
, double_int_neg (cst
));
2327 case FLOOR_DIV_EXPR
:
2328 case EXACT_DIV_EXPR
:
2329 op0
= TREE_OPERAND (val
, 0);
2330 op1
= TREE_OPERAND (val
, 1);
2331 if (TREE_CODE (op1
) != INTEGER_CST
2332 || tree_int_cst_sign_bit (op1
))
2335 bnd
= derive_constant_upper_bound (op0
);
2336 return double_int_udiv (bnd
, tree_to_double_int (op1
), FLOOR_DIV_EXPR
);
2339 op1
= TREE_OPERAND (val
, 1);
2340 if (TREE_CODE (op1
) != INTEGER_CST
2341 || tree_int_cst_sign_bit (op1
))
2343 return tree_to_double_int (op1
);
2346 stmt
= SSA_NAME_DEF_STMT (val
);
2347 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
2348 || GIMPLE_STMT_OPERAND (stmt
, 0) != val
)
2350 return derive_constant_upper_bound (GIMPLE_STMT_OPERAND (stmt
, 1));
2357 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
2358 is true if the loop is exited immediately after STMT, and this exit
2359 is taken at last when the STMT is executed BOUND + 1 times.
2360 REALISTIC is true if the estimate comes from a reliable source
2361 (number of iterations analysis, or size of data accessed in the loop).
2362 I_BOUND is an unsigned double_int upper estimate on BOUND. */
2365 record_estimate (struct loop
*loop
, tree bound
, double_int i_bound
,
2366 tree at_stmt
, bool is_exit
, bool realistic
)
2368 struct nb_iter_bound
*elt
= xmalloc (sizeof (struct nb_iter_bound
));
2370 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2372 fprintf (dump_file
, "Statement %s", is_exit
? "(exit)" : "");
2373 print_generic_expr (dump_file
, at_stmt
, TDF_SLIM
);
2374 fprintf (dump_file
, " is executed at most ");
2375 print_generic_expr (dump_file
, bound
, TDF_SLIM
);
2376 fprintf (dump_file
, " (bounded by ");
2377 dump_double_int (dump_file
, i_bound
, true);
2378 fprintf (dump_file
, ") + 1 times in loop %d.\n", loop
->num
);
2381 elt
->bound
= i_bound
;
2382 elt
->stmt
= at_stmt
;
2383 elt
->is_exit
= is_exit
;
2384 elt
->realistic
= realistic
&& TREE_CODE (bound
) == INTEGER_CST
;
2385 elt
->next
= loop
->bounds
;
2389 /* Record the estimate on number of iterations of LOOP based on the fact that
2390 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
2391 its values belong to the range <LOW, HIGH>. DATA_SIZE_BOUNDS_P is true if
2392 LOW and HIGH are derived from the size of data. */
2395 record_nonwrapping_iv (struct loop
*loop
, tree base
, tree step
, tree stmt
,
2396 tree low
, tree high
, bool data_size_bounds_p
)
2398 tree niter_bound
, extreme
, delta
;
2399 tree type
= TREE_TYPE (base
), unsigned_type
;
2402 if (TREE_CODE (step
) != INTEGER_CST
|| integer_zerop (step
))
2405 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2407 fprintf (dump_file
, "Induction variable (");
2408 print_generic_expr (dump_file
, TREE_TYPE (base
), TDF_SLIM
);
2409 fprintf (dump_file
, ") ");
2410 print_generic_expr (dump_file
, base
, TDF_SLIM
);
2411 fprintf (dump_file
, " + ");
2412 print_generic_expr (dump_file
, step
, TDF_SLIM
);
2413 fprintf (dump_file
, " * iteration does not wrap in statement ");
2414 print_generic_expr (dump_file
, stmt
, TDF_SLIM
);
2415 fprintf (dump_file
, " in loop %d.\n", loop
->num
);
2418 unsigned_type
= unsigned_type_for (type
);
2419 base
= fold_convert (unsigned_type
, base
);
2420 step
= fold_convert (unsigned_type
, step
);
2422 if (tree_int_cst_sign_bit (step
))
2424 extreme
= fold_convert (unsigned_type
, low
);
2425 if (TREE_CODE (base
) != INTEGER_CST
)
2426 base
= fold_convert (unsigned_type
, high
);
2427 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
2428 step
= fold_build1 (NEGATE_EXPR
, unsigned_type
, step
);
2432 extreme
= fold_convert (unsigned_type
, high
);
2433 if (TREE_CODE (base
) != INTEGER_CST
)
2434 base
= fold_convert (unsigned_type
, low
);
2435 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
2438 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
2439 would get out of the range. */
2440 niter_bound
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step
);
2441 max
= derive_constant_upper_bound (niter_bound
);
2442 record_estimate (loop
, niter_bound
, max
, stmt
, false, data_size_bounds_p
);
2445 /* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe
2446 approximation of the number of iterations for LOOP. */
2449 compute_estimated_nb_iterations (struct loop
*loop
)
2451 struct nb_iter_bound
*bound
;
2452 double_int bnd_val
, delta
;
2455 gcc_assert (loop
->estimate_state
== EST_NOT_AVAILABLE
);
2457 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
2459 if (!bound
->realistic
)
2462 bnd_val
= bound
->bound
;
2463 /* If bound->stmt is an exit, then every statement in the loop is
2464 executed at most BND_VAL + 1 times. If it is not an exit, then
2465 some of the statements before it could be executed BND_VAL + 2
2466 times, if an exit of LOOP is before stmt. */
2467 exit
= single_exit (loop
);
2471 && dominated_by_p (CDI_DOMINATORS
,
2472 exit
->src
, bb_for_stmt (bound
->stmt
))))
2473 delta
= double_int_one
;
2475 delta
= double_int_two
;
2476 bnd_val
= double_int_add (bnd_val
, delta
);
2478 /* If an overflow occured, ignore the result. */
2479 if (double_int_ucmp (bnd_val
, delta
) < 0)
2482 /* Update only when there is no previous estimation, or when the current
2483 estimation is smaller. */
2484 if (loop
->estimate_state
== EST_NOT_AVAILABLE
2485 || double_int_ucmp (bnd_val
, loop
->estimated_nb_iterations
) < 0)
2487 loop
->estimate_state
= EST_AVAILABLE
;
2488 loop
->estimated_nb_iterations
= bnd_val
;
2493 /* Returns true if REF is a reference to an array at the end of a dynamically
2494 allocated structure. If this is the case, the array may be allocated larger
2495 than its upper bound implies. */
2498 array_at_struct_end_p (tree ref
)
2500 tree base
= get_base_address (ref
);
2503 /* Unless the reference is through a pointer, the size of the array matches
2505 if (!base
|| !INDIRECT_REF_P (base
))
2508 for (;handled_component_p (ref
); ref
= parent
)
2510 parent
= TREE_OPERAND (ref
, 0);
2512 if (TREE_CODE (ref
) == COMPONENT_REF
)
2514 /* All fields of a union are at its end. */
2515 if (TREE_CODE (TREE_TYPE (parent
)) == UNION_TYPE
)
2518 /* Unless the field is at the end of the struct, we are done. */
2519 field
= TREE_OPERAND (ref
, 1);
2520 if (TREE_CHAIN (field
))
2524 /* The other options are ARRAY_REF, ARRAY_RANGE_REF, VIEW_CONVERT_EXPR.
2525 In all these cases, we might be accessing the last element, and
2526 although in practice this will probably never happen, it is legal for
2527 the indices of this last element to exceed the bounds of the array.
2528 Therefore, continue checking. */
2531 gcc_assert (INDIRECT_REF_P (ref
));
2535 /* Determine information about number of iterations a LOOP from the index
2536 IDX of a data reference accessed in STMT. Callback for for_each_index. */
2545 idx_infer_loop_bounds (tree base
, tree
*idx
, void *dta
)
2547 struct ilb_data
*data
= dta
;
2548 tree ev
, init
, step
;
2549 tree low
, high
, type
, next
;
2551 struct loop
*loop
= data
->loop
;
2553 if (TREE_CODE (base
) != ARRAY_REF
2554 || array_at_struct_end_p (base
))
2557 ev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, *idx
));
2558 init
= initial_condition (ev
);
2559 step
= evolution_part_in_loop_num (ev
, loop
->num
);
2563 || TREE_CODE (step
) != INTEGER_CST
2564 || integer_zerop (step
)
2565 || tree_contains_chrecs (init
, NULL
)
2566 || chrec_contains_symbols_defined_in_loop (init
, loop
->num
))
2569 low
= array_ref_low_bound (base
);
2570 high
= array_ref_up_bound (base
);
2572 /* The case of nonconstant bounds could be handled, but it would be
2574 if (TREE_CODE (low
) != INTEGER_CST
2576 || TREE_CODE (high
) != INTEGER_CST
)
2578 sign
= tree_int_cst_sign_bit (step
);
2579 type
= TREE_TYPE (step
);
2581 /* In case the relevant bound of the array does not fit in type, or
2582 it does, but bound + step (in type) still belongs into the range of the
2583 array, the index may wrap and still stay within the range of the array
2584 (consider e.g. if the array is indexed by the full range of
2587 To make things simpler, we require both bounds to fit into type, although
2588 there are cases where this would not be strictly necessary. */
2589 if (!int_fits_type_p (high
, type
)
2590 || !int_fits_type_p (low
, type
))
2592 low
= fold_convert (type
, low
);
2593 high
= fold_convert (type
, high
);
2596 next
= fold_binary (PLUS_EXPR
, type
, low
, step
);
2598 next
= fold_binary (PLUS_EXPR
, type
, high
, step
);
2600 if (tree_int_cst_compare (low
, next
) <= 0
2601 && tree_int_cst_compare (next
, high
) <= 0)
2604 record_nonwrapping_iv (loop
, init
, step
, data
->stmt
, low
, high
, true);
2608 /* Determine information about number of iterations a LOOP from the bounds
2609 of arrays in the data reference REF accessed in STMT. */
2612 infer_loop_bounds_from_ref (struct loop
*loop
, tree stmt
, tree ref
)
2614 struct ilb_data data
;
2618 for_each_index (&ref
, idx_infer_loop_bounds
, &data
);
2621 /* Determine information about number of iterations of a LOOP from the way
2622 arrays are used in STMT. */
2625 infer_loop_bounds_from_array (struct loop
*loop
, tree stmt
)
2629 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
2631 tree op0
= GIMPLE_STMT_OPERAND (stmt
, 0);
2632 tree op1
= GIMPLE_STMT_OPERAND (stmt
, 1);
2634 /* For each memory access, analyze its access function
2635 and record a bound on the loop iteration domain. */
2636 if (REFERENCE_CLASS_P (op0
))
2637 infer_loop_bounds_from_ref (loop
, stmt
, op0
);
2639 if (REFERENCE_CLASS_P (op1
))
2640 infer_loop_bounds_from_ref (loop
, stmt
, op1
);
2644 call
= get_call_expr_in (stmt
);
2648 call_expr_arg_iterator iter
;
2650 FOR_EACH_CALL_EXPR_ARG (arg
, iter
, call
)
2651 if (REFERENCE_CLASS_P (arg
))
2652 infer_loop_bounds_from_ref (loop
, stmt
, arg
);
2656 /* Determine information about number of iterations of a LOOP from the fact
2657 that signed arithmetics in STMT does not overflow. */
2660 infer_loop_bounds_from_signedness (struct loop
*loop
, tree stmt
)
2662 tree def
, base
, step
, scev
, type
, low
, high
;
2664 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
2667 def
= GIMPLE_STMT_OPERAND (stmt
, 0);
2669 if (TREE_CODE (def
) != SSA_NAME
)
2672 type
= TREE_TYPE (def
);
2673 if (!INTEGRAL_TYPE_P (type
)
2674 || !TYPE_OVERFLOW_UNDEFINED (type
))
2677 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
2678 if (chrec_contains_undetermined (scev
))
2681 base
= initial_condition_in_loop_num (scev
, loop
->num
);
2682 step
= evolution_part_in_loop_num (scev
, loop
->num
);
2685 || TREE_CODE (step
) != INTEGER_CST
2686 || tree_contains_chrecs (base
, NULL
)
2687 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
2690 low
= lower_bound_in_type (type
, type
);
2691 high
= upper_bound_in_type (type
, type
);
2693 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false);
2696 /* The following analyzers are extracting informations on the bounds
2697 of LOOP from the following undefined behaviors:
2699 - data references should not access elements over the statically
2702 - signed variables should not overflow when flag_wrapv is not set.
2706 infer_loop_bounds_from_undefined (struct loop
*loop
)
2710 block_stmt_iterator bsi
;
2713 bbs
= get_loop_body (loop
);
2715 for (i
= 0; i
< loop
->num_nodes
; i
++)
2719 /* If BB is not executed in each iteration of the loop, we cannot
2720 use it to infer any information about # of iterations of the loop. */
2721 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
2724 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
2726 tree stmt
= bsi_stmt (bsi
);
2728 infer_loop_bounds_from_array (loop
, stmt
);
2729 infer_loop_bounds_from_signedness (loop
, stmt
);
2737 /* Records estimates on numbers of iterations of LOOP. */
2740 estimate_numbers_of_iterations_loop (struct loop
*loop
)
2742 VEC (edge
, heap
) *exits
;
2745 struct tree_niter_desc niter_desc
;
2748 /* Give up if we already have tried to compute an estimation. */
2749 if (loop
->estimate_state
!= EST_NOT_COMPUTED
)
2751 loop
->estimate_state
= EST_NOT_AVAILABLE
;
2753 exits
= get_loop_exit_edges (loop
);
2754 for (i
= 0; VEC_iterate (edge
, exits
, i
, ex
); i
++)
2756 if (!number_of_iterations_exit (loop
, ex
, &niter_desc
, false))
2759 niter
= niter_desc
.niter
;
2760 type
= TREE_TYPE (niter
);
2761 if (TREE_CODE (niter_desc
.may_be_zero
) != INTEGER_CST
)
2762 niter
= build3 (COND_EXPR
, type
, niter_desc
.may_be_zero
,
2763 build_int_cst (type
, 0),
2765 record_estimate (loop
, niter
, niter_desc
.max
,
2766 last_stmt (ex
->src
),
2769 VEC_free (edge
, heap
, exits
);
2771 infer_loop_bounds_from_undefined (loop
);
2772 compute_estimated_nb_iterations (loop
);
2775 /* Records estimates on numbers of iterations of loops. */
2778 estimate_numbers_of_iterations (void)
2783 /* We don't want to issue signed overflow warnings while getting
2784 loop iteration estimates. */
2785 fold_defer_overflow_warnings ();
2787 FOR_EACH_LOOP (li
, loop
, 0)
2789 estimate_numbers_of_iterations_loop (loop
);
2792 fold_undefer_and_ignore_overflow_warnings ();
2795 /* Returns true if statement S1 dominates statement S2. */
2798 stmt_dominates_stmt_p (tree s1
, tree s2
)
2800 basic_block bb1
= bb_for_stmt (s1
), bb2
= bb_for_stmt (s2
);
2808 block_stmt_iterator bsi
;
2810 for (bsi
= bsi_start (bb1
); bsi_stmt (bsi
) != s2
; bsi_next (&bsi
))
2811 if (bsi_stmt (bsi
) == s1
)
2817 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
2820 /* Returns true when we can prove that the number of executions of
2821 STMT in the loop is at most NITER, according to the bound on
2822 the number of executions of the statement NITER_BOUND->stmt recorded in
2823 NITER_BOUND. If STMT is NULL, we must prove this bound for all
2824 statements in the loop. */
2827 n_of_executions_at_most (tree stmt
,
2828 struct nb_iter_bound
*niter_bound
,
2831 double_int bound
= niter_bound
->bound
;
2832 tree nit_type
= TREE_TYPE (niter
), e
;
2835 gcc_assert (TYPE_UNSIGNED (nit_type
));
2837 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
2838 the number of iterations is small. */
2839 if (!double_int_fits_to_tree_p (nit_type
, bound
))
2842 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
2843 times. This means that:
2845 -- if NITER_BOUND->is_exit is true, then everything before
2846 NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
2847 times, and everything after it at most NITER_BOUND->bound times.
2849 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
2850 is executed, then NITER_BOUND->stmt is executed as well in the same
2851 iteration (we conclude that if both statements belong to the same
2852 basic block, or if STMT is after NITER_BOUND->stmt), then STMT
2853 is executed at most NITER_BOUND->bound + 1 times. Otherwise STMT is
2854 executed at most NITER_BOUND->bound + 2 times. */
2856 if (niter_bound
->is_exit
)
2859 && stmt
!= niter_bound
->stmt
2860 && stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
2868 || (bb_for_stmt (stmt
) != bb_for_stmt (niter_bound
->stmt
)
2869 && !stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
)))
2871 bound
= double_int_add (bound
, double_int_one
);
2872 if (double_int_zero_p (bound
)
2873 || !double_int_fits_to_tree_p (nit_type
, bound
))
2879 e
= fold_binary (cmp
, boolean_type_node
,
2880 niter
, double_int_to_tree (nit_type
, bound
));
2881 return e
&& integer_nonzerop (e
);
2884 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
2887 nowrap_type_p (tree type
)
2889 if (INTEGRAL_TYPE_P (type
)
2890 && TYPE_OVERFLOW_UNDEFINED (type
))
2893 if (POINTER_TYPE_P (type
))
2899 /* Return false only when the induction variable BASE + STEP * I is
2900 known to not overflow: i.e. when the number of iterations is small
2901 enough with respect to the step and initial condition in order to
2902 keep the evolution confined in TYPEs bounds. Return true when the
2903 iv is known to overflow or when the property is not computable.
2905 USE_OVERFLOW_SEMANTICS is true if this function should assume that
2906 the rules for overflow of the given language apply (e.g., that signed
2907 arithmetics in C does not overflow). */
2910 scev_probably_wraps_p (tree base
, tree step
,
2911 tree at_stmt
, struct loop
*loop
,
2912 bool use_overflow_semantics
)
2914 struct nb_iter_bound
*bound
;
2915 tree delta
, step_abs
;
2916 tree unsigned_type
, valid_niter
;
2917 tree type
= TREE_TYPE (step
);
2919 /* FIXME: We really need something like
2920 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
2922 We used to test for the following situation that frequently appears
2923 during address arithmetics:
2925 D.1621_13 = (long unsigned intD.4) D.1620_12;
2926 D.1622_14 = D.1621_13 * 8;
2927 D.1623_15 = (doubleD.29 *) D.1622_14;
2929 And derived that the sequence corresponding to D_14
2930 can be proved to not wrap because it is used for computing a
2931 memory access; however, this is not really the case -- for example,
2932 if D_12 = (unsigned char) [254,+,1], then D_14 has values
2933 2032, 2040, 0, 8, ..., but the code is still legal. */
2935 if (chrec_contains_undetermined (base
)
2936 || chrec_contains_undetermined (step
)
2937 || TREE_CODE (step
) != INTEGER_CST
)
2940 if (integer_zerop (step
))
2943 /* If we can use the fact that signed and pointer arithmetics does not
2944 wrap, we are done. */
2945 if (use_overflow_semantics
&& nowrap_type_p (type
))
2948 /* Don't issue signed overflow warnings. */
2949 fold_defer_overflow_warnings ();
2951 /* Otherwise, compute the number of iterations before we reach the
2952 bound of the type, and verify that the loop is exited before this
2954 unsigned_type
= unsigned_type_for (type
);
2955 base
= fold_convert (unsigned_type
, base
);
2957 if (tree_int_cst_sign_bit (step
))
2959 tree extreme
= fold_convert (unsigned_type
,
2960 lower_bound_in_type (type
, type
));
2961 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
2962 step_abs
= fold_build1 (NEGATE_EXPR
, unsigned_type
,
2963 fold_convert (unsigned_type
, step
));
2967 tree extreme
= fold_convert (unsigned_type
,
2968 upper_bound_in_type (type
, type
));
2969 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
2970 step_abs
= fold_convert (unsigned_type
, step
);
2973 valid_niter
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step_abs
);
2975 estimate_numbers_of_iterations_loop (loop
);
2976 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
2978 if (n_of_executions_at_most (at_stmt
, bound
, valid_niter
))
2980 fold_undefer_and_ignore_overflow_warnings ();
2985 fold_undefer_and_ignore_overflow_warnings ();
2987 /* At this point we still don't have a proof that the iv does not
2988 overflow: give up. */
2992 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
2995 free_numbers_of_iterations_estimates_loop (struct loop
*loop
)
2997 struct nb_iter_bound
*bound
, *next
;
2999 loop
->nb_iterations
= NULL
;
3000 loop
->estimate_state
= EST_NOT_COMPUTED
;
3001 for (bound
= loop
->bounds
; bound
; bound
= next
)
3007 loop
->bounds
= NULL
;
3010 /* Frees the information on upper bounds on numbers of iterations of loops. */
3013 free_numbers_of_iterations_estimates (void)
3018 FOR_EACH_LOOP (li
, loop
, 0)
3020 free_numbers_of_iterations_estimates_loop (loop
);
3024 /* Substitute value VAL for ssa name NAME inside expressions held
3028 substitute_in_loop_info (struct loop
*loop
, tree name
, tree val
)
3030 loop
->nb_iterations
= simplify_replace_tree (loop
->nb_iterations
, name
, val
);