1 /* Functions to determine/estimate number of iterations of a loop.
2 Copyright (C) 2004-2021 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"
45 #include "gimple-range.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 class 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
;
125 bool no_wrap
= nowrap_type_p (type
);
127 signop sgn
= TYPE_SIGN (type
);
135 STRIP_SIGN_NOPS (c0
);
136 STRIP_SIGN_NOPS (c1
);
137 ctype
= TREE_TYPE (c0
);
138 if (!useless_type_conversion_p (ctype
, type
))
144 /* We could derive quite precise information from EQ_EXPR, however,
145 such a guard is unlikely to appear, so we do not bother with
150 /* NE_EXPR comparisons do not contain much of useful information,
151 except for cases of comparing with bounds. */
152 if (TREE_CODE (c1
) != INTEGER_CST
153 || !INTEGRAL_TYPE_P (type
))
156 /* Ensure that the condition speaks about an expression in the same
158 ctype
= TREE_TYPE (c0
);
159 if (TYPE_PRECISION (ctype
) != TYPE_PRECISION (type
))
161 c0
= fold_convert (type
, c0
);
162 c1
= fold_convert (type
, c1
);
164 if (operand_equal_p (var
, c0
, 0))
168 /* Case of comparing VAR with its below/up bounds. */
170 wi::to_mpz (wi::to_wide (c1
), valc1
, TYPE_SIGN (type
));
171 if (mpz_cmp (valc1
, below
) == 0)
173 if (mpz_cmp (valc1
, up
) == 0)
180 /* Case of comparing with the bounds of the type. */
181 wide_int min
= wi::min_value (type
);
182 wide_int max
= wi::max_value (type
);
184 if (wi::to_wide (c1
) == min
)
186 if (wi::to_wide (c1
) == max
)
190 /* Quick return if no useful information. */
202 split_to_var_and_offset (expand_simple_operations (c0
), &varc0
, offc0
);
203 split_to_var_and_offset (expand_simple_operations (c1
), &varc1
, offc1
);
205 /* We are only interested in comparisons of expressions based on VAR. */
206 if (operand_equal_p (var
, varc1
, 0))
208 std::swap (varc0
, varc1
);
209 mpz_swap (offc0
, offc1
);
210 cmp
= swap_tree_comparison (cmp
);
212 else if (!operand_equal_p (var
, varc0
, 0))
221 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_query (cfun
)->range_of_expr (r
, varc1
)
234 && r
.kind () == VR_RANGE
)
236 gcc_assert (wi::le_p (r
.lower_bound (), r
.upper_bound (), sgn
));
237 wi::to_mpz (r
.lower_bound (), minc1
, sgn
);
238 wi::to_mpz (r
.upper_bound (), maxc1
, sgn
);
242 mpz_set (minc1
, mint
);
243 mpz_set (maxc1
, maxt
);
246 /* Compute valid range information for varc1 + offc1. Note nothing
247 useful can be derived if it overflows or underflows. Overflow or
248 underflow could happen when:
250 offc1 > 0 && varc1 + offc1 > MAX_VAL (type)
251 offc1 < 0 && varc1 + offc1 < MIN_VAL (type). */
252 mpz_add (minc1
, minc1
, offc1
);
253 mpz_add (maxc1
, maxc1
, offc1
);
255 || mpz_sgn (offc1
) == 0
256 || (mpz_sgn (offc1
) < 0 && mpz_cmp (minc1
, mint
) >= 0)
257 || (mpz_sgn (offc1
) > 0 && mpz_cmp (maxc1
, maxt
) <= 0));
261 if (mpz_cmp (minc1
, mint
) < 0)
262 mpz_set (minc1
, mint
);
263 if (mpz_cmp (maxc1
, maxt
) > 0)
264 mpz_set (maxc1
, maxt
);
269 mpz_sub_ui (maxc1
, maxc1
, 1);
274 mpz_add_ui (minc1
, minc1
, 1);
277 /* Compute range information for varc0. If there is no overflow,
278 the condition implied that
280 (varc0) cmp (varc1 + offc1 - offc0)
282 We can possibly improve the upper bound of varc0 if cmp is LE_EXPR,
283 or the below bound if cmp is GE_EXPR.
285 To prove there is no overflow/underflow, we need to check below
287 1) cmp == LE_EXPR && offc0 > 0
289 (varc0 + offc0) doesn't overflow
290 && (varc1 + offc1 - offc0) doesn't underflow
292 2) cmp == LE_EXPR && offc0 < 0
294 (varc0 + offc0) doesn't underflow
295 && (varc1 + offc1 - offc0) doesn't overfloe
297 In this case, (varc0 + offc0) will never underflow if we can
298 prove (varc1 + offc1 - offc0) doesn't overflow.
300 3) cmp == GE_EXPR && offc0 < 0
302 (varc0 + offc0) doesn't underflow
303 && (varc1 + offc1 - offc0) doesn't overflow
305 4) cmp == GE_EXPR && offc0 > 0
307 (varc0 + offc0) doesn't overflow
308 && (varc1 + offc1 - offc0) doesn't underflow
310 In this case, (varc0 + offc0) will never overflow if we can
311 prove (varc1 + offc1 - offc0) doesn't underflow.
313 Note we only handle case 2 and 4 in below code. */
315 mpz_sub (minc1
, minc1
, offc0
);
316 mpz_sub (maxc1
, maxc1
, offc0
);
318 || mpz_sgn (offc0
) == 0
320 && mpz_sgn (offc0
) < 0 && mpz_cmp (maxc1
, maxt
) <= 0)
322 && mpz_sgn (offc0
) > 0 && mpz_cmp (minc1
, mint
) >= 0));
328 if (mpz_cmp (up
, maxc1
) > 0)
333 if (mpz_cmp (below
, minc1
) < 0)
334 mpz_set (below
, minc1
);
346 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
347 in TYPE to MIN and MAX. */
350 determine_value_range (class loop
*loop
, tree type
, tree var
, mpz_t off
,
351 mpz_t min
, mpz_t max
)
357 enum value_range_kind rtype
= VR_VARYING
;
359 /* If the expression is a constant, we know its value exactly. */
360 if (integer_zerop (var
))
367 get_type_static_bounds (type
, min
, max
);
369 /* See if we have some range info from VRP. */
370 if (TREE_CODE (var
) == SSA_NAME
&& INTEGRAL_TYPE_P (type
))
372 edge e
= loop_preheader_edge (loop
);
373 signop sgn
= TYPE_SIGN (type
);
376 /* Either for VAR itself... */
377 value_range var_range
;
378 get_range_query (cfun
)->range_of_expr (var_range
, var
);
379 rtype
= var_range
.kind ();
380 if (!var_range
.undefined_p ())
382 minv
= var_range
.lower_bound ();
383 maxv
= var_range
.upper_bound ();
386 /* Or for PHI results in loop->header where VAR is used as
387 PHI argument from the loop preheader edge. */
388 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
390 gphi
*phi
= gsi
.phi ();
391 value_range phi_range
;
392 if (PHI_ARG_DEF_FROM_EDGE (phi
, e
) == var
393 && get_range_query (cfun
)->range_of_expr (phi_range
,
394 gimple_phi_result (phi
))
395 && phi_range
.kind () == VR_RANGE
)
397 if (rtype
!= VR_RANGE
)
400 minv
= phi_range
.lower_bound ();
401 maxv
= phi_range
.upper_bound ();
405 minv
= wi::max (minv
, phi_range
.lower_bound (), sgn
);
406 maxv
= wi::min (maxv
, phi_range
.upper_bound (), sgn
);
407 /* If the PHI result range are inconsistent with
408 the VAR range, give up on looking at the PHI
409 results. This can happen if VR_UNDEFINED is
411 if (wi::gt_p (minv
, maxv
, sgn
))
414 get_range_query (cfun
)->range_of_expr (vr
, var
);
416 if (!vr
.undefined_p ())
418 minv
= vr
.lower_bound ();
419 maxv
= vr
.upper_bound ();
428 if (rtype
!= VR_RANGE
)
435 gcc_assert (wi::le_p (minv
, maxv
, sgn
));
436 wi::to_mpz (minv
, minm
, sgn
);
437 wi::to_mpz (maxv
, maxm
, sgn
);
439 /* Now walk the dominators of the loop header and use the entry
440 guards to refine the estimates. */
441 for (bb
= loop
->header
;
442 bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && cnt
< MAX_DOMINATORS_TO_WALK
;
443 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
450 if (!single_pred_p (bb
))
452 e
= single_pred_edge (bb
);
454 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
457 cond
= last_stmt (e
->src
);
458 c0
= gimple_cond_lhs (cond
);
459 cmp
= gimple_cond_code (cond
);
460 c1
= gimple_cond_rhs (cond
);
462 if (e
->flags
& EDGE_FALSE_VALUE
)
463 cmp
= invert_tree_comparison (cmp
, false);
465 refine_value_range_using_guard (type
, var
, c0
, cmp
, c1
, minm
, maxm
);
469 mpz_add (minm
, minm
, off
);
470 mpz_add (maxm
, maxm
, off
);
471 /* If the computation may not wrap or off is zero, then this
472 is always fine. If off is negative and minv + off isn't
473 smaller than type's minimum, or off is positive and
474 maxv + off isn't bigger than type's maximum, use the more
475 precise range too. */
476 if (nowrap_type_p (type
)
477 || mpz_sgn (off
) == 0
478 || (mpz_sgn (off
) < 0 && mpz_cmp (minm
, min
) >= 0)
479 || (mpz_sgn (off
) > 0 && mpz_cmp (maxm
, max
) <= 0))
491 /* If the computation may wrap, we know nothing about the value, except for
492 the range of the type. */
493 if (!nowrap_type_p (type
))
496 /* Since the addition of OFF does not wrap, if OFF is positive, then we may
497 add it to MIN, otherwise to MAX. */
498 if (mpz_sgn (off
) < 0)
499 mpz_add (max
, max
, off
);
501 mpz_add (min
, min
, off
);
504 /* Stores the bounds on the difference of the values of the expressions
505 (var + X) and (var + Y), computed in TYPE, to BNDS. */
508 bound_difference_of_offsetted_base (tree type
, mpz_t x
, mpz_t y
,
511 int rel
= mpz_cmp (x
, y
);
512 bool may_wrap
= !nowrap_type_p (type
);
515 /* If X == Y, then the expressions are always equal.
516 If X > Y, there are the following possibilities:
517 a) neither of var + X and var + Y overflow or underflow, or both of
518 them do. Then their difference is X - Y.
519 b) var + X overflows, and var + Y does not. Then the values of the
520 expressions are var + X - M and var + Y, where M is the range of
521 the type, and their difference is X - Y - M.
522 c) var + Y underflows and var + X does not. Their difference again
524 Therefore, if the arithmetics in type does not overflow, then the
525 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
526 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
527 (X - Y, X - Y + M). */
531 mpz_set_ui (bnds
->below
, 0);
532 mpz_set_ui (bnds
->up
, 0);
537 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), m
, UNSIGNED
);
538 mpz_add_ui (m
, m
, 1);
539 mpz_sub (bnds
->up
, x
, y
);
540 mpz_set (bnds
->below
, bnds
->up
);
545 mpz_sub (bnds
->below
, bnds
->below
, m
);
547 mpz_add (bnds
->up
, bnds
->up
, m
);
553 /* From condition C0 CMP C1 derives information regarding the
554 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
555 and stores it to BNDS. */
558 refine_bounds_using_guard (tree type
, tree varx
, mpz_t offx
,
559 tree vary
, mpz_t offy
,
560 tree c0
, enum tree_code cmp
, tree c1
,
563 tree varc0
, varc1
, ctype
;
564 mpz_t offc0
, offc1
, loffx
, loffy
, bnd
;
566 bool no_wrap
= nowrap_type_p (type
);
575 STRIP_SIGN_NOPS (c0
);
576 STRIP_SIGN_NOPS (c1
);
577 ctype
= TREE_TYPE (c0
);
578 if (!useless_type_conversion_p (ctype
, type
))
584 /* We could derive quite precise information from EQ_EXPR, however, such
585 a guard is unlikely to appear, so we do not bother with handling
590 /* NE_EXPR comparisons do not contain much of useful information, except for
591 special case of comparing with the bounds of the type. */
592 if (TREE_CODE (c1
) != INTEGER_CST
593 || !INTEGRAL_TYPE_P (type
))
596 /* Ensure that the condition speaks about an expression in the same type
598 ctype
= TREE_TYPE (c0
);
599 if (TYPE_PRECISION (ctype
) != TYPE_PRECISION (type
))
601 c0
= fold_convert (type
, c0
);
602 c1
= fold_convert (type
, c1
);
604 if (TYPE_MIN_VALUE (type
)
605 && operand_equal_p (c1
, TYPE_MIN_VALUE (type
), 0))
610 if (TYPE_MAX_VALUE (type
)
611 && operand_equal_p (c1
, TYPE_MAX_VALUE (type
), 0))
624 split_to_var_and_offset (expand_simple_operations (c0
), &varc0
, offc0
);
625 split_to_var_and_offset (expand_simple_operations (c1
), &varc1
, offc1
);
627 /* We are only interested in comparisons of expressions based on VARX and
628 VARY. TODO -- we might also be able to derive some bounds from
629 expressions containing just one of the variables. */
631 if (operand_equal_p (varx
, varc1
, 0))
633 std::swap (varc0
, varc1
);
634 mpz_swap (offc0
, offc1
);
635 cmp
= swap_tree_comparison (cmp
);
638 if (!operand_equal_p (varx
, varc0
, 0)
639 || !operand_equal_p (vary
, varc1
, 0))
642 mpz_init_set (loffx
, offx
);
643 mpz_init_set (loffy
, offy
);
645 if (cmp
== GT_EXPR
|| cmp
== GE_EXPR
)
647 std::swap (varx
, vary
);
648 mpz_swap (offc0
, offc1
);
649 mpz_swap (loffx
, loffy
);
650 cmp
= swap_tree_comparison (cmp
);
654 /* If there is no overflow, the condition implies that
656 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
658 The overflows and underflows may complicate things a bit; each
659 overflow decreases the appropriate offset by M, and underflow
660 increases it by M. The above inequality would not necessarily be
663 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
664 VARX + OFFC0 overflows, but VARX + OFFX does not.
665 This may only happen if OFFX < OFFC0.
666 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
667 VARY + OFFC1 underflows and VARY + OFFY does not.
668 This may only happen if OFFY > OFFC1. */
677 x_ok
= (integer_zerop (varx
)
678 || mpz_cmp (loffx
, offc0
) >= 0);
679 y_ok
= (integer_zerop (vary
)
680 || mpz_cmp (loffy
, offc1
) <= 0);
686 mpz_sub (bnd
, loffx
, loffy
);
687 mpz_add (bnd
, bnd
, offc1
);
688 mpz_sub (bnd
, bnd
, offc0
);
691 mpz_sub_ui (bnd
, bnd
, 1);
696 if (mpz_cmp (bnds
->below
, bnd
) < 0)
697 mpz_set (bnds
->below
, bnd
);
701 if (mpz_cmp (bnd
, bnds
->up
) < 0)
702 mpz_set (bnds
->up
, bnd
);
714 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
715 The subtraction is considered to be performed in arbitrary precision,
718 We do not attempt to be too clever regarding the value ranges of X and
719 Y; most of the time, they are just integers or ssa names offsetted by
720 integer. However, we try to use the information contained in the
721 comparisons before the loop (usually created by loop header copying). */
724 bound_difference (class loop
*loop
, tree x
, tree y
, bounds
*bnds
)
726 tree type
= TREE_TYPE (x
);
729 mpz_t minx
, maxx
, miny
, maxy
;
737 /* Get rid of unnecessary casts, but preserve the value of
742 mpz_init (bnds
->below
);
746 split_to_var_and_offset (x
, &varx
, offx
);
747 split_to_var_and_offset (y
, &vary
, offy
);
749 if (!integer_zerop (varx
)
750 && operand_equal_p (varx
, vary
, 0))
752 /* Special case VARX == VARY -- we just need to compare the
753 offsets. The matters are a bit more complicated in the
754 case addition of offsets may wrap. */
755 bound_difference_of_offsetted_base (type
, offx
, offy
, bnds
);
759 /* Otherwise, use the value ranges to determine the initial
760 estimates on below and up. */
765 determine_value_range (loop
, type
, varx
, offx
, minx
, maxx
);
766 determine_value_range (loop
, type
, vary
, offy
, miny
, maxy
);
768 mpz_sub (bnds
->below
, minx
, maxy
);
769 mpz_sub (bnds
->up
, maxx
, miny
);
776 /* If both X and Y are constants, we cannot get any more precise. */
777 if (integer_zerop (varx
) && integer_zerop (vary
))
780 /* Now walk the dominators of the loop header and use the entry
781 guards to refine the estimates. */
782 for (bb
= loop
->header
;
783 bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && cnt
< MAX_DOMINATORS_TO_WALK
;
784 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
786 if (!single_pred_p (bb
))
788 e
= single_pred_edge (bb
);
790 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
793 cond
= last_stmt (e
->src
);
794 c0
= gimple_cond_lhs (cond
);
795 cmp
= gimple_cond_code (cond
);
796 c1
= gimple_cond_rhs (cond
);
798 if (e
->flags
& EDGE_FALSE_VALUE
)
799 cmp
= invert_tree_comparison (cmp
, false);
801 refine_bounds_using_guard (type
, varx
, offx
, vary
, offy
,
811 /* Update the bounds in BNDS that restrict the value of X to the bounds
812 that restrict the value of X + DELTA. X can be obtained as a
813 difference of two values in TYPE. */
816 bounds_add (bounds
*bnds
, const widest_int
&delta
, tree type
)
821 wi::to_mpz (delta
, mdelta
, SIGNED
);
824 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), max
, UNSIGNED
);
826 mpz_add (bnds
->up
, bnds
->up
, mdelta
);
827 mpz_add (bnds
->below
, bnds
->below
, mdelta
);
829 if (mpz_cmp (bnds
->up
, max
) > 0)
830 mpz_set (bnds
->up
, max
);
833 if (mpz_cmp (bnds
->below
, max
) < 0)
834 mpz_set (bnds
->below
, max
);
840 /* Update the bounds in BNDS that restrict the value of X to the bounds
841 that restrict the value of -X. */
844 bounds_negate (bounds
*bnds
)
848 mpz_init_set (tmp
, bnds
->up
);
849 mpz_neg (bnds
->up
, bnds
->below
);
850 mpz_neg (bnds
->below
, tmp
);
854 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
857 inverse (tree x
, tree mask
)
859 tree type
= TREE_TYPE (x
);
861 unsigned ctr
= tree_floor_log2 (mask
);
863 if (TYPE_PRECISION (type
) <= HOST_BITS_PER_WIDE_INT
)
865 unsigned HOST_WIDE_INT ix
;
866 unsigned HOST_WIDE_INT imask
;
867 unsigned HOST_WIDE_INT irslt
= 1;
869 gcc_assert (cst_and_fits_in_hwi (x
));
870 gcc_assert (cst_and_fits_in_hwi (mask
));
872 ix
= int_cst_value (x
);
873 imask
= int_cst_value (mask
);
882 rslt
= build_int_cst_type (type
, irslt
);
886 rslt
= build_int_cst (type
, 1);
889 rslt
= int_const_binop (MULT_EXPR
, rslt
, x
);
890 x
= int_const_binop (MULT_EXPR
, x
, x
);
892 rslt
= int_const_binop (BIT_AND_EXPR
, rslt
, mask
);
898 /* Derives the upper bound BND on the number of executions of loop with exit
899 condition S * i <> C. If NO_OVERFLOW is true, then the control variable of
900 the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed
901 that the loop ends through this exit, i.e., the induction variable ever
902 reaches the value of C.
904 The value C is equal to final - base, where final and base are the final and
905 initial value of the actual induction variable in the analysed loop. BNDS
906 bounds the value of this difference when computed in signed type with
907 unbounded range, while the computation of C is performed in an unsigned
908 type with the range matching the range of the type of the induction variable.
909 In particular, BNDS.up contains an upper bound on C in the following cases:
910 -- if the iv must reach its final value without overflow, i.e., if
911 NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
912 -- if final >= base, which we know to hold when BNDS.below >= 0. */
915 number_of_iterations_ne_max (mpz_t bnd
, bool no_overflow
, tree c
, tree s
,
916 bounds
*bnds
, bool exit_must_be_taken
)
920 tree type
= TREE_TYPE (c
);
921 bool bnds_u_valid
= ((no_overflow
&& exit_must_be_taken
)
922 || mpz_sgn (bnds
->below
) >= 0);
925 || (TREE_CODE (c
) == INTEGER_CST
926 && TREE_CODE (s
) == INTEGER_CST
927 && wi::mod_trunc (wi::to_wide (c
), wi::to_wide (s
),
928 TYPE_SIGN (type
)) == 0)
929 || (TYPE_OVERFLOW_UNDEFINED (type
)
930 && multiple_of_p (type
, c
, s
)))
932 /* If C is an exact multiple of S, then its value will be reached before
933 the induction variable overflows (unless the loop is exited in some
934 other way before). Note that the actual induction variable in the
935 loop (which ranges from base to final instead of from 0 to C) may
936 overflow, in which case BNDS.up will not be giving a correct upper
937 bound on C; thus, BNDS_U_VALID had to be computed in advance. */
939 exit_must_be_taken
= true;
942 /* If the induction variable can overflow, the number of iterations is at
943 most the period of the control variable (or infinite, but in that case
944 the whole # of iterations analysis will fail). */
947 max
= wi::mask
<widest_int
> (TYPE_PRECISION (type
)
948 - wi::ctz (wi::to_wide (s
)), false);
949 wi::to_mpz (max
, bnd
, UNSIGNED
);
953 /* Now we know that the induction variable does not overflow, so the loop
954 iterates at most (range of type / S) times. */
955 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), bnd
, UNSIGNED
);
957 /* If the induction variable is guaranteed to reach the value of C before
959 if (exit_must_be_taken
)
961 /* ... then we can strengthen this to C / S, and possibly we can use
962 the upper bound on C given by BNDS. */
963 if (TREE_CODE (c
) == INTEGER_CST
)
964 wi::to_mpz (wi::to_wide (c
), bnd
, UNSIGNED
);
965 else if (bnds_u_valid
)
966 mpz_set (bnd
, bnds
->up
);
970 wi::to_mpz (wi::to_wide (s
), d
, UNSIGNED
);
971 mpz_fdiv_q (bnd
, bnd
, d
);
975 /* Determines number of iterations of loop whose ending condition
976 is IV <> FINAL. TYPE is the type of the iv. The number of
977 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
978 we know that the exit must be taken eventually, i.e., that the IV
979 ever reaches the value FINAL (we derived this earlier, and possibly set
980 NITER->assumptions to make sure this is the case). BNDS contains the
981 bounds on the difference FINAL - IV->base. */
984 number_of_iterations_ne (class loop
*loop
, tree type
, affine_iv
*iv
,
985 tree final
, class tree_niter_desc
*niter
,
986 bool exit_must_be_taken
, bounds
*bnds
)
988 tree niter_type
= unsigned_type_for (type
);
989 tree s
, c
, d
, bits
, assumption
, tmp
, bound
;
992 niter
->control
= *iv
;
993 niter
->bound
= final
;
994 niter
->cmp
= NE_EXPR
;
996 /* Rearrange the terms so that we get inequality S * i <> C, with S
997 positive. Also cast everything to the unsigned type. If IV does
998 not overflow, BNDS bounds the value of C. Also, this is the
999 case if the computation |FINAL - IV->base| does not overflow, i.e.,
1000 if BNDS->below in the result is nonnegative. */
1001 if (tree_int_cst_sign_bit (iv
->step
))
1003 s
= fold_convert (niter_type
,
1004 fold_build1 (NEGATE_EXPR
, type
, iv
->step
));
1005 c
= fold_build2 (MINUS_EXPR
, niter_type
,
1006 fold_convert (niter_type
, iv
->base
),
1007 fold_convert (niter_type
, final
));
1008 bounds_negate (bnds
);
1012 s
= fold_convert (niter_type
, iv
->step
);
1013 c
= fold_build2 (MINUS_EXPR
, niter_type
,
1014 fold_convert (niter_type
, final
),
1015 fold_convert (niter_type
, iv
->base
));
1019 number_of_iterations_ne_max (max
, iv
->no_overflow
, c
, s
, bnds
,
1020 exit_must_be_taken
);
1021 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, max
, false),
1022 TYPE_SIGN (niter_type
));
1025 /* Compute no-overflow information for the control iv. This can be
1026 proven when below two conditions are satisfied:
1028 1) IV evaluates toward FINAL at beginning, i.e:
1029 base <= FINAL ; step > 0
1030 base >= FINAL ; step < 0
1032 2) |FINAL - base| is an exact multiple of step.
1034 Unfortunately, it's hard to prove above conditions after pass loop-ch
1035 because loop with exit condition (IV != FINAL) usually will be guarded
1036 by initial-condition (IV.base - IV.step != FINAL). In this case, we
1037 can alternatively try to prove below conditions:
1039 1') IV evaluates toward FINAL at beginning, i.e:
1040 new_base = base - step < FINAL ; step > 0
1041 && base - step doesn't underflow
1042 new_base = base - step > FINAL ; step < 0
1043 && base - step doesn't overflow
1045 2') |FINAL - new_base| is an exact multiple of step.
1047 Please refer to PR34114 as an example of loop-ch's impact, also refer
1048 to PR72817 as an example why condition 2') is necessary.
1050 Note, for NE_EXPR, base equals to FINAL is a special case, in
1051 which the loop exits immediately, and the iv does not overflow. */
1052 if (!niter
->control
.no_overflow
1053 && (integer_onep (s
) || multiple_of_p (type
, c
, s
)))
1055 tree t
, cond
, new_c
, relaxed_cond
= boolean_false_node
;
1057 if (tree_int_cst_sign_bit (iv
->step
))
1059 cond
= fold_build2 (GE_EXPR
, boolean_type_node
, iv
->base
, final
);
1060 if (TREE_CODE (type
) == INTEGER_TYPE
)
1062 /* Only when base - step doesn't overflow. */
1063 t
= TYPE_MAX_VALUE (type
);
1064 t
= fold_build2 (PLUS_EXPR
, type
, t
, iv
->step
);
1065 t
= fold_build2 (GE_EXPR
, boolean_type_node
, t
, iv
->base
);
1066 if (integer_nonzerop (t
))
1068 t
= fold_build2 (MINUS_EXPR
, type
, iv
->base
, iv
->step
);
1069 new_c
= fold_build2 (MINUS_EXPR
, niter_type
,
1070 fold_convert (niter_type
, t
),
1071 fold_convert (niter_type
, final
));
1072 if (multiple_of_p (type
, new_c
, s
))
1073 relaxed_cond
= fold_build2 (GT_EXPR
, boolean_type_node
,
1080 cond
= fold_build2 (LE_EXPR
, boolean_type_node
, iv
->base
, final
);
1081 if (TREE_CODE (type
) == INTEGER_TYPE
)
1083 /* Only when base - step doesn't underflow. */
1084 t
= TYPE_MIN_VALUE (type
);
1085 t
= fold_build2 (PLUS_EXPR
, type
, t
, iv
->step
);
1086 t
= fold_build2 (LE_EXPR
, boolean_type_node
, t
, iv
->base
);
1087 if (integer_nonzerop (t
))
1089 t
= fold_build2 (MINUS_EXPR
, type
, iv
->base
, iv
->step
);
1090 new_c
= fold_build2 (MINUS_EXPR
, niter_type
,
1091 fold_convert (niter_type
, final
),
1092 fold_convert (niter_type
, t
));
1093 if (multiple_of_p (type
, new_c
, s
))
1094 relaxed_cond
= fold_build2 (LT_EXPR
, boolean_type_node
,
1100 t
= simplify_using_initial_conditions (loop
, cond
);
1101 if (!t
|| !integer_onep (t
))
1102 t
= simplify_using_initial_conditions (loop
, relaxed_cond
);
1104 if (t
&& integer_onep (t
))
1105 niter
->control
.no_overflow
= true;
1108 /* First the trivial cases -- when the step is 1. */
1109 if (integer_onep (s
))
1114 if (niter
->control
.no_overflow
&& multiple_of_p (type
, c
, s
))
1116 niter
->niter
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, c
, s
);
1120 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
1121 is infinite. Otherwise, the number of iterations is
1122 (inverse(s/d) * (c/d)) mod (size of mode/d). */
1123 bits
= num_ending_zeros (s
);
1124 bound
= build_low_bits_mask (niter_type
,
1125 (TYPE_PRECISION (niter_type
)
1126 - tree_to_uhwi (bits
)));
1128 d
= fold_binary_to_constant (LSHIFT_EXPR
, niter_type
,
1129 build_int_cst (niter_type
, 1), bits
);
1130 s
= fold_binary_to_constant (RSHIFT_EXPR
, niter_type
, s
, bits
);
1132 if (!exit_must_be_taken
)
1134 /* If we cannot assume that the exit is taken eventually, record the
1135 assumptions for divisibility of c. */
1136 assumption
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, c
, d
);
1137 assumption
= fold_build2 (EQ_EXPR
, boolean_type_node
,
1138 assumption
, build_int_cst (niter_type
, 0));
1139 if (!integer_nonzerop (assumption
))
1140 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1141 niter
->assumptions
, assumption
);
1144 c
= fold_build2 (EXACT_DIV_EXPR
, niter_type
, c
, d
);
1145 if (integer_onep (s
))
1151 tmp
= fold_build2 (MULT_EXPR
, niter_type
, c
, inverse (s
, bound
));
1152 niter
->niter
= fold_build2 (BIT_AND_EXPR
, niter_type
, tmp
, bound
);
1157 /* Checks whether we can determine the final value of the control variable
1158 of the loop with ending condition IV0 < IV1 (computed in TYPE).
1159 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
1160 of the step. The assumptions necessary to ensure that the computation
1161 of the final value does not overflow are recorded in NITER. If we
1162 find the final value, we adjust DELTA and return TRUE. Otherwise
1163 we return false. BNDS bounds the value of IV1->base - IV0->base,
1164 and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
1165 true if we know that the exit must be taken eventually. */
1168 number_of_iterations_lt_to_ne (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1169 class tree_niter_desc
*niter
,
1170 tree
*delta
, tree step
,
1171 bool exit_must_be_taken
, bounds
*bnds
)
1173 tree niter_type
= TREE_TYPE (step
);
1174 tree mod
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, *delta
, step
);
1177 tree assumption
= boolean_true_node
, bound
, noloop
;
1178 bool ret
= false, fv_comp_no_overflow
;
1180 if (POINTER_TYPE_P (type
))
1183 if (TREE_CODE (mod
) != INTEGER_CST
)
1185 if (integer_nonzerop (mod
))
1186 mod
= fold_build2 (MINUS_EXPR
, niter_type
, step
, mod
);
1187 tmod
= fold_convert (type1
, mod
);
1190 wi::to_mpz (wi::to_wide (mod
), mmod
, UNSIGNED
);
1191 mpz_neg (mmod
, mmod
);
1193 /* If the induction variable does not overflow and the exit is taken,
1194 then the computation of the final value does not overflow. This is
1195 also obviously the case if the new final value is equal to the
1196 current one. Finally, we postulate this for pointer type variables,
1197 as the code cannot rely on the object to that the pointer points being
1198 placed at the end of the address space (and more pragmatically,
1199 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
1200 if (integer_zerop (mod
) || POINTER_TYPE_P (type
))
1201 fv_comp_no_overflow
= true;
1202 else if (!exit_must_be_taken
)
1203 fv_comp_no_overflow
= false;
1205 fv_comp_no_overflow
=
1206 (iv0
->no_overflow
&& integer_nonzerop (iv0
->step
))
1207 || (iv1
->no_overflow
&& integer_nonzerop (iv1
->step
));
1209 if (integer_nonzerop (iv0
->step
))
1211 /* The final value of the iv is iv1->base + MOD, assuming that this
1212 computation does not overflow, and that
1213 iv0->base <= iv1->base + MOD. */
1214 if (!fv_comp_no_overflow
)
1216 bound
= fold_build2 (MINUS_EXPR
, type1
,
1217 TYPE_MAX_VALUE (type1
), tmod
);
1218 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
1220 if (integer_zerop (assumption
))
1223 if (mpz_cmp (mmod
, bnds
->below
) < 0)
1224 noloop
= boolean_false_node
;
1225 else if (POINTER_TYPE_P (type
))
1226 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
1228 fold_build_pointer_plus (iv1
->base
, tmod
));
1230 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
1232 fold_build2 (PLUS_EXPR
, type1
,
1237 /* The final value of the iv is iv0->base - MOD, assuming that this
1238 computation does not overflow, and that
1239 iv0->base - MOD <= iv1->base. */
1240 if (!fv_comp_no_overflow
)
1242 bound
= fold_build2 (PLUS_EXPR
, type1
,
1243 TYPE_MIN_VALUE (type1
), tmod
);
1244 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
1246 if (integer_zerop (assumption
))
1249 if (mpz_cmp (mmod
, bnds
->below
) < 0)
1250 noloop
= boolean_false_node
;
1251 else if (POINTER_TYPE_P (type
))
1252 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
1253 fold_build_pointer_plus (iv0
->base
,
1254 fold_build1 (NEGATE_EXPR
,
1258 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
1259 fold_build2 (MINUS_EXPR
, type1
,
1264 if (!integer_nonzerop (assumption
))
1265 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1268 if (!integer_zerop (noloop
))
1269 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1272 bounds_add (bnds
, wi::to_widest (mod
), type
);
1273 *delta
= fold_build2 (PLUS_EXPR
, niter_type
, *delta
, mod
);
1281 /* Add assertions to NITER that ensure that the control variable of the loop
1282 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
1283 are TYPE. Returns false if we can prove that there is an overflow, true
1284 otherwise. STEP is the absolute value of the step. */
1287 assert_no_overflow_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1288 class tree_niter_desc
*niter
, tree step
)
1290 tree bound
, d
, assumption
, diff
;
1291 tree niter_type
= TREE_TYPE (step
);
1293 if (integer_nonzerop (iv0
->step
))
1295 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
1296 if (iv0
->no_overflow
)
1299 /* If iv0->base is a constant, we can determine the last value before
1300 overflow precisely; otherwise we conservatively assume
1303 if (TREE_CODE (iv0
->base
) == INTEGER_CST
)
1305 d
= fold_build2 (MINUS_EXPR
, niter_type
,
1306 fold_convert (niter_type
, TYPE_MAX_VALUE (type
)),
1307 fold_convert (niter_type
, iv0
->base
));
1308 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
1311 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
1312 build_int_cst (niter_type
, 1));
1313 bound
= fold_build2 (MINUS_EXPR
, type
,
1314 TYPE_MAX_VALUE (type
), fold_convert (type
, diff
));
1315 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
1320 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
1321 if (iv1
->no_overflow
)
1324 if (TREE_CODE (iv1
->base
) == INTEGER_CST
)
1326 d
= fold_build2 (MINUS_EXPR
, niter_type
,
1327 fold_convert (niter_type
, iv1
->base
),
1328 fold_convert (niter_type
, TYPE_MIN_VALUE (type
)));
1329 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
1332 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
1333 build_int_cst (niter_type
, 1));
1334 bound
= fold_build2 (PLUS_EXPR
, type
,
1335 TYPE_MIN_VALUE (type
), fold_convert (type
, diff
));
1336 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
1340 if (integer_zerop (assumption
))
1342 if (!integer_nonzerop (assumption
))
1343 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1344 niter
->assumptions
, assumption
);
1346 iv0
->no_overflow
= true;
1347 iv1
->no_overflow
= true;
1351 /* Add an assumption to NITER that a loop whose ending condition
1352 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
1353 bounds the value of IV1->base - IV0->base. */
1356 assert_loop_rolls_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1357 class tree_niter_desc
*niter
, bounds
*bnds
)
1359 tree assumption
= boolean_true_node
, bound
, diff
;
1360 tree mbz
, mbzl
, mbzr
, type1
;
1361 bool rolls_p
, no_overflow_p
;
1365 /* We are going to compute the number of iterations as
1366 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
1367 variant of TYPE. This formula only works if
1369 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
1371 (where MAX is the maximum value of the unsigned variant of TYPE, and
1372 the computations in this formula are performed in full precision,
1373 i.e., without overflows).
1375 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
1376 we have a condition of the form iv0->base - step < iv1->base before the loop,
1377 and for loops iv0->base < iv1->base - step * i the condition
1378 iv0->base < iv1->base + step, due to loop header copying, which enable us
1379 to prove the lower bound.
1381 The upper bound is more complicated. Unless the expressions for initial
1382 and final value themselves contain enough information, we usually cannot
1383 derive it from the context. */
1385 /* First check whether the answer does not follow from the bounds we gathered
1387 if (integer_nonzerop (iv0
->step
))
1388 dstep
= wi::to_widest (iv0
->step
);
1391 dstep
= wi::sext (wi::to_widest (iv1
->step
), TYPE_PRECISION (type
));
1396 wi::to_mpz (dstep
, mstep
, UNSIGNED
);
1397 mpz_neg (mstep
, mstep
);
1398 mpz_add_ui (mstep
, mstep
, 1);
1400 rolls_p
= mpz_cmp (mstep
, bnds
->below
) <= 0;
1403 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), max
, UNSIGNED
);
1404 mpz_add (max
, max
, mstep
);
1405 no_overflow_p
= (mpz_cmp (bnds
->up
, max
) <= 0
1406 /* For pointers, only values lying inside a single object
1407 can be compared or manipulated by pointer arithmetics.
1408 Gcc in general does not allow or handle objects larger
1409 than half of the address space, hence the upper bound
1410 is satisfied for pointers. */
1411 || POINTER_TYPE_P (type
));
1415 if (rolls_p
&& no_overflow_p
)
1419 if (POINTER_TYPE_P (type
))
1422 /* Now the hard part; we must formulate the assumption(s) as expressions, and
1423 we must be careful not to introduce overflow. */
1425 if (integer_nonzerop (iv0
->step
))
1427 diff
= fold_build2 (MINUS_EXPR
, type1
,
1428 iv0
->step
, build_int_cst (type1
, 1));
1430 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
1431 0 address never belongs to any object, we can assume this for
1433 if (!POINTER_TYPE_P (type
))
1435 bound
= fold_build2 (PLUS_EXPR
, type1
,
1436 TYPE_MIN_VALUE (type
), diff
);
1437 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
1441 /* And then we can compute iv0->base - diff, and compare it with
1443 mbzl
= fold_build2 (MINUS_EXPR
, type1
,
1444 fold_convert (type1
, iv0
->base
), diff
);
1445 mbzr
= fold_convert (type1
, iv1
->base
);
1449 diff
= fold_build2 (PLUS_EXPR
, type1
,
1450 iv1
->step
, build_int_cst (type1
, 1));
1452 if (!POINTER_TYPE_P (type
))
1454 bound
= fold_build2 (PLUS_EXPR
, type1
,
1455 TYPE_MAX_VALUE (type
), diff
);
1456 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
1460 mbzl
= fold_convert (type1
, iv0
->base
);
1461 mbzr
= fold_build2 (MINUS_EXPR
, type1
,
1462 fold_convert (type1
, iv1
->base
), diff
);
1465 if (!integer_nonzerop (assumption
))
1466 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1467 niter
->assumptions
, assumption
);
1470 mbz
= fold_build2 (GT_EXPR
, boolean_type_node
, mbzl
, mbzr
);
1471 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1472 niter
->may_be_zero
, mbz
);
1476 /* Determines number of iterations of loop whose ending condition
1477 is IV0 < IV1 which likes: {base, -C} < n, or n < {base, C}.
1478 The number of iterations is stored to NITER. */
1481 number_of_iterations_until_wrap (class loop
*, tree type
, affine_iv
*iv0
,
1482 affine_iv
*iv1
, class tree_niter_desc
*niter
)
1484 tree niter_type
= unsigned_type_for (type
);
1485 tree step
, num
, assumptions
, may_be_zero
, span
;
1486 wide_int high
, low
, max
, min
;
1488 may_be_zero
= fold_build2 (LE_EXPR
, boolean_type_node
, iv1
->base
, iv0
->base
);
1489 if (integer_onep (may_be_zero
))
1492 int prec
= TYPE_PRECISION (type
);
1493 signop sgn
= TYPE_SIGN (type
);
1494 min
= wi::min_value (prec
, sgn
);
1495 max
= wi::max_value (prec
, sgn
);
1497 /* n < {base, C}. */
1498 if (integer_zerop (iv0
->step
) && !tree_int_cst_sign_bit (iv1
->step
))
1501 /* MIN + C - 1 <= n. */
1502 tree last
= wide_int_to_tree (type
, min
+ wi::to_wide (step
) - 1);
1503 assumptions
= fold_build2 (LE_EXPR
, boolean_type_node
, last
, iv0
->base
);
1504 if (integer_zerop (assumptions
))
1507 num
= fold_build2 (MINUS_EXPR
, niter_type
, wide_int_to_tree (type
, max
),
1510 if (TREE_CODE (iv1
->base
) == INTEGER_CST
)
1511 low
= wi::to_wide (iv1
->base
) - 1;
1512 else if (TREE_CODE (iv0
->base
) == INTEGER_CST
)
1513 low
= wi::to_wide (iv0
->base
);
1517 /* {base, -C} < n. */
1518 else if (tree_int_cst_sign_bit (iv0
->step
) && integer_zerop (iv1
->step
))
1520 step
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (iv0
->step
), iv0
->step
);
1521 /* MAX - C + 1 >= n. */
1522 tree last
= wide_int_to_tree (type
, max
- wi::to_wide (step
) + 1);
1523 assumptions
= fold_build2 (GE_EXPR
, boolean_type_node
, last
, iv1
->base
);
1524 if (integer_zerop (assumptions
))
1527 num
= fold_build2 (MINUS_EXPR
, niter_type
, iv0
->base
,
1528 wide_int_to_tree (type
, min
));
1530 if (TREE_CODE (iv0
->base
) == INTEGER_CST
)
1531 high
= wi::to_wide (iv0
->base
) + 1;
1532 else if (TREE_CODE (iv1
->base
) == INTEGER_CST
)
1533 high
= wi::to_wide (iv1
->base
);
1540 /* (delta + step - 1) / step */
1541 step
= fold_convert (niter_type
, step
);
1542 num
= fold_convert (niter_type
, num
);
1543 num
= fold_build2 (PLUS_EXPR
, niter_type
, num
, step
);
1544 niter
->niter
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, num
, step
);
1546 widest_int delta
, s
;
1547 delta
= widest_int::from (high
, sgn
) - widest_int::from (low
, sgn
);
1548 s
= wi::to_widest (step
);
1549 delta
= delta
+ s
- 1;
1550 niter
->max
= wi::udiv_floor (delta
, s
);
1552 niter
->may_be_zero
= may_be_zero
;
1554 if (!integer_nonzerop (assumptions
))
1555 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1556 niter
->assumptions
, assumptions
);
1558 niter
->control
.no_overflow
= false;
1560 /* Update bound and exit condition as:
1561 bound = niter * STEP + (IVbase - STEP).
1562 { IVbase - STEP, +, STEP } != bound
1563 Here, biasing IVbase by 1 step makes 'bound' be the value before wrap.
1565 niter
->control
.base
= fold_build2 (MINUS_EXPR
, niter_type
,
1566 niter
->control
.base
, niter
->control
.step
);
1567 span
= fold_build2 (MULT_EXPR
, niter_type
, niter
->niter
,
1568 fold_convert (niter_type
, niter
->control
.step
));
1569 niter
->bound
= fold_build2 (PLUS_EXPR
, niter_type
, span
,
1570 fold_convert (niter_type
, niter
->control
.base
));
1571 niter
->bound
= fold_convert (type
, niter
->bound
);
1572 niter
->cmp
= NE_EXPR
;
1577 /* Determines number of iterations of loop whose ending condition
1578 is IV0 < IV1. TYPE is the type of the iv. The number of
1579 iterations is stored to NITER. BNDS bounds the difference
1580 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
1581 that the exit must be taken eventually. */
1584 number_of_iterations_lt (class loop
*loop
, tree type
, affine_iv
*iv0
,
1585 affine_iv
*iv1
, class tree_niter_desc
*niter
,
1586 bool exit_must_be_taken
, bounds
*bnds
)
1588 tree niter_type
= unsigned_type_for (type
);
1589 tree delta
, step
, s
;
1592 if (integer_nonzerop (iv0
->step
))
1594 niter
->control
= *iv0
;
1595 niter
->cmp
= LT_EXPR
;
1596 niter
->bound
= iv1
->base
;
1600 niter
->control
= *iv1
;
1601 niter
->cmp
= GT_EXPR
;
1602 niter
->bound
= iv0
->base
;
1605 /* {base, -C} < n, or n < {base, C} */
1606 if (tree_int_cst_sign_bit (iv0
->step
)
1607 || (!integer_zerop (iv1
->step
) && !tree_int_cst_sign_bit (iv1
->step
)))
1608 return number_of_iterations_until_wrap (loop
, type
, iv0
, iv1
, niter
);
1610 delta
= fold_build2 (MINUS_EXPR
, niter_type
,
1611 fold_convert (niter_type
, iv1
->base
),
1612 fold_convert (niter_type
, iv0
->base
));
1614 /* First handle the special case that the step is +-1. */
1615 if ((integer_onep (iv0
->step
) && integer_zerop (iv1
->step
))
1616 || (integer_all_onesp (iv1
->step
) && integer_zerop (iv0
->step
)))
1618 /* for (i = iv0->base; i < iv1->base; i++)
1622 for (i = iv1->base; i > iv0->base; i--).
1624 In both cases # of iterations is iv1->base - iv0->base, assuming that
1625 iv1->base >= iv0->base.
1627 First try to derive a lower bound on the value of
1628 iv1->base - iv0->base, computed in full precision. If the difference
1629 is nonnegative, we are done, otherwise we must record the
1632 if (mpz_sgn (bnds
->below
) < 0)
1633 niter
->may_be_zero
= fold_build2 (LT_EXPR
, boolean_type_node
,
1634 iv1
->base
, iv0
->base
);
1635 niter
->niter
= delta
;
1636 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, bnds
->up
, false),
1637 TYPE_SIGN (niter_type
));
1638 niter
->control
.no_overflow
= true;
1642 if (integer_nonzerop (iv0
->step
))
1643 step
= fold_convert (niter_type
, iv0
->step
);
1645 step
= fold_convert (niter_type
,
1646 fold_build1 (NEGATE_EXPR
, type
, iv1
->step
));
1648 /* If we can determine the final value of the control iv exactly, we can
1649 transform the condition to != comparison. In particular, this will be
1650 the case if DELTA is constant. */
1651 if (number_of_iterations_lt_to_ne (type
, iv0
, iv1
, niter
, &delta
, step
,
1652 exit_must_be_taken
, bnds
))
1656 zps
.base
= build_int_cst (niter_type
, 0);
1658 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1659 zps does not overflow. */
1660 zps
.no_overflow
= true;
1662 return number_of_iterations_ne (loop
, type
, &zps
,
1663 delta
, niter
, true, bnds
);
1666 /* Make sure that the control iv does not overflow. */
1667 if (!assert_no_overflow_lt (type
, iv0
, iv1
, niter
, step
))
1670 /* We determine the number of iterations as (delta + step - 1) / step. For
1671 this to work, we must know that iv1->base >= iv0->base - step + 1,
1672 otherwise the loop does not roll. */
1673 assert_loop_rolls_lt (type
, iv0
, iv1
, niter
, bnds
);
1675 s
= fold_build2 (MINUS_EXPR
, niter_type
,
1676 step
, build_int_cst (niter_type
, 1));
1677 delta
= fold_build2 (PLUS_EXPR
, niter_type
, delta
, s
);
1678 niter
->niter
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, delta
, step
);
1682 wi::to_mpz (wi::to_wide (step
), mstep
, UNSIGNED
);
1683 mpz_add (tmp
, bnds
->up
, mstep
);
1684 mpz_sub_ui (tmp
, tmp
, 1);
1685 mpz_fdiv_q (tmp
, tmp
, mstep
);
1686 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, tmp
, false),
1687 TYPE_SIGN (niter_type
));
1694 /* Determines number of iterations of loop whose ending condition
1695 is IV0 <= IV1. TYPE is the type of the iv. The number of
1696 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
1697 we know that this condition must eventually become false (we derived this
1698 earlier, and possibly set NITER->assumptions to make sure this
1699 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1702 number_of_iterations_le (class loop
*loop
, tree type
, affine_iv
*iv0
,
1703 affine_iv
*iv1
, class tree_niter_desc
*niter
,
1704 bool exit_must_be_taken
, bounds
*bnds
)
1708 if (POINTER_TYPE_P (type
))
1711 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1712 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1713 value of the type. This we must know anyway, since if it is
1714 equal to this value, the loop rolls forever. We do not check
1715 this condition for pointer type ivs, as the code cannot rely on
1716 the object to that the pointer points being placed at the end of
1717 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1718 not defined for pointers). */
1720 if (!exit_must_be_taken
&& !POINTER_TYPE_P (type
))
1722 if (integer_nonzerop (iv0
->step
))
1723 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1724 iv1
->base
, TYPE_MAX_VALUE (type
));
1726 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1727 iv0
->base
, TYPE_MIN_VALUE (type
));
1729 if (integer_zerop (assumption
))
1731 if (!integer_nonzerop (assumption
))
1732 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1733 niter
->assumptions
, assumption
);
1736 if (integer_nonzerop (iv0
->step
))
1738 if (POINTER_TYPE_P (type
))
1739 iv1
->base
= fold_build_pointer_plus_hwi (iv1
->base
, 1);
1741 iv1
->base
= fold_build2 (PLUS_EXPR
, type1
, iv1
->base
,
1742 build_int_cst (type1
, 1));
1744 else if (POINTER_TYPE_P (type
))
1745 iv0
->base
= fold_build_pointer_plus_hwi (iv0
->base
, -1);
1747 iv0
->base
= fold_build2 (MINUS_EXPR
, type1
,
1748 iv0
->base
, build_int_cst (type1
, 1));
1750 bounds_add (bnds
, 1, type1
);
1752 return number_of_iterations_lt (loop
, type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1756 /* Dumps description of affine induction variable IV to FILE. */
1759 dump_affine_iv (FILE *file
, affine_iv
*iv
)
1761 if (!integer_zerop (iv
->step
))
1762 fprintf (file
, "[");
1764 print_generic_expr (dump_file
, iv
->base
, TDF_SLIM
);
1766 if (!integer_zerop (iv
->step
))
1768 fprintf (file
, ", + , ");
1769 print_generic_expr (dump_file
, iv
->step
, TDF_SLIM
);
1770 fprintf (file
, "]%s", iv
->no_overflow
? "(no_overflow)" : "");
1774 /* Determine the number of iterations according to condition (for staying
1775 inside loop) which compares two induction variables using comparison
1776 operator CODE. The induction variable on left side of the comparison
1777 is IV0, the right-hand side is IV1. Both induction variables must have
1778 type TYPE, which must be an integer or pointer type. The steps of the
1779 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1781 LOOP is the loop whose number of iterations we are determining.
1783 ONLY_EXIT is true if we are sure this is the only way the loop could be
1784 exited (including possibly non-returning function calls, exceptions, etc.)
1785 -- in this case we can use the information whether the control induction
1786 variables can overflow or not in a more efficient way.
1788 if EVERY_ITERATION is true, we know the test is executed on every iteration.
1790 The results (number of iterations and assumptions as described in
1791 comments at class tree_niter_desc in tree-ssa-loop.h) are stored to NITER.
1792 Returns false if it fails to determine number of iterations, true if it
1793 was determined (possibly with some assumptions). */
1796 number_of_iterations_cond (class loop
*loop
,
1797 tree type
, affine_iv
*iv0
, enum tree_code code
,
1798 affine_iv
*iv1
, class tree_niter_desc
*niter
,
1799 bool only_exit
, bool every_iteration
)
1801 bool exit_must_be_taken
= false, ret
;
1804 /* If the test is not executed every iteration, wrapping may make the test
1806 TODO: the overflow case can be still used as unreliable estimate of upper
1807 bound. But we have no API to pass it down to number of iterations code
1808 and, at present, it will not use it anyway. */
1809 if (!every_iteration
1810 && (!iv0
->no_overflow
|| !iv1
->no_overflow
1811 || code
== NE_EXPR
|| code
== EQ_EXPR
))
1814 /* The meaning of these assumptions is this:
1816 then the rest of information does not have to be valid
1817 if may_be_zero then the loop does not roll, even if
1819 niter
->assumptions
= boolean_true_node
;
1820 niter
->may_be_zero
= boolean_false_node
;
1821 niter
->niter
= NULL_TREE
;
1823 niter
->bound
= NULL_TREE
;
1824 niter
->cmp
= ERROR_MARK
;
1826 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1827 the control variable is on lhs. */
1828 if (code
== GE_EXPR
|| code
== GT_EXPR
1829 || (code
== NE_EXPR
&& integer_zerop (iv0
->step
)))
1831 std::swap (iv0
, iv1
);
1832 code
= swap_tree_comparison (code
);
1835 if (POINTER_TYPE_P (type
))
1837 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1838 to the same object. If they do, the control variable cannot wrap
1839 (as wrap around the bounds of memory will never return a pointer
1840 that would be guaranteed to point to the same object, even if we
1841 avoid undefined behavior by casting to size_t and back). */
1842 iv0
->no_overflow
= true;
1843 iv1
->no_overflow
= true;
1846 /* If the control induction variable does not overflow and the only exit
1847 from the loop is the one that we analyze, we know it must be taken
1851 if (!integer_zerop (iv0
->step
) && iv0
->no_overflow
)
1852 exit_must_be_taken
= true;
1853 else if (!integer_zerop (iv1
->step
) && iv1
->no_overflow
)
1854 exit_must_be_taken
= true;
1857 /* We can handle cases which neither of the sides of the comparison is
1860 {iv0.base, iv0.step} cmp_code {iv1.base, iv1.step}
1862 {iv0.base, iv0.step - iv1.step} cmp_code {iv1.base, 0}
1864 provided that either below condition is satisfied:
1866 a) the test is NE_EXPR;
1867 b) iv0.step - iv1.step is integer and iv0/iv1 don't overflow.
1869 This rarely occurs in practice, but it is simple enough to manage. */
1870 if (!integer_zerop (iv0
->step
) && !integer_zerop (iv1
->step
))
1872 tree step_type
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1873 tree step
= fold_binary_to_constant (MINUS_EXPR
, step_type
,
1874 iv0
->step
, iv1
->step
);
1876 /* No need to check sign of the new step since below code takes care
1879 && (TREE_CODE (step
) != INTEGER_CST
1880 || !iv0
->no_overflow
|| !iv1
->no_overflow
))
1884 if (!POINTER_TYPE_P (type
))
1885 iv0
->no_overflow
= false;
1887 iv1
->step
= build_int_cst (step_type
, 0);
1888 iv1
->no_overflow
= true;
1891 /* If the result of the comparison is a constant, the loop is weird. More
1892 precise handling would be possible, but the situation is not common enough
1893 to waste time on it. */
1894 if (integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
))
1897 /* If the loop exits immediately, there is nothing to do. */
1898 tree tem
= fold_binary (code
, boolean_type_node
, iv0
->base
, iv1
->base
);
1899 if (tem
&& integer_zerop (tem
))
1901 if (!every_iteration
)
1903 niter
->niter
= build_int_cst (unsigned_type_for (type
), 0);
1908 /* OK, now we know we have a senseful loop. Handle several cases, depending
1909 on what comparison operator is used. */
1910 bound_difference (loop
, iv1
->base
, iv0
->base
, &bnds
);
1912 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1915 "Analyzing # of iterations of loop %d\n", loop
->num
);
1917 fprintf (dump_file
, " exit condition ");
1918 dump_affine_iv (dump_file
, iv0
);
1919 fprintf (dump_file
, " %s ",
1920 code
== NE_EXPR
? "!="
1921 : code
== LT_EXPR
? "<"
1923 dump_affine_iv (dump_file
, iv1
);
1924 fprintf (dump_file
, "\n");
1926 fprintf (dump_file
, " bounds on difference of bases: ");
1927 mpz_out_str (dump_file
, 10, bnds
.below
);
1928 fprintf (dump_file
, " ... ");
1929 mpz_out_str (dump_file
, 10, bnds
.up
);
1930 fprintf (dump_file
, "\n");
1936 gcc_assert (integer_zerop (iv1
->step
));
1937 ret
= number_of_iterations_ne (loop
, type
, iv0
, iv1
->base
, niter
,
1938 exit_must_be_taken
, &bnds
);
1942 ret
= number_of_iterations_lt (loop
, type
, iv0
, iv1
, niter
,
1943 exit_must_be_taken
, &bnds
);
1947 ret
= number_of_iterations_le (loop
, type
, iv0
, iv1
, niter
,
1948 exit_must_be_taken
, &bnds
);
1955 mpz_clear (bnds
.up
);
1956 mpz_clear (bnds
.below
);
1958 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1962 fprintf (dump_file
, " result:\n");
1963 if (!integer_nonzerop (niter
->assumptions
))
1965 fprintf (dump_file
, " under assumptions ");
1966 print_generic_expr (dump_file
, niter
->assumptions
, TDF_SLIM
);
1967 fprintf (dump_file
, "\n");
1970 if (!integer_zerop (niter
->may_be_zero
))
1972 fprintf (dump_file
, " zero if ");
1973 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
1974 fprintf (dump_file
, "\n");
1977 fprintf (dump_file
, " # of iterations ");
1978 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
1979 fprintf (dump_file
, ", bounded by ");
1980 print_decu (niter
->max
, dump_file
);
1981 fprintf (dump_file
, "\n");
1984 fprintf (dump_file
, " failed\n\n");
1989 /* Substitute NEW_TREE for OLD in EXPR and fold the result.
1990 If VALUEIZE is non-NULL then OLD and NEW_TREE are ignored and instead
1991 all SSA names are replaced with the result of calling the VALUEIZE
1992 function with the SSA name as argument. */
1995 simplify_replace_tree (tree expr
, tree old
, tree new_tree
,
1996 tree (*valueize
) (tree
, void*), void *context
,
2000 tree ret
= NULL_TREE
, e
, se
;
2005 /* Do not bother to replace constants. */
2006 if (CONSTANT_CLASS_P (expr
))
2011 if (TREE_CODE (expr
) == SSA_NAME
)
2013 new_tree
= valueize (expr
, context
);
2014 if (new_tree
!= expr
)
2018 else if (expr
== old
2019 || operand_equal_p (expr
, old
, 0))
2020 return unshare_expr (new_tree
);
2025 n
= TREE_OPERAND_LENGTH (expr
);
2026 for (i
= 0; i
< n
; i
++)
2028 e
= TREE_OPERAND (expr
, i
);
2029 se
= simplify_replace_tree (e
, old
, new_tree
, valueize
, context
, do_fold
);
2034 ret
= copy_node (expr
);
2036 TREE_OPERAND (ret
, i
) = se
;
2039 return (ret
? (do_fold
? fold (ret
) : ret
) : expr
);
2042 /* Expand definitions of ssa names in EXPR as long as they are simple
2043 enough, and return the new expression. If STOP is specified, stop
2044 expanding if EXPR equals to it. */
2047 expand_simple_operations (tree expr
, tree stop
, hash_map
<tree
, tree
> &cache
)
2050 tree ret
= NULL_TREE
, e
, ee
, e1
;
2051 enum tree_code code
;
2054 if (expr
== NULL_TREE
)
2057 if (is_gimple_min_invariant (expr
))
2060 code
= TREE_CODE (expr
);
2061 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
2063 n
= TREE_OPERAND_LENGTH (expr
);
2064 for (i
= 0; i
< n
; i
++)
2066 e
= TREE_OPERAND (expr
, i
);
2067 /* SCEV analysis feeds us with a proper expression
2068 graph matching the SSA graph. Avoid turning it
2069 into a tree here, thus handle tree sharing
2071 ??? The SSA walk below still turns the SSA graph
2072 into a tree but until we find a testcase do not
2073 introduce additional tree sharing here. */
2075 tree
&cee
= cache
.get_or_insert (e
, &existed_p
);
2081 ee
= expand_simple_operations (e
, stop
, cache
);
2083 *cache
.get (e
) = ee
;
2089 ret
= copy_node (expr
);
2091 TREE_OPERAND (ret
, i
) = ee
;
2097 fold_defer_overflow_warnings ();
2099 fold_undefer_and_ignore_overflow_warnings ();
2103 /* Stop if it's not ssa name or the one we don't want to expand. */
2104 if (TREE_CODE (expr
) != SSA_NAME
|| expr
== stop
)
2107 stmt
= SSA_NAME_DEF_STMT (expr
);
2108 if (gimple_code (stmt
) == GIMPLE_PHI
)
2110 basic_block src
, dest
;
2112 if (gimple_phi_num_args (stmt
) != 1)
2114 e
= PHI_ARG_DEF (stmt
, 0);
2116 /* Avoid propagating through loop exit phi nodes, which
2117 could break loop-closed SSA form restrictions. */
2118 dest
= gimple_bb (stmt
);
2119 src
= single_pred (dest
);
2120 if (TREE_CODE (e
) == SSA_NAME
2121 && src
->loop_father
!= dest
->loop_father
)
2124 return expand_simple_operations (e
, stop
, cache
);
2126 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2129 /* Avoid expanding to expressions that contain SSA names that need
2130 to take part in abnormal coalescing. */
2132 FOR_EACH_SSA_TREE_OPERAND (e
, stmt
, iter
, SSA_OP_USE
)
2133 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (e
))
2136 e
= gimple_assign_rhs1 (stmt
);
2137 code
= gimple_assign_rhs_code (stmt
);
2138 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
2140 if (is_gimple_min_invariant (e
))
2143 if (code
== SSA_NAME
)
2144 return expand_simple_operations (e
, stop
, cache
);
2145 else if (code
== ADDR_EXPR
)
2148 tree base
= get_addr_base_and_unit_offset (TREE_OPERAND (e
, 0),
2151 && TREE_CODE (base
) == MEM_REF
)
2153 ee
= expand_simple_operations (TREE_OPERAND (base
, 0), stop
,
2155 return fold_build2 (POINTER_PLUS_EXPR
, TREE_TYPE (expr
), ee
,
2156 wide_int_to_tree (sizetype
,
2157 mem_ref_offset (base
)
2168 /* Casts are simple. */
2169 ee
= expand_simple_operations (e
, stop
, cache
);
2170 return fold_build1 (code
, TREE_TYPE (expr
), ee
);
2174 if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (expr
))
2175 && TYPE_OVERFLOW_TRAPS (TREE_TYPE (expr
)))
2178 case POINTER_PLUS_EXPR
:
2179 /* And increments and decrements by a constant are simple. */
2180 e1
= gimple_assign_rhs2 (stmt
);
2181 if (!is_gimple_min_invariant (e1
))
2184 ee
= expand_simple_operations (e
, stop
, cache
);
2185 return fold_build2 (code
, TREE_TYPE (expr
), ee
, e1
);
2193 expand_simple_operations (tree expr
, tree stop
)
2195 hash_map
<tree
, tree
> cache
;
2196 return expand_simple_operations (expr
, stop
, cache
);
2199 /* Tries to simplify EXPR using the condition COND. Returns the simplified
2200 expression (or EXPR unchanged, if no simplification was possible). */
2203 tree_simplify_using_condition_1 (tree cond
, tree expr
)
2206 tree e
, e0
, e1
, e2
, notcond
;
2207 enum tree_code code
= TREE_CODE (expr
);
2209 if (code
== INTEGER_CST
)
2212 if (code
== TRUTH_OR_EXPR
2213 || code
== TRUTH_AND_EXPR
2214 || code
== COND_EXPR
)
2218 e0
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 0));
2219 if (TREE_OPERAND (expr
, 0) != e0
)
2222 e1
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 1));
2223 if (TREE_OPERAND (expr
, 1) != e1
)
2226 if (code
== COND_EXPR
)
2228 e2
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 2));
2229 if (TREE_OPERAND (expr
, 2) != e2
)
2237 if (code
== COND_EXPR
)
2238 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
2240 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
2246 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
2247 propagation, and vice versa. Fold does not handle this, since it is
2248 considered too expensive. */
2249 if (TREE_CODE (cond
) == EQ_EXPR
)
2251 e0
= TREE_OPERAND (cond
, 0);
2252 e1
= TREE_OPERAND (cond
, 1);
2254 /* We know that e0 == e1. Check whether we cannot simplify expr
2256 e
= simplify_replace_tree (expr
, e0
, e1
);
2257 if (integer_zerop (e
) || integer_nonzerop (e
))
2260 e
= simplify_replace_tree (expr
, e1
, e0
);
2261 if (integer_zerop (e
) || integer_nonzerop (e
))
2264 if (TREE_CODE (expr
) == EQ_EXPR
)
2266 e0
= TREE_OPERAND (expr
, 0);
2267 e1
= TREE_OPERAND (expr
, 1);
2269 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
2270 e
= simplify_replace_tree (cond
, e0
, e1
);
2271 if (integer_zerop (e
))
2273 e
= simplify_replace_tree (cond
, e1
, e0
);
2274 if (integer_zerop (e
))
2277 if (TREE_CODE (expr
) == NE_EXPR
)
2279 e0
= TREE_OPERAND (expr
, 0);
2280 e1
= TREE_OPERAND (expr
, 1);
2282 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
2283 e
= simplify_replace_tree (cond
, e0
, e1
);
2284 if (integer_zerop (e
))
2285 return boolean_true_node
;
2286 e
= simplify_replace_tree (cond
, e1
, e0
);
2287 if (integer_zerop (e
))
2288 return boolean_true_node
;
2291 /* Check whether COND ==> EXPR. */
2292 notcond
= invert_truthvalue (cond
);
2293 e
= fold_binary (TRUTH_OR_EXPR
, boolean_type_node
, notcond
, expr
);
2294 if (e
&& integer_nonzerop (e
))
2297 /* Check whether COND ==> not EXPR. */
2298 e
= fold_binary (TRUTH_AND_EXPR
, boolean_type_node
, cond
, expr
);
2299 if (e
&& integer_zerop (e
))
2305 /* Tries to simplify EXPR using the condition COND. Returns the simplified
2306 expression (or EXPR unchanged, if no simplification was possible).
2307 Wrapper around tree_simplify_using_condition_1 that ensures that chains
2308 of simple operations in definitions of ssa names in COND are expanded,
2309 so that things like casts or incrementing the value of the bound before
2310 the loop do not cause us to fail. */
2313 tree_simplify_using_condition (tree cond
, tree expr
)
2315 cond
= expand_simple_operations (cond
);
2317 return tree_simplify_using_condition_1 (cond
, expr
);
2320 /* Tries to simplify EXPR using the conditions on entry to LOOP.
2321 Returns the simplified expression (or EXPR unchanged, if no
2322 simplification was possible). */
2325 simplify_using_initial_conditions (class loop
*loop
, tree expr
)
2330 tree cond
, expanded
, backup
;
2333 if (TREE_CODE (expr
) == INTEGER_CST
)
2336 backup
= expanded
= expand_simple_operations (expr
);
2338 /* Limit walking the dominators to avoid quadraticness in
2339 the number of BBs times the number of loops in degenerate
2341 for (bb
= loop
->header
;
2342 bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && cnt
< MAX_DOMINATORS_TO_WALK
;
2343 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
2345 if (!single_pred_p (bb
))
2347 e
= single_pred_edge (bb
);
2349 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
2352 stmt
= last_stmt (e
->src
);
2353 cond
= fold_build2 (gimple_cond_code (stmt
),
2355 gimple_cond_lhs (stmt
),
2356 gimple_cond_rhs (stmt
));
2357 if (e
->flags
& EDGE_FALSE_VALUE
)
2358 cond
= invert_truthvalue (cond
);
2359 expanded
= tree_simplify_using_condition (cond
, expanded
);
2360 /* Break if EXPR is simplified to const values. */
2362 && (integer_zerop (expanded
) || integer_nonzerop (expanded
)))
2368 /* Return the original expression if no simplification is done. */
2369 return operand_equal_p (backup
, expanded
, 0) ? expr
: expanded
;
2372 /* Tries to simplify EXPR using the evolutions of the loop invariants
2373 in the superloops of LOOP. Returns the simplified expression
2374 (or EXPR unchanged, if no simplification was possible). */
2377 simplify_using_outer_evolutions (class loop
*loop
, tree expr
)
2379 enum tree_code code
= TREE_CODE (expr
);
2383 if (is_gimple_min_invariant (expr
))
2386 if (code
== TRUTH_OR_EXPR
2387 || code
== TRUTH_AND_EXPR
2388 || code
== COND_EXPR
)
2392 e0
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 0));
2393 if (TREE_OPERAND (expr
, 0) != e0
)
2396 e1
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 1));
2397 if (TREE_OPERAND (expr
, 1) != e1
)
2400 if (code
== COND_EXPR
)
2402 e2
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 2));
2403 if (TREE_OPERAND (expr
, 2) != e2
)
2411 if (code
== COND_EXPR
)
2412 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
2414 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
2420 e
= instantiate_parameters (loop
, expr
);
2421 if (is_gimple_min_invariant (e
))
2427 /* Returns true if EXIT is the only possible exit from LOOP. */
2430 loop_only_exit_p (const class loop
*loop
, basic_block
*body
, const_edge exit
)
2432 gimple_stmt_iterator bsi
;
2435 if (exit
!= single_exit (loop
))
2438 for (i
= 0; i
< loop
->num_nodes
; i
++)
2439 for (bsi
= gsi_start_bb (body
[i
]); !gsi_end_p (bsi
); gsi_next (&bsi
))
2440 if (stmt_can_terminate_bb_p (gsi_stmt (bsi
)))
2446 /* Stores description of number of iterations of LOOP derived from
2447 EXIT (an exit edge of the LOOP) in NITER. Returns true if some useful
2448 information could be derived (and fields of NITER have meaning described
2449 in comments at class tree_niter_desc declaration), false otherwise.
2450 When EVERY_ITERATION is true, only tests that are known to be executed
2451 every iteration are considered (i.e. only test that alone bounds the loop).
2452 If AT_STMT is not NULL, this function stores LOOP's condition statement in
2453 it when returning true. */
2456 number_of_iterations_exit_assumptions (class loop
*loop
, edge exit
,
2457 class tree_niter_desc
*niter
,
2458 gcond
**at_stmt
, bool every_iteration
,
2465 enum tree_code code
;
2469 /* The condition at a fake exit (if it exists) does not control its
2471 if (exit
->flags
& EDGE_FAKE
)
2474 /* Nothing to analyze if the loop is known to be infinite. */
2475 if (loop_constraint_set_p (loop
, LOOP_C_INFINITE
))
2478 safe
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit
->src
);
2480 if (every_iteration
&& !safe
)
2483 niter
->assumptions
= boolean_false_node
;
2484 niter
->control
.base
= NULL_TREE
;
2485 niter
->control
.step
= NULL_TREE
;
2486 niter
->control
.no_overflow
= false;
2487 last
= last_stmt (exit
->src
);
2490 stmt
= dyn_cast
<gcond
*> (last
);
2494 /* We want the condition for staying inside loop. */
2495 code
= gimple_cond_code (stmt
);
2496 if (exit
->flags
& EDGE_TRUE_VALUE
)
2497 code
= invert_tree_comparison (code
, false);
2512 op0
= gimple_cond_lhs (stmt
);
2513 op1
= gimple_cond_rhs (stmt
);
2514 type
= TREE_TYPE (op0
);
2516 if (TREE_CODE (type
) != INTEGER_TYPE
2517 && !POINTER_TYPE_P (type
))
2520 tree iv0_niters
= NULL_TREE
;
2521 if (!simple_iv_with_niters (loop
, loop_containing_stmt (stmt
),
2522 op0
, &iv0
, safe
? &iv0_niters
: NULL
, false))
2523 return number_of_iterations_popcount (loop
, exit
, code
, niter
);
2524 tree iv1_niters
= NULL_TREE
;
2525 if (!simple_iv_with_niters (loop
, loop_containing_stmt (stmt
),
2526 op1
, &iv1
, safe
? &iv1_niters
: NULL
, false))
2528 /* Give up on complicated case. */
2529 if (iv0_niters
&& iv1_niters
)
2532 /* We don't want to see undefined signed overflow warnings while
2533 computing the number of iterations. */
2534 fold_defer_overflow_warnings ();
2536 iv0
.base
= expand_simple_operations (iv0
.base
);
2537 iv1
.base
= expand_simple_operations (iv1
.base
);
2538 bool body_from_caller
= true;
2541 body
= get_loop_body (loop
);
2542 body_from_caller
= false;
2544 bool only_exit_p
= loop_only_exit_p (loop
, body
, exit
);
2545 if (!body_from_caller
)
2547 if (!number_of_iterations_cond (loop
, type
, &iv0
, code
, &iv1
, niter
,
2550 fold_undefer_and_ignore_overflow_warnings ();
2554 /* Incorporate additional assumption implied by control iv. */
2555 tree iv_niters
= iv0_niters
? iv0_niters
: iv1_niters
;
2558 tree assumption
= fold_build2 (LE_EXPR
, boolean_type_node
, niter
->niter
,
2559 fold_convert (TREE_TYPE (niter
->niter
),
2562 if (!integer_nonzerop (assumption
))
2563 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
2564 niter
->assumptions
, assumption
);
2566 /* Refine upper bound if possible. */
2567 if (TREE_CODE (iv_niters
) == INTEGER_CST
2568 && niter
->max
> wi::to_widest (iv_niters
))
2569 niter
->max
= wi::to_widest (iv_niters
);
2572 /* There is no assumptions if the loop is known to be finite. */
2573 if (!integer_zerop (niter
->assumptions
)
2574 && loop_constraint_set_p (loop
, LOOP_C_FINITE
))
2575 niter
->assumptions
= boolean_true_node
;
2579 niter
->assumptions
= simplify_using_outer_evolutions (loop
,
2580 niter
->assumptions
);
2581 niter
->may_be_zero
= simplify_using_outer_evolutions (loop
,
2582 niter
->may_be_zero
);
2583 niter
->niter
= simplify_using_outer_evolutions (loop
, niter
->niter
);
2587 = simplify_using_initial_conditions (loop
,
2588 niter
->assumptions
);
2590 = simplify_using_initial_conditions (loop
,
2591 niter
->may_be_zero
);
2593 fold_undefer_and_ignore_overflow_warnings ();
2595 /* If NITER has simplified into a constant, update MAX. */
2596 if (TREE_CODE (niter
->niter
) == INTEGER_CST
)
2597 niter
->max
= wi::to_widest (niter
->niter
);
2602 return (!integer_zerop (niter
->assumptions
));
2606 /* Utility function to check if OP is defined by a stmt
2607 that is a val - 1. */
2610 ssa_defined_by_minus_one_stmt_p (tree op
, tree val
)
2613 return (TREE_CODE (op
) == SSA_NAME
2614 && (stmt
= SSA_NAME_DEF_STMT (op
))
2615 && is_gimple_assign (stmt
)
2616 && (gimple_assign_rhs_code (stmt
) == PLUS_EXPR
)
2617 && val
== gimple_assign_rhs1 (stmt
)
2618 && integer_minus_onep (gimple_assign_rhs2 (stmt
)));
2622 /* See if LOOP is a popcout implementation, determine NITER for the loop
2633 b_11 = PHI <b_5(D)(2), b_6(3)>
2641 OR we match copy-header version:
2648 b_11 = PHI <b_5(2), b_6(3)>
2658 If popcount pattern, update NITER accordingly.
2659 i.e., set NITER to __builtin_popcount (b)
2660 return true if we did, false otherwise.
2665 number_of_iterations_popcount (loop_p loop
, edge exit
,
2666 enum tree_code code
,
2667 class tree_niter_desc
*niter
)
2673 tree fn
= NULL_TREE
;
2675 /* Check loop terminating branch is like
2677 gimple
*stmt
= last_stmt (exit
->src
);
2679 || gimple_code (stmt
) != GIMPLE_COND
2681 || !integer_zerop (gimple_cond_rhs (stmt
))
2682 || TREE_CODE (gimple_cond_lhs (stmt
)) != SSA_NAME
)
2685 gimple
*and_stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt
));
2687 /* Depending on copy-header is performed, feeding PHI stmts might be in
2688 the loop header or loop latch, handle this. */
2689 if (gimple_code (and_stmt
) == GIMPLE_PHI
2690 && gimple_bb (and_stmt
) == loop
->header
2691 && gimple_phi_num_args (and_stmt
) == 2
2692 && (TREE_CODE (gimple_phi_arg_def (and_stmt
,
2693 loop_latch_edge (loop
)->dest_idx
))
2696 /* SSA used in exit condition is defined by PHI stmt
2697 b_11 = PHI <b_5(D)(2), b_6(3)>
2698 from the PHI stmt, get the and_stmt
2700 tree t
= gimple_phi_arg_def (and_stmt
, loop_latch_edge (loop
)->dest_idx
);
2701 and_stmt
= SSA_NAME_DEF_STMT (t
);
2705 /* Make sure it is indeed an and stmt (b_6 = _1 & b_11). */
2706 if (!is_gimple_assign (and_stmt
)
2707 || gimple_assign_rhs_code (and_stmt
) != BIT_AND_EXPR
)
2710 tree b_11
= gimple_assign_rhs1 (and_stmt
);
2711 tree _1
= gimple_assign_rhs2 (and_stmt
);
2713 /* Check that _1 is defined by _b11 + -1 (_1 = b_11 + -1).
2714 Also make sure that b_11 is the same in and_stmt and _1 defining stmt.
2715 Also canonicalize if _1 and _b11 are revrsed. */
2716 if (ssa_defined_by_minus_one_stmt_p (b_11
, _1
))
2717 std::swap (b_11
, _1
);
2718 else if (ssa_defined_by_minus_one_stmt_p (_1
, b_11
))
2722 /* Check the recurrence:
2723 ... = PHI <b_5(2), b_6(3)>. */
2724 gimple
*phi
= SSA_NAME_DEF_STMT (b_11
);
2725 if (gimple_code (phi
) != GIMPLE_PHI
2726 || (gimple_bb (phi
) != loop_latch_edge (loop
)->dest
)
2727 || (gimple_assign_lhs (and_stmt
)
2728 != gimple_phi_arg_def (phi
, loop_latch_edge (loop
)->dest_idx
)))
2731 /* We found a match. Get the corresponding popcount builtin. */
2732 tree src
= gimple_phi_arg_def (phi
, loop_preheader_edge (loop
)->dest_idx
);
2733 if (TYPE_PRECISION (TREE_TYPE (src
)) <= TYPE_PRECISION (integer_type_node
))
2734 fn
= builtin_decl_implicit (BUILT_IN_POPCOUNT
);
2735 else if (TYPE_PRECISION (TREE_TYPE (src
))
2736 == TYPE_PRECISION (long_integer_type_node
))
2737 fn
= builtin_decl_implicit (BUILT_IN_POPCOUNTL
);
2738 else if (TYPE_PRECISION (TREE_TYPE (src
))
2739 == TYPE_PRECISION (long_long_integer_type_node
)
2740 || (TYPE_PRECISION (TREE_TYPE (src
))
2741 == 2 * TYPE_PRECISION (long_long_integer_type_node
)))
2742 fn
= builtin_decl_implicit (BUILT_IN_POPCOUNTLL
);
2747 /* Update NITER params accordingly */
2748 tree utype
= unsigned_type_for (TREE_TYPE (src
));
2749 src
= fold_convert (utype
, src
);
2750 if (TYPE_PRECISION (TREE_TYPE (src
)) < TYPE_PRECISION (integer_type_node
))
2751 src
= fold_convert (unsigned_type_node
, src
);
2753 if (TYPE_PRECISION (TREE_TYPE (src
))
2754 == 2 * TYPE_PRECISION (long_long_integer_type_node
))
2756 int prec
= TYPE_PRECISION (long_long_integer_type_node
);
2757 tree src1
= fold_convert (long_long_unsigned_type_node
,
2758 fold_build2 (RSHIFT_EXPR
, TREE_TYPE (src
),
2760 build_int_cst (integer_type_node
,
2762 tree src2
= fold_convert (long_long_unsigned_type_node
, src
);
2763 call
= build_call_expr (fn
, 1, src1
);
2764 call
= fold_build2 (PLUS_EXPR
, TREE_TYPE (call
), call
,
2765 build_call_expr (fn
, 1, src2
));
2766 call
= fold_convert (utype
, call
);
2769 call
= fold_convert (utype
, build_call_expr (fn
, 1, src
));
2771 iter
= fold_build2 (MINUS_EXPR
, utype
, call
, build_int_cst (utype
, 1));
2775 if (TREE_CODE (call
) == INTEGER_CST
)
2776 max
= tree_to_uhwi (call
);
2778 max
= TYPE_PRECISION (TREE_TYPE (src
));
2782 niter
->niter
= iter
;
2783 niter
->assumptions
= boolean_true_node
;
2787 tree may_be_zero
= fold_build2 (EQ_EXPR
, boolean_type_node
, src
,
2788 build_zero_cst (TREE_TYPE (src
)));
2790 = simplify_using_initial_conditions (loop
, may_be_zero
);
2793 niter
->may_be_zero
= boolean_false_node
;
2796 niter
->bound
= NULL_TREE
;
2797 niter
->cmp
= ERROR_MARK
;
2802 /* Like number_of_iterations_exit_assumptions, but return TRUE only if
2803 the niter information holds unconditionally. */
2806 number_of_iterations_exit (class loop
*loop
, edge exit
,
2807 class tree_niter_desc
*niter
,
2808 bool warn
, bool every_iteration
,
2812 if (!number_of_iterations_exit_assumptions (loop
, exit
, niter
,
2813 &stmt
, every_iteration
, body
))
2816 if (integer_nonzerop (niter
->assumptions
))
2819 if (warn
&& dump_enabled_p ())
2820 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, stmt
,
2821 "missed loop optimization: niters analysis ends up "
2822 "with assumptions.\n");
2827 /* Try to determine the number of iterations of LOOP. If we succeed,
2828 expression giving number of iterations is returned and *EXIT is
2829 set to the edge from that the information is obtained. Otherwise
2830 chrec_dont_know is returned. */
2833 find_loop_niter (class loop
*loop
, edge
*exit
)
2836 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
);
2838 tree niter
= NULL_TREE
, aniter
;
2839 class tree_niter_desc desc
;
2842 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2844 if (!number_of_iterations_exit (loop
, ex
, &desc
, false))
2847 if (integer_nonzerop (desc
.may_be_zero
))
2849 /* We exit in the first iteration through this exit.
2850 We won't find anything better. */
2851 niter
= build_int_cst (unsigned_type_node
, 0);
2856 if (!integer_zerop (desc
.may_be_zero
))
2859 aniter
= desc
.niter
;
2863 /* Nothing recorded yet. */
2869 /* Prefer constants, the lower the better. */
2870 if (TREE_CODE (aniter
) != INTEGER_CST
)
2873 if (TREE_CODE (niter
) != INTEGER_CST
)
2880 if (tree_int_cst_lt (aniter
, niter
))
2888 return niter
? niter
: chrec_dont_know
;
2891 /* Return true if loop is known to have bounded number of iterations. */
2894 finite_loop_p (class loop
*loop
)
2899 flags
= flags_from_decl_or_type (current_function_decl
);
2900 if ((flags
& (ECF_CONST
|ECF_PURE
)) && !(flags
& ECF_LOOPING_CONST_OR_PURE
))
2902 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2903 fprintf (dump_file
, "Found loop %i to be finite: it is within pure or const function.\n",
2908 if (loop
->any_upper_bound
2909 || max_loop_iterations (loop
, &nit
))
2911 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2912 fprintf (dump_file
, "Found loop %i to be finite: upper bound found.\n",
2920 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
);
2923 /* If the loop has a normal exit, we can assume it will terminate. */
2924 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2925 if (!(ex
->flags
& (EDGE_EH
| EDGE_ABNORMAL
| EDGE_FAKE
)))
2928 fprintf (dump_file
, "Assume loop %i to be finite: it has an exit "
2929 "and -ffinite-loops is on.\n", loop
->num
);
2939 Analysis of a number of iterations of a loop by a brute-force evaluation.
2943 /* Bound on the number of iterations we try to evaluate. */
2945 #define MAX_ITERATIONS_TO_TRACK \
2946 ((unsigned) param_max_iterations_to_track)
2948 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
2949 result by a chain of operations such that all but exactly one of their
2950 operands are constants. */
2953 chain_of_csts_start (class loop
*loop
, tree x
)
2955 gimple
*stmt
= SSA_NAME_DEF_STMT (x
);
2957 basic_block bb
= gimple_bb (stmt
);
2958 enum tree_code code
;
2961 || !flow_bb_inside_loop_p (loop
, bb
))
2964 if (gimple_code (stmt
) == GIMPLE_PHI
)
2966 if (bb
== loop
->header
)
2967 return as_a
<gphi
*> (stmt
);
2972 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2973 || gimple_assign_rhs_class (stmt
) == GIMPLE_TERNARY_RHS
)
2976 code
= gimple_assign_rhs_code (stmt
);
2977 if (gimple_references_memory_p (stmt
)
2978 || TREE_CODE_CLASS (code
) == tcc_reference
2979 || (code
== ADDR_EXPR
2980 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
2983 use
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
2984 if (use
== NULL_TREE
)
2987 return chain_of_csts_start (loop
, use
);
2990 /* Determines whether the expression X is derived from a result of a phi node
2991 in header of LOOP such that
2993 * the derivation of X consists only from operations with constants
2994 * the initial value of the phi node is constant
2995 * the value of the phi node in the next iteration can be derived from the
2996 value in the current iteration by a chain of operations with constants,
2997 or is also a constant
2999 If such phi node exists, it is returned, otherwise NULL is returned. */
3002 get_base_for (class loop
*loop
, tree x
)
3007 if (is_gimple_min_invariant (x
))
3010 phi
= chain_of_csts_start (loop
, x
);
3014 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
3015 next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
3017 if (!is_gimple_min_invariant (init
))
3020 if (TREE_CODE (next
) == SSA_NAME
3021 && chain_of_csts_start (loop
, next
) != phi
)
3027 /* Given an expression X, then
3029 * if X is NULL_TREE, we return the constant BASE.
3030 * if X is a constant, we return the constant X.
3031 * otherwise X is a SSA name, whose value in the considered loop is derived
3032 by a chain of operations with constant from a result of a phi node in
3033 the header of the loop. Then we return value of X when the value of the
3034 result of this phi node is given by the constant BASE. */
3037 get_val_for (tree x
, tree base
)
3041 gcc_checking_assert (is_gimple_min_invariant (base
));
3045 else if (is_gimple_min_invariant (x
))
3048 stmt
= SSA_NAME_DEF_STMT (x
);
3049 if (gimple_code (stmt
) == GIMPLE_PHI
)
3052 gcc_checking_assert (is_gimple_assign (stmt
));
3054 /* STMT must be either an assignment of a single SSA name or an
3055 expression involving an SSA name and a constant. Try to fold that
3056 expression using the value for the SSA name. */
3057 if (gimple_assign_ssa_name_copy_p (stmt
))
3058 return get_val_for (gimple_assign_rhs1 (stmt
), base
);
3059 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_UNARY_RHS
3060 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
3061 return fold_build1 (gimple_assign_rhs_code (stmt
),
3062 TREE_TYPE (gimple_assign_lhs (stmt
)),
3063 get_val_for (gimple_assign_rhs1 (stmt
), base
));
3064 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_BINARY_RHS
)
3066 tree rhs1
= gimple_assign_rhs1 (stmt
);
3067 tree rhs2
= gimple_assign_rhs2 (stmt
);
3068 if (TREE_CODE (rhs1
) == SSA_NAME
)
3069 rhs1
= get_val_for (rhs1
, base
);
3070 else if (TREE_CODE (rhs2
) == SSA_NAME
)
3071 rhs2
= get_val_for (rhs2
, base
);
3074 return fold_build2 (gimple_assign_rhs_code (stmt
),
3075 TREE_TYPE (gimple_assign_lhs (stmt
)), rhs1
, rhs2
);
3082 /* Tries to count the number of iterations of LOOP till it exits by EXIT
3083 by brute force -- i.e. by determining the value of the operands of the
3084 condition at EXIT in first few iterations of the loop (assuming that
3085 these values are constant) and determining the first one in that the
3086 condition is not satisfied. Returns the constant giving the number
3087 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
3090 loop_niter_by_eval (class loop
*loop
, edge exit
)
3093 tree op
[2], val
[2], next
[2], aval
[2];
3099 cond
= last_stmt (exit
->src
);
3100 if (!cond
|| gimple_code (cond
) != GIMPLE_COND
)
3101 return chrec_dont_know
;
3103 cmp
= gimple_cond_code (cond
);
3104 if (exit
->flags
& EDGE_TRUE_VALUE
)
3105 cmp
= invert_tree_comparison (cmp
, false);
3115 op
[0] = gimple_cond_lhs (cond
);
3116 op
[1] = gimple_cond_rhs (cond
);
3120 return chrec_dont_know
;
3123 for (j
= 0; j
< 2; j
++)
3125 if (is_gimple_min_invariant (op
[j
]))
3128 next
[j
] = NULL_TREE
;
3133 phi
= get_base_for (loop
, op
[j
]);
3135 return chrec_dont_know
;
3136 val
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
3137 next
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
3141 /* Don't issue signed overflow warnings. */
3142 fold_defer_overflow_warnings ();
3144 for (i
= 0; i
< MAX_ITERATIONS_TO_TRACK
; i
++)
3146 for (j
= 0; j
< 2; j
++)
3147 aval
[j
] = get_val_for (op
[j
], val
[j
]);
3149 acnd
= fold_binary (cmp
, boolean_type_node
, aval
[0], aval
[1]);
3150 if (acnd
&& integer_zerop (acnd
))
3152 fold_undefer_and_ignore_overflow_warnings ();
3153 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3155 "Proved that loop %d iterates %d times using brute force.\n",
3157 return build_int_cst (unsigned_type_node
, i
);
3160 for (j
= 0; j
< 2; j
++)
3163 val
[j
] = get_val_for (next
[j
], val
[j
]);
3164 if (!is_gimple_min_invariant (val
[j
]))
3166 fold_undefer_and_ignore_overflow_warnings ();
3167 return chrec_dont_know
;
3171 /* If the next iteration would use the same base values
3172 as the current one, there is no point looping further,
3173 all following iterations will be the same as this one. */
3174 if (val
[0] == aval
[0] && val
[1] == aval
[1])
3178 fold_undefer_and_ignore_overflow_warnings ();
3180 return chrec_dont_know
;
3183 /* Finds the exit of the LOOP by that the loop exits after a constant
3184 number of iterations and stores the exit edge to *EXIT. The constant
3185 giving the number of iterations of LOOP is returned. The number of
3186 iterations is determined using loop_niter_by_eval (i.e. by brute force
3187 evaluation). If we are unable to find the exit for that loop_niter_by_eval
3188 determines the number of iterations, chrec_dont_know is returned. */
3191 find_loop_niter_by_eval (class loop
*loop
, edge
*exit
)
3194 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
);
3196 tree niter
= NULL_TREE
, aniter
;
3200 /* Loops with multiple exits are expensive to handle and less important. */
3201 if (!flag_expensive_optimizations
3202 && exits
.length () > 1)
3203 return chrec_dont_know
;
3205 FOR_EACH_VEC_ELT (exits
, i
, ex
)
3207 if (!just_once_each_iteration_p (loop
, ex
->src
))
3210 aniter
= loop_niter_by_eval (loop
, ex
);
3211 if (chrec_contains_undetermined (aniter
))
3215 && !tree_int_cst_lt (aniter
, niter
))
3222 return niter
? niter
: chrec_dont_know
;
3227 Analysis of upper bounds on number of iterations of a loop.
3231 static widest_int
derive_constant_upper_bound_ops (tree
, tree
,
3232 enum tree_code
, tree
);
3234 /* Returns a constant upper bound on the value of the right-hand side of
3235 an assignment statement STMT. */
3238 derive_constant_upper_bound_assign (gimple
*stmt
)
3240 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3241 tree op0
= gimple_assign_rhs1 (stmt
);
3242 tree op1
= gimple_assign_rhs2 (stmt
);
3244 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt
)),
3248 /* Returns a constant upper bound on the value of expression VAL. VAL
3249 is considered to be unsigned. If its type is signed, its value must
3253 derive_constant_upper_bound (tree val
)
3255 enum tree_code code
;
3258 extract_ops_from_tree (val
, &code
, &op0
, &op1
, &op2
);
3259 return derive_constant_upper_bound_ops (TREE_TYPE (val
), op0
, code
, op1
);
3262 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
3263 whose type is TYPE. The expression is considered to be unsigned. If
3264 its type is signed, its value must be nonnegative. */
3267 derive_constant_upper_bound_ops (tree type
, tree op0
,
3268 enum tree_code code
, tree op1
)
3271 widest_int bnd
, max
, cst
;
3274 if (INTEGRAL_TYPE_P (type
))
3275 maxt
= TYPE_MAX_VALUE (type
);
3277 maxt
= upper_bound_in_type (type
, type
);
3279 max
= wi::to_widest (maxt
);
3284 return wi::to_widest (op0
);
3287 subtype
= TREE_TYPE (op0
);
3288 if (!TYPE_UNSIGNED (subtype
)
3289 /* If TYPE is also signed, the fact that VAL is nonnegative implies
3290 that OP0 is nonnegative. */
3291 && TYPE_UNSIGNED (type
)
3292 && !tree_expr_nonnegative_p (op0
))
3294 /* If we cannot prove that the casted expression is nonnegative,
3295 we cannot establish more useful upper bound than the precision
3296 of the type gives us. */
3300 /* We now know that op0 is an nonnegative value. Try deriving an upper
3302 bnd
= derive_constant_upper_bound (op0
);
3304 /* If the bound does not fit in TYPE, max. value of TYPE could be
3306 if (wi::ltu_p (max
, bnd
))
3312 case POINTER_PLUS_EXPR
:
3314 if (TREE_CODE (op1
) != INTEGER_CST
3315 || !tree_expr_nonnegative_p (op0
))
3318 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
3319 choose the most logical way how to treat this constant regardless
3320 of the signedness of the type. */
3321 cst
= wi::sext (wi::to_widest (op1
), TYPE_PRECISION (type
));
3322 if (code
!= MINUS_EXPR
)
3325 bnd
= derive_constant_upper_bound (op0
);
3327 if (wi::neg_p (cst
))
3330 /* Avoid CST == 0x80000... */
3331 if (wi::neg_p (cst
))
3334 /* OP0 + CST. We need to check that
3335 BND <= MAX (type) - CST. */
3337 widest_int mmax
= max
- cst
;
3338 if (wi::leu_p (bnd
, mmax
))
3345 /* OP0 - CST, where CST >= 0.
3347 If TYPE is signed, we have already verified that OP0 >= 0, and we
3348 know that the result is nonnegative. This implies that
3351 If TYPE is unsigned, we must additionally know that OP0 >= CST,
3352 otherwise the operation underflows.
3355 /* This should only happen if the type is unsigned; however, for
3356 buggy programs that use overflowing signed arithmetics even with
3357 -fno-wrapv, this condition may also be true for signed values. */
3358 if (wi::ltu_p (bnd
, cst
))
3361 if (TYPE_UNSIGNED (type
))
3363 tree tem
= fold_binary (GE_EXPR
, boolean_type_node
, op0
,
3364 wide_int_to_tree (type
, cst
));
3365 if (!tem
|| integer_nonzerop (tem
))
3374 case FLOOR_DIV_EXPR
:
3375 case EXACT_DIV_EXPR
:
3376 if (TREE_CODE (op1
) != INTEGER_CST
3377 || tree_int_cst_sign_bit (op1
))
3380 bnd
= derive_constant_upper_bound (op0
);
3381 return wi::udiv_floor (bnd
, wi::to_widest (op1
));
3384 if (TREE_CODE (op1
) != INTEGER_CST
3385 || tree_int_cst_sign_bit (op1
))
3387 return wi::to_widest (op1
);
3390 stmt
= SSA_NAME_DEF_STMT (op0
);
3391 if (gimple_code (stmt
) != GIMPLE_ASSIGN
3392 || gimple_assign_lhs (stmt
) != op0
)
3394 return derive_constant_upper_bound_assign (stmt
);
3401 /* Emit a -Waggressive-loop-optimizations warning if needed. */
3404 do_warn_aggressive_loop_optimizations (class loop
*loop
,
3405 widest_int i_bound
, gimple
*stmt
)
3407 /* Don't warn if the loop doesn't have known constant bound. */
3408 if (!loop
->nb_iterations
3409 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
3410 || !warn_aggressive_loop_optimizations
3411 /* To avoid warning multiple times for the same loop,
3412 only start warning when we preserve loops. */
3413 || (cfun
->curr_properties
& PROP_loops
) == 0
3414 /* Only warn once per loop. */
3415 || loop
->warned_aggressive_loop_optimizations
3416 /* Only warn if undefined behavior gives us lower estimate than the
3417 known constant bound. */
3418 || wi::cmpu (i_bound
, wi::to_widest (loop
->nb_iterations
)) >= 0
3419 /* And undefined behavior happens unconditionally. */
3420 || !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (stmt
)))
3423 edge e
= single_exit (loop
);
3427 gimple
*estmt
= last_stmt (e
->src
);
3428 char buf
[WIDE_INT_PRINT_BUFFER_SIZE
];
3429 print_dec (i_bound
, buf
, TYPE_UNSIGNED (TREE_TYPE (loop
->nb_iterations
))
3430 ? UNSIGNED
: SIGNED
);
3431 auto_diagnostic_group d
;
3432 if (warning_at (gimple_location (stmt
), OPT_Waggressive_loop_optimizations
,
3433 "iteration %s invokes undefined behavior", buf
))
3434 inform (gimple_location (estmt
), "within this loop");
3435 loop
->warned_aggressive_loop_optimizations
= true;
3438 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
3439 is true if the loop is exited immediately after STMT, and this exit
3440 is taken at last when the STMT is executed BOUND + 1 times.
3441 REALISTIC is true if BOUND is expected to be close to the real number
3442 of iterations. UPPER is true if we are sure the loop iterates at most
3443 BOUND times. I_BOUND is a widest_int upper estimate on BOUND. */
3446 record_estimate (class loop
*loop
, tree bound
, const widest_int
&i_bound
,
3447 gimple
*at_stmt
, bool is_exit
, bool realistic
, bool upper
)
3451 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3453 fprintf (dump_file
, "Statement %s", is_exit
? "(exit)" : "");
3454 print_gimple_stmt (dump_file
, at_stmt
, 0, TDF_SLIM
);
3455 fprintf (dump_file
, " is %sexecuted at most ",
3456 upper
? "" : "probably ");
3457 print_generic_expr (dump_file
, bound
, TDF_SLIM
);
3458 fprintf (dump_file
, " (bounded by ");
3459 print_decu (i_bound
, dump_file
);
3460 fprintf (dump_file
, ") + 1 times in loop %d.\n", loop
->num
);
3463 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
3464 real number of iterations. */
3465 if (TREE_CODE (bound
) != INTEGER_CST
)
3468 gcc_checking_assert (i_bound
== wi::to_widest (bound
));
3470 /* If we have a guaranteed upper bound, record it in the appropriate
3471 list, unless this is an !is_exit bound (i.e. undefined behavior in
3472 at_stmt) in a loop with known constant number of iterations. */
3475 || loop
->nb_iterations
== NULL_TREE
3476 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
))
3478 class nb_iter_bound
*elt
= ggc_alloc
<nb_iter_bound
> ();
3480 elt
->bound
= i_bound
;
3481 elt
->stmt
= at_stmt
;
3482 elt
->is_exit
= is_exit
;
3483 elt
->next
= loop
->bounds
;
3487 /* If statement is executed on every path to the loop latch, we can directly
3488 infer the upper bound on the # of iterations of the loop. */
3489 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (at_stmt
)))
3492 /* Update the number of iteration estimates according to the bound.
3493 If at_stmt is an exit then the loop latch is executed at most BOUND times,
3494 otherwise it can be executed BOUND + 1 times. We will lower the estimate
3495 later if such statement must be executed on last iteration */
3500 widest_int new_i_bound
= i_bound
+ delta
;
3502 /* If an overflow occurred, ignore the result. */
3503 if (wi::ltu_p (new_i_bound
, delta
))
3506 if (upper
&& !is_exit
)
3507 do_warn_aggressive_loop_optimizations (loop
, new_i_bound
, at_stmt
);
3508 record_niter_bound (loop
, new_i_bound
, realistic
, upper
);
3511 /* Records the control iv analyzed in NITER for LOOP if the iv is valid
3512 and doesn't overflow. */
3515 record_control_iv (class loop
*loop
, class tree_niter_desc
*niter
)
3517 struct control_iv
*iv
;
3519 if (!niter
->control
.base
|| !niter
->control
.step
)
3522 if (!integer_onep (niter
->assumptions
) || !niter
->control
.no_overflow
)
3525 iv
= ggc_alloc
<control_iv
> ();
3526 iv
->base
= niter
->control
.base
;
3527 iv
->step
= niter
->control
.step
;
3528 iv
->next
= loop
->control_ivs
;
3529 loop
->control_ivs
= iv
;
3534 /* This function returns TRUE if below conditions are satisfied:
3535 1) VAR is SSA variable.
3536 2) VAR is an IV:{base, step} in its defining loop.
3537 3) IV doesn't overflow.
3538 4) Both base and step are integer constants.
3539 5) Base is the MIN/MAX value depends on IS_MIN.
3540 Store value of base to INIT correspondingly. */
3543 get_cst_init_from_scev (tree var
, wide_int
*init
, bool is_min
)
3545 if (TREE_CODE (var
) != SSA_NAME
)
3548 gimple
*def_stmt
= SSA_NAME_DEF_STMT (var
);
3549 class loop
*loop
= loop_containing_stmt (def_stmt
);
3555 if (!simple_iv (loop
, loop
, var
, &iv
, false))
3558 if (!iv
.no_overflow
)
3561 if (TREE_CODE (iv
.base
) != INTEGER_CST
|| TREE_CODE (iv
.step
) != INTEGER_CST
)
3564 if (is_min
== tree_int_cst_sign_bit (iv
.step
))
3567 *init
= wi::to_wide (iv
.base
);
3571 /* Record the estimate on number of iterations of LOOP based on the fact that
3572 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
3573 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
3574 estimated number of iterations is expected to be close to the real one.
3575 UPPER is true if we are sure the induction variable does not wrap. */
3578 record_nonwrapping_iv (class loop
*loop
, tree base
, tree step
, gimple
*stmt
,
3579 tree low
, tree high
, bool realistic
, bool upper
)
3581 tree niter_bound
, extreme
, delta
;
3582 tree type
= TREE_TYPE (base
), unsigned_type
;
3583 tree orig_base
= base
;
3585 if (TREE_CODE (step
) != INTEGER_CST
|| integer_zerop (step
))
3588 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3590 fprintf (dump_file
, "Induction variable (");
3591 print_generic_expr (dump_file
, TREE_TYPE (base
), TDF_SLIM
);
3592 fprintf (dump_file
, ") ");
3593 print_generic_expr (dump_file
, base
, TDF_SLIM
);
3594 fprintf (dump_file
, " + ");
3595 print_generic_expr (dump_file
, step
, TDF_SLIM
);
3596 fprintf (dump_file
, " * iteration does not wrap in statement ");
3597 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3598 fprintf (dump_file
, " in loop %d.\n", loop
->num
);
3601 unsigned_type
= unsigned_type_for (type
);
3602 base
= fold_convert (unsigned_type
, base
);
3603 step
= fold_convert (unsigned_type
, step
);
3605 if (tree_int_cst_sign_bit (step
))
3608 value_range base_range
;
3609 if (get_range_query (cfun
)->range_of_expr (base_range
, orig_base
)
3610 && !base_range
.undefined_p ())
3611 max
= base_range
.upper_bound ();
3612 extreme
= fold_convert (unsigned_type
, low
);
3613 if (TREE_CODE (orig_base
) == SSA_NAME
3614 && TREE_CODE (high
) == INTEGER_CST
3615 && INTEGRAL_TYPE_P (TREE_TYPE (orig_base
))
3616 && (base_range
.kind () == VR_RANGE
3617 || get_cst_init_from_scev (orig_base
, &max
, false))
3618 && wi::gts_p (wi::to_wide (high
), max
))
3619 base
= wide_int_to_tree (unsigned_type
, max
);
3620 else if (TREE_CODE (base
) != INTEGER_CST
3621 && dominated_by_p (CDI_DOMINATORS
,
3622 loop
->latch
, gimple_bb (stmt
)))
3623 base
= fold_convert (unsigned_type
, high
);
3624 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
3625 step
= fold_build1 (NEGATE_EXPR
, unsigned_type
, step
);
3630 value_range base_range
;
3631 if (get_range_query (cfun
)->range_of_expr (base_range
, orig_base
)
3632 && !base_range
.undefined_p ())
3633 min
= base_range
.lower_bound ();
3634 extreme
= fold_convert (unsigned_type
, high
);
3635 if (TREE_CODE (orig_base
) == SSA_NAME
3636 && TREE_CODE (low
) == INTEGER_CST
3637 && INTEGRAL_TYPE_P (TREE_TYPE (orig_base
))
3638 && (base_range
.kind () == VR_RANGE
3639 || get_cst_init_from_scev (orig_base
, &min
, true))
3640 && wi::gts_p (min
, wi::to_wide (low
)))
3641 base
= wide_int_to_tree (unsigned_type
, min
);
3642 else if (TREE_CODE (base
) != INTEGER_CST
3643 && dominated_by_p (CDI_DOMINATORS
,
3644 loop
->latch
, gimple_bb (stmt
)))
3645 base
= fold_convert (unsigned_type
, low
);
3646 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
3649 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
3650 would get out of the range. */
3651 niter_bound
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step
);
3652 widest_int max
= derive_constant_upper_bound (niter_bound
);
3653 record_estimate (loop
, niter_bound
, max
, stmt
, false, realistic
, upper
);
3656 /* Determine information about number of iterations a LOOP from the index
3657 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
3658 guaranteed to be executed in every iteration of LOOP. Callback for
3668 idx_infer_loop_bounds (tree base
, tree
*idx
, void *dta
)
3670 struct ilb_data
*data
= (struct ilb_data
*) dta
;
3671 tree ev
, init
, step
;
3672 tree low
, high
, type
, next
;
3673 bool sign
, upper
= true, at_end
= false;
3674 class loop
*loop
= data
->loop
;
3676 if (TREE_CODE (base
) != ARRAY_REF
)
3679 /* For arrays at the end of the structure, we are not guaranteed that they
3680 do not really extend over their declared size. However, for arrays of
3681 size greater than one, this is unlikely to be intended. */
3682 if (array_at_struct_end_p (base
))
3688 class loop
*dloop
= loop_containing_stmt (data
->stmt
);
3692 ev
= analyze_scalar_evolution (dloop
, *idx
);
3693 ev
= instantiate_parameters (loop
, ev
);
3694 init
= initial_condition (ev
);
3695 step
= evolution_part_in_loop_num (ev
, loop
->num
);
3699 || TREE_CODE (step
) != INTEGER_CST
3700 || integer_zerop (step
)
3701 || tree_contains_chrecs (init
, NULL
)
3702 || chrec_contains_symbols_defined_in_loop (init
, loop
->num
))
3705 low
= array_ref_low_bound (base
);
3706 high
= array_ref_up_bound (base
);
3708 /* The case of nonconstant bounds could be handled, but it would be
3710 if (TREE_CODE (low
) != INTEGER_CST
3712 || TREE_CODE (high
) != INTEGER_CST
)
3714 sign
= tree_int_cst_sign_bit (step
);
3715 type
= TREE_TYPE (step
);
3717 /* The array of length 1 at the end of a structure most likely extends
3718 beyond its bounds. */
3720 && operand_equal_p (low
, high
, 0))
3723 /* In case the relevant bound of the array does not fit in type, or
3724 it does, but bound + step (in type) still belongs into the range of the
3725 array, the index may wrap and still stay within the range of the array
3726 (consider e.g. if the array is indexed by the full range of
3729 To make things simpler, we require both bounds to fit into type, although
3730 there are cases where this would not be strictly necessary. */
3731 if (!int_fits_type_p (high
, type
)
3732 || !int_fits_type_p (low
, type
))
3734 low
= fold_convert (type
, low
);
3735 high
= fold_convert (type
, high
);
3738 next
= fold_binary (PLUS_EXPR
, type
, low
, step
);
3740 next
= fold_binary (PLUS_EXPR
, type
, high
, step
);
3742 if (tree_int_cst_compare (low
, next
) <= 0
3743 && tree_int_cst_compare (next
, high
) <= 0)
3746 /* If access is not executed on every iteration, we must ensure that overlow
3747 may not make the access valid later. */
3748 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (data
->stmt
))
3749 && scev_probably_wraps_p (NULL_TREE
,
3750 initial_condition_in_loop_num (ev
, loop
->num
),
3751 step
, data
->stmt
, loop
, true))
3754 record_nonwrapping_iv (loop
, init
, step
, data
->stmt
, low
, high
, false, upper
);
3758 /* Determine information about number of iterations a LOOP from the bounds
3759 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
3760 STMT is guaranteed to be executed in every iteration of LOOP.*/
3763 infer_loop_bounds_from_ref (class loop
*loop
, gimple
*stmt
, tree ref
)
3765 struct ilb_data data
;
3769 for_each_index (&ref
, idx_infer_loop_bounds
, &data
);
3772 /* Determine information about number of iterations of a LOOP from the way
3773 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
3774 executed in every iteration of LOOP. */
3777 infer_loop_bounds_from_array (class loop
*loop
, gimple
*stmt
)
3779 if (is_gimple_assign (stmt
))
3781 tree op0
= gimple_assign_lhs (stmt
);
3782 tree op1
= gimple_assign_rhs1 (stmt
);
3784 /* For each memory access, analyze its access function
3785 and record a bound on the loop iteration domain. */
3786 if (REFERENCE_CLASS_P (op0
))
3787 infer_loop_bounds_from_ref (loop
, stmt
, op0
);
3789 if (REFERENCE_CLASS_P (op1
))
3790 infer_loop_bounds_from_ref (loop
, stmt
, op1
);
3792 else if (is_gimple_call (stmt
))
3795 unsigned i
, n
= gimple_call_num_args (stmt
);
3797 lhs
= gimple_call_lhs (stmt
);
3798 if (lhs
&& REFERENCE_CLASS_P (lhs
))
3799 infer_loop_bounds_from_ref (loop
, stmt
, lhs
);
3801 for (i
= 0; i
< n
; i
++)
3803 arg
= gimple_call_arg (stmt
, i
);
3804 if (REFERENCE_CLASS_P (arg
))
3805 infer_loop_bounds_from_ref (loop
, stmt
, arg
);
3810 /* Determine information about number of iterations of a LOOP from the fact
3811 that pointer arithmetics in STMT does not overflow. */
3814 infer_loop_bounds_from_pointer_arith (class loop
*loop
, gimple
*stmt
)
3816 tree def
, base
, step
, scev
, type
, low
, high
;
3819 if (!is_gimple_assign (stmt
)
3820 || gimple_assign_rhs_code (stmt
) != POINTER_PLUS_EXPR
)
3823 def
= gimple_assign_lhs (stmt
);
3824 if (TREE_CODE (def
) != SSA_NAME
)
3827 type
= TREE_TYPE (def
);
3828 if (!nowrap_type_p (type
))
3831 ptr
= gimple_assign_rhs1 (stmt
);
3832 if (!expr_invariant_in_loop_p (loop
, ptr
))
3835 var
= gimple_assign_rhs2 (stmt
);
3836 if (TYPE_PRECISION (type
) != TYPE_PRECISION (TREE_TYPE (var
)))
3839 class loop
*uloop
= loop_containing_stmt (stmt
);
3840 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (uloop
, def
));
3841 if (chrec_contains_undetermined (scev
))
3844 base
= initial_condition_in_loop_num (scev
, loop
->num
);
3845 step
= evolution_part_in_loop_num (scev
, loop
->num
);
3848 || TREE_CODE (step
) != INTEGER_CST
3849 || tree_contains_chrecs (base
, NULL
)
3850 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
3853 low
= lower_bound_in_type (type
, type
);
3854 high
= upper_bound_in_type (type
, type
);
3856 /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
3857 produce a NULL pointer. The contrary would mean NULL points to an object,
3858 while NULL is supposed to compare unequal with the address of all objects.
3859 Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
3860 NULL pointer since that would mean wrapping, which we assume here not to
3861 happen. So, we can exclude NULL from the valid range of pointer
3863 if (flag_delete_null_pointer_checks
&& int_cst_value (low
) == 0)
3864 low
= build_int_cstu (TREE_TYPE (low
), TYPE_ALIGN_UNIT (TREE_TYPE (type
)));
3866 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
3869 /* Determine information about number of iterations of a LOOP from the fact
3870 that signed arithmetics in STMT does not overflow. */
3873 infer_loop_bounds_from_signedness (class loop
*loop
, gimple
*stmt
)
3875 tree def
, base
, step
, scev
, type
, low
, high
;
3877 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
3880 def
= gimple_assign_lhs (stmt
);
3882 if (TREE_CODE (def
) != SSA_NAME
)
3885 type
= TREE_TYPE (def
);
3886 if (!INTEGRAL_TYPE_P (type
)
3887 || !TYPE_OVERFLOW_UNDEFINED (type
))
3890 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
3891 if (chrec_contains_undetermined (scev
))
3894 base
= initial_condition_in_loop_num (scev
, loop
->num
);
3895 step
= evolution_part_in_loop_num (scev
, loop
->num
);
3898 || TREE_CODE (step
) != INTEGER_CST
3899 || tree_contains_chrecs (base
, NULL
)
3900 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
3903 low
= lower_bound_in_type (type
, type
);
3904 high
= upper_bound_in_type (type
, type
);
3906 get_range_query (cfun
)->range_of_expr (r
, def
);
3907 if (r
.kind () == VR_RANGE
)
3909 low
= wide_int_to_tree (type
, r
.lower_bound ());
3910 high
= wide_int_to_tree (type
, r
.upper_bound ());
3913 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
3916 /* The following analyzers are extracting informations on the bounds
3917 of LOOP from the following undefined behaviors:
3919 - data references should not access elements over the statically
3922 - signed variables should not overflow when flag_wrapv is not set.
3926 infer_loop_bounds_from_undefined (class loop
*loop
, basic_block
*bbs
)
3929 gimple_stmt_iterator bsi
;
3933 for (i
= 0; i
< loop
->num_nodes
; i
++)
3937 /* If BB is not executed in each iteration of the loop, we cannot
3938 use the operations in it to infer reliable upper bound on the
3939 # of iterations of the loop. However, we can use it as a guess.
3940 Reliable guesses come only from array bounds. */
3941 reliable
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
);
3943 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
3945 gimple
*stmt
= gsi_stmt (bsi
);
3947 infer_loop_bounds_from_array (loop
, stmt
);
3951 infer_loop_bounds_from_signedness (loop
, stmt
);
3952 infer_loop_bounds_from_pointer_arith (loop
, stmt
);
3959 /* Compare wide ints, callback for qsort. */
3962 wide_int_cmp (const void *p1
, const void *p2
)
3964 const widest_int
*d1
= (const widest_int
*) p1
;
3965 const widest_int
*d2
= (const widest_int
*) p2
;
3966 return wi::cmpu (*d1
, *d2
);
3969 /* Return index of BOUND in BOUNDS array sorted in increasing order.
3970 Lookup by binary search. */
3973 bound_index (const vec
<widest_int
> &bounds
, const widest_int
&bound
)
3975 unsigned int end
= bounds
.length ();
3976 unsigned int begin
= 0;
3978 /* Find a matching index by means of a binary search. */
3979 while (begin
!= end
)
3981 unsigned int middle
= (begin
+ end
) / 2;
3982 widest_int index
= bounds
[middle
];
3986 else if (wi::ltu_p (index
, bound
))
3994 /* We recorded loop bounds only for statements dominating loop latch (and thus
3995 executed each loop iteration). If there are any bounds on statements not
3996 dominating the loop latch we can improve the estimate by walking the loop
3997 body and seeing if every path from loop header to loop latch contains
3998 some bounded statement. */
4001 discover_iteration_bound_by_body_walk (class loop
*loop
)
4003 class nb_iter_bound
*elt
;
4004 auto_vec
<widest_int
> bounds
;
4005 vec
<vec
<basic_block
> > queues
= vNULL
;
4006 vec
<basic_block
> queue
= vNULL
;
4007 ptrdiff_t queue_index
;
4008 ptrdiff_t latch_index
= 0;
4010 /* Discover what bounds may interest us. */
4011 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
4013 widest_int bound
= elt
->bound
;
4015 /* Exit terminates loop at given iteration, while non-exits produce undefined
4016 effect on the next iteration. */
4020 /* If an overflow occurred, ignore the result. */
4025 if (!loop
->any_upper_bound
4026 || wi::ltu_p (bound
, loop
->nb_iterations_upper_bound
))
4027 bounds
.safe_push (bound
);
4030 /* Exit early if there is nothing to do. */
4031 if (!bounds
.exists ())
4034 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4035 fprintf (dump_file
, " Trying to walk loop body to reduce the bound.\n");
4037 /* Sort the bounds in decreasing order. */
4038 bounds
.qsort (wide_int_cmp
);
4040 /* For every basic block record the lowest bound that is guaranteed to
4041 terminate the loop. */
4043 hash_map
<basic_block
, ptrdiff_t> bb_bounds
;
4044 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
4046 widest_int bound
= elt
->bound
;
4050 /* If an overflow occurred, ignore the result. */
4055 if (!loop
->any_upper_bound
4056 || wi::ltu_p (bound
, loop
->nb_iterations_upper_bound
))
4058 ptrdiff_t index
= bound_index (bounds
, bound
);
4059 ptrdiff_t *entry
= bb_bounds
.get (gimple_bb (elt
->stmt
));
4061 bb_bounds
.put (gimple_bb (elt
->stmt
), index
);
4062 else if ((ptrdiff_t)*entry
> index
)
4067 hash_map
<basic_block
, ptrdiff_t> block_priority
;
4069 /* Perform shortest path discovery loop->header ... loop->latch.
4071 The "distance" is given by the smallest loop bound of basic block
4072 present in the path and we look for path with largest smallest bound
4075 To avoid the need for fibonacci heap on double ints we simply compress
4076 double ints into indexes to BOUNDS array and then represent the queue
4077 as arrays of queues for every index.
4078 Index of BOUNDS.length() means that the execution of given BB has
4079 no bounds determined.
4081 VISITED is a pointer map translating basic block into smallest index
4082 it was inserted into the priority queue with. */
4085 /* Start walk in loop header with index set to infinite bound. */
4086 queue_index
= bounds
.length ();
4087 queues
.safe_grow_cleared (queue_index
+ 1, true);
4088 queue
.safe_push (loop
->header
);
4089 queues
[queue_index
] = queue
;
4090 block_priority
.put (loop
->header
, queue_index
);
4092 for (; queue_index
>= 0; queue_index
--)
4094 if (latch_index
< queue_index
)
4096 while (queues
[queue_index
].length ())
4099 ptrdiff_t bound_index
= queue_index
;
4103 queue
= queues
[queue_index
];
4106 /* OK, we later inserted the BB with lower priority, skip it. */
4107 if (*block_priority
.get (bb
) > queue_index
)
4110 /* See if we can improve the bound. */
4111 ptrdiff_t *entry
= bb_bounds
.get (bb
);
4112 if (entry
&& *entry
< bound_index
)
4113 bound_index
= *entry
;
4115 /* Insert succesors into the queue, watch for latch edge
4116 and record greatest index we saw. */
4117 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4119 bool insert
= false;
4121 if (loop_exit_edge_p (loop
, e
))
4124 if (e
== loop_latch_edge (loop
)
4125 && latch_index
< bound_index
)
4126 latch_index
= bound_index
;
4127 else if (!(entry
= block_priority
.get (e
->dest
)))
4130 block_priority
.put (e
->dest
, bound_index
);
4132 else if (*entry
< bound_index
)
4135 *entry
= bound_index
;
4139 queues
[bound_index
].safe_push (e
->dest
);
4143 queues
[queue_index
].release ();
4146 gcc_assert (latch_index
>= 0);
4147 if ((unsigned)latch_index
< bounds
.length ())
4149 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4151 fprintf (dump_file
, "Found better loop bound ");
4152 print_decu (bounds
[latch_index
], dump_file
);
4153 fprintf (dump_file
, "\n");
4155 record_niter_bound (loop
, bounds
[latch_index
], false, true);
4161 /* See if every path cross the loop goes through a statement that is known
4162 to not execute at the last iteration. In that case we can decrese iteration
4166 maybe_lower_iteration_bound (class loop
*loop
)
4168 hash_set
<gimple
*> *not_executed_last_iteration
= NULL
;
4169 class nb_iter_bound
*elt
;
4170 bool found_exit
= false;
4171 auto_vec
<basic_block
> queue
;
4174 /* Collect all statements with interesting (i.e. lower than
4175 nb_iterations_upper_bound) bound on them.
4177 TODO: Due to the way record_estimate choose estimates to store, the bounds
4178 will be always nb_iterations_upper_bound-1. We can change this to record
4179 also statements not dominating the loop latch and update the walk bellow
4180 to the shortest path algorithm. */
4181 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
4184 && wi::ltu_p (elt
->bound
, loop
->nb_iterations_upper_bound
))
4186 if (!not_executed_last_iteration
)
4187 not_executed_last_iteration
= new hash_set
<gimple
*>;
4188 not_executed_last_iteration
->add (elt
->stmt
);
4191 if (!not_executed_last_iteration
)
4194 /* Start DFS walk in the loop header and see if we can reach the
4195 loop latch or any of the exits (including statements with side
4196 effects that may terminate the loop otherwise) without visiting
4197 any of the statements known to have undefined effect on the last
4199 queue
.safe_push (loop
->header
);
4200 visited
= BITMAP_ALLOC (NULL
);
4201 bitmap_set_bit (visited
, loop
->header
->index
);
4206 basic_block bb
= queue
.pop ();
4207 gimple_stmt_iterator gsi
;
4208 bool stmt_found
= false;
4210 /* Loop for possible exits and statements bounding the execution. */
4211 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
4213 gimple
*stmt
= gsi_stmt (gsi
);
4214 if (not_executed_last_iteration
->contains (stmt
))
4219 if (gimple_has_side_effects (stmt
))
4228 /* If no bounding statement is found, continue the walk. */
4234 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4236 if (loop_exit_edge_p (loop
, e
)
4237 || e
== loop_latch_edge (loop
))
4242 if (bitmap_set_bit (visited
, e
->dest
->index
))
4243 queue
.safe_push (e
->dest
);
4247 while (queue
.length () && !found_exit
);
4249 /* If every path through the loop reach bounding statement before exit,
4250 then we know the last iteration of the loop will have undefined effect
4251 and we can decrease number of iterations. */
4255 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4256 fprintf (dump_file
, "Reducing loop iteration estimate by 1; "
4257 "undefined statement must be executed at the last iteration.\n");
4258 record_niter_bound (loop
, loop
->nb_iterations_upper_bound
- 1,
4262 BITMAP_FREE (visited
);
4263 delete not_executed_last_iteration
;
4266 /* Get expected upper bound for number of loop iterations for
4267 BUILT_IN_EXPECT_WITH_PROBABILITY for a condition COND. */
4270 get_upper_bound_based_on_builtin_expr_with_prob (gcond
*cond
)
4275 tree lhs
= gimple_cond_lhs (cond
);
4276 if (TREE_CODE (lhs
) != SSA_NAME
)
4279 gimple
*stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (cond
));
4280 gcall
*def
= dyn_cast
<gcall
*> (stmt
);
4284 tree decl
= gimple_call_fndecl (def
);
4286 || !fndecl_built_in_p (decl
, BUILT_IN_EXPECT_WITH_PROBABILITY
)
4287 || gimple_call_num_args (stmt
) != 3)
4290 tree c
= gimple_call_arg (def
, 1);
4291 tree condt
= TREE_TYPE (lhs
);
4292 tree res
= fold_build2 (gimple_cond_code (cond
),
4294 gimple_cond_rhs (cond
));
4295 if (TREE_CODE (res
) != INTEGER_CST
)
4299 tree prob
= gimple_call_arg (def
, 2);
4300 tree t
= TREE_TYPE (prob
);
4302 = build_real_from_int_cst (t
,
4304 if (integer_zerop (res
))
4305 prob
= fold_build2 (MINUS_EXPR
, t
, one
, prob
);
4306 tree r
= fold_build2 (RDIV_EXPR
, t
, one
, prob
);
4307 if (TREE_CODE (r
) != REAL_CST
)
4311 = real_to_integer (TREE_REAL_CST_PTR (r
));
4312 return build_int_cst (condt
, probi
);
4315 /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
4316 is true also use estimates derived from undefined behavior. */
4319 estimate_numbers_of_iterations (class loop
*loop
)
4323 class tree_niter_desc niter_desc
;
4328 /* Give up if we already have tried to compute an estimation. */
4329 if (loop
->estimate_state
!= EST_NOT_COMPUTED
)
4332 loop
->estimate_state
= EST_AVAILABLE
;
4334 /* If we have a measured profile, use it to estimate the number of
4335 iterations. Normally this is recorded by branch_prob right after
4336 reading the profile. In case we however found a new loop, record the
4339 Explicitly check for profile status so we do not report
4340 wrong prediction hitrates for guessed loop iterations heuristics.
4341 Do not recompute already recorded bounds - we ought to be better on
4342 updating iteration bounds than updating profile in general and thus
4343 recomputing iteration bounds later in the compilation process will just
4344 introduce random roundoff errors. */
4345 if (!loop
->any_estimate
4346 && loop
->header
->count
.reliable_p ())
4348 gcov_type nit
= expected_loop_iterations_unbounded (loop
);
4349 bound
= gcov_type_to_wide_int (nit
);
4350 record_niter_bound (loop
, bound
, true, false);
4353 /* Ensure that loop->nb_iterations is computed if possible. If it turns out
4354 to be constant, we avoid undefined behavior implied bounds and instead
4355 diagnose those loops with -Waggressive-loop-optimizations. */
4356 number_of_latch_executions (loop
);
4358 basic_block
*body
= get_loop_body (loop
);
4359 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
, body
);
4360 likely_exit
= single_likely_exit (loop
, exits
);
4361 FOR_EACH_VEC_ELT (exits
, i
, ex
)
4363 if (ex
== likely_exit
)
4365 gimple
*stmt
= last_stmt (ex
->src
);
4368 gcond
*cond
= dyn_cast
<gcond
*> (stmt
);
4370 = get_upper_bound_based_on_builtin_expr_with_prob (cond
);
4371 if (niter_bound
!= NULL_TREE
)
4373 widest_int max
= derive_constant_upper_bound (niter_bound
);
4374 record_estimate (loop
, niter_bound
, max
, cond
,
4380 if (!number_of_iterations_exit (loop
, ex
, &niter_desc
,
4381 false, false, body
))
4384 niter
= niter_desc
.niter
;
4385 type
= TREE_TYPE (niter
);
4386 if (TREE_CODE (niter_desc
.may_be_zero
) != INTEGER_CST
)
4387 niter
= build3 (COND_EXPR
, type
, niter_desc
.may_be_zero
,
4388 build_int_cst (type
, 0),
4390 record_estimate (loop
, niter
, niter_desc
.max
,
4391 last_stmt (ex
->src
),
4392 true, ex
== likely_exit
, true);
4393 record_control_iv (loop
, &niter_desc
);
4396 if (flag_aggressive_loop_optimizations
)
4397 infer_loop_bounds_from_undefined (loop
, body
);
4400 discover_iteration_bound_by_body_walk (loop
);
4402 maybe_lower_iteration_bound (loop
);
4404 /* If we know the exact number of iterations of this loop, try to
4405 not break code with undefined behavior by not recording smaller
4406 maximum number of iterations. */
4407 if (loop
->nb_iterations
4408 && TREE_CODE (loop
->nb_iterations
) == INTEGER_CST
)
4410 loop
->any_upper_bound
= true;
4411 loop
->nb_iterations_upper_bound
= wi::to_widest (loop
->nb_iterations
);
4415 /* Sets NIT to the estimated number of executions of the latch of the
4416 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
4417 large as the number of iterations. If we have no reliable estimate,
4418 the function returns false, otherwise returns true. */
4421 estimated_loop_iterations (class loop
*loop
, widest_int
*nit
)
4423 /* When SCEV information is available, try to update loop iterations
4424 estimate. Otherwise just return whatever we recorded earlier. */
4425 if (scev_initialized_p ())
4426 estimate_numbers_of_iterations (loop
);
4428 return (get_estimated_loop_iterations (loop
, nit
));
4431 /* Similar to estimated_loop_iterations, but returns the estimate only
4432 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
4433 on the number of iterations of LOOP could not be derived, returns -1. */
4436 estimated_loop_iterations_int (class loop
*loop
)
4439 HOST_WIDE_INT hwi_nit
;
4441 if (!estimated_loop_iterations (loop
, &nit
))
4444 if (!wi::fits_shwi_p (nit
))
4446 hwi_nit
= nit
.to_shwi ();
4448 return hwi_nit
< 0 ? -1 : hwi_nit
;
4452 /* Sets NIT to an upper bound for the maximum number of executions of the
4453 latch of the LOOP. If we have no reliable estimate, the function returns
4454 false, otherwise returns true. */
4457 max_loop_iterations (class loop
*loop
, widest_int
*nit
)
4459 /* When SCEV information is available, try to update loop iterations
4460 estimate. Otherwise just return whatever we recorded earlier. */
4461 if (scev_initialized_p ())
4462 estimate_numbers_of_iterations (loop
);
4464 return get_max_loop_iterations (loop
, nit
);
4467 /* Similar to max_loop_iterations, but returns the estimate only
4468 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
4469 on the number of iterations of LOOP could not be derived, returns -1. */
4472 max_loop_iterations_int (class loop
*loop
)
4475 HOST_WIDE_INT hwi_nit
;
4477 if (!max_loop_iterations (loop
, &nit
))
4480 if (!wi::fits_shwi_p (nit
))
4482 hwi_nit
= nit
.to_shwi ();
4484 return hwi_nit
< 0 ? -1 : hwi_nit
;
4487 /* Sets NIT to an likely upper bound for the maximum number of executions of the
4488 latch of the LOOP. If we have no reliable estimate, the function returns
4489 false, otherwise returns true. */
4492 likely_max_loop_iterations (class loop
*loop
, widest_int
*nit
)
4494 /* When SCEV information is available, try to update loop iterations
4495 estimate. Otherwise just return whatever we recorded earlier. */
4496 if (scev_initialized_p ())
4497 estimate_numbers_of_iterations (loop
);
4499 return get_likely_max_loop_iterations (loop
, nit
);
4502 /* Similar to max_loop_iterations, but returns the estimate only
4503 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
4504 on the number of iterations of LOOP could not be derived, returns -1. */
4507 likely_max_loop_iterations_int (class loop
*loop
)
4510 HOST_WIDE_INT hwi_nit
;
4512 if (!likely_max_loop_iterations (loop
, &nit
))
4515 if (!wi::fits_shwi_p (nit
))
4517 hwi_nit
= nit
.to_shwi ();
4519 return hwi_nit
< 0 ? -1 : hwi_nit
;
4522 /* Returns an estimate for the number of executions of statements
4523 in the LOOP. For statements before the loop exit, this exceeds
4524 the number of execution of the latch by one. */
4527 estimated_stmt_executions_int (class loop
*loop
)
4529 HOST_WIDE_INT nit
= estimated_loop_iterations_int (loop
);
4535 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
4537 /* If the computation overflows, return -1. */
4538 return snit
< 0 ? -1 : snit
;
4541 /* Sets NIT to the maximum number of executions of the latch of the
4542 LOOP, plus one. If we have no reliable estimate, the function returns
4543 false, otherwise returns true. */
4546 max_stmt_executions (class loop
*loop
, widest_int
*nit
)
4548 widest_int nit_minus_one
;
4550 if (!max_loop_iterations (loop
, nit
))
4553 nit_minus_one
= *nit
;
4557 return wi::gtu_p (*nit
, nit_minus_one
);
4560 /* Sets NIT to the estimated maximum number of executions of the latch of the
4561 LOOP, plus one. If we have no likely estimate, the function returns
4562 false, otherwise returns true. */
4565 likely_max_stmt_executions (class loop
*loop
, widest_int
*nit
)
4567 widest_int nit_minus_one
;
4569 if (!likely_max_loop_iterations (loop
, nit
))
4572 nit_minus_one
= *nit
;
4576 return wi::gtu_p (*nit
, nit_minus_one
);
4579 /* Sets NIT to the estimated number of executions of the latch of the
4580 LOOP, plus one. If we have no reliable estimate, the function returns
4581 false, otherwise returns true. */
4584 estimated_stmt_executions (class loop
*loop
, widest_int
*nit
)
4586 widest_int nit_minus_one
;
4588 if (!estimated_loop_iterations (loop
, nit
))
4591 nit_minus_one
= *nit
;
4595 return wi::gtu_p (*nit
, nit_minus_one
);
4598 /* Records estimates on numbers of iterations of loops. */
4601 estimate_numbers_of_iterations (function
*fn
)
4603 /* We don't want to issue signed overflow warnings while getting
4604 loop iteration estimates. */
4605 fold_defer_overflow_warnings ();
4607 for (auto loop
: loops_list (fn
, 0))
4608 estimate_numbers_of_iterations (loop
);
4610 fold_undefer_and_ignore_overflow_warnings ();
4613 /* Returns true if statement S1 dominates statement S2. */
4616 stmt_dominates_stmt_p (gimple
*s1
, gimple
*s2
)
4618 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
4626 gimple_stmt_iterator bsi
;
4628 if (gimple_code (s2
) == GIMPLE_PHI
)
4631 if (gimple_code (s1
) == GIMPLE_PHI
)
4634 for (bsi
= gsi_start_bb (bb1
); gsi_stmt (bsi
) != s2
; gsi_next (&bsi
))
4635 if (gsi_stmt (bsi
) == s1
)
4641 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
4644 /* Returns true when we can prove that the number of executions of
4645 STMT in the loop is at most NITER, according to the bound on
4646 the number of executions of the statement NITER_BOUND->stmt recorded in
4647 NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT.
4649 ??? This code can become quite a CPU hog - we can have many bounds,
4650 and large basic block forcing stmt_dominates_stmt_p to be queried
4651 many times on a large basic blocks, so the whole thing is O(n^2)
4652 for scev_probably_wraps_p invocation (that can be done n times).
4654 It would make more sense (and give better answers) to remember BB
4655 bounds computed by discover_iteration_bound_by_body_walk. */
4658 n_of_executions_at_most (gimple
*stmt
,
4659 class nb_iter_bound
*niter_bound
,
4662 widest_int bound
= niter_bound
->bound
;
4663 tree nit_type
= TREE_TYPE (niter
), e
;
4666 gcc_assert (TYPE_UNSIGNED (nit_type
));
4668 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
4669 the number of iterations is small. */
4670 if (!wi::fits_to_tree_p (bound
, nit_type
))
4673 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
4674 times. This means that:
4676 -- if NITER_BOUND->is_exit is true, then everything after
4677 it at most NITER_BOUND->bound times.
4679 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
4680 is executed, then NITER_BOUND->stmt is executed as well in the same
4681 iteration then STMT is executed at most NITER_BOUND->bound + 1 times.
4683 If we can determine that NITER_BOUND->stmt is always executed
4684 after STMT, then STMT is executed at most NITER_BOUND->bound + 2 times.
4685 We conclude that if both statements belong to the same
4686 basic block and STMT is before NITER_BOUND->stmt and there are no
4687 statements with side effects in between. */
4689 if (niter_bound
->is_exit
)
4691 if (stmt
== niter_bound
->stmt
4692 || !stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
4698 if (!stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
4700 gimple_stmt_iterator bsi
;
4701 if (gimple_bb (stmt
) != gimple_bb (niter_bound
->stmt
)
4702 || gimple_code (stmt
) == GIMPLE_PHI
4703 || gimple_code (niter_bound
->stmt
) == GIMPLE_PHI
)
4706 /* By stmt_dominates_stmt_p we already know that STMT appears
4707 before NITER_BOUND->STMT. Still need to test that the loop
4708 cannot be terinated by a side effect in between. */
4709 for (bsi
= gsi_for_stmt (stmt
); gsi_stmt (bsi
) != niter_bound
->stmt
;
4711 if (gimple_has_side_effects (gsi_stmt (bsi
)))
4715 || !wi::fits_to_tree_p (bound
, nit_type
))
4721 e
= fold_binary (cmp
, boolean_type_node
,
4722 niter
, wide_int_to_tree (nit_type
, bound
));
4723 return e
&& integer_nonzerop (e
);
4726 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
4729 nowrap_type_p (tree type
)
4731 if (ANY_INTEGRAL_TYPE_P (type
)
4732 && TYPE_OVERFLOW_UNDEFINED (type
))
4735 if (POINTER_TYPE_P (type
))
4741 /* Return true if we can prove LOOP is exited before evolution of induction
4742 variable {BASE, STEP} overflows with respect to its type bound. */
4745 loop_exits_before_overflow (tree base
, tree step
,
4746 gimple
*at_stmt
, class loop
*loop
)
4749 struct control_iv
*civ
;
4750 class nb_iter_bound
*bound
;
4751 tree e
, delta
, step_abs
, unsigned_base
;
4752 tree type
= TREE_TYPE (step
);
4753 tree unsigned_type
, valid_niter
;
4755 /* Don't issue signed overflow warnings. */
4756 fold_defer_overflow_warnings ();
4758 /* Compute the number of iterations before we reach the bound of the
4759 type, and verify that the loop is exited before this occurs. */
4760 unsigned_type
= unsigned_type_for (type
);
4761 unsigned_base
= fold_convert (unsigned_type
, base
);
4763 if (tree_int_cst_sign_bit (step
))
4765 tree extreme
= fold_convert (unsigned_type
,
4766 lower_bound_in_type (type
, type
));
4767 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, unsigned_base
, extreme
);
4768 step_abs
= fold_build1 (NEGATE_EXPR
, unsigned_type
,
4769 fold_convert (unsigned_type
, step
));
4773 tree extreme
= fold_convert (unsigned_type
,
4774 upper_bound_in_type (type
, type
));
4775 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, unsigned_base
);
4776 step_abs
= fold_convert (unsigned_type
, step
);
4779 valid_niter
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step_abs
);
4781 estimate_numbers_of_iterations (loop
);
4783 if (max_loop_iterations (loop
, &niter
)
4784 && wi::fits_to_tree_p (niter
, TREE_TYPE (valid_niter
))
4785 && (e
= fold_binary (GT_EXPR
, boolean_type_node
, valid_niter
,
4786 wide_int_to_tree (TREE_TYPE (valid_niter
),
4788 && integer_nonzerop (e
))
4790 fold_undefer_and_ignore_overflow_warnings ();
4794 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
4796 if (n_of_executions_at_most (at_stmt
, bound
, valid_niter
))
4798 fold_undefer_and_ignore_overflow_warnings ();
4802 fold_undefer_and_ignore_overflow_warnings ();
4804 /* Try to prove loop is exited before {base, step} overflows with the
4805 help of analyzed loop control IV. This is done only for IVs with
4806 constant step because otherwise we don't have the information. */
4807 if (TREE_CODE (step
) == INTEGER_CST
)
4809 for (civ
= loop
->control_ivs
; civ
; civ
= civ
->next
)
4811 enum tree_code code
;
4812 tree civ_type
= TREE_TYPE (civ
->step
);
4814 /* Have to consider type difference because operand_equal_p ignores
4815 that for constants. */
4816 if (TYPE_UNSIGNED (type
) != TYPE_UNSIGNED (civ_type
)
4817 || element_precision (type
) != element_precision (civ_type
))
4820 /* Only consider control IV with same step. */
4821 if (!operand_equal_p (step
, civ
->step
, 0))
4824 /* Done proving if this is a no-overflow control IV. */
4825 if (operand_equal_p (base
, civ
->base
, 0))
4828 /* Control IV is recorded after expanding simple operations,
4829 Here we expand base and compare it too. */
4830 tree expanded_base
= expand_simple_operations (base
);
4831 if (operand_equal_p (expanded_base
, civ
->base
, 0))
4834 /* If this is a before stepping control IV, in other words, we have
4836 {civ_base, step} = {base + step, step}
4838 Because civ {base + step, step} doesn't overflow during loop
4839 iterations, {base, step} will not overflow if we can prove the
4840 operation "base + step" does not overflow. Specifically, we try
4841 to prove below conditions are satisfied:
4843 base <= UPPER_BOUND (type) - step ;;step > 0
4844 base >= LOWER_BOUND (type) - step ;;step < 0
4846 by proving the reverse conditions are false using loop's initial
4848 if (POINTER_TYPE_P (TREE_TYPE (base
)))
4849 code
= POINTER_PLUS_EXPR
;
4853 tree stepped
= fold_build2 (code
, TREE_TYPE (base
), base
, step
);
4854 tree expanded_stepped
= fold_build2 (code
, TREE_TYPE (base
),
4855 expanded_base
, step
);
4856 if (operand_equal_p (stepped
, civ
->base
, 0)
4857 || operand_equal_p (expanded_stepped
, civ
->base
, 0))
4861 if (tree_int_cst_sign_bit (step
))
4864 extreme
= lower_bound_in_type (type
, type
);
4869 extreme
= upper_bound_in_type (type
, type
);
4871 extreme
= fold_build2 (MINUS_EXPR
, type
, extreme
, step
);
4872 e
= fold_build2 (code
, boolean_type_node
, base
, extreme
);
4873 e
= simplify_using_initial_conditions (loop
, e
);
4874 if (integer_zerop (e
))
4883 /* VAR is scev variable whose evolution part is constant STEP, this function
4884 proves that VAR can't overflow by using value range info. If VAR's value
4885 range is [MIN, MAX], it can be proven by:
4886 MAX + step doesn't overflow ; if step > 0
4888 MIN + step doesn't underflow ; if step < 0.
4890 We can only do this if var is computed in every loop iteration, i.e, var's
4891 definition has to dominate loop latch. Consider below example:
4899 # RANGE [0, 4294967294] NONZERO 65535
4900 # i_21 = PHI <0(3), i_18(9)>
4907 # RANGE [0, 65533] NONZERO 65535
4908 _6 = i_21 + 4294967295;
4909 # RANGE [0, 65533] NONZERO 65535
4910 _7 = (long unsigned int) _6;
4911 # RANGE [0, 524264] NONZERO 524280
4913 # PT = nonlocal escaped
4918 # RANGE [1, 65535] NONZERO 65535
4932 VAR _6 doesn't overflow only with pre-condition (i_21 != 0), here we
4933 can't use _6 to prove no-overlfow for _7. In fact, var _7 takes value
4934 sequence (4294967295, 0, 1, ..., 65533) in loop life time, rather than
4935 (4294967295, 4294967296, ...). */
4938 scev_var_range_cant_overflow (tree var
, tree step
, class loop
*loop
)
4941 wide_int minv
, maxv
, diff
, step_wi
;
4943 if (TREE_CODE (step
) != INTEGER_CST
|| !INTEGRAL_TYPE_P (TREE_TYPE (var
)))
4946 /* Check if VAR evaluates in every loop iteration. It's not the case
4947 if VAR is default definition or does not dominate loop's latch. */
4948 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (var
));
4949 if (!def_bb
|| !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, def_bb
))
4953 get_range_query (cfun
)->range_of_expr (r
, var
);
4954 if (r
.kind () != VR_RANGE
)
4957 /* VAR is a scev whose evolution part is STEP and value range info
4958 is [MIN, MAX], we can prove its no-overflowness by conditions:
4960 type_MAX - MAX >= step ; if step > 0
4961 MIN - type_MIN >= |step| ; if step < 0.
4963 Or VAR must take value outside of value range, which is not true. */
4964 step_wi
= wi::to_wide (step
);
4965 type
= TREE_TYPE (var
);
4966 if (tree_int_cst_sign_bit (step
))
4968 diff
= r
.lower_bound () - wi::to_wide (lower_bound_in_type (type
, type
));
4969 step_wi
= - step_wi
;
4972 diff
= wi::to_wide (upper_bound_in_type (type
, type
)) - r
.upper_bound ();
4974 return (wi::geu_p (diff
, step_wi
));
4977 /* Return false only when the induction variable BASE + STEP * I is
4978 known to not overflow: i.e. when the number of iterations is small
4979 enough with respect to the step and initial condition in order to
4980 keep the evolution confined in TYPEs bounds. Return true when the
4981 iv is known to overflow or when the property is not computable.
4983 USE_OVERFLOW_SEMANTICS is true if this function should assume that
4984 the rules for overflow of the given language apply (e.g., that signed
4985 arithmetics in C does not overflow).
4987 If VAR is a ssa variable, this function also returns false if VAR can
4988 be proven not overflow with value range info. */
4991 scev_probably_wraps_p (tree var
, tree base
, tree step
,
4992 gimple
*at_stmt
, class loop
*loop
,
4993 bool use_overflow_semantics
)
4995 /* FIXME: We really need something like
4996 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
4998 We used to test for the following situation that frequently appears
4999 during address arithmetics:
5001 D.1621_13 = (long unsigned intD.4) D.1620_12;
5002 D.1622_14 = D.1621_13 * 8;
5003 D.1623_15 = (doubleD.29 *) D.1622_14;
5005 And derived that the sequence corresponding to D_14
5006 can be proved to not wrap because it is used for computing a
5007 memory access; however, this is not really the case -- for example,
5008 if D_12 = (unsigned char) [254,+,1], then D_14 has values
5009 2032, 2040, 0, 8, ..., but the code is still legal. */
5011 if (chrec_contains_undetermined (base
)
5012 || chrec_contains_undetermined (step
))
5015 if (integer_zerop (step
))
5018 /* If we can use the fact that signed and pointer arithmetics does not
5019 wrap, we are done. */
5020 if (use_overflow_semantics
&& nowrap_type_p (TREE_TYPE (base
)))
5023 /* To be able to use estimates on number of iterations of the loop,
5024 we must have an upper bound on the absolute value of the step. */
5025 if (TREE_CODE (step
) != INTEGER_CST
)
5028 /* Check if var can be proven not overflow with value range info. */
5029 if (var
&& TREE_CODE (var
) == SSA_NAME
5030 && scev_var_range_cant_overflow (var
, step
, loop
))
5033 if (loop_exits_before_overflow (base
, step
, at_stmt
, loop
))
5036 /* At this point we still don't have a proof that the iv does not
5037 overflow: give up. */
5041 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
5044 free_numbers_of_iterations_estimates (class loop
*loop
)
5046 struct control_iv
*civ
;
5047 class nb_iter_bound
*bound
;
5049 loop
->nb_iterations
= NULL
;
5050 loop
->estimate_state
= EST_NOT_COMPUTED
;
5051 for (bound
= loop
->bounds
; bound
;)
5053 class nb_iter_bound
*next
= bound
->next
;
5057 loop
->bounds
= NULL
;
5059 for (civ
= loop
->control_ivs
; civ
;)
5061 struct control_iv
*next
= civ
->next
;
5065 loop
->control_ivs
= NULL
;
5068 /* Frees the information on upper bounds on numbers of iterations of loops. */
5071 free_numbers_of_iterations_estimates (function
*fn
)
5073 for (auto loop
: loops_list (fn
, 0))
5074 free_numbers_of_iterations_estimates (loop
);
5077 /* Substitute value VAL for ssa name NAME inside expressions held
5081 substitute_in_loop_info (class loop
*loop
, tree name
, tree val
)
5083 loop
->nb_iterations
= simplify_replace_tree (loop
->nb_iterations
, name
, val
);