This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Flow graph cleanup, version 2
- To: egcs-patches at cygnus dot com
- Subject: Flow graph cleanup, version 2
- From: Bernd Schmidt <crux at pool dot informatik dot rwth-aachen dot de>
- Date: Mon, 26 Oct 1998 13:54:11 +0100 (MET)
Here's an updated version of the flow graph patches. These apply to today's
CVS tree. The only other changes are to rename free_flow_memory to
free_bb_memory (slightly more accurate name), as well as to call this
function from find_basic_blocks.
Bernd
* flow.c (XNMALLOC): New macro.
(flow_int_list_blocks, basic_block_succ, basic_block_pred): New
static variables.
(add_edge, add_edge_to_label): New static functions.
(free_bb_memory): New function.
(flow_delete_insn): Delete function.
(basic_block_drops_in): Delete variable.
(find_basic_blocks): Allocate and initialize basic_block_head,
basic_block_succ. Don't allocate basic_block_drops_in.
Call free_bb_memory at the beginning.
(find_basic_blocks_1): Don't do multiple passes.
Delete code to compute basic_block_drops_in.
After calling make_edges, mark blocks reached by current block live.
Update test for unreachable live blocks.
(mark_label_ref): Delete args X, CHECKDUP. Add PRED arg. All callers
changed.
Simplify to call add_edge_to_label when a LABEL_REF is found.
(make_edges): Simplify to call add_edge_to_label instead of
mark_label_ref most of the time.
Compute here whether control drops into the next block.
(delete_unreachable_blocks): Return void. All callers changed.
Delete unreachable blocks in reverse order.
After deleting all unreachable blocks, renumber the remaining ones
and update n_basic_blocks.
(delete_block): Speed up deletion a bit.
Don't set basic_block_drops_in for deleted blocks.
(free_basic_block_vars): Don't free basic_block_drops_in.
(life_analysis_1): Update to use new edge representation.
(dump_flow_info): Delete code to print basic block info; call
dump_bb_data instead.
(compute_preds_succs): Delete code to recompute basic_block_drops_in
and uid_block_number.
Simply copy the previously computed cfg.
(dump_bb_data): New arg LIVE_INFO. All callers changed.
Print register lifetime information if LIVE_INFO is nonzero.
* basic-block.h (dump_bb_data): Adjust prototype.
* gcse.c (gcse_main): Update call to dump_bb_data.
* rtl.h (free_bb_memory): Declare.
* toplev.c (rest_of_compilation): Call free_bb_memory.
Index: basic-block.h
===================================================================
RCS file: /usr/local/cvs/gcs/gcc/basic-block.h,v
retrieving revision 1.1.1.11
diff -u -p -r1.1.1.11 basic-block.h
--- basic-block.h 1998/10/12 10:43:35 1.1.1.11
+++ basic-block.h 1998/10/24 11:29:38
@@ -190,7 +190,8 @@ extern int *uid_block_number;
extern void compute_preds_succs PROTO ((int_list_ptr *, int_list_ptr *,
int *, int *));
-extern void dump_bb_data PROTO ((FILE *, int_list_ptr *, int_list_ptr *));
+extern void dump_bb_data PROTO ((FILE *, int_list_ptr *, int_list_ptr *,
+ int));
extern void free_bb_mem PROTO ((void));
extern void free_basic_block_vars PROTO ((int));
Index: flow.c
===================================================================
RCS file: /usr/local/cvs/gcs/gcc/flow.c,v
retrieving revision 1.1.1.47
diff -u -p -r1.1.1.47 flow.c
--- flow.c 1998/10/20 17:20:05 1.1.1.47
+++ flow.c 1998/10/24 11:45:25
@@ -128,6 +128,8 @@ Boston, MA 02111-1307, USA. */
#define obstack_chunk_alloc xmalloc
#define obstack_chunk_free free
+#define XNMALLOC(TYPE, COUNT) ((TYPE *) xmalloc ((COUNT) * sizeof (TYPE)))
+
/* The contents of the current function definition are allocated
in this obstack, and all are freed at the end of the function.
For top-level functions, this is temporary_obstack.
@@ -217,11 +219,15 @@ regset regs_live_at_setjmp;
The first two regs in the list are a pair, and the next two
are another pair, etc. */
rtx regs_may_share;
+
+/* Pointer to head of predecessor/successor block list. */
+static int_list_block *flow_int_list_blocks;
-/* Element N is nonzero if control can drop into basic block N
- from the preceding basic block. Freed after life_analysis. */
+/* Element N is the list of successors of basic block N. */
+static int_list_ptr *basic_block_succ;
-static char *basic_block_drops_in;
+/* Element N is the list of predecessors of basic block N. */
+static int_list_ptr *basic_block_pred;
/* Element N is depth within loops of the last insn in basic block number N.
Freed after life_analysis. */
@@ -249,14 +255,15 @@ static HARD_REG_SET elim_reg_set;
/* Forward declarations */
static void find_basic_blocks_1 PROTO((rtx, rtx));
+static void add_edge PROTO((int, int));
+static void add_edge_to_label PROTO((int, rtx));
static void make_edges PROTO((int));
-static void mark_label_ref PROTO((rtx, rtx, int));
-static int delete_unreachable_blocks PROTO((void));
+static void mark_label_ref PROTO((int, rtx));
+static void delete_unreachable_blocks PROTO((void));
static int delete_block PROTO((int));
static void life_analysis_1 PROTO((rtx, int));
static void propagate_block PROTO((regset, rtx, rtx, int,
regset, int));
-static rtx flow_delete_insn PROTO((rtx));
static int set_noop_p PROTO((rtx));
static int noop_move_p PROTO((rtx));
static void record_volatile_insns PROTO((rtx));
@@ -304,6 +311,10 @@ find_basic_blocks (f, nregs, file)
rtx nonlocal_label_list = nonlocal_label_rtx_list ();
int in_libcall_block = 0;
+ /* Avoid leaking memory if this is called multiple times per compiled
+ function. */
+ free_bb_memory ();
+
/* Count the basic blocks. Also find maximum insn uid value used. */
{
@@ -382,14 +393,17 @@ find_basic_blocks (f, nregs, file)
/* Allocate some tables that last till end of compiling this function
and some needed only in find_basic_blocks and life_analysis. */
- basic_block_head = (rtx *) xmalloc (n_basic_blocks * sizeof (rtx));
- basic_block_end = (rtx *) xmalloc (n_basic_blocks * sizeof (rtx));
- basic_block_drops_in = (char *) xmalloc (n_basic_blocks);
+ basic_block_head = XNMALLOC (rtx, n_basic_blocks);
+ basic_block_end = XNMALLOC (rtx, n_basic_blocks);
+ basic_block_succ = XNMALLOC (int_list_ptr, n_basic_blocks);
+ basic_block_pred = XNMALLOC (int_list_ptr, n_basic_blocks);
+ bzero ((char *)basic_block_succ, n_basic_blocks * sizeof (int_list_ptr));
+ bzero ((char *)basic_block_pred, n_basic_blocks * sizeof (int_list_ptr));
+
basic_block_computed_jump_target = (char *) oballoc (n_basic_blocks);
- basic_block_loop_depth = (short *) xmalloc (n_basic_blocks * sizeof (short));
- uid_block_number
- = (int *) xmalloc ((max_uid_for_flow + 1) * sizeof (int));
- uid_volatile = (char *) xmalloc (max_uid_for_flow + 1);
+ basic_block_loop_depth = XNMALLOC (short, n_basic_blocks);
+ uid_block_number = XNMALLOC (int, (max_uid_for_flow + 1));
+ uid_volatile = XNMALLOC (char, (max_uid_for_flow + 1));
bzero (uid_volatile, max_uid_for_flow + 1);
find_basic_blocks_1 (f, nonlocal_label_list);
@@ -435,15 +449,13 @@ find_basic_blocks_1 (f, nonlocal_labels)
register char *block_marked = (char *) alloca (n_basic_blocks);
rtx note, eh_note;
enum rtx_code prev_code, code;
- int depth, pass;
+ int depth;
int in_libcall_block = 0;
int call_had_abnormal_edge = 0;
- pass = 1;
active_eh_region = (int *) alloca ((max_uid_for_flow + 1) * sizeof (int));
nested_eh_region = (int *) alloca ((max_label_num () + 1) * sizeof (int));
nonlocal_label_list = nonlocal_labels;
- restart:
label_value_list = 0;
block_live_static = block_live;
@@ -564,23 +576,8 @@ find_basic_blocks_1 (f, nonlocal_labels)
in_libcall_block = 0;
}
- /* During the second pass, `n_basic_blocks' is only an upper bound.
- Only perform the sanity check for the first pass, and on the second
- pass ensure `n_basic_blocks' is set to the correct value. */
- if (pass == 1 && i + 1 != n_basic_blocks)
+ if (i + 1 != n_basic_blocks)
abort ();
- n_basic_blocks = i + 1;
-
- /* Record which basic blocks control can drop in to. */
-
- for (i = 0; i < n_basic_blocks; i++)
- {
- for (insn = PREV_INSN (basic_block_head[i]);
- insn && GET_CODE (insn) == NOTE; insn = PREV_INSN (insn))
- ;
-
- basic_block_drops_in[i] = insn && GET_CODE (insn) != BARRIER;
- }
/* Now find which basic blocks can actually be reached
and put all jump insns' LABEL_REFS onto the ref-chains
@@ -589,7 +586,6 @@ find_basic_blocks_1 (f, nonlocal_labels)
if (n_basic_blocks > 0)
{
int something_marked = 1;
- int deleted = 0;
/* Pass over all blocks, marking each block that is reachable
and has not yet been marked.
@@ -603,10 +599,15 @@ find_basic_blocks_1 (f, nonlocal_labels)
for (i = 0; i < n_basic_blocks; i++)
if (block_live[i] && !block_marked[i])
{
+ int_list_ptr p;
+
block_marked[i] = 1;
something_marked = 1;
make_edges (i);
+
+ for (p = basic_block_succ[i]; p; p = p->next)
+ block_live[INT_LIST_VAL (p)] = 1;
}
}
@@ -618,40 +619,11 @@ find_basic_blocks_1 (f, nonlocal_labels)
later during the compile or at runtime. It's easier to debug the
problem here than later! */
for (i = 1; i < n_basic_blocks; i++)
- if (block_live[i] && ! basic_block_drops_in[i]
- && GET_CODE (basic_block_head[i]) == CODE_LABEL
- && LABEL_REFS (basic_block_head[i]) == basic_block_head[i])
+ if (block_live[i] && basic_block_pred[i] == 0)
abort ();
if (! reload_completed)
- deleted = delete_unreachable_blocks ();
-
- /* There are pathological cases where one function calling hundreds of
- nested inline functions can generate lots and lots of unreachable
- blocks that jump can't delete. Since we don't use sparse matrices
- a lot of memory will be needed to compile such functions.
- Implementing sparse matrices is a fair bit of work and it is not
- clear that they win more than they lose (we don't want to
- unnecessarily slow down compilation of normal code). By making
- another pass for the pathological case, we can greatly speed up
- their compilation without hurting normal code. This works because
- all the insns in the unreachable blocks have either been deleted or
- turned into notes.
- Note that we're talking about reducing memory usage by 10's of
- megabytes and reducing compilation time by several minutes. */
- /* ??? The choice of when to make another pass is a bit arbitrary,
- and was derived from empirical data. */
- if (pass == 1
- && deleted > 200)
- {
- pass++;
- n_basic_blocks -= deleted;
- /* `n_basic_blocks' may not be correct at this point: two previously
- separate blocks may now be merged. That's ok though as we
- recalculate it during the second pass. It certainly can't be
- any larger than the current value. */
- goto restart;
- }
+ delete_unreachable_blocks ();
}
}
@@ -671,10 +643,74 @@ set_block_num (insn, bb)
}
BLOCK_NUM (insn) = bb;
}
-
/* Subroutines of find_basic_blocks. */
+void
+free_bb_memory ()
+{
+ free_int_list (&flow_int_list_blocks);
+}
+
+/* Make an edge in the cfg from block PRED to block SUCC. */
+static void
+add_edge (pred, succ)
+ int pred, succ;
+{
+ add_int_list_node (&flow_int_list_blocks, basic_block_pred + succ, pred);
+ add_int_list_node (&flow_int_list_blocks, basic_block_succ + pred, succ);
+}
+
+/* Make an edge in the cfg from block PRED to the block starting with
+ label LABEL. */
+static void
+add_edge_to_label (pred, label)
+ int pred;
+ rtx label;
+{
+ /* If the label was never emitted, this insn is junk,
+ but avoid a crash trying to refer to BLOCK_NUM (label).
+ This can happen as a result of a syntax error
+ and a diagnostic has already been printed. */
+ if (INSN_UID (label) == 0)
+ return;
+
+ add_edge (pred, BLOCK_NUM (label));
+}
+
+/* Check expression X for label references. If one is found, add an edge
+ from basic block PRED to the block beginning with the label. */
+
+static void
+mark_label_ref (pred, x)
+ int pred;
+ rtx x;
+{
+ register RTX_CODE code;
+ register int i;
+ register char *fmt;
+
+ code = GET_CODE (x);
+ if (code == LABEL_REF)
+ {
+ add_edge_to_label (pred, XEXP (x, 0));
+ return;
+ }
+
+ fmt = GET_RTX_FORMAT (code);
+ for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+ {
+ if (fmt[i] == 'e')
+ mark_label_ref (pred, XEXP (x, i));
+ if (fmt[i] == 'E')
+ {
+ register int j;
+ for (j = 0; j < XVECLEN (x, i); j++)
+ mark_label_ref (pred, XVECEXP (x, i, j));
+ }
+ }
+}
+
/* For basic block I, make edges and mark live all blocks which are reachable
from it. */
static void
@@ -682,19 +718,27 @@ make_edges (i)
int i;
{
rtx insn, x;
+
+ /* See if control drops into the next block. */
+ if (i + 1 < n_basic_blocks)
+ {
+ for (insn = PREV_INSN (basic_block_head[i + 1]);
+ insn && GET_CODE (insn) == NOTE; insn = PREV_INSN (insn))
+ ;
+
+ if (insn && GET_CODE (insn) != BARRIER)
+ add_edge (i, i + 1);
+ }
- if (i + 1 < n_basic_blocks && basic_block_drops_in[i + 1])
- block_live_static[i + 1] = 1;
insn = basic_block_end[i];
if (GET_CODE (insn) == JUMP_INSN)
- mark_label_ref (PATTERN (insn), insn, 0);
+ mark_label_ref (i, PATTERN (insn));
/* If we have any forced labels, mark them as potentially reachable from
this block. */
for (x = forced_labels; x; x = XEXP (x, 1))
if (! LABEL_REF_NONLOCAL_P (x))
- mark_label_ref (gen_rtx_LABEL_REF (VOIDmode, XEXP (x, 0)),
- insn, 0);
+ add_edge_to_label (i, XEXP (x, 0));
/* Now scan the insns for this block, we may need to make edges for some of
them to various non-obvious locations (exception handlers, nonlocal
@@ -731,12 +775,7 @@ make_edges (i)
{
if (REG_NOTE_KIND (note) == REG_LABEL
&& XEXP (note, 0) != eh_return_stub_label)
- {
- x = XEXP (note, 0);
- block_live_static[BLOCK_NUM (x)] = 1;
- mark_label_ref (gen_rtx_LABEL_REF (VOIDmode, x),
- insn, 0);
- }
+ add_edge_to_label (i, XEXP (note, 0));
}
/* If this is a computed jump, then mark it as reaching everything
@@ -748,16 +787,14 @@ make_edges (i)
{
int b = BLOCK_NUM (XEXP (x, 0));
basic_block_computed_jump_target[b] = 1;
- mark_label_ref (gen_rtx_LABEL_REF (VOIDmode, XEXP (x, 0)),
- insn, 0);
+ add_edge (i, b);
}
for (x = forced_labels; x; x = XEXP (x, 1))
{
int b = BLOCK_NUM (XEXP (x, 0));
basic_block_computed_jump_target[b] = 1;
- mark_label_ref (gen_rtx_LABEL_REF (VOIDmode, XEXP (x, 0)),
- insn, 0);
+ add_edge (i, b);
}
}
@@ -775,21 +812,17 @@ make_edges (i)
int region;
handler_info *ptr;
region = active_eh_region[INSN_UID (insn)];
- for ( ; region;
- region = nested_eh_region[region])
+ for ( ; region; region = nested_eh_region[region])
{
ptr = get_first_handler (region);
for ( ; ptr ; ptr = ptr->next)
- mark_label_ref (gen_rtx_LABEL_REF (VOIDmode,
- ptr->handler_label),
- insn, 0);
+ add_edge_to_label (i, ptr->handler_label);
}
}
if (! asynchronous_exceptions)
{
for (x = nonlocal_label_list; x; x = XEXP (x, 1))
- mark_label_ref (gen_rtx_LABEL_REF (VOIDmode, XEXP (x, 0)),
- insn, 0);
+ add_edge_to_label (i, XEXP (x, 0));
}
/* ??? This could be made smarter: in some cases it's possible
to tell that certain calls will not do a nonlocal goto.
@@ -807,101 +840,79 @@ make_edges (i)
the eh_stub labels within it. So we have to make additional edges in
the flow graph. */
if (i + 1 == n_basic_blocks && eh_return_stub_label != 0)
- {
- mark_label_ref (gen_rtx_LABEL_REF (VOIDmode, eh_return_stub_label),
- basic_block_end[i], 0);
- }
+ add_edge_to_label (i, eh_return_stub_label);
}
-/* Check expression X for label references;
- if one is found, add INSN to the label's chain of references.
-
- CHECKDUP means check for and avoid creating duplicate references
- from the same insn. Such duplicates do no serious harm but
- can slow life analysis. CHECKDUP is set only when duplicates
- are likely. */
-
-static void
-mark_label_ref (x, insn, checkdup)
- rtx x, insn;
- int checkdup;
-{
- register RTX_CODE code;
- register int i;
- register char *fmt;
-
- /* We can be called with NULL when scanning label_value_list. */
- if (x == 0)
- return;
-
- code = GET_CODE (x);
- if (code == LABEL_REF)
- {
- register rtx label = XEXP (x, 0);
- register rtx y;
- if (GET_CODE (label) != CODE_LABEL)
- abort ();
- /* If the label was never emitted, this insn is junk,
- but avoid a crash trying to refer to BLOCK_NUM (label).
- This can happen as a result of a syntax error
- and a diagnostic has already been printed. */
- if (INSN_UID (label) == 0)
- return;
- CONTAINING_INSN (x) = insn;
- /* if CHECKDUP is set, check for duplicate ref from same insn
- and don't insert. */
- if (checkdup)
- for (y = LABEL_REFS (label); y != label; y = LABEL_NEXTREF (y))
- if (CONTAINING_INSN (y) == insn)
- return;
- LABEL_NEXTREF (x) = LABEL_REFS (label);
- LABEL_REFS (label) = x;
- block_live_static[BLOCK_NUM (label)] = 1;
- return;
- }
-
- fmt = GET_RTX_FORMAT (code);
- for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
- {
- if (fmt[i] == 'e')
- mark_label_ref (XEXP (x, i), insn, 0);
- if (fmt[i] == 'E')
- {
- register int j;
- for (j = 0; j < XVECLEN (x, i); j++)
- mark_label_ref (XVECEXP (x, i, j), insn, 1);
- }
- }
-}
-
/* Now delete the code for any basic blocks that can't be reached.
They can occur because jump_optimize does not recognize unreachable loops
- as unreachable.
- Return the number of deleted blocks. */
-static int
+ as unreachable. */
+static void
delete_unreachable_blocks ()
{
int deleted_handler = 0;
int deleted = 0;
- int i;
+ int i, j;
rtx insn;
+ int *block_num_map = XNMALLOC (int, n_basic_blocks);
- for (i = 0; i < n_basic_blocks; i++)
+ for (i = n_basic_blocks - 1; i >= 0; i--)
if (! block_live_static[i])
+ deleted_handler |= delete_block (i);
+
+ for (i = 0; i < n_basic_blocks; i++)
+ if (block_live_static[i])
+ block_num_map[i] = i - deleted;
+ else
{
deleted++;
-
- deleted_handler |= delete_block (i);
+ block_num_map[i] = -1;
}
+ /* Eliminate all traces of the deleted blocks by renumbering the remaining
+ ones. */
+ for (i = j = 0; i < n_basic_blocks; i++)
+ {
+ int_list_ptr p;
+
+ if (block_num_map[i] == -1)
+ continue;
+
+ for (p = basic_block_pred[i]; p; p = p->next)
+ INT_LIST_VAL (p) = block_num_map[INT_LIST_VAL (p)];
+ for (p = basic_block_succ[i]; p; p = p->next)
+ INT_LIST_VAL (p) = block_num_map[INT_LIST_VAL (p)];
+
+ if (i != j)
+ {
+ rtx tmp = basic_block_head[i];
+ for (;;)
+ {
+ BLOCK_NUM (tmp) = j;
+ if (tmp == basic_block_end[i])
+ break;
+ tmp = NEXT_INSN (tmp);
+ }
+ basic_block_head[j] = basic_block_head[i];
+ basic_block_end[j] = basic_block_end[i];
+ basic_block_pred[j] = basic_block_pred[i];
+ basic_block_succ[j] = basic_block_succ[i];
+ basic_block_loop_depth[j] = basic_block_loop_depth[i];
+ basic_block_computed_jump_target[j]
+ = basic_block_computed_jump_target[i];
+ }
+ j++;
+ }
+ n_basic_blocks -= deleted;
+ free (block_num_map);
+
/* If we deleted an exception handler, we may have EH region
begin/end blocks to remove as well. */
if (deleted_handler)
for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
if (GET_CODE (insn) == NOTE)
{
- if ((NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG) ||
- (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END))
+ if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG ||
+ NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)
{
int num = CODE_LABEL_NUMBER (insn);
/* A NULL handler indicates a region is no longer needed */
@@ -912,7 +923,6 @@ delete_unreachable_blocks ()
}
}
}
- return deleted;
}
/* Delete the insns in a (non-live) block. We physically delete every
@@ -932,83 +942,89 @@ delete_block (i)
{
int deleted_handler = 0;
rtx insn;
+ rtx kept_head = 0;
+ rtx kept_tail = 0;
- if (basic_block_head[i] != basic_block_end[i])
+ /* If the head of this block is a CODE_LABEL, then it might
+ be the label for an exception handler which can't be
+ reached.
+
+ We need to remove the label from the exception_handler_label
+ list and remove the associated NOTE_EH_REGION_BEG and
+ NOTE_EH_REGION_END notes. */
+ insn = basic_block_head[i];
+ if (GET_CODE (insn) == CODE_LABEL)
{
- /* It would be quicker to delete all of these with a single
- unchaining, rather than one at a time, but we need to keep
- the NOTE's. */
- insn = NEXT_INSN (basic_block_head[i]);
- while (insn != basic_block_end[i])
+ rtx x, *prev = &exception_handler_labels;
+
+ for (x = exception_handler_labels; x; x = XEXP (x, 1))
{
- if (GET_CODE (insn) == BARRIER)
- abort ();
- else if (GET_CODE (insn) != NOTE)
- insn = flow_delete_insn (insn);
- else
- insn = NEXT_INSN (insn);
+ if (XEXP (x, 0) == insn)
+ {
+ /* Found a match, splice this label out of the
+ EH label list. */
+ *prev = XEXP (x, 1);
+ XEXP (x, 1) = NULL_RTX;
+ XEXP (x, 0) = NULL_RTX;
+
+ /* Remove the handler from all regions */
+ remove_handler (insn);
+ deleted_handler = 1;
+ break;
+ }
+ prev = &XEXP (x, 1);
}
}
+ /* Walk the insns of the block, building a chain of NOTEs that need to be
+ kept. */
insn = basic_block_head[i];
- if (GET_CODE (insn) != NOTE)
+ for (;;)
{
- /* Turn the head into a deleted insn note. */
if (GET_CODE (insn) == BARRIER)
abort ();
-
- /* If the head of this block is a CODE_LABEL, then it might
- be the label for an exception handler which can't be
- reached.
-
- We need to remove the label from the exception_handler_label
- list and remove the associated NOTE_EH_REGION_BEG and
- NOTE_EH_REGION_END notes. */
- if (GET_CODE (insn) == CODE_LABEL)
+ else if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) != NOTE_INSN_DELETED)
{
- rtx x, *prev = &exception_handler_labels;
-
- for (x = exception_handler_labels; x; x = XEXP (x, 1))
+ if (kept_head == 0)
+ kept_head = kept_tail = insn;
+ else
{
- if (XEXP (x, 0) == insn)
- {
- /* Found a match, splice this label out of the
- EH label list. */
- *prev = XEXP (x, 1);
- XEXP (x, 1) = NULL_RTX;
- XEXP (x, 0) = NULL_RTX;
-
- /* Remove the handler from all regions */
- remove_handler (insn);
- deleted_handler = 1;
- break;
- }
- prev = &XEXP (x, 1);
+ NEXT_INSN (kept_tail) = insn;
+ PREV_INSN (insn) = kept_tail;
+ kept_tail = insn;
}
}
-
- PUT_CODE (insn, NOTE);
- NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
- NOTE_SOURCE_FILE (insn) = 0;
- }
- insn = basic_block_end[i];
- if (GET_CODE (insn) != NOTE)
- {
- /* Turn the tail into a deleted insn note. */
- if (GET_CODE (insn) == BARRIER)
- abort ();
- PUT_CODE (insn, NOTE);
- NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
- NOTE_SOURCE_FILE (insn) = 0;
+ if (insn == basic_block_end[i])
+ break;
+ insn = NEXT_INSN (insn);
}
+ insn = NEXT_INSN (insn);
+
/* BARRIERs are between basic blocks, not part of one.
Delete a BARRIER if the preceding jump is deleted.
We cannot alter a BARRIER into a NOTE
because it is too short; but we can really delete
it because it is not part of a basic block. */
- if (NEXT_INSN (insn) != 0
- && GET_CODE (NEXT_INSN (insn)) == BARRIER)
- delete_insn (NEXT_INSN (insn));
+ if (insn != 0 && GET_CODE (insn) == BARRIER)
+ insn = NEXT_INSN (insn);
+
+ /* Now unchain all of the block, and put the chain of kept notes in its
+ place. */
+ if (kept_head == 0)
+ {
+ NEXT_INSN (PREV_INSN (basic_block_head[i])) = insn;
+ if (insn != 0)
+ PREV_INSN (insn) = PREV_INSN (basic_block_head[i]);
+ }
+ else
+ {
+ NEXT_INSN (PREV_INSN (basic_block_head[i])) = kept_head;
+ if (insn != 0)
+ PREV_INSN (insn) = kept_tail;
+
+ PREV_INSN (kept_head) = PREV_INSN (basic_block_head[i]);
+ NEXT_INSN (kept_tail) = insn;
+ }
/* Each time we delete some basic blocks,
see if there is a jump around them that is
@@ -1031,14 +1047,6 @@ delete_block (i)
&& INSN_UID (label) != 0
&& BLOCK_NUM (label) == j)
{
- int k;
-
- /* The deleted blocks still show up in the cfg,
- so we must set basic_block_drops_in for blocks
- I to J inclusive to keep the cfg accurate. */
- for (k = i; k <= j; k++)
- basic_block_drops_in[k] = 1;
-
PUT_CODE (insn, NOTE);
NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
NOTE_SOURCE_FILE (insn) = 0;
@@ -1052,20 +1060,6 @@ delete_block (i)
return deleted_handler;
}
-
-/* Delete INSN by patching it out.
- Return the next insn. */
-
-static rtx
-flow_delete_insn (insn)
- rtx insn;
-{
- /* ??? For the moment we assume we don't have to watch for NULLs here
- since the start/end of basic blocks aren't deleted like this. */
- NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
- PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
- return NEXT_INSN (insn);
-}
/* Perform data flow analysis.
F is the first insn of the function and NREGS the number of register numbers
@@ -1110,12 +1104,6 @@ void
free_basic_block_vars (keep_head_end_p)
int keep_head_end_p;
{
- if (basic_block_drops_in)
- {
- free (basic_block_drops_in);
- /* Tell dump_flow_info this isn't available anymore. */
- basic_block_drops_in = 0;
- }
if (basic_block_loop_depth)
{
free (basic_block_loop_depth);
@@ -1485,26 +1473,16 @@ life_analysis_1 (f, nregs)
}
{
- register rtx jump, head;
+ int_list_ptr p;
- /* Update the basic_block_new_live_at_end's of the block
- that falls through into this one (if any). */
- head = basic_block_head[i];
- if (basic_block_drops_in[i])
- IOR_REG_SET (basic_block_new_live_at_end[i-1],
- basic_block_live_at_start[i]);
-
/* Update the basic_block_new_live_at_end's of
- all the blocks that jump to this one. */
- if (GET_CODE (head) == CODE_LABEL)
- for (jump = LABEL_REFS (head);
- jump != head;
- jump = LABEL_NEXTREF (jump))
- {
- register int from_block = BLOCK_NUM (CONTAINING_INSN (jump));
- IOR_REG_SET (basic_block_new_live_at_end[from_block],
- basic_block_live_at_start[i]);
- }
+ all the blocks that reach this one. */
+ for (p = basic_block_pred[i]; p; p = p->next)
+ {
+ register int from_block = INT_LIST_VAL (p);
+ IOR_REG_SET (basic_block_new_live_at_end[from_block],
+ basic_block_live_at_start[i]);
+ }
}
#ifdef USE_C_ALLOCA
alloca (0);
@@ -3192,39 +3170,7 @@ dump_flow_info (file)
fprintf (file, ".\n");
}
fprintf (file, "\n%d basic blocks.\n", n_basic_blocks);
- for (i = 0; i < n_basic_blocks; i++)
- {
- register rtx head, jump;
- register int regno;
- fprintf (file, "\nBasic block %d: first insn %d, last %d.\n",
- i,
- INSN_UID (basic_block_head[i]),
- INSN_UID (basic_block_end[i]));
- /* The control flow graph's storage is freed
- now when flow_analysis returns.
- Don't try to print it if it is gone. */
- if (basic_block_drops_in)
- {
- fprintf (file, "Reached from blocks: ");
- head = basic_block_head[i];
- if (GET_CODE (head) == CODE_LABEL)
- for (jump = LABEL_REFS (head);
- jump != head;
- jump = LABEL_NEXTREF (jump))
- {
- register int from_block = BLOCK_NUM (CONTAINING_INSN (jump));
- fprintf (file, " %d", from_block);
- }
- if (basic_block_drops_in[i])
- fprintf (file, " previous");
- }
- fprintf (file, "\nRegisters live at start:");
- for (regno = 0; regno < max_regno; regno++)
- if (REGNO_REG_SET_P (basic_block_live_at_start[i], regno))
- fprintf (file, " %d", regno);
- fprintf (file, "\n");
- }
- fprintf (file, "\n");
+ dump_bb_data (file, basic_block_pred, basic_block_succ, 1);
}
@@ -3407,117 +3353,46 @@ compute_preds_succs (s_preds, s_succs, n
int *num_preds;
int *num_succs;
{
- int bb, clear_local_bb_vars = 0;
+ int bb;
bzero ((char *) s_preds, n_basic_blocks * sizeof (int_list_ptr));
bzero ((char *) s_succs, n_basic_blocks * sizeof (int_list_ptr));
bzero ((char *) num_preds, n_basic_blocks * sizeof (int));
bzero ((char *) num_succs, n_basic_blocks * sizeof (int));
-
- /* This routine can be called after life analysis; in that case
- basic_block_drops_in and uid_block_number will not be available
- and we must recompute their values. */
- if (basic_block_drops_in == NULL || uid_block_number == NULL)
- {
- clear_local_bb_vars = 1;
- basic_block_drops_in = (char *) alloca (n_basic_blocks);
- uid_block_number = (int *) alloca ((get_max_uid () + 1) * sizeof (int));
-
- bzero ((char *) basic_block_drops_in, n_basic_blocks * sizeof (char));
- bzero ((char *) uid_block_number, n_basic_blocks * sizeof (int));
-
- /* Scan each basic block setting basic_block_drops_in and
- uid_block_number as needed. */
- for (bb = 0; bb < n_basic_blocks; bb++)
- {
- rtx insn, stop_insn;
- if (bb == 0)
- stop_insn = NULL_RTX;
- else
- stop_insn = basic_block_end[bb-1];
-
- /* Look backwards from the start of this block. Stop if we
- hit the start of the function or the end of a previous
- block. Don't walk backwards through blocks that are just
- deleted insns! */
- for (insn = PREV_INSN (basic_block_head[bb]);
- insn && insn != stop_insn && GET_CODE (insn) == NOTE;
- insn = PREV_INSN (insn))
- ;
-
- /* Never set basic_block_drops_in for the first block. It is
- implicit.
-
- If we stopped on anything other than a BARRIER, then this
- block drops in. */
- if (bb != 0)
- basic_block_drops_in[bb] = (insn ? GET_CODE (insn) != BARRIER : 1);
-
- insn = basic_block_head[bb];
- while (insn)
- {
- BLOCK_NUM (insn) = bb;
- if (insn == basic_block_end[bb])
- break;
- insn = NEXT_INSN (insn);
- }
- }
- }
-
+ /* It's somewhat stupid to simply copy the information. The passes
+ which use this function ought to be changed to refer directly to
+ basic_block_succ and its relatives. */
for (bb = 0; bb < n_basic_blocks; bb++)
{
- rtx head;
- rtx jump;
+ rtx jump = BLOCK_END (bb);
+ enum rtx_code code = GET_CODE (jump);
+ int_list_ptr p;
+
+ for (p = basic_block_succ[bb]; p; p = p->next)
+ add_pred_succ (bb, INT_LIST_VAL (p), s_preds, s_succs, num_preds,
+ num_succs);
- head = BLOCK_HEAD (bb);
-
- if (GET_CODE (head) == CODE_LABEL)
- for (jump = LABEL_REFS (head);
- jump != head;
- jump = LABEL_NEXTREF (jump))
- {
- if (! INSN_DELETED_P (CONTAINING_INSN (jump))
- && (GET_CODE (CONTAINING_INSN (jump)) != NOTE
- || (NOTE_LINE_NUMBER (CONTAINING_INSN (jump))
- != NOTE_INSN_DELETED)))
- add_pred_succ (BLOCK_NUM (CONTAINING_INSN (jump)), bb,
- s_preds, s_succs, num_preds, num_succs);
- }
-
- jump = BLOCK_END (bb);
/* If this is a RETURN insn or a conditional jump in the last
basic block, or a non-jump insn in the last basic block, then
this block reaches the exit block. */
- if ((GET_CODE (jump) == JUMP_INSN && GET_CODE (PATTERN (jump)) == RETURN)
- || (((GET_CODE (jump) == JUMP_INSN
+ if ((code == JUMP_INSN && GET_CODE (PATTERN (jump)) == RETURN)
+ || (((code == JUMP_INSN
&& condjump_p (jump) && !simplejump_p (jump))
- || GET_CODE (jump) != JUMP_INSN)
- && (bb == n_basic_blocks - 1)))
+ || code != JUMP_INSN)
+ && bb == n_basic_blocks - 1))
add_pred_succ (bb, EXIT_BLOCK, s_preds, s_succs, num_preds, num_succs);
-
- if (basic_block_drops_in[bb])
- add_pred_succ (bb - 1, bb, s_preds, s_succs, num_preds, num_succs);
}
add_pred_succ (ENTRY_BLOCK, 0, s_preds, s_succs, num_preds, num_succs);
-
-
- /* If we allocated any variables in temporary storage, clear out the
- pointer to the local storage to avoid dangling pointers. */
- if (clear_local_bb_vars)
- {
- basic_block_drops_in = NULL;
- uid_block_number = NULL;
-
- }
}
void
-dump_bb_data (file, preds, succs)
+dump_bb_data (file, preds, succs, live_info)
FILE *file;
int_list_ptr *preds;
int_list_ptr *succs;
+ int live_info;
{
int bb;
int_list_ptr p;
@@ -3545,6 +3420,15 @@ dump_bb_data (file, preds, succs)
fprintf (file, " exit");
else
fprintf (file, " %d", succ_bb);
+ }
+ if (live_info)
+ {
+ int regno;
+ fprintf (file, "\nRegisters live at start:");
+ for (regno = 0; regno < max_regno; regno++)
+ if (REGNO_REG_SET_P (basic_block_live_at_start[bb], regno))
+ fprintf (file, " %d", regno);
+ fprintf (file, "\n");
}
fprintf (file, "\n");
}
Index: gcse.c
===================================================================
RCS file: /usr/local/cvs/gcs/gcc/gcse.c,v
retrieving revision 1.1.1.13
diff -u -p -r1.1.1.13 gcse.c
--- gcse.c 1998/10/22 11:02:19 1.1.1.13
+++ gcse.c 1998/10/24 11:29:38
@@ -700,9 +700,7 @@ gcse_main (f, file)
compute_preds_succs (s_preds, s_succs, num_preds, num_succs);
if (file)
- {
- dump_bb_data (file, s_preds, s_succs);
- }
+ dump_bb_data (file, s_preds, s_succs, 0);
/* Record where pseudo-registers are set.
This data is kept accurate during each pass.
Index: rtl.h
===================================================================
RCS file: /usr/local/cvs/gcs/gcc/rtl.h,v
retrieving revision 1.1.1.43
diff -u -p -r1.1.1.43 rtl.h
--- rtl.h 1998/10/22 11:02:43 1.1.1.43
+++ rtl.h 1998/10/24 11:45:40
@@ -1371,6 +1371,7 @@ extern void recompute_reg_usage PROTO (
#ifdef BUFSIZ
extern void dump_flow_info PROTO ((FILE *));
#endif
+extern void free_bb_memory PROTO ((void));
/* In expmed.c */
extern void init_expmed PROTO ((void));
Index: toplev.c
===================================================================
RCS file: /usr/local/cvs/gcs/gcc/toplev.c,v
retrieving revision 1.1.1.53
diff -u -p -r1.1.1.53 toplev.c
--- toplev.c 1998/10/22 11:02:47 1.1.1.53
+++ toplev.c 1998/10/24 11:45:32
@@ -3933,6 +3933,8 @@ rest_of_compilation (decl)
exit_rest_of_compilation:
+ free_bb_memory ();
+
/* In case the function was not output,
don't leave any temporary anonymous types
queued up for sdb output. */