/* Loop manipulation code for GNU compiler.
- Copyright (C) 2002, 2003 Free Software Foundation, Inc.
+ Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
This file is part of GCC.
#include "cfglayout.h"
#include "output.h"
-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 (basic_block *, int);
+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 *);
+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 *, int);
+static void fix_irreducible_loops (basic_block);
+
+#define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
+
+/* Splits basic block BB after INSN, returns created edge. Updates loops
+ and dominators. */
+edge
+split_loop_bb (basic_block bb, rtx insn)
+{
+ edge e;
+
+ /* Split the block. */
+ e = split_block (bb, insn);
+
+ /* Add dest to loop. */
+ add_bb_to_loop (e->dest, e->src->loop_father);
+
+ return e;
+}
+
+/* Checks whether basic block BB is dominated by DATA. */
+static bool
+rpe_enum_p (basic_block bb, void *data)
+{
+ 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
+ into array BBS, that will be allocated large enough to contain them.
+ 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 (edge e, basic_block **bbs)
+{
+ if (e->dest->pred->pred_next)
+ abort ();
+
+ /* Find bbs in the path. */
+ *bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
+ return dfs_enumerate_from (e->dest, 0, rpe_enum_p, *bbs,
+ n_basic_blocks, e->dest);
+}
+
+/* Fix placement of basic block BB inside loop hierarchy stored in LOOPS --
+ Let L be a loop to that BB belongs. Then every successor of BB must either
+ 1) belong to some superloop of loop L, or
+ 2) be a header of loop K such that K->outer is superloop of L
+ Returns true if we had to move BB into other loop to enforce this condition,
+ false if the placement of BB was already correct (provided that placements
+ of its successors are correct). */
+static bool
+fix_bb_placement (struct loops *loops, basic_block bb)
+{
+ edge e;
+ struct loop *loop = loops->tree_root, *act;
+
+ for (e = bb->succ; e; e = e->succ_next)
+ {
+ if (e->dest == EXIT_BLOCK_PTR)
+ continue;
+
+ act = e->dest->loop_father;
+ if (act->header == e->dest)
+ act = act->outer;
+
+ if (flow_loop_nested_p (loop, act))
+ loop = act;
+ }
+
+ if (loop == bb->loop_father)
+ return false;
+
+ remove_bb_from_loops (bb);
+ add_bb_to_loop (bb, loop);
+
+ return true;
+}
+
+/* Fix placements of basic blocks inside loop hierarchy stored in loops; i.e.
+ enforce condition condition stated in description of fix_bb_placement. We
+ start from basic block FROM that had some of its successors removed, so that
+ 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 similar, except that instead of
+ successors we consider edges coming out of the loops. */
+static void
+fix_bb_placements (struct loops *loops, basic_block from)
+{
+ sbitmap in_queue;
+ basic_block *queue, *qtop, *qbeg, *qend;
+ struct loop *base_loop;
+ edge e;
+
+ /* We pass through blocks back-reachable from FROM, testing whether some
+ of their successors moved to outer loop. It may be necessary to
+ iterate several times, but it is finite, as we stop unless we move
+ the basic block up the loop structure. The whole story is a bit
+ more complicated due to presence of subloops, those are moved using
+ fix_loop_placement. */
+
+ base_loop = from->loop_father;
+ if (base_loop == loops->tree_root)
+ return;
+
+ in_queue = sbitmap_alloc (last_basic_block);
+ sbitmap_zero (in_queue);
+ SET_BIT (in_queue, from->index);
+ /* Prevent us from going out of the base_loop. */
+ SET_BIT (in_queue, base_loop->header->index);
+
+ queue = xmalloc ((base_loop->num_nodes + 1) * sizeof (basic_block));
+ qtop = queue + base_loop->num_nodes + 1;
+ qbeg = queue;
+ qend = queue + 1;
+ *qbeg = from;
+
+ while (qbeg != qend)
+ {
+ from = *qbeg;
+ qbeg++;
+ if (qbeg == qtop)
+ qbeg = queue;
+ RESET_BIT (in_queue, from->index);
+
+ if (from->loop_father->header == from)
+ {
+ /* Subloop header, maybe move the loop upward. */
+ if (!fix_loop_placement (from->loop_father))
+ continue;
+ }
+ else
+ {
+ /* Ordinary basic block. */
+ if (!fix_bb_placement (loops, from))
+ continue;
+ }
+
+ /* Something has changed, insert predecessors into queue. */
+ for (e = from->pred; e; e = e->pred_next)
+ {
+ basic_block pred = e->src;
+ struct loop *nca;
+
+ if (TEST_BIT (in_queue, pred->index))
+ continue;
+
+ /* 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);
+ if (pred->loop_father != base_loop
+ && (nca == base_loop
+ || nca != pred->loop_father))
+ pred = pred->loop_father->header;
+ else if (!flow_loop_nested_p (from->loop_father, pred->loop_father))
+ {
+ /* No point in processing it. */
+ continue;
+ }
+
+ if (TEST_BIT (in_queue, pred->index))
+ continue;
+
+ /* Schedule the basic block. */
+ *qend = pred;
+ qend++;
+ if (qend == qtop)
+ qend = queue;
+ SET_BIT (in_queue, pred->index);
+ }
+ }
+ free (in_queue);
+ 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 (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;
+
+ 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)->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 (CDI_DOMINATORS,
+ e->src->loop_father->latch, e->dest))
+ unloop (loops, e->src->loop_father);
+
+ /* Identify the path. */
+ nrem = find_path (e, &rem_bbs);
+
+ n_bord_bbs = 0;
+ bord_bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
+ seen = sbitmap_alloc (last_basic_block);
+ sbitmap_zero (seen);
+
+ /* Find "border" hexes -- i.e. those with predecessor in removed path. */
+ for (i = 0; i < nrem; i++)
+ SET_BIT (seen, rem_bbs[i]->index);
+ 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;
+ }
+ }
+
+ /* Remove the path. */
+ from = e->src;
+ if (!loop_delete_branch_edge (e, 1))
+ abort ();
+ dom_bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
+
+ /* 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);
+ for (i = 0; i < n_bord_bbs; i++)
+ {
+ basic_block ldom;
+
+ bb = get_immediate_dominator (CDI_DOMINATORS, bord_bbs[i]);
+ if (TEST_BIT (seen, bb->index))
+ continue;
+ SET_BIT (seen, bb->index);
+
+ for (ldom = first_dom_son (CDI_DOMINATORS, bb);
+ ldom;
+ ldom = next_dom_son (CDI_DOMINATORS, ldom))
+ if (!dominated_by_p (CDI_DOMINATORS, from, ldom))
+ dom_bbs[n_dom_bbs++] = ldom;
+ }
+
+ free (seen);
+
+ /* Recount dominators. */
+ iterate_fix_dominators (CDI_DOMINATORS, 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);
+ fix_loop_placements (loops, from->loop_father);
+
+ return true;
+}
+
+/* Predicate for enumeration in add_loop. */
+static bool
+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 (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. */
+ bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
+ n = dfs_enumerate_from (loop->latch, 1, alp_enum_p,
+ 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);
+}
+
+/* Multiply all frequencies of basic blocks in array BBS of length NBBS
+ by NUM/DEN. */
+static void
+scale_bbs_frequencies (basic_block *bbs, int nbbs, int num, int den)
+{
+ int i;
+ edge e;
+
+ for (i = 0; i < nbbs; i++)
+ {
+ bbs[i]->frequency = (bbs[i]->frequency * num) / den;
+ bbs[i]->count = RDIV (bbs[i]->count * num, den);
+ for (e = bbs[i]->succ; e; e = e->succ_next)
+ e->count = (e->count * num) /den;
+ }
+}
+
+/* Multiply all frequencies in LOOP by NUM/DEN. */
+static void
+scale_loop_frequencies (struct loop *loop, int num, int den)
+{
+ basic_block *bbs;
+
+ bbs = get_loop_body (loop);
+ scale_bbs_frequencies (bbs, loop->num_nodes, num, den);
+ free (bbs);
+}
+
+/* Make area between HEADER_EDGE and LATCH_EDGE a loop by connecting
+ latch to header and update loop tree stored in LOOPS and dominators
+ accordingly. Everything between them plus LATCH_EDGE destination must
+ be dominated by HEADER_EDGE destination, and back-reachable from
+ LATCH_EDGE source. HEADER_EDGE is redirected to basic block SWITCH_BB,
+ FALLTHRU_EDGE (SWITCH_BB) to original destination of HEADER_EDGE and
+ BRANCH_EDGE (SWITCH_BB) to original destination of LATCH_EDGE.
+ Returns newly created loop. */
+
+struct loop *
+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;
+ basic_block *dom_bbs, *body;
+ unsigned n_dom_bbs, i;
+ sbitmap seen;
+ struct loop *loop = xcalloc (1, sizeof (struct loop));
+ struct loop *outer = succ_bb->loop_father->outer;
+ int freq, prob, tot_prob;
+ gcov_type cnt;
+ edge e;
+
+ loop->header = header_edge->dest;
+ loop->latch = latch_edge->src;
+
+ freq = EDGE_FREQUENCY (header_edge);
+ cnt = header_edge->count;
+ prob = switch_bb->succ->probability;
+ tot_prob = prob + switch_bb->succ->succ_next->probability;
+ if (tot_prob == 0)
+ tot_prob = 1;
+
+ /* Redirect edges. */
+ loop_redirect_edge (latch_edge, loop->header);
+ loop_redirect_edge (BRANCH_EDGE (switch_bb), succ_bb);
+
+ loop_redirect_edge (header_edge, switch_bb);
+ loop_redirect_edge (FALLTHRU_EDGE (switch_bb), loop->header);
+
+ /* Update dominators. */
+ set_immediate_dominator (CDI_DOMINATORS, switch_bb, pred_bb);
+ set_immediate_dominator (CDI_DOMINATORS, loop->header, switch_bb);
+
+ 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. */
+ switch_bb->frequency = freq;
+ switch_bb->count = cnt;
+ for (e = switch_bb->succ; e; e = e->succ_next)
+ e->count = (switch_bb->count * e->probability) / REG_BR_PROB_BASE;
+ scale_loop_frequencies (loop, prob, tot_prob);
+ scale_loop_frequencies (succ_bb->loop_father, tot_prob - prob, tot_prob);
+
+ /* Update dominators of blocks outside of LOOP. */
+ dom_bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
+ n_dom_bbs = 0;
+ seen = sbitmap_alloc (last_basic_block);
+ sbitmap_zero (seen);
+ body = get_loop_body (loop);
+
+ for (i = 0; i < loop->num_nodes; i++)
+ SET_BIT (seen, body[i]->index);
+
+ for (i = 0; i < loop->num_nodes; i++)
+ {
+ basic_block ldom;
+
+ for (ldom = first_dom_son (CDI_DOMINATORS, body[i]);
+ ldom;
+ ldom = next_dom_son (CDI_DOMINATORS, ldom))
+ if (!TEST_BIT (seen, ldom->index))
+ {
+ SET_BIT (seen, ldom->index);
+ dom_bbs[n_dom_bbs++] = ldom;
+ }
+ }
+
+ iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs);
+
+ free (body);
+ free (seen);
+ free (dom_bbs);
+
+ 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 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 (struct loop *loop)
+{
+ basic_block *body;
+ unsigned i;
+ edge e;
+ struct loop *father = loop->pred[0], *act;
+
+ body = get_loop_body (loop);
+ for (i = 0; i < loop->num_nodes; i++)
+ for (e = body[i]->succ; e; e = e->succ_next)
+ if (!flow_bb_inside_loop_p (loop, e->dest))
+ {
+ act = find_common_loop (loop, e->dest->loop_father);
+ if (flow_loop_nested_p (father, act))
+ father = act;
+ }
+ free (body);
+
+ if (father != loop->outer)
+ {
+ for (act = loop->outer; act != father; act = act->outer)
+ act->num_nodes -= loop->num_nodes;
+ flow_loop_tree_node_remove (loop);
+ flow_loop_tree_node_add (father, loop);
+ return 1;
+ }
+ return 0;
+}
+
+/* Fix placement of superloops of LOOP inside loop tree, i.e. ensure that
+ condition stated in description of fix_loop_placement holds for them.
+ 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 (struct loops *loops, struct loop *loop)
+{
+ struct loop *outer;
+
+ while (loop->outer)
+ {
+ outer = loop->outer;
+ if (!fix_loop_placement (loop))
+ break;
+
+ /* Changing the placement of a loop in the loop tree may alter the
+ validity of condition 2) of the description of fix_bb_placement
+ for its preheader, because the successor is the header and belongs
+ to the loop. So call fix_bb_placements to fix up the placement
+ of the preheader and (possibly) of its predecessors. */
+ fix_bb_placements (loops, loop_preheader_edge (loop)->src);
+ loop = outer;
+ }
+}
+
+/* Creates place for a new LOOP in LOOPS structure. */
+static void
+place_new_loop (struct loops *loops, struct loop *loop)
+{
+ loops->parray =
+ xrealloc (loops->parray, (loops->num + 1) * sizeof (struct loop *));
+ loops->parray[loops->num] = loop;
+
+ loop->num = loops->num++;
+}
+
+/* Copies copy of LOOP as subloop of TARGET loop, placing newly
+ created loop into LOOPS structure. */
+static struct loop *
+duplicate_loop (struct loops *loops, struct loop *loop, struct loop *target)
+{
+ struct loop *cloop;
+ cloop = xcalloc (1, sizeof (struct loop));
+ place_new_loop (loops, cloop);
+
+ /* Initialize copied loop. */
+ cloop->level = loop->level;
+
+ /* Set it as copy of loop. */
+ loop->copy = cloop;
+
+ /* Add it to target. */
+ flow_loop_tree_node_add (target, cloop);
+
+ return cloop;
+}
+
+/* Copies structure of subloops of LOOP into TARGET loop, placing
+ newly created loops into loop tree stored in LOOPS. */
+static void
+duplicate_subloops (struct loops *loops, struct loop *loop, struct loop *target)
+{
+ struct loop *aloop, *cloop;
+
+ for (aloop = loop->inner; aloop; aloop = aloop->next)
+ {
+ cloop = duplicate_loop (loops, aloop, target);
+ duplicate_subloops (loops, 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 (struct loops *loops, struct loop **copied_loops, int n, struct loop *target)
+{
+ struct loop *aloop;
+ int i;
+
+ for (i = 0; i < n; i++)
+ {
+ aloop = duplicate_loop (loops, copied_loops[i], target);
+ duplicate_subloops (loops, copied_loops[i], aloop);
+ }
+}
+
+/* Redirects edge E to basic block DEST. */
+static void
+loop_redirect_edge (edge e, basic_block dest)
+{
+ if (e->dest == dest)
+ return;
+
+ redirect_edge_and_branch_force (e, dest);
+}
+
+/* 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 (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;
+ /* And it must be just a simple branch. */
+ if (!any_condjump_p (BB_END (src)))
+ return false;
+
+ snd = e == src->succ ? src->succ->succ_next : src->succ;
+ newdest = snd->dest;
+ if (newdest == EXIT_BLOCK_PTR)
+ return false;
+
+ /* 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. */
+ abort ();
+ }
+
+ return false; /* To avoid warning, cannot get here. */
+}
+
+/* Check whether LOOP's body can be duplicated. */
+bool
+can_duplicate_loop_p (struct loop *loop)
+{
+ int ret;
+ basic_block *bbs = get_loop_body (loop);
+
+ ret = can_copy_bbs_p (bbs, loop->num_nodes);
+ free (bbs);
+
+ return ret;
+}
+
+
+/* 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 (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;
+ unsigned n_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;
+ 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;
+ int p, freq_in, freq_le, freq_out_orig;
+ int prob_pass_thru, prob_pass_wont_exit, prob_pass_main;
+ int add_irreducible_flag;
+
+ if (e->dest != loop->header)
+ abort ();
+ if (ndupl <= 0)
+ abort ();
+
+ if (orig)
+ {
+ /* Orig must be edge out of the loop. */
+ if (!flow_bb_inside_loop_p (loop, orig->src))
+ abort ();
+ if (flow_bb_inside_loop_p (loop, orig->dest))
+ abort ();
+ }
+
+ bbs = get_loop_body (loop);
+
+ /* Check whether duplication is possible. */
+ if (!can_copy_bbs_p (bbs, loop->num_nodes))
+ {
+ free (bbs);
+ return false;
+ }
+ new_bbs = xmalloc (sizeof (basic_block) * loop->num_nodes);
+
+ /* 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);
+
+ if (flags & DLTHE_FLAG_UPDATE_FREQ)
+ {
+ /* Calculate coefficients by that we have to scale frequencies
+ of duplicated loop bodies. */
+ freq_in = header->frequency;
+ freq_le = EDGE_FREQUENCY (latch_edge);
+ if (freq_in == 0)
+ freq_in = 1;
+ if (freq_in < freq_le)
+ freq_in = freq_le;
+ freq_out_orig = orig ? EDGE_FREQUENCY (orig) : freq_in - freq_le;
+ if (freq_out_orig > freq_in - freq_le)
+ freq_out_orig = freq_in - freq_le;
+ prob_pass_thru = RDIV (REG_BR_PROB_BASE * freq_le, freq_in);
+ prob_pass_wont_exit =
+ RDIV (REG_BR_PROB_BASE * (freq_le + freq_out_orig), freq_in);
+
+ scale_step = xmalloc (ndupl * sizeof (int));
+
+ for (i = 1; i <= ndupl; i++)
+ scale_step[i - 1] = TEST_BIT (wont_exit, i)
+ ? prob_pass_wont_exit
+ : prob_pass_thru;
+
+ if (is_latch)
+ {
+ prob_pass_main = TEST_BIT (wont_exit, 0)
+ ? prob_pass_wont_exit
+ : prob_pass_thru;
+ p = prob_pass_main;
+ scale_main = REG_BR_PROB_BASE;
+ for (i = 0; i < ndupl; i++)
+ {
+ scale_main += p;
+ p = RDIV (p * scale_step[i], REG_BR_PROB_BASE);
+ }
+ scale_main = RDIV (REG_BR_PROB_BASE * REG_BR_PROB_BASE, scale_main);
+ scale_act = RDIV (scale_main * prob_pass_main, REG_BR_PROB_BASE);
+ }
+ else
+ {
+ scale_main = REG_BR_PROB_BASE;
+ for (i = 0; i < ndupl; i++)
+ scale_main = RDIV (scale_main * scale_step[i], REG_BR_PROB_BASE);
+ scale_act = REG_BR_PROB_BASE - prob_pass_thru;
+ }
+ for (i = 0; i < ndupl; i++)
+ if (scale_step[i] < 0 || scale_step[i] > REG_BR_PROB_BASE)
+ abort ();
+ if (scale_main < 0 || scale_main > REG_BR_PROB_BASE
+ || scale_act < 0 || scale_act > REG_BR_PROB_BASE)
+ abort ();
+ }
+
+ /* Loop the new bbs will belong to. */
+ target = e->src->loop_father;
+
+ /* Original loops. */
+ n_orig_loops = 0;
+ for (aloop = loop->inner; aloop; aloop = aloop->next)
+ n_orig_loops++;
+ orig_loops = xcalloc (n_orig_loops, sizeof (struct loop *));
+ for (aloop = loop->inner, i = 0; aloop; aloop = aloop->next, i++)
+ orig_loops[i] = aloop;
+
+ loop->copy = target;
+
+ n = loop->num_nodes;
+
+ first_active = xmalloc (n * sizeof (basic_block));
+ if (is_latch)
+ {
+ memcpy (first_active, bbs, n * sizeof (basic_block));
+ first_active_latch = latch;
+ }
+
+ /* 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, new_bbs, spec_edges, 2, new_spec_edges, loop);
+
+ /* Note whether the blocks and edges belong to an irreducible loop. */
+ if (add_irreducible_flag)
+ {
+ for (i = 0; i < n; i++)
+ new_bbs[i]->rbi->duplicated = 1;
+ for (i = 0; i < n; i++)
+ {
+ 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;
+ }
+
+ /* 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 (CDI_DOMINATORS, new_bbs[0], latch);
+ latch = loop->latch = new_bbs[1];
+ e = latch_edge = new_spec_edges[SE_LATCH];
+ }
+ 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 (CDI_DOMINATORS, 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 = new_bbs[1];
+ }
+
+ /* Set counts and frequencies. */
+ if (flags & DLTHE_FLAG_UPDATE_FREQ)
+ {
+ scale_bbs_frequencies (new_bbs, n, scale_act, REG_BR_PROB_BASE);
+ scale_act = RDIV (scale_act * scale_step[j], REG_BR_PROB_BASE);
+ }
+ }
+ free (new_bbs);
+ free (orig_loops);
+
+ /* Update the original loop. */
+ if (!is_latch)
+ set_immediate_dominator (CDI_DOMINATORS, e->dest, e->src);
+ if (flags & DLTHE_FLAG_UPDATE_FREQ)
+ {
+ scale_bbs_frequencies (bbs, n, scale_main, REG_BR_PROB_BASE);
+ free (scale_step);
+ }
+
+ /* Update dominators of outer blocks if affected. */
+ for (i = 0; i < n; i++)
+ {
+ basic_block dominated, dom_bb, *dom_bbs;
+ int n_dom_bbs,j;
+
+ bb = bbs[i];
+ n_dom_bbs = get_dominated_by (CDI_DOMINATORS, bb, &dom_bbs);
+ for (j = 0; j < n_dom_bbs; j++)
+ {
+ dominated = dom_bbs[j];
+ if (flow_bb_inside_loop_p (loop, dominated))
+ continue;
+ dom_bb = nearest_common_dominator (
+ CDI_DOMINATORS, first_active[i], first_active_latch);
+ set_immediate_dominator (CDI_DOMINATORS, dominated, dom_bb);
+ }
+ free (dom_bbs);
+ }
+ free (first_active);
+
+ free (bbs);
+
+ return true;
+}
+
+/* A callback for make_forwarder block, to redirect all edges except for
+ MFB_KJ_EDGE to the entry part. E is the edge for that we should decide
+ whether to redirect it. */
+
+static edge mfb_kj_edge;
+static bool
+mfb_keep_just (edge e)
+{
+ 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 = jump->succ->dest->loop_father;
+
+ if (dom_computed[CDI_DOMINATORS])
+ set_immediate_dominator (CDI_DOMINATORS, jump, jump->pred->src);
+ 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.
- */
+ The function also updates dominators. */
+
static basic_block
-create_preheader (loop, dom, flags)
- struct loop *loop;
- dominance_info dom;
- int flags;
+create_preheader (struct loop *loop, int flags)
{
edge e, fallthru;
basic_block dummy;
- basic_block jump, src = 0;
struct loop *cloop, *ploop;
int nentry = 0;
- rtx insn;
+ bool irred = false;
cloop = loop->outer;
{
if (e->src == loop->latch)
continue;
+ irred |= (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
nentry++;
}
if (!nentry)
return NULL;
}
- insn = first_insn_after_basic_block_note (loop->header);
- if (insn)
- insn = PREV_INSN (insn);
- else
- insn = get_last_insn ();
- if (insn == loop->header->end)
- {
- /* 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);
+ mfb_kj_edge = loop_latch_edge (loop);
+ fallthru = make_forwarder_block (loop->header, mfb_keep_just,
+ mfb_update_loops);
dummy = fallthru->src;
loop->header = fallthru->dest;
if (ploop->latch == dummy)
ploop->latch = fallthru->dest;
- add_to_dominance_info (dom, fallthru->dest);
-
- /* Redirect edges. */
+ /* Reorganize blocks so that the preheader is not stuck in the middle of the
+ loop. */
for (e = dummy->pred; e; e = e->pred_next)
- {
- src = e->src;
- if (src == loop->latch)
- break;
- }
- if (!e)
- abort ();
+ if (e->src != loop->latch)
+ break;
+ move_block_after (dummy, 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
+ loop->header->loop_father = loop;
+ add_bb_to_loop (dummy, cloop);
+
+ if (irred)
{
- 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;
- }
+ dummy->flags |= BB_IRREDUCIBLE_LOOP;
+ dummy->succ->flags |= EDGE_IRREDUCIBLE_LOOP;
}
- /* Update structures. */
- redirect_immediate_dominators (dom, dummy, loop->header);
- set_immediate_dominator (dom, loop->header, dummy);
- loop->header->loop_father = loop;
- add_bb_to_loop (dummy, cloop);
- if (rtl_dump_file)
- fprintf (rtl_dump_file, "Created preheader block for loop %i\n",
+ if (dump_file)
+ fprintf (dump_file, "Created preheader block for loop %i\n",
loop->num);
return dummy;
}
-/* Create preheaders for each loop; for meaning of flags see
- create_preheader. */
+/* 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++)
- create_preheader (loops->parray[i], loops->cfg.dom, flags);
+ create_preheader (loops->parray[i], flags);
loops->state |= LOOPS_HAVE_PREHEADERS;
}
-/* Forces all loop latches to have only single successor. */
+/* 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;
- loop_split_edge_with (e, NULL_RTX, loops);
+ loop_split_edge_with (e, NULL_RTX);
}
loops->state |= LOOPS_HAVE_SIMPLE_LATCHES;
}
-/* A quite stupid function to put INSNS on E. They are supposed to form
- just one basic block. Jumps out are not handled, so cfg do not have to
- be ok after this function. */
+/* 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 (e, insns, loops)
- edge e;
- rtx insns;
- struct loops *loops;
+loop_split_edge_with (edge e, rtx insns)
{
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);
- add_to_dominance_info (loops->cfg.dom, new_bb);
+ new_bb = split_edge (e);
add_bb_to_loop (new_bb, loop_c);
new_bb->flags = insns ? BB_SUPERBLOCK : 0;
- if (src->flags & BB_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_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)
+ new_e = new_bb->succ;
+ if (e->flags & EDGE_IRREDUCIBLE_LOOP)
{
- start_sequence ();
- emit_insn (insns);
- insns = get_insns ();
- end_sequence ();
- emit_insn_after (insns, new_bb->end);
+ new_bb->flags |= BB_IRREDUCIBLE_LOOP;
+ new_e->flags |= EDGE_IRREDUCIBLE_LOOP;
}
- set_immediate_dominator (loops->cfg.dom, new_bb, src);
- set_immediate_dominator (loops->cfg.dom, dest,
- recount_dominator (loops->cfg.dom, dest));
+ 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;
}
+
+/* Uses the natural loop discovery to recreate loop notes. */
+void
+create_loop_notes (void)
+{
+ rtx insn, head, end;
+ struct loops loops;
+ struct loop *loop;
+ basic_block *first, *last, bb, pbb;
+ struct loop **stack, **top;
+
+#ifdef ENABLE_CHECKING
+ /* Verify that there really are no loop notes. */
+ for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
+ if (NOTE_P (insn)
+ && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
+ abort ();
+#endif
+
+ flow_loops_find (&loops, LOOP_TREE);
+ free_dominance_info (CDI_DOMINATORS);
+ if (loops.num > 1)
+ {
+ last = xcalloc (loops.num, sizeof (basic_block));
+
+ FOR_EACH_BB (bb)
+ {
+ for (loop = bb->loop_father; loop->outer; loop = loop->outer)
+ last[loop->num] = bb;
+ }
+
+ first = xcalloc (loops.num, sizeof (basic_block));
+ stack = xcalloc (loops.num, sizeof (struct loop *));
+ top = stack;
+
+ FOR_EACH_BB (bb)
+ {
+ for (loop = bb->loop_father; loop->outer; loop = loop->outer)
+ {
+ if (!first[loop->num])
+ {
+ *top++ = loop;
+ first[loop->num] = bb;
+ }
+
+ if (bb == last[loop->num])
+ {
+ /* Prevent loops from overlapping. */
+ while (*--top != loop)
+ last[(*top)->num] = EXIT_BLOCK_PTR;
+
+ /* If loop starts with jump into it, place the note in
+ front of the jump. */
+ insn = PREV_INSN (BB_HEAD (first[loop->num]));
+ if (insn
+ && BARRIER_P (insn))
+ insn = PREV_INSN (insn);
+
+ if (insn
+ && JUMP_P (insn)
+ && any_uncondjump_p (insn)
+ && onlyjump_p (insn))
+ {
+ pbb = BLOCK_FOR_INSN (insn);
+ if (!pbb || !pbb->succ || pbb->succ->succ_next)
+ abort ();
+
+ if (!flow_bb_inside_loop_p (loop, pbb->succ->dest))
+ insn = BB_HEAD (first[loop->num]);
+ }
+ else
+ insn = BB_HEAD (first[loop->num]);
+
+ head = BB_HEAD (first[loop->num]);
+ emit_note_before (NOTE_INSN_LOOP_BEG, insn);
+ BB_HEAD (first[loop->num]) = head;
+
+ /* Position the note correctly wrto barrier. */
+ insn = BB_END (last[loop->num]);
+ if (NEXT_INSN (insn)
+ && BARRIER_P (NEXT_INSN (insn)))
+ insn = NEXT_INSN (insn);
+
+ end = BB_END (last[loop->num]);
+ emit_note_after (NOTE_INSN_LOOP_END, insn);
+ BB_END (last[loop->num]) = end;
+ }
+ }
+ }
+
+ free (first);
+ free (last);
+ free (stack);
+ }
+ flow_loops_free (&loops);
+}