2013-08-02 Paolo Carlini <paolo.carlini@oracle.com>
[official-gcc.git] / gcc / tree-ssa-loop-niter.c
blob9d6f9efb089ed2531dcf3fa87dfeed25f8b98cfe
1 /* Functions to determine/estimate number of iterations of a loop.
2 Copyright (C) 2004-2013 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 "tm.h"
24 #include "tree.h"
25 #include "tm_p.h"
26 #include "basic-block.h"
27 #include "gimple-pretty-print.h"
28 #include "intl.h"
29 #include "tree-flow.h"
30 #include "dumpfile.h"
31 #include "cfgloop.h"
32 #include "ggc.h"
33 #include "tree-chrec.h"
34 #include "tree-scalar-evolution.h"
35 #include "tree-data-ref.h"
36 #include "params.h"
37 #include "flags.h"
38 #include "diagnostic-core.h"
39 #include "tree-inline.h"
40 #include "tree-pass.h"
42 #define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
44 /* The maximum number of dominator BBs we search for conditions
45 of loop header copies we use for simplifying a conditional
46 expression. */
47 #define MAX_DOMINATORS_TO_WALK 8
51 Analysis of number of iterations of an affine exit test.
55 /* Bounds on some value, BELOW <= X <= UP. */
57 typedef struct
59 mpz_t below, up;
60 } bounds;
63 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */
65 static void
66 split_to_var_and_offset (tree expr, tree *var, mpz_t offset)
68 tree type = TREE_TYPE (expr);
69 tree op0, op1;
70 double_int off;
71 bool negate = false;
73 *var = expr;
74 mpz_set_ui (offset, 0);
76 switch (TREE_CODE (expr))
78 case MINUS_EXPR:
79 negate = true;
80 /* Fallthru. */
82 case PLUS_EXPR:
83 case POINTER_PLUS_EXPR:
84 op0 = TREE_OPERAND (expr, 0);
85 op1 = TREE_OPERAND (expr, 1);
87 if (TREE_CODE (op1) != INTEGER_CST)
88 break;
90 *var = op0;
91 /* Always sign extend the offset. */
92 off = tree_to_double_int (op1);
93 off = off.sext (TYPE_PRECISION (type));
94 mpz_set_double_int (offset, off, false);
95 if (negate)
96 mpz_neg (offset, offset);
97 break;
99 case INTEGER_CST:
100 *var = build_int_cst_type (type, 0);
101 off = tree_to_double_int (expr);
102 mpz_set_double_int (offset, off, TYPE_UNSIGNED (type));
103 break;
105 default:
106 break;
110 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
111 in TYPE to MIN and MAX. */
113 static void
114 determine_value_range (tree type, tree var, mpz_t off,
115 mpz_t min, mpz_t max)
117 /* If the expression is a constant, we know its value exactly. */
118 if (integer_zerop (var))
120 mpz_set (min, off);
121 mpz_set (max, off);
122 return;
125 /* If the computation may wrap, we know nothing about the value, except for
126 the range of the type. */
127 get_type_static_bounds (type, min, max);
128 if (!nowrap_type_p (type))
129 return;
131 /* Since the addition of OFF does not wrap, if OFF is positive, then we may
132 add it to MIN, otherwise to MAX. */
133 if (mpz_sgn (off) < 0)
134 mpz_add (max, max, off);
135 else
136 mpz_add (min, min, off);
139 /* Stores the bounds on the difference of the values of the expressions
140 (var + X) and (var + Y), computed in TYPE, to BNDS. */
142 static void
143 bound_difference_of_offsetted_base (tree type, mpz_t x, mpz_t y,
144 bounds *bnds)
146 int rel = mpz_cmp (x, y);
147 bool may_wrap = !nowrap_type_p (type);
148 mpz_t m;
150 /* If X == Y, then the expressions are always equal.
151 If X > Y, there are the following possibilities:
152 a) neither of var + X and var + Y overflow or underflow, or both of
153 them do. Then their difference is X - Y.
154 b) var + X overflows, and var + Y does not. Then the values of the
155 expressions are var + X - M and var + Y, where M is the range of
156 the type, and their difference is X - Y - M.
157 c) var + Y underflows and var + X does not. Their difference again
158 is M - X + Y.
159 Therefore, if the arithmetics in type does not overflow, then the
160 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
161 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
162 (X - Y, X - Y + M). */
164 if (rel == 0)
166 mpz_set_ui (bnds->below, 0);
167 mpz_set_ui (bnds->up, 0);
168 return;
171 mpz_init (m);
172 mpz_set_double_int (m, double_int::mask (TYPE_PRECISION (type)), true);
173 mpz_add_ui (m, m, 1);
174 mpz_sub (bnds->up, x, y);
175 mpz_set (bnds->below, bnds->up);
177 if (may_wrap)
179 if (rel > 0)
180 mpz_sub (bnds->below, bnds->below, m);
181 else
182 mpz_add (bnds->up, bnds->up, m);
185 mpz_clear (m);
188 /* From condition C0 CMP C1 derives information regarding the
189 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
190 and stores it to BNDS. */
192 static void
193 refine_bounds_using_guard (tree type, tree varx, mpz_t offx,
194 tree vary, mpz_t offy,
195 tree c0, enum tree_code cmp, tree c1,
196 bounds *bnds)
198 tree varc0, varc1, tmp, ctype;
199 mpz_t offc0, offc1, loffx, loffy, bnd;
200 bool lbound = false;
201 bool no_wrap = nowrap_type_p (type);
202 bool x_ok, y_ok;
204 switch (cmp)
206 case LT_EXPR:
207 case LE_EXPR:
208 case GT_EXPR:
209 case GE_EXPR:
210 STRIP_SIGN_NOPS (c0);
211 STRIP_SIGN_NOPS (c1);
212 ctype = TREE_TYPE (c0);
213 if (!useless_type_conversion_p (ctype, type))
214 return;
216 break;
218 case EQ_EXPR:
219 /* We could derive quite precise information from EQ_EXPR, however, such
220 a guard is unlikely to appear, so we do not bother with handling
221 it. */
222 return;
224 case NE_EXPR:
225 /* NE_EXPR comparisons do not contain much of useful information, except for
226 special case of comparing with the bounds of the type. */
227 if (TREE_CODE (c1) != INTEGER_CST
228 || !INTEGRAL_TYPE_P (type))
229 return;
231 /* Ensure that the condition speaks about an expression in the same type
232 as X and Y. */
233 ctype = TREE_TYPE (c0);
234 if (TYPE_PRECISION (ctype) != TYPE_PRECISION (type))
235 return;
236 c0 = fold_convert (type, c0);
237 c1 = fold_convert (type, c1);
239 if (TYPE_MIN_VALUE (type)
240 && operand_equal_p (c1, TYPE_MIN_VALUE (type), 0))
242 cmp = GT_EXPR;
243 break;
245 if (TYPE_MAX_VALUE (type)
246 && operand_equal_p (c1, TYPE_MAX_VALUE (type), 0))
248 cmp = LT_EXPR;
249 break;
252 return;
253 default:
254 return;
257 mpz_init (offc0);
258 mpz_init (offc1);
259 split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0);
260 split_to_var_and_offset (expand_simple_operations (c1), &varc1, offc1);
262 /* We are only interested in comparisons of expressions based on VARX and
263 VARY. TODO -- we might also be able to derive some bounds from
264 expressions containing just one of the variables. */
266 if (operand_equal_p (varx, varc1, 0))
268 tmp = varc0; varc0 = varc1; varc1 = tmp;
269 mpz_swap (offc0, offc1);
270 cmp = swap_tree_comparison (cmp);
273 if (!operand_equal_p (varx, varc0, 0)
274 || !operand_equal_p (vary, varc1, 0))
275 goto end;
277 mpz_init_set (loffx, offx);
278 mpz_init_set (loffy, offy);
280 if (cmp == GT_EXPR || cmp == GE_EXPR)
282 tmp = varx; varx = vary; vary = tmp;
283 mpz_swap (offc0, offc1);
284 mpz_swap (loffx, loffy);
285 cmp = swap_tree_comparison (cmp);
286 lbound = true;
289 /* If there is no overflow, the condition implies that
291 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
293 The overflows and underflows may complicate things a bit; each
294 overflow decreases the appropriate offset by M, and underflow
295 increases it by M. The above inequality would not necessarily be
296 true if
298 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
299 VARX + OFFC0 overflows, but VARX + OFFX does not.
300 This may only happen if OFFX < OFFC0.
301 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
302 VARY + OFFC1 underflows and VARY + OFFY does not.
303 This may only happen if OFFY > OFFC1. */
305 if (no_wrap)
307 x_ok = true;
308 y_ok = true;
310 else
312 x_ok = (integer_zerop (varx)
313 || mpz_cmp (loffx, offc0) >= 0);
314 y_ok = (integer_zerop (vary)
315 || mpz_cmp (loffy, offc1) <= 0);
318 if (x_ok && y_ok)
320 mpz_init (bnd);
321 mpz_sub (bnd, loffx, loffy);
322 mpz_add (bnd, bnd, offc1);
323 mpz_sub (bnd, bnd, offc0);
325 if (cmp == LT_EXPR)
326 mpz_sub_ui (bnd, bnd, 1);
328 if (lbound)
330 mpz_neg (bnd, bnd);
331 if (mpz_cmp (bnds->below, bnd) < 0)
332 mpz_set (bnds->below, bnd);
334 else
336 if (mpz_cmp (bnd, bnds->up) < 0)
337 mpz_set (bnds->up, bnd);
339 mpz_clear (bnd);
342 mpz_clear (loffx);
343 mpz_clear (loffy);
344 end:
345 mpz_clear (offc0);
346 mpz_clear (offc1);
349 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
350 The subtraction is considered to be performed in arbitrary precision,
351 without overflows.
353 We do not attempt to be too clever regarding the value ranges of X and
354 Y; most of the time, they are just integers or ssa names offsetted by
355 integer. However, we try to use the information contained in the
356 comparisons before the loop (usually created by loop header copying). */
358 static void
359 bound_difference (struct loop *loop, tree x, tree y, bounds *bnds)
361 tree type = TREE_TYPE (x);
362 tree varx, vary;
363 mpz_t offx, offy;
364 mpz_t minx, maxx, miny, maxy;
365 int cnt = 0;
366 edge e;
367 basic_block bb;
368 tree c0, c1;
369 gimple cond;
370 enum tree_code cmp;
372 /* Get rid of unnecessary casts, but preserve the value of
373 the expressions. */
374 STRIP_SIGN_NOPS (x);
375 STRIP_SIGN_NOPS (y);
377 mpz_init (bnds->below);
378 mpz_init (bnds->up);
379 mpz_init (offx);
380 mpz_init (offy);
381 split_to_var_and_offset (x, &varx, offx);
382 split_to_var_and_offset (y, &vary, offy);
384 if (!integer_zerop (varx)
385 && operand_equal_p (varx, vary, 0))
387 /* Special case VARX == VARY -- we just need to compare the
388 offsets. The matters are a bit more complicated in the
389 case addition of offsets may wrap. */
390 bound_difference_of_offsetted_base (type, offx, offy, bnds);
392 else
394 /* Otherwise, use the value ranges to determine the initial
395 estimates on below and up. */
396 mpz_init (minx);
397 mpz_init (maxx);
398 mpz_init (miny);
399 mpz_init (maxy);
400 determine_value_range (type, varx, offx, minx, maxx);
401 determine_value_range (type, vary, offy, miny, maxy);
403 mpz_sub (bnds->below, minx, maxy);
404 mpz_sub (bnds->up, maxx, miny);
405 mpz_clear (minx);
406 mpz_clear (maxx);
407 mpz_clear (miny);
408 mpz_clear (maxy);
411 /* If both X and Y are constants, we cannot get any more precise. */
412 if (integer_zerop (varx) && integer_zerop (vary))
413 goto end;
415 /* Now walk the dominators of the loop header and use the entry
416 guards to refine the estimates. */
417 for (bb = loop->header;
418 bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK;
419 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
421 if (!single_pred_p (bb))
422 continue;
423 e = single_pred_edge (bb);
425 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
426 continue;
428 cond = last_stmt (e->src);
429 c0 = gimple_cond_lhs (cond);
430 cmp = gimple_cond_code (cond);
431 c1 = gimple_cond_rhs (cond);
433 if (e->flags & EDGE_FALSE_VALUE)
434 cmp = invert_tree_comparison (cmp, false);
436 refine_bounds_using_guard (type, varx, offx, vary, offy,
437 c0, cmp, c1, bnds);
438 ++cnt;
441 end:
442 mpz_clear (offx);
443 mpz_clear (offy);
446 /* Update the bounds in BNDS that restrict the value of X to the bounds
447 that restrict the value of X + DELTA. X can be obtained as a
448 difference of two values in TYPE. */
450 static void
451 bounds_add (bounds *bnds, double_int delta, tree type)
453 mpz_t mdelta, max;
455 mpz_init (mdelta);
456 mpz_set_double_int (mdelta, delta, false);
458 mpz_init (max);
459 mpz_set_double_int (max, double_int::mask (TYPE_PRECISION (type)), true);
461 mpz_add (bnds->up, bnds->up, mdelta);
462 mpz_add (bnds->below, bnds->below, mdelta);
464 if (mpz_cmp (bnds->up, max) > 0)
465 mpz_set (bnds->up, max);
467 mpz_neg (max, max);
468 if (mpz_cmp (bnds->below, max) < 0)
469 mpz_set (bnds->below, max);
471 mpz_clear (mdelta);
472 mpz_clear (max);
475 /* Update the bounds in BNDS that restrict the value of X to the bounds
476 that restrict the value of -X. */
478 static void
479 bounds_negate (bounds *bnds)
481 mpz_t tmp;
483 mpz_init_set (tmp, bnds->up);
484 mpz_neg (bnds->up, bnds->below);
485 mpz_neg (bnds->below, tmp);
486 mpz_clear (tmp);
489 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
491 static tree
492 inverse (tree x, tree mask)
494 tree type = TREE_TYPE (x);
495 tree rslt;
496 unsigned ctr = tree_floor_log2 (mask);
498 if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT)
500 unsigned HOST_WIDE_INT ix;
501 unsigned HOST_WIDE_INT imask;
502 unsigned HOST_WIDE_INT irslt = 1;
504 gcc_assert (cst_and_fits_in_hwi (x));
505 gcc_assert (cst_and_fits_in_hwi (mask));
507 ix = int_cst_value (x);
508 imask = int_cst_value (mask);
510 for (; ctr; ctr--)
512 irslt *= ix;
513 ix *= ix;
515 irslt &= imask;
517 rslt = build_int_cst_type (type, irslt);
519 else
521 rslt = build_int_cst (type, 1);
522 for (; ctr; ctr--)
524 rslt = int_const_binop (MULT_EXPR, rslt, x);
525 x = int_const_binop (MULT_EXPR, x, x);
527 rslt = int_const_binop (BIT_AND_EXPR, rslt, mask);
530 return rslt;
533 /* Derives the upper bound BND on the number of executions of loop with exit
534 condition S * i <> C. If NO_OVERFLOW is true, then the control variable of
535 the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed
536 that the loop ends through this exit, i.e., the induction variable ever
537 reaches the value of C.
539 The value C is equal to final - base, where final and base are the final and
540 initial value of the actual induction variable in the analysed loop. BNDS
541 bounds the value of this difference when computed in signed type with
542 unbounded range, while the computation of C is performed in an unsigned
543 type with the range matching the range of the type of the induction variable.
544 In particular, BNDS.up contains an upper bound on C in the following cases:
545 -- if the iv must reach its final value without overflow, i.e., if
546 NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
547 -- if final >= base, which we know to hold when BNDS.below >= 0. */
549 static void
550 number_of_iterations_ne_max (mpz_t bnd, bool no_overflow, tree c, tree s,
551 bounds *bnds, bool exit_must_be_taken)
553 double_int max;
554 mpz_t d;
555 tree type = TREE_TYPE (c);
556 bool bnds_u_valid = ((no_overflow && exit_must_be_taken)
557 || mpz_sgn (bnds->below) >= 0);
559 if (integer_onep (s)
560 || (TREE_CODE (c) == INTEGER_CST
561 && TREE_CODE (s) == INTEGER_CST
562 && tree_to_double_int (c).mod (tree_to_double_int (s),
563 TYPE_UNSIGNED (type),
564 EXACT_DIV_EXPR).is_zero ())
565 || (TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (c))
566 && multiple_of_p (type, c, s)))
568 /* If C is an exact multiple of S, then its value will be reached before
569 the induction variable overflows (unless the loop is exited in some
570 other way before). Note that the actual induction variable in the
571 loop (which ranges from base to final instead of from 0 to C) may
572 overflow, in which case BNDS.up will not be giving a correct upper
573 bound on C; thus, BNDS_U_VALID had to be computed in advance. */
574 no_overflow = true;
575 exit_must_be_taken = true;
578 /* If the induction variable can overflow, the number of iterations is at
579 most the period of the control variable (or infinite, but in that case
580 the whole # of iterations analysis will fail). */
581 if (!no_overflow)
583 max = double_int::mask (TYPE_PRECISION (type)
584 - tree_low_cst (num_ending_zeros (s), 1));
585 mpz_set_double_int (bnd, max, true);
586 return;
589 /* Now we know that the induction variable does not overflow, so the loop
590 iterates at most (range of type / S) times. */
591 mpz_set_double_int (bnd, double_int::mask (TYPE_PRECISION (type)), true);
593 /* If the induction variable is guaranteed to reach the value of C before
594 overflow, ... */
595 if (exit_must_be_taken)
597 /* ... then we can strengthen this to C / S, and possibly we can use
598 the upper bound on C given by BNDS. */
599 if (TREE_CODE (c) == INTEGER_CST)
600 mpz_set_double_int (bnd, tree_to_double_int (c), true);
601 else if (bnds_u_valid)
602 mpz_set (bnd, bnds->up);
605 mpz_init (d);
606 mpz_set_double_int (d, tree_to_double_int (s), true);
607 mpz_fdiv_q (bnd, bnd, d);
608 mpz_clear (d);
611 /* Determines number of iterations of loop whose ending condition
612 is IV <> FINAL. TYPE is the type of the iv. The number of
613 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
614 we know that the exit must be taken eventually, i.e., that the IV
615 ever reaches the value FINAL (we derived this earlier, and possibly set
616 NITER->assumptions to make sure this is the case). BNDS contains the
617 bounds on the difference FINAL - IV->base. */
619 static bool
620 number_of_iterations_ne (tree type, affine_iv *iv, tree final,
621 struct tree_niter_desc *niter, bool exit_must_be_taken,
622 bounds *bnds)
624 tree niter_type = unsigned_type_for (type);
625 tree s, c, d, bits, assumption, tmp, bound;
626 mpz_t max;
628 niter->control = *iv;
629 niter->bound = final;
630 niter->cmp = NE_EXPR;
632 /* Rearrange the terms so that we get inequality S * i <> C, with S
633 positive. Also cast everything to the unsigned type. If IV does
634 not overflow, BNDS bounds the value of C. Also, this is the
635 case if the computation |FINAL - IV->base| does not overflow, i.e.,
636 if BNDS->below in the result is nonnegative. */
637 if (tree_int_cst_sign_bit (iv->step))
639 s = fold_convert (niter_type,
640 fold_build1 (NEGATE_EXPR, type, iv->step));
641 c = fold_build2 (MINUS_EXPR, niter_type,
642 fold_convert (niter_type, iv->base),
643 fold_convert (niter_type, final));
644 bounds_negate (bnds);
646 else
648 s = fold_convert (niter_type, iv->step);
649 c = fold_build2 (MINUS_EXPR, niter_type,
650 fold_convert (niter_type, final),
651 fold_convert (niter_type, iv->base));
654 mpz_init (max);
655 number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds,
656 exit_must_be_taken);
657 niter->max = mpz_get_double_int (niter_type, max, false);
658 mpz_clear (max);
660 /* First the trivial cases -- when the step is 1. */
661 if (integer_onep (s))
663 niter->niter = c;
664 return true;
667 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
668 is infinite. Otherwise, the number of iterations is
669 (inverse(s/d) * (c/d)) mod (size of mode/d). */
670 bits = num_ending_zeros (s);
671 bound = build_low_bits_mask (niter_type,
672 (TYPE_PRECISION (niter_type)
673 - tree_low_cst (bits, 1)));
675 d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
676 build_int_cst (niter_type, 1), bits);
677 s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
679 if (!exit_must_be_taken)
681 /* If we cannot assume that the exit is taken eventually, record the
682 assumptions for divisibility of c. */
683 assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d);
684 assumption = fold_build2 (EQ_EXPR, boolean_type_node,
685 assumption, build_int_cst (niter_type, 0));
686 if (!integer_nonzerop (assumption))
687 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
688 niter->assumptions, assumption);
691 c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d);
692 tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound));
693 niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound);
694 return true;
697 /* Checks whether we can determine the final value of the control variable
698 of the loop with ending condition IV0 < IV1 (computed in TYPE).
699 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
700 of the step. The assumptions necessary to ensure that the computation
701 of the final value does not overflow are recorded in NITER. If we
702 find the final value, we adjust DELTA and return TRUE. Otherwise
703 we return false. BNDS bounds the value of IV1->base - IV0->base,
704 and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
705 true if we know that the exit must be taken eventually. */
707 static bool
708 number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1,
709 struct tree_niter_desc *niter,
710 tree *delta, tree step,
711 bool exit_must_be_taken, bounds *bnds)
713 tree niter_type = TREE_TYPE (step);
714 tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step);
715 tree tmod;
716 mpz_t mmod;
717 tree assumption = boolean_true_node, bound, noloop;
718 bool ret = false, fv_comp_no_overflow;
719 tree type1 = type;
720 if (POINTER_TYPE_P (type))
721 type1 = sizetype;
723 if (TREE_CODE (mod) != INTEGER_CST)
724 return false;
725 if (integer_nonzerop (mod))
726 mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
727 tmod = fold_convert (type1, mod);
729 mpz_init (mmod);
730 mpz_set_double_int (mmod, tree_to_double_int (mod), true);
731 mpz_neg (mmod, mmod);
733 /* If the induction variable does not overflow and the exit is taken,
734 then the computation of the final value does not overflow. This is
735 also obviously the case if the new final value is equal to the
736 current one. Finally, we postulate this for pointer type variables,
737 as the code cannot rely on the object to that the pointer points being
738 placed at the end of the address space (and more pragmatically,
739 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
740 if (integer_zerop (mod) || POINTER_TYPE_P (type))
741 fv_comp_no_overflow = true;
742 else if (!exit_must_be_taken)
743 fv_comp_no_overflow = false;
744 else
745 fv_comp_no_overflow =
746 (iv0->no_overflow && integer_nonzerop (iv0->step))
747 || (iv1->no_overflow && integer_nonzerop (iv1->step));
749 if (integer_nonzerop (iv0->step))
751 /* The final value of the iv is iv1->base + MOD, assuming that this
752 computation does not overflow, and that
753 iv0->base <= iv1->base + MOD. */
754 if (!fv_comp_no_overflow)
756 bound = fold_build2 (MINUS_EXPR, type1,
757 TYPE_MAX_VALUE (type1), tmod);
758 assumption = fold_build2 (LE_EXPR, boolean_type_node,
759 iv1->base, bound);
760 if (integer_zerop (assumption))
761 goto end;
763 if (mpz_cmp (mmod, bnds->below) < 0)
764 noloop = boolean_false_node;
765 else if (POINTER_TYPE_P (type))
766 noloop = fold_build2 (GT_EXPR, boolean_type_node,
767 iv0->base,
768 fold_build_pointer_plus (iv1->base, tmod));
769 else
770 noloop = fold_build2 (GT_EXPR, boolean_type_node,
771 iv0->base,
772 fold_build2 (PLUS_EXPR, type1,
773 iv1->base, tmod));
775 else
777 /* The final value of the iv is iv0->base - MOD, assuming that this
778 computation does not overflow, and that
779 iv0->base - MOD <= iv1->base. */
780 if (!fv_comp_no_overflow)
782 bound = fold_build2 (PLUS_EXPR, type1,
783 TYPE_MIN_VALUE (type1), tmod);
784 assumption = fold_build2 (GE_EXPR, boolean_type_node,
785 iv0->base, bound);
786 if (integer_zerop (assumption))
787 goto end;
789 if (mpz_cmp (mmod, bnds->below) < 0)
790 noloop = boolean_false_node;
791 else if (POINTER_TYPE_P (type))
792 noloop = fold_build2 (GT_EXPR, boolean_type_node,
793 fold_build_pointer_plus (iv0->base,
794 fold_build1 (NEGATE_EXPR,
795 type1, tmod)),
796 iv1->base);
797 else
798 noloop = fold_build2 (GT_EXPR, boolean_type_node,
799 fold_build2 (MINUS_EXPR, type1,
800 iv0->base, tmod),
801 iv1->base);
804 if (!integer_nonzerop (assumption))
805 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
806 niter->assumptions,
807 assumption);
808 if (!integer_zerop (noloop))
809 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
810 niter->may_be_zero,
811 noloop);
812 bounds_add (bnds, tree_to_double_int (mod), type);
813 *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod);
815 ret = true;
816 end:
817 mpz_clear (mmod);
818 return ret;
821 /* Add assertions to NITER that ensure that the control variable of the loop
822 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
823 are TYPE. Returns false if we can prove that there is an overflow, true
824 otherwise. STEP is the absolute value of the step. */
826 static bool
827 assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
828 struct tree_niter_desc *niter, tree step)
830 tree bound, d, assumption, diff;
831 tree niter_type = TREE_TYPE (step);
833 if (integer_nonzerop (iv0->step))
835 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
836 if (iv0->no_overflow)
837 return true;
839 /* If iv0->base is a constant, we can determine the last value before
840 overflow precisely; otherwise we conservatively assume
841 MAX - STEP + 1. */
843 if (TREE_CODE (iv0->base) == INTEGER_CST)
845 d = fold_build2 (MINUS_EXPR, niter_type,
846 fold_convert (niter_type, TYPE_MAX_VALUE (type)),
847 fold_convert (niter_type, iv0->base));
848 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
850 else
851 diff = fold_build2 (MINUS_EXPR, niter_type, step,
852 build_int_cst (niter_type, 1));
853 bound = fold_build2 (MINUS_EXPR, type,
854 TYPE_MAX_VALUE (type), fold_convert (type, diff));
855 assumption = fold_build2 (LE_EXPR, boolean_type_node,
856 iv1->base, bound);
858 else
860 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
861 if (iv1->no_overflow)
862 return true;
864 if (TREE_CODE (iv1->base) == INTEGER_CST)
866 d = fold_build2 (MINUS_EXPR, niter_type,
867 fold_convert (niter_type, iv1->base),
868 fold_convert (niter_type, TYPE_MIN_VALUE (type)));
869 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
871 else
872 diff = fold_build2 (MINUS_EXPR, niter_type, step,
873 build_int_cst (niter_type, 1));
874 bound = fold_build2 (PLUS_EXPR, type,
875 TYPE_MIN_VALUE (type), fold_convert (type, diff));
876 assumption = fold_build2 (GE_EXPR, boolean_type_node,
877 iv0->base, bound);
880 if (integer_zerop (assumption))
881 return false;
882 if (!integer_nonzerop (assumption))
883 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
884 niter->assumptions, assumption);
886 iv0->no_overflow = true;
887 iv1->no_overflow = true;
888 return true;
891 /* Add an assumption to NITER that a loop whose ending condition
892 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
893 bounds the value of IV1->base - IV0->base. */
895 static void
896 assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
897 struct tree_niter_desc *niter, bounds *bnds)
899 tree assumption = boolean_true_node, bound, diff;
900 tree mbz, mbzl, mbzr, type1;
901 bool rolls_p, no_overflow_p;
902 double_int dstep;
903 mpz_t mstep, max;
905 /* We are going to compute the number of iterations as
906 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
907 variant of TYPE. This formula only works if
909 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
911 (where MAX is the maximum value of the unsigned variant of TYPE, and
912 the computations in this formula are performed in full precision,
913 i.e., without overflows).
915 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
916 we have a condition of the form iv0->base - step < iv1->base before the loop,
917 and for loops iv0->base < iv1->base - step * i the condition
918 iv0->base < iv1->base + step, due to loop header copying, which enable us
919 to prove the lower bound.
921 The upper bound is more complicated. Unless the expressions for initial
922 and final value themselves contain enough information, we usually cannot
923 derive it from the context. */
925 /* First check whether the answer does not follow from the bounds we gathered
926 before. */
927 if (integer_nonzerop (iv0->step))
928 dstep = tree_to_double_int (iv0->step);
929 else
931 dstep = tree_to_double_int (iv1->step).sext (TYPE_PRECISION (type));
932 dstep = -dstep;
935 mpz_init (mstep);
936 mpz_set_double_int (mstep, dstep, true);
937 mpz_neg (mstep, mstep);
938 mpz_add_ui (mstep, mstep, 1);
940 rolls_p = mpz_cmp (mstep, bnds->below) <= 0;
942 mpz_init (max);
943 mpz_set_double_int (max, double_int::mask (TYPE_PRECISION (type)), true);
944 mpz_add (max, max, mstep);
945 no_overflow_p = (mpz_cmp (bnds->up, max) <= 0
946 /* For pointers, only values lying inside a single object
947 can be compared or manipulated by pointer arithmetics.
948 Gcc in general does not allow or handle objects larger
949 than half of the address space, hence the upper bound
950 is satisfied for pointers. */
951 || POINTER_TYPE_P (type));
952 mpz_clear (mstep);
953 mpz_clear (max);
955 if (rolls_p && no_overflow_p)
956 return;
958 type1 = type;
959 if (POINTER_TYPE_P (type))
960 type1 = sizetype;
962 /* Now the hard part; we must formulate the assumption(s) as expressions, and
963 we must be careful not to introduce overflow. */
965 if (integer_nonzerop (iv0->step))
967 diff = fold_build2 (MINUS_EXPR, type1,
968 iv0->step, build_int_cst (type1, 1));
970 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
971 0 address never belongs to any object, we can assume this for
972 pointers. */
973 if (!POINTER_TYPE_P (type))
975 bound = fold_build2 (PLUS_EXPR, type1,
976 TYPE_MIN_VALUE (type), diff);
977 assumption = fold_build2 (GE_EXPR, boolean_type_node,
978 iv0->base, bound);
981 /* And then we can compute iv0->base - diff, and compare it with
982 iv1->base. */
983 mbzl = fold_build2 (MINUS_EXPR, type1,
984 fold_convert (type1, iv0->base), diff);
985 mbzr = fold_convert (type1, iv1->base);
987 else
989 diff = fold_build2 (PLUS_EXPR, type1,
990 iv1->step, build_int_cst (type1, 1));
992 if (!POINTER_TYPE_P (type))
994 bound = fold_build2 (PLUS_EXPR, type1,
995 TYPE_MAX_VALUE (type), diff);
996 assumption = fold_build2 (LE_EXPR, boolean_type_node,
997 iv1->base, bound);
1000 mbzl = fold_convert (type1, iv0->base);
1001 mbzr = fold_build2 (MINUS_EXPR, type1,
1002 fold_convert (type1, iv1->base), diff);
1005 if (!integer_nonzerop (assumption))
1006 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1007 niter->assumptions, assumption);
1008 if (!rolls_p)
1010 mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr);
1011 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
1012 niter->may_be_zero, mbz);
1016 /* Determines number of iterations of loop whose ending condition
1017 is IV0 < IV1. TYPE is the type of the iv. The number of
1018 iterations is stored to NITER. BNDS bounds the difference
1019 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
1020 that the exit must be taken eventually. */
1022 static bool
1023 number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
1024 struct tree_niter_desc *niter,
1025 bool exit_must_be_taken, bounds *bnds)
1027 tree niter_type = unsigned_type_for (type);
1028 tree delta, step, s;
1029 mpz_t mstep, tmp;
1031 if (integer_nonzerop (iv0->step))
1033 niter->control = *iv0;
1034 niter->cmp = LT_EXPR;
1035 niter->bound = iv1->base;
1037 else
1039 niter->control = *iv1;
1040 niter->cmp = GT_EXPR;
1041 niter->bound = iv0->base;
1044 delta = fold_build2 (MINUS_EXPR, niter_type,
1045 fold_convert (niter_type, iv1->base),
1046 fold_convert (niter_type, iv0->base));
1048 /* First handle the special case that the step is +-1. */
1049 if ((integer_onep (iv0->step) && integer_zerop (iv1->step))
1050 || (integer_all_onesp (iv1->step) && integer_zerop (iv0->step)))
1052 /* for (i = iv0->base; i < iv1->base; i++)
1056 for (i = iv1->base; i > iv0->base; i--).
1058 In both cases # of iterations is iv1->base - iv0->base, assuming that
1059 iv1->base >= iv0->base.
1061 First try to derive a lower bound on the value of
1062 iv1->base - iv0->base, computed in full precision. If the difference
1063 is nonnegative, we are done, otherwise we must record the
1064 condition. */
1066 if (mpz_sgn (bnds->below) < 0)
1067 niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
1068 iv1->base, iv0->base);
1069 niter->niter = delta;
1070 niter->max = mpz_get_double_int (niter_type, bnds->up, false);
1071 return true;
1074 if (integer_nonzerop (iv0->step))
1075 step = fold_convert (niter_type, iv0->step);
1076 else
1077 step = fold_convert (niter_type,
1078 fold_build1 (NEGATE_EXPR, type, iv1->step));
1080 /* If we can determine the final value of the control iv exactly, we can
1081 transform the condition to != comparison. In particular, this will be
1082 the case if DELTA is constant. */
1083 if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step,
1084 exit_must_be_taken, bnds))
1086 affine_iv zps;
1088 zps.base = build_int_cst (niter_type, 0);
1089 zps.step = step;
1090 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1091 zps does not overflow. */
1092 zps.no_overflow = true;
1094 return number_of_iterations_ne (type, &zps, delta, niter, true, bnds);
1097 /* Make sure that the control iv does not overflow. */
1098 if (!assert_no_overflow_lt (type, iv0, iv1, niter, step))
1099 return false;
1101 /* We determine the number of iterations as (delta + step - 1) / step. For
1102 this to work, we must know that iv1->base >= iv0->base - step + 1,
1103 otherwise the loop does not roll. */
1104 assert_loop_rolls_lt (type, iv0, iv1, niter, bnds);
1106 s = fold_build2 (MINUS_EXPR, niter_type,
1107 step, build_int_cst (niter_type, 1));
1108 delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
1109 niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
1111 mpz_init (mstep);
1112 mpz_init (tmp);
1113 mpz_set_double_int (mstep, tree_to_double_int (step), true);
1114 mpz_add (tmp, bnds->up, mstep);
1115 mpz_sub_ui (tmp, tmp, 1);
1116 mpz_fdiv_q (tmp, tmp, mstep);
1117 niter->max = mpz_get_double_int (niter_type, tmp, false);
1118 mpz_clear (mstep);
1119 mpz_clear (tmp);
1121 return true;
1124 /* Determines number of iterations of loop whose ending condition
1125 is IV0 <= IV1. TYPE is the type of the iv. The number of
1126 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
1127 we know that this condition must eventually become false (we derived this
1128 earlier, and possibly set NITER->assumptions to make sure this
1129 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1131 static bool
1132 number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1,
1133 struct tree_niter_desc *niter, bool exit_must_be_taken,
1134 bounds *bnds)
1136 tree assumption;
1137 tree type1 = type;
1138 if (POINTER_TYPE_P (type))
1139 type1 = sizetype;
1141 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1142 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1143 value of the type. This we must know anyway, since if it is
1144 equal to this value, the loop rolls forever. We do not check
1145 this condition for pointer type ivs, as the code cannot rely on
1146 the object to that the pointer points being placed at the end of
1147 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1148 not defined for pointers). */
1150 if (!exit_must_be_taken && !POINTER_TYPE_P (type))
1152 if (integer_nonzerop (iv0->step))
1153 assumption = fold_build2 (NE_EXPR, boolean_type_node,
1154 iv1->base, TYPE_MAX_VALUE (type));
1155 else
1156 assumption = fold_build2 (NE_EXPR, boolean_type_node,
1157 iv0->base, TYPE_MIN_VALUE (type));
1159 if (integer_zerop (assumption))
1160 return false;
1161 if (!integer_nonzerop (assumption))
1162 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1163 niter->assumptions, assumption);
1166 if (integer_nonzerop (iv0->step))
1168 if (POINTER_TYPE_P (type))
1169 iv1->base = fold_build_pointer_plus_hwi (iv1->base, 1);
1170 else
1171 iv1->base = fold_build2 (PLUS_EXPR, type1, iv1->base,
1172 build_int_cst (type1, 1));
1174 else if (POINTER_TYPE_P (type))
1175 iv0->base = fold_build_pointer_plus_hwi (iv0->base, -1);
1176 else
1177 iv0->base = fold_build2 (MINUS_EXPR, type1,
1178 iv0->base, build_int_cst (type1, 1));
1180 bounds_add (bnds, double_int_one, type1);
1182 return number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken,
1183 bnds);
1186 /* Dumps description of affine induction variable IV to FILE. */
1188 static void
1189 dump_affine_iv (FILE *file, affine_iv *iv)
1191 if (!integer_zerop (iv->step))
1192 fprintf (file, "[");
1194 print_generic_expr (dump_file, iv->base, TDF_SLIM);
1196 if (!integer_zerop (iv->step))
1198 fprintf (file, ", + , ");
1199 print_generic_expr (dump_file, iv->step, TDF_SLIM);
1200 fprintf (file, "]%s", iv->no_overflow ? "(no_overflow)" : "");
1204 /* Determine the number of iterations according to condition (for staying
1205 inside loop) which compares two induction variables using comparison
1206 operator CODE. The induction variable on left side of the comparison
1207 is IV0, the right-hand side is IV1. Both induction variables must have
1208 type TYPE, which must be an integer or pointer type. The steps of the
1209 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1211 LOOP is the loop whose number of iterations we are determining.
1213 ONLY_EXIT is true if we are sure this is the only way the loop could be
1214 exited (including possibly non-returning function calls, exceptions, etc.)
1215 -- in this case we can use the information whether the control induction
1216 variables can overflow or not in a more efficient way.
1218 if EVERY_ITERATION is true, we know the test is executed on every iteration.
1220 The results (number of iterations and assumptions as described in
1221 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
1222 Returns false if it fails to determine number of iterations, true if it
1223 was determined (possibly with some assumptions). */
1225 static bool
1226 number_of_iterations_cond (struct loop *loop,
1227 tree type, affine_iv *iv0, enum tree_code code,
1228 affine_iv *iv1, struct tree_niter_desc *niter,
1229 bool only_exit, bool every_iteration)
1231 bool exit_must_be_taken = false, ret;
1232 bounds bnds;
1234 /* If the test is not executed every iteration, wrapping may make the test
1235 to pass again.
1236 TODO: the overflow case can be still used as unreliable estimate of upper
1237 bound. But we have no API to pass it down to number of iterations code
1238 and, at present, it will not use it anyway. */
1239 if (!every_iteration
1240 && (!iv0->no_overflow || !iv1->no_overflow
1241 || code == NE_EXPR || code == EQ_EXPR))
1242 return false;
1244 /* The meaning of these assumptions is this:
1245 if !assumptions
1246 then the rest of information does not have to be valid
1247 if may_be_zero then the loop does not roll, even if
1248 niter != 0. */
1249 niter->assumptions = boolean_true_node;
1250 niter->may_be_zero = boolean_false_node;
1251 niter->niter = NULL_TREE;
1252 niter->max = double_int_zero;
1254 niter->bound = NULL_TREE;
1255 niter->cmp = ERROR_MARK;
1257 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1258 the control variable is on lhs. */
1259 if (code == GE_EXPR || code == GT_EXPR
1260 || (code == NE_EXPR && integer_zerop (iv0->step)))
1262 SWAP (iv0, iv1);
1263 code = swap_tree_comparison (code);
1266 if (POINTER_TYPE_P (type))
1268 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1269 to the same object. If they do, the control variable cannot wrap
1270 (as wrap around the bounds of memory will never return a pointer
1271 that would be guaranteed to point to the same object, even if we
1272 avoid undefined behavior by casting to size_t and back). */
1273 iv0->no_overflow = true;
1274 iv1->no_overflow = true;
1277 /* If the control induction variable does not overflow and the only exit
1278 from the loop is the one that we analyze, we know it must be taken
1279 eventually. */
1280 if (only_exit)
1282 if (!integer_zerop (iv0->step) && iv0->no_overflow)
1283 exit_must_be_taken = true;
1284 else if (!integer_zerop (iv1->step) && iv1->no_overflow)
1285 exit_must_be_taken = true;
1288 /* We can handle the case when neither of the sides of the comparison is
1289 invariant, provided that the test is NE_EXPR. This rarely occurs in
1290 practice, but it is simple enough to manage. */
1291 if (!integer_zerop (iv0->step) && !integer_zerop (iv1->step))
1293 tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
1294 if (code != NE_EXPR)
1295 return false;
1297 iv0->step = fold_binary_to_constant (MINUS_EXPR, step_type,
1298 iv0->step, iv1->step);
1299 iv0->no_overflow = false;
1300 iv1->step = build_int_cst (step_type, 0);
1301 iv1->no_overflow = true;
1304 /* If the result of the comparison is a constant, the loop is weird. More
1305 precise handling would be possible, but the situation is not common enough
1306 to waste time on it. */
1307 if (integer_zerop (iv0->step) && integer_zerop (iv1->step))
1308 return false;
1310 /* Ignore loops of while (i-- < 10) type. */
1311 if (code != NE_EXPR)
1313 if (iv0->step && tree_int_cst_sign_bit (iv0->step))
1314 return false;
1316 if (!integer_zerop (iv1->step) && !tree_int_cst_sign_bit (iv1->step))
1317 return false;
1320 /* If the loop exits immediately, there is nothing to do. */
1321 tree tem = fold_binary (code, boolean_type_node, iv0->base, iv1->base);
1322 if (tem && integer_zerop (tem))
1324 niter->niter = build_int_cst (unsigned_type_for (type), 0);
1325 niter->max = double_int_zero;
1326 return true;
1329 /* OK, now we know we have a senseful loop. Handle several cases, depending
1330 on what comparison operator is used. */
1331 bound_difference (loop, iv1->base, iv0->base, &bnds);
1333 if (dump_file && (dump_flags & TDF_DETAILS))
1335 fprintf (dump_file,
1336 "Analyzing # of iterations of loop %d\n", loop->num);
1338 fprintf (dump_file, " exit condition ");
1339 dump_affine_iv (dump_file, iv0);
1340 fprintf (dump_file, " %s ",
1341 code == NE_EXPR ? "!="
1342 : code == LT_EXPR ? "<"
1343 : "<=");
1344 dump_affine_iv (dump_file, iv1);
1345 fprintf (dump_file, "\n");
1347 fprintf (dump_file, " bounds on difference of bases: ");
1348 mpz_out_str (dump_file, 10, bnds.below);
1349 fprintf (dump_file, " ... ");
1350 mpz_out_str (dump_file, 10, bnds.up);
1351 fprintf (dump_file, "\n");
1354 switch (code)
1356 case NE_EXPR:
1357 gcc_assert (integer_zerop (iv1->step));
1358 ret = number_of_iterations_ne (type, iv0, iv1->base, niter,
1359 exit_must_be_taken, &bnds);
1360 break;
1362 case LT_EXPR:
1363 ret = number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken,
1364 &bnds);
1365 break;
1367 case LE_EXPR:
1368 ret = number_of_iterations_le (type, iv0, iv1, niter, exit_must_be_taken,
1369 &bnds);
1370 break;
1372 default:
1373 gcc_unreachable ();
1376 mpz_clear (bnds.up);
1377 mpz_clear (bnds.below);
1379 if (dump_file && (dump_flags & TDF_DETAILS))
1381 if (ret)
1383 fprintf (dump_file, " result:\n");
1384 if (!integer_nonzerop (niter->assumptions))
1386 fprintf (dump_file, " under assumptions ");
1387 print_generic_expr (dump_file, niter->assumptions, TDF_SLIM);
1388 fprintf (dump_file, "\n");
1391 if (!integer_zerop (niter->may_be_zero))
1393 fprintf (dump_file, " zero if ");
1394 print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
1395 fprintf (dump_file, "\n");
1398 fprintf (dump_file, " # of iterations ");
1399 print_generic_expr (dump_file, niter->niter, TDF_SLIM);
1400 fprintf (dump_file, ", bounded by ");
1401 dump_double_int (dump_file, niter->max, true);
1402 fprintf (dump_file, "\n");
1404 else
1405 fprintf (dump_file, " failed\n\n");
1407 return ret;
1410 /* Substitute NEW for OLD in EXPR and fold the result. */
1412 static tree
1413 simplify_replace_tree (tree expr, tree old, tree new_tree)
1415 unsigned i, n;
1416 tree ret = NULL_TREE, e, se;
1418 if (!expr)
1419 return NULL_TREE;
1421 /* Do not bother to replace constants. */
1422 if (CONSTANT_CLASS_P (old))
1423 return expr;
1425 if (expr == old
1426 || operand_equal_p (expr, old, 0))
1427 return unshare_expr (new_tree);
1429 if (!EXPR_P (expr))
1430 return expr;
1432 n = TREE_OPERAND_LENGTH (expr);
1433 for (i = 0; i < n; i++)
1435 e = TREE_OPERAND (expr, i);
1436 se = simplify_replace_tree (e, old, new_tree);
1437 if (e == se)
1438 continue;
1440 if (!ret)
1441 ret = copy_node (expr);
1443 TREE_OPERAND (ret, i) = se;
1446 return (ret ? fold (ret) : expr);
1449 /* Expand definitions of ssa names in EXPR as long as they are simple
1450 enough, and return the new expression. */
1452 tree
1453 expand_simple_operations (tree expr)
1455 unsigned i, n;
1456 tree ret = NULL_TREE, e, ee, e1;
1457 enum tree_code code;
1458 gimple stmt;
1460 if (expr == NULL_TREE)
1461 return expr;
1463 if (is_gimple_min_invariant (expr))
1464 return expr;
1466 code = TREE_CODE (expr);
1467 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
1469 n = TREE_OPERAND_LENGTH (expr);
1470 for (i = 0; i < n; i++)
1472 e = TREE_OPERAND (expr, i);
1473 ee = expand_simple_operations (e);
1474 if (e == ee)
1475 continue;
1477 if (!ret)
1478 ret = copy_node (expr);
1480 TREE_OPERAND (ret, i) = ee;
1483 if (!ret)
1484 return expr;
1486 fold_defer_overflow_warnings ();
1487 ret = fold (ret);
1488 fold_undefer_and_ignore_overflow_warnings ();
1489 return ret;
1492 if (TREE_CODE (expr) != SSA_NAME)
1493 return expr;
1495 stmt = SSA_NAME_DEF_STMT (expr);
1496 if (gimple_code (stmt) == GIMPLE_PHI)
1498 basic_block src, dest;
1500 if (gimple_phi_num_args (stmt) != 1)
1501 return expr;
1502 e = PHI_ARG_DEF (stmt, 0);
1504 /* Avoid propagating through loop exit phi nodes, which
1505 could break loop-closed SSA form restrictions. */
1506 dest = gimple_bb (stmt);
1507 src = single_pred (dest);
1508 if (TREE_CODE (e) == SSA_NAME
1509 && src->loop_father != dest->loop_father)
1510 return expr;
1512 return expand_simple_operations (e);
1514 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1515 return expr;
1517 /* Avoid expanding to expressions that contain SSA names that need
1518 to take part in abnormal coalescing. */
1519 ssa_op_iter iter;
1520 FOR_EACH_SSA_TREE_OPERAND (e, stmt, iter, SSA_OP_USE)
1521 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (e))
1522 return expr;
1524 e = gimple_assign_rhs1 (stmt);
1525 code = gimple_assign_rhs_code (stmt);
1526 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1528 if (is_gimple_min_invariant (e))
1529 return e;
1531 if (code == SSA_NAME)
1532 return expand_simple_operations (e);
1534 return expr;
1537 switch (code)
1539 CASE_CONVERT:
1540 /* Casts are simple. */
1541 ee = expand_simple_operations (e);
1542 return fold_build1 (code, TREE_TYPE (expr), ee);
1544 case PLUS_EXPR:
1545 case MINUS_EXPR:
1546 case POINTER_PLUS_EXPR:
1547 /* And increments and decrements by a constant are simple. */
1548 e1 = gimple_assign_rhs2 (stmt);
1549 if (!is_gimple_min_invariant (e1))
1550 return expr;
1552 ee = expand_simple_operations (e);
1553 return fold_build2 (code, TREE_TYPE (expr), ee, e1);
1555 default:
1556 return expr;
1560 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1561 expression (or EXPR unchanged, if no simplification was possible). */
1563 static tree
1564 tree_simplify_using_condition_1 (tree cond, tree expr)
1566 bool changed;
1567 tree e, te, e0, e1, e2, notcond;
1568 enum tree_code code = TREE_CODE (expr);
1570 if (code == INTEGER_CST)
1571 return expr;
1573 if (code == TRUTH_OR_EXPR
1574 || code == TRUTH_AND_EXPR
1575 || code == COND_EXPR)
1577 changed = false;
1579 e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0));
1580 if (TREE_OPERAND (expr, 0) != e0)
1581 changed = true;
1583 e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1));
1584 if (TREE_OPERAND (expr, 1) != e1)
1585 changed = true;
1587 if (code == COND_EXPR)
1589 e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2));
1590 if (TREE_OPERAND (expr, 2) != e2)
1591 changed = true;
1593 else
1594 e2 = NULL_TREE;
1596 if (changed)
1598 if (code == COND_EXPR)
1599 expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
1600 else
1601 expr = fold_build2 (code, boolean_type_node, e0, e1);
1604 return expr;
1607 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
1608 propagation, and vice versa. Fold does not handle this, since it is
1609 considered too expensive. */
1610 if (TREE_CODE (cond) == EQ_EXPR)
1612 e0 = TREE_OPERAND (cond, 0);
1613 e1 = TREE_OPERAND (cond, 1);
1615 /* We know that e0 == e1. Check whether we cannot simplify expr
1616 using this fact. */
1617 e = simplify_replace_tree (expr, e0, e1);
1618 if (integer_zerop (e) || integer_nonzerop (e))
1619 return e;
1621 e = simplify_replace_tree (expr, e1, e0);
1622 if (integer_zerop (e) || integer_nonzerop (e))
1623 return e;
1625 if (TREE_CODE (expr) == EQ_EXPR)
1627 e0 = TREE_OPERAND (expr, 0);
1628 e1 = TREE_OPERAND (expr, 1);
1630 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
1631 e = simplify_replace_tree (cond, e0, e1);
1632 if (integer_zerop (e))
1633 return e;
1634 e = simplify_replace_tree (cond, e1, e0);
1635 if (integer_zerop (e))
1636 return e;
1638 if (TREE_CODE (expr) == NE_EXPR)
1640 e0 = TREE_OPERAND (expr, 0);
1641 e1 = TREE_OPERAND (expr, 1);
1643 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
1644 e = simplify_replace_tree (cond, e0, e1);
1645 if (integer_zerop (e))
1646 return boolean_true_node;
1647 e = simplify_replace_tree (cond, e1, e0);
1648 if (integer_zerop (e))
1649 return boolean_true_node;
1652 te = expand_simple_operations (expr);
1654 /* Check whether COND ==> EXPR. */
1655 notcond = invert_truthvalue (cond);
1656 e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te);
1657 if (e && integer_nonzerop (e))
1658 return e;
1660 /* Check whether COND ==> not EXPR. */
1661 e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te);
1662 if (e && integer_zerop (e))
1663 return e;
1665 return expr;
1668 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1669 expression (or EXPR unchanged, if no simplification was possible).
1670 Wrapper around tree_simplify_using_condition_1 that ensures that chains
1671 of simple operations in definitions of ssa names in COND are expanded,
1672 so that things like casts or incrementing the value of the bound before
1673 the loop do not cause us to fail. */
1675 static tree
1676 tree_simplify_using_condition (tree cond, tree expr)
1678 cond = expand_simple_operations (cond);
1680 return tree_simplify_using_condition_1 (cond, expr);
1683 /* Tries to simplify EXPR using the conditions on entry to LOOP.
1684 Returns the simplified expression (or EXPR unchanged, if no
1685 simplification was possible).*/
1687 static tree
1688 simplify_using_initial_conditions (struct loop *loop, tree expr)
1690 edge e;
1691 basic_block bb;
1692 gimple stmt;
1693 tree cond;
1694 int cnt = 0;
1696 if (TREE_CODE (expr) == INTEGER_CST)
1697 return expr;
1699 /* Limit walking the dominators to avoid quadraticness in
1700 the number of BBs times the number of loops in degenerate
1701 cases. */
1702 for (bb = loop->header;
1703 bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK;
1704 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1706 if (!single_pred_p (bb))
1707 continue;
1708 e = single_pred_edge (bb);
1710 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
1711 continue;
1713 stmt = last_stmt (e->src);
1714 cond = fold_build2 (gimple_cond_code (stmt),
1715 boolean_type_node,
1716 gimple_cond_lhs (stmt),
1717 gimple_cond_rhs (stmt));
1718 if (e->flags & EDGE_FALSE_VALUE)
1719 cond = invert_truthvalue (cond);
1720 expr = tree_simplify_using_condition (cond, expr);
1721 ++cnt;
1724 return expr;
1727 /* Tries to simplify EXPR using the evolutions of the loop invariants
1728 in the superloops of LOOP. Returns the simplified expression
1729 (or EXPR unchanged, if no simplification was possible). */
1731 static tree
1732 simplify_using_outer_evolutions (struct loop *loop, tree expr)
1734 enum tree_code code = TREE_CODE (expr);
1735 bool changed;
1736 tree e, e0, e1, e2;
1738 if (is_gimple_min_invariant (expr))
1739 return expr;
1741 if (code == TRUTH_OR_EXPR
1742 || code == TRUTH_AND_EXPR
1743 || code == COND_EXPR)
1745 changed = false;
1747 e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
1748 if (TREE_OPERAND (expr, 0) != e0)
1749 changed = true;
1751 e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
1752 if (TREE_OPERAND (expr, 1) != e1)
1753 changed = true;
1755 if (code == COND_EXPR)
1757 e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
1758 if (TREE_OPERAND (expr, 2) != e2)
1759 changed = true;
1761 else
1762 e2 = NULL_TREE;
1764 if (changed)
1766 if (code == COND_EXPR)
1767 expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
1768 else
1769 expr = fold_build2 (code, boolean_type_node, e0, e1);
1772 return expr;
1775 e = instantiate_parameters (loop, expr);
1776 if (is_gimple_min_invariant (e))
1777 return e;
1779 return expr;
1782 /* Returns true if EXIT is the only possible exit from LOOP. */
1784 bool
1785 loop_only_exit_p (const struct loop *loop, const_edge exit)
1787 basic_block *body;
1788 gimple_stmt_iterator bsi;
1789 unsigned i;
1790 gimple call;
1792 if (exit != single_exit (loop))
1793 return false;
1795 body = get_loop_body (loop);
1796 for (i = 0; i < loop->num_nodes; i++)
1798 for (bsi = gsi_start_bb (body[i]); !gsi_end_p (bsi); gsi_next (&bsi))
1800 call = gsi_stmt (bsi);
1801 if (gimple_code (call) != GIMPLE_CALL)
1802 continue;
1804 if (gimple_has_side_effects (call))
1806 free (body);
1807 return false;
1812 free (body);
1813 return true;
1816 /* Stores description of number of iterations of LOOP derived from
1817 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
1818 useful information could be derived (and fields of NITER has
1819 meaning described in comments at struct tree_niter_desc
1820 declaration), false otherwise. If WARN is true and
1821 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1822 potentially unsafe assumptions.
1823 When EVERY_ITERATION is true, only tests that are known to be executed
1824 every iteration are considered (i.e. only test that alone bounds the loop).
1827 bool
1828 number_of_iterations_exit (struct loop *loop, edge exit,
1829 struct tree_niter_desc *niter,
1830 bool warn, bool every_iteration)
1832 gimple stmt;
1833 tree type;
1834 tree op0, op1;
1835 enum tree_code code;
1836 affine_iv iv0, iv1;
1837 bool safe;
1839 safe = dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src);
1841 if (every_iteration && !safe)
1842 return false;
1844 niter->assumptions = boolean_false_node;
1845 stmt = last_stmt (exit->src);
1846 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
1847 return false;
1849 /* We want the condition for staying inside loop. */
1850 code = gimple_cond_code (stmt);
1851 if (exit->flags & EDGE_TRUE_VALUE)
1852 code = invert_tree_comparison (code, false);
1854 switch (code)
1856 case GT_EXPR:
1857 case GE_EXPR:
1858 case LT_EXPR:
1859 case LE_EXPR:
1860 case NE_EXPR:
1861 break;
1863 default:
1864 return false;
1867 op0 = gimple_cond_lhs (stmt);
1868 op1 = gimple_cond_rhs (stmt);
1869 type = TREE_TYPE (op0);
1871 if (TREE_CODE (type) != INTEGER_TYPE
1872 && !POINTER_TYPE_P (type))
1873 return false;
1875 if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, false))
1876 return false;
1877 if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, false))
1878 return false;
1880 /* We don't want to see undefined signed overflow warnings while
1881 computing the number of iterations. */
1882 fold_defer_overflow_warnings ();
1884 iv0.base = expand_simple_operations (iv0.base);
1885 iv1.base = expand_simple_operations (iv1.base);
1886 if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter,
1887 loop_only_exit_p (loop, exit), safe))
1889 fold_undefer_and_ignore_overflow_warnings ();
1890 return false;
1893 if (optimize >= 3)
1895 niter->assumptions = simplify_using_outer_evolutions (loop,
1896 niter->assumptions);
1897 niter->may_be_zero = simplify_using_outer_evolutions (loop,
1898 niter->may_be_zero);
1899 niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
1902 niter->assumptions
1903 = simplify_using_initial_conditions (loop,
1904 niter->assumptions);
1905 niter->may_be_zero
1906 = simplify_using_initial_conditions (loop,
1907 niter->may_be_zero);
1909 fold_undefer_and_ignore_overflow_warnings ();
1911 /* If NITER has simplified into a constant, update MAX. */
1912 if (TREE_CODE (niter->niter) == INTEGER_CST)
1913 niter->max = tree_to_double_int (niter->niter);
1915 if (integer_onep (niter->assumptions))
1916 return true;
1918 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1919 But if we can prove that there is overflow or some other source of weird
1920 behavior, ignore the loop even with -funsafe-loop-optimizations. */
1921 if (integer_zerop (niter->assumptions) || !single_exit (loop))
1922 return false;
1924 if (flag_unsafe_loop_optimizations)
1925 niter->assumptions = boolean_true_node;
1927 if (warn)
1929 const char *wording;
1930 location_t loc = gimple_location (stmt);
1932 /* We can provide a more specific warning if one of the operator is
1933 constant and the other advances by +1 or -1. */
1934 if (!integer_zerop (iv1.step)
1935 ? (integer_zerop (iv0.step)
1936 && (integer_onep (iv1.step) || integer_all_onesp (iv1.step)))
1937 : (integer_onep (iv0.step) || integer_all_onesp (iv0.step)))
1938 wording =
1939 flag_unsafe_loop_optimizations
1940 ? N_("assuming that the loop is not infinite")
1941 : N_("cannot optimize possibly infinite loops");
1942 else
1943 wording =
1944 flag_unsafe_loop_optimizations
1945 ? N_("assuming that the loop counter does not overflow")
1946 : N_("cannot optimize loop, the loop counter may overflow");
1948 warning_at ((LOCATION_LINE (loc) > 0) ? loc : input_location,
1949 OPT_Wunsafe_loop_optimizations, "%s", gettext (wording));
1952 return flag_unsafe_loop_optimizations;
1955 /* Try to determine the number of iterations of LOOP. If we succeed,
1956 expression giving number of iterations is returned and *EXIT is
1957 set to the edge from that the information is obtained. Otherwise
1958 chrec_dont_know is returned. */
1960 tree
1961 find_loop_niter (struct loop *loop, edge *exit)
1963 unsigned i;
1964 vec<edge> exits = get_loop_exit_edges (loop);
1965 edge ex;
1966 tree niter = NULL_TREE, aniter;
1967 struct tree_niter_desc desc;
1969 *exit = NULL;
1970 FOR_EACH_VEC_ELT (exits, i, ex)
1972 if (!number_of_iterations_exit (loop, ex, &desc, false))
1973 continue;
1975 if (integer_nonzerop (desc.may_be_zero))
1977 /* We exit in the first iteration through this exit.
1978 We won't find anything better. */
1979 niter = build_int_cst (unsigned_type_node, 0);
1980 *exit = ex;
1981 break;
1984 if (!integer_zerop (desc.may_be_zero))
1985 continue;
1987 aniter = desc.niter;
1989 if (!niter)
1991 /* Nothing recorded yet. */
1992 niter = aniter;
1993 *exit = ex;
1994 continue;
1997 /* Prefer constants, the lower the better. */
1998 if (TREE_CODE (aniter) != INTEGER_CST)
1999 continue;
2001 if (TREE_CODE (niter) != INTEGER_CST)
2003 niter = aniter;
2004 *exit = ex;
2005 continue;
2008 if (tree_int_cst_lt (aniter, niter))
2010 niter = aniter;
2011 *exit = ex;
2012 continue;
2015 exits.release ();
2017 return niter ? niter : chrec_dont_know;
2020 /* Return true if loop is known to have bounded number of iterations. */
2022 bool
2023 finite_loop_p (struct loop *loop)
2025 double_int nit;
2026 int flags;
2028 if (flag_unsafe_loop_optimizations)
2029 return true;
2030 flags = flags_from_decl_or_type (current_function_decl);
2031 if ((flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE))
2033 if (dump_file && (dump_flags & TDF_DETAILS))
2034 fprintf (dump_file, "Found loop %i to be finite: it is within pure or const function.\n",
2035 loop->num);
2036 return true;
2039 if (loop->any_upper_bound
2040 || max_loop_iterations (loop, &nit))
2042 if (dump_file && (dump_flags & TDF_DETAILS))
2043 fprintf (dump_file, "Found loop %i to be finite: upper bound found.\n",
2044 loop->num);
2045 return true;
2047 return false;
2052 Analysis of a number of iterations of a loop by a brute-force evaluation.
2056 /* Bound on the number of iterations we try to evaluate. */
2058 #define MAX_ITERATIONS_TO_TRACK \
2059 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
2061 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
2062 result by a chain of operations such that all but exactly one of their
2063 operands are constants. */
2065 static gimple
2066 chain_of_csts_start (struct loop *loop, tree x)
2068 gimple stmt = SSA_NAME_DEF_STMT (x);
2069 tree use;
2070 basic_block bb = gimple_bb (stmt);
2071 enum tree_code code;
2073 if (!bb
2074 || !flow_bb_inside_loop_p (loop, bb))
2075 return NULL;
2077 if (gimple_code (stmt) == GIMPLE_PHI)
2079 if (bb == loop->header)
2080 return stmt;
2082 return NULL;
2085 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2086 return NULL;
2088 code = gimple_assign_rhs_code (stmt);
2089 if (gimple_references_memory_p (stmt)
2090 || TREE_CODE_CLASS (code) == tcc_reference
2091 || (code == ADDR_EXPR
2092 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
2093 return NULL;
2095 use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
2096 if (use == NULL_TREE)
2097 return NULL;
2099 return chain_of_csts_start (loop, use);
2102 /* Determines whether the expression X is derived from a result of a phi node
2103 in header of LOOP such that
2105 * the derivation of X consists only from operations with constants
2106 * the initial value of the phi node is constant
2107 * the value of the phi node in the next iteration can be derived from the
2108 value in the current iteration by a chain of operations with constants.
2110 If such phi node exists, it is returned, otherwise NULL is returned. */
2112 static gimple
2113 get_base_for (struct loop *loop, tree x)
2115 gimple phi;
2116 tree init, next;
2118 if (is_gimple_min_invariant (x))
2119 return NULL;
2121 phi = chain_of_csts_start (loop, x);
2122 if (!phi)
2123 return NULL;
2125 init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
2126 next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
2128 if (TREE_CODE (next) != SSA_NAME)
2129 return NULL;
2131 if (!is_gimple_min_invariant (init))
2132 return NULL;
2134 if (chain_of_csts_start (loop, next) != phi)
2135 return NULL;
2137 return phi;
2140 /* Given an expression X, then
2142 * if X is NULL_TREE, we return the constant BASE.
2143 * otherwise X is a SSA name, whose value in the considered loop is derived
2144 by a chain of operations with constant from a result of a phi node in
2145 the header of the loop. Then we return value of X when the value of the
2146 result of this phi node is given by the constant BASE. */
2148 static tree
2149 get_val_for (tree x, tree base)
2151 gimple stmt;
2153 gcc_assert (is_gimple_min_invariant (base));
2155 if (!x)
2156 return base;
2158 stmt = SSA_NAME_DEF_STMT (x);
2159 if (gimple_code (stmt) == GIMPLE_PHI)
2160 return base;
2162 gcc_assert (is_gimple_assign (stmt));
2164 /* STMT must be either an assignment of a single SSA name or an
2165 expression involving an SSA name and a constant. Try to fold that
2166 expression using the value for the SSA name. */
2167 if (gimple_assign_ssa_name_copy_p (stmt))
2168 return get_val_for (gimple_assign_rhs1 (stmt), base);
2169 else if (gimple_assign_rhs_class (stmt) == GIMPLE_UNARY_RHS
2170 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
2172 return fold_build1 (gimple_assign_rhs_code (stmt),
2173 gimple_expr_type (stmt),
2174 get_val_for (gimple_assign_rhs1 (stmt), base));
2176 else if (gimple_assign_rhs_class (stmt) == GIMPLE_BINARY_RHS)
2178 tree rhs1 = gimple_assign_rhs1 (stmt);
2179 tree rhs2 = gimple_assign_rhs2 (stmt);
2180 if (TREE_CODE (rhs1) == SSA_NAME)
2181 rhs1 = get_val_for (rhs1, base);
2182 else if (TREE_CODE (rhs2) == SSA_NAME)
2183 rhs2 = get_val_for (rhs2, base);
2184 else
2185 gcc_unreachable ();
2186 return fold_build2 (gimple_assign_rhs_code (stmt),
2187 gimple_expr_type (stmt), rhs1, rhs2);
2189 else
2190 gcc_unreachable ();
2194 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2195 by brute force -- i.e. by determining the value of the operands of the
2196 condition at EXIT in first few iterations of the loop (assuming that
2197 these values are constant) and determining the first one in that the
2198 condition is not satisfied. Returns the constant giving the number
2199 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
2201 tree
2202 loop_niter_by_eval (struct loop *loop, edge exit)
2204 tree acnd;
2205 tree op[2], val[2], next[2], aval[2];
2206 gimple phi, cond;
2207 unsigned i, j;
2208 enum tree_code cmp;
2210 cond = last_stmt (exit->src);
2211 if (!cond || gimple_code (cond) != GIMPLE_COND)
2212 return chrec_dont_know;
2214 cmp = gimple_cond_code (cond);
2215 if (exit->flags & EDGE_TRUE_VALUE)
2216 cmp = invert_tree_comparison (cmp, false);
2218 switch (cmp)
2220 case EQ_EXPR:
2221 case NE_EXPR:
2222 case GT_EXPR:
2223 case GE_EXPR:
2224 case LT_EXPR:
2225 case LE_EXPR:
2226 op[0] = gimple_cond_lhs (cond);
2227 op[1] = gimple_cond_rhs (cond);
2228 break;
2230 default:
2231 return chrec_dont_know;
2234 for (j = 0; j < 2; j++)
2236 if (is_gimple_min_invariant (op[j]))
2238 val[j] = op[j];
2239 next[j] = NULL_TREE;
2240 op[j] = NULL_TREE;
2242 else
2244 phi = get_base_for (loop, op[j]);
2245 if (!phi)
2246 return chrec_dont_know;
2247 val[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
2248 next[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
2252 /* Don't issue signed overflow warnings. */
2253 fold_defer_overflow_warnings ();
2255 for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
2257 for (j = 0; j < 2; j++)
2258 aval[j] = get_val_for (op[j], val[j]);
2260 acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]);
2261 if (acnd && integer_zerop (acnd))
2263 fold_undefer_and_ignore_overflow_warnings ();
2264 if (dump_file && (dump_flags & TDF_DETAILS))
2265 fprintf (dump_file,
2266 "Proved that loop %d iterates %d times using brute force.\n",
2267 loop->num, i);
2268 return build_int_cst (unsigned_type_node, i);
2271 for (j = 0; j < 2; j++)
2273 val[j] = get_val_for (next[j], val[j]);
2274 if (!is_gimple_min_invariant (val[j]))
2276 fold_undefer_and_ignore_overflow_warnings ();
2277 return chrec_dont_know;
2282 fold_undefer_and_ignore_overflow_warnings ();
2284 return chrec_dont_know;
2287 /* Finds the exit of the LOOP by that the loop exits after a constant
2288 number of iterations and stores the exit edge to *EXIT. The constant
2289 giving the number of iterations of LOOP is returned. The number of
2290 iterations is determined using loop_niter_by_eval (i.e. by brute force
2291 evaluation). If we are unable to find the exit for that loop_niter_by_eval
2292 determines the number of iterations, chrec_dont_know is returned. */
2294 tree
2295 find_loop_niter_by_eval (struct loop *loop, edge *exit)
2297 unsigned i;
2298 vec<edge> exits = get_loop_exit_edges (loop);
2299 edge ex;
2300 tree niter = NULL_TREE, aniter;
2302 *exit = NULL;
2304 /* Loops with multiple exits are expensive to handle and less important. */
2305 if (!flag_expensive_optimizations
2306 && exits.length () > 1)
2308 exits.release ();
2309 return chrec_dont_know;
2312 FOR_EACH_VEC_ELT (exits, i, ex)
2314 if (!just_once_each_iteration_p (loop, ex->src))
2315 continue;
2317 aniter = loop_niter_by_eval (loop, ex);
2318 if (chrec_contains_undetermined (aniter))
2319 continue;
2321 if (niter
2322 && !tree_int_cst_lt (aniter, niter))
2323 continue;
2325 niter = aniter;
2326 *exit = ex;
2328 exits.release ();
2330 return niter ? niter : chrec_dont_know;
2335 Analysis of upper bounds on number of iterations of a loop.
2339 static double_int derive_constant_upper_bound_ops (tree, tree,
2340 enum tree_code, tree);
2342 /* Returns a constant upper bound on the value of the right-hand side of
2343 an assignment statement STMT. */
2345 static double_int
2346 derive_constant_upper_bound_assign (gimple stmt)
2348 enum tree_code code = gimple_assign_rhs_code (stmt);
2349 tree op0 = gimple_assign_rhs1 (stmt);
2350 tree op1 = gimple_assign_rhs2 (stmt);
2352 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt)),
2353 op0, code, op1);
2356 /* Returns a constant upper bound on the value of expression VAL. VAL
2357 is considered to be unsigned. If its type is signed, its value must
2358 be nonnegative. */
2360 static double_int
2361 derive_constant_upper_bound (tree val)
2363 enum tree_code code;
2364 tree op0, op1;
2366 extract_ops_from_tree (val, &code, &op0, &op1);
2367 return derive_constant_upper_bound_ops (TREE_TYPE (val), op0, code, op1);
2370 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
2371 whose type is TYPE. The expression is considered to be unsigned. If
2372 its type is signed, its value must be nonnegative. */
2374 static double_int
2375 derive_constant_upper_bound_ops (tree type, tree op0,
2376 enum tree_code code, tree op1)
2378 tree subtype, maxt;
2379 double_int bnd, max, mmax, cst;
2380 gimple stmt;
2382 if (INTEGRAL_TYPE_P (type))
2383 maxt = TYPE_MAX_VALUE (type);
2384 else
2385 maxt = upper_bound_in_type (type, type);
2387 max = tree_to_double_int (maxt);
2389 switch (code)
2391 case INTEGER_CST:
2392 return tree_to_double_int (op0);
2394 CASE_CONVERT:
2395 subtype = TREE_TYPE (op0);
2396 if (!TYPE_UNSIGNED (subtype)
2397 /* If TYPE is also signed, the fact that VAL is nonnegative implies
2398 that OP0 is nonnegative. */
2399 && TYPE_UNSIGNED (type)
2400 && !tree_expr_nonnegative_p (op0))
2402 /* If we cannot prove that the casted expression is nonnegative,
2403 we cannot establish more useful upper bound than the precision
2404 of the type gives us. */
2405 return max;
2408 /* We now know that op0 is an nonnegative value. Try deriving an upper
2409 bound for it. */
2410 bnd = derive_constant_upper_bound (op0);
2412 /* If the bound does not fit in TYPE, max. value of TYPE could be
2413 attained. */
2414 if (max.ult (bnd))
2415 return max;
2417 return bnd;
2419 case PLUS_EXPR:
2420 case POINTER_PLUS_EXPR:
2421 case MINUS_EXPR:
2422 if (TREE_CODE (op1) != INTEGER_CST
2423 || !tree_expr_nonnegative_p (op0))
2424 return max;
2426 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
2427 choose the most logical way how to treat this constant regardless
2428 of the signedness of the type. */
2429 cst = tree_to_double_int (op1);
2430 cst = cst.sext (TYPE_PRECISION (type));
2431 if (code != MINUS_EXPR)
2432 cst = -cst;
2434 bnd = derive_constant_upper_bound (op0);
2436 if (cst.is_negative ())
2438 cst = -cst;
2439 /* Avoid CST == 0x80000... */
2440 if (cst.is_negative ())
2441 return max;;
2443 /* OP0 + CST. We need to check that
2444 BND <= MAX (type) - CST. */
2446 mmax -= cst;
2447 if (bnd.ugt (mmax))
2448 return max;
2450 return bnd + cst;
2452 else
2454 /* OP0 - CST, where CST >= 0.
2456 If TYPE is signed, we have already verified that OP0 >= 0, and we
2457 know that the result is nonnegative. This implies that
2458 VAL <= BND - CST.
2460 If TYPE is unsigned, we must additionally know that OP0 >= CST,
2461 otherwise the operation underflows.
2464 /* This should only happen if the type is unsigned; however, for
2465 buggy programs that use overflowing signed arithmetics even with
2466 -fno-wrapv, this condition may also be true for signed values. */
2467 if (bnd.ult (cst))
2468 return max;
2470 if (TYPE_UNSIGNED (type))
2472 tree tem = fold_binary (GE_EXPR, boolean_type_node, op0,
2473 double_int_to_tree (type, cst));
2474 if (!tem || integer_nonzerop (tem))
2475 return max;
2478 bnd -= cst;
2481 return bnd;
2483 case FLOOR_DIV_EXPR:
2484 case EXACT_DIV_EXPR:
2485 if (TREE_CODE (op1) != INTEGER_CST
2486 || tree_int_cst_sign_bit (op1))
2487 return max;
2489 bnd = derive_constant_upper_bound (op0);
2490 return bnd.udiv (tree_to_double_int (op1), FLOOR_DIV_EXPR);
2492 case BIT_AND_EXPR:
2493 if (TREE_CODE (op1) != INTEGER_CST
2494 || tree_int_cst_sign_bit (op1))
2495 return max;
2496 return tree_to_double_int (op1);
2498 case SSA_NAME:
2499 stmt = SSA_NAME_DEF_STMT (op0);
2500 if (gimple_code (stmt) != GIMPLE_ASSIGN
2501 || gimple_assign_lhs (stmt) != op0)
2502 return max;
2503 return derive_constant_upper_bound_assign (stmt);
2505 default:
2506 return max;
2510 /* Records that every statement in LOOP is executed I_BOUND times.
2511 REALISTIC is true if I_BOUND is expected to be close to the real number
2512 of iterations. UPPER is true if we are sure the loop iterates at most
2513 I_BOUND times. */
2515 void
2516 record_niter_bound (struct loop *loop, double_int i_bound, bool realistic,
2517 bool upper)
2519 /* Update the bounds only when there is no previous estimation, or when the
2520 current estimation is smaller. */
2521 if (upper
2522 && (!loop->any_upper_bound
2523 || i_bound.ult (loop->nb_iterations_upper_bound)))
2525 loop->any_upper_bound = true;
2526 loop->nb_iterations_upper_bound = i_bound;
2528 if (realistic
2529 && (!loop->any_estimate
2530 || i_bound.ult (loop->nb_iterations_estimate)))
2532 loop->any_estimate = true;
2533 loop->nb_iterations_estimate = i_bound;
2536 /* If an upper bound is smaller than the realistic estimate of the
2537 number of iterations, use the upper bound instead. */
2538 if (loop->any_upper_bound
2539 && loop->any_estimate
2540 && loop->nb_iterations_upper_bound.ult (loop->nb_iterations_estimate))
2541 loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
2544 /* Emit a -Waggressive-loop-optimizations warning if needed. */
2546 static void
2547 do_warn_aggressive_loop_optimizations (struct loop *loop,
2548 double_int i_bound, gimple stmt)
2550 /* Don't warn if the loop doesn't have known constant bound. */
2551 if (!loop->nb_iterations
2552 || TREE_CODE (loop->nb_iterations) != INTEGER_CST
2553 || !warn_aggressive_loop_optimizations
2554 /* To avoid warning multiple times for the same loop,
2555 only start warning when we preserve loops. */
2556 || (cfun->curr_properties & PROP_loops) == 0
2557 /* Only warn once per loop. */
2558 || loop->warned_aggressive_loop_optimizations
2559 /* Only warn if undefined behavior gives us lower estimate than the
2560 known constant bound. */
2561 || i_bound.ucmp (tree_to_double_int (loop->nb_iterations)) >= 0
2562 /* And undefined behavior happens unconditionally. */
2563 || !dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (stmt)))
2564 return;
2566 edge e = single_exit (loop);
2567 if (e == NULL)
2568 return;
2570 gimple estmt = last_stmt (e->src);
2571 if (warning_at (gimple_location (stmt), OPT_Waggressive_loop_optimizations,
2572 "iteration %E invokes undefined behavior",
2573 double_int_to_tree (TREE_TYPE (loop->nb_iterations),
2574 i_bound)))
2575 inform (gimple_location (estmt), "containing loop");
2576 loop->warned_aggressive_loop_optimizations = true;
2579 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
2580 is true if the loop is exited immediately after STMT, and this exit
2581 is taken at last when the STMT is executed BOUND + 1 times.
2582 REALISTIC is true if BOUND is expected to be close to the real number
2583 of iterations. UPPER is true if we are sure the loop iterates at most
2584 BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */
2586 static void
2587 record_estimate (struct loop *loop, tree bound, double_int i_bound,
2588 gimple at_stmt, bool is_exit, bool realistic, bool upper)
2590 double_int delta;
2592 if (dump_file && (dump_flags & TDF_DETAILS))
2594 fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : "");
2595 print_gimple_stmt (dump_file, at_stmt, 0, TDF_SLIM);
2596 fprintf (dump_file, " is %sexecuted at most ",
2597 upper ? "" : "probably ");
2598 print_generic_expr (dump_file, bound, TDF_SLIM);
2599 fprintf (dump_file, " (bounded by ");
2600 dump_double_int (dump_file, i_bound, true);
2601 fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num);
2604 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
2605 real number of iterations. */
2606 if (TREE_CODE (bound) != INTEGER_CST)
2607 realistic = false;
2608 else
2609 gcc_checking_assert (i_bound == tree_to_double_int (bound));
2610 if (!upper && !realistic)
2611 return;
2613 /* If we have a guaranteed upper bound, record it in the appropriate
2614 list, unless this is an !is_exit bound (i.e. undefined behavior in
2615 at_stmt) in a loop with known constant number of iterations. */
2616 if (upper
2617 && (is_exit
2618 || loop->nb_iterations == NULL_TREE
2619 || TREE_CODE (loop->nb_iterations) != INTEGER_CST))
2621 struct nb_iter_bound *elt = ggc_alloc_nb_iter_bound ();
2623 elt->bound = i_bound;
2624 elt->stmt = at_stmt;
2625 elt->is_exit = is_exit;
2626 elt->next = loop->bounds;
2627 loop->bounds = elt;
2630 /* If statement is executed on every path to the loop latch, we can directly
2631 infer the upper bound on the # of iterations of the loop. */
2632 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (at_stmt)))
2633 return;
2635 /* Update the number of iteration estimates according to the bound.
2636 If at_stmt is an exit then the loop latch is executed at most BOUND times,
2637 otherwise it can be executed BOUND + 1 times. We will lower the estimate
2638 later if such statement must be executed on last iteration */
2639 if (is_exit)
2640 delta = double_int_zero;
2641 else
2642 delta = double_int_one;
2643 i_bound += delta;
2645 /* If an overflow occurred, ignore the result. */
2646 if (i_bound.ult (delta))
2647 return;
2649 if (upper && !is_exit)
2650 do_warn_aggressive_loop_optimizations (loop, i_bound, at_stmt);
2651 record_niter_bound (loop, i_bound, realistic, upper);
2654 /* Record the estimate on number of iterations of LOOP based on the fact that
2655 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
2656 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
2657 estimated number of iterations is expected to be close to the real one.
2658 UPPER is true if we are sure the induction variable does not wrap. */
2660 static void
2661 record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple stmt,
2662 tree low, tree high, bool realistic, bool upper)
2664 tree niter_bound, extreme, delta;
2665 tree type = TREE_TYPE (base), unsigned_type;
2666 double_int max;
2668 if (TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
2669 return;
2671 if (dump_file && (dump_flags & TDF_DETAILS))
2673 fprintf (dump_file, "Induction variable (");
2674 print_generic_expr (dump_file, TREE_TYPE (base), TDF_SLIM);
2675 fprintf (dump_file, ") ");
2676 print_generic_expr (dump_file, base, TDF_SLIM);
2677 fprintf (dump_file, " + ");
2678 print_generic_expr (dump_file, step, TDF_SLIM);
2679 fprintf (dump_file, " * iteration does not wrap in statement ");
2680 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2681 fprintf (dump_file, " in loop %d.\n", loop->num);
2684 unsigned_type = unsigned_type_for (type);
2685 base = fold_convert (unsigned_type, base);
2686 step = fold_convert (unsigned_type, step);
2688 if (tree_int_cst_sign_bit (step))
2690 extreme = fold_convert (unsigned_type, low);
2691 if (TREE_CODE (base) != INTEGER_CST)
2692 base = fold_convert (unsigned_type, high);
2693 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
2694 step = fold_build1 (NEGATE_EXPR, unsigned_type, step);
2696 else
2698 extreme = fold_convert (unsigned_type, high);
2699 if (TREE_CODE (base) != INTEGER_CST)
2700 base = fold_convert (unsigned_type, low);
2701 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
2704 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
2705 would get out of the range. */
2706 niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step);
2707 max = derive_constant_upper_bound (niter_bound);
2708 record_estimate (loop, niter_bound, max, stmt, false, realistic, upper);
2711 /* Determine information about number of iterations a LOOP from the index
2712 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
2713 guaranteed to be executed in every iteration of LOOP. Callback for
2714 for_each_index. */
2716 struct ilb_data
2718 struct loop *loop;
2719 gimple stmt;
2722 static bool
2723 idx_infer_loop_bounds (tree base, tree *idx, void *dta)
2725 struct ilb_data *data = (struct ilb_data *) dta;
2726 tree ev, init, step;
2727 tree low, high, type, next;
2728 bool sign, upper = true, at_end = false;
2729 struct loop *loop = data->loop;
2730 bool reliable = true;
2732 if (TREE_CODE (base) != ARRAY_REF)
2733 return true;
2735 /* For arrays at the end of the structure, we are not guaranteed that they
2736 do not really extend over their declared size. However, for arrays of
2737 size greater than one, this is unlikely to be intended. */
2738 if (array_at_struct_end_p (base))
2740 at_end = true;
2741 upper = false;
2744 struct loop *dloop = loop_containing_stmt (data->stmt);
2745 if (!dloop)
2746 return true;
2748 ev = analyze_scalar_evolution (dloop, *idx);
2749 ev = instantiate_parameters (loop, ev);
2750 init = initial_condition (ev);
2751 step = evolution_part_in_loop_num (ev, loop->num);
2753 if (!init
2754 || !step
2755 || TREE_CODE (step) != INTEGER_CST
2756 || integer_zerop (step)
2757 || tree_contains_chrecs (init, NULL)
2758 || chrec_contains_symbols_defined_in_loop (init, loop->num))
2759 return true;
2761 low = array_ref_low_bound (base);
2762 high = array_ref_up_bound (base);
2764 /* The case of nonconstant bounds could be handled, but it would be
2765 complicated. */
2766 if (TREE_CODE (low) != INTEGER_CST
2767 || !high
2768 || TREE_CODE (high) != INTEGER_CST)
2769 return true;
2770 sign = tree_int_cst_sign_bit (step);
2771 type = TREE_TYPE (step);
2773 /* The array of length 1 at the end of a structure most likely extends
2774 beyond its bounds. */
2775 if (at_end
2776 && operand_equal_p (low, high, 0))
2777 return true;
2779 /* In case the relevant bound of the array does not fit in type, or
2780 it does, but bound + step (in type) still belongs into the range of the
2781 array, the index may wrap and still stay within the range of the array
2782 (consider e.g. if the array is indexed by the full range of
2783 unsigned char).
2785 To make things simpler, we require both bounds to fit into type, although
2786 there are cases where this would not be strictly necessary. */
2787 if (!int_fits_type_p (high, type)
2788 || !int_fits_type_p (low, type))
2789 return true;
2790 low = fold_convert (type, low);
2791 high = fold_convert (type, high);
2793 if (sign)
2794 next = fold_binary (PLUS_EXPR, type, low, step);
2795 else
2796 next = fold_binary (PLUS_EXPR, type, high, step);
2798 if (tree_int_cst_compare (low, next) <= 0
2799 && tree_int_cst_compare (next, high) <= 0)
2800 return true;
2802 /* If access is not executed on every iteration, we must ensure that overlow may
2803 not make the access valid later. */
2804 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (data->stmt))
2805 && scev_probably_wraps_p (initial_condition_in_loop_num (ev, loop->num),
2806 step, data->stmt, loop, true))
2807 reliable = false;
2809 record_nonwrapping_iv (loop, init, step, data->stmt, low, high, reliable, upper);
2810 return true;
2813 /* Determine information about number of iterations a LOOP from the bounds
2814 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
2815 STMT is guaranteed to be executed in every iteration of LOOP.*/
2817 static void
2818 infer_loop_bounds_from_ref (struct loop *loop, gimple stmt, tree ref)
2820 struct ilb_data data;
2822 data.loop = loop;
2823 data.stmt = stmt;
2824 for_each_index (&ref, idx_infer_loop_bounds, &data);
2827 /* Determine information about number of iterations of a LOOP from the way
2828 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
2829 executed in every iteration of LOOP. */
2831 static void
2832 infer_loop_bounds_from_array (struct loop *loop, gimple stmt)
2834 if (is_gimple_assign (stmt))
2836 tree op0 = gimple_assign_lhs (stmt);
2837 tree op1 = gimple_assign_rhs1 (stmt);
2839 /* For each memory access, analyze its access function
2840 and record a bound on the loop iteration domain. */
2841 if (REFERENCE_CLASS_P (op0))
2842 infer_loop_bounds_from_ref (loop, stmt, op0);
2844 if (REFERENCE_CLASS_P (op1))
2845 infer_loop_bounds_from_ref (loop, stmt, op1);
2847 else if (is_gimple_call (stmt))
2849 tree arg, lhs;
2850 unsigned i, n = gimple_call_num_args (stmt);
2852 lhs = gimple_call_lhs (stmt);
2853 if (lhs && REFERENCE_CLASS_P (lhs))
2854 infer_loop_bounds_from_ref (loop, stmt, lhs);
2856 for (i = 0; i < n; i++)
2858 arg = gimple_call_arg (stmt, i);
2859 if (REFERENCE_CLASS_P (arg))
2860 infer_loop_bounds_from_ref (loop, stmt, arg);
2865 /* Determine information about number of iterations of a LOOP from the fact
2866 that pointer arithmetics in STMT does not overflow. */
2868 static void
2869 infer_loop_bounds_from_pointer_arith (struct loop *loop, gimple stmt)
2871 tree def, base, step, scev, type, low, high;
2872 tree var, ptr;
2874 if (!is_gimple_assign (stmt)
2875 || gimple_assign_rhs_code (stmt) != POINTER_PLUS_EXPR)
2876 return;
2878 def = gimple_assign_lhs (stmt);
2879 if (TREE_CODE (def) != SSA_NAME)
2880 return;
2882 type = TREE_TYPE (def);
2883 if (!nowrap_type_p (type))
2884 return;
2886 ptr = gimple_assign_rhs1 (stmt);
2887 if (!expr_invariant_in_loop_p (loop, ptr))
2888 return;
2890 var = gimple_assign_rhs2 (stmt);
2891 if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (var)))
2892 return;
2894 scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
2895 if (chrec_contains_undetermined (scev))
2896 return;
2898 base = initial_condition_in_loop_num (scev, loop->num);
2899 step = evolution_part_in_loop_num (scev, loop->num);
2901 if (!base || !step
2902 || TREE_CODE (step) != INTEGER_CST
2903 || tree_contains_chrecs (base, NULL)
2904 || chrec_contains_symbols_defined_in_loop (base, loop->num))
2905 return;
2907 low = lower_bound_in_type (type, type);
2908 high = upper_bound_in_type (type, type);
2910 /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
2911 produce a NULL pointer. The contrary would mean NULL points to an object,
2912 while NULL is supposed to compare unequal with the address of all objects.
2913 Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
2914 NULL pointer since that would mean wrapping, which we assume here not to
2915 happen. So, we can exclude NULL from the valid range of pointer
2916 arithmetic. */
2917 if (flag_delete_null_pointer_checks && int_cst_value (low) == 0)
2918 low = build_int_cstu (TREE_TYPE (low), TYPE_ALIGN_UNIT (TREE_TYPE (type)));
2920 record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
2923 /* Determine information about number of iterations of a LOOP from the fact
2924 that signed arithmetics in STMT does not overflow. */
2926 static void
2927 infer_loop_bounds_from_signedness (struct loop *loop, gimple stmt)
2929 tree def, base, step, scev, type, low, high;
2931 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2932 return;
2934 def = gimple_assign_lhs (stmt);
2936 if (TREE_CODE (def) != SSA_NAME)
2937 return;
2939 type = TREE_TYPE (def);
2940 if (!INTEGRAL_TYPE_P (type)
2941 || !TYPE_OVERFLOW_UNDEFINED (type))
2942 return;
2944 scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
2945 if (chrec_contains_undetermined (scev))
2946 return;
2948 base = initial_condition_in_loop_num (scev, loop->num);
2949 step = evolution_part_in_loop_num (scev, loop->num);
2951 if (!base || !step
2952 || TREE_CODE (step) != INTEGER_CST
2953 || tree_contains_chrecs (base, NULL)
2954 || chrec_contains_symbols_defined_in_loop (base, loop->num))
2955 return;
2957 low = lower_bound_in_type (type, type);
2958 high = upper_bound_in_type (type, type);
2960 record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
2963 /* The following analyzers are extracting informations on the bounds
2964 of LOOP from the following undefined behaviors:
2966 - data references should not access elements over the statically
2967 allocated size,
2969 - signed variables should not overflow when flag_wrapv is not set.
2972 static void
2973 infer_loop_bounds_from_undefined (struct loop *loop)
2975 unsigned i;
2976 basic_block *bbs;
2977 gimple_stmt_iterator bsi;
2978 basic_block bb;
2979 bool reliable;
2981 bbs = get_loop_body (loop);
2983 for (i = 0; i < loop->num_nodes; i++)
2985 bb = bbs[i];
2987 /* If BB is not executed in each iteration of the loop, we cannot
2988 use the operations in it to infer reliable upper bound on the
2989 # of iterations of the loop. However, we can use it as a guess.
2990 Reliable guesses come only from array bounds. */
2991 reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb);
2993 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
2995 gimple stmt = gsi_stmt (bsi);
2997 infer_loop_bounds_from_array (loop, stmt);
2999 if (reliable)
3001 infer_loop_bounds_from_signedness (loop, stmt);
3002 infer_loop_bounds_from_pointer_arith (loop, stmt);
3008 free (bbs);
3011 /* Converts VAL to double_int. */
3013 static double_int
3014 gcov_type_to_double_int (gcov_type val)
3016 double_int ret;
3018 ret.low = (unsigned HOST_WIDE_INT) val;
3019 /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by
3020 the size of type. */
3021 val >>= HOST_BITS_PER_WIDE_INT - 1;
3022 val >>= 1;
3023 ret.high = (unsigned HOST_WIDE_INT) val;
3025 return ret;
3028 /* Compare double ints, callback for qsort. */
3031 double_int_cmp (const void *p1, const void *p2)
3033 const double_int *d1 = (const double_int *)p1;
3034 const double_int *d2 = (const double_int *)p2;
3035 if (*d1 == *d2)
3036 return 0;
3037 if (d1->ult (*d2))
3038 return -1;
3039 return 1;
3042 /* Return index of BOUND in BOUNDS array sorted in increasing order.
3043 Lookup by binary search. */
3046 bound_index (vec<double_int> bounds, double_int bound)
3048 unsigned int end = bounds.length ();
3049 unsigned int begin = 0;
3051 /* Find a matching index by means of a binary search. */
3052 while (begin != end)
3054 unsigned int middle = (begin + end) / 2;
3055 double_int index = bounds[middle];
3057 if (index == bound)
3058 return middle;
3059 else if (index.ult (bound))
3060 begin = middle + 1;
3061 else
3062 end = middle;
3064 gcc_unreachable ();
3067 /* We recorded loop bounds only for statements dominating loop latch (and thus
3068 executed each loop iteration). If there are any bounds on statements not
3069 dominating the loop latch we can improve the estimate by walking the loop
3070 body and seeing if every path from loop header to loop latch contains
3071 some bounded statement. */
3073 static void
3074 discover_iteration_bound_by_body_walk (struct loop *loop)
3076 pointer_map_t *bb_bounds;
3077 struct nb_iter_bound *elt;
3078 vec<double_int> bounds = vNULL;
3079 vec<vec<basic_block> > queues = vNULL;
3080 vec<basic_block> queue = vNULL;
3081 ptrdiff_t queue_index;
3082 ptrdiff_t latch_index = 0;
3083 pointer_map_t *block_priority;
3085 /* Discover what bounds may interest us. */
3086 for (elt = loop->bounds; elt; elt = elt->next)
3088 double_int bound = elt->bound;
3090 /* Exit terminates loop at given iteration, while non-exits produce undefined
3091 effect on the next iteration. */
3092 if (!elt->is_exit)
3094 bound += double_int_one;
3095 /* If an overflow occurred, ignore the result. */
3096 if (bound.is_zero ())
3097 continue;
3100 if (!loop->any_upper_bound
3101 || bound.ult (loop->nb_iterations_upper_bound))
3102 bounds.safe_push (bound);
3105 /* Exit early if there is nothing to do. */
3106 if (!bounds.exists ())
3107 return;
3109 if (dump_file && (dump_flags & TDF_DETAILS))
3110 fprintf (dump_file, " Trying to walk loop body to reduce the bound.\n");
3112 /* Sort the bounds in decreasing order. */
3113 qsort (bounds.address (), bounds.length (),
3114 sizeof (double_int), double_int_cmp);
3116 /* For every basic block record the lowest bound that is guaranteed to
3117 terminate the loop. */
3119 bb_bounds = pointer_map_create ();
3120 for (elt = loop->bounds; elt; elt = elt->next)
3122 double_int bound = elt->bound;
3123 if (!elt->is_exit)
3125 bound += double_int_one;
3126 /* If an overflow occurred, ignore the result. */
3127 if (bound.is_zero ())
3128 continue;
3131 if (!loop->any_upper_bound
3132 || bound.ult (loop->nb_iterations_upper_bound))
3134 ptrdiff_t index = bound_index (bounds, bound);
3135 void **entry = pointer_map_contains (bb_bounds,
3136 gimple_bb (elt->stmt));
3137 if (!entry)
3138 *pointer_map_insert (bb_bounds,
3139 gimple_bb (elt->stmt)) = (void *)index;
3140 else if ((ptrdiff_t)*entry > index)
3141 *entry = (void *)index;
3145 block_priority = pointer_map_create ();
3147 /* Perform shortest path discovery loop->header ... loop->latch.
3149 The "distance" is given by the smallest loop bound of basic block
3150 present in the path and we look for path with largest smallest bound
3151 on it.
3153 To avoid the need for fibonacci heap on double ints we simply compress
3154 double ints into indexes to BOUNDS array and then represent the queue
3155 as arrays of queues for every index.
3156 Index of BOUNDS.length() means that the execution of given BB has
3157 no bounds determined.
3159 VISITED is a pointer map translating basic block into smallest index
3160 it was inserted into the priority queue with. */
3161 latch_index = -1;
3163 /* Start walk in loop header with index set to infinite bound. */
3164 queue_index = bounds.length ();
3165 queues.safe_grow_cleared (queue_index + 1);
3166 queue.safe_push (loop->header);
3167 queues[queue_index] = queue;
3168 *pointer_map_insert (block_priority, loop->header) = (void *)queue_index;
3170 for (; queue_index >= 0; queue_index--)
3172 if (latch_index < queue_index)
3174 while (queues[queue_index].length ())
3176 basic_block bb;
3177 ptrdiff_t bound_index = queue_index;
3178 void **entry;
3179 edge e;
3180 edge_iterator ei;
3182 queue = queues[queue_index];
3183 bb = queue.pop ();
3185 /* OK, we later inserted the BB with lower priority, skip it. */
3186 if ((ptrdiff_t)*pointer_map_contains (block_priority, bb) > queue_index)
3187 continue;
3189 /* See if we can improve the bound. */
3190 entry = pointer_map_contains (bb_bounds, bb);
3191 if (entry && (ptrdiff_t)*entry < bound_index)
3192 bound_index = (ptrdiff_t)*entry;
3194 /* Insert succesors into the queue, watch for latch edge
3195 and record greatest index we saw. */
3196 FOR_EACH_EDGE (e, ei, bb->succs)
3198 bool insert = false;
3199 void **entry;
3201 if (loop_exit_edge_p (loop, e))
3202 continue;
3204 if (e == loop_latch_edge (loop)
3205 && latch_index < bound_index)
3206 latch_index = bound_index;
3207 else if (!(entry = pointer_map_contains (block_priority, e->dest)))
3209 insert = true;
3210 *pointer_map_insert (block_priority, e->dest) = (void *)bound_index;
3212 else if ((ptrdiff_t)*entry < bound_index)
3214 insert = true;
3215 *entry = (void *)bound_index;
3218 if (insert)
3219 queues[bound_index].safe_push (e->dest);
3223 queues[queue_index].release ();
3226 gcc_assert (latch_index >= 0);
3227 if ((unsigned)latch_index < bounds.length ())
3229 if (dump_file && (dump_flags & TDF_DETAILS))
3231 fprintf (dump_file, "Found better loop bound ");
3232 dump_double_int (dump_file, bounds[latch_index], true);
3233 fprintf (dump_file, "\n");
3235 record_niter_bound (loop, bounds[latch_index], false, true);
3238 queues.release ();
3239 bounds.release ();
3240 pointer_map_destroy (bb_bounds);
3241 pointer_map_destroy (block_priority);
3244 /* See if every path cross the loop goes through a statement that is known
3245 to not execute at the last iteration. In that case we can decrese iteration
3246 count by 1. */
3248 static void
3249 maybe_lower_iteration_bound (struct loop *loop)
3251 pointer_set_t *not_executed_last_iteration = NULL;
3252 struct nb_iter_bound *elt;
3253 bool found_exit = false;
3254 vec<basic_block> queue = vNULL;
3255 bitmap visited;
3257 /* Collect all statements with interesting (i.e. lower than
3258 nb_iterations_upper_bound) bound on them.
3260 TODO: Due to the way record_estimate choose estimates to store, the bounds
3261 will be always nb_iterations_upper_bound-1. We can change this to record
3262 also statements not dominating the loop latch and update the walk bellow
3263 to the shortest path algorthm. */
3264 for (elt = loop->bounds; elt; elt = elt->next)
3266 if (!elt->is_exit
3267 && elt->bound.ult (loop->nb_iterations_upper_bound))
3269 if (!not_executed_last_iteration)
3270 not_executed_last_iteration = pointer_set_create ();
3271 pointer_set_insert (not_executed_last_iteration, elt->stmt);
3274 if (!not_executed_last_iteration)
3275 return;
3277 /* Start DFS walk in the loop header and see if we can reach the
3278 loop latch or any of the exits (including statements with side
3279 effects that may terminate the loop otherwise) without visiting
3280 any of the statements known to have undefined effect on the last
3281 iteration. */
3282 queue.safe_push (loop->header);
3283 visited = BITMAP_ALLOC (NULL);
3284 bitmap_set_bit (visited, loop->header->index);
3285 found_exit = false;
3289 basic_block bb = queue.pop ();
3290 gimple_stmt_iterator gsi;
3291 bool stmt_found = false;
3293 /* Loop for possible exits and statements bounding the execution. */
3294 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3296 gimple stmt = gsi_stmt (gsi);
3297 if (pointer_set_contains (not_executed_last_iteration, stmt))
3299 stmt_found = true;
3300 break;
3302 if (gimple_has_side_effects (stmt))
3304 found_exit = true;
3305 break;
3308 if (found_exit)
3309 break;
3311 /* If no bounding statement is found, continue the walk. */
3312 if (!stmt_found)
3314 edge e;
3315 edge_iterator ei;
3317 FOR_EACH_EDGE (e, ei, bb->succs)
3319 if (loop_exit_edge_p (loop, e)
3320 || e == loop_latch_edge (loop))
3322 found_exit = true;
3323 break;
3325 if (bitmap_set_bit (visited, e->dest->index))
3326 queue.safe_push (e->dest);
3330 while (queue.length () && !found_exit);
3332 /* If every path through the loop reach bounding statement before exit,
3333 then we know the last iteration of the loop will have undefined effect
3334 and we can decrease number of iterations. */
3336 if (!found_exit)
3338 if (dump_file && (dump_flags & TDF_DETAILS))
3339 fprintf (dump_file, "Reducing loop iteration estimate by 1; "
3340 "undefined statement must be executed at the last iteration.\n");
3341 record_niter_bound (loop, loop->nb_iterations_upper_bound - double_int_one,
3342 false, true);
3344 BITMAP_FREE (visited);
3345 queue.release ();
3346 pointer_set_destroy (not_executed_last_iteration);
3349 /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
3350 is true also use estimates derived from undefined behavior. */
3352 void
3353 estimate_numbers_of_iterations_loop (struct loop *loop)
3355 vec<edge> exits;
3356 tree niter, type;
3357 unsigned i;
3358 struct tree_niter_desc niter_desc;
3359 edge ex;
3360 double_int bound;
3361 edge likely_exit;
3363 /* Give up if we already have tried to compute an estimation. */
3364 if (loop->estimate_state != EST_NOT_COMPUTED)
3365 return;
3367 loop->estimate_state = EST_AVAILABLE;
3368 /* Force estimate compuation but leave any existing upper bound in place. */
3369 loop->any_estimate = false;
3371 /* Ensure that loop->nb_iterations is computed if possible. If it turns out
3372 to be constant, we avoid undefined behavior implied bounds and instead
3373 diagnose those loops with -Waggressive-loop-optimizations. */
3374 number_of_latch_executions (loop);
3376 exits = get_loop_exit_edges (loop);
3377 likely_exit = single_likely_exit (loop);
3378 FOR_EACH_VEC_ELT (exits, i, ex)
3380 if (!number_of_iterations_exit (loop, ex, &niter_desc, false, false))
3381 continue;
3383 niter = niter_desc.niter;
3384 type = TREE_TYPE (niter);
3385 if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST)
3386 niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
3387 build_int_cst (type, 0),
3388 niter);
3389 record_estimate (loop, niter, niter_desc.max,
3390 last_stmt (ex->src),
3391 true, ex == likely_exit, true);
3393 exits.release ();
3395 if (flag_aggressive_loop_optimizations)
3396 infer_loop_bounds_from_undefined (loop);
3398 discover_iteration_bound_by_body_walk (loop);
3400 maybe_lower_iteration_bound (loop);
3402 /* If we have a measured profile, use it to estimate the number of
3403 iterations. */
3404 if (loop->header->count != 0)
3406 gcov_type nit = expected_loop_iterations_unbounded (loop) + 1;
3407 bound = gcov_type_to_double_int (nit);
3408 record_niter_bound (loop, bound, true, false);
3411 /* If we know the exact number of iterations of this loop, try to
3412 not break code with undefined behavior by not recording smaller
3413 maximum number of iterations. */
3414 if (loop->nb_iterations
3415 && TREE_CODE (loop->nb_iterations) == INTEGER_CST)
3417 loop->any_upper_bound = true;
3418 loop->nb_iterations_upper_bound
3419 = tree_to_double_int (loop->nb_iterations);
3423 /* Sets NIT to the estimated number of executions of the latch of the
3424 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
3425 large as the number of iterations. If we have no reliable estimate,
3426 the function returns false, otherwise returns true. */
3428 bool
3429 estimated_loop_iterations (struct loop *loop, double_int *nit)
3431 /* When SCEV information is available, try to update loop iterations
3432 estimate. Otherwise just return whatever we recorded earlier. */
3433 if (scev_initialized_p ())
3434 estimate_numbers_of_iterations_loop (loop);
3436 /* Even if the bound is not recorded, possibly we can derrive one from
3437 profile. */
3438 if (!loop->any_estimate)
3440 if (loop->header->count)
3442 *nit = gcov_type_to_double_int
3443 (expected_loop_iterations_unbounded (loop) + 1);
3444 return true;
3446 return false;
3449 *nit = loop->nb_iterations_estimate;
3450 return true;
3453 /* Sets NIT to an upper bound for the maximum number of executions of the
3454 latch of the LOOP. If we have no reliable estimate, the function returns
3455 false, otherwise returns true. */
3457 bool
3458 max_loop_iterations (struct loop *loop, double_int *nit)
3460 /* When SCEV information is available, try to update loop iterations
3461 estimate. Otherwise just return whatever we recorded earlier. */
3462 if (scev_initialized_p ())
3463 estimate_numbers_of_iterations_loop (loop);
3464 if (!loop->any_upper_bound)
3465 return false;
3467 *nit = loop->nb_iterations_upper_bound;
3468 return true;
3471 /* Similar to estimated_loop_iterations, but returns the estimate only
3472 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3473 on the number of iterations of LOOP could not be derived, returns -1. */
3475 HOST_WIDE_INT
3476 estimated_loop_iterations_int (struct loop *loop)
3478 double_int nit;
3479 HOST_WIDE_INT hwi_nit;
3481 if (!estimated_loop_iterations (loop, &nit))
3482 return -1;
3484 if (!nit.fits_shwi ())
3485 return -1;
3486 hwi_nit = nit.to_shwi ();
3488 return hwi_nit < 0 ? -1 : hwi_nit;
3491 /* Similar to max_loop_iterations, but returns the estimate only
3492 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3493 on the number of iterations of LOOP could not be derived, returns -1. */
3495 HOST_WIDE_INT
3496 max_loop_iterations_int (struct loop *loop)
3498 double_int nit;
3499 HOST_WIDE_INT hwi_nit;
3501 if (!max_loop_iterations (loop, &nit))
3502 return -1;
3504 if (!nit.fits_shwi ())
3505 return -1;
3506 hwi_nit = nit.to_shwi ();
3508 return hwi_nit < 0 ? -1 : hwi_nit;
3511 /* Returns an upper bound on the number of executions of statements
3512 in the LOOP. For statements before the loop exit, this exceeds
3513 the number of execution of the latch by one. */
3515 HOST_WIDE_INT
3516 max_stmt_executions_int (struct loop *loop)
3518 HOST_WIDE_INT nit = max_loop_iterations_int (loop);
3519 HOST_WIDE_INT snit;
3521 if (nit == -1)
3522 return -1;
3524 snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
3526 /* If the computation overflows, return -1. */
3527 return snit < 0 ? -1 : snit;
3530 /* Returns an estimate for the number of executions of statements
3531 in the LOOP. For statements before the loop exit, this exceeds
3532 the number of execution of the latch by one. */
3534 HOST_WIDE_INT
3535 estimated_stmt_executions_int (struct loop *loop)
3537 HOST_WIDE_INT nit = estimated_loop_iterations_int (loop);
3538 HOST_WIDE_INT snit;
3540 if (nit == -1)
3541 return -1;
3543 snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
3545 /* If the computation overflows, return -1. */
3546 return snit < 0 ? -1 : snit;
3549 /* Sets NIT to the estimated maximum number of executions of the latch of the
3550 LOOP, plus one. If we have no reliable estimate, the function returns
3551 false, otherwise returns true. */
3553 bool
3554 max_stmt_executions (struct loop *loop, double_int *nit)
3556 double_int nit_minus_one;
3558 if (!max_loop_iterations (loop, nit))
3559 return false;
3561 nit_minus_one = *nit;
3563 *nit += double_int_one;
3565 return (*nit).ugt (nit_minus_one);
3568 /* Sets NIT to the estimated number of executions of the latch of the
3569 LOOP, plus one. If we have no reliable estimate, the function returns
3570 false, otherwise returns true. */
3572 bool
3573 estimated_stmt_executions (struct loop *loop, double_int *nit)
3575 double_int nit_minus_one;
3577 if (!estimated_loop_iterations (loop, nit))
3578 return false;
3580 nit_minus_one = *nit;
3582 *nit += double_int_one;
3584 return (*nit).ugt (nit_minus_one);
3587 /* Records estimates on numbers of iterations of loops. */
3589 void
3590 estimate_numbers_of_iterations (void)
3592 loop_iterator li;
3593 struct loop *loop;
3595 /* We don't want to issue signed overflow warnings while getting
3596 loop iteration estimates. */
3597 fold_defer_overflow_warnings ();
3599 FOR_EACH_LOOP (li, loop, 0)
3601 estimate_numbers_of_iterations_loop (loop);
3604 fold_undefer_and_ignore_overflow_warnings ();
3607 /* Returns true if statement S1 dominates statement S2. */
3609 bool
3610 stmt_dominates_stmt_p (gimple s1, gimple s2)
3612 basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
3614 if (!bb1
3615 || s1 == s2)
3616 return true;
3618 if (bb1 == bb2)
3620 gimple_stmt_iterator bsi;
3622 if (gimple_code (s2) == GIMPLE_PHI)
3623 return false;
3625 if (gimple_code (s1) == GIMPLE_PHI)
3626 return true;
3628 for (bsi = gsi_start_bb (bb1); gsi_stmt (bsi) != s2; gsi_next (&bsi))
3629 if (gsi_stmt (bsi) == s1)
3630 return true;
3632 return false;
3635 return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
3638 /* Returns true when we can prove that the number of executions of
3639 STMT in the loop is at most NITER, according to the bound on
3640 the number of executions of the statement NITER_BOUND->stmt recorded in
3641 NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT.
3643 ??? This code can become quite a CPU hog - we can have many bounds,
3644 and large basic block forcing stmt_dominates_stmt_p to be queried
3645 many times on a large basic blocks, so the whole thing is O(n^2)
3646 for scev_probably_wraps_p invocation (that can be done n times).
3648 It would make more sense (and give better answers) to remember BB
3649 bounds computed by discover_iteration_bound_by_body_walk. */
3651 static bool
3652 n_of_executions_at_most (gimple stmt,
3653 struct nb_iter_bound *niter_bound,
3654 tree niter)
3656 double_int bound = niter_bound->bound;
3657 tree nit_type = TREE_TYPE (niter), e;
3658 enum tree_code cmp;
3660 gcc_assert (TYPE_UNSIGNED (nit_type));
3662 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
3663 the number of iterations is small. */
3664 if (!double_int_fits_to_tree_p (nit_type, bound))
3665 return false;
3667 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3668 times. This means that:
3670 -- if NITER_BOUND->is_exit is true, then everything after
3671 it at most NITER_BOUND->bound times.
3673 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
3674 is executed, then NITER_BOUND->stmt is executed as well in the same
3675 iteration then STMT is executed at most NITER_BOUND->bound + 1 times.
3677 If we can determine that NITER_BOUND->stmt is always executed
3678 after STMT, then STMT is executed at most NITER_BOUND->bound + 2 times.
3679 We conclude that if both statements belong to the same
3680 basic block and STMT is before NITER_BOUND->stmt and there are no
3681 statements with side effects in between. */
3683 if (niter_bound->is_exit)
3685 if (stmt == niter_bound->stmt
3686 || !stmt_dominates_stmt_p (niter_bound->stmt, stmt))
3687 return false;
3688 cmp = GE_EXPR;
3690 else
3692 if (!stmt_dominates_stmt_p (niter_bound->stmt, stmt))
3694 gimple_stmt_iterator bsi;
3695 if (gimple_bb (stmt) != gimple_bb (niter_bound->stmt)
3696 || gimple_code (stmt) == GIMPLE_PHI
3697 || gimple_code (niter_bound->stmt) == GIMPLE_PHI)
3698 return false;
3700 /* By stmt_dominates_stmt_p we already know that STMT appears
3701 before NITER_BOUND->STMT. Still need to test that the loop
3702 can not be terinated by a side effect in between. */
3703 for (bsi = gsi_for_stmt (stmt); gsi_stmt (bsi) != niter_bound->stmt;
3704 gsi_next (&bsi))
3705 if (gimple_has_side_effects (gsi_stmt (bsi)))
3706 return false;
3707 bound += double_int_one;
3708 if (bound.is_zero ()
3709 || !double_int_fits_to_tree_p (nit_type, bound))
3710 return false;
3712 cmp = GT_EXPR;
3715 e = fold_binary (cmp, boolean_type_node,
3716 niter, double_int_to_tree (nit_type, bound));
3717 return e && integer_nonzerop (e);
3720 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
3722 bool
3723 nowrap_type_p (tree type)
3725 if (INTEGRAL_TYPE_P (type)
3726 && TYPE_OVERFLOW_UNDEFINED (type))
3727 return true;
3729 if (POINTER_TYPE_P (type))
3730 return true;
3732 return false;
3735 /* Return false only when the induction variable BASE + STEP * I is
3736 known to not overflow: i.e. when the number of iterations is small
3737 enough with respect to the step and initial condition in order to
3738 keep the evolution confined in TYPEs bounds. Return true when the
3739 iv is known to overflow or when the property is not computable.
3741 USE_OVERFLOW_SEMANTICS is true if this function should assume that
3742 the rules for overflow of the given language apply (e.g., that signed
3743 arithmetics in C does not overflow). */
3745 bool
3746 scev_probably_wraps_p (tree base, tree step,
3747 gimple at_stmt, struct loop *loop,
3748 bool use_overflow_semantics)
3750 tree delta, step_abs;
3751 tree unsigned_type, valid_niter;
3752 tree type = TREE_TYPE (step);
3753 tree e;
3754 double_int niter;
3755 struct nb_iter_bound *bound;
3757 /* FIXME: We really need something like
3758 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
3760 We used to test for the following situation that frequently appears
3761 during address arithmetics:
3763 D.1621_13 = (long unsigned intD.4) D.1620_12;
3764 D.1622_14 = D.1621_13 * 8;
3765 D.1623_15 = (doubleD.29 *) D.1622_14;
3767 And derived that the sequence corresponding to D_14
3768 can be proved to not wrap because it is used for computing a
3769 memory access; however, this is not really the case -- for example,
3770 if D_12 = (unsigned char) [254,+,1], then D_14 has values
3771 2032, 2040, 0, 8, ..., but the code is still legal. */
3773 if (chrec_contains_undetermined (base)
3774 || chrec_contains_undetermined (step))
3775 return true;
3777 if (integer_zerop (step))
3778 return false;
3780 /* If we can use the fact that signed and pointer arithmetics does not
3781 wrap, we are done. */
3782 if (use_overflow_semantics && nowrap_type_p (TREE_TYPE (base)))
3783 return false;
3785 /* To be able to use estimates on number of iterations of the loop,
3786 we must have an upper bound on the absolute value of the step. */
3787 if (TREE_CODE (step) != INTEGER_CST)
3788 return true;
3790 /* Don't issue signed overflow warnings. */
3791 fold_defer_overflow_warnings ();
3793 /* Otherwise, compute the number of iterations before we reach the
3794 bound of the type, and verify that the loop is exited before this
3795 occurs. */
3796 unsigned_type = unsigned_type_for (type);
3797 base = fold_convert (unsigned_type, base);
3799 if (tree_int_cst_sign_bit (step))
3801 tree extreme = fold_convert (unsigned_type,
3802 lower_bound_in_type (type, type));
3803 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
3804 step_abs = fold_build1 (NEGATE_EXPR, unsigned_type,
3805 fold_convert (unsigned_type, step));
3807 else
3809 tree extreme = fold_convert (unsigned_type,
3810 upper_bound_in_type (type, type));
3811 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
3812 step_abs = fold_convert (unsigned_type, step);
3815 valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
3817 estimate_numbers_of_iterations_loop (loop);
3819 if (max_loop_iterations (loop, &niter)
3820 && double_int_fits_to_tree_p (TREE_TYPE (valid_niter), niter)
3821 && (e = fold_binary (GT_EXPR, boolean_type_node, valid_niter,
3822 double_int_to_tree (TREE_TYPE (valid_niter),
3823 niter))) != NULL
3824 && integer_nonzerop (e))
3826 fold_undefer_and_ignore_overflow_warnings ();
3827 return false;
3829 if (at_stmt)
3830 for (bound = loop->bounds; bound; bound = bound->next)
3832 if (n_of_executions_at_most (at_stmt, bound, valid_niter))
3834 fold_undefer_and_ignore_overflow_warnings ();
3835 return false;
3839 fold_undefer_and_ignore_overflow_warnings ();
3841 /* At this point we still don't have a proof that the iv does not
3842 overflow: give up. */
3843 return true;
3846 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
3848 void
3849 free_numbers_of_iterations_estimates_loop (struct loop *loop)
3851 struct nb_iter_bound *bound, *next;
3853 loop->nb_iterations = NULL;
3854 loop->estimate_state = EST_NOT_COMPUTED;
3855 for (bound = loop->bounds; bound; bound = next)
3857 next = bound->next;
3858 ggc_free (bound);
3861 loop->bounds = NULL;
3864 /* Frees the information on upper bounds on numbers of iterations of loops. */
3866 void
3867 free_numbers_of_iterations_estimates (void)
3869 loop_iterator li;
3870 struct loop *loop;
3872 FOR_EACH_LOOP (li, loop, 0)
3874 free_numbers_of_iterations_estimates_loop (loop);
3878 /* Substitute value VAL for ssa name NAME inside expressions held
3879 at LOOP. */
3881 void
3882 substitute_in_loop_info (struct loop *loop, tree name, tree val)
3884 loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);