Creating a prettier flow graph
Bernd Schmidt
crux@pool.informatik.rwth-aachen.de
Mon Oct 12 14:37:00 GMT 1998
Currently, the cfg built by flow.c is a fairly ugly construct, consisting
of a circular LABEL_REFS chain and the basic_block_drops_in array. This
patch does the following:
- represent edges as int_list, like compute_preds_succs
- delete most of compute_preds_succs as a result (all of it should be
deleted, and the other passes which use it should simply use the
previously computed cfg IMHO)
- delete all traces of unreachable blocks by renumbering the live ones.
That might make the rest of the compiler run minimally faster, and it
also gets rid of the restarting code in find_basic_blocks_1.
- make delete_block a tiny bit faster.
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_flow_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.
(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_flow_memory): Declare.
* toplev.c (rest_of_compilation): Call free_flow_memory.
Index: basic-block.h
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/basic-block.h,v
retrieving revision 1.15
diff -u -p -r1.15 basic-block.h
--- basic-block.h 1998/10/10 22:03:33 1.15
+++ basic-block.h 1998/10/12 14:17:44
@@ -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: /egcs/carton/cvsfiles/egcs/gcc/flow.c,v
retrieving revision 1.69
diff -u -p -r1.69 flow.c
--- flow.c 1998/10/11 15:02:04 1.69
+++ flow.c 1998/10/12 14:17:51
@@ -124,6 +124,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.
@@ -222,11 +224,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. */
@@ -254,14 +260,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));
@@ -390,15 +397,18 @@ 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 = 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_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_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);
@@ -444,11 +454,10 @@ 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;
@@ -587,24 +596,9 @@ 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
of their target labels. */
@@ -612,7 +606,6 @@ find_basic_blocks_1 (f, nonlocal_labels)
if (n_basic_blocks > 0)
{
int something_marked = 1;
- int deleted;
/* Pass over all blocks, marking each block that is reachable
and has not yet been marked.
@@ -626,10 +619,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;
}
}
@@ -641,39 +639,10 @@ 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 ();
-
- 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 ();
}
}
@@ -693,10 +662,81 @@ set_block_num (insn, bb)
}
BLOCK_NUM (insn) = bb;
}
-
/* Subroutines of find_basic_blocks. */
+void
+free_flow_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;
+{
+ int_list_ptr p;
+
+ /* Check for duplicates. */
+ for (p = basic_block_pred[succ]; p; p = p->next)
+ if (INT_LIST_VAL (p) == pred)
+ return;
+
+ 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
@@ -705,18 +745,26 @@ make_edges (i)
{
rtx insn, x;
- if (i + 1 < n_basic_blocks && basic_block_drops_in[i + 1])
- block_live_static[i + 1] = 1;
+ /* 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);
+ }
+
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
@@ -753,12 +801,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
@@ -770,16 +813,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);
}
}
@@ -797,21 +838,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.
@@ -829,101 +866,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);
- }
-}
-
-/* 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);
- }
- }
+ add_edge_to_label (i, eh_return_stub_label);
}
/* 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 */
@@ -934,7 +949,6 @@ delete_unreachable_blocks ()
}
}
}
- return deleted;
}
/* Delete the insns in a (non-live) block. We physically delete every
@@ -954,84 +968,92 @@ 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. This will destroy basic_block_head/basic_block_end for this
+ block, but they are not referenced hereafter. */
+ 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
being turned into a no-op. If so, delete it. */
@@ -1053,14 +1075,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;
@@ -1074,20 +1088,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
@@ -1132,12 +1132,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);
@@ -1466,26 +1460,16 @@ life_analysis_1 (f, nregs)
}
{
- register rtx jump, head;
-
- /* 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]);
+ int_list_ptr p;
/* 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);
@@ -3216,39 +3200,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);
}
@@ -3431,117 +3383,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;
@@ -3569,6 +3450,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: /egcs/carton/cvsfiles/egcs/gcc/gcse.c,v
retrieving revision 1.17
diff -u -p -r1.17 gcse.c
--- gcse.c 1998/10/10 23:18:29 1.17
+++ gcse.c 1998/10/12 14:17:53
@@ -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: /egcs/carton/cvsfiles/egcs/gcc/rtl.h,v
retrieving revision 1.55
diff -u -p -r1.55 rtl.h
--- rtl.h 1998/10/06 19:39:34 1.55
+++ rtl.h 1998/10/12 14:17:54
@@ -1391,6 +1391,7 @@ extern void recompute_reg_usage PROTO (
#ifdef BUFSIZ
extern void dump_flow_info PROTO ((FILE *));
#endif
+extern void free_flow_memory PROTO ((void));
/* In expmed.c */
extern void init_expmed PROTO ((void));
Index: toplev.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/toplev.c,v
retrieving revision 1.107
diff -u -p -r1.107 toplev.c
--- toplev.c 1998/10/10 23:18:32 1.107
+++ toplev.c 1998/10/12 14:17:56
@@ -3908,6 +3908,8 @@ rest_of_compilation (decl)
exit_rest_of_compilation:
+ free_flow_memory ();
+
/* In case the function was not output,
don't leave any temporary anonymous types
queued up for sdb output. */
More information about the Gcc-patches
mailing list