1 /* Functions to determine/estimate number of iterations of a loop.
2 Copyright (C) 2004-2020 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"
47 /* The maximum number of dominator BBs we search for conditions
48 of loop header copies we use for simplifying a conditional
50 #define MAX_DOMINATORS_TO_WALK 8
54 Analysis of number of iterations of an affine exit test.
58 /* Bounds on some value, BELOW <= X <= UP. */
65 static bool number_of_iterations_popcount (loop_p loop
, edge exit
,
67 class tree_niter_desc
*niter
);
70 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */
73 split_to_var_and_offset (tree expr
, tree
*var
, mpz_t offset
)
75 tree type
= TREE_TYPE (expr
);
80 mpz_set_ui (offset
, 0);
82 switch (TREE_CODE (expr
))
89 case POINTER_PLUS_EXPR
:
90 op0
= TREE_OPERAND (expr
, 0);
91 op1
= TREE_OPERAND (expr
, 1);
93 if (TREE_CODE (op1
) != INTEGER_CST
)
97 /* Always sign extend the offset. */
98 wi::to_mpz (wi::to_wide (op1
), offset
, SIGNED
);
100 mpz_neg (offset
, offset
);
104 *var
= build_int_cst_type (type
, 0);
105 wi::to_mpz (wi::to_wide (expr
), offset
, TYPE_SIGN (type
));
113 /* From condition C0 CMP C1 derives information regarding the value range
114 of VAR, which is of TYPE. Results are stored in to BELOW and UP. */
117 refine_value_range_using_guard (tree type
, tree var
,
118 tree c0
, enum tree_code cmp
, tree c1
,
119 mpz_t below
, mpz_t up
)
121 tree varc0
, varc1
, ctype
;
123 mpz_t mint
, maxt
, minc1
, maxc1
;
125 bool no_wrap
= nowrap_type_p (type
);
127 signop sgn
= TYPE_SIGN (type
);
135 STRIP_SIGN_NOPS (c0
);
136 STRIP_SIGN_NOPS (c1
);
137 ctype
= TREE_TYPE (c0
);
138 if (!useless_type_conversion_p (ctype
, type
))
144 /* We could derive quite precise information from EQ_EXPR, however,
145 such a guard is unlikely to appear, so we do not bother with
150 /* NE_EXPR comparisons do not contain much of useful information,
151 except for cases of comparing with bounds. */
152 if (TREE_CODE (c1
) != INTEGER_CST
153 || !INTEGRAL_TYPE_P (type
))
156 /* Ensure that the condition speaks about an expression in the same
158 ctype
= TREE_TYPE (c0
);
159 if (TYPE_PRECISION (ctype
) != TYPE_PRECISION (type
))
161 c0
= fold_convert (type
, c0
);
162 c1
= fold_convert (type
, c1
);
164 if (operand_equal_p (var
, c0
, 0))
168 /* Case of comparing VAR with its below/up bounds. */
170 wi::to_mpz (wi::to_wide (c1
), valc1
, TYPE_SIGN (type
));
171 if (mpz_cmp (valc1
, below
) == 0)
173 if (mpz_cmp (valc1
, up
) == 0)
180 /* Case of comparing with the bounds of the type. */
181 wide_int min
= wi::min_value (type
);
182 wide_int max
= wi::max_value (type
);
184 if (wi::to_wide (c1
) == min
)
186 if (wi::to_wide (c1
) == max
)
190 /* Quick return if no useful information. */
202 split_to_var_and_offset (expand_simple_operations (c0
), &varc0
, offc0
);
203 split_to_var_and_offset (expand_simple_operations (c1
), &varc1
, offc1
);
205 /* We are only interested in comparisons of expressions based on VAR. */
206 if (operand_equal_p (var
, varc1
, 0))
208 std::swap (varc0
, varc1
);
209 mpz_swap (offc0
, offc1
);
210 cmp
= swap_tree_comparison (cmp
);
212 else if (!operand_equal_p (var
, varc0
, 0))
221 get_type_static_bounds (type
, mint
, maxt
);
224 /* Setup range information for varc1. */
225 if (integer_zerop (varc1
))
227 wi::to_mpz (0, minc1
, TYPE_SIGN (type
));
228 wi::to_mpz (0, maxc1
, TYPE_SIGN (type
));
230 else if (TREE_CODE (varc1
) == SSA_NAME
231 && INTEGRAL_TYPE_P (type
)
232 && get_range_info (varc1
, &minv
, &maxv
) == VR_RANGE
)
234 gcc_assert (wi::le_p (minv
, maxv
, sgn
));
235 wi::to_mpz (minv
, minc1
, sgn
);
236 wi::to_mpz (maxv
, maxc1
, sgn
);
240 mpz_set (minc1
, mint
);
241 mpz_set (maxc1
, maxt
);
244 /* Compute valid range information for varc1 + offc1. Note nothing
245 useful can be derived if it overflows or underflows. Overflow or
246 underflow could happen when:
248 offc1 > 0 && varc1 + offc1 > MAX_VAL (type)
249 offc1 < 0 && varc1 + offc1 < MIN_VAL (type). */
250 mpz_add (minc1
, minc1
, offc1
);
251 mpz_add (maxc1
, maxc1
, offc1
);
253 || mpz_sgn (offc1
) == 0
254 || (mpz_sgn (offc1
) < 0 && mpz_cmp (minc1
, mint
) >= 0)
255 || (mpz_sgn (offc1
) > 0 && mpz_cmp (maxc1
, maxt
) <= 0));
259 if (mpz_cmp (minc1
, mint
) < 0)
260 mpz_set (minc1
, mint
);
261 if (mpz_cmp (maxc1
, maxt
) > 0)
262 mpz_set (maxc1
, maxt
);
267 mpz_sub_ui (maxc1
, maxc1
, 1);
272 mpz_add_ui (minc1
, minc1
, 1);
275 /* Compute range information for varc0. If there is no overflow,
276 the condition implied that
278 (varc0) cmp (varc1 + offc1 - offc0)
280 We can possibly improve the upper bound of varc0 if cmp is LE_EXPR,
281 or the below bound if cmp is GE_EXPR.
283 To prove there is no overflow/underflow, we need to check below
285 1) cmp == LE_EXPR && offc0 > 0
287 (varc0 + offc0) doesn't overflow
288 && (varc1 + offc1 - offc0) doesn't underflow
290 2) cmp == LE_EXPR && offc0 < 0
292 (varc0 + offc0) doesn't underflow
293 && (varc1 + offc1 - offc0) doesn't overfloe
295 In this case, (varc0 + offc0) will never underflow if we can
296 prove (varc1 + offc1 - offc0) doesn't overflow.
298 3) cmp == GE_EXPR && offc0 < 0
300 (varc0 + offc0) doesn't underflow
301 && (varc1 + offc1 - offc0) doesn't overflow
303 4) cmp == GE_EXPR && offc0 > 0
305 (varc0 + offc0) doesn't overflow
306 && (varc1 + offc1 - offc0) doesn't underflow
308 In this case, (varc0 + offc0) will never overflow if we can
309 prove (varc1 + offc1 - offc0) doesn't underflow.
311 Note we only handle case 2 and 4 in below code. */
313 mpz_sub (minc1
, minc1
, offc0
);
314 mpz_sub (maxc1
, maxc1
, offc0
);
316 || mpz_sgn (offc0
) == 0
318 && mpz_sgn (offc0
) < 0 && mpz_cmp (maxc1
, maxt
) <= 0)
320 && mpz_sgn (offc0
) > 0 && mpz_cmp (minc1
, mint
) >= 0));
326 if (mpz_cmp (up
, maxc1
) > 0)
331 if (mpz_cmp (below
, minc1
) < 0)
332 mpz_set (below
, minc1
);
344 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
345 in TYPE to MIN and MAX. */
348 determine_value_range (class loop
*loop
, tree type
, tree var
, mpz_t off
,
349 mpz_t min
, mpz_t max
)
355 enum value_range_kind rtype
= VR_VARYING
;
357 /* If the expression is a constant, we know its value exactly. */
358 if (integer_zerop (var
))
365 get_type_static_bounds (type
, min
, max
);
367 /* See if we have some range info from VRP. */
368 if (TREE_CODE (var
) == SSA_NAME
&& INTEGRAL_TYPE_P (type
))
370 edge e
= loop_preheader_edge (loop
);
371 signop sgn
= TYPE_SIGN (type
);
374 /* Either for VAR itself... */
375 rtype
= get_range_info (var
, &minv
, &maxv
);
376 /* Or for PHI results in loop->header where VAR is used as
377 PHI argument from the loop preheader edge. */
378 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
380 gphi
*phi
= gsi
.phi ();
382 if (PHI_ARG_DEF_FROM_EDGE (phi
, e
) == var
383 && (get_range_info (gimple_phi_result (phi
), &minc
, &maxc
)
386 if (rtype
!= VR_RANGE
)
394 minv
= wi::max (minv
, minc
, sgn
);
395 maxv
= wi::min (maxv
, maxc
, sgn
);
396 /* If the PHI result range are inconsistent with
397 the VAR range, give up on looking at the PHI
398 results. This can happen if VR_UNDEFINED is
400 if (wi::gt_p (minv
, maxv
, sgn
))
402 rtype
= get_range_info (var
, &minv
, &maxv
);
410 if (rtype
!= VR_RANGE
)
417 gcc_assert (wi::le_p (minv
, maxv
, sgn
));
418 wi::to_mpz (minv
, minm
, sgn
);
419 wi::to_mpz (maxv
, maxm
, sgn
);
421 /* Now walk the dominators of the loop header and use the entry
422 guards to refine the estimates. */
423 for (bb
= loop
->header
;
424 bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && cnt
< MAX_DOMINATORS_TO_WALK
;
425 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
432 if (!single_pred_p (bb
))
434 e
= single_pred_edge (bb
);
436 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
439 cond
= last_stmt (e
->src
);
440 c0
= gimple_cond_lhs (cond
);
441 cmp
= gimple_cond_code (cond
);
442 c1
= gimple_cond_rhs (cond
);
444 if (e
->flags
& EDGE_FALSE_VALUE
)
445 cmp
= invert_tree_comparison (cmp
, false);
447 refine_value_range_using_guard (type
, var
, c0
, cmp
, c1
, minm
, maxm
);
451 mpz_add (minm
, minm
, off
);
452 mpz_add (maxm
, maxm
, off
);
453 /* If the computation may not wrap or off is zero, then this
454 is always fine. If off is negative and minv + off isn't
455 smaller than type's minimum, or off is positive and
456 maxv + off isn't bigger than type's maximum, use the more
457 precise range too. */
458 if (nowrap_type_p (type
)
459 || mpz_sgn (off
) == 0
460 || (mpz_sgn (off
) < 0 && mpz_cmp (minm
, min
) >= 0)
461 || (mpz_sgn (off
) > 0 && mpz_cmp (maxm
, max
) <= 0))
473 /* If the computation may wrap, we know nothing about the value, except for
474 the range of the type. */
475 if (!nowrap_type_p (type
))
478 /* Since the addition of OFF does not wrap, if OFF is positive, then we may
479 add it to MIN, otherwise to MAX. */
480 if (mpz_sgn (off
) < 0)
481 mpz_add (max
, max
, off
);
483 mpz_add (min
, min
, off
);
486 /* Stores the bounds on the difference of the values of the expressions
487 (var + X) and (var + Y), computed in TYPE, to BNDS. */
490 bound_difference_of_offsetted_base (tree type
, mpz_t x
, mpz_t y
,
493 int rel
= mpz_cmp (x
, y
);
494 bool may_wrap
= !nowrap_type_p (type
);
497 /* If X == Y, then the expressions are always equal.
498 If X > Y, there are the following possibilities:
499 a) neither of var + X and var + Y overflow or underflow, or both of
500 them do. Then their difference is X - Y.
501 b) var + X overflows, and var + Y does not. Then the values of the
502 expressions are var + X - M and var + Y, where M is the range of
503 the type, and their difference is X - Y - M.
504 c) var + Y underflows and var + X does not. Their difference again
506 Therefore, if the arithmetics in type does not overflow, then the
507 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
508 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
509 (X - Y, X - Y + M). */
513 mpz_set_ui (bnds
->below
, 0);
514 mpz_set_ui (bnds
->up
, 0);
519 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), m
, UNSIGNED
);
520 mpz_add_ui (m
, m
, 1);
521 mpz_sub (bnds
->up
, x
, y
);
522 mpz_set (bnds
->below
, bnds
->up
);
527 mpz_sub (bnds
->below
, bnds
->below
, m
);
529 mpz_add (bnds
->up
, bnds
->up
, m
);
535 /* From condition C0 CMP C1 derives information regarding the
536 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
537 and stores it to BNDS. */
540 refine_bounds_using_guard (tree type
, tree varx
, mpz_t offx
,
541 tree vary
, mpz_t offy
,
542 tree c0
, enum tree_code cmp
, tree c1
,
545 tree varc0
, varc1
, ctype
;
546 mpz_t offc0
, offc1
, loffx
, loffy
, bnd
;
548 bool no_wrap
= nowrap_type_p (type
);
557 STRIP_SIGN_NOPS (c0
);
558 STRIP_SIGN_NOPS (c1
);
559 ctype
= TREE_TYPE (c0
);
560 if (!useless_type_conversion_p (ctype
, type
))
566 /* We could derive quite precise information from EQ_EXPR, however, such
567 a guard is unlikely to appear, so we do not bother with handling
572 /* NE_EXPR comparisons do not contain much of useful information, except for
573 special case of comparing with the bounds of the type. */
574 if (TREE_CODE (c1
) != INTEGER_CST
575 || !INTEGRAL_TYPE_P (type
))
578 /* Ensure that the condition speaks about an expression in the same type
580 ctype
= TREE_TYPE (c0
);
581 if (TYPE_PRECISION (ctype
) != TYPE_PRECISION (type
))
583 c0
= fold_convert (type
, c0
);
584 c1
= fold_convert (type
, c1
);
586 if (TYPE_MIN_VALUE (type
)
587 && operand_equal_p (c1
, TYPE_MIN_VALUE (type
), 0))
592 if (TYPE_MAX_VALUE (type
)
593 && operand_equal_p (c1
, TYPE_MAX_VALUE (type
), 0))
606 split_to_var_and_offset (expand_simple_operations (c0
), &varc0
, offc0
);
607 split_to_var_and_offset (expand_simple_operations (c1
), &varc1
, offc1
);
609 /* We are only interested in comparisons of expressions based on VARX and
610 VARY. TODO -- we might also be able to derive some bounds from
611 expressions containing just one of the variables. */
613 if (operand_equal_p (varx
, varc1
, 0))
615 std::swap (varc0
, varc1
);
616 mpz_swap (offc0
, offc1
);
617 cmp
= swap_tree_comparison (cmp
);
620 if (!operand_equal_p (varx
, varc0
, 0)
621 || !operand_equal_p (vary
, varc1
, 0))
624 mpz_init_set (loffx
, offx
);
625 mpz_init_set (loffy
, offy
);
627 if (cmp
== GT_EXPR
|| cmp
== GE_EXPR
)
629 std::swap (varx
, vary
);
630 mpz_swap (offc0
, offc1
);
631 mpz_swap (loffx
, loffy
);
632 cmp
= swap_tree_comparison (cmp
);
636 /* If there is no overflow, the condition implies that
638 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
640 The overflows and underflows may complicate things a bit; each
641 overflow decreases the appropriate offset by M, and underflow
642 increases it by M. The above inequality would not necessarily be
645 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
646 VARX + OFFC0 overflows, but VARX + OFFX does not.
647 This may only happen if OFFX < OFFC0.
648 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
649 VARY + OFFC1 underflows and VARY + OFFY does not.
650 This may only happen if OFFY > OFFC1. */
659 x_ok
= (integer_zerop (varx
)
660 || mpz_cmp (loffx
, offc0
) >= 0);
661 y_ok
= (integer_zerop (vary
)
662 || mpz_cmp (loffy
, offc1
) <= 0);
668 mpz_sub (bnd
, loffx
, loffy
);
669 mpz_add (bnd
, bnd
, offc1
);
670 mpz_sub (bnd
, bnd
, offc0
);
673 mpz_sub_ui (bnd
, bnd
, 1);
678 if (mpz_cmp (bnds
->below
, bnd
) < 0)
679 mpz_set (bnds
->below
, bnd
);
683 if (mpz_cmp (bnd
, bnds
->up
) < 0)
684 mpz_set (bnds
->up
, bnd
);
696 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
697 The subtraction is considered to be performed in arbitrary precision,
700 We do not attempt to be too clever regarding the value ranges of X and
701 Y; most of the time, they are just integers or ssa names offsetted by
702 integer. However, we try to use the information contained in the
703 comparisons before the loop (usually created by loop header copying). */
706 bound_difference (class loop
*loop
, tree x
, tree y
, bounds
*bnds
)
708 tree type
= TREE_TYPE (x
);
711 mpz_t minx
, maxx
, miny
, maxy
;
719 /* Get rid of unnecessary casts, but preserve the value of
724 mpz_init (bnds
->below
);
728 split_to_var_and_offset (x
, &varx
, offx
);
729 split_to_var_and_offset (y
, &vary
, offy
);
731 if (!integer_zerop (varx
)
732 && operand_equal_p (varx
, vary
, 0))
734 /* Special case VARX == VARY -- we just need to compare the
735 offsets. The matters are a bit more complicated in the
736 case addition of offsets may wrap. */
737 bound_difference_of_offsetted_base (type
, offx
, offy
, bnds
);
741 /* Otherwise, use the value ranges to determine the initial
742 estimates on below and up. */
747 determine_value_range (loop
, type
, varx
, offx
, minx
, maxx
);
748 determine_value_range (loop
, type
, vary
, offy
, miny
, maxy
);
750 mpz_sub (bnds
->below
, minx
, maxy
);
751 mpz_sub (bnds
->up
, maxx
, miny
);
758 /* If both X and Y are constants, we cannot get any more precise. */
759 if (integer_zerop (varx
) && integer_zerop (vary
))
762 /* Now walk the dominators of the loop header and use the entry
763 guards to refine the estimates. */
764 for (bb
= loop
->header
;
765 bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && cnt
< MAX_DOMINATORS_TO_WALK
;
766 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
768 if (!single_pred_p (bb
))
770 e
= single_pred_edge (bb
);
772 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
775 cond
= last_stmt (e
->src
);
776 c0
= gimple_cond_lhs (cond
);
777 cmp
= gimple_cond_code (cond
);
778 c1
= gimple_cond_rhs (cond
);
780 if (e
->flags
& EDGE_FALSE_VALUE
)
781 cmp
= invert_tree_comparison (cmp
, false);
783 refine_bounds_using_guard (type
, varx
, offx
, vary
, offy
,
793 /* Update the bounds in BNDS that restrict the value of X to the bounds
794 that restrict the value of X + DELTA. X can be obtained as a
795 difference of two values in TYPE. */
798 bounds_add (bounds
*bnds
, const widest_int
&delta
, tree type
)
803 wi::to_mpz (delta
, mdelta
, SIGNED
);
806 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), max
, UNSIGNED
);
808 mpz_add (bnds
->up
, bnds
->up
, mdelta
);
809 mpz_add (bnds
->below
, bnds
->below
, mdelta
);
811 if (mpz_cmp (bnds
->up
, max
) > 0)
812 mpz_set (bnds
->up
, max
);
815 if (mpz_cmp (bnds
->below
, max
) < 0)
816 mpz_set (bnds
->below
, max
);
822 /* Update the bounds in BNDS that restrict the value of X to the bounds
823 that restrict the value of -X. */
826 bounds_negate (bounds
*bnds
)
830 mpz_init_set (tmp
, bnds
->up
);
831 mpz_neg (bnds
->up
, bnds
->below
);
832 mpz_neg (bnds
->below
, tmp
);
836 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
839 inverse (tree x
, tree mask
)
841 tree type
= TREE_TYPE (x
);
843 unsigned ctr
= tree_floor_log2 (mask
);
845 if (TYPE_PRECISION (type
) <= HOST_BITS_PER_WIDE_INT
)
847 unsigned HOST_WIDE_INT ix
;
848 unsigned HOST_WIDE_INT imask
;
849 unsigned HOST_WIDE_INT irslt
= 1;
851 gcc_assert (cst_and_fits_in_hwi (x
));
852 gcc_assert (cst_and_fits_in_hwi (mask
));
854 ix
= int_cst_value (x
);
855 imask
= int_cst_value (mask
);
864 rslt
= build_int_cst_type (type
, irslt
);
868 rslt
= build_int_cst (type
, 1);
871 rslt
= int_const_binop (MULT_EXPR
, rslt
, x
);
872 x
= int_const_binop (MULT_EXPR
, x
, x
);
874 rslt
= int_const_binop (BIT_AND_EXPR
, rslt
, mask
);
880 /* Derives the upper bound BND on the number of executions of loop with exit
881 condition S * i <> C. If NO_OVERFLOW is true, then the control variable of
882 the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed
883 that the loop ends through this exit, i.e., the induction variable ever
884 reaches the value of C.
886 The value C is equal to final - base, where final and base are the final and
887 initial value of the actual induction variable in the analysed loop. BNDS
888 bounds the value of this difference when computed in signed type with
889 unbounded range, while the computation of C is performed in an unsigned
890 type with the range matching the range of the type of the induction variable.
891 In particular, BNDS.up contains an upper bound on C in the following cases:
892 -- if the iv must reach its final value without overflow, i.e., if
893 NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
894 -- if final >= base, which we know to hold when BNDS.below >= 0. */
897 number_of_iterations_ne_max (mpz_t bnd
, bool no_overflow
, tree c
, tree s
,
898 bounds
*bnds
, bool exit_must_be_taken
)
902 tree type
= TREE_TYPE (c
);
903 bool bnds_u_valid
= ((no_overflow
&& exit_must_be_taken
)
904 || mpz_sgn (bnds
->below
) >= 0);
907 || (TREE_CODE (c
) == INTEGER_CST
908 && TREE_CODE (s
) == INTEGER_CST
909 && wi::mod_trunc (wi::to_wide (c
), wi::to_wide (s
),
910 TYPE_SIGN (type
)) == 0)
911 || (TYPE_OVERFLOW_UNDEFINED (type
)
912 && multiple_of_p (type
, c
, s
)))
914 /* If C is an exact multiple of S, then its value will be reached before
915 the induction variable overflows (unless the loop is exited in some
916 other way before). Note that the actual induction variable in the
917 loop (which ranges from base to final instead of from 0 to C) may
918 overflow, in which case BNDS.up will not be giving a correct upper
919 bound on C; thus, BNDS_U_VALID had to be computed in advance. */
921 exit_must_be_taken
= true;
924 /* If the induction variable can overflow, the number of iterations is at
925 most the period of the control variable (or infinite, but in that case
926 the whole # of iterations analysis will fail). */
929 max
= wi::mask
<widest_int
> (TYPE_PRECISION (type
)
930 - wi::ctz (wi::to_wide (s
)), false);
931 wi::to_mpz (max
, bnd
, UNSIGNED
);
935 /* Now we know that the induction variable does not overflow, so the loop
936 iterates at most (range of type / S) times. */
937 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), bnd
, UNSIGNED
);
939 /* If the induction variable is guaranteed to reach the value of C before
941 if (exit_must_be_taken
)
943 /* ... then we can strengthen this to C / S, and possibly we can use
944 the upper bound on C given by BNDS. */
945 if (TREE_CODE (c
) == INTEGER_CST
)
946 wi::to_mpz (wi::to_wide (c
), bnd
, UNSIGNED
);
947 else if (bnds_u_valid
)
948 mpz_set (bnd
, bnds
->up
);
952 wi::to_mpz (wi::to_wide (s
), d
, UNSIGNED
);
953 mpz_fdiv_q (bnd
, bnd
, d
);
957 /* Determines number of iterations of loop whose ending condition
958 is IV <> FINAL. TYPE is the type of the iv. The number of
959 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
960 we know that the exit must be taken eventually, i.e., that the IV
961 ever reaches the value FINAL (we derived this earlier, and possibly set
962 NITER->assumptions to make sure this is the case). BNDS contains the
963 bounds on the difference FINAL - IV->base. */
966 number_of_iterations_ne (class loop
*loop
, tree type
, affine_iv
*iv
,
967 tree final
, class tree_niter_desc
*niter
,
968 bool exit_must_be_taken
, bounds
*bnds
)
970 tree niter_type
= unsigned_type_for (type
);
971 tree s
, c
, d
, bits
, assumption
, tmp
, bound
;
974 niter
->control
= *iv
;
975 niter
->bound
= final
;
976 niter
->cmp
= NE_EXPR
;
978 /* Rearrange the terms so that we get inequality S * i <> C, with S
979 positive. Also cast everything to the unsigned type. If IV does
980 not overflow, BNDS bounds the value of C. Also, this is the
981 case if the computation |FINAL - IV->base| does not overflow, i.e.,
982 if BNDS->below in the result is nonnegative. */
983 if (tree_int_cst_sign_bit (iv
->step
))
985 s
= fold_convert (niter_type
,
986 fold_build1 (NEGATE_EXPR
, type
, iv
->step
));
987 c
= fold_build2 (MINUS_EXPR
, niter_type
,
988 fold_convert (niter_type
, iv
->base
),
989 fold_convert (niter_type
, final
));
990 bounds_negate (bnds
);
994 s
= fold_convert (niter_type
, iv
->step
);
995 c
= fold_build2 (MINUS_EXPR
, niter_type
,
996 fold_convert (niter_type
, final
),
997 fold_convert (niter_type
, iv
->base
));
1001 number_of_iterations_ne_max (max
, iv
->no_overflow
, c
, s
, bnds
,
1002 exit_must_be_taken
);
1003 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, max
, false),
1004 TYPE_SIGN (niter_type
));
1007 /* Compute no-overflow information for the control iv. This can be
1008 proven when below two conditions are satisfied:
1010 1) IV evaluates toward FINAL at beginning, i.e:
1011 base <= FINAL ; step > 0
1012 base >= FINAL ; step < 0
1014 2) |FINAL - base| is an exact multiple of step.
1016 Unfortunately, it's hard to prove above conditions after pass loop-ch
1017 because loop with exit condition (IV != FINAL) usually will be guarded
1018 by initial-condition (IV.base - IV.step != FINAL). In this case, we
1019 can alternatively try to prove below conditions:
1021 1') IV evaluates toward FINAL at beginning, i.e:
1022 new_base = base - step < FINAL ; step > 0
1023 && base - step doesn't underflow
1024 new_base = base - step > FINAL ; step < 0
1025 && base - step doesn't overflow
1027 2') |FINAL - new_base| is an exact multiple of step.
1029 Please refer to PR34114 as an example of loop-ch's impact, also refer
1030 to PR72817 as an example why condition 2') is necessary.
1032 Note, for NE_EXPR, base equals to FINAL is a special case, in
1033 which the loop exits immediately, and the iv does not overflow. */
1034 if (!niter
->control
.no_overflow
1035 && (integer_onep (s
) || multiple_of_p (type
, c
, s
)))
1037 tree t
, cond
, new_c
, relaxed_cond
= boolean_false_node
;
1039 if (tree_int_cst_sign_bit (iv
->step
))
1041 cond
= fold_build2 (GE_EXPR
, boolean_type_node
, iv
->base
, final
);
1042 if (TREE_CODE (type
) == INTEGER_TYPE
)
1044 /* Only when base - step doesn't overflow. */
1045 t
= TYPE_MAX_VALUE (type
);
1046 t
= fold_build2 (PLUS_EXPR
, type
, t
, iv
->step
);
1047 t
= fold_build2 (GE_EXPR
, boolean_type_node
, t
, iv
->base
);
1048 if (integer_nonzerop (t
))
1050 t
= fold_build2 (MINUS_EXPR
, type
, iv
->base
, iv
->step
);
1051 new_c
= fold_build2 (MINUS_EXPR
, niter_type
,
1052 fold_convert (niter_type
, t
),
1053 fold_convert (niter_type
, final
));
1054 if (multiple_of_p (type
, new_c
, s
))
1055 relaxed_cond
= fold_build2 (GT_EXPR
, boolean_type_node
,
1062 cond
= fold_build2 (LE_EXPR
, boolean_type_node
, iv
->base
, final
);
1063 if (TREE_CODE (type
) == INTEGER_TYPE
)
1065 /* Only when base - step doesn't underflow. */
1066 t
= TYPE_MIN_VALUE (type
);
1067 t
= fold_build2 (PLUS_EXPR
, type
, t
, iv
->step
);
1068 t
= fold_build2 (LE_EXPR
, boolean_type_node
, t
, iv
->base
);
1069 if (integer_nonzerop (t
))
1071 t
= fold_build2 (MINUS_EXPR
, type
, iv
->base
, iv
->step
);
1072 new_c
= fold_build2 (MINUS_EXPR
, niter_type
,
1073 fold_convert (niter_type
, final
),
1074 fold_convert (niter_type
, t
));
1075 if (multiple_of_p (type
, new_c
, s
))
1076 relaxed_cond
= fold_build2 (LT_EXPR
, boolean_type_node
,
1082 t
= simplify_using_initial_conditions (loop
, cond
);
1083 if (!t
|| !integer_onep (t
))
1084 t
= simplify_using_initial_conditions (loop
, relaxed_cond
);
1086 if (t
&& integer_onep (t
))
1087 niter
->control
.no_overflow
= true;
1090 /* First the trivial cases -- when the step is 1. */
1091 if (integer_onep (s
))
1096 if (niter
->control
.no_overflow
&& multiple_of_p (type
, c
, s
))
1098 niter
->niter
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, c
, s
);
1102 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
1103 is infinite. Otherwise, the number of iterations is
1104 (inverse(s/d) * (c/d)) mod (size of mode/d). */
1105 bits
= num_ending_zeros (s
);
1106 bound
= build_low_bits_mask (niter_type
,
1107 (TYPE_PRECISION (niter_type
)
1108 - tree_to_uhwi (bits
)));
1110 d
= fold_binary_to_constant (LSHIFT_EXPR
, niter_type
,
1111 build_int_cst (niter_type
, 1), bits
);
1112 s
= fold_binary_to_constant (RSHIFT_EXPR
, niter_type
, s
, bits
);
1114 if (!exit_must_be_taken
)
1116 /* If we cannot assume that the exit is taken eventually, record the
1117 assumptions for divisibility of c. */
1118 assumption
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, c
, d
);
1119 assumption
= fold_build2 (EQ_EXPR
, boolean_type_node
,
1120 assumption
, build_int_cst (niter_type
, 0));
1121 if (!integer_nonzerop (assumption
))
1122 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1123 niter
->assumptions
, assumption
);
1126 c
= fold_build2 (EXACT_DIV_EXPR
, niter_type
, c
, d
);
1127 if (integer_onep (s
))
1133 tmp
= fold_build2 (MULT_EXPR
, niter_type
, c
, inverse (s
, bound
));
1134 niter
->niter
= fold_build2 (BIT_AND_EXPR
, niter_type
, tmp
, bound
);
1139 /* Checks whether we can determine the final value of the control variable
1140 of the loop with ending condition IV0 < IV1 (computed in TYPE).
1141 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
1142 of the step. The assumptions necessary to ensure that the computation
1143 of the final value does not overflow are recorded in NITER. If we
1144 find the final value, we adjust DELTA and return TRUE. Otherwise
1145 we return false. BNDS bounds the value of IV1->base - IV0->base,
1146 and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
1147 true if we know that the exit must be taken eventually. */
1150 number_of_iterations_lt_to_ne (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1151 class tree_niter_desc
*niter
,
1152 tree
*delta
, tree step
,
1153 bool exit_must_be_taken
, bounds
*bnds
)
1155 tree niter_type
= TREE_TYPE (step
);
1156 tree mod
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, *delta
, step
);
1159 tree assumption
= boolean_true_node
, bound
, noloop
;
1160 bool ret
= false, fv_comp_no_overflow
;
1162 if (POINTER_TYPE_P (type
))
1165 if (TREE_CODE (mod
) != INTEGER_CST
)
1167 if (integer_nonzerop (mod
))
1168 mod
= fold_build2 (MINUS_EXPR
, niter_type
, step
, mod
);
1169 tmod
= fold_convert (type1
, mod
);
1172 wi::to_mpz (wi::to_wide (mod
), mmod
, UNSIGNED
);
1173 mpz_neg (mmod
, mmod
);
1175 /* If the induction variable does not overflow and the exit is taken,
1176 then the computation of the final value does not overflow. This is
1177 also obviously the case if the new final value is equal to the
1178 current one. Finally, we postulate this for pointer type variables,
1179 as the code cannot rely on the object to that the pointer points being
1180 placed at the end of the address space (and more pragmatically,
1181 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
1182 if (integer_zerop (mod
) || POINTER_TYPE_P (type
))
1183 fv_comp_no_overflow
= true;
1184 else if (!exit_must_be_taken
)
1185 fv_comp_no_overflow
= false;
1187 fv_comp_no_overflow
=
1188 (iv0
->no_overflow
&& integer_nonzerop (iv0
->step
))
1189 || (iv1
->no_overflow
&& integer_nonzerop (iv1
->step
));
1191 if (integer_nonzerop (iv0
->step
))
1193 /* The final value of the iv is iv1->base + MOD, assuming that this
1194 computation does not overflow, and that
1195 iv0->base <= iv1->base + MOD. */
1196 if (!fv_comp_no_overflow
)
1198 bound
= fold_build2 (MINUS_EXPR
, type1
,
1199 TYPE_MAX_VALUE (type1
), tmod
);
1200 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
1202 if (integer_zerop (assumption
))
1205 if (mpz_cmp (mmod
, bnds
->below
) < 0)
1206 noloop
= boolean_false_node
;
1207 else if (POINTER_TYPE_P (type
))
1208 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
1210 fold_build_pointer_plus (iv1
->base
, tmod
));
1212 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
1214 fold_build2 (PLUS_EXPR
, type1
,
1219 /* The final value of the iv is iv0->base - MOD, assuming that this
1220 computation does not overflow, and that
1221 iv0->base - MOD <= iv1->base. */
1222 if (!fv_comp_no_overflow
)
1224 bound
= fold_build2 (PLUS_EXPR
, type1
,
1225 TYPE_MIN_VALUE (type1
), tmod
);
1226 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
1228 if (integer_zerop (assumption
))
1231 if (mpz_cmp (mmod
, bnds
->below
) < 0)
1232 noloop
= boolean_false_node
;
1233 else if (POINTER_TYPE_P (type
))
1234 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
1235 fold_build_pointer_plus (iv0
->base
,
1236 fold_build1 (NEGATE_EXPR
,
1240 noloop
= fold_build2 (GT_EXPR
, boolean_type_node
,
1241 fold_build2 (MINUS_EXPR
, type1
,
1246 if (!integer_nonzerop (assumption
))
1247 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1250 if (!integer_zerop (noloop
))
1251 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1254 bounds_add (bnds
, wi::to_widest (mod
), type
);
1255 *delta
= fold_build2 (PLUS_EXPR
, niter_type
, *delta
, mod
);
1263 /* Add assertions to NITER that ensure that the control variable of the loop
1264 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
1265 are TYPE. Returns false if we can prove that there is an overflow, true
1266 otherwise. STEP is the absolute value of the step. */
1269 assert_no_overflow_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1270 class tree_niter_desc
*niter
, tree step
)
1272 tree bound
, d
, assumption
, diff
;
1273 tree niter_type
= TREE_TYPE (step
);
1275 if (integer_nonzerop (iv0
->step
))
1277 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
1278 if (iv0
->no_overflow
)
1281 /* If iv0->base is a constant, we can determine the last value before
1282 overflow precisely; otherwise we conservatively assume
1285 if (TREE_CODE (iv0
->base
) == INTEGER_CST
)
1287 d
= fold_build2 (MINUS_EXPR
, niter_type
,
1288 fold_convert (niter_type
, TYPE_MAX_VALUE (type
)),
1289 fold_convert (niter_type
, iv0
->base
));
1290 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
1293 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
1294 build_int_cst (niter_type
, 1));
1295 bound
= fold_build2 (MINUS_EXPR
, type
,
1296 TYPE_MAX_VALUE (type
), fold_convert (type
, diff
));
1297 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
1302 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
1303 if (iv1
->no_overflow
)
1306 if (TREE_CODE (iv1
->base
) == INTEGER_CST
)
1308 d
= fold_build2 (MINUS_EXPR
, niter_type
,
1309 fold_convert (niter_type
, iv1
->base
),
1310 fold_convert (niter_type
, TYPE_MIN_VALUE (type
)));
1311 diff
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, d
, step
);
1314 diff
= fold_build2 (MINUS_EXPR
, niter_type
, step
,
1315 build_int_cst (niter_type
, 1));
1316 bound
= fold_build2 (PLUS_EXPR
, type
,
1317 TYPE_MIN_VALUE (type
), fold_convert (type
, diff
));
1318 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
1322 if (integer_zerop (assumption
))
1324 if (!integer_nonzerop (assumption
))
1325 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1326 niter
->assumptions
, assumption
);
1328 iv0
->no_overflow
= true;
1329 iv1
->no_overflow
= true;
1333 /* Add an assumption to NITER that a loop whose ending condition
1334 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
1335 bounds the value of IV1->base - IV0->base. */
1338 assert_loop_rolls_lt (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
1339 class tree_niter_desc
*niter
, bounds
*bnds
)
1341 tree assumption
= boolean_true_node
, bound
, diff
;
1342 tree mbz
, mbzl
, mbzr
, type1
;
1343 bool rolls_p
, no_overflow_p
;
1347 /* We are going to compute the number of iterations as
1348 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
1349 variant of TYPE. This formula only works if
1351 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
1353 (where MAX is the maximum value of the unsigned variant of TYPE, and
1354 the computations in this formula are performed in full precision,
1355 i.e., without overflows).
1357 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
1358 we have a condition of the form iv0->base - step < iv1->base before the loop,
1359 and for loops iv0->base < iv1->base - step * i the condition
1360 iv0->base < iv1->base + step, due to loop header copying, which enable us
1361 to prove the lower bound.
1363 The upper bound is more complicated. Unless the expressions for initial
1364 and final value themselves contain enough information, we usually cannot
1365 derive it from the context. */
1367 /* First check whether the answer does not follow from the bounds we gathered
1369 if (integer_nonzerop (iv0
->step
))
1370 dstep
= wi::to_widest (iv0
->step
);
1373 dstep
= wi::sext (wi::to_widest (iv1
->step
), TYPE_PRECISION (type
));
1378 wi::to_mpz (dstep
, mstep
, UNSIGNED
);
1379 mpz_neg (mstep
, mstep
);
1380 mpz_add_ui (mstep
, mstep
, 1);
1382 rolls_p
= mpz_cmp (mstep
, bnds
->below
) <= 0;
1385 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type
)), max
, UNSIGNED
);
1386 mpz_add (max
, max
, mstep
);
1387 no_overflow_p
= (mpz_cmp (bnds
->up
, max
) <= 0
1388 /* For pointers, only values lying inside a single object
1389 can be compared or manipulated by pointer arithmetics.
1390 Gcc in general does not allow or handle objects larger
1391 than half of the address space, hence the upper bound
1392 is satisfied for pointers. */
1393 || POINTER_TYPE_P (type
));
1397 if (rolls_p
&& no_overflow_p
)
1401 if (POINTER_TYPE_P (type
))
1404 /* Now the hard part; we must formulate the assumption(s) as expressions, and
1405 we must be careful not to introduce overflow. */
1407 if (integer_nonzerop (iv0
->step
))
1409 diff
= fold_build2 (MINUS_EXPR
, type1
,
1410 iv0
->step
, build_int_cst (type1
, 1));
1412 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
1413 0 address never belongs to any object, we can assume this for
1415 if (!POINTER_TYPE_P (type
))
1417 bound
= fold_build2 (PLUS_EXPR
, type1
,
1418 TYPE_MIN_VALUE (type
), diff
);
1419 assumption
= fold_build2 (GE_EXPR
, boolean_type_node
,
1423 /* And then we can compute iv0->base - diff, and compare it with
1425 mbzl
= fold_build2 (MINUS_EXPR
, type1
,
1426 fold_convert (type1
, iv0
->base
), diff
);
1427 mbzr
= fold_convert (type1
, iv1
->base
);
1431 diff
= fold_build2 (PLUS_EXPR
, type1
,
1432 iv1
->step
, build_int_cst (type1
, 1));
1434 if (!POINTER_TYPE_P (type
))
1436 bound
= fold_build2 (PLUS_EXPR
, type1
,
1437 TYPE_MAX_VALUE (type
), diff
);
1438 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
1442 mbzl
= fold_convert (type1
, iv0
->base
);
1443 mbzr
= fold_build2 (MINUS_EXPR
, type1
,
1444 fold_convert (type1
, iv1
->base
), diff
);
1447 if (!integer_nonzerop (assumption
))
1448 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1449 niter
->assumptions
, assumption
);
1452 mbz
= fold_build2 (GT_EXPR
, boolean_type_node
, mbzl
, mbzr
);
1453 niter
->may_be_zero
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1454 niter
->may_be_zero
, mbz
);
1458 /* Determines number of iterations of loop whose ending condition
1459 is IV0 < IV1. TYPE is the type of the iv. The number of
1460 iterations is stored to NITER. BNDS bounds the difference
1461 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
1462 that the exit must be taken eventually. */
1465 number_of_iterations_lt (class loop
*loop
, tree type
, affine_iv
*iv0
,
1466 affine_iv
*iv1
, class tree_niter_desc
*niter
,
1467 bool exit_must_be_taken
, bounds
*bnds
)
1469 tree niter_type
= unsigned_type_for (type
);
1470 tree delta
, step
, s
;
1473 if (integer_nonzerop (iv0
->step
))
1475 niter
->control
= *iv0
;
1476 niter
->cmp
= LT_EXPR
;
1477 niter
->bound
= iv1
->base
;
1481 niter
->control
= *iv1
;
1482 niter
->cmp
= GT_EXPR
;
1483 niter
->bound
= iv0
->base
;
1486 delta
= fold_build2 (MINUS_EXPR
, niter_type
,
1487 fold_convert (niter_type
, iv1
->base
),
1488 fold_convert (niter_type
, iv0
->base
));
1490 /* First handle the special case that the step is +-1. */
1491 if ((integer_onep (iv0
->step
) && integer_zerop (iv1
->step
))
1492 || (integer_all_onesp (iv1
->step
) && integer_zerop (iv0
->step
)))
1494 /* for (i = iv0->base; i < iv1->base; i++)
1498 for (i = iv1->base; i > iv0->base; i--).
1500 In both cases # of iterations is iv1->base - iv0->base, assuming that
1501 iv1->base >= iv0->base.
1503 First try to derive a lower bound on the value of
1504 iv1->base - iv0->base, computed in full precision. If the difference
1505 is nonnegative, we are done, otherwise we must record the
1508 if (mpz_sgn (bnds
->below
) < 0)
1509 niter
->may_be_zero
= fold_build2 (LT_EXPR
, boolean_type_node
,
1510 iv1
->base
, iv0
->base
);
1511 niter
->niter
= delta
;
1512 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, bnds
->up
, false),
1513 TYPE_SIGN (niter_type
));
1514 niter
->control
.no_overflow
= true;
1518 if (integer_nonzerop (iv0
->step
))
1519 step
= fold_convert (niter_type
, iv0
->step
);
1521 step
= fold_convert (niter_type
,
1522 fold_build1 (NEGATE_EXPR
, type
, iv1
->step
));
1524 /* If we can determine the final value of the control iv exactly, we can
1525 transform the condition to != comparison. In particular, this will be
1526 the case if DELTA is constant. */
1527 if (number_of_iterations_lt_to_ne (type
, iv0
, iv1
, niter
, &delta
, step
,
1528 exit_must_be_taken
, bnds
))
1532 zps
.base
= build_int_cst (niter_type
, 0);
1534 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1535 zps does not overflow. */
1536 zps
.no_overflow
= true;
1538 return number_of_iterations_ne (loop
, type
, &zps
,
1539 delta
, niter
, true, bnds
);
1542 /* Make sure that the control iv does not overflow. */
1543 if (!assert_no_overflow_lt (type
, iv0
, iv1
, niter
, step
))
1546 /* We determine the number of iterations as (delta + step - 1) / step. For
1547 this to work, we must know that iv1->base >= iv0->base - step + 1,
1548 otherwise the loop does not roll. */
1549 assert_loop_rolls_lt (type
, iv0
, iv1
, niter
, bnds
);
1551 s
= fold_build2 (MINUS_EXPR
, niter_type
,
1552 step
, build_int_cst (niter_type
, 1));
1553 delta
= fold_build2 (PLUS_EXPR
, niter_type
, delta
, s
);
1554 niter
->niter
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, delta
, step
);
1558 wi::to_mpz (wi::to_wide (step
), mstep
, UNSIGNED
);
1559 mpz_add (tmp
, bnds
->up
, mstep
);
1560 mpz_sub_ui (tmp
, tmp
, 1);
1561 mpz_fdiv_q (tmp
, tmp
, mstep
);
1562 niter
->max
= widest_int::from (wi::from_mpz (niter_type
, tmp
, false),
1563 TYPE_SIGN (niter_type
));
1570 /* Determines number of iterations of loop whose ending condition
1571 is IV0 <= IV1. TYPE is the type of the iv. The number of
1572 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
1573 we know that this condition must eventually become false (we derived this
1574 earlier, and possibly set NITER->assumptions to make sure this
1575 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1578 number_of_iterations_le (class loop
*loop
, tree type
, affine_iv
*iv0
,
1579 affine_iv
*iv1
, class tree_niter_desc
*niter
,
1580 bool exit_must_be_taken
, bounds
*bnds
)
1584 if (POINTER_TYPE_P (type
))
1587 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1588 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1589 value of the type. This we must know anyway, since if it is
1590 equal to this value, the loop rolls forever. We do not check
1591 this condition for pointer type ivs, as the code cannot rely on
1592 the object to that the pointer points being placed at the end of
1593 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1594 not defined for pointers). */
1596 if (!exit_must_be_taken
&& !POINTER_TYPE_P (type
))
1598 if (integer_nonzerop (iv0
->step
))
1599 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1600 iv1
->base
, TYPE_MAX_VALUE (type
));
1602 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
1603 iv0
->base
, TYPE_MIN_VALUE (type
));
1605 if (integer_zerop (assumption
))
1607 if (!integer_nonzerop (assumption
))
1608 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1609 niter
->assumptions
, assumption
);
1612 if (integer_nonzerop (iv0
->step
))
1614 if (POINTER_TYPE_P (type
))
1615 iv1
->base
= fold_build_pointer_plus_hwi (iv1
->base
, 1);
1617 iv1
->base
= fold_build2 (PLUS_EXPR
, type1
, iv1
->base
,
1618 build_int_cst (type1
, 1));
1620 else if (POINTER_TYPE_P (type
))
1621 iv0
->base
= fold_build_pointer_plus_hwi (iv0
->base
, -1);
1623 iv0
->base
= fold_build2 (MINUS_EXPR
, type1
,
1624 iv0
->base
, build_int_cst (type1
, 1));
1626 bounds_add (bnds
, 1, type1
);
1628 return number_of_iterations_lt (loop
, type
, iv0
, iv1
, niter
, exit_must_be_taken
,
1632 /* Dumps description of affine induction variable IV to FILE. */
1635 dump_affine_iv (FILE *file
, affine_iv
*iv
)
1637 if (!integer_zerop (iv
->step
))
1638 fprintf (file
, "[");
1640 print_generic_expr (dump_file
, iv
->base
, TDF_SLIM
);
1642 if (!integer_zerop (iv
->step
))
1644 fprintf (file
, ", + , ");
1645 print_generic_expr (dump_file
, iv
->step
, TDF_SLIM
);
1646 fprintf (file
, "]%s", iv
->no_overflow
? "(no_overflow)" : "");
1650 /* Given exit condition IV0 CODE IV1 in TYPE, this function adjusts
1651 the condition for loop-until-wrap cases. For example:
1652 (unsigned){8, -1}_loop < 10 => {0, 1} != 9
1653 10 < (unsigned){0, max - 7}_loop => {0, 1} != 8
1654 Return true if condition is successfully adjusted. */
1657 adjust_cond_for_loop_until_wrap (tree type
, affine_iv
*iv0
, tree_code
*code
,
1660 /* Only support simple cases for the moment. */
1661 if (TREE_CODE (iv0
->base
) != INTEGER_CST
1662 || TREE_CODE (iv1
->base
) != INTEGER_CST
)
1665 tree niter_type
= unsigned_type_for (type
), high
, low
;
1666 /* Case: i-- < 10. */
1667 if (integer_zerop (iv1
->step
))
1669 /* TODO: Should handle case in which abs(step) != 1. */
1670 if (!integer_minus_onep (iv0
->step
))
1672 /* Give up on infinite loop. */
1673 if (*code
== LE_EXPR
1674 && tree_int_cst_equal (iv1
->base
, TYPE_MAX_VALUE (type
)))
1676 high
= fold_build2 (PLUS_EXPR
, niter_type
,
1677 fold_convert (niter_type
, iv0
->base
),
1678 build_int_cst (niter_type
, 1));
1679 low
= fold_convert (niter_type
, TYPE_MIN_VALUE (type
));
1681 else if (integer_zerop (iv0
->step
))
1683 /* TODO: Should handle case in which abs(step) != 1. */
1684 if (!integer_onep (iv1
->step
))
1686 /* Give up on infinite loop. */
1687 if (*code
== LE_EXPR
1688 && tree_int_cst_equal (iv0
->base
, TYPE_MIN_VALUE (type
)))
1690 high
= fold_convert (niter_type
, TYPE_MAX_VALUE (type
));
1691 low
= fold_build2 (MINUS_EXPR
, niter_type
,
1692 fold_convert (niter_type
, iv1
->base
),
1693 build_int_cst (niter_type
, 1));
1699 iv0
->step
= fold_convert (niter_type
, integer_one_node
);
1701 iv1
->step
= build_int_cst (niter_type
, 0);
1706 /* Determine the number of iterations according to condition (for staying
1707 inside loop) which compares two induction variables using comparison
1708 operator CODE. The induction variable on left side of the comparison
1709 is IV0, the right-hand side is IV1. Both induction variables must have
1710 type TYPE, which must be an integer or pointer type. The steps of the
1711 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1713 LOOP is the loop whose number of iterations we are determining.
1715 ONLY_EXIT is true if we are sure this is the only way the loop could be
1716 exited (including possibly non-returning function calls, exceptions, etc.)
1717 -- in this case we can use the information whether the control induction
1718 variables can overflow or not in a more efficient way.
1720 if EVERY_ITERATION is true, we know the test is executed on every iteration.
1722 The results (number of iterations and assumptions as described in
1723 comments at class tree_niter_desc in tree-ssa-loop.h) are stored to NITER.
1724 Returns false if it fails to determine number of iterations, true if it
1725 was determined (possibly with some assumptions). */
1728 number_of_iterations_cond (class loop
*loop
,
1729 tree type
, affine_iv
*iv0
, enum tree_code code
,
1730 affine_iv
*iv1
, class tree_niter_desc
*niter
,
1731 bool only_exit
, bool every_iteration
)
1733 bool exit_must_be_taken
= false, ret
;
1736 /* If the test is not executed every iteration, wrapping may make the test
1738 TODO: the overflow case can be still used as unreliable estimate of upper
1739 bound. But we have no API to pass it down to number of iterations code
1740 and, at present, it will not use it anyway. */
1741 if (!every_iteration
1742 && (!iv0
->no_overflow
|| !iv1
->no_overflow
1743 || code
== NE_EXPR
|| code
== EQ_EXPR
))
1746 /* The meaning of these assumptions is this:
1748 then the rest of information does not have to be valid
1749 if may_be_zero then the loop does not roll, even if
1751 niter
->assumptions
= boolean_true_node
;
1752 niter
->may_be_zero
= boolean_false_node
;
1753 niter
->niter
= NULL_TREE
;
1755 niter
->bound
= NULL_TREE
;
1756 niter
->cmp
= ERROR_MARK
;
1758 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1759 the control variable is on lhs. */
1760 if (code
== GE_EXPR
|| code
== GT_EXPR
1761 || (code
== NE_EXPR
&& integer_zerop (iv0
->step
)))
1763 std::swap (iv0
, iv1
);
1764 code
= swap_tree_comparison (code
);
1767 if (POINTER_TYPE_P (type
))
1769 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1770 to the same object. If they do, the control variable cannot wrap
1771 (as wrap around the bounds of memory will never return a pointer
1772 that would be guaranteed to point to the same object, even if we
1773 avoid undefined behavior by casting to size_t and back). */
1774 iv0
->no_overflow
= true;
1775 iv1
->no_overflow
= true;
1778 /* If the control induction variable does not overflow and the only exit
1779 from the loop is the one that we analyze, we know it must be taken
1783 if (!integer_zerop (iv0
->step
) && iv0
->no_overflow
)
1784 exit_must_be_taken
= true;
1785 else if (!integer_zerop (iv1
->step
) && iv1
->no_overflow
)
1786 exit_must_be_taken
= true;
1789 /* We can handle cases which neither of the sides of the comparison is
1792 {iv0.base, iv0.step} cmp_code {iv1.base, iv1.step}
1794 {iv0.base, iv0.step - iv1.step} cmp_code {iv1.base, 0}
1796 provided that either below condition is satisfied:
1798 a) the test is NE_EXPR;
1799 b) iv0.step - iv1.step is integer and iv0/iv1 don't overflow.
1801 This rarely occurs in practice, but it is simple enough to manage. */
1802 if (!integer_zerop (iv0
->step
) && !integer_zerop (iv1
->step
))
1804 tree step_type
= POINTER_TYPE_P (type
) ? sizetype
: type
;
1805 tree step
= fold_binary_to_constant (MINUS_EXPR
, step_type
,
1806 iv0
->step
, iv1
->step
);
1808 /* No need to check sign of the new step since below code takes care
1811 && (TREE_CODE (step
) != INTEGER_CST
1812 || !iv0
->no_overflow
|| !iv1
->no_overflow
))
1816 if (!POINTER_TYPE_P (type
))
1817 iv0
->no_overflow
= false;
1819 iv1
->step
= build_int_cst (step_type
, 0);
1820 iv1
->no_overflow
= true;
1823 /* If the result of the comparison is a constant, the loop is weird. More
1824 precise handling would be possible, but the situation is not common enough
1825 to waste time on it. */
1826 if (integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
))
1829 /* If the loop exits immediately, there is nothing to do. */
1830 tree tem
= fold_binary (code
, boolean_type_node
, iv0
->base
, iv1
->base
);
1831 if (tem
&& integer_zerop (tem
))
1833 if (!every_iteration
)
1835 niter
->niter
= build_int_cst (unsigned_type_for (type
), 0);
1840 /* Handle special case loops: while (i-- < 10) and while (10 < i++) by
1841 adjusting iv0, iv1 and code. */
1843 && (tree_int_cst_sign_bit (iv0
->step
)
1844 || (!integer_zerop (iv1
->step
)
1845 && !tree_int_cst_sign_bit (iv1
->step
)))
1846 && !adjust_cond_for_loop_until_wrap (type
, iv0
, &code
, iv1
))
1849 /* OK, now we know we have a senseful loop. Handle several cases, depending
1850 on what comparison operator is used. */
1851 bound_difference (loop
, iv1
->base
, iv0
->base
, &bnds
);
1853 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1856 "Analyzing # of iterations of loop %d\n", loop
->num
);
1858 fprintf (dump_file
, " exit condition ");
1859 dump_affine_iv (dump_file
, iv0
);
1860 fprintf (dump_file
, " %s ",
1861 code
== NE_EXPR
? "!="
1862 : code
== LT_EXPR
? "<"
1864 dump_affine_iv (dump_file
, iv1
);
1865 fprintf (dump_file
, "\n");
1867 fprintf (dump_file
, " bounds on difference of bases: ");
1868 mpz_out_str (dump_file
, 10, bnds
.below
);
1869 fprintf (dump_file
, " ... ");
1870 mpz_out_str (dump_file
, 10, bnds
.up
);
1871 fprintf (dump_file
, "\n");
1877 gcc_assert (integer_zerop (iv1
->step
));
1878 ret
= number_of_iterations_ne (loop
, type
, iv0
, iv1
->base
, niter
,
1879 exit_must_be_taken
, &bnds
);
1883 ret
= number_of_iterations_lt (loop
, type
, iv0
, iv1
, niter
,
1884 exit_must_be_taken
, &bnds
);
1888 ret
= number_of_iterations_le (loop
, type
, iv0
, iv1
, niter
,
1889 exit_must_be_taken
, &bnds
);
1896 mpz_clear (bnds
.up
);
1897 mpz_clear (bnds
.below
);
1899 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1903 fprintf (dump_file
, " result:\n");
1904 if (!integer_nonzerop (niter
->assumptions
))
1906 fprintf (dump_file
, " under assumptions ");
1907 print_generic_expr (dump_file
, niter
->assumptions
, TDF_SLIM
);
1908 fprintf (dump_file
, "\n");
1911 if (!integer_zerop (niter
->may_be_zero
))
1913 fprintf (dump_file
, " zero if ");
1914 print_generic_expr (dump_file
, niter
->may_be_zero
, TDF_SLIM
);
1915 fprintf (dump_file
, "\n");
1918 fprintf (dump_file
, " # of iterations ");
1919 print_generic_expr (dump_file
, niter
->niter
, TDF_SLIM
);
1920 fprintf (dump_file
, ", bounded by ");
1921 print_decu (niter
->max
, dump_file
);
1922 fprintf (dump_file
, "\n");
1925 fprintf (dump_file
, " failed\n\n");
1930 /* Substitute NEW_TREE for OLD in EXPR and fold the result.
1931 If VALUEIZE is non-NULL then OLD and NEW_TREE are ignored and instead
1932 all SSA names are replaced with the result of calling the VALUEIZE
1933 function with the SSA name as argument. */
1936 simplify_replace_tree (tree expr
, tree old
, tree new_tree
,
1937 tree (*valueize
) (tree
, void*), void *context
,
1941 tree ret
= NULL_TREE
, e
, se
;
1946 /* Do not bother to replace constants. */
1947 if (CONSTANT_CLASS_P (expr
))
1952 if (TREE_CODE (expr
) == SSA_NAME
)
1954 new_tree
= valueize (expr
, context
);
1955 if (new_tree
!= expr
)
1959 else if (expr
== old
1960 || operand_equal_p (expr
, old
, 0))
1961 return unshare_expr (new_tree
);
1966 n
= TREE_OPERAND_LENGTH (expr
);
1967 for (i
= 0; i
< n
; i
++)
1969 e
= TREE_OPERAND (expr
, i
);
1970 se
= simplify_replace_tree (e
, old
, new_tree
, valueize
, context
, do_fold
);
1975 ret
= copy_node (expr
);
1977 TREE_OPERAND (ret
, i
) = se
;
1980 return (ret
? (do_fold
? fold (ret
) : ret
) : expr
);
1983 /* Expand definitions of ssa names in EXPR as long as they are simple
1984 enough, and return the new expression. If STOP is specified, stop
1985 expanding if EXPR equals to it. */
1988 expand_simple_operations (tree expr
, tree stop
, hash_map
<tree
, tree
> &cache
)
1991 tree ret
= NULL_TREE
, e
, ee
, e1
;
1992 enum tree_code code
;
1995 if (expr
== NULL_TREE
)
1998 if (is_gimple_min_invariant (expr
))
2001 code
= TREE_CODE (expr
);
2002 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
2004 n
= TREE_OPERAND_LENGTH (expr
);
2005 for (i
= 0; i
< n
; i
++)
2007 e
= TREE_OPERAND (expr
, i
);
2008 /* SCEV analysis feeds us with a proper expression
2009 graph matching the SSA graph. Avoid turning it
2010 into a tree here, thus handle tree sharing
2012 ??? The SSA walk below still turns the SSA graph
2013 into a tree but until we find a testcase do not
2014 introduce additional tree sharing here. */
2016 tree
&cee
= cache
.get_or_insert (e
, &existed_p
);
2022 ee
= expand_simple_operations (e
, stop
, cache
);
2024 *cache
.get (e
) = ee
;
2030 ret
= copy_node (expr
);
2032 TREE_OPERAND (ret
, i
) = ee
;
2038 fold_defer_overflow_warnings ();
2040 fold_undefer_and_ignore_overflow_warnings ();
2044 /* Stop if it's not ssa name or the one we don't want to expand. */
2045 if (TREE_CODE (expr
) != SSA_NAME
|| expr
== stop
)
2048 stmt
= SSA_NAME_DEF_STMT (expr
);
2049 if (gimple_code (stmt
) == GIMPLE_PHI
)
2051 basic_block src
, dest
;
2053 if (gimple_phi_num_args (stmt
) != 1)
2055 e
= PHI_ARG_DEF (stmt
, 0);
2057 /* Avoid propagating through loop exit phi nodes, which
2058 could break loop-closed SSA form restrictions. */
2059 dest
= gimple_bb (stmt
);
2060 src
= single_pred (dest
);
2061 if (TREE_CODE (e
) == SSA_NAME
2062 && src
->loop_father
!= dest
->loop_father
)
2065 return expand_simple_operations (e
, stop
, cache
);
2067 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2070 /* Avoid expanding to expressions that contain SSA names that need
2071 to take part in abnormal coalescing. */
2073 FOR_EACH_SSA_TREE_OPERAND (e
, stmt
, iter
, SSA_OP_USE
)
2074 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (e
))
2077 e
= gimple_assign_rhs1 (stmt
);
2078 code
= gimple_assign_rhs_code (stmt
);
2079 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
)
2081 if (is_gimple_min_invariant (e
))
2084 if (code
== SSA_NAME
)
2085 return expand_simple_operations (e
, stop
, cache
);
2086 else if (code
== ADDR_EXPR
)
2089 tree base
= get_addr_base_and_unit_offset (TREE_OPERAND (e
, 0),
2092 && TREE_CODE (base
) == MEM_REF
)
2094 ee
= expand_simple_operations (TREE_OPERAND (base
, 0), stop
,
2096 return fold_build2 (POINTER_PLUS_EXPR
, TREE_TYPE (expr
), ee
,
2097 wide_int_to_tree (sizetype
,
2098 mem_ref_offset (base
)
2109 /* Casts are simple. */
2110 ee
= expand_simple_operations (e
, stop
, cache
);
2111 return fold_build1 (code
, TREE_TYPE (expr
), ee
);
2115 if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (expr
))
2116 && TYPE_OVERFLOW_TRAPS (TREE_TYPE (expr
)))
2119 case POINTER_PLUS_EXPR
:
2120 /* And increments and decrements by a constant are simple. */
2121 e1
= gimple_assign_rhs2 (stmt
);
2122 if (!is_gimple_min_invariant (e1
))
2125 ee
= expand_simple_operations (e
, stop
, cache
);
2126 return fold_build2 (code
, TREE_TYPE (expr
), ee
, e1
);
2134 expand_simple_operations (tree expr
, tree stop
)
2136 hash_map
<tree
, tree
> cache
;
2137 return expand_simple_operations (expr
, stop
, cache
);
2140 /* Tries to simplify EXPR using the condition COND. Returns the simplified
2141 expression (or EXPR unchanged, if no simplification was possible). */
2144 tree_simplify_using_condition_1 (tree cond
, tree expr
)
2147 tree e
, e0
, e1
, e2
, notcond
;
2148 enum tree_code code
= TREE_CODE (expr
);
2150 if (code
== INTEGER_CST
)
2153 if (code
== TRUTH_OR_EXPR
2154 || code
== TRUTH_AND_EXPR
2155 || code
== COND_EXPR
)
2159 e0
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 0));
2160 if (TREE_OPERAND (expr
, 0) != e0
)
2163 e1
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 1));
2164 if (TREE_OPERAND (expr
, 1) != e1
)
2167 if (code
== COND_EXPR
)
2169 e2
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 2));
2170 if (TREE_OPERAND (expr
, 2) != e2
)
2178 if (code
== COND_EXPR
)
2179 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
2181 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
2187 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
2188 propagation, and vice versa. Fold does not handle this, since it is
2189 considered too expensive. */
2190 if (TREE_CODE (cond
) == EQ_EXPR
)
2192 e0
= TREE_OPERAND (cond
, 0);
2193 e1
= TREE_OPERAND (cond
, 1);
2195 /* We know that e0 == e1. Check whether we cannot simplify expr
2197 e
= simplify_replace_tree (expr
, e0
, e1
);
2198 if (integer_zerop (e
) || integer_nonzerop (e
))
2201 e
= simplify_replace_tree (expr
, e1
, e0
);
2202 if (integer_zerop (e
) || integer_nonzerop (e
))
2205 if (TREE_CODE (expr
) == EQ_EXPR
)
2207 e0
= TREE_OPERAND (expr
, 0);
2208 e1
= TREE_OPERAND (expr
, 1);
2210 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
2211 e
= simplify_replace_tree (cond
, e0
, e1
);
2212 if (integer_zerop (e
))
2214 e
= simplify_replace_tree (cond
, e1
, e0
);
2215 if (integer_zerop (e
))
2218 if (TREE_CODE (expr
) == NE_EXPR
)
2220 e0
= TREE_OPERAND (expr
, 0);
2221 e1
= TREE_OPERAND (expr
, 1);
2223 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
2224 e
= simplify_replace_tree (cond
, e0
, e1
);
2225 if (integer_zerop (e
))
2226 return boolean_true_node
;
2227 e
= simplify_replace_tree (cond
, e1
, e0
);
2228 if (integer_zerop (e
))
2229 return boolean_true_node
;
2232 /* Check whether COND ==> EXPR. */
2233 notcond
= invert_truthvalue (cond
);
2234 e
= fold_binary (TRUTH_OR_EXPR
, boolean_type_node
, notcond
, expr
);
2235 if (e
&& integer_nonzerop (e
))
2238 /* Check whether COND ==> not EXPR. */
2239 e
= fold_binary (TRUTH_AND_EXPR
, boolean_type_node
, cond
, expr
);
2240 if (e
&& integer_zerop (e
))
2246 /* Tries to simplify EXPR using the condition COND. Returns the simplified
2247 expression (or EXPR unchanged, if no simplification was possible).
2248 Wrapper around tree_simplify_using_condition_1 that ensures that chains
2249 of simple operations in definitions of ssa names in COND are expanded,
2250 so that things like casts or incrementing the value of the bound before
2251 the loop do not cause us to fail. */
2254 tree_simplify_using_condition (tree cond
, tree expr
)
2256 cond
= expand_simple_operations (cond
);
2258 return tree_simplify_using_condition_1 (cond
, expr
);
2261 /* Tries to simplify EXPR using the conditions on entry to LOOP.
2262 Returns the simplified expression (or EXPR unchanged, if no
2263 simplification was possible). */
2266 simplify_using_initial_conditions (class loop
*loop
, tree expr
)
2271 tree cond
, expanded
, backup
;
2274 if (TREE_CODE (expr
) == INTEGER_CST
)
2277 backup
= expanded
= expand_simple_operations (expr
);
2279 /* Limit walking the dominators to avoid quadraticness in
2280 the number of BBs times the number of loops in degenerate
2282 for (bb
= loop
->header
;
2283 bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
) && cnt
< MAX_DOMINATORS_TO_WALK
;
2284 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
2286 if (!single_pred_p (bb
))
2288 e
= single_pred_edge (bb
);
2290 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
2293 stmt
= last_stmt (e
->src
);
2294 cond
= fold_build2 (gimple_cond_code (stmt
),
2296 gimple_cond_lhs (stmt
),
2297 gimple_cond_rhs (stmt
));
2298 if (e
->flags
& EDGE_FALSE_VALUE
)
2299 cond
= invert_truthvalue (cond
);
2300 expanded
= tree_simplify_using_condition (cond
, expanded
);
2301 /* Break if EXPR is simplified to const values. */
2303 && (integer_zerop (expanded
) || integer_nonzerop (expanded
)))
2309 /* Return the original expression if no simplification is done. */
2310 return operand_equal_p (backup
, expanded
, 0) ? expr
: expanded
;
2313 /* Tries to simplify EXPR using the evolutions of the loop invariants
2314 in the superloops of LOOP. Returns the simplified expression
2315 (or EXPR unchanged, if no simplification was possible). */
2318 simplify_using_outer_evolutions (class loop
*loop
, tree expr
)
2320 enum tree_code code
= TREE_CODE (expr
);
2324 if (is_gimple_min_invariant (expr
))
2327 if (code
== TRUTH_OR_EXPR
2328 || code
== TRUTH_AND_EXPR
2329 || code
== COND_EXPR
)
2333 e0
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 0));
2334 if (TREE_OPERAND (expr
, 0) != e0
)
2337 e1
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 1));
2338 if (TREE_OPERAND (expr
, 1) != e1
)
2341 if (code
== COND_EXPR
)
2343 e2
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 2));
2344 if (TREE_OPERAND (expr
, 2) != e2
)
2352 if (code
== COND_EXPR
)
2353 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
2355 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
2361 e
= instantiate_parameters (loop
, expr
);
2362 if (is_gimple_min_invariant (e
))
2368 /* Returns true if EXIT is the only possible exit from LOOP. */
2371 loop_only_exit_p (const class loop
*loop
, basic_block
*body
, const_edge exit
)
2373 gimple_stmt_iterator bsi
;
2376 if (exit
!= single_exit (loop
))
2379 for (i
= 0; i
< loop
->num_nodes
; i
++)
2380 for (bsi
= gsi_start_bb (body
[i
]); !gsi_end_p (bsi
); gsi_next (&bsi
))
2381 if (stmt_can_terminate_bb_p (gsi_stmt (bsi
)))
2387 /* Stores description of number of iterations of LOOP derived from
2388 EXIT (an exit edge of the LOOP) in NITER. Returns true if some useful
2389 information could be derived (and fields of NITER have meaning described
2390 in comments at class tree_niter_desc declaration), false otherwise.
2391 When EVERY_ITERATION is true, only tests that are known to be executed
2392 every iteration are considered (i.e. only test that alone bounds the loop).
2393 If AT_STMT is not NULL, this function stores LOOP's condition statement in
2394 it when returning true. */
2397 number_of_iterations_exit_assumptions (class loop
*loop
, edge exit
,
2398 class tree_niter_desc
*niter
,
2399 gcond
**at_stmt
, bool every_iteration
,
2406 enum tree_code code
;
2410 /* Nothing to analyze if the loop is known to be infinite. */
2411 if (loop_constraint_set_p (loop
, LOOP_C_INFINITE
))
2414 safe
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit
->src
);
2416 if (every_iteration
&& !safe
)
2419 niter
->assumptions
= boolean_false_node
;
2420 niter
->control
.base
= NULL_TREE
;
2421 niter
->control
.step
= NULL_TREE
;
2422 niter
->control
.no_overflow
= false;
2423 last
= last_stmt (exit
->src
);
2426 stmt
= dyn_cast
<gcond
*> (last
);
2430 /* We want the condition for staying inside loop. */
2431 code
= gimple_cond_code (stmt
);
2432 if (exit
->flags
& EDGE_TRUE_VALUE
)
2433 code
= invert_tree_comparison (code
, false);
2448 op0
= gimple_cond_lhs (stmt
);
2449 op1
= gimple_cond_rhs (stmt
);
2450 type
= TREE_TYPE (op0
);
2452 if (TREE_CODE (type
) != INTEGER_TYPE
2453 && !POINTER_TYPE_P (type
))
2456 tree iv0_niters
= NULL_TREE
;
2457 if (!simple_iv_with_niters (loop
, loop_containing_stmt (stmt
),
2458 op0
, &iv0
, safe
? &iv0_niters
: NULL
, false))
2459 return number_of_iterations_popcount (loop
, exit
, code
, niter
);
2460 tree iv1_niters
= NULL_TREE
;
2461 if (!simple_iv_with_niters (loop
, loop_containing_stmt (stmt
),
2462 op1
, &iv1
, safe
? &iv1_niters
: NULL
, false))
2464 /* Give up on complicated case. */
2465 if (iv0_niters
&& iv1_niters
)
2468 /* We don't want to see undefined signed overflow warnings while
2469 computing the number of iterations. */
2470 fold_defer_overflow_warnings ();
2472 iv0
.base
= expand_simple_operations (iv0
.base
);
2473 iv1
.base
= expand_simple_operations (iv1
.base
);
2474 bool body_from_caller
= true;
2477 body
= get_loop_body (loop
);
2478 body_from_caller
= false;
2480 bool only_exit_p
= loop_only_exit_p (loop
, body
, exit
);
2481 if (!body_from_caller
)
2483 if (!number_of_iterations_cond (loop
, type
, &iv0
, code
, &iv1
, niter
,
2486 fold_undefer_and_ignore_overflow_warnings ();
2490 /* Incorporate additional assumption implied by control iv. */
2491 tree iv_niters
= iv0_niters
? iv0_niters
: iv1_niters
;
2494 tree assumption
= fold_build2 (LE_EXPR
, boolean_type_node
, niter
->niter
,
2495 fold_convert (TREE_TYPE (niter
->niter
),
2498 if (!integer_nonzerop (assumption
))
2499 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
2500 niter
->assumptions
, assumption
);
2502 /* Refine upper bound if possible. */
2503 if (TREE_CODE (iv_niters
) == INTEGER_CST
2504 && niter
->max
> wi::to_widest (iv_niters
))
2505 niter
->max
= wi::to_widest (iv_niters
);
2508 /* There is no assumptions if the loop is known to be finite. */
2509 if (!integer_zerop (niter
->assumptions
)
2510 && loop_constraint_set_p (loop
, LOOP_C_FINITE
))
2511 niter
->assumptions
= boolean_true_node
;
2515 niter
->assumptions
= simplify_using_outer_evolutions (loop
,
2516 niter
->assumptions
);
2517 niter
->may_be_zero
= simplify_using_outer_evolutions (loop
,
2518 niter
->may_be_zero
);
2519 niter
->niter
= simplify_using_outer_evolutions (loop
, niter
->niter
);
2523 = simplify_using_initial_conditions (loop
,
2524 niter
->assumptions
);
2526 = simplify_using_initial_conditions (loop
,
2527 niter
->may_be_zero
);
2529 fold_undefer_and_ignore_overflow_warnings ();
2531 /* If NITER has simplified into a constant, update MAX. */
2532 if (TREE_CODE (niter
->niter
) == INTEGER_CST
)
2533 niter
->max
= wi::to_widest (niter
->niter
);
2538 return (!integer_zerop (niter
->assumptions
));
2542 /* Utility function to check if OP is defined by a stmt
2543 that is a val - 1. */
2546 ssa_defined_by_minus_one_stmt_p (tree op
, tree val
)
2549 return (TREE_CODE (op
) == SSA_NAME
2550 && (stmt
= SSA_NAME_DEF_STMT (op
))
2551 && is_gimple_assign (stmt
)
2552 && (gimple_assign_rhs_code (stmt
) == PLUS_EXPR
)
2553 && val
== gimple_assign_rhs1 (stmt
)
2554 && integer_minus_onep (gimple_assign_rhs2 (stmt
)));
2558 /* See if LOOP is a popcout implementation, determine NITER for the loop
2569 b_11 = PHI <b_5(D)(2), b_6(3)>
2577 OR we match copy-header version:
2584 b_11 = PHI <b_5(2), b_6(3)>
2594 If popcount pattern, update NITER accordingly.
2595 i.e., set NITER to __builtin_popcount (b)
2596 return true if we did, false otherwise.
2601 number_of_iterations_popcount (loop_p loop
, edge exit
,
2602 enum tree_code code
,
2603 class tree_niter_desc
*niter
)
2609 tree fn
= NULL_TREE
;
2611 /* Check loop terminating branch is like
2613 gimple
*stmt
= last_stmt (exit
->src
);
2615 || gimple_code (stmt
) != GIMPLE_COND
2617 || !integer_zerop (gimple_cond_rhs (stmt
))
2618 || TREE_CODE (gimple_cond_lhs (stmt
)) != SSA_NAME
)
2621 gimple
*and_stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt
));
2623 /* Depending on copy-header is performed, feeding PHI stmts might be in
2624 the loop header or loop latch, handle this. */
2625 if (gimple_code (and_stmt
) == GIMPLE_PHI
2626 && gimple_bb (and_stmt
) == loop
->header
2627 && gimple_phi_num_args (and_stmt
) == 2
2628 && (TREE_CODE (gimple_phi_arg_def (and_stmt
,
2629 loop_latch_edge (loop
)->dest_idx
))
2632 /* SSA used in exit condition is defined by PHI stmt
2633 b_11 = PHI <b_5(D)(2), b_6(3)>
2634 from the PHI stmt, get the and_stmt
2636 tree t
= gimple_phi_arg_def (and_stmt
, loop_latch_edge (loop
)->dest_idx
);
2637 and_stmt
= SSA_NAME_DEF_STMT (t
);
2641 /* Make sure it is indeed an and stmt (b_6 = _1 & b_11). */
2642 if (!is_gimple_assign (and_stmt
)
2643 || gimple_assign_rhs_code (and_stmt
) != BIT_AND_EXPR
)
2646 tree b_11
= gimple_assign_rhs1 (and_stmt
);
2647 tree _1
= gimple_assign_rhs2 (and_stmt
);
2649 /* Check that _1 is defined by _b11 + -1 (_1 = b_11 + -1).
2650 Also make sure that b_11 is the same in and_stmt and _1 defining stmt.
2651 Also canonicalize if _1 and _b11 are revrsed. */
2652 if (ssa_defined_by_minus_one_stmt_p (b_11
, _1
))
2653 std::swap (b_11
, _1
);
2654 else if (ssa_defined_by_minus_one_stmt_p (_1
, b_11
))
2658 /* Check the recurrence:
2659 ... = PHI <b_5(2), b_6(3)>. */
2660 gimple
*phi
= SSA_NAME_DEF_STMT (b_11
);
2661 if (gimple_code (phi
) != GIMPLE_PHI
2662 || (gimple_bb (phi
) != loop_latch_edge (loop
)->dest
)
2663 || (gimple_assign_lhs (and_stmt
)
2664 != gimple_phi_arg_def (phi
, loop_latch_edge (loop
)->dest_idx
)))
2667 /* We found a match. Get the corresponding popcount builtin. */
2668 tree src
= gimple_phi_arg_def (phi
, loop_preheader_edge (loop
)->dest_idx
);
2669 if (TYPE_PRECISION (TREE_TYPE (src
)) == TYPE_PRECISION (integer_type_node
))
2670 fn
= builtin_decl_implicit (BUILT_IN_POPCOUNT
);
2671 else if (TYPE_PRECISION (TREE_TYPE (src
)) == TYPE_PRECISION
2672 (long_integer_type_node
))
2673 fn
= builtin_decl_implicit (BUILT_IN_POPCOUNTL
);
2674 else if (TYPE_PRECISION (TREE_TYPE (src
)) == TYPE_PRECISION
2675 (long_long_integer_type_node
))
2676 fn
= builtin_decl_implicit (BUILT_IN_POPCOUNTLL
);
2678 /* ??? Support promoting char/short to int. */
2682 /* Update NITER params accordingly */
2683 tree utype
= unsigned_type_for (TREE_TYPE (src
));
2684 src
= fold_convert (utype
, src
);
2685 tree call
= fold_convert (utype
, build_call_expr (fn
, 1, src
));
2687 iter
= fold_build2 (MINUS_EXPR
, utype
,
2689 build_int_cst (utype
, 1));
2693 if (TREE_CODE (call
) == INTEGER_CST
)
2694 max
= tree_to_uhwi (call
);
2696 max
= TYPE_PRECISION (TREE_TYPE (src
));
2700 niter
->niter
= iter
;
2701 niter
->assumptions
= boolean_true_node
;
2705 tree may_be_zero
= fold_build2 (EQ_EXPR
, boolean_type_node
, src
,
2708 niter
->may_be_zero
=
2709 simplify_using_initial_conditions (loop
, may_be_zero
);
2712 niter
->may_be_zero
= boolean_false_node
;
2715 niter
->bound
= NULL_TREE
;
2716 niter
->cmp
= ERROR_MARK
;
2721 /* Like number_of_iterations_exit_assumptions, but return TRUE only if
2722 the niter information holds unconditionally. */
2725 number_of_iterations_exit (class loop
*loop
, edge exit
,
2726 class tree_niter_desc
*niter
,
2727 bool warn
, bool every_iteration
,
2731 if (!number_of_iterations_exit_assumptions (loop
, exit
, niter
,
2732 &stmt
, every_iteration
, body
))
2735 if (integer_nonzerop (niter
->assumptions
))
2738 if (warn
&& dump_enabled_p ())
2739 dump_printf_loc (MSG_MISSED_OPTIMIZATION
, stmt
,
2740 "missed loop optimization: niters analysis ends up "
2741 "with assumptions.\n");
2746 /* Try to determine the number of iterations of LOOP. If we succeed,
2747 expression giving number of iterations is returned and *EXIT is
2748 set to the edge from that the information is obtained. Otherwise
2749 chrec_dont_know is returned. */
2752 find_loop_niter (class loop
*loop
, edge
*exit
)
2755 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
);
2757 tree niter
= NULL_TREE
, aniter
;
2758 class tree_niter_desc desc
;
2761 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2763 if (!number_of_iterations_exit (loop
, ex
, &desc
, false))
2766 if (integer_nonzerop (desc
.may_be_zero
))
2768 /* We exit in the first iteration through this exit.
2769 We won't find anything better. */
2770 niter
= build_int_cst (unsigned_type_node
, 0);
2775 if (!integer_zerop (desc
.may_be_zero
))
2778 aniter
= desc
.niter
;
2782 /* Nothing recorded yet. */
2788 /* Prefer constants, the lower the better. */
2789 if (TREE_CODE (aniter
) != INTEGER_CST
)
2792 if (TREE_CODE (niter
) != INTEGER_CST
)
2799 if (tree_int_cst_lt (aniter
, niter
))
2807 return niter
? niter
: chrec_dont_know
;
2810 /* Return true if loop is known to have bounded number of iterations. */
2813 finite_loop_p (class loop
*loop
)
2818 flags
= flags_from_decl_or_type (current_function_decl
);
2819 if ((flags
& (ECF_CONST
|ECF_PURE
)) && !(flags
& ECF_LOOPING_CONST_OR_PURE
))
2821 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2822 fprintf (dump_file
, "Found loop %i to be finite: it is within pure or const function.\n",
2827 if (loop
->any_upper_bound
2828 || max_loop_iterations (loop
, &nit
))
2830 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2831 fprintf (dump_file
, "Found loop %i to be finite: upper bound found.\n",
2839 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
);
2842 /* If the loop has a normal exit, we can assume it will terminate. */
2843 FOR_EACH_VEC_ELT (exits
, i
, ex
)
2844 if (!(ex
->flags
& (EDGE_EH
| EDGE_ABNORMAL
| EDGE_FAKE
)))
2847 fprintf (dump_file
, "Assume loop %i to be finite: it has an exit "
2848 "and -ffinite-loops is on.\n", loop
->num
);
2858 Analysis of a number of iterations of a loop by a brute-force evaluation.
2862 /* Bound on the number of iterations we try to evaluate. */
2864 #define MAX_ITERATIONS_TO_TRACK \
2865 ((unsigned) param_max_iterations_to_track)
2867 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
2868 result by a chain of operations such that all but exactly one of their
2869 operands are constants. */
2872 chain_of_csts_start (class loop
*loop
, tree x
)
2874 gimple
*stmt
= SSA_NAME_DEF_STMT (x
);
2876 basic_block bb
= gimple_bb (stmt
);
2877 enum tree_code code
;
2880 || !flow_bb_inside_loop_p (loop
, bb
))
2883 if (gimple_code (stmt
) == GIMPLE_PHI
)
2885 if (bb
== loop
->header
)
2886 return as_a
<gphi
*> (stmt
);
2891 if (gimple_code (stmt
) != GIMPLE_ASSIGN
2892 || gimple_assign_rhs_class (stmt
) == GIMPLE_TERNARY_RHS
)
2895 code
= gimple_assign_rhs_code (stmt
);
2896 if (gimple_references_memory_p (stmt
)
2897 || TREE_CODE_CLASS (code
) == tcc_reference
2898 || (code
== ADDR_EXPR
2899 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt
))))
2902 use
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
2903 if (use
== NULL_TREE
)
2906 return chain_of_csts_start (loop
, use
);
2909 /* Determines whether the expression X is derived from a result of a phi node
2910 in header of LOOP such that
2912 * the derivation of X consists only from operations with constants
2913 * the initial value of the phi node is constant
2914 * the value of the phi node in the next iteration can be derived from the
2915 value in the current iteration by a chain of operations with constants,
2916 or is also a constant
2918 If such phi node exists, it is returned, otherwise NULL is returned. */
2921 get_base_for (class loop
*loop
, tree x
)
2926 if (is_gimple_min_invariant (x
))
2929 phi
= chain_of_csts_start (loop
, x
);
2933 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2934 next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2936 if (!is_gimple_min_invariant (init
))
2939 if (TREE_CODE (next
) == SSA_NAME
2940 && chain_of_csts_start (loop
, next
) != phi
)
2946 /* Given an expression X, then
2948 * if X is NULL_TREE, we return the constant BASE.
2949 * if X is a constant, we return the constant X.
2950 * otherwise X is a SSA name, whose value in the considered loop is derived
2951 by a chain of operations with constant from a result of a phi node in
2952 the header of the loop. Then we return value of X when the value of the
2953 result of this phi node is given by the constant BASE. */
2956 get_val_for (tree x
, tree base
)
2960 gcc_checking_assert (is_gimple_min_invariant (base
));
2964 else if (is_gimple_min_invariant (x
))
2967 stmt
= SSA_NAME_DEF_STMT (x
);
2968 if (gimple_code (stmt
) == GIMPLE_PHI
)
2971 gcc_checking_assert (is_gimple_assign (stmt
));
2973 /* STMT must be either an assignment of a single SSA name or an
2974 expression involving an SSA name and a constant. Try to fold that
2975 expression using the value for the SSA name. */
2976 if (gimple_assign_ssa_name_copy_p (stmt
))
2977 return get_val_for (gimple_assign_rhs1 (stmt
), base
);
2978 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_UNARY_RHS
2979 && TREE_CODE (gimple_assign_rhs1 (stmt
)) == SSA_NAME
)
2980 return fold_build1 (gimple_assign_rhs_code (stmt
),
2981 gimple_expr_type (stmt
),
2982 get_val_for (gimple_assign_rhs1 (stmt
), base
));
2983 else if (gimple_assign_rhs_class (stmt
) == GIMPLE_BINARY_RHS
)
2985 tree rhs1
= gimple_assign_rhs1 (stmt
);
2986 tree rhs2
= gimple_assign_rhs2 (stmt
);
2987 if (TREE_CODE (rhs1
) == SSA_NAME
)
2988 rhs1
= get_val_for (rhs1
, base
);
2989 else if (TREE_CODE (rhs2
) == SSA_NAME
)
2990 rhs2
= get_val_for (rhs2
, base
);
2993 return fold_build2 (gimple_assign_rhs_code (stmt
),
2994 gimple_expr_type (stmt
), rhs1
, rhs2
);
3001 /* Tries to count the number of iterations of LOOP till it exits by EXIT
3002 by brute force -- i.e. by determining the value of the operands of the
3003 condition at EXIT in first few iterations of the loop (assuming that
3004 these values are constant) and determining the first one in that the
3005 condition is not satisfied. Returns the constant giving the number
3006 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
3009 loop_niter_by_eval (class loop
*loop
, edge exit
)
3012 tree op
[2], val
[2], next
[2], aval
[2];
3018 cond
= last_stmt (exit
->src
);
3019 if (!cond
|| gimple_code (cond
) != GIMPLE_COND
)
3020 return chrec_dont_know
;
3022 cmp
= gimple_cond_code (cond
);
3023 if (exit
->flags
& EDGE_TRUE_VALUE
)
3024 cmp
= invert_tree_comparison (cmp
, false);
3034 op
[0] = gimple_cond_lhs (cond
);
3035 op
[1] = gimple_cond_rhs (cond
);
3039 return chrec_dont_know
;
3042 for (j
= 0; j
< 2; j
++)
3044 if (is_gimple_min_invariant (op
[j
]))
3047 next
[j
] = NULL_TREE
;
3052 phi
= get_base_for (loop
, op
[j
]);
3054 return chrec_dont_know
;
3055 val
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
3056 next
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
3060 /* Don't issue signed overflow warnings. */
3061 fold_defer_overflow_warnings ();
3063 for (i
= 0; i
< MAX_ITERATIONS_TO_TRACK
; i
++)
3065 for (j
= 0; j
< 2; j
++)
3066 aval
[j
] = get_val_for (op
[j
], val
[j
]);
3068 acnd
= fold_binary (cmp
, boolean_type_node
, aval
[0], aval
[1]);
3069 if (acnd
&& integer_zerop (acnd
))
3071 fold_undefer_and_ignore_overflow_warnings ();
3072 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3074 "Proved that loop %d iterates %d times using brute force.\n",
3076 return build_int_cst (unsigned_type_node
, i
);
3079 for (j
= 0; j
< 2; j
++)
3082 val
[j
] = get_val_for (next
[j
], val
[j
]);
3083 if (!is_gimple_min_invariant (val
[j
]))
3085 fold_undefer_and_ignore_overflow_warnings ();
3086 return chrec_dont_know
;
3090 /* If the next iteration would use the same base values
3091 as the current one, there is no point looping further,
3092 all following iterations will be the same as this one. */
3093 if (val
[0] == aval
[0] && val
[1] == aval
[1])
3097 fold_undefer_and_ignore_overflow_warnings ();
3099 return chrec_dont_know
;
3102 /* Finds the exit of the LOOP by that the loop exits after a constant
3103 number of iterations and stores the exit edge to *EXIT. The constant
3104 giving the number of iterations of LOOP is returned. The number of
3105 iterations is determined using loop_niter_by_eval (i.e. by brute force
3106 evaluation). If we are unable to find the exit for that loop_niter_by_eval
3107 determines the number of iterations, chrec_dont_know is returned. */
3110 find_loop_niter_by_eval (class loop
*loop
, edge
*exit
)
3113 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
);
3115 tree niter
= NULL_TREE
, aniter
;
3119 /* Loops with multiple exits are expensive to handle and less important. */
3120 if (!flag_expensive_optimizations
3121 && exits
.length () > 1)
3122 return chrec_dont_know
;
3124 FOR_EACH_VEC_ELT (exits
, i
, ex
)
3126 if (!just_once_each_iteration_p (loop
, ex
->src
))
3129 aniter
= loop_niter_by_eval (loop
, ex
);
3130 if (chrec_contains_undetermined (aniter
))
3134 && !tree_int_cst_lt (aniter
, niter
))
3141 return niter
? niter
: chrec_dont_know
;
3146 Analysis of upper bounds on number of iterations of a loop.
3150 static widest_int
derive_constant_upper_bound_ops (tree
, tree
,
3151 enum tree_code
, tree
);
3153 /* Returns a constant upper bound on the value of the right-hand side of
3154 an assignment statement STMT. */
3157 derive_constant_upper_bound_assign (gimple
*stmt
)
3159 enum tree_code code
= gimple_assign_rhs_code (stmt
);
3160 tree op0
= gimple_assign_rhs1 (stmt
);
3161 tree op1
= gimple_assign_rhs2 (stmt
);
3163 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt
)),
3167 /* Returns a constant upper bound on the value of expression VAL. VAL
3168 is considered to be unsigned. If its type is signed, its value must
3172 derive_constant_upper_bound (tree val
)
3174 enum tree_code code
;
3177 extract_ops_from_tree (val
, &code
, &op0
, &op1
, &op2
);
3178 return derive_constant_upper_bound_ops (TREE_TYPE (val
), op0
, code
, op1
);
3181 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
3182 whose type is TYPE. The expression is considered to be unsigned. If
3183 its type is signed, its value must be nonnegative. */
3186 derive_constant_upper_bound_ops (tree type
, tree op0
,
3187 enum tree_code code
, tree op1
)
3190 widest_int bnd
, max
, cst
;
3193 if (INTEGRAL_TYPE_P (type
))
3194 maxt
= TYPE_MAX_VALUE (type
);
3196 maxt
= upper_bound_in_type (type
, type
);
3198 max
= wi::to_widest (maxt
);
3203 return wi::to_widest (op0
);
3206 subtype
= TREE_TYPE (op0
);
3207 if (!TYPE_UNSIGNED (subtype
)
3208 /* If TYPE is also signed, the fact that VAL is nonnegative implies
3209 that OP0 is nonnegative. */
3210 && TYPE_UNSIGNED (type
)
3211 && !tree_expr_nonnegative_p (op0
))
3213 /* If we cannot prove that the casted expression is nonnegative,
3214 we cannot establish more useful upper bound than the precision
3215 of the type gives us. */
3219 /* We now know that op0 is an nonnegative value. Try deriving an upper
3221 bnd
= derive_constant_upper_bound (op0
);
3223 /* If the bound does not fit in TYPE, max. value of TYPE could be
3225 if (wi::ltu_p (max
, bnd
))
3231 case POINTER_PLUS_EXPR
:
3233 if (TREE_CODE (op1
) != INTEGER_CST
3234 || !tree_expr_nonnegative_p (op0
))
3237 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
3238 choose the most logical way how to treat this constant regardless
3239 of the signedness of the type. */
3240 cst
= wi::sext (wi::to_widest (op1
), TYPE_PRECISION (type
));
3241 if (code
!= MINUS_EXPR
)
3244 bnd
= derive_constant_upper_bound (op0
);
3246 if (wi::neg_p (cst
))
3249 /* Avoid CST == 0x80000... */
3250 if (wi::neg_p (cst
))
3253 /* OP0 + CST. We need to check that
3254 BND <= MAX (type) - CST. */
3256 widest_int mmax
= max
- cst
;
3257 if (wi::leu_p (bnd
, mmax
))
3264 /* OP0 - CST, where CST >= 0.
3266 If TYPE is signed, we have already verified that OP0 >= 0, and we
3267 know that the result is nonnegative. This implies that
3270 If TYPE is unsigned, we must additionally know that OP0 >= CST,
3271 otherwise the operation underflows.
3274 /* This should only happen if the type is unsigned; however, for
3275 buggy programs that use overflowing signed arithmetics even with
3276 -fno-wrapv, this condition may also be true for signed values. */
3277 if (wi::ltu_p (bnd
, cst
))
3280 if (TYPE_UNSIGNED (type
))
3282 tree tem
= fold_binary (GE_EXPR
, boolean_type_node
, op0
,
3283 wide_int_to_tree (type
, cst
));
3284 if (!tem
|| integer_nonzerop (tem
))
3293 case FLOOR_DIV_EXPR
:
3294 case EXACT_DIV_EXPR
:
3295 if (TREE_CODE (op1
) != INTEGER_CST
3296 || tree_int_cst_sign_bit (op1
))
3299 bnd
= derive_constant_upper_bound (op0
);
3300 return wi::udiv_floor (bnd
, wi::to_widest (op1
));
3303 if (TREE_CODE (op1
) != INTEGER_CST
3304 || tree_int_cst_sign_bit (op1
))
3306 return wi::to_widest (op1
);
3309 stmt
= SSA_NAME_DEF_STMT (op0
);
3310 if (gimple_code (stmt
) != GIMPLE_ASSIGN
3311 || gimple_assign_lhs (stmt
) != op0
)
3313 return derive_constant_upper_bound_assign (stmt
);
3320 /* Emit a -Waggressive-loop-optimizations warning if needed. */
3323 do_warn_aggressive_loop_optimizations (class loop
*loop
,
3324 widest_int i_bound
, gimple
*stmt
)
3326 /* Don't warn if the loop doesn't have known constant bound. */
3327 if (!loop
->nb_iterations
3328 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
3329 || !warn_aggressive_loop_optimizations
3330 /* To avoid warning multiple times for the same loop,
3331 only start warning when we preserve loops. */
3332 || (cfun
->curr_properties
& PROP_loops
) == 0
3333 /* Only warn once per loop. */
3334 || loop
->warned_aggressive_loop_optimizations
3335 /* Only warn if undefined behavior gives us lower estimate than the
3336 known constant bound. */
3337 || wi::cmpu (i_bound
, wi::to_widest (loop
->nb_iterations
)) >= 0
3338 /* And undefined behavior happens unconditionally. */
3339 || !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (stmt
)))
3342 edge e
= single_exit (loop
);
3346 gimple
*estmt
= last_stmt (e
->src
);
3347 char buf
[WIDE_INT_PRINT_BUFFER_SIZE
];
3348 print_dec (i_bound
, buf
, TYPE_UNSIGNED (TREE_TYPE (loop
->nb_iterations
))
3349 ? UNSIGNED
: SIGNED
);
3350 auto_diagnostic_group d
;
3351 if (warning_at (gimple_location (stmt
), OPT_Waggressive_loop_optimizations
,
3352 "iteration %s invokes undefined behavior", buf
))
3353 inform (gimple_location (estmt
), "within this loop");
3354 loop
->warned_aggressive_loop_optimizations
= true;
3357 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
3358 is true if the loop is exited immediately after STMT, and this exit
3359 is taken at last when the STMT is executed BOUND + 1 times.
3360 REALISTIC is true if BOUND is expected to be close to the real number
3361 of iterations. UPPER is true if we are sure the loop iterates at most
3362 BOUND times. I_BOUND is a widest_int upper estimate on BOUND. */
3365 record_estimate (class loop
*loop
, tree bound
, const widest_int
&i_bound
,
3366 gimple
*at_stmt
, bool is_exit
, bool realistic
, bool upper
)
3370 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3372 fprintf (dump_file
, "Statement %s", is_exit
? "(exit)" : "");
3373 print_gimple_stmt (dump_file
, at_stmt
, 0, TDF_SLIM
);
3374 fprintf (dump_file
, " is %sexecuted at most ",
3375 upper
? "" : "probably ");
3376 print_generic_expr (dump_file
, bound
, TDF_SLIM
);
3377 fprintf (dump_file
, " (bounded by ");
3378 print_decu (i_bound
, dump_file
);
3379 fprintf (dump_file
, ") + 1 times in loop %d.\n", loop
->num
);
3382 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
3383 real number of iterations. */
3384 if (TREE_CODE (bound
) != INTEGER_CST
)
3387 gcc_checking_assert (i_bound
== wi::to_widest (bound
));
3389 /* If we have a guaranteed upper bound, record it in the appropriate
3390 list, unless this is an !is_exit bound (i.e. undefined behavior in
3391 at_stmt) in a loop with known constant number of iterations. */
3394 || loop
->nb_iterations
== NULL_TREE
3395 || TREE_CODE (loop
->nb_iterations
) != INTEGER_CST
))
3397 class nb_iter_bound
*elt
= ggc_alloc
<nb_iter_bound
> ();
3399 elt
->bound
= i_bound
;
3400 elt
->stmt
= at_stmt
;
3401 elt
->is_exit
= is_exit
;
3402 elt
->next
= loop
->bounds
;
3406 /* If statement is executed on every path to the loop latch, we can directly
3407 infer the upper bound on the # of iterations of the loop. */
3408 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (at_stmt
)))
3411 /* Update the number of iteration estimates according to the bound.
3412 If at_stmt is an exit then the loop latch is executed at most BOUND times,
3413 otherwise it can be executed BOUND + 1 times. We will lower the estimate
3414 later if such statement must be executed on last iteration */
3419 widest_int new_i_bound
= i_bound
+ delta
;
3421 /* If an overflow occurred, ignore the result. */
3422 if (wi::ltu_p (new_i_bound
, delta
))
3425 if (upper
&& !is_exit
)
3426 do_warn_aggressive_loop_optimizations (loop
, new_i_bound
, at_stmt
);
3427 record_niter_bound (loop
, new_i_bound
, realistic
, upper
);
3430 /* Records the control iv analyzed in NITER for LOOP if the iv is valid
3431 and doesn't overflow. */
3434 record_control_iv (class loop
*loop
, class tree_niter_desc
*niter
)
3436 struct control_iv
*iv
;
3438 if (!niter
->control
.base
|| !niter
->control
.step
)
3441 if (!integer_onep (niter
->assumptions
) || !niter
->control
.no_overflow
)
3444 iv
= ggc_alloc
<control_iv
> ();
3445 iv
->base
= niter
->control
.base
;
3446 iv
->step
= niter
->control
.step
;
3447 iv
->next
= loop
->control_ivs
;
3448 loop
->control_ivs
= iv
;
3453 /* This function returns TRUE if below conditions are satisfied:
3454 1) VAR is SSA variable.
3455 2) VAR is an IV:{base, step} in its defining loop.
3456 3) IV doesn't overflow.
3457 4) Both base and step are integer constants.
3458 5) Base is the MIN/MAX value depends on IS_MIN.
3459 Store value of base to INIT correspondingly. */
3462 get_cst_init_from_scev (tree var
, wide_int
*init
, bool is_min
)
3464 if (TREE_CODE (var
) != SSA_NAME
)
3467 gimple
*def_stmt
= SSA_NAME_DEF_STMT (var
);
3468 class loop
*loop
= loop_containing_stmt (def_stmt
);
3474 if (!simple_iv (loop
, loop
, var
, &iv
, false))
3477 if (!iv
.no_overflow
)
3480 if (TREE_CODE (iv
.base
) != INTEGER_CST
|| TREE_CODE (iv
.step
) != INTEGER_CST
)
3483 if (is_min
== tree_int_cst_sign_bit (iv
.step
))
3486 *init
= wi::to_wide (iv
.base
);
3490 /* Record the estimate on number of iterations of LOOP based on the fact that
3491 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
3492 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
3493 estimated number of iterations is expected to be close to the real one.
3494 UPPER is true if we are sure the induction variable does not wrap. */
3497 record_nonwrapping_iv (class loop
*loop
, tree base
, tree step
, gimple
*stmt
,
3498 tree low
, tree high
, bool realistic
, bool upper
)
3500 tree niter_bound
, extreme
, delta
;
3501 tree type
= TREE_TYPE (base
), unsigned_type
;
3502 tree orig_base
= base
;
3504 if (TREE_CODE (step
) != INTEGER_CST
|| integer_zerop (step
))
3507 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3509 fprintf (dump_file
, "Induction variable (");
3510 print_generic_expr (dump_file
, TREE_TYPE (base
), TDF_SLIM
);
3511 fprintf (dump_file
, ") ");
3512 print_generic_expr (dump_file
, base
, TDF_SLIM
);
3513 fprintf (dump_file
, " + ");
3514 print_generic_expr (dump_file
, step
, TDF_SLIM
);
3515 fprintf (dump_file
, " * iteration does not wrap in statement ");
3516 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
3517 fprintf (dump_file
, " in loop %d.\n", loop
->num
);
3520 unsigned_type
= unsigned_type_for (type
);
3521 base
= fold_convert (unsigned_type
, base
);
3522 step
= fold_convert (unsigned_type
, step
);
3524 if (tree_int_cst_sign_bit (step
))
3527 extreme
= fold_convert (unsigned_type
, low
);
3528 if (TREE_CODE (orig_base
) == SSA_NAME
3529 && TREE_CODE (high
) == INTEGER_CST
3530 && INTEGRAL_TYPE_P (TREE_TYPE (orig_base
))
3531 && (get_range_info (orig_base
, &min
, &max
) == VR_RANGE
3532 || get_cst_init_from_scev (orig_base
, &max
, false))
3533 && wi::gts_p (wi::to_wide (high
), max
))
3534 base
= wide_int_to_tree (unsigned_type
, max
);
3535 else if (TREE_CODE (base
) != INTEGER_CST
3536 && dominated_by_p (CDI_DOMINATORS
,
3537 loop
->latch
, gimple_bb (stmt
)))
3538 base
= fold_convert (unsigned_type
, high
);
3539 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
3540 step
= fold_build1 (NEGATE_EXPR
, unsigned_type
, step
);
3545 extreme
= fold_convert (unsigned_type
, high
);
3546 if (TREE_CODE (orig_base
) == SSA_NAME
3547 && TREE_CODE (low
) == INTEGER_CST
3548 && INTEGRAL_TYPE_P (TREE_TYPE (orig_base
))
3549 && (get_range_info (orig_base
, &min
, &max
) == VR_RANGE
3550 || get_cst_init_from_scev (orig_base
, &min
, true))
3551 && wi::gts_p (min
, wi::to_wide (low
)))
3552 base
= wide_int_to_tree (unsigned_type
, min
);
3553 else if (TREE_CODE (base
) != INTEGER_CST
3554 && dominated_by_p (CDI_DOMINATORS
,
3555 loop
->latch
, gimple_bb (stmt
)))
3556 base
= fold_convert (unsigned_type
, low
);
3557 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
3560 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
3561 would get out of the range. */
3562 niter_bound
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step
);
3563 widest_int max
= derive_constant_upper_bound (niter_bound
);
3564 record_estimate (loop
, niter_bound
, max
, stmt
, false, realistic
, upper
);
3567 /* Determine information about number of iterations a LOOP from the index
3568 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
3569 guaranteed to be executed in every iteration of LOOP. Callback for
3579 idx_infer_loop_bounds (tree base
, tree
*idx
, void *dta
)
3581 struct ilb_data
*data
= (struct ilb_data
*) dta
;
3582 tree ev
, init
, step
;
3583 tree low
, high
, type
, next
;
3584 bool sign
, upper
= true, at_end
= false;
3585 class loop
*loop
= data
->loop
;
3587 if (TREE_CODE (base
) != ARRAY_REF
)
3590 /* For arrays at the end of the structure, we are not guaranteed that they
3591 do not really extend over their declared size. However, for arrays of
3592 size greater than one, this is unlikely to be intended. */
3593 if (array_at_struct_end_p (base
))
3599 class loop
*dloop
= loop_containing_stmt (data
->stmt
);
3603 ev
= analyze_scalar_evolution (dloop
, *idx
);
3604 ev
= instantiate_parameters (loop
, ev
);
3605 init
= initial_condition (ev
);
3606 step
= evolution_part_in_loop_num (ev
, loop
->num
);
3610 || TREE_CODE (step
) != INTEGER_CST
3611 || integer_zerop (step
)
3612 || tree_contains_chrecs (init
, NULL
)
3613 || chrec_contains_symbols_defined_in_loop (init
, loop
->num
))
3616 low
= array_ref_low_bound (base
);
3617 high
= array_ref_up_bound (base
);
3619 /* The case of nonconstant bounds could be handled, but it would be
3621 if (TREE_CODE (low
) != INTEGER_CST
3623 || TREE_CODE (high
) != INTEGER_CST
)
3625 sign
= tree_int_cst_sign_bit (step
);
3626 type
= TREE_TYPE (step
);
3628 /* The array of length 1 at the end of a structure most likely extends
3629 beyond its bounds. */
3631 && operand_equal_p (low
, high
, 0))
3634 /* In case the relevant bound of the array does not fit in type, or
3635 it does, but bound + step (in type) still belongs into the range of the
3636 array, the index may wrap and still stay within the range of the array
3637 (consider e.g. if the array is indexed by the full range of
3640 To make things simpler, we require both bounds to fit into type, although
3641 there are cases where this would not be strictly necessary. */
3642 if (!int_fits_type_p (high
, type
)
3643 || !int_fits_type_p (low
, type
))
3645 low
= fold_convert (type
, low
);
3646 high
= fold_convert (type
, high
);
3649 next
= fold_binary (PLUS_EXPR
, type
, low
, step
);
3651 next
= fold_binary (PLUS_EXPR
, type
, high
, step
);
3653 if (tree_int_cst_compare (low
, next
) <= 0
3654 && tree_int_cst_compare (next
, high
) <= 0)
3657 /* If access is not executed on every iteration, we must ensure that overlow
3658 may not make the access valid later. */
3659 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, gimple_bb (data
->stmt
))
3660 && scev_probably_wraps_p (NULL_TREE
,
3661 initial_condition_in_loop_num (ev
, loop
->num
),
3662 step
, data
->stmt
, loop
, true))
3665 record_nonwrapping_iv (loop
, init
, step
, data
->stmt
, low
, high
, false, upper
);
3669 /* Determine information about number of iterations a LOOP from the bounds
3670 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
3671 STMT is guaranteed to be executed in every iteration of LOOP.*/
3674 infer_loop_bounds_from_ref (class loop
*loop
, gimple
*stmt
, tree ref
)
3676 struct ilb_data data
;
3680 for_each_index (&ref
, idx_infer_loop_bounds
, &data
);
3683 /* Determine information about number of iterations of a LOOP from the way
3684 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
3685 executed in every iteration of LOOP. */
3688 infer_loop_bounds_from_array (class loop
*loop
, gimple
*stmt
)
3690 if (is_gimple_assign (stmt
))
3692 tree op0
= gimple_assign_lhs (stmt
);
3693 tree op1
= gimple_assign_rhs1 (stmt
);
3695 /* For each memory access, analyze its access function
3696 and record a bound on the loop iteration domain. */
3697 if (REFERENCE_CLASS_P (op0
))
3698 infer_loop_bounds_from_ref (loop
, stmt
, op0
);
3700 if (REFERENCE_CLASS_P (op1
))
3701 infer_loop_bounds_from_ref (loop
, stmt
, op1
);
3703 else if (is_gimple_call (stmt
))
3706 unsigned i
, n
= gimple_call_num_args (stmt
);
3708 lhs
= gimple_call_lhs (stmt
);
3709 if (lhs
&& REFERENCE_CLASS_P (lhs
))
3710 infer_loop_bounds_from_ref (loop
, stmt
, lhs
);
3712 for (i
= 0; i
< n
; i
++)
3714 arg
= gimple_call_arg (stmt
, i
);
3715 if (REFERENCE_CLASS_P (arg
))
3716 infer_loop_bounds_from_ref (loop
, stmt
, arg
);
3721 /* Determine information about number of iterations of a LOOP from the fact
3722 that pointer arithmetics in STMT does not overflow. */
3725 infer_loop_bounds_from_pointer_arith (class loop
*loop
, gimple
*stmt
)
3727 tree def
, base
, step
, scev
, type
, low
, high
;
3730 if (!is_gimple_assign (stmt
)
3731 || gimple_assign_rhs_code (stmt
) != POINTER_PLUS_EXPR
)
3734 def
= gimple_assign_lhs (stmt
);
3735 if (TREE_CODE (def
) != SSA_NAME
)
3738 type
= TREE_TYPE (def
);
3739 if (!nowrap_type_p (type
))
3742 ptr
= gimple_assign_rhs1 (stmt
);
3743 if (!expr_invariant_in_loop_p (loop
, ptr
))
3746 var
= gimple_assign_rhs2 (stmt
);
3747 if (TYPE_PRECISION (type
) != TYPE_PRECISION (TREE_TYPE (var
)))
3750 class loop
*uloop
= loop_containing_stmt (stmt
);
3751 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (uloop
, def
));
3752 if (chrec_contains_undetermined (scev
))
3755 base
= initial_condition_in_loop_num (scev
, loop
->num
);
3756 step
= evolution_part_in_loop_num (scev
, loop
->num
);
3759 || TREE_CODE (step
) != INTEGER_CST
3760 || tree_contains_chrecs (base
, NULL
)
3761 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
3764 low
= lower_bound_in_type (type
, type
);
3765 high
= upper_bound_in_type (type
, type
);
3767 /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
3768 produce a NULL pointer. The contrary would mean NULL points to an object,
3769 while NULL is supposed to compare unequal with the address of all objects.
3770 Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
3771 NULL pointer since that would mean wrapping, which we assume here not to
3772 happen. So, we can exclude NULL from the valid range of pointer
3774 if (flag_delete_null_pointer_checks
&& int_cst_value (low
) == 0)
3775 low
= build_int_cstu (TREE_TYPE (low
), TYPE_ALIGN_UNIT (TREE_TYPE (type
)));
3777 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
3780 /* Determine information about number of iterations of a LOOP from the fact
3781 that signed arithmetics in STMT does not overflow. */
3784 infer_loop_bounds_from_signedness (class loop
*loop
, gimple
*stmt
)
3786 tree def
, base
, step
, scev
, type
, low
, high
;
3788 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
3791 def
= gimple_assign_lhs (stmt
);
3793 if (TREE_CODE (def
) != SSA_NAME
)
3796 type
= TREE_TYPE (def
);
3797 if (!INTEGRAL_TYPE_P (type
)
3798 || !TYPE_OVERFLOW_UNDEFINED (type
))
3801 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
3802 if (chrec_contains_undetermined (scev
))
3805 base
= initial_condition_in_loop_num (scev
, loop
->num
);
3806 step
= evolution_part_in_loop_num (scev
, loop
->num
);
3809 || TREE_CODE (step
) != INTEGER_CST
3810 || tree_contains_chrecs (base
, NULL
)
3811 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
3814 low
= lower_bound_in_type (type
, type
);
3815 high
= upper_bound_in_type (type
, type
);
3816 wide_int minv
, maxv
;
3817 if (get_range_info (def
, &minv
, &maxv
) == VR_RANGE
)
3819 low
= wide_int_to_tree (type
, minv
);
3820 high
= wide_int_to_tree (type
, maxv
);
3823 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false, true);
3826 /* The following analyzers are extracting informations on the bounds
3827 of LOOP from the following undefined behaviors:
3829 - data references should not access elements over the statically
3832 - signed variables should not overflow when flag_wrapv is not set.
3836 infer_loop_bounds_from_undefined (class loop
*loop
, basic_block
*bbs
)
3839 gimple_stmt_iterator bsi
;
3843 for (i
= 0; i
< loop
->num_nodes
; i
++)
3847 /* If BB is not executed in each iteration of the loop, we cannot
3848 use the operations in it to infer reliable upper bound on the
3849 # of iterations of the loop. However, we can use it as a guess.
3850 Reliable guesses come only from array bounds. */
3851 reliable
= dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
);
3853 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
3855 gimple
*stmt
= gsi_stmt (bsi
);
3857 infer_loop_bounds_from_array (loop
, stmt
);
3861 infer_loop_bounds_from_signedness (loop
, stmt
);
3862 infer_loop_bounds_from_pointer_arith (loop
, stmt
);
3869 /* Compare wide ints, callback for qsort. */
3872 wide_int_cmp (const void *p1
, const void *p2
)
3874 const widest_int
*d1
= (const widest_int
*) p1
;
3875 const widest_int
*d2
= (const widest_int
*) p2
;
3876 return wi::cmpu (*d1
, *d2
);
3879 /* Return index of BOUND in BOUNDS array sorted in increasing order.
3880 Lookup by binary search. */
3883 bound_index (vec
<widest_int
> bounds
, const widest_int
&bound
)
3885 unsigned int end
= bounds
.length ();
3886 unsigned int begin
= 0;
3888 /* Find a matching index by means of a binary search. */
3889 while (begin
!= end
)
3891 unsigned int middle
= (begin
+ end
) / 2;
3892 widest_int index
= bounds
[middle
];
3896 else if (wi::ltu_p (index
, bound
))
3904 /* We recorded loop bounds only for statements dominating loop latch (and thus
3905 executed each loop iteration). If there are any bounds on statements not
3906 dominating the loop latch we can improve the estimate by walking the loop
3907 body and seeing if every path from loop header to loop latch contains
3908 some bounded statement. */
3911 discover_iteration_bound_by_body_walk (class loop
*loop
)
3913 class nb_iter_bound
*elt
;
3914 auto_vec
<widest_int
> bounds
;
3915 vec
<vec
<basic_block
> > queues
= vNULL
;
3916 vec
<basic_block
> queue
= vNULL
;
3917 ptrdiff_t queue_index
;
3918 ptrdiff_t latch_index
= 0;
3920 /* Discover what bounds may interest us. */
3921 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3923 widest_int bound
= elt
->bound
;
3925 /* Exit terminates loop at given iteration, while non-exits produce undefined
3926 effect on the next iteration. */
3930 /* If an overflow occurred, ignore the result. */
3935 if (!loop
->any_upper_bound
3936 || wi::ltu_p (bound
, loop
->nb_iterations_upper_bound
))
3937 bounds
.safe_push (bound
);
3940 /* Exit early if there is nothing to do. */
3941 if (!bounds
.exists ())
3944 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3945 fprintf (dump_file
, " Trying to walk loop body to reduce the bound.\n");
3947 /* Sort the bounds in decreasing order. */
3948 bounds
.qsort (wide_int_cmp
);
3950 /* For every basic block record the lowest bound that is guaranteed to
3951 terminate the loop. */
3953 hash_map
<basic_block
, ptrdiff_t> bb_bounds
;
3954 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
3956 widest_int bound
= elt
->bound
;
3960 /* If an overflow occurred, ignore the result. */
3965 if (!loop
->any_upper_bound
3966 || wi::ltu_p (bound
, loop
->nb_iterations_upper_bound
))
3968 ptrdiff_t index
= bound_index (bounds
, bound
);
3969 ptrdiff_t *entry
= bb_bounds
.get (gimple_bb (elt
->stmt
));
3971 bb_bounds
.put (gimple_bb (elt
->stmt
), index
);
3972 else if ((ptrdiff_t)*entry
> index
)
3977 hash_map
<basic_block
, ptrdiff_t> block_priority
;
3979 /* Perform shortest path discovery loop->header ... loop->latch.
3981 The "distance" is given by the smallest loop bound of basic block
3982 present in the path and we look for path with largest smallest bound
3985 To avoid the need for fibonacci heap on double ints we simply compress
3986 double ints into indexes to BOUNDS array and then represent the queue
3987 as arrays of queues for every index.
3988 Index of BOUNDS.length() means that the execution of given BB has
3989 no bounds determined.
3991 VISITED is a pointer map translating basic block into smallest index
3992 it was inserted into the priority queue with. */
3995 /* Start walk in loop header with index set to infinite bound. */
3996 queue_index
= bounds
.length ();
3997 queues
.safe_grow_cleared (queue_index
+ 1, true);
3998 queue
.safe_push (loop
->header
);
3999 queues
[queue_index
] = queue
;
4000 block_priority
.put (loop
->header
, queue_index
);
4002 for (; queue_index
>= 0; queue_index
--)
4004 if (latch_index
< queue_index
)
4006 while (queues
[queue_index
].length ())
4009 ptrdiff_t bound_index
= queue_index
;
4013 queue
= queues
[queue_index
];
4016 /* OK, we later inserted the BB with lower priority, skip it. */
4017 if (*block_priority
.get (bb
) > queue_index
)
4020 /* See if we can improve the bound. */
4021 ptrdiff_t *entry
= bb_bounds
.get (bb
);
4022 if (entry
&& *entry
< bound_index
)
4023 bound_index
= *entry
;
4025 /* Insert succesors into the queue, watch for latch edge
4026 and record greatest index we saw. */
4027 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4029 bool insert
= false;
4031 if (loop_exit_edge_p (loop
, e
))
4034 if (e
== loop_latch_edge (loop
)
4035 && latch_index
< bound_index
)
4036 latch_index
= bound_index
;
4037 else if (!(entry
= block_priority
.get (e
->dest
)))
4040 block_priority
.put (e
->dest
, bound_index
);
4042 else if (*entry
< bound_index
)
4045 *entry
= bound_index
;
4049 queues
[bound_index
].safe_push (e
->dest
);
4053 queues
[queue_index
].release ();
4056 gcc_assert (latch_index
>= 0);
4057 if ((unsigned)latch_index
< bounds
.length ())
4059 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4061 fprintf (dump_file
, "Found better loop bound ");
4062 print_decu (bounds
[latch_index
], dump_file
);
4063 fprintf (dump_file
, "\n");
4065 record_niter_bound (loop
, bounds
[latch_index
], false, true);
4071 /* See if every path cross the loop goes through a statement that is known
4072 to not execute at the last iteration. In that case we can decrese iteration
4076 maybe_lower_iteration_bound (class loop
*loop
)
4078 hash_set
<gimple
*> *not_executed_last_iteration
= NULL
;
4079 class nb_iter_bound
*elt
;
4080 bool found_exit
= false;
4081 auto_vec
<basic_block
> queue
;
4084 /* Collect all statements with interesting (i.e. lower than
4085 nb_iterations_upper_bound) bound on them.
4087 TODO: Due to the way record_estimate choose estimates to store, the bounds
4088 will be always nb_iterations_upper_bound-1. We can change this to record
4089 also statements not dominating the loop latch and update the walk bellow
4090 to the shortest path algorithm. */
4091 for (elt
= loop
->bounds
; elt
; elt
= elt
->next
)
4094 && wi::ltu_p (elt
->bound
, loop
->nb_iterations_upper_bound
))
4096 if (!not_executed_last_iteration
)
4097 not_executed_last_iteration
= new hash_set
<gimple
*>;
4098 not_executed_last_iteration
->add (elt
->stmt
);
4101 if (!not_executed_last_iteration
)
4104 /* Start DFS walk in the loop header and see if we can reach the
4105 loop latch or any of the exits (including statements with side
4106 effects that may terminate the loop otherwise) without visiting
4107 any of the statements known to have undefined effect on the last
4109 queue
.safe_push (loop
->header
);
4110 visited
= BITMAP_ALLOC (NULL
);
4111 bitmap_set_bit (visited
, loop
->header
->index
);
4116 basic_block bb
= queue
.pop ();
4117 gimple_stmt_iterator gsi
;
4118 bool stmt_found
= false;
4120 /* Loop for possible exits and statements bounding the execution. */
4121 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
4123 gimple
*stmt
= gsi_stmt (gsi
);
4124 if (not_executed_last_iteration
->contains (stmt
))
4129 if (gimple_has_side_effects (stmt
))
4138 /* If no bounding statement is found, continue the walk. */
4144 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
4146 if (loop_exit_edge_p (loop
, e
)
4147 || e
== loop_latch_edge (loop
))
4152 if (bitmap_set_bit (visited
, e
->dest
->index
))
4153 queue
.safe_push (e
->dest
);
4157 while (queue
.length () && !found_exit
);
4159 /* If every path through the loop reach bounding statement before exit,
4160 then we know the last iteration of the loop will have undefined effect
4161 and we can decrease number of iterations. */
4165 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
4166 fprintf (dump_file
, "Reducing loop iteration estimate by 1; "
4167 "undefined statement must be executed at the last iteration.\n");
4168 record_niter_bound (loop
, loop
->nb_iterations_upper_bound
- 1,
4172 BITMAP_FREE (visited
);
4173 delete not_executed_last_iteration
;
4176 /* Get expected upper bound for number of loop iterations for
4177 BUILT_IN_EXPECT_WITH_PROBABILITY for a condition COND. */
4180 get_upper_bound_based_on_builtin_expr_with_prob (gcond
*cond
)
4185 tree lhs
= gimple_cond_lhs (cond
);
4186 if (TREE_CODE (lhs
) != SSA_NAME
)
4189 gimple
*stmt
= SSA_NAME_DEF_STMT (gimple_cond_lhs (cond
));
4190 gcall
*def
= dyn_cast
<gcall
*> (stmt
);
4194 tree decl
= gimple_call_fndecl (def
);
4196 || !fndecl_built_in_p (decl
, BUILT_IN_EXPECT_WITH_PROBABILITY
)
4197 || gimple_call_num_args (stmt
) != 3)
4200 tree c
= gimple_call_arg (def
, 1);
4201 tree condt
= TREE_TYPE (lhs
);
4202 tree res
= fold_build2 (gimple_cond_code (cond
),
4204 gimple_cond_rhs (cond
));
4205 if (TREE_CODE (res
) != INTEGER_CST
)
4209 tree prob
= gimple_call_arg (def
, 2);
4210 tree t
= TREE_TYPE (prob
);
4212 = build_real_from_int_cst (t
,
4214 if (integer_zerop (res
))
4215 prob
= fold_build2 (MINUS_EXPR
, t
, one
, prob
);
4216 tree r
= fold_build2 (RDIV_EXPR
, t
, one
, prob
);
4217 if (TREE_CODE (r
) != REAL_CST
)
4221 = real_to_integer (TREE_REAL_CST_PTR (r
));
4222 return build_int_cst (condt
, probi
);
4225 /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
4226 is true also use estimates derived from undefined behavior. */
4229 estimate_numbers_of_iterations (class loop
*loop
)
4233 class tree_niter_desc niter_desc
;
4238 /* Give up if we already have tried to compute an estimation. */
4239 if (loop
->estimate_state
!= EST_NOT_COMPUTED
)
4242 loop
->estimate_state
= EST_AVAILABLE
;
4244 /* If we have a measured profile, use it to estimate the number of
4245 iterations. Normally this is recorded by branch_prob right after
4246 reading the profile. In case we however found a new loop, record the
4249 Explicitly check for profile status so we do not report
4250 wrong prediction hitrates for guessed loop iterations heuristics.
4251 Do not recompute already recorded bounds - we ought to be better on
4252 updating iteration bounds than updating profile in general and thus
4253 recomputing iteration bounds later in the compilation process will just
4254 introduce random roundoff errors. */
4255 if (!loop
->any_estimate
4256 && loop
->header
->count
.reliable_p ())
4258 gcov_type nit
= expected_loop_iterations_unbounded (loop
);
4259 bound
= gcov_type_to_wide_int (nit
);
4260 record_niter_bound (loop
, bound
, true, false);
4263 /* Ensure that loop->nb_iterations is computed if possible. If it turns out
4264 to be constant, we avoid undefined behavior implied bounds and instead
4265 diagnose those loops with -Waggressive-loop-optimizations. */
4266 number_of_latch_executions (loop
);
4268 basic_block
*body
= get_loop_body (loop
);
4269 auto_vec
<edge
> exits
= get_loop_exit_edges (loop
, body
);
4270 likely_exit
= single_likely_exit (loop
, exits
);
4271 FOR_EACH_VEC_ELT (exits
, i
, ex
)
4273 if (ex
== likely_exit
)
4275 gimple
*stmt
= last_stmt (ex
->src
);
4278 gcond
*cond
= dyn_cast
<gcond
*> (stmt
);
4280 = get_upper_bound_based_on_builtin_expr_with_prob (cond
);
4281 if (niter_bound
!= NULL_TREE
)
4283 widest_int max
= derive_constant_upper_bound (niter_bound
);
4284 record_estimate (loop
, niter_bound
, max
, cond
,
4290 if (!number_of_iterations_exit (loop
, ex
, &niter_desc
,
4291 false, false, body
))
4294 niter
= niter_desc
.niter
;
4295 type
= TREE_TYPE (niter
);
4296 if (TREE_CODE (niter_desc
.may_be_zero
) != INTEGER_CST
)
4297 niter
= build3 (COND_EXPR
, type
, niter_desc
.may_be_zero
,
4298 build_int_cst (type
, 0),
4300 record_estimate (loop
, niter
, niter_desc
.max
,
4301 last_stmt (ex
->src
),
4302 true, ex
== likely_exit
, true);
4303 record_control_iv (loop
, &niter_desc
);
4306 if (flag_aggressive_loop_optimizations
)
4307 infer_loop_bounds_from_undefined (loop
, body
);
4310 discover_iteration_bound_by_body_walk (loop
);
4312 maybe_lower_iteration_bound (loop
);
4314 /* If we know the exact number of iterations of this loop, try to
4315 not break code with undefined behavior by not recording smaller
4316 maximum number of iterations. */
4317 if (loop
->nb_iterations
4318 && TREE_CODE (loop
->nb_iterations
) == INTEGER_CST
)
4320 loop
->any_upper_bound
= true;
4321 loop
->nb_iterations_upper_bound
= wi::to_widest (loop
->nb_iterations
);
4325 /* Sets NIT to the estimated number of executions of the latch of the
4326 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
4327 large as the number of iterations. If we have no reliable estimate,
4328 the function returns false, otherwise returns true. */
4331 estimated_loop_iterations (class loop
*loop
, widest_int
*nit
)
4333 /* When SCEV information is available, try to update loop iterations
4334 estimate. Otherwise just return whatever we recorded earlier. */
4335 if (scev_initialized_p ())
4336 estimate_numbers_of_iterations (loop
);
4338 return (get_estimated_loop_iterations (loop
, nit
));
4341 /* Similar to estimated_loop_iterations, but returns the estimate only
4342 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
4343 on the number of iterations of LOOP could not be derived, returns -1. */
4346 estimated_loop_iterations_int (class loop
*loop
)
4349 HOST_WIDE_INT hwi_nit
;
4351 if (!estimated_loop_iterations (loop
, &nit
))
4354 if (!wi::fits_shwi_p (nit
))
4356 hwi_nit
= nit
.to_shwi ();
4358 return hwi_nit
< 0 ? -1 : hwi_nit
;
4362 /* Sets NIT to an upper bound for the maximum number of executions of the
4363 latch of the LOOP. If we have no reliable estimate, the function returns
4364 false, otherwise returns true. */
4367 max_loop_iterations (class loop
*loop
, widest_int
*nit
)
4369 /* When SCEV information is available, try to update loop iterations
4370 estimate. Otherwise just return whatever we recorded earlier. */
4371 if (scev_initialized_p ())
4372 estimate_numbers_of_iterations (loop
);
4374 return get_max_loop_iterations (loop
, nit
);
4377 /* Similar to max_loop_iterations, but returns the estimate only
4378 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
4379 on the number of iterations of LOOP could not be derived, returns -1. */
4382 max_loop_iterations_int (class loop
*loop
)
4385 HOST_WIDE_INT hwi_nit
;
4387 if (!max_loop_iterations (loop
, &nit
))
4390 if (!wi::fits_shwi_p (nit
))
4392 hwi_nit
= nit
.to_shwi ();
4394 return hwi_nit
< 0 ? -1 : hwi_nit
;
4397 /* Sets NIT to an likely upper bound for the maximum number of executions of the
4398 latch of the LOOP. If we have no reliable estimate, the function returns
4399 false, otherwise returns true. */
4402 likely_max_loop_iterations (class loop
*loop
, widest_int
*nit
)
4404 /* When SCEV information is available, try to update loop iterations
4405 estimate. Otherwise just return whatever we recorded earlier. */
4406 if (scev_initialized_p ())
4407 estimate_numbers_of_iterations (loop
);
4409 return get_likely_max_loop_iterations (loop
, nit
);
4412 /* Similar to max_loop_iterations, but returns the estimate only
4413 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
4414 on the number of iterations of LOOP could not be derived, returns -1. */
4417 likely_max_loop_iterations_int (class loop
*loop
)
4420 HOST_WIDE_INT hwi_nit
;
4422 if (!likely_max_loop_iterations (loop
, &nit
))
4425 if (!wi::fits_shwi_p (nit
))
4427 hwi_nit
= nit
.to_shwi ();
4429 return hwi_nit
< 0 ? -1 : hwi_nit
;
4432 /* Returns an estimate for the number of executions of statements
4433 in the LOOP. For statements before the loop exit, this exceeds
4434 the number of execution of the latch by one. */
4437 estimated_stmt_executions_int (class loop
*loop
)
4439 HOST_WIDE_INT nit
= estimated_loop_iterations_int (loop
);
4445 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
4447 /* If the computation overflows, return -1. */
4448 return snit
< 0 ? -1 : snit
;
4451 /* Sets NIT to the maximum number of executions of the latch of the
4452 LOOP, plus one. If we have no reliable estimate, the function returns
4453 false, otherwise returns true. */
4456 max_stmt_executions (class loop
*loop
, widest_int
*nit
)
4458 widest_int nit_minus_one
;
4460 if (!max_loop_iterations (loop
, nit
))
4463 nit_minus_one
= *nit
;
4467 return wi::gtu_p (*nit
, nit_minus_one
);
4470 /* Sets NIT to the estimated maximum number of executions of the latch of the
4471 LOOP, plus one. If we have no likely estimate, the function returns
4472 false, otherwise returns true. */
4475 likely_max_stmt_executions (class loop
*loop
, widest_int
*nit
)
4477 widest_int nit_minus_one
;
4479 if (!likely_max_loop_iterations (loop
, nit
))
4482 nit_minus_one
= *nit
;
4486 return wi::gtu_p (*nit
, nit_minus_one
);
4489 /* Sets NIT to the estimated number of executions of the latch of the
4490 LOOP, plus one. If we have no reliable estimate, the function returns
4491 false, otherwise returns true. */
4494 estimated_stmt_executions (class loop
*loop
, widest_int
*nit
)
4496 widest_int nit_minus_one
;
4498 if (!estimated_loop_iterations (loop
, nit
))
4501 nit_minus_one
= *nit
;
4505 return wi::gtu_p (*nit
, nit_minus_one
);
4508 /* Records estimates on numbers of iterations of loops. */
4511 estimate_numbers_of_iterations (function
*fn
)
4515 /* We don't want to issue signed overflow warnings while getting
4516 loop iteration estimates. */
4517 fold_defer_overflow_warnings ();
4519 FOR_EACH_LOOP_FN (fn
, loop
, 0)
4520 estimate_numbers_of_iterations (loop
);
4522 fold_undefer_and_ignore_overflow_warnings ();
4525 /* Returns true if statement S1 dominates statement S2. */
4528 stmt_dominates_stmt_p (gimple
*s1
, gimple
*s2
)
4530 basic_block bb1
= gimple_bb (s1
), bb2
= gimple_bb (s2
);
4538 gimple_stmt_iterator bsi
;
4540 if (gimple_code (s2
) == GIMPLE_PHI
)
4543 if (gimple_code (s1
) == GIMPLE_PHI
)
4546 for (bsi
= gsi_start_bb (bb1
); gsi_stmt (bsi
) != s2
; gsi_next (&bsi
))
4547 if (gsi_stmt (bsi
) == s1
)
4553 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
4556 /* Returns true when we can prove that the number of executions of
4557 STMT in the loop is at most NITER, according to the bound on
4558 the number of executions of the statement NITER_BOUND->stmt recorded in
4559 NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT.
4561 ??? This code can become quite a CPU hog - we can have many bounds,
4562 and large basic block forcing stmt_dominates_stmt_p to be queried
4563 many times on a large basic blocks, so the whole thing is O(n^2)
4564 for scev_probably_wraps_p invocation (that can be done n times).
4566 It would make more sense (and give better answers) to remember BB
4567 bounds computed by discover_iteration_bound_by_body_walk. */
4570 n_of_executions_at_most (gimple
*stmt
,
4571 class nb_iter_bound
*niter_bound
,
4574 widest_int bound
= niter_bound
->bound
;
4575 tree nit_type
= TREE_TYPE (niter
), e
;
4578 gcc_assert (TYPE_UNSIGNED (nit_type
));
4580 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
4581 the number of iterations is small. */
4582 if (!wi::fits_to_tree_p (bound
, nit_type
))
4585 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
4586 times. This means that:
4588 -- if NITER_BOUND->is_exit is true, then everything after
4589 it at most NITER_BOUND->bound times.
4591 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
4592 is executed, then NITER_BOUND->stmt is executed as well in the same
4593 iteration then STMT is executed at most NITER_BOUND->bound + 1 times.
4595 If we can determine that NITER_BOUND->stmt is always executed
4596 after STMT, then STMT is executed at most NITER_BOUND->bound + 2 times.
4597 We conclude that if both statements belong to the same
4598 basic block and STMT is before NITER_BOUND->stmt and there are no
4599 statements with side effects in between. */
4601 if (niter_bound
->is_exit
)
4603 if (stmt
== niter_bound
->stmt
4604 || !stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
4610 if (!stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
4612 gimple_stmt_iterator bsi
;
4613 if (gimple_bb (stmt
) != gimple_bb (niter_bound
->stmt
)
4614 || gimple_code (stmt
) == GIMPLE_PHI
4615 || gimple_code (niter_bound
->stmt
) == GIMPLE_PHI
)
4618 /* By stmt_dominates_stmt_p we already know that STMT appears
4619 before NITER_BOUND->STMT. Still need to test that the loop
4620 cannot be terinated by a side effect in between. */
4621 for (bsi
= gsi_for_stmt (stmt
); gsi_stmt (bsi
) != niter_bound
->stmt
;
4623 if (gimple_has_side_effects (gsi_stmt (bsi
)))
4627 || !wi::fits_to_tree_p (bound
, nit_type
))
4633 e
= fold_binary (cmp
, boolean_type_node
,
4634 niter
, wide_int_to_tree (nit_type
, bound
));
4635 return e
&& integer_nonzerop (e
);
4638 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
4641 nowrap_type_p (tree type
)
4643 if (ANY_INTEGRAL_TYPE_P (type
)
4644 && TYPE_OVERFLOW_UNDEFINED (type
))
4647 if (POINTER_TYPE_P (type
))
4653 /* Return true if we can prove LOOP is exited before evolution of induction
4654 variable {BASE, STEP} overflows with respect to its type bound. */
4657 loop_exits_before_overflow (tree base
, tree step
,
4658 gimple
*at_stmt
, class loop
*loop
)
4661 struct control_iv
*civ
;
4662 class nb_iter_bound
*bound
;
4663 tree e
, delta
, step_abs
, unsigned_base
;
4664 tree type
= TREE_TYPE (step
);
4665 tree unsigned_type
, valid_niter
;
4667 /* Don't issue signed overflow warnings. */
4668 fold_defer_overflow_warnings ();
4670 /* Compute the number of iterations before we reach the bound of the
4671 type, and verify that the loop is exited before this occurs. */
4672 unsigned_type
= unsigned_type_for (type
);
4673 unsigned_base
= fold_convert (unsigned_type
, base
);
4675 if (tree_int_cst_sign_bit (step
))
4677 tree extreme
= fold_convert (unsigned_type
,
4678 lower_bound_in_type (type
, type
));
4679 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, unsigned_base
, extreme
);
4680 step_abs
= fold_build1 (NEGATE_EXPR
, unsigned_type
,
4681 fold_convert (unsigned_type
, step
));
4685 tree extreme
= fold_convert (unsigned_type
,
4686 upper_bound_in_type (type
, type
));
4687 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, unsigned_base
);
4688 step_abs
= fold_convert (unsigned_type
, step
);
4691 valid_niter
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step_abs
);
4693 estimate_numbers_of_iterations (loop
);
4695 if (max_loop_iterations (loop
, &niter
)
4696 && wi::fits_to_tree_p (niter
, TREE_TYPE (valid_niter
))
4697 && (e
= fold_binary (GT_EXPR
, boolean_type_node
, valid_niter
,
4698 wide_int_to_tree (TREE_TYPE (valid_niter
),
4700 && integer_nonzerop (e
))
4702 fold_undefer_and_ignore_overflow_warnings ();
4706 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
4708 if (n_of_executions_at_most (at_stmt
, bound
, valid_niter
))
4710 fold_undefer_and_ignore_overflow_warnings ();
4714 fold_undefer_and_ignore_overflow_warnings ();
4716 /* Try to prove loop is exited before {base, step} overflows with the
4717 help of analyzed loop control IV. This is done only for IVs with
4718 constant step because otherwise we don't have the information. */
4719 if (TREE_CODE (step
) == INTEGER_CST
)
4721 for (civ
= loop
->control_ivs
; civ
; civ
= civ
->next
)
4723 enum tree_code code
;
4724 tree civ_type
= TREE_TYPE (civ
->step
);
4726 /* Have to consider type difference because operand_equal_p ignores
4727 that for constants. */
4728 if (TYPE_UNSIGNED (type
) != TYPE_UNSIGNED (civ_type
)
4729 || element_precision (type
) != element_precision (civ_type
))
4732 /* Only consider control IV with same step. */
4733 if (!operand_equal_p (step
, civ
->step
, 0))
4736 /* Done proving if this is a no-overflow control IV. */
4737 if (operand_equal_p (base
, civ
->base
, 0))
4740 /* Control IV is recorded after expanding simple operations,
4741 Here we expand base and compare it too. */
4742 tree expanded_base
= expand_simple_operations (base
);
4743 if (operand_equal_p (expanded_base
, civ
->base
, 0))
4746 /* If this is a before stepping control IV, in other words, we have
4748 {civ_base, step} = {base + step, step}
4750 Because civ {base + step, step} doesn't overflow during loop
4751 iterations, {base, step} will not overflow if we can prove the
4752 operation "base + step" does not overflow. Specifically, we try
4753 to prove below conditions are satisfied:
4755 base <= UPPER_BOUND (type) - step ;;step > 0
4756 base >= LOWER_BOUND (type) - step ;;step < 0
4758 by proving the reverse conditions are false using loop's initial
4760 if (POINTER_TYPE_P (TREE_TYPE (base
)))
4761 code
= POINTER_PLUS_EXPR
;
4765 tree stepped
= fold_build2 (code
, TREE_TYPE (base
), base
, step
);
4766 tree expanded_stepped
= fold_build2 (code
, TREE_TYPE (base
),
4767 expanded_base
, step
);
4768 if (operand_equal_p (stepped
, civ
->base
, 0)
4769 || operand_equal_p (expanded_stepped
, civ
->base
, 0))
4773 if (tree_int_cst_sign_bit (step
))
4776 extreme
= lower_bound_in_type (type
, type
);
4781 extreme
= upper_bound_in_type (type
, type
);
4783 extreme
= fold_build2 (MINUS_EXPR
, type
, extreme
, step
);
4784 e
= fold_build2 (code
, boolean_type_node
, base
, extreme
);
4785 e
= simplify_using_initial_conditions (loop
, e
);
4786 if (integer_zerop (e
))
4795 /* VAR is scev variable whose evolution part is constant STEP, this function
4796 proves that VAR can't overflow by using value range info. If VAR's value
4797 range is [MIN, MAX], it can be proven by:
4798 MAX + step doesn't overflow ; if step > 0
4800 MIN + step doesn't underflow ; if step < 0.
4802 We can only do this if var is computed in every loop iteration, i.e, var's
4803 definition has to dominate loop latch. Consider below example:
4811 # RANGE [0, 4294967294] NONZERO 65535
4812 # i_21 = PHI <0(3), i_18(9)>
4819 # RANGE [0, 65533] NONZERO 65535
4820 _6 = i_21 + 4294967295;
4821 # RANGE [0, 65533] NONZERO 65535
4822 _7 = (long unsigned int) _6;
4823 # RANGE [0, 524264] NONZERO 524280
4825 # PT = nonlocal escaped
4830 # RANGE [1, 65535] NONZERO 65535
4844 VAR _6 doesn't overflow only with pre-condition (i_21 != 0), here we
4845 can't use _6 to prove no-overlfow for _7. In fact, var _7 takes value
4846 sequence (4294967295, 0, 1, ..., 65533) in loop life time, rather than
4847 (4294967295, 4294967296, ...). */
4850 scev_var_range_cant_overflow (tree var
, tree step
, class loop
*loop
)
4853 wide_int minv
, maxv
, diff
, step_wi
;
4854 enum value_range_kind rtype
;
4856 if (TREE_CODE (step
) != INTEGER_CST
|| !INTEGRAL_TYPE_P (TREE_TYPE (var
)))
4859 /* Check if VAR evaluates in every loop iteration. It's not the case
4860 if VAR is default definition or does not dominate loop's latch. */
4861 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (var
));
4862 if (!def_bb
|| !dominated_by_p (CDI_DOMINATORS
, loop
->latch
, def_bb
))
4865 rtype
= get_range_info (var
, &minv
, &maxv
);
4866 if (rtype
!= VR_RANGE
)
4869 /* VAR is a scev whose evolution part is STEP and value range info
4870 is [MIN, MAX], we can prove its no-overflowness by conditions:
4872 type_MAX - MAX >= step ; if step > 0
4873 MIN - type_MIN >= |step| ; if step < 0.
4875 Or VAR must take value outside of value range, which is not true. */
4876 step_wi
= wi::to_wide (step
);
4877 type
= TREE_TYPE (var
);
4878 if (tree_int_cst_sign_bit (step
))
4880 diff
= minv
- wi::to_wide (lower_bound_in_type (type
, type
));
4881 step_wi
= - step_wi
;
4884 diff
= wi::to_wide (upper_bound_in_type (type
, type
)) - maxv
;
4886 return (wi::geu_p (diff
, step_wi
));
4889 /* Return false only when the induction variable BASE + STEP * I is
4890 known to not overflow: i.e. when the number of iterations is small
4891 enough with respect to the step and initial condition in order to
4892 keep the evolution confined in TYPEs bounds. Return true when the
4893 iv is known to overflow or when the property is not computable.
4895 USE_OVERFLOW_SEMANTICS is true if this function should assume that
4896 the rules for overflow of the given language apply (e.g., that signed
4897 arithmetics in C does not overflow).
4899 If VAR is a ssa variable, this function also returns false if VAR can
4900 be proven not overflow with value range info. */
4903 scev_probably_wraps_p (tree var
, tree base
, tree step
,
4904 gimple
*at_stmt
, class loop
*loop
,
4905 bool use_overflow_semantics
)
4907 /* FIXME: We really need something like
4908 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
4910 We used to test for the following situation that frequently appears
4911 during address arithmetics:
4913 D.1621_13 = (long unsigned intD.4) D.1620_12;
4914 D.1622_14 = D.1621_13 * 8;
4915 D.1623_15 = (doubleD.29 *) D.1622_14;
4917 And derived that the sequence corresponding to D_14
4918 can be proved to not wrap because it is used for computing a
4919 memory access; however, this is not really the case -- for example,
4920 if D_12 = (unsigned char) [254,+,1], then D_14 has values
4921 2032, 2040, 0, 8, ..., but the code is still legal. */
4923 if (chrec_contains_undetermined (base
)
4924 || chrec_contains_undetermined (step
))
4927 if (integer_zerop (step
))
4930 /* If we can use the fact that signed and pointer arithmetics does not
4931 wrap, we are done. */
4932 if (use_overflow_semantics
&& nowrap_type_p (TREE_TYPE (base
)))
4935 /* To be able to use estimates on number of iterations of the loop,
4936 we must have an upper bound on the absolute value of the step. */
4937 if (TREE_CODE (step
) != INTEGER_CST
)
4940 /* Check if var can be proven not overflow with value range info. */
4941 if (var
&& TREE_CODE (var
) == SSA_NAME
4942 && scev_var_range_cant_overflow (var
, step
, loop
))
4945 if (loop_exits_before_overflow (base
, step
, at_stmt
, loop
))
4948 /* At this point we still don't have a proof that the iv does not
4949 overflow: give up. */
4953 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
4956 free_numbers_of_iterations_estimates (class loop
*loop
)
4958 struct control_iv
*civ
;
4959 class nb_iter_bound
*bound
;
4961 loop
->nb_iterations
= NULL
;
4962 loop
->estimate_state
= EST_NOT_COMPUTED
;
4963 for (bound
= loop
->bounds
; bound
;)
4965 class nb_iter_bound
*next
= bound
->next
;
4969 loop
->bounds
= NULL
;
4971 for (civ
= loop
->control_ivs
; civ
;)
4973 struct control_iv
*next
= civ
->next
;
4977 loop
->control_ivs
= NULL
;
4980 /* Frees the information on upper bounds on numbers of iterations of loops. */
4983 free_numbers_of_iterations_estimates (function
*fn
)
4987 FOR_EACH_LOOP_FN (fn
, loop
, 0)
4988 free_numbers_of_iterations_estimates (loop
);
4991 /* Substitute value VAL for ssa name NAME inside expressions held
4995 substitute_in_loop_info (class loop
*loop
, tree name
, tree val
)
4997 loop
->nb_iterations
= simplify_replace_tree (loop
->nb_iterations
, name
, val
);