/* Scalar evolution detector.
- Copyright (C) 2003, 2004, 2005 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.
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
{
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;
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;
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 (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. */
res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
chrec_is_positive (tree chrec, bool *value)
{
bool value0, value1, value2;
- tree type, end_value, nb_iter;
+ 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;
- 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. */
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;
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;
}
else
{
+ 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);
set_nb_iterations_in_loop (struct loop *loop,
tree res)
{
- 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
- 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 = ");
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);
}
/* Outer loop. */
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, 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 t_false;
}
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;
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)
+ || symbol_mem_tag (SSA_NAME_VAR (ptr)))
return true;
FOR_EACH_IMM_USE_FAST (use_p, imm_iter, ptr)
if (TREE_CODE (stmt) == COND_EXPR)
return true;
- if (TREE_CODE (stmt) != MODIFY_EXPR)
+ if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
continue;
- rhs = TREE_OPERAND (stmt, 1);
+ rhs = GIMPLE_STMT_OPERAND (stmt, 1);
if (!COMPARISON_CLASS_P (rhs))
continue;
- if (TREE_OPERAND (stmt, 0) == ptr
- || TREE_OPERAND (stmt, 1) == ptr)
+ if (GIMPLE_STMT_OPERAND (stmt, 0) == ptr
+ || GIMPLE_STMT_OPERAND (stmt, 1) == ptr)
return true;
}
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)
return NULL_TREE;
loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
- exit = loop->single_exit;
+ exit = single_exit (loop);
if (!exit)
return NULL_TREE;
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");
- exit = loop->single_exit;
+ exit = single_exit (loop);
if (!exit)
goto end;
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. */
for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
{
- tree res = number_of_iterations_in_loop (loop_containing_stmt (cond));
+ 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");
/* 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);
initialize_scalar_evolutions_analyzer ();
- for (i = 1; i < loops->num; i++)
- if (loops->parray[i])
- 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;
}
}
&& !chrec_contains_symbols_defined_in_loop (ev, loop->num))
{
iv->base = ev;
+ iv->step = build_int_cst (TREE_TYPE (ev), 0);
iv->no_overflow = true;
return true;
}
|| chrec_contains_symbols_defined_in_loop (iv->base, loop->num))
return false;
- iv->no_overflow = (!folded_casts
- && !flag_wrapv
- && !TYPE_UNSIGNED (type));
+ iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (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);
struct loop *loop, *ex_loop;
bitmap ssa_names_to_remove = NULL;
unsigned i;
+ loop_iterator li;
if (!current_loops)
return 0;
}
}
- /* Remove the ssa names that were replaced by constants. We do not remove them
- directly in the previous cycle, since this invalidates scev cache. */
+ /* 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;
- unsigned i;
EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
{
phi = SSA_NAME_DEF_STMT (name);
gcc_assert (TREE_CODE (phi) == PHI_NODE);
- remove_phi_node (phi, NULL);
+ remove_phi_node (phi, NULL, true);
}
BITMAP_FREE (ssa_names_to_remove);
}
/* Now the regular final value replacement. */
- for (i = current_loops->num - 1; i > 0; i--)
+ FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
{
edge exit;
tree def, rslt, ass, niter;
block_stmt_iterator bsi;
- loop = current_loops->parray[i];
- if (!loop)
- continue;
-
/* If we do not know exact number of iterations of the loop, we cannot
replace the final value. */
- exit = loop->single_exit;
+ exit = single_exit (loop);
if (!exit)
continue;
- niter = number_of_iterations_in_loop (loop);
+ niter = number_of_latch_executions (loop);
if (niter == chrec_dont_know
/* If computing the number of iterations is expensive, it may be
better not to introduce computations involving it. */
|| contains_abnormal_ssa_name_p (def))
continue;
- /* Eliminate the phi node and replace it by a computation outside
+ /* 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);
+ remove_phi_node (phi, NULL_TREE, false);
- ass = build2 (MODIFY_EXPR, void_type_node, rslt, NULL_TREE);
+ 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);
}
- TREE_OPERAND (ass, 1) = def;
+ GIMPLE_STMT_OPERAND (ass, 1) = def;
update_stmt (ass);
}
}
OSDN Git Service
