This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch, commited] remove redundant field from loop structure
- From: Zdenek Dvorak <rakdver at kam dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Fri, 11 May 2007 17:58:31 +0200
- Subject: [patch, commited] remove redundant field from loop structure
Hello,
struct loop contains fields "outer" (the immediate superloop of the
loop) and "pred" (list of all superloops of the loop). Obviously,
the "outer" field is redundant, as it is equal to the last member of
the "pred" list. Although loop structures do not consume a significant
portion of memory, I think it is better to avoid this redundancy.
The patch also renames the "pred" field (as the current name is
completely unintelligible) to "superloops", and makes it a vector; since
the length of this vector is equal to the depth of the loop, the "depth"
field is also removed.
The patch is mostly mechanical, replacing uses of the "outer" and
"depth" fields with new "loop_outer" and "loop_depth" accessor
functions.
Bootstrapped & regtested on i686, commited.
Zdenek
Index: ChangeLog
===================================================================
*** ChangeLog (revision 124618)
--- ChangeLog (working copy)
***************
*** 1,3 ****
--- 1,37 ----
+ 2007-05-11 Zdenek Dvorak <dvorakz@suse.cz>
+
+ * tree-loop-linear.c (gather_interchange_stats, try_interchange_loops):
+ Use loop_depth and loop_outer accessor functions.
+ * tree-ssa-loop-im.c (outermost_invariant_loop, set_level,
+ determine_invariantness_stmt, move_computations_stmt): Ditto.
+ * cfgloopmanip.c (fix_bb_placement, fix_loop_placement, remove_path,
+ add_loop, loopify, unloop, fix_loop_structure): Ditto.
+ * tree-ssa-loop-manip.c (find_uses_to_rename_use): Ditto.
+ * tree-scalar-evolution.c (interpret_loop_phi,
+ compute_scalar_evolution_in_loop, analyze_scalar_evolution_in_loop,
+ instantiate_parameters_1, scev_const_prop): Ditto.
+ * cfghooks.c (make_forwarder_block): Ditto.
+ * cfgloopanal.c (mark_irreducible_loops, mark_loop_exit_edges): Ditto.
+ * modulo-sched.c (loop_canon_p): Ditto.
+ * tree-vectorizer.c (slpeel_tree_duplicate_loop_to_edge_cfg,
+ slpeel_can_duplicate_loop_p): Ditto.
+ * lambda-code.c (invariant_in_loop_and_outer_loops): Ditto.
+ * tree-cfg.c (tree_duplicate_sese_region): Ditto.
+ * cfgloop.c (flow_loop_dump, flow_loop_nodes_find, rescan_loop_exit,
+ cancel_loop, verify_loop_structure): Ditto.
+ (flow_loop_nested_p, superloop_at_depth, flow_loop_free,
+ add_bb_to_loop, remove_bb_from_loops, find_common_loop): Use the
+ superloops vector instead of "pred" array.
+ (establish_preds): Take father loop as an argument. Initialize the
+ superloops vector.
+ (flow_loop_tree_node_add): Pass father loop to establish_preds. Do not
+ initialize loop->outer.
+ (flow_loop_tree_node_remove): Truncate the superloops vector.
+ * cfgloop.h (struct loop): Removed field "outer", fields "depth" and
+ "pred" merged to "superloops" vector.
+ (loop_depth, loop_outer): New.
+ (fel_init): Use loop_outer.
+
2007-05-11 Jan Hubicka <jh@suse.cz>
* cgraphunit.c: Include gt-cgraphunit.h
Index: tree-loop-linear.c
===================================================================
*** tree-loop-linear.c (revision 124618)
--- tree-loop-linear.c (working copy)
*************** gather_interchange_stats (VEC (ddr_p, he
*** 117,123 ****
for (j = 0; j < DDR_NUM_DIST_VECTS (ddr); j++)
{
! int dist = DDR_DIST_VECT (ddr, j)[loop->depth - first_loop->depth];
if (dist == 0)
(*nb_deps_not_carried_by_loop) += 1;
--- 117,123 ----
for (j = 0; j < DDR_NUM_DIST_VECTS (ddr); j++)
{
! int dist = DDR_DIST_VECT (ddr, j)[loop_depth (loop) - loop_depth (first_loop)];
if (dist == 0)
(*nb_deps_not_carried_by_loop) += 1;
*************** try_interchange_loops (lambda_trans_matr
*** 200,206 ****
loop_j;
loop_j = loop_j->inner)
for (loop_i = first_loop;
! loop_i->depth < loop_j->depth;
loop_i = loop_i->inner)
{
gather_interchange_stats (dependence_relations, datarefs,
--- 200,206 ----
loop_j;
loop_j = loop_j->inner)
for (loop_i = first_loop;
! loop_depth (loop_i) < loop_depth (loop_j);
loop_i = loop_i->inner)
{
gather_interchange_stats (dependence_relations, datarefs,
*************** try_interchange_loops (lambda_trans_matr
*** 230,243 ****
|| double_int_ucmp (access_strides_i, access_strides_j) < 0)
{
lambda_matrix_row_exchange (LTM_MATRIX (trans),
! loop_i->depth - first_loop->depth,
! loop_j->depth - first_loop->depth);
/* Validate the resulting matrix. When the transformation
is not valid, reverse to the previous transformation. */
if (!lambda_transform_legal_p (trans, depth, dependence_relations))
lambda_matrix_row_exchange (LTM_MATRIX (trans),
! loop_i->depth - first_loop->depth,
! loop_j->depth - first_loop->depth);
}
}
--- 230,243 ----
|| double_int_ucmp (access_strides_i, access_strides_j) < 0)
{
lambda_matrix_row_exchange (LTM_MATRIX (trans),
! loop_depth (loop_i) - loop_depth (first_loop),
! loop_depth (loop_j) - loop_depth (first_loop));
/* Validate the resulting matrix. When the transformation
is not valid, reverse to the previous transformation. */
if (!lambda_transform_legal_p (trans, depth, dependence_relations))
lambda_matrix_row_exchange (LTM_MATRIX (trans),
! loop_depth (loop_i) - loop_depth (first_loop),
! loop_depth (loop_j) - loop_depth (first_loop));
}
}
Index: tree-ssa-loop-im.c
===================================================================
*** tree-ssa-loop-im.c (revision 124618)
--- tree-ssa-loop-im.c (working copy)
*************** outermost_invariant_loop (tree def, stru
*** 316,325 ****
if (LIM_DATA (def_stmt) && LIM_DATA (def_stmt)->max_loop)
max_loop = find_common_loop (max_loop,
! LIM_DATA (def_stmt)->max_loop->outer);
if (max_loop == loop)
return NULL;
! max_loop = superloop_at_depth (loop, max_loop->depth + 1);
return max_loop;
}
--- 316,325 ----
if (LIM_DATA (def_stmt) && LIM_DATA (def_stmt)->max_loop)
max_loop = find_common_loop (max_loop,
! loop_outer (LIM_DATA (def_stmt)->max_loop));
if (max_loop == loop)
return NULL;
! max_loop = superloop_at_depth (loop, loop_depth (max_loop) + 1);
return max_loop;
}
*************** set_level (tree stmt, struct loop *orig_
*** 525,531 ****
stmt_loop = find_common_loop (orig_loop, stmt_loop);
if (LIM_DATA (stmt) && LIM_DATA (stmt)->tgt_loop)
stmt_loop = find_common_loop (stmt_loop,
! LIM_DATA (stmt)->tgt_loop->outer);
if (flow_loop_nested_p (stmt_loop, level))
return;
--- 525,531 ----
stmt_loop = find_common_loop (orig_loop, stmt_loop);
if (LIM_DATA (stmt) && LIM_DATA (stmt)->tgt_loop)
stmt_loop = find_common_loop (stmt_loop,
! loop_outer (LIM_DATA (stmt)->tgt_loop));
if (flow_loop_nested_p (stmt_loop, level))
return;
*************** determine_invariantness_stmt (struct dom
*** 709,720 ****
bool maybe_never = ALWAYS_EXECUTED_IN (bb) == NULL;
struct loop *outermost = ALWAYS_EXECUTED_IN (bb);
! if (!bb->loop_father->outer)
return;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
! bb->index, bb->loop_father->num, bb->loop_father->depth);
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
--- 709,720 ----
bool maybe_never = ALWAYS_EXECUTED_IN (bb) == NULL;
struct loop *outermost = ALWAYS_EXECUTED_IN (bb);
! if (!loop_outer (bb->loop_father))
return;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
! bb->index, bb->loop_father->num, loop_depth (bb->loop_father));
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
*************** determine_invariantness_stmt (struct dom
*** 774,780 ****
{
print_generic_stmt_indented (dump_file, stmt, 0, 2);
fprintf (dump_file, " invariant up to level %d, cost %d.\n\n",
! LIM_DATA (stmt)->max_loop->depth,
LIM_DATA (stmt)->cost);
}
--- 774,780 ----
{
print_generic_stmt_indented (dump_file, stmt, 0, 2);
fprintf (dump_file, " invariant up to level %d, cost %d.\n\n",
! loop_depth (LIM_DATA (stmt)->max_loop),
LIM_DATA (stmt)->cost);
}
*************** move_computations_stmt (struct dom_walk_
*** 815,821 ****
tree stmt;
unsigned cost = 0;
! if (!bb->loop_father->outer)
return;
for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
--- 815,821 ----
tree stmt;
unsigned cost = 0;
! if (!loop_outer (bb->loop_father))
return;
for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
Index: cfgloopmanip.c
===================================================================
*** cfgloopmanip.c (revision 124618)
--- cfgloopmanip.c (working copy)
*************** fix_bb_placement (basic_block bb)
*** 102,108 ****
act = e->dest->loop_father;
if (act->header == e->dest)
! act = act->outer;
if (flow_loop_nested_p (loop, act))
loop = act;
--- 102,108 ----
act = e->dest->loop_father;
if (act->header == e->dest)
! act = loop_outer (act);
if (flow_loop_nested_p (loop, act))
loop = act;
*************** fix_loop_placement (struct loop *loop)
*** 138,146 ****
father = act;
}
! if (father != loop->outer)
{
! for (act = loop->outer; act != father; act = act->outer)
act->num_nodes -= loop->num_nodes;
flow_loop_tree_node_remove (loop);
flow_loop_tree_node_add (father, loop);
--- 138,146 ----
father = act;
}
! if (father != loop_outer (loop))
{
! for (act = loop_outer (loop); act != father; act = loop_outer (act))
act->num_nodes -= loop->num_nodes;
flow_loop_tree_node_remove (loop);
flow_loop_tree_node_add (father, loop);
*************** remove_path (edge e)
*** 305,311 ****
we belong to. In this case first unloop the loops, then proceed
normally. We may assume that e->dest is not a header of any loop,
as it now has exactly one predecessor. */
! while (e->src->loop_father->outer
&& dominated_by_p (CDI_DOMINATORS,
e->src->loop_father->latch, e->dest))
unloop (e->src->loop_father, &irred_invalidated);
--- 305,311 ----
we belong to. In this case first unloop the loops, then proceed
normally. We may assume that e->dest is not a header of any loop,
as it now has exactly one predecessor. */
! while (loop_outer (e->src->loop_father)
&& dominated_by_p (CDI_DOMINATORS,
e->src->loop_father->latch, e->dest))
unloop (e->src->loop_father, &irred_invalidated);
*************** add_loop (struct loop *loop, struct loop
*** 434,440 ****
/* If we find a direct subloop of OUTER, move it to LOOP. */
subloop = bbs[i]->loop_father;
! if (subloop->outer == outer
&& subloop->header == bbs[i])
{
flow_loop_tree_node_remove (subloop);
--- 434,440 ----
/* If we find a direct subloop of OUTER, move it to LOOP. */
subloop = bbs[i]->loop_father;
! if (loop_outer (subloop) == outer
&& subloop->header == bbs[i])
{
flow_loop_tree_node_remove (subloop);
*************** loopify (edge latch_edge, edge header_ed
*** 477,483 ****
unsigned n_dom_bbs, i;
sbitmap seen;
struct loop *loop = alloc_loop ();
! struct loop *outer = succ_bb->loop_father->outer;
int freq;
gcov_type cnt;
edge e;
--- 477,483 ----
unsigned n_dom_bbs, i;
sbitmap seen;
struct loop *loop = alloc_loop ();
! struct loop *outer = loop_outer (succ_bb->loop_father);
int freq;
gcov_type cnt;
edge e;
*************** unloop (struct loop *loop, bool *irred_i
*** 592,598 ****
if (body[i]->loop_father == loop)
{
remove_bb_from_loops (body[i]);
! add_bb_to_loop (body[i], loop->outer);
}
free(body);
--- 592,598 ----
if (body[i]->loop_father == loop)
{
remove_bb_from_loops (body[i]);
! add_bb_to_loop (body[i], loop_outer (loop));
}
free(body);
*************** unloop (struct loop *loop, bool *irred_i
*** 600,606 ****
{
ploop = loop->inner;
flow_loop_tree_node_remove (ploop);
! flow_loop_tree_node_add (loop->outer, ploop);
}
/* Remove the loop and free its data. */
--- 600,606 ----
{
ploop = loop->inner;
flow_loop_tree_node_remove (ploop);
! flow_loop_tree_node_add (loop_outer (loop), ploop);
}
/* Remove the loop and free its data. */
*************** fix_loop_placements (struct loop *loop,
*** 627,635 ****
{
struct loop *outer;
! while (loop->outer)
{
! outer = loop->outer;
if (!fix_loop_placement (loop))
break;
--- 627,635 ----
{
struct loop *outer;
! while (loop_outer (loop))
{
! outer = loop_outer (loop);
if (!fix_loop_placement (loop))
break;
*************** fix_loop_structure (bitmap changed_bbs)
*** 1393,1399 ****
FOR_EACH_BB (bb)
{
if (changed_bbs)
! bb->aux = (void *) (size_t) bb->loop_father->depth;
bb->loop_father = current_loops->tree_root;
}
--- 1393,1399 ----
FOR_EACH_BB (bb)
{
if (changed_bbs)
! bb->aux = (void *) (size_t) loop_depth (bb->loop_father);
bb->loop_father = current_loops->tree_root;
}
*************** fix_loop_structure (bitmap changed_bbs)
*** 1416,1422 ****
{
ploop = loop->inner;
flow_loop_tree_node_remove (ploop);
! flow_loop_tree_node_add (loop->outer, ploop);
}
/* Remove the loop and free its data. */
--- 1416,1422 ----
{
ploop = loop->inner;
flow_loop_tree_node_remove (ploop);
! flow_loop_tree_node_add (loop_outer (loop), ploop);
}
/* Remove the loop and free its data. */
*************** fix_loop_structure (bitmap changed_bbs)
*** 1439,1445 ****
FOR_EACH_LOOP (li, loop, 0)
{
ploop = superloop[loop->num];
! if (ploop != loop->outer)
{
flow_loop_tree_node_remove (loop);
flow_loop_tree_node_add (ploop, loop);
--- 1439,1445 ----
FOR_EACH_LOOP (li, loop, 0)
{
ploop = superloop[loop->num];
! if (ploop != loop_outer (loop))
{
flow_loop_tree_node_remove (loop);
flow_loop_tree_node_add (ploop, loop);
*************** fix_loop_structure (bitmap changed_bbs)
*** 1452,1458 ****
{
FOR_EACH_BB (bb)
{
! if ((void *) (size_t) bb->loop_father->depth != bb->aux)
bitmap_set_bit (changed_bbs, bb->index);
bb->aux = NULL;
--- 1452,1458 ----
{
FOR_EACH_BB (bb)
{
! if ((void *) (size_t) loop_depth (bb->loop_father) != bb->aux)
bitmap_set_bit (changed_bbs, bb->index);
bb->aux = NULL;
Index: tree-ssa-loop-manip.c
===================================================================
*** tree-ssa-loop-manip.c (revision 124618)
--- tree-ssa-loop-manip.c (working copy)
*************** find_uses_to_rename_use (basic_block bb,
*** 244,250 ****
def_loop = def_bb->loop_father;
/* If the definition is not inside loop, it is not interesting. */
! if (!def_loop->outer)
return;
if (!use_blocks[ver])
--- 244,250 ----
def_loop = def_bb->loop_father;
/* If the definition is not inside loop, it is not interesting. */
! if (!loop_outer (def_loop))
return;
if (!use_blocks[ver])
Index: tree-scalar-evolution.c
===================================================================
*** tree-scalar-evolution.c (revision 124618)
--- tree-scalar-evolution.c (working copy)
*************** interpret_loop_phi (struct loop *loop, t
*** 1534,1540 ****
(phi_loop, PHI_RESULT (loop_phi_node));
/* Dive one level deeper. */
! subloop = superloop_at_depth (phi_loop, loop->depth + 1);
/* Interpret the subloop. */
res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
--- 1534,1540 ----
(phi_loop, PHI_RESULT (loop_phi_node));
/* Dive one level deeper. */
! subloop = superloop_at_depth (phi_loop, loop_depth (loop) + 1);
/* Interpret the subloop. */
res = compute_overall_effect_of_inner_loop (subloop, evolution_fn);
*************** compute_scalar_evolution_in_loop (struct
*** 1680,1686 ****
if (def_loop == wrto_loop)
return ev;
! def_loop = superloop_at_depth (def_loop, wrto_loop->depth + 1);
res = compute_overall_effect_of_inner_loop (def_loop, ev);
return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
--- 1680,1686 ----
if (def_loop == wrto_loop)
return ev;
! def_loop = superloop_at_depth (def_loop, loop_depth (wrto_loop) + 1);
res = compute_overall_effect_of_inner_loop (def_loop, ev);
return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
*************** analyze_scalar_evolution_in_loop (struct
*** 2023,2029 ****
|| !val)
return chrec_dont_know;
! use_loop = use_loop->outer;
}
}
--- 2023,2029 ----
|| !val)
return chrec_dont_know;
! use_loop = loop_outer (use_loop);
}
}
*************** instantiate_parameters_1 (struct loop *l
*** 2169,2176 ****
/* Don't instantiate loop-closed-ssa phi nodes. */
if (TREE_CODE (res) == SSA_NAME
&& (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL
! || (loop_containing_stmt (SSA_NAME_DEF_STMT (res))->depth
! > def_loop->depth)))
{
if (res == chrec)
res = loop_closed_phi_def (chrec);
--- 2169,2176 ----
/* 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);
*************** scev_const_prop (void)
*** 2966,2972 ****
tree_block_label (exit->dest);
bsi = bsi_after_labels (exit->dest);
! ex_loop = superloop_at_depth (loop, exit->dest->loop_father->depth + 1);
for (phi = phi_nodes (exit->dest); phi; phi = next_phi)
{
--- 2966,2973 ----
tree_block_label (exit->dest);
bsi = bsi_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)
{
Index: cfghooks.c
===================================================================
*** cfghooks.c (revision 124618)
--- cfghooks.c (working copy)
*************** make_forwarder_block (basic_block bb, bo
*** 767,773 ****
}
/* In case we split loop latch, update it. */
! for (ploop = loop; ploop; ploop = ploop->outer)
if (ploop->latch == dummy)
ploop->latch = bb;
}
--- 767,773 ----
}
/* In case we split loop latch, update it. */
! for (ploop = loop; ploop; ploop = loop_outer (ploop))
if (ploop->latch == dummy)
ploop->latch = bb;
}
Index: cfgloopanal.c
===================================================================
*** cfgloopanal.c (revision 124618)
--- cfgloopanal.c (working copy)
*************** mark_irreducible_loops (void)
*** 276,282 ****
int num = current_loops ? number_of_loops () : 1;
int *queue1 = XNEWVEC (int, last_basic_block + num);
int *queue2 = XNEWVEC (int, last_basic_block + num);
! int nq, depth;
struct loop *cloop, *loop;
loop_iterator li;
--- 276,283 ----
int num = current_loops ? number_of_loops () : 1;
int *queue1 = XNEWVEC (int, last_basic_block + num);
int *queue2 = XNEWVEC (int, last_basic_block + num);
! int nq;
! unsigned depth;
struct loop *cloop, *loop;
loop_iterator li;
*************** mark_irreducible_loops (void)
*** 321,332 ****
if (!flow_bb_inside_loop_p (act->loop_father, e->dest))
{
! depth = find_common_loop (act->loop_father,
! e->dest->loop_father)->depth + 1;
! if (depth == act->loop_father->depth)
cloop = act->loop_father;
else
! cloop = act->loop_father->pred[depth];
src = LOOP_REPR (cloop);
}
--- 322,334 ----
if (!flow_bb_inside_loop_p (act->loop_father, e->dest))
{
! depth = 1 + loop_depth (find_common_loop (act->loop_father,
! e->dest->loop_father));
! if (depth == loop_depth (act->loop_father))
cloop = act->loop_father;
else
! cloop = VEC_index (loop_p, act->loop_father->superloops,
! depth);
src = LOOP_REPR (cloop);
}
*************** mark_loop_exit_edges (void)
*** 612,618 ****
FOR_EACH_EDGE (e, ei, bb->succs)
{
! if (bb->loop_father->outer
&& loop_exit_edge_p (bb->loop_father, e))
e->flags |= EDGE_LOOP_EXIT;
else
--- 614,620 ----
FOR_EACH_EDGE (e, ei, bb->succs)
{
! if (loop_outer (bb->loop_father)
&& loop_exit_edge_p (bb->loop_father, e))
e->flags |= EDGE_LOOP_EXIT;
else
Index: modulo-sched.c
===================================================================
*** modulo-sched.c (revision 124618)
--- modulo-sched.c (working copy)
*************** static bool
*** 811,817 ****
loop_canon_p (struct loop *loop)
{
! if (loop->inner || ! loop->outer)
return false;
if (!single_exit (loop))
--- 811,817 ----
loop_canon_p (struct loop *loop)
{
! if (loop->inner || !loop_outer (loop))
return false;
if (!single_exit (loop))
Index: tree-vectorizer.c
===================================================================
*** tree-vectorizer.c (revision 124618)
--- tree-vectorizer.c (working copy)
*************** slpeel_tree_duplicate_loop_to_edge_cfg (
*** 832,838 ****
}
/* Generate new loop structure. */
! new_loop = duplicate_loop (loop, loop->outer);
if (!new_loop)
{
free (bbs);
--- 832,838 ----
}
/* Generate new loop structure. */
! new_loop = duplicate_loop (loop, loop_outer (loop));
if (!new_loop)
{
free (bbs);
*************** slpeel_can_duplicate_loop_p (struct loop
*** 962,968 ****
if (loop->inner
/* All loops have an outer scope; the only case loop->outer is NULL is for
the function itself. */
! || !loop->outer
|| loop->num_nodes != 2
|| !empty_block_p (loop->latch)
|| !single_exit (loop)
--- 962,968 ----
if (loop->inner
/* All loops have an outer scope; the only case loop->outer is NULL is for
the function itself. */
! || !loop_outer (loop)
|| loop->num_nodes != 2
|| !empty_block_p (loop->latch)
|| !single_exit (loop)
Index: lambda-code.c
===================================================================
*** lambda-code.c (revision 124618)
--- lambda-code.c (working copy)
*************** invariant_in_loop_and_outer_loops (struc
*** 1187,1198 ****
{
if (is_gimple_min_invariant (op))
return true;
! if (loop->depth == 0)
return true;
if (!expr_invariant_in_loop_p (loop, op))
return false;
! if (loop->outer
! && !invariant_in_loop_and_outer_loops (loop->outer, op))
return false;
return true;
}
--- 1187,1197 ----
{
if (is_gimple_min_invariant (op))
return true;
! if (loop_depth (loop) == 0)
return true;
if (!expr_invariant_in_loop_p (loop, op))
return false;
! if (!invariant_in_loop_and_outer_loops (loop_outer (loop), op))
return false;
return true;
}
Index: cfgloop.c
===================================================================
*** cfgloop.c (revision 124618)
--- cfgloop.c (working copy)
*************** Software Foundation, 51 Franklin Street,
*** 36,42 ****
#include "output.h"
static void flow_loops_cfg_dump (FILE *);
- static void establish_preds (struct loop *);
/* Dump loop related CFG information. */
--- 36,41 ----
*************** flow_loops_cfg_dump (FILE *file)
*** 65,72 ****
bool
flow_loop_nested_p (const struct loop *outer, const struct loop *loop)
{
! return (loop->depth > outer->depth
! && loop->pred[outer->depth] == outer);
}
/* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
--- 64,73 ----
bool
flow_loop_nested_p (const struct loop *outer, const struct loop *loop)
{
! unsigned odepth = loop_depth (outer);
!
! return (loop_depth (loop) > odepth
! && VEC_index (loop_p, loop->superloops, odepth) == outer);
}
/* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
*************** flow_loop_nested_p (const struct loop *o
*** 75,86 ****
struct loop *
superloop_at_depth (struct loop *loop, unsigned depth)
{
! gcc_assert (depth <= (unsigned) loop->depth);
! if (depth == (unsigned) loop->depth)
return loop;
! return loop->pred[depth];
}
/* Returns the list of the latch edges of LOOP. */
--- 76,89 ----
struct loop *
superloop_at_depth (struct loop *loop, unsigned depth)
{
! unsigned ldepth = loop_depth (loop);
!
! gcc_assert (depth <= ldepth);
! if (depth == ldepth)
return loop;
! return VEC_index (loop_p, loop->superloops, depth);
}
/* Returns the list of the latch edges of LOOP. */
*************** flow_loop_dump (const struct loop *loop,
*** 133,139 ****
}
fprintf (file, ";; depth %d, outer %ld\n",
! loop->depth, (long) (loop->outer ? loop->outer->num : -1));
fprintf (file, ";; nodes:");
bbs = get_loop_body (loop);
--- 136,143 ----
}
fprintf (file, ";; depth %d, outer %ld\n",
! loop_depth (loop), (long) (loop_outer (loop)
! ? loop_outer (loop)->num : -1));
fprintf (file, ";; nodes:");
bbs = get_loop_body (loop);
*************** flow_loop_free (struct loop *loop)
*** 175,182 ****
{
struct loop_exit *exit, *next;
! if (loop->pred)
! free (loop->pred);
/* Break the list of the loop exit records. They will be freed when the
corresponding edge is rescanned or removed, and this avoids
--- 179,185 ----
{
struct loop_exit *exit, *next;
! VEC_free (loop_p, heap, loop->superloops);
/* Break the list of the loop exit records. They will be freed when the
corresponding edge is rescanned or removed, and this avoids
*************** flow_loop_nodes_find (basic_block header
*** 226,234 ****
int num_nodes = 1;
edge latch;
edge_iterator latch_ei;
header->loop_father = loop;
! header->loop_depth = loop->depth;
FOR_EACH_EDGE (latch, latch_ei, loop->header->preds)
{
--- 229,238 ----
int num_nodes = 1;
edge latch;
edge_iterator latch_ei;
+ unsigned depth = loop_depth (loop);
header->loop_father = loop;
! header->loop_depth = depth;
FOR_EACH_EDGE (latch, latch_ei, loop->header->preds)
{
*************** flow_loop_nodes_find (basic_block header
*** 239,245 ****
num_nodes++;
VEC_safe_push (basic_block, heap, stack, latch->src);
latch->src->loop_father = loop;
! latch->src->loop_depth = loop->depth;
while (!VEC_empty (basic_block, stack))
{
--- 243,249 ----
num_nodes++;
VEC_safe_push (basic_block, heap, stack, latch->src);
latch->src->loop_father = loop;
! latch->src->loop_depth = depth;
while (!VEC_empty (basic_block, stack))
{
*************** flow_loop_nodes_find (basic_block header
*** 256,262 ****
if (ancestor->loop_father != loop)
{
ancestor->loop_father = loop;
! ancestor->loop_depth = loop->depth;
num_nodes++;
VEC_safe_push (basic_block, heap, stack, ancestor);
}
--- 260,266 ----
if (ancestor->loop_father != loop)
{
ancestor->loop_father = loop;
! ancestor->loop_depth = depth;
num_nodes++;
VEC_safe_push (basic_block, heap, stack, ancestor);
}
*************** flow_loop_nodes_find (basic_block header
*** 268,291 ****
return num_nodes;
}
static void
! establish_preds (struct loop *loop)
{
! struct loop *ploop, *father = loop->outer;
!
! loop->depth = father->depth + 1;
/* Remember the current loop depth if it is the largest seen so far. */
! cfun->max_loop_depth = MAX (cfun->max_loop_depth, loop->depth);
! if (loop->pred)
! free (loop->pred);
! loop->pred = XNEWVEC (struct loop *, loop->depth);
! memcpy (loop->pred, father->pred, sizeof (struct loop *) * father->depth);
! loop->pred[father->depth] = father;
for (ploop = loop->inner; ploop; ploop = ploop->next)
! establish_preds (ploop);
}
/* Add LOOP to the loop hierarchy tree where FATHER is father of the
--- 272,298 ----
return num_nodes;
}
+ /* Records the vector of superloops of the loop LOOP, whose immediate
+ superloop is FATHER. */
+
static void
! establish_preds (struct loop *loop, struct loop *father)
{
! loop_p ploop;
! unsigned depth = loop_depth (father) + 1;
! unsigned i;
/* Remember the current loop depth if it is the largest seen so far. */
! cfun->max_loop_depth = MAX (cfun->max_loop_depth, (int) depth);
! VEC_truncate (loop_p, loop->superloops, 0);
! VEC_reserve (loop_p, heap, loop->superloops, depth);
! for (i = 0; VEC_iterate (loop_p, father->superloops, i, ploop); i++)
! VEC_quick_push (loop_p, loop->superloops, ploop);
! VEC_quick_push (loop_p, loop->superloops, father);
for (ploop = loop->inner; ploop; ploop = ploop->next)
! establish_preds (ploop, loop);
}
/* Add LOOP to the loop hierarchy tree where FATHER is father of the
*************** flow_loop_tree_node_add (struct loop *fa
*** 297,305 ****
{
loop->next = father->inner;
father->inner = loop;
- loop->outer = father;
! establish_preds (loop);
}
/* Remove LOOP from the loop hierarchy tree. */
--- 304,311 ----
{
loop->next = father->inner;
father->inner = loop;
! establish_preds (loop, father);
}
/* Remove LOOP from the loop hierarchy tree. */
*************** flow_loop_tree_node_remove (struct loop
*** 309,329 ****
{
struct loop *prev, *father;
! father = loop->outer;
! loop->outer = NULL;
/* Remove loop from the list of sons. */
if (father->inner == loop)
father->inner = loop->next;
else
{
! for (prev = father->inner; prev->next != loop; prev = prev->next);
prev->next = loop->next;
}
! loop->depth = -1;
! free (loop->pred);
! loop->pred = NULL;
}
/* Allocates and returns new loop structure. */
--- 315,333 ----
{
struct loop *prev, *father;
! father = loop_outer (loop);
/* Remove loop from the list of sons. */
if (father->inner == loop)
father->inner = loop->next;
else
{
! for (prev = father->inner; prev->next != loop; prev = prev->next)
! continue;
prev->next = loop->next;
}
! VEC_truncate (loop_p, loop->superloops, 0);
}
/* Allocates and returns new loop structure. */
*************** rescan_loop_exit (edge e, bool new_edge,
*** 994,1000 ****
cloop = find_common_loop (e->src->loop_father, e->dest->loop_father);
for (aloop = e->src->loop_father;
aloop != cloop;
! aloop = aloop->outer)
{
exit = XNEW (struct loop_exit);
exit->e = e;
--- 998,1004 ----
cloop = find_common_loop (e->src->loop_father, e->dest->loop_father);
for (aloop = e->src->loop_father;
aloop != cloop;
! aloop = loop_outer (aloop))
{
exit = XNEW (struct loop_exit);
exit->e = e;
*************** num_loop_branches (const struct loop *lo
*** 1161,1176 ****
void
add_bb_to_loop (basic_block bb, struct loop *loop)
{
! int i;
edge_iterator ei;
edge e;
gcc_assert (bb->loop_father == NULL);
bb->loop_father = loop;
! bb->loop_depth = loop->depth;
loop->num_nodes++;
! for (i = 0; i < loop->depth; i++)
! loop->pred[i]->num_nodes++;
FOR_EACH_EDGE (e, ei, bb->succs)
{
--- 1165,1181 ----
void
add_bb_to_loop (basic_block bb, struct loop *loop)
{
! unsigned i;
! loop_p ploop;
edge_iterator ei;
edge e;
gcc_assert (bb->loop_father == NULL);
bb->loop_father = loop;
! bb->loop_depth = loop_depth (loop);
loop->num_nodes++;
! for (i = 0; VEC_iterate (loop_p, loop->superloops, i, ploop); i++)
! ploop->num_nodes++;
FOR_EACH_EDGE (e, ei, bb->succs)
{
*************** remove_bb_from_loops (basic_block bb)
*** 1188,1200 ****
{
int i;
struct loop *loop = bb->loop_father;
edge_iterator ei;
edge e;
gcc_assert (loop != NULL);
loop->num_nodes--;
! for (i = 0; i < loop->depth; i++)
! loop->pred[i]->num_nodes--;
bb->loop_father = NULL;
bb->loop_depth = 0;
--- 1193,1206 ----
{
int i;
struct loop *loop = bb->loop_father;
+ loop_p ploop;
edge_iterator ei;
edge e;
gcc_assert (loop != NULL);
loop->num_nodes--;
! for (i = 0; VEC_iterate (loop_p, loop->superloops, i, ploop); i++)
! ploop->num_nodes--;
bb->loop_father = NULL;
bb->loop_depth = 0;
*************** remove_bb_from_loops (basic_block bb)
*** 1212,1229 ****
struct loop *
find_common_loop (struct loop *loop_s, struct loop *loop_d)
{
if (!loop_s) return loop_d;
if (!loop_d) return loop_s;
! if (loop_s->depth < loop_d->depth)
! loop_d = loop_d->pred[loop_s->depth];
! else if (loop_s->depth > loop_d->depth)
! loop_s = loop_s->pred[loop_d->depth];
while (loop_s != loop_d)
{
! loop_s = loop_s->outer;
! loop_d = loop_d->outer;
}
return loop_s;
}
--- 1218,1240 ----
struct loop *
find_common_loop (struct loop *loop_s, struct loop *loop_d)
{
+ unsigned sdepth, ddepth;
+
if (!loop_s) return loop_d;
if (!loop_d) return loop_s;
! sdepth = loop_depth (loop_s);
! ddepth = loop_depth (loop_d);
!
! if (sdepth < ddepth)
! loop_d = VEC_index (loop_p, loop_d->superloops, sdepth);
! else if (sdepth > ddepth)
! loop_s = VEC_index (loop_p, loop_s->superloops, ddepth);
while (loop_s != loop_d)
{
! loop_s = loop_outer (loop_s);
! loop_d = loop_outer (loop_d);
}
return loop_s;
}
*************** cancel_loop (struct loop *loop)
*** 1250,1262 ****
{
basic_block *bbs;
unsigned i;
gcc_assert (!loop->inner);
/* Move blocks up one level (they should be removed as soon as possible). */
bbs = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
! bbs[i]->loop_father = loop->outer;
delete_loop (loop);
}
--- 1261,1274 ----
{
basic_block *bbs;
unsigned i;
+ struct loop *outer = loop_outer (loop);
gcc_assert (!loop->inner);
/* Move blocks up one level (they should be removed as soon as possible). */
bbs = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
! bbs[i]->loop_father = outer;
delete_loop (loop);
}
*************** verify_loop_structure (void)
*** 1295,1301 ****
sizes[0] = 2;
FOR_EACH_BB (bb)
! for (loop = bb->loop_father; loop; loop = loop->outer)
sizes[loop->num]++;
FOR_EACH_LOOP (li, loop, LI_INCLUDE_ROOT)
--- 1307,1313 ----
sizes[0] = 2;
FOR_EACH_BB (bb)
! for (loop = bb->loop_father; loop; loop = loop_outer (loop))
sizes[loop->num]++;
FOR_EACH_LOOP (li, loop, LI_INCLUDE_ROOT)
*************** verify_loop_structure (void)
*** 1494,1500 ****
for (loop = bb->loop_father;
loop != e->dest->loop_father;
! loop = loop->outer)
{
eloops--;
sizes[loop->num]++;
--- 1506,1512 ----
for (loop = bb->loop_father;
loop != e->dest->loop_father;
! loop = loop_outer (loop))
{
eloops--;
sizes[loop->num]++;
Index: cfgloop.h
===================================================================
*** cfgloop.h (revision 124618)
--- cfgloop.h (working copy)
*************** struct loop_exit
*** 85,90 ****
--- 85,94 ----
struct loop_exit *next_e;
};
+ typedef struct loop *loop_p;
+ DEF_VEC_P (loop_p);
+ DEF_VEC_ALLOC_P (loop_p, heap);
+
/* Structure to hold information for each natural loop. */
struct loop
{
*************** struct loop
*** 109,122 ****
/* Number of blocks contained within the loop. */
unsigned num_nodes;
! /* The loop nesting depth. */
! int depth;
!
! /* Superloops of the loop. */
! struct loop **pred;
!
! /* The outer (parent) loop or NULL if outermost loop. */
! struct loop *outer;
/* The first inner (child) loop or NULL if innermost loop. */
struct loop *inner;
--- 113,120 ----
/* Number of blocks contained within the loop. */
unsigned num_nodes;
! /* Superloops of the loop, starting with the outermost loop. */
! VEC (loop_p, heap) *superloops;
/* The first inner (child) loop or NULL if innermost loop. */
struct loop *inner;
*************** enum
*** 178,187 ****
| LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
#define AVOID_CFG_MODIFICATIONS (LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
- typedef struct loop *loop_p;
- DEF_VEC_P (loop_p);
- DEF_VEC_ALLOC_P (loop_p, heap);
-
/* Structure to hold CFG information about natural loops within a function. */
struct loops
{
--- 176,181 ----
*************** get_loop (unsigned num)
*** 410,415 ****
--- 404,431 ----
return VEC_index (loop_p, current_loops->larray, num);
}
+ /* Returns the number of superloops of LOOP. */
+
+ static inline unsigned
+ loop_depth (const struct loop *loop)
+ {
+ return VEC_length (loop_p, loop->superloops);
+ }
+
+ /* Returns the immediate superloop of LOOP, or NULL if LOOP is the outermost
+ loop. */
+
+ static inline struct loop *
+ loop_outer (const struct loop *loop)
+ {
+ unsigned n = VEC_length (loop_p, loop->superloops);
+
+ if (n == 0)
+ return NULL;
+
+ return VEC_index (loop_p, loop->superloops, n - 1);
+ }
+
/* Returns the list of loops in current_loops. */
static inline VEC (loop_p, heap) *
*************** fel_init (loop_iterator *li, loop_p *loo
*** 519,528 ****
aloop = aloop->inner)
continue;
}
! else if (!aloop->outer)
break;
else
! aloop = aloop->outer;
}
}
else
--- 535,544 ----
aloop = aloop->inner)
continue;
}
! else if (!loop_outer (aloop))
break;
else
! aloop = loop_outer (aloop);
}
}
else
*************** fel_init (loop_iterator *li, loop_p *loo
*** 539,545 ****
else
{
while (aloop != NULL && aloop->next == NULL)
! aloop = aloop->outer;
if (aloop == NULL)
break;
aloop = aloop->next;
--- 555,561 ----
else
{
while (aloop != NULL && aloop->next == NULL)
! aloop = loop_outer (aloop);
if (aloop == NULL)
break;
aloop = aloop->next;
Index: tree-cfg.c
===================================================================
*** tree-cfg.c (revision 124618)
--- tree-cfg.c (working copy)
*************** tree_duplicate_sese_region (edge entry,
*** 4367,4373 ****
if (loop->header == entry->dest)
{
copying_header = true;
! loop->copy = loop->outer;
if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
return false;
--- 4367,4373 ----
if (loop->header == entry->dest)
{
copying_header = true;
! loop->copy = loop_outer (loop);
if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
return false;