/* 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 "obstack.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"
+#include "timevar.h"
/* Store the data structures necessary for depth-first search. */
struct depth_first_search_dsS {
};
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,
+ basic_block);
+static void flow_dfs_compute_reverse_finish (depth_first_search_ds);
+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
+ && REG_P (XEXP (PATTERN (insn), 0))
+ && 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->head;
+ rtx insn;
+
if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR
- || !bb->succ || bb->succ->succ_next)
+ || EDGE_COUNT (bb->succs) != 1)
return false;
- while (insn != bb->end)
- {
- if (INSN_P (insn) && active_insn_p (insn))
- return false;
- insn = NEXT_INSN (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));
+ || (JUMP_P (insn) && simplejump_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;
+ edge e;
+ edge_iterator ei;
- if (src->index + 1 == target->index && !active_insn_p (insn2))
+ if (target == EXIT_BLOCK_PTR)
+ return true;
+ if (src->next_bb != target)
+ return 0;
+ FOR_EACH_EDGE (e, ei, src->succs)
+ if (e->dest == EXIT_BLOCK_PTR
+ && e->flags & EDGE_FALLTHRU)
+ return 0;
+
+ insn2 = BB_HEAD (target);
+ if (insn2 && !active_insn_p (insn2))
insn2 = next_active_insn (insn2);
+
/* ??? Later we may add code to move jump tables offline. */
return next_active_insn (insn) == insn2;
}
+
+/* Return nonzero if we could reach target from src by falling through,
+ if the target was made adjacent. If we already have a fall-through
+ edge to the exit block, we can't do that. */
+bool
+could_fall_through (basic_block src, basic_block target)
+{
+ edge e;
+ edge_iterator ei;
+
+ if (target == EXIT_BLOCK_PTR)
+ return true;
+ FOR_EACH_EDGE (e, ei, src->succs)
+ if (e->dest == EXIT_BLOCK_PTR
+ && e->flags & EDGE_FALLTHRU)
+ return 0;
+ return true;
+}
\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;
+ edge_iterator *stack;
int *pre;
int *post;
int sp;
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 = xcalloc (last_basic_block, sizeof (int));
+ post = xcalloc (last_basic_block, sizeof (int));
/* Allocate stack for back-tracking up CFG. */
- stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
+ stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator));
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);
/* 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--;
}
return found;
}
-/* Return true if we need to add fake edge to exit.
- Helper function for the flow_call_edges_add. */
-
-static bool
-need_fake_edge_p (insn)
- rtx insn;
-{
- if (!INSN_P (insn))
- return false;
-
- if ((GET_CODE (insn) == CALL_INSN
- && !SIBLING_CALL_P (insn)
- && !find_reg_note (insn, REG_NORETURN, NULL)
- && !find_reg_note (insn, REG_ALWAYS_RETURN, NULL)
- && !CONST_OR_PURE_CALL_P (insn)))
- return true;
-
- return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS
- && MEM_VOLATILE_P (PATTERN (insn)))
- || (GET_CODE (PATTERN (insn)) == PARALLEL
- && asm_noperands (insn) != -1
- && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0)))
- || GET_CODE (PATTERN (insn)) == ASM_INPUT);
-}
-
-/* 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
- that were split.
-
- The goal is to expose cases in which entering a basic block does not imply
- that all subsequent instructions must be executed. */
+/* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru. */
-int
-flow_call_edges_add (blocks)
- sbitmap blocks;
+void
+set_edge_can_fallthru_flag (void)
{
- int i;
- int blocks_split = 0;
- int bb_num = 0;
- basic_block *bbs;
- 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 (! blocks)
- {
- for (i = 0; i < n_basic_blocks; i++)
- bbs[bb_num++] = BASIC_BLOCK (i);
- 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;
- });
- }
-
- /* In the last basic block, before epilogue generation, there will be
- a fallthru edge to EXIT. Special care is required if the last insn
- of the last basic block is a call because make_edge folds duplicate
- edges, which would result in the fallthru edge also being marked
- fake, which would result in the fallthru edge being removed by
- remove_fake_edges, which would result in an invalid CFG.
-
- Moreover, we can't elide the outgoing fake edge, since the block
- profiler needs to take this into account in order to solve the minimal
- spanning tree in the case that the call doesn't return.
-
- Handle this by adding a dummy instruction in a new last basic block. */
- if (check_last_block
- && need_fake_edge_p (BASIC_BLOCK (n_basic_blocks - 1)->end))
- {
- edge e;
- for (e = BASIC_BLOCK (n_basic_blocks - 1)->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 ();
- }
-
-
- /* Now add fake edges to the function exit for any non constant
- calls since there is no way that we can determine if they will
- return or not... */
+ basic_block bb;
- for (i = 0; i < bb_num; i++)
+ FOR_EACH_BB (bb)
{
- basic_block bb = bbs[i];
- rtx insn;
- rtx prev_insn;
+ edge e;
+ edge_iterator ei;
- for (insn = bb->end; ; insn = prev_insn)
+ FOR_EACH_EDGE (e, ei, bb->succs)
{
- prev_insn = PREV_INSN (insn);
- if (need_fake_edge_p (insn))
- {
- edge e;
-
- /* The above condition should be enough to verify that there is
- no edge to the exit block in CFG already. Calling make_edge in
- such case would make us to mark that edge as fake and remove it
- later. */
-#ifdef ENABLE_CHECKING
- if (insn == bb->end)
- for (e = bb->succ; e; e = e->succ_next)
- if (e->dest == EXIT_BLOCK_PTR)
- abort ();
-#endif
-
- /* Note that the following may create a new basic block
- and renumber the existing basic blocks. */
- e = split_block (bb, insn);
- if (e)
- blocks_split++;
-
- make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
- }
- if (insn == bb->head)
- break;
- }
- }
+ e->flags &= ~EDGE_CAN_FALLTHRU;
- if (blocks_split)
- verify_flow_info ();
+ /* The FALLTHRU edge is also CAN_FALLTHRU edge. */
+ if (e->flags & EDGE_FALLTHRU)
+ e->flags |= EDGE_CAN_FALLTHRU;
+ }
- free (bbs);
- return blocks_split;
+ /* If the BB ends with an invertible condjump all (2) edges are
+ CAN_FALLTHRU edges. */
+ 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);
+ EDGE_SUCC (bb, 0)->flags |= EDGE_CAN_FALLTHRU;
+ EDGE_SUCC (bb, 1)->flags |= EDGE_CAN_FALLTHRU;
+ }
}
+
/* 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;
- int i, n;
- basic_block *tos, *worklist;
+ edge_iterator ei;
+ basic_block *tos, *worklist, bb;
- n = n_basic_blocks;
- tos = worklist = (basic_block *) xmalloc (sizeof (basic_block) * n);
+ tos = worklist = 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
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)
+ FOR_EACH_EDGE (e, ei, b->succs)
if (!(e->dest->flags & BB_REACHABLE))
{
*tos++ = e->dest;
and the data structure is filled in. */
struct edge_list *
-create_edge_list ()
+create_edge_list (void)
{
struct edge_list *elist;
edge e;
int num_edges;
- int x;
int block_count;
+ basic_block bb;
+ edge_iterator ei;
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++;
+ num_edges += EDGE_COUNT (bb->succs);
}
- /* 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 = 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;
- /* 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;
- num_edges++;
- }
-
- for (x = 0; x < n_basic_blocks; x++)
- {
- basic_block bb = BASIC_BLOCK (x);
+ /* Follow successors of blocks, and register these edges. */
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ elist->index_to_edge[num_edges++] = e;
- /* 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;
- num_edges++;
- }
- }
return elist;
}
/* 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;
+
fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
elist->num_blocks - 2, elist->num_edges);
extra edges. */
void
-verify_edge_list (f, elist)
- FILE *f;
- struct edge_list *elist;
+verify_edge_list (FILE *f, struct edge_list *elist)
{
- int x, pred, succ, index;
+ int pred, succ, index;
edge e;
+ basic_block bb, p, s;
+ edge_iterator ei;
- 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)
+ FOR_EACH_EDGE (e, ei, bb->succs)
{
pred = e->src->index;
succ = e->dest->index;
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);
index, succ, INDEX_EDGE_SUCC_BB (elist, index)->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)
+ 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;
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;
+/* Given PRED and SUCC blocks, return the edge which connects the blocks.
+ If no such edge exists, return NULL. */
- 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)));
+edge
+find_edge (basic_block pred, basic_block succ)
+{
+ edge e;
+ edge_iterator ei;
+
+ if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
+ {
+ FOR_EACH_EDGE (e, ei, pred->succs)
+ if (e->dest == succ)
+ return e;
}
- for (pred = 0; pred < n_basic_blocks; pred++)
+ else
{
- 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));
+ FOR_EACH_EDGE (e, ei, succ->preds)
+ if (e->src == pred)
+ return e;
}
+
+ return NULL;
}
/* 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;
+
for (x = 0; x < NUM_EDGES (edge_list); x++)
- {
- if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
- && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
- return x;
- }
+ if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
+ && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
+ return x;
+
return (EDGE_INDEX_NO_EDGE);
}
/* 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;
for (i = 0; i < num_edges; i++)
fprintf (file, "%d->%d ", edge_list[i]->src->index,
edge_list[i]->dest->index);
+
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 (bb)
- basic_block bb;
+remove_fake_predecessors (basic_block bb)
{
edge e;
- for (e = bb->succ; e;)
+ edge_iterator ei;
+
+ 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);
}
}
fake predecessors. */
void
-remove_fake_edges ()
+remove_fake_edges (void)
{
- int x;
+ basic_block bb;
+
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
+ remove_fake_predecessors (bb);
+}
- for (x = 0; x < n_basic_blocks; x++)
- remove_fake_successors (BASIC_BLOCK (x));
+/* This routine will remove all fake edges to the EXIT_BLOCK. */
- /* We've handled all successors except the entry block's. */
- remove_fake_successors (ENTRY_BLOCK_PTR);
+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. */
void
-add_noreturn_fake_exit_edges ()
+add_noreturn_fake_exit_edges (void)
{
- 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 (EDGE_COUNT (bb->succs) == 0)
+ make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
}
/* This function adds a fake edge between any infinite loops to the
nodes not reachable from the exit block. */
void
-connect_infinite_loops_to_exit ()
+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
reachable from the exit block. */
- struct depth_first_search_dsS dfs_ds;
-
flow_dfs_compute_reverse_init (&dfs_ds);
flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR);
/* 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;
+
make_edge (unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE);
flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block);
}
flow_dfs_compute_reverse_finish (&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;
+ edge_iterator *stack;
int sp;
int postnum = 0;
sbitmap visited;
/* Allocate stack for back-tracking up CFG. */
- stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
+ stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator));
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);
/* 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)
- {
- /* Since the DEST node has been visited for the first
- time, check its successors. */
- stack[sp++] = dest->succ;
- }
+ if (EDGE_COUNT (dest->succs) > 0)
+ /* Since the DEST node has been visited for the first
+ time, check its successors. */
+ stack[sp++] = ei_start (dest->succs);
else
rts_order[postnum++] = dest->index;
}
else
{
- if (! e->succ_next && src != ENTRY_BLOCK_PTR)
+ if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR)
rts_order[postnum++] = 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--;
}
}
/* 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;
+ edge_iterator *stack;
int sp;
int dfsnum = 0;
int rcnum = n_basic_blocks - 1;
sbitmap visited;
/* Allocate stack for back-tracking up CFG. */
- stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
+ stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator));
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);
/* 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))
dfsnum++;
- if (dest->succ)
- {
- /* Since the DEST node has been visited for the first
- time, check its successors. */
- stack[sp++] = dest->succ;
- }
- else
- {
- /* There are no successors for the DEST node so assign
- its reverse completion number. */
- if (rc_order)
- rc_order[rcnum--] = dest->index;
- }
+ if (EDGE_COUNT (dest->succs) > 0)
+ /* Since the DEST node has been visited for the first
+ time, check its successors. */
+ stack[sp++] = ei_start (dest->succs);
+ else if (rc_order)
+ /* There are no successors for the DEST node so assign
+ its reverse completion number. */
+ rc_order[rcnum--] = dest->index;
}
else
{
- if (! e->succ_next && src != ENTRY_BLOCK_PTR)
- {
- /* There are no more successors for the SRC node
- so assign its reverse completion number. */
- if (rc_order)
- rc_order[rcnum--] = src->index;
- }
-
- if (e->succ_next)
- stack[sp - 1] = e->succ_next;
+ if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR
+ && rc_order)
+ /* There are no more successors for the SRC node
+ so assign its reverse completion number. */
+ rc_order[rcnum--] = src->index;
+
+ 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 ();
+ /* The number of nodes visited should be the number of blocks. */
+ gcc_assert (dfsnum == n_basic_blocks);
- /* 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 (pot_order)
- int *pot_order;
-{
- edge e;
- edge *stack;
- int i;
- int max_successors;
- int sp;
- sbitmap visited;
- struct dfst_node *node;
- struct dfst_node *dfst;
-
- /* 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, sizeof (struct dfst_node));
- for (i = 0; i < n_basic_blocks; i++)
- {
- max_successors = 0;
- for (e = BASIC_BLOCK (i)->succ; e; e = e->succ_next)
- max_successors++;
- dfst[i].node = max_successors ? (struct dfst_node **)
- xcalloc (max_successors,
- sizeof (struct dfst_node *))
- : NULL;
- }
-
- /* Allocate bitmap to track nodes that have been visited. */
- visited = sbitmap_alloc (n_basic_blocks);
-
- /* 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[0];
- 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 < n_basic_blocks; i++)
- if (dfst[i].node)
- free (dfst[i].node);
- free (dfst);
-}
-
/* Compute the depth first search order on the _reverse_ graph and
store in the array DFS_ORDER, marking the nodes visited in VISITED.
Returns the number of nodes visited.
/* 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 ((n_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. */
- 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);
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->index - (INVALID_BLOCK + 1));
- return;
}
-/* Continue the depth-first search through the reverse graph starting
- with the block at the stack's top and ending when the stack is
- empty. Visited nodes are marked. Returns an unvisited basic
- block, or NULL if there is none available. */
+/* Continue the depth-first search through the reverse graph starting with the
+ block at the stack's top and ending when the stack is empty. Visited nodes
+ are marked. Returns an unvisited basic block, or NULL if there is none
+ 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 last_unvisited)
{
basic_block bb;
edge e;
- int i;
+ 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)
+ FOR_EACH_EDGE (e, ei, bb->preds)
if (!TEST_BIT (data->visited_blocks,
e->src->index - (INVALID_BLOCK + 1)))
flow_dfs_compute_reverse_add_bb (data, e->src);
}
/* 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, last_unvisited, 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);
- return;
}
+
+/* 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;
+ edge_iterator ei;
+ lbb = st[--sp];
+ if (reverse)
+ {
+ FOR_EACH_EDGE (e, ei, lbb->preds)
+ if (!(e->src->flags & BB_VISITED) && predicate (e->src, data))
+ {
+ gcc_assert (tv != rslt_max);
+ rslt[tv++] = st[sp++] = e->src;
+ e->src->flags |= BB_VISITED;
+ }
+ }
+ else
+ {
+ FOR_EACH_EDGE (e, ei, lbb->succs)
+ if (!(e->dest->flags & BB_VISITED) && predicate (e->dest, data))
+ {
+ gcc_assert (tv != rslt_max);
+ 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;
+}
+
+
+/* Computing the Dominance Frontier:
+
+ As described in Morgan, section 3.5, this may be done simply by
+ walking the dominator tree bottom-up, computing the frontier for
+ the children before the parent. When considering a block B,
+ there are two cases:
+
+ (1) A flow graph edge leaving B that does not lead to a child
+ of B in the dominator tree must be a block that is either equal
+ to B or not dominated by B. Such blocks belong in the frontier
+ of B.
+
+ (2) Consider a block X in the frontier of one of the children C
+ of B. If X is not equal to B and is not dominated by B, it
+ is in the frontier of B. */
+
+static void
+compute_dominance_frontiers_1 (bitmap *frontiers, basic_block bb, sbitmap done)
+{
+ edge e;
+ edge_iterator ei;
+ basic_block c;
+
+ SET_BIT (done, bb->index);
+
+ /* Do the frontier of the children first. Not all children in the
+ dominator tree (blocks dominated by this one) are children in the
+ CFG, so check all blocks. */
+ for (c = first_dom_son (CDI_DOMINATORS, bb);
+ c;
+ c = next_dom_son (CDI_DOMINATORS, c))
+ {
+ if (! TEST_BIT (done, c->index))
+ compute_dominance_frontiers_1 (frontiers, c, done);
+ }
+
+ /* Find blocks conforming to rule (1) above. */
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ if (e->dest == EXIT_BLOCK_PTR)
+ continue;
+ if (get_immediate_dominator (CDI_DOMINATORS, e->dest) != bb)
+ bitmap_set_bit (frontiers[bb->index], e->dest->index);
+ }
+
+ /* Find blocks conforming to rule (2). */
+ for (c = first_dom_son (CDI_DOMINATORS, bb);
+ c;
+ c = next_dom_son (CDI_DOMINATORS, c))
+ {
+ unsigned x;
+ bitmap_iterator bi;
+
+ EXECUTE_IF_SET_IN_BITMAP (frontiers[c->index], 0, x, bi)
+ {
+ if (get_immediate_dominator (CDI_DOMINATORS, BASIC_BLOCK (x)) != bb)
+ bitmap_set_bit (frontiers[bb->index], x);
+ }
+ }
+}
+
+
+void
+compute_dominance_frontiers (bitmap *frontiers)
+{
+ sbitmap done = sbitmap_alloc (last_basic_block);
+
+ timevar_push (TV_DOM_FRONTIERS);
+
+ sbitmap_zero (done);
+
+ compute_dominance_frontiers_1 (frontiers, EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest, done);
+
+ sbitmap_free (done);
+
+ timevar_pop (TV_DOM_FRONTIERS);
+}
+
OSDN Git Service
