/* Calculate (post)dominators in slightly super-linear time.
- Copyright (C) 2000, 2003, 2004 Free Software Foundation, Inc.
+ Copyright (C) 2000, 2003, 2004, 2005 Free Software Foundation, Inc.
Contributed by Michael Matz (matz@ifh.de).
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 implements the well known algorithm from Lengauer and Tarjan
to compute the dominators in a control flow graph. A basic block D is said
The algorithm computes this dominator tree implicitly by computing for
each block its immediate dominator. We use tree balancing and path
- compression, so its the O(e*a(e,v)) variant, where a(e,v) is the very
+ compression, so it's the O(e*a(e,v)) variant, where a(e,v) is the very
slowly growing functional inverse of the Ackerman function. */
#include "config.h"
#include "tm.h"
#include "rtl.h"
#include "hard-reg-set.h"
+#include "obstack.h"
#include "basic-block.h"
-#include "errors.h"
+#include "toplev.h"
#include "et-forest.h"
+#include "timevar.h"
/* Whether the dominators and the postdominators are available. */
enum dom_state dom_computed[2];
'undefined' or 'end of list'. The name of each node is given by the dfs
number of the corresponding basic block. Please note, that we include the
artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to
- support multiple entry points. As it has no real basic block index we use
- 'last_basic_block' for that. Its dfs number is of course 1. */
+ support multiple entry points. Its dfs number is of course 1. */
/* Type of Basic Block aka. TBB */
typedef unsigned int TBB;
is true for every basic block bb, but not the opposite. */
basic_block *dfs_to_bb;
- /* This is the next free DFS number when creating the DFS tree or forest. */
+ /* This is the next free DFS number when creating the DFS tree. */
unsigned int dfsnum;
/* The number of nodes in the DFS tree (==dfsnum-1). */
unsigned int nodes;
+
+ /* Blocks with bits set here have a fake edge to EXIT. These are used
+ to turn a DFS forest into a proper tree. */
+ bitmap fake_exit_edge;
};
-static void init_dom_info (struct dom_info *);
+static void init_dom_info (struct dom_info *, enum cdi_direction);
static void free_dom_info (struct dom_info *);
static void calc_dfs_tree_nonrec (struct dom_info *, basic_block,
enum cdi_direction);
static void calc_idoms (struct dom_info *, enum cdi_direction);
void debug_dominance_info (enum cdi_direction);
+/* Keeps track of the*/
+static unsigned n_bbs_in_dom_tree[2];
+
/* Helper macro for allocating and initializing an array,
for aesthetic reasons. */
#define init_ar(var, type, num, content) \
{ \
unsigned int i = 1; /* Catch content == i. */ \
if (! (content)) \
- (var) = xcalloc ((num), sizeof (type)); \
+ (var) = XCNEWVEC (type, num); \
else \
{ \
- (var) = xmalloc ((num) * sizeof (type)); \
+ (var) = XNEWVEC (type, (num)); \
for (i = 0; i < num; i++) \
(var)[i] = (content); \
} \
This initializes the contents of DI, which already must be allocated. */
static void
-init_dom_info (struct dom_info *di)
+init_dom_info (struct dom_info *di, enum cdi_direction dir)
{
- /* We need memory for n_basic_blocks nodes and the ENTRY_BLOCK or
- EXIT_BLOCK. */
- unsigned int num = n_basic_blocks + 1 + 1;
+ unsigned int num = n_basic_blocks;
init_ar (di->dfs_parent, TBB, num, 0);
init_ar (di->path_min, TBB, num, i);
init_ar (di->key, TBB, num, i);
di->dfsnum = 1;
di->nodes = 0;
+
+ di->fake_exit_edge = dir ? BITMAP_ALLOC (NULL) : NULL;
}
#undef init_ar
free (di->set_child);
free (di->dfs_order);
free (di->dfs_to_bb);
+ BITMAP_FREE (di->fake_exit_edge);
}
/* The nonrecursive variant of creating a DFS tree. DI is our working
assigned their dfs number and are linked together to form a tree. */
static void
-calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, enum cdi_direction reverse)
+calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb,
+ enum cdi_direction reverse)
{
- /* We never call this with bb==EXIT_BLOCK_PTR (ENTRY_BLOCK_PTR if REVERSE). */
/* We call this _only_ if bb is not already visited. */
edge e;
TBB child_i, my_i = 0;
- edge *stack;
+ edge_iterator *stack;
+ edge_iterator ei, einext;
int sp;
/* Start block (ENTRY_BLOCK_PTR for forward problem, EXIT_BLOCK for backward
problem). */
/* Ending block. */
basic_block ex_block;
- stack = xmalloc ((n_basic_blocks + 3) * sizeof (edge));
+ stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
sp = 0;
/* Initialize our border blocks, and the first edge. */
if (reverse)
{
- e = bb->pred;
+ ei = ei_start (bb->preds);
en_block = EXIT_BLOCK_PTR;
ex_block = ENTRY_BLOCK_PTR;
}
else
{
- e = bb->succ;
+ ei = ei_start (bb->succs);
en_block = ENTRY_BLOCK_PTR;
ex_block = EXIT_BLOCK_PTR;
}
/* This loop traverses edges e in depth first manner, and fills the
stack. */
- while (e)
+ while (!ei_end_p (ei))
{
- edge e_next;
+ e = ei_edge (ei);
/* Deduce from E the current and the next block (BB and BN), and the
next edge. */
with the next edge out of the current node. */
if (bn == ex_block || di->dfs_order[bn->index])
{
- e = e->pred_next;
+ ei_next (&ei);
continue;
}
bb = e->dest;
- e_next = bn->pred;
+ einext = ei_start (bn->preds);
}
else
{
bn = e->dest;
if (bn == ex_block || di->dfs_order[bn->index])
{
- e = e->succ_next;
+ ei_next (&ei);
continue;
}
bb = e->src;
- e_next = bn->succ;
+ einext = ei_start (bn->succs);
}
- if (bn == en_block)
- abort ();
+ gcc_assert (bn != en_block);
/* Fill the DFS tree info calculatable _before_ recursing. */
if (bb != en_block)
di->dfs_parent[child_i] = my_i;
/* Save the current point in the CFG on the stack, and recurse. */
- stack[sp++] = e;
- e = e_next;
+ stack[sp++] = ei;
+ ei = einext;
}
if (!sp)
break;
- e = stack[--sp];
+ ei = stack[--sp];
/* OK. The edge-list was exhausted, meaning normally we would
end the recursion. After returning from the recursive call,
the block not yet completed (the parent of the one above)
in e->src. This could be used e.g. for computing the number of
descendants or the tree depth. */
- if (reverse)
- e = e->pred_next;
- else
- e = e->succ_next;
+ ei_next (&ei);
}
free (stack);
}
{
/* In the post-dom case we may have nodes without a path to EXIT_BLOCK.
They are reverse-unreachable. In the dom-case we disallow such
- nodes, but in post-dom we have to deal with them, so we simply
- include them in the DFS tree which actually becomes a forest. */
+ nodes, but in post-dom we have to deal with them.
+
+ There are two situations in which this occurs. First, noreturn
+ functions. Second, infinite loops. In the first case we need to
+ pretend that there is an edge to the exit block. In the second
+ case, we wind up with a forest. We need to process all noreturn
+ blocks before we know if we've got any infinite loops. */
+
basic_block b;
+ bool saw_unconnected = false;
+
FOR_EACH_BB_REVERSE (b)
{
- if (di->dfs_order[b->index])
- continue;
+ if (EDGE_COUNT (b->succs) > 0)
+ {
+ if (di->dfs_order[b->index] == 0)
+ saw_unconnected = true;
+ continue;
+ }
+ bitmap_set_bit (di->fake_exit_edge, b->index);
di->dfs_order[b->index] = di->dfsnum;
di->dfs_to_bb[di->dfsnum] = b;
+ di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block];
di->dfsnum++;
calc_dfs_tree_nonrec (di, b, reverse);
}
+
+ if (saw_unconnected)
+ {
+ FOR_EACH_BB_REVERSE (b)
+ {
+ if (di->dfs_order[b->index])
+ continue;
+ bitmap_set_bit (di->fake_exit_edge, b->index);
+ di->dfs_order[b->index] = di->dfsnum;
+ di->dfs_to_bb[di->dfsnum] = b;
+ di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block];
+ di->dfsnum++;
+ calc_dfs_tree_nonrec (di, b, reverse);
+ }
+ }
}
di->nodes = di->dfsnum - 1;
/* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all. */
- if (di->nodes != (unsigned int) n_basic_blocks + 1)
- abort ();
+ gcc_assert (di->nodes == (unsigned int) n_basic_blocks - 1);
}
/* Compress the path from V to the root of its set and update path_min at the
{
TBB v, w, k, par;
basic_block en_block;
+ edge_iterator ei, einext;
+
if (reverse)
en_block = EXIT_BLOCK_PTR;
else
while (v > 1)
{
basic_block bb = di->dfs_to_bb[v];
- edge e, e_next;
+ edge e;
par = di->dfs_parent[v];
k = v;
+
+ ei = (reverse) ? ei_start (bb->succs) : ei_start (bb->preds);
+
if (reverse)
- e = bb->succ;
- else
- e = bb->pred;
+ {
+ /* If this block has a fake edge to exit, process that first. */
+ if (bitmap_bit_p (di->fake_exit_edge, bb->index))
+ {
+ einext = ei;
+ einext.index = 0;
+ goto do_fake_exit_edge;
+ }
+ }
/* Search all direct predecessors for the smallest node with a path
to them. That way we have the smallest node with also a path to
us only over nodes behind us. In effect we search for our
semidominator. */
- for (; e; e = e_next)
+ while (!ei_end_p (ei))
{
TBB k1;
basic_block b;
- if (reverse)
- {
- b = e->dest;
- e_next = e->succ_next;
- }
- else
+ e = ei_edge (ei);
+ b = (reverse) ? e->dest : e->src;
+ einext = ei;
+ ei_next (&einext);
+
+ if (b == en_block)
{
- b = e->src;
- e_next = e->pred_next;
+ do_fake_exit_edge:
+ k1 = di->dfs_order[last_basic_block];
}
- if (b == en_block)
- k1 = di->dfs_order[last_basic_block];
else
k1 = di->dfs_order[b->index];
k1 = di->key[eval (di, k1)];
if (k1 < k)
k = k1;
+
+ ei = einext;
}
di->key[v] = k;
{
assign_dfs_numbers (node->son, num);
for (son = node->son->right; son != node->son; son = son->right)
- assign_dfs_numbers (son, num);
+ assign_dfs_numbers (son, num);
}
node->dfs_num_out = (*num)++;
int num = 0;
basic_block bb;
- if (dom_computed[dir] < DOM_NO_FAST_QUERY)
- abort ();
+ gcc_assert (dom_info_available_p (dir));
if (dom_computed[dir] == DOM_OK)
return;
FOR_ALL_BB (bb)
{
if (!bb->dom[dir]->father)
- assign_dfs_numbers (bb->dom[dir], &num);
+ assign_dfs_numbers (bb->dom[dir], &num);
}
dom_computed[dir] = DOM_OK;
if (dom_computed[dir] == DOM_OK)
return;
- if (dom_computed[dir] != DOM_NO_FAST_QUERY)
+ timevar_push (TV_DOMINANCE);
+ if (!dom_info_available_p (dir))
{
- if (dom_computed[dir] != DOM_NONE)
- free_dominance_info (dir);
+ gcc_assert (!n_bbs_in_dom_tree[dir]);
FOR_ALL_BB (b)
{
b->dom[dir] = et_new_tree (b);
}
+ n_bbs_in_dom_tree[dir] = n_basic_blocks;
- init_dom_info (&di);
+ init_dom_info (&di, dir);
calc_dfs_tree (&di, dir);
calc_idoms (&di, dir);
}
compute_dom_fast_query (dir);
+
+ timevar_pop (TV_DOMINANCE);
}
/* Free dominance information for direction DIR. */
{
basic_block bb;
- if (!dom_computed[dir])
+ if (!dom_info_available_p (dir))
return;
FOR_ALL_BB (bb)
{
- delete_from_dominance_info (dir, bb);
+ et_free_tree_force (bb->dom[dir]);
+ bb->dom[dir] = NULL;
}
+ et_free_pools ();
+
+ n_bbs_in_dom_tree[dir] = 0;
dom_computed[dir] = DOM_NONE;
}
{
struct et_node *node = bb->dom[dir];
- if (!dom_computed[dir])
- abort ();
+ gcc_assert (dom_computed[dir]);
if (!node->father)
return NULL;
- return node->father->data;
+ return node->father->data;
}
/* Set the immediate dominator of the block possibly removing
{
struct et_node *node = bb->dom[dir];
- if (!dom_computed[dir])
- abort ();
+ gcc_assert (dom_computed[dir]);
if (node->father)
{
if (node->father->data == dominated_by)
- return;
+ return;
et_split (node);
}
int n;
struct et_node *node = bb->dom[dir], *son = node->son, *ason;
- if (!dom_computed[dir])
- abort ();
+ gcc_assert (dom_computed[dir]);
if (!son)
{
for (ason = son->right, n = 1; ason != son; ason = ason->right)
n++;
- *bbs = xmalloc (n * sizeof (basic_block));
+ *bbs = XNEWVEC (basic_block, n);
(*bbs)[0] = son->data;
for (ason = son->right, n = 1; ason != son; ason = ason->right)
(*bbs)[n++] = ason->data;
return n;
}
+/* Find all basic blocks that are immediately dominated (in direction DIR)
+ by some block between N_REGION ones stored in REGION, except for blocks
+ in the REGION itself. The found blocks are stored to DOMS and their number
+ is returned. */
+
+unsigned
+get_dominated_by_region (enum cdi_direction dir, basic_block *region,
+ unsigned n_region, basic_block *doms)
+{
+ unsigned n_doms = 0, i;
+ basic_block dom;
+
+ for (i = 0; i < n_region; i++)
+ region[i]->flags |= BB_DUPLICATED;
+ for (i = 0; i < n_region; i++)
+ for (dom = first_dom_son (dir, region[i]);
+ dom;
+ dom = next_dom_son (dir, dom))
+ if (!(dom->flags & BB_DUPLICATED))
+ doms[n_doms++] = dom;
+ for (i = 0; i < n_region; i++)
+ region[i]->flags &= ~BB_DUPLICATED;
+
+ return n_doms;
+}
+
/* Redirect all edges pointing to BB to TO. */
void
redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
{
struct et_node *bb_node = bb->dom[dir], *to_node = to->dom[dir], *son;
- if (!dom_computed[dir])
- abort ();
+ gcc_assert (dom_computed[dir]);
if (!bb_node->son)
return;
basic_block
nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2)
{
- if (!dom_computed[dir])
- abort ();
+ gcc_assert (dom_computed[dir]);
if (!bb1)
return bb2;
return et_nca (bb1->dom[dir], bb2->dom[dir])->data;
}
+
+/* Find the nearest common dominator for the basic blocks in BLOCKS,
+ using dominance direction DIR. */
+
+basic_block
+nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
+{
+ unsigned i, first;
+ bitmap_iterator bi;
+ basic_block dom;
+
+ first = bitmap_first_set_bit (blocks);
+ dom = BASIC_BLOCK (first);
+ EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
+ if (dom != BASIC_BLOCK (i))
+ dom = nearest_common_dominator (dir, dom, BASIC_BLOCK (i));
+
+ return dom;
+}
+
+/* Given a dominator tree, we can determine whether one thing
+ dominates another in constant time by using two DFS numbers:
+
+ 1. The number for when we visit a node on the way down the tree
+ 2. The number for when we visit a node on the way back up the tree
+
+ You can view these as bounds for the range of dfs numbers the
+ nodes in the subtree of the dominator tree rooted at that node
+ will contain.
+
+ The dominator tree is always a simple acyclic tree, so there are
+ only three possible relations two nodes in the dominator tree have
+ to each other:
+
+ 1. Node A is above Node B (and thus, Node A dominates node B)
+
+ A
+ |
+ C
+ / \
+ B D
+
+
+ In the above case, DFS_Number_In of A will be <= DFS_Number_In of
+ B, and DFS_Number_Out of A will be >= DFS_Number_Out of B. This is
+ because we must hit A in the dominator tree *before* B on the walk
+ down, and we will hit A *after* B on the walk back up
+
+ 2. Node A is below node B (and thus, node B dominates node A)
+
+
+ B
+ |
+ A
+ / \
+ C D
+
+ In the above case, DFS_Number_In of A will be >= DFS_Number_In of
+ B, and DFS_Number_Out of A will be <= DFS_Number_Out of B.
+
+ This is because we must hit A in the dominator tree *after* B on
+ the walk down, and we will hit A *before* B on the walk back up
+
+ 3. Node A and B are siblings (and thus, neither dominates the other)
+
+ C
+ |
+ D
+ / \
+ A B
+
+ In the above case, DFS_Number_In of A will *always* be <=
+ DFS_Number_In of B, and DFS_Number_Out of A will *always* be <=
+ DFS_Number_Out of B. This is because we will always finish the dfs
+ walk of one of the subtrees before the other, and thus, the dfs
+ numbers for one subtree can't intersect with the range of dfs
+ numbers for the other subtree. If you swap A and B's position in
+ the dominator tree, the comparison changes direction, but the point
+ is that both comparisons will always go the same way if there is no
+ dominance relationship.
+
+ Thus, it is sufficient to write
+
+ A_Dominates_B (node A, node B)
+ {
+ return DFS_Number_In(A) <= DFS_Number_In(B)
+ && DFS_Number_Out (A) >= DFS_Number_Out(B);
+ }
+
+ A_Dominated_by_B (node A, node B)
+ {
+ return DFS_Number_In(A) >= DFS_Number_In(A)
+ && DFS_Number_Out (A) <= DFS_Number_Out(B);
+ } */
+
/* Return TRUE in case BB1 is dominated by BB2. */
bool
dominated_by_p (enum cdi_direction dir, basic_block bb1, basic_block bb2)
-{
+{
struct et_node *n1 = bb1->dom[dir], *n2 = bb2->dom[dir];
- if (!dom_computed[dir])
- abort ();
+ gcc_assert (dom_computed[dir]);
if (dom_computed[dir] == DOM_OK)
return (n1->dfs_num_in >= n2->dfs_num_in
- && n1->dfs_num_out <= n2->dfs_num_out);
+ && n1->dfs_num_out <= n2->dfs_num_out);
return et_below (n1, n2);
}
+/* Returns the entry dfs number for basic block BB, in the direction DIR. */
+
+unsigned
+bb_dom_dfs_in (enum cdi_direction dir, basic_block bb)
+{
+ struct et_node *n = bb->dom[dir];
+
+ gcc_assert (dom_computed[dir] == DOM_OK);
+ return n->dfs_num_in;
+}
+
+/* Returns the exit dfs number for basic block BB, in the direction DIR. */
+
+unsigned
+bb_dom_dfs_out (enum cdi_direction dir, basic_block bb)
+{
+ struct et_node *n = bb->dom[dir];
+
+ gcc_assert (dom_computed[dir] == DOM_OK);
+ return n->dfs_num_out;
+}
+
/* Verify invariants of dominator structure. */
void
verify_dominators (enum cdi_direction dir)
int err = 0;
basic_block bb;
- if (!dom_computed[dir])
- abort ();
+ gcc_assert (dom_info_available_p (dir));
FOR_EACH_BB (bb)
{
basic_block dom_bb;
+ basic_block imm_bb;
dom_bb = recount_dominator (dir, bb);
- if (dom_bb != get_immediate_dominator (dir, bb))
+ imm_bb = get_immediate_dominator (dir, bb);
+ if (dom_bb != imm_bb)
{
- error ("dominator of %d should be %d, not %d",
- bb->index, dom_bb->index, get_immediate_dominator(dir, bb)->index);
+ if ((dom_bb == NULL) || (imm_bb == NULL))
+ error ("dominator of %d status unknown", bb->index);
+ else
+ error ("dominator of %d should be %d, not %d",
+ bb->index, dom_bb->index, imm_bb->index);
err = 1;
}
}
- if (err)
- abort ();
+
+ if (dir == CDI_DOMINATORS)
+ {
+ FOR_EACH_BB (bb)
+ {
+ if (!dominated_by_p (dir, bb, ENTRY_BLOCK_PTR))
+ {
+ error ("ENTRY does not dominate bb %d", bb->index);
+ err = 1;
+ }
+ }
+ }
+
+ gcc_assert (!err);
}
-/* Recount dominator of BB. */
+/* Determine immediate dominator (or postdominator, according to DIR) of BB,
+ assuming that dominators of other blocks are correct. We also use it to
+ recompute the dominators in a restricted area, by iterating it until it
+ reaches a fixed point. */
+
basic_block
recount_dominator (enum cdi_direction dir, basic_block bb)
{
- basic_block dom_bb = NULL;
- edge e;
+ basic_block dom_bb = NULL;
+ edge e;
+ edge_iterator ei;
- if (!dom_computed[dir])
- abort ();
+ gcc_assert (dom_computed[dir]);
- for (e = bb->pred; e; e = e->pred_next)
- {
- if (!dominated_by_p (dir, e->src, bb))
- dom_bb = nearest_common_dominator (dir, dom_bb, e->src);
- }
+ if (dir == CDI_DOMINATORS)
+ {
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ /* Ignore the predecessors that either are not reachable from
+ the entry block, or whose dominator was not determined yet. */
+ if (!dominated_by_p (dir, e->src, ENTRY_BLOCK_PTR))
+ continue;
- return dom_bb;
+ if (!dominated_by_p (dir, e->src, bb))
+ dom_bb = nearest_common_dominator (dir, dom_bb, e->src);
+ }
+ }
+ else
+ {
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ if (!dominated_by_p (dir, e->dest, bb))
+ dom_bb = nearest_common_dominator (dir, dom_bb, e->dest);
+ }
+ }
+
+ return dom_bb;
}
/* Iteratively recount dominators of BBS. The change is supposed to be local
int i, changed = 1;
basic_block old_dom, new_dom;
- if (!dom_computed[dir])
- abort ();
+ gcc_assert (dom_computed[dir]);
+
+ for (i = 0; i < n; i++)
+ set_immediate_dominator (dir, bbs[i], NULL);
while (changed)
{
}
}
}
+
+ for (i = 0; i < n; i++)
+ gcc_assert (get_immediate_dominator (dir, bbs[i]));
}
void
add_to_dominance_info (enum cdi_direction dir, basic_block bb)
{
- if (!dom_computed[dir])
- abort ();
-
- if (bb->dom[dir])
- abort ();
+ gcc_assert (dom_computed[dir]);
+ gcc_assert (!bb->dom[dir]);
+ n_bbs_in_dom_tree[dir]++;
+
bb->dom[dir] = et_new_tree (bb);
if (dom_computed[dir] == DOM_OK)
void
delete_from_dominance_info (enum cdi_direction dir, basic_block bb)
{
- if (!dom_computed[dir])
- abort ();
+ gcc_assert (dom_computed[dir]);
et_free_tree (bb->dom[dir]);
bb->dom[dir] = NULL;
+ n_bbs_in_dom_tree[dir]--;
if (dom_computed[dir] == DOM_OK)
dom_computed[dir] = DOM_NO_FAST_QUERY;
return next->father->son == next ? NULL : next->data;
}
+/* Returns true if dominance information for direction DIR is available. */
+
+bool
+dom_info_available_p (enum cdi_direction dir)
+{
+ return dom_computed[dir] != DOM_NONE;
+}
+
void
debug_dominance_info (enum cdi_direction dir)
{
OSDN Git Service
