@@ -581,40 +581,6 @@ get_scalar_evolution (basic_block instantiated_below, tree scalar)
/* Depth first search algorithm. */
-enum t_bool {
- t_false,
- t_true,
- t_dont_know
-};
-
-class scev_dfs
-{
-public:
- scev_dfs (class loop *loop_, gphi *phi_, tree init_cond_)
- : loop (loop_), loop_phi_node (phi_), init_cond (init_cond_) {}
- t_bool get_ev (tree *, tree);
-
-private:
- t_bool follow_ssa_edge_expr (gimple *, tree, tree *, int);
- t_bool follow_ssa_edge_binary (gimple *at_stmt,
- tree type, tree rhs0, enum tree_code code,
- tree rhs1, tree *evolution_of_loop, int limit);
- t_bool follow_ssa_edge_in_condition_phi_branch (int i,
- gphi *condition_phi,
- tree *evolution_of_branch,
- tree init_cond, int limit);
- t_bool follow_ssa_edge_in_condition_phi (gphi *condition_phi,
- tree *evolution_of_loop, int limit);
- t_bool follow_ssa_edge_inner_loop_phi (gphi *loop_phi_node,
- tree *evolution_of_loop, int limit);
- tree add_to_evolution (tree chrec_before, tree to_add, gimple *at_stmt);
- tree add_to_evolution_1 (tree chrec_before, tree to_add, gimple *at_stmt);
-
- class loop *loop;
- gphi *loop_phi_node;
- tree init_cond;
-};
-
t_bool
scev_dfs::get_ev (tree *ev_fn, tree arg)
{
@@ -622,6 +588,18 @@ scev_dfs::get_ev (tree *ev_fn, tree arg)
return follow_ssa_edge_expr (loop_phi_node, arg, ev_fn, 0);
}
+/* Alternative form that takes any assign stmt. The stmt is explored until any
+ phi node is found, which is explored normally for a evolution. The evolution
+ between the stmt and phi is added to the left of the evolution. */
+t_bool
+scev_dfs::get_ev (tree *ev_fn, tree arg, gimple *stmt)
+{
+ gcc_assert (loop_phi_node == NULL);
+ gcc_assert (init_cond == NULL);
+ *ev_fn = chrec_dont_know;
+ return follow_ssa_edge_expr (stmt, arg, ev_fn, 0);
+}
+
/* Helper function for add_to_evolution. Returns the evolution
function for an assignment of the form "a = b + c", where "a" and
"b" are on the strongly connected component. CHREC_BEFORE is the
@@ -639,12 +617,68 @@ scev_dfs::add_to_evolution_1 (tree chrec_before, tree to_add, gimple *at_stmt)
unsigned loop_nb = loop->num;
class loop *chloop;
+ /* Otherwise, add it to the base. */
+ if (!loop_phi_node)
+ {
+ switch (TREE_CODE (chrec_before))
+ {
+ case POLYNOMIAL_CHREC:
+ {
+ chloop = get_chrec_loop (chrec_before);
+ gcc_assert (chloop == loop);
+ unsigned var;
+
+ type = chrec_type (chrec_before);
+
+ var = CHREC_VARIABLE (chrec_before);
+ left = CHREC_LEFT (chrec_before);
+ right = CHREC_RIGHT (chrec_before);
+
+ if (POINTER_TYPE_P (TREE_TYPE (to_add)))
+ {
+ /* Pointers should not be added to pointers. */
+ gcc_assert (!POINTER_TYPE_P (type));
+ type = TREE_TYPE (to_add);
+
+ tree step = convert_to_ptrofftype (left);
+
+ left = to_add;
+ to_add = step;
+
+ right = chrec_convert (sizetype, right, at_stmt);
+ }
+
+ left = chrec_convert (type, left, at_stmt);
+ to_add = chrec_convert_rhs (type, to_add, at_stmt);
+ left = chrec_fold_plus (chrec_type (left), left, to_add);
+
+ /* When we have an evolution in a non-wrapping type and
+ in the process of accumulating CHREC_RIGHT there was
+ overflow this indicates in the association that happened
+ in building the CHREC clearly involved UB. Avoid this.
+ In building a CHREC we basically turn (a + INCR1) + INCR2
+ into a + (INCR1 + INCR2) which is not always valid.
+ Note this check only catches few invalid cases. */
+ if ((INTEGRAL_TYPE_P (type) && !TYPE_OVERFLOW_WRAPS (type))
+ && TREE_CODE (left) == INTEGER_CST && TREE_OVERFLOW (left))
+ return chrec_dont_know;
+
+ /* NOTE: This allow loop variant vars on the LEFT of the chrec.
+ This will need to be dealt with by the consumer. */
+ return build_polynomial_chrec (var, left, right, true);
+ }
+
+ default:
+ return chrec_dont_know;
+ }
+ }
+
+ /* If we are in a loop phi node, then add this to the evolution. */
switch (TREE_CODE (chrec_before))
{
case POLYNOMIAL_CHREC:
chloop = get_chrec_loop (chrec_before);
- if (chloop == loop
- || flow_loop_nested_p (chloop, loop))
+ if (chloop == loop || flow_loop_nested_p (chloop, loop))
{
unsigned var;
@@ -655,9 +689,8 @@ scev_dfs::add_to_evolution_1 (tree chrec_before, tree to_add, gimple *at_stmt)
{
var = loop_nb;
left = chrec_before;
- right = SCALAR_FLOAT_TYPE_P (type)
- ? build_real (type, dconst0)
- : build_int_cst (type, 0);
+ right = SCALAR_FLOAT_TYPE_P (type) ? build_real (type, dconst0)
+ : build_int_cst (type, 0);
}
else
{
@@ -676,9 +709,8 @@ scev_dfs::add_to_evolution_1 (tree chrec_before, tree to_add, gimple *at_stmt)
In building a CHREC we basically turn (a + INCR1) + INCR2
into a + (INCR1 + INCR2) which is not always valid.
Note this check only catches few invalid cases. */
- if ((INTEGRAL_TYPE_P (type) && ! TYPE_OVERFLOW_WRAPS (type))
- && TREE_CODE (right) == INTEGER_CST
- && TREE_OVERFLOW (right))
+ if ((INTEGRAL_TYPE_P (type) && !TYPE_OVERFLOW_WRAPS (type))
+ && TREE_CODE (right) == INTEGER_CST && TREE_OVERFLOW (right))
return chrec_dont_know;
return build_polynomial_chrec (var, left, right);
}
@@ -687,12 +719,12 @@ scev_dfs::add_to_evolution_1 (tree chrec_before, tree to_add, gimple *at_stmt)
gcc_assert (flow_loop_nested_p (loop, chloop));
/* Search the evolution in LOOP_NB. */
- left = add_to_evolution_1 (CHREC_LEFT (chrec_before),
- to_add, at_stmt);
+ left
+ = add_to_evolution_1 (CHREC_LEFT (chrec_before), to_add, at_stmt);
right = CHREC_RIGHT (chrec_before);
right = chrec_convert_rhs (chrec_type (left), right, at_stmt);
- return build_polynomial_chrec (CHREC_VARIABLE (chrec_before),
- left, right);
+ return build_polynomial_chrec (CHREC_VARIABLE (chrec_before), left,
+ right, true);
}
default:
@@ -849,16 +881,24 @@ scev_dfs::add_to_evolution_1 (tree chrec_before, tree to_add, gimple *at_stmt)
| a -> {inita, +, 2 + initb, +, 1}_1
+ If TYPE is not NULL, the to_add is converted to the required type in order
+ to be added to a chrec of type TYPE.
*/
tree
-scev_dfs::add_to_evolution (tree chrec_before, tree to_add, gimple *at_stmt)
+scev_dfs::add_to_evolution (tree chrec_before, tree type, tree to_add,
+ gimple *at_stmt)
{
tree res = NULL_TREE;
if (to_add == NULL_TREE)
return chrec_before;
+ if (!loop_phi_node && POINTER_TYPE_P (TREE_TYPE (to_add)))
+ chrec_before = chrec_convert_rhs (type, chrec_before, at_stmt);
+ else
+ chrec_before = chrec_convert (type, chrec_before, at_stmt);
+
/* TO_ADD is either a scalar, or a parameter. TO_ADD is not
instantiated at this point. */
if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
@@ -888,7 +928,6 @@ scev_dfs::add_to_evolution (tree chrec_before, tree to_add, gimple *at_stmt)
return res;
}
-
/* Follow the ssa edge into the binary expression RHS0 CODE RHS1.
Return true if the strongly connected component has been found. */
@@ -919,16 +958,15 @@ scev_dfs::follow_ssa_edge_binary (gimple *at_stmt, tree type, tree rhs0,
evol = *evolution_of_loop;
res = follow_ssa_edge_expr (at_stmt, rhs0, &evol, limit);
if (res == t_true)
- *evolution_of_loop = add_to_evolution
- (chrec_convert (type, evol, at_stmt), rhs1, at_stmt);
+ *evolution_of_loop = add_to_evolution (evol, type, rhs1,
+ at_stmt);
else if (res == t_false)
{
res = follow_ssa_edge_expr
(at_stmt, rhs1, evolution_of_loop, limit);
if (res == t_true)
- *evolution_of_loop = add_to_evolution
- (chrec_convert (type, *evolution_of_loop, at_stmt),
- rhs0, at_stmt);
+ *evolution_of_loop = add_to_evolution (*evolution_of_loop,
+ type, rhs0, at_stmt);
}
}
@@ -942,9 +980,8 @@ scev_dfs::follow_ssa_edge_binary (gimple *at_stmt, tree type, tree rhs0,
"a = ... + c". */
res = follow_ssa_edge_expr (at_stmt, rhs1, evolution_of_loop, limit);
if (res == t_true)
- *evolution_of_loop = add_to_evolution
- (chrec_convert (type, *evolution_of_loop, at_stmt),
- rhs0, at_stmt);
+ *evolution_of_loop
+ = add_to_evolution (*evolution_of_loop, type, rhs0, at_stmt);
}
else
@@ -1153,12 +1190,46 @@ scev_dfs::follow_ssa_edge_expr (gimple *at_stmt, tree expr,
return t_true;
}
+ class loop *def_loop = loop_containing_stmt (def);
/* Otherwise, the evolution of the HALTING_PHI depends
on the evolution of another loop-phi-node, i.e. the
evolution function is a higher degree polynomial. */
- class loop *def_loop = loop_containing_stmt (def);
if (def_loop == loop)
- return t_false;
+ {
+ /* If we are in a situation where halting phi is defined and this
+ is not it, then we should abort. */
+ if (halting_phi)
+ return t_false;
+
+ /* Otherwise, we should see if halting phi has a valid evolution.
+ and then base our evolution off that. */
+ loop_phi_node = phi;
+ init_cond = analyze_initial_condition (phi);
+
+ int i, n = gimple_phi_num_args (phi);
+ for (i = 0; i < n; i++)
+ {
+ tree arg = PHI_ARG_DEF (phi, i);
+
+ /* Select the edges that enter the loop body. */
+ basic_block bb = gimple_phi_arg_edge (phi, i)->src;
+ if (!flow_bb_inside_loop_p (loop, bb))
+ continue;
+
+ /* This phi defines an IV in our loop that we append to. */
+ t_bool res = follow_ssa_edge_expr (phi, arg,
+ evolution_of_loop, limit);
+ if (res == t_true)
+ {
+ loop_phi_node = NULL;
+ init_cond = NULL;
+ return t_true;
+ }
+ }
+ init_cond = NULL;
+ loop_phi_node = NULL;
+ return t_false;
+ }
/* Inner loop. */
if (flow_loop_nested_p (loop, def_loop))
@@ -1258,9 +1329,8 @@ scev_dfs::follow_ssa_edge_expr (gimple *at_stmt, tree expr,
t_bool res = follow_ssa_edge_expr (at_stmt, rhs0,
evolution_of_loop, limit);
if (res == t_true)
- *evolution_of_loop = add_to_evolution
- (chrec_convert (type, *evolution_of_loop, at_stmt),
- rhs1, at_stmt);
+ *evolution_of_loop
+ = add_to_evolution (*evolution_of_loop, type, rhs1, at_stmt);
return res;
}
/* Else search for the SCC in both rhs0 and rhs1. */
@@ -1289,10 +1359,8 @@ scev_dfs::follow_ssa_edge_expr (gimple *at_stmt, tree expr,
tree to_add = chrec_convert_rhs (utype, rhs1);
to_add = chrec_fold_multiply (utype, to_add,
build_int_cst_type (utype, -1));
- *evolution_of_loop
- = chrec_convert (utype, *evolution_of_loop, at_stmt);
*evolution_of_loop = add_to_evolution (*evolution_of_loop,
- to_add, at_stmt);
+ utype, to_add, at_stmt);
*evolution_of_loop
= chrec_convert (type, *evolution_of_loop, at_stmt);
}
@@ -1301,9 +1369,7 @@ scev_dfs::follow_ssa_edge_expr (gimple *at_stmt, tree expr,
tree to_add = chrec_fold_multiply (type, rhs1,
build_minus_one_cst (type));
*evolution_of_loop
- = add_to_evolution (chrec_convert (type, *evolution_of_loop,
- at_stmt),
- to_add, at_stmt);
+ = add_to_evolution (*evolution_of_loop, type, to_add, at_stmt);
}
return res;
}
@@ -1598,7 +1664,7 @@ follow_copies_to_constant (tree var)
This analyzer does not analyze the evolution outside the current
loop, and leaves this task to the on-demand tree reconstructor. */
-static tree
+tree
analyze_initial_condition (gphi *loop_phi_node)
{
int i, n;
@@ -74,4 +74,47 @@ get_chrec_loop (const_tree chrec)
return get_loop (cfun, CHREC_VARIABLE (chrec));
}
+/* Depth first search algorithm. */
+
+tree analyze_initial_condition (gphi *);
+
+enum t_bool {
+ t_false,
+ t_true,
+ t_dont_know
+};
+
+/* If phi is NULL, then this is just a statement, and we will need to find
+ a relevant phi in the loop, and it's evolution from that. */
+class scev_dfs
+{
+public:
+ scev_dfs (class loop *loop_, gphi *phi_, tree init_cond_)
+ : loop (loop_), loop_phi_node (phi_), init_cond (init_cond_) {}
+ t_bool get_ev (tree *, tree);
+ t_bool get_ev (tree *ev_fn, tree arg, gimple *stmt);
+
+private:
+ t_bool follow_ssa_edge_expr (gimple *, tree, tree *, int);
+ t_bool follow_ssa_edge_binary (gimple *at_stmt,
+ tree type, tree rhs0, enum tree_code code,
+ tree rhs1, tree *evolution_of_loop, int limit);
+ t_bool follow_ssa_edge_in_condition_phi_branch (int i,
+ gphi *condition_phi,
+ tree *evolution_of_branch,
+ tree init_cond, int limit);
+ t_bool follow_ssa_edge_in_condition_phi (gphi *condition_phi,
+ tree *evolution_of_loop, int limit);
+ t_bool follow_ssa_edge_inner_loop_phi (gphi *loop_phi_node,
+ tree *evolution_of_loop, int limit);
+ tree add_to_evolution (tree, tree, tree, gimple *);
+ tree add_to_evolution_1 (tree, tree, gimple *);
+
+ tree add_to_base (tree chrec_before, tree to_add, gimple *at_stmt);
+
+ class loop *loop;
+ gphi *loop_phi_node;
+ tree init_cond;
+};
+
#endif /* GCC_TREE_SCALAR_EVOLUTION_H */