1 /* Functions to determine/estimate number of iterations of a loop.
2 Copyright (C) 2004-2024 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 "internal-fn.h"
46 #include "gimple-range.h"
50 /* The maximum number of dominator BBs we search for conditions
51 of loop header copies we use for simplifying a conditional
53 #define MAX_DOMINATORS_TO_WALK 8
57 Analysis of number of iterations of an affine exit test.
61 /* Bounds on some value, BELOW <= X <= UP. */
68 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */
71 split_to_var_and_offset (tree expr
, tree
*var
, mpz_t offset
)
73 tree type
= TREE_TYPE (expr
);
78 mpz_set_ui (offset
, 0);
80 switch (TREE_CODE (expr
))
87 case POINTER_PLUS_EXPR
:
88 op0
= TREE_OPERAND (expr
, 0);
89 op1
= TREE_OPERAND (expr
, 1);
91 if (TREE_CODE (op1
) != INTEGER_CST
)
95 /* Always sign extend the offset. */
96 wi::to_mpz (wi::to_wide (op1
), offset
, SIGNED
);
98 mpz_neg (offset
, offset
);
102 *var
= build_int_cst_type (type
, 0);
103 wi::to_mpz (wi::to_wide (expr
), offset
, TYPE_SIGN (type
));
111 /* From condition C0 CMP C1 derives information regarding the value range
112 of VAR, which is of TYPE. Results are stored in to BELOW and UP. */
115 refine_value_range_using_guard (tree type
, tree var
,
116 tree c0
, enum tree_code cmp
, tree c1
,
117 mpz_t below
, mpz_t up
)
119 tree varc0
, varc1
, ctype
;
121 mpz_t mint
, maxt
, minc1
, maxc1
;
122 bool no_wrap
= nowrap_type_p (type
);
124 signop sgn
= TYPE_SIGN (type
);
132 STRIP_SIGN_NOPS (c0
);
133 STRIP_SIGN_NOPS (c1
);
134 ctype
= TREE_TYPE (c0
);
135 if (!useless_type_conversion_p (ctype
, type
))
141 /* We could derive quite precise information from EQ_EXPR, however,
142 such a guard is unlikely to appear, so we do not bother with
147 /* NE_EXPR comparisons do not contain much of useful information,
148 except for cases of comparing with bounds. */
149 if (TREE_CODE (c1
) != INTEGER_CST
150 || !INTEGRAL_TYPE_P (type
))
153 /* Ensure that the condition speaks about an expression in the same
155 ctype
= TREE_TYPE (c0
);
156 if (TYPE_PRECISION (ctype
) != TYPE_PRECISION (type
))
158 c0
= fold_convert (type
, c0
);
159 c1
= fold_convert (type
, c1
);
161 if (operand_equal_p (var
, c0
, 0))
163 /* Case of comparing VAR with its below/up bounds. */
165 wi::to_mpz (wi::to_wide (c1
), valc1
, TYPE_SIGN (type
));
166 if (mpz_cmp (valc1
, below
) == 0)
168 if (mpz_cmp (valc1
, up
) == 0)
173 /* Case of comparing with the bounds of the type. */
174 wide_int min
= wi::min_value (type
);
175 wide_int max
= wi::max_value (type
);
177 if (wi::to_wide (c1
) == min
)
179 if (wi::to_wide (c1
) == max
)
183 /* Quick return if no useful information. */
195 split_to_var_and_offset (expand_simple_operations (c0
), &varc0
, offc0
);
196 split_to_var_and_offset (expand_simple_operations (c1
), &varc1
, offc1
);
198 /* We are only interested in comparisons of expressions based on VAR. */
199 if (operand_equal_p (var
, varc1
, 0))
201 std::swap (varc0
, varc1
);
202 mpz_swap (offc0
, offc1
);
203 cmp
= swap_tree_comparison (cmp
);
205 else if (!operand_equal_p (var
, varc0
, 0))
214 get_type_static_bounds (type
, mint
, maxt
);
217 Value_Range
r (TREE_TYPE (varc1
));
218 /* Setup range information for varc1. */
219 if (integer_zerop (varc1
))
221 wi::to_mpz (0, minc1
, TYPE_SIGN (type
));
222 wi::to_mpz (0, maxc1
, TYPE_SIGN (type
));
224 else if (TREE_CODE (varc1
) == SSA_NAME
225 && INTEGRAL_TYPE_P (type
)
226 && get_range_query (cfun
)->range_of_expr (r
, varc1
)
230 gcc_assert (wi::le_p (r
.lower_bound (), r
.upper_bound (), sgn
));
231 wi::to_mpz (r
.lower_bound (), minc1
, sgn
);
232 wi::to_mpz (r
.upper_bound (), maxc1
, sgn
);
236 mpz_set (minc1
, mint
);
237 mpz_set (maxc1
, maxt
);
240 /* Compute valid range information for varc1 + offc1. Note nothing
241 useful can be derived if it overflows or underflows. Overflow or
242 underflow could happen when:
244 offc1 > 0 && varc1 + offc1 > MAX_VAL (type)
245 offc1 < 0 && varc1 + offc1 < MIN_VAL (type). */
246 mpz_add (minc1
, minc1
, offc1
);
247 mpz_add (maxc1
, maxc1
, offc1
);
249 || mpz_sgn (offc1
) == 0
250 || (mpz_sgn (offc1
) < 0 && mpz_cmp (minc1
, mint
) >= 0)
251 || (mpz_sgn (offc1
) > 0 && mpz_cmp (maxc1
, maxt
) <= 0));
255 if (mpz_cmp (minc1
, mint
) < 0)
256 mpz_set (minc1
, mint
);
257 if (mpz_cmp (maxc1
, maxt
) > 0)
258 mpz_set (maxc1
, maxt
);
263 mpz_sub_ui (maxc1
, maxc1
, 1);
268 mpz_add_ui (minc1
, minc1
, 1);
271 /* Compute range information for varc0. If there is no overflow,
272 the condition implied that
274 (varc0) cmp (varc1 + offc1 - offc0)
276 We can possibly improve the upper bound of varc0 if cmp is LE_EXPR,
277 or the below bound if cmp is GE_EXPR.
279 To prove there is no overflow/underflow, we need to check below
281 1) cmp == LE_EXPR && offc0 > 0
283 (varc0 + offc0) doesn't overflow
284 && (varc1 + offc1 - offc0) doesn't underflow
286 2) cmp == LE_EXPR && offc0 < 0
288 (varc0 + offc0) doesn't underflow
289 && (varc1 + offc1 - offc0) doesn't overfloe
291 In this case, (varc0 + offc0) will never underflow if we can
292 prove (varc1 + offc1 - offc0) doesn't overflow.
294 3) cmp == GE_EXPR && offc0 < 0
296 (varc0 + offc0) doesn't underflow
297 && (varc1 + offc1 - offc0) doesn't overflow
299 4) cmp == GE_EXPR && offc0 > 0
301 (varc0 + offc0) doesn't overflow
302 && (varc1 + offc1 - offc0) doesn't underflow
304 In this case, (varc0 + offc0) will never overflow if we can
305 prove (varc1 + offc1 - offc0) doesn't underflow.
307 Note we only handle case 2 and 4 in below code. */
309 mpz_sub (minc1
, minc1
, offc0
);
310 mpz_sub (maxc1
, maxc1
, offc0
);
312 || mpz_sgn (offc0
) == 0
314 && mpz_sgn (offc0
) < 0 && mpz_cmp (maxc1
, maxt
) <= 0)
316 && mpz_sgn (offc0
) > 0 && mpz_cmp (minc1
, mint
) >= 0));
322 if (mpz_cmp (up
, maxc1
) > 0)
327 if (mpz_cmp (below
, minc1
) < 0)
328 mpz_set (below
, minc1
);
340 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
341 in TYPE to MIN and MAX. */
344 determine_value_range (class loop
*loop
, tree type
, tree var
, mpz_t off
,
345 mpz_t min
, mpz_t max
)
351 enum value_range_kind rtype
= VR_VARYING
;
353 /* If the expression is a constant, we know its value exactly. */
354 if (integer_zerop (var
))
361 get_type_static_bounds (type
, min
, max
);
363 /* See if we have some range info from VRP. */
364 if (TREE_CODE (var
) == SSA_NAME
&& INTEGRAL_TYPE_P (type
))
366 edge e
= loop_preheader_edge (loop
);
367 signop sgn
= TYPE_SIGN (type
);
370 /* Either for VAR itself... */
371 Value_Range
var_range (TREE_TYPE (var
));
372 get_range_query (cfun
)->range_of_expr (var_range
, var
);
373 if (var_range
.varying_p () || var_range
.undefined_p ())
377 if (!var_range
.undefined_p ())
379 minv
= var_range
.lower_bound ();
380 maxv
= var_range
.upper_bound ();
383 /* Or for PHI results in loop->header where VAR is used as
384 PHI argument from the loop preheader edge. */
385 Value_Range
phi_range (TREE_TYPE (var
));
386 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
388 gphi
*phi
= gsi
.phi ();
389 if (PHI_ARG_DEF_FROM_EDGE (phi
, e
) == var
390 && get_range_query (cfun
)->range_of_expr (phi_range
,
391 gimple_phi_result (phi
))
392 && !phi_range
.varying_p ()
393 && !phi_range
.undefined_p ())
395 if (rtype
!= VR_RANGE
)
398 minv
= phi_range
.lower_bound ();
399 maxv
= phi_range
.upper_bound ();
403 minv
= wi::max (minv
, phi_range
.lower_bound (), sgn
);
404 maxv
= wi::min (maxv
, phi_range
.upper_bound (), sgn
);
405 /* If the PHI result range are inconsistent with
406 the VAR range, give up on looking at the PHI
407 results. This can happen if VR_UNDEFINED is
409 if (wi::gt_p (minv
, maxv
, sgn
))
411 Value_Range
vr (TREE_TYPE (var
));
412 get_range_query (cfun
)->range_of_expr (vr
, var
);
413 if (vr
.varying_p () || vr
.undefined_p ())
417 if (!vr
.undefined_p ())
419 minv
= vr
.lower_bound ();
420 maxv
= vr
.upper_bound ();
429 if (rtype
!= VR_RANGE
)
436 gcc_assert (wi::le_p (minv
, maxv
, sgn
));
437 wi::to_mpz (minv
, minm
, sgn
);
438 wi::to_mpz (maxv
, maxm
, sgn
);
440 /* Now walk the dominators of the loop header and use the entry
441 guards to refine the estimates. */
442 for (bb
= loop
->header
;
443 bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && cnt
< MAX_DOMINATORS_TO_WALK
;
444 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 gcond
*cond
= as_a
<gcond
*> (*gsi_last_bb (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
);
514 /* If X == Y, then the expressions are always equal.
515 If X > Y, there are the following possibilities:
516 a) neither of var + X and var + Y overflow or underflow, or both of
517 them do. Then their difference is X - Y.
518 b) var + X overflows, and var + Y does not. Then the values of the
519 expressions are var + X - M and var + Y, where M is the range of
520 the type, and their difference is X - Y - M.
521 c) var + Y underflows and var + X does not. Their difference again
523 Therefore, if the arithmetics in type does not overflow, then the
524 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
525 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
526 (X - Y, X - Y + M). */
530 mpz_set_ui (bnds
->below
, 0);
531 mpz_set_ui (bnds
->up
, 0);
536 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), m
, UNSIGNED
);
537 mpz_add_ui (m
, m
, 1);
538 mpz_sub (bnds
->up
, x
, y
);
539 mpz_set (bnds
->below
, bnds
->up
);
544 mpz_sub (bnds
->below
, bnds
->below
, m
);
546 mpz_add (bnds
->up
, bnds
->up
, m
);
550 /* From condition C0 CMP C1 derives information regarding the
551 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
552 and stores it to BNDS. */
555 refine_bounds_using_guard (tree type
, tree varx
, mpz_t offx
,
556 tree vary
, mpz_t offy
,
557 tree c0
, enum tree_code cmp
, tree c1
,
560 tree varc0
, varc1
, ctype
;
561 mpz_t offc0
, offc1
, loffx
, loffy
, bnd
;
563 bool no_wrap
= nowrap_type_p (type
);
572 STRIP_SIGN_NOPS (c0
);
573 STRIP_SIGN_NOPS (c1
);
574 ctype
= TREE_TYPE (c0
);
575 if (!useless_type_conversion_p (ctype
, type
))
581 /* We could derive quite precise information from EQ_EXPR, however, such
582 a guard is unlikely to appear, so we do not bother with handling
587 /* NE_EXPR comparisons do not contain much of useful information, except for
588 special case of comparing with the bounds of the type. */
589 if (TREE_CODE (c1
) != INTEGER_CST
590 || !INTEGRAL_TYPE_P (type
))
593 /* Ensure that the condition speaks about an expression in the same type
595 ctype
= TREE_TYPE (c0
);
596 if (TYPE_PRECISION (ctype
) != TYPE_PRECISION (type
))
598 c0
= fold_convert (type
, c0
);
599 c1
= fold_convert (type
, c1
);
601 if (TYPE_MIN_VALUE (type
)
602 && operand_equal_p (c1
, TYPE_MIN_VALUE (type
), 0))
607 if (TYPE_MAX_VALUE (type
)
608 && operand_equal_p (c1
, TYPE_MAX_VALUE (type
), 0))
621 split_to_var_and_offset (expand_simple_operations (c0
), &varc0
, offc0
);
622 split_to_var_and_offset (expand_simple_operations (c1
), &varc1
, offc1
);
624 /* We are only interested in comparisons of expressions based on VARX and
625 VARY. TODO -- we might also be able to derive some bounds from
626 expressions containing just one of the variables. */
628 if (operand_equal_p (varx
, varc1
, 0))
630 std::swap (varc0
, varc1
);
631 mpz_swap (offc0
, offc1
);
632 cmp
= swap_tree_comparison (cmp
);
635 if (!operand_equal_p (varx
, varc0
, 0)
636 || !operand_equal_p (vary
, varc1
, 0))
639 mpz_init_set (loffx
, offx
);
640 mpz_init_set (loffy
, offy
);
642 if (cmp
== GT_EXPR
|| cmp
== GE_EXPR
)
644 std::swap (varx
, vary
);
645 mpz_swap (offc0
, offc1
);
646 mpz_swap (loffx
, loffy
);
647 cmp
= swap_tree_comparison (cmp
);
651 /* If there is no overflow, the condition implies that
653 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
655 The overflows and underflows may complicate things a bit; each
656 overflow decreases the appropriate offset by M, and underflow
657 increases it by M. The above inequality would not necessarily be
660 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
661 VARX + OFFC0 overflows, but VARX + OFFX does not.
662 This may only happen if OFFX < OFFC0.
663 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
664 VARY + OFFC1 underflows and VARY + OFFY does not.
665 This may only happen if OFFY > OFFC1. */
674 x_ok
= (integer_zerop (varx
)
675 || mpz_cmp (loffx
, offc0
) >= 0);
676 y_ok
= (integer_zerop (vary
)
677 || mpz_cmp (loffy
, offc1
) <= 0);
683 mpz_sub (bnd
, loffx
, loffy
);
684 mpz_add (bnd
, bnd
, offc1
);
685 mpz_sub (bnd
, bnd
, offc0
);
688 mpz_sub_ui (bnd
, bnd
, 1);
693 if (mpz_cmp (bnds
->below
, bnd
) < 0)
694 mpz_set (bnds
->below
, bnd
);
698 if (mpz_cmp (bnd
, bnds
->up
) < 0)
699 mpz_set (bnds
->up
, bnd
);
711 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
712 The subtraction is considered to be performed in arbitrary precision,
715 We do not attempt to be too clever regarding the value ranges of X and
716 Y; most of the time, they are just integers or ssa names offsetted by
717 integer. However, we try to use the information contained in the
718 comparisons before the loop (usually created by loop header copying). */
721 bound_difference (class loop
*loop
, tree x
, tree y
, bounds
*bnds
)
723 tree type
= TREE_TYPE (x
);
732 /* Get rid of unnecessary casts, but preserve the value of
737 mpz_init (bnds
->below
);
741 split_to_var_and_offset (x
, &varx
, offx
);
742 split_to_var_and_offset (y
, &vary
, offy
);
744 if (!integer_zerop (varx
)
745 && operand_equal_p (varx
, vary
, 0))
747 /* Special case VARX == VARY -- we just need to compare the
748 offsets. The matters are a bit more complicated in the
749 case addition of offsets may wrap. */
750 bound_difference_of_offsetted_base (type
, offx
, offy
, bnds
);
754 /* Otherwise, use the value ranges to determine the initial
755 estimates on below and up. */
756 auto_mpz minx
, maxx
, miny
, maxy
;
757 determine_value_range (loop
, type
, varx
, offx
, minx
, maxx
);
758 determine_value_range (loop
, type
, vary
, offy
, miny
, maxy
);
760 mpz_sub (bnds
->below
, minx
, maxy
);
761 mpz_sub (bnds
->up
, maxx
, miny
);
764 /* If both X and Y are constants, we cannot get any more precise. */
765 if (integer_zerop (varx
) && integer_zerop (vary
))
768 /* Now walk the dominators of the loop header and use the entry
769 guards to refine the estimates. */
770 for (bb
= loop
->header
;
771 bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && cnt
< MAX_DOMINATORS_TO_WALK
;
772 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
774 if (!single_pred_p (bb
))
776 e
= single_pred_edge (bb
);
778 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
781 gcond
*cond
= as_a
<gcond
*> (*gsi_last_bb (e
->src
));
782 c0
= gimple_cond_lhs (cond
);
783 cmp
= gimple_cond_code (cond
);
784 c1
= gimple_cond_rhs (cond
);
786 if (e
->flags
& EDGE_FALSE_VALUE
)
787 cmp
= invert_tree_comparison (cmp
, false);
789 refine_bounds_using_guard (type
, varx
, offx
, vary
, offy
,
799 /* Update the bounds in BNDS that restrict the value of X to the bounds
800 that restrict the value of X + DELTA. X can be obtained as a
801 difference of two values in TYPE. */
804 bounds_add (bounds
*bnds
, const widest_int
&delta
, tree type
)
809 wi::to_mpz (delta
, mdelta
, SIGNED
);
812 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), max
, UNSIGNED
);
814 mpz_add (bnds
->up
, bnds
->up
, mdelta
);
815 mpz_add (bnds
->below
, bnds
->below
, mdelta
);
817 if (mpz_cmp (bnds
->up
, max
) > 0)
818 mpz_set (bnds
->up
, max
);
821 if (mpz_cmp (bnds
->below
, max
) < 0)
822 mpz_set (bnds
->below
, max
);
828 /* Update the bounds in BNDS that restrict the value of X to the bounds
829 that restrict the value of -X. */
832 bounds_negate (bounds
*bnds
)
836 mpz_init_set (tmp
, bnds
->up
);
837 mpz_neg (bnds
->up
, bnds
->below
);
838 mpz_neg (bnds
->below
, tmp
);
842 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
845 inverse (tree x
, tree mask
)
847 tree type
= TREE_TYPE (x
);
849 unsigned ctr
= tree_floor_log2 (mask
);
851 if (TYPE_PRECISION (type
) <= HOST_BITS_PER_WIDE_INT
)
853 unsigned HOST_WIDE_INT ix
;
854 unsigned HOST_WIDE_INT imask
;
855 unsigned HOST_WIDE_INT irslt
= 1;
857 gcc_assert (cst_and_fits_in_hwi (x
));
858 gcc_assert (cst_and_fits_in_hwi (mask
));
860 ix
= int_cst_value (x
);
861 imask
= int_cst_value (mask
);
870 rslt
= build_int_cst_type (type
, irslt
);
874 rslt
= build_int_cst (type
, 1);
877 rslt
= int_const_binop (MULT_EXPR
, rslt
, x
);
878 x
= int_const_binop (MULT_EXPR
, x
, x
);
880 rslt
= int_const_binop (BIT_AND_EXPR
, rslt
, mask
);
886 /* Derives the upper bound BND on the number of executions of loop with exit
887 condition S * i <> C. If NO_OVERFLOW is true, then the control variable of
888 the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed
889 that the loop ends through this exit, i.e., the induction variable ever
890 reaches the value of C.
892 The value C is equal to final - base, where final and base are the final and
893 initial value of the actual induction variable in the analysed loop. BNDS
894 bounds the value of this difference when computed in signed type with
895 unbounded range, while the computation of C is performed in an unsigned
896 type with the range matching the range of the type of the induction variable.
897 In particular, BNDS.up contains an upper bound on C in the following cases:
898 -- if the iv must reach its final value without overflow, i.e., if
899 NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
900 -- if final >= base, which we know to hold when BNDS.below >= 0. */
903 number_of_iterations_ne_max (mpz_t bnd
, bool no_overflow
, tree c
, tree s
,
904 bounds
*bnds
, bool exit_must_be_taken
)
908 tree type
= TREE_TYPE (c
);
909 bool bnds_u_valid
= ((no_overflow
&& exit_must_be_taken
)
910 || mpz_sgn (bnds
->below
) >= 0);
913 || (TREE_CODE (c
) == INTEGER_CST
914 && TREE_CODE (s
) == INTEGER_CST
915 && wi::mod_trunc (wi::to_wide (c
), wi::to_wide (s
),
916 TYPE_SIGN (type
)) == 0)
917 || (TYPE_OVERFLOW_UNDEFINED (type
)
918 && multiple_of_p (type
, c
, s
)))
920 /* If C is an exact multiple of S, then its value will be reached before
921 the induction variable overflows (unless the loop is exited in some
922 other way before). Note that the actual induction variable in the
923 loop (which ranges from base to final instead of from 0 to C) may
924 overflow, in which case BNDS.up will not be giving a correct upper
925 bound on C; thus, BNDS_U_VALID had to be computed in advance. */
927 exit_must_be_taken
= true;
930 /* If the induction variable can overflow, the number of iterations is at
931 most the period of the control variable (or infinite, but in that case
932 the whole # of iterations analysis will fail). */
935 max
= wi::mask
<widest_int
> (TYPE_PRECISION (type
)
936 - wi::ctz (wi::to_wide (s
)), false);
937 wi::to_mpz (max
, bnd
, UNSIGNED
);
941 /* Now we know that the induction variable does not overflow, so the loop
942 iterates at most (range of type / S) times. */
943 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), bnd
, UNSIGNED
);
945 /* If the induction variable is guaranteed to reach the value of C before
947 if (exit_must_be_taken
)
949 /* ... then we can strengthen this to C / S, and possibly we can use
950 the upper bound on C given by BNDS. */
951 if (TREE_CODE (c
) == INTEGER_CST
)
952 wi::to_mpz (wi::to_wide (c
), bnd
, UNSIGNED
);
953 else if (bnds_u_valid
)
954 mpz_set (bnd
, bnds
->up
);
958 wi::to_mpz (wi::to_wide (s
), d
, UNSIGNED
);
959 mpz_fdiv_q (bnd
, bnd
, d
);
963 /* Determines number of iterations of loop whose ending condition
964 is IV <> FINAL. TYPE is the type of the iv. The number of
965 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
966 we know that the exit must be taken eventually, i.e., that the IV
967 ever reaches the value FINAL (we derived this earlier, and possibly set
968 NITER->assumptions to make sure this is the case). BNDS contains the
969 bounds on the difference FINAL - IV->base. */
972 number_of_iterations_ne (class loop
*loop
, tree type
, affine_iv
*iv
,
973 tree final
, class tree_niter_desc
*niter
,
974 bool exit_must_be_taken
, bounds
*bnds
)
976 tree niter_type
= unsigned_type_for (type
);
977 tree s
, c
, d
, bits
, assumption
, tmp
, bound
;
979 niter
->control
= *iv
;
980 niter
->bound
= final
;
981 niter
->cmp
= NE_EXPR
;
983 /* Rearrange the terms so that we get inequality S * i <> C, with S
984 positive. Also cast everything to the unsigned type. If IV does
985 not overflow, BNDS bounds the value of C. Also, this is the
986 case if the computation |FINAL - IV->base| does not overflow, i.e.,
987 if BNDS->below in the result is nonnegative. */
988 if (tree_int_cst_sign_bit (iv
->step
))
990 s
= fold_convert (niter_type
,
991 fold_build1 (NEGATE_EXPR
, type
, iv
->step
));
992 c
= fold_build2 (MINUS_EXPR
, niter_type
,
993 fold_convert (niter_type
, iv
->base
),
994 fold_convert (niter_type
, final
));
995 bounds_negate (bnds
);
999 s
= fold_convert (niter_type
, iv
->step
);
1000 c
= fold_build2 (MINUS_EXPR
, niter_type
,
1001 fold_convert (niter_type
, final
),
1002 fold_convert (niter_type
, iv
->base
));
1006 number_of_iterations_ne_max (max
, iv
->no_overflow
, c
, s
, bnds
,
1007 exit_must_be_taken
);
1008 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, max
, false),
1009 TYPE_SIGN (niter_type
));
1011 /* Compute no-overflow information for the control iv. This can be
1012 proven when below two conditions are satisfied:
1014 1) IV evaluates toward FINAL at beginning, i.e:
1015 base <= FINAL ; step > 0
1016 base >= FINAL ; step < 0
1018 2) |FINAL - base| is an exact multiple of step.
1020 Unfortunately, it's hard to prove above conditions after pass loop-ch
1021 because loop with exit condition (IV != FINAL) usually will be guarded
1022 by initial-condition (IV.base - IV.step != FINAL). In this case, we
1023 can alternatively try to prove below conditions:
1025 1') IV evaluates toward FINAL at beginning, i.e:
1026 new_base = base - step < FINAL ; step > 0
1027 && base - step doesn't underflow
1028 new_base = base - step > FINAL ; step < 0
1029 && base - step doesn't overflow
1031 Please refer to PR34114 as an example of loop-ch's impact.
1033 Note, for NE_EXPR, base equals to FINAL is a special case, in
1034 which the loop exits immediately, and the iv does not overflow.
1036 Also note, we prove condition 2) by checking base and final seperately
1037 along with condition 1) or 1'). Since we ensure the difference
1038 computation of c does not wrap with cond below and the adjusted s
1039 will fit a signed type as well as an unsigned we can safely do
1040 this using the type of the IV if it is not pointer typed. */
1042 if (POINTER_TYPE_P (type
))
1044 if (!niter
->control
.no_overflow
1045 && (integer_onep (s
)
1046 || (multiple_of_p (mtype
, fold_convert (mtype
, iv
->base
),
1047 fold_convert (mtype
, s
), false)
1048 && multiple_of_p (mtype
, fold_convert (mtype
, final
),
1049 fold_convert (mtype
, s
), false))))
1051 tree t
, cond
, relaxed_cond
= boolean_false_node
;
1053 if (tree_int_cst_sign_bit (iv
->step
))
1055 cond
= fold_build2 (GE_EXPR
, boolean_type_node
, iv
->base
, final
);
1056 if (TREE_CODE (type
) == INTEGER_TYPE
)
1058 /* Only when base - step doesn't overflow. */
1059 t
= TYPE_MAX_VALUE (type
);
1060 t
= fold_build2 (PLUS_EXPR
, type
, t
, iv
->step
);
1061 t
= fold_build2 (GE_EXPR
, boolean_type_node
, t
, iv
->base
);
1062 if (integer_nonzerop (t
))
1064 t
= fold_build2 (MINUS_EXPR
, type
, iv
->base
, iv
->step
);
1065 relaxed_cond
= fold_build2 (GT_EXPR
, boolean_type_node
, t
,
1072 cond
= fold_build2 (LE_EXPR
, boolean_type_node
, iv
->base
, final
);
1073 if (TREE_CODE (type
) == INTEGER_TYPE
)
1075 /* Only when base - step doesn't underflow. */
1076 t
= TYPE_MIN_VALUE (type
);
1077 t
= fold_build2 (PLUS_EXPR
, type
, t
, iv
->step
);
1078 t
= fold_build2 (LE_EXPR
, boolean_type_node
, t
, iv
->base
);
1079 if (integer_nonzerop (t
))
1081 t
= fold_build2 (MINUS_EXPR
, type
, iv
->base
, iv
->step
);
1082 relaxed_cond
= fold_build2 (LT_EXPR
, boolean_type_node
, t
,
1088 t
= simplify_using_initial_conditions (loop
, cond
);
1089 if (!t
|| !integer_onep (t
))
1090 t
= simplify_using_initial_conditions (loop
, relaxed_cond
);
1092 if (t
&& integer_onep (t
))
1094 niter
->control
.no_overflow
= true;
1095 niter
->niter
= fold_build2 (EXACT_DIV_EXPR
, niter_type
, c
, s
);
1100 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
1101 is infinite. Otherwise, the number of iterations is
1102 (inverse(s/d) * (c/d)) mod (size of mode/d). */
1103 bits
= num_ending_zeros (s
);
1104 bound
= build_low_bits_mask (niter_type
,
1105 (TYPE_PRECISION (niter_type
)
1106 - tree_to_uhwi (bits
)));
1108 d
= fold_binary_to_constant (LSHIFT_EXPR
, niter_type
,
1109 build_int_cst (niter_type
, 1), bits
);
1110 s
= fold_binary_to_constant (RSHIFT_EXPR
, niter_type
, s
, bits
);
1112 if (!exit_must_be_taken
)
1114 /* If we cannot assume that the exit is taken eventually, record the
1115 assumptions for divisibility of c. */
1116 assumption
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, c
, d
);
1117 assumption
= fold_build2 (EQ_EXPR
, boolean_type_node
,
1118 assumption
, build_int_cst (niter_type
, 0));
1119 if (!integer_nonzerop (assumption
))
1120 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1121 niter
->assumptions
, assumption
);
1124 c
= fold_build2 (EXACT_DIV_EXPR
, niter_type
, c
, d
);
1125 if (integer_onep (s
))
1131 tmp
= fold_build2 (MULT_EXPR
, niter_type
, c
, inverse (s
, bound
));
1132 niter
->niter
= fold_build2 (BIT_AND_EXPR
, niter_type
, tmp
, bound
);
1137 /* Checks whether we can determine the final value of the control variable
1138 of the loop with ending condition IV0 < IV1 (computed in TYPE).
1139 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
1140 of the step. The assumptions necessary to ensure that the computation
1141 of the final value does not overflow are recorded in NITER. If we
1142 find the final value, we adjust DELTA and return TRUE. Otherwise
1143 we return false. BNDS bounds the value of IV1->base - IV0->base,
1144 and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
1145 true if we know that the exit must be taken eventually. */
1148 number_of_iterations_lt_to_ne (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1149 class tree_niter_desc
*niter
,
1150 tree
*delta
, tree step
,
1151 bool exit_must_be_taken
, bounds
*bnds
)
1153 tree niter_type
= TREE_TYPE (step
);
1154 tree mod
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, *delta
, step
);
1156 tree assumption
= boolean_true_node
, bound
, noloop
;
1157 bool fv_comp_no_overflow
;
1159 if (POINTER_TYPE_P (type
))
1162 if (TREE_CODE (mod
) != INTEGER_CST
)
1164 if (integer_nonzerop (mod
))
1165 mod
= fold_build2 (MINUS_EXPR
, niter_type
, step
, mod
);
1166 tmod
= fold_convert (type1
, mod
);
1169 wi::to_mpz (wi::to_wide (mod
), mmod
, UNSIGNED
);
1170 mpz_neg (mmod
, mmod
);
1172 /* If the induction variable does not overflow and the exit is taken,
1173 then the computation of the final value does not overflow. This is
1174 also obviously the case if the new final value is equal to the
1175 current one. Finally, we postulate this for pointer type variables,
1176 as the code cannot rely on the object to that the pointer points being
1177 placed at the end of the address space (and more pragmatically,
1178 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
1179 if (integer_zerop (mod
) || POINTER_TYPE_P (type
))
1180 fv_comp_no_overflow
= true;
1181 else if (!exit_must_be_taken
)
1182 fv_comp_no_overflow
= false;
1184 fv_comp_no_overflow
=
1185 (iv0
->no_overflow
&& integer_nonzerop (iv0
->step
))
1186 || (iv1
->no_overflow
&& integer_nonzerop (iv1
->step
));
1188 if (integer_nonzerop (iv0
->step
))
1190 /* The final value of the iv is iv1->base + MOD, assuming that this
1191 computation does not overflow, and that
1192 iv0->base <= iv1->base + MOD. */
1193 if (!fv_comp_no_overflow
)
1195 bound
= fold_build2 (MINUS_EXPR
, type1
,
1196 TYPE_MAX_VALUE (type1
), tmod
);
1197 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
1199 if (integer_zerop (assumption
))
1202 if (mpz_cmp (mmod
, bnds
->below
) < 0)
1203 noloop
= boolean_false_node
;
1204 else if (POINTER_TYPE_P (type
))
1205 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
1207 fold_build_pointer_plus (iv1
->base
, tmod
));
1209 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
1211 fold_build2 (PLUS_EXPR
, type1
,
1216 /* The final value of the iv is iv0->base - MOD, assuming that this
1217 computation does not overflow, and that
1218 iv0->base - MOD <= iv1->base. */
1219 if (!fv_comp_no_overflow
)
1221 bound
= fold_build2 (PLUS_EXPR
, type1
,
1222 TYPE_MIN_VALUE (type1
), tmod
);
1223 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
1225 if (integer_zerop (assumption
))
1228 if (mpz_cmp (mmod
, bnds
->below
) < 0)
1229 noloop
= boolean_false_node
;
1230 else if (POINTER_TYPE_P (type
))
1231 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
1232 fold_build_pointer_plus (iv0
->base
,
1233 fold_build1 (NEGATE_EXPR
,
1237 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
1238 fold_build2 (MINUS_EXPR
, type1
,
1243 if (!integer_nonzerop (assumption
))
1244 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1247 if (!integer_zerop (noloop
))
1248 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1251 bounds_add (bnds
, wi::to_widest (mod
), type
);
1252 *delta
= fold_build2 (PLUS_EXPR
, niter_type
, *delta
, mod
);
1257 /* Add assertions to NITER that ensure that the control variable of the loop
1258 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
1259 are TYPE. Returns false if we can prove that there is an overflow, true
1260 otherwise. STEP is the absolute value of the step. */
1263 assert_no_overflow_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1264 class tree_niter_desc
*niter
, tree step
)
1266 tree bound
, d
, assumption
, diff
;
1267 tree niter_type
= TREE_TYPE (step
);
1269 if (integer_nonzerop (iv0
->step
))
1271 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
1272 if (iv0
->no_overflow
)
1275 /* If iv0->base is a constant, we can determine the last value before
1276 overflow precisely; otherwise we conservatively assume
1279 if (TREE_CODE (iv0
->base
) == INTEGER_CST
)
1281 d
= fold_build2 (MINUS_EXPR
, niter_type
,
1282 fold_convert (niter_type
, TYPE_MAX_VALUE (type
)),
1283 fold_convert (niter_type
, iv0
->base
));
1284 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
1287 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
1288 build_int_cst (niter_type
, 1));
1289 bound
= fold_build2 (MINUS_EXPR
, type
,
1290 TYPE_MAX_VALUE (type
), fold_convert (type
, diff
));
1291 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
1296 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
1297 if (iv1
->no_overflow
)
1300 if (TREE_CODE (iv1
->base
) == INTEGER_CST
)
1302 d
= fold_build2 (MINUS_EXPR
, niter_type
,
1303 fold_convert (niter_type
, iv1
->base
),
1304 fold_convert (niter_type
, TYPE_MIN_VALUE (type
)));
1305 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
1308 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
1309 build_int_cst (niter_type
, 1));
1310 bound
= fold_build2 (PLUS_EXPR
, type
,
1311 TYPE_MIN_VALUE (type
), fold_convert (type
, diff
));
1312 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
1316 if (integer_zerop (assumption
))
1318 if (!integer_nonzerop (assumption
))
1319 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1320 niter
->assumptions
, assumption
);
1322 iv0
->no_overflow
= true;
1323 iv1
->no_overflow
= true;
1327 /* Add an assumption to NITER that a loop whose ending condition
1328 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
1329 bounds the value of IV1->base - IV0->base. */
1332 assert_loop_rolls_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1333 class tree_niter_desc
*niter
, bounds
*bnds
)
1335 tree assumption
= boolean_true_node
, bound
, diff
;
1336 tree mbz
, mbzl
, mbzr
, type1
;
1337 bool rolls_p
, no_overflow_p
;
1341 /* We are going to compute the number of iterations as
1342 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
1343 variant of TYPE. This formula only works if
1345 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
1347 (where MAX is the maximum value of the unsigned variant of TYPE, and
1348 the computations in this formula are performed in full precision,
1349 i.e., without overflows).
1351 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
1352 we have a condition of the form iv0->base - step < iv1->base before the loop,
1353 and for loops iv0->base < iv1->base - step * i the condition
1354 iv0->base < iv1->base + step, due to loop header copying, which enable us
1355 to prove the lower bound.
1357 The upper bound is more complicated. Unless the expressions for initial
1358 and final value themselves contain enough information, we usually cannot
1359 derive it from the context. */
1361 /* First check whether the answer does not follow from the bounds we gathered
1363 if (integer_nonzerop (iv0
->step
))
1364 dstep
= wi::to_widest (iv0
->step
);
1367 dstep
= wi::sext (wi::to_widest (iv1
->step
), TYPE_PRECISION (type
));
1372 wi::to_mpz (dstep
, mstep
, UNSIGNED
);
1373 mpz_neg (mstep
, mstep
);
1374 mpz_add_ui (mstep
, mstep
, 1);
1376 rolls_p
= mpz_cmp (mstep
, bnds
->below
) <= 0;
1379 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), max
, UNSIGNED
);
1380 mpz_add (max
, max
, mstep
);
1381 no_overflow_p
= (mpz_cmp (bnds
->up
, max
) <= 0
1382 /* For pointers, only values lying inside a single object
1383 can be compared or manipulated by pointer arithmetics.
1384 Gcc in general does not allow or handle objects larger
1385 than half of the address space, hence the upper bound
1386 is satisfied for pointers. */
1387 || POINTER_TYPE_P (type
));
1391 if (rolls_p
&& no_overflow_p
)
1395 if (POINTER_TYPE_P (type
))
1398 /* Now the hard part; we must formulate the assumption(s) as expressions, and
1399 we must be careful not to introduce overflow. */
1401 if (integer_nonzerop (iv0
->step
))
1403 diff
= fold_build2 (MINUS_EXPR
, type1
,
1404 iv0
->step
, build_int_cst (type1
, 1));
1406 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
1407 0 address never belongs to any object, we can assume this for
1409 if (!POINTER_TYPE_P (type
))
1411 bound
= fold_build2 (PLUS_EXPR
, type1
,
1412 TYPE_MIN_VALUE (type
), diff
);
1413 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
1417 /* And then we can compute iv0->base - diff, and compare it with
1419 mbzl
= fold_build2 (MINUS_EXPR
, type1
,
1420 fold_convert (type1
, iv0
->base
), diff
);
1421 mbzr
= fold_convert (type1
, iv1
->base
);
1425 diff
= fold_build2 (PLUS_EXPR
, type1
,
1426 iv1
->step
, build_int_cst (type1
, 1));
1428 if (!POINTER_TYPE_P (type
))
1430 bound
= fold_build2 (PLUS_EXPR
, type1
,
1431 TYPE_MAX_VALUE (type
), diff
);
1432 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
1436 mbzl
= fold_convert (type1
, iv0
->base
);
1437 mbzr
= fold_build2 (MINUS_EXPR
, type1
,
1438 fold_convert (type1
, iv1
->base
), diff
);
1441 if (!integer_nonzerop (assumption
))
1442 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1443 niter
->assumptions
, assumption
);
1446 mbz
= fold_build2 (GT_EXPR
, boolean_type_node
, mbzl
, mbzr
);
1447 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1448 niter
->may_be_zero
, mbz
);
1452 /* Determines number of iterations of loop whose ending condition
1453 is IV0 < IV1 which likes: {base, -C} < n, or n < {base, C}.
1454 The number of iterations is stored to NITER. */
1457 number_of_iterations_until_wrap (class loop
*loop
, tree type
, affine_iv
*iv0
,
1458 affine_iv
*iv1
, class tree_niter_desc
*niter
)
1460 tree niter_type
= unsigned_type_for (type
);
1461 tree step
, num
, assumptions
, may_be_zero
, span
;
1462 wide_int high
, low
, max
, min
;
1464 may_be_zero
= fold_build2 (LE_EXPR
, boolean_type_node
, iv1
->base
, iv0
->base
);
1465 if (integer_onep (may_be_zero
))
1468 int prec
= TYPE_PRECISION (type
);
1469 signop sgn
= TYPE_SIGN (type
);
1470 min
= wi::min_value (prec
, sgn
);
1471 max
= wi::max_value (prec
, sgn
);
1473 /* n < {base, C}. */
1474 if (integer_zerop (iv0
->step
) && !tree_int_cst_sign_bit (iv1
->step
))
1477 /* MIN + C - 1 <= n. */
1478 tree last
= wide_int_to_tree (type
, min
+ wi::to_wide (step
) - 1);
1479 assumptions
= fold_build2 (LE_EXPR
, boolean_type_node
, last
, iv0
->base
);
1480 if (integer_zerop (assumptions
))
1483 num
= fold_build2 (MINUS_EXPR
, niter_type
,
1484 wide_int_to_tree (niter_type
, max
),
1485 fold_convert (niter_type
, iv1
->base
));
1487 /* When base has the form iv + 1, if we know iv >= n, then iv + 1 < n
1488 only when iv + 1 overflows, i.e. when iv == TYPE_VALUE_MAX. */
1490 && integer_onep (step
)
1491 && TREE_CODE (iv1
->base
) == PLUS_EXPR
1492 && integer_onep (TREE_OPERAND (iv1
->base
, 1)))
1494 tree cond
= fold_build2 (GE_EXPR
, boolean_type_node
,
1495 TREE_OPERAND (iv1
->base
, 0), iv0
->base
);
1496 cond
= simplify_using_initial_conditions (loop
, cond
);
1497 if (integer_onep (cond
))
1498 may_be_zero
= fold_build2 (EQ_EXPR
, boolean_type_node
,
1499 TREE_OPERAND (iv1
->base
, 0),
1500 TYPE_MAX_VALUE (type
));
1504 if (TREE_CODE (iv1
->base
) == INTEGER_CST
)
1505 low
= wi::to_wide (iv1
->base
) - 1;
1506 else if (TREE_CODE (iv0
->base
) == INTEGER_CST
)
1507 low
= wi::to_wide (iv0
->base
);
1511 /* {base, -C} < n. */
1512 else if (tree_int_cst_sign_bit (iv0
->step
) && integer_zerop (iv1
->step
))
1514 step
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (iv0
->step
), iv0
->step
);
1515 /* MAX - C + 1 >= n. */
1516 tree last
= wide_int_to_tree (type
, max
- wi::to_wide (step
) + 1);
1517 assumptions
= fold_build2 (GE_EXPR
, boolean_type_node
, last
, iv1
->base
);
1518 if (integer_zerop (assumptions
))
1521 num
= fold_build2 (MINUS_EXPR
, niter_type
,
1522 fold_convert (niter_type
, iv0
->base
),
1523 wide_int_to_tree (niter_type
, min
));
1525 if (TREE_CODE (iv0
->base
) == INTEGER_CST
)
1526 high
= wi::to_wide (iv0
->base
) + 1;
1527 else if (TREE_CODE (iv1
->base
) == INTEGER_CST
)
1528 high
= wi::to_wide (iv1
->base
);
1535 /* (delta + step - 1) / step */
1536 step
= fold_convert (niter_type
, step
);
1537 num
= fold_build2 (PLUS_EXPR
, niter_type
, num
, step
);
1538 niter
->niter
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, num
, step
);
1540 widest_int delta
, s
;
1541 delta
= widest_int::from (high
, sgn
) - widest_int::from (low
, sgn
);
1542 s
= wi::to_widest (step
);
1543 delta
= delta
+ s
- 1;
1544 niter
->max
= wi::udiv_floor (delta
, s
);
1546 niter
->may_be_zero
= may_be_zero
;
1548 if (!integer_nonzerop (assumptions
))
1549 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1550 niter
->assumptions
, assumptions
);
1552 niter
->control
.no_overflow
= false;
1554 /* Update bound and exit condition as:
1555 bound = niter * STEP + (IVbase - STEP).
1556 { IVbase - STEP, +, STEP } != bound
1557 Here, biasing IVbase by 1 step makes 'bound' be the value before wrap.
1559 tree base_type
= TREE_TYPE (niter
->control
.base
);
1560 if (POINTER_TYPE_P (base_type
))
1562 tree utype
= unsigned_type_for (base_type
);
1564 = fold_build2 (MINUS_EXPR
, utype
,
1565 fold_convert (utype
, niter
->control
.base
),
1566 fold_convert (utype
, niter
->control
.step
));
1567 niter
->control
.base
= fold_convert (base_type
, niter
->control
.base
);
1571 = fold_build2 (MINUS_EXPR
, base_type
, niter
->control
.base
,
1572 niter
->control
.step
);
1574 span
= fold_build2 (MULT_EXPR
, niter_type
, niter
->niter
,
1575 fold_convert (niter_type
, niter
->control
.step
));
1576 niter
->bound
= fold_build2 (PLUS_EXPR
, niter_type
, span
,
1577 fold_convert (niter_type
, niter
->control
.base
));
1578 niter
->bound
= fold_convert (type
, niter
->bound
);
1579 niter
->cmp
= NE_EXPR
;
1584 /* Determines number of iterations of loop whose ending condition
1585 is IV0 < IV1. TYPE is the type of the iv. The number of
1586 iterations is stored to NITER. BNDS bounds the difference
1587 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
1588 that the exit must be taken eventually. */
1591 number_of_iterations_lt (class loop
*loop
, tree type
, affine_iv
*iv0
,
1592 affine_iv
*iv1
, class tree_niter_desc
*niter
,
1593 bool exit_must_be_taken
, bounds
*bnds
)
1595 tree niter_type
= unsigned_type_for (type
);
1596 tree delta
, step
, s
;
1599 if (integer_nonzerop (iv0
->step
))
1601 niter
->control
= *iv0
;
1602 niter
->cmp
= LT_EXPR
;
1603 niter
->bound
= iv1
->base
;
1607 niter
->control
= *iv1
;
1608 niter
->cmp
= GT_EXPR
;
1609 niter
->bound
= iv0
->base
;
1612 /* {base, -C} < n, or n < {base, C} */
1613 if (tree_int_cst_sign_bit (iv0
->step
)
1614 || (!integer_zerop (iv1
->step
) && !tree_int_cst_sign_bit (iv1
->step
)))
1615 return number_of_iterations_until_wrap (loop
, type
, iv0
, iv1
, niter
);
1617 delta
= fold_build2 (MINUS_EXPR
, niter_type
,
1618 fold_convert (niter_type
, iv1
->base
),
1619 fold_convert (niter_type
, iv0
->base
));
1621 /* First handle the special case that the step is +-1. */
1622 if ((integer_onep (iv0
->step
) && integer_zerop (iv1
->step
))
1623 || (integer_all_onesp (iv1
->step
) && integer_zerop (iv0
->step
)))
1625 /* for (i = iv0->base; i < iv1->base; i++)
1629 for (i = iv1->base; i > iv0->base; i--).
1631 In both cases # of iterations is iv1->base - iv0->base, assuming that
1632 iv1->base >= iv0->base.
1634 First try to derive a lower bound on the value of
1635 iv1->base - iv0->base, computed in full precision. If the difference
1636 is nonnegative, we are done, otherwise we must record the
1639 if (mpz_sgn (bnds
->below
) < 0)
1640 niter
->may_be_zero
= fold_build2 (LT_EXPR
, boolean_type_node
,
1641 iv1
->base
, iv0
->base
);
1642 niter
->niter
= delta
;
1643 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, bnds
->up
, false),
1644 TYPE_SIGN (niter_type
));
1645 niter
->control
.no_overflow
= true;
1649 if (integer_nonzerop (iv0
->step
))
1650 step
= fold_convert (niter_type
, iv0
->step
);
1652 step
= fold_convert (niter_type
,
1653 fold_build1 (NEGATE_EXPR
, type
, iv1
->step
));
1655 /* If we can determine the final value of the control iv exactly, we can
1656 transform the condition to != comparison. In particular, this will be
1657 the case if DELTA is constant. */
1658 if (number_of_iterations_lt_to_ne (type
, iv0
, iv1
, niter
, &delta
, step
,
1659 exit_must_be_taken
, bnds
))
1663 zps
.base
= build_int_cst (niter_type
, 0);
1665 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1666 zps does not overflow. */
1667 zps
.no_overflow
= true;
1669 return number_of_iterations_ne (loop
, type
, &zps
,
1670 delta
, niter
, true, bnds
);
1673 /* Make sure that the control iv does not overflow. */
1674 if (!assert_no_overflow_lt (type
, iv0
, iv1
, niter
, step
))
1677 /* We determine the number of iterations as (delta + step - 1) / step. For
1678 this to work, we must know that iv1->base >= iv0->base - step + 1,
1679 otherwise the loop does not roll. */
1680 assert_loop_rolls_lt (type
, iv0
, iv1
, niter
, bnds
);
1682 s
= fold_build2 (MINUS_EXPR
, niter_type
,
1683 step
, build_int_cst (niter_type
, 1));
1684 delta
= fold_build2 (PLUS_EXPR
, niter_type
, delta
, s
);
1685 niter
->niter
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, delta
, step
);
1689 wi::to_mpz (wi::to_wide (step
), mstep
, UNSIGNED
);
1690 mpz_add (tmp
, bnds
->up
, mstep
);
1691 mpz_sub_ui (tmp
, tmp
, 1);
1692 mpz_fdiv_q (tmp
, tmp
, mstep
);
1693 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, tmp
, false),
1694 TYPE_SIGN (niter_type
));
1701 /* Determines number of iterations of loop whose ending condition
1702 is IV0 <= IV1. TYPE is the type of the iv. The number of
1703 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
1704 we know that this condition must eventually become false (we derived this
1705 earlier, and possibly set NITER->assumptions to make sure this
1706 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1709 number_of_iterations_le (class loop
*loop
, tree type
, affine_iv
*iv0
,
1710 affine_iv
*iv1
, class tree_niter_desc
*niter
,
1711 bool exit_must_be_taken
, bounds
*bnds
)
1715 if (POINTER_TYPE_P (type
))
1718 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1719 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1720 value of the type. This we must know anyway, since if it is
1721 equal to this value, the loop rolls forever. We do not check
1722 this condition for pointer type ivs, as the code cannot rely on
1723 the object to that the pointer points being placed at the end of
1724 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1725 not defined for pointers). */
1727 if (!exit_must_be_taken
&& !POINTER_TYPE_P (type
))
1729 if (integer_nonzerop (iv0
->step
))
1730 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1731 iv1
->base
, TYPE_MAX_VALUE (type
));
1733 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1734 iv0
->base
, TYPE_MIN_VALUE (type
));
1736 if (integer_zerop (assumption
))
1738 if (!integer_nonzerop (assumption
))
1739 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1740 niter
->assumptions
, assumption
);
1743 if (integer_nonzerop (iv0
->step
))
1745 if (POINTER_TYPE_P (type
))
1746 iv1
->base
= fold_build_pointer_plus_hwi (iv1
->base
, 1);
1748 iv1
->base
= fold_build2 (PLUS_EXPR
, type1
, iv1
->base
,
1749 build_int_cst (type1
, 1));
1751 else if (POINTER_TYPE_P (type
))
1752 iv0
->base
= fold_build_pointer_plus_hwi (iv0
->base
, -1);
1754 iv0
->base
= fold_build2 (MINUS_EXPR
, type1
,
1755 iv0
->base
, build_int_cst (type1
, 1));
1757 bounds_add (bnds
, 1, type1
);
1759 return number_of_iterations_lt (loop
, type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1763 /* Dumps description of affine induction variable IV to FILE. */
1766 dump_affine_iv (FILE *file
, affine_iv
*iv
)
1768 if (!integer_zerop (iv
->step
))
1769 fprintf (file
, "[");
1771 print_generic_expr (dump_file
, iv
->base
, TDF_SLIM
);
1773 if (!integer_zerop (iv
->step
))
1775 fprintf (file
, ", + , ");
1776 print_generic_expr (dump_file
, iv
->step
, TDF_SLIM
);
1777 fprintf (file
, "]%s", iv
->no_overflow
? "(no_overflow)" : "");
1781 /* Determine the number of iterations according to condition (for staying
1782 inside loop) which compares two induction variables using comparison
1783 operator CODE. The induction variable on left side of the comparison
1784 is IV0, the right-hand side is IV1. Both induction variables must have
1785 type TYPE, which must be an integer or pointer type. The steps of the
1786 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1788 LOOP is the loop whose number of iterations we are determining.
1790 ONLY_EXIT is true if we are sure this is the only way the loop could be
1791 exited (including possibly non-returning function calls, exceptions, etc.)
1792 -- in this case we can use the information whether the control induction
1793 variables can overflow or not in a more efficient way.
1795 if EVERY_ITERATION is true, we know the test is executed on every iteration.
1797 The results (number of iterations and assumptions as described in
1798 comments at class tree_niter_desc in tree-ssa-loop.h) are stored to NITER.
1799 Returns false if it fails to determine number of iterations, true if it
1800 was determined (possibly with some assumptions). */
1803 number_of_iterations_cond (class loop
*loop
,
1804 tree type
, affine_iv
*iv0
, enum tree_code code
,
1805 affine_iv
*iv1
, class tree_niter_desc
*niter
,
1806 bool only_exit
, bool every_iteration
)
1808 bool exit_must_be_taken
= false, ret
;
1811 /* If the test is not executed every iteration, wrapping may make the test
1813 TODO: the overflow case can be still used as unreliable estimate of upper
1814 bound. But we have no API to pass it down to number of iterations code
1815 and, at present, it will not use it anyway. */
1816 if (!every_iteration
1817 && (!iv0
->no_overflow
|| !iv1
->no_overflow
1818 || code
== NE_EXPR
|| code
== EQ_EXPR
))
1821 /* The meaning of these assumptions is this:
1823 then the rest of information does not have to be valid
1824 if may_be_zero then the loop does not roll, even if
1826 niter
->assumptions
= boolean_true_node
;
1827 niter
->may_be_zero
= boolean_false_node
;
1828 niter
->niter
= NULL_TREE
;
1830 niter
->bound
= NULL_TREE
;
1831 niter
->cmp
= ERROR_MARK
;
1833 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1834 the control variable is on lhs. */
1835 if (code
== GE_EXPR
|| code
== GT_EXPR
1836 || (code
== NE_EXPR
&& integer_zerop (iv0
->step
)))
1838 std::swap (iv0
, iv1
);
1839 code
= swap_tree_comparison (code
);
1842 if (POINTER_TYPE_P (type
))
1844 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1845 to the same object. If they do, the control variable cannot wrap
1846 (as wrap around the bounds of memory will never return a pointer
1847 that would be guaranteed to point to the same object, even if we
1848 avoid undefined behavior by casting to size_t and back). */
1849 iv0
->no_overflow
= true;
1850 iv1
->no_overflow
= true;
1853 /* If the control induction variable does not overflow and the only exit
1854 from the loop is the one that we analyze, we know it must be taken
1858 if (!integer_zerop (iv0
->step
) && iv0
->no_overflow
)
1859 exit_must_be_taken
= true;
1860 else if (!integer_zerop (iv1
->step
) && iv1
->no_overflow
)
1861 exit_must_be_taken
= true;
1864 /* We can handle cases which neither of the sides of the comparison is
1867 {iv0.base, iv0.step} cmp_code {iv1.base, iv1.step}
1869 {iv0.base, iv0.step - iv1.step} cmp_code {iv1.base, 0}
1871 provided that either below condition is satisfied:
1873 a) the test is NE_EXPR;
1874 b) iv0 and iv1 do not overflow and iv0.step - iv1.step is of
1875 the same sign and of less or equal magnitude than iv0.step
1877 This rarely occurs in practice, but it is simple enough to manage. */
1878 if (!integer_zerop (iv0
->step
) && !integer_zerop (iv1
->step
))
1880 tree step_type
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1881 tree step
= fold_binary_to_constant (MINUS_EXPR
, step_type
,
1882 iv0
->step
, iv1
->step
);
1884 /* For code other than NE_EXPR we have to ensure moving the evolution
1885 of IV1 to that of IV0 does not introduce overflow. */
1886 if (TREE_CODE (step
) != INTEGER_CST
1887 || !iv0
->no_overflow
|| !iv1
->no_overflow
)
1889 if (code
!= NE_EXPR
)
1891 iv0
->no_overflow
= false;
1893 /* If the new step of IV0 has changed sign or is of greater
1894 magnitude then we do not know whether IV0 does overflow
1895 and thus the transform is not valid for code other than NE_EXPR. */
1896 else if (tree_int_cst_sign_bit (step
) != tree_int_cst_sign_bit (iv0
->step
)
1897 || wi::gtu_p (wi::abs (wi::to_widest (step
)),
1898 wi::abs (wi::to_widest (iv0
->step
))))
1900 if (POINTER_TYPE_P (type
) && code
!= NE_EXPR
)
1901 /* For relational pointer compares we have further guarantees
1902 that the pointers always point to the same object (or one
1903 after it) and that objects do not cross the zero page. So
1904 not only is the transform always valid for relational
1905 pointer compares, we also know the resulting IV does not
1908 else if (code
!= NE_EXPR
)
1911 iv0
->no_overflow
= false;
1915 iv1
->step
= build_int_cst (step_type
, 0);
1916 iv1
->no_overflow
= true;
1919 /* If the result of the comparison is a constant, the loop is weird. More
1920 precise handling would be possible, but the situation is not common enough
1921 to waste time on it. */
1922 if (integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
))
1925 /* If the loop exits immediately, there is nothing to do. */
1926 tree tem
= fold_binary (code
, boolean_type_node
, iv0
->base
, iv1
->base
);
1927 if (tem
&& integer_zerop (tem
))
1929 if (!every_iteration
)
1931 niter
->niter
= build_int_cst (unsigned_type_for (type
), 0);
1936 /* OK, now we know we have a senseful loop. Handle several cases, depending
1937 on what comparison operator is used. */
1938 bound_difference (loop
, iv1
->base
, iv0
->base
, &bnds
);
1940 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1943 "Analyzing # of iterations of loop %d\n", loop
->num
);
1945 fprintf (dump_file
, " exit condition ");
1946 dump_affine_iv (dump_file
, iv0
);
1947 fprintf (dump_file
, " %s ",
1948 code
== NE_EXPR
? "!="
1949 : code
== LT_EXPR
? "<"
1951 dump_affine_iv (dump_file
, iv1
);
1952 fprintf (dump_file
, "\n");
1954 fprintf (dump_file
, " bounds on difference of bases: ");
1955 mpz_out_str (dump_file
, 10, bnds
.below
);
1956 fprintf (dump_file
, " ... ");
1957 mpz_out_str (dump_file
, 10, bnds
.up
);
1958 fprintf (dump_file
, "\n");
1964 gcc_assert (integer_zerop (iv1
->step
));
1965 ret
= number_of_iterations_ne (loop
, type
, iv0
, iv1
->base
, niter
,
1966 exit_must_be_taken
, &bnds
);
1970 ret
= number_of_iterations_lt (loop
, type
, iv0
, iv1
, niter
,
1971 exit_must_be_taken
, &bnds
);
1975 ret
= number_of_iterations_le (loop
, type
, iv0
, iv1
, niter
,
1976 exit_must_be_taken
, &bnds
);
1983 mpz_clear (bnds
.up
);
1984 mpz_clear (bnds
.below
);
1986 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1990 fprintf (dump_file
, " result:\n");
1991 if (!integer_nonzerop (niter
->assumptions
))
1993 fprintf (dump_file
, " under assumptions ");
1994 print_generic_expr (dump_file
, niter
->assumptions
, TDF_SLIM
);
1995 fprintf (dump_file
, "\n");
1998 if (!integer_zerop (niter
->may_be_zero
))
2000 fprintf (dump_file
, " zero if ");
2001 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
2002 fprintf (dump_file
, "\n");
2005 fprintf (dump_file
, " # of iterations ");
2006 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
2007 fprintf (dump_file
, ", bounded by ");
2008 print_decu (niter
->max
, dump_file
);
2009 fprintf (dump_file
, "\n");
2012 fprintf (dump_file
, " failed\n\n");
2017 /* Return an expression that computes the popcount of src. */
2020 build_popcount_expr (tree src
)
2023 bool use_ifn
= false;
2024 int prec
= TYPE_PRECISION (TREE_TYPE (src
));
2025 int i_prec
= TYPE_PRECISION (integer_type_node
);
2026 int li_prec
= TYPE_PRECISION (long_integer_type_node
);
2027 int lli_prec
= TYPE_PRECISION (long_long_integer_type_node
);
2029 tree utype
= unsigned_type_for (TREE_TYPE (src
));
2030 src
= fold_convert (utype
, src
);
2032 if (direct_internal_fn_supported_p (IFN_POPCOUNT
, utype
, OPTIMIZE_FOR_BOTH
))
2034 else if (prec
<= i_prec
)
2035 fn
= builtin_decl_implicit (BUILT_IN_POPCOUNT
);
2036 else if (prec
== li_prec
)
2037 fn
= builtin_decl_implicit (BUILT_IN_POPCOUNTL
);
2038 else if (prec
== lli_prec
|| prec
== 2 * lli_prec
)
2039 fn
= builtin_decl_implicit (BUILT_IN_POPCOUNTLL
);
2045 call
= build_call_expr_internal_loc (UNKNOWN_LOCATION
, IFN_POPCOUNT
,
2046 integer_type_node
, 1, src
);
2047 else if (prec
== 2 * lli_prec
)
2049 tree src1
= fold_convert (long_long_unsigned_type_node
,
2050 fold_build2 (RSHIFT_EXPR
, TREE_TYPE (src
),
2052 build_int_cst (integer_type_node
,
2054 tree src2
= fold_convert (long_long_unsigned_type_node
, src
);
2055 tree call1
= build_call_expr (fn
, 1, src1
);
2056 tree call2
= build_call_expr (fn
, 1, src2
);
2057 call
= fold_build2 (PLUS_EXPR
, integer_type_node
, call1
, call2
);
2062 src
= fold_convert (unsigned_type_node
, src
);
2064 call
= build_call_expr (fn
, 1, src
);
2070 /* Utility function to check if OP is defined by a stmt
2071 that is a val - 1. */
2074 ssa_defined_by_minus_one_stmt_p (tree op
, tree val
)
2077 return (TREE_CODE (op
) == SSA_NAME
2078 && (stmt
= SSA_NAME_DEF_STMT (op
))
2079 && is_gimple_assign (stmt
)
2080 && (gimple_assign_rhs_code (stmt
) == PLUS_EXPR
)
2081 && val
== gimple_assign_rhs1 (stmt
)
2082 && integer_minus_onep (gimple_assign_rhs2 (stmt
)));
2085 /* See comment below for number_of_iterations_bitcount.
2086 For popcount, we have:
2101 number_of_iterations_popcount (loop_p loop
, edge exit
,
2102 enum tree_code code
,
2103 class tree_niter_desc
*niter
)
2105 bool modify_before_test
= true;
2108 /* Check that condition for staying inside the loop is like
2110 gcond
*cond_stmt
= safe_dyn_cast
<gcond
*> (*gsi_last_bb (exit
->src
));
2113 || !integer_zerop (gimple_cond_rhs (cond_stmt
))
2114 || TREE_CODE (gimple_cond_lhs (cond_stmt
)) != SSA_NAME
)
2117 tree iv_2
= gimple_cond_lhs (cond_stmt
);
2118 gimple
*iv_2_stmt
= SSA_NAME_DEF_STMT (iv_2
);
2120 /* If the test comes before the iv modification, then these will actually be
2121 iv_1 and a phi node. */
2122 if (gimple_code (iv_2_stmt
) == GIMPLE_PHI
2123 && gimple_bb (iv_2_stmt
) == loop
->header
2124 && gimple_phi_num_args (iv_2_stmt
) == 2
2125 && (TREE_CODE (gimple_phi_arg_def (iv_2_stmt
,
2126 loop_latch_edge (loop
)->dest_idx
))
2129 /* iv_2 is actually one of the inputs to the phi. */
2130 iv_2
= gimple_phi_arg_def (iv_2_stmt
, loop_latch_edge (loop
)->dest_idx
);
2131 iv_2_stmt
= SSA_NAME_DEF_STMT (iv_2
);
2132 modify_before_test
= false;
2135 /* Make sure iv_2_stmt is an and stmt (iv_2 = _1 & iv_1). */
2136 if (!is_gimple_assign (iv_2_stmt
)
2137 || gimple_assign_rhs_code (iv_2_stmt
) != BIT_AND_EXPR
)
2140 tree iv_1
= gimple_assign_rhs1 (iv_2_stmt
);
2141 tree _1
= gimple_assign_rhs2 (iv_2_stmt
);
2143 /* Check that _1 is defined by (_1 = iv_1 + -1).
2144 Also make sure that _1 is the same in and_stmt and _1 defining stmt.
2145 Also canonicalize if _1 and _b11 are revrsed. */
2146 if (ssa_defined_by_minus_one_stmt_p (iv_1
, _1
))
2147 std::swap (iv_1
, _1
);
2148 else if (ssa_defined_by_minus_one_stmt_p (_1
, iv_1
))
2153 /* Check the recurrence. */
2154 gimple
*phi
= SSA_NAME_DEF_STMT (iv_1
);
2155 if (gimple_code (phi
) != GIMPLE_PHI
2156 || (gimple_bb (phi
) != loop_latch_edge (loop
)->dest
)
2157 || (iv_2
!= gimple_phi_arg_def (phi
, loop_latch_edge (loop
)->dest_idx
)))
2160 /* We found a match. */
2161 tree src
= gimple_phi_arg_def (phi
, loop_preheader_edge (loop
)->dest_idx
);
2162 int src_precision
= TYPE_PRECISION (TREE_TYPE (src
));
2164 /* Get the corresponding popcount builtin. */
2165 tree expr
= build_popcount_expr (src
);
2170 max
= src_precision
;
2172 tree may_be_zero
= boolean_false_node
;
2174 if (modify_before_test
)
2176 expr
= fold_build2 (MINUS_EXPR
, integer_type_node
, expr
,
2179 may_be_zero
= fold_build2 (EQ_EXPR
, boolean_type_node
, src
,
2180 build_zero_cst (TREE_TYPE (src
)));
2183 expr
= fold_convert (unsigned_type_node
, expr
);
2185 niter
->assumptions
= boolean_true_node
;
2186 niter
->may_be_zero
= simplify_using_initial_conditions (loop
, may_be_zero
);
2187 niter
->niter
= simplify_using_initial_conditions(loop
, expr
);
2189 if (TREE_CODE (niter
->niter
) == INTEGER_CST
)
2190 niter
->max
= tree_to_uhwi (niter
->niter
);
2194 niter
->bound
= NULL_TREE
;
2195 niter
->cmp
= ERROR_MARK
;
2199 /* Return an expression that counts the leading/trailing zeroes of src.
2201 If define_at_zero is true, then the built expression will be defined to
2202 return the precision of src when src == 0 (using either a conditional
2203 expression or a suitable internal function).
2204 Otherwise, we can elide the conditional expression and let src = 0 invoke
2205 undefined behaviour. */
2208 build_cltz_expr (tree src
, bool leading
, bool define_at_zero
)
2211 internal_fn ifn
= leading
? IFN_CLZ
: IFN_CTZ
;
2212 bool use_ifn
= false;
2213 int prec
= TYPE_PRECISION (TREE_TYPE (src
));
2214 int i_prec
= TYPE_PRECISION (integer_type_node
);
2215 int li_prec
= TYPE_PRECISION (long_integer_type_node
);
2216 int lli_prec
= TYPE_PRECISION (long_long_integer_type_node
);
2218 tree utype
= unsigned_type_for (TREE_TYPE (src
));
2219 src
= fold_convert (utype
, src
);
2221 if (direct_internal_fn_supported_p (ifn
, utype
, OPTIMIZE_FOR_BOTH
))
2223 else if (prec
<= i_prec
)
2224 fn
= leading
? builtin_decl_implicit (BUILT_IN_CLZ
)
2225 : builtin_decl_implicit (BUILT_IN_CTZ
);
2226 else if (prec
== li_prec
)
2227 fn
= leading
? builtin_decl_implicit (BUILT_IN_CLZL
)
2228 : builtin_decl_implicit (BUILT_IN_CTZL
);
2229 else if (prec
== lli_prec
|| prec
== 2 * lli_prec
)
2230 fn
= leading
? builtin_decl_implicit (BUILT_IN_CLZLL
)
2231 : builtin_decl_implicit (BUILT_IN_CTZLL
);
2239 int optab_defined_at_zero
2241 ? CLZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (utype
), val
)
2242 : CTZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (utype
), val
));
2243 tree arg2
= NULL_TREE
;
2244 if (define_at_zero
&& optab_defined_at_zero
== 2 && val
== prec
)
2245 arg2
= build_int_cst (integer_type_node
, val
);
2246 call
= build_call_expr_internal_loc (UNKNOWN_LOCATION
, ifn
,
2247 integer_type_node
, arg2
? 2 : 1,
2249 if (define_at_zero
&& arg2
== NULL_TREE
)
2251 tree is_zero
= fold_build2 (NE_EXPR
, boolean_type_node
, src
,
2252 build_zero_cst (TREE_TYPE (src
)));
2253 call
= fold_build3 (COND_EXPR
, integer_type_node
, is_zero
, call
,
2254 build_int_cst (integer_type_node
, prec
));
2257 else if (prec
== 2 * lli_prec
)
2259 tree src1
= fold_convert (long_long_unsigned_type_node
,
2260 fold_build2 (RSHIFT_EXPR
, TREE_TYPE (src
),
2262 build_int_cst (integer_type_node
,
2264 tree src2
= fold_convert (long_long_unsigned_type_node
, src
);
2265 /* We count the zeroes in src1, and add the number in src2 when src1
2268 std::swap (src1
, src2
);
2269 tree call1
= build_call_expr (fn
, 1, src1
);
2270 tree call2
= build_call_expr (fn
, 1, src2
);
2273 tree is_zero2
= fold_build2 (NE_EXPR
, boolean_type_node
, src2
,
2274 build_zero_cst (TREE_TYPE (src2
)));
2275 call2
= fold_build3 (COND_EXPR
, integer_type_node
, is_zero2
, call2
,
2276 build_int_cst (integer_type_node
, lli_prec
));
2278 tree is_zero1
= fold_build2 (NE_EXPR
, boolean_type_node
, src1
,
2279 build_zero_cst (TREE_TYPE (src1
)));
2280 call
= fold_build3 (COND_EXPR
, integer_type_node
, is_zero1
, call1
,
2281 fold_build2 (PLUS_EXPR
, integer_type_node
, call2
,
2282 build_int_cst (integer_type_node
,
2288 src
= fold_convert (unsigned_type_node
, src
);
2290 call
= build_call_expr (fn
, 1, src
);
2293 tree is_zero
= fold_build2 (NE_EXPR
, boolean_type_node
, src
,
2294 build_zero_cst (TREE_TYPE (src
)));
2295 call
= fold_build3 (COND_EXPR
, integer_type_node
, is_zero
, call
,
2296 build_int_cst (integer_type_node
, prec
));
2299 if (leading
&& prec
< i_prec
)
2300 call
= fold_build2 (MINUS_EXPR
, integer_type_node
, call
,
2301 build_int_cst (integer_type_node
, i_prec
- prec
));
2307 /* See comment below for number_of_iterations_bitcount.
2308 For c[lt]z, we have:
2311 iv_2 = iv_1 << 1 OR iv_1 >> 1
2314 if (iv & 1 << (prec-1)) OR (iv & 1)
2317 src precision - c[lt]z (src)
2322 number_of_iterations_cltz (loop_p loop
, edge exit
,
2323 enum tree_code code
,
2324 class tree_niter_desc
*niter
)
2326 bool modify_before_test
= true;
2331 /* Check that condition for staying inside the loop is like
2333 gcond
*cond_stmt
= safe_dyn_cast
<gcond
*> (*gsi_last_bb (exit
->src
));
2335 || (code
!= EQ_EXPR
&& code
!= GE_EXPR
)
2336 || !integer_zerop (gimple_cond_rhs (cond_stmt
))
2337 || TREE_CODE (gimple_cond_lhs (cond_stmt
)) != SSA_NAME
)
2340 if (code
== EQ_EXPR
)
2342 /* Make sure we check a bitwise and with a suitable constant */
2343 gimple
*and_stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (cond_stmt
));
2344 if (!is_gimple_assign (and_stmt
)
2345 || gimple_assign_rhs_code (and_stmt
) != BIT_AND_EXPR
2346 || !integer_pow2p (gimple_assign_rhs2 (and_stmt
))
2347 || TREE_CODE (gimple_assign_rhs1 (and_stmt
)) != SSA_NAME
)
2350 checked_bit
= tree_log2 (gimple_assign_rhs2 (and_stmt
));
2352 iv_2
= gimple_assign_rhs1 (and_stmt
);
2356 /* We have a GE_EXPR - a signed comparison with zero is equivalent to
2357 testing the leading bit, so check for this pattern too. */
2359 iv_2
= gimple_cond_lhs (cond_stmt
);
2360 tree test_value_type
= TREE_TYPE (iv_2
);
2362 if (TYPE_UNSIGNED (test_value_type
))
2365 gimple
*test_value_stmt
= SSA_NAME_DEF_STMT (iv_2
);
2367 if (is_gimple_assign (test_value_stmt
)
2368 && gimple_assign_rhs_code (test_value_stmt
) == NOP_EXPR
)
2370 /* If the test value comes from a NOP_EXPR, then we need to unwrap
2371 this. We conservatively require that both types have the same
2373 iv_2
= gimple_assign_rhs1 (test_value_stmt
);
2374 tree rhs_type
= TREE_TYPE (iv_2
);
2375 if (TREE_CODE (iv_2
) != SSA_NAME
2376 || TREE_CODE (rhs_type
) != INTEGER_TYPE
2377 || (TYPE_PRECISION (rhs_type
)
2378 != TYPE_PRECISION (test_value_type
)))
2382 checked_bit
= TYPE_PRECISION (test_value_type
) - 1;
2385 gimple
*iv_2_stmt
= SSA_NAME_DEF_STMT (iv_2
);
2387 /* If the test comes before the iv modification, then these will actually be
2388 iv_1 and a phi node. */
2389 if (gimple_code (iv_2_stmt
) == GIMPLE_PHI
2390 && gimple_bb (iv_2_stmt
) == loop
->header
2391 && gimple_phi_num_args (iv_2_stmt
) == 2
2392 && (TREE_CODE (gimple_phi_arg_def (iv_2_stmt
,
2393 loop_latch_edge (loop
)->dest_idx
))
2396 /* iv_2 is actually one of the inputs to the phi. */
2397 iv_2
= gimple_phi_arg_def (iv_2_stmt
, loop_latch_edge (loop
)->dest_idx
);
2398 iv_2_stmt
= SSA_NAME_DEF_STMT (iv_2
);
2399 modify_before_test
= false;
2402 /* Make sure iv_2_stmt is a logical shift by one stmt:
2403 iv_2 = iv_1 {<<|>>} 1 */
2404 if (!is_gimple_assign (iv_2_stmt
)
2405 || (gimple_assign_rhs_code (iv_2_stmt
) != LSHIFT_EXPR
2406 && (gimple_assign_rhs_code (iv_2_stmt
) != RSHIFT_EXPR
2407 || !TYPE_UNSIGNED (TREE_TYPE (gimple_assign_lhs (iv_2_stmt
)))))
2408 || !integer_onep (gimple_assign_rhs2 (iv_2_stmt
)))
2411 bool left_shift
= (gimple_assign_rhs_code (iv_2_stmt
) == LSHIFT_EXPR
);
2413 tree iv_1
= gimple_assign_rhs1 (iv_2_stmt
);
2415 /* Check the recurrence. */
2416 gimple
*phi
= SSA_NAME_DEF_STMT (iv_1
);
2417 if (gimple_code (phi
) != GIMPLE_PHI
2418 || (gimple_bb (phi
) != loop_latch_edge (loop
)->dest
)
2419 || (iv_2
!= gimple_phi_arg_def (phi
, loop_latch_edge (loop
)->dest_idx
)))
2422 /* We found a match. */
2423 tree src
= gimple_phi_arg_def (phi
, loop_preheader_edge (loop
)->dest_idx
);
2424 int src_precision
= TYPE_PRECISION (TREE_TYPE (src
));
2426 /* Apply any needed preprocessing to src. */
2427 int num_ignored_bits
;
2429 num_ignored_bits
= src_precision
- checked_bit
- 1;
2431 num_ignored_bits
= checked_bit
;
2433 if (modify_before_test
)
2436 if (num_ignored_bits
!= 0)
2437 src
= fold_build2 (left_shift
? LSHIFT_EXPR
: RSHIFT_EXPR
,
2438 TREE_TYPE (src
), src
,
2439 build_int_cst (integer_type_node
, num_ignored_bits
));
2441 /* Get the corresponding c[lt]z builtin. */
2442 tree expr
= build_cltz_expr (src
, left_shift
, false);
2447 max
= src_precision
- num_ignored_bits
- 1;
2449 expr
= fold_convert (unsigned_type_node
, expr
);
2451 tree assumptions
= fold_build2 (NE_EXPR
, boolean_type_node
, src
,
2452 build_zero_cst (TREE_TYPE (src
)));
2454 niter
->assumptions
= simplify_using_initial_conditions (loop
, assumptions
);
2455 niter
->may_be_zero
= boolean_false_node
;
2456 niter
->niter
= simplify_using_initial_conditions (loop
, expr
);
2458 if (TREE_CODE (niter
->niter
) == INTEGER_CST
)
2459 niter
->max
= tree_to_uhwi (niter
->niter
);
2463 niter
->bound
= NULL_TREE
;
2464 niter
->cmp
= ERROR_MARK
;
2469 /* See comment below for number_of_iterations_bitcount.
2470 For c[lt]z complement, we have:
2473 iv_2 = iv_1 >> 1 OR iv_1 << 1
2479 src precision - c[lt]z (src)
2484 number_of_iterations_cltz_complement (loop_p loop
, edge exit
,
2485 enum tree_code code
,
2486 class tree_niter_desc
*niter
)
2488 bool modify_before_test
= true;
2491 /* Check that condition for staying inside the loop is like
2493 gcond
*cond_stmt
= safe_dyn_cast
<gcond
*> (*gsi_last_bb (exit
->src
));
2496 || !integer_zerop (gimple_cond_rhs (cond_stmt
))
2497 || TREE_CODE (gimple_cond_lhs (cond_stmt
)) != SSA_NAME
)
2500 tree iv_2
= gimple_cond_lhs (cond_stmt
);
2501 gimple
*iv_2_stmt
= SSA_NAME_DEF_STMT (iv_2
);
2503 /* If the test comes before the iv modification, then these will actually be
2504 iv_1 and a phi node. */
2505 if (gimple_code (iv_2_stmt
) == GIMPLE_PHI
2506 && gimple_bb (iv_2_stmt
) == loop
->header
2507 && gimple_phi_num_args (iv_2_stmt
) == 2
2508 && (TREE_CODE (gimple_phi_arg_def (iv_2_stmt
,
2509 loop_latch_edge (loop
)->dest_idx
))
2512 /* iv_2 is actually one of the inputs to the phi. */
2513 iv_2
= gimple_phi_arg_def (iv_2_stmt
, loop_latch_edge (loop
)->dest_idx
);
2514 iv_2_stmt
= SSA_NAME_DEF_STMT (iv_2
);
2515 modify_before_test
= false;
2518 /* Make sure iv_2_stmt is a logical shift by one stmt:
2519 iv_2 = iv_1 {>>|<<} 1 */
2520 if (!is_gimple_assign (iv_2_stmt
)
2521 || (gimple_assign_rhs_code (iv_2_stmt
) != LSHIFT_EXPR
2522 && (gimple_assign_rhs_code (iv_2_stmt
) != RSHIFT_EXPR
2523 || !TYPE_UNSIGNED (TREE_TYPE (gimple_assign_lhs (iv_2_stmt
)))))
2524 || !integer_onep (gimple_assign_rhs2 (iv_2_stmt
)))
2527 bool left_shift
= (gimple_assign_rhs_code (iv_2_stmt
) == LSHIFT_EXPR
);
2529 tree iv_1
= gimple_assign_rhs1 (iv_2_stmt
);
2531 /* Check the recurrence. */
2532 gimple
*phi
= SSA_NAME_DEF_STMT (iv_1
);
2533 if (gimple_code (phi
) != GIMPLE_PHI
2534 || (gimple_bb (phi
) != loop_latch_edge (loop
)->dest
)
2535 || (iv_2
!= gimple_phi_arg_def (phi
, loop_latch_edge (loop
)->dest_idx
)))
2538 /* We found a match. */
2539 tree src
= gimple_phi_arg_def (phi
, loop_preheader_edge (loop
)->dest_idx
);
2540 int src_precision
= TYPE_PRECISION (TREE_TYPE (src
));
2542 /* Get the corresponding c[lt]z builtin. */
2543 tree expr
= build_cltz_expr (src
, !left_shift
, true);
2548 expr
= fold_build2 (MINUS_EXPR
, integer_type_node
,
2549 build_int_cst (integer_type_node
, src_precision
),
2552 max
= src_precision
;
2554 tree may_be_zero
= boolean_false_node
;
2556 if (modify_before_test
)
2558 expr
= fold_build2 (MINUS_EXPR
, integer_type_node
, expr
,
2561 may_be_zero
= fold_build2 (EQ_EXPR
, boolean_type_node
, src
,
2562 build_zero_cst (TREE_TYPE (src
)));
2565 expr
= fold_convert (unsigned_type_node
, expr
);
2567 niter
->assumptions
= boolean_true_node
;
2568 niter
->may_be_zero
= simplify_using_initial_conditions (loop
, may_be_zero
);
2569 niter
->niter
= simplify_using_initial_conditions (loop
, expr
);
2571 if (TREE_CODE (niter
->niter
) == INTEGER_CST
)
2572 niter
->max
= tree_to_uhwi (niter
->niter
);
2576 niter
->bound
= NULL_TREE
;
2577 niter
->cmp
= ERROR_MARK
;
2581 /* See if LOOP contains a bit counting idiom. The idiom consists of two parts:
2582 1. A modification to the induction variabler;.
2583 2. A test to determine whether or not to exit the loop.
2585 These can come in either order - i.e.:
2588 iv_1 = PHI <src(2), iv_2(4)>
2595 iv_2 = modify (iv_1)
2601 iv_1 = PHI <src(2), iv_2(4)>
2602 iv_2 = modify (iv_1)
2610 The second form can be generated by copying the loop header out of the loop.
2612 In the first case, the number of latch executions will be equal to the
2613 number of induction variable modifications required before the test fails.
2615 In the second case (modify_before_test), if we assume that the number of
2616 modifications required before the test fails is nonzero, then the number of
2617 latch executions will be one less than this number.
2619 If we recognise the pattern, then we update niter accordingly, and return
2623 number_of_iterations_bitcount (loop_p loop
, edge exit
,
2624 enum tree_code code
,
2625 class tree_niter_desc
*niter
)
2627 return (number_of_iterations_popcount (loop
, exit
, code
, niter
)
2628 || number_of_iterations_cltz (loop
, exit
, code
, niter
)
2629 || number_of_iterations_cltz_complement (loop
, exit
, code
, niter
));
2632 /* Substitute NEW_TREE for OLD in EXPR and fold the result.
2633 If VALUEIZE is non-NULL then OLD and NEW_TREE are ignored and instead
2634 all SSA names are replaced with the result of calling the VALUEIZE
2635 function with the SSA name as argument. */
2638 simplify_replace_tree (tree expr
, tree old
, tree new_tree
,
2639 tree (*valueize
) (tree
, void*), void *context
,
2643 tree ret
= NULL_TREE
, e
, se
;
2648 /* Do not bother to replace constants. */
2649 if (CONSTANT_CLASS_P (expr
))
2654 if (TREE_CODE (expr
) == SSA_NAME
)
2656 new_tree
= valueize (expr
, context
);
2657 if (new_tree
!= expr
)
2661 else if (expr
== old
2662 || operand_equal_p (expr
, old
, 0))
2663 return unshare_expr (new_tree
);
2668 n
= TREE_OPERAND_LENGTH (expr
);
2669 for (i
= 0; i
< n
; i
++)
2671 e
= TREE_OPERAND (expr
, i
);
2672 se
= simplify_replace_tree (e
, old
, new_tree
, valueize
, context
, do_fold
);
2677 ret
= copy_node (expr
);
2679 TREE_OPERAND (ret
, i
) = se
;
2682 return (ret
? (do_fold
? fold (ret
) : ret
) : expr
);
2685 /* Expand definitions of ssa names in EXPR as long as they are simple
2686 enough, and return the new expression. If STOP is specified, stop
2687 expanding if EXPR equals to it. */
2690 expand_simple_operations (tree expr
, tree stop
, hash_map
<tree
, tree
> &cache
)
2693 tree ret
= NULL_TREE
, e
, ee
, e1
;
2694 enum tree_code code
;
2697 if (expr
== NULL_TREE
)
2700 if (is_gimple_min_invariant (expr
))
2703 code
= TREE_CODE (expr
);
2704 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
2706 n
= TREE_OPERAND_LENGTH (expr
);
2707 for (i
= 0; i
< n
; i
++)
2709 e
= TREE_OPERAND (expr
, i
);
2712 /* SCEV analysis feeds us with a proper expression
2713 graph matching the SSA graph. Avoid turning it
2714 into a tree here, thus handle tree sharing
2716 ??? The SSA walk below still turns the SSA graph
2717 into a tree but until we find a testcase do not
2718 introduce additional tree sharing here. */
2720 tree
&cee
= cache
.get_or_insert (e
, &existed_p
);
2726 ee
= expand_simple_operations (e
, stop
, cache
);
2728 *cache
.get (e
) = ee
;
2734 ret
= copy_node (expr
);
2736 TREE_OPERAND (ret
, i
) = ee
;
2742 fold_defer_overflow_warnings ();
2744 fold_undefer_and_ignore_overflow_warnings ();
2748 /* Stop if it's not ssa name or the one we don't want to expand. */
2749 if (TREE_CODE (expr
) != SSA_NAME
|| expr
== stop
)
2752 stmt
= SSA_NAME_DEF_STMT (expr
);
2753 if (gimple_code (stmt
) == GIMPLE_PHI
)
2755 basic_block src
, dest
;
2757 if (gimple_phi_num_args (stmt
) != 1)
2759 e
= PHI_ARG_DEF (stmt
, 0);
2761 /* Avoid propagating through loop exit phi nodes, which
2762 could break loop-closed SSA form restrictions. */
2763 dest
= gimple_bb (stmt
);
2764 src
= single_pred (dest
);
2765 if (TREE_CODE (e
) == SSA_NAME
2766 && src
->loop_father
!= dest
->loop_father
)
2769 return expand_simple_operations (e
, stop
, cache
);
2771 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2774 /* Avoid expanding to expressions that contain SSA names that need
2775 to take part in abnormal coalescing. */
2777 FOR_EACH_SSA_TREE_OPERAND (e
, stmt
, iter
, SSA_OP_USE
)
2778 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (e
))
2781 e
= gimple_assign_rhs1 (stmt
);
2782 code
= gimple_assign_rhs_code (stmt
);
2783 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
2785 if (is_gimple_min_invariant (e
))
2788 if (code
== SSA_NAME
)
2789 return expand_simple_operations (e
, stop
, cache
);
2790 else if (code
== ADDR_EXPR
)
2793 tree base
= get_addr_base_and_unit_offset (TREE_OPERAND (e
, 0),
2796 && TREE_CODE (base
) == MEM_REF
)
2798 ee
= expand_simple_operations (TREE_OPERAND (base
, 0), stop
,
2800 return fold_build2 (POINTER_PLUS_EXPR
, TREE_TYPE (expr
), ee
,
2801 wide_int_to_tree (sizetype
,
2802 mem_ref_offset (base
)
2813 /* Casts are simple. */
2814 ee
= expand_simple_operations (e
, stop
, cache
);
2815 return fold_build1 (code
, TREE_TYPE (expr
), ee
);
2820 if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (expr
))
2821 && TYPE_OVERFLOW_TRAPS (TREE_TYPE (expr
)))
2824 case POINTER_PLUS_EXPR
:
2825 /* And increments and decrements by a constant are simple. */
2826 e1
= gimple_assign_rhs2 (stmt
);
2827 if (!is_gimple_min_invariant (e1
))
2830 ee
= expand_simple_operations (e
, stop
, cache
);
2831 return fold_build2 (code
, TREE_TYPE (expr
), ee
, e1
);
2839 expand_simple_operations (tree expr
, tree stop
)
2841 hash_map
<tree
, tree
> cache
;
2842 return expand_simple_operations (expr
, stop
, cache
);
2845 /* Tries to simplify EXPR using the condition COND. Returns the simplified
2846 expression (or EXPR unchanged, if no simplification was possible). */
2849 tree_simplify_using_condition_1 (tree cond
, tree expr
)
2852 tree e
, e0
, e1
, e2
, notcond
;
2853 enum tree_code code
= TREE_CODE (expr
);
2855 if (code
== INTEGER_CST
)
2858 if (code
== TRUTH_OR_EXPR
2859 || code
== TRUTH_AND_EXPR
2860 || code
== COND_EXPR
)
2864 e0
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 0));
2865 if (TREE_OPERAND (expr
, 0) != e0
)
2868 e1
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 1));
2869 if (TREE_OPERAND (expr
, 1) != e1
)
2872 if (code
== COND_EXPR
)
2874 e2
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 2));
2875 if (TREE_OPERAND (expr
, 2) != e2
)
2883 if (code
== COND_EXPR
)
2884 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
2886 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
2892 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
2893 propagation, and vice versa. Fold does not handle this, since it is
2894 considered too expensive. */
2895 if (TREE_CODE (cond
) == EQ_EXPR
)
2897 e0
= TREE_OPERAND (cond
, 0);
2898 e1
= TREE_OPERAND (cond
, 1);
2900 /* We know that e0 == e1. Check whether we cannot simplify expr
2902 e
= simplify_replace_tree (expr
, e0
, e1
);
2903 if (integer_zerop (e
) || integer_nonzerop (e
))
2906 e
= simplify_replace_tree (expr
, e1
, e0
);
2907 if (integer_zerop (e
) || integer_nonzerop (e
))
2910 if (TREE_CODE (expr
) == EQ_EXPR
)
2912 e0
= TREE_OPERAND (expr
, 0);
2913 e1
= TREE_OPERAND (expr
, 1);
2915 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
2916 e
= simplify_replace_tree (cond
, e0
, e1
);
2917 if (integer_zerop (e
))
2919 e
= simplify_replace_tree (cond
, e1
, e0
);
2920 if (integer_zerop (e
))
2923 if (TREE_CODE (expr
) == NE_EXPR
)
2925 e0
= TREE_OPERAND (expr
, 0);
2926 e1
= TREE_OPERAND (expr
, 1);
2928 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
2929 e
= simplify_replace_tree (cond
, e0
, e1
);
2930 if (integer_zerop (e
))
2931 return boolean_true_node
;
2932 e
= simplify_replace_tree (cond
, e1
, e0
);
2933 if (integer_zerop (e
))
2934 return boolean_true_node
;
2937 /* Check whether COND ==> EXPR. */
2938 notcond
= invert_truthvalue (cond
);
2939 e
= fold_binary (TRUTH_OR_EXPR
, boolean_type_node
, notcond
, expr
);
2940 if (e
&& integer_nonzerop (e
))
2943 /* Check whether COND ==> not EXPR. */
2944 e
= fold_binary (TRUTH_AND_EXPR
, boolean_type_node
, cond
, expr
);
2945 if (e
&& integer_zerop (e
))
2951 /* Tries to simplify EXPR using the condition COND. Returns the simplified
2952 expression (or EXPR unchanged, if no simplification was possible).
2953 Wrapper around tree_simplify_using_condition_1 that ensures that chains
2954 of simple operations in definitions of ssa names in COND are expanded,
2955 so that things like casts or incrementing the value of the bound before
2956 the loop do not cause us to fail. */
2959 tree_simplify_using_condition (tree cond
, tree expr
)
2961 cond
= expand_simple_operations (cond
);
2963 return tree_simplify_using_condition_1 (cond
, expr
);
2966 /* Tries to simplify EXPR using the conditions on entry to LOOP.
2967 Returns the simplified expression (or EXPR unchanged, if no
2968 simplification was possible). */
2971 simplify_using_initial_conditions (class loop
*loop
, tree expr
)
2975 tree cond
, expanded
, backup
;
2978 if (TREE_CODE (expr
) == INTEGER_CST
)
2981 backup
= expanded
= expand_simple_operations (expr
);
2983 /* Limit walking the dominators to avoid quadraticness in
2984 the number of BBs times the number of loops in degenerate
2986 for (bb
= loop
->header
;
2987 bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && cnt
< MAX_DOMINATORS_TO_WALK
;
2988 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
2990 if (!single_pred_p (bb
))
2992 e
= single_pred_edge (bb
);
2994 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
2997 gcond
*stmt
= as_a
<gcond
*> (*gsi_last_bb (e
->src
));
2998 cond
= fold_build2 (gimple_cond_code (stmt
),
3000 gimple_cond_lhs (stmt
),
3001 gimple_cond_rhs (stmt
));
3002 if (e
->flags
& EDGE_FALSE_VALUE
)
3003 cond
= invert_truthvalue (cond
);
3004 expanded
= tree_simplify_using_condition (cond
, expanded
);
3005 /* Break if EXPR is simplified to const values. */
3007 && (integer_zerop (expanded
) || integer_nonzerop (expanded
)))
3013 /* Return the original expression if no simplification is done. */
3014 return operand_equal_p (backup
, expanded
, 0) ? expr
: expanded
;
3017 /* Tries to simplify EXPR using the evolutions of the loop invariants
3018 in the superloops of LOOP. Returns the simplified expression
3019 (or EXPR unchanged, if no simplification was possible). */
3022 simplify_using_outer_evolutions (class loop
*loop
, tree expr
)
3024 enum tree_code code
= TREE_CODE (expr
);
3028 if (is_gimple_min_invariant (expr
))
3031 if (code
== TRUTH_OR_EXPR
3032 || code
== TRUTH_AND_EXPR
3033 || code
== COND_EXPR
)
3037 e0
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 0));
3038 if (TREE_OPERAND (expr
, 0) != e0
)
3041 e1
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 1));
3042 if (TREE_OPERAND (expr
, 1) != e1
)
3045 if (code
== COND_EXPR
)
3047 e2
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 2));
3048 if (TREE_OPERAND (expr
, 2) != e2
)
3056 if (code
== COND_EXPR
)
3057 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
3059 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
3065 e
= instantiate_parameters (loop
, expr
);
3066 if (is_gimple_min_invariant (e
))
3072 /* Returns true if EXIT is the only possible exit from LOOP. */
3075 loop_only_exit_p (const class loop
*loop
, basic_block
*body
, const_edge exit
)
3077 gimple_stmt_iterator bsi
;
3080 if (exit
!= single_exit (loop
))
3083 for (i
= 0; i
< loop
->num_nodes
; i
++)
3084 for (bsi
= gsi_start_bb (body
[i
]); !gsi_end_p (bsi
); gsi_next (&bsi
))
3085 if (stmt_can_terminate_bb_p (gsi_stmt (bsi
)))
3091 /* Stores description of number of iterations of LOOP derived from
3092 EXIT (an exit edge of the LOOP) in NITER. Returns true if some useful
3093 information could be derived (and fields of NITER have meaning described
3094 in comments at class tree_niter_desc declaration), false otherwise.
3095 When EVERY_ITERATION is true, only tests that are known to be executed
3096 every iteration are considered (i.e. only test that alone bounds the loop).
3097 If AT_STMT is not NULL, this function stores LOOP's condition statement in
3098 it when returning true. */
3101 number_of_iterations_exit_assumptions (class loop
*loop
, edge exit
,
3102 class tree_niter_desc
*niter
,
3103 gcond
**at_stmt
, bool every_iteration
,
3108 enum tree_code code
;
3112 /* The condition at a fake exit (if it exists) does not control its
3114 if (exit
->flags
& EDGE_FAKE
)
3117 /* Nothing to analyze if the loop is known to be infinite. */
3118 if (loop_constraint_set_p (loop
, LOOP_C_INFINITE
))
3121 safe
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit
->src
);
3123 if (every_iteration
&& !safe
)
3126 niter
->assumptions
= boolean_false_node
;
3127 niter
->control
.base
= NULL_TREE
;
3128 niter
->control
.step
= NULL_TREE
;
3129 niter
->control
.no_overflow
= false;
3130 gcond
*stmt
= safe_dyn_cast
<gcond
*> (*gsi_last_bb (exit
->src
));
3137 /* We want the condition for staying inside loop. */
3138 code
= gimple_cond_code (stmt
);
3139 if (exit
->flags
& EDGE_TRUE_VALUE
)
3140 code
= invert_tree_comparison (code
, false);
3152 return number_of_iterations_cltz (loop
, exit
, code
, niter
);
3158 op0
= gimple_cond_lhs (stmt
);
3159 op1
= gimple_cond_rhs (stmt
);
3160 type
= TREE_TYPE (op0
);
3162 if (TREE_CODE (type
) != INTEGER_TYPE
3163 && !POINTER_TYPE_P (type
))
3166 tree iv0_niters
= NULL_TREE
;
3167 if (!simple_iv_with_niters (loop
, loop_containing_stmt (stmt
),
3168 op0
, &iv0
, safe
? &iv0_niters
: NULL
, false))
3169 return number_of_iterations_bitcount (loop
, exit
, code
, niter
);
3170 tree iv1_niters
= NULL_TREE
;
3171 if (!simple_iv_with_niters (loop
, loop_containing_stmt (stmt
),
3172 op1
, &iv1
, safe
? &iv1_niters
: NULL
, false))
3174 /* Give up on complicated case. */
3175 if (iv0_niters
&& iv1_niters
)
3178 /* We don't want to see undefined signed overflow warnings while
3179 computing the number of iterations. */
3180 fold_defer_overflow_warnings ();
3182 iv0
.base
= expand_simple_operations (iv0
.base
);
3183 iv1
.base
= expand_simple_operations (iv1
.base
);
3184 bool body_from_caller
= true;
3187 body
= get_loop_body (loop
);
3188 body_from_caller
= false;
3190 bool only_exit_p
= loop_only_exit_p (loop
, body
, exit
);
3191 if (!body_from_caller
)
3193 if (!number_of_iterations_cond (loop
, type
, &iv0
, code
, &iv1
, niter
,
3196 fold_undefer_and_ignore_overflow_warnings ();
3200 /* Incorporate additional assumption implied by control iv. */
3201 tree iv_niters
= iv0_niters
? iv0_niters
: iv1_niters
;
3204 tree assumption
= fold_build2 (LE_EXPR
, boolean_type_node
, niter
->niter
,
3205 fold_convert (TREE_TYPE (niter
->niter
),
3208 if (!integer_nonzerop (assumption
))
3209 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
3210 niter
->assumptions
, assumption
);
3212 /* Refine upper bound if possible. */
3213 if (TREE_CODE (iv_niters
) == INTEGER_CST
3214 && niter
->max
> wi::to_widest (iv_niters
))
3215 niter
->max
= wi::to_widest (iv_niters
);
3218 /* There is no assumptions if the loop is known to be finite. */
3219 if (!integer_zerop (niter
->assumptions
)
3220 && loop_constraint_set_p (loop
, LOOP_C_FINITE
))
3221 niter
->assumptions
= boolean_true_node
;
3225 niter
->assumptions
= simplify_using_outer_evolutions (loop
,
3226 niter
->assumptions
);
3227 niter
->may_be_zero
= simplify_using_outer_evolutions (loop
,
3228 niter
->may_be_zero
);
3229 niter
->niter
= simplify_using_outer_evolutions (loop
, niter
->niter
);
3233 = simplify_using_initial_conditions (loop
,
3234 niter
->assumptions
);
3236 = simplify_using_initial_conditions (loop
,
3237 niter
->may_be_zero
);
3239 fold_undefer_and_ignore_overflow_warnings ();
3241 /* If NITER has simplified into a constant, update MAX. */
3242 if (TREE_CODE (niter
->niter
) == INTEGER_CST
)
3243 niter
->max
= wi::to_widest (niter
->niter
);
3245 return (!integer_zerop (niter
->assumptions
));
3248 /* Like number_of_iterations_exit_assumptions, but return TRUE only if
3249 the niter information holds unconditionally. */
3252 number_of_iterations_exit (class loop
*loop
, edge exit
,
3253 class tree_niter_desc
*niter
,
3254 bool warn
, bool every_iteration
,
3258 if (!number_of_iterations_exit_assumptions (loop
, exit
, niter
,
3259 &stmt
, every_iteration
, body
))
3262 if (integer_nonzerop (niter
->assumptions
))
3265 if (warn
&& dump_enabled_p ())
3266 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, stmt
,
3267 "missed loop optimization: niters analysis ends up "
3268 "with assumptions.\n");
3273 /* Try to determine the number of iterations of LOOP. If we succeed,
3274 expression giving number of iterations is returned and *EXIT is
3275 set to the edge from that the information is obtained. Otherwise
3276 chrec_dont_know is returned. */
3279 find_loop_niter (class loop
*loop
, edge
*exit
)
3282 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
);
3284 tree niter
= NULL_TREE
, aniter
;
3285 class tree_niter_desc desc
;
3288 FOR_EACH_VEC_ELT (exits
, i
, ex
)
3290 if (!number_of_iterations_exit (loop
, ex
, &desc
, false))
3293 if (integer_nonzerop (desc
.may_be_zero
))
3295 /* We exit in the first iteration through this exit.
3296 We won't find anything better. */
3297 niter
= build_int_cst (unsigned_type_node
, 0);
3302 if (!integer_zerop (desc
.may_be_zero
))
3305 aniter
= desc
.niter
;
3309 /* Nothing recorded yet. */
3315 /* Prefer constants, the lower the better. */
3316 if (TREE_CODE (aniter
) != INTEGER_CST
)
3319 if (TREE_CODE (niter
) != INTEGER_CST
)
3326 if (tree_int_cst_lt (aniter
, niter
))
3334 return niter
? niter
: chrec_dont_know
;
3337 /* Return true if loop is known to have bounded number of iterations. */
3340 finite_loop_p (class loop
*loop
)
3348 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
);
3351 /* If the loop has a normal exit, we can assume it will terminate. */
3352 FOR_EACH_VEC_ELT (exits
, i
, ex
)
3353 if (!(ex
->flags
& (EDGE_EH
| EDGE_ABNORMAL
| EDGE_FAKE
)))
3356 fprintf (dump_file
, "Assume loop %i to be finite: it has an exit "
3357 "and -ffinite-loops is on or loop was "
3358 "previously finite.\n",
3364 flags
= flags_from_decl_or_type (current_function_decl
);
3365 if ((flags
& (ECF_CONST
|ECF_PURE
)) && !(flags
& ECF_LOOPING_CONST_OR_PURE
))
3367 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3369 "Found loop %i to be finite: it is within "
3370 "pure or const function.\n",
3372 loop
->finite_p
= true;
3376 if (loop
->any_upper_bound
3377 /* Loop with no normal exit will not pass max_loop_iterations. */
3378 || (!loop
->finite_p
&& max_loop_iterations (loop
, &nit
)))
3380 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3381 fprintf (dump_file
, "Found loop %i to be finite: upper bound found.\n",
3383 loop
->finite_p
= true;
3392 Analysis of a number of iterations of a loop by a brute-force evaluation.
3396 /* Bound on the number of iterations we try to evaluate. */
3398 #define MAX_ITERATIONS_TO_TRACK \
3399 ((unsigned) param_max_iterations_to_track)
3401 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
3402 result by a chain of operations such that all but exactly one of their
3403 operands are constants. */
3406 chain_of_csts_start (class loop
*loop
, tree x
)
3408 gimple
*stmt
= SSA_NAME_DEF_STMT (x
);
3410 basic_block bb
= gimple_bb (stmt
);
3411 enum tree_code code
;
3414 || !flow_bb_inside_loop_p (loop
, bb
))
3417 if (gimple_code (stmt
) == GIMPLE_PHI
)
3419 if (bb
== loop
->header
)
3420 return as_a
<gphi
*> (stmt
);
3425 if (gimple_code (stmt
) != GIMPLE_ASSIGN
3426 || gimple_assign_rhs_class (stmt
) == GIMPLE_TERNARY_RHS
)
3429 code
= gimple_assign_rhs_code (stmt
);
3430 if (gimple_references_memory_p (stmt
)
3431 || TREE_CODE_CLASS (code
) == tcc_reference
3432 || (code
== ADDR_EXPR
3433 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
3436 use
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
3437 if (use
== NULL_TREE
)
3440 return chain_of_csts_start (loop
, use
);
3443 /* Determines whether the expression X is derived from a result of a phi node
3444 in header of LOOP such that
3446 * the derivation of X consists only from operations with constants
3447 * the initial value of the phi node is constant
3448 * the value of the phi node in the next iteration can be derived from the
3449 value in the current iteration by a chain of operations with constants,
3450 or is also a constant
3452 If such phi node exists, it is returned, otherwise NULL is returned. */
3455 get_base_for (class loop
*loop
, tree x
)
3460 if (is_gimple_min_invariant (x
))
3463 phi
= chain_of_csts_start (loop
, x
);
3467 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
3468 next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
3470 if (!is_gimple_min_invariant (init
))
3473 if (TREE_CODE (next
) == SSA_NAME
3474 && chain_of_csts_start (loop
, next
) != phi
)
3480 /* Given an expression X, then
3482 * if X is NULL_TREE, we return the constant BASE.
3483 * if X is a constant, we return the constant X.
3484 * otherwise X is a SSA name, whose value in the considered loop is derived
3485 by a chain of operations with constant from a result of a phi node in
3486 the header of the loop. Then we return value of X when the value of the
3487 result of this phi node is given by the constant BASE. */
3490 get_val_for (tree x
, tree base
)
3494 gcc_checking_assert (is_gimple_min_invariant (base
));
3498 else if (is_gimple_min_invariant (x
))
3501 stmt
= SSA_NAME_DEF_STMT (x
);
3502 if (gimple_code (stmt
) == GIMPLE_PHI
)
3505 gcc_checking_assert (is_gimple_assign (stmt
));
3507 /* STMT must be either an assignment of a single SSA name or an
3508 expression involving an SSA name and a constant. Try to fold that
3509 expression using the value for the SSA name. */
3510 if (gimple_assign_ssa_name_copy_p (stmt
))
3511 return get_val_for (gimple_assign_rhs1 (stmt
), base
);
3512 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_UNARY_RHS
3513 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
3514 return fold_build1 (gimple_assign_rhs_code (stmt
),
3515 TREE_TYPE (gimple_assign_lhs (stmt
)),
3516 get_val_for (gimple_assign_rhs1 (stmt
), base
));
3517 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_BINARY_RHS
)
3519 tree rhs1
= gimple_assign_rhs1 (stmt
);
3520 tree rhs2
= gimple_assign_rhs2 (stmt
);
3521 if (TREE_CODE (rhs1
) == SSA_NAME
)
3522 rhs1
= get_val_for (rhs1
, base
);
3523 else if (TREE_CODE (rhs2
) == SSA_NAME
)
3524 rhs2
= get_val_for (rhs2
, base
);
3527 return fold_build2 (gimple_assign_rhs_code (stmt
),
3528 TREE_TYPE (gimple_assign_lhs (stmt
)), rhs1
, rhs2
);
3535 /* Tries to count the number of iterations of LOOP till it exits by EXIT
3536 by brute force -- i.e. by determining the value of the operands of the
3537 condition at EXIT in first few iterations of the loop (assuming that
3538 these values are constant) and determining the first one in that the
3539 condition is not satisfied. Returns the constant giving the number
3540 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
3543 loop_niter_by_eval (class loop
*loop
, edge exit
)
3546 tree op
[2], val
[2], next
[2], aval
[2];
3551 gcond
*cond
= safe_dyn_cast
<gcond
*> (*gsi_last_bb (exit
->src
));
3553 return chrec_dont_know
;
3555 cmp
= gimple_cond_code (cond
);
3556 if (exit
->flags
& EDGE_TRUE_VALUE
)
3557 cmp
= invert_tree_comparison (cmp
, false);
3567 op
[0] = gimple_cond_lhs (cond
);
3568 op
[1] = gimple_cond_rhs (cond
);
3572 return chrec_dont_know
;
3575 for (j
= 0; j
< 2; j
++)
3577 if (is_gimple_min_invariant (op
[j
]))
3580 next
[j
] = NULL_TREE
;
3585 phi
= get_base_for (loop
, op
[j
]);
3587 return chrec_dont_know
;
3588 val
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
3589 next
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
3593 /* Don't issue signed overflow warnings. */
3594 fold_defer_overflow_warnings ();
3596 for (i
= 0; i
< MAX_ITERATIONS_TO_TRACK
; i
++)
3598 for (j
= 0; j
< 2; j
++)
3599 aval
[j
] = get_val_for (op
[j
], val
[j
]);
3601 acnd
= fold_binary (cmp
, boolean_type_node
, aval
[0], aval
[1]);
3602 if (acnd
&& integer_zerop (acnd
))
3604 fold_undefer_and_ignore_overflow_warnings ();
3605 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3607 "Proved that loop %d iterates %d times using brute force.\n",
3609 return build_int_cst (unsigned_type_node
, i
);
3612 for (j
= 0; j
< 2; j
++)
3615 val
[j
] = get_val_for (next
[j
], val
[j
]);
3616 if (!is_gimple_min_invariant (val
[j
]))
3618 fold_undefer_and_ignore_overflow_warnings ();
3619 return chrec_dont_know
;
3623 /* If the next iteration would use the same base values
3624 as the current one, there is no point looping further,
3625 all following iterations will be the same as this one. */
3626 if (val
[0] == aval
[0] && val
[1] == aval
[1])
3630 fold_undefer_and_ignore_overflow_warnings ();
3632 return chrec_dont_know
;
3635 /* Finds the exit of the LOOP by that the loop exits after a constant
3636 number of iterations and stores the exit edge to *EXIT. The constant
3637 giving the number of iterations of LOOP is returned. The number of
3638 iterations is determined using loop_niter_by_eval (i.e. by brute force
3639 evaluation). If we are unable to find the exit for that loop_niter_by_eval
3640 determines the number of iterations, chrec_dont_know is returned. */
3643 find_loop_niter_by_eval (class loop
*loop
, edge
*exit
)
3646 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
);
3648 tree niter
= NULL_TREE
, aniter
;
3652 /* Loops with multiple exits are expensive to handle and less important. */
3653 if (!flag_expensive_optimizations
3654 && exits
.length () > 1)
3655 return chrec_dont_know
;
3657 FOR_EACH_VEC_ELT (exits
, i
, ex
)
3659 if (!just_once_each_iteration_p (loop
, ex
->src
))
3662 aniter
= loop_niter_by_eval (loop
, ex
);
3663 if (chrec_contains_undetermined (aniter
))
3667 && !tree_int_cst_lt (aniter
, niter
))
3674 return niter
? niter
: chrec_dont_know
;
3679 Analysis of upper bounds on number of iterations of a loop.
3683 static widest_int
derive_constant_upper_bound_ops (tree
, tree
,
3684 enum tree_code
, tree
);
3686 /* Returns a constant upper bound on the value of the right-hand side of
3687 an assignment statement STMT. */
3690 derive_constant_upper_bound_assign (gimple
*stmt
)
3692 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3693 tree op0
= gimple_assign_rhs1 (stmt
);
3694 tree op1
= gimple_assign_rhs2 (stmt
);
3696 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt
)),
3700 /* Returns a constant upper bound on the value of expression VAL. VAL
3701 is considered to be unsigned. If its type is signed, its value must
3705 derive_constant_upper_bound (tree val
)
3707 enum tree_code code
;
3710 extract_ops_from_tree (val
, &code
, &op0
, &op1
, &op2
);
3711 return derive_constant_upper_bound_ops (TREE_TYPE (val
), op0
, code
, op1
);
3714 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
3715 whose type is TYPE. The expression is considered to be unsigned. If
3716 its type is signed, its value must be nonnegative. */
3719 derive_constant_upper_bound_ops (tree type
, tree op0
,
3720 enum tree_code code
, tree op1
)
3723 widest_int bnd
, max
, cst
;
3726 if (INTEGRAL_TYPE_P (type
))
3727 maxt
= TYPE_MAX_VALUE (type
);
3729 maxt
= upper_bound_in_type (type
, type
);
3731 max
= wi::to_widest (maxt
);
3736 return wi::to_widest (op0
);
3739 subtype
= TREE_TYPE (op0
);
3740 if (!TYPE_UNSIGNED (subtype
)
3741 /* If TYPE is also signed, the fact that VAL is nonnegative implies
3742 that OP0 is nonnegative. */
3743 && TYPE_UNSIGNED (type
)
3744 && !tree_expr_nonnegative_p (op0
))
3746 /* If we cannot prove that the casted expression is nonnegative,
3747 we cannot establish more useful upper bound than the precision
3748 of the type gives us. */
3752 /* We now know that op0 is an nonnegative value. Try deriving an upper
3754 bnd
= derive_constant_upper_bound (op0
);
3756 /* If the bound does not fit in TYPE, max. value of TYPE could be
3758 if (wi::ltu_p (max
, bnd
))
3764 case POINTER_PLUS_EXPR
:
3766 if (TREE_CODE (op1
) != INTEGER_CST
3767 || !tree_expr_nonnegative_p (op0
))
3770 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
3771 choose the most logical way how to treat this constant regardless
3772 of the signedness of the type. */
3773 cst
= wi::sext (wi::to_widest (op1
), TYPE_PRECISION (type
));
3774 if (code
!= MINUS_EXPR
)
3777 bnd
= derive_constant_upper_bound (op0
);
3779 if (wi::neg_p (cst
))
3782 /* Avoid CST == 0x80000... */
3783 if (wi::neg_p (cst
))
3786 /* OP0 + CST. We need to check that
3787 BND <= MAX (type) - CST. */
3789 widest_int mmax
= max
- cst
;
3790 if (wi::leu_p (bnd
, mmax
))
3797 /* OP0 - CST, where CST >= 0.
3799 If TYPE is signed, we have already verified that OP0 >= 0, and we
3800 know that the result is nonnegative. This implies that
3803 If TYPE is unsigned, we must additionally know that OP0 >= CST,
3804 otherwise the operation underflows.
3807 /* This should only happen if the type is unsigned; however, for
3808 buggy programs that use overflowing signed arithmetics even with
3809 -fno-wrapv, this condition may also be true for signed values. */
3810 if (wi::ltu_p (bnd
, cst
))
3813 if (TYPE_UNSIGNED (type
))
3815 tree tem
= fold_binary (GE_EXPR
, boolean_type_node
, op0
,
3816 wide_int_to_tree (type
, cst
));
3817 if (!tem
|| integer_nonzerop (tem
))
3826 case FLOOR_DIV_EXPR
:
3827 case EXACT_DIV_EXPR
:
3828 if (TREE_CODE (op1
) != INTEGER_CST
3829 || tree_int_cst_sign_bit (op1
))
3832 bnd
= derive_constant_upper_bound (op0
);
3833 return wi::udiv_floor (bnd
, wi::to_widest (op1
));
3836 if (TREE_CODE (op1
) != INTEGER_CST
3837 || tree_int_cst_sign_bit (op1
))
3839 return wi::to_widest (op1
);
3842 stmt
= SSA_NAME_DEF_STMT (op0
);
3843 if (gimple_code (stmt
) != GIMPLE_ASSIGN
3844 || gimple_assign_lhs (stmt
) != op0
)
3846 return derive_constant_upper_bound_assign (stmt
);
3853 /* Emit a -Waggressive-loop-optimizations warning if needed. */
3856 do_warn_aggressive_loop_optimizations (class loop
*loop
,
3857 widest_int i_bound
, gimple
*stmt
)
3859 /* Don't warn if the loop doesn't have known constant bound. */
3860 if (!loop
->nb_iterations
3861 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
3862 || !warn_aggressive_loop_optimizations
3863 /* To avoid warning multiple times for the same loop,
3864 only start warning when we preserve loops. */
3865 || (cfun
->curr_properties
& PROP_loops
) == 0
3866 /* Only warn once per loop. */
3867 || loop
->warned_aggressive_loop_optimizations
3868 /* Only warn if undefined behavior gives us lower estimate than the
3869 known constant bound. */
3870 || wi::cmpu (i_bound
, wi::to_widest (loop
->nb_iterations
)) >= 0
3871 /* And undefined behavior happens unconditionally. */
3872 || !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (stmt
)))
3875 edge e
= single_exit (loop
);
3879 gimple
*estmt
= last_nondebug_stmt (e
->src
);
3880 char buf
[WIDE_INT_PRINT_BUFFER_SIZE
], *p
;
3882 if (print_dec_buf_size (i_bound
, TYPE_SIGN (TREE_TYPE (loop
->nb_iterations
)),
3884 p
= XALLOCAVEC (char, len
);
3887 print_dec (i_bound
, p
, TYPE_SIGN (TREE_TYPE (loop
->nb_iterations
)));
3888 auto_diagnostic_group d
;
3889 if (warning_at (gimple_location (stmt
), OPT_Waggressive_loop_optimizations
,
3890 "iteration %s invokes undefined behavior", p
))
3891 inform (gimple_location (estmt
), "within this loop");
3892 loop
->warned_aggressive_loop_optimizations
= true;
3895 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
3896 is true if the loop is exited immediately after STMT, and this exit
3897 is taken at last when the STMT is executed BOUND + 1 times.
3898 REALISTIC is true if BOUND is expected to be close to the real number
3899 of iterations. UPPER is true if we are sure the loop iterates at most
3900 BOUND times. I_BOUND is a widest_int upper estimate on BOUND. */
3903 record_estimate (class loop
*loop
, tree bound
, const widest_int
&i_bound
,
3904 gimple
*at_stmt
, bool is_exit
, bool realistic
, bool upper
)
3908 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3910 fprintf (dump_file
, "Statement %s", is_exit
? "(exit)" : "");
3911 print_gimple_stmt (dump_file
, at_stmt
, 0, TDF_SLIM
);
3912 fprintf (dump_file
, " is %sexecuted at most ",
3913 upper
? "" : "probably ");
3914 print_generic_expr (dump_file
, bound
, TDF_SLIM
);
3915 fprintf (dump_file
, " (bounded by ");
3916 print_decu (i_bound
, dump_file
);
3917 fprintf (dump_file
, ") + 1 times in loop %d.\n", loop
->num
);
3920 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
3921 real number of iterations. */
3922 if (TREE_CODE (bound
) != INTEGER_CST
)
3925 gcc_checking_assert (i_bound
== wi::to_widest (bound
));
3927 if (wi::min_precision (i_bound
, SIGNED
) > bound_wide_int ().get_precision ())
3930 /* If we have a guaranteed upper bound, record it in the appropriate
3931 list, unless this is an !is_exit bound (i.e. undefined behavior in
3932 at_stmt) in a loop with known constant number of iterations. */
3935 || loop
->nb_iterations
== NULL_TREE
3936 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
))
3938 class nb_iter_bound
*elt
= ggc_alloc
<nb_iter_bound
> ();
3940 elt
->bound
= bound_wide_int::from (i_bound
, SIGNED
);
3941 elt
->stmt
= at_stmt
;
3942 elt
->is_exit
= is_exit
;
3943 elt
->next
= loop
->bounds
;
3947 /* If statement is executed on every path to the loop latch, we can directly
3948 infer the upper bound on the # of iterations of the loop. */
3949 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (at_stmt
)))
3952 /* Update the number of iteration estimates according to the bound.
3953 If at_stmt is an exit then the loop latch is executed at most BOUND times,
3954 otherwise it can be executed BOUND + 1 times. We will lower the estimate
3955 later if such statement must be executed on last iteration */
3960 widest_int new_i_bound
= i_bound
+ delta
;
3962 /* If an overflow occurred, ignore the result. */
3963 if (wi::ltu_p (new_i_bound
, delta
))
3966 if (upper
&& !is_exit
)
3967 do_warn_aggressive_loop_optimizations (loop
, new_i_bound
, at_stmt
);
3968 record_niter_bound (loop
, new_i_bound
, realistic
, upper
);
3971 /* Records the control iv analyzed in NITER for LOOP if the iv is valid
3972 and doesn't overflow. */
3975 record_control_iv (class loop
*loop
, class tree_niter_desc
*niter
)
3977 struct control_iv
*iv
;
3979 if (!niter
->control
.base
|| !niter
->control
.step
)
3982 if (!integer_onep (niter
->assumptions
) || !niter
->control
.no_overflow
)
3985 iv
= ggc_alloc
<control_iv
> ();
3986 iv
->base
= niter
->control
.base
;
3987 iv
->step
= niter
->control
.step
;
3988 iv
->next
= loop
->control_ivs
;
3989 loop
->control_ivs
= iv
;
3994 /* This function returns TRUE if below conditions are satisfied:
3995 1) VAR is SSA variable.
3996 2) VAR is an IV:{base, step} in its defining loop.
3997 3) IV doesn't overflow.
3998 4) Both base and step are integer constants.
3999 5) Base is the MIN/MAX value depends on IS_MIN.
4000 Store value of base to INIT correspondingly. */
4003 get_cst_init_from_scev (tree var
, wide_int
*init
, bool is_min
)
4005 if (TREE_CODE (var
) != SSA_NAME
)
4008 gimple
*def_stmt
= SSA_NAME_DEF_STMT (var
);
4009 class loop
*loop
= loop_containing_stmt (def_stmt
);
4015 if (!simple_iv (loop
, loop
, var
, &iv
, false))
4018 if (!iv
.no_overflow
)
4021 if (TREE_CODE (iv
.base
) != INTEGER_CST
|| TREE_CODE (iv
.step
) != INTEGER_CST
)
4024 if (is_min
== tree_int_cst_sign_bit (iv
.step
))
4027 *init
= wi::to_wide (iv
.base
);
4031 /* Record the estimate on number of iterations of LOOP based on the fact that
4032 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
4033 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
4034 estimated number of iterations is expected to be close to the real one.
4035 UPPER is true if we are sure the induction variable does not wrap. */
4038 record_nonwrapping_iv (class loop
*loop
, tree base
, tree step
, gimple
*stmt
,
4039 tree low
, tree high
, bool realistic
, bool upper
)
4041 tree niter_bound
, extreme
, delta
;
4042 tree type
= TREE_TYPE (base
), unsigned_type
;
4043 tree orig_base
= base
;
4045 if (TREE_CODE (step
) != INTEGER_CST
|| integer_zerop (step
))
4048 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4050 fprintf (dump_file
, "Induction variable (");
4051 print_generic_expr (dump_file
, TREE_TYPE (base
), TDF_SLIM
);
4052 fprintf (dump_file
, ") ");
4053 print_generic_expr (dump_file
, base
, TDF_SLIM
);
4054 fprintf (dump_file
, " + ");
4055 print_generic_expr (dump_file
, step
, TDF_SLIM
);
4056 fprintf (dump_file
, " * iteration does not wrap in statement ");
4057 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
4058 fprintf (dump_file
, " in loop %d.\n", loop
->num
);
4061 unsigned_type
= unsigned_type_for (type
);
4062 base
= fold_convert (unsigned_type
, base
);
4063 step
= fold_convert (unsigned_type
, step
);
4065 if (tree_int_cst_sign_bit (step
))
4068 Value_Range
base_range (TREE_TYPE (orig_base
));
4069 if (get_range_query (cfun
)->range_of_expr (base_range
, orig_base
)
4070 && !base_range
.undefined_p ())
4071 max
= base_range
.upper_bound ();
4072 extreme
= fold_convert (unsigned_type
, low
);
4073 if (TREE_CODE (orig_base
) == SSA_NAME
4074 && TREE_CODE (high
) == INTEGER_CST
4075 && INTEGRAL_TYPE_P (TREE_TYPE (orig_base
))
4076 && ((!base_range
.varying_p ()
4077 && !base_range
.undefined_p ())
4078 || get_cst_init_from_scev (orig_base
, &max
, false))
4079 && wi::gts_p (wi::to_wide (high
), max
))
4080 base
= wide_int_to_tree (unsigned_type
, max
);
4081 else if (TREE_CODE (base
) != INTEGER_CST
4082 && dominated_by_p (CDI_DOMINATORS
,
4083 loop
->latch
, gimple_bb (stmt
)))
4084 base
= fold_convert (unsigned_type
, high
);
4085 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
4086 step
= fold_build1 (NEGATE_EXPR
, unsigned_type
, step
);
4091 Value_Range
base_range (TREE_TYPE (orig_base
));
4092 if (get_range_query (cfun
)->range_of_expr (base_range
, orig_base
)
4093 && !base_range
.undefined_p ())
4094 min
= base_range
.lower_bound ();
4095 extreme
= fold_convert (unsigned_type
, high
);
4096 if (TREE_CODE (orig_base
) == SSA_NAME
4097 && TREE_CODE (low
) == INTEGER_CST
4098 && INTEGRAL_TYPE_P (TREE_TYPE (orig_base
))
4099 && ((!base_range
.varying_p ()
4100 && !base_range
.undefined_p ())
4101 || get_cst_init_from_scev (orig_base
, &min
, true))
4102 && wi::gts_p (min
, wi::to_wide (low
)))
4103 base
= wide_int_to_tree (unsigned_type
, min
);
4104 else if (TREE_CODE (base
) != INTEGER_CST
4105 && dominated_by_p (CDI_DOMINATORS
,
4106 loop
->latch
, gimple_bb (stmt
)))
4107 base
= fold_convert (unsigned_type
, low
);
4108 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
4111 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
4112 would get out of the range. */
4113 niter_bound
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step
);
4114 widest_int max
= derive_constant_upper_bound (niter_bound
);
4115 record_estimate (loop
, niter_bound
, max
, stmt
, false, realistic
, upper
);
4118 /* Determine information about number of iterations a LOOP from the index
4119 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
4120 guaranteed to be executed in every iteration of LOOP. Callback for
4130 idx_infer_loop_bounds (tree base
, tree
*idx
, void *dta
)
4132 struct ilb_data
*data
= (struct ilb_data
*) dta
;
4133 tree ev
, init
, step
;
4134 tree low
, high
, type
, next
;
4135 bool sign
, upper
= true, has_flexible_size
= false;
4136 class loop
*loop
= data
->loop
;
4138 if (TREE_CODE (base
) != ARRAY_REF
)
4141 /* For arrays that might have flexible sizes, it is not guaranteed that they
4142 do not really extend over their declared size. */
4143 if (array_ref_flexible_size_p (base
))
4145 has_flexible_size
= true;
4149 class loop
*dloop
= loop_containing_stmt (data
->stmt
);
4153 ev
= analyze_scalar_evolution (dloop
, *idx
);
4154 ev
= instantiate_parameters (loop
, ev
);
4155 init
= initial_condition (ev
);
4156 step
= evolution_part_in_loop_num (ev
, loop
->num
);
4160 || TREE_CODE (step
) != INTEGER_CST
4161 || integer_zerop (step
)
4162 || tree_contains_chrecs (init
, NULL
)
4163 || chrec_contains_symbols_defined_in_loop (init
, loop
->num
))
4166 low
= array_ref_low_bound (base
);
4167 high
= array_ref_up_bound (base
);
4169 /* The case of nonconstant bounds could be handled, but it would be
4171 if (TREE_CODE (low
) != INTEGER_CST
4173 || TREE_CODE (high
) != INTEGER_CST
)
4175 sign
= tree_int_cst_sign_bit (step
);
4176 type
= TREE_TYPE (step
);
4178 /* The array that might have flexible size most likely extends
4179 beyond its bounds. */
4180 if (has_flexible_size
4181 && operand_equal_p (low
, high
, 0))
4184 /* In case the relevant bound of the array does not fit in type, or
4185 it does, but bound + step (in type) still belongs into the range of the
4186 array, the index may wrap and still stay within the range of the array
4187 (consider e.g. if the array is indexed by the full range of
4190 To make things simpler, we require both bounds to fit into type, although
4191 there are cases where this would not be strictly necessary. */
4192 if (!int_fits_type_p (high
, type
)
4193 || !int_fits_type_p (low
, type
))
4195 low
= fold_convert (type
, low
);
4196 high
= fold_convert (type
, high
);
4199 next
= fold_binary (PLUS_EXPR
, type
, low
, step
);
4201 next
= fold_binary (PLUS_EXPR
, type
, high
, step
);
4203 if (tree_int_cst_compare (low
, next
) <= 0
4204 && tree_int_cst_compare (next
, high
) <= 0)
4207 /* If access is not executed on every iteration, we must ensure that overlow
4208 may not make the access valid later. */
4209 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (data
->stmt
)))
4211 if (scev_probably_wraps_p (NULL_TREE
,
4212 initial_condition_in_loop_num (ev
, loop
->num
),
4213 step
, data
->stmt
, loop
, true))
4217 record_nonwrapping_chrec (ev
);
4219 record_nonwrapping_iv (loop
, init
, step
, data
->stmt
, low
, high
, false, upper
);
4223 /* Determine information about number of iterations a LOOP from the bounds
4224 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
4225 STMT is guaranteed to be executed in every iteration of LOOP.*/
4228 infer_loop_bounds_from_ref (class loop
*loop
, gimple
*stmt
, tree ref
)
4230 struct ilb_data data
;
4234 for_each_index (&ref
, idx_infer_loop_bounds
, &data
);
4237 /* Determine information about number of iterations of a LOOP from the way
4238 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
4239 executed in every iteration of LOOP. */
4242 infer_loop_bounds_from_array (class loop
*loop
, gimple
*stmt
)
4244 if (is_gimple_assign (stmt
))
4246 tree op0
= gimple_assign_lhs (stmt
);
4247 tree op1
= gimple_assign_rhs1 (stmt
);
4249 /* For each memory access, analyze its access function
4250 and record a bound on the loop iteration domain. */
4251 if (REFERENCE_CLASS_P (op0
))
4252 infer_loop_bounds_from_ref (loop
, stmt
, op0
);
4254 if (REFERENCE_CLASS_P (op1
))
4255 infer_loop_bounds_from_ref (loop
, stmt
, op1
);
4257 else if (is_gimple_call (stmt
))
4260 unsigned i
, n
= gimple_call_num_args (stmt
);
4262 lhs
= gimple_call_lhs (stmt
);
4263 if (lhs
&& REFERENCE_CLASS_P (lhs
))
4264 infer_loop_bounds_from_ref (loop
, stmt
, lhs
);
4266 for (i
= 0; i
< n
; i
++)
4268 arg
= gimple_call_arg (stmt
, i
);
4269 if (REFERENCE_CLASS_P (arg
))
4270 infer_loop_bounds_from_ref (loop
, stmt
, arg
);
4275 /* Determine information about number of iterations of a LOOP from the fact
4276 that pointer arithmetics in STMT does not overflow. */
4279 infer_loop_bounds_from_pointer_arith (class loop
*loop
, gimple
*stmt
)
4281 tree def
, base
, step
, scev
, type
, low
, high
;
4284 if (!is_gimple_assign (stmt
)
4285 || gimple_assign_rhs_code (stmt
) != POINTER_PLUS_EXPR
)
4288 def
= gimple_assign_lhs (stmt
);
4289 if (TREE_CODE (def
) != SSA_NAME
)
4292 type
= TREE_TYPE (def
);
4293 if (!nowrap_type_p (type
))
4296 ptr
= gimple_assign_rhs1 (stmt
);
4297 if (!expr_invariant_in_loop_p (loop
, ptr
))
4300 var
= gimple_assign_rhs2 (stmt
);
4301 if (TYPE_PRECISION (type
) != TYPE_PRECISION (TREE_TYPE (var
)))
4304 class loop
*uloop
= loop_containing_stmt (stmt
);
4305 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (uloop
, def
));
4306 if (chrec_contains_undetermined (scev
))
4309 base
= initial_condition_in_loop_num (scev
, loop
->num
);
4310 step
= evolution_part_in_loop_num (scev
, loop
->num
);
4313 || TREE_CODE (step
) != INTEGER_CST
4314 || tree_contains_chrecs (base
, NULL
)
4315 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
4318 low
= lower_bound_in_type (type
, type
);
4319 high
= upper_bound_in_type (type
, type
);
4321 /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
4322 produce a NULL pointer. The contrary would mean NULL points to an object,
4323 while NULL is supposed to compare unequal with the address of all objects.
4324 Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
4325 NULL pointer since that would mean wrapping, which we assume here not to
4326 happen. So, we can exclude NULL from the valid range of pointer
4328 if (flag_delete_null_pointer_checks
&& int_cst_value (low
) == 0)
4329 low
= build_int_cstu (TREE_TYPE (low
), TYPE_ALIGN_UNIT (TREE_TYPE (type
)));
4331 record_nonwrapping_chrec (scev
);
4332 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
4335 /* Determine information about number of iterations of a LOOP from the fact
4336 that signed arithmetics in STMT does not overflow. */
4339 infer_loop_bounds_from_signedness (class loop
*loop
, gimple
*stmt
)
4341 tree def
, base
, step
, scev
, type
, low
, high
;
4343 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
4346 def
= gimple_assign_lhs (stmt
);
4348 if (TREE_CODE (def
) != SSA_NAME
)
4351 type
= TREE_TYPE (def
);
4352 if (!INTEGRAL_TYPE_P (type
)
4353 || !TYPE_OVERFLOW_UNDEFINED (type
))
4356 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
4357 if (chrec_contains_undetermined (scev
))
4360 base
= initial_condition_in_loop_num (scev
, loop
->num
);
4361 step
= evolution_part_in_loop_num (scev
, loop
->num
);
4364 || TREE_CODE (step
) != INTEGER_CST
4365 || tree_contains_chrecs (base
, NULL
)
4366 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
4369 low
= lower_bound_in_type (type
, type
);
4370 high
= upper_bound_in_type (type
, type
);
4371 Value_Range
r (TREE_TYPE (def
));
4372 get_range_query (cfun
)->range_of_expr (r
, def
);
4373 if (!r
.varying_p () && !r
.undefined_p ())
4375 low
= wide_int_to_tree (type
, r
.lower_bound ());
4376 high
= wide_int_to_tree (type
, r
.upper_bound ());
4379 record_nonwrapping_chrec (scev
);
4380 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
4383 /* The following analyzers are extracting informations on the bounds
4384 of LOOP from the following undefined behaviors:
4386 - data references should not access elements over the statically
4389 - signed variables should not overflow when flag_wrapv is not set.
4393 infer_loop_bounds_from_undefined (class loop
*loop
, basic_block
*bbs
)
4396 gimple_stmt_iterator bsi
;
4400 for (i
= 0; i
< loop
->num_nodes
; i
++)
4404 /* If BB is not executed in each iteration of the loop, we cannot
4405 use the operations in it to infer reliable upper bound on the
4406 # of iterations of the loop. However, we can use it as a guess.
4407 Reliable guesses come only from array bounds. */
4408 reliable
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
);
4410 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4412 gimple
*stmt
= gsi_stmt (bsi
);
4414 infer_loop_bounds_from_array (loop
, stmt
);
4418 infer_loop_bounds_from_signedness (loop
, stmt
);
4419 infer_loop_bounds_from_pointer_arith (loop
, stmt
);
4426 /* Compare wide ints, callback for qsort. */
4429 wide_int_cmp (const void *p1
, const void *p2
)
4431 const bound_wide_int
*d1
= (const bound_wide_int
*) p1
;
4432 const bound_wide_int
*d2
= (const bound_wide_int
*) p2
;
4433 return wi::cmpu (*d1
, *d2
);
4436 /* Return index of BOUND in BOUNDS array sorted in increasing order.
4437 Lookup by binary search. */
4440 bound_index (const vec
<bound_wide_int
> &bounds
, const bound_wide_int
&bound
)
4442 unsigned int end
= bounds
.length ();
4443 unsigned int begin
= 0;
4445 /* Find a matching index by means of a binary search. */
4446 while (begin
!= end
)
4448 unsigned int middle
= (begin
+ end
) / 2;
4449 bound_wide_int index
= bounds
[middle
];
4453 else if (wi::ltu_p (index
, bound
))
4461 /* We recorded loop bounds only for statements dominating loop latch (and thus
4462 executed each loop iteration). If there are any bounds on statements not
4463 dominating the loop latch we can improve the estimate by walking the loop
4464 body and seeing if every path from loop header to loop latch contains
4465 some bounded statement. */
4468 discover_iteration_bound_by_body_walk (class loop
*loop
)
4470 class nb_iter_bound
*elt
;
4471 auto_vec
<bound_wide_int
> bounds
;
4472 vec
<vec
<basic_block
> > queues
= vNULL
;
4473 vec
<basic_block
> queue
= vNULL
;
4474 ptrdiff_t queue_index
;
4475 ptrdiff_t latch_index
= 0;
4477 /* Discover what bounds may interest us. */
4478 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
4480 bound_wide_int bound
= elt
->bound
;
4482 /* Exit terminates loop at given iteration, while non-exits produce undefined
4483 effect on the next iteration. */
4487 /* If an overflow occurred, ignore the result. */
4492 if (!loop
->any_upper_bound
4493 || wi::ltu_p (bound
, loop
->nb_iterations_upper_bound
))
4494 bounds
.safe_push (bound
);
4497 /* Exit early if there is nothing to do. */
4498 if (!bounds
.exists ())
4501 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4502 fprintf (dump_file
, " Trying to walk loop body to reduce the bound.\n");
4504 /* Sort the bounds in decreasing order. */
4505 bounds
.qsort (wide_int_cmp
);
4507 /* For every basic block record the lowest bound that is guaranteed to
4508 terminate the loop. */
4510 hash_map
<basic_block
, ptrdiff_t> bb_bounds
;
4511 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
4513 bound_wide_int bound
= elt
->bound
;
4517 /* If an overflow occurred, ignore the result. */
4522 if (!loop
->any_upper_bound
4523 || wi::ltu_p (bound
, loop
->nb_iterations_upper_bound
))
4525 ptrdiff_t index
= bound_index (bounds
, bound
);
4526 ptrdiff_t *entry
= bb_bounds
.get (gimple_bb (elt
->stmt
));
4528 bb_bounds
.put (gimple_bb (elt
->stmt
), index
);
4529 else if ((ptrdiff_t)*entry
> index
)
4534 hash_map
<basic_block
, ptrdiff_t> block_priority
;
4536 /* Perform shortest path discovery loop->header ... loop->latch.
4538 The "distance" is given by the smallest loop bound of basic block
4539 present in the path and we look for path with largest smallest bound
4542 To avoid the need for fibonacci heap on double ints we simply compress
4543 double ints into indexes to BOUNDS array and then represent the queue
4544 as arrays of queues for every index.
4545 Index of BOUNDS.length() means that the execution of given BB has
4546 no bounds determined.
4548 VISITED is a pointer map translating basic block into smallest index
4549 it was inserted into the priority queue with. */
4552 /* Start walk in loop header with index set to infinite bound. */
4553 queue_index
= bounds
.length ();
4554 queues
.safe_grow_cleared (queue_index
+ 1, true);
4555 queue
.safe_push (loop
->header
);
4556 queues
[queue_index
] = queue
;
4557 block_priority
.put (loop
->header
, queue_index
);
4559 for (; queue_index
>= 0; queue_index
--)
4561 if (latch_index
< queue_index
)
4563 while (queues
[queue_index
].length ())
4566 ptrdiff_t bound_index
= queue_index
;
4570 queue
= queues
[queue_index
];
4573 /* OK, we later inserted the BB with lower priority, skip it. */
4574 if (*block_priority
.get (bb
) > queue_index
)
4577 /* See if we can improve the bound. */
4578 ptrdiff_t *entry
= bb_bounds
.get (bb
);
4579 if (entry
&& *entry
< bound_index
)
4580 bound_index
= *entry
;
4582 /* Insert succesors into the queue, watch for latch edge
4583 and record greatest index we saw. */
4584 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4586 bool insert
= false;
4588 if (loop_exit_edge_p (loop
, e
))
4591 if (e
== loop_latch_edge (loop
)
4592 && latch_index
< bound_index
)
4593 latch_index
= bound_index
;
4594 else if (!(entry
= block_priority
.get (e
->dest
)))
4597 block_priority
.put (e
->dest
, bound_index
);
4599 else if (*entry
< bound_index
)
4602 *entry
= bound_index
;
4606 queues
[bound_index
].safe_push (e
->dest
);
4610 queues
[queue_index
].release ();
4613 gcc_assert (latch_index
>= 0);
4614 if ((unsigned)latch_index
< bounds
.length ())
4616 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4618 fprintf (dump_file
, "Found better loop bound ");
4619 print_decu (bounds
[latch_index
], dump_file
);
4620 fprintf (dump_file
, "\n");
4622 record_niter_bound (loop
, widest_int::from (bounds
[latch_index
],
4623 SIGNED
), false, true);
4629 /* See if every path cross the loop goes through a statement that is known
4630 to not execute at the last iteration. In that case we can decrese iteration
4634 maybe_lower_iteration_bound (class loop
*loop
)
4636 hash_set
<gimple
*> *not_executed_last_iteration
= NULL
;
4637 class nb_iter_bound
*elt
;
4638 bool found_exit
= false;
4639 auto_vec
<basic_block
> queue
;
4642 /* Collect all statements with interesting (i.e. lower than
4643 nb_iterations_upper_bound) bound on them.
4645 TODO: Due to the way record_estimate choose estimates to store, the bounds
4646 will be always nb_iterations_upper_bound-1. We can change this to record
4647 also statements not dominating the loop latch and update the walk bellow
4648 to the shortest path algorithm. */
4649 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
4652 && wi::ltu_p (elt
->bound
, loop
->nb_iterations_upper_bound
))
4654 if (!not_executed_last_iteration
)
4655 not_executed_last_iteration
= new hash_set
<gimple
*>;
4656 not_executed_last_iteration
->add (elt
->stmt
);
4659 if (!not_executed_last_iteration
)
4662 /* Start DFS walk in the loop header and see if we can reach the
4663 loop latch or any of the exits (including statements with side
4664 effects that may terminate the loop otherwise) without visiting
4665 any of the statements known to have undefined effect on the last
4667 queue
.safe_push (loop
->header
);
4668 visited
= BITMAP_ALLOC (NULL
);
4669 bitmap_set_bit (visited
, loop
->header
->index
);
4674 basic_block bb
= queue
.pop ();
4675 gimple_stmt_iterator gsi
;
4676 bool stmt_found
= false;
4678 /* Loop for possible exits and statements bounding the execution. */
4679 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
4681 gimple
*stmt
= gsi_stmt (gsi
);
4682 if (not_executed_last_iteration
->contains (stmt
))
4687 if (gimple_has_side_effects (stmt
))
4696 /* If no bounding statement is found, continue the walk. */
4702 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4704 if (loop_exit_edge_p (loop
, e
)
4705 || e
== loop_latch_edge (loop
))
4710 if (bitmap_set_bit (visited
, e
->dest
->index
))
4711 queue
.safe_push (e
->dest
);
4715 while (queue
.length () && !found_exit
);
4717 /* If every path through the loop reach bounding statement before exit,
4718 then we know the last iteration of the loop will have undefined effect
4719 and we can decrease number of iterations. */
4723 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4724 fprintf (dump_file
, "Reducing loop iteration estimate by 1; "
4725 "undefined statement must be executed at the last iteration.\n");
4726 record_niter_bound (loop
, widest_int::from (loop
->nb_iterations_upper_bound
,
4731 BITMAP_FREE (visited
);
4732 delete not_executed_last_iteration
;
4735 /* Get expected upper bound for number of loop iterations for
4736 BUILT_IN_EXPECT_WITH_PROBABILITY for a condition COND. */
4739 get_upper_bound_based_on_builtin_expr_with_prob (gcond
*cond
)
4744 tree lhs
= gimple_cond_lhs (cond
);
4745 if (TREE_CODE (lhs
) != SSA_NAME
)
4748 gimple
*stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (cond
));
4749 gcall
*def
= dyn_cast
<gcall
*> (stmt
);
4753 tree decl
= gimple_call_fndecl (def
);
4755 || !fndecl_built_in_p (decl
, BUILT_IN_EXPECT_WITH_PROBABILITY
)
4756 || gimple_call_num_args (stmt
) != 3)
4759 tree c
= gimple_call_arg (def
, 1);
4760 tree condt
= TREE_TYPE (lhs
);
4761 tree res
= fold_build2 (gimple_cond_code (cond
),
4763 gimple_cond_rhs (cond
));
4764 if (TREE_CODE (res
) != INTEGER_CST
)
4768 tree prob
= gimple_call_arg (def
, 2);
4769 tree t
= TREE_TYPE (prob
);
4771 = build_real_from_int_cst (t
,
4773 if (integer_zerop (res
))
4774 prob
= fold_build2 (MINUS_EXPR
, t
, one
, prob
);
4775 tree r
= fold_build2 (RDIV_EXPR
, t
, one
, prob
);
4776 if (TREE_CODE (r
) != REAL_CST
)
4780 = real_to_integer (TREE_REAL_CST_PTR (r
));
4781 return build_int_cst (condt
, probi
);
4784 /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
4785 is true also use estimates derived from undefined behavior. */
4788 estimate_numbers_of_iterations (class loop
*loop
)
4792 class tree_niter_desc niter_desc
;
4797 /* Give up if we already have tried to compute an estimation. */
4798 if (loop
->estimate_state
!= EST_NOT_COMPUTED
)
4801 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4802 fprintf (dump_file
, "Estimating # of iterations of loop %d\n", loop
->num
);
4804 loop
->estimate_state
= EST_AVAILABLE
;
4809 /* If we have a measured profile, use it to estimate the number of
4810 iterations. Normally this is recorded by branch_prob right after
4811 reading the profile. In case we however found a new loop, record the
4814 Explicitly check for profile status so we do not report
4815 wrong prediction hitrates for guessed loop iterations heuristics.
4816 Do not recompute already recorded bounds - we ought to be better on
4817 updating iteration bounds than updating profile in general and thus
4818 recomputing iteration bounds later in the compilation process will just
4819 introduce random roundoff errors. */
4820 if (!loop
->any_estimate
4821 && expected_loop_iterations_by_profile (loop
, &nit
, &reliable
)
4824 bound
= nit
.to_nearest_int ();
4825 record_niter_bound (loop
, bound
, true, false);
4828 /* Ensure that loop->nb_iterations is computed if possible. If it turns out
4829 to be constant, we avoid undefined behavior implied bounds and instead
4830 diagnose those loops with -Waggressive-loop-optimizations. */
4831 number_of_latch_executions (loop
);
4833 basic_block
*body
= get_loop_body (loop
);
4834 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
, body
);
4835 likely_exit
= single_likely_exit (loop
, exits
);
4836 FOR_EACH_VEC_ELT (exits
, i
, ex
)
4838 if (ex
== likely_exit
)
4840 gimple
*stmt
= *gsi_last_bb (ex
->src
);
4843 gcond
*cond
= dyn_cast
<gcond
*> (stmt
);
4845 = get_upper_bound_based_on_builtin_expr_with_prob (cond
);
4846 if (niter_bound
!= NULL_TREE
)
4848 widest_int max
= derive_constant_upper_bound (niter_bound
);
4849 record_estimate (loop
, niter_bound
, max
, cond
,
4855 if (!number_of_iterations_exit (loop
, ex
, &niter_desc
,
4856 false, false, body
))
4859 niter
= niter_desc
.niter
;
4860 type
= TREE_TYPE (niter
);
4861 if (TREE_CODE (niter_desc
.may_be_zero
) != INTEGER_CST
)
4862 niter
= build3 (COND_EXPR
, type
, niter_desc
.may_be_zero
,
4863 build_int_cst (type
, 0),
4865 record_estimate (loop
, niter
, niter_desc
.max
,
4866 last_nondebug_stmt (ex
->src
),
4867 true, ex
== likely_exit
, true);
4868 record_control_iv (loop
, &niter_desc
);
4871 if (flag_aggressive_loop_optimizations
)
4872 infer_loop_bounds_from_undefined (loop
, body
);
4875 discover_iteration_bound_by_body_walk (loop
);
4877 maybe_lower_iteration_bound (loop
);
4879 /* If we know the exact number of iterations of this loop, try to
4880 not break code with undefined behavior by not recording smaller
4881 maximum number of iterations. */
4882 if (loop
->nb_iterations
4883 && TREE_CODE (loop
->nb_iterations
) == INTEGER_CST
4884 && (wi::min_precision (wi::to_widest (loop
->nb_iterations
), SIGNED
)
4885 <= bound_wide_int ().get_precision ()))
4887 loop
->any_upper_bound
= true;
4888 loop
->nb_iterations_upper_bound
4889 = bound_wide_int::from (wi::to_widest (loop
->nb_iterations
), SIGNED
);
4893 /* Sets NIT to the estimated number of executions of the latch of the
4894 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
4895 large as the number of iterations. If we have no reliable estimate,
4896 the function returns false, otherwise returns true. */
4899 estimated_loop_iterations (class loop
*loop
, widest_int
*nit
)
4901 /* When SCEV information is available, try to update loop iterations
4902 estimate. Otherwise just return whatever we recorded earlier. */
4903 if (scev_initialized_p ())
4904 estimate_numbers_of_iterations (loop
);
4906 return (get_estimated_loop_iterations (loop
, nit
));
4909 /* Similar to estimated_loop_iterations, but returns the estimate only
4910 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
4911 on the number of iterations of LOOP could not be derived, returns -1. */
4914 estimated_loop_iterations_int (class loop
*loop
)
4917 HOST_WIDE_INT hwi_nit
;
4919 if (!estimated_loop_iterations (loop
, &nit
))
4922 if (!wi::fits_shwi_p (nit
))
4924 hwi_nit
= nit
.to_shwi ();
4926 return hwi_nit
< 0 ? -1 : hwi_nit
;
4930 /* Sets NIT to an upper bound for the maximum number of executions of the
4931 latch of the LOOP. If we have no reliable estimate, the function returns
4932 false, otherwise returns true. */
4935 max_loop_iterations (class loop
*loop
, widest_int
*nit
)
4937 /* When SCEV information is available, try to update loop iterations
4938 estimate. Otherwise just return whatever we recorded earlier. */
4939 if (scev_initialized_p ())
4940 estimate_numbers_of_iterations (loop
);
4942 return get_max_loop_iterations (loop
, nit
);
4945 /* Similar to max_loop_iterations, but returns the estimate only
4946 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
4947 on the number of iterations of LOOP could not be derived, returns -1. */
4950 max_loop_iterations_int (class loop
*loop
)
4953 HOST_WIDE_INT hwi_nit
;
4955 if (!max_loop_iterations (loop
, &nit
))
4958 if (!wi::fits_shwi_p (nit
))
4960 hwi_nit
= nit
.to_shwi ();
4962 return hwi_nit
< 0 ? -1 : hwi_nit
;
4965 /* Sets NIT to an likely upper bound for the maximum number of executions of the
4966 latch of the LOOP. If we have no reliable estimate, the function returns
4967 false, otherwise returns true. */
4970 likely_max_loop_iterations (class loop
*loop
, widest_int
*nit
)
4972 /* When SCEV information is available, try to update loop iterations
4973 estimate. Otherwise just return whatever we recorded earlier. */
4974 if (scev_initialized_p ())
4975 estimate_numbers_of_iterations (loop
);
4977 return get_likely_max_loop_iterations (loop
, nit
);
4980 /* Similar to max_loop_iterations, but returns the estimate only
4981 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
4982 on the number of iterations of LOOP could not be derived, returns -1. */
4985 likely_max_loop_iterations_int (class loop
*loop
)
4988 HOST_WIDE_INT hwi_nit
;
4990 if (!likely_max_loop_iterations (loop
, &nit
))
4993 if (!wi::fits_shwi_p (nit
))
4995 hwi_nit
= nit
.to_shwi ();
4997 return hwi_nit
< 0 ? -1 : hwi_nit
;
5000 /* Returns an estimate for the number of executions of statements
5001 in the LOOP. For statements before the loop exit, this exceeds
5002 the number of execution of the latch by one. */
5005 estimated_stmt_executions_int (class loop
*loop
)
5007 HOST_WIDE_INT nit
= estimated_loop_iterations_int (loop
);
5013 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
5015 /* If the computation overflows, return -1. */
5016 return snit
< 0 ? -1 : snit
;
5019 /* Sets NIT to the maximum number of executions of the latch of the
5020 LOOP, plus one. If we have no reliable estimate, the function returns
5021 false, otherwise returns true. */
5024 max_stmt_executions (class loop
*loop
, widest_int
*nit
)
5026 widest_int nit_minus_one
;
5028 if (!max_loop_iterations (loop
, nit
))
5031 nit_minus_one
= *nit
;
5035 return wi::gtu_p (*nit
, nit_minus_one
);
5038 /* Sets NIT to the estimated maximum number of executions of the latch of the
5039 LOOP, plus one. If we have no likely estimate, the function returns
5040 false, otherwise returns true. */
5043 likely_max_stmt_executions (class loop
*loop
, widest_int
*nit
)
5045 widest_int nit_minus_one
;
5047 if (!likely_max_loop_iterations (loop
, nit
))
5050 nit_minus_one
= *nit
;
5054 return wi::gtu_p (*nit
, nit_minus_one
);
5057 /* Sets NIT to the estimated number of executions of the latch of the
5058 LOOP, plus one. If we have no reliable estimate, the function returns
5059 false, otherwise returns true. */
5062 estimated_stmt_executions (class loop
*loop
, widest_int
*nit
)
5064 widest_int nit_minus_one
;
5066 if (!estimated_loop_iterations (loop
, nit
))
5069 nit_minus_one
= *nit
;
5073 return wi::gtu_p (*nit
, nit_minus_one
);
5076 /* Records estimates on numbers of iterations of loops. */
5079 estimate_numbers_of_iterations (function
*fn
)
5081 /* We don't want to issue signed overflow warnings while getting
5082 loop iteration estimates. */
5083 fold_defer_overflow_warnings ();
5085 for (auto loop
: loops_list (fn
, 0))
5086 estimate_numbers_of_iterations (loop
);
5088 fold_undefer_and_ignore_overflow_warnings ();
5091 /* Returns true if statement S1 dominates statement S2. */
5094 stmt_dominates_stmt_p (gimple
*s1
, gimple
*s2
)
5096 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
5104 gimple_stmt_iterator bsi
;
5106 if (gimple_code (s2
) == GIMPLE_PHI
)
5109 if (gimple_code (s1
) == GIMPLE_PHI
)
5112 for (bsi
= gsi_start_bb (bb1
); gsi_stmt (bsi
) != s2
; gsi_next (&bsi
))
5113 if (gsi_stmt (bsi
) == s1
)
5119 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
5122 /* Returns true when we can prove that the number of executions of
5123 STMT in the loop is at most NITER, according to the bound on
5124 the number of executions of the statement NITER_BOUND->stmt recorded in
5125 NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT.
5127 ??? This code can become quite a CPU hog - we can have many bounds,
5128 and large basic block forcing stmt_dominates_stmt_p to be queried
5129 many times on a large basic blocks, so the whole thing is O(n^2)
5130 for scev_probably_wraps_p invocation (that can be done n times).
5132 It would make more sense (and give better answers) to remember BB
5133 bounds computed by discover_iteration_bound_by_body_walk. */
5136 n_of_executions_at_most (gimple
*stmt
,
5137 class nb_iter_bound
*niter_bound
,
5140 widest_int bound
= widest_int::from (niter_bound
->bound
, SIGNED
);
5141 tree nit_type
= TREE_TYPE (niter
), e
;
5144 gcc_assert (TYPE_UNSIGNED (nit_type
));
5146 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
5147 the number of iterations is small. */
5148 if (!wi::fits_to_tree_p (bound
, nit_type
))
5151 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
5152 times. This means that:
5154 -- if NITER_BOUND->is_exit is true, then everything after
5155 it at most NITER_BOUND->bound times.
5157 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
5158 is executed, then NITER_BOUND->stmt is executed as well in the same
5159 iteration then STMT is executed at most NITER_BOUND->bound + 1 times.
5161 If we can determine that NITER_BOUND->stmt is always executed
5162 after STMT, then STMT is executed at most NITER_BOUND->bound + 2 times.
5163 We conclude that if both statements belong to the same
5164 basic block and STMT is before NITER_BOUND->stmt and there are no
5165 statements with side effects in between. */
5167 if (niter_bound
->is_exit
)
5169 if (stmt
== niter_bound
->stmt
5170 || !stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
5176 if (!stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
5178 gimple_stmt_iterator bsi
;
5179 if (gimple_bb (stmt
) != gimple_bb (niter_bound
->stmt
)
5180 || gimple_code (stmt
) == GIMPLE_PHI
5181 || gimple_code (niter_bound
->stmt
) == GIMPLE_PHI
)
5184 /* By stmt_dominates_stmt_p we already know that STMT appears
5185 before NITER_BOUND->STMT. Still need to test that the loop
5186 cannot be terinated by a side effect in between. */
5187 for (bsi
= gsi_for_stmt (stmt
); gsi_stmt (bsi
) != niter_bound
->stmt
;
5189 if (gimple_has_side_effects (gsi_stmt (bsi
)))
5193 || !wi::fits_to_tree_p (bound
, nit_type
))
5199 e
= fold_binary (cmp
, boolean_type_node
,
5200 niter
, wide_int_to_tree (nit_type
, bound
));
5201 return e
&& integer_nonzerop (e
);
5204 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
5207 nowrap_type_p (tree type
)
5209 if (ANY_INTEGRAL_TYPE_P (type
)
5210 && TYPE_OVERFLOW_UNDEFINED (type
))
5213 if (POINTER_TYPE_P (type
))
5219 /* Return true if we can prove LOOP is exited before evolution of induction
5220 variable {BASE, STEP} overflows with respect to its type bound. */
5223 loop_exits_before_overflow (tree base
, tree step
,
5224 gimple
*at_stmt
, class loop
*loop
)
5227 struct control_iv
*civ
;
5228 class nb_iter_bound
*bound
;
5229 tree e
, delta
, step_abs
, unsigned_base
;
5230 tree type
= TREE_TYPE (step
);
5231 tree unsigned_type
, valid_niter
;
5233 /* Don't issue signed overflow warnings. */
5234 fold_defer_overflow_warnings ();
5236 /* Compute the number of iterations before we reach the bound of the
5237 type, and verify that the loop is exited before this occurs. */
5238 unsigned_type
= unsigned_type_for (type
);
5239 unsigned_base
= fold_convert (unsigned_type
, base
);
5241 if (tree_int_cst_sign_bit (step
))
5243 tree extreme
= fold_convert (unsigned_type
,
5244 lower_bound_in_type (type
, type
));
5245 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, unsigned_base
, extreme
);
5246 step_abs
= fold_build1 (NEGATE_EXPR
, unsigned_type
,
5247 fold_convert (unsigned_type
, step
));
5251 tree extreme
= fold_convert (unsigned_type
,
5252 upper_bound_in_type (type
, type
));
5253 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, unsigned_base
);
5254 step_abs
= fold_convert (unsigned_type
, step
);
5257 valid_niter
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step_abs
);
5259 estimate_numbers_of_iterations (loop
);
5261 if (max_loop_iterations (loop
, &niter
)
5262 && wi::fits_to_tree_p (niter
, TREE_TYPE (valid_niter
))
5263 && (e
= fold_binary (GT_EXPR
, boolean_type_node
, valid_niter
,
5264 wide_int_to_tree (TREE_TYPE (valid_niter
),
5266 && integer_nonzerop (e
))
5268 fold_undefer_and_ignore_overflow_warnings ();
5272 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
5274 if (n_of_executions_at_most (at_stmt
, bound
, valid_niter
))
5276 fold_undefer_and_ignore_overflow_warnings ();
5280 fold_undefer_and_ignore_overflow_warnings ();
5282 /* Try to prove loop is exited before {base, step} overflows with the
5283 help of analyzed loop control IV. This is done only for IVs with
5284 constant step because otherwise we don't have the information. */
5285 if (TREE_CODE (step
) == INTEGER_CST
)
5287 for (civ
= loop
->control_ivs
; civ
; civ
= civ
->next
)
5289 enum tree_code code
;
5290 tree civ_type
= TREE_TYPE (civ
->step
);
5292 /* Have to consider type difference because operand_equal_p ignores
5293 that for constants. */
5294 if (TYPE_UNSIGNED (type
) != TYPE_UNSIGNED (civ_type
)
5295 || element_precision (type
) != element_precision (civ_type
))
5298 /* Only consider control IV with same step. */
5299 if (!operand_equal_p (step
, civ
->step
, 0))
5302 /* Done proving if this is a no-overflow control IV. */
5303 if (operand_equal_p (base
, civ
->base
, 0))
5306 /* Control IV is recorded after expanding simple operations,
5307 Here we expand base and compare it too. */
5308 tree expanded_base
= expand_simple_operations (base
);
5309 if (operand_equal_p (expanded_base
, civ
->base
, 0))
5312 /* If this is a before stepping control IV, in other words, we have
5314 {civ_base, step} = {base + step, step}
5316 Because civ {base + step, step} doesn't overflow during loop
5317 iterations, {base, step} will not overflow if we can prove the
5318 operation "base + step" does not overflow. Specifically, we try
5319 to prove below conditions are satisfied:
5321 base <= UPPER_BOUND (type) - step ;;step > 0
5322 base >= LOWER_BOUND (type) - step ;;step < 0
5324 by proving the reverse conditions are false using loop's initial
5326 if (POINTER_TYPE_P (TREE_TYPE (base
)))
5327 code
= POINTER_PLUS_EXPR
;
5331 tree stepped
= fold_build2 (code
, TREE_TYPE (base
), base
, step
);
5332 tree expanded_stepped
= fold_build2 (code
, TREE_TYPE (base
),
5333 expanded_base
, step
);
5334 if (operand_equal_p (stepped
, civ
->base
, 0)
5335 || operand_equal_p (expanded_stepped
, civ
->base
, 0))
5339 if (tree_int_cst_sign_bit (step
))
5342 extreme
= lower_bound_in_type (type
, type
);
5347 extreme
= upper_bound_in_type (type
, type
);
5349 extreme
= fold_build2 (MINUS_EXPR
, type
, extreme
, step
);
5350 e
= fold_build2 (code
, boolean_type_node
, base
, extreme
);
5351 e
= simplify_using_initial_conditions (loop
, e
);
5352 if (integer_zerop (e
))
5361 /* VAR is scev variable whose evolution part is constant STEP, this function
5362 proves that VAR can't overflow by using value range info. If VAR's value
5363 range is [MIN, MAX], it can be proven by:
5364 MAX + step doesn't overflow ; if step > 0
5366 MIN + step doesn't underflow ; if step < 0.
5368 We can only do this if var is computed in every loop iteration, i.e, var's
5369 definition has to dominate loop latch. Consider below example:
5377 # RANGE [0, 4294967294] NONZERO 65535
5378 # i_21 = PHI <0(3), i_18(9)>
5385 # RANGE [0, 65533] NONZERO 65535
5386 _6 = i_21 + 4294967295;
5387 # RANGE [0, 65533] NONZERO 65535
5388 _7 = (long unsigned int) _6;
5389 # RANGE [0, 524264] NONZERO 524280
5391 # PT = nonlocal escaped
5396 # RANGE [1, 65535] NONZERO 65535
5410 VAR _6 doesn't overflow only with pre-condition (i_21 != 0), here we
5411 can't use _6 to prove no-overlfow for _7. In fact, var _7 takes value
5412 sequence (4294967295, 0, 1, ..., 65533) in loop life time, rather than
5413 (4294967295, 4294967296, ...). */
5416 scev_var_range_cant_overflow (tree var
, tree step
, class loop
*loop
)
5419 wide_int minv
, maxv
, diff
, step_wi
;
5421 if (TREE_CODE (step
) != INTEGER_CST
|| !INTEGRAL_TYPE_P (TREE_TYPE (var
)))
5424 /* Check if VAR evaluates in every loop iteration. It's not the case
5425 if VAR is default definition or does not dominate loop's latch. */
5426 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (var
));
5427 if (!def_bb
|| !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, def_bb
))
5430 Value_Range
r (TREE_TYPE (var
));
5431 get_range_query (cfun
)->range_of_expr (r
, var
);
5432 if (r
.varying_p () || r
.undefined_p ())
5435 /* VAR is a scev whose evolution part is STEP and value range info
5436 is [MIN, MAX], we can prove its no-overflowness by conditions:
5438 type_MAX - MAX >= step ; if step > 0
5439 MIN - type_MIN >= |step| ; if step < 0.
5441 Or VAR must take value outside of value range, which is not true. */
5442 step_wi
= wi::to_wide (step
);
5443 type
= TREE_TYPE (var
);
5444 if (tree_int_cst_sign_bit (step
))
5446 diff
= r
.lower_bound () - wi::to_wide (lower_bound_in_type (type
, type
));
5447 step_wi
= - step_wi
;
5450 diff
= wi::to_wide (upper_bound_in_type (type
, type
)) - r
.upper_bound ();
5452 return (wi::geu_p (diff
, step_wi
));
5455 /* Return false only when the induction variable BASE + STEP * I is
5456 known to not overflow: i.e. when the number of iterations is small
5457 enough with respect to the step and initial condition in order to
5458 keep the evolution confined in TYPEs bounds. Return true when the
5459 iv is known to overflow or when the property is not computable.
5461 USE_OVERFLOW_SEMANTICS is true if this function should assume that
5462 the rules for overflow of the given language apply (e.g., that signed
5463 arithmetics in C does not overflow).
5465 If VAR is a ssa variable, this function also returns false if VAR can
5466 be proven not overflow with value range info. */
5469 scev_probably_wraps_p (tree var
, tree base
, tree step
,
5470 gimple
*at_stmt
, class loop
*loop
,
5471 bool use_overflow_semantics
)
5473 /* FIXME: We really need something like
5474 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
5476 We used to test for the following situation that frequently appears
5477 during address arithmetics:
5479 D.1621_13 = (long unsigned intD.4) D.1620_12;
5480 D.1622_14 = D.1621_13 * 8;
5481 D.1623_15 = (doubleD.29 *) D.1622_14;
5483 And derived that the sequence corresponding to D_14
5484 can be proved to not wrap because it is used for computing a
5485 memory access; however, this is not really the case -- for example,
5486 if D_12 = (unsigned char) [254,+,1], then D_14 has values
5487 2032, 2040, 0, 8, ..., but the code is still legal. */
5489 if (chrec_contains_undetermined (base
)
5490 || chrec_contains_undetermined (step
))
5493 if (integer_zerop (step
))
5496 /* If we can use the fact that signed and pointer arithmetics does not
5497 wrap, we are done. */
5498 if (use_overflow_semantics
&& nowrap_type_p (TREE_TYPE (base
)))
5501 /* To be able to use estimates on number of iterations of the loop,
5502 we must have an upper bound on the absolute value of the step. */
5503 if (TREE_CODE (step
) != INTEGER_CST
)
5506 /* Check if var can be proven not overflow with value range info. */
5507 if (var
&& TREE_CODE (var
) == SSA_NAME
5508 && scev_var_range_cant_overflow (var
, step
, loop
))
5511 if (loop_exits_before_overflow (base
, step
, at_stmt
, loop
))
5514 /* Check the nonwrapping flag, which may be set by niter analysis (e.g., the
5515 above loop exits before overflow). */
5516 if (var
&& nonwrapping_chrec_p (analyze_scalar_evolution (loop
, var
)))
5519 /* At this point we still don't have a proof that the iv does not
5520 overflow: give up. */
5524 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
5527 free_numbers_of_iterations_estimates (class loop
*loop
)
5529 struct control_iv
*civ
;
5530 class nb_iter_bound
*bound
;
5532 loop
->nb_iterations
= NULL
;
5533 loop
->estimate_state
= EST_NOT_COMPUTED
;
5534 for (bound
= loop
->bounds
; bound
;)
5536 class nb_iter_bound
*next
= bound
->next
;
5540 loop
->bounds
= NULL
;
5542 for (civ
= loop
->control_ivs
; civ
;)
5544 struct control_iv
*next
= civ
->next
;
5548 loop
->control_ivs
= NULL
;
5551 /* Frees the information on upper bounds on numbers of iterations of loops. */
5554 free_numbers_of_iterations_estimates (function
*fn
)
5556 for (auto loop
: loops_list (fn
, 0))
5557 free_numbers_of_iterations_estimates (loop
);
5560 /* Substitute value VAL for ssa name NAME inside expressions held
5564 substitute_in_loop_info (class loop
*loop
, tree name
, tree val
)
5566 loop
->nb_iterations
= simplify_replace_tree (loop
->nb_iterations
, name
, val
);