tree-ssa-loop-niter.c (estimate_numbers_of_iterations_loop): Do not predict loops...
[gcc.git] / gcc / tree-ssa-loop-niter.c
1 /* Functions to determine/estimate number of iterations of a loop.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
3 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
10 later version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "tm_p.h"
27 #include "basic-block.h"
28 #include "gimple-pretty-print.h"
29 #include "intl.h"
30 #include "tree-flow.h"
31 #include "dumpfile.h"
32 #include "cfgloop.h"
33 #include "ggc.h"
34 #include "tree-chrec.h"
35 #include "tree-scalar-evolution.h"
36 #include "tree-data-ref.h"
37 #include "params.h"
38 #include "flags.h"
39 #include "diagnostic-core.h"
40 #include "tree-inline.h"
41 #include "gmp.h"
42
43 #define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
44
45 /* The maximum number of dominator BBs we search for conditions
46 of loop header copies we use for simplifying a conditional
47 expression. */
48 #define MAX_DOMINATORS_TO_WALK 8
49
50 /*
51
52 Analysis of number of iterations of an affine exit test.
53
54 */
55
56 /* Bounds on some value, BELOW <= X <= UP. */
57
58 typedef struct
59 {
60 mpz_t below, up;
61 } bounds;
62
63
64 /* Splits expression EXPR to a variable part VAR and constant OFFSET. */
65
66 static void
67 split_to_var_and_offset (tree expr, tree *var, mpz_t offset)
68 {
69 tree type = TREE_TYPE (expr);
70 tree op0, op1;
71 double_int off;
72 bool negate = false;
73
74 *var = expr;
75 mpz_set_ui (offset, 0);
76
77 switch (TREE_CODE (expr))
78 {
79 case MINUS_EXPR:
80 negate = true;
81 /* Fallthru. */
82
83 case PLUS_EXPR:
84 case POINTER_PLUS_EXPR:
85 op0 = TREE_OPERAND (expr, 0);
86 op1 = TREE_OPERAND (expr, 1);
87
88 if (TREE_CODE (op1) != INTEGER_CST)
89 break;
90
91 *var = op0;
92 /* Always sign extend the offset. */
93 off = tree_to_double_int (op1);
94 off = off.sext (TYPE_PRECISION (type));
95 mpz_set_double_int (offset, off, false);
96 if (negate)
97 mpz_neg (offset, offset);
98 break;
99
100 case INTEGER_CST:
101 *var = build_int_cst_type (type, 0);
102 off = tree_to_double_int (expr);
103 mpz_set_double_int (offset, off, TYPE_UNSIGNED (type));
104 break;
105
106 default:
107 break;
108 }
109 }
110
111 /* Stores estimate on the minimum/maximum value of the expression VAR + OFF
112 in TYPE to MIN and MAX. */
113
114 static void
115 determine_value_range (tree type, tree var, mpz_t off,
116 mpz_t min, mpz_t max)
117 {
118 /* If the expression is a constant, we know its value exactly. */
119 if (integer_zerop (var))
120 {
121 mpz_set (min, off);
122 mpz_set (max, off);
123 return;
124 }
125
126 /* If the computation may wrap, we know nothing about the value, except for
127 the range of the type. */
128 get_type_static_bounds (type, min, max);
129 if (!nowrap_type_p (type))
130 return;
131
132 /* Since the addition of OFF does not wrap, if OFF is positive, then we may
133 add it to MIN, otherwise to MAX. */
134 if (mpz_sgn (off) < 0)
135 mpz_add (max, max, off);
136 else
137 mpz_add (min, min, off);
138 }
139
140 /* Stores the bounds on the difference of the values of the expressions
141 (var + X) and (var + Y), computed in TYPE, to BNDS. */
142
143 static void
144 bound_difference_of_offsetted_base (tree type, mpz_t x, mpz_t y,
145 bounds *bnds)
146 {
147 int rel = mpz_cmp (x, y);
148 bool may_wrap = !nowrap_type_p (type);
149 mpz_t m;
150
151 /* If X == Y, then the expressions are always equal.
152 If X > Y, there are the following possibilities:
153 a) neither of var + X and var + Y overflow or underflow, or both of
154 them do. Then their difference is X - Y.
155 b) var + X overflows, and var + Y does not. Then the values of the
156 expressions are var + X - M and var + Y, where M is the range of
157 the type, and their difference is X - Y - M.
158 c) var + Y underflows and var + X does not. Their difference again
159 is M - X + Y.
160 Therefore, if the arithmetics in type does not overflow, then the
161 bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y)
162 Similarly, if X < Y, the bounds are either (X - Y, X - Y) or
163 (X - Y, X - Y + M). */
164
165 if (rel == 0)
166 {
167 mpz_set_ui (bnds->below, 0);
168 mpz_set_ui (bnds->up, 0);
169 return;
170 }
171
172 mpz_init (m);
173 mpz_set_double_int (m, double_int::mask (TYPE_PRECISION (type)), true);
174 mpz_add_ui (m, m, 1);
175 mpz_sub (bnds->up, x, y);
176 mpz_set (bnds->below, bnds->up);
177
178 if (may_wrap)
179 {
180 if (rel > 0)
181 mpz_sub (bnds->below, bnds->below, m);
182 else
183 mpz_add (bnds->up, bnds->up, m);
184 }
185
186 mpz_clear (m);
187 }
188
189 /* From condition C0 CMP C1 derives information regarding the
190 difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE,
191 and stores it to BNDS. */
192
193 static void
194 refine_bounds_using_guard (tree type, tree varx, mpz_t offx,
195 tree vary, mpz_t offy,
196 tree c0, enum tree_code cmp, tree c1,
197 bounds *bnds)
198 {
199 tree varc0, varc1, tmp, ctype;
200 mpz_t offc0, offc1, loffx, loffy, bnd;
201 bool lbound = false;
202 bool no_wrap = nowrap_type_p (type);
203 bool x_ok, y_ok;
204
205 switch (cmp)
206 {
207 case LT_EXPR:
208 case LE_EXPR:
209 case GT_EXPR:
210 case GE_EXPR:
211 STRIP_SIGN_NOPS (c0);
212 STRIP_SIGN_NOPS (c1);
213 ctype = TREE_TYPE (c0);
214 if (!useless_type_conversion_p (ctype, type))
215 return;
216
217 break;
218
219 case EQ_EXPR:
220 /* We could derive quite precise information from EQ_EXPR, however, such
221 a guard is unlikely to appear, so we do not bother with handling
222 it. */
223 return;
224
225 case NE_EXPR:
226 /* NE_EXPR comparisons do not contain much of useful information, except for
227 special case of comparing with the bounds of the type. */
228 if (TREE_CODE (c1) != INTEGER_CST
229 || !INTEGRAL_TYPE_P (type))
230 return;
231
232 /* Ensure that the condition speaks about an expression in the same type
233 as X and Y. */
234 ctype = TREE_TYPE (c0);
235 if (TYPE_PRECISION (ctype) != TYPE_PRECISION (type))
236 return;
237 c0 = fold_convert (type, c0);
238 c1 = fold_convert (type, c1);
239
240 if (TYPE_MIN_VALUE (type)
241 && operand_equal_p (c1, TYPE_MIN_VALUE (type), 0))
242 {
243 cmp = GT_EXPR;
244 break;
245 }
246 if (TYPE_MAX_VALUE (type)
247 && operand_equal_p (c1, TYPE_MAX_VALUE (type), 0))
248 {
249 cmp = LT_EXPR;
250 break;
251 }
252
253 return;
254 default:
255 return;
256 }
257
258 mpz_init (offc0);
259 mpz_init (offc1);
260 split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0);
261 split_to_var_and_offset (expand_simple_operations (c1), &varc1, offc1);
262
263 /* We are only interested in comparisons of expressions based on VARX and
264 VARY. TODO -- we might also be able to derive some bounds from
265 expressions containing just one of the variables. */
266
267 if (operand_equal_p (varx, varc1, 0))
268 {
269 tmp = varc0; varc0 = varc1; varc1 = tmp;
270 mpz_swap (offc0, offc1);
271 cmp = swap_tree_comparison (cmp);
272 }
273
274 if (!operand_equal_p (varx, varc0, 0)
275 || !operand_equal_p (vary, varc1, 0))
276 goto end;
277
278 mpz_init_set (loffx, offx);
279 mpz_init_set (loffy, offy);
280
281 if (cmp == GT_EXPR || cmp == GE_EXPR)
282 {
283 tmp = varx; varx = vary; vary = tmp;
284 mpz_swap (offc0, offc1);
285 mpz_swap (loffx, loffy);
286 cmp = swap_tree_comparison (cmp);
287 lbound = true;
288 }
289
290 /* If there is no overflow, the condition implies that
291
292 (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0).
293
294 The overflows and underflows may complicate things a bit; each
295 overflow decreases the appropriate offset by M, and underflow
296 increases it by M. The above inequality would not necessarily be
297 true if
298
299 -- VARX + OFFX underflows and VARX + OFFC0 does not, or
300 VARX + OFFC0 overflows, but VARX + OFFX does not.
301 This may only happen if OFFX < OFFC0.
302 -- VARY + OFFY overflows and VARY + OFFC1 does not, or
303 VARY + OFFC1 underflows and VARY + OFFY does not.
304 This may only happen if OFFY > OFFC1. */
305
306 if (no_wrap)
307 {
308 x_ok = true;
309 y_ok = true;
310 }
311 else
312 {
313 x_ok = (integer_zerop (varx)
314 || mpz_cmp (loffx, offc0) >= 0);
315 y_ok = (integer_zerop (vary)
316 || mpz_cmp (loffy, offc1) <= 0);
317 }
318
319 if (x_ok && y_ok)
320 {
321 mpz_init (bnd);
322 mpz_sub (bnd, loffx, loffy);
323 mpz_add (bnd, bnd, offc1);
324 mpz_sub (bnd, bnd, offc0);
325
326 if (cmp == LT_EXPR)
327 mpz_sub_ui (bnd, bnd, 1);
328
329 if (lbound)
330 {
331 mpz_neg (bnd, bnd);
332 if (mpz_cmp (bnds->below, bnd) < 0)
333 mpz_set (bnds->below, bnd);
334 }
335 else
336 {
337 if (mpz_cmp (bnd, bnds->up) < 0)
338 mpz_set (bnds->up, bnd);
339 }
340 mpz_clear (bnd);
341 }
342
343 mpz_clear (loffx);
344 mpz_clear (loffy);
345 end:
346 mpz_clear (offc0);
347 mpz_clear (offc1);
348 }
349
350 /* Stores the bounds on the value of the expression X - Y in LOOP to BNDS.
351 The subtraction is considered to be performed in arbitrary precision,
352 without overflows.
353
354 We do not attempt to be too clever regarding the value ranges of X and
355 Y; most of the time, they are just integers or ssa names offsetted by
356 integer. However, we try to use the information contained in the
357 comparisons before the loop (usually created by loop header copying). */
358
359 static void
360 bound_difference (struct loop *loop, tree x, tree y, bounds *bnds)
361 {
362 tree type = TREE_TYPE (x);
363 tree varx, vary;
364 mpz_t offx, offy;
365 mpz_t minx, maxx, miny, maxy;
366 int cnt = 0;
367 edge e;
368 basic_block bb;
369 tree c0, c1;
370 gimple cond;
371 enum tree_code cmp;
372
373 /* Get rid of unnecessary casts, but preserve the value of
374 the expressions. */
375 STRIP_SIGN_NOPS (x);
376 STRIP_SIGN_NOPS (y);
377
378 mpz_init (bnds->below);
379 mpz_init (bnds->up);
380 mpz_init (offx);
381 mpz_init (offy);
382 split_to_var_and_offset (x, &varx, offx);
383 split_to_var_and_offset (y, &vary, offy);
384
385 if (!integer_zerop (varx)
386 && operand_equal_p (varx, vary, 0))
387 {
388 /* Special case VARX == VARY -- we just need to compare the
389 offsets. The matters are a bit more complicated in the
390 case addition of offsets may wrap. */
391 bound_difference_of_offsetted_base (type, offx, offy, bnds);
392 }
393 else
394 {
395 /* Otherwise, use the value ranges to determine the initial
396 estimates on below and up. */
397 mpz_init (minx);
398 mpz_init (maxx);
399 mpz_init (miny);
400 mpz_init (maxy);
401 determine_value_range (type, varx, offx, minx, maxx);
402 determine_value_range (type, vary, offy, miny, maxy);
403
404 mpz_sub (bnds->below, minx, maxy);
405 mpz_sub (bnds->up, maxx, miny);
406 mpz_clear (minx);
407 mpz_clear (maxx);
408 mpz_clear (miny);
409 mpz_clear (maxy);
410 }
411
412 /* If both X and Y are constants, we cannot get any more precise. */
413 if (integer_zerop (varx) && integer_zerop (vary))
414 goto end;
415
416 /* Now walk the dominators of the loop header and use the entry
417 guards to refine the estimates. */
418 for (bb = loop->header;
419 bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK;
420 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
421 {
422 if (!single_pred_p (bb))
423 continue;
424 e = single_pred_edge (bb);
425
426 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
427 continue;
428
429 cond = last_stmt (e->src);
430 c0 = gimple_cond_lhs (cond);
431 cmp = gimple_cond_code (cond);
432 c1 = gimple_cond_rhs (cond);
433
434 if (e->flags & EDGE_FALSE_VALUE)
435 cmp = invert_tree_comparison (cmp, false);
436
437 refine_bounds_using_guard (type, varx, offx, vary, offy,
438 c0, cmp, c1, bnds);
439 ++cnt;
440 }
441
442 end:
443 mpz_clear (offx);
444 mpz_clear (offy);
445 }
446
447 /* Update the bounds in BNDS that restrict the value of X to the bounds
448 that restrict the value of X + DELTA. X can be obtained as a
449 difference of two values in TYPE. */
450
451 static void
452 bounds_add (bounds *bnds, double_int delta, tree type)
453 {
454 mpz_t mdelta, max;
455
456 mpz_init (mdelta);
457 mpz_set_double_int (mdelta, delta, false);
458
459 mpz_init (max);
460 mpz_set_double_int (max, double_int::mask (TYPE_PRECISION (type)), true);
461
462 mpz_add (bnds->up, bnds->up, mdelta);
463 mpz_add (bnds->below, bnds->below, mdelta);
464
465 if (mpz_cmp (bnds->up, max) > 0)
466 mpz_set (bnds->up, max);
467
468 mpz_neg (max, max);
469 if (mpz_cmp (bnds->below, max) < 0)
470 mpz_set (bnds->below, max);
471
472 mpz_clear (mdelta);
473 mpz_clear (max);
474 }
475
476 /* Update the bounds in BNDS that restrict the value of X to the bounds
477 that restrict the value of -X. */
478
479 static void
480 bounds_negate (bounds *bnds)
481 {
482 mpz_t tmp;
483
484 mpz_init_set (tmp, bnds->up);
485 mpz_neg (bnds->up, bnds->below);
486 mpz_neg (bnds->below, tmp);
487 mpz_clear (tmp);
488 }
489
490 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
491
492 static tree
493 inverse (tree x, tree mask)
494 {
495 tree type = TREE_TYPE (x);
496 tree rslt;
497 unsigned ctr = tree_floor_log2 (mask);
498
499 if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT)
500 {
501 unsigned HOST_WIDE_INT ix;
502 unsigned HOST_WIDE_INT imask;
503 unsigned HOST_WIDE_INT irslt = 1;
504
505 gcc_assert (cst_and_fits_in_hwi (x));
506 gcc_assert (cst_and_fits_in_hwi (mask));
507
508 ix = int_cst_value (x);
509 imask = int_cst_value (mask);
510
511 for (; ctr; ctr--)
512 {
513 irslt *= ix;
514 ix *= ix;
515 }
516 irslt &= imask;
517
518 rslt = build_int_cst_type (type, irslt);
519 }
520 else
521 {
522 rslt = build_int_cst (type, 1);
523 for (; ctr; ctr--)
524 {
525 rslt = int_const_binop (MULT_EXPR, rslt, x);
526 x = int_const_binop (MULT_EXPR, x, x);
527 }
528 rslt = int_const_binop (BIT_AND_EXPR, rslt, mask);
529 }
530
531 return rslt;
532 }
533
534 /* Derives the upper bound BND on the number of executions of loop with exit
535 condition S * i <> C. If NO_OVERFLOW is true, then the control variable of
536 the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed
537 that the loop ends through this exit, i.e., the induction variable ever
538 reaches the value of C.
539
540 The value C is equal to final - base, where final and base are the final and
541 initial value of the actual induction variable in the analysed loop. BNDS
542 bounds the value of this difference when computed in signed type with
543 unbounded range, while the computation of C is performed in an unsigned
544 type with the range matching the range of the type of the induction variable.
545 In particular, BNDS.up contains an upper bound on C in the following cases:
546 -- if the iv must reach its final value without overflow, i.e., if
547 NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or
548 -- if final >= base, which we know to hold when BNDS.below >= 0. */
549
550 static void
551 number_of_iterations_ne_max (mpz_t bnd, bool no_overflow, tree c, tree s,
552 bounds *bnds, bool exit_must_be_taken)
553 {
554 double_int max;
555 mpz_t d;
556 bool bnds_u_valid = ((no_overflow && exit_must_be_taken)
557 || mpz_sgn (bnds->below) >= 0);
558
559 if (multiple_of_p (TREE_TYPE (c), c, s))
560 {
561 /* If C is an exact multiple of S, then its value will be reached before
562 the induction variable overflows (unless the loop is exited in some
563 other way before). Note that the actual induction variable in the
564 loop (which ranges from base to final instead of from 0 to C) may
565 overflow, in which case BNDS.up will not be giving a correct upper
566 bound on C; thus, BNDS_U_VALID had to be computed in advance. */
567 no_overflow = true;
568 exit_must_be_taken = true;
569 }
570
571 /* If the induction variable can overflow, the number of iterations is at
572 most the period of the control variable (or infinite, but in that case
573 the whole # of iterations analysis will fail). */
574 if (!no_overflow)
575 {
576 max = double_int::mask (TYPE_PRECISION (TREE_TYPE (c))
577 - tree_low_cst (num_ending_zeros (s), 1));
578 mpz_set_double_int (bnd, max, true);
579 return;
580 }
581
582 /* Now we know that the induction variable does not overflow, so the loop
583 iterates at most (range of type / S) times. */
584 mpz_set_double_int (bnd, double_int::mask (TYPE_PRECISION (TREE_TYPE (c))),
585 true);
586
587 /* If the induction variable is guaranteed to reach the value of C before
588 overflow, ... */
589 if (exit_must_be_taken)
590 {
591 /* ... then we can strengthen this to C / S, and possibly we can use
592 the upper bound on C given by BNDS. */
593 if (TREE_CODE (c) == INTEGER_CST)
594 mpz_set_double_int (bnd, tree_to_double_int (c), true);
595 else if (bnds_u_valid)
596 mpz_set (bnd, bnds->up);
597 }
598
599 mpz_init (d);
600 mpz_set_double_int (d, tree_to_double_int (s), true);
601 mpz_fdiv_q (bnd, bnd, d);
602 mpz_clear (d);
603 }
604
605 /* Determines number of iterations of loop whose ending condition
606 is IV <> FINAL. TYPE is the type of the iv. The number of
607 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
608 we know that the exit must be taken eventually, i.e., that the IV
609 ever reaches the value FINAL (we derived this earlier, and possibly set
610 NITER->assumptions to make sure this is the case). BNDS contains the
611 bounds on the difference FINAL - IV->base. */
612
613 static bool
614 number_of_iterations_ne (tree type, affine_iv *iv, tree final,
615 struct tree_niter_desc *niter, bool exit_must_be_taken,
616 bounds *bnds)
617 {
618 tree niter_type = unsigned_type_for (type);
619 tree s, c, d, bits, assumption, tmp, bound;
620 mpz_t max;
621
622 niter->control = *iv;
623 niter->bound = final;
624 niter->cmp = NE_EXPR;
625
626 /* Rearrange the terms so that we get inequality S * i <> C, with S
627 positive. Also cast everything to the unsigned type. If IV does
628 not overflow, BNDS bounds the value of C. Also, this is the
629 case if the computation |FINAL - IV->base| does not overflow, i.e.,
630 if BNDS->below in the result is nonnegative. */
631 if (tree_int_cst_sign_bit (iv->step))
632 {
633 s = fold_convert (niter_type,
634 fold_build1 (NEGATE_EXPR, type, iv->step));
635 c = fold_build2 (MINUS_EXPR, niter_type,
636 fold_convert (niter_type, iv->base),
637 fold_convert (niter_type, final));
638 bounds_negate (bnds);
639 }
640 else
641 {
642 s = fold_convert (niter_type, iv->step);
643 c = fold_build2 (MINUS_EXPR, niter_type,
644 fold_convert (niter_type, final),
645 fold_convert (niter_type, iv->base));
646 }
647
648 mpz_init (max);
649 number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds,
650 exit_must_be_taken);
651 niter->max = mpz_get_double_int (niter_type, max, false);
652 mpz_clear (max);
653
654 /* First the trivial cases -- when the step is 1. */
655 if (integer_onep (s))
656 {
657 niter->niter = c;
658 return true;
659 }
660
661 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
662 is infinite. Otherwise, the number of iterations is
663 (inverse(s/d) * (c/d)) mod (size of mode/d). */
664 bits = num_ending_zeros (s);
665 bound = build_low_bits_mask (niter_type,
666 (TYPE_PRECISION (niter_type)
667 - tree_low_cst (bits, 1)));
668
669 d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
670 build_int_cst (niter_type, 1), bits);
671 s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
672
673 if (!exit_must_be_taken)
674 {
675 /* If we cannot assume that the exit is taken eventually, record the
676 assumptions for divisibility of c. */
677 assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d);
678 assumption = fold_build2 (EQ_EXPR, boolean_type_node,
679 assumption, build_int_cst (niter_type, 0));
680 if (!integer_nonzerop (assumption))
681 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
682 niter->assumptions, assumption);
683 }
684
685 c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d);
686 tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound));
687 niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound);
688 return true;
689 }
690
691 /* Checks whether we can determine the final value of the control variable
692 of the loop with ending condition IV0 < IV1 (computed in TYPE).
693 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
694 of the step. The assumptions necessary to ensure that the computation
695 of the final value does not overflow are recorded in NITER. If we
696 find the final value, we adjust DELTA and return TRUE. Otherwise
697 we return false. BNDS bounds the value of IV1->base - IV0->base,
698 and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
699 true if we know that the exit must be taken eventually. */
700
701 static bool
702 number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1,
703 struct tree_niter_desc *niter,
704 tree *delta, tree step,
705 bool exit_must_be_taken, bounds *bnds)
706 {
707 tree niter_type = TREE_TYPE (step);
708 tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step);
709 tree tmod;
710 mpz_t mmod;
711 tree assumption = boolean_true_node, bound, noloop;
712 bool ret = false, fv_comp_no_overflow;
713 tree type1 = type;
714 if (POINTER_TYPE_P (type))
715 type1 = sizetype;
716
717 if (TREE_CODE (mod) != INTEGER_CST)
718 return false;
719 if (integer_nonzerop (mod))
720 mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
721 tmod = fold_convert (type1, mod);
722
723 mpz_init (mmod);
724 mpz_set_double_int (mmod, tree_to_double_int (mod), true);
725 mpz_neg (mmod, mmod);
726
727 /* If the induction variable does not overflow and the exit is taken,
728 then the computation of the final value does not overflow. This is
729 also obviously the case if the new final value is equal to the
730 current one. Finally, we postulate this for pointer type variables,
731 as the code cannot rely on the object to that the pointer points being
732 placed at the end of the address space (and more pragmatically,
733 TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
734 if (integer_zerop (mod) || POINTER_TYPE_P (type))
735 fv_comp_no_overflow = true;
736 else if (!exit_must_be_taken)
737 fv_comp_no_overflow = false;
738 else
739 fv_comp_no_overflow =
740 (iv0->no_overflow && integer_nonzerop (iv0->step))
741 || (iv1->no_overflow && integer_nonzerop (iv1->step));
742
743 if (integer_nonzerop (iv0->step))
744 {
745 /* The final value of the iv is iv1->base + MOD, assuming that this
746 computation does not overflow, and that
747 iv0->base <= iv1->base + MOD. */
748 if (!fv_comp_no_overflow)
749 {
750 bound = fold_build2 (MINUS_EXPR, type1,
751 TYPE_MAX_VALUE (type1), tmod);
752 assumption = fold_build2 (LE_EXPR, boolean_type_node,
753 iv1->base, bound);
754 if (integer_zerop (assumption))
755 goto end;
756 }
757 if (mpz_cmp (mmod, bnds->below) < 0)
758 noloop = boolean_false_node;
759 else if (POINTER_TYPE_P (type))
760 noloop = fold_build2 (GT_EXPR, boolean_type_node,
761 iv0->base,
762 fold_build_pointer_plus (iv1->base, tmod));
763 else
764 noloop = fold_build2 (GT_EXPR, boolean_type_node,
765 iv0->base,
766 fold_build2 (PLUS_EXPR, type1,
767 iv1->base, tmod));
768 }
769 else
770 {
771 /* The final value of the iv is iv0->base - MOD, assuming that this
772 computation does not overflow, and that
773 iv0->base - MOD <= iv1->base. */
774 if (!fv_comp_no_overflow)
775 {
776 bound = fold_build2 (PLUS_EXPR, type1,
777 TYPE_MIN_VALUE (type1), tmod);
778 assumption = fold_build2 (GE_EXPR, boolean_type_node,
779 iv0->base, bound);
780 if (integer_zerop (assumption))
781 goto end;
782 }
783 if (mpz_cmp (mmod, bnds->below) < 0)
784 noloop = boolean_false_node;
785 else if (POINTER_TYPE_P (type))
786 noloop = fold_build2 (GT_EXPR, boolean_type_node,
787 fold_build_pointer_plus (iv0->base,
788 fold_build1 (NEGATE_EXPR,
789 type1, tmod)),
790 iv1->base);
791 else
792 noloop = fold_build2 (GT_EXPR, boolean_type_node,
793 fold_build2 (MINUS_EXPR, type1,
794 iv0->base, tmod),
795 iv1->base);
796 }
797
798 if (!integer_nonzerop (assumption))
799 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
800 niter->assumptions,
801 assumption);
802 if (!integer_zerop (noloop))
803 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
804 niter->may_be_zero,
805 noloop);
806 bounds_add (bnds, tree_to_double_int (mod), type);
807 *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod);
808
809 ret = true;
810 end:
811 mpz_clear (mmod);
812 return ret;
813 }
814
815 /* Add assertions to NITER that ensure that the control variable of the loop
816 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
817 are TYPE. Returns false if we can prove that there is an overflow, true
818 otherwise. STEP is the absolute value of the step. */
819
820 static bool
821 assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
822 struct tree_niter_desc *niter, tree step)
823 {
824 tree bound, d, assumption, diff;
825 tree niter_type = TREE_TYPE (step);
826
827 if (integer_nonzerop (iv0->step))
828 {
829 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
830 if (iv0->no_overflow)
831 return true;
832
833 /* If iv0->base is a constant, we can determine the last value before
834 overflow precisely; otherwise we conservatively assume
835 MAX - STEP + 1. */
836
837 if (TREE_CODE (iv0->base) == INTEGER_CST)
838 {
839 d = fold_build2 (MINUS_EXPR, niter_type,
840 fold_convert (niter_type, TYPE_MAX_VALUE (type)),
841 fold_convert (niter_type, iv0->base));
842 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
843 }
844 else
845 diff = fold_build2 (MINUS_EXPR, niter_type, step,
846 build_int_cst (niter_type, 1));
847 bound = fold_build2 (MINUS_EXPR, type,
848 TYPE_MAX_VALUE (type), fold_convert (type, diff));
849 assumption = fold_build2 (LE_EXPR, boolean_type_node,
850 iv1->base, bound);
851 }
852 else
853 {
854 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
855 if (iv1->no_overflow)
856 return true;
857
858 if (TREE_CODE (iv1->base) == INTEGER_CST)
859 {
860 d = fold_build2 (MINUS_EXPR, niter_type,
861 fold_convert (niter_type, iv1->base),
862 fold_convert (niter_type, TYPE_MIN_VALUE (type)));
863 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
864 }
865 else
866 diff = fold_build2 (MINUS_EXPR, niter_type, step,
867 build_int_cst (niter_type, 1));
868 bound = fold_build2 (PLUS_EXPR, type,
869 TYPE_MIN_VALUE (type), fold_convert (type, diff));
870 assumption = fold_build2 (GE_EXPR, boolean_type_node,
871 iv0->base, bound);
872 }
873
874 if (integer_zerop (assumption))
875 return false;
876 if (!integer_nonzerop (assumption))
877 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
878 niter->assumptions, assumption);
879
880 iv0->no_overflow = true;
881 iv1->no_overflow = true;
882 return true;
883 }
884
885 /* Add an assumption to NITER that a loop whose ending condition
886 is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS
887 bounds the value of IV1->base - IV0->base. */
888
889 static void
890 assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
891 struct tree_niter_desc *niter, bounds *bnds)
892 {
893 tree assumption = boolean_true_node, bound, diff;
894 tree mbz, mbzl, mbzr, type1;
895 bool rolls_p, no_overflow_p;
896 double_int dstep;
897 mpz_t mstep, max;
898
899 /* We are going to compute the number of iterations as
900 (iv1->base - iv0->base + step - 1) / step, computed in the unsigned
901 variant of TYPE. This formula only works if
902
903 -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1
904
905 (where MAX is the maximum value of the unsigned variant of TYPE, and
906 the computations in this formula are performed in full precision,
907 i.e., without overflows).
908
909 Usually, for loops with exit condition iv0->base + step * i < iv1->base,
910 we have a condition of the form iv0->base - step < iv1->base before the loop,
911 and for loops iv0->base < iv1->base - step * i the condition
912 iv0->base < iv1->base + step, due to loop header copying, which enable us
913 to prove the lower bound.
914
915 The upper bound is more complicated. Unless the expressions for initial
916 and final value themselves contain enough information, we usually cannot
917 derive it from the context. */
918
919 /* First check whether the answer does not follow from the bounds we gathered
920 before. */
921 if (integer_nonzerop (iv0->step))
922 dstep = tree_to_double_int (iv0->step);
923 else
924 {
925 dstep = tree_to_double_int (iv1->step).sext (TYPE_PRECISION (type));
926 dstep = -dstep;
927 }
928
929 mpz_init (mstep);
930 mpz_set_double_int (mstep, dstep, true);
931 mpz_neg (mstep, mstep);
932 mpz_add_ui (mstep, mstep, 1);
933
934 rolls_p = mpz_cmp (mstep, bnds->below) <= 0;
935
936 mpz_init (max);
937 mpz_set_double_int (max, double_int::mask (TYPE_PRECISION (type)), true);
938 mpz_add (max, max, mstep);
939 no_overflow_p = (mpz_cmp (bnds->up, max) <= 0
940 /* For pointers, only values lying inside a single object
941 can be compared or manipulated by pointer arithmetics.
942 Gcc in general does not allow or handle objects larger
943 than half of the address space, hence the upper bound
944 is satisfied for pointers. */
945 || POINTER_TYPE_P (type));
946 mpz_clear (mstep);
947 mpz_clear (max);
948
949 if (rolls_p && no_overflow_p)
950 return;
951
952 type1 = type;
953 if (POINTER_TYPE_P (type))
954 type1 = sizetype;
955
956 /* Now the hard part; we must formulate the assumption(s) as expressions, and
957 we must be careful not to introduce overflow. */
958
959 if (integer_nonzerop (iv0->step))
960 {
961 diff = fold_build2 (MINUS_EXPR, type1,
962 iv0->step, build_int_cst (type1, 1));
963
964 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
965 0 address never belongs to any object, we can assume this for
966 pointers. */
967 if (!POINTER_TYPE_P (type))
968 {
969 bound = fold_build2 (PLUS_EXPR, type1,
970 TYPE_MIN_VALUE (type), diff);
971 assumption = fold_build2 (GE_EXPR, boolean_type_node,
972 iv0->base, bound);
973 }
974
975 /* And then we can compute iv0->base - diff, and compare it with
976 iv1->base. */
977 mbzl = fold_build2 (MINUS_EXPR, type1,
978 fold_convert (type1, iv0->base), diff);
979 mbzr = fold_convert (type1, iv1->base);
980 }
981 else
982 {
983 diff = fold_build2 (PLUS_EXPR, type1,
984 iv1->step, build_int_cst (type1, 1));
985
986 if (!POINTER_TYPE_P (type))
987 {
988 bound = fold_build2 (PLUS_EXPR, type1,
989 TYPE_MAX_VALUE (type), diff);
990 assumption = fold_build2 (LE_EXPR, boolean_type_node,
991 iv1->base, bound);
992 }
993
994 mbzl = fold_convert (type1, iv0->base);
995 mbzr = fold_build2 (MINUS_EXPR, type1,
996 fold_convert (type1, iv1->base), diff);
997 }
998
999 if (!integer_nonzerop (assumption))
1000 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1001 niter->assumptions, assumption);
1002 if (!rolls_p)
1003 {
1004 mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr);
1005 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
1006 niter->may_be_zero, mbz);
1007 }
1008 }
1009
1010 /* Determines number of iterations of loop whose ending condition
1011 is IV0 < IV1. TYPE is the type of the iv. The number of
1012 iterations is stored to NITER. BNDS bounds the difference
1013 IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
1014 that the exit must be taken eventually. */
1015
1016 static bool
1017 number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
1018 struct tree_niter_desc *niter,
1019 bool exit_must_be_taken, bounds *bnds)
1020 {
1021 tree niter_type = unsigned_type_for (type);
1022 tree delta, step, s;
1023 mpz_t mstep, tmp;
1024
1025 if (integer_nonzerop (iv0->step))
1026 {
1027 niter->control = *iv0;
1028 niter->cmp = LT_EXPR;
1029 niter->bound = iv1->base;
1030 }
1031 else
1032 {
1033 niter->control = *iv1;
1034 niter->cmp = GT_EXPR;
1035 niter->bound = iv0->base;
1036 }
1037
1038 delta = fold_build2 (MINUS_EXPR, niter_type,
1039 fold_convert (niter_type, iv1->base),
1040 fold_convert (niter_type, iv0->base));
1041
1042 /* First handle the special case that the step is +-1. */
1043 if ((integer_onep (iv0->step) && integer_zerop (iv1->step))
1044 || (integer_all_onesp (iv1->step) && integer_zerop (iv0->step)))
1045 {
1046 /* for (i = iv0->base; i < iv1->base; i++)
1047
1048 or
1049
1050 for (i = iv1->base; i > iv0->base; i--).
1051
1052 In both cases # of iterations is iv1->base - iv0->base, assuming that
1053 iv1->base >= iv0->base.
1054
1055 First try to derive a lower bound on the value of
1056 iv1->base - iv0->base, computed in full precision. If the difference
1057 is nonnegative, we are done, otherwise we must record the
1058 condition. */
1059
1060 if (mpz_sgn (bnds->below) < 0)
1061 niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
1062 iv1->base, iv0->base);
1063 niter->niter = delta;
1064 niter->max = mpz_get_double_int (niter_type, bnds->up, false);
1065 return true;
1066 }
1067
1068 if (integer_nonzerop (iv0->step))
1069 step = fold_convert (niter_type, iv0->step);
1070 else
1071 step = fold_convert (niter_type,
1072 fold_build1 (NEGATE_EXPR, type, iv1->step));
1073
1074 /* If we can determine the final value of the control iv exactly, we can
1075 transform the condition to != comparison. In particular, this will be
1076 the case if DELTA is constant. */
1077 if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step,
1078 exit_must_be_taken, bnds))
1079 {
1080 affine_iv zps;
1081
1082 zps.base = build_int_cst (niter_type, 0);
1083 zps.step = step;
1084 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
1085 zps does not overflow. */
1086 zps.no_overflow = true;
1087
1088 return number_of_iterations_ne (type, &zps, delta, niter, true, bnds);
1089 }
1090
1091 /* Make sure that the control iv does not overflow. */
1092 if (!assert_no_overflow_lt (type, iv0, iv1, niter, step))
1093 return false;
1094
1095 /* We determine the number of iterations as (delta + step - 1) / step. For
1096 this to work, we must know that iv1->base >= iv0->base - step + 1,
1097 otherwise the loop does not roll. */
1098 assert_loop_rolls_lt (type, iv0, iv1, niter, bnds);
1099
1100 s = fold_build2 (MINUS_EXPR, niter_type,
1101 step, build_int_cst (niter_type, 1));
1102 delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
1103 niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
1104
1105 mpz_init (mstep);
1106 mpz_init (tmp);
1107 mpz_set_double_int (mstep, tree_to_double_int (step), true);
1108 mpz_add (tmp, bnds->up, mstep);
1109 mpz_sub_ui (tmp, tmp, 1);
1110 mpz_fdiv_q (tmp, tmp, mstep);
1111 niter->max = mpz_get_double_int (niter_type, tmp, false);
1112 mpz_clear (mstep);
1113 mpz_clear (tmp);
1114
1115 return true;
1116 }
1117
1118 /* Determines number of iterations of loop whose ending condition
1119 is IV0 <= IV1. TYPE is the type of the iv. The number of
1120 iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
1121 we know that this condition must eventually become false (we derived this
1122 earlier, and possibly set NITER->assumptions to make sure this
1123 is the case). BNDS bounds the difference IV1->base - IV0->base. */
1124
1125 static bool
1126 number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1,
1127 struct tree_niter_desc *niter, bool exit_must_be_taken,
1128 bounds *bnds)
1129 {
1130 tree assumption;
1131 tree type1 = type;
1132 if (POINTER_TYPE_P (type))
1133 type1 = sizetype;
1134
1135 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
1136 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
1137 value of the type. This we must know anyway, since if it is
1138 equal to this value, the loop rolls forever. We do not check
1139 this condition for pointer type ivs, as the code cannot rely on
1140 the object to that the pointer points being placed at the end of
1141 the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is
1142 not defined for pointers). */
1143
1144 if (!exit_must_be_taken && !POINTER_TYPE_P (type))
1145 {
1146 if (integer_nonzerop (iv0->step))
1147 assumption = fold_build2 (NE_EXPR, boolean_type_node,
1148 iv1->base, TYPE_MAX_VALUE (type));
1149 else
1150 assumption = fold_build2 (NE_EXPR, boolean_type_node,
1151 iv0->base, TYPE_MIN_VALUE (type));
1152
1153 if (integer_zerop (assumption))
1154 return false;
1155 if (!integer_nonzerop (assumption))
1156 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1157 niter->assumptions, assumption);
1158 }
1159
1160 if (integer_nonzerop (iv0->step))
1161 {
1162 if (POINTER_TYPE_P (type))
1163 iv1->base = fold_build_pointer_plus_hwi (iv1->base, 1);
1164 else
1165 iv1->base = fold_build2 (PLUS_EXPR, type1, iv1->base,
1166 build_int_cst (type1, 1));
1167 }
1168 else if (POINTER_TYPE_P (type))
1169 iv0->base = fold_build_pointer_plus_hwi (iv0->base, -1);
1170 else
1171 iv0->base = fold_build2 (MINUS_EXPR, type1,
1172 iv0->base, build_int_cst (type1, 1));
1173
1174 bounds_add (bnds, double_int_one, type1);
1175
1176 return number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken,
1177 bnds);
1178 }
1179
1180 /* Dumps description of affine induction variable IV to FILE. */
1181
1182 static void
1183 dump_affine_iv (FILE *file, affine_iv *iv)
1184 {
1185 if (!integer_zerop (iv->step))
1186 fprintf (file, "[");
1187
1188 print_generic_expr (dump_file, iv->base, TDF_SLIM);
1189
1190 if (!integer_zerop (iv->step))
1191 {
1192 fprintf (file, ", + , ");
1193 print_generic_expr (dump_file, iv->step, TDF_SLIM);
1194 fprintf (file, "]%s", iv->no_overflow ? "(no_overflow)" : "");
1195 }
1196 }
1197
1198 /* Determine the number of iterations according to condition (for staying
1199 inside loop) which compares two induction variables using comparison
1200 operator CODE. The induction variable on left side of the comparison
1201 is IV0, the right-hand side is IV1. Both induction variables must have
1202 type TYPE, which must be an integer or pointer type. The steps of the
1203 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
1204
1205 LOOP is the loop whose number of iterations we are determining.
1206
1207 ONLY_EXIT is true if we are sure this is the only way the loop could be
1208 exited (including possibly non-returning function calls, exceptions, etc.)
1209 -- in this case we can use the information whether the control induction
1210 variables can overflow or not in a more efficient way.
1211
1212 The results (number of iterations and assumptions as described in
1213 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
1214 Returns false if it fails to determine number of iterations, true if it
1215 was determined (possibly with some assumptions). */
1216
1217 static bool
1218 number_of_iterations_cond (struct loop *loop,
1219 tree type, affine_iv *iv0, enum tree_code code,
1220 affine_iv *iv1, struct tree_niter_desc *niter,
1221 bool only_exit)
1222 {
1223 bool exit_must_be_taken = false, ret;
1224 bounds bnds;
1225
1226 /* The meaning of these assumptions is this:
1227 if !assumptions
1228 then the rest of information does not have to be valid
1229 if may_be_zero then the loop does not roll, even if
1230 niter != 0. */
1231 niter->assumptions = boolean_true_node;
1232 niter->may_be_zero = boolean_false_node;
1233 niter->niter = NULL_TREE;
1234 niter->max = double_int_zero;
1235
1236 niter->bound = NULL_TREE;
1237 niter->cmp = ERROR_MARK;
1238
1239 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
1240 the control variable is on lhs. */
1241 if (code == GE_EXPR || code == GT_EXPR
1242 || (code == NE_EXPR && integer_zerop (iv0->step)))
1243 {
1244 SWAP (iv0, iv1);
1245 code = swap_tree_comparison (code);
1246 }
1247
1248 if (POINTER_TYPE_P (type))
1249 {
1250 /* Comparison of pointers is undefined unless both iv0 and iv1 point
1251 to the same object. If they do, the control variable cannot wrap
1252 (as wrap around the bounds of memory will never return a pointer
1253 that would be guaranteed to point to the same object, even if we
1254 avoid undefined behavior by casting to size_t and back). */
1255 iv0->no_overflow = true;
1256 iv1->no_overflow = true;
1257 }
1258
1259 /* If the control induction variable does not overflow and the only exit
1260 from the loop is the one that we analyze, we know it must be taken
1261 eventually. */
1262 if (only_exit)
1263 {
1264 if (!integer_zerop (iv0->step) && iv0->no_overflow)
1265 exit_must_be_taken = true;
1266 else if (!integer_zerop (iv1->step) && iv1->no_overflow)
1267 exit_must_be_taken = true;
1268 }
1269
1270 /* We can handle the case when neither of the sides of the comparison is
1271 invariant, provided that the test is NE_EXPR. This rarely occurs in
1272 practice, but it is simple enough to manage. */
1273 if (!integer_zerop (iv0->step) && !integer_zerop (iv1->step))
1274 {
1275 tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
1276 if (code != NE_EXPR)
1277 return false;
1278
1279 iv0->step = fold_binary_to_constant (MINUS_EXPR, step_type,
1280 iv0->step, iv1->step);
1281 iv0->no_overflow = false;
1282 iv1->step = build_int_cst (step_type, 0);
1283 iv1->no_overflow = true;
1284 }
1285
1286 /* If the result of the comparison is a constant, the loop is weird. More
1287 precise handling would be possible, but the situation is not common enough
1288 to waste time on it. */
1289 if (integer_zerop (iv0->step) && integer_zerop (iv1->step))
1290 return false;
1291
1292 /* Ignore loops of while (i-- < 10) type. */
1293 if (code != NE_EXPR)
1294 {
1295 if (iv0->step && tree_int_cst_sign_bit (iv0->step))
1296 return false;
1297
1298 if (!integer_zerop (iv1->step) && !tree_int_cst_sign_bit (iv1->step))
1299 return false;
1300 }
1301
1302 /* If the loop exits immediately, there is nothing to do. */
1303 if (integer_zerop (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
1304 {
1305 niter->niter = build_int_cst (unsigned_type_for (type), 0);
1306 niter->max = double_int_zero;
1307 return true;
1308 }
1309
1310 /* OK, now we know we have a senseful loop. Handle several cases, depending
1311 on what comparison operator is used. */
1312 bound_difference (loop, iv1->base, iv0->base, &bnds);
1313
1314 if (dump_file && (dump_flags & TDF_DETAILS))
1315 {
1316 fprintf (dump_file,
1317 "Analyzing # of iterations of loop %d\n", loop->num);
1318
1319 fprintf (dump_file, " exit condition ");
1320 dump_affine_iv (dump_file, iv0);
1321 fprintf (dump_file, " %s ",
1322 code == NE_EXPR ? "!="
1323 : code == LT_EXPR ? "<"
1324 : "<=");
1325 dump_affine_iv (dump_file, iv1);
1326 fprintf (dump_file, "\n");
1327
1328 fprintf (dump_file, " bounds on difference of bases: ");
1329 mpz_out_str (dump_file, 10, bnds.below);
1330 fprintf (dump_file, " ... ");
1331 mpz_out_str (dump_file, 10, bnds.up);
1332 fprintf (dump_file, "\n");
1333 }
1334
1335 switch (code)
1336 {
1337 case NE_EXPR:
1338 gcc_assert (integer_zerop (iv1->step));
1339 ret = number_of_iterations_ne (type, iv0, iv1->base, niter,
1340 exit_must_be_taken, &bnds);
1341 break;
1342
1343 case LT_EXPR:
1344 ret = number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken,
1345 &bnds);
1346 break;
1347
1348 case LE_EXPR:
1349 ret = number_of_iterations_le (type, iv0, iv1, niter, exit_must_be_taken,
1350 &bnds);
1351 break;
1352
1353 default:
1354 gcc_unreachable ();
1355 }
1356
1357 mpz_clear (bnds.up);
1358 mpz_clear (bnds.below);
1359
1360 if (dump_file && (dump_flags & TDF_DETAILS))
1361 {
1362 if (ret)
1363 {
1364 fprintf (dump_file, " result:\n");
1365 if (!integer_nonzerop (niter->assumptions))
1366 {
1367 fprintf (dump_file, " under assumptions ");
1368 print_generic_expr (dump_file, niter->assumptions, TDF_SLIM);
1369 fprintf (dump_file, "\n");
1370 }
1371
1372 if (!integer_zerop (niter->may_be_zero))
1373 {
1374 fprintf (dump_file, " zero if ");
1375 print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
1376 fprintf (dump_file, "\n");
1377 }
1378
1379 fprintf (dump_file, " # of iterations ");
1380 print_generic_expr (dump_file, niter->niter, TDF_SLIM);
1381 fprintf (dump_file, ", bounded by ");
1382 dump_double_int (dump_file, niter->max, true);
1383 fprintf (dump_file, "\n");
1384 }
1385 else
1386 fprintf (dump_file, " failed\n\n");
1387 }
1388 return ret;
1389 }
1390
1391 /* Substitute NEW for OLD in EXPR and fold the result. */
1392
1393 static tree
1394 simplify_replace_tree (tree expr, tree old, tree new_tree)
1395 {
1396 unsigned i, n;
1397 tree ret = NULL_TREE, e, se;
1398
1399 if (!expr)
1400 return NULL_TREE;
1401
1402 /* Do not bother to replace constants. */
1403 if (CONSTANT_CLASS_P (old))
1404 return expr;
1405
1406 if (expr == old
1407 || operand_equal_p (expr, old, 0))
1408 return unshare_expr (new_tree);
1409
1410 if (!EXPR_P (expr))
1411 return expr;
1412
1413 n = TREE_OPERAND_LENGTH (expr);
1414 for (i = 0; i < n; i++)
1415 {
1416 e = TREE_OPERAND (expr, i);
1417 se = simplify_replace_tree (e, old, new_tree);
1418 if (e == se)
1419 continue;
1420
1421 if (!ret)
1422 ret = copy_node (expr);
1423
1424 TREE_OPERAND (ret, i) = se;
1425 }
1426
1427 return (ret ? fold (ret) : expr);
1428 }
1429
1430 /* Expand definitions of ssa names in EXPR as long as they are simple
1431 enough, and return the new expression. */
1432
1433 tree
1434 expand_simple_operations (tree expr)
1435 {
1436 unsigned i, n;
1437 tree ret = NULL_TREE, e, ee, e1;
1438 enum tree_code code;
1439 gimple stmt;
1440
1441 if (expr == NULL_TREE)
1442 return expr;
1443
1444 if (is_gimple_min_invariant (expr))
1445 return expr;
1446
1447 code = TREE_CODE (expr);
1448 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
1449 {
1450 n = TREE_OPERAND_LENGTH (expr);
1451 for (i = 0; i < n; i++)
1452 {
1453 e = TREE_OPERAND (expr, i);
1454 ee = expand_simple_operations (e);
1455 if (e == ee)
1456 continue;
1457
1458 if (!ret)
1459 ret = copy_node (expr);
1460
1461 TREE_OPERAND (ret, i) = ee;
1462 }
1463
1464 if (!ret)
1465 return expr;
1466
1467 fold_defer_overflow_warnings ();
1468 ret = fold (ret);
1469 fold_undefer_and_ignore_overflow_warnings ();
1470 return ret;
1471 }
1472
1473 if (TREE_CODE (expr) != SSA_NAME)
1474 return expr;
1475
1476 stmt = SSA_NAME_DEF_STMT (expr);
1477 if (gimple_code (stmt) == GIMPLE_PHI)
1478 {
1479 basic_block src, dest;
1480
1481 if (gimple_phi_num_args (stmt) != 1)
1482 return expr;
1483 e = PHI_ARG_DEF (stmt, 0);
1484
1485 /* Avoid propagating through loop exit phi nodes, which
1486 could break loop-closed SSA form restrictions. */
1487 dest = gimple_bb (stmt);
1488 src = single_pred (dest);
1489 if (TREE_CODE (e) == SSA_NAME
1490 && src->loop_father != dest->loop_father)
1491 return expr;
1492
1493 return expand_simple_operations (e);
1494 }
1495 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1496 return expr;
1497
1498 e = gimple_assign_rhs1 (stmt);
1499 code = gimple_assign_rhs_code (stmt);
1500 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1501 {
1502 if (is_gimple_min_invariant (e))
1503 return e;
1504
1505 if (code == SSA_NAME)
1506 return expand_simple_operations (e);
1507
1508 return expr;
1509 }
1510
1511 switch (code)
1512 {
1513 CASE_CONVERT:
1514 /* Casts are simple. */
1515 ee = expand_simple_operations (e);
1516 return fold_build1 (code, TREE_TYPE (expr), ee);
1517
1518 case PLUS_EXPR:
1519 case MINUS_EXPR:
1520 case POINTER_PLUS_EXPR:
1521 /* And increments and decrements by a constant are simple. */
1522 e1 = gimple_assign_rhs2 (stmt);
1523 if (!is_gimple_min_invariant (e1))
1524 return expr;
1525
1526 ee = expand_simple_operations (e);
1527 return fold_build2 (code, TREE_TYPE (expr), ee, e1);
1528
1529 default:
1530 return expr;
1531 }
1532 }
1533
1534 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1535 expression (or EXPR unchanged, if no simplification was possible). */
1536
1537 static tree
1538 tree_simplify_using_condition_1 (tree cond, tree expr)
1539 {
1540 bool changed;
1541 tree e, te, e0, e1, e2, notcond;
1542 enum tree_code code = TREE_CODE (expr);
1543
1544 if (code == INTEGER_CST)
1545 return expr;
1546
1547 if (code == TRUTH_OR_EXPR
1548 || code == TRUTH_AND_EXPR
1549 || code == COND_EXPR)
1550 {
1551 changed = false;
1552
1553 e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0));
1554 if (TREE_OPERAND (expr, 0) != e0)
1555 changed = true;
1556
1557 e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1));
1558 if (TREE_OPERAND (expr, 1) != e1)
1559 changed = true;
1560
1561 if (code == COND_EXPR)
1562 {
1563 e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2));
1564 if (TREE_OPERAND (expr, 2) != e2)
1565 changed = true;
1566 }
1567 else
1568 e2 = NULL_TREE;
1569
1570 if (changed)
1571 {
1572 if (code == COND_EXPR)
1573 expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
1574 else
1575 expr = fold_build2 (code, boolean_type_node, e0, e1);
1576 }
1577
1578 return expr;
1579 }
1580
1581 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
1582 propagation, and vice versa. Fold does not handle this, since it is
1583 considered too expensive. */
1584 if (TREE_CODE (cond) == EQ_EXPR)
1585 {
1586 e0 = TREE_OPERAND (cond, 0);
1587 e1 = TREE_OPERAND (cond, 1);
1588
1589 /* We know that e0 == e1. Check whether we cannot simplify expr
1590 using this fact. */
1591 e = simplify_replace_tree (expr, e0, e1);
1592 if (integer_zerop (e) || integer_nonzerop (e))
1593 return e;
1594
1595 e = simplify_replace_tree (expr, e1, e0);
1596 if (integer_zerop (e) || integer_nonzerop (e))
1597 return e;
1598 }
1599 if (TREE_CODE (expr) == EQ_EXPR)
1600 {
1601 e0 = TREE_OPERAND (expr, 0);
1602 e1 = TREE_OPERAND (expr, 1);
1603
1604 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
1605 e = simplify_replace_tree (cond, e0, e1);
1606 if (integer_zerop (e))
1607 return e;
1608 e = simplify_replace_tree (cond, e1, e0);
1609 if (integer_zerop (e))
1610 return e;
1611 }
1612 if (TREE_CODE (expr) == NE_EXPR)
1613 {
1614 e0 = TREE_OPERAND (expr, 0);
1615 e1 = TREE_OPERAND (expr, 1);
1616
1617 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
1618 e = simplify_replace_tree (cond, e0, e1);
1619 if (integer_zerop (e))
1620 return boolean_true_node;
1621 e = simplify_replace_tree (cond, e1, e0);
1622 if (integer_zerop (e))
1623 return boolean_true_node;
1624 }
1625
1626 te = expand_simple_operations (expr);
1627
1628 /* Check whether COND ==> EXPR. */
1629 notcond = invert_truthvalue (cond);
1630 e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te);
1631 if (e && integer_nonzerop (e))
1632 return e;
1633
1634 /* Check whether COND ==> not EXPR. */
1635 e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te);
1636 if (e && integer_zerop (e))
1637 return e;
1638
1639 return expr;
1640 }
1641
1642 /* Tries to simplify EXPR using the condition COND. Returns the simplified
1643 expression (or EXPR unchanged, if no simplification was possible).
1644 Wrapper around tree_simplify_using_condition_1 that ensures that chains
1645 of simple operations in definitions of ssa names in COND are expanded,
1646 so that things like casts or incrementing the value of the bound before
1647 the loop do not cause us to fail. */
1648
1649 static tree
1650 tree_simplify_using_condition (tree cond, tree expr)
1651 {
1652 cond = expand_simple_operations (cond);
1653
1654 return tree_simplify_using_condition_1 (cond, expr);
1655 }
1656
1657 /* Tries to simplify EXPR using the conditions on entry to LOOP.
1658 Returns the simplified expression (or EXPR unchanged, if no
1659 simplification was possible).*/
1660
1661 static tree
1662 simplify_using_initial_conditions (struct loop *loop, tree expr)
1663 {
1664 edge e;
1665 basic_block bb;
1666 gimple stmt;
1667 tree cond;
1668 int cnt = 0;
1669
1670 if (TREE_CODE (expr) == INTEGER_CST)
1671 return expr;
1672
1673 /* Limit walking the dominators to avoid quadraticness in
1674 the number of BBs times the number of loops in degenerate
1675 cases. */
1676 for (bb = loop->header;
1677 bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK;
1678 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
1679 {
1680 if (!single_pred_p (bb))
1681 continue;
1682 e = single_pred_edge (bb);
1683
1684 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
1685 continue;
1686
1687 stmt = last_stmt (e->src);
1688 cond = fold_build2 (gimple_cond_code (stmt),
1689 boolean_type_node,
1690 gimple_cond_lhs (stmt),
1691 gimple_cond_rhs (stmt));
1692 if (e->flags & EDGE_FALSE_VALUE)
1693 cond = invert_truthvalue (cond);
1694 expr = tree_simplify_using_condition (cond, expr);
1695 ++cnt;
1696 }
1697
1698 return expr;
1699 }
1700
1701 /* Tries to simplify EXPR using the evolutions of the loop invariants
1702 in the superloops of LOOP. Returns the simplified expression
1703 (or EXPR unchanged, if no simplification was possible). */
1704
1705 static tree
1706 simplify_using_outer_evolutions (struct loop *loop, tree expr)
1707 {
1708 enum tree_code code = TREE_CODE (expr);
1709 bool changed;
1710 tree e, e0, e1, e2;
1711
1712 if (is_gimple_min_invariant (expr))
1713 return expr;
1714
1715 if (code == TRUTH_OR_EXPR
1716 || code == TRUTH_AND_EXPR
1717 || code == COND_EXPR)
1718 {
1719 changed = false;
1720
1721 e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
1722 if (TREE_OPERAND (expr, 0) != e0)
1723 changed = true;
1724
1725 e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
1726 if (TREE_OPERAND (expr, 1) != e1)
1727 changed = true;
1728
1729 if (code == COND_EXPR)
1730 {
1731 e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
1732 if (TREE_OPERAND (expr, 2) != e2)
1733 changed = true;
1734 }
1735 else
1736 e2 = NULL_TREE;
1737
1738 if (changed)
1739 {
1740 if (code == COND_EXPR)
1741 expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
1742 else
1743 expr = fold_build2 (code, boolean_type_node, e0, e1);
1744 }
1745
1746 return expr;
1747 }
1748
1749 e = instantiate_parameters (loop, expr);
1750 if (is_gimple_min_invariant (e))
1751 return e;
1752
1753 return expr;
1754 }
1755
1756 /* Returns true if EXIT is the only possible exit from LOOP. */
1757
1758 bool
1759 loop_only_exit_p (const struct loop *loop, const_edge exit)
1760 {
1761 basic_block *body;
1762 gimple_stmt_iterator bsi;
1763 unsigned i;
1764 gimple call;
1765
1766 if (exit != single_exit (loop))
1767 return false;
1768
1769 body = get_loop_body (loop);
1770 for (i = 0; i < loop->num_nodes; i++)
1771 {
1772 for (bsi = gsi_start_bb (body[i]); !gsi_end_p (bsi); gsi_next (&bsi))
1773 {
1774 call = gsi_stmt (bsi);
1775 if (gimple_code (call) != GIMPLE_CALL)
1776 continue;
1777
1778 if (gimple_has_side_effects (call))
1779 {
1780 free (body);
1781 return false;
1782 }
1783 }
1784 }
1785
1786 free (body);
1787 return true;
1788 }
1789
1790 /* Stores description of number of iterations of LOOP derived from
1791 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
1792 useful information could be derived (and fields of NITER has
1793 meaning described in comments at struct tree_niter_desc
1794 declaration), false otherwise. If WARN is true and
1795 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1796 potentially unsafe assumptions. */
1797
1798 bool
1799 number_of_iterations_exit (struct loop *loop, edge exit,
1800 struct tree_niter_desc *niter,
1801 bool warn)
1802 {
1803 gimple stmt;
1804 tree type;
1805 tree op0, op1;
1806 enum tree_code code;
1807 affine_iv iv0, iv1;
1808
1809 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
1810 return false;
1811
1812 niter->assumptions = boolean_false_node;
1813 stmt = last_stmt (exit->src);
1814 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
1815 return false;
1816
1817 /* We want the condition for staying inside loop. */
1818 code = gimple_cond_code (stmt);
1819 if (exit->flags & EDGE_TRUE_VALUE)
1820 code = invert_tree_comparison (code, false);
1821
1822 switch (code)
1823 {
1824 case GT_EXPR:
1825 case GE_EXPR:
1826 case NE_EXPR:
1827 case LT_EXPR:
1828 case LE_EXPR:
1829 break;
1830
1831 default:
1832 return false;
1833 }
1834
1835 op0 = gimple_cond_lhs (stmt);
1836 op1 = gimple_cond_rhs (stmt);
1837 type = TREE_TYPE (op0);
1838
1839 if (TREE_CODE (type) != INTEGER_TYPE
1840 && !POINTER_TYPE_P (type))
1841 return false;
1842
1843 if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, false))
1844 return false;
1845 if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, false))
1846 return false;
1847
1848 /* We don't want to see undefined signed overflow warnings while
1849 computing the number of iterations. */
1850 fold_defer_overflow_warnings ();
1851
1852 iv0.base = expand_simple_operations (iv0.base);
1853 iv1.base = expand_simple_operations (iv1.base);
1854 if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter,
1855 loop_only_exit_p (loop, exit)))
1856 {
1857 fold_undefer_and_ignore_overflow_warnings ();
1858 return false;
1859 }
1860
1861 if (optimize >= 3)
1862 {
1863 niter->assumptions = simplify_using_outer_evolutions (loop,
1864 niter->assumptions);
1865 niter->may_be_zero = simplify_using_outer_evolutions (loop,
1866 niter->may_be_zero);
1867 niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
1868 }
1869
1870 niter->assumptions
1871 = simplify_using_initial_conditions (loop,
1872 niter->assumptions);
1873 niter->may_be_zero
1874 = simplify_using_initial_conditions (loop,
1875 niter->may_be_zero);
1876
1877 fold_undefer_and_ignore_overflow_warnings ();
1878
1879 if (integer_onep (niter->assumptions))
1880 return true;
1881
1882 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1883 But if we can prove that there is overflow or some other source of weird
1884 behavior, ignore the loop even with -funsafe-loop-optimizations. */
1885 if (integer_zerop (niter->assumptions) || !single_exit (loop))
1886 return false;
1887
1888 if (flag_unsafe_loop_optimizations)
1889 niter->assumptions = boolean_true_node;
1890
1891 if (warn)
1892 {
1893 const char *wording;
1894 location_t loc = gimple_location (stmt);
1895
1896 /* We can provide a more specific warning if one of the operator is
1897 constant and the other advances by +1 or -1. */
1898 if (!integer_zerop (iv1.step)
1899 ? (integer_zerop (iv0.step)
1900 && (integer_onep (iv1.step) || integer_all_onesp (iv1.step)))
1901 : (integer_onep (iv0.step) || integer_all_onesp (iv0.step)))
1902 wording =
1903 flag_unsafe_loop_optimizations
1904 ? N_("assuming that the loop is not infinite")
1905 : N_("cannot optimize possibly infinite loops");
1906 else
1907 wording =
1908 flag_unsafe_loop_optimizations
1909 ? N_("assuming that the loop counter does not overflow")
1910 : N_("cannot optimize loop, the loop counter may overflow");
1911
1912 warning_at ((LOCATION_LINE (loc) > 0) ? loc : input_location,
1913 OPT_Wunsafe_loop_optimizations, "%s", gettext (wording));
1914 }
1915
1916 return flag_unsafe_loop_optimizations;
1917 }
1918
1919 /* Try to determine the number of iterations of LOOP. If we succeed,
1920 expression giving number of iterations is returned and *EXIT is
1921 set to the edge from that the information is obtained. Otherwise
1922 chrec_dont_know is returned. */
1923
1924 tree
1925 find_loop_niter (struct loop *loop, edge *exit)
1926 {
1927 unsigned i;
1928 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1929 edge ex;
1930 tree niter = NULL_TREE, aniter;
1931 struct tree_niter_desc desc;
1932
1933 *exit = NULL;
1934 FOR_EACH_VEC_ELT (edge, exits, i, ex)
1935 {
1936 if (!just_once_each_iteration_p (loop, ex->src))
1937 continue;
1938
1939 if (!number_of_iterations_exit (loop, ex, &desc, false))
1940 continue;
1941
1942 if (integer_nonzerop (desc.may_be_zero))
1943 {
1944 /* We exit in the first iteration through this exit.
1945 We won't find anything better. */
1946 niter = build_int_cst (unsigned_type_node, 0);
1947 *exit = ex;
1948 break;
1949 }
1950
1951 if (!integer_zerop (desc.may_be_zero))
1952 continue;
1953
1954 aniter = desc.niter;
1955
1956 if (!niter)
1957 {
1958 /* Nothing recorded yet. */
1959 niter = aniter;
1960 *exit = ex;
1961 continue;
1962 }
1963
1964 /* Prefer constants, the lower the better. */
1965 if (TREE_CODE (aniter) != INTEGER_CST)
1966 continue;
1967
1968 if (TREE_CODE (niter) != INTEGER_CST)
1969 {
1970 niter = aniter;
1971 *exit = ex;
1972 continue;
1973 }
1974
1975 if (tree_int_cst_lt (aniter, niter))
1976 {
1977 niter = aniter;
1978 *exit = ex;
1979 continue;
1980 }
1981 }
1982 VEC_free (edge, heap, exits);
1983
1984 return niter ? niter : chrec_dont_know;
1985 }
1986
1987 /* Return true if loop is known to have bounded number of iterations. */
1988
1989 bool
1990 finite_loop_p (struct loop *loop)
1991 {
1992 unsigned i;
1993 VEC (edge, heap) *exits;
1994 edge ex;
1995 struct tree_niter_desc desc;
1996 bool finite = false;
1997 int flags;
1998
1999 if (flag_unsafe_loop_optimizations)
2000 return true;
2001 flags = flags_from_decl_or_type (current_function_decl);
2002 if ((flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE))
2003 {
2004 if (dump_file && (dump_flags & TDF_DETAILS))
2005 fprintf (dump_file, "Found loop %i to be finite: it is within pure or const function.\n",
2006 loop->num);
2007 return true;
2008 }
2009
2010 exits = get_loop_exit_edges (loop);
2011 FOR_EACH_VEC_ELT (edge, exits, i, ex)
2012 {
2013 if (!just_once_each_iteration_p (loop, ex->src))
2014 continue;
2015
2016 if (number_of_iterations_exit (loop, ex, &desc, false))
2017 {
2018 if (dump_file && (dump_flags & TDF_DETAILS))
2019 {
2020 fprintf (dump_file, "Found loop %i to be finite: iterating ", loop->num);
2021 print_generic_expr (dump_file, desc.niter, TDF_SLIM);
2022 fprintf (dump_file, " times\n");
2023 }
2024 finite = true;
2025 break;
2026 }
2027 }
2028 VEC_free (edge, heap, exits);
2029 return finite;
2030 }
2031
2032 /*
2033
2034 Analysis of a number of iterations of a loop by a brute-force evaluation.
2035
2036 */
2037
2038 /* Bound on the number of iterations we try to evaluate. */
2039
2040 #define MAX_ITERATIONS_TO_TRACK \
2041 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
2042
2043 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
2044 result by a chain of operations such that all but exactly one of their
2045 operands are constants. */
2046
2047 static gimple
2048 chain_of_csts_start (struct loop *loop, tree x)
2049 {
2050 gimple stmt = SSA_NAME_DEF_STMT (x);
2051 tree use;
2052 basic_block bb = gimple_bb (stmt);
2053 enum tree_code code;
2054
2055 if (!bb
2056 || !flow_bb_inside_loop_p (loop, bb))
2057 return NULL;
2058
2059 if (gimple_code (stmt) == GIMPLE_PHI)
2060 {
2061 if (bb == loop->header)
2062 return stmt;
2063
2064 return NULL;
2065 }
2066
2067 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2068 return NULL;
2069
2070 code = gimple_assign_rhs_code (stmt);
2071 if (gimple_references_memory_p (stmt)
2072 || TREE_CODE_CLASS (code) == tcc_reference
2073 || (code == ADDR_EXPR
2074 && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
2075 return NULL;
2076
2077 use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
2078 if (use == NULL_TREE)
2079 return NULL;
2080
2081 return chain_of_csts_start (loop, use);
2082 }
2083
2084 /* Determines whether the expression X is derived from a result of a phi node
2085 in header of LOOP such that
2086
2087 * the derivation of X consists only from operations with constants
2088 * the initial value of the phi node is constant
2089 * the value of the phi node in the next iteration can be derived from the
2090 value in the current iteration by a chain of operations with constants.
2091
2092 If such phi node exists, it is returned, otherwise NULL is returned. */
2093
2094 static gimple
2095 get_base_for (struct loop *loop, tree x)
2096 {
2097 gimple phi;
2098 tree init, next;
2099
2100 if (is_gimple_min_invariant (x))
2101 return NULL;
2102
2103 phi = chain_of_csts_start (loop, x);
2104 if (!phi)
2105 return NULL;
2106
2107 init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
2108 next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
2109
2110 if (TREE_CODE (next) != SSA_NAME)
2111 return NULL;
2112
2113 if (!is_gimple_min_invariant (init))
2114 return NULL;
2115
2116 if (chain_of_csts_start (loop, next) != phi)
2117 return NULL;
2118
2119 return phi;
2120 }
2121
2122 /* Given an expression X, then
2123
2124 * if X is NULL_TREE, we return the constant BASE.
2125 * otherwise X is a SSA name, whose value in the considered loop is derived
2126 by a chain of operations with constant from a result of a phi node in
2127 the header of the loop. Then we return value of X when the value of the
2128 result of this phi node is given by the constant BASE. */
2129
2130 static tree
2131 get_val_for (tree x, tree base)
2132 {
2133 gimple stmt;
2134
2135 gcc_assert (is_gimple_min_invariant (base));
2136
2137 if (!x)
2138 return base;
2139
2140 stmt = SSA_NAME_DEF_STMT (x);
2141 if (gimple_code (stmt) == GIMPLE_PHI)
2142 return base;
2143
2144 gcc_assert (is_gimple_assign (stmt));
2145
2146 /* STMT must be either an assignment of a single SSA name or an
2147 expression involving an SSA name and a constant. Try to fold that
2148 expression using the value for the SSA name. */
2149 if (gimple_assign_ssa_name_copy_p (stmt))
2150 return get_val_for (gimple_assign_rhs1 (stmt), base);
2151 else if (gimple_assign_rhs_class (stmt) == GIMPLE_UNARY_RHS
2152 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
2153 {
2154 return fold_build1 (gimple_assign_rhs_code (stmt),
2155 gimple_expr_type (stmt),
2156 get_val_for (gimple_assign_rhs1 (stmt), base));
2157 }
2158 else if (gimple_assign_rhs_class (stmt) == GIMPLE_BINARY_RHS)
2159 {
2160 tree rhs1 = gimple_assign_rhs1 (stmt);
2161 tree rhs2 = gimple_assign_rhs2 (stmt);
2162 if (TREE_CODE (rhs1) == SSA_NAME)
2163 rhs1 = get_val_for (rhs1, base);
2164 else if (TREE_CODE (rhs2) == SSA_NAME)
2165 rhs2 = get_val_for (rhs2, base);
2166 else
2167 gcc_unreachable ();
2168 return fold_build2 (gimple_assign_rhs_code (stmt),
2169 gimple_expr_type (stmt), rhs1, rhs2);
2170 }
2171 else
2172 gcc_unreachable ();
2173 }
2174
2175
2176 /* Tries to count the number of iterations of LOOP till it exits by EXIT
2177 by brute force -- i.e. by determining the value of the operands of the
2178 condition at EXIT in first few iterations of the loop (assuming that
2179 these values are constant) and determining the first one in that the
2180 condition is not satisfied. Returns the constant giving the number
2181 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
2182
2183 tree
2184 loop_niter_by_eval (struct loop *loop, edge exit)
2185 {
2186 tree acnd;
2187 tree op[2], val[2], next[2], aval[2];
2188 gimple phi, cond;
2189 unsigned i, j;
2190 enum tree_code cmp;
2191
2192 cond = last_stmt (exit->src);
2193 if (!cond || gimple_code (cond) != GIMPLE_COND)
2194 return chrec_dont_know;
2195
2196 cmp = gimple_cond_code (cond);
2197 if (exit->flags & EDGE_TRUE_VALUE)
2198 cmp = invert_tree_comparison (cmp, false);
2199
2200 switch (cmp)
2201 {
2202 case EQ_EXPR:
2203 case NE_EXPR:
2204 case GT_EXPR:
2205 case GE_EXPR:
2206 case LT_EXPR:
2207 case LE_EXPR:
2208 op[0] = gimple_cond_lhs (cond);
2209 op[1] = gimple_cond_rhs (cond);
2210 break;
2211
2212 default:
2213 return chrec_dont_know;
2214 }
2215
2216 for (j = 0; j < 2; j++)
2217 {
2218 if (is_gimple_min_invariant (op[j]))
2219 {
2220 val[j] = op[j];
2221 next[j] = NULL_TREE;
2222 op[j] = NULL_TREE;
2223 }
2224 else
2225 {
2226 phi = get_base_for (loop, op[j]);
2227 if (!phi)
2228 return chrec_dont_know;
2229 val[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
2230 next[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
2231 }
2232 }
2233
2234 /* Don't issue signed overflow warnings. */
2235 fold_defer_overflow_warnings ();
2236
2237 for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
2238 {
2239 for (j = 0; j < 2; j++)
2240 aval[j] = get_val_for (op[j], val[j]);
2241
2242 acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]);
2243 if (acnd && integer_zerop (acnd))
2244 {
2245 fold_undefer_and_ignore_overflow_warnings ();
2246 if (dump_file && (dump_flags & TDF_DETAILS))
2247 fprintf (dump_file,
2248 "Proved that loop %d iterates %d times using brute force.\n",
2249 loop->num, i);
2250 return build_int_cst (unsigned_type_node, i);
2251 }
2252
2253 for (j = 0; j < 2; j++)
2254 {
2255 val[j] = get_val_for (next[j], val[j]);
2256 if (!is_gimple_min_invariant (val[j]))
2257 {
2258 fold_undefer_and_ignore_overflow_warnings ();
2259 return chrec_dont_know;
2260 }
2261 }
2262 }
2263
2264 fold_undefer_and_ignore_overflow_warnings ();
2265
2266 return chrec_dont_know;
2267 }
2268
2269 /* Finds the exit of the LOOP by that the loop exits after a constant
2270 number of iterations and stores the exit edge to *EXIT. The constant
2271 giving the number of iterations of LOOP is returned. The number of
2272 iterations is determined using loop_niter_by_eval (i.e. by brute force
2273 evaluation). If we are unable to find the exit for that loop_niter_by_eval
2274 determines the number of iterations, chrec_dont_know is returned. */
2275
2276 tree
2277 find_loop_niter_by_eval (struct loop *loop, edge *exit)
2278 {
2279 unsigned i;
2280 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
2281 edge ex;
2282 tree niter = NULL_TREE, aniter;
2283
2284 *exit = NULL;
2285
2286 /* Loops with multiple exits are expensive to handle and less important. */
2287 if (!flag_expensive_optimizations
2288 && VEC_length (edge, exits) > 1)
2289 {
2290 VEC_free (edge, heap, exits);
2291 return chrec_dont_know;
2292 }
2293
2294 FOR_EACH_VEC_ELT (edge, exits, i, ex)
2295 {
2296 if (!just_once_each_iteration_p (loop, ex->src))
2297 continue;
2298
2299 aniter = loop_niter_by_eval (loop, ex);
2300 if (chrec_contains_undetermined (aniter))
2301 continue;
2302
2303 if (niter
2304 && !tree_int_cst_lt (aniter, niter))
2305 continue;
2306
2307 niter = aniter;
2308 *exit = ex;
2309 }
2310 VEC_free (edge, heap, exits);
2311
2312 return niter ? niter : chrec_dont_know;
2313 }
2314
2315 /*
2316
2317 Analysis of upper bounds on number of iterations of a loop.
2318
2319 */
2320
2321 static double_int derive_constant_upper_bound_ops (tree, tree,
2322 enum tree_code, tree);
2323
2324 /* Returns a constant upper bound on the value of the right-hand side of
2325 an assignment statement STMT. */
2326
2327 static double_int
2328 derive_constant_upper_bound_assign (gimple stmt)
2329 {
2330 enum tree_code code = gimple_assign_rhs_code (stmt);
2331 tree op0 = gimple_assign_rhs1 (stmt);
2332 tree op1 = gimple_assign_rhs2 (stmt);
2333
2334 return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt)),
2335 op0, code, op1);
2336 }
2337
2338 /* Returns a constant upper bound on the value of expression VAL. VAL
2339 is considered to be unsigned. If its type is signed, its value must
2340 be nonnegative. */
2341
2342 static double_int
2343 derive_constant_upper_bound (tree val)
2344 {
2345 enum tree_code code;
2346 tree op0, op1;
2347
2348 extract_ops_from_tree (val, &code, &op0, &op1);
2349 return derive_constant_upper_bound_ops (TREE_TYPE (val), op0, code, op1);
2350 }
2351
2352 /* Returns a constant upper bound on the value of expression OP0 CODE OP1,
2353 whose type is TYPE. The expression is considered to be unsigned. If
2354 its type is signed, its value must be nonnegative. */
2355
2356 static double_int
2357 derive_constant_upper_bound_ops (tree type, tree op0,
2358 enum tree_code code, tree op1)
2359 {
2360 tree subtype, maxt;
2361 double_int bnd, max, mmax, cst;
2362 gimple stmt;
2363
2364 if (INTEGRAL_TYPE_P (type))
2365 maxt = TYPE_MAX_VALUE (type);
2366 else
2367 maxt = upper_bound_in_type (type, type);
2368
2369 max = tree_to_double_int (maxt);
2370
2371 switch (code)
2372 {
2373 case INTEGER_CST:
2374 return tree_to_double_int (op0);
2375
2376 CASE_CONVERT:
2377 subtype = TREE_TYPE (op0);
2378 if (!TYPE_UNSIGNED (subtype)
2379 /* If TYPE is also signed, the fact that VAL is nonnegative implies
2380 that OP0 is nonnegative. */
2381 && TYPE_UNSIGNED (type)
2382 && !tree_expr_nonnegative_p (op0))
2383 {
2384 /* If we cannot prove that the casted expression is nonnegative,
2385 we cannot establish more useful upper bound than the precision
2386 of the type gives us. */
2387 return max;
2388 }
2389
2390 /* We now know that op0 is an nonnegative value. Try deriving an upper
2391 bound for it. */
2392 bnd = derive_constant_upper_bound (op0);
2393
2394 /* If the bound does not fit in TYPE, max. value of TYPE could be
2395 attained. */
2396 if (max.ult (bnd))
2397 return max;
2398
2399 return bnd;
2400
2401 case PLUS_EXPR:
2402 case POINTER_PLUS_EXPR:
2403 case MINUS_EXPR:
2404 if (TREE_CODE (op1) != INTEGER_CST
2405 || !tree_expr_nonnegative_p (op0))
2406 return max;
2407
2408 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
2409 choose the most logical way how to treat this constant regardless
2410 of the signedness of the type. */
2411 cst = tree_to_double_int (op1);
2412 cst = cst.sext (TYPE_PRECISION (type));
2413 if (code != MINUS_EXPR)
2414 cst = -cst;
2415
2416 bnd = derive_constant_upper_bound (op0);
2417
2418 if (cst.is_negative ())
2419 {
2420 cst = -cst;
2421 /* Avoid CST == 0x80000... */
2422 if (cst.is_negative ())
2423 return max;;
2424
2425 /* OP0 + CST. We need to check that
2426 BND <= MAX (type) - CST. */
2427
2428 mmax -= cst;
2429 if (bnd.ugt (mmax))
2430 return max;
2431
2432 return bnd + cst;
2433 }
2434 else
2435 {
2436 /* OP0 - CST, where CST >= 0.
2437
2438 If TYPE is signed, we have already verified that OP0 >= 0, and we
2439 know that the result is nonnegative. This implies that
2440 VAL <= BND - CST.
2441
2442 If TYPE is unsigned, we must additionally know that OP0 >= CST,
2443 otherwise the operation underflows.
2444 */
2445
2446 /* This should only happen if the type is unsigned; however, for
2447 buggy programs that use overflowing signed arithmetics even with
2448 -fno-wrapv, this condition may also be true for signed values. */
2449 if (bnd.ult (cst))
2450 return max;
2451
2452 if (TYPE_UNSIGNED (type))
2453 {
2454 tree tem = fold_binary (GE_EXPR, boolean_type_node, op0,
2455 double_int_to_tree (type, cst));
2456 if (!tem || integer_nonzerop (tem))
2457 return max;
2458 }
2459
2460 bnd -= cst;
2461 }
2462
2463 return bnd;
2464
2465 case FLOOR_DIV_EXPR:
2466 case EXACT_DIV_EXPR:
2467 if (TREE_CODE (op1) != INTEGER_CST
2468 || tree_int_cst_sign_bit (op1))
2469 return max;
2470
2471 bnd = derive_constant_upper_bound (op0);
2472 return bnd.udiv (tree_to_double_int (op1), FLOOR_DIV_EXPR);
2473
2474 case BIT_AND_EXPR:
2475 if (TREE_CODE (op1) != INTEGER_CST
2476 || tree_int_cst_sign_bit (op1))
2477 return max;
2478 return tree_to_double_int (op1);
2479
2480 case SSA_NAME:
2481 stmt = SSA_NAME_DEF_STMT (op0);
2482 if (gimple_code (stmt) != GIMPLE_ASSIGN
2483 || gimple_assign_lhs (stmt) != op0)
2484 return max;
2485 return derive_constant_upper_bound_assign (stmt);
2486
2487 default:
2488 return max;
2489 }
2490 }
2491
2492 /* Records that every statement in LOOP is executed I_BOUND times.
2493 REALISTIC is true if I_BOUND is expected to be close to the real number
2494 of iterations. UPPER is true if we are sure the loop iterates at most
2495 I_BOUND times. */
2496
2497 void
2498 record_niter_bound (struct loop *loop, double_int i_bound, bool realistic,
2499 bool upper)
2500 {
2501 /* Update the bounds only when there is no previous estimation, or when the
2502 current estimation is smaller. */
2503 if (upper
2504 && (!loop->any_upper_bound
2505 || i_bound.ult (loop->nb_iterations_upper_bound)))
2506 {
2507 loop->any_upper_bound = true;
2508 loop->nb_iterations_upper_bound = i_bound;
2509 }
2510 if (realistic
2511 && (!loop->any_estimate
2512 || i_bound.ult (loop->nb_iterations_estimate)))
2513 {
2514 loop->any_estimate = true;
2515 loop->nb_iterations_estimate = i_bound;
2516 }
2517
2518 /* If an upper bound is smaller than the realistic estimate of the
2519 number of iterations, use the upper bound instead. */
2520 if (loop->any_upper_bound
2521 && loop->any_estimate
2522 && loop->nb_iterations_upper_bound.ult (loop->nb_iterations_estimate))
2523 loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
2524 }
2525
2526 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
2527 is true if the loop is exited immediately after STMT, and this exit
2528 is taken at last when the STMT is executed BOUND + 1 times.
2529 REALISTIC is true if BOUND is expected to be close to the real number
2530 of iterations. UPPER is true if we are sure the loop iterates at most
2531 BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */
2532
2533 static void
2534 record_estimate (struct loop *loop, tree bound, double_int i_bound,
2535 gimple at_stmt, bool is_exit, bool realistic, bool upper)
2536 {
2537 double_int delta;
2538 edge exit;
2539
2540 if (dump_file && (dump_flags & TDF_DETAILS))
2541 {
2542 fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : "");
2543 print_gimple_stmt (dump_file, at_stmt, 0, TDF_SLIM);
2544 fprintf (dump_file, " is %sexecuted at most ",
2545 upper ? "" : "probably ");
2546 print_generic_expr (dump_file, bound, TDF_SLIM);
2547 fprintf (dump_file, " (bounded by ");
2548 dump_double_int (dump_file, i_bound, true);
2549 fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num);
2550 }
2551
2552 /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
2553 real number of iterations. */
2554 if (TREE_CODE (bound) != INTEGER_CST)
2555 realistic = false;
2556 if (!upper && !realistic)
2557 return;
2558
2559 /* If we have a guaranteed upper bound, record it in the appropriate
2560 list. */
2561 if (upper)
2562 {
2563 struct nb_iter_bound *elt = ggc_alloc_nb_iter_bound ();
2564
2565 elt->bound = i_bound;
2566 elt->stmt = at_stmt;
2567 elt->is_exit = is_exit;
2568 elt->next = loop->bounds;
2569 loop->bounds = elt;
2570 }
2571
2572 /* Update the number of iteration estimates according to the bound.
2573 If at_stmt is an exit or dominates the single exit from the loop,
2574 then the loop latch is executed at most BOUND times, otherwise
2575 it can be executed BOUND + 1 times. */
2576 exit = single_exit (loop);
2577 if (is_exit
2578 || (exit != NULL
2579 && dominated_by_p (CDI_DOMINATORS,
2580 exit->src, gimple_bb (at_stmt))))
2581 delta = double_int_zero;
2582 else
2583 delta = double_int_one;
2584 i_bound += delta;
2585
2586 /* If an overflow occurred, ignore the result. */
2587 if (i_bound.ult (delta))
2588 return;
2589
2590 record_niter_bound (loop, i_bound, realistic, upper);
2591 }
2592
2593 /* Record the estimate on number of iterations of LOOP based on the fact that
2594 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
2595 its values belong to the range <LOW, HIGH>. REALISTIC is true if the
2596 estimated number of iterations is expected to be close to the real one.
2597 UPPER is true if we are sure the induction variable does not wrap. */
2598
2599 static void
2600 record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple stmt,
2601 tree low, tree high, bool realistic, bool upper)
2602 {
2603 tree niter_bound, extreme, delta;
2604 tree type = TREE_TYPE (base), unsigned_type;
2605 double_int max;
2606
2607 if (TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
2608 return;
2609
2610 if (dump_file && (dump_flags & TDF_DETAILS))
2611 {
2612 fprintf (dump_file, "Induction variable (");
2613 print_generic_expr (dump_file, TREE_TYPE (base), TDF_SLIM);
2614 fprintf (dump_file, ") ");
2615 print_generic_expr (dump_file, base, TDF_SLIM);
2616 fprintf (dump_file, " + ");
2617 print_generic_expr (dump_file, step, TDF_SLIM);
2618 fprintf (dump_file, " * iteration does not wrap in statement ");
2619 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2620 fprintf (dump_file, " in loop %d.\n", loop->num);
2621 }
2622
2623 unsigned_type = unsigned_type_for (type);
2624 base = fold_convert (unsigned_type, base);
2625 step = fold_convert (unsigned_type, step);
2626
2627 if (tree_int_cst_sign_bit (step))
2628 {
2629 extreme = fold_convert (unsigned_type, low);
2630 if (TREE_CODE (base) != INTEGER_CST)
2631 base = fold_convert (unsigned_type, high);
2632 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
2633 step = fold_build1 (NEGATE_EXPR, unsigned_type, step);
2634 }
2635 else
2636 {
2637 extreme = fold_convert (unsigned_type, high);
2638 if (TREE_CODE (base) != INTEGER_CST)
2639 base = fold_convert (unsigned_type, low);
2640 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
2641 }
2642
2643 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
2644 would get out of the range. */
2645 niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step);
2646 max = derive_constant_upper_bound (niter_bound);
2647 record_estimate (loop, niter_bound, max, stmt, false, realistic, upper);
2648 }
2649
2650 /* Determine information about number of iterations a LOOP from the index
2651 IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
2652 guaranteed to be executed in every iteration of LOOP. Callback for
2653 for_each_index. */
2654
2655 struct ilb_data
2656 {
2657 struct loop *loop;
2658 gimple stmt;
2659 bool reliable;
2660 };
2661
2662 static bool
2663 idx_infer_loop_bounds (tree base, tree *idx, void *dta)
2664 {
2665 struct ilb_data *data = (struct ilb_data *) dta;
2666 tree ev, init, step;
2667 tree low, high, type, next;
2668 bool sign, upper = data->reliable, at_end = false;
2669 struct loop *loop = data->loop;
2670
2671 if (TREE_CODE (base) != ARRAY_REF)
2672 return true;
2673
2674 /* For arrays at the end of the structure, we are not guaranteed that they
2675 do not really extend over their declared size. However, for arrays of
2676 size greater than one, this is unlikely to be intended. */
2677 if (array_at_struct_end_p (base))
2678 {
2679 at_end = true;
2680 upper = false;
2681 }
2682
2683 ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx));
2684 init = initial_condition (ev);
2685 step = evolution_part_in_loop_num (ev, loop->num);
2686
2687 if (!init
2688 || !step
2689 || TREE_CODE (step) != INTEGER_CST
2690 || integer_zerop (step)
2691 || tree_contains_chrecs (init, NULL)
2692 || chrec_contains_symbols_defined_in_loop (init, loop->num))
2693 return true;
2694
2695 low = array_ref_low_bound (base);
2696 high = array_ref_up_bound (base);
2697
2698 /* The case of nonconstant bounds could be handled, but it would be
2699 complicated. */
2700 if (TREE_CODE (low) != INTEGER_CST
2701 || !high
2702 || TREE_CODE (high) != INTEGER_CST)
2703 return true;
2704 sign = tree_int_cst_sign_bit (step);
2705 type = TREE_TYPE (step);
2706
2707 /* The array of length 1 at the end of a structure most likely extends
2708 beyond its bounds. */
2709 if (at_end
2710 && operand_equal_p (low, high, 0))
2711 return true;
2712
2713 /* In case the relevant bound of the array does not fit in type, or
2714 it does, but bound + step (in type) still belongs into the range of the
2715 array, the index may wrap and still stay within the range of the array
2716 (consider e.g. if the array is indexed by the full range of
2717 unsigned char).
2718
2719 To make things simpler, we require both bounds to fit into type, although
2720 there are cases where this would not be strictly necessary. */
2721 if (!int_fits_type_p (high, type)
2722 || !int_fits_type_p (low, type))
2723 return true;
2724 low = fold_convert (type, low);
2725 high = fold_convert (type, high);
2726
2727 if (sign)
2728 next = fold_binary (PLUS_EXPR, type, low, step);
2729 else
2730 next = fold_binary (PLUS_EXPR, type, high, step);
2731
2732 if (tree_int_cst_compare (low, next) <= 0
2733 && tree_int_cst_compare (next, high) <= 0)
2734 return true;
2735
2736 record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true, upper);
2737 return true;
2738 }
2739
2740 /* Determine information about number of iterations a LOOP from the bounds
2741 of arrays in the data reference REF accessed in STMT. RELIABLE is true if
2742 STMT is guaranteed to be executed in every iteration of LOOP.*/
2743
2744 static void
2745 infer_loop_bounds_from_ref (struct loop *loop, gimple stmt, tree ref,
2746 bool reliable)
2747 {
2748 struct ilb_data data;
2749
2750 data.loop = loop;
2751 data.stmt = stmt;
2752 data.reliable = reliable;
2753 for_each_index (&ref, idx_infer_loop_bounds, &data);
2754 }
2755
2756 /* Determine information about number of iterations of a LOOP from the way
2757 arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
2758 executed in every iteration of LOOP. */
2759
2760 static void
2761 infer_loop_bounds_from_array (struct loop *loop, gimple stmt, bool reliable)
2762 {
2763 if (is_gimple_assign (stmt))
2764 {
2765 tree op0 = gimple_assign_lhs (stmt);
2766 tree op1 = gimple_assign_rhs1 (stmt);
2767
2768 /* For each memory access, analyze its access function
2769 and record a bound on the loop iteration domain. */
2770 if (REFERENCE_CLASS_P (op0))
2771 infer_loop_bounds_from_ref (loop, stmt, op0, reliable);
2772
2773 if (REFERENCE_CLASS_P (op1))
2774 infer_loop_bounds_from_ref (loop, stmt, op1, reliable);
2775 }
2776 else if (is_gimple_call (stmt))
2777 {
2778 tree arg, lhs;
2779 unsigned i, n = gimple_call_num_args (stmt);
2780
2781 lhs = gimple_call_lhs (stmt);
2782 if (lhs && REFERENCE_CLASS_P (lhs))
2783 infer_loop_bounds_from_ref (loop, stmt, lhs, reliable);
2784
2785 for (i = 0; i < n; i++)
2786 {
2787 arg = gimple_call_arg (stmt, i);
2788 if (REFERENCE_CLASS_P (arg))
2789 infer_loop_bounds_from_ref (loop, stmt, arg, reliable);
2790 }
2791 }
2792 }
2793
2794 /* Determine information about number of iterations of a LOOP from the fact
2795 that pointer arithmetics in STMT does not overflow. */
2796
2797 static void
2798 infer_loop_bounds_from_pointer_arith (struct loop *loop, gimple stmt)
2799 {
2800 tree def, base, step, scev, type, low, high;
2801 tree var, ptr;
2802
2803 if (!is_gimple_assign (stmt)
2804 || gimple_assign_rhs_code (stmt) != POINTER_PLUS_EXPR)
2805 return;
2806
2807 def = gimple_assign_lhs (stmt);
2808 if (TREE_CODE (def) != SSA_NAME)
2809 return;
2810
2811 type = TREE_TYPE (def);
2812 if (!nowrap_type_p (type))
2813 return;
2814
2815 ptr = gimple_assign_rhs1 (stmt);
2816 if (!expr_invariant_in_loop_p (loop, ptr))
2817 return;
2818
2819 var = gimple_assign_rhs2 (stmt);
2820 if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (var)))
2821 return;
2822
2823 scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
2824 if (chrec_contains_undetermined (scev))
2825 return;
2826
2827 base = initial_condition_in_loop_num (scev, loop->num);
2828 step = evolution_part_in_loop_num (scev, loop->num);
2829
2830 if (!base || !step
2831 || TREE_CODE (step) != INTEGER_CST
2832 || tree_contains_chrecs (base, NULL)
2833 || chrec_contains_symbols_defined_in_loop (base, loop->num))
2834 return;
2835
2836 low = lower_bound_in_type (type, type);
2837 high = upper_bound_in_type (type, type);
2838
2839 /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot
2840 produce a NULL pointer. The contrary would mean NULL points to an object,
2841 while NULL is supposed to compare unequal with the address of all objects.
2842 Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a
2843 NULL pointer since that would mean wrapping, which we assume here not to
2844 happen. So, we can exclude NULL from the valid range of pointer
2845 arithmetic. */
2846 if (flag_delete_null_pointer_checks && int_cst_value (low) == 0)
2847 low = build_int_cstu (TREE_TYPE (low), TYPE_ALIGN_UNIT (TREE_TYPE (type)));
2848
2849 record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
2850 }
2851
2852 /* Determine information about number of iterations of a LOOP from the fact
2853 that signed arithmetics in STMT does not overflow. */
2854
2855 static void
2856 infer_loop_bounds_from_signedness (struct loop *loop, gimple stmt)
2857 {
2858 tree def, base, step, scev, type, low, high;
2859
2860 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2861 return;
2862
2863 def = gimple_assign_lhs (stmt);
2864
2865 if (TREE_CODE (def) != SSA_NAME)
2866 return;
2867
2868 type = TREE_TYPE (def);
2869 if (!INTEGRAL_TYPE_P (type)
2870 || !TYPE_OVERFLOW_UNDEFINED (type))
2871 return;
2872
2873 scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
2874 if (chrec_contains_undetermined (scev))
2875 return;
2876
2877 base = initial_condition_in_loop_num (scev, loop->num);
2878 step = evolution_part_in_loop_num (scev, loop->num);
2879
2880 if (!base || !step
2881 || TREE_CODE (step) != INTEGER_CST
2882 || tree_contains_chrecs (base, NULL)
2883 || chrec_contains_symbols_defined_in_loop (base, loop->num))
2884 return;
2885
2886 low = lower_bound_in_type (type, type);
2887 high = upper_bound_in_type (type, type);
2888
2889 record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
2890 }
2891
2892 /* The following analyzers are extracting informations on the bounds
2893 of LOOP from the following undefined behaviors:
2894
2895 - data references should not access elements over the statically
2896 allocated size,
2897
2898 - signed variables should not overflow when flag_wrapv is not set.
2899 */
2900
2901 static void
2902 infer_loop_bounds_from_undefined (struct loop *loop)
2903 {
2904 unsigned i;
2905 basic_block *bbs;
2906 gimple_stmt_iterator bsi;
2907 basic_block bb;
2908 bool reliable;
2909
2910 bbs = get_loop_body (loop);
2911
2912 for (i = 0; i < loop->num_nodes; i++)
2913 {
2914 bb = bbs[i];
2915
2916 /* If BB is not executed in each iteration of the loop, we cannot
2917 use the operations in it to infer reliable upper bound on the
2918 # of iterations of the loop. However, we can use it as a guess. */
2919 reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb);
2920
2921 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
2922 {
2923 gimple stmt = gsi_stmt (bsi);
2924
2925 infer_loop_bounds_from_array (loop, stmt, reliable);
2926
2927 if (reliable)
2928 {
2929 infer_loop_bounds_from_signedness (loop, stmt);
2930 infer_loop_bounds_from_pointer_arith (loop, stmt);
2931 }
2932 }
2933
2934 }
2935
2936 free (bbs);
2937 }
2938
2939 /* Converts VAL to double_int. */
2940
2941 static double_int
2942 gcov_type_to_double_int (gcov_type val)
2943 {
2944 double_int ret;
2945
2946 ret.low = (unsigned HOST_WIDE_INT) val;
2947 /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by
2948 the size of type. */
2949 val >>= HOST_BITS_PER_WIDE_INT - 1;
2950 val >>= 1;
2951 ret.high = (unsigned HOST_WIDE_INT) val;
2952
2953 return ret;
2954 }
2955
2956 /* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
2957 is true also use estimates derived from undefined behavior. */
2958
2959 void
2960 estimate_numbers_of_iterations_loop (struct loop *loop)
2961 {
2962 VEC (edge, heap) *exits;
2963 tree niter, type;
2964 unsigned i;
2965 struct tree_niter_desc niter_desc;
2966 edge ex;
2967 double_int bound;
2968 edge likely_exit;
2969
2970 /* Give up if we already have tried to compute an estimation. */
2971 if (loop->estimate_state != EST_NOT_COMPUTED)
2972 return;
2973
2974 loop->estimate_state = EST_AVAILABLE;
2975 /* Force estimate compuation but leave any existing upper bound in place. */
2976 loop->any_estimate = false;
2977
2978 exits = get_loop_exit_edges (loop);
2979 likely_exit = single_likely_exit (loop);
2980 FOR_EACH_VEC_ELT (edge, exits, i, ex)
2981 {
2982 if (!number_of_iterations_exit (loop, ex, &niter_desc, false))
2983 continue;
2984
2985 niter = niter_desc.niter;
2986 type = TREE_TYPE (niter);
2987 if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST)
2988 niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
2989 build_int_cst (type, 0),
2990 niter);
2991 record_estimate (loop, niter, niter_desc.max,
2992 last_stmt (ex->src),
2993 true, ex == likely_exit, true);
2994 }
2995 VEC_free (edge, heap, exits);
2996
2997 infer_loop_bounds_from_undefined (loop);
2998
2999 /* If we have a measured profile, use it to estimate the number of
3000 iterations. */
3001 if (loop->header->count != 0)
3002 {
3003 gcov_type nit = expected_loop_iterations_unbounded (loop) + 1;
3004 bound = gcov_type_to_double_int (nit);
3005 record_niter_bound (loop, bound, true, false);
3006 }
3007 }
3008
3009 /* Sets NIT to the estimated number of executions of the latch of the
3010 LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as
3011 large as the number of iterations. If we have no reliable estimate,
3012 the function returns false, otherwise returns true. */
3013
3014 bool
3015 estimated_loop_iterations (struct loop *loop, double_int *nit)
3016 {
3017 /* When SCEV information is available, try to update loop iterations
3018 estimate. Otherwise just return whatever we recorded earlier. */
3019 if (scev_initialized_p ())
3020 estimate_numbers_of_iterations_loop (loop);
3021
3022 /* Even if the bound is not recorded, possibly we can derrive one from
3023 profile. */
3024 if (!loop->any_estimate)
3025 {
3026 if (loop->header->count)
3027 {
3028 *nit = gcov_type_to_double_int
3029 (expected_loop_iterations_unbounded (loop) + 1);
3030 return true;
3031 }
3032 return false;
3033 }
3034
3035 *nit = loop->nb_iterations_estimate;
3036 return true;
3037 }
3038
3039 /* Sets NIT to an upper bound for the maximum number of executions of the
3040 latch of the LOOP. If we have no reliable estimate, the function returns
3041 false, otherwise returns true. */
3042
3043 bool
3044 max_loop_iterations (struct loop *loop, double_int *nit)
3045 {
3046 /* When SCEV information is available, try to update loop iterations
3047 estimate. Otherwise just return whatever we recorded earlier. */
3048 if (scev_initialized_p ())
3049 estimate_numbers_of_iterations_loop (loop);
3050 if (!loop->any_upper_bound)
3051 return false;
3052
3053 *nit = loop->nb_iterations_upper_bound;
3054 return true;
3055 }
3056
3057 /* Similar to estimated_loop_iterations, but returns the estimate only
3058 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3059 on the number of iterations of LOOP could not be derived, returns -1. */
3060
3061 HOST_WIDE_INT
3062 estimated_loop_iterations_int (struct loop *loop)
3063 {
3064 double_int nit;
3065 HOST_WIDE_INT hwi_nit;
3066
3067 if (!estimated_loop_iterations (loop, &nit))
3068 return -1;
3069
3070 if (!nit.fits_shwi ())
3071 return -1;
3072 hwi_nit = nit.to_shwi ();
3073
3074 return hwi_nit < 0 ? -1 : hwi_nit;
3075 }
3076
3077 /* Similar to max_loop_iterations, but returns the estimate only
3078 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
3079 on the number of iterations of LOOP could not be derived, returns -1. */
3080
3081 HOST_WIDE_INT
3082 max_loop_iterations_int (struct loop *loop)
3083 {
3084 double_int nit;
3085 HOST_WIDE_INT hwi_nit;
3086
3087 if (!max_loop_iterations (loop, &nit))
3088 return -1;
3089
3090 if (!nit.fits_shwi ())
3091 return -1;
3092 hwi_nit = nit.to_shwi ();
3093
3094 return hwi_nit < 0 ? -1 : hwi_nit;
3095 }
3096
3097 /* Returns an upper bound on the number of executions of statements
3098 in the LOOP. For statements before the loop exit, this exceeds
3099 the number of execution of the latch by one. */
3100
3101 HOST_WIDE_INT
3102 max_stmt_executions_int (struct loop *loop)
3103 {
3104 HOST_WIDE_INT nit = max_loop_iterations_int (loop);
3105 HOST_WIDE_INT snit;
3106
3107 if (nit == -1)
3108 return -1;
3109
3110 snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
3111
3112 /* If the computation overflows, return -1. */
3113 return snit < 0 ? -1 : snit;
3114 }
3115
3116 /* Returns an estimate for the number of executions of statements
3117 in the LOOP. For statements before the loop exit, this exceeds
3118 the number of execution of the latch by one. */
3119
3120 HOST_WIDE_INT
3121 estimated_stmt_executions_int (struct loop *loop)
3122 {
3123 HOST_WIDE_INT nit = estimated_loop_iterations_int (loop);
3124 HOST_WIDE_INT snit;
3125
3126 if (nit == -1)
3127 return -1;
3128
3129 snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
3130
3131 /* If the computation overflows, return -1. */
3132 return snit < 0 ? -1 : snit;
3133 }
3134
3135 /* Sets NIT to the estimated maximum number of executions of the latch of the
3136 LOOP, plus one. If we have no reliable estimate, the function returns
3137 false, otherwise returns true. */
3138
3139 bool
3140 max_stmt_executions (struct loop *loop, double_int *nit)
3141 {
3142 double_int nit_minus_one;
3143
3144 if (!max_loop_iterations (loop, nit))
3145 return false;
3146
3147 nit_minus_one = *nit;
3148
3149 *nit += double_int_one;
3150
3151 return (*nit).ugt (nit_minus_one);
3152 }
3153
3154 /* Sets NIT to the estimated number of executions of the latch of the
3155 LOOP, plus one. If we have no reliable estimate, the function returns
3156 false, otherwise returns true. */
3157
3158 bool
3159 estimated_stmt_executions (struct loop *loop, double_int *nit)
3160 {
3161 double_int nit_minus_one;
3162
3163 if (!estimated_loop_iterations (loop, nit))
3164 return false;
3165
3166 nit_minus_one = *nit;
3167
3168 *nit += double_int_one;
3169
3170 return (*nit).ugt (nit_minus_one);
3171 }
3172
3173 /* Records estimates on numbers of iterations of loops. */
3174
3175 void
3176 estimate_numbers_of_iterations (void)
3177 {
3178 loop_iterator li;
3179 struct loop *loop;
3180
3181 /* We don't want to issue signed overflow warnings while getting
3182 loop iteration estimates. */
3183 fold_defer_overflow_warnings ();
3184
3185 FOR_EACH_LOOP (li, loop, 0)
3186 {
3187 estimate_numbers_of_iterations_loop (loop);
3188 }
3189
3190 fold_undefer_and_ignore_overflow_warnings ();
3191 }
3192
3193 /* Returns true if statement S1 dominates statement S2. */
3194
3195 bool
3196 stmt_dominates_stmt_p (gimple s1, gimple s2)
3197 {
3198 basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
3199
3200 if (!bb1
3201 || s1 == s2)
3202 return true;
3203
3204 if (bb1 == bb2)
3205 {
3206 gimple_stmt_iterator bsi;
3207
3208 if (gimple_code (s2) == GIMPLE_PHI)
3209 return false;
3210
3211 if (gimple_code (s1) == GIMPLE_PHI)
3212 return true;
3213
3214 for (bsi = gsi_start_bb (bb1); gsi_stmt (bsi) != s2; gsi_next (&bsi))
3215 if (gsi_stmt (bsi) == s1)
3216 return true;
3217
3218 return false;
3219 }
3220
3221 return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
3222 }
3223
3224 /* Returns true when we can prove that the number of executions of
3225 STMT in the loop is at most NITER, according to the bound on
3226 the number of executions of the statement NITER_BOUND->stmt recorded in
3227 NITER_BOUND. If STMT is NULL, we must prove this bound for all
3228 statements in the loop. */
3229
3230 static bool
3231 n_of_executions_at_most (gimple stmt,
3232 struct nb_iter_bound *niter_bound,
3233 tree niter)
3234 {
3235 double_int bound = niter_bound->bound;
3236 tree nit_type = TREE_TYPE (niter), e;
3237 enum tree_code cmp;
3238
3239 gcc_assert (TYPE_UNSIGNED (nit_type));
3240
3241 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
3242 the number of iterations is small. */
3243 if (!double_int_fits_to_tree_p (nit_type, bound))
3244 return false;
3245
3246 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3247 times. This means that:
3248
3249 -- if NITER_BOUND->is_exit is true, then everything before
3250 NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
3251 times, and everything after it at most NITER_BOUND->bound times.
3252
3253 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
3254 is executed, then NITER_BOUND->stmt is executed as well in the same
3255 iteration (we conclude that if both statements belong to the same
3256 basic block, or if STMT is after NITER_BOUND->stmt), then STMT
3257 is executed at most NITER_BOUND->bound + 1 times. Otherwise STMT is
3258 executed at most NITER_BOUND->bound + 2 times. */
3259
3260 if (niter_bound->is_exit)
3261 {
3262 if (stmt
3263 && stmt != niter_bound->stmt
3264 && stmt_dominates_stmt_p (niter_bound->stmt, stmt))
3265 cmp = GE_EXPR;
3266 else
3267 cmp = GT_EXPR;
3268 }
3269 else
3270 {
3271 if (!stmt
3272 || (gimple_bb (stmt) != gimple_bb (niter_bound->stmt)
3273 && !stmt_dominates_stmt_p (niter_bound->stmt, stmt)))
3274 {
3275 bound += double_int_one;
3276 if (bound.is_zero ()
3277 || !double_int_fits_to_tree_p (nit_type, bound))
3278 return false;
3279 }
3280 cmp = GT_EXPR;
3281 }
3282
3283 e = fold_binary (cmp, boolean_type_node,
3284 niter, double_int_to_tree (nit_type, bound));
3285 return e && integer_nonzerop (e);
3286 }
3287
3288 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
3289
3290 bool
3291 nowrap_type_p (tree type)
3292 {
3293 if (INTEGRAL_TYPE_P (type)
3294 && TYPE_OVERFLOW_UNDEFINED (type))
3295 return true;
3296
3297 if (POINTER_TYPE_P (type))
3298 return true;
3299
3300 return false;
3301 }
3302
3303 /* Return false only when the induction variable BASE + STEP * I is
3304 known to not overflow: i.e. when the number of iterations is small
3305 enough with respect to the step and initial condition in order to
3306 keep the evolution confined in TYPEs bounds. Return true when the
3307 iv is known to overflow or when the property is not computable.
3308
3309 USE_OVERFLOW_SEMANTICS is true if this function should assume that
3310 the rules for overflow of the given language apply (e.g., that signed
3311 arithmetics in C does not overflow). */
3312
3313 bool
3314 scev_probably_wraps_p (tree base, tree step,
3315 gimple at_stmt, struct loop *loop,
3316 bool use_overflow_semantics)
3317 {
3318 struct nb_iter_bound *bound;
3319 tree delta, step_abs;
3320 tree unsigned_type, valid_niter;
3321 tree type = TREE_TYPE (step);
3322
3323 /* FIXME: We really need something like
3324 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
3325
3326 We used to test for the following situation that frequently appears
3327 during address arithmetics:
3328
3329 D.1621_13 = (long unsigned intD.4) D.1620_12;
3330 D.1622_14 = D.1621_13 * 8;
3331 D.1623_15 = (doubleD.29 *) D.1622_14;
3332
3333 And derived that the sequence corresponding to D_14
3334 can be proved to not wrap because it is used for computing a
3335 memory access; however, this is not really the case -- for example,
3336 if D_12 = (unsigned char) [254,+,1], then D_14 has values
3337 2032, 2040, 0, 8, ..., but the code is still legal. */
3338
3339 if (chrec_contains_undetermined (base)
3340 || chrec_contains_undetermined (step))
3341 return true;
3342
3343 if (integer_zerop (step))
3344 return false;
3345
3346 /* If we can use the fact that signed and pointer arithmetics does not
3347 wrap, we are done. */
3348 if (use_overflow_semantics && nowrap_type_p (TREE_TYPE (base)))
3349 return false;
3350
3351 /* To be able to use estimates on number of iterations of the loop,
3352 we must have an upper bound on the absolute value of the step. */
3353 if (TREE_CODE (step) != INTEGER_CST)
3354 return true;
3355
3356 /* Don't issue signed overflow warnings. */
3357 fold_defer_overflow_warnings ();
3358
3359 /* Otherwise, compute the number of iterations before we reach the
3360 bound of the type, and verify that the loop is exited before this
3361 occurs. */
3362 unsigned_type = unsigned_type_for (type);
3363 base = fold_convert (unsigned_type, base);
3364
3365 if (tree_int_cst_sign_bit (step))
3366 {
3367 tree extreme = fold_convert (unsigned_type,
3368 lower_bound_in_type (type, type));
3369 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
3370 step_abs = fold_build1 (NEGATE_EXPR, unsigned_type,
3371 fold_convert (unsigned_type, step));
3372 }
3373 else
3374 {
3375 tree extreme = fold_convert (unsigned_type,
3376 upper_bound_in_type (type, type));
3377 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
3378 step_abs = fold_convert (unsigned_type, step);
3379 }
3380
3381 valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
3382
3383 estimate_numbers_of_iterations_loop (loop);
3384 for (bound = loop->bounds; bound; bound = bound->next)
3385 {
3386 if (n_of_executions_at_most (at_stmt, bound, valid_niter))
3387 {
3388 fold_undefer_and_ignore_overflow_warnings ();
3389 return false;
3390 }
3391 }
3392
3393 fold_undefer_and_ignore_overflow_warnings ();
3394
3395 /* At this point we still don't have a proof that the iv does not
3396 overflow: give up. */
3397 return true;
3398 }
3399
3400 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
3401
3402 void
3403 free_numbers_of_iterations_estimates_loop (struct loop *loop)
3404 {
3405 struct nb_iter_bound *bound, *next;
3406
3407 loop->nb_iterations = NULL;
3408 loop->estimate_state = EST_NOT_COMPUTED;
3409 for (bound = loop->bounds; bound; bound = next)
3410 {
3411 next = bound->next;
3412 ggc_free (bound);
3413 }
3414
3415 loop->bounds = NULL;
3416 }
3417
3418 /* Frees the information on upper bounds on numbers of iterations of loops. */
3419
3420 void
3421 free_numbers_of_iterations_estimates (void)
3422 {
3423 loop_iterator li;
3424 struct loop *loop;
3425
3426 FOR_EACH_LOOP (li, loop, 0)
3427 {
3428 free_numbers_of_iterations_estimates_loop (loop);
3429 }
3430 }
3431
3432 /* Substitute value VAL for ssa name NAME inside expressions held
3433 at LOOP. */
3434
3435 void
3436 substitute_in_loop_info (struct loop *loop, tree name, tree val)
3437 {
3438 loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);
3439 }