1 /* Functions to determine/estimate number of iterations of a loop.
2 Copyright (C) 2004, 2005 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
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
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
23 #include "coretypes.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
31 #include "diagnostic.h"
33 #include "tree-flow.h"
34 #include "tree-dump.h"
36 #include "tree-pass.h"
38 #include "tree-chrec.h"
39 #include "tree-scalar-evolution.h"
40 #include "tree-data-ref.h"
44 #include "tree-inline.h"
46 #define SWAP(X, Y) do { void *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
51 Analysis of number of iterations of an affine exit test.
55 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
58 inverse (tree x, tree mask)
60 tree type = TREE_TYPE (x);
62 unsigned ctr = tree_floor_log2 (mask);
64 if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT)
66 unsigned HOST_WIDE_INT ix;
67 unsigned HOST_WIDE_INT imask;
68 unsigned HOST_WIDE_INT irslt = 1;
70 gcc_assert (cst_and_fits_in_hwi (x));
71 gcc_assert (cst_and_fits_in_hwi (mask));
73 ix = int_cst_value (x);
74 imask = int_cst_value (mask);
83 rslt = build_int_cst_type (type, irslt);
87 rslt = build_int_cst (type, 1);
90 rslt = int_const_binop (MULT_EXPR, rslt, x, 0);
91 x = int_const_binop (MULT_EXPR, x, x, 0);
93 rslt = int_const_binop (BIT_AND_EXPR, rslt, mask, 0);
99 /* Determines number of iterations of loop whose ending condition
100 is IV <> FINAL. TYPE is the type of the iv. The number of
101 iterations is stored to NITER. NEVER_INFINITE is true if
102 we know that the exit must be taken eventually, i.e., that the IV
103 ever reaches the value FINAL (we derived this earlier, and possibly set
104 NITER->assumptions to make sure this is the case). */
107 number_of_iterations_ne (tree type, affine_iv *iv, tree final,
108 struct tree_niter_desc *niter, bool never_infinite)
110 tree niter_type = unsigned_type_for (type);
111 tree s, c, d, bits, assumption, tmp, bound;
113 niter->control = *iv;
114 niter->bound = final;
115 niter->cmp = NE_EXPR;
117 /* Rearrange the terms so that we get inequality s * i <> c, with s
118 positive. Also cast everything to the unsigned type. */
119 if (tree_int_cst_sign_bit (iv->step))
121 s = fold_convert (niter_type,
122 fold_build1 (NEGATE_EXPR, type, iv->step));
123 c = fold_build2 (MINUS_EXPR, niter_type,
124 fold_convert (niter_type, iv->base),
125 fold_convert (niter_type, final));
129 s = fold_convert (niter_type, iv->step);
130 c = fold_build2 (MINUS_EXPR, niter_type,
131 fold_convert (niter_type, final),
132 fold_convert (niter_type, iv->base));
135 /* First the trivial cases -- when the step is 1. */
136 if (integer_onep (s))
142 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
143 is infinite. Otherwise, the number of iterations is
144 (inverse(s/d) * (c/d)) mod (size of mode/d). */
145 bits = num_ending_zeros (s);
146 bound = build_low_bits_mask (niter_type,
147 (TYPE_PRECISION (niter_type)
148 - tree_low_cst (bits, 1)));
150 d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
151 build_int_cst (niter_type, 1), bits);
152 s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
156 /* If we cannot assume that the loop is not infinite, record the
157 assumptions for divisibility of c. */
158 assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d);
159 assumption = fold_build2 (EQ_EXPR, boolean_type_node,
160 assumption, build_int_cst (niter_type, 0));
161 if (!integer_nonzerop (assumption))
162 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
163 niter->assumptions, assumption);
166 c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d);
167 tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound));
168 niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound);
172 /* Checks whether we can determine the final value of the control variable
173 of the loop with ending condition IV0 < IV1 (computed in TYPE).
174 DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
175 of the step. The assumptions necessary to ensure that the computation
176 of the final value does not overflow are recorded in NITER. If we
177 find the final value, we adjust DELTA and return TRUE. Otherwise
181 number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1,
182 struct tree_niter_desc *niter,
183 tree *delta, tree step)
185 tree niter_type = TREE_TYPE (step);
186 tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step);
188 tree assumption = boolean_true_node, bound, noloop;
190 if (TREE_CODE (mod) != INTEGER_CST)
192 if (integer_nonzerop (mod))
193 mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
194 tmod = fold_convert (type, mod);
196 if (nonnull_and_integer_nonzerop (iv0->step))
198 /* The final value of the iv is iv1->base + MOD, assuming that this
199 computation does not overflow, and that
200 iv0->base <= iv1->base + MOD. */
201 if (!iv1->no_overflow && !integer_zerop (mod))
203 bound = fold_build2 (MINUS_EXPR, type,
204 TYPE_MAX_VALUE (type), tmod);
205 assumption = fold_build2 (LE_EXPR, boolean_type_node,
207 if (integer_zerop (assumption))
210 noloop = fold_build2 (GT_EXPR, boolean_type_node,
212 fold_build2 (PLUS_EXPR, type,
217 /* The final value of the iv is iv0->base - MOD, assuming that this
218 computation does not overflow, and that
219 iv0->base - MOD <= iv1->base. */
220 if (!iv0->no_overflow && !integer_zerop (mod))
222 bound = fold_build2 (PLUS_EXPR, type,
223 TYPE_MIN_VALUE (type), tmod);
224 assumption = fold_build2 (GE_EXPR, boolean_type_node,
226 if (integer_zerop (assumption))
229 noloop = fold_build2 (GT_EXPR, boolean_type_node,
230 fold_build2 (MINUS_EXPR, type,
235 if (!integer_nonzerop (assumption))
236 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
239 if (!integer_zerop (noloop))
240 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
243 *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod);
247 /* Add assertions to NITER that ensure that the control variable of the loop
248 with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
249 are TYPE. Returns false if we can prove that there is an overflow, true
250 otherwise. STEP is the absolute value of the step. */
253 assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
254 struct tree_niter_desc *niter, tree step)
256 tree bound, d, assumption, diff;
257 tree niter_type = TREE_TYPE (step);
259 if (nonnull_and_integer_nonzerop (iv0->step))
261 /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
262 if (iv0->no_overflow)
265 /* If iv0->base is a constant, we can determine the last value before
266 overflow precisely; otherwise we conservatively assume
269 if (TREE_CODE (iv0->base) == INTEGER_CST)
271 d = fold_build2 (MINUS_EXPR, niter_type,
272 fold_convert (niter_type, TYPE_MAX_VALUE (type)),
273 fold_convert (niter_type, iv0->base));
274 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
277 diff = fold_build2 (MINUS_EXPR, niter_type, step,
278 build_int_cst (niter_type, 1));
279 bound = fold_build2 (MINUS_EXPR, type,
280 TYPE_MAX_VALUE (type), fold_convert (type, diff));
281 assumption = fold_build2 (LE_EXPR, boolean_type_node,
286 /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
287 if (iv1->no_overflow)
290 if (TREE_CODE (iv1->base) == INTEGER_CST)
292 d = fold_build2 (MINUS_EXPR, niter_type,
293 fold_convert (niter_type, iv1->base),
294 fold_convert (niter_type, TYPE_MIN_VALUE (type)));
295 diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
298 diff = fold_build2 (MINUS_EXPR, niter_type, step,
299 build_int_cst (niter_type, 1));
300 bound = fold_build2 (PLUS_EXPR, type,
301 TYPE_MIN_VALUE (type), fold_convert (type, diff));
302 assumption = fold_build2 (GE_EXPR, boolean_type_node,
306 if (integer_zerop (assumption))
308 if (!integer_nonzerop (assumption))
309 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
310 niter->assumptions, assumption);
312 iv0->no_overflow = true;
313 iv1->no_overflow = true;
317 /* Add an assumption to NITER that a loop whose ending condition
318 is IV0 < IV1 rolls. TYPE is the type of the control iv. */
321 assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
322 struct tree_niter_desc *niter)
324 tree assumption = boolean_true_node, bound, diff;
325 tree mbz, mbzl, mbzr;
327 if (nonnull_and_integer_nonzerop (iv0->step))
329 diff = fold_build2 (MINUS_EXPR, type,
330 iv0->step, build_int_cst (type, 1));
332 /* We need to know that iv0->base >= MIN + iv0->step - 1. Since
333 0 address never belongs to any object, we can assume this for
335 if (!POINTER_TYPE_P (type))
337 bound = fold_build2 (PLUS_EXPR, type,
338 TYPE_MIN_VALUE (type), diff);
339 assumption = fold_build2 (GE_EXPR, boolean_type_node,
343 /* And then we can compute iv0->base - diff, and compare it with
345 mbzl = fold_build2 (MINUS_EXPR, type, iv0->base, diff);
350 diff = fold_build2 (PLUS_EXPR, type,
351 iv1->step, build_int_cst (type, 1));
353 if (!POINTER_TYPE_P (type))
355 bound = fold_build2 (PLUS_EXPR, type,
356 TYPE_MAX_VALUE (type), diff);
357 assumption = fold_build2 (LE_EXPR, boolean_type_node,
362 mbzr = fold_build2 (MINUS_EXPR, type, iv1->base, diff);
365 mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr);
367 if (!integer_nonzerop (assumption))
368 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
369 niter->assumptions, assumption);
370 if (!integer_zerop (mbz))
371 niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
372 niter->may_be_zero, mbz);
375 /* Determines number of iterations of loop whose ending condition
376 is IV0 < IV1. TYPE is the type of the iv. The number of
377 iterations is stored to NITER. */
380 number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
381 struct tree_niter_desc *niter,
382 bool never_infinite ATTRIBUTE_UNUSED)
384 tree niter_type = unsigned_type_for (type);
387 if (nonnull_and_integer_nonzerop (iv0->step))
389 niter->control = *iv0;
390 niter->cmp = LT_EXPR;
391 niter->bound = iv1->base;
395 niter->control = *iv1;
396 niter->cmp = GT_EXPR;
397 niter->bound = iv0->base;
400 delta = fold_build2 (MINUS_EXPR, niter_type,
401 fold_convert (niter_type, iv1->base),
402 fold_convert (niter_type, iv0->base));
404 /* First handle the special case that the step is +-1. */
405 if ((iv0->step && integer_onep (iv0->step)
406 && null_or_integer_zerop (iv1->step))
407 || (iv1->step && integer_all_onesp (iv1->step)
408 && null_or_integer_zerop (iv0->step)))
410 /* for (i = iv0->base; i < iv1->base; i++)
414 for (i = iv1->base; i > iv0->base; i--).
416 In both cases # of iterations is iv1->base - iv0->base, assuming that
417 iv1->base >= iv0->base. */
418 niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
419 iv1->base, iv0->base);
420 niter->niter = delta;
424 if (nonnull_and_integer_nonzerop (iv0->step))
425 step = fold_convert (niter_type, iv0->step);
427 step = fold_convert (niter_type,
428 fold_build1 (NEGATE_EXPR, type, iv1->step));
430 /* If we can determine the final value of the control iv exactly, we can
431 transform the condition to != comparison. In particular, this will be
432 the case if DELTA is constant. */
433 if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step))
437 zps.base = build_int_cst (niter_type, 0);
439 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
440 zps does not overflow. */
441 zps.no_overflow = true;
443 return number_of_iterations_ne (type, &zps, delta, niter, true);
446 /* Make sure that the control iv does not overflow. */
447 if (!assert_no_overflow_lt (type, iv0, iv1, niter, step))
450 /* We determine the number of iterations as (delta + step - 1) / step. For
451 this to work, we must know that iv1->base >= iv0->base - step + 1,
452 otherwise the loop does not roll. */
453 assert_loop_rolls_lt (type, iv0, iv1, niter);
455 s = fold_build2 (MINUS_EXPR, niter_type,
456 step, build_int_cst (niter_type, 1));
457 delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
458 niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
462 /* Determines number of iterations of loop whose ending condition
463 is IV0 <= IV1. TYPE is the type of the iv. The number of
464 iterations is stored to NITER. NEVER_INFINITE is true if
465 we know that this condition must eventually become false (we derived this
466 earlier, and possibly set NITER->assumptions to make sure this
470 number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1,
471 struct tree_niter_desc *niter, bool never_infinite)
475 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
476 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
477 value of the type. This we must know anyway, since if it is
478 equal to this value, the loop rolls forever. */
482 if (nonnull_and_integer_nonzerop (iv0->step))
483 assumption = fold_build2 (NE_EXPR, boolean_type_node,
484 iv1->base, TYPE_MAX_VALUE (type));
486 assumption = fold_build2 (NE_EXPR, boolean_type_node,
487 iv0->base, TYPE_MIN_VALUE (type));
489 if (integer_zerop (assumption))
491 if (!integer_nonzerop (assumption))
492 niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
493 niter->assumptions, assumption);
496 if (nonnull_and_integer_nonzerop (iv0->step))
497 iv1->base = fold_build2 (PLUS_EXPR, type,
498 iv1->base, build_int_cst (type, 1));
500 iv0->base = fold_build2 (MINUS_EXPR, type,
501 iv0->base, build_int_cst (type, 1));
502 return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite);
505 /* Determine the number of iterations according to condition (for staying
506 inside loop) which compares two induction variables using comparison
507 operator CODE. The induction variable on left side of the comparison
508 is IV0, the right-hand side is IV1. Both induction variables must have
509 type TYPE, which must be an integer or pointer type. The steps of the
510 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
512 ONLY_EXIT is true if we are sure this is the only way the loop could be
513 exited (including possibly non-returning function calls, exceptions, etc.)
514 -- in this case we can use the information whether the control induction
515 variables can overflow or not in a more efficient way.
517 The results (number of iterations and assumptions as described in
518 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
519 Returns false if it fails to determine number of iterations, true if it
520 was determined (possibly with some assumptions). */
523 number_of_iterations_cond (tree type, affine_iv *iv0, enum tree_code code,
524 affine_iv *iv1, struct tree_niter_desc *niter,
529 /* The meaning of these assumptions is this:
531 then the rest of information does not have to be valid
532 if may_be_zero then the loop does not roll, even if
534 niter->assumptions = boolean_true_node;
535 niter->may_be_zero = boolean_false_node;
536 niter->niter = NULL_TREE;
537 niter->additional_info = boolean_true_node;
539 niter->bound = NULL_TREE;
540 niter->cmp = ERROR_MARK;
542 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
543 the control variable is on lhs. */
544 if (code == GE_EXPR || code == GT_EXPR
545 || (code == NE_EXPR && null_or_integer_zerop (iv0->step)))
548 code = swap_tree_comparison (code);
553 /* If this is not the only possible exit from the loop, the information
554 that the induction variables cannot overflow as derived from
555 signedness analysis cannot be relied upon. We use them e.g. in the
556 following way: given loop for (i = 0; i <= n; i++), if i is
557 signed, it cannot overflow, thus this loop is equivalent to
558 for (i = 0; i < n + 1; i++); however, if n == MAX, but the loop
559 is exited in some other way before i overflows, this transformation
560 is incorrect (the new loop exits immediately). */
561 iv0->no_overflow = false;
562 iv1->no_overflow = false;
565 if (POINTER_TYPE_P (type))
567 /* Comparison of pointers is undefined unless both iv0 and iv1 point
568 to the same object. If they do, the control variable cannot wrap
569 (as wrap around the bounds of memory will never return a pointer
570 that would be guaranteed to point to the same object, even if we
571 avoid undefined behavior by casting to size_t and back). The
572 restrictions on pointer arithmetics and comparisons of pointers
573 ensure that using the no-overflow assumptions is correct in this
574 case even if ONLY_EXIT is false. */
575 iv0->no_overflow = true;
576 iv1->no_overflow = true;
579 /* If the control induction variable does not overflow, the loop obviously
580 cannot be infinite. */
581 if (!null_or_integer_zerop (iv0->step) && iv0->no_overflow)
582 never_infinite = true;
583 else if (!null_or_integer_zerop (iv1->step) && iv1->no_overflow)
584 never_infinite = true;
586 never_infinite = false;
588 /* We can handle the case when neither of the sides of the comparison is
589 invariant, provided that the test is NE_EXPR. This rarely occurs in
590 practice, but it is simple enough to manage. */
591 if (!null_or_integer_zerop (iv0->step) && !null_or_integer_zerop (iv1->step))
596 iv0->step = fold_binary_to_constant (MINUS_EXPR, type,
597 iv0->step, iv1->step);
598 iv0->no_overflow = false;
599 iv1->step = NULL_TREE;
600 iv1->no_overflow = true;
603 /* If the result of the comparison is a constant, the loop is weird. More
604 precise handling would be possible, but the situation is not common enough
605 to waste time on it. */
606 if (null_or_integer_zerop (iv0->step) && null_or_integer_zerop (iv1->step))
609 /* Ignore loops of while (i-- < 10) type. */
612 if (iv0->step && tree_int_cst_sign_bit (iv0->step))
615 if (!null_or_integer_zerop (iv1->step) && !tree_int_cst_sign_bit (iv1->step))
619 /* If the loop exits immediately, there is nothing to do. */
620 if (integer_zerop (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
622 niter->niter = build_int_cst (unsigned_type_for (type), 0);
626 /* OK, now we know we have a senseful loop. Handle several cases, depending
627 on what comparison operator is used. */
631 gcc_assert (null_or_integer_zerop (iv1->step));
632 return number_of_iterations_ne (type, iv0, iv1->base, niter, never_infinite);
634 return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite);
636 return number_of_iterations_le (type, iv0, iv1, niter, never_infinite);
642 /* Substitute NEW for OLD in EXPR and fold the result. */
645 simplify_replace_tree (tree expr, tree old, tree new)
648 tree ret = NULL_TREE, e, se;
654 || operand_equal_p (expr, old, 0))
655 return unshare_expr (new);
657 if (!EXPR_P (expr) && !GIMPLE_STMT_P (expr))
660 n = TREE_CODE_LENGTH (TREE_CODE (expr));
661 for (i = 0; i < n; i++)
663 e = TREE_OPERAND (expr, i);
664 se = simplify_replace_tree (e, old, new);
669 ret = copy_node (expr);
671 TREE_OPERAND (ret, i) = se;
674 return (ret ? fold (ret) : expr);
677 /* Expand definitions of ssa names in EXPR as long as they are simple
678 enough, and return the new expression. */
681 expand_simple_operations (tree expr)
684 tree ret = NULL_TREE, e, ee, stmt;
687 if (expr == NULL_TREE)
690 if (is_gimple_min_invariant (expr))
693 code = TREE_CODE (expr);
694 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
696 n = TREE_CODE_LENGTH (code);
697 for (i = 0; i < n; i++)
699 e = TREE_OPERAND (expr, i);
700 ee = expand_simple_operations (e);
705 ret = copy_node (expr);
707 TREE_OPERAND (ret, i) = ee;
710 return (ret ? fold (ret) : expr);
713 if (TREE_CODE (expr) != SSA_NAME)
716 stmt = SSA_NAME_DEF_STMT (expr);
717 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
720 e = GIMPLE_STMT_OPERAND (stmt, 1);
721 if (/* Casts are simple. */
722 TREE_CODE (e) != NOP_EXPR
723 && TREE_CODE (e) != CONVERT_EXPR
724 /* Copies are simple. */
725 && TREE_CODE (e) != SSA_NAME
726 /* Assignments of invariants are simple. */
727 && !is_gimple_min_invariant (e)
728 /* And increments and decrements by a constant are simple. */
729 && !((TREE_CODE (e) == PLUS_EXPR
730 || TREE_CODE (e) == MINUS_EXPR)
731 && is_gimple_min_invariant (TREE_OPERAND (e, 1))))
734 return expand_simple_operations (e);
737 /* Tries to simplify EXPR using the condition COND. Returns the simplified
738 expression (or EXPR unchanged, if no simplification was possible). */
741 tree_simplify_using_condition_1 (tree cond, tree expr)
744 tree e, te, e0, e1, e2, notcond;
745 enum tree_code code = TREE_CODE (expr);
747 if (code == INTEGER_CST)
750 if (code == TRUTH_OR_EXPR
751 || code == TRUTH_AND_EXPR
752 || code == COND_EXPR)
756 e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0));
757 if (TREE_OPERAND (expr, 0) != e0)
760 e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1));
761 if (TREE_OPERAND (expr, 1) != e1)
764 if (code == COND_EXPR)
766 e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2));
767 if (TREE_OPERAND (expr, 2) != e2)
775 if (code == COND_EXPR)
776 expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
778 expr = fold_build2 (code, boolean_type_node, e0, e1);
784 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
785 propagation, and vice versa. Fold does not handle this, since it is
786 considered too expensive. */
787 if (TREE_CODE (cond) == EQ_EXPR)
789 e0 = TREE_OPERAND (cond, 0);
790 e1 = TREE_OPERAND (cond, 1);
792 /* We know that e0 == e1. Check whether we cannot simplify expr
794 e = simplify_replace_tree (expr, e0, e1);
795 if (integer_zerop (e) || integer_nonzerop (e))
798 e = simplify_replace_tree (expr, e1, e0);
799 if (integer_zerop (e) || integer_nonzerop (e))
802 if (TREE_CODE (expr) == EQ_EXPR)
804 e0 = TREE_OPERAND (expr, 0);
805 e1 = TREE_OPERAND (expr, 1);
807 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
808 e = simplify_replace_tree (cond, e0, e1);
809 if (integer_zerop (e))
811 e = simplify_replace_tree (cond, e1, e0);
812 if (integer_zerop (e))
815 if (TREE_CODE (expr) == NE_EXPR)
817 e0 = TREE_OPERAND (expr, 0);
818 e1 = TREE_OPERAND (expr, 1);
820 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
821 e = simplify_replace_tree (cond, e0, e1);
822 if (integer_zerop (e))
823 return boolean_true_node;
824 e = simplify_replace_tree (cond, e1, e0);
825 if (integer_zerop (e))
826 return boolean_true_node;
829 te = expand_simple_operations (expr);
831 /* Check whether COND ==> EXPR. */
832 notcond = invert_truthvalue (cond);
833 e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te);
834 if (e && integer_nonzerop (e))
837 /* Check whether COND ==> not EXPR. */
838 e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te);
839 if (e && integer_zerop (e))
845 /* Tries to simplify EXPR using the condition COND. Returns the simplified
846 expression (or EXPR unchanged, if no simplification was possible).
847 Wrapper around tree_simplify_using_condition_1 that ensures that chains
848 of simple operations in definitions of ssa names in COND are expanded,
849 so that things like casts or incrementing the value of the bound before
850 the loop do not cause us to fail. */
853 tree_simplify_using_condition (tree cond, tree expr)
855 cond = expand_simple_operations (cond);
857 return tree_simplify_using_condition_1 (cond, expr);
860 /* The maximum number of dominator BBs we search for conditions
861 of loop header copies we use for simplifying a conditional
863 #define MAX_DOMINATORS_TO_WALK 8
865 /* Tries to simplify EXPR using the conditions on entry to LOOP.
866 Record the conditions used for simplification to CONDS_USED.
867 Returns the simplified expression (or EXPR unchanged, if no
868 simplification was possible).*/
871 simplify_using_initial_conditions (struct loop *loop, tree expr,
879 if (TREE_CODE (expr) == INTEGER_CST)
882 /* Limit walking the dominators to avoid quadraticness in
883 the number of BBs times the number of loops in degenerate
885 for (bb = loop->header;
886 bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK;
887 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
889 if (!single_pred_p (bb))
891 e = single_pred_edge (bb);
893 if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
896 cond = COND_EXPR_COND (last_stmt (e->src));
897 if (e->flags & EDGE_FALSE_VALUE)
898 cond = invert_truthvalue (cond);
899 exp = tree_simplify_using_condition (cond, expr);
902 *conds_used = fold_build2 (TRUTH_AND_EXPR,
914 /* Tries to simplify EXPR using the evolutions of the loop invariants
915 in the superloops of LOOP. Returns the simplified expression
916 (or EXPR unchanged, if no simplification was possible). */
919 simplify_using_outer_evolutions (struct loop *loop, tree expr)
921 enum tree_code code = TREE_CODE (expr);
925 if (is_gimple_min_invariant (expr))
928 if (code == TRUTH_OR_EXPR
929 || code == TRUTH_AND_EXPR
930 || code == COND_EXPR)
934 e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
935 if (TREE_OPERAND (expr, 0) != e0)
938 e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
939 if (TREE_OPERAND (expr, 1) != e1)
942 if (code == COND_EXPR)
944 e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
945 if (TREE_OPERAND (expr, 2) != e2)
953 if (code == COND_EXPR)
954 expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
956 expr = fold_build2 (code, boolean_type_node, e0, e1);
962 e = instantiate_parameters (loop, expr);
963 if (is_gimple_min_invariant (e))
969 /* Returns true if EXIT is the only possible exit from LOOP. */
972 loop_only_exit_p (struct loop *loop, edge exit)
975 block_stmt_iterator bsi;
979 if (exit != single_exit (loop))
982 body = get_loop_body (loop);
983 for (i = 0; i < loop->num_nodes; i++)
985 for (bsi = bsi_start (body[0]); !bsi_end_p (bsi); bsi_next (&bsi))
987 call = get_call_expr_in (bsi_stmt (bsi));
988 if (call && TREE_SIDE_EFFECTS (call))
1000 /* Stores description of number of iterations of LOOP derived from
1001 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
1002 useful information could be derived (and fields of NITER has
1003 meaning described in comments at struct tree_niter_desc
1004 declaration), false otherwise. If WARN is true and
1005 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1006 potentially unsafe assumptions. */
1009 number_of_iterations_exit (struct loop *loop, edge exit,
1010 struct tree_niter_desc *niter,
1013 tree stmt, cond, type;
1015 enum tree_code code;
1018 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
1021 niter->assumptions = boolean_false_node;
1022 stmt = last_stmt (exit->src);
1023 if (!stmt || TREE_CODE (stmt) != COND_EXPR)
1026 /* We want the condition for staying inside loop. */
1027 cond = COND_EXPR_COND (stmt);
1028 if (exit->flags & EDGE_TRUE_VALUE)
1029 cond = invert_truthvalue (cond);
1031 code = TREE_CODE (cond);
1045 op0 = TREE_OPERAND (cond, 0);
1046 op1 = TREE_OPERAND (cond, 1);
1047 type = TREE_TYPE (op0);
1049 if (TREE_CODE (type) != INTEGER_TYPE
1050 && !POINTER_TYPE_P (type))
1053 if (!simple_iv (loop, stmt, op0, &iv0, false))
1055 if (!simple_iv (loop, stmt, op1, &iv1, false))
1058 iv0.base = expand_simple_operations (iv0.base);
1059 iv1.base = expand_simple_operations (iv1.base);
1060 if (!number_of_iterations_cond (type, &iv0, code, &iv1, niter,
1061 loop_only_exit_p (loop, exit)))
1066 niter->assumptions = simplify_using_outer_evolutions (loop,
1067 niter->assumptions);
1068 niter->may_be_zero = simplify_using_outer_evolutions (loop,
1069 niter->may_be_zero);
1070 niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
1073 niter->additional_info = boolean_true_node;
1075 = simplify_using_initial_conditions (loop,
1077 &niter->additional_info);
1079 = simplify_using_initial_conditions (loop,
1081 &niter->additional_info);
1083 if (integer_onep (niter->assumptions))
1086 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1087 But if we can prove that there is overflow or some other source of weird
1088 behavior, ignore the loop even with -funsafe-loop-optimizations. */
1089 if (integer_zerop (niter->assumptions))
1092 if (flag_unsafe_loop_optimizations)
1093 niter->assumptions = boolean_true_node;
1097 const char *wording;
1098 location_t loc = EXPR_LOCATION (stmt);
1100 /* We can provide a more specific warning if one of the operator is
1101 constant and the other advances by +1 or -1. */
1102 if (!null_or_integer_zerop (iv1.step)
1103 ? (null_or_integer_zerop (iv0.step)
1104 && (integer_onep (iv1.step) || integer_all_onesp (iv1.step)))
1106 && (integer_onep (iv0.step) || integer_all_onesp (iv0.step))))
1108 flag_unsafe_loop_optimizations
1109 ? N_("assuming that the loop is not infinite")
1110 : N_("cannot optimize possibly infinite loops");
1113 flag_unsafe_loop_optimizations
1114 ? N_("assuming that the loop counter does not overflow")
1115 : N_("cannot optimize loop, the loop counter may overflow");
1117 if (LOCATION_LINE (loc) > 0)
1118 warning (OPT_Wunsafe_loop_optimizations, "%H%s", &loc, gettext (wording));
1120 warning (OPT_Wunsafe_loop_optimizations, "%s", gettext (wording));
1123 return flag_unsafe_loop_optimizations;
1126 /* Try to determine the number of iterations of LOOP. If we succeed,
1127 expression giving number of iterations is returned and *EXIT is
1128 set to the edge from that the information is obtained. Otherwise
1129 chrec_dont_know is returned. */
1132 find_loop_niter (struct loop *loop, edge *exit)
1135 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1137 tree niter = NULL_TREE, aniter;
1138 struct tree_niter_desc desc;
1141 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
1143 if (!just_once_each_iteration_p (loop, ex->src))
1146 if (!number_of_iterations_exit (loop, ex, &desc, false))
1149 if (integer_nonzerop (desc.may_be_zero))
1151 /* We exit in the first iteration through this exit.
1152 We won't find anything better. */
1153 niter = build_int_cst (unsigned_type_node, 0);
1158 if (!integer_zerop (desc.may_be_zero))
1161 aniter = desc.niter;
1165 /* Nothing recorded yet. */
1171 /* Prefer constants, the lower the better. */
1172 if (TREE_CODE (aniter) != INTEGER_CST)
1175 if (TREE_CODE (niter) != INTEGER_CST)
1182 if (tree_int_cst_lt (aniter, niter))
1189 VEC_free (edge, heap, exits);
1191 return niter ? niter : chrec_dont_know;
1196 Analysis of a number of iterations of a loop by a brute-force evaluation.
1200 /* Bound on the number of iterations we try to evaluate. */
1202 #define MAX_ITERATIONS_TO_TRACK \
1203 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
1205 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
1206 result by a chain of operations such that all but exactly one of their
1207 operands are constants. */
1210 chain_of_csts_start (struct loop *loop, tree x)
1212 tree stmt = SSA_NAME_DEF_STMT (x);
1214 basic_block bb = bb_for_stmt (stmt);
1217 || !flow_bb_inside_loop_p (loop, bb))
1220 if (TREE_CODE (stmt) == PHI_NODE)
1222 if (bb == loop->header)
1228 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
1231 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
1233 if (SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF) == NULL_DEF_OPERAND_P)
1236 use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
1237 if (use == NULL_USE_OPERAND_P)
1240 return chain_of_csts_start (loop, use);
1243 /* Determines whether the expression X is derived from a result of a phi node
1244 in header of LOOP such that
1246 * the derivation of X consists only from operations with constants
1247 * the initial value of the phi node is constant
1248 * the value of the phi node in the next iteration can be derived from the
1249 value in the current iteration by a chain of operations with constants.
1251 If such phi node exists, it is returned. If X is a constant, X is returned
1252 unchanged. Otherwise NULL_TREE is returned. */
1255 get_base_for (struct loop *loop, tree x)
1257 tree phi, init, next;
1259 if (is_gimple_min_invariant (x))
1262 phi = chain_of_csts_start (loop, x);
1266 init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1267 next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
1269 if (TREE_CODE (next) != SSA_NAME)
1272 if (!is_gimple_min_invariant (init))
1275 if (chain_of_csts_start (loop, next) != phi)
1281 /* Given an expression X, then
1283 * if X is NULL_TREE, we return the constant BASE.
1284 * otherwise X is a SSA name, whose value in the considered loop is derived
1285 by a chain of operations with constant from a result of a phi node in
1286 the header of the loop. Then we return value of X when the value of the
1287 result of this phi node is given by the constant BASE. */
1290 get_val_for (tree x, tree base)
1296 gcc_assert (is_gimple_min_invariant (base));
1301 stmt = SSA_NAME_DEF_STMT (x);
1302 if (TREE_CODE (stmt) == PHI_NODE)
1305 FOR_EACH_SSA_USE_OPERAND (op, stmt, iter, SSA_OP_USE)
1307 nx = USE_FROM_PTR (op);
1308 val = get_val_for (nx, base);
1310 val = fold (GIMPLE_STMT_OPERAND (stmt, 1));
1312 /* only iterate loop once. */
1316 /* Should never reach here. */
1320 /* Tries to count the number of iterations of LOOP till it exits by EXIT
1321 by brute force -- i.e. by determining the value of the operands of the
1322 condition at EXIT in first few iterations of the loop (assuming that
1323 these values are constant) and determining the first one in that the
1324 condition is not satisfied. Returns the constant giving the number
1325 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
1328 loop_niter_by_eval (struct loop *loop, edge exit)
1330 tree cond, cnd, acnd;
1331 tree op[2], val[2], next[2], aval[2], phi[2];
1335 cond = last_stmt (exit->src);
1336 if (!cond || TREE_CODE (cond) != COND_EXPR)
1337 return chrec_dont_know;
1339 cnd = COND_EXPR_COND (cond);
1340 if (exit->flags & EDGE_TRUE_VALUE)
1341 cnd = invert_truthvalue (cnd);
1343 cmp = TREE_CODE (cnd);
1352 for (j = 0; j < 2; j++)
1353 op[j] = TREE_OPERAND (cnd, j);
1357 return chrec_dont_know;
1360 for (j = 0; j < 2; j++)
1362 phi[j] = get_base_for (loop, op[j]);
1364 return chrec_dont_know;
1367 for (j = 0; j < 2; j++)
1369 if (TREE_CODE (phi[j]) == PHI_NODE)
1371 val[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_preheader_edge (loop));
1372 next[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_latch_edge (loop));
1377 next[j] = NULL_TREE;
1382 for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
1384 for (j = 0; j < 2; j++)
1385 aval[j] = get_val_for (op[j], val[j]);
1387 acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]);
1388 if (acnd && integer_zerop (acnd))
1390 if (dump_file && (dump_flags & TDF_DETAILS))
1392 "Proved that loop %d iterates %d times using brute force.\n",
1394 return build_int_cst (unsigned_type_node, i);
1397 for (j = 0; j < 2; j++)
1399 val[j] = get_val_for (next[j], val[j]);
1400 if (!is_gimple_min_invariant (val[j]))
1401 return chrec_dont_know;
1405 return chrec_dont_know;
1408 /* Finds the exit of the LOOP by that the loop exits after a constant
1409 number of iterations and stores the exit edge to *EXIT. The constant
1410 giving the number of iterations of LOOP is returned. The number of
1411 iterations is determined using loop_niter_by_eval (i.e. by brute force
1412 evaluation). If we are unable to find the exit for that loop_niter_by_eval
1413 determines the number of iterations, chrec_dont_know is returned. */
1416 find_loop_niter_by_eval (struct loop *loop, edge *exit)
1419 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
1421 tree niter = NULL_TREE, aniter;
1424 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
1426 if (!just_once_each_iteration_p (loop, ex->src))
1429 aniter = loop_niter_by_eval (loop, ex);
1430 if (chrec_contains_undetermined (aniter))
1434 && !tree_int_cst_lt (aniter, niter))
1440 VEC_free (edge, heap, exits);
1442 return niter ? niter : chrec_dont_know;
1447 Analysis of upper bounds on number of iterations of a loop.
1451 /* Returns true if we can prove that COND ==> VAL >= 0. */
1454 implies_nonnegative_p (tree cond, tree val)
1456 tree type = TREE_TYPE (val);
1459 if (tree_expr_nonnegative_p (val))
1462 if (integer_nonzerop (cond))
1465 compare = fold_build2 (GE_EXPR,
1466 boolean_type_node, val, build_int_cst (type, 0));
1467 compare = tree_simplify_using_condition_1 (cond, compare);
1469 return integer_nonzerop (compare);
1472 /* Returns true if we can prove that COND ==> A >= B. */
1475 implies_ge_p (tree cond, tree a, tree b)
1477 tree compare = fold_build2 (GE_EXPR, boolean_type_node, a, b);
1479 if (integer_nonzerop (compare))
1482 if (integer_nonzerop (cond))
1485 compare = tree_simplify_using_condition_1 (cond, compare);
1487 return integer_nonzerop (compare);
1490 /* Returns a constant upper bound on the value of expression VAL. VAL
1491 is considered to be unsigned. If its type is signed, its value must
1494 The condition ADDITIONAL must be satisfied (for example, if VAL is
1495 "(unsigned) n" and ADDITIONAL is "n > 0", then we can derive that
1496 VAL is at most (unsigned) MAX_INT). */
1499 derive_constant_upper_bound (tree val, tree additional)
1501 tree type = TREE_TYPE (val);
1502 tree op0, op1, subtype, maxt;
1503 double_int bnd, max, mmax, cst;
1506 if (INTEGRAL_TYPE_P (type))
1507 maxt = TYPE_MAX_VALUE (type);
1509 maxt = upper_bound_in_type (type, type);
1511 max = tree_to_double_int (maxt);
1513 switch (TREE_CODE (val))
1516 return tree_to_double_int (val);
1520 op0 = TREE_OPERAND (val, 0);
1521 subtype = TREE_TYPE (op0);
1522 if (!TYPE_UNSIGNED (subtype)
1523 /* If TYPE is also signed, the fact that VAL is nonnegative implies
1524 that OP0 is nonnegative. */
1525 && TYPE_UNSIGNED (type)
1526 && !implies_nonnegative_p (additional, op0))
1528 /* If we cannot prove that the casted expression is nonnegative,
1529 we cannot establish more useful upper bound than the precision
1530 of the type gives us. */
1534 /* We now know that op0 is an nonnegative value. Try deriving an upper
1536 bnd = derive_constant_upper_bound (op0, additional);
1538 /* If the bound does not fit in TYPE, max. value of TYPE could be
1540 if (double_int_ucmp (max, bnd) < 0)
1547 op0 = TREE_OPERAND (val, 0);
1548 op1 = TREE_OPERAND (val, 1);
1550 if (TREE_CODE (op1) != INTEGER_CST
1551 || !implies_nonnegative_p (additional, op0))
1554 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
1555 choose the most logical way how to treat this constant regardless
1556 of the signedness of the type. */
1557 cst = tree_to_double_int (op1);
1558 cst = double_int_sext (cst, TYPE_PRECISION (type));
1559 if (TREE_CODE (val) == PLUS_EXPR)
1560 cst = double_int_neg (cst);
1562 bnd = derive_constant_upper_bound (op0, additional);
1564 if (double_int_negative_p (cst))
1566 cst = double_int_neg (cst);
1567 /* Avoid CST == 0x80000... */
1568 if (double_int_negative_p (cst))
1571 /* OP0 + CST. We need to check that
1572 BND <= MAX (type) - CST. */
1574 mmax = double_int_add (max, double_int_neg (cst));
1575 if (double_int_ucmp (bnd, mmax) > 0)
1578 return double_int_add (bnd, cst);
1582 /* OP0 - CST, where CST >= 0.
1584 If TYPE is signed, we have already verified that OP0 >= 0, and we
1585 know that the result is nonnegative. This implies that
1588 If TYPE is unsigned, we must additionally know that OP0 >= CST,
1589 otherwise the operation underflows.
1592 /* This should only happen if the type is unsigned; however, for
1593 programs that use overflowing signed arithmetics even with
1594 -fno-wrapv, this condition may also be true for signed values. */
1595 if (double_int_ucmp (bnd, cst) < 0)
1598 if (TYPE_UNSIGNED (type)
1599 && !implies_ge_p (additional,
1600 op0, double_int_to_tree (type, cst)))
1603 bnd = double_int_add (bnd, double_int_neg (cst));
1608 case FLOOR_DIV_EXPR:
1609 case EXACT_DIV_EXPR:
1610 op0 = TREE_OPERAND (val, 0);
1611 op1 = TREE_OPERAND (val, 1);
1612 if (TREE_CODE (op1) != INTEGER_CST
1613 || tree_int_cst_sign_bit (op1))
1616 bnd = derive_constant_upper_bound (op0, additional);
1617 return double_int_udiv (bnd, tree_to_double_int (op1), FLOOR_DIV_EXPR);
1620 op1 = TREE_OPERAND (val, 1);
1621 if (TREE_CODE (op1) != INTEGER_CST
1622 || tree_int_cst_sign_bit (op1))
1624 return tree_to_double_int (op1);
1627 stmt = SSA_NAME_DEF_STMT (val);
1628 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT
1629 || GIMPLE_STMT_OPERAND (stmt, 0) != val)
1631 return derive_constant_upper_bound (GIMPLE_STMT_OPERAND (stmt, 1),
1639 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. The
1640 additional condition ADDITIONAL is recorded with the bound. IS_EXIT
1641 is true if the loop is exited immediately after STMT, and this exit
1642 is taken at last when the STMT is executed BOUND + 1 times.
1643 REALISTIC is true if the estimate comes from a reliable source
1644 (number of iterations analysis, or size of data accessed in the loop). */
1647 record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt,
1648 bool is_exit, bool realistic)
1650 struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound));
1651 double_int i_bound = derive_constant_upper_bound (bound, additional);
1653 if (dump_file && (dump_flags & TDF_DETAILS))
1655 fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : "");
1656 print_generic_expr (dump_file, at_stmt, TDF_SLIM);
1657 fprintf (dump_file, " is executed at most ");
1658 print_generic_expr (dump_file, bound, TDF_SLIM);
1659 fprintf (dump_file, " (bounded by ");
1660 dump_double_int (dump_file, i_bound, true);
1661 fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num);
1664 elt->bound = i_bound;
1665 elt->stmt = at_stmt;
1666 elt->is_exit = is_exit;
1667 elt->realistic = realistic && TREE_CODE (bound) == INTEGER_CST;
1668 elt->next = loop->bounds;
1672 /* Record the estimate on number of iterations of LOOP based on the fact that
1673 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
1674 its values belong to the range <LOW, HIGH>. DATA_SIZE_BOUNDS_P is true if
1675 LOW and HIGH are derived from the size of data. */
1678 record_nonwrapping_iv (struct loop *loop, tree base, tree step, tree stmt,
1679 tree low, tree high, bool data_size_bounds_p)
1681 tree niter_bound, extreme, delta;
1682 tree type = TREE_TYPE (base), unsigned_type;
1684 if (TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
1687 if (dump_file && (dump_flags & TDF_DETAILS))
1689 fprintf (dump_file, "Induction variable (");
1690 print_generic_expr (dump_file, TREE_TYPE (base), TDF_SLIM);
1691 fprintf (dump_file, ") ");
1692 print_generic_expr (dump_file, base, TDF_SLIM);
1693 fprintf (dump_file, " + ");
1694 print_generic_expr (dump_file, step, TDF_SLIM);
1695 fprintf (dump_file, " * iteration does not wrap in statement ");
1696 print_generic_expr (dump_file, stmt, TDF_SLIM);
1697 fprintf (dump_file, " in loop %d.\n", loop->num);
1700 unsigned_type = unsigned_type_for (type);
1701 base = fold_convert (unsigned_type, base);
1702 step = fold_convert (unsigned_type, step);
1704 if (tree_int_cst_sign_bit (step))
1706 extreme = fold_convert (unsigned_type, low);
1707 if (TREE_CODE (base) != INTEGER_CST)
1708 base = fold_convert (unsigned_type, high);
1709 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
1710 step = fold_build1 (NEGATE_EXPR, unsigned_type, step);
1714 extreme = fold_convert (unsigned_type, high);
1715 if (TREE_CODE (base) != INTEGER_CST)
1716 base = fold_convert (unsigned_type, low);
1717 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
1720 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
1721 would get out of the range. */
1722 niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step);
1723 record_estimate (loop, niter_bound, boolean_true_node, stmt,
1724 false, data_size_bounds_p);
1727 /* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe
1728 approximation of the number of iterations for LOOP. */
1731 compute_estimated_nb_iterations (struct loop *loop)
1733 struct nb_iter_bound *bound;
1735 gcc_assert (loop->estimate_state == EST_NOT_AVAILABLE);
1737 for (bound = loop->bounds; bound; bound = bound->next)
1739 if (!bound->realistic)
1742 /* Update only when there is no previous estimation, or when the current
1743 estimation is smaller. */
1744 if (loop->estimate_state == EST_NOT_AVAILABLE
1745 || double_int_ucmp (bound->bound, loop->estimated_nb_iterations) < 0)
1747 loop->estimate_state = EST_AVAILABLE;
1748 loop->estimated_nb_iterations = bound->bound;
1753 /* Determine information about number of iterations a LOOP from the index
1754 IDX of a data reference accessed in STMT. Callback for for_each_index. */
1763 idx_infer_loop_bounds (tree base, tree *idx, void *dta)
1765 struct ilb_data *data = dta;
1766 tree ev, init, step;
1767 tree low, high, type, next;
1769 struct loop *loop = data->loop;
1771 if (TREE_CODE (base) != ARRAY_REF)
1774 ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx));
1775 init = initial_condition (ev);
1776 step = evolution_part_in_loop_num (ev, loop->num);
1780 || TREE_CODE (step) != INTEGER_CST
1781 || integer_zerop (step)
1782 || tree_contains_chrecs (init, NULL)
1783 || chrec_contains_symbols_defined_in_loop (init, loop->num))
1786 low = array_ref_low_bound (base);
1787 high = array_ref_up_bound (base);
1789 /* The case of nonconstant bounds could be handled, but it would be
1791 if (TREE_CODE (low) != INTEGER_CST
1793 || TREE_CODE (high) != INTEGER_CST)
1795 sign = tree_int_cst_sign_bit (step);
1796 type = TREE_TYPE (step);
1798 /* In case the relevant bound of the array does not fit in type, or
1799 it does, but bound + step (in type) still belongs into the range of the
1800 array, the index may wrap and still stay within the range of the array
1801 (consider e.g. if the array is indexed by the full range of
1804 To make things simpler, we require both bounds to fit into type, although
1805 there are cases where this would not be strictly necessary. */
1806 if (!int_fits_type_p (high, type)
1807 || !int_fits_type_p (low, type))
1809 low = fold_convert (type, low);
1810 high = fold_convert (type, high);
1813 next = fold_binary (PLUS_EXPR, type, low, step);
1815 next = fold_binary (PLUS_EXPR, type, high, step);
1817 if (tree_int_cst_compare (low, next) <= 0
1818 && tree_int_cst_compare (next, high) <= 0)
1821 record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true);
1825 /* Determine information about number of iterations a LOOP from the bounds
1826 of arrays in the data reference REF accessed in STMT. */
1829 infer_loop_bounds_from_ref (struct loop *loop, tree stmt, tree ref)
1831 struct ilb_data data;
1835 for_each_index (&ref, idx_infer_loop_bounds, &data);
1838 /* Determine information about number of iterations of a LOOP from the way
1839 arrays are used in STMT. */
1842 infer_loop_bounds_from_array (struct loop *loop, tree stmt)
1846 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
1848 tree op0 = GIMPLE_STMT_OPERAND (stmt, 0);
1849 tree op1 = GIMPLE_STMT_OPERAND (stmt, 1);
1851 /* For each memory access, analyze its access function
1852 and record a bound on the loop iteration domain. */
1853 if (REFERENCE_CLASS_P (op0))
1854 infer_loop_bounds_from_ref (loop, stmt, op0);
1856 if (REFERENCE_CLASS_P (op1))
1857 infer_loop_bounds_from_ref (loop, stmt, op1);
1861 call = get_call_expr_in (stmt);
1866 for (args = TREE_OPERAND (call, 1); args; args = TREE_CHAIN (args))
1867 if (REFERENCE_CLASS_P (TREE_VALUE (args)))
1868 infer_loop_bounds_from_ref (loop, stmt, TREE_VALUE (args));
1872 /* Determine information about number of iterations of a LOOP from the fact
1873 that signed arithmetics in STMT does not overflow. */
1876 infer_loop_bounds_from_signedness (struct loop *loop, tree stmt)
1878 tree def, base, step, scev, type, low, high;
1880 if (flag_wrapv || TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
1883 def = GIMPLE_STMT_OPERAND (stmt, 0);
1885 if (TREE_CODE (def) != SSA_NAME)
1888 type = TREE_TYPE (def);
1889 if (!INTEGRAL_TYPE_P (type)
1890 || TYPE_UNSIGNED (type))
1893 scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
1894 if (chrec_contains_undetermined (scev))
1897 base = initial_condition_in_loop_num (scev, loop->num);
1898 step = evolution_part_in_loop_num (scev, loop->num);
1901 || TREE_CODE (step) != INTEGER_CST
1902 || tree_contains_chrecs (base, NULL)
1903 || chrec_contains_symbols_defined_in_loop (base, loop->num))
1906 low = lower_bound_in_type (type, type);
1907 high = upper_bound_in_type (type, type);
1909 record_nonwrapping_iv (loop, base, step, stmt, low, high, false);
1912 /* The following analyzers are extracting informations on the bounds
1913 of LOOP from the following undefined behaviors:
1915 - data references should not access elements over the statically
1918 - signed variables should not overflow when flag_wrapv is not set.
1922 infer_loop_bounds_from_undefined (struct loop *loop)
1926 block_stmt_iterator bsi;
1929 bbs = get_loop_body (loop);
1931 for (i = 0; i < loop->num_nodes; i++)
1935 /* If BB is not executed in each iteration of the loop, we cannot
1936 use it to infer any information about # of iterations of the loop. */
1937 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1940 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1942 tree stmt = bsi_stmt (bsi);
1944 infer_loop_bounds_from_array (loop, stmt);
1945 infer_loop_bounds_from_signedness (loop, stmt);
1953 /* Records estimates on numbers of iterations of LOOP. */
1956 estimate_numbers_of_iterations_loop (struct loop *loop)
1958 VEC (edge, heap) *exits;
1961 struct tree_niter_desc niter_desc;
1964 /* Give up if we already have tried to compute an estimation. */
1965 if (loop->estimate_state != EST_NOT_COMPUTED)
1967 loop->estimate_state = EST_NOT_AVAILABLE;
1969 exits = get_loop_exit_edges (loop);
1970 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
1972 if (!number_of_iterations_exit (loop, ex, &niter_desc, false))
1975 niter = niter_desc.niter;
1976 type = TREE_TYPE (niter);
1977 if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST)
1978 niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
1979 build_int_cst (type, 0),
1981 record_estimate (loop, niter,
1982 niter_desc.additional_info,
1983 last_stmt (ex->src),
1986 VEC_free (edge, heap, exits);
1988 infer_loop_bounds_from_undefined (loop);
1989 compute_estimated_nb_iterations (loop);
1992 /* Records estimates on numbers of iterations of loops. */
1995 estimate_numbers_of_iterations (void)
2000 FOR_EACH_LOOP (li, loop, 0)
2002 estimate_numbers_of_iterations_loop (loop);
2006 /* Returns true if statement S1 dominates statement S2. */
2009 stmt_dominates_stmt_p (tree s1, tree s2)
2011 basic_block bb1 = bb_for_stmt (s1), bb2 = bb_for_stmt (s2);
2019 block_stmt_iterator bsi;
2021 for (bsi = bsi_start (bb1); bsi_stmt (bsi) != s2; bsi_next (&bsi))
2022 if (bsi_stmt (bsi) == s1)
2028 return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
2031 /* Returns true when we can prove that the number of executions of
2032 STMT in the loop is at most NITER, according to the bound on
2033 the number of executions of the statement NITER_BOUND->stmt recorded in
2034 NITER_BOUND. If STMT is NULL, we must prove this bound for all
2035 statements in the loop. */
2038 n_of_executions_at_most (tree stmt,
2039 struct nb_iter_bound *niter_bound,
2042 double_int bound = niter_bound->bound;
2043 tree nit_type = TREE_TYPE (niter), e;
2046 gcc_assert (TYPE_UNSIGNED (nit_type));
2048 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
2049 the number of iterations is small. */
2050 if (!double_int_fits_to_tree_p (nit_type, bound))
2053 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
2054 times. This means that:
2056 -- if NITER_BOUND->is_exit is true, then everything before
2057 NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
2058 times, and everything after it at most NITER_BOUND->bound times.
2060 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
2061 is executed, then NITER_BOUND->stmt is executed as well in the same
2062 iteration (we conclude that if both statements belong to the same
2063 basic block, or if STMT is after NITER_BOUND->stmt), then STMT
2064 is executed at most NITER_BOUND->bound + 1 times. Otherwise STMT is
2065 executed at most NITER_BOUND->bound + 2 times. */
2067 if (niter_bound->is_exit)
2070 && stmt != niter_bound->stmt
2071 && stmt_dominates_stmt_p (niter_bound->stmt, stmt))
2079 || (bb_for_stmt (stmt) != bb_for_stmt (niter_bound->stmt)
2080 && !stmt_dominates_stmt_p (niter_bound->stmt, stmt)))
2082 bound = double_int_add (bound, double_int_one);
2083 if (double_int_zero_p (bound)
2084 || !double_int_fits_to_tree_p (nit_type, bound))
2090 e = fold_binary (cmp, boolean_type_node,
2091 niter, double_int_to_tree (nit_type, bound));
2092 return e && integer_nonzerop (e);
2095 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
2098 nowrap_type_p (tree type)
2101 && INTEGRAL_TYPE_P (type)
2102 && !TYPE_UNSIGNED (type))
2105 if (POINTER_TYPE_P (type))
2111 /* Return false only when the induction variable BASE + STEP * I is
2112 known to not overflow: i.e. when the number of iterations is small
2113 enough with respect to the step and initial condition in order to
2114 keep the evolution confined in TYPEs bounds. Return true when the
2115 iv is known to overflow or when the property is not computable.
2117 USE_OVERFLOW_SEMANTICS is true if this function should assume that
2118 the rules for overflow of the given language apply (e.g., that signed
2119 arithmetics in C does not overflow). */
2122 scev_probably_wraps_p (tree base, tree step,
2123 tree at_stmt, struct loop *loop,
2124 bool use_overflow_semantics)
2126 struct nb_iter_bound *bound;
2127 tree delta, step_abs;
2128 tree unsigned_type, valid_niter;
2129 tree type = TREE_TYPE (step);
2131 /* FIXME: We really need something like
2132 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
2134 We used to test for the following situation that frequently appears
2135 during address arithmetics:
2137 D.1621_13 = (long unsigned intD.4) D.1620_12;
2138 D.1622_14 = D.1621_13 * 8;
2139 D.1623_15 = (doubleD.29 *) D.1622_14;
2141 And derived that the sequence corresponding to D_14
2142 can be proved to not wrap because it is used for computing a
2143 memory access; however, this is not really the case -- for example,
2144 if D_12 = (unsigned char) [254,+,1], then D_14 has values
2145 2032, 2040, 0, 8, ..., but the code is still legal. */
2147 if (chrec_contains_undetermined (base)
2148 || chrec_contains_undetermined (step)
2149 || TREE_CODE (step) != INTEGER_CST)
2152 if (integer_zerop (step))
2155 /* If we can use the fact that signed and pointer arithmetics does not
2156 wrap, we are done. */
2157 if (use_overflow_semantics && nowrap_type_p (type))
2160 /* Otherwise, compute the number of iterations before we reach the
2161 bound of the type, and verify that the loop is exited before this
2163 unsigned_type = unsigned_type_for (type);
2164 base = fold_convert (unsigned_type, base);
2166 if (tree_int_cst_sign_bit (step))
2168 tree extreme = fold_convert (unsigned_type,
2169 lower_bound_in_type (type, type));
2170 delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
2171 step_abs = fold_build1 (NEGATE_EXPR, unsigned_type,
2172 fold_convert (unsigned_type, step));
2176 tree extreme = fold_convert (unsigned_type,
2177 upper_bound_in_type (type, type));
2178 delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
2179 step_abs = fold_convert (unsigned_type, step);
2182 valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
2184 estimate_numbers_of_iterations_loop (loop);
2185 for (bound = loop->bounds; bound; bound = bound->next)
2186 if (n_of_executions_at_most (at_stmt, bound, valid_niter))
2189 /* At this point we still don't have a proof that the iv does not
2190 overflow: give up. */
2194 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
2197 free_numbers_of_iterations_estimates_loop (struct loop *loop)
2199 struct nb_iter_bound *bound, *next;
2201 loop->nb_iterations = NULL;
2202 loop->estimate_state = EST_NOT_COMPUTED;
2203 for (bound = loop->bounds; bound; bound = next)
2209 loop->bounds = NULL;
2212 /* Frees the information on upper bounds on numbers of iterations of loops. */
2215 free_numbers_of_iterations_estimates (void)
2220 FOR_EACH_LOOP (li, loop, 0)
2222 free_numbers_of_iterations_estimates_loop (loop);
2226 /* Substitute value VAL for ssa name NAME inside expressions held
2230 substitute_in_loop_info (struct loop *loop, tree name, tree val)
2232 loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);