#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "rtl.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "regs.h"
#include "flags.h"
#include "output.h"
#include "function.h"
#include "except.h"
#include "toplev.h"
#include "tm_p.h"
#include "obstack.h"
#include "insn-config.h"
#include "cfglayout.h"
#include "expr.h"
#include "target.h"
rtx label_value_list;
static int can_delete_note_p (rtx);
static int can_delete_label_p (rtx);
static void commit_one_edge_insertion (edge, int);
static rtx last_loop_beg_note (rtx);
static bool back_edge_of_syntactic_loop_p (basic_block, basic_block);
static basic_block rtl_split_edge (edge);
static bool rtl_move_block_after (basic_block, basic_block);
static int rtl_verify_flow_info (void);
static basic_block cfg_layout_split_block (basic_block, void *);
static edge cfg_layout_redirect_edge_and_branch (edge, basic_block);
static basic_block cfg_layout_redirect_edge_and_branch_force (edge, basic_block);
static void cfg_layout_delete_block (basic_block);
static void rtl_delete_block (basic_block);
static basic_block rtl_redirect_edge_and_branch_force (edge, basic_block);
static edge rtl_redirect_edge_and_branch (edge, basic_block);
static basic_block rtl_split_block (basic_block, void *);
static void rtl_dump_bb (basic_block, FILE *, int);
static int rtl_verify_flow_info_1 (void);
static void mark_killed_regs (rtx, rtx, void *);
static void rtl_make_forwarder_block (edge);
static int
can_delete_note_p (rtx note)
{
return (NOTE_LINE_NUMBER (note) == NOTE_INSN_DELETED
|| NOTE_LINE_NUMBER (note) == NOTE_INSN_BASIC_BLOCK
|| NOTE_LINE_NUMBER (note) == NOTE_INSN_UNLIKELY_EXECUTED_CODE);
}
static int
can_delete_label_p (rtx label)
{
return (!LABEL_PRESERVE_P (label)
&& LABEL_NAME (label) == 0
&& !in_expr_list_p (forced_labels, label)
&& !in_expr_list_p (label_value_list, label));
}
rtx
delete_insn (rtx insn)
{
rtx next = NEXT_INSN (insn);
rtx note;
bool really_delete = true;
if (LABEL_P (insn))
{
if (! can_delete_label_p (insn))
{
const char *name = LABEL_NAME (insn);
really_delete = false;
PUT_CODE (insn, NOTE);
NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED_LABEL;
NOTE_DELETED_LABEL_NAME (insn) = name;
}
remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels);
}
if (really_delete)
{
gcc_assert (!INSN_DELETED_P (insn));
remove_insn (insn);
INSN_DELETED_P (insn) = 1;
}
if (JUMP_P (insn)
&& JUMP_LABEL (insn)
&& LABEL_P (JUMP_LABEL (insn)))
LABEL_NUSES (JUMP_LABEL (insn))--;
else
{
while ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)) != NULL_RTX
&& LABEL_P (XEXP (note, 0)))
{
LABEL_NUSES (XEXP (note, 0))--;
remove_note (insn, note);
}
}
if (JUMP_P (insn)
&& (GET_CODE (PATTERN (insn)) == ADDR_VEC
|| GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
{
rtx pat = PATTERN (insn);
int diff_vec_p = GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC;
int len = XVECLEN (pat, diff_vec_p);
int i;
for (i = 0; i < len; i++)
{
rtx label = XEXP (XVECEXP (pat, diff_vec_p, i), 0);
if (!NOTE_P (label))
LABEL_NUSES (label)--;
}
}
return next;
}
rtx
delete_insn_and_edges (rtx insn)
{
rtx x;
bool purge = false;
if (INSN_P (insn)
&& BLOCK_FOR_INSN (insn)
&& BB_END (BLOCK_FOR_INSN (insn)) == insn)
purge = true;
x = delete_insn (insn);
if (purge)
purge_dead_edges (BLOCK_FOR_INSN (insn));
return x;
}
void
delete_insn_chain (rtx start, rtx finish)
{
rtx next;
while (1)
{
next = NEXT_INSN (start);
if (NOTE_P (start) && !can_delete_note_p (start))
;
else
next = delete_insn (start);
if (start == finish)
break;
start = next;
}
}
void
delete_insn_chain_and_edges (rtx first, rtx last)
{
bool purge = false;
if (INSN_P (last)
&& BLOCK_FOR_INSN (last)
&& BB_END (BLOCK_FOR_INSN (last)) == last)
purge = true;
delete_insn_chain (first, last);
if (purge)
purge_dead_edges (BLOCK_FOR_INSN (last));
}
basic_block
create_basic_block_structure (rtx head, rtx end, rtx bb_note, basic_block after)
{
basic_block bb;
if (bb_note
&& (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
&& bb->aux == NULL)
{
rtx after;
if (LABEL_P (head))
after = head;
else
{
after = PREV_INSN (head);
head = bb_note;
}
if (after != bb_note && NEXT_INSN (after) != bb_note)
reorder_insns_nobb (bb_note, bb_note, after);
}
else
{
bb = alloc_block ();
if (!head && !end)
head = end = bb_note
= emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
else if (LABEL_P (head) && end)
{
bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
if (head == end)
end = bb_note;
}
else
{
bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
head = bb_note;
if (!end)
end = head;
}
NOTE_BASIC_BLOCK (bb_note) = bb;
}
if (NEXT_INSN (end) == bb_note)
end = bb_note;
BB_HEAD (bb) = head;
BB_END (bb) = end;
bb->index = last_basic_block++;
bb->flags = BB_NEW;
link_block (bb, after);
BASIC_BLOCK (bb->index) = bb;
update_bb_for_insn (bb);
BB_SET_PARTITION (bb, BB_UNPARTITIONED);
bb->aux = bb;
return bb;
}
static basic_block
rtl_create_basic_block (void *headp, void *endp, basic_block after)
{
rtx head = headp, end = endp;
basic_block bb;
if ((size_t) last_basic_block >= VARRAY_SIZE (basic_block_info))
{
size_t new_size = last_basic_block + (last_basic_block + 3) / 4;
VARRAY_GROW (basic_block_info, new_size);
}
n_basic_blocks++;
bb = create_basic_block_structure (head, end, NULL, after);
bb->aux = NULL;
return bb;
}
static basic_block
cfg_layout_create_basic_block (void *head, void *end, basic_block after)
{
basic_block newbb = rtl_create_basic_block (head, end, after);
initialize_bb_rbi (newbb);
return newbb;
}
static void
rtl_delete_block (basic_block b)
{
rtx insn, end, tmp;
insn = BB_HEAD (b);
if (LABEL_P (insn))
maybe_remove_eh_handler (insn);
end = BB_END (b);
if (tablejump_p (end, NULL, &tmp))
end = tmp;
tmp = next_nonnote_insn (end);
while (tmp && BARRIER_P (tmp))
{
end = tmp;
tmp = next_nonnote_insn (end);
}
BB_HEAD (b) = NULL;
delete_insn_chain (insn, end);
}
void
compute_bb_for_insn (void)
{
basic_block bb;
FOR_EACH_BB (bb)
{
rtx end = BB_END (bb);
rtx insn;
for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
{
BLOCK_FOR_INSN (insn) = bb;
if (insn == end)
break;
}
}
}
void
free_bb_for_insn (void)
{
rtx insn;
for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
if (!BARRIER_P (insn))
BLOCK_FOR_INSN (insn) = NULL;
}
rtx
entry_of_function (void)
{
return (n_basic_blocks ? BB_HEAD (ENTRY_BLOCK_PTR->next_bb) : get_insns ());
}
void
update_bb_for_insn (basic_block bb)
{
rtx insn;
for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
{
if (!BARRIER_P (insn))
set_block_for_insn (insn, bb);
if (insn == BB_END (bb))
break;
}
}
static basic_block
rtl_split_block (basic_block bb, void *insnp)
{
basic_block new_bb;
rtx insn = insnp;
edge e;
edge_iterator ei;
if (!insn)
{
insn = first_insn_after_basic_block_note (bb);
if (insn)
insn = PREV_INSN (insn);
else
insn = get_last_insn ();
}
if (insn == BB_END (bb))
emit_note_after (NOTE_INSN_DELETED, insn);
new_bb = create_basic_block (NEXT_INSN (insn), BB_END (bb), bb);
BB_COPY_PARTITION (new_bb, bb);
BB_END (bb) = insn;
new_bb->succs = bb->succs;
bb->succs = NULL;
FOR_EACH_EDGE (e, ei, new_bb->succs)
e->src = new_bb;
if (bb->global_live_at_start)
{
new_bb->global_live_at_start = ALLOC_REG_SET (®_obstack);
new_bb->global_live_at_end = ALLOC_REG_SET (®_obstack);
COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end);
COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_end);
propagate_block (new_bb, new_bb->global_live_at_start, NULL, NULL, 0);
COPY_REG_SET (bb->global_live_at_end,
new_bb->global_live_at_start);
#ifdef HAVE_conditional_execution
if (reload_completed)
{
bb->flags |= BB_DIRTY;
new_bb->flags |= BB_DIRTY;
}
#endif
}
return new_bb;
}
static void
rtl_merge_blocks (basic_block a, basic_block b)
{
rtx b_head = BB_HEAD (b), b_end = BB_END (b), a_end = BB_END (a);
rtx del_first = NULL_RTX, del_last = NULL_RTX;
int b_empty = 0;
if (LABEL_P (b_head))
{
if (b_head == b_end)
b_empty = 1;
del_first = del_last = b_head;
b_head = NEXT_INSN (b_head);
}
if (NOTE_INSN_BASIC_BLOCK_P (b_head))
{
if (b_head == b_end)
b_empty = 1;
if (! del_last)
del_first = b_head;
del_last = b_head;
b_head = NEXT_INSN (b_head);
}
if (JUMP_P (a_end))
{
rtx prev;
for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
if (!NOTE_P (prev)
|| NOTE_LINE_NUMBER (prev) == NOTE_INSN_BASIC_BLOCK
|| prev == BB_HEAD (a))
break;
del_first = a_end;
#ifdef HAVE_cc0
if (only_sets_cc0_p (prev))
{
rtx tmp = prev;
prev = prev_nonnote_insn (prev);
if (!prev)
prev = BB_HEAD (a);
del_first = tmp;
}
#endif
a_end = PREV_INSN (del_first);
}
else if (BARRIER_P (NEXT_INSN (a_end)))
del_first = NEXT_INSN (a_end);
BB_HEAD (b) = NULL;
delete_insn_chain (del_first, del_last);
if (!b_empty)
{
rtx x;
for (x = a_end; x != b_end; x = NEXT_INSN (x))
set_block_for_insn (x, a);
set_block_for_insn (b_end, a);
a_end = b_end;
}
BB_END (a) = a_end;
}
static bool
rtl_can_merge_blocks (basic_block a,basic_block b)
{
if (flag_reorder_blocks_and_partition
&& (find_reg_note (BB_END (a), REG_CROSSING_JUMP, NULL_RTX)
|| find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX)
|| BB_PARTITION (a) != BB_PARTITION (b)))
return false;
return (EDGE_COUNT (a->succs) == 1
&& EDGE_SUCC (a, 0)->dest == b
&& EDGE_COUNT (b->preds) == 1
&& a != b
&& !(EDGE_SUCC (a, 0)->flags & EDGE_COMPLEX)
&& a->next_bb == b
&& a != ENTRY_BLOCK_PTR && b != EXIT_BLOCK_PTR
&& (!JUMP_P (BB_END (a))
|| (reload_completed
? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
}
rtx
block_label (basic_block block)
{
if (block == EXIT_BLOCK_PTR)
return NULL_RTX;
if (!LABEL_P (BB_HEAD (block)))
{
BB_HEAD (block) = emit_label_before (gen_label_rtx (), BB_HEAD (block));
}
return BB_HEAD (block);
}
edge
try_redirect_by_replacing_jump (edge e, basic_block target, bool in_cfglayout)
{
basic_block src = e->src;
rtx insn = BB_END (src), kill_from;
rtx set;
int fallthru = 0;
if (flag_reorder_blocks_and_partition
&& (find_reg_note (insn, REG_CROSSING_JUMP, NULL_RTX)
|| BB_PARTITION (src) != BB_PARTITION (target)))
return NULL;
if (EDGE_COUNT (src->succs) >= 3
|| (EDGE_COUNT (src->succs) == 2
&& EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target))
return NULL;
if (!onlyjump_p (insn))
return NULL;
if ((!optimize || reload_completed) && tablejump_p (insn, NULL, NULL))
return NULL;
set = single_set (insn);
if (!set || side_effects_p (set))
return NULL;
kill_from = insn;
#ifdef HAVE_cc0
if (reg_mentioned_p (cc0_rtx, PATTERN (insn)))
kill_from = PREV_INSN (insn);
#endif
if (in_cfglayout || can_fallthru (src, target))
{
if (dump_file)
fprintf (dump_file, "Removing jump %i.\n", INSN_UID (insn));
fallthru = 1;
if (in_cfglayout)
{
rtx insn = src->rbi->footer;
delete_insn_chain (kill_from, BB_END (src));
while (insn)
{
if (BARRIER_P (insn))
{
if (PREV_INSN (insn))
NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
else
src->rbi->footer = NEXT_INSN (insn);
if (NEXT_INSN (insn))
PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
}
if (LABEL_P (insn))
break;
insn = NEXT_INSN (insn);
}
}
else
delete_insn_chain (kill_from, PREV_INSN (BB_HEAD (target)));
}
else if (simplejump_p (insn))
{
if (e->dest == target)
return NULL;
if (dump_file)
fprintf (dump_file, "Redirecting jump %i from %i to %i.\n",
INSN_UID (insn), e->dest->index, target->index);
if (!redirect_jump (insn, block_label (target), 0))
{
gcc_assert (target == EXIT_BLOCK_PTR);
return NULL;
}
}
else if (target == EXIT_BLOCK_PTR)
return NULL;
else
{
rtx target_label = block_label (target);
rtx barrier, label, table;
emit_jump_insn_after_noloc (gen_jump (target_label), insn);
JUMP_LABEL (BB_END (src)) = target_label;
LABEL_NUSES (target_label)++;
if (dump_file)
fprintf (dump_file, "Replacing insn %i by jump %i\n",
INSN_UID (insn), INSN_UID (BB_END (src)));
delete_insn_chain (kill_from, insn);
if (tablejump_p (insn, &label, &table))
delete_insn_chain (label, table);
barrier = next_nonnote_insn (BB_END (src));
if (!barrier || !BARRIER_P (barrier))
emit_barrier_after (BB_END (src));
else
{
if (barrier != NEXT_INSN (BB_END (src)))
{
rtx new_insn = BB_END (src);
rtx tmp;
for (tmp = NEXT_INSN (BB_END (src)); tmp != barrier;
tmp = NEXT_INSN (tmp))
set_block_for_insn (tmp, src);
NEXT_INSN (PREV_INSN (new_insn)) = NEXT_INSN (new_insn);
PREV_INSN (NEXT_INSN (new_insn)) = PREV_INSN (new_insn);
NEXT_INSN (new_insn) = barrier;
NEXT_INSN (PREV_INSN (barrier)) = new_insn;
PREV_INSN (new_insn) = PREV_INSN (barrier);
PREV_INSN (barrier) = new_insn;
}
}
}
while (EDGE_COUNT (src->succs) > 1)
remove_edge (e);
e = EDGE_SUCC (src, 0);
if (fallthru)
e->flags = EDGE_FALLTHRU;
else
e->flags = 0;
e->probability = REG_BR_PROB_BASE;
e->count = src->count;
while (NOTE_P (BB_END (e->src))
&& NOTE_LINE_NUMBER (BB_END (e->src)) >= 0)
delete_insn (BB_END (e->src));
if (e->dest != target)
redirect_edge_succ (e, target);
return e;
}
static rtx
last_loop_beg_note (rtx insn)
{
rtx last = insn;
for (insn = NEXT_INSN (insn); insn && NOTE_P (insn)
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK;
insn = NEXT_INSN (insn))
if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
last = insn;
return last;
}
static edge
redirect_branch_edge (edge e, basic_block target)
{
rtx tmp;
rtx old_label = BB_HEAD (e->dest);
basic_block src = e->src;
rtx insn = BB_END (src);
if (e->flags & EDGE_FALLTHRU)
return NULL;
else if (!JUMP_P (insn))
return NULL;
if (tablejump_p (insn, NULL, &tmp))
{
rtvec vec;
int j;
rtx new_label = block_label (target);
if (target == EXIT_BLOCK_PTR)
return NULL;
if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
vec = XVEC (PATTERN (tmp), 0);
else
vec = XVEC (PATTERN (tmp), 1);
for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
{
RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
--LABEL_NUSES (old_label);
++LABEL_NUSES (new_label);
}
if ((tmp = single_set (insn)) != NULL
&& SET_DEST (tmp) == pc_rtx
&& GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
&& GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
&& XEXP (XEXP (SET_SRC (tmp), 2), 0) == old_label)
{
XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (VOIDmode,
new_label);
--LABEL_NUSES (old_label);
++LABEL_NUSES (new_label);
}
}
else
{
if (computed_jump_p (insn)
|| returnjump_p (insn))
return NULL;
gcc_assert (JUMP_LABEL (insn) == old_label);
if (!redirect_jump (insn, block_label (target), 0))
{
gcc_assert (target == EXIT_BLOCK_PTR);
return NULL;
}
}
if (dump_file)
fprintf (dump_file, "Edge %i->%i redirected to %i\n",
e->src->index, e->dest->index, target->index);
if (e->dest != target)
e = redirect_edge_succ_nodup (e, target);
return e;
}
static edge
rtl_redirect_edge_and_branch (edge e, basic_block target)
{
edge ret;
basic_block src = e->src;
if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
return NULL;
if (e->dest == target)
return e;
if ((ret = try_redirect_by_replacing_jump (e, target, false)) != NULL)
{
src->flags |= BB_DIRTY;
return ret;
}
ret = redirect_branch_edge (e, target);
if (!ret)
return NULL;
src->flags |= BB_DIRTY;
return ret;
}
static basic_block
force_nonfallthru_and_redirect (edge e, basic_block target)
{
basic_block jump_block, new_bb = NULL, src = e->src;
rtx note;
edge new_edge;
int abnormal_edge_flags = 0;
if (e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR
&& any_condjump_p (BB_END (e->src))
&& e->src->next_bb == e->dest
&& JUMP_LABEL (BB_END (e->src)) == BB_HEAD (e->dest))
{
rtx note;
edge b = unchecked_make_edge (e->src, target, 0);
bool redirected;
redirected = redirect_jump (BB_END (e->src), block_label (target), 0);
gcc_assert (redirected);
note = find_reg_note (BB_END (e->src), REG_BR_PROB, NULL_RTX);
if (note)
{
int prob = INTVAL (XEXP (note, 0));
b->probability = prob;
b->count = e->count * prob / REG_BR_PROB_BASE;
e->probability -= e->probability;
e->count -= b->count;
if (e->probability < 0)
e->probability = 0;
if (e->count < 0)
e->count = 0;
}
}
if (e->flags & EDGE_ABNORMAL)
{
gcc_assert (e->dest == target);
abnormal_edge_flags = e->flags & ~(EDGE_FALLTHRU | EDGE_CAN_FALLTHRU);
e->flags &= EDGE_FALLTHRU | EDGE_CAN_FALLTHRU;
}
else
{
gcc_assert (e->flags & EDGE_FALLTHRU);
if (e->src == ENTRY_BLOCK_PTR)
{
edge tmp;
edge_iterator ei;
bool found = false;
basic_block bb = create_basic_block (BB_HEAD (e->dest), NULL, ENTRY_BLOCK_PTR);
e->src = bb;
for (ei = ei_start (ENTRY_BLOCK_PTR->succs); (tmp = ei_safe_edge (ei)); )
{
if (tmp == e)
{
VEC_unordered_remove (edge, ENTRY_BLOCK_PTR->succs, ei.index);
found = true;
break;
}
else
ei_next (&ei);
}
gcc_assert (found);
VEC_safe_push (edge, bb->succs, e);
make_single_succ_edge (ENTRY_BLOCK_PTR, bb, EDGE_FALLTHRU);
}
}
if (EDGE_COUNT (e->src->succs) >= 2 || abnormal_edge_flags)
{
if (!tablejump_p (BB_END (e->src), NULL, ¬e))
note = BB_END (e->src);
note = last_loop_beg_note (note);
note = NEXT_INSN (note);
jump_block = create_basic_block (note, NULL, e->src);
jump_block->count = e->count;
jump_block->frequency = EDGE_FREQUENCY (e);
jump_block->loop_depth = target->loop_depth;
if (target->global_live_at_start)
{
jump_block->global_live_at_start = ALLOC_REG_SET (®_obstack);
jump_block->global_live_at_end = ALLOC_REG_SET (®_obstack);
COPY_REG_SET (jump_block->global_live_at_start,
target->global_live_at_start);
COPY_REG_SET (jump_block->global_live_at_end,
target->global_live_at_start);
}
BB_COPY_PARTITION (jump_block, e->src);
if (flag_reorder_blocks_and_partition
&& targetm.have_named_sections)
{
if (BB_PARTITION (jump_block) == BB_COLD_PARTITION)
{
rtx bb_note, new_note;
for (bb_note = BB_HEAD (jump_block);
bb_note && bb_note != NEXT_INSN (BB_END (jump_block));
bb_note = NEXT_INSN (bb_note))
if (NOTE_P (bb_note)
&& NOTE_LINE_NUMBER (bb_note) == NOTE_INSN_BASIC_BLOCK)
break;
new_note = emit_note_after (NOTE_INSN_UNLIKELY_EXECUTED_CODE,
bb_note);
NOTE_BASIC_BLOCK (new_note) = jump_block;
}
if (JUMP_P (BB_END (jump_block))
&& !any_condjump_p (BB_END (jump_block))
&& (EDGE_SUCC (jump_block, 0)->flags & EDGE_CROSSING))
REG_NOTES (BB_END (jump_block)) = gen_rtx_EXPR_LIST
(REG_CROSSING_JUMP, NULL_RTX,
REG_NOTES (BB_END (jump_block)));
}
new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
new_edge->probability = e->probability;
new_edge->count = e->count;
redirect_edge_pred (e, jump_block);
e->probability = REG_BR_PROB_BASE;
new_bb = jump_block;
}
else
jump_block = e->src;
e->flags &= ~EDGE_FALLTHRU;
if (target == EXIT_BLOCK_PTR)
{
#ifdef HAVE_return
emit_jump_insn_after_noloc (gen_return (), BB_END (jump_block));
#else
gcc_unreachable ();
#endif
}
else
{
rtx label = block_label (target);
emit_jump_insn_after_noloc (gen_jump (label), BB_END (jump_block));
JUMP_LABEL (BB_END (jump_block)) = label;
LABEL_NUSES (label)++;
}
emit_barrier_after (BB_END (jump_block));
redirect_edge_succ_nodup (e, target);
if (abnormal_edge_flags)
make_edge (src, target, abnormal_edge_flags);
return new_bb;
}
basic_block
force_nonfallthru (edge e)
{
return force_nonfallthru_and_redirect (e, e->dest);
}
static basic_block
rtl_redirect_edge_and_branch_force (edge e, basic_block target)
{
if (redirect_edge_and_branch (e, target)
|| e->dest == target)
return NULL;
return force_nonfallthru_and_redirect (e, target);
}
static void
rtl_tidy_fallthru_edge (edge e)
{
rtx q;
basic_block b = e->src, c = b->next_bb;
for (q = NEXT_INSN (BB_END (b)); q != BB_HEAD (c); q = NEXT_INSN (q))
if (INSN_P (q))
return;
q = BB_END (b);
if (JUMP_P (q)
&& onlyjump_p (q)
&& (any_uncondjump_p (q)
|| EDGE_COUNT (b->succs) == 1))
{
#ifdef HAVE_cc0
if (any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q)))
q = PREV_INSN (q);
#endif
q = PREV_INSN (q);
while (NOTE_P (q) && NOTE_LINE_NUMBER (q) >= 0)
q = PREV_INSN (q);
}
if (q != PREV_INSN (BB_HEAD (c)))
delete_insn_chain (NEXT_INSN (q), PREV_INSN (BB_HEAD (c)));
e->flags |= EDGE_FALLTHRU;
}
static bool
back_edge_of_syntactic_loop_p (basic_block bb1, basic_block bb2)
{
rtx insn;
int count = 0;
basic_block bb;
if (bb1 == bb2)
return true;
for (bb = bb1; bb && bb != bb2; bb = bb->next_bb)
continue;
if (!bb)
return false;
for (insn = BB_END (bb1); insn != BB_HEAD (bb2) && count >= 0;
insn = NEXT_INSN (insn))
if (NOTE_P (insn))
{
if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
count++;
else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
count--;
}
return count >= 0;
}
static bool
rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED,
basic_block after ATTRIBUTE_UNUSED)
{
return false;
}
static basic_block
rtl_split_edge (edge edge_in)
{
basic_block bb;
rtx before;
gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
if ((edge_in->flags & EDGE_FALLTHRU) == 0)
{
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, edge_in->dest->preds)
if (e->flags & EDGE_FALLTHRU)
break;
if (e)
force_nonfallthru (e);
}
if (edge_in->dest != EXIT_BLOCK_PTR
&& PREV_INSN (BB_HEAD (edge_in->dest))
&& NOTE_P (PREV_INSN (BB_HEAD (edge_in->dest)))
&& (NOTE_LINE_NUMBER (PREV_INSN (BB_HEAD (edge_in->dest)))
== NOTE_INSN_LOOP_BEG)
&& !back_edge_of_syntactic_loop_p (edge_in->dest, edge_in->src))
before = PREV_INSN (BB_HEAD (edge_in->dest));
else if (edge_in->dest != EXIT_BLOCK_PTR)
before = BB_HEAD (edge_in->dest);
else
before = NULL_RTX;
if (edge_in->flags & EDGE_FALLTHRU && edge_in->dest == EXIT_BLOCK_PTR)
{
before = NEXT_INSN (BB_END (edge_in->src));
if (before
&& NOTE_P (before)
&& NOTE_LINE_NUMBER (before) == NOTE_INSN_LOOP_END)
before = NEXT_INSN (before);
bb = create_basic_block (before, NULL, edge_in->src);
BB_COPY_PARTITION (bb, edge_in->src);
}
else
{
bb = create_basic_block (before, NULL, edge_in->dest->prev_bb);
BB_COPY_PARTITION (bb, edge_in->dest);
}
if (edge_in->dest->global_live_at_start)
{
bb->global_live_at_start = ALLOC_REG_SET (®_obstack);
bb->global_live_at_end = ALLOC_REG_SET (®_obstack);
COPY_REG_SET (bb->global_live_at_start,
edge_in->dest->global_live_at_start);
COPY_REG_SET (bb->global_live_at_end,
edge_in->dest->global_live_at_start);
}
make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
if ((edge_in->flags & EDGE_FALLTHRU) == 0)
{
edge redirected = redirect_edge_and_branch (edge_in, bb);
gcc_assert (redirected);
}
else
redirect_edge_succ (edge_in, bb);
return bb;
}
void
insert_insn_on_edge (rtx pattern, edge e)
{
gcc_assert (!((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e)));
if (e->insns.r == NULL_RTX)
start_sequence ();
else
push_to_sequence (e->insns.r);
emit_insn (pattern);
e->insns.r = get_insns ();
end_sequence ();
}
static void
mark_killed_regs (rtx reg, rtx set ATTRIBUTE_UNUSED, void *data)
{
regset killed = data;
int regno, i;
if (GET_CODE (reg) == SUBREG)
reg = SUBREG_REG (reg);
if (!REG_P (reg))
return;
regno = REGNO (reg);
if (regno >= FIRST_PSEUDO_REGISTER)
SET_REGNO_REG_SET (killed, regno);
else
{
for (i = 0; i < (int) hard_regno_nregs[regno][GET_MODE (reg)]; i++)
SET_REGNO_REG_SET (killed, regno + i);
}
}
bool
safe_insert_insn_on_edge (rtx insn, edge e)
{
rtx x;
regset killed;
rtx save_regs = NULL_RTX;
unsigned regno;
int noccmode;
enum machine_mode mode;
reg_set_iterator rsi;
#ifdef AVOID_CCMODE_COPIES
noccmode = true;
#else
noccmode = false;
#endif
killed = ALLOC_REG_SET (®_obstack);
for (x = insn; x; x = NEXT_INSN (x))
if (INSN_P (x))
note_stores (PATTERN (x), mark_killed_regs, killed);
for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
if (!fixed_regs[regno]
&& !REGNO_PTR_FRAME_P (regno))
SET_REGNO_REG_SET (killed, regno);
bitmap_and_into (killed, e->dest->global_live_at_start);
EXECUTE_IF_SET_IN_REG_SET (killed, 0, regno, rsi)
{
mode = regno < FIRST_PSEUDO_REGISTER
? reg_raw_mode[regno]
: GET_MODE (regno_reg_rtx[regno]);
if (mode == VOIDmode)
return false;
if (noccmode && mode == CCmode)
return false;
save_regs = alloc_EXPR_LIST (0,
alloc_EXPR_LIST (0,
gen_reg_rtx (mode),
gen_raw_REG (mode, regno)),
save_regs);
}
if (save_regs)
{
rtx from, to;
start_sequence ();
for (x = save_regs; x; x = XEXP (x, 1))
{
from = XEXP (XEXP (x, 0), 1);
to = XEXP (XEXP (x, 0), 0);
emit_move_insn (to, from);
}
emit_insn (insn);
for (x = save_regs; x; x = XEXP (x, 1))
{
from = XEXP (XEXP (x, 0), 0);
to = XEXP (XEXP (x, 0), 1);
emit_move_insn (to, from);
}
insn = get_insns ();
end_sequence ();
free_EXPR_LIST_list (&save_regs);
}
insert_insn_on_edge (insn, e);
FREE_REG_SET (killed);
return true;
}
static void
commit_one_edge_insertion (edge e, int watch_calls)
{
rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last;
basic_block bb = NULL;
insns = e->insns.r;
e->insns.r = NULL_RTX;
if (watch_calls && (e->flags & EDGE_FALLTHRU)
&& EDGE_COUNT (e->dest->preds) == 1
&& e->src != ENTRY_BLOCK_PTR
&& CALL_P (BB_END (e->src)))
{
rtx next = next_nonnote_insn (BB_END (e->src));
after = BB_HEAD (e->dest);
while (next
&& keep_with_call_p (next))
{
after = next;
next = next_nonnote_insn (next);
}
bb = e->dest;
}
if (!before && !after)
{
if (EDGE_COUNT (e->dest->preds) == 1 && e->dest != EXIT_BLOCK_PTR)
{
bb = e->dest;
tmp = BB_HEAD (bb);
if (LABEL_P (tmp))
tmp = NEXT_INSN (tmp);
if (NOTE_INSN_BASIC_BLOCK_P (tmp))
tmp = NEXT_INSN (tmp);
if (tmp
&& NOTE_P (tmp)
&& NOTE_LINE_NUMBER (tmp) == NOTE_INSN_UNLIKELY_EXECUTED_CODE)
tmp = NEXT_INSN (tmp);
if (tmp == BB_HEAD (bb))
before = tmp;
else if (tmp)
after = PREV_INSN (tmp);
else
after = get_last_insn ();
}
else if ((e->flags & EDGE_ABNORMAL) == 0
&& EDGE_COUNT (e->src->succs) == 1
&& e->src != ENTRY_BLOCK_PTR)
{
bb = e->src;
if (JUMP_P (BB_END (bb)))
for (before = BB_END (bb);
NOTE_P (PREV_INSN (before))
&& NOTE_LINE_NUMBER (PREV_INSN (before)) ==
NOTE_INSN_LOOP_BEG; before = PREV_INSN (before))
;
else
{
gcc_assert (e->flags & EDGE_FALLTHRU);
after = BB_END (bb);
}
}
else
{
bb = split_edge (e);
after = BB_END (bb);
if (flag_reorder_blocks_and_partition
&& targetm.have_named_sections
&& e->src != ENTRY_BLOCK_PTR
&& BB_PARTITION (e->src) == BB_COLD_PARTITION
&& !(e->flags & EDGE_CROSSING))
{
rtx bb_note, new_note, cur_insn;
bb_note = NULL_RTX;
for (cur_insn = BB_HEAD (bb); cur_insn != NEXT_INSN (BB_END (bb));
cur_insn = NEXT_INSN (cur_insn))
if (NOTE_P (cur_insn)
&& NOTE_LINE_NUMBER (cur_insn) == NOTE_INSN_BASIC_BLOCK)
{
bb_note = cur_insn;
break;
}
new_note = emit_note_after (NOTE_INSN_UNLIKELY_EXECUTED_CODE,
bb_note);
NOTE_BASIC_BLOCK (new_note) = bb;
if (JUMP_P (BB_END (bb))
&& !any_condjump_p (BB_END (bb))
&& (EDGE_SUCC (bb, 0)->flags & EDGE_CROSSING))
REG_NOTES (BB_END (bb)) = gen_rtx_EXPR_LIST
(REG_CROSSING_JUMP, NULL_RTX, REG_NOTES (BB_END (bb)));
if (after == bb_note)
after = new_note;
}
}
}
if (before)
{
emit_insn_before_noloc (insns, before);
last = prev_nonnote_insn (before);
}
else
last = emit_insn_after_noloc (insns, after);
if (returnjump_p (last))
{
e = EDGE_SUCC (bb, 0);
gcc_assert (e->dest == EXIT_BLOCK_PTR
&& EDGE_COUNT (bb->succs) == 1 && (e->flags & EDGE_FALLTHRU));
e->flags &= ~EDGE_FALLTHRU;
emit_barrier_after (last);
if (before)
delete_insn (before);
}
else
gcc_assert (!JUMP_P (last));
bb->aux = &bb->aux;
}
void
commit_edge_insertions (void)
{
basic_block bb;
sbitmap blocks;
bool changed = false;
#ifdef ENABLE_CHECKING
verify_flow_info ();
#endif
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
{
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->succs)
if (e->insns.r)
{
changed = true;
commit_one_edge_insertion (e, false);
}
}
if (!changed)
return;
blocks = sbitmap_alloc (last_basic_block);
sbitmap_zero (blocks);
FOR_EACH_BB (bb)
if (bb->aux)
{
SET_BIT (blocks, bb->index);
gcc_assert (bb->aux == &bb->aux);
bb->aux = NULL;
}
find_many_sub_basic_blocks (blocks);
sbitmap_free (blocks);
}
void
commit_edge_insertions_watch_calls (void)
{
basic_block bb;
sbitmap blocks;
bool changed = false;
#ifdef ENABLE_CHECKING
verify_flow_info ();
#endif
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
{
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->succs)
if (e->insns.r)
{
changed = true;
commit_one_edge_insertion (e, true);
}
}
if (!changed)
return;
blocks = sbitmap_alloc (last_basic_block);
sbitmap_zero (blocks);
FOR_EACH_BB (bb)
if (bb->aux)
{
SET_BIT (blocks, bb->index);
gcc_assert (bb->aux == &bb->aux);
bb->aux = NULL;
}
find_many_sub_basic_blocks (blocks);
sbitmap_free (blocks);
}
static void
rtl_dump_bb (basic_block bb, FILE *outf, int indent)
{
rtx insn;
rtx last;
char *s_indent;
s_indent = alloca ((size_t) indent + 1);
memset (s_indent, ' ', (size_t) indent);
s_indent[indent] = '\0';
fprintf (outf, ";;%s Registers live at start: ", s_indent);
dump_regset (bb->global_live_at_start, outf);
putc ('\n', outf);
for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb)); insn != last;
insn = NEXT_INSN (insn))
print_rtl_single (outf, insn);
fprintf (outf, ";;%s Registers live at end: ", s_indent);
dump_regset (bb->global_live_at_end, outf);
putc ('\n', outf);
}
void
print_rtl_with_bb (FILE *outf, rtx rtx_first)
{
rtx tmp_rtx;
if (rtx_first == 0)
fprintf (outf, "(nil)\n");
else
{
enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
int max_uid = get_max_uid ();
basic_block *start = xcalloc (max_uid, sizeof (basic_block));
basic_block *end = xcalloc (max_uid, sizeof (basic_block));
enum bb_state *in_bb_p = xcalloc (max_uid, sizeof (enum bb_state));
basic_block bb;
FOR_EACH_BB_REVERSE (bb)
{
rtx x;
start[INSN_UID (BB_HEAD (bb))] = bb;
end[INSN_UID (BB_END (bb))] = bb;
for (x = BB_HEAD (bb); x != NULL_RTX; x = NEXT_INSN (x))
{
enum bb_state state = IN_MULTIPLE_BB;
if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
state = IN_ONE_BB;
in_bb_p[INSN_UID (x)] = state;
if (x == BB_END (bb))
break;
}
}
for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
{
int did_output;
if ((bb = start[INSN_UID (tmp_rtx)]) != NULL)
{
fprintf (outf, ";; Start of basic block %d, registers live:",
bb->index);
dump_regset (bb->global_live_at_start, outf);
putc ('\n', outf);
}
if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
&& !NOTE_P (tmp_rtx)
&& !BARRIER_P (tmp_rtx))
fprintf (outf, ";; Insn is not within a basic block\n");
else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
fprintf (outf, ";; Insn is in multiple basic blocks\n");
did_output = print_rtl_single (outf, tmp_rtx);
if ((bb = end[INSN_UID (tmp_rtx)]) != NULL)
{
fprintf (outf, ";; End of basic block %d, registers live:\n",
bb->index);
dump_regset (bb->global_live_at_end, outf);
putc ('\n', outf);
}
if (did_output)
putc ('\n', outf);
}
free (start);
free (end);
free (in_bb_p);
}
if (current_function_epilogue_delay_list != 0)
{
fprintf (outf, "\n;; Insns in epilogue delay list:\n\n");
for (tmp_rtx = current_function_epilogue_delay_list; tmp_rtx != 0;
tmp_rtx = XEXP (tmp_rtx, 1))
print_rtl_single (outf, XEXP (tmp_rtx, 0));
}
}
void
update_br_prob_note (basic_block bb)
{
rtx note;
if (!JUMP_P (BB_END (bb)))
return;
note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX);
if (!note || INTVAL (XEXP (note, 0)) == BRANCH_EDGE (bb)->probability)
return;
XEXP (note, 0) = GEN_INT (BRANCH_EDGE (bb)->probability);
}
static int
rtl_verify_flow_info_1 (void)
{
const int max_uid = get_max_uid ();
rtx last_head = get_last_insn ();
basic_block *bb_info;
rtx x;
int err = 0;
basic_block bb, last_bb_seen;
bb_info = xcalloc (max_uid, sizeof (basic_block));
last_bb_seen = ENTRY_BLOCK_PTR;
FOR_EACH_BB_REVERSE (bb)
{
rtx head = BB_HEAD (bb);
rtx end = BB_END (bb);
for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
if (x == end)
break;
if (!x)
{
error ("end insn %d for block %d not found in the insn stream",
INSN_UID (end), bb->index);
err = 1;
}
for (; x != NULL_RTX; x = PREV_INSN (x))
{
if (bb_info[INSN_UID (x)] != NULL)
{
error ("insn %d is in multiple basic blocks (%d and %d)",
INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
err = 1;
}
bb_info[INSN_UID (x)] = bb;
if (x == head)
break;
}
if (!x)
{
error ("head insn %d for block %d not found in the insn stream",
INSN_UID (head), bb->index);
err = 1;
}
last_head = x;
}
FOR_EACH_BB_REVERSE (bb)
{
int n_fallthru = 0, n_eh = 0, n_call = 0, n_abnormal = 0, n_branch = 0;
edge e, fallthru = NULL;
rtx note;
edge_iterator ei;
if (JUMP_P (BB_END (bb))
&& (note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX))
&& EDGE_COUNT (bb->succs) >= 2
&& any_condjump_p (BB_END (bb)))
{
if (INTVAL (XEXP (note, 0)) != BRANCH_EDGE (bb)->probability
&& profile_status != PROFILE_ABSENT)
{
error ("verify_flow_info: REG_BR_PROB does not match cfg %wi %i",
INTVAL (XEXP (note, 0)), BRANCH_EDGE (bb)->probability);
err = 1;
}
}
FOR_EACH_EDGE (e, ei, bb->succs)
{
if (e->flags & EDGE_FALLTHRU)
{
n_fallthru++, fallthru = e;
if ((e->flags & EDGE_CROSSING)
|| (BB_PARTITION (e->src) != BB_PARTITION (e->dest)
&& e->src != ENTRY_BLOCK_PTR
&& e->dest != EXIT_BLOCK_PTR))
{
error ("Fallthru edge crosses section boundary (bb %i)",
e->src->index);
err = 1;
}
}
if ((e->flags & ~(EDGE_DFS_BACK
| EDGE_CAN_FALLTHRU
| EDGE_IRREDUCIBLE_LOOP
| EDGE_LOOP_EXIT
| EDGE_CROSSING)) == 0)
n_branch++;
if (e->flags & EDGE_ABNORMAL_CALL)
n_call++;
if (e->flags & EDGE_EH)
n_eh++;
else if (e->flags & EDGE_ABNORMAL)
n_abnormal++;
}
if (n_eh && GET_CODE (PATTERN (BB_END (bb))) != RESX
&& !find_reg_note (BB_END (bb), REG_EH_REGION, NULL_RTX))
{
error ("Missing REG_EH_REGION note in the end of bb %i", bb->index);
err = 1;
}
if (n_branch
&& (!JUMP_P (BB_END (bb))
|| (n_branch > 1 && (any_uncondjump_p (BB_END (bb))
|| any_condjump_p (BB_END (bb))))))
{
error ("Too many outgoing branch edges from bb %i", bb->index);
err = 1;
}
if (n_fallthru && any_uncondjump_p (BB_END (bb)))
{
error ("Fallthru edge after unconditional jump %i", bb->index);
err = 1;
}
if (n_branch != 1 && any_uncondjump_p (BB_END (bb)))
{
error ("Wrong amount of branch edges after unconditional jump %i", bb->index);
err = 1;
}
if (n_branch != 1 && any_condjump_p (BB_END (bb))
&& JUMP_LABEL (BB_END (bb)) != BB_HEAD (fallthru->dest))
{
error ("Wrong amount of branch edges after conditional jump %i", bb->index);
err = 1;
}
if (n_call && !CALL_P (BB_END (bb)))
{
error ("Call edges for non-call insn in bb %i", bb->index);
err = 1;
}
if (n_abnormal
&& (!CALL_P (BB_END (bb)) && n_call != n_abnormal)
&& (!JUMP_P (BB_END (bb))
|| any_condjump_p (BB_END (bb))
|| any_uncondjump_p (BB_END (bb))))
{
error ("Abnormal edges for no purpose in bb %i", bb->index);
err = 1;
}
for (x = BB_HEAD (bb); x != NEXT_INSN (BB_END (bb)); x = NEXT_INSN (x))
if (!BARRIER_P (x) && BLOCK_FOR_INSN (x) != bb)
{
debug_rtx (x);
if (! BLOCK_FOR_INSN (x))
error
("insn %d inside basic block %d but block_for_insn is NULL",
INSN_UID (x), bb->index);
else
error
("insn %d inside basic block %d but block_for_insn is %i",
INSN_UID (x), bb->index, BLOCK_FOR_INSN (x)->index);
err = 1;
}
x = BB_HEAD (bb);
if (LABEL_P (x))
{
if (BB_END (bb) == x)
{
error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
bb->index);
err = 1;
}
x = NEXT_INSN (x);
}
if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
{
error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
bb->index);
err = 1;
}
if (BB_END (bb) == x)
;
else
for (x = NEXT_INSN (x); x; x = NEXT_INSN (x))
{
if (NOTE_INSN_BASIC_BLOCK_P (x))
{
error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
INSN_UID (x), bb->index);
err = 1;
}
if (x == BB_END (bb))
break;
if (control_flow_insn_p (x))
{
error ("in basic block %d:", bb->index);
fatal_insn ("flow control insn inside a basic block", x);
}
}
}
free (bb_info);
return err;
}
static int
rtl_verify_flow_info (void)
{
basic_block bb;
int err = rtl_verify_flow_info_1 ();
rtx x;
int num_bb_notes;
const rtx rtx_first = get_insns ();
basic_block last_bb_seen = ENTRY_BLOCK_PTR, curr_bb = NULL;
FOR_EACH_BB_REVERSE (bb)
{
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->succs)
if (e->flags & EDGE_FALLTHRU)
break;
if (!e)
{
rtx insn;
for (insn = BB_END (bb); !insn || !BARRIER_P (insn);
insn = NEXT_INSN (insn))
if (!insn
|| (NOTE_P (insn)
&& NOTE_LINE_NUMBER (insn) == NOTE_INSN_BASIC_BLOCK))
{
error ("missing barrier after block %i", bb->index);
err = 1;
break;
}
}
else if (e->src != ENTRY_BLOCK_PTR
&& e->dest != EXIT_BLOCK_PTR)
{
rtx insn;
if (e->src->next_bb != e->dest)
{
error
("verify_flow_info: Incorrect blocks for fallthru %i->%i",
e->src->index, e->dest->index);
err = 1;
}
else
for (insn = NEXT_INSN (BB_END (e->src)); insn != BB_HEAD (e->dest);
insn = NEXT_INSN (insn))
if (BARRIER_P (insn) || INSN_P (insn))
{
error ("verify_flow_info: Incorrect fallthru %i->%i",
e->src->index, e->dest->index);
fatal_insn ("wrong insn in the fallthru edge", insn);
err = 1;
}
}
}
num_bb_notes = 0;
last_bb_seen = ENTRY_BLOCK_PTR;
for (x = rtx_first; x; x = NEXT_INSN (x))
{
if (NOTE_INSN_BASIC_BLOCK_P (x))
{
bb = NOTE_BASIC_BLOCK (x);
num_bb_notes++;
if (bb != last_bb_seen->next_bb)
internal_error ("basic blocks not laid down consecutively");
curr_bb = last_bb_seen = bb;
}
if (!curr_bb)
{
switch (GET_CODE (x))
{
case BARRIER:
case NOTE:
break;
case CODE_LABEL:
if (NEXT_INSN (x)
&& JUMP_P (NEXT_INSN (x))
&& (GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_DIFF_VEC
|| GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_VEC))
x = NEXT_INSN (x);
break;
default:
fatal_insn ("insn outside basic block", x);
}
}
if (JUMP_P (x)
&& returnjump_p (x) && ! condjump_p (x)
&& ! (NEXT_INSN (x) && BARRIER_P (NEXT_INSN (x))))
fatal_insn ("return not followed by barrier", x);
if (curr_bb && x == BB_END (curr_bb))
curr_bb = NULL;
}
if (num_bb_notes != n_basic_blocks)
internal_error
("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
num_bb_notes, n_basic_blocks);
return err;
}
bool
purge_dead_edges (basic_block bb)
{
edge e;
rtx insn = BB_END (bb), note;
bool purged = false;
bool found;
edge_iterator ei;
if (NONJUMP_INSN_P (insn)
&& (note = find_reg_note (insn, REG_EH_REGION, NULL)))
{
rtx eqnote;
if (! may_trap_p (PATTERN (insn))
|| ((eqnote = find_reg_equal_equiv_note (insn))
&& ! may_trap_p (XEXP (eqnote, 0))))
remove_note (insn, note);
}
for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
{
if (e->flags & EDGE_EH)
{
if (can_throw_internal (BB_END (bb)))
{
if ((e->flags & EDGE_ABNORMAL_CALL)
&& GET_CODE (BB_END (bb)) != CALL_INSN)
e->flags &= ~EDGE_ABNORMAL_CALL;
ei_next (&ei);
continue;
}
}
else if (e->flags & EDGE_ABNORMAL_CALL)
{
if (CALL_P (BB_END (bb))
&& (! (note = find_reg_note (insn, REG_EH_REGION, NULL))
|| INTVAL (XEXP (note, 0)) >= 0))
{
ei_next (&ei);
continue;
}
}
else
{
ei_next (&ei);
continue;
}
remove_edge (e);
bb->flags |= BB_DIRTY;
purged = true;
}
if (JUMP_P (insn))
{
rtx note;
edge b,f;
edge_iterator ei;
if (!any_condjump_p (insn)
&& !returnjump_p (insn)
&& !simplejump_p (insn))
return purged;
if (simplejump_p (insn))
{
note = find_reg_note (insn, REG_BR_PROB, NULL);
if (note)
remove_note (insn, note);
while ((note = find_reg_note (insn, REG_BR_PRED, NULL)))
remove_note (insn, note);
}
for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
{
e->flags &= ~EDGE_ABNORMAL;
if ((e->flags & EDGE_FALLTHRU) && any_condjump_p (insn))
{
ei_next (&ei);
continue;
}
else if (e->dest != EXIT_BLOCK_PTR
&& BB_HEAD (e->dest) == JUMP_LABEL (insn))
{
ei_next (&ei);
continue;
}
else if (e->dest == EXIT_BLOCK_PTR && returnjump_p (insn))
{
ei_next (&ei);
continue;
}
else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
{
e->flags |= EDGE_ABNORMAL;
ei_next (&ei);
continue;
}
bb->flags |= BB_DIRTY;
purged = true;
remove_edge (e);
}
if (EDGE_COUNT (bb->succs) == 0 || !purged)
return purged;
if (dump_file)
fprintf (dump_file, "Purged edges from bb %i\n", bb->index);
if (!optimize)
return purged;
if (EDGE_COUNT (bb->succs) == 1)
{
EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
EDGE_SUCC (bb, 0)->count = bb->count;
}
else
{
note = find_reg_note (insn, REG_BR_PROB, NULL);
if (!note)
return purged;
b = BRANCH_EDGE (bb);
f = FALLTHRU_EDGE (bb);
b->probability = INTVAL (XEXP (note, 0));
f->probability = REG_BR_PROB_BASE - b->probability;
b->count = bb->count * b->probability / REG_BR_PROB_BASE;
f->count = bb->count * f->probability / REG_BR_PROB_BASE;
}
return purged;
}
else if (CALL_P (insn) && SIBLING_CALL_P (insn))
{
gcc_assert (EDGE_COUNT (bb->succs) == 1);
gcc_assert (EDGE_SUCC (bb, 0)->flags == (EDGE_SIBCALL | EDGE_ABNORMAL));
return 0;
}
found = false;
FOR_EACH_EDGE (e, ei, bb->succs)
if (! (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU)))
{
found = true;
break;
}
if (!found)
return purged;
for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
{
if (!(e->flags & EDGE_FALLTHRU))
{
bb->flags |= BB_DIRTY;
remove_edge (e);
purged = true;
}
else
ei_next (&ei);
}
gcc_assert (EDGE_COUNT (bb->succs) == 1);
EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
EDGE_SUCC (bb, 0)->count = bb->count;
if (dump_file)
fprintf (dump_file, "Purged non-fallthru edges from bb %i\n",
bb->index);
return purged;
}
bool
purge_all_dead_edges (int update_life_p)
{
int purged = false;
sbitmap blocks = 0;
basic_block bb;
if (update_life_p)
{
blocks = sbitmap_alloc (last_basic_block);
sbitmap_zero (blocks);
}
FOR_EACH_BB (bb)
{
bool purged_here = purge_dead_edges (bb);
purged |= purged_here;
if (purged_here && update_life_p)
SET_BIT (blocks, bb->index);
}
if (update_life_p && purged)
update_life_info (blocks, UPDATE_LIFE_GLOBAL,
PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE
| PROP_KILL_DEAD_CODE);
if (update_life_p)
sbitmap_free (blocks);
return purged;
}
static basic_block
cfg_layout_split_block (basic_block bb, void *insnp)
{
rtx insn = insnp;
basic_block new_bb = rtl_split_block (bb, insn);
new_bb->rbi->footer = bb->rbi->footer;
bb->rbi->footer = NULL;
return new_bb;
}
static edge
cfg_layout_redirect_edge_and_branch (edge e, basic_block dest)
{
basic_block src = e->src;
edge ret;
if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
return NULL;
if (e->dest == dest)
return e;
if (e->src != ENTRY_BLOCK_PTR
&& (ret = try_redirect_by_replacing_jump (e, dest, true)))
{
src->flags |= BB_DIRTY;
return ret;
}
if (e->src == ENTRY_BLOCK_PTR
&& (e->flags & EDGE_FALLTHRU) && !(e->flags & EDGE_COMPLEX))
{
if (dump_file)
fprintf (dump_file, "Redirecting entry edge from bb %i to %i\n",
e->src->index, dest->index);
e->src->flags |= BB_DIRTY;
redirect_edge_succ (e, dest);
return e;
}
if (e->flags & EDGE_FALLTHRU)
{
if (JUMP_P (BB_END (src))
&& label_is_jump_target_p (BB_HEAD (e->dest),
BB_END (src)))
{
edge redirected;
if (dump_file)
fprintf (dump_file, "Fallthru edge unified with branch "
"%i->%i redirected to %i\n",
e->src->index, e->dest->index, dest->index);
e->flags &= ~EDGE_FALLTHRU;
redirected = redirect_branch_edge (e, dest);
gcc_assert (redirected);
e->flags |= EDGE_FALLTHRU;
e->src->flags |= BB_DIRTY;
return e;
}
if (EDGE_COUNT (src->succs) == 2)
{
edge s = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
if (s->dest == dest
&& any_condjump_p (BB_END (src))
&& onlyjump_p (BB_END (src)))
delete_insn (BB_END (src));
}
ret = redirect_edge_succ_nodup (e, dest);
if (dump_file)
fprintf (dump_file, "Fallthru edge %i->%i redirected to %i\n",
e->src->index, e->dest->index, dest->index);
}
else
ret = redirect_branch_edge (e, dest);
gcc_assert (!simplejump_p (BB_END (src)));
src->flags |= BB_DIRTY;
return ret;
}
static basic_block
cfg_layout_redirect_edge_and_branch_force (edge e, basic_block dest)
{
edge redirected = cfg_layout_redirect_edge_and_branch (e, dest);
gcc_assert (redirected);
return NULL;
}
static void
cfg_layout_delete_block (basic_block bb)
{
rtx insn, next, prev = PREV_INSN (BB_HEAD (bb)), *to, remaints;
if (bb->rbi->header)
{
next = BB_HEAD (bb);
if (prev)
NEXT_INSN (prev) = bb->rbi->header;
else
set_first_insn (bb->rbi->header);
PREV_INSN (bb->rbi->header) = prev;
insn = bb->rbi->header;
while (NEXT_INSN (insn))
insn = NEXT_INSN (insn);
NEXT_INSN (insn) = next;
PREV_INSN (next) = insn;
}
next = NEXT_INSN (BB_END (bb));
if (bb->rbi->footer)
{
insn = bb->rbi->footer;
while (insn)
{
if (BARRIER_P (insn))
{
if (PREV_INSN (insn))
NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
else
bb->rbi->footer = NEXT_INSN (insn);
if (NEXT_INSN (insn))
PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
}
if (LABEL_P (insn))
break;
insn = NEXT_INSN (insn);
}
if (bb->rbi->footer)
{
insn = BB_END (bb);
NEXT_INSN (insn) = bb->rbi->footer;
PREV_INSN (bb->rbi->footer) = insn;
while (NEXT_INSN (insn))
insn = NEXT_INSN (insn);
NEXT_INSN (insn) = next;
if (next)
PREV_INSN (next) = insn;
else
set_last_insn (insn);
}
}
if (bb->next_bb != EXIT_BLOCK_PTR)
to = &bb->next_bb->rbi->header;
else
to = &cfg_layout_function_footer;
rtl_delete_block (bb);
if (prev)
prev = NEXT_INSN (prev);
else
prev = get_insns ();
if (next)
next = PREV_INSN (next);
else
next = get_last_insn ();
if (next && NEXT_INSN (next) != prev)
{
remaints = unlink_insn_chain (prev, next);
insn = remaints;
while (NEXT_INSN (insn))
insn = NEXT_INSN (insn);
NEXT_INSN (insn) = *to;
if (*to)
PREV_INSN (*to) = insn;
*to = remaints;
}
}
static bool
cfg_layout_can_merge_blocks_p (basic_block a, basic_block b)
{
if (flag_reorder_blocks_and_partition
&& (find_reg_note (BB_END (a), REG_CROSSING_JUMP, NULL_RTX)
|| find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX)
|| BB_PARTITION (a) != BB_PARTITION (b)))
return false;
return (EDGE_COUNT (a->succs) == 1
&& EDGE_SUCC (a, 0)->dest == b
&& EDGE_COUNT (b->preds) == 1
&& a != b
&& !(EDGE_SUCC (a, 0)->flags & EDGE_COMPLEX)
&& a != ENTRY_BLOCK_PTR && b != EXIT_BLOCK_PTR
&& (!JUMP_P (BB_END (a))
|| (reload_completed
? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
}
static void
cfg_layout_merge_blocks (basic_block a, basic_block b)
{
#ifdef ENABLE_CHECKING
gcc_assert (cfg_layout_can_merge_blocks_p (a, b));
#endif
if (LABEL_P (BB_HEAD (b)))
delete_insn (BB_HEAD (b));
if (JUMP_P (BB_END (a)))
try_redirect_by_replacing_jump (EDGE_SUCC (a, 0), b, true);
gcc_assert (!JUMP_P (BB_END (a)));
if (b->rbi->header)
{
rtx first = BB_END (a), last;
last = emit_insn_after_noloc (b->rbi->header, BB_END (a));
delete_insn_chain (NEXT_INSN (first), last);
b->rbi->header = NULL;
}
if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
{
rtx first = unlink_insn_chain (BB_HEAD (b), BB_END (b));
emit_insn_after_noloc (first, BB_END (a));
if (!NOTE_INSN_BASIC_BLOCK_P (first))
first = NEXT_INSN (first);
gcc_assert (NOTE_INSN_BASIC_BLOCK_P (first));
BB_HEAD (b) = NULL;
delete_insn (first);
}
else
{
rtx insn;
for (insn = BB_HEAD (b);
insn != NEXT_INSN (BB_END (b));
insn = NEXT_INSN (insn))
set_block_for_insn (insn, a);
insn = BB_HEAD (b);
if (!NOTE_INSN_BASIC_BLOCK_P (insn))
insn = NEXT_INSN (insn);
gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
BB_HEAD (b) = NULL;
BB_END (a) = BB_END (b);
delete_insn (insn);
}
if (b->rbi->footer)
{
if (!a->rbi->footer)
a->rbi->footer = b->rbi->footer;
else
{
rtx last = a->rbi->footer;
while (NEXT_INSN (last))
last = NEXT_INSN (last);
NEXT_INSN (last) = b->rbi->footer;
PREV_INSN (b->rbi->footer) = last;
}
b->rbi->footer = NULL;
}
if (dump_file)
fprintf (dump_file, "Merged blocks %d and %d.\n",
a->index, b->index);
}
static basic_block
cfg_layout_split_edge (edge e)
{
edge new_e;
basic_block new_bb =
create_basic_block (e->src != ENTRY_BLOCK_PTR
? NEXT_INSN (BB_END (e->src)) : get_insns (),
NULL_RTX, e->src);
if (e->dest->global_live_at_start)
{
new_bb->global_live_at_start = ALLOC_REG_SET (®_obstack);
new_bb->global_live_at_end = ALLOC_REG_SET (®_obstack);
COPY_REG_SET (new_bb->global_live_at_start,
e->dest->global_live_at_start);
COPY_REG_SET (new_bb->global_live_at_end,
e->dest->global_live_at_start);
}
new_e = make_edge (new_bb, e->dest, EDGE_FALLTHRU);
redirect_edge_and_branch_force (e, new_bb);
return new_bb;
}
static void
rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED)
{
}
static bool
rtl_block_ends_with_call_p (basic_block bb)
{
rtx insn = BB_END (bb);
while (!CALL_P (insn)
&& insn != BB_HEAD (bb)
&& keep_with_call_p (insn))
insn = PREV_INSN (insn);
return (CALL_P (insn));
}
static bool
rtl_block_ends_with_condjump_p (basic_block bb)
{
return any_condjump_p (BB_END (bb));
}
static bool
need_fake_edge_p (rtx insn)
{
if (!INSN_P (insn))
return false;
if ((CALL_P (insn)
&& !SIBLING_CALL_P (insn)
&& !find_reg_note (insn, REG_NORETURN, NULL)
&& !find_reg_note (insn, REG_ALWAYS_RETURN, NULL)
&& !CONST_OR_PURE_CALL_P (insn)))
return true;
return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS
&& MEM_VOLATILE_P (PATTERN (insn)))
|| (GET_CODE (PATTERN (insn)) == PARALLEL
&& asm_noperands (insn) != -1
&& MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0)))
|| GET_CODE (PATTERN (insn)) == ASM_INPUT);
}
static int
rtl_flow_call_edges_add (sbitmap blocks)
{
int i;
int blocks_split = 0;
int last_bb = last_basic_block;
bool check_last_block = false;
if (n_basic_blocks == 0)
return 0;
if (! blocks)
check_last_block = true;
else
check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
if (check_last_block)
{
basic_block bb = EXIT_BLOCK_PTR->prev_bb;
rtx insn = BB_END (bb);
while (insn != BB_HEAD (bb)
&& keep_with_call_p (insn))
insn = PREV_INSN (insn);
if (need_fake_edge_p (insn))
{
edge e;
e = find_edge (bb, EXIT_BLOCK_PTR);
if (e)
{
insert_insn_on_edge (gen_rtx_USE (VOIDmode, const0_rtx), e);
commit_edge_insertions ();
}
}
}
for (i = 0; i < last_bb; i++)
{
basic_block bb = BASIC_BLOCK (i);
rtx insn;
rtx prev_insn;
if (!bb)
continue;
if (blocks && !TEST_BIT (blocks, i))
continue;
for (insn = BB_END (bb); ; insn = prev_insn)
{
prev_insn = PREV_INSN (insn);
if (need_fake_edge_p (insn))
{
edge e;
rtx split_at_insn = insn;
if (CALL_P (insn))
while (split_at_insn != BB_END (bb)
&& keep_with_call_p (NEXT_INSN (split_at_insn)))
split_at_insn = NEXT_INSN (split_at_insn);
#ifdef ENABLE_CHECKING
if (split_at_insn == BB_END (bb))
{
e = find_edge (bb, EXIT_BLOCK_PTR);
gcc_assert (e == NULL);
}
#endif
if (split_at_insn != BB_END (bb))
{
e = split_block (bb, split_at_insn);
if (e)
blocks_split++;
}
make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
}
if (insn == BB_HEAD (bb))
break;
}
}
if (blocks_split)
verify_flow_info ();
return blocks_split;
}
struct cfg_hooks rtl_cfg_hooks = {
"rtl",
rtl_verify_flow_info,
rtl_dump_bb,
rtl_create_basic_block,
rtl_redirect_edge_and_branch,
rtl_redirect_edge_and_branch_force,
rtl_delete_block,
rtl_split_block,
rtl_move_block_after,
rtl_can_merge_blocks,
rtl_merge_blocks,
rtl_predict_edge,
rtl_predicted_by_p,
NULL,
NULL,
rtl_split_edge,
rtl_make_forwarder_block,
rtl_tidy_fallthru_edge,
rtl_block_ends_with_call_p,
rtl_block_ends_with_condjump_p,
rtl_flow_call_edges_add,
NULL,
NULL
};
extern bool cfg_layout_can_duplicate_bb_p (basic_block);
extern basic_block cfg_layout_duplicate_bb (basic_block);
struct cfg_hooks cfg_layout_rtl_cfg_hooks = {
"cfglayout mode",
rtl_verify_flow_info_1,
rtl_dump_bb,
cfg_layout_create_basic_block,
cfg_layout_redirect_edge_and_branch,
cfg_layout_redirect_edge_and_branch_force,
cfg_layout_delete_block,
cfg_layout_split_block,
rtl_move_block_after,
cfg_layout_can_merge_blocks_p,
cfg_layout_merge_blocks,
rtl_predict_edge,
rtl_predicted_by_p,
cfg_layout_can_duplicate_bb_p,
cfg_layout_duplicate_bb,
cfg_layout_split_edge,
rtl_make_forwarder_block,
NULL,
rtl_block_ends_with_call_p,
rtl_block_ends_with_condjump_p,
rtl_flow_call_edges_add,
NULL,
NULL
};