#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. */
rtx insn = src->end;
rtx insn2 = target->head;
- if (src->index + 1 != target->index)
+ if (src->next_bb != target)
return 0;
if (!active_insn_p (insn2))
bool found = false;
/* Allocate the preorder and postorder number arrays. */
- pre = (int *) xcalloc (n_basic_blocks, sizeof (int));
- post = (int *) xcalloc (n_basic_blocks, sizeof (int));
+ pre = (int *) xcalloc (last_basic_block, sizeof (int));
+ post = (int *) xcalloc (last_basic_block, sizeof (int));
/* Allocate stack for back-tracking up CFG. */
stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
sp = 0;
/* Allocate bitmap to track nodes that have been visited. */
- visited = sbitmap_alloc (n_basic_blocks);
+ visited = sbitmap_alloc (last_basic_block);
/* None of the nodes in the CFG have been visited yet. */
sbitmap_zero (visited);
return found;
}
+/* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru. */
+
+void
+set_edge_can_fallthru_flag ()
+{
+ basic_block 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;
+
+ /* If the BB ends with an invertable 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))
+ continue;
+ if (!invert_jump (bb->end, JUMP_LABEL (bb->end), 0))
+ continue;
+ invert_jump (bb->end, JUMP_LABEL (bb->end), 0);
+ bb->succ->flags |= EDGE_CAN_FALLTHRU;
+ bb->succ->succ_next->flags |= EDGE_CAN_FALLTHRU;
+ }
+}
+
/* Return true if we need to add fake edge to exit.
Helper function for the flow_call_edges_add. */
{
int i;
int blocks_split = 0;
- int bb_num = 0;
- basic_block *bbs;
+ int last_bb = last_basic_block;
bool check_last_block = false;
- /* Map bb indices into basic block pointers since split_block
- will renumber the basic blocks. */
-
- bbs = xmalloc (n_basic_blocks * sizeof (*bbs));
+ if (n_basic_blocks == 0)
+ return 0;
if (! blocks)
- {
- for (i = 0; i < n_basic_blocks; i++)
- bbs[bb_num++] = BASIC_BLOCK (i);
-
- check_last_block = true;
- }
+ check_last_block = true;
else
- EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i,
- {
- bbs[bb_num++] = BASIC_BLOCK (i);
- if (i == n_basic_blocks - 1)
- check_last_block = true;
- });
+ 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
Handle this by adding a dummy instruction in a new last basic block. */
if (check_last_block)
{
- basic_block bb = BASIC_BLOCK (n_basic_blocks - 1);
+ basic_block bb = EXIT_BLOCK_PTR->prev_bb;
rtx insn = bb->end;
/* Back up past insns that must be kept in the same block as a call. */
calls since there is no way that we can determine if they will
return or not... */
- for (i = 0; i < bb_num; i++)
+ for (i = 0; i < last_bb; i++)
{
- basic_block bb = bbs[i];
+ basic_block bb = BASIC_BLOCK (i);
rtx insn;
rtx prev_insn;
+ if (!bb)
+ continue;
+
+ if (blocks && !TEST_BIT (blocks, i))
+ continue;
+
for (insn = bb->end; ; insn = prev_insn)
{
prev_insn = PREV_INSN (insn);
/* Note that the following may create a new basic block
and renumber the existing basic blocks. */
- e = split_block (bb, split_at_insn);
- if (e)
- blocks_split++;
+ if (split_at_insn != bb->end)
+ {
+ e = split_block (bb, split_at_insn);
+ if (e)
+ blocks_split++;
+ }
make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
}
if (blocks_split)
verify_flow_info ();
- free (bbs);
return blocks_split;
}
find_unreachable_blocks ()
{
edge e;
- int i, n;
- basic_block *tos, *worklist;
+ basic_block *tos, *worklist, bb;
- n = n_basic_blocks;
- tos = worklist = (basic_block *) xmalloc (sizeof (basic_block) * n);
+ tos = worklist =
+ (basic_block *) xmalloc (sizeof (basic_block) * n_basic_blocks);
/* Clear all the reachability flags. */
- for (i = 0; i < n; ++i)
- BASIC_BLOCK (i)->flags &= ~BB_REACHABLE;
+ FOR_EACH_BB (bb)
+ bb->flags &= ~BB_REACHABLE;
/* Add our starting points to the worklist. Almost always there will
be only one. It isn't inconceivable that we might one day directly
struct edge_list *elist;
edge e;
int num_edges;
- int x;
int block_count;
+ basic_block bb;
block_count = n_basic_blocks + 2; /* Include the entry and exit blocks. */
/* Determine the number of edges in the flow graph by counting successor
edges on each basic block. */
- for (x = 0; x < n_basic_blocks; x++)
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
{
- basic_block bb = BASIC_BLOCK (x);
-
for (e = bb->succ; e; e = e->succ_next)
num_edges++;
}
- /* Don't forget successors of the entry block. */
- for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
- num_edges++;
-
elist = (struct edge_list *) xmalloc (sizeof (struct edge_list));
elist->num_blocks = block_count;
elist->num_edges = num_edges;
num_edges = 0;
- /* Follow successors of the entry block, and register these edges. */
- for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
- elist->index_to_edge[num_edges++] = e;
-
- for (x = 0; x < n_basic_blocks; x++)
- {
- basic_block bb = BASIC_BLOCK (x);
-
- /* Follow all successors of blocks, and register these edges. */
- for (e = bb->succ; e; e = e->succ_next)
- elist->index_to_edge[num_edges++] = e;
- }
+ /* Follow successors of blocks, and register these edges. */
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
+ for (e = bb->succ; e; e = e->succ_next)
+ elist->index_to_edge[num_edges++] = e;
return elist;
}
FILE *f;
struct edge_list *elist;
{
- int x, pred, succ, index;
+ int pred, succ, index;
edge e;
+ basic_block bb, p, s;
- for (x = 0; x < n_basic_blocks; x++)
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
{
- basic_block bb = BASIC_BLOCK (x);
-
for (e = bb->succ; e; e = e->succ_next)
{
pred = e->src->index;
}
}
- for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
- {
- pred = e->src->index;
- succ = e->dest->index;
- index = EDGE_INDEX (elist, e->src, e->dest);
- if (index == EDGE_INDEX_NO_EDGE)
- {
- fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ);
- continue;
- }
-
- 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)->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)->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 (pred = 0; pred < n_basic_blocks; pred++)
- for (succ = 0; succ < n_basic_blocks; succ++)
+ FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
+ FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
{
- basic_block p = BASIC_BLOCK (pred);
- basic_block s = BASIC_BLOCK (succ);
int found_edge = 0;
for (e = p->succ; e; e = e->succ_next)
break;
}
- if (EDGE_INDEX (elist, BASIC_BLOCK (pred), BASIC_BLOCK (succ))
+ 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",
- pred, succ);
- if (EDGE_INDEX (elist, BASIC_BLOCK (pred), BASIC_BLOCK (succ))
+ 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",
- pred, succ, EDGE_INDEX (elist, BASIC_BLOCK (pred),
- BASIC_BLOCK (succ)));
+ p->index, s->index, EDGE_INDEX (elist, p, s));
}
-
- for (succ = 0; succ < n_basic_blocks; succ++)
- {
- basic_block p = ENTRY_BLOCK_PTR;
- basic_block s = BASIC_BLOCK (succ);
- int found_edge = 0;
-
- for (e = p->succ; e; e = e->succ_next)
- if (e->dest == s)
- {
- found_edge = 1;
- break;
- }
-
- for (e = s->pred; e; e = e->pred_next)
- if (e->src == p)
- {
- found_edge = 1;
- break;
- }
-
- if (EDGE_INDEX (elist, ENTRY_BLOCK_PTR, BASIC_BLOCK (succ))
- == EDGE_INDEX_NO_EDGE && found_edge != 0)
- fprintf (f, "*** Edge (entry, %d) appears to not have an index\n",
- succ);
- if (EDGE_INDEX (elist, ENTRY_BLOCK_PTR, BASIC_BLOCK (succ))
- != EDGE_INDEX_NO_EDGE && found_edge == 0)
- fprintf (f, "*** Edge (entry, %d) has index %d, but no edge exists\n",
- succ, EDGE_INDEX (elist, ENTRY_BLOCK_PTR,
- BASIC_BLOCK (succ)));
- }
-
- for (pred = 0; pred < n_basic_blocks; pred++)
- {
- basic_block p = BASIC_BLOCK (pred);
- basic_block s = EXIT_BLOCK_PTR;
- int found_edge = 0;
-
- for (e = p->succ; e; e = e->succ_next)
- if (e->dest == s)
- {
- found_edge = 1;
- break;
- }
-
- for (e = s->pred; e; e = e->pred_next)
- if (e->src == p)
- {
- found_edge = 1;
- break;
- }
-
- if (EDGE_INDEX (elist, BASIC_BLOCK (pred), EXIT_BLOCK_PTR)
- == EDGE_INDEX_NO_EDGE && found_edge != 0)
- fprintf (f, "*** Edge (%d, exit) appears to not have an index\n",
- pred);
- if (EDGE_INDEX (elist, BASIC_BLOCK (pred), EXIT_BLOCK_PTR)
- != EDGE_INDEX_NO_EDGE && found_edge == 0)
- fprintf (f, "*** Edge (%d, exit) has index %d, but no edge exists\n",
- pred, EDGE_INDEX (elist, BASIC_BLOCK (pred),
- EXIT_BLOCK_PTR));
- }
}
/* This routine will determine what, if any, edge there is between
void
remove_fake_edges ()
{
- int x;
-
- for (x = 0; x < n_basic_blocks; x++)
- remove_fake_successors (BASIC_BLOCK (x));
+ basic_block bb;
- /* We've handled all successors except the entry block's. */
- remove_fake_successors (ENTRY_BLOCK_PTR);
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
+ remove_fake_successors (bb);
}
/* This function will add a fake edge between any block which has no
void
add_noreturn_fake_exit_edges ()
{
- int x;
+ basic_block bb;
- for (x = 0; x < n_basic_blocks; x++)
- if (BASIC_BLOCK (x)->succ == NULL)
- make_single_succ_edge (BASIC_BLOCK (x), EXIT_BLOCK_PTR, EDGE_FAKE);
+ FOR_EACH_BB (bb)
+ if (bb->succ == NULL)
+ make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
}
/* This function adds a fake edge between any infinite loops to the
sp = 0;
/* Allocate bitmap to track nodes that have been visited. */
- visited = sbitmap_alloc (n_basic_blocks);
+ visited = sbitmap_alloc (last_basic_block);
/* None of the nodes in the CFG have been visited yet. */
sbitmap_zero (visited);
sp = 0;
/* Allocate bitmap to track nodes that have been visited. */
- visited = sbitmap_alloc (n_basic_blocks);
+ visited = sbitmap_alloc (last_basic_block);
/* None of the nodes in the CFG have been visited yet. */
sbitmap_zero (visited);
sbitmap visited;
struct dfst_node *node;
struct dfst_node *dfst;
+ basic_block bb;
/* Allocate stack for back-tracking up CFG. */
stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
sp = 0;
/* Allocate the tree. */
- dfst = (struct dfst_node *) xcalloc (n_basic_blocks,
+ dfst = (struct dfst_node *) xcalloc (last_basic_block,
sizeof (struct dfst_node));
- for (i = 0; i < n_basic_blocks; i++)
+ FOR_EACH_BB (bb)
{
max_successors = 0;
- for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next)
+ for (e = bb->succ; e; e = e->succ_next)
max_successors++;
- dfst[i].node
+ dfst[bb->index].node
= (max_successors
? (struct dfst_node **) xcalloc (max_successors,
sizeof (struct dfst_node *))
}
/* Allocate bitmap to track nodes that have been visited. */
- visited = sbitmap_alloc (n_basic_blocks);
+ visited = sbitmap_alloc (last_basic_block);
/* None of the nodes in the CFG have been visited yet. */
sbitmap_zero (visited);
walking the tree from right to left. */
i = 0;
- node = &dfst[0];
+ node = &dfst[ENTRY_BLOCK_PTR->next_bb->index];
pot_order[i++] = 0;
while (node)
/* Free the tree. */
- for (i = 0; i < n_basic_blocks; i++)
+ for (i = 0; i < last_basic_block; i++)
if (dfst[i].node)
free (dfst[i].node);
data->sp = 0;
/* Allocate bitmap to track nodes that have been visited. */
- data->visited_blocks = sbitmap_alloc (n_basic_blocks - (INVALID_BLOCK + 1));
+ data->visited_blocks = sbitmap_alloc (last_basic_block - (INVALID_BLOCK + 1));
/* None of the nodes in the CFG have been visited yet. */
sbitmap_zero (data->visited_blocks);
{
basic_block bb;
edge e;
- int i;
while (data->sp > 0)
{
}
/* Determine if there are unvisited basic blocks. */
- for (i = n_basic_blocks - (INVALID_BLOCK + 1); --i >= 0; )
- if (!TEST_BIT (data->visited_blocks, i))
- return BASIC_BLOCK (i + (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
