/* Functions to determine/estimate number of iterations of a loop.
- Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
+ Copyright (C) 2004, 2005, 2006, 2007, 2008 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
+Free Software Foundation; either version 3, or (at your option) any
later version.
GCC is distributed in the hope that it will be useful, but WITHOUT
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, 51 Franklin Street, Fifth Floor, Boston, MA
-02110-1301, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
#include "tree-inline.h"
#include "gmp.h"
-#define SWAP(X, Y) do { void *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
+#define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
/* The maximum number of dominator BBs we search for conditions
of loop header copies we use for simplifying a conditional
mpz_t below, up;
} bounds;
-/* Sets RESULT to VAL, taken unsigned if UNS is true and as signed
- otherwise. */
-
-static void
-mpz_set_double_int (mpz_t result, double_int val, bool uns)
-{
- bool negate = false;
- unsigned HOST_WIDE_INT vp[2];
-
- if (!uns && double_int_negative_p (val))
- {
- negate = true;
- val = double_int_neg (val);
- }
-
- vp[0] = val.low;
- vp[1] = (unsigned HOST_WIDE_INT) val.high;
- mpz_import (result, 2, -1, sizeof (HOST_WIDE_INT), 0, 0, vp);
-
- if (negate)
- mpz_neg (result, result);
-}
-
-/* Stores bounds of TYPE to MIN and MAX. */
-
-static void
-get_type_bounds (tree type, mpz_t min, mpz_t max)
-{
- if (TYPE_UNSIGNED (type))
- {
- mpz_set_ui (min, 0);
- mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true);
- }
- else
- {
- double_int mx, mn;
-
- mx = double_int_mask (TYPE_PRECISION (type) - 1);
- mn = double_int_sext (double_int_add (mx, double_int_one),
- TYPE_PRECISION (type));
- mpz_set_double_int (max, mx, true);
- mpz_set_double_int (min, mn, false);
- }
-}
-
-/* Returns VAL converted to TYPE. If VAL does not fit in TYPE,
- the minimum or maximum value of the type is returned instead. */
-
-static double_int
-mpz_to_double_int (tree type, mpz_t val)
-{
- mpz_t min, max;
- unsigned HOST_WIDE_INT vp[2];
- bool negate = false;
- size_t count;
- double_int res;
-
- mpz_init (min);
- mpz_init (max);
- get_type_bounds (type, min, max);
-
- if (mpz_cmp (val, min) < 0)
- mpz_set (val, min);
- else if (mpz_cmp (val, max) > 0)
- mpz_set (val, max);
-
- if (mpz_sgn (val) < 0)
- negate = true;
-
- vp[0] = 0;
- vp[1] = 0;
- mpz_export (vp, &count, -1, sizeof (HOST_WIDE_INT), 0, 0, val);
- gcc_assert (count <= 2);
-
- mpz_clear (min);
- mpz_clear (max);
-
- res.low = vp[0];
- res.high = (HOST_WIDE_INT) vp[1];
-
- res = double_int_ext (res, TYPE_PRECISION (type), TYPE_UNSIGNED (type));
- if (negate)
- res = double_int_neg (res);
-
- return res;
-}
/* Splits expression EXPR to a variable part VAR and constant OFFSET. */
/* Fallthru. */
case PLUS_EXPR:
+ case POINTER_PLUS_EXPR:
op0 = TREE_OPERAND (expr, 0);
op1 = TREE_OPERAND (expr, 1);
/* If the computation may wrap, we know nothing about the value, except for
the range of the type. */
- get_type_bounds (type, min, max);
+ get_type_static_bounds (type, min, max);
if (!nowrap_type_p (type))
return;
STRIP_SIGN_NOPS (c0);
STRIP_SIGN_NOPS (c1);
ctype = TREE_TYPE (c0);
- if (!tree_ssa_useless_type_conversion_1 (ctype, type))
+ if (!useless_type_conversion_p (ctype, type))
return;
break;
int cnt = 0;
edge e;
basic_block bb;
- tree cond, c0, c1;
+ tree c0, c1;
+ gimple cond;
enum tree_code cmp;
/* Get rid of unnecessary casts, but preserve the value of
if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
continue;
- cond = COND_EXPR_COND (last_stmt (e->src));
- if (!COMPARISON_CLASS_P (cond))
- continue;
- c0 = TREE_OPERAND (cond, 0);
- cmp = TREE_CODE (cond);
- c1 = TREE_OPERAND (cond, 1);
+ cond = last_stmt (e->src);
+ c0 = gimple_cond_lhs (cond);
+ cmp = gimple_cond_code (cond);
+ c1 = gimple_cond_rhs (cond);
if (e->flags & EDGE_FALSE_VALUE)
cmp = invert_tree_comparison (cmp, false);
mpz_init (max);
number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds);
- niter->max = mpz_to_double_int (niter_type, max);
+ niter->max = mpz_get_double_int (niter_type, max, false);
mpz_clear (max);
/* First the trivial cases -- when the step is 1. */
mpz_t mmod;
tree assumption = boolean_true_node, bound, noloop;
bool ret = false;
+ tree type1 = type;
+ if (POINTER_TYPE_P (type))
+ type1 = sizetype;
if (TREE_CODE (mod) != INTEGER_CST)
return false;
if (integer_nonzerop (mod))
mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
- tmod = fold_convert (type, mod);
+ tmod = fold_convert (type1, mod);
mpz_init (mmod);
mpz_set_double_int (mmod, tree_to_double_int (mod), true);
/* The final value of the iv is iv1->base + MOD, assuming that this
computation does not overflow, and that
iv0->base <= iv1->base + MOD. */
- if (!iv1->no_overflow && !integer_zerop (mod))
+ if (!iv0->no_overflow && !integer_zerop (mod))
{
- bound = fold_build2 (MINUS_EXPR, type,
- TYPE_MAX_VALUE (type), tmod);
+ bound = fold_build2 (MINUS_EXPR, type1,
+ TYPE_MAX_VALUE (type1), tmod);
+ if (POINTER_TYPE_P (type))
+ bound = fold_convert (type, bound);
assumption = fold_build2 (LE_EXPR, boolean_type_node,
iv1->base, bound);
if (integer_zerop (assumption))
}
if (mpz_cmp (mmod, bnds->below) < 0)
noloop = boolean_false_node;
+ else if (POINTER_TYPE_P (type))
+ noloop = fold_build2 (GT_EXPR, boolean_type_node,
+ iv0->base,
+ fold_build2 (POINTER_PLUS_EXPR, type,
+ iv1->base, tmod));
else
noloop = fold_build2 (GT_EXPR, boolean_type_node,
iv0->base,
- fold_build2 (PLUS_EXPR, type,
+ fold_build2 (PLUS_EXPR, type1,
iv1->base, tmod));
}
else
/* The final value of the iv is iv0->base - MOD, assuming that this
computation does not overflow, and that
iv0->base - MOD <= iv1->base. */
- if (!iv0->no_overflow && !integer_zerop (mod))
+ if (!iv1->no_overflow && !integer_zerop (mod))
{
- bound = fold_build2 (PLUS_EXPR, type,
- TYPE_MIN_VALUE (type), tmod);
+ bound = fold_build2 (PLUS_EXPR, type1,
+ TYPE_MIN_VALUE (type1), tmod);
+ if (POINTER_TYPE_P (type))
+ bound = fold_convert (type, bound);
assumption = fold_build2 (GE_EXPR, boolean_type_node,
iv0->base, bound);
if (integer_zerop (assumption))
}
if (mpz_cmp (mmod, bnds->below) < 0)
noloop = boolean_false_node;
+ else if (POINTER_TYPE_P (type))
+ noloop = fold_build2 (GT_EXPR, boolean_type_node,
+ fold_build2 (POINTER_PLUS_EXPR, type,
+ iv0->base,
+ fold_build1 (NEGATE_EXPR,
+ type1, tmod)),
+ iv1->base);
else
noloop = fold_build2 (GT_EXPR, boolean_type_node,
- fold_build2 (MINUS_EXPR, type,
+ fold_build2 (MINUS_EXPR, type1,
iv0->base, tmod),
iv1->base);
}
struct tree_niter_desc *niter, bounds *bnds)
{
tree assumption = boolean_true_node, bound, diff;
- tree mbz, mbzl, mbzr;
+ tree mbz, mbzl, mbzr, type1;
bool rolls_p, no_overflow_p;
double_int dstep;
mpz_t mstep, max;
if (rolls_p && no_overflow_p)
return;
+
+ type1 = type;
+ if (POINTER_TYPE_P (type))
+ type1 = sizetype;
/* Now the hard part; we must formulate the assumption(s) as expressions, and
we must be careful not to introduce overflow. */
if (integer_nonzerop (iv0->step))
{
- diff = fold_build2 (MINUS_EXPR, type,
- iv0->step, build_int_cst (type, 1));
+ diff = fold_build2 (MINUS_EXPR, type1,
+ iv0->step, build_int_cst (type1, 1));
/* We need to know that iv0->base >= MIN + iv0->step - 1. Since
0 address never belongs to any object, we can assume this for
pointers. */
if (!POINTER_TYPE_P (type))
{
- bound = fold_build2 (PLUS_EXPR, type,
+ bound = fold_build2 (PLUS_EXPR, type1,
TYPE_MIN_VALUE (type), diff);
assumption = fold_build2 (GE_EXPR, boolean_type_node,
iv0->base, bound);
/* And then we can compute iv0->base - diff, and compare it with
iv1->base. */
- mbzl = fold_build2 (MINUS_EXPR, type, iv0->base, diff);
- mbzr = iv1->base;
+ mbzl = fold_build2 (MINUS_EXPR, type1,
+ fold_convert (type1, iv0->base), diff);
+ mbzr = fold_convert (type1, iv1->base);
}
else
{
- diff = fold_build2 (PLUS_EXPR, type,
- iv1->step, build_int_cst (type, 1));
+ diff = fold_build2 (PLUS_EXPR, type1,
+ iv1->step, build_int_cst (type1, 1));
if (!POINTER_TYPE_P (type))
{
- bound = fold_build2 (PLUS_EXPR, type,
+ bound = fold_build2 (PLUS_EXPR, type1,
TYPE_MAX_VALUE (type), diff);
assumption = fold_build2 (LE_EXPR, boolean_type_node,
iv1->base, bound);
}
- mbzl = iv0->base;
- mbzr = fold_build2 (MINUS_EXPR, type, iv1->base, diff);
+ mbzl = fold_convert (type1, iv0->base);
+ mbzr = fold_build2 (MINUS_EXPR, type1,
+ fold_convert (type1, iv1->base), diff);
}
if (!integer_nonzerop (assumption))
niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
iv1->base, iv0->base);
niter->niter = delta;
- niter->max = mpz_to_double_int (niter_type, bnds->up);
+ niter->max = mpz_get_double_int (niter_type, bnds->up, false);
return true;
}
mpz_add (tmp, bnds->up, mstep);
mpz_sub_ui (tmp, tmp, 1);
mpz_fdiv_q (tmp, tmp, mstep);
- niter->max = mpz_to_double_int (niter_type, tmp);
+ niter->max = mpz_get_double_int (niter_type, tmp, false);
mpz_clear (mstep);
mpz_clear (tmp);
bounds *bnds)
{
tree assumption;
+ tree type1 = type;
+ if (POINTER_TYPE_P (type))
+ type1 = sizetype;
/* Say that IV0 is the control variable. Then IV0 <= IV1 iff
IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest
}
if (integer_nonzerop (iv0->step))
- iv1->base = fold_build2 (PLUS_EXPR, type,
- iv1->base, build_int_cst (type, 1));
+ {
+ if (POINTER_TYPE_P (type))
+ iv1->base = fold_build2 (POINTER_PLUS_EXPR, type, iv1->base,
+ build_int_cst (type1, 1));
+ else
+ iv1->base = fold_build2 (PLUS_EXPR, type1, iv1->base,
+ build_int_cst (type1, 1));
+ }
+ else if (POINTER_TYPE_P (type))
+ iv0->base = fold_build2 (POINTER_PLUS_EXPR, type, iv0->base,
+ fold_build1 (NEGATE_EXPR, type1,
+ build_int_cst (type1, 1)));
else
- iv0->base = fold_build2 (MINUS_EXPR, type,
- iv0->base, build_int_cst (type, 1));
+ iv0->base = fold_build2 (MINUS_EXPR, type1,
+ iv0->base, build_int_cst (type1, 1));
- bounds_add (bnds, double_int_one, type);
+ bounds_add (bnds, double_int_one, type1);
return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite, bnds);
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file,
- "Analysing # of iterations of loop %d\n", loop->num);
+ "Analyzing # of iterations of loop %d\n", loop->num);
fprintf (dump_file, " exit condition ");
dump_affine_iv (dump_file, iv0);
/* Substitute NEW for OLD in EXPR and fold the result. */
static tree
-simplify_replace_tree (tree expr, tree old, tree new)
+simplify_replace_tree (tree expr, tree old, tree new_tree)
{
unsigned i, n;
tree ret = NULL_TREE, e, se;
if (expr == old
|| operand_equal_p (expr, old, 0))
- return unshare_expr (new);
+ return unshare_expr (new_tree);
- if (!EXPR_P (expr) && !GIMPLE_STMT_P (expr))
+ if (!EXPR_P (expr))
return expr;
n = TREE_OPERAND_LENGTH (expr);
for (i = 0; i < n; i++)
{
e = TREE_OPERAND (expr, i);
- se = simplify_replace_tree (e, old, new);
+ se = simplify_replace_tree (e, old, new_tree);
if (e == se)
continue;
expand_simple_operations (tree expr)
{
unsigned i, n;
- tree ret = NULL_TREE, e, ee, stmt;
+ tree ret = NULL_TREE, e, ee, e1;
enum tree_code code;
+ gimple stmt;
if (expr == NULL_TREE)
return expr;
return expr;
stmt = SSA_NAME_DEF_STMT (expr);
- if (TREE_CODE (stmt) == PHI_NODE)
+ if (gimple_code (stmt) == GIMPLE_PHI)
{
basic_block src, dest;
- if (PHI_NUM_ARGS (stmt) != 1)
+ if (gimple_phi_num_args (stmt) != 1)
return expr;
e = PHI_ARG_DEF (stmt, 0);
/* Avoid propagating through loop exit phi nodes, which
could break loop-closed SSA form restrictions. */
- dest = bb_for_stmt (stmt);
+ dest = gimple_bb (stmt);
src = single_pred (dest);
if (TREE_CODE (e) == SSA_NAME
&& src->loop_father != dest->loop_father)
return expand_simple_operations (e);
}
- if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
+ if (gimple_code (stmt) != GIMPLE_ASSIGN)
return expr;
- e = GIMPLE_STMT_OPERAND (stmt, 1);
- if (/* Casts are simple. */
- TREE_CODE (e) != NOP_EXPR
- && TREE_CODE (e) != CONVERT_EXPR
- /* Copies are simple. */
- && TREE_CODE (e) != SSA_NAME
- /* Assignments of invariants are simple. */
- && !is_gimple_min_invariant (e)
+ e = gimple_assign_rhs1 (stmt);
+ code = gimple_assign_rhs_code (stmt);
+ if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
+ {
+ if (is_gimple_min_invariant (e))
+ return e;
+
+ if (code == SSA_NAME)
+ return expand_simple_operations (e);
+
+ return expr;
+ }
+
+ switch (code)
+ {
+ CASE_CONVERT:
+ /* Casts are simple. */
+ ee = expand_simple_operations (e);
+ return fold_build1 (code, TREE_TYPE (expr), ee);
+
+ case PLUS_EXPR:
+ case MINUS_EXPR:
+ case POINTER_PLUS_EXPR:
/* And increments and decrements by a constant are simple. */
- && !((TREE_CODE (e) == PLUS_EXPR
- || TREE_CODE (e) == MINUS_EXPR)
- && is_gimple_min_invariant (TREE_OPERAND (e, 1))))
- return expr;
+ e1 = gimple_assign_rhs2 (stmt);
+ if (!is_gimple_min_invariant (e1))
+ return expr;
+
+ ee = expand_simple_operations (e);
+ return fold_build2 (code, TREE_TYPE (expr), ee, e1);
- return expand_simple_operations (e);
+ default:
+ return expr;
+ }
}
/* Tries to simplify EXPR using the condition COND. Returns the simplified
{
edge e;
basic_block bb;
+ gimple stmt;
tree cond;
int cnt = 0;
if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
continue;
- cond = COND_EXPR_COND (last_stmt (e->src));
+ stmt = last_stmt (e->src);
+ cond = fold_build2 (gimple_cond_code (stmt),
+ boolean_type_node,
+ gimple_cond_lhs (stmt),
+ gimple_cond_rhs (stmt));
if (e->flags & EDGE_FALSE_VALUE)
cond = invert_truthvalue (cond);
expr = tree_simplify_using_condition (cond, expr);
/* Returns true if EXIT is the only possible exit from LOOP. */
-static bool
-loop_only_exit_p (struct loop *loop, edge exit)
+bool
+loop_only_exit_p (const struct loop *loop, const_edge exit)
{
basic_block *body;
- block_stmt_iterator bsi;
+ gimple_stmt_iterator bsi;
unsigned i;
- tree call;
+ gimple call;
if (exit != single_exit (loop))
return false;
body = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
{
- for (bsi = bsi_start (body[0]); !bsi_end_p (bsi); bsi_next (&bsi))
+ for (bsi = gsi_start_bb (body[i]); !gsi_end_p (bsi); gsi_next (&bsi))
{
- call = get_call_expr_in (bsi_stmt (bsi));
- if (call && TREE_SIDE_EFFECTS (call))
+ call = gsi_stmt (bsi);
+ if (gimple_code (call) != GIMPLE_CALL)
+ continue;
+
+ if (gimple_has_side_effects (call))
{
free (body);
return false;
struct tree_niter_desc *niter,
bool warn)
{
- tree stmt, cond, type;
+ gimple stmt;
+ tree type;
tree op0, op1;
enum tree_code code;
affine_iv iv0, iv1;
niter->assumptions = boolean_false_node;
stmt = last_stmt (exit->src);
- if (!stmt || TREE_CODE (stmt) != COND_EXPR)
+ if (!stmt || gimple_code (stmt) != GIMPLE_COND)
return false;
/* We want the condition for staying inside loop. */
- cond = COND_EXPR_COND (stmt);
+ code = gimple_cond_code (stmt);
if (exit->flags & EDGE_TRUE_VALUE)
- cond = invert_truthvalue (cond);
+ code = invert_tree_comparison (code, false);
- code = TREE_CODE (cond);
switch (code)
{
case GT_EXPR:
return false;
}
- op0 = TREE_OPERAND (cond, 0);
- op1 = TREE_OPERAND (cond, 1);
+ op0 = gimple_cond_lhs (stmt);
+ op1 = gimple_cond_rhs (stmt);
type = TREE_TYPE (op0);
if (TREE_CODE (type) != INTEGER_TYPE
&& !POINTER_TYPE_P (type))
return false;
- if (!simple_iv (loop, stmt, op0, &iv0, false))
+ if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, false))
return false;
- if (!simple_iv (loop, stmt, op1, &iv1, false))
+ if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, false))
return false;
/* We don't want to see undefined signed overflow warnings while
if (warn)
{
const char *wording;
- location_t loc = EXPR_LOCATION (stmt);
+ location_t loc = gimple_location (stmt);
/* We can provide a more specific warning if one of the operator is
constant and the other advances by +1 or -1. */
return niter ? niter : chrec_dont_know;
}
+/* Return true if loop is known to have bounded number of iterations. */
+
+bool
+finite_loop_p (struct loop *loop)
+{
+ unsigned i;
+ VEC (edge, heap) *exits = get_loop_exit_edges (loop);
+ edge ex;
+ struct tree_niter_desc desc;
+ bool finite = false;
+
+ if (flag_unsafe_loop_optimizations)
+ return true;
+ if ((TREE_READONLY (current_function_decl)
+ || DECL_PURE_P (current_function_decl))
+ && !DECL_LOOPING_CONST_OR_PURE_P (current_function_decl))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Found loop %i to be finite: it is within pure or const function.\n",
+ loop->num);
+ return true;
+ }
+
+ exits = get_loop_exit_edges (loop);
+ for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
+ {
+ if (!just_once_each_iteration_p (loop, ex->src))
+ continue;
+
+ if (number_of_iterations_exit (loop, ex, &desc, false))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Found loop %i to be finite: iterating ", loop->num);
+ print_generic_expr (dump_file, desc.niter, TDF_SLIM);
+ fprintf (dump_file, " times\n");
+ }
+ finite = true;
+ break;
+ }
+ }
+ VEC_free (edge, heap, exits);
+ return finite;
+}
+
/*
Analysis of a number of iterations of a loop by a brute-force evaluation.
result by a chain of operations such that all but exactly one of their
operands are constants. */
-static tree
+static gimple
chain_of_csts_start (struct loop *loop, tree x)
{
- tree stmt = SSA_NAME_DEF_STMT (x);
+ gimple stmt = SSA_NAME_DEF_STMT (x);
tree use;
- basic_block bb = bb_for_stmt (stmt);
+ basic_block bb = gimple_bb (stmt);
+ enum tree_code code;
if (!bb
|| !flow_bb_inside_loop_p (loop, bb))
- return NULL_TREE;
+ return NULL;
- if (TREE_CODE (stmt) == PHI_NODE)
+ if (gimple_code (stmt) == GIMPLE_PHI)
{
if (bb == loop->header)
return stmt;
- return NULL_TREE;
+ return NULL;
}
- if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
- return NULL_TREE;
+ if (gimple_code (stmt) != GIMPLE_ASSIGN)
+ return NULL;
- if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
- return NULL_TREE;
- if (SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF) == NULL_DEF_OPERAND_P)
- return NULL_TREE;
+ code = gimple_assign_rhs_code (stmt);
+ if (gimple_references_memory_p (stmt)
+ || TREE_CODE_CLASS (code) == tcc_reference
+ || (code == ADDR_EXPR
+ && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
+ return NULL;
use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
- if (use == NULL_USE_OPERAND_P)
- return NULL_TREE;
+ if (use == NULL_TREE)
+ return NULL;
return chain_of_csts_start (loop, use);
}
* 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. */
+ If such phi node exists, it is returned, otherwise NULL is returned. */
-static tree
+static gimple
get_base_for (struct loop *loop, tree x)
{
- tree phi, init, next;
+ gimple phi;
+ tree init, next;
if (is_gimple_min_invariant (x))
- return x;
+ return NULL;
phi = chain_of_csts_start (loop, x);
if (!phi)
- return NULL_TREE;
+ return NULL;
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;
+ return NULL;
if (!is_gimple_min_invariant (init))
- return NULL_TREE;
+ return NULL;
if (chain_of_csts_start (loop, next) != phi)
- return NULL_TREE;
+ return NULL;
return phi;
}
static tree
get_val_for (tree x, tree base)
{
- tree stmt, nx, val;
- use_operand_p op;
- ssa_op_iter iter;
+ gimple stmt;
gcc_assert (is_gimple_min_invariant (base));
return base;
stmt = SSA_NAME_DEF_STMT (x);
- if (TREE_CODE (stmt) == PHI_NODE)
+ if (gimple_code (stmt) == GIMPLE_PHI)
return base;
- FOR_EACH_SSA_USE_OPERAND (op, stmt, iter, SSA_OP_USE)
+ gcc_assert (is_gimple_assign (stmt));
+
+ /* STMT must be either an assignment of a single SSA name or an
+ expression involving an SSA name and a constant. Try to fold that
+ expression using the value for the SSA name. */
+ if (gimple_assign_ssa_name_copy_p (stmt))
+ return get_val_for (gimple_assign_rhs1 (stmt), base);
+ else if (gimple_assign_rhs_class (stmt) == GIMPLE_UNARY_RHS
+ && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
{
- nx = USE_FROM_PTR (op);
- val = get_val_for (nx, base);
- SET_USE (op, val);
- val = fold (GIMPLE_STMT_OPERAND (stmt, 1));
- SET_USE (op, nx);
- /* only iterate loop once. */
- return val;
+ return fold_build1 (gimple_assign_rhs_code (stmt),
+ gimple_expr_type (stmt),
+ get_val_for (gimple_assign_rhs1 (stmt), base));
}
-
- /* Should never reach here. */
- gcc_unreachable ();
+ else if (gimple_assign_rhs_class (stmt) == GIMPLE_BINARY_RHS)
+ {
+ tree rhs1 = gimple_assign_rhs1 (stmt);
+ tree rhs2 = gimple_assign_rhs2 (stmt);
+ if (TREE_CODE (rhs1) == SSA_NAME)
+ rhs1 = get_val_for (rhs1, base);
+ else if (TREE_CODE (rhs2) == SSA_NAME)
+ rhs2 = get_val_for (rhs2, base);
+ else
+ gcc_unreachable ();
+ return fold_build2 (gimple_assign_rhs_code (stmt),
+ gimple_expr_type (stmt), rhs1, rhs2);
+ }
+ else
+ gcc_unreachable ();
}
+
/* 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
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];
+ tree acnd;
+ tree op[2], val[2], next[2], aval[2];
+ gimple phi, cond;
unsigned i, j;
enum tree_code cmp;
cond = last_stmt (exit->src);
- if (!cond || TREE_CODE (cond) != COND_EXPR)
+ if (!cond || gimple_code (cond) != GIMPLE_COND)
return chrec_dont_know;
- cnd = COND_EXPR_COND (cond);
+ cmp = gimple_cond_code (cond);
if (exit->flags & EDGE_TRUE_VALUE)
- cnd = invert_truthvalue (cnd);
+ cmp = invert_tree_comparison (cmp, false);
- cmp = TREE_CODE (cnd);
switch (cmp)
{
case EQ_EXPR:
case GE_EXPR:
case LT_EXPR:
case LE_EXPR:
- for (j = 0; j < 2; j++)
- op[j] = TREE_OPERAND (cnd, j);
+ op[0] = gimple_cond_lhs (cond);
+ op[1] = gimple_cond_rhs (cond);
break;
default:
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)
+ if (is_gimple_min_invariant (op[j]))
{
- 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));
+ val[j] = op[j];
+ next[j] = NULL_TREE;
+ op[j] = NULL_TREE;
}
else
{
- val[j] = phi[j];
- next[j] = NULL_TREE;
- op[j] = NULL_TREE;
+ phi = get_base_for (loop, op[j]);
+ if (!phi)
+ return chrec_dont_know;
+ val[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
+ next[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
}
}
*/
+static double_int derive_constant_upper_bound_ops (tree, tree,
+ enum tree_code, tree);
+
+/* Returns a constant upper bound on the value of the right-hand side of
+ an assignment statement STMT. */
+
+static double_int
+derive_constant_upper_bound_assign (gimple stmt)
+{
+ enum tree_code code = gimple_assign_rhs_code (stmt);
+ tree op0 = gimple_assign_rhs1 (stmt);
+ tree op1 = gimple_assign_rhs2 (stmt);
+
+ return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt)),
+ op0, code, op1);
+}
+
/* Returns a constant upper bound on the value of expression VAL. VAL
is considered to be unsigned. If its type is signed, its value must
be nonnegative. */
static double_int
derive_constant_upper_bound (tree val)
{
- tree type = TREE_TYPE (val);
- tree op0, op1, subtype, maxt;
+ enum tree_code code;
+ tree op0, op1;
+
+ extract_ops_from_tree (val, &code, &op0, &op1);
+ return derive_constant_upper_bound_ops (TREE_TYPE (val), op0, code, op1);
+}
+
+/* Returns a constant upper bound on the value of expression OP0 CODE OP1,
+ whose type is TYPE. The expression is considered to be unsigned. If
+ its type is signed, its value must be nonnegative. */
+
+static double_int
+derive_constant_upper_bound_ops (tree type, tree op0,
+ enum tree_code code, tree op1)
+{
+ tree subtype, maxt;
double_int bnd, max, mmax, cst;
- tree stmt;
+ gimple stmt;
if (INTEGRAL_TYPE_P (type))
maxt = TYPE_MAX_VALUE (type);
max = tree_to_double_int (maxt);
- switch (TREE_CODE (val))
+ switch (code)
{
case INTEGER_CST:
- return tree_to_double_int (val);
+ return tree_to_double_int (op0);
- case NOP_EXPR:
- case CONVERT_EXPR:
- op0 = TREE_OPERAND (val, 0);
+ CASE_CONVERT:
subtype = TREE_TYPE (op0);
if (!TYPE_UNSIGNED (subtype)
/* If TYPE is also signed, the fact that VAL is nonnegative implies
return bnd;
case PLUS_EXPR:
+ case POINTER_PLUS_EXPR:
case MINUS_EXPR:
- op0 = TREE_OPERAND (val, 0);
- op1 = TREE_OPERAND (val, 1);
-
if (TREE_CODE (op1) != INTEGER_CST
|| !tree_expr_nonnegative_p (op0))
return max;
of the signedness of the type. */
cst = tree_to_double_int (op1);
cst = double_int_sext (cst, TYPE_PRECISION (type));
- if (TREE_CODE (val) == PLUS_EXPR)
+ if (code != MINUS_EXPR)
cst = double_int_neg (cst);
bnd = derive_constant_upper_bound (op0);
case FLOOR_DIV_EXPR:
case EXACT_DIV_EXPR:
- op0 = TREE_OPERAND (val, 0);
- op1 = TREE_OPERAND (val, 1);
if (TREE_CODE (op1) != INTEGER_CST
|| tree_int_cst_sign_bit (op1))
return max;
return double_int_udiv (bnd, tree_to_double_int (op1), FLOOR_DIV_EXPR);
case BIT_AND_EXPR:
- op1 = TREE_OPERAND (val, 1);
if (TREE_CODE (op1) != INTEGER_CST
|| tree_int_cst_sign_bit (op1))
return max;
return tree_to_double_int (op1);
case SSA_NAME:
- stmt = SSA_NAME_DEF_STMT (val);
- if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT
- || GIMPLE_STMT_OPERAND (stmt, 0) != val)
+ stmt = SSA_NAME_DEF_STMT (op0);
+ if (gimple_code (stmt) != GIMPLE_ASSIGN
+ || gimple_assign_lhs (stmt) != op0)
return max;
- return derive_constant_upper_bound (GIMPLE_STMT_OPERAND (stmt, 1));
+ return derive_constant_upper_bound_assign (stmt);
default:
return max;
}
/* Records that every statement in LOOP is executed I_BOUND times.
- REALISTIC is true if I_BOUND is expected to be close the the real number
+ REALISTIC is true if I_BOUND is expected to be close to the real number
of iterations. UPPER is true if we are sure the loop iterates at most
I_BOUND times. */
/* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
is true if the loop is exited immediately after STMT, and this exit
is taken at last when the STMT is executed BOUND + 1 times.
- REALISTIC is true if BOUND is expected to be close the the real number
+ REALISTIC is true if BOUND is expected to be close to the real number
of iterations. UPPER is true if we are sure the loop iterates at most
BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */
static void
record_estimate (struct loop *loop, tree bound, double_int i_bound,
- tree at_stmt, bool is_exit, bool realistic, bool upper)
+ gimple at_stmt, bool is_exit, bool realistic, bool upper)
{
double_int delta;
edge exit;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : "");
- print_generic_expr (dump_file, at_stmt, TDF_SLIM);
+ print_gimple_stmt (dump_file, at_stmt, 0, TDF_SLIM);
fprintf (dump_file, " is %sexecuted at most ",
upper ? "" : "probably ");
print_generic_expr (dump_file, bound, TDF_SLIM);
list. */
if (upper)
{
- struct nb_iter_bound *elt = XNEW (struct nb_iter_bound);
+ struct nb_iter_bound *elt = GGC_NEW (struct nb_iter_bound);
elt->bound = i_bound;
elt->stmt = at_stmt;
if (is_exit
|| (exit != NULL
&& dominated_by_p (CDI_DOMINATORS,
- exit->src, bb_for_stmt (at_stmt))))
+ exit->src, gimple_bb (at_stmt))))
delta = double_int_one;
else
delta = double_int_two;
i_bound = double_int_add (i_bound, delta);
- /* If an overflow occured, ignore the result. */
+ /* If an overflow occurred, ignore the result. */
if (double_int_ucmp (i_bound, delta) < 0)
return;
UPPER is true if we are sure the induction variable does not wrap. */
static void
-record_nonwrapping_iv (struct loop *loop, tree base, tree step, tree stmt,
+record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple stmt,
tree low, tree high, bool realistic, bool upper)
{
tree niter_bound, extreme, delta;
fprintf (dump_file, " + ");
print_generic_expr (dump_file, step, TDF_SLIM);
fprintf (dump_file, " * iteration does not wrap in statement ");
- print_generic_expr (dump_file, stmt, TDF_SLIM);
+ print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
fprintf (dump_file, " in loop %d.\n", loop->num);
}
struct ilb_data
{
struct loop *loop;
- tree stmt;
+ gimple stmt;
bool reliable;
};
static bool
idx_infer_loop_bounds (tree base, tree *idx, void *dta)
{
- struct ilb_data *data = dta;
+ struct ilb_data *data = (struct ilb_data *) dta;
tree ev, init, step;
tree low, high, type, next;
bool sign, upper = data->reliable, at_end = false;
STMT is guaranteed to be executed in every iteration of LOOP.*/
static void
-infer_loop_bounds_from_ref (struct loop *loop, tree stmt, tree ref,
+infer_loop_bounds_from_ref (struct loop *loop, gimple stmt, tree ref,
bool reliable)
{
struct ilb_data data;
executed in every iteration of LOOP. */
static void
-infer_loop_bounds_from_array (struct loop *loop, tree stmt, bool reliable)
+infer_loop_bounds_from_array (struct loop *loop, gimple stmt, bool reliable)
{
- tree call;
-
- if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
+ if (is_gimple_assign (stmt))
{
- tree op0 = GIMPLE_STMT_OPERAND (stmt, 0);
- tree op1 = GIMPLE_STMT_OPERAND (stmt, 1);
+ tree op0 = gimple_assign_lhs (stmt);
+ tree op1 = gimple_assign_rhs1 (stmt);
/* For each memory access, analyze its access function
and record a bound on the loop iteration domain. */
if (REFERENCE_CLASS_P (op1))
infer_loop_bounds_from_ref (loop, stmt, op1, reliable);
}
-
-
- call = get_call_expr_in (stmt);
- if (call)
+ else if (is_gimple_call (stmt))
{
- tree arg;
- call_expr_arg_iterator iter;
+ tree arg, lhs;
+ unsigned i, n = gimple_call_num_args (stmt);
- FOR_EACH_CALL_EXPR_ARG (arg, iter, call)
- if (REFERENCE_CLASS_P (arg))
- infer_loop_bounds_from_ref (loop, stmt, arg, reliable);
+ lhs = gimple_call_lhs (stmt);
+ if (lhs && REFERENCE_CLASS_P (lhs))
+ infer_loop_bounds_from_ref (loop, stmt, lhs, reliable);
+
+ for (i = 0; i < n; i++)
+ {
+ arg = gimple_call_arg (stmt, i);
+ if (REFERENCE_CLASS_P (arg))
+ infer_loop_bounds_from_ref (loop, stmt, arg, reliable);
+ }
}
}
that signed arithmetics in STMT does not overflow. */
static void
-infer_loop_bounds_from_signedness (struct loop *loop, tree stmt)
+infer_loop_bounds_from_signedness (struct loop *loop, gimple stmt)
{
tree def, base, step, scev, type, low, high;
- if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
+ if (gimple_code (stmt) != GIMPLE_ASSIGN)
return;
- def = GIMPLE_STMT_OPERAND (stmt, 0);
+ def = gimple_assign_lhs (stmt);
if (TREE_CODE (def) != SSA_NAME)
return;
{
unsigned i;
basic_block *bbs;
- block_stmt_iterator bsi;
+ gimple_stmt_iterator bsi;
basic_block bb;
bool reliable;
# of iterations of the loop. However, we can use it as a guess. */
reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb);
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
{
- tree stmt = bsi_stmt (bsi);
+ gimple stmt = gsi_stmt (bsi);
infer_loop_bounds_from_array (loop, stmt, reliable);
/* Returns true if statement S1 dominates statement S2. */
-static bool
-stmt_dominates_stmt_p (tree s1, tree s2)
+bool
+stmt_dominates_stmt_p (gimple s1, gimple s2)
{
- basic_block bb1 = bb_for_stmt (s1), bb2 = bb_for_stmt (s2);
+ basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
if (!bb1
|| s1 == s2)
if (bb1 == bb2)
{
- block_stmt_iterator bsi;
+ gimple_stmt_iterator bsi;
+
+ if (gimple_code (s2) == GIMPLE_PHI)
+ return false;
+
+ if (gimple_code (s1) == GIMPLE_PHI)
+ return true;
- for (bsi = bsi_start (bb1); bsi_stmt (bsi) != s2; bsi_next (&bsi))
- if (bsi_stmt (bsi) == s1)
+ for (bsi = gsi_start_bb (bb1); gsi_stmt (bsi) != s2; gsi_next (&bsi))
+ if (gsi_stmt (bsi) == s1)
return true;
return false;
statements in the loop. */
static bool
-n_of_executions_at_most (tree stmt,
+n_of_executions_at_most (gimple stmt,
struct nb_iter_bound *niter_bound,
tree niter)
{
else
{
if (!stmt
- || (bb_for_stmt (stmt) != bb_for_stmt (niter_bound->stmt)
+ || (gimple_bb (stmt) != gimple_bb (niter_bound->stmt)
&& !stmt_dominates_stmt_p (niter_bound->stmt, stmt)))
{
bound = double_int_add (bound, double_int_one);
bool
scev_probably_wraps_p (tree base, tree step,
- tree at_stmt, struct loop *loop,
+ gimple at_stmt, struct loop *loop,
bool use_overflow_semantics)
{
struct nb_iter_bound *bound;
2032, 2040, 0, 8, ..., but the code is still legal. */
if (chrec_contains_undetermined (base)
- || chrec_contains_undetermined (step)
- || TREE_CODE (step) != INTEGER_CST)
+ || chrec_contains_undetermined (step))
return true;
if (integer_zerop (step))
/* If we can use the fact that signed and pointer arithmetics does not
wrap, we are done. */
- if (use_overflow_semantics && nowrap_type_p (type))
+ if (use_overflow_semantics && nowrap_type_p (TREE_TYPE (base)))
return false;
+ /* To be able to use estimates on number of iterations of the loop,
+ we must have an upper bound on the absolute value of the step. */
+ if (TREE_CODE (step) != INTEGER_CST)
+ return true;
+
/* Don't issue signed overflow warnings. */
fold_defer_overflow_warnings ();
for (bound = loop->bounds; bound; bound = next)
{
next = bound->next;
- free (bound);
+ ggc_free (bound);
}
loop->bounds = NULL;