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);
}
follow_ssa_edge_expr (struct loop *loop, gimple at_stmt, tree expr,
gimple halting_phi, tree *evolution_of_loop, int limit)
{
- t_bool res = t_false;
- tree rhs0, rhs1;
- tree type = TREE_TYPE (expr);
- enum tree_code code;
-
+ 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 MINUS_EXPR,
- an ASSERT_EXPR,
- other cases are not yet handled. */
- code = TREE_CODE (expr);
+
switch (code)
{
- case NOP_EXPR:
+ 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);
/* 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);
- STRIP_TYPE_NOPS (rhs0);
- STRIP_TYPE_NOPS (rhs1);
- return follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,
- halting_phi, evolution_of_loop, limit);
+ 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. */
- tree op0 = ASSERT_EXPR_VAR (expr);
- 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;
- }
-
+ /* 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_ssa_edge_in_rhs (struct loop *loop, gimple stmt,
gimple halting_phi, tree *evolution_of_loop, int limit)
{
- tree type = TREE_TYPE (gimple_assign_lhs (stmt));
enum tree_code code = gimple_assign_rhs_code (stmt);
+ tree type = gimple_expr_type (stmt), rhs1, rhs2;
+ t_bool res;
- switch (get_gimple_rhs_class (code))
+ switch (code)
{
- case GIMPLE_BINARY_RHS:
- return follow_ssa_edge_binary (loop, stmt, type,
- gimple_assign_rhs1 (stmt), code,
- gimple_assign_rhs2 (stmt),
- halting_phi, evolution_of_loop, limit);
- case GIMPLE_SINGLE_RHS:
- return follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
- halting_phi, evolution_of_loop, limit);
- case GIMPLE_UNARY_RHS:
- if (code == NOP_EXPR)
- {
- /* This assignment is under the form "a_1 = (cast) rhs. */
- t_bool res
- = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
+ 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);
- *evolution_of_loop = chrec_convert (type, *evolution_of_loop, stmt);
- return res;
- }
- /* FALLTHRU */
+ break;
default:
- return t_false;
+ 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. */
*evolution_of_loop = evolution_of_branch;
- /* If the phi node is just a copy, do not increase the limit. */
n = gimple_phi_num_args (condition_phi);
- if (n > 1)
- limit++;
-
for (i = 1; i < n; i++)
{
/* Quickly give up when the evolution of one of the branches is
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;
bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
if (!flow_bb_inside_loop_p (loop, bb))
continue;
-
+
if (TREE_CODE (arg) == SSA_NAME)
{
+ bool val = false;
+
ssa_chain = SSA_NAME_DEF_STMT (arg);
/* 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, 0);
+
+ /* If ev_fn has no evolution in the inner loop, and the
+ init_cond is not equal to ev_fn, then we have an
+ ambiguity between two possible values, as we cannot know
+ the number of iterations at this point. */
+ if (TREE_CODE (ev_fn) != POLYNOMIAL_CHREC
+ && no_evolution_in_loop_p (ev_fn, loop->num, &val) && val
+ && !operand_equal_p (init_cond, ev_fn, 0))
+ ev_fn = chrec_dont_know;
}
else
res = t_false;
-
+
/* When it is impossible to go back on the same
loop_phi_node by following the ssa edges, the
evolution is represented by a peeled chrec, i.e. the
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);
*/
return NULL_TREE;
}
+static tree instantiate_scev_1 (basic_block, struct loop *, tree, bool,
+ htab_t, int);
+
+/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
+ and EVOLUTION_LOOP, that were left under a symbolic form.
+
+ CHREC is an SSA_NAME to be instantiated.
+
+ CACHE is the cache of already instantiated values.
+
+ FOLD_CONVERSIONS should be set to true when the conversions that
+ may wrap in signed/pointer type are folded, as long as the value of
+ the chrec is preserved.
+
+ SIZE_EXPR is used for computing the size of the expression to be
+ instantiated, and to stop if it exceeds some limit. */
+
+static tree
+instantiate_scev_name (basic_block instantiate_below,
+ struct loop *evolution_loop, tree chrec,
+ bool fold_conversions, htab_t cache, int size_expr)
+{
+ tree res;
+ struct loop *def_loop;
+ basic_block 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
+ || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb))
+ return chrec;
+
+ /* We cache the value of instantiated variable to avoid exponential
+ time complexity due to reevaluations. We also store the convenient
+ value in the cache in order to prevent infinite recursion -- we do
+ not want to instantiate the SSA_NAME if it is in a mixer
+ structure. This is used for avoiding the instantiation of
+ recursively defined functions, such as:
+
+ | a_2 -> {0, +, 1, +, a_2}_1 */
+
+ res = get_instantiated_value (cache, instantiate_below, chrec);
+ if (res)
+ 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. */
+ res = analyze_scalar_evolution (def_loop, chrec);
+
+ /* Don't instantiate loop-closed-ssa phi nodes. */
+ if (TREE_CODE (res) == SSA_NAME
+ && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL
+ || (loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
+ > loop_depth (def_loop))))
+ {
+ if (res == chrec)
+ res = loop_closed_phi_def (chrec);
+ else
+ res = chrec;
+
+ 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 (instantiate_below, evolution_loop, res,
+ fold_conversions, cache, size_expr);
+
+ /* Store the correct value to the cache. */
+ set_instantiated_value (cache, instantiate_below, chrec, res);
+ return res;
+
+}
+
+/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
+ and EVOLUTION_LOOP, that were left under a symbolic form.
+
+ CHREC is a binary expression to be instantiated.
+
+ CACHE is the cache of already instantiated values.
+
+ FOLD_CONVERSIONS should be set to true when the conversions that
+ may wrap in signed/pointer type are folded, as long as the value of
+ the chrec is preserved.
+
+ SIZE_EXPR is used for computing the size of the expression to be
+ instantiated, and to stop if it exceeds some limit. */
+
+static tree
+instantiate_scev_binary (basic_block instantiate_below,
+ struct loop *evolution_loop, tree chrec,
+ bool fold_conversions, htab_t cache, int size_expr)
+{
+ tree op1;
+ tree 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 (instantiate_below, evolution_loop,
+ TREE_OPERAND (chrec, 1), fold_conversions, cache,
+ size_expr);
+ if (op1 == chrec_dont_know)
+ return chrec_dont_know;
+
+ if (TREE_OPERAND (chrec, 0) != op0
+ || TREE_OPERAND (chrec, 1) != op1)
+ {
+ tree type = chrec_type (chrec);
+
+ op0 = chrec_convert (type, op0, NULL);
+ op1 = chrec_convert_rhs (type, op1, NULL);
+
+ switch (TREE_CODE (chrec))
+ {
+ case POINTER_PLUS_EXPR:
+ case PLUS_EXPR:
+ return chrec_fold_plus (type, op0, op1);
+
+ case MINUS_EXPR:
+ return chrec_fold_minus (type, op0, op1);
+
+ case MULT_EXPR:
+ return chrec_fold_multiply (type, op0, op1);
+
+ default:
+ gcc_unreachable ();
+ }
+ }
+
+ return chrec;
+}
+
/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
and EVOLUTION_LOOP, that were left under a symbolic form.
struct loop *evolution_loop, tree chrec,
bool fold_conversions, htab_t cache, int size_expr)
{
- tree res, op0, op1, op2;
- basic_block def_bb;
- struct loop *def_loop;
+ tree op0, op1, op2;
tree type = chrec_type (chrec);
/* Give up if the expression is larger than the MAX that we allow. */
switch (TREE_CODE (chrec))
{
case SSA_NAME:
- 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
- || dominated_by_p (CDI_DOMINATORS, instantiate_below, def_bb))
- return chrec;
-
- /* We cache the value of instantiated variable to avoid exponential
- time complexity due to reevaluations. We also store the convenient
- value in the cache in order to prevent infinite recursion -- we do
- not want to instantiate the SSA_NAME if it is in a mixer
- structure. This is used for avoiding the instantiation of
- recursively defined functions, such as:
-
- | a_2 -> {0, +, 1, +, a_2}_1 */
-
- res = get_instantiated_value (cache, instantiate_below, chrec);
- if (res)
- 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. */
- res = analyze_scalar_evolution (def_loop, chrec);
-
- /* Don't instantiate loop-closed-ssa phi nodes. */
- if (TREE_CODE (res) == SSA_NAME
- && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL
- || (loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
- > loop_depth (def_loop))))
- {
- if (res == chrec)
- res = loop_closed_phi_def (chrec);
- else
- res = chrec;
-
- if (res == NULL_TREE)
- res = chrec_dont_know;
- }
-
- else if (res != chrec_dont_know)
- res = instantiate_scev_1 (instantiate_below, evolution_loop, res,
- fold_conversions, cache, size_expr);
-
- /* Store the correct value to the cache. */
- set_instantiated_value (cache, instantiate_below, chrec, res);
- return res;
+ return instantiate_scev_name (instantiate_below, evolution_loop, chrec,
+ fold_conversions, cache, size_expr);
case POLYNOMIAL_CHREC:
op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
case POINTER_PLUS_EXPR:
case PLUS_EXPR:
- 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 (instantiate_below, evolution_loop,
- TREE_OPERAND (chrec, 1), fold_conversions, cache,
- size_expr);
- if (op1 == chrec_dont_know)
- return chrec_dont_know;
-
- if (TREE_OPERAND (chrec, 0) != op0
- || TREE_OPERAND (chrec, 1) != op1)
- {
- 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 (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 (instantiate_below, evolution_loop,
- TREE_OPERAND (chrec, 1),
- fold_conversions, cache, size_expr);
- if (op1 == chrec_dont_know)
- return chrec_dont_know;
-
- if (TREE_OPERAND (chrec, 0) != op0
- || TREE_OPERAND (chrec, 1) != op1)
- {
- 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 (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 (instantiate_below, evolution_loop,
- TREE_OPERAND (chrec, 1),
- fold_conversions, cache, size_expr);
- if (op1 == chrec_dont_know)
- return chrec_dont_know;
-
- if (TREE_OPERAND (chrec, 0) != op0
- || TREE_OPERAND (chrec, 1) != op1)
- {
- op0 = chrec_convert (type, op0, NULL);
- op1 = chrec_convert (type, op1, NULL);
- chrec = chrec_fold_multiply (type, op0, op1);
- }
- return chrec;
+ return instantiate_scev_binary (instantiate_below, evolution_loop, chrec,
+ fold_conversions, cache, size_expr);
CASE_CONVERT:
op0 = instantiate_scev_1 (instantiate_below, evolution_loop,
case SCEV_KNOWN:
return chrec_known;
-
+
default:
break;
}