#include "cfglayout.h"
#include "output.h"
-static struct loop * duplicate_loop PARAMS ((struct loops *,
- struct loop *, struct loop *));
-static void duplicate_subloops PARAMS ((struct loops *, struct loop *,
- struct loop *));
-static void copy_loops_to PARAMS ((struct loops *, struct loop **,
- int, struct loop *));
-static void loop_redirect_edge PARAMS ((edge, basic_block));
-static bool loop_delete_branch_edge PARAMS ((edge));
-static void copy_bbs PARAMS ((basic_block *, int, edge,
- edge, basic_block **,
- struct loops *, edge *,
- edge *, int));
-static void remove_bbs PARAMS ((dominance_info, basic_block *,
- int));
-static bool rpe_enum_p PARAMS ((basic_block, void *));
-static int find_path PARAMS ((edge, dominance_info,
- basic_block **));
-static bool alp_enum_p PARAMS ((basic_block, void *));
-static void add_loop PARAMS ((struct loops *, struct loop *));
-static void fix_loop_placements PARAMS ((struct loop *));
-static bool fix_bb_placement PARAMS ((struct loops *, basic_block));
-static void fix_bb_placements PARAMS ((struct loops *, basic_block));
-static void place_new_loop PARAMS ((struct loops *, struct loop *));
-static void scale_loop_frequencies PARAMS ((struct loop *, int, int));
-static void scale_bbs_frequencies PARAMS ((basic_block *, int, int, int));
-static void record_exit_edges PARAMS ((edge, basic_block *, int,
- edge *, unsigned *, int));
-static basic_block create_preheader PARAMS ((struct loop *, dominance_info,
- int));
+static struct loop * duplicate_loop (struct loops *, struct loop *,
+ struct loop *);
+static void duplicate_subloops (struct loops *, struct loop *, struct loop *);
+static void copy_loops_to (struct loops *, struct loop **, int,
+ struct loop *);
+static void loop_redirect_edge (edge, basic_block);
+static bool loop_delete_branch_edge (edge, int);
+static void remove_bbs (dominance_info, basic_block *, int);
+static bool rpe_enum_p (basic_block, void *);
+static int find_path (edge, dominance_info, basic_block **);
+static bool alp_enum_p (basic_block, void *);
+static void add_loop (struct loops *, struct loop *);
+static void fix_loop_placements (struct loop *);
+static bool fix_bb_placement (struct loops *, basic_block);
+static void fix_bb_placements (struct loops *, basic_block);
+static void place_new_loop (struct loops *, struct loop *);
+static void scale_loop_frequencies (struct loop *, int, int);
+static void scale_bbs_frequencies (basic_block *, int, int, int);
+static basic_block create_preheader (struct loop *, dominance_info, int);
+static void fix_irreducible_loops (basic_block);
/* Splits basic block BB after INSN, returns created edge. Updates loops
and dominators. */
edge
-split_loop_bb (loops, bb, insn)
- struct loops *loops;
- basic_block bb;
- rtx insn;
+split_loop_bb (struct loops *loops, basic_block bb, rtx insn)
{
edge e;
basic_block *dom_bbs;
free (dom_bbs);
set_immediate_dominator (loops->cfg.dom, e->dest, e->src);
- /* Take care of RBI. */
- alloc_aux_for_block (e->dest, sizeof (struct reorder_block_def));
-
return e;
}
};
static bool
-rpe_enum_p (bb, data)
- basic_block bb;
- void *data;
+rpe_enum_p (basic_block bb, void *data)
{
struct rpe_data *rpe = data;
return dominated_by_p (rpe->doms, bb, rpe->dom);
/* Remove basic blocks BBS from loop structure and dominance info,
and delete them afterwards. */
static void
-remove_bbs (dom, bbs, nbbs)
- dominance_info dom;
- basic_block *bbs;
- int nbbs;
+remove_bbs (dominance_info dom, basic_block *bbs, int nbbs)
{
int i;
{
remove_bb_from_loops (bbs[i]);
delete_from_dominance_info (dom, bbs[i]);
- flow_delete_block (bbs[i]);
+ delete_block (bbs[i]);
}
}
/* Find path -- i.e. the basic blocks dominated by edge E and put them
into array BBS, that will be allocated large enough to contain them.
- The number of basic blocks in the path is returned. */
+ E->dest must have exactly one predecessor for this to work (it is
+ easy to achieve and we do not put it here because we do not want to
+ alter anything by this function). The number of basic blocks in the
+ path is returned. */
static int
-find_path (e, doms, bbs)
- edge e;
- dominance_info doms;
- basic_block **bbs;
+find_path (edge e, dominance_info doms, basic_block **bbs)
{
- edge ae = NULL;
struct rpe_data rpe;
if (e->dest->pred->pred_next)
- {
- for (ae = e->dest->pred; ae; ae = ae->pred_next)
- if (ae != e && !dominated_by_p (doms, ae->src, e->dest))
- break;
- }
- if (ae)
- {
- /* The path is formed just by the edge. */
- *bbs = NULL;
- return 0;
- }
+ abort ();
/* Find bbs in the path. */
rpe.dom = e->dest;
false if the placement of BB was already correct (provided that placements
of its successors are correct). */
static bool
-fix_bb_placement (loops, bb)
- struct loops *loops;
- basic_block bb;
+fix_bb_placement (struct loops *loops, basic_block bb)
{
edge e;
struct loop *loop = loops->tree_root, *act;
his placement no longer has to be correct, and iteratively fix placement of
its predecessors that may change if placement of FROM changed. Also fix
placement of subloops of FROM->loop_father, that might also be altered due
- to this change; the condition for them is simmilar, except that instead of
+ to this change; the condition for them is similar, except that instead of
successors we consider edges coming out of the loops. */
static void
-fix_bb_placements (loops, from)
- struct loops *loops;
- basic_block from;
+fix_bb_placements (struct loops *loops, basic_block from)
{
sbitmap in_queue;
basic_block *queue, *qtop, *qbeg, *qend;
/* Prevent us from going out of the base_loop. */
SET_BIT (in_queue, base_loop->header->index);
- queue = xcalloc (base_loop->num_nodes + 1, sizeof (basic_block));
+ queue = xmalloc ((base_loop->num_nodes + 1) * sizeof (basic_block));
qtop = queue + base_loop->num_nodes + 1;
qbeg = queue;
qend = queue + 1;
if (TEST_BIT (in_queue, pred->index))
continue;
- /* If it is subloop, then it either was not moved, or
+ /* If it is subloop, then it either was not moved, or
the path up the loop tree from base_loop do not contain
it. */
nca = find_common_loop (pred->loop_father, base_loop);
free (queue);
}
+/* Basic block from has lost one or more of its predecessors, so it might
+ mo longer be part irreducible loop. Fix it and proceed recursively
+ for its successors if needed. */
+static void
+fix_irreducible_loops (basic_block from)
+{
+ basic_block bb;
+ basic_block *stack;
+ int stack_top;
+ sbitmap on_stack;
+ edge *edges, e;
+ unsigned n_edges, i;
+
+ if (!(from->flags & BB_IRREDUCIBLE_LOOP))
+ return;
+
+ on_stack = sbitmap_alloc (last_basic_block);
+ sbitmap_zero (on_stack);
+ SET_BIT (on_stack, from->index);
+ stack = xmalloc (from->loop_father->num_nodes * sizeof (basic_block));
+ stack[0] = from;
+ stack_top = 1;
+
+ while (stack_top)
+ {
+ bb = stack[--stack_top];
+ RESET_BIT (on_stack, bb->index);
+
+ for (e = bb->pred; e; e = e->pred_next)
+ if (e->flags & EDGE_IRREDUCIBLE_LOOP)
+ break;
+ if (e)
+ continue;
+
+ bb->flags &= ~BB_IRREDUCIBLE_LOOP;
+ if (bb->loop_father->header == bb)
+ edges = get_loop_exit_edges (bb->loop_father, &n_edges);
+ else
+ {
+ n_edges = 0;
+ for (e = bb->succ; e; e = e->succ_next)
+ n_edges++;
+ edges = xmalloc (n_edges * sizeof (edge));
+ n_edges = 0;
+ for (e = bb->succ; e; e = e->succ_next)
+ edges[n_edges++] = e;
+ }
+
+ for (i = 0; i < n_edges; i++)
+ {
+ e = edges[i];
+
+ if (e->flags & EDGE_IRREDUCIBLE_LOOP)
+ {
+ if (!flow_bb_inside_loop_p (from->loop_father, e->dest))
+ continue;
+
+ e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
+ if (TEST_BIT (on_stack, e->dest->index))
+ continue;
+
+ SET_BIT (on_stack, e->dest->index);
+ stack[stack_top++] = e->dest;
+ }
+ }
+ free (edges);
+ }
+
+ free (on_stack);
+ free (stack);
+}
+
/* Removes path beginning at edge E, i.e. remove basic blocks dominated by E
and update loop structure stored in LOOPS and dominators. Return true if
we were able to remove the path, false otherwise (and nothing is affected
then). */
bool
-remove_path (loops, e)
- struct loops *loops;
- edge e;
+remove_path (struct loops *loops, edge e)
{
edge ae;
basic_block *rem_bbs, *bord_bbs, *dom_bbs, from, bb;
int i, nrem, n_bord_bbs, n_dom_bbs;
sbitmap seen;
- /* First identify the path. */
+ if (!loop_delete_branch_edge (e, 0))
+ return false;
+
+ /* We need to check whether basic blocks are dominated by the edge
+ e, but we only have basic block dominators. This is easy to
+ fix -- when e->dest has exactly one predecessor, this corresponds
+ to blocks dominated by e->dest, if not, split the edge. */
+ if (e->dest->pred->pred_next)
+ e = loop_split_edge_with (e, NULL_RTX, loops)->pred;
+
+ /* 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
+ 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 (loops->cfg.dom,
+ e->src->loop_father->latch, e->dest))
+ unloop (loops, e->src->loop_father);
+
+ /* Identify the path. */
nrem = find_path (e, loops->cfg.dom, &rem_bbs);
n_bord_bbs = 0;
/* Find "border" hexes -- i.e. those with predecessor in removed path. */
for (i = 0; i < nrem; i++)
SET_BIT (seen, rem_bbs[i]->index);
- if (nrem)
+ for (i = 0; i < nrem; i++)
{
- for (i = 0; i < nrem; i++)
- {
- bb = rem_bbs[i];
- for (ae = rem_bbs[i]->succ; ae; ae = ae->succ_next)
- if (ae->dest != EXIT_BLOCK_PTR && !TEST_BIT (seen, ae->dest->index))
- {
- SET_BIT (seen, ae->dest->index);
- bord_bbs[n_bord_bbs++] = ae->dest;
- }
- }
+ bb = rem_bbs[i];
+ for (ae = rem_bbs[i]->succ; ae; ae = ae->succ_next)
+ if (ae->dest != EXIT_BLOCK_PTR && !TEST_BIT (seen, ae->dest->index))
+ {
+ SET_BIT (seen, ae->dest->index);
+ bord_bbs[n_bord_bbs++] = ae->dest;
+ }
}
- else if (e->dest != EXIT_BLOCK_PTR)
- bord_bbs[n_bord_bbs++] = e->dest;
/* Remove the path. */
from = e->src;
- if (!loop_delete_branch_edge (e))
- {
- free (rem_bbs);
- free (bord_bbs);
- free (seen);
- return false;
- }
+ if (!loop_delete_branch_edge (e, 1))
+ abort ();
dom_bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
/* Cancel loops contained in the path. */
remove_bbs (loops->cfg.dom, rem_bbs, nrem);
free (rem_bbs);
- /* Find blocks with whose dominators may be affected. */
+ /* Find blocks whose dominators may be affected. */
n_dom_bbs = 0;
sbitmap_zero (seen);
for (i = 0; i < n_bord_bbs; i++)
free(ldom);
}
- free (bord_bbs);
free (seen);
/* Recount dominators. */
iterate_fix_dominators (loops->cfg.dom, dom_bbs, n_dom_bbs);
free (dom_bbs);
+ /* These blocks have lost some predecessor(s), thus their irreducible
+ status could be changed. */
+ for (i = 0; i < n_bord_bbs; i++)
+ fix_irreducible_loops (bord_bbs[i]);
+ free (bord_bbs);
+
/* Fix placements of basic blocks inside loops and the placement of
loops in the loop tree. */
fix_bb_placements (loops, from);
/* Predicate for enumeration in add_loop. */
static bool
-alp_enum_p (bb, alp_header)
- basic_block bb;
- void *alp_header;
+alp_enum_p (basic_block bb, void *alp_header)
{
return bb != (basic_block) alp_header;
}
/* 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 (loops, loop)
- struct loops *loops;
- struct loop *loop;
+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;
free (bbs);
}
-/* Multiply all frequencies of basic blocks in array BBS of lenght NBBS
+/* Multiply all frequencies of basic blocks in array BBS of length NBBS
by NUM/DEN. */
static void
-scale_bbs_frequencies (bbs, nbbs, num, den)
- basic_block *bbs;
- int nbbs;
- int num;
- int den;
+scale_bbs_frequencies (basic_block *bbs, int nbbs, int num, int den)
{
int i;
edge e;
/* Multiply all frequencies in LOOP by NUM/DEN. */
static void
-scale_loop_frequencies (loop, num, den)
- struct loop *loop;
- int num;
- int den;
+scale_loop_frequencies (struct loop *loop, int num, int den)
{
basic_block *bbs;
SWITCH_BB->succ->succ_next to original destination of HEADER_EDGE.
Returns newly created loop. */
struct loop *
-loopify (loops, latch_edge, header_edge, switch_bb)
- struct loops *loops;
- edge latch_edge;
- edge header_edge;
- basic_block switch_bb;
+loopify (struct loops *loops, edge latch_edge, edge header_edge, basic_block switch_bb)
{
basic_block succ_bb = latch_edge->dest;
basic_block pred_bb = header_edge->src;
return loop;
}
+/* Remove the latch edge of a LOOP and update LOOPS tree to indicate that
+ the LOOP was removed. After this function, original loop latch will
+ have no successor, which caller is expected to fix somehow. */
+void
+unloop (struct loops *loops, struct loop *loop)
+{
+ basic_block *body;
+ struct loop *ploop;
+ unsigned i, n;
+ basic_block latch = loop->latch;
+ edge *edges;
+ unsigned n_edges;
+
+ /* This is relatively straightforward. The dominators are unchanged, as
+ loop header dominates loop latch, so the only thing we have to care of
+ is the placement of loops and basic blocks inside the loop tree. We
+ move them all to the loop->outer, and then let fix_bb_placements do
+ its work. */
+
+ body = get_loop_body (loop);
+ edges = get_loop_exit_edges (loop, &n_edges);
+ n = loop->num_nodes;
+ for (i = 0; i < n; i++)
+ if (body[i]->loop_father == loop)
+ {
+ remove_bb_from_loops (body[i]);
+ add_bb_to_loop (body[i], loop->outer);
+ }
+ free(body);
+
+ while (loop->inner)
+ {
+ ploop = loop->inner;
+ flow_loop_tree_node_remove (ploop);
+ flow_loop_tree_node_add (loop->outer, ploop);
+ }
+
+ /* Remove the loop and free its data. */
+ flow_loop_tree_node_remove (loop);
+ loops->parray[loop->num] = NULL;
+ flow_loop_free (loop);
+
+ remove_edge (latch->succ);
+ fix_bb_placements (loops, latch);
+
+ /* If the loop was inside an irreducible region, we would have to somehow
+ update the irreducible marks inside its body. While it is certainly
+ possible to do, it is a bit complicated and this situation should be
+ very rare, so we just remark all loops in this case. */
+ for (i = 0; i < n_edges; i++)
+ if (edges[i]->flags & EDGE_IRREDUCIBLE_LOOP)
+ break;
+ if (i != n_edges)
+ mark_irreducible_loops (loops);
+ free (edges);
+}
+
/* Fix placement of LOOP inside loop tree, i.e. find the innermost superloop
- FATHER of LOOP such that all of the edges comming out of LOOP belong to
+ FATHER of LOOP such that all of the edges coming out of LOOP belong to
FATHER, and set it as outer loop of LOOP. Return 1 if placement of
LOOP changed. */
int
-fix_loop_placement (loop)
- struct loop *loop;
+fix_loop_placement (struct loop *loop)
{
basic_block *body;
unsigned i;
It is used in case when we removed some edges coming out of LOOP, which
may cause the right placement of LOOP inside loop tree to change. */
static void
-fix_loop_placements (loop)
- struct loop *loop;
+fix_loop_placements (struct loop *loop)
{
struct loop *outer;
/* Creates place for a new LOOP in LOOPS structure. */
static void
-place_new_loop (loops, loop)
- struct loops *loops;
- struct loop *loop;
+place_new_loop (struct loops *loops, struct loop *loop)
{
loops->parray =
xrealloc (loops->parray, (loops->num + 1) * sizeof (struct loop *));
/* Copies copy of LOOP as subloop of TARGET loop, placing newly
created loop into LOOPS structure. */
static struct loop *
-duplicate_loop (loops, loop, target)
- struct loops *loops;
- struct loop *loop;
- struct loop *target;
+duplicate_loop (struct loops *loops, struct loop *loop, struct loop *target)
{
struct loop *cloop;
cloop = xcalloc (1, sizeof (struct loop));
/* Copies structure of subloops of LOOP into TARGET loop, placing
newly created loops into loop tree stored in LOOPS. */
-static void
-duplicate_subloops (loops, loop, target)
- struct loops *loops;
- struct loop *loop;
- struct loop *target;
+static void
+duplicate_subloops (struct loops *loops, struct loop *loop, struct loop *target)
{
struct loop *aloop, *cloop;
/* Copies structure of subloops of N loops, stored in array COPIED_LOOPS,
into TARGET loop, placing newly created loops into loop tree LOOPS. */
-static void
-copy_loops_to (loops, copied_loops, n, target)
- struct loops *loops;
- struct loop **copied_loops;
- int n;
- struct loop *target;
+static void
+copy_loops_to (struct loops *loops, struct loop **copied_loops, int n, struct loop *target)
{
struct loop *aloop;
int i;
/* Redirects edge E to basic block DEST. */
static void
-loop_redirect_edge (e, dest)
- edge e;
- basic_block dest;
+loop_redirect_edge (edge e, basic_block dest)
{
if (e->dest == dest)
return;
- cfg_layout_redirect_edge (e, dest);
+ redirect_edge_and_branch_force (e, dest);
}
-/* Deletes edge E from a branch if possible. */
+/* Deletes edge E from a branch if possible. Unless REALLY_DELETE is set,
+ just test whether it is possible to remove the edge. */
static bool
-loop_delete_branch_edge (e)
- edge e;
+loop_delete_branch_edge (edge e, int really_delete)
{
basic_block src = e->src;
+ int irr;
+ edge snd;
if (src->succ->succ_next)
{
basic_block newdest;
+
/* Cannot handle more than two exit edges. */
if (src->succ->succ_next->succ_next)
return false;
if (!any_condjump_p (src->end))
return false;
- newdest = (e == src->succ
- ? src->succ->succ_next->dest : src->succ->dest);
+ snd = e == src->succ ? src->succ->succ_next : src->succ;
+ newdest = snd->dest;
if (newdest == EXIT_BLOCK_PTR)
return false;
- return cfg_layout_redirect_edge (e, newdest);
+ /* Hopefully the above conditions should suffice. */
+ if (!really_delete)
+ return true;
+
+ /* Redirecting behaves wrongly wrto this flag. */
+ irr = snd->flags & EDGE_IRREDUCIBLE_LOOP;
+
+ if (!redirect_edge_and_branch (e, newdest))
+ return false;
+ src->succ->flags &= ~EDGE_IRREDUCIBLE_LOOP;
+ src->succ->flags |= irr;
+
+ return true;
}
else
{
/* Cannot happen -- we are using this only to remove an edge
- from branch. */
+ from branch. */
abort ();
}
return false; /* To avoid warning, cannot get here. */
}
-/* Duplicates N basic blocks stored in array BBS (they form a body of
- duplicated loop). Newly created basic blocks are placed into array NEW_BBS
- that we allocate. Edges from basic blocks in BBS are also duplicated and
- copies of those of them that lead into BBS are redirected to appropriate
- newly created block. The function also assigns bbs into loops and updates
- dominators. If ADD_IRREDUCIBLE_FLAG is set, newly created basic blocks that
- are not members of any inner loop are marked irreducible.
-
- Additionally, we perform following manipulation with edges:
- We have two special edges given. LATCH_EDGE is the latch edge of the
- duplicated loop and leads into its header (one of blocks in BBS);
- it does not have neccessarily lead from one of the blocks, because
- we may be copying the loop body several times in unrolling.
- Edge ENTRY leads also leads to header, and it is either latch or entry
- edge. Copy of LATCH_EDGE is redirected to header and is stored in
- HEADER_EDGE, the ENTRY edge is redirected into copy of header and
- returned as COPY_HEADER_EDGE. The effect is following:
- if LATCH_EDGE == ENTRY, then the loop is unrolled by one copy,
- HEADER_EDGE is latch of a new loop, COPY_HEADER_EDGE leads from original
- latch source to first block in copy.
- if LATCH_EDGE != ENTRY, then the loop is peeled by one copy,
- HEADER_EDGE is entry edge of the loop, COPY_HEADER_EDGE leads from
- original entry block to first block in peeled copy.
- */
-static void
-copy_bbs (bbs, n, entry, latch_edge, new_bbs, loops, header_edge, copy_header_edge, add_irreducible_flag)
- basic_block *bbs;
- int n;
- edge entry;
- edge latch_edge;
- basic_block **new_bbs;
- struct loops *loops;
- edge *header_edge;
- edge *copy_header_edge;
- int add_irreducible_flag;
-{
- int i;
- basic_block bb, new_bb, header = entry->dest, dom_bb;
- edge e;
-
- /* Duplicate bbs, update dominators, assign bbs to loops. */
- (*new_bbs) = xcalloc (n, sizeof (basic_block));
- for (i = 0; i < n; i++)
- {
- /* Duplicate. */
- bb = bbs[i];
- new_bb = (*new_bbs)[i] = cfg_layout_duplicate_bb (bb, NULL);
- RBI (new_bb)->duplicated = 1;
- /* Add to loop. */
- add_bb_to_loop (new_bb, bb->loop_father->copy);
- add_to_dominance_info (loops->cfg.dom, new_bb);
- /* Possibly set header. */
- if (bb->loop_father->header == bb && bb != header)
- new_bb->loop_father->header = new_bb;
- /* Or latch. */
- if (bb->loop_father->latch == bb &&
- bb->loop_father != header->loop_father)
- new_bb->loop_father->latch = new_bb;
- /* Take care of irreducible loops. */
- if (add_irreducible_flag
- && bb->loop_father == header->loop_father)
- new_bb->flags |= BB_IRREDUCIBLE_LOOP;
- }
-
- /* Set dominators. */
- for (i = 0; i < n; i++)
- {
- bb = bbs[i];
- new_bb = (*new_bbs)[i];
- if (bb != header)
- {
- /* For anything else than loop header, just copy it. */
- dom_bb = get_immediate_dominator (loops->cfg.dom, bb);
- dom_bb = RBI (dom_bb)->copy;
- }
- else
- {
- /* Copy of header is dominated by entry source. */
- dom_bb = entry->src;
- }
- if (!dom_bb)
- abort ();
- set_immediate_dominator (loops->cfg.dom, new_bb, dom_bb);
- }
-
- /* Redirect edges. */
- for (i = 0; i < n; i++)
- {
- edge e_pred;
- new_bb = (*new_bbs)[i];
- bb = bbs[i];
- for (e = bb->pred; e; e = e_pred)
- {
- basic_block src = e->src;
-
- e_pred = e->pred_next;
-
- if (!RBI (src)->duplicated)
- continue;
-
- /* Leads to copied loop and it is not latch edge, redirect it. */
- if (bb != header)
- loop_redirect_edge (e, new_bb);
- }
- }
-
- /* Redirect header edge. */
- bb = RBI (latch_edge->src)->copy;
- for (e = bb->succ; e->dest != latch_edge->dest; e = e->succ_next);
- *header_edge = e;
- loop_redirect_edge (*header_edge, header);
-
- /* Redirect entry to copy of header. */
- loop_redirect_edge (entry, RBI (header)->copy);
- *copy_header_edge = entry;
-
- /* Clear information about duplicates. */
- for (i = 0; i < n; i++)
- RBI ((*new_bbs)[i])->duplicated = 0;
-}
-
/* Check whether LOOP's body can be duplicated. */
bool
-can_duplicate_loop_p (loop)
- struct loop *loop;
+can_duplicate_loop_p (struct loop *loop)
{
- basic_block *bbs;
- unsigned i;
-
- bbs = get_loop_body (loop);
-
- for (i = 0; i < loop->num_nodes; i++)
- {
- edge e;
-
- /* In case loop contains abnormal edge we can not redirect,
- we can't perform duplication. */
-
- for (e = bbs[i]->succ; e; e = e->succ_next)
- if ((e->flags & EDGE_ABNORMAL)
- && flow_bb_inside_loop_p (loop, e->dest))
- {
- free (bbs);
- return false;
- }
+ int ret;
+ basic_block *bbs = get_loop_body (loop);
- if (!cfg_layout_can_duplicate_bb_p (bbs[i]))
- {
- free (bbs);
- return false;
- }
- }
+ ret = can_copy_bbs_p (bbs, loop->num_nodes);
free (bbs);
-
- return true;
-}
-
-/* Record edges, leading from NBBS basic blocks stored in BBS, that were created
- by copying ORIG edge (or just ORIG edge if IS_ORIG is set).
- If ORIG is NULL, then record all edges coming outside of BBS. Store them
- into TO_REMOVE array that must be large enough to hold them all; their
- number is returned in N_TO_REMOVE. */
-static void
-record_exit_edges (orig, bbs, nbbs, to_remove, n_to_remove, is_orig)
- edge orig;
- basic_block *bbs;
- int nbbs;
- edge *to_remove;
- unsigned *n_to_remove;
- int is_orig;
-{
- sbitmap my_blocks;
- int i;
- edge e;
-
- if (orig)
- {
- if (is_orig)
- {
- to_remove[(*n_to_remove)++] = orig;
- return;
- }
-
- for (e = RBI (orig->src)->copy->succ; e; e = e->succ_next)
- if (e->dest == orig->dest)
- break;
- if (!e)
- abort ();
-
- to_remove[(*n_to_remove)++] = e;
- }
- else
- {
- my_blocks = sbitmap_alloc (last_basic_block);
- sbitmap_zero (my_blocks);
- for (i = 0; i < nbbs; i++)
- SET_BIT (my_blocks, bbs[i]->index);
-
- for (i = 0; i < nbbs; i++)
- for (e = bbs[i]->succ; e; e = e->succ_next)
- if (e->dest == EXIT_BLOCK_PTR ||
- !TEST_BIT (my_blocks, e->dest->index))
- to_remove[(*n_to_remove)++] = e;
-
- free (my_blocks);
- }
+
+ return ret;
}
-
#define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
-/* Duplicates body of LOOP to given edge E NDUPL times. Takes care of
- updating LOOPS structure and dominators. E's destination must be LOOP
- header for this to work, i.e. it must be entry or latch edge of this loop;
- these are unique, as the loops must have preheaders for this function to
- work correctly (in case E is latch, the function unrolls the loop, if E is
- entry edge, it peels the loop). Store edges created by copying ORIG edge
- (if NULL, then all edges leaving loop) from copies corresponding to set
- bits in WONT_EXIT bitmap (bit 0 corresponds to original LOOP body, the
- other copies are numbered in order given by control flow through them)
- into TO_REMOVE array. Returns false if duplication is impossible. */
+/* Duplicates body of LOOP to given edge E NDUPL times. Takes care of updating
+ LOOPS structure and dominators. E's destination must be LOOP header for
+ this to work, i.e. it must be entry or latch edge of this loop; these are
+ unique, as the loops must have preheaders for this function to work
+ correctly (in case E is latch, the function unrolls the loop, if E is entry
+ edge, it peels the loop). Store edges created by copying ORIG edge from
+ copies corresponding to set bits in WONT_EXIT bitmap (bit 0 corresponds to
+ original LOOP body, the other copies are numbered in order given by control
+ flow through them) into TO_REMOVE array. Returns false if duplication is
+ impossible. */
int
-duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit, orig,
- to_remove, n_to_remove, flags)
- struct loop *loop;
- edge e;
- struct loops *loops;
- unsigned ndupl;
- sbitmap wont_exit;
- edge orig;
- edge *to_remove;
- unsigned *n_to_remove;
- int flags;
+duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops,
+ unsigned int ndupl, sbitmap wont_exit,
+ edge orig, edge *to_remove,
+ unsigned int *n_to_remove, int flags)
{
struct loop *target, *aloop;
struct loop **orig_loops;
basic_block header = loop->header, latch = loop->latch;
basic_block *new_bbs, *bbs, *first_active;
basic_block new_bb, bb, first_active_latch = NULL;
- edge ae, latch_edge, he;
+ edge ae, latch_edge;
+ edge spec_edges[2], new_spec_edges[2];
+#define SE_LATCH 0
+#define SE_ORIG 1
unsigned i, j, n;
int is_latch = (latch == e->src);
int scale_act = 0, *scale_step = NULL, scale_main = 0;
bbs = get_loop_body (loop);
/* Check whether duplication is possible. */
-
- for (i = 0; i < loop->num_nodes; i++)
+ if (!can_copy_bbs_p (bbs, loop->num_nodes))
{
- if (!cfg_layout_can_duplicate_bb_p (bbs[i]))
- {
- free (bbs);
- return false;
- }
+ free (bbs);
+ return false;
}
+ new_bbs = xmalloc (sizeof (basic_block) * loop->num_nodes);
- add_irreducible_flag = !is_latch && (e->src->flags & BB_IRREDUCIBLE_LOOP);
+ /* In case we are doing loop peeling and the loop is in the middle of
+ irreducible region, the peeled copies will be inside it too. */
+ add_irreducible_flag = e->flags & EDGE_IRREDUCIBLE_LOOP;
+ if (is_latch && add_irreducible_flag)
+ abort ();
/* Find edge from latch. */
latch_edge = loop_latch_edge (loop);
scale_step = xmalloc (ndupl * sizeof (int));
for (i = 1; i <= ndupl; i++)
- scale_step[i - 1] = TEST_BIT (wont_exit, i)
+ scale_step[i - 1] = TEST_BIT (wont_exit, i)
? prob_pass_wont_exit
: prob_pass_thru;
}
/* Loop the new bbs will belong to. */
- target = find_common_loop (e->src->loop_father, e->dest->loop_father);
+ target = e->src->loop_father;
/* Original loops. */
n_orig_loops = 0;
orig_loops[i] = aloop;
loop->copy = target;
-
- /* Original basic blocks. */
+
n = loop->num_nodes;
- first_active = xcalloc(n, sizeof (basic_block));
+ first_active = xmalloc (n * sizeof (basic_block));
if (is_latch)
{
memcpy (first_active, bbs, n * sizeof (basic_block));
first_active_latch = latch;
}
- /* Record exit edges in original loop body. */
- if (TEST_BIT (wont_exit, 0))
- record_exit_edges (orig, bbs, n, to_remove, n_to_remove, true);
-
+ /* Record exit edge in original loop body. */
+ if (orig && TEST_BIT (wont_exit, 0))
+ to_remove[(*n_to_remove)++] = orig;
+
+ spec_edges[SE_ORIG] = orig;
+ spec_edges[SE_LATCH] = latch_edge;
+
for (j = 0; j < ndupl; j++)
{
/* Copy loops. */
copy_loops_to (loops, orig_loops, n_orig_loops, target);
/* Copy bbs. */
- copy_bbs (bbs, n, e, latch_edge, &new_bbs, loops,
- &e, &he, add_irreducible_flag);
- if (is_latch)
- loop->latch = RBI (latch)->copy;
+ copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop, loops);
- /* Record exit edges in this copy. */
- if (TEST_BIT (wont_exit, j + 1))
- record_exit_edges (orig, new_bbs, n, to_remove, n_to_remove, false);
-
- /* Set counts and frequencies. */
- for (i = 0; i < n; i++)
+ /* Note whether the blocks and edges belong to an irreducible loop. */
+ if (add_irreducible_flag)
{
- new_bb = new_bbs[i];
- bb = bbs[i];
-
- if (flags & DLTHE_FLAG_UPDATE_FREQ)
- {
- new_bb->count = RDIV (scale_act * bb->count, REG_BR_PROB_BASE);
- new_bb->frequency = RDIV (scale_act * bb->frequency,
- REG_BR_PROB_BASE);
- }
- else
+ for (i = 0; i < n; i++)
+ new_bbs[i]->rbi->duplicated = 1;
+ for (i = 0; i < n; i++)
{
- new_bb->count = bb->count;
- new_bb->frequency = bb->frequency;
+ new_bb = new_bbs[i];
+ if (new_bb->loop_father == target)
+ new_bb->flags |= BB_IRREDUCIBLE_LOOP;
+
+ for (ae = new_bb->succ; ae; ae = ae->succ_next)
+ if (ae->dest->rbi->duplicated
+ && (ae->src->loop_father == target
+ || ae->dest->loop_father == target))
+ ae->flags |= EDGE_IRREDUCIBLE_LOOP;
}
+ for (i = 0; i < n; i++)
+ new_bbs[i]->rbi->duplicated = 0;
+ }
- for (ae = new_bb->succ; ae; ae = ae->succ_next)
- ae->count = RDIV (new_bb->count * ae->probability,
- REG_BR_PROB_BASE);
+ /* Redirect the special edges. */
+ if (is_latch)
+ {
+ redirect_edge_and_branch_force (latch_edge, new_bbs[0]);
+ redirect_edge_and_branch_force (new_spec_edges[SE_LATCH],
+ loop->header);
+ set_immediate_dominator (loops->cfg.dom, new_bbs[0], latch);
+ latch = loop->latch = new_bbs[1];
+ e = latch_edge = new_spec_edges[SE_LATCH];
}
- if (flags & DLTHE_FLAG_UPDATE_FREQ)
- scale_act = RDIV (scale_act * scale_step[j], REG_BR_PROB_BASE);
+ else
+ {
+ redirect_edge_and_branch_force (new_spec_edges[SE_LATCH],
+ loop->header);
+ redirect_edge_and_branch_force (e, new_bbs[0]);
+ set_immediate_dominator (loops->cfg.dom, new_bbs[0], e->src);
+ e = new_spec_edges[SE_LATCH];
+ }
+
+ /* Record exit edge in this copy. */
+ if (orig && TEST_BIT (wont_exit, j + 1))
+ to_remove[(*n_to_remove)++] = new_spec_edges[SE_ORIG];
+ /* Record the first copy in the control flow order if it is not
+ the original loop (i.e. in case of peeling). */
if (!first_active_latch)
{
memcpy (first_active, new_bbs, n * sizeof (basic_block));
- first_active_latch = RBI (latch)->copy;
+ first_active_latch = new_bbs[1];
}
-
- free (new_bbs);
-
- /* Original loop header is dominated by latch copy
- if we duplicated on its only entry edge. */
- if (!is_latch && !header->pred->pred_next->pred_next)
- set_immediate_dominator (loops->cfg.dom, header, RBI (latch)->copy);
- if (is_latch && j == 0)
+
+ /* Set counts and frequencies. */
+ if (flags & DLTHE_FLAG_UPDATE_FREQ)
{
- /* Update edge from latch. */
- for (latch_edge = RBI (header)->copy->pred;
- latch_edge->src != latch;
- latch_edge = latch_edge->pred_next);
+ scale_bbs_frequencies (new_bbs, n, scale_act, REG_BR_PROB_BASE);
+ scale_act = RDIV (scale_act * scale_step[j], REG_BR_PROB_BASE);
}
}
- /* Now handle original loop. */
+ free (new_bbs);
+ free (orig_loops);
- /* Update edge counts. */
+ /* Update the original loop. */
+ if (!is_latch)
+ set_immediate_dominator (loops->cfg.dom, e->dest, e->src);
if (flags & DLTHE_FLAG_UPDATE_FREQ)
{
- for (i = 0; i < n; i++)
- {
- bb = bbs[i];
- bb->count = RDIV (scale_main * bb->count, REG_BR_PROB_BASE);
- bb->frequency = RDIV (scale_main * bb->frequency, REG_BR_PROB_BASE);
- for (ae = bb->succ; ae; ae = ae->succ_next)
- ae->count = RDIV (bb->count * ae->probability, REG_BR_PROB_BASE);
- }
+ scale_bbs_frequencies (bbs, n, scale_main, REG_BR_PROB_BASE);
free (scale_step);
}
- free (orig_loops);
- /* Update dominators of other blocks if affected. */
+ /* Update dominators of outer blocks if affected. */
for (i = 0; i < n; i++)
{
basic_block dominated, dom_bb, *dom_bbs;
entry; otherwise we also force preheader block to have only one successor.
The function also updates dominators stored in DOM. */
static basic_block
-create_preheader (loop, dom, flags)
- struct loop *loop;
- dominance_info dom;
- int flags;
+create_preheader (struct loop *loop, dominance_info dom, int flags)
{
edge e, fallthru;
basic_block dummy;
/* Split_block would not split block after its end. */
emit_note_after (NOTE_INSN_DELETED, insn);
}
- if (flags & CP_INSIDE_CFGLAYOUT)
- fallthru = cfg_layout_split_block (loop->header, insn);
- else
- fallthru = split_block (loop->header, insn);
+ fallthru = split_block (loop->header, insn);
dummy = fallthru->src;
loop->header = fallthru->dest;
ploop->latch = fallthru->dest;
add_to_dominance_info (dom, fallthru->dest);
-
- /* Redirect edges. */
+
+ /* Redirect edges. */
for (e = dummy->pred; e; e = e->pred_next)
{
src = e->src;
dummy->frequency -= EDGE_FREQUENCY (e);
dummy->count -= e->count;
fallthru->count -= e->count;
- if (flags & CP_INSIDE_CFGLAYOUT)
- cfg_layout_redirect_edge (e, loop->header);
- else
+ jump = redirect_edge_and_branch_force (e, loop->header);
+ if (jump)
{
- jump = redirect_edge_and_branch_force (e, loop->header);
- if (jump)
- {
- add_to_dominance_info (dom, jump);
- set_immediate_dominator (dom, jump, src);
- add_bb_to_loop (jump, loop);
- loop->latch = jump;
- }
+ add_to_dominance_info (dom, jump);
+ set_immediate_dominator (dom, jump, src);
+ add_bb_to_loop (jump, loop);
+ loop->latch = jump;
}
/* Update structures. */
/* Create preheaders for each loop from loop tree stored in LOOPS; for meaning
of FLAGS see create_preheader. */
void
-create_preheaders (loops, flags)
- struct loops *loops;
- int flags;
+create_preheaders (struct loops *loops, int flags)
{
unsigned i;
for (i = 1; i < loops->num; i++)
/* Forces all loop latches of loops from loop tree LOOPS to have only single
successor. */
void
-force_single_succ_latches (loops)
- struct loops *loops;
+force_single_succ_latches (struct loops *loops)
{
unsigned i;
struct loop *loop;
for (i = 1; i < loops->num; i++)
{
loop = loops->parray[i];
- if (!loop->latch->succ->succ_next)
+ if (loop->latch != loop->header
+ && !loop->latch->succ->succ_next)
continue;
-
+
for (e = loop->header->pred; e->src != loop->latch; e = e->pred_next)
continue;
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 (e, insns, loops)
- edge e;
- rtx insns;
- struct loops *loops;
+loop_split_edge_with (edge e, rtx insns, struct loops *loops)
{
basic_block src, dest, new_bb;
struct loop *loop_c;
edge new_e;
-
+
src = e->src;
dest = e->dest;
/* Create basic block for it. */
- new_bb = create_basic_block (NULL_RTX, NULL_RTX, EXIT_BLOCK_PTR->prev_bb);
+ new_bb = split_edge (e);
add_to_dominance_info (loops->cfg.dom, new_bb);
add_bb_to_loop (new_bb, loop_c);
new_bb->flags = insns ? BB_SUPERBLOCK : 0;
- if (src->flags & BB_IRREDUCIBLE_LOOP)
+
+ new_e = new_bb->succ;
+ if (e->flags & EDGE_IRREDUCIBLE_LOOP)
{
- /* We expect simple preheaders here. */
- if ((dest->flags & BB_IRREDUCIBLE_LOOP)
- || dest->loop_father->header == dest)
- new_bb->flags |= BB_IRREDUCIBLE_LOOP;
+ new_bb->flags |= BB_IRREDUCIBLE_LOOP;
+ new_e->flags |= EDGE_IRREDUCIBLE_LOOP;
}
- new_e = make_edge (new_bb, dest, EDGE_FALLTHRU);
- new_e->probability = REG_BR_PROB_BASE;
- new_e->count = e->count;
-
- new_bb->count = e->count;
- new_bb->frequency = EDGE_FREQUENCY (e);
- cfg_layout_redirect_edge (e, new_bb);
-
- alloc_aux_for_block (new_bb, sizeof (struct reorder_block_def));
if (insns)
- {
- start_sequence ();
- emit_insn (insns);
- insns = get_insns ();
- end_sequence ();
- emit_insn_after (insns, new_bb->end);
- }
+ emit_insn_after (insns, new_bb->end);
set_immediate_dominator (loops->cfg.dom, new_bb, src);
set_immediate_dominator (loops->cfg.dom, dest,
if (dest->loop_father->latch == src)
dest->loop_father->latch = new_bb;
-
+
return new_bb;
}
OSDN Git Service
