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