#include "basic-block.h"
#include "cfgloop.h"
#include "cfglayout.h"
+#include "cfghooks.h"
#include "output.h"
static void duplicate_subloops (struct loops *, struct loop *, struct loop *);
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);
static void unloop (struct loops *, struct loop *);
int stack_top;
sbitmap on_stack;
edge *edges, e;
- unsigned n_edges, i;
+ unsigned num_edges, i;
if (!(from->flags & BB_IRREDUCIBLE_LOOP))
return;
bb->flags &= ~BB_IRREDUCIBLE_LOOP;
if (bb->loop_father->header == bb)
- edges = get_loop_exit_edges (bb->loop_father, &n_edges);
+ edges = get_loop_exit_edges (bb->loop_father, &num_edges);
else
{
- n_edges = EDGE_COUNT (bb->succs);
- edges = xmalloc (n_edges * sizeof (edge));
+ num_edges = EDGE_COUNT (bb->succs);
+ edges = xmalloc (num_edges * sizeof (edge));
FOR_EACH_EDGE (e, ei, bb->succs)
edges[ei.index] = e;
}
- for (i = 0; i < n_edges; i++)
+ for (i = 0; i < num_edges; i++)
{
e = edges[i];
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 (EDGE_COUNT (e->dest->preds) > 1)
- e = EDGE_PRED (loop_split_edge_with (e, NULL_RTX), 0);
+ 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
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++)
- {
- edge_iterator ei;
- bbs[i]->frequency = (bbs[i]->frequency * num) / den;
- bbs[i]->count = RDIV (bbs[i]->count * num, den);
- FOR_EACH_EDGE (e, ei, bbs[i]->succs)
- 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);
+ scale_bbs_frequencies_int (bbs, loop->num_nodes, num, den);
free (bbs);
}
unsigned i, n;
basic_block latch = loop->latch;
edge *edges;
- unsigned n_edges;
+ unsigned num_edges;
/* This is relatively straightforward. The dominators are unchanged, as
loop header dominates loop latch, so the only thing we have to care of
its work. */
body = get_loop_body (loop);
- edges = get_loop_exit_edges (loop, &n_edges);
+ edges = get_loop_exit_edges (loop, &num_edges);
n = loop->num_nodes;
for (i = 0; i < n; i++)
if (body[i]->loop_father == loop)
loops->parray[loop->num] = NULL;
flow_loop_free (loop);
- remove_edge (EDGE_SUCC (latch, 0));
+ remove_edge (single_succ_edge (latch));
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++)
+ for (i = 0; i < num_edges; i++)
if (edges[i]->flags & EDGE_IRREDUCIBLE_LOOP)
break;
- if (i != n_edges)
+ if (i != num_edges)
mark_irreducible_loops (loops);
free (edges);
}
if (!redirect_edge_and_branch (e, newdest))
return false;
- EDGE_SUCC (src, 0)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
- EDGE_SUCC (src, 0)->flags |= irr;
+ single_succ_edge (src)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
+ single_succ_edge (src)->flags |= irr;
return true;
}
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
+bool
duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops,
unsigned int ndupl, sbitmap wont_exit,
edge orig, edge *to_remove,
/* Set counts and frequencies. */
if (flags & DLTHE_FLAG_UPDATE_FREQ)
{
- scale_bbs_frequencies (new_bbs, n, scale_act, REG_BR_PROB_BASE);
+ scale_bbs_frequencies_int (new_bbs, n, scale_act, REG_BR_PROB_BASE);
scale_act = RDIV (scale_act * scale_step[j], REG_BR_PROB_BASE);
}
}
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);
+ scale_bbs_frequencies_int (bbs, n, scale_main, REG_BR_PROB_BASE);
free (scale_step);
}
static void
mfb_update_loops (basic_block jump)
{
- struct loop *loop = EDGE_SUCC (jump, 0)->dest->loop_father;
+ struct loop *loop = single_succ (jump)->loop_father;
if (dom_computed[CDI_DOMINATORS])
- set_immediate_dominator (CDI_DOMINATORS, jump, EDGE_PRED (jump, 0)->src);
+ set_immediate_dominator (CDI_DOMINATORS, jump, single_pred (jump));
add_bb_to_loop (jump, loop);
loop->latch = jump;
}
continue;
irred |= (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
nentry++;
- if (EDGE_COUNT (e->src->succs) == 1)
+ if (single_succ_p (e->src))
one_succ_pred = e;
}
gcc_assert (nentry);
e = EDGE_PRED (loop->header,
EDGE_PRED (loop->header, 0)->src == loop->latch);
- if (!(flags & CP_SIMPLE_PREHEADERS) || EDGE_COUNT (e->src->succs) == 1)
+ if (!(flags & CP_SIMPLE_PREHEADERS) || single_succ_p (e->src))
return NULL;
}
if (irred)
{
dummy->flags |= BB_IRREDUCIBLE_LOOP;
- EDGE_SUCC (dummy, 0)->flags |= EDGE_IRREDUCIBLE_LOOP;
+ single_succ_edge (dummy)->flags |= EDGE_IRREDUCIBLE_LOOP;
}
if (dump_file)
for (i = 1; i < loops->num; i++)
{
loop = loops->parray[i];
- if (loop->latch != loop->header && EDGE_COUNT (loop->latch->succs) == 1)
+ if (loop->latch != loop->header && single_succ_p (loop->latch))
continue;
e = find_edge (loop->latch, loop->header);
&& onlyjump_p (insn))
{
pbb = BLOCK_FOR_INSN (insn);
- gcc_assert (pbb && EDGE_COUNT (pbb->succs) == 1);
+ gcc_assert (pbb && single_succ_p (pbb));
- if (!flow_bb_inside_loop_p (loop, EDGE_SUCC (pbb, 0)->dest))
+ if (!flow_bb_inside_loop_p (loop, single_succ (pbb)))
insn = BB_HEAD (first[loop->num]);
}
else
flow_loops_free (&loops);
}
+/* 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.
+ e is an incoming edge. Returns the basic block containing the
+ condition.
+
+ --- edge e ---- > [second_head]
+
+ Split it and insert new conditional expression and adjust edges.
+
+ --- edge e ---> [cond expr] ---> [first_head]
+ |
+ +---------> [second_head]
+*/
+
+static basic_block
+lv_adjust_loop_entry_edge (basic_block first_head,
+ basic_block second_head,
+ edge e,
+ tree cond_expr)
+{
+ basic_block new_head = NULL;
+ edge e1;
+
+ gcc_assert (e->dest == second_head);
+
+ /* Split edge 'e'. This will create a new basic block, where we can
+ insert conditional expr. */
+ new_head = split_edge (e);
+
+
+ lv_add_condition_to_bb (first_head, second_head, new_head,
+ cond_expr);
+
+ e1 = make_edge (new_head, first_head, EDGE_TRUE_VALUE);
+ set_immediate_dominator (CDI_DOMINATORS, first_head, new_head);
+ set_immediate_dominator (CDI_DOMINATORS, second_head, new_head);
+
+ /* Adjust loop header phi nodes. */
+ lv_adjust_loop_header_phi (first_head, second_head, new_head, e1);
+
+ return new_head;
+}
+
+/* Main entry point for Loop Versioning transformation.
+
+This transformation given a condition and a loop, creates
+-if (condition) { loop_copy1 } else { loop_copy2 },
+where loop_copy1 is the loop transformed in one way, and loop_copy2
+is the loop transformed in another way (or unchanged). 'condition'
+may be a run time test for things that were not resolved by static
+analysis (overlapping ranges (anti-aliasing), alignment, etc.). */
+
+struct loop *
+loop_version (struct loops *loops, struct loop * loop,
+ void *cond_expr, basic_block *condition_bb)
+{
+ basic_block first_head, second_head;
+ edge entry, latch_edge, exit, true_edge, false_edge;
+ int irred_flag;
+ struct loop *nloop;
+
+ /* CHECKME: Loop versioning does not handle nested loop at this point. */
+ if (loop->inner)
+ return NULL;
+
+ /* Record entry and latch edges for the loop */
+ entry = loop_preheader_edge (loop);
+ irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
+ entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
+
+ /* Note down head of loop as first_head. */
+ first_head = entry->dest;
+
+ /* Duplicate loop. */
+ if (!cfg_hook_duplicate_loop_to_header_edge (loop, entry, loops, 1,
+ NULL, NULL, NULL, NULL, 0))
+ return NULL;
+
+ /* After duplication entry edge now points to new loop head block.
+ Note down new head as second_head. */
+ second_head = entry->dest;
+
+ /* Split loop entry edge and insert new block with cond expr. */
+ *condition_bb = lv_adjust_loop_entry_edge (first_head, second_head,
+ entry, cond_expr);
+ if (!*condition_bb)
+ {
+ entry->flags |= irred_flag;
+ return NULL;
+ }
+
+ latch_edge = single_succ_edge (loop->latch->rbi->copy);
+
+ extract_cond_bb_edges (*condition_bb, &true_edge, &false_edge);
+ nloop = loopify (loops,
+ latch_edge,
+ single_pred_edge (loop->header->rbi->copy),
+ *condition_bb, true_edge, false_edge,
+ false /* Do not redirect all edges. */);
+
+ exit = loop->single_exit;
+ if (exit)
+ nloop->single_exit = find_edge (exit->src->rbi->copy, exit->dest);
+
+ /* loopify redirected latch_edge. Update its PENDING_STMTS. */
+ lv_flush_pending_stmts (latch_edge);
+
+ /* loopify redirected condition_bb's succ edge. Update its PENDING_STMTS. */
+ extract_cond_bb_edges (*condition_bb, &true_edge, &false_edge);
+ lv_flush_pending_stmts (false_edge);
+ /* Adjust irreducible flag. */
+ if (irred_flag)
+ {
+ (*condition_bb)->flags |= BB_IRREDUCIBLE_LOOP;
+ loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP;
+ loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP;
+ single_pred_edge ((*condition_bb))->flags |= EDGE_IRREDUCIBLE_LOOP;
+ }
+
+ /* 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;
+}
+
/* The structure of LOOPS might have changed. Some loops might get removed
(and their headers and latches were set to NULL), loop exists might get
removed (thus the loop nesting may be wrong), and some blocks and edges
OSDN Git Service
