llvm / llvm-archive / 48649d2c83b557841c9e5c978d9ab5af13cb52e5 / . / llvm-gcc-4.0 / gcc / tree-ssa-loop-niter.c

/* Functions to determine/estimate number of iterations of a loop. | |

Copyright (C) 2004, 2005 Free Software Foundation, Inc. | |

This file is part of GCC. | |

GCC is free software; you can redistribute it and/or modify it | |

under the terms of the GNU General Public License as published by the | |

Free Software Foundation; either version 2, or (at your option) any | |

later version. | |

GCC is distributed in the hope that it will be useful, but WITHOUT | |

ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |

FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |

for more details. | |

You should have received a copy of the GNU General Public License | |

along with GCC; see the file COPYING. If not, write to the Free | |

Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |

02111-1307, USA. */ | |

#include "config.h" | |

#include "system.h" | |

#include "coretypes.h" | |

#include "tm.h" | |

#include "tree.h" | |

#include "rtl.h" | |

#include "tm_p.h" | |

#include "hard-reg-set.h" | |

#include "basic-block.h" | |

#include "output.h" | |

#include "diagnostic.h" | |

#include "tree-flow.h" | |

#include "tree-dump.h" | |

#include "cfgloop.h" | |

#include "tree-pass.h" | |

#include "ggc.h" | |

#include "tree-chrec.h" | |

#include "tree-scalar-evolution.h" | |

#include "tree-data-ref.h" | |

#include "params.h" | |

#include "flags.h" | |

#include "tree-inline.h" | |

#define SWAP(X, Y) do { void *tmp = (X); (X) = (Y); (Y) = tmp; } while (0) | |

/* | |

Analysis of number of iterations of an affine exit test. | |

*/ | |

/* Returns true if ARG is either NULL_TREE or constant zero. Unlike | |

integer_zerop, it does not care about overflow flags. */ | |

bool | |

zero_p (tree arg) | |

{ | |

if (!arg) | |

return true; | |

if (TREE_CODE (arg) != INTEGER_CST) | |

return false; | |

return (TREE_INT_CST_LOW (arg) == 0 && TREE_INT_CST_HIGH (arg) == 0); | |

} | |

/* Returns true if ARG a nonzero constant. Unlike integer_nonzerop, it does | |

not care about overflow flags. */ | |

static bool | |

nonzero_p (tree arg) | |

{ | |

if (!arg) | |

return false; | |

if (TREE_CODE (arg) != INTEGER_CST) | |

return false; | |

return (TREE_INT_CST_LOW (arg) != 0 || TREE_INT_CST_HIGH (arg) != 0); | |

} | |

/* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */ | |

static tree | |

inverse (tree x, tree mask) | |

{ | |

tree type = TREE_TYPE (x); | |

tree rslt; | |

unsigned ctr = tree_floor_log2 (mask); | |

if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT) | |

{ | |

unsigned HOST_WIDE_INT ix; | |

unsigned HOST_WIDE_INT imask; | |

unsigned HOST_WIDE_INT irslt = 1; | |

gcc_assert (cst_and_fits_in_hwi (x)); | |

gcc_assert (cst_and_fits_in_hwi (mask)); | |

ix = int_cst_value (x); | |

imask = int_cst_value (mask); | |

for (; ctr; ctr--) | |

{ | |

irslt *= ix; | |

ix *= ix; | |

} | |

irslt &= imask; | |

rslt = build_int_cst_type (type, irslt); | |

} | |

else | |

{ | |

rslt = build_int_cst_type (type, 1); | |

for (; ctr; ctr--) | |

{ | |

rslt = fold_binary_to_constant (MULT_EXPR, type, rslt, x); | |

x = fold_binary_to_constant (MULT_EXPR, type, x, x); | |

} | |

rslt = fold_binary_to_constant (BIT_AND_EXPR, type, rslt, mask); | |

} | |

return rslt; | |

} | |

/* Determine the number of iterations according to condition (for staying | |

inside loop) which compares two induction variables using comparison | |

operator CODE. The induction variable on left side of the comparison | |

has base BASE0 and step STEP0. the right-hand side one has base | |

BASE1 and step STEP1. Both induction variables must have type TYPE, | |

which must be an integer or pointer type. STEP0 and STEP1 must be | |

constants (or NULL_TREE, which is interpreted as constant zero). | |

The results (number of iterations and assumptions as described in | |

comments at struct tree_niter_desc in tree-flow.h) are stored to NITER. | |

In case we are unable to determine number of iterations, contents of | |

this structure is unchanged. */ | |

void | |

number_of_iterations_cond (tree type, tree base0, tree step0, | |

enum tree_code code, tree base1, tree step1, | |

struct tree_niter_desc *niter) | |

