/* 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.
#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"
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 bool flow_active_insn_p (rtx);
\f
edge e;
edge_iterator ei;
- FOR_EACH_EDGE (e, ei, pred->succs)
- 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
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 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_iterator *stack, ei;
- 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)
- {
- max_successors = EDGE_COUNT (bb->succs);
- dfst[bb->index].node
- = (max_successors
- ? xcalloc (max_successors, sizeof (struct dfst_node *)) : NULL);
- }
-
- /* 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++] = ei_start (ENTRY_BLOCK_PTR->succs);
-
- while (sp)
- {
- basic_block src;
- basic_block dest;
-
- /* Look at the edge on the top of the stack. */
- 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);
-
- /* 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 (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 (! ei_one_before_end_p (ei))
- ei_next (&stack[sp - 1]);
- 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);
-}
-
/* 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.
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;
}
/* Determine if there are unvisited basic blocks. */
- FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR, NULL, prev_bb)
+ FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb)
if (!TEST_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1)))
return bb;
}
-/* Computing the Dominance Frontier:
+/* 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.
- 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:
+ First, we identify each join point, j (any node with more than one
+ incoming edge is a join point).
- (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.
+ 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.
+*/
- (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)
+compute_dominance_frontiers_1 (bitmap *frontiers)
{
- edge e;
+ edge p;
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)
+ basic_block b;
+ FOR_EACH_BB (b)
{
- 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))
- {
- int x;
- bitmap_iterator bi;
-
- EXECUTE_IF_SET_IN_BITMAP (frontiers[c->index], 0, x, bi)
+ if (EDGE_COUNT (b->preds) >= 2)
{
- if (get_immediate_dominator (CDI_DOMINATORS, BASIC_BLOCK (x)) != bb)
- bitmap_set_bit (frontiers[bb->index], x);
+ 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)
{
- 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);
+ compute_dominance_frontiers_1 (frontiers);
timevar_pop (TV_DOM_FRONTIERS);
}
OSDN Git Service
