1 /* Functions to determine/estimate number of iterations of a loop.
2 Copyright (C) 2004-2013 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
26 #include "basic-block.h"
27 #include "gimple-pretty-print.h"
30 #include "gimple-ssa.h"
32 #include "tree-phinodes.h"
33 #include "ssa-iterators.h"
34 #include "tree-ssa-loop.h"
38 #include "tree-chrec.h"
39 #include "tree-scalar-evolution.h"
40 #include "tree-data-ref.h"
43 #include "diagnostic-core.h"
44 #include "tree-inline.h"
45 #include "tree-pass.h"
48 #define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
50 /* The maximum number of dominator BBs we search for conditions
51 of loop header copies we use for simplifying a conditional
53 #define MAX_DOMINATORS_TO_WALK 8
57 Analysis of number of iterations of an affine exit test.
61 /* Bounds on some value, BELOW <= X <= UP. */
69 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */
72 split_to_var_and_offset (tree expr
, tree
*var
, mpz_t offset
)
74 tree type
= TREE_TYPE (expr
);
80 mpz_set_ui (offset
, 0);
82 switch (TREE_CODE (expr
))
89 case POINTER_PLUS_EXPR
:
90 op0
= TREE_OPERAND (expr
, 0);
91 op1
= TREE_OPERAND (expr
, 1);
93 if (TREE_CODE (op1
) != INTEGER_CST
)
97 /* Always sign extend the offset. */
98 off
= tree_to_double_int (op1
);
99 off
= off
.sext (TYPE_PRECISION (type
));
100 mpz_set_double_int (offset
, off
, false);
102 mpz_neg (offset
, offset
);
106 *var
= build_int_cst_type (type
, 0);
107 off
= tree_to_double_int (expr
);
108 mpz_set_double_int (offset
, off
, TYPE_UNSIGNED (type
));
116 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
117 in TYPE to MIN and MAX. */
120 determine_value_range (tree type
, tree var
, mpz_t off
,
121 mpz_t min
, mpz_t max
)
123 /* If the expression is a constant, we know its value exactly. */
124 if (integer_zerop (var
))
131 /* If the computation may wrap, we know nothing about the value, except for
132 the range of the type. */
133 get_type_static_bounds (type
, min
, max
);
134 if (!nowrap_type_p (type
))
137 /* Since the addition of OFF does not wrap, if OFF is positive, then we may
138 add it to MIN, otherwise to MAX. */
139 if (mpz_sgn (off
) < 0)
140 mpz_add (max
, max
, off
);
142 mpz_add (min
, min
, off
);
145 /* Stores the bounds on the difference of the values of the expressions
146 (var + X) and (var + Y), computed in TYPE, to BNDS. */
149 bound_difference_of_offsetted_base (tree type
, mpz_t x
, mpz_t y
,
152 int rel
= mpz_cmp (x
, y
);
153 bool may_wrap
= !nowrap_type_p (type
);
156 /* If X == Y, then the expressions are always equal.
157 If X > Y, there are the following possibilities:
158 a) neither of var + X and var + Y overflow or underflow, or both of
159 them do. Then their difference is X - Y.
160 b) var + X overflows, and var + Y does not. Then the values of the
161 expressions are var + X - M and var + Y, where M is the range of
162 the type, and their difference is X - Y - M.
163 c) var + Y underflows and var + X does not. Their difference again
165 Therefore, if the arithmetics in type does not overflow, then the
166 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
167 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
168 (X - Y, X - Y + M). */
172 mpz_set_ui (bnds
->below
, 0);
173 mpz_set_ui (bnds
->up
, 0);
178 mpz_set_double_int (m
, double_int::mask (TYPE_PRECISION (type
)), true);
179 mpz_add_ui (m
, m
, 1);
180 mpz_sub (bnds
->up
, x
, y
);
181 mpz_set (bnds
->below
, bnds
->up
);
186 mpz_sub (bnds
->below
, bnds
->below
, m
);
188 mpz_add (bnds
->up
, bnds
->up
, m
);
194 /* From condition C0 CMP C1 derives information regarding the
195 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
196 and stores it to BNDS. */
199 refine_bounds_using_guard (tree type
, tree varx
, mpz_t offx
,
200 tree vary
, mpz_t offy
,
201 tree c0
, enum tree_code cmp
, tree c1
,
204 tree varc0
, varc1
, tmp
, ctype
;
205 mpz_t offc0
, offc1
, loffx
, loffy
, bnd
;
207 bool no_wrap
= nowrap_type_p (type
);
216 STRIP_SIGN_NOPS (c0
);
217 STRIP_SIGN_NOPS (c1
);
218 ctype
= TREE_TYPE (c0
);
219 if (!useless_type_conversion_p (ctype
, type
))
225 /* We could derive quite precise information from EQ_EXPR, however, such
226 a guard is unlikely to appear, so we do not bother with handling
231 /* NE_EXPR comparisons do not contain much of useful information, except for
232 special case of comparing with the bounds of the type. */
233 if (TREE_CODE (c1
) != INTEGER_CST
234 || !INTEGRAL_TYPE_P (type
))
237 /* Ensure that the condition speaks about an expression in the same type
239 ctype
= TREE_TYPE (c0
);
240 if (TYPE_PRECISION (ctype
) != TYPE_PRECISION (type
))
242 c0
= fold_convert (type
, c0
);
243 c1
= fold_convert (type
, c1
);
245 if (TYPE_MIN_VALUE (type
)
246 && operand_equal_p (c1
, TYPE_MIN_VALUE (type
), 0))
251 if (TYPE_MAX_VALUE (type
)
252 && operand_equal_p (c1
, TYPE_MAX_VALUE (type
), 0))
265 split_to_var_and_offset (expand_simple_operations (c0
), &varc0
, offc0
);
266 split_to_var_and_offset (expand_simple_operations (c1
), &varc1
, offc1
);
268 /* We are only interested in comparisons of expressions based on VARX and
269 VARY. TODO -- we might also be able to derive some bounds from
270 expressions containing just one of the variables. */
272 if (operand_equal_p (varx
, varc1
, 0))
274 tmp
= varc0
; varc0
= varc1
; varc1
= tmp
;
275 mpz_swap (offc0
, offc1
);
276 cmp
= swap_tree_comparison (cmp
);
279 if (!operand_equal_p (varx
, varc0
, 0)
280 || !operand_equal_p (vary
, varc1
, 0))
283 mpz_init_set (loffx
, offx
);
284 mpz_init_set (loffy
, offy
);
286 if (cmp
== GT_EXPR
|| cmp
== GE_EXPR
)
288 tmp
= varx
; varx
= vary
; vary
= tmp
;
289 mpz_swap (offc0
, offc1
);
290 mpz_swap (loffx
, loffy
);
291 cmp
= swap_tree_comparison (cmp
);
295 /* If there is no overflow, the condition implies that
297 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
299 The overflows and underflows may complicate things a bit; each
300 overflow decreases the appropriate offset by M, and underflow
301 increases it by M. The above inequality would not necessarily be
304 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
305 VARX + OFFC0 overflows, but VARX + OFFX does not.
306 This may only happen if OFFX < OFFC0.
307 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
308 VARY + OFFC1 underflows and VARY + OFFY does not.
309 This may only happen if OFFY > OFFC1. */
318 x_ok
= (integer_zerop (varx
)
319 || mpz_cmp (loffx
, offc0
) >= 0);
320 y_ok
= (integer_zerop (vary
)
321 || mpz_cmp (loffy
, offc1
) <= 0);
327 mpz_sub (bnd
, loffx
, loffy
);
328 mpz_add (bnd
, bnd
, offc1
);
329 mpz_sub (bnd
, bnd
, offc0
);
332 mpz_sub_ui (bnd
, bnd
, 1);
337 if (mpz_cmp (bnds
->below
, bnd
) < 0)
338 mpz_set (bnds
->below
, bnd
);
342 if (mpz_cmp (bnd
, bnds
->up
) < 0)
343 mpz_set (bnds
->up
, bnd
);
355 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
356 The subtraction is considered to be performed in arbitrary precision,
359 We do not attempt to be too clever regarding the value ranges of X and
360 Y; most of the time, they are just integers or ssa names offsetted by
361 integer. However, we try to use the information contained in the
362 comparisons before the loop (usually created by loop header copying). */
365 bound_difference (struct loop
*loop
, tree x
, tree y
, bounds
*bnds
)
367 tree type
= TREE_TYPE (x
);
370 mpz_t minx
, maxx
, miny
, maxy
;
378 /* Get rid of unnecessary casts, but preserve the value of
383 mpz_init (bnds
->below
);
387 split_to_var_and_offset (x
, &varx
, offx
);
388 split_to_var_and_offset (y
, &vary
, offy
);
390 if (!integer_zerop (varx
)
391 && operand_equal_p (varx
, vary
, 0))
393 /* Special case VARX == VARY -- we just need to compare the
394 offsets. The matters are a bit more complicated in the
395 case addition of offsets may wrap. */
396 bound_difference_of_offsetted_base (type
, offx
, offy
, bnds
);
400 /* Otherwise, use the value ranges to determine the initial
401 estimates on below and up. */
406 determine_value_range (type
, varx
, offx
, minx
, maxx
);
407 determine_value_range (type
, vary
, offy
, miny
, maxy
);
409 mpz_sub (bnds
->below
, minx
, maxy
);
410 mpz_sub (bnds
->up
, maxx
, miny
);
417 /* If both X and Y are constants, we cannot get any more precise. */
418 if (integer_zerop (varx
) && integer_zerop (vary
))
421 /* Now walk the dominators of the loop header and use the entry
422 guards to refine the estimates. */
423 for (bb
= loop
->header
;
424 bb
!= ENTRY_BLOCK_PTR
&& cnt
< MAX_DOMINATORS_TO_WALK
;
425 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
427 if (!single_pred_p (bb
))
429 e
= single_pred_edge (bb
);
431 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
434 cond
= last_stmt (e
->src
);
435 c0
= gimple_cond_lhs (cond
);
436 cmp
= gimple_cond_code (cond
);
437 c1
= gimple_cond_rhs (cond
);
439 if (e
->flags
& EDGE_FALSE_VALUE
)
440 cmp
= invert_tree_comparison (cmp
, false);
442 refine_bounds_using_guard (type
, varx
, offx
, vary
, offy
,
452 /* Update the bounds in BNDS that restrict the value of X to the bounds
453 that restrict the value of X + DELTA. X can be obtained as a
454 difference of two values in TYPE. */
457 bounds_add (bounds
*bnds
, double_int delta
, tree type
)
462 mpz_set_double_int (mdelta
, delta
, false);
465 mpz_set_double_int (max
, double_int::mask (TYPE_PRECISION (type
)), true);
467 mpz_add (bnds
->up
, bnds
->up
, mdelta
);
468 mpz_add (bnds
->below
, bnds
->below
, mdelta
);
470 if (mpz_cmp (bnds
->up
, max
) > 0)
471 mpz_set (bnds
->up
, max
);
474 if (mpz_cmp (bnds
->below
, max
) < 0)
475 mpz_set (bnds
->below
, max
);
481 /* Update the bounds in BNDS that restrict the value of X to the bounds
482 that restrict the value of -X. */
485 bounds_negate (bounds
*bnds
)
489 mpz_init_set (tmp
, bnds
->up
);
490 mpz_neg (bnds
->up
, bnds
->below
);
491 mpz_neg (bnds
->below
, tmp
);
495 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
498 inverse (tree x
, tree mask
)
500 tree type
= TREE_TYPE (x
);
502 unsigned ctr
= tree_floor_log2 (mask
);
504 if (TYPE_PRECISION (type
) <= HOST_BITS_PER_WIDE_INT
)
506 unsigned HOST_WIDE_INT ix
;
507 unsigned HOST_WIDE_INT imask
;
508 unsigned HOST_WIDE_INT irslt
= 1;
510 gcc_assert (cst_and_fits_in_hwi (x
));
511 gcc_assert (cst_and_fits_in_hwi (mask
));
513 ix
= int_cst_value (x
);
514 imask
= int_cst_value (mask
);
523 rslt
= build_int_cst_type (type
, irslt
);
527 rslt
= build_int_cst (type
, 1);
530 rslt
= int_const_binop (MULT_EXPR
, rslt
, x
);
531 x
= int_const_binop (MULT_EXPR
, x
, x
);
533 rslt
= int_const_binop (BIT_AND_EXPR
, rslt
, mask
);
539 /* Derives the upper bound BND on the number of executions of loop with exit
540 condition S * i <> C. If NO_OVERFLOW is true, then the control variable of
541 the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed
542 that the loop ends through this exit, i.e., the induction variable ever
543 reaches the value of C.
545 The value C is equal to final - base, where final and base are the final and
546 initial value of the actual induction variable in the analysed loop. BNDS
547 bounds the value of this difference when computed in signed type with
548 unbounded range, while the computation of C is performed in an unsigned
549 type with the range matching the range of the type of the induction variable.
550 In particular, BNDS.up contains an upper bound on C in the following cases:
551 -- if the iv must reach its final value without overflow, i.e., if
552 NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
553 -- if final >= base, which we know to hold when BNDS.below >= 0. */
556 number_of_iterations_ne_max (mpz_t bnd
, bool no_overflow
, tree c
, tree s
,
557 bounds
*bnds
, bool exit_must_be_taken
)
561 tree type
= TREE_TYPE (c
);
562 bool bnds_u_valid
= ((no_overflow
&& exit_must_be_taken
)
563 || mpz_sgn (bnds
->below
) >= 0);
566 || (TREE_CODE (c
) == INTEGER_CST
567 && TREE_CODE (s
) == INTEGER_CST
568 && tree_to_double_int (c
).mod (tree_to_double_int (s
),
569 TYPE_UNSIGNED (type
),
570 EXACT_DIV_EXPR
).is_zero ())
571 || (TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (c
))
572 && multiple_of_p (type
, c
, s
)))
574 /* If C is an exact multiple of S, then its value will be reached before
575 the induction variable overflows (unless the loop is exited in some
576 other way before). Note that the actual induction variable in the
577 loop (which ranges from base to final instead of from 0 to C) may
578 overflow, in which case BNDS.up will not be giving a correct upper
579 bound on C; thus, BNDS_U_VALID had to be computed in advance. */
581 exit_must_be_taken
= true;
584 /* If the induction variable can overflow, the number of iterations is at
585 most the period of the control variable (or infinite, but in that case
586 the whole # of iterations analysis will fail). */
589 max
= double_int::mask (TYPE_PRECISION (type
)
590 - tree_low_cst (num_ending_zeros (s
), 1));
591 mpz_set_double_int (bnd
, max
, true);
595 /* Now we know that the induction variable does not overflow, so the loop
596 iterates at most (range of type / S) times. */
597 mpz_set_double_int (bnd
, double_int::mask (TYPE_PRECISION (type
)), true);
599 /* If the induction variable is guaranteed to reach the value of C before
601 if (exit_must_be_taken
)
603 /* ... then we can strengthen this to C / S, and possibly we can use
604 the upper bound on C given by BNDS. */
605 if (TREE_CODE (c
) == INTEGER_CST
)
606 mpz_set_double_int (bnd
, tree_to_double_int (c
), true);
607 else if (bnds_u_valid
)
608 mpz_set (bnd
, bnds
->up
);
612 mpz_set_double_int (d
, tree_to_double_int (s
), true);
613 mpz_fdiv_q (bnd
, bnd
, d
);
617 /* Determines number of iterations of loop whose ending condition
618 is IV <> FINAL. TYPE is the type of the iv. The number of
619 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
620 we know that the exit must be taken eventually, i.e., that the IV
621 ever reaches the value FINAL (we derived this earlier, and possibly set
622 NITER->assumptions to make sure this is the case). BNDS contains the
623 bounds on the difference FINAL - IV->base. */
626 number_of_iterations_ne (tree type
, affine_iv
*iv
, tree final
,
627 struct tree_niter_desc
*niter
, bool exit_must_be_taken
,
630 tree niter_type
= unsigned_type_for (type
);
631 tree s
, c
, d
, bits
, assumption
, tmp
, bound
;
634 niter
->control
= *iv
;
635 niter
->bound
= final
;
636 niter
->cmp
= NE_EXPR
;
638 /* Rearrange the terms so that we get inequality S * i <> C, with S
639 positive. Also cast everything to the unsigned type. If IV does
640 not overflow, BNDS bounds the value of C. Also, this is the
641 case if the computation |FINAL - IV->base| does not overflow, i.e.,
642 if BNDS->below in the result is nonnegative. */
643 if (tree_int_cst_sign_bit (iv
->step
))
645 s
= fold_convert (niter_type
,
646 fold_build1 (NEGATE_EXPR
, type
, iv
->step
));
647 c
= fold_build2 (MINUS_EXPR
, niter_type
,
648 fold_convert (niter_type
, iv
->base
),
649 fold_convert (niter_type
, final
));
650 bounds_negate (bnds
);
654 s
= fold_convert (niter_type
, iv
->step
);
655 c
= fold_build2 (MINUS_EXPR
, niter_type
,
656 fold_convert (niter_type
, final
),
657 fold_convert (niter_type
, iv
->base
));
661 number_of_iterations_ne_max (max
, iv
->no_overflow
, c
, s
, bnds
,
663 niter
->max
= mpz_get_double_int (niter_type
, max
, false);
666 /* First the trivial cases -- when the step is 1. */
667 if (integer_onep (s
))
673 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
674 is infinite. Otherwise, the number of iterations is
675 (inverse(s/d) * (c/d)) mod (size of mode/d). */
676 bits
= num_ending_zeros (s
);
677 bound
= build_low_bits_mask (niter_type
,
678 (TYPE_PRECISION (niter_type
)
679 - tree_low_cst (bits
, 1)));
681 d
= fold_binary_to_constant (LSHIFT_EXPR
, niter_type
,
682 build_int_cst (niter_type
, 1), bits
);
683 s
= fold_binary_to_constant (RSHIFT_EXPR
, niter_type
, s
, bits
);
685 if (!exit_must_be_taken
)
687 /* If we cannot assume that the exit is taken eventually, record the
688 assumptions for divisibility of c. */
689 assumption
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, c
, d
);
690 assumption
= fold_build2 (EQ_EXPR
, boolean_type_node
,
691 assumption
, build_int_cst (niter_type
, 0));
692 if (!integer_nonzerop (assumption
))
693 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
694 niter
->assumptions
, assumption
);
697 c
= fold_build2 (EXACT_DIV_EXPR
, niter_type
, c
, d
);
698 tmp
= fold_build2 (MULT_EXPR
, niter_type
, c
, inverse (s
, bound
));
699 niter
->niter
= fold_build2 (BIT_AND_EXPR
, niter_type
, tmp
, bound
);
703 /* Checks whether we can determine the final value of the control variable
704 of the loop with ending condition IV0 < IV1 (computed in TYPE).
705 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
706 of the step. The assumptions necessary to ensure that the computation
707 of the final value does not overflow are recorded in NITER. If we
708 find the final value, we adjust DELTA and return TRUE. Otherwise
709 we return false. BNDS bounds the value of IV1->base - IV0->base,
710 and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
711 true if we know that the exit must be taken eventually. */
714 number_of_iterations_lt_to_ne (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
715 struct tree_niter_desc
*niter
,
716 tree
*delta
, tree step
,
717 bool exit_must_be_taken
, bounds
*bnds
)
719 tree niter_type
= TREE_TYPE (step
);
720 tree mod
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, *delta
, step
);
723 tree assumption
= boolean_true_node
, bound
, noloop
;
724 bool ret
= false, fv_comp_no_overflow
;
726 if (POINTER_TYPE_P (type
))
729 if (TREE_CODE (mod
) != INTEGER_CST
)
731 if (integer_nonzerop (mod
))
732 mod
= fold_build2 (MINUS_EXPR
, niter_type
, step
, mod
);
733 tmod
= fold_convert (type1
, mod
);
736 mpz_set_double_int (mmod
, tree_to_double_int (mod
), true);
737 mpz_neg (mmod
, mmod
);
739 /* If the induction variable does not overflow and the exit is taken,
740 then the computation of the final value does not overflow. This is
741 also obviously the case if the new final value is equal to the
742 current one. Finally, we postulate this for pointer type variables,
743 as the code cannot rely on the object to that the pointer points being
744 placed at the end of the address space (and more pragmatically,
745 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
746 if (integer_zerop (mod
) || POINTER_TYPE_P (type
))
747 fv_comp_no_overflow
= true;
748 else if (!exit_must_be_taken
)
749 fv_comp_no_overflow
= false;
751 fv_comp_no_overflow
=
752 (iv0
->no_overflow
&& integer_nonzerop (iv0
->step
))
753 || (iv1
->no_overflow
&& integer_nonzerop (iv1
->step
));
755 if (integer_nonzerop (iv0
->step
))
757 /* The final value of the iv is iv1->base + MOD, assuming that this
758 computation does not overflow, and that
759 iv0->base <= iv1->base + MOD. */
760 if (!fv_comp_no_overflow
)
762 bound
= fold_build2 (MINUS_EXPR
, type1
,
763 TYPE_MAX_VALUE (type1
), tmod
);
764 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
766 if (integer_zerop (assumption
))
769 if (mpz_cmp (mmod
, bnds
->below
) < 0)
770 noloop
= boolean_false_node
;
771 else if (POINTER_TYPE_P (type
))
772 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
774 fold_build_pointer_plus (iv1
->base
, tmod
));
776 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
778 fold_build2 (PLUS_EXPR
, type1
,
783 /* The final value of the iv is iv0->base - MOD, assuming that this
784 computation does not overflow, and that
785 iv0->base - MOD <= iv1->base. */
786 if (!fv_comp_no_overflow
)
788 bound
= fold_build2 (PLUS_EXPR
, type1
,
789 TYPE_MIN_VALUE (type1
), tmod
);
790 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
792 if (integer_zerop (assumption
))
795 if (mpz_cmp (mmod
, bnds
->below
) < 0)
796 noloop
= boolean_false_node
;
797 else if (POINTER_TYPE_P (type
))
798 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
799 fold_build_pointer_plus (iv0
->base
,
800 fold_build1 (NEGATE_EXPR
,
804 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
805 fold_build2 (MINUS_EXPR
, type1
,
810 if (!integer_nonzerop (assumption
))
811 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
814 if (!integer_zerop (noloop
))
815 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
818 bounds_add (bnds
, tree_to_double_int (mod
), type
);
819 *delta
= fold_build2 (PLUS_EXPR
, niter_type
, *delta
, mod
);
827 /* Add assertions to NITER that ensure that the control variable of the loop
828 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
829 are TYPE. Returns false if we can prove that there is an overflow, true
830 otherwise. STEP is the absolute value of the step. */
833 assert_no_overflow_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
834 struct tree_niter_desc
*niter
, tree step
)
836 tree bound
, d
, assumption
, diff
;
837 tree niter_type
= TREE_TYPE (step
);
839 if (integer_nonzerop (iv0
->step
))
841 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
842 if (iv0
->no_overflow
)
845 /* If iv0->base is a constant, we can determine the last value before
846 overflow precisely; otherwise we conservatively assume
849 if (TREE_CODE (iv0
->base
) == INTEGER_CST
)
851 d
= fold_build2 (MINUS_EXPR
, niter_type
,
852 fold_convert (niter_type
, TYPE_MAX_VALUE (type
)),
853 fold_convert (niter_type
, iv0
->base
));
854 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
857 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
858 build_int_cst (niter_type
, 1));
859 bound
= fold_build2 (MINUS_EXPR
, type
,
860 TYPE_MAX_VALUE (type
), fold_convert (type
, diff
));
861 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
866 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
867 if (iv1
->no_overflow
)
870 if (TREE_CODE (iv1
->base
) == INTEGER_CST
)
872 d
= fold_build2 (MINUS_EXPR
, niter_type
,
873 fold_convert (niter_type
, iv1
->base
),
874 fold_convert (niter_type
, TYPE_MIN_VALUE (type
)));
875 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
878 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
879 build_int_cst (niter_type
, 1));
880 bound
= fold_build2 (PLUS_EXPR
, type
,
881 TYPE_MIN_VALUE (type
), fold_convert (type
, diff
));
882 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
886 if (integer_zerop (assumption
))
888 if (!integer_nonzerop (assumption
))
889 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
890 niter
->assumptions
, assumption
);
892 iv0
->no_overflow
= true;
893 iv1
->no_overflow
= true;
897 /* Add an assumption to NITER that a loop whose ending condition
898 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
899 bounds the value of IV1->base - IV0->base. */
902 assert_loop_rolls_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
903 struct tree_niter_desc
*niter
, bounds
*bnds
)
905 tree assumption
= boolean_true_node
, bound
, diff
;
906 tree mbz
, mbzl
, mbzr
, type1
;
907 bool rolls_p
, no_overflow_p
;
911 /* We are going to compute the number of iterations as
912 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
913 variant of TYPE. This formula only works if
915 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
917 (where MAX is the maximum value of the unsigned variant of TYPE, and
918 the computations in this formula are performed in full precision,
919 i.e., without overflows).
921 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
922 we have a condition of the form iv0->base - step < iv1->base before the loop,
923 and for loops iv0->base < iv1->base - step * i the condition
924 iv0->base < iv1->base + step, due to loop header copying, which enable us
925 to prove the lower bound.
927 The upper bound is more complicated. Unless the expressions for initial
928 and final value themselves contain enough information, we usually cannot
929 derive it from the context. */
931 /* First check whether the answer does not follow from the bounds we gathered
933 if (integer_nonzerop (iv0
->step
))
934 dstep
= tree_to_double_int (iv0
->step
);
937 dstep
= tree_to_double_int (iv1
->step
).sext (TYPE_PRECISION (type
));
942 mpz_set_double_int (mstep
, dstep
, true);
943 mpz_neg (mstep
, mstep
);
944 mpz_add_ui (mstep
, mstep
, 1);
946 rolls_p
= mpz_cmp (mstep
, bnds
->below
) <= 0;
949 mpz_set_double_int (max
, double_int::mask (TYPE_PRECISION (type
)), true);
950 mpz_add (max
, max
, mstep
);
951 no_overflow_p
= (mpz_cmp (bnds
->up
, max
) <= 0
952 /* For pointers, only values lying inside a single object
953 can be compared or manipulated by pointer arithmetics.
954 Gcc in general does not allow or handle objects larger
955 than half of the address space, hence the upper bound
956 is satisfied for pointers. */
957 || POINTER_TYPE_P (type
));
961 if (rolls_p
&& no_overflow_p
)
965 if (POINTER_TYPE_P (type
))
968 /* Now the hard part; we must formulate the assumption(s) as expressions, and
969 we must be careful not to introduce overflow. */
971 if (integer_nonzerop (iv0
->step
))
973 diff
= fold_build2 (MINUS_EXPR
, type1
,
974 iv0
->step
, build_int_cst (type1
, 1));
976 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
977 0 address never belongs to any object, we can assume this for
979 if (!POINTER_TYPE_P (type
))
981 bound
= fold_build2 (PLUS_EXPR
, type1
,
982 TYPE_MIN_VALUE (type
), diff
);
983 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
987 /* And then we can compute iv0->base - diff, and compare it with
989 mbzl
= fold_build2 (MINUS_EXPR
, type1
,
990 fold_convert (type1
, iv0
->base
), diff
);
991 mbzr
= fold_convert (type1
, iv1
->base
);
995 diff
= fold_build2 (PLUS_EXPR
, type1
,
996 iv1
->step
, build_int_cst (type1
, 1));
998 if (!POINTER_TYPE_P (type
))
1000 bound
= fold_build2 (PLUS_EXPR
, type1
,
1001 TYPE_MAX_VALUE (type
), diff
);
1002 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
1006 mbzl
= fold_convert (type1
, iv0
->base
);
1007 mbzr
= fold_build2 (MINUS_EXPR
, type1
,
1008 fold_convert (type1
, iv1
->base
), diff
);
1011 if (!integer_nonzerop (assumption
))
1012 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1013 niter
->assumptions
, assumption
);
1016 mbz
= fold_build2 (GT_EXPR
, boolean_type_node
, mbzl
, mbzr
);
1017 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1018 niter
->may_be_zero
, mbz
);
1022 /* Determines number of iterations of loop whose ending condition
1023 is IV0 < IV1. TYPE is the type of the iv. The number of
1024 iterations is stored to NITER. BNDS bounds the difference
1025 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
1026 that the exit must be taken eventually. */
1029 number_of_iterations_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1030 struct tree_niter_desc
*niter
,
1031 bool exit_must_be_taken
, bounds
*bnds
)
1033 tree niter_type
= unsigned_type_for (type
);
1034 tree delta
, step
, s
;
1037 if (integer_nonzerop (iv0
->step
))
1039 niter
->control
= *iv0
;
1040 niter
->cmp
= LT_EXPR
;
1041 niter
->bound
= iv1
->base
;
1045 niter
->control
= *iv1
;
1046 niter
->cmp
= GT_EXPR
;
1047 niter
->bound
= iv0
->base
;
1050 delta
= fold_build2 (MINUS_EXPR
, niter_type
,
1051 fold_convert (niter_type
, iv1
->base
),
1052 fold_convert (niter_type
, iv0
->base
));
1054 /* First handle the special case that the step is +-1. */
1055 if ((integer_onep (iv0
->step
) && integer_zerop (iv1
->step
))
1056 || (integer_all_onesp (iv1
->step
) && integer_zerop (iv0
->step
)))
1058 /* for (i = iv0->base; i < iv1->base; i++)
1062 for (i = iv1->base; i > iv0->base; i--).
1064 In both cases # of iterations is iv1->base - iv0->base, assuming that
1065 iv1->base >= iv0->base.
1067 First try to derive a lower bound on the value of
1068 iv1->base - iv0->base, computed in full precision. If the difference
1069 is nonnegative, we are done, otherwise we must record the
1072 if (mpz_sgn (bnds
->below
) < 0)
1073 niter
->may_be_zero
= fold_build2 (LT_EXPR
, boolean_type_node
,
1074 iv1
->base
, iv0
->base
);
1075 niter
->niter
= delta
;
1076 niter
->max
= mpz_get_double_int (niter_type
, bnds
->up
, false);
1080 if (integer_nonzerop (iv0
->step
))
1081 step
= fold_convert (niter_type
, iv0
->step
);
1083 step
= fold_convert (niter_type
,
1084 fold_build1 (NEGATE_EXPR
, type
, iv1
->step
));
1086 /* If we can determine the final value of the control iv exactly, we can
1087 transform the condition to != comparison. In particular, this will be
1088 the case if DELTA is constant. */
1089 if (number_of_iterations_lt_to_ne (type
, iv0
, iv1
, niter
, &delta
, step
,
1090 exit_must_be_taken
, bnds
))
1094 zps
.base
= build_int_cst (niter_type
, 0);
1096 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1097 zps does not overflow. */
1098 zps
.no_overflow
= true;
1100 return number_of_iterations_ne (type
, &zps
, delta
, niter
, true, bnds
);
1103 /* Make sure that the control iv does not overflow. */
1104 if (!assert_no_overflow_lt (type
, iv0
, iv1
, niter
, step
))
1107 /* We determine the number of iterations as (delta + step - 1) / step. For
1108 this to work, we must know that iv1->base >= iv0->base - step + 1,
1109 otherwise the loop does not roll. */
1110 assert_loop_rolls_lt (type
, iv0
, iv1
, niter
, bnds
);
1112 s
= fold_build2 (MINUS_EXPR
, niter_type
,
1113 step
, build_int_cst (niter_type
, 1));
1114 delta
= fold_build2 (PLUS_EXPR
, niter_type
, delta
, s
);
1115 niter
->niter
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, delta
, step
);
1119 mpz_set_double_int (mstep
, tree_to_double_int (step
), true);
1120 mpz_add (tmp
, bnds
->up
, mstep
);
1121 mpz_sub_ui (tmp
, tmp
, 1);
1122 mpz_fdiv_q (tmp
, tmp
, mstep
);
1123 niter
->max
= mpz_get_double_int (niter_type
, tmp
, false);
1130 /* Determines number of iterations of loop whose ending condition
1131 is IV0 <= IV1. TYPE is the type of the iv. The number of
1132 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
1133 we know that this condition must eventually become false (we derived this
1134 earlier, and possibly set NITER->assumptions to make sure this
1135 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1138 number_of_iterations_le (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1139 struct tree_niter_desc
*niter
, bool exit_must_be_taken
,
1144 if (POINTER_TYPE_P (type
))
1147 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1148 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1149 value of the type. This we must know anyway, since if it is
1150 equal to this value, the loop rolls forever. We do not check
1151 this condition for pointer type ivs, as the code cannot rely on
1152 the object to that the pointer points being placed at the end of
1153 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1154 not defined for pointers). */
1156 if (!exit_must_be_taken
&& !POINTER_TYPE_P (type
))
1158 if (integer_nonzerop (iv0
->step
))
1159 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1160 iv1
->base
, TYPE_MAX_VALUE (type
));
1162 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1163 iv0
->base
, TYPE_MIN_VALUE (type
));
1165 if (integer_zerop (assumption
))
1167 if (!integer_nonzerop (assumption
))
1168 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1169 niter
->assumptions
, assumption
);
1172 if (integer_nonzerop (iv0
->step
))
1174 if (POINTER_TYPE_P (type
))
1175 iv1
->base
= fold_build_pointer_plus_hwi (iv1
->base
, 1);
1177 iv1
->base
= fold_build2 (PLUS_EXPR
, type1
, iv1
->base
,
1178 build_int_cst (type1
, 1));
1180 else if (POINTER_TYPE_P (type
))
1181 iv0
->base
= fold_build_pointer_plus_hwi (iv0
->base
, -1);
1183 iv0
->base
= fold_build2 (MINUS_EXPR
, type1
,
1184 iv0
->base
, build_int_cst (type1
, 1));
1186 bounds_add (bnds
, double_int_one
, type1
);
1188 return number_of_iterations_lt (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1192 /* Dumps description of affine induction variable IV to FILE. */
1195 dump_affine_iv (FILE *file
, affine_iv
*iv
)
1197 if (!integer_zerop (iv
->step
))
1198 fprintf (file
, "[");
1200 print_generic_expr (dump_file
, iv
->base
, TDF_SLIM
);
1202 if (!integer_zerop (iv
->step
))
1204 fprintf (file
, ", + , ");
1205 print_generic_expr (dump_file
, iv
->step
, TDF_SLIM
);
1206 fprintf (file
, "]%s", iv
->no_overflow
? "(no_overflow)" : "");
1210 /* Determine the number of iterations according to condition (for staying
1211 inside loop) which compares two induction variables using comparison
1212 operator CODE. The induction variable on left side of the comparison
1213 is IV0, the right-hand side is IV1. Both induction variables must have
1214 type TYPE, which must be an integer or pointer type. The steps of the
1215 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1217 LOOP is the loop whose number of iterations we are determining.
1219 ONLY_EXIT is true if we are sure this is the only way the loop could be
1220 exited (including possibly non-returning function calls, exceptions, etc.)
1221 -- in this case we can use the information whether the control induction
1222 variables can overflow or not in a more efficient way.
1224 if EVERY_ITERATION is true, we know the test is executed on every iteration.
1226 The results (number of iterations and assumptions as described in
1227 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
1228 Returns false if it fails to determine number of iterations, true if it
1229 was determined (possibly with some assumptions). */
1232 number_of_iterations_cond (struct loop
*loop
,
1233 tree type
, affine_iv
*iv0
, enum tree_code code
,
1234 affine_iv
*iv1
, struct tree_niter_desc
*niter
,
1235 bool only_exit
, bool every_iteration
)
1237 bool exit_must_be_taken
= false, ret
;
1240 /* If the test is not executed every iteration, wrapping may make the test
1242 TODO: the overflow case can be still used as unreliable estimate of upper
1243 bound. But we have no API to pass it down to number of iterations code
1244 and, at present, it will not use it anyway. */
1245 if (!every_iteration
1246 && (!iv0
->no_overflow
|| !iv1
->no_overflow
1247 || code
== NE_EXPR
|| code
== EQ_EXPR
))
1250 /* The meaning of these assumptions is this:
1252 then the rest of information does not have to be valid
1253 if may_be_zero then the loop does not roll, even if
1255 niter
->assumptions
= boolean_true_node
;
1256 niter
->may_be_zero
= boolean_false_node
;
1257 niter
->niter
= NULL_TREE
;
1258 niter
->max
= double_int_zero
;
1260 niter
->bound
= NULL_TREE
;
1261 niter
->cmp
= ERROR_MARK
;
1263 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1264 the control variable is on lhs. */
1265 if (code
== GE_EXPR
|| code
== GT_EXPR
1266 || (code
== NE_EXPR
&& integer_zerop (iv0
->step
)))
1269 code
= swap_tree_comparison (code
);
1272 if (POINTER_TYPE_P (type
))
1274 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1275 to the same object. If they do, the control variable cannot wrap
1276 (as wrap around the bounds of memory will never return a pointer
1277 that would be guaranteed to point to the same object, even if we
1278 avoid undefined behavior by casting to size_t and back). */
1279 iv0
->no_overflow
= true;
1280 iv1
->no_overflow
= true;
1283 /* If the control induction variable does not overflow and the only exit
1284 from the loop is the one that we analyze, we know it must be taken
1288 if (!integer_zerop (iv0
->step
) && iv0
->no_overflow
)
1289 exit_must_be_taken
= true;
1290 else if (!integer_zerop (iv1
->step
) && iv1
->no_overflow
)
1291 exit_must_be_taken
= true;
1294 /* We can handle the case when neither of the sides of the comparison is
1295 invariant, provided that the test is NE_EXPR. This rarely occurs in
1296 practice, but it is simple enough to manage. */
1297 if (!integer_zerop (iv0
->step
) && !integer_zerop (iv1
->step
))
1299 tree step_type
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1300 if (code
!= NE_EXPR
)
1303 iv0
->step
= fold_binary_to_constant (MINUS_EXPR
, step_type
,
1304 iv0
->step
, iv1
->step
);
1305 iv0
->no_overflow
= false;
1306 iv1
->step
= build_int_cst (step_type
, 0);
1307 iv1
->no_overflow
= true;
1310 /* If the result of the comparison is a constant, the loop is weird. More
1311 precise handling would be possible, but the situation is not common enough
1312 to waste time on it. */
1313 if (integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
))
1316 /* Ignore loops of while (i-- < 10) type. */
1317 if (code
!= NE_EXPR
)
1319 if (iv0
->step
&& tree_int_cst_sign_bit (iv0
->step
))
1322 if (!integer_zerop (iv1
->step
) && !tree_int_cst_sign_bit (iv1
->step
))
1326 /* If the loop exits immediately, there is nothing to do. */
1327 tree tem
= fold_binary (code
, boolean_type_node
, iv0
->base
, iv1
->base
);
1328 if (tem
&& integer_zerop (tem
))
1330 niter
->niter
= build_int_cst (unsigned_type_for (type
), 0);
1331 niter
->max
= double_int_zero
;
1335 /* OK, now we know we have a senseful loop. Handle several cases, depending
1336 on what comparison operator is used. */
1337 bound_difference (loop
, iv1
->base
, iv0
->base
, &bnds
);
1339 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1342 "Analyzing # of iterations of loop %d\n", loop
->num
);
1344 fprintf (dump_file
, " exit condition ");
1345 dump_affine_iv (dump_file
, iv0
);
1346 fprintf (dump_file
, " %s ",
1347 code
== NE_EXPR
? "!="
1348 : code
== LT_EXPR
? "<"
1350 dump_affine_iv (dump_file
, iv1
);
1351 fprintf (dump_file
, "\n");
1353 fprintf (dump_file
, " bounds on difference of bases: ");
1354 mpz_out_str (dump_file
, 10, bnds
.below
);
1355 fprintf (dump_file
, " ... ");
1356 mpz_out_str (dump_file
, 10, bnds
.up
);
1357 fprintf (dump_file
, "\n");
1363 gcc_assert (integer_zerop (iv1
->step
));
1364 ret
= number_of_iterations_ne (type
, iv0
, iv1
->base
, niter
,
1365 exit_must_be_taken
, &bnds
);
1369 ret
= number_of_iterations_lt (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1374 ret
= number_of_iterations_le (type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1382 mpz_clear (bnds
.up
);
1383 mpz_clear (bnds
.below
);
1385 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1389 fprintf (dump_file
, " result:\n");
1390 if (!integer_nonzerop (niter
->assumptions
))
1392 fprintf (dump_file
, " under assumptions ");
1393 print_generic_expr (dump_file
, niter
->assumptions
, TDF_SLIM
);
1394 fprintf (dump_file
, "\n");
1397 if (!integer_zerop (niter
->may_be_zero
))
1399 fprintf (dump_file
, " zero if ");
1400 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
1401 fprintf (dump_file
, "\n");
1404 fprintf (dump_file
, " # of iterations ");
1405 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
1406 fprintf (dump_file
, ", bounded by ");
1407 dump_double_int (dump_file
, niter
->max
, true);
1408 fprintf (dump_file
, "\n");
1411 fprintf (dump_file
, " failed\n\n");
1416 /* Substitute NEW for OLD in EXPR and fold the result. */
1419 simplify_replace_tree (tree expr
, tree old
, tree new_tree
)
1422 tree ret
= NULL_TREE
, e
, se
;
1427 /* Do not bother to replace constants. */
1428 if (CONSTANT_CLASS_P (old
))
1432 || operand_equal_p (expr
, old
, 0))
1433 return unshare_expr (new_tree
);
1438 n
= TREE_OPERAND_LENGTH (expr
);
1439 for (i
= 0; i
< n
; i
++)
1441 e
= TREE_OPERAND (expr
, i
);
1442 se
= simplify_replace_tree (e
, old
, new_tree
);
1447 ret
= copy_node (expr
);
1449 TREE_OPERAND (ret
, i
) = se
;
1452 return (ret
? fold (ret
) : expr
);
1455 /* Expand definitions of ssa names in EXPR as long as they are simple
1456 enough, and return the new expression. */
1459 expand_simple_operations (tree expr
)
1462 tree ret
= NULL_TREE
, e
, ee
, e1
;
1463 enum tree_code code
;
1466 if (expr
== NULL_TREE
)
1469 if (is_gimple_min_invariant (expr
))
1472 code
= TREE_CODE (expr
);
1473 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
1475 n
= TREE_OPERAND_LENGTH (expr
);
1476 for (i
= 0; i
< n
; i
++)
1478 e
= TREE_OPERAND (expr
, i
);
1479 ee
= expand_simple_operations (e
);
1484 ret
= copy_node (expr
);
1486 TREE_OPERAND (ret
, i
) = ee
;
1492 fold_defer_overflow_warnings ();
1494 fold_undefer_and_ignore_overflow_warnings ();
1498 if (TREE_CODE (expr
) != SSA_NAME
)
1501 stmt
= SSA_NAME_DEF_STMT (expr
);
1502 if (gimple_code (stmt
) == GIMPLE_PHI
)
1504 basic_block src
, dest
;
1506 if (gimple_phi_num_args (stmt
) != 1)
1508 e
= PHI_ARG_DEF (stmt
, 0);
1510 /* Avoid propagating through loop exit phi nodes, which
1511 could break loop-closed SSA form restrictions. */
1512 dest
= gimple_bb (stmt
);
1513 src
= single_pred (dest
);
1514 if (TREE_CODE (e
) == SSA_NAME
1515 && src
->loop_father
!= dest
->loop_father
)
1518 return expand_simple_operations (e
);
1520 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1523 /* Avoid expanding to expressions that contain SSA names that need
1524 to take part in abnormal coalescing. */
1526 FOR_EACH_SSA_TREE_OPERAND (e
, stmt
, iter
, SSA_OP_USE
)
1527 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (e
))
1530 e
= gimple_assign_rhs1 (stmt
);
1531 code
= gimple_assign_rhs_code (stmt
);
1532 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1534 if (is_gimple_min_invariant (e
))
1537 if (code
== SSA_NAME
)
1538 return expand_simple_operations (e
);
1546 /* Casts are simple. */
1547 ee
= expand_simple_operations (e
);
1548 return fold_build1 (code
, TREE_TYPE (expr
), ee
);
1552 case POINTER_PLUS_EXPR
:
1553 /* And increments and decrements by a constant are simple. */
1554 e1
= gimple_assign_rhs2 (stmt
);
1555 if (!is_gimple_min_invariant (e1
))
1558 ee
= expand_simple_operations (e
);
1559 return fold_build2 (code
, TREE_TYPE (expr
), ee
, e1
);
1566 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1567 expression (or EXPR unchanged, if no simplification was possible). */
1570 tree_simplify_using_condition_1 (tree cond
, tree expr
)
1573 tree e
, te
, e0
, e1
, e2
, notcond
;
1574 enum tree_code code
= TREE_CODE (expr
);
1576 if (code
== INTEGER_CST
)
1579 if (code
== TRUTH_OR_EXPR
1580 || code
== TRUTH_AND_EXPR
1581 || code
== COND_EXPR
)
1585 e0
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 0));
1586 if (TREE_OPERAND (expr
, 0) != e0
)
1589 e1
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 1));
1590 if (TREE_OPERAND (expr
, 1) != e1
)
1593 if (code
== COND_EXPR
)
1595 e2
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 2));
1596 if (TREE_OPERAND (expr
, 2) != e2
)
1604 if (code
== COND_EXPR
)
1605 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1607 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1613 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
1614 propagation, and vice versa. Fold does not handle this, since it is
1615 considered too expensive. */
1616 if (TREE_CODE (cond
) == EQ_EXPR
)
1618 e0
= TREE_OPERAND (cond
, 0);
1619 e1
= TREE_OPERAND (cond
, 1);
1621 /* We know that e0 == e1. Check whether we cannot simplify expr
1623 e
= simplify_replace_tree (expr
, e0
, e1
);
1624 if (integer_zerop (e
) || integer_nonzerop (e
))
1627 e
= simplify_replace_tree (expr
, e1
, e0
);
1628 if (integer_zerop (e
) || integer_nonzerop (e
))
1631 if (TREE_CODE (expr
) == EQ_EXPR
)
1633 e0
= TREE_OPERAND (expr
, 0);
1634 e1
= TREE_OPERAND (expr
, 1);
1636 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
1637 e
= simplify_replace_tree (cond
, e0
, e1
);
1638 if (integer_zerop (e
))
1640 e
= simplify_replace_tree (cond
, e1
, e0
);
1641 if (integer_zerop (e
))
1644 if (TREE_CODE (expr
) == NE_EXPR
)
1646 e0
= TREE_OPERAND (expr
, 0);
1647 e1
= TREE_OPERAND (expr
, 1);
1649 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
1650 e
= simplify_replace_tree (cond
, e0
, e1
);
1651 if (integer_zerop (e
))
1652 return boolean_true_node
;
1653 e
= simplify_replace_tree (cond
, e1
, e0
);
1654 if (integer_zerop (e
))
1655 return boolean_true_node
;
1658 te
= expand_simple_operations (expr
);
1660 /* Check whether COND ==> EXPR. */
1661 notcond
= invert_truthvalue (cond
);
1662 e
= fold_binary (TRUTH_OR_EXPR
, boolean_type_node
, notcond
, te
);
1663 if (e
&& integer_nonzerop (e
))
1666 /* Check whether COND ==> not EXPR. */
1667 e
= fold_binary (TRUTH_AND_EXPR
, boolean_type_node
, cond
, te
);
1668 if (e
&& integer_zerop (e
))
1674 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1675 expression (or EXPR unchanged, if no simplification was possible).
1676 Wrapper around tree_simplify_using_condition_1 that ensures that chains
1677 of simple operations in definitions of ssa names in COND are expanded,
1678 so that things like casts or incrementing the value of the bound before
1679 the loop do not cause us to fail. */
1682 tree_simplify_using_condition (tree cond
, tree expr
)
1684 cond
= expand_simple_operations (cond
);
1686 return tree_simplify_using_condition_1 (cond
, expr
);
1689 /* Tries to simplify EXPR using the conditions on entry to LOOP.
1690 Returns the simplified expression (or EXPR unchanged, if no
1691 simplification was possible).*/
1694 simplify_using_initial_conditions (struct loop
*loop
, tree expr
)
1702 if (TREE_CODE (expr
) == INTEGER_CST
)
1705 /* Limit walking the dominators to avoid quadraticness in
1706 the number of BBs times the number of loops in degenerate
1708 for (bb
= loop
->header
;
1709 bb
!= ENTRY_BLOCK_PTR
&& cnt
< MAX_DOMINATORS_TO_WALK
;
1710 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
1712 if (!single_pred_p (bb
))
1714 e
= single_pred_edge (bb
);
1716 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
1719 stmt
= last_stmt (e
->src
);
1720 cond
= fold_build2 (gimple_cond_code (stmt
),
1722 gimple_cond_lhs (stmt
),
1723 gimple_cond_rhs (stmt
));
1724 if (e
->flags
& EDGE_FALSE_VALUE
)
1725 cond
= invert_truthvalue (cond
);
1726 expr
= tree_simplify_using_condition (cond
, expr
);
1733 /* Tries to simplify EXPR using the evolutions of the loop invariants
1734 in the superloops of LOOP. Returns the simplified expression
1735 (or EXPR unchanged, if no simplification was possible). */
1738 simplify_using_outer_evolutions (struct loop
*loop
, tree expr
)
1740 enum tree_code code
= TREE_CODE (expr
);
1744 if (is_gimple_min_invariant (expr
))
1747 if (code
== TRUTH_OR_EXPR
1748 || code
== TRUTH_AND_EXPR
1749 || code
== COND_EXPR
)
1753 e0
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 0));
1754 if (TREE_OPERAND (expr
, 0) != e0
)
1757 e1
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 1));
1758 if (TREE_OPERAND (expr
, 1) != e1
)
1761 if (code
== COND_EXPR
)
1763 e2
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 2));
1764 if (TREE_OPERAND (expr
, 2) != e2
)
1772 if (code
== COND_EXPR
)
1773 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
1775 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
1781 e
= instantiate_parameters (loop
, expr
);
1782 if (is_gimple_min_invariant (e
))
1788 /* Returns true if EXIT is the only possible exit from LOOP. */
1791 loop_only_exit_p (const struct loop
*loop
, const_edge exit
)
1794 gimple_stmt_iterator bsi
;
1798 if (exit
!= single_exit (loop
))
1801 body
= get_loop_body (loop
);
1802 for (i
= 0; i
< loop
->num_nodes
; i
++)
1804 for (bsi
= gsi_start_bb (body
[i
]); !gsi_end_p (bsi
); gsi_next (&bsi
))
1806 call
= gsi_stmt (bsi
);
1807 if (gimple_code (call
) != GIMPLE_CALL
)
1810 if (gimple_has_side_effects (call
))
1822 /* Stores description of number of iterations of LOOP derived from
1823 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
1824 useful information could be derived (and fields of NITER has
1825 meaning described in comments at struct tree_niter_desc
1826 declaration), false otherwise. If WARN is true and
1827 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1828 potentially unsafe assumptions.
1829 When EVERY_ITERATION is true, only tests that are known to be executed
1830 every iteration are considered (i.e. only test that alone bounds the loop).
1834 number_of_iterations_exit (struct loop
*loop
, edge exit
,
1835 struct tree_niter_desc
*niter
,
1836 bool warn
, bool every_iteration
)
1841 enum tree_code code
;
1845 safe
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit
->src
);
1847 if (every_iteration
&& !safe
)
1850 niter
->assumptions
= boolean_false_node
;
1851 stmt
= last_stmt (exit
->src
);
1852 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
1855 /* We want the condition for staying inside loop. */
1856 code
= gimple_cond_code (stmt
);
1857 if (exit
->flags
& EDGE_TRUE_VALUE
)
1858 code
= invert_tree_comparison (code
, false);
1873 op0
= gimple_cond_lhs (stmt
);
1874 op1
= gimple_cond_rhs (stmt
);
1875 type
= TREE_TYPE (op0
);
1877 if (TREE_CODE (type
) != INTEGER_TYPE
1878 && !POINTER_TYPE_P (type
))
1881 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op0
, &iv0
, false))
1883 if (!simple_iv (loop
, loop_containing_stmt (stmt
), op1
, &iv1
, false))
1886 /* We don't want to see undefined signed overflow warnings while
1887 computing the number of iterations. */
1888 fold_defer_overflow_warnings ();
1890 iv0
.base
= expand_simple_operations (iv0
.base
);
1891 iv1
.base
= expand_simple_operations (iv1
.base
);
1892 if (!number_of_iterations_cond (loop
, type
, &iv0
, code
, &iv1
, niter
,
1893 loop_only_exit_p (loop
, exit
), safe
))
1895 fold_undefer_and_ignore_overflow_warnings ();
1901 niter
->assumptions
= simplify_using_outer_evolutions (loop
,
1902 niter
->assumptions
);
1903 niter
->may_be_zero
= simplify_using_outer_evolutions (loop
,
1904 niter
->may_be_zero
);
1905 niter
->niter
= simplify_using_outer_evolutions (loop
, niter
->niter
);
1909 = simplify_using_initial_conditions (loop
,
1910 niter
->assumptions
);
1912 = simplify_using_initial_conditions (loop
,
1913 niter
->may_be_zero
);
1915 fold_undefer_and_ignore_overflow_warnings ();
1917 /* If NITER has simplified into a constant, update MAX. */
1918 if (TREE_CODE (niter
->niter
) == INTEGER_CST
)
1919 niter
->max
= tree_to_double_int (niter
->niter
);
1921 if (integer_onep (niter
->assumptions
))
1924 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1925 But if we can prove that there is overflow or some other source of weird
1926 behavior, ignore the loop even with -funsafe-loop-optimizations. */
1927 if (integer_zerop (niter
->assumptions
) || !single_exit (loop
))
1930 if (flag_unsafe_loop_optimizations
)
1931 niter
->assumptions
= boolean_true_node
;
1935 const char *wording
;
1936 location_t loc
= gimple_location (stmt
);
1938 /* We can provide a more specific warning if one of the operator is
1939 constant and the other advances by +1 or -1. */
1940 if (!integer_zerop (iv1
.step
)
1941 ? (integer_zerop (iv0
.step
)
1942 && (integer_onep (iv1
.step
) || integer_all_onesp (iv1
.step
)))
1943 : (integer_onep (iv0
.step
) || integer_all_onesp (iv0
.step
)))
1945 flag_unsafe_loop_optimizations
1946 ? N_("assuming that the loop is not infinite")
1947 : N_("cannot optimize possibly infinite loops");
1950 flag_unsafe_loop_optimizations
1951 ? N_("assuming that the loop counter does not overflow")
1952 : N_("cannot optimize loop, the loop counter may overflow");
1954 warning_at ((LOCATION_LINE (loc
) > 0) ? loc
: input_location
,
1955 OPT_Wunsafe_loop_optimizations
, "%s", gettext (wording
));
1958 return flag_unsafe_loop_optimizations
;
1961 /* Try to determine the number of iterations of LOOP. If we succeed,
1962 expression giving number of iterations is returned and *EXIT is
1963 set to the edge from that the information is obtained. Otherwise
1964 chrec_dont_know is returned. */
1967 find_loop_niter (struct loop
*loop
, edge
*exit
)
1970 vec
<edge
> exits
= get_loop_exit_edges (loop
);
1972 tree niter
= NULL_TREE
, aniter
;
1973 struct tree_niter_desc desc
;
1976 FOR_EACH_VEC_ELT (exits
, i
, ex
)
1978 if (!number_of_iterations_exit (loop
, ex
, &desc
, false))
1981 if (integer_nonzerop (desc
.may_be_zero
))
1983 /* We exit in the first iteration through this exit.
1984 We won't find anything better. */
1985 niter
= build_int_cst (unsigned_type_node
, 0);
1990 if (!integer_zerop (desc
.may_be_zero
))
1993 aniter
= desc
.niter
;
1997 /* Nothing recorded yet. */
2003 /* Prefer constants, the lower the better. */
2004 if (TREE_CODE (aniter
) != INTEGER_CST
)
2007 if (TREE_CODE (niter
) != INTEGER_CST
)
2014 if (tree_int_cst_lt (aniter
, niter
))
2023 return niter
? niter
: chrec_dont_know
;
2026 /* Return true if loop is known to have bounded number of iterations. */
2029 finite_loop_p (struct loop
*loop
)
2034 if (flag_unsafe_loop_optimizations
)
2036 flags
= flags_from_decl_or_type (current_function_decl
);
2037 if ((flags
& (ECF_CONST
|ECF_PURE
)) && !(flags
& ECF_LOOPING_CONST_OR_PURE
))
2039 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2040 fprintf (dump_file
, "Found loop %i to be finite: it is within pure or const function.\n",
2045 if (loop
->any_upper_bound
2046 || max_loop_iterations (loop
, &nit
))
2048 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2049 fprintf (dump_file
, "Found loop %i to be finite: upper bound found.\n",
2058 Analysis of a number of iterations of a loop by a brute-force evaluation.
2062 /* Bound on the number of iterations we try to evaluate. */
2064 #define MAX_ITERATIONS_TO_TRACK \
2065 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
2067 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
2068 result by a chain of operations such that all but exactly one of their
2069 operands are constants. */
2072 chain_of_csts_start (struct loop
*loop
, tree x
)
2074 gimple stmt
= SSA_NAME_DEF_STMT (x
);
2076 basic_block bb
= gimple_bb (stmt
);
2077 enum tree_code code
;
2080 || !flow_bb_inside_loop_p (loop
, bb
))
2083 if (gimple_code (stmt
) == GIMPLE_PHI
)
2085 if (bb
== loop
->header
)
2091 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2094 code
= gimple_assign_rhs_code (stmt
);
2095 if (gimple_references_memory_p (stmt
)
2096 || TREE_CODE_CLASS (code
) == tcc_reference
2097 || (code
== ADDR_EXPR
2098 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
2101 use
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
2102 if (use
== NULL_TREE
)
2105 return chain_of_csts_start (loop
, use
);
2108 /* Determines whether the expression X is derived from a result of a phi node
2109 in header of LOOP such that
2111 * the derivation of X consists only from operations with constants
2112 * the initial value of the phi node is constant
2113 * the value of the phi node in the next iteration can be derived from the
2114 value in the current iteration by a chain of operations with constants.
2116 If such phi node exists, it is returned, otherwise NULL is returned. */
2119 get_base_for (struct loop
*loop
, tree x
)
2124 if (is_gimple_min_invariant (x
))
2127 phi
= chain_of_csts_start (loop
, x
);
2131 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2132 next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2134 if (TREE_CODE (next
) != SSA_NAME
)
2137 if (!is_gimple_min_invariant (init
))
2140 if (chain_of_csts_start (loop
, next
) != phi
)
2146 /* Given an expression X, then
2148 * if X is NULL_TREE, we return the constant BASE.
2149 * otherwise X is a SSA name, whose value in the considered loop is derived
2150 by a chain of operations with constant from a result of a phi node in
2151 the header of the loop. Then we return value of X when the value of the
2152 result of this phi node is given by the constant BASE. */
2155 get_val_for (tree x
, tree base
)
2159 gcc_assert (is_gimple_min_invariant (base
));
2164 stmt
= SSA_NAME_DEF_STMT (x
);
2165 if (gimple_code (stmt
) == GIMPLE_PHI
)
2168 gcc_assert (is_gimple_assign (stmt
));
2170 /* STMT must be either an assignment of a single SSA name or an
2171 expression involving an SSA name and a constant. Try to fold that
2172 expression using the value for the SSA name. */
2173 if (gimple_assign_ssa_name_copy_p (stmt
))
2174 return get_val_for (gimple_assign_rhs1 (stmt
), base
);
2175 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_UNARY_RHS
2176 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
2178 return fold_build1 (gimple_assign_rhs_code (stmt
),
2179 gimple_expr_type (stmt
),
2180 get_val_for (gimple_assign_rhs1 (stmt
), base
));
2182 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_BINARY_RHS
)
2184 tree rhs1
= gimple_assign_rhs1 (stmt
);
2185 tree rhs2
= gimple_assign_rhs2 (stmt
);
2186 if (TREE_CODE (rhs1
) == SSA_NAME
)
2187 rhs1
= get_val_for (rhs1
, base
);
2188 else if (TREE_CODE (rhs2
) == SSA_NAME
)
2189 rhs2
= get_val_for (rhs2
, base
);
2192 return fold_build2 (gimple_assign_rhs_code (stmt
),
2193 gimple_expr_type (stmt
), rhs1
, rhs2
);
2200 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2201 by brute force -- i.e. by determining the value of the operands of the
2202 condition at EXIT in first few iterations of the loop (assuming that
2203 these values are constant) and determining the first one in that the
2204 condition is not satisfied. Returns the constant giving the number
2205 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
2208 loop_niter_by_eval (struct loop
*loop
, edge exit
)
2211 tree op
[2], val
[2], next
[2], aval
[2];
2216 cond
= last_stmt (exit
->src
);
2217 if (!cond
|| gimple_code (cond
) != GIMPLE_COND
)
2218 return chrec_dont_know
;
2220 cmp
= gimple_cond_code (cond
);
2221 if (exit
->flags
& EDGE_TRUE_VALUE
)
2222 cmp
= invert_tree_comparison (cmp
, false);
2232 op
[0] = gimple_cond_lhs (cond
);
2233 op
[1] = gimple_cond_rhs (cond
);
2237 return chrec_dont_know
;
2240 for (j
= 0; j
< 2; j
++)
2242 if (is_gimple_min_invariant (op
[j
]))
2245 next
[j
] = NULL_TREE
;
2250 phi
= get_base_for (loop
, op
[j
]);
2252 return chrec_dont_know
;
2253 val
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2254 next
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2258 /* Don't issue signed overflow warnings. */
2259 fold_defer_overflow_warnings ();
2261 for (i
= 0; i
< MAX_ITERATIONS_TO_TRACK
; i
++)
2263 for (j
= 0; j
< 2; j
++)
2264 aval
[j
] = get_val_for (op
[j
], val
[j
]);
2266 acnd
= fold_binary (cmp
, boolean_type_node
, aval
[0], aval
[1]);
2267 if (acnd
&& integer_zerop (acnd
))
2269 fold_undefer_and_ignore_overflow_warnings ();
2270 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2272 "Proved that loop %d iterates %d times using brute force.\n",
2274 return build_int_cst (unsigned_type_node
, i
);
2277 for (j
= 0; j
< 2; j
++)
2279 val
[j
] = get_val_for (next
[j
], val
[j
]);
2280 if (!is_gimple_min_invariant (val
[j
]))
2282 fold_undefer_and_ignore_overflow_warnings ();
2283 return chrec_dont_know
;
2288 fold_undefer_and_ignore_overflow_warnings ();
2290 return chrec_dont_know
;
2293 /* Finds the exit of the LOOP by that the loop exits after a constant
2294 number of iterations and stores the exit edge to *EXIT. The constant
2295 giving the number of iterations of LOOP is returned. The number of
2296 iterations is determined using loop_niter_by_eval (i.e. by brute force
2297 evaluation). If we are unable to find the exit for that loop_niter_by_eval
2298 determines the number of iterations, chrec_dont_know is returned. */
2301 find_loop_niter_by_eval (struct loop
*loop
, edge
*exit
)
2304 vec
<edge
> exits
= get_loop_exit_edges (loop
);
2306 tree niter
= NULL_TREE
, aniter
;
2310 /* Loops with multiple exits are expensive to handle and less important. */
2311 if (!flag_expensive_optimizations
2312 && exits
.length () > 1)
2315 return chrec_dont_know
;
2318 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2320 if (!just_once_each_iteration_p (loop
, ex
->src
))
2323 aniter
= loop_niter_by_eval (loop
, ex
);
2324 if (chrec_contains_undetermined (aniter
))
2328 && !tree_int_cst_lt (aniter
, niter
))
2336 return niter
? niter
: chrec_dont_know
;
2341 Analysis of upper bounds on number of iterations of a loop.
2345 static double_int
derive_constant_upper_bound_ops (tree
, tree
,
2346 enum tree_code
, tree
);
2348 /* Returns a constant upper bound on the value of the right-hand side of
2349 an assignment statement STMT. */
2352 derive_constant_upper_bound_assign (gimple stmt
)
2354 enum tree_code code
= gimple_assign_rhs_code (stmt
);
2355 tree op0
= gimple_assign_rhs1 (stmt
);
2356 tree op1
= gimple_assign_rhs2 (stmt
);
2358 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt
)),
2362 /* Returns a constant upper bound on the value of expression VAL. VAL
2363 is considered to be unsigned. If its type is signed, its value must
2367 derive_constant_upper_bound (tree val
)
2369 enum tree_code code
;
2372 extract_ops_from_tree (val
, &code
, &op0
, &op1
);
2373 return derive_constant_upper_bound_ops (TREE_TYPE (val
), op0
, code
, op1
);
2376 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
2377 whose type is TYPE. The expression is considered to be unsigned. If
2378 its type is signed, its value must be nonnegative. */
2381 derive_constant_upper_bound_ops (tree type
, tree op0
,
2382 enum tree_code code
, tree op1
)
2385 double_int bnd
, max
, mmax
, cst
;
2388 if (INTEGRAL_TYPE_P (type
))
2389 maxt
= TYPE_MAX_VALUE (type
);
2391 maxt
= upper_bound_in_type (type
, type
);
2393 max
= tree_to_double_int (maxt
);
2398 return tree_to_double_int (op0
);
2401 subtype
= TREE_TYPE (op0
);
2402 if (!TYPE_UNSIGNED (subtype
)
2403 /* If TYPE is also signed, the fact that VAL is nonnegative implies
2404 that OP0 is nonnegative. */
2405 && TYPE_UNSIGNED (type
)
2406 && !tree_expr_nonnegative_p (op0
))
2408 /* If we cannot prove that the casted expression is nonnegative,
2409 we cannot establish more useful upper bound than the precision
2410 of the type gives us. */
2414 /* We now know that op0 is an nonnegative value. Try deriving an upper
2416 bnd
= derive_constant_upper_bound (op0
);
2418 /* If the bound does not fit in TYPE, max. value of TYPE could be
2426 case POINTER_PLUS_EXPR
:
2428 if (TREE_CODE (op1
) != INTEGER_CST
2429 || !tree_expr_nonnegative_p (op0
))
2432 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
2433 choose the most logical way how to treat this constant regardless
2434 of the signedness of the type. */
2435 cst
= tree_to_double_int (op1
);
2436 cst
= cst
.sext (TYPE_PRECISION (type
));
2437 if (code
!= MINUS_EXPR
)
2440 bnd
= derive_constant_upper_bound (op0
);
2442 if (cst
.is_negative ())
2445 /* Avoid CST == 0x80000... */
2446 if (cst
.is_negative ())
2449 /* OP0 + CST. We need to check that
2450 BND <= MAX (type) - CST. */
2460 /* OP0 - CST, where CST >= 0.
2462 If TYPE is signed, we have already verified that OP0 >= 0, and we
2463 know that the result is nonnegative. This implies that
2466 If TYPE is unsigned, we must additionally know that OP0 >= CST,
2467 otherwise the operation underflows.
2470 /* This should only happen if the type is unsigned; however, for
2471 buggy programs that use overflowing signed arithmetics even with
2472 -fno-wrapv, this condition may also be true for signed values. */
2476 if (TYPE_UNSIGNED (type
))
2478 tree tem
= fold_binary (GE_EXPR
, boolean_type_node
, op0
,
2479 double_int_to_tree (type
, cst
));
2480 if (!tem
|| integer_nonzerop (tem
))
2489 case FLOOR_DIV_EXPR
:
2490 case EXACT_DIV_EXPR
:
2491 if (TREE_CODE (op1
) != INTEGER_CST
2492 || tree_int_cst_sign_bit (op1
))
2495 bnd
= derive_constant_upper_bound (op0
);
2496 return bnd
.udiv (tree_to_double_int (op1
), FLOOR_DIV_EXPR
);
2499 if (TREE_CODE (op1
) != INTEGER_CST
2500 || tree_int_cst_sign_bit (op1
))
2502 return tree_to_double_int (op1
);
2505 stmt
= SSA_NAME_DEF_STMT (op0
);
2506 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2507 || gimple_assign_lhs (stmt
) != op0
)
2509 return derive_constant_upper_bound_assign (stmt
);
2516 /* Emit a -Waggressive-loop-optimizations warning if needed. */
2519 do_warn_aggressive_loop_optimizations (struct loop
*loop
,
2520 double_int i_bound
, gimple stmt
)
2522 /* Don't warn if the loop doesn't have known constant bound. */
2523 if (!loop
->nb_iterations
2524 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
2525 || !warn_aggressive_loop_optimizations
2526 /* To avoid warning multiple times for the same loop,
2527 only start warning when we preserve loops. */
2528 || (cfun
->curr_properties
& PROP_loops
) == 0
2529 /* Only warn once per loop. */
2530 || loop
->warned_aggressive_loop_optimizations
2531 /* Only warn if undefined behavior gives us lower estimate than the
2532 known constant bound. */
2533 || i_bound
.ucmp (tree_to_double_int (loop
->nb_iterations
)) >= 0
2534 /* And undefined behavior happens unconditionally. */
2535 || !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (stmt
)))
2538 edge e
= single_exit (loop
);
2542 gimple estmt
= last_stmt (e
->src
);
2543 if (warning_at (gimple_location (stmt
), OPT_Waggressive_loop_optimizations
,
2544 "iteration %E invokes undefined behavior",
2545 double_int_to_tree (TREE_TYPE (loop
->nb_iterations
),
2547 inform (gimple_location (estmt
), "containing loop");
2548 loop
->warned_aggressive_loop_optimizations
= true;
2551 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
2552 is true if the loop is exited immediately after STMT, and this exit
2553 is taken at last when the STMT is executed BOUND + 1 times.
2554 REALISTIC is true if BOUND is expected to be close to the real number
2555 of iterations. UPPER is true if we are sure the loop iterates at most
2556 BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */
2559 record_estimate (struct loop
*loop
, tree bound
, double_int i_bound
,
2560 gimple at_stmt
, bool is_exit
, bool realistic
, bool upper
)
2564 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2566 fprintf (dump_file
, "Statement %s", is_exit
? "(exit)" : "");
2567 print_gimple_stmt (dump_file
, at_stmt
, 0, TDF_SLIM
);
2568 fprintf (dump_file
, " is %sexecuted at most ",
2569 upper
? "" : "probably ");
2570 print_generic_expr (dump_file
, bound
, TDF_SLIM
);
2571 fprintf (dump_file
, " (bounded by ");
2572 dump_double_int (dump_file
, i_bound
, true);
2573 fprintf (dump_file
, ") + 1 times in loop %d.\n", loop
->num
);
2576 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
2577 real number of iterations. */
2578 if (TREE_CODE (bound
) != INTEGER_CST
)
2581 gcc_checking_assert (i_bound
== tree_to_double_int (bound
));
2582 if (!upper
&& !realistic
)
2585 /* If we have a guaranteed upper bound, record it in the appropriate
2586 list, unless this is an !is_exit bound (i.e. undefined behavior in
2587 at_stmt) in a loop with known constant number of iterations. */
2590 || loop
->nb_iterations
== NULL_TREE
2591 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
))
2593 struct nb_iter_bound
*elt
= ggc_alloc_nb_iter_bound ();
2595 elt
->bound
= i_bound
;
2596 elt
->stmt
= at_stmt
;
2597 elt
->is_exit
= is_exit
;
2598 elt
->next
= loop
->bounds
;
2602 /* If statement is executed on every path to the loop latch, we can directly
2603 infer the upper bound on the # of iterations of the loop. */
2604 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (at_stmt
)))
2607 /* Update the number of iteration estimates according to the bound.
2608 If at_stmt is an exit then the loop latch is executed at most BOUND times,
2609 otherwise it can be executed BOUND + 1 times. We will lower the estimate
2610 later if such statement must be executed on last iteration */
2612 delta
= double_int_zero
;
2614 delta
= double_int_one
;
2617 /* If an overflow occurred, ignore the result. */
2618 if (i_bound
.ult (delta
))
2621 if (upper
&& !is_exit
)
2622 do_warn_aggressive_loop_optimizations (loop
, i_bound
, at_stmt
);
2623 record_niter_bound (loop
, i_bound
, realistic
, upper
);
2626 /* Record the estimate on number of iterations of LOOP based on the fact that
2627 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
2628 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
2629 estimated number of iterations is expected to be close to the real one.
2630 UPPER is true if we are sure the induction variable does not wrap. */
2633 record_nonwrapping_iv (struct loop
*loop
, tree base
, tree step
, gimple stmt
,
2634 tree low
, tree high
, bool realistic
, bool upper
)
2636 tree niter_bound
, extreme
, delta
;
2637 tree type
= TREE_TYPE (base
), unsigned_type
;
2640 if (TREE_CODE (step
) != INTEGER_CST
|| integer_zerop (step
))
2643 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2645 fprintf (dump_file
, "Induction variable (");
2646 print_generic_expr (dump_file
, TREE_TYPE (base
), TDF_SLIM
);
2647 fprintf (dump_file
, ") ");
2648 print_generic_expr (dump_file
, base
, TDF_SLIM
);
2649 fprintf (dump_file
, " + ");
2650 print_generic_expr (dump_file
, step
, TDF_SLIM
);
2651 fprintf (dump_file
, " * iteration does not wrap in statement ");
2652 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2653 fprintf (dump_file
, " in loop %d.\n", loop
->num
);
2656 unsigned_type
= unsigned_type_for (type
);
2657 base
= fold_convert (unsigned_type
, base
);
2658 step
= fold_convert (unsigned_type
, step
);
2660 if (tree_int_cst_sign_bit (step
))
2662 extreme
= fold_convert (unsigned_type
, low
);
2663 if (TREE_CODE (base
) != INTEGER_CST
)
2664 base
= fold_convert (unsigned_type
, high
);
2665 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
2666 step
= fold_build1 (NEGATE_EXPR
, unsigned_type
, step
);
2670 extreme
= fold_convert (unsigned_type
, high
);
2671 if (TREE_CODE (base
) != INTEGER_CST
)
2672 base
= fold_convert (unsigned_type
, low
);
2673 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
2676 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
2677 would get out of the range. */
2678 niter_bound
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step
);
2679 max
= derive_constant_upper_bound (niter_bound
);
2680 record_estimate (loop
, niter_bound
, max
, stmt
, false, realistic
, upper
);
2683 /* Determine information about number of iterations a LOOP from the index
2684 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
2685 guaranteed to be executed in every iteration of LOOP. Callback for
2695 idx_infer_loop_bounds (tree base
, tree
*idx
, void *dta
)
2697 struct ilb_data
*data
= (struct ilb_data
*) dta
;
2698 tree ev
, init
, step
;
2699 tree low
, high
, type
, next
;
2700 bool sign
, upper
= true, at_end
= false;
2701 struct loop
*loop
= data
->loop
;
2702 bool reliable
= true;
2704 if (TREE_CODE (base
) != ARRAY_REF
)
2707 /* For arrays at the end of the structure, we are not guaranteed that they
2708 do not really extend over their declared size. However, for arrays of
2709 size greater than one, this is unlikely to be intended. */
2710 if (array_at_struct_end_p (base
))
2716 struct loop
*dloop
= loop_containing_stmt (data
->stmt
);
2720 ev
= analyze_scalar_evolution (dloop
, *idx
);
2721 ev
= instantiate_parameters (loop
, ev
);
2722 init
= initial_condition (ev
);
2723 step
= evolution_part_in_loop_num (ev
, loop
->num
);
2727 || TREE_CODE (step
) != INTEGER_CST
2728 || integer_zerop (step
)
2729 || tree_contains_chrecs (init
, NULL
)
2730 || chrec_contains_symbols_defined_in_loop (init
, loop
->num
))
2733 low
= array_ref_low_bound (base
);
2734 high
= array_ref_up_bound (base
);
2736 /* The case of nonconstant bounds could be handled, but it would be
2738 if (TREE_CODE (low
) != INTEGER_CST
2740 || TREE_CODE (high
) != INTEGER_CST
)
2742 sign
= tree_int_cst_sign_bit (step
);
2743 type
= TREE_TYPE (step
);
2745 /* The array of length 1 at the end of a structure most likely extends
2746 beyond its bounds. */
2748 && operand_equal_p (low
, high
, 0))
2751 /* In case the relevant bound of the array does not fit in type, or
2752 it does, but bound + step (in type) still belongs into the range of the
2753 array, the index may wrap and still stay within the range of the array
2754 (consider e.g. if the array is indexed by the full range of
2757 To make things simpler, we require both bounds to fit into type, although
2758 there are cases where this would not be strictly necessary. */
2759 if (!int_fits_type_p (high
, type
)
2760 || !int_fits_type_p (low
, type
))
2762 low
= fold_convert (type
, low
);
2763 high
= fold_convert (type
, high
);
2766 next
= fold_binary (PLUS_EXPR
, type
, low
, step
);
2768 next
= fold_binary (PLUS_EXPR
, type
, high
, step
);
2770 if (tree_int_cst_compare (low
, next
) <= 0
2771 && tree_int_cst_compare (next
, high
) <= 0)
2774 /* If access is not executed on every iteration, we must ensure that overlow may
2775 not make the access valid later. */
2776 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (data
->stmt
))
2777 && scev_probably_wraps_p (initial_condition_in_loop_num (ev
, loop
->num
),
2778 step
, data
->stmt
, loop
, true))
2781 record_nonwrapping_iv (loop
, init
, step
, data
->stmt
, low
, high
, reliable
, upper
);
2785 /* Determine information about number of iterations a LOOP from the bounds
2786 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
2787 STMT is guaranteed to be executed in every iteration of LOOP.*/
2790 infer_loop_bounds_from_ref (struct loop
*loop
, gimple stmt
, tree ref
)
2792 struct ilb_data data
;
2796 for_each_index (&ref
, idx_infer_loop_bounds
, &data
);
2799 /* Determine information about number of iterations of a LOOP from the way
2800 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
2801 executed in every iteration of LOOP. */
2804 infer_loop_bounds_from_array (struct loop
*loop
, gimple stmt
)
2806 if (is_gimple_assign (stmt
))
2808 tree op0
= gimple_assign_lhs (stmt
);
2809 tree op1
= gimple_assign_rhs1 (stmt
);
2811 /* For each memory access, analyze its access function
2812 and record a bound on the loop iteration domain. */
2813 if (REFERENCE_CLASS_P (op0
))
2814 infer_loop_bounds_from_ref (loop
, stmt
, op0
);
2816 if (REFERENCE_CLASS_P (op1
))
2817 infer_loop_bounds_from_ref (loop
, stmt
, op1
);
2819 else if (is_gimple_call (stmt
))
2822 unsigned i
, n
= gimple_call_num_args (stmt
);
2824 lhs
= gimple_call_lhs (stmt
);
2825 if (lhs
&& REFERENCE_CLASS_P (lhs
))
2826 infer_loop_bounds_from_ref (loop
, stmt
, lhs
);
2828 for (i
= 0; i
< n
; i
++)
2830 arg
= gimple_call_arg (stmt
, i
);
2831 if (REFERENCE_CLASS_P (arg
))
2832 infer_loop_bounds_from_ref (loop
, stmt
, arg
);
2837 /* Determine information about number of iterations of a LOOP from the fact
2838 that pointer arithmetics in STMT does not overflow. */
2841 infer_loop_bounds_from_pointer_arith (struct loop
*loop
, gimple stmt
)
2843 tree def
, base
, step
, scev
, type
, low
, high
;
2846 if (!is_gimple_assign (stmt
)
2847 || gimple_assign_rhs_code (stmt
) != POINTER_PLUS_EXPR
)
2850 def
= gimple_assign_lhs (stmt
);
2851 if (TREE_CODE (def
) != SSA_NAME
)
2854 type
= TREE_TYPE (def
);
2855 if (!nowrap_type_p (type
))
2858 ptr
= gimple_assign_rhs1 (stmt
);
2859 if (!expr_invariant_in_loop_p (loop
, ptr
))
2862 var
= gimple_assign_rhs2 (stmt
);
2863 if (TYPE_PRECISION (type
) != TYPE_PRECISION (TREE_TYPE (var
)))
2866 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
2867 if (chrec_contains_undetermined (scev
))
2870 base
= initial_condition_in_loop_num (scev
, loop
->num
);
2871 step
= evolution_part_in_loop_num (scev
, loop
->num
);
2874 || TREE_CODE (step
) != INTEGER_CST
2875 || tree_contains_chrecs (base
, NULL
)
2876 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
2879 low
= lower_bound_in_type (type
, type
);
2880 high
= upper_bound_in_type (type
, type
);
2882 /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
2883 produce a NULL pointer. The contrary would mean NULL points to an object,
2884 while NULL is supposed to compare unequal with the address of all objects.
2885 Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
2886 NULL pointer since that would mean wrapping, which we assume here not to
2887 happen. So, we can exclude NULL from the valid range of pointer
2889 if (flag_delete_null_pointer_checks
&& int_cst_value (low
) == 0)
2890 low
= build_int_cstu (TREE_TYPE (low
), TYPE_ALIGN_UNIT (TREE_TYPE (type
)));
2892 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
2895 /* Determine information about number of iterations of a LOOP from the fact
2896 that signed arithmetics in STMT does not overflow. */
2899 infer_loop_bounds_from_signedness (struct loop
*loop
, gimple stmt
)
2901 tree def
, base
, step
, scev
, type
, low
, high
;
2903 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2906 def
= gimple_assign_lhs (stmt
);
2908 if (TREE_CODE (def
) != SSA_NAME
)
2911 type
= TREE_TYPE (def
);
2912 if (!INTEGRAL_TYPE_P (type
)
2913 || !TYPE_OVERFLOW_UNDEFINED (type
))
2916 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
2917 if (chrec_contains_undetermined (scev
))
2920 base
= initial_condition_in_loop_num (scev
, loop
->num
);
2921 step
= evolution_part_in_loop_num (scev
, loop
->num
);
2924 || TREE_CODE (step
) != INTEGER_CST
2925 || tree_contains_chrecs (base
, NULL
)
2926 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
2929 low
= lower_bound_in_type (type
, type
);
2930 high
= upper_bound_in_type (type
, type
);
2932 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
2935 /* The following analyzers are extracting informations on the bounds
2936 of LOOP from the following undefined behaviors:
2938 - data references should not access elements over the statically
2941 - signed variables should not overflow when flag_wrapv is not set.
2945 infer_loop_bounds_from_undefined (struct loop
*loop
)
2949 gimple_stmt_iterator bsi
;
2953 bbs
= get_loop_body (loop
);
2955 for (i
= 0; i
< loop
->num_nodes
; i
++)
2959 /* If BB is not executed in each iteration of the loop, we cannot
2960 use the operations in it to infer reliable upper bound on the
2961 # of iterations of the loop. However, we can use it as a guess.
2962 Reliable guesses come only from array bounds. */
2963 reliable
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
);
2965 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
2967 gimple stmt
= gsi_stmt (bsi
);
2969 infer_loop_bounds_from_array (loop
, stmt
);
2973 infer_loop_bounds_from_signedness (loop
, stmt
);
2974 infer_loop_bounds_from_pointer_arith (loop
, stmt
);
2985 /* Compare double ints, callback for qsort. */
2988 double_int_cmp (const void *p1
, const void *p2
)
2990 const double_int
*d1
= (const double_int
*)p1
;
2991 const double_int
*d2
= (const double_int
*)p2
;
2999 /* Return index of BOUND in BOUNDS array sorted in increasing order.
3000 Lookup by binary search. */
3003 bound_index (vec
<double_int
> bounds
, double_int bound
)
3005 unsigned int end
= bounds
.length ();
3006 unsigned int begin
= 0;
3008 /* Find a matching index by means of a binary search. */
3009 while (begin
!= end
)
3011 unsigned int middle
= (begin
+ end
) / 2;
3012 double_int index
= bounds
[middle
];
3016 else if (index
.ult (bound
))
3024 /* We recorded loop bounds only for statements dominating loop latch (and thus
3025 executed each loop iteration). If there are any bounds on statements not
3026 dominating the loop latch we can improve the estimate by walking the loop
3027 body and seeing if every path from loop header to loop latch contains
3028 some bounded statement. */
3031 discover_iteration_bound_by_body_walk (struct loop
*loop
)
3033 pointer_map_t
*bb_bounds
;
3034 struct nb_iter_bound
*elt
;
3035 vec
<double_int
> bounds
= vNULL
;
3036 vec
<vec
<basic_block
> > queues
= vNULL
;
3037 vec
<basic_block
> queue
= vNULL
;
3038 ptrdiff_t queue_index
;
3039 ptrdiff_t latch_index
= 0;
3040 pointer_map_t
*block_priority
;
3042 /* Discover what bounds may interest us. */
3043 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3045 double_int bound
= elt
->bound
;
3047 /* Exit terminates loop at given iteration, while non-exits produce undefined
3048 effect on the next iteration. */
3051 bound
+= double_int_one
;
3052 /* If an overflow occurred, ignore the result. */
3053 if (bound
.is_zero ())
3057 if (!loop
->any_upper_bound
3058 || bound
.ult (loop
->nb_iterations_upper_bound
))
3059 bounds
.safe_push (bound
);
3062 /* Exit early if there is nothing to do. */
3063 if (!bounds
.exists ())
3066 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3067 fprintf (dump_file
, " Trying to walk loop body to reduce the bound.\n");
3069 /* Sort the bounds in decreasing order. */
3070 qsort (bounds
.address (), bounds
.length (),
3071 sizeof (double_int
), double_int_cmp
);
3073 /* For every basic block record the lowest bound that is guaranteed to
3074 terminate the loop. */
3076 bb_bounds
= pointer_map_create ();
3077 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3079 double_int bound
= elt
->bound
;
3082 bound
+= double_int_one
;
3083 /* If an overflow occurred, ignore the result. */
3084 if (bound
.is_zero ())
3088 if (!loop
->any_upper_bound
3089 || bound
.ult (loop
->nb_iterations_upper_bound
))
3091 ptrdiff_t index
= bound_index (bounds
, bound
);
3092 void **entry
= pointer_map_contains (bb_bounds
,
3093 gimple_bb (elt
->stmt
));
3095 *pointer_map_insert (bb_bounds
,
3096 gimple_bb (elt
->stmt
)) = (void *)index
;
3097 else if ((ptrdiff_t)*entry
> index
)
3098 *entry
= (void *)index
;
3102 block_priority
= pointer_map_create ();
3104 /* Perform shortest path discovery loop->header ... loop->latch.
3106 The "distance" is given by the smallest loop bound of basic block
3107 present in the path and we look for path with largest smallest bound
3110 To avoid the need for fibonacci heap on double ints we simply compress
3111 double ints into indexes to BOUNDS array and then represent the queue
3112 as arrays of queues for every index.
3113 Index of BOUNDS.length() means that the execution of given BB has
3114 no bounds determined.
3116 VISITED is a pointer map translating basic block into smallest index
3117 it was inserted into the priority queue with. */
3120 /* Start walk in loop header with index set to infinite bound. */
3121 queue_index
= bounds
.length ();
3122 queues
.safe_grow_cleared (queue_index
+ 1);
3123 queue
.safe_push (loop
->header
);
3124 queues
[queue_index
] = queue
;
3125 *pointer_map_insert (block_priority
, loop
->header
) = (void *)queue_index
;
3127 for (; queue_index
>= 0; queue_index
--)
3129 if (latch_index
< queue_index
)
3131 while (queues
[queue_index
].length ())
3134 ptrdiff_t bound_index
= queue_index
;
3139 queue
= queues
[queue_index
];
3142 /* OK, we later inserted the BB with lower priority, skip it. */
3143 if ((ptrdiff_t)*pointer_map_contains (block_priority
, bb
) > queue_index
)
3146 /* See if we can improve the bound. */
3147 entry
= pointer_map_contains (bb_bounds
, bb
);
3148 if (entry
&& (ptrdiff_t)*entry
< bound_index
)
3149 bound_index
= (ptrdiff_t)*entry
;
3151 /* Insert succesors into the queue, watch for latch edge
3152 and record greatest index we saw. */
3153 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3155 bool insert
= false;
3158 if (loop_exit_edge_p (loop
, e
))
3161 if (e
== loop_latch_edge (loop
)
3162 && latch_index
< bound_index
)
3163 latch_index
= bound_index
;
3164 else if (!(entry
= pointer_map_contains (block_priority
, e
->dest
)))
3167 *pointer_map_insert (block_priority
, e
->dest
) = (void *)bound_index
;
3169 else if ((ptrdiff_t)*entry
< bound_index
)
3172 *entry
= (void *)bound_index
;
3176 queues
[bound_index
].safe_push (e
->dest
);
3180 queues
[queue_index
].release ();
3183 gcc_assert (latch_index
>= 0);
3184 if ((unsigned)latch_index
< bounds
.length ())
3186 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3188 fprintf (dump_file
, "Found better loop bound ");
3189 dump_double_int (dump_file
, bounds
[latch_index
], true);
3190 fprintf (dump_file
, "\n");
3192 record_niter_bound (loop
, bounds
[latch_index
], false, true);
3197 pointer_map_destroy (bb_bounds
);
3198 pointer_map_destroy (block_priority
);
3201 /* See if every path cross the loop goes through a statement that is known
3202 to not execute at the last iteration. In that case we can decrese iteration
3206 maybe_lower_iteration_bound (struct loop
*loop
)
3208 pointer_set_t
*not_executed_last_iteration
= NULL
;
3209 struct nb_iter_bound
*elt
;
3210 bool found_exit
= false;
3211 vec
<basic_block
> queue
= vNULL
;
3214 /* Collect all statements with interesting (i.e. lower than
3215 nb_iterations_upper_bound) bound on them.
3217 TODO: Due to the way record_estimate choose estimates to store, the bounds
3218 will be always nb_iterations_upper_bound-1. We can change this to record
3219 also statements not dominating the loop latch and update the walk bellow
3220 to the shortest path algorthm. */
3221 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3224 && elt
->bound
.ult (loop
->nb_iterations_upper_bound
))
3226 if (!not_executed_last_iteration
)
3227 not_executed_last_iteration
= pointer_set_create ();
3228 pointer_set_insert (not_executed_last_iteration
, elt
->stmt
);
3231 if (!not_executed_last_iteration
)
3234 /* Start DFS walk in the loop header and see if we can reach the
3235 loop latch or any of the exits (including statements with side
3236 effects that may terminate the loop otherwise) without visiting
3237 any of the statements known to have undefined effect on the last
3239 queue
.safe_push (loop
->header
);
3240 visited
= BITMAP_ALLOC (NULL
);
3241 bitmap_set_bit (visited
, loop
->header
->index
);
3246 basic_block bb
= queue
.pop ();
3247 gimple_stmt_iterator gsi
;
3248 bool stmt_found
= false;
3250 /* Loop for possible exits and statements bounding the execution. */
3251 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3253 gimple stmt
= gsi_stmt (gsi
);
3254 if (pointer_set_contains (not_executed_last_iteration
, stmt
))
3259 if (gimple_has_side_effects (stmt
))
3268 /* If no bounding statement is found, continue the walk. */
3274 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3276 if (loop_exit_edge_p (loop
, e
)
3277 || e
== loop_latch_edge (loop
))
3282 if (bitmap_set_bit (visited
, e
->dest
->index
))
3283 queue
.safe_push (e
->dest
);
3287 while (queue
.length () && !found_exit
);
3289 /* If every path through the loop reach bounding statement before exit,
3290 then we know the last iteration of the loop will have undefined effect
3291 and we can decrease number of iterations. */
3295 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3296 fprintf (dump_file
, "Reducing loop iteration estimate by 1; "
3297 "undefined statement must be executed at the last iteration.\n");
3298 record_niter_bound (loop
, loop
->nb_iterations_upper_bound
- double_int_one
,
3301 BITMAP_FREE (visited
);
3303 pointer_set_destroy (not_executed_last_iteration
);
3306 /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
3307 is true also use estimates derived from undefined behavior. */
3310 estimate_numbers_of_iterations_loop (struct loop
*loop
)
3315 struct tree_niter_desc niter_desc
;
3320 /* Give up if we already have tried to compute an estimation. */
3321 if (loop
->estimate_state
!= EST_NOT_COMPUTED
)
3324 loop
->estimate_state
= EST_AVAILABLE
;
3325 /* Force estimate compuation but leave any existing upper bound in place. */
3326 loop
->any_estimate
= false;
3328 /* Ensure that loop->nb_iterations is computed if possible. If it turns out
3329 to be constant, we avoid undefined behavior implied bounds and instead
3330 diagnose those loops with -Waggressive-loop-optimizations. */
3331 number_of_latch_executions (loop
);
3333 exits
= get_loop_exit_edges (loop
);
3334 likely_exit
= single_likely_exit (loop
);
3335 FOR_EACH_VEC_ELT (exits
, i
, ex
)
3337 if (!number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
3340 niter
= niter_desc
.niter
;
3341 type
= TREE_TYPE (niter
);
3342 if (TREE_CODE (niter_desc
.may_be_zero
) != INTEGER_CST
)
3343 niter
= build3 (COND_EXPR
, type
, niter_desc
.may_be_zero
,
3344 build_int_cst (type
, 0),
3346 record_estimate (loop
, niter
, niter_desc
.max
,
3347 last_stmt (ex
->src
),
3348 true, ex
== likely_exit
, true);
3352 if (flag_aggressive_loop_optimizations
)
3353 infer_loop_bounds_from_undefined (loop
);
3355 discover_iteration_bound_by_body_walk (loop
);
3357 maybe_lower_iteration_bound (loop
);
3359 /* If we have a measured profile, use it to estimate the number of
3361 if (loop
->header
->count
!= 0)
3363 gcov_type nit
= expected_loop_iterations_unbounded (loop
) + 1;
3364 bound
= gcov_type_to_double_int (nit
);
3365 record_niter_bound (loop
, bound
, true, false);
3368 /* If we know the exact number of iterations of this loop, try to
3369 not break code with undefined behavior by not recording smaller
3370 maximum number of iterations. */
3371 if (loop
->nb_iterations
3372 && TREE_CODE (loop
->nb_iterations
) == INTEGER_CST
)
3374 loop
->any_upper_bound
= true;
3375 loop
->nb_iterations_upper_bound
3376 = tree_to_double_int (loop
->nb_iterations
);
3380 /* Sets NIT to the estimated number of executions of the latch of the
3381 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
3382 large as the number of iterations. If we have no reliable estimate,
3383 the function returns false, otherwise returns true. */
3386 estimated_loop_iterations (struct loop
*loop
, double_int
*nit
)
3388 /* When SCEV information is available, try to update loop iterations
3389 estimate. Otherwise just return whatever we recorded earlier. */
3390 if (scev_initialized_p ())
3391 estimate_numbers_of_iterations_loop (loop
);
3393 return (get_estimated_loop_iterations (loop
, nit
));
3396 /* Similar to estimated_loop_iterations, but returns the estimate only
3397 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3398 on the number of iterations of LOOP could not be derived, returns -1. */
3401 estimated_loop_iterations_int (struct loop
*loop
)
3404 HOST_WIDE_INT hwi_nit
;
3406 if (!estimated_loop_iterations (loop
, &nit
))
3409 if (!nit
.fits_shwi ())
3411 hwi_nit
= nit
.to_shwi ();
3413 return hwi_nit
< 0 ? -1 : hwi_nit
;
3417 /* Sets NIT to an upper bound for the maximum number of executions of the
3418 latch of the LOOP. If we have no reliable estimate, the function returns
3419 false, otherwise returns true. */
3422 max_loop_iterations (struct loop
*loop
, double_int
*nit
)
3424 /* When SCEV information is available, try to update loop iterations
3425 estimate. Otherwise just return whatever we recorded earlier. */
3426 if (scev_initialized_p ())
3427 estimate_numbers_of_iterations_loop (loop
);
3429 return get_max_loop_iterations (loop
, nit
);
3432 /* Similar to max_loop_iterations, but returns the estimate only
3433 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3434 on the number of iterations of LOOP could not be derived, returns -1. */
3437 max_loop_iterations_int (struct loop
*loop
)
3440 HOST_WIDE_INT hwi_nit
;
3442 if (!max_loop_iterations (loop
, &nit
))
3445 if (!nit
.fits_shwi ())
3447 hwi_nit
= nit
.to_shwi ();
3449 return hwi_nit
< 0 ? -1 : hwi_nit
;
3452 /* Returns an estimate for the number of executions of statements
3453 in the LOOP. For statements before the loop exit, this exceeds
3454 the number of execution of the latch by one. */
3457 estimated_stmt_executions_int (struct loop
*loop
)
3459 HOST_WIDE_INT nit
= estimated_loop_iterations_int (loop
);
3465 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
3467 /* If the computation overflows, return -1. */
3468 return snit
< 0 ? -1 : snit
;
3471 /* Sets NIT to the estimated maximum number of executions of the latch of the
3472 LOOP, plus one. If we have no reliable estimate, the function returns
3473 false, otherwise returns true. */
3476 max_stmt_executions (struct loop
*loop
, double_int
*nit
)
3478 double_int nit_minus_one
;
3480 if (!max_loop_iterations (loop
, nit
))
3483 nit_minus_one
= *nit
;
3485 *nit
+= double_int_one
;
3487 return (*nit
).ugt (nit_minus_one
);
3490 /* Sets NIT to the estimated number of executions of the latch of the
3491 LOOP, plus one. If we have no reliable estimate, the function returns
3492 false, otherwise returns true. */
3495 estimated_stmt_executions (struct loop
*loop
, double_int
*nit
)
3497 double_int nit_minus_one
;
3499 if (!estimated_loop_iterations (loop
, nit
))
3502 nit_minus_one
= *nit
;
3504 *nit
+= double_int_one
;
3506 return (*nit
).ugt (nit_minus_one
);
3509 /* Records estimates on numbers of iterations of loops. */
3512 estimate_numbers_of_iterations (void)
3517 /* We don't want to issue signed overflow warnings while getting
3518 loop iteration estimates. */
3519 fold_defer_overflow_warnings ();
3521 FOR_EACH_LOOP (li
, loop
, 0)
3523 estimate_numbers_of_iterations_loop (loop
);
3526 fold_undefer_and_ignore_overflow_warnings ();
3529 /* Returns true if statement S1 dominates statement S2. */
3532 stmt_dominates_stmt_p (gimple s1
, gimple s2
)
3534 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
3542 gimple_stmt_iterator bsi
;
3544 if (gimple_code (s2
) == GIMPLE_PHI
)
3547 if (gimple_code (s1
) == GIMPLE_PHI
)
3550 for (bsi
= gsi_start_bb (bb1
); gsi_stmt (bsi
) != s2
; gsi_next (&bsi
))
3551 if (gsi_stmt (bsi
) == s1
)
3557 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
3560 /* Returns true when we can prove that the number of executions of
3561 STMT in the loop is at most NITER, according to the bound on
3562 the number of executions of the statement NITER_BOUND->stmt recorded in
3563 NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT.
3565 ??? This code can become quite a CPU hog - we can have many bounds,
3566 and large basic block forcing stmt_dominates_stmt_p to be queried
3567 many times on a large basic blocks, so the whole thing is O(n^2)
3568 for scev_probably_wraps_p invocation (that can be done n times).
3570 It would make more sense (and give better answers) to remember BB
3571 bounds computed by discover_iteration_bound_by_body_walk. */
3574 n_of_executions_at_most (gimple stmt
,
3575 struct nb_iter_bound
*niter_bound
,
3578 double_int bound
= niter_bound
->bound
;
3579 tree nit_type
= TREE_TYPE (niter
), e
;
3582 gcc_assert (TYPE_UNSIGNED (nit_type
));
3584 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
3585 the number of iterations is small. */
3586 if (!double_int_fits_to_tree_p (nit_type
, bound
))
3589 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3590 times. This means that:
3592 -- if NITER_BOUND->is_exit is true, then everything after
3593 it at most NITER_BOUND->bound times.
3595 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
3596 is executed, then NITER_BOUND->stmt is executed as well in the same
3597 iteration then STMT is executed at most NITER_BOUND->bound + 1 times.
3599 If we can determine that NITER_BOUND->stmt is always executed
3600 after STMT, then STMT is executed at most NITER_BOUND->bound + 2 times.
3601 We conclude that if both statements belong to the same
3602 basic block and STMT is before NITER_BOUND->stmt and there are no
3603 statements with side effects in between. */
3605 if (niter_bound
->is_exit
)
3607 if (stmt
== niter_bound
->stmt
3608 || !stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
3614 if (!stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
3616 gimple_stmt_iterator bsi
;
3617 if (gimple_bb (stmt
) != gimple_bb (niter_bound
->stmt
)
3618 || gimple_code (stmt
) == GIMPLE_PHI
3619 || gimple_code (niter_bound
->stmt
) == GIMPLE_PHI
)
3622 /* By stmt_dominates_stmt_p we already know that STMT appears
3623 before NITER_BOUND->STMT. Still need to test that the loop
3624 can not be terinated by a side effect in between. */
3625 for (bsi
= gsi_for_stmt (stmt
); gsi_stmt (bsi
) != niter_bound
->stmt
;
3627 if (gimple_has_side_effects (gsi_stmt (bsi
)))
3629 bound
+= double_int_one
;
3630 if (bound
.is_zero ()
3631 || !double_int_fits_to_tree_p (nit_type
, bound
))
3637 e
= fold_binary (cmp
, boolean_type_node
,
3638 niter
, double_int_to_tree (nit_type
, bound
));
3639 return e
&& integer_nonzerop (e
);
3642 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
3645 nowrap_type_p (tree type
)
3647 if (INTEGRAL_TYPE_P (type
)
3648 && TYPE_OVERFLOW_UNDEFINED (type
))
3651 if (POINTER_TYPE_P (type
))
3657 /* Return false only when the induction variable BASE + STEP * I is
3658 known to not overflow: i.e. when the number of iterations is small
3659 enough with respect to the step and initial condition in order to
3660 keep the evolution confined in TYPEs bounds. Return true when the
3661 iv is known to overflow or when the property is not computable.
3663 USE_OVERFLOW_SEMANTICS is true if this function should assume that
3664 the rules for overflow of the given language apply (e.g., that signed
3665 arithmetics in C does not overflow). */
3668 scev_probably_wraps_p (tree base
, tree step
,
3669 gimple at_stmt
, struct loop
*loop
,
3670 bool use_overflow_semantics
)
3672 tree delta
, step_abs
;
3673 tree unsigned_type
, valid_niter
;
3674 tree type
= TREE_TYPE (step
);
3677 struct nb_iter_bound
*bound
;
3679 /* FIXME: We really need something like
3680 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
3682 We used to test for the following situation that frequently appears
3683 during address arithmetics:
3685 D.1621_13 = (long unsigned intD.4) D.1620_12;
3686 D.1622_14 = D.1621_13 * 8;
3687 D.1623_15 = (doubleD.29 *) D.1622_14;
3689 And derived that the sequence corresponding to D_14
3690 can be proved to not wrap because it is used for computing a
3691 memory access; however, this is not really the case -- for example,
3692 if D_12 = (unsigned char) [254,+,1], then D_14 has values
3693 2032, 2040, 0, 8, ..., but the code is still legal. */
3695 if (chrec_contains_undetermined (base
)
3696 || chrec_contains_undetermined (step
))
3699 if (integer_zerop (step
))
3702 /* If we can use the fact that signed and pointer arithmetics does not
3703 wrap, we are done. */
3704 if (use_overflow_semantics
&& nowrap_type_p (TREE_TYPE (base
)))
3707 /* To be able to use estimates on number of iterations of the loop,
3708 we must have an upper bound on the absolute value of the step. */
3709 if (TREE_CODE (step
) != INTEGER_CST
)
3712 /* Don't issue signed overflow warnings. */
3713 fold_defer_overflow_warnings ();
3715 /* Otherwise, compute the number of iterations before we reach the
3716 bound of the type, and verify that the loop is exited before this
3718 unsigned_type
= unsigned_type_for (type
);
3719 base
= fold_convert (unsigned_type
, base
);
3721 if (tree_int_cst_sign_bit (step
))
3723 tree extreme
= fold_convert (unsigned_type
,
3724 lower_bound_in_type (type
, type
));
3725 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
3726 step_abs
= fold_build1 (NEGATE_EXPR
, unsigned_type
,
3727 fold_convert (unsigned_type
, step
));
3731 tree extreme
= fold_convert (unsigned_type
,
3732 upper_bound_in_type (type
, type
));
3733 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
3734 step_abs
= fold_convert (unsigned_type
, step
);
3737 valid_niter
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step_abs
);
3739 estimate_numbers_of_iterations_loop (loop
);
3741 if (max_loop_iterations (loop
, &niter
)
3742 && double_int_fits_to_tree_p (TREE_TYPE (valid_niter
), niter
)
3743 && (e
= fold_binary (GT_EXPR
, boolean_type_node
, valid_niter
,
3744 double_int_to_tree (TREE_TYPE (valid_niter
),
3746 && integer_nonzerop (e
))
3748 fold_undefer_and_ignore_overflow_warnings ();
3752 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
3754 if (n_of_executions_at_most (at_stmt
, bound
, valid_niter
))
3756 fold_undefer_and_ignore_overflow_warnings ();
3761 fold_undefer_and_ignore_overflow_warnings ();
3763 /* At this point we still don't have a proof that the iv does not
3764 overflow: give up. */
3768 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
3771 free_numbers_of_iterations_estimates_loop (struct loop
*loop
)
3773 struct nb_iter_bound
*bound
, *next
;
3775 loop
->nb_iterations
= NULL
;
3776 loop
->estimate_state
= EST_NOT_COMPUTED
;
3777 for (bound
= loop
->bounds
; bound
; bound
= next
)
3783 loop
->bounds
= NULL
;
3786 /* Frees the information on upper bounds on numbers of iterations of loops. */
3789 free_numbers_of_iterations_estimates (void)
3794 FOR_EACH_LOOP (li
, loop
, 0)
3796 free_numbers_of_iterations_estimates_loop (loop
);
3800 /* Substitute value VAL for ssa name NAME inside expressions held
3804 substitute_in_loop_info (struct loop
*loop
, tree name
, tree val
)
3806 loop
->nb_iterations
= simplify_replace_tree (loop
->nb_iterations
, name
, val
);