{ | |

tree step, delta, mmin, mmax; | |

tree may_xform, bound, s, d, tmp; | |

bool was_sharp = false; | |

tree assumption; | |

tree assumptions = boolean_true_node; | |

tree noloop_assumptions = boolean_false_node; | |

tree niter_type, signed_niter_type; | |

tree bits; | |

/* The meaning of these assumptions is this: | |

if !assumptions | |

then the rest of information does not have to be valid | |

if noloop_assumptions then the loop does not have to roll | |

(but it is only conservative approximation, i.e. it only says that | |

if !noloop_assumptions, then the loop does not end before the computed | |

number of iterations) */ | |

/* Make < comparison from > ones. */ | |

if (code == GE_EXPR | |

|| code == GT_EXPR) | |

{ | |

SWAP (base0, base1); | |

SWAP (step0, step1); | |

code = swap_tree_comparison (code); | |

} | |

/* We can handle the case when neither of the sides of the comparison is | |

invariant, provided that the test is NE_EXPR. This rarely occurs in | |

practice, but it is simple enough to manage. */ | |

if (!zero_p (step0) && !zero_p (step1)) | |

{ | |

if (code != NE_EXPR) | |

return; | |

step0 = fold_binary_to_constant (MINUS_EXPR, type, step0, step1); | |

step1 = NULL_TREE; | |

} | |

/* If the result is a constant, the loop is weird. More precise handling | |

would be possible, but the situation is not common enough to waste time | |

on it. */ | |

if (zero_p (step0) && zero_p (step1)) | |

return; | |

/* Ignore loops of while (i-- < 10) type. */ | |

if (code != NE_EXPR) | |

{ | |

if (step0 && !tree_expr_nonnegative_p (step0)) | |

return; | |

if (!zero_p (step1) && tree_expr_nonnegative_p (step1)) | |

return; | |

} | |

if (POINTER_TYPE_P (type)) | |

{ | |

/* We assume pointer arithmetic never overflows. */ | |

mmin = mmax = NULL_TREE; | |

} | |

else | |

{ | |

mmin = TYPE_MIN_VALUE (type); | |

mmax = TYPE_MAX_VALUE (type); | |

} | |

/* Some more condition normalization. We must record some assumptions | |

due to overflows. */ | |

if (code == LT_EXPR) | |

{ | |

/* We want to take care only of <=; this is easy, | |

as in cases the overflow would make the transformation unsafe the loop | |

does not roll. Seemingly it would make more sense to want to take | |

care of <, as NE is more similar to it, but the problem is that here | |

the transformation would be more difficult due to possibly infinite | |

loops. */ | |

if (zero_p (step0)) | |

{ | |

if (mmax) | |

assumption = fold (build2 (EQ_EXPR, boolean_type_node, base0, mmax)); | |

else | |

assumption = boolean_false_node; | |

if (nonzero_p (assumption)) | |

goto zero_iter; | |

base0 = fold (build2 (PLUS_EXPR, type, base0, | |

build_int_cst_type (type, 1))); | |

} | |

else | |

{ | |

if (mmin) | |

assumption = fold (build2 (EQ_EXPR, boolean_type_node, base1, mmin)); | |

else | |

assumption = boolean_false_node; | |

if (nonzero_p (assumption)) | |

goto zero_iter; | |

base1 = fold (build2 (MINUS_EXPR, type, base1, | |

build_int_cst_type (type, 1))); | |

} | |

noloop_assumptions = assumption; | |

code = LE_EXPR; | |

/* It will be useful to be able to tell the difference once more in | |

<= -> != reduction. */ | |

was_sharp = true; | |

} | |

/* Take care of trivially infinite loops. */ | |

if (code != NE_EXPR) | |

{ | |

if (zero_p (step0) | |

&& mmin | |

&& operand_equal_p (base0, mmin, 0)) | |

return; | |

if (zero_p (step1) | |

&& mmax | |

&& operand_equal_p (base1, mmax, 0)) | |

return; | |

} | |

/* If we can we want to take care of NE conditions instead of size | |

comparisons, as they are much more friendly (most importantly | |

this takes care of special handling of loops with step 1). We can | |

do it if we first check that upper bound is greater or equal to | |

lower bound, their difference is constant c modulo step and that | |

there is not an overflow. */ | |

if (code != NE_EXPR) | |

{ | |

if (zero_p (step0)) | |

step = fold_unary_to_constant (NEGATE_EXPR, type, step1); | |

else | |

step = step0; | |

/* APPLE LOCAL mainline 2005-09-01 */ | |

delta = fold (build2 (MINUS_EXPR, type, base1, base0)); | |

delta = fold (build2 (FLOOR_MOD_EXPR, type, delta, step)); | |

may_xform = boolean_false_node; | |

if (TREE_CODE (delta) == INTEGER_CST) | |

{ | |

tmp = fold_binary_to_constant (MINUS_EXPR, type, step, | |

build_int_cst_type (type, 1)); | |

if (was_sharp | |

&& operand_equal_p (delta, tmp, 0)) | |

{ | |

/* A special case. We have transformed condition of type | |

for (i = 0; i < 4; i += 4) | |

into | |

for (i = 0; i <= 3; i += 4) | |

obviously if the test for overflow during that transformation | |

passed, we cannot overflow here. Most importantly any | |

loop with sharp end condition and step 1 falls into this | |

category, so handling this case specially is definitely | |

worth the troubles. */ | |

may_xform = boolean_true_node; | |

} | |

else if (zero_p (step0)) | |

{ | |

if (!mmin) | |

may_xform = boolean_true_node; | |

else | |

{ | |

bound = fold_binary_to_constant (PLUS_EXPR, type, | |

mmin, step); | |

bound = fold_binary_to_constant (MINUS_EXPR, type, | |

bound, delta); | |

may_xform = fold (build2 (LE_EXPR, boolean_type_node, | |

bound, base0)); | |

} | |

} | |

else | |

{ | |

if (!mmax) | |

may_xform = boolean_true_node; | |

else | |

{ | |

bound = fold_binary_to_constant (MINUS_EXPR, type, | |

mmax, step); | |

bound = fold_binary_to_constant (PLUS_EXPR, type, | |

bound, delta); | |

may_xform = fold (build2 (LE_EXPR, boolean_type_node, | |

base1, bound)); | |

} | |

} | |

} | |

if (!zero_p (may_xform)) | |

{ | |

/* We perform the transformation always provided that it is not | |

completely senseless. This is OK, as we would need this assumption | |

to determine the number of iterations anyway. */ | |

if (!nonzero_p (may_xform)) | |

assumptions = may_xform; | |

if (zero_p (step0)) | |

{ | |

base0 = fold (build2 (PLUS_EXPR, type, base0, delta)); | |

base0 = fold (build2 (MINUS_EXPR, type, base0, step)); | |

} | |

else | |

{ | |

base1 = fold (build2 (MINUS_EXPR, type, base1, delta)); | |

base1 = fold (build2 (PLUS_EXPR, type, base1, step)); | |

} | |

assumption = fold (build2 (GT_EXPR, boolean_type_node, base0, base1)); | |

noloop_assumptions = fold (build2 (TRUTH_OR_EXPR, boolean_type_node, | |

noloop_assumptions, assumption)); | |

code = NE_EXPR; | |

} | |

} | |

/* Count the number of iterations. */ | |

niter_type = unsigned_type_for (type); | |

signed_niter_type = signed_type_for (type); | |

if (code == NE_EXPR) | |

{ | |

/* Everything we do here is just arithmetics modulo size of mode. This | |

makes us able to do more involved computations of number of iterations | |

than in other cases. First transform the condition into shape | |

s * i <> c, with s positive. */ | |

base1 = fold (build2 (MINUS_EXPR, type, base1, base0)); | |

base0 = NULL_TREE; | |

if (!zero_p (step1)) | |

step0 = fold_unary_to_constant (NEGATE_EXPR, type, step1); | |

step1 = NULL_TREE; | |

if (!tree_expr_nonnegative_p (fold_convert (signed_niter_type, step0))) | |

{ | |

step0 = fold_unary_to_constant (NEGATE_EXPR, type, step0); | |

base1 = fold (build1 (NEGATE_EXPR, type, base1)); | |

} | |

base1 = fold_convert (niter_type, base1); | |

step0 = fold_convert (niter_type, step0); | |

/* Let nsd (step, size of mode) = d. If d does not divide c, the loop | |

is infinite. Otherwise, the number of iterations is | |

(inverse(s/d) * (c/d)) mod (size of mode/d). */ | |

bits = num_ending_zeros (step0); | |

d = fold_binary_to_constant (LSHIFT_EXPR, niter_type, | |

build_int_cst_type (niter_type, 1), bits); | |

s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, step0, bits); | |

bound = build_low_bits_mask (niter_type, | |

(TYPE_PRECISION (niter_type) | |

- tree_low_cst (bits, 1))); | |

assumption = fold (build2 (FLOOR_MOD_EXPR, niter_type, base1, d)); | |

assumption = fold (build2 (EQ_EXPR, boolean_type_node, | |

assumption, | |

build_int_cst (niter_type, 0))); | |

assumptions = fold (build2 (TRUTH_AND_EXPR, boolean_type_node, | |

assumptions, assumption)); | |

tmp = fold (build2 (EXACT_DIV_EXPR, niter_type, base1, d)); | |

tmp = fold (build2 (MULT_EXPR, niter_type, tmp, inverse (s, bound))); | |

niter->niter = fold (build2 (BIT_AND_EXPR, niter_type, tmp, bound)); | |

} | |

