#include "config.h"
#include "system.h"
#include "tree.h"
#include "rtl.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "flags.h"
#include "output.h"
#include "cfglayout.h"
#include "target.h"
#include "langhooks.h"
static void make_reorder_chain PARAMS ((void));
static basic_block make_reorder_chain_1 PARAMS ((basic_block, basic_block));
static void find_rarely_executed_basic_blocks PARAMS ((void));
static void mark_bb_for_unlikely_executed_section PARAMS((basic_block));
static void fix_branches_for_unexecuted_code PARAMS ((void));
static void
make_reorder_chain ()
{
basic_block prev = NULL;
basic_block next, bb;
do
{
next = NULL;
FOR_EACH_BB (bb)
if (! RBI (bb)->visited)
{
next = bb;
break;
}
if (next)
prev = make_reorder_chain_1 (next, prev);
}
while (next);
RBI (prev)->next = NULL;
}
static basic_block
make_reorder_chain_1 (bb, prev)
basic_block bb;
basic_block prev;
{
edge e;
basic_block next;
rtx note;
if (prev)
{
restart:
RBI (prev)->next = bb;
if (rtl_dump_file && prev->next_bb != bb)
fprintf (rtl_dump_file, "Reordering block %d after %d\n",
bb->index, prev->index);
}
else
{
if (bb->prev_bb != ENTRY_BLOCK_PTR)
abort ();
}
RBI (bb)->visited = 1;
prev = bb;
if (bb->succ == NULL)
return prev;
next = NULL;
if (any_condjump_p (bb->end)
&& (note = find_reg_note (bb->end, REG_BR_PROB, 0)) != NULL)
{
int taken, probability;
edge e_taken, e_fall;
probability = INTVAL (XEXP (note, 0));
taken = probability > REG_BR_PROB_BASE / 2;
e_taken = e_fall = NULL;
for (e = bb->succ; e ; e = e->succ_next)
{
if (e->flags & EDGE_FALLTHRU)
e_fall = e;
else if (! (e->flags & EDGE_EH))
e_taken = e;
}
next = ((taken && e_taken) ? e_taken : e_fall)->dest;
}
if (! next)
{
for (e = bb->succ; e ; e = e->succ_next)
if (e->flags & EDGE_FALLTHRU)
{
next = e->dest;
break;
}
else if (e->dest == bb->next_bb)
{
if (! (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)))
next = e->dest;
}
}
if (! next || next == EXIT_BLOCK_PTR || RBI (next)->visited)
next = NULL;
for (e = bb->succ; e; e = e->succ_next)
if (e->dest != EXIT_BLOCK_PTR
&& ! RBI (e->dest)->visited
&& e->dest->succ
&& ! (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)))
{
if (next)
{
prev = make_reorder_chain_1 (next, prev);
next = RBI (e->dest)->visited ? NULL : e->dest;
}
else
next = e->dest;
}
if (next)
{
bb = next;
goto restart;
}
return prev;
}
static void
find_rarely_executed_basic_blocks ()
{
basic_block bb;
FOR_EACH_BB (bb)
if (probably_never_executed_bb_p (bb))
mark_bb_for_unlikely_executed_section (bb);
}
static void
mark_bb_for_unlikely_executed_section (bb)
basic_block bb;
{
rtx cur_insn;
rtx insert_insn = NULL;
rtx new_note;
for (cur_insn = bb->head; cur_insn != bb->end; cur_insn = NEXT_INSN (cur_insn))
{
if ((GET_CODE (cur_insn) != NOTE)
&& (GET_CODE (cur_insn) != CODE_LABEL))
{
insert_insn = cur_insn;
break;
}
}
if ((!insert_insn)
&& (GET_CODE (cur_insn) != NOTE)
&& (GET_CODE (cur_insn) != CODE_LABEL))
insert_insn = cur_insn;
if (insert_insn)
{
new_note = emit_note_before (NOTE_INSN_UNLIKELY_EXECUTED_CODE, insert_insn);
NOTE_BASIC_BLOCK (new_note) = bb;
}
}
static void
fix_branches_for_unexecuted_code ()
{
rtx cur_insn, old_jump, new_jump, jump_insn, old_label, new_label, label;
rtx new_note, new_note2, set_src, barrier;
edge cur_edge, crossing_edge, fall_thru, succ1, succ2, new_edge, e;
basic_block cur_bb, new_bb, dest, src;
int *bb_colors;
int *bb_has_label;
int *bb_has_jump;
edge *crossing_edges;
int i;
int n_crossing_edges;
int found;
int max_array_size;
bb_colors = xcalloc (2*last_basic_block, sizeof (int));
bb_has_label = xcalloc (2*last_basic_block, sizeof (int));
bb_has_jump = xcalloc (2*last_basic_block, sizeof (int));
crossing_edges = xcalloc (2*last_basic_block, sizeof (edge));
max_array_size = 2*last_basic_block;
found = 0;
FOR_EACH_BB (cur_bb)
{
for (cur_insn = cur_bb->head; cur_insn != cur_bb->end;
cur_insn = NEXT_INSN (cur_insn))
{
if ((GET_CODE (cur_insn) == NOTE)
&& (NOTE_LINE_NUMBER (cur_insn) == NOTE_INSN_UNLIKELY_EXECUTED_CODE))
{
bb_colors[cur_bb->index] = 1;
found++;
}
else if (GET_CODE (cur_insn) == CODE_LABEL)
bb_has_label[cur_bb->index] = 1;
else if (GET_CODE (cur_insn) == JUMP_INSN)
bb_has_jump[cur_bb->index] = 1;
}
if (cur_insn == cur_bb->end)
{
if ((GET_CODE (cur_insn) == NOTE)
&& (NOTE_LINE_NUMBER (cur_insn) == NOTE_INSN_UNLIKELY_EXECUTED_CODE))
{
bb_colors[cur_bb->index] = 1;
found++;
}
else if (GET_CODE (cur_insn) == CODE_LABEL)
bb_has_label[cur_bb->index] = 1;
else if (GET_CODE (cur_insn) == JUMP_INSN)
bb_has_jump[cur_bb->index] = 1;
}
}
i=0;
FOR_EACH_BB (cur_bb)
{
for (cur_edge = cur_bb->succ; cur_edge; cur_edge = cur_edge->succ_next)
{
if ((cur_edge->src) && (cur_edge->dest))
{
if (bb_colors[cur_edge->src->index] !=
bb_colors[cur_edge->dest->index])
{
crossing_edges[i] = cur_edge;
i++;
}
}
}
}
n_crossing_edges = i+1;
for (i=0; i < n_crossing_edges; i++)
{
if (crossing_edges[i])
{
src = crossing_edges[i]->src;
dest = crossing_edges[i]->dest;
if (dest && (dest->index != -2))
{
if (!(bb_has_label[dest->index]))
{
rtx new_label = gen_label_rtx ();
emit_label_before (new_label, dest->head);
dest->head = new_label;
bb_has_label[dest->index] = 1;
}
if (src && (src->index != -1))
{
if (!(bb_has_jump[src->index]))
{
if ((src->succ) && (src->succ->succ_next == NULL))
{
cur_insn = dest->head;
found = 0;
label = NULL;
while ((cur_insn != dest->end) && !found)
{
if (GET_CODE(cur_insn) == CODE_LABEL)
{
label= cur_insn;
found = 1;
}
else
cur_insn = NEXT_INSN (cur_insn);
}
if (cur_insn == dest->end)
if (GET_CODE(cur_insn) == CODE_LABEL)
{
label= cur_insn;
found = 1;
}
if (found)
{
new_jump = emit_jump_insn_after (gen_jump (label),
src->end);
barrier = emit_barrier_after (new_jump);
JUMP_LABEL (new_jump) = label;
LABEL_NUSES (label) += 1;
RBI (src)->footer = unlink_insn_chain (barrier,
barrier);
}
}
else
{
abort();
}
}
}
}
}
}
for (i = 0; i < n_crossing_edges; i++)
{
e = crossing_edges[i];
if (e && e->src)
{
src = e->src;
jump_insn = src->end;
if (GET_CODE(jump_insn) == JUMP_INSN)
{
if ((src->succ) && (src->succ->succ_next == NULL))
{
new_note = emit_note_before (NOTE_INSN_DONT_SHORTEN_BRANCH,
jump_insn);
NOTE_BASIC_BLOCK (new_note) = src;
}
}
}
}
FOR_EACH_BB (cur_bb)
{
fall_thru = NULL;
succ1 = cur_bb->succ;
if (succ1)
succ2 = succ1->succ_next;
else
succ2 = NULL;
if ((succ1)
&& (succ1->flags & EDGE_FALLTHRU))
fall_thru = succ1;
else if ((succ2)
&& (succ2->flags & EDGE_FALLTHRU))
fall_thru = succ2;
if (fall_thru)
{
if (scan_ahead_for_unlikely_executed_note (fall_thru->src->head) !=
scan_ahead_for_unlikely_executed_note (fall_thru->dest->head))
{
dest = fall_thru->dest;
if (dest->index > max_array_size)
abort ();
else if (!(bb_has_label[dest->index]))
{
new_label = gen_label_rtx();
emit_label_before (new_label, dest->head);
dest->head = new_label;
bb_has_label[dest->index] = 1;
}
else
{
found = 0;
new_label = NULL;
for (cur_insn = dest->head; (cur_insn != dest->end) && !found;
cur_insn = NEXT_INSN (cur_insn))
{
if (GET_CODE(cur_insn) == CODE_LABEL)
{
new_label = cur_insn;
found = 1;
}
}
if (cur_insn == dest->end)
if (GET_CODE(cur_insn) == CODE_LABEL)
new_label = cur_insn;
}
new_bb = create_basic_block (NULL, NULL, cur_bb);
alloc_aux_for_block (new_bb, sizeof (struct reorder_block_def));
RBI (new_bb)->next = RBI (cur_bb)->next;
RBI (cur_bb)->next = new_bb;
new_jump = emit_jump_insn_after (gen_jump (new_label),
new_bb->head);
barrier = emit_barrier_after (new_jump);
JUMP_LABEL (new_jump) = new_label;
LABEL_NUSES (new_label) += 1;
RBI (new_bb)->footer = unlink_insn_chain (barrier, barrier);
new_note = emit_note_before (NOTE_INSN_DONT_SHORTEN_BRANCH,
new_jump);
NOTE_BASIC_BLOCK (new_note) = new_bb;
if (new_bb->index < max_array_size)
bb_has_jump[new_bb->index] = 1;
if (scan_ahead_for_unlikely_executed_note (cur_bb->head))
{
new_note2 = emit_note_before (NOTE_INSN_UNLIKELY_EXECUTED_CODE,
new_note);
NOTE_BASIC_BLOCK (new_note2) = new_bb;
}
for (old_jump = cur_bb->head; old_jump != cur_bb->end;
old_jump = NEXT_INSN (old_jump))
if (GET_CODE (old_jump) == JUMP_INSN)
break;
if (GET_CODE (old_jump) == JUMP_INSN)
{
new_note = emit_note_before (NOTE_INSN_DONT_SHORTEN_BRANCH,
old_jump);
NOTE_BASIC_BLOCK (new_note) = cur_bb;
}
dest = fall_thru->dest;
redirect_edge_succ (fall_thru, new_bb);
new_edge = make_edge (new_bb, dest, 0);
}
}
}
FOR_EACH_BB (cur_bb)
{
crossing_edge = NULL;
succ1 = cur_bb->succ;
if (succ1)
succ2 = succ1->succ_next;
else
succ2 = NULL;
if ((succ1)
&& (scan_ahead_for_unlikely_executed_note (succ1->src->head) !=
scan_ahead_for_unlikely_executed_note (succ1->dest->head)))
crossing_edge = succ1;
else if ((succ2)
&& (scan_ahead_for_unlikely_executed_note (succ2->src->head) !=
scan_ahead_for_unlikely_executed_note (succ2->dest->head)))
crossing_edge = succ2;
if (crossing_edge)
{
if (cur_bb->index >= max_array_size)
abort ();
else if (bb_has_jump[cur_bb->index])
{
found = 0;
old_jump = NULL;
for (cur_insn = cur_bb->head; (cur_insn != cur_bb->end) && !found;
cur_insn = NEXT_INSN (cur_insn))
{
if (GET_CODE (cur_insn) == JUMP_INSN)
{
found = 1;
old_jump = cur_insn;
}
}
if (cur_insn == cur_bb->end)
if (GET_CODE (cur_insn) == JUMP_INSN)
old_jump = cur_insn;
if ((GET_CODE (old_jump) == JUMP_INSN) &&
(GET_CODE (PATTERN (old_jump)) == SET) &&
(GET_CODE (SET_SRC (PATTERN (old_jump))) == IF_THEN_ELSE))
{
set_src = SET_SRC (PATTERN (old_jump));
if (GET_CODE (XEXP (set_src, 1)) == PC)
old_label = XEXP (set_src, 2);
else if (GET_CODE (XEXP (set_src, 2)) == PC)
old_label = XEXP (set_src, 1);
new_note = emit_note_before (NOTE_INSN_DONT_SHORTEN_BRANCH,
old_jump);
NOTE_BASIC_BLOCK (new_note) = cur_bb;
new_bb = create_basic_block (NULL, NULL, cur_bb);
alloc_aux_for_block (new_bb, sizeof (struct reorder_block_def));
RBI (new_bb)->next = RBI (cur_bb)->next;
RBI (cur_bb)->next = new_bb;
new_label = gen_label_rtx ();
emit_label_before (new_label, new_bb->head);
new_bb->head = new_label;
if (new_bb->index < max_array_size)
bb_has_label[new_bb->index] = 1;
if (GET_CODE (old_label) == LABEL_REF)
{
old_label = JUMP_LABEL (old_jump);
new_jump = emit_jump_insn_after (gen_jump (old_label),
new_bb->end);
}
else if (GET_CODE (old_label) == RETURN)
new_jump = emit_jump_insn_after (gen_return (), new_bb->end);
else
abort ();
barrier = emit_barrier_after (new_jump);
JUMP_LABEL (new_jump) = old_label;
RBI (new_bb)->footer = unlink_insn_chain (barrier, barrier);
new_note = emit_note_before (NOTE_INSN_DONT_SHORTEN_BRANCH,
new_jump);
NOTE_BASIC_BLOCK (new_note) = new_bb;
if (new_bb->index < max_array_size)
bb_has_jump [new_bb->index] = 1;
if (scan_ahead_for_unlikely_executed_note (cur_bb->head))
{
new_note2 = emit_note_before (NOTE_INSN_UNLIKELY_EXECUTED_CODE,
new_note);
NOTE_BASIC_BLOCK (new_note2) = new_bb;
}
redirect_jump (old_jump, new_label, 0);
dest = crossing_edge->dest;
redirect_edge_succ (crossing_edge, new_bb);
new_edge = make_edge (new_bb, dest, 0);
}
}
}
}
free (bb_colors);
free (bb_has_label);
free (bb_has_jump);
free (crossing_edges);
}
void
reorder_basic_blocks (partition_flag)
int partition_flag;
{
if (n_basic_blocks <= 1)
return;
if ((* targetm.cannot_modify_jumps_p) ())
return;
cfg_layout_initialize ();
if ((partition_flag)
&& (!flag_exceptions)
&& (strcmp (lang_hooks.name, "GNU C++") != 0))
find_rarely_executed_basic_blocks();
make_reorder_chain ();
if (rtl_dump_file)
dump_flow_info (rtl_dump_file);
if ((partition_flag)
&& (!flag_exceptions)
&& (strcmp (lang_hooks.name, "GNU C++") != 0))
fix_branches_for_unexecuted_code ();
cfg_layout_finalize ();
}