/* Scalar evolution detector.
- Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 Free Software
- Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
+ 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 GIMPLE_MODIFY_STMT: if the right hand side
+ - When the definition is a GIMPLE_ASSIGN: 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
value of loop_2 for "j" is 4, and the evolution of "k" in loop_1 is
{0, +, 1}_1. To obtain the evolution function in loop_3 and
instantiate the scalar variables up to loop_1, one has to use:
- instantiate_scev (loop_1, loop_3, "j + k"). The result of this
- call is {{0, +, 1}_1, +, 1}_2.
+ instantiate_scev (block_before_loop (loop_1), loop_3, "j + k").
+ The result of this call is {{0, +, 1}_1, +, 1}_2.
Example 3: Higher degree polynomials.
static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
-/* The cached information about a ssa name VAR, claiming that inside LOOP,
- the value of VAR can be expressed as CHREC. */
+/* The cached information about an SSA name VAR, claiming that below
+ basic block INSTANTIATED_BELOW, the value of VAR can be expressed
+ as CHREC. */
-struct scev_info_str GTY(())
-{
+struct GTY(()) scev_info_str {
+ basic_block instantiated_below;
tree var;
tree chrec;
};
happen, then it qualifies it with chrec_known. */
tree chrec_known;
-static bitmap already_instantiated;
-
static GTY ((param_is (struct scev_info_str))) htab_t scalar_evolution_info;
\f
-/* Constructs a new SCEV_INFO_STR structure. */
+/* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
static inline struct scev_info_str *
-new_scev_info_str (tree var)
+new_scev_info_str (basic_block instantiated_below, tree var)
{
struct scev_info_str *res;
res = GGC_NEW (struct scev_info_str);
res->var = var;
res->chrec = chrec_not_analyzed_yet;
-
+ res->instantiated_below = instantiated_below;
+
return res;
}
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;
+ return (elt1->var == elt2->var
+ && elt1->instantiated_below == elt2->instantiated_below);
}
/* Deletes database element E. */
ggc_free (e);
}
-/* Get the index corresponding to VAR in the current LOOP. If
- it's the first time we ask for this VAR, then we return
- chrec_not_analyzed_yet for this VAR and return its index. */
+/* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
+ A first query on VAR returns chrec_not_analyzed_yet. */
static tree *
-find_var_scev_info (tree var)
+find_var_scev_info (basic_block instantiated_below, tree var)
{
struct scev_info_str *res;
struct scev_info_str tmp;
PTR *slot;
tmp.var = var;
+ tmp.instantiated_below = instantiated_below;
slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT);
if (!*slot)
- *slot = new_scev_info_str (var);
+ *slot = new_scev_info_str (instantiated_below, var);
res = (struct scev_info_str *) *slot;
return &res->chrec;
if (TREE_CODE (chrec) == SSA_NAME)
{
- tree def = SSA_NAME_DEF_STMT (chrec);
+ gimple def = SSA_NAME_DEF_STMT (chrec);
struct loop *def_loop = loop_containing_stmt (def);
struct loop *loop = get_loop (loop_nb);
/* Return true when PHI is a loop-phi-node. */
static bool
-loop_phi_node_p (tree phi)
+loop_phi_node_p (gimple phi)
{
/* The implementation of this function is based on the following
property: "all the loop-phi-nodes of a loop are contained in the
loop's header basic block". */
- return loop_containing_stmt (phi)->header == bb_for_stmt (phi);
+ return loop_containing_stmt (phi)->header == gimple_bb (phi);
}
/* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
EVOLUTION_FN = {i_0, +, 2}_1.
*/
-static tree
+tree
compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
{
bool val = false;
/* 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);
-
+
+ if (chrec_contains_symbols_defined_in_loop (res, loop->num))
+ res = instantiate_parameters (loop, res);
+
/* Continue the computation until ending on a parent of LOOP. */
return compute_overall_effect_of_inner_loop (loop, res);
}
/* Associate CHREC to SCALAR. */
static void
-set_scalar_evolution (tree scalar, tree chrec)
+set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec)
{
tree *scalar_info;
if (TREE_CODE (scalar) != SSA_NAME)
return;
- scalar_info = find_var_scev_info (scalar);
+ scalar_info = find_var_scev_info (instantiated_below, scalar);
if (dump_file)
{
if (dump_flags & TDF_DETAILS)
{
fprintf (dump_file, "(set_scalar_evolution \n");
+ fprintf (dump_file, " instantiated_below = %d \n",
+ instantiated_below->index);
fprintf (dump_file, " (scalar = ");
print_generic_expr (dump_file, scalar, 0);
fprintf (dump_file, ")\n (scalar_evolution = ");
*scalar_info = chrec;
}
-/* Retrieve the chrec associated to SCALAR in the LOOP. */
+/* Retrieve the chrec associated to SCALAR instantiated below
+ INSTANTIATED_BELOW block. */
static tree
-get_scalar_evolution (tree scalar)
+get_scalar_evolution (basic_block instantiated_below, tree scalar)
{
tree res;
switch (TREE_CODE (scalar))
{
case SSA_NAME:
- res = *find_var_scev_info (scalar);
+ res = *find_var_scev_info (instantiated_below, scalar);
break;
case REAL_CST:
static tree
add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
- tree at_stmt)
+ gimple at_stmt)
{
tree type, left, right;
struct loop *loop = get_loop (loop_nb), *chloop;
static tree
add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
- tree to_add, tree at_stmt)
+ tree to_add, gimple at_stmt)
{
tree type = chrec_type (to_add);
tree res = NULL_TREE;
scalar evolution analysis. For the moment, greedily select all the
loop nests we could analyze. */
-/* Return true when it is possible to analyze the condition expression
- EXPR. */
-
-static bool
-analyzable_condition (const_tree expr)
-{
- tree condition;
-
- if (TREE_CODE (expr) != COND_EXPR)
- return false;
-
- condition = TREE_OPERAND (expr, 0);
-
- switch (TREE_CODE (condition))
- {
- case SSA_NAME:
- return true;
-
- case LT_EXPR:
- case LE_EXPR:
- case GT_EXPR:
- case GE_EXPR:
- case EQ_EXPR:
- case NE_EXPR:
- return true;
-
- default:
- return false;
- }
-
- return false;
-}
-
/* For a loop with a single exit edge, return the COND_EXPR that
guards the exit edge. If the expression is too difficult to
analyze, then give up. */
-tree
+gimple
get_loop_exit_condition (const struct loop *loop)
{
- tree res = NULL_TREE;
+ gimple res = NULL;
edge exit_edge = single_exit (loop);
if (dump_file && (dump_flags & TDF_DETAILS))
if (exit_edge)
{
- tree expr;
+ gimple stmt;
- expr = last_stmt (exit_edge->src);
- if (analyzable_condition (expr))
- res = expr;
+ stmt = last_stmt (exit_edge->src);
+ if (gimple_code (stmt) == GIMPLE_COND)
+ res = stmt;
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
- print_generic_expr (dump_file, res, 0);
+ print_gimple_stmt (dump_file, res, 0, 0);
fprintf (dump_file, ")\n");
}
static void
get_exit_conditions_rec (struct loop *loop,
- VEC(tree,heap) **exit_conditions)
+ VEC(gimple,heap) **exit_conditions)
{
if (!loop)
return;
if (single_exit (loop))
{
- tree loop_condition = get_loop_exit_condition (loop);
+ gimple loop_condition = get_loop_exit_condition (loop);
if (loop_condition)
- VEC_safe_push (tree, heap, *exit_conditions, loop_condition);
+ VEC_safe_push (gimple, heap, *exit_conditions, loop_condition);
}
}
initializes the EXIT_CONDITIONS array. */
static void
-select_loops_exit_conditions (VEC(tree,heap) **exit_conditions)
+select_loops_exit_conditions (VEC(gimple,heap) **exit_conditions)
{
struct loop *function_body = current_loops->tree_root;
} t_bool;
-static t_bool follow_ssa_edge (struct loop *loop, tree, tree, tree *, int);
+static t_bool follow_ssa_edge (struct loop *loop, gimple, gimple, tree *, int);
-/* Follow the ssa edge into the right hand side RHS of an assignment.
+/* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
Return true if the strongly connected component has been found. */
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)
+follow_ssa_edge_binary (struct loop *loop, gimple at_stmt,
+ tree type, tree rhs0, enum tree_code code, tree rhs1,
+ gimple halting_phi, tree *evolution_of_loop, int limit)
{
t_bool res = t_false;
- tree rhs0, rhs1;
- tree type_rhs = TREE_TYPE (rhs);
tree evol;
- enum tree_code code;
-
- /* The RHS is one of the following cases:
- - an SSA_NAME,
- - an INTEGER_CST,
- - a PLUS_EXPR,
- - a POINTER_PLUS_EXPR,
- - a MINUS_EXPR,
- - an ASSERT_EXPR,
- - other cases are not yet handled. */
- code = TREE_CODE (rhs);
+
switch (code)
{
- 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, 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 = 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, limit);
- break;
-
case POINTER_PLUS_EXPR:
case PLUS_EXPR:
- /* This case is under the form "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)
evol = *evolution_of_loop;
res = follow_ssa_edge
- (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
- &evol, limit);
+ (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, &evol, limit);
if (res == t_true)
*evolution_of_loop = add_to_evolution
(loop->num,
- chrec_convert (type_rhs, evol, at_stmt),
+ chrec_convert (type, evol, at_stmt),
code, rhs1, at_stmt);
else if (res == t_false)
if (res == t_true)
*evolution_of_loop = add_to_evolution
(loop->num,
- chrec_convert (type_rhs, *evolution_of_loop, at_stmt),
+ chrec_convert (type, *evolution_of_loop, at_stmt),
code, rhs0, at_stmt);
else if (res == t_dont_know)
evolution_of_loop, limit);
if (res == t_true)
*evolution_of_loop = add_to_evolution
- (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
+ (loop->num, chrec_convert (type, *evolution_of_loop,
at_stmt),
code, rhs1, at_stmt);
evolution_of_loop, limit);
if (res == t_true)
*evolution_of_loop = add_to_evolution
- (loop->num, chrec_convert (type_rhs, *evolution_of_loop,
+ (loop->num, chrec_convert (type, *evolution_of_loop,
at_stmt),
code, rhs0, at_stmt);
"a = ... + ...". */
/* And there is nothing to do. */
res = t_false;
-
break;
case MINUS_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)
{
/* Match an assignment under the form:
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),
+ (loop->num, chrec_convert (type, *evolution_of_loop, at_stmt),
MINUS_EXPR, rhs1, at_stmt);
else if (res == t_dont_know)
"a = ... - ...". */
/* And there is nothing to do. */
res = t_false;
-
break;
+
+ default:
+ res = t_false;
+ }
+
+ return res;
+}
- case ASSERT_EXPR:
- {
- /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
- It must be handled as a copy assignment of the form a_1 = a_2. */
- tree op0 = ASSERT_EXPR_VAR (rhs);
- if (TREE_CODE (op0) == SSA_NAME)
- res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (op0),
- halting_phi, evolution_of_loop, limit);
- else
- res = t_false;
- break;
- }
+/* Follow the ssa edge into the expression EXPR.
+ Return true if the strongly connected component has been found. */
+
+static t_bool
+follow_ssa_edge_expr (struct loop *loop, gimple at_stmt, tree expr,
+ gimple halting_phi, tree *evolution_of_loop, int limit)
+{
+ enum tree_code code = TREE_CODE (expr);
+ tree type = TREE_TYPE (expr), rhs0, rhs1;
+ t_bool res;
+
+ /* The EXPR is one of the following cases:
+ - an SSA_NAME,
+ - an INTEGER_CST,
+ - a PLUS_EXPR,
+ - a POINTER_PLUS_EXPR,
+ - a MINUS_EXPR,
+ - an ASSERT_EXPR,
+ - other cases are not yet handled. */
+
+ switch (code)
+ {
+ CASE_CONVERT:
+ /* This assignment is under the form "a_1 = (cast) rhs. */
+ res = follow_ssa_edge_expr (loop, at_stmt, TREE_OPERAND (expr, 0),
+ halting_phi, evolution_of_loop, limit);
+ *evolution_of_loop = chrec_convert (type, *evolution_of_loop, at_stmt);
+ break;
+
+ case INTEGER_CST:
+ /* This assignment is under the form "a_1 = 7". */
+ 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 (expr), halting_phi, evolution_of_loop, limit);
+ break;
+
+ case POINTER_PLUS_EXPR:
+ case PLUS_EXPR:
+ case MINUS_EXPR:
+ /* This case is under the form "rhs0 +- rhs1". */
+ rhs0 = TREE_OPERAND (expr, 0);
+ rhs1 = TREE_OPERAND (expr, 1);
+ type = TREE_TYPE (rhs0);
+ STRIP_USELESS_TYPE_CONVERSION (rhs0);
+ STRIP_USELESS_TYPE_CONVERSION (rhs1);
+ res = follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,
+ halting_phi, evolution_of_loop, limit);
+ break;
+ case ASSERT_EXPR:
+ /* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
+ It must be handled as a copy assignment of the form a_1 = a_2. */
+ rhs0 = ASSERT_EXPR_VAR (expr);
+ if (TREE_CODE (rhs0) == SSA_NAME)
+ res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0),
+ halting_phi, evolution_of_loop, limit);
+ else
+ res = t_false;
+ break;
default:
res = t_false;
break;
}
-
+
+ return res;
+}
+
+/* Follow the ssa edge into the right hand side of an assignment STMT.
+ Return true if the strongly connected component has been found. */
+
+static t_bool
+follow_ssa_edge_in_rhs (struct loop *loop, gimple stmt,
+ gimple halting_phi, tree *evolution_of_loop, int limit)
+{
+ enum tree_code code = gimple_assign_rhs_code (stmt);
+ tree type = gimple_expr_type (stmt), rhs1, rhs2;
+ t_bool res;
+
+ switch (code)
+ {
+ CASE_CONVERT:
+ /* This assignment is under the form "a_1 = (cast) rhs. */
+ res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
+ halting_phi, evolution_of_loop, limit);
+ *evolution_of_loop = chrec_convert (type, *evolution_of_loop, stmt);
+ break;
+
+ case POINTER_PLUS_EXPR:
+ case PLUS_EXPR:
+ case MINUS_EXPR:
+ rhs1 = gimple_assign_rhs1 (stmt);
+ rhs2 = gimple_assign_rhs2 (stmt);
+ type = TREE_TYPE (rhs1);
+ res = follow_ssa_edge_binary (loop, stmt, type, rhs1, code, rhs2,
+ halting_phi, evolution_of_loop, limit);
+ break;
+
+ default:
+ if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
+ res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
+ halting_phi, evolution_of_loop, limit);
+ else
+ res = t_false;
+ break;
+ }
+
return res;
}
/* Checks whether the I-th argument of a PHI comes from a backedge. */
static bool
-backedge_phi_arg_p (const_tree phi, int i)
+backedge_phi_arg_p (gimple phi, int i)
{
- const_edge e = PHI_ARG_EDGE (phi, i);
+ const_edge e = gimple_phi_arg_edge (phi, i);
/* We would in fact like to test EDGE_DFS_BACK here, but we do not care
about updating it anywhere, and this should work as well most of the
static inline t_bool
follow_ssa_edge_in_condition_phi_branch (int i,
struct loop *loop,
- tree condition_phi,
- tree halting_phi,
+ gimple condition_phi,
+ gimple halting_phi,
tree *evolution_of_branch,
tree init_cond, int limit)
{
static t_bool
follow_ssa_edge_in_condition_phi (struct loop *loop,
- tree condition_phi,
- tree halting_phi,
+ gimple condition_phi,
+ gimple halting_phi,
tree *evolution_of_loop, int limit)
{
- int i;
+ int i, n;
tree init = *evolution_of_loop;
tree evolution_of_branch;
t_bool res = follow_ssa_edge_in_condition_phi_branch (0, loop, condition_phi,
*evolution_of_loop = evolution_of_branch;
- /* If the phi node is just a copy, do not increase the limit. */
- if (PHI_NUM_ARGS (condition_phi) > 1)
- limit++;
-
- for (i = 1; i < PHI_NUM_ARGS (condition_phi); i++)
+ n = gimple_phi_num_args (condition_phi);
+ for (i = 1; i < n; i++)
{
/* Quickly give up when the evolution of one of the branches is
not known. */
if (*evolution_of_loop == chrec_dont_know)
return t_true;
+ /* Increase the limit by the PHI argument number to avoid exponential
+ time and memory complexity. */
res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
halting_phi,
&evolution_of_branch,
- init, limit);
+ init, limit + i);
if (res == t_false || res == t_dont_know)
return res;
static t_bool
follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
- tree loop_phi_node,
- tree halting_phi,
+ gimple loop_phi_node,
+ gimple halting_phi,
tree *evolution_of_loop, int limit)
{
struct loop *loop = loop_containing_stmt (loop_phi_node);
if (ev == PHI_RESULT (loop_phi_node))
{
t_bool res = t_false;
- int i;
+ int i, n = gimple_phi_num_args (loop_phi_node);
- for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
+ for (i = 0; i < n; i++)
{
tree arg = PHI_ARG_DEF (loop_phi_node, i);
basic_block bb;
/* Follow the edges that exit the inner loop. */
- bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
+ bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
if (!flow_bb_inside_loop_p (loop, bb))
- res = follow_ssa_edge_in_rhs (outer_loop, loop_phi_node,
- arg, halting_phi,
- evolution_of_loop, limit);
+ res = follow_ssa_edge_expr (outer_loop, loop_phi_node,
+ arg, halting_phi,
+ evolution_of_loop, limit);
if (res == t_true)
break;
}
/* 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, limit);
+ return follow_ssa_edge_expr (outer_loop, loop_phi_node, ev, halting_phi,
+ evolution_of_loop, limit);
}
/* Follow an SSA edge from a loop-phi-node to itself, constructing a
path that is analyzed on the return walk. */
static t_bool
-follow_ssa_edge (struct loop *loop, tree def, tree halting_phi,
+follow_ssa_edge (struct loop *loop, gimple def, gimple halting_phi,
tree *evolution_of_loop, int limit)
{
struct loop *def_loop;
- if (TREE_CODE (def) == NOP_EXPR)
+ if (gimple_nop_p (def))
return t_false;
/* Give up if the path is longer than the MAX that we allow. */
def_loop = loop_containing_stmt (def);
- switch (TREE_CODE (def))
+ switch (gimple_code (def))
{
- case PHI_NODE:
+ case GIMPLE_PHI:
if (!loop_phi_node_p (def))
/* DEF is a condition-phi-node. Follow the branches, and
record their evolutions. Finally, merge the collected
/* Outer loop. */
return t_false;
- case GIMPLE_MODIFY_STMT:
- return follow_ssa_edge_in_rhs (loop, def,
- GIMPLE_STMT_OPERAND (def, 1),
- halting_phi,
+ case GIMPLE_ASSIGN:
+ return follow_ssa_edge_in_rhs (loop, def, halting_phi,
evolution_of_loop, limit);
default:
/* At this level of abstraction, the program is just a set
- of GIMPLE_MODIFY_STMTs and PHI_NODEs. In principle there is no
+ of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
other node to be handled. */
return t_false;
}
function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
static tree
-analyze_evolution_in_loop (tree loop_phi_node,
+analyze_evolution_in_loop (gimple loop_phi_node,
tree init_cond)
{
- int i;
+ int i, n = gimple_phi_num_args (loop_phi_node);
tree evolution_function = chrec_not_analyzed_yet;
struct loop *loop = loop_containing_stmt (loop_phi_node);
basic_block bb;
{
fprintf (dump_file, "(analyze_evolution_in_loop \n");
fprintf (dump_file, " (loop_phi_node = ");
- print_generic_expr (dump_file, loop_phi_node, 0);
+ print_gimple_stmt (dump_file, loop_phi_node, 0, 0);
fprintf (dump_file, ")\n");
}
- for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
+ for (i = 0; i < n; i++)
{
tree arg = PHI_ARG_DEF (loop_phi_node, i);
- tree ssa_chain, ev_fn;
+ gimple ssa_chain;
+ tree ev_fn;
t_bool res;
/* Select the edges that enter the loop body. */
- bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
+ bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
if (!flow_bb_inside_loop_p (loop, bb))
continue;
loop, and leaves this task to the on-demand tree reconstructor. */
static tree
-analyze_initial_condition (tree loop_phi_node)
+analyze_initial_condition (gimple loop_phi_node)
{
- int i;
+ int i, n;
tree init_cond = chrec_not_analyzed_yet;
- struct loop *loop = bb_for_stmt (loop_phi_node)->loop_father;
+ struct loop *loop = loop_containing_stmt (loop_phi_node);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "(analyze_initial_condition \n");
fprintf (dump_file, " (loop_phi_node = \n");
- print_generic_expr (dump_file, loop_phi_node, 0);
+ print_gimple_stmt (dump_file, loop_phi_node, 0, 0);
fprintf (dump_file, ")\n");
}
- for (i = 0; i < PHI_NUM_ARGS (loop_phi_node); i++)
+ n = gimple_phi_num_args (loop_phi_node);
+ for (i = 0; i < n; i++)
{
tree branch = PHI_ARG_DEF (loop_phi_node, i);
- basic_block bb = PHI_ARG_EDGE (loop_phi_node, i)->src;
+ basic_block bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
/* When the branch is oriented to the loop's body, it does
not contribute to the initial condition. */
if (init_cond == chrec_not_analyzed_yet)
init_cond = chrec_dont_know;
+ /* During early loop unrolling we do not have fully constant propagated IL.
+ Handle degenerate PHIs here to not miss important unrollings. */
+ if (TREE_CODE (init_cond) == SSA_NAME)
+ {
+ gimple def = SSA_NAME_DEF_STMT (init_cond);
+ tree res;
+ if (gimple_code (def) == GIMPLE_PHI
+ && (res = degenerate_phi_result (def)) != NULL_TREE
+ /* Only allow invariants here, otherwise we may break
+ loop-closed SSA form. */
+ && is_gimple_min_invariant (res))
+ init_cond = res;
+ }
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (init_cond = ");
/* Analyze the scalar evolution for LOOP_PHI_NODE. */
static tree
-interpret_loop_phi (struct loop *loop, tree loop_phi_node)
+interpret_loop_phi (struct loop *loop, gimple loop_phi_node)
{
tree res;
struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
analyzed. */
static tree
-interpret_condition_phi (struct loop *loop, tree condition_phi)
+interpret_condition_phi (struct loop *loop, gimple condition_phi)
{
- int i;
+ int i, n = gimple_phi_num_args (condition_phi);
tree res = chrec_not_analyzed_yet;
- for (i = 0; i < PHI_NUM_ARGS (condition_phi); i++)
+ for (i = 0; i < n; i++)
{
tree branch_chrec;
return res;
}
-/* Interpret the right hand side of a GIMPLE_MODIFY_STMT OPND1. If we didn't
+/* Interpret the operation RHS1 OP RHS2. If we didn't
analyze this node before, follow the definitions until ending
- either on an analyzed GIMPLE_MODIFY_STMT, or on a loop-phi-node. On the
+ either on an analyzed GIMPLE_ASSIGN, 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_stmt (struct loop *loop, tree at_stmt,
- tree opnd1, tree type)
+interpret_rhs_expr (struct loop *loop, gimple at_stmt,
+ tree type, tree rhs1, enum tree_code code, tree rhs2)
{
- tree res, opnd10, opnd11, chrec10, chrec11;
+ tree res, chrec1, chrec2;
+
+ if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
+ {
+ if (is_gimple_min_invariant (rhs1))
+ return chrec_convert (type, rhs1, at_stmt);
+
+ if (code == SSA_NAME)
+ return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
+ at_stmt);
+
+ if (code == ASSERT_EXPR)
+ {
+ rhs1 = ASSERT_EXPR_VAR (rhs1);
+ return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
+ at_stmt);
+ }
- if (is_gimple_min_invariant (opnd1))
- return chrec_convert (type, opnd1, at_stmt);
+ return chrec_dont_know;
+ }
- switch (TREE_CODE (opnd1))
+ switch (code)
{
case POINTER_PLUS_EXPR:
- opnd10 = TREE_OPERAND (opnd1, 0);
- opnd11 = TREE_OPERAND (opnd1, 1);
- chrec10 = analyze_scalar_evolution (loop, opnd10);
- chrec11 = analyze_scalar_evolution (loop, opnd11);
- chrec10 = chrec_convert (type, chrec10, at_stmt);
- chrec11 = chrec_convert (sizetype, chrec11, at_stmt);
- res = chrec_fold_plus (type, chrec10, chrec11);
+ chrec1 = analyze_scalar_evolution (loop, rhs1);
+ chrec2 = analyze_scalar_evolution (loop, rhs2);
+ chrec1 = chrec_convert (type, chrec1, at_stmt);
+ chrec2 = chrec_convert (sizetype, chrec2, at_stmt);
+ res = chrec_fold_plus (type, chrec1, chrec2);
break;
case PLUS_EXPR:
- opnd10 = TREE_OPERAND (opnd1, 0);
- opnd11 = TREE_OPERAND (opnd1, 1);
- chrec10 = analyze_scalar_evolution (loop, opnd10);
- chrec11 = analyze_scalar_evolution (loop, opnd11);
- chrec10 = chrec_convert (type, chrec10, at_stmt);
- chrec11 = chrec_convert (type, chrec11, at_stmt);
- res = chrec_fold_plus (type, chrec10, chrec11);
+ chrec1 = analyze_scalar_evolution (loop, rhs1);
+ chrec2 = analyze_scalar_evolution (loop, rhs2);
+ chrec1 = chrec_convert (type, chrec1, at_stmt);
+ chrec2 = chrec_convert (type, chrec2, at_stmt);
+ res = chrec_fold_plus (type, chrec1, chrec2);
break;
case MINUS_EXPR:
- opnd10 = TREE_OPERAND (opnd1, 0);
- opnd11 = TREE_OPERAND (opnd1, 1);
- chrec10 = analyze_scalar_evolution (loop, opnd10);
- chrec11 = analyze_scalar_evolution (loop, opnd11);
- chrec10 = chrec_convert (type, chrec10, at_stmt);
- chrec11 = chrec_convert (type, chrec11, at_stmt);
- res = chrec_fold_minus (type, chrec10, chrec11);
+ chrec1 = analyze_scalar_evolution (loop, rhs1);
+ chrec2 = analyze_scalar_evolution (loop, rhs2);
+ chrec1 = chrec_convert (type, chrec1, at_stmt);
+ chrec2 = chrec_convert (type, chrec2, at_stmt);
+ res = chrec_fold_minus (type, chrec1, chrec2);
break;
case NEGATE_EXPR:
- opnd10 = TREE_OPERAND (opnd1, 0);
- chrec10 = analyze_scalar_evolution (loop, opnd10);
- chrec10 = chrec_convert (type, chrec10, at_stmt);
+ chrec1 = analyze_scalar_evolution (loop, rhs1);
+ chrec1 = chrec_convert (type, chrec1, at_stmt);
/* TYPE may be integer, real or complex, so use fold_convert. */
- res = chrec_fold_multiply (type, chrec10,
+ res = chrec_fold_multiply (type, chrec1,
fold_convert (type, integer_minus_one_node));
break;
- case MULT_EXPR:
- opnd10 = TREE_OPERAND (opnd1, 0);
- opnd11 = TREE_OPERAND (opnd1, 1);
- chrec10 = analyze_scalar_evolution (loop, opnd10);
- chrec11 = analyze_scalar_evolution (loop, opnd11);
- chrec10 = chrec_convert (type, chrec10, at_stmt);
- chrec11 = chrec_convert (type, chrec11, at_stmt);
- res = chrec_fold_multiply (type, chrec10, chrec11);
- break;
-
- case SSA_NAME:
- res = chrec_convert (type, analyze_scalar_evolution (loop, opnd1),
- at_stmt);
+ case BIT_NOT_EXPR:
+ /* Handle ~X as -1 - X. */
+ chrec1 = analyze_scalar_evolution (loop, rhs1);
+ chrec1 = chrec_convert (type, chrec1, at_stmt);
+ res = chrec_fold_minus (type,
+ fold_convert (type, integer_minus_one_node),
+ chrec1);
break;
- case ASSERT_EXPR:
- opnd10 = ASSERT_EXPR_VAR (opnd1);
- res = chrec_convert (type, analyze_scalar_evolution (loop, opnd10),
- at_stmt);
+ case MULT_EXPR:
+ chrec1 = analyze_scalar_evolution (loop, rhs1);
+ chrec2 = analyze_scalar_evolution (loop, rhs2);
+ chrec1 = chrec_convert (type, chrec1, at_stmt);
+ chrec2 = chrec_convert (type, chrec2, at_stmt);
+ res = chrec_fold_multiply (type, chrec1, chrec2);
break;
CASE_CONVERT:
- opnd10 = TREE_OPERAND (opnd1, 0);
- chrec10 = analyze_scalar_evolution (loop, opnd10);
- res = chrec_convert (type, chrec10, at_stmt);
+ chrec1 = analyze_scalar_evolution (loop, rhs1);
+ res = chrec_convert (type, chrec1, at_stmt);
break;
default:
return res;
}
+/* Interpret the expression EXPR. */
+
+static tree
+interpret_expr (struct loop *loop, gimple at_stmt, tree expr)
+{
+ enum tree_code code;
+ tree type = TREE_TYPE (expr), op0, op1;
+
+ if (automatically_generated_chrec_p (expr))
+ return expr;
+
+ if (TREE_CODE (expr) == POLYNOMIAL_CHREC)
+ return chrec_dont_know;
+
+ extract_ops_from_tree (expr, &code, &op0, &op1);
+
+ return interpret_rhs_expr (loop, at_stmt, type,
+ op0, code, op1);
+}
+
+/* Interpret the rhs of the assignment STMT. */
+
+static tree
+interpret_gimple_assign (struct loop *loop, gimple stmt)
+{
+ tree type = TREE_TYPE (gimple_assign_lhs (stmt));
+ enum tree_code code = gimple_assign_rhs_code (stmt);
+
+ return interpret_rhs_expr (loop, stmt, type,
+ gimple_assign_rhs1 (stmt), code,
+ gimple_assign_rhs2 (stmt));
+}
+
\f
/* This section contains all the entry points:
static tree
analyze_scalar_evolution_1 (struct loop *loop, tree var, tree res)
{
- tree def, type = TREE_TYPE (var);
+ tree type = TREE_TYPE (var);
+ gimple def;
basic_block bb;
struct loop *def_loop;
return chrec_dont_know;
if (TREE_CODE (var) != SSA_NAME)
- return interpret_rhs_modify_stmt (loop, NULL_TREE, var, type);
+ return interpret_expr (loop, NULL, var);
def = SSA_NAME_DEF_STMT (var);
- bb = bb_for_stmt (def);
+ bb = gimple_bb (def);
def_loop = bb ? bb->loop_father : NULL;
if (bb == NULL
goto set_and_end;
}
- switch (TREE_CODE (def))
+ switch (gimple_code (def))
{
- case GIMPLE_MODIFY_STMT:
- res = interpret_rhs_modify_stmt (loop, def,
- GIMPLE_STMT_OPERAND (def, 1), type);
+ case GIMPLE_ASSIGN:
+ res = interpret_gimple_assign (loop, def);
break;
- case PHI_NODE:
+ case GIMPLE_PHI:
if (loop_phi_node_p (def))
res = interpret_loop_phi (loop, def);
else
res = var;
if (loop == def_loop)
- set_scalar_evolution (var, res);
+ set_scalar_evolution (block_before_loop (loop), var, res);
return res;
}
-/* Entry point for the scalar evolution analyzer.
- Analyzes and returns the scalar evolution of the ssa_name VAR.
- LOOP_NB is the identifier number of the loop in which the variable
- is used.
+/* Analyzes and returns the scalar evolution of the ssa_name VAR in
+ LOOP. LOOP is the loop in which the variable is used.
Example of use: having a pointer VAR to a SSA_NAME node, STMT a
pointer to the statement that uses this variable, in order to
determine the evolution function of the variable, use the following
calls:
- unsigned loop_nb = loop_containing_stmt (stmt)->num;
- tree chrec_with_symbols = analyze_scalar_evolution (loop_nb, var);
+ loop_p loop = loop_containing_stmt (stmt);
+ tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
*/
fprintf (dump_file, ")\n");
}
- res = analyze_scalar_evolution_1 (loop, var, get_scalar_evolution (var));
-
- if (TREE_CODE (var) == SSA_NAME && res == chrec_dont_know)
- res = var;
+ res = get_scalar_evolution (block_before_loop (loop), var);
+ res = analyze_scalar_evolution_1 (loop, var, res);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, ")\n");
}
/* 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).
+ WRTO_LOOP (which should be a superloop of USE_LOOP)
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). */
+ at the moment in order to keep things simple).
+
+ To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
+ example:
+
+ for (i = 0; i < 100; i++) -- loop 1
+ {
+ for (j = 0; j < 100; j++) -- loop 2
+ {
+ k1 = i;
+ k2 = j;
+
+ use2 (k1, k2);
+
+ for (t = 0; t < 100; t++) -- loop 3
+ use3 (k1, k2);
+
+ }
+ use1 (k1, k2);
+ }
+
+ Both k1 and k2 are invariants in loop3, thus
+ analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
+ analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
+
+ As they are invariant, it does not matter whether we consider their
+ usage in loop 3 or loop 2, hence
+ analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
+ analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
+ analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
+ analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
+
+ Similarly for their evolutions with respect to loop 1. The values of K2
+ in the use in loop 2 vary independently on loop 1, thus we cannot express
+ the evolution with respect to loop 1:
+ analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
+ analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
+ analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
+ analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
+
+ The value of k2 in the use in loop 1 is known, though:
+ analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
+ analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
+ */
static tree
analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop,
bool val = false;
tree ev = version, tmp;
+ /* We cannot just do
+
+ tmp = analyze_scalar_evolution (use_loop, version);
+ ev = resolve_mixers (wrto_loop, tmp);
+
+ as resolve_mixers would query the scalar evolution with respect to
+ wrto_loop. For example, in the situation described in the function
+ comment, suppose that wrto_loop = loop1, use_loop = loop3 and
+ version = k2. Then
+
+ analyze_scalar_evolution (use_loop, version) = k2
+
+ and resolve_mixers (loop1, k2) finds that the value of k2 in loop 1
+ is 100, which is a wrong result, since we are interested in the
+ value in loop 3.
+
+ Instead, we need to proceed from use_loop to wrto_loop loop by loop,
+ each time checking that there is no evolution in the inner loop. */
+
if (folded_casts)
*folded_casts = false;
while (1)
}
}
-/* Returns instantiated value for VERSION in CACHE. */
+/* Returns from CACHE the value for VERSION instantiated below
+ INSTANTIATED_BELOW block. */
static tree
-get_instantiated_value (htab_t cache, tree version)
+get_instantiated_value (htab_t cache, basic_block instantiated_below,
+ tree version)
{
struct scev_info_str *info, pattern;
pattern.var = version;
+ pattern.instantiated_below = instantiated_below;
info = (struct scev_info_str *) htab_find (cache, &pattern);
if (info)
return NULL_TREE;
}
-/* Sets instantiated value for VERSION to VAL in CACHE. */
+/* Sets in CACHE the value of VERSION instantiated below basic block
+ INSTANTIATED_BELOW to VAL. */
static void
-set_instantiated_value (htab_t cache, tree version, tree val)
+set_instantiated_value (htab_t cache, basic_block instantiated_below,
+ tree version, tree val)
{
struct scev_info_str *info, pattern;
PTR *slot;
pattern.var = version;
+ pattern.instantiated_below = instantiated_below;
slot = htab_find_slot (cache, &pattern, INSERT);
if (!*slot)
- *slot = new_scev_info_str (version);
+ *slot = new_scev_info_str (instantiated_below, version);
info = (struct scev_info_str *) *slot;
info->chrec = val;
}
{
struct loop *loop;
edge exit;
- tree phi;
+ gimple phi;
+ gimple_stmt_iterator psi;
if (var == NULL_TREE
|| TREE_CODE (var) != SSA_NAME)
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);
+ for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
+ {
+ phi = gsi_stmt (psi);
+ if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
+ return PHI_RESULT (phi);
+ }
return NULL_TREE;
}
-/* Analyze all the parameters of the chrec, between INSTANTIATION_LOOP
+/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
and EVOLUTION_LOOP, that were left under a symbolic form.
CHREC is the scalar evolution to instantiate.
instantiated, and to stop if it exceeds some limit. */
static tree
-instantiate_scev_1 (struct loop *instantiation_loop,
+instantiate_scev_1 (basic_block instantiate_below,
struct loop *evolution_loop, tree chrec,
bool fold_conversions, htab_t cache, int size_expr)
{
switch (TREE_CODE (chrec))
{
case SSA_NAME:
- def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (chrec));
+ def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec));
/* A parameter (or loop invariant and we do not want to include
evolutions in outer loops), nothing to do. */
if (!def_bb
|| loop_depth (def_bb->loop_father) == 0
- || !flow_bb_inside_loop_p (instantiation_loop, def_bb))
+ || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb))
return chrec;
/* We cache the value of instantiated variable to avoid exponential
| a_2 -> {0, +, 1, +, a_2}_1 */
- res = get_instantiated_value (cache, chrec);
+ res = get_instantiated_value (cache, instantiate_below, chrec);
if (res)
return res;
- /* Store the convenient value for chrec in the structure. If it
- is defined outside of the loop, we may just leave it in symbolic
- form, otherwise we need to admit that we do not know its behavior
- inside the loop. */
- res = !flow_bb_inside_loop_p (instantiation_loop, def_bb)
- ? chrec : chrec_dont_know;
- set_instantiated_value (cache, chrec, res);
-
- /* To make things even more complicated, instantiate_scev_1
- calls analyze_scalar_evolution that may call # of iterations
- analysis that may in turn call instantiate_scev_1 again.
- To prevent the infinite recursion, keep also the bitmap of
- ssa names that are being instantiated globally. */
- if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec)))
- return res;
+ res = chrec_dont_know;
+ set_instantiated_value (cache, instantiate_below, chrec, res);
def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
/* If the analysis yields a parametric chrec, instantiate the
result again. */
- bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec));
res = analyze_scalar_evolution (def_loop, chrec);
/* Don't instantiate loop-closed-ssa phi nodes. */
else
res = chrec;
- if (res == NULL_TREE)
+ if (res == NULL_TREE
+ || !dominated_by_p (CDI_DOMINATORS, instantiate_below,
+ gimple_bb (SSA_NAME_DEF_STMT (res))))
res = chrec_dont_know;
}
else if (res != chrec_dont_know)
- res = instantiate_scev_1 (instantiation_loop, evolution_loop, res,
+ res = instantiate_scev_1 (instantiate_below, evolution_loop, res,
fold_conversions, cache, size_expr);
- bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
-
/* Store the correct value to the cache. */
- set_instantiated_value (cache, chrec, res);
+ set_instantiated_value (cache, instantiate_below, chrec, res);
return res;
case POLYNOMIAL_CHREC:
- op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
CHREC_LEFT (chrec), fold_conversions, cache,
size_expr);
if (op0 == chrec_dont_know)
return chrec_dont_know;
- op1 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op1 = instantiate_scev_1 (instantiate_below, evolution_loop,
CHREC_RIGHT (chrec), fold_conversions, cache,
size_expr);
if (op1 == chrec_dont_know)
if (CHREC_LEFT (chrec) != op0
|| CHREC_RIGHT (chrec) != op1)
{
- op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL_TREE);
+ op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL);
chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
}
return chrec;
case POINTER_PLUS_EXPR:
case PLUS_EXPR:
- op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
TREE_OPERAND (chrec, 0), fold_conversions, cache,
size_expr);
if (op0 == chrec_dont_know)
return chrec_dont_know;
- op1 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op1 = instantiate_scev_1 (instantiate_below, evolution_loop,
TREE_OPERAND (chrec, 1), fold_conversions, cache,
size_expr);
if (op1 == chrec_dont_know)
if (TREE_OPERAND (chrec, 0) != op0
|| TREE_OPERAND (chrec, 1) != op1)
{
- op0 = chrec_convert (type, op0, NULL_TREE);
- op1 = chrec_convert_rhs (type, op1, NULL_TREE);
+ op0 = chrec_convert (type, op0, NULL);
+ op1 = chrec_convert_rhs (type, op1, NULL);
chrec = chrec_fold_plus (type, op0, op1);
}
return chrec;
case MINUS_EXPR:
- op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
TREE_OPERAND (chrec, 0), fold_conversions, cache,
size_expr);
if (op0 == chrec_dont_know)
return chrec_dont_know;
- op1 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op1 = instantiate_scev_1 (instantiate_below, evolution_loop,
TREE_OPERAND (chrec, 1),
fold_conversions, cache, size_expr);
if (op1 == chrec_dont_know)
if (TREE_OPERAND (chrec, 0) != op0
|| TREE_OPERAND (chrec, 1) != op1)
{
- op0 = chrec_convert (type, op0, NULL_TREE);
- op1 = chrec_convert (type, op1, NULL_TREE);
+ op0 = chrec_convert (type, op0, NULL);
+ op1 = chrec_convert (type, op1, NULL);
chrec = chrec_fold_minus (type, op0, op1);
}
return chrec;
case MULT_EXPR:
- op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
TREE_OPERAND (chrec, 0),
fold_conversions, cache, size_expr);
if (op0 == chrec_dont_know)
return chrec_dont_know;
- op1 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op1 = instantiate_scev_1 (instantiate_below, evolution_loop,
TREE_OPERAND (chrec, 1),
fold_conversions, cache, size_expr);
if (op1 == chrec_dont_know)
if (TREE_OPERAND (chrec, 0) != op0
|| TREE_OPERAND (chrec, 1) != op1)
{
- op0 = chrec_convert (type, op0, NULL_TREE);
- op1 = chrec_convert (type, op1, NULL_TREE);
+ op0 = chrec_convert (type, op0, NULL);
+ op1 = chrec_convert (type, op1, NULL);
chrec = chrec_fold_multiply (type, op0, op1);
}
return chrec;
CASE_CONVERT:
- op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
TREE_OPERAND (chrec, 0),
fold_conversions, cache, size_expr);
if (op0 == chrec_dont_know)
if (fold_conversions)
return fold_convert (TREE_TYPE (chrec), op0);
- return chrec_convert (TREE_TYPE (chrec), op0, NULL_TREE);
+ return chrec_convert (TREE_TYPE (chrec), op0, NULL);
+
+ case BIT_NOT_EXPR:
+ /* Handle ~X as -1 - X. */
+ op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
+ TREE_OPERAND (chrec, 0),
+ fold_conversions, cache, size_expr);
+ if (op0 == chrec_dont_know)
+ return chrec_dont_know;
+
+ if (TREE_OPERAND (chrec, 0) != op0)
+ {
+ op0 = chrec_convert (type, op0, NULL);
+ chrec = chrec_fold_minus (type,
+ fold_convert (type,
+ integer_minus_one_node),
+ op0);
+ }
+ return chrec;
case SCEV_NOT_KNOWN:
return chrec_dont_know;
break;
}
- gcc_assert (!VL_EXP_CLASS_P (chrec));
+ if (VL_EXP_CLASS_P (chrec))
+ return chrec_dont_know;
+
switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
{
case 3:
- op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
TREE_OPERAND (chrec, 0),
fold_conversions, cache, size_expr);
if (op0 == chrec_dont_know)
return chrec_dont_know;
- op1 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op1 = instantiate_scev_1 (instantiate_below, evolution_loop,
TREE_OPERAND (chrec, 1),
fold_conversions, cache, size_expr);
if (op1 == chrec_dont_know)
return chrec_dont_know;
- op2 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op2 = instantiate_scev_1 (instantiate_below, evolution_loop,
TREE_OPERAND (chrec, 2),
fold_conversions, cache, size_expr);
if (op2 == chrec_dont_know)
TREE_TYPE (chrec), op0, op1, op2);
case 2:
- op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
TREE_OPERAND (chrec, 0),
fold_conversions, cache, size_expr);
if (op0 == chrec_dont_know)
return chrec_dont_know;
- op1 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op1 = instantiate_scev_1 (instantiate_below, evolution_loop,
TREE_OPERAND (chrec, 1),
fold_conversions, cache, size_expr);
if (op1 == chrec_dont_know)
return fold_build2 (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
case 1:
- op0 = instantiate_scev_1 (instantiation_loop, evolution_loop,
+ op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
TREE_OPERAND (chrec, 0),
fold_conversions, cache, size_expr);
if (op0 == chrec_dont_know)
}
/* Analyze all the parameters of the chrec that were left under a
- symbolic form. INSTANTIATION_LOOP is the loop in which symbolic
- names have to be instantiated, and EVOLUTION_LOOP is the loop in
- which the evolution of scalars have to be analyzed. */
+ symbolic form. INSTANTIATE_BELOW is the basic block that stops the
+ recursive instantiation of parameters: a parameter is a variable
+ that is defined in a basic block that dominates INSTANTIATE_BELOW or
+ a function parameter. */
tree
-instantiate_scev (struct loop *instantiation_loop, struct loop *evolution_loop,
+instantiate_scev (basic_block instantiate_below, struct loop *evolution_loop,
tree chrec)
{
tree res;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "(instantiate_scev \n");
- fprintf (dump_file, " (instantiation_loop = %d)\n", instantiation_loop->num);
+ fprintf (dump_file, " (instantiate_below = %d)\n", instantiate_below->index);
fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num);
fprintf (dump_file, " (chrec = ");
print_generic_expr (dump_file, chrec, 0);
fprintf (dump_file, ")\n");
}
- res = instantiate_scev_1 (instantiation_loop, evolution_loop, chrec, false,
+ res = instantiate_scev_1 (instantiate_below, evolution_loop, chrec, false,
cache, 0);
if (dump_file && (dump_flags & TDF_DETAILS))
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_scev_1 (loop, loop, chrec, true, cache, 0);
+ tree ret = instantiate_scev_1 (block_before_loop (loop), loop, chrec, true,
+ cache, 0);
htab_delete (cache);
return ret;
}
from the EXIT_CONDITIONS array. */
static void
-number_of_iterations_for_all_loops (VEC(tree,heap) **exit_conditions)
+number_of_iterations_for_all_loops (VEC(gimple,heap) **exit_conditions)
{
unsigned int i;
unsigned nb_chrec_dont_know_loops = 0;
unsigned nb_static_loops = 0;
- tree cond;
+ gimple cond;
- for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
+ for (i = 0; VEC_iterate (gimple, *exit_conditions, i, cond); i++)
{
tree res = number_of_latch_executions (loop_containing_stmt (cond));
if (chrec_contains_undetermined (res))
index. This allows the parallelization of the loop. */
static void
-analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(tree,heap) **exit_conditions)
+analyze_scalar_evolution_for_all_loop_phi_nodes (VEC(gimple,heap) **exit_conditions)
{
unsigned int i;
struct chrec_stats stats;
- tree cond;
+ gimple cond, phi;
+ gimple_stmt_iterator psi;
reset_chrecs_counters (&stats);
- for (i = 0; VEC_iterate (tree, *exit_conditions, i, cond); i++)
+ for (i = 0; VEC_iterate (gimple, *exit_conditions, i, cond); i++)
{
struct loop *loop;
basic_block bb;
- tree phi, chrec;
+ tree chrec;
loop = loop_containing_stmt (cond);
bb = loop->header;
- for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
- if (is_gimple_reg (PHI_RESULT (phi)))
- {
- chrec = instantiate_parameters
- (loop,
- analyze_scalar_evolution (loop, PHI_RESULT (phi)));
+ for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
+ {
+ phi = gsi_stmt (psi);
+ if (is_gimple_reg (PHI_RESULT (phi)))
+ {
+ chrec = instantiate_parameters
+ (loop,
+ analyze_scalar_evolution (loop, PHI_RESULT (phi)));
- if (dump_file && (dump_flags & TDF_STATS))
- gather_chrec_stats (chrec, &stats);
- }
+ if (dump_file && (dump_flags & TDF_STATS))
+ gather_chrec_stats (chrec, &stats);
+ }
+ }
}
if (dump_file && (dump_flags & TDF_STATS))
del_scev_info,
ggc_calloc,
ggc_free);
- already_instantiated = BITMAP_ALLOC (NULL);
initialize_scalar_evolutions_analyzer ();
}
}
-/* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
- 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). */
+/* Checks whether use of OP in USE_LOOP behaves as a simple affine iv with
+ respect to WRTO_LOOP and returns its base and step in IV if possible
+ (see analyze_scalar_evolution_in_loop for more details on USE_LOOP
+ and WRTO_LOOP). 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). Consequently, adding an
+ induction variable
+
+ for (i = IV->base; ; i += IV->step)
+
+ is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
+ false for the type of the induction variable, or you can prove that i does
+ not wrap by some other argument. Otherwise, this might introduce undefined
+ behavior, and
+
+ for (i = iv->base; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
+
+ must be used instead. */
bool
-simple_iv (struct loop *loop, tree stmt, tree op, affine_iv *iv,
- bool allow_nonconstant_step)
+simple_iv (struct loop *wrto_loop, struct loop *use_loop, tree op,
+ affine_iv *iv, bool allow_nonconstant_step)
{
- basic_block bb = bb_for_stmt (stmt);
tree type, ev;
bool folded_casts;
&& TREE_CODE (type) != POINTER_TYPE)
return false;
- ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op,
+ ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op,
&folded_casts);
- if (chrec_contains_undetermined (ev))
+ if (chrec_contains_undetermined (ev)
+ || chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num))
return false;
- if (tree_does_not_contain_chrecs (ev)
- && !chrec_contains_symbols_defined_in_loop (ev, loop->num))
+ if (tree_does_not_contain_chrecs (ev))
{
iv->base = ev;
iv->step = build_int_cst (TREE_TYPE (ev), 0);
}
if (TREE_CODE (ev) != POLYNOMIAL_CHREC
- || CHREC_VARIABLE (ev) != (unsigned) loop->num)
+ || CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num)
return false;
iv->step = CHREC_RIGHT (ev);
- if (allow_nonconstant_step)
- {
- if (tree_contains_chrecs (iv->step, NULL)
- || chrec_contains_symbols_defined_in_loop (iv->step, loop->num))
- return false;
- }
- else if (TREE_CODE (iv->step) != INTEGER_CST)
+ if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST)
+ || tree_contains_chrecs (iv->step, NULL))
return false;
iv->base = CHREC_LEFT (ev);
- if (tree_contains_chrecs (iv->base, NULL)
- || chrec_contains_symbols_defined_in_loop (iv->base, loop->num))
+ if (tree_contains_chrecs (iv->base, NULL))
return false;
iv->no_overflow = !folded_casts && TYPE_OVERFLOW_UNDEFINED (type);
void
scev_analysis (void)
{
- VEC(tree,heap) *exit_conditions;
+ VEC(gimple,heap) *exit_conditions;
- exit_conditions = VEC_alloc (tree, heap, 37);
+ exit_conditions = VEC_alloc (gimple, heap, 37);
select_loops_exit_conditions (&exit_conditions);
if (dump_file && (dump_flags & TDF_STATS))
analyze_scalar_evolution_for_all_loop_phi_nodes (&exit_conditions);
number_of_iterations_for_all_loops (&exit_conditions);
- VEC_free (tree, heap, exit_conditions);
+ VEC_free (gimple, heap, exit_conditions);
}
/* Finalize the scalar evolution analysis. */
if (!scalar_evolution_info)
return;
htab_delete (scalar_evolution_info);
- BITMAP_FREE (already_instantiated);
scalar_evolution_info = NULL;
}
+/* Returns true if the expression EXPR is considered to be too expensive
+ for scev_const_prop. */
+
+bool
+expression_expensive_p (tree expr)
+{
+ enum tree_code code;
+
+ if (is_gimple_val (expr))
+ return false;
+
+ code = TREE_CODE (expr);
+ if (code == TRUNC_DIV_EXPR
+ || code == CEIL_DIV_EXPR
+ || code == FLOOR_DIV_EXPR
+ || code == ROUND_DIV_EXPR
+ || code == TRUNC_MOD_EXPR
+ || code == CEIL_MOD_EXPR
+ || code == FLOOR_MOD_EXPR
+ || code == ROUND_MOD_EXPR
+ || code == EXACT_DIV_EXPR)
+ {
+ /* Division by power of two is usually cheap, so we allow it.
+ Forbid anything else. */
+ if (!integer_pow2p (TREE_OPERAND (expr, 1)))
+ return true;
+ }
+
+ switch (TREE_CODE_CLASS (code))
+ {
+ case tcc_binary:
+ case tcc_comparison:
+ if (expression_expensive_p (TREE_OPERAND (expr, 1)))
+ return true;
+
+ /* Fallthru. */
+ case tcc_unary:
+ return expression_expensive_p (TREE_OPERAND (expr, 0));
+
+ default:
+ return true;
+ }
+}
+
/* 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.
scev_const_prop (void)
{
basic_block bb;
- tree name, phi, next_phi, type, ev;
+ tree name, type, ev;
+ gimple phi, ass;
struct loop *loop, *ex_loop;
bitmap ssa_names_to_remove = NULL;
unsigned i;
loop_iterator li;
+ gimple_stmt_iterator psi;
if (number_of_loops () <= 1)
return 0;
{
loop = bb->loop_father;
- for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
{
+ phi = gsi_stmt (psi);
name = PHI_RESULT (phi);
if (!is_gimple_reg (name))
EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, 0, i, bi)
{
+ gimple_stmt_iterator psi;
name = ssa_name (i);
phi = SSA_NAME_DEF_STMT (name);
- gcc_assert (TREE_CODE (phi) == PHI_NODE);
- remove_phi_node (phi, NULL, true);
+ gcc_assert (gimple_code (phi) == GIMPLE_PHI);
+ psi = gsi_for_stmt (phi);
+ remove_phi_node (&psi, true);
}
BITMAP_FREE (ssa_names_to_remove);
FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
{
edge exit;
- tree def, rslt, ass, niter;
- block_stmt_iterator bsi;
+ tree def, rslt, niter;
+ gimple_stmt_iterator bsi;
/* If we do not know exact number of iterations of the loop, we cannot
replace the final value. */
continue;
niter = number_of_latch_executions (loop);
- /* We used to check here whether the computation of NITER is expensive,
- and avoided final value elimination if that is the case. The problem
- is that it is hard to evaluate whether the expression is too
- expensive, as we do not know what optimization opportunities the
- elimination of the final value may reveal. Therefore, we now
- eliminate the final values of induction variables unconditionally. */
if (niter == chrec_dont_know)
continue;
/* Ensure that it is possible to insert new statements somewhere. */
if (!single_pred_p (exit->dest))
split_loop_exit_edge (exit);
- bsi = bsi_after_labels (exit->dest);
+ bsi = gsi_after_labels (exit->dest);
ex_loop = superloop_at_depth (loop,
loop_depth (exit->dest->loop_father) + 1);
- for (phi = phi_nodes (exit->dest); phi; phi = next_phi)
+ for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); )
{
- next_phi = PHI_CHAIN (phi);
+ phi = gsi_stmt (psi);
rslt = PHI_RESULT (phi);
def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
if (!is_gimple_reg (def))
- continue;
+ {
+ gsi_next (&psi);
+ continue;
+ }
if (!POINTER_TYPE_P (TREE_TYPE (def))
&& !INTEGRAL_TYPE_P (TREE_TYPE (def)))
- continue;
+ {
+ gsi_next (&psi);
+ continue;
+ }
def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL);
def = compute_overall_effect_of_inner_loop (ex_loop, def);
/* 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;
+ || contains_abnormal_ssa_name_p (def)
+ /* Do not emit expensive expressions. The rationale is that
+ when someone writes a code like
+
+ while (n > 45) n -= 45;
+
+ he probably knows that n is not large, and does not want it
+ to be turned into n %= 45. */
+ || expression_expensive_p (def))
+ {
+ gsi_next (&psi);
+ continue;
+ }
/* Eliminate the PHI node and replace it by a computation outside
the loop. */
def = unshare_expr (def);
- remove_phi_node (phi, NULL_TREE, false);
-
- ass = build_gimple_modify_stmt (rslt, NULL_TREE);
- SSA_NAME_DEF_STMT (rslt) = ass;
- {
- block_stmt_iterator dest = bsi;
- bsi_insert_before (&dest, ass, BSI_NEW_STMT);
- def = force_gimple_operand_bsi (&dest, def, false, NULL_TREE,
- true, BSI_SAME_STMT);
- }
- GIMPLE_STMT_OPERAND (ass, 1) = def;
- update_stmt (ass);
+ remove_phi_node (&psi, false);
+
+ def = force_gimple_operand_gsi (&bsi, def, false, NULL_TREE,
+ true, GSI_SAME_STMT);
+ ass = gimple_build_assign (rslt, def);
+ gsi_insert_before (&bsi, ass, GSI_SAME_STMT);
}
}
return 0;
OSDN Git Service
