{
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
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,
{
/* 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, limit);
+ &evol, 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);
+ chrec_convert (type_rhs, evol, at_stmt),
+ PLUS_EXPR, rhs1, at_stmt);
else if (res == t_false)
{
*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;
*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;
*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;
if (res == t_true)
*evolution_of_loop = add_to_evolution
(loop->num, chrec_convert (type_rhs, *evolution_of_loop, at_stmt),
- MINUS_EXPR, rhs1);
+ MINUS_EXPR, rhs1, at_stmt);
else if (res == t_dont_know)
*evolution_of_loop = chrec_dont_know;
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);
-
- 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, limit);
-
- if (res == t_true || res == t_dont_know)
- *evolution_of_loop = chrec_dont_know;
-
- else if (res == t_false)
- {
- res = follow_ssa_edge
- (loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
- evolution_of_loop, limit);
-
- if (res == t_true || res == t_dont_know)
- *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, limit);
- if (res == t_true || res == t_dont_know)
- *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, limit);
- if (res == t_true || 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 = t_false;
-
- break;
-
case ASSERT_EXPR:
{
/* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
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:
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)
/* 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;
}
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))
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:
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:
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:
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:
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;
}
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, rslt, ass;
+ tree def, rslt, ass, niter;
block_stmt_iterator bsi;
loop = current_loops->parray[i];
/* 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;
/* Ensure that it is possible to insert new statements somewhere. */
&& !INTEGRAL_TYPE_P (TREE_TYPE (def)))
continue;
- def = analyze_scalar_evolution_in_loop (ex_loop, 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, ex_loop->num))
continue;
- /* If computing the expression is expensive, let it remain in the
- loop. */
- if (expression_expensive_p (def))
- continue;
-
/* Eliminate the phi node and replace it by a computation outside
the loop. */
def = unshare_expr (def);
ass = build2 (MODIFY_EXPR, void_type_node, rslt, NULL_TREE);
SSA_NAME_DEF_STMT (rslt) = ass;
- bsi_insert_after (&bsi, ass, BSI_NEW_STMT);
- def = force_gimple_operand_bsi (&bsi, def, false, NULL_TREE);
+ {
+ 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;
}
OSDN Git Service
