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 true if ARG is either NULL_TREE or constant zero. Unlike
56 integer_zerop, it does not care about overflow flags. */
64 if (TREE_CODE (arg
) != INTEGER_CST
)
67 return (TREE_INT_CST_LOW (arg
) == 0 && TREE_INT_CST_HIGH (arg
) == 0);
70 /* Returns true if ARG a nonzero constant. Unlike integer_nonzerop, it does
71 not care about overflow flags. */
79 if (TREE_CODE (arg
) != INTEGER_CST
)
82 return (TREE_INT_CST_LOW (arg
) != 0 || TREE_INT_CST_HIGH (arg
) != 0);
85 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
88 inverse (tree x
, tree mask
)
90 tree type
= TREE_TYPE (x
);
92 unsigned ctr
= tree_floor_log2 (mask
);
94 if (TYPE_PRECISION (type
) <= HOST_BITS_PER_WIDE_INT
)
96 unsigned HOST_WIDE_INT ix
;
97 unsigned HOST_WIDE_INT imask
;
98 unsigned HOST_WIDE_INT irslt
= 1;
100 gcc_assert (cst_and_fits_in_hwi (x
));
101 gcc_assert (cst_and_fits_in_hwi (mask
));
103 ix
= int_cst_value (x
);
104 imask
= int_cst_value (mask
);
113 rslt
= build_int_cst_type (type
, irslt
);
117 rslt
= build_int_cst_type (type
, 1);
120 rslt
= int_const_binop (MULT_EXPR
, rslt
, x
, 0);
121 x
= int_const_binop (MULT_EXPR
, x
, x
, 0);
123 rslt
= int_const_binop (BIT_AND_EXPR
, rslt
, mask
, 0);
129 /* Determine the number of iterations according to condition (for staying
130 inside loop) which compares two induction variables using comparison
131 operator CODE. The induction variable on left side of the comparison
132 has base BASE0 and step STEP0. the right-hand side one has base
133 BASE1 and step STEP1. Both induction variables must have type TYPE,
134 which must be an integer or pointer type. STEP0 and STEP1 must be
135 constants (or NULL_TREE, which is interpreted as constant zero).
137 The results (number of iterations and assumptions as described in
138 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
139 In case we are unable to determine number of iterations, contents of
140 this structure is unchanged. */
143 number_of_iterations_cond (tree type
, tree base0
, tree step0
,
144 enum tree_code code
, tree base1
, tree step1
,
145 struct tree_niter_desc
*niter
)
147 tree step
, delta
, mmin
, mmax
;
148 tree may_xform
, bound
, s
, d
, tmp
;
149 bool was_sharp
= false;
151 tree assumptions
= boolean_true_node
;
152 tree noloop_assumptions
= boolean_false_node
;
153 tree niter_type
, signed_niter_type
;
156 /* The meaning of these assumptions is this:
158 then the rest of information does not have to be valid
159 if noloop_assumptions then the loop does not have to roll
160 (but it is only conservative approximation, i.e. it only says that
161 if !noloop_assumptions, then the loop does not end before the computed
162 number of iterations) */
164 /* Make < comparison from > ones. */
170 code
= swap_tree_comparison (code
);
173 /* We can handle the case when neither of the sides of the comparison is
174 invariant, provided that the test is NE_EXPR. This rarely occurs in
175 practice, but it is simple enough to manage. */
176 if (!zero_p (step0
) && !zero_p (step1
))
181 step0
= fold_binary_to_constant (MINUS_EXPR
, type
, step0
, step1
);
185 /* If the result is a constant, the loop is weird. More precise handling
186 would be possible, but the situation is not common enough to waste time
188 if (zero_p (step0
) && zero_p (step1
))
191 /* Ignore loops of while (i-- < 10) type. */
194 if (step0
&& tree_int_cst_sign_bit (step0
))
197 if (!zero_p (step1
) && !tree_int_cst_sign_bit (step1
))
201 if (POINTER_TYPE_P (type
))
203 /* We assume pointer arithmetic never overflows. */
204 mmin
= mmax
= NULL_TREE
;
208 mmin
= TYPE_MIN_VALUE (type
);
209 mmax
= TYPE_MAX_VALUE (type
);
212 /* Some more condition normalization. We must record some assumptions
217 /* We want to take care only of <=; this is easy,
218 as in cases the overflow would make the transformation unsafe the loop
219 does not roll. Seemingly it would make more sense to want to take
220 care of <, as NE is more similar to it, but the problem is that here
221 the transformation would be more difficult due to possibly infinite
226 assumption
= fold_build2 (EQ_EXPR
, boolean_type_node
, base0
, mmax
);
228 assumption
= boolean_false_node
;
229 if (nonzero_p (assumption
))
231 base0
= fold_build2 (PLUS_EXPR
, type
, base0
,
232 build_int_cst_type (type
, 1));
237 assumption
= fold_build2 (EQ_EXPR
, boolean_type_node
, base1
, mmin
);
239 assumption
= boolean_false_node
;
240 if (nonzero_p (assumption
))
242 base1
= fold_build2 (MINUS_EXPR
, type
, base1
,
243 build_int_cst_type (type
, 1));
245 noloop_assumptions
= assumption
;
248 /* It will be useful to be able to tell the difference once more in
249 <= -> != reduction. */
253 /* Take care of trivially infinite loops. */
258 && operand_equal_p (base0
, mmin
, 0))
262 && operand_equal_p (base1
, mmax
, 0))
266 /* If we can we want to take care of NE conditions instead of size
267 comparisons, as they are much more friendly (most importantly
268 this takes care of special handling of loops with step 1). We can
269 do it if we first check that upper bound is greater or equal to
270 lower bound, their difference is constant c modulo step and that
271 there is not an overflow. */
275 step
= fold_unary_to_constant (NEGATE_EXPR
, type
, step1
);
278 delta
= fold_build2 (MINUS_EXPR
, type
, base1
, base0
);
279 delta
= fold_build2 (FLOOR_MOD_EXPR
, type
, delta
, step
);
280 may_xform
= boolean_false_node
;
282 if (TREE_CODE (delta
) == INTEGER_CST
)
284 tmp
= fold_binary_to_constant (MINUS_EXPR
, type
, step
,
285 build_int_cst_type (type
, 1));
287 && operand_equal_p (delta
, tmp
, 0))
289 /* A special case. We have transformed condition of type
290 for (i = 0; i < 4; i += 4)
292 for (i = 0; i <= 3; i += 4)
293 obviously if the test for overflow during that transformation
294 passed, we cannot overflow here. Most importantly any
295 loop with sharp end condition and step 1 falls into this
296 category, so handling this case specially is definitely
297 worth the troubles. */
298 may_xform
= boolean_true_node
;
300 else if (zero_p (step0
))
303 may_xform
= boolean_true_node
;
306 bound
= fold_binary_to_constant (PLUS_EXPR
, type
,
308 bound
= fold_binary_to_constant (MINUS_EXPR
, type
,
310 may_xform
= fold_build2 (LE_EXPR
, boolean_type_node
,
317 may_xform
= boolean_true_node
;
320 bound
= fold_binary_to_constant (MINUS_EXPR
, type
,
322 bound
= fold_binary_to_constant (PLUS_EXPR
, type
,
324 may_xform
= fold_build2 (LE_EXPR
, boolean_type_node
,
330 if (!zero_p (may_xform
))
332 /* We perform the transformation always provided that it is not
333 completely senseless. This is OK, as we would need this assumption
334 to determine the number of iterations anyway. */
335 if (!nonzero_p (may_xform
))
336 assumptions
= may_xform
;
340 base0
= fold_build2 (PLUS_EXPR
, type
, base0
, delta
);
341 base0
= fold_build2 (MINUS_EXPR
, type
, base0
, step
);
345 base1
= fold_build2 (MINUS_EXPR
, type
, base1
, delta
);
346 base1
= fold_build2 (PLUS_EXPR
, type
, base1
, step
);
349 assumption
= fold_build2 (GT_EXPR
, boolean_type_node
, base0
, base1
);
350 noloop_assumptions
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
351 noloop_assumptions
, assumption
);
356 /* Count the number of iterations. */
357 niter_type
= unsigned_type_for (type
);
358 signed_niter_type
= signed_type_for (type
);
362 /* Everything we do here is just arithmetics modulo size of mode. This
363 makes us able to do more involved computations of number of iterations
364 than in other cases. First transform the condition into shape
365 s * i <> c, with s positive. */
366 base1
= fold_build2 (MINUS_EXPR
, type
, base1
, base0
);
369 step0
= fold_unary_to_constant (NEGATE_EXPR
, type
, step1
);
371 if (tree_int_cst_sign_bit (fold_convert (signed_niter_type
, step0
)))
373 step0
= fold_unary_to_constant (NEGATE_EXPR
, type
, step0
);
374 base1
= fold_build1 (NEGATE_EXPR
, type
, base1
);
377 base1
= fold_convert (niter_type
, base1
);
378 step0
= fold_convert (niter_type
, step0
);
380 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
381 is infinite. Otherwise, the number of iterations is
382 (inverse(s/d) * (c/d)) mod (size of mode/d). */
383 bits
= num_ending_zeros (step0
);
384 d
= fold_binary_to_constant (LSHIFT_EXPR
, niter_type
,
385 build_int_cst_type (niter_type
, 1), bits
);
386 s
= fold_binary_to_constant (RSHIFT_EXPR
, niter_type
, step0
, bits
);
388 bound
= build_low_bits_mask (niter_type
,
389 (TYPE_PRECISION (niter_type
)
390 - tree_low_cst (bits
, 1)));
392 assumption
= fold_build2 (FLOOR_MOD_EXPR
, niter_type
, base1
, d
);
393 assumption
= fold_build2 (EQ_EXPR
, boolean_type_node
,
395 build_int_cst (niter_type
, 0));
396 assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
397 assumptions
, assumption
);
399 tmp
= fold_build2 (EXACT_DIV_EXPR
, niter_type
, base1
, d
);
400 tmp
= fold_build2 (MULT_EXPR
, niter_type
, tmp
, inverse (s
, bound
));
401 niter
->niter
= fold_build2 (BIT_AND_EXPR
, niter_type
, tmp
, bound
);
406 /* Condition in shape a + s * i <= b
407 We must know that b + s does not overflow and a <= b + s and then we
408 can compute number of iterations as (b + s - a) / s. (It might
409 seem that we in fact could be more clever about testing the b + s
410 overflow condition using some information about b - a mod s,
411 but it was already taken into account during LE -> NE transform). */
415 bound
= fold_binary_to_constant (MINUS_EXPR
, type
, mmax
, step0
);
416 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
418 assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
419 assumptions
, assumption
);
423 tmp
= fold_build2 (PLUS_EXPR
, type
, base1
, step0
);
424 assumption
= fold_build2 (GT_EXPR
, boolean_type_node
, base0
, tmp
);
425 delta
= fold_build2 (PLUS_EXPR
, type
, base1
, step
);
426 delta
= fold_build2 (MINUS_EXPR
, type
, delta
, base0
);
427 delta
= fold_convert (niter_type
, delta
);
431 /* Condition in shape a <= b - s * i
432 We must know that a - s does not overflow and a - s <= b and then
433 we can again compute number of iterations as (b - (a - s)) / s. */
436 bound
= fold_binary_to_constant (MINUS_EXPR
, type
, mmin
, step1
);
437 assumption
= fold_build2 (LE_EXPR
, boolean_type_node
,
439 assumptions
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
440 assumptions
, assumption
);
442 step
= fold_build1 (NEGATE_EXPR
, type
, step1
);
443 tmp
= fold_build2 (PLUS_EXPR
, type
, base0
, step1
);
444 assumption
= fold_build2 (GT_EXPR
, boolean_type_node
, tmp
, base1
);
445 delta
= fold_build2 (MINUS_EXPR
, type
, base0
, step
);
446 delta
= fold_build2 (MINUS_EXPR
, type
, base1
, delta
);
447 delta
= fold_convert (niter_type
, delta
);
449 noloop_assumptions
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
450 noloop_assumptions
, assumption
);
451 delta
= fold_build2 (FLOOR_DIV_EXPR
, niter_type
, delta
,
452 fold_convert (niter_type
, step
));
453 niter
->niter
= delta
;
456 niter
->assumptions
= assumptions
;
457 niter
->may_be_zero
= noloop_assumptions
;
461 niter
->assumptions
= boolean_true_node
;
462 niter
->may_be_zero
= boolean_true_node
;
463 niter
->niter
= build_int_cst_type (type
, 0);
468 /* Similar to number_of_iterations_cond, but only handles the special
469 case of loops with step 1 or -1. The meaning of the arguments
470 is the same as in number_of_iterations_cond. The function
471 returns true if the special case was recognized, false otherwise. */
474 number_of_iterations_special (tree type
, tree base0
, tree step0
,
475 enum tree_code code
, tree base1
, tree step1
,
476 struct tree_niter_desc
*niter
)
478 tree niter_type
= unsigned_type_for (type
), mmax
, mmin
;
480 /* Make < comparison from > ones. */
486 code
= swap_tree_comparison (code
);
499 else if (!zero_p (step1
))
502 if (integer_onep (step0
))
504 /* for (i = base0; i != base1; i++) */
505 niter
->assumptions
= boolean_true_node
;
506 niter
->may_be_zero
= boolean_false_node
;
507 niter
->niter
= fold_build2 (MINUS_EXPR
, type
, base1
, base0
);
508 niter
->additional_info
= boolean_true_node
;
510 else if (integer_all_onesp (step0
))
512 /* for (i = base0; i != base1; i--) */
513 niter
->assumptions
= boolean_true_node
;
514 niter
->may_be_zero
= boolean_false_node
;
515 niter
->niter
= fold_build2 (MINUS_EXPR
, type
, base0
, base1
);
523 if ((step0
&& integer_onep (step0
) && zero_p (step1
))
524 || (step1
&& integer_all_onesp (step1
) && zero_p (step0
)))
526 /* for (i = base0; i < base1; i++)
530 for (i = base1; i > base0; i--).
532 In both cases # of iterations is base1 - base0. */
534 niter
->assumptions
= boolean_true_node
;
535 niter
->may_be_zero
= fold_build2 (GT_EXPR
, boolean_type_node
,
537 niter
->niter
= fold_build2 (MINUS_EXPR
, type
, base1
, base0
);
544 if (POINTER_TYPE_P (type
))
546 /* We assume pointer arithmetic never overflows. */
547 mmin
= mmax
= NULL_TREE
;
551 mmin
= TYPE_MIN_VALUE (type
);
552 mmax
= TYPE_MAX_VALUE (type
);
555 if (step0
&& integer_onep (step0
) && zero_p (step1
))
557 /* for (i = base0; i <= base1; i++) */
559 niter
->assumptions
= fold_build2 (NE_EXPR
, boolean_type_node
,
562 niter
->assumptions
= boolean_true_node
;
563 base1
= fold_build2 (PLUS_EXPR
, type
, base1
,
564 build_int_cst_type (type
, 1));
566 else if (step1
&& integer_all_onesp (step1
) && zero_p (step0
))
568 /* for (i = base1; i >= base0; i--) */
570 niter
->assumptions
= fold_build2 (NE_EXPR
, boolean_type_node
,
573 niter
->assumptions
= boolean_true_node
;
574 base0
= fold_build2 (MINUS_EXPR
, type
, base0
,
575 build_int_cst_type (type
, 1));
580 niter
->may_be_zero
= fold_build2 (GT_EXPR
, boolean_type_node
,
582 niter
->niter
= fold_build2 (MINUS_EXPR
, type
, base1
, base0
);
589 niter
->niter
= fold_convert (niter_type
, niter
->niter
);
590 niter
->additional_info
= boolean_true_node
;
594 /* Substitute NEW for OLD in EXPR and fold the result. */
597 simplify_replace_tree (tree expr
, tree old
, tree
new)
600 tree ret
= NULL_TREE
, e
, se
;
606 || operand_equal_p (expr
, old
, 0))
607 return unshare_expr (new);
612 n
= TREE_CODE_LENGTH (TREE_CODE (expr
));
613 for (i
= 0; i
< n
; i
++)
615 e
= TREE_OPERAND (expr
, i
);
616 se
= simplify_replace_tree (e
, old
, new);
621 ret
= copy_node (expr
);
623 TREE_OPERAND (ret
, i
) = se
;
626 return (ret
? fold (ret
) : expr
);
629 /* Expand definitions of ssa names in EXPR as long as they are simple
630 enough, and return the new expression. */
633 expand_simple_operations (tree expr
)
636 tree ret
= NULL_TREE
, e
, ee
, stmt
;
637 enum tree_code code
= TREE_CODE (expr
);
639 if (is_gimple_min_invariant (expr
))
642 if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code
)))
644 n
= TREE_CODE_LENGTH (code
);
645 for (i
= 0; i
< n
; i
++)
647 e
= TREE_OPERAND (expr
, i
);
648 ee
= expand_simple_operations (e
);
653 ret
= copy_node (expr
);
655 TREE_OPERAND (ret
, i
) = ee
;
658 return (ret
? fold (ret
) : expr
);
661 if (TREE_CODE (expr
) != SSA_NAME
)
664 stmt
= SSA_NAME_DEF_STMT (expr
);
665 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
668 e
= TREE_OPERAND (stmt
, 1);
669 if (/* Casts are simple. */
670 TREE_CODE (e
) != NOP_EXPR
671 && TREE_CODE (e
) != CONVERT_EXPR
672 /* Copies are simple. */
673 && TREE_CODE (e
) != SSA_NAME
674 /* Assignments of invariants are simple. */
675 && !is_gimple_min_invariant (e
)
676 /* And increments and decrements by a constant are simple. */
677 && !((TREE_CODE (e
) == PLUS_EXPR
678 || TREE_CODE (e
) == MINUS_EXPR
)
679 && is_gimple_min_invariant (TREE_OPERAND (e
, 1))))
682 return expand_simple_operations (e
);
685 /* Tries to simplify EXPR using the condition COND. Returns the simplified
686 expression (or EXPR unchanged, if no simplification was possible). */
689 tree_simplify_using_condition_1 (tree cond
, tree expr
)
692 tree e
, te
, e0
, e1
, e2
, notcond
;
693 enum tree_code code
= TREE_CODE (expr
);
695 if (code
== INTEGER_CST
)
698 if (code
== TRUTH_OR_EXPR
699 || code
== TRUTH_AND_EXPR
700 || code
== COND_EXPR
)
704 e0
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 0));
705 if (TREE_OPERAND (expr
, 0) != e0
)
708 e1
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 1));
709 if (TREE_OPERAND (expr
, 1) != e1
)
712 if (code
== COND_EXPR
)
714 e2
= tree_simplify_using_condition_1 (cond
, TREE_OPERAND (expr
, 2));
715 if (TREE_OPERAND (expr
, 2) != e2
)
723 if (code
== COND_EXPR
)
724 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
726 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
732 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
733 propagation, and vice versa. Fold does not handle this, since it is
734 considered too expensive. */
735 if (TREE_CODE (cond
) == EQ_EXPR
)
737 e0
= TREE_OPERAND (cond
, 0);
738 e1
= TREE_OPERAND (cond
, 1);
740 /* We know that e0 == e1. Check whether we cannot simplify expr
742 e
= simplify_replace_tree (expr
, e0
, e1
);
743 if (zero_p (e
) || nonzero_p (e
))
746 e
= simplify_replace_tree (expr
, e1
, e0
);
747 if (zero_p (e
) || nonzero_p (e
))
750 if (TREE_CODE (expr
) == EQ_EXPR
)
752 e0
= TREE_OPERAND (expr
, 0);
753 e1
= TREE_OPERAND (expr
, 1);
755 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
756 e
= simplify_replace_tree (cond
, e0
, e1
);
759 e
= simplify_replace_tree (cond
, e1
, e0
);
763 if (TREE_CODE (expr
) == NE_EXPR
)
765 e0
= TREE_OPERAND (expr
, 0);
766 e1
= TREE_OPERAND (expr
, 1);
768 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
769 e
= simplify_replace_tree (cond
, e0
, e1
);
771 return boolean_true_node
;
772 e
= simplify_replace_tree (cond
, e1
, e0
);
774 return boolean_true_node
;
777 te
= expand_simple_operations (expr
);
779 /* Check whether COND ==> EXPR. */
780 notcond
= invert_truthvalue (cond
);
781 e
= fold_binary (TRUTH_OR_EXPR
, boolean_type_node
, notcond
, te
);
785 /* Check whether COND ==> not EXPR. */
786 e
= fold_binary (TRUTH_AND_EXPR
, boolean_type_node
, cond
, te
);
793 /* Tries to simplify EXPR using the condition COND. Returns the simplified
794 expression (or EXPR unchanged, if no simplification was possible).
795 Wrapper around tree_simplify_using_condition_1 that ensures that chains
796 of simple operations in definitions of ssa names in COND are expanded,
797 so that things like casts or incrementing the value of the bound before
798 the loop do not cause us to fail. */
801 tree_simplify_using_condition (tree cond
, tree expr
)
803 cond
= expand_simple_operations (cond
);
805 return tree_simplify_using_condition_1 (cond
, expr
);
808 /* Tries to simplify EXPR using the conditions on entry to LOOP.
809 Record the conditions used for simplification to CONDS_USED.
810 Returns the simplified expression (or EXPR unchanged, if no
811 simplification was possible).*/
814 simplify_using_initial_conditions (struct loop
*loop
, tree expr
,
821 if (TREE_CODE (expr
) == INTEGER_CST
)
824 for (bb
= loop
->header
;
825 bb
!= ENTRY_BLOCK_PTR
;
826 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
828 if (!single_pred_p (bb
))
830 e
= single_pred_edge (bb
);
832 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
835 cond
= COND_EXPR_COND (last_stmt (e
->src
));
836 if (e
->flags
& EDGE_FALSE_VALUE
)
837 cond
= invert_truthvalue (cond
);
838 exp
= tree_simplify_using_condition (cond
, expr
);
841 *conds_used
= fold_build2 (TRUTH_AND_EXPR
,
852 /* Tries to simplify EXPR using the evolutions of the loop invariants
853 in the superloops of LOOP. Returns the simplified expression
854 (or EXPR unchanged, if no simplification was possible). */
857 simplify_using_outer_evolutions (struct loop
*loop
, tree expr
)
859 enum tree_code code
= TREE_CODE (expr
);
863 if (is_gimple_min_invariant (expr
))
866 if (code
== TRUTH_OR_EXPR
867 || code
== TRUTH_AND_EXPR
868 || code
== COND_EXPR
)
872 e0
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 0));
873 if (TREE_OPERAND (expr
, 0) != e0
)
876 e1
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 1));
877 if (TREE_OPERAND (expr
, 1) != e1
)
880 if (code
== COND_EXPR
)
882 e2
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 2));
883 if (TREE_OPERAND (expr
, 2) != e2
)
891 if (code
== COND_EXPR
)
892 expr
= fold_build3 (code
, boolean_type_node
, e0
, e1
, e2
);
894 expr
= fold_build2 (code
, boolean_type_node
, e0
, e1
);
900 e
= instantiate_parameters (loop
, expr
);
901 if (is_gimple_min_invariant (e
))
907 /* Stores description of number of iterations of LOOP derived from
908 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
909 useful information could be derived (and fields of NITER has
910 meaning described in comments at struct tree_niter_desc
911 declaration), false otherwise. If WARN is true and
912 -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
913 potentially unsafe assumptions. */
916 number_of_iterations_exit (struct loop
*loop
, edge exit
,
917 struct tree_niter_desc
*niter
,
920 tree stmt
, cond
, type
;
921 tree op0
, base0
, step0
;
922 tree op1
, base1
, step1
;
925 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit
->src
))
928 niter
->assumptions
= boolean_false_node
;
929 stmt
= last_stmt (exit
->src
);
930 if (!stmt
|| TREE_CODE (stmt
) != COND_EXPR
)
933 /* We want the condition for staying inside loop. */
934 cond
= COND_EXPR_COND (stmt
);
935 if (exit
->flags
& EDGE_TRUE_VALUE
)
936 cond
= invert_truthvalue (cond
);
938 code
= TREE_CODE (cond
);
952 op0
= TREE_OPERAND (cond
, 0);
953 op1
= TREE_OPERAND (cond
, 1);
954 type
= TREE_TYPE (op0
);
956 if (TREE_CODE (type
) != INTEGER_TYPE
957 && !POINTER_TYPE_P (type
))
960 if (!simple_iv (loop
, stmt
, op0
, &base0
, &step0
, false))
962 if (!simple_iv (loop
, stmt
, op1
, &base1
, &step1
, false))
965 niter
->niter
= NULL_TREE
;
967 /* Handle common special cases first, so that we do not need to use
968 generic (and slow) analysis very often. */
969 if (!number_of_iterations_special (type
, base0
, step0
, code
, base1
, step1
,
973 number_of_iterations_cond (type
, base0
, step0
, code
, base1
, step1
,
982 niter
->assumptions
= simplify_using_outer_evolutions (loop
,
984 niter
->may_be_zero
= simplify_using_outer_evolutions (loop
,
986 niter
->niter
= simplify_using_outer_evolutions (loop
, niter
->niter
);
989 niter
->additional_info
= boolean_true_node
;
991 = simplify_using_initial_conditions (loop
,
993 &niter
->additional_info
);
995 = simplify_using_initial_conditions (loop
,
997 &niter
->additional_info
);
999 if (integer_onep (niter
->assumptions
))
1002 /* With -funsafe-loop-optimizations we assume that nothing bad can happen.
1003 But if we can prove that there is overflow or some other source of weird
1004 behavior, ignore the loop even with -funsafe-loop-optimizations. */
1005 if (integer_zerop (niter
->assumptions
))
1008 if (flag_unsafe_loop_optimizations
)
1009 niter
->assumptions
= boolean_true_node
;
1013 const char *wording
;
1014 location_t loc
= EXPR_LOCATION (stmt
);
1016 /* We can provide a more specific warning if one of the operator is
1017 constant and the other advances by +1 or -1. */
1018 if (step1
? !step0
&& (integer_onep (step1
) || integer_all_onesp (step1
))
1019 : step0
&& (integer_onep (step0
) || integer_all_onesp (step0
)))
1021 flag_unsafe_loop_optimizations
1022 ? N_("assuming that the loop is not infinite")
1023 : N_("cannot optimize possibly infinite loops");
1026 flag_unsafe_loop_optimizations
1027 ? N_("assuming that the loop counter does not overflow")
1028 : N_("cannot optimize loop, the loop counter may overflow");
1030 if (LOCATION_LINE (loc
) > 0)
1031 warning (OPT_Wunsafe_loop_optimizations
, "%H%s", &loc
, gettext (wording
));
1033 warning (OPT_Wunsafe_loop_optimizations
, "%s", gettext (wording
));
1036 return flag_unsafe_loop_optimizations
;
1039 /* Try to determine the number of iterations of LOOP. If we succeed,
1040 expression giving number of iterations is returned and *EXIT is
1041 set to the edge from that the information is obtained. Otherwise
1042 chrec_dont_know is returned. */
1045 find_loop_niter (struct loop
*loop
, edge
*exit
)
1047 unsigned n_exits
, i
;
1048 edge
*exits
= get_loop_exit_edges (loop
, &n_exits
);
1050 tree niter
= NULL_TREE
, aniter
;
1051 struct tree_niter_desc desc
;
1054 for (i
= 0; i
< n_exits
; i
++)
1057 if (!just_once_each_iteration_p (loop
, ex
->src
))
1060 if (!number_of_iterations_exit (loop
, ex
, &desc
, false))
1063 if (nonzero_p (desc
.may_be_zero
))
1065 /* We exit in the first iteration through this exit.
1066 We won't find anything better. */
1067 niter
= build_int_cst_type (unsigned_type_node
, 0);
1072 if (!zero_p (desc
.may_be_zero
))
1075 aniter
= desc
.niter
;
1079 /* Nothing recorded yet. */
1085 /* Prefer constants, the lower the better. */
1086 if (TREE_CODE (aniter
) != INTEGER_CST
)
1089 if (TREE_CODE (niter
) != INTEGER_CST
)
1096 if (tree_int_cst_lt (aniter
, niter
))
1105 return niter
? niter
: chrec_dont_know
;
1110 Analysis of a number of iterations of a loop by a brute-force evaluation.
1114 /* Bound on the number of iterations we try to evaluate. */
1116 #define MAX_ITERATIONS_TO_TRACK \
1117 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
1119 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
1120 result by a chain of operations such that all but exactly one of their
1121 operands are constants. */
1124 chain_of_csts_start (struct loop
*loop
, tree x
)
1126 tree stmt
= SSA_NAME_DEF_STMT (x
);
1128 basic_block bb
= bb_for_stmt (stmt
);
1131 || !flow_bb_inside_loop_p (loop
, bb
))
1134 if (TREE_CODE (stmt
) == PHI_NODE
)
1136 if (bb
== loop
->header
)
1142 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
1145 if (!ZERO_SSA_OPERANDS (stmt
, SSA_OP_ALL_VIRTUALS
))
1147 if (SINGLE_SSA_DEF_OPERAND (stmt
, SSA_OP_DEF
) == NULL_DEF_OPERAND_P
)
1150 use
= SINGLE_SSA_TREE_OPERAND (stmt
, SSA_OP_USE
);
1151 if (use
== NULL_USE_OPERAND_P
)
1154 return chain_of_csts_start (loop
, use
);
1157 /* Determines whether the expression X is derived from a result of a phi node
1158 in header of LOOP such that
1160 * the derivation of X consists only from operations with constants
1161 * the initial value of the phi node is constant
1162 * the value of the phi node in the next iteration can be derived from the
1163 value in the current iteration by a chain of operations with constants.
1165 If such phi node exists, it is returned. If X is a constant, X is returned
1166 unchanged. Otherwise NULL_TREE is returned. */
1169 get_base_for (struct loop
*loop
, tree x
)
1171 tree phi
, init
, next
;
1173 if (is_gimple_min_invariant (x
))
1176 phi
= chain_of_csts_start (loop
, x
);
1180 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
1181 next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
1183 if (TREE_CODE (next
) != SSA_NAME
)
1186 if (!is_gimple_min_invariant (init
))
1189 if (chain_of_csts_start (loop
, next
) != phi
)
1195 /* Given an expression X, then
1197 * if BASE is NULL_TREE, X must be a constant and we return X.
1198 * otherwise X is a SSA name, whose value in the considered loop is derived
1199 by a chain of operations with constant from a result of a phi node in
1200 the header of the loop. Then we return value of X when the value of the
1201 result of this phi node is given by the constant BASE. */
1204 get_val_for (tree x
, tree base
)
1213 stmt
= SSA_NAME_DEF_STMT (x
);
1214 if (TREE_CODE (stmt
) == PHI_NODE
)
1217 FOR_EACH_SSA_USE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
1219 nx
= USE_FROM_PTR (op
);
1220 val
= get_val_for (nx
, base
);
1222 val
= fold (TREE_OPERAND (stmt
, 1));
1224 /* only iterate loop once. */
1228 /* Should never reach here. */
1232 /* Tries to count the number of iterations of LOOP till it exits by EXIT
1233 by brute force -- i.e. by determining the value of the operands of the
1234 condition at EXIT in first few iterations of the loop (assuming that
1235 these values are constant) and determining the first one in that the
1236 condition is not satisfied. Returns the constant giving the number
1237 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
1240 loop_niter_by_eval (struct loop
*loop
, edge exit
)
1242 tree cond
, cnd
, acnd
;
1243 tree op
[2], val
[2], next
[2], aval
[2], phi
[2];
1247 cond
= last_stmt (exit
->src
);
1248 if (!cond
|| TREE_CODE (cond
) != COND_EXPR
)
1249 return chrec_dont_know
;
1251 cnd
= COND_EXPR_COND (cond
);
1252 if (exit
->flags
& EDGE_TRUE_VALUE
)
1253 cnd
= invert_truthvalue (cnd
);
1255 cmp
= TREE_CODE (cnd
);
1264 for (j
= 0; j
< 2; j
++)
1265 op
[j
] = TREE_OPERAND (cnd
, j
);
1269 return chrec_dont_know
;
1272 for (j
= 0; j
< 2; j
++)
1274 phi
[j
] = get_base_for (loop
, op
[j
]);
1276 return chrec_dont_know
;
1279 for (j
= 0; j
< 2; j
++)
1281 if (TREE_CODE (phi
[j
]) == PHI_NODE
)
1283 val
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
[j
], loop_preheader_edge (loop
));
1284 next
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
[j
], loop_latch_edge (loop
));
1289 next
[j
] = NULL_TREE
;
1294 for (i
= 0; i
< MAX_ITERATIONS_TO_TRACK
; i
++)
1296 for (j
= 0; j
< 2; j
++)
1297 aval
[j
] = get_val_for (op
[j
], val
[j
]);
1299 acnd
= fold_binary (cmp
, boolean_type_node
, aval
[0], aval
[1]);
1300 if (acnd
&& zero_p (acnd
))
1302 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1304 "Proved that loop %d iterates %d times using brute force.\n",
1306 return build_int_cst (unsigned_type_node
, i
);
1309 for (j
= 0; j
< 2; j
++)
1310 val
[j
] = get_val_for (next
[j
], val
[j
]);
1313 return chrec_dont_know
;
1316 /* Finds the exit of the LOOP by that the loop exits after a constant
1317 number of iterations and stores the exit edge to *EXIT. The constant
1318 giving the number of iterations of LOOP is returned. The number of
1319 iterations is determined using loop_niter_by_eval (i.e. by brute force
1320 evaluation). If we are unable to find the exit for that loop_niter_by_eval
1321 determines the number of iterations, chrec_dont_know is returned. */
1324 find_loop_niter_by_eval (struct loop
*loop
, edge
*exit
)
1326 unsigned n_exits
, i
;
1327 edge
*exits
= get_loop_exit_edges (loop
, &n_exits
);
1329 tree niter
= NULL_TREE
, aniter
;
1332 for (i
= 0; i
< n_exits
; i
++)
1335 if (!just_once_each_iteration_p (loop
, ex
->src
))
1338 aniter
= loop_niter_by_eval (loop
, ex
);
1339 if (chrec_contains_undetermined (aniter
))
1343 && !tree_int_cst_lt (aniter
, niter
))
1351 return niter
? niter
: chrec_dont_know
;
1356 Analysis of upper bounds on number of iterations of a loop.
1360 /* Records that AT_STMT is executed at most BOUND times in LOOP. The
1361 additional condition ADDITIONAL is recorded with the bound. */
1364 record_estimate (struct loop
*loop
, tree bound
, tree additional
, tree at_stmt
)
1366 struct nb_iter_bound
*elt
= xmalloc (sizeof (struct nb_iter_bound
));
1368 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1370 fprintf (dump_file
, "Statements after ");
1371 print_generic_expr (dump_file
, at_stmt
, TDF_SLIM
);
1372 fprintf (dump_file
, " are executed at most ");
1373 print_generic_expr (dump_file
, bound
, TDF_SLIM
);
1374 fprintf (dump_file
, " times in loop %d.\n", loop
->num
);
1378 elt
->at_stmt
= at_stmt
;
1379 elt
->additional
= additional
;
1380 elt
->next
= loop
->bounds
;
1384 /* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe
1385 approximation of the number of iterations for LOOP. */
1388 compute_estimated_nb_iterations (struct loop
*loop
)
1390 struct nb_iter_bound
*bound
;
1392 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
1393 if (TREE_CODE (bound
->bound
) == INTEGER_CST
1394 /* Update only when there is no previous estimation. */
1395 && (chrec_contains_undetermined (loop
->estimated_nb_iterations
)
1396 /* Or when the current estimation is smaller. */
1397 || tree_int_cst_lt (bound
->bound
, loop
->estimated_nb_iterations
)))
1398 loop
->estimated_nb_iterations
= bound
->bound
;
1401 /* The following analyzers are extracting informations on the bounds
1402 of LOOP from the following undefined behaviors:
1404 - data references should not access elements over the statically
1407 - signed variables should not overflow when flag_wrapv is not set.
1411 infer_loop_bounds_from_undefined (struct loop
*loop
)
1414 basic_block bb
, *bbs
;
1415 block_stmt_iterator bsi
;
1417 bbs
= get_loop_body (loop
);
1419 for (i
= 0; i
< loop
->num_nodes
; i
++)
1423 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1425 tree stmt
= bsi_stmt (bsi
);
1427 switch (TREE_CODE (stmt
))
1431 tree op0
= TREE_OPERAND (stmt
, 0);
1432 tree op1
= TREE_OPERAND (stmt
, 1);
1434 /* For each array access, analyze its access function
1435 and record a bound on the loop iteration domain. */
1436 if (TREE_CODE (op1
) == ARRAY_REF
)
1437 analyze_array (stmt
, op1
, true);
1439 if (TREE_CODE (op0
) == ARRAY_REF
)
1440 analyze_array (stmt
, op0
, false);
1442 /* For each signed type variable in LOOP, analyze its
1443 scalar evolution and record a bound of the loop
1444 based on the type's ranges. */
1445 else if (!flag_wrapv
&& TREE_CODE (op0
) == SSA_NAME
)
1447 tree init
, step
, diff
, estimation
;
1448 tree scev
= instantiate_parameters
1449 (loop
, analyze_scalar_evolution (loop
, op0
));
1450 tree type
= chrec_type (scev
);
1453 if (chrec_contains_undetermined (scev
)
1454 || TYPE_UNSIGNED (type
))
1457 init
= initial_condition_in_loop_num (scev
, loop
->num
);
1458 step
= evolution_part_in_loop_num (scev
, loop
->num
);
1460 if (init
== NULL_TREE
1461 || step
== NULL_TREE
1462 || TREE_CODE (init
) != INTEGER_CST
1463 || TREE_CODE (step
) != INTEGER_CST
1464 || TYPE_MIN_VALUE (type
) == NULL_TREE
1465 || TYPE_MAX_VALUE (type
) == NULL_TREE
)
1468 utype
= unsigned_type_for (type
);
1469 if (tree_int_cst_lt (step
, integer_zero_node
))
1470 diff
= fold_build2 (MINUS_EXPR
, utype
, init
,
1471 TYPE_MIN_VALUE (type
));
1473 diff
= fold_build2 (MINUS_EXPR
, utype
,
1474 TYPE_MAX_VALUE (type
), init
);
1476 estimation
= fold_build2 (CEIL_DIV_EXPR
, utype
, diff
,
1478 record_estimate (loop
, estimation
, boolean_true_node
, stmt
);
1488 for (args
= TREE_OPERAND (stmt
, 1); args
;
1489 args
= TREE_CHAIN (args
))
1490 if (TREE_CODE (TREE_VALUE (args
)) == ARRAY_REF
)
1491 analyze_array (stmt
, TREE_VALUE (args
), true);
1501 if (chrec_contains_undetermined (loop
->estimated_nb_iterations
))
1502 compute_estimated_nb_iterations (loop
);
1508 /* Records estimates on numbers of iterations of LOOP. */
1511 estimate_numbers_of_iterations_loop (struct loop
*loop
)
1515 unsigned i
, n_exits
;
1516 struct tree_niter_desc niter_desc
;
1518 /* Give up if we already have tried to compute an estimation. */
1519 if (loop
->estimated_nb_iterations
== chrec_dont_know
1520 /* Or when we already have an estimation. */
1521 || (loop
->estimated_nb_iterations
!= NULL_TREE
1522 && TREE_CODE (loop
->estimated_nb_iterations
) == INTEGER_CST
))
1525 loop
->estimated_nb_iterations
= chrec_dont_know
;
1527 exits
= get_loop_exit_edges (loop
, &n_exits
);
1528 for (i
= 0; i
< n_exits
; i
++)
1530 if (!number_of_iterations_exit (loop
, exits
[i
], &niter_desc
, false))
1533 niter
= niter_desc
.niter
;
1534 type
= TREE_TYPE (niter
);
1535 if (!zero_p (niter_desc
.may_be_zero
)
1536 && !nonzero_p (niter_desc
.may_be_zero
))
1537 niter
= build3 (COND_EXPR
, type
, niter_desc
.may_be_zero
,
1538 build_int_cst_type (type
, 0),
1540 record_estimate (loop
, niter
,
1541 niter_desc
.additional_info
,
1542 last_stmt (exits
[i
]->src
));
1546 if (chrec_contains_undetermined (loop
->estimated_nb_iterations
))
1547 infer_loop_bounds_from_undefined (loop
);
1550 /* Records estimates on numbers of iterations of LOOPS. */
1553 estimate_numbers_of_iterations (struct loops
*loops
)
1558 for (i
= 1; i
< loops
->num
; i
++)
1560 loop
= loops
->parray
[i
];
1562 estimate_numbers_of_iterations_loop (loop
);
1566 /* If A > B, returns -1. If A == B, returns 0. If A < B, returns 1.
1567 If neither of these relations can be proved, returns 2. */
1570 compare_trees (tree a
, tree b
)
1572 tree typea
= TREE_TYPE (a
), typeb
= TREE_TYPE (b
);
1575 if (TYPE_PRECISION (typea
) > TYPE_PRECISION (typeb
))
1580 a
= fold_convert (type
, a
);
1581 b
= fold_convert (type
, b
);
1583 if (nonzero_p (fold_binary (EQ_EXPR
, boolean_type_node
, a
, b
)))
1585 if (nonzero_p (fold_binary (LT_EXPR
, boolean_type_node
, a
, b
)))
1587 if (nonzero_p (fold_binary (GT_EXPR
, boolean_type_node
, a
, b
)))
1593 /* Returns true if statement S1 dominates statement S2. */
1596 stmt_dominates_stmt_p (tree s1
, tree s2
)
1598 basic_block bb1
= bb_for_stmt (s1
), bb2
= bb_for_stmt (s2
);
1606 block_stmt_iterator bsi
;
1608 for (bsi
= bsi_start (bb1
); bsi_stmt (bsi
) != s2
; bsi_next (&bsi
))
1609 if (bsi_stmt (bsi
) == s1
)
1615 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
1618 /* Return true when it is possible to prove that the induction
1619 variable does not wrap: vary outside the type specified bounds.
1620 Checks whether BOUND < VALID_NITER that means in the context of iv
1621 conversion that all the iterations in the loop are safe: not
1624 The statement NITER_BOUND->AT_STMT is executed at most
1625 NITER_BOUND->BOUND times in the loop.
1627 NITER_BOUND->ADDITIONAL is the additional condition recorded for
1628 operands of the bound. This is useful in the following case,
1629 created by loop header copying:
1638 If the n > 0 condition is taken into account, the number of iterations of the
1639 loop can be expressed as n - 1. If the type of n is signed, the ADDITIONAL
1640 assumption "n > 0" says us that the value of the number of iterations is at
1641 most MAX_TYPE - 1 (without this assumption, it might overflow). */
1644 proved_non_wrapping_p (tree at_stmt
,
1645 struct nb_iter_bound
*niter_bound
,
1650 tree bound
= niter_bound
->bound
;
1653 if (TYPE_PRECISION (new_type
) > TYPE_PRECISION (TREE_TYPE (bound
)))
1654 bound
= fold_convert (unsigned_type_for (new_type
), bound
);
1656 valid_niter
= fold_convert (TREE_TYPE (bound
), valid_niter
);
1658 /* Give up if BOUND was not folded to an INTEGER_CST, as in PR23434. */
1659 if (TREE_CODE (bound
) != INTEGER_CST
)
1662 /* After the statement niter_bound->at_stmt we know that anything is
1663 executed at most BOUND times. */
1664 if (at_stmt
&& stmt_dominates_stmt_p (niter_bound
->at_stmt
, at_stmt
))
1666 /* Before the statement niter_bound->at_stmt we know that anything
1667 is executed at most BOUND + 1 times. */
1671 cond
= fold_binary (cmp
, boolean_type_node
, valid_niter
, bound
);
1672 if (nonzero_p (cond
))
1675 cond
= build2 (cmp
, boolean_type_node
, valid_niter
, bound
);
1676 /* Try taking additional conditions into account. */
1677 cond
= fold_binary (TRUTH_OR_EXPR
, boolean_type_node
,
1678 invert_truthvalue (niter_bound
->additional
),
1681 if (nonzero_p (cond
))
1687 /* Checks whether it is correct to count the induction variable BASE +
1688 STEP * I at AT_STMT in a wider type NEW_TYPE, using the bounds on
1689 numbers of iterations of a LOOP. If it is possible, return the
1690 value of step of the induction variable in the NEW_TYPE, otherwise
1691 return NULL_TREE. */
1694 convert_step_widening (struct loop
*loop
, tree new_type
, tree base
, tree step
,
1697 struct nb_iter_bound
*bound
;
1698 tree base_in_new_type
, base_plus_step_in_new_type
, step_in_new_type
;
1699 tree delta
, step_abs
;
1700 tree unsigned_type
, valid_niter
;
1702 /* Compute the new step. For example, {(uchar) 100, +, (uchar) 240}
1703 is converted to {(uint) 100, +, (uint) 0xfffffff0} in order to
1704 keep the values of the induction variable unchanged: 100, 84, 68,
1707 Another example is: (uint) {(uchar)100, +, (uchar)3} is converted
1708 to {(uint)100, +, (uint)3}.
1710 Before returning the new step, verify that the number of
1711 iterations is less than DELTA / STEP_ABS (i.e. in the previous
1712 example (256 - 100) / 3) such that the iv does not wrap (in which
1713 case the operations are too difficult to be represented and
1714 handled: the values of the iv should be taken modulo 256 in the
1715 wider type; this is not implemented). */
1716 base_in_new_type
= fold_convert (new_type
, base
);
1717 base_plus_step_in_new_type
=
1718 fold_convert (new_type
,
1719 fold_build2 (PLUS_EXPR
, TREE_TYPE (base
), base
, step
));
1720 step_in_new_type
= fold_build2 (MINUS_EXPR
, new_type
,
1721 base_plus_step_in_new_type
,
1724 if (TREE_CODE (step_in_new_type
) != INTEGER_CST
)
1727 switch (compare_trees (base_plus_step_in_new_type
, base_in_new_type
))
1731 tree extreme
= upper_bound_in_type (new_type
, TREE_TYPE (base
));
1732 delta
= fold_build2 (MINUS_EXPR
, new_type
, extreme
,
1734 step_abs
= step_in_new_type
;
1740 tree extreme
= lower_bound_in_type (new_type
, TREE_TYPE (base
));
1741 delta
= fold_build2 (MINUS_EXPR
, new_type
, base_in_new_type
,
1743 step_abs
= fold_build1 (NEGATE_EXPR
, new_type
, step_in_new_type
);
1748 return step_in_new_type
;
1754 unsigned_type
= unsigned_type_for (new_type
);
1755 delta
= fold_convert (unsigned_type
, delta
);
1756 step_abs
= fold_convert (unsigned_type
, step_abs
);
1757 valid_niter
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
,
1760 estimate_numbers_of_iterations_loop (loop
);
1761 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
1762 if (proved_non_wrapping_p (at_stmt
, bound
, new_type
, valid_niter
))
1763 return step_in_new_type
;
1765 /* Fail when the loop has no bound estimations, or when no bound can
1766 be used for verifying the conversion. */
1770 /* Returns true when VAR is used in pointer arithmetics. DEPTH is
1771 used for limiting the search. */
1774 used_in_pointer_arithmetic_p (tree var
, int depth
)
1776 use_operand_p use_p
;
1777 imm_use_iterator iter
;
1780 || TREE_CODE (var
) != SSA_NAME
1781 || !has_single_use (var
))
1784 FOR_EACH_IMM_USE_FAST (use_p
, iter
, var
)
1786 tree stmt
= USE_STMT (use_p
);
1788 if (stmt
&& TREE_CODE (stmt
) == MODIFY_EXPR
)
1790 tree rhs
= TREE_OPERAND (stmt
, 1);
1792 if (TREE_CODE (rhs
) == NOP_EXPR
1793 || TREE_CODE (rhs
) == CONVERT_EXPR
)
1795 if (POINTER_TYPE_P (TREE_TYPE (rhs
)))
1800 return used_in_pointer_arithmetic_p (TREE_OPERAND (stmt
, 0),
1807 /* Return false only when the induction variable BASE + STEP * I is
1808 known to not overflow: i.e. when the number of iterations is small
1809 enough with respect to the step and initial condition in order to
1810 keep the evolution confined in TYPEs bounds. Return true when the
1811 iv is known to overflow or when the property is not computable.
1813 Initialize INIT_IS_MAX to true when the evolution goes from
1814 INIT_IS_MAX to LOWER_BOUND_IN_TYPE, false in the contrary case.
1815 When this property cannot be determined, UNKNOWN_MAX is set to
1819 scev_probably_wraps_p (tree type
, tree base
, tree step
,
1820 tree at_stmt
, struct loop
*loop
,
1821 bool *init_is_max
, bool *unknown_max
)
1823 struct nb_iter_bound
*bound
;
1824 tree delta
, step_abs
;
1825 tree unsigned_type
, valid_niter
;
1826 tree base_plus_step
, bpsps
;
1829 /* FIXME: The following code will not be used anymore once
1830 http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html is
1833 If AT_STMT is a cast to unsigned that is later used for
1834 referencing a memory location, it is followed by a pointer
1835 conversion just after. Because pointers do not wrap, the
1836 sequences that reference the memory do not wrap either. In the
1837 following example, sequences corresponding to D_13 and to D_14
1838 can be proved to not wrap because they are used for computing a
1841 D.1621_13 = (long unsigned intD.4) D.1620_12;
1842 D.1622_14 = D.1621_13 * 8;
1843 D.1623_15 = (doubleD.29 *) D.1622_14;
1845 if (at_stmt
&& TREE_CODE (at_stmt
) == MODIFY_EXPR
)
1847 tree op0
= TREE_OPERAND (at_stmt
, 0);
1848 tree op1
= TREE_OPERAND (at_stmt
, 1);
1849 tree type_op1
= TREE_TYPE (op1
);
1851 if ((TYPE_UNSIGNED (type_op1
)
1852 && used_in_pointer_arithmetic_p (op0
, 2))
1853 || POINTER_TYPE_P (type_op1
))
1855 *unknown_max
= true;
1860 if (TREE_CODE (base
) == REAL_CST
1861 || TREE_CODE (step
) == REAL_CST
)
1863 *unknown_max
= true;
1867 *unknown_max
= false;
1868 base_plus_step
= fold_build2 (PLUS_EXPR
, type
, base
, step
);
1869 bpsps
= fold_build2 (PLUS_EXPR
, type
, base_plus_step
, step
);
1870 cps
= compare_trees (base_plus_step
, base
);
1871 cpsps
= compare_trees (bpsps
, base_plus_step
);
1873 /* Check that the sequence is not wrapping in the first step: it
1874 should have the same monotonicity for the first two steps. See
1883 tree extreme
= upper_bound_in_type (type
, TREE_TYPE (base
));
1884 delta
= fold_build2 (MINUS_EXPR
, type
, extreme
, base
);
1886 *init_is_max
= false;
1892 tree extreme
= lower_bound_in_type (type
, TREE_TYPE (base
));
1893 delta
= fold_build2 (MINUS_EXPR
, type
, base
, extreme
);
1894 step_abs
= fold_build1 (NEGATE_EXPR
, type
, step
);
1895 *init_is_max
= true;
1900 /* This means step is equal to 0. This should not happen. It
1901 could happen in convert step, but not here. Safely answer
1902 don't know as in the default case. */
1905 *unknown_max
= true;
1909 /* If AT_STMT represents a cast operation, we may not be able to
1910 take advantage of the undefinedness of signed type evolutions.
1912 implement-c.texi states: "For conversion to a type of width
1913 N, the value is reduced modulo 2^N to be within range of the
1916 See PR 21959 for a test case. Essentially, given a cast
1921 sc = (signed char) uc;
1925 where uc and sc have the scev {0, +, 1}, we would consider uc to
1926 wrap around, but not sc, because it is of a signed type. This
1927 causes VRP to erroneously fold the predicate above because it
1928 thinks that sc cannot be negative. */
1929 if (at_stmt
&& TREE_CODE (at_stmt
) == MODIFY_EXPR
)
1931 tree rhs
= TREE_OPERAND (at_stmt
, 1);
1932 tree outer_t
= TREE_TYPE (rhs
);
1934 if (!TYPE_UNSIGNED (outer_t
)
1935 && (TREE_CODE (rhs
) == NOP_EXPR
|| TREE_CODE (rhs
) == CONVERT_EXPR
))
1937 tree inner_t
= TREE_TYPE (TREE_OPERAND (rhs
, 0));
1939 /* If the inner type is unsigned and its size and/or
1940 precision are smaller to that of the outer type, then the
1941 expression may wrap around. */
1942 if (TYPE_UNSIGNED (inner_t
)
1943 && (TYPE_SIZE (inner_t
) <= TYPE_SIZE (outer_t
)
1944 || TYPE_PRECISION (inner_t
) <= TYPE_PRECISION (outer_t
)))
1946 *unknown_max
= true;
1952 /* After having set INIT_IS_MAX, we can return false: when not using
1953 wrapping arithmetic, signed types don't wrap. */
1954 if (!flag_wrapv
&& !TYPE_UNSIGNED (type
))
1957 unsigned_type
= unsigned_type_for (type
);
1958 delta
= fold_convert (unsigned_type
, delta
);
1959 step_abs
= fold_convert (unsigned_type
, step_abs
);
1960 valid_niter
= fold_build2 (FLOOR_DIV_EXPR
, unsigned_type
, delta
, step_abs
);
1962 estimate_numbers_of_iterations_loop (loop
);
1963 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
1964 if (proved_non_wrapping_p (at_stmt
, bound
, type
, valid_niter
))
1967 /* At this point we still don't have a proof that the iv does not
1968 overflow: give up. */
1969 *unknown_max
= true;
1973 /* Return the conversion to NEW_TYPE of the STEP of an induction
1974 variable BASE + STEP * I at AT_STMT. When it fails, return
1978 convert_step (struct loop
*loop
, tree new_type
, tree base
, tree step
,
1981 tree base_type
= TREE_TYPE (base
);
1983 /* When not using wrapping arithmetic, signed types don't wrap. */
1984 if (!flag_wrapv
&& !TYPE_UNSIGNED (base_type
))
1985 return fold_convert (new_type
, step
);
1987 if (TYPE_PRECISION (new_type
) > TYPE_PRECISION (base_type
))
1988 return convert_step_widening (loop
, new_type
, base
, step
, at_stmt
);
1990 return fold_convert (new_type
, step
);
1993 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
1996 free_numbers_of_iterations_estimates_loop (struct loop
*loop
)
1998 struct nb_iter_bound
*bound
, *next
;
2000 for (bound
= loop
->bounds
; bound
; bound
= next
)
2006 loop
->bounds
= NULL
;
2009 /* Frees the information on upper bounds on numbers of iterations of LOOPS. */
2012 free_numbers_of_iterations_estimates (struct loops
*loops
)
2017 for (i
= 1; i
< loops
->num
; i
++)
2019 loop
= loops
->parray
[i
];
2021 free_numbers_of_iterations_estimates_loop (loop
);
2025 /* Substitute value VAL for ssa name NAME inside expressions held
2029 substitute_in_loop_info (struct loop
*loop
, tree name
, tree val
)
2031 struct nb_iter_bound
*bound
;
2033 loop
->nb_iterations
= simplify_replace_tree (loop
->nb_iterations
, name
, val
);
2034 loop
->estimated_nb_iterations
2035 = simplify_replace_tree (loop
->estimated_nb_iterations
, name
, val
);
2036 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
2038 bound
->bound
= simplify_replace_tree (bound
->bound
, name
, val
);
2039 bound
->additional
= simplify_replace_tree (bound
->additional
, name
, val
);