/* 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. */
PARAMS ((depth_first_search_ds));
static void remove_fake_successors PARAMS ((basic_block));
static bool need_fake_edge_p PARAMS ((rtx));
-static bool keep_with_call_p PARAMS ((rtx));
+static bool flow_active_insn_p PARAMS ((rtx));
\f
+/* Like active_insn_p, except keep the return value clobber around
+ even after reload. */
+
+static bool
+flow_active_insn_p (insn)
+ 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. */
return false;
for (insn = bb->head; insn != bb->end; insn = NEXT_INSN (insn))
- if (INSN_P (insn) && active_insn_p (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. */
rtx insn = src->end;
rtx insn2 = target->head;
- if (src->index + 1 == target->index && !active_insn_p (insn2))
+ if (src->next_bb != target)
+ return 0;
+
+ if (!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
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. */
|| GET_CODE (PATTERN (insn)) == ASM_INPUT);
}
-/* Return true if INSN should be kept in the same block as a preceding call.
- This is done for a single-set whose destination is a fixed register or
- whose source is the function return value. This is a helper function for
- flow_call_edges_add. */
-
-static bool
-keep_with_call_p (insn)
- rtx insn;
-{
- rtx set;
-
- if (INSN_P (insn) && (set = single_set (insn)) != NULL)
- {
- if (GET_CODE (SET_DEST (set)) == REG
- && fixed_regs[REGNO (SET_DEST (set))])
- return true;
- if (GET_CODE (SET_SRC (set)) == REG
- && FUNCTION_VALUE_REGNO_P (REGNO (SET_SRC (set))))
- return true;
- }
- return false;
-}
-
/* Add fake edges to the function exit for any non constant and non noreturn
calls, volatile inline assembly in the bitmap of blocks specified by
BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
{
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. 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 ()
{
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);
}
/* 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. */
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);
/* 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
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) PARAMS ((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