else | |

{ | |

if (zero_p (step1)) | |

/* Condition in shape a + s * i <= b | |

We must know that b + s does not overflow and a <= b + s and then we | |

can compute number of iterations as (b + s - a) / s. (It might | |

seem that we in fact could be more clever about testing the b + s | |

overflow condition using some information about b - a mod s, | |

but it was already taken into account during LE -> NE transform). */ | |

{ | |

if (mmax) | |

{ | |

bound = fold_binary_to_constant (MINUS_EXPR, type, mmax, step0); | |

assumption = fold (build2 (LE_EXPR, boolean_type_node, | |

base1, bound)); | |

assumptions = fold (build2 (TRUTH_AND_EXPR, boolean_type_node, | |

assumptions, assumption)); | |

} | |

step = step0; | |

tmp = fold (build2 (PLUS_EXPR, type, base1, step0)); | |

assumption = fold (build2 (GT_EXPR, boolean_type_node, base0, tmp)); | |

delta = fold (build2 (PLUS_EXPR, type, base1, step)); | |

delta = fold (build2 (MINUS_EXPR, type, delta, base0)); | |

delta = fold_convert (niter_type, delta); | |

} | |

else | |

{ | |

/* Condition in shape a <= b - s * i | |

We must know that a - s does not overflow and a - s <= b and then | |

we can again compute number of iterations as (b - (a - s)) / s. */ | |

if (mmin) | |

{ | |

bound = fold_binary_to_constant (MINUS_EXPR, type, mmin, step1); | |

assumption = fold (build2 (LE_EXPR, boolean_type_node, | |

bound, base0)); | |

assumptions = fold (build2 (TRUTH_AND_EXPR, boolean_type_node, | |

assumptions, assumption)); | |

} | |

step = fold (build1 (NEGATE_EXPR, type, step1)); | |

tmp = fold (build2 (PLUS_EXPR, type, base0, step1)); | |

assumption = fold (build2 (GT_EXPR, boolean_type_node, tmp, base1)); | |

delta = fold (build2 (MINUS_EXPR, type, base0, step)); | |

delta = fold (build2 (MINUS_EXPR, type, base1, delta)); | |

delta = fold_convert (niter_type, delta); | |

} | |

noloop_assumptions = fold (build2 (TRUTH_OR_EXPR, boolean_type_node, | |

noloop_assumptions, assumption)); | |

delta = fold (build2 (FLOOR_DIV_EXPR, niter_type, delta, | |

fold_convert (niter_type, step))); | |

niter->niter = delta; | |

} | |

niter->assumptions = assumptions; | |

niter->may_be_zero = noloop_assumptions; | |

return; | |

zero_iter: | |

niter->assumptions = boolean_true_node; | |

niter->may_be_zero = boolean_true_node; | |

niter->niter = build_int_cst_type (type, 0); | |

return; | |

} | |

/* Tries to simplify EXPR using the evolutions of the loop invariants | |

in the superloops of LOOP. Returns the simplified expression | |

(or EXPR unchanged, if no simplification was possible). */ | |

static tree | |

simplify_using_outer_evolutions (struct loop *loop, tree expr) | |

{ | |

enum tree_code code = TREE_CODE (expr); | |

bool changed; | |

tree e, e0, e1, e2; | |

if (is_gimple_min_invariant (expr)) | |

return expr; | |

if (code == TRUTH_OR_EXPR | |

|| code == TRUTH_AND_EXPR | |

|| code == COND_EXPR) | |

{ | |

changed = false; | |

e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0)); | |

if (TREE_OPERAND (expr, 0) != e0) | |

changed = true; | |

e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1)); | |

if (TREE_OPERAND (expr, 1) != e1) | |

changed = true; | |

if (code == COND_EXPR) | |

{ | |

e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2)); | |

if (TREE_OPERAND (expr, 2) != e2) | |

changed = true; | |

} | |

else | |

e2 = NULL_TREE; | |

if (changed) | |

