/* Control flow graph manipulation code for GNU compiler.
Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
- 1999, 2000, 2001 Free Software Foundation, Inc.
+ 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
This file is part of GCC.
#include "toplev.h"
#include "tm_p.h"
#include "obstack.h"
+#include "insn-config.h"
/* Stubs in case we don't have a return insn. */
#ifndef HAVE_return
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 void commit_one_edge_insertion PARAMS ((edge, int));
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));
/* User declared labels must be preserved. */
&& LABEL_NAME (label) == 0
&& !in_expr_list_p (forced_labels, label)
- && !in_expr_list_p (label_value_list, label)
- && !in_expr_list_p (exception_handler_labels, label));
+ && !in_expr_list_p (label_value_list, label));
}
/* Delete INSN by patching it out. Return the next insn. */
if (really_delete)
{
+ /* If this insn has already been deleted, something is very wrong. */
+ if (INSN_DELETED_P (insn))
+ abort ();
remove_insn (insn);
INSN_DELETED_P (insn) = 1;
}
int i;
for (i = 0; i < len; i++)
- LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0))--;
+ {
+ rtx label = XEXP (XVECEXP (pat, diff_vec_p, i), 0);
+
+ /* When deleting code in bulk (e.g. removing many unreachable
+ blocks) we can delete a label that's a target of the vector
+ before deleting the vector itself. */
+ if (GET_CODE (label) != NOTE)
+ LABEL_NUSES (label)--;
+ }
}
return next;
}
+/* Like delete_insn but also purge dead edges from BB. */
+rtx
+delete_insn_and_edges (insn)
+ rtx insn;
+{
+ rtx x;
+ bool purge = false;
+
+ if (basic_block_for_insn
+ && INSN_P (insn)
+ && (unsigned int)INSN_UID (insn) < basic_block_for_insn->num_elements
+ && BLOCK_FOR_INSN (insn)
+ && BLOCK_FOR_INSN (insn)->end == insn)
+ purge = true;
+ x = delete_insn (insn);
+ if (purge)
+ purge_dead_edges (BLOCK_FOR_INSN (insn));
+ return x;
+}
+
/* Unlink a chain of insns between START and FINISH, leaving notes
that must be paired. */
start = next;
}
}
+
+/* Like delete_insn but also purge dead edges from BB. */
+void
+delete_insn_chain_and_edges (first, last)
+ rtx first, last;
+{
+ bool purge = false;
+
+ if (basic_block_for_insn
+ && INSN_P (last)
+ && (unsigned int)INSN_UID (last) < basic_block_for_insn->num_elements
+ && BLOCK_FOR_INSN (last)
+ && BLOCK_FOR_INSN (last)->end == last)
+ purge = true;
+ delete_insn_chain (first, last);
+ if (purge)
+ purge_dead_edges (BLOCK_FOR_INSN (last));
+}
\f
/* Create a new basic block consisting of the instructions between HEAD and END
inclusive. This function is designed to allow fast BB construction - reuses
bb->head = head;
bb->end = end;
bb->index = index;
+ bb->flags = BB_NEW;
BASIC_BLOCK (index) = bb;
if (basic_block_for_insn)
update_bb_for_insn (bb);
to post-process the stream to remove empty blocks, loops, ranges, etc. */
int
-flow_delete_block (b)
+flow_delete_block_noexpunge (b)
basic_block b;
{
int deleted_handler = 0;
insn = b->head;
- never_reached_warning (insn);
+ never_reached_warning (insn, b->end);
if (GET_CODE (insn) == CODE_LABEL)
maybe_remove_eh_handler (insn);
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);
+
/* Remove the basic block from the array, and compact behind it. */
expunge_block (b);
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
+ /* In the presence of conditional execution we are not able to update
+ liveness precisely. */
+ if (reload_completed)
+ {
+ bb->flags |= BB_DIRTY;
+ new_bb->flags |= BB_DIRTY;
+ }
+#endif
}
return new_edge;
for (e = b->succ; e; e = e->succ_next)
e->src = a;
a->succ = b->succ;
+ a->flags |= b->flags;
/* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */
b->pred = b->succ = NULL;
rtx x;
for (x = a_end; x != b_end; x = NEXT_INSN (x))
- BLOCK_FOR_INSN (x) = a;
+ set_block_for_insn (x, a);
- BLOCK_FOR_INSN (b_end) = a;
+ set_block_for_insn (b_end, a);
}
a_end = b_end;
if (rtl_dump_file)
fprintf (rtl_dump_file, "Redirecting jump %i from %i to %i.\n",
INSN_UID (insn), e->dest->index, target->index);
- redirect_jump (insn, block_label (target), 0);
+ if (!redirect_jump (insn, block_label (target), 0))
+ {
+ if (target == EXIT_BLOCK_PTR)
+ return false;
+ abort ();
+ }
}
+ /* Cannot do anything for target exit block. */
+ else if (target == EXIT_BLOCK_PTR)
+ return false;
+
/* Or replace possibly complicated jump insn by simple jump insn. */
else
{
rtx target_label = block_label (target);
- rtx barrier;
+ rtx barrier, tmp;
emit_jump_insn_after (gen_jump (target_label), insn);
JUMP_LABEL (src->end) = target_label;
fprintf (rtl_dump_file, "Replacing insn %i by jump %i\n",
INSN_UID (insn), INSN_UID (src->end));
+
delete_insn_chain (kill_from, insn);
+ /* Recognize a tablejump that we are converting to a
+ simple jump and remove its associated CODE_LABEL
+ and ADDR_VEC or ADDR_DIFF_VEC. */
+ 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);
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
return false;
/* If the insn doesn't go where we think, we're confused. */
- if (JUMP_LABEL (insn) != old_label
- /* If the substitution doesn't succeed, die. This can happen
- if the back end emitted unrecognizable instructions. */
- || !redirect_jump (insn, block_label (target), 0))
+ if (JUMP_LABEL (insn) != old_label)
abort ();
+
+ /* If the substitution doesn't succeed, die. This can happen
+ if the back end emitted unrecognizable instructions or if
+ target is exit block on some arches. */
+ if (!redirect_jump (insn, block_label (target), 0))
+ {
+ if (target == EXIT_BLOCK_PTR)
+ return false;
+ abort ();
+ }
}
if (rtl_dump_file)
abort ();
else if (!(e->flags & EDGE_FALLTHRU))
abort ();
- else if (e->src->succ->succ_next)
+ else if (e->src == ENTRY_BLOCK_PTR)
+ {
+ /* We can't redirect the entry block. Create an empty block at the
+ start of the function which we use to add the new jump. */
+ edge *pe1;
+ basic_block bb = create_basic_block (0, e->dest->head, NULL);
+
+ /* Change the existing edge's source to be the new block, and add
+ a new edge from the entry block to the new block. */
+ e->src = bb;
+ 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)
{
/* Create the new structures. */
note = last_loop_beg_note (e->src->end);
/* Update the CFG for the instructions queued on edge E. */
static void
-commit_one_edge_insertion (e)
+commit_one_edge_insertion (e, watch_calls)
edge e;
+ int watch_calls;
{
rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last;
basic_block bb;
insns = e->insns;
e->insns = NULL_RTX;
- /* Figure out where to put these things. If the destination has
- one predecessor, insert there. Except for the exit block. */
- if (e->dest->pred->pred_next == NULL
- && e->dest != EXIT_BLOCK_PTR)
+ /* Special case -- avoid inserting code between call and storing
+ its return value. */
+ if (watch_calls && (e->flags & EDGE_FALLTHRU) && !e->dest->pred->pred_next
+ && e->src != ENTRY_BLOCK_PTR
+ && GET_CODE (e->src->end) == CALL_INSN)
{
+ rtx next = next_nonnote_insn (e->src->end);
+
+ after = e->dest->head;
+ /* The first insn after the call may be a stack pop, skip it. */
+ while (next
+ && keep_with_call_p (next))
+ {
+ after = next;
+ next = next_nonnote_insn (next);
+ }
bb = e->dest;
-
- /* Get the location correct wrt a code label, and "nice" wrt
- a basic block note, and before everything else. */
- 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);
}
-
- /* If the source has one successor and the edge is not abnormal,
- insert there. Except for the entry block. */
- else if ((e->flags & EDGE_ABNORMAL) == 0
- && e->src->succ->succ_next == NULL
- && e->src != ENTRY_BLOCK_PTR)
+ if (!before && !after)
{
- bb = e->src;
-
- /* It is possible to have a non-simple jump here. Consider a target
- where some forms of unconditional jumps clobber a register. This
- happens on the fr30 for example.
-
- We know this block has a single successor, so we can just emit
- the queued insns before the jump. */
- 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
+ /* Figure out where to put these things. If the destination has
+ one predecessor, insert there. Except for the exit block. */
+ if (e->dest->pred->pred_next == NULL && e->dest != EXIT_BLOCK_PTR)
+ {
+ bb = e->dest;
+
+ /* Get the location correct wrt a code label, and "nice" wrt
+ a basic block note, and before everything else. */
+ 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 if (tmp)
+ after = PREV_INSN (tmp);
+ else
+ after = get_last_insn ();
+ }
+
+ /* If the source has one successor and the edge is not abnormal,
+ insert there. Except for the entry block. */
+ else if ((e->flags & EDGE_ABNORMAL) == 0
+ && e->src->succ->succ_next == NULL
+ && e->src != ENTRY_BLOCK_PTR)
{
- /* We'd better be fallthru, or we've lost track of what's what. */
- if ((e->flags & EDGE_FALLTHRU) == 0)
- abort ();
+ bb = e->src;
+
+ /* It is possible to have a non-simple jump here. Consider a target
+ where some forms of unconditional jumps clobber a register. This
+ happens on the fr30 for example.
+
+ We know this block has a single successor, so we can just emit
+ the queued insns before the jump. */
+ 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
+ {
+ /* We'd better be fallthru, or we've lost track of what's what. */
+ if ((e->flags & EDGE_FALLTHRU) == 0)
+ abort ();
+ after = bb->end;
+ }
+ }
+ /* Otherwise we must split the edge. */
+ else
+ {
+ bb = split_edge (e);
after = bb->end;
}
}
- /* Otherwise we must split the edge. */
- else
- {
- bb = split_edge (e);
- after = bb->end;
- }
-
/* Now that we've found the spot, do the insertion. */
if (before)
{
/* ??? Remove all outgoing edges from BB and add one for EXIT.
This is not currently a problem because this only happens
- for the (single) epilogue, which already has a fallthru edge
- to EXIT. */
+ for the (single) epilogue, which already has a fallthru edge
+ to EXIT. */
e = bb->succ;
if (e->dest != EXIT_BLOCK_PTR
- || e->succ_next != NULL
- || (e->flags & EDGE_FALLTHRU) == 0)
+ || e->succ_next != NULL || (e->flags & EDGE_FALLTHRU) == 0)
abort ();
e->flags &= ~EDGE_FALLTHRU;
{
next = e->succ_next;
if (e->insns)
- commit_one_edge_insertion (e);
+ commit_one_edge_insertion (e, false);
+ }
+
+ if (++i >= n_basic_blocks)
+ break;
+ bb = BASIC_BLOCK (i);
+ }
+}
+\f
+/* Update the CFG for all queued instructions, taking special care of inserting
+ code on edges between call and storing its return value. */
+
+void
+commit_edge_insertions_watch_calls ()
+{
+ 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, true);
}
if (++i >= n_basic_blocks)
}
}
\f
+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);
+}
+\f
/* Verify the CFG consistency. This function check some CFG invariants and
aborts when something is wrong. Hope that this function will help to
convert many optimization passes to preserve CFG consistent.
for (i = n_basic_blocks - 1; i >= 0; i--)
{
basic_block bb = BASIC_BLOCK (i);
- int has_fallthru = 0;
+ int n_fallthru = 0, n_eh = 0, n_call = 0, n_abnormal = 0, n_branch = 0;
edge e;
+ rtx note;
+ if (INSN_P (bb->end)
+ && (note = find_reg_note (bb->end, REG_BR_PROB, NULL_RTX))
+ && any_condjump_p (bb->end))
+ {
+ if (INTVAL (XEXP (note, 0)) != BRANCH_EDGE (bb)->probability)
+ {
+ error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
+ INTVAL (XEXP (note, 0)), BRANCH_EDGE (bb)->probability);
+ err = 1;
+ }
+ }
+ if (bb->count < 0)
+ {
+ error ("verify_flow_info: Wrong count of block %i %i",
+ bb->index, (int)bb->count);
+ err = 1;
+ }
+ if (bb->frequency < 0)
+ {
+ error ("verify_flow_info: Wrong frequency of block %i %i",
+ bb->index, bb->frequency);
+ err = 1;
+ }
for (e = bb->succ; e; e = e->succ_next)
{
if (last_visited [e->dest->index + 2] == bb)
e->src->index, e->dest->index);
err = 1;
}
+ if (e->probability < 0 || e->probability > REG_BR_PROB_BASE)
+ {
+ error ("verify_flow_info: Wrong probability of edge %i->%i %i",
+ e->src->index, e->dest->index, e->probability);
+ err = 1;
+ }
+ if (e->count < 0)
+ {
+ error ("verify_flow_info: Wrong count of edge %i->%i %i",
+ e->src->index, e->dest->index, (int)e->count);
+ err = 1;
+ }
last_visited [e->dest->index + 2] = bb;
if (e->flags & EDGE_FALLTHRU)
- has_fallthru = 1;
+ n_fallthru++;
+
+ if ((e->flags & ~EDGE_DFS_BACK) == 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 ((e->flags & EDGE_FALLTHRU)
&& e->src != ENTRY_BLOCK_PTR
edge_checksum[e->dest->index + 2] += (size_t) e;
}
- if (!has_fallthru)
+ if (n_eh && GET_CODE (PATTERN (bb->end)) != RESX
+ && !find_reg_note (bb->end, REG_EH_REGION, NULL_RTX))
+ {
+ error ("Missing REG_EH_REGION note in the end of bb %i", bb->index);
+ err = 1;
+ }
+ if (n_branch
+ && (GET_CODE (bb->end) != JUMP_INSN
+ || (n_branch > 1 && (any_uncondjump_p (bb->end)
+ || any_condjump_p (bb->end)))))
+ {
+ error ("Too many outgoing branch edges from bb %i", bb->index);
+ err = 1;
+ }
+ if (n_fallthru && any_uncondjump_p (bb->end))
+ {
+ error ("Fallthru edge after unconditional jump %i", bb->index);
+ err = 1;
+ }
+ if (n_branch != 1 && any_uncondjump_p (bb->end))
+ {
+ error ("Wrong amount of branch edges after unconditional jump %i", bb->index);
+ err = 1;
+ }
+ if (n_branch != 1 && any_condjump_p (bb->end)
+ && JUMP_LABEL (bb->end) != BASIC_BLOCK (bb->index + 1)->head)
+ {
+ error ("Wrong amount of branch edges after conditional jump %i", bb->index);
+ err = 1;
+ }
+ if (n_call && GET_CODE (bb->end) != CALL_INSN)
+ {
+ error ("Call edges for non-call insn in bb %i", bb->index);
+ err = 1;
+ }
+ if (n_abnormal
+ && (GET_CODE (bb->end) != CALL_INSN && n_call != n_abnormal)
+ && (GET_CODE (bb->end) != JUMP_INSN
+ || any_condjump_p (bb->end)
+ || any_uncondjump_p (bb->end)))
+ {
+ error ("Abnormal edges for no purpose in bb %i", bb->index);
+ err = 1;
+ }
+
+ if (!n_fallthru)
{
rtx insn;
rtx insn = bb->end, note;
bool purged = false;
- /* ??? This makes no sense since the later test includes more cases. */
- if (GET_CODE (insn) == JUMP_INSN && !simplejump_p (insn))
- return false;
+ /* If this instruction cannot trap, remove REG_EH_REGION notes. */
+ 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);
+ }
+
+ /* Cleanup abnormal edges caused by throwing insns that have been
+ eliminated. */
+ 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);
+ bb->flags |= BB_DIRTY;
+ purged = true;
+ }
+ }
if (GET_CODE (insn) == JUMP_INSN)
{
if (!any_condjump_p (insn)
&& !returnjump_p (insn)
&& !simplejump_p (insn))
- return false;
+ return purged;
+
+ /* Branch probability/prediction notes are defined only for
+ condjumps. We've possibly turned condjump into simplejump. */
+ 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 (e = bb->succ; e; e = next)
{
&& returnjump_p (insn))
continue;
+ bb->flags |= BB_DIRTY;
purged = true;
remove_edge (e);
}
if (!bb->succ || !purged)
- return false;
+ return purged;
if (rtl_dump_file)
fprintf (rtl_dump_file, "Purged edges from bb %i\n", bb->index);
return purged;
}
- /* If this instruction cannot trap, remove REG_EH_REGION notes. */
- 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);
- }
-
- /* Cleanup abnormal edges caused by throwing insns that have been
- eliminated. */
- 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 we don't see a jump insn, we don't know exactly why the block would
have been broken at this point. Look for a simple, non-fallthru edge,
as these are only created by conditional branches. If we find such an
{
next = e->succ_next;
if (!(e->flags & EDGE_FALLTHRU))
- remove_edge (e), purged = true;
+ {
+ bb->flags |= BB_DIRTY;
+ remove_edge (e);
+ purged = true;
+ }
}
if (!bb->succ || bb->succ->succ_next)
OSDN Git Service
