/* Control flow graph analysis code for GNU compiler.
Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
- 1999, 2000, 2001, 2003, 2004 Free Software Foundation, Inc.
+ 1999, 2000, 2001, 2003, 2004, 2005 Free Software Foundation, Inc.
This file is part of GCC.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
/* This file contains various simple utilities to analyze the CFG. */
#include "config.h"
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
+#include "obstack.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "insn-config.h"
#include "recog.h"
#include "toplev.h"
#include "tm_p.h"
+#include "timevar.h"
/* Store the data structures necessary for depth-first search. */
struct depth_first_search_dsS {
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 basic_block flow_dfs_compute_reverse_execute (depth_first_search_ds,
+ basic_block);
static void flow_dfs_compute_reverse_finish (depth_first_search_ds);
-static void remove_fake_successors (basic_block);
static bool flow_active_insn_p (rtx);
\f
/* Like active_insn_p, except keep the return value clobber around
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. */
+ possibility for register lifetime confusion. */
if (GET_CODE (PATTERN (insn)) == CLOBBER
&& REG_P (XEXP (PATTERN (insn), 0))
&& REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0)))
rtx insn;
if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR
- || !bb->succ || bb->succ->succ_next)
+ || !single_succ_p (bb))
return false;
for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
rtx insn = BB_END (src);
rtx insn2;
edge e;
+ edge_iterator ei;
if (target == EXIT_BLOCK_PTR)
return true;
if (src->next_bb != target)
return 0;
- for (e = src->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, src->succs)
if (e->dest == EXIT_BLOCK_PTR
&& e->flags & EDGE_FALLTHRU)
- return 0;
+ return 0;
insn2 = BB_HEAD (target);
if (insn2 && !active_insn_p (insn2))
could_fall_through (basic_block src, basic_block target)
{
edge e;
+ edge_iterator ei;
if (target == EXIT_BLOCK_PTR)
return true;
- for (e = src->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, src->succs)
if (e->dest == EXIT_BLOCK_PTR
&& e->flags & EDGE_FALLTHRU)
- return 0;
+ return 0;
return true;
}
\f
Steven Muchnick
Morgan Kaufmann, 1997
- and heavily borrowed from flow_depth_first_order_compute. */
+ and heavily borrowed from pre_and_rev_post_order_compute. */
bool
mark_dfs_back_edges (void)
{
- edge *stack;
+ edge_iterator *stack;
int *pre;
int *post;
int sp;
bool found = false;
/* Allocate the preorder and postorder number arrays. */
- pre = xcalloc (last_basic_block, sizeof (int));
- post = xcalloc (last_basic_block, sizeof (int));
+ pre = XCNEWVEC (int, last_basic_block);
+ post = XCNEWVEC (int, last_basic_block);
/* Allocate stack for back-tracking up CFG. */
- stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge));
+ stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
sp = 0;
/* Allocate bitmap to track nodes that have been visited. */
sbitmap_zero (visited);
/* Push the first edge on to the stack. */
- stack[sp++] = ENTRY_BLOCK_PTR->succ;
+ stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
while (sp)
{
- edge e;
+ edge_iterator ei;
basic_block src;
basic_block dest;
/* Look at the edge on the top of the stack. */
- e = stack[sp - 1];
- src = e->src;
- dest = e->dest;
- e->flags &= ~EDGE_DFS_BACK;
+ ei = stack[sp - 1];
+ src = ei_edge (ei)->src;
+ dest = ei_edge (ei)->dest;
+ ei_edge (ei)->flags &= ~EDGE_DFS_BACK;
/* Check if the edge destination has been visited yet. */
if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
SET_BIT (visited, dest->index);
pre[dest->index] = prenum++;
- if (dest->succ)
+ if (EDGE_COUNT (dest->succs) > 0)
{
/* Since the DEST node has been visited for the first
time, check its successors. */
- stack[sp++] = dest->succ;
+ stack[sp++] = ei_start (dest->succs);
}
else
post[dest->index] = postnum++;
if (dest != EXIT_BLOCK_PTR && src != ENTRY_BLOCK_PTR
&& pre[src->index] >= pre[dest->index]
&& post[dest->index] == 0)
- e->flags |= EDGE_DFS_BACK, found = true;
+ ei_edge (ei)->flags |= EDGE_DFS_BACK, found = true;
- if (! e->succ_next && src != ENTRY_BLOCK_PTR)
+ if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR)
post[src->index] = postnum++;
- if (e->succ_next)
- stack[sp - 1] = e->succ_next;
+ if (!ei_one_before_end_p (ei))
+ ei_next (&stack[sp - 1]);
else
sp--;
}
FOR_EACH_BB (bb)
{
edge e;
+ edge_iterator ei;
- for (e = bb->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, bb->succs)
{
e->flags &= ~EDGE_CAN_FALLTHRU;
/* 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)
+ if (EDGE_COUNT (bb->succs) != 2)
continue;
if (!any_condjump_p (BB_END (bb)))
continue;
if (!invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0))
continue;
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;
+ EDGE_SUCC (bb, 0)->flags |= EDGE_CAN_FALLTHRU;
+ EDGE_SUCC (bb, 1)->flags |= EDGE_CAN_FALLTHRU;
}
}
find_unreachable_blocks (void)
{
edge e;
+ edge_iterator ei;
basic_block *tos, *worklist, bb;
- tos = worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
+ tos = worklist = XNEWVEC (basic_block, n_basic_blocks);
/* Clear all the reachability flags. */
be only one. It isn't inconceivable that we might one day directly
support Fortran alternate entry points. */
- for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
{
*tos++ = e->dest;
{
basic_block b = *--tos;
- for (e = b->succ; e; e = e->succ_next)
- if (!(e->dest->flags & BB_REACHABLE))
- {
- *tos++ = e->dest;
- e->dest->flags |= BB_REACHABLE;
- }
+ FOR_EACH_EDGE (e, ei, b->succs)
+ {
+ basic_block dest = e->dest;
+
+ if (!(dest->flags & BB_REACHABLE))
+ {
+ *tos++ = dest;
+ dest->flags |= BB_REACHABLE;
+ }
+ }
}
free (worklist);
int num_edges;
int block_count;
basic_block bb;
+ edge_iterator ei;
- block_count = n_basic_blocks + 2; /* Include the entry and exit blocks. */
+ block_count = n_basic_blocks; /* 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++;
+ num_edges += EDGE_COUNT (bb->succs);
}
- elist = xmalloc (sizeof (struct edge_list));
+ elist = XNEW (struct edge_list);
elist->num_blocks = block_count;
elist->num_edges = num_edges;
- elist->index_to_edge = xmalloc (sizeof (edge) * num_edges);
+ elist->index_to_edge = XNEWVEC (edge, num_edges);
num_edges = 0;
/* 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)
+ FOR_EACH_EDGE (e, ei, bb->succs)
elist->index_to_edge[num_edges++] = e;
return elist;
int x;
fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
- elist->num_blocks - 2, elist->num_edges);
+ elist->num_blocks, elist->num_edges);
for (x = 0; x < elist->num_edges; x++)
{
int pred, succ, index;
edge e;
basic_block bb, p, s;
+ edge_iterator ei;
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
{
- for (e = bb->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, bb->succs)
{
pred = e->src->index;
succ = e->dest->index;
{
int found_edge = 0;
- for (e = p->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, p->succs)
if (e->dest == s)
{
found_edge = 1;
break;
}
- for (e = s->pred; e; e = e->pred_next)
+ FOR_EACH_EDGE (e, ei, s->preds)
if (e->src == p)
{
found_edge = 1;
find_edge (basic_block pred, basic_block succ)
{
edge e;
+ edge_iterator ei;
- for (e = pred->succ; e; e = e->succ_next)
- if (e->dest == succ)
- return e;
+ if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
+ {
+ FOR_EACH_EDGE (e, ei, pred->succs)
+ if (e->dest == succ)
+ return e;
+ }
+ else
+ {
+ FOR_EACH_EDGE (e, ei, succ->preds)
+ if (e->src == pred)
+ return e;
+ }
return NULL;
}
void
flow_nodes_print (const char *str, const sbitmap nodes, FILE *file)
{
- int node;
+ unsigned int node = 0;
+ sbitmap_iterator sbi;
if (! nodes)
return;
fprintf (file, "%s { ", str);
- EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {fprintf (file, "%d ", node);});
+ EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, sbi)
+ fprintf (file, "%d ", node);
fputs ("}\n", file);
}
}
\f
-/* This routine will remove any fake successor edges for a basic block.
- When the edge is removed, it is also removed from whatever predecessor
+/* This routine will remove any fake predecessor edges for a basic block.
+ When the edge is removed, it is also removed from whatever successor
list it is in. */
static void
-remove_fake_successors (basic_block bb)
+remove_fake_predecessors (basic_block bb)
{
edge e;
+ edge_iterator ei;
- for (e = bb->succ; e;)
+ for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
{
- edge tmp = e;
-
- e = e->succ_next;
- if ((tmp->flags & EDGE_FAKE) == EDGE_FAKE)
- remove_edge (tmp);
+ if ((e->flags & EDGE_FAKE) == EDGE_FAKE)
+ remove_edge (e);
+ else
+ ei_next (&ei);
}
}
{
basic_block bb;
- FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
- remove_fake_successors (bb);
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
+ remove_fake_predecessors (bb);
+}
+
+/* This routine will remove all fake edges to the EXIT_BLOCK. */
+
+void
+remove_fake_exit_edges (void)
+{
+ remove_fake_predecessors (EXIT_BLOCK_PTR);
}
+
/* This function will add a fake edge between any block which has no
successors, and the exit block. Some data flow equations require these
edges to exist. */
basic_block bb;
FOR_EACH_BB (bb)
- if (bb->succ == NULL)
+ if (EDGE_COUNT (bb->succs) == 0)
make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
}
void
connect_infinite_loops_to_exit (void)
{
- basic_block unvisited_block;
+ basic_block unvisited_block = EXIT_BLOCK_PTR;
struct depth_first_search_dsS dfs_ds;
/* Perform depth-first search in the reverse graph to find nodes
/* Repeatedly add fake edges, updating the unreachable nodes. */
while (1)
{
- unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds);
+ unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds,
+ unvisited_block);
if (!unvisited_block)
break;
return;
}
\f
-/* Compute reverse top sort order. */
+/* Compute reverse top sort order.
+ This is computing a post order numbering of the graph. */
-void
-flow_reverse_top_sort_order_compute (int *rts_order)
+int
+post_order_compute (int *post_order, bool include_entry_exit)
{
- edge *stack;
+ edge_iterator *stack;
int sp;
- int postnum = 0;
+ int post_order_num = 0;
sbitmap visited;
+ if (include_entry_exit)
+ post_order[post_order_num++] = EXIT_BLOCK;
+
/* Allocate stack for back-tracking up CFG. */
- stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge));
+ stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
sp = 0;
/* Allocate bitmap to track nodes that have been visited. */
sbitmap_zero (visited);
/* Push the first edge on to the stack. */
- stack[sp++] = ENTRY_BLOCK_PTR->succ;
+ stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
while (sp)
{
- edge e;
+ edge_iterator ei;
basic_block src;
basic_block dest;
/* Look at the edge on the top of the stack. */
- e = stack[sp - 1];
- src = e->src;
- dest = e->dest;
+ ei = stack[sp - 1];
+ src = ei_edge (ei)->src;
+ dest = ei_edge (ei)->dest;
/* Check if the edge destination has been visited yet. */
if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
/* Mark that we have visited the destination. */
SET_BIT (visited, dest->index);
- if (dest->succ)
+ if (EDGE_COUNT (dest->succs) > 0)
/* Since the DEST node has been visited for the first
time, check its successors. */
- stack[sp++] = dest->succ;
+ stack[sp++] = ei_start (dest->succs);
else
- rts_order[postnum++] = dest->index;
+ post_order[post_order_num++] = dest->index;
}
else
{
- if (! e->succ_next && src != ENTRY_BLOCK_PTR)
- rts_order[postnum++] = src->index;
+ if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR)
+ post_order[post_order_num++] = src->index;
- if (e->succ_next)
- stack[sp - 1] = e->succ_next;
+ if (!ei_one_before_end_p (ei))
+ ei_next (&stack[sp - 1]);
else
sp--;
}
}
+ if (include_entry_exit)
+ post_order[post_order_num++] = ENTRY_BLOCK;
+
free (stack);
sbitmap_free (visited);
+ return post_order_num;
}
/* Compute the depth first search order and store in the array
- DFS_ORDER if nonzero, marking the nodes visited in VISITED. If
- RC_ORDER is nonzero, return the reverse completion number for each
+ PRE_ORDER if nonzero, marking the nodes visited in VISITED. If
+ REV_POST_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. */
+ possible.
+
+ pre_order is a really a preorder numbering of the graph.
+ rev_post_order is really a reverse postorder numbering of the graph.
+ */
int
-flow_depth_first_order_compute (int *dfs_order, int *rc_order)
+pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order,
+ bool include_entry_exit)
{
- edge *stack;
+ edge_iterator *stack;
int sp;
- int dfsnum = 0;
- int rcnum = n_basic_blocks - 1;
+ int pre_order_num = 0;
+ int rev_post_order_num = n_basic_blocks - 1;
sbitmap visited;
/* Allocate stack for back-tracking up CFG. */
- stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge));
+ stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
sp = 0;
+ if (include_entry_exit)
+ {
+ if (pre_order)
+ pre_order[pre_order_num] = ENTRY_BLOCK;
+ pre_order_num++;
+ if (rev_post_order)
+ rev_post_order[rev_post_order_num--] = ENTRY_BLOCK;
+ }
+ else
+ rev_post_order_num -= NUM_FIXED_BLOCKS;
+
/* Allocate bitmap to track nodes that have been visited. */
visited = sbitmap_alloc (last_basic_block);
sbitmap_zero (visited);
/* Push the first edge on to the stack. */
- stack[sp++] = ENTRY_BLOCK_PTR->succ;
+ stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
while (sp)
{
- edge e;
+ edge_iterator ei;
basic_block src;
basic_block dest;
/* Look at the edge on the top of the stack. */
- e = stack[sp - 1];
- src = e->src;
- dest = e->dest;
+ ei = stack[sp - 1];
+ src = ei_edge (ei)->src;
+ dest = ei_edge (ei)->dest;
/* Check if the edge destination has been visited yet. */
if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
/* Mark that we have visited the destination. */
SET_BIT (visited, dest->index);
- if (dfs_order)
- dfs_order[dfsnum] = dest->index;
+ if (pre_order)
+ pre_order[pre_order_num] = dest->index;
- dfsnum++;
+ pre_order_num++;
- if (dest->succ)
+ if (EDGE_COUNT (dest->succs) > 0)
/* Since the DEST node has been visited for the first
time, check its successors. */
- stack[sp++] = dest->succ;
- else if (rc_order)
+ stack[sp++] = ei_start (dest->succs);
+ else if (rev_post_order)
/* There are no successors for the DEST node so assign
its reverse completion number. */
- rc_order[rcnum--] = dest->index;
+ rev_post_order[rev_post_order_num--] = dest->index;
}
else
{
- if (! e->succ_next && src != ENTRY_BLOCK_PTR
- && rc_order)
+ if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR
+ && rev_post_order)
/* There are no more successors for the SRC node
so assign its reverse completion number. */
- rc_order[rcnum--] = src->index;
+ rev_post_order[rev_post_order_num--] = src->index;
- if (e->succ_next)
- stack[sp - 1] = e->succ_next;
+ if (!ei_one_before_end_p (ei))
+ ei_next (&stack[sp - 1]);
else
sp--;
}
free (stack);
sbitmap_free (visited);
- /* The number of nodes visited should not be greater than
- n_basic_blocks. */
- if (dfsnum > n_basic_blocks)
- abort ();
-
- /* There are some nodes left in the CFG that are unreachable. */
- if (dfsnum < n_basic_blocks)
- abort ();
-
- return dfsnum;
-}
-
-struct dfst_node
-{
- unsigned nnodes;
- struct dfst_node **node;
- struct dfst_node *up;
-};
-
-/* Compute a preorder transversal ordering such that a sub-tree which
- is the source of a cross edge appears before the sub-tree which is
- the destination of the cross edge. This allows for easy detection
- of all the entry blocks for a loop.
-
- The ordering is compute by:
-
- 1) Generating a depth first spanning tree.
-
- 2) Walking the resulting tree from right to left. */
-
-void
-flow_preorder_transversal_compute (int *pot_order)
-{
- edge e;
- edge *stack;
- int i;
- int max_successors;
- int sp;
- sbitmap visited;
- struct dfst_node *node;
- struct dfst_node *dfst;
- basic_block bb;
-
- /* Allocate stack for back-tracking up CFG. */
- stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge));
- sp = 0;
-
- /* Allocate the tree. */
- dfst = xcalloc (last_basic_block, sizeof (struct dfst_node));
-
- FOR_EACH_BB (bb)
+ if (include_entry_exit)
{
- max_successors = 0;
- for (e = bb->succ; e; e = e->succ_next)
- max_successors++;
-
- dfst[bb->index].node
- = (max_successors
- ? xcalloc (max_successors, sizeof (struct dfst_node *)) : NULL);
+ if (pre_order)
+ pre_order[pre_order_num] = EXIT_BLOCK;
+ pre_order_num++;
+ if (rev_post_order)
+ rev_post_order[rev_post_order_num--] = EXIT_BLOCK;
+ /* The number of nodes visited should be the number of blocks. */
+ gcc_assert (pre_order_num == n_basic_blocks);
}
+ else
+ /* The number of nodes visited should be the number of blocks minus
+ the entry and exit blocks which are not visited here. */
+ gcc_assert (pre_order_num == n_basic_blocks - NUM_FIXED_BLOCKS);
- /* Allocate bitmap to track nodes that have been visited. */
- visited = sbitmap_alloc (last_basic_block);
-
- /* None of the nodes in the CFG have been visited yet. */
- sbitmap_zero (visited);
-
- /* Push the first edge on to the stack. */
- stack[sp++] = ENTRY_BLOCK_PTR->succ;
-
- while (sp)
- {
- basic_block src;
- basic_block dest;
-
- /* Look at the edge on the top of the stack. */
- e = stack[sp - 1];
- src = e->src;
- dest = e->dest;
-
- /* Check if the edge destination has been visited yet. */
- if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
- {
- /* Mark that we have visited the destination. */
- SET_BIT (visited, dest->index);
-
- /* Add the destination to the preorder tree. */
- if (src != ENTRY_BLOCK_PTR)
- {
- dfst[src->index].node[dfst[src->index].nnodes++]
- = &dfst[dest->index];
- dfst[dest->index].up = &dfst[src->index];
- }
-
- if (dest->succ)
- /* Since the DEST node has been visited for the first
- time, check its successors. */
- stack[sp++] = dest->succ;
- }
-
- else if (e->succ_next)
- stack[sp - 1] = e->succ_next;
- else
- sp--;
- }
-
- free (stack);
- sbitmap_free (visited);
-
- /* Record the preorder transversal order by
- walking the tree from right to left. */
-
- i = 0;
- node = &dfst[ENTRY_BLOCK_PTR->next_bb->index];
- pot_order[i++] = 0;
-
- while (node)
- {
- if (node->nnodes)
- {
- node = node->node[--node->nnodes];
- pot_order[i++] = node - dfst;
- }
- else
- node = node->up;
- }
-
- /* Free the tree. */
-
- for (i = 0; i < last_basic_block; i++)
- if (dfst[i].node)
- free (dfst[i].node);
-
- free (dfst);
+ return pre_order_num;
}
/* Compute the depth first search order on the _reverse_ graph and
flow_dfs_compute_reverse_init (depth_first_search_ds data)
{
/* Allocate stack for back-tracking up CFG. */
- data->stack = xmalloc ((n_basic_blocks - (INVALID_BLOCK + 1))
- * sizeof (basic_block));
+ data->stack = XNEWVEC (basic_block, n_basic_blocks);
data->sp = 0;
/* Allocate bitmap to track nodes that have been visited. */
- data->visited_blocks = sbitmap_alloc (last_basic_block - (INVALID_BLOCK + 1));
+ data->visited_blocks = sbitmap_alloc (last_basic_block);
/* None of the nodes in the CFG have been visited yet. */
sbitmap_zero (data->visited_blocks);
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->index - (INVALID_BLOCK + 1));
+ SET_BIT (data->visited_blocks, bb->index);
}
/* Continue the depth-first search through the reverse graph starting with the
available. */
static basic_block
-flow_dfs_compute_reverse_execute (depth_first_search_ds data)
+flow_dfs_compute_reverse_execute (depth_first_search_ds data,
+ basic_block last_unvisited)
{
basic_block bb;
edge e;
+ edge_iterator ei;
while (data->sp > 0)
{
bb = data->stack[--data->sp];
/* Perform depth-first search on adjacent vertices. */
- for (e = bb->pred; e; e = e->pred_next)
- if (!TEST_BIT (data->visited_blocks,
- e->src->index - (INVALID_BLOCK + 1)))
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ if (!TEST_BIT (data->visited_blocks, e->src->index))
flow_dfs_compute_reverse_add_bb (data, e->src);
}
/* Determine if there are unvisited basic blocks. */
- FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR, NULL, prev_bb)
- if (!TEST_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1)))
+ FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb)
+ if (!TEST_BIT (data->visited_blocks, bb->index))
return bb;
return NULL;
{
basic_block *st, lbb;
int sp = 0, tv = 0;
+ unsigned size;
+
+ /* A bitmap to keep track of visited blocks. Allocating it each time
+ this function is called is not possible, since dfs_enumerate_from
+ is often used on small (almost) disjoint parts of cfg (bodies of
+ loops), and allocating a large sbitmap would lead to quadratic
+ behavior. */
+ static sbitmap visited;
+ static unsigned v_size;
+
+#define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index))
+#define UNMARK_VISITED(BB) (RESET_BIT (visited, (BB)->index))
+#define VISITED_P(BB) (TEST_BIT (visited, (BB)->index))
+
+ /* Resize the VISITED sbitmap if necessary. */
+ size = last_basic_block;
+ if (size < 10)
+ size = 10;
+
+ if (!visited)
+ {
- st = xcalloc (rslt_max, sizeof (basic_block));
+ visited = sbitmap_alloc (size);
+ sbitmap_zero (visited);
+ v_size = size;
+ }
+ else if (v_size < size)
+ {
+ /* Ensure that we increase the size of the sbitmap exponentially. */
+ if (2 * v_size > size)
+ size = 2 * v_size;
+
+ visited = sbitmap_resize (visited, size, 0);
+ v_size = size;
+ }
+
+ st = XCNEWVEC (basic_block, rslt_max);
rslt[tv++] = st[sp++] = bb;
- bb->flags |= BB_VISITED;
+ MARK_VISITED (bb);
while (sp)
{
edge e;
+ edge_iterator ei;
lbb = st[--sp];
if (reverse)
- {
- for (e = lbb->pred; e; e = e->pred_next)
- if (!(e->src->flags & BB_VISITED) && predicate (e->src, data))
+ {
+ FOR_EACH_EDGE (e, ei, lbb->preds)
+ if (!VISITED_P (e->src) && predicate (e->src, data))
{
- if (tv == rslt_max)
- abort ();
- rslt[tv++] = st[sp++] = e->src;
- e->src->flags |= BB_VISITED;
+ gcc_assert (tv != rslt_max);
+ rslt[tv++] = st[sp++] = e->src;
+ MARK_VISITED (e->src);
}
- }
+ }
else
- {
- for (e = lbb->succ; e; e = e->succ_next)
- if (!(e->dest->flags & BB_VISITED) && predicate (e->dest, data))
+ {
+ FOR_EACH_EDGE (e, ei, lbb->succs)
+ if (!VISITED_P (e->dest) && predicate (e->dest, data))
{
- if (tv == rslt_max)
- abort ();
- rslt[tv++] = st[sp++] = e->dest;
- e->dest->flags |= BB_VISITED;
+ gcc_assert (tv != rslt_max);
+ rslt[tv++] = st[sp++] = e->dest;
+ MARK_VISITED (e->dest);
}
}
}
free (st);
for (sp = 0; sp < tv; sp++)
- rslt[sp]->flags &= ~BB_VISITED;
+ UNMARK_VISITED (rslt[sp]);
return tv;
+#undef MARK_VISITED
+#undef UNMARK_VISITED
+#undef VISITED_P
}
+
+
+/* Compute dominance frontiers, ala Harvey, Ferrante, et al.
+
+ This algorithm can be found in Timothy Harvey's PhD thesis, at
+ http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative
+ dominance algorithms.
+
+ First, we identify each join point, j (any node with more than one
+ incoming edge is a join point).
+
+ We then examine each predecessor, p, of j and walk up the dominator tree
+ starting at p.
+
+ We stop the walk when we reach j's immediate dominator - j is in the
+ dominance frontier of each of the nodes in the walk, except for j's
+ immediate dominator. Intuitively, all of the rest of j's dominators are
+ shared by j's predecessors as well.
+ Since they dominate j, they will not have j in their dominance frontiers.
+
+ The number of nodes touched by this algorithm is equal to the size
+ of the dominance frontiers, no more, no less.
+*/
+
+
+static void
+compute_dominance_frontiers_1 (bitmap *frontiers)
+{
+ edge p;
+ edge_iterator ei;
+ basic_block b;
+ FOR_EACH_BB (b)
+ {
+ if (EDGE_COUNT (b->preds) >= 2)
+ {
+ FOR_EACH_EDGE (p, ei, b->preds)
+ {
+ basic_block runner = p->src;
+ basic_block domsb;
+ if (runner == ENTRY_BLOCK_PTR)
+ continue;
+
+ domsb = get_immediate_dominator (CDI_DOMINATORS, b);
+ while (runner != domsb)
+ {
+ bitmap_set_bit (frontiers[runner->index],
+ b->index);
+ runner = get_immediate_dominator (CDI_DOMINATORS,
+ runner);
+ }
+ }
+ }
+ }
+}
+
+
+void
+compute_dominance_frontiers (bitmap *frontiers)
+{
+ timevar_push (TV_DOM_FRONTIERS);
+
+ compute_dominance_frontiers_1 (frontiers);
+
+ timevar_pop (TV_DOM_FRONTIERS);
+}
+
OSDN Git Service
