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 "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);
{
struct scev_info_str *res;
- res = xmalloc (sizeof (struct scev_info_str));
+ res = XNEW (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;
}
if (!*slot)
*slot = new_scev_info_str (var);
- res = *slot;
+ res = (struct scev_info_str *) *slot;
return &res->chrec;
}
else
{
tree res;
+ tree type = chrec_type (nb_iter);
/* 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,
- build_int_cst_type (chrec_type (nb_iter), 1));
+ nb_iter = chrec_fold_minus (type, nb_iter,
+ build_int_cst (type, 1));
/* evolution_fn is the evolution function in LOOP. Get
its value in the nb_iter-th iteration. */
bool
chrec_is_positive (tree chrec, bool *value)
{
- bool value0, value1;
- bool value2;
- tree end_value;
- tree nb_iter;
+ bool value0, value1, value2;
+ tree type, end_value, nb_iter;
switch (TREE_CODE (chrec))
{
if (chrec_contains_undetermined (nb_iter))
return false;
- nb_iter = chrec_fold_minus
- (chrec_type (nb_iter), nb_iter,
- build_int_cst (chrec_type (nb_iter), 1));
+ type = chrec_type (nb_iter);
+ nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1));
#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,
- build_int_cst (chrec_type (nb_iter), 1));
+ 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;
+
switch (TREE_CODE (chrec_before))
{
case POLYNOMIAL_CHREC:
if (CHREC_VARIABLE (chrec_before) <= loop_nb)
{
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)
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));
+ {
+ /* 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;
? 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,
- build_int_cst_type (chrec_type (res), 1));
+ tree type = chrec_type (res);
+
+ res = chrec_fold_plus (type, res, build_int_cst (type, 1));
/* FIXME HWI: However we want to store one iteration less than the
count of the loop in order to be compatible with the other
get_loop_exit_condition (struct loop *loop)
{
tree res = NULL_TREE;
- edge exit_edge = loop->single_exit;
-
+ edge exit_edge = single_exit (loop);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(get_loop_exit_condition \n ");
get_exit_conditions_rec (loop->inner, exit_conditions);
get_exit_conditions_rec (loop->next, exit_conditions);
- if (loop->single_exit)
+ if (single_exit (loop))
{
tree loop_condition = get_loop_exit_condition (loop);
initializes the EXIT_CONDITIONS array. */
static void
-select_loops_exit_conditions (struct loops *loops,
- VEC(tree,heap) **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 at_stmt,
- 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,
case NOP_EXPR:
/* This assignment is under the form "a_1 = (cast) rhs. */
res = follow_ssa_edge_in_rhs (loop, at_stmt, TREE_OPERAND (rhs, 0),
- halting_phi, evolution_of_loop);
+ 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, at_stmt),
- 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, at_stmt),
- PLUS_EXPR, rhs0);
+ 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,
at_stmt),
- PLUS_EXPR, rhs1);
+ 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,
at_stmt),
- PLUS_EXPR, rhs0);
+ 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;
/* 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, limit);
+ if (res == t_true)
*evolution_of_loop = add_to_evolution
- (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
- at_stmt),
- MINUS_EXPR, rhs1);
- }
- else
- /* Otherwise, match an assignment under the form:
- "a = ... - ...". */
- /* And there is nothing to do. */
- res = 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);
+ (loop->num, chrec_convert (type_rhs, *evolution_of_loop, at_stmt),
+ MINUS_EXPR, rhs1, at_stmt);
- 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)
+ else if (res == t_dont_know)
*evolution_of_loop = chrec_dont_know;
}
-
else
/* Otherwise, match an assignment under the form:
- "a = ... * ...". */
+ "a = ... - ...". */
/* And there is nothing to do. */
- res = false;
+ res = t_false;
break;
-
+
case ASSERT_EXPR:
{
/* This assignment is of the form: "a_1 = ASSERT_EXPR <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);
+ halting_phi, evolution_of_loop, limit);
else
- res = false;
+ res = t_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
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++)
/* Quickly give up when the evolution of one of the branches is
not known. */
if (*evolution_of_loop == chrec_dont_know)
- return true;
+ return t_true;
- if (!follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
- halting_phi,
- &evolution_of_branch,
- init))
- return false;
+ 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, loop_phi_node,
- 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, loop_phi_node, ev, halting_phi,
- evolution_of_loop);
+ 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, 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:
+ case GIMPLE_MODIFY_STMT:
return follow_ssa_edge_in_rhs (loop, def,
- TREE_OPERAND (def, 1),
+ 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
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
return res;
}
-/* Interpret the right hand side of a modify_expr OPND1. If we didn't
+/* 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 modify_expr, or on a loop-phi-node. On the
+ 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 at_stmt,
- tree opnd1, tree type)
+interpret_rhs_modify_stmt (struct loop *loop, tree at_stmt,
+ tree opnd1, tree type)
{
tree res, opnd10, opnd11, chrec10, chrec11;
opnd10 = TREE_OPERAND (opnd1, 0);
chrec10 = analyze_scalar_evolution (loop, opnd10);
chrec10 = chrec_convert (type, chrec10, at_stmt);
- res = chrec_fold_multiply (type, chrec10, SCALAR_FLOAT_TYPE_P (type)
- ? build_real (type, dconstm1)
- : build_int_cst_type (type, -1));
+ /* 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:
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);
+ var_ann_t v_ann = var_ann (SSA_NAME_VAR (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)
+ || v_ann->symbol_mem_tag)
+ 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, NULL_TREE, 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, def, 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;
struct scev_info_str *info, pattern;
pattern.var = version;
- info = htab_find (cache, &pattern);
+ info = (struct scev_info_str *) htab_find (cache, &pattern);
if (info)
return info->chrec;
pattern.var = version;
slot = htab_find_slot (cache, &pattern, INSERT);
- if (*slot)
- info = *slot;
- else
- info = *slot = new_scev_info_str (version);
+ 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. CACHE is the cache of already instantiated
- values. */
+ 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,
- htab_t cache)
+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;
-
+ 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;
/* 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;
result again. */
bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec));
res = analyze_scalar_evolution (def_loop, chrec);
- if (res != chrec_dont_know)
- res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs,
- cache);
+
+ /* Don't instantiate loop-closed-ssa phi nodes. */
+ if (TREE_CODE (res) == SSA_NAME
+ && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL
+ || (loop_containing_stmt (SSA_NAME_DEF_STMT (res))->depth
+ > def_loop->depth)))
+ {
+ 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. */
case POLYNOMIAL_CHREC:
op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
- allow_superloop_chrecs, cache);
+ flags, cache, size_expr);
if (op0 == chrec_dont_know)
return chrec_dont_know;
op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
- allow_superloop_chrecs, cache);
+ flags, cache, size_expr);
if (op1 == chrec_dont_know)
return chrec_dont_know;
if (CHREC_LEFT (chrec) != op0
|| CHREC_RIGHT (chrec) != op1)
- chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, 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, cache);
+ 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, cache);
+ flags, cache, size_expr);
if (op1 == chrec_dont_know)
return chrec_dont_know;
if (TREE_OPERAND (chrec, 0) != op0
|| TREE_OPERAND (chrec, 1) != op1)
- chrec = chrec_fold_plus (TREE_TYPE (chrec), op0, 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, cache);
+ 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, cache);
+ flags, cache, size_expr);
if (op1 == chrec_dont_know)
return chrec_dont_know;
if (TREE_OPERAND (chrec, 0) != op0
|| TREE_OPERAND (chrec, 1) != op1)
- chrec = chrec_fold_minus (TREE_TYPE (chrec), op0, 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, cache);
+ 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, cache);
+ flags, cache, size_expr);
if (op1 == chrec_dont_know)
return chrec_dont_know;
if (TREE_OPERAND (chrec, 0) != op0
|| TREE_OPERAND (chrec, 1) != op1)
- chrec = chrec_fold_multiply (TREE_TYPE (chrec), op0, 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, cache);
+ flags, cache, size_expr);
if (op0 == chrec_dont_know)
return chrec_dont_know;
+ 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:
{
case 3:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
- allow_superloop_chrecs, cache);
+ 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, cache);
+ 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, cache);
+ flags, cache, size_expr);
if (op2 == chrec_dont_know)
return chrec_dont_know;
case 2:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
- allow_superloop_chrecs, cache);
+ 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, cache);
+ flags, cache, size_expr);
if (op1 == chrec_dont_know)
return chrec_dont_know;
case 1:
op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
- allow_superloop_chrecs, cache);
+ flags, cache, size_expr);
if (op0 == chrec_dont_know)
return chrec_dont_know;
if (op0 == TREE_OPERAND (chrec, 0))
fprintf (dump_file, ")\n");
}
- res = instantiate_parameters_1 (loop, chrec, true, cache);
+ res = instantiate_parameters_1 (loop, chrec, INSERT_SUPERLOOP_CHRECS, cache,
+ 0);
if (dump_file && (dump_flags & TDF_DETAILS))
{
}
/* 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
resolve_mixers (struct loop *loop, tree chrec)
{
htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
- tree ret = instantiate_parameters_1 (loop, chrec, false, cache);
+ tree ret = instantiate_parameters_1 (loop, chrec, FOLD_CONVERSIONS, cache, 0);
htab_delete (cache);
return ret;
}
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(number_of_iterations_in_loop\n");
- exit = loop->single_exit;
+ exit = single_exit (loop);
if (!exit)
goto end;
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;
}
/* Initialize the analysis of scalar evolutions for LOOPS. */
void
-scev_initialize (struct loops *loops)
+scev_initialize (void)
{
unsigned i;
- current_loops = loops;
scalar_evolution_info = htab_create (100, hash_scev_info,
eq_scev_info, del_scev_info);
initialize_scalar_evolutions_analyzer ();
- for (i = 1; i < loops->num; i++)
- if (loops->parray[i])
- loops->parray[i]->nb_iterations = NULL_TREE;
+ for (i = 1; i < current_loops->num; i++)
+ if (current_loops->parray[i])
+ current_loops->parray[i]->nb_iterations = NULL_TREE;
}
/* Cleans up the information cached by the scalar evolutions analysis. */
}
/* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
- its BASE and STEP 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. */
+ 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->no_overflow = true;
return true;
}
|| CHREC_VARIABLE (ev) != (unsigned) loop->num)
return false;
- *step = CHREC_RIGHT (ev);
+ iv->step = CHREC_RIGHT (ev);
if (allow_nonconstant_step)
{
- if (tree_contains_chrecs (*step, NULL)
- || chrec_contains_symbols_defined_in_loop (*step, loop->num))
+ if (tree_contains_chrecs (iv->step, NULL)
+ || chrec_contains_symbols_defined_in_loop (iv->step, loop->num))
return false;
}
- else if (TREE_CODE (*step) != INTEGER_CST)
+ else if (TREE_CODE (iv->step) != INTEGER_CST)
return false;
- *base = CHREC_LEFT (ev);
- if (tree_contains_chrecs (*base, NULL)
- || 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
+ && !flag_wrapv
+ && !TYPE_UNSIGNED (type));
return true;
}
VEC(tree,heap) *exit_conditions;
exit_conditions = VEC_alloc (tree, heap, 37);
- select_loops_exit_conditions (current_loops, &exit_conditions);
+ select_loops_exit_conditions (&exit_conditions);
if (dump_file && (dump_flags & TDF_STATS))
analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions);
BITMAP_FREE (already_instantiated);
}
+/* Returns true if EXPR looks expensive. */
+
+static bool
+expression_expensive_p (tree expr)
+{
+ return force_expr_to_var_cost (expr) >= target_spill_cost;
+}
+
/* 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. */
-void
+unsigned int
scev_const_prop (void)
{
basic_block bb;
unsigned i;
if (!current_loops)
- return;
+ return 0;
FOR_EACH_BB (bb)
{
continue;
/* Replace the uses of the name. */
- replace_uses_by (name, ev);
+ if (name != ev)
+ replace_uses_by (name, ev);
if (!ssa_names_to_remove)
ssa_names_to_remove = BITMAP_ALLOC (NULL);
for (i = current_loops->num - 1; i > 0; i--)
{
edge exit;
- tree def, stmts;
+ tree def, rslt, ass, niter;
+ block_stmt_iterator bsi;
loop = current_loops->parray[i];
if (!loop)
/* If we do not know exact number of iterations of the loop, we cannot
replace the final value. */
- exit = loop->single_exit;
- if (!exit
- || number_of_iterations_in_loop (loop) == chrec_dont_know)
+ exit = single_exit (loop);
+ if (!exit)
+ continue;
+
+ niter = number_of_iterations_in_loop (loop);
+ if (niter == chrec_dont_know
+ /* If computing the number of iterations is expensive, it may be
+ better not to introduce computations involving it. */
+ || expression_expensive_p (niter))
continue;
- ex_loop = exit->dest->loop_father;
+
+ /* 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, exit->dest->loop_father->depth + 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)
- || expr_invariant_in_loop_p (loop, def))
+ 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, ex_loop, def);
+ 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, loop->num))
+ || 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;
- /* If computing the expression is expensive, let it remain in
- loop. TODO -- we should take the cost of computing the expression
- in loop into account. */
- if (force_expr_to_var_cost (def) >= target_spill_cost)
- continue;
+ /* Eliminate the phi node and replace it by a computation outside
+ the loop. */
def = unshare_expr (def);
+ SET_PHI_RESULT (phi, NULL_TREE);
+ remove_phi_node (phi, NULL_TREE);
- if (is_gimple_val (def))
- stmts = NULL_TREE;
- else
- def = force_gimple_operand (def, &stmts, true,
- SSA_NAME_VAR (PHI_RESULT (phi)));
- SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, exit), def);
- if (stmts)
- compute_phi_arg_on_exit (exit, stmts, def);
+ ass = build2 (GIMPLE_MODIFY_STMT, void_type_node, 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;
}