1 /* Functions to determine/estimate number of iterations of a loop.
2 Copyright (C) 2004-2023 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"
49 /* The maximum number of dominator BBs we search for conditions
50 of loop header copies we use for simplifying a conditional
52 #define MAX_DOMINATORS_TO_WALK 8
56 Analysis of number of iterations of an affine exit test.
60 /* Bounds on some value, BELOW <= X <= UP. */
67 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */
70 split_to_var_and_offset (tree expr
, tree
*var
, mpz_t offset
)
72 tree type
= TREE_TYPE (expr
);
77 mpz_set_ui (offset
, 0);
79 switch (TREE_CODE (expr
))
86 case POINTER_PLUS_EXPR
:
87 op0
= TREE_OPERAND (expr
, 0);
88 op1
= TREE_OPERAND (expr
, 1);
90 if (TREE_CODE (op1
) != INTEGER_CST
)
94 /* Always sign extend the offset. */
95 wi::to_mpz (wi::to_wide (op1
), offset
, SIGNED
);
97 mpz_neg (offset
, offset
);
101 *var
= build_int_cst_type (type
, 0);
102 wi::to_mpz (wi::to_wide (expr
), offset
, TYPE_SIGN (type
));
110 /* From condition C0 CMP C1 derives information regarding the value range
111 of VAR, which is of TYPE. Results are stored in to BELOW and UP. */
114 refine_value_range_using_guard (tree type
, tree var
,
115 tree c0
, enum tree_code cmp
, tree c1
,
116 mpz_t below
, mpz_t up
)
118 tree varc0
, varc1
, ctype
;
120 mpz_t mint
, maxt
, minc1
, maxc1
;
121 bool no_wrap
= nowrap_type_p (type
);
123 signop sgn
= TYPE_SIGN (type
);
131 STRIP_SIGN_NOPS (c0
);
132 STRIP_SIGN_NOPS (c1
);
133 ctype
= TREE_TYPE (c0
);
134 if (!useless_type_conversion_p (ctype
, type
))
140 /* We could derive quite precise information from EQ_EXPR, however,
141 such a guard is unlikely to appear, so we do not bother with
146 /* NE_EXPR comparisons do not contain much of useful information,
147 except for cases of comparing with bounds. */
148 if (TREE_CODE (c1
) != INTEGER_CST
149 || !INTEGRAL_TYPE_P (type
))
152 /* Ensure that the condition speaks about an expression in the same
154 ctype
= TREE_TYPE (c0
);
155 if (TYPE_PRECISION (ctype
) != TYPE_PRECISION (type
))
157 c0
= fold_convert (type
, c0
);
158 c1
= fold_convert (type
, c1
);
160 if (operand_equal_p (var
, c0
, 0))
164 /* Case of comparing VAR with its below/up bounds. */
166 wi::to_mpz (wi::to_wide (c1
), valc1
, TYPE_SIGN (type
));
167 if (mpz_cmp (valc1
, below
) == 0)
169 if (mpz_cmp (valc1
, up
) == 0)
176 /* Case of comparing with the bounds of the type. */
177 wide_int min
= wi::min_value (type
);
178 wide_int max
= wi::max_value (type
);
180 if (wi::to_wide (c1
) == min
)
182 if (wi::to_wide (c1
) == max
)
186 /* Quick return if no useful information. */
198 split_to_var_and_offset (expand_simple_operations (c0
), &varc0
, offc0
);
199 split_to_var_and_offset (expand_simple_operations (c1
), &varc1
, offc1
);
201 /* We are only interested in comparisons of expressions based on VAR. */
202 if (operand_equal_p (var
, varc1
, 0))
204 std::swap (varc0
, varc1
);
205 mpz_swap (offc0
, offc1
);
206 cmp
= swap_tree_comparison (cmp
);
208 else if (!operand_equal_p (var
, varc0
, 0))
217 get_type_static_bounds (type
, mint
, maxt
);
220 Value_Range
r (TREE_TYPE (varc1
));
221 /* Setup range information for varc1. */
222 if (integer_zerop (varc1
))
224 wi::to_mpz (0, minc1
, TYPE_SIGN (type
));
225 wi::to_mpz (0, maxc1
, TYPE_SIGN (type
));
227 else if (TREE_CODE (varc1
) == SSA_NAME
228 && INTEGRAL_TYPE_P (type
)
229 && get_range_query (cfun
)->range_of_expr (r
, varc1
)
230 && r
.kind () == VR_RANGE
)
232 gcc_assert (wi::le_p (r
.lower_bound (), r
.upper_bound (), sgn
));
233 wi::to_mpz (r
.lower_bound (), minc1
, sgn
);
234 wi::to_mpz (r
.upper_bound (), maxc1
, sgn
);
238 mpz_set (minc1
, mint
);
239 mpz_set (maxc1
, maxt
);
242 /* Compute valid range information for varc1 + offc1. Note nothing
243 useful can be derived if it overflows or underflows. Overflow or
244 underflow could happen when:
246 offc1 > 0 && varc1 + offc1 > MAX_VAL (type)
247 offc1 < 0 && varc1 + offc1 < MIN_VAL (type). */
248 mpz_add (minc1
, minc1
, offc1
);
249 mpz_add (maxc1
, maxc1
, offc1
);
251 || mpz_sgn (offc1
) == 0
252 || (mpz_sgn (offc1
) < 0 && mpz_cmp (minc1
, mint
) >= 0)
253 || (mpz_sgn (offc1
) > 0 && mpz_cmp (maxc1
, maxt
) <= 0));
257 if (mpz_cmp (minc1
, mint
) < 0)
258 mpz_set (minc1
, mint
);
259 if (mpz_cmp (maxc1
, maxt
) > 0)
260 mpz_set (maxc1
, maxt
);
265 mpz_sub_ui (maxc1
, maxc1
, 1);
270 mpz_add_ui (minc1
, minc1
, 1);
273 /* Compute range information for varc0. If there is no overflow,
274 the condition implied that
276 (varc0) cmp (varc1 + offc1 - offc0)
278 We can possibly improve the upper bound of varc0 if cmp is LE_EXPR,
279 or the below bound if cmp is GE_EXPR.
281 To prove there is no overflow/underflow, we need to check below
283 1) cmp == LE_EXPR && offc0 > 0
285 (varc0 + offc0) doesn't overflow
286 && (varc1 + offc1 - offc0) doesn't underflow
288 2) cmp == LE_EXPR && offc0 < 0
290 (varc0 + offc0) doesn't underflow
291 && (varc1 + offc1 - offc0) doesn't overfloe
293 In this case, (varc0 + offc0) will never underflow if we can
294 prove (varc1 + offc1 - offc0) doesn't overflow.
296 3) cmp == GE_EXPR && offc0 < 0
298 (varc0 + offc0) doesn't underflow
299 && (varc1 + offc1 - offc0) doesn't overflow
301 4) cmp == GE_EXPR && offc0 > 0
303 (varc0 + offc0) doesn't overflow
304 && (varc1 + offc1 - offc0) doesn't underflow
306 In this case, (varc0 + offc0) will never overflow if we can
307 prove (varc1 + offc1 - offc0) doesn't underflow.
309 Note we only handle case 2 and 4 in below code. */
311 mpz_sub (minc1
, minc1
, offc0
);
312 mpz_sub (maxc1
, maxc1
, offc0
);
314 || mpz_sgn (offc0
) == 0
316 && mpz_sgn (offc0
) < 0 && mpz_cmp (maxc1
, maxt
) <= 0)
318 && mpz_sgn (offc0
) > 0 && mpz_cmp (minc1
, mint
) >= 0));
324 if (mpz_cmp (up
, maxc1
) > 0)
329 if (mpz_cmp (below
, minc1
) < 0)
330 mpz_set (below
, minc1
);
342 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
343 in TYPE to MIN and MAX. */
346 determine_value_range (class loop
*loop
, tree type
, tree var
, mpz_t off
,
347 mpz_t min
, mpz_t max
)
353 enum value_range_kind rtype
= VR_VARYING
;
355 /* If the expression is a constant, we know its value exactly. */
356 if (integer_zerop (var
))
363 get_type_static_bounds (type
, min
, max
);
365 /* See if we have some range info from VRP. */
366 if (TREE_CODE (var
) == SSA_NAME
&& INTEGRAL_TYPE_P (type
))
368 edge e
= loop_preheader_edge (loop
);
369 signop sgn
= TYPE_SIGN (type
);
372 /* Either for VAR itself... */
373 Value_Range
var_range (TREE_TYPE (var
));
374 get_range_query (cfun
)->range_of_expr (var_range
, var
);
375 rtype
= var_range
.kind ();
376 if (!var_range
.undefined_p ())
378 minv
= var_range
.lower_bound ();
379 maxv
= var_range
.upper_bound ();
382 /* Or for PHI results in loop->header where VAR is used as
383 PHI argument from the loop preheader edge. */
384 Value_Range
phi_range (TREE_TYPE (var
));
385 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
387 gphi
*phi
= gsi
.phi ();
388 if (PHI_ARG_DEF_FROM_EDGE (phi
, e
) == var
389 && get_range_query (cfun
)->range_of_expr (phi_range
,
390 gimple_phi_result (phi
))
391 && phi_range
.kind () == VR_RANGE
)
393 if (rtype
!= VR_RANGE
)
396 minv
= phi_range
.lower_bound ();
397 maxv
= phi_range
.upper_bound ();
401 minv
= wi::max (minv
, phi_range
.lower_bound (), sgn
);
402 maxv
= wi::min (maxv
, phi_range
.upper_bound (), sgn
);
403 /* If the PHI result range are inconsistent with
404 the VAR range, give up on looking at the PHI
405 results. This can happen if VR_UNDEFINED is
407 if (wi::gt_p (minv
, maxv
, sgn
))
409 Value_Range
vr (TREE_TYPE (var
));
410 get_range_query (cfun
)->range_of_expr (vr
, var
);
412 if (!vr
.undefined_p ())
414 minv
= vr
.lower_bound ();
415 maxv
= vr
.upper_bound ();
424 if (rtype
!= VR_RANGE
)
431 gcc_assert (wi::le_p (minv
, maxv
, sgn
));
432 wi::to_mpz (minv
, minm
, sgn
);
433 wi::to_mpz (maxv
, maxm
, sgn
);
435 /* Now walk the dominators of the loop header and use the entry
436 guards to refine the estimates. */
437 for (bb
= loop
->header
;
438 bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && cnt
< MAX_DOMINATORS_TO_WALK
;
439 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
446 if (!single_pred_p (bb
))
448 e
= single_pred_edge (bb
);
450 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
453 cond
= last_stmt (e
->src
);
454 c0
= gimple_cond_lhs (cond
);
455 cmp
= gimple_cond_code (cond
);
456 c1
= gimple_cond_rhs (cond
);
458 if (e
->flags
& EDGE_FALSE_VALUE
)
459 cmp
= invert_tree_comparison (cmp
, false);
461 refine_value_range_using_guard (type
, var
, c0
, cmp
, c1
, minm
, maxm
);
465 mpz_add (minm
, minm
, off
);
466 mpz_add (maxm
, maxm
, off
);
467 /* If the computation may not wrap or off is zero, then this
468 is always fine. If off is negative and minv + off isn't
469 smaller than type's minimum, or off is positive and
470 maxv + off isn't bigger than type's maximum, use the more
471 precise range too. */
472 if (nowrap_type_p (type
)
473 || mpz_sgn (off
) == 0
474 || (mpz_sgn (off
) < 0 && mpz_cmp (minm
, min
) >= 0)
475 || (mpz_sgn (off
) > 0 && mpz_cmp (maxm
, max
) <= 0))
487 /* If the computation may wrap, we know nothing about the value, except for
488 the range of the type. */
489 if (!nowrap_type_p (type
))
492 /* Since the addition of OFF does not wrap, if OFF is positive, then we may
493 add it to MIN, otherwise to MAX. */
494 if (mpz_sgn (off
) < 0)
495 mpz_add (max
, max
, off
);
497 mpz_add (min
, min
, off
);
500 /* Stores the bounds on the difference of the values of the expressions
501 (var + X) and (var + Y), computed in TYPE, to BNDS. */
504 bound_difference_of_offsetted_base (tree type
, mpz_t x
, mpz_t y
,
507 int rel
= mpz_cmp (x
, y
);
508 bool may_wrap
= !nowrap_type_p (type
);
511 /* If X == Y, then the expressions are always equal.
512 If X > Y, there are the following possibilities:
513 a) neither of var + X and var + Y overflow or underflow, or both of
514 them do. Then their difference is X - Y.
515 b) var + X overflows, and var + Y does not. Then the values of the
516 expressions are var + X - M and var + Y, where M is the range of
517 the type, and their difference is X - Y - M.
518 c) var + Y underflows and var + X does not. Their difference again
520 Therefore, if the arithmetics in type does not overflow, then the
521 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
522 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
523 (X - Y, X - Y + M). */
527 mpz_set_ui (bnds
->below
, 0);
528 mpz_set_ui (bnds
->up
, 0);
533 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), m
, UNSIGNED
);
534 mpz_add_ui (m
, m
, 1);
535 mpz_sub (bnds
->up
, x
, y
);
536 mpz_set (bnds
->below
, bnds
->up
);
541 mpz_sub (bnds
->below
, bnds
->below
, m
);
543 mpz_add (bnds
->up
, bnds
->up
, m
);
549 /* From condition C0 CMP C1 derives information regarding the
550 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
551 and stores it to BNDS. */
554 refine_bounds_using_guard (tree type
, tree varx
, mpz_t offx
,
555 tree vary
, mpz_t offy
,
556 tree c0
, enum tree_code cmp
, tree c1
,
559 tree varc0
, varc1
, ctype
;
560 mpz_t offc0
, offc1
, loffx
, loffy
, bnd
;
562 bool no_wrap
= nowrap_type_p (type
);
571 STRIP_SIGN_NOPS (c0
);
572 STRIP_SIGN_NOPS (c1
);
573 ctype
= TREE_TYPE (c0
);
574 if (!useless_type_conversion_p (ctype
, type
))
580 /* We could derive quite precise information from EQ_EXPR, however, such
581 a guard is unlikely to appear, so we do not bother with handling
586 /* NE_EXPR comparisons do not contain much of useful information, except for
587 special case of comparing with the bounds of the type. */
588 if (TREE_CODE (c1
) != INTEGER_CST
589 || !INTEGRAL_TYPE_P (type
))
592 /* Ensure that the condition speaks about an expression in the same type
594 ctype
= TREE_TYPE (c0
);
595 if (TYPE_PRECISION (ctype
) != TYPE_PRECISION (type
))
597 c0
= fold_convert (type
, c0
);
598 c1
= fold_convert (type
, c1
);
600 if (TYPE_MIN_VALUE (type
)
601 && operand_equal_p (c1
, TYPE_MIN_VALUE (type
), 0))
606 if (TYPE_MAX_VALUE (type
)
607 && operand_equal_p (c1
, TYPE_MAX_VALUE (type
), 0))
620 split_to_var_and_offset (expand_simple_operations (c0
), &varc0
, offc0
);
621 split_to_var_and_offset (expand_simple_operations (c1
), &varc1
, offc1
);
623 /* We are only interested in comparisons of expressions based on VARX and
624 VARY. TODO -- we might also be able to derive some bounds from
625 expressions containing just one of the variables. */
627 if (operand_equal_p (varx
, varc1
, 0))
629 std::swap (varc0
, varc1
);
630 mpz_swap (offc0
, offc1
);
631 cmp
= swap_tree_comparison (cmp
);
634 if (!operand_equal_p (varx
, varc0
, 0)
635 || !operand_equal_p (vary
, varc1
, 0))
638 mpz_init_set (loffx
, offx
);
639 mpz_init_set (loffy
, offy
);
641 if (cmp
== GT_EXPR
|| cmp
== GE_EXPR
)
643 std::swap (varx
, vary
);
644 mpz_swap (offc0
, offc1
);
645 mpz_swap (loffx
, loffy
);
646 cmp
= swap_tree_comparison (cmp
);
650 /* If there is no overflow, the condition implies that
652 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
654 The overflows and underflows may complicate things a bit; each
655 overflow decreases the appropriate offset by M, and underflow
656 increases it by M. The above inequality would not necessarily be
659 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
660 VARX + OFFC0 overflows, but VARX + OFFX does not.
661 This may only happen if OFFX < OFFC0.
662 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
663 VARY + OFFC1 underflows and VARY + OFFY does not.
664 This may only happen if OFFY > OFFC1. */
673 x_ok
= (integer_zerop (varx
)
674 || mpz_cmp (loffx
, offc0
) >= 0);
675 y_ok
= (integer_zerop (vary
)
676 || mpz_cmp (loffy
, offc1
) <= 0);
682 mpz_sub (bnd
, loffx
, loffy
);
683 mpz_add (bnd
, bnd
, offc1
);
684 mpz_sub (bnd
, bnd
, offc0
);
687 mpz_sub_ui (bnd
, bnd
, 1);
692 if (mpz_cmp (bnds
->below
, bnd
) < 0)
693 mpz_set (bnds
->below
, bnd
);
697 if (mpz_cmp (bnd
, bnds
->up
) < 0)
698 mpz_set (bnds
->up
, bnd
);
710 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
711 The subtraction is considered to be performed in arbitrary precision,
714 We do not attempt to be too clever regarding the value ranges of X and
715 Y; most of the time, they are just integers or ssa names offsetted by
716 integer. However, we try to use the information contained in the
717 comparisons before the loop (usually created by loop header copying). */
720 bound_difference (class loop
*loop
, tree x
, tree y
, bounds
*bnds
)
722 tree type
= TREE_TYPE (x
);
725 mpz_t minx
, maxx
, miny
, maxy
;
733 /* Get rid of unnecessary casts, but preserve the value of
738 mpz_init (bnds
->below
);
742 split_to_var_and_offset (x
, &varx
, offx
);
743 split_to_var_and_offset (y
, &vary
, offy
);
745 if (!integer_zerop (varx
)
746 && operand_equal_p (varx
, vary
, 0))
748 /* Special case VARX == VARY -- we just need to compare the
749 offsets. The matters are a bit more complicated in the
750 case addition of offsets may wrap. */
751 bound_difference_of_offsetted_base (type
, offx
, offy
, bnds
);
755 /* Otherwise, use the value ranges to determine the initial
756 estimates on below and up. */
761 determine_value_range (loop
, type
, varx
, offx
, minx
, maxx
);
762 determine_value_range (loop
, type
, vary
, offy
, miny
, maxy
);
764 mpz_sub (bnds
->below
, minx
, maxy
);
765 mpz_sub (bnds
->up
, maxx
, miny
);
772 /* If both X and Y are constants, we cannot get any more precise. */
773 if (integer_zerop (varx
) && integer_zerop (vary
))
776 /* Now walk the dominators of the loop header and use the entry
777 guards to refine the estimates. */
778 for (bb
= loop
->header
;
779 bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && cnt
< MAX_DOMINATORS_TO_WALK
;
780 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
782 if (!single_pred_p (bb
))
784 e
= single_pred_edge (bb
);
786 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
789 cond
= last_stmt (e
->src
);
790 c0
= gimple_cond_lhs (cond
);
791 cmp
= gimple_cond_code (cond
);
792 c1
= gimple_cond_rhs (cond
);
794 if (e
->flags
& EDGE_FALSE_VALUE
)
795 cmp
= invert_tree_comparison (cmp
, false);
797 refine_bounds_using_guard (type
, varx
, offx
, vary
, offy
,
807 /* Update the bounds in BNDS that restrict the value of X to the bounds
808 that restrict the value of X + DELTA. X can be obtained as a
809 difference of two values in TYPE. */
812 bounds_add (bounds
*bnds
, const widest_int
&delta
, tree type
)
817 wi::to_mpz (delta
, mdelta
, SIGNED
);
820 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), max
, UNSIGNED
);
822 mpz_add (bnds
->up
, bnds
->up
, mdelta
);
823 mpz_add (bnds
->below
, bnds
->below
, mdelta
);
825 if (mpz_cmp (bnds
->up
, max
) > 0)
826 mpz_set (bnds
->up
, max
);
829 if (mpz_cmp (bnds
->below
, max
) < 0)
830 mpz_set (bnds
->below
, max
);
836 /* Update the bounds in BNDS that restrict the value of X to the bounds
837 that restrict the value of -X. */
840 bounds_negate (bounds
*bnds
)
844 mpz_init_set (tmp
, bnds
->up
);
845 mpz_neg (bnds
->up
, bnds
->below
);
846 mpz_neg (bnds
->below
, tmp
);
850 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
853 inverse (tree x
, tree mask
)
855 tree type
= TREE_TYPE (x
);
857 unsigned ctr
= tree_floor_log2 (mask
);
859 if (TYPE_PRECISION (type
) <= HOST_BITS_PER_WIDE_INT
)
861 unsigned HOST_WIDE_INT ix
;
862 unsigned HOST_WIDE_INT imask
;
863 unsigned HOST_WIDE_INT irslt
= 1;
865 gcc_assert (cst_and_fits_in_hwi (x
));
866 gcc_assert (cst_and_fits_in_hwi (mask
));
868 ix
= int_cst_value (x
);
869 imask
= int_cst_value (mask
);
878 rslt
= build_int_cst_type (type
, irslt
);
882 rslt
= build_int_cst (type
, 1);
885 rslt
= int_const_binop (MULT_EXPR
, rslt
, x
);
886 x
= int_const_binop (MULT_EXPR
, x
, x
);
888 rslt
= int_const_binop (BIT_AND_EXPR
, rslt
, mask
);
894 /* Derives the upper bound BND on the number of executions of loop with exit
895 condition S * i <> C. If NO_OVERFLOW is true, then the control variable of
896 the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed
897 that the loop ends through this exit, i.e., the induction variable ever
898 reaches the value of C.
900 The value C is equal to final - base, where final and base are the final and
901 initial value of the actual induction variable in the analysed loop. BNDS
902 bounds the value of this difference when computed in signed type with
903 unbounded range, while the computation of C is performed in an unsigned
904 type with the range matching the range of the type of the induction variable.
905 In particular, BNDS.up contains an upper bound on C in the following cases:
906 -- if the iv must reach its final value without overflow, i.e., if
907 NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
908 -- if final >= base, which we know to hold when BNDS.below >= 0. */
911 number_of_iterations_ne_max (mpz_t bnd
, bool no_overflow
, tree c
, tree s
,
912 bounds
*bnds
, bool exit_must_be_taken
)
916 tree type
= TREE_TYPE (c
);
917 bool bnds_u_valid
= ((no_overflow
&& exit_must_be_taken
)
918 || mpz_sgn (bnds
->below
) >= 0);
921 || (TREE_CODE (c
) == INTEGER_CST
922 && TREE_CODE (s
) == INTEGER_CST
923 && wi::mod_trunc (wi::to_wide (c
), wi::to_wide (s
),
924 TYPE_SIGN (type
)) == 0)
925 || (TYPE_OVERFLOW_UNDEFINED (type
)
926 && multiple_of_p (type
, c
, s
)))
928 /* If C is an exact multiple of S, then its value will be reached before
929 the induction variable overflows (unless the loop is exited in some
930 other way before). Note that the actual induction variable in the
931 loop (which ranges from base to final instead of from 0 to C) may
932 overflow, in which case BNDS.up will not be giving a correct upper
933 bound on C; thus, BNDS_U_VALID had to be computed in advance. */
935 exit_must_be_taken
= true;
938 /* If the induction variable can overflow, the number of iterations is at
939 most the period of the control variable (or infinite, but in that case
940 the whole # of iterations analysis will fail). */
943 max
= wi::mask
<widest_int
> (TYPE_PRECISION (type
)
944 - wi::ctz (wi::to_wide (s
)), false);
945 wi::to_mpz (max
, bnd
, UNSIGNED
);
949 /* Now we know that the induction variable does not overflow, so the loop
950 iterates at most (range of type / S) times. */
951 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), bnd
, UNSIGNED
);
953 /* If the induction variable is guaranteed to reach the value of C before
955 if (exit_must_be_taken
)
957 /* ... then we can strengthen this to C / S, and possibly we can use
958 the upper bound on C given by BNDS. */
959 if (TREE_CODE (c
) == INTEGER_CST
)
960 wi::to_mpz (wi::to_wide (c
), bnd
, UNSIGNED
);
961 else if (bnds_u_valid
)
962 mpz_set (bnd
, bnds
->up
);
966 wi::to_mpz (wi::to_wide (s
), d
, UNSIGNED
);
967 mpz_fdiv_q (bnd
, bnd
, d
);
971 /* Determines number of iterations of loop whose ending condition
972 is IV <> FINAL. TYPE is the type of the iv. The number of
973 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
974 we know that the exit must be taken eventually, i.e., that the IV
975 ever reaches the value FINAL (we derived this earlier, and possibly set
976 NITER->assumptions to make sure this is the case). BNDS contains the
977 bounds on the difference FINAL - IV->base. */
980 number_of_iterations_ne (class loop
*loop
, tree type
, affine_iv
*iv
,
981 tree final
, class tree_niter_desc
*niter
,
982 bool exit_must_be_taken
, bounds
*bnds
)
984 tree niter_type
= unsigned_type_for (type
);
985 tree s
, c
, d
, bits
, assumption
, tmp
, bound
;
988 niter
->control
= *iv
;
989 niter
->bound
= final
;
990 niter
->cmp
= NE_EXPR
;
992 /* Rearrange the terms so that we get inequality S * i <> C, with S
993 positive. Also cast everything to the unsigned type. If IV does
994 not overflow, BNDS bounds the value of C. Also, this is the
995 case if the computation |FINAL - IV->base| does not overflow, i.e.,
996 if BNDS->below in the result is nonnegative. */
997 if (tree_int_cst_sign_bit (iv
->step
))
999 s
= fold_convert (niter_type
,
1000 fold_build1 (NEGATE_EXPR
, type
, iv
->step
));
1001 c
= fold_build2 (MINUS_EXPR
, niter_type
,
1002 fold_convert (niter_type
, iv
->base
),
1003 fold_convert (niter_type
, final
));
1004 bounds_negate (bnds
);
1008 s
= fold_convert (niter_type
, iv
->step
);
1009 c
= fold_build2 (MINUS_EXPR
, niter_type
,
1010 fold_convert (niter_type
, final
),
1011 fold_convert (niter_type
, iv
->base
));
1015 number_of_iterations_ne_max (max
, iv
->no_overflow
, c
, s
, bnds
,
1016 exit_must_be_taken
);
1017 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, max
, false),
1018 TYPE_SIGN (niter_type
));
1021 /* Compute no-overflow information for the control iv. This can be
1022 proven when below two conditions are satisfied:
1024 1) IV evaluates toward FINAL at beginning, i.e:
1025 base <= FINAL ; step > 0
1026 base >= FINAL ; step < 0
1028 2) |FINAL - base| is an exact multiple of step.
1030 Unfortunately, it's hard to prove above conditions after pass loop-ch
1031 because loop with exit condition (IV != FINAL) usually will be guarded
1032 by initial-condition (IV.base - IV.step != FINAL). In this case, we
1033 can alternatively try to prove below conditions:
1035 1') IV evaluates toward FINAL at beginning, i.e:
1036 new_base = base - step < FINAL ; step > 0
1037 && base - step doesn't underflow
1038 new_base = base - step > FINAL ; step < 0
1039 && base - step doesn't overflow
1041 Please refer to PR34114 as an example of loop-ch's impact.
1043 Note, for NE_EXPR, base equals to FINAL is a special case, in
1044 which the loop exits immediately, and the iv does not overflow.
1046 Also note, we prove condition 2) by checking base and final seperately
1047 along with condition 1) or 1'). Since we ensure the difference
1048 computation of c does not wrap with cond below and the adjusted s
1049 will fit a signed type as well as an unsigned we can safely do
1050 this using the type of the IV if it is not pointer typed. */
1052 if (POINTER_TYPE_P (type
))
1054 if (!niter
->control
.no_overflow
1055 && (integer_onep (s
)
1056 || (multiple_of_p (mtype
, fold_convert (mtype
, iv
->base
),
1057 fold_convert (mtype
, s
), false)
1058 && multiple_of_p (mtype
, fold_convert (mtype
, final
),
1059 fold_convert (mtype
, s
), false))))
1061 tree t
, cond
, relaxed_cond
= boolean_false_node
;
1063 if (tree_int_cst_sign_bit (iv
->step
))
1065 cond
= fold_build2 (GE_EXPR
, boolean_type_node
, iv
->base
, final
);
1066 if (TREE_CODE (type
) == INTEGER_TYPE
)
1068 /* Only when base - step doesn't overflow. */
1069 t
= TYPE_MAX_VALUE (type
);
1070 t
= fold_build2 (PLUS_EXPR
, type
, t
, iv
->step
);
1071 t
= fold_build2 (GE_EXPR
, boolean_type_node
, t
, iv
->base
);
1072 if (integer_nonzerop (t
))
1074 t
= fold_build2 (MINUS_EXPR
, type
, iv
->base
, iv
->step
);
1075 relaxed_cond
= fold_build2 (GT_EXPR
, boolean_type_node
, t
,
1082 cond
= fold_build2 (LE_EXPR
, boolean_type_node
, iv
->base
, final
);
1083 if (TREE_CODE (type
) == INTEGER_TYPE
)
1085 /* Only when base - step doesn't underflow. */
1086 t
= TYPE_MIN_VALUE (type
);
1087 t
= fold_build2 (PLUS_EXPR
, type
, t
, iv
->step
);
1088 t
= fold_build2 (LE_EXPR
, boolean_type_node
, t
, iv
->base
);
1089 if (integer_nonzerop (t
))
1091 t
= fold_build2 (MINUS_EXPR
, type
, iv
->base
, iv
->step
);
1092 relaxed_cond
= fold_build2 (LT_EXPR
, boolean_type_node
, t
,
1098 t
= simplify_using_initial_conditions (loop
, cond
);
1099 if (!t
|| !integer_onep (t
))
1100 t
= simplify_using_initial_conditions (loop
, relaxed_cond
);
1102 if (t
&& integer_onep (t
))
1104 niter
->control
.no_overflow
= true;
1105 niter
->niter
= fold_build2 (EXACT_DIV_EXPR
, niter_type
, c
, s
);
1110 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
1111 is infinite. Otherwise, the number of iterations is
1112 (inverse(s/d) * (c/d)) mod (size of mode/d). */
1113 bits
= num_ending_zeros (s
);
1114 bound
= build_low_bits_mask (niter_type
,
1115 (TYPE_PRECISION (niter_type
)
1116 - tree_to_uhwi (bits
)));
1118 d
= fold_binary_to_constant (LSHIFT_EXPR
, niter_type
,
1119 build_int_cst (niter_type
, 1), bits
);
1120 s
= fold_binary_to_constant (RSHIFT_EXPR
, niter_type
, s
, bits
);
1122 if (!exit_must_be_taken
)
1124 /* If we cannot assume that the exit is taken eventually, record the
1125 assumptions for divisibility of c. */
1126 assumption
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, c
, d
);
1127 assumption
= fold_build2 (EQ_EXPR
, boolean_type_node
,
1128 assumption
, build_int_cst (niter_type
, 0));
1129 if (!integer_nonzerop (assumption
))
1130 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1131 niter
->assumptions
, assumption
);
1134 c
= fold_build2 (EXACT_DIV_EXPR
, niter_type
, c
, d
);
1135 if (integer_onep (s
))
1141 tmp
= fold_build2 (MULT_EXPR
, niter_type
, c
, inverse (s
, bound
));
1142 niter
->niter
= fold_build2 (BIT_AND_EXPR
, niter_type
, tmp
, bound
);
1147 /* Checks whether we can determine the final value of the control variable
1148 of the loop with ending condition IV0 < IV1 (computed in TYPE).
1149 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
1150 of the step. The assumptions necessary to ensure that the computation
1151 of the final value does not overflow are recorded in NITER. If we
1152 find the final value, we adjust DELTA and return TRUE. Otherwise
1153 we return false. BNDS bounds the value of IV1->base - IV0->base,
1154 and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
1155 true if we know that the exit must be taken eventually. */
1158 number_of_iterations_lt_to_ne (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1159 class tree_niter_desc
*niter
,
1160 tree
*delta
, tree step
,
1161 bool exit_must_be_taken
, bounds
*bnds
)
1163 tree niter_type
= TREE_TYPE (step
);
1164 tree mod
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, *delta
, step
);
1167 tree assumption
= boolean_true_node
, bound
, noloop
;
1168 bool ret
= false, fv_comp_no_overflow
;
1170 if (POINTER_TYPE_P (type
))
1173 if (TREE_CODE (mod
) != INTEGER_CST
)
1175 if (integer_nonzerop (mod
))
1176 mod
= fold_build2 (MINUS_EXPR
, niter_type
, step
, mod
);
1177 tmod
= fold_convert (type1
, mod
);
1180 wi::to_mpz (wi::to_wide (mod
), mmod
, UNSIGNED
);
1181 mpz_neg (mmod
, mmod
);
1183 /* If the induction variable does not overflow and the exit is taken,
1184 then the computation of the final value does not overflow. This is
1185 also obviously the case if the new final value is equal to the
1186 current one. Finally, we postulate this for pointer type variables,
1187 as the code cannot rely on the object to that the pointer points being
1188 placed at the end of the address space (and more pragmatically,
1189 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
1190 if (integer_zerop (mod
) || POINTER_TYPE_P (type
))
1191 fv_comp_no_overflow
= true;
1192 else if (!exit_must_be_taken
)
1193 fv_comp_no_overflow
= false;
1195 fv_comp_no_overflow
=
1196 (iv0
->no_overflow
&& integer_nonzerop (iv0
->step
))
1197 || (iv1
->no_overflow
&& integer_nonzerop (iv1
->step
));
1199 if (integer_nonzerop (iv0
->step
))
1201 /* The final value of the iv is iv1->base + MOD, assuming that this
1202 computation does not overflow, and that
1203 iv0->base <= iv1->base + MOD. */
1204 if (!fv_comp_no_overflow
)
1206 bound
= fold_build2 (MINUS_EXPR
, type1
,
1207 TYPE_MAX_VALUE (type1
), tmod
);
1208 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
1210 if (integer_zerop (assumption
))
1213 if (mpz_cmp (mmod
, bnds
->below
) < 0)
1214 noloop
= boolean_false_node
;
1215 else if (POINTER_TYPE_P (type
))
1216 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
1218 fold_build_pointer_plus (iv1
->base
, tmod
));
1220 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
1222 fold_build2 (PLUS_EXPR
, type1
,
1227 /* The final value of the iv is iv0->base - MOD, assuming that this
1228 computation does not overflow, and that
1229 iv0->base - MOD <= iv1->base. */
1230 if (!fv_comp_no_overflow
)
1232 bound
= fold_build2 (PLUS_EXPR
, type1
,
1233 TYPE_MIN_VALUE (type1
), tmod
);
1234 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
1236 if (integer_zerop (assumption
))
1239 if (mpz_cmp (mmod
, bnds
->below
) < 0)
1240 noloop
= boolean_false_node
;
1241 else if (POINTER_TYPE_P (type
))
1242 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
1243 fold_build_pointer_plus (iv0
->base
,
1244 fold_build1 (NEGATE_EXPR
,
1248 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
1249 fold_build2 (MINUS_EXPR
, type1
,
1254 if (!integer_nonzerop (assumption
))
1255 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1258 if (!integer_zerop (noloop
))
1259 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1262 bounds_add (bnds
, wi::to_widest (mod
), type
);
1263 *delta
= fold_build2 (PLUS_EXPR
, niter_type
, *delta
, mod
);
1271 /* Add assertions to NITER that ensure that the control variable of the loop
1272 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
1273 are TYPE. Returns false if we can prove that there is an overflow, true
1274 otherwise. STEP is the absolute value of the step. */
1277 assert_no_overflow_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1278 class tree_niter_desc
*niter
, tree step
)
1280 tree bound
, d
, assumption
, diff
;
1281 tree niter_type
= TREE_TYPE (step
);
1283 if (integer_nonzerop (iv0
->step
))
1285 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
1286 if (iv0
->no_overflow
)
1289 /* If iv0->base is a constant, we can determine the last value before
1290 overflow precisely; otherwise we conservatively assume
1293 if (TREE_CODE (iv0
->base
) == INTEGER_CST
)
1295 d
= fold_build2 (MINUS_EXPR
, niter_type
,
1296 fold_convert (niter_type
, TYPE_MAX_VALUE (type
)),
1297 fold_convert (niter_type
, iv0
->base
));
1298 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
1301 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
1302 build_int_cst (niter_type
, 1));
1303 bound
= fold_build2 (MINUS_EXPR
, type
,
1304 TYPE_MAX_VALUE (type
), fold_convert (type
, diff
));
1305 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
1310 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
1311 if (iv1
->no_overflow
)
1314 if (TREE_CODE (iv1
->base
) == INTEGER_CST
)
1316 d
= fold_build2 (MINUS_EXPR
, niter_type
,
1317 fold_convert (niter_type
, iv1
->base
),
1318 fold_convert (niter_type
, TYPE_MIN_VALUE (type
)));
1319 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
1322 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
1323 build_int_cst (niter_type
, 1));
1324 bound
= fold_build2 (PLUS_EXPR
, type
,
1325 TYPE_MIN_VALUE (type
), fold_convert (type
, diff
));
1326 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
1330 if (integer_zerop (assumption
))
1332 if (!integer_nonzerop (assumption
))
1333 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1334 niter
->assumptions
, assumption
);
1336 iv0
->no_overflow
= true;
1337 iv1
->no_overflow
= true;
1341 /* Add an assumption to NITER that a loop whose ending condition
1342 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
1343 bounds the value of IV1->base - IV0->base. */
1346 assert_loop_rolls_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1347 class tree_niter_desc
*niter
, bounds
*bnds
)
1349 tree assumption
= boolean_true_node
, bound
, diff
;
1350 tree mbz
, mbzl
, mbzr
, type1
;
1351 bool rolls_p
, no_overflow_p
;
1355 /* We are going to compute the number of iterations as
1356 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
1357 variant of TYPE. This formula only works if
1359 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
1361 (where MAX is the maximum value of the unsigned variant of TYPE, and
1362 the computations in this formula are performed in full precision,
1363 i.e., without overflows).
1365 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
1366 we have a condition of the form iv0->base - step < iv1->base before the loop,
1367 and for loops iv0->base < iv1->base - step * i the condition
1368 iv0->base < iv1->base + step, due to loop header copying, which enable us
1369 to prove the lower bound.
1371 The upper bound is more complicated. Unless the expressions for initial
1372 and final value themselves contain enough information, we usually cannot
1373 derive it from the context. */
1375 /* First check whether the answer does not follow from the bounds we gathered
1377 if (integer_nonzerop (iv0
->step
))
1378 dstep
= wi::to_widest (iv0
->step
);
1381 dstep
= wi::sext (wi::to_widest (iv1
->step
), TYPE_PRECISION (type
));
1386 wi::to_mpz (dstep
, mstep
, UNSIGNED
);
1387 mpz_neg (mstep
, mstep
);
1388 mpz_add_ui (mstep
, mstep
, 1);
1390 rolls_p
= mpz_cmp (mstep
, bnds
->below
) <= 0;
1393 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), max
, UNSIGNED
);
1394 mpz_add (max
, max
, mstep
);
1395 no_overflow_p
= (mpz_cmp (bnds
->up
, max
) <= 0
1396 /* For pointers, only values lying inside a single object
1397 can be compared or manipulated by pointer arithmetics.
1398 Gcc in general does not allow or handle objects larger
1399 than half of the address space, hence the upper bound
1400 is satisfied for pointers. */
1401 || POINTER_TYPE_P (type
));
1405 if (rolls_p
&& no_overflow_p
)
1409 if (POINTER_TYPE_P (type
))
1412 /* Now the hard part; we must formulate the assumption(s) as expressions, and
1413 we must be careful not to introduce overflow. */
1415 if (integer_nonzerop (iv0
->step
))
1417 diff
= fold_build2 (MINUS_EXPR
, type1
,
1418 iv0
->step
, build_int_cst (type1
, 1));
1420 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
1421 0 address never belongs to any object, we can assume this for
1423 if (!POINTER_TYPE_P (type
))
1425 bound
= fold_build2 (PLUS_EXPR
, type1
,
1426 TYPE_MIN_VALUE (type
), diff
);
1427 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
1431 /* And then we can compute iv0->base - diff, and compare it with
1433 mbzl
= fold_build2 (MINUS_EXPR
, type1
,
1434 fold_convert (type1
, iv0
->base
), diff
);
1435 mbzr
= fold_convert (type1
, iv1
->base
);
1439 diff
= fold_build2 (PLUS_EXPR
, type1
,
1440 iv1
->step
, build_int_cst (type1
, 1));
1442 if (!POINTER_TYPE_P (type
))
1444 bound
= fold_build2 (PLUS_EXPR
, type1
,
1445 TYPE_MAX_VALUE (type
), diff
);
1446 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
1450 mbzl
= fold_convert (type1
, iv0
->base
);
1451 mbzr
= fold_build2 (MINUS_EXPR
, type1
,
1452 fold_convert (type1
, iv1
->base
), diff
);
1455 if (!integer_nonzerop (assumption
))
1456 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1457 niter
->assumptions
, assumption
);
1460 mbz
= fold_build2 (GT_EXPR
, boolean_type_node
, mbzl
, mbzr
);
1461 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1462 niter
->may_be_zero
, mbz
);
1466 /* Determines number of iterations of loop whose ending condition
1467 is IV0 < IV1 which likes: {base, -C} < n, or n < {base, C}.
1468 The number of iterations is stored to NITER. */
1471 number_of_iterations_until_wrap (class loop
*loop
, tree type
, affine_iv
*iv0
,
1472 affine_iv
*iv1
, class tree_niter_desc
*niter
)
1474 tree niter_type
= unsigned_type_for (type
);
1475 tree step
, num
, assumptions
, may_be_zero
, span
;
1476 wide_int high
, low
, max
, min
;
1478 may_be_zero
= fold_build2 (LE_EXPR
, boolean_type_node
, iv1
->base
, iv0
->base
);
1479 if (integer_onep (may_be_zero
))
1482 int prec
= TYPE_PRECISION (type
);
1483 signop sgn
= TYPE_SIGN (type
);
1484 min
= wi::min_value (prec
, sgn
);
1485 max
= wi::max_value (prec
, sgn
);
1487 /* n < {base, C}. */
1488 if (integer_zerop (iv0
->step
) && !tree_int_cst_sign_bit (iv1
->step
))
1491 /* MIN + C - 1 <= n. */
1492 tree last
= wide_int_to_tree (type
, min
+ wi::to_wide (step
) - 1);
1493 assumptions
= fold_build2 (LE_EXPR
, boolean_type_node
, last
, iv0
->base
);
1494 if (integer_zerop (assumptions
))
1497 num
= fold_build2 (MINUS_EXPR
, niter_type
, wide_int_to_tree (type
, max
),
1500 /* When base has the form iv + 1, if we know iv >= n, then iv + 1 < n
1501 only when iv + 1 overflows, i.e. when iv == TYPE_VALUE_MAX. */
1503 && integer_onep (step
)
1504 && TREE_CODE (iv1
->base
) == PLUS_EXPR
1505 && integer_onep (TREE_OPERAND (iv1
->base
, 1)))
1507 tree cond
= fold_build2 (GE_EXPR
, boolean_type_node
,
1508 TREE_OPERAND (iv1
->base
, 0), iv0
->base
);
1509 cond
= simplify_using_initial_conditions (loop
, cond
);
1510 if (integer_onep (cond
))
1511 may_be_zero
= fold_build2 (EQ_EXPR
, boolean_type_node
,
1512 TREE_OPERAND (iv1
->base
, 0),
1513 TYPE_MAX_VALUE (type
));
1517 if (TREE_CODE (iv1
->base
) == INTEGER_CST
)
1518 low
= wi::to_wide (iv1
->base
) - 1;
1519 else if (TREE_CODE (iv0
->base
) == INTEGER_CST
)
1520 low
= wi::to_wide (iv0
->base
);
1524 /* {base, -C} < n. */
1525 else if (tree_int_cst_sign_bit (iv0
->step
) && integer_zerop (iv1
->step
))
1527 step
= fold_build1 (NEGATE_EXPR
, TREE_TYPE (iv0
->step
), iv0
->step
);
1528 /* MAX - C + 1 >= n. */
1529 tree last
= wide_int_to_tree (type
, max
- wi::to_wide (step
) + 1);
1530 assumptions
= fold_build2 (GE_EXPR
, boolean_type_node
, last
, iv1
->base
);
1531 if (integer_zerop (assumptions
))
1534 num
= fold_build2 (MINUS_EXPR
, niter_type
, iv0
->base
,
1535 wide_int_to_tree (type
, min
));
1537 if (TREE_CODE (iv0
->base
) == INTEGER_CST
)
1538 high
= wi::to_wide (iv0
->base
) + 1;
1539 else if (TREE_CODE (iv1
->base
) == INTEGER_CST
)
1540 high
= wi::to_wide (iv1
->base
);
1547 /* (delta + step - 1) / step */
1548 step
= fold_convert (niter_type
, step
);
1549 num
= fold_convert (niter_type
, num
);
1550 num
= fold_build2 (PLUS_EXPR
, niter_type
, num
, step
);
1551 niter
->niter
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, num
, step
);
1553 widest_int delta
, s
;
1554 delta
= widest_int::from (high
, sgn
) - widest_int::from (low
, sgn
);
1555 s
= wi::to_widest (step
);
1556 delta
= delta
+ s
- 1;
1557 niter
->max
= wi::udiv_floor (delta
, s
);
1559 niter
->may_be_zero
= may_be_zero
;
1561 if (!integer_nonzerop (assumptions
))
1562 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1563 niter
->assumptions
, assumptions
);
1565 niter
->control
.no_overflow
= false;
1567 /* Update bound and exit condition as:
1568 bound = niter * STEP + (IVbase - STEP).
1569 { IVbase - STEP, +, STEP } != bound
1570 Here, biasing IVbase by 1 step makes 'bound' be the value before wrap.
1572 tree base_type
= TREE_TYPE (niter
->control
.base
);
1573 if (POINTER_TYPE_P (base_type
))
1575 tree utype
= unsigned_type_for (base_type
);
1577 = fold_build2 (MINUS_EXPR
, utype
,
1578 fold_convert (utype
, niter
->control
.base
),
1579 fold_convert (utype
, niter
->control
.step
));
1580 niter
->control
.base
= fold_convert (base_type
, niter
->control
.base
);
1584 = fold_build2 (MINUS_EXPR
, base_type
, niter
->control
.base
,
1585 niter
->control
.step
);
1587 span
= fold_build2 (MULT_EXPR
, niter_type
, niter
->niter
,
1588 fold_convert (niter_type
, niter
->control
.step
));
1589 niter
->bound
= fold_build2 (PLUS_EXPR
, niter_type
, span
,
1590 fold_convert (niter_type
, niter
->control
.base
));
1591 niter
->bound
= fold_convert (type
, niter
->bound
);
1592 niter
->cmp
= NE_EXPR
;
1597 /* Determines number of iterations of loop whose ending condition
1598 is IV0 < IV1. TYPE is the type of the iv. The number of
1599 iterations is stored to NITER. BNDS bounds the difference
1600 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
1601 that the exit must be taken eventually. */
1604 number_of_iterations_lt (class loop
*loop
, tree type
, affine_iv
*iv0
,
1605 affine_iv
*iv1
, class tree_niter_desc
*niter
,
1606 bool exit_must_be_taken
, bounds
*bnds
)
1608 tree niter_type
= unsigned_type_for (type
);
1609 tree delta
, step
, s
;
1612 if (integer_nonzerop (iv0
->step
))
1614 niter
->control
= *iv0
;
1615 niter
->cmp
= LT_EXPR
;
1616 niter
->bound
= iv1
->base
;
1620 niter
->control
= *iv1
;
1621 niter
->cmp
= GT_EXPR
;
1622 niter
->bound
= iv0
->base
;
1625 /* {base, -C} < n, or n < {base, C} */
1626 if (tree_int_cst_sign_bit (iv0
->step
)
1627 || (!integer_zerop (iv1
->step
) && !tree_int_cst_sign_bit (iv1
->step
)))
1628 return number_of_iterations_until_wrap (loop
, type
, iv0
, iv1
, niter
);
1630 delta
= fold_build2 (MINUS_EXPR
, niter_type
,
1631 fold_convert (niter_type
, iv1
->base
),
1632 fold_convert (niter_type
, iv0
->base
));
1634 /* First handle the special case that the step is +-1. */
1635 if ((integer_onep (iv0
->step
) && integer_zerop (iv1
->step
))
1636 || (integer_all_onesp (iv1
->step
) && integer_zerop (iv0
->step
)))
1638 /* for (i = iv0->base; i < iv1->base; i++)
1642 for (i = iv1->base; i > iv0->base; i--).
1644 In both cases # of iterations is iv1->base - iv0->base, assuming that
1645 iv1->base >= iv0->base.
1647 First try to derive a lower bound on the value of
1648 iv1->base - iv0->base, computed in full precision. If the difference
1649 is nonnegative, we are done, otherwise we must record the
1652 if (mpz_sgn (bnds
->below
) < 0)
1653 niter
->may_be_zero
= fold_build2 (LT_EXPR
, boolean_type_node
,
1654 iv1
->base
, iv0
->base
);
1655 niter
->niter
= delta
;
1656 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, bnds
->up
, false),
1657 TYPE_SIGN (niter_type
));
1658 niter
->control
.no_overflow
= true;
1662 if (integer_nonzerop (iv0
->step
))
1663 step
= fold_convert (niter_type
, iv0
->step
);
1665 step
= fold_convert (niter_type
,
1666 fold_build1 (NEGATE_EXPR
, type
, iv1
->step
));
1668 /* If we can determine the final value of the control iv exactly, we can
1669 transform the condition to != comparison. In particular, this will be
1670 the case if DELTA is constant. */
1671 if (number_of_iterations_lt_to_ne (type
, iv0
, iv1
, niter
, &delta
, step
,
1672 exit_must_be_taken
, bnds
))
1676 zps
.base
= build_int_cst (niter_type
, 0);
1678 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1679 zps does not overflow. */
1680 zps
.no_overflow
= true;
1682 return number_of_iterations_ne (loop
, type
, &zps
,
1683 delta
, niter
, true, bnds
);
1686 /* Make sure that the control iv does not overflow. */
1687 if (!assert_no_overflow_lt (type
, iv0
, iv1
, niter
, step
))
1690 /* We determine the number of iterations as (delta + step - 1) / step. For
1691 this to work, we must know that iv1->base >= iv0->base - step + 1,
1692 otherwise the loop does not roll. */
1693 assert_loop_rolls_lt (type
, iv0
, iv1
, niter
, bnds
);
1695 s
= fold_build2 (MINUS_EXPR
, niter_type
,
1696 step
, build_int_cst (niter_type
, 1));
1697 delta
= fold_build2 (PLUS_EXPR
, niter_type
, delta
, s
);
1698 niter
->niter
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, delta
, step
);
1702 wi::to_mpz (wi::to_wide (step
), mstep
, UNSIGNED
);
1703 mpz_add (tmp
, bnds
->up
, mstep
);
1704 mpz_sub_ui (tmp
, tmp
, 1);
1705 mpz_fdiv_q (tmp
, tmp
, mstep
);
1706 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, tmp
, false),
1707 TYPE_SIGN (niter_type
));
1714 /* Determines number of iterations of loop whose ending condition
1715 is IV0 <= IV1. TYPE is the type of the iv. The number of
1716 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
1717 we know that this condition must eventually become false (we derived this
1718 earlier, and possibly set NITER->assumptions to make sure this
1719 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1722 number_of_iterations_le (class loop
*loop
, tree type
, affine_iv
*iv0
,
1723 affine_iv
*iv1
, class tree_niter_desc
*niter
,
1724 bool exit_must_be_taken
, bounds
*bnds
)
1728 if (POINTER_TYPE_P (type
))
1731 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1732 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1733 value of the type. This we must know anyway, since if it is
1734 equal to this value, the loop rolls forever. We do not check
1735 this condition for pointer type ivs, as the code cannot rely on
1736 the object to that the pointer points being placed at the end of
1737 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1738 not defined for pointers). */
1740 if (!exit_must_be_taken
&& !POINTER_TYPE_P (type
))
1742 if (integer_nonzerop (iv0
->step
))
1743 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1744 iv1
->base
, TYPE_MAX_VALUE (type
));
1746 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1747 iv0
->base
, TYPE_MIN_VALUE (type
));
1749 if (integer_zerop (assumption
))
1751 if (!integer_nonzerop (assumption
))
1752 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1753 niter
->assumptions
, assumption
);
1756 if (integer_nonzerop (iv0
->step
))
1758 if (POINTER_TYPE_P (type
))
1759 iv1
->base
= fold_build_pointer_plus_hwi (iv1
->base
, 1);
1761 iv1
->base
= fold_build2 (PLUS_EXPR
, type1
, iv1
->base
,
1762 build_int_cst (type1
, 1));
1764 else if (POINTER_TYPE_P (type
))
1765 iv0
->base
= fold_build_pointer_plus_hwi (iv0
->base
, -1);
1767 iv0
->base
= fold_build2 (MINUS_EXPR
, type1
,
1768 iv0
->base
, build_int_cst (type1
, 1));
1770 bounds_add (bnds
, 1, type1
);
1772 return number_of_iterations_lt (loop
, type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1776 /* Dumps description of affine induction variable IV to FILE. */
1779 dump_affine_iv (FILE *file
, affine_iv
*iv
)
1781 if (!integer_zerop (iv
->step
))
1782 fprintf (file
, "[");
1784 print_generic_expr (dump_file
, iv
->base
, TDF_SLIM
);
1786 if (!integer_zerop (iv
->step
))
1788 fprintf (file
, ", + , ");
1789 print_generic_expr (dump_file
, iv
->step
, TDF_SLIM
);
1790 fprintf (file
, "]%s", iv
->no_overflow
? "(no_overflow)" : "");
1794 /* Determine the number of iterations according to condition (for staying
1795 inside loop) which compares two induction variables using comparison
1796 operator CODE. The induction variable on left side of the comparison
1797 is IV0, the right-hand side is IV1. Both induction variables must have
1798 type TYPE, which must be an integer or pointer type. The steps of the
1799 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1801 LOOP is the loop whose number of iterations we are determining.
1803 ONLY_EXIT is true if we are sure this is the only way the loop could be
1804 exited (including possibly non-returning function calls, exceptions, etc.)
1805 -- in this case we can use the information whether the control induction
1806 variables can overflow or not in a more efficient way.
1808 if EVERY_ITERATION is true, we know the test is executed on every iteration.
1810 The results (number of iterations and assumptions as described in
1811 comments at class tree_niter_desc in tree-ssa-loop.h) are stored to NITER.
1812 Returns false if it fails to determine number of iterations, true if it
1813 was determined (possibly with some assumptions). */
1816 number_of_iterations_cond (class loop
*loop
,
1817 tree type
, affine_iv
*iv0
, enum tree_code code
,
1818 affine_iv
*iv1
, class tree_niter_desc
*niter
,
1819 bool only_exit
, bool every_iteration
)
1821 bool exit_must_be_taken
= false, ret
;
1824 /* If the test is not executed every iteration, wrapping may make the test
1826 TODO: the overflow case can be still used as unreliable estimate of upper
1827 bound. But we have no API to pass it down to number of iterations code
1828 and, at present, it will not use it anyway. */
1829 if (!every_iteration
1830 && (!iv0
->no_overflow
|| !iv1
->no_overflow
1831 || code
== NE_EXPR
|| code
== EQ_EXPR
))
1834 /* The meaning of these assumptions is this:
1836 then the rest of information does not have to be valid
1837 if may_be_zero then the loop does not roll, even if
1839 niter
->assumptions
= boolean_true_node
;
1840 niter
->may_be_zero
= boolean_false_node
;
1841 niter
->niter
= NULL_TREE
;
1843 niter
->bound
= NULL_TREE
;
1844 niter
->cmp
= ERROR_MARK
;
1846 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1847 the control variable is on lhs. */
1848 if (code
== GE_EXPR
|| code
== GT_EXPR
1849 || (code
== NE_EXPR
&& integer_zerop (iv0
->step
)))
1851 std::swap (iv0
, iv1
);
1852 code
= swap_tree_comparison (code
);
1855 if (POINTER_TYPE_P (type
))
1857 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1858 to the same object. If they do, the control variable cannot wrap
1859 (as wrap around the bounds of memory will never return a pointer
1860 that would be guaranteed to point to the same object, even if we
1861 avoid undefined behavior by casting to size_t and back). */
1862 iv0
->no_overflow
= true;
1863 iv1
->no_overflow
= true;
1866 /* If the control induction variable does not overflow and the only exit
1867 from the loop is the one that we analyze, we know it must be taken
1871 if (!integer_zerop (iv0
->step
) && iv0
->no_overflow
)
1872 exit_must_be_taken
= true;
1873 else if (!integer_zerop (iv1
->step
) && iv1
->no_overflow
)
1874 exit_must_be_taken
= true;
1877 /* We can handle cases which neither of the sides of the comparison is
1880 {iv0.base, iv0.step} cmp_code {iv1.base, iv1.step}
1882 {iv0.base, iv0.step - iv1.step} cmp_code {iv1.base, 0}
1884 provided that either below condition is satisfied:
1886 a) the test is NE_EXPR;
1887 b) iv0 and iv1 do not overflow and iv0.step - iv1.step is of
1888 the same sign and of less or equal magnitude than iv0.step
1890 This rarely occurs in practice, but it is simple enough to manage. */
1891 if (!integer_zerop (iv0
->step
) && !integer_zerop (iv1
->step
))
1893 tree step_type
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1894 tree step
= fold_binary_to_constant (MINUS_EXPR
, step_type
,
1895 iv0
->step
, iv1
->step
);
1897 /* For code other than NE_EXPR we have to ensure moving the evolution
1898 of IV1 to that of IV0 does not introduce overflow. */
1899 if (TREE_CODE (step
) != INTEGER_CST
1900 || !iv0
->no_overflow
|| !iv1
->no_overflow
)
1902 if (code
!= NE_EXPR
)
1904 iv0
->no_overflow
= false;
1906 /* If the new step of IV0 has changed sign or is of greater
1907 magnitude then we do not know whether IV0 does overflow
1908 and thus the transform is not valid for code other than NE_EXPR. */
1909 else if (tree_int_cst_sign_bit (step
) != tree_int_cst_sign_bit (iv0
->step
)
1910 || wi::gtu_p (wi::abs (wi::to_widest (step
)),
1911 wi::abs (wi::to_widest (iv0
->step
))))
1913 if (POINTER_TYPE_P (type
) && code
!= NE_EXPR
)
1914 /* For relational pointer compares we have further guarantees
1915 that the pointers always point to the same object (or one
1916 after it) and that objects do not cross the zero page. So
1917 not only is the transform always valid for relational
1918 pointer compares, we also know the resulting IV does not
1921 else if (code
!= NE_EXPR
)
1924 iv0
->no_overflow
= false;
1928 iv1
->step
= build_int_cst (step_type
, 0);
1929 iv1
->no_overflow
= true;
1932 /* If the result of the comparison is a constant, the loop is weird. More
1933 precise handling would be possible, but the situation is not common enough
1934 to waste time on it. */
1935 if (integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
))
1938 /* If the loop exits immediately, there is nothing to do. */
1939 tree tem
= fold_binary (code
, boolean_type_node
, iv0
->base
, iv1
->base
);
1940 if (tem
&& integer_zerop (tem
))
1942 if (!every_iteration
)
1944 niter
->niter
= build_int_cst (unsigned_type_for (type
), 0);
1949 /* OK, now we know we have a senseful loop. Handle several cases, depending
1950 on what comparison operator is used. */
1951 bound_difference (loop
, iv1
->base
, iv0
->base
, &bnds
);
1953 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1956 "Analyzing # of iterations of loop %d\n", loop
->num
);
1958 fprintf (dump_file
, " exit condition ");
1959 dump_affine_iv (dump_file
, iv0
);
1960 fprintf (dump_file
, " %s ",
1961 code
== NE_EXPR
? "!="
1962 : code
== LT_EXPR
? "<"
1964 dump_affine_iv (dump_file
, iv1
);
1965 fprintf (dump_file
, "\n");
1967 fprintf (dump_file
, " bounds on difference of bases: ");
1968 mpz_out_str (dump_file
, 10, bnds
.below
);
1969 fprintf (dump_file
, " ... ");
1970 mpz_out_str (dump_file
, 10, bnds
.up
);
1971 fprintf (dump_file
, "\n");
1977 gcc_assert (integer_zerop (iv1
->step
));
1978 ret
= number_of_iterations_ne (loop
, type
, iv0
, iv1
->base
, niter
,
1979 exit_must_be_taken
, &bnds
);
1983 ret
= number_of_iterations_lt (loop
, type
, iv0
, iv1
, niter
,
1984 exit_must_be_taken
, &bnds
);
1988 ret
= number_of_iterations_le (loop
, type
, iv0
, iv1
, niter
,
1989 exit_must_be_taken
, &bnds
);
1996 mpz_clear (bnds
.up
);
1997 mpz_clear (bnds
.below
);
1999 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2003 fprintf (dump_file
, " result:\n");
2004 if (!integer_nonzerop (niter
->assumptions
))
2006 fprintf (dump_file
, " under assumptions ");
2007 print_generic_expr (dump_file
, niter
->assumptions
, TDF_SLIM
);
2008 fprintf (dump_file
, "\n");
2011 if (!integer_zerop (niter
->may_be_zero
))
2013 fprintf (dump_file
, " zero if ");
2014 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
2015 fprintf (dump_file
, "\n");
2018 fprintf (dump_file
, " # of iterations ");
2019 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
2020 fprintf (dump_file
, ", bounded by ");
2021 print_decu (niter
->max
, dump_file
);
2022 fprintf (dump_file
, "\n");
2025 fprintf (dump_file
, " failed\n\n");
2030 /* Return an expression that computes the popcount of src. */
2033 build_popcount_expr (tree src
)
2036 bool use_ifn
= false;
2037 int prec
= TYPE_PRECISION (TREE_TYPE (src
));
2038 int i_prec
= TYPE_PRECISION (integer_type_node
);
2039 int li_prec
= TYPE_PRECISION (long_integer_type_node
);
2040 int lli_prec
= TYPE_PRECISION (long_long_integer_type_node
);
2042 tree utype
= unsigned_type_for (TREE_TYPE (src
));
2043 src
= fold_convert (utype
, src
);
2045 if (direct_internal_fn_supported_p (IFN_POPCOUNT
, utype
, OPTIMIZE_FOR_BOTH
))
2047 else if (prec
<= i_prec
)
2048 fn
= builtin_decl_implicit (BUILT_IN_POPCOUNT
);
2049 else if (prec
== li_prec
)
2050 fn
= builtin_decl_implicit (BUILT_IN_POPCOUNTL
);
2051 else if (prec
== lli_prec
|| prec
== 2 * lli_prec
)
2052 fn
= builtin_decl_implicit (BUILT_IN_POPCOUNTLL
);
2058 call
= build_call_expr_internal_loc (UNKNOWN_LOCATION
, IFN_POPCOUNT
,
2059 integer_type_node
, 1, src
);
2060 else if (prec
== 2 * lli_prec
)
2062 tree src1
= fold_convert (long_long_unsigned_type_node
,
2063 fold_build2 (RSHIFT_EXPR
, TREE_TYPE (src
),
2065 build_int_cst (integer_type_node
,
2067 tree src2
= fold_convert (long_long_unsigned_type_node
, src
);
2068 tree call1
= build_call_expr (fn
, 1, src1
);
2069 tree call2
= build_call_expr (fn
, 1, src2
);
2070 call
= fold_build2 (PLUS_EXPR
, integer_type_node
, call1
, call2
);
2075 src
= fold_convert (unsigned_type_node
, src
);
2077 call
= build_call_expr (fn
, 1, src
);
2083 /* Utility function to check if OP is defined by a stmt
2084 that is a val - 1. */
2087 ssa_defined_by_minus_one_stmt_p (tree op
, tree val
)
2090 return (TREE_CODE (op
) == SSA_NAME
2091 && (stmt
= SSA_NAME_DEF_STMT (op
))
2092 && is_gimple_assign (stmt
)
2093 && (gimple_assign_rhs_code (stmt
) == PLUS_EXPR
)
2094 && val
== gimple_assign_rhs1 (stmt
)
2095 && integer_minus_onep (gimple_assign_rhs2 (stmt
)));
2098 /* See comment below for number_of_iterations_bitcount.
2099 For popcount, we have:
2114 number_of_iterations_popcount (loop_p loop
, edge exit
,
2115 enum tree_code code
,
2116 class tree_niter_desc
*niter
)
2118 bool modify_before_test
= true;
2121 /* Check that condition for staying inside the loop is like
2123 gimple
*cond_stmt
= last_stmt (exit
->src
);
2125 || gimple_code (cond_stmt
) != GIMPLE_COND
2127 || !integer_zerop (gimple_cond_rhs (cond_stmt
))
2128 || TREE_CODE (gimple_cond_lhs (cond_stmt
)) != SSA_NAME
)
2131 tree iv_2
= gimple_cond_lhs (cond_stmt
);
2132 gimple
*iv_2_stmt
= SSA_NAME_DEF_STMT (iv_2
);
2134 /* If the test comes before the iv modification, then these will actually be
2135 iv_1 and a phi node. */
2136 if (gimple_code (iv_2_stmt
) == GIMPLE_PHI
2137 && gimple_bb (iv_2_stmt
) == loop
->header
2138 && gimple_phi_num_args (iv_2_stmt
) == 2
2139 && (TREE_CODE (gimple_phi_arg_def (iv_2_stmt
,
2140 loop_latch_edge (loop
)->dest_idx
))
2143 /* iv_2 is actually one of the inputs to the phi. */
2144 iv_2
= gimple_phi_arg_def (iv_2_stmt
, loop_latch_edge (loop
)->dest_idx
);
2145 iv_2_stmt
= SSA_NAME_DEF_STMT (iv_2
);
2146 modify_before_test
= false;
2149 /* Make sure iv_2_stmt is an and stmt (iv_2 = _1 & iv_1). */
2150 if (!is_gimple_assign (iv_2_stmt
)
2151 || gimple_assign_rhs_code (iv_2_stmt
) != BIT_AND_EXPR
)
2154 tree iv_1
= gimple_assign_rhs1 (iv_2_stmt
);
2155 tree _1
= gimple_assign_rhs2 (iv_2_stmt
);
2157 /* Check that _1 is defined by (_1 = iv_1 + -1).
2158 Also make sure that _1 is the same in and_stmt and _1 defining stmt.
2159 Also canonicalize if _1 and _b11 are revrsed. */
2160 if (ssa_defined_by_minus_one_stmt_p (iv_1
, _1
))
2161 std::swap (iv_1
, _1
);
2162 else if (ssa_defined_by_minus_one_stmt_p (_1
, iv_1
))
2167 /* Check the recurrence. */
2168 gimple
*phi
= SSA_NAME_DEF_STMT (iv_1
);
2169 if (gimple_code (phi
) != GIMPLE_PHI
2170 || (gimple_bb (phi
) != loop_latch_edge (loop
)->dest
)
2171 || (iv_2
!= gimple_phi_arg_def (phi
, loop_latch_edge (loop
)->dest_idx
)))
2174 /* We found a match. */
2175 tree src
= gimple_phi_arg_def (phi
, loop_preheader_edge (loop
)->dest_idx
);
2176 int src_precision
= TYPE_PRECISION (TREE_TYPE (src
));
2178 /* Get the corresponding popcount builtin. */
2179 tree expr
= build_popcount_expr (src
);
2184 max
= src_precision
;
2186 tree may_be_zero
= boolean_false_node
;
2188 if (modify_before_test
)
2190 expr
= fold_build2 (MINUS_EXPR
, integer_type_node
, expr
,
2193 may_be_zero
= fold_build2 (EQ_EXPR
, boolean_type_node
, src
,
2194 build_zero_cst (TREE_TYPE (src
)));
2197 expr
= fold_convert (unsigned_type_node
, expr
);
2199 niter
->assumptions
= boolean_true_node
;
2200 niter
->may_be_zero
= simplify_using_initial_conditions (loop
, may_be_zero
);
2201 niter
->niter
= simplify_using_initial_conditions(loop
, expr
);
2203 if (TREE_CODE (niter
->niter
) == INTEGER_CST
)
2204 niter
->max
= tree_to_uhwi (niter
->niter
);
2208 niter
->bound
= NULL_TREE
;
2209 niter
->cmp
= ERROR_MARK
;
2213 /* Return an expression that counts the leading/trailing zeroes of src.
2215 If define_at_zero is true, then the built expression will be defined to
2216 return the precision of src when src == 0 (using either a conditional
2217 expression or a suitable internal function).
2218 Otherwise, we can elide the conditional expression and let src = 0 invoke
2219 undefined behaviour. */
2222 build_cltz_expr (tree src
, bool leading
, bool define_at_zero
)
2225 internal_fn ifn
= leading
? IFN_CLZ
: IFN_CTZ
;
2226 bool use_ifn
= false;
2227 int prec
= TYPE_PRECISION (TREE_TYPE (src
));
2228 int i_prec
= TYPE_PRECISION (integer_type_node
);
2229 int li_prec
= TYPE_PRECISION (long_integer_type_node
);
2230 int lli_prec
= TYPE_PRECISION (long_long_integer_type_node
);
2232 tree utype
= unsigned_type_for (TREE_TYPE (src
));
2233 src
= fold_convert (utype
, src
);
2235 if (direct_internal_fn_supported_p (ifn
, utype
, OPTIMIZE_FOR_BOTH
))
2237 else if (prec
<= i_prec
)
2238 fn
= leading
? builtin_decl_implicit (BUILT_IN_CLZ
)
2239 : builtin_decl_implicit (BUILT_IN_CTZ
);
2240 else if (prec
== li_prec
)
2241 fn
= leading
? builtin_decl_implicit (BUILT_IN_CLZL
)
2242 : builtin_decl_implicit (BUILT_IN_CTZL
);
2243 else if (prec
== lli_prec
|| prec
== 2 * lli_prec
)
2244 fn
= leading
? builtin_decl_implicit (BUILT_IN_CLZLL
)
2245 : builtin_decl_implicit (BUILT_IN_CTZLL
);
2252 call
= build_call_expr_internal_loc (UNKNOWN_LOCATION
, ifn
,
2253 integer_type_node
, 1, src
);
2255 int optab_defined_at_zero
2257 ? CLZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (utype
), val
)
2258 : CTZ_DEFINED_VALUE_AT_ZERO (SCALAR_INT_TYPE_MODE (utype
), val
));
2259 if (define_at_zero
&& !(optab_defined_at_zero
== 2 && val
== prec
))
2261 tree is_zero
= fold_build2 (NE_EXPR
, boolean_type_node
, src
,
2262 build_zero_cst (TREE_TYPE (src
)));
2263 call
= fold_build3 (COND_EXPR
, integer_type_node
, is_zero
, call
,
2264 build_int_cst (integer_type_node
, prec
));
2267 else if (prec
== 2 * lli_prec
)
2269 tree src1
= fold_convert (long_long_unsigned_type_node
,
2270 fold_build2 (RSHIFT_EXPR
, TREE_TYPE (src
),
2272 build_int_cst (integer_type_node
,
2274 tree src2
= fold_convert (long_long_unsigned_type_node
, src
);
2275 /* We count the zeroes in src1, and add the number in src2 when src1
2278 std::swap (src1
, src2
);
2279 tree call1
= build_call_expr (fn
, 1, src1
);
2280 tree call2
= build_call_expr (fn
, 1, src2
);
2283 tree is_zero2
= fold_build2 (NE_EXPR
, boolean_type_node
, src2
,
2284 build_zero_cst (TREE_TYPE (src2
)));
2285 call2
= fold_build3 (COND_EXPR
, integer_type_node
, is_zero2
, call2
,
2286 build_int_cst (integer_type_node
, lli_prec
));
2288 tree is_zero1
= fold_build2 (NE_EXPR
, boolean_type_node
, src1
,
2289 build_zero_cst (TREE_TYPE (src1
)));
2290 call
= fold_build3 (COND_EXPR
, integer_type_node
, is_zero1
, call1
,
2291 fold_build2 (PLUS_EXPR
, integer_type_node
, call2
,
2292 build_int_cst (integer_type_node
,
2298 src
= fold_convert (unsigned_type_node
, src
);
2300 call
= build_call_expr (fn
, 1, src
);
2303 tree is_zero
= fold_build2 (NE_EXPR
, boolean_type_node
, src
,
2304 build_zero_cst (TREE_TYPE (src
)));
2305 call
= fold_build3 (COND_EXPR
, integer_type_node
, is_zero
, call
,
2306 build_int_cst (integer_type_node
, prec
));
2309 if (leading
&& prec
< i_prec
)
2310 call
= fold_build2 (MINUS_EXPR
, integer_type_node
, call
,
2311 build_int_cst (integer_type_node
, i_prec
- prec
));
2317 /* See comment below for number_of_iterations_bitcount.
2318 For c[lt]z, we have:
2321 iv_2 = iv_1 << 1 OR iv_1 >> 1
2324 if (iv & 1 << (prec-1)) OR (iv & 1)
2327 src precision - c[lt]z (src)
2332 number_of_iterations_cltz (loop_p loop
, edge exit
,
2333 enum tree_code code
,
2334 class tree_niter_desc
*niter
)
2336 bool modify_before_test
= true;
2341 /* Check that condition for staying inside the loop is like
2343 gimple
*cond_stmt
= last_stmt (exit
->src
);
2345 || gimple_code (cond_stmt
) != GIMPLE_COND
2346 || (code
!= EQ_EXPR
&& code
!= GE_EXPR
)
2347 || !integer_zerop (gimple_cond_rhs (cond_stmt
))
2348 || TREE_CODE (gimple_cond_lhs (cond_stmt
)) != SSA_NAME
)
2351 if (code
== EQ_EXPR
)
2353 /* Make sure we check a bitwise and with a suitable constant */
2354 gimple
*and_stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (cond_stmt
));
2355 if (!is_gimple_assign (and_stmt
)
2356 || gimple_assign_rhs_code (and_stmt
) != BIT_AND_EXPR
2357 || !integer_pow2p (gimple_assign_rhs2 (and_stmt
))
2358 || TREE_CODE (gimple_assign_rhs1 (and_stmt
)) != SSA_NAME
)
2361 checked_bit
= tree_log2 (gimple_assign_rhs2 (and_stmt
));
2363 iv_2
= gimple_assign_rhs1 (and_stmt
);
2367 /* We have a GE_EXPR - a signed comparison with zero is equivalent to
2368 testing the leading bit, so check for this pattern too. */
2370 iv_2
= gimple_cond_lhs (cond_stmt
);
2371 tree test_value_type
= TREE_TYPE (iv_2
);
2373 if (TYPE_UNSIGNED (test_value_type
))
2376 gimple
*test_value_stmt
= SSA_NAME_DEF_STMT (iv_2
);
2378 if (is_gimple_assign (test_value_stmt
)
2379 && gimple_assign_rhs_code (test_value_stmt
) == NOP_EXPR
)
2381 /* If the test value comes from a NOP_EXPR, then we need to unwrap
2382 this. We conservatively require that both types have the same
2384 iv_2
= gimple_assign_rhs1 (test_value_stmt
);
2385 tree rhs_type
= TREE_TYPE (iv_2
);
2386 if (TREE_CODE (iv_2
) != SSA_NAME
2387 || TREE_CODE (rhs_type
) != INTEGER_TYPE
2388 || (TYPE_PRECISION (rhs_type
)
2389 != TYPE_PRECISION (test_value_type
)))
2393 checked_bit
= TYPE_PRECISION (test_value_type
) - 1;
2396 gimple
*iv_2_stmt
= SSA_NAME_DEF_STMT (iv_2
);
2398 /* If the test comes before the iv modification, then these will actually be
2399 iv_1 and a phi node. */
2400 if (gimple_code (iv_2_stmt
) == GIMPLE_PHI
2401 && gimple_bb (iv_2_stmt
) == loop
->header
2402 && gimple_phi_num_args (iv_2_stmt
) == 2
2403 && (TREE_CODE (gimple_phi_arg_def (iv_2_stmt
,
2404 loop_latch_edge (loop
)->dest_idx
))
2407 /* iv_2 is actually one of the inputs to the phi. */
2408 iv_2
= gimple_phi_arg_def (iv_2_stmt
, loop_latch_edge (loop
)->dest_idx
);
2409 iv_2_stmt
= SSA_NAME_DEF_STMT (iv_2
);
2410 modify_before_test
= false;
2413 /* Make sure iv_2_stmt is a logical shift by one stmt:
2414 iv_2 = iv_1 {<<|>>} 1 */
2415 if (!is_gimple_assign (iv_2_stmt
)
2416 || (gimple_assign_rhs_code (iv_2_stmt
) != LSHIFT_EXPR
2417 && (gimple_assign_rhs_code (iv_2_stmt
) != RSHIFT_EXPR
2418 || !TYPE_UNSIGNED (TREE_TYPE (gimple_assign_lhs (iv_2_stmt
)))))
2419 || !integer_onep (gimple_assign_rhs2 (iv_2_stmt
)))
2422 bool left_shift
= (gimple_assign_rhs_code (iv_2_stmt
) == LSHIFT_EXPR
);
2424 tree iv_1
= gimple_assign_rhs1 (iv_2_stmt
);
2426 /* Check the recurrence. */
2427 gimple
*phi
= SSA_NAME_DEF_STMT (iv_1
);
2428 if (gimple_code (phi
) != GIMPLE_PHI
2429 || (gimple_bb (phi
) != loop_latch_edge (loop
)->dest
)
2430 || (iv_2
!= gimple_phi_arg_def (phi
, loop_latch_edge (loop
)->dest_idx
)))
2433 /* We found a match. */
2434 tree src
= gimple_phi_arg_def (phi
, loop_preheader_edge (loop
)->dest_idx
);
2435 int src_precision
= TYPE_PRECISION (TREE_TYPE (src
));
2437 /* Apply any needed preprocessing to src. */
2438 int num_ignored_bits
;
2440 num_ignored_bits
= src_precision
- checked_bit
- 1;
2442 num_ignored_bits
= checked_bit
;
2444 if (modify_before_test
)
2447 if (num_ignored_bits
!= 0)
2448 src
= fold_build2 (left_shift
? LSHIFT_EXPR
: RSHIFT_EXPR
,
2449 TREE_TYPE (src
), src
,
2450 build_int_cst (integer_type_node
, num_ignored_bits
));
2452 /* Get the corresponding c[lt]z builtin. */
2453 tree expr
= build_cltz_expr (src
, left_shift
, false);
2458 max
= src_precision
- num_ignored_bits
- 1;
2460 expr
= fold_convert (unsigned_type_node
, expr
);
2462 tree assumptions
= fold_build2 (NE_EXPR
, boolean_type_node
, src
,
2463 build_zero_cst (TREE_TYPE (src
)));
2465 niter
->assumptions
= simplify_using_initial_conditions (loop
, assumptions
);
2466 niter
->may_be_zero
= boolean_false_node
;
2467 niter
->niter
= simplify_using_initial_conditions (loop
, expr
);
2469 if (TREE_CODE (niter
->niter
) == INTEGER_CST
)
2470 niter
->max
= tree_to_uhwi (niter
->niter
);
2474 niter
->bound
= NULL_TREE
;
2475 niter
->cmp
= ERROR_MARK
;
2480 /* See comment below for number_of_iterations_bitcount.
2481 For c[lt]z complement, we have:
2484 iv_2 = iv_1 >> 1 OR iv_1 << 1
2490 src precision - c[lt]z (src)
2495 number_of_iterations_cltz_complement (loop_p loop
, edge exit
,
2496 enum tree_code code
,
2497 class tree_niter_desc
*niter
)
2499 bool modify_before_test
= true;
2502 /* Check that condition for staying inside the loop is like
2504 gimple
*cond_stmt
= last_stmt (exit
->src
);
2506 || gimple_code (cond_stmt
) != GIMPLE_COND
2508 || !integer_zerop (gimple_cond_rhs (cond_stmt
))
2509 || TREE_CODE (gimple_cond_lhs (cond_stmt
)) != SSA_NAME
)
2512 tree iv_2
= gimple_cond_lhs (cond_stmt
);
2513 gimple
*iv_2_stmt
= SSA_NAME_DEF_STMT (iv_2
);
2515 /* If the test comes before the iv modification, then these will actually be
2516 iv_1 and a phi node. */
2517 if (gimple_code (iv_2_stmt
) == GIMPLE_PHI
2518 && gimple_bb (iv_2_stmt
) == loop
->header
2519 && gimple_phi_num_args (iv_2_stmt
) == 2
2520 && (TREE_CODE (gimple_phi_arg_def (iv_2_stmt
,
2521 loop_latch_edge (loop
)->dest_idx
))
2524 /* iv_2 is actually one of the inputs to the phi. */
2525 iv_2
= gimple_phi_arg_def (iv_2_stmt
, loop_latch_edge (loop
)->dest_idx
);
2526 iv_2_stmt
= SSA_NAME_DEF_STMT (iv_2
);
2527 modify_before_test
= false;
2530 /* Make sure iv_2_stmt is a logical shift by one stmt:
2531 iv_2 = iv_1 {>>|<<} 1 */
2532 if (!is_gimple_assign (iv_2_stmt
)
2533 || (gimple_assign_rhs_code (iv_2_stmt
) != LSHIFT_EXPR
2534 && (gimple_assign_rhs_code (iv_2_stmt
) != RSHIFT_EXPR
2535 || !TYPE_UNSIGNED (TREE_TYPE (gimple_assign_lhs (iv_2_stmt
)))))
2536 || !integer_onep (gimple_assign_rhs2 (iv_2_stmt
)))
2539 bool left_shift
= (gimple_assign_rhs_code (iv_2_stmt
) == LSHIFT_EXPR
);
2541 tree iv_1
= gimple_assign_rhs1 (iv_2_stmt
);
2543 /* Check the recurrence. */
2544 gimple
*phi
= SSA_NAME_DEF_STMT (iv_1
);
2545 if (gimple_code (phi
) != GIMPLE_PHI
2546 || (gimple_bb (phi
) != loop_latch_edge (loop
)->dest
)
2547 || (iv_2
!= gimple_phi_arg_def (phi
, loop_latch_edge (loop
)->dest_idx
)))
2550 /* We found a match. */
2551 tree src
= gimple_phi_arg_def (phi
, loop_preheader_edge (loop
)->dest_idx
);
2552 int src_precision
= TYPE_PRECISION (TREE_TYPE (src
));
2554 /* Get the corresponding c[lt]z builtin. */
2555 tree expr
= build_cltz_expr (src
, !left_shift
, true);
2560 expr
= fold_build2 (MINUS_EXPR
, integer_type_node
,
2561 build_int_cst (integer_type_node
, src_precision
),
2564 max
= src_precision
;
2566 tree may_be_zero
= boolean_false_node
;
2568 if (modify_before_test
)
2570 expr
= fold_build2 (MINUS_EXPR
, integer_type_node
, expr
,
2573 may_be_zero
= fold_build2 (EQ_EXPR
, boolean_type_node
, src
,
2574 build_zero_cst (TREE_TYPE (src
)));
2577 expr
= fold_convert (unsigned_type_node
, expr
);
2579 niter
->assumptions
= boolean_true_node
;
2580 niter
->may_be_zero
= simplify_using_initial_conditions (loop
, may_be_zero
);
2581 niter
->niter
= simplify_using_initial_conditions (loop
, expr
);
2583 if (TREE_CODE (niter
->niter
) == INTEGER_CST
)
2584 niter
->max
= tree_to_uhwi (niter
->niter
);
2588 niter
->bound
= NULL_TREE
;
2589 niter
->cmp
= ERROR_MARK
;
2593 /* See if LOOP contains a bit counting idiom. The idiom consists of two parts:
2594 1. A modification to the induction variabler;.
2595 2. A test to determine whether or not to exit the loop.
2597 These can come in either order - i.e.:
2600 iv_1 = PHI <src(2), iv_2(4)>
2607 iv_2 = modify (iv_1)
2613 iv_1 = PHI <src(2), iv_2(4)>
2614 iv_2 = modify (iv_1)
2622 The second form can be generated by copying the loop header out of the loop.
2624 In the first case, the number of latch executions will be equal to the
2625 number of induction variable modifications required before the test fails.
2627 In the second case (modify_before_test), if we assume that the number of
2628 modifications required before the test fails is nonzero, then the number of
2629 latch executions will be one less than this number.
2631 If we recognise the pattern, then we update niter accordingly, and return
2635 number_of_iterations_bitcount (loop_p loop
, edge exit
,
2636 enum tree_code code
,
2637 class tree_niter_desc
*niter
)
2639 return (number_of_iterations_popcount (loop
, exit
, code
, niter
)
2640 || number_of_iterations_cltz (loop
, exit
, code
, niter
)
2641 || number_of_iterations_cltz_complement (loop
, exit
, code
, niter
));
2644 /* Substitute NEW_TREE for OLD in EXPR and fold the result.
2645 If VALUEIZE is non-NULL then OLD and NEW_TREE are ignored and instead
2646 all SSA names are replaced with the result of calling the VALUEIZE
2647 function with the SSA name as argument. */
2650 simplify_replace_tree (tree expr
, tree old
, tree new_tree
,
2651 tree (*valueize
) (tree
, void*), void *context
,
2655 tree ret
= NULL_TREE
, e
, se
;
2660 /* Do not bother to replace constants. */
2661 if (CONSTANT_CLASS_P (expr
))
2666 if (TREE_CODE (expr
) == SSA_NAME
)
2668 new_tree
= valueize (expr
, context
);
2669 if (new_tree
!= expr
)
2673 else if (expr
== old
2674 || operand_equal_p (expr
, old
, 0))
2675 return unshare_expr (new_tree
);
2680 n
= TREE_OPERAND_LENGTH (expr
);
2681 for (i
= 0; i
< n
; i
++)
2683 e
= TREE_OPERAND (expr
, i
);
2684 se
= simplify_replace_tree (e
, old
, new_tree
, valueize
, context
, do_fold
);
2689 ret
= copy_node (expr
);
2691 TREE_OPERAND (ret
, i
) = se
;
2694 return (ret
? (do_fold
? fold (ret
) : ret
) : expr
);
2697 /* Expand definitions of ssa names in EXPR as long as they are simple
2698 enough, and return the new expression. If STOP is specified, stop
2699 expanding if EXPR equals to it. */
2702 expand_simple_operations (tree expr
, tree stop
, hash_map
<tree
, tree
> &cache
)
2705 tree ret
= NULL_TREE
, e
, ee
, e1
;
2706 enum tree_code code
;
2709 if (expr
== NULL_TREE
)
2712 if (is_gimple_min_invariant (expr
))
2715 code
= TREE_CODE (expr
);
2716 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
2718 n
= TREE_OPERAND_LENGTH (expr
);
2719 for (i
= 0; i
< n
; i
++)
2721 e
= TREE_OPERAND (expr
, i
);
2724 /* SCEV analysis feeds us with a proper expression
2725 graph matching the SSA graph. Avoid turning it
2726 into a tree here, thus handle tree sharing
2728 ??? The SSA walk below still turns the SSA graph
2729 into a tree but until we find a testcase do not
2730 introduce additional tree sharing here. */
2732 tree
&cee
= cache
.get_or_insert (e
, &existed_p
);
2738 ee
= expand_simple_operations (e
, stop
, cache
);
2740 *cache
.get (e
) = ee
;
2746 ret
= copy_node (expr
);
2748 TREE_OPERAND (ret
, i
) = ee
;
2754 fold_defer_overflow_warnings ();
2756 fold_undefer_and_ignore_overflow_warnings ();
2760 /* Stop if it's not ssa name or the one we don't want to expand. */
2761 if (TREE_CODE (expr
) != SSA_NAME
|| expr
== stop
)
2764 stmt
= SSA_NAME_DEF_STMT (expr
);
2765 if (gimple_code (stmt
) == GIMPLE_PHI
)
2767 basic_block src
, dest
;
2769 if (gimple_phi_num_args (stmt
) != 1)
2771 e
= PHI_ARG_DEF (stmt
, 0);
2773 /* Avoid propagating through loop exit phi nodes, which
2774 could break loop-closed SSA form restrictions. */
2775 dest
= gimple_bb (stmt
);
2776 src
= single_pred (dest
);
2777 if (TREE_CODE (e
) == SSA_NAME
2778 && src
->loop_father
!= dest
->loop_father
)
2781 return expand_simple_operations (e
, stop
, cache
);
2783 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2786 /* Avoid expanding to expressions that contain SSA names that need
2787 to take part in abnormal coalescing. */
2789 FOR_EACH_SSA_TREE_OPERAND (e
, stmt
, iter
, SSA_OP_USE
)
2790 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (e
))
2793 e
= gimple_assign_rhs1 (stmt
);
2794 code
= gimple_assign_rhs_code (stmt
);
2795 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
2797 if (is_gimple_min_invariant (e
))
2800 if (code
== SSA_NAME
)
2801 return expand_simple_operations (e
, stop
, cache
);
2802 else if (code
== ADDR_EXPR
)
2805 tree base
= get_addr_base_and_unit_offset (TREE_OPERAND (e
, 0),
2808 && TREE_CODE (base
) == MEM_REF
)
2810 ee
= expand_simple_operations (TREE_OPERAND (base
, 0), stop
,
2812 return fold_build2 (POINTER_PLUS_EXPR
, TREE_TYPE (expr
), ee
,
2813 wide_int_to_tree (sizetype
,
2814 mem_ref_offset (base
)
2825 /* Casts are simple. */
2826 ee
= expand_simple_operations (e
, stop
, cache
);
2827 return fold_build1 (code
, TREE_TYPE (expr
), ee
);
2832 if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (expr
))
2833 && TYPE_OVERFLOW_TRAPS (TREE_TYPE (expr
)))
2836 case POINTER_PLUS_EXPR
:
2837 /* And increments and decrements by a constant are simple. */
2838 e1
= gimple_assign_rhs2 (stmt
);
2839 if (!is_gimple_min_invariant (e1
))
2842 ee
= expand_simple_operations (e
, stop
, cache
);
2843 return fold_build2 (code
, TREE_TYPE (expr
), ee
, e1
);
2851 expand_simple_operations (tree expr
, tree stop
)
2853 hash_map
<tree
, tree
> cache
;
2854 return expand_simple_operations (expr
, stop
, cache
);
2857 /* Tries to simplify EXPR using the condition COND. Returns the simplified
2858 expression (or EXPR unchanged, if no simplification was possible). */
2861 tree_simplify_using_condition_1 (tree cond
, tree expr
)
2864 tree e
, e0
, e1
, e2
, notcond
;
2865 enum tree_code code
= TREE_CODE (expr
);
2867 if (code
== INTEGER_CST
)
2870 if (code
== TRUTH_OR_EXPR
2871 || code
== TRUTH_AND_EXPR
2872 || code
== COND_EXPR
)
2876 e0
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 0));
2877 if (TREE_OPERAND (expr
, 0) != e0
)
2880 e1
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 1));
2881 if (TREE_OPERAND (expr
, 1) != e1
)
2884 if (code
== COND_EXPR
)
2886 e2
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 2));
2887 if (TREE_OPERAND (expr
, 2) != e2
)
2895 if (code
== COND_EXPR
)
2896 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
2898 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
2904 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
2905 propagation, and vice versa. Fold does not handle this, since it is
2906 considered too expensive. */
2907 if (TREE_CODE (cond
) == EQ_EXPR
)
2909 e0
= TREE_OPERAND (cond
, 0);
2910 e1
= TREE_OPERAND (cond
, 1);
2912 /* We know that e0 == e1. Check whether we cannot simplify expr
2914 e
= simplify_replace_tree (expr
, e0
, e1
);
2915 if (integer_zerop (e
) || integer_nonzerop (e
))
2918 e
= simplify_replace_tree (expr
, e1
, e0
);
2919 if (integer_zerop (e
) || integer_nonzerop (e
))
2922 if (TREE_CODE (expr
) == EQ_EXPR
)
2924 e0
= TREE_OPERAND (expr
, 0);
2925 e1
= TREE_OPERAND (expr
, 1);
2927 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
2928 e
= simplify_replace_tree (cond
, e0
, e1
);
2929 if (integer_zerop (e
))
2931 e
= simplify_replace_tree (cond
, e1
, e0
);
2932 if (integer_zerop (e
))
2935 if (TREE_CODE (expr
) == NE_EXPR
)
2937 e0
= TREE_OPERAND (expr
, 0);
2938 e1
= TREE_OPERAND (expr
, 1);
2940 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
2941 e
= simplify_replace_tree (cond
, e0
, e1
);
2942 if (integer_zerop (e
))
2943 return boolean_true_node
;
2944 e
= simplify_replace_tree (cond
, e1
, e0
);
2945 if (integer_zerop (e
))
2946 return boolean_true_node
;
2949 /* Check whether COND ==> EXPR. */
2950 notcond
= invert_truthvalue (cond
);
2951 e
= fold_binary (TRUTH_OR_EXPR
, boolean_type_node
, notcond
, expr
);
2952 if (e
&& integer_nonzerop (e
))
2955 /* Check whether COND ==> not EXPR. */
2956 e
= fold_binary (TRUTH_AND_EXPR
, boolean_type_node
, cond
, expr
);
2957 if (e
&& integer_zerop (e
))
2963 /* Tries to simplify EXPR using the condition COND. Returns the simplified
2964 expression (or EXPR unchanged, if no simplification was possible).
2965 Wrapper around tree_simplify_using_condition_1 that ensures that chains
2966 of simple operations in definitions of ssa names in COND are expanded,
2967 so that things like casts or incrementing the value of the bound before
2968 the loop do not cause us to fail. */
2971 tree_simplify_using_condition (tree cond
, tree expr
)
2973 cond
= expand_simple_operations (cond
);
2975 return tree_simplify_using_condition_1 (cond
, expr
);
2978 /* Tries to simplify EXPR using the conditions on entry to LOOP.
2979 Returns the simplified expression (or EXPR unchanged, if no
2980 simplification was possible). */
2983 simplify_using_initial_conditions (class loop
*loop
, tree expr
)
2988 tree cond
, expanded
, backup
;
2991 if (TREE_CODE (expr
) == INTEGER_CST
)
2994 backup
= expanded
= expand_simple_operations (expr
);
2996 /* Limit walking the dominators to avoid quadraticness in
2997 the number of BBs times the number of loops in degenerate
2999 for (bb
= loop
->header
;
3000 bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && cnt
< MAX_DOMINATORS_TO_WALK
;
3001 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
3003 if (!single_pred_p (bb
))
3005 e
= single_pred_edge (bb
);
3007 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
3010 stmt
= last_stmt (e
->src
);
3011 cond
= fold_build2 (gimple_cond_code (stmt
),
3013 gimple_cond_lhs (stmt
),
3014 gimple_cond_rhs (stmt
));
3015 if (e
->flags
& EDGE_FALSE_VALUE
)
3016 cond
= invert_truthvalue (cond
);
3017 expanded
= tree_simplify_using_condition (cond
, expanded
);
3018 /* Break if EXPR is simplified to const values. */
3020 && (integer_zerop (expanded
) || integer_nonzerop (expanded
)))
3026 /* Return the original expression if no simplification is done. */
3027 return operand_equal_p (backup
, expanded
, 0) ? expr
: expanded
;
3030 /* Tries to simplify EXPR using the evolutions of the loop invariants
3031 in the superloops of LOOP. Returns the simplified expression
3032 (or EXPR unchanged, if no simplification was possible). */
3035 simplify_using_outer_evolutions (class loop
*loop
, tree expr
)
3037 enum tree_code code
= TREE_CODE (expr
);
3041 if (is_gimple_min_invariant (expr
))
3044 if (code
== TRUTH_OR_EXPR
3045 || code
== TRUTH_AND_EXPR
3046 || code
== COND_EXPR
)
3050 e0
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 0));
3051 if (TREE_OPERAND (expr
, 0) != e0
)
3054 e1
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 1));
3055 if (TREE_OPERAND (expr
, 1) != e1
)
3058 if (code
== COND_EXPR
)
3060 e2
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 2));
3061 if (TREE_OPERAND (expr
, 2) != e2
)
3069 if (code
== COND_EXPR
)
3070 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
3072 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
3078 e
= instantiate_parameters (loop
, expr
);
3079 if (is_gimple_min_invariant (e
))
3085 /* Returns true if EXIT is the only possible exit from LOOP. */
3088 loop_only_exit_p (const class loop
*loop
, basic_block
*body
, const_edge exit
)
3090 gimple_stmt_iterator bsi
;
3093 if (exit
!= single_exit (loop
))
3096 for (i
= 0; i
< loop
->num_nodes
; i
++)
3097 for (bsi
= gsi_start_bb (body
[i
]); !gsi_end_p (bsi
); gsi_next (&bsi
))
3098 if (stmt_can_terminate_bb_p (gsi_stmt (bsi
)))
3104 /* Stores description of number of iterations of LOOP derived from
3105 EXIT (an exit edge of the LOOP) in NITER. Returns true if some useful
3106 information could be derived (and fields of NITER have meaning described
3107 in comments at class tree_niter_desc declaration), false otherwise.
3108 When EVERY_ITERATION is true, only tests that are known to be executed
3109 every iteration are considered (i.e. only test that alone bounds the loop).
3110 If AT_STMT is not NULL, this function stores LOOP's condition statement in
3111 it when returning true. */
3114 number_of_iterations_exit_assumptions (class loop
*loop
, edge exit
,
3115 class tree_niter_desc
*niter
,
3116 gcond
**at_stmt
, bool every_iteration
,
3123 enum tree_code code
;
3127 /* The condition at a fake exit (if it exists) does not control its
3129 if (exit
->flags
& EDGE_FAKE
)
3132 /* Nothing to analyze if the loop is known to be infinite. */
3133 if (loop_constraint_set_p (loop
, LOOP_C_INFINITE
))
3136 safe
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit
->src
);
3138 if (every_iteration
&& !safe
)
3141 niter
->assumptions
= boolean_false_node
;
3142 niter
->control
.base
= NULL_TREE
;
3143 niter
->control
.step
= NULL_TREE
;
3144 niter
->control
.no_overflow
= false;
3145 last
= last_stmt (exit
->src
);
3148 stmt
= dyn_cast
<gcond
*> (last
);
3155 /* We want the condition for staying inside loop. */
3156 code
= gimple_cond_code (stmt
);
3157 if (exit
->flags
& EDGE_TRUE_VALUE
)
3158 code
= invert_tree_comparison (code
, false);
3170 return number_of_iterations_cltz (loop
, exit
, code
, niter
);
3176 op0
= gimple_cond_lhs (stmt
);
3177 op1
= gimple_cond_rhs (stmt
);
3178 type
= TREE_TYPE (op0
);
3180 if (TREE_CODE (type
) != INTEGER_TYPE
3181 && !POINTER_TYPE_P (type
))
3184 tree iv0_niters
= NULL_TREE
;
3185 if (!simple_iv_with_niters (loop
, loop_containing_stmt (stmt
),
3186 op0
, &iv0
, safe
? &iv0_niters
: NULL
, false))
3187 return number_of_iterations_bitcount (loop
, exit
, code
, niter
);
3188 tree iv1_niters
= NULL_TREE
;
3189 if (!simple_iv_with_niters (loop
, loop_containing_stmt (stmt
),
3190 op1
, &iv1
, safe
? &iv1_niters
: NULL
, false))
3192 /* Give up on complicated case. */
3193 if (iv0_niters
&& iv1_niters
)
3196 /* We don't want to see undefined signed overflow warnings while
3197 computing the number of iterations. */
3198 fold_defer_overflow_warnings ();
3200 iv0
.base
= expand_simple_operations (iv0
.base
);
3201 iv1
.base
= expand_simple_operations (iv1
.base
);
3202 bool body_from_caller
= true;
3205 body
= get_loop_body (loop
);
3206 body_from_caller
= false;
3208 bool only_exit_p
= loop_only_exit_p (loop
, body
, exit
);
3209 if (!body_from_caller
)
3211 if (!number_of_iterations_cond (loop
, type
, &iv0
, code
, &iv1
, niter
,
3214 fold_undefer_and_ignore_overflow_warnings ();
3218 /* Incorporate additional assumption implied by control iv. */
3219 tree iv_niters
= iv0_niters
? iv0_niters
: iv1_niters
;
3222 tree assumption
= fold_build2 (LE_EXPR
, boolean_type_node
, niter
->niter
,
3223 fold_convert (TREE_TYPE (niter
->niter
),
3226 if (!integer_nonzerop (assumption
))
3227 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
3228 niter
->assumptions
, assumption
);
3230 /* Refine upper bound if possible. */
3231 if (TREE_CODE (iv_niters
) == INTEGER_CST
3232 && niter
->max
> wi::to_widest (iv_niters
))
3233 niter
->max
= wi::to_widest (iv_niters
);
3236 /* There is no assumptions if the loop is known to be finite. */
3237 if (!integer_zerop (niter
->assumptions
)
3238 && loop_constraint_set_p (loop
, LOOP_C_FINITE
))
3239 niter
->assumptions
= boolean_true_node
;
3243 niter
->assumptions
= simplify_using_outer_evolutions (loop
,
3244 niter
->assumptions
);
3245 niter
->may_be_zero
= simplify_using_outer_evolutions (loop
,
3246 niter
->may_be_zero
);
3247 niter
->niter
= simplify_using_outer_evolutions (loop
, niter
->niter
);
3251 = simplify_using_initial_conditions (loop
,
3252 niter
->assumptions
);
3254 = simplify_using_initial_conditions (loop
,
3255 niter
->may_be_zero
);
3257 fold_undefer_and_ignore_overflow_warnings ();
3259 /* If NITER has simplified into a constant, update MAX. */
3260 if (TREE_CODE (niter
->niter
) == INTEGER_CST
)
3261 niter
->max
= wi::to_widest (niter
->niter
);
3263 return (!integer_zerop (niter
->assumptions
));
3266 /* Like number_of_iterations_exit_assumptions, but return TRUE only if
3267 the niter information holds unconditionally. */
3270 number_of_iterations_exit (class loop
*loop
, edge exit
,
3271 class tree_niter_desc
*niter
,
3272 bool warn
, bool every_iteration
,
3276 if (!number_of_iterations_exit_assumptions (loop
, exit
, niter
,
3277 &stmt
, every_iteration
, body
))
3280 if (integer_nonzerop (niter
->assumptions
))
3283 if (warn
&& dump_enabled_p ())
3284 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, stmt
,
3285 "missed loop optimization: niters analysis ends up "
3286 "with assumptions.\n");
3291 /* Try to determine the number of iterations of LOOP. If we succeed,
3292 expression giving number of iterations is returned and *EXIT is
3293 set to the edge from that the information is obtained. Otherwise
3294 chrec_dont_know is returned. */
3297 find_loop_niter (class loop
*loop
, edge
*exit
)
3300 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
);
3302 tree niter
= NULL_TREE
, aniter
;
3303 class tree_niter_desc desc
;
3306 FOR_EACH_VEC_ELT (exits
, i
, ex
)
3308 if (!number_of_iterations_exit (loop
, ex
, &desc
, false))
3311 if (integer_nonzerop (desc
.may_be_zero
))
3313 /* We exit in the first iteration through this exit.
3314 We won't find anything better. */
3315 niter
= build_int_cst (unsigned_type_node
, 0);
3320 if (!integer_zerop (desc
.may_be_zero
))
3323 aniter
= desc
.niter
;
3327 /* Nothing recorded yet. */
3333 /* Prefer constants, the lower the better. */
3334 if (TREE_CODE (aniter
) != INTEGER_CST
)
3337 if (TREE_CODE (niter
) != INTEGER_CST
)
3344 if (tree_int_cst_lt (aniter
, niter
))
3352 return niter
? niter
: chrec_dont_know
;
3355 /* Return true if loop is known to have bounded number of iterations. */
3358 finite_loop_p (class loop
*loop
)
3363 flags
= flags_from_decl_or_type (current_function_decl
);
3364 if ((flags
& (ECF_CONST
|ECF_PURE
)) && !(flags
& ECF_LOOPING_CONST_OR_PURE
))
3366 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3367 fprintf (dump_file
, "Found loop %i to be finite: it is within pure or const function.\n",
3372 if (loop
->any_upper_bound
3373 || max_loop_iterations (loop
, &nit
))
3375 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3376 fprintf (dump_file
, "Found loop %i to be finite: upper bound found.\n",
3384 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
);
3387 /* If the loop has a normal exit, we can assume it will terminate. */
3388 FOR_EACH_VEC_ELT (exits
, i
, ex
)
3389 if (!(ex
->flags
& (EDGE_EH
| EDGE_ABNORMAL
| EDGE_FAKE
)))
3392 fprintf (dump_file
, "Assume loop %i to be finite: it has an exit "
3393 "and -ffinite-loops is on.\n", loop
->num
);
3403 Analysis of a number of iterations of a loop by a brute-force evaluation.
3407 /* Bound on the number of iterations we try to evaluate. */
3409 #define MAX_ITERATIONS_TO_TRACK \
3410 ((unsigned) param_max_iterations_to_track)
3412 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
3413 result by a chain of operations such that all but exactly one of their
3414 operands are constants. */
3417 chain_of_csts_start (class loop
*loop
, tree x
)
3419 gimple
*stmt
= SSA_NAME_DEF_STMT (x
);
3421 basic_block bb
= gimple_bb (stmt
);
3422 enum tree_code code
;
3425 || !flow_bb_inside_loop_p (loop
, bb
))
3428 if (gimple_code (stmt
) == GIMPLE_PHI
)
3430 if (bb
== loop
->header
)
3431 return as_a
<gphi
*> (stmt
);
3436 if (gimple_code (stmt
) != GIMPLE_ASSIGN
3437 || gimple_assign_rhs_class (stmt
) == GIMPLE_TERNARY_RHS
)
3440 code
= gimple_assign_rhs_code (stmt
);
3441 if (gimple_references_memory_p (stmt
)
3442 || TREE_CODE_CLASS (code
) == tcc_reference
3443 || (code
== ADDR_EXPR
3444 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
3447 use
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
3448 if (use
== NULL_TREE
)
3451 return chain_of_csts_start (loop
, use
);
3454 /* Determines whether the expression X is derived from a result of a phi node
3455 in header of LOOP such that
3457 * the derivation of X consists only from operations with constants
3458 * the initial value of the phi node is constant
3459 * the value of the phi node in the next iteration can be derived from the
3460 value in the current iteration by a chain of operations with constants,
3461 or is also a constant
3463 If such phi node exists, it is returned, otherwise NULL is returned. */
3466 get_base_for (class loop
*loop
, tree x
)
3471 if (is_gimple_min_invariant (x
))
3474 phi
= chain_of_csts_start (loop
, x
);
3478 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
3479 next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
3481 if (!is_gimple_min_invariant (init
))
3484 if (TREE_CODE (next
) == SSA_NAME
3485 && chain_of_csts_start (loop
, next
) != phi
)
3491 /* Given an expression X, then
3493 * if X is NULL_TREE, we return the constant BASE.
3494 * if X is a constant, we return the constant X.
3495 * otherwise X is a SSA name, whose value in the considered loop is derived
3496 by a chain of operations with constant from a result of a phi node in
3497 the header of the loop. Then we return value of X when the value of the
3498 result of this phi node is given by the constant BASE. */
3501 get_val_for (tree x
, tree base
)
3505 gcc_checking_assert (is_gimple_min_invariant (base
));
3509 else if (is_gimple_min_invariant (x
))
3512 stmt
= SSA_NAME_DEF_STMT (x
);
3513 if (gimple_code (stmt
) == GIMPLE_PHI
)
3516 gcc_checking_assert (is_gimple_assign (stmt
));
3518 /* STMT must be either an assignment of a single SSA name or an
3519 expression involving an SSA name and a constant. Try to fold that
3520 expression using the value for the SSA name. */
3521 if (gimple_assign_ssa_name_copy_p (stmt
))
3522 return get_val_for (gimple_assign_rhs1 (stmt
), base
);
3523 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_UNARY_RHS
3524 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
3525 return fold_build1 (gimple_assign_rhs_code (stmt
),
3526 TREE_TYPE (gimple_assign_lhs (stmt
)),
3527 get_val_for (gimple_assign_rhs1 (stmt
), base
));
3528 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_BINARY_RHS
)
3530 tree rhs1
= gimple_assign_rhs1 (stmt
);
3531 tree rhs2
= gimple_assign_rhs2 (stmt
);
3532 if (TREE_CODE (rhs1
) == SSA_NAME
)
3533 rhs1
= get_val_for (rhs1
, base
);
3534 else if (TREE_CODE (rhs2
) == SSA_NAME
)
3535 rhs2
= get_val_for (rhs2
, base
);
3538 return fold_build2 (gimple_assign_rhs_code (stmt
),
3539 TREE_TYPE (gimple_assign_lhs (stmt
)), rhs1
, rhs2
);
3546 /* Tries to count the number of iterations of LOOP till it exits by EXIT
3547 by brute force -- i.e. by determining the value of the operands of the
3548 condition at EXIT in first few iterations of the loop (assuming that
3549 these values are constant) and determining the first one in that the
3550 condition is not satisfied. Returns the constant giving the number
3551 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
3554 loop_niter_by_eval (class loop
*loop
, edge exit
)
3557 tree op
[2], val
[2], next
[2], aval
[2];
3563 cond
= last_stmt (exit
->src
);
3564 if (!cond
|| gimple_code (cond
) != GIMPLE_COND
)
3565 return chrec_dont_know
;
3567 cmp
= gimple_cond_code (cond
);
3568 if (exit
->flags
& EDGE_TRUE_VALUE
)
3569 cmp
= invert_tree_comparison (cmp
, false);
3579 op
[0] = gimple_cond_lhs (cond
);
3580 op
[1] = gimple_cond_rhs (cond
);
3584 return chrec_dont_know
;
3587 for (j
= 0; j
< 2; j
++)
3589 if (is_gimple_min_invariant (op
[j
]))
3592 next
[j
] = NULL_TREE
;
3597 phi
= get_base_for (loop
, op
[j
]);
3599 return chrec_dont_know
;
3600 val
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
3601 next
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
3605 /* Don't issue signed overflow warnings. */
3606 fold_defer_overflow_warnings ();
3608 for (i
= 0; i
< MAX_ITERATIONS_TO_TRACK
; i
++)
3610 for (j
= 0; j
< 2; j
++)
3611 aval
[j
] = get_val_for (op
[j
], val
[j
]);
3613 acnd
= fold_binary (cmp
, boolean_type_node
, aval
[0], aval
[1]);
3614 if (acnd
&& integer_zerop (acnd
))
3616 fold_undefer_and_ignore_overflow_warnings ();
3617 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3619 "Proved that loop %d iterates %d times using brute force.\n",
3621 return build_int_cst (unsigned_type_node
, i
);
3624 for (j
= 0; j
< 2; j
++)
3627 val
[j
] = get_val_for (next
[j
], val
[j
]);
3628 if (!is_gimple_min_invariant (val
[j
]))
3630 fold_undefer_and_ignore_overflow_warnings ();
3631 return chrec_dont_know
;
3635 /* If the next iteration would use the same base values
3636 as the current one, there is no point looping further,
3637 all following iterations will be the same as this one. */
3638 if (val
[0] == aval
[0] && val
[1] == aval
[1])
3642 fold_undefer_and_ignore_overflow_warnings ();
3644 return chrec_dont_know
;
3647 /* Finds the exit of the LOOP by that the loop exits after a constant
3648 number of iterations and stores the exit edge to *EXIT. The constant
3649 giving the number of iterations of LOOP is returned. The number of
3650 iterations is determined using loop_niter_by_eval (i.e. by brute force
3651 evaluation). If we are unable to find the exit for that loop_niter_by_eval
3652 determines the number of iterations, chrec_dont_know is returned. */
3655 find_loop_niter_by_eval (class loop
*loop
, edge
*exit
)
3658 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
);
3660 tree niter
= NULL_TREE
, aniter
;
3664 /* Loops with multiple exits are expensive to handle and less important. */
3665 if (!flag_expensive_optimizations
3666 && exits
.length () > 1)
3667 return chrec_dont_know
;
3669 FOR_EACH_VEC_ELT (exits
, i
, ex
)
3671 if (!just_once_each_iteration_p (loop
, ex
->src
))
3674 aniter
= loop_niter_by_eval (loop
, ex
);
3675 if (chrec_contains_undetermined (aniter
))
3679 && !tree_int_cst_lt (aniter
, niter
))
3686 return niter
? niter
: chrec_dont_know
;
3691 Analysis of upper bounds on number of iterations of a loop.
3695 static widest_int
derive_constant_upper_bound_ops (tree
, tree
,
3696 enum tree_code
, tree
);
3698 /* Returns a constant upper bound on the value of the right-hand side of
3699 an assignment statement STMT. */
3702 derive_constant_upper_bound_assign (gimple
*stmt
)
3704 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3705 tree op0
= gimple_assign_rhs1 (stmt
);
3706 tree op1
= gimple_assign_rhs2 (stmt
);
3708 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt
)),
3712 /* Returns a constant upper bound on the value of expression VAL. VAL
3713 is considered to be unsigned. If its type is signed, its value must
3717 derive_constant_upper_bound (tree val
)
3719 enum tree_code code
;
3722 extract_ops_from_tree (val
, &code
, &op0
, &op1
, &op2
);
3723 return derive_constant_upper_bound_ops (TREE_TYPE (val
), op0
, code
, op1
);
3726 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
3727 whose type is TYPE. The expression is considered to be unsigned. If
3728 its type is signed, its value must be nonnegative. */
3731 derive_constant_upper_bound_ops (tree type
, tree op0
,
3732 enum tree_code code
, tree op1
)
3735 widest_int bnd
, max
, cst
;
3738 if (INTEGRAL_TYPE_P (type
))
3739 maxt
= TYPE_MAX_VALUE (type
);
3741 maxt
= upper_bound_in_type (type
, type
);
3743 max
= wi::to_widest (maxt
);
3748 return wi::to_widest (op0
);
3751 subtype
= TREE_TYPE (op0
);
3752 if (!TYPE_UNSIGNED (subtype
)
3753 /* If TYPE is also signed, the fact that VAL is nonnegative implies
3754 that OP0 is nonnegative. */
3755 && TYPE_UNSIGNED (type
)
3756 && !tree_expr_nonnegative_p (op0
))
3758 /* If we cannot prove that the casted expression is nonnegative,
3759 we cannot establish more useful upper bound than the precision
3760 of the type gives us. */
3764 /* We now know that op0 is an nonnegative value. Try deriving an upper
3766 bnd
= derive_constant_upper_bound (op0
);
3768 /* If the bound does not fit in TYPE, max. value of TYPE could be
3770 if (wi::ltu_p (max
, bnd
))
3776 case POINTER_PLUS_EXPR
:
3778 if (TREE_CODE (op1
) != INTEGER_CST
3779 || !tree_expr_nonnegative_p (op0
))
3782 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
3783 choose the most logical way how to treat this constant regardless
3784 of the signedness of the type. */
3785 cst
= wi::sext (wi::to_widest (op1
), TYPE_PRECISION (type
));
3786 if (code
!= MINUS_EXPR
)
3789 bnd
= derive_constant_upper_bound (op0
);
3791 if (wi::neg_p (cst
))
3794 /* Avoid CST == 0x80000... */
3795 if (wi::neg_p (cst
))
3798 /* OP0 + CST. We need to check that
3799 BND <= MAX (type) - CST. */
3801 widest_int mmax
= max
- cst
;
3802 if (wi::leu_p (bnd
, mmax
))
3809 /* OP0 - CST, where CST >= 0.
3811 If TYPE is signed, we have already verified that OP0 >= 0, and we
3812 know that the result is nonnegative. This implies that
3815 If TYPE is unsigned, we must additionally know that OP0 >= CST,
3816 otherwise the operation underflows.
3819 /* This should only happen if the type is unsigned; however, for
3820 buggy programs that use overflowing signed arithmetics even with
3821 -fno-wrapv, this condition may also be true for signed values. */
3822 if (wi::ltu_p (bnd
, cst
))
3825 if (TYPE_UNSIGNED (type
))
3827 tree tem
= fold_binary (GE_EXPR
, boolean_type_node
, op0
,
3828 wide_int_to_tree (type
, cst
));
3829 if (!tem
|| integer_nonzerop (tem
))
3838 case FLOOR_DIV_EXPR
:
3839 case EXACT_DIV_EXPR
:
3840 if (TREE_CODE (op1
) != INTEGER_CST
3841 || tree_int_cst_sign_bit (op1
))
3844 bnd
= derive_constant_upper_bound (op0
);
3845 return wi::udiv_floor (bnd
, wi::to_widest (op1
));
3848 if (TREE_CODE (op1
) != INTEGER_CST
3849 || tree_int_cst_sign_bit (op1
))
3851 return wi::to_widest (op1
);
3854 stmt
= SSA_NAME_DEF_STMT (op0
);
3855 if (gimple_code (stmt
) != GIMPLE_ASSIGN
3856 || gimple_assign_lhs (stmt
) != op0
)
3858 return derive_constant_upper_bound_assign (stmt
);
3865 /* Emit a -Waggressive-loop-optimizations warning if needed. */
3868 do_warn_aggressive_loop_optimizations (class loop
*loop
,
3869 widest_int i_bound
, gimple
*stmt
)
3871 /* Don't warn if the loop doesn't have known constant bound. */
3872 if (!loop
->nb_iterations
3873 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
3874 || !warn_aggressive_loop_optimizations
3875 /* To avoid warning multiple times for the same loop,
3876 only start warning when we preserve loops. */
3877 || (cfun
->curr_properties
& PROP_loops
) == 0
3878 /* Only warn once per loop. */
3879 || loop
->warned_aggressive_loop_optimizations
3880 /* Only warn if undefined behavior gives us lower estimate than the
3881 known constant bound. */
3882 || wi::cmpu (i_bound
, wi::to_widest (loop
->nb_iterations
)) >= 0
3883 /* And undefined behavior happens unconditionally. */
3884 || !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (stmt
)))
3887 edge e
= single_exit (loop
);
3891 gimple
*estmt
= last_stmt (e
->src
);
3892 char buf
[WIDE_INT_PRINT_BUFFER_SIZE
];
3893 print_dec (i_bound
, buf
, TYPE_UNSIGNED (TREE_TYPE (loop
->nb_iterations
))
3894 ? UNSIGNED
: SIGNED
);
3895 auto_diagnostic_group d
;
3896 if (warning_at (gimple_location (stmt
), OPT_Waggressive_loop_optimizations
,
3897 "iteration %s invokes undefined behavior", buf
))
3898 inform (gimple_location (estmt
), "within this loop");
3899 loop
->warned_aggressive_loop_optimizations
= true;
3902 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
3903 is true if the loop is exited immediately after STMT, and this exit
3904 is taken at last when the STMT is executed BOUND + 1 times.
3905 REALISTIC is true if BOUND is expected to be close to the real number
3906 of iterations. UPPER is true if we are sure the loop iterates at most
3907 BOUND times. I_BOUND is a widest_int upper estimate on BOUND. */
3910 record_estimate (class loop
*loop
, tree bound
, const widest_int
&i_bound
,
3911 gimple
*at_stmt
, bool is_exit
, bool realistic
, bool upper
)
3915 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3917 fprintf (dump_file
, "Statement %s", is_exit
? "(exit)" : "");
3918 print_gimple_stmt (dump_file
, at_stmt
, 0, TDF_SLIM
);
3919 fprintf (dump_file
, " is %sexecuted at most ",
3920 upper
? "" : "probably ");
3921 print_generic_expr (dump_file
, bound
, TDF_SLIM
);
3922 fprintf (dump_file
, " (bounded by ");
3923 print_decu (i_bound
, dump_file
);
3924 fprintf (dump_file
, ") + 1 times in loop %d.\n", loop
->num
);
3927 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
3928 real number of iterations. */
3929 if (TREE_CODE (bound
) != INTEGER_CST
)
3932 gcc_checking_assert (i_bound
== wi::to_widest (bound
));
3934 /* If we have a guaranteed upper bound, record it in the appropriate
3935 list, unless this is an !is_exit bound (i.e. undefined behavior in
3936 at_stmt) in a loop with known constant number of iterations. */
3939 || loop
->nb_iterations
== NULL_TREE
3940 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
))
3942 class nb_iter_bound
*elt
= ggc_alloc
<nb_iter_bound
> ();
3944 elt
->bound
= i_bound
;
3945 elt
->stmt
= at_stmt
;
3946 elt
->is_exit
= is_exit
;
3947 elt
->next
= loop
->bounds
;
3951 /* If statement is executed on every path to the loop latch, we can directly
3952 infer the upper bound on the # of iterations of the loop. */
3953 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (at_stmt
)))
3956 /* Update the number of iteration estimates according to the bound.
3957 If at_stmt is an exit then the loop latch is executed at most BOUND times,
3958 otherwise it can be executed BOUND + 1 times. We will lower the estimate
3959 later if such statement must be executed on last iteration */
3964 widest_int new_i_bound
= i_bound
+ delta
;
3966 /* If an overflow occurred, ignore the result. */
3967 if (wi::ltu_p (new_i_bound
, delta
))
3970 if (upper
&& !is_exit
)
3971 do_warn_aggressive_loop_optimizations (loop
, new_i_bound
, at_stmt
);
3972 record_niter_bound (loop
, new_i_bound
, realistic
, upper
);
3975 /* Records the control iv analyzed in NITER for LOOP if the iv is valid
3976 and doesn't overflow. */
3979 record_control_iv (class loop
*loop
, class tree_niter_desc
*niter
)
3981 struct control_iv
*iv
;
3983 if (!niter
->control
.base
|| !niter
->control
.step
)
3986 if (!integer_onep (niter
->assumptions
) || !niter
->control
.no_overflow
)
3989 iv
= ggc_alloc
<control_iv
> ();
3990 iv
->base
= niter
->control
.base
;
3991 iv
->step
= niter
->control
.step
;
3992 iv
->next
= loop
->control_ivs
;
3993 loop
->control_ivs
= iv
;
3998 /* This function returns TRUE if below conditions are satisfied:
3999 1) VAR is SSA variable.
4000 2) VAR is an IV:{base, step} in its defining loop.
4001 3) IV doesn't overflow.
4002 4) Both base and step are integer constants.
4003 5) Base is the MIN/MAX value depends on IS_MIN.
4004 Store value of base to INIT correspondingly. */
4007 get_cst_init_from_scev (tree var
, wide_int
*init
, bool is_min
)
4009 if (TREE_CODE (var
) != SSA_NAME
)
4012 gimple
*def_stmt
= SSA_NAME_DEF_STMT (var
);
4013 class loop
*loop
= loop_containing_stmt (def_stmt
);
4019 if (!simple_iv (loop
, loop
, var
, &iv
, false))
4022 if (!iv
.no_overflow
)
4025 if (TREE_CODE (iv
.base
) != INTEGER_CST
|| TREE_CODE (iv
.step
) != INTEGER_CST
)
4028 if (is_min
== tree_int_cst_sign_bit (iv
.step
))
4031 *init
= wi::to_wide (iv
.base
);
4035 /* Record the estimate on number of iterations of LOOP based on the fact that
4036 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
4037 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
4038 estimated number of iterations is expected to be close to the real one.
4039 UPPER is true if we are sure the induction variable does not wrap. */
4042 record_nonwrapping_iv (class loop
*loop
, tree base
, tree step
, gimple
*stmt
,
4043 tree low
, tree high
, bool realistic
, bool upper
)
4045 tree niter_bound
, extreme
, delta
;
4046 tree type
= TREE_TYPE (base
), unsigned_type
;
4047 tree orig_base
= base
;
4049 if (TREE_CODE (step
) != INTEGER_CST
|| integer_zerop (step
))
4052 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4054 fprintf (dump_file
, "Induction variable (");
4055 print_generic_expr (dump_file
, TREE_TYPE (base
), TDF_SLIM
);
4056 fprintf (dump_file
, ") ");
4057 print_generic_expr (dump_file
, base
, TDF_SLIM
);
4058 fprintf (dump_file
, " + ");
4059 print_generic_expr (dump_file
, step
, TDF_SLIM
);
4060 fprintf (dump_file
, " * iteration does not wrap in statement ");
4061 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
4062 fprintf (dump_file
, " in loop %d.\n", loop
->num
);
4065 unsigned_type
= unsigned_type_for (type
);
4066 base
= fold_convert (unsigned_type
, base
);
4067 step
= fold_convert (unsigned_type
, step
);
4069 if (tree_int_cst_sign_bit (step
))
4072 Value_Range
base_range (TREE_TYPE (orig_base
));
4073 if (get_range_query (cfun
)->range_of_expr (base_range
, orig_base
)
4074 && !base_range
.undefined_p ())
4075 max
= base_range
.upper_bound ();
4076 extreme
= fold_convert (unsigned_type
, low
);
4077 if (TREE_CODE (orig_base
) == SSA_NAME
4078 && TREE_CODE (high
) == INTEGER_CST
4079 && INTEGRAL_TYPE_P (TREE_TYPE (orig_base
))
4080 && (base_range
.kind () == VR_RANGE
4081 || get_cst_init_from_scev (orig_base
, &max
, false))
4082 && wi::gts_p (wi::to_wide (high
), max
))
4083 base
= wide_int_to_tree (unsigned_type
, max
);
4084 else if (TREE_CODE (base
) != INTEGER_CST
4085 && dominated_by_p (CDI_DOMINATORS
,
4086 loop
->latch
, gimple_bb (stmt
)))
4087 base
= fold_convert (unsigned_type
, high
);
4088 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
4089 step
= fold_build1 (NEGATE_EXPR
, unsigned_type
, step
);
4094 Value_Range
base_range (TREE_TYPE (orig_base
));
4095 if (get_range_query (cfun
)->range_of_expr (base_range
, orig_base
)
4096 && !base_range
.undefined_p ())
4097 min
= base_range
.lower_bound ();
4098 extreme
= fold_convert (unsigned_type
, high
);
4099 if (TREE_CODE (orig_base
) == SSA_NAME
4100 && TREE_CODE (low
) == INTEGER_CST
4101 && INTEGRAL_TYPE_P (TREE_TYPE (orig_base
))
4102 && (base_range
.kind () == VR_RANGE
4103 || get_cst_init_from_scev (orig_base
, &min
, true))
4104 && wi::gts_p (min
, wi::to_wide (low
)))
4105 base
= wide_int_to_tree (unsigned_type
, min
);
4106 else if (TREE_CODE (base
) != INTEGER_CST
4107 && dominated_by_p (CDI_DOMINATORS
,
4108 loop
->latch
, gimple_bb (stmt
)))
4109 base
= fold_convert (unsigned_type
, low
);
4110 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
4113 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
4114 would get out of the range. */
4115 niter_bound
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step
);
4116 widest_int max
= derive_constant_upper_bound (niter_bound
);
4117 record_estimate (loop
, niter_bound
, max
, stmt
, false, realistic
, upper
);
4120 /* Determine information about number of iterations a LOOP from the index
4121 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
4122 guaranteed to be executed in every iteration of LOOP. Callback for
4132 idx_infer_loop_bounds (tree base
, tree
*idx
, void *dta
)
4134 struct ilb_data
*data
= (struct ilb_data
*) dta
;
4135 tree ev
, init
, step
;
4136 tree low
, high
, type
, next
;
4137 bool sign
, upper
= true, has_flexible_size
= false;
4138 class loop
*loop
= data
->loop
;
4140 if (TREE_CODE (base
) != ARRAY_REF
)
4143 /* For arrays that might have flexible sizes, it is not guaranteed that they
4144 do not really extend over their declared size. */
4145 if (array_ref_flexible_size_p (base
))
4147 has_flexible_size
= true;
4151 class loop
*dloop
= loop_containing_stmt (data
->stmt
);
4155 ev
= analyze_scalar_evolution (dloop
, *idx
);
4156 ev
= instantiate_parameters (loop
, ev
);
4157 init
= initial_condition (ev
);
4158 step
= evolution_part_in_loop_num (ev
, loop
->num
);
4162 || TREE_CODE (step
) != INTEGER_CST
4163 || integer_zerop (step
)
4164 || tree_contains_chrecs (init
, NULL
)
4165 || chrec_contains_symbols_defined_in_loop (init
, loop
->num
))
4168 low
= array_ref_low_bound (base
);
4169 high
= array_ref_up_bound (base
);
4171 /* The case of nonconstant bounds could be handled, but it would be
4173 if (TREE_CODE (low
) != INTEGER_CST
4175 || TREE_CODE (high
) != INTEGER_CST
)
4177 sign
= tree_int_cst_sign_bit (step
);
4178 type
= TREE_TYPE (step
);
4180 /* The array that might have flexible size most likely extends
4181 beyond its bounds. */
4182 if (has_flexible_size
4183 && operand_equal_p (low
, high
, 0))
4186 /* In case the relevant bound of the array does not fit in type, or
4187 it does, but bound + step (in type) still belongs into the range of the
4188 array, the index may wrap and still stay within the range of the array
4189 (consider e.g. if the array is indexed by the full range of
4192 To make things simpler, we require both bounds to fit into type, although
4193 there are cases where this would not be strictly necessary. */
4194 if (!int_fits_type_p (high
, type
)
4195 || !int_fits_type_p (low
, type
))
4197 low
= fold_convert (type
, low
);
4198 high
= fold_convert (type
, high
);
4201 next
= fold_binary (PLUS_EXPR
, type
, low
, step
);
4203 next
= fold_binary (PLUS_EXPR
, type
, high
, step
);
4205 if (tree_int_cst_compare (low
, next
) <= 0
4206 && tree_int_cst_compare (next
, high
) <= 0)
4209 /* If access is not executed on every iteration, we must ensure that overlow
4210 may not make the access valid later. */
4211 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (data
->stmt
))
4212 && scev_probably_wraps_p (NULL_TREE
,
4213 initial_condition_in_loop_num (ev
, loop
->num
),
4214 step
, data
->stmt
, loop
, true))
4217 record_nonwrapping_iv (loop
, init
, step
, data
->stmt
, low
, high
, false, upper
);
4221 /* Determine information about number of iterations a LOOP from the bounds
4222 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
4223 STMT is guaranteed to be executed in every iteration of LOOP.*/
4226 infer_loop_bounds_from_ref (class loop
*loop
, gimple
*stmt
, tree ref
)
4228 struct ilb_data data
;
4232 for_each_index (&ref
, idx_infer_loop_bounds
, &data
);
4235 /* Determine information about number of iterations of a LOOP from the way
4236 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
4237 executed in every iteration of LOOP. */
4240 infer_loop_bounds_from_array (class loop
*loop
, gimple
*stmt
)
4242 if (is_gimple_assign (stmt
))
4244 tree op0
= gimple_assign_lhs (stmt
);
4245 tree op1
= gimple_assign_rhs1 (stmt
);
4247 /* For each memory access, analyze its access function
4248 and record a bound on the loop iteration domain. */
4249 if (REFERENCE_CLASS_P (op0
))
4250 infer_loop_bounds_from_ref (loop
, stmt
, op0
);
4252 if (REFERENCE_CLASS_P (op1
))
4253 infer_loop_bounds_from_ref (loop
, stmt
, op1
);
4255 else if (is_gimple_call (stmt
))
4258 unsigned i
, n
= gimple_call_num_args (stmt
);
4260 lhs
= gimple_call_lhs (stmt
);
4261 if (lhs
&& REFERENCE_CLASS_P (lhs
))
4262 infer_loop_bounds_from_ref (loop
, stmt
, lhs
);
4264 for (i
= 0; i
< n
; i
++)
4266 arg
= gimple_call_arg (stmt
, i
);
4267 if (REFERENCE_CLASS_P (arg
))
4268 infer_loop_bounds_from_ref (loop
, stmt
, arg
);
4273 /* Determine information about number of iterations of a LOOP from the fact
4274 that pointer arithmetics in STMT does not overflow. */
4277 infer_loop_bounds_from_pointer_arith (class loop
*loop
, gimple
*stmt
)
4279 tree def
, base
, step
, scev
, type
, low
, high
;
4282 if (!is_gimple_assign (stmt
)
4283 || gimple_assign_rhs_code (stmt
) != POINTER_PLUS_EXPR
)
4286 def
= gimple_assign_lhs (stmt
);
4287 if (TREE_CODE (def
) != SSA_NAME
)
4290 type
= TREE_TYPE (def
);
4291 if (!nowrap_type_p (type
))
4294 ptr
= gimple_assign_rhs1 (stmt
);
4295 if (!expr_invariant_in_loop_p (loop
, ptr
))
4298 var
= gimple_assign_rhs2 (stmt
);
4299 if (TYPE_PRECISION (type
) != TYPE_PRECISION (TREE_TYPE (var
)))
4302 class loop
*uloop
= loop_containing_stmt (stmt
);
4303 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (uloop
, def
));
4304 if (chrec_contains_undetermined (scev
))
4307 base
= initial_condition_in_loop_num (scev
, loop
->num
);
4308 step
= evolution_part_in_loop_num (scev
, loop
->num
);
4311 || TREE_CODE (step
) != INTEGER_CST
4312 || tree_contains_chrecs (base
, NULL
)
4313 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
4316 low
= lower_bound_in_type (type
, type
);
4317 high
= upper_bound_in_type (type
, type
);
4319 /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
4320 produce a NULL pointer. The contrary would mean NULL points to an object,
4321 while NULL is supposed to compare unequal with the address of all objects.
4322 Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
4323 NULL pointer since that would mean wrapping, which we assume here not to
4324 happen. So, we can exclude NULL from the valid range of pointer
4326 if (flag_delete_null_pointer_checks
&& int_cst_value (low
) == 0)
4327 low
= build_int_cstu (TREE_TYPE (low
), TYPE_ALIGN_UNIT (TREE_TYPE (type
)));
4329 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
4332 /* Determine information about number of iterations of a LOOP from the fact
4333 that signed arithmetics in STMT does not overflow. */
4336 infer_loop_bounds_from_signedness (class loop
*loop
, gimple
*stmt
)
4338 tree def
, base
, step
, scev
, type
, low
, high
;
4340 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
4343 def
= gimple_assign_lhs (stmt
);
4345 if (TREE_CODE (def
) != SSA_NAME
)
4348 type
= TREE_TYPE (def
);
4349 if (!INTEGRAL_TYPE_P (type
)
4350 || !TYPE_OVERFLOW_UNDEFINED (type
))
4353 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
4354 if (chrec_contains_undetermined (scev
))
4357 base
= initial_condition_in_loop_num (scev
, loop
->num
);
4358 step
= evolution_part_in_loop_num (scev
, loop
->num
);
4361 || TREE_CODE (step
) != INTEGER_CST
4362 || tree_contains_chrecs (base
, NULL
)
4363 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
4366 low
= lower_bound_in_type (type
, type
);
4367 high
= upper_bound_in_type (type
, type
);
4368 Value_Range
r (TREE_TYPE (def
));
4369 get_range_query (cfun
)->range_of_expr (r
, def
);
4370 if (r
.kind () == VR_RANGE
)
4372 low
= wide_int_to_tree (type
, r
.lower_bound ());
4373 high
= wide_int_to_tree (type
, r
.upper_bound ());
4376 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
4379 /* The following analyzers are extracting informations on the bounds
4380 of LOOP from the following undefined behaviors:
4382 - data references should not access elements over the statically
4385 - signed variables should not overflow when flag_wrapv is not set.
4389 infer_loop_bounds_from_undefined (class loop
*loop
, basic_block
*bbs
)
4392 gimple_stmt_iterator bsi
;
4396 for (i
= 0; i
< loop
->num_nodes
; i
++)
4400 /* If BB is not executed in each iteration of the loop, we cannot
4401 use the operations in it to infer reliable upper bound on the
4402 # of iterations of the loop. However, we can use it as a guess.
4403 Reliable guesses come only from array bounds. */
4404 reliable
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
);
4406 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
4408 gimple
*stmt
= gsi_stmt (bsi
);
4410 infer_loop_bounds_from_array (loop
, stmt
);
4414 infer_loop_bounds_from_signedness (loop
, stmt
);
4415 infer_loop_bounds_from_pointer_arith (loop
, stmt
);
4422 /* Compare wide ints, callback for qsort. */
4425 wide_int_cmp (const void *p1
, const void *p2
)
4427 const widest_int
*d1
= (const widest_int
*) p1
;
4428 const widest_int
*d2
= (const widest_int
*) p2
;
4429 return wi::cmpu (*d1
, *d2
);
4432 /* Return index of BOUND in BOUNDS array sorted in increasing order.
4433 Lookup by binary search. */
4436 bound_index (const vec
<widest_int
> &bounds
, const widest_int
&bound
)
4438 unsigned int end
= bounds
.length ();
4439 unsigned int begin
= 0;
4441 /* Find a matching index by means of a binary search. */
4442 while (begin
!= end
)
4444 unsigned int middle
= (begin
+ end
) / 2;
4445 widest_int index
= bounds
[middle
];
4449 else if (wi::ltu_p (index
, bound
))
4457 /* We recorded loop bounds only for statements dominating loop latch (and thus
4458 executed each loop iteration). If there are any bounds on statements not
4459 dominating the loop latch we can improve the estimate by walking the loop
4460 body and seeing if every path from loop header to loop latch contains
4461 some bounded statement. */
4464 discover_iteration_bound_by_body_walk (class loop
*loop
)
4466 class nb_iter_bound
*elt
;
4467 auto_vec
<widest_int
> bounds
;
4468 vec
<vec
<basic_block
> > queues
= vNULL
;
4469 vec
<basic_block
> queue
= vNULL
;
4470 ptrdiff_t queue_index
;
4471 ptrdiff_t latch_index
= 0;
4473 /* Discover what bounds may interest us. */
4474 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
4476 widest_int bound
= elt
->bound
;
4478 /* Exit terminates loop at given iteration, while non-exits produce undefined
4479 effect on the next iteration. */
4483 /* If an overflow occurred, ignore the result. */
4488 if (!loop
->any_upper_bound
4489 || wi::ltu_p (bound
, loop
->nb_iterations_upper_bound
))
4490 bounds
.safe_push (bound
);
4493 /* Exit early if there is nothing to do. */
4494 if (!bounds
.exists ())
4497 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4498 fprintf (dump_file
, " Trying to walk loop body to reduce the bound.\n");
4500 /* Sort the bounds in decreasing order. */
4501 bounds
.qsort (wide_int_cmp
);
4503 /* For every basic block record the lowest bound that is guaranteed to
4504 terminate the loop. */
4506 hash_map
<basic_block
, ptrdiff_t> bb_bounds
;
4507 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
4509 widest_int bound
= elt
->bound
;
4513 /* If an overflow occurred, ignore the result. */
4518 if (!loop
->any_upper_bound
4519 || wi::ltu_p (bound
, loop
->nb_iterations_upper_bound
))
4521 ptrdiff_t index
= bound_index (bounds
, bound
);
4522 ptrdiff_t *entry
= bb_bounds
.get (gimple_bb (elt
->stmt
));
4524 bb_bounds
.put (gimple_bb (elt
->stmt
), index
);
4525 else if ((ptrdiff_t)*entry
> index
)
4530 hash_map
<basic_block
, ptrdiff_t> block_priority
;
4532 /* Perform shortest path discovery loop->header ... loop->latch.
4534 The "distance" is given by the smallest loop bound of basic block
4535 present in the path and we look for path with largest smallest bound
4538 To avoid the need for fibonacci heap on double ints we simply compress
4539 double ints into indexes to BOUNDS array and then represent the queue
4540 as arrays of queues for every index.
4541 Index of BOUNDS.length() means that the execution of given BB has
4542 no bounds determined.
4544 VISITED is a pointer map translating basic block into smallest index
4545 it was inserted into the priority queue with. */
4548 /* Start walk in loop header with index set to infinite bound. */
4549 queue_index
= bounds
.length ();
4550 queues
.safe_grow_cleared (queue_index
+ 1, true);
4551 queue
.safe_push (loop
->header
);
4552 queues
[queue_index
] = queue
;
4553 block_priority
.put (loop
->header
, queue_index
);
4555 for (; queue_index
>= 0; queue_index
--)
4557 if (latch_index
< queue_index
)
4559 while (queues
[queue_index
].length ())
4562 ptrdiff_t bound_index
= queue_index
;
4566 queue
= queues
[queue_index
];
4569 /* OK, we later inserted the BB with lower priority, skip it. */
4570 if (*block_priority
.get (bb
) > queue_index
)
4573 /* See if we can improve the bound. */
4574 ptrdiff_t *entry
= bb_bounds
.get (bb
);
4575 if (entry
&& *entry
< bound_index
)
4576 bound_index
= *entry
;
4578 /* Insert succesors into the queue, watch for latch edge
4579 and record greatest index we saw. */
4580 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4582 bool insert
= false;
4584 if (loop_exit_edge_p (loop
, e
))
4587 if (e
== loop_latch_edge (loop
)
4588 && latch_index
< bound_index
)
4589 latch_index
= bound_index
;
4590 else if (!(entry
= block_priority
.get (e
->dest
)))
4593 block_priority
.put (e
->dest
, bound_index
);
4595 else if (*entry
< bound_index
)
4598 *entry
= bound_index
;
4602 queues
[bound_index
].safe_push (e
->dest
);
4606 queues
[queue_index
].release ();
4609 gcc_assert (latch_index
>= 0);
4610 if ((unsigned)latch_index
< bounds
.length ())
4612 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4614 fprintf (dump_file
, "Found better loop bound ");
4615 print_decu (bounds
[latch_index
], dump_file
);
4616 fprintf (dump_file
, "\n");
4618 record_niter_bound (loop
, bounds
[latch_index
], false, true);
4624 /* See if every path cross the loop goes through a statement that is known
4625 to not execute at the last iteration. In that case we can decrese iteration
4629 maybe_lower_iteration_bound (class loop
*loop
)
4631 hash_set
<gimple
*> *not_executed_last_iteration
= NULL
;
4632 class nb_iter_bound
*elt
;
4633 bool found_exit
= false;
4634 auto_vec
<basic_block
> queue
;
4637 /* Collect all statements with interesting (i.e. lower than
4638 nb_iterations_upper_bound) bound on them.
4640 TODO: Due to the way record_estimate choose estimates to store, the bounds
4641 will be always nb_iterations_upper_bound-1. We can change this to record
4642 also statements not dominating the loop latch and update the walk bellow
4643 to the shortest path algorithm. */
4644 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
4647 && wi::ltu_p (elt
->bound
, loop
->nb_iterations_upper_bound
))
4649 if (!not_executed_last_iteration
)
4650 not_executed_last_iteration
= new hash_set
<gimple
*>;
4651 not_executed_last_iteration
->add (elt
->stmt
);
4654 if (!not_executed_last_iteration
)
4657 /* Start DFS walk in the loop header and see if we can reach the
4658 loop latch or any of the exits (including statements with side
4659 effects that may terminate the loop otherwise) without visiting
4660 any of the statements known to have undefined effect on the last
4662 queue
.safe_push (loop
->header
);
4663 visited
= BITMAP_ALLOC (NULL
);
4664 bitmap_set_bit (visited
, loop
->header
->index
);
4669 basic_block bb
= queue
.pop ();
4670 gimple_stmt_iterator gsi
;
4671 bool stmt_found
= false;
4673 /* Loop for possible exits and statements bounding the execution. */
4674 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
4676 gimple
*stmt
= gsi_stmt (gsi
);
4677 if (not_executed_last_iteration
->contains (stmt
))
4682 if (gimple_has_side_effects (stmt
))
4691 /* If no bounding statement is found, continue the walk. */
4697 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4699 if (loop_exit_edge_p (loop
, e
)
4700 || e
== loop_latch_edge (loop
))
4705 if (bitmap_set_bit (visited
, e
->dest
->index
))
4706 queue
.safe_push (e
->dest
);
4710 while (queue
.length () && !found_exit
);
4712 /* If every path through the loop reach bounding statement before exit,
4713 then we know the last iteration of the loop will have undefined effect
4714 and we can decrease number of iterations. */
4718 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4719 fprintf (dump_file
, "Reducing loop iteration estimate by 1; "
4720 "undefined statement must be executed at the last iteration.\n");
4721 record_niter_bound (loop
, loop
->nb_iterations_upper_bound
- 1,
4725 BITMAP_FREE (visited
);
4726 delete not_executed_last_iteration
;
4729 /* Get expected upper bound for number of loop iterations for
4730 BUILT_IN_EXPECT_WITH_PROBABILITY for a condition COND. */
4733 get_upper_bound_based_on_builtin_expr_with_prob (gcond
*cond
)
4738 tree lhs
= gimple_cond_lhs (cond
);
4739 if (TREE_CODE (lhs
) != SSA_NAME
)
4742 gimple
*stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (cond
));
4743 gcall
*def
= dyn_cast
<gcall
*> (stmt
);
4747 tree decl
= gimple_call_fndecl (def
);
4749 || !fndecl_built_in_p (decl
, BUILT_IN_EXPECT_WITH_PROBABILITY
)
4750 || gimple_call_num_args (stmt
) != 3)
4753 tree c
= gimple_call_arg (def
, 1);
4754 tree condt
= TREE_TYPE (lhs
);
4755 tree res
= fold_build2 (gimple_cond_code (cond
),
4757 gimple_cond_rhs (cond
));
4758 if (TREE_CODE (res
) != INTEGER_CST
)
4762 tree prob
= gimple_call_arg (def
, 2);
4763 tree t
= TREE_TYPE (prob
);
4765 = build_real_from_int_cst (t
,
4767 if (integer_zerop (res
))
4768 prob
= fold_build2 (MINUS_EXPR
, t
, one
, prob
);
4769 tree r
= fold_build2 (RDIV_EXPR
, t
, one
, prob
);
4770 if (TREE_CODE (r
) != REAL_CST
)
4774 = real_to_integer (TREE_REAL_CST_PTR (r
));
4775 return build_int_cst (condt
, probi
);
4778 /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
4779 is true also use estimates derived from undefined behavior. */
4782 estimate_numbers_of_iterations (class loop
*loop
)
4786 class tree_niter_desc niter_desc
;
4791 /* Give up if we already have tried to compute an estimation. */
4792 if (loop
->estimate_state
!= EST_NOT_COMPUTED
)
4795 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4796 fprintf (dump_file
, "Estimating # of iterations of loop %d\n", loop
->num
);
4798 loop
->estimate_state
= EST_AVAILABLE
;
4800 /* If we have a measured profile, use it to estimate the number of
4801 iterations. Normally this is recorded by branch_prob right after
4802 reading the profile. In case we however found a new loop, record the
4805 Explicitly check for profile status so we do not report
4806 wrong prediction hitrates for guessed loop iterations heuristics.
4807 Do not recompute already recorded bounds - we ought to be better on
4808 updating iteration bounds than updating profile in general and thus
4809 recomputing iteration bounds later in the compilation process will just
4810 introduce random roundoff errors. */
4811 if (!loop
->any_estimate
4812 && loop
->header
->count
.reliable_p ())
4814 gcov_type nit
= expected_loop_iterations_unbounded (loop
);
4815 bound
= gcov_type_to_wide_int (nit
);
4816 record_niter_bound (loop
, bound
, true, false);
4819 /* Ensure that loop->nb_iterations is computed if possible. If it turns out
4820 to be constant, we avoid undefined behavior implied bounds and instead
4821 diagnose those loops with -Waggressive-loop-optimizations. */
4822 number_of_latch_executions (loop
);
4824 basic_block
*body
= get_loop_body (loop
);
4825 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
, body
);
4826 likely_exit
= single_likely_exit (loop
, exits
);
4827 FOR_EACH_VEC_ELT (exits
, i
, ex
)
4829 if (ex
== likely_exit
)
4831 gimple
*stmt
= last_stmt (ex
->src
);
4834 gcond
*cond
= dyn_cast
<gcond
*> (stmt
);
4836 = get_upper_bound_based_on_builtin_expr_with_prob (cond
);
4837 if (niter_bound
!= NULL_TREE
)
4839 widest_int max
= derive_constant_upper_bound (niter_bound
);
4840 record_estimate (loop
, niter_bound
, max
, cond
,
4846 if (!number_of_iterations_exit (loop
, ex
, &niter_desc
,
4847 false, false, body
))
4850 niter
= niter_desc
.niter
;
4851 type
= TREE_TYPE (niter
);
4852 if (TREE_CODE (niter_desc
.may_be_zero
) != INTEGER_CST
)
4853 niter
= build3 (COND_EXPR
, type
, niter_desc
.may_be_zero
,
4854 build_int_cst (type
, 0),
4856 record_estimate (loop
, niter
, niter_desc
.max
,
4857 last_stmt (ex
->src
),
4858 true, ex
== likely_exit
, true);
4859 record_control_iv (loop
, &niter_desc
);
4862 if (flag_aggressive_loop_optimizations
)
4863 infer_loop_bounds_from_undefined (loop
, body
);
4866 discover_iteration_bound_by_body_walk (loop
);
4868 maybe_lower_iteration_bound (loop
);
4870 /* If we know the exact number of iterations of this loop, try to
4871 not break code with undefined behavior by not recording smaller
4872 maximum number of iterations. */
4873 if (loop
->nb_iterations
4874 && TREE_CODE (loop
->nb_iterations
) == INTEGER_CST
)
4876 loop
->any_upper_bound
= true;
4877 loop
->nb_iterations_upper_bound
= wi::to_widest (loop
->nb_iterations
);
4881 /* Sets NIT to the estimated number of executions of the latch of the
4882 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
4883 large as the number of iterations. If we have no reliable estimate,
4884 the function returns false, otherwise returns true. */
4887 estimated_loop_iterations (class loop
*loop
, widest_int
*nit
)
4889 /* When SCEV information is available, try to update loop iterations
4890 estimate. Otherwise just return whatever we recorded earlier. */
4891 if (scev_initialized_p ())
4892 estimate_numbers_of_iterations (loop
);
4894 return (get_estimated_loop_iterations (loop
, nit
));
4897 /* Similar to estimated_loop_iterations, but returns the estimate only
4898 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
4899 on the number of iterations of LOOP could not be derived, returns -1. */
4902 estimated_loop_iterations_int (class loop
*loop
)
4905 HOST_WIDE_INT hwi_nit
;
4907 if (!estimated_loop_iterations (loop
, &nit
))
4910 if (!wi::fits_shwi_p (nit
))
4912 hwi_nit
= nit
.to_shwi ();
4914 return hwi_nit
< 0 ? -1 : hwi_nit
;
4918 /* Sets NIT to an upper bound for the maximum number of executions of the
4919 latch of the LOOP. If we have no reliable estimate, the function returns
4920 false, otherwise returns true. */
4923 max_loop_iterations (class loop
*loop
, widest_int
*nit
)
4925 /* When SCEV information is available, try to update loop iterations
4926 estimate. Otherwise just return whatever we recorded earlier. */
4927 if (scev_initialized_p ())
4928 estimate_numbers_of_iterations (loop
);
4930 return get_max_loop_iterations (loop
, nit
);
4933 /* Similar to max_loop_iterations, but returns the estimate only
4934 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
4935 on the number of iterations of LOOP could not be derived, returns -1. */
4938 max_loop_iterations_int (class loop
*loop
)
4941 HOST_WIDE_INT hwi_nit
;
4943 if (!max_loop_iterations (loop
, &nit
))
4946 if (!wi::fits_shwi_p (nit
))
4948 hwi_nit
= nit
.to_shwi ();
4950 return hwi_nit
< 0 ? -1 : hwi_nit
;
4953 /* Sets NIT to an likely upper bound for the maximum number of executions of the
4954 latch of the LOOP. If we have no reliable estimate, the function returns
4955 false, otherwise returns true. */
4958 likely_max_loop_iterations (class loop
*loop
, widest_int
*nit
)
4960 /* When SCEV information is available, try to update loop iterations
4961 estimate. Otherwise just return whatever we recorded earlier. */
4962 if (scev_initialized_p ())
4963 estimate_numbers_of_iterations (loop
);
4965 return get_likely_max_loop_iterations (loop
, nit
);
4968 /* Similar to max_loop_iterations, but returns the estimate only
4969 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
4970 on the number of iterations of LOOP could not be derived, returns -1. */
4973 likely_max_loop_iterations_int (class loop
*loop
)
4976 HOST_WIDE_INT hwi_nit
;
4978 if (!likely_max_loop_iterations (loop
, &nit
))
4981 if (!wi::fits_shwi_p (nit
))
4983 hwi_nit
= nit
.to_shwi ();
4985 return hwi_nit
< 0 ? -1 : hwi_nit
;
4988 /* Returns an estimate for the number of executions of statements
4989 in the LOOP. For statements before the loop exit, this exceeds
4990 the number of execution of the latch by one. */
4993 estimated_stmt_executions_int (class loop
*loop
)
4995 HOST_WIDE_INT nit
= estimated_loop_iterations_int (loop
);
5001 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
5003 /* If the computation overflows, return -1. */
5004 return snit
< 0 ? -1 : snit
;
5007 /* Sets NIT to the maximum number of executions of the latch of the
5008 LOOP, plus one. If we have no reliable estimate, the function returns
5009 false, otherwise returns true. */
5012 max_stmt_executions (class loop
*loop
, widest_int
*nit
)
5014 widest_int nit_minus_one
;
5016 if (!max_loop_iterations (loop
, nit
))
5019 nit_minus_one
= *nit
;
5023 return wi::gtu_p (*nit
, nit_minus_one
);
5026 /* Sets NIT to the estimated maximum number of executions of the latch of the
5027 LOOP, plus one. If we have no likely estimate, the function returns
5028 false, otherwise returns true. */
5031 likely_max_stmt_executions (class loop
*loop
, widest_int
*nit
)
5033 widest_int nit_minus_one
;
5035 if (!likely_max_loop_iterations (loop
, nit
))
5038 nit_minus_one
= *nit
;
5042 return wi::gtu_p (*nit
, nit_minus_one
);
5045 /* Sets NIT to the estimated number of executions of the latch of the
5046 LOOP, plus one. If we have no reliable estimate, the function returns
5047 false, otherwise returns true. */
5050 estimated_stmt_executions (class loop
*loop
, widest_int
*nit
)
5052 widest_int nit_minus_one
;
5054 if (!estimated_loop_iterations (loop
, nit
))
5057 nit_minus_one
= *nit
;
5061 return wi::gtu_p (*nit
, nit_minus_one
);
5064 /* Records estimates on numbers of iterations of loops. */
5067 estimate_numbers_of_iterations (function
*fn
)
5069 /* We don't want to issue signed overflow warnings while getting
5070 loop iteration estimates. */
5071 fold_defer_overflow_warnings ();
5073 for (auto loop
: loops_list (fn
, 0))
5074 estimate_numbers_of_iterations (loop
);
5076 fold_undefer_and_ignore_overflow_warnings ();
5079 /* Returns true if statement S1 dominates statement S2. */
5082 stmt_dominates_stmt_p (gimple
*s1
, gimple
*s2
)
5084 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
5092 gimple_stmt_iterator bsi
;
5094 if (gimple_code (s2
) == GIMPLE_PHI
)
5097 if (gimple_code (s1
) == GIMPLE_PHI
)
5100 for (bsi
= gsi_start_bb (bb1
); gsi_stmt (bsi
) != s2
; gsi_next (&bsi
))
5101 if (gsi_stmt (bsi
) == s1
)
5107 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
5110 /* Returns true when we can prove that the number of executions of
5111 STMT in the loop is at most NITER, according to the bound on
5112 the number of executions of the statement NITER_BOUND->stmt recorded in
5113 NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT.
5115 ??? This code can become quite a CPU hog - we can have many bounds,
5116 and large basic block forcing stmt_dominates_stmt_p to be queried
5117 many times on a large basic blocks, so the whole thing is O(n^2)
5118 for scev_probably_wraps_p invocation (that can be done n times).
5120 It would make more sense (and give better answers) to remember BB
5121 bounds computed by discover_iteration_bound_by_body_walk. */
5124 n_of_executions_at_most (gimple
*stmt
,
5125 class nb_iter_bound
*niter_bound
,
5128 widest_int bound
= niter_bound
->bound
;
5129 tree nit_type
= TREE_TYPE (niter
), e
;
5132 gcc_assert (TYPE_UNSIGNED (nit_type
));
5134 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
5135 the number of iterations is small. */
5136 if (!wi::fits_to_tree_p (bound
, nit_type
))
5139 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
5140 times. This means that:
5142 -- if NITER_BOUND->is_exit is true, then everything after
5143 it at most NITER_BOUND->bound times.
5145 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
5146 is executed, then NITER_BOUND->stmt is executed as well in the same
5147 iteration then STMT is executed at most NITER_BOUND->bound + 1 times.
5149 If we can determine that NITER_BOUND->stmt is always executed
5150 after STMT, then STMT is executed at most NITER_BOUND->bound + 2 times.
5151 We conclude that if both statements belong to the same
5152 basic block and STMT is before NITER_BOUND->stmt and there are no
5153 statements with side effects in between. */
5155 if (niter_bound
->is_exit
)
5157 if (stmt
== niter_bound
->stmt
5158 || !stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
5164 if (!stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
5166 gimple_stmt_iterator bsi
;
5167 if (gimple_bb (stmt
) != gimple_bb (niter_bound
->stmt
)
5168 || gimple_code (stmt
) == GIMPLE_PHI
5169 || gimple_code (niter_bound
->stmt
) == GIMPLE_PHI
)
5172 /* By stmt_dominates_stmt_p we already know that STMT appears
5173 before NITER_BOUND->STMT. Still need to test that the loop
5174 cannot be terinated by a side effect in between. */
5175 for (bsi
= gsi_for_stmt (stmt
); gsi_stmt (bsi
) != niter_bound
->stmt
;
5177 if (gimple_has_side_effects (gsi_stmt (bsi
)))
5181 || !wi::fits_to_tree_p (bound
, nit_type
))
5187 e
= fold_binary (cmp
, boolean_type_node
,
5188 niter
, wide_int_to_tree (nit_type
, bound
));
5189 return e
&& integer_nonzerop (e
);
5192 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
5195 nowrap_type_p (tree type
)
5197 if (ANY_INTEGRAL_TYPE_P (type
)
5198 && TYPE_OVERFLOW_UNDEFINED (type
))
5201 if (POINTER_TYPE_P (type
))
5207 /* Return true if we can prove LOOP is exited before evolution of induction
5208 variable {BASE, STEP} overflows with respect to its type bound. */
5211 loop_exits_before_overflow (tree base
, tree step
,
5212 gimple
*at_stmt
, class loop
*loop
)
5215 struct control_iv
*civ
;
5216 class nb_iter_bound
*bound
;
5217 tree e
, delta
, step_abs
, unsigned_base
;
5218 tree type
= TREE_TYPE (step
);
5219 tree unsigned_type
, valid_niter
;
5221 /* Don't issue signed overflow warnings. */
5222 fold_defer_overflow_warnings ();
5224 /* Compute the number of iterations before we reach the bound of the
5225 type, and verify that the loop is exited before this occurs. */
5226 unsigned_type
= unsigned_type_for (type
);
5227 unsigned_base
= fold_convert (unsigned_type
, base
);
5229 if (tree_int_cst_sign_bit (step
))
5231 tree extreme
= fold_convert (unsigned_type
,
5232 lower_bound_in_type (type
, type
));
5233 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, unsigned_base
, extreme
);
5234 step_abs
= fold_build1 (NEGATE_EXPR
, unsigned_type
,
5235 fold_convert (unsigned_type
, step
));
5239 tree extreme
= fold_convert (unsigned_type
,
5240 upper_bound_in_type (type
, type
));
5241 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, unsigned_base
);
5242 step_abs
= fold_convert (unsigned_type
, step
);
5245 valid_niter
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step_abs
);
5247 estimate_numbers_of_iterations (loop
);
5249 if (max_loop_iterations (loop
, &niter
)
5250 && wi::fits_to_tree_p (niter
, TREE_TYPE (valid_niter
))
5251 && (e
= fold_binary (GT_EXPR
, boolean_type_node
, valid_niter
,
5252 wide_int_to_tree (TREE_TYPE (valid_niter
),
5254 && integer_nonzerop (e
))
5256 fold_undefer_and_ignore_overflow_warnings ();
5260 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
5262 if (n_of_executions_at_most (at_stmt
, bound
, valid_niter
))
5264 fold_undefer_and_ignore_overflow_warnings ();
5268 fold_undefer_and_ignore_overflow_warnings ();
5270 /* Try to prove loop is exited before {base, step} overflows with the
5271 help of analyzed loop control IV. This is done only for IVs with
5272 constant step because otherwise we don't have the information. */
5273 if (TREE_CODE (step
) == INTEGER_CST
)
5275 for (civ
= loop
->control_ivs
; civ
; civ
= civ
->next
)
5277 enum tree_code code
;
5278 tree civ_type
= TREE_TYPE (civ
->step
);
5280 /* Have to consider type difference because operand_equal_p ignores
5281 that for constants. */
5282 if (TYPE_UNSIGNED (type
) != TYPE_UNSIGNED (civ_type
)
5283 || element_precision (type
) != element_precision (civ_type
))
5286 /* Only consider control IV with same step. */
5287 if (!operand_equal_p (step
, civ
->step
, 0))
5290 /* Done proving if this is a no-overflow control IV. */
5291 if (operand_equal_p (base
, civ
->base
, 0))
5294 /* Control IV is recorded after expanding simple operations,
5295 Here we expand base and compare it too. */
5296 tree expanded_base
= expand_simple_operations (base
);
5297 if (operand_equal_p (expanded_base
, civ
->base
, 0))
5300 /* If this is a before stepping control IV, in other words, we have
5302 {civ_base, step} = {base + step, step}
5304 Because civ {base + step, step} doesn't overflow during loop
5305 iterations, {base, step} will not overflow if we can prove the
5306 operation "base + step" does not overflow. Specifically, we try
5307 to prove below conditions are satisfied:
5309 base <= UPPER_BOUND (type) - step ;;step > 0
5310 base >= LOWER_BOUND (type) - step ;;step < 0
5312 by proving the reverse conditions are false using loop's initial
5314 if (POINTER_TYPE_P (TREE_TYPE (base
)))
5315 code
= POINTER_PLUS_EXPR
;
5319 tree stepped
= fold_build2 (code
, TREE_TYPE (base
), base
, step
);
5320 tree expanded_stepped
= fold_build2 (code
, TREE_TYPE (base
),
5321 expanded_base
, step
);
5322 if (operand_equal_p (stepped
, civ
->base
, 0)
5323 || operand_equal_p (expanded_stepped
, civ
->base
, 0))
5327 if (tree_int_cst_sign_bit (step
))
5330 extreme
= lower_bound_in_type (type
, type
);
5335 extreme
= upper_bound_in_type (type
, type
);
5337 extreme
= fold_build2 (MINUS_EXPR
, type
, extreme
, step
);
5338 e
= fold_build2 (code
, boolean_type_node
, base
, extreme
);
5339 e
= simplify_using_initial_conditions (loop
, e
);
5340 if (integer_zerop (e
))
5349 /* VAR is scev variable whose evolution part is constant STEP, this function
5350 proves that VAR can't overflow by using value range info. If VAR's value
5351 range is [MIN, MAX], it can be proven by:
5352 MAX + step doesn't overflow ; if step > 0
5354 MIN + step doesn't underflow ; if step < 0.
5356 We can only do this if var is computed in every loop iteration, i.e, var's
5357 definition has to dominate loop latch. Consider below example:
5365 # RANGE [0, 4294967294] NONZERO 65535
5366 # i_21 = PHI <0(3), i_18(9)>
5373 # RANGE [0, 65533] NONZERO 65535
5374 _6 = i_21 + 4294967295;
5375 # RANGE [0, 65533] NONZERO 65535
5376 _7 = (long unsigned int) _6;
5377 # RANGE [0, 524264] NONZERO 524280
5379 # PT = nonlocal escaped
5384 # RANGE [1, 65535] NONZERO 65535
5398 VAR _6 doesn't overflow only with pre-condition (i_21 != 0), here we
5399 can't use _6 to prove no-overlfow for _7. In fact, var _7 takes value
5400 sequence (4294967295, 0, 1, ..., 65533) in loop life time, rather than
5401 (4294967295, 4294967296, ...). */
5404 scev_var_range_cant_overflow (tree var
, tree step
, class loop
*loop
)
5407 wide_int minv
, maxv
, diff
, step_wi
;
5409 if (TREE_CODE (step
) != INTEGER_CST
|| !INTEGRAL_TYPE_P (TREE_TYPE (var
)))
5412 /* Check if VAR evaluates in every loop iteration. It's not the case
5413 if VAR is default definition or does not dominate loop's latch. */
5414 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (var
));
5415 if (!def_bb
|| !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, def_bb
))
5418 Value_Range
r (TREE_TYPE (var
));
5419 get_range_query (cfun
)->range_of_expr (r
, var
);
5420 if (r
.kind () != VR_RANGE
)
5423 /* VAR is a scev whose evolution part is STEP and value range info
5424 is [MIN, MAX], we can prove its no-overflowness by conditions:
5426 type_MAX - MAX >= step ; if step > 0
5427 MIN - type_MIN >= |step| ; if step < 0.
5429 Or VAR must take value outside of value range, which is not true. */
5430 step_wi
= wi::to_wide (step
);
5431 type
= TREE_TYPE (var
);
5432 if (tree_int_cst_sign_bit (step
))
5434 diff
= r
.lower_bound () - wi::to_wide (lower_bound_in_type (type
, type
));
5435 step_wi
= - step_wi
;
5438 diff
= wi::to_wide (upper_bound_in_type (type
, type
)) - r
.upper_bound ();
5440 return (wi::geu_p (diff
, step_wi
));
5443 /* Return false only when the induction variable BASE + STEP * I is
5444 known to not overflow: i.e. when the number of iterations is small
5445 enough with respect to the step and initial condition in order to
5446 keep the evolution confined in TYPEs bounds. Return true when the
5447 iv is known to overflow or when the property is not computable.
5449 USE_OVERFLOW_SEMANTICS is true if this function should assume that
5450 the rules for overflow of the given language apply (e.g., that signed
5451 arithmetics in C does not overflow).
5453 If VAR is a ssa variable, this function also returns false if VAR can
5454 be proven not overflow with value range info. */
5457 scev_probably_wraps_p (tree var
, tree base
, tree step
,
5458 gimple
*at_stmt
, class loop
*loop
,
5459 bool use_overflow_semantics
)
5461 /* FIXME: We really need something like
5462 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
5464 We used to test for the following situation that frequently appears
5465 during address arithmetics:
5467 D.1621_13 = (long unsigned intD.4) D.1620_12;
5468 D.1622_14 = D.1621_13 * 8;
5469 D.1623_15 = (doubleD.29 *) D.1622_14;
5471 And derived that the sequence corresponding to D_14
5472 can be proved to not wrap because it is used for computing a
5473 memory access; however, this is not really the case -- for example,
5474 if D_12 = (unsigned char) [254,+,1], then D_14 has values
5475 2032, 2040, 0, 8, ..., but the code is still legal. */
5477 if (chrec_contains_undetermined (base
)
5478 || chrec_contains_undetermined (step
))
5481 if (integer_zerop (step
))
5484 /* If we can use the fact that signed and pointer arithmetics does not
5485 wrap, we are done. */
5486 if (use_overflow_semantics
&& nowrap_type_p (TREE_TYPE (base
)))
5489 /* To be able to use estimates on number of iterations of the loop,
5490 we must have an upper bound on the absolute value of the step. */
5491 if (TREE_CODE (step
) != INTEGER_CST
)
5494 /* Check if var can be proven not overflow with value range info. */
5495 if (var
&& TREE_CODE (var
) == SSA_NAME
5496 && scev_var_range_cant_overflow (var
, step
, loop
))
5499 if (loop_exits_before_overflow (base
, step
, at_stmt
, loop
))
5502 /* At this point we still don't have a proof that the iv does not
5503 overflow: give up. */
5507 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
5510 free_numbers_of_iterations_estimates (class loop
*loop
)
5512 struct control_iv
*civ
;
5513 class nb_iter_bound
*bound
;
5515 loop
->nb_iterations
= NULL
;
5516 loop
->estimate_state
= EST_NOT_COMPUTED
;
5517 for (bound
= loop
->bounds
; bound
;)
5519 class nb_iter_bound
*next
= bound
->next
;
5523 loop
->bounds
= NULL
;
5525 for (civ
= loop
->control_ivs
; civ
;)
5527 struct control_iv
*next
= civ
->next
;
5531 loop
->control_ivs
= NULL
;
5534 /* Frees the information on upper bounds on numbers of iterations of loops. */
5537 free_numbers_of_iterations_estimates (function
*fn
)
5539 for (auto loop
: loops_list (fn
, 0))
5540 free_numbers_of_iterations_estimates (loop
);
5543 /* Substitute value VAL for ssa name NAME inside expressions held
5547 substitute_in_loop_info (class loop
*loop
, tree name
, tree val
)
5549 loop
->nb_iterations
= simplify_replace_tree (loop
->nb_iterations
, name
, val
);