{ | |

if (code == COND_EXPR) | |

expr = build3 (code, boolean_type_node, e0, e1, e2); | |

else | |

expr = build2 (code, boolean_type_node, e0, e1); | |

expr = fold (expr); | |

} | |

return expr; | |

} | |

e = instantiate_parameters (loop, expr); | |

if (is_gimple_min_invariant (e)) | |

return e; | |

return expr; | |

} | |

/* Substitute NEW for OLD in EXPR and fold the result. */ | |

static tree | |

simplify_replace_tree (tree expr, tree old, tree new) | |

{ | |

unsigned i, n; | |

tree ret = NULL_TREE, e, se; | |

if (!expr) | |

return NULL_TREE; | |

if (expr == old | |

|| operand_equal_p (expr, old, 0)) | |

return unshare_expr (new); | |

if (!EXPR_P (expr)) | |

return expr; | |

n = TREE_CODE_LENGTH (TREE_CODE (expr)); | |

for (i = 0; i < n; i++) | |

{ | |

e = TREE_OPERAND (expr, i); | |

se = simplify_replace_tree (e, old, new); | |

if (e == se) | |

continue; | |

if (!ret) | |

ret = copy_node (expr); | |

TREE_OPERAND (ret, i) = se; | |

} | |

return (ret ? fold (ret) : expr); | |

} | |

/* Tries to simplify EXPR using the condition COND. Returns the simplified | |

expression (or EXPR unchanged, if no simplification was possible).*/ | |

static tree | |

tree_simplify_using_condition (tree cond, tree expr) | |

{ | |

bool changed; | |

tree e, e0, e1, e2, notcond; | |

enum tree_code code = TREE_CODE (expr); | |

if (code == INTEGER_CST) | |

return expr; | |

if (code == TRUTH_OR_EXPR | |

|| code == TRUTH_AND_EXPR | |

|| code == COND_EXPR) | |

{ | |

changed = false; | |

e0 = tree_simplify_using_condition (cond, TREE_OPERAND (expr, 0)); | |

if (TREE_OPERAND (expr, 0) != e0) | |

changed = true; | |

e1 = tree_simplify_using_condition (cond, TREE_OPERAND (expr, 1)); | |

if (TREE_OPERAND (expr, 1) != e1) | |

changed = true; | |

if (code == COND_EXPR) | |

{ | |

e2 = tree_simplify_using_condition (cond, TREE_OPERAND (expr, 2)); | |

if (TREE_OPERAND (expr, 2) != e2) | |

changed = true; | |

} | |

else | |

e2 = NULL_TREE; | |

if (changed) | |

{ | |

if (code == COND_EXPR) | |

expr = build3 (code, boolean_type_node, e0, e1, e2); | |

else | |

expr = build2 (code, boolean_type_node, e0, e1); | |

expr = fold (expr); | |

} | |

return expr; | |

} | |

/* In case COND is equality, we may be able to simplify EXPR by copy/constant | |

propagation, and vice versa. Fold does not handle this, since it is | |

considered too expensive. */ | |

if (TREE_CODE (cond) == EQ_EXPR) | |

{ | |

e0 = TREE_OPERAND (cond, 0); | |

e1 = TREE_OPERAND (cond, 1); | |

/* We know that e0 == e1. Check whether we cannot simplify expr | |

using this fact. */ | |

e = simplify_replace_tree (expr, e0, e1); | |

if (zero_p (e) || nonzero_p (e)) | |

return e; | |

e = simplify_replace_tree (expr, e1, e0); | |

if (zero_p (e) || nonzero_p (e)) | |

return e; | |

} | |

if (TREE_CODE (expr) == EQ_EXPR) | |

{ | |

e0 = TREE_OPERAND (expr, 0); | |

e1 = TREE_OPERAND (expr, 1); | |

/* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */ | |

e = simplify_replace_tree (cond, e0, e1); | |

if (zero_p (e)) | |

return e; | |

e = simplify_replace_tree (cond, e1, e0); | |

if (zero_p (e)) | |

return e; | |

} | |

if (TREE_CODE (expr) == NE_EXPR) | |

{ | |

e0 = TREE_OPERAND (expr, 0); | |

e1 = TREE_OPERAND (expr, 1); | |

/* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */ | |

e = simplify_replace_tree (cond, e0, e1); | |

if (zero_p (e)) | |

return boolean_true_node; | |

e = simplify_replace_tree (cond, e1, e0); | |

if (zero_p (e)) | |

return boolean_true_node; | |

} | |

/* Check whether COND ==> EXPR. */ | |

notcond = invert_truthvalue (cond); | |

e = fold (build2 (TRUTH_OR_EXPR, boolean_type_node, | |

notcond, expr)); | |

if (nonzero_p (e)) | |

return e; | |

/* Check whether COND ==> not EXPR. */ | |

e = fold (build2 (TRUTH_AND_EXPR, boolean_type_node, | |

cond, expr)); | |

if (zero_p (e)) | |

return e; | |

return expr; | |

} | |

/* Tries to simplify EXPR using the conditions on entry to LOOP. | |

Record the conditions used for simplification to CONDS_USED. | |

Returns the simplified expression (or EXPR unchanged, if no | |

simplification was possible).*/ | |

static tree | |

simplify_using_initial_conditions (struct loop *loop, tree expr, | |

tree *conds_used) | |

{ | |

edge e; | |

basic_block bb; | |

tree exp, cond; | |

if (TREE_CODE (expr) == INTEGER_CST) | |

return expr; | |

for (bb = loop->header; | |

bb != ENTRY_BLOCK_PTR; | |

bb = get_immediate_dominator (CDI_DOMINATORS, bb)) | |

{ | |

e = EDGE_PRED (bb, 0); | |

if (EDGE_COUNT (bb->preds) > 1) | |

continue; | |

if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))) | |

continue; | |

cond = COND_EXPR_COND (last_stmt (e->src)); | |

if (e->flags & EDGE_FALSE_VALUE) | |

cond = invert_truthvalue (cond); | |

exp = tree_simplify_using_condition (cond, expr); | |

if (exp != expr) | |

*conds_used = fold (build2 (TRUTH_AND_EXPR, | |

boolean_type_node, | |

*conds_used, | |

cond)); | |

expr = exp; | |

} | |

return expr; | |

} | |

/* Stores description of number of iterations of LOOP derived from | |

EXIT (an exit edge of the LOOP) in NITER. Returns true if some | |

useful information could be derived (and fields of NITER has | |

meaning described in comments at struct tree_niter_desc | |

declaration), false otherwise. */ | |

bool | |

number_of_iterations_exit (struct loop *loop, edge exit, | |

struct tree_niter_desc *niter) | |

{ | |

tree stmt, cond, type; | |

tree op0, base0, step0; | |

tree op1, base1, step1; | |

enum tree_code code; | |

if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src)) | |

return false; | |

niter->assumptions = boolean_false_node; | |

stmt = last_stmt (exit->src); | |

if (!stmt || TREE_CODE (stmt) != COND_EXPR) | |

return false; | |

/* We want the condition for staying inside loop. */ | |

cond = COND_EXPR_COND (stmt); | |

if (exit->flags & EDGE_TRUE_VALUE) | |

cond = invert_truthvalue (cond); | |

code = TREE_CODE (cond); | |

switch (code) | |

{ | |

case GT_EXPR: | |

case GE_EXPR: | |

case NE_EXPR: | |

case LT_EXPR: | |

case LE_EXPR: | |

break; | |

default: | |

return false; | |

} | |

op0 = TREE_OPERAND (cond, 0); | |

op1 = TREE_OPERAND (cond, 1); | |

type = TREE_TYPE (op0); | |

if (TREE_CODE (type) != INTEGER_TYPE | |

&& !POINTER_TYPE_P (type)) | |

return false; | |

if (!simple_iv (loop, stmt, op0, &base0, &step0)) | |

return false; | |

if (!simple_iv (loop, stmt, op1, &base1, &step1)) | |

return false; | |

niter->niter = NULL_TREE; | |

number_of_iterations_cond (type, base0, step0, code, base1, step1, | |

niter); | |

if (!niter->niter) | |

return false; | |

niter->assumptions = simplify_using_outer_evolutions (loop, | |

niter->assumptions); | |

niter->may_be_zero = simplify_using_outer_evolutions (loop, | |

niter->may_be_zero); | |

niter->niter = simplify_using_outer_evolutions (loop, niter->niter); | |

niter->additional_info = boolean_true_node; | |

niter->assumptions | |

= simplify_using_initial_conditions (loop, | |

niter->assumptions, | |

&niter->additional_info); | |

niter->may_be_zero | |

= simplify_using_initial_conditions (loop, | |

niter->may_be_zero, | |

&niter->additional_info); | |

return integer_onep (niter->assumptions); | |

} | |

/* Try to determine the number of iterations of LOOP. If we succeed, | |

expression giving number of iterations is returned and *EXIT is | |

set to the edge from that the information is obtained. Otherwise | |

chrec_dont_know is returned. */ | |

tree | |

find_loop_niter (struct loop *loop, edge *exit) | |

{ | |

unsigned n_exits, i; | |

edge *exits = get_loop_exit_edges (loop, &n_exits); | |

edge ex; | |

tree niter = NULL_TREE, aniter; | |

struct tree_niter_desc desc; | |

*exit = NULL; | |

for (i = 0; i < n_exits; i++) | |

{ | |

ex = exits[i]; | |

if (!just_once_each_iteration_p (loop, ex->src)) | |

continue; | |

if (!number_of_iterations_exit (loop, ex, &desc)) | |

continue; | |

if (nonzero_p (desc.may_be_zero)) | |

{ | |

/* We exit in the first iteration through this exit. | |

We won't find anything better. */ | |

niter = build_int_cst_type (unsigned_type_node, 0); | |

*exit = ex; | |

break; | |

} | |

if (!zero_p (desc.may_be_zero)) | |

continue; | |

aniter = desc.niter; | |

if (!niter) | |

{ | |

/* Nothing recorded yet. */ | |

niter = aniter; | |

*exit = ex; | |

continue; | |

} | |

/* Prefer constants, the lower the better. */ | |

if (TREE_CODE (aniter) != INTEGER_CST) | |

continue; | |

if (TREE_CODE (niter) != INTEGER_CST) | |

{ | |

niter = aniter; | |

*exit = ex; | |

continue; | |

} | |

if (tree_int_cst_lt (aniter, niter)) | |

{ | |

niter = aniter; | |

*exit = ex; | |

continue; | |

} | |

} | |

free (exits); | |

return niter ? niter : chrec_dont_know; | |

} | |

/* | |

Analysis of a number of iterations of a loop by a brute-force evaluation. | |

*/ | |

/* Bound on the number of iterations we try to evaluate. */ | |

#define MAX_ITERATIONS_TO_TRACK \ | |

((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK)) | |

/* Returns the loop phi node of LOOP such that ssa name X is derived from its | |

result by a chain of operations such that all but exactly one of their | |

operands are constants. */ | |

static tree | |

chain_of_csts_start (struct loop *loop, tree x) | |

{ | |

tree stmt = SSA_NAME_DEF_STMT (x); | |

basic_block bb = bb_for_stmt (stmt); | |

use_optype uses; | |

if (!bb | |

|| !flow_bb_inside_loop_p (loop, bb)) | |

return NULL_TREE; | |

if (TREE_CODE (stmt) == PHI_NODE) | |

{ | |

if (bb == loop->header) | |

return stmt; | |

return NULL_TREE; | |

} | |

if (TREE_CODE (stmt) != MODIFY_EXPR) | |

return NULL_TREE; | |

get_stmt_operands (stmt); | |

if (NUM_VUSES (STMT_VUSE_OPS (stmt)) > 0) | |

return NULL_TREE; | |

if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) > 0) | |

return NULL_TREE; | |

if (NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt)) > 0) | |

return NULL_TREE; | |

if (NUM_DEFS (STMT_DEF_OPS (stmt)) > 1) | |

return NULL_TREE; | |

uses = STMT_USE_OPS (stmt); | |

if (NUM_USES (uses) != 1) | |

return NULL_TREE; | |

return chain_of_csts_start (loop, USE_OP (uses, 0)); | |

} | |

/* Determines whether the expression X is derived from a result of a phi node | |

in header of LOOP such that | |

* the derivation of X consists only from operations with constants | |

* the initial value of the phi node is constant | |

* the value of the phi node in the next iteration can be derived from the | |

value in the current iteration by a chain of operations with constants. | |

If such phi node exists, it is returned. If X is a constant, X is returned | |

unchanged. Otherwise NULL_TREE is returned. */ | |

static tree | |

get_base_for (struct loop *loop, tree x) | |

{ | |

tree phi, init, next; | |

if (is_gimple_min_invariant (x)) | |

return x; | |

phi = chain_of_csts_start (loop, x); | |

if (!phi) | |

return NULL_TREE; | |

init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop)); | |

next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop)); | |

if (TREE_CODE (next) != SSA_NAME) | |

return NULL_TREE; | |

if (!is_gimple_min_invariant (init)) | |

return NULL_TREE; | |

if (chain_of_csts_start (loop, next) != phi) | |

return NULL_TREE; | |

return phi; | |

} | |

/* Given an expression X, then | |

* if BASE is NULL_TREE, X must be a constant and we return X. | |

* otherwise X is a SSA name, whose value in the considered loop is derived | |

by a chain of operations with constant from a result of a phi node in | |

the header of the loop. Then we return value of X when the value of the | |

result of this phi node is given by the constant BASE. */ | |

static tree | |

get_val_for (tree x, tree base) | |

{ | |

tree stmt, nx, val; | |

use_optype uses; | |

use_operand_p op; | |

if (!x) | |

return base; | |

stmt = SSA_NAME_DEF_STMT (x); | |

if (TREE_CODE (stmt) == PHI_NODE) | |

return base; | |

uses = STMT_USE_OPS (stmt); | |

op = USE_OP_PTR (uses, 0); | |

nx = USE_FROM_PTR (op); | |

val = get_val_for (nx, base); | |

SET_USE (op, val); | |

val = fold (TREE_OPERAND (stmt, 1)); | |

SET_USE (op, nx); | |

return val; | |

} | |

/* Tries to count the number of iterations of LOOP till it exits by EXIT | |

by brute force -- i.e. by determining the value of the operands of the | |

condition at EXIT in first few iterations of the loop (assuming that | |

these values are constant) and determining the first one in that the | |

condition is not satisfied. Returns the constant giving the number | |

of the iterations of LOOP if successful, chrec_dont_know otherwise. */ | |

tree | |

loop_niter_by_eval (struct loop *loop, edge exit) | |

{ | |

tree cond, cnd, acnd; | |

tree op[2], val[2], next[2], aval[2], phi[2]; | |

unsigned i, j; | |

enum tree_code cmp; | |

cond = last_stmt (exit->src); | |

if (!cond || TREE_CODE (cond) != COND_EXPR) | |

return chrec_dont_know; | |

cnd = COND_EXPR_COND (cond); | |

if (exit->flags & EDGE_TRUE_VALUE) | |

cnd = invert_truthvalue (cnd); | |

cmp = TREE_CODE (cnd); | |

switch (cmp) | |

{ | |

case EQ_EXPR: | |

case NE_EXPR: | |

case GT_EXPR: | |

case GE_EXPR: | |

case LT_EXPR: | |

case LE_EXPR: | |

for (j = 0; j < 2; j++) | |

op[j] = TREE_OPERAND (cnd, j); | |

break; | |

default: | |

return chrec_dont_know; | |

} | |

for (j = 0; j < 2; j++) | |

{ | |

phi[j] = get_base_for (loop, op[j]); | |

if (!phi[j]) | |

return chrec_dont_know; | |

} | |

for (j = 0; j < 2; j++) | |

{ | |

if (TREE_CODE (phi[j]) == PHI_NODE) | |

{ | |

val[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_preheader_edge (loop)); | |

next[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_latch_edge (loop)); | |

} | |

else | |

{ | |

val[j] = phi[j]; | |

next[j] = NULL_TREE; | |

op[j] = NULL_TREE; | |

} | |

} | |

for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++) | |

{ | |

for (j = 0; j < 2; j++) | |

aval[j] = get_val_for (op[j], val[j]); | |

acnd = fold (build2 (cmp, boolean_type_node, aval[0], aval[1])); | |

if (zero_p (acnd)) | |

{ | |

if (dump_file && (dump_flags & TDF_DETAILS)) | |

fprintf (dump_file, | |

"Proved that loop %d iterates %d times using brute force.\n", | |

loop->num, i); | |

return build_int_cst (unsigned_type_node, i); | |

} | |

for (j = 0; j < 2; j++) | |

val[j] = get_val_for (next[j], val[j]); | |

} | |

return chrec_dont_know; | |

} | |

/* Finds the exit of the LOOP by that the loop exits after a constant | |

number of iterations and stores the exit edge to *EXIT. The constant | |

giving the number of iterations of LOOP is returned. The number of | |

iterations is determined using loop_niter_by_eval (i.e. by brute force | |

evaluation). If we are unable to find the exit for that loop_niter_by_eval | |

determines the number of iterations, chrec_dont_know is returned. */ | |

tree | |

find_loop_niter_by_eval (struct loop *loop, edge *exit) | |

{ | |

unsigned n_exits, i; | |

edge *exits = get_loop_exit_edges (loop, &n_exits); | |

edge ex; | |

tree niter = NULL_TREE, aniter; | |

*exit = NULL; | |

for (i = 0; i < n_exits; i++) | |

{ | |

ex = exits[i]; | |

if (!just_once_each_iteration_p (loop, ex->src)) | |

continue; | |

aniter = loop_niter_by_eval (loop, ex); | |

if (chrec_contains_undetermined (aniter)) | |

continue; | |

if (niter | |

&& !tree_int_cst_lt (aniter, niter)) | |

continue; | |

niter = aniter; | |

*exit = ex; | |

} | |

free (exits); | |

return niter ? niter : chrec_dont_know; | |

} | |

/* | |

Analysis of upper bounds on number of iterations of a loop. | |

*/ | |

/* Records that AT_STMT is executed at most BOUND times in LOOP. The | |

additional condition ADDITIONAL is recorded with the bound. */ | |

void | |

record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt) | |

{ | |

struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound)); | |

if (dump_file && (dump_flags & TDF_DETAILS)) | |

{ | |

fprintf (dump_file, "Statements after "); | |

print_generic_expr (dump_file, at_stmt, TDF_SLIM); | |

fprintf (dump_file, " are executed at most "); | |

print_generic_expr (dump_file, bound, TDF_SLIM); | |

fprintf (dump_file, " times in loop %d.\n", loop->num); | |

} | |

elt->bound = bound; | |

elt->at_stmt = at_stmt; | |

elt->additional = additional; | |

elt->next = loop->bounds; | |

loop->bounds = elt; | |

} | |

/* Records estimates on numbers of iterations of LOOP. */ | |

static void | |

estimate_numbers_of_iterations_loop (struct loop *loop) | |

{ | |

edge *exits; | |

tree niter, type; | |

unsigned i, n_exits; | |

struct tree_niter_desc niter_desc; | |

exits = get_loop_exit_edges (loop, &n_exits); | |

for (i = 0; i < n_exits; i++) | |

{ | |

if (!number_of_iterations_exit (loop, exits[i], &niter_desc)) | |

continue; | |

niter = niter_desc.niter; | |

type = TREE_TYPE (niter); | |

if (!zero_p (niter_desc.may_be_zero) | |

&& !nonzero_p (niter_desc.may_be_zero)) | |

niter = build3 (COND_EXPR, type, niter_desc.may_be_zero, | |

build_int_cst_type (type, 0), | |

niter); | |

record_estimate (loop, niter, | |

niter_desc.additional_info, | |

last_stmt (exits[i]->src)); | |

} | |

free (exits); | |

/* Analyzes the bounds of arrays accessed in the loop. */ | |

if (loop->estimated_nb_iterations == NULL_TREE) | |

{ | |

varray_type datarefs; | |

VARRAY_GENERIC_PTR_INIT (datarefs, 3, "datarefs"); | |

find_data_references_in_loop (loop, &datarefs); | |

free_data_refs (datarefs); | |

} | |

} | |

/* Records estimates on numbers of iterations of LOOPS. */ | |

void | |

estimate_numbers_of_iterations (struct loops *loops) | |

{ | |

unsigned i; | |

struct loop *loop; | |

for (i = 1; i < loops->num; i++) | |

{ | |

loop = loops->parray[i]; | |

if (loop) | |

estimate_numbers_of_iterations_loop (loop); | |

} | |

} | |

/* If A > B, returns -1. If A == B, returns 0. If A < B, returns 1. | |

If neither of these relations can be proved, returns 2. */ | |

static int | |

compare_trees (tree a, tree b) | |

{ | |

tree typea = TREE_TYPE (a), typeb = TREE_TYPE (b); | |

tree type; | |

if (TYPE_PRECISION (typea) > TYPE_PRECISION (typeb)) | |

type = typea; | |

else | |

type = typeb; | |

a = fold_convert (type, a); | |

b = fold_convert (type, b); | |

if (nonzero_p (fold (build2 (EQ_EXPR, boolean_type_node, a, b)))) | |

return 0; | |

if (nonzero_p (fold (build2 (LT_EXPR, boolean_type_node, a, b)))) | |

return 1; | |

if (nonzero_p (fold (build2 (GT_EXPR, boolean_type_node, a, b)))) | |

return -1; | |

return 2; | |

} | |

/* Returns true if statement S1 dominates statement S2. */ | |

static bool | |

stmt_dominates_stmt_p (tree s1, tree s2) | |

{ | |

basic_block bb1 = bb_for_stmt (s1), bb2 = bb_for_stmt (s2); | |

if (!bb1 | |

|| s1 == s2) | |

return true; | |

if (bb1 == bb2) | |

{ | |

block_stmt_iterator bsi; | |

for (bsi = bsi_start (bb1); bsi_stmt (bsi) != s2; bsi_next (&bsi)) | |

if (bsi_stmt (bsi) == s1) | |

return true; | |

return false; | |

} | |

return dominated_by_p (CDI_DOMINATORS, bb2, bb1); | |

} | |

/* Checks whether it is correct to count the induction variable BASE + STEP * I | |

at AT_STMT in wider TYPE, using the fact that statement OF is executed at | |

most BOUND times in the loop. If it is possible, return the value of step | |

of the induction variable in the TYPE, otherwise return NULL_TREE. | |

ADDITIONAL is the additional condition recorded for operands of the bound. | |

This is useful in the following case, created by loop header copying: | |

i = 0; | |

if (n > 0) | |

do | |

{ | |

something; | |

} while (++i < n) | |

If the n > 0 condition is taken into account, the number of iterations of the | |

loop can be expressed as n - 1. If the type of n is signed, the ADDITIONAL | |

assumption "n > 0" says us that the value of the number of iterations is at | |

most MAX_TYPE - 1 (without this assumption, it might overflow). */ | |

static tree | |

can_count_iv_in_wider_type_bound (tree type, tree base, tree step, | |

tree at_stmt, | |

tree bound, | |

tree additional, | |

tree of) | |

{ | |

tree inner_type = TREE_TYPE (base), b, bplusstep, new_step, new_step_abs; | |

tree valid_niter, extreme, unsigned_type, delta, bound_type; | |

tree cond; | |

b = fold_convert (type, base); | |

bplusstep = fold_convert (type, | |

fold (build2 (PLUS_EXPR, inner_type, base, step))); | |

new_step = fold (build2 (MINUS_EXPR, type, bplusstep, b)); | |

if (TREE_CODE (new_step) != INTEGER_CST) | |

return NULL_TREE; | |

switch (compare_trees (bplusstep, b)) | |

{ | |

case -1: | |

extreme = upper_bound_in_type (type, inner_type); | |

delta = fold (build2 (MINUS_EXPR, type, extreme, b)); | |

new_step_abs = new_step; | |

break; | |

case 1: | |

extreme = lower_bound_in_type (type, inner_type); | |

new_step_abs = fold (build1 (NEGATE_EXPR, type, new_step)); | |

delta = fold (build2 (MINUS_EXPR, type, b, extreme)); | |

break; | |

case 0: | |

return new_step; | |

default: | |

return NULL_TREE; | |

} | |

unsigned_type = unsigned_type_for (type); | |

delta = fold_convert (unsigned_type, delta); | |

new_step_abs = fold_convert (unsigned_type, new_step_abs); | |

valid_niter = fold (build2 (FLOOR_DIV_EXPR, unsigned_type, | |

delta, new_step_abs)); | |

bound_type = TREE_TYPE (bound); | |

if (TYPE_PRECISION (type) > TYPE_PRECISION (bound_type)) | |

bound = fold_convert (unsigned_type, bound); | |

else | |

valid_niter = fold_convert (bound_type, valid_niter); | |

if (at_stmt && stmt_dominates_stmt_p (of, at_stmt)) | |

{ | |

/* After the statement OF we know that anything is executed at most | |

BOUND times. */ | |

cond = build2 (GE_EXPR, boolean_type_node, valid_niter, bound); | |

} | |

else | |

{ | |

/* Before the statement OF we know that anything is executed at most | |

BOUND + 1 times. */ | |

cond = build2 (GT_EXPR, boolean_type_node, valid_niter, bound); | |

} | |

cond = fold (cond); | |

if (nonzero_p (cond)) | |

return new_step; | |

/* Try taking additional conditions into account. */ | |

cond = build2 (TRUTH_OR_EXPR, boolean_type_node, | |

invert_truthvalue (additional), | |

cond); | |

cond = fold (cond); | |

if (nonzero_p (cond)) | |

return new_step; | |

return NULL_TREE; | |

} | |

/* Checks whether it is correct to count the induction variable BASE + STEP * I | |

at AT_STMT in wider TYPE, using the bounds on numbers of iterations of a | |

LOOP. If it is possible, return the value of step of the induction variable | |

in the TYPE, otherwise return NULL_TREE. */ | |

tree | |

can_count_iv_in_wider_type (struct loop *loop, tree type, tree base, tree step, | |

tree at_stmt) | |

{ | |

struct nb_iter_bound *bound; | |

tree new_step; | |

for (bound = loop->bounds; bound; bound = bound->next) | |

{ | |

new_step = can_count_iv_in_wider_type_bound (type, base, step, | |

at_stmt, | |

bound->bound, | |

bound->additional, | |

bound->at_stmt); | |

if (new_step) | |

return new_step; | |

} | |

return NULL_TREE; | |

} | |

/* Frees the information on upper bounds on numbers of iterations of LOOP. */ | |

static void | |

free_numbers_of_iterations_estimates_loop (struct loop *loop) | |

{ | |

struct nb_iter_bound *bound, *next; | |

for (bound = loop->bounds; bound; bound = next) | |

{ | |

next = bound->next; | |

free (bound); | |

} | |

loop->bounds = NULL; | |

} | |

/* Frees the information on upper bounds on numbers of iterations of LOOPS. */ | |

void | |

free_numbers_of_iterations_estimates (struct loops *loops) | |

{ | |

unsigned i; | |

struct loop *loop; | |

for (i = 1; i < loops->num; i++) | |

{ | |

loop = loops->parray[i]; | |

if (loop) | |

free_numbers_of_iterations_estimates_loop (loop); | |

} | |

} | |

/* APPLE LOCAL begin lno */ | |

/* | |

Removal of loops in DCE. | |

*/ | |

/* If we are able to prove that the LOOP always exits, turn off the | |

EDGE_DFS_BACK flag from its latch edge. */ | |

static void | |

unmark_surely_finite_loop (struct loop *loop) | |

{ | |

edge *exits; | |

unsigned i, n_exits; | |

struct tree_niter_desc niter_desc; | |

exits = get_loop_exit_edges (loop, &n_exits); | |

for (i = 0; i < n_exits; i++) | |

if (number_of_iterations_exit (loop, exits[i], &niter_desc)) | |

{ | |

loop_latch_edge (loop)->flags &= ~EDGE_DFS_BACK; | |

return; | |

} | |

} | |

/* Emit special statements preventing removal of possibly infinite loops in | |

CD_DCE to the latches of LOOPS for that we are not able to prove that they | |

iterate just finite number of times. */ | |

void | |

mark_maybe_infinite_loops (struct loops *loops) | |

{ | |

unsigned i; | |

struct loop *loop; | |

basic_block bb; | |

edge e; | |

tree stmt; | |

bool inserted = false; | |

block_stmt_iterator bsi; | |

mark_dfs_back_edges (); | |

for (i = 1; i < loops->num; i++) | |

{ | |

loop = loops->parray[i]; | |

if (loop) | |

unmark_surely_finite_loop (loop); | |

} | |

FOR_EACH_BB (bb) | |

{ | |

edge_iterator ei; | |

FOR_EACH_EDGE (e, ei, bb->succs) | |

if (e->flags & EDGE_DFS_BACK) | |

{ | |

stmt = build_function_call_expr (built_in_decls[BUILT_IN_MAYBE_INFINITE_LOOP], | |

NULL); | |

if (!(e->flags & EDGE_ABNORMAL)) | |

{ | |

bsi_insert_on_edge (e, stmt); | |

inserted = true; | |

continue; | |

} | |

/* We cannot insert on abnormal edge, so insert to the basic block | |

at its start. */ | |

bsi = bsi_last (e->src); | |

if (!bsi_end_p (bsi) | |

&& stmt_ends_bb_p (bsi_stmt (bsi))) | |

bsi_insert_before (&bsi, stmt, BSI_NEW_STMT); | |

else | |

bsi_insert_after (&bsi, stmt, BSI_NEW_STMT); | |

} | |

} | |

if (inserted) | |

loop_commit_inserts (); | |

} | |

/* APPLE LOCAL end lno */ |