#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 *));
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
rtx bb_note;
int i, j;
- if (BLOCK_FOR_INSN (insn) != bb)
- abort ();
-
/* 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 (function_obstack, sizeof (*new_bb));
+ new_bb = (basic_block) obstack_alloc (&flow_obstack, sizeof (*new_bb));
new_edge = (edge) xcalloc (1, sizeof (*new_edge));
n_edges++;
if (bb->global_live_at_start)
{
- new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (function_obstack);
- new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (function_obstack);
+ 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
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 (new_bb->global_live_at_end,
+ COPY_REG_SET (bb->global_live_at_end,
new_bb->global_live_at_start);
}
}
/* 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);
}
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
|| (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);
+ }
}
}
}
}
+/* 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
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;
}
}
-/* 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.
flow_loop_dump (loop, file, loop_dump_aux, verbose)
const struct loop *loop;
FILE *file;
- void (*loop_dump_aux)(const struct loop *, FILE *, int);
+ void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int));
int verbose;
{
if (! loop || ! loop->header)
loop->depth, loop->level,
(long) (loop->outer ? loop->outer->num : -1));
- flow_edge_list_print (";; entry edges", loop->entry_edges,
+ 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,
+ 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);
}
flow_loops_dump (loops, file, loop_dump_aux, verbose)
const struct loops *loops;
FILE *file;
- void (*loop_dump_aux)(const struct loop *, FILE *, int);
+ void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int));
int verbose;
{
int i;
{
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->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);
}
}
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 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);
-
- /* 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
