1 /* Functions to determine/estimate number of iterations of a loop.
2 Copyright (C) 2004-2018 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"
27 #include "tree-pass.h"
29 #include "gimple-pretty-print.h"
30 #include "diagnostic-core.h"
31 #include "stor-layout.h"
32 #include "fold-const.h"
36 #include "gimple-iterator.h"
38 #include "tree-ssa-loop-ivopts.h"
39 #include "tree-ssa-loop-niter.h"
40 #include "tree-ssa-loop.h"
42 #include "tree-chrec.h"
43 #include "tree-scalar-evolution.h"
48 /* The maximum number of dominator BBs we search for conditions
49 of loop header copies we use for simplifying a conditional
51 #define MAX_DOMINATORS_TO_WALK 8
55 Analysis of number of iterations of an affine exit test.
59 /* Bounds on some value, BELOW <= X <= UP. */
66 static bool number_of_iterations_popcount (loop_p loop
, edge exit
,
68 struct tree_niter_desc
*niter
);
71 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */
74 split_to_var_and_offset (tree expr
, tree
*var
, mpz_t offset
)
76 tree type
= TREE_TYPE (expr
);
81 mpz_set_ui (offset
, 0);
83 switch (TREE_CODE (expr
))
90 case POINTER_PLUS_EXPR
:
91 op0
= TREE_OPERAND (expr
, 0);
92 op1
= TREE_OPERAND (expr
, 1);
94 if (TREE_CODE (op1
) != INTEGER_CST
)
98 /* Always sign extend the offset. */
99 wi::to_mpz (wi::to_wide (op1
), offset
, SIGNED
);
101 mpz_neg (offset
, offset
);
105 *var
= build_int_cst_type (type
, 0);
106 wi::to_mpz (wi::to_wide (expr
), offset
, TYPE_SIGN (type
));
114 /* From condition C0 CMP C1 derives information regarding the value range
115 of VAR, which is of TYPE. Results are stored in to BELOW and UP. */
118 refine_value_range_using_guard (tree type
, tree var
,
119 tree c0
, enum tree_code cmp
, tree c1
,
120 mpz_t below
, mpz_t up
)
122 tree varc0
, varc1
, ctype
;
124 mpz_t mint
, maxt
, minc1
, maxc1
;
126 bool no_wrap
= nowrap_type_p (type
);
128 signop sgn
= TYPE_SIGN (type
);
136 STRIP_SIGN_NOPS (c0
);
137 STRIP_SIGN_NOPS (c1
);
138 ctype
= TREE_TYPE (c0
);
139 if (!useless_type_conversion_p (ctype
, type
))
145 /* We could derive quite precise information from EQ_EXPR, however,
146 such a guard is unlikely to appear, so we do not bother with
151 /* NE_EXPR comparisons do not contain much of useful information,
152 except for cases of comparing with bounds. */
153 if (TREE_CODE (c1
) != INTEGER_CST
154 || !INTEGRAL_TYPE_P (type
))
157 /* Ensure that the condition speaks about an expression in the same
159 ctype
= TREE_TYPE (c0
);
160 if (TYPE_PRECISION (ctype
) != TYPE_PRECISION (type
))
162 c0
= fold_convert (type
, c0
);
163 c1
= fold_convert (type
, c1
);
165 if (operand_equal_p (var
, c0
, 0))
169 /* Case of comparing VAR with its below/up bounds. */
171 wi::to_mpz (wi::to_wide (c1
), valc1
, TYPE_SIGN (type
));
172 if (mpz_cmp (valc1
, below
) == 0)
174 if (mpz_cmp (valc1
, up
) == 0)
181 /* Case of comparing with the bounds of the type. */
182 wide_int min
= wi::min_value (type
);
183 wide_int max
= wi::max_value (type
);
185 if (wi::to_wide (c1
) == min
)
187 if (wi::to_wide (c1
) == max
)
191 /* Quick return if no useful information. */
203 split_to_var_and_offset (expand_simple_operations (c0
), &varc0
, offc0
);
204 split_to_var_and_offset (expand_simple_operations (c1
), &varc1
, offc1
);
206 /* We are only interested in comparisons of expressions based on VAR. */
207 if (operand_equal_p (var
, varc1
, 0))
209 std::swap (varc0
, varc1
);
210 mpz_swap (offc0
, offc1
);
211 cmp
= swap_tree_comparison (cmp
);
213 else if (!operand_equal_p (var
, varc0
, 0))
222 get_type_static_bounds (type
, mint
, maxt
);
225 /* Setup range information for varc1. */
226 if (integer_zerop (varc1
))
228 wi::to_mpz (0, minc1
, TYPE_SIGN (type
));
229 wi::to_mpz (0, maxc1
, TYPE_SIGN (type
));
231 else if (TREE_CODE (varc1
) == SSA_NAME
232 && INTEGRAL_TYPE_P (type
)
233 && get_range_info (varc1
, &minv
, &maxv
) == VR_RANGE
)
235 gcc_assert (wi::le_p (minv
, maxv
, sgn
));
236 wi::to_mpz (minv
, minc1
, sgn
);
237 wi::to_mpz (maxv
, maxc1
, sgn
);
241 mpz_set (minc1
, mint
);
242 mpz_set (maxc1
, maxt
);
245 /* Compute valid range information for varc1 + offc1. Note nothing
246 useful can be derived if it overflows or underflows. Overflow or
247 underflow could happen when:
249 offc1 > 0 && varc1 + offc1 > MAX_VAL (type)
250 offc1 < 0 && varc1 + offc1 < MIN_VAL (type). */
251 mpz_add (minc1
, minc1
, offc1
);
252 mpz_add (maxc1
, maxc1
, offc1
);
254 || mpz_sgn (offc1
) == 0
255 || (mpz_sgn (offc1
) < 0 && mpz_cmp (minc1
, mint
) >= 0)
256 || (mpz_sgn (offc1
) > 0 && mpz_cmp (maxc1
, maxt
) <= 0));
260 if (mpz_cmp (minc1
, mint
) < 0)
261 mpz_set (minc1
, mint
);
262 if (mpz_cmp (maxc1
, maxt
) > 0)
263 mpz_set (maxc1
, maxt
);
268 mpz_sub_ui (maxc1
, maxc1
, 1);
273 mpz_add_ui (minc1
, minc1
, 1);
276 /* Compute range information for varc0. If there is no overflow,
277 the condition implied that
279 (varc0) cmp (varc1 + offc1 - offc0)
281 We can possibly improve the upper bound of varc0 if cmp is LE_EXPR,
282 or the below bound if cmp is GE_EXPR.
284 To prove there is no overflow/underflow, we need to check below
286 1) cmp == LE_EXPR && offc0 > 0
288 (varc0 + offc0) doesn't overflow
289 && (varc1 + offc1 - offc0) doesn't underflow
291 2) cmp == LE_EXPR && offc0 < 0
293 (varc0 + offc0) doesn't underflow
294 && (varc1 + offc1 - offc0) doesn't overfloe
296 In this case, (varc0 + offc0) will never underflow if we can
297 prove (varc1 + offc1 - offc0) doesn't overflow.
299 3) cmp == GE_EXPR && offc0 < 0
301 (varc0 + offc0) doesn't underflow
302 && (varc1 + offc1 - offc0) doesn't overflow
304 4) cmp == GE_EXPR && offc0 > 0
306 (varc0 + offc0) doesn't overflow
307 && (varc1 + offc1 - offc0) doesn't underflow
309 In this case, (varc0 + offc0) will never overflow if we can
310 prove (varc1 + offc1 - offc0) doesn't underflow.
312 Note we only handle case 2 and 4 in below code. */
314 mpz_sub (minc1
, minc1
, offc0
);
315 mpz_sub (maxc1
, maxc1
, offc0
);
317 || mpz_sgn (offc0
) == 0
319 && mpz_sgn (offc0
) < 0 && mpz_cmp (maxc1
, maxt
) <= 0)
321 && mpz_sgn (offc0
) > 0 && mpz_cmp (minc1
, mint
) >= 0));
327 if (mpz_cmp (up
, maxc1
) > 0)
332 if (mpz_cmp (below
, minc1
) < 0)
333 mpz_set (below
, minc1
);
345 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
346 in TYPE to MIN and MAX. */
349 determine_value_range (struct loop
*loop
, tree type
, tree var
, mpz_t off
,
350 mpz_t min
, mpz_t max
)
356 enum value_range_type rtype
= VR_VARYING
;
358 /* If the expression is a constant, we know its value exactly. */
359 if (integer_zerop (var
))
366 get_type_static_bounds (type
, min
, max
);
368 /* See if we have some range info from VRP. */
369 if (TREE_CODE (var
) == SSA_NAME
&& INTEGRAL_TYPE_P (type
))
371 edge e
= loop_preheader_edge (loop
);
372 signop sgn
= TYPE_SIGN (type
);
375 /* Either for VAR itself... */
376 rtype
= get_range_info (var
, &minv
, &maxv
);
377 /* Or for PHI results in loop->header where VAR is used as
378 PHI argument from the loop preheader edge. */
379 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
381 gphi
*phi
= gsi
.phi ();
383 if (PHI_ARG_DEF_FROM_EDGE (phi
, e
) == var
384 && (get_range_info (gimple_phi_result (phi
), &minc
, &maxc
)
387 if (rtype
!= VR_RANGE
)
395 minv
= wi::max (minv
, minc
, sgn
);
396 maxv
= wi::min (maxv
, maxc
, sgn
);
397 /* If the PHI result range are inconsistent with
398 the VAR range, give up on looking at the PHI
399 results. This can happen if VR_UNDEFINED is
401 if (wi::gt_p (minv
, maxv
, sgn
))
403 rtype
= get_range_info (var
, &minv
, &maxv
);
411 if (rtype
!= VR_RANGE
)
418 gcc_assert (wi::le_p (minv
, maxv
, sgn
));
419 wi::to_mpz (minv
, minm
, sgn
);
420 wi::to_mpz (maxv
, maxm
, sgn
);
422 /* Now walk the dominators of the loop header and use the entry
423 guards to refine the estimates. */
424 for (bb
= loop
->header
;
425 bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && cnt
< MAX_DOMINATORS_TO_WALK
;
426 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
433 if (!single_pred_p (bb
))
435 e
= single_pred_edge (bb
);
437 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
440 cond
= last_stmt (e
->src
);
441 c0
= gimple_cond_lhs (cond
);
442 cmp
= gimple_cond_code (cond
);
443 c1
= gimple_cond_rhs (cond
);
445 if (e
->flags
& EDGE_FALSE_VALUE
)
446 cmp
= invert_tree_comparison (cmp
, false);
448 refine_value_range_using_guard (type
, var
, c0
, cmp
, c1
, minm
, maxm
);
452 mpz_add (minm
, minm
, off
);
453 mpz_add (maxm
, maxm
, off
);
454 /* If the computation may not wrap or off is zero, then this
455 is always fine. If off is negative and minv + off isn't
456 smaller than type's minimum, or off is positive and
457 maxv + off isn't bigger than type's maximum, use the more
458 precise range too. */
459 if (nowrap_type_p (type
)
460 || mpz_sgn (off
) == 0
461 || (mpz_sgn (off
) < 0 && mpz_cmp (minm
, min
) >= 0)
462 || (mpz_sgn (off
) > 0 && mpz_cmp (maxm
, max
) <= 0))
474 /* If the computation may wrap, we know nothing about the value, except for
475 the range of the type. */
476 if (!nowrap_type_p (type
))
479 /* Since the addition of OFF does not wrap, if OFF is positive, then we may
480 add it to MIN, otherwise to MAX. */
481 if (mpz_sgn (off
) < 0)
482 mpz_add (max
, max
, off
);
484 mpz_add (min
, min
, off
);
487 /* Stores the bounds on the difference of the values of the expressions
488 (var + X) and (var + Y), computed in TYPE, to BNDS. */
491 bound_difference_of_offsetted_base (tree type
, mpz_t x
, mpz_t y
,
494 int rel
= mpz_cmp (x
, y
);
495 bool may_wrap
= !nowrap_type_p (type
);
498 /* If X == Y, then the expressions are always equal.
499 If X > Y, there are the following possibilities:
500 a) neither of var + X and var + Y overflow or underflow, or both of
501 them do. Then their difference is X - Y.
502 b) var + X overflows, and var + Y does not. Then the values of the
503 expressions are var + X - M and var + Y, where M is the range of
504 the type, and their difference is X - Y - M.
505 c) var + Y underflows and var + X does not. Their difference again
507 Therefore, if the arithmetics in type does not overflow, then the
508 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
509 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
510 (X - Y, X - Y + M). */
514 mpz_set_ui (bnds
->below
, 0);
515 mpz_set_ui (bnds
->up
, 0);
520 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), m
, UNSIGNED
);
521 mpz_add_ui (m
, m
, 1);
522 mpz_sub (bnds
->up
, x
, y
);
523 mpz_set (bnds
->below
, bnds
->up
);
528 mpz_sub (bnds
->below
, bnds
->below
, m
);
530 mpz_add (bnds
->up
, bnds
->up
, m
);
536 /* From condition C0 CMP C1 derives information regarding the
537 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
538 and stores it to BNDS. */
541 refine_bounds_using_guard (tree type
, tree varx
, mpz_t offx
,
542 tree vary
, mpz_t offy
,
543 tree c0
, enum tree_code cmp
, tree c1
,
546 tree varc0
, varc1
, ctype
;
547 mpz_t offc0
, offc1
, loffx
, loffy
, bnd
;
549 bool no_wrap
= nowrap_type_p (type
);
558 STRIP_SIGN_NOPS (c0
);
559 STRIP_SIGN_NOPS (c1
);
560 ctype
= TREE_TYPE (c0
);
561 if (!useless_type_conversion_p (ctype
, type
))
567 /* We could derive quite precise information from EQ_EXPR, however, such
568 a guard is unlikely to appear, so we do not bother with handling
573 /* NE_EXPR comparisons do not contain much of useful information, except for
574 special case of comparing with the bounds of the type. */
575 if (TREE_CODE (c1
) != INTEGER_CST
576 || !INTEGRAL_TYPE_P (type
))
579 /* Ensure that the condition speaks about an expression in the same type
581 ctype
= TREE_TYPE (c0
);
582 if (TYPE_PRECISION (ctype
) != TYPE_PRECISION (type
))
584 c0
= fold_convert (type
, c0
);
585 c1
= fold_convert (type
, c1
);
587 if (TYPE_MIN_VALUE (type
)
588 && operand_equal_p (c1
, TYPE_MIN_VALUE (type
), 0))
593 if (TYPE_MAX_VALUE (type
)
594 && operand_equal_p (c1
, TYPE_MAX_VALUE (type
), 0))
607 split_to_var_and_offset (expand_simple_operations (c0
), &varc0
, offc0
);
608 split_to_var_and_offset (expand_simple_operations (c1
), &varc1
, offc1
);
610 /* We are only interested in comparisons of expressions based on VARX and
611 VARY. TODO -- we might also be able to derive some bounds from
612 expressions containing just one of the variables. */
614 if (operand_equal_p (varx
, varc1
, 0))
616 std::swap (varc0
, varc1
);
617 mpz_swap (offc0
, offc1
);
618 cmp
= swap_tree_comparison (cmp
);
621 if (!operand_equal_p (varx
, varc0
, 0)
622 || !operand_equal_p (vary
, varc1
, 0))
625 mpz_init_set (loffx
, offx
);
626 mpz_init_set (loffy
, offy
);
628 if (cmp
== GT_EXPR
|| cmp
== GE_EXPR
)
630 std::swap (varx
, vary
);
631 mpz_swap (offc0
, offc1
);
632 mpz_swap (loffx
, loffy
);
633 cmp
= swap_tree_comparison (cmp
);
637 /* If there is no overflow, the condition implies that
639 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
641 The overflows and underflows may complicate things a bit; each
642 overflow decreases the appropriate offset by M, and underflow
643 increases it by M. The above inequality would not necessarily be
646 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
647 VARX + OFFC0 overflows, but VARX + OFFX does not.
648 This may only happen if OFFX < OFFC0.
649 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
650 VARY + OFFC1 underflows and VARY + OFFY does not.
651 This may only happen if OFFY > OFFC1. */
660 x_ok
= (integer_zerop (varx
)
661 || mpz_cmp (loffx
, offc0
) >= 0);
662 y_ok
= (integer_zerop (vary
)
663 || mpz_cmp (loffy
, offc1
) <= 0);
669 mpz_sub (bnd
, loffx
, loffy
);
670 mpz_add (bnd
, bnd
, offc1
);
671 mpz_sub (bnd
, bnd
, offc0
);
674 mpz_sub_ui (bnd
, bnd
, 1);
679 if (mpz_cmp (bnds
->below
, bnd
) < 0)
680 mpz_set (bnds
->below
, bnd
);
684 if (mpz_cmp (bnd
, bnds
->up
) < 0)
685 mpz_set (bnds
->up
, bnd
);
697 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
698 The subtraction is considered to be performed in arbitrary precision,
701 We do not attempt to be too clever regarding the value ranges of X and
702 Y; most of the time, they are just integers or ssa names offsetted by
703 integer. However, we try to use the information contained in the
704 comparisons before the loop (usually created by loop header copying). */
707 bound_difference (struct loop
*loop
, tree x
, tree y
, bounds
*bnds
)
709 tree type
= TREE_TYPE (x
);
712 mpz_t minx
, maxx
, miny
, maxy
;
720 /* Get rid of unnecessary casts, but preserve the value of
725 mpz_init (bnds
->below
);
729 split_to_var_and_offset (x
, &varx
, offx
);
730 split_to_var_and_offset (y
, &vary
, offy
);
732 if (!integer_zerop (varx
)
733 && operand_equal_p (varx
, vary
, 0))
735 /* Special case VARX == VARY -- we just need to compare the
736 offsets. The matters are a bit more complicated in the
737 case addition of offsets may wrap. */
738 bound_difference_of_offsetted_base (type
, offx
, offy
, bnds
);
742 /* Otherwise, use the value ranges to determine the initial
743 estimates on below and up. */
748 determine_value_range (loop
, type
, varx
, offx
, minx
, maxx
);
749 determine_value_range (loop
, type
, vary
, offy
, miny
, maxy
);
751 mpz_sub (bnds
->below
, minx
, maxy
);
752 mpz_sub (bnds
->up
, maxx
, miny
);
759 /* If both X and Y are constants, we cannot get any more precise. */
760 if (integer_zerop (varx
) && integer_zerop (vary
))
763 /* Now walk the dominators of the loop header and use the entry
764 guards to refine the estimates. */
765 for (bb
= loop
->header
;
766 bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && cnt
< MAX_DOMINATORS_TO_WALK
;
767 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
769 if (!single_pred_p (bb
))
771 e
= single_pred_edge (bb
);
773 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
776 cond
= last_stmt (e
->src
);
777 c0
= gimple_cond_lhs (cond
);
778 cmp
= gimple_cond_code (cond
);
779 c1
= gimple_cond_rhs (cond
);
781 if (e
->flags
& EDGE_FALSE_VALUE
)
782 cmp
= invert_tree_comparison (cmp
, false);
784 refine_bounds_using_guard (type
, varx
, offx
, vary
, offy
,
794 /* Update the bounds in BNDS that restrict the value of X to the bounds
795 that restrict the value of X + DELTA. X can be obtained as a
796 difference of two values in TYPE. */
799 bounds_add (bounds
*bnds
, const widest_int
&delta
, tree type
)
804 wi::to_mpz (delta
, mdelta
, SIGNED
);
807 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), max
, UNSIGNED
);
809 mpz_add (bnds
->up
, bnds
->up
, mdelta
);
810 mpz_add (bnds
->below
, bnds
->below
, mdelta
);
812 if (mpz_cmp (bnds
->up
, max
) > 0)
813 mpz_set (bnds
->up
, max
);
816 if (mpz_cmp (bnds
->below
, max
) < 0)
817 mpz_set (bnds
->below
, max
);
823 /* Update the bounds in BNDS that restrict the value of X to the bounds
824 that restrict the value of -X. */
827 bounds_negate (bounds
*bnds
)
831 mpz_init_set (tmp
, bnds
->up
);
832 mpz_neg (bnds
->up
, bnds
->below
);
833 mpz_neg (bnds
->below
, tmp
);
837 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
840 inverse (tree x
, tree mask
)
842 tree type
= TREE_TYPE (x
);
844 unsigned ctr
= tree_floor_log2 (mask
);
846 if (TYPE_PRECISION (type
) <= HOST_BITS_PER_WIDE_INT
)
848 unsigned HOST_WIDE_INT ix
;
849 unsigned HOST_WIDE_INT imask
;
850 unsigned HOST_WIDE_INT irslt
= 1;
852 gcc_assert (cst_and_fits_in_hwi (x
));
853 gcc_assert (cst_and_fits_in_hwi (mask
));
855 ix
= int_cst_value (x
);
856 imask
= int_cst_value (mask
);
865 rslt
= build_int_cst_type (type
, irslt
);
869 rslt
= build_int_cst (type
, 1);
872 rslt
= int_const_binop (MULT_EXPR
, rslt
, x
);
873 x
= int_const_binop (MULT_EXPR
, x
, x
);
875 rslt
= int_const_binop (BIT_AND_EXPR
, rslt
, mask
);
881 /* Derives the upper bound BND on the number of executions of loop with exit
882 condition S * i <> C. If NO_OVERFLOW is true, then the control variable of
883 the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed
884 that the loop ends through this exit, i.e., the induction variable ever
885 reaches the value of C.
887 The value C is equal to final - base, where final and base are the final and
888 initial value of the actual induction variable in the analysed loop. BNDS
889 bounds the value of this difference when computed in signed type with
890 unbounded range, while the computation of C is performed in an unsigned
891 type with the range matching the range of the type of the induction variable.
892 In particular, BNDS.up contains an upper bound on C in the following cases:
893 -- if the iv must reach its final value without overflow, i.e., if
894 NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
895 -- if final >= base, which we know to hold when BNDS.below >= 0. */
898 number_of_iterations_ne_max (mpz_t bnd
, bool no_overflow
, tree c
, tree s
,
899 bounds
*bnds
, bool exit_must_be_taken
)
903 tree type
= TREE_TYPE (c
);
904 bool bnds_u_valid
= ((no_overflow
&& exit_must_be_taken
)
905 || mpz_sgn (bnds
->below
) >= 0);
908 || (TREE_CODE (c
) == INTEGER_CST
909 && TREE_CODE (s
) == INTEGER_CST
910 && wi::mod_trunc (wi::to_wide (c
), wi::to_wide (s
),
911 TYPE_SIGN (type
)) == 0)
912 || (TYPE_OVERFLOW_UNDEFINED (type
)
913 && multiple_of_p (type
, c
, s
)))
915 /* If C is an exact multiple of S, then its value will be reached before
916 the induction variable overflows (unless the loop is exited in some
917 other way before). Note that the actual induction variable in the
918 loop (which ranges from base to final instead of from 0 to C) may
919 overflow, in which case BNDS.up will not be giving a correct upper
920 bound on C; thus, BNDS_U_VALID had to be computed in advance. */
922 exit_must_be_taken
= true;
925 /* If the induction variable can overflow, the number of iterations is at
926 most the period of the control variable (or infinite, but in that case
927 the whole # of iterations analysis will fail). */
930 max
= wi::mask
<widest_int
> (TYPE_PRECISION (type
)
931 - wi::ctz (wi::to_wide (s
)), false);
932 wi::to_mpz (max
, bnd
, UNSIGNED
);
936 /* Now we know that the induction variable does not overflow, so the loop
937 iterates at most (range of type / S) times. */
938 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), bnd
, UNSIGNED
);
940 /* If the induction variable is guaranteed to reach the value of C before
942 if (exit_must_be_taken
)
944 /* ... then we can strengthen this to C / S, and possibly we can use
945 the upper bound on C given by BNDS. */
946 if (TREE_CODE (c
) == INTEGER_CST
)
947 wi::to_mpz (wi::to_wide (c
), bnd
, UNSIGNED
);
948 else if (bnds_u_valid
)
949 mpz_set (bnd
, bnds
->up
);
953 wi::to_mpz (wi::to_wide (s
), d
, UNSIGNED
);
954 mpz_fdiv_q (bnd
, bnd
, d
);
958 /* Determines number of iterations of loop whose ending condition
959 is IV <> FINAL. TYPE is the type of the iv. The number of
960 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
961 we know that the exit must be taken eventually, i.e., that the IV
962 ever reaches the value FINAL (we derived this earlier, and possibly set
963 NITER->assumptions to make sure this is the case). BNDS contains the
964 bounds on the difference FINAL - IV->base. */
967 number_of_iterations_ne (struct loop
*loop
, tree type
, affine_iv
*iv
,
968 tree final
, struct tree_niter_desc
*niter
,
969 bool exit_must_be_taken
, bounds
*bnds
)
971 tree niter_type
= unsigned_type_for (type
);
972 tree s
, c
, d
, bits
, assumption
, tmp
, bound
;
975 niter
->control
= *iv
;
976 niter
->bound
= final
;
977 niter
->cmp
= NE_EXPR
;
979 /* Rearrange the terms so that we get inequality S * i <> C, with S
980 positive. Also cast everything to the unsigned type. If IV does
981 not overflow, BNDS bounds the value of C. Also, this is the
982 case if the computation |FINAL - IV->base| does not overflow, i.e.,
983 if BNDS->below in the result is nonnegative. */
984 if (tree_int_cst_sign_bit (iv
->step
))
986 s
= fold_convert (niter_type
,
987 fold_build1 (NEGATE_EXPR
, type
, iv
->step
));
988 c
= fold_build2 (MINUS_EXPR
, niter_type
,
989 fold_convert (niter_type
, iv
->base
),
990 fold_convert (niter_type
, final
));
991 bounds_negate (bnds
);
995 s
= fold_convert (niter_type
, iv
->step
);
996 c
= fold_build2 (MINUS_EXPR
, niter_type
,
997 fold_convert (niter_type
, final
),
998 fold_convert (niter_type
, iv
->base
));
1002 number_of_iterations_ne_max (max
, iv
->no_overflow
, c
, s
, bnds
,
1003 exit_must_be_taken
);
1004 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, max
, false),
1005 TYPE_SIGN (niter_type
));
1008 /* Compute no-overflow information for the control iv. This can be
1009 proven when below two conditions are satisfied:
1011 1) IV evaluates toward FINAL at beginning, i.e:
1012 base <= FINAL ; step > 0
1013 base >= FINAL ; step < 0
1015 2) |FINAL - base| is an exact multiple of step.
1017 Unfortunately, it's hard to prove above conditions after pass loop-ch
1018 because loop with exit condition (IV != FINAL) usually will be guarded
1019 by initial-condition (IV.base - IV.step != FINAL). In this case, we
1020 can alternatively try to prove below conditions:
1022 1') IV evaluates toward FINAL at beginning, i.e:
1023 new_base = base - step < FINAL ; step > 0
1024 && base - step doesn't underflow
1025 new_base = base - step > FINAL ; step < 0
1026 && base - step doesn't overflow
1028 2') |FINAL - new_base| is an exact multiple of step.
1030 Please refer to PR34114 as an example of loop-ch's impact, also refer
1031 to PR72817 as an example why condition 2') is necessary.
1033 Note, for NE_EXPR, base equals to FINAL is a special case, in
1034 which the loop exits immediately, and the iv does not overflow. */
1035 if (!niter
->control
.no_overflow
1036 && (integer_onep (s
) || multiple_of_p (type
, c
, s
)))
1038 tree t
, cond
, new_c
, relaxed_cond
= boolean_false_node
;
1040 if (tree_int_cst_sign_bit (iv
->step
))
1042 cond
= fold_build2 (GE_EXPR
, boolean_type_node
, iv
->base
, final
);
1043 if (TREE_CODE (type
) == INTEGER_TYPE
)
1045 /* Only when base - step doesn't overflow. */
1046 t
= TYPE_MAX_VALUE (type
);
1047 t
= fold_build2 (PLUS_EXPR
, type
, t
, iv
->step
);
1048 t
= fold_build2 (GE_EXPR
, boolean_type_node
, t
, iv
->base
);
1049 if (integer_nonzerop (t
))
1051 t
= fold_build2 (MINUS_EXPR
, type
, iv
->base
, iv
->step
);
1052 new_c
= fold_build2 (MINUS_EXPR
, niter_type
,
1053 fold_convert (niter_type
, t
),
1054 fold_convert (niter_type
, final
));
1055 if (multiple_of_p (type
, new_c
, s
))
1056 relaxed_cond
= fold_build2 (GT_EXPR
, boolean_type_node
,
1063 cond
= fold_build2 (LE_EXPR
, boolean_type_node
, iv
->base
, final
);
1064 if (TREE_CODE (type
) == INTEGER_TYPE
)
1066 /* Only when base - step doesn't underflow. */
1067 t
= TYPE_MIN_VALUE (type
);
1068 t
= fold_build2 (PLUS_EXPR
, type
, t
, iv
->step
);
1069 t
= fold_build2 (LE_EXPR
, boolean_type_node
, t
, iv
->base
);
1070 if (integer_nonzerop (t
))
1072 t
= fold_build2 (MINUS_EXPR
, type
, iv
->base
, iv
->step
);
1073 new_c
= fold_build2 (MINUS_EXPR
, niter_type
,
1074 fold_convert (niter_type
, final
),
1075 fold_convert (niter_type
, t
));
1076 if (multiple_of_p (type
, new_c
, s
))
1077 relaxed_cond
= fold_build2 (LT_EXPR
, boolean_type_node
,
1083 t
= simplify_using_initial_conditions (loop
, cond
);
1084 if (!t
|| !integer_onep (t
))
1085 t
= simplify_using_initial_conditions (loop
, relaxed_cond
);
1087 if (t
&& integer_onep (t
))
1088 niter
->control
.no_overflow
= true;
1091 /* First the trivial cases -- when the step is 1. */
1092 if (integer_onep (s
))
1097 if (niter
->control
.no_overflow
&& multiple_of_p (type
, c
, s
))
1099 niter
->niter
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, c
, s
);
1103 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
1104 is infinite. Otherwise, the number of iterations is
1105 (inverse(s/d) * (c/d)) mod (size of mode/d). */
1106 bits
= num_ending_zeros (s
);
1107 bound
= build_low_bits_mask (niter_type
,
1108 (TYPE_PRECISION (niter_type
)
1109 - tree_to_uhwi (bits
)));
1111 d
= fold_binary_to_constant (LSHIFT_EXPR
, niter_type
,
1112 build_int_cst (niter_type
, 1), bits
);
1113 s
= fold_binary_to_constant (RSHIFT_EXPR
, niter_type
, s
, bits
);
1115 if (!exit_must_be_taken
)
1117 /* If we cannot assume that the exit is taken eventually, record the
1118 assumptions for divisibility of c. */
1119 assumption
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, c
, d
);
1120 assumption
= fold_build2 (EQ_EXPR
, boolean_type_node
,
1121 assumption
, build_int_cst (niter_type
, 0));
1122 if (!integer_nonzerop (assumption
))
1123 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1124 niter
->assumptions
, assumption
);
1127 c
= fold_build2 (EXACT_DIV_EXPR
, niter_type
, c
, d
);
1128 tmp
= fold_build2 (MULT_EXPR
, niter_type
, c
, inverse (s
, bound
));
1129 niter
->niter
= fold_build2 (BIT_AND_EXPR
, niter_type
, tmp
, bound
);
1133 /* Checks whether we can determine the final value of the control variable
1134 of the loop with ending condition IV0 < IV1 (computed in TYPE).
1135 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
1136 of the step. The assumptions necessary to ensure that the computation
1137 of the final value does not overflow are recorded in NITER. If we
1138 find the final value, we adjust DELTA and return TRUE. Otherwise
1139 we return false. BNDS bounds the value of IV1->base - IV0->base,
1140 and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
1141 true if we know that the exit must be taken eventually. */
1144 number_of_iterations_lt_to_ne (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1145 struct tree_niter_desc
*niter
,
1146 tree
*delta
, tree step
,
1147 bool exit_must_be_taken
, bounds
*bnds
)
1149 tree niter_type
= TREE_TYPE (step
);
1150 tree mod
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, *delta
, step
);
1153 tree assumption
= boolean_true_node
, bound
, noloop
;
1154 bool ret
= false, fv_comp_no_overflow
;
1156 if (POINTER_TYPE_P (type
))
1159 if (TREE_CODE (mod
) != INTEGER_CST
)
1161 if (integer_nonzerop (mod
))
1162 mod
= fold_build2 (MINUS_EXPR
, niter_type
, step
, mod
);
1163 tmod
= fold_convert (type1
, mod
);
1166 wi::to_mpz (wi::to_wide (mod
), mmod
, UNSIGNED
);
1167 mpz_neg (mmod
, mmod
);
1169 /* If the induction variable does not overflow and the exit is taken,
1170 then the computation of the final value does not overflow. This is
1171 also obviously the case if the new final value is equal to the
1172 current one. Finally, we postulate this for pointer type variables,
1173 as the code cannot rely on the object to that the pointer points being
1174 placed at the end of the address space (and more pragmatically,
1175 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
1176 if (integer_zerop (mod
) || POINTER_TYPE_P (type
))
1177 fv_comp_no_overflow
= true;
1178 else if (!exit_must_be_taken
)
1179 fv_comp_no_overflow
= false;
1181 fv_comp_no_overflow
=
1182 (iv0
->no_overflow
&& integer_nonzerop (iv0
->step
))
1183 || (iv1
->no_overflow
&& integer_nonzerop (iv1
->step
));
1185 if (integer_nonzerop (iv0
->step
))
1187 /* The final value of the iv is iv1->base + MOD, assuming that this
1188 computation does not overflow, and that
1189 iv0->base <= iv1->base + MOD. */
1190 if (!fv_comp_no_overflow
)
1192 bound
= fold_build2 (MINUS_EXPR
, type1
,
1193 TYPE_MAX_VALUE (type1
), tmod
);
1194 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
1196 if (integer_zerop (assumption
))
1199 if (mpz_cmp (mmod
, bnds
->below
) < 0)
1200 noloop
= boolean_false_node
;
1201 else if (POINTER_TYPE_P (type
))
1202 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
1204 fold_build_pointer_plus (iv1
->base
, tmod
));
1206 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
1208 fold_build2 (PLUS_EXPR
, type1
,
1213 /* The final value of the iv is iv0->base - MOD, assuming that this
1214 computation does not overflow, and that
1215 iv0->base - MOD <= iv1->base. */
1216 if (!fv_comp_no_overflow
)
1218 bound
= fold_build2 (PLUS_EXPR
, type1
,
1219 TYPE_MIN_VALUE (type1
), tmod
);
1220 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
1222 if (integer_zerop (assumption
))
1225 if (mpz_cmp (mmod
, bnds
->below
) < 0)
1226 noloop
= boolean_false_node
;
1227 else if (POINTER_TYPE_P (type
))
1228 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
1229 fold_build_pointer_plus (iv0
->base
,
1230 fold_build1 (NEGATE_EXPR
,
1234 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
1235 fold_build2 (MINUS_EXPR
, type1
,
1240 if (!integer_nonzerop (assumption
))
1241 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1244 if (!integer_zerop (noloop
))
1245 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1248 bounds_add (bnds
, wi::to_widest (mod
), type
);
1249 *delta
= fold_build2 (PLUS_EXPR
, niter_type
, *delta
, mod
);
1257 /* Add assertions to NITER that ensure that the control variable of the loop
1258 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
1259 are TYPE. Returns false if we can prove that there is an overflow, true
1260 otherwise. STEP is the absolute value of the step. */
1263 assert_no_overflow_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1264 struct tree_niter_desc
*niter
, tree step
)
1266 tree bound
, d
, assumption
, diff
;
1267 tree niter_type
= TREE_TYPE (step
);
1269 if (integer_nonzerop (iv0
->step
))
1271 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
1272 if (iv0
->no_overflow
)
1275 /* If iv0->base is a constant, we can determine the last value before
1276 overflow precisely; otherwise we conservatively assume
1279 if (TREE_CODE (iv0
->base
) == INTEGER_CST
)
1281 d
= fold_build2 (MINUS_EXPR
, niter_type
,
1282 fold_convert (niter_type
, TYPE_MAX_VALUE (type
)),
1283 fold_convert (niter_type
, iv0
->base
));
1284 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
1287 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
1288 build_int_cst (niter_type
, 1));
1289 bound
= fold_build2 (MINUS_EXPR
, type
,
1290 TYPE_MAX_VALUE (type
), fold_convert (type
, diff
));
1291 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
1296 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
1297 if (iv1
->no_overflow
)
1300 if (TREE_CODE (iv1
->base
) == INTEGER_CST
)
1302 d
= fold_build2 (MINUS_EXPR
, niter_type
,
1303 fold_convert (niter_type
, iv1
->base
),
1304 fold_convert (niter_type
, TYPE_MIN_VALUE (type
)));
1305 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
1308 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
1309 build_int_cst (niter_type
, 1));
1310 bound
= fold_build2 (PLUS_EXPR
, type
,
1311 TYPE_MIN_VALUE (type
), fold_convert (type
, diff
));
1312 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
1316 if (integer_zerop (assumption
))
1318 if (!integer_nonzerop (assumption
))
1319 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1320 niter
->assumptions
, assumption
);
1322 iv0
->no_overflow
= true;
1323 iv1
->no_overflow
= true;
1327 /* Add an assumption to NITER that a loop whose ending condition
1328 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
1329 bounds the value of IV1->base - IV0->base. */
1332 assert_loop_rolls_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1333 struct tree_niter_desc
*niter
, bounds
*bnds
)
1335 tree assumption
= boolean_true_node
, bound
, diff
;
1336 tree mbz
, mbzl
, mbzr
, type1
;
1337 bool rolls_p
, no_overflow_p
;
1341 /* We are going to compute the number of iterations as
1342 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
1343 variant of TYPE. This formula only works if
1345 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
1347 (where MAX is the maximum value of the unsigned variant of TYPE, and
1348 the computations in this formula are performed in full precision,
1349 i.e., without overflows).
1351 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
1352 we have a condition of the form iv0->base - step < iv1->base before the loop,
1353 and for loops iv0->base < iv1->base - step * i the condition
1354 iv0->base < iv1->base + step, due to loop header copying, which enable us
1355 to prove the lower bound.
1357 The upper bound is more complicated. Unless the expressions for initial
1358 and final value themselves contain enough information, we usually cannot
1359 derive it from the context. */
1361 /* First check whether the answer does not follow from the bounds we gathered
1363 if (integer_nonzerop (iv0
->step
))
1364 dstep
= wi::to_widest (iv0
->step
);
1367 dstep
= wi::sext (wi::to_widest (iv1
->step
), TYPE_PRECISION (type
));
1372 wi::to_mpz (dstep
, mstep
, UNSIGNED
);
1373 mpz_neg (mstep
, mstep
);
1374 mpz_add_ui (mstep
, mstep
, 1);
1376 rolls_p
= mpz_cmp (mstep
, bnds
->below
) <= 0;
1379 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), max
, UNSIGNED
);
1380 mpz_add (max
, max
, mstep
);
1381 no_overflow_p
= (mpz_cmp (bnds
->up
, max
) <= 0
1382 /* For pointers, only values lying inside a single object
1383 can be compared or manipulated by pointer arithmetics.
1384 Gcc in general does not allow or handle objects larger
1385 than half of the address space, hence the upper bound
1386 is satisfied for pointers. */
1387 || POINTER_TYPE_P (type
));
1391 if (rolls_p
&& no_overflow_p
)
1395 if (POINTER_TYPE_P (type
))
1398 /* Now the hard part; we must formulate the assumption(s) as expressions, and
1399 we must be careful not to introduce overflow. */
1401 if (integer_nonzerop (iv0
->step
))
1403 diff
= fold_build2 (MINUS_EXPR
, type1
,
1404 iv0
->step
, build_int_cst (type1
, 1));
1406 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
1407 0 address never belongs to any object, we can assume this for
1409 if (!POINTER_TYPE_P (type
))
1411 bound
= fold_build2 (PLUS_EXPR
, type1
,
1412 TYPE_MIN_VALUE (type
), diff
);
1413 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
1417 /* And then we can compute iv0->base - diff, and compare it with
1419 mbzl
= fold_build2 (MINUS_EXPR
, type1
,
1420 fold_convert (type1
, iv0
->base
), diff
);
1421 mbzr
= fold_convert (type1
, iv1
->base
);
1425 diff
= fold_build2 (PLUS_EXPR
, type1
,
1426 iv1
->step
, build_int_cst (type1
, 1));
1428 if (!POINTER_TYPE_P (type
))
1430 bound
= fold_build2 (PLUS_EXPR
, type1
,
1431 TYPE_MAX_VALUE (type
), diff
);
1432 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
1436 mbzl
= fold_convert (type1
, iv0
->base
);
1437 mbzr
= fold_build2 (MINUS_EXPR
, type1
,
1438 fold_convert (type1
, iv1
->base
), diff
);
1441 if (!integer_nonzerop (assumption
))
1442 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1443 niter
->assumptions
, assumption
);
1446 mbz
= fold_build2 (GT_EXPR
, boolean_type_node
, mbzl
, mbzr
);
1447 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1448 niter
->may_be_zero
, mbz
);
1452 /* Determines number of iterations of loop whose ending condition
1453 is IV0 < IV1. TYPE is the type of the iv. The number of
1454 iterations is stored to NITER. BNDS bounds the difference
1455 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
1456 that the exit must be taken eventually. */
1459 number_of_iterations_lt (struct loop
*loop
, tree type
, affine_iv
*iv0
,
1460 affine_iv
*iv1
, struct tree_niter_desc
*niter
,
1461 bool exit_must_be_taken
, bounds
*bnds
)
1463 tree niter_type
= unsigned_type_for (type
);
1464 tree delta
, step
, s
;
1467 if (integer_nonzerop (iv0
->step
))
1469 niter
->control
= *iv0
;
1470 niter
->cmp
= LT_EXPR
;
1471 niter
->bound
= iv1
->base
;
1475 niter
->control
= *iv1
;
1476 niter
->cmp
= GT_EXPR
;
1477 niter
->bound
= iv0
->base
;
1480 delta
= fold_build2 (MINUS_EXPR
, niter_type
,
1481 fold_convert (niter_type
, iv1
->base
),
1482 fold_convert (niter_type
, iv0
->base
));
1484 /* First handle the special case that the step is +-1. */
1485 if ((integer_onep (iv0
->step
) && integer_zerop (iv1
->step
))
1486 || (integer_all_onesp (iv1
->step
) && integer_zerop (iv0
->step
)))
1488 /* for (i = iv0->base; i < iv1->base; i++)
1492 for (i = iv1->base; i > iv0->base; i--).
1494 In both cases # of iterations is iv1->base - iv0->base, assuming that
1495 iv1->base >= iv0->base.
1497 First try to derive a lower bound on the value of
1498 iv1->base - iv0->base, computed in full precision. If the difference
1499 is nonnegative, we are done, otherwise we must record the
1502 if (mpz_sgn (bnds
->below
) < 0)
1503 niter
->may_be_zero
= fold_build2 (LT_EXPR
, boolean_type_node
,
1504 iv1
->base
, iv0
->base
);
1505 niter
->niter
= delta
;
1506 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, bnds
->up
, false),
1507 TYPE_SIGN (niter_type
));
1508 niter
->control
.no_overflow
= true;
1512 if (integer_nonzerop (iv0
->step
))
1513 step
= fold_convert (niter_type
, iv0
->step
);
1515 step
= fold_convert (niter_type
,
1516 fold_build1 (NEGATE_EXPR
, type
, iv1
->step
));
1518 /* If we can determine the final value of the control iv exactly, we can
1519 transform the condition to != comparison. In particular, this will be
1520 the case if DELTA is constant. */
1521 if (number_of_iterations_lt_to_ne (type
, iv0
, iv1
, niter
, &delta
, step
,
1522 exit_must_be_taken
, bnds
))
1526 zps
.base
= build_int_cst (niter_type
, 0);
1528 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1529 zps does not overflow. */
1530 zps
.no_overflow
= true;
1532 return number_of_iterations_ne (loop
, type
, &zps
,
1533 delta
, niter
, true, bnds
);
1536 /* Make sure that the control iv does not overflow. */
1537 if (!assert_no_overflow_lt (type
, iv0
, iv1
, niter
, step
))
1540 /* We determine the number of iterations as (delta + step - 1) / step. For
1541 this to work, we must know that iv1->base >= iv0->base - step + 1,
1542 otherwise the loop does not roll. */
1543 assert_loop_rolls_lt (type
, iv0
, iv1
, niter
, bnds
);
1545 s
= fold_build2 (MINUS_EXPR
, niter_type
,
1546 step
, build_int_cst (niter_type
, 1));
1547 delta
= fold_build2 (PLUS_EXPR
, niter_type
, delta
, s
);
1548 niter
->niter
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, delta
, step
);
1552 wi::to_mpz (wi::to_wide (step
), mstep
, UNSIGNED
);
1553 mpz_add (tmp
, bnds
->up
, mstep
);
1554 mpz_sub_ui (tmp
, tmp
, 1);
1555 mpz_fdiv_q (tmp
, tmp
, mstep
);
1556 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, tmp
, false),
1557 TYPE_SIGN (niter_type
));
1564 /* Determines number of iterations of loop whose ending condition
1565 is IV0 <= IV1. TYPE is the type of the iv. The number of
1566 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
1567 we know that this condition must eventually become false (we derived this
1568 earlier, and possibly set NITER->assumptions to make sure this
1569 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1572 number_of_iterations_le (struct loop
*loop
, tree type
, affine_iv
*iv0
,
1573 affine_iv
*iv1
, struct tree_niter_desc
*niter
,
1574 bool exit_must_be_taken
, bounds
*bnds
)
1578 if (POINTER_TYPE_P (type
))
1581 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1582 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1583 value of the type. This we must know anyway, since if it is
1584 equal to this value, the loop rolls forever. We do not check
1585 this condition for pointer type ivs, as the code cannot rely on
1586 the object to that the pointer points being placed at the end of
1587 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1588 not defined for pointers). */
1590 if (!exit_must_be_taken
&& !POINTER_TYPE_P (type
))
1592 if (integer_nonzerop (iv0
->step
))
1593 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1594 iv1
->base
, TYPE_MAX_VALUE (type
));
1596 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1597 iv0
->base
, TYPE_MIN_VALUE (type
));
1599 if (integer_zerop (assumption
))
1601 if (!integer_nonzerop (assumption
))
1602 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1603 niter
->assumptions
, assumption
);
1606 if (integer_nonzerop (iv0
->step
))
1608 if (POINTER_TYPE_P (type
))
1609 iv1
->base
= fold_build_pointer_plus_hwi (iv1
->base
, 1);
1611 iv1
->base
= fold_build2 (PLUS_EXPR
, type1
, iv1
->base
,
1612 build_int_cst (type1
, 1));
1614 else if (POINTER_TYPE_P (type
))
1615 iv0
->base
= fold_build_pointer_plus_hwi (iv0
->base
, -1);
1617 iv0
->base
= fold_build2 (MINUS_EXPR
, type1
,
1618 iv0
->base
, build_int_cst (type1
, 1));
1620 bounds_add (bnds
, 1, type1
);
1622 return number_of_iterations_lt (loop
, type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1626 /* Dumps description of affine induction variable IV to FILE. */
1629 dump_affine_iv (FILE *file
, affine_iv
*iv
)
1631 if (!integer_zerop (iv
->step
))
1632 fprintf (file
, "[");
1634 print_generic_expr (dump_file
, iv
->base
, TDF_SLIM
);
1636 if (!integer_zerop (iv
->step
))
1638 fprintf (file
, ", + , ");
1639 print_generic_expr (dump_file
, iv
->step
, TDF_SLIM
);
1640 fprintf (file
, "]%s", iv
->no_overflow
? "(no_overflow)" : "");
1644 /* Determine the number of iterations according to condition (for staying
1645 inside loop) which compares two induction variables using comparison
1646 operator CODE. The induction variable on left side of the comparison
1647 is IV0, the right-hand side is IV1. Both induction variables must have
1648 type TYPE, which must be an integer or pointer type. The steps of the
1649 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1651 LOOP is the loop whose number of iterations we are determining.
1653 ONLY_EXIT is true if we are sure this is the only way the loop could be
1654 exited (including possibly non-returning function calls, exceptions, etc.)
1655 -- in this case we can use the information whether the control induction
1656 variables can overflow or not in a more efficient way.
1658 if EVERY_ITERATION is true, we know the test is executed on every iteration.
1660 The results (number of iterations and assumptions as described in
1661 comments at struct tree_niter_desc in tree-ssa-loop.h) are stored to NITER.
1662 Returns false if it fails to determine number of iterations, true if it
1663 was determined (possibly with some assumptions). */
1666 number_of_iterations_cond (struct loop
*loop
,
1667 tree type
, affine_iv
*iv0
, enum tree_code code
,
1668 affine_iv
*iv1
, struct tree_niter_desc
*niter
,
1669 bool only_exit
, bool every_iteration
)
1671 bool exit_must_be_taken
= false, ret
;
1674 /* If the test is not executed every iteration, wrapping may make the test
1676 TODO: the overflow case can be still used as unreliable estimate of upper
1677 bound. But we have no API to pass it down to number of iterations code
1678 and, at present, it will not use it anyway. */
1679 if (!every_iteration
1680 && (!iv0
->no_overflow
|| !iv1
->no_overflow
1681 || code
== NE_EXPR
|| code
== EQ_EXPR
))
1684 /* The meaning of these assumptions is this:
1686 then the rest of information does not have to be valid
1687 if may_be_zero then the loop does not roll, even if
1689 niter
->assumptions
= boolean_true_node
;
1690 niter
->may_be_zero
= boolean_false_node
;
1691 niter
->niter
= NULL_TREE
;
1693 niter
->bound
= NULL_TREE
;
1694 niter
->cmp
= ERROR_MARK
;
1696 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1697 the control variable is on lhs. */
1698 if (code
== GE_EXPR
|| code
== GT_EXPR
1699 || (code
== NE_EXPR
&& integer_zerop (iv0
->step
)))
1701 std::swap (iv0
, iv1
);
1702 code
= swap_tree_comparison (code
);
1705 if (POINTER_TYPE_P (type
))
1707 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1708 to the same object. If they do, the control variable cannot wrap
1709 (as wrap around the bounds of memory will never return a pointer
1710 that would be guaranteed to point to the same object, even if we
1711 avoid undefined behavior by casting to size_t and back). */
1712 iv0
->no_overflow
= true;
1713 iv1
->no_overflow
= true;
1716 /* If the control induction variable does not overflow and the only exit
1717 from the loop is the one that we analyze, we know it must be taken
1721 if (!integer_zerop (iv0
->step
) && iv0
->no_overflow
)
1722 exit_must_be_taken
= true;
1723 else if (!integer_zerop (iv1
->step
) && iv1
->no_overflow
)
1724 exit_must_be_taken
= true;
1727 /* We can handle cases which neither of the sides of the comparison is
1730 {iv0.base, iv0.step} cmp_code {iv1.base, iv1.step}
1732 {iv0.base, iv0.step - iv1.step} cmp_code {iv1.base, 0}
1734 provided that either below condition is satisfied:
1736 a) the test is NE_EXPR;
1737 b) iv0.step - iv1.step is integer and iv0/iv1 don't overflow.
1739 This rarely occurs in practice, but it is simple enough to manage. */
1740 if (!integer_zerop (iv0
->step
) && !integer_zerop (iv1
->step
))
1742 tree step_type
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1743 tree step
= fold_binary_to_constant (MINUS_EXPR
, step_type
,
1744 iv0
->step
, iv1
->step
);
1746 /* No need to check sign of the new step since below code takes care
1749 && (TREE_CODE (step
) != INTEGER_CST
1750 || !iv0
->no_overflow
|| !iv1
->no_overflow
))
1754 if (!POINTER_TYPE_P (type
))
1755 iv0
->no_overflow
= false;
1757 iv1
->step
= build_int_cst (step_type
, 0);
1758 iv1
->no_overflow
= true;
1761 /* If the result of the comparison is a constant, the loop is weird. More
1762 precise handling would be possible, but the situation is not common enough
1763 to waste time on it. */
1764 if (integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
))
1767 /* Ignore loops of while (i-- < 10) type. */
1768 if (code
!= NE_EXPR
)
1770 if (iv0
->step
&& tree_int_cst_sign_bit (iv0
->step
))
1773 if (!integer_zerop (iv1
->step
) && !tree_int_cst_sign_bit (iv1
->step
))
1777 /* If the loop exits immediately, there is nothing to do. */
1778 tree tem
= fold_binary (code
, boolean_type_node
, iv0
->base
, iv1
->base
);
1779 if (tem
&& integer_zerop (tem
))
1781 niter
->niter
= build_int_cst (unsigned_type_for (type
), 0);
1786 /* OK, now we know we have a senseful loop. Handle several cases, depending
1787 on what comparison operator is used. */
1788 bound_difference (loop
, iv1
->base
, iv0
->base
, &bnds
);
1790 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1793 "Analyzing # of iterations of loop %d\n", loop
->num
);
1795 fprintf (dump_file
, " exit condition ");
1796 dump_affine_iv (dump_file
, iv0
);
1797 fprintf (dump_file
, " %s ",
1798 code
== NE_EXPR
? "!="
1799 : code
== LT_EXPR
? "<"
1801 dump_affine_iv (dump_file
, iv1
);
1802 fprintf (dump_file
, "\n");
1804 fprintf (dump_file
, " bounds on difference of bases: ");
1805 mpz_out_str (dump_file
, 10, bnds
.below
);
1806 fprintf (dump_file
, " ... ");
1807 mpz_out_str (dump_file
, 10, bnds
.up
);
1808 fprintf (dump_file
, "\n");
1814 gcc_assert (integer_zerop (iv1
->step
));
1815 ret
= number_of_iterations_ne (loop
, type
, iv0
, iv1
->base
, niter
,
1816 exit_must_be_taken
, &bnds
);
1820 ret
= number_of_iterations_lt (loop
, type
, iv0
, iv1
, niter
,
1821 exit_must_be_taken
, &bnds
);
1825 ret
= number_of_iterations_le (loop
, type
, iv0
, iv1
, niter
,
1826 exit_must_be_taken
, &bnds
);
1833 mpz_clear (bnds
.up
);
1834 mpz_clear (bnds
.below
);
1836 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1840 fprintf (dump_file
, " result:\n");
1841 if (!integer_nonzerop (niter
->assumptions
))
1843 fprintf (dump_file
, " under assumptions ");
1844 print_generic_expr (dump_file
, niter
->assumptions
, TDF_SLIM
);
1845 fprintf (dump_file
, "\n");
1848 if (!integer_zerop (niter
->may_be_zero
))
1850 fprintf (dump_file
, " zero if ");
1851 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
1852 fprintf (dump_file
, "\n");
1855 fprintf (dump_file
, " # of iterations ");
1856 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
1857 fprintf (dump_file
, ", bounded by ");
1858 print_decu (niter
->max
, dump_file
);
1859 fprintf (dump_file
, "\n");
1862 fprintf (dump_file
, " failed\n\n");
1867 /* Substitute NEW for OLD in EXPR and fold the result. */
1870 simplify_replace_tree (tree expr
, tree old
, tree new_tree
)
1873 tree ret
= NULL_TREE
, e
, se
;
1878 /* Do not bother to replace constants. */
1879 if (CONSTANT_CLASS_P (old
))
1883 || operand_equal_p (expr
, old
, 0))
1884 return unshare_expr (new_tree
);
1889 n
= TREE_OPERAND_LENGTH (expr
);
1890 for (i
= 0; i
< n
; i
++)
1892 e
= TREE_OPERAND (expr
, i
);
1893 se
= simplify_replace_tree (e
, old
, new_tree
);
1898 ret
= copy_node (expr
);
1900 TREE_OPERAND (ret
, i
) = se
;
1903 return (ret
? fold (ret
) : expr
);
1906 /* Expand definitions of ssa names in EXPR as long as they are simple
1907 enough, and return the new expression. If STOP is specified, stop
1908 expanding if EXPR equals to it. */
1911 expand_simple_operations (tree expr
, tree stop
)
1914 tree ret
= NULL_TREE
, e
, ee
, e1
;
1915 enum tree_code code
;
1918 if (expr
== NULL_TREE
)
1921 if (is_gimple_min_invariant (expr
))
1924 code
= TREE_CODE (expr
);
1925 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
1927 n
= TREE_OPERAND_LENGTH (expr
);
1928 for (i
= 0; i
< n
; i
++)
1930 e
= TREE_OPERAND (expr
, i
);
1931 ee
= expand_simple_operations (e
, stop
);
1936 ret
= copy_node (expr
);
1938 TREE_OPERAND (ret
, i
) = ee
;
1944 fold_defer_overflow_warnings ();
1946 fold_undefer_and_ignore_overflow_warnings ();
1950 /* Stop if it's not ssa name or the one we don't want to expand. */
1951 if (TREE_CODE (expr
) != SSA_NAME
|| expr
== stop
)
1954 stmt
= SSA_NAME_DEF_STMT (expr
);
1955 if (gimple_code (stmt
) == GIMPLE_PHI
)
1957 basic_block src
, dest
;
1959 if (gimple_phi_num_args (stmt
) != 1)
1961 e
= PHI_ARG_DEF (stmt
, 0);
1963 /* Avoid propagating through loop exit phi nodes, which
1964 could break loop-closed SSA form restrictions. */
1965 dest
= gimple_bb (stmt
);
1966 src
= single_pred (dest
);
1967 if (TREE_CODE (e
) == SSA_NAME
1968 && src
->loop_father
!= dest
->loop_father
)
1971 return expand_simple_operations (e
, stop
);
1973 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1976 /* Avoid expanding to expressions that contain SSA names that need
1977 to take part in abnormal coalescing. */
1979 FOR_EACH_SSA_TREE_OPERAND (e
, stmt
, iter
, SSA_OP_USE
)
1980 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (e
))
1983 e
= gimple_assign_rhs1 (stmt
);
1984 code
= gimple_assign_rhs_code (stmt
);
1985 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
1987 if (is_gimple_min_invariant (e
))
1990 if (code
== SSA_NAME
)
1991 return expand_simple_operations (e
, stop
);
1992 else if (code
== ADDR_EXPR
)
1995 tree base
= get_addr_base_and_unit_offset (TREE_OPERAND (e
, 0),
1998 && TREE_CODE (base
) == MEM_REF
)
2000 ee
= expand_simple_operations (TREE_OPERAND (base
, 0), stop
);
2001 return fold_build2 (POINTER_PLUS_EXPR
, TREE_TYPE (expr
), ee
,
2002 wide_int_to_tree (sizetype
,
2003 mem_ref_offset (base
)
2014 /* Casts are simple. */
2015 ee
= expand_simple_operations (e
, stop
);
2016 return fold_build1 (code
, TREE_TYPE (expr
), ee
);
2020 if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (expr
))
2021 && TYPE_OVERFLOW_TRAPS (TREE_TYPE (expr
)))
2024 case POINTER_PLUS_EXPR
:
2025 /* And increments and decrements by a constant are simple. */
2026 e1
= gimple_assign_rhs2 (stmt
);
2027 if (!is_gimple_min_invariant (e1
))
2030 ee
= expand_simple_operations (e
, stop
);
2031 return fold_build2 (code
, TREE_TYPE (expr
), ee
, e1
);
2038 /* Tries to simplify EXPR using the condition COND. Returns the simplified
2039 expression (or EXPR unchanged, if no simplification was possible). */
2042 tree_simplify_using_condition_1 (tree cond
, tree expr
)
2045 tree e
, e0
, e1
, e2
, notcond
;
2046 enum tree_code code
= TREE_CODE (expr
);
2048 if (code
== INTEGER_CST
)
2051 if (code
== TRUTH_OR_EXPR
2052 || code
== TRUTH_AND_EXPR
2053 || code
== COND_EXPR
)
2057 e0
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 0));
2058 if (TREE_OPERAND (expr
, 0) != e0
)
2061 e1
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 1));
2062 if (TREE_OPERAND (expr
, 1) != e1
)
2065 if (code
== COND_EXPR
)
2067 e2
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 2));
2068 if (TREE_OPERAND (expr
, 2) != e2
)
2076 if (code
== COND_EXPR
)
2077 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
2079 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
2085 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
2086 propagation, and vice versa. Fold does not handle this, since it is
2087 considered too expensive. */
2088 if (TREE_CODE (cond
) == EQ_EXPR
)
2090 e0
= TREE_OPERAND (cond
, 0);
2091 e1
= TREE_OPERAND (cond
, 1);
2093 /* We know that e0 == e1. Check whether we cannot simplify expr
2095 e
= simplify_replace_tree (expr
, e0
, e1
);
2096 if (integer_zerop (e
) || integer_nonzerop (e
))
2099 e
= simplify_replace_tree (expr
, e1
, e0
);
2100 if (integer_zerop (e
) || integer_nonzerop (e
))
2103 if (TREE_CODE (expr
) == EQ_EXPR
)
2105 e0
= TREE_OPERAND (expr
, 0);
2106 e1
= TREE_OPERAND (expr
, 1);
2108 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
2109 e
= simplify_replace_tree (cond
, e0
, e1
);
2110 if (integer_zerop (e
))
2112 e
= simplify_replace_tree (cond
, e1
, e0
);
2113 if (integer_zerop (e
))
2116 if (TREE_CODE (expr
) == NE_EXPR
)
2118 e0
= TREE_OPERAND (expr
, 0);
2119 e1
= TREE_OPERAND (expr
, 1);
2121 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
2122 e
= simplify_replace_tree (cond
, e0
, e1
);
2123 if (integer_zerop (e
))
2124 return boolean_true_node
;
2125 e
= simplify_replace_tree (cond
, e1
, e0
);
2126 if (integer_zerop (e
))
2127 return boolean_true_node
;
2130 /* Check whether COND ==> EXPR. */
2131 notcond
= invert_truthvalue (cond
);
2132 e
= fold_binary (TRUTH_OR_EXPR
, boolean_type_node
, notcond
, expr
);
2133 if (e
&& integer_nonzerop (e
))
2136 /* Check whether COND ==> not EXPR. */
2137 e
= fold_binary (TRUTH_AND_EXPR
, boolean_type_node
, cond
, expr
);
2138 if (e
&& integer_zerop (e
))
2144 /* Tries to simplify EXPR using the condition COND. Returns the simplified
2145 expression (or EXPR unchanged, if no simplification was possible).
2146 Wrapper around tree_simplify_using_condition_1 that ensures that chains
2147 of simple operations in definitions of ssa names in COND are expanded,
2148 so that things like casts or incrementing the value of the bound before
2149 the loop do not cause us to fail. */
2152 tree_simplify_using_condition (tree cond
, tree expr
)
2154 cond
= expand_simple_operations (cond
);
2156 return tree_simplify_using_condition_1 (cond
, expr
);
2159 /* Tries to simplify EXPR using the conditions on entry to LOOP.
2160 Returns the simplified expression (or EXPR unchanged, if no
2161 simplification was possible). */
2164 simplify_using_initial_conditions (struct loop
*loop
, tree expr
)
2169 tree cond
, expanded
, backup
;
2172 if (TREE_CODE (expr
) == INTEGER_CST
)
2175 backup
= expanded
= expand_simple_operations (expr
);
2177 /* Limit walking the dominators to avoid quadraticness in
2178 the number of BBs times the number of loops in degenerate
2180 for (bb
= loop
->header
;
2181 bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && cnt
< MAX_DOMINATORS_TO_WALK
;
2182 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
2184 if (!single_pred_p (bb
))
2186 e
= single_pred_edge (bb
);
2188 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
2191 stmt
= last_stmt (e
->src
);
2192 cond
= fold_build2 (gimple_cond_code (stmt
),
2194 gimple_cond_lhs (stmt
),
2195 gimple_cond_rhs (stmt
));
2196 if (e
->flags
& EDGE_FALSE_VALUE
)
2197 cond
= invert_truthvalue (cond
);
2198 expanded
= tree_simplify_using_condition (cond
, expanded
);
2199 /* Break if EXPR is simplified to const values. */
2201 && (integer_zerop (expanded
) || integer_nonzerop (expanded
)))
2207 /* Return the original expression if no simplification is done. */
2208 return operand_equal_p (backup
, expanded
, 0) ? expr
: expanded
;
2211 /* Tries to simplify EXPR using the evolutions of the loop invariants
2212 in the superloops of LOOP. Returns the simplified expression
2213 (or EXPR unchanged, if no simplification was possible). */
2216 simplify_using_outer_evolutions (struct loop
*loop
, tree expr
)
2218 enum tree_code code
= TREE_CODE (expr
);
2222 if (is_gimple_min_invariant (expr
))
2225 if (code
== TRUTH_OR_EXPR
2226 || code
== TRUTH_AND_EXPR
2227 || code
== COND_EXPR
)
2231 e0
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 0));
2232 if (TREE_OPERAND (expr
, 0) != e0
)
2235 e1
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 1));
2236 if (TREE_OPERAND (expr
, 1) != e1
)
2239 if (code
== COND_EXPR
)
2241 e2
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 2));
2242 if (TREE_OPERAND (expr
, 2) != e2
)
2250 if (code
== COND_EXPR
)
2251 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
2253 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
2259 e
= instantiate_parameters (loop
, expr
);
2260 if (is_gimple_min_invariant (e
))
2266 /* Returns true if EXIT is the only possible exit from LOOP. */
2269 loop_only_exit_p (const struct loop
*loop
, const_edge exit
)
2272 gimple_stmt_iterator bsi
;
2275 if (exit
!= single_exit (loop
))
2278 body
= get_loop_body (loop
);
2279 for (i
= 0; i
< loop
->num_nodes
; i
++)
2281 for (bsi
= gsi_start_bb (body
[i
]); !gsi_end_p (bsi
); gsi_next (&bsi
))
2282 if (stmt_can_terminate_bb_p (gsi_stmt (bsi
)))
2293 /* Stores description of number of iterations of LOOP derived from
2294 EXIT (an exit edge of the LOOP) in NITER. Returns true if some useful
2295 information could be derived (and fields of NITER have meaning described
2296 in comments at struct tree_niter_desc declaration), false otherwise.
2297 When EVERY_ITERATION is true, only tests that are known to be executed
2298 every iteration are considered (i.e. only test that alone bounds the loop).
2299 If AT_STMT is not NULL, this function stores LOOP's condition statement in
2300 it when returning true. */
2303 number_of_iterations_exit_assumptions (struct loop
*loop
, edge exit
,
2304 struct tree_niter_desc
*niter
,
2305 gcond
**at_stmt
, bool every_iteration
)
2311 enum tree_code code
;
2315 /* Nothing to analyze if the loop is known to be infinite. */
2316 if (loop_constraint_set_p (loop
, LOOP_C_INFINITE
))
2319 safe
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit
->src
);
2321 if (every_iteration
&& !safe
)
2324 niter
->assumptions
= boolean_false_node
;
2325 niter
->control
.base
= NULL_TREE
;
2326 niter
->control
.step
= NULL_TREE
;
2327 niter
->control
.no_overflow
= false;
2328 last
= last_stmt (exit
->src
);
2331 stmt
= dyn_cast
<gcond
*> (last
);
2335 /* We want the condition for staying inside loop. */
2336 code
= gimple_cond_code (stmt
);
2337 if (exit
->flags
& EDGE_TRUE_VALUE
)
2338 code
= invert_tree_comparison (code
, false);
2353 op0
= gimple_cond_lhs (stmt
);
2354 op1
= gimple_cond_rhs (stmt
);
2355 type
= TREE_TYPE (op0
);
2357 if (TREE_CODE (type
) != INTEGER_TYPE
2358 && !POINTER_TYPE_P (type
))
2361 tree iv0_niters
= NULL_TREE
;
2362 if (!simple_iv_with_niters (loop
, loop_containing_stmt (stmt
),
2363 op0
, &iv0
, safe
? &iv0_niters
: NULL
, false))
2364 return number_of_iterations_popcount (loop
, exit
, code
, niter
);
2365 tree iv1_niters
= NULL_TREE
;
2366 if (!simple_iv_with_niters (loop
, loop_containing_stmt (stmt
),
2367 op1
, &iv1
, safe
? &iv1_niters
: NULL
, false))
2369 /* Give up on complicated case. */
2370 if (iv0_niters
&& iv1_niters
)
2373 /* We don't want to see undefined signed overflow warnings while
2374 computing the number of iterations. */
2375 fold_defer_overflow_warnings ();
2377 iv0
.base
= expand_simple_operations (iv0
.base
);
2378 iv1
.base
= expand_simple_operations (iv1
.base
);
2379 if (!number_of_iterations_cond (loop
, type
, &iv0
, code
, &iv1
, niter
,
2380 loop_only_exit_p (loop
, exit
), safe
))
2382 fold_undefer_and_ignore_overflow_warnings ();
2386 /* Incorporate additional assumption implied by control iv. */
2387 tree iv_niters
= iv0_niters
? iv0_niters
: iv1_niters
;
2390 tree assumption
= fold_build2 (LE_EXPR
, boolean_type_node
, niter
->niter
,
2391 fold_convert (TREE_TYPE (niter
->niter
),
2394 if (!integer_nonzerop (assumption
))
2395 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
2396 niter
->assumptions
, assumption
);
2398 /* Refine upper bound if possible. */
2399 if (TREE_CODE (iv_niters
) == INTEGER_CST
2400 && niter
->max
> wi::to_widest (iv_niters
))
2401 niter
->max
= wi::to_widest (iv_niters
);
2404 /* There is no assumptions if the loop is known to be finite. */
2405 if (!integer_zerop (niter
->assumptions
)
2406 && loop_constraint_set_p (loop
, LOOP_C_FINITE
))
2407 niter
->assumptions
= boolean_true_node
;
2411 niter
->assumptions
= simplify_using_outer_evolutions (loop
,
2412 niter
->assumptions
);
2413 niter
->may_be_zero
= simplify_using_outer_evolutions (loop
,
2414 niter
->may_be_zero
);
2415 niter
->niter
= simplify_using_outer_evolutions (loop
, niter
->niter
);
2419 = simplify_using_initial_conditions (loop
,
2420 niter
->assumptions
);
2422 = simplify_using_initial_conditions (loop
,
2423 niter
->may_be_zero
);
2425 fold_undefer_and_ignore_overflow_warnings ();
2427 /* If NITER has simplified into a constant, update MAX. */
2428 if (TREE_CODE (niter
->niter
) == INTEGER_CST
)
2429 niter
->max
= wi::to_widest (niter
->niter
);
2434 return (!integer_zerop (niter
->assumptions
));
2438 /* Utility function to check if OP is defined by a stmt
2439 that is a val - 1. */
2442 ssa_defined_by_minus_one_stmt_p (tree op
, tree val
)
2445 return (TREE_CODE (op
) == SSA_NAME
2446 && (stmt
= SSA_NAME_DEF_STMT (op
))
2447 && is_gimple_assign (stmt
)
2448 && (gimple_assign_rhs_code (stmt
) == PLUS_EXPR
)
2449 && val
== gimple_assign_rhs1 (stmt
)
2450 && integer_minus_onep (gimple_assign_rhs2 (stmt
)));
2454 /* See if LOOP is a popcout implementation, determine NITER for the loop
2465 b_11 = PHI <b_5(D)(2), b_6(3)>
2473 OR we match copy-header version:
2480 b_11 = PHI <b_5(2), b_6(3)>
2490 If popcount pattern, update NITER accordingly.
2491 i.e., set NITER to __builtin_popcount (b)
2492 return true if we did, false otherwise.
2497 number_of_iterations_popcount (loop_p loop
, edge exit
,
2498 enum tree_code code
,
2499 struct tree_niter_desc
*niter
)
2505 tree fn
= NULL_TREE
;
2507 /* Check loop terminating branch is like
2509 gimple
*stmt
= last_stmt (exit
->src
);
2511 || gimple_code (stmt
) != GIMPLE_COND
2513 || !integer_zerop (gimple_cond_rhs (stmt
))
2514 || TREE_CODE (gimple_cond_lhs (stmt
)) != SSA_NAME
)
2517 gimple
*and_stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt
));
2519 /* Depending on copy-header is performed, feeding PHI stmts might be in
2520 the loop header or loop latch, handle this. */
2521 if (gimple_code (and_stmt
) == GIMPLE_PHI
2522 && gimple_bb (and_stmt
) == loop
->header
2523 && gimple_phi_num_args (and_stmt
) == 2
2524 && (TREE_CODE (gimple_phi_arg_def (and_stmt
,
2525 loop_latch_edge (loop
)->dest_idx
))
2528 /* SSA used in exit condition is defined by PHI stmt
2529 b_11 = PHI <b_5(D)(2), b_6(3)>
2530 from the PHI stmt, get the and_stmt
2532 tree t
= gimple_phi_arg_def (and_stmt
, loop_latch_edge (loop
)->dest_idx
);
2533 and_stmt
= SSA_NAME_DEF_STMT (t
);
2537 /* Make sure it is indeed an and stmt (b_6 = _1 & b_11). */
2538 if (!is_gimple_assign (and_stmt
)
2539 || gimple_assign_rhs_code (and_stmt
) != BIT_AND_EXPR
)
2542 tree b_11
= gimple_assign_rhs1 (and_stmt
);
2543 tree _1
= gimple_assign_rhs2 (and_stmt
);
2545 /* Check that _1 is defined by _b11 + -1 (_1 = b_11 + -1).
2546 Also make sure that b_11 is the same in and_stmt and _1 defining stmt.
2547 Also canonicalize if _1 and _b11 are revrsed. */
2548 if (ssa_defined_by_minus_one_stmt_p (b_11
, _1
))
2549 std::swap (b_11
, _1
);
2550 else if (ssa_defined_by_minus_one_stmt_p (_1
, b_11
))
2554 /* Check the recurrence:
2555 ... = PHI <b_5(2), b_6(3)>. */
2556 gimple
*phi
= SSA_NAME_DEF_STMT (b_11
);
2557 if (gimple_code (phi
) != GIMPLE_PHI
2558 || (gimple_assign_lhs (and_stmt
)
2559 != gimple_phi_arg_def (phi
, loop_latch_edge (loop
)->dest_idx
)))
2562 /* We found a match. Get the corresponding popcount builtin. */
2563 tree src
= gimple_phi_arg_def (phi
, loop_preheader_edge (loop
)->dest_idx
);
2564 if (TYPE_PRECISION (TREE_TYPE (src
)) == TYPE_PRECISION (integer_type_node
))
2565 fn
= builtin_decl_implicit (BUILT_IN_POPCOUNT
);
2566 else if (TYPE_PRECISION (TREE_TYPE (src
)) == TYPE_PRECISION
2567 (long_integer_type_node
))
2568 fn
= builtin_decl_implicit (BUILT_IN_POPCOUNTL
);
2569 else if (TYPE_PRECISION (TREE_TYPE (src
)) == TYPE_PRECISION
2570 (long_long_integer_type_node
))
2571 fn
= builtin_decl_implicit (BUILT_IN_POPCOUNTLL
);
2573 /* ??? Support promoting char/short to int. */
2577 /* Update NITER params accordingly */
2578 tree utype
= unsigned_type_for (TREE_TYPE (src
));
2579 src
= fold_convert (utype
, src
);
2580 tree call
= fold_convert (utype
, build_call_expr (fn
, 1, src
));
2582 iter
= fold_build2 (MINUS_EXPR
, utype
,
2584 build_int_cst (utype
, 1));
2588 if (TREE_CODE (call
) == INTEGER_CST
)
2589 max
= tree_to_uhwi (call
);
2592 max
= TYPE_PRECISION (TREE_TYPE (src
));
2597 niter
->niter
= iter
;
2598 niter
->assumptions
= boolean_true_node
;
2600 niter
->may_be_zero
= fold_build2 (EQ_EXPR
, boolean_type_node
, src
,
2604 niter
->may_be_zero
= boolean_false_node
;
2607 niter
->bound
= NULL_TREE
;
2608 niter
->cmp
= ERROR_MARK
;
2613 /* Like number_of_iterations_exit_assumptions, but return TRUE only if
2614 the niter information holds unconditionally. */
2617 number_of_iterations_exit (struct loop
*loop
, edge exit
,
2618 struct tree_niter_desc
*niter
,
2619 bool warn
, bool every_iteration
)
2622 if (!number_of_iterations_exit_assumptions (loop
, exit
, niter
,
2623 &stmt
, every_iteration
))
2626 if (integer_nonzerop (niter
->assumptions
))
2630 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, stmt
,
2631 "missed loop optimization: niters analysis ends up "
2632 "with assumptions.\n");
2637 /* Try to determine the number of iterations of LOOP. If we succeed,
2638 expression giving number of iterations is returned and *EXIT is
2639 set to the edge from that the information is obtained. Otherwise
2640 chrec_dont_know is returned. */
2643 find_loop_niter (struct loop
*loop
, edge
*exit
)
2646 vec
<edge
> exits
= get_loop_exit_edges (loop
);
2648 tree niter
= NULL_TREE
, aniter
;
2649 struct tree_niter_desc desc
;
2652 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2654 if (!number_of_iterations_exit (loop
, ex
, &desc
, false))
2657 if (integer_nonzerop (desc
.may_be_zero
))
2659 /* We exit in the first iteration through this exit.
2660 We won't find anything better. */
2661 niter
= build_int_cst (unsigned_type_node
, 0);
2666 if (!integer_zerop (desc
.may_be_zero
))
2669 aniter
= desc
.niter
;
2673 /* Nothing recorded yet. */
2679 /* Prefer constants, the lower the better. */
2680 if (TREE_CODE (aniter
) != INTEGER_CST
)
2683 if (TREE_CODE (niter
) != INTEGER_CST
)
2690 if (tree_int_cst_lt (aniter
, niter
))
2699 return niter
? niter
: chrec_dont_know
;
2702 /* Return true if loop is known to have bounded number of iterations. */
2705 finite_loop_p (struct loop
*loop
)
2710 flags
= flags_from_decl_or_type (current_function_decl
);
2711 if ((flags
& (ECF_CONST
|ECF_PURE
)) && !(flags
& ECF_LOOPING_CONST_OR_PURE
))
2713 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2714 fprintf (dump_file
, "Found loop %i to be finite: it is within pure or const function.\n",
2719 if (loop
->any_upper_bound
2720 || max_loop_iterations (loop
, &nit
))
2722 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2723 fprintf (dump_file
, "Found loop %i to be finite: upper bound found.\n",
2732 Analysis of a number of iterations of a loop by a brute-force evaluation.
2736 /* Bound on the number of iterations we try to evaluate. */
2738 #define MAX_ITERATIONS_TO_TRACK \
2739 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
2741 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
2742 result by a chain of operations such that all but exactly one of their
2743 operands are constants. */
2746 chain_of_csts_start (struct loop
*loop
, tree x
)
2748 gimple
*stmt
= SSA_NAME_DEF_STMT (x
);
2750 basic_block bb
= gimple_bb (stmt
);
2751 enum tree_code code
;
2754 || !flow_bb_inside_loop_p (loop
, bb
))
2757 if (gimple_code (stmt
) == GIMPLE_PHI
)
2759 if (bb
== loop
->header
)
2760 return as_a
<gphi
*> (stmt
);
2765 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2766 || gimple_assign_rhs_class (stmt
) == GIMPLE_TERNARY_RHS
)
2769 code
= gimple_assign_rhs_code (stmt
);
2770 if (gimple_references_memory_p (stmt
)
2771 || TREE_CODE_CLASS (code
) == tcc_reference
2772 || (code
== ADDR_EXPR
2773 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
2776 use
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
2777 if (use
== NULL_TREE
)
2780 return chain_of_csts_start (loop
, use
);
2783 /* Determines whether the expression X is derived from a result of a phi node
2784 in header of LOOP such that
2786 * the derivation of X consists only from operations with constants
2787 * the initial value of the phi node is constant
2788 * the value of the phi node in the next iteration can be derived from the
2789 value in the current iteration by a chain of operations with constants,
2790 or is also a constant
2792 If such phi node exists, it is returned, otherwise NULL is returned. */
2795 get_base_for (struct loop
*loop
, tree x
)
2800 if (is_gimple_min_invariant (x
))
2803 phi
= chain_of_csts_start (loop
, x
);
2807 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2808 next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2810 if (!is_gimple_min_invariant (init
))
2813 if (TREE_CODE (next
) == SSA_NAME
2814 && chain_of_csts_start (loop
, next
) != phi
)
2820 /* Given an expression X, then
2822 * if X is NULL_TREE, we return the constant BASE.
2823 * if X is a constant, we return the constant X.
2824 * otherwise X is a SSA name, whose value in the considered loop is derived
2825 by a chain of operations with constant from a result of a phi node in
2826 the header of the loop. Then we return value of X when the value of the
2827 result of this phi node is given by the constant BASE. */
2830 get_val_for (tree x
, tree base
)
2834 gcc_checking_assert (is_gimple_min_invariant (base
));
2838 else if (is_gimple_min_invariant (x
))
2841 stmt
= SSA_NAME_DEF_STMT (x
);
2842 if (gimple_code (stmt
) == GIMPLE_PHI
)
2845 gcc_checking_assert (is_gimple_assign (stmt
));
2847 /* STMT must be either an assignment of a single SSA name or an
2848 expression involving an SSA name and a constant. Try to fold that
2849 expression using the value for the SSA name. */
2850 if (gimple_assign_ssa_name_copy_p (stmt
))
2851 return get_val_for (gimple_assign_rhs1 (stmt
), base
);
2852 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_UNARY_RHS
2853 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
2854 return fold_build1 (gimple_assign_rhs_code (stmt
),
2855 gimple_expr_type (stmt
),
2856 get_val_for (gimple_assign_rhs1 (stmt
), base
));
2857 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_BINARY_RHS
)
2859 tree rhs1
= gimple_assign_rhs1 (stmt
);
2860 tree rhs2
= gimple_assign_rhs2 (stmt
);
2861 if (TREE_CODE (rhs1
) == SSA_NAME
)
2862 rhs1
= get_val_for (rhs1
, base
);
2863 else if (TREE_CODE (rhs2
) == SSA_NAME
)
2864 rhs2
= get_val_for (rhs2
, base
);
2867 return fold_build2 (gimple_assign_rhs_code (stmt
),
2868 gimple_expr_type (stmt
), rhs1
, rhs2
);
2875 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2876 by brute force -- i.e. by determining the value of the operands of the
2877 condition at EXIT in first few iterations of the loop (assuming that
2878 these values are constant) and determining the first one in that the
2879 condition is not satisfied. Returns the constant giving the number
2880 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
2883 loop_niter_by_eval (struct loop
*loop
, edge exit
)
2886 tree op
[2], val
[2], next
[2], aval
[2];
2892 cond
= last_stmt (exit
->src
);
2893 if (!cond
|| gimple_code (cond
) != GIMPLE_COND
)
2894 return chrec_dont_know
;
2896 cmp
= gimple_cond_code (cond
);
2897 if (exit
->flags
& EDGE_TRUE_VALUE
)
2898 cmp
= invert_tree_comparison (cmp
, false);
2908 op
[0] = gimple_cond_lhs (cond
);
2909 op
[1] = gimple_cond_rhs (cond
);
2913 return chrec_dont_know
;
2916 for (j
= 0; j
< 2; j
++)
2918 if (is_gimple_min_invariant (op
[j
]))
2921 next
[j
] = NULL_TREE
;
2926 phi
= get_base_for (loop
, op
[j
]);
2928 return chrec_dont_know
;
2929 val
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2930 next
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2934 /* Don't issue signed overflow warnings. */
2935 fold_defer_overflow_warnings ();
2937 for (i
= 0; i
< MAX_ITERATIONS_TO_TRACK
; i
++)
2939 for (j
= 0; j
< 2; j
++)
2940 aval
[j
] = get_val_for (op
[j
], val
[j
]);
2942 acnd
= fold_binary (cmp
, boolean_type_node
, aval
[0], aval
[1]);
2943 if (acnd
&& integer_zerop (acnd
))
2945 fold_undefer_and_ignore_overflow_warnings ();
2946 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2948 "Proved that loop %d iterates %d times using brute force.\n",
2950 return build_int_cst (unsigned_type_node
, i
);
2953 for (j
= 0; j
< 2; j
++)
2956 val
[j
] = get_val_for (next
[j
], val
[j
]);
2957 if (!is_gimple_min_invariant (val
[j
]))
2959 fold_undefer_and_ignore_overflow_warnings ();
2960 return chrec_dont_know
;
2964 /* If the next iteration would use the same base values
2965 as the current one, there is no point looping further,
2966 all following iterations will be the same as this one. */
2967 if (val
[0] == aval
[0] && val
[1] == aval
[1])
2971 fold_undefer_and_ignore_overflow_warnings ();
2973 return chrec_dont_know
;
2976 /* Finds the exit of the LOOP by that the loop exits after a constant
2977 number of iterations and stores the exit edge to *EXIT. The constant
2978 giving the number of iterations of LOOP is returned. The number of
2979 iterations is determined using loop_niter_by_eval (i.e. by brute force
2980 evaluation). If we are unable to find the exit for that loop_niter_by_eval
2981 determines the number of iterations, chrec_dont_know is returned. */
2984 find_loop_niter_by_eval (struct loop
*loop
, edge
*exit
)
2987 vec
<edge
> exits
= get_loop_exit_edges (loop
);
2989 tree niter
= NULL_TREE
, aniter
;
2993 /* Loops with multiple exits are expensive to handle and less important. */
2994 if (!flag_expensive_optimizations
2995 && exits
.length () > 1)
2998 return chrec_dont_know
;
3001 FOR_EACH_VEC_ELT (exits
, i
, ex
)
3003 if (!just_once_each_iteration_p (loop
, ex
->src
))
3006 aniter
= loop_niter_by_eval (loop
, ex
);
3007 if (chrec_contains_undetermined (aniter
))
3011 && !tree_int_cst_lt (aniter
, niter
))
3019 return niter
? niter
: chrec_dont_know
;
3024 Analysis of upper bounds on number of iterations of a loop.
3028 static widest_int
derive_constant_upper_bound_ops (tree
, tree
,
3029 enum tree_code
, tree
);
3031 /* Returns a constant upper bound on the value of the right-hand side of
3032 an assignment statement STMT. */
3035 derive_constant_upper_bound_assign (gimple
*stmt
)
3037 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3038 tree op0
= gimple_assign_rhs1 (stmt
);
3039 tree op1
= gimple_assign_rhs2 (stmt
);
3041 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt
)),
3045 /* Returns a constant upper bound on the value of expression VAL. VAL
3046 is considered to be unsigned. If its type is signed, its value must
3050 derive_constant_upper_bound (tree val
)
3052 enum tree_code code
;
3055 extract_ops_from_tree (val
, &code
, &op0
, &op1
, &op2
);
3056 return derive_constant_upper_bound_ops (TREE_TYPE (val
), op0
, code
, op1
);
3059 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
3060 whose type is TYPE. The expression is considered to be unsigned. If
3061 its type is signed, its value must be nonnegative. */
3064 derive_constant_upper_bound_ops (tree type
, tree op0
,
3065 enum tree_code code
, tree op1
)
3068 widest_int bnd
, max
, cst
;
3071 if (INTEGRAL_TYPE_P (type
))
3072 maxt
= TYPE_MAX_VALUE (type
);
3074 maxt
= upper_bound_in_type (type
, type
);
3076 max
= wi::to_widest (maxt
);
3081 return wi::to_widest (op0
);
3084 subtype
= TREE_TYPE (op0
);
3085 if (!TYPE_UNSIGNED (subtype
)
3086 /* If TYPE is also signed, the fact that VAL is nonnegative implies
3087 that OP0 is nonnegative. */
3088 && TYPE_UNSIGNED (type
)
3089 && !tree_expr_nonnegative_p (op0
))
3091 /* If we cannot prove that the casted expression is nonnegative,
3092 we cannot establish more useful upper bound than the precision
3093 of the type gives us. */
3097 /* We now know that op0 is an nonnegative value. Try deriving an upper
3099 bnd
= derive_constant_upper_bound (op0
);
3101 /* If the bound does not fit in TYPE, max. value of TYPE could be
3103 if (wi::ltu_p (max
, bnd
))
3109 case POINTER_PLUS_EXPR
:
3111 if (TREE_CODE (op1
) != INTEGER_CST
3112 || !tree_expr_nonnegative_p (op0
))
3115 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
3116 choose the most logical way how to treat this constant regardless
3117 of the signedness of the type. */
3118 cst
= wi::sext (wi::to_widest (op1
), TYPE_PRECISION (type
));
3119 if (code
!= MINUS_EXPR
)
3122 bnd
= derive_constant_upper_bound (op0
);
3124 if (wi::neg_p (cst
))
3127 /* Avoid CST == 0x80000... */
3128 if (wi::neg_p (cst
))
3131 /* OP0 + CST. We need to check that
3132 BND <= MAX (type) - CST. */
3134 widest_int mmax
= max
- cst
;
3135 if (wi::leu_p (bnd
, mmax
))
3142 /* OP0 - CST, where CST >= 0.
3144 If TYPE is signed, we have already verified that OP0 >= 0, and we
3145 know that the result is nonnegative. This implies that
3148 If TYPE is unsigned, we must additionally know that OP0 >= CST,
3149 otherwise the operation underflows.
3152 /* This should only happen if the type is unsigned; however, for
3153 buggy programs that use overflowing signed arithmetics even with
3154 -fno-wrapv, this condition may also be true for signed values. */
3155 if (wi::ltu_p (bnd
, cst
))
3158 if (TYPE_UNSIGNED (type
))
3160 tree tem
= fold_binary (GE_EXPR
, boolean_type_node
, op0
,
3161 wide_int_to_tree (type
, cst
));
3162 if (!tem
|| integer_nonzerop (tem
))
3171 case FLOOR_DIV_EXPR
:
3172 case EXACT_DIV_EXPR
:
3173 if (TREE_CODE (op1
) != INTEGER_CST
3174 || tree_int_cst_sign_bit (op1
))
3177 bnd
= derive_constant_upper_bound (op0
);
3178 return wi::udiv_floor (bnd
, wi::to_widest (op1
));
3181 if (TREE_CODE (op1
) != INTEGER_CST
3182 || tree_int_cst_sign_bit (op1
))
3184 return wi::to_widest (op1
);
3187 stmt
= SSA_NAME_DEF_STMT (op0
);
3188 if (gimple_code (stmt
) != GIMPLE_ASSIGN
3189 || gimple_assign_lhs (stmt
) != op0
)
3191 return derive_constant_upper_bound_assign (stmt
);
3198 /* Emit a -Waggressive-loop-optimizations warning if needed. */
3201 do_warn_aggressive_loop_optimizations (struct loop
*loop
,
3202 widest_int i_bound
, gimple
*stmt
)
3204 /* Don't warn if the loop doesn't have known constant bound. */
3205 if (!loop
->nb_iterations
3206 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
3207 || !warn_aggressive_loop_optimizations
3208 /* To avoid warning multiple times for the same loop,
3209 only start warning when we preserve loops. */
3210 || (cfun
->curr_properties
& PROP_loops
) == 0
3211 /* Only warn once per loop. */
3212 || loop
->warned_aggressive_loop_optimizations
3213 /* Only warn if undefined behavior gives us lower estimate than the
3214 known constant bound. */
3215 || wi::cmpu (i_bound
, wi::to_widest (loop
->nb_iterations
)) >= 0
3216 /* And undefined behavior happens unconditionally. */
3217 || !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (stmt
)))
3220 edge e
= single_exit (loop
);
3224 gimple
*estmt
= last_stmt (e
->src
);
3225 char buf
[WIDE_INT_PRINT_BUFFER_SIZE
];
3226 print_dec (i_bound
, buf
, TYPE_UNSIGNED (TREE_TYPE (loop
->nb_iterations
))
3227 ? UNSIGNED
: SIGNED
);
3228 if (warning_at (gimple_location (stmt
), OPT_Waggressive_loop_optimizations
,
3229 "iteration %s invokes undefined behavior", buf
))
3230 inform (gimple_location (estmt
), "within this loop");
3231 loop
->warned_aggressive_loop_optimizations
= true;
3234 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
3235 is true if the loop is exited immediately after STMT, and this exit
3236 is taken at last when the STMT is executed BOUND + 1 times.
3237 REALISTIC is true if BOUND is expected to be close to the real number
3238 of iterations. UPPER is true if we are sure the loop iterates at most
3239 BOUND times. I_BOUND is a widest_int upper estimate on BOUND. */
3242 record_estimate (struct loop
*loop
, tree bound
, const widest_int
&i_bound
,
3243 gimple
*at_stmt
, bool is_exit
, bool realistic
, bool upper
)
3247 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3249 fprintf (dump_file
, "Statement %s", is_exit
? "(exit)" : "");
3250 print_gimple_stmt (dump_file
, at_stmt
, 0, TDF_SLIM
);
3251 fprintf (dump_file
, " is %sexecuted at most ",
3252 upper
? "" : "probably ");
3253 print_generic_expr (dump_file
, bound
, TDF_SLIM
);
3254 fprintf (dump_file
, " (bounded by ");
3255 print_decu (i_bound
, dump_file
);
3256 fprintf (dump_file
, ") + 1 times in loop %d.\n", loop
->num
);
3259 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
3260 real number of iterations. */
3261 if (TREE_CODE (bound
) != INTEGER_CST
)
3264 gcc_checking_assert (i_bound
== wi::to_widest (bound
));
3266 /* If we have a guaranteed upper bound, record it in the appropriate
3267 list, unless this is an !is_exit bound (i.e. undefined behavior in
3268 at_stmt) in a loop with known constant number of iterations. */
3271 || loop
->nb_iterations
== NULL_TREE
3272 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
))
3274 struct nb_iter_bound
*elt
= ggc_alloc
<nb_iter_bound
> ();
3276 elt
->bound
= i_bound
;
3277 elt
->stmt
= at_stmt
;
3278 elt
->is_exit
= is_exit
;
3279 elt
->next
= loop
->bounds
;
3283 /* If statement is executed on every path to the loop latch, we can directly
3284 infer the upper bound on the # of iterations of the loop. */
3285 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (at_stmt
)))
3288 /* Update the number of iteration estimates according to the bound.
3289 If at_stmt is an exit then the loop latch is executed at most BOUND times,
3290 otherwise it can be executed BOUND + 1 times. We will lower the estimate
3291 later if such statement must be executed on last iteration */
3296 widest_int new_i_bound
= i_bound
+ delta
;
3298 /* If an overflow occurred, ignore the result. */
3299 if (wi::ltu_p (new_i_bound
, delta
))
3302 if (upper
&& !is_exit
)
3303 do_warn_aggressive_loop_optimizations (loop
, new_i_bound
, at_stmt
);
3304 record_niter_bound (loop
, new_i_bound
, realistic
, upper
);
3307 /* Records the control iv analyzed in NITER for LOOP if the iv is valid
3308 and doesn't overflow. */
3311 record_control_iv (struct loop
*loop
, struct tree_niter_desc
*niter
)
3313 struct control_iv
*iv
;
3315 if (!niter
->control
.base
|| !niter
->control
.step
)
3318 if (!integer_onep (niter
->assumptions
) || !niter
->control
.no_overflow
)
3321 iv
= ggc_alloc
<control_iv
> ();
3322 iv
->base
= niter
->control
.base
;
3323 iv
->step
= niter
->control
.step
;
3324 iv
->next
= loop
->control_ivs
;
3325 loop
->control_ivs
= iv
;
3330 /* This function returns TRUE if below conditions are satisfied:
3331 1) VAR is SSA variable.
3332 2) VAR is an IV:{base, step} in its defining loop.
3333 3) IV doesn't overflow.
3334 4) Both base and step are integer constants.
3335 5) Base is the MIN/MAX value depends on IS_MIN.
3336 Store value of base to INIT correspondingly. */
3339 get_cst_init_from_scev (tree var
, wide_int
*init
, bool is_min
)
3341 if (TREE_CODE (var
) != SSA_NAME
)
3344 gimple
*def_stmt
= SSA_NAME_DEF_STMT (var
);
3345 struct loop
*loop
= loop_containing_stmt (def_stmt
);
3351 if (!simple_iv (loop
, loop
, var
, &iv
, false))
3354 if (!iv
.no_overflow
)
3357 if (TREE_CODE (iv
.base
) != INTEGER_CST
|| TREE_CODE (iv
.step
) != INTEGER_CST
)
3360 if (is_min
== tree_int_cst_sign_bit (iv
.step
))
3363 *init
= wi::to_wide (iv
.base
);
3367 /* Record the estimate on number of iterations of LOOP based on the fact that
3368 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
3369 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
3370 estimated number of iterations is expected to be close to the real one.
3371 UPPER is true if we are sure the induction variable does not wrap. */
3374 record_nonwrapping_iv (struct loop
*loop
, tree base
, tree step
, gimple
*stmt
,
3375 tree low
, tree high
, bool realistic
, bool upper
)
3377 tree niter_bound
, extreme
, delta
;
3378 tree type
= TREE_TYPE (base
), unsigned_type
;
3379 tree orig_base
= base
;
3381 if (TREE_CODE (step
) != INTEGER_CST
|| integer_zerop (step
))
3384 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3386 fprintf (dump_file
, "Induction variable (");
3387 print_generic_expr (dump_file
, TREE_TYPE (base
), TDF_SLIM
);
3388 fprintf (dump_file
, ") ");
3389 print_generic_expr (dump_file
, base
, TDF_SLIM
);
3390 fprintf (dump_file
, " + ");
3391 print_generic_expr (dump_file
, step
, TDF_SLIM
);
3392 fprintf (dump_file
, " * iteration does not wrap in statement ");
3393 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3394 fprintf (dump_file
, " in loop %d.\n", loop
->num
);
3397 unsigned_type
= unsigned_type_for (type
);
3398 base
= fold_convert (unsigned_type
, base
);
3399 step
= fold_convert (unsigned_type
, step
);
3401 if (tree_int_cst_sign_bit (step
))
3404 extreme
= fold_convert (unsigned_type
, low
);
3405 if (TREE_CODE (orig_base
) == SSA_NAME
3406 && TREE_CODE (high
) == INTEGER_CST
3407 && INTEGRAL_TYPE_P (TREE_TYPE (orig_base
))
3408 && (get_range_info (orig_base
, &min
, &max
) == VR_RANGE
3409 || get_cst_init_from_scev (orig_base
, &max
, false))
3410 && wi::gts_p (wi::to_wide (high
), max
))
3411 base
= wide_int_to_tree (unsigned_type
, max
);
3412 else if (TREE_CODE (base
) != INTEGER_CST
3413 && dominated_by_p (CDI_DOMINATORS
,
3414 loop
->latch
, gimple_bb (stmt
)))
3415 base
= fold_convert (unsigned_type
, high
);
3416 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
3417 step
= fold_build1 (NEGATE_EXPR
, unsigned_type
, step
);
3422 extreme
= fold_convert (unsigned_type
, high
);
3423 if (TREE_CODE (orig_base
) == SSA_NAME
3424 && TREE_CODE (low
) == INTEGER_CST
3425 && INTEGRAL_TYPE_P (TREE_TYPE (orig_base
))
3426 && (get_range_info (orig_base
, &min
, &max
) == VR_RANGE
3427 || get_cst_init_from_scev (orig_base
, &min
, true))
3428 && wi::gts_p (min
, wi::to_wide (low
)))
3429 base
= wide_int_to_tree (unsigned_type
, min
);
3430 else if (TREE_CODE (base
) != INTEGER_CST
3431 && dominated_by_p (CDI_DOMINATORS
,
3432 loop
->latch
, gimple_bb (stmt
)))
3433 base
= fold_convert (unsigned_type
, low
);
3434 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
3437 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
3438 would get out of the range. */
3439 niter_bound
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step
);
3440 widest_int max
= derive_constant_upper_bound (niter_bound
);
3441 record_estimate (loop
, niter_bound
, max
, stmt
, false, realistic
, upper
);
3444 /* Determine information about number of iterations a LOOP from the index
3445 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
3446 guaranteed to be executed in every iteration of LOOP. Callback for
3456 idx_infer_loop_bounds (tree base
, tree
*idx
, void *dta
)
3458 struct ilb_data
*data
= (struct ilb_data
*) dta
;
3459 tree ev
, init
, step
;
3460 tree low
, high
, type
, next
;
3461 bool sign
, upper
= true, at_end
= false;
3462 struct loop
*loop
= data
->loop
;
3464 if (TREE_CODE (base
) != ARRAY_REF
)
3467 /* For arrays at the end of the structure, we are not guaranteed that they
3468 do not really extend over their declared size. However, for arrays of
3469 size greater than one, this is unlikely to be intended. */
3470 if (array_at_struct_end_p (base
))
3476 struct loop
*dloop
= loop_containing_stmt (data
->stmt
);
3480 ev
= analyze_scalar_evolution (dloop
, *idx
);
3481 ev
= instantiate_parameters (loop
, ev
);
3482 init
= initial_condition (ev
);
3483 step
= evolution_part_in_loop_num (ev
, loop
->num
);
3487 || TREE_CODE (step
) != INTEGER_CST
3488 || integer_zerop (step
)
3489 || tree_contains_chrecs (init
, NULL
)
3490 || chrec_contains_symbols_defined_in_loop (init
, loop
->num
))
3493 low
= array_ref_low_bound (base
);
3494 high
= array_ref_up_bound (base
);
3496 /* The case of nonconstant bounds could be handled, but it would be
3498 if (TREE_CODE (low
) != INTEGER_CST
3500 || TREE_CODE (high
) != INTEGER_CST
)
3502 sign
= tree_int_cst_sign_bit (step
);
3503 type
= TREE_TYPE (step
);
3505 /* The array of length 1 at the end of a structure most likely extends
3506 beyond its bounds. */
3508 && operand_equal_p (low
, high
, 0))
3511 /* In case the relevant bound of the array does not fit in type, or
3512 it does, but bound + step (in type) still belongs into the range of the
3513 array, the index may wrap and still stay within the range of the array
3514 (consider e.g. if the array is indexed by the full range of
3517 To make things simpler, we require both bounds to fit into type, although
3518 there are cases where this would not be strictly necessary. */
3519 if (!int_fits_type_p (high
, type
)
3520 || !int_fits_type_p (low
, type
))
3522 low
= fold_convert (type
, low
);
3523 high
= fold_convert (type
, high
);
3526 next
= fold_binary (PLUS_EXPR
, type
, low
, step
);
3528 next
= fold_binary (PLUS_EXPR
, type
, high
, step
);
3530 if (tree_int_cst_compare (low
, next
) <= 0
3531 && tree_int_cst_compare (next
, high
) <= 0)
3534 /* If access is not executed on every iteration, we must ensure that overlow
3535 may not make the access valid later. */
3536 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (data
->stmt
))
3537 && scev_probably_wraps_p (NULL_TREE
,
3538 initial_condition_in_loop_num (ev
, loop
->num
),
3539 step
, data
->stmt
, loop
, true))
3542 record_nonwrapping_iv (loop
, init
, step
, data
->stmt
, low
, high
, false, upper
);
3546 /* Determine information about number of iterations a LOOP from the bounds
3547 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
3548 STMT is guaranteed to be executed in every iteration of LOOP.*/
3551 infer_loop_bounds_from_ref (struct loop
*loop
, gimple
*stmt
, tree ref
)
3553 struct ilb_data data
;
3557 for_each_index (&ref
, idx_infer_loop_bounds
, &data
);
3560 /* Determine information about number of iterations of a LOOP from the way
3561 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
3562 executed in every iteration of LOOP. */
3565 infer_loop_bounds_from_array (struct loop
*loop
, gimple
*stmt
)
3567 if (is_gimple_assign (stmt
))
3569 tree op0
= gimple_assign_lhs (stmt
);
3570 tree op1
= gimple_assign_rhs1 (stmt
);
3572 /* For each memory access, analyze its access function
3573 and record a bound on the loop iteration domain. */
3574 if (REFERENCE_CLASS_P (op0
))
3575 infer_loop_bounds_from_ref (loop
, stmt
, op0
);
3577 if (REFERENCE_CLASS_P (op1
))
3578 infer_loop_bounds_from_ref (loop
, stmt
, op1
);
3580 else if (is_gimple_call (stmt
))
3583 unsigned i
, n
= gimple_call_num_args (stmt
);
3585 lhs
= gimple_call_lhs (stmt
);
3586 if (lhs
&& REFERENCE_CLASS_P (lhs
))
3587 infer_loop_bounds_from_ref (loop
, stmt
, lhs
);
3589 for (i
= 0; i
< n
; i
++)
3591 arg
= gimple_call_arg (stmt
, i
);
3592 if (REFERENCE_CLASS_P (arg
))
3593 infer_loop_bounds_from_ref (loop
, stmt
, arg
);
3598 /* Determine information about number of iterations of a LOOP from the fact
3599 that pointer arithmetics in STMT does not overflow. */
3602 infer_loop_bounds_from_pointer_arith (struct loop
*loop
, gimple
*stmt
)
3604 tree def
, base
, step
, scev
, type
, low
, high
;
3607 if (!is_gimple_assign (stmt
)
3608 || gimple_assign_rhs_code (stmt
) != POINTER_PLUS_EXPR
)
3611 def
= gimple_assign_lhs (stmt
);
3612 if (TREE_CODE (def
) != SSA_NAME
)
3615 type
= TREE_TYPE (def
);
3616 if (!nowrap_type_p (type
))
3619 ptr
= gimple_assign_rhs1 (stmt
);
3620 if (!expr_invariant_in_loop_p (loop
, ptr
))
3623 var
= gimple_assign_rhs2 (stmt
);
3624 if (TYPE_PRECISION (type
) != TYPE_PRECISION (TREE_TYPE (var
)))
3627 struct loop
*uloop
= loop_containing_stmt (stmt
);
3628 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (uloop
, def
));
3629 if (chrec_contains_undetermined (scev
))
3632 base
= initial_condition_in_loop_num (scev
, loop
->num
);
3633 step
= evolution_part_in_loop_num (scev
, loop
->num
);
3636 || TREE_CODE (step
) != INTEGER_CST
3637 || tree_contains_chrecs (base
, NULL
)
3638 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
3641 low
= lower_bound_in_type (type
, type
);
3642 high
= upper_bound_in_type (type
, type
);
3644 /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
3645 produce a NULL pointer. The contrary would mean NULL points to an object,
3646 while NULL is supposed to compare unequal with the address of all objects.
3647 Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
3648 NULL pointer since that would mean wrapping, which we assume here not to
3649 happen. So, we can exclude NULL from the valid range of pointer
3651 if (flag_delete_null_pointer_checks
&& int_cst_value (low
) == 0)
3652 low
= build_int_cstu (TREE_TYPE (low
), TYPE_ALIGN_UNIT (TREE_TYPE (type
)));
3654 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
3657 /* Determine information about number of iterations of a LOOP from the fact
3658 that signed arithmetics in STMT does not overflow. */
3661 infer_loop_bounds_from_signedness (struct loop
*loop
, gimple
*stmt
)
3663 tree def
, base
, step
, scev
, type
, low
, high
;
3665 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
3668 def
= gimple_assign_lhs (stmt
);
3670 if (TREE_CODE (def
) != SSA_NAME
)
3673 type
= TREE_TYPE (def
);
3674 if (!INTEGRAL_TYPE_P (type
)
3675 || !TYPE_OVERFLOW_UNDEFINED (type
))
3678 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
3679 if (chrec_contains_undetermined (scev
))
3682 base
= initial_condition_in_loop_num (scev
, loop
->num
);
3683 step
= evolution_part_in_loop_num (scev
, loop
->num
);
3686 || TREE_CODE (step
) != INTEGER_CST
3687 || tree_contains_chrecs (base
, NULL
)
3688 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
3691 low
= lower_bound_in_type (type
, type
);
3692 high
= upper_bound_in_type (type
, type
);
3693 wide_int minv
, maxv
;
3694 if (get_range_info (def
, &minv
, &maxv
) == VR_RANGE
)
3696 low
= wide_int_to_tree (type
, minv
);
3697 high
= wide_int_to_tree (type
, maxv
);
3700 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
3703 /* The following analyzers are extracting informations on the bounds
3704 of LOOP from the following undefined behaviors:
3706 - data references should not access elements over the statically
3709 - signed variables should not overflow when flag_wrapv is not set.
3713 infer_loop_bounds_from_undefined (struct loop
*loop
)
3717 gimple_stmt_iterator bsi
;
3721 bbs
= get_loop_body (loop
);
3723 for (i
= 0; i
< loop
->num_nodes
; i
++)
3727 /* If BB is not executed in each iteration of the loop, we cannot
3728 use the operations in it to infer reliable upper bound on the
3729 # of iterations of the loop. However, we can use it as a guess.
3730 Reliable guesses come only from array bounds. */
3731 reliable
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
);
3733 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
3735 gimple
*stmt
= gsi_stmt (bsi
);
3737 infer_loop_bounds_from_array (loop
, stmt
);
3741 infer_loop_bounds_from_signedness (loop
, stmt
);
3742 infer_loop_bounds_from_pointer_arith (loop
, stmt
);
3751 /* Compare wide ints, callback for qsort. */
3754 wide_int_cmp (const void *p1
, const void *p2
)
3756 const widest_int
*d1
= (const widest_int
*) p1
;
3757 const widest_int
*d2
= (const widest_int
*) p2
;
3758 return wi::cmpu (*d1
, *d2
);
3761 /* Return index of BOUND in BOUNDS array sorted in increasing order.
3762 Lookup by binary search. */
3765 bound_index (vec
<widest_int
> bounds
, const widest_int
&bound
)
3767 unsigned int end
= bounds
.length ();
3768 unsigned int begin
= 0;
3770 /* Find a matching index by means of a binary search. */
3771 while (begin
!= end
)
3773 unsigned int middle
= (begin
+ end
) / 2;
3774 widest_int index
= bounds
[middle
];
3778 else if (wi::ltu_p (index
, bound
))
3786 /* We recorded loop bounds only for statements dominating loop latch (and thus
3787 executed each loop iteration). If there are any bounds on statements not
3788 dominating the loop latch we can improve the estimate by walking the loop
3789 body and seeing if every path from loop header to loop latch contains
3790 some bounded statement. */
3793 discover_iteration_bound_by_body_walk (struct loop
*loop
)
3795 struct nb_iter_bound
*elt
;
3796 auto_vec
<widest_int
> bounds
;
3797 vec
<vec
<basic_block
> > queues
= vNULL
;
3798 vec
<basic_block
> queue
= vNULL
;
3799 ptrdiff_t queue_index
;
3800 ptrdiff_t latch_index
= 0;
3802 /* Discover what bounds may interest us. */
3803 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3805 widest_int bound
= elt
->bound
;
3807 /* Exit terminates loop at given iteration, while non-exits produce undefined
3808 effect on the next iteration. */
3812 /* If an overflow occurred, ignore the result. */
3817 if (!loop
->any_upper_bound
3818 || wi::ltu_p (bound
, loop
->nb_iterations_upper_bound
))
3819 bounds
.safe_push (bound
);
3822 /* Exit early if there is nothing to do. */
3823 if (!bounds
.exists ())
3826 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3827 fprintf (dump_file
, " Trying to walk loop body to reduce the bound.\n");
3829 /* Sort the bounds in decreasing order. */
3830 bounds
.qsort (wide_int_cmp
);
3832 /* For every basic block record the lowest bound that is guaranteed to
3833 terminate the loop. */
3835 hash_map
<basic_block
, ptrdiff_t> bb_bounds
;
3836 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3838 widest_int bound
= elt
->bound
;
3842 /* If an overflow occurred, ignore the result. */
3847 if (!loop
->any_upper_bound
3848 || wi::ltu_p (bound
, loop
->nb_iterations_upper_bound
))
3850 ptrdiff_t index
= bound_index (bounds
, bound
);
3851 ptrdiff_t *entry
= bb_bounds
.get (gimple_bb (elt
->stmt
));
3853 bb_bounds
.put (gimple_bb (elt
->stmt
), index
);
3854 else if ((ptrdiff_t)*entry
> index
)
3859 hash_map
<basic_block
, ptrdiff_t> block_priority
;
3861 /* Perform shortest path discovery loop->header ... loop->latch.
3863 The "distance" is given by the smallest loop bound of basic block
3864 present in the path and we look for path with largest smallest bound
3867 To avoid the need for fibonacci heap on double ints we simply compress
3868 double ints into indexes to BOUNDS array and then represent the queue
3869 as arrays of queues for every index.
3870 Index of BOUNDS.length() means that the execution of given BB has
3871 no bounds determined.
3873 VISITED is a pointer map translating basic block into smallest index
3874 it was inserted into the priority queue with. */
3877 /* Start walk in loop header with index set to infinite bound. */
3878 queue_index
= bounds
.length ();
3879 queues
.safe_grow_cleared (queue_index
+ 1);
3880 queue
.safe_push (loop
->header
);
3881 queues
[queue_index
] = queue
;
3882 block_priority
.put (loop
->header
, queue_index
);
3884 for (; queue_index
>= 0; queue_index
--)
3886 if (latch_index
< queue_index
)
3888 while (queues
[queue_index
].length ())
3891 ptrdiff_t bound_index
= queue_index
;
3895 queue
= queues
[queue_index
];
3898 /* OK, we later inserted the BB with lower priority, skip it. */
3899 if (*block_priority
.get (bb
) > queue_index
)
3902 /* See if we can improve the bound. */
3903 ptrdiff_t *entry
= bb_bounds
.get (bb
);
3904 if (entry
&& *entry
< bound_index
)
3905 bound_index
= *entry
;
3907 /* Insert succesors into the queue, watch for latch edge
3908 and record greatest index we saw. */
3909 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3911 bool insert
= false;
3913 if (loop_exit_edge_p (loop
, e
))
3916 if (e
== loop_latch_edge (loop
)
3917 && latch_index
< bound_index
)
3918 latch_index
= bound_index
;
3919 else if (!(entry
= block_priority
.get (e
->dest
)))
3922 block_priority
.put (e
->dest
, bound_index
);
3924 else if (*entry
< bound_index
)
3927 *entry
= bound_index
;
3931 queues
[bound_index
].safe_push (e
->dest
);
3935 queues
[queue_index
].release ();
3938 gcc_assert (latch_index
>= 0);
3939 if ((unsigned)latch_index
< bounds
.length ())
3941 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3943 fprintf (dump_file
, "Found better loop bound ");
3944 print_decu (bounds
[latch_index
], dump_file
);
3945 fprintf (dump_file
, "\n");
3947 record_niter_bound (loop
, bounds
[latch_index
], false, true);
3953 /* See if every path cross the loop goes through a statement that is known
3954 to not execute at the last iteration. In that case we can decrese iteration
3958 maybe_lower_iteration_bound (struct loop
*loop
)
3960 hash_set
<gimple
*> *not_executed_last_iteration
= NULL
;
3961 struct nb_iter_bound
*elt
;
3962 bool found_exit
= false;
3963 auto_vec
<basic_block
> queue
;
3966 /* Collect all statements with interesting (i.e. lower than
3967 nb_iterations_upper_bound) bound on them.
3969 TODO: Due to the way record_estimate choose estimates to store, the bounds
3970 will be always nb_iterations_upper_bound-1. We can change this to record
3971 also statements not dominating the loop latch and update the walk bellow
3972 to the shortest path algorithm. */
3973 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3976 && wi::ltu_p (elt
->bound
, loop
->nb_iterations_upper_bound
))
3978 if (!not_executed_last_iteration
)
3979 not_executed_last_iteration
= new hash_set
<gimple
*>;
3980 not_executed_last_iteration
->add (elt
->stmt
);
3983 if (!not_executed_last_iteration
)
3986 /* Start DFS walk in the loop header and see if we can reach the
3987 loop latch or any of the exits (including statements with side
3988 effects that may terminate the loop otherwise) without visiting
3989 any of the statements known to have undefined effect on the last
3991 queue
.safe_push (loop
->header
);
3992 visited
= BITMAP_ALLOC (NULL
);
3993 bitmap_set_bit (visited
, loop
->header
->index
);
3998 basic_block bb
= queue
.pop ();
3999 gimple_stmt_iterator gsi
;
4000 bool stmt_found
= false;
4002 /* Loop for possible exits and statements bounding the execution. */
4003 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
4005 gimple
*stmt
= gsi_stmt (gsi
);
4006 if (not_executed_last_iteration
->contains (stmt
))
4011 if (gimple_has_side_effects (stmt
))
4020 /* If no bounding statement is found, continue the walk. */
4026 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4028 if (loop_exit_edge_p (loop
, e
)
4029 || e
== loop_latch_edge (loop
))
4034 if (bitmap_set_bit (visited
, e
->dest
->index
))
4035 queue
.safe_push (e
->dest
);
4039 while (queue
.length () && !found_exit
);
4041 /* If every path through the loop reach bounding statement before exit,
4042 then we know the last iteration of the loop will have undefined effect
4043 and we can decrease number of iterations. */
4047 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4048 fprintf (dump_file
, "Reducing loop iteration estimate by 1; "
4049 "undefined statement must be executed at the last iteration.\n");
4050 record_niter_bound (loop
, loop
->nb_iterations_upper_bound
- 1,
4054 BITMAP_FREE (visited
);
4055 delete not_executed_last_iteration
;
4058 /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
4059 is true also use estimates derived from undefined behavior. */
4062 estimate_numbers_of_iterations (struct loop
*loop
)
4067 struct tree_niter_desc niter_desc
;
4072 /* Give up if we already have tried to compute an estimation. */
4073 if (loop
->estimate_state
!= EST_NOT_COMPUTED
)
4076 loop
->estimate_state
= EST_AVAILABLE
;
4078 /* If we have a measured profile, use it to estimate the number of
4079 iterations. Normally this is recorded by branch_prob right after
4080 reading the profile. In case we however found a new loop, record the
4083 Explicitly check for profile status so we do not report
4084 wrong prediction hitrates for guessed loop iterations heuristics.
4085 Do not recompute already recorded bounds - we ought to be better on
4086 updating iteration bounds than updating profile in general and thus
4087 recomputing iteration bounds later in the compilation process will just
4088 introduce random roundoff errors. */
4089 if (!loop
->any_estimate
4090 && loop
->header
->count
.reliable_p ())
4092 gcov_type nit
= expected_loop_iterations_unbounded (loop
);
4093 bound
= gcov_type_to_wide_int (nit
);
4094 record_niter_bound (loop
, bound
, true, false);
4097 /* Ensure that loop->nb_iterations is computed if possible. If it turns out
4098 to be constant, we avoid undefined behavior implied bounds and instead
4099 diagnose those loops with -Waggressive-loop-optimizations. */
4100 number_of_latch_executions (loop
);
4102 exits
= get_loop_exit_edges (loop
);
4103 likely_exit
= single_likely_exit (loop
);
4104 FOR_EACH_VEC_ELT (exits
, i
, ex
)
4106 if (!number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
4109 niter
= niter_desc
.niter
;
4110 type
= TREE_TYPE (niter
);
4111 if (TREE_CODE (niter_desc
.may_be_zero
) != INTEGER_CST
)
4112 niter
= build3 (COND_EXPR
, type
, niter_desc
.may_be_zero
,
4113 build_int_cst (type
, 0),
4115 record_estimate (loop
, niter
, niter_desc
.max
,
4116 last_stmt (ex
->src
),
4117 true, ex
== likely_exit
, true);
4118 record_control_iv (loop
, &niter_desc
);
4122 if (flag_aggressive_loop_optimizations
)
4123 infer_loop_bounds_from_undefined (loop
);
4125 discover_iteration_bound_by_body_walk (loop
);
4127 maybe_lower_iteration_bound (loop
);
4129 /* If we know the exact number of iterations of this loop, try to
4130 not break code with undefined behavior by not recording smaller
4131 maximum number of iterations. */
4132 if (loop
->nb_iterations
4133 && TREE_CODE (loop
->nb_iterations
) == INTEGER_CST
)
4135 loop
->any_upper_bound
= true;
4136 loop
->nb_iterations_upper_bound
= wi::to_widest (loop
->nb_iterations
);
4140 /* Sets NIT to the estimated number of executions of the latch of the
4141 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
4142 large as the number of iterations. If we have no reliable estimate,
4143 the function returns false, otherwise returns true. */
4146 estimated_loop_iterations (struct loop
*loop
, widest_int
*nit
)
4148 /* When SCEV information is available, try to update loop iterations
4149 estimate. Otherwise just return whatever we recorded earlier. */
4150 if (scev_initialized_p ())
4151 estimate_numbers_of_iterations (loop
);
4153 return (get_estimated_loop_iterations (loop
, nit
));
4156 /* Similar to estimated_loop_iterations, but returns the estimate only
4157 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
4158 on the number of iterations of LOOP could not be derived, returns -1. */
4161 estimated_loop_iterations_int (struct loop
*loop
)
4164 HOST_WIDE_INT hwi_nit
;
4166 if (!estimated_loop_iterations (loop
, &nit
))
4169 if (!wi::fits_shwi_p (nit
))
4171 hwi_nit
= nit
.to_shwi ();
4173 return hwi_nit
< 0 ? -1 : hwi_nit
;
4177 /* Sets NIT to an upper bound for the maximum number of executions of the
4178 latch of the LOOP. If we have no reliable estimate, the function returns
4179 false, otherwise returns true. */
4182 max_loop_iterations (struct loop
*loop
, widest_int
*nit
)
4184 /* When SCEV information is available, try to update loop iterations
4185 estimate. Otherwise just return whatever we recorded earlier. */
4186 if (scev_initialized_p ())
4187 estimate_numbers_of_iterations (loop
);
4189 return get_max_loop_iterations (loop
, nit
);
4192 /* Similar to max_loop_iterations, but returns the estimate only
4193 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
4194 on the number of iterations of LOOP could not be derived, returns -1. */
4197 max_loop_iterations_int (struct loop
*loop
)
4200 HOST_WIDE_INT hwi_nit
;
4202 if (!max_loop_iterations (loop
, &nit
))
4205 if (!wi::fits_shwi_p (nit
))
4207 hwi_nit
= nit
.to_shwi ();
4209 return hwi_nit
< 0 ? -1 : hwi_nit
;
4212 /* Sets NIT to an likely upper bound for the maximum number of executions of the
4213 latch of the LOOP. If we have no reliable estimate, the function returns
4214 false, otherwise returns true. */
4217 likely_max_loop_iterations (struct loop
*loop
, widest_int
*nit
)
4219 /* When SCEV information is available, try to update loop iterations
4220 estimate. Otherwise just return whatever we recorded earlier. */
4221 if (scev_initialized_p ())
4222 estimate_numbers_of_iterations (loop
);
4224 return get_likely_max_loop_iterations (loop
, nit
);
4227 /* Similar to max_loop_iterations, but returns the estimate only
4228 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
4229 on the number of iterations of LOOP could not be derived, returns -1. */
4232 likely_max_loop_iterations_int (struct loop
*loop
)
4235 HOST_WIDE_INT hwi_nit
;
4237 if (!likely_max_loop_iterations (loop
, &nit
))
4240 if (!wi::fits_shwi_p (nit
))
4242 hwi_nit
= nit
.to_shwi ();
4244 return hwi_nit
< 0 ? -1 : hwi_nit
;
4247 /* Returns an estimate for the number of executions of statements
4248 in the LOOP. For statements before the loop exit, this exceeds
4249 the number of execution of the latch by one. */
4252 estimated_stmt_executions_int (struct loop
*loop
)
4254 HOST_WIDE_INT nit
= estimated_loop_iterations_int (loop
);
4260 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
4262 /* If the computation overflows, return -1. */
4263 return snit
< 0 ? -1 : snit
;
4266 /* Sets NIT to the maximum number of executions of the latch of the
4267 LOOP, plus one. If we have no reliable estimate, the function returns
4268 false, otherwise returns true. */
4271 max_stmt_executions (struct loop
*loop
, widest_int
*nit
)
4273 widest_int nit_minus_one
;
4275 if (!max_loop_iterations (loop
, nit
))
4278 nit_minus_one
= *nit
;
4282 return wi::gtu_p (*nit
, nit_minus_one
);
4285 /* Sets NIT to the estimated maximum number of executions of the latch of the
4286 LOOP, plus one. If we have no likely estimate, the function returns
4287 false, otherwise returns true. */
4290 likely_max_stmt_executions (struct loop
*loop
, widest_int
*nit
)
4292 widest_int nit_minus_one
;
4294 if (!likely_max_loop_iterations (loop
, nit
))
4297 nit_minus_one
= *nit
;
4301 return wi::gtu_p (*nit
, nit_minus_one
);
4304 /* Sets NIT to the estimated number of executions of the latch of the
4305 LOOP, plus one. If we have no reliable estimate, the function returns
4306 false, otherwise returns true. */
4309 estimated_stmt_executions (struct loop
*loop
, widest_int
*nit
)
4311 widest_int nit_minus_one
;
4313 if (!estimated_loop_iterations (loop
, nit
))
4316 nit_minus_one
= *nit
;
4320 return wi::gtu_p (*nit
, nit_minus_one
);
4323 /* Records estimates on numbers of iterations of loops. */
4326 estimate_numbers_of_iterations (function
*fn
)
4330 /* We don't want to issue signed overflow warnings while getting
4331 loop iteration estimates. */
4332 fold_defer_overflow_warnings ();
4334 FOR_EACH_LOOP_FN (fn
, loop
, 0)
4335 estimate_numbers_of_iterations (loop
);
4337 fold_undefer_and_ignore_overflow_warnings ();
4340 /* Returns true if statement S1 dominates statement S2. */
4343 stmt_dominates_stmt_p (gimple
*s1
, gimple
*s2
)
4345 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
4353 gimple_stmt_iterator bsi
;
4355 if (gimple_code (s2
) == GIMPLE_PHI
)
4358 if (gimple_code (s1
) == GIMPLE_PHI
)
4361 for (bsi
= gsi_start_bb (bb1
); gsi_stmt (bsi
) != s2
; gsi_next (&bsi
))
4362 if (gsi_stmt (bsi
) == s1
)
4368 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
4371 /* Returns true when we can prove that the number of executions of
4372 STMT in the loop is at most NITER, according to the bound on
4373 the number of executions of the statement NITER_BOUND->stmt recorded in
4374 NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT.
4376 ??? This code can become quite a CPU hog - we can have many bounds,
4377 and large basic block forcing stmt_dominates_stmt_p to be queried
4378 many times on a large basic blocks, so the whole thing is O(n^2)
4379 for scev_probably_wraps_p invocation (that can be done n times).
4381 It would make more sense (and give better answers) to remember BB
4382 bounds computed by discover_iteration_bound_by_body_walk. */
4385 n_of_executions_at_most (gimple
*stmt
,
4386 struct nb_iter_bound
*niter_bound
,
4389 widest_int bound
= niter_bound
->bound
;
4390 tree nit_type
= TREE_TYPE (niter
), e
;
4393 gcc_assert (TYPE_UNSIGNED (nit_type
));
4395 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
4396 the number of iterations is small. */
4397 if (!wi::fits_to_tree_p (bound
, nit_type
))
4400 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
4401 times. This means that:
4403 -- if NITER_BOUND->is_exit is true, then everything after
4404 it at most NITER_BOUND->bound times.
4406 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
4407 is executed, then NITER_BOUND->stmt is executed as well in the same
4408 iteration then STMT is executed at most NITER_BOUND->bound + 1 times.
4410 If we can determine that NITER_BOUND->stmt is always executed
4411 after STMT, then STMT is executed at most NITER_BOUND->bound + 2 times.
4412 We conclude that if both statements belong to the same
4413 basic block and STMT is before NITER_BOUND->stmt and there are no
4414 statements with side effects in between. */
4416 if (niter_bound
->is_exit
)
4418 if (stmt
== niter_bound
->stmt
4419 || !stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
4425 if (!stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
4427 gimple_stmt_iterator bsi
;
4428 if (gimple_bb (stmt
) != gimple_bb (niter_bound
->stmt
)
4429 || gimple_code (stmt
) == GIMPLE_PHI
4430 || gimple_code (niter_bound
->stmt
) == GIMPLE_PHI
)
4433 /* By stmt_dominates_stmt_p we already know that STMT appears
4434 before NITER_BOUND->STMT. Still need to test that the loop
4435 can not be terinated by a side effect in between. */
4436 for (bsi
= gsi_for_stmt (stmt
); gsi_stmt (bsi
) != niter_bound
->stmt
;
4438 if (gimple_has_side_effects (gsi_stmt (bsi
)))
4442 || !wi::fits_to_tree_p (bound
, nit_type
))
4448 e
= fold_binary (cmp
, boolean_type_node
,
4449 niter
, wide_int_to_tree (nit_type
, bound
));
4450 return e
&& integer_nonzerop (e
);
4453 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
4456 nowrap_type_p (tree type
)
4458 if (ANY_INTEGRAL_TYPE_P (type
)
4459 && TYPE_OVERFLOW_UNDEFINED (type
))
4462 if (POINTER_TYPE_P (type
))
4468 /* Return true if we can prove LOOP is exited before evolution of induction
4469 variable {BASE, STEP} overflows with respect to its type bound. */
4472 loop_exits_before_overflow (tree base
, tree step
,
4473 gimple
*at_stmt
, struct loop
*loop
)
4476 struct control_iv
*civ
;
4477 struct nb_iter_bound
*bound
;
4478 tree e
, delta
, step_abs
, unsigned_base
;
4479 tree type
= TREE_TYPE (step
);
4480 tree unsigned_type
, valid_niter
;
4482 /* Don't issue signed overflow warnings. */
4483 fold_defer_overflow_warnings ();
4485 /* Compute the number of iterations before we reach the bound of the
4486 type, and verify that the loop is exited before this occurs. */
4487 unsigned_type
= unsigned_type_for (type
);
4488 unsigned_base
= fold_convert (unsigned_type
, base
);
4490 if (tree_int_cst_sign_bit (step
))
4492 tree extreme
= fold_convert (unsigned_type
,
4493 lower_bound_in_type (type
, type
));
4494 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, unsigned_base
, extreme
);
4495 step_abs
= fold_build1 (NEGATE_EXPR
, unsigned_type
,
4496 fold_convert (unsigned_type
, step
));
4500 tree extreme
= fold_convert (unsigned_type
,
4501 upper_bound_in_type (type
, type
));
4502 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, unsigned_base
);
4503 step_abs
= fold_convert (unsigned_type
, step
);
4506 valid_niter
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step_abs
);
4508 estimate_numbers_of_iterations (loop
);
4510 if (max_loop_iterations (loop
, &niter
)
4511 && wi::fits_to_tree_p (niter
, TREE_TYPE (valid_niter
))
4512 && (e
= fold_binary (GT_EXPR
, boolean_type_node
, valid_niter
,
4513 wide_int_to_tree (TREE_TYPE (valid_niter
),
4515 && integer_nonzerop (e
))
4517 fold_undefer_and_ignore_overflow_warnings ();
4521 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
4523 if (n_of_executions_at_most (at_stmt
, bound
, valid_niter
))
4525 fold_undefer_and_ignore_overflow_warnings ();
4529 fold_undefer_and_ignore_overflow_warnings ();
4531 /* Try to prove loop is exited before {base, step} overflows with the
4532 help of analyzed loop control IV. This is done only for IVs with
4533 constant step because otherwise we don't have the information. */
4534 if (TREE_CODE (step
) == INTEGER_CST
)
4536 for (civ
= loop
->control_ivs
; civ
; civ
= civ
->next
)
4538 enum tree_code code
;
4539 tree civ_type
= TREE_TYPE (civ
->step
);
4541 /* Have to consider type difference because operand_equal_p ignores
4542 that for constants. */
4543 if (TYPE_UNSIGNED (type
) != TYPE_UNSIGNED (civ_type
)
4544 || element_precision (type
) != element_precision (civ_type
))
4547 /* Only consider control IV with same step. */
4548 if (!operand_equal_p (step
, civ
->step
, 0))
4551 /* Done proving if this is a no-overflow control IV. */
4552 if (operand_equal_p (base
, civ
->base
, 0))
4555 /* Control IV is recorded after expanding simple operations,
4556 Here we expand base and compare it too. */
4557 tree expanded_base
= expand_simple_operations (base
);
4558 if (operand_equal_p (expanded_base
, civ
->base
, 0))
4561 /* If this is a before stepping control IV, in other words, we have
4563 {civ_base, step} = {base + step, step}
4565 Because civ {base + step, step} doesn't overflow during loop
4566 iterations, {base, step} will not overflow if we can prove the
4567 operation "base + step" does not overflow. Specifically, we try
4568 to prove below conditions are satisfied:
4570 base <= UPPER_BOUND (type) - step ;;step > 0
4571 base >= LOWER_BOUND (type) - step ;;step < 0
4573 by proving the reverse conditions are false using loop's initial
4575 if (POINTER_TYPE_P (TREE_TYPE (base
)))
4576 code
= POINTER_PLUS_EXPR
;
4580 tree stepped
= fold_build2 (code
, TREE_TYPE (base
), base
, step
);
4581 tree expanded_stepped
= fold_build2 (code
, TREE_TYPE (base
),
4582 expanded_base
, step
);
4583 if (operand_equal_p (stepped
, civ
->base
, 0)
4584 || operand_equal_p (expanded_stepped
, civ
->base
, 0))
4588 if (tree_int_cst_sign_bit (step
))
4591 extreme
= lower_bound_in_type (type
, type
);
4596 extreme
= upper_bound_in_type (type
, type
);
4598 extreme
= fold_build2 (MINUS_EXPR
, type
, extreme
, step
);
4599 e
= fold_build2 (code
, boolean_type_node
, base
, extreme
);
4600 e
= simplify_using_initial_conditions (loop
, e
);
4601 if (integer_zerop (e
))
4610 /* VAR is scev variable whose evolution part is constant STEP, this function
4611 proves that VAR can't overflow by using value range info. If VAR's value
4612 range is [MIN, MAX], it can be proven by:
4613 MAX + step doesn't overflow ; if step > 0
4615 MIN + step doesn't underflow ; if step < 0.
4617 We can only do this if var is computed in every loop iteration, i.e, var's
4618 definition has to dominate loop latch. Consider below example:
4626 # RANGE [0, 4294967294] NONZERO 65535
4627 # i_21 = PHI <0(3), i_18(9)>
4634 # RANGE [0, 65533] NONZERO 65535
4635 _6 = i_21 + 4294967295;
4636 # RANGE [0, 65533] NONZERO 65535
4637 _7 = (long unsigned int) _6;
4638 # RANGE [0, 524264] NONZERO 524280
4640 # PT = nonlocal escaped
4645 # RANGE [1, 65535] NONZERO 65535
4659 VAR _6 doesn't overflow only with pre-condition (i_21 != 0), here we
4660 can't use _6 to prove no-overlfow for _7. In fact, var _7 takes value
4661 sequence (4294967295, 0, 1, ..., 65533) in loop life time, rather than
4662 (4294967295, 4294967296, ...). */
4665 scev_var_range_cant_overflow (tree var
, tree step
, struct loop
*loop
)
4668 wide_int minv
, maxv
, diff
, step_wi
;
4669 enum value_range_type rtype
;
4671 if (TREE_CODE (step
) != INTEGER_CST
|| !INTEGRAL_TYPE_P (TREE_TYPE (var
)))
4674 /* Check if VAR evaluates in every loop iteration. It's not the case
4675 if VAR is default definition or does not dominate loop's latch. */
4676 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (var
));
4677 if (!def_bb
|| !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, def_bb
))
4680 rtype
= get_range_info (var
, &minv
, &maxv
);
4681 if (rtype
!= VR_RANGE
)
4684 /* VAR is a scev whose evolution part is STEP and value range info
4685 is [MIN, MAX], we can prove its no-overflowness by conditions:
4687 type_MAX - MAX >= step ; if step > 0
4688 MIN - type_MIN >= |step| ; if step < 0.
4690 Or VAR must take value outside of value range, which is not true. */
4691 step_wi
= wi::to_wide (step
);
4692 type
= TREE_TYPE (var
);
4693 if (tree_int_cst_sign_bit (step
))
4695 diff
= minv
- wi::to_wide (lower_bound_in_type (type
, type
));
4696 step_wi
= - step_wi
;
4699 diff
= wi::to_wide (upper_bound_in_type (type
, type
)) - maxv
;
4701 return (wi::geu_p (diff
, step_wi
));
4704 /* Return false only when the induction variable BASE + STEP * I is
4705 known to not overflow: i.e. when the number of iterations is small
4706 enough with respect to the step and initial condition in order to
4707 keep the evolution confined in TYPEs bounds. Return true when the
4708 iv is known to overflow or when the property is not computable.
4710 USE_OVERFLOW_SEMANTICS is true if this function should assume that
4711 the rules for overflow of the given language apply (e.g., that signed
4712 arithmetics in C does not overflow).
4714 If VAR is a ssa variable, this function also returns false if VAR can
4715 be proven not overflow with value range info. */
4718 scev_probably_wraps_p (tree var
, tree base
, tree step
,
4719 gimple
*at_stmt
, struct loop
*loop
,
4720 bool use_overflow_semantics
)
4722 /* FIXME: We really need something like
4723 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
4725 We used to test for the following situation that frequently appears
4726 during address arithmetics:
4728 D.1621_13 = (long unsigned intD.4) D.1620_12;
4729 D.1622_14 = D.1621_13 * 8;
4730 D.1623_15 = (doubleD.29 *) D.1622_14;
4732 And derived that the sequence corresponding to D_14
4733 can be proved to not wrap because it is used for computing a
4734 memory access; however, this is not really the case -- for example,
4735 if D_12 = (unsigned char) [254,+,1], then D_14 has values
4736 2032, 2040, 0, 8, ..., but the code is still legal. */
4738 if (chrec_contains_undetermined (base
)
4739 || chrec_contains_undetermined (step
))
4742 if (integer_zerop (step
))
4745 /* If we can use the fact that signed and pointer arithmetics does not
4746 wrap, we are done. */
4747 if (use_overflow_semantics
&& nowrap_type_p (TREE_TYPE (base
)))
4750 /* To be able to use estimates on number of iterations of the loop,
4751 we must have an upper bound on the absolute value of the step. */
4752 if (TREE_CODE (step
) != INTEGER_CST
)
4755 /* Check if var can be proven not overflow with value range info. */
4756 if (var
&& TREE_CODE (var
) == SSA_NAME
4757 && scev_var_range_cant_overflow (var
, step
, loop
))
4760 if (loop_exits_before_overflow (base
, step
, at_stmt
, loop
))
4763 /* At this point we still don't have a proof that the iv does not
4764 overflow: give up. */
4768 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
4771 free_numbers_of_iterations_estimates (struct loop
*loop
)
4773 struct control_iv
*civ
;
4774 struct nb_iter_bound
*bound
;
4776 loop
->nb_iterations
= NULL
;
4777 loop
->estimate_state
= EST_NOT_COMPUTED
;
4778 for (bound
= loop
->bounds
; bound
;)
4780 struct nb_iter_bound
*next
= bound
->next
;
4784 loop
->bounds
= NULL
;
4786 for (civ
= loop
->control_ivs
; civ
;)
4788 struct control_iv
*next
= civ
->next
;
4792 loop
->control_ivs
= NULL
;
4795 /* Frees the information on upper bounds on numbers of iterations of loops. */
4798 free_numbers_of_iterations_estimates (function
*fn
)
4802 FOR_EACH_LOOP_FN (fn
, loop
, 0)
4803 free_numbers_of_iterations_estimates (loop
);
4806 /* Substitute value VAL for ssa name NAME inside expressions held
4810 substitute_in_loop_info (struct loop
*loop
, tree name
, tree val
)
4812 loop
->nb_iterations
= simplify_replace_tree (loop
->nb_iterations
, name
, val
);