#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. */
post = (int *) xcalloc (last_basic_block, sizeof (int));
/* Allocate stack for back-tracking up CFG. */
- stack = (edge *) xmalloc ((num_basic_blocks + 1) * sizeof (edge));
+ stack = (edge *) 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;
{
basic_block bb;
- FOR_ALL_BB (bb)
+ FOR_EACH_BB (bb)
{
edge e;
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
basic_block *tos, *worklist, bb;
tos = worklist =
- (basic_block *) xmalloc (sizeof (basic_block) * num_basic_blocks);
+ (basic_block *) 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
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++;
}
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);
}
}
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
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);
}
{
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);
}
sbitmap visited;
/* Allocate stack for back-tracking up CFG. */
- stack = (edge *) xmalloc ((num_basic_blocks + 1) * sizeof (edge));
+ stack = (edge *) 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;
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 = (edge *) 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;
basic_block bb;
/* Allocate stack for back-tracking up CFG. */
- stack = (edge *) xmalloc ((num_basic_blocks + 1) * sizeof (edge));
+ stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
sp = 0;
/* Allocate the tree. */
dfst = (struct dfst_node *) 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
+ ? (struct dfst_node **) 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)
depth_first_search_ds data;
{
/* Allocate stack for back-tracking up CFG. */
- data->stack = (basic_block *) xmalloc ((num_basic_blocks - (INVALID_BLOCK + 1))
+ data->stack = (basic_block *) xmalloc ((n_basic_blocks - (INVALID_BLOCK + 1))
* sizeof (basic_block));
data->sp = 0;
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
/* 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;
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 (bb, reverse, predicate, rslt, rslt_max, data)
+ 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
