/* Control flow graph building 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, 2003 Free Software Foundation, Inc.
This file is part of GCC.
\f
#include "config.h"
#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
#include "tree.h"
#include "rtl.h"
#include "hard-reg-set.h"
#include "except.h"
#include "toplev.h"
#include "timevar.h"
-#include "obstack.h"
static int count_basic_blocks PARAMS ((rtx));
static void find_basic_blocks_1 PARAMS ((rtx));
static rtx find_label_refs PARAMS ((rtx, rtx));
-static void make_edges PARAMS ((rtx, int, int, int));
+static void make_edges PARAMS ((rtx, basic_block,
+ basic_block, int));
static void make_label_edge PARAMS ((sbitmap *, basic_block,
rtx, int));
static void make_eh_edge PARAMS ((sbitmap *, basic_block, rtx));
static void find_bb_boundaries PARAMS ((basic_block));
static void compute_outgoing_frequencies PARAMS ((basic_block));
-static bool inside_basic_block_p PARAMS ((rtx));
-static bool control_flow_insn_p PARAMS ((rtx));
\f
/* Return true if insn is something that should be contained inside basic
block. */
-static bool
+bool
inside_basic_block_p (insn)
rtx insn;
{
/* Return true if INSN may cause control flow transfer, so it should be last in
the basic block. */
-static bool
+bool
control_flow_insn_p (insn)
rtx insn;
{
switch (GET_CODE (insn))
{
- case NOTE:
- case CODE_LABEL:
- return false;
-
- case JUMP_INSN:
- /* Jump insn always causes control transfer except for tablejumps. */
- return (GET_CODE (PATTERN (insn)) != ADDR_VEC
- && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC);
-
- case CALL_INSN:
- /* Call insn may return to the nonlocal goto handler. */
- return ((nonlocal_goto_handler_labels
- && (0 == (note = find_reg_note (insn, REG_EH_REGION,
- NULL_RTX))
- || INTVAL (XEXP (note, 0)) >= 0))
- /* Or may trap. */
- || can_throw_internal (insn));
-
- case INSN:
- return (flag_non_call_exceptions && can_throw_internal (insn));
-
- case BARRIER:
- /* It is nonsence to reach barrier when looking for the
- end of basic block, but before dead code is eliminated
- this may happen. */
- return false;
-
- default:
- abort ();
+ case NOTE:
+ case CODE_LABEL:
+ return false;
+
+ case JUMP_INSN:
+ /* Jump insn always causes control transfer except for tablejumps. */
+ return (GET_CODE (PATTERN (insn)) != ADDR_VEC
+ && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC);
+
+ case CALL_INSN:
+ /* Call insn may return to the nonlocal goto handler. */
+ return ((nonlocal_goto_handler_labels
+ && (0 == (note = find_reg_note (insn, REG_EH_REGION,
+ NULL_RTX))
+ || INTVAL (XEXP (note, 0)) >= 0))
+ /* Or may trap. */
+ || can_throw_internal (insn));
+
+ case INSN:
+ return (flag_non_call_exceptions && can_throw_internal (insn));
+
+ case BARRIER:
+ /* It is nonsence to reach barrier when looking for the
+ end of basic block, but before dead code is eliminated
+ this may happen. */
+ return false;
+
+ default:
+ abort ();
}
}
for (insn = f; insn; insn = NEXT_INSN (insn))
{
- /* Code labels and barriers causes curent basic block to be
+ /* Code labels and barriers causes current basic block to be
terminated at previous real insn. */
if ((GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == BARRIER)
&& saw_insn)
rtx lab = XEXP (note, 0), next;
if ((next = next_nonnote_insn (lab)) != NULL
- && GET_CODE (next) == JUMP_INSN
- && (GET_CODE (PATTERN (next)) == ADDR_VEC
- || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
+ && GET_CODE (next) == JUMP_INSN
+ && (GET_CODE (PATTERN (next)) == ADDR_VEC
+ || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
;
else if (GET_CODE (lab) == NOTE)
;
static void
make_edges (label_value_list, min, max, update_p)
rtx label_value_list;
- int min, max, update_p;
+ basic_block min, max;
+ int update_p;
{
- int i;
+ basic_block bb;
sbitmap *edge_cache = NULL;
/* Assume no computed jump; revise as we create edges. */
/* Heavy use of computed goto in machine-generated code can lead to
nearly fully-connected CFGs. In that case we spend a significant
amount of time searching the edge lists for duplicates. */
- if (forced_labels || label_value_list)
+ if (forced_labels || label_value_list || cfun->max_jumptable_ents > 100)
{
- edge_cache = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
- sbitmap_vector_zero (edge_cache, n_basic_blocks);
+ edge_cache = sbitmap_vector_alloc (last_basic_block, last_basic_block);
+ sbitmap_vector_zero (edge_cache, last_basic_block);
if (update_p)
- for (i = min; i <= max; ++i)
+ FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
{
edge e;
- for (e = BASIC_BLOCK (i)->succ; e ; e = e->succ_next)
+ for (e = bb->succ; e ; e = e->succ_next)
if (e->dest != EXIT_BLOCK_PTR)
- SET_BIT (edge_cache[i], e->dest->index);
+ SET_BIT (edge_cache[bb->index], e->dest->index);
}
}
- /* By nature of the way these get numbered, block 0 is always the entry. */
- if (min == 0)
- cached_make_edge (edge_cache, ENTRY_BLOCK_PTR, BASIC_BLOCK (0),
+ /* By nature of the way these get numbered, ENTRY_BLOCK_PTR->next_bb block
+ is always the entry. */
+ if (min == ENTRY_BLOCK_PTR->next_bb)
+ cached_make_edge (edge_cache, ENTRY_BLOCK_PTR, min,
EDGE_FALLTHRU);
- for (i = min; i <= max; ++i)
+ FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
{
- basic_block bb = BASIC_BLOCK (i);
rtx insn, x;
enum rtx_code code;
int force_fallthru = 0;
- if (GET_CODE (bb->head) == CODE_LABEL && LABEL_ALTERNATE_NAME (bb->head))
+ if (GET_CODE (bb->head) == CODE_LABEL && LABEL_ALT_ENTRY_P (bb->head))
cached_make_edge (NULL, ENTRY_BLOCK_PTR, bb, 0);
/* Examine the last instruction of the block, and discover the
else if (find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
;
- /* ??? Recognize a tablejump and do the right thing. */
- else 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))
+ /* Recognize a tablejump and do the right thing. */
+ else if (tablejump_p (insn, NULL, &tmp))
{
rtvec vec;
int j;
worry about EH edges, since we wouldn't have created the sibling call
in the first place. */
if (code == CALL_INSN && SIBLING_CALL_P (insn))
- cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR,
- EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
+ cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, EDGE_SIBCALL);
/* If this is a CALL_INSN, then mark it as reaching the active EH
handler for this CALL_INSN. If we're handling non-call
}
/* Find out if we can drop through to the next block. */
- insn = next_nonnote_insn (insn);
- if (!insn || (i + 1 == n_basic_blocks && force_fallthru))
+ insn = NEXT_INSN (insn);
+ while (insn
+ && GET_CODE (insn) == NOTE
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK)
+ insn = NEXT_INSN (insn);
+
+ if (!insn || (bb->next_bb == EXIT_BLOCK_PTR && force_fallthru))
cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
- else if (i + 1 < n_basic_blocks)
+ else if (bb->next_bb != EXIT_BLOCK_PTR)
{
- rtx tmp = BLOCK_HEAD (i + 1);
- if (GET_CODE (tmp) == NOTE)
- tmp = next_nonnote_insn (tmp);
- if (force_fallthru || insn == tmp)
- cached_make_edge (edge_cache, bb, BASIC_BLOCK (i + 1),
- EDGE_FALLTHRU);
+ if (force_fallthru || insn == bb->next_bb->head)
+ cached_make_edge (edge_cache, bb, bb->next_bb, EDGE_FALLTHRU);
}
}
rtx f;
{
rtx insn, next;
- int i = 0;
rtx bb_note = NULL_RTX;
rtx lvl = NULL_RTX;
rtx trll = NULL_RTX;
rtx head = NULL_RTX;
rtx end = NULL_RTX;
+ basic_block prev = ENTRY_BLOCK_PTR;
/* We process the instructions in a slightly different way than we did
previously. This is so that we see a NOTE_BASIC_BLOCK after we have
if ((GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == BARRIER)
&& head)
{
- create_basic_block_structure (i++, head, end, bb_note);
+ prev = create_basic_block_structure (head, end, bb_note, prev);
head = end = NULL_RTX;
bb_note = NULL_RTX;
}
if (head && control_flow_insn_p (insn))
{
- create_basic_block_structure (i++, head, end, bb_note);
+ prev = create_basic_block_structure (head, end, bb_note, prev);
head = end = NULL_RTX;
bb_note = NULL_RTX;
}
}
if (head != NULL_RTX)
- create_basic_block_structure (i++, head, end, bb_note);
+ create_basic_block_structure (head, end, bb_note, prev);
else if (bb_note)
delete_insn (bb_note);
- if (i != n_basic_blocks)
+ if (last_basic_block != n_basic_blocks)
abort ();
label_value_list = lvl;
int nregs ATTRIBUTE_UNUSED;
FILE *file ATTRIBUTE_UNUSED;
{
- int max_uid;
- timevar_push (TV_CFG);
+ basic_block bb;
- basic_block_for_insn = 0;
+ timevar_push (TV_CFG);
/* Flush out existing data. */
if (basic_block_info != NULL)
{
- int i;
-
clear_edges ();
/* Clear bb->aux on all extant basic blocks. We'll use this as a
tag for reuse during create_basic_block, just in case some pass
copies around basic block notes improperly. */
- for (i = 0; i < n_basic_blocks; ++i)
- BASIC_BLOCK (i)->aux = NULL;
+ FOR_EACH_BB (bb)
+ bb->aux = NULL;
VARRAY_FREE (basic_block_info);
}
n_basic_blocks = count_basic_blocks (f);
+ last_basic_block = 0;
+ ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
+ EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
/* Size the basic block table. The actual structures will be allocated
by find_basic_blocks_1, since we want to keep the structure pointers
find_basic_blocks_1 (f);
- /* Record the block to which an insn belongs. */
- /* ??? This should be done another way, by which (perhaps) a label is
- tagged directly with the basic block that it starts. It is used for
- more than that currently, but IMO that is the only valid use. */
-
- max_uid = get_max_uid ();
-#ifdef AUTO_INC_DEC
- /* Leave space for insns life_analysis makes in some cases for auto-inc.
- These cases are rare, so we don't need too much space. */
- max_uid += max_uid / 10;
-#endif
-
- compute_bb_for_insn (max_uid);
-
/* Discover the edges of our cfg. */
- make_edges (label_value_list, 0, n_basic_blocks - 1, 0);
+ make_edges (label_value_list, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, 0);
/* Do very simple cleanup now, for the benefit of code that runs between
here and cleanup_cfg, e.g. thread_prologue_and_epilogue_insns. */
bb = fallthru->dest;
remove_edge (fallthru);
flow_transfer_insn = NULL_RTX;
- if (LABEL_ALTERNATE_NAME (insn))
+ if (LABEL_ALT_ENTRY_P (insn))
make_edge (ENTRY_BLOCK_PTR, bb, 0);
}
find_many_sub_basic_blocks (blocks)
sbitmap blocks;
{
- int i;
- int min, max;
+ basic_block bb, min, max;
- for (i = 0; i < n_basic_blocks; i++)
- SET_STATE (BASIC_BLOCK (i),
- TEST_BIT (blocks, i) ? BLOCK_TO_SPLIT : BLOCK_ORIGINAL);
+ FOR_EACH_BB (bb)
+ SET_STATE (bb,
+ TEST_BIT (blocks, bb->index) ? BLOCK_TO_SPLIT : BLOCK_ORIGINAL);
- for (i = 0; i < n_basic_blocks; i++)
- if (STATE (BASIC_BLOCK (i)) == BLOCK_TO_SPLIT)
- find_bb_boundaries (BASIC_BLOCK (i));
+ FOR_EACH_BB (bb)
+ if (STATE (bb) == BLOCK_TO_SPLIT)
+ find_bb_boundaries (bb);
- for (i = 0; i < n_basic_blocks; i++)
- if (STATE (BASIC_BLOCK (i)) != BLOCK_ORIGINAL)
+ FOR_EACH_BB (bb)
+ if (STATE (bb) != BLOCK_ORIGINAL)
break;
- min = max = i;
- for (; i < n_basic_blocks; i++)
- if (STATE (BASIC_BLOCK (i)) != BLOCK_ORIGINAL)
- max = i;
+ min = max = bb;
+ for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb)
+ if (STATE (bb) != BLOCK_ORIGINAL)
+ max = bb;
/* Now re-scan and wire in all edges. This expect simple (conditional)
jumps at the end of each new basic blocks. */
/* Update branch probabilities. Expect only (un)conditional jumps
to be created with only the forward edges. */
- for (i = min; i <= max; i++)
+ FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
{
edge e;
- basic_block b = BASIC_BLOCK (i);
- if (STATE (b) == BLOCK_ORIGINAL)
+ if (STATE (bb) == BLOCK_ORIGINAL)
continue;
- if (STATE (b) == BLOCK_NEW)
+ if (STATE (bb) == BLOCK_NEW)
{
- b->count = 0;
- b->frequency = 0;
- for (e = b->pred; e; e=e->pred_next)
+ bb->count = 0;
+ bb->frequency = 0;
+ for (e = bb->pred; e; e = e->pred_next)
{
- b->count += e->count;
- b->frequency += EDGE_FREQUENCY (e);
+ bb->count += e->count;
+ bb->frequency += EDGE_FREQUENCY (e);
}
}
- compute_outgoing_frequencies (b);
+ compute_outgoing_frequencies (bb);
}
- for (i = 0; i < n_basic_blocks; i++)
- SET_STATE (BASIC_BLOCK (i), 0);
+ FOR_EACH_BB (bb)
+ SET_STATE (bb, 0);
}
/* Like above but for single basic block only. */
void
find_sub_basic_blocks (bb)
- basic_block bb;
+ basic_block bb;
{
- int i;
- int min, max;
- basic_block next = (bb->index == n_basic_blocks - 1
- ? NULL : BASIC_BLOCK (bb->index + 1));
+ basic_block min, max, b;
+ basic_block next = bb->next_bb;
- min = bb->index;
+ min = bb;
find_bb_boundaries (bb);
- max = (next ? next->index : n_basic_blocks) - 1;
+ max = next->prev_bb;
/* Now re-scan and wire in all edges. This expect simple (conditional)
jumps at the end of each new basic blocks. */
/* Update branch probabilities. Expect only (un)conditional jumps
to be created with only the forward edges. */
- for (i = min; i <= max; i++)
+ FOR_BB_BETWEEN (b, min, max->next_bb, next_bb)
{
edge e;
- basic_block b = BASIC_BLOCK (i);
- if (i != min)
+ if (b != min)
{
b->count = 0;
b->frequency = 0;
- for (e = b->pred; e; e=e->pred_next)
+ for (e = b->pred; e; e = e->pred_next)
{
b->count += e->count;
b->frequency += EDGE_FREQUENCY (e);
OSDN Git Service
