#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;
}
\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),
+ chrec_convert (type_rhs, evol, at_stmt),
PLUS_EXPR, rhs1);
- 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);
+
+ 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);
+
+ 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);
+
+ 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);
- 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:
return follow_ssa_edge_in_rhs (loop, def,
TREE_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
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
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:
/* 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;
}
}
/* 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;
-
+
+ /* 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;
}
else if (res != chrec_dont_know)
- res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs,
- cache);
+ res = instantiate_parameters_1 (loop, res, flags, cache, size_expr);
bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
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;
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;
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;
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;
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;
{
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;
}
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;
}
}
/* 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;
}
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)
{
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)
+ 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)
- || def == PHI_RESULT (phi)
- || (TREE_CODE (def) == SSA_NAME
- && loop_containing_stmt (SSA_NAME_DEF_STMT (def))
- && loop_containing_stmt (phi)
- && loop_containing_stmt (SSA_NAME_DEF_STMT (def))
- == loop_containing_stmt (phi)))
+ || chrec_contains_symbols_defined_in_loop (def, ex_loop->num))
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 (MODIFY_EXPR, 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);
+ }
+ TREE_OPERAND (ass, 1) = def;
+ update_stmt (ass);
}
}
+ return 0;
}