1 /* Functions to determine/estimate number of iterations of a loop.
2 Copyright (C) 2004, 2005, 2006, 2007 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 (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 (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 (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 (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 ((integer_onep (iv0
->step
) && integer_zerop (iv1
->step
))
406 || (integer_all_onesp (iv1
->step
) && integer_zerop (iv0
->step
)))
408 /* for (i = iv0->base; i < iv1->base; i++)
412 for (i = iv1->base; i > iv0->base; i--).
414 In both cases # of iterations is iv1->base - iv0->base, assuming that
415 iv1->base >= iv0->base. */
416 niter
->may_be_zero
= fold_build2 (LT_EXPR
, boolean_type_node
,
417 iv1
->base
, iv0
->base
);
418 niter
->niter
= delta
;
422 if (integer_nonzerop (iv0
->step
))
423 step
= fold_convert (niter_type
, iv0
->step
);
425 step
= fold_convert (niter_type
,
426 fold_build1 (NEGATE_EXPR
, type
, iv1
->step
));
428 /* If we can determine the final value of the control iv exactly, we can
429 transform the condition to != comparison. In particular, this will be
430 the case if DELTA is constant. */
431 if (number_of_iterations_lt_to_ne (type
, iv0
, iv1
, niter
, &delta
, step
))
435 zps
.base
= build_int_cst (niter_type
, 0);
437 /* number_of_iterations_lt_to_ne will add assumptions that ensure that
438 zps does not overflow. */
439 zps
.no_overflow
= true;
441 return number_of_iterations_ne (type
, &zps
, delta
, niter
, true);
444 /* Make sure that the control iv does not overflow. */
445 if (!assert_no_overflow_lt (type
, iv0
, iv1
, niter
, step
))
448 /* We determine the number of iterations as (delta + step - 1) / step. For
449 this to work, we must know that iv1->base >= iv0->base - step + 1,
450 otherwise the loop does not roll. */
451 assert_loop_rolls_lt (type
, iv0
, iv1
, niter
);
453 s
= fold_build2 (MINUS_EXPR
, niter_type
,
454 step
, build_int_cst (niter_type
, 1));
455 delta
= fold_build2 (PLUS_EXPR
, niter_type
, delta
, s
);
456 niter
->niter
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, delta
, step
);
460 /* Determines number of iterations of loop whose ending condition
461 is IV0 <= IV1. TYPE is the type of the iv. The number of
462 iterations is stored to NITER. NEVER_INFINITE is true if
463 we know that this condition must eventually become false (we derived this
464 earlier, and possibly set NITER->assumptions to make sure this
468 number_of_iterations_le (tree type
, affine_iv
*iv0
, affine_iv
*iv1
,
469 struct tree_niter_desc
*niter
, bool never_infinite
)
473 /* Say that IV0 is the control variable. Then IV0 <= IV1 iff
474 IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
475 value of the type. This we must know anyway, since if it is
476 equal to this value, the loop rolls forever. */
480 if (integer_nonzerop (iv0
->step
))
481 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
482 iv1
->base
, TYPE_MAX_VALUE (type
));
484 assumption
= fold_build2 (NE_EXPR
, boolean_type_node
,
485 iv0
->base
, TYPE_MIN_VALUE (type
));
487 if (integer_zerop (assumption
))
489 if (!integer_nonzerop (assumption
))
490 niter
->assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
491 niter
->assumptions
, assumption
);
494 if (integer_nonzerop (iv0
->step
))
495 iv1
->base
= fold_build2 (PLUS_EXPR
, type
,
496 iv1
->base
, build_int_cst (type
, 1));
498 iv0
->base
= fold_build2 (MINUS_EXPR
, type
,
499 iv0
->base
, build_int_cst (type
, 1));
500 return number_of_iterations_lt (type
, iv0
, iv1
, niter
, never_infinite
);
503 /* Determine the number of iterations according to condition (for staying
504 inside loop) which compares two induction variables using comparison
505 operator CODE. The induction variable on left side of the comparison
506 is IV0, the right-hand side is IV1. Both induction variables must have
507 type TYPE, which must be an integer or pointer type. The steps of the
508 ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
510 ONLY_EXIT is true if we are sure this is the only way the loop could be
511 exited (including possibly non-returning function calls, exceptions, etc.)
512 -- in this case we can use the information whether the control induction
513 variables can overflow or not in a more efficient way.
515 The results (number of iterations and assumptions as described in
516 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
517 Returns false if it fails to determine number of iterations, true if it
518 was determined (possibly with some assumptions). */
521 number_of_iterations_cond (tree type
, affine_iv
*iv0
, enum tree_code code
,
522 affine_iv
*iv1
, struct tree_niter_desc
*niter
,
527 /* The meaning of these assumptions is this:
529 then the rest of information does not have to be valid
530 if may_be_zero then the loop does not roll, even if
532 niter
->assumptions
= boolean_true_node
;
533 niter
->may_be_zero
= boolean_false_node
;
534 niter
->niter
= NULL_TREE
;
535 niter
->additional_info
= boolean_true_node
;
537 niter
->bound
= NULL_TREE
;
538 niter
->cmp
= ERROR_MARK
;
540 /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
541 the control variable is on lhs. */
542 if (code
== GE_EXPR
|| code
== GT_EXPR
543 || (code
== NE_EXPR
&& integer_zerop (iv0
->step
)))
546 code
= swap_tree_comparison (code
);
551 /* If this is not the only possible exit from the loop, the information
552 that the induction variables cannot overflow as derived from
553 signedness analysis cannot be relied upon. We use them e.g. in the
554 following way: given loop for (i = 0; i <= n; i++), if i is
555 signed, it cannot overflow, thus this loop is equivalent to
556 for (i = 0; i < n + 1; i++); however, if n == MAX, but the loop
557 is exited in some other way before i overflows, this transformation
558 is incorrect (the new loop exits immediately). */
559 iv0
->no_overflow
= false;
560 iv1
->no_overflow
= false;
563 if (POINTER_TYPE_P (type
))
565 /* Comparison of pointers is undefined unless both iv0 and iv1 point
566 to the same object. If they do, the control variable cannot wrap
567 (as wrap around the bounds of memory will never return a pointer
568 that would be guaranteed to point to the same object, even if we
569 avoid undefined behavior by casting to size_t and back). The
570 restrictions on pointer arithmetics and comparisons of pointers
571 ensure that using the no-overflow assumptions is correct in this
572 case even if ONLY_EXIT is false. */
573 iv0
->no_overflow
= true;
574 iv1
->no_overflow
= true;
577 /* If the control induction variable does not overflow, the loop obviously
578 cannot be infinite. */
579 if (!integer_zerop (iv0
->step
) && iv0
->no_overflow
)
580 never_infinite
= true;
581 else if (!integer_zerop (iv1
->step
) && iv1
->no_overflow
)
582 never_infinite
= true;
584 never_infinite
= false;
586 /* We can handle the case when neither of the sides of the comparison is
587 invariant, provided that the test is NE_EXPR. This rarely occurs in
588 practice, but it is simple enough to manage. */
589 if (!integer_zerop (iv0
->step
) && !integer_zerop (iv1
->step
))
594 iv0
->step
= fold_binary_to_constant (MINUS_EXPR
, type
,
595 iv0
->step
, iv1
->step
);
596 iv0
->no_overflow
= false;
597 iv1
->step
= build_int_cst (type
, 0);
598 iv1
->no_overflow
= true;
601 /* If the result of the comparison is a constant, the loop is weird. More
602 precise handling would be possible, but the situation is not common enough
603 to waste time on it. */
604 if (integer_zerop (iv0
->step
) && integer_zerop (iv1
->step
))
607 /* Ignore loops of while (i-- < 10) type. */
610 if (iv0
->step
&& tree_int_cst_sign_bit (iv0
->step
))
613 if (!integer_zerop (iv1
->step
) && !tree_int_cst_sign_bit (iv1
->step
))
617 /* If the loop exits immediately, there is nothing to do. */
618 if (integer_zerop (fold_build2 (code
, boolean_type_node
, iv0
->base
, iv1
->base
)))
620 niter
->niter
= build_int_cst (unsigned_type_for (type
), 0);
624 /* OK, now we know we have a senseful loop. Handle several cases, depending
625 on what comparison operator is used. */
629 gcc_assert (integer_zerop (iv1
->step
));
630 return number_of_iterations_ne (type
, iv0
, iv1
->base
, niter
, never_infinite
);
632 return number_of_iterations_lt (type
, iv0
, iv1
, niter
, never_infinite
);
634 return number_of_iterations_le (type
, iv0
, iv1
, niter
, never_infinite
);
640 /* Substitute NEW for OLD in EXPR and fold the result. */
643 simplify_replace_tree (tree expr
, tree old
, tree
new)
646 tree ret
= NULL_TREE
, e
, se
;
652 || operand_equal_p (expr
, old
, 0))
653 return unshare_expr (new);
655 if (!EXPR_P (expr
) && !GIMPLE_STMT_P (expr
))
658 n
= TREE_CODE_LENGTH (TREE_CODE (expr
));
659 for (i
= 0; i
< n
; i
++)
661 e
= TREE_OPERAND (expr
, i
);
662 se
= simplify_replace_tree (e
, old
, new);
667 ret
= copy_node (expr
);
669 TREE_OPERAND (ret
, i
) = se
;
672 return (ret
? fold (ret
) : expr
);
675 /* Expand definitions of ssa names in EXPR as long as they are simple
676 enough, and return the new expression. */
679 expand_simple_operations (tree expr
)
682 tree ret
= NULL_TREE
, e
, ee
, stmt
;
685 if (expr
== NULL_TREE
)
688 if (is_gimple_min_invariant (expr
))
691 code
= TREE_CODE (expr
);
692 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
694 n
= TREE_CODE_LENGTH (code
);
695 for (i
= 0; i
< n
; i
++)
697 e
= TREE_OPERAND (expr
, i
);
698 ee
= expand_simple_operations (e
);
703 ret
= copy_node (expr
);
705 TREE_OPERAND (ret
, i
) = ee
;
711 fold_defer_overflow_warnings ();
713 fold_undefer_and_ignore_overflow_warnings ();
717 if (TREE_CODE (expr
) != SSA_NAME
)
720 stmt
= SSA_NAME_DEF_STMT (expr
);
721 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
724 e
= GIMPLE_STMT_OPERAND (stmt
, 1);
725 if (/* Casts are simple. */
726 TREE_CODE (e
) != NOP_EXPR
727 && TREE_CODE (e
) != CONVERT_EXPR
728 /* Copies are simple. */
729 && TREE_CODE (e
) != SSA_NAME
730 /* Assignments of invariants are simple. */
731 && !is_gimple_min_invariant (e
)
732 /* And increments and decrements by a constant are simple. */
733 && !((TREE_CODE (e
) == PLUS_EXPR
734 || TREE_CODE (e
) == MINUS_EXPR
)
735 && is_gimple_min_invariant (TREE_OPERAND (e
, 1))))
738 return expand_simple_operations (e
);
741 /* Tries to simplify EXPR using the condition COND. Returns the simplified
742 expression (or EXPR unchanged, if no simplification was possible). */
745 tree_simplify_using_condition_1 (tree cond
, tree expr
)
748 tree e
, te
, e0
, e1
, e2
, notcond
;
749 enum tree_code code
= TREE_CODE (expr
);
751 if (code
== INTEGER_CST
)
754 if (code
== TRUTH_OR_EXPR
755 || code
== TRUTH_AND_EXPR
756 || code
== COND_EXPR
)
760 e0
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 0));
761 if (TREE_OPERAND (expr
, 0) != e0
)
764 e1
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 1));
765 if (TREE_OPERAND (expr
, 1) != e1
)
768 if (code
== COND_EXPR
)
770 e2
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 2));
771 if (TREE_OPERAND (expr
, 2) != e2
)
779 if (code
== COND_EXPR
)
780 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
782 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
788 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
789 propagation, and vice versa. Fold does not handle this, since it is
790 considered too expensive. */
791 if (TREE_CODE (cond
) == EQ_EXPR
)
793 e0
= TREE_OPERAND (cond
, 0);
794 e1
= TREE_OPERAND (cond
, 1);
796 /* We know that e0 == e1. Check whether we cannot simplify expr
798 e
= simplify_replace_tree (expr
, e0
, e1
);
799 if (integer_zerop (e
) || integer_nonzerop (e
))
802 e
= simplify_replace_tree (expr
, e1
, e0
);
803 if (integer_zerop (e
) || integer_nonzerop (e
))
806 if (TREE_CODE (expr
) == EQ_EXPR
)
808 e0
= TREE_OPERAND (expr
, 0);
809 e1
= TREE_OPERAND (expr
, 1);
811 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
812 e
= simplify_replace_tree (cond
, e0
, e1
);
813 if (integer_zerop (e
))
815 e
= simplify_replace_tree (cond
, e1
, e0
);
816 if (integer_zerop (e
))
819 if (TREE_CODE (expr
) == NE_EXPR
)
821 e0
= TREE_OPERAND (expr
, 0);
822 e1
= TREE_OPERAND (expr
, 1);
824 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
825 e
= simplify_replace_tree (cond
, e0
, e1
);
826 if (integer_zerop (e
))
827 return boolean_true_node
;
828 e
= simplify_replace_tree (cond
, e1
, e0
);
829 if (integer_zerop (e
))
830 return boolean_true_node
;
833 te
= expand_simple_operations (expr
);
835 /* Check whether COND ==> EXPR. */
836 notcond
= invert_truthvalue (cond
);
837 e
= fold_binary (TRUTH_OR_EXPR
, boolean_type_node
, notcond
, te
);
838 if (e
&& integer_nonzerop (e
))
841 /* Check whether COND ==> not EXPR. */
842 e
= fold_binary (TRUTH_AND_EXPR
, boolean_type_node
, cond
, te
);
843 if (e
&& integer_zerop (e
))
849 /* Tries to simplify EXPR using the condition COND. Returns the simplified
850 expression (or EXPR unchanged, if no simplification was possible).
851 Wrapper around tree_simplify_using_condition_1 that ensures that chains
852 of simple operations in definitions of ssa names in COND are expanded,
853 so that things like casts or incrementing the value of the bound before
854 the loop do not cause us to fail. */
857 tree_simplify_using_condition (tree cond
, tree expr
)
859 cond
= expand_simple_operations (cond
);
861 return tree_simplify_using_condition_1 (cond
, expr
);
864 /* The maximum number of dominator BBs we search for conditions
865 of loop header copies we use for simplifying a conditional
867 #define MAX_DOMINATORS_TO_WALK 8
869 /* Tries to simplify EXPR using the conditions on entry to LOOP.
870 Record the conditions used for simplification to CONDS_USED.
871 Returns the simplified expression (or EXPR unchanged, if no
872 simplification was possible).*/
875 simplify_using_initial_conditions (struct loop
*loop
, tree expr
,
883 if (TREE_CODE (expr
) == INTEGER_CST
)
886 /* Limit walking the dominators to avoid quadraticness in
887 the number of BBs times the number of loops in degenerate
889 for (bb
= loop
->header
;
890 bb
!= ENTRY_BLOCK_PTR
&& cnt
< MAX_DOMINATORS_TO_WALK
;
891 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
893 if (!single_pred_p (bb
))
895 e
= single_pred_edge (bb
);
897 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
900 cond
= COND_EXPR_COND (last_stmt (e
->src
));
901 if (e
->flags
& EDGE_FALSE_VALUE
)
902 cond
= invert_truthvalue (cond
);
903 exp
= tree_simplify_using_condition (cond
, expr
);
906 *conds_used
= fold_build2 (TRUTH_AND_EXPR
,
918 /* Tries to simplify EXPR using the evolutions of the loop invariants
919 in the superloops of LOOP. Returns the simplified expression
920 (or EXPR unchanged, if no simplification was possible). */
923 simplify_using_outer_evolutions (struct loop
*loop
, tree expr
)
925 enum tree_code code
= TREE_CODE (expr
);
929 if (is_gimple_min_invariant (expr
))
932 if (code
== TRUTH_OR_EXPR
933 || code
== TRUTH_AND_EXPR
934 || code
== COND_EXPR
)
938 e0
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 0));
939 if (TREE_OPERAND (expr
, 0) != e0
)
942 e1
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 1));
943 if (TREE_OPERAND (expr
, 1) != e1
)
946 if (code
== COND_EXPR
)
948 e2
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 2));
949 if (TREE_OPERAND (expr
, 2) != e2
)
957 if (code
== COND_EXPR
)
958 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
960 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
966 e
= instantiate_parameters (loop
, expr
);
967 if (is_gimple_min_invariant (e
))
973 /* Returns true if EXIT is the only possible exit from LOOP. */
976 loop_only_exit_p (struct loop
*loop
, edge exit
)
979 block_stmt_iterator bsi
;
983 if (exit
!= single_exit (loop
))
986 body
= get_loop_body (loop
);
987 for (i
= 0; i
< loop
->num_nodes
; i
++)
989 for (bsi
= bsi_start (body
[0]); !bsi_end_p (bsi
); bsi_next (&bsi
))
991 call
= get_call_expr_in (bsi_stmt (bsi
));
992 if (call
&& TREE_SIDE_EFFECTS (call
))
1004 /* Stores description of number of iterations of LOOP derived from
1005 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
1006 useful information could be derived (and fields of NITER has
1007 meaning described in comments at struct tree_niter_desc
1008 declaration), false otherwise. If WARN is true and
1009 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
1010 potentially unsafe assumptions. */
1013 number_of_iterations_exit (struct loop
*loop
, edge exit
,
1014 struct tree_niter_desc
*niter
,
1017 tree stmt
, cond
, type
;
1019 enum tree_code code
;
1022 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit
->src
))
1025 niter
->assumptions
= boolean_false_node
;
1026 stmt
= last_stmt (exit
->src
);
1027 if (!stmt
|| TREE_CODE (stmt
) != COND_EXPR
)
1030 /* We want the condition for staying inside loop. */
1031 cond
= COND_EXPR_COND (stmt
);
1032 if (exit
->flags
& EDGE_TRUE_VALUE
)
1033 cond
= invert_truthvalue (cond
);
1035 code
= TREE_CODE (cond
);
1049 op0
= TREE_OPERAND (cond
, 0);
1050 op1
= TREE_OPERAND (cond
, 1);
1051 type
= TREE_TYPE (op0
);
1053 if (TREE_CODE (type
) != INTEGER_TYPE
1054 && !POINTER_TYPE_P (type
))
1057 if (!simple_iv (loop
, stmt
, op0
, &iv0
, false))
1059 if (!simple_iv (loop
, stmt
, op1
, &iv1
, false))
1062 /* We don't want to see undefined signed overflow warnings while
1063 computing the nmber of iterations. */
1064 fold_defer_overflow_warnings ();
1066 iv0
.base
= expand_simple_operations (iv0
.base
);
1067 iv1
.base
= expand_simple_operations (iv1
.base
);
1068 if (!number_of_iterations_cond (type
, &iv0
, code
, &iv1
, niter
,
1069 loop_only_exit_p (loop
, exit
)))
1071 fold_undefer_and_ignore_overflow_warnings ();
1077 niter
->assumptions
= simplify_using_outer_evolutions (loop
,
1078 niter
->assumptions
);
1079 niter
->may_be_zero
= simplify_using_outer_evolutions (loop
,
1080 niter
->may_be_zero
);
1081 niter
->niter
= simplify_using_outer_evolutions (loop
, niter
->niter
);
1084 niter
->additional_info
= boolean_true_node
;
1086 = simplify_using_initial_conditions (loop
,
1088 &niter
->additional_info
);
1090 = simplify_using_initial_conditions (loop
,
1092 &niter
->additional_info
);
1094 fold_undefer_and_ignore_overflow_warnings ();
1096 if (integer_onep (niter
->assumptions
))
1099 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1100 But if we can prove that there is overflow or some other source of weird
1101 behavior, ignore the loop even with -funsafe-loop-optimizations. */
1102 if (integer_zerop (niter
->assumptions
))
1105 if (flag_unsafe_loop_optimizations
)
1106 niter
->assumptions
= boolean_true_node
;
1110 const char *wording
;
1111 location_t loc
= EXPR_LOCATION (stmt
);
1113 /* We can provide a more specific warning if one of the operator is
1114 constant and the other advances by +1 or -1. */
1115 if (!integer_zerop (iv1
.step
)
1116 ? (integer_zerop (iv0
.step
)
1117 && (integer_onep (iv1
.step
) || integer_all_onesp (iv1
.step
)))
1118 : (integer_onep (iv0
.step
) || integer_all_onesp (iv0
.step
)))
1120 flag_unsafe_loop_optimizations
1121 ? N_("assuming that the loop is not infinite")
1122 : N_("cannot optimize possibly infinite loops");
1125 flag_unsafe_loop_optimizations
1126 ? N_("assuming that the loop counter does not overflow")
1127 : N_("cannot optimize loop, the loop counter may overflow");
1129 if (LOCATION_LINE (loc
) > 0)
1130 warning (OPT_Wunsafe_loop_optimizations
, "%H%s", &loc
, gettext (wording
));
1132 warning (OPT_Wunsafe_loop_optimizations
, "%s", gettext (wording
));
1135 return flag_unsafe_loop_optimizations
;
1138 /* Try to determine the number of iterations of LOOP. If we succeed,
1139 expression giving number of iterations is returned and *EXIT is
1140 set to the edge from that the information is obtained. Otherwise
1141 chrec_dont_know is returned. */
1144 find_loop_niter (struct loop
*loop
, edge
*exit
)
1147 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
1149 tree niter
= NULL_TREE
, aniter
;
1150 struct tree_niter_desc desc
;
1153 for (i
= 0; VEC_iterate (edge
, exits
, i
, ex
); i
++)
1155 if (!just_once_each_iteration_p (loop
, ex
->src
))
1158 if (!number_of_iterations_exit (loop
, ex
, &desc
, false))
1161 if (integer_nonzerop (desc
.may_be_zero
))
1163 /* We exit in the first iteration through this exit.
1164 We won't find anything better. */
1165 niter
= build_int_cst (unsigned_type_node
, 0);
1170 if (!integer_zerop (desc
.may_be_zero
))
1173 aniter
= desc
.niter
;
1177 /* Nothing recorded yet. */
1183 /* Prefer constants, the lower the better. */
1184 if (TREE_CODE (aniter
) != INTEGER_CST
)
1187 if (TREE_CODE (niter
) != INTEGER_CST
)
1194 if (tree_int_cst_lt (aniter
, niter
))
1201 VEC_free (edge
, heap
, exits
);
1203 return niter
? niter
: chrec_dont_know
;
1208 Analysis of a number of iterations of a loop by a brute-force evaluation.
1212 /* Bound on the number of iterations we try to evaluate. */
1214 #define MAX_ITERATIONS_TO_TRACK \
1215 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
1217 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
1218 result by a chain of operations such that all but exactly one of their
1219 operands are constants. */
1222 chain_of_csts_start (struct loop
*loop
, tree x
)
1224 tree stmt
= SSA_NAME_DEF_STMT (x
);
1226 basic_block bb
= bb_for_stmt (stmt
);
1229 || !flow_bb_inside_loop_p (loop
, bb
))
1232 if (TREE_CODE (stmt
) == PHI_NODE
)
1234 if (bb
== loop
->header
)
1240 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
1243 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
1245 if (SINGLE_SSA_DEF_OPERAND (stmt
, SSA_OP_DEF
) == NULL_DEF_OPERAND_P
)
1248 use
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1249 if (use
== NULL_USE_OPERAND_P
)
1252 return chain_of_csts_start (loop
, use
);
1255 /* Determines whether the expression X is derived from a result of a phi node
1256 in header of LOOP such that
1258 * the derivation of X consists only from operations with constants
1259 * the initial value of the phi node is constant
1260 * the value of the phi node in the next iteration can be derived from the
1261 value in the current iteration by a chain of operations with constants.
1263 If such phi node exists, it is returned. If X is a constant, X is returned
1264 unchanged. Otherwise NULL_TREE is returned. */
1267 get_base_for (struct loop
*loop
, tree x
)
1269 tree phi
, init
, next
;
1271 if (is_gimple_min_invariant (x
))
1274 phi
= chain_of_csts_start (loop
, x
);
1278 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
1279 next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
1281 if (TREE_CODE (next
) != SSA_NAME
)
1284 if (!is_gimple_min_invariant (init
))
1287 if (chain_of_csts_start (loop
, next
) != phi
)
1293 /* Given an expression X, then
1295 * if X is NULL_TREE, we return the constant BASE.
1296 * otherwise X is a SSA name, whose value in the considered loop is derived
1297 by a chain of operations with constant from a result of a phi node in
1298 the header of the loop. Then we return value of X when the value of the
1299 result of this phi node is given by the constant BASE. */
1302 get_val_for (tree x
, tree base
)
1308 gcc_assert (is_gimple_min_invariant (base
));
1313 stmt
= SSA_NAME_DEF_STMT (x
);
1314 if (TREE_CODE (stmt
) == PHI_NODE
)
1317 FOR_EACH_SSA_USE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
1319 nx
= USE_FROM_PTR (op
);
1320 val
= get_val_for (nx
, base
);
1322 val
= fold (GIMPLE_STMT_OPERAND (stmt
, 1));
1324 /* only iterate loop once. */
1328 /* Should never reach here. */
1332 /* Tries to count the number of iterations of LOOP till it exits by EXIT
1333 by brute force -- i.e. by determining the value of the operands of the
1334 condition at EXIT in first few iterations of the loop (assuming that
1335 these values are constant) and determining the first one in that the
1336 condition is not satisfied. Returns the constant giving the number
1337 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
1340 loop_niter_by_eval (struct loop
*loop
, edge exit
)
1342 tree cond
, cnd
, acnd
;
1343 tree op
[2], val
[2], next
[2], aval
[2], phi
[2];
1347 cond
= last_stmt (exit
->src
);
1348 if (!cond
|| TREE_CODE (cond
) != COND_EXPR
)
1349 return chrec_dont_know
;
1351 cnd
= COND_EXPR_COND (cond
);
1352 if (exit
->flags
& EDGE_TRUE_VALUE
)
1353 cnd
= invert_truthvalue (cnd
);
1355 cmp
= TREE_CODE (cnd
);
1364 for (j
= 0; j
< 2; j
++)
1365 op
[j
] = TREE_OPERAND (cnd
, j
);
1369 return chrec_dont_know
;
1372 for (j
= 0; j
< 2; j
++)
1374 phi
[j
] = get_base_for (loop
, op
[j
]);
1376 return chrec_dont_know
;
1379 for (j
= 0; j
< 2; j
++)
1381 if (TREE_CODE (phi
[j
]) == PHI_NODE
)
1383 val
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
[j
], loop_preheader_edge (loop
));
1384 next
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
[j
], loop_latch_edge (loop
));
1389 next
[j
] = NULL_TREE
;
1394 /* Don't issue signed overflow warnings. */
1395 fold_defer_overflow_warnings ();
1397 for (i
= 0; i
< MAX_ITERATIONS_TO_TRACK
; i
++)
1399 for (j
= 0; j
< 2; j
++)
1400 aval
[j
] = get_val_for (op
[j
], val
[j
]);
1402 acnd
= fold_binary (cmp
, boolean_type_node
, aval
[0], aval
[1]);
1403 if (acnd
&& integer_zerop (acnd
))
1405 fold_undefer_and_ignore_overflow_warnings ();
1406 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1408 "Proved that loop %d iterates %d times using brute force.\n",
1410 return build_int_cst (unsigned_type_node
, i
);
1413 for (j
= 0; j
< 2; j
++)
1415 val
[j
] = get_val_for (next
[j
], val
[j
]);
1416 if (!is_gimple_min_invariant (val
[j
]))
1418 fold_undefer_and_ignore_overflow_warnings ();
1419 return chrec_dont_know
;
1424 fold_undefer_and_ignore_overflow_warnings ();
1426 return chrec_dont_know
;
1429 /* Finds the exit of the LOOP by that the loop exits after a constant
1430 number of iterations and stores the exit edge to *EXIT. The constant
1431 giving the number of iterations of LOOP is returned. The number of
1432 iterations is determined using loop_niter_by_eval (i.e. by brute force
1433 evaluation). If we are unable to find the exit for that loop_niter_by_eval
1434 determines the number of iterations, chrec_dont_know is returned. */
1437 find_loop_niter_by_eval (struct loop
*loop
, edge
*exit
)
1440 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
1442 tree niter
= NULL_TREE
, aniter
;
1445 for (i
= 0; VEC_iterate (edge
, exits
, i
, ex
); i
++)
1447 if (!just_once_each_iteration_p (loop
, ex
->src
))
1450 aniter
= loop_niter_by_eval (loop
, ex
);
1451 if (chrec_contains_undetermined (aniter
))
1455 && !tree_int_cst_lt (aniter
, niter
))
1461 VEC_free (edge
, heap
, exits
);
1463 return niter
? niter
: chrec_dont_know
;
1468 Analysis of upper bounds on number of iterations of a loop.
1472 /* Returns true if we can prove that COND ==> VAL >= 0. */
1475 implies_nonnegative_p (tree cond
, tree val
)
1477 tree type
= TREE_TYPE (val
);
1480 if (tree_expr_nonnegative_p (val
))
1483 if (integer_nonzerop (cond
))
1486 compare
= fold_build2 (GE_EXPR
,
1487 boolean_type_node
, val
, build_int_cst (type
, 0));
1488 compare
= tree_simplify_using_condition_1 (cond
, compare
);
1490 return integer_nonzerop (compare
);
1493 /* Returns true if we can prove that COND ==> A >= B. */
1496 implies_ge_p (tree cond
, tree a
, tree b
)
1498 tree compare
= fold_build2 (GE_EXPR
, boolean_type_node
, a
, b
);
1500 if (integer_nonzerop (compare
))
1503 if (integer_nonzerop (cond
))
1506 compare
= tree_simplify_using_condition_1 (cond
, compare
);
1508 return integer_nonzerop (compare
);
1511 /* Returns a constant upper bound on the value of expression VAL. VAL
1512 is considered to be unsigned. If its type is signed, its value must
1515 The condition ADDITIONAL must be satisfied (for example, if VAL is
1516 "(unsigned) n" and ADDITIONAL is "n > 0", then we can derive that
1517 VAL is at most (unsigned) MAX_INT). */
1520 derive_constant_upper_bound (tree val
, tree additional
)
1522 tree type
= TREE_TYPE (val
);
1523 tree op0
, op1
, subtype
, maxt
;
1524 double_int bnd
, max
, mmax
, cst
;
1527 if (INTEGRAL_TYPE_P (type
))
1528 maxt
= TYPE_MAX_VALUE (type
);
1530 maxt
= upper_bound_in_type (type
, type
);
1532 max
= tree_to_double_int (maxt
);
1534 switch (TREE_CODE (val
))
1537 return tree_to_double_int (val
);
1541 op0
= TREE_OPERAND (val
, 0);
1542 subtype
= TREE_TYPE (op0
);
1543 if (!TYPE_UNSIGNED (subtype
)
1544 /* If TYPE is also signed, the fact that VAL is nonnegative implies
1545 that OP0 is nonnegative. */
1546 && TYPE_UNSIGNED (type
)
1547 && !implies_nonnegative_p (additional
, op0
))
1549 /* If we cannot prove that the casted expression is nonnegative,
1550 we cannot establish more useful upper bound than the precision
1551 of the type gives us. */
1555 /* We now know that op0 is an nonnegative value. Try deriving an upper
1557 bnd
= derive_constant_upper_bound (op0
, additional
);
1559 /* If the bound does not fit in TYPE, max. value of TYPE could be
1561 if (double_int_ucmp (max
, bnd
) < 0)
1568 op0
= TREE_OPERAND (val
, 0);
1569 op1
= TREE_OPERAND (val
, 1);
1571 if (TREE_CODE (op1
) != INTEGER_CST
1572 || !implies_nonnegative_p (additional
, op0
))
1575 /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
1576 choose the most logical way how to treat this constant regardless
1577 of the signedness of the type. */
1578 cst
= tree_to_double_int (op1
);
1579 cst
= double_int_sext (cst
, TYPE_PRECISION (type
));
1580 if (TREE_CODE (val
) == PLUS_EXPR
)
1581 cst
= double_int_neg (cst
);
1583 bnd
= derive_constant_upper_bound (op0
, additional
);
1585 if (double_int_negative_p (cst
))
1587 cst
= double_int_neg (cst
);
1588 /* Avoid CST == 0x80000... */
1589 if (double_int_negative_p (cst
))
1592 /* OP0 + CST. We need to check that
1593 BND <= MAX (type) - CST. */
1595 mmax
= double_int_add (max
, double_int_neg (cst
));
1596 if (double_int_ucmp (bnd
, mmax
) > 0)
1599 return double_int_add (bnd
, cst
);
1603 /* OP0 - CST, where CST >= 0.
1605 If TYPE is signed, we have already verified that OP0 >= 0, and we
1606 know that the result is nonnegative. This implies that
1609 If TYPE is unsigned, we must additionally know that OP0 >= CST,
1610 otherwise the operation underflows.
1613 /* This should only happen if the type is unsigned; however, for
1614 programs that use overflowing signed arithmetics even with
1615 -fno-wrapv, this condition may also be true for signed values. */
1616 if (double_int_ucmp (bnd
, cst
) < 0)
1619 if (TYPE_UNSIGNED (type
)
1620 && !implies_ge_p (additional
,
1621 op0
, double_int_to_tree (type
, cst
)))
1624 bnd
= double_int_add (bnd
, double_int_neg (cst
));
1629 case FLOOR_DIV_EXPR
:
1630 case EXACT_DIV_EXPR
:
1631 op0
= TREE_OPERAND (val
, 0);
1632 op1
= TREE_OPERAND (val
, 1);
1633 if (TREE_CODE (op1
) != INTEGER_CST
1634 || tree_int_cst_sign_bit (op1
))
1637 bnd
= derive_constant_upper_bound (op0
, additional
);
1638 return double_int_udiv (bnd
, tree_to_double_int (op1
), FLOOR_DIV_EXPR
);
1641 op1
= TREE_OPERAND (val
, 1);
1642 if (TREE_CODE (op1
) != INTEGER_CST
1643 || tree_int_cst_sign_bit (op1
))
1645 return tree_to_double_int (op1
);
1648 stmt
= SSA_NAME_DEF_STMT (val
);
1649 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
1650 || GIMPLE_STMT_OPERAND (stmt
, 0) != val
)
1652 return derive_constant_upper_bound (GIMPLE_STMT_OPERAND (stmt
, 1),
1660 /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. The
1661 additional condition ADDITIONAL is recorded with the bound. IS_EXIT
1662 is true if the loop is exited immediately after STMT, and this exit
1663 is taken at last when the STMT is executed BOUND + 1 times.
1664 REALISTIC is true if the estimate comes from a reliable source
1665 (number of iterations analysis, or size of data accessed in the loop). */
1668 record_estimate (struct loop
*loop
, tree bound
, tree additional
, tree at_stmt
,
1669 bool is_exit
, bool realistic
)
1671 struct nb_iter_bound
*elt
= xmalloc (sizeof (struct nb_iter_bound
));
1672 double_int i_bound
= derive_constant_upper_bound (bound
, additional
);
1674 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1676 fprintf (dump_file
, "Statement %s", is_exit
? "(exit)" : "");
1677 print_generic_expr (dump_file
, at_stmt
, TDF_SLIM
);
1678 fprintf (dump_file
, " is executed at most ");
1679 print_generic_expr (dump_file
, bound
, TDF_SLIM
);
1680 fprintf (dump_file
, " (bounded by ");
1681 dump_double_int (dump_file
, i_bound
, true);
1682 fprintf (dump_file
, ") + 1 times in loop %d.\n", loop
->num
);
1685 elt
->bound
= i_bound
;
1686 elt
->stmt
= at_stmt
;
1687 elt
->is_exit
= is_exit
;
1688 elt
->realistic
= realistic
&& TREE_CODE (bound
) == INTEGER_CST
;
1689 elt
->next
= loop
->bounds
;
1693 /* Record the estimate on number of iterations of LOOP based on the fact that
1694 the induction variable BASE + STEP * i evaluated in STMT does not wrap and
1695 its values belong to the range <LOW, HIGH>. DATA_SIZE_BOUNDS_P is true if
1696 LOW and HIGH are derived from the size of data. */
1699 record_nonwrapping_iv (struct loop
*loop
, tree base
, tree step
, tree stmt
,
1700 tree low
, tree high
, bool data_size_bounds_p
)
1702 tree niter_bound
, extreme
, delta
;
1703 tree type
= TREE_TYPE (base
), unsigned_type
;
1705 if (TREE_CODE (step
) != INTEGER_CST
|| integer_zerop (step
))
1708 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1710 fprintf (dump_file
, "Induction variable (");
1711 print_generic_expr (dump_file
, TREE_TYPE (base
), TDF_SLIM
);
1712 fprintf (dump_file
, ") ");
1713 print_generic_expr (dump_file
, base
, TDF_SLIM
);
1714 fprintf (dump_file
, " + ");
1715 print_generic_expr (dump_file
, step
, TDF_SLIM
);
1716 fprintf (dump_file
, " * iteration does not wrap in statement ");
1717 print_generic_expr (dump_file
, stmt
, TDF_SLIM
);
1718 fprintf (dump_file
, " in loop %d.\n", loop
->num
);
1721 unsigned_type
= unsigned_type_for (type
);
1722 base
= fold_convert (unsigned_type
, base
);
1723 step
= fold_convert (unsigned_type
, step
);
1725 if (tree_int_cst_sign_bit (step
))
1727 extreme
= fold_convert (unsigned_type
, low
);
1728 if (TREE_CODE (base
) != INTEGER_CST
)
1729 base
= fold_convert (unsigned_type
, high
);
1730 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
1731 step
= fold_build1 (NEGATE_EXPR
, unsigned_type
, step
);
1735 extreme
= fold_convert (unsigned_type
, high
);
1736 if (TREE_CODE (base
) != INTEGER_CST
)
1737 base
= fold_convert (unsigned_type
, low
);
1738 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
1741 /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
1742 would get out of the range. */
1743 niter_bound
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step
);
1744 record_estimate (loop
, niter_bound
, boolean_true_node
, stmt
,
1745 false, data_size_bounds_p
);
1748 /* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe
1749 approximation of the number of iterations for LOOP. */
1752 compute_estimated_nb_iterations (struct loop
*loop
)
1754 struct nb_iter_bound
*bound
;
1756 gcc_assert (loop
->estimate_state
== EST_NOT_AVAILABLE
);
1758 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
1760 if (!bound
->realistic
)
1763 /* Update only when there is no previous estimation, or when the current
1764 estimation is smaller. */
1765 if (loop
->estimate_state
== EST_NOT_AVAILABLE
1766 || double_int_ucmp (bound
->bound
, loop
->estimated_nb_iterations
) < 0)
1768 loop
->estimate_state
= EST_AVAILABLE
;
1769 loop
->estimated_nb_iterations
= bound
->bound
;
1774 /* Determine information about number of iterations a LOOP from the index
1775 IDX of a data reference accessed in STMT. Callback for for_each_index. */
1784 idx_infer_loop_bounds (tree base
, tree
*idx
, void *dta
)
1786 struct ilb_data
*data
= dta
;
1787 tree ev
, init
, step
;
1788 tree low
, high
, type
, next
;
1790 struct loop
*loop
= data
->loop
;
1792 if (TREE_CODE (base
) != ARRAY_REF
)
1795 ev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, *idx
));
1796 init
= initial_condition (ev
);
1797 step
= evolution_part_in_loop_num (ev
, loop
->num
);
1801 || TREE_CODE (step
) != INTEGER_CST
1802 || integer_zerop (step
)
1803 || tree_contains_chrecs (init
, NULL
)
1804 || chrec_contains_symbols_defined_in_loop (init
, loop
->num
))
1807 low
= array_ref_low_bound (base
);
1808 high
= array_ref_up_bound (base
);
1810 /* The case of nonconstant bounds could be handled, but it would be
1812 if (TREE_CODE (low
) != INTEGER_CST
1814 || TREE_CODE (high
) != INTEGER_CST
)
1816 sign
= tree_int_cst_sign_bit (step
);
1817 type
= TREE_TYPE (step
);
1819 /* In case the relevant bound of the array does not fit in type, or
1820 it does, but bound + step (in type) still belongs into the range of the
1821 array, the index may wrap and still stay within the range of the array
1822 (consider e.g. if the array is indexed by the full range of
1825 To make things simpler, we require both bounds to fit into type, although
1826 there are cases where this would not be strictly necessary. */
1827 if (!int_fits_type_p (high
, type
)
1828 || !int_fits_type_p (low
, type
))
1830 low
= fold_convert (type
, low
);
1831 high
= fold_convert (type
, high
);
1834 next
= fold_binary (PLUS_EXPR
, type
, low
, step
);
1836 next
= fold_binary (PLUS_EXPR
, type
, high
, step
);
1838 if (tree_int_cst_compare (low
, next
) <= 0
1839 && tree_int_cst_compare (next
, high
) <= 0)
1842 record_nonwrapping_iv (loop
, init
, step
, data
->stmt
, low
, high
, true);
1846 /* Determine information about number of iterations a LOOP from the bounds
1847 of arrays in the data reference REF accessed in STMT. */
1850 infer_loop_bounds_from_ref (struct loop
*loop
, tree stmt
, tree ref
)
1852 struct ilb_data data
;
1856 for_each_index (&ref
, idx_infer_loop_bounds
, &data
);
1859 /* Determine information about number of iterations of a LOOP from the way
1860 arrays are used in STMT. */
1863 infer_loop_bounds_from_array (struct loop
*loop
, tree stmt
)
1867 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
1869 tree op0
= GIMPLE_STMT_OPERAND (stmt
, 0);
1870 tree op1
= GIMPLE_STMT_OPERAND (stmt
, 1);
1872 /* For each memory access, analyze its access function
1873 and record a bound on the loop iteration domain. */
1874 if (REFERENCE_CLASS_P (op0
))
1875 infer_loop_bounds_from_ref (loop
, stmt
, op0
);
1877 if (REFERENCE_CLASS_P (op1
))
1878 infer_loop_bounds_from_ref (loop
, stmt
, op1
);
1882 call
= get_call_expr_in (stmt
);
1887 for (args
= TREE_OPERAND (call
, 1); args
; args
= TREE_CHAIN (args
))
1888 if (REFERENCE_CLASS_P (TREE_VALUE (args
)))
1889 infer_loop_bounds_from_ref (loop
, stmt
, TREE_VALUE (args
));
1893 /* Determine information about number of iterations of a LOOP from the fact
1894 that signed arithmetics in STMT does not overflow. */
1897 infer_loop_bounds_from_signedness (struct loop
*loop
, tree stmt
)
1899 tree def
, base
, step
, scev
, type
, low
, high
;
1901 if (TREE_CODE (stmt
) != GIMPLE_MODIFY_STMT
)
1904 def
= GIMPLE_STMT_OPERAND (stmt
, 0);
1906 if (TREE_CODE (def
) != SSA_NAME
)
1909 type
= TREE_TYPE (def
);
1910 if (!INTEGRAL_TYPE_P (type
)
1911 || !TYPE_OVERFLOW_UNDEFINED (type
))
1914 scev
= instantiate_parameters (loop
, analyze_scalar_evolution (loop
, def
));
1915 if (chrec_contains_undetermined (scev
))
1918 base
= initial_condition_in_loop_num (scev
, loop
->num
);
1919 step
= evolution_part_in_loop_num (scev
, loop
->num
);
1922 || TREE_CODE (step
) != INTEGER_CST
1923 || tree_contains_chrecs (base
, NULL
)
1924 || chrec_contains_symbols_defined_in_loop (base
, loop
->num
))
1927 low
= lower_bound_in_type (type
, type
);
1928 high
= upper_bound_in_type (type
, type
);
1930 record_nonwrapping_iv (loop
, base
, step
, stmt
, low
, high
, false);
1933 /* The following analyzers are extracting informations on the bounds
1934 of LOOP from the following undefined behaviors:
1936 - data references should not access elements over the statically
1939 - signed variables should not overflow when flag_wrapv is not set.
1943 infer_loop_bounds_from_undefined (struct loop
*loop
)
1947 block_stmt_iterator bsi
;
1950 bbs
= get_loop_body (loop
);
1952 for (i
= 0; i
< loop
->num_nodes
; i
++)
1956 /* If BB is not executed in each iteration of the loop, we cannot
1957 use it to infer any information about # of iterations of the loop. */
1958 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1961 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1963 tree stmt
= bsi_stmt (bsi
);
1965 infer_loop_bounds_from_array (loop
, stmt
);
1966 infer_loop_bounds_from_signedness (loop
, stmt
);
1974 /* Records estimates on numbers of iterations of LOOP. */
1977 estimate_numbers_of_iterations_loop (struct loop
*loop
)
1979 VEC (edge
, heap
) *exits
;
1982 struct tree_niter_desc niter_desc
;
1985 /* Give up if we already have tried to compute an estimation. */
1986 if (loop
->estimate_state
!= EST_NOT_COMPUTED
)
1988 loop
->estimate_state
= EST_NOT_AVAILABLE
;
1990 exits
= get_loop_exit_edges (loop
);
1991 for (i
= 0; VEC_iterate (edge
, exits
, i
, ex
); i
++)
1993 if (!number_of_iterations_exit (loop
, ex
, &niter_desc
, false))
1996 niter
= niter_desc
.niter
;
1997 type
= TREE_TYPE (niter
);
1998 if (TREE_CODE (niter_desc
.may_be_zero
) != INTEGER_CST
)
1999 niter
= build3 (COND_EXPR
, type
, niter_desc
.may_be_zero
,
2000 build_int_cst (type
, 0),
2002 record_estimate (loop
, niter
,
2003 niter_desc
.additional_info
,
2004 last_stmt (ex
->src
),
2007 VEC_free (edge
, heap
, exits
);
2009 infer_loop_bounds_from_undefined (loop
);
2010 compute_estimated_nb_iterations (loop
);
2013 /* Records estimates on numbers of iterations of loops. */
2016 estimate_numbers_of_iterations (void)
2021 /* We don't want to issue signed overflow warnings while getting
2022 loop iteration estimates. */
2023 fold_defer_overflow_warnings ();
2025 FOR_EACH_LOOP (li
, loop
, 0)
2027 estimate_numbers_of_iterations_loop (loop
);
2030 fold_undefer_and_ignore_overflow_warnings ();
2033 /* Returns true if statement S1 dominates statement S2. */
2036 stmt_dominates_stmt_p (tree s1
, tree s2
)
2038 basic_block bb1
= bb_for_stmt (s1
), bb2
= bb_for_stmt (s2
);
2046 block_stmt_iterator bsi
;
2048 for (bsi
= bsi_start (bb1
); bsi_stmt (bsi
) != s2
; bsi_next (&bsi
))
2049 if (bsi_stmt (bsi
) == s1
)
2055 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
2058 /* Returns true when we can prove that the number of executions of
2059 STMT in the loop is at most NITER, according to the bound on
2060 the number of executions of the statement NITER_BOUND->stmt recorded in
2061 NITER_BOUND. If STMT is NULL, we must prove this bound for all
2062 statements in the loop. */
2065 n_of_executions_at_most (tree stmt
,
2066 struct nb_iter_bound
*niter_bound
,
2069 double_int bound
= niter_bound
->bound
;
2070 tree nit_type
= TREE_TYPE (niter
), e
;
2073 gcc_assert (TYPE_UNSIGNED (nit_type
));
2075 /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
2076 the number of iterations is small. */
2077 if (!double_int_fits_to_tree_p (nit_type
, bound
))
2080 /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
2081 times. This means that:
2083 -- if NITER_BOUND->is_exit is true, then everything before
2084 NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
2085 times, and everything after it at most NITER_BOUND->bound times.
2087 -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
2088 is executed, then NITER_BOUND->stmt is executed as well in the same
2089 iteration (we conclude that if both statements belong to the same
2090 basic block, or if STMT is after NITER_BOUND->stmt), then STMT
2091 is executed at most NITER_BOUND->bound + 1 times. Otherwise STMT is
2092 executed at most NITER_BOUND->bound + 2 times. */
2094 if (niter_bound
->is_exit
)
2097 && stmt
!= niter_bound
->stmt
2098 && stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
))
2106 || (bb_for_stmt (stmt
) != bb_for_stmt (niter_bound
->stmt
)
2107 && !stmt_dominates_stmt_p (niter_bound
->stmt
, stmt
)))
2109 bound
= double_int_add (bound
, double_int_one
);
2110 if (double_int_zero_p (bound
)
2111 || !double_int_fits_to_tree_p (nit_type
, bound
))
2117 e
= fold_binary (cmp
, boolean_type_node
,
2118 niter
, double_int_to_tree (nit_type
, bound
));
2119 return e
&& integer_nonzerop (e
);
2122 /* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
2125 nowrap_type_p (tree type
)
2127 if (INTEGRAL_TYPE_P (type
)
2128 && TYPE_OVERFLOW_UNDEFINED (type
))
2131 if (POINTER_TYPE_P (type
))
2137 /* Return false only when the induction variable BASE + STEP * I is
2138 known to not overflow: i.e. when the number of iterations is small
2139 enough with respect to the step and initial condition in order to
2140 keep the evolution confined in TYPEs bounds. Return true when the
2141 iv is known to overflow or when the property is not computable.
2143 USE_OVERFLOW_SEMANTICS is true if this function should assume that
2144 the rules for overflow of the given language apply (e.g., that signed
2145 arithmetics in C does not overflow). */
2148 scev_probably_wraps_p (tree base
, tree step
,
2149 tree at_stmt
, struct loop
*loop
,
2150 bool use_overflow_semantics
)
2152 struct nb_iter_bound
*bound
;
2153 tree delta
, step_abs
;
2154 tree unsigned_type
, valid_niter
;
2155 tree type
= TREE_TYPE (step
);
2157 /* FIXME: We really need something like
2158 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
2160 We used to test for the following situation that frequently appears
2161 during address arithmetics:
2163 D.1621_13 = (long unsigned intD.4) D.1620_12;
2164 D.1622_14 = D.1621_13 * 8;
2165 D.1623_15 = (doubleD.29 *) D.1622_14;
2167 And derived that the sequence corresponding to D_14
2168 can be proved to not wrap because it is used for computing a
2169 memory access; however, this is not really the case -- for example,
2170 if D_12 = (unsigned char) [254,+,1], then D_14 has values
2171 2032, 2040, 0, 8, ..., but the code is still legal. */
2173 if (chrec_contains_undetermined (base
)
2174 || chrec_contains_undetermined (step
)
2175 || TREE_CODE (step
) != INTEGER_CST
)
2178 if (integer_zerop (step
))
2181 /* If we can use the fact that signed and pointer arithmetics does not
2182 wrap, we are done. */
2183 if (use_overflow_semantics
&& nowrap_type_p (type
))
2186 /* Don't issue signed overflow warnings. */
2187 fold_defer_overflow_warnings ();
2189 /* Otherwise, compute the number of iterations before we reach the
2190 bound of the type, and verify that the loop is exited before this
2192 unsigned_type
= unsigned_type_for (type
);
2193 base
= fold_convert (unsigned_type
, base
);
2195 if (tree_int_cst_sign_bit (step
))
2197 tree extreme
= fold_convert (unsigned_type
,
2198 lower_bound_in_type (type
, type
));
2199 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, base
, extreme
);
2200 step_abs
= fold_build1 (NEGATE_EXPR
, unsigned_type
,
2201 fold_convert (unsigned_type
, step
));
2205 tree extreme
= fold_convert (unsigned_type
,
2206 upper_bound_in_type (type
, type
));
2207 delta
= fold_build2 (MINUS_EXPR
, unsigned_type
, extreme
, base
);
2208 step_abs
= fold_convert (unsigned_type
, step
);
2211 valid_niter
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step_abs
);
2213 estimate_numbers_of_iterations_loop (loop
);
2214 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
2216 if (n_of_executions_at_most (at_stmt
, bound
, valid_niter
))
2218 fold_undefer_and_ignore_overflow_warnings ();
2223 fold_undefer_and_ignore_overflow_warnings ();
2225 /* At this point we still don't have a proof that the iv does not
2226 overflow: give up. */
2230 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
2233 free_numbers_of_iterations_estimates_loop (struct loop
*loop
)
2235 struct nb_iter_bound
*bound
, *next
;
2237 loop
->nb_iterations
= NULL
;
2238 loop
->estimate_state
= EST_NOT_COMPUTED
;
2239 for (bound
= loop
->bounds
; bound
; bound
= next
)
2245 loop
->bounds
= NULL
;
2248 /* Frees the information on upper bounds on numbers of iterations of loops. */
2251 free_numbers_of_iterations_estimates (void)
2256 FOR_EACH_LOOP (li
, loop
, 0)
2258 free_numbers_of_iterations_estimates_loop (loop
);
2262 /* Substitute value VAL for ssa name NAME inside expressions held
2266 substitute_in_loop_info (struct loop
*loop
, tree name
, tree val
)
2268 loop
->nb_iterations
= simplify_replace_tree (loop
->nb_iterations
, name
, val
);