1 /* Functions to determine/estimate number of iterations of a loop.
2 Copyright (C) 2004 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"
41 #include "tree-inline.h"
43 #define SWAP(X, Y) do { void *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
45 /* Just to shorten the ugly names. */
46 #define EXEC_BINARY nondestructive_fold_binary_to_constant
47 #define EXEC_UNARY nondestructive_fold_unary_to_constant
51 Analysis of number of iterations of an affine exit test.
55 /* Returns true if ARG is either NULL_TREE or constant zero. */
63 return integer_zerop (arg
);
66 /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
69 inverse (tree x
, tree mask
)
71 tree type
= TREE_TYPE (x
);
72 tree ctr
= EXEC_BINARY (RSHIFT_EXPR
, type
, mask
, integer_one_node
);
73 tree rslt
= convert (type
, integer_one_node
);
75 while (integer_nonzerop (ctr
))
77 rslt
= EXEC_BINARY (MULT_EXPR
, type
, rslt
, x
);
78 rslt
= EXEC_BINARY (BIT_AND_EXPR
, type
, rslt
, mask
);
79 x
= EXEC_BINARY (MULT_EXPR
, type
, x
, x
);
80 x
= EXEC_BINARY (BIT_AND_EXPR
, type
, x
, mask
);
81 ctr
= EXEC_BINARY (RSHIFT_EXPR
, type
, ctr
, integer_one_node
);
87 /* Determine the number of iterations according to condition (for staying
88 inside loop) which compares two induction variables using comparison
89 operator CODE. The induction variable on left side of the comparison
90 has base BASE0 and step STEP0. the right-hand side one has base
91 BASE1 and step STEP1. Both induction variables must have type TYPE,
92 which must be an integer or pointer type. STEP0 and STEP1 must be
93 constants (or NULL_TREE, which is interpreted as constant zero).
95 The results (number of iterations and assumptions as described in
96 comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
97 In case we are unable to determine number of iterations, contents of
98 this structure is unchanged. */
101 number_of_iterations_cond (tree type
, tree base0
, tree step0
,
102 enum tree_code code
, tree base1
, tree step1
,
103 struct tree_niter_desc
*niter
)
105 tree step
, delta
, mmin
, mmax
;
106 tree may_xform
, bound
, s
, d
, tmp
;
107 bool was_sharp
= false;
109 tree assumptions
= boolean_true_node
;
110 tree noloop_assumptions
= boolean_false_node
;
111 tree niter_type
, signed_niter_type
;
113 /* The meaning of these assumptions is this:
115 then the rest of information does not have to be valid
116 if noloop_assumptions then the loop does not have to roll
117 (but it is only conservative approximation, i.e. it only says that
118 if !noloop_assumptions, then the loop does not end before the computed
119 number of iterations) */
121 /* Make < comparison from > ones. */
127 code
= swap_tree_comparison (code
);
130 /* We can handle the case when neither of the sides of the comparison is
131 invariant, provided that the test is NE_EXPR. This rarely occurs in
132 practice, but it is simple enough to manage. */
133 if (!zero_p (step0
) && !zero_p (step1
))
138 step0
= EXEC_BINARY (MINUS_EXPR
, type
, step0
, step1
);
142 /* If the result is a constant, the loop is weird. More precise handling
143 would be possible, but the situation is not common enough to waste time
145 if (zero_p (step0
) && zero_p (step1
))
148 /* Ignore loops of while (i-- < 10) type. */
151 if (step0
&& !tree_expr_nonnegative_p (step0
))
154 if (!zero_p (step1
) && tree_expr_nonnegative_p (step1
))
158 if (POINTER_TYPE_P (type
))
160 /* We assume pointer arithmetic never overflows. */
161 mmin
= mmax
= NULL_TREE
;
165 mmin
= TYPE_MIN_VALUE (type
);
166 mmax
= TYPE_MAX_VALUE (type
);
169 /* Some more condition normalization. We must record some assumptions
174 /* We want to take care only of <=; this is easy,
175 as in cases the overflow would make the transformation unsafe the loop
176 does not roll. Seemingly it would make more sense to want to take
177 care of <, as NE is more similar to it, but the problem is that here
178 the transformation would be more difficult due to possibly infinite
183 assumption
= fold (build (EQ_EXPR
, boolean_type_node
, base0
, mmax
));
185 assumption
= boolean_false_node
;
186 if (integer_nonzerop (assumption
))
188 base0
= fold (build (PLUS_EXPR
, type
, base0
,
189 convert (type
, integer_one_node
)));
194 assumption
= fold (build (EQ_EXPR
, boolean_type_node
, base1
, mmin
));
196 assumption
= boolean_false_node
;
197 if (integer_nonzerop (assumption
))
199 base1
= fold (build (MINUS_EXPR
, type
, base1
,
200 convert (type
, integer_one_node
)));
202 noloop_assumptions
= assumption
;
205 /* It will be useful to be able to tell the difference once more in
206 <= -> != reduction. */
210 /* Take care of trivially infinite loops. */
215 && operand_equal_p (base0
, mmin
, 0))
219 && operand_equal_p (base1
, mmax
, 0))
223 /* If we can we want to take care of NE conditions instead of size
224 comparisons, as they are much more friendly (most importantly
225 this takes care of special handling of loops with step 1). We can
226 do it if we first check that upper bound is greater or equal to
227 lower bound, their difference is constant c modulo step and that
228 there is not an overflow. */
232 step
= EXEC_UNARY (NEGATE_EXPR
, type
, step1
);
235 delta
= build (MINUS_EXPR
, type
, base1
, base0
);
236 delta
= fold (build (FLOOR_MOD_EXPR
, type
, delta
, step
));
237 may_xform
= boolean_false_node
;
239 if (TREE_CODE (delta
) == INTEGER_CST
)
241 tmp
= EXEC_BINARY (MINUS_EXPR
, type
, step
,
242 convert (type
, integer_one_node
));
244 && operand_equal_p (delta
, tmp
, 0))
246 /* A special case. We have transformed condition of type
247 for (i = 0; i < 4; i += 4)
249 for (i = 0; i <= 3; i += 4)
250 obviously if the test for overflow during that transformation
251 passed, we cannot overflow here. Most importantly any
252 loop with sharp end condition and step 1 falls into this
253 category, so handling this case specially is definitely
254 worth the troubles. */
255 may_xform
= boolean_true_node
;
257 else if (zero_p (step0
))
260 may_xform
= boolean_true_node
;
263 bound
= EXEC_BINARY (PLUS_EXPR
, type
, mmin
, step
);
264 bound
= EXEC_BINARY (MINUS_EXPR
, type
, bound
, delta
);
265 may_xform
= fold (build (LE_EXPR
, boolean_type_node
,
272 may_xform
= boolean_true_node
;
275 bound
= EXEC_BINARY (MINUS_EXPR
, type
, mmax
, step
);
276 bound
= EXEC_BINARY (PLUS_EXPR
, type
, bound
, delta
);
277 may_xform
= fold (build (LE_EXPR
, boolean_type_node
,
283 if (!integer_zerop (may_xform
))
285 /* We perform the transformation always provided that it is not
286 completely senseless. This is OK, as we would need this assumption
287 to determine the number of iterations anyway. */
288 if (!integer_nonzerop (may_xform
))
289 assumptions
= may_xform
;
293 base0
= build (PLUS_EXPR
, type
, base0
, delta
);
294 base0
= fold (build (MINUS_EXPR
, type
, base0
, step
));
298 base1
= build (MINUS_EXPR
, type
, base1
, delta
);
299 base1
= fold (build (PLUS_EXPR
, type
, base1
, step
));
302 assumption
= fold (build (GT_EXPR
, boolean_type_node
, base0
, base1
));
303 noloop_assumptions
= fold (build (TRUTH_OR_EXPR
, boolean_type_node
,
304 noloop_assumptions
, assumption
));
309 /* Count the number of iterations. */
310 niter_type
= unsigned_type_for (type
);
311 signed_niter_type
= signed_type_for (type
);
315 /* Everything we do here is just arithmetics modulo size of mode. This
316 makes us able to do more involved computations of number of iterations
317 than in other cases. First transform the condition into shape
318 s * i <> c, with s positive. */
319 base1
= fold (build (MINUS_EXPR
, type
, base1
, base0
));
322 step0
= EXEC_UNARY (NEGATE_EXPR
, type
, step1
);
324 if (!tree_expr_nonnegative_p (convert (signed_niter_type
, step0
)))
326 step0
= EXEC_UNARY (NEGATE_EXPR
, type
, step0
);
327 base1
= fold (build1 (NEGATE_EXPR
, type
, base1
));
330 base1
= convert (niter_type
, base1
);
331 step0
= convert (niter_type
, step0
);
333 /* Let nsd (s, size of mode) = d. If d does not divide c, the loop
334 is infinite. Otherwise, the number of iterations is
335 (inverse(s/d) * (c/d)) mod (size of mode/d). */
337 d
= integer_one_node
;
338 bound
= convert (niter_type
, build_int_cst (NULL_TREE
, -1));
341 tmp
= EXEC_BINARY (BIT_AND_EXPR
, niter_type
, s
,
342 convert (niter_type
, integer_one_node
));
343 if (integer_nonzerop (tmp
))
346 s
= EXEC_BINARY (RSHIFT_EXPR
, niter_type
, s
,
347 convert (niter_type
, integer_one_node
));
348 d
= EXEC_BINARY (LSHIFT_EXPR
, niter_type
, d
,
349 convert (niter_type
, integer_one_node
));
350 bound
= EXEC_BINARY (RSHIFT_EXPR
, niter_type
, bound
,
351 convert (niter_type
, integer_one_node
));
354 assumption
= fold (build2 (FLOOR_MOD_EXPR
, niter_type
, base1
, d
));
355 assumption
= fold (build2 (EQ_EXPR
, boolean_type_node
,
357 build_int_cst (niter_type
, 0)));
358 assumptions
= fold (build2 (TRUTH_AND_EXPR
, boolean_type_node
,
359 assumptions
, assumption
));
361 tmp
= fold (build (EXACT_DIV_EXPR
, niter_type
, base1
, d
));
362 tmp
= fold (build (MULT_EXPR
, niter_type
, tmp
, inverse (s
, bound
)));
363 niter
->niter
= fold (build (BIT_AND_EXPR
, niter_type
, tmp
, bound
));
368 /* Condition in shape a + s * i <= b
369 We must know that b + s does not overflow and a <= b + s and then we
370 can compute number of iterations as (b + s - a) / s. (It might
371 seem that we in fact could be more clever about testing the b + s
372 overflow condition using some information about b - a mod s,
373 but it was already taken into account during LE -> NE transform). */
377 bound
= EXEC_BINARY (MINUS_EXPR
, type
, mmax
, step0
);
378 assumption
= fold (build (LE_EXPR
, boolean_type_node
,
380 assumptions
= fold (build (TRUTH_AND_EXPR
, boolean_type_node
,
381 assumptions
, assumption
));
385 tmp
= fold (build (PLUS_EXPR
, type
, base1
, step0
));
386 assumption
= fold (build (GT_EXPR
, boolean_type_node
, base0
, tmp
));
387 delta
= fold (build (PLUS_EXPR
, type
, base1
, step
));
388 delta
= fold (build (MINUS_EXPR
, type
, delta
, base0
));
389 delta
= convert (niter_type
, delta
);
393 /* Condition in shape a <= b - s * i
394 We must know that a - s does not overflow and a - s <= b and then
395 we can again compute number of iterations as (b - (a - s)) / s. */
398 bound
= EXEC_BINARY (MINUS_EXPR
, type
, mmin
, step1
);
399 assumption
= fold (build (LE_EXPR
, boolean_type_node
,
401 assumptions
= fold (build (TRUTH_AND_EXPR
, boolean_type_node
,
402 assumptions
, assumption
));
404 step
= fold (build1 (NEGATE_EXPR
, type
, step1
));
405 tmp
= fold (build (PLUS_EXPR
, type
, base0
, step1
));
406 assumption
= fold (build (GT_EXPR
, boolean_type_node
, tmp
, base1
));
407 delta
= fold (build (MINUS_EXPR
, type
, base0
, step
));
408 delta
= fold (build (MINUS_EXPR
, type
, base1
, delta
));
409 delta
= convert (niter_type
, delta
);
411 noloop_assumptions
= fold (build (TRUTH_OR_EXPR
, boolean_type_node
,
412 noloop_assumptions
, assumption
));
413 delta
= fold (build (FLOOR_DIV_EXPR
, niter_type
, delta
,
414 convert (niter_type
, step
)));
415 niter
->niter
= delta
;
418 niter
->assumptions
= assumptions
;
419 niter
->may_be_zero
= noloop_assumptions
;
423 niter
->assumptions
= boolean_true_node
;
424 niter
->may_be_zero
= boolean_true_node
;
425 niter
->niter
= convert (type
, integer_zero_node
);
429 /* Tries to simplify EXPR using the evolutions of the loop invariants
430 in the superloops of LOOP. Returns the simplified expression
431 (or EXPR unchanged, if no simplification was possible). */
434 simplify_using_outer_evolutions (struct loop
*loop
, tree expr
)
436 enum tree_code code
= TREE_CODE (expr
);
440 if (is_gimple_min_invariant (expr
))
443 if (code
== TRUTH_OR_EXPR
444 || code
== TRUTH_AND_EXPR
445 || code
== COND_EXPR
)
449 e0
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 0));
450 if (TREE_OPERAND (expr
, 0) != e0
)
453 e1
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 1));
454 if (TREE_OPERAND (expr
, 1) != e1
)
457 if (code
== COND_EXPR
)
459 e2
= simplify_using_outer_evolutions (loop
, TREE_OPERAND (expr
, 2));
460 if (TREE_OPERAND (expr
, 2) != e2
)
468 if (code
== COND_EXPR
)
469 expr
= build (code
, boolean_type_node
, e0
, e1
, e2
);
471 expr
= build (code
, boolean_type_node
, e0
, e1
);
478 e
= instantiate_parameters (loop
, expr
);
479 if (is_gimple_min_invariant (e
))
485 /* Tries to simplify EXPR using the condition COND. Returns the simplified
486 expression (or EXPR unchanged, if no simplification was possible).*/
489 tree_simplify_using_condition (tree cond
, tree expr
)
492 tree e
, e0
, e1
, e2
, notcond
;
493 enum tree_code code
= TREE_CODE (expr
);
495 if (code
== INTEGER_CST
)
498 if (code
== TRUTH_OR_EXPR
499 || code
== TRUTH_AND_EXPR
500 || code
== COND_EXPR
)
504 e0
= tree_simplify_using_condition (cond
, TREE_OPERAND (expr
, 0));
505 if (TREE_OPERAND (expr
, 0) != e0
)
508 e1
= tree_simplify_using_condition (cond
, TREE_OPERAND (expr
, 1));
509 if (TREE_OPERAND (expr
, 1) != e1
)
512 if (code
== COND_EXPR
)
514 e2
= tree_simplify_using_condition (cond
, TREE_OPERAND (expr
, 2));
515 if (TREE_OPERAND (expr
, 2) != e2
)
523 if (code
== COND_EXPR
)
524 expr
= build (code
, boolean_type_node
, e0
, e1
, e2
);
526 expr
= build (code
, boolean_type_node
, e0
, e1
);
533 /* Check whether COND ==> EXPR. */
534 notcond
= invert_truthvalue (cond
);
535 e
= fold (build (TRUTH_OR_EXPR
, boolean_type_node
,
537 if (integer_nonzerop (e
))
540 /* Check whether COND ==> not EXPR. */
541 e
= fold (build (TRUTH_AND_EXPR
, boolean_type_node
,
543 if (integer_zerop (e
))
549 /* Tries to simplify EXPR using the conditions on entry to LOOP.
550 Record the conditions used for simplification to CONDS_USED.
551 Returns the simplified expression (or EXPR unchanged, if no
552 simplification was possible).*/
555 simplify_using_initial_conditions (struct loop
*loop
, tree expr
,
562 if (TREE_CODE (expr
) == INTEGER_CST
)
565 for (bb
= loop
->header
;
566 bb
!= ENTRY_BLOCK_PTR
;
567 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
573 if (!(e
->flags
& (EDGE_TRUE_VALUE
| EDGE_FALSE_VALUE
)))
576 cond
= COND_EXPR_COND (last_stmt (e
->src
));
577 if (e
->flags
& EDGE_FALSE_VALUE
)
578 cond
= invert_truthvalue (cond
);
579 exp
= tree_simplify_using_condition (cond
, expr
);
582 *conds_used
= fold (build (TRUTH_AND_EXPR
,
593 /* Stores description of number of iterations of LOOP derived from
594 EXIT (an exit edge of the LOOP) in NITER. Returns true if some
595 useful information could be derived (and fields of NITER has
596 meaning described in comments at struct tree_niter_desc
597 declaration), false otherwise. */
600 number_of_iterations_exit (struct loop
*loop
, edge exit
,
601 struct tree_niter_desc
*niter
)
603 tree stmt
, cond
, type
;
604 tree op0
, base0
, step0
;
605 tree op1
, base1
, step1
;
608 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, exit
->src
))
611 niter
->assumptions
= boolean_false_node
;
612 stmt
= last_stmt (exit
->src
);
613 if (!stmt
|| TREE_CODE (stmt
) != COND_EXPR
)
616 /* We want the condition for staying inside loop. */
617 cond
= COND_EXPR_COND (stmt
);
618 if (exit
->flags
& EDGE_TRUE_VALUE
)
619 cond
= invert_truthvalue (cond
);
621 code
= TREE_CODE (cond
);
635 op0
= TREE_OPERAND (cond
, 0);
636 op1
= TREE_OPERAND (cond
, 1);
637 type
= TREE_TYPE (op0
);
639 if (TREE_CODE (type
) != INTEGER_TYPE
640 && !POINTER_TYPE_P (type
))
643 if (!simple_iv (loop
, stmt
, op0
, &base0
, &step0
))
645 if (!simple_iv (loop
, stmt
, op1
, &base1
, &step1
))
648 niter
->niter
= NULL_TREE
;
649 number_of_iterations_cond (type
, base0
, step0
, code
, base1
, step1
,
654 niter
->assumptions
= simplify_using_outer_evolutions (loop
,
656 niter
->may_be_zero
= simplify_using_outer_evolutions (loop
,
658 niter
->niter
= simplify_using_outer_evolutions (loop
, niter
->niter
);
660 niter
->additional_info
= boolean_true_node
;
662 = simplify_using_initial_conditions (loop
,
664 &niter
->additional_info
);
666 = simplify_using_initial_conditions (loop
,
668 &niter
->additional_info
);
669 return integer_onep (niter
->assumptions
);
674 Analysis of a number of iterations of a loop by a brute-force evaluation.
678 /* Bound on the number of iterations we try to evaluate. */
680 #define MAX_ITERATIONS_TO_TRACK \
681 ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
683 /* Returns the loop phi node of LOOP such that ssa name X is derived from its
684 result by a chain of operations such that all but exactly one of their
685 operands are constants. */
688 chain_of_csts_start (struct loop
*loop
, tree x
)
690 tree stmt
= SSA_NAME_DEF_STMT (x
);
691 basic_block bb
= bb_for_stmt (stmt
);
695 || !flow_bb_inside_loop_p (loop
, bb
))
698 if (TREE_CODE (stmt
) == PHI_NODE
)
700 if (bb
== loop
->header
)
706 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
709 get_stmt_operands (stmt
);
710 if (NUM_VUSES (STMT_VUSE_OPS (stmt
)) > 0)
712 if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt
)) > 0)
714 if (NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt
)) > 0)
716 if (NUM_DEFS (STMT_DEF_OPS (stmt
)) > 1)
718 uses
= STMT_USE_OPS (stmt
);
719 if (NUM_USES (uses
) != 1)
722 return chain_of_csts_start (loop
, USE_OP (uses
, 0));
725 /* Determines whether the expression X is derived from a result of a phi node
726 in header of LOOP such that
728 * the derivation of X consists only from operations with constants
729 * the initial value of the phi node is constant
730 * the value of the phi node in the next iteration can be derived from the
731 value in the current iteration by a chain of operations with constants.
733 If such phi node exists, it is returned. If X is a constant, X is returned
734 unchanged. Otherwise NULL_TREE is returned. */
737 get_base_for (struct loop
*loop
, tree x
)
739 tree phi
, init
, next
;
741 if (is_gimple_min_invariant (x
))
744 phi
= chain_of_csts_start (loop
, x
);
748 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
749 next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
751 if (TREE_CODE (next
) != SSA_NAME
)
754 if (!is_gimple_min_invariant (init
))
757 if (chain_of_csts_start (loop
, next
) != phi
)
763 /* Given an expression X, then
765 * if BASE is NULL_TREE, X must be a constant and we return X.
766 * otherwise X is a SSA name, whose value in the considered loop is derived
767 by a chain of operations with constant from a result of a phi node in
768 the header of the loop. Then we return value of X when the value of the
769 result of this phi node is given by the constant BASE. */
772 get_val_for (tree x
, tree base
)
781 stmt
= SSA_NAME_DEF_STMT (x
);
782 if (TREE_CODE (stmt
) == PHI_NODE
)
785 uses
= STMT_USE_OPS (stmt
);
786 op
= USE_OP_PTR (uses
, 0);
788 nx
= USE_FROM_PTR (op
);
789 val
= get_val_for (nx
, base
);
791 val
= fold (TREE_OPERAND (stmt
, 1));
797 /* Tries to count the number of iterations of LOOP till it exits by EXIT
798 by brute force -- i.e. by determining the value of the operands of the
799 condition at EXIT in first few iterations of the loop (assuming that
800 these values are constant) and determining the first one in that the
801 condition is not satisfied. Returns the constant giving the number
802 of the iterations of LOOP if successful, chrec_dont_know otherwise. */
805 loop_niter_by_eval (struct loop
*loop
, edge exit
)
807 tree cond
, cnd
, acnd
;
808 tree op
[2], val
[2], next
[2], aval
[2], phi
[2];
812 cond
= last_stmt (exit
->src
);
813 if (!cond
|| TREE_CODE (cond
) != COND_EXPR
)
814 return chrec_dont_know
;
816 cnd
= COND_EXPR_COND (cond
);
817 if (exit
->flags
& EDGE_TRUE_VALUE
)
818 cnd
= invert_truthvalue (cnd
);
820 cmp
= TREE_CODE (cnd
);
829 for (j
= 0; j
< 2; j
++)
830 op
[j
] = TREE_OPERAND (cnd
, j
);
834 return chrec_dont_know
;
837 for (j
= 0; j
< 2; j
++)
839 phi
[j
] = get_base_for (loop
, op
[j
]);
841 return chrec_dont_know
;
844 for (j
= 0; j
< 2; j
++)
846 if (TREE_CODE (phi
[j
]) == PHI_NODE
)
848 val
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
[j
], loop_preheader_edge (loop
));
849 next
[j
] = PHI_ARG_DEF_FROM_EDGE (phi
[j
], loop_latch_edge (loop
));
859 for (i
= 0; i
< MAX_ITERATIONS_TO_TRACK
; i
++)
861 for (j
= 0; j
< 2; j
++)
862 aval
[j
] = get_val_for (op
[j
], val
[j
]);
864 acnd
= fold (build (cmp
, boolean_type_node
, aval
[0], aval
[1]));
865 if (integer_zerop (acnd
))
867 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
869 "Proved that loop %d iterates %d times using brute force.\n",
871 return build_int_cst (unsigned_type_node
, i
);
874 for (j
= 0; j
< 2; j
++)
875 val
[j
] = get_val_for (next
[j
], val
[j
]);
878 return chrec_dont_know
;
881 /* Finds the exit of the LOOP by that the loop exits after a constant
882 number of iterations and stores the exit edge to *EXIT. The constant
883 giving the number of iterations of LOOP is returned. The number of
884 iterations is determined using loop_niter_by_eval (i.e. by brute force
885 evaluation). If we are unable to find the exit for that loop_niter_by_eval
886 determines the number of iterations, chrec_dont_know is returned. */
889 find_loop_niter_by_eval (struct loop
*loop
, edge
*exit
)
892 edge
*exits
= get_loop_exit_edges (loop
, &n_exits
);
894 tree niter
= NULL_TREE
, aniter
;
897 for (i
= 0; i
< n_exits
; i
++)
900 if (!just_once_each_iteration_p (loop
, ex
->src
))
903 aniter
= loop_niter_by_eval (loop
, ex
);
904 if (chrec_contains_undetermined (aniter
)
905 || TREE_CODE (aniter
) != INTEGER_CST
)
909 && !integer_nonzerop (fold (build (LT_EXPR
, boolean_type_node
,
918 return niter
? niter
: chrec_dont_know
;
923 Analysis of upper bounds on number of iterations of a loop.
927 /* The structure describing a bound on number of iterations of a loop. */
931 tree bound
; /* The expression whose value is an upper bound on the
932 number of executions of anything after ... */
933 tree at_stmt
; /* ... this statement during one execution of loop. */
934 tree additional
; /* A conjunction of conditions the operands of BOUND
935 satisfy. The additional information about the value
936 of the bound may be derived from it. */
937 struct nb_iter_bound
*next
;
938 /* The next bound in a list. */
941 /* Records that AT_STMT is executed at most BOUND times in LOOP. The
942 additional condition ADDITIONAL is recorded with the bound. */
945 record_estimate (struct loop
*loop
, tree bound
, tree additional
, tree at_stmt
)
947 struct nb_iter_bound
*elt
= xmalloc (sizeof (struct nb_iter_bound
));
949 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
951 fprintf (dump_file
, "Statements after ");
952 print_generic_expr (dump_file
, at_stmt
, TDF_SLIM
);
953 fprintf (dump_file
, " are executed at most ");
954 print_generic_expr (dump_file
, bound
, TDF_SLIM
);
955 fprintf (dump_file
, " times in loop %d.\n", loop
->num
);
959 elt
->at_stmt
= at_stmt
;
960 elt
->additional
= additional
;
961 elt
->next
= loop
->bounds
;
965 /* Records estimates on numbers of iterations of LOOP. */
968 estimate_numbers_of_iterations_loop (struct loop
*loop
)
973 struct tree_niter_desc niter_desc
;
975 exits
= get_loop_exit_edges (loop
, &n_exits
);
976 for (i
= 0; i
< n_exits
; i
++)
978 if (!number_of_iterations_exit (loop
, exits
[i
], &niter_desc
))
981 niter
= niter_desc
.niter
;
982 type
= TREE_TYPE (niter
);
983 if (!integer_zerop (niter_desc
.may_be_zero
)
984 && !integer_nonzerop (niter_desc
.may_be_zero
))
985 niter
= build (COND_EXPR
, type
, niter_desc
.may_be_zero
,
986 convert (type
, integer_zero_node
),
988 record_estimate (loop
, niter
,
989 niter_desc
.additional_info
,
990 last_stmt (exits
[i
]->src
));
994 /* TODO Here we could use other possibilities, like bounds of arrays accessed
998 /* Records estimates on numbers of iterations of LOOPS. */
1001 estimate_numbers_of_iterations (struct loops
*loops
)
1006 for (i
= 1; i
< loops
->num
; i
++)
1008 loop
= loops
->parray
[i
];
1010 estimate_numbers_of_iterations_loop (loop
);
1014 /* If A > B, returns -1. If A == B, returns 0. If A < B, returns 1.
1015 If neither of these relations can be proved, returns 2. */
1018 compare_trees (tree a
, tree b
)
1020 tree typea
= TREE_TYPE (a
), typeb
= TREE_TYPE (b
);
1023 if (TYPE_PRECISION (typea
) > TYPE_PRECISION (typeb
))
1028 a
= convert (type
, a
);
1029 b
= convert (type
, b
);
1031 if (integer_nonzerop (fold (build (EQ_EXPR
, boolean_type_node
, a
, b
))))
1033 if (integer_nonzerop (fold (build (LT_EXPR
, boolean_type_node
, a
, b
))))
1035 if (integer_nonzerop (fold (build (GT_EXPR
, boolean_type_node
, a
, b
))))
1041 /* Returns the largest value obtainable by casting something in INNER type to
1045 upper_bound_in_type (tree outer
, tree inner
)
1047 unsigned HOST_WIDE_INT lo
, hi
;
1048 unsigned bits
= TYPE_PRECISION (inner
);
1050 if (TYPE_UNSIGNED (outer
) || TYPE_UNSIGNED (inner
))
1052 /* Zero extending in these cases. */
1053 if (bits
<= HOST_BITS_PER_WIDE_INT
)
1056 lo
= (~(unsigned HOST_WIDE_INT
) 0)
1057 >> (HOST_BITS_PER_WIDE_INT
- bits
);
1061 hi
= (~(unsigned HOST_WIDE_INT
) 0)
1062 >> (2 * HOST_BITS_PER_WIDE_INT
- bits
);
1063 lo
= ~(unsigned HOST_WIDE_INT
) 0;
1068 /* Sign extending in these cases. */
1069 if (bits
<= HOST_BITS_PER_WIDE_INT
)
1072 lo
= (~(unsigned HOST_WIDE_INT
) 0)
1073 >> (HOST_BITS_PER_WIDE_INT
- bits
) >> 1;
1077 hi
= (~(unsigned HOST_WIDE_INT
) 0)
1078 >> (2 * HOST_BITS_PER_WIDE_INT
- bits
) >> 1;
1079 lo
= ~(unsigned HOST_WIDE_INT
) 0;
1083 return convert (outer
,
1085 build_int_cst_wide (NULL_TREE
, lo
, hi
)));
1088 /* Returns the smallest value obtainable by casting something in INNER type to
1092 lower_bound_in_type (tree outer
, tree inner
)
1094 unsigned HOST_WIDE_INT lo
, hi
;
1095 unsigned bits
= TYPE_PRECISION (inner
);
1097 if (TYPE_UNSIGNED (outer
) || TYPE_UNSIGNED (inner
))
1099 else if (bits
<= HOST_BITS_PER_WIDE_INT
)
1101 hi
= ~(unsigned HOST_WIDE_INT
) 0;
1102 lo
= (~(unsigned HOST_WIDE_INT
) 0) << (bits
- 1);
1106 hi
= (~(unsigned HOST_WIDE_INT
) 0) << (bits
- HOST_BITS_PER_WIDE_INT
- 1);
1110 return convert (outer
,
1112 build_int_cst_wide (NULL_TREE
, lo
, hi
)));
1115 /* Returns true if statement S1 dominates statement S2. */
1118 stmt_dominates_stmt_p (tree s1
, tree s2
)
1120 basic_block bb1
= bb_for_stmt (s1
), bb2
= bb_for_stmt (s2
);
1128 block_stmt_iterator bsi
;
1130 for (bsi
= bsi_start (bb1
); bsi_stmt (bsi
) != s2
; bsi_next (&bsi
))
1131 if (bsi_stmt (bsi
) == s1
)
1137 return dominated_by_p (CDI_DOMINATORS
, bb2
, bb1
);
1140 /* Checks whether it is correct to count the induction variable BASE + STEP * I
1141 at AT_STMT in wider TYPE, using the fact that statement OF is executed at
1142 most BOUND times in the loop. If it is possible, return the value of step
1143 of the induction variable in the TYPE, otherwise return NULL_TREE.
1145 ADDITIONAL is the additional condition recorded for operands of the bound.
1146 This is useful in the following case, created by loop header copying:
1155 If the n > 0 condition is taken into account, the number of iterations of the
1156 loop can be expressed as n - 1. If the type of n is signed, the ADDITIONAL
1157 assumption "n > 0" says us that the value of the number of iterations is at
1158 most MAX_TYPE - 1 (without this assumption, it might overflow). */
1161 can_count_iv_in_wider_type_bound (tree type
, tree base
, tree step
,
1167 tree inner_type
= TREE_TYPE (base
), b
, bplusstep
, new_step
, new_step_abs
;
1168 tree valid_niter
, extreme
, unsigned_type
, delta
, bound_type
;
1171 b
= convert (type
, base
);
1172 bplusstep
= convert (type
,
1173 fold (build (PLUS_EXPR
, inner_type
, base
, step
)));
1174 new_step
= fold (build (MINUS_EXPR
, type
, bplusstep
, b
));
1175 if (TREE_CODE (new_step
) != INTEGER_CST
)
1178 switch (compare_trees (bplusstep
, b
))
1181 extreme
= upper_bound_in_type (type
, inner_type
);
1182 delta
= fold (build (MINUS_EXPR
, type
, extreme
, b
));
1183 new_step_abs
= new_step
;
1187 extreme
= lower_bound_in_type (type
, inner_type
);
1188 new_step_abs
= fold (build (NEGATE_EXPR
, type
, new_step
));
1189 delta
= fold (build (MINUS_EXPR
, type
, b
, extreme
));
1199 unsigned_type
= unsigned_type_for (type
);
1200 delta
= convert (unsigned_type
, delta
);
1201 new_step_abs
= convert (unsigned_type
, new_step_abs
);
1202 valid_niter
= fold (build (FLOOR_DIV_EXPR
, unsigned_type
,
1203 delta
, new_step_abs
));
1205 bound_type
= TREE_TYPE (bound
);
1206 if (TYPE_PRECISION (type
) > TYPE_PRECISION (bound_type
))
1207 bound
= convert (unsigned_type
, bound
);
1209 valid_niter
= convert (bound_type
, valid_niter
);
1211 if (at_stmt
&& stmt_dominates_stmt_p (of
, at_stmt
))
1213 /* After the statement OF we know that anything is executed at most
1215 cond
= build (GE_EXPR
, boolean_type_node
, valid_niter
, bound
);
1219 /* Before the statement OF we know that anything is executed at most
1221 cond
= build (GT_EXPR
, boolean_type_node
, valid_niter
, bound
);
1225 if (integer_nonzerop (cond
))
1228 /* Try taking additional conditions into account. */
1229 cond
= build (TRUTH_OR_EXPR
, boolean_type_node
,
1230 invert_truthvalue (additional
),
1233 if (integer_nonzerop (cond
))
1239 /* Checks whether it is correct to count the induction variable BASE + STEP * I
1240 at AT_STMT in wider TYPE, using the bounds on numbers of iterations of a
1241 LOOP. If it is possible, return the value of step of the induction variable
1242 in the TYPE, otherwise return NULL_TREE. */
1245 can_count_iv_in_wider_type (struct loop
*loop
, tree type
, tree base
, tree step
,
1248 struct nb_iter_bound
*bound
;
1251 for (bound
= loop
->bounds
; bound
; bound
= bound
->next
)
1253 new_step
= can_count_iv_in_wider_type_bound (type
, base
, step
,
1266 /* Frees the information on upper bounds on numbers of iterations of LOOP. */
1269 free_numbers_of_iterations_estimates_loop (struct loop
*loop
)
1271 struct nb_iter_bound
*bound
, *next
;
1273 for (bound
= loop
->bounds
; bound
; bound
= next
)
1279 loop
->bounds
= NULL
;
1282 /* Frees the information on upper bounds on numbers of iterations of LOOPS. */
1285 free_numbers_of_iterations_estimates (struct loops
*loops
)
1290 for (i
= 1; i
< loops
->num
; i
++)
1292 loop
= loops
->parray
[i
];
1294 free_numbers_of_iterations_estimates_loop (loop
);