/* Scalar evolution detector.
- Copyright (C) 2003, 2004 Free Software Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
Contributed by Sebastian Pop <s.pop@laposte.net>
This file is part of GCC.
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. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
/*
Description:
Given a scalar variable to be analyzed, follow the SSA edge to
its definition:
- - When the definition is a MODIFY_EXPR: if the right hand side
+ - When the definition is a GIMPLE_MODIFY_STMT: if the right hand side
(RHS) of the definition cannot be statically analyzed, the answer
of the analyzer is: "don't know".
Otherwise, for all the variables that are not yet analyzed in the
#include "system.h"
#include "coretypes.h"
#include "tm.h"
-#include "errors.h"
#include "ggc.h"
#include "tree.h"
+#include "real.h"
/* These RTL headers are needed for basic-block.h. */
#include "rtl.h"
#include "tree-scalar-evolution.h"
#include "tree-pass.h"
#include "flags.h"
+#include "params.h"
static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
-static tree resolve_mixers (struct loop *, tree);
/* The cached information about a ssa name VAR, claiming that inside LOOP,
the value of VAR can be expressed as CHREC. */
-struct scev_info_str
+struct scev_info_str GTY(())
{
tree var;
tree chrec;
static bitmap already_instantiated;
-static htab_t scalar_evolution_info;
+static GTY ((param_is (struct scev_info_str))) htab_t scalar_evolution_info;
\f
/* Constructs a new SCEV_INFO_STR structure. */
{
struct scev_info_str *res;
- res = xmalloc (sizeof (struct scev_info_str));
+ res = GGC_NEW (struct scev_info_str);
res->var = var;
res->chrec = chrec_not_analyzed_yet;
static int
eq_scev_info (const void *e1, const void *e2)
{
- const struct scev_info_str *elt1 = e1;
- const struct scev_info_str *elt2 = e2;
+ const struct scev_info_str *elt1 = (const struct scev_info_str *) e1;
+ const struct scev_info_str *elt2 = (const struct scev_info_str *) e2;
return elt1->var == elt2->var;
}
static void
del_scev_info (void *e)
{
- free (e);
+ ggc_free (e);
}
/* Get the index corresponding to VAR in the current LOOP. If
it's the first time we ask for this VAR, then we return
- chrec_not_analysed_yet for this VAR and return its index. */
+ chrec_not_analyzed_yet for this VAR and return its index. */
static tree *
find_var_scev_info (tree var)
if (!*slot)
*slot = new_scev_info_str (var);
- res = *slot;
+ res = (struct scev_info_str *) *slot;
return &res->chrec;
}
-/* Tries to express CHREC in wider type TYPE. */
-
-tree
-count_ev_in_wider_type (tree type, tree chrec)
-{
- tree base, step;
- struct loop *loop;
-
- if (!evolution_function_is_affine_p (chrec))
- return fold_convert (type, chrec);
-
- base = CHREC_LEFT (chrec);
- step = CHREC_RIGHT (chrec);
- loop = current_loops->parray[CHREC_VARIABLE (chrec)];
-
- /* TODO -- if we knew the statement at that the conversion occurs,
- we could pass it to can_count_iv_in_wider_type and get a better
- result. */
- step = can_count_iv_in_wider_type (loop, type, base, step, NULL_TREE);
- if (!step)
- return fold_convert (type, chrec);
- base = chrec_convert (type, base);
-
- return build_polynomial_chrec (CHREC_VARIABLE (chrec),
- base, step);
-}
-
/* Return true when CHREC contains symbolic names defined in
LOOP_NB. */
bool
chrec_contains_symbols_defined_in_loop (tree chrec, unsigned loop_nb)
{
+ int i, n;
+
if (chrec == NULL_TREE)
return false;
{
tree def = SSA_NAME_DEF_STMT (chrec);
struct loop *def_loop = loop_containing_stmt (def);
- struct loop *loop = current_loops->parray[loop_nb];
+ struct loop *loop = get_loop (loop_nb);
if (def_loop == NULL)
return false;
return false;
}
- switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
- {
- case 3:
- if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 2),
- loop_nb))
- return true;
-
- case 2:
- if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 1),
- loop_nb))
- return true;
-
- case 1:
- if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, 0),
- loop_nb))
- return true;
-
- default:
- return false;
- }
+ n = TREE_OPERAND_LENGTH (chrec);
+ for (i = 0; i < n; i++)
+ if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
+ loop_nb))
+ return true;
+ return false;
}
/* Return true when PHI is a loop-phi-node. */
else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
{
- if (CHREC_VARIABLE (evolution_fn) >= (unsigned) loop->num)
+ struct loop *inner_loop = get_chrec_loop (evolution_fn);
+
+ if (inner_loop == loop
+ || flow_loop_nested_p (loop, inner_loop))
{
- struct loop *inner_loop =
- current_loops->parray[CHREC_VARIABLE (evolution_fn)];
- tree nb_iter = number_of_iterations_in_loop (inner_loop);
+ tree nb_iter = number_of_latch_executions (inner_loop);
if (nb_iter == chrec_dont_know)
return chrec_dont_know;
{
tree res;
- /* Number of iterations is off by one (the ssa name we
- analyze must be defined before the exit). */
- nb_iter = chrec_fold_minus (chrec_type (nb_iter),
- nb_iter,
- fold_convert (chrec_type (nb_iter),
- integer_one_node));
-
/* evolution_fn is the evolution function in LOOP. Get
its value in the nb_iter-th iteration. */
res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
- /* Continue the computation until ending on a parent of LOOP. */
+ /* Continue the computation until ending on a parent of LOOP. */
return compute_overall_effect_of_inner_loop (loop, res);
}
}
bool
chrec_is_positive (tree chrec, bool *value)
{
- bool value0, value1;
- bool value2;
- tree end_value;
- tree nb_iter;
+ bool value0, value1, value2;
+ tree end_value, nb_iter;
switch (TREE_CODE (chrec))
{
if (!evolution_function_is_affine_p (chrec))
return false;
- nb_iter = number_of_iterations_in_loop
- (current_loops->parray[CHREC_VARIABLE (chrec)]);
-
+ nb_iter = number_of_latch_executions (get_chrec_loop (chrec));
if (chrec_contains_undetermined (nb_iter))
return false;
- nb_iter = chrec_fold_minus
- (chrec_type (nb_iter), nb_iter,
- fold_convert (chrec_type (nb_iter), integer_one_node));
-
#if 0
/* TODO -- If the test is after the exit, we may decrease the number of
iterations by one. */
if (after_exit)
- nb_iter = chrec_fold_minus
- (chrec_type (nb_iter), nb_iter,
- fold_convert (chrec_type (nb_iter), integer_one_node));
+ nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1));
#endif
end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
part for this loop. */
static tree
-add_to_evolution_1 (unsigned loop_nb,
- tree chrec_before,
- tree to_add)
+add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
+ tree at_stmt)
{
+ tree type, left, right;
+ struct loop *loop = get_loop (loop_nb), *chloop;
+
switch (TREE_CODE (chrec_before))
{
case POLYNOMIAL_CHREC:
- if (CHREC_VARIABLE (chrec_before) <= loop_nb)
+ chloop = get_chrec_loop (chrec_before);
+ if (chloop == loop
+ || flow_loop_nested_p (chloop, loop))
{
unsigned var;
- tree left, right;
- tree type = chrec_type (chrec_before);
+
+ type = chrec_type (chrec_before);
/* When there is no evolution part in this loop, build it. */
- if (CHREC_VARIABLE (chrec_before) < loop_nb)
+ if (chloop != loop)
{
var = loop_nb;
left = chrec_before;
- right = fold_convert (type, integer_zero_node);
+ right = SCALAR_FLOAT_TYPE_P (type)
+ ? build_real (type, dconst0)
+ : build_int_cst (type, 0);
}
else
{
right = CHREC_RIGHT (chrec_before);
}
- return build_polynomial_chrec
- (var, left, chrec_fold_plus (type, right, to_add));
+ to_add = chrec_convert (type, to_add, at_stmt);
+ right = chrec_convert (type, right, at_stmt);
+ right = chrec_fold_plus (type, right, to_add);
+ return build_polynomial_chrec (var, left, right);
}
else
- /* Search the evolution in LOOP_NB. */
- return build_polynomial_chrec
- (CHREC_VARIABLE (chrec_before),
- add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before), to_add),
- CHREC_RIGHT (chrec_before));
+ {
+ gcc_assert (flow_loop_nested_p (loop, chloop));
+
+ /* Search the evolution in LOOP_NB. */
+ left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before),
+ to_add, at_stmt);
+ right = CHREC_RIGHT (chrec_before);
+ right = chrec_convert (chrec_type (left), right, at_stmt);
+ return build_polynomial_chrec (CHREC_VARIABLE (chrec_before),
+ left, right);
+ }
default:
/* These nodes do not depend on a loop. */
if (chrec_before == chrec_dont_know)
return chrec_dont_know;
- return build_polynomial_chrec (loop_nb, chrec_before, to_add);
+
+ left = chrec_before;
+ right = chrec_convert (chrec_type (left), to_add, at_stmt);
+ return build_polynomial_chrec (loop_nb, left, right);
}
}
*/
static tree
-add_to_evolution (unsigned loop_nb,
- tree chrec_before,
- enum tree_code code,
- tree to_add)
+add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
+ tree to_add, tree at_stmt)
{
tree type = chrec_type (to_add);
tree res = NULL_TREE;
}
if (code == MINUS_EXPR)
- to_add = chrec_fold_multiply (type, to_add,
- fold_convert (type, integer_minus_one_node));
+ to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type)
+ ? build_real (type, dconstm1)
+ : build_int_cst_type (type, -1));
- res = add_to_evolution_1 (loop_nb, chrec_before, to_add);
+ res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt);
if (dump_file && (dump_flags & TDF_DETAILS))
{
set_nb_iterations_in_loop (struct loop *loop,
tree res)
{
- res = chrec_fold_plus (chrec_type (res), res, integer_one_node);
- /* FIXME HWI: However we want to store one iteration less than the
- count of the loop in order to be compatible with the other
- nb_iter computations in loop-iv. This also allows the
- representation of nb_iters that are equal to MAX_INT. */
- if ((TREE_CODE (res) == INTEGER_CST && TREE_INT_CST_LOW (res) == 0)
- || TREE_OVERFLOW (res))
- res = chrec_dont_know;
-
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (set_nb_iterations_in_loop = ");
switch (TREE_CODE (condition))
{
case SSA_NAME:
- /* Volatile expressions are not analyzable. */
- if (TREE_THIS_VOLATILE (SSA_NAME_VAR (condition)))
- return false;
return true;
case LT_EXPR:
case GE_EXPR:
case EQ_EXPR:
case NE_EXPR:
- {
- tree opnd0, opnd1;
-
- opnd0 = TREE_OPERAND (condition, 0);
- opnd1 = TREE_OPERAND (condition, 1);
-
- if (TREE_CODE (opnd0) == SSA_NAME
- && TREE_THIS_VOLATILE (SSA_NAME_VAR (opnd0)))
- return false;
-
- if (TREE_CODE (opnd1) == SSA_NAME
- && TREE_THIS_VOLATILE (SSA_NAME_VAR (opnd1)))
- return false;
-
- return true;
- }
+ return true;
default:
return false;
get_loop_exit_condition (struct loop *loop)
{
tree res = NULL_TREE;
+ edge exit_edge = single_exit (loop);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(get_loop_exit_condition \n ");
- if (loop->exit_edges)
+ if (exit_edge)
{
- edge exit_edge;
tree expr;
- exit_edge = loop->exit_edges[0];
expr = last_stmt (exit_edge->src);
-
if (analyzable_condition (expr))
res = expr;
}
static void
get_exit_conditions_rec (struct loop *loop,
- varray_type *exit_conditions)
+ VEC(tree,heap) **exit_conditions)
{
if (!loop)
return;
get_exit_conditions_rec (loop->inner, exit_conditions);
get_exit_conditions_rec (loop->next, exit_conditions);
- flow_loop_scan (loop, LOOP_EXIT_EDGES);
- if (loop->num_exits == 1)
+ if (single_exit (loop))
{
tree loop_condition = get_loop_exit_condition (loop);
if (loop_condition)
- VARRAY_PUSH_TREE (*exit_conditions, loop_condition);
+ VEC_safe_push (tree, heap, *exit_conditions, loop_condition);
}
}
/* Select the candidate loop nests for the analysis. This function
- initializes the EXIT_CONDITIONS array. */
+ initializes the EXIT_CONDITIONS array. */
static void
-select_loops_exit_conditions (struct loops *loops,
- varray_type *exit_conditions)
+select_loops_exit_conditions (VEC(tree,heap) **exit_conditions)
{
- struct loop *function_body = loops->parray[0];
+ struct loop *function_body = current_loops->tree_root;
get_exit_conditions_rec (function_body->inner, exit_conditions);
}
\f
/* Depth first search algorithm. */
-static bool follow_ssa_edge (struct loop *loop, tree, tree, tree *);
+typedef enum t_bool {
+ t_false,
+ t_true,
+ t_dont_know
+} t_bool;
+
+
+static t_bool follow_ssa_edge (struct loop *loop, tree, tree, tree *, int);
/* Follow the ssa edge into the right hand side RHS of an assignment.
Return true if the strongly connected component has been found. */
-static bool
-follow_ssa_edge_in_rhs (struct loop *loop,
- tree rhs,
- tree halting_phi,
- tree *evolution_of_loop)
+static t_bool
+follow_ssa_edge_in_rhs (struct loop *loop, tree at_stmt, tree rhs,
+ tree halting_phi, tree *evolution_of_loop, int limit)
{
- bool res = false;
+ t_bool res = t_false;
tree rhs0, rhs1;
tree type_rhs = TREE_TYPE (rhs);
+ tree evol;
/* The RHS is one of the following cases:
- an SSA_NAME,
- an INTEGER_CST,
- a PLUS_EXPR,
- a MINUS_EXPR,
- - other cases are not yet handled.
- */
+ - an ASSERT_EXPR,
+ - other cases are not yet handled. */
switch (TREE_CODE (rhs))
{
case NOP_EXPR:
/* This assignment is under the form "a_1 = (cast) rhs. */
- res = follow_ssa_edge_in_rhs (loop, TREE_OPERAND (rhs, 0), halting_phi,
- evolution_of_loop);
- *evolution_of_loop = chrec_convert (TREE_TYPE (rhs), *evolution_of_loop);
+ res = follow_ssa_edge_in_rhs (loop, at_stmt, TREE_OPERAND (rhs, 0),
+ halting_phi, evolution_of_loop, limit);
+ *evolution_of_loop = chrec_convert (TREE_TYPE (rhs),
+ *evolution_of_loop, at_stmt);
break;
case INTEGER_CST:
/* This assignment is under the form "a_1 = 7". */
- res = false;
+ res = t_false;
break;
case SSA_NAME:
/* This assignment is under the form: "a_1 = b_2". */
res = follow_ssa_edge
- (loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop);
+ (loop, SSA_NAME_DEF_STMT (rhs), halting_phi, evolution_of_loop, limit);
break;
case PLUS_EXPR:
{
/* Match an assignment under the form:
"a = b + c". */
+ evol = *evolution_of_loop;
res = follow_ssa_edge
(loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
- evolution_of_loop);
+ &evol, limit);
- if (res)
+ if (res == t_true)
*evolution_of_loop = add_to_evolution
(loop->num,
- chrec_convert (type_rhs, *evolution_of_loop),
- PLUS_EXPR, rhs1);
+ chrec_convert (type_rhs, evol, at_stmt),
+ PLUS_EXPR, rhs1, at_stmt);
- else
+ else if (res == t_false)
{
res = follow_ssa_edge
(loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
- evolution_of_loop);
+ evolution_of_loop, limit);
- if (res)
+ if (res == t_true)
*evolution_of_loop = add_to_evolution
(loop->num,
- chrec_convert (type_rhs, *evolution_of_loop),
- PLUS_EXPR, rhs0);
+ chrec_convert (type_rhs, *evolution_of_loop, at_stmt),
+ PLUS_EXPR, rhs0, at_stmt);
+
+ else if (res == t_dont_know)
+ *evolution_of_loop = chrec_dont_know;
}
+
+ else if (res == t_dont_know)
+ *evolution_of_loop = chrec_dont_know;
}
else
"a = b + ...". */
res = follow_ssa_edge
(loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
- evolution_of_loop);
- if (res)
+ evolution_of_loop, limit);
+ if (res == t_true)
*evolution_of_loop = add_to_evolution
- (loop->num, chrec_convert (type_rhs, *evolution_of_loop),
- PLUS_EXPR, rhs1);
+ (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
+ at_stmt),
+ PLUS_EXPR, rhs1, at_stmt);
+
+ else if (res == t_dont_know)
+ *evolution_of_loop = chrec_dont_know;
}
}
"a = ... + c". */
res = follow_ssa_edge
(loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
- evolution_of_loop);
- if (res)
+ evolution_of_loop, limit);
+ if (res == t_true)
*evolution_of_loop = add_to_evolution
- (loop->num, chrec_convert (type_rhs, *evolution_of_loop),
- PLUS_EXPR, rhs0);
+ (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
+ at_stmt),
+ PLUS_EXPR, rhs0, at_stmt);
+
+ else if (res == t_dont_know)
+ *evolution_of_loop = chrec_dont_know;
}
else
/* Otherwise, match an assignment under the form:
"a = ... + ...". */
/* And there is nothing to do. */
- res = false;
+ res = t_false;
break;
if (TREE_CODE (rhs0) == SSA_NAME)
{
- if (TREE_CODE (rhs1) == SSA_NAME)
- {
- /* Match an assignment under the form:
- "a = b - c". */
- res = follow_ssa_edge
- (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
- evolution_of_loop);
-
- if (res)
- *evolution_of_loop = add_to_evolution
- (loop->num, chrec_convert (type_rhs, *evolution_of_loop),
- MINUS_EXPR, rhs1);
-
- else
- {
- res = follow_ssa_edge
- (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
- evolution_of_loop);
-
- if (res)
- *evolution_of_loop = add_to_evolution
- (loop->num,
- chrec_fold_multiply (type_rhs,
- *evolution_of_loop,
- fold_convert (type_rhs,
- integer_minus_one_node)),
- PLUS_EXPR, rhs0);
- }
- }
-
- else
- {
- /* Match an assignment under the form:
- "a = b - ...". */
- res = follow_ssa_edge
- (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
- evolution_of_loop);
- if (res)
- *evolution_of_loop = add_to_evolution
- (loop->num, chrec_convert (type_rhs, *evolution_of_loop),
- MINUS_EXPR, rhs1);
- }
- }
-
- else if (TREE_CODE (rhs1) == SSA_NAME)
- {
/* Match an assignment under the form:
- "a = ... - c". */
- res = follow_ssa_edge
- (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
- evolution_of_loop);
- if (res)
+ "a = b - ...". */
+ res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
+ evolution_of_loop, limit);
+ if (res == t_true)
*evolution_of_loop = add_to_evolution
- (loop->num,
- chrec_fold_multiply (type_rhs,
- *evolution_of_loop,
- fold_convert (type_rhs, integer_minus_one_node)),
- PLUS_EXPR, rhs0);
+ (loop->num, chrec_convert (type_rhs, *evolution_of_loop, at_stmt),
+ MINUS_EXPR, rhs1, at_stmt);
+
+ else if (res == t_dont_know)
+ *evolution_of_loop = chrec_dont_know;
}
-
else
/* Otherwise, match an assignment under the form:
"a = ... - ...". */
/* And there is nothing to do. */
- res = false;
+ res = t_false;
break;
- case MULT_EXPR:
- /* This case is under the form "opnd0 = rhs0 * rhs1". */
- rhs0 = TREE_OPERAND (rhs, 0);
- rhs1 = TREE_OPERAND (rhs, 1);
- STRIP_TYPE_NOPS (rhs0);
- STRIP_TYPE_NOPS (rhs1);
+ case ASSERT_EXPR:
+ {
+ /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
+ It must be handled as a copy assignment of the form a_1 = a_2. */
+ tree op0 = ASSERT_EXPR_VAR (rhs);
+ if (TREE_CODE (op0) == SSA_NAME)
+ res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (op0),
+ halting_phi, evolution_of_loop, limit);
+ else
+ res = t_false;
+ break;
+ }
- if (TREE_CODE (rhs0) == SSA_NAME)
- {
- if (TREE_CODE (rhs1) == SSA_NAME)
- {
- /* Match an assignment under the form:
- "a = b * c". */
- res = follow_ssa_edge
- (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
- evolution_of_loop);
-
- if (res)
- *evolution_of_loop = chrec_dont_know;
-
- else
- {
- res = follow_ssa_edge
- (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
- evolution_of_loop);
-
- if (res)
- *evolution_of_loop = chrec_dont_know;
- }
- }
-
- else
- {
- /* Match an assignment under the form:
- "a = b * ...". */
- res = follow_ssa_edge
- (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
- evolution_of_loop);
- if (res)
- *evolution_of_loop = chrec_dont_know;
- }
- }
-
- else if (TREE_CODE (rhs1) == SSA_NAME)
- {
- /* Match an assignment under the form:
- "a = ... * c". */
- res = follow_ssa_edge
- (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
- evolution_of_loop);
- if (res)
- *evolution_of_loop = chrec_dont_know;
- }
-
- else
- /* Otherwise, match an assignment under the form:
- "a = ... * ...". */
- /* And there is nothing to do. */
- res = false;
-
- break;
default:
- res = false;
+ res = t_false;
break;
}
true if the strongly connected component has been found following
this path. */
-static inline bool
+static inline t_bool
follow_ssa_edge_in_condition_phi_branch (int i,
struct loop *loop,
tree condition_phi,
tree halting_phi,
tree *evolution_of_branch,
- tree init_cond)
+ tree init_cond, int limit)
{
tree branch = PHI_ARG_DEF (condition_phi, i);
*evolution_of_branch = chrec_dont_know;
/* Do not follow back edges (they must belong to an irreducible loop, which
we really do not want to worry about). */
if (backedge_phi_arg_p (condition_phi, i))
- return false;
+ return t_false;
if (TREE_CODE (branch) == SSA_NAME)
{
*evolution_of_branch = init_cond;
return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
- evolution_of_branch);
+ evolution_of_branch, limit);
}
/* This case occurs when one of the condition branches sets
- the variable to a constant: ie. a phi-node like
+ the variable to a constant: i.e. a phi-node like
"a_2 = PHI <a_7(5), 2(6)>;".
FIXME: This case have to be refined correctly:
in some cases it is possible to say something better than
chrec_dont_know, for example using a wrap-around notation. */
- return false;
+ return t_false;
}
/* This function merges the branches of a condition-phi-node in a
loop. */
-static bool
+static t_bool
follow_ssa_edge_in_condition_phi (struct loop *loop,
tree condition_phi,
tree halting_phi,
- tree *evolution_of_loop)
+ tree *evolution_of_loop, int limit)
{
int i;
tree init = *evolution_of_loop;
tree evolution_of_branch;
+ t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
+ halting_phi,
+ &evolution_of_branch,
+ init, limit);
+ if (res == t_false || res == t_dont_know)
+ return res;
- if (!follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
- halting_phi,
- &evolution_of_branch,
- init))
- return false;
*evolution_of_loop = evolution_of_branch;
for (i = 1; i < PHI_NUM_ARGS (condition_phi); i++)
{
- if (!follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
- halting_phi,
- &evolution_of_branch,
- init))
- return false;
+ /* Quickly give up when the evolution of one of the branches is
+ not known. */
+ if (*evolution_of_loop == chrec_dont_know)
+ return t_true;
+
+ res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
+ halting_phi,
+ &evolution_of_branch,
+ init, limit);
+ if (res == t_false || res == t_dont_know)
+ return res;
*evolution_of_loop = chrec_merge (*evolution_of_loop,
evolution_of_branch);
}
- return true;
+ return t_true;
}
/* Follow an SSA edge in an inner loop. It computes the overall
it follows the edges in the parent loop. The inner loop is
considered as a single statement. */
-static bool
+static t_bool
follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
tree loop_phi_node,
tree halting_phi,
- tree *evolution_of_loop)
+ tree *evolution_of_loop, int limit)
{
struct loop *loop = loop_containing_stmt (loop_phi_node);
tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
result of the analysis is a symbolic parameter. */
if (ev == PHI_RESULT (loop_phi_node))
{
- bool res = false;
+ t_bool res = t_false;
int i;
for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
/* Follow the edges that exit the inner loop. */
bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
if (!flow_bb_inside_loop_p (loop, bb))
- res = res || follow_ssa_edge_in_rhs (outer_loop, arg, halting_phi,
- evolution_of_loop);
+ res = follow_ssa_edge_in_rhs (outer_loop, loop_phi_node,
+ arg, halting_phi,
+ evolution_of_loop, limit);
+ if (res == t_true)
+ break;
}
/* If the path crosses this loop-phi, give up. */
- if (res == true)
+ if (res == t_true)
*evolution_of_loop = chrec_dont_know;
return res;
/* Otherwise, compute the overall effect of the inner loop. */
ev = compute_overall_effect_of_inner_loop (loop, ev);
- return follow_ssa_edge_in_rhs (outer_loop, ev, halting_phi,
- evolution_of_loop);
+ return follow_ssa_edge_in_rhs (outer_loop, loop_phi_node, ev, halting_phi,
+ evolution_of_loop, limit);
}
/* Follow an SSA edge from a loop-phi-node to itself, constructing a
path that is analyzed on the return walk. */
-static bool
-follow_ssa_edge (struct loop *loop,
- tree def,
- tree halting_phi,
- tree *evolution_of_loop)
+static t_bool
+follow_ssa_edge (struct loop *loop, tree def, tree halting_phi,
+ tree *evolution_of_loop, int limit)
{
struct loop *def_loop;
if (TREE_CODE (def) == NOP_EXPR)
- return false;
+ return t_false;
+
+ /* Give up if the path is longer than the MAX that we allow. */
+ if (limit++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
+ return t_dont_know;
def_loop = loop_containing_stmt (def);
information and set the approximation to the main
variable. */
return follow_ssa_edge_in_condition_phi
- (loop, def, halting_phi, evolution_of_loop);
+ (loop, def, halting_phi, evolution_of_loop, limit);
/* When the analyzed phi is the halting_phi, the
depth-first search is over: we have found a path from
the halting_phi to itself in the loop. */
if (def == halting_phi)
- return true;
+ return t_true;
/* Otherwise, the evolution of the HALTING_PHI depends
- on the evolution of another loop-phi-node, ie. the
+ on the evolution of another loop-phi-node, i.e. the
evolution function is a higher degree polynomial. */
if (def_loop == loop)
- return false;
+ return t_false;
/* Inner loop. */
if (flow_loop_nested_p (loop, def_loop))
return follow_ssa_edge_inner_loop_phi
- (loop, def, halting_phi, evolution_of_loop);
+ (loop, def, halting_phi, evolution_of_loop, limit);
/* Outer loop. */
- return false;
+ return t_false;
- case MODIFY_EXPR:
- return follow_ssa_edge_in_rhs (loop,
- TREE_OPERAND (def, 1),
+ case GIMPLE_MODIFY_STMT:
+ return follow_ssa_edge_in_rhs (loop, def,
+ GIMPLE_STMT_OPERAND (def, 1),
halting_phi,
- evolution_of_loop);
+ evolution_of_loop, limit);
default:
/* At this level of abstraction, the program is just a set
- of MODIFY_EXPRs and PHI_NODEs. In principle there is no
+ of GIMPLE_MODIFY_STMTs and PHI_NODEs. In principle there is no
other node to be handled. */
- return false;
+ return t_false;
}
}
{
tree arg = PHI_ARG_DEF (loop_phi_node, i);
tree ssa_chain, ev_fn;
- bool res;
+ t_bool res;
/* Select the edges that enter the loop body. */
bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
/* Pass in the initial condition to the follow edge function. */
ev_fn = init_cond;
- res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn);
+ res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, 0);
}
else
- res = false;
+ res = t_false;
/* When it is impossible to go back on the same
loop_phi_node by following the ssa edges, the
- evolution is represented by a peeled chrec, ie. the
+ evolution is represented by a peeled chrec, i.e. the
first iteration, EV_FN has the value INIT_COND, then
all the other iterations it has the value of ARG.
For the moment, PEELED_CHREC nodes are not built. */
- if (!res)
+ if (res != t_true)
ev_fn = chrec_dont_know;
/* When there are multiple back edges of the loop (which in fact never
- happens currently, but nevertheless), merge their evolutions. */
+ happens currently, but nevertheless), merge their evolutions. */
evolution_function = chrec_merge (evolution_function, ev_fn);
}
(phi_loop, PHI_RESULT (loop_phi_node));
/* Dive one level deeper. */
- subloop = superloop_at_depth (phi_loop, loop->depth + 1);
+ subloop = superloop_at_depth (phi_loop, loop_depth (loop) + 1);
/* Interpret the subloop. */
res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
return res;
}
-/* Interpret the right hand side of a modify_expr OPND1. If we didn't
- analyzed this node before, follow the definitions until ending
- either on an analyzed modify_expr, or on a loop-phi-node. On the
+/* Interpret the right hand side of a GIMPLE_MODIFY_STMT OPND1. If we didn't
+ analyze this node before, follow the definitions until ending
+ either on an analyzed GIMPLE_MODIFY_STMT, or on a loop-phi-node. On the
return path, this function propagates evolutions (ala constant copy
propagation). OPND1 is not a GIMPLE expression because we could
analyze the effect of an inner loop: see interpret_loop_phi. */
static tree
-interpret_rhs_modify_expr (struct loop *loop,
- tree opnd1, tree type)
+interpret_rhs_modify_stmt (struct loop *loop, tree at_stmt,
+ tree opnd1, tree type)
{
tree res, opnd10, opnd11, chrec10, chrec11;
-
+
if (is_gimple_min_invariant (opnd1))
- return chrec_convert (type, opnd1);
-
+ return chrec_convert (type, opnd1, at_stmt);
+
switch (TREE_CODE (opnd1))
{
case PLUS_EXPR:
opnd11 = TREE_OPERAND (opnd1, 1);
chrec10 = analyze_scalar_evolution (loop, opnd10);
chrec11 = analyze_scalar_evolution (loop, opnd11);
- chrec10 = chrec_convert (type, chrec10);
- chrec11 = chrec_convert (type, chrec11);
+ chrec10 = chrec_convert (type, chrec10, at_stmt);
+ chrec11 = chrec_convert (type, chrec11, at_stmt);
res = chrec_fold_plus (type, chrec10, chrec11);
break;
opnd11 = TREE_OPERAND (opnd1, 1);
chrec10 = analyze_scalar_evolution (loop, opnd10);
chrec11 = analyze_scalar_evolution (loop, opnd11);
- chrec10 = chrec_convert (type, chrec10);
- chrec11 = chrec_convert (type, chrec11);
+ chrec10 = chrec_convert (type, chrec10, at_stmt);
+ chrec11 = chrec_convert (type, chrec11, at_stmt);
res = chrec_fold_minus (type, chrec10, chrec11);
break;
case NEGATE_EXPR:
opnd10 = TREE_OPERAND (opnd1, 0);
chrec10 = analyze_scalar_evolution (loop, opnd10);
- chrec10 = chrec_convert (type, chrec10);
- res = chrec_fold_minus (type, fold_convert (type, integer_zero_node),
- chrec10);
+ chrec10 = chrec_convert (type, chrec10, at_stmt);
+ /* TYPE may be integer, real or complex, so use fold_convert. */
+ res = chrec_fold_multiply (type, chrec10,
+ fold_convert (type, integer_minus_one_node));
break;
case MULT_EXPR:
opnd11 = TREE_OPERAND (opnd1, 1);
chrec10 = analyze_scalar_evolution (loop, opnd10);
chrec11 = analyze_scalar_evolution (loop, opnd11);
- chrec10 = chrec_convert (type, chrec10);
- chrec11 = chrec_convert (type, chrec11);
+ chrec10 = chrec_convert (type, chrec10, at_stmt);
+ chrec11 = chrec_convert (type, chrec11, at_stmt);
res = chrec_fold_multiply (type, chrec10, chrec11);
break;
case SSA_NAME:
- res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1));
+ res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1),
+ at_stmt);
+ break;
+
+ case ASSERT_EXPR:
+ opnd10 = ASSERT_EXPR_VAR (opnd1);
+ res = chrec_convert (type, analyze_scalar_evolution (loop, opnd10),
+ at_stmt);
break;
case NOP_EXPR:
case CONVERT_EXPR:
opnd10 = TREE_OPERAND (opnd1, 0);
chrec10 = analyze_scalar_evolution (loop, opnd10);
- res = chrec_convert (type, chrec10);
+ res = chrec_convert (type, chrec10, at_stmt);
break;
default:
if (def_loop == wrto_loop)
return ev;
- def_loop = superloop_at_depth (def_loop, wrto_loop->depth + 1);
+ def_loop = superloop_at_depth (def_loop, loop_depth (wrto_loop) + 1);
res = compute_overall_effect_of_inner_loop (def_loop, ev);
return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
}
+/* Folds EXPR, if it is a cast to pointer, assuming that the created
+ polynomial_chrec does not wrap. */
+
+static tree
+fold_used_pointer_cast (tree expr)
+{
+ tree op;
+ tree type, inner_type;
+
+ if (TREE_CODE (expr) != NOP_EXPR && TREE_CODE (expr) != CONVERT_EXPR)
+ return expr;
+
+ op = TREE_OPERAND (expr, 0);
+ if (TREE_CODE (op) != POLYNOMIAL_CHREC)
+ return expr;
+
+ type = TREE_TYPE (expr);
+ inner_type = TREE_TYPE (op);
+
+ if (!INTEGRAL_TYPE_P (inner_type)
+ || TYPE_PRECISION (inner_type) != TYPE_PRECISION (type))
+ return expr;
+
+ return build_polynomial_chrec (CHREC_VARIABLE (op),
+ chrec_convert (type, CHREC_LEFT (op), NULL_TREE),
+ chrec_convert (type, CHREC_RIGHT (op), NULL_TREE));
+}
+
+/* Returns true if EXPR is an expression corresponding to offset of pointer
+ in p + offset. */
+
+static bool
+pointer_offset_p (tree expr)
+{
+ if (TREE_CODE (expr) == INTEGER_CST)
+ return true;
+
+ if ((TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR)
+ && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0))))
+ return true;
+
+ return false;
+}
+
+/* EXPR is a scalar evolution of a pointer that is dereferenced or used in
+ comparison. This means that it must point to a part of some object in
+ memory, which enables us to argue about overflows and possibly simplify
+ the EXPR. AT_STMT is the statement in which this conversion has to be
+ performed. Returns the simplified value.
+
+ Currently, for
+
+ int i, n;
+ int *p;
+
+ for (i = -n; i < n; i++)
+ *(p + i) = ...;
+
+ We generate the following code (assuming that size of int and size_t is
+ 4 bytes):
+
+ for (i = -n; i < n; i++)
+ {
+ size_t tmp1, tmp2;
+ int *tmp3, *tmp4;
+
+ tmp1 = (size_t) i; (1)
+ tmp2 = 4 * tmp1; (2)
+ tmp3 = (int *) tmp2; (3)
+ tmp4 = p + tmp3; (4)
+
+ *tmp4 = ...;
+ }
+
+ We in general assume that pointer arithmetics does not overflow (since its
+ behavior is undefined in that case). One of the problems is that our
+ translation does not capture this property very well -- (int *) is
+ considered unsigned, hence the computation in (4) does overflow if i is
+ negative.
+
+ This impreciseness creates complications in scev analysis. The scalar
+ evolution of i is [-n, +, 1]. Since int and size_t have the same precision
+ (in this example), and size_t is unsigned (so we do not care about
+ overflows), we succeed to derive that scev of tmp1 is [(size_t) -n, +, 1]
+ and scev of tmp2 is [4 * (size_t) -n, +, 4]. With tmp3, we run into
+ problem -- [(int *) (4 * (size_t) -n), +, 4] wraps, and since we on several
+ places assume that this is not the case for scevs with pointer type, we
+ cannot use this scev for tmp3; hence, its scev is
+ (int *) [(4 * (size_t) -n), +, 4], and scev of tmp4 is
+ p + (int *) [(4 * (size_t) -n), +, 4]. Most of the optimizers are unable to
+ work with scevs of this shape.
+
+ However, since tmp4 is dereferenced, all its values must belong to a single
+ object, and taking into account that the precision of int * and size_t is
+ the same, it is impossible for its scev to wrap. Hence, we can derive that
+ its evolution is [p + (int *) (4 * (size_t) -n), +, 4], which the optimizers
+ can work with.
+
+ ??? Maybe we should use different representation for pointer arithmetics,
+ however that is a long-term project with a lot of potential for creating
+ bugs. */
+
+static tree
+fold_used_pointer (tree expr, tree at_stmt)
+{
+ tree op0, op1, new0, new1;
+ enum tree_code code = TREE_CODE (expr);
+
+ if (code == PLUS_EXPR
+ || code == MINUS_EXPR)
+ {
+ op0 = TREE_OPERAND (expr, 0);
+ op1 = TREE_OPERAND (expr, 1);
+
+ if (pointer_offset_p (op1))
+ {
+ new0 = fold_used_pointer (op0, at_stmt);
+ new1 = fold_used_pointer_cast (op1);
+ }
+ else if (code == PLUS_EXPR && pointer_offset_p (op0))
+ {
+ new0 = fold_used_pointer_cast (op0);
+ new1 = fold_used_pointer (op1, at_stmt);
+ }
+ else
+ return expr;
+
+ if (new0 == op0 && new1 == op1)
+ return expr;
+
+ new0 = chrec_convert (TREE_TYPE (expr), new0, at_stmt);
+ new1 = chrec_convert (TREE_TYPE (expr), new1, at_stmt);
+
+ if (code == PLUS_EXPR)
+ expr = chrec_fold_plus (TREE_TYPE (expr), new0, new1);
+ else
+ expr = chrec_fold_minus (TREE_TYPE (expr), new0, new1);
+
+ return expr;
+ }
+ else
+ return fold_used_pointer_cast (expr);
+}
+
+/* Returns true if PTR is dereferenced, or used in comparison. */
+
+static bool
+pointer_used_p (tree ptr)
+{
+ use_operand_p use_p;
+ imm_use_iterator imm_iter;
+ tree stmt, rhs;
+ struct ptr_info_def *pi = get_ptr_info (ptr);
+
+ /* Check whether the pointer has a memory tag; if it does, it is
+ (or at least used to be) dereferenced. */
+ if ((pi != NULL && pi->name_mem_tag != NULL)
+ || symbol_mem_tag (SSA_NAME_VAR (ptr)))
+ return true;
+
+ FOR_EACH_IMM_USE_FAST (use_p, imm_iter, ptr)
+ {
+ stmt = USE_STMT (use_p);
+ if (TREE_CODE (stmt) == COND_EXPR)
+ return true;
+
+ if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
+ continue;
+
+ rhs = GIMPLE_STMT_OPERAND (stmt, 1);
+ if (!COMPARISON_CLASS_P (rhs))
+ continue;
+
+ if (GIMPLE_STMT_OPERAND (stmt, 0) == ptr
+ || GIMPLE_STMT_OPERAND (stmt, 1) == ptr)
+ return true;
+ }
+
+ return false;
+}
+
/* Helper recursive function. */
static tree
basic_block bb;
struct loop *def_loop;
- if (loop == NULL)
+ if (loop == NULL || TREE_CODE (type) == VECTOR_TYPE)
return chrec_dont_know;
if (TREE_CODE (var) != SSA_NAME)
- return interpret_rhs_modify_expr (loop, var, type);
+ return interpret_rhs_modify_stmt (loop, NULL_TREE, var, type);
def = SSA_NAME_DEF_STMT (var);
bb = bb_for_stmt (def);
switch (TREE_CODE (def))
{
- case MODIFY_EXPR:
- res = interpret_rhs_modify_expr (loop, TREE_OPERAND (def, 1), type);
+ case GIMPLE_MODIFY_STMT:
+ res = interpret_rhs_modify_stmt (loop, def,
+ GIMPLE_STMT_OPERAND (def, 1), type);
+
+ if (POINTER_TYPE_P (type)
+ && !automatically_generated_chrec_p (res)
+ && pointer_used_p (var))
+ res = fold_used_pointer (res, def);
break;
case PHI_NODE:
/* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
WRTO_LOOP (which should be a superloop of both USE_LOOP and definition
- of VERSION). */
+ of VERSION).
+
+ FOLDED_CASTS is set to true if resolve_mixers used
+ chrec_convert_aggressive (TODO -- not really, we are way too conservative
+ at the moment in order to keep things simple). */
static tree
analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
- tree version)
+ tree version, bool *folded_casts)
{
bool val = false;
- tree ev = version;
+ tree ev = version, tmp;
+ if (folded_casts)
+ *folded_casts = false;
while (1)
{
- ev = analyze_scalar_evolution (use_loop, ev);
- ev = resolve_mixers (use_loop, ev);
+ tmp = analyze_scalar_evolution (use_loop, ev);
+ ev = resolve_mixers (use_loop, tmp);
+
+ if (folded_casts && tmp != ev)
+ *folded_casts = true;
if (use_loop == wrto_loop)
return ev;
|| !val)
return chrec_dont_know;
- use_loop = use_loop->outer;
+ use_loop = loop_outer (use_loop);
}
}
+/* Returns instantiated value for VERSION in CACHE. */
+
+static tree
+get_instantiated_value (htab_t cache, tree version)
+{
+ struct scev_info_str *info, pattern;
+
+ pattern.var = version;
+ info = (struct scev_info_str *) htab_find (cache, &pattern);
+
+ if (info)
+ return info->chrec;
+ else
+ return NULL_TREE;
+}
+
+/* Sets instantiated value for VERSION to VAL in CACHE. */
+
+static void
+set_instantiated_value (htab_t cache, tree version, tree val)
+{
+ struct scev_info_str *info, pattern;
+ PTR *slot;
+
+ pattern.var = version;
+ slot = htab_find_slot (cache, &pattern, INSERT);
+
+ if (!*slot)
+ *slot = new_scev_info_str (version);
+ info = (struct scev_info_str *) *slot;
+ info->chrec = val;
+}
+
+/* Return the closed_loop_phi node for VAR. If there is none, return
+ NULL_TREE. */
+
+static tree
+loop_closed_phi_def (tree var)
+{
+ struct loop *loop;
+ edge exit;
+ tree phi;
+
+ if (var == NULL_TREE
+ || TREE_CODE (var) != SSA_NAME)
+ return NULL_TREE;
+
+ loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
+ exit = single_exit (loop);
+ if (!exit)
+ return NULL_TREE;
+
+ for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
+ if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
+ return PHI_RESULT (phi);
+
+ return NULL_TREE;
+}
+
/* Analyze all the parameters of the chrec that were left under a symbolic form,
- with respect to LOOP. CHREC is the chrec to instantiate. If
- ALLOW_SUPERLOOP_CHRECS is true, replacing loop invariants with
- outer loop chrecs is done. */
+ with respect to LOOP. CHREC is the chrec to instantiate. CACHE is the cache
+ of already instantiated values. FLAGS modify the way chrecs are
+ instantiated. SIZE_EXPR is used for computing the size of the expression to
+ be instantiated, and to stop if it exceeds some limit. */
+/* Values for FLAGS. */
+enum
+{
+ INSERT_SUPERLOOP_CHRECS = 1, /* Loop invariants are replaced with chrecs
+ in outer loops. */
+ FOLD_CONVERSIONS = 2 /* The conversions that may wrap in
+ signed/pointer type are folded, as long as the
+ value of the chrec is preserved. */
+};
+
static tree
-instantiate_parameters_1 (struct loop *loop, tree chrec,
- bool allow_superloop_chrecs)
+instantiate_parameters_1 (struct loop *loop, tree chrec, int flags, htab_t cache,
+ int size_expr)
{
tree res, op0, op1, op2;
basic_block def_bb;
struct loop *def_loop;
-
- if (chrec == NULL_TREE
- || automatically_generated_chrec_p (chrec))
- return chrec;
-
- if (is_gimple_min_invariant (chrec))
+ tree type = chrec_type (chrec);
+
+ /* Give up if the expression is larger than the MAX that we allow. */
+ if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
+ return chrec_dont_know;
+
+ if (automatically_generated_chrec_p (chrec)
+ || is_gimple_min_invariant (chrec))
return chrec;
switch (TREE_CODE (chrec))
/* A parameter (or loop invariant and we do not want to include
evolutions in outer loops), nothing to do. */
if (!def_bb
- || (!allow_superloop_chrecs
+ || (!(flags & INSERT_SUPERLOOP_CHRECS)
&& !flow_bb_inside_loop_p (loop, def_bb)))
return chrec;
- /* Don't instantiate the SSA_NAME if it is in a mixer
+ /* We cache the value of instantiated variable to avoid exponential
+ time complexity due to reevaluations. We also store the convenient
+ value in the cache in order to prevent infinite recursion -- we do
+ not want to instantiate the SSA_NAME if it is in a mixer
structure. This is used for avoiding the instantiation of
recursively defined functions, such as:
| a_2 -> {0, +, 1, +, a_2}_1 */
-
+
+ res = get_instantiated_value (cache, chrec);
+ if (res)
+ return res;
+
+ /* Store the convenient value for chrec in the structure. If it
+ is defined outside of the loop, we may just leave it in symbolic
+ form, otherwise we need to admit that we do not know its behavior
+ inside the loop. */
+ res = !flow_bb_inside_loop_p (loop, def_bb) ? chrec : chrec_dont_know;
+ set_instantiated_value (cache, chrec, res);
+
+ /* To make things even more complicated, instantiate_parameters_1
+ calls analyze_scalar_evolution that may call # of iterations
+ analysis that may in turn call instantiate_parameters_1 again.
+ To prevent the infinite recursion, keep also the bitmap of
+ ssa names that are being instantiated globally. */
if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec)))
- {
- if (!flow_bb_inside_loop_p (loop, def_bb))
- {
- /* We may keep the loop invariant in symbolic form. */
- return chrec;
- }
- else
- {
- /* Something with unknown behavior in LOOP. */
- return chrec_dont_know;
- }
- }
+ return res;
def_loop = find_common_loop (loop, def_bb->loop_father);
/* If the analysis yields a parametric chrec, instantiate the
- result again. Avoid the cyclic instantiation in mixers. */
+ result again. */
bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec));
res = analyze_scalar_evolution (def_loop, chrec);
- res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs);
+
+ /* Don't instantiate loop-closed-ssa phi nodes. */
+ if (TREE_CODE (res) == SSA_NAME
+ && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL
+ || (loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
+ > loop_depth (def_loop))))
+ {
+ if (res == chrec)
+ res = loop_closed_phi_def (chrec);
+ else
+ res = chrec;
+
+ if (res == NULL_TREE)
+ res = chrec_dont_know;
+ }
+
+ else if (res != chrec_dont_know)
+ res = instantiate_parameters_1 (loop, res, flags, cache, size_expr);
+
bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
+
+ /* Store the correct value to the cache. */
+ set_instantiated_value (cache, chrec, res);
return res;
case POLYNOMIAL_CHREC:
op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
- allow_superloop_chrecs);
+ flags, cache, size_expr);
+ if (op0 == chrec_dont_know)
+ return chrec_dont_know;
+
op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
- allow_superloop_chrecs);
- return build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
+ flags, cache, size_expr);
+ if (op1 == chrec_dont_know)
+ return chrec_dont_know;
+
+ if (CHREC_LEFT (chrec) != op0
+ || CHREC_RIGHT (chrec) != op1)
+ {
+ op1 = chrec_convert (chrec_type (op0), op1, NULL_TREE);
+ chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
+ }
+ return chrec;
case PLUS_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
- allow_superloop_chrecs);
+ flags, cache, size_expr);
+ if (op0 == chrec_dont_know)
+ return chrec_dont_know;
+
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
- allow_superloop_chrecs);
- return chrec_fold_plus (TREE_TYPE (chrec), op0, op1);
+ flags, cache, size_expr);
+ if (op1 == chrec_dont_know)
+ return chrec_dont_know;
+
+ if (TREE_OPERAND (chrec, 0) != op0
+ || TREE_OPERAND (chrec, 1) != op1)
+ {
+ op0 = chrec_convert (type, op0, NULL_TREE);
+ op1 = chrec_convert (type, op1, NULL_TREE);
+ chrec = chrec_fold_plus (type, op0, op1);
+ }
+ return chrec;
case MINUS_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
- allow_superloop_chrecs);
+ flags, cache, size_expr);
+ if (op0 == chrec_dont_know)
+ return chrec_dont_know;
+
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
- allow_superloop_chrecs);
- return chrec_fold_minus (TREE_TYPE (chrec), op0, op1);
+ flags, cache, size_expr);
+ if (op1 == chrec_dont_know)
+ return chrec_dont_know;
+
+ if (TREE_OPERAND (chrec, 0) != op0
+ || TREE_OPERAND (chrec, 1) != op1)
+ {
+ op0 = chrec_convert (type, op0, NULL_TREE);
+ op1 = chrec_convert (type, op1, NULL_TREE);
+ chrec = chrec_fold_minus (type, op0, op1);
+ }
+ return chrec;
case MULT_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
- allow_superloop_chrecs);
+ flags, cache, size_expr);
+ if (op0 == chrec_dont_know)
+ return chrec_dont_know;
+
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
- allow_superloop_chrecs);
- return chrec_fold_multiply (TREE_TYPE (chrec), op0, op1);
+ flags, cache, size_expr);
+ if (op1 == chrec_dont_know)
+ return chrec_dont_know;
+
+ if (TREE_OPERAND (chrec, 0) != op0
+ || TREE_OPERAND (chrec, 1) != op1)
+ {
+ op0 = chrec_convert (type, op0, NULL_TREE);
+ op1 = chrec_convert (type, op1, NULL_TREE);
+ chrec = chrec_fold_multiply (type, op0, op1);
+ }
+ return chrec;
case NOP_EXPR:
case CONVERT_EXPR:
case NON_LVALUE_EXPR:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
- allow_superloop_chrecs);
+ flags, cache, size_expr);
if (op0 == chrec_dont_know)
return chrec_dont_know;
- return chrec_convert (TREE_TYPE (chrec), op0);
+ if (flags & FOLD_CONVERSIONS)
+ {
+ tree tmp = chrec_convert_aggressive (TREE_TYPE (chrec), op0);
+ if (tmp)
+ return tmp;
+ }
+
+ if (op0 == TREE_OPERAND (chrec, 0))
+ return chrec;
+
+ /* If we used chrec_convert_aggressive, we can no longer assume that
+ signed chrecs do not overflow, as chrec_convert does, so avoid
+ calling it in that case. */
+ if (flags & FOLD_CONVERSIONS)
+ return fold_convert (TREE_TYPE (chrec), op0);
+
+ return chrec_convert (TREE_TYPE (chrec), op0, NULL_TREE);
case SCEV_NOT_KNOWN:
return chrec_dont_know;
break;
}
+ gcc_assert (!VL_EXP_CLASS_P (chrec));
switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
{
case 3:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
- allow_superloop_chrecs);
+ flags, cache, size_expr);
+ if (op0 == chrec_dont_know)
+ return chrec_dont_know;
+
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
- allow_superloop_chrecs);
+ flags, cache, size_expr);
+ if (op1 == chrec_dont_know)
+ return chrec_dont_know;
+
op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2),
- allow_superloop_chrecs);
- if (op0 == chrec_dont_know
- || op1 == chrec_dont_know
- || op2 == chrec_dont_know)
+ flags, cache, size_expr);
+ if (op2 == chrec_dont_know)
return chrec_dont_know;
- return fold (build (TREE_CODE (chrec),
- TREE_TYPE (chrec), op0, op1, op2));
+
+ if (op0 == TREE_OPERAND (chrec, 0)
+ && op1 == TREE_OPERAND (chrec, 1)
+ && op2 == TREE_OPERAND (chrec, 2))
+ return chrec;
+
+ return fold_build3 (TREE_CODE (chrec),
+ TREE_TYPE (chrec), op0, op1, op2);
case 2:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
- allow_superloop_chrecs);
+ flags, cache, size_expr);
+ if (op0 == chrec_dont_know)
+ return chrec_dont_know;
+
op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
- allow_superloop_chrecs);
- if (op0 == chrec_dont_know
- || op1 == chrec_dont_know)
+ flags, cache, size_expr);
+ if (op1 == chrec_dont_know)
return chrec_dont_know;
- return fold (build (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1));
+
+ if (op0 == TREE_OPERAND (chrec, 0)
+ && op1 == TREE_OPERAND (chrec, 1))
+ return chrec;
+ return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
case 1:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
- allow_superloop_chrecs);
+ flags, cache, size_expr);
if (op0 == chrec_dont_know)
return chrec_dont_know;
- return fold (build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0));
+ if (op0 == TREE_OPERAND (chrec, 0))
+ return chrec;
+ return fold_build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0);
case 0:
return chrec;
tree chrec)
{
tree res;
+ htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, ")\n");
}
- res = instantiate_parameters_1 (loop, chrec, true);
+ res = instantiate_parameters_1 (loop, chrec, INSERT_SUPERLOOP_CHRECS, cache,
+ 0);
if (dump_file && (dump_flags & TDF_DETAILS))
{
print_generic_expr (dump_file, res, 0);
fprintf (dump_file, "))\n");
}
+
+ htab_delete (cache);
return res;
}
/* Similar to instantiate_parameters, but does not introduce the
- evolutions in outer loops for LOOP invariants in CHREC. */
+ evolutions in outer loops for LOOP invariants in CHREC, and does not
+ care about causing overflows, as long as they do not affect value
+ of an expression. */
-static tree
+tree
resolve_mixers (struct loop *loop, tree chrec)
{
- return instantiate_parameters_1 (loop, chrec, false);
+ htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
+ tree ret = instantiate_parameters_1 (loop, chrec, FOLD_CONVERSIONS, cache, 0);
+ htab_delete (cache);
+ return ret;
}
/* Entry point for the analysis of the number of iterations pass.
the loop body has been executed 6 times. */
tree
-number_of_iterations_in_loop (struct loop *loop)
+number_of_latch_executions (struct loop *loop)
{
tree res, type;
edge exit;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(number_of_iterations_in_loop\n");
- if (!loop->exit_edges)
+ exit = single_exit (loop);
+ if (!exit)
goto end;
- exit = loop->exit_edges[0];
- if (!number_of_iterations_exit (loop, exit, &niter_desc))
+ if (!number_of_iterations_exit (loop, exit, &niter_desc, false))
goto end;
type = TREE_TYPE (niter_desc.niter);
if (integer_nonzerop (niter_desc.may_be_zero))
- res = fold_convert (type, integer_zero_node);
+ res = build_int_cst (type, 0);
else if (integer_zerop (niter_desc.may_be_zero))
res = niter_desc.niter;
else
return set_nb_iterations_in_loop (loop, res);
}
+/* Returns the number of executions of the exit condition of LOOP,
+ i.e., the number by one higher than number_of_latch_executions.
+ Note that unline number_of_latch_executions, this number does
+ not necessarily fit in the unsigned variant of the type of
+ the control variable -- if the number of iterations is a constant,
+ we return chrec_dont_know if adding one to number_of_latch_executions
+ overflows; however, in case the number of iterations is symbolic
+ expression, the caller is responsible for dealing with this
+ the possible overflow. */
+
+tree
+number_of_exit_cond_executions (struct loop *loop)
+{
+ tree ret = number_of_latch_executions (loop);
+ tree type = chrec_type (ret);
+
+ if (chrec_contains_undetermined (ret))
+ return ret;
+
+ ret = chrec_fold_plus (type, ret, build_int_cst (type, 1));
+ if (TREE_CODE (ret) == INTEGER_CST
+ && TREE_OVERFLOW (ret))
+ return chrec_dont_know;
+
+ return ret;
+}
+
/* One of the drivers for testing the scalar evolutions analysis.
This function computes the number of iterations for all the loops
from the EXIT_CONDITIONS array. */
static void
-number_of_iterations_for_all_loops (varray_type exit_conditions)
+number_of_iterations_for_all_loops (VEC(tree,heap) **exit_conditions)
{
unsigned int i;
unsigned nb_chrec_dont_know_loops = 0;
unsigned nb_static_loops = 0;
+ tree cond;
- for (i = 0; i < VARRAY_ACTIVE_SIZE (exit_conditions); i++)
+ for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
{
- tree res = number_of_iterations_in_loop
- (loop_containing_stmt (VARRAY_TREE (exit_conditions, i)));
+ tree res = number_of_latch_executions (loop_containing_stmt (cond));
if (chrec_contains_undetermined (res))
nb_chrec_dont_know_loops++;
else
fprintf (dump_file, "-----------------------------------------\n");
fprintf (dump_file, "%d\tnb_chrec_dont_know_loops\n", nb_chrec_dont_know_loops);
fprintf (dump_file, "%d\tnb_static_loops\n", nb_static_loops);
- fprintf (dump_file, "%d\tnb_total_loops\n", current_loops->num);
+ fprintf (dump_file, "%d\tnb_total_loops\n", number_of_loops ());
fprintf (dump_file, "-----------------------------------------\n");
fprintf (dump_file, ")\n\n");
fprintf (dump_file, " affine_univariate\n");
stats->nb_affine++;
}
- else if (evolution_function_is_affine_multivariate_p (chrec))
+ else if (evolution_function_is_affine_multivariate_p (chrec, 0))
{
if (dump_file && (dump_flags & TDF_STATS))
fprintf (dump_file, " affine_multivariate\n");
index. This allows the parallelization of the loop. */
static void
-analyze_scalar_evolution_for_all_loop_phi_nodes (varray_type exit_conditions)
+analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree,heap) **exit_conditions)
{
unsigned int i;
struct chrec_stats stats;
+ tree cond;
reset_chrecs_counters (&stats);
- for (i = 0; i < VARRAY_ACTIVE_SIZE (exit_conditions); i++)
+ for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
{
struct loop *loop;
basic_block bb;
tree phi, chrec;
- loop = loop_containing_stmt (VARRAY_TREE (exit_conditions, i));
+ loop = loop_containing_stmt (cond);
bb = loop->header;
- for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
if (is_gimple_reg (PHI_RESULT (phi)))
{
chrec = instantiate_parameters
static int
gather_stats_on_scev_database_1 (void **slot, void *stats)
{
- struct scev_info_str *entry = *slot;
+ struct scev_info_str *entry = (struct scev_info_str *) *slot;
- gather_chrec_stats (entry->chrec, stats);
+ gather_chrec_stats (entry->chrec, (struct chrec_stats *) stats);
return 1;
}
chrec_not_analyzed_yet = NULL_TREE;
chrec_dont_know = make_node (SCEV_NOT_KNOWN);
chrec_known = make_node (SCEV_KNOWN);
- TREE_TYPE (chrec_dont_know) = NULL_TREE;
- TREE_TYPE (chrec_known) = NULL_TREE;
+ TREE_TYPE (chrec_dont_know) = void_type_node;
+ TREE_TYPE (chrec_known) = void_type_node;
}
}
/* Initialize the analysis of scalar evolutions for LOOPS. */
void
-scev_initialize (struct loops *loops)
+scev_initialize (void)
{
- unsigned i;
- current_loops = loops;
+ loop_iterator li;
+ struct loop *loop;
- scalar_evolution_info = htab_create (100, hash_scev_info,
- eq_scev_info, del_scev_info);
- already_instantiated = BITMAP_XMALLOC ();
+ scalar_evolution_info = htab_create_alloc (100,
+ hash_scev_info,
+ eq_scev_info,
+ del_scev_info,
+ ggc_calloc,
+ ggc_free);
+ already_instantiated = BITMAP_ALLOC (NULL);
initialize_scalar_evolutions_analyzer ();
- for (i = 1; i < loops->num; i++)
- if (loops->parray[i])
- {
- flow_loop_scan (loops->parray[i], LOOP_EXIT_EDGES);
- loops->parray[i]->nb_iterations = NULL_TREE;
- }
+ FOR_EACH_LOOP (li, loop, 0)
+ {
+ loop->nb_iterations = NULL_TREE;
+ }
}
/* Cleans up the information cached by the scalar evolutions analysis. */
void
scev_reset (void)
{
- unsigned i;
+ loop_iterator li;
struct loop *loop;
if (!scalar_evolution_info || !current_loops)
return;
htab_empty (scalar_evolution_info);
- for (i = 1; i < current_loops->num; i++)
+ FOR_EACH_LOOP (li, loop, 0)
{
- loop = current_loops->parray[i];
- if (loop)
- loop->nb_iterations = NULL_TREE;
+ loop->nb_iterations = NULL_TREE;
}
}
/* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
- its BASE and STEP if possible. */
+ its base and step in IV if possible. If ALLOW_NONCONSTANT_STEP is true, we
+ want step to be invariant in LOOP. Otherwise we require it to be an
+ integer constant. IV->no_overflow is set to true if we are sure the iv cannot
+ overflow (e.g. because it is computed in signed arithmetics). */
bool
-simple_iv (struct loop *loop, tree stmt, tree op, tree *base, tree *step)
+simple_iv (struct loop *loop, tree stmt, tree op, affine_iv *iv,
+ bool allow_nonconstant_step)
{
basic_block bb = bb_for_stmt (stmt);
tree type, ev;
+ bool folded_casts;
- *base = NULL_TREE;
- *step = NULL_TREE;
+ iv->base = NULL_TREE;
+ iv->step = NULL_TREE;
+ iv->no_overflow = false;
type = TREE_TYPE (op);
if (TREE_CODE (type) != INTEGER_TYPE
&& TREE_CODE (type) != POINTER_TYPE)
return false;
- ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op);
+ ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op,
+ &folded_casts);
if (chrec_contains_undetermined (ev))
return false;
if (tree_does_not_contain_chrecs (ev)
&& !chrec_contains_symbols_defined_in_loop (ev, loop->num))
{
- *base = ev;
+ iv->base = ev;
+ iv->step = build_int_cst (TREE_TYPE (ev), 0);
+ iv->no_overflow = true;
return true;
}
|| CHREC_VARIABLE (ev) != (unsigned) loop->num)
return false;
- *step = CHREC_RIGHT (ev);
- if (TREE_CODE (*step) != INTEGER_CST)
+ iv->step = CHREC_RIGHT (ev);
+ if (allow_nonconstant_step)
+ {
+ if (tree_contains_chrecs (iv->step, NULL)
+ || chrec_contains_symbols_defined_in_loop (iv->step, loop->num))
+ return false;
+ }
+ else if (TREE_CODE (iv->step) != INTEGER_CST)
return false;
- *base = CHREC_LEFT (ev);
- if (tree_contains_chrecs (*base)
- || chrec_contains_symbols_defined_in_loop (*base, loop->num))
+
+ iv->base = CHREC_LEFT (ev);
+ if (tree_contains_chrecs (iv->base, NULL)
+ || chrec_contains_symbols_defined_in_loop (iv->base, loop->num))
return false;
+ iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (type);
+
return true;
}
void
scev_analysis (void)
{
- varray_type exit_conditions;
+ VEC(tree,heap) *exit_conditions;
- VARRAY_GENERIC_PTR_INIT (exit_conditions, 37, "exit_conditions");
- select_loops_exit_conditions (current_loops, &exit_conditions);
+ exit_conditions = VEC_alloc (tree, heap, 37);
+ select_loops_exit_conditions (&exit_conditions);
if (dump_file && (dump_flags & TDF_STATS))
- analyze_scalar_evolution_for_all_loop_phi_nodes (exit_conditions);
+ analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions);
- number_of_iterations_for_all_loops (exit_conditions);
- VARRAY_CLEAR (exit_conditions);
+ number_of_iterations_for_all_loops (&exit_conditions);
+ VEC_free (tree, heap, exit_conditions);
}
/* Finalize the scalar evolution analysis. */
scev_finalize (void)
{
htab_delete (scalar_evolution_info);
- BITMAP_XFREE (already_instantiated);
+ BITMAP_FREE (already_instantiated);
+ scalar_evolution_info = NULL;
+}
+
+/* Replace ssa names for that scev can prove they are constant by the
+ appropriate constants. Also perform final value replacement in loops,
+ in case the replacement expressions are cheap.
+
+ We only consider SSA names defined by phi nodes; rest is left to the
+ ordinary constant propagation pass. */
+
+unsigned int
+scev_const_prop (void)
+{
+ basic_block bb;
+ tree name, phi, next_phi, type, ev;
+ struct loop *loop, *ex_loop;
+ bitmap ssa_names_to_remove = NULL;
+ unsigned i;
+ loop_iterator li;
+
+ if (!current_loops)
+ return 0;
+
+ FOR_EACH_BB (bb)
+ {
+ loop = bb->loop_father;
+
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ {
+ name = PHI_RESULT (phi);
+
+ if (!is_gimple_reg (name))
+ continue;
+
+ type = TREE_TYPE (name);
+
+ if (!POINTER_TYPE_P (type)
+ && !INTEGRAL_TYPE_P (type))
+ continue;
+
+ ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name));
+ if (!is_gimple_min_invariant (ev)
+ || !may_propagate_copy (name, ev))
+ continue;
+
+ /* Replace the uses of the name. */
+ if (name != ev)
+ replace_uses_by (name, ev);
+
+ if (!ssa_names_to_remove)
+ ssa_names_to_remove = BITMAP_ALLOC (NULL);
+ bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
+ }
+ }
+
+ /* Remove the ssa names that were replaced by constants. We do not
+ remove them directly in the previous cycle, since this
+ invalidates scev cache. */
+ if (ssa_names_to_remove)
+ {
+ bitmap_iterator bi;
+
+ EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
+ {
+ name = ssa_name (i);
+ phi = SSA_NAME_DEF_STMT (name);
+
+ gcc_assert (TREE_CODE (phi) == PHI_NODE);
+ remove_phi_node (phi, NULL, true);
+ }
+
+ BITMAP_FREE (ssa_names_to_remove);
+ scev_reset ();
+ }
+
+ /* Now the regular final value replacement. */
+ FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
+ {
+ edge exit;
+ tree def, rslt, ass, niter;
+ block_stmt_iterator bsi;
+
+ /* If we do not know exact number of iterations of the loop, we cannot
+ replace the final value. */
+ exit = single_exit (loop);
+ if (!exit)
+ continue;
+
+ niter = number_of_latch_executions (loop);
+ /* We used to check here whether the computation of NITER is expensive,
+ and avoided final value elimination if that is the case. The problem
+ is that it is hard to evaluate whether the expression is too
+ expensive, as we do not know what optimization opportunities the
+ the elimination of the final value may reveal. Therefore, we now
+ eliminate the final values of induction variables unconditionally. */
+ if (niter == chrec_dont_know)
+ continue;
+
+ /* Ensure that it is possible to insert new statements somewhere. */
+ if (!single_pred_p (exit->dest))
+ split_loop_exit_edge (exit);
+ tree_block_label (exit->dest);
+ bsi = bsi_after_labels (exit->dest);
+
+ ex_loop = superloop_at_depth (loop,
+ loop_depth (exit->dest->loop_father) + 1);
+
+ for (phi = phi_nodes (exit->dest); phi; phi = next_phi)
+ {
+ next_phi = PHI_CHAIN (phi);
+ rslt = PHI_RESULT (phi);
+ def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
+ if (!is_gimple_reg (def))
+ continue;
+
+ if (!POINTER_TYPE_P (TREE_TYPE (def))
+ && !INTEGRAL_TYPE_P (TREE_TYPE (def)))
+ continue;
+
+ def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL);
+ def = compute_overall_effect_of_inner_loop (ex_loop, def);
+ if (!tree_does_not_contain_chrecs (def)
+ || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
+ /* Moving the computation from the loop may prolong life range
+ of some ssa names, which may cause problems if they appear
+ on abnormal edges. */
+ || contains_abnormal_ssa_name_p (def))
+ continue;
+
+ /* Eliminate the PHI node and replace it by a computation outside
+ the loop. */
+ def = unshare_expr (def);
+ remove_phi_node (phi, NULL_TREE, false);
+
+ ass = build_gimple_modify_stmt (rslt, NULL_TREE);
+ SSA_NAME_DEF_STMT (rslt) = ass;
+ {
+ block_stmt_iterator dest = bsi;
+ bsi_insert_before (&dest, ass, BSI_NEW_STMT);
+ def = force_gimple_operand_bsi (&dest, def, false, NULL_TREE);
+ }
+ GIMPLE_STMT_OPERAND (ass, 1) = def;
+ update_stmt (ass);
+ }
+ }
+ return 0;
}
+#include "gt-tree-scalar-evolution.h"
OSDN Git Service
