This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] Update loops in cfg manipulation functions
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Mon, 23 Oct 2006 10:53:31 +0200
- Subject: [patch] Update loops in cfg manipulation functions
Hello,
this patch makes cfg manipulation functions (in cfghooks.c) update loops
automatically if they are available.
At the moment, cfg manipulation functions do not update loop structures;
if you need that, you must use specialized versions of them. This makes
it difficult to write a code that should work both if loops were
analyzed and if they were not (at the moment there is not much of such
code, but one example will be the OMP expansion code that will be
required to run also in the loop parallelization).
Another motivation for changing this behavior is the project to enable
access to loop information to most of the passes
(http://gcc.gnu.org/wiki/PreservingLoops) -- once loops are preserved
most of the time, it would be quite cumbersome to use specialized
functions to update cfg everywhere.
Finally, also the functions that manipulate loops turn out to be a bit
simpler this way, as in some cases, they no longer need to update loops
explicitly.
To achieve this behavior, all passes are taught to use global current_loops
variable. Since there may be only one such structure per function
(there are links to it from cfg), I moved current_loops to struct function.
Bootstrapped (with -funroll-all-loops -fpeel-loops -funswitch-loops -fprofile-generate
-ftree-vectorize) and regtested on i686, x86_64 and ppc.
Zdenek
* tree-vrp.c (execute_vrp): Do not update current_loops.
* loop-unswitch.c (unswitch_loop): Do not use loop_split_edge_with.
* doc/loop.texi: Remove documentation for cancelled functions.
* tree-ssa-loop-im.c (loop_commit_inserts): Removed.
(move_computations, determine_lsm): Use bsi_commit_edge_inserts
instead.
* cfgloopmanip.c (remove_bbs): Do not update loops explicitly.
(remove_path): Ensure that in delete_basic_blocks, the loops
are still allocated.
(add_loop): Work on valid loop structures.
(loopify): Modify call of add_loop.
(mfb_update_loops): Removed.
(create_preheader): Do not update loops explicitly.
(force_single_succ_latches, loop_version): Do not use
loop_split_edge_with.
(loop_split_edge_with): Removed.
* tree-ssa-loop-manip.c (create_iv, determine_exit_conditions):
Do not use bsi_insert_on_edge_immediate_loop.
(split_loop_exit_edge, tree_unroll_loop): Do not use
loop_split_edge_with.
(bsi_insert_on_edge_immediate_loop): Removed.
* tree-ssa-loop-ch.c (copy_loop_headers): Use current_loops. Do not
use loop_split_edge_with.
* cfghooks.c: Include cfgloop.h.
(verify_flow_info): Verify that loop_father is filled iff current_loops
are available.
(redirect_edge_and_branch_force, split_block, delete_basic_block,
split_edge, merge_blocks, make_forwarder_block, duplicate_block):
Update cfg.
* cfgloopanal.c (mark_irreducible_loops): Work if the function contains
no loops.
* modulo-sched.c (generate_prolog_epilog, canon_loop): Do not use
loop_split_edge_with.
(sms_schedule): Use current_loops.
* tree-ssa-dom.c (tree_ssa_dominator_optimize): Use current_loops.
* loop-init.c (loop_optimizer_init, loop_optimizer_finalize): Set
current_loops.
(rtl_loop_init, rtl_loop_done): Do not set current_loops.
* tree-ssa-sink.c (execute_sink_code): Use current_loops.
* ifcvt.c (if_convert): Ditto.
* predict.c (predict_loops): Do not clear current_loops.
(tree_estimate_probability): Use current_loops.
(propagate_freq): Receive head of the region to propagate instead of
loop.
(estimate_loops_at_level): Do not use shared to_visit bitmap.
(estimate_loops): New function. Handle case current_loops == NULL.
(estimate_bb_frequencies): Do not allocate tovisit. Use
estimate_loops.
* tree-ssa-loop.c (current_loops): Removed.
(tree_loop_optimizer_init): Do not return loops.
(tree_ssa_loop_init, tree_ssa_loop_done): Do not set current_loops.
* tree-vectorizer.c (slpeel_update_phi_nodes_for_guard1,
slpeel_update_phi_nodes_for_guard2, slpeel_tree_peel_loop_to_edge):
Do not update loops explicitly.
* function.h (struct function): Add x_current_loops field.
(current_loops): New macro.
* tree-if-conv.c (combine_blocks): Do not update loops explicitly.
* loop-unroll.c (split_edge_and_insert): New function.
(unroll_loop_runtime_iterations, analyze_insns_in_loop): Do not
use loop_split_edge_with.
* loop-doloop.c (add_test, doloop_modify): Ditto.
* tree-ssa-pre.c (init_pre, fini_pre): Do not set current_loops.
* cfglayout.c (copy_bbs): Do not update loops explicitly.
* lambda-code.c (perfect_nestify): Do not use loop_split_edge_with.
* tree-vect-transform.c (vect_transform_loop): Do not update loops
explicitly.
* cfgloop.c (flow_loops_cfg_dump): Do not dump dfs_order and rc_order.
(flow_loops_free): Do not free dfs_order and rc_order.
(flow_loops_find): Do not set dfs_order and rc_order in loops
structure. Do not call loops and flow info verification.
(add_bb_to_loop, remove_bb_from_loops): Check whether the block
already belongs to some loop.
* cfgloop.h (struct loops): Remove struct cfg.
(current_loops, loop_split_edge_with): Declaration removed.
(loop_optimizer_init, loop_optimizer_finalize): Declaration changed.
* tree-flow.h (loop_commit_inserts, bsi_insert_on_edge_immediate_loop):
Declaration removed.
* Makefile.in (cfghooks.o): Add CFGLOOP_H dependency.
* basic-block.h (split_edge_and_insert): Declare.
* tree-cfg.c (remove_bb): Do not update loops explicitly.
Index: tree-vrp.c
===================================================================
*** tree-vrp.c (revision 117970)
--- tree-vrp.c (working copy)
*************** execute_vrp (void)
*** 4781,4787 ****
{
insert_range_assertions ();
! current_loops = loop_optimizer_init (LOOPS_NORMAL);
if (current_loops)
scev_initialize (current_loops);
--- 4781,4787 ----
{
insert_range_assertions ();
! loop_optimizer_init (LOOPS_NORMAL);
if (current_loops)
scev_initialize (current_loops);
*************** execute_vrp (void)
*** 4792,4799 ****
if (current_loops)
{
scev_finalize ();
! loop_optimizer_finalize (current_loops);
! current_loops = NULL;
}
/* ASSERT_EXPRs must be removed before finalizing jump threads
--- 4792,4798 ----
if (current_loops)
{
scev_finalize ();
! loop_optimizer_finalize ();
}
/* ASSERT_EXPRs must be removed before finalizing jump threads
Index: loop-unswitch.c
===================================================================
*** loop-unswitch.c (revision 117970)
--- loop-unswitch.c (working copy)
*************** unswitch_loop (struct loops *loops, stru
*** 480,487 ****
fix_loop_placement (nloop);
/* Preserve the simple loop preheaders. */
! loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
! loop_split_edge_with (loop_preheader_edge (nloop), NULL_RTX);
return nloop;
}
--- 480,487 ----
fix_loop_placement (nloop);
/* Preserve the simple loop preheaders. */
! split_edge (loop_preheader_edge (loop));
! split_edge (loop_preheader_edge (nloop));
return nloop;
}
Index: doc/loop.texi
===================================================================
*** doc/loop.texi (revision 117970)
--- doc/loop.texi (working copy)
*************** The loops tree can be manipulated using
*** 195,213 ****
@item @code{remove_bb_from_loops}: Removes a basic block from loops.
@end itemize
! The specialized versions of several low-level CFG functions that also
! update loop structures are provided:
@itemize
- @item @code{loop_split_edge_with}: Splits an edge, and places a
- specified RTL code on it. On GIMPLE, the function can still be used,
- but the code must be NULL.
- @item @code{bsi_insert_on_edge_immediate_loop}: Inserts code on edge,
- splitting it if necessary. Only works on GIMPLE.
@item @code{remove_path}: Removes an edge and all blocks it dominates.
- @item @code{loop_commit_inserts}: Commits insertions scheduled on edges,
- and sets loops for the new blocks. This function can only be used on
- GIMPLE.
@item @code{split_loop_exit_edge}: Splits exit edge of the loop,
ensuring that PHI node arguments remain in the loop (this ensures that
loop-closed SSA form is preserved). Only useful on GIMPLE.
--- 195,205 ----
@item @code{remove_bb_from_loops}: Removes a basic block from loops.
@end itemize
! Most low-level CFG functions update loops automatically. The following
! functions handle some more complicated cases of CFG manipulations:
@itemize
@item @code{remove_path}: Removes an edge and all blocks it dominates.
@item @code{split_loop_exit_edge}: Splits exit edge of the loop,
ensuring that PHI node arguments remain in the loop (this ensures that
loop-closed SSA form is preserved). Only useful on GIMPLE.
Index: tree-ssa-loop-im.c
===================================================================
*** tree-ssa-loop-im.c (revision 117970)
--- tree-ssa-loop-im.c (working copy)
*************** determine_invariantness (void)
*** 690,714 ****
fini_walk_dominator_tree (&walk_data);
}
- /* Commits edge insertions and updates loop structures. */
-
- void
- loop_commit_inserts (void)
- {
- unsigned old_last_basic_block, i;
- basic_block bb;
-
- old_last_basic_block = last_basic_block;
- bsi_commit_edge_inserts ();
- for (i = old_last_basic_block; i < (unsigned) last_basic_block; i++)
- {
- bb = BASIC_BLOCK (i);
- add_bb_to_loop (bb,
- find_common_loop (single_pred (bb)->loop_father,
- single_succ (bb)->loop_father));
- }
- }
-
/* Hoist the statements in basic block BB out of the loops prescribed by
data stored in LIM_DATA structures associated with each statement. Callback
for walk_dominator_tree. */
--- 690,695 ----
*************** move_computations (void)
*** 778,784 ****
walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
fini_walk_dominator_tree (&walk_data);
! loop_commit_inserts ();
if (need_ssa_update_p ())
rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
}
--- 759,765 ----
walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
fini_walk_dominator_tree (&walk_data);
! bsi_commit_edge_inserts ();
if (need_ssa_update_p ())
rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
}
*************** determine_lsm (struct loops *loops)
*** 1419,1425 ****
loop = loop->outer;
if (loop == loops->tree_root)
{
! loop_commit_inserts ();
return;
}
}
--- 1400,1406 ----
loop = loop->outer;
if (loop == loops->tree_root)
{
! bsi_commit_edge_inserts ();
return;
}
}
Index: cfgloopmanip.c
===================================================================
*** cfgloopmanip.c (revision 117970)
--- cfgloopmanip.c (working copy)
*************** static void remove_bbs (basic_block *, i
*** 40,46 ****
static bool rpe_enum_p (basic_block, void *);
static int find_path (edge, basic_block **);
static bool alp_enum_p (basic_block, void *);
- static void add_loop (struct loops *, struct loop *);
static void fix_loop_placements (struct loops *, struct loop *, bool *);
static bool fix_bb_placement (struct loops *, basic_block);
static void fix_bb_placements (struct loops *, basic_block, bool *);
--- 40,45 ----
*************** rpe_enum_p (basic_block bb, void *data)
*** 58,75 ****
return dominated_by_p (CDI_DOMINATORS, bb, data);
}
! /* Remove basic blocks BBS from loop structure and dominance info,
! and delete them afterwards. */
static void
remove_bbs (basic_block *bbs, int nbbs)
{
int i;
for (i = 0; i < nbbs; i++)
! {
! remove_bb_from_loops (bbs[i]);
! delete_basic_block (bbs[i]);
! }
}
/* Find path -- i.e. the basic blocks dominated by edge E and put them
--- 57,71 ----
return dominated_by_p (CDI_DOMINATORS, bb, data);
}
! /* Remove basic blocks BBS. NBBS is the number of the basic blocks. */
!
static void
remove_bbs (basic_block *bbs, int nbbs)
{
int i;
for (i = 0; i < nbbs; i++)
! delete_basic_block (bbs[i]);
}
/* Find path -- i.e. the basic blocks dominated by edge E and put them
*************** remove_path (struct loops *loops, edge e
*** 247,255 ****
{
edge ae;
basic_block *rem_bbs, *bord_bbs, *dom_bbs, from, bb;
! int i, nrem, n_bord_bbs, n_dom_bbs;
sbitmap seen;
bool deleted, irred_invalidated = false;
if (!loop_delete_branch_edge (e, 0))
return false;
--- 243,252 ----
{
edge ae;
basic_block *rem_bbs, *bord_bbs, *dom_bbs, from, bb;
! int i, nrem, n_bord_bbs, n_dom_bbs, nreml;
sbitmap seen;
bool deleted, irred_invalidated = false;
+ struct loop **deleted_loop;
if (!loop_delete_branch_edge (e, 0))
return false;
*************** remove_path (struct loops *loops, edge e
*** 267,273 ****
fix -- when e->dest has exactly one predecessor, this corresponds
to blocks dominated by e->dest, if not, split the edge. */
if (!single_pred_p (e->dest))
! e = single_pred_edge (loop_split_edge_with (e, NULL_RTX));
/* It may happen that by removing path we remove one or more loops
we belong to. In this case first unloop the loops, then proceed
--- 264,270 ----
fix -- when e->dest has exactly one predecessor, this corresponds
to blocks dominated by e->dest, if not, split the edge. */
if (!single_pred_p (e->dest))
! e = single_pred_edge (split_edge (e));
/* It may happen that by removing path we remove one or more loops
we belong to. In this case first unloop the loops, then proceed
*************** remove_path (struct loops *loops, edge e
*** 311,323 ****
dom_bbs = XCNEWVEC (basic_block, n_basic_blocks);
/* Cancel loops contained in the path. */
for (i = 0; i < nrem; i++)
if (rem_bbs[i]->loop_father->header == rem_bbs[i])
! cancel_loop_tree (loops, rem_bbs[i]->loop_father);
remove_bbs (rem_bbs, nrem);
free (rem_bbs);
/* Find blocks whose dominators may be affected. */
n_dom_bbs = 0;
sbitmap_zero (seen);
--- 308,326 ----
dom_bbs = XCNEWVEC (basic_block, n_basic_blocks);
/* Cancel loops contained in the path. */
+ deleted_loop = XNEWVEC (struct loop *, nrem);
+ nreml = 0;
for (i = 0; i < nrem; i++)
if (rem_bbs[i]->loop_father->header == rem_bbs[i])
! deleted_loop[nreml++] = rem_bbs[i]->loop_father;
remove_bbs (rem_bbs, nrem);
free (rem_bbs);
+ for (i = 0; i < nreml; i++)
+ cancel_loop_tree (loops, deleted_loop[i]);
+ free (deleted_loop);
+
/* Find blocks whose dominators may be affected. */
n_dom_bbs = 0;
sbitmap_zero (seen);
*************** alp_enum_p (basic_block bb, void *alp_he
*** 364,378 ****
}
/* Given LOOP structure with filled header and latch, find the body of the
! corresponding loop and add it to LOOPS tree. */
static void
! add_loop (struct loops *loops, struct loop *loop)
{
basic_block *bbs;
int i, n;
/* Add it to loop structure. */
place_new_loop (loops, loop);
loop->level = 1;
/* Find its nodes. */
--- 367,384 ----
}
/* Given LOOP structure with filled header and latch, find the body of the
! corresponding loop and add it to LOOPS tree. Insert the LOOP as a son of
! outer. */
!
static void
! add_loop (struct loops *loops, struct loop *loop, struct loop *outer)
{
basic_block *bbs;
int i, n;
/* Add it to loop structure. */
place_new_loop (loops, loop);
+ flow_loop_tree_node_add (outer, loop);
loop->level = 1;
/* Find its nodes. */
*************** add_loop (struct loops *loops, struct lo
*** 381,387 ****
bbs, n_basic_blocks, loop->header);
for (i = 0; i < n; i++)
! add_bb_to_loop (bbs[i], loop);
add_bb_to_loop (loop->header, loop);
free (bbs);
--- 387,397 ----
bbs, n_basic_blocks, loop->header);
for (i = 0; i < n; i++)
! {
! remove_bb_from_loops (bbs[i]);
! add_bb_to_loop (bbs[i], loop);
! }
! remove_bb_from_loops (loop->header);
add_bb_to_loop (loop->header, loop);
free (bbs);
*************** loopify (struct loops *loops, edge latch
*** 453,462 ****
set_immediate_dominator (CDI_DOMINATORS, succ_bb, switch_bb);
/* Compute new loop. */
! add_loop (loops, loop);
! flow_loop_tree_node_add (outer, loop);
/* Add switch_bb to appropriate loop. */
add_bb_to_loop (switch_bb, outer);
/* Fix frequencies. */
--- 463,473 ----
set_immediate_dominator (CDI_DOMINATORS, succ_bb, switch_bb);
/* Compute new loop. */
! add_loop (loops, loop, outer);
/* Add switch_bb to appropriate loop. */
+ if (switch_bb->loop_father)
+ remove_bb_from_loops (switch_bb);
add_bb_to_loop (switch_bb, outer);
/* Fix frequencies. */
*************** mfb_keep_just (edge e)
*** 1068,1088 ****
return e != mfb_kj_edge;
}
- /* A callback for make_forwarder block, to update data structures for a basic
- block JUMP created by redirecting an edge (only the latch edge is being
- redirected). */
-
- static void
- mfb_update_loops (basic_block jump)
- {
- struct loop *loop = single_succ (jump)->loop_father;
-
- if (dom_computed[CDI_DOMINATORS])
- set_immediate_dominator (CDI_DOMINATORS, jump, single_pred (jump));
- add_bb_to_loop (jump, loop);
- loop->latch = jump;
- }
-
/* Creates a pre-header for a LOOP. Returns newly created block. Unless
CP_SIMPLE_PREHEADERS is set in FLAGS, we only force LOOP to have single
entry; otherwise we also force preheader block to have only one successor.
--- 1079,1084 ----
*************** create_preheader (struct loop *loop, int
*** 1093,1107 ****
{
edge e, fallthru;
basic_block dummy;
- struct loop *cloop, *ploop;
int nentry = 0;
bool irred = false;
bool latch_edge_was_fallthru;
edge one_succ_pred = 0;
edge_iterator ei;
- cloop = loop->outer;
-
FOR_EACH_EDGE (e, ei, loop->header->preds)
{
if (e->src == loop->latch)
--- 1089,1100 ----
*************** create_preheader (struct loop *loop, int
*** 1125,1141 ****
mfb_kj_edge = loop_latch_edge (loop);
latch_edge_was_fallthru = (mfb_kj_edge->flags & EDGE_FALLTHRU) != 0;
! fallthru = make_forwarder_block (loop->header, mfb_keep_just,
! mfb_update_loops);
dummy = fallthru->src;
loop->header = fallthru->dest;
- /* The header could be a latch of some superloop(s); due to design of
- split_block, it would now move to fallthru->dest. */
- for (ploop = loop; ploop; ploop = ploop->outer)
- if (ploop->latch == dummy)
- ploop->latch = fallthru->dest;
-
/* Try to be clever in placing the newly created preheader. The idea is to
avoid breaking any "fallthruness" relationship between blocks.
--- 1118,1127 ----
mfb_kj_edge = loop_latch_edge (loop);
latch_edge_was_fallthru = (mfb_kj_edge->flags & EDGE_FALLTHRU) != 0;
! fallthru = make_forwarder_block (loop->header, mfb_keep_just, NULL);
dummy = fallthru->src;
loop->header = fallthru->dest;
/* Try to be clever in placing the newly created preheader. The idea is to
avoid breaking any "fallthruness" relationship between blocks.
*************** create_preheader (struct loop *loop, int
*** 1154,1162 ****
move_block_after (dummy, e->src);
}
- loop->header->loop_father = loop;
- add_bb_to_loop (dummy, cloop);
-
if (irred)
{
dummy->flags |= BB_IRREDUCIBLE_LOOP;
--- 1140,1145 ----
*************** force_single_succ_latches (struct loops
*** 1198,1238 ****
e = find_edge (loop->latch, loop->header);
! loop_split_edge_with (e, NULL_RTX);
}
loops->state |= LOOPS_HAVE_SIMPLE_LATCHES;
}
- /* A quite stupid function to put INSNS on edge E. They are supposed to form
- just one basic block. Jumps in INSNS are not handled, so cfg do not have to
- be ok after this function. The created block is placed on correct place
- in LOOPS structure and its dominator is set. */
- basic_block
- loop_split_edge_with (edge e, rtx insns)
- {
- basic_block src, dest, new_bb;
- struct loop *loop_c;
-
- src = e->src;
- dest = e->dest;
-
- loop_c = find_common_loop (src->loop_father, dest->loop_father);
-
- /* Create basic block for it. */
-
- new_bb = split_edge (e);
- add_bb_to_loop (new_bb, loop_c);
- new_bb->flags |= (insns ? BB_SUPERBLOCK : 0);
-
- if (insns)
- emit_insn_after (insns, BB_END (new_bb));
-
- if (dest->loop_father->latch == src)
- dest->loop_father->latch = new_bb;
-
- return new_bb;
- }
-
/* This function is called from loop_version. It splits the entry edge
of the loop we want to version, adds the versioning condition, and
adjust the edges to the two versions of the loop appropriately.
--- 1181,1191 ----
e = find_edge (loop->latch, loop->header);
! split_edge (e);
}
loops->state |= LOOPS_HAVE_SIMPLE_LATCHES;
}
/* This function is called from loop_version. It splits the entry edge
of the loop we want to version, adds the versioning condition, and
adjust the edges to the two versions of the loop appropriately.
*************** loop_version (struct loops *loops, struc
*** 1380,1387 ****
/* At this point condition_bb is loop predheader with two successors,
first_head and second_head. Make sure that loop predheader has only
one successor. */
! loop_split_edge_with (loop_preheader_edge (loop), NULL);
! loop_split_edge_with (loop_preheader_edge (nloop), NULL);
return nloop;
}
--- 1333,1340 ----
/* At this point condition_bb is loop predheader with two successors,
first_head and second_head. Make sure that loop predheader has only
one successor. */
! split_edge (loop_preheader_edge (loop));
! split_edge (loop_preheader_edge (nloop));
return nloop;
}
Index: tree-ssa-loop-manip.c
===================================================================
*** tree-ssa-loop-manip.c (revision 117970)
--- tree-ssa-loop-manip.c (working copy)
*************** create_iv (tree base, tree step, tree va
*** 98,104 ****
loop (i.e. the step should be loop invariant). */
step = force_gimple_operand (step, &stmts, true, var);
if (stmts)
! bsi_insert_on_edge_immediate_loop (pe, stmts);
stmt = build2 (MODIFY_EXPR, void_type_node, va,
build2 (incr_op, TREE_TYPE (base),
--- 98,104 ----
loop (i.e. the step should be loop invariant). */
step = force_gimple_operand (step, &stmts, true, var);
if (stmts)
! bsi_insert_on_edge_immediate (pe, stmts);
stmt = build2 (MODIFY_EXPR, void_type_node, va,
build2 (incr_op, TREE_TYPE (base),
*************** create_iv (tree base, tree step, tree va
*** 111,117 ****
initial = force_gimple_operand (base, &stmts, true, var);
if (stmts)
! bsi_insert_on_edge_immediate_loop (pe, stmts);
stmt = create_phi_node (vb, loop->header);
SSA_NAME_DEF_STMT (vb) = stmt;
--- 111,117 ----
initial = force_gimple_operand (base, &stmts, true, var);
if (stmts)
! bsi_insert_on_edge_immediate (pe, stmts);
stmt = create_phi_node (vb, loop->header);
SSA_NAME_DEF_STMT (vb) = stmt;
*************** void
*** 445,451 ****
split_loop_exit_edge (edge exit)
{
basic_block dest = exit->dest;
! basic_block bb = loop_split_edge_with (exit, NULL);
tree phi, new_phi, new_name, name;
use_operand_p op_p;
--- 445,451 ----
split_loop_exit_edge (edge exit)
{
basic_block dest = exit->dest;
! basic_block bb = split_edge (exit);
tree phi, new_phi, new_name, name;
use_operand_p op_p;
*************** split_loop_exit_edge (edge exit)
*** 470,501 ****
}
}
- /* Insert statement STMT to the edge E and update the loop structures.
- Returns the newly created block (if any). */
-
- basic_block
- bsi_insert_on_edge_immediate_loop (edge e, tree stmt)
- {
- basic_block src, dest, new_bb;
- struct loop *loop_c;
-
- src = e->src;
- dest = e->dest;
-
- loop_c = find_common_loop (src->loop_father, dest->loop_father);
-
- new_bb = bsi_insert_on_edge_immediate (e, stmt);
-
- if (!new_bb)
- return NULL;
-
- add_bb_to_loop (new_bb, loop_c);
- if (dest->loop_father->latch == src)
- dest->loop_father->latch = new_bb;
-
- return new_bb;
- }
-
/* Returns the basic block in that statements should be emitted for induction
variables incremented at the end of the LOOP. */
--- 470,475 ----
*************** determine_exit_conditions (struct loop *
*** 749,755 ****
cond = force_gimple_operand (unshare_expr (cond), &stmts, false, NULL_TREE);
if (stmts)
! bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts);
/* cond now may be a gimple comparison, which would be OK, but also any
other gimple rhs (say a && b). In this case we need to force it to
operand. */
--- 723,729 ----
cond = force_gimple_operand (unshare_expr (cond), &stmts, false, NULL_TREE);
if (stmts)
! bsi_insert_on_edge_immediate (loop_preheader_edge (loop), stmts);
/* cond now may be a gimple comparison, which would be OK, but also any
other gimple rhs (say a && b). In this case we need to force it to
operand. */
*************** determine_exit_conditions (struct loop *
*** 757,772 ****
{
cond = force_gimple_operand (cond, &stmts, true, NULL_TREE);
if (stmts)
! bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts);
}
*enter_cond = cond;
base = force_gimple_operand (unshare_expr (base), &stmts, true, NULL_TREE);
if (stmts)
! bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts);
bound = force_gimple_operand (unshare_expr (bound), &stmts, true, NULL_TREE);
if (stmts)
! bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts);
*exit_base = base;
*exit_step = bigstep;
--- 731,746 ----
{
cond = force_gimple_operand (cond, &stmts, true, NULL_TREE);
if (stmts)
! bsi_insert_on_edge_immediate (loop_preheader_edge (loop), stmts);
}
*enter_cond = cond;
base = force_gimple_operand (unshare_expr (base), &stmts, true, NULL_TREE);
if (stmts)
! bsi_insert_on_edge_immediate (loop_preheader_edge (loop), stmts);
bound = force_gimple_operand (unshare_expr (bound), &stmts, true, NULL_TREE);
if (stmts)
! bsi_insert_on_edge_immediate (loop_preheader_edge (loop), stmts);
*exit_base = base;
*exit_step = bigstep;
*************** tree_unroll_loop (struct loops *loops, s
*** 881,887 ****
/* Prepare the cfg and update the phi nodes. */
rest = loop_preheader_edge (new_loop)->src;
precond_edge = single_pred_edge (rest);
! loop_split_edge_with (loop_latch_edge (loop), NULL);
exit_bb = single_pred (loop->latch);
new_exit = make_edge (exit_bb, rest, EDGE_FALSE_VALUE | irr);
--- 855,861 ----
/* Prepare the cfg and update the phi nodes. */
rest = loop_preheader_edge (new_loop)->src;
precond_edge = single_pred_edge (rest);
! split_edge (loop_latch_edge (loop));
exit_bb = single_pred (loop->latch);
new_exit = make_edge (exit_bb, rest, EDGE_FALSE_VALUE | irr);
Index: tree-ssa-loop-ch.c
===================================================================
*** tree-ssa-loop-ch.c (revision 117970)
--- tree-ssa-loop-ch.c (working copy)
*************** do_while_loop_p (struct loop *loop)
*** 123,129 ****
static unsigned int
copy_loop_headers (void)
{
- struct loops *loops;
unsigned i;
struct loop *loop;
basic_block header;
--- 123,128 ----
*************** copy_loop_headers (void)
*** 132,156 ****
unsigned n_bbs;
unsigned bbs_size;
! loops = loop_optimizer_init (LOOPS_HAVE_PREHEADERS
! | LOOPS_HAVE_SIMPLE_LATCHES);
! if (!loops)
return 0;
#ifdef ENABLE_CHECKING
! verify_loop_structure (loops);
#endif
bbs = XNEWVEC (basic_block, n_basic_blocks);
copied_bbs = XNEWVEC (basic_block, n_basic_blocks);
bbs_size = n_basic_blocks;
! for (i = 1; i < loops->num; i++)
{
/* Copy at most 20 insns. */
int limit = 20;
! loop = loops->parray[i];
if (!loop)
continue;
header = loop->header;
--- 131,155 ----
unsigned n_bbs;
unsigned bbs_size;
! loop_optimizer_init (LOOPS_HAVE_PREHEADERS
! | LOOPS_HAVE_SIMPLE_LATCHES);
! if (!current_loops)
return 0;
#ifdef ENABLE_CHECKING
! verify_loop_structure (current_loops);
#endif
bbs = XNEWVEC (basic_block, n_basic_blocks);
copied_bbs = XNEWVEC (basic_block, n_basic_blocks);
bbs_size = n_basic_blocks;
! for (i = 1; i < current_loops->num; i++)
{
/* Copy at most 20 insns. */
int limit = 20;
! loop = current_loops->parray[i];
if (!loop)
continue;
header = loop->header;
*************** copy_loop_headers (void)
*** 194,200 ****
/* Ensure that the header will have just the latch as a predecessor
inside the loop. */
if (!single_pred_p (exit->dest))
! exit = single_pred_edge (loop_split_edge_with (exit, NULL));
entry = loop_preheader_edge (loop);
--- 193,199 ----
/* Ensure that the header will have just the latch as a predecessor
inside the loop. */
if (!single_pred_p (exit->dest))
! exit = single_pred_edge (split_edge (exit));
entry = loop_preheader_edge (loop);
*************** copy_loop_headers (void)
*** 206,219 ****
/* Ensure that the latch and the preheader is simple (we know that they
are not now, since there was the loop exit condition. */
! loop_split_edge_with (loop_preheader_edge (loop), NULL);
! loop_split_edge_with (loop_latch_edge (loop), NULL);
}
free (bbs);
free (copied_bbs);
! loop_optimizer_finalize (loops);
return 0;
}
--- 205,218 ----
/* Ensure that the latch and the preheader is simple (we know that they
are not now, since there was the loop exit condition. */
! split_edge (loop_preheader_edge (loop));
! split_edge (loop_latch_edge (loop));
}
free (bbs);
free (copied_bbs);
! loop_optimizer_finalize ();
return 0;
}
Index: cfghooks.c
===================================================================
*** cfghooks.c (revision 117970)
--- cfghooks.c (working copy)
*************** Boston, MA 02110-1301, USA. */
*** 29,34 ****
--- 29,35 ----
#include "tree-flow.h"
#include "timevar.h"
#include "toplev.h"
+ #include "cfgloop.h"
/* A pointer to one of the hooks containers. */
static struct cfg_hooks *cfg_hooks;
*************** verify_flow_info (void)
*** 108,113 ****
--- 109,126 ----
edge e;
edge_iterator ei;
+ if (bb->loop_father != NULL && current_loops == NULL)
+ {
+ error ("verify_flow_info: Block %i has loop_father, but there are no loops",
+ bb->index);
+ err = 1;
+ }
+ if (bb->loop_father == NULL && current_loops != NULL)
+ {
+ error ("verify_flow_info: Block %i lacks loop_father", bb->index);
+ err = 1;
+ }
+
if (bb->count < 0)
{
error ("verify_flow_info: Wrong count of block %i %i",
*************** basic_block
*** 301,312 ****
--- 314,332 ----
redirect_edge_and_branch_force (edge e, basic_block dest)
{
basic_block ret;
+ struct loop *loop;
if (!cfg_hooks->redirect_edge_and_branch_force)
internal_error ("%s does not support redirect_edge_and_branch_force",
cfg_hooks->name);
ret = cfg_hooks->redirect_edge_and_branch_force (e, dest);
+ if (current_loops != NULL && ret != NULL)
+ {
+ loop = find_common_loop (single_pred (ret)->loop_father,
+ single_succ (ret)->loop_father);
+ add_bb_to_loop (ret, loop);
+ }
return ret;
}
*************** split_block (basic_block bb, void *i)
*** 337,342 ****
--- 357,365 ----
set_immediate_dominator (CDI_DOMINATORS, new_bb, bb);
}
+ if (current_loops != NULL)
+ add_bb_to_loop (new_bb, bb->loop_father);
+
return make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU);
}
*************** delete_basic_block (basic_block bb)
*** 374,379 ****
--- 397,418 ----
cfg_hooks->delete_basic_block (bb);
+ if (current_loops != NULL)
+ {
+ struct loop *loop = bb->loop_father;
+
+ /* If we remove the header or the latch of a loop, mark the loop for
+ removal by setting its header and latch to NULL. */
+ if (loop->latch == bb
+ || loop->header == bb)
+ {
+ loop->header = NULL;
+ loop->latch = NULL;
+ }
+
+ remove_bb_from_loops (bb);
+ }
+
/* Remove the edges into and out of this block. Note that there may
indeed be edges in, if we are removing an unreachable loop. */
while (EDGE_COUNT (bb->preds) != 0)
*************** split_edge (edge e)
*** 400,405 ****
--- 439,446 ----
int freq = EDGE_FREQUENCY (e);
edge f;
bool irr = (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
+ struct loop *loop;
+ basic_block src = e->src, dest = e->dest;
if (!cfg_hooks->split_edge)
internal_error ("%s does not support split_edge", cfg_hooks->name);
*************** split_edge (edge e)
*** 448,454 ****
if (!f)
set_immediate_dominator (CDI_DOMINATORS, single_succ (ret), ret);
}
! };
return ret;
}
--- 489,504 ----
if (!f)
set_immediate_dominator (CDI_DOMINATORS, single_succ (ret), ret);
}
! }
!
! if (current_loops != NULL)
! {
! loop = find_common_loop (src->loop_father, dest->loop_father);
! add_bb_to_loop (ret, loop);
!
! if (loop->latch == src)
! loop->latch = ret;
! }
return ret;
}
*************** merge_blocks (basic_block a, basic_block
*** 527,532 ****
--- 577,585 ----
if (!cfg_hooks->merge_blocks)
internal_error ("%s does not support merge_blocks", cfg_hooks->name);
+ if (current_loops != NULL)
+ remove_bb_from_loops (b);
+
cfg_hooks->merge_blocks (a, b);
/* Normally there should only be one successor of A and that is B, but
*************** make_forwarder_block (basic_block bb, bo
*** 568,573 ****
--- 621,627 ----
edge e, fallthru;
edge_iterator ei;
basic_block dummy, jump;
+ struct loop *loop, *ploop, *cloop;
if (!cfg_hooks->make_forwarder_block)
internal_error ("%s does not support make_forwarder_block",
*************** make_forwarder_block (basic_block bb, bo
*** 610,615 ****
--- 664,696 ----
iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, 2);
}
+ if (current_loops != NULL)
+ {
+ /* If we do not split a loop header, then both blocks belong to the
+ same loop. In case we split loop header and do not redirect the
+ latch edge to DUMMY, then DUMMY belongs to the outer loop, and
+ BB becomes the new header. */
+ loop = dummy->loop_father;
+ if (loop->header == dummy
+ && find_edge (loop->latch, dummy) == NULL)
+ {
+ remove_bb_from_loops (dummy);
+ loop->header = bb;
+
+ cloop = loop;
+ FOR_EACH_EDGE (e, ei, dummy->preds)
+ {
+ cloop = find_common_loop (cloop, e->src->loop_father);
+ }
+ add_bb_to_loop (dummy, cloop);
+ }
+
+ /* In case we split loop latch, update it. */
+ for (ploop = loop; ploop; ploop = ploop->outer)
+ if (ploop->latch == dummy)
+ ploop->latch = bb;
+ }
+
cfg_hooks->make_forwarder_block (fallthru);
return fallthru;
*************** duplicate_block (basic_block bb, edge e,
*** 761,766 ****
--- 842,851 ----
set_bb_original (new_bb, bb);
set_bb_copy (bb, new_bb);
+ /* Add the new block to the prescribed loop. */
+ if (current_loops != NULL)
+ add_bb_to_loop (new_bb, bb->loop_father->copy);
+
return new_bb;
}
Index: cfgloopanal.c
===================================================================
*** cfgloopanal.c (revision 117970)
--- cfgloopanal.c (working copy)
*************** mark_irreducible_loops (struct loops *lo
*** 273,280 ****
edge_iterator ei;
int i, src, dest;
struct graph *g;
! int *queue1 = XNEWVEC (int, last_basic_block + loops->num);
! int *queue2 = XNEWVEC (int, last_basic_block + loops->num);
int nq, depth;
struct loop *cloop;
--- 273,281 ----
edge_iterator ei;
int i, src, dest;
struct graph *g;
! int num = loops ? loops->num : 1;
! int *queue1 = XNEWVEC (int, last_basic_block + num);
! int *queue2 = XNEWVEC (int, last_basic_block + num);
int nq, depth;
struct loop *cloop;
*************** mark_irreducible_loops (struct loops *lo
*** 287,293 ****
}
/* Create the edge lists. */
! g = new_graph (last_basic_block + loops->num);
FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
FOR_EACH_EDGE (e, ei, act->succs)
--- 288,294 ----
}
/* Create the edge lists. */
! g = new_graph (last_basic_block + num);
FOR_BB_BETWEEN (act, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
FOR_EACH_EDGE (e, ei, act->succs)
*************** mark_irreducible_loops (struct loops *lo
*** 296,330 ****
if (e->dest == EXIT_BLOCK_PTR)
continue;
- /* And latch edges. */
- if (e->dest->loop_father->header == e->dest
- && e->dest->loop_father->latch == act)
- continue;
-
- /* Edges inside a single loop should be left where they are. Edges
- to subloop headers should lead to representative of the subloop,
- but from the same place.
-
- Edges exiting loops should lead from representative
- of the son of nearest common ancestor of the loops in that
- act lays. */
-
src = BB_REPR (act);
dest = BB_REPR (e->dest);
! if (e->dest->loop_father->header == e->dest)
! dest = LOOP_REPR (e->dest->loop_father);
!
! 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);
}
add_edge (g, src, dest, e);
--- 297,334 ----
if (e->dest == EXIT_BLOCK_PTR)
continue;
src = BB_REPR (act);
dest = BB_REPR (e->dest);
! if (loops)
{
! /* Ignore latch edges. */
! if (e->dest->loop_father->header == e->dest
! && e->dest->loop_father->latch == act)
! continue;
!
! /* Edges inside a single loop should be left where they are. Edges
! to subloop headers should lead to representative of the subloop,
! but from the same place.
!
! Edges exiting loops should lead from representative
! of the son of nearest common ancestor of the loops in that
! act lays. */
!
! if (e->dest->loop_father->header == e->dest)
! dest = LOOP_REPR (e->dest->loop_father);
!
! 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);
! }
}
add_edge (g, src, dest, e);
*************** mark_irreducible_loops (struct loops *lo
*** 339,345 ****
{
queue1[nq++] = BB_REPR (act);
}
! for (i = 1; i < (int) loops->num; i++)
if (loops->parray[i])
queue1[nq++] = LOOP_REPR (loops->parray[i]);
dfs (g, queue1, nq, queue2, false);
--- 343,349 ----
{
queue1[nq++] = BB_REPR (act);
}
! for (i = 1; i < num; i++)
if (loops->parray[i])
queue1[nq++] = LOOP_REPR (loops->parray[i]);
dfs (g, queue1, nq, queue2, false);
*************** mark_irreducible_loops (struct loops *lo
*** 354,360 ****
free (queue1);
free (queue2);
! loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
}
/* Counts number of insns inside LOOP. */
--- 358,365 ----
free (queue1);
free (queue2);
! if (loops)
! loops->state |= LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
}
/* Counts number of insns inside LOOP. */
Index: modulo-sched.c
===================================================================
*** modulo-sched.c (revision 117970)
--- modulo-sched.c (working copy)
*************** generate_prolog_epilog (partial_schedule
*** 742,750 ****
for (i = 0; i < last_stage; i++)
duplicate_insns_of_cycles (ps, 0, i, 1);
! /* Put the prolog , on the one and only entry edge. */
e = loop_preheader_edge (loop);
! loop_split_edge_with(e , get_insns());
end_sequence ();
--- 742,750 ----
for (i = 0; i < last_stage; i++)
duplicate_insns_of_cycles (ps, 0, i, 1);
! /* Put the prolog on the entry edge. */
e = loop_preheader_edge (loop);
! split_edge_and_insert (e, get_insns());
end_sequence ();
*************** generate_prolog_epilog (partial_schedule
*** 754,763 ****
for (i = 0; i < last_stage; i++)
duplicate_insns_of_cycles (ps, i + 1, last_stage, 0);
! /* Put the epilogue on the one and only one exit edge. */
gcc_assert (loop->single_exit);
e = loop->single_exit;
! loop_split_edge_with(e , get_insns());
end_sequence ();
}
--- 754,763 ----
for (i = 0; i < last_stage; i++)
duplicate_insns_of_cycles (ps, i + 1, last_stage, 0);
! /* Put the epilogue on the exit edge. */
gcc_assert (loop->single_exit);
e = loop->single_exit;
! split_edge_and_insert (e, get_insns());
end_sequence ();
}
*************** canon_loop (struct loop *loop)
*** 879,885 ****
block. */
FOR_EACH_EDGE (e, i, EXIT_BLOCK_PTR->preds)
if ((e->flags & EDGE_FALLTHRU) && (EDGE_COUNT (e->src->succs) > 1))
! loop_split_edge_with (e, NULL_RTX);
if (loop->latch == loop->header
|| EDGE_COUNT (loop->latch->succs) > 1)
--- 879,885 ----
block. */
FOR_EACH_EDGE (e, i, EXIT_BLOCK_PTR->preds)
if ((e->flags & EDGE_FALLTHRU) && (EDGE_COUNT (e->src->succs) > 1))
! split_edge (e);
if (loop->latch == loop->header
|| EDGE_COUNT (loop->latch->succs) > 1)
*************** canon_loop (struct loop *loop)
*** 887,893 ****
FOR_EACH_EDGE (e, i, loop->header->preds)
if (e->src == loop->latch)
break;
! loop_split_edge_with (e, NULL_RTX);
}
}
--- 887,893 ----
FOR_EACH_EDGE (e, i, loop->header->preds)
if (e->src == loop->latch)
break;
! split_edge (e);
}
}
*************** sms_schedule (void)
*** 904,910 ****
unsigned i,num_loops;
partial_schedule_ptr ps;
struct df *df;
- struct loops *loops;
basic_block bb = NULL;
/* vars to the versioning only if needed*/
struct loop * nloop;
--- 904,909 ----
*************** sms_schedule (void)
*** 912,921 ****
edge latch_edge;
gcov_type trip_count = 0;
! loops = loop_optimizer_init (LOOPS_HAVE_PREHEADERS
! | LOOPS_HAVE_MARKED_SINGLE_EXITS);
! if (!loops)
! return; /* There is no loops to schedule. */
/* Initialize issue_rate. */
if (targetm.sched.issue_rate)
--- 911,920 ----
edge latch_edge;
gcov_type trip_count = 0;
! loop_optimizer_init (LOOPS_HAVE_PREHEADERS
! | LOOPS_HAVE_MARKED_SINGLE_EXITS);
! if (!current_loops)
! return; /* There are no loops to schedule. */
/* Initialize issue_rate. */
if (targetm.sched.issue_rate)
*************** sms_schedule (void)
*** 945,960 ****
/* Allocate memory to hold the DDG array one entry for each loop.
We use loop->num as index into this array. */
! g_arr = XCNEWVEC (ddg_ptr, loops->num);
/* Build DDGs for all the relevant loops and hold them in G_ARR
indexed by the loop index. */
! for (i = 0; i < loops->num; i++)
{
rtx head, tail;
rtx count_reg;
! struct loop *loop = loops->parray[i];
/* For debugging. */
if ((passes++ > MAX_SMS_LOOP_NUMBER) && (MAX_SMS_LOOP_NUMBER != -1))
--- 944,959 ----
/* Allocate memory to hold the DDG array one entry for each loop.
We use loop->num as index into this array. */
! g_arr = XCNEWVEC (ddg_ptr, current_loops->num);
/* Build DDGs for all the relevant loops and hold them in G_ARR
indexed by the loop index. */
! for (i = 0; i < current_loops->num; i++)
{
rtx head, tail;
rtx count_reg;
! struct loop *loop = current_loops->parray[i];
/* For debugging. */
if ((passes++ > MAX_SMS_LOOP_NUMBER) && (MAX_SMS_LOOP_NUMBER != -1))
*************** sms_schedule (void)
*** 1058,1064 ****
df = NULL;
/* We don't want to perform SMS on new loops - created by versioning. */
! num_loops = loops->num;
/* Go over the built DDGs and perfrom SMS for each one of them. */
for (i = 0; i < num_loops; i++)
{
--- 1057,1063 ----
df = NULL;
/* We don't want to perform SMS on new loops - created by versioning. */
! num_loops = current_loops->num;
/* Go over the built DDGs and perfrom SMS for each one of them. */
for (i = 0; i < num_loops; i++)
{
*************** sms_schedule (void)
*** 1067,1073 ****
int mii, rec_mii;
unsigned stage_count = 0;
HOST_WIDEST_INT loop_count = 0;
! struct loop *loop = loops->parray[i];
if (! (g = g_arr[i]))
continue;
--- 1066,1072 ----
int mii, rec_mii;
unsigned stage_count = 0;
HOST_WIDEST_INT loop_count = 0;
! struct loop *loop = current_loops->parray[i];
if (! (g = g_arr[i]))
continue;
*************** sms_schedule (void)
*** 1226,1233 ****
rtx comp_rtx = gen_rtx_fmt_ee (GT, VOIDmode, count_reg,
GEN_INT(stage_count));
! nloop = loop_version (loops, loop, comp_rtx, &condition_bb,
! true);
}
/* Set new iteration count of loop kernel. */
--- 1225,1232 ----
rtx comp_rtx = gen_rtx_fmt_ee (GT, VOIDmode, count_reg,
GEN_INT(stage_count));
! nloop = loop_version (current_loops, loop, comp_rtx,
! &condition_bb, true);
}
/* Set new iteration count of loop kernel. */
*************** sms_schedule (void)
*** 1267,1273 ****
/* Release scheduler data, needed until now because of DFA. */
sched_finish ();
! loop_optimizer_finalize (loops);
}
/* The SMS scheduling algorithm itself
--- 1266,1272 ----
/* Release scheduler data, needed until now because of DFA. */
sched_finish ();
! loop_optimizer_finalize ();
}
/* The SMS scheduling algorithm itself
Index: tree-ssa-dom.c
===================================================================
*** tree-ssa-dom.c (revision 117970)
--- tree-ssa-dom.c (working copy)
*************** tree_ssa_dominator_optimize (void)
*** 240,246 ****
{
struct dom_walk_data walk_data;
unsigned int i;
- struct loops loops_info;
memset (&opt_stats, 0, sizeof (opt_stats));
--- 240,245 ----
*************** tree_ssa_dominator_optimize (void)
*** 276,284 ****
/* We need to know which edges exit loops so that we can
aggressively thread through loop headers to an exit
edge. */
! flow_loops_find (&loops_info);
! mark_loop_exit_edges (&loops_info);
! flow_loops_free (&loops_info);
/* Clean up the CFG so that any forwarder blocks created by loop
canonicalization are removed. */
--- 275,286 ----
/* We need to know which edges exit loops so that we can
aggressively thread through loop headers to an exit
edge. */
! loop_optimizer_init (0);
! if (current_loops)
! {
! mark_loop_exit_edges (current_loops);
! loop_optimizer_finalize ();
! }
/* Clean up the CFG so that any forwarder blocks created by loop
canonicalization are removed. */
Index: loop-init.c
===================================================================
*** loop-init.c (revision 117970)
--- loop-init.c (working copy)
*************** Software Foundation, 51 Franklin Street,
*** 33,49 ****
#include "flags.h"
! /* Initialize loop optimizer. This is used by the tree and RTL loop
optimizers. FLAGS specify what properties to compute and/or ensure for
loops. */
! struct loops *
loop_optimizer_init (unsigned flags)
{
- struct loops *loops = XCNEW (struct loops);
edge e;
edge_iterator ei;
static bool first_time = true;
if (first_time)
{
--- 33,49 ----
#include "flags.h"
! /* Initialize loop structures. This is used by the tree and RTL loop
optimizers. FLAGS specify what properties to compute and/or ensure for
loops. */
! void
loop_optimizer_init (unsigned flags)
{
edge e;
edge_iterator ei;
static bool first_time = true;
+ struct loops *loops;
if (first_time)
{
*************** loop_optimizer_init (unsigned flags)
*** 51,56 ****
--- 51,59 ----
init_set_costs ();
}
+ gcc_assert (!current_loops);
+ loops = XCNEW (struct loops);
+
/* Avoid annoying special cases of edges going to exit
block. */
*************** loop_optimizer_init (unsigned flags)
*** 62,124 ****
/* Find the loops. */
! if (flow_loops_find (loops) <= 1)
{
/* No loops. */
! flow_loops_free (loops);
! free (loops);
!
! return NULL;
}
- /* Not going to update these. */
- free (loops->cfg.rc_order);
- loops->cfg.rc_order = NULL;
- free (loops->cfg.dfs_order);
- loops->cfg.dfs_order = NULL;
-
/* Create pre-headers. */
if (flags & LOOPS_HAVE_PREHEADERS)
! create_preheaders (loops, CP_SIMPLE_PREHEADERS);
/* Force all latches to have only single successor. */
if (flags & LOOPS_HAVE_SIMPLE_LATCHES)
! force_single_succ_latches (loops);
/* Mark irreducible loops. */
if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
! mark_irreducible_loops (loops);
if (flags & LOOPS_HAVE_MARKED_SINGLE_EXITS)
! mark_single_exit_loops (loops);
/* Dump loops. */
! flow_loops_dump (loops, dump_file, NULL, 1);
#ifdef ENABLE_CHECKING
verify_dominators (CDI_DOMINATORS);
! verify_loop_structure (loops);
#endif
-
- return loops;
}
! /* Finalize loop optimizer. */
void
! loop_optimizer_finalize (struct loops *loops)
{
unsigned i;
! if (!loops)
return;
! for (i = 1; i < loops->num; i++)
! if (loops->parray[i])
! free_simple_loop_desc (loops->parray[i]);
/* Clean up. */
! flow_loops_free (loops);
! free (loops);
/* Checking. */
#ifdef ENABLE_CHECKING
--- 65,128 ----
/* Find the loops. */
! flow_loops_find (loops);
! current_loops = loops;
!
! if (current_loops->num <= 1)
{
/* No loops. */
! loop_optimizer_finalize ();
! return;
}
/* Create pre-headers. */
if (flags & LOOPS_HAVE_PREHEADERS)
! create_preheaders (current_loops, CP_SIMPLE_PREHEADERS);
/* Force all latches to have only single successor. */
if (flags & LOOPS_HAVE_SIMPLE_LATCHES)
! force_single_succ_latches (current_loops);
/* Mark irreducible loops. */
if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
! mark_irreducible_loops (current_loops);
if (flags & LOOPS_HAVE_MARKED_SINGLE_EXITS)
! mark_single_exit_loops (current_loops);
/* Dump loops. */
! flow_loops_dump (current_loops, dump_file, NULL, 1);
#ifdef ENABLE_CHECKING
verify_dominators (CDI_DOMINATORS);
! verify_loop_structure (current_loops);
#endif
}
! /* Finalize loop structures. */
!
void
! loop_optimizer_finalize (void)
{
unsigned i;
+ basic_block bb;
! if (!current_loops)
return;
! for (i = 1; i < current_loops->num; i++)
! if (current_loops->parray[i])
! free_simple_loop_desc (current_loops->parray[i]);
/* Clean up. */
! flow_loops_free (current_loops);
! free (current_loops);
! current_loops = NULL;
!
! FOR_ALL_BB (bb)
! {
! bb->loop_father = NULL;
! }
/* Checking. */
#ifdef ENABLE_CHECKING
*************** rtl_loop_init (void)
*** 173,179 ****
/* Initialize structures for layout changes. */
cfg_layout_initialize (0);
! current_loops = loop_optimizer_init (LOOPS_NORMAL);
return 0;
}
--- 177,183 ----
/* Initialize structures for layout changes. */
cfg_layout_initialize (0);
! loop_optimizer_init (LOOPS_NORMAL);
return 0;
}
*************** struct tree_opt_pass pass_rtl_loop_init
*** 196,209 ****
/* Finalization of the RTL loop passes. */
static unsigned int
rtl_loop_done (void)
{
basic_block bb;
! if (current_loops)
! loop_optimizer_finalize (current_loops);
!
free_dominance_info (CDI_DOMINATORS);
/* Finalize layout changes. */
--- 200,212 ----
/* Finalization of the RTL loop passes. */
+
static unsigned int
rtl_loop_done (void)
{
basic_block bb;
! loop_optimizer_finalize ();
free_dominance_info (CDI_DOMINATORS);
/* Finalize layout changes. */
*************** rtl_loop_done (void)
*** 218,224 ****
if (dump_file)
dump_flow_info (dump_file, dump_flags);
- current_loops = NULL;
return 0;
}
--- 221,226 ----
Index: tree-ssa-sink.c
===================================================================
*** tree-ssa-sink.c (revision 117970)
--- tree-ssa-sink.c (working copy)
*************** sink_code_in_bb (basic_block bb)
*** 522,528 ****
static void
execute_sink_code (void)
{
! struct loops *loops = loop_optimizer_init (LOOPS_NORMAL);
connect_infinite_loops_to_exit ();
memset (&sink_stats, 0, sizeof (sink_stats));
--- 522,528 ----
static void
execute_sink_code (void)
{
! loop_optimizer_init (LOOPS_NORMAL);
connect_infinite_loops_to_exit ();
memset (&sink_stats, 0, sizeof (sink_stats));
*************** execute_sink_code (void)
*** 532,538 ****
fprintf (dump_file, "Sunk statements:%d\n", sink_stats.sunk);
free_dominance_info (CDI_POST_DOMINATORS);
remove_fake_exit_edges ();
! loop_optimizer_finalize (loops);
}
/* Gate and execute functions for PRE. */
--- 532,538 ----
fprintf (dump_file, "Sunk statements:%d\n", sink_stats.sunk);
free_dominance_info (CDI_POST_DOMINATORS);
remove_fake_exit_edges ();
! loop_optimizer_finalize ();
}
/* Gate and execute functions for PRE. */
Index: ifcvt.c
===================================================================
*** ifcvt.c (revision 117970)
--- ifcvt.c (working copy)
*************** if_convert (int x_life_data_ok)
*** 3853,3863 ****
&& (!flag_reorder_blocks_and_partition || !no_new_pseudos
|| !targetm.have_named_sections))
{
! struct loops loops;
!
! flow_loops_find (&loops);
! mark_loop_exit_edges (&loops);
! flow_loops_free (&loops);
free_dominance_info (CDI_DOMINATORS);
}
--- 3853,3864 ----
&& (!flag_reorder_blocks_and_partition || !no_new_pseudos
|| !targetm.have_named_sections))
{
! loop_optimizer_init (0);
! if (current_loops)
! {
! mark_loop_exit_edges (current_loops);
! loop_optimizer_finalize ();
! }
free_dominance_info (CDI_DOMINATORS);
}
Index: predict.c
===================================================================
*** predict.c (revision 117970)
--- predict.c (working copy)
*************** static sreal real_zero, real_one, real_a
*** 74,81 ****
static void combine_predictions_for_insn (rtx, basic_block);
static void dump_prediction (FILE *, enum br_predictor, int, basic_block, int);
- static void estimate_loops_at_level (struct loop *, bitmap);
- static void propagate_freq (struct loop *, bitmap);
static void estimate_bb_frequencies (struct loops *);
static void predict_paths_leading_to (basic_block, int *, enum br_predictor, enum prediction);
static bool last_basic_block_p (basic_block);
--- 74,79 ----
*************** predict_loops (struct loops *loops_info,
*** 777,786 ****
}
if (!rtlsimpleloops)
! {
! scev_finalize ();
! current_loops = NULL;
! }
}
/* Attempt to predict probabilities of BB outgoing edges using local
--- 775,781 ----
}
if (!rtlsimpleloops)
! scev_finalize ();
}
/* Attempt to predict probabilities of BB outgoing edges using local
*************** static unsigned int
*** 1289,1299 ****
tree_estimate_probability (void)
{
basic_block bb;
- struct loops loops_info;
! flow_loops_find (&loops_info);
if (dump_file && (dump_flags & TDF_DETAILS))
! flow_loops_dump (&loops_info, dump_file, NULL, 0);
add_noreturn_fake_exit_edges ();
connect_infinite_loops_to_exit ();
--- 1284,1293 ----
tree_estimate_probability (void)
{
basic_block bb;
! loop_optimizer_init (0);
if (dump_file && (dump_flags & TDF_DETAILS))
! flow_loops_dump (current_loops, dump_file, NULL, 0);
add_noreturn_fake_exit_edges ();
connect_infinite_loops_to_exit ();
*************** tree_estimate_probability (void)
*** 1302,1309 ****
tree_bb_level_predictions ();
! mark_irreducible_loops (&loops_info);
! predict_loops (&loops_info, false);
FOR_EACH_BB (bb)
{
--- 1296,1304 ----
tree_bb_level_predictions ();
! mark_irreducible_loops (current_loops);
! if (current_loops)
! predict_loops (current_loops, false);
FOR_EACH_BB (bb)
{
*************** tree_estimate_probability (void)
*** 1365,1374 ****
combine_predictions_for_bb (bb);
strip_builtin_expect ();
! estimate_bb_frequencies (&loops_info);
free_dominance_info (CDI_POST_DOMINATORS);
remove_fake_exit_edges ();
! flow_loops_free (&loops_info);
if (dump_file && (dump_flags & TDF_DETAILS))
dump_tree_cfg (dump_file, dump_flags);
if (profile_status == PROFILE_ABSENT)
--- 1360,1369 ----
combine_predictions_for_bb (bb);
strip_builtin_expect ();
! estimate_bb_frequencies (current_loops);
free_dominance_info (CDI_POST_DOMINATORS);
remove_fake_exit_edges ();
! loop_optimizer_finalize ();
if (dump_file && (dump_flags & TDF_DETAILS))
dump_tree_cfg (dump_file, dump_flags);
if (profile_status == PROFILE_ABSENT)
*************** typedef struct edge_info_def
*** 1547,1558 ****
#define EDGE_INFO(E) ((edge_info) (E)->aux)
/* Helper function for estimate_bb_frequencies.
! Propagate the frequencies for LOOP. */
static void
! propagate_freq (struct loop *loop, bitmap tovisit)
{
- basic_block head = loop->header;
basic_block bb;
basic_block last;
unsigned i;
--- 1542,1553 ----
#define EDGE_INFO(E) ((edge_info) (E)->aux)
/* Helper function for estimate_bb_frequencies.
! Propagate the frequencies in blocks marked in
! TOVISIT, starting in HEAD. */
static void
! propagate_freq (basic_block head, bitmap tovisit)
{
basic_block bb;
basic_block last;
unsigned i;
*************** propagate_freq (struct loop *loop, bitma
*** 1689,1695 ****
/* Estimate probabilities of loopback edges in loops at same nest level. */
static void
! estimate_loops_at_level (struct loop *first_loop, bitmap tovisit)
{
struct loop *loop;
--- 1684,1690 ----
/* Estimate probabilities of loopback edges in loops at same nest level. */
static void
! estimate_loops_at_level (struct loop *first_loop)
{
struct loop *loop;
*************** estimate_loops_at_level (struct loop *fi
*** 1698,1722 ****
edge e;
basic_block *bbs;
unsigned i;
! estimate_loops_at_level (loop->inner, tovisit);
! /* Do not do this for dummy function loop. */
! if (EDGE_COUNT (loop->latch->succs) > 0)
! {
! /* Find current loop back edge and mark it. */
! e = loop_latch_edge (loop);
! EDGE_INFO (e)->back_edge = 1;
! }
bbs = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
bitmap_set_bit (tovisit, bbs[i]->index);
free (bbs);
! propagate_freq (loop, tovisit);
}
}
/* Convert counts measured by profile driven feedback to frequencies.
Return nonzero iff there was any nonzero execution count. */
--- 1693,1736 ----
edge e;
basic_block *bbs;
unsigned i;
+ bitmap tovisit = BITMAP_ALLOC (NULL);
! estimate_loops_at_level (loop->inner);
! /* Find current loop back edge and mark it. */
! e = loop_latch_edge (loop);
! EDGE_INFO (e)->back_edge = 1;
bbs = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
bitmap_set_bit (tovisit, bbs[i]->index);
free (bbs);
! propagate_freq (loop->header, tovisit);
! BITMAP_FREE (tovisit);
}
}
+ /* Propates frequencies through structure of LOOPS. */
+
+ static void
+ estimate_loops (struct loops *loops)
+ {
+ bitmap tovisit = BITMAP_ALLOC (NULL);
+ basic_block bb;
+
+ /* Start by estimating the frequencies in the loops. */
+ if (loops)
+ estimate_loops_at_level (loops->tree_root->inner);
+
+ /* Now propagate the frequencies through all the blocks. */
+ FOR_ALL_BB (bb)
+ {
+ bitmap_set_bit (tovisit, bb->index);
+ }
+ propagate_freq (ENTRY_BLOCK_PTR, tovisit);
+ BITMAP_FREE (tovisit);
+ }
+
/* Convert counts measured by profile driven feedback to frequencies.
Return nonzero iff there was any nonzero execution count. */
*************** estimate_bb_frequencies (struct loops *l
*** 1787,1793 ****
if (!flag_branch_probabilities || !counts_to_freqs ())
{
static int real_values_initialized = 0;
- bitmap tovisit;
if (!real_values_initialized)
{
--- 1801,1806 ----
*************** estimate_bb_frequencies (struct loops *l
*** 1806,1812 ****
single_succ_edge (ENTRY_BLOCK_PTR)->probability = REG_BR_PROB_BASE;
/* Set up block info for each basic block. */
- tovisit = BITMAP_ALLOC (NULL);
alloc_aux_for_blocks (sizeof (struct block_info_def));
alloc_aux_for_edges (sizeof (struct edge_info_def));
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
--- 1819,1824 ----
*************** estimate_bb_frequencies (struct loops *l
*** 1825,1831 ****
/* First compute probabilities locally for each loop from innermost
to outermost to examine probabilities for back edges. */
! estimate_loops_at_level (loops->tree_root, tovisit);
memcpy (&freq_max, &real_zero, sizeof (real_zero));
FOR_EACH_BB (bb)
--- 1837,1843 ----
/* First compute probabilities locally for each loop from innermost
to outermost to examine probabilities for back edges. */
! estimate_loops (loops);
memcpy (&freq_max, &real_zero, sizeof (real_zero));
FOR_EACH_BB (bb)
*************** estimate_bb_frequencies (struct loops *l
*** 1844,1850 ****
free_aux_for_blocks ();
free_aux_for_edges ();
- BITMAP_FREE (tovisit);
}
compute_function_frequency ();
if (flag_reorder_functions)
--- 1856,1861 ----
Index: tree-ssa-loop.c
===================================================================
*** tree-ssa-loop.c (revision 117970)
--- tree-ssa-loop.c (working copy)
*************** Software Foundation, 51 Franklin Street,
*** 38,63 ****
#include "tree-inline.h"
#include "tree-scalar-evolution.h"
- /* The loop tree currently optimized. */
-
- struct loops *current_loops = NULL;
-
/* Initializes the loop structures. */
! static struct loops *
tree_loop_optimizer_init (void)
{
! struct loops *loops;
!
! loops = loop_optimizer_init (LOOPS_NORMAL
! | LOOPS_HAVE_MARKED_SINGLE_EXITS);
!
! if (!loops)
! return NULL;
rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
-
- return loops;
}
/* The loop superpass. */
--- 38,54 ----
#include "tree-inline.h"
#include "tree-scalar-evolution.h"
/* Initializes the loop structures. */
! static void
tree_loop_optimizer_init (void)
{
! loop_optimizer_init (LOOPS_NORMAL
! | LOOPS_HAVE_MARKED_SINGLE_EXITS);
! if (!current_loops)
! return;
rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
}
/* The loop superpass. */
*************** struct tree_opt_pass pass_tree_loop =
*** 90,96 ****
static unsigned int
tree_ssa_loop_init (void)
{
! current_loops = tree_loop_optimizer_init ();
if (!current_loops)
return 0;
--- 81,87 ----
static unsigned int
tree_ssa_loop_init (void)
{
! tree_loop_optimizer_init ();
if (!current_loops)
return 0;
*************** tree_ssa_loop_done (void)
*** 488,495 ****
free_numbers_of_iterations_estimates (current_loops);
scev_finalize ();
! loop_optimizer_finalize (current_loops);
! current_loops = NULL;
return 0;
}
--- 479,485 ----
free_numbers_of_iterations_estimates (current_loops);
scev_finalize ();
! loop_optimizer_finalize ();
return 0;
}
Index: tree-vectorizer.c
===================================================================
*** tree-vectorizer.c (revision 117970)
--- tree-vectorizer.c (working copy)
*************** slpeel_update_phi_nodes_for_guard1 (edge
*** 519,525 ****
/* Create new bb between loop and new_merge_bb. */
*new_exit_bb = split_edge (loop->single_exit);
- add_bb_to_loop (*new_exit_bb, loop->outer);
new_exit_e = EDGE_SUCC (*new_exit_bb, 0);
--- 519,524 ----
*************** slpeel_update_phi_nodes_for_guard2 (edge
*** 645,651 ****
/* Create new bb between loop and new_merge_bb. */
*new_exit_bb = split_edge (loop->single_exit);
- add_bb_to_loop (*new_exit_bb, loop->outer);
new_exit_e = EDGE_SUCC (*new_exit_bb, 0);
--- 644,649 ----
*************** slpeel_tree_peel_loop_to_edge (struct lo
*** 1156,1164 ****
*/
bb_before_first_loop = split_edge (loop_preheader_edge (first_loop));
- add_bb_to_loop (bb_before_first_loop, first_loop->outer);
bb_before_second_loop = split_edge (first_loop->single_exit);
- add_bb_to_loop (bb_before_second_loop, first_loop->outer);
pre_condition =
fold_build2 (LE_EXPR, boolean_type_node, first_niters,
--- 1154,1160 ----
*************** slpeel_tree_peel_loop_to_edge (struct lo
*** 1198,1204 ****
bb_between_loops = new_exit_bb;
bb_after_second_loop = split_edge (second_loop->single_exit);
- add_bb_to_loop (bb_after_second_loop, second_loop->outer);
pre_condition =
fold_build2 (EQ_EXPR, boolean_type_node, first_niters, niters);
--- 1194,1199 ----
Index: function.h
===================================================================
*** function.h (revision 117970)
--- function.h (working copy)
*************** struct function GTY(())
*** 189,194 ****
--- 189,197 ----
/* The control flow graph for this function. */
struct control_flow_graph *cfg;
+ /* The loops in this function. */
+ struct loops * GTY((skip)) x_current_loops;
+
/* For function.c. */
/* Points to the FUNCTION_DECL of this function. */
*************** extern int trampolines_created;
*** 520,525 ****
--- 523,529 ----
#define avail_temp_slots (cfun->x_avail_temp_slots)
#define temp_slot_level (cfun->x_temp_slot_level)
#define nonlocal_goto_handler_labels (cfun->x_nonlocal_goto_handler_labels)
+ #define current_loops (cfun->x_current_loops)
/* Given a function decl for a containing function,
return the `struct function' for it. */
Index: tree-if-conv.c
===================================================================
*** tree-if-conv.c (revision 117970)
--- tree-if-conv.c (working copy)
*************** combine_blocks (struct loop *loop)
*** 949,965 ****
/* Update stmt list. */
last = tsi_last (merge_target_bb->stmt_list);
tsi_link_after (&last, bb->stmt_list, TSI_NEW_STMT);
! bb->stmt_list = NULL;
! /* Update dominator info. */
! if (dom_computed[CDI_DOMINATORS])
! delete_from_dominance_info (CDI_DOMINATORS, bb);
! if (dom_computed[CDI_POST_DOMINATORS])
! delete_from_dominance_info (CDI_POST_DOMINATORS, bb);
!
! /* Remove basic block. */
! remove_bb_from_loops (bb);
! expunge_block (bb);
}
/* Now if possible, merge loop header and block with exit edge.
--- 949,957 ----
/* Update stmt list. */
last = tsi_last (merge_target_bb->stmt_list);
tsi_link_after (&last, bb->stmt_list, TSI_NEW_STMT);
! bb->stmt_list = alloc_stmt_list ();
! delete_basic_block (bb);
}
/* Now if possible, merge loop header and block with exit edge.
*************** combine_blocks (struct loop *loop)
*** 968,977 ****
if (exit_bb
&& exit_bb != loop->header
&& can_merge_blocks_p (loop->header, exit_bb))
! {
! remove_bb_from_loops (exit_bb);
! merge_blocks (loop->header, exit_bb);
! }
}
/* Make new temp variable of type TYPE. Add MODIFY_EXPR to assign EXP
--- 960,966 ----
if (exit_bb
&& exit_bb != loop->header
&& can_merge_blocks_p (loop->header, exit_bb))
! merge_blocks (loop->header, exit_bb);
}
/* Make new temp variable of type TYPE. Add MODIFY_EXPR to assign EXP
Index: loop-unroll.c
===================================================================
*** loop-unroll.c (revision 117970)
--- loop-unroll.c (working copy)
*************** decide_unroll_runtime_iterations (struct
*** 899,904 ****
--- 899,916 ----
loop->lpt_decision.times);
}
+ /* Splits edge E and inserts INSNS on it. */
+
+ basic_block
+ split_edge_and_insert (edge e, rtx insns)
+ {
+ basic_block bb = split_edge (e);
+ gcc_assert (insns != NULL_RTX);
+ emit_insn_after (insns, BB_END (bb));
+ bb->flags |= BB_SUPERBLOCK;
+ return bb;
+ }
+
/* Unroll LOOP for that we are able to count number of iterations in runtime
LOOP->LPT_DECISION.TIMES + 1 times. The transformation does this (with some
extra care for case n < 0):
*************** unroll_loop_runtime_iterations (struct l
*** 1009,1015 ****
end_sequence ();
/* Precondition the loop. */
! loop_split_edge_with (loop_preheader_edge (loop), init_code);
remove_edges = XCNEWVEC (edge, max_unroll + n_peel + 1);
n_remove_edges = 0;
--- 1021,1027 ----
end_sequence ();
/* Precondition the loop. */
! split_edge_and_insert (loop_preheader_edge (loop), init_code);
remove_edges = XCNEWVEC (edge, max_unroll + n_peel + 1);
n_remove_edges = 0;
*************** unroll_loop_runtime_iterations (struct l
*** 1033,1040 ****
gcc_assert (ok);
/* Record the place where switch will be built for preconditioning. */
! swtch = loop_split_edge_with (loop_preheader_edge (loop),
! NULL_RTX);
for (i = 0; i < n_peel; i++)
{
--- 1045,1051 ----
gcc_assert (ok);
/* Record the place where switch will be built for preconditioning. */
! swtch = split_edge (loop_preheader_edge (loop));
for (i = 0; i < n_peel; i++)
{
*************** unroll_loop_runtime_iterations (struct l
*** 1053,1064 ****
j = n_peel - i - (extra_zero_check ? 0 : 1);
p = REG_BR_PROB_BASE / (i + 2);
! preheader = loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
branch_code = compare_and_jump_seq (copy_rtx (niter), GEN_INT (j), EQ,
block_label (preheader), p,
NULL_RTX);
! swtch = loop_split_edge_with (single_pred_edge (swtch), branch_code);
set_immediate_dominator (CDI_DOMINATORS, preheader, swtch);
single_pred_edge (swtch)->probability = REG_BR_PROB_BASE - p;
e = make_edge (swtch, preheader,
--- 1064,1075 ----
j = n_peel - i - (extra_zero_check ? 0 : 1);
p = REG_BR_PROB_BASE / (i + 2);
! preheader = split_edge (loop_preheader_edge (loop));
branch_code = compare_and_jump_seq (copy_rtx (niter), GEN_INT (j), EQ,
block_label (preheader), p,
NULL_RTX);
! swtch = split_edge_and_insert (single_pred_edge (swtch), branch_code);
set_immediate_dominator (CDI_DOMINATORS, preheader, swtch);
single_pred_edge (swtch)->probability = REG_BR_PROB_BASE - p;
e = make_edge (swtch, preheader,
*************** unroll_loop_runtime_iterations (struct l
*** 1071,1082 ****
/* Add branch for zero iterations. */
p = REG_BR_PROB_BASE / (max_unroll + 1);
swtch = ezc_swtch;
! preheader = loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
branch_code = compare_and_jump_seq (copy_rtx (niter), const0_rtx, EQ,
block_label (preheader), p,
NULL_RTX);
! swtch = loop_split_edge_with (single_succ_edge (swtch), branch_code);
set_immediate_dominator (CDI_DOMINATORS, preheader, swtch);
single_succ_edge (swtch)->probability = REG_BR_PROB_BASE - p;
e = make_edge (swtch, preheader,
--- 1082,1093 ----
/* Add branch for zero iterations. */
p = REG_BR_PROB_BASE / (max_unroll + 1);
swtch = ezc_swtch;
! preheader = split_edge (loop_preheader_edge (loop));
branch_code = compare_and_jump_seq (copy_rtx (niter), const0_rtx, EQ,
block_label (preheader), p,
NULL_RTX);
! swtch = split_edge_and_insert (single_succ_edge (swtch), branch_code);
set_immediate_dominator (CDI_DOMINATORS, preheader, swtch);
single_succ_edge (swtch)->probability = REG_BR_PROB_BASE - p;
e = make_edge (swtch, preheader,
*************** analyze_insns_in_loop (struct loop *loop
*** 1717,1734 ****
si_info_hash, si_info_eq, free);
/* Record the loop exit bb and loop preheader before the unrolling. */
! if (!loop_preheader_edge (loop)->src)
! {
! loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
! opt_info->loop_preheader = loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
! }
! else
! opt_info->loop_preheader = loop_preheader_edge (loop)->src;
if (num_edges == 1
&& !(edges[0]->flags & EDGE_COMPLEX))
{
! opt_info->loop_exit = loop_split_edge_with (edges[0], NULL_RTX);
can_apply = true;
}
--- 1728,1739 ----
si_info_hash, si_info_eq, free);
/* Record the loop exit bb and loop preheader before the unrolling. */
! opt_info->loop_preheader = loop_preheader_edge (loop)->src;
if (num_edges == 1
&& !(edges[0]->flags & EDGE_COMPLEX))
{
! opt_info->loop_exit = split_edge (edges[0]);
can_apply = true;
}
Index: loop-doloop.c
===================================================================
*** loop-doloop.c (revision 117970)
--- loop-doloop.c (working copy)
*************** add_test (rtx cond, edge *e, basic_block
*** 257,263 ****
seq = get_insns ();
end_sequence ();
! bb = loop_split_edge_with (*e, seq);
*e = single_succ_edge (bb);
if (any_uncondjump_p (jump))
--- 257,263 ----
seq = get_insns ();
end_sequence ();
! bb = split_edge_and_insert (*e, seq);
*e = single_succ_edge (bb);
if (any_uncondjump_p (jump))
*************** doloop_modify (struct loop *loop, struct
*** 372,380 ****
rtx ass = copy_rtx (desc->noloop_assumptions);
basic_block preheader = loop_preheader_edge (loop)->src;
basic_block set_zero
! = loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
basic_block new_preheader
! = loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
edge te;
/* Expand the condition testing the assumptions and if it does not pass,
--- 372,380 ----
rtx ass = copy_rtx (desc->noloop_assumptions);
basic_block preheader = loop_preheader_edge (loop)->src;
basic_block set_zero
! = split_edge (loop_preheader_edge (loop));
basic_block new_preheader
! = split_edge (loop_preheader_edge (loop));
edge te;
/* Expand the condition testing the assumptions and if it does not pass,
*************** doloop_modify (struct loop *loop, struct
*** 406,412 ****
{
/* All the conditions were simplified to false, remove the
unreachable set_zero block. */
- remove_bb_from_loops (set_zero);
delete_basic_block (set_zero);
}
else
--- 406,411 ----
Index: tree-ssa-pre.c
===================================================================
*** tree-ssa-pre.c (revision 117970)
--- tree-ssa-pre.c (working copy)
*************** init_pre (bool do_fre)
*** 3763,3769 ****
vn_init ();
if (!do_fre)
! current_loops = loop_optimizer_init (LOOPS_NORMAL);
connect_infinite_loops_to_exit ();
memset (&pre_stats, 0, sizeof (pre_stats));
--- 3763,3769 ----
vn_init ();
if (!do_fre)
! loop_optimizer_init (LOOPS_NORMAL);
connect_infinite_loops_to_exit ();
memset (&pre_stats, 0, sizeof (pre_stats));
*************** fini_pre (bool do_fre)
*** 3877,3886 ****
SSA_NAME_VALUE (name) = NULL;
}
if (!do_fre && current_loops)
! {
! loop_optimizer_finalize (current_loops);
! current_loops = NULL;
! }
}
/* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
--- 3877,3883 ----
SSA_NAME_VALUE (name) = NULL;
}
if (!do_fre && current_loops)
! loop_optimizer_finalize ();
}
/* Main entry point to the SSA-PRE pass. DO_FRE is true if the caller
Index: cfglayout.c
===================================================================
*** cfglayout.c (revision 117970)
--- cfglayout.c (working copy)
*************** copy_bbs (basic_block *bbs, unsigned n,
*** 1230,1238 ****
new_bb = new_bbs[i] = duplicate_block (bb, NULL, after);
after = new_bb;
bb->flags |= BB_DUPLICATED;
! /* Add to loop. */
! add_bb_to_loop (new_bb, bb->loop_father->copy);
! /* Possibly set header. */
if (bb->loop_father->header == bb && bb->loop_father != base)
new_bb->loop_father->header = new_bb;
/* Or latch. */
--- 1230,1236 ----
new_bb = new_bbs[i] = duplicate_block (bb, NULL, after);
after = new_bb;
bb->flags |= BB_DUPLICATED;
! /* Possibly set loop header. */
if (bb->loop_father->header == bb && bb->loop_father != base)
new_bb->loop_father->header = new_bb;
/* Or latch. */
Index: lambda-code.c
===================================================================
*** lambda-code.c (revision 117970)
--- lambda-code.c (working copy)
*************** perfect_nestify (struct loops *loops,
*** 2391,2397 ****
/* Create the new loop. */
olddest = loop->single_exit->dest;
! preheaderbb = loop_split_edge_with (loop->single_exit, NULL);
headerbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
/* Push the exit phi nodes that we are moving. */
--- 2391,2397 ----
/* Create the new loop. */
olddest = loop->single_exit->dest;
! preheaderbb = split_edge (loop->single_exit);
headerbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
/* Push the exit phi nodes that we are moving. */
Index: tree-vect-transform.c
===================================================================
*** tree-vect-transform.c (revision 117970)
--- tree-vect-transform.c (working copy)
*************** vect_transform_loop (loop_vec_info loop_
*** 3017,3023 ****
merge_bb = loop->single_exit->dest;
gcc_assert (EDGE_COUNT (merge_bb->preds) == 2);
new_exit_bb = split_edge (loop->single_exit);
- add_bb_to_loop (new_exit_bb, loop->outer);
new_exit_e = loop->single_exit;
e = EDGE_SUCC (new_exit_bb, 0);
--- 3017,3022 ----
*************** vect_transform_loop (loop_vec_info loop_
*** 3069,3076 ****
gcc_assert (EDGE_COUNT (loop->header->preds) == 2);
! loop_split_edge_with (loop_preheader_edge (loop), NULL);
!
/* FORNOW: the vectorizer supports only loops which body consist
of one basic block (header + empty latch). When the vectorizer will
--- 3068,3074 ----
gcc_assert (EDGE_COUNT (loop->header->preds) == 2);
! split_edge (loop_preheader_edge (loop));
/* FORNOW: the vectorizer supports only loops which body consist
of one basic block (header + empty latch). When the vectorizer will
Index: cfgloop.c
===================================================================
*** cfgloop.c (revision 117970)
--- cfgloop.c (working copy)
*************** static bool glb_enum_p (basic_block, voi
*** 52,58 ****
static void
flow_loops_cfg_dump (const struct loops *loops, FILE *file)
{
- int i;
basic_block bb;
if (! loops->num || ! file)
--- 52,57 ----
*************** flow_loops_cfg_dump (const struct loops
*** 68,93 ****
fprintf (file, "%d ", succ->dest->index);
fprintf (file, "}\n");
}
-
- /* Dump the DFS node order. */
- if (loops->cfg.dfs_order)
- {
- fputs (";; DFS order: ", file);
- for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
- fprintf (file, "%d ", loops->cfg.dfs_order[i]);
-
- fputs ("\n", file);
- }
-
- /* Dump the reverse completion node order. */
- if (loops->cfg.rc_order)
- {
- fputs (";; RC order: ", file);
- for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
- fprintf (file, "%d ", loops->cfg.rc_order[i]);
-
- fputs ("\n", file);
- }
}
/* Return nonzero if the nodes of LOOP are a subset of OUTER. */
--- 67,72 ----
*************** flow_loops_free (struct loops *loops)
*** 208,219 ****
free (loops->parray);
loops->parray = NULL;
-
- if (loops->cfg.dfs_order)
- free (loops->cfg.dfs_order);
- if (loops->cfg.rc_order)
- free (loops->cfg.rc_order);
-
}
}
--- 187,192 ----
*************** flow_loops_find (struct loops *loops)
*** 697,706 ****
rc_order = XNEWVEC (int, n_basic_blocks);
pre_and_rev_post_order_compute (dfs_order, rc_order, false);
- /* Save CFG derived information to avoid recomputing it. */
- loops->cfg.dfs_order = dfs_order;
- loops->cfg.rc_order = rc_order;
-
num_loops = 1;
for (b = 0; b < n_basic_blocks - NUM_FIXED_BLOCKS; b++)
--- 670,675 ----
*************** flow_loops_find (struct loops *loops)
*** 744,759 ****
loops->num = num_loops;
initialize_loops_parallel_p (loops);
}
sbitmap_free (headers);
loops->state = 0;
- #ifdef ENABLE_CHECKING
- verify_flow_info ();
- verify_loop_structure (loops);
- #endif
-
return loops->num;
}
--- 713,726 ----
loops->num = num_loops;
initialize_loops_parallel_p (loops);
+
+ free (dfs_order);
+ free (rc_order);
}
sbitmap_free (headers);
loops->state = 0;
return loops->num;
}
*************** add_bb_to_loop (basic_block bb, struct l
*** 969,980 ****
{
int i;
bb->loop_father = loop;
bb->loop_depth = loop->depth;
loop->num_nodes++;
for (i = 0; i < loop->depth; i++)
loop->pred[i]->num_nodes++;
! }
/* Remove basic block BB from loops. */
void
--- 936,948 ----
{
int i;
+ 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++;
! }
/* Remove basic block BB from loops. */
void
*************** remove_bb_from_loops (basic_block bb)
*** 983,988 ****
--- 951,957 ----
int i;
struct loop *loop = bb->loop_father;
+ gcc_assert (loop != NULL);
loop->num_nodes--;
for (i = 0; i < loop->depth; i++)
loop->pred[i]->num_nodes--;
Index: cfgloop.h
===================================================================
*** cfgloop.h (revision 117970)
--- cfgloop.h (working copy)
*************** struct loops
*** 159,183 ****
/* Pointer to root of loop hierarchy tree. */
struct loop *tree_root;
- /* Information derived from the CFG. */
- struct cfg
- {
- /* The ordering of the basic blocks in a depth first search. */
- int *dfs_order;
-
- /* The reverse completion ordering of the basic blocks found in a
- depth first search. */
- int *rc_order;
- } cfg;
-
/* Headers shared by multiple loops that should be merged. */
sbitmap shared_headers;
};
- /* The loop tree currently optimized. */
-
- extern struct loops *current_loops;
-
/* Loop recognition. */
extern int flow_loops_find (struct loops *);
extern void flow_loops_free (struct loops *);
--- 159,168 ----
*************** extern void remove_bb_from_loops (basic_
*** 220,226 ****
extern void cancel_loop_tree (struct loops *, struct loop *);
- extern basic_block loop_split_edge_with (edge, rtx);
extern int fix_loop_placement (struct loop *);
enum
--- 205,210 ----
*************** extern unsigned global_cost_for_size (un
*** 382,389 ****
extern void init_set_costs (void);
/* Loop optimizer initialization. */
! extern struct loops *loop_optimizer_init (unsigned);
! extern void loop_optimizer_finalize (struct loops *);
/* Optimization passes. */
extern void unswitch_loops (struct loops *);
--- 366,373 ----
extern void init_set_costs (void);
/* Loop optimizer initialization. */
! extern void loop_optimizer_init (unsigned);
! extern void loop_optimizer_finalize (void);
/* Optimization passes. */
extern void unswitch_loops (struct loops *);
*************** extern void unswitch_loops (struct loops
*** 391,398 ****
enum
{
UAP_PEEL = 1, /* Enables loop peeling. */
! UAP_UNROLL = 2, /* Enables peeling of loops if it seems profitable. */
! UAP_UNROLL_ALL = 4 /* Enables peeling of all loops. */
};
extern void unroll_and_peel_loops (struct loops *, int);
--- 375,382 ----
enum
{
UAP_PEEL = 1, /* Enables loop peeling. */
! UAP_UNROLL = 2, /* Enables unrolling of loops if it seems profitable. */
! UAP_UNROLL_ALL = 4 /* Enables unrolling of all loops. */
};
extern void unroll_and_peel_loops (struct loops *, int);
Index: tree-flow.h
===================================================================
*** tree-flow.h (revision 117970)
--- tree-flow.h (working copy)
*************** void free_numbers_of_iterations_estimate
*** 831,843 ****
void free_numbers_of_iterations_estimates_loop (struct loop *);
void rewrite_into_loop_closed_ssa (bitmap, unsigned);
void verify_loop_closed_ssa (void);
- void loop_commit_inserts (void);
bool for_each_index (tree *, bool (*) (tree, tree *, void *), void *);
void create_iv (tree, tree, tree, struct loop *, block_stmt_iterator *, bool,
tree *, tree *);
void split_loop_exit_edge (edge);
unsigned force_expr_to_var_cost (tree);
- basic_block bsi_insert_on_edge_immediate_loop (edge, tree);
void standard_iv_increment_position (struct loop *, block_stmt_iterator *,
bool *);
basic_block ip_end_pos (struct loop *);
--- 831,841 ----
Index: Makefile.in
===================================================================
*** Makefile.in (revision 117970)
--- Makefile.in (working copy)
*************** cfg.o : cfg.c $(CONFIG_H) $(SYSTEM_H) co
*** 2423,2429 ****
$(REGS_H) hard-reg-set.h output.h toplev.h $(FUNCTION_H) except.h $(GGC_H) \
$(TM_P_H) $(TIMEVAR_H) $(OBSTACK_H) $(TREE_H) alloc-pool.h $(HASHTAB_H)
cfghooks.o: cfghooks.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
! $(TREE_H) $(BASIC_BLOCK_H) $(TREE_FLOW_H) $(TIMEVAR_H) toplev.h
cfgexpand.o : cfgexpand.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
$(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(FUNCTION_H) $(TIMEVAR_H) $(TM_H) \
coretypes.h $(TREE_DUMP_H) except.h langhooks.h tree-pass.h $(RTL_H) \
--- 2423,2429 ----
$(REGS_H) hard-reg-set.h output.h toplev.h $(FUNCTION_H) except.h $(GGC_H) \
$(TM_P_H) $(TIMEVAR_H) $(OBSTACK_H) $(TREE_H) alloc-pool.h $(HASHTAB_H)
cfghooks.o: cfghooks.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
! $(TREE_H) $(BASIC_BLOCK_H) $(TREE_FLOW_H) $(TIMEVAR_H) toplev.h $(CFGLOOP_H)
cfgexpand.o : cfgexpand.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \
$(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(FUNCTION_H) $(TIMEVAR_H) $(TM_H) \
coretypes.h $(TREE_DUMP_H) except.h langhooks.h tree-pass.h $(RTL_H) \
Index: basic-block.h
===================================================================
*** basic-block.h (revision 117970)
--- basic-block.h (working copy)
*************** extern void update_bb_for_insn (basic_bl
*** 486,491 ****
--- 486,492 ----
extern void free_basic_block_vars (void);
extern void insert_insn_on_edge (rtx, edge);
+ basic_block split_edge_and_insert (edge, rtx);
extern void commit_edge_insertions (void);
extern void commit_edge_insertions_watch_calls (void);
Index: tree-cfg.c
===================================================================
*** tree-cfg.c (revision 117970)
--- tree-cfg.c (working copy)
*************** remove_bb (basic_block bb)
*** 1997,2020 ****
}
}
- /* If we remove the header or the latch of a loop, mark the loop for
- removal by setting its header and latch to NULL. */
if (current_loops)
{
struct loop *loop = bb->loop_father;
if (loop->latch == bb
|| loop->header == bb)
! {
! loop->latch = NULL;
! loop->header = NULL;
!
! /* Also clean up the information associated with the loop. Updating
! it would waste time. More importantly, it may refer to ssa
! names that were defined in other removed basic block -- these
! ssa names are now removed and invalid. */
! free_numbers_of_iterations_estimates_loop (loop);
! }
}
/* Remove all the instructions in the block. */
--- 1997,2011 ----
}
}
if (current_loops)
{
struct loop *loop = bb->loop_father;
+ /* If a loop gets removed, clean up the information associated
+ with it. */
if (loop->latch == bb
|| loop->header == bb)
! free_numbers_of_iterations_estimates_loop (loop);
}
/* Remove all the instructions in the block. */