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) \
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. */
di->dfsnum = 1;
di->nodes = 0;
+
+ di->fake_exit_edge = dir ? BITMAP_XMALLOC () : NULL;
}
#undef init_ar
free (di->set_child);
free (di->dfs_order);
free (di->dfs_to_bb);
+ BITMAP_XFREE (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;
{
/* 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 (b->succ)
+ {
+ 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;
par = di->dfs_parent[v];
k = v;
if (reverse)
- e = bb->succ;
+ {
+ e = bb->succ;
+
+ /* If this block has a fake edge to exit, process that first. */
+ if (bitmap_bit_p (di->fake_exit_edge, bb->index))
+ {
+ e_next = e;
+ goto do_fake_exit_edge;
+ }
+ }
else
e = bb->pred;
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)
+ for (; e ; e = e_next)
{
TBB k1;
basic_block b;
e_next = e->pred_next;
}
if (b == en_block)
- k1 = di->dfs_order[last_basic_block];
+ {
+ do_fake_exit_edge:
+ k1 = di->dfs_order[last_basic_block];
+ }
else
k1 = di->dfs_order[b->index];
{
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)++;
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_NO_FAST_QUERY)
{
if (dom_computed[dir] != DOM_NONE)
- free_dominance_info (dir);
+ free_dominance_info (dir);
+
+ if (n_bbs_in_dom_tree[dir])
+ abort ();
FOR_ALL_BB (b)
{
b->dom[dir] = et_new_tree (b);
}
+ n_bbs_in_dom_tree[dir] = n_basic_blocks + 2;
- init_dom_info (&di);
+ init_dom_info (&di, dir);
calc_dfs_tree (&di, dir);
calc_idoms (&di, dir);
delete_from_dominance_info (dir, bb);
}
+ /* If there are any nodes left, something is wrong. */
+ if (n_bbs_in_dom_tree[dir])
+ abort ();
+
dom_computed[dir] = DOM_NONE;
}
if (!node->father)
return NULL;
- return node->father->data;
+ return node->father->data;
}
/* Set the immediate dominator of the block possibly removing
if (node->father)
{
if (node->father->data == dominated_by)
- return;
+ return;
et_split (node);
}
/* 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])
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);
}
err = 1;
}
}
+
+ if (dir == CDI_DOMINATORS
+ && dom_computed[dir] >= DOM_NO_FAST_QUERY)
+ {
+ FOR_EACH_BB (bb)
+ {
+ if (!dominated_by_p (dir, bb, ENTRY_BLOCK_PTR))
+ {
+ error ("ENTRY does not dominate bb %d", bb->index);
+ err = 1;
+ }
+ }
+ }
+
if (err)
abort ();
}
/* 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 fixpoint. */
+ reaches a fixed point. */
basic_block
recount_dominator (enum cdi_direction dir, basic_block bb)
{
for (e = bb->pred; e; e = e->pred_next)
{
+ /* 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;
+
if (!dominated_by_p (dir, e->src, bb))
dom_bb = nearest_common_dominator (dir, dom_bb, e->src);
}
if (!dom_computed[dir])
abort ();
+ for (i = 0; i < n; i++)
+ set_immediate_dominator (dir, bbs[i], NULL);
+
while (changed)
{
changed = 0;
}
}
}
+
+ for (i = 0; i < n; i++)
+ if (!get_immediate_dominator (dir, bbs[i]))
+ abort ();
}
void
if (bb->dom[dir])
abort ();
+ n_bbs_in_dom_tree[dir]++;
+
bb->dom[dir] = et_new_tree (bb);
if (dom_computed[dir] == DOM_OK)
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;
OSDN Git Service
