#include "config.h"
#include "system.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"
#ifndef HAVE_return
#define HAVE_return 0
#define gen_return() NULL_RTX
#endif
varray_type basic_block_for_insn;
rtx label_value_list;
rtx tail_recursion_label_list;
static int can_delete_note_p PARAMS ((rtx));
static int can_delete_label_p PARAMS ((rtx));
static void commit_one_edge_insertion PARAMS ((edge));
static bool try_redirect_by_replacing_jump PARAMS ((edge, basic_block));
static rtx last_loop_beg_note PARAMS ((rtx));
static bool back_edge_of_syntactic_loop_p PARAMS ((basic_block, basic_block));
static basic_block force_nonfallthru_and_redirect PARAMS ((edge, basic_block));
static int
can_delete_note_p (note)
rtx note;
{
return (NOTE_LINE_NUMBER (note) == NOTE_INSN_DELETED
|| NOTE_LINE_NUMBER (note) == NOTE_INSN_BASIC_BLOCK);
}
static int
can_delete_label_p (label)
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 (insn)
rtx insn;
{
rtx next = NEXT_INSN (insn);
rtx note;
bool really_delete = true;
if (GET_CODE (insn) == CODE_LABEL)
{
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_SOURCE_FILE (insn) = name;
}
remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels);
}
if (really_delete)
{
if (INSN_DELETED_P (insn))
abort ();
remove_insn (insn);
INSN_DELETED_P (insn) = 1;
}
if (GET_CODE (insn) == JUMP_INSN
&& JUMP_LABEL (insn)
&& GET_CODE (JUMP_LABEL (insn)) == CODE_LABEL)
LABEL_NUSES (JUMP_LABEL (insn))--;
else if ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)) != NULL_RTX
&& GET_CODE (XEXP (note, 0)) == CODE_LABEL)
LABEL_NUSES (XEXP (note, 0))--;
if (GET_CODE (insn) == JUMP_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 (GET_CODE (label) != NOTE)
LABEL_NUSES (label)--;
}
}
return next;
}
void
delete_insn_chain (start, finish)
rtx start, finish;
{
rtx next;
while (1)
{
next = NEXT_INSN (start);
if (GET_CODE (start) == NOTE && !can_delete_note_p (start))
;
else
next = delete_insn (start);
if (start == finish)
break;
start = next;
}
}
basic_block
create_basic_block_structure (index, head, end, bb_note)
int index;
rtx head, end, bb_note;
{
basic_block bb;
if (bb_note
&& ! RTX_INTEGRATED_P (bb_note)
&& (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
&& bb->aux == NULL)
{
rtx after;
if (GET_CODE (head) == CODE_LABEL)
after = head;
else
{
after = PREV_INSN (head);
head = bb_note;
}
if (after != bb_note && NEXT_INSN (after) != bb_note)
reorder_insns (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 (GET_CODE (head) == CODE_LABEL && 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 = head;
bb->end = end;
bb->index = index;
BASIC_BLOCK (index) = bb;
if (basic_block_for_insn)
update_bb_for_insn (bb);
bb->aux = bb;
return bb;
}
basic_block
create_basic_block (index, head, end)
int index;
rtx head, end;
{
basic_block bb;
int i;
VARRAY_GROW (basic_block_info, ++n_basic_blocks);
for (i = n_basic_blocks - 1; i > index; --i)
{
basic_block tmp = BASIC_BLOCK (i - 1);
BASIC_BLOCK (i) = tmp;
tmp->index = i;
}
bb = create_basic_block_structure (index, head, end, NULL);
bb->aux = NULL;
return bb;
}
int
flow_delete_block_noexpunge (b)
basic_block b;
{
int deleted_handler = 0;
rtx insn, end, tmp;
insn = b->head;
never_reached_warning (insn, b->end);
if (GET_CODE (insn) == CODE_LABEL)
maybe_remove_eh_handler (insn);
end = b->end;
if (GET_CODE (end) == JUMP_INSN
&& (tmp = JUMP_LABEL (end)) != NULL_RTX
&& (tmp = NEXT_INSN (tmp)) != NULL_RTX
&& GET_CODE (tmp) == JUMP_INSN
&& (GET_CODE (PATTERN (tmp)) == ADDR_VEC
|| GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
end = tmp;
tmp = next_nonnote_insn (end);
if (tmp && GET_CODE (tmp) == BARRIER)
end = tmp;
b->head = NULL;
delete_insn_chain (insn, end);
while (b->pred != NULL)
remove_edge (b->pred);
while (b->succ != NULL)
remove_edge (b->succ);
b->pred = NULL;
b->succ = NULL;
return deleted_handler;
}
int
flow_delete_block (b)
basic_block b;
{
int deleted_handler = flow_delete_block_noexpunge (b);
expunge_block (b);
return deleted_handler;
}
void
compute_bb_for_insn (max)
int max;
{
int i;
if (basic_block_for_insn)
VARRAY_FREE (basic_block_for_insn);
VARRAY_BB_INIT (basic_block_for_insn, max, "basic_block_for_insn");
for (i = 0; i < n_basic_blocks; ++i)
{
basic_block bb = BASIC_BLOCK (i);
rtx end = bb->end;
rtx insn;
for (insn = bb->head; ; insn = NEXT_INSN (insn))
{
if (INSN_UID (insn) < max)
VARRAY_BB (basic_block_for_insn, INSN_UID (insn)) = bb;
if (insn == end)
break;
}
}
}
void
free_bb_for_insn ()
{
if (basic_block_for_insn)
VARRAY_FREE (basic_block_for_insn);
basic_block_for_insn = 0;
}
void
update_bb_for_insn (bb)
basic_block bb;
{
rtx insn;
if (! basic_block_for_insn)
return;
for (insn = bb->head; ; insn = NEXT_INSN (insn))
{
set_block_for_insn (insn, bb);
if (insn == bb->end)
break;
}
}
void
set_block_for_insn (insn, bb)
rtx insn;
basic_block bb;
{
size_t uid = INSN_UID (insn);
if (uid >= basic_block_for_insn->num_elements)
{
size_t new_size = uid + (uid + 7) / 8;
VARRAY_GROW (basic_block_for_insn, new_size);
}
VARRAY_BB (basic_block_for_insn, uid) = bb;
}
edge
split_block (bb, insn)
basic_block bb;
rtx insn;
{
basic_block new_bb;
edge new_edge;
edge e;
if (bb->end == insn)
return 0;
new_bb = create_basic_block (bb->index + 1, NEXT_INSN (insn), bb->end);
new_bb->count = bb->count;
new_bb->frequency = bb->frequency;
new_bb->loop_depth = bb->loop_depth;
bb->end = insn;
new_bb->succ = bb->succ;
bb->succ = NULL;
for (e = new_bb->succ; e; e = e->succ_next)
e->src = new_bb;
new_edge = make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU);
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_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);
}
return new_edge;
}
void
merge_blocks_nomove (a, b)
basic_block a, b;
{
rtx b_head = b->head, b_end = b->end, a_end = a->end;
rtx del_first = NULL_RTX, del_last = NULL_RTX;
int b_empty = 0;
edge e;
if (GET_CODE (b_head) == CODE_LABEL)
{
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 (GET_CODE (a_end) == JUMP_INSN)
{
rtx prev;
for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
if (GET_CODE (prev) != NOTE
|| NOTE_LINE_NUMBER (prev) == NOTE_INSN_BASIC_BLOCK
|| prev == a->head)
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 = a->head;
del_first = tmp;
}
#endif
a_end = PREV_INSN (del_first);
}
else if (GET_CODE (NEXT_INSN (a_end)) == BARRIER)
del_first = NEXT_INSN (a_end);
while (a->succ)
remove_edge (a->succ);
for (e = b->succ; e; e = e->succ_next)
e->src = a;
a->succ = b->succ;
b->pred = b->succ = NULL;
a->global_live_at_end = b->global_live_at_end;
expunge_block (b);
delete_insn_chain (del_first, del_last);
if (!b_empty)
{
if (basic_block_for_insn)
{
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;
}
a->end = a_end;
}
rtx
block_label (block)
basic_block block;
{
if (block == EXIT_BLOCK_PTR)
return NULL_RTX;
if (GET_CODE (block->head) != CODE_LABEL)
{
block->head = emit_label_before (gen_label_rtx (), block->head);
if (basic_block_for_insn)
set_block_for_insn (block->head, block);
}
return block->head;
}
static bool
try_redirect_by_replacing_jump (e, target)
edge e;
basic_block target;
{
basic_block src = e->src;
rtx insn = src->end, kill_from;
edge tmp;
rtx set;
int fallthru = 0;
for (tmp = src->succ; tmp; tmp = tmp->succ_next)
if (tmp->dest != target && tmp != e)
break;
if (tmp || !onlyjump_p (insn))
return false;
set = single_set (insn);
if (!set || side_effects_p (set))
return false;
kill_from = insn;
#ifdef HAVE_cc0
if (reg_mentioned_p (cc0_rtx, PATTERN (insn)))
kill_from = PREV_INSN (insn);
#endif
if (can_fallthru (src, target))
{
if (rtl_dump_file)
fprintf (rtl_dump_file, "Removing jump %i.\n", INSN_UID (insn));
fallthru = 1;
delete_insn_chain (kill_from, PREV_INSN (target->head));
}
else if (simplejump_p (insn))
{
if (e->dest == target)
return false;
if (rtl_dump_file)
fprintf (rtl_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))
{
if (target == EXIT_BLOCK_PTR)
return false;
abort ();
}
}
else if (target == EXIT_BLOCK_PTR)
return false;
else
{
rtx target_label = block_label (target);
rtx barrier, tmp;
emit_jump_insn_after (gen_jump (target_label), insn);
JUMP_LABEL (src->end) = target_label;
LABEL_NUSES (target_label)++;
if (rtl_dump_file)
fprintf (rtl_dump_file, "Replacing insn %i by jump %i\n",
INSN_UID (insn), INSN_UID (src->end));
delete_insn_chain (kill_from, insn);
if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
&& (tmp = NEXT_INSN (tmp)) != NULL_RTX
&& GET_CODE (tmp) == JUMP_INSN
&& (GET_CODE (PATTERN (tmp)) == ADDR_VEC
|| GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
{
delete_insn_chain (JUMP_LABEL (insn), tmp);
}
barrier = next_nonnote_insn (src->end);
if (!barrier || GET_CODE (barrier) != BARRIER)
emit_barrier_after (src->end);
}
while (src->succ->succ_next)
remove_edge (src->succ);
e = src->succ;
if (fallthru)
e->flags = EDGE_FALLTHRU;
else
e->flags = 0;
e->probability = REG_BR_PROB_BASE;
e->count = src->count;
while (GET_CODE (e->src->end) == NOTE
&& NOTE_LINE_NUMBER (e->src->end) >= 0)
delete_insn (e->src->end);
if (e->dest != target)
redirect_edge_succ (e, target);
return true;
}
static rtx
last_loop_beg_note (insn)
rtx insn;
{
rtx last = insn;
for (insn = NEXT_INSN (insn); insn && GET_CODE (insn) == NOTE
&& 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;
}
bool
redirect_edge_and_branch (e, target)
edge e;
basic_block target;
{
rtx tmp;
rtx old_label = e->dest->head;
basic_block src = e->src;
rtx insn = src->end;
if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
return false;
if (try_redirect_by_replacing_jump (e, target))
return true;
else if (e->dest == target)
return false;
if (e->flags & EDGE_FALLTHRU)
return false;
else if (GET_CODE (insn) != JUMP_INSN)
return false;
if ((tmp = JUMP_LABEL (insn)) != NULL_RTX
&& (tmp = NEXT_INSN (tmp)) != NULL_RTX
&& GET_CODE (tmp) == JUMP_INSN
&& (GET_CODE (PATTERN (tmp)) == ADDR_VEC
|| GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC))
{
rtvec vec;
int j;
rtx new_label = block_label (target);
if (target == EXIT_BLOCK_PTR)
return false;
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 false;
if (JUMP_LABEL (insn) != old_label)
abort ();
if (!redirect_jump (insn, block_label (target), 0))
{
if (target == EXIT_BLOCK_PTR)
return false;
abort ();
}
}
if (rtl_dump_file)
fprintf (rtl_dump_file, "Edge %i->%i redirected to %i\n",
e->src->index, e->dest->index, target->index);
if (e->dest != target)
redirect_edge_succ_nodup (e, target);
return true;
}
static basic_block
force_nonfallthru_and_redirect (e, target)
edge e;
basic_block target;
{
basic_block jump_block, new_bb = NULL;
rtx note;
edge new_edge;
if (e->flags & EDGE_ABNORMAL)
abort ();
else if (!(e->flags & EDGE_FALLTHRU))
abort ();
else if (e->src == ENTRY_BLOCK_PTR)
{
edge *pe1;
basic_block bb = create_basic_block (0, e->dest->head, NULL);
e->src = bb;
bb->count = e->count;
bb->frequency = EDGE_FREQUENCY (e);
bb->loop_depth = 0;
for (pe1 = &ENTRY_BLOCK_PTR->succ; *pe1; pe1 = &(*pe1)->succ_next)
if (*pe1 == e)
{
*pe1 = e->succ_next;
break;
}
e->succ_next = 0;
bb->succ = e;
make_single_succ_edge (ENTRY_BLOCK_PTR, bb, EDGE_FALLTHRU);
}
if (e->src->succ->succ_next)
{
note = last_loop_beg_note (e->src->end);
jump_block
= create_basic_block (e->src->index + 1, NEXT_INSN (note), NULL);
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
= OBSTACK_ALLOC_REG_SET (&flow_obstack);
jump_block->global_live_at_end
= OBSTACK_ALLOC_REG_SET (&flow_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);
}
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)
{
if (HAVE_return)
emit_jump_insn_after (gen_return (), jump_block->end);
else
abort ();
}
else
{
rtx label = block_label (target);
emit_jump_insn_after (gen_jump (label), jump_block->end);
JUMP_LABEL (jump_block->end) = label;
LABEL_NUSES (label)++;
}
emit_barrier_after (jump_block->end);
redirect_edge_succ_nodup (e, target);
return new_bb;
}
basic_block
force_nonfallthru (e)
edge e;
{
return force_nonfallthru_and_redirect (e, e->dest);
}
basic_block
redirect_edge_and_branch_force (e, target)
edge e;
basic_block target;
{
if (redirect_edge_and_branch (e, target)
|| e->dest == target)
return NULL;
return force_nonfallthru_and_redirect (e, target);
}
void
tidy_fallthru_edge (e, b, c)
edge e;
basic_block b, c;
{
rtx q;
if (next_real_insn (b->end) != next_real_insn (PREV_INSN (c->head)))
return;
q = b->end;
if (GET_CODE (q) == JUMP_INSN
&& onlyjump_p (q)
&& (any_uncondjump_p (q)
|| (b->succ == e && e->succ_next == NULL)))
{
#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 (GET_CODE (q) == NOTE && NOTE_LINE_NUMBER (q) >= 0)
q = PREV_INSN (q);
}
if (q != PREV_INSN (c->head))
delete_insn_chain (NEXT_INSN (q), PREV_INSN (c->head));
e->flags |= EDGE_FALLTHRU;
}
void
tidy_fallthru_edges ()
{
int i;
for (i = 1; i < n_basic_blocks; i++)
{
basic_block b = BASIC_BLOCK (i - 1);
basic_block c = BASIC_BLOCK (i);
edge s;
if ((s = b->succ) != NULL
&& ! (s->flags & EDGE_COMPLEX)
&& s->succ_next == NULL
&& s->dest == c
&& (GET_CODE (b->end) != JUMP_INSN
|| onlyjump_p (b->end)))
tidy_fallthru_edge (s, b, c);
}
}
static bool
back_edge_of_syntactic_loop_p (bb1, bb2)
basic_block bb1, bb2;
{
rtx insn;
int count = 0;
if (bb1->index > bb2->index)
return false;
else if (bb1->index == bb2->index)
return true;
for (insn = bb1->end; insn != bb2->head && count >= 0;
insn = NEXT_INSN (insn))
if (GET_CODE (insn) == NOTE)
{
if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
count++;
else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
count--;
}
return count >= 0;
}
basic_block
split_edge (edge_in)
edge edge_in;
{
basic_block bb;
edge edge_out;
rtx before;
if ((edge_in->flags & EDGE_ABNORMAL) != 0)
abort ();
if ((edge_in->flags & EDGE_FALLTHRU) == 0)
{
edge e;
for (e = edge_in->dest->pred; e; e = e->pred_next)
if (e->flags & EDGE_FALLTHRU)
break;
if (e)
force_nonfallthru (e);
}
if (edge_in->dest != EXIT_BLOCK_PTR
&& PREV_INSN (edge_in->dest->head)
&& GET_CODE (PREV_INSN (edge_in->dest->head)) == NOTE
&& (NOTE_LINE_NUMBER (PREV_INSN (edge_in->dest->head))
== NOTE_INSN_LOOP_BEG)
&& !back_edge_of_syntactic_loop_p (edge_in->dest, edge_in->src))
before = PREV_INSN (edge_in->dest->head);
else if (edge_in->dest != EXIT_BLOCK_PTR)
before = edge_in->dest->head;
else
before = NULL_RTX;
bb = create_basic_block (edge_in->dest == EXIT_BLOCK_PTR ? n_basic_blocks
: edge_in->dest->index, before, NULL);
bb->count = edge_in->count;
bb->frequency = EDGE_FREQUENCY (edge_in);
bb->loop_depth = edge_in->dest->loop_depth;
if (edge_in->dest->global_live_at_start)
{
bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_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);
}
edge_out = make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
if ((edge_in->flags & EDGE_FALLTHRU) == 0)
{
if (!redirect_edge_and_branch (edge_in, bb))
abort ();
}
else
redirect_edge_succ (edge_in, bb);
return bb;
}
void
insert_insn_on_edge (pattern, e)
rtx pattern;
edge e;
{
if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
abort ();
if (e->insns == NULL_RTX)
start_sequence ();
else
push_to_sequence (e->insns);
emit_insn (pattern);
e->insns = get_insns ();
end_sequence ();
}
static void
commit_one_edge_insertion (e)
edge e;
{
rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last;
basic_block bb;
insns = e->insns;
e->insns = NULL_RTX;
if (e->dest->pred->pred_next == NULL
&& e->dest != EXIT_BLOCK_PTR)
{
bb = e->dest;
tmp = bb->head;
if (GET_CODE (tmp) == CODE_LABEL)
tmp = NEXT_INSN (tmp);
if (NOTE_INSN_BASIC_BLOCK_P (tmp))
tmp = NEXT_INSN (tmp);
if (tmp == bb->head)
before = tmp;
else
after = PREV_INSN (tmp);
}
else if ((e->flags & EDGE_ABNORMAL) == 0
&& e->src->succ->succ_next == NULL
&& e->src != ENTRY_BLOCK_PTR)
{
bb = e->src;
if (GET_CODE (bb->end) == JUMP_INSN)
for (before = bb->end;
GET_CODE (PREV_INSN (before)) == NOTE
&& NOTE_LINE_NUMBER (PREV_INSN (before)) == NOTE_INSN_LOOP_BEG;
before = PREV_INSN (before))
;
else
{
if ((e->flags & EDGE_FALLTHRU) == 0)
abort ();
after = bb->end;
}
}
else
{
bb = split_edge (e);
after = bb->end;
}
if (before)
{
emit_insns_before (insns, before);
last = prev_nonnote_insn (before);
}
else
last = emit_insns_after (insns, after);
if (returnjump_p (last))
{
e = bb->succ;
if (e->dest != EXIT_BLOCK_PTR
|| e->succ_next != NULL
|| (e->flags & EDGE_FALLTHRU) == 0)
abort ();
e->flags &= ~EDGE_FALLTHRU;
emit_barrier_after (last);
if (before)
delete_insn (before);
}
else if (GET_CODE (last) == JUMP_INSN)
abort ();
find_sub_basic_blocks (bb);
}
void
commit_edge_insertions ()
{
int i;
basic_block bb;
#ifdef ENABLE_CHECKING
verify_flow_info ();
#endif
i = -1;
bb = ENTRY_BLOCK_PTR;
while (1)
{
edge e, next;
for (e = bb->succ; e; e = next)
{
next = e->succ_next;
if (e->insns)
commit_one_edge_insertion (e);
}
if (++i >= n_basic_blocks)
break;
bb = BASIC_BLOCK (i);
}
}
void
dump_bb (bb, outf)
basic_block bb;
FILE *outf;
{
rtx insn;
rtx last;
edge e;
fprintf (outf, ";; Basic block %d, loop depth %d, count ",
bb->index, bb->loop_depth);
fprintf (outf, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count);
putc ('\n', outf);
fputs (";; Predecessors: ", outf);
for (e = bb->pred; e; e = e->pred_next)
dump_edge_info (outf, e, 0);
putc ('\n', outf);
fputs (";; Registers live at start:", outf);
dump_regset (bb->global_live_at_start, outf);
putc ('\n', outf);
for (insn = bb->head, last = NEXT_INSN (bb->end); insn != last;
insn = NEXT_INSN (insn))
print_rtl_single (outf, insn);
fputs (";; Registers live at end:", outf);
dump_regset (bb->global_live_at_end, outf);
putc ('\n', outf);
fputs (";; Successors: ", outf);
for (e = bb->succ; e; e = e->succ_next)
dump_edge_info (outf, e, 1);
putc ('\n', outf);
}
void
debug_bb (bb)
basic_block bb;
{
dump_bb (bb, stderr);
}
void
debug_bb_n (n)
int n;
{
dump_bb (BASIC_BLOCK (n), stderr);
}
void
print_rtl_with_bb (outf, rtx_first)
FILE *outf;
rtx rtx_first;
{
rtx tmp_rtx;
if (rtx_first == 0)
fprintf (outf, "(nil)\n");
else
{
int i;
enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
int max_uid = get_max_uid ();
basic_block *start
= (basic_block *) xcalloc (max_uid, sizeof (basic_block));
basic_block *end
= (basic_block *) xcalloc (max_uid, sizeof (basic_block));
enum bb_state *in_bb_p
= (enum bb_state *) xcalloc (max_uid, sizeof (enum bb_state));
for (i = n_basic_blocks - 1; i >= 0; i--)
{
basic_block bb = BASIC_BLOCK (i);
rtx x;
start[INSN_UID (bb->head)] = bb;
end[INSN_UID (bb->end)] = bb;
for (x = bb->head; 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)
break;
}
}
for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
{
int did_output;
basic_block bb;
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
&& GET_CODE (tmp_rtx) != NOTE
&& GET_CODE (tmp_rtx) != BARRIER)
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 (bb)
basic_block bb;
{
rtx note;
if (GET_CODE (bb->end) != JUMP_INSN)
return;
note = find_reg_note (bb->end, 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);
}
void
verify_flow_info ()
{
const int max_uid = get_max_uid ();
const rtx rtx_first = get_insns ();
rtx last_head = get_last_insn ();
basic_block *bb_info, *last_visited;
size_t *edge_checksum;
rtx x;
int i, last_bb_num_seen, num_bb_notes, err = 0;
bb_info = (basic_block *) xcalloc (max_uid, sizeof (basic_block));
last_visited = (basic_block *) xcalloc (n_basic_blocks + 2,
sizeof (basic_block));
edge_checksum = (size_t *) xcalloc (n_basic_blocks + 2, sizeof (size_t));
for (i = n_basic_blocks - 1; i >= 0; i--)
{
basic_block bb = BASIC_BLOCK (i);
rtx head = bb->head;
rtx end = bb->end;
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 (i = n_basic_blocks - 1; i >= 0; i--)
{
basic_block bb = BASIC_BLOCK (i);
int has_fallthru = 0;
edge e;
for (e = bb->succ; e; e = e->succ_next)
{
if (last_visited [e->dest->index + 2] == bb)
{
error ("verify_flow_info: Duplicate edge %i->%i",
e->src->index, e->dest->index);
err = 1;
}
last_visited [e->dest->index + 2] = bb;
if (e->flags & EDGE_FALLTHRU)
has_fallthru = 1;
if ((e->flags & EDGE_FALLTHRU)
&& e->src != ENTRY_BLOCK_PTR
&& e->dest != EXIT_BLOCK_PTR)
{
rtx insn;
if (e->src->index + 1 != e->dest->index)
{
error
("verify_flow_info: Incorrect blocks for fallthru %i->%i",
e->src->index, e->dest->index);
err = 1;
}
else
for (insn = NEXT_INSN (e->src->end); insn != e->dest->head;
insn = NEXT_INSN (insn))
if (GET_CODE (insn) == BARRIER
#ifndef CASE_DROPS_THROUGH
|| INSN_P (insn)
#else
|| (INSN_P (insn) && ! JUMP_TABLE_DATA_P (insn))
#endif
)
{
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;
}
}
if (e->src != bb)
{
error ("verify_flow_info: Basic block %d succ edge is corrupted",
bb->index);
fprintf (stderr, "Predecessor: ");
dump_edge_info (stderr, e, 0);
fprintf (stderr, "\nSuccessor: ");
dump_edge_info (stderr, e, 1);
fprintf (stderr, "\n");
err = 1;
}
edge_checksum[e->dest->index + 2] += (size_t) e;
}
if (!has_fallthru)
{
rtx insn;
for (insn = bb->end; !insn || GET_CODE (insn) != BARRIER;
insn = NEXT_INSN (insn))
if (!insn
|| (GET_CODE (insn) == NOTE
&& NOTE_LINE_NUMBER (insn) == NOTE_INSN_BASIC_BLOCK))
{
error ("missing barrier after block %i", bb->index);
err = 1;
break;
}
}
for (e = bb->pred; e; e = e->pred_next)
{
if (e->dest != bb)
{
error ("basic block %d pred edge is corrupted", bb->index);
fputs ("Predecessor: ", stderr);
dump_edge_info (stderr, e, 0);
fputs ("\nSuccessor: ", stderr);
dump_edge_info (stderr, e, 1);
fputc ('\n', stderr);
err = 1;
}
edge_checksum[e->dest->index + 2] -= (size_t) e;
}
for (x = bb->head; x != NEXT_INSN (bb->end); x = NEXT_INSN (x))
if (basic_block_for_insn && 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;
if (GET_CODE (x) == CODE_LABEL)
{
if (bb->end == 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 == 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)
break;
if (GET_CODE (x) == JUMP_INSN
|| GET_CODE (x) == CODE_LABEL
|| GET_CODE (x) == BARRIER)
{
error ("in basic block %d:", bb->index);
fatal_insn ("flow control insn inside a basic block", x);
}
}
}
{
edge e;
for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next)
edge_checksum[e->dest->index + 2] += (size_t) e;
for (e = EXIT_BLOCK_PTR->pred; e ; e = e->pred_next)
edge_checksum[e->dest->index + 2] -= (size_t) e;
}
for (i = -2; i < n_basic_blocks; ++i)
if (edge_checksum[i + 2])
{
error ("basic block %i edge lists are corrupted", i);
err = 1;
}
last_bb_num_seen = -1;
num_bb_notes = 0;
for (x = rtx_first; x; x = NEXT_INSN (x))
{
if (NOTE_INSN_BASIC_BLOCK_P (x))
{
basic_block bb = NOTE_BASIC_BLOCK (x);
num_bb_notes++;
if (bb->index != last_bb_num_seen + 1)
internal_error ("basic blocks not numbered consecutively");
last_bb_num_seen = bb->index;
}
if (!bb_info[INSN_UID (x)])
{
switch (GET_CODE (x))
{
case BARRIER:
case NOTE:
break;
case CODE_LABEL:
if (NEXT_INSN (x)
&& GET_CODE (NEXT_INSN (x)) == JUMP_INSN
&& (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 (INSN_P (x)
&& GET_CODE (x) == JUMP_INSN
&& returnjump_p (x) && ! condjump_p (x)
&& ! (NEXT_INSN (x) && GET_CODE (NEXT_INSN (x)) == BARRIER))
fatal_insn ("return not followed by barrier", x);
}
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);
if (err)
internal_error ("verify_flow_info failed");
free (bb_info);
free (last_visited);
free (edge_checksum);
}
bool
purge_dead_edges (bb)
basic_block bb;
{
edge e, next;
rtx insn = bb->end, note;
bool purged = false;
if (GET_CODE (insn) == 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);
}
if (! can_throw_internal (bb->end))
for (e = bb->succ; e; e = next)
{
next = e->succ_next;
if (e->flags & EDGE_EH)
{
remove_edge (e);
purged = true;
}
}
if (GET_CODE (insn) == JUMP_INSN)
{
rtx note;
edge b,f;
if (!any_condjump_p (insn)
&& !returnjump_p (insn)
&& !simplejump_p (insn))
return false;
for (e = bb->succ; e; e = next)
{
next = e->succ_next;
e->flags &= ~EDGE_ABNORMAL;
if ((e->flags & EDGE_FALLTHRU)
&& any_condjump_p (insn))
continue;
else if (e->dest != EXIT_BLOCK_PTR
&& e->dest->head == JUMP_LABEL (insn))
continue;
else if (e->dest == EXIT_BLOCK_PTR
&& returnjump_p (insn))
continue;
purged = true;
remove_edge (e);
}
if (!bb->succ || !purged)
return false;
if (rtl_dump_file)
fprintf (rtl_dump_file, "Purged edges from bb %i\n", bb->index);
if (!optimize)
return purged;
if (!bb->succ->succ_next)
{
bb->succ->probability = REG_BR_PROB_BASE;
bb->succ->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;
}
for (e = bb->succ; e && (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU));
e = e->succ_next)
;
if (!e)
return purged;
for (e = bb->succ; e; e = next)
{
next = e->succ_next;
if (!(e->flags & EDGE_FALLTHRU))
remove_edge (e), purged = true;
}
if (!bb->succ || bb->succ->succ_next)
abort ();
bb->succ->probability = REG_BR_PROB_BASE;
bb->succ->count = bb->count;
if (rtl_dump_file)
fprintf (rtl_dump_file, "Purged non-fallthru edges from bb %i\n",
bb->index);
return purged;
}
bool
purge_all_dead_edges (update_life_p)
int update_life_p;
{
int i, purged = false;
sbitmap blocks = 0;
if (update_life_p)
{
blocks = sbitmap_alloc (n_basic_blocks);
sbitmap_zero (blocks);
}
for (i = 0; i < n_basic_blocks; i++)
{
bool purged_here = purge_dead_edges (BASIC_BLOCK (i));
purged |= purged_here;
if (purged_here && update_life_p)
SET_BIT (blocks, i);
}
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;
}