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