===================================================================
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-ivopts" } */
+
+struct header {
+ unsigned long size;
+ struct header **ptr;
+};
+
+extern unsigned long top;
+
+int foo (struct header *start, int size)
+{
+ struct header *hd = start;
+ top = 0;
+ while (hd != 0 && top+1 < size)
+ {
+ ++top;
+ hd = (hd->ptr)[4];
+ }
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump "iv2tmp.* = .* + \[0-9\]*" "ivopts" } } */
+/* { dg-final { cleanup-tree-dump "ivopts" } } */
===================================================================
@@ -56,6 +56,24 @@ along with GCC; see the file COPYING3. If not see
4) The trees are transformed to use the new variables, the dead code is
removed.
+ Induction variable is possibly used outside of loop. The algorithm
+ handles outside iv use like:
+ -- Marks iv use outside of loop by recording the corresponding exit
+ edge along which the iv is used. If an induction variable is
+ used both inside and outside of loop, outside use will be ignored,
+ as if it is escalated into inside one.
+ -- Computes the use cost against location of the end of source block
+ of the exit edge, and amortize the cost against loop iteration
+ number.
+ -- Inserts computation of outside iv use along the exit edge, rather
+ than in basic block of current loop.
+ TODO: For degenerable phi node with identical arguments, if computations
+ of arguments along each exit edge are identical, the algorithm inserts
+ duplicate gimples for each phi argument. In this case, only one version
+ of computation should be inserted at the beginning of the basic block.
+ Unfortunately, it's hard to know whether the computations are identical
+ before acutally rewrting the uses.
+
All of this is done loop by loop. Doing it globally is theoretically
possible, it might give a better performance and it might enable us
to decide costs more precisely, but getting all the interactions right
@@ -125,6 +143,19 @@ avg_loop_niter (struct loop *loop)
return niter;
}
+/* The types used by the induction variable optimizations. */
+
+typedef struct iv_use *iv_use_p;
+typedef struct iv_cand *iv_cand_p;
+
+/* Indicate what kind of use recorded for struct iv. */
+enum iv_use_location
+{
+ NONE_LOC, /* iv has no use for it. */
+ OUTSIDE_LOOP, /* iv has outside use for it. */
+ INSIDE_LOOP /* iv has inside use for it. */
+};
+
/* Representation of the induction variable. */
struct iv
{
@@ -132,9 +163,12 @@ struct iv
tree base_object; /* A memory object to that the induction variable points. */
tree step; /* Step of the iv (constant only). */
tree ssa_name; /* The ssa name with the value. */
+ iv_use_p inside_use; /* The id of inside loop use. */
+ vec<iv_use_p> *outside_uses_vec;
+ /* The pointers to outside loop uses. */
+ enum iv_use_location use_loc;
+ /* What kind of use for this iv. */
bool biv_p; /* Is it a biv? */
- bool have_use_for; /* Do we already have a use for it? */
- unsigned use_id; /* The identifier in the use if it is the case. */
};
/* Per-ssa version information (induction variable descriptions, etc.). */
@@ -200,6 +234,8 @@ struct iv_use
struct iv_cand *selected;
/* The selected candidate. */
+ edge exit_edge; /* Exit edge for outside loop uses. */
+ bool outside_use_p; /* True for outside loop uses. */
};
/* The position where the iv is computed. */
@@ -243,12 +279,16 @@ struct iv_inv_expr_ent
hashval_t hash;
};
-/* The data used by the induction variable optimizations. */
+/* Exit edge information. */
+struct edge_info
+{
+ edge exit_edge;
+ edge split_edge;
+ basic_block split_bb;
+};
-typedef struct iv_use *iv_use_p;
+typedef struct edge_info *edge_info_p;
-typedef struct iv_cand *iv_cand_p;
-
/* Hashtable helpers. */
struct iv_inv_expr_hasher : typed_free_remove <iv_inv_expr_ent>
@@ -306,12 +346,27 @@ struct ivopts_data
/* The uses of induction variables. */
vec<iv_use_p> iv_uses;
+ /* The uses vectors allocated for iv. These vectors have to be
+ recorded and released via this field, because there are lots
+ of pointer copies for iv structure in this optimization. */
+ vec<void *> alloc_uses_vecs;
+
/* The candidates. */
vec<iv_cand_p> iv_candidates;
/* A bitmap of important candidates. */
bitmap important_candidates;
+ /* A bitmap of basic blocks containing use which does not satisfy
+ loop closed ssa property. */
+ bitmap changed_bbs;
+
+ /* Pointer map embodying a mapping from exit edge to its edge_info. */
+ struct pointer_map_t *edge_map;
+
+ /* Obstack for exit edge information. */
+ struct obstack edge_obstack;
+
/* The maximum invariant id. */
unsigned max_inv_id;
@@ -447,6 +502,38 @@ iv_cand (struct ivopts_data *data, unsigned i)
return data->iv_candidates[i];
}
+/* Add an entry for edge EXIT_EDGE to the edge-to-edge_info mapping
+ if not exist yet. */
+static struct edge_info *
+init_edge_info (struct ivopts_data *data, edge exit_edge)
+{
+ void **p = pointer_map_contains (data->edge_map, exit_edge);
+ edge_info_p c;
+
+ if (p)
+ return (edge_info_p)*p;
+
+ p = pointer_map_insert (data->edge_map, exit_edge);
+ c = (edge_info_p) obstack_alloc (&data->edge_obstack,
+ sizeof (struct edge_info));
+ c->exit_edge = exit_edge;
+ c->split_edge = NULL;
+ c->split_bb = NULL;
+ *p = c;
+ return c;
+}
+
+/* Get edge_info for edge EXIT_EDGE, return NULL if it doesn't exist. */
+static struct edge_info *
+get_edge_info (struct ivopts_data *data, edge exit_edge)
+{
+ void **p = pointer_map_contains (data->edge_map, exit_edge);
+ if (!p)
+ return NULL;
+
+ return (struct edge_info *) *p;
+}
+
/* The single loop exit if it dominates the latch, NULL otherwise. */
edge
@@ -517,7 +604,8 @@ dump_use (FILE *file, struct iv_use *use)
switch (use->type)
{
case USE_NONLINEAR_EXPR:
- fprintf (file, " generic\n");
+ fprintf (file, " generic(%s)\n",
+ use->outside_use_p ? "outside" : "inside");
break;
case USE_ADDRESS:
@@ -860,9 +948,13 @@ tree_ssa_iv_optimize_init (struct ivopts_data *dat
data->version_info = XCNEWVEC (struct version_info, data->version_info_size);
data->relevant = BITMAP_ALLOC (NULL);
data->important_candidates = BITMAP_ALLOC (NULL);
+ data->changed_bbs = BITMAP_ALLOC (NULL);
+ data->edge_map = NULL;
+ gcc_obstack_init (&data->edge_obstack);
data->max_inv_id = 0;
data->niters = NULL;
data->iv_uses.create (20);
+ data->alloc_uses_vecs.create (20);
data->iv_candidates.create (20);
data->inv_expr_tab.create (10);
data->inv_expr_id = 0;
@@ -930,9 +1022,10 @@ alloc_iv (tree base, tree step)
iv->base = base;
iv->base_object = determine_base_object (base);
iv->step = step;
+ iv->inside_use = NULL;
+ iv->outside_uses_vec = NULL;
+ iv->use_loc = NONE_LOC;
iv->biv_p = false;
- iv->have_use_for = false;
- iv->use_id = 0;
iv->ssa_name = NULL_TREE;
return iv;
@@ -1193,11 +1286,13 @@ find_induction_variables (struct ivopts_data *data
return true;
}
-/* Records a use of type USE_TYPE at *USE_P in STMT whose value is IV. */
+/* Records a use of type USE_TYPE at *USE_P in STMT whose value is IV.
+ EXIT_EDGE is the exit edge through which IV is used outside of loop,
+ which is NULL if this is a use inside loop. */
static struct iv_use *
record_use (struct ivopts_data *data, tree *use_p, struct iv *iv,
- gimple stmt, enum use_type use_type)
+ gimple stmt, enum use_type use_type, edge exit_edge)
{
struct iv_use *use = XCNEW (struct iv_use);
@@ -1205,6 +1300,8 @@ record_use (struct ivopts_data *data, tree *use_p,
use->type = use_type;
use->iv = iv;
use->stmt = stmt;
+ use->outside_use_p = (exit_edge != NULL) ? true : false;
+ use->exit_edge = exit_edge;
use->op_p = use_p;
use->related_cands = BITMAP_ALLOC (NULL);
@@ -1212,6 +1309,10 @@ record_use (struct ivopts_data *data, tree *use_p,
caller. */
iv->ssa_name = NULL_TREE;
+ /* Record the exit edge for rewriting. */
+ if (exit_edge != NULL)
+ (void) init_edge_info (data, exit_edge);
+
if (dump_file && (dump_flags & TDF_DETAILS))
dump_use (dump_file, use);
@@ -1247,10 +1348,12 @@ record_invariant (struct ivopts_data *data, tree o
bitmap_set_bit (data->relevant, SSA_NAME_VERSION (op));
}
-/* Checks whether the use OP is interesting and if so, records it. */
+/* Checks whether the use OP is interesting and if so, records it.
+ EXIT_EDGE is the corresponding exit edge if we are looking for
+ outside loop use in OP. */
static struct iv_use *
-find_interesting_uses_op (struct ivopts_data *data, tree op)
+find_interesting_uses_op (struct ivopts_data *data, tree op, edge exit_edge)
{
struct iv *iv;
struct iv *civ;
@@ -1264,12 +1367,35 @@ static struct iv_use *
if (!iv)
return NULL;
- if (iv->have_use_for)
+ /* Outside use must be along normal exit edge. */
+ if (exit_edge != NULL)
+ gcc_assert ((exit_edge->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0);
+
+ /* Just return if there is use inside loop. */
+ if (iv->use_loc == INSIDE_LOOP)
{
- use = iv_use (data, iv->use_id);
+ gcc_assert (iv->inside_use != NULL);
+ gcc_assert (iv->inside_use->type == USE_NONLINEAR_EXPR);
+ return iv->inside_use;
+ }
- gcc_assert (use->type == USE_NONLINEAR_EXPR);
- return use;
+ /* Check if the outside use has already been recorded for this
+ exit edge. */
+ if (iv->use_loc == OUTSIDE_LOOP && exit_edge != NULL)
+ {
+ unsigned int i;
+
+ gcc_assert (iv->outside_uses_vec != NULL);
+ gcc_assert (iv->outside_uses_vec->length () > 0);
+
+ FOR_EACH_VEC_ELT ((*iv->outside_uses_vec), i, use)
+ {
+ gcc_assert (use->outside_use_p);
+ gcc_assert (use->type == USE_NONLINEAR_EXPR);
+
+ if (exit_edge == use->exit_edge)
+ return use;
+ }
}
if (integer_zerop (iv->step))
@@ -1277,8 +1403,16 @@ static struct iv_use *
record_invariant (data, op, true);
return NULL;
}
- iv->have_use_for = true;
+ iv->use_loc = exit_edge ? OUTSIDE_LOOP : INSIDE_LOOP;
+
+ /* Allocate vector for outside uses and record it. */
+ if (exit_edge != NULL && iv->outside_uses_vec == NULL)
+ {
+ vec_alloc (iv->outside_uses_vec, 4);
+ data->alloc_uses_vecs.safe_push ((void *)iv->outside_uses_vec);
+ }
+
civ = XNEW (struct iv);
*civ = *iv;
@@ -1286,8 +1420,11 @@ static struct iv_use *
gcc_assert (gimple_code (stmt) == GIMPLE_PHI
|| is_gimple_assign (stmt));
- use = record_use (data, NULL, civ, stmt, USE_NONLINEAR_EXPR);
- iv->use_id = use->id;
+ use = record_use (data, NULL, civ, stmt, USE_NONLINEAR_EXPR, exit_edge);
+ if (iv->use_loc == OUTSIDE_LOOP)
+ iv->outside_uses_vec->safe_push (use);
+ else
+ iv->inside_use = use;
return use;
}
@@ -1368,14 +1505,14 @@ find_interesting_uses_cond (struct ivopts_data *da
if (!extract_cond_operands (data, stmt, &var_p, &bound_p, &var_iv, NULL))
{
- find_interesting_uses_op (data, *var_p);
- find_interesting_uses_op (data, *bound_p);
+ find_interesting_uses_op (data, *var_p, NULL);
+ find_interesting_uses_op (data, *bound_p, NULL);
return;
}
civ = XNEW (struct iv);
*civ = *var_iv;
- record_use (data, NULL, civ, stmt, USE_COMPARE);
+ record_use (data, NULL, civ, stmt, USE_COMPARE, NULL);
}
/* Returns the outermost loop EXPR is obviously invariant in
@@ -1560,11 +1697,11 @@ idx_record_use (tree base, tree *idx,
void *vdata)
{
struct ivopts_data *data = (struct ivopts_data *) vdata;
- find_interesting_uses_op (data, *idx);
+ find_interesting_uses_op (data, *idx, NULL);
if (TREE_CODE (base) == ARRAY_REF || TREE_CODE (base) == ARRAY_RANGE_REF)
{
- find_interesting_uses_op (data, array_ref_element_size (base));
- find_interesting_uses_op (data, array_ref_low_bound (base));
+ find_interesting_uses_op (data, array_ref_element_size (base), NULL);
+ find_interesting_uses_op (data, array_ref_low_bound (base), NULL);
}
return true;
}
@@ -1831,7 +1968,7 @@ find_interesting_uses_address (struct ivopts_data
}
civ = alloc_iv (base, step);
- record_use (data, op_p, civ, stmt, USE_ADDRESS);
+ record_use (data, op_p, civ, stmt, USE_ADDRESS, NULL);
return;
fail:
@@ -1897,7 +2034,7 @@ find_interesting_uses_stmt (struct ivopts_data *da
if (REFERENCE_CLASS_P (*rhs))
find_interesting_uses_address (data, stmt, rhs);
else
- find_interesting_uses_op (data, *rhs);
+ find_interesting_uses_op (data, *rhs, NULL);
if (REFERENCE_CLASS_P (*lhs))
find_interesting_uses_address (data, stmt, lhs);
@@ -1938,26 +2075,30 @@ find_interesting_uses_stmt (struct ivopts_data *da
if (!iv)
continue;
- find_interesting_uses_op (data, op);
+ find_interesting_uses_op (data, op, NULL);
}
}
/* Finds interesting uses of induction variables outside of loops
- on loop exit edge EXIT. */
+ on loop exit edge EXIT_EDGE. NORMAL_EDGE_P is true if EXIT_EDGE
+ is a normal edge. */
static void
-find_interesting_uses_outside (struct ivopts_data *data, edge exit)
+find_interesting_uses_outside (struct ivopts_data *data,
+ edge exit_edge, bool normal_edge_p)
{
gimple phi;
gimple_stmt_iterator psi;
tree def;
- for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
+ for (psi = gsi_start_phis (exit_edge->dest);
+ !gsi_end_p (psi); gsi_next (&psi))
{
phi = gsi_stmt (psi);
- def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
+ def = PHI_ARG_DEF_FROM_EDGE (phi, exit_edge);
if (!virtual_operand_p (def))
- find_interesting_uses_op (data, def);
+ find_interesting_uses_op (data, def,
+ normal_edge_p ? exit_edge : NULL);
}
}
@@ -1976,6 +2117,11 @@ find_interesting_uses (struct ivopts_data *data)
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Uses:\n\n");
+ /* Deliberately find uses in two passes with each for inside loop iv
+ uses and outside loop iv uses. By this strategy, we don't need
+ to escalate outside use to inside one.
+
+ Find inside uses in the first pass. */
for (i = 0; i < data->current_loop->num_nodes; i++)
{
edge_iterator ei;
@@ -1983,8 +2129,11 @@ find_interesting_uses (struct ivopts_data *data)
FOR_EACH_EDGE (e, ei, bb->succs)
if (e->dest != EXIT_BLOCK_PTR
+ /* Outside use along abnormal exit edge is treated as
+ inside one. */
+ && (e->flags & (EDGE_COMPLEX | EDGE_FAKE)) != 0
&& !flow_bb_inside_loop_p (data->current_loop, e->dest))
- find_interesting_uses_outside (data, e);
+ find_interesting_uses_outside (data, e, false);
for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
find_interesting_uses_stmt (data, gsi_stmt (bsi));
@@ -1993,6 +2142,19 @@ find_interesting_uses (struct ivopts_data *data)
find_interesting_uses_stmt (data, gsi_stmt (bsi));
}
+ /* Find outside uses in the second pass. */
+ for (i = 0; i < data->current_loop->num_nodes; i++)
+ {
+ edge_iterator ei;
+ bb = body[i];
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (e->dest != EXIT_BLOCK_PTR
+ && (e->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0
+ && !flow_bb_inside_loop_p (data->current_loop, e->dest))
+ find_interesting_uses_outside (data, e, true);
+ }
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
bitmap_iterator bi;
@@ -3097,7 +3259,17 @@ get_computation_at (struct loop *loop,
static tree
get_computation (struct loop *loop, struct iv_use *use, struct iv_cand *cand)
{
- return get_computation_at (loop, use, cand, use->stmt);
+ gimple at = NULL;
+
+ /* Outside use should be computed at the end of source block of exit
+ edge. */
+ if (use->outside_use_p)
+ at = last_stmt (use->exit_edge->src);
+
+ if (at == NULL)
+ at = use->stmt;
+
+ return get_computation_at (loop, use, cand, at);
}
/* Adjust the cost COST for being in loop setup rather than loop body.
@@ -4242,6 +4414,8 @@ determine_use_iv_cost_generic (struct ivopts_data
cost = get_computation_cost (data, use, cand, false, &depends_on,
NULL, &inv_expr_id);
+ if (use->outside_use_p)
+ cost.cost = adjust_setup_cost (data, cost.cost);
set_use_iv_cost (data, use, cand, cost, depends_on, NULL_TREE, ERROR_MARK,
inv_expr_id);
@@ -6093,7 +6267,7 @@ create_new_iv (struct ivopts_data *data, struct iv
name_info (data, cand->var_after)->preserve_biv = true;
/* Rewrite the increment so that it uses var_before directly. */
- find_interesting_uses_op (data, cand->var_after)->selected = cand;
+ find_interesting_uses_op (data, cand->var_after, NULL)->selected = cand;
return;
}
@@ -6239,6 +6413,139 @@ rewrite_use_nonlinear_expr (struct ivopts_data *da
}
}
+/* Rewrites outside USE (definition of iv used in a nonlinear expression
+ outside of loop) using candidate CAND. The implementation is like
+ rewrite_use_nonlinear_expr except the exit edge will be split and
+ the computation of USE will be inserted in the newly created basic
+ block. */
+
+static void
+rewrite_use_outside_of_loop (struct ivopts_data *data,
+ struct iv_use *use, struct iv_cand *cand)
+{
+ tree comp;
+ tree op, tgt, new_tgt;
+ gimple ass;
+ gimple_stmt_iterator bsi;
+ edge e;
+ basic_block new_bb;
+ struct edge_info *einfo;
+
+ gcc_assert (use->outside_use_p && use->exit_edge != NULL);
+ /* An important special case -- if we are asked to express value of
+ the original iv by itself, just exit; there is no need to
+ introduce a new computation (that might also need casting the
+ variable to unsigned and back). */
+ if (cand->pos == IP_ORIGINAL
+ && cand->incremented_at == use->stmt)
+ {
+ enum tree_code stmt_code;
+
+ gcc_assert (is_gimple_assign (use->stmt));
+ gcc_assert (gimple_assign_lhs (use->stmt) == cand->var_after);
+
+ /* Check whether we may leave the computation unchanged.
+ This is the case only if it does not rely on other
+ computations in the loop -- otherwise, the computation
+ we rely upon may be removed in remove_unused_ivs,
+ thus leading to ICE. */
+ stmt_code = gimple_assign_rhs_code (use->stmt);
+ if (stmt_code == PLUS_EXPR
+ || stmt_code == MINUS_EXPR
+ || stmt_code == POINTER_PLUS_EXPR)
+ {
+ if (gimple_assign_rhs1 (use->stmt) == cand->var_before)
+ op = gimple_assign_rhs2 (use->stmt);
+ else if (gimple_assign_rhs2 (use->stmt) == cand->var_before)
+ op = gimple_assign_rhs1 (use->stmt);
+ else
+ op = NULL_TREE;
+ }
+ else
+ op = NULL_TREE;
+
+ if (op && expr_invariant_in_loop_p (data->current_loop, op))
+ return;
+ }
+
+ comp = get_computation (data->current_loop, use, cand);
+ gcc_assert (comp != NULL_TREE);
+
+ switch (gimple_code (use->stmt))
+ {
+ case GIMPLE_PHI:
+ tgt = PHI_RESULT (use->stmt);
+ break;
+
+ case GIMPLE_ASSIGN:
+ tgt = gimple_assign_lhs (use->stmt);
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+
+ einfo = get_edge_info (data, use->exit_edge);
+ gcc_assert (einfo->exit_edge == use->exit_edge);
+ if (einfo->split_edge == NULL)
+ {
+ gcc_assert (einfo->split_bb == NULL);
+ new_bb = split_edge (use->exit_edge);
+ e = single_succ_edge (new_bb);
+ einfo->split_bb = new_bb;
+ einfo->split_edge = e;
+ }
+ else
+ {
+ gcc_assert (einfo->split_bb != NULL);
+ new_bb = einfo->split_bb;
+ e = einfo->split_edge;
+ }
+ bsi = gsi_last_bb (new_bb);
+ /* Record basic blocks containing use which does not satisfy loop
+ closed ssa property. */
+ bitmap_set_bit (data->changed_bbs, new_bb->index);
+ bitmap_set_bit (data->changed_bbs, e->dest->index);
+
+ if (!valid_gimple_rhs_p (comp))
+ {
+ comp = force_gimple_operand_gsi (&bsi, comp, true, NULL_TREE,
+ false, GSI_CONTINUE_LINKING);
+ if (POINTER_TYPE_P (TREE_TYPE (tgt)))
+ {
+ duplicate_ssa_name_ptr_info (comp, SSA_NAME_PTR_INFO (tgt));
+ /* As this isn't a plain copy we have to reset alignment
+ information. */
+ if (SSA_NAME_PTR_INFO (comp))
+ mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (comp));
+ }
+ }
+ new_tgt = make_temp_ssa_name (TREE_TYPE (tgt), NULL, "iv2tmp");
+
+ if (POINTER_TYPE_P (TREE_TYPE (tgt)))
+ {
+ duplicate_ssa_name_ptr_info (new_tgt, SSA_NAME_PTR_INFO (tgt));
+ /* As this isn't a plain copy we have to reset alignment
+ information. */
+ if (SSA_NAME_PTR_INFO (new_tgt))
+ mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (new_tgt));
+ }
+
+ ass = gimple_build_assign (new_tgt, comp);
+ gsi_insert_after (&bsi, ass, GSI_CONTINUE_LINKING);
+
+ for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
+ {
+ gimple phi = gsi_stmt (bsi);
+ tree def = PHI_ARG_DEF_FROM_EDGE (phi, e);
+ if (def != tgt)
+ continue;
+
+ SET_PHI_ARG_DEF (phi, e->dest_idx, new_tgt);
+ update_stmt (phi);
+ }
+}
+
/* Performs a peephole optimization to reorder the iv update statement with
a mem ref to enable instruction combining in later phases. The mem ref uses
the iv value before the update, so the reordering transformation requires
@@ -6420,7 +6727,14 @@ rewrite_use (struct ivopts_data *data, struct iv_u
switch (use->type)
{
case USE_NONLINEAR_EXPR:
- rewrite_use_nonlinear_expr (data, use, cand);
+ if (use->outside_use_p)
+ {
+ gcc_assert (use->exit_edge != NULL);
+ rewrite_use_outside_of_loop (data, use, cand);
+ }
+ else
+ rewrite_use_nonlinear_expr (data, use, cand);
+
break;
case USE_ADDRESS:
@@ -6477,11 +6791,12 @@ remove_unused_ivs (struct ivopts_data *data)
if (info->iv
&& !integer_zerop (info->iv->step)
&& !info->inv_id
- && !info->iv->have_use_for
+ /* Outside use is computated on exit edge. */
+ && info->iv->use_loc != INSIDE_LOOP
&& !info->preserve_biv)
{
bitmap_set_bit (toremove, SSA_NAME_VERSION (info->iv->ssa_name));
-
+
tree def = info->iv->ssa_name;
if (MAY_HAVE_DEBUG_STMTS && SSA_NAME_DEF_STMT (def))
@@ -6625,6 +6940,9 @@ free_loop_data (struct ivopts_data *data)
struct version_info *info;
info = ver_info (data, i);
+ if (info->iv != NULL)
+ info->iv->outside_uses_vec = NULL;
+
free (info->iv);
info->iv = NULL;
info->has_nonlin_use = false;
@@ -6637,6 +6955,8 @@ free_loop_data (struct ivopts_data *data)
for (i = 0; i < n_iv_uses (data); i++)
{
struct iv_use *use = iv_use (data, i);
+ if (use->iv != NULL)
+ use->iv->outside_uses_vec = NULL;
free (use->iv);
BITMAP_FREE (use->related_cands);
@@ -6648,9 +6968,19 @@ free_loop_data (struct ivopts_data *data)
}
data->iv_uses.truncate (0);
+ for (i = 0; i < data->alloc_uses_vecs.length (); i++)
+ {
+ vec<iv_use_p> *uses_vec = (vec<iv_use_p> *)data->alloc_uses_vecs[i];
+ gcc_assert (uses_vec != NULL);
+ vec_free (uses_vec);
+ }
+ data->alloc_uses_vecs.truncate (0);
+
for (i = 0; i < n_iv_cands (data); i++)
{
struct iv_cand *cand = iv_cand (data, i);
+ if (cand->iv != NULL)
+ cand->iv->outside_uses_vec = NULL;
free (cand->iv);
if (cand->depends_on)
@@ -6666,6 +6996,12 @@ free_loop_data (struct ivopts_data *data)
data->version_info = XCNEWVEC (struct version_info, data->version_info_size);
}
+ if (data->edge_map != NULL)
+ {
+ pointer_map_destroy (data->edge_map);
+ data->edge_map = NULL;
+ }
+
data->max_inv_id = 0;
FOR_EACH_VEC_ELT (decl_rtl_to_reset, i, obj)
@@ -6687,9 +7023,13 @@ tree_ssa_iv_optimize_finalize (struct ivopts_data
free (data->version_info);
BITMAP_FREE (data->relevant);
BITMAP_FREE (data->important_candidates);
+ BITMAP_FREE (data->changed_bbs);
+ data->edge_map = NULL;
+ obstack_free (&data->edge_obstack, NULL);
decl_rtl_to_reset.release ();
data->iv_uses.release ();
+ data->alloc_uses_vecs.release ();
data->iv_candidates.release ();
data->inv_expr_tab.dispose ();
}
@@ -6726,6 +7066,8 @@ tree_ssa_iv_optimize_loop (struct ivopts_data *dat
gcc_assert (!data->niters);
data->current_loop = loop;
data->speed = optimize_loop_for_speed_p (loop);
+ /* Allocate the mapping from edge to edge_info for this loop. */
+ data->edge_map = pointer_map_create ();
if (dump_file && (dump_flags & TDF_DETAILS))
{
@@ -6812,6 +7154,12 @@ tree_ssa_iv_optimize (void)
flow_loop_dump (loop, dump_file, NULL, 1);
tree_ssa_iv_optimize_loop (&data, loop);
+ /* Update ssa form if it's changed. */
+ if (!bitmap_empty_p (data.changed_bbs))
+ {
+ rewrite_into_loop_closed_ssa (data.changed_bbs, TODO_update_ssa);
+ bitmap_clear (data.changed_bbs);
+ }
}
tree_ssa_iv_optimize_finalize (&data);