#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
#include "hard-reg-set.h"
#include "obstack.h"
#include "basic-block.h"
#include "cfgloop.h"
#include "cfglayout.h"
#include "output.h"
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);
static void unloop (struct loops *, struct loop *);
#define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
edge
split_loop_bb (basic_block bb, void *insn)
{
edge e;
e = split_block (bb, insn);
add_bb_to_loop (e->dest, e->src->loop_father);
return e;
}
static bool
rpe_enum_p (basic_block bb, void *data)
{
return dominated_by_p (CDI_DOMINATORS, bb, data);
}
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]);
}
}
static int
find_path (edge e, basic_block **bbs)
{
gcc_assert (EDGE_COUNT (e->dest->preds) <= 1);
*bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
return dfs_enumerate_from (e->dest, 0, rpe_enum_p, *bbs,
n_basic_blocks, e->dest);
}
static bool
fix_bb_placement (struct loops *loops, basic_block bb)
{
edge e;
edge_iterator ei;
struct loop *loop = loops->tree_root, *act;
FOR_EACH_EDGE (e, ei, bb->succs)
{
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;
}
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;
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);
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)
{
edge_iterator ei;
from = *qbeg;
qbeg++;
if (qbeg == qtop)
qbeg = queue;
RESET_BIT (in_queue, from->index);
if (from->loop_father->header == from)
{
if (!fix_loop_placement (from->loop_father))
continue;
}
else
{
if (!fix_bb_placement (loops, from))
continue;
}
FOR_EACH_EDGE (e, ei, from->preds)
{
basic_block pred = e->src;
struct loop *nca;
if (TEST_BIT (in_queue, pred->index))
continue;
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))
{
continue;
}
if (TEST_BIT (in_queue, pred->index))
continue;
*qend = pred;
qend++;
if (qend == qtop)
qend = queue;
SET_BIT (in_queue, pred->index);
}
}
free (in_queue);
free (queue);
}
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)
{
edge_iterator ei;
bb = stack[--stack_top];
RESET_BIT (on_stack, bb->index);
FOR_EACH_EDGE (e, ei, bb->preds)
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 = EDGE_COUNT (bb->succs);
edges = xmalloc (n_edges * sizeof (edge));
FOR_EACH_EDGE (e, ei, bb->succs)
edges[ei.index] = 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);
}
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;
bool deleted;
if (!loop_delete_branch_edge (e, 0))
return false;
if (EDGE_COUNT (e->dest->preds) > 1)
e = EDGE_PRED (loop_split_edge_with (e, NULL_RTX), 0);
while (e->src->loop_father->outer
&& dominated_by_p (CDI_DOMINATORS,
e->src->loop_father->latch, e->dest))
unloop (loops, e->src->loop_father);
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);
for (i = 0; i < nrem; i++)
SET_BIT (seen, rem_bbs[i]->index);
for (i = 0; i < nrem; i++)
{
edge_iterator ei;
bb = rem_bbs[i];
FOR_EACH_EDGE (ae, ei, rem_bbs[i]->succs)
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;
}
}
from = e->src;
deleted = loop_delete_branch_edge (e, 1);
gcc_assert (deleted);
dom_bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
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);
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);
iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs);
free (dom_bbs);
for (i = 0; i < n_bord_bbs; i++)
fix_irreducible_loops (bord_bbs[i]);
free (bord_bbs);
fix_bb_placements (loops, from);
fix_loop_placements (loops, from->loop_father);
return true;
}
static bool
alp_enum_p (basic_block bb, void *alp_header)
{
return bb != (basic_block) alp_header;
}
static void
add_loop (struct loops *loops, struct loop *loop)
{
basic_block *bbs;
int i, n;
place_new_loop (loops, loop);
loop->level = 1;
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);
}
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;
}
}
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);
}
struct loop *
loopify (struct loops *loops, edge latch_edge, edge header_edge,
basic_block switch_bb, edge true_edge, edge false_edge,
bool redirect_all_edges)
{
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;
edge_iterator ei;
loop->header = header_edge->dest;
loop->latch = latch_edge->src;
freq = EDGE_FREQUENCY (header_edge);
cnt = header_edge->count;
prob = EDGE_SUCC (switch_bb, 0)->probability;
tot_prob = prob + EDGE_SUCC (switch_bb, 1)->probability;
if (tot_prob == 0)
tot_prob = 1;
loop_redirect_edge (latch_edge, loop->header);
loop_redirect_edge (true_edge, succ_bb);
if (redirect_all_edges)
{
loop_redirect_edge (header_edge, switch_bb);
loop_redirect_edge (false_edge, loop->header);
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);
add_loop (loops, loop);
flow_loop_tree_node_add (outer, loop);
add_bb_to_loop (switch_bb, outer);
switch_bb->frequency = freq;
switch_bb->count = cnt;
FOR_EACH_EDGE (e, ei, switch_bb->succs)
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);
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;
}
static 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;
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);
}
flow_loop_tree_node_remove (loop);
loops->parray[loop->num] = NULL;
flow_loop_free (loop);
remove_edge (EDGE_SUCC (latch, 0));
fix_bb_placements (loops, latch);
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);
}
int
fix_loop_placement (struct loop *loop)
{
basic_block *body;
unsigned i;
edge e;
edge_iterator ei;
struct loop *father = loop->pred[0], *act;
body = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
FOR_EACH_EDGE (e, ei, body[i]->succs)
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;
}
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;
fix_bb_placements (loops, loop_preheader_edge (loop)->src);
loop = outer;
}
}
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++;
}
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);
cloop->level = loop->level;
loop->copy = cloop;
flow_loop_tree_node_add (target, cloop);
return cloop;
}
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);
}
}
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);
}
}
static void
loop_redirect_edge (edge e, basic_block dest)
{
if (e->dest == dest)
return;
redirect_edge_and_branch_force (e, dest);
}
static bool
loop_delete_branch_edge (edge e, int really_delete)
{
basic_block src = e->src;
basic_block newdest;
int irr;
edge snd;
gcc_assert (EDGE_COUNT (src->succs) > 1);
if (EDGE_COUNT (src->succs) > 2)
return false;
if (!any_condjump_p (BB_END (src)))
return false;
snd = e == EDGE_SUCC (src, 0) ? EDGE_SUCC (src, 1) : EDGE_SUCC (src, 0);
newdest = snd->dest;
if (newdest == EXIT_BLOCK_PTR)
return false;
if (!really_delete)
return true;
irr = snd->flags & EDGE_IRREDUCIBLE_LOOP;
if (!redirect_edge_and_branch (e, newdest))
return false;
EDGE_SUCC (src, 0)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
EDGE_SUCC (src, 0)->flags |= irr;
return true;
}
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;
}
static void
update_single_exits_after_duplication (basic_block *bbs, unsigned nbbs,
struct loop *loop)
{
unsigned i;
for (i = 0; i < nbbs; i++)
bbs[i]->rbi->duplicated = 1;
for (; loop->outer; loop = loop->outer)
{
if (!loop->single_exit)
continue;
if (loop->single_exit->src->rbi->duplicated)
loop->single_exit = NULL;
}
for (i = 0; i < nbbs; i++)
bbs[i]->rbi->duplicated = 0;
}
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;
gcc_assert (e->dest == loop->header);
gcc_assert (ndupl > 0);
if (orig)
{
gcc_assert (flow_bb_inside_loop_p (loop, orig->src));
gcc_assert (!flow_bb_inside_loop_p (loop, orig->dest));
}
bbs = get_loop_body (loop);
if (!can_copy_bbs_p (bbs, loop->num_nodes))
{
free (bbs);
return false;
}
new_bbs = xmalloc (sizeof (basic_block) * loop->num_nodes);
add_irreducible_flag = e->flags & EDGE_IRREDUCIBLE_LOOP;
gcc_assert (!is_latch || !add_irreducible_flag);
latch_edge = loop_latch_edge (loop);
if (flags & DLTHE_FLAG_UPDATE_FREQ)
{
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++)
gcc_assert (scale_step[i] >= 0 && scale_step[i] <= REG_BR_PROB_BASE);
gcc_assert (scale_main >= 0 && scale_main <= REG_BR_PROB_BASE
&& scale_act >= 0 && scale_act <= REG_BR_PROB_BASE);
}
target = e->src->loop_father;
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;
}
if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS)
update_single_exits_after_duplication (bbs, n, target);
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_to (loops, orig_loops, n_orig_loops, target);
copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop);
for (i = 0; i < n; i++)
new_bbs[i]->rbi->copy_number = j + 1;
if (add_irreducible_flag)
{
for (i = 0; i < n; i++)
new_bbs[i]->rbi->duplicated = 1;
for (i = 0; i < n; i++)
{
edge_iterator ei;
new_bb = new_bbs[i];
if (new_bb->loop_father == target)
new_bb->flags |= BB_IRREDUCIBLE_LOOP;
FOR_EACH_EDGE (ae, ei, new_bb->succs)
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;
}
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];
}
if (orig && TEST_BIT (wont_exit, j + 1))
to_remove[(*n_to_remove)++] = new_spec_edges[SE_ORIG];
if (!first_active_latch)
{
memcpy (first_active, new_bbs, n * sizeof (basic_block));
first_active_latch = new_bbs[1];
}
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);
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);
}
for (i = 0; i < n; i++)
{
basic_block dominated, dom_bb, *dom_bbs;
int n_dom_bbs,j;
bb = bbs[i];
bb->rbi->copy_number = 0;
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;
}
static edge mfb_kj_edge;
static bool
mfb_keep_just (edge e)
{
return e != mfb_kj_edge;
}
static void
mfb_update_loops (basic_block jump)
{
struct loop *loop = EDGE_SUCC (jump, 0)->dest->loop_father;
if (dom_computed[CDI_DOMINATORS])
set_immediate_dominator (CDI_DOMINATORS, jump, EDGE_PRED (jump, 0)->src);
add_bb_to_loop (jump, loop);
loop->latch = jump;
}
static basic_block
create_preheader (struct loop *loop, int flags)
{
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)
continue;
irred |= (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
nentry++;
if (EDGE_COUNT (e->src->succs) == 1)
one_succ_pred = e;
}
gcc_assert (nentry);
if (nentry == 1)
{
e = EDGE_PRED (loop->header,
EDGE_PRED (loop->header, 0)->src == loop->latch);
if (!(flags & CP_SIMPLE_PREHEADERS) || EDGE_COUNT (e->src->succs) == 1)
return NULL;
}
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;
for (ploop = loop; ploop; ploop = ploop->outer)
if (ploop->latch == dummy)
ploop->latch = fallthru->dest;
if (latch_edge_was_fallthru)
{
if (one_succ_pred)
e = one_succ_pred;
else
e = EDGE_PRED (dummy, 0);
move_block_after (dummy, e->src);
}
loop->header->loop_father = loop;
add_bb_to_loop (dummy, cloop);
if (irred)
{
dummy->flags |= BB_IRREDUCIBLE_LOOP;
EDGE_SUCC (dummy, 0)->flags |= EDGE_IRREDUCIBLE_LOOP;
}
if (dump_file)
fprintf (dump_file, "Created preheader block for loop %i\n",
loop->num);
return dummy;
}
void
create_preheaders (struct loops *loops, int flags)
{
unsigned i;
for (i = 1; i < loops->num; i++)
create_preheader (loops->parray[i], flags);
loops->state |= LOOPS_HAVE_PREHEADERS;
}
void
force_single_succ_latches (struct loops *loops)
{
unsigned i;
struct loop *loop;
edge e;
for (i = 1; i < loops->num; i++)
{
loop = loops->parray[i];
if (loop->latch != loop->header && EDGE_COUNT (loop->latch->succs) == 1)
continue;
e = find_edge (loop->latch, loop->header);
loop_split_edge_with (e, NULL_RTX);
}
loops->state |= LOOPS_HAVE_SIMPLE_LATCHES;
}
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);
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;
}
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;
unsigned int i;
#ifdef ENABLE_CHECKING
for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
gcc_assert (!NOTE_P (insn) ||
NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
#endif
flow_loops_find (&loops, LOOP_TREE);
free_dominance_info (CDI_DOMINATORS);
if (loops.num > 1)
{
basic_block * shadow;
signed char * in_body;
shadow = xcalloc (loops.num, sizeof (basic_block));
in_body = xcalloc (loops.num, sizeof (signed char));
FOR_EACH_BB (bb)
{
loop = bb->loop_father;
if (loop->num == 0)
continue;
if (bb == loop->header && in_body[loop->num] == 0)
in_body[loop->num] = 1;
if (bb == loop->latch)
in_body[loop->num] = -1;
if (in_body[loop->num] == 1
&& shadow[loop->num] == 0
&& BB_END (bb)
&& JUMP_P (BB_END (bb))
&& onlyjump_p (BB_END (bb))
&& any_uncondjump_p (BB_END (bb)))
shadow[loop->num] = bb;
}
for (i = 1; i < loops.num; i++)
{
loop = loops.parray[i];
if (loop->header->loop_father != loop
|| loop->latch->loop_father != loop)
shadow[i] = 0;
}
memset (in_body, 0, sizeof(char) * loops.num);
FOR_EACH_BB (bb)
{
loop = bb->loop_father;
if (loop->num == 0 || shadow[loop->num] == 0)
continue;
if (bb == loop->header)
{
if (in_body[loop->num] == 0)
in_body[loop->num] = 1;
}
if (bb == loop->latch)
in_body[loop->num] = -1;
if (bb != loop->header && bb != loop->latch && in_body[loop->num] != 1)
{
rtx last_insn, table;
basic_block next_bb = bb->next_bb;
basic_block prev_bb = bb->prev_bb;
basic_block restart_bb = prev_bb;
edge e = find_edge (bb, next_bb);
edge e2 = find_edge (prev_bb, bb);
if (e && (e->flags & EDGE_FALLTHRU) && next_bb->loop_father != loop)
{
basic_block new_bb;
if (e->dest == EXIT_BLOCK_PTR)
{
new_bb = split_edge (e);
new_bb->loop_father = EXIT_BLOCK_PTR->loop_father;
new_bb->loop_depth = 0;
}
new_bb = force_nonfallthru (e);
if (new_bb)
{
new_bb->loop_father = loop;
new_bb->loop_depth = shadow[loop->num]->loop_depth;
}
}
if (e2 && (e2->flags & EDGE_FALLTHRU) && prev_bb->loop_father != loop)
{
basic_block new_bb = force_nonfallthru (e2);
if (new_bb)
{
new_bb->loop_father = prev_bb->loop_father;
new_bb->loop_depth = prev_bb->loop_depth;
restart_bb = new_bb;
}
}
last_insn = BB_END (bb);
if (tablejump_p (last_insn, NULL, &table))
last_insn = table;
if (BARRIER_P (NEXT_INSN (last_insn)))
last_insn = NEXT_INSN (last_insn);
reorder_insns_nobb(BB_HEAD (bb), last_insn,
PREV_INSN (BB_HEAD (shadow[loop->num]->next_bb)));
unlink_block (bb);
link_block (bb, shadow[loop->num]);
shadow[loop->num] = bb;
bb = restart_bb;
}
}
free (in_body);
free (shadow);
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])
{
while (*--top != loop)
last[(*top)->num] = EXIT_BLOCK_PTR;
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);
gcc_assert (pbb && EDGE_COUNT (pbb->succs) == 1);
if (!flow_bb_inside_loop_p (loop, EDGE_SUCC (pbb, 0)->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;
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);
}