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_kind 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 /* Given exit condition IV0 CODE IV1 in TYPE, this function adjusts
1645 the condition for loop-until-wrap cases. For example:
1646 (unsigned){8, -1}_loop < 10 => {0, 1} != 9
1647 10 < (unsigned){0, max - 7}_loop => {0, 1} != 8
1648 Return true if condition is successfully adjusted. */
1651 adjust_cond_for_loop_until_wrap (tree type
, affine_iv
*iv0
, tree_code
*code
,
1654 /* Only support simple cases for the moment. */
1655 if (TREE_CODE (iv0
->base
) != INTEGER_CST
1656 || TREE_CODE (iv1
->base
) != INTEGER_CST
)
1659 tree niter_type
= unsigned_type_for (type
), high
, low
;
1660 /* Case: i-- < 10. */
1661 if (integer_zerop (iv1
->step
))
1663 /* TODO: Should handle case in which abs(step) != 1. */
1664 if (!integer_minus_onep (iv0
->step
))
1666 /* Give up on infinite loop. */
1667 if (*code
== LE_EXPR
1668 && tree_int_cst_equal (iv1
->base
, TYPE_MAX_VALUE (type
)))
1670 high
= fold_build2 (PLUS_EXPR
, niter_type
,
1671 fold_convert (niter_type
, iv0
->base
),
1672 build_int_cst (niter_type
, 1));
1673 low
= fold_convert (niter_type
, TYPE_MIN_VALUE (type
));
1675 else if (integer_zerop (iv0
->step
))
1677 /* TODO: Should handle case in which abs(step) != 1. */
1678 if (!integer_onep (iv1
->step
))
1680 /* Give up on infinite loop. */
1681 if (*code
== LE_EXPR
1682 && tree_int_cst_equal (iv0
->base
, TYPE_MIN_VALUE (type
)))
1684 high
= fold_convert (niter_type
, TYPE_MAX_VALUE (type
));
1685 low
= fold_build2 (MINUS_EXPR
, niter_type
,
1686 fold_convert (niter_type
, iv1
->base
),
1687 build_int_cst (niter_type
, 1));
1693 iv0
->step
= fold_convert (niter_type
, integer_one_node
);
1695 iv1
->step
= build_int_cst (niter_type
, 0);
1700 /* Determine the number of iterations according to condition (for staying
1701 inside loop) which compares two induction variables using comparison
1702 operator CODE. The induction variable on left side of the comparison
1703 is IV0, the right-hand side is IV1. Both induction variables must have
1704 type TYPE, which must be an integer or pointer type. The steps of the
1705 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1707 LOOP is the loop whose number of iterations we are determining.
1709 ONLY_EXIT is true if we are sure this is the only way the loop could be
1710 exited (including possibly non-returning function calls, exceptions, etc.)
1711 -- in this case we can use the information whether the control induction
1712 variables can overflow or not in a more efficient way.
1714 if EVERY_ITERATION is true, we know the test is executed on every iteration.
1716 The results (number of iterations and assumptions as described in
1717 comments at struct tree_niter_desc in tree-ssa-loop.h) are stored to NITER.
1718 Returns false if it fails to determine number of iterations, true if it
1719 was determined (possibly with some assumptions). */
1722 number_of_iterations_cond (struct loop
*loop
,
1723 tree type
, affine_iv
*iv0
, enum tree_code code
,
1724 affine_iv
*iv1
, struct tree_niter_desc
*niter
,
1725 bool only_exit
, bool every_iteration
)
1727 bool exit_must_be_taken
= false, ret
;
1730 /* If the test is not executed every iteration, wrapping may make the test
1732 TODO: the overflow case can be still used as unreliable estimate of upper
1733 bound. But we have no API to pass it down to number of iterations code
1734 and, at present, it will not use it anyway. */
1735 if (!every_iteration
1736 && (!iv0
->no_overflow
|| !iv1
->no_overflow
1737 || code
== NE_EXPR
|| code
== EQ_EXPR
))
1740 /* The meaning of these assumptions is this:
1742 then the rest of information does not have to be valid
1743 if may_be_zero then the loop does not roll, even if
1745 niter
->assumptions
= boolean_true_node
;
1746 niter
->may_be_zero
= boolean_false_node
;
1747 niter
->niter
= NULL_TREE
;
1749 niter
->bound
= NULL_TREE
;
1750 niter
->cmp
= ERROR_MARK
;
1752 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1753 the control variable is on lhs. */
1754 if (code
== GE_EXPR
|| code
== GT_EXPR
1755 || (code
== NE_EXPR
&& integer_zerop (iv0
->step
)))
1757 std::swap (iv0
, iv1
);
1758 code
= swap_tree_comparison (code
);
1761 if (POINTER_TYPE_P (type
))
1763 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1764 to the same object. If they do, the control variable cannot wrap
1765 (as wrap around the bounds of memory will never return a pointer
1766 that would be guaranteed to point to the same object, even if we
1767 avoid undefined behavior by casting to size_t and back). */
1768 iv0
->no_overflow
= true;
1769 iv1
->no_overflow
= true;
1772 /* If the control induction variable does not overflow and the only exit
1773 from the loop is the one that we analyze, we know it must be taken
1777 if (!integer_zerop (iv0
->step
) && iv0
->no_overflow
)
1778 exit_must_be_taken
= true;
1779 else if (!integer_zerop (iv1
->step
) && iv1
->no_overflow
)
1780 exit_must_be_taken
= true;
1783 /* We can handle cases which neither of the sides of the comparison is
1786 {iv0.base, iv0.step} cmp_code {iv1.base, iv1.step}
1788 {iv0.base, iv0.step - iv1.step} cmp_code {iv1.base, 0}
1790 provided that either below condition is satisfied:
1792 a) the test is NE_EXPR;
1793 b) iv0.step - iv1.step is integer and iv0/iv1 don't overflow.
1795 This rarely occurs in practice, but it is simple enough to manage. */
1796 if (!integer_zerop (iv0
->step
) && !integer_zerop (iv1
->step
))
1798 tree step_type
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1799 tree step
= fold_binary_to_constant (MINUS_EXPR
, step_type
,
1800 iv0
->step
, iv1
->step
);
1802 /* No need to check sign of the new step since below code takes care
1805 && (TREE_CODE (step
) != INTEGER_CST
1806 || !iv0
->no_overflow
|| !iv1
->no_overflow
))
1810 if (!POINTER_TYPE_P (type
))
1811 iv0
->no_overflow
= false;
1813 iv1
->step
= build_int_cst (step_type
, 0);
1814 iv1
->no_overflow
= true;
1817 /* If the result of the comparison is a constant, the loop is weird. More
1818 precise handling would be possible, but the situation is not common enough
1819 to waste time on it. */
1820 if (integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
))
1823 /* If the loop exits immediately, there is nothing to do. */
1824 tree tem
= fold_binary (code
, boolean_type_node
, iv0
->base
, iv1
->base
);
1825 if (tem
&& integer_zerop (tem
))
1827 niter
->niter
= build_int_cst (unsigned_type_for (type
), 0);
1832 /* Handle special case loops: while (i-- < 10) and while (10 < i++) by
1833 adjusting iv0, iv1 and code. */
1835 && (tree_int_cst_sign_bit (iv0
->step
)
1836 || (!integer_zerop (iv1
->step
)
1837 && !tree_int_cst_sign_bit (iv1
->step
)))
1838 && !adjust_cond_for_loop_until_wrap (type
, iv0
, &code
, iv1
))
1841 /* OK, now we know we have a senseful loop. Handle several cases, depending
1842 on what comparison operator is used. */
1843 bound_difference (loop
, iv1
->base
, iv0
->base
, &bnds
);
1845 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1848 "Analyzing # of iterations of loop %d\n", loop
->num
);
1850 fprintf (dump_file
, " exit condition ");
1851 dump_affine_iv (dump_file
, iv0
);
1852 fprintf (dump_file
, " %s ",
1853 code
== NE_EXPR
? "!="
1854 : code
== LT_EXPR
? "<"
1856 dump_affine_iv (dump_file
, iv1
);
1857 fprintf (dump_file
, "\n");
1859 fprintf (dump_file
, " bounds on difference of bases: ");
1860 mpz_out_str (dump_file
, 10, bnds
.below
);
1861 fprintf (dump_file
, " ... ");
1862 mpz_out_str (dump_file
, 10, bnds
.up
);
1863 fprintf (dump_file
, "\n");
1869 gcc_assert (integer_zerop (iv1
->step
));
1870 ret
= number_of_iterations_ne (loop
, type
, iv0
, iv1
->base
, niter
,
1871 exit_must_be_taken
, &bnds
);
1875 ret
= number_of_iterations_lt (loop
, type
, iv0
, iv1
, niter
,
1876 exit_must_be_taken
, &bnds
);
1880 ret
= number_of_iterations_le (loop
, type
, iv0
, iv1
, niter
,
1881 exit_must_be_taken
, &bnds
);
1888 mpz_clear (bnds
.up
);
1889 mpz_clear (bnds
.below
);
1891 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1895 fprintf (dump_file
, " result:\n");
1896 if (!integer_nonzerop (niter
->assumptions
))
1898 fprintf (dump_file
, " under assumptions ");
1899 print_generic_expr (dump_file
, niter
->assumptions
, TDF_SLIM
);
1900 fprintf (dump_file
, "\n");
1903 if (!integer_zerop (niter
->may_be_zero
))
1905 fprintf (dump_file
, " zero if ");
1906 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
1907 fprintf (dump_file
, "\n");
1910 fprintf (dump_file
, " # of iterations ");
1911 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
1912 fprintf (dump_file
, ", bounded by ");
1913 print_decu (niter
->max
, dump_file
);
1914 fprintf (dump_file
, "\n");
1917 fprintf (dump_file
, " failed\n\n");
1922 /* Substitute NEW_TREE for OLD in EXPR and fold the result.
1923 If VALUEIZE is non-NULL then OLD and NEW_TREE are ignored and instead
1924 all SSA names are replaced with the result of calling the VALUEIZE
1925 function with the SSA name as argument. */
1928 simplify_replace_tree (tree expr
, tree old
, tree new_tree
,
1929 tree (*valueize
) (tree
))
1932 tree ret
= NULL_TREE
, e
, se
;
1937 /* Do not bother to replace constants. */
1938 if (CONSTANT_CLASS_P (expr
))
1943 if (TREE_CODE (expr
) == SSA_NAME
)
1945 new_tree
= valueize (expr
);
1946 if (new_tree
!= expr
)
1950 else if (expr
== old
1951 || operand_equal_p (expr
, old
, 0))
1952 return unshare_expr (new_tree
);
1957 n
= TREE_OPERAND_LENGTH (expr
);
1958 for (i
= 0; i
< n
; i
++)
1960 e
= TREE_OPERAND (expr
, i
);
1961 se
= simplify_replace_tree (e
, old
, new_tree
, valueize
);
1966 ret
= copy_node (expr
);
1968 TREE_OPERAND (ret
, i
) = se
;
1971 return (ret
? fold (ret
) : expr
);
1974 /* Expand definitions of ssa names in EXPR as long as they are simple
1975 enough, and return the new expression. If STOP is specified, stop
1976 expanding if EXPR equals to it. */
1979 expand_simple_operations (tree expr
, tree stop
)
1982 tree ret
= NULL_TREE
, e
, ee
, e1
;
1983 enum tree_code code
;
1986 if (expr
== NULL_TREE
)
1989 if (is_gimple_min_invariant (expr
))
1992 code
= TREE_CODE (expr
);
1993 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
1995 n
= TREE_OPERAND_LENGTH (expr
);
1996 for (i
= 0; i
< n
; i
++)
1998 e
= TREE_OPERAND (expr
, i
);
1999 ee
= expand_simple_operations (e
, stop
);
2004 ret
= copy_node (expr
);
2006 TREE_OPERAND (ret
, i
) = ee
;
2012 fold_defer_overflow_warnings ();
2014 fold_undefer_and_ignore_overflow_warnings ();
2018 /* Stop if it's not ssa name or the one we don't want to expand. */
2019 if (TREE_CODE (expr
) != SSA_NAME
|| expr
== stop
)
2022 stmt
= SSA_NAME_DEF_STMT (expr
);
2023 if (gimple_code (stmt
) == GIMPLE_PHI
)
2025 basic_block src
, dest
;
2027 if (gimple_phi_num_args (stmt
) != 1)
2029 e
= PHI_ARG_DEF (stmt
, 0);
2031 /* Avoid propagating through loop exit phi nodes, which
2032 could break loop-closed SSA form restrictions. */
2033 dest
= gimple_bb (stmt
);
2034 src
= single_pred (dest
);
2035 if (TREE_CODE (e
) == SSA_NAME
2036 && src
->loop_father
!= dest
->loop_father
)
2039 return expand_simple_operations (e
, stop
);
2041 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2044 /* Avoid expanding to expressions that contain SSA names that need
2045 to take part in abnormal coalescing. */
2047 FOR_EACH_SSA_TREE_OPERAND (e
, stmt
, iter
, SSA_OP_USE
)
2048 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (e
))
2051 e
= gimple_assign_rhs1 (stmt
);
2052 code
= gimple_assign_rhs_code (stmt
);
2053 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
2055 if (is_gimple_min_invariant (e
))
2058 if (code
== SSA_NAME
)
2059 return expand_simple_operations (e
, stop
);
2060 else if (code
== ADDR_EXPR
)
2063 tree base
= get_addr_base_and_unit_offset (TREE_OPERAND (e
, 0),
2066 && TREE_CODE (base
) == MEM_REF
)
2068 ee
= expand_simple_operations (TREE_OPERAND (base
, 0), stop
);
2069 return fold_build2 (POINTER_PLUS_EXPR
, TREE_TYPE (expr
), ee
,
2070 wide_int_to_tree (sizetype
,
2071 mem_ref_offset (base
)
2082 /* Casts are simple. */
2083 ee
= expand_simple_operations (e
, stop
);
2084 return fold_build1 (code
, TREE_TYPE (expr
), ee
);
2088 if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (expr
))
2089 && TYPE_OVERFLOW_TRAPS (TREE_TYPE (expr
)))
2092 case POINTER_PLUS_EXPR
:
2093 /* And increments and decrements by a constant are simple. */
2094 e1
= gimple_assign_rhs2 (stmt
);
2095 if (!is_gimple_min_invariant (e1
))
2098 ee
= expand_simple_operations (e
, stop
);
2099 return fold_build2 (code
, TREE_TYPE (expr
), ee
, e1
);
2106 /* Tries to simplify EXPR using the condition COND. Returns the simplified
2107 expression (or EXPR unchanged, if no simplification was possible). */
2110 tree_simplify_using_condition_1 (tree cond
, tree expr
)
2113 tree e
, e0
, e1
, e2
, notcond
;
2114 enum tree_code code
= TREE_CODE (expr
);
2116 if (code
== INTEGER_CST
)
2119 if (code
== TRUTH_OR_EXPR
2120 || code
== TRUTH_AND_EXPR
2121 || code
== COND_EXPR
)
2125 e0
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 0));
2126 if (TREE_OPERAND (expr
, 0) != e0
)
2129 e1
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 1));
2130 if (TREE_OPERAND (expr
, 1) != e1
)
2133 if (code
== COND_EXPR
)
2135 e2
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 2));
2136 if (TREE_OPERAND (expr
, 2) != e2
)
2144 if (code
== COND_EXPR
)
2145 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
2147 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
2153 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
2154 propagation, and vice versa. Fold does not handle this, since it is
2155 considered too expensive. */
2156 if (TREE_CODE (cond
) == EQ_EXPR
)
2158 e0
= TREE_OPERAND (cond
, 0);
2159 e1
= TREE_OPERAND (cond
, 1);
2161 /* We know that e0 == e1. Check whether we cannot simplify expr
2163 e
= simplify_replace_tree (expr
, e0
, e1
);
2164 if (integer_zerop (e
) || integer_nonzerop (e
))
2167 e
= simplify_replace_tree (expr
, e1
, e0
);
2168 if (integer_zerop (e
) || integer_nonzerop (e
))
2171 if (TREE_CODE (expr
) == EQ_EXPR
)
2173 e0
= TREE_OPERAND (expr
, 0);
2174 e1
= TREE_OPERAND (expr
, 1);
2176 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
2177 e
= simplify_replace_tree (cond
, e0
, e1
);
2178 if (integer_zerop (e
))
2180 e
= simplify_replace_tree (cond
, e1
, e0
);
2181 if (integer_zerop (e
))
2184 if (TREE_CODE (expr
) == NE_EXPR
)
2186 e0
= TREE_OPERAND (expr
, 0);
2187 e1
= TREE_OPERAND (expr
, 1);
2189 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
2190 e
= simplify_replace_tree (cond
, e0
, e1
);
2191 if (integer_zerop (e
))
2192 return boolean_true_node
;
2193 e
= simplify_replace_tree (cond
, e1
, e0
);
2194 if (integer_zerop (e
))
2195 return boolean_true_node
;
2198 /* Check whether COND ==> EXPR. */
2199 notcond
= invert_truthvalue (cond
);
2200 e
= fold_binary (TRUTH_OR_EXPR
, boolean_type_node
, notcond
, expr
);
2201 if (e
&& integer_nonzerop (e
))
2204 /* Check whether COND ==> not EXPR. */
2205 e
= fold_binary (TRUTH_AND_EXPR
, boolean_type_node
, cond
, expr
);
2206 if (e
&& integer_zerop (e
))
2212 /* Tries to simplify EXPR using the condition COND. Returns the simplified
2213 expression (or EXPR unchanged, if no simplification was possible).
2214 Wrapper around tree_simplify_using_condition_1 that ensures that chains
2215 of simple operations in definitions of ssa names in COND are expanded,
2216 so that things like casts or incrementing the value of the bound before
2217 the loop do not cause us to fail. */
2220 tree_simplify_using_condition (tree cond
, tree expr
)
2222 cond
= expand_simple_operations (cond
);
2224 return tree_simplify_using_condition_1 (cond
, expr
);
2227 /* Tries to simplify EXPR using the conditions on entry to LOOP.
2228 Returns the simplified expression (or EXPR unchanged, if no
2229 simplification was possible). */
2232 simplify_using_initial_conditions (struct loop
*loop
, tree expr
)
2237 tree cond
, expanded
, backup
;
2240 if (TREE_CODE (expr
) == INTEGER_CST
)
2243 backup
= expanded
= expand_simple_operations (expr
);
2245 /* Limit walking the dominators to avoid quadraticness in
2246 the number of BBs times the number of loops in degenerate
2248 for (bb
= loop
->header
;
2249 bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && cnt
< MAX_DOMINATORS_TO_WALK
;
2250 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
2252 if (!single_pred_p (bb
))
2254 e
= single_pred_edge (bb
);
2256 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
2259 stmt
= last_stmt (e
->src
);
2260 cond
= fold_build2 (gimple_cond_code (stmt
),
2262 gimple_cond_lhs (stmt
),
2263 gimple_cond_rhs (stmt
));
2264 if (e
->flags
& EDGE_FALSE_VALUE
)
2265 cond
= invert_truthvalue (cond
);
2266 expanded
= tree_simplify_using_condition (cond
, expanded
);
2267 /* Break if EXPR is simplified to const values. */
2269 && (integer_zerop (expanded
) || integer_nonzerop (expanded
)))
2275 /* Return the original expression if no simplification is done. */
2276 return operand_equal_p (backup
, expanded
, 0) ? expr
: expanded
;
2279 /* Tries to simplify EXPR using the evolutions of the loop invariants
2280 in the superloops of LOOP. Returns the simplified expression
2281 (or EXPR unchanged, if no simplification was possible). */
2284 simplify_using_outer_evolutions (struct loop
*loop
, tree expr
)
2286 enum tree_code code
= TREE_CODE (expr
);
2290 if (is_gimple_min_invariant (expr
))
2293 if (code
== TRUTH_OR_EXPR
2294 || code
== TRUTH_AND_EXPR
2295 || code
== COND_EXPR
)
2299 e0
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 0));
2300 if (TREE_OPERAND (expr
, 0) != e0
)
2303 e1
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 1));
2304 if (TREE_OPERAND (expr
, 1) != e1
)
2307 if (code
== COND_EXPR
)
2309 e2
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 2));
2310 if (TREE_OPERAND (expr
, 2) != e2
)
2318 if (code
== COND_EXPR
)
2319 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
2321 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
2327 e
= instantiate_parameters (loop
, expr
);
2328 if (is_gimple_min_invariant (e
))
2334 /* Returns true if EXIT is the only possible exit from LOOP. */
2337 loop_only_exit_p (const struct loop
*loop
, const_edge exit
)
2340 gimple_stmt_iterator bsi
;
2343 if (exit
!= single_exit (loop
))
2346 body
= get_loop_body (loop
);
2347 for (i
= 0; i
< loop
->num_nodes
; i
++)
2349 for (bsi
= gsi_start_bb (body
[i
]); !gsi_end_p (bsi
); gsi_next (&bsi
))
2350 if (stmt_can_terminate_bb_p (gsi_stmt (bsi
)))
2361 /* Stores description of number of iterations of LOOP derived from
2362 EXIT (an exit edge of the LOOP) in NITER. Returns true if some useful
2363 information could be derived (and fields of NITER have meaning described
2364 in comments at struct tree_niter_desc declaration), false otherwise.
2365 When EVERY_ITERATION is true, only tests that are known to be executed
2366 every iteration are considered (i.e. only test that alone bounds the loop).
2367 If AT_STMT is not NULL, this function stores LOOP's condition statement in
2368 it when returning true. */
2371 number_of_iterations_exit_assumptions (struct loop
*loop
, edge exit
,
2372 struct tree_niter_desc
*niter
,
2373 gcond
**at_stmt
, bool every_iteration
)
2379 enum tree_code code
;
2383 /* Nothing to analyze if the loop is known to be infinite. */
2384 if (loop_constraint_set_p (loop
, LOOP_C_INFINITE
))
2387 safe
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit
->src
);
2389 if (every_iteration
&& !safe
)
2392 niter
->assumptions
= boolean_false_node
;
2393 niter
->control
.base
= NULL_TREE
;
2394 niter
->control
.step
= NULL_TREE
;
2395 niter
->control
.no_overflow
= false;
2396 last
= last_stmt (exit
->src
);
2399 stmt
= dyn_cast
<gcond
*> (last
);
2403 /* We want the condition for staying inside loop. */
2404 code
= gimple_cond_code (stmt
);
2405 if (exit
->flags
& EDGE_TRUE_VALUE
)
2406 code
= invert_tree_comparison (code
, false);
2421 op0
= gimple_cond_lhs (stmt
);
2422 op1
= gimple_cond_rhs (stmt
);
2423 type
= TREE_TYPE (op0
);
2425 if (TREE_CODE (type
) != INTEGER_TYPE
2426 && !POINTER_TYPE_P (type
))
2429 tree iv0_niters
= NULL_TREE
;
2430 if (!simple_iv_with_niters (loop
, loop_containing_stmt (stmt
),
2431 op0
, &iv0
, safe
? &iv0_niters
: NULL
, false))
2432 return number_of_iterations_popcount (loop
, exit
, code
, niter
);
2433 tree iv1_niters
= NULL_TREE
;
2434 if (!simple_iv_with_niters (loop
, loop_containing_stmt (stmt
),
2435 op1
, &iv1
, safe
? &iv1_niters
: NULL
, false))
2437 /* Give up on complicated case. */
2438 if (iv0_niters
&& iv1_niters
)
2441 /* We don't want to see undefined signed overflow warnings while
2442 computing the number of iterations. */
2443 fold_defer_overflow_warnings ();
2445 iv0
.base
= expand_simple_operations (iv0
.base
);
2446 iv1
.base
= expand_simple_operations (iv1
.base
);
2447 if (!number_of_iterations_cond (loop
, type
, &iv0
, code
, &iv1
, niter
,
2448 loop_only_exit_p (loop
, exit
), safe
))
2450 fold_undefer_and_ignore_overflow_warnings ();
2454 /* Incorporate additional assumption implied by control iv. */
2455 tree iv_niters
= iv0_niters
? iv0_niters
: iv1_niters
;
2458 tree assumption
= fold_build2 (LE_EXPR
, boolean_type_node
, niter
->niter
,
2459 fold_convert (TREE_TYPE (niter
->niter
),
2462 if (!integer_nonzerop (assumption
))
2463 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
2464 niter
->assumptions
, assumption
);
2466 /* Refine upper bound if possible. */
2467 if (TREE_CODE (iv_niters
) == INTEGER_CST
2468 && niter
->max
> wi::to_widest (iv_niters
))
2469 niter
->max
= wi::to_widest (iv_niters
);
2472 /* There is no assumptions if the loop is known to be finite. */
2473 if (!integer_zerop (niter
->assumptions
)
2474 && loop_constraint_set_p (loop
, LOOP_C_FINITE
))
2475 niter
->assumptions
= boolean_true_node
;
2479 niter
->assumptions
= simplify_using_outer_evolutions (loop
,
2480 niter
->assumptions
);
2481 niter
->may_be_zero
= simplify_using_outer_evolutions (loop
,
2482 niter
->may_be_zero
);
2483 niter
->niter
= simplify_using_outer_evolutions (loop
, niter
->niter
);
2487 = simplify_using_initial_conditions (loop
,
2488 niter
->assumptions
);
2490 = simplify_using_initial_conditions (loop
,
2491 niter
->may_be_zero
);
2493 fold_undefer_and_ignore_overflow_warnings ();
2495 /* If NITER has simplified into a constant, update MAX. */
2496 if (TREE_CODE (niter
->niter
) == INTEGER_CST
)
2497 niter
->max
= wi::to_widest (niter
->niter
);
2502 return (!integer_zerop (niter
->assumptions
));
2506 /* Utility function to check if OP is defined by a stmt
2507 that is a val - 1. */
2510 ssa_defined_by_minus_one_stmt_p (tree op
, tree val
)
2513 return (TREE_CODE (op
) == SSA_NAME
2514 && (stmt
= SSA_NAME_DEF_STMT (op
))
2515 && is_gimple_assign (stmt
)
2516 && (gimple_assign_rhs_code (stmt
) == PLUS_EXPR
)
2517 && val
== gimple_assign_rhs1 (stmt
)
2518 && integer_minus_onep (gimple_assign_rhs2 (stmt
)));
2522 /* See if LOOP is a popcout implementation, determine NITER for the loop
2533 b_11 = PHI <b_5(D)(2), b_6(3)>
2541 OR we match copy-header version:
2548 b_11 = PHI <b_5(2), b_6(3)>
2558 If popcount pattern, update NITER accordingly.
2559 i.e., set NITER to __builtin_popcount (b)
2560 return true if we did, false otherwise.
2565 number_of_iterations_popcount (loop_p loop
, edge exit
,
2566 enum tree_code code
,
2567 struct tree_niter_desc
*niter
)
2573 tree fn
= NULL_TREE
;
2575 /* Check loop terminating branch is like
2577 gimple
*stmt
= last_stmt (exit
->src
);
2579 || gimple_code (stmt
) != GIMPLE_COND
2581 || !integer_zerop (gimple_cond_rhs (stmt
))
2582 || TREE_CODE (gimple_cond_lhs (stmt
)) != SSA_NAME
)
2585 gimple
*and_stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt
));
2587 /* Depending on copy-header is performed, feeding PHI stmts might be in
2588 the loop header or loop latch, handle this. */
2589 if (gimple_code (and_stmt
) == GIMPLE_PHI
2590 && gimple_bb (and_stmt
) == loop
->header
2591 && gimple_phi_num_args (and_stmt
) == 2
2592 && (TREE_CODE (gimple_phi_arg_def (and_stmt
,
2593 loop_latch_edge (loop
)->dest_idx
))
2596 /* SSA used in exit condition is defined by PHI stmt
2597 b_11 = PHI <b_5(D)(2), b_6(3)>
2598 from the PHI stmt, get the and_stmt
2600 tree t
= gimple_phi_arg_def (and_stmt
, loop_latch_edge (loop
)->dest_idx
);
2601 and_stmt
= SSA_NAME_DEF_STMT (t
);
2605 /* Make sure it is indeed an and stmt (b_6 = _1 & b_11). */
2606 if (!is_gimple_assign (and_stmt
)
2607 || gimple_assign_rhs_code (and_stmt
) != BIT_AND_EXPR
)
2610 tree b_11
= gimple_assign_rhs1 (and_stmt
);
2611 tree _1
= gimple_assign_rhs2 (and_stmt
);
2613 /* Check that _1 is defined by _b11 + -1 (_1 = b_11 + -1).
2614 Also make sure that b_11 is the same in and_stmt and _1 defining stmt.
2615 Also canonicalize if _1 and _b11 are revrsed. */
2616 if (ssa_defined_by_minus_one_stmt_p (b_11
, _1
))
2617 std::swap (b_11
, _1
);
2618 else if (ssa_defined_by_minus_one_stmt_p (_1
, b_11
))
2622 /* Check the recurrence:
2623 ... = PHI <b_5(2), b_6(3)>. */
2624 gimple
*phi
= SSA_NAME_DEF_STMT (b_11
);
2625 if (gimple_code (phi
) != GIMPLE_PHI
2626 || (gimple_bb (phi
) != loop_latch_edge (loop
)->dest
)
2627 || (gimple_assign_lhs (and_stmt
)
2628 != gimple_phi_arg_def (phi
, loop_latch_edge (loop
)->dest_idx
)))
2631 /* We found a match. Get the corresponding popcount builtin. */
2632 tree src
= gimple_phi_arg_def (phi
, loop_preheader_edge (loop
)->dest_idx
);
2633 if (TYPE_PRECISION (TREE_TYPE (src
)) == TYPE_PRECISION (integer_type_node
))
2634 fn
= builtin_decl_implicit (BUILT_IN_POPCOUNT
);
2635 else if (TYPE_PRECISION (TREE_TYPE (src
)) == TYPE_PRECISION
2636 (long_integer_type_node
))
2637 fn
= builtin_decl_implicit (BUILT_IN_POPCOUNTL
);
2638 else if (TYPE_PRECISION (TREE_TYPE (src
)) == TYPE_PRECISION
2639 (long_long_integer_type_node
))
2640 fn
= builtin_decl_implicit (BUILT_IN_POPCOUNTLL
);
2642 /* ??? Support promoting char/short to int. */
2646 /* Update NITER params accordingly */
2647 tree utype
= unsigned_type_for (TREE_TYPE (src
));
2648 src
= fold_convert (utype
, src
);
2649 tree call
= fold_convert (utype
, build_call_expr (fn
, 1, src
));
2651 iter
= fold_build2 (MINUS_EXPR
, utype
,
2653 build_int_cst (utype
, 1));
2657 if (TREE_CODE (call
) == INTEGER_CST
)
2658 max
= tree_to_uhwi (call
);
2660 max
= TYPE_PRECISION (TREE_TYPE (src
));
2664 niter
->niter
= iter
;
2665 niter
->assumptions
= boolean_true_node
;
2669 tree may_be_zero
= fold_build2 (EQ_EXPR
, boolean_type_node
, src
,
2672 niter
->may_be_zero
=
2673 simplify_using_initial_conditions (loop
, may_be_zero
);
2676 niter
->may_be_zero
= boolean_false_node
;
2679 niter
->bound
= NULL_TREE
;
2680 niter
->cmp
= ERROR_MARK
;
2685 /* Like number_of_iterations_exit_assumptions, but return TRUE only if
2686 the niter information holds unconditionally. */
2689 number_of_iterations_exit (struct loop
*loop
, edge exit
,
2690 struct tree_niter_desc
*niter
,
2691 bool warn
, bool every_iteration
)
2694 if (!number_of_iterations_exit_assumptions (loop
, exit
, niter
,
2695 &stmt
, every_iteration
))
2698 if (integer_nonzerop (niter
->assumptions
))
2701 if (warn
&& dump_enabled_p ())
2702 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, stmt
,
2703 "missed loop optimization: niters analysis ends up "
2704 "with assumptions.\n");
2709 /* Try to determine the number of iterations of LOOP. If we succeed,
2710 expression giving number of iterations is returned and *EXIT is
2711 set to the edge from that the information is obtained. Otherwise
2712 chrec_dont_know is returned. */
2715 find_loop_niter (struct loop
*loop
, edge
*exit
)
2718 vec
<edge
> exits
= get_loop_exit_edges (loop
);
2720 tree niter
= NULL_TREE
, aniter
;
2721 struct tree_niter_desc desc
;
2724 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2726 if (!number_of_iterations_exit (loop
, ex
, &desc
, false))
2729 if (integer_nonzerop (desc
.may_be_zero
))
2731 /* We exit in the first iteration through this exit.
2732 We won't find anything better. */
2733 niter
= build_int_cst (unsigned_type_node
, 0);
2738 if (!integer_zerop (desc
.may_be_zero
))
2741 aniter
= desc
.niter
;
2745 /* Nothing recorded yet. */
2751 /* Prefer constants, the lower the better. */
2752 if (TREE_CODE (aniter
) != INTEGER_CST
)
2755 if (TREE_CODE (niter
) != INTEGER_CST
)
2762 if (tree_int_cst_lt (aniter
, niter
))
2771 return niter
? niter
: chrec_dont_know
;
2774 /* Return true if loop is known to have bounded number of iterations. */
2777 finite_loop_p (struct loop
*loop
)
2782 flags
= flags_from_decl_or_type (current_function_decl
);
2783 if ((flags
& (ECF_CONST
|ECF_PURE
)) && !(flags
& ECF_LOOPING_CONST_OR_PURE
))
2785 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2786 fprintf (dump_file
, "Found loop %i to be finite: it is within pure or const function.\n",
2791 if (loop
->any_upper_bound
2792 || max_loop_iterations (loop
, &nit
))
2794 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2795 fprintf (dump_file
, "Found loop %i to be finite: upper bound found.\n",
2804 Analysis of a number of iterations of a loop by a brute-force evaluation.
2808 /* Bound on the number of iterations we try to evaluate. */
2810 #define MAX_ITERATIONS_TO_TRACK \
2811 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
2813 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
2814 result by a chain of operations such that all but exactly one of their
2815 operands are constants. */
2818 chain_of_csts_start (struct loop
*loop
, tree x
)
2820 gimple
*stmt
= SSA_NAME_DEF_STMT (x
);
2822 basic_block bb
= gimple_bb (stmt
);
2823 enum tree_code code
;
2826 || !flow_bb_inside_loop_p (loop
, bb
))
2829 if (gimple_code (stmt
) == GIMPLE_PHI
)
2831 if (bb
== loop
->header
)
2832 return as_a
<gphi
*> (stmt
);
2837 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2838 || gimple_assign_rhs_class (stmt
) == GIMPLE_TERNARY_RHS
)
2841 code
= gimple_assign_rhs_code (stmt
);
2842 if (gimple_references_memory_p (stmt
)
2843 || TREE_CODE_CLASS (code
) == tcc_reference
2844 || (code
== ADDR_EXPR
2845 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
2848 use
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
2849 if (use
== NULL_TREE
)
2852 return chain_of_csts_start (loop
, use
);
2855 /* Determines whether the expression X is derived from a result of a phi node
2856 in header of LOOP such that
2858 * the derivation of X consists only from operations with constants
2859 * the initial value of the phi node is constant
2860 * the value of the phi node in the next iteration can be derived from the
2861 value in the current iteration by a chain of operations with constants,
2862 or is also a constant
2864 If such phi node exists, it is returned, otherwise NULL is returned. */
2867 get_base_for (struct loop
*loop
, tree x
)
2872 if (is_gimple_min_invariant (x
))
2875 phi
= chain_of_csts_start (loop
, x
);
2879 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2880 next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2882 if (!is_gimple_min_invariant (init
))
2885 if (TREE_CODE (next
) == SSA_NAME
2886 && chain_of_csts_start (loop
, next
) != phi
)
2892 /* Given an expression X, then
2894 * if X is NULL_TREE, we return the constant BASE.
2895 * if X is a constant, we return the constant X.
2896 * otherwise X is a SSA name, whose value in the considered loop is derived
2897 by a chain of operations with constant from a result of a phi node in
2898 the header of the loop. Then we return value of X when the value of the
2899 result of this phi node is given by the constant BASE. */
2902 get_val_for (tree x
, tree base
)
2906 gcc_checking_assert (is_gimple_min_invariant (base
));
2910 else if (is_gimple_min_invariant (x
))
2913 stmt
= SSA_NAME_DEF_STMT (x
);
2914 if (gimple_code (stmt
) == GIMPLE_PHI
)
2917 gcc_checking_assert (is_gimple_assign (stmt
));
2919 /* STMT must be either an assignment of a single SSA name or an
2920 expression involving an SSA name and a constant. Try to fold that
2921 expression using the value for the SSA name. */
2922 if (gimple_assign_ssa_name_copy_p (stmt
))
2923 return get_val_for (gimple_assign_rhs1 (stmt
), base
);
2924 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_UNARY_RHS
2925 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
2926 return fold_build1 (gimple_assign_rhs_code (stmt
),
2927 gimple_expr_type (stmt
),
2928 get_val_for (gimple_assign_rhs1 (stmt
), base
));
2929 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_BINARY_RHS
)
2931 tree rhs1
= gimple_assign_rhs1 (stmt
);
2932 tree rhs2
= gimple_assign_rhs2 (stmt
);
2933 if (TREE_CODE (rhs1
) == SSA_NAME
)
2934 rhs1
= get_val_for (rhs1
, base
);
2935 else if (TREE_CODE (rhs2
) == SSA_NAME
)
2936 rhs2
= get_val_for (rhs2
, base
);
2939 return fold_build2 (gimple_assign_rhs_code (stmt
),
2940 gimple_expr_type (stmt
), rhs1
, rhs2
);
2947 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2948 by brute force -- i.e. by determining the value of the operands of the
2949 condition at EXIT in first few iterations of the loop (assuming that
2950 these values are constant) and determining the first one in that the
2951 condition is not satisfied. Returns the constant giving the number
2952 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
2955 loop_niter_by_eval (struct loop
*loop
, edge exit
)
2958 tree op
[2], val
[2], next
[2], aval
[2];
2964 cond
= last_stmt (exit
->src
);
2965 if (!cond
|| gimple_code (cond
) != GIMPLE_COND
)
2966 return chrec_dont_know
;
2968 cmp
= gimple_cond_code (cond
);
2969 if (exit
->flags
& EDGE_TRUE_VALUE
)
2970 cmp
= invert_tree_comparison (cmp
, false);
2980 op
[0] = gimple_cond_lhs (cond
);
2981 op
[1] = gimple_cond_rhs (cond
);
2985 return chrec_dont_know
;
2988 for (j
= 0; j
< 2; j
++)
2990 if (is_gimple_min_invariant (op
[j
]))
2993 next
[j
] = NULL_TREE
;
2998 phi
= get_base_for (loop
, op
[j
]);
3000 return chrec_dont_know
;
3001 val
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
3002 next
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
3006 /* Don't issue signed overflow warnings. */
3007 fold_defer_overflow_warnings ();
3009 for (i
= 0; i
< MAX_ITERATIONS_TO_TRACK
; i
++)
3011 for (j
= 0; j
< 2; j
++)
3012 aval
[j
] = get_val_for (op
[j
], val
[j
]);
3014 acnd
= fold_binary (cmp
, boolean_type_node
, aval
[0], aval
[1]);
3015 if (acnd
&& integer_zerop (acnd
))
3017 fold_undefer_and_ignore_overflow_warnings ();
3018 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3020 "Proved that loop %d iterates %d times using brute force.\n",
3022 return build_int_cst (unsigned_type_node
, i
);
3025 for (j
= 0; j
< 2; j
++)
3028 val
[j
] = get_val_for (next
[j
], val
[j
]);
3029 if (!is_gimple_min_invariant (val
[j
]))
3031 fold_undefer_and_ignore_overflow_warnings ();
3032 return chrec_dont_know
;
3036 /* If the next iteration would use the same base values
3037 as the current one, there is no point looping further,
3038 all following iterations will be the same as this one. */
3039 if (val
[0] == aval
[0] && val
[1] == aval
[1])
3043 fold_undefer_and_ignore_overflow_warnings ();
3045 return chrec_dont_know
;
3048 /* Finds the exit of the LOOP by that the loop exits after a constant
3049 number of iterations and stores the exit edge to *EXIT. The constant
3050 giving the number of iterations of LOOP is returned. The number of
3051 iterations is determined using loop_niter_by_eval (i.e. by brute force
3052 evaluation). If we are unable to find the exit for that loop_niter_by_eval
3053 determines the number of iterations, chrec_dont_know is returned. */
3056 find_loop_niter_by_eval (struct loop
*loop
, edge
*exit
)
3059 vec
<edge
> exits
= get_loop_exit_edges (loop
);
3061 tree niter
= NULL_TREE
, aniter
;
3065 /* Loops with multiple exits are expensive to handle and less important. */
3066 if (!flag_expensive_optimizations
3067 && exits
.length () > 1)
3070 return chrec_dont_know
;
3073 FOR_EACH_VEC_ELT (exits
, i
, ex
)
3075 if (!just_once_each_iteration_p (loop
, ex
->src
))
3078 aniter
= loop_niter_by_eval (loop
, ex
);
3079 if (chrec_contains_undetermined (aniter
))
3083 && !tree_int_cst_lt (aniter
, niter
))
3091 return niter
? niter
: chrec_dont_know
;
3096 Analysis of upper bounds on number of iterations of a loop.
3100 static widest_int
derive_constant_upper_bound_ops (tree
, tree
,
3101 enum tree_code
, tree
);
3103 /* Returns a constant upper bound on the value of the right-hand side of
3104 an assignment statement STMT. */
3107 derive_constant_upper_bound_assign (gimple
*stmt
)
3109 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3110 tree op0
= gimple_assign_rhs1 (stmt
);
3111 tree op1
= gimple_assign_rhs2 (stmt
);
3113 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt
)),
3117 /* Returns a constant upper bound on the value of expression VAL. VAL
3118 is considered to be unsigned. If its type is signed, its value must
3122 derive_constant_upper_bound (tree val
)
3124 enum tree_code code
;
3127 extract_ops_from_tree (val
, &code
, &op0
, &op1
, &op2
);
3128 return derive_constant_upper_bound_ops (TREE_TYPE (val
), op0
, code
, op1
);
3131 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
3132 whose type is TYPE. The expression is considered to be unsigned. If
3133 its type is signed, its value must be nonnegative. */
3136 derive_constant_upper_bound_ops (tree type
, tree op0
,
3137 enum tree_code code
, tree op1
)
3140 widest_int bnd
, max
, cst
;
3143 if (INTEGRAL_TYPE_P (type
))
3144 maxt
= TYPE_MAX_VALUE (type
);
3146 maxt
= upper_bound_in_type (type
, type
);
3148 max
= wi::to_widest (maxt
);
3153 return wi::to_widest (op0
);
3156 subtype
= TREE_TYPE (op0
);
3157 if (!TYPE_UNSIGNED (subtype
)
3158 /* If TYPE is also signed, the fact that VAL is nonnegative implies
3159 that OP0 is nonnegative. */
3160 && TYPE_UNSIGNED (type
)
3161 && !tree_expr_nonnegative_p (op0
))
3163 /* If we cannot prove that the casted expression is nonnegative,
3164 we cannot establish more useful upper bound than the precision
3165 of the type gives us. */
3169 /* We now know that op0 is an nonnegative value. Try deriving an upper
3171 bnd
= derive_constant_upper_bound (op0
);
3173 /* If the bound does not fit in TYPE, max. value of TYPE could be
3175 if (wi::ltu_p (max
, bnd
))
3181 case POINTER_PLUS_EXPR
:
3183 if (TREE_CODE (op1
) != INTEGER_CST
3184 || !tree_expr_nonnegative_p (op0
))
3187 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
3188 choose the most logical way how to treat this constant regardless
3189 of the signedness of the type. */
3190 cst
= wi::sext (wi::to_widest (op1
), TYPE_PRECISION (type
));
3191 if (code
!= MINUS_EXPR
)
3194 bnd
= derive_constant_upper_bound (op0
);
3196 if (wi::neg_p (cst
))
3199 /* Avoid CST == 0x80000... */
3200 if (wi::neg_p (cst
))
3203 /* OP0 + CST. We need to check that
3204 BND <= MAX (type) - CST. */
3206 widest_int mmax
= max
- cst
;
3207 if (wi::leu_p (bnd
, mmax
))
3214 /* OP0 - CST, where CST >= 0.
3216 If TYPE is signed, we have already verified that OP0 >= 0, and we
3217 know that the result is nonnegative. This implies that
3220 If TYPE is unsigned, we must additionally know that OP0 >= CST,
3221 otherwise the operation underflows.
3224 /* This should only happen if the type is unsigned; however, for
3225 buggy programs that use overflowing signed arithmetics even with
3226 -fno-wrapv, this condition may also be true for signed values. */
3227 if (wi::ltu_p (bnd
, cst
))
3230 if (TYPE_UNSIGNED (type
))
3232 tree tem
= fold_binary (GE_EXPR
, boolean_type_node
, op0
,
3233 wide_int_to_tree (type
, cst
));
3234 if (!tem
|| integer_nonzerop (tem
))
3243 case FLOOR_DIV_EXPR
:
3244 case EXACT_DIV_EXPR
:
3245 if (TREE_CODE (op1
) != INTEGER_CST
3246 || tree_int_cst_sign_bit (op1
))
3249 bnd
= derive_constant_upper_bound (op0
);
3250 return wi::udiv_floor (bnd
, wi::to_widest (op1
));
3253 if (TREE_CODE (op1
) != INTEGER_CST
3254 || tree_int_cst_sign_bit (op1
))
3256 return wi::to_widest (op1
);
3259 stmt
= SSA_NAME_DEF_STMT (op0
);
3260 if (gimple_code (stmt
) != GIMPLE_ASSIGN
3261 || gimple_assign_lhs (stmt
) != op0
)
3263 return derive_constant_upper_bound_assign (stmt
);
3270 /* Emit a -Waggressive-loop-optimizations warning if needed. */
3273 do_warn_aggressive_loop_optimizations (struct loop
*loop
,
3274 widest_int i_bound
, gimple
*stmt
)
3276 /* Don't warn if the loop doesn't have known constant bound. */
3277 if (!loop
->nb_iterations
3278 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
3279 || !warn_aggressive_loop_optimizations
3280 /* To avoid warning multiple times for the same loop,
3281 only start warning when we preserve loops. */
3282 || (cfun
->curr_properties
& PROP_loops
) == 0
3283 /* Only warn once per loop. */
3284 || loop
->warned_aggressive_loop_optimizations
3285 /* Only warn if undefined behavior gives us lower estimate than the
3286 known constant bound. */
3287 || wi::cmpu (i_bound
, wi::to_widest (loop
->nb_iterations
)) >= 0
3288 /* And undefined behavior happens unconditionally. */
3289 || !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (stmt
)))
3292 edge e
= single_exit (loop
);
3296 gimple
*estmt
= last_stmt (e
->src
);
3297 char buf
[WIDE_INT_PRINT_BUFFER_SIZE
];
3298 print_dec (i_bound
, buf
, TYPE_UNSIGNED (TREE_TYPE (loop
->nb_iterations
))
3299 ? UNSIGNED
: SIGNED
);
3300 auto_diagnostic_group d
;
3301 if (warning_at (gimple_location (stmt
), OPT_Waggressive_loop_optimizations
,
3302 "iteration %s invokes undefined behavior", buf
))
3303 inform (gimple_location (estmt
), "within this loop");
3304 loop
->warned_aggressive_loop_optimizations
= true;
3307 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
3308 is true if the loop is exited immediately after STMT, and this exit
3309 is taken at last when the STMT is executed BOUND + 1 times.
3310 REALISTIC is true if BOUND is expected to be close to the real number
3311 of iterations. UPPER is true if we are sure the loop iterates at most
3312 BOUND times. I_BOUND is a widest_int upper estimate on BOUND. */
3315 record_estimate (struct loop
*loop
, tree bound
, const widest_int
&i_bound
,
3316 gimple
*at_stmt
, bool is_exit
, bool realistic
, bool upper
)
3320 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3322 fprintf (dump_file
, "Statement %s", is_exit
? "(exit)" : "");
3323 print_gimple_stmt (dump_file
, at_stmt
, 0, TDF_SLIM
);
3324 fprintf (dump_file
, " is %sexecuted at most ",
3325 upper
? "" : "probably ");
3326 print_generic_expr (dump_file
, bound
, TDF_SLIM
);
3327 fprintf (dump_file
, " (bounded by ");
3328 print_decu (i_bound
, dump_file
);
3329 fprintf (dump_file
, ") + 1 times in loop %d.\n", loop
->num
);
3332 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
3333 real number of iterations. */
3334 if (TREE_CODE (bound
) != INTEGER_CST
)
3337 gcc_checking_assert (i_bound
== wi::to_widest (bound
));
3339 /* If we have a guaranteed upper bound, record it in the appropriate
3340 list, unless this is an !is_exit bound (i.e. undefined behavior in
3341 at_stmt) in a loop with known constant number of iterations. */
3344 || loop
->nb_iterations
== NULL_TREE
3345 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
))
3347 struct nb_iter_bound
*elt
= ggc_alloc
<nb_iter_bound
> ();
3349 elt
->bound
= i_bound
;
3350 elt
->stmt
= at_stmt
;
3351 elt
->is_exit
= is_exit
;
3352 elt
->next
= loop
->bounds
;
3356 /* If statement is executed on every path to the loop latch, we can directly
3357 infer the upper bound on the # of iterations of the loop. */
3358 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (at_stmt
)))
3361 /* Update the number of iteration estimates according to the bound.
3362 If at_stmt is an exit then the loop latch is executed at most BOUND times,
3363 otherwise it can be executed BOUND + 1 times. We will lower the estimate
3364 later if such statement must be executed on last iteration */
3369 widest_int new_i_bound
= i_bound
+ delta
;
3371 /* If an overflow occurred, ignore the result. */
3372 if (wi::ltu_p (new_i_bound
, delta
))
3375 if (upper
&& !is_exit
)
3376 do_warn_aggressive_loop_optimizations (loop
, new_i_bound
, at_stmt
);
3377 record_niter_bound (loop
, new_i_bound
, realistic
, upper
);
3380 /* Records the control iv analyzed in NITER for LOOP if the iv is valid
3381 and doesn't overflow. */
3384 record_control_iv (struct loop
*loop
, struct tree_niter_desc
*niter
)
3386 struct control_iv
*iv
;
3388 if (!niter
->control
.base
|| !niter
->control
.step
)
3391 if (!integer_onep (niter
->assumptions
) || !niter
->control
.no_overflow
)
3394 iv
= ggc_alloc
<control_iv
> ();
3395 iv
->base
= niter
->control
.base
;
3396 iv
->step
= niter
->control
.step
;
3397 iv
->next
= loop
->control_ivs
;
3398 loop
->control_ivs
= iv
;
3403 /* This function returns TRUE if below conditions are satisfied:
3404 1) VAR is SSA variable.
3405 2) VAR is an IV:{base, step} in its defining loop.
3406 3) IV doesn't overflow.
3407 4) Both base and step are integer constants.
3408 5) Base is the MIN/MAX value depends on IS_MIN.
3409 Store value of base to INIT correspondingly. */
3412 get_cst_init_from_scev (tree var
, wide_int
*init
, bool is_min
)
3414 if (TREE_CODE (var
) != SSA_NAME
)
3417 gimple
*def_stmt
= SSA_NAME_DEF_STMT (var
);
3418 struct loop
*loop
= loop_containing_stmt (def_stmt
);
3424 if (!simple_iv (loop
, loop
, var
, &iv
, false))
3427 if (!iv
.no_overflow
)
3430 if (TREE_CODE (iv
.base
) != INTEGER_CST
|| TREE_CODE (iv
.step
) != INTEGER_CST
)
3433 if (is_min
== tree_int_cst_sign_bit (iv
.step
))
3436 *init
= wi::to_wide (iv
.base
);
3440 /* Record the estimate on number of iterations of LOOP based on the fact that
3441 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
3442 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
3443 estimated number of iterations is expected to be close to the real one.
3444 UPPER is true if we are sure the induction variable does not wrap. */
3447 record_nonwrapping_iv (struct loop
*loop
, tree base
, tree step
, gimple
*stmt
,
3448 tree low
, tree high
, bool realistic
, bool upper
)
3450 tree niter_bound
, extreme
, delta
;
3451 tree type
= TREE_TYPE (base
), unsigned_type
;
3452 tree orig_base
= base
;
3454 if (TREE_CODE (step
) != INTEGER_CST
|| integer_zerop (step
))
3457 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3459 fprintf (dump_file
, "Induction variable (");
3460 print_generic_expr (dump_file
, TREE_TYPE (base
), TDF_SLIM
);
3461 fprintf (dump_file
, ") ");
3462 print_generic_expr (dump_file
, base
, TDF_SLIM
);
3463 fprintf (dump_file
, " + ");
3464 print_generic_expr (dump_file
, step
, TDF_SLIM
);
3465 fprintf (dump_file
, " * iteration does not wrap in statement ");
3466 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3467 fprintf (dump_file
, " in loop %d.\n", loop
->num
);
3470 unsigned_type
= unsigned_type_for (type
);
3471 base
= fold_convert (unsigned_type
, base
);
3472 step
= fold_convert (unsigned_type
, step
);
3474 if (tree_int_cst_sign_bit (step
))
3477 extreme
= fold_convert (unsigned_type
, low
);
3478 if (TREE_CODE (orig_base
) == SSA_NAME
3479 && TREE_CODE (high
) == INTEGER_CST
3480 && INTEGRAL_TYPE_P (TREE_TYPE (orig_base
))
3481 && (get_range_info (orig_base
, &min
, &max
) == VR_RANGE
3482 || get_cst_init_from_scev (orig_base
, &max
, false))
3483 && wi::gts_p (wi::to_wide (high
), max
))
3484 base
= wide_int_to_tree (unsigned_type
, max
);
3485 else if (TREE_CODE (base
) != INTEGER_CST
3486 && dominated_by_p (CDI_DOMINATORS
,
3487 loop
->latch
, gimple_bb (stmt
)))
3488 base
= fold_convert (unsigned_type
, high
);
3489 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
3490 step
= fold_build1 (NEGATE_EXPR
, unsigned_type
, step
);
3495 extreme
= fold_convert (unsigned_type
, high
);
3496 if (TREE_CODE (orig_base
) == SSA_NAME
3497 && TREE_CODE (low
) == INTEGER_CST
3498 && INTEGRAL_TYPE_P (TREE_TYPE (orig_base
))
3499 && (get_range_info (orig_base
, &min
, &max
) == VR_RANGE
3500 || get_cst_init_from_scev (orig_base
, &min
, true))
3501 && wi::gts_p (min
, wi::to_wide (low
)))
3502 base
= wide_int_to_tree (unsigned_type
, min
);
3503 else if (TREE_CODE (base
) != INTEGER_CST
3504 && dominated_by_p (CDI_DOMINATORS
,
3505 loop
->latch
, gimple_bb (stmt
)))
3506 base
= fold_convert (unsigned_type
, low
);
3507 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
3510 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
3511 would get out of the range. */
3512 niter_bound
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step
);
3513 widest_int max
= derive_constant_upper_bound (niter_bound
);
3514 record_estimate (loop
, niter_bound
, max
, stmt
, false, realistic
, upper
);
3517 /* Determine information about number of iterations a LOOP from the index
3518 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
3519 guaranteed to be executed in every iteration of LOOP. Callback for
3529 idx_infer_loop_bounds (tree base
, tree
*idx
, void *dta
)
3531 struct ilb_data
*data
= (struct ilb_data
*) dta
;
3532 tree ev
, init
, step
;
3533 tree low
, high
, type
, next
;
3534 bool sign
, upper
= true, at_end
= false;
3535 struct loop
*loop
= data
->loop
;
3537 if (TREE_CODE (base
) != ARRAY_REF
)
3540 /* For arrays at the end of the structure, we are not guaranteed that they
3541 do not really extend over their declared size. However, for arrays of
3542 size greater than one, this is unlikely to be intended. */
3543 if (array_at_struct_end_p (base
))
3549 struct loop
*dloop
= loop_containing_stmt (data
->stmt
);
3553 ev
= analyze_scalar_evolution (dloop
, *idx
);
3554 ev
= instantiate_parameters (loop
, ev
);
3555 init
= initial_condition (ev
);
3556 step
= evolution_part_in_loop_num (ev
, loop
->num
);
3560 || TREE_CODE (step
) != INTEGER_CST
3561 || integer_zerop (step
)
3562 || tree_contains_chrecs (init
, NULL
)
3563 || chrec_contains_symbols_defined_in_loop (init
, loop
->num
))
3566 low
= array_ref_low_bound (base
);
3567 high
= array_ref_up_bound (base
);
3569 /* The case of nonconstant bounds could be handled, but it would be
3571 if (TREE_CODE (low
) != INTEGER_CST
3573 || TREE_CODE (high
) != INTEGER_CST
)
3575 sign
= tree_int_cst_sign_bit (step
);
3576 type
= TREE_TYPE (step
);
3578 /* The array of length 1 at the end of a structure most likely extends
3579 beyond its bounds. */
3581 && operand_equal_p (low
, high
, 0))
3584 /* In case the relevant bound of the array does not fit in type, or
3585 it does, but bound + step (in type) still belongs into the range of the
3586 array, the index may wrap and still stay within the range of the array
3587 (consider e.g. if the array is indexed by the full range of
3590 To make things simpler, we require both bounds to fit into type, although
3591 there are cases where this would not be strictly necessary. */
3592 if (!int_fits_type_p (high
, type
)
3593 || !int_fits_type_p (low
, type
))
3595 low
= fold_convert (type
, low
);
3596 high
= fold_convert (type
, high
);
3599 next
= fold_binary (PLUS_EXPR
, type
, low
, step
);
3601 next
= fold_binary (PLUS_EXPR
, type
, high
, step
);
3603 if (tree_int_cst_compare (low
, next
) <= 0
3604 && tree_int_cst_compare (next
, high
) <= 0)
3607 /* If access is not executed on every iteration, we must ensure that overlow
3608 may not make the access valid later. */
3609 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (data
->stmt
))
3610 && scev_probably_wraps_p (NULL_TREE
,
3611 initial_condition_in_loop_num (ev
, loop
->num
),
3612 step
, data
->stmt
, loop
, true))
3615 record_nonwrapping_iv (loop
, init
, step
, data
->stmt
, low
, high
, false, upper
);
3619 /* Determine information about number of iterations a LOOP from the bounds
3620 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
3621 STMT is guaranteed to be executed in every iteration of LOOP.*/
3624 infer_loop_bounds_from_ref (struct loop
*loop
, gimple
*stmt
, tree ref
)
3626 struct ilb_data data
;
3630 for_each_index (&ref
, idx_infer_loop_bounds
, &data
);
3633 /* Determine information about number of iterations of a LOOP from the way
3634 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
3635 executed in every iteration of LOOP. */
3638 infer_loop_bounds_from_array (struct loop
*loop
, gimple
*stmt
)
3640 if (is_gimple_assign (stmt
))
3642 tree op0
= gimple_assign_lhs (stmt
);
3643 tree op1
= gimple_assign_rhs1 (stmt
);
3645 /* For each memory access, analyze its access function
3646 and record a bound on the loop iteration domain. */
3647 if (REFERENCE_CLASS_P (op0
))
3648 infer_loop_bounds_from_ref (loop
, stmt
, op0
);
3650 if (REFERENCE_CLASS_P (op1
))
3651 infer_loop_bounds_from_ref (loop
, stmt
, op1
);
3653 else if (is_gimple_call (stmt
))
3656 unsigned i
, n
= gimple_call_num_args (stmt
);
3658 lhs
= gimple_call_lhs (stmt
);
3659 if (lhs
&& REFERENCE_CLASS_P (lhs
))
3660 infer_loop_bounds_from_ref (loop
, stmt
, lhs
);
3662 for (i
= 0; i
< n
; i
++)
3664 arg
= gimple_call_arg (stmt
, i
);
3665 if (REFERENCE_CLASS_P (arg
))
3666 infer_loop_bounds_from_ref (loop
, stmt
, arg
);
3671 /* Determine information about number of iterations of a LOOP from the fact
3672 that pointer arithmetics in STMT does not overflow. */
3675 infer_loop_bounds_from_pointer_arith (struct loop
*loop
, gimple
*stmt
)
3677 tree def
, base
, step
, scev
, type
, low
, high
;
3680 if (!is_gimple_assign (stmt
)
3681 || gimple_assign_rhs_code (stmt
) != POINTER_PLUS_EXPR
)
3684 def
= gimple_assign_lhs (stmt
);
3685 if (TREE_CODE (def
) != SSA_NAME
)
3688 type
= TREE_TYPE (def
);
3689 if (!nowrap_type_p (type
))
3692 ptr
= gimple_assign_rhs1 (stmt
);
3693 if (!expr_invariant_in_loop_p (loop
, ptr
))
3696 var
= gimple_assign_rhs2 (stmt
);
3697 if (TYPE_PRECISION (type
) != TYPE_PRECISION (TREE_TYPE (var
)))
3700 struct loop
*uloop
= loop_containing_stmt (stmt
);
3701 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (uloop
, def
));
3702 if (chrec_contains_undetermined (scev
))
3705 base
= initial_condition_in_loop_num (scev
, loop
->num
);
3706 step
= evolution_part_in_loop_num (scev
, loop
->num
);
3709 || TREE_CODE (step
) != INTEGER_CST
3710 || tree_contains_chrecs (base
, NULL
)
3711 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
3714 low
= lower_bound_in_type (type
, type
);
3715 high
= upper_bound_in_type (type
, type
);
3717 /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
3718 produce a NULL pointer. The contrary would mean NULL points to an object,
3719 while NULL is supposed to compare unequal with the address of all objects.
3720 Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
3721 NULL pointer since that would mean wrapping, which we assume here not to
3722 happen. So, we can exclude NULL from the valid range of pointer
3724 if (flag_delete_null_pointer_checks
&& int_cst_value (low
) == 0)
3725 low
= build_int_cstu (TREE_TYPE (low
), TYPE_ALIGN_UNIT (TREE_TYPE (type
)));
3727 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
3730 /* Determine information about number of iterations of a LOOP from the fact
3731 that signed arithmetics in STMT does not overflow. */
3734 infer_loop_bounds_from_signedness (struct loop
*loop
, gimple
*stmt
)
3736 tree def
, base
, step
, scev
, type
, low
, high
;
3738 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
3741 def
= gimple_assign_lhs (stmt
);
3743 if (TREE_CODE (def
) != SSA_NAME
)
3746 type
= TREE_TYPE (def
);
3747 if (!INTEGRAL_TYPE_P (type
)
3748 || !TYPE_OVERFLOW_UNDEFINED (type
))
3751 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
3752 if (chrec_contains_undetermined (scev
))
3755 base
= initial_condition_in_loop_num (scev
, loop
->num
);
3756 step
= evolution_part_in_loop_num (scev
, loop
->num
);
3759 || TREE_CODE (step
) != INTEGER_CST
3760 || tree_contains_chrecs (base
, NULL
)
3761 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
3764 low
= lower_bound_in_type (type
, type
);
3765 high
= upper_bound_in_type (type
, type
);
3766 wide_int minv
, maxv
;
3767 if (get_range_info (def
, &minv
, &maxv
) == VR_RANGE
)
3769 low
= wide_int_to_tree (type
, minv
);
3770 high
= wide_int_to_tree (type
, maxv
);
3773 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
3776 /* The following analyzers are extracting informations on the bounds
3777 of LOOP from the following undefined behaviors:
3779 - data references should not access elements over the statically
3782 - signed variables should not overflow when flag_wrapv is not set.
3786 infer_loop_bounds_from_undefined (struct loop
*loop
)
3790 gimple_stmt_iterator bsi
;
3794 bbs
= get_loop_body (loop
);
3796 for (i
= 0; i
< loop
->num_nodes
; i
++)
3800 /* If BB is not executed in each iteration of the loop, we cannot
3801 use the operations in it to infer reliable upper bound on the
3802 # of iterations of the loop. However, we can use it as a guess.
3803 Reliable guesses come only from array bounds. */
3804 reliable
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
);
3806 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
3808 gimple
*stmt
= gsi_stmt (bsi
);
3810 infer_loop_bounds_from_array (loop
, stmt
);
3814 infer_loop_bounds_from_signedness (loop
, stmt
);
3815 infer_loop_bounds_from_pointer_arith (loop
, stmt
);
3824 /* Compare wide ints, callback for qsort. */
3827 wide_int_cmp (const void *p1
, const void *p2
)
3829 const widest_int
*d1
= (const widest_int
*) p1
;
3830 const widest_int
*d2
= (const widest_int
*) p2
;
3831 return wi::cmpu (*d1
, *d2
);
3834 /* Return index of BOUND in BOUNDS array sorted in increasing order.
3835 Lookup by binary search. */
3838 bound_index (vec
<widest_int
> bounds
, const widest_int
&bound
)
3840 unsigned int end
= bounds
.length ();
3841 unsigned int begin
= 0;
3843 /* Find a matching index by means of a binary search. */
3844 while (begin
!= end
)
3846 unsigned int middle
= (begin
+ end
) / 2;
3847 widest_int index
= bounds
[middle
];
3851 else if (wi::ltu_p (index
, bound
))
3859 /* We recorded loop bounds only for statements dominating loop latch (and thus
3860 executed each loop iteration). If there are any bounds on statements not
3861 dominating the loop latch we can improve the estimate by walking the loop
3862 body and seeing if every path from loop header to loop latch contains
3863 some bounded statement. */
3866 discover_iteration_bound_by_body_walk (struct loop
*loop
)
3868 struct nb_iter_bound
*elt
;
3869 auto_vec
<widest_int
> bounds
;
3870 vec
<vec
<basic_block
> > queues
= vNULL
;
3871 vec
<basic_block
> queue
= vNULL
;
3872 ptrdiff_t queue_index
;
3873 ptrdiff_t latch_index
= 0;
3875 /* Discover what bounds may interest us. */
3876 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3878 widest_int bound
= elt
->bound
;
3880 /* Exit terminates loop at given iteration, while non-exits produce undefined
3881 effect on the next iteration. */
3885 /* If an overflow occurred, ignore the result. */
3890 if (!loop
->any_upper_bound
3891 || wi::ltu_p (bound
, loop
->nb_iterations_upper_bound
))
3892 bounds
.safe_push (bound
);
3895 /* Exit early if there is nothing to do. */
3896 if (!bounds
.exists ())
3899 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3900 fprintf (dump_file
, " Trying to walk loop body to reduce the bound.\n");
3902 /* Sort the bounds in decreasing order. */
3903 bounds
.qsort (wide_int_cmp
);
3905 /* For every basic block record the lowest bound that is guaranteed to
3906 terminate the loop. */
3908 hash_map
<basic_block
, ptrdiff_t> bb_bounds
;
3909 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3911 widest_int bound
= elt
->bound
;
3915 /* If an overflow occurred, ignore the result. */
3920 if (!loop
->any_upper_bound
3921 || wi::ltu_p (bound
, loop
->nb_iterations_upper_bound
))
3923 ptrdiff_t index
= bound_index (bounds
, bound
);
3924 ptrdiff_t *entry
= bb_bounds
.get (gimple_bb (elt
->stmt
));
3926 bb_bounds
.put (gimple_bb (elt
->stmt
), index
);
3927 else if ((ptrdiff_t)*entry
> index
)
3932 hash_map
<basic_block
, ptrdiff_t> block_priority
;
3934 /* Perform shortest path discovery loop->header ... loop->latch.
3936 The "distance" is given by the smallest loop bound of basic block
3937 present in the path and we look for path with largest smallest bound
3940 To avoid the need for fibonacci heap on double ints we simply compress
3941 double ints into indexes to BOUNDS array and then represent the queue
3942 as arrays of queues for every index.
3943 Index of BOUNDS.length() means that the execution of given BB has
3944 no bounds determined.
3946 VISITED is a pointer map translating basic block into smallest index
3947 it was inserted into the priority queue with. */
3950 /* Start walk in loop header with index set to infinite bound. */
3951 queue_index
= bounds
.length ();
3952 queues
.safe_grow_cleared (queue_index
+ 1);
3953 queue
.safe_push (loop
->header
);
3954 queues
[queue_index
] = queue
;
3955 block_priority
.put (loop
->header
, queue_index
);
3957 for (; queue_index
>= 0; queue_index
--)
3959 if (latch_index
< queue_index
)
3961 while (queues
[queue_index
].length ())
3964 ptrdiff_t bound_index
= queue_index
;
3968 queue
= queues
[queue_index
];
3971 /* OK, we later inserted the BB with lower priority, skip it. */
3972 if (*block_priority
.get (bb
) > queue_index
)
3975 /* See if we can improve the bound. */
3976 ptrdiff_t *entry
= bb_bounds
.get (bb
);
3977 if (entry
&& *entry
< bound_index
)
3978 bound_index
= *entry
;
3980 /* Insert succesors into the queue, watch for latch edge
3981 and record greatest index we saw. */
3982 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
3984 bool insert
= false;
3986 if (loop_exit_edge_p (loop
, e
))
3989 if (e
== loop_latch_edge (loop
)
3990 && latch_index
< bound_index
)
3991 latch_index
= bound_index
;
3992 else if (!(entry
= block_priority
.get (e
->dest
)))
3995 block_priority
.put (e
->dest
, bound_index
);
3997 else if (*entry
< bound_index
)
4000 *entry
= bound_index
;
4004 queues
[bound_index
].safe_push (e
->dest
);
4008 queues
[queue_index
].release ();
4011 gcc_assert (latch_index
>= 0);
4012 if ((unsigned)latch_index
< bounds
.length ())
4014 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4016 fprintf (dump_file
, "Found better loop bound ");
4017 print_decu (bounds
[latch_index
], dump_file
);
4018 fprintf (dump_file
, "\n");
4020 record_niter_bound (loop
, bounds
[latch_index
], false, true);
4026 /* See if every path cross the loop goes through a statement that is known
4027 to not execute at the last iteration. In that case we can decrese iteration
4031 maybe_lower_iteration_bound (struct loop
*loop
)
4033 hash_set
<gimple
*> *not_executed_last_iteration
= NULL
;
4034 struct nb_iter_bound
*elt
;
4035 bool found_exit
= false;
4036 auto_vec
<basic_block
> queue
;
4039 /* Collect all statements with interesting (i.e. lower than
4040 nb_iterations_upper_bound) bound on them.
4042 TODO: Due to the way record_estimate choose estimates to store, the bounds
4043 will be always nb_iterations_upper_bound-1. We can change this to record
4044 also statements not dominating the loop latch and update the walk bellow
4045 to the shortest path algorithm. */
4046 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
4049 && wi::ltu_p (elt
->bound
, loop
->nb_iterations_upper_bound
))
4051 if (!not_executed_last_iteration
)
4052 not_executed_last_iteration
= new hash_set
<gimple
*>;
4053 not_executed_last_iteration
->add (elt
->stmt
);
4056 if (!not_executed_last_iteration
)
4059 /* Start DFS walk in the loop header and see if we can reach the
4060 loop latch or any of the exits (including statements with side
4061 effects that may terminate the loop otherwise) without visiting
4062 any of the statements known to have undefined effect on the last
4064 queue
.safe_push (loop
->header
);
4065 visited
= BITMAP_ALLOC (NULL
);
4066 bitmap_set_bit (visited
, loop
->header
->index
);
4071 basic_block bb
= queue
.pop ();
4072 gimple_stmt_iterator gsi
;
4073 bool stmt_found
= false;
4075 /* Loop for possible exits and statements bounding the execution. */
4076 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
4078 gimple
*stmt
= gsi_stmt (gsi
);
4079 if (not_executed_last_iteration
->contains (stmt
))
4084 if (gimple_has_side_effects (stmt
))
4093 /* If no bounding statement is found, continue the walk. */
4099 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4101 if (loop_exit_edge_p (loop
, e
)
4102 || e
== loop_latch_edge (loop
))
4107 if (bitmap_set_bit (visited
, e
->dest
->index
))
4108 queue
.safe_push (e
->dest
);
4112 while (queue
.length () && !found_exit
);
4114 /* If every path through the loop reach bounding statement before exit,
4115 then we know the last iteration of the loop will have undefined effect
4116 and we can decrease number of iterations. */
4120 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4121 fprintf (dump_file
, "Reducing loop iteration estimate by 1; "
4122 "undefined statement must be executed at the last iteration.\n");
4123 record_niter_bound (loop
, loop
->nb_iterations_upper_bound
- 1,
4127 BITMAP_FREE (visited
);
4128 delete not_executed_last_iteration
;
4131 /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
4132 is true also use estimates derived from undefined behavior. */
4135 estimate_numbers_of_iterations (struct loop
*loop
)
4140 struct tree_niter_desc niter_desc
;
4145 /* Give up if we already have tried to compute an estimation. */
4146 if (loop
->estimate_state
!= EST_NOT_COMPUTED
)
4149 loop
->estimate_state
= EST_AVAILABLE
;
4151 /* If we have a measured profile, use it to estimate the number of
4152 iterations. Normally this is recorded by branch_prob right after
4153 reading the profile. In case we however found a new loop, record the
4156 Explicitly check for profile status so we do not report
4157 wrong prediction hitrates for guessed loop iterations heuristics.
4158 Do not recompute already recorded bounds - we ought to be better on
4159 updating iteration bounds than updating profile in general and thus
4160 recomputing iteration bounds later in the compilation process will just
4161 introduce random roundoff errors. */
4162 if (!loop
->any_estimate
4163 && loop
->header
->count
.reliable_p ())
4165 gcov_type nit
= expected_loop_iterations_unbounded (loop
);
4166 bound
= gcov_type_to_wide_int (nit
);
4167 record_niter_bound (loop
, bound
, true, false);
4170 /* Ensure that loop->nb_iterations is computed if possible. If it turns out
4171 to be constant, we avoid undefined behavior implied bounds and instead
4172 diagnose those loops with -Waggressive-loop-optimizations. */
4173 number_of_latch_executions (loop
);
4175 exits
= get_loop_exit_edges (loop
);
4176 likely_exit
= single_likely_exit (loop
);
4177 FOR_EACH_VEC_ELT (exits
, i
, ex
)
4179 if (!number_of_iterations_exit (loop
, ex
, &niter_desc
, false, false))
4182 niter
= niter_desc
.niter
;
4183 type
= TREE_TYPE (niter
);
4184 if (TREE_CODE (niter_desc
.may_be_zero
) != INTEGER_CST
)
4185 niter
= build3 (COND_EXPR
, type
, niter_desc
.may_be_zero
,
4186 build_int_cst (type
, 0),
4188 record_estimate (loop
, niter
, niter_desc
.max
,
4189 last_stmt (ex
->src
),
4190 true, ex
== likely_exit
, true);
4191 record_control_iv (loop
, &niter_desc
);
4195 if (flag_aggressive_loop_optimizations
)
4196 infer_loop_bounds_from_undefined (loop
);
4198 discover_iteration_bound_by_body_walk (loop
);
4200 maybe_lower_iteration_bound (loop
);
4202 /* If we know the exact number of iterations of this loop, try to
4203 not break code with undefined behavior by not recording smaller
4204 maximum number of iterations. */
4205 if (loop
->nb_iterations
4206 && TREE_CODE (loop
->nb_iterations
) == INTEGER_CST
)
4208 loop
->any_upper_bound
= true;
4209 loop
->nb_iterations_upper_bound
= wi::to_widest (loop
->nb_iterations
);
4213 /* Sets NIT to the estimated number of executions of the latch of the
4214 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
4215 large as the number of iterations. If we have no reliable estimate,
4216 the function returns false, otherwise returns true. */
4219 estimated_loop_iterations (struct loop
*loop
, widest_int
*nit
)
4221 /* When SCEV information is available, try to update loop iterations
4222 estimate. Otherwise just return whatever we recorded earlier. */
4223 if (scev_initialized_p ())
4224 estimate_numbers_of_iterations (loop
);
4226 return (get_estimated_loop_iterations (loop
, nit
));
4229 /* Similar to estimated_loop_iterations, but returns the estimate only
4230 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
4231 on the number of iterations of LOOP could not be derived, returns -1. */
4234 estimated_loop_iterations_int (struct loop
*loop
)
4237 HOST_WIDE_INT hwi_nit
;
4239 if (!estimated_loop_iterations (loop
, &nit
))
4242 if (!wi::fits_shwi_p (nit
))
4244 hwi_nit
= nit
.to_shwi ();
4246 return hwi_nit
< 0 ? -1 : hwi_nit
;
4250 /* Sets NIT to an upper bound for the maximum number of executions of the
4251 latch of the LOOP. If we have no reliable estimate, the function returns
4252 false, otherwise returns true. */
4255 max_loop_iterations (struct loop
*loop
, widest_int
*nit
)
4257 /* When SCEV information is available, try to update loop iterations
4258 estimate. Otherwise just return whatever we recorded earlier. */
4259 if (scev_initialized_p ())
4260 estimate_numbers_of_iterations (loop
);
4262 return get_max_loop_iterations (loop
, nit
);
4265 /* Similar to max_loop_iterations, but returns the estimate only
4266 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
4267 on the number of iterations of LOOP could not be derived, returns -1. */
4270 max_loop_iterations_int (struct loop
*loop
)
4273 HOST_WIDE_INT hwi_nit
;
4275 if (!max_loop_iterations (loop
, &nit
))
4278 if (!wi::fits_shwi_p (nit
))
4280 hwi_nit
= nit
.to_shwi ();
4282 return hwi_nit
< 0 ? -1 : hwi_nit
;
4285 /* Sets NIT to an likely upper bound for the maximum number of executions of the
4286 latch of the LOOP. If we have no reliable estimate, the function returns
4287 false, otherwise returns true. */
4290 likely_max_loop_iterations (struct loop
*loop
, widest_int
*nit
)
4292 /* When SCEV information is available, try to update loop iterations
4293 estimate. Otherwise just return whatever we recorded earlier. */
4294 if (scev_initialized_p ())
4295 estimate_numbers_of_iterations (loop
);
4297 return get_likely_max_loop_iterations (loop
, nit
);
4300 /* Similar to max_loop_iterations, but returns the estimate only
4301 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
4302 on the number of iterations of LOOP could not be derived, returns -1. */
4305 likely_max_loop_iterations_int (struct loop
*loop
)
4308 HOST_WIDE_INT hwi_nit
;
4310 if (!likely_max_loop_iterations (loop
, &nit
))
4313 if (!wi::fits_shwi_p (nit
))
4315 hwi_nit
= nit
.to_shwi ();
4317 return hwi_nit
< 0 ? -1 : hwi_nit
;
4320 /* Returns an estimate for the number of executions of statements
4321 in the LOOP. For statements before the loop exit, this exceeds
4322 the number of execution of the latch by one. */
4325 estimated_stmt_executions_int (struct loop
*loop
)
4327 HOST_WIDE_INT nit
= estimated_loop_iterations_int (loop
);
4333 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
4335 /* If the computation overflows, return -1. */
4336 return snit
< 0 ? -1 : snit
;
4339 /* Sets NIT to the maximum number of executions of the latch of the
4340 LOOP, plus one. If we have no reliable estimate, the function returns
4341 false, otherwise returns true. */
4344 max_stmt_executions (struct loop
*loop
, widest_int
*nit
)
4346 widest_int nit_minus_one
;
4348 if (!max_loop_iterations (loop
, nit
))
4351 nit_minus_one
= *nit
;
4355 return wi::gtu_p (*nit
, nit_minus_one
);
4358 /* Sets NIT to the estimated maximum number of executions of the latch of the
4359 LOOP, plus one. If we have no likely estimate, the function returns
4360 false, otherwise returns true. */
4363 likely_max_stmt_executions (struct loop
*loop
, widest_int
*nit
)
4365 widest_int nit_minus_one
;
4367 if (!likely_max_loop_iterations (loop
, nit
))
4370 nit_minus_one
= *nit
;
4374 return wi::gtu_p (*nit
, nit_minus_one
);
4377 /* Sets NIT to the estimated number of executions of the latch of the
4378 LOOP, plus one. If we have no reliable estimate, the function returns
4379 false, otherwise returns true. */
4382 estimated_stmt_executions (struct loop
*loop
, widest_int
*nit
)
4384 widest_int nit_minus_one
;
4386 if (!estimated_loop_iterations (loop
, nit
))
4389 nit_minus_one
= *nit
;
4393 return wi::gtu_p (*nit
, nit_minus_one
);
4396 /* Records estimates on numbers of iterations of loops. */
4399 estimate_numbers_of_iterations (function
*fn
)
4403 /* We don't want to issue signed overflow warnings while getting
4404 loop iteration estimates. */
4405 fold_defer_overflow_warnings ();
4407 FOR_EACH_LOOP_FN (fn
, loop
, 0)
4408 estimate_numbers_of_iterations (loop
);
4410 fold_undefer_and_ignore_overflow_warnings ();
4413 /* Returns true if statement S1 dominates statement S2. */
4416 stmt_dominates_stmt_p (gimple
*s1
, gimple
*s2
)
4418 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
4426 gimple_stmt_iterator bsi
;
4428 if (gimple_code (s2
) == GIMPLE_PHI
)
4431 if (gimple_code (s1
) == GIMPLE_PHI
)
4434 for (bsi
= gsi_start_bb (bb1
); gsi_stmt (bsi
) != s2
; gsi_next (&bsi
))
4435 if (gsi_stmt (bsi
) == s1
)
4441 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
4444 /* Returns true when we can prove that the number of executions of
4445 STMT in the loop is at most NITER, according to the bound on
4446 the number of executions of the statement NITER_BOUND->stmt recorded in
4447 NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT.
4449 ??? This code can become quite a CPU hog - we can have many bounds,
4450 and large basic block forcing stmt_dominates_stmt_p to be queried
4451 many times on a large basic blocks, so the whole thing is O(n^2)
4452 for scev_probably_wraps_p invocation (that can be done n times).
4454 It would make more sense (and give better answers) to remember BB
4455 bounds computed by discover_iteration_bound_by_body_walk. */
4458 n_of_executions_at_most (gimple
*stmt
,
4459 struct nb_iter_bound
*niter_bound
,
4462 widest_int bound
= niter_bound
->bound
;
4463 tree nit_type
= TREE_TYPE (niter
), e
;
4466 gcc_assert (TYPE_UNSIGNED (nit_type
));
4468 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
4469 the number of iterations is small. */
4470 if (!wi::fits_to_tree_p (bound
, nit_type
))
4473 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
4474 times. This means that:
4476 -- if NITER_BOUND->is_exit is true, then everything after
4477 it at most NITER_BOUND->bound times.
4479 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
4480 is executed, then NITER_BOUND->stmt is executed as well in the same
4481 iteration then STMT is executed at most NITER_BOUND->bound + 1 times.
4483 If we can determine that NITER_BOUND->stmt is always executed
4484 after STMT, then STMT is executed at most NITER_BOUND->bound + 2 times.
4485 We conclude that if both statements belong to the same
4486 basic block and STMT is before NITER_BOUND->stmt and there are no
4487 statements with side effects in between. */
4489 if (niter_bound
->is_exit
)
4491 if (stmt
== niter_bound
->stmt
4492 || !stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
4498 if (!stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
4500 gimple_stmt_iterator bsi
;
4501 if (gimple_bb (stmt
) != gimple_bb (niter_bound
->stmt
)
4502 || gimple_code (stmt
) == GIMPLE_PHI
4503 || gimple_code (niter_bound
->stmt
) == GIMPLE_PHI
)
4506 /* By stmt_dominates_stmt_p we already know that STMT appears
4507 before NITER_BOUND->STMT. Still need to test that the loop
4508 can not be terinated by a side effect in between. */
4509 for (bsi
= gsi_for_stmt (stmt
); gsi_stmt (bsi
) != niter_bound
->stmt
;
4511 if (gimple_has_side_effects (gsi_stmt (bsi
)))
4515 || !wi::fits_to_tree_p (bound
, nit_type
))
4521 e
= fold_binary (cmp
, boolean_type_node
,
4522 niter
, wide_int_to_tree (nit_type
, bound
));
4523 return e
&& integer_nonzerop (e
);
4526 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
4529 nowrap_type_p (tree type
)
4531 if (ANY_INTEGRAL_TYPE_P (type
)
4532 && TYPE_OVERFLOW_UNDEFINED (type
))
4535 if (POINTER_TYPE_P (type
))
4541 /* Return true if we can prove LOOP is exited before evolution of induction
4542 variable {BASE, STEP} overflows with respect to its type bound. */
4545 loop_exits_before_overflow (tree base
, tree step
,
4546 gimple
*at_stmt
, struct loop
*loop
)
4549 struct control_iv
*civ
;
4550 struct nb_iter_bound
*bound
;
4551 tree e
, delta
, step_abs
, unsigned_base
;
4552 tree type
= TREE_TYPE (step
);
4553 tree unsigned_type
, valid_niter
;
4555 /* Don't issue signed overflow warnings. */
4556 fold_defer_overflow_warnings ();
4558 /* Compute the number of iterations before we reach the bound of the
4559 type, and verify that the loop is exited before this occurs. */
4560 unsigned_type
= unsigned_type_for (type
);
4561 unsigned_base
= fold_convert (unsigned_type
, base
);
4563 if (tree_int_cst_sign_bit (step
))
4565 tree extreme
= fold_convert (unsigned_type
,
4566 lower_bound_in_type (type
, type
));
4567 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, unsigned_base
, extreme
);
4568 step_abs
= fold_build1 (NEGATE_EXPR
, unsigned_type
,
4569 fold_convert (unsigned_type
, step
));
4573 tree extreme
= fold_convert (unsigned_type
,
4574 upper_bound_in_type (type
, type
));
4575 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, unsigned_base
);
4576 step_abs
= fold_convert (unsigned_type
, step
);
4579 valid_niter
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step_abs
);
4581 estimate_numbers_of_iterations (loop
);
4583 if (max_loop_iterations (loop
, &niter
)
4584 && wi::fits_to_tree_p (niter
, TREE_TYPE (valid_niter
))
4585 && (e
= fold_binary (GT_EXPR
, boolean_type_node
, valid_niter
,
4586 wide_int_to_tree (TREE_TYPE (valid_niter
),
4588 && integer_nonzerop (e
))
4590 fold_undefer_and_ignore_overflow_warnings ();
4594 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
4596 if (n_of_executions_at_most (at_stmt
, bound
, valid_niter
))
4598 fold_undefer_and_ignore_overflow_warnings ();
4602 fold_undefer_and_ignore_overflow_warnings ();
4604 /* Try to prove loop is exited before {base, step} overflows with the
4605 help of analyzed loop control IV. This is done only for IVs with
4606 constant step because otherwise we don't have the information. */
4607 if (TREE_CODE (step
) == INTEGER_CST
)
4609 for (civ
= loop
->control_ivs
; civ
; civ
= civ
->next
)
4611 enum tree_code code
;
4612 tree civ_type
= TREE_TYPE (civ
->step
);
4614 /* Have to consider type difference because operand_equal_p ignores
4615 that for constants. */
4616 if (TYPE_UNSIGNED (type
) != TYPE_UNSIGNED (civ_type
)
4617 || element_precision (type
) != element_precision (civ_type
))
4620 /* Only consider control IV with same step. */
4621 if (!operand_equal_p (step
, civ
->step
, 0))
4624 /* Done proving if this is a no-overflow control IV. */
4625 if (operand_equal_p (base
, civ
->base
, 0))
4628 /* Control IV is recorded after expanding simple operations,
4629 Here we expand base and compare it too. */
4630 tree expanded_base
= expand_simple_operations (base
);
4631 if (operand_equal_p (expanded_base
, civ
->base
, 0))
4634 /* If this is a before stepping control IV, in other words, we have
4636 {civ_base, step} = {base + step, step}
4638 Because civ {base + step, step} doesn't overflow during loop
4639 iterations, {base, step} will not overflow if we can prove the
4640 operation "base + step" does not overflow. Specifically, we try
4641 to prove below conditions are satisfied:
4643 base <= UPPER_BOUND (type) - step ;;step > 0
4644 base >= LOWER_BOUND (type) - step ;;step < 0
4646 by proving the reverse conditions are false using loop's initial
4648 if (POINTER_TYPE_P (TREE_TYPE (base
)))
4649 code
= POINTER_PLUS_EXPR
;
4653 tree stepped
= fold_build2 (code
, TREE_TYPE (base
), base
, step
);
4654 tree expanded_stepped
= fold_build2 (code
, TREE_TYPE (base
),
4655 expanded_base
, step
);
4656 if (operand_equal_p (stepped
, civ
->base
, 0)
4657 || operand_equal_p (expanded_stepped
, civ
->base
, 0))
4661 if (tree_int_cst_sign_bit (step
))
4664 extreme
= lower_bound_in_type (type
, type
);
4669 extreme
= upper_bound_in_type (type
, type
);
4671 extreme
= fold_build2 (MINUS_EXPR
, type
, extreme
, step
);
4672 e
= fold_build2 (code
, boolean_type_node
, base
, extreme
);
4673 e
= simplify_using_initial_conditions (loop
, e
);
4674 if (integer_zerop (e
))
4683 /* VAR is scev variable whose evolution part is constant STEP, this function
4684 proves that VAR can't overflow by using value range info. If VAR's value
4685 range is [MIN, MAX], it can be proven by:
4686 MAX + step doesn't overflow ; if step > 0
4688 MIN + step doesn't underflow ; if step < 0.
4690 We can only do this if var is computed in every loop iteration, i.e, var's
4691 definition has to dominate loop latch. Consider below example:
4699 # RANGE [0, 4294967294] NONZERO 65535
4700 # i_21 = PHI <0(3), i_18(9)>
4707 # RANGE [0, 65533] NONZERO 65535
4708 _6 = i_21 + 4294967295;
4709 # RANGE [0, 65533] NONZERO 65535
4710 _7 = (long unsigned int) _6;
4711 # RANGE [0, 524264] NONZERO 524280
4713 # PT = nonlocal escaped
4718 # RANGE [1, 65535] NONZERO 65535
4732 VAR _6 doesn't overflow only with pre-condition (i_21 != 0), here we
4733 can't use _6 to prove no-overlfow for _7. In fact, var _7 takes value
4734 sequence (4294967295, 0, 1, ..., 65533) in loop life time, rather than
4735 (4294967295, 4294967296, ...). */
4738 scev_var_range_cant_overflow (tree var
, tree step
, struct loop
*loop
)
4741 wide_int minv
, maxv
, diff
, step_wi
;
4742 enum value_range_kind rtype
;
4744 if (TREE_CODE (step
) != INTEGER_CST
|| !INTEGRAL_TYPE_P (TREE_TYPE (var
)))
4747 /* Check if VAR evaluates in every loop iteration. It's not the case
4748 if VAR is default definition or does not dominate loop's latch. */
4749 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (var
));
4750 if (!def_bb
|| !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, def_bb
))
4753 rtype
= get_range_info (var
, &minv
, &maxv
);
4754 if (rtype
!= VR_RANGE
)
4757 /* VAR is a scev whose evolution part is STEP and value range info
4758 is [MIN, MAX], we can prove its no-overflowness by conditions:
4760 type_MAX - MAX >= step ; if step > 0
4761 MIN - type_MIN >= |step| ; if step < 0.
4763 Or VAR must take value outside of value range, which is not true. */
4764 step_wi
= wi::to_wide (step
);
4765 type
= TREE_TYPE (var
);
4766 if (tree_int_cst_sign_bit (step
))
4768 diff
= minv
- wi::to_wide (lower_bound_in_type (type
, type
));
4769 step_wi
= - step_wi
;
4772 diff
= wi::to_wide (upper_bound_in_type (type
, type
)) - maxv
;
4774 return (wi::geu_p (diff
, step_wi
));
4777 /* Return false only when the induction variable BASE + STEP * I is
4778 known to not overflow: i.e. when the number of iterations is small
4779 enough with respect to the step and initial condition in order to
4780 keep the evolution confined in TYPEs bounds. Return true when the
4781 iv is known to overflow or when the property is not computable.
4783 USE_OVERFLOW_SEMANTICS is true if this function should assume that
4784 the rules for overflow of the given language apply (e.g., that signed
4785 arithmetics in C does not overflow).
4787 If VAR is a ssa variable, this function also returns false if VAR can
4788 be proven not overflow with value range info. */
4791 scev_probably_wraps_p (tree var
, tree base
, tree step
,
4792 gimple
*at_stmt
, struct loop
*loop
,
4793 bool use_overflow_semantics
)
4795 /* FIXME: We really need something like
4796 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
4798 We used to test for the following situation that frequently appears
4799 during address arithmetics:
4801 D.1621_13 = (long unsigned intD.4) D.1620_12;
4802 D.1622_14 = D.1621_13 * 8;
4803 D.1623_15 = (doubleD.29 *) D.1622_14;
4805 And derived that the sequence corresponding to D_14
4806 can be proved to not wrap because it is used for computing a
4807 memory access; however, this is not really the case -- for example,
4808 if D_12 = (unsigned char) [254,+,1], then D_14 has values
4809 2032, 2040, 0, 8, ..., but the code is still legal. */
4811 if (chrec_contains_undetermined (base
)
4812 || chrec_contains_undetermined (step
))
4815 if (integer_zerop (step
))
4818 /* If we can use the fact that signed and pointer arithmetics does not
4819 wrap, we are done. */
4820 if (use_overflow_semantics
&& nowrap_type_p (TREE_TYPE (base
)))
4823 /* To be able to use estimates on number of iterations of the loop,
4824 we must have an upper bound on the absolute value of the step. */
4825 if (TREE_CODE (step
) != INTEGER_CST
)
4828 /* Check if var can be proven not overflow with value range info. */
4829 if (var
&& TREE_CODE (var
) == SSA_NAME
4830 && scev_var_range_cant_overflow (var
, step
, loop
))
4833 if (loop_exits_before_overflow (base
, step
, at_stmt
, loop
))
4836 /* At this point we still don't have a proof that the iv does not
4837 overflow: give up. */
4841 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
4844 free_numbers_of_iterations_estimates (struct loop
*loop
)
4846 struct control_iv
*civ
;
4847 struct nb_iter_bound
*bound
;
4849 loop
->nb_iterations
= NULL
;
4850 loop
->estimate_state
= EST_NOT_COMPUTED
;
4851 for (bound
= loop
->bounds
; bound
;)
4853 struct nb_iter_bound
*next
= bound
->next
;
4857 loop
->bounds
= NULL
;
4859 for (civ
= loop
->control_ivs
; civ
;)
4861 struct control_iv
*next
= civ
->next
;
4865 loop
->control_ivs
= NULL
;
4868 /* Frees the information on upper bounds on numbers of iterations of loops. */
4871 free_numbers_of_iterations_estimates (function
*fn
)
4875 FOR_EACH_LOOP_FN (fn
, loop
, 0)
4876 free_numbers_of_iterations_estimates (loop
);
4879 /* Substitute value VAL for ssa name NAME inside expressions held
4883 substitute_in_loop_info (struct loop
*loop
, tree name
, tree val
)
4885 loop
->nb_iterations
= simplify_replace_tree (loop
->nb_iterations
, name
, val
);