Fix compilation failure with C++98 compilers
[official-gcc.git] / gcc / tree-ssa-loop-niter.c
blob7b6c91ca6daf0060657689a332baa65863a35012
1 /* Functions to determine/estimate number of iterations of a loop.
2 Copyright (C) 2004-2018 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
9 later version.
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
14 for more details.
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/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "backend.h"
24 #include "rtl.h"
25 #include "tree.h"
26 #include "gimple.h"
27 #include "tree-pass.h"
28 #include "ssa.h"
29 #include "gimple-pretty-print.h"
30 #include "diagnostic-core.h"
31 #include "stor-layout.h"
32 #include "fold-const.h"
33 #include "calls.h"
34 #include "intl.h"
35 #include "gimplify.h"
36 #include "gimple-iterator.h"
37 #include "tree-cfg.h"
38 #include "tree-ssa-loop-ivopts.h"
39 #include "tree-ssa-loop-niter.h"
40 #include "tree-ssa-loop.h"
41 #include "cfgloop.h"
42 #include "tree-chrec.h"
43 #include "tree-scalar-evolution.h"
44 #include "params.h"
45 #include "tree-dfa.h"
48 /* The maximum number of dominator BBs we search for conditions
49 of loop header copies we use for simplifying a conditional
50 expression. */
51 #define MAX_DOMINATORS_TO_WALK 8
55 Analysis of number of iterations of an affine exit test.
59 /* Bounds on some value, BELOW <= X <= UP. */
61 struct bounds
63 mpz_t below, up;
66 static bool number_of_iterations_popcount (loop_p loop, edge exit,
67 enum tree_code code,
68 struct tree_niter_desc *niter);
71 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */
73 static void
74 split_to_var_and_offset (tree expr, tree *var, mpz_t offset)
76 tree type = TREE_TYPE (expr);
77 tree op0, op1;
78 bool negate = false;
80 *var = expr;
81 mpz_set_ui (offset, 0);
83 switch (TREE_CODE (expr))
85 case MINUS_EXPR:
86 negate = true;
87 /* Fallthru. */
89 case PLUS_EXPR:
90 case POINTER_PLUS_EXPR:
91 op0 = TREE_OPERAND (expr, 0);
92 op1 = TREE_OPERAND (expr, 1);
94 if (TREE_CODE (op1) != INTEGER_CST)
95 break;
97 *var = op0;
98 /* Always sign extend the offset. */
99 wi::to_mpz (wi::to_wide (op1), offset, SIGNED);
100 if (negate)
101 mpz_neg (offset, offset);
102 break;
104 case INTEGER_CST:
105 *var = build_int_cst_type (type, 0);
106 wi::to_mpz (wi::to_wide (expr), offset, TYPE_SIGN (type));
107 break;
109 default:
110 break;
114 /* From condition C0 CMP C1 derives information regarding the value range
115 of VAR, which is of TYPE. Results are stored in to BELOW and UP. */
117 static void
118 refine_value_range_using_guard (tree type, tree var,
119 tree c0, enum tree_code cmp, tree c1,
120 mpz_t below, mpz_t up)
122 tree varc0, varc1, ctype;
123 mpz_t offc0, offc1;
124 mpz_t mint, maxt, minc1, maxc1;
125 wide_int minv, maxv;
126 bool no_wrap = nowrap_type_p (type);
127 bool c0_ok, c1_ok;
128 signop sgn = TYPE_SIGN (type);
130 switch (cmp)
132 case LT_EXPR:
133 case LE_EXPR:
134 case GT_EXPR:
135 case GE_EXPR:
136 STRIP_SIGN_NOPS (c0);
137 STRIP_SIGN_NOPS (c1);
138 ctype = TREE_TYPE (c0);
139 if (!useless_type_conversion_p (ctype, type))
140 return;
142 break;
144 case EQ_EXPR:
145 /* We could derive quite precise information from EQ_EXPR, however,
146 such a guard is unlikely to appear, so we do not bother with
147 handling it. */
148 return;
150 case NE_EXPR:
151 /* NE_EXPR comparisons do not contain much of useful information,
152 except for cases of comparing with bounds. */
153 if (TREE_CODE (c1) != INTEGER_CST
154 || !INTEGRAL_TYPE_P (type))
155 return;
157 /* Ensure that the condition speaks about an expression in the same
158 type as X and Y. */
159 ctype = TREE_TYPE (c0);
160 if (TYPE_PRECISION (ctype) != TYPE_PRECISION (type))
161 return;
162 c0 = fold_convert (type, c0);
163 c1 = fold_convert (type, c1);
165 if (operand_equal_p (var, c0, 0))
167 mpz_t valc1;
169 /* Case of comparing VAR with its below/up bounds. */
170 mpz_init (valc1);
171 wi::to_mpz (wi::to_wide (c1), valc1, TYPE_SIGN (type));
172 if (mpz_cmp (valc1, below) == 0)
173 cmp = GT_EXPR;
174 if (mpz_cmp (valc1, up) == 0)
175 cmp = LT_EXPR;
177 mpz_clear (valc1);
179 else
181 /* Case of comparing with the bounds of the type. */
182 wide_int min = wi::min_value (type);
183 wide_int max = wi::max_value (type);
185 if (wi::to_wide (c1) == min)
186 cmp = GT_EXPR;
187 if (wi::to_wide (c1) == max)
188 cmp = LT_EXPR;
191 /* Quick return if no useful information. */
192 if (cmp == NE_EXPR)
193 return;
195 break;
197 default:
198 return;
201 mpz_init (offc0);
202 mpz_init (offc1);
203 split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0);
204 split_to_var_and_offset (expand_simple_operations (c1), &varc1, offc1);
206 /* We are only interested in comparisons of expressions based on VAR. */
207 if (operand_equal_p (var, varc1, 0))
209 std::swap (varc0, varc1);
210 mpz_swap (offc0, offc1);
211 cmp = swap_tree_comparison (cmp);
213 else if (!operand_equal_p (var, varc0, 0))
215 mpz_clear (offc0);
216 mpz_clear (offc1);
217 return;
220 mpz_init (mint);
221 mpz_init (maxt);
222 get_type_static_bounds (type, mint, maxt);
223 mpz_init (minc1);
224 mpz_init (maxc1);
225 /* Setup range information for varc1. */
226 if (integer_zerop (varc1))
228 wi::to_mpz (0, minc1, TYPE_SIGN (type));
229 wi::to_mpz (0, maxc1, TYPE_SIGN (type));
231 else if (TREE_CODE (varc1) == SSA_NAME
232 && INTEGRAL_TYPE_P (type)
233 && get_range_info (varc1, &minv, &maxv) == VR_RANGE)
235 gcc_assert (wi::le_p (minv, maxv, sgn));
236 wi::to_mpz (minv, minc1, sgn);
237 wi::to_mpz (maxv, maxc1, sgn);
239 else
241 mpz_set (minc1, mint);
242 mpz_set (maxc1, maxt);
245 /* Compute valid range information for varc1 + offc1. Note nothing
246 useful can be derived if it overflows or underflows. Overflow or
247 underflow could happen when:
249 offc1 > 0 && varc1 + offc1 > MAX_VAL (type)
250 offc1 < 0 && varc1 + offc1 < MIN_VAL (type). */
251 mpz_add (minc1, minc1, offc1);
252 mpz_add (maxc1, maxc1, offc1);
253 c1_ok = (no_wrap
254 || mpz_sgn (offc1) == 0
255 || (mpz_sgn (offc1) < 0 && mpz_cmp (minc1, mint) >= 0)
256 || (mpz_sgn (offc1) > 0 && mpz_cmp (maxc1, maxt) <= 0));
257 if (!c1_ok)
258 goto end;
260 if (mpz_cmp (minc1, mint) < 0)
261 mpz_set (minc1, mint);
262 if (mpz_cmp (maxc1, maxt) > 0)
263 mpz_set (maxc1, maxt);
265 if (cmp == LT_EXPR)
267 cmp = LE_EXPR;
268 mpz_sub_ui (maxc1, maxc1, 1);
270 if (cmp == GT_EXPR)
272 cmp = GE_EXPR;
273 mpz_add_ui (minc1, minc1, 1);
276 /* Compute range information for varc0. If there is no overflow,
277 the condition implied that
279 (varc0) cmp (varc1 + offc1 - offc0)
281 We can possibly improve the upper bound of varc0 if cmp is LE_EXPR,
282 or the below bound if cmp is GE_EXPR.
284 To prove there is no overflow/underflow, we need to check below
285 four cases:
286 1) cmp == LE_EXPR && offc0 > 0
288 (varc0 + offc0) doesn't overflow
289 && (varc1 + offc1 - offc0) doesn't underflow
291 2) cmp == LE_EXPR && offc0 < 0
293 (varc0 + offc0) doesn't underflow
294 && (varc1 + offc1 - offc0) doesn't overfloe
296 In this case, (varc0 + offc0) will never underflow if we can
297 prove (varc1 + offc1 - offc0) doesn't overflow.
299 3) cmp == GE_EXPR && offc0 < 0
301 (varc0 + offc0) doesn't underflow
302 && (varc1 + offc1 - offc0) doesn't overflow
304 4) cmp == GE_EXPR && offc0 > 0
306 (varc0 + offc0) doesn't overflow
307 && (varc1 + offc1 - offc0) doesn't underflow
309 In this case, (varc0 + offc0) will never overflow if we can
310 prove (varc1 + offc1 - offc0) doesn't underflow.
312 Note we only handle case 2 and 4 in below code. */
314 mpz_sub (minc1, minc1, offc0);
315 mpz_sub (maxc1, maxc1, offc0);
316 c0_ok = (no_wrap
317 || mpz_sgn (offc0) == 0
318 || (cmp == LE_EXPR
319 && mpz_sgn (offc0) < 0 && mpz_cmp (maxc1, maxt) <= 0)
320 || (cmp == GE_EXPR
321 && mpz_sgn (offc0) > 0 && mpz_cmp (minc1, mint) >= 0));
322 if (!c0_ok)
323 goto end;
325 if (cmp == LE_EXPR)
327 if (mpz_cmp (up, maxc1) > 0)
328 mpz_set (up, maxc1);
330 else
332 if (mpz_cmp (below, minc1) < 0)
333 mpz_set (below, minc1);
336 end:
337 mpz_clear (mint);
338 mpz_clear (maxt);
339 mpz_clear (minc1);
340 mpz_clear (maxc1);
341 mpz_clear (offc0);
342 mpz_clear (offc1);
345 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
346 in TYPE to MIN and MAX. */
348 static void
349 determine_value_range (struct loop *loop, tree type, tree var, mpz_t off,
350 mpz_t min, mpz_t max)
352 int cnt = 0;
353 mpz_t minm, maxm;
354 basic_block bb;
355 wide_int minv, maxv;
356 enum value_range_type rtype = VR_VARYING;
358 /* If the expression is a constant, we know its value exactly. */
359 if (integer_zerop (var))
361 mpz_set (min, off);
362 mpz_set (max, off);
363 return;
366 get_type_static_bounds (type, min, max);
368 /* See if we have some range info from VRP. */
369 if (TREE_CODE (var) == SSA_NAME && INTEGRAL_TYPE_P (type))
371 edge e = loop_preheader_edge (loop);
372 signop sgn = TYPE_SIGN (type);
373 gphi_iterator gsi;
375 /* Either for VAR itself... */
376 rtype = get_range_info (var, &minv, &maxv);
377 /* Or for PHI results in loop->header where VAR is used as
378 PHI argument from the loop preheader edge. */
379 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
381 gphi *phi = gsi.phi ();
382 wide_int minc, maxc;
383 if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var
384 && (get_range_info (gimple_phi_result (phi), &minc, &maxc)
385 == VR_RANGE))
387 if (rtype != VR_RANGE)
389 rtype = VR_RANGE;
390 minv = minc;
391 maxv = maxc;
393 else
395 minv = wi::max (minv, minc, sgn);
396 maxv = wi::min (maxv, maxc, sgn);
397 /* If the PHI result range are inconsistent with
398 the VAR range, give up on looking at the PHI
399 results. This can happen if VR_UNDEFINED is
400 involved. */
401 if (wi::gt_p (minv, maxv, sgn))
403 rtype = get_range_info (var, &minv, &maxv);
404 break;
409 mpz_init (minm);
410 mpz_init (maxm);
411 if (rtype != VR_RANGE)
413 mpz_set (minm, min);
414 mpz_set (maxm, max);
416 else
418 gcc_assert (wi::le_p (minv, maxv, sgn));
419 wi::to_mpz (minv, minm, sgn);
420 wi::to_mpz (maxv, maxm, sgn);
422 /* Now walk the dominators of the loop header and use the entry
423 guards to refine the estimates. */
424 for (bb = loop->header;
425 bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) && cnt < MAX_DOMINATORS_TO_WALK;
426 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
428 edge e;
429 tree c0, c1;
430 gimple *cond;
431 enum tree_code cmp;
433 if (!single_pred_p (bb))
434 continue;
435 e = single_pred_edge (bb);
437 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
438 continue;
440 cond = last_stmt (e->src);
441 c0 = gimple_cond_lhs (cond);
442 cmp = gimple_cond_code (cond);
443 c1 = gimple_cond_rhs (cond);
445 if (e->flags & EDGE_FALSE_VALUE)
446 cmp = invert_tree_comparison (cmp, false);
448 refine_value_range_using_guard (type, var, c0, cmp, c1, minm, maxm);
449 ++cnt;
452 mpz_add (minm, minm, off);
453 mpz_add (maxm, maxm, off);
454 /* If the computation may not wrap or off is zero, then this
455 is always fine. If off is negative and minv + off isn't
456 smaller than type's minimum, or off is positive and
457 maxv + off isn't bigger than type's maximum, use the more
458 precise range too. */
459 if (nowrap_type_p (type)
460 || mpz_sgn (off) == 0
461 || (mpz_sgn (off) < 0 && mpz_cmp (minm, min) >= 0)
462 || (mpz_sgn (off) > 0 && mpz_cmp (maxm, max) <= 0))
464 mpz_set (min, minm);
465 mpz_set (max, maxm);
466 mpz_clear (minm);
467 mpz_clear (maxm);
468 return;
470 mpz_clear (minm);
471 mpz_clear (maxm);
474 /* If the computation may wrap, we know nothing about the value, except for
475 the range of the type. */
476 if (!nowrap_type_p (type))
477 return;
479 /* Since the addition of OFF does not wrap, if OFF is positive, then we may
480 add it to MIN, otherwise to MAX. */
481 if (mpz_sgn (off) < 0)
482 mpz_add (max, max, off);
483 else
484 mpz_add (min, min, off);
487 /* Stores the bounds on the difference of the values of the expressions
488 (var + X) and (var + Y), computed in TYPE, to BNDS. */
490 static void
491 bound_difference_of_offsetted_base (tree type, mpz_t x, mpz_t y,
492 bounds *bnds)
494 int rel = mpz_cmp (x, y);
495 bool may_wrap = !nowrap_type_p (type);
496 mpz_t m;
498 /* If X == Y, then the expressions are always equal.
499 If X > Y, there are the following possibilities:
500 a) neither of var + X and var + Y overflow or underflow, or both of
501 them do. Then their difference is X - Y.
502 b) var + X overflows, and var + Y does not. Then the values of the
503 expressions are var + X - M and var + Y, where M is the range of
504 the type, and their difference is X - Y - M.
505 c) var + Y underflows and var + X does not. Their difference again
506 is M - X + Y.
507 Therefore, if the arithmetics in type does not overflow, then the
508 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
509 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
510 (X - Y, X - Y + M). */
512 if (rel == 0)
514 mpz_set_ui (bnds->below, 0);
515 mpz_set_ui (bnds->up, 0);
516 return;
519 mpz_init (m);
520 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type)), m, UNSIGNED);
521 mpz_add_ui (m, m, 1);
522 mpz_sub (bnds->up, x, y);
523 mpz_set (bnds->below, bnds->up);
525 if (may_wrap)
527 if (rel > 0)
528 mpz_sub (bnds->below, bnds->below, m);
529 else
530 mpz_add (bnds->up, bnds->up, m);
533 mpz_clear (m);
536 /* From condition C0 CMP C1 derives information regarding the
537 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
538 and stores it to BNDS. */
540 static void
541 refine_bounds_using_guard (tree type, tree varx, mpz_t offx,
542 tree vary, mpz_t offy,
543 tree c0, enum tree_code cmp, tree c1,
544 bounds *bnds)
546 tree varc0, varc1, ctype;
547 mpz_t offc0, offc1, loffx, loffy, bnd;
548 bool lbound = false;
549 bool no_wrap = nowrap_type_p (type);
550 bool x_ok, y_ok;
552 switch (cmp)
554 case LT_EXPR:
555 case LE_EXPR:
556 case GT_EXPR:
557 case GE_EXPR:
558 STRIP_SIGN_NOPS (c0);
559 STRIP_SIGN_NOPS (c1);
560 ctype = TREE_TYPE (c0);
561 if (!useless_type_conversion_p (ctype, type))
562 return;
564 break;
566 case EQ_EXPR:
567 /* We could derive quite precise information from EQ_EXPR, however, such
568 a guard is unlikely to appear, so we do not bother with handling
569 it. */
570 return;
572 case NE_EXPR:
573 /* NE_EXPR comparisons do not contain much of useful information, except for
574 special case of comparing with the bounds of the type. */
575 if (TREE_CODE (c1) != INTEGER_CST
576 || !INTEGRAL_TYPE_P (type))
577 return;
579 /* Ensure that the condition speaks about an expression in the same type
580 as X and Y. */
581 ctype = TREE_TYPE (c0);
582 if (TYPE_PRECISION (ctype) != TYPE_PRECISION (type))
583 return;
584 c0 = fold_convert (type, c0);
585 c1 = fold_convert (type, c1);
587 if (TYPE_MIN_VALUE (type)
588 && operand_equal_p (c1, TYPE_MIN_VALUE (type), 0))
590 cmp = GT_EXPR;
591 break;
593 if (TYPE_MAX_VALUE (type)
594 && operand_equal_p (c1, TYPE_MAX_VALUE (type), 0))
596 cmp = LT_EXPR;
597 break;
600 return;
601 default:
602 return;
605 mpz_init (offc0);
606 mpz_init (offc1);
607 split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0);
608 split_to_var_and_offset (expand_simple_operations (c1), &varc1, offc1);
610 /* We are only interested in comparisons of expressions based on VARX and
611 VARY. TODO -- we might also be able to derive some bounds from
612 expressions containing just one of the variables. */
614 if (operand_equal_p (varx, varc1, 0))
616 std::swap (varc0, varc1);
617 mpz_swap (offc0, offc1);
618 cmp = swap_tree_comparison (cmp);
621 if (!operand_equal_p (varx, varc0, 0)
622 || !operand_equal_p (vary, varc1, 0))
623 goto end;
625 mpz_init_set (loffx, offx);
626 mpz_init_set (loffy, offy);
628 if (cmp == GT_EXPR || cmp == GE_EXPR)
630 std::swap (varx, vary);
631 mpz_swap (offc0, offc1);
632 mpz_swap (loffx, loffy);
633 cmp = swap_tree_comparison (cmp);
634 lbound = true;
637 /* If there is no overflow, the condition implies that
639 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
641 The overflows and underflows may complicate things a bit; each
642 overflow decreases the appropriate offset by M, and underflow
643 increases it by M. The above inequality would not necessarily be
644 true if
646 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
647 VARX + OFFC0 overflows, but VARX + OFFX does not.
648 This may only happen if OFFX < OFFC0.
649 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
650 VARY + OFFC1 underflows and VARY + OFFY does not.
651 This may only happen if OFFY > OFFC1. */
653 if (no_wrap)
655 x_ok = true;
656 y_ok = true;
658 else
660 x_ok = (integer_zerop (varx)
661 || mpz_cmp (loffx, offc0) >= 0);
662 y_ok = (integer_zerop (vary)
663 || mpz_cmp (loffy, offc1) <= 0);
666 if (x_ok && y_ok)
668 mpz_init (bnd);
669 mpz_sub (bnd, loffx, loffy);
670 mpz_add (bnd, bnd, offc1);
671 mpz_sub (bnd, bnd, offc0);
673 if (cmp == LT_EXPR)
674 mpz_sub_ui (bnd, bnd, 1);
676 if (lbound)
678 mpz_neg (bnd, bnd);
679 if (mpz_cmp (bnds->below, bnd) < 0)
680 mpz_set (bnds->below, bnd);
682 else
684 if (mpz_cmp (bnd, bnds->up) < 0)
685 mpz_set (bnds->up, bnd);
687 mpz_clear (bnd);
690 mpz_clear (loffx);
691 mpz_clear (loffy);
692 end:
693 mpz_clear (offc0);
694 mpz_clear (offc1);
697 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
698 The subtraction is considered to be performed in arbitrary precision,
699 without overflows.
701 We do not attempt to be too clever regarding the value ranges of X and
702 Y; most of the time, they are just integers or ssa names offsetted by
703 integer. However, we try to use the information contained in the
704 comparisons before the loop (usually created by loop header copying). */
706 static void
707 bound_difference (struct loop *loop, tree x, tree y, bounds *bnds)
709 tree type = TREE_TYPE (x);
710 tree varx, vary;
711 mpz_t offx, offy;
712 mpz_t minx, maxx, miny, maxy;
713 int cnt = 0;
714 edge e;
715 basic_block bb;
716 tree c0, c1;
717 gimple *cond;
718 enum tree_code cmp;
720 /* Get rid of unnecessary casts, but preserve the value of
721 the expressions. */
722 STRIP_SIGN_NOPS (x);
723 STRIP_SIGN_NOPS (y);
725 mpz_init (bnds->below);
726 mpz_init (bnds->up);
727 mpz_init (offx);
728 mpz_init (offy);
729 split_to_var_and_offset (x, &varx, offx);
730 split_to_var_and_offset (y, &vary, offy);
732 if (!integer_zerop (varx)
733 && operand_equal_p (varx, vary, 0))
735 /* Special case VARX == VARY -- we just need to compare the
736 offsets. The matters are a bit more complicated in the
737 case addition of offsets may wrap. */
738 bound_difference_of_offsetted_base (type, offx, offy, bnds);
740 else
742 /* Otherwise, use the value ranges to determine the initial
743 estimates on below and up. */
744 mpz_init (minx);
745 mpz_init (maxx);
746 mpz_init (miny);
747 mpz_init (maxy);
748 determine_value_range (loop, type, varx, offx, minx, maxx);
749 determine_value_range (loop, type, vary, offy, miny, maxy);
751 mpz_sub (bnds->below, minx, maxy);
752 mpz_sub (bnds->up, maxx, miny);
753 mpz_clear (minx);
754 mpz_clear (maxx);
755 mpz_clear (miny);
756 mpz_clear (maxy);
759 /* If both X and Y are constants, we cannot get any more precise. */
760 if (integer_zerop (varx) && integer_zerop (vary))
761 goto end;
763 /* Now walk the dominators of the loop header and use the entry
764 guards to refine the estimates. */
765 for (bb = loop->header;
766 bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) && cnt < MAX_DOMINATORS_TO_WALK;
767 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
769 if (!single_pred_p (bb))
770 continue;
771 e = single_pred_edge (bb);
773 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
774 continue;
776 cond = last_stmt (e->src);
777 c0 = gimple_cond_lhs (cond);
778 cmp = gimple_cond_code (cond);
779 c1 = gimple_cond_rhs (cond);
781 if (e->flags & EDGE_FALSE_VALUE)
782 cmp = invert_tree_comparison (cmp, false);
784 refine_bounds_using_guard (type, varx, offx, vary, offy,
785 c0, cmp, c1, bnds);
786 ++cnt;
789 end:
790 mpz_clear (offx);
791 mpz_clear (offy);
794 /* Update the bounds in BNDS that restrict the value of X to the bounds
795 that restrict the value of X + DELTA. X can be obtained as a
796 difference of two values in TYPE. */
798 static void
799 bounds_add (bounds *bnds, const widest_int &delta, tree type)
801 mpz_t mdelta, max;
803 mpz_init (mdelta);
804 wi::to_mpz (delta, mdelta, SIGNED);
806 mpz_init (max);
807 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type)), max, UNSIGNED);
809 mpz_add (bnds->up, bnds->up, mdelta);
810 mpz_add (bnds->below, bnds->below, mdelta);
812 if (mpz_cmp (bnds->up, max) > 0)
813 mpz_set (bnds->up, max);
815 mpz_neg (max, max);
816 if (mpz_cmp (bnds->below, max) < 0)
817 mpz_set (bnds->below, max);
819 mpz_clear (mdelta);
820 mpz_clear (max);
823 /* Update the bounds in BNDS that restrict the value of X to the bounds
824 that restrict the value of -X. */
826 static void
827 bounds_negate (bounds *bnds)
829 mpz_t tmp;
831 mpz_init_set (tmp, bnds->up);
832 mpz_neg (bnds->up, bnds->below);
833 mpz_neg (bnds->below, tmp);
834 mpz_clear (tmp);
837 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
839 static tree
840 inverse (tree x, tree mask)
842 tree type = TREE_TYPE (x);
843 tree rslt;
844 unsigned ctr = tree_floor_log2 (mask);
846 if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT)
848 unsigned HOST_WIDE_INT ix;
849 unsigned HOST_WIDE_INT imask;
850 unsigned HOST_WIDE_INT irslt = 1;
852 gcc_assert (cst_and_fits_in_hwi (x));
853 gcc_assert (cst_and_fits_in_hwi (mask));
855 ix = int_cst_value (x);
856 imask = int_cst_value (mask);
858 for (; ctr; ctr--)
860 irslt *= ix;
861 ix *= ix;
863 irslt &= imask;
865 rslt = build_int_cst_type (type, irslt);
867 else
869 rslt = build_int_cst (type, 1);
870 for (; ctr; ctr--)
872 rslt = int_const_binop (MULT_EXPR, rslt, x);
873 x = int_const_binop (MULT_EXPR, x, x);
875 rslt = int_const_binop (BIT_AND_EXPR, rslt, mask);
878 return rslt;
881 /* Derives the upper bound BND on the number of executions of loop with exit
882 condition S * i <> C. If NO_OVERFLOW is true, then the control variable of
883 the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed
884 that the loop ends through this exit, i.e., the induction variable ever
885 reaches the value of C.
887 The value C is equal to final - base, where final and base are the final and
888 initial value of the actual induction variable in the analysed loop. BNDS
889 bounds the value of this difference when computed in signed type with
890 unbounded range, while the computation of C is performed in an unsigned
891 type with the range matching the range of the type of the induction variable.
892 In particular, BNDS.up contains an upper bound on C in the following cases:
893 -- if the iv must reach its final value without overflow, i.e., if
894 NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
895 -- if final >= base, which we know to hold when BNDS.below >= 0. */
897 static void
898 number_of_iterations_ne_max (mpz_t bnd, bool no_overflow, tree c, tree s,
899 bounds *bnds, bool exit_must_be_taken)
901 widest_int max;
902 mpz_t d;
903 tree type = TREE_TYPE (c);
904 bool bnds_u_valid = ((no_overflow && exit_must_be_taken)
905 || mpz_sgn (bnds->below) >= 0);
907 if (integer_onep (s)
908 || (TREE_CODE (c) == INTEGER_CST
909 && TREE_CODE (s) == INTEGER_CST
910 && wi::mod_trunc (wi::to_wide (c), wi::to_wide (s),
911 TYPE_SIGN (type)) == 0)
912 || (TYPE_OVERFLOW_UNDEFINED (type)
913 && multiple_of_p (type, c, s)))
915 /* If C is an exact multiple of S, then its value will be reached before
916 the induction variable overflows (unless the loop is exited in some
917 other way before). Note that the actual induction variable in the
918 loop (which ranges from base to final instead of from 0 to C) may
919 overflow, in which case BNDS.up will not be giving a correct upper
920 bound on C; thus, BNDS_U_VALID had to be computed in advance. */
921 no_overflow = true;
922 exit_must_be_taken = true;
925 /* If the induction variable can overflow, the number of iterations is at
926 most the period of the control variable (or infinite, but in that case
927 the whole # of iterations analysis will fail). */
928 if (!no_overflow)
930 max = wi::mask <widest_int> (TYPE_PRECISION (type)
931 - wi::ctz (wi::to_wide (s)), false);
932 wi::to_mpz (max, bnd, UNSIGNED);
933 return;
936 /* Now we know that the induction variable does not overflow, so the loop
937 iterates at most (range of type / S) times. */
938 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type)), bnd, UNSIGNED);
940 /* If the induction variable is guaranteed to reach the value of C before
941 overflow, ... */
942 if (exit_must_be_taken)
944 /* ... then we can strengthen this to C / S, and possibly we can use
945 the upper bound on C given by BNDS. */
946 if (TREE_CODE (c) == INTEGER_CST)
947 wi::to_mpz (wi::to_wide (c), bnd, UNSIGNED);
948 else if (bnds_u_valid)
949 mpz_set (bnd, bnds->up);
952 mpz_init (d);
953 wi::to_mpz (wi::to_wide (s), d, UNSIGNED);
954 mpz_fdiv_q (bnd, bnd, d);
955 mpz_clear (d);
958 /* Determines number of iterations of loop whose ending condition
959 is IV <> FINAL. TYPE is the type of the iv. The number of
960 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
961 we know that the exit must be taken eventually, i.e., that the IV
962 ever reaches the value FINAL (we derived this earlier, and possibly set
963 NITER->assumptions to make sure this is the case). BNDS contains the
964 bounds on the difference FINAL - IV->base. */
966 static bool
967 number_of_iterations_ne (struct loop *loop, tree type, affine_iv *iv,
968 tree final, struct tree_niter_desc *niter,
969 bool exit_must_be_taken, bounds *bnds)
971 tree niter_type = unsigned_type_for (type);
972 tree s, c, d, bits, assumption, tmp, bound;
973 mpz_t max;
975 niter->control = *iv;
976 niter->bound = final;
977 niter->cmp = NE_EXPR;
979 /* Rearrange the terms so that we get inequality S * i <> C, with S
980 positive. Also cast everything to the unsigned type. If IV does
981 not overflow, BNDS bounds the value of C. Also, this is the
982 case if the computation |FINAL - IV->base| does not overflow, i.e.,
983 if BNDS->below in the result is nonnegative. */
984 if (tree_int_cst_sign_bit (iv->step))
986 s = fold_convert (niter_type,
987 fold_build1 (NEGATE_EXPR, type, iv->step));
988 c = fold_build2 (MINUS_EXPR, niter_type,
989 fold_convert (niter_type, iv->base),
990 fold_convert (niter_type, final));
991 bounds_negate (bnds);
993 else
995 s = fold_convert (niter_type, iv->step);
996 c = fold_build2 (MINUS_EXPR, niter_type,
997 fold_convert (niter_type, final),
998 fold_convert (niter_type, iv->base));
1001 mpz_init (max);
1002 number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds,
1003 exit_must_be_taken);
1004 niter->max = widest_int::from (wi::from_mpz (niter_type, max, false),
1005 TYPE_SIGN (niter_type));
1006 mpz_clear (max);
1008 /* Compute no-overflow information for the control iv. This can be
1009 proven when below two conditions are satisfied:
1011 1) IV evaluates toward FINAL at beginning, i.e:
1012 base <= FINAL ; step > 0
1013 base >= FINAL ; step < 0
1015 2) |FINAL - base| is an exact multiple of step.
1017 Unfortunately, it's hard to prove above conditions after pass loop-ch
1018 because loop with exit condition (IV != FINAL) usually will be guarded
1019 by initial-condition (IV.base - IV.step != FINAL). In this case, we
1020 can alternatively try to prove below conditions:
1022 1') IV evaluates toward FINAL at beginning, i.e:
1023 new_base = base - step < FINAL ; step > 0
1024 && base - step doesn't underflow
1025 new_base = base - step > FINAL ; step < 0
1026 && base - step doesn't overflow
1028 2') |FINAL - new_base| is an exact multiple of step.
1030 Please refer to PR34114 as an example of loop-ch's impact, also refer
1031 to PR72817 as an example why condition 2') is necessary.
1033 Note, for NE_EXPR, base equals to FINAL is a special case, in
1034 which the loop exits immediately, and the iv does not overflow. */
1035 if (!niter->control.no_overflow
1036 && (integer_onep (s) || multiple_of_p (type, c, s)))
1038 tree t, cond, new_c, relaxed_cond = boolean_false_node;
1040 if (tree_int_cst_sign_bit (iv->step))
1042 cond = fold_build2 (GE_EXPR, boolean_type_node, iv->base, final);
1043 if (TREE_CODE (type) == INTEGER_TYPE)
1045 /* Only when base - step doesn't overflow. */
1046 t = TYPE_MAX_VALUE (type);
1047 t = fold_build2 (PLUS_EXPR, type, t, iv->step);
1048 t = fold_build2 (GE_EXPR, boolean_type_node, t, iv->base);
1049 if (integer_nonzerop (t))
1051 t = fold_build2 (MINUS_EXPR, type, iv->base, iv->step);
1052 new_c = fold_build2 (MINUS_EXPR, niter_type,
1053 fold_convert (niter_type, t),
1054 fold_convert (niter_type, final));
1055 if (multiple_of_p (type, new_c, s))
1056 relaxed_cond = fold_build2 (GT_EXPR, boolean_type_node,
1057 t, final);
1061 else
1063 cond = fold_build2 (LE_EXPR, boolean_type_node, iv->base, final);
1064 if (TREE_CODE (type) == INTEGER_TYPE)
1066 /* Only when base - step doesn't underflow. */
1067 t = TYPE_MIN_VALUE (type);
1068 t = fold_build2 (PLUS_EXPR, type, t, iv->step);
1069 t = fold_build2 (LE_EXPR, boolean_type_node, t, iv->base);
1070 if (integer_nonzerop (t))
1072 t = fold_build2 (MINUS_EXPR, type, iv->base, iv->step);
1073 new_c = fold_build2 (MINUS_EXPR, niter_type,
1074 fold_convert (niter_type, final),
1075 fold_convert (niter_type, t));
1076 if (multiple_of_p (type, new_c, s))
1077 relaxed_cond = fold_build2 (LT_EXPR, boolean_type_node,
1078 t, final);
1083 t = simplify_using_initial_conditions (loop, cond);
1084 if (!t || !integer_onep (t))
1085 t = simplify_using_initial_conditions (loop, relaxed_cond);
1087 if (t && integer_onep (t))
1088 niter->control.no_overflow = true;
1091 /* First the trivial cases -- when the step is 1. */
1092 if (integer_onep (s))
1094 niter->niter = c;
1095 return true;
1097 if (niter->control.no_overflow && multiple_of_p (type, c, s))
1099 niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, c, s);
1100 return true;
1103 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
1104 is infinite. Otherwise, the number of iterations is
1105 (inverse(s/d) * (c/d)) mod (size of mode/d). */
1106 bits = num_ending_zeros (s);
1107 bound = build_low_bits_mask (niter_type,
1108 (TYPE_PRECISION (niter_type)
1109 - tree_to_uhwi (bits)));
1111 d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
1112 build_int_cst (niter_type, 1), bits);
1113 s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
1115 if (!exit_must_be_taken)
1117 /* If we cannot assume that the exit is taken eventually, record the
1118 assumptions for divisibility of c. */
1119 assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d);
1120 assumption = fold_build2 (EQ_EXPR, boolean_type_node,
1121 assumption, build_int_cst (niter_type, 0));
1122 if (!integer_nonzerop (assumption))
1123 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1124 niter->assumptions, assumption);
1127 c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d);
1128 tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound));
1129 niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound);
1130 return true;
1133 /* Checks whether we can determine the final value of the control variable
1134 of the loop with ending condition IV0 < IV1 (computed in TYPE).
1135 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
1136 of the step. The assumptions necessary to ensure that the computation
1137 of the final value does not overflow are recorded in NITER. If we
1138 find the final value, we adjust DELTA and return TRUE. Otherwise
1139 we return false. BNDS bounds the value of IV1->base - IV0->base,
1140 and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
1141 true if we know that the exit must be taken eventually. */
1143 static bool
1144 number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1,
1145 struct tree_niter_desc *niter,
1146 tree *delta, tree step,
1147 bool exit_must_be_taken, bounds *bnds)
1149 tree niter_type = TREE_TYPE (step);
1150 tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step);
1151 tree tmod;
1152 mpz_t mmod;
1153 tree assumption = boolean_true_node, bound, noloop;
1154 bool ret = false, fv_comp_no_overflow;
1155 tree type1 = type;
1156 if (POINTER_TYPE_P (type))
1157 type1 = sizetype;
1159 if (TREE_CODE (mod) != INTEGER_CST)
1160 return false;
1161 if (integer_nonzerop (mod))
1162 mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
1163 tmod = fold_convert (type1, mod);
1165 mpz_init (mmod);
1166 wi::to_mpz (wi::to_wide (mod), mmod, UNSIGNED);
1167 mpz_neg (mmod, mmod);
1169 /* If the induction variable does not overflow and the exit is taken,
1170 then the computation of the final value does not overflow. This is
1171 also obviously the case if the new final value is equal to the
1172 current one. Finally, we postulate this for pointer type variables,
1173 as the code cannot rely on the object to that the pointer points being
1174 placed at the end of the address space (and more pragmatically,
1175 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
1176 if (integer_zerop (mod) || POINTER_TYPE_P (type))
1177 fv_comp_no_overflow = true;
1178 else if (!exit_must_be_taken)
1179 fv_comp_no_overflow = false;
1180 else
1181 fv_comp_no_overflow =
1182 (iv0->no_overflow && integer_nonzerop (iv0->step))
1183 || (iv1->no_overflow && integer_nonzerop (iv1->step));
1185 if (integer_nonzerop (iv0->step))
1187 /* The final value of the iv is iv1->base + MOD, assuming that this
1188 computation does not overflow, and that
1189 iv0->base <= iv1->base + MOD. */
1190 if (!fv_comp_no_overflow)
1192 bound = fold_build2 (MINUS_EXPR, type1,
1193 TYPE_MAX_VALUE (type1), tmod);
1194 assumption = fold_build2 (LE_EXPR, boolean_type_node,
1195 iv1->base, bound);
1196 if (integer_zerop (assumption))
1197 goto end;
1199 if (mpz_cmp (mmod, bnds->below) < 0)
1200 noloop = boolean_false_node;
1201 else if (POINTER_TYPE_P (type))
1202 noloop = fold_build2 (GT_EXPR, boolean_type_node,
1203 iv0->base,
1204 fold_build_pointer_plus (iv1->base, tmod));
1205 else
1206 noloop = fold_build2 (GT_EXPR, boolean_type_node,
1207 iv0->base,
1208 fold_build2 (PLUS_EXPR, type1,
1209 iv1->base, tmod));
1211 else
1213 /* The final value of the iv is iv0->base - MOD, assuming that this
1214 computation does not overflow, and that
1215 iv0->base - MOD <= iv1->base. */
1216 if (!fv_comp_no_overflow)
1218 bound = fold_build2 (PLUS_EXPR, type1,
1219 TYPE_MIN_VALUE (type1), tmod);
1220 assumption = fold_build2 (GE_EXPR, boolean_type_node,
1221 iv0->base, bound);
1222 if (integer_zerop (assumption))
1223 goto end;
1225 if (mpz_cmp (mmod, bnds->below) < 0)
1226 noloop = boolean_false_node;
1227 else if (POINTER_TYPE_P (type))
1228 noloop = fold_build2 (GT_EXPR, boolean_type_node,
1229 fold_build_pointer_plus (iv0->base,
1230 fold_build1 (NEGATE_EXPR,
1231 type1, tmod)),
1232 iv1->base);
1233 else
1234 noloop = fold_build2 (GT_EXPR, boolean_type_node,
1235 fold_build2 (MINUS_EXPR, type1,
1236 iv0->base, tmod),
1237 iv1->base);
1240 if (!integer_nonzerop (assumption))
1241 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1242 niter->assumptions,
1243 assumption);
1244 if (!integer_zerop (noloop))
1245 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
1246 niter->may_be_zero,
1247 noloop);
1248 bounds_add (bnds, wi::to_widest (mod), type);
1249 *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod);
1251 ret = true;
1252 end:
1253 mpz_clear (mmod);
1254 return ret;
1257 /* Add assertions to NITER that ensure that the control variable of the loop
1258 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
1259 are TYPE. Returns false if we can prove that there is an overflow, true
1260 otherwise. STEP is the absolute value of the step. */
1262 static bool
1263 assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
1264 struct tree_niter_desc *niter, tree step)
1266 tree bound, d, assumption, diff;
1267 tree niter_type = TREE_TYPE (step);
1269 if (integer_nonzerop (iv0->step))
1271 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
1272 if (iv0->no_overflow)
1273 return true;
1275 /* If iv0->base is a constant, we can determine the last value before
1276 overflow precisely; otherwise we conservatively assume
1277 MAX - STEP + 1. */
1279 if (TREE_CODE (iv0->base) == INTEGER_CST)
1281 d = fold_build2 (MINUS_EXPR, niter_type,
1282 fold_convert (niter_type, TYPE_MAX_VALUE (type)),
1283 fold_convert (niter_type, iv0->base));
1284 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
1286 else
1287 diff = fold_build2 (MINUS_EXPR, niter_type, step,
1288 build_int_cst (niter_type, 1));
1289 bound = fold_build2 (MINUS_EXPR, type,
1290 TYPE_MAX_VALUE (type), fold_convert (type, diff));
1291 assumption = fold_build2 (LE_EXPR, boolean_type_node,
1292 iv1->base, bound);
1294 else
1296 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
1297 if (iv1->no_overflow)
1298 return true;
1300 if (TREE_CODE (iv1->base) == INTEGER_CST)
1302 d = fold_build2 (MINUS_EXPR, niter_type,
1303 fold_convert (niter_type, iv1->base),
1304 fold_convert (niter_type, TYPE_MIN_VALUE (type)));
1305 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
1307 else
1308 diff = fold_build2 (MINUS_EXPR, niter_type, step,
1309 build_int_cst (niter_type, 1));
1310 bound = fold_build2 (PLUS_EXPR, type,
1311 TYPE_MIN_VALUE (type), fold_convert (type, diff));
1312 assumption = fold_build2 (GE_EXPR, boolean_type_node,
1313 iv0->base, bound);
1316 if (integer_zerop (assumption))
1317 return false;
1318 if (!integer_nonzerop (assumption))
1319 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1320 niter->assumptions, assumption);
1322 iv0->no_overflow = true;
1323 iv1->no_overflow = true;
1324 return true;
1327 /* Add an assumption to NITER that a loop whose ending condition
1328 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
1329 bounds the value of IV1->base - IV0->base. */
1331 static void
1332 assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
1333 struct tree_niter_desc *niter, bounds *bnds)
1335 tree assumption = boolean_true_node, bound, diff;
1336 tree mbz, mbzl, mbzr, type1;
1337 bool rolls_p, no_overflow_p;
1338 widest_int dstep;
1339 mpz_t mstep, max;
1341 /* We are going to compute the number of iterations as
1342 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
1343 variant of TYPE. This formula only works if
1345 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
1347 (where MAX is the maximum value of the unsigned variant of TYPE, and
1348 the computations in this formula are performed in full precision,
1349 i.e., without overflows).
1351 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
1352 we have a condition of the form iv0->base - step < iv1->base before the loop,
1353 and for loops iv0->base < iv1->base - step * i the condition
1354 iv0->base < iv1->base + step, due to loop header copying, which enable us
1355 to prove the lower bound.
1357 The upper bound is more complicated. Unless the expressions for initial
1358 and final value themselves contain enough information, we usually cannot
1359 derive it from the context. */
1361 /* First check whether the answer does not follow from the bounds we gathered
1362 before. */
1363 if (integer_nonzerop (iv0->step))
1364 dstep = wi::to_widest (iv0->step);
1365 else
1367 dstep = wi::sext (wi::to_widest (iv1->step), TYPE_PRECISION (type));
1368 dstep = -dstep;
1371 mpz_init (mstep);
1372 wi::to_mpz (dstep, mstep, UNSIGNED);
1373 mpz_neg (mstep, mstep);
1374 mpz_add_ui (mstep, mstep, 1);
1376 rolls_p = mpz_cmp (mstep, bnds->below) <= 0;
1378 mpz_init (max);
1379 wi::to_mpz (wi::minus_one (TYPE_PRECISION (type)), max, UNSIGNED);
1380 mpz_add (max, max, mstep);
1381 no_overflow_p = (mpz_cmp (bnds->up, max) <= 0
1382 /* For pointers, only values lying inside a single object
1383 can be compared or manipulated by pointer arithmetics.
1384 Gcc in general does not allow or handle objects larger
1385 than half of the address space, hence the upper bound
1386 is satisfied for pointers. */
1387 || POINTER_TYPE_P (type));
1388 mpz_clear (mstep);
1389 mpz_clear (max);
1391 if (rolls_p && no_overflow_p)
1392 return;
1394 type1 = type;
1395 if (POINTER_TYPE_P (type))
1396 type1 = sizetype;
1398 /* Now the hard part; we must formulate the assumption(s) as expressions, and
1399 we must be careful not to introduce overflow. */
1401 if (integer_nonzerop (iv0->step))
1403 diff = fold_build2 (MINUS_EXPR, type1,
1404 iv0->step, build_int_cst (type1, 1));
1406 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
1407 0 address never belongs to any object, we can assume this for
1408 pointers. */
1409 if (!POINTER_TYPE_P (type))
1411 bound = fold_build2 (PLUS_EXPR, type1,
1412 TYPE_MIN_VALUE (type), diff);
1413 assumption = fold_build2 (GE_EXPR, boolean_type_node,
1414 iv0->base, bound);
1417 /* And then we can compute iv0->base - diff, and compare it with
1418 iv1->base. */
1419 mbzl = fold_build2 (MINUS_EXPR, type1,
1420 fold_convert (type1, iv0->base), diff);
1421 mbzr = fold_convert (type1, iv1->base);
1423 else
1425 diff = fold_build2 (PLUS_EXPR, type1,
1426 iv1->step, build_int_cst (type1, 1));
1428 if (!POINTER_TYPE_P (type))
1430 bound = fold_build2 (PLUS_EXPR, type1,
1431 TYPE_MAX_VALUE (type), diff);
1432 assumption = fold_build2 (LE_EXPR, boolean_type_node,
1433 iv1->base, bound);
1436 mbzl = fold_convert (type1, iv0->base);
1437 mbzr = fold_build2 (MINUS_EXPR, type1,
1438 fold_convert (type1, iv1->base), diff);
1441 if (!integer_nonzerop (assumption))
1442 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1443 niter->assumptions, assumption);
1444 if (!rolls_p)
1446 mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr);
1447 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
1448 niter->may_be_zero, mbz);
1452 /* Determines number of iterations of loop whose ending condition
1453 is IV0 < IV1. TYPE is the type of the iv. The number of
1454 iterations is stored to NITER. BNDS bounds the difference
1455 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
1456 that the exit must be taken eventually. */
1458 static bool
1459 number_of_iterations_lt (struct loop *loop, tree type, affine_iv *iv0,
1460 affine_iv *iv1, struct tree_niter_desc *niter,
1461 bool exit_must_be_taken, bounds *bnds)
1463 tree niter_type = unsigned_type_for (type);
1464 tree delta, step, s;
1465 mpz_t mstep, tmp;
1467 if (integer_nonzerop (iv0->step))
1469 niter->control = *iv0;
1470 niter->cmp = LT_EXPR;
1471 niter->bound = iv1->base;
1473 else
1475 niter->control = *iv1;
1476 niter->cmp = GT_EXPR;
1477 niter->bound = iv0->base;
1480 delta = fold_build2 (MINUS_EXPR, niter_type,
1481 fold_convert (niter_type, iv1->base),
1482 fold_convert (niter_type, iv0->base));
1484 /* First handle the special case that the step is +-1. */
1485 if ((integer_onep (iv0->step) && integer_zerop (iv1->step))
1486 || (integer_all_onesp (iv1->step) && integer_zerop (iv0->step)))
1488 /* for (i = iv0->base; i < iv1->base; i++)
1492 for (i = iv1->base; i > iv0->base; i--).
1494 In both cases # of iterations is iv1->base - iv0->base, assuming that
1495 iv1->base >= iv0->base.
1497 First try to derive a lower bound on the value of
1498 iv1->base - iv0->base, computed in full precision. If the difference
1499 is nonnegative, we are done, otherwise we must record the
1500 condition. */
1502 if (mpz_sgn (bnds->below) < 0)
1503 niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
1504 iv1->base, iv0->base);
1505 niter->niter = delta;
1506 niter->max = widest_int::from (wi::from_mpz (niter_type, bnds->up, false),
1507 TYPE_SIGN (niter_type));
1508 niter->control.no_overflow = true;
1509 return true;
1512 if (integer_nonzerop (iv0->step))
1513 step = fold_convert (niter_type, iv0->step);
1514 else
1515 step = fold_convert (niter_type,
1516 fold_build1 (NEGATE_EXPR, type, iv1->step));
1518 /* If we can determine the final value of the control iv exactly, we can
1519 transform the condition to != comparison. In particular, this will be
1520 the case if DELTA is constant. */
1521 if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step,
1522 exit_must_be_taken, bnds))
1524 affine_iv zps;
1526 zps.base = build_int_cst (niter_type, 0);
1527 zps.step = step;
1528 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1529 zps does not overflow. */
1530 zps.no_overflow = true;
1532 return number_of_iterations_ne (loop, type, &zps,
1533 delta, niter, true, bnds);
1536 /* Make sure that the control iv does not overflow. */
1537 if (!assert_no_overflow_lt (type, iv0, iv1, niter, step))
1538 return false;
1540 /* We determine the number of iterations as (delta + step - 1) / step. For
1541 this to work, we must know that iv1->base >= iv0->base - step + 1,
1542 otherwise the loop does not roll. */
1543 assert_loop_rolls_lt (type, iv0, iv1, niter, bnds);
1545 s = fold_build2 (MINUS_EXPR, niter_type,
1546 step, build_int_cst (niter_type, 1));
1547 delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
1548 niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
1550 mpz_init (mstep);
1551 mpz_init (tmp);
1552 wi::to_mpz (wi::to_wide (step), mstep, UNSIGNED);
1553 mpz_add (tmp, bnds->up, mstep);
1554 mpz_sub_ui (tmp, tmp, 1);
1555 mpz_fdiv_q (tmp, tmp, mstep);
1556 niter->max = widest_int::from (wi::from_mpz (niter_type, tmp, false),
1557 TYPE_SIGN (niter_type));
1558 mpz_clear (mstep);
1559 mpz_clear (tmp);
1561 return true;
1564 /* Determines number of iterations of loop whose ending condition
1565 is IV0 <= IV1. TYPE is the type of the iv. The number of
1566 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
1567 we know that this condition must eventually become false (we derived this
1568 earlier, and possibly set NITER->assumptions to make sure this
1569 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1571 static bool
1572 number_of_iterations_le (struct loop *loop, tree type, affine_iv *iv0,
1573 affine_iv *iv1, struct tree_niter_desc *niter,
1574 bool exit_must_be_taken, bounds *bnds)
1576 tree assumption;
1577 tree type1 = type;
1578 if (POINTER_TYPE_P (type))
1579 type1 = sizetype;
1581 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1582 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1583 value of the type. This we must know anyway, since if it is
1584 equal to this value, the loop rolls forever. We do not check
1585 this condition for pointer type ivs, as the code cannot rely on
1586 the object to that the pointer points being placed at the end of
1587 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1588 not defined for pointers). */
1590 if (!exit_must_be_taken && !POINTER_TYPE_P (type))
1592 if (integer_nonzerop (iv0->step))
1593 assumption = fold_build2 (NE_EXPR, boolean_type_node,
1594 iv1->base, TYPE_MAX_VALUE (type));
1595 else
1596 assumption = fold_build2 (NE_EXPR, boolean_type_node,
1597 iv0->base, TYPE_MIN_VALUE (type));
1599 if (integer_zerop (assumption))
1600 return false;
1601 if (!integer_nonzerop (assumption))
1602 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1603 niter->assumptions, assumption);
1606 if (integer_nonzerop (iv0->step))
1608 if (POINTER_TYPE_P (type))
1609 iv1->base = fold_build_pointer_plus_hwi (iv1->base, 1);
1610 else
1611 iv1->base = fold_build2 (PLUS_EXPR, type1, iv1->base,
1612 build_int_cst (type1, 1));
1614 else if (POINTER_TYPE_P (type))
1615 iv0->base = fold_build_pointer_plus_hwi (iv0->base, -1);
1616 else
1617 iv0->base = fold_build2 (MINUS_EXPR, type1,
1618 iv0->base, build_int_cst (type1, 1));
1620 bounds_add (bnds, 1, type1);
1622 return number_of_iterations_lt (loop, type, iv0, iv1, niter, exit_must_be_taken,
1623 bnds);
1626 /* Dumps description of affine induction variable IV to FILE. */
1628 static void
1629 dump_affine_iv (FILE *file, affine_iv *iv)
1631 if (!integer_zerop (iv->step))
1632 fprintf (file, "[");
1634 print_generic_expr (dump_file, iv->base, TDF_SLIM);
1636 if (!integer_zerop (iv->step))
1638 fprintf (file, ", + , ");
1639 print_generic_expr (dump_file, iv->step, TDF_SLIM);
1640 fprintf (file, "]%s", iv->no_overflow ? "(no_overflow)" : "");
1644 /* Determine the number of iterations according to condition (for staying
1645 inside loop) which compares two induction variables using comparison
1646 operator CODE. The induction variable on left side of the comparison
1647 is IV0, the right-hand side is IV1. Both induction variables must have
1648 type TYPE, which must be an integer or pointer type. The steps of the
1649 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1651 LOOP is the loop whose number of iterations we are determining.
1653 ONLY_EXIT is true if we are sure this is the only way the loop could be
1654 exited (including possibly non-returning function calls, exceptions, etc.)
1655 -- in this case we can use the information whether the control induction
1656 variables can overflow or not in a more efficient way.
1658 if EVERY_ITERATION is true, we know the test is executed on every iteration.
1660 The results (number of iterations and assumptions as described in
1661 comments at struct tree_niter_desc in tree-ssa-loop.h) are stored to NITER.
1662 Returns false if it fails to determine number of iterations, true if it
1663 was determined (possibly with some assumptions). */
1665 static bool
1666 number_of_iterations_cond (struct loop *loop,
1667 tree type, affine_iv *iv0, enum tree_code code,
1668 affine_iv *iv1, struct tree_niter_desc *niter,
1669 bool only_exit, bool every_iteration)
1671 bool exit_must_be_taken = false, ret;
1672 bounds bnds;
1674 /* If the test is not executed every iteration, wrapping may make the test
1675 to pass again.
1676 TODO: the overflow case can be still used as unreliable estimate of upper
1677 bound. But we have no API to pass it down to number of iterations code
1678 and, at present, it will not use it anyway. */
1679 if (!every_iteration
1680 && (!iv0->no_overflow || !iv1->no_overflow
1681 || code == NE_EXPR || code == EQ_EXPR))
1682 return false;
1684 /* The meaning of these assumptions is this:
1685 if !assumptions
1686 then the rest of information does not have to be valid
1687 if may_be_zero then the loop does not roll, even if
1688 niter != 0. */
1689 niter->assumptions = boolean_true_node;
1690 niter->may_be_zero = boolean_false_node;
1691 niter->niter = NULL_TREE;
1692 niter->max = 0;
1693 niter->bound = NULL_TREE;
1694 niter->cmp = ERROR_MARK;
1696 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1697 the control variable is on lhs. */
1698 if (code == GE_EXPR || code == GT_EXPR
1699 || (code == NE_EXPR && integer_zerop (iv0->step)))
1701 std::swap (iv0, iv1);
1702 code = swap_tree_comparison (code);
1705 if (POINTER_TYPE_P (type))
1707 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1708 to the same object. If they do, the control variable cannot wrap
1709 (as wrap around the bounds of memory will never return a pointer
1710 that would be guaranteed to point to the same object, even if we
1711 avoid undefined behavior by casting to size_t and back). */
1712 iv0->no_overflow = true;
1713 iv1->no_overflow = true;
1716 /* If the control induction variable does not overflow and the only exit
1717 from the loop is the one that we analyze, we know it must be taken
1718 eventually. */
1719 if (only_exit)
1721 if (!integer_zerop (iv0->step) && iv0->no_overflow)
1722 exit_must_be_taken = true;
1723 else if (!integer_zerop (iv1->step) && iv1->no_overflow)
1724 exit_must_be_taken = true;
1727 /* We can handle cases which neither of the sides of the comparison is
1728 invariant:
1730 {iv0.base, iv0.step} cmp_code {iv1.base, iv1.step}
1731 as if:
1732 {iv0.base, iv0.step - iv1.step} cmp_code {iv1.base, 0}
1734 provided that either below condition is satisfied:
1736 a) the test is NE_EXPR;
1737 b) iv0.step - iv1.step is integer and iv0/iv1 don't overflow.
1739 This rarely occurs in practice, but it is simple enough to manage. */
1740 if (!integer_zerop (iv0->step) && !integer_zerop (iv1->step))
1742 tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
1743 tree step = fold_binary_to_constant (MINUS_EXPR, step_type,
1744 iv0->step, iv1->step);
1746 /* No need to check sign of the new step since below code takes care
1747 of this well. */
1748 if (code != NE_EXPR
1749 && (TREE_CODE (step) != INTEGER_CST
1750 || !iv0->no_overflow || !iv1->no_overflow))
1751 return false;
1753 iv0->step = step;
1754 if (!POINTER_TYPE_P (type))
1755 iv0->no_overflow = false;
1757 iv1->step = build_int_cst (step_type, 0);
1758 iv1->no_overflow = true;
1761 /* If the result of the comparison is a constant, the loop is weird. More
1762 precise handling would be possible, but the situation is not common enough
1763 to waste time on it. */
1764 if (integer_zerop (iv0->step) && integer_zerop (iv1->step))
1765 return false;
1767 /* Ignore loops of while (i-- < 10) type. */
1768 if (code != NE_EXPR)
1770 if (iv0->step && tree_int_cst_sign_bit (iv0->step))
1771 return false;
1773 if (!integer_zerop (iv1->step) && !tree_int_cst_sign_bit (iv1->step))
1774 return false;
1777 /* If the loop exits immediately, there is nothing to do. */
1778 tree tem = fold_binary (code, boolean_type_node, iv0->base, iv1->base);
1779 if (tem && integer_zerop (tem))
1781 niter->niter = build_int_cst (unsigned_type_for (type), 0);
1782 niter->max = 0;
1783 return true;
1786 /* OK, now we know we have a senseful loop. Handle several cases, depending
1787 on what comparison operator is used. */
1788 bound_difference (loop, iv1->base, iv0->base, &bnds);
1790 if (dump_file && (dump_flags & TDF_DETAILS))
1792 fprintf (dump_file,
1793 "Analyzing # of iterations of loop %d\n", loop->num);
1795 fprintf (dump_file, " exit condition ");
1796 dump_affine_iv (dump_file, iv0);
1797 fprintf (dump_file, " %s ",
1798 code == NE_EXPR ? "!="
1799 : code == LT_EXPR ? "<"
1800 : "<=");
1801 dump_affine_iv (dump_file, iv1);
1802 fprintf (dump_file, "\n");
1804 fprintf (dump_file, " bounds on difference of bases: ");
1805 mpz_out_str (dump_file, 10, bnds.below);
1806 fprintf (dump_file, " ... ");
1807 mpz_out_str (dump_file, 10, bnds.up);
1808 fprintf (dump_file, "\n");
1811 switch (code)
1813 case NE_EXPR:
1814 gcc_assert (integer_zerop (iv1->step));
1815 ret = number_of_iterations_ne (loop, type, iv0, iv1->base, niter,
1816 exit_must_be_taken, &bnds);
1817 break;
1819 case LT_EXPR:
1820 ret = number_of_iterations_lt (loop, type, iv0, iv1, niter,
1821 exit_must_be_taken, &bnds);
1822 break;
1824 case LE_EXPR:
1825 ret = number_of_iterations_le (loop, type, iv0, iv1, niter,
1826 exit_must_be_taken, &bnds);
1827 break;
1829 default:
1830 gcc_unreachable ();
1833 mpz_clear (bnds.up);
1834 mpz_clear (bnds.below);
1836 if (dump_file && (dump_flags & TDF_DETAILS))
1838 if (ret)
1840 fprintf (dump_file, " result:\n");
1841 if (!integer_nonzerop (niter->assumptions))
1843 fprintf (dump_file, " under assumptions ");
1844 print_generic_expr (dump_file, niter->assumptions, TDF_SLIM);
1845 fprintf (dump_file, "\n");
1848 if (!integer_zerop (niter->may_be_zero))
1850 fprintf (dump_file, " zero if ");
1851 print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
1852 fprintf (dump_file, "\n");
1855 fprintf (dump_file, " # of iterations ");
1856 print_generic_expr (dump_file, niter->niter, TDF_SLIM);
1857 fprintf (dump_file, ", bounded by ");
1858 print_decu (niter->max, dump_file);
1859 fprintf (dump_file, "\n");
1861 else
1862 fprintf (dump_file, " failed\n\n");
1864 return ret;
1867 /* Substitute NEW for OLD in EXPR and fold the result. */
1869 static tree
1870 simplify_replace_tree (tree expr, tree old, tree new_tree)
1872 unsigned i, n;
1873 tree ret = NULL_TREE, e, se;
1875 if (!expr)
1876 return NULL_TREE;
1878 /* Do not bother to replace constants. */
1879 if (CONSTANT_CLASS_P (old))
1880 return expr;
1882 if (expr == old
1883 || operand_equal_p (expr, old, 0))
1884 return unshare_expr (new_tree);
1886 if (!EXPR_P (expr))
1887 return expr;
1889 n = TREE_OPERAND_LENGTH (expr);
1890 for (i = 0; i < n; i++)
1892 e = TREE_OPERAND (expr, i);
1893 se = simplify_replace_tree (e, old, new_tree);
1894 if (e == se)
1895 continue;
1897 if (!ret)
1898 ret = copy_node (expr);
1900 TREE_OPERAND (ret, i) = se;
1903 return (ret ? fold (ret) : expr);
1906 /* Expand definitions of ssa names in EXPR as long as they are simple
1907 enough, and return the new expression. If STOP is specified, stop
1908 expanding if EXPR equals to it. */
1910 tree
1911 expand_simple_operations (tree expr, tree stop)
1913 unsigned i, n;
1914 tree ret = NULL_TREE, e, ee, e1;
1915 enum tree_code code;
1916 gimple *stmt;
1918 if (expr == NULL_TREE)
1919 return expr;
1921 if (is_gimple_min_invariant (expr))
1922 return expr;
1924 code = TREE_CODE (expr);
1925 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
1927 n = TREE_OPERAND_LENGTH (expr);
1928 for (i = 0; i < n; i++)
1930 e = TREE_OPERAND (expr, i);
1931 ee = expand_simple_operations (e, stop);
1932 if (e == ee)
1933 continue;
1935 if (!ret)
1936 ret = copy_node (expr);
1938 TREE_OPERAND (ret, i) = ee;
1941 if (!ret)
1942 return expr;
1944 fold_defer_overflow_warnings ();
1945 ret = fold (ret);
1946 fold_undefer_and_ignore_overflow_warnings ();
1947 return ret;
1950 /* Stop if it's not ssa name or the one we don't want to expand. */
1951 if (TREE_CODE (expr) != SSA_NAME || expr == stop)
1952 return expr;
1954 stmt = SSA_NAME_DEF_STMT (expr);
1955 if (gimple_code (stmt) == GIMPLE_PHI)
1957 basic_block src, dest;
1959 if (gimple_phi_num_args (stmt) != 1)
1960 return expr;
1961 e = PHI_ARG_DEF (stmt, 0);
1963 /* Avoid propagating through loop exit phi nodes, which
1964 could break loop-closed SSA form restrictions. */
1965 dest = gimple_bb (stmt);
1966 src = single_pred (dest);
1967 if (TREE_CODE (e) == SSA_NAME
1968 && src->loop_father != dest->loop_father)
1969 return expr;
1971 return expand_simple_operations (e, stop);
1973 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1974 return expr;
1976 /* Avoid expanding to expressions that contain SSA names that need
1977 to take part in abnormal coalescing. */
1978 ssa_op_iter iter;
1979 FOR_EACH_SSA_TREE_OPERAND (e, stmt, iter, SSA_OP_USE)
1980 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (e))
1981 return expr;
1983 e = gimple_assign_rhs1 (stmt);
1984 code = gimple_assign_rhs_code (stmt);
1985 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1987 if (is_gimple_min_invariant (e))
1988 return e;
1990 if (code == SSA_NAME)
1991 return expand_simple_operations (e, stop);
1992 else if (code == ADDR_EXPR)
1994 poly_int64 offset;
1995 tree base = get_addr_base_and_unit_offset (TREE_OPERAND (e, 0),
1996 &offset);
1997 if (base
1998 && TREE_CODE (base) == MEM_REF)
2000 ee = expand_simple_operations (TREE_OPERAND (base, 0), stop);
2001 return fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (expr), ee,
2002 wide_int_to_tree (sizetype,
2003 mem_ref_offset (base)
2004 + offset));
2008 return expr;
2011 switch (code)
2013 CASE_CONVERT:
2014 /* Casts are simple. */
2015 ee = expand_simple_operations (e, stop);
2016 return fold_build1 (code, TREE_TYPE (expr), ee);
2018 case PLUS_EXPR:
2019 case MINUS_EXPR:
2020 if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (expr))
2021 && TYPE_OVERFLOW_TRAPS (TREE_TYPE (expr)))
2022 return expr;
2023 /* Fallthru. */
2024 case POINTER_PLUS_EXPR:
2025 /* And increments and decrements by a constant are simple. */
2026 e1 = gimple_assign_rhs2 (stmt);
2027 if (!is_gimple_min_invariant (e1))
2028 return expr;
2030 ee = expand_simple_operations (e, stop);
2031 return fold_build2 (code, TREE_TYPE (expr), ee, e1);
2033 default:
2034 return expr;
2038 /* Tries to simplify EXPR using the condition COND. Returns the simplified
2039 expression (or EXPR unchanged, if no simplification was possible). */
2041 static tree
2042 tree_simplify_using_condition_1 (tree cond, tree expr)
2044 bool changed;
2045 tree e, e0, e1, e2, notcond;
2046 enum tree_code code = TREE_CODE (expr);
2048 if (code == INTEGER_CST)
2049 return expr;
2051 if (code == TRUTH_OR_EXPR
2052 || code == TRUTH_AND_EXPR
2053 || code == COND_EXPR)
2055 changed = false;
2057 e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0));
2058 if (TREE_OPERAND (expr, 0) != e0)
2059 changed = true;
2061 e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1));
2062 if (TREE_OPERAND (expr, 1) != e1)
2063 changed = true;
2065 if (code == COND_EXPR)
2067 e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2));
2068 if (TREE_OPERAND (expr, 2) != e2)
2069 changed = true;
2071 else
2072 e2 = NULL_TREE;
2074 if (changed)
2076 if (code == COND_EXPR)
2077 expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
2078 else
2079 expr = fold_build2 (code, boolean_type_node, e0, e1);
2082 return expr;
2085 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
2086 propagation, and vice versa. Fold does not handle this, since it is
2087 considered too expensive. */
2088 if (TREE_CODE (cond) == EQ_EXPR)
2090 e0 = TREE_OPERAND (cond, 0);
2091 e1 = TREE_OPERAND (cond, 1);
2093 /* We know that e0 == e1. Check whether we cannot simplify expr
2094 using this fact. */
2095 e = simplify_replace_tree (expr, e0, e1);
2096 if (integer_zerop (e) || integer_nonzerop (e))
2097 return e;
2099 e = simplify_replace_tree (expr, e1, e0);
2100 if (integer_zerop (e) || integer_nonzerop (e))
2101 return e;
2103 if (TREE_CODE (expr) == EQ_EXPR)
2105 e0 = TREE_OPERAND (expr, 0);
2106 e1 = TREE_OPERAND (expr, 1);
2108 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
2109 e = simplify_replace_tree (cond, e0, e1);
2110 if (integer_zerop (e))
2111 return e;
2112 e = simplify_replace_tree (cond, e1, e0);
2113 if (integer_zerop (e))
2114 return e;
2116 if (TREE_CODE (expr) == NE_EXPR)
2118 e0 = TREE_OPERAND (expr, 0);
2119 e1 = TREE_OPERAND (expr, 1);
2121 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
2122 e = simplify_replace_tree (cond, e0, e1);
2123 if (integer_zerop (e))
2124 return boolean_true_node;
2125 e = simplify_replace_tree (cond, e1, e0);
2126 if (integer_zerop (e))
2127 return boolean_true_node;
2130 /* Check whether COND ==> EXPR. */
2131 notcond = invert_truthvalue (cond);
2132 e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, expr);
2133 if (e && integer_nonzerop (e))
2134 return e;
2136 /* Check whether COND ==> not EXPR. */
2137 e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, expr);
2138 if (e && integer_zerop (e))
2139 return e;
2141 return expr;
2144 /* Tries to simplify EXPR using the condition COND. Returns the simplified
2145 expression (or EXPR unchanged, if no simplification was possible).
2146 Wrapper around tree_simplify_using_condition_1 that ensures that chains
2147 of simple operations in definitions of ssa names in COND are expanded,
2148 so that things like casts or incrementing the value of the bound before
2149 the loop do not cause us to fail. */
2151 static tree
2152 tree_simplify_using_condition (tree cond, tree expr)
2154 cond = expand_simple_operations (cond);
2156 return tree_simplify_using_condition_1 (cond, expr);
2159 /* Tries to simplify EXPR using the conditions on entry to LOOP.
2160 Returns the simplified expression (or EXPR unchanged, if no
2161 simplification was possible). */
2163 tree
2164 simplify_using_initial_conditions (struct loop *loop, tree expr)
2166 edge e;
2167 basic_block bb;
2168 gimple *stmt;
2169 tree cond, expanded, backup;
2170 int cnt = 0;
2172 if (TREE_CODE (expr) == INTEGER_CST)
2173 return expr;
2175 backup = expanded = expand_simple_operations (expr);
2177 /* Limit walking the dominators to avoid quadraticness in
2178 the number of BBs times the number of loops in degenerate
2179 cases. */
2180 for (bb = loop->header;
2181 bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) && cnt < MAX_DOMINATORS_TO_WALK;
2182 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
2184 if (!single_pred_p (bb))
2185 continue;
2186 e = single_pred_edge (bb);
2188 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
2189 continue;
2191 stmt = last_stmt (e->src);
2192 cond = fold_build2 (gimple_cond_code (stmt),
2193 boolean_type_node,
2194 gimple_cond_lhs (stmt),
2195 gimple_cond_rhs (stmt));
2196 if (e->flags & EDGE_FALSE_VALUE)
2197 cond = invert_truthvalue (cond);
2198 expanded = tree_simplify_using_condition (cond, expanded);
2199 /* Break if EXPR is simplified to const values. */
2200 if (expanded
2201 && (integer_zerop (expanded) || integer_nonzerop (expanded)))
2202 return expanded;
2204 ++cnt;
2207 /* Return the original expression if no simplification is done. */
2208 return operand_equal_p (backup, expanded, 0) ? expr : expanded;
2211 /* Tries to simplify EXPR using the evolutions of the loop invariants
2212 in the superloops of LOOP. Returns the simplified expression
2213 (or EXPR unchanged, if no simplification was possible). */
2215 static tree
2216 simplify_using_outer_evolutions (struct loop *loop, tree expr)
2218 enum tree_code code = TREE_CODE (expr);
2219 bool changed;
2220 tree e, e0, e1, e2;
2222 if (is_gimple_min_invariant (expr))
2223 return expr;
2225 if (code == TRUTH_OR_EXPR
2226 || code == TRUTH_AND_EXPR
2227 || code == COND_EXPR)
2229 changed = false;
2231 e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
2232 if (TREE_OPERAND (expr, 0) != e0)
2233 changed = true;
2235 e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
2236 if (TREE_OPERAND (expr, 1) != e1)
2237 changed = true;
2239 if (code == COND_EXPR)
2241 e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
2242 if (TREE_OPERAND (expr, 2) != e2)
2243 changed = true;
2245 else
2246 e2 = NULL_TREE;
2248 if (changed)
2250 if (code == COND_EXPR)
2251 expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
2252 else
2253 expr = fold_build2 (code, boolean_type_node, e0, e1);
2256 return expr;
2259 e = instantiate_parameters (loop, expr);
2260 if (is_gimple_min_invariant (e))
2261 return e;
2263 return expr;
2266 /* Returns true if EXIT is the only possible exit from LOOP. */
2268 bool
2269 loop_only_exit_p (const struct loop *loop, const_edge exit)
2271 basic_block *body;
2272 gimple_stmt_iterator bsi;
2273 unsigned i;
2275 if (exit != single_exit (loop))
2276 return false;
2278 body = get_loop_body (loop);
2279 for (i = 0; i < loop->num_nodes; i++)
2281 for (bsi = gsi_start_bb (body[i]); !gsi_end_p (bsi); gsi_next (&bsi))
2282 if (stmt_can_terminate_bb_p (gsi_stmt (bsi)))
2284 free (body);
2285 return true;
2289 free (body);
2290 return true;
2293 /* Stores description of number of iterations of LOOP derived from
2294 EXIT (an exit edge of the LOOP) in NITER. Returns true if some useful
2295 information could be derived (and fields of NITER have meaning described
2296 in comments at struct tree_niter_desc declaration), false otherwise.
2297 When EVERY_ITERATION is true, only tests that are known to be executed
2298 every iteration are considered (i.e. only test that alone bounds the loop).
2299 If AT_STMT is not NULL, this function stores LOOP's condition statement in
2300 it when returning true. */
2302 bool
2303 number_of_iterations_exit_assumptions (struct loop *loop, edge exit,
2304 struct tree_niter_desc *niter,
2305 gcond **at_stmt, bool every_iteration)
2307 gimple *last;
2308 gcond *stmt;
2309 tree type;
2310 tree op0, op1;
2311 enum tree_code code;
2312 affine_iv iv0, iv1;
2313 bool safe;
2315 /* Nothing to analyze if the loop is known to be infinite. */
2316 if (loop_constraint_set_p (loop, LOOP_C_INFINITE))
2317 return false;
2319 safe = dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src);
2321 if (every_iteration && !safe)
2322 return false;
2324 niter->assumptions = boolean_false_node;
2325 niter->control.base = NULL_TREE;
2326 niter->control.step = NULL_TREE;
2327 niter->control.no_overflow = false;
2328 last = last_stmt (exit->src);
2329 if (!last)
2330 return false;
2331 stmt = dyn_cast <gcond *> (last);
2332 if (!stmt)
2333 return false;
2335 /* We want the condition for staying inside loop. */
2336 code = gimple_cond_code (stmt);
2337 if (exit->flags & EDGE_TRUE_VALUE)
2338 code = invert_tree_comparison (code, false);
2340 switch (code)
2342 case GT_EXPR:
2343 case GE_EXPR:
2344 case LT_EXPR:
2345 case LE_EXPR:
2346 case NE_EXPR:
2347 break;
2349 default:
2350 return false;
2353 op0 = gimple_cond_lhs (stmt);
2354 op1 = gimple_cond_rhs (stmt);
2355 type = TREE_TYPE (op0);
2357 if (TREE_CODE (type) != INTEGER_TYPE
2358 && !POINTER_TYPE_P (type))
2359 return false;
2361 tree iv0_niters = NULL_TREE;
2362 if (!simple_iv_with_niters (loop, loop_containing_stmt (stmt),
2363 op0, &iv0, safe ? &iv0_niters : NULL, false))
2364 return number_of_iterations_popcount (loop, exit, code, niter);
2365 tree iv1_niters = NULL_TREE;
2366 if (!simple_iv_with_niters (loop, loop_containing_stmt (stmt),
2367 op1, &iv1, safe ? &iv1_niters : NULL, false))
2368 return false;
2369 /* Give up on complicated case. */
2370 if (iv0_niters && iv1_niters)
2371 return false;
2373 /* We don't want to see undefined signed overflow warnings while
2374 computing the number of iterations. */
2375 fold_defer_overflow_warnings ();
2377 iv0.base = expand_simple_operations (iv0.base);
2378 iv1.base = expand_simple_operations (iv1.base);
2379 if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter,
2380 loop_only_exit_p (loop, exit), safe))
2382 fold_undefer_and_ignore_overflow_warnings ();
2383 return false;
2386 /* Incorporate additional assumption implied by control iv. */
2387 tree iv_niters = iv0_niters ? iv0_niters : iv1_niters;
2388 if (iv_niters)
2390 tree assumption = fold_build2 (LE_EXPR, boolean_type_node, niter->niter,
2391 fold_convert (TREE_TYPE (niter->niter),
2392 iv_niters));
2394 if (!integer_nonzerop (assumption))
2395 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
2396 niter->assumptions, assumption);
2398 /* Refine upper bound if possible. */
2399 if (TREE_CODE (iv_niters) == INTEGER_CST
2400 && niter->max > wi::to_widest (iv_niters))
2401 niter->max = wi::to_widest (iv_niters);
2404 /* There is no assumptions if the loop is known to be finite. */
2405 if (!integer_zerop (niter->assumptions)
2406 && loop_constraint_set_p (loop, LOOP_C_FINITE))
2407 niter->assumptions = boolean_true_node;
2409 if (optimize >= 3)
2411 niter->assumptions = simplify_using_outer_evolutions (loop,
2412 niter->assumptions);
2413 niter->may_be_zero = simplify_using_outer_evolutions (loop,
2414 niter->may_be_zero);
2415 niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
2418 niter->assumptions
2419 = simplify_using_initial_conditions (loop,
2420 niter->assumptions);
2421 niter->may_be_zero
2422 = simplify_using_initial_conditions (loop,
2423 niter->may_be_zero);
2425 fold_undefer_and_ignore_overflow_warnings ();
2427 /* If NITER has simplified into a constant, update MAX. */
2428 if (TREE_CODE (niter->niter) == INTEGER_CST)
2429 niter->max = wi::to_widest (niter->niter);
2431 if (at_stmt)
2432 *at_stmt = stmt;
2434 return (!integer_zerop (niter->assumptions));
2438 /* Utility function to check if OP is defined by a stmt
2439 that is a val - 1. */
2441 static bool
2442 ssa_defined_by_minus_one_stmt_p (tree op, tree val)
2444 gimple *stmt;
2445 return (TREE_CODE (op) == SSA_NAME
2446 && (stmt = SSA_NAME_DEF_STMT (op))
2447 && is_gimple_assign (stmt)
2448 && (gimple_assign_rhs_code (stmt) == PLUS_EXPR)
2449 && val == gimple_assign_rhs1 (stmt)
2450 && integer_minus_onep (gimple_assign_rhs2 (stmt)));
2454 /* See if LOOP is a popcout implementation, determine NITER for the loop
2456 We match:
2457 <bb 2>
2458 goto <bb 4>
2460 <bb 3>
2461 _1 = b_11 + -1
2462 b_6 = _1 & b_11
2464 <bb 4>
2465 b_11 = PHI <b_5(D)(2), b_6(3)>
2467 exit block
2468 if (b_11 != 0)
2469 goto <bb 3>
2470 else
2471 goto <bb 5>
2473 OR we match copy-header version:
2474 if (b_5 != 0)
2475 goto <bb 3>
2476 else
2477 goto <bb 4>
2479 <bb 3>
2480 b_11 = PHI <b_5(2), b_6(3)>
2481 _1 = b_11 + -1
2482 b_6 = _1 & b_11
2484 exit block
2485 if (b_6 != 0)
2486 goto <bb 3>
2487 else
2488 goto <bb 4>
2490 If popcount pattern, update NITER accordingly.
2491 i.e., set NITER to __builtin_popcount (b)
2492 return true if we did, false otherwise.
2496 static bool
2497 number_of_iterations_popcount (loop_p loop, edge exit,
2498 enum tree_code code,
2499 struct tree_niter_desc *niter)
2501 bool adjust = true;
2502 tree iter;
2503 HOST_WIDE_INT max;
2504 adjust = true;
2505 tree fn = NULL_TREE;
2507 /* Check loop terminating branch is like
2508 if (b != 0). */
2509 gimple *stmt = last_stmt (exit->src);
2510 if (!stmt
2511 || gimple_code (stmt) != GIMPLE_COND
2512 || code != NE_EXPR
2513 || !integer_zerop (gimple_cond_rhs (stmt))
2514 || TREE_CODE (gimple_cond_lhs (stmt)) != SSA_NAME)
2515 return false;
2517 gimple *and_stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt));
2519 /* Depending on copy-header is performed, feeding PHI stmts might be in
2520 the loop header or loop latch, handle this. */
2521 if (gimple_code (and_stmt) == GIMPLE_PHI
2522 && gimple_bb (and_stmt) == loop->header
2523 && gimple_phi_num_args (and_stmt) == 2
2524 && (TREE_CODE (gimple_phi_arg_def (and_stmt,
2525 loop_latch_edge (loop)->dest_idx))
2526 == SSA_NAME))
2528 /* SSA used in exit condition is defined by PHI stmt
2529 b_11 = PHI <b_5(D)(2), b_6(3)>
2530 from the PHI stmt, get the and_stmt
2531 b_6 = _1 & b_11. */
2532 tree t = gimple_phi_arg_def (and_stmt, loop_latch_edge (loop)->dest_idx);
2533 and_stmt = SSA_NAME_DEF_STMT (t);
2534 adjust = false;
2537 /* Make sure it is indeed an and stmt (b_6 = _1 & b_11). */
2538 if (!is_gimple_assign (and_stmt)
2539 || gimple_assign_rhs_code (and_stmt) != BIT_AND_EXPR)
2540 return false;
2542 tree b_11 = gimple_assign_rhs1 (and_stmt);
2543 tree _1 = gimple_assign_rhs2 (and_stmt);
2545 /* Check that _1 is defined by _b11 + -1 (_1 = b_11 + -1).
2546 Also make sure that b_11 is the same in and_stmt and _1 defining stmt.
2547 Also canonicalize if _1 and _b11 are revrsed. */
2548 if (ssa_defined_by_minus_one_stmt_p (b_11, _1))
2549 std::swap (b_11, _1);
2550 else if (ssa_defined_by_minus_one_stmt_p (_1, b_11))
2552 else
2553 return false;
2554 /* Check the recurrence:
2555 ... = PHI <b_5(2), b_6(3)>. */
2556 gimple *phi = SSA_NAME_DEF_STMT (b_11);
2557 if (gimple_code (phi) != GIMPLE_PHI
2558 || (gimple_bb (phi) != loop_latch_edge (loop)->dest)
2559 || (gimple_assign_lhs (and_stmt)
2560 != gimple_phi_arg_def (phi, loop_latch_edge (loop)->dest_idx)))
2561 return false;
2563 /* We found a match. Get the corresponding popcount builtin. */
2564 tree src = gimple_phi_arg_def (phi, loop_preheader_edge (loop)->dest_idx);
2565 if (TYPE_PRECISION (TREE_TYPE (src)) == TYPE_PRECISION (integer_type_node))
2566 fn = builtin_decl_implicit (BUILT_IN_POPCOUNT);
2567 else if (TYPE_PRECISION (TREE_TYPE (src)) == TYPE_PRECISION
2568 (long_integer_type_node))
2569 fn = builtin_decl_implicit (BUILT_IN_POPCOUNTL);
2570 else if (TYPE_PRECISION (TREE_TYPE (src)) == TYPE_PRECISION
2571 (long_long_integer_type_node))
2572 fn = builtin_decl_implicit (BUILT_IN_POPCOUNTLL);
2574 /* ??? Support promoting char/short to int. */
2575 if (!fn)
2576 return false;
2578 /* Update NITER params accordingly */
2579 tree utype = unsigned_type_for (TREE_TYPE (src));
2580 src = fold_convert (utype, src);
2581 tree call = fold_convert (utype, build_call_expr (fn, 1, src));
2582 if (adjust)
2583 iter = fold_build2 (MINUS_EXPR, utype,
2584 call,
2585 build_int_cst (utype, 1));
2586 else
2587 iter = call;
2589 if (TREE_CODE (call) == INTEGER_CST)
2590 max = tree_to_uhwi (call);
2591 else
2593 max = TYPE_PRECISION (TREE_TYPE (src));
2594 if (adjust)
2595 max = max - 1;
2598 niter->niter = iter;
2599 niter->assumptions = boolean_true_node;
2601 if (adjust)
2603 tree may_be_zero = fold_build2 (EQ_EXPR, boolean_type_node, src,
2604 build_zero_cst
2605 (TREE_TYPE (src)));
2606 niter->may_be_zero =
2607 simplify_using_initial_conditions (loop, may_be_zero);
2609 else
2610 niter->may_be_zero = boolean_false_node;
2612 niter->max = max;
2613 niter->bound = NULL_TREE;
2614 niter->cmp = ERROR_MARK;
2615 return true;
2619 /* Like number_of_iterations_exit_assumptions, but return TRUE only if
2620 the niter information holds unconditionally. */
2622 bool
2623 number_of_iterations_exit (struct loop *loop, edge exit,
2624 struct tree_niter_desc *niter,
2625 bool warn, bool every_iteration)
2627 gcond *stmt;
2628 if (!number_of_iterations_exit_assumptions (loop, exit, niter,
2629 &stmt, every_iteration))
2630 return false;
2632 if (integer_nonzerop (niter->assumptions))
2633 return true;
2635 if (warn)
2636 dump_printf_loc (MSG_MISSED_OPTIMIZATION, stmt,
2637 "missed loop optimization: niters analysis ends up "
2638 "with assumptions.\n");
2640 return false;
2643 /* Try to determine the number of iterations of LOOP. If we succeed,
2644 expression giving number of iterations is returned and *EXIT is
2645 set to the edge from that the information is obtained. Otherwise
2646 chrec_dont_know is returned. */
2648 tree
2649 find_loop_niter (struct loop *loop, edge *exit)
2651 unsigned i;
2652 vec<edge> exits = get_loop_exit_edges (loop);
2653 edge ex;
2654 tree niter = NULL_TREE, aniter;
2655 struct tree_niter_desc desc;
2657 *exit = NULL;
2658 FOR_EACH_VEC_ELT (exits, i, ex)
2660 if (!number_of_iterations_exit (loop, ex, &desc, false))
2661 continue;
2663 if (integer_nonzerop (desc.may_be_zero))
2665 /* We exit in the first iteration through this exit.
2666 We won't find anything better. */
2667 niter = build_int_cst (unsigned_type_node, 0);
2668 *exit = ex;
2669 break;
2672 if (!integer_zerop (desc.may_be_zero))
2673 continue;
2675 aniter = desc.niter;
2677 if (!niter)
2679 /* Nothing recorded yet. */
2680 niter = aniter;
2681 *exit = ex;
2682 continue;
2685 /* Prefer constants, the lower the better. */
2686 if (TREE_CODE (aniter) != INTEGER_CST)
2687 continue;
2689 if (TREE_CODE (niter) != INTEGER_CST)
2691 niter = aniter;
2692 *exit = ex;
2693 continue;
2696 if (tree_int_cst_lt (aniter, niter))
2698 niter = aniter;
2699 *exit = ex;
2700 continue;
2703 exits.release ();
2705 return niter ? niter : chrec_dont_know;
2708 /* Return true if loop is known to have bounded number of iterations. */
2710 bool
2711 finite_loop_p (struct loop *loop)
2713 widest_int nit;
2714 int flags;
2716 flags = flags_from_decl_or_type (current_function_decl);
2717 if ((flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE))
2719 if (dump_file && (dump_flags & TDF_DETAILS))
2720 fprintf (dump_file, "Found loop %i to be finite: it is within pure or const function.\n",
2721 loop->num);
2722 return true;
2725 if (loop->any_upper_bound
2726 || max_loop_iterations (loop, &nit))
2728 if (dump_file && (dump_flags & TDF_DETAILS))
2729 fprintf (dump_file, "Found loop %i to be finite: upper bound found.\n",
2730 loop->num);
2731 return true;
2733 return false;
2738 Analysis of a number of iterations of a loop by a brute-force evaluation.
2742 /* Bound on the number of iterations we try to evaluate. */
2744 #define MAX_ITERATIONS_TO_TRACK \
2745 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
2747 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
2748 result by a chain of operations such that all but exactly one of their
2749 operands are constants. */
2751 static gphi *
2752 chain_of_csts_start (struct loop *loop, tree x)
2754 gimple *stmt = SSA_NAME_DEF_STMT (x);
2755 tree use;
2756 basic_block bb = gimple_bb (stmt);
2757 enum tree_code code;
2759 if (!bb
2760 || !flow_bb_inside_loop_p (loop, bb))
2761 return NULL;
2763 if (gimple_code (stmt) == GIMPLE_PHI)
2765 if (bb == loop->header)
2766 return as_a <gphi *> (stmt);
2768 return NULL;
2771 if (gimple_code (stmt) != GIMPLE_ASSIGN
2772 || gimple_assign_rhs_class (stmt) == GIMPLE_TERNARY_RHS)
2773 return NULL;
2775 code = gimple_assign_rhs_code (stmt);
2776 if (gimple_references_memory_p (stmt)
2777 || TREE_CODE_CLASS (code) == tcc_reference
2778 || (code == ADDR_EXPR
2779 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
2780 return NULL;
2782 use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
2783 if (use == NULL_TREE)
2784 return NULL;
2786 return chain_of_csts_start (loop, use);
2789 /* Determines whether the expression X is derived from a result of a phi node
2790 in header of LOOP such that
2792 * the derivation of X consists only from operations with constants
2793 * the initial value of the phi node is constant
2794 * the value of the phi node in the next iteration can be derived from the
2795 value in the current iteration by a chain of operations with constants,
2796 or is also a constant
2798 If such phi node exists, it is returned, otherwise NULL is returned. */
2800 static gphi *
2801 get_base_for (struct loop *loop, tree x)
2803 gphi *phi;
2804 tree init, next;
2806 if (is_gimple_min_invariant (x))
2807 return NULL;
2809 phi = chain_of_csts_start (loop, x);
2810 if (!phi)
2811 return NULL;
2813 init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
2814 next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
2816 if (!is_gimple_min_invariant (init))
2817 return NULL;
2819 if (TREE_CODE (next) == SSA_NAME
2820 && chain_of_csts_start (loop, next) != phi)
2821 return NULL;
2823 return phi;
2826 /* Given an expression X, then
2828 * if X is NULL_TREE, we return the constant BASE.
2829 * if X is a constant, we return the constant X.
2830 * otherwise X is a SSA name, whose value in the considered loop is derived
2831 by a chain of operations with constant from a result of a phi node in
2832 the header of the loop. Then we return value of X when the value of the
2833 result of this phi node is given by the constant BASE. */
2835 static tree
2836 get_val_for (tree x, tree base)
2838 gimple *stmt;
2840 gcc_checking_assert (is_gimple_min_invariant (base));
2842 if (!x)
2843 return base;
2844 else if (is_gimple_min_invariant (x))
2845 return x;
2847 stmt = SSA_NAME_DEF_STMT (x);
2848 if (gimple_code (stmt) == GIMPLE_PHI)
2849 return base;
2851 gcc_checking_assert (is_gimple_assign (stmt));
2853 /* STMT must be either an assignment of a single SSA name or an
2854 expression involving an SSA name and a constant. Try to fold that
2855 expression using the value for the SSA name. */
2856 if (gimple_assign_ssa_name_copy_p (stmt))
2857 return get_val_for (gimple_assign_rhs1 (stmt), base);
2858 else if (gimple_assign_rhs_class (stmt) == GIMPLE_UNARY_RHS
2859 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
2860 return fold_build1 (gimple_assign_rhs_code (stmt),
2861 gimple_expr_type (stmt),
2862 get_val_for (gimple_assign_rhs1 (stmt), base));
2863 else if (gimple_assign_rhs_class (stmt) == GIMPLE_BINARY_RHS)
2865 tree rhs1 = gimple_assign_rhs1 (stmt);
2866 tree rhs2 = gimple_assign_rhs2 (stmt);
2867 if (TREE_CODE (rhs1) == SSA_NAME)
2868 rhs1 = get_val_for (rhs1, base);
2869 else if (TREE_CODE (rhs2) == SSA_NAME)
2870 rhs2 = get_val_for (rhs2, base);
2871 else
2872 gcc_unreachable ();
2873 return fold_build2 (gimple_assign_rhs_code (stmt),
2874 gimple_expr_type (stmt), rhs1, rhs2);
2876 else
2877 gcc_unreachable ();
2881 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2882 by brute force -- i.e. by determining the value of the operands of the
2883 condition at EXIT in first few iterations of the loop (assuming that
2884 these values are constant) and determining the first one in that the
2885 condition is not satisfied. Returns the constant giving the number
2886 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
2888 tree
2889 loop_niter_by_eval (struct loop *loop, edge exit)
2891 tree acnd;
2892 tree op[2], val[2], next[2], aval[2];
2893 gphi *phi;
2894 gimple *cond;
2895 unsigned i, j;
2896 enum tree_code cmp;
2898 cond = last_stmt (exit->src);
2899 if (!cond || gimple_code (cond) != GIMPLE_COND)
2900 return chrec_dont_know;
2902 cmp = gimple_cond_code (cond);
2903 if (exit->flags & EDGE_TRUE_VALUE)
2904 cmp = invert_tree_comparison (cmp, false);
2906 switch (cmp)
2908 case EQ_EXPR:
2909 case NE_EXPR:
2910 case GT_EXPR:
2911 case GE_EXPR:
2912 case LT_EXPR:
2913 case LE_EXPR:
2914 op[0] = gimple_cond_lhs (cond);
2915 op[1] = gimple_cond_rhs (cond);
2916 break;
2918 default:
2919 return chrec_dont_know;
2922 for (j = 0; j < 2; j++)
2924 if (is_gimple_min_invariant (op[j]))
2926 val[j] = op[j];
2927 next[j] = NULL_TREE;
2928 op[j] = NULL_TREE;
2930 else
2932 phi = get_base_for (loop, op[j]);
2933 if (!phi)
2934 return chrec_dont_know;
2935 val[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
2936 next[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
2940 /* Don't issue signed overflow warnings. */
2941 fold_defer_overflow_warnings ();
2943 for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
2945 for (j = 0; j < 2; j++)
2946 aval[j] = get_val_for (op[j], val[j]);
2948 acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]);
2949 if (acnd && integer_zerop (acnd))
2951 fold_undefer_and_ignore_overflow_warnings ();
2952 if (dump_file && (dump_flags & TDF_DETAILS))
2953 fprintf (dump_file,
2954 "Proved that loop %d iterates %d times using brute force.\n",
2955 loop->num, i);
2956 return build_int_cst (unsigned_type_node, i);
2959 for (j = 0; j < 2; j++)
2961 aval[j] = val[j];
2962 val[j] = get_val_for (next[j], val[j]);
2963 if (!is_gimple_min_invariant (val[j]))
2965 fold_undefer_and_ignore_overflow_warnings ();
2966 return chrec_dont_know;
2970 /* If the next iteration would use the same base values
2971 as the current one, there is no point looping further,
2972 all following iterations will be the same as this one. */
2973 if (val[0] == aval[0] && val[1] == aval[1])
2974 break;
2977 fold_undefer_and_ignore_overflow_warnings ();
2979 return chrec_dont_know;
2982 /* Finds the exit of the LOOP by that the loop exits after a constant
2983 number of iterations and stores the exit edge to *EXIT. The constant
2984 giving the number of iterations of LOOP is returned. The number of
2985 iterations is determined using loop_niter_by_eval (i.e. by brute force
2986 evaluation). If we are unable to find the exit for that loop_niter_by_eval
2987 determines the number of iterations, chrec_dont_know is returned. */
2989 tree
2990 find_loop_niter_by_eval (struct loop *loop, edge *exit)
2992 unsigned i;
2993 vec<edge> exits = get_loop_exit_edges (loop);
2994 edge ex;
2995 tree niter = NULL_TREE, aniter;
2997 *exit = NULL;
2999 /* Loops with multiple exits are expensive to handle and less important. */
3000 if (!flag_expensive_optimizations
3001 && exits.length () > 1)
3003 exits.release ();
3004 return chrec_dont_know;
3007 FOR_EACH_VEC_ELT (exits, i, ex)
3009 if (!just_once_each_iteration_p (loop, ex->src))
3010 continue;
3012 aniter = loop_niter_by_eval (loop, ex);
3013 if (chrec_contains_undetermined (aniter))
3014 continue;
3016 if (niter
3017 && !tree_int_cst_lt (aniter, niter))
3018 continue;
3020 niter = aniter;
3021 *exit = ex;
3023 exits.release ();
3025 return niter ? niter : chrec_dont_know;
3030 Analysis of upper bounds on number of iterations of a loop.
3034 static widest_int derive_constant_upper_bound_ops (tree, tree,
3035 enum tree_code, tree);
3037 /* Returns a constant upper bound on the value of the right-hand side of
3038 an assignment statement STMT. */
3040 static widest_int
3041 derive_constant_upper_bound_assign (gimple *stmt)
3043 enum tree_code code = gimple_assign_rhs_code (stmt);
3044 tree op0 = gimple_assign_rhs1 (stmt);
3045 tree op1 = gimple_assign_rhs2 (stmt);
3047 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt)),
3048 op0, code, op1);
3051 /* Returns a constant upper bound on the value of expression VAL. VAL
3052 is considered to be unsigned. If its type is signed, its value must
3053 be nonnegative. */
3055 static widest_int
3056 derive_constant_upper_bound (tree val)
3058 enum tree_code code;
3059 tree op0, op1, op2;
3061 extract_ops_from_tree (val, &code, &op0, &op1, &op2);
3062 return derive_constant_upper_bound_ops (TREE_TYPE (val), op0, code, op1);
3065 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
3066 whose type is TYPE. The expression is considered to be unsigned. If
3067 its type is signed, its value must be nonnegative. */
3069 static widest_int
3070 derive_constant_upper_bound_ops (tree type, tree op0,
3071 enum tree_code code, tree op1)
3073 tree subtype, maxt;
3074 widest_int bnd, max, cst;
3075 gimple *stmt;
3077 if (INTEGRAL_TYPE_P (type))
3078 maxt = TYPE_MAX_VALUE (type);
3079 else
3080 maxt = upper_bound_in_type (type, type);
3082 max = wi::to_widest (maxt);
3084 switch (code)
3086 case INTEGER_CST:
3087 return wi::to_widest (op0);
3089 CASE_CONVERT:
3090 subtype = TREE_TYPE (op0);
3091 if (!TYPE_UNSIGNED (subtype)
3092 /* If TYPE is also signed, the fact that VAL is nonnegative implies
3093 that OP0 is nonnegative. */
3094 && TYPE_UNSIGNED (type)
3095 && !tree_expr_nonnegative_p (op0))
3097 /* If we cannot prove that the casted expression is nonnegative,
3098 we cannot establish more useful upper bound than the precision
3099 of the type gives us. */
3100 return max;
3103 /* We now know that op0 is an nonnegative value. Try deriving an upper
3104 bound for it. */
3105 bnd = derive_constant_upper_bound (op0);
3107 /* If the bound does not fit in TYPE, max. value of TYPE could be
3108 attained. */
3109 if (wi::ltu_p (max, bnd))
3110 return max;
3112 return bnd;
3114 case PLUS_EXPR:
3115 case POINTER_PLUS_EXPR:
3116 case MINUS_EXPR:
3117 if (TREE_CODE (op1) != INTEGER_CST
3118 || !tree_expr_nonnegative_p (op0))
3119 return max;
3121 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
3122 choose the most logical way how to treat this constant regardless
3123 of the signedness of the type. */
3124 cst = wi::sext (wi::to_widest (op1), TYPE_PRECISION (type));
3125 if (code != MINUS_EXPR)
3126 cst = -cst;
3128 bnd = derive_constant_upper_bound (op0);
3130 if (wi::neg_p (cst))
3132 cst = -cst;
3133 /* Avoid CST == 0x80000... */
3134 if (wi::neg_p (cst))
3135 return max;
3137 /* OP0 + CST. We need to check that
3138 BND <= MAX (type) - CST. */
3140 widest_int mmax = max - cst;
3141 if (wi::leu_p (bnd, mmax))
3142 return max;
3144 return bnd + cst;
3146 else
3148 /* OP0 - CST, where CST >= 0.
3150 If TYPE is signed, we have already verified that OP0 >= 0, and we
3151 know that the result is nonnegative. This implies that
3152 VAL <= BND - CST.
3154 If TYPE is unsigned, we must additionally know that OP0 >= CST,
3155 otherwise the operation underflows.
3158 /* This should only happen if the type is unsigned; however, for
3159 buggy programs that use overflowing signed arithmetics even with
3160 -fno-wrapv, this condition may also be true for signed values. */
3161 if (wi::ltu_p (bnd, cst))
3162 return max;
3164 if (TYPE_UNSIGNED (type))
3166 tree tem = fold_binary (GE_EXPR, boolean_type_node, op0,
3167 wide_int_to_tree (type, cst));
3168 if (!tem || integer_nonzerop (tem))
3169 return max;
3172 bnd -= cst;
3175 return bnd;
3177 case FLOOR_DIV_EXPR:
3178 case EXACT_DIV_EXPR:
3179 if (TREE_CODE (op1) != INTEGER_CST
3180 || tree_int_cst_sign_bit (op1))
3181 return max;
3183 bnd = derive_constant_upper_bound (op0);
3184 return wi::udiv_floor (bnd, wi::to_widest (op1));
3186 case BIT_AND_EXPR:
3187 if (TREE_CODE (op1) != INTEGER_CST
3188 || tree_int_cst_sign_bit (op1))
3189 return max;
3190 return wi::to_widest (op1);
3192 case SSA_NAME:
3193 stmt = SSA_NAME_DEF_STMT (op0);
3194 if (gimple_code (stmt) != GIMPLE_ASSIGN
3195 || gimple_assign_lhs (stmt) != op0)
3196 return max;
3197 return derive_constant_upper_bound_assign (stmt);
3199 default:
3200 return max;
3204 /* Emit a -Waggressive-loop-optimizations warning if needed. */
3206 static void
3207 do_warn_aggressive_loop_optimizations (struct loop *loop,
3208 widest_int i_bound, gimple *stmt)
3210 /* Don't warn if the loop doesn't have known constant bound. */
3211 if (!loop->nb_iterations
3212 || TREE_CODE (loop->nb_iterations) != INTEGER_CST
3213 || !warn_aggressive_loop_optimizations
3214 /* To avoid warning multiple times for the same loop,
3215 only start warning when we preserve loops. */
3216 || (cfun->curr_properties & PROP_loops) == 0
3217 /* Only warn once per loop. */
3218 || loop->warned_aggressive_loop_optimizations
3219 /* Only warn if undefined behavior gives us lower estimate than the
3220 known constant bound. */
3221 || wi::cmpu (i_bound, wi::to_widest (loop->nb_iterations)) >= 0
3222 /* And undefined behavior happens unconditionally. */
3223 || !dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (stmt)))
3224 return;
3226 edge e = single_exit (loop);
3227 if (e == NULL)
3228 return;
3230 gimple *estmt = last_stmt (e->src);
3231 char buf[WIDE_INT_PRINT_BUFFER_SIZE];
3232 print_dec (i_bound, buf, TYPE_UNSIGNED (TREE_TYPE (loop->nb_iterations))
3233 ? UNSIGNED : SIGNED);
3234 auto_diagnostic_group d;
3235 if (warning_at (gimple_location (stmt), OPT_Waggressive_loop_optimizations,
3236 "iteration %s invokes undefined behavior", buf))
3237 inform (gimple_location (estmt), "within this loop");
3238 loop->warned_aggressive_loop_optimizations = true;
3241 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
3242 is true if the loop is exited immediately after STMT, and this exit
3243 is taken at last when the STMT is executed BOUND + 1 times.
3244 REALISTIC is true if BOUND is expected to be close to the real number
3245 of iterations. UPPER is true if we are sure the loop iterates at most
3246 BOUND times. I_BOUND is a widest_int upper estimate on BOUND. */
3248 static void
3249 record_estimate (struct loop *loop, tree bound, const widest_int &i_bound,
3250 gimple *at_stmt, bool is_exit, bool realistic, bool upper)
3252 widest_int delta;
3254 if (dump_file && (dump_flags & TDF_DETAILS))
3256 fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : "");
3257 print_gimple_stmt (dump_file, at_stmt, 0, TDF_SLIM);
3258 fprintf (dump_file, " is %sexecuted at most ",
3259 upper ? "" : "probably ");
3260 print_generic_expr (dump_file, bound, TDF_SLIM);
3261 fprintf (dump_file, " (bounded by ");
3262 print_decu (i_bound, dump_file);
3263 fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num);
3266 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
3267 real number of iterations. */
3268 if (TREE_CODE (bound) != INTEGER_CST)
3269 realistic = false;
3270 else
3271 gcc_checking_assert (i_bound == wi::to_widest (bound));
3273 /* If we have a guaranteed upper bound, record it in the appropriate
3274 list, unless this is an !is_exit bound (i.e. undefined behavior in
3275 at_stmt) in a loop with known constant number of iterations. */
3276 if (upper
3277 && (is_exit
3278 || loop->nb_iterations == NULL_TREE
3279 || TREE_CODE (loop->nb_iterations) != INTEGER_CST))
3281 struct nb_iter_bound *elt = ggc_alloc<nb_iter_bound> ();
3283 elt->bound = i_bound;
3284 elt->stmt = at_stmt;
3285 elt->is_exit = is_exit;
3286 elt->next = loop->bounds;
3287 loop->bounds = elt;
3290 /* If statement is executed on every path to the loop latch, we can directly
3291 infer the upper bound on the # of iterations of the loop. */
3292 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (at_stmt)))
3293 upper = false;
3295 /* Update the number of iteration estimates according to the bound.
3296 If at_stmt is an exit then the loop latch is executed at most BOUND times,
3297 otherwise it can be executed BOUND + 1 times. We will lower the estimate
3298 later if such statement must be executed on last iteration */
3299 if (is_exit)
3300 delta = 0;
3301 else
3302 delta = 1;
3303 widest_int new_i_bound = i_bound + delta;
3305 /* If an overflow occurred, ignore the result. */
3306 if (wi::ltu_p (new_i_bound, delta))
3307 return;
3309 if (upper && !is_exit)
3310 do_warn_aggressive_loop_optimizations (loop, new_i_bound, at_stmt);
3311 record_niter_bound (loop, new_i_bound, realistic, upper);
3314 /* Records the control iv analyzed in NITER for LOOP if the iv is valid
3315 and doesn't overflow. */
3317 static void
3318 record_control_iv (struct loop *loop, struct tree_niter_desc *niter)
3320 struct control_iv *iv;
3322 if (!niter->control.base || !niter->control.step)
3323 return;
3325 if (!integer_onep (niter->assumptions) || !niter->control.no_overflow)
3326 return;
3328 iv = ggc_alloc<control_iv> ();
3329 iv->base = niter->control.base;
3330 iv->step = niter->control.step;
3331 iv->next = loop->control_ivs;
3332 loop->control_ivs = iv;
3334 return;
3337 /* This function returns TRUE if below conditions are satisfied:
3338 1) VAR is SSA variable.
3339 2) VAR is an IV:{base, step} in its defining loop.
3340 3) IV doesn't overflow.
3341 4) Both base and step are integer constants.
3342 5) Base is the MIN/MAX value depends on IS_MIN.
3343 Store value of base to INIT correspondingly. */
3345 static bool
3346 get_cst_init_from_scev (tree var, wide_int *init, bool is_min)
3348 if (TREE_CODE (var) != SSA_NAME)
3349 return false;
3351 gimple *def_stmt = SSA_NAME_DEF_STMT (var);
3352 struct loop *loop = loop_containing_stmt (def_stmt);
3354 if (loop == NULL)
3355 return false;
3357 affine_iv iv;
3358 if (!simple_iv (loop, loop, var, &iv, false))
3359 return false;
3361 if (!iv.no_overflow)
3362 return false;
3364 if (TREE_CODE (iv.base) != INTEGER_CST || TREE_CODE (iv.step) != INTEGER_CST)
3365 return false;
3367 if (is_min == tree_int_cst_sign_bit (iv.step))
3368 return false;
3370 *init = wi::to_wide (iv.base);
3371 return true;
3374 /* Record the estimate on number of iterations of LOOP based on the fact that
3375 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
3376 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
3377 estimated number of iterations is expected to be close to the real one.
3378 UPPER is true if we are sure the induction variable does not wrap. */
3380 static void
3381 record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple *stmt,
3382 tree low, tree high, bool realistic, bool upper)
3384 tree niter_bound, extreme, delta;
3385 tree type = TREE_TYPE (base), unsigned_type;
3386 tree orig_base = base;
3388 if (TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
3389 return;
3391 if (dump_file && (dump_flags & TDF_DETAILS))
3393 fprintf (dump_file, "Induction variable (");
3394 print_generic_expr (dump_file, TREE_TYPE (base), TDF_SLIM);
3395 fprintf (dump_file, ") ");
3396 print_generic_expr (dump_file, base, TDF_SLIM);
3397 fprintf (dump_file, " + ");
3398 print_generic_expr (dump_file, step, TDF_SLIM);
3399 fprintf (dump_file, " * iteration does not wrap in statement ");
3400 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
3401 fprintf (dump_file, " in loop %d.\n", loop->num);
3404 unsigned_type = unsigned_type_for (type);
3405 base = fold_convert (unsigned_type, base);
3406 step = fold_convert (unsigned_type, step);
3408 if (tree_int_cst_sign_bit (step))
3410 wide_int min, max;
3411 extreme = fold_convert (unsigned_type, low);
3412 if (TREE_CODE (orig_base) == SSA_NAME
3413 && TREE_CODE (high) == INTEGER_CST
3414 && INTEGRAL_TYPE_P (TREE_TYPE (orig_base))
3415 && (get_range_info (orig_base, &min, &max) == VR_RANGE
3416 || get_cst_init_from_scev (orig_base, &max, false))
3417 && wi::gts_p (wi::to_wide (high), max))
3418 base = wide_int_to_tree (unsigned_type, max);
3419 else if (TREE_CODE (base) != INTEGER_CST
3420 && dominated_by_p (CDI_DOMINATORS,
3421 loop->latch, gimple_bb (stmt)))
3422 base = fold_convert (unsigned_type, high);
3423 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
3424 step = fold_build1 (NEGATE_EXPR, unsigned_type, step);
3426 else
3428 wide_int min, max;
3429 extreme = fold_convert (unsigned_type, high);
3430 if (TREE_CODE (orig_base) == SSA_NAME
3431 && TREE_CODE (low) == INTEGER_CST
3432 && INTEGRAL_TYPE_P (TREE_TYPE (orig_base))
3433 && (get_range_info (orig_base, &min, &max) == VR_RANGE
3434 || get_cst_init_from_scev (orig_base, &min, true))
3435 && wi::gts_p (min, wi::to_wide (low)))
3436 base = wide_int_to_tree (unsigned_type, min);
3437 else if (TREE_CODE (base) != INTEGER_CST
3438 && dominated_by_p (CDI_DOMINATORS,
3439 loop->latch, gimple_bb (stmt)))
3440 base = fold_convert (unsigned_type, low);
3441 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
3444 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
3445 would get out of the range. */
3446 niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step);
3447 widest_int max = derive_constant_upper_bound (niter_bound);
3448 record_estimate (loop, niter_bound, max, stmt, false, realistic, upper);
3451 /* Determine information about number of iterations a LOOP from the index
3452 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
3453 guaranteed to be executed in every iteration of LOOP. Callback for
3454 for_each_index. */
3456 struct ilb_data
3458 struct loop *loop;
3459 gimple *stmt;
3462 static bool
3463 idx_infer_loop_bounds (tree base, tree *idx, void *dta)
3465 struct ilb_data *data = (struct ilb_data *) dta;
3466 tree ev, init, step;
3467 tree low, high, type, next;
3468 bool sign, upper = true, at_end = false;
3469 struct loop *loop = data->loop;
3471 if (TREE_CODE (base) != ARRAY_REF)
3472 return true;
3474 /* For arrays at the end of the structure, we are not guaranteed that they
3475 do not really extend over their declared size. However, for arrays of
3476 size greater than one, this is unlikely to be intended. */
3477 if (array_at_struct_end_p (base))
3479 at_end = true;
3480 upper = false;
3483 struct loop *dloop = loop_containing_stmt (data->stmt);
3484 if (!dloop)
3485 return true;
3487 ev = analyze_scalar_evolution (dloop, *idx);
3488 ev = instantiate_parameters (loop, ev);
3489 init = initial_condition (ev);
3490 step = evolution_part_in_loop_num (ev, loop->num);
3492 if (!init
3493 || !step
3494 || TREE_CODE (step) != INTEGER_CST
3495 || integer_zerop (step)
3496 || tree_contains_chrecs (init, NULL)
3497 || chrec_contains_symbols_defined_in_loop (init, loop->num))
3498 return true;
3500 low = array_ref_low_bound (base);
3501 high = array_ref_up_bound (base);
3503 /* The case of nonconstant bounds could be handled, but it would be
3504 complicated. */
3505 if (TREE_CODE (low) != INTEGER_CST
3506 || !high
3507 || TREE_CODE (high) != INTEGER_CST)
3508 return true;
3509 sign = tree_int_cst_sign_bit (step);
3510 type = TREE_TYPE (step);
3512 /* The array of length 1 at the end of a structure most likely extends
3513 beyond its bounds. */
3514 if (at_end
3515 && operand_equal_p (low, high, 0))
3516 return true;
3518 /* In case the relevant bound of the array does not fit in type, or
3519 it does, but bound + step (in type) still belongs into the range of the
3520 array, the index may wrap and still stay within the range of the array
3521 (consider e.g. if the array is indexed by the full range of
3522 unsigned char).
3524 To make things simpler, we require both bounds to fit into type, although
3525 there are cases where this would not be strictly necessary. */
3526 if (!int_fits_type_p (high, type)
3527 || !int_fits_type_p (low, type))
3528 return true;
3529 low = fold_convert (type, low);
3530 high = fold_convert (type, high);
3532 if (sign)
3533 next = fold_binary (PLUS_EXPR, type, low, step);
3534 else
3535 next = fold_binary (PLUS_EXPR, type, high, step);
3537 if (tree_int_cst_compare (low, next) <= 0
3538 && tree_int_cst_compare (next, high) <= 0)
3539 return true;
3541 /* If access is not executed on every iteration, we must ensure that overlow
3542 may not make the access valid later. */
3543 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (data->stmt))
3544 && scev_probably_wraps_p (NULL_TREE,
3545 initial_condition_in_loop_num (ev, loop->num),
3546 step, data->stmt, loop, true))
3547 upper = false;
3549 record_nonwrapping_iv (loop, init, step, data->stmt, low, high, false, upper);
3550 return true;
3553 /* Determine information about number of iterations a LOOP from the bounds
3554 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
3555 STMT is guaranteed to be executed in every iteration of LOOP.*/
3557 static void
3558 infer_loop_bounds_from_ref (struct loop *loop, gimple *stmt, tree ref)
3560 struct ilb_data data;
3562 data.loop = loop;
3563 data.stmt = stmt;
3564 for_each_index (&ref, idx_infer_loop_bounds, &data);
3567 /* Determine information about number of iterations of a LOOP from the way
3568 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
3569 executed in every iteration of LOOP. */
3571 static void
3572 infer_loop_bounds_from_array (struct loop *loop, gimple *stmt)
3574 if (is_gimple_assign (stmt))
3576 tree op0 = gimple_assign_lhs (stmt);
3577 tree op1 = gimple_assign_rhs1 (stmt);
3579 /* For each memory access, analyze its access function
3580 and record a bound on the loop iteration domain. */
3581 if (REFERENCE_CLASS_P (op0))
3582 infer_loop_bounds_from_ref (loop, stmt, op0);
3584 if (REFERENCE_CLASS_P (op1))
3585 infer_loop_bounds_from_ref (loop, stmt, op1);
3587 else if (is_gimple_call (stmt))
3589 tree arg, lhs;
3590 unsigned i, n = gimple_call_num_args (stmt);
3592 lhs = gimple_call_lhs (stmt);
3593 if (lhs && REFERENCE_CLASS_P (lhs))
3594 infer_loop_bounds_from_ref (loop, stmt, lhs);
3596 for (i = 0; i < n; i++)
3598 arg = gimple_call_arg (stmt, i);
3599 if (REFERENCE_CLASS_P (arg))
3600 infer_loop_bounds_from_ref (loop, stmt, arg);
3605 /* Determine information about number of iterations of a LOOP from the fact
3606 that pointer arithmetics in STMT does not overflow. */
3608 static void
3609 infer_loop_bounds_from_pointer_arith (struct loop *loop, gimple *stmt)
3611 tree def, base, step, scev, type, low, high;
3612 tree var, ptr;
3614 if (!is_gimple_assign (stmt)
3615 || gimple_assign_rhs_code (stmt) != POINTER_PLUS_EXPR)
3616 return;
3618 def = gimple_assign_lhs (stmt);
3619 if (TREE_CODE (def) != SSA_NAME)
3620 return;
3622 type = TREE_TYPE (def);
3623 if (!nowrap_type_p (type))
3624 return;
3626 ptr = gimple_assign_rhs1 (stmt);
3627 if (!expr_invariant_in_loop_p (loop, ptr))
3628 return;
3630 var = gimple_assign_rhs2 (stmt);
3631 if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (var)))
3632 return;
3634 struct loop *uloop = loop_containing_stmt (stmt);
3635 scev = instantiate_parameters (loop, analyze_scalar_evolution (uloop, def));
3636 if (chrec_contains_undetermined (scev))
3637 return;
3639 base = initial_condition_in_loop_num (scev, loop->num);
3640 step = evolution_part_in_loop_num (scev, loop->num);
3642 if (!base || !step
3643 || TREE_CODE (step) != INTEGER_CST
3644 || tree_contains_chrecs (base, NULL)
3645 || chrec_contains_symbols_defined_in_loop (base, loop->num))
3646 return;
3648 low = lower_bound_in_type (type, type);
3649 high = upper_bound_in_type (type, type);
3651 /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
3652 produce a NULL pointer. The contrary would mean NULL points to an object,
3653 while NULL is supposed to compare unequal with the address of all objects.
3654 Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
3655 NULL pointer since that would mean wrapping, which we assume here not to
3656 happen. So, we can exclude NULL from the valid range of pointer
3657 arithmetic. */
3658 if (flag_delete_null_pointer_checks && int_cst_value (low) == 0)
3659 low = build_int_cstu (TREE_TYPE (low), TYPE_ALIGN_UNIT (TREE_TYPE (type)));
3661 record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
3664 /* Determine information about number of iterations of a LOOP from the fact
3665 that signed arithmetics in STMT does not overflow. */
3667 static void
3668 infer_loop_bounds_from_signedness (struct loop *loop, gimple *stmt)
3670 tree def, base, step, scev, type, low, high;
3672 if (gimple_code (stmt) != GIMPLE_ASSIGN)
3673 return;
3675 def = gimple_assign_lhs (stmt);
3677 if (TREE_CODE (def) != SSA_NAME)
3678 return;
3680 type = TREE_TYPE (def);
3681 if (!INTEGRAL_TYPE_P (type)
3682 || !TYPE_OVERFLOW_UNDEFINED (type))
3683 return;
3685 scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
3686 if (chrec_contains_undetermined (scev))
3687 return;
3689 base = initial_condition_in_loop_num (scev, loop->num);
3690 step = evolution_part_in_loop_num (scev, loop->num);
3692 if (!base || !step
3693 || TREE_CODE (step) != INTEGER_CST
3694 || tree_contains_chrecs (base, NULL)
3695 || chrec_contains_symbols_defined_in_loop (base, loop->num))
3696 return;
3698 low = lower_bound_in_type (type, type);
3699 high = upper_bound_in_type (type, type);
3700 wide_int minv, maxv;
3701 if (get_range_info (def, &minv, &maxv) == VR_RANGE)
3703 low = wide_int_to_tree (type, minv);
3704 high = wide_int_to_tree (type, maxv);
3707 record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
3710 /* The following analyzers are extracting informations on the bounds
3711 of LOOP from the following undefined behaviors:
3713 - data references should not access elements over the statically
3714 allocated size,
3716 - signed variables should not overflow when flag_wrapv is not set.
3719 static void
3720 infer_loop_bounds_from_undefined (struct loop *loop)
3722 unsigned i;
3723 basic_block *bbs;
3724 gimple_stmt_iterator bsi;
3725 basic_block bb;
3726 bool reliable;
3728 bbs = get_loop_body (loop);
3730 for (i = 0; i < loop->num_nodes; i++)
3732 bb = bbs[i];
3734 /* If BB is not executed in each iteration of the loop, we cannot
3735 use the operations in it to infer reliable upper bound on the
3736 # of iterations of the loop. However, we can use it as a guess.
3737 Reliable guesses come only from array bounds. */
3738 reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb);
3740 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
3742 gimple *stmt = gsi_stmt (bsi);
3744 infer_loop_bounds_from_array (loop, stmt);
3746 if (reliable)
3748 infer_loop_bounds_from_signedness (loop, stmt);
3749 infer_loop_bounds_from_pointer_arith (loop, stmt);
3755 free (bbs);
3758 /* Compare wide ints, callback for qsort. */
3760 static int
3761 wide_int_cmp (const void *p1, const void *p2)
3763 const widest_int *d1 = (const widest_int *) p1;
3764 const widest_int *d2 = (const widest_int *) p2;
3765 return wi::cmpu (*d1, *d2);
3768 /* Return index of BOUND in BOUNDS array sorted in increasing order.
3769 Lookup by binary search. */
3771 static int
3772 bound_index (vec<widest_int> bounds, const widest_int &bound)
3774 unsigned int end = bounds.length ();
3775 unsigned int begin = 0;
3777 /* Find a matching index by means of a binary search. */
3778 while (begin != end)
3780 unsigned int middle = (begin + end) / 2;
3781 widest_int index = bounds[middle];
3783 if (index == bound)
3784 return middle;
3785 else if (wi::ltu_p (index, bound))
3786 begin = middle + 1;
3787 else
3788 end = middle;
3790 gcc_unreachable ();
3793 /* We recorded loop bounds only for statements dominating loop latch (and thus
3794 executed each loop iteration). If there are any bounds on statements not
3795 dominating the loop latch we can improve the estimate by walking the loop
3796 body and seeing if every path from loop header to loop latch contains
3797 some bounded statement. */
3799 static void
3800 discover_iteration_bound_by_body_walk (struct loop *loop)
3802 struct nb_iter_bound *elt;
3803 auto_vec<widest_int> bounds;
3804 vec<vec<basic_block> > queues = vNULL;
3805 vec<basic_block> queue = vNULL;
3806 ptrdiff_t queue_index;
3807 ptrdiff_t latch_index = 0;
3809 /* Discover what bounds may interest us. */
3810 for (elt = loop->bounds; elt; elt = elt->next)
3812 widest_int bound = elt->bound;
3814 /* Exit terminates loop at given iteration, while non-exits produce undefined
3815 effect on the next iteration. */
3816 if (!elt->is_exit)
3818 bound += 1;
3819 /* If an overflow occurred, ignore the result. */
3820 if (bound == 0)
3821 continue;
3824 if (!loop->any_upper_bound
3825 || wi::ltu_p (bound, loop->nb_iterations_upper_bound))
3826 bounds.safe_push (bound);
3829 /* Exit early if there is nothing to do. */
3830 if (!bounds.exists ())
3831 return;
3833 if (dump_file && (dump_flags & TDF_DETAILS))
3834 fprintf (dump_file, " Trying to walk loop body to reduce the bound.\n");
3836 /* Sort the bounds in decreasing order. */
3837 bounds.qsort (wide_int_cmp);
3839 /* For every basic block record the lowest bound that is guaranteed to
3840 terminate the loop. */
3842 hash_map<basic_block, ptrdiff_t> bb_bounds;
3843 for (elt = loop->bounds; elt; elt = elt->next)
3845 widest_int bound = elt->bound;
3846 if (!elt->is_exit)
3848 bound += 1;
3849 /* If an overflow occurred, ignore the result. */
3850 if (bound == 0)
3851 continue;
3854 if (!loop->any_upper_bound
3855 || wi::ltu_p (bound, loop->nb_iterations_upper_bound))
3857 ptrdiff_t index = bound_index (bounds, bound);
3858 ptrdiff_t *entry = bb_bounds.get (gimple_bb (elt->stmt));
3859 if (!entry)
3860 bb_bounds.put (gimple_bb (elt->stmt), index);
3861 else if ((ptrdiff_t)*entry > index)
3862 *entry = index;
3866 hash_map<basic_block, ptrdiff_t> block_priority;
3868 /* Perform shortest path discovery loop->header ... loop->latch.
3870 The "distance" is given by the smallest loop bound of basic block
3871 present in the path and we look for path with largest smallest bound
3872 on it.
3874 To avoid the need for fibonacci heap on double ints we simply compress
3875 double ints into indexes to BOUNDS array and then represent the queue
3876 as arrays of queues for every index.
3877 Index of BOUNDS.length() means that the execution of given BB has
3878 no bounds determined.
3880 VISITED is a pointer map translating basic block into smallest index
3881 it was inserted into the priority queue with. */
3882 latch_index = -1;
3884 /* Start walk in loop header with index set to infinite bound. */
3885 queue_index = bounds.length ();
3886 queues.safe_grow_cleared (queue_index + 1);
3887 queue.safe_push (loop->header);
3888 queues[queue_index] = queue;
3889 block_priority.put (loop->header, queue_index);
3891 for (; queue_index >= 0; queue_index--)
3893 if (latch_index < queue_index)
3895 while (queues[queue_index].length ())
3897 basic_block bb;
3898 ptrdiff_t bound_index = queue_index;
3899 edge e;
3900 edge_iterator ei;
3902 queue = queues[queue_index];
3903 bb = queue.pop ();
3905 /* OK, we later inserted the BB with lower priority, skip it. */
3906 if (*block_priority.get (bb) > queue_index)
3907 continue;
3909 /* See if we can improve the bound. */
3910 ptrdiff_t *entry = bb_bounds.get (bb);
3911 if (entry && *entry < bound_index)
3912 bound_index = *entry;
3914 /* Insert succesors into the queue, watch for latch edge
3915 and record greatest index we saw. */
3916 FOR_EACH_EDGE (e, ei, bb->succs)
3918 bool insert = false;
3920 if (loop_exit_edge_p (loop, e))
3921 continue;
3923 if (e == loop_latch_edge (loop)
3924 && latch_index < bound_index)
3925 latch_index = bound_index;
3926 else if (!(entry = block_priority.get (e->dest)))
3928 insert = true;
3929 block_priority.put (e->dest, bound_index);
3931 else if (*entry < bound_index)
3933 insert = true;
3934 *entry = bound_index;
3937 if (insert)
3938 queues[bound_index].safe_push (e->dest);
3942 queues[queue_index].release ();
3945 gcc_assert (latch_index >= 0);
3946 if ((unsigned)latch_index < bounds.length ())
3948 if (dump_file && (dump_flags & TDF_DETAILS))
3950 fprintf (dump_file, "Found better loop bound ");
3951 print_decu (bounds[latch_index], dump_file);
3952 fprintf (dump_file, "\n");
3954 record_niter_bound (loop, bounds[latch_index], false, true);
3957 queues.release ();
3960 /* See if every path cross the loop goes through a statement that is known
3961 to not execute at the last iteration. In that case we can decrese iteration
3962 count by 1. */
3964 static void
3965 maybe_lower_iteration_bound (struct loop *loop)
3967 hash_set<gimple *> *not_executed_last_iteration = NULL;
3968 struct nb_iter_bound *elt;
3969 bool found_exit = false;
3970 auto_vec<basic_block> queue;
3971 bitmap visited;
3973 /* Collect all statements with interesting (i.e. lower than
3974 nb_iterations_upper_bound) bound on them.
3976 TODO: Due to the way record_estimate choose estimates to store, the bounds
3977 will be always nb_iterations_upper_bound-1. We can change this to record
3978 also statements not dominating the loop latch and update the walk bellow
3979 to the shortest path algorithm. */
3980 for (elt = loop->bounds; elt; elt = elt->next)
3982 if (!elt->is_exit
3983 && wi::ltu_p (elt->bound, loop->nb_iterations_upper_bound))
3985 if (!not_executed_last_iteration)
3986 not_executed_last_iteration = new hash_set<gimple *>;
3987 not_executed_last_iteration->add (elt->stmt);
3990 if (!not_executed_last_iteration)
3991 return;
3993 /* Start DFS walk in the loop header and see if we can reach the
3994 loop latch or any of the exits (including statements with side
3995 effects that may terminate the loop otherwise) without visiting
3996 any of the statements known to have undefined effect on the last
3997 iteration. */
3998 queue.safe_push (loop->header);
3999 visited = BITMAP_ALLOC (NULL);
4000 bitmap_set_bit (visited, loop->header->index);
4001 found_exit = false;
4005 basic_block bb = queue.pop ();
4006 gimple_stmt_iterator gsi;
4007 bool stmt_found = false;
4009 /* Loop for possible exits and statements bounding the execution. */
4010 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4012 gimple *stmt = gsi_stmt (gsi);
4013 if (not_executed_last_iteration->contains (stmt))
4015 stmt_found = true;
4016 break;
4018 if (gimple_has_side_effects (stmt))
4020 found_exit = true;
4021 break;
4024 if (found_exit)
4025 break;
4027 /* If no bounding statement is found, continue the walk. */
4028 if (!stmt_found)
4030 edge e;
4031 edge_iterator ei;
4033 FOR_EACH_EDGE (e, ei, bb->succs)
4035 if (loop_exit_edge_p (loop, e)
4036 || e == loop_latch_edge (loop))
4038 found_exit = true;
4039 break;
4041 if (bitmap_set_bit (visited, e->dest->index))
4042 queue.safe_push (e->dest);
4046 while (queue.length () && !found_exit);
4048 /* If every path through the loop reach bounding statement before exit,
4049 then we know the last iteration of the loop will have undefined effect
4050 and we can decrease number of iterations. */
4052 if (!found_exit)
4054 if (dump_file && (dump_flags & TDF_DETAILS))
4055 fprintf (dump_file, "Reducing loop iteration estimate by 1; "
4056 "undefined statement must be executed at the last iteration.\n");
4057 record_niter_bound (loop, loop->nb_iterations_upper_bound - 1,
4058 false, true);
4061 BITMAP_FREE (visited);
4062 delete not_executed_last_iteration;
4065 /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
4066 is true also use estimates derived from undefined behavior. */
4068 void
4069 estimate_numbers_of_iterations (struct loop *loop)
4071 vec<edge> exits;
4072 tree niter, type;
4073 unsigned i;
4074 struct tree_niter_desc niter_desc;
4075 edge ex;
4076 widest_int bound;
4077 edge likely_exit;
4079 /* Give up if we already have tried to compute an estimation. */
4080 if (loop->estimate_state != EST_NOT_COMPUTED)
4081 return;
4083 loop->estimate_state = EST_AVAILABLE;
4085 /* If we have a measured profile, use it to estimate the number of
4086 iterations. Normally this is recorded by branch_prob right after
4087 reading the profile. In case we however found a new loop, record the
4088 information here.
4090 Explicitly check for profile status so we do not report
4091 wrong prediction hitrates for guessed loop iterations heuristics.
4092 Do not recompute already recorded bounds - we ought to be better on
4093 updating iteration bounds than updating profile in general and thus
4094 recomputing iteration bounds later in the compilation process will just
4095 introduce random roundoff errors. */
4096 if (!loop->any_estimate
4097 && loop->header->count.reliable_p ())
4099 gcov_type nit = expected_loop_iterations_unbounded (loop);
4100 bound = gcov_type_to_wide_int (nit);
4101 record_niter_bound (loop, bound, true, false);
4104 /* Ensure that loop->nb_iterations is computed if possible. If it turns out
4105 to be constant, we avoid undefined behavior implied bounds and instead
4106 diagnose those loops with -Waggressive-loop-optimizations. */
4107 number_of_latch_executions (loop);
4109 exits = get_loop_exit_edges (loop);
4110 likely_exit = single_likely_exit (loop);
4111 FOR_EACH_VEC_ELT (exits, i, ex)
4113 if (!number_of_iterations_exit (loop, ex, &niter_desc, false, false))
4114 continue;
4116 niter = niter_desc.niter;
4117 type = TREE_TYPE (niter);
4118 if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST)
4119 niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
4120 build_int_cst (type, 0),
4121 niter);
4122 record_estimate (loop, niter, niter_desc.max,
4123 last_stmt (ex->src),
4124 true, ex == likely_exit, true);
4125 record_control_iv (loop, &niter_desc);
4127 exits.release ();
4129 if (flag_aggressive_loop_optimizations)
4130 infer_loop_bounds_from_undefined (loop);
4132 discover_iteration_bound_by_body_walk (loop);
4134 maybe_lower_iteration_bound (loop);
4136 /* If we know the exact number of iterations of this loop, try to
4137 not break code with undefined behavior by not recording smaller
4138 maximum number of iterations. */
4139 if (loop->nb_iterations
4140 && TREE_CODE (loop->nb_iterations) == INTEGER_CST)
4142 loop->any_upper_bound = true;
4143 loop->nb_iterations_upper_bound = wi::to_widest (loop->nb_iterations);
4147 /* Sets NIT to the estimated number of executions of the latch of the
4148 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
4149 large as the number of iterations. If we have no reliable estimate,
4150 the function returns false, otherwise returns true. */
4152 bool
4153 estimated_loop_iterations (struct loop *loop, widest_int *nit)
4155 /* When SCEV information is available, try to update loop iterations
4156 estimate. Otherwise just return whatever we recorded earlier. */
4157 if (scev_initialized_p ())
4158 estimate_numbers_of_iterations (loop);
4160 return (get_estimated_loop_iterations (loop, nit));
4163 /* Similar to estimated_loop_iterations, but returns the estimate only
4164 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
4165 on the number of iterations of LOOP could not be derived, returns -1. */
4167 HOST_WIDE_INT
4168 estimated_loop_iterations_int (struct loop *loop)
4170 widest_int nit;
4171 HOST_WIDE_INT hwi_nit;
4173 if (!estimated_loop_iterations (loop, &nit))
4174 return -1;
4176 if (!wi::fits_shwi_p (nit))
4177 return -1;
4178 hwi_nit = nit.to_shwi ();
4180 return hwi_nit < 0 ? -1 : hwi_nit;
4184 /* Sets NIT to an upper bound for the maximum number of executions of the
4185 latch of the LOOP. If we have no reliable estimate, the function returns
4186 false, otherwise returns true. */
4188 bool
4189 max_loop_iterations (struct loop *loop, widest_int *nit)
4191 /* When SCEV information is available, try to update loop iterations
4192 estimate. Otherwise just return whatever we recorded earlier. */
4193 if (scev_initialized_p ())
4194 estimate_numbers_of_iterations (loop);
4196 return get_max_loop_iterations (loop, nit);
4199 /* Similar to max_loop_iterations, but returns the estimate only
4200 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
4201 on the number of iterations of LOOP could not be derived, returns -1. */
4203 HOST_WIDE_INT
4204 max_loop_iterations_int (struct loop *loop)
4206 widest_int nit;
4207 HOST_WIDE_INT hwi_nit;
4209 if (!max_loop_iterations (loop, &nit))
4210 return -1;
4212 if (!wi::fits_shwi_p (nit))
4213 return -1;
4214 hwi_nit = nit.to_shwi ();
4216 return hwi_nit < 0 ? -1 : hwi_nit;
4219 /* Sets NIT to an likely upper bound for the maximum number of executions of the
4220 latch of the LOOP. If we have no reliable estimate, the function returns
4221 false, otherwise returns true. */
4223 bool
4224 likely_max_loop_iterations (struct loop *loop, widest_int *nit)
4226 /* When SCEV information is available, try to update loop iterations
4227 estimate. Otherwise just return whatever we recorded earlier. */
4228 if (scev_initialized_p ())
4229 estimate_numbers_of_iterations (loop);
4231 return get_likely_max_loop_iterations (loop, nit);
4234 /* Similar to max_loop_iterations, but returns the estimate only
4235 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
4236 on the number of iterations of LOOP could not be derived, returns -1. */
4238 HOST_WIDE_INT
4239 likely_max_loop_iterations_int (struct loop *loop)
4241 widest_int nit;
4242 HOST_WIDE_INT hwi_nit;
4244 if (!likely_max_loop_iterations (loop, &nit))
4245 return -1;
4247 if (!wi::fits_shwi_p (nit))
4248 return -1;
4249 hwi_nit = nit.to_shwi ();
4251 return hwi_nit < 0 ? -1 : hwi_nit;
4254 /* Returns an estimate for the number of executions of statements
4255 in the LOOP. For statements before the loop exit, this exceeds
4256 the number of execution of the latch by one. */
4258 HOST_WIDE_INT
4259 estimated_stmt_executions_int (struct loop *loop)
4261 HOST_WIDE_INT nit = estimated_loop_iterations_int (loop);
4262 HOST_WIDE_INT snit;
4264 if (nit == -1)
4265 return -1;
4267 snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
4269 /* If the computation overflows, return -1. */
4270 return snit < 0 ? -1 : snit;
4273 /* Sets NIT to the maximum number of executions of the latch of the
4274 LOOP, plus one. If we have no reliable estimate, the function returns
4275 false, otherwise returns true. */
4277 bool
4278 max_stmt_executions (struct loop *loop, widest_int *nit)
4280 widest_int nit_minus_one;
4282 if (!max_loop_iterations (loop, nit))
4283 return false;
4285 nit_minus_one = *nit;
4287 *nit += 1;
4289 return wi::gtu_p (*nit, nit_minus_one);
4292 /* Sets NIT to the estimated maximum number of executions of the latch of the
4293 LOOP, plus one. If we have no likely estimate, the function returns
4294 false, otherwise returns true. */
4296 bool
4297 likely_max_stmt_executions (struct loop *loop, widest_int *nit)
4299 widest_int nit_minus_one;
4301 if (!likely_max_loop_iterations (loop, nit))
4302 return false;
4304 nit_minus_one = *nit;
4306 *nit += 1;
4308 return wi::gtu_p (*nit, nit_minus_one);
4311 /* Sets NIT to the estimated number of executions of the latch of the
4312 LOOP, plus one. If we have no reliable estimate, the function returns
4313 false, otherwise returns true. */
4315 bool
4316 estimated_stmt_executions (struct loop *loop, widest_int *nit)
4318 widest_int nit_minus_one;
4320 if (!estimated_loop_iterations (loop, nit))
4321 return false;
4323 nit_minus_one = *nit;
4325 *nit += 1;
4327 return wi::gtu_p (*nit, nit_minus_one);
4330 /* Records estimates on numbers of iterations of loops. */
4332 void
4333 estimate_numbers_of_iterations (function *fn)
4335 struct loop *loop;
4337 /* We don't want to issue signed overflow warnings while getting
4338 loop iteration estimates. */
4339 fold_defer_overflow_warnings ();
4341 FOR_EACH_LOOP_FN (fn, loop, 0)
4342 estimate_numbers_of_iterations (loop);
4344 fold_undefer_and_ignore_overflow_warnings ();
4347 /* Returns true if statement S1 dominates statement S2. */
4349 bool
4350 stmt_dominates_stmt_p (gimple *s1, gimple *s2)
4352 basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
4354 if (!bb1
4355 || s1 == s2)
4356 return true;
4358 if (bb1 == bb2)
4360 gimple_stmt_iterator bsi;
4362 if (gimple_code (s2) == GIMPLE_PHI)
4363 return false;
4365 if (gimple_code (s1) == GIMPLE_PHI)
4366 return true;
4368 for (bsi = gsi_start_bb (bb1); gsi_stmt (bsi) != s2; gsi_next (&bsi))
4369 if (gsi_stmt (bsi) == s1)
4370 return true;
4372 return false;
4375 return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
4378 /* Returns true when we can prove that the number of executions of
4379 STMT in the loop is at most NITER, according to the bound on
4380 the number of executions of the statement NITER_BOUND->stmt recorded in
4381 NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT.
4383 ??? This code can become quite a CPU hog - we can have many bounds,
4384 and large basic block forcing stmt_dominates_stmt_p to be queried
4385 many times on a large basic blocks, so the whole thing is O(n^2)
4386 for scev_probably_wraps_p invocation (that can be done n times).
4388 It would make more sense (and give better answers) to remember BB
4389 bounds computed by discover_iteration_bound_by_body_walk. */
4391 static bool
4392 n_of_executions_at_most (gimple *stmt,
4393 struct nb_iter_bound *niter_bound,
4394 tree niter)
4396 widest_int bound = niter_bound->bound;
4397 tree nit_type = TREE_TYPE (niter), e;
4398 enum tree_code cmp;
4400 gcc_assert (TYPE_UNSIGNED (nit_type));
4402 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
4403 the number of iterations is small. */
4404 if (!wi::fits_to_tree_p (bound, nit_type))
4405 return false;
4407 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
4408 times. This means that:
4410 -- if NITER_BOUND->is_exit is true, then everything after
4411 it at most NITER_BOUND->bound times.
4413 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
4414 is executed, then NITER_BOUND->stmt is executed as well in the same
4415 iteration then STMT is executed at most NITER_BOUND->bound + 1 times.
4417 If we can determine that NITER_BOUND->stmt is always executed
4418 after STMT, then STMT is executed at most NITER_BOUND->bound + 2 times.
4419 We conclude that if both statements belong to the same
4420 basic block and STMT is before NITER_BOUND->stmt and there are no
4421 statements with side effects in between. */
4423 if (niter_bound->is_exit)
4425 if (stmt == niter_bound->stmt
4426 || !stmt_dominates_stmt_p (niter_bound->stmt, stmt))
4427 return false;
4428 cmp = GE_EXPR;
4430 else
4432 if (!stmt_dominates_stmt_p (niter_bound->stmt, stmt))
4434 gimple_stmt_iterator bsi;
4435 if (gimple_bb (stmt) != gimple_bb (niter_bound->stmt)
4436 || gimple_code (stmt) == GIMPLE_PHI
4437 || gimple_code (niter_bound->stmt) == GIMPLE_PHI)
4438 return false;
4440 /* By stmt_dominates_stmt_p we already know that STMT appears
4441 before NITER_BOUND->STMT. Still need to test that the loop
4442 can not be terinated by a side effect in between. */
4443 for (bsi = gsi_for_stmt (stmt); gsi_stmt (bsi) != niter_bound->stmt;
4444 gsi_next (&bsi))
4445 if (gimple_has_side_effects (gsi_stmt (bsi)))
4446 return false;
4447 bound += 1;
4448 if (bound == 0
4449 || !wi::fits_to_tree_p (bound, nit_type))
4450 return false;
4452 cmp = GT_EXPR;
4455 e = fold_binary (cmp, boolean_type_node,
4456 niter, wide_int_to_tree (nit_type, bound));
4457 return e && integer_nonzerop (e);
4460 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
4462 bool
4463 nowrap_type_p (tree type)
4465 if (ANY_INTEGRAL_TYPE_P (type)
4466 && TYPE_OVERFLOW_UNDEFINED (type))
4467 return true;
4469 if (POINTER_TYPE_P (type))
4470 return true;
4472 return false;
4475 /* Return true if we can prove LOOP is exited before evolution of induction
4476 variable {BASE, STEP} overflows with respect to its type bound. */
4478 static bool
4479 loop_exits_before_overflow (tree base, tree step,
4480 gimple *at_stmt, struct loop *loop)
4482 widest_int niter;
4483 struct control_iv *civ;
4484 struct nb_iter_bound *bound;
4485 tree e, delta, step_abs, unsigned_base;
4486 tree type = TREE_TYPE (step);
4487 tree unsigned_type, valid_niter;
4489 /* Don't issue signed overflow warnings. */
4490 fold_defer_overflow_warnings ();
4492 /* Compute the number of iterations before we reach the bound of the
4493 type, and verify that the loop is exited before this occurs. */
4494 unsigned_type = unsigned_type_for (type);
4495 unsigned_base = fold_convert (unsigned_type, base);
4497 if (tree_int_cst_sign_bit (step))
4499 tree extreme = fold_convert (unsigned_type,
4500 lower_bound_in_type (type, type));
4501 delta = fold_build2 (MINUS_EXPR, unsigned_type, unsigned_base, extreme);
4502 step_abs = fold_build1 (NEGATE_EXPR, unsigned_type,
4503 fold_convert (unsigned_type, step));
4505 else
4507 tree extreme = fold_convert (unsigned_type,
4508 upper_bound_in_type (type, type));
4509 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, unsigned_base);
4510 step_abs = fold_convert (unsigned_type, step);
4513 valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
4515 estimate_numbers_of_iterations (loop);
4517 if (max_loop_iterations (loop, &niter)
4518 && wi::fits_to_tree_p (niter, TREE_TYPE (valid_niter))
4519 && (e = fold_binary (GT_EXPR, boolean_type_node, valid_niter,
4520 wide_int_to_tree (TREE_TYPE (valid_niter),
4521 niter))) != NULL
4522 && integer_nonzerop (e))
4524 fold_undefer_and_ignore_overflow_warnings ();
4525 return true;
4527 if (at_stmt)
4528 for (bound = loop->bounds; bound; bound = bound->next)
4530 if (n_of_executions_at_most (at_stmt, bound, valid_niter))
4532 fold_undefer_and_ignore_overflow_warnings ();
4533 return true;
4536 fold_undefer_and_ignore_overflow_warnings ();
4538 /* Try to prove loop is exited before {base, step} overflows with the
4539 help of analyzed loop control IV. This is done only for IVs with
4540 constant step because otherwise we don't have the information. */
4541 if (TREE_CODE (step) == INTEGER_CST)
4543 for (civ = loop->control_ivs; civ; civ = civ->next)
4545 enum tree_code code;
4546 tree civ_type = TREE_TYPE (civ->step);
4548 /* Have to consider type difference because operand_equal_p ignores
4549 that for constants. */
4550 if (TYPE_UNSIGNED (type) != TYPE_UNSIGNED (civ_type)
4551 || element_precision (type) != element_precision (civ_type))
4552 continue;
4554 /* Only consider control IV with same step. */
4555 if (!operand_equal_p (step, civ->step, 0))
4556 continue;
4558 /* Done proving if this is a no-overflow control IV. */
4559 if (operand_equal_p (base, civ->base, 0))
4560 return true;
4562 /* Control IV is recorded after expanding simple operations,
4563 Here we expand base and compare it too. */
4564 tree expanded_base = expand_simple_operations (base);
4565 if (operand_equal_p (expanded_base, civ->base, 0))
4566 return true;
4568 /* If this is a before stepping control IV, in other words, we have
4570 {civ_base, step} = {base + step, step}
4572 Because civ {base + step, step} doesn't overflow during loop
4573 iterations, {base, step} will not overflow if we can prove the
4574 operation "base + step" does not overflow. Specifically, we try
4575 to prove below conditions are satisfied:
4577 base <= UPPER_BOUND (type) - step ;;step > 0
4578 base >= LOWER_BOUND (type) - step ;;step < 0
4580 by proving the reverse conditions are false using loop's initial
4581 condition. */
4582 if (POINTER_TYPE_P (TREE_TYPE (base)))
4583 code = POINTER_PLUS_EXPR;
4584 else
4585 code = PLUS_EXPR;
4587 tree stepped = fold_build2 (code, TREE_TYPE (base), base, step);
4588 tree expanded_stepped = fold_build2 (code, TREE_TYPE (base),
4589 expanded_base, step);
4590 if (operand_equal_p (stepped, civ->base, 0)
4591 || operand_equal_p (expanded_stepped, civ->base, 0))
4593 tree extreme;
4595 if (tree_int_cst_sign_bit (step))
4597 code = LT_EXPR;
4598 extreme = lower_bound_in_type (type, type);
4600 else
4602 code = GT_EXPR;
4603 extreme = upper_bound_in_type (type, type);
4605 extreme = fold_build2 (MINUS_EXPR, type, extreme, step);
4606 e = fold_build2 (code, boolean_type_node, base, extreme);
4607 e = simplify_using_initial_conditions (loop, e);
4608 if (integer_zerop (e))
4609 return true;
4614 return false;
4617 /* VAR is scev variable whose evolution part is constant STEP, this function
4618 proves that VAR can't overflow by using value range info. If VAR's value
4619 range is [MIN, MAX], it can be proven by:
4620 MAX + step doesn't overflow ; if step > 0
4622 MIN + step doesn't underflow ; if step < 0.
4624 We can only do this if var is computed in every loop iteration, i.e, var's
4625 definition has to dominate loop latch. Consider below example:
4628 unsigned int i;
4630 <bb 3>:
4632 <bb 4>:
4633 # RANGE [0, 4294967294] NONZERO 65535
4634 # i_21 = PHI <0(3), i_18(9)>
4635 if (i_21 != 0)
4636 goto <bb 6>;
4637 else
4638 goto <bb 8>;
4640 <bb 6>:
4641 # RANGE [0, 65533] NONZERO 65535
4642 _6 = i_21 + 4294967295;
4643 # RANGE [0, 65533] NONZERO 65535
4644 _7 = (long unsigned int) _6;
4645 # RANGE [0, 524264] NONZERO 524280
4646 _8 = _7 * 8;
4647 # PT = nonlocal escaped
4648 _9 = a_14 + _8;
4649 *_9 = 0;
4651 <bb 8>:
4652 # RANGE [1, 65535] NONZERO 65535
4653 i_18 = i_21 + 1;
4654 if (i_18 >= 65535)
4655 goto <bb 10>;
4656 else
4657 goto <bb 9>;
4659 <bb 9>:
4660 goto <bb 4>;
4662 <bb 10>:
4663 return;
4666 VAR _6 doesn't overflow only with pre-condition (i_21 != 0), here we
4667 can't use _6 to prove no-overlfow for _7. In fact, var _7 takes value
4668 sequence (4294967295, 0, 1, ..., 65533) in loop life time, rather than
4669 (4294967295, 4294967296, ...). */
4671 static bool
4672 scev_var_range_cant_overflow (tree var, tree step, struct loop *loop)
4674 tree type;
4675 wide_int minv, maxv, diff, step_wi;
4676 enum value_range_type rtype;
4678 if (TREE_CODE (step) != INTEGER_CST || !INTEGRAL_TYPE_P (TREE_TYPE (var)))
4679 return false;
4681 /* Check if VAR evaluates in every loop iteration. It's not the case
4682 if VAR is default definition or does not dominate loop's latch. */
4683 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var));
4684 if (!def_bb || !dominated_by_p (CDI_DOMINATORS, loop->latch, def_bb))
4685 return false;
4687 rtype = get_range_info (var, &minv, &maxv);
4688 if (rtype != VR_RANGE)
4689 return false;
4691 /* VAR is a scev whose evolution part is STEP and value range info
4692 is [MIN, MAX], we can prove its no-overflowness by conditions:
4694 type_MAX - MAX >= step ; if step > 0
4695 MIN - type_MIN >= |step| ; if step < 0.
4697 Or VAR must take value outside of value range, which is not true. */
4698 step_wi = wi::to_wide (step);
4699 type = TREE_TYPE (var);
4700 if (tree_int_cst_sign_bit (step))
4702 diff = minv - wi::to_wide (lower_bound_in_type (type, type));
4703 step_wi = - step_wi;
4705 else
4706 diff = wi::to_wide (upper_bound_in_type (type, type)) - maxv;
4708 return (wi::geu_p (diff, step_wi));
4711 /* Return false only when the induction variable BASE + STEP * I is
4712 known to not overflow: i.e. when the number of iterations is small
4713 enough with respect to the step and initial condition in order to
4714 keep the evolution confined in TYPEs bounds. Return true when the
4715 iv is known to overflow or when the property is not computable.
4717 USE_OVERFLOW_SEMANTICS is true if this function should assume that
4718 the rules for overflow of the given language apply (e.g., that signed
4719 arithmetics in C does not overflow).
4721 If VAR is a ssa variable, this function also returns false if VAR can
4722 be proven not overflow with value range info. */
4724 bool
4725 scev_probably_wraps_p (tree var, tree base, tree step,
4726 gimple *at_stmt, struct loop *loop,
4727 bool use_overflow_semantics)
4729 /* FIXME: We really need something like
4730 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
4732 We used to test for the following situation that frequently appears
4733 during address arithmetics:
4735 D.1621_13 = (long unsigned intD.4) D.1620_12;
4736 D.1622_14 = D.1621_13 * 8;
4737 D.1623_15 = (doubleD.29 *) D.1622_14;
4739 And derived that the sequence corresponding to D_14
4740 can be proved to not wrap because it is used for computing a
4741 memory access; however, this is not really the case -- for example,
4742 if D_12 = (unsigned char) [254,+,1], then D_14 has values
4743 2032, 2040, 0, 8, ..., but the code is still legal. */
4745 if (chrec_contains_undetermined (base)
4746 || chrec_contains_undetermined (step))
4747 return true;
4749 if (integer_zerop (step))
4750 return false;
4752 /* If we can use the fact that signed and pointer arithmetics does not
4753 wrap, we are done. */
4754 if (use_overflow_semantics && nowrap_type_p (TREE_TYPE (base)))
4755 return false;
4757 /* To be able to use estimates on number of iterations of the loop,
4758 we must have an upper bound on the absolute value of the step. */
4759 if (TREE_CODE (step) != INTEGER_CST)
4760 return true;
4762 /* Check if var can be proven not overflow with value range info. */
4763 if (var && TREE_CODE (var) == SSA_NAME
4764 && scev_var_range_cant_overflow (var, step, loop))
4765 return false;
4767 if (loop_exits_before_overflow (base, step, at_stmt, loop))
4768 return false;
4770 /* At this point we still don't have a proof that the iv does not
4771 overflow: give up. */
4772 return true;
4775 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
4777 void
4778 free_numbers_of_iterations_estimates (struct loop *loop)
4780 struct control_iv *civ;
4781 struct nb_iter_bound *bound;
4783 loop->nb_iterations = NULL;
4784 loop->estimate_state = EST_NOT_COMPUTED;
4785 for (bound = loop->bounds; bound;)
4787 struct nb_iter_bound *next = bound->next;
4788 ggc_free (bound);
4789 bound = next;
4791 loop->bounds = NULL;
4793 for (civ = loop->control_ivs; civ;)
4795 struct control_iv *next = civ->next;
4796 ggc_free (civ);
4797 civ = next;
4799 loop->control_ivs = NULL;
4802 /* Frees the information on upper bounds on numbers of iterations of loops. */
4804 void
4805 free_numbers_of_iterations_estimates (function *fn)
4807 struct loop *loop;
4809 FOR_EACH_LOOP_FN (fn, loop, 0)
4810 free_numbers_of_iterations_estimates (loop);
4813 /* Substitute value VAL for ssa name NAME inside expressions held
4814 at LOOP. */
4816 void
4817 substitute_in_loop_info (struct loop *loop, tree name, tree val)
4819 loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);