#include "config.h"
#include "system.h"
#include "tree.h"
#include "rtl.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "insn-config.h"
#include "output.h"
#include "function.h"
#include "obstack.h"
#include "cfglayout.h"
extern struct obstack flow_obstack;
static rtx function_footer;
static rtx skip_insns_after_block PARAMS ((basic_block));
static void record_effective_endpoints PARAMS ((void));
static rtx label_for_bb PARAMS ((basic_block));
static void fixup_reorder_chain PARAMS ((void));
static void set_block_levels PARAMS ((tree, int));
static void change_scope PARAMS ((rtx, tree, tree));
void verify_insn_chain PARAMS ((void));
static void cleanup_unconditional_jumps PARAMS ((void));
static void fixup_fallthru_exit_predecessor PARAMS ((void));
rtx unlink_insn_chain PARAMS ((rtx, rtx));
static void update_unlikely_executed_notes PARAMS ((basic_block));
extern bool has_dont_shorten_branch PARAMS ((basic_block));
static rtx duplicate_insn_chain PARAMS ((rtx, rtx));
rtx
unlink_insn_chain (first, last)
rtx first;
rtx last;
{
rtx prevfirst = PREV_INSN (first);
rtx nextlast = NEXT_INSN (last);
PREV_INSN (first) = NULL;
NEXT_INSN (last) = NULL;
if (prevfirst)
NEXT_INSN (prevfirst) = nextlast;
if (nextlast)
PREV_INSN (nextlast) = prevfirst;
else
set_last_insn (prevfirst);
if (!prevfirst)
set_first_insn (nextlast);
return first;
}
static rtx
skip_insns_after_block (bb)
basic_block bb;
{
rtx insn, last_insn, next_head, prev;
next_head = NULL_RTX;
if (bb->next_bb != EXIT_BLOCK_PTR)
next_head = bb->next_bb->head;
for (last_insn = insn = bb->end; (insn = NEXT_INSN (insn)) != 0; )
{
if (insn == next_head)
break;
switch (GET_CODE (insn))
{
case BARRIER:
last_insn = insn;
continue;
case NOTE:
switch (NOTE_LINE_NUMBER (insn))
{
case NOTE_INSN_LOOP_END:
case NOTE_INSN_BLOCK_END:
last_insn = insn;
continue;
case NOTE_INSN_DELETED:
case NOTE_INSN_DELETED_LABEL:
continue;
default:
continue;
break;
}
break;
case CODE_LABEL:
if (NEXT_INSN (insn)
&& GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
&& (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
|| GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
{
insn = NEXT_INSN (insn);
last_insn = insn;
continue;
}
break;
default:
break;
}
break;
}
for (insn = last_insn; insn != bb->end; insn = prev)
{
prev = PREV_INSN (insn);
if (GET_CODE (insn) == NOTE)
switch (NOTE_LINE_NUMBER (insn))
{
case NOTE_INSN_LOOP_END:
case NOTE_INSN_BLOCK_END:
case NOTE_INSN_DELETED:
case NOTE_INSN_DELETED_LABEL:
continue;
default:
reorder_insns (insn, insn, last_insn);
}
}
return last_insn;
}
static rtx
label_for_bb (bb)
basic_block bb;
{
rtx label = bb->head;
if (GET_CODE (label) != CODE_LABEL)
{
if (rtl_dump_file)
fprintf (rtl_dump_file, "Emitting label for block %d\n", bb->index);
label = block_label (bb);
}
return label;
}
static void
record_effective_endpoints ()
{
rtx next_insn = get_insns ();
basic_block bb;
FOR_EACH_BB (bb)
{
rtx end;
if (PREV_INSN (bb->head) && next_insn != bb->head)
RBI (bb)->header = unlink_insn_chain (next_insn,
PREV_INSN (bb->head));
end = skip_insns_after_block (bb);
if (NEXT_INSN (bb->end) && bb->end != end)
RBI (bb)->footer = unlink_insn_chain (NEXT_INSN (bb->end), end);
next_insn = NEXT_INSN (bb->end);
}
function_footer = next_insn;
if (function_footer)
function_footer = unlink_insn_chain (function_footer, get_last_insn ());
}
void
scope_to_insns_initialize ()
{
tree block = NULL;
rtx insn, next;
for (insn = get_insns (); insn; insn = next)
{
next = NEXT_INSN (insn);
if (active_insn_p (insn)
&& GET_CODE (PATTERN (insn)) != ADDR_VEC
&& GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC)
INSN_SCOPE (insn) = block;
else if (GET_CODE (insn) == NOTE)
{
switch (NOTE_LINE_NUMBER (insn))
{
case NOTE_INSN_BLOCK_BEG:
block = NOTE_BLOCK (insn);
delete_insn (insn);
break;
case NOTE_INSN_BLOCK_END:
block = BLOCK_SUPERCONTEXT (block);
delete_insn (insn);
break;
default:
break;
}
}
}
set_block_levels (DECL_INITIAL (cfun->decl), 0);
}
static void
set_block_levels (block, level)
tree block;
int level;
{
while (block)
{
BLOCK_NUMBER (block) = level;
set_block_levels (BLOCK_SUBBLOCKS (block), level + 1);
block = BLOCK_CHAIN (block);
}
}
tree
choose_inner_scope (s1, s2)
tree s1, s2;
{
if (!s1)
return s2;
if (!s2)
return s1;
if (BLOCK_NUMBER (s1) > BLOCK_NUMBER (s2))
return s1;
return s2;
}
static void
change_scope (orig_insn, s1, s2)
rtx orig_insn;
tree s1, s2;
{
rtx insn = orig_insn;
tree com = NULL_TREE;
tree ts1 = s1, ts2 = s2;
tree s;
while (ts1 != ts2)
{
if (ts1 == NULL || ts2 == NULL)
abort ();
if (BLOCK_NUMBER (ts1) > BLOCK_NUMBER (ts2))
ts1 = BLOCK_SUPERCONTEXT (ts1);
else if (BLOCK_NUMBER (ts1) < BLOCK_NUMBER (ts2))
ts2 = BLOCK_SUPERCONTEXT (ts2);
else
{
ts1 = BLOCK_SUPERCONTEXT (ts1);
ts2 = BLOCK_SUPERCONTEXT (ts2);
}
}
com = ts1;
s = s1;
while (s != com)
{
rtx note = emit_note_before (NOTE_INSN_BLOCK_END, insn);
NOTE_BLOCK (note) = s;
s = BLOCK_SUPERCONTEXT (s);
}
s = s2;
while (s != com)
{
insn = emit_note_before (NOTE_INSN_BLOCK_BEG, insn);
NOTE_BLOCK (insn) = s;
s = BLOCK_SUPERCONTEXT (s);
}
}
void
scope_to_insns_finalize ()
{
tree cur_block = DECL_INITIAL (cfun->decl);
rtx insn, note;
insn = get_insns ();
if (!active_insn_p (insn))
insn = next_active_insn (insn);
for (; insn; insn = next_active_insn (insn))
{
tree this_block;
this_block = INSN_SCOPE (insn);
if (GET_CODE (PATTERN (insn)) == SEQUENCE)
{
int i;
rtx body = PATTERN (insn);
this_block = NULL;
for (i = 0; i < XVECLEN (body, 0); i++)
this_block = choose_inner_scope (this_block,
INSN_SCOPE (XVECEXP (body, 0, i)));
}
if (! this_block)
continue;
if (this_block != cur_block)
{
change_scope (insn, cur_block, this_block);
cur_block = this_block;
}
}
note = emit_note (NULL, NOTE_INSN_DELETED);
change_scope (note, cur_block, DECL_INITIAL (cfun->decl));
delete_insn (note);
reorder_blocks ();
}
static void
fixup_reorder_chain ()
{
basic_block bb, prev_bb;
int index;
rtx insn = NULL;
for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0;
bb != 0;
bb = RBI (bb)->next, index++)
{
if (RBI (bb)->header)
{
if (insn)
NEXT_INSN (insn) = RBI (bb)->header;
else
set_first_insn (RBI (bb)->header);
PREV_INSN (RBI (bb)->header) = insn;
insn = RBI (bb)->header;
while (NEXT_INSN (insn))
insn = NEXT_INSN (insn);
}
if (insn)
NEXT_INSN (insn) = bb->head;
else
set_first_insn (bb->head);
PREV_INSN (bb->head) = insn;
insn = bb->end;
if (RBI (bb)->footer)
{
NEXT_INSN (insn) = RBI (bb)->footer;
PREV_INSN (RBI (bb)->footer) = insn;
while (NEXT_INSN (insn))
insn = NEXT_INSN (insn);
}
}
if (index != n_basic_blocks)
abort ();
NEXT_INSN (insn) = function_footer;
if (function_footer)
PREV_INSN (function_footer) = insn;
while (NEXT_INSN (insn))
insn = NEXT_INSN (insn);
set_last_insn (insn);
#ifdef ENABLE_CHECKING
verify_insn_chain ();
#endif
for (bb = ENTRY_BLOCK_PTR->next_bb; bb ; bb = RBI (bb)->next)
{
edge e_fall, e_taken, e;
rtx bb_end_insn;
basic_block nb;
basic_block old_bb;
if (bb->succ == NULL)
continue;
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;
bb_end_insn = bb->end;
if (GET_CODE (bb_end_insn) == JUMP_INSN)
{
if (any_condjump_p (bb_end_insn))
{
if (RBI (bb)->next == e_fall->dest
|| (!RBI (bb)->next
&& e_fall->dest == EXIT_BLOCK_PTR))
continue;
if (RBI (bb)->next != e_taken->dest)
{
rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0);
if (note
&& INTVAL (XEXP (note, 0)) < REG_BR_PROB_BASE / 2
&& invert_jump (bb_end_insn,
label_for_bb (e_fall->dest), 0))
{
e_fall->flags &= ~EDGE_FALLTHRU;
e_taken->flags |= EDGE_FALLTHRU;
update_br_prob_note (bb);
e = e_fall, e_fall = e_taken, e_taken = e;
}
}
else if (invert_jump (bb_end_insn,
label_for_bb (e_fall->dest), 0))
{
e_fall->flags &= ~EDGE_FALLTHRU;
e_taken->flags |= EDGE_FALLTHRU;
update_br_prob_note (bb);
continue;
}
}
else if (returnjump_p (bb_end_insn))
continue;
else
{
if (! e_fall)
continue;
if (RBI (bb)->next == e_fall->dest)
continue;
#ifdef CASE_DROPS_THROUGH
bb_end_insn = skip_insns_after_block (bb);
#else
abort ();
#endif
}
}
else
{
if (! e_fall)
continue;
if (RBI (bb)->next == e_fall->dest)
continue;
if (!RBI (bb)->next && e_fall->dest == EXIT_BLOCK_PTR)
continue;
}
nb = force_nonfallthru (e_fall);
if (nb)
{
alloc_aux_for_block (nb, sizeof (struct reorder_block_def));
RBI (nb)->visited = 1;
RBI (nb)->next = RBI (bb)->next;
RBI (bb)->next = nb;
old_bb = bb;
bb = nb;
if (has_dont_shorten_note (old_bb))
{
rtx new_note;
rtx new_jump, cur_insn;
new_jump = NULL;
for (cur_insn = nb->head; cur_insn!= nb->end;
cur_insn = NEXT_INSN (cur_insn))
if (GET_CODE (cur_insn) == JUMP_INSN)
{
new_jump = cur_insn;
break;
}
if ((!new_jump) && (GET_CODE (cur_insn) == JUMP_INSN))
new_jump = cur_insn;
if (new_jump)
{
new_note = emit_note_before (NOTE_INSN_DONT_SHORTEN_BRANCH,
new_jump);
NOTE_BASIC_BLOCK (new_note) = nb;
}
else
abort ();
}
{
if (scan_ahead_for_unlikely_executed_note (bb->pred->src->head))
{
rtx new_note;
rtx note = e_fall->src->head;
while ((!(INSN_P (note)))
&& (note != e_fall->src->end))
note = NEXT_INSN (note);
new_note = emit_note_before (NOTE_INSN_UNLIKELY_EXECUTED_CODE,
note);
NOTE_BASIC_BLOCK (new_note) = bb;
}
}
}
}
if (rtl_dump_file)
{
fprintf (rtl_dump_file, "Reordered sequence:\n");
for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0; bb; bb = RBI (bb)->next, index ++)
{
fprintf (rtl_dump_file, " %i ", index);
if (RBI (bb)->original)
fprintf (rtl_dump_file, "duplicate of %i ",
RBI (bb)->original->index);
else if (forwarder_block_p (bb) && GET_CODE (bb->head) != CODE_LABEL)
fprintf (rtl_dump_file, "compensation ");
else
fprintf (rtl_dump_file, "bb %i ", bb->index);
fprintf (rtl_dump_file, " [%i]\n", bb->frequency);
}
}
prev_bb = ENTRY_BLOCK_PTR;
bb = ENTRY_BLOCK_PTR->next_bb;
index = 0;
for (; bb; prev_bb = bb, bb = RBI (bb)->next, index ++)
{
bb->index = index;
BASIC_BLOCK (index) = bb;
update_unlikely_executed_notes (bb);
bb->prev_bb = prev_bb;
prev_bb->next_bb = bb;
}
prev_bb->next_bb = EXIT_BLOCK_PTR;
EXIT_BLOCK_PTR->prev_bb = prev_bb;
}
static void
update_unlikely_executed_notes (bb)
basic_block bb;
{
rtx cur_insn;
for (cur_insn = bb->head; cur_insn != bb->end; cur_insn = NEXT_INSN (cur_insn))
{
if (GET_CODE (cur_insn) == NOTE)
{
if ((NOTE_LINE_NUMBER (cur_insn) == NOTE_INSN_UNLIKELY_EXECUTED_CODE)
|| (NOTE_LINE_NUMBER (cur_insn) == NOTE_INSN_DONT_SHORTEN_BRANCH))
NOTE_BASIC_BLOCK (cur_insn) = bb;
}
}
}
void
verify_insn_chain ()
{
rtx x, prevx, nextx;
int insn_cnt1, insn_cnt2;
for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
x != 0;
prevx = x, insn_cnt1++, x = NEXT_INSN (x))
if (PREV_INSN (x) != prevx)
abort ();
if (prevx != get_last_insn ())
abort ();
for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
x != 0;
nextx = x, insn_cnt2++, x = PREV_INSN (x))
if (NEXT_INSN (x) != nextx)
abort ();
if (insn_cnt1 != insn_cnt2)
abort ();
}
static void
cleanup_unconditional_jumps ()
{
basic_block bb;
FOR_EACH_BB (bb)
{
if (!bb->succ)
continue;
if (bb->succ->flags & EDGE_FALLTHRU)
continue;
if (!bb->succ->succ_next)
{
rtx insn;
if (GET_CODE (bb->head) != CODE_LABEL && forwarder_block_p (bb)
&& bb->prev_bb != ENTRY_BLOCK_PTR)
{
basic_block prev = bb->prev_bb;
if (rtl_dump_file)
fprintf (rtl_dump_file, "Removing forwarder BB %i\n",
bb->index);
redirect_edge_succ_nodup (bb->pred, bb->succ->dest);
flow_delete_block (bb);
bb = prev;
}
else if (simplejump_p (bb->end))
{
rtx jump = bb->end;
if (rtl_dump_file)
fprintf (rtl_dump_file, "Removing jump %i in BB %i\n",
INSN_UID (jump), bb->index);
delete_insn (jump);
bb->succ->flags |= EDGE_FALLTHRU;
}
else
continue;
insn = NEXT_INSN (bb->end);
while (insn
&& (GET_CODE (insn) != NOTE
|| NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK))
{
rtx next = NEXT_INSN (insn);
if (GET_CODE (insn) == BARRIER)
delete_barrier (insn);
insn = next;
}
}
}
}
static void
fixup_fallthru_exit_predecessor ()
{
edge e;
basic_block bb = NULL;
for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
if (e->flags & EDGE_FALLTHRU)
bb = e->src;
if (bb && RBI (bb)->next)
{
basic_block c = ENTRY_BLOCK_PTR->next_bb;
while (RBI (c)->next != bb)
c = RBI (c)->next;
RBI (c)->next = RBI (bb)->next;
while (RBI (c)->next)
c = RBI (c)->next;
RBI (c)->next = bb;
RBI (bb)->next = NULL;
}
}
bool
cfg_layout_can_duplicate_bb_p (bb)
basic_block bb;
{
rtx next;
edge s;
if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR)
return false;
for (s = bb->succ; s; s = s->succ_next)
if (s->dest == EXIT_BLOCK_PTR && s->flags & EDGE_FALLTHRU)
return false;
if (GET_CODE (bb->end) == JUMP_INSN && JUMP_LABEL (bb->end)
&& (next = next_nonnote_insn (JUMP_LABEL (bb->end)))
&& GET_CODE (next) == JUMP_INSN
&& (GET_CODE (PATTERN (next)) == ADDR_VEC
|| GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
return false;
return true;
}
static rtx
duplicate_insn_chain (from, to)
rtx from, to;
{
rtx insn, last;
last = emit_note (NULL, NOTE_INSN_DELETED);
for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
{
rtx new;
switch (GET_CODE (insn))
{
case INSN:
case CALL_INSN:
case JUMP_INSN:
if (GET_CODE (PATTERN (insn)) == ADDR_VEC
|| GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
break;
new = emit_copy_of_insn_after (insn, get_last_insn ());
break;
case CODE_LABEL:
break;
case BARRIER:
emit_barrier ();
break;
case NOTE:
switch (NOTE_LINE_NUMBER (insn))
{
case NOTE_INSN_PROLOGUE_END:
case NOTE_INSN_LOOP_VTOP:
case NOTE_INSN_LOOP_CONT:
case NOTE_INSN_LOOP_BEG:
case NOTE_INSN_LOOP_END:
case NOTE_INSN_DELETED:
case NOTE_INSN_DELETED_LABEL:
case NOTE_INSN_EPILOGUE_BEG:
case NOTE_INSN_FUNCTION_END:
case NOTE_INSN_FUNCTION_BEG:
case NOTE_INSN_BASIC_BLOCK:
break;
case NOTE_INSN_BLOCK_BEG:
case NOTE_INSN_BLOCK_END:
case NOTE_INSN_EH_REGION_BEG:
case NOTE_INSN_EH_REGION_END:
abort ();
break;
case NOTE_INSN_REPEATED_LINE_NUMBER:
emit_note (NOTE_SOURCE_FILE (insn), NOTE_LINE_NUMBER (insn));
break;
default:
if (NOTE_LINE_NUMBER (insn) < 0)
abort ();
emit_note (NOTE_SOURCE_FILE (insn), NOTE_LINE_NUMBER (insn));
}
break;
default:
abort ();
}
}
insn = NEXT_INSN (last);
delete_insn (last);
return insn;
}
void
cfg_layout_redirect_edge (e, dest)
edge e;
basic_block dest;
{
basic_block src = e->src;
basic_block old_next_bb = src->next_bb;
src->next_bb = NULL;
if (e->flags & EDGE_FALLTHRU)
{
if (src->succ->succ_next
&& !src->succ->succ_next->succ_next)
{
edge s = e->succ_next ? e->succ_next : src->succ;
if (s->dest == dest
&& any_condjump_p (src->end)
&& onlyjump_p (src->end))
delete_insn (src->end);
}
redirect_edge_succ_nodup (e, dest);
}
else
redirect_edge_and_branch (e, dest);
if (simplejump_p (src->end))
{
delete_insn (src->end);
delete_barrier (NEXT_INSN (src->end));
src->succ->flags |= EDGE_FALLTHRU;
}
src->next_bb = old_next_bb;
}
basic_block
cfg_layout_duplicate_bb (bb, e)
basic_block bb;
edge e;
{
rtx insn;
edge s, n;
basic_block new_bb;
gcov_type new_count = e ? e->count : 0;
if (bb->count < new_count)
new_count = bb->count;
if (!bb->pred)
abort ();
#ifdef ENABLE_CHECKING
if (!cfg_layout_can_duplicate_bb_p (bb))
abort ();
#endif
insn = duplicate_insn_chain (bb->head, bb->end);
new_bb = create_basic_block (insn,
insn ? get_last_insn () : NULL,
EXIT_BLOCK_PTR->prev_bb);
alloc_aux_for_block (new_bb, sizeof (struct reorder_block_def));
if (RBI (bb)->header)
{
insn = RBI (bb)->header;
while (NEXT_INSN (insn))
insn = NEXT_INSN (insn);
insn = duplicate_insn_chain (RBI (bb)->header, insn);
if (insn)
RBI (new_bb)->header = unlink_insn_chain (insn, get_last_insn ());
}
if (RBI (bb)->footer)
{
insn = RBI (bb)->footer;
while (NEXT_INSN (insn))
insn = NEXT_INSN (insn);
insn = duplicate_insn_chain (RBI (bb)->footer, insn);
if (insn)
RBI (new_bb)->footer = unlink_insn_chain (insn, get_last_insn ());
}
if (bb->global_live_at_start)
{
new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_start);
COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end);
}
new_bb->loop_depth = bb->loop_depth;
new_bb->flags = bb->flags;
for (s = bb->succ; s; s = s->succ_next)
{
n = make_edge (new_bb, s->dest, s->flags);
n->probability = s->probability;
if (new_count)
n->count = s->count * (new_count * 10000 / bb->count) / 10000;
else
n->count = 0;
s->count -= n->count;
}
new_bb->count = new_count;
bb->count -= new_count;
if (e)
{
new_bb->frequency = EDGE_FREQUENCY (e);
bb->frequency -= EDGE_FREQUENCY (e);
cfg_layout_redirect_edge (e, new_bb);
}
if (bb->count < 0)
bb->count = 0;
if (bb->frequency < 0)
bb->frequency = 0;
RBI (new_bb)->original = bb;
return new_bb;
}
void
cfg_layout_initialize ()
{
alloc_aux_for_blocks (sizeof (struct reorder_block_def));
cleanup_unconditional_jumps ();
record_effective_endpoints ();
}
void
cfg_layout_finalize ()
{
fixup_fallthru_exit_predecessor ();
fixup_reorder_chain ();
#ifdef ENABLE_CHECKING
verify_insn_chain ();
#endif
free_aux_for_blocks ();
#ifdef ENABLE_CHECKING
verify_flow_info ();
#endif
}