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, 59 Temple Place - Suite 330, Boston, MA
23 #include "coretypes.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
31 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-dump.h"
35 #include "tree-pass.h"
37 #include "tree-chrec.h"
38 #include "tree-scalar-evolution.h"
39 #include "tree-data-ref.h"
42 #include "tree-inline.h"
44 #define SWAP(X, Y) do { void *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
49 Analysis of number of iterations of an affine exit test.
53 /* Returns true if ARG is either NULL_TREE or constant zero. Unlike
54 integer_zerop, it does not care about overflow flags. */
62 if (TREE_CODE (arg
) != INTEGER_CST
)
65 return (TREE_INT_CST_LOW (arg
) == 0 && TREE_INT_CST_HIGH (arg
) == 0);
68 /* Returns true if ARG a nonzero constant. Unlike integer_nonzerop, it does
69 not care about overflow flags. */
77 if (TREE_CODE (arg
) != INTEGER_CST
)
80 return (TREE_INT_CST_LOW (arg
) != 0 || TREE_INT_CST_HIGH (arg
) != 0);
83 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
86 inverse (tree x
, tree mask
)
88 tree type
= TREE_TYPE (x
);
90 unsigned ctr
= tree_floor_log2 (mask
);
92 if (TYPE_PRECISION (type
) <= HOST_BITS_PER_WIDE_INT
)
94 unsigned HOST_WIDE_INT ix
;
95 unsigned HOST_WIDE_INT imask
;
96 unsigned HOST_WIDE_INT irslt
= 1;
98 gcc_assert (cst_and_fits_in_hwi (x
));
99 gcc_assert (cst_and_fits_in_hwi (mask
));
101 ix
= int_cst_value (x
);
102 imask
= int_cst_value (mask
);
111 rslt
= build_int_cst_type (type
, irslt
);
115 rslt
= build_int_cst_type (type
, 1);
118 rslt
= fold_binary_to_constant (MULT_EXPR
, type
, rslt
, x
);
119 x
= fold_binary_to_constant (MULT_EXPR
, type
, x
, x
);
121 rslt
= fold_binary_to_constant (BIT_AND_EXPR
, type
, rslt
, mask
);
127 /* Determine the number of iterations according to condition (for staying
128 inside loop) which compares two induction variables using comparison
129 operator CODE. The induction variable on left side of the comparison
130 has base BASE0 and step STEP0. the right-hand side one has base
131 BASE1 and step STEP1. Both induction variables must have type TYPE,
132 which must be an integer or pointer type. STEP0 and STEP1 must be
133 constants (or NULL_TREE, which is interpreted as constant zero).
135 The results (number of iterations and assumptions as described in
136 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
137 In case we are unable to determine number of iterations, contents of
138 this structure is unchanged. */
141 number_of_iterations_cond (tree type
, tree base0
, tree step0
,
142 enum tree_code code
, tree base1
, tree step1
,
143 struct tree_niter_desc
*niter
)
145 tree step
, delta
, mmin
, mmax
;
146 tree may_xform
, bound
, s
, d
, tmp
;
147 bool was_sharp
= false;
149 tree assumptions
= boolean_true_node
;
150 tree noloop_assumptions
= boolean_false_node
;
151 tree niter_type
, signed_niter_type
;
154 /* The meaning of these assumptions is this:
156 then the rest of information does not have to be valid
157 if noloop_assumptions then the loop does not have to roll
158 (but it is only conservative approximation, i.e. it only says that
159 if !noloop_assumptions, then the loop does not end before the computed
160 number of iterations) */
162 /* Make < comparison from > ones. */
168 code
= swap_tree_comparison (code
);
171 /* We can handle the case when neither of the sides of the comparison is
172 invariant, provided that the test is NE_EXPR. This rarely occurs in
173 practice, but it is simple enough to manage. */
174 if (!zero_p (step0
) && !zero_p (step1
))
179 step0
= fold_binary_to_constant (MINUS_EXPR
, type
, step0
, step1
);
183 /* If the result is a constant, the loop is weird. More precise handling
184 would be possible, but the situation is not common enough to waste time
186 if (zero_p (step0
) && zero_p (step1
))
189 /* Ignore loops of while (i-- < 10) type. */
192 if (step0
&& !tree_expr_nonnegative_p (step0
))
195 if (!zero_p (step1
) && tree_expr_nonnegative_p (step1
))
199 if (POINTER_TYPE_P (type
))
201 /* We assume pointer arithmetic never overflows. */
202 mmin
= mmax
= NULL_TREE
;
206 mmin
= TYPE_MIN_VALUE (type
);
207 mmax
= TYPE_MAX_VALUE (type
);
210 /* Some more condition normalization. We must record some assumptions
215 /* We want to take care only of <=; this is easy,
216 as in cases the overflow would make the transformation unsafe the loop
217 does not roll. Seemingly it would make more sense to want to take
218 care of <, as NE is more similar to it, but the problem is that here
219 the transformation would be more difficult due to possibly infinite
224 assumption
= fold (build2 (EQ_EXPR
, boolean_type_node
, base0
, mmax
));
226 assumption
= boolean_false_node
;
227 if (nonzero_p (assumption
))
229 base0
= fold (build2 (PLUS_EXPR
, type
, base0
,
230 build_int_cst_type (type
, 1)));
235 assumption
= fold (build2 (EQ_EXPR
, boolean_type_node
, base1
, mmin
));
237 assumption
= boolean_false_node
;
238 if (nonzero_p (assumption
))
240 base1
= fold (build2 (MINUS_EXPR
, type
, base1
,
241 build_int_cst_type (type
, 1)));
243 noloop_assumptions
= assumption
;
246 /* It will be useful to be able to tell the difference once more in
247 <= -> != reduction. */
251 /* Take care of trivially infinite loops. */
256 && operand_equal_p (base0
, mmin
, 0))
260 && operand_equal_p (base1
, mmax
, 0))
264 /* If we can we want to take care of NE conditions instead of size
265 comparisons, as they are much more friendly (most importantly
266 this takes care of special handling of loops with step 1). We can
267 do it if we first check that upper bound is greater or equal to
268 lower bound, their difference is constant c modulo step and that
269 there is not an overflow. */
273 step
= fold_unary_to_constant (NEGATE_EXPR
, type
, step1
);
276 delta
= build2 (MINUS_EXPR
, type
, base1
, base0
);
277 delta
= fold (build2 (FLOOR_MOD_EXPR
, type
, delta
, step
));
278 may_xform
= boolean_false_node
;
280 if (TREE_CODE (delta
) == INTEGER_CST
)
282 tmp
= fold_binary_to_constant (MINUS_EXPR
, type
, step
,
283 build_int_cst_type (type
, 1));
285 && operand_equal_p (delta
, tmp
, 0))
287 /* A special case. We have transformed condition of type
288 for (i = 0; i < 4; i += 4)
290 for (i = 0; i <= 3; i += 4)
291 obviously if the test for overflow during that transformation
292 passed, we cannot overflow here. Most importantly any
293 loop with sharp end condition and step 1 falls into this
294 category, so handling this case specially is definitely
295 worth the troubles. */
296 may_xform
= boolean_true_node
;
298 else if (zero_p (step0
))
301 may_xform
= boolean_true_node
;
304 bound
= fold_binary_to_constant (PLUS_EXPR
, type
,
306 bound
= fold_binary_to_constant (MINUS_EXPR
, type
,
308 may_xform
= fold (build2 (LE_EXPR
, boolean_type_node
,
315 may_xform
= boolean_true_node
;
318 bound
= fold_binary_to_constant (MINUS_EXPR
, type
,
320 bound
= fold_binary_to_constant (PLUS_EXPR
, type
,
322 may_xform
= fold (build2 (LE_EXPR
, boolean_type_node
,
328 if (!zero_p (may_xform
))
330 /* We perform the transformation always provided that it is not
331 completely senseless. This is OK, as we would need this assumption
332 to determine the number of iterations anyway. */
333 if (!nonzero_p (may_xform
))
334 assumptions
= may_xform
;
338 base0
= fold (build2 (PLUS_EXPR
, type
, base0
, delta
));
339 base0
= fold (build2 (MINUS_EXPR
, type
, base0
, step
));
343 base1
= fold (build2 (MINUS_EXPR
, type
, base1
, delta
));
344 base1
= fold (build2 (PLUS_EXPR
, type
, base1
, step
));
347 assumption
= fold (build2 (GT_EXPR
, boolean_type_node
, base0
, base1
));
348 noloop_assumptions
= fold (build2 (TRUTH_OR_EXPR
, boolean_type_node
,
349 noloop_assumptions
, assumption
));
354 /* Count the number of iterations. */
355 niter_type
= unsigned_type_for (type
);
356 signed_niter_type
= signed_type_for (type
);
360 /* Everything we do here is just arithmetics modulo size of mode. This
361 makes us able to do more involved computations of number of iterations
362 than in other cases. First transform the condition into shape
363 s * i <> c, with s positive. */
364 base1
= fold (build2 (MINUS_EXPR
, type
, base1
, base0
));
367 step0
= fold_unary_to_constant (NEGATE_EXPR
, type
, step1
);
369 if (!tree_expr_nonnegative_p (fold_convert (signed_niter_type
, step0
)))
371 step0
= fold_unary_to_constant (NEGATE_EXPR
, type
, step0
);
372 base1
= fold (build1 (NEGATE_EXPR
, type
, base1
));
375 base1
= fold_convert (niter_type
, base1
);
376 step0
= fold_convert (niter_type
, step0
);
378 /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
379 is infinite. Otherwise, the number of iterations is
380 (inverse(s/d) * (c/d)) mod (size of mode/d). */
381 bits
= num_ending_zeros (step0
);
382 d
= fold_binary_to_constant (LSHIFT_EXPR
, niter_type
,
383 build_int_cst_type (niter_type
, 1), bits
);
384 s
= fold_binary_to_constant (RSHIFT_EXPR
, niter_type
, step0
, bits
);
386 bound
= build_low_bits_mask (niter_type
,
387 (TYPE_PRECISION (niter_type
)
388 - tree_low_cst (bits
, 1)));
390 assumption
= fold (build2 (FLOOR_MOD_EXPR
, niter_type
, base1
, d
));
391 assumption
= fold (build2 (EQ_EXPR
, boolean_type_node
,
393 build_int_cst (niter_type
, 0)));
394 assumptions
= fold (build2 (TRUTH_AND_EXPR
, boolean_type_node
,
395 assumptions
, assumption
));
397 tmp
= fold (build2 (EXACT_DIV_EXPR
, niter_type
, base1
, d
));
398 tmp
= fold (build2 (MULT_EXPR
, niter_type
, tmp
, inverse (s
, bound
)));
399 niter
->niter
= fold (build2 (BIT_AND_EXPR
, niter_type
, tmp
, bound
));
404 /* Condition in shape a + s * i <= b
405 We must know that b + s does not overflow and a <= b + s and then we
406 can compute number of iterations as (b + s - a) / s. (It might
407 seem that we in fact could be more clever about testing the b + s
408 overflow condition using some information about b - a mod s,
409 but it was already taken into account during LE -> NE transform). */
413 bound
= fold_binary_to_constant (MINUS_EXPR
, type
, mmax
, step0
);
414 assumption
= fold (build2 (LE_EXPR
, boolean_type_node
,
416 assumptions
= fold (build2 (TRUTH_AND_EXPR
, boolean_type_node
,
417 assumptions
, assumption
));
421 tmp
= fold (build2 (PLUS_EXPR
, type
, base1
, step0
));
422 assumption
= fold (build2 (GT_EXPR
, boolean_type_node
, base0
, tmp
));
423 delta
= fold (build2 (PLUS_EXPR
, type
, base1
, step
));
424 delta
= fold (build2 (MINUS_EXPR
, type
, delta
, base0
));
425 delta
= fold_convert (niter_type
, delta
);
429 /* Condition in shape a <= b - s * i
430 We must know that a - s does not overflow and a - s <= b and then
431 we can again compute number of iterations as (b - (a - s)) / s. */
434 bound
= fold_binary_to_constant (MINUS_EXPR
, type
, mmin
, step1
);
435 assumption
= fold (build2 (LE_EXPR
, boolean_type_node
,
437 assumptions
= fold (build2 (TRUTH_AND_EXPR
, boolean_type_node
,
438 assumptions
, assumption
));
440 step
= fold (build1 (NEGATE_EXPR
, type
, step1
));
441 tmp
= fold (build2 (PLUS_EXPR
, type
, base0
, step1
));
442 assumption
= fold (build2 (GT_EXPR
, boolean_type_node
, tmp
, base1
));
443 delta
= fold (build2 (MINUS_EXPR
, type
, base0
, step
));
444 delta
= fold (build2 (MINUS_EXPR
, type
, base1
, delta
));
445 delta
= fold_convert (niter_type
, delta
);
447 noloop_assumptions
= fold (build2 (TRUTH_OR_EXPR
, boolean_type_node
,
448 noloop_assumptions
, assumption
));
449 delta
= fold (build2 (FLOOR_DIV_EXPR
, niter_type
, delta
,
450 fold_convert (niter_type
, step
)));
451 niter
->niter
= delta
;
454 niter
->assumptions
= assumptions
;
455 niter
->may_be_zero
= noloop_assumptions
;
459 niter
->assumptions
= boolean_true_node
;
460 niter
->may_be_zero
= boolean_true_node
;
461 niter
->niter
= build_int_cst_type (type
, 0);
465 /* Tries to simplify EXPR using the evolutions of the loop invariants
466 in the superloops of LOOP. Returns the simplified expression
467 (or EXPR unchanged, if no simplification was possible). */
470 simplify_using_outer_evolutions (struct loop
*loop
, tree expr
)
472 enum tree_code code
= TREE_CODE (expr
);
476 if (is_gimple_min_invariant (expr
))
479 if (code
== TRUTH_OR_EXPR
480 || code
== TRUTH_AND_EXPR
481 || code
== COND_EXPR
)
485 e0
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 0));
486 if (TREE_OPERAND (expr
, 0) != e0
)
489 e1
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 1));
490 if (TREE_OPERAND (expr
, 1) != e1
)
493 if (code
== COND_EXPR
)
495 e2
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 2));
496 if (TREE_OPERAND (expr
, 2) != e2
)
504 if (code
== COND_EXPR
)
505 expr
= build3 (code
, boolean_type_node
, e0
, e1
, e2
);
507 expr
= build2 (code
, boolean_type_node
, e0
, e1
);
514 e
= instantiate_parameters (loop
, expr
);
515 if (is_gimple_min_invariant (e
))
521 /* Substitute NEW for OLD in EXPR and fold the result. */
524 simplify_replace_tree (tree expr
, tree old
, tree
new)
527 tree ret
= NULL_TREE
, e
, se
;
533 || operand_equal_p (expr
, old
, 0))
534 return unshare_expr (new);
539 n
= TREE_CODE_LENGTH (TREE_CODE (expr
));
540 for (i
= 0; i
< n
; i
++)
542 e
= TREE_OPERAND (expr
, i
);
543 se
= simplify_replace_tree (e
, old
, new);
548 ret
= copy_node (expr
);
550 TREE_OPERAND (ret
, i
) = se
;
553 return (ret
? fold (ret
) : expr
);
556 /* Tries to simplify EXPR using the condition COND. Returns the simplified
557 expression (or EXPR unchanged, if no simplification was possible).*/
560 tree_simplify_using_condition (tree cond
, tree expr
)
563 tree e
, e0
, e1
, e2
, notcond
;
564 enum tree_code code
= TREE_CODE (expr
);
566 if (code
== INTEGER_CST
)
569 if (code
== TRUTH_OR_EXPR
570 || code
== TRUTH_AND_EXPR
571 || code
== COND_EXPR
)
575 e0
= tree_simplify_using_condition (cond
, TREE_OPERAND (expr
, 0));
576 if (TREE_OPERAND (expr
, 0) != e0
)
579 e1
= tree_simplify_using_condition (cond
, TREE_OPERAND (expr
, 1));
580 if (TREE_OPERAND (expr
, 1) != e1
)
583 if (code
== COND_EXPR
)
585 e2
= tree_simplify_using_condition (cond
, TREE_OPERAND (expr
, 2));
586 if (TREE_OPERAND (expr
, 2) != e2
)
594 if (code
== COND_EXPR
)
595 expr
= build3 (code
, boolean_type_node
, e0
, e1
, e2
);
597 expr
= build2 (code
, boolean_type_node
, e0
, e1
);
604 /* In case COND is equality, we may be able to simplify EXPR by copy/constant
605 propagation, and vice versa. Fold does not handle this, since it is
606 considered too expensive. */
607 if (TREE_CODE (cond
) == EQ_EXPR
)
609 e0
= TREE_OPERAND (cond
, 0);
610 e1
= TREE_OPERAND (cond
, 1);
612 /* We know that e0 == e1. Check whether we cannot simplify expr
614 e
= simplify_replace_tree (expr
, e0
, e1
);
615 if (zero_p (e
) || nonzero_p (e
))
618 e
= simplify_replace_tree (expr
, e1
, e0
);
619 if (zero_p (e
) || nonzero_p (e
))
622 if (TREE_CODE (expr
) == EQ_EXPR
)
624 e0
= TREE_OPERAND (expr
, 0);
625 e1
= TREE_OPERAND (expr
, 1);
627 /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
628 e
= simplify_replace_tree (cond
, e0
, e1
);
631 e
= simplify_replace_tree (cond
, e1
, e0
);
635 if (TREE_CODE (expr
) == NE_EXPR
)
637 e0
= TREE_OPERAND (expr
, 0);
638 e1
= TREE_OPERAND (expr
, 1);
640 /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
641 e
= simplify_replace_tree (cond
, e0
, e1
);
643 return boolean_true_node
;
644 e
= simplify_replace_tree (cond
, e1
, e0
);
646 return boolean_true_node
;
649 /* Check whether COND ==> EXPR. */
650 notcond
= invert_truthvalue (cond
);
651 e
= fold (build2 (TRUTH_OR_EXPR
, boolean_type_node
,
656 /* Check whether COND ==> not EXPR. */
657 e
= fold (build2 (TRUTH_AND_EXPR
, boolean_type_node
,
665 /* Tries to simplify EXPR using the conditions on entry to LOOP.
666 Record the conditions used for simplification to CONDS_USED.
667 Returns the simplified expression (or EXPR unchanged, if no
668 simplification was possible).*/
671 simplify_using_initial_conditions (struct loop
*loop
, tree expr
,
678 if (TREE_CODE (expr
) == INTEGER_CST
)
681 for (bb
= loop
->header
;
682 bb
!= ENTRY_BLOCK_PTR
;
683 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
685 if (!single_pred_p (bb
))
687 e
= single_pred_edge (bb
);
689 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
692 cond
= COND_EXPR_COND (last_stmt (e
->src
));
693 if (e
->flags
& EDGE_FALSE_VALUE
)
694 cond
= invert_truthvalue (cond
);
695 exp
= tree_simplify_using_condition (cond
, expr
);
698 *conds_used
= fold (build2 (TRUTH_AND_EXPR
,
709 /* Stores description of number of iterations of LOOP derived from
710 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
711 useful information could be derived (and fields of NITER has
712 meaning described in comments at struct tree_niter_desc
713 declaration), false otherwise. */
716 number_of_iterations_exit (struct loop
*loop
, edge exit
,
717 struct tree_niter_desc
*niter
)
719 tree stmt
, cond
, type
;
720 tree op0
, base0
, step0
;
721 tree op1
, base1
, step1
;
724 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit
->src
))
727 niter
->assumptions
= boolean_false_node
;
728 stmt
= last_stmt (exit
->src
);
729 if (!stmt
|| TREE_CODE (stmt
) != COND_EXPR
)
732 /* We want the condition for staying inside loop. */
733 cond
= COND_EXPR_COND (stmt
);
734 if (exit
->flags
& EDGE_TRUE_VALUE
)
735 cond
= invert_truthvalue (cond
);
737 code
= TREE_CODE (cond
);
751 op0
= TREE_OPERAND (cond
, 0);
752 op1
= TREE_OPERAND (cond
, 1);
753 type
= TREE_TYPE (op0
);
755 if (TREE_CODE (type
) != INTEGER_TYPE
756 && !POINTER_TYPE_P (type
))
759 if (!simple_iv (loop
, stmt
, op0
, &base0
, &step0
))
761 if (!simple_iv (loop
, stmt
, op1
, &base1
, &step1
))
764 niter
->niter
= NULL_TREE
;
765 number_of_iterations_cond (type
, base0
, step0
, code
, base1
, step1
,
770 niter
->assumptions
= simplify_using_outer_evolutions (loop
,
772 niter
->may_be_zero
= simplify_using_outer_evolutions (loop
,
774 niter
->niter
= simplify_using_outer_evolutions (loop
, niter
->niter
);
776 niter
->additional_info
= boolean_true_node
;
778 = simplify_using_initial_conditions (loop
,
780 &niter
->additional_info
);
782 = simplify_using_initial_conditions (loop
,
784 &niter
->additional_info
);
785 return integer_onep (niter
->assumptions
);
788 /* Try to determine the number of iterations of LOOP. If we succeed,
789 expression giving number of iterations is returned and *EXIT is
790 set to the edge from that the information is obtained. Otherwise
791 chrec_dont_know is returned. */
794 find_loop_niter (struct loop
*loop
, edge
*exit
)
797 edge
*exits
= get_loop_exit_edges (loop
, &n_exits
);
799 tree niter
= NULL_TREE
, aniter
;
800 struct tree_niter_desc desc
;
803 for (i
= 0; i
< n_exits
; i
++)
806 if (!just_once_each_iteration_p (loop
, ex
->src
))
809 if (!number_of_iterations_exit (loop
, ex
, &desc
))
812 if (nonzero_p (desc
.may_be_zero
))
814 /* We exit in the first iteration through this exit.
815 We won't find anything better. */
816 niter
= build_int_cst_type (unsigned_type_node
, 0);
821 if (!zero_p (desc
.may_be_zero
))
828 /* Nothing recorded yet. */
834 /* Prefer constants, the lower the better. */
835 if (TREE_CODE (aniter
) != INTEGER_CST
)
838 if (TREE_CODE (niter
) != INTEGER_CST
)
845 if (tree_int_cst_lt (aniter
, niter
))
854 return niter
? niter
: chrec_dont_know
;
859 Analysis of a number of iterations of a loop by a brute-force evaluation.
863 /* Bound on the number of iterations we try to evaluate. */
865 #define MAX_ITERATIONS_TO_TRACK \
866 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
868 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
869 result by a chain of operations such that all but exactly one of their
870 operands are constants. */
873 chain_of_csts_start (struct loop
*loop
, tree x
)
875 tree stmt
= SSA_NAME_DEF_STMT (x
);
876 basic_block bb
= bb_for_stmt (stmt
);
880 || !flow_bb_inside_loop_p (loop
, bb
))
883 if (TREE_CODE (stmt
) == PHI_NODE
)
885 if (bb
== loop
->header
)
891 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
894 get_stmt_operands (stmt
);
895 if (NUM_VUSES (STMT_VUSE_OPS (stmt
)) > 0)
897 if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt
)) > 0)
899 if (NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt
)) > 0)
901 if (NUM_DEFS (STMT_DEF_OPS (stmt
)) > 1)
903 uses
= STMT_USE_OPS (stmt
);
904 if (NUM_USES (uses
) != 1)
907 return chain_of_csts_start (loop
, USE_OP (uses
, 0));
910 /* Determines whether the expression X is derived from a result of a phi node
911 in header of LOOP such that
913 * the derivation of X consists only from operations with constants
914 * the initial value of the phi node is constant
915 * the value of the phi node in the next iteration can be derived from the
916 value in the current iteration by a chain of operations with constants.
918 If such phi node exists, it is returned. If X is a constant, X is returned
919 unchanged. Otherwise NULL_TREE is returned. */
922 get_base_for (struct loop
*loop
, tree x
)
924 tree phi
, init
, next
;
926 if (is_gimple_min_invariant (x
))
929 phi
= chain_of_csts_start (loop
, x
);
933 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
934 next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
936 if (TREE_CODE (next
) != SSA_NAME
)
939 if (!is_gimple_min_invariant (init
))
942 if (chain_of_csts_start (loop
, next
) != phi
)
948 /* Given an expression X, then
950 * if BASE is NULL_TREE, X must be a constant and we return X.
951 * otherwise X is a SSA name, whose value in the considered loop is derived
952 by a chain of operations with constant from a result of a phi node in
953 the header of the loop. Then we return value of X when the value of the
954 result of this phi node is given by the constant BASE. */
957 get_val_for (tree x
, tree base
)
966 stmt
= SSA_NAME_DEF_STMT (x
);
967 if (TREE_CODE (stmt
) == PHI_NODE
)
970 uses
= STMT_USE_OPS (stmt
);
971 op
= USE_OP_PTR (uses
, 0);
973 nx
= USE_FROM_PTR (op
);
974 val
= get_val_for (nx
, base
);
976 val
= fold (TREE_OPERAND (stmt
, 1));
982 /* Tries to count the number of iterations of LOOP till it exits by EXIT
983 by brute force -- i.e. by determining the value of the operands of the
984 condition at EXIT in first few iterations of the loop (assuming that
985 these values are constant) and determining the first one in that the
986 condition is not satisfied. Returns the constant giving the number
987 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
990 loop_niter_by_eval (struct loop
*loop
, edge exit
)
992 tree cond
, cnd
, acnd
;
993 tree op
[2], val
[2], next
[2], aval
[2], phi
[2];
997 cond
= last_stmt (exit
->src
);
998 if (!cond
|| TREE_CODE (cond
) != COND_EXPR
)
999 return chrec_dont_know
;
1001 cnd
= COND_EXPR_COND (cond
);
1002 if (exit
->flags
& EDGE_TRUE_VALUE
)
1003 cnd
= invert_truthvalue (cnd
);
1005 cmp
= TREE_CODE (cnd
);
1014 for (j
= 0; j
< 2; j
++)
1015 op
[j
] = TREE_OPERAND (cnd
, j
);
1019 return chrec_dont_know
;
1022 for (j
= 0; j
< 2; j
++)
1024 phi
[j
] = get_base_for (loop
, op
[j
]);
1026 return chrec_dont_know
;
1029 for (j
= 0; j
< 2; j
++)
1031 if (TREE_CODE (phi
[j
]) == PHI_NODE
)
1033 val
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
[j
], loop_preheader_edge (loop
));
1034 next
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
[j
], loop_latch_edge (loop
));
1039 next
[j
] = NULL_TREE
;
1044 for (i
= 0; i
< MAX_ITERATIONS_TO_TRACK
; i
++)
1046 for (j
= 0; j
< 2; j
++)
1047 aval
[j
] = get_val_for (op
[j
], val
[j
]);
1049 acnd
= fold (build2 (cmp
, boolean_type_node
, aval
[0], aval
[1]));
1052 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1054 "Proved that loop %d iterates %d times using brute force.\n",
1056 return build_int_cst (unsigned_type_node
, i
);
1059 for (j
= 0; j
< 2; j
++)
1060 val
[j
] = get_val_for (next
[j
], val
[j
]);
1063 return chrec_dont_know
;
1066 /* Finds the exit of the LOOP by that the loop exits after a constant
1067 number of iterations and stores the exit edge to *EXIT. The constant
1068 giving the number of iterations of LOOP is returned. The number of
1069 iterations is determined using loop_niter_by_eval (i.e. by brute force
1070 evaluation). If we are unable to find the exit for that loop_niter_by_eval
1071 determines the number of iterations, chrec_dont_know is returned. */
1074 find_loop_niter_by_eval (struct loop
*loop
, edge
*exit
)
1076 unsigned n_exits
, i
;
1077 edge
*exits
= get_loop_exit_edges (loop
, &n_exits
);
1079 tree niter
= NULL_TREE
, aniter
;
1082 for (i
= 0; i
< n_exits
; i
++)
1085 if (!just_once_each_iteration_p (loop
, ex
->src
))
1088 aniter
= loop_niter_by_eval (loop
, ex
);
1089 if (chrec_contains_undetermined (aniter
))
1093 && !tree_int_cst_lt (aniter
, niter
))
1101 return niter
? niter
: chrec_dont_know
;
1106 Analysis of upper bounds on number of iterations of a loop.
1110 /* Records that AT_STMT is executed at most BOUND times in LOOP. The
1111 additional condition ADDITIONAL is recorded with the bound. */
1114 record_estimate (struct loop
*loop
, tree bound
, tree additional
, tree at_stmt
)
1116 struct nb_iter_bound
*elt
= xmalloc (sizeof (struct nb_iter_bound
));
1118 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1120 fprintf (dump_file
, "Statements after ");
1121 print_generic_expr (dump_file
, at_stmt
, TDF_SLIM
);
1122 fprintf (dump_file
, " are executed at most ");
1123 print_generic_expr (dump_file
, bound
, TDF_SLIM
);
1124 fprintf (dump_file
, " times in loop %d.\n", loop
->num
);
1128 elt
->at_stmt
= at_stmt
;
1129 elt
->additional
= additional
;
1130 elt
->next
= loop
->bounds
;
1134 /* Records estimates on numbers of iterations of LOOP. */
1137 estimate_numbers_of_iterations_loop (struct loop
*loop
)
1141 unsigned i
, n_exits
;
1142 struct tree_niter_desc niter_desc
;
1144 exits
= get_loop_exit_edges (loop
, &n_exits
);
1145 for (i
= 0; i
< n_exits
; i
++)
1147 if (!number_of_iterations_exit (loop
, exits
[i
], &niter_desc
))
1150 niter
= niter_desc
.niter
;
1151 type
= TREE_TYPE (niter
);
1152 if (!zero_p (niter_desc
.may_be_zero
)
1153 && !nonzero_p (niter_desc
.may_be_zero
))
1154 niter
= build3 (COND_EXPR
, type
, niter_desc
.may_be_zero
,
1155 build_int_cst_type (type
, 0),
1157 record_estimate (loop
, niter
,
1158 niter_desc
.additional_info
,
1159 last_stmt (exits
[i
]->src
));
1163 /* Analyzes the bounds of arrays accessed in the loop. */
1164 if (loop
->estimated_nb_iterations
== NULL_TREE
)
1166 varray_type datarefs
;
1167 VARRAY_GENERIC_PTR_INIT (datarefs
, 3, "datarefs");
1168 find_data_references_in_loop (loop
, &datarefs
);
1169 free_data_refs (datarefs
);
1173 /* Records estimates on numbers of iterations of LOOPS. */
1176 estimate_numbers_of_iterations (struct loops
*loops
)
1181 for (i
= 1; i
< loops
->num
; i
++)
1183 loop
= loops
->parray
[i
];
1185 estimate_numbers_of_iterations_loop (loop
);
1189 /* If A > B, returns -1. If A == B, returns 0. If A < B, returns 1.
1190 If neither of these relations can be proved, returns 2. */
1193 compare_trees (tree a
, tree b
)
1195 tree typea
= TREE_TYPE (a
), typeb
= TREE_TYPE (b
);
1198 if (TYPE_PRECISION (typea
) > TYPE_PRECISION (typeb
))
1203 a
= fold_convert (type
, a
);
1204 b
= fold_convert (type
, b
);
1206 if (nonzero_p (fold (build2 (EQ_EXPR
, boolean_type_node
, a
, b
))))
1208 if (nonzero_p (fold (build2 (LT_EXPR
, boolean_type_node
, a
, b
))))
1210 if (nonzero_p (fold (build2 (GT_EXPR
, boolean_type_node
, a
, b
))))
1216 /* Returns true if statement S1 dominates statement S2. */
1219 stmt_dominates_stmt_p (tree s1
, tree s2
)
1221 basic_block bb1
= bb_for_stmt (s1
), bb2
= bb_for_stmt (s2
);
1229 block_stmt_iterator bsi
;
1231 for (bsi
= bsi_start (bb1
); bsi_stmt (bsi
) != s2
; bsi_next (&bsi
))
1232 if (bsi_stmt (bsi
) == s1
)
1238 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
1241 /* Checks whether it is correct to count the induction variable BASE + STEP * I
1242 at AT_STMT in wider TYPE, using the fact that statement OF is executed at
1243 most BOUND times in the loop. If it is possible, return the value of step
1244 of the induction variable in the TYPE, otherwise return NULL_TREE.
1246 ADDITIONAL is the additional condition recorded for operands of the bound.
1247 This is useful in the following case, created by loop header copying:
1256 If the n > 0 condition is taken into account, the number of iterations of the
1257 loop can be expressed as n - 1. If the type of n is signed, the ADDITIONAL
1258 assumption "n > 0" says us that the value of the number of iterations is at
1259 most MAX_TYPE - 1 (without this assumption, it might overflow). */
1262 can_count_iv_in_wider_type_bound (tree type
, tree base
, tree step
,
1268 tree inner_type
= TREE_TYPE (base
), b
, bplusstep
, new_step
, new_step_abs
;
1269 tree valid_niter
, extreme
, unsigned_type
, delta
, bound_type
;
1272 b
= fold_convert (type
, base
);
1273 bplusstep
= fold_convert (type
,
1274 fold (build2 (PLUS_EXPR
, inner_type
, base
, step
)));
1275 new_step
= fold (build2 (MINUS_EXPR
, type
, bplusstep
, b
));
1276 if (TREE_CODE (new_step
) != INTEGER_CST
)
1279 switch (compare_trees (bplusstep
, b
))
1282 extreme
= upper_bound_in_type (type
, inner_type
);
1283 delta
= fold (build2 (MINUS_EXPR
, type
, extreme
, b
));
1284 new_step_abs
= new_step
;
1288 extreme
= lower_bound_in_type (type
, inner_type
);
1289 new_step_abs
= fold (build1 (NEGATE_EXPR
, type
, new_step
));
1290 delta
= fold (build2 (MINUS_EXPR
, type
, b
, extreme
));
1300 unsigned_type
= unsigned_type_for (type
);
1301 delta
= fold_convert (unsigned_type
, delta
);
1302 new_step_abs
= fold_convert (unsigned_type
, new_step_abs
);
1303 valid_niter
= fold (build2 (FLOOR_DIV_EXPR
, unsigned_type
,
1304 delta
, new_step_abs
));
1306 bound_type
= TREE_TYPE (bound
);
1307 if (TYPE_PRECISION (type
) > TYPE_PRECISION (bound_type
))
1308 bound
= fold_convert (unsigned_type
, bound
);
1310 valid_niter
= fold_convert (bound_type
, valid_niter
);
1312 if (at_stmt
&& stmt_dominates_stmt_p (of
, at_stmt
))
1314 /* After the statement OF we know that anything is executed at most
1316 cond
= build2 (GE_EXPR
, boolean_type_node
, valid_niter
, bound
);
1320 /* Before the statement OF we know that anything is executed at most
1322 cond
= build2 (GT_EXPR
, boolean_type_node
, valid_niter
, bound
);
1326 if (nonzero_p (cond
))
1329 /* Try taking additional conditions into account. */
1330 cond
= build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1331 invert_truthvalue (additional
),
1334 if (nonzero_p (cond
))
1340 /* Checks whether it is correct to count the induction variable BASE + STEP * I
1341 at AT_STMT in wider TYPE, using the bounds on numbers of iterations of a
1342 LOOP. If it is possible, return the value of step of the induction variable
1343 in the TYPE, otherwise return NULL_TREE. */
1346 can_count_iv_in_wider_type (struct loop
*loop
, tree type
, tree base
, tree step
,
1349 struct nb_iter_bound
*bound
;
1352 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
1354 new_step
= can_count_iv_in_wider_type_bound (type
, base
, step
,
1367 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
1370 free_numbers_of_iterations_estimates_loop (struct loop
*loop
)
1372 struct nb_iter_bound
*bound
, *next
;
1374 for (bound
= loop
->bounds
; bound
; bound
= next
)
1380 loop
->bounds
= NULL
;
1383 /* Frees the information on upper bounds on numbers of iterations of LOOPS. */
1386 free_numbers_of_iterations_estimates (struct loops
*loops
)
1391 for (i
= 1; i
< loops
->num
; i
++)
1393 loop
= loops
->parray
[i
];
1395 free_numbers_of_iterations_estimates_loop (loop
);