#define EPILOGUE_USES(REGNO) 0
#endif
-/* 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.
- Separate obstacks are made for nested functions. */
+/* The obstack on which the flow graph components are allocated. */
-extern struct obstack *function_obstack;
+struct obstack flow_obstack;
+static char *flow_firstobj;
/* Number of basic blocks in the current function. */
static void invalidate_mems_from_autoinc PARAMS ((struct propagate_block_info *,
rtx));
+static void invalidate_mems_from_set PARAMS ((struct propagate_block_info *,
+ rtx));
static void remove_fake_successors PARAMS ((basic_block));
-static void flow_nodes_print PARAMS ((const char *, const sbitmap, FILE *));
-static void flow_exits_print PARAMS ((const char *, const edge *, int, FILE *));
-static void flow_loops_cfg_dump PARAMS ((const struct loops *, FILE *));
-static int flow_loop_nested_p PARAMS ((struct loop *, struct loop *));
-static int flow_loop_exits_find PARAMS ((const sbitmap, edge **));
+static void flow_nodes_print PARAMS ((const char *, const sbitmap,
+ FILE *));
+static void flow_edge_list_print PARAMS ((const char *, const edge *,
+ int, FILE *));
+static void flow_loops_cfg_dump PARAMS ((const struct loops *,
+ FILE *));
+static int flow_loop_nested_p PARAMS ((struct loop *,
+ struct loop *));
+static int flow_loop_entry_edges_find PARAMS ((basic_block, const sbitmap,
+ edge **));
+static int flow_loop_exit_edges_find PARAMS ((const sbitmap, edge **));
static int flow_loop_nodes_find PARAMS ((basic_block, basic_block, sbitmap));
static int flow_depth_first_order_compute PARAMS ((int *, int *));
static void flow_dfs_compute_reverse_init
PARAMS ((depth_first_search_ds));
static void flow_dfs_compute_reverse_finish
PARAMS ((depth_first_search_ds));
-static basic_block flow_loop_pre_header_find PARAMS ((basic_block, const sbitmap *));
+static void flow_loop_pre_header_scan PARAMS ((struct loop *));
+static basic_block flow_loop_pre_header_find PARAMS ((basic_block,
+ const sbitmap *));
static void flow_loop_tree_node_add PARAMS ((struct loop *, struct loop *));
static void flow_loops_tree_build PARAMS ((struct loops *));
static int flow_loop_level_compute PARAMS ((struct loop *, int));
static int flow_loops_level_compute PARAMS ((struct loops *));
+static void allocate_bb_life_data PARAMS ((void));
\f
/* Find basic blocks of the current function.
F is the first insn of the function and NREGS the number of register
#endif
}
+void
+check_function_return_warnings ()
+{
+ if (warn_missing_noreturn
+ && !TREE_THIS_VOLATILE (cfun->decl)
+ && EXIT_BLOCK_PTR->pred == NULL)
+ warning ("function might be possible candidate for attribute `noreturn'");
+
+ /* If we have a path to EXIT, then we do return. */
+ if (TREE_THIS_VOLATILE (cfun->decl)
+ && EXIT_BLOCK_PTR->pred != NULL)
+ warning ("`noreturn' function does return");
+
+ /* If the clobber_return_insn appears in some basic block, then we
+ do reach the end without returning a value. */
+ else if (warn_return_type
+ && cfun->x_clobber_return_insn != NULL
+ && EXIT_BLOCK_PTR->pred != NULL)
+ {
+ int max_uid = get_max_uid ();
+
+ /* If clobber_return_insn was excised by jump1, then renumber_insns
+ can make max_uid smaller than the number still recorded in our rtx.
+ That's fine, since this is a quick way of verifying that the insn
+ is no longer in the chain. */
+ if (INSN_UID (cfun->x_clobber_return_insn) < max_uid)
+ {
+ /* Recompute insn->block mapping, since the initial mapping is
+ set before we delete unreachable blocks. */
+ compute_bb_for_insn (max_uid);
+
+ if (BLOCK_FOR_INSN (cfun->x_clobber_return_insn) != NULL)
+ warning ("control reaches end of non-void function");
+ }
+ }
+}
+
/* Count the basic blocks of the function. */
static int
the same lifetime by allocating it off the function obstack
rather than using malloc. */
- bb = (basic_block) obstack_alloc (function_obstack, sizeof (*bb));
+ bb = (basic_block) obstack_alloc (&flow_obstack, sizeof (*bb));
memset (bb, 0, sizeof (*bb));
if (GET_CODE (head) == CODE_LABEL)
if (code == CALL_INSN && SIBLING_CALL_P (insn))
make_edge (edge_cache, bb, EXIT_BLOCK_PTR,
EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
- else
/* If this is a CALL_INSN, then mark it as reaching the active EH
handler for this CALL_INSN. If we're handling asynchronous
Also mark the CALL_INSN as reaching any nonlocal goto handler. */
- if (code == CALL_INSN || asynchronous_exceptions)
+ else if (code == CALL_INSN || asynchronous_exceptions)
{
/* Add any appropriate EH edges. We do this unconditionally
since there may be a REG_EH_REGION or REG_EH_RETHROW note
}
}
\f
+/* Split a block BB after insn INSN creating a new fallthru edge.
+ Return the new edge. Note that to keep other parts of the compiler happy,
+ this function renumbers all the basic blocks so that the new
+ one has a number one greater than the block split. */
+
+edge
+split_block (bb, insn)
+ basic_block bb;
+ rtx insn;
+{
+ basic_block new_bb;
+ edge new_edge;
+ edge e;
+ rtx bb_note;
+ int i, j;
+
+ /* There is no point splitting the block after its end. */
+ if (bb->end == insn)
+ return 0;
+
+ /* Create the new structures. */
+ new_bb = (basic_block) obstack_alloc (&flow_obstack, sizeof (*new_bb));
+ new_edge = (edge) xcalloc (1, sizeof (*new_edge));
+ n_edges++;
+
+ memset (new_bb, 0, sizeof (*new_bb));
+
+ new_bb->head = NEXT_INSN (insn);
+ new_bb->end = bb->end;
+ bb->end = insn;
+
+ new_bb->succ = bb->succ;
+ bb->succ = new_edge;
+ new_bb->pred = new_edge;
+ new_bb->count = bb->count;
+ new_bb->loop_depth = bb->loop_depth;
+
+ new_edge->src = bb;
+ new_edge->dest = new_bb;
+ new_edge->flags = EDGE_FALLTHRU;
+ new_edge->probability = REG_BR_PROB_BASE;
+ new_edge->count = bb->count;
+
+ /* Redirect the src of the successor edges of bb to point to new_bb. */
+ for (e = new_bb->succ; e; e = e->succ_next)
+ e->src = new_bb;
+
+ /* Place the new block just after the block being split. */
+ VARRAY_GROW (basic_block_info, ++n_basic_blocks);
+
+ /* Some parts of the compiler expect blocks to be number in
+ sequential order so insert the new block immediately after the
+ block being split.. */
+ j = bb->index;
+ for (i = n_basic_blocks - 1; i > j + 1; --i)
+ {
+ basic_block tmp = BASIC_BLOCK (i - 1);
+ BASIC_BLOCK (i) = tmp;
+ tmp->index = i;
+ }
+
+ BASIC_BLOCK (i) = new_bb;
+ new_bb->index = i;
+
+ /* Create the basic block note. */
+ bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK,
+ new_bb->head);
+ NOTE_BASIC_BLOCK (bb_note) = new_bb;
+ new_bb->head = bb_note;
+
+ update_bb_for_insn (new_bb);
+
+ if (bb->global_live_at_start)
+ {
+ new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
+ new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
+ COPY_REG_SET (new_bb->global_live_at_end, bb->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->global_live_at_start, bb->global_live_at_end);
+ propagate_block (new_bb, new_bb->global_live_at_start, NULL, 0);
+ COPY_REG_SET (bb->global_live_at_end,
+ new_bb->global_live_at_start);
+ }
+
+ return new_edge;
+}
+
+
/* Split a (typically critical) edge. Return the new block.
Abort on abnormal edges.
}
/* Create the new structures. */
- bb = (basic_block) obstack_alloc (function_obstack, sizeof (*bb));
+ bb = (basic_block) obstack_alloc (&flow_obstack, sizeof (*bb));
edge_out = (edge) xcalloc (1, sizeof (*edge_out));
n_edges++;
/* ??? This info is likely going to be out of date very soon. */
if (old_succ->global_live_at_start)
{
- bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (function_obstack);
- bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (function_obstack);
+ bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
+ bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
COPY_REG_SET (bb->global_live_at_start, old_succ->global_live_at_start);
COPY_REG_SET (bb->global_live_at_end, old_succ->global_live_at_start);
}
rtx prev;
for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
- if (GET_CODE (prev) != NOTE || prev == a->head)
+ if (GET_CODE (prev) != NOTE
+ || NOTE_LINE_NUMBER (prev) == NOTE_INSN_BASIC_BLOCK
+ || prev == a->head)
break;
del_first = a_end;
NOTE_SOURCE_FILE (q) = 0;
}
else
- b->end = q = PREV_INSN (q);
+ q = PREV_INSN (q);
+
+ b->end = q;
}
/* Selectively unlink the sequence. */
CLEAR_HARD_REG_SET (elim_reg_set);
#ifdef ELIMINABLE_REGS
- for (i = 0; i < (int) (sizeof eliminables / sizeof eliminables[0]); i++)
+ for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
#else
SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM);
the case for blocks within infinite loops. */
SET_REGNO_REG_SET (new_live_at_end, STACK_POINTER_REGNUM);
+ /* Similarly for the frame pointer before reload. Any reference
+ to any pseudo before reload is a potential reference of the
+ frame pointer. */
+ if (! reload_completed)
+ SET_REGNO_REG_SET (new_live_at_end, FRAME_POINTER_REGNUM);
+
/* Regs used in phi nodes are not included in
global_live_at_start, since they are live only along a
particular edge. Set those regs that are live because of a
if (bb->local_set == NULL)
{
- bb->local_set = OBSTACK_ALLOC_REG_SET (function_obstack);
+ bb->local_set = OBSTACK_ALLOC_REG_SET (&flow_obstack);
rescan = 1;
}
else
/* Allocate the permanent data structures that represent the results
of life analysis. Not static since used also for stupid life analysis. */
-void
+static void
allocate_bb_life_data ()
{
register int i;
{
basic_block bb = BASIC_BLOCK (i);
- bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (function_obstack);
- bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (function_obstack);
+ bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
+ bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
}
ENTRY_BLOCK_PTR->global_live_at_end
- = OBSTACK_ALLOC_REG_SET (function_obstack);
+ = OBSTACK_ALLOC_REG_SET (&flow_obstack);
EXIT_BLOCK_PTR->global_live_at_start
- = OBSTACK_ALLOC_REG_SET (function_obstack);
+ = OBSTACK_ALLOC_REG_SET (&flow_obstack);
- regs_live_at_setjmp = OBSTACK_ALLOC_REG_SET (function_obstack);
+ regs_live_at_setjmp = OBSTACK_ALLOC_REG_SET (&flow_obstack);
}
void
if (bitmap_operation (diff, bb_true->global_live_at_start,
bb_false->global_live_at_start, BITMAP_XOR))
{
- if (GET_CODE (XEXP (cond_true, 0)) != REG)
+ rtx reg = XEXP (cond_true, 0);
+
+ if (GET_CODE (reg) == SUBREG)
+ reg = SUBREG_REG (reg);
+
+ if (GET_CODE (reg) != REG)
abort ();
- SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (XEXP (cond_true, 0)));
+
+ SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (reg));
/* For each such register, mark it conditionally dead. */
EXECUTE_IF_SET_IN_REG_SET
recording any such that are made and show them dead at the end. We do
a very conservative and simple job here. */
if (optimize
+ && ! (TREE_CODE (TREE_TYPE (current_function_decl)) == FUNCTION_TYPE
+ && (TYPE_RETURNS_STACK_DEPRESSED
+ (TREE_TYPE (current_function_decl))))
&& (flags & PROP_SCAN_DEAD_CODE)
&& (bb->succ == NULL
|| (bb->succ->succ_next == NULL
|| (GET_CODE (XEXP (mem, 0)) == PLUS
&& XEXP (XEXP (mem, 0), 0) == frame_pointer_rtx
&& GET_CODE (XEXP (XEXP (mem, 0), 1)) == CONST_INT))
- pbi->mem_set_list = alloc_EXPR_LIST (0, mem, pbi->mem_set_list);
+ {
+#ifdef AUTO_INC_DEC
+ /* Store a copy of mem, otherwise the address may be scrogged
+ by find_auto_inc. This matters because insn_dead_p uses
+ an rtx_equal_p check to determine if two addresses are
+ the same. This works before find_auto_inc, but fails
+ after find_auto_inc, causing discrepencies between the
+ set of live registers calculated during the
+ calculate_global_regs_live phase and what actually exists
+ after flow completes, leading to aborts. */
+ if (flags & PROP_AUTOINC)
+ mem = shallow_copy_rtx (mem);
+#endif
+ pbi->mem_set_list = alloc_EXPR_LIST (0, mem, pbi->mem_set_list);
+ }
}
}
temp = pbi->mem_set_list;
while (temp)
{
- if (rtx_equal_p (XEXP (temp, 0), r))
+ rtx mem = XEXP (temp, 0);
+
+ if (rtx_equal_p (mem, r))
return 1;
+#ifdef AUTO_INC_DEC
+ /* Check if memory reference matches an auto increment. Only
+ post increment/decrement or modify are valid. */
+ if (GET_MODE (mem) == GET_MODE (r)
+ && (GET_CODE (XEXP (mem, 0)) == POST_DEC
+ || GET_CODE (XEXP (mem, 0)) == POST_INC
+ || GET_CODE (XEXP (mem, 0)) == POST_MODIFY)
+ && GET_MODE (XEXP (mem, 0)) == GET_MODE (r)
+ && rtx_equal_p (XEXP (XEXP (mem, 0), 0), XEXP (r, 0)))
+ return 1;
+#endif
temp = XEXP (temp, 1);
}
}
}
}
+/* EXP is either a MEM or a REG. Remove any dependant entries
+ from pbi->mem_set_list. */
+
+static void
+invalidate_mems_from_set (pbi, exp)
+ struct propagate_block_info *pbi;
+ rtx exp;
+{
+ rtx temp = pbi->mem_set_list;
+ rtx prev = NULL_RTX;
+ rtx next;
+
+ while (temp)
+ {
+ next = XEXP (temp, 1);
+ if ((GET_CODE (exp) == MEM
+ && output_dependence (XEXP (temp, 0), exp))
+ || (GET_CODE (exp) == REG
+ && reg_overlap_mentioned_p (exp, XEXP (temp, 0))))
+ {
+ /* Splice this entry out of the list. */
+ if (prev)
+ XEXP (prev, 1) = next;
+ else
+ pbi->mem_set_list = next;
+ free_EXPR_LIST_node (temp);
+ }
+ else
+ prev = temp;
+ temp = next;
+ }
+}
+
/* Process the registers that are set within X. Their bits are set to
1 in the regset DEAD, because they are dead prior to this insn.
if (optimize && (flags & PROP_SCAN_DEAD_CODE))
{
if (GET_CODE (reg) == MEM || GET_CODE (reg) == REG)
- {
- rtx temp = pbi->mem_set_list;
- rtx prev = NULL_RTX;
- rtx next;
-
- while (temp)
- {
- next = XEXP (temp, 1);
- if ((GET_CODE (reg) == MEM
- && output_dependence (XEXP (temp, 0), reg))
- || (GET_CODE (reg) == REG
- && reg_overlap_mentioned_p (reg, XEXP (temp, 0))))
- {
- /* Splice this entry out of the list. */
- if (prev)
- XEXP (prev, 1) = next;
- else
- pbi->mem_set_list = next;
- free_EXPR_LIST_node (temp);
- }
- else
- prev = temp;
- temp = next;
- }
- }
+ invalidate_mems_from_set (pbi, reg);
/* If the memory reference had embedded side effects (autoincrement
address modes. Then we may need to kill some entries on the
everything that invalidates it. To be safe, don't eliminate any
stores though SP; none of them should be redundant anyway. */
&& ! reg_mentioned_p (stack_pointer_rtx, reg))
- pbi->mem_set_list = alloc_EXPR_LIST (0, reg, pbi->mem_set_list);
+ {
+#ifdef AUTO_INC_DEC
+ /* Store a copy of mem, otherwise the address may be
+ scrogged by find_auto_inc. */
+ if (flags & PROP_AUTOINC)
+ reg = shallow_copy_rtx (reg);
+#endif
+ pbi->mem_set_list = alloc_EXPR_LIST (0, reg, pbi->mem_set_list);
+ }
}
if (GET_CODE (reg) == REG
splay_tree_insert (pbi->reg_cond_dead, regno,
(splay_tree_value) rcli);
- SET_REGNO_REG_SET (pbi->reg_cond_reg,
- REGNO (XEXP (cond, 0)));
+ SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (XEXP (cond, 0)));
/* Not unconditionaly dead. */
return 0;
{
rcli->condition = ncond;
- SET_REGNO_REG_SET (pbi->reg_cond_reg,
- REGNO (XEXP (cond, 0)));
+ SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (XEXP (cond, 0)));
/* Not unconditionaly dead. */
return 0;
Change it to q = p, ...*q..., q = q+size.
Then fall into the usual case. */
rtx insns, temp;
- basic_block bb;
start_sequence ();
emit_move_insn (q, incr_reg);
/* If the original source was dead, it's dead now. */
rtx note;
- while (note = find_reg_note (incr, REG_DEAD, NULL_RTX))
+ while ((note = find_reg_note (incr, REG_DEAD, NULL_RTX)) != NULL_RTX)
{
remove_note (incr, note);
if (XEXP (note, 0) != incr_reg)
splay_tree_remove (pbi->reg_cond_dead, regno);
}
else
- rcli->condition = ncond;
+ {
+ rcli->condition = ncond;
+ SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (XEXP (cond, 0)));
+ }
}
}
else
rcli->condition = not_reg_cond (cond);
splay_tree_insert (pbi->reg_cond_dead, regno,
(splay_tree_value) rcli);
+
+ SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (XEXP (cond, 0)));
}
}
else if (some_was_live)
int regno = REGNO (SET_DEST (x));
rtx y = pbi->reg_next_use[regno];
if (y != 0
+ && SET_DEST (x) != stack_pointer_rtx
&& BLOCK_NUM (y) == BLOCK_NUM (insn)
/* Don't do this if the reg dies, or gets set in y; a standard addressing
mode would be better. */
&& ! dead_or_set_p (y, SET_DEST (x))
&& try_pre_increment (y, SET_DEST (x), amount))
{
- /* We have found a suitable auto-increment
- and already changed insn Y to do it.
- So flush this increment-instruction. */
- PUT_CODE (insn, NOTE);
- NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
- NOTE_SOURCE_FILE (insn) = 0;
- /* Count a reference to this reg for the increment
- insn we are deleting. When a reg is incremented.
- spilling it is worse, so we want to make that
- less likely. */
+ /* We have found a suitable auto-increment and already changed
+ insn Y to do it. So flush this increment instruction. */
+ propagate_block_delete_insn (pbi->bb, insn);
+
+ /* Count a reference to this reg for the increment insn we are
+ deleting. When a reg is incremented, spilling it is worse,
+ so we want to make that less likely. */
if (regno >= FIRST_PSEUDO_REGISTER)
{
REG_N_REFS (regno) += (optimize_size ? 1
: pbi->bb->loop_depth + 1);
REG_N_SETS (regno)++;
}
+
+ /* Flush any remembered memories depending on the value of
+ the incremented register. */
+ invalidate_mems_from_set (pbi, SET_DEST (x));
+
return 1;
}
return 0;
if (comma)
fputc (',', file);
- if (i < (int) (sizeof (bitnames) / sizeof (*bitnames)))
+ if (i < (int) ARRAY_SIZE (bitnames))
fputs (bitnames[i], file);
else
fprintf (file, "%d", i);
}
}
-/* Compute dominator relationships using new flow graph structures. */
-
-void
-compute_flow_dominators (dominators, post_dominators)
- sbitmap *dominators;
- sbitmap *post_dominators;
-{
- int bb;
- sbitmap *temp_bitmap;
- edge e;
- basic_block *worklist, *workend, *qin, *qout;
- int qlen;
-
- /* Allocate a worklist array/queue. Entries are only added to the
- list if they were not already on the list. So the size is
- bounded by the number of basic blocks. */
- worklist = (basic_block *) xmalloc (sizeof (basic_block) * n_basic_blocks);
- workend = &worklist[n_basic_blocks];
-
- temp_bitmap = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
- sbitmap_vector_zero (temp_bitmap, n_basic_blocks);
-
- if (dominators)
- {
- /* The optimistic setting of dominators requires us to put every
- block on the work list initially. */
- qin = qout = worklist;
- for (bb = 0; bb < n_basic_blocks; bb++)
- {
- *qin++ = BASIC_BLOCK (bb);
- BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
- }
- qlen = n_basic_blocks;
- qin = worklist;
-
- /* We want a maximal solution, so initially assume everything dominates
- everything else. */
- sbitmap_vector_ones (dominators, n_basic_blocks);
-
- /* Mark successors of the entry block so we can identify them below. */
- for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
- e->dest->aux = ENTRY_BLOCK_PTR;
-
- /* Iterate until the worklist is empty. */
- while (qlen)
- {
- /* Take the first entry off the worklist. */
- basic_block b = *qout++;
- if (qout >= workend)
- qout = worklist;
- qlen--;
-
- bb = b->index;
-
- /* Compute the intersection of the dominators of all the
- predecessor blocks.
-
- If one of the predecessor blocks is the ENTRY block, then the
- intersection of the dominators of the predecessor blocks is
- defined as the null set. We can identify such blocks by the
- special value in the AUX field in the block structure. */
- if (b->aux == ENTRY_BLOCK_PTR)
- {
- /* Do not clear the aux field for blocks which are
- successors of the ENTRY block. That way we never add
- them to the worklist again.
-
- The intersect of dominators of the preds of this block is
- defined as the null set. */
- sbitmap_zero (temp_bitmap[bb]);
- }
- else
- {
- /* Clear the aux field of this block so it can be added to
- the worklist again if necessary. */
- b->aux = NULL;
- sbitmap_intersection_of_preds (temp_bitmap[bb], dominators, bb);
- }
-
- /* Make sure each block always dominates itself. */
- SET_BIT (temp_bitmap[bb], bb);
-
- /* If the out state of this block changed, then we need to
- add the successors of this block to the worklist if they
- are not already on the worklist. */
- if (sbitmap_a_and_b (dominators[bb], dominators[bb], temp_bitmap[bb]))
- {
- for (e = b->succ; e; e = e->succ_next)
- {
- if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR)
- {
- *qin++ = e->dest;
- if (qin >= workend)
- qin = worklist;
- qlen++;
-
- e->dest->aux = e;
- }
- }
- }
- }
- }
-
- if (post_dominators)
- {
- /* The optimistic setting of dominators requires us to put every
- block on the work list initially. */
- qin = qout = worklist;
- for (bb = 0; bb < n_basic_blocks; bb++)
- {
- *qin++ = BASIC_BLOCK (bb);
- BASIC_BLOCK (bb)->aux = BASIC_BLOCK (bb);
- }
- qlen = n_basic_blocks;
- qin = worklist;
-
- /* We want a maximal solution, so initially assume everything post
- dominates everything else. */
- sbitmap_vector_ones (post_dominators, n_basic_blocks);
-
- /* Mark predecessors of the exit block so we can identify them below. */
- for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
- e->src->aux = EXIT_BLOCK_PTR;
-
- /* Iterate until the worklist is empty. */
- while (qlen)
- {
- /* Take the first entry off the worklist. */
- basic_block b = *qout++;
- if (qout >= workend)
- qout = worklist;
- qlen--;
-
- bb = b->index;
-
- /* Compute the intersection of the post dominators of all the
- successor blocks.
-
- If one of the successor blocks is the EXIT block, then the
- intersection of the dominators of the successor blocks is
- defined as the null set. We can identify such blocks by the
- special value in the AUX field in the block structure. */
- if (b->aux == EXIT_BLOCK_PTR)
- {
- /* Do not clear the aux field for blocks which are
- predecessors of the EXIT block. That way we we never
- add them to the worklist again.
-
- The intersect of dominators of the succs of this block is
- defined as the null set. */
- sbitmap_zero (temp_bitmap[bb]);
- }
- else
- {
- /* Clear the aux field of this block so it can be added to
- the worklist again if necessary. */
- b->aux = NULL;
- sbitmap_intersection_of_succs (temp_bitmap[bb],
- post_dominators, bb);
- }
-
- /* Make sure each block always post dominates itself. */
- SET_BIT (temp_bitmap[bb], bb);
-
- /* If the out state of this block changed, then we need to
- add the successors of this block to the worklist if they
- are not already on the worklist. */
- if (sbitmap_a_and_b (post_dominators[bb],
- post_dominators[bb],
- temp_bitmap[bb]))
- {
- for (e = b->pred; e; e = e->pred_next)
- {
- if (!e->src->aux && e->src != ENTRY_BLOCK_PTR)
- {
- *qin++ = e->src;
- if (qin >= workend)
- qin = worklist;
- qlen++;
-
- e->src->aux = e;
- }
- }
- }
- }
- }
-
- free (worklist);
- free (temp_bitmap);
-}
-
-/* Given DOMINATORS, compute the immediate dominators into IDOM. If a
- block dominates only itself, its entry remains as INVALID_BLOCK. */
-
-void
-compute_immediate_dominators (idom, dominators)
- int *idom;
- sbitmap *dominators;
-{
- sbitmap *tmp;
- int b;
-
- tmp = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
-
- /* Begin with tmp(n) = dom(n) - { n }. */
- for (b = n_basic_blocks; --b >= 0;)
- {
- sbitmap_copy (tmp[b], dominators[b]);
- RESET_BIT (tmp[b], b);
- }
-
- /* Subtract out all of our dominator's dominators. */
- for (b = n_basic_blocks; --b >= 0;)
- {
- sbitmap tmp_b = tmp[b];
- int s;
-
- for (s = n_basic_blocks; --s >= 0;)
- if (TEST_BIT (tmp_b, s))
- sbitmap_difference (tmp_b, tmp_b, tmp[s]);
- }
-
- /* Find the one bit set in the bitmap and put it in the output array. */
- for (b = n_basic_blocks; --b >= 0;)
- {
- int t;
- EXECUTE_IF_SET_IN_SBITMAP (tmp[b], 0, t, { idom[b] = t; });
- }
-
- sbitmap_vector_free (tmp);
-}
-
-/* Given POSTDOMINATORS, compute the immediate postdominators into
- IDOM. If a block is only dominated by itself, its entry remains as
- INVALID_BLOCK. */
-
-void
-compute_immediate_postdominators (idom, postdominators)
- int *idom;
- sbitmap *postdominators;
-{
- compute_immediate_dominators (idom, postdominators);
-}
-
/* Recompute register set/reference counts immediately prior to register
allocation.
return count;
}
+
+/* Update insns block within BB. */
+
+void
+update_bb_for_insn (bb)
+ basic_block bb;
+{
+ rtx insn;
+
+ if (! basic_block_for_insn)
+ return;
+
+ for (insn = bb->head; ; insn = NEXT_INSN (insn))
+ {
+ set_block_for_insn (insn, bb);
+
+ if (insn == bb->end)
+ break;
+ }
+}
+
+
/* Record INSN's block as BB. */
void
\f
/* Dump the list of basic blocks in the bitmap NODES. */
-static void
+static void
flow_nodes_print (str, nodes, file)
const char *str;
const sbitmap nodes;
{
int node;
+ if (! nodes)
+ return;
+
fprintf (file, "%s { ", str);
EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {fprintf (file, "%d ", node);});
fputs ("}\n", file);
}
-/* Dump the list of exiting edges in the array EDGES. */
-static void
-flow_exits_print (str, edges, num_edges, file)
+/* Dump the list of edges in the array EDGE_LIST. */
+
+static void
+flow_edge_list_print (str, edge_list, num_edges, file)
const char *str;
- const edge *edges;
+ const edge *edge_list;
int num_edges;
FILE *file;
{
int i;
+ if (! edge_list)
+ return;
+
fprintf (file, "%s { ", str);
for (i = 0; i < num_edges; i++)
- fprintf (file, "%d->%d ", edges[i]->src->index, edges[i]->dest->index);
+ fprintf (file, "%d->%d ", edge_list[i]->src->index,
+ edge_list[i]->dest->index);
fputs ("}\n", file);
}
+
/* Dump loop related CFG information. */
static void
return sbitmap_a_subset_b_p (loop->nodes, outer->nodes);
}
-/* Dump the loop information specified by LOOPS to the stream FILE. */
+/* Dump the loop information specified by LOOP to the stream FILE
+ using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
void
-flow_loops_dump (loops, file, verbose)
+flow_loop_dump (loop, file, loop_dump_aux, verbose)
+ const struct loop *loop;
+ FILE *file;
+ void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int));
+ int verbose;
+{
+ if (! loop || ! loop->header)
+ return;
+
+ fprintf (file, ";;\n;; Loop %d (%d to %d):%s%s\n",
+ loop->num, INSN_UID (loop->first->head),
+ INSN_UID (loop->last->end),
+ loop->shared ? " shared" : "",
+ loop->invalid ? " invalid" : "");
+ fprintf (file, ";; header %d, latch %d, pre-header %d, first %d, last %d\n",
+ loop->header->index, loop->latch->index,
+ loop->pre_header ? loop->pre_header->index : -1,
+ loop->first->index, loop->last->index);
+ fprintf (file, ";; depth %d, level %d, outer %ld\n",
+ loop->depth, loop->level,
+ (long) (loop->outer ? loop->outer->num : -1));
+
+ if (loop->pre_header_edges)
+ flow_edge_list_print (";; pre-header edges", loop->pre_header_edges,
+ loop->num_pre_header_edges, file);
+ flow_edge_list_print (";; entry edges", loop->entry_edges,
+ loop->num_entries, file);
+ fprintf (file, ";; %d", loop->num_nodes);
+ flow_nodes_print (" nodes", loop->nodes, file);
+ flow_edge_list_print (";; exit edges", loop->exit_edges,
+ loop->num_exits, file);
+ if (loop->exits_doms)
+ flow_nodes_print (";; exit doms", loop->exits_doms, file);
+ if (loop_dump_aux)
+ loop_dump_aux (loop, file, verbose);
+}
+
+
+/* Dump the loop information specified by LOOPS to the stream FILE,
+ using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
+void
+flow_loops_dump (loops, file, loop_dump_aux, verbose)
const struct loops *loops;
FILE *file;
+ void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int));
int verbose;
{
int i;
if (! num_loops || ! file)
return;
- fprintf (file, ";; %d loops found, %d levels\n",
+ fprintf (file, ";; %d loops found, %d levels\n",
num_loops, loops->levels);
for (i = 0; i < num_loops; i++)
{
struct loop *loop = &loops->array[i];
- fprintf (file, ";; loop %d (%d to %d):\n;; header %d, latch %d, pre-header %d, depth %d, level %d, outer %ld\n",
- i, INSN_UID (loop->header->head), INSN_UID (loop->latch->end),
- loop->header->index, loop->latch->index,
- loop->pre_header ? loop->pre_header->index : -1,
- loop->depth, loop->level,
- (long) (loop->outer ? (loop->outer - loops->array) : -1));
- fprintf (file, ";; %d", loop->num_nodes);
- flow_nodes_print (" nodes", loop->nodes, file);
- fprintf (file, ";; %d", loop->num_exits);
- flow_exits_print (" exits", loop->exits, loop->num_exits, file);
+ flow_loop_dump (loop, file, loop_dump_aux, verbose);
if (loop->shared)
{
must be disjoint. */
disjoint = ! flow_loop_nested_p (smaller ? loop : oloop,
smaller ? oloop : loop);
- fprintf (file,
+ fprintf (file,
";; loop header %d shared by loops %d, %d %s\n",
loop->header->index, i, j,
disjoint ? "disjoint" : "nested");
}
}
}
-
- if (verbose)
- {
- /* Print diagnostics to compare our concept of a loop with
- what the loop notes say. */
- if (GET_CODE (PREV_INSN (loop->first->head)) != NOTE
- || NOTE_LINE_NUMBER (PREV_INSN (loop->first->head))
- != NOTE_INSN_LOOP_BEG)
- fprintf (file, ";; No NOTE_INSN_LOOP_BEG at %d\n",
- INSN_UID (PREV_INSN (loop->first->head)));
- if (GET_CODE (NEXT_INSN (loop->last->end)) != NOTE
- || NOTE_LINE_NUMBER (NEXT_INSN (loop->last->end))
- != NOTE_INSN_LOOP_END)
- fprintf (file, ";; No NOTE_INSN_LOOP_END at %d\n",
- INSN_UID (NEXT_INSN (loop->last->end)));
- }
}
if (verbose)
flow_loops_cfg_dump (loops, file);
}
+
/* Free all the memory allocated for LOOPS. */
void
{
struct loop *loop = &loops->array[i];
+ if (loop->pre_header_edges)
+ free (loop->pre_header_edges);
if (loop->nodes)
sbitmap_free (loop->nodes);
- if (loop->exits)
- free (loop->exits);
+ if (loop->entry_edges)
+ free (loop->entry_edges);
+ if (loop->exit_edges)
+ free (loop->exit_edges);
+ if (loop->exits_doms)
+ sbitmap_free (loop->exits_doms);
}
free (loops->array);
loops->array = NULL;
if (loops->cfg.dfs_order)
free (loops->cfg.dfs_order);
- sbitmap_free (loops->shared_headers);
+ if (loops->shared_headers)
+ sbitmap_free (loops->shared_headers);
+ }
+}
+
+
+/* Find the entry edges into the loop with header HEADER and nodes
+ NODES and store in ENTRY_EDGES array. Return the number of entry
+ edges from the loop. */
+
+static int
+flow_loop_entry_edges_find (header, nodes, entry_edges)
+ basic_block header;
+ const sbitmap nodes;
+ edge **entry_edges;
+{
+ edge e;
+ int num_entries;
+
+ *entry_edges = NULL;
+
+ num_entries = 0;
+ for (e = header->pred; e; e = e->pred_next)
+ {
+ basic_block src = e->src;
+
+ if (src == ENTRY_BLOCK_PTR || ! TEST_BIT (nodes, src->index))
+ num_entries++;
+ }
+
+ if (! num_entries)
+ abort ();
+
+ *entry_edges = (edge *) xmalloc (num_entries * sizeof (edge *));
+
+ num_entries = 0;
+ for (e = header->pred; e; e = e->pred_next)
+ {
+ basic_block src = e->src;
+
+ if (src == ENTRY_BLOCK_PTR || ! TEST_BIT (nodes, src->index))
+ (*entry_edges)[num_entries++] = e;
}
+
+ return num_entries;
}
-/* Find the exits from the loop using the bitmap of loop nodes NODES
- and store in EXITS array. Return the number of exits from the
- loop. */
+
+/* Find the exit edges from the loop using the bitmap of loop nodes
+ NODES and store in EXIT_EDGES array. Return the number of
+ exit edges from the loop. */
static int
-flow_loop_exits_find (nodes, exits)
+flow_loop_exit_edges_find (nodes, exit_edges)
const sbitmap nodes;
- edge **exits;
+ edge **exit_edges;
{
edge e;
int node;
int num_exits;
- *exits = NULL;
+ *exit_edges = NULL;
/* Check all nodes within the loop to see if there are any
successors not in the loop. Note that a node may have multiple
- exiting edges. */
+ exiting edges ????? A node can have one jumping edge and one fallthru
+ edge so only one of these can exit the loop. */
num_exits = 0;
EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {
for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next)
{
- basic_block dest = e->dest;
+ basic_block dest = e->dest;
if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index))
num_exits++;
if (! num_exits)
return 0;
- *exits = (edge *) xmalloc (num_exits * sizeof (edge *));
+ *exit_edges = (edge *) xmalloc (num_exits * sizeof (edge *));
/* Store all exiting edges into an array. */
num_exits = 0;
EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {
for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next)
{
- basic_block dest = e->dest;
+ basic_block dest = e->dest;
if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index))
- (*exits)[num_exits++] = e;
+ (*exit_edges)[num_exits++] = e;
}
});
return num_exits;
}
+
/* Find the nodes contained within the loop with header HEADER and
latch LATCH and store in NODES. Return the number of nodes within
the loop. */
return;
}
+
+/* Find the root node of the loop pre-header extended basic block and
+ the edges along the trace from the root node to the loop header. */
+
+static void
+flow_loop_pre_header_scan (loop)
+ struct loop *loop;
+{
+ int num = 0;
+ basic_block ebb;
+
+ loop->num_pre_header_edges = 0;
+
+ if (loop->num_entries != 1)
+ return;
+
+ ebb = loop->entry_edges[0]->src;
+
+ if (ebb != ENTRY_BLOCK_PTR)
+ {
+ edge e;
+
+ /* Count number of edges along trace from loop header to
+ root of pre-header extended basic block. Usually this is
+ only one or two edges. */
+ num++;
+ while (ebb->pred->src != ENTRY_BLOCK_PTR && ! ebb->pred->pred_next)
+ {
+ ebb = ebb->pred->src;
+ num++;
+ }
+
+ loop->pre_header_edges = (edge *) xmalloc (num * sizeof (edge *));
+ loop->num_pre_header_edges = num;
+
+ /* Store edges in order that they are followed. The source
+ of the first edge is the root node of the pre-header extended
+ basic block and the destination of the last last edge is
+ the loop header. */
+ for (e = loop->entry_edges[0]; num; e = e->src->pred)
+ {
+ loop->pre_header_edges[--num] = e;
+ }
+ }
+}
+
+
/* Return the block for the pre-header of the loop with header
HEADER where DOM specifies the dominator information. Return NULL if
there is no pre-header. */
return levels;
}
+
/* Find all the natural loops in the function and save in LOOPS structure
and recalculate loop_depth information in basic block structures.
+ FLAGS controls which loop information is collected.
Return the number of natural loops found. */
int
-flow_loops_find (loops)
+flow_loops_find (loops, flags)
struct loops *loops;
+ int flags;
{
int i;
int b;
int *dfs_order;
int *rc_order;
- loops->num = 0;
- loops->array = NULL;
- loops->tree = NULL;
- dfs_order = NULL;
- rc_order = NULL;
+ /* This function cannot be repeatedly called with different
+ flags to build up the loop information. The loop tree
+ must always be built if this function is called. */
+ if (! (flags & LOOP_TREE))
+ abort ();
+
+ memset (loops, 0, sizeof (*loops));
/* Taking care of this degenerate case makes the rest of
this code simpler. */
if (n_basic_blocks == 0)
return 0;
+ dfs_order = NULL;
+ rc_order = NULL;
+
/* Compute the dominators. */
dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
- compute_flow_dominators (dom, NULL);
+ calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
/* Count the number of loop edges (back edges). This should be the
- same as the number of natural loops. Also clear the loop_depth
- and as we work from inner->outer in a loop nest we call
- find_loop_nodes_find which will increment loop_depth for nodes
- within the current loop, which happens to enclose inner loops. */
+ same as the number of natural loops. */
num_loops = 0;
for (b = 0; b < n_basic_blocks; b++)
{
- BASIC_BLOCK (b)->loop_depth = 0;
- for (e = BASIC_BLOCK (b)->pred; e; e = e->pred_next)
+ basic_block header;
+
+ header = BASIC_BLOCK (b);
+ header->loop_depth = 0;
+
+ for (e = header->pred; e; e = e->pred_next)
{
basic_block latch = e->src;
loop. It also has single back edge to the header
from a latch node. Note that multiple natural loops
may share the same header. */
+ if (b != header->index)
+ abort ();
+
if (latch != ENTRY_BLOCK_PTR && TEST_BIT (dom[latch->index], b))
num_loops++;
}
{
basic_block header;
- /* Search the nodes of the CFG in DFS order that we can find
- outer loops first. */
+ /* Search the nodes of the CFG in reverse completion order
+ so that we can find outer loops first. */
header = BASIC_BLOCK (rc_order[b]);
/* Look for all the possible latch blocks for this header. */
loop->latch = latch;
loop->num = num_loops;
- /* Keep track of blocks that are loop headers so
- that we can tell which loops should be merged. */
- if (TEST_BIT (headers, header->index))
- SET_BIT (loops->shared_headers, header->index);
- SET_BIT (headers, header->index);
-
- /* Find nodes contained within the loop. */
- loop->nodes = sbitmap_alloc (n_basic_blocks);
- loop->num_nodes
- = flow_loop_nodes_find (header, latch, loop->nodes);
-
- /* Compute first and last blocks within the loop.
- These are often the same as the loop header and
- loop latch respectively, but this is not always
- the case. */
- loop->first
- = BASIC_BLOCK (sbitmap_first_set_bit (loop->nodes));
- loop->last
- = BASIC_BLOCK (sbitmap_last_set_bit (loop->nodes));
-
- /* Find edges which exit the loop. Note that a node
- may have several exit edges. */
- loop->num_exits
- = flow_loop_exits_find (loop->nodes, &loop->exits);
-
- /* Look to see if the loop has a pre-header node. */
- loop->pre_header = flow_loop_pre_header_find (header, dom);
-
num_loops++;
}
}
}
+ for (i = 0; i < num_loops; i++)
+ {
+ struct loop *loop = &loops->array[i];
+ int j;
+
+ /* Keep track of blocks that are loop headers so
+ that we can tell which loops should be merged. */
+ if (TEST_BIT (headers, loop->header->index))
+ SET_BIT (loops->shared_headers, loop->header->index);
+ SET_BIT (headers, loop->header->index);
+
+ /* Find nodes contained within the loop. */
+ loop->nodes = sbitmap_alloc (n_basic_blocks);
+ loop->num_nodes
+ = flow_loop_nodes_find (loop->header, loop->latch, loop->nodes);
+
+ /* Compute first and last blocks within the loop.
+ These are often the same as the loop header and
+ loop latch respectively, but this is not always
+ the case. */
+ loop->first
+ = BASIC_BLOCK (sbitmap_first_set_bit (loop->nodes));
+ loop->last
+ = BASIC_BLOCK (sbitmap_last_set_bit (loop->nodes));
+
+ if (flags & LOOP_EDGES)
+ {
+ /* Find edges which enter the loop header.
+ Note that the entry edges should only
+ enter the header of a natural loop. */
+ loop->num_entries
+ = flow_loop_entry_edges_find (loop->header,
+ loop->nodes,
+ &loop->entry_edges);
+
+ /* Find edges which exit the loop. */
+ loop->num_exits
+ = flow_loop_exit_edges_find (loop->nodes,
+ &loop->exit_edges);
+
+ /* Determine which loop nodes dominate all the exits
+ of the loop. */
+ loop->exits_doms = sbitmap_alloc (n_basic_blocks);
+ sbitmap_copy (loop->exits_doms, loop->nodes);
+ for (j = 0; j < loop->num_exits; j++)
+ sbitmap_a_and_b (loop->exits_doms, loop->exits_doms,
+ dom[loop->exit_edges[j]->src->index]);
+
+ /* The header of a natural loop must dominate
+ all exits. */
+ if (! TEST_BIT (loop->exits_doms, loop->header->index))
+ abort ();
+ }
+
+ if (flags & LOOP_PRE_HEADER)
+ {
+ /* Look to see if the loop has a pre-header node. */
+ loop->pre_header
+ = flow_loop_pre_header_find (loop->header, dom);
+
+ flow_loop_pre_header_scan (loop);
+ }
+ }
+
/* Natural loops with shared headers may either be disjoint or
nested. Disjoint loops with shared headers cannot be inner
loops and should be merged. For now just mark loops that share
return num_loops;
}
+
+/* Update the information regarding the loops in the CFG
+ specified by LOOPS. */
+int
+flow_loops_update (loops, flags)
+ struct loops *loops;
+ int flags;
+{
+ /* One day we may want to update the current loop data. For now
+ throw away the old stuff and rebuild what we need. */
+ if (loops->array)
+ flow_loops_free (loops);
+
+ return flow_loops_find (loops, flags);
+}
+
+
/* Return non-zero if edge E enters header of LOOP from outside of LOOP. */
int
SET_HARD_REG_BIT (*to, i);
});
}
+
+/* Called once at intialization time. */
+
+void
+init_flow ()
+{
+ static int initialized;
+
+ if (!initialized)
+ {
+ gcc_obstack_init (&flow_obstack);
+ flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0);
+ initialized = 1;
+ }
+ else
+ {
+ obstack_free (&flow_obstack, flow_firstobj);
+ flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0);
+ }
+}
OSDN Git Service
