/* Control flow graph manipulation code for GNU compiler.
Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
- 1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
+ 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
+ Free Software Foundation, Inc.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
-Software Foundation; either version 2, or (at your option) any later
+Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
for more details.
You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
-02110-1301, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
/* This file contains low level functions to manipulate the CFG and analyze it
that are aware of the RTL intermediate language.
#include "cfgloop.h"
#include "ggc.h"
#include "tree-pass.h"
+#include "df.h"
static int can_delete_note_p (rtx);
static int can_delete_label_p (rtx);
}
/* Unlink a chain of insns between START and FINISH, leaving notes
- that must be paired. */
+ that must be paired. If CLEAR_BB is true, we set bb field for
+ insns that cannot be removed to NULL. */
void
-delete_insn_chain (rtx start, rtx finish)
+delete_insn_chain (rtx start, rtx finish, bool clear_bb)
{
rtx next;
else
next = delete_insn (start);
+ if (clear_bb && !INSN_DELETED_P (start))
+ set_block_for_insn (start, NULL);
+
if (start == finish)
break;
start = next;
}
}
-
-/* Like delete_insn but also purge dead edges from BB. */
-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));
-}
\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->flags = BB_NEW | BB_RTL;
link_block (bb, after);
SET_BASIC_BLOCK (bb->index, bb);
+ df_bb_refs_record (bb->index, false);
update_bb_for_insn (bb);
BB_SET_PARTITION (bb, BB_UNPARTITIONED);
/* Selectively delete the entire chain. */
BB_HEAD (b) = NULL;
- delete_insn_chain (insn, end);
- if (b->il.rtl->global_live_at_start)
- {
- FREE_REG_SET (b->il.rtl->global_live_at_start);
- FREE_REG_SET (b->il.rtl->global_live_at_end);
- b->il.rtl->global_live_at_start = NULL;
- b->il.rtl->global_live_at_end = NULL;
- }
+ delete_insn_chain (insn, end, true);
+
+
+ if (dump_file)
+ fprintf (dump_file, "deleting block %d\n", b->index);
+ df_bb_delete (b->index);
}
\f
/* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
{
if (!BARRIER_P (insn))
- set_block_for_insn (insn, bb);
+ {
+ set_block_for_insn (insn, bb);
+ df_insn_change_bb (insn);
+ }
if (insn == BB_END (bb))
break;
}
}
\f
+/* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
+ note associated with the BLOCK. */
+
+static rtx
+first_insn_after_basic_block_note (basic_block block)
+{
+ rtx insn;
+
+ /* Get the first instruction in the block. */
+ insn = BB_HEAD (block);
+
+ if (insn == NULL_RTX)
+ return NULL_RTX;
+ if (LABEL_P (insn))
+ insn = NEXT_INSN (insn);
+ gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
+
+ return NEXT_INSN (insn);
+}
+
/* Creates a new basic block just after basic block B by splitting
everything after specified instruction I. */
FOR_EACH_EDGE (e, ei, new_bb->succs)
e->src = new_bb;
- if (bb->il.rtl->global_live_at_start)
- {
- new_bb->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack);
- new_bb->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack);
- COPY_REG_SET (new_bb->il.rtl->global_live_at_end, bb->il.rtl->global_live_at_end);
-
- /* We now have to calculate which registers are live at the end
- of the split basic block and at the start of the new basic
- block. Start with those registers that are known to be live
- at the end of the original basic block and get
- propagate_block to determine which registers are live. */
- COPY_REG_SET (new_bb->il.rtl->global_live_at_start, bb->il.rtl->global_live_at_end);
- propagate_block (new_bb, new_bb->il.rtl->global_live_at_start, NULL, NULL, 0);
- COPY_REG_SET (bb->il.rtl->global_live_at_end,
- new_bb->il.rtl->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
- }
-
+ /* The new block starts off being dirty. */
+ df_set_bb_dirty (bb);
return new_bb;
}
rtx del_first = NULL_RTX, del_last = NULL_RTX;
int b_empty = 0;
+ if (dump_file)
+ fprintf (dump_file, "merging block %d into block %d\n", b->index, a->index);
+
/* If there was a CODE_LABEL beginning B, delete it. */
if (LABEL_P (b_head))
{
/* Delete everything marked above as well as crap that might be
hanging out between the two blocks. */
BB_HEAD (b) = NULL;
- delete_insn_chain (del_first, del_last);
+ delete_insn_chain (del_first, del_last, true);
/* Reassociate the insns of B with A. */
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 (x, a);
+ df_insn_change_bb (x);
+ }
set_block_for_insn (b_end, a);
+ df_insn_change_bb (b_end);
a_end = b_end;
}
+ df_bb_delete (b->index);
BB_END (a) = a_end;
- a->il.rtl->global_live_at_end = b->il.rtl->global_live_at_end;
}
+
/* Return true when block A and B can be merged. */
static bool
rtl_can_merge_blocks (basic_block a,basic_block b)
{
rtx insn = src->il.rtl->footer;
- delete_insn_chain (kill_from, BB_END (src));
+ delete_insn_chain (kill_from, BB_END (src), false);
/* Remove barriers but keep jumptables. */
while (insn)
}
}
else
- delete_insn_chain (kill_from, PREV_INSN (BB_HEAD (target)));
+ delete_insn_chain (kill_from, PREV_INSN (BB_HEAD (target)),
+ false);
}
/* If this already is simplejump, redirect it. */
INSN_UID (insn), INSN_UID (BB_END (src)));
- delete_insn_chain (kill_from, insn);
+ delete_insn_chain (kill_from, insn, false);
/* 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 (tablejump_p (insn, &label, &table))
- delete_insn_chain (label, table);
+ delete_insn_chain (label, table, false);
barrier = next_nonnote_insn (BB_END (src));
if (!barrier || !BARRIER_P (barrier))
for (tmp = NEXT_INSN (BB_END (src)); tmp != barrier;
tmp = NEXT_INSN (tmp))
- set_block_for_insn (tmp, src);
+ {
+ set_block_for_insn (tmp, src);
+ df_insn_change_bb (tmp);
+ }
NEXT_INSN (PREV_INSN (new_insn)) = NEXT_INSN (new_insn);
PREV_INSN (NEXT_INSN (new_insn)) = PREV_INSN (new_insn);
if (e->dest != target)
redirect_edge_succ (e, target);
-
return e;
}
if (e->dest != target)
e = redirect_edge_succ_nodup (e, target);
+
return e;
}
if ((ret = try_redirect_by_replacing_jump (e, target, false)) != NULL)
{
- src->flags |= BB_DIRTY;
+ df_set_bb_dirty (src);
return ret;
}
if (!ret)
return NULL;
- src->flags |= BB_DIRTY;
+ df_set_bb_dirty (src);
return ret;
}
jump_block->frequency = EDGE_FREQUENCY (e);
jump_block->loop_depth = target->loop_depth;
- if (target->il.rtl->global_live_at_start)
- {
- jump_block->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack);
- jump_block->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack);
- COPY_REG_SET (jump_block->il.rtl->global_live_at_start,
- target->il.rtl->global_live_at_start);
- COPY_REG_SET (jump_block->il.rtl->global_live_at_end,
- target->il.rtl->global_live_at_start);
- }
-
/* Make sure new block ends up in correct hot/cold section. */
BB_COPY_PARTITION (jump_block, e->src);
if (abnormal_edge_flags)
make_edge (src, target, abnormal_edge_flags);
+ df_mark_solutions_dirty ();
return new_bb;
}
/* In case the edge redirection failed, try to force it to be non-fallthru
and redirect newly created simplejump. */
- e->src->flags |= BB_DIRTY;
+ df_set_bb_dirty (e->src);
return force_nonfallthru_and_redirect (e, target);
}
/* Selectively unlink the sequence. */
if (q != PREV_INSN (BB_HEAD (c)))
- delete_insn_chain (NEXT_INSN (q), PREV_INSN (BB_HEAD (c)));
+ delete_insn_chain (NEXT_INSN (q), PREV_INSN (BB_HEAD (c)), false);
e->flags |= EDGE_FALLTHRU;
}
BB_COPY_PARTITION (bb, edge_in->dest);
}
- /* ??? This info is likely going to be out of date very soon. */
- if (edge_in->dest->il.rtl->global_live_at_start)
- {
- bb->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack);
- bb->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack);
- COPY_REG_SET (bb->il.rtl->global_live_at_start,
- edge_in->dest->il.rtl->global_live_at_start);
- COPY_REG_SET (bb->il.rtl->global_live_at_end,
- edge_in->dest->il.rtl->global_live_at_start);
- }
-
make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
/* For non-fallthru edges, we must adjust the predecessor's
if (before)
{
- emit_insn_before_noloc (insns, before);
+ emit_insn_before_noloc (insns, before, bb);
last = prev_nonnote_insn (before);
}
else
- last = emit_insn_after_noloc (insns, after);
+ last = emit_insn_after_noloc (insns, after, bb);
if (returnjump_p (last))
{
sbitmap_free (blocks);
}
\f
+
/* Print out RTL-specific basic block information (live information
at start and end). */
s_indent = (char *) 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->il.rtl->global_live_at_start, outf);
- putc ('\n', outf);
+
+ if (df)
+ {
+ df_dump_top (bb, 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->il.rtl->global_live_at_end, outf);
- putc ('\n', outf);
+ if (df)
+ {
+ df_dump_bottom (bb, outf);
+ putc ('\n', outf);
+ }
+
}
\f
/* Like print_rtl, but also print out live information for the start of each
print_rtl_with_bb (FILE *outf, rtx rtx_first)
{
rtx tmp_rtx;
-
if (rtx_first == 0)
fprintf (outf, "(nil)\n");
else
basic_block bb;
+ if (df)
+ df_dump_start (outf);
+
FOR_EACH_BB_REVERSE (bb)
{
rtx x;
for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
{
int did_output;
- edge_iterator ei;
- edge e;
-
if ((bb = start[INSN_UID (tmp_rtx)]) != NULL)
{
- fprintf (outf, ";; Start of basic block %d, registers live:",
- bb->index);
- dump_regset (bb->il.rtl->global_live_at_start, outf);
- putc ('\n', outf);
+ edge e;
+ edge_iterator ei;
+
+ fprintf (outf, ";; Start of basic block (");
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ fprintf (outf, " %d", e->src->index);
+ fprintf (outf, ") -> %d\n", bb->index);
+
+ if (df)
+ {
+ df_dump_top (bb, outf);
+ putc ('\n', outf);
+ }
FOR_EACH_EDGE (e, ei, bb->preds)
{
fputs (";; Pred edge ", outf);
if ((bb = end[INSN_UID (tmp_rtx)]) != NULL)
{
- fprintf (outf, ";; End of basic block %d, registers live:",
- bb->index);
- dump_regset (bb->il.rtl->global_live_at_end, outf);
+ edge e;
+ edge_iterator ei;
+
+ fprintf (outf, ";; End of basic block %d -> (", bb->index);
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ fprintf (outf, " %d", e->dest->index);
+ fprintf (outf, ")\n");
+
+ if (df)
+ {
+ df_dump_bottom (bb, outf);
+ putc ('\n', outf);
+ }
putc ('\n', outf);
FOR_EACH_EDGE (e, ei, bb->succs)
{
fputc ('\n', outf);
}
}
-
if (did_output)
putc ('\n', outf);
}
bb->index);
err = 1;
}
+
+ for (insn = bb->il.rtl->header; insn; insn = NEXT_INSN (insn))
+ if (!BARRIER_P (insn)
+ && BLOCK_FOR_INSN (insn) != NULL)
+ {
+ error ("insn %d in header of bb %d has non-NULL basic block",
+ INSN_UID (insn), bb->index);
+ err = 1;
+ }
+ for (insn = bb->il.rtl->footer; insn; insn = NEXT_INSN (insn))
+ if (!BARRIER_P (insn)
+ && BLOCK_FOR_INSN (insn) != NULL)
+ {
+ error ("insn %d in footer of bb %d has non-NULL basic block",
+ INSN_UID (insn), bb->index);
+ err = 1;
+ }
}
/* Now check the basic blocks (boundaries etc.) */
rtx head = BB_HEAD (bb);
rtx end = BB_END (bb);
- /* Verify the end of the basic block is in the INSN chain. */
for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
- if (x == end)
- break;
+ {
+ /* Verify the end of the basic block is in the INSN chain. */
+ if (x == end)
+ break;
+
+ /* And that the code outside of basic blocks has NULL bb field. */
+ if (!BARRIER_P (x)
+ && BLOCK_FOR_INSN (x) != NULL)
+ {
+ error ("insn %d outside of basic blocks has non-NULL bb field",
+ INSN_UID (x));
+ err = 1;
+ }
+ }
if (!x)
{
err = 1;
}
- last_head = x;
+ last_head = PREV_INSN (x);
FOR_EACH_EDGE (e, ei, bb->succs)
if (e->flags & EDGE_FALLTHRU)
}
}
+ for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
+ {
+ /* Check that the code before the first basic block has NULL
+ bb field. */
+ if (!BARRIER_P (x)
+ && BLOCK_FOR_INSN (x) != NULL)
+ {
+ error ("insn %d outside of basic blocks has non-NULL bb field",
+ INSN_UID (x));
+ err = 1;
+ }
+ }
free (bb_info);
num_bb_notes = 0;
}
remove_edge (e);
- bb->flags |= BB_DIRTY;
+ df_set_bb_dirty (bb);
purged = true;
}
}
/* We do not need this edge. */
- bb->flags |= BB_DIRTY;
+ df_set_bb_dirty (bb);
purged = true;
remove_edge (e);
}
{
if (!(e->flags & (EDGE_FALLTHRU | EDGE_FAKE)))
{
- bb->flags |= BB_DIRTY;
+ df_set_bb_dirty (bb);
remove_edge (e);
purged = true;
}
return new_bb;
}
-
/* Redirect Edge to DEST. */
static edge
cfg_layout_redirect_edge_and_branch (edge e, basic_block dest)
if (e->src != ENTRY_BLOCK_PTR
&& (ret = try_redirect_by_replacing_jump (e, dest, true)))
{
- src->flags |= BB_DIRTY;
+ df_set_bb_dirty (src);
return ret;
}
fprintf (dump_file, "Redirecting entry edge from bb %i to %i\n",
e->src->index, dest->index);
- e->src->flags |= BB_DIRTY;
+ df_set_bb_dirty (e->src);
redirect_edge_succ (e, dest);
return e;
}
redirected = redirect_branch_edge (e, dest);
gcc_assert (redirected);
e->flags |= EDGE_FALLTHRU;
- e->src->flags |= BB_DIRTY;
+ df_set_bb_dirty (e->src);
return e;
}
/* In case we are redirecting fallthru edge to the branch edge
/* We don't want simplejumps in the insn stream during cfglayout. */
gcc_assert (!simplejump_p (BB_END (src)));
- src->flags |= BB_DIRTY;
+ df_set_bb_dirty (src);
return ret;
}
gcc_assert (cfg_layout_can_merge_blocks_p (a, b));
#endif
+ if (dump_file)
+ fprintf (dump_file, "merging block %d into block %d\n", b->index, a->index);
+
/* If there was a CODE_LABEL beginning B, delete it. */
if (LABEL_P (BB_HEAD (b)))
{
{
rtx first = BB_END (a), last;
- last = emit_insn_after_noloc (b->il.rtl->header, BB_END (a));
- delete_insn_chain (NEXT_INSN (first), last);
+ last = emit_insn_after_noloc (b->il.rtl->header, BB_END (a), a);
+ delete_insn_chain (NEXT_INSN (first), last, false);
b->il.rtl->header = NULL;
}
{
rtx first = unlink_insn_chain (BB_HEAD (b), BB_END (b));
- emit_insn_after_noloc (first, BB_END (a));
+ emit_insn_after_noloc (first, BB_END (a), a);
/* Skip possible DELETED_LABEL insn. */
if (!NOTE_INSN_BASIC_BLOCK_P (first))
first = NEXT_INSN (first);
for (insn = BB_HEAD (b);
insn != NEXT_INSN (BB_END (b));
insn = NEXT_INSN (insn))
- set_block_for_insn (insn, a);
+ {
+ set_block_for_insn (insn, a);
+ df_insn_change_bb (insn);
+ }
+
insn = BB_HEAD (b);
/* Skip possible DELETED_LABEL insn. */
if (!NOTE_INSN_BASIC_BLOCK_P (insn))
delete_insn (insn);
}
+ df_bb_delete (b->index);
+
/* Possible tablejumps and barriers should appear after the block. */
if (b->il.rtl->footer)
{
}
b->il.rtl->footer = NULL;
}
- a->il.rtl->global_live_at_end = b->il.rtl->global_live_at_end;
if (dump_file)
fprintf (dump_file, "Merged blocks %d and %d.\n",
? NEXT_INSN (BB_END (e->src)) : get_insns (),
NULL_RTX, e->src);
- /* ??? This info is likely going to be out of date very soon, but we must
- create it to avoid getting an ICE later. */
- if (e->dest->il.rtl->global_live_at_start)
- {
- new_bb->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack);
- new_bb->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack);
- COPY_REG_SET (new_bb->il.rtl->global_live_at_start,
- e->dest->il.rtl->global_live_at_start);
- COPY_REG_SET (new_bb->il.rtl->global_live_at_end,
- e->dest->il.rtl->global_live_at_start);
- }
-
make_edge (new_bb, e->dest, EDGE_FALLTHRU);
redirect_edge_and_branch_force (e, new_bb);
#endif
/* FIXME: What if something in cc0/jump uses value set in new
insn? */
- new_insn = emit_insn_before_noloc (pat, insn);
+ new_insn = emit_insn_before_noloc (pat, insn, bb);
}
/* Likewise if the last insn is a call, as will happen in the presence
|| NOTE_INSN_BASIC_BLOCK_P (insn))
insn = NEXT_INSN (insn);
- new_insn = emit_insn_before_noloc (pat, insn);
+ new_insn = emit_insn_before_noloc (pat, insn, bb);
}
else
- new_insn = emit_insn_after_noloc (pat, insn);
+ new_insn = emit_insn_after_noloc (pat, insn, bb);
return new_insn;
}
/* We do not want to declare these functions in a header file, since they
should only be used through the cfghooks interface, and we do not want to
move them here since it would require also moving quite a lot of related
- code. */
+ code. They are in cfglayout.c. */
extern bool cfg_layout_can_duplicate_bb_p (basic_block);
extern basic_block cfg_layout_duplicate_bb (basic_block);