/* Control flow graph analysis 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, 2003, 2004 Free Software Foundation, Inc.
This file is part of GCC.
/* This file contains various simple utilities to analyze the CFG. */
#include "config.h"
#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
#include "rtl.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "insn-config.h"
#include "recog.h"
#include "toplev.h"
-#include "obstack.h"
#include "tm_p.h"
/* Store the data structures necessary for depth-first search. */
};
typedef struct depth_first_search_dsS *depth_first_search_ds;
-static void flow_dfs_compute_reverse_init
- PARAMS ((depth_first_search_ds));
-static void flow_dfs_compute_reverse_add_bb
- PARAMS ((depth_first_search_ds, basic_block));
-static basic_block flow_dfs_compute_reverse_execute
- PARAMS ((depth_first_search_ds));
-static void flow_dfs_compute_reverse_finish
- PARAMS ((depth_first_search_ds));
-static void remove_fake_successors PARAMS ((basic_block));
-static bool need_fake_edge_p PARAMS ((rtx));
+static void flow_dfs_compute_reverse_init (depth_first_search_ds);
+static void flow_dfs_compute_reverse_add_bb (depth_first_search_ds,
+ basic_block);
+static basic_block flow_dfs_compute_reverse_execute (depth_first_search_ds);
+static void flow_dfs_compute_reverse_finish (depth_first_search_ds);
+static void remove_fake_successors (basic_block);
+static bool need_fake_edge_p (rtx);
+static bool flow_active_insn_p (rtx);
\f
+/* Like active_insn_p, except keep the return value clobber around
+ even after reload. */
+
+static bool
+flow_active_insn_p (rtx insn)
+{
+ if (active_insn_p (insn))
+ return true;
+
+ /* A clobber of the function return value exists for buggy
+ programs that fail to return a value. Its effect is to
+ keep the return value from being live across the entire
+ function. If we allow it to be skipped, we introduce the
+ possibility for register livetime aborts. */
+ if (GET_CODE (PATTERN (insn)) == CLOBBER
+ && GET_CODE (XEXP (PATTERN (insn), 0)) == REG
+ && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0)))
+ return true;
+
+ return false;
+}
+
/* Return true if the block has no effect and only forwards control flow to
its single destination. */
bool
-forwarder_block_p (bb)
- basic_block bb;
+forwarder_block_p (basic_block bb)
{
rtx insn;
|| !bb->succ || bb->succ->succ_next)
return false;
- for (insn = bb->head; insn != bb->end; insn = NEXT_INSN (insn))
- if (INSN_P (insn) && active_insn_p (insn))
+ for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
+ if (INSN_P (insn) && flow_active_insn_p (insn))
return false;
return (!INSN_P (insn)
|| (GET_CODE (insn) == JUMP_INSN && simplejump_p (insn))
- || !active_insn_p (insn));
+ || !flow_active_insn_p (insn));
}
/* Return nonzero if we can reach target from src by falling through. */
bool
-can_fallthru (src, target)
- basic_block src, target;
+can_fallthru (basic_block src, basic_block target)
{
- rtx insn = src->end;
- rtx insn2 = target->head;
+ rtx insn = BB_END (src);
+ rtx insn2 = target == EXIT_BLOCK_PTR ? NULL : BB_HEAD (target);
if (src->next_bb != target)
return 0;
- if (!active_insn_p (insn2))
+ if (insn2 && !active_insn_p (insn2))
insn2 = next_active_insn (insn2);
/* ??? Later we may add code to move jump tables offline. */
}
\f
/* Mark the back edges in DFS traversal.
- Return non-zero if a loop (natural or otherwise) is present.
+ Return nonzero if a loop (natural or otherwise) is present.
Inspired by Depth_First_Search_PP described in:
Advanced Compiler Design and Implementation
and heavily borrowed from flow_depth_first_order_compute. */
bool
-mark_dfs_back_edges ()
+mark_dfs_back_edges (void)
{
edge *stack;
int *pre;
bool found = false;
/* Allocate the preorder and postorder number arrays. */
- pre = (int *) xcalloc (last_basic_block, sizeof (int));
- post = (int *) xcalloc (last_basic_block, sizeof (int));
+ pre = xcalloc (last_basic_block, sizeof (int));
+ post = xcalloc (last_basic_block, sizeof (int));
/* Allocate stack for back-tracking up CFG. */
- stack = (edge *) xmalloc ((num_basic_blocks + 1) * sizeof (edge));
+ stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge));
sp = 0;
/* Allocate bitmap to track nodes that have been visited. */
e->flags &= ~EDGE_DFS_BACK;
/* Check if the edge destination has been visited yet. */
- if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->sindex))
+ if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
{
/* Mark that we have visited the destination. */
- SET_BIT (visited, dest->sindex);
+ SET_BIT (visited, dest->index);
- pre[dest->sindex] = prenum++;
+ pre[dest->index] = prenum++;
if (dest->succ)
{
/* Since the DEST node has been visited for the first
stack[sp++] = dest->succ;
}
else
- post[dest->sindex] = postnum++;
+ post[dest->index] = postnum++;
}
else
{
if (dest != EXIT_BLOCK_PTR && src != ENTRY_BLOCK_PTR
- && pre[src->sindex] >= pre[dest->sindex]
- && post[dest->sindex] == 0)
+ && pre[src->index] >= pre[dest->index]
+ && post[dest->index] == 0)
e->flags |= EDGE_DFS_BACK, found = true;
if (! e->succ_next && src != ENTRY_BLOCK_PTR)
- post[src->sindex] = postnum++;
+ post[src->index] = postnum++;
if (e->succ_next)
stack[sp - 1] = e->succ_next;
/* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru. */
void
-set_edge_can_fallthru_flag ()
+set_edge_can_fallthru_flag (void)
{
basic_block bb;
- FOR_ALL_BB (bb)
+ FOR_EACH_BB (bb)
{
edge e;
- /* The FALLTHRU edge is also CAN_FALLTHRU edge. */
for (e = bb->succ; e; e = e->succ_next)
- if (e->flags & EDGE_FALLTHRU)
- e->flags |= EDGE_CAN_FALLTHRU;
+ {
+ e->flags &= ~EDGE_CAN_FALLTHRU;
+
+ /* The FALLTHRU edge is also CAN_FALLTHRU edge. */
+ if (e->flags & EDGE_FALLTHRU)
+ e->flags |= EDGE_CAN_FALLTHRU;
+ }
- /* If the BB ends with an invertable condjump all (2) edges are
+ /* If the BB ends with an invertible condjump all (2) edges are
CAN_FALLTHRU edges. */
if (!bb->succ || !bb->succ->succ_next || bb->succ->succ_next->succ_next)
continue;
- if (!any_condjump_p (bb->end))
+ if (!any_condjump_p (BB_END (bb)))
continue;
- if (!invert_jump (bb->end, JUMP_LABEL (bb->end), 0))
+ if (!invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0))
continue;
- invert_jump (bb->end, JUMP_LABEL (bb->end), 0);
+ invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0);
bb->succ->flags |= EDGE_CAN_FALLTHRU;
bb->succ->succ_next->flags |= EDGE_CAN_FALLTHRU;
}
Helper function for the flow_call_edges_add. */
static bool
-need_fake_edge_p (insn)
- rtx insn;
+need_fake_edge_p (rtx insn)
{
if (!INSN_P (insn))
return false;
that all subsequent instructions must be executed. */
int
-flow_call_edges_add (blocks)
- sbitmap blocks;
+flow_call_edges_add (sbitmap blocks)
{
int i;
int blocks_split = 0;
int last_bb = last_basic_block;
bool check_last_block = false;
- if (num_basic_blocks == 0)
+ if (n_basic_blocks == 0)
return 0;
if (! blocks)
check_last_block = true;
else
- check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->sindex);
+ check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
/* In the last basic block, before epilogue generation, there will be
a fallthru edge to EXIT. Special care is required if the last insn
if (check_last_block)
{
basic_block bb = EXIT_BLOCK_PTR->prev_bb;
- rtx insn = bb->end;
+ rtx insn = BB_END (bb);
/* Back up past insns that must be kept in the same block as a call. */
- while (insn != bb->head
+ while (insn != BB_HEAD (bb)
&& keep_with_call_p (insn))
insn = PREV_INSN (insn);
for (e = bb->succ; e; e = e->succ_next)
if (e->dest == EXIT_BLOCK_PTR)
- break;
-
- insert_insn_on_edge (gen_rtx_USE (VOIDmode, const0_rtx), e);
- commit_edge_insertions ();
+ {
+ insert_insn_on_edge (gen_rtx_USE (VOIDmode, const0_rtx), e);
+ commit_edge_insertions ();
+ break;
+ }
}
}
for (i = 0; i < last_bb; i++)
{
basic_block bb = BASIC_BLOCK (i);
+ rtx libcall_end = NULL_RTX;
rtx insn;
rtx prev_insn;
if (blocks && !TEST_BIT (blocks, i))
continue;
- for (insn = bb->end; ; insn = prev_insn)
+ for (insn = BB_END (bb); ; insn = prev_insn)
{
prev_insn = PREV_INSN (insn);
if (need_fake_edge_p (insn))
edge e;
rtx split_at_insn = insn;
+ /* Don't split libcalls. */
+ if (libcall_end)
+ split_at_insn = libcall_end;
+
/* Don't split the block between a call and an insn that should
remain in the same block as the call. */
- if (GET_CODE (insn) == CALL_INSN)
- while (split_at_insn != bb->end
+ else if (GET_CODE (insn) == CALL_INSN)
+ while (split_at_insn != BB_END (bb)
&& keep_with_call_p (NEXT_INSN (split_at_insn)))
split_at_insn = NEXT_INSN (split_at_insn);
cause us to mark that edge as fake and remove it later. */
#ifdef ENABLE_CHECKING
- if (split_at_insn == bb->end)
+ if (split_at_insn == BB_END (bb))
for (e = bb->succ; e; e = e->succ_next)
if (e->dest == EXIT_BLOCK_PTR)
abort ();
/* Note that the following may create a new basic block
and renumber the existing basic blocks. */
- if (split_at_insn != bb->end)
+ if (split_at_insn != BB_END (bb))
{
e = split_block (bb, split_at_insn);
if (e)
make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
}
- if (insn == bb->head)
+ /* Watch out for REG_LIBCALL/REG_RETVAL notes so that we know
+ whether we are currently in a libcall or not. Remember that
+ we are scanning backwards! */
+ if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
+ libcall_end = insn;
+ if (find_reg_note (insn, REG_LIBCALL, NULL_RTX))
+ libcall_end = NULL_RTX;
+
+ if (insn == BB_HEAD (bb))
break;
}
}
}
/* Find unreachable blocks. An unreachable block will have 0 in
- the reachable bit in block->flags. A non-zero value indicates the
+ the reachable bit in block->flags. A nonzero value indicates the
block is reachable. */
void
-find_unreachable_blocks ()
+find_unreachable_blocks (void)
{
edge e;
basic_block *tos, *worklist, bb;
- tos = worklist =
- (basic_block *) xmalloc (sizeof (basic_block) * num_basic_blocks);
+ tos = worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
/* Clear all the reachability flags. */
- FOR_ALL_BB (bb)
+ FOR_EACH_BB (bb)
bb->flags &= ~BB_REACHABLE;
/* Add our starting points to the worklist. Almost always there will
and the data structure is filled in. */
struct edge_list *
-create_edge_list ()
+create_edge_list (void)
{
struct edge_list *elist;
edge e;
int block_count;
basic_block bb;
- block_count = num_basic_blocks + 2; /* Include the entry and exit blocks. */
+ block_count = n_basic_blocks + 2; /* Include the entry and exit blocks. */
num_edges = 0;
edges on each basic block. */
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
{
-
for (e = bb->succ; e; e = e->succ_next)
num_edges++;
}
- elist = (struct edge_list *) xmalloc (sizeof (struct edge_list));
+ elist = xmalloc (sizeof (struct edge_list));
elist->num_blocks = block_count;
elist->num_edges = num_edges;
- elist->index_to_edge = (edge *) xmalloc (sizeof (edge) * num_edges);
+ elist->index_to_edge = xmalloc (sizeof (edge) * num_edges);
num_edges = 0;
/* This function free's memory associated with an edge list. */
void
-free_edge_list (elist)
- struct edge_list *elist;
+free_edge_list (struct edge_list *elist)
{
if (elist)
{
/* This function provides debug output showing an edge list. */
void
-print_edge_list (f, elist)
- FILE *f;
- struct edge_list *elist;
+print_edge_list (FILE *f, struct edge_list *elist)
{
int x;
if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR)
fprintf (f, "entry,");
else
- fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->sindex);
+ fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index);
if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR)
fprintf (f, "exit)\n");
else
- fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->sindex);
+ fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index);
}
}
extra edges. */
void
-verify_edge_list (f, elist)
- FILE *f;
- struct edge_list *elist;
+verify_edge_list (FILE *f, struct edge_list *elist)
{
- int index, pred, succ;
+ int pred, succ, index;
edge e;
basic_block bb, p, s;
{
for (e = bb->succ; e; e = e->succ_next)
{
- pred = e->src->sindex;
- succ = e->dest->sindex;
+ pred = e->src->index;
+ succ = e->dest->index;
index = EDGE_INDEX (elist, e->src, e->dest);
if (index == EDGE_INDEX_NO_EDGE)
{
continue;
}
- if (INDEX_EDGE_PRED_BB (elist, index)->sindex != pred)
+ if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
fprintf (f, "*p* Pred for index %d should be %d not %d\n",
- index, pred, INDEX_EDGE_PRED_BB (elist, index)->sindex);
- if (INDEX_EDGE_SUCC_BB (elist, index)->sindex != succ)
+ index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
+ if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
fprintf (f, "*p* Succ for index %d should be %d not %d\n",
- index, succ, INDEX_EDGE_SUCC_BB (elist, index)->sindex);
+ index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
}
}
- /* We've verified that all the edges are in the list, no lets make sure
+ /* We've verified that all the edges are in the list, now lets make sure
there are no spurious edges in the list. */
FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
- FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
+ FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
{
int found_edge = 0;
if (EDGE_INDEX (elist, p, s)
== EDGE_INDEX_NO_EDGE && found_edge != 0)
fprintf (f, "*** Edge (%d, %d) appears to not have an index\n",
- p->sindex, s->sindex);
+ p->index, s->index);
if (EDGE_INDEX (elist, p, s)
!= EDGE_INDEX_NO_EDGE && found_edge == 0)
fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
- p->sindex, s->sindex, EDGE_INDEX (elist, p, s));
+ p->index, s->index, EDGE_INDEX (elist, p, s));
}
-
}
/* This routine will determine what, if any, edge there is between
a specified predecessor and successor. */
int
-find_edge_index (edge_list, pred, succ)
- struct edge_list *edge_list;
- basic_block pred, succ;
+find_edge_index (struct edge_list *edge_list, basic_block pred, basic_block succ)
{
int x;
/* Dump the list of basic blocks in the bitmap NODES. */
void
-flow_nodes_print (str, nodes, file)
- const char *str;
- const sbitmap nodes;
- FILE *file;
+flow_nodes_print (const char *str, const sbitmap nodes, FILE *file)
{
int node;
/* Dump the list of edges in the array EDGE_LIST. */
void
-flow_edge_list_print (str, edge_list, num_edges, file)
- const char *str;
- const edge *edge_list;
- int num_edges;
- FILE *file;
+flow_edge_list_print (const char *str, const edge *edge_list, int num_edges, FILE *file)
{
int i;
fprintf (file, "%s { ", str);
for (i = 0; i < num_edges; i++)
- fprintf (file, "%d->%d ", edge_list[i]->src->sindex,
- edge_list[i]->dest->sindex);
+ fprintf (file, "%d->%d ", edge_list[i]->src->index,
+ edge_list[i]->dest->index);
fputs ("}\n", file);
}
list it is in. */
static void
-remove_fake_successors (bb)
- basic_block bb;
+remove_fake_successors (basic_block bb)
{
edge e;
fake predecessors. */
void
-remove_fake_edges ()
+remove_fake_edges (void)
{
basic_block bb;
edges to exist. */
void
-add_noreturn_fake_exit_edges ()
+add_noreturn_fake_exit_edges (void)
{
basic_block bb;
- FOR_ALL_BB (bb)
+ FOR_EACH_BB (bb)
if (bb->succ == NULL)
make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
}
nodes not reachable from the exit block. */
void
-connect_infinite_loops_to_exit ()
+connect_infinite_loops_to_exit (void)
{
basic_block unvisited_block;
struct depth_first_search_dsS dfs_ds;
return;
}
\f
-/* Compute reverse top sort order */
+/* Compute reverse top sort order. */
void
-flow_reverse_top_sort_order_compute (rts_order)
- int *rts_order;
+flow_reverse_top_sort_order_compute (int *rts_order)
{
edge *stack;
int sp;
sbitmap visited;
/* Allocate stack for back-tracking up CFG. */
- stack = (edge *) xmalloc ((num_basic_blocks + 1) * sizeof (edge));
+ stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge));
sp = 0;
/* Allocate bitmap to track nodes that have been visited. */
dest = e->dest;
/* Check if the edge destination has been visited yet. */
- if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->sindex))
+ if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
{
/* Mark that we have visited the destination. */
- SET_BIT (visited, dest->sindex);
+ SET_BIT (visited, dest->index);
if (dest->succ)
/* Since the DEST node has been visited for the first
time, check its successors. */
stack[sp++] = dest->succ;
else
- rts_order[postnum++] = dest->sindex;
+ rts_order[postnum++] = dest->index;
}
else
{
if (! e->succ_next && src != ENTRY_BLOCK_PTR)
- rts_order[postnum++] = src->sindex;
+ rts_order[postnum++] = src->index;
if (e->succ_next)
stack[sp - 1] = e->succ_next;
}
/* Compute the depth first search order and store in the array
- DFS_ORDER if non-zero, marking the nodes visited in VISITED. If
- RC_ORDER is non-zero, return the reverse completion number for each
+ DFS_ORDER if nonzero, marking the nodes visited in VISITED. If
+ RC_ORDER is nonzero, return the reverse completion number for each
node. Returns the number of nodes visited. A depth first search
tries to get as far away from the starting point as quickly as
possible. */
int
-flow_depth_first_order_compute (dfs_order, rc_order)
- int *dfs_order;
- int *rc_order;
+flow_depth_first_order_compute (int *dfs_order, int *rc_order)
{
edge *stack;
int sp;
int dfsnum = 0;
- int rcnum = num_basic_blocks - 1;
+ int rcnum = n_basic_blocks - 1;
sbitmap visited;
/* Allocate stack for back-tracking up CFG. */
- stack = (edge *) xmalloc ((num_basic_blocks + 1) * sizeof (edge));
+ stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge));
sp = 0;
/* Allocate bitmap to track nodes that have been visited. */
dest = e->dest;
/* Check if the edge destination has been visited yet. */
- if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->sindex))
+ if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
{
/* Mark that we have visited the destination. */
- SET_BIT (visited, dest->sindex);
+ SET_BIT (visited, dest->index);
if (dfs_order)
- dfs_order[dfsnum] = dest->sindex;
+ dfs_order[dfsnum] = dest->index;
dfsnum++;
else if (rc_order)
/* There are no successors for the DEST node so assign
its reverse completion number. */
- rc_order[rcnum--] = dest->sindex;
+ rc_order[rcnum--] = dest->index;
}
else
{
&& rc_order)
/* There are no more successors for the SRC node
so assign its reverse completion number. */
- rc_order[rcnum--] = src->sindex;
+ rc_order[rcnum--] = src->index;
if (e->succ_next)
stack[sp - 1] = e->succ_next;
sbitmap_free (visited);
/* The number of nodes visited should not be greater than
- num_basic_blocks. */
- if (dfsnum > num_basic_blocks)
+ n_basic_blocks. */
+ if (dfsnum > n_basic_blocks)
abort ();
/* There are some nodes left in the CFG that are unreachable. */
- if (dfsnum < num_basic_blocks)
+ if (dfsnum < n_basic_blocks)
abort ();
return dfsnum;
2) Walking the resulting tree from right to left. */
void
-flow_preorder_transversal_compute (pot_order)
- int *pot_order;
+flow_preorder_transversal_compute (int *pot_order)
{
edge e;
edge *stack;
basic_block bb;
/* Allocate stack for back-tracking up CFG. */
- stack = (edge *) xmalloc ((num_basic_blocks + 1) * sizeof (edge));
+ stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge));
sp = 0;
/* Allocate the tree. */
- dfst = (struct dfst_node *) xcalloc (last_basic_block,
- sizeof (struct dfst_node));
+ dfst = xcalloc (last_basic_block, sizeof (struct dfst_node));
- FOR_ALL_BB (bb)
+ FOR_EACH_BB (bb)
{
max_successors = 0;
for (e = bb->succ; e; e = e->succ_next)
max_successors++;
- if (max_successors)
- dfst[bb->sindex].node
- = (struct dfst_node **) xcalloc (max_successors,
- sizeof (struct dfst_node *));
+ dfst[bb->index].node
+ = (max_successors
+ ? xcalloc (max_successors, sizeof (struct dfst_node *)) : NULL);
}
/* Allocate bitmap to track nodes that have been visited. */
dest = e->dest;
/* Check if the edge destination has been visited yet. */
- if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->sindex))
+ if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
{
/* Mark that we have visited the destination. */
- SET_BIT (visited, dest->sindex);
+ SET_BIT (visited, dest->index);
/* Add the destination to the preorder tree. */
if (src != ENTRY_BLOCK_PTR)
{
- dfst[src->sindex].node[dfst[src->sindex].nnodes++]
- = &dfst[dest->sindex];
- dfst[dest->sindex].up = &dfst[src->sindex];
+ dfst[src->index].node[dfst[src->index].nnodes++]
+ = &dfst[dest->index];
+ dfst[dest->index].up = &dfst[src->index];
}
if (dest->succ)
walking the tree from right to left. */
i = 0;
- node = &dfst[ENTRY_BLOCK_PTR->next_bb->sindex];
+ node = &dfst[ENTRY_BLOCK_PTR->next_bb->index];
pot_order[i++] = 0;
while (node)
/* Initialize the data structures used for depth-first search on the
reverse graph. If INITIALIZE_STACK is nonzero, the exit block is
added to the basic block stack. DATA is the current depth-first
- search context. If INITIALIZE_STACK is non-zero, there is an
+ search context. If INITIALIZE_STACK is nonzero, there is an
element on the stack. */
static void
-flow_dfs_compute_reverse_init (data)
- depth_first_search_ds data;
+flow_dfs_compute_reverse_init (depth_first_search_ds data)
{
/* Allocate stack for back-tracking up CFG. */
- data->stack = (basic_block *) xmalloc ((num_basic_blocks - (INVALID_BLOCK + 1))
- * sizeof (basic_block));
+ data->stack = xmalloc ((n_basic_blocks - (INVALID_BLOCK + 1))
+ * sizeof (basic_block));
data->sp = 0;
/* Allocate bitmap to track nodes that have been visited. */
block. */
static void
-flow_dfs_compute_reverse_add_bb (data, bb)
- depth_first_search_ds data;
- basic_block bb;
+flow_dfs_compute_reverse_add_bb (depth_first_search_ds data, basic_block bb)
{
data->stack[data->sp++] = bb;
- SET_BIT (data->visited_blocks, bb->sindex - (INVALID_BLOCK + 1));
+ SET_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1));
}
/* Continue the depth-first search through the reverse graph starting with the
available. */
static basic_block
-flow_dfs_compute_reverse_execute (data)
- depth_first_search_ds data;
+flow_dfs_compute_reverse_execute (depth_first_search_ds data)
{
basic_block bb;
edge e;
/* Perform depth-first search on adjacent vertices. */
for (e = bb->pred; e; e = e->pred_next)
if (!TEST_BIT (data->visited_blocks,
- e->src->sindex - (INVALID_BLOCK + 1)))
+ e->src->index - (INVALID_BLOCK + 1)))
flow_dfs_compute_reverse_add_bb (data, e->src);
}
/* Determine if there are unvisited basic blocks. */
- FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
- if (!TEST_BIT (data->visited_blocks, bb->sindex - (INVALID_BLOCK + 1)))
+ FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR, NULL, prev_bb)
+ if (!TEST_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1)))
return bb;
return NULL;
reverse graph. */
static void
-flow_dfs_compute_reverse_finish (data)
- depth_first_search_ds data;
+flow_dfs_compute_reverse_finish (depth_first_search_ds data)
{
free (data->stack);
sbitmap_free (data->visited_blocks);
}
+
+/* Performs dfs search from BB over vertices satisfying PREDICATE;
+ if REVERSE, go against direction of edges. Returns number of blocks
+ found and their list in RSLT. RSLT can contain at most RSLT_MAX items. */
+int
+dfs_enumerate_from (basic_block bb, int reverse,
+ bool (*predicate) (basic_block, void *),
+ basic_block *rslt, int rslt_max, void *data)
+{
+ basic_block *st, lbb;
+ int sp = 0, tv = 0;
+
+ st = xcalloc (rslt_max, sizeof (basic_block));
+ rslt[tv++] = st[sp++] = bb;
+ bb->flags |= BB_VISITED;
+ while (sp)
+ {
+ edge e;
+ lbb = st[--sp];
+ if (reverse)
+ {
+ for (e = lbb->pred; e; e = e->pred_next)
+ if (!(e->src->flags & BB_VISITED) && predicate (e->src, data))
+ {
+ if (tv == rslt_max)
+ abort ();
+ rslt[tv++] = st[sp++] = e->src;
+ e->src->flags |= BB_VISITED;
+ }
+ }
+ else
+ {
+ for (e = lbb->succ; e; e = e->succ_next)
+ if (!(e->dest->flags & BB_VISITED) && predicate (e->dest, data))
+ {
+ if (tv == rslt_max)
+ abort ();
+ rslt[tv++] = st[sp++] = e->dest;
+ e->dest->flags |= BB_VISITED;
+ }
+ }
+ }
+ free (st);
+ for (sp = 0; sp < tv; sp++)
+ rslt[sp]->flags &= ~BB_VISITED;
+ return tv;
+}
OSDN Git Service
