/* Calculate (post)dominators in slightly super-linear time.
- Copyright (C) 2000, 2003, 2004, 2005, 2006, 2007, 2008 Free
- Software Foundation, Inc.
+ Copyright (C) 2000-2015 Free Software Foundation, Inc.
Contributed by Michael Matz (matz@ifh.de).
This file is part of GCC.
#include "rtl.h"
#include "hard-reg-set.h"
#include "obstack.h"
+#include "predict.h"
+#include "function.h"
+#include "dominance.h"
+#include "cfg.h"
+#include "cfganal.h"
#include "basic-block.h"
-#include "toplev.h"
+#include "diagnostic-core.h"
+#include "alloc-pool.h"
#include "et-forest.h"
#include "timevar.h"
-#include "vecprim.h"
-#include "pointer-set.h"
#include "graphds.h"
+#include "bitmap.h"
/* We name our nodes with integers, beginning with 1. Zero is reserved for
'undefined' or 'end of list'. The name of each node is given by the dfs
init_dom_info (struct dom_info *di, enum cdi_direction dir)
{
/* We need memory for n_basic_blocks nodes. */
- unsigned int num = n_basic_blocks;
+ unsigned int num = n_basic_blocks_for_fn (cfun);
init_ar (di->dfs_parent, TBB, num, 0);
init_ar (di->path_min, TBB, num, i);
init_ar (di->key, TBB, num, i);
init_ar (di->set_size, unsigned int, num, 1);
init_ar (di->set_child, TBB, num, 0);
- init_ar (di->dfs_order, TBB, (unsigned int) last_basic_block + 1, 0);
+ init_ar (di->dfs_order, TBB,
+ (unsigned int) last_basic_block_for_fn (cfun) + 1, 0);
init_ar (di->dfs_to_bb, basic_block, num, 0);
di->dfsnum = 1;
static unsigned int
dom_convert_dir_to_idx (enum cdi_direction dir)
{
- gcc_assert (dir == CDI_DOMINATORS || dir == CDI_POST_DOMINATORS);
+ gcc_checking_assert (dir == CDI_DOMINATORS || dir == CDI_POST_DOMINATORS);
return dir - 1;
}
edge_iterator *stack;
edge_iterator ei, einext;
int sp;
- /* Start block (ENTRY_BLOCK_PTR for forward problem, EXIT_BLOCK for backward
+ /* Start block (the entry block for forward problem, exit block for backward
problem). */
basic_block en_block;
/* Ending block. */
basic_block ex_block;
- stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
+ stack = XNEWVEC (edge_iterator, n_basic_blocks_for_fn (cfun) + 1);
sp = 0;
/* Initialize our border blocks, and the first edge. */
if (reverse)
{
ei = ei_start (bb->preds);
- en_block = EXIT_BLOCK_PTR;
- ex_block = ENTRY_BLOCK_PTR;
+ en_block = EXIT_BLOCK_PTR_FOR_FN (cfun);
+ ex_block = ENTRY_BLOCK_PTR_FOR_FN (cfun);
}
else
{
ei = ei_start (bb->succs);
- en_block = ENTRY_BLOCK_PTR;
- ex_block = EXIT_BLOCK_PTR;
+ en_block = ENTRY_BLOCK_PTR_FOR_FN (cfun);
+ ex_block = EXIT_BLOCK_PTR_FOR_FN (cfun);
}
/* When the stack is empty we break out of this loop. */
if (bb != en_block)
my_i = di->dfs_order[bb->index];
else
- my_i = di->dfs_order[last_basic_block];
+ my_i = di->dfs_order[last_basic_block_for_fn (cfun)];
child_i = di->dfs_order[bn->index] = di->dfsnum++;
di->dfs_to_bb[child_i] = bn;
di->dfs_parent[child_i] = my_i;
calc_dfs_tree (struct dom_info *di, bool reverse)
{
/* The first block is the ENTRY_BLOCK (or EXIT_BLOCK if REVERSE). */
- basic_block begin = reverse ? EXIT_BLOCK_PTR : ENTRY_BLOCK_PTR;
- di->dfs_order[last_basic_block] = di->dfsnum;
+ basic_block begin = (reverse
+ ? EXIT_BLOCK_PTR_FOR_FN (cfun) : ENTRY_BLOCK_PTR_FOR_FN (cfun));
+ di->dfs_order[last_basic_block_for_fn (cfun)] = di->dfsnum;
di->dfs_to_bb[di->dfsnum] = begin;
di->dfsnum++;
basic_block b;
bool saw_unconnected = false;
- FOR_EACH_BB_REVERSE (b)
+ FOR_EACH_BB_REVERSE_FN (b, cfun)
{
if (EDGE_COUNT (b->succs) > 0)
{
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->dfs_parent[di->dfsnum] =
+ di->dfs_order[last_basic_block_for_fn (cfun)];
di->dfsnum++;
calc_dfs_tree_nonrec (di, b, reverse);
}
if (saw_unconnected)
{
- FOR_EACH_BB_REVERSE (b)
+ FOR_EACH_BB_REVERSE_FN (b, cfun)
{
+ basic_block b2;
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];
+ b2 = dfs_find_deadend (b);
+ gcc_checking_assert (di->dfs_order[b2->index] == 0);
+ bitmap_set_bit (di->fake_exit_edge, b2->index);
+ di->dfs_order[b2->index] = di->dfsnum;
+ di->dfs_to_bb[di->dfsnum] = b2;
+ di->dfs_parent[di->dfsnum] =
+ di->dfs_order[last_basic_block_for_fn (cfun)];
di->dfsnum++;
- calc_dfs_tree_nonrec (di, b, reverse);
+ calc_dfs_tree_nonrec (di, b2, reverse);
+ gcc_checking_assert (di->dfs_order[b->index]);
}
}
}
di->nodes = di->dfsnum - 1;
/* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all. */
- gcc_assert (di->nodes == (unsigned int) n_basic_blocks - 1);
+ gcc_assert (di->nodes == (unsigned int) n_basic_blocks_for_fn (cfun) - 1);
}
/* Compress the path from V to the root of its set and update path_min at the
di->path_min[s] = di->path_min[w];
di->set_size[v] += di->set_size[w];
if (di->set_size[v] < 2 * di->set_size[w])
- {
- TBB tmp = s;
- s = di->set_child[v];
- di->set_child[v] = tmp;
- }
+ std::swap (di->set_child[v], s);
/* Merge all subtrees. */
while (s)
edge_iterator ei, einext;
if (reverse)
- en_block = EXIT_BLOCK_PTR;
+ en_block = EXIT_BLOCK_PTR_FOR_FN (cfun);
else
- en_block = ENTRY_BLOCK_PTR;
+ en_block = ENTRY_BLOCK_PTR_FOR_FN (cfun);
/* Go backwards in DFS order, to first look at the leafs. */
v = di->nodes;
if (b == en_block)
{
do_fake_exit_edge:
- k1 = di->dfs_order[last_basic_block];
+ k1 = di->dfs_order[last_basic_block_for_fn (cfun)];
}
else
k1 = di->dfs_order[b->index];
basic_block bb;
unsigned int dir_index = dom_convert_dir_to_idx (dir);
- gcc_assert (dom_info_available_p (dir));
+ gcc_checking_assert (dom_info_available_p (dir));
if (dom_computed[dir_index] == DOM_OK)
return;
- FOR_ALL_BB (bb)
+ FOR_ALL_BB_FN (bb, cfun)
{
if (!bb->dom[dir_index]->father)
assign_dfs_numbers (bb->dom[dir_index], &num);
bool reverse = (dir == CDI_POST_DOMINATORS) ? true : false;
if (dom_computed[dir_index] == DOM_OK)
- return;
+ {
+#if ENABLE_CHECKING
+ verify_dominators (dir);
+#endif
+ return;
+ }
timevar_push (TV_DOMINANCE);
if (!dom_info_available_p (dir))
{
gcc_assert (!n_bbs_in_dom_tree[dir_index]);
- FOR_ALL_BB (b)
+ FOR_ALL_BB_FN (b, cfun)
{
b->dom[dir_index] = et_new_tree (b);
}
- n_bbs_in_dom_tree[dir_index] = n_basic_blocks;
+ n_bbs_in_dom_tree[dir_index] = n_basic_blocks_for_fn (cfun);
init_dom_info (&di, dir);
calc_dfs_tree (&di, reverse);
calc_idoms (&di, reverse);
- FOR_EACH_BB (b)
+ FOR_EACH_BB_FN (b, cfun)
{
TBB d = di.dom[di.dfs_order[b->index]];
free_dom_info (&di);
dom_computed[dir_index] = DOM_NO_FAST_QUERY;
}
+ else
+ {
+#if ENABLE_CHECKING
+ verify_dominators (dir);
+#endif
+ }
compute_dom_fast_query (dir);
/* Free dominance information for direction DIR. */
void
-free_dominance_info (enum cdi_direction dir)
+free_dominance_info (function *fn, enum cdi_direction dir)
{
basic_block bb;
unsigned int dir_index = dom_convert_dir_to_idx (dir);
- if (!dom_info_available_p (dir))
+ if (!dom_info_available_p (fn, dir))
return;
- FOR_ALL_BB (bb)
+ FOR_ALL_BB_FN (bb, fn)
{
et_free_tree_force (bb->dom[dir_index]);
bb->dom[dir_index] = NULL;
}
et_free_pools ();
- n_bbs_in_dom_tree[dir_index] = 0;
+ fn->cfg->x_n_bbs_in_dom_tree[dir_index] = 0;
+
+ fn->cfg->x_dom_computed[dir_index] = DOM_NONE;
+}
- dom_computed[dir_index] = DOM_NONE;
+void
+free_dominance_info (enum cdi_direction dir)
+{
+ free_dominance_info (cfun, dir);
}
/* Return the immediate dominator of basic block BB. */
unsigned int dir_index = dom_convert_dir_to_idx (dir);
struct et_node *node = bb->dom[dir_index];
- gcc_assert (dom_computed[dir_index]);
+ gcc_checking_assert (dom_computed[dir_index]);
if (!node->father)
return NULL;
- return node->father->data;
+ return (basic_block) node->father->data;
}
/* Set the immediate dominator of the block possibly removing
existing edge. NULL can be used to remove any edge. */
-inline void
+void
set_immediate_dominator (enum cdi_direction dir, basic_block bb,
basic_block dominated_by)
{
unsigned int dir_index = dom_convert_dir_to_idx (dir);
struct et_node *node = bb->dom[dir_index];
-
- gcc_assert (dom_computed[dir_index]);
+
+ gcc_checking_assert (dom_computed[dir_index]);
if (node->father)
{
/* Returns the list of basic blocks immediately dominated by BB, in the
direction DIR. */
-VEC (basic_block, heap) *
+vec<basic_block>
get_dominated_by (enum cdi_direction dir, basic_block bb)
{
- int n;
unsigned int dir_index = dom_convert_dir_to_idx (dir);
struct et_node *node = bb->dom[dir_index], *son = node->son, *ason;
- VEC (basic_block, heap) *bbs = NULL;
+ vec<basic_block> bbs = vNULL;
- gcc_assert (dom_computed[dir_index]);
+ gcc_checking_assert (dom_computed[dir_index]);
if (!son)
- return NULL;
+ return vNULL;
- VEC_safe_push (basic_block, heap, bbs, son->data);
- for (ason = son->right, n = 1; ason != son; ason = ason->right)
- VEC_safe_push (basic_block, heap, bbs, ason->data);
+ bbs.safe_push ((basic_block) son->data);
+ for (ason = son->right; ason != son; ason = ason->right)
+ bbs.safe_push ((basic_block) ason->data);
return bbs;
}
/* Returns the list of 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. */
-
-VEC (basic_block, heap) *
+
+vec<basic_block>
get_dominated_by_region (enum cdi_direction dir, basic_block *region,
unsigned n_region)
{
unsigned i;
basic_block dom;
- VEC (basic_block, heap) *doms = NULL;
+ vec<basic_block> doms = vNULL;
for (i = 0; i < n_region; i++)
region[i]->flags |= BB_DUPLICATED;
dom;
dom = next_dom_son (dir, dom))
if (!(dom->flags & BB_DUPLICATED))
- VEC_safe_push (basic_block, heap, doms, dom);
+ doms.safe_push (dom);
for (i = 0; i < n_region; i++)
region[i]->flags &= ~BB_DUPLICATED;
return doms;
}
+/* Returns the list of basic blocks including BB dominated by BB, in the
+ direction DIR up to DEPTH in the dominator tree. The DEPTH of zero will
+ produce a vector containing all dominated blocks. The vector will be sorted
+ in preorder. */
+
+vec<basic_block>
+get_dominated_to_depth (enum cdi_direction dir, basic_block bb, int depth)
+{
+ vec<basic_block> bbs = vNULL;
+ unsigned i;
+ unsigned next_level_start;
+
+ i = 0;
+ bbs.safe_push (bb);
+ next_level_start = 1; /* = bbs.length (); */
+
+ do
+ {
+ basic_block son;
+
+ bb = bbs[i++];
+ for (son = first_dom_son (dir, bb);
+ son;
+ son = next_dom_son (dir, son))
+ bbs.safe_push (son);
+
+ if (i == next_level_start && --depth)
+ next_level_start = bbs.length ();
+ }
+ while (i < next_level_start);
+
+ return bbs;
+}
+
+/* Returns the list of basic blocks including BB dominated by BB, in the
+ direction DIR. The vector will be sorted in preorder. */
+
+vec<basic_block>
+get_all_dominated_blocks (enum cdi_direction dir, basic_block bb)
+{
+ return get_dominated_to_depth (dir, bb, 0);
+}
+
/* Redirect all edges pointing to BB to TO. */
void
redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
{
unsigned int dir_index = dom_convert_dir_to_idx (dir);
struct et_node *bb_node, *to_node, *son;
-
+
bb_node = bb->dom[dir_index];
to_node = to->dom[dir_index];
- gcc_assert (dom_computed[dir_index]);
+ gcc_checking_assert (dom_computed[dir_index]);
if (!bb_node->son)
return;
{
unsigned int dir_index = dom_convert_dir_to_idx (dir);
- gcc_assert (dom_computed[dir_index]);
+ gcc_checking_assert (dom_computed[dir_index]);
if (!bb1)
return bb2;
if (!bb2)
return bb1;
- return et_nca (bb1->dom[dir_index], bb2->dom[dir_index])->data;
+ return (basic_block) et_nca (bb1->dom[dir_index], bb2->dom[dir_index])->data;
}
unsigned i, first;
bitmap_iterator bi;
basic_block dom;
-
+
first = bitmap_first_set_bit (blocks);
- dom = BASIC_BLOCK (first);
+ dom = BASIC_BLOCK_FOR_FN (cfun, first);
EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
- if (dom != BASIC_BLOCK (i))
- dom = nearest_common_dominator (dir, dom, BASIC_BLOCK (i));
+ if (dom != BASIC_BLOCK_FOR_FN (cfun, i))
+ dom = nearest_common_dominator (dir, dom, BASIC_BLOCK_FOR_FN (cfun, i));
return dom;
}
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
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
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
A_Dominates_B (node A, node B)
{
- return DFS_Number_In(A) <= DFS_Number_In(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)
+ return DFS_Number_In(A) >= DFS_Number_In(B)
&& 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, const_basic_block bb1, const_basic_block bb2)
-{
+{
unsigned int dir_index = dom_convert_dir_to_idx (dir);
struct et_node *n1 = bb1->dom[dir_index], *n2 = bb2->dom[dir_index];
-
- gcc_assert (dom_computed[dir_index]);
+
+ gcc_checking_assert (dom_computed[dir_index]);
if (dom_computed[dir_index] == DOM_OK)
return (n1->dfs_num_in >= n2->dfs_num_in
unsigned int dir_index = dom_convert_dir_to_idx (dir);
struct et_node *n = bb->dom[dir_index];
- gcc_assert (dom_computed[dir_index] == DOM_OK);
+ gcc_checking_assert (dom_computed[dir_index] == DOM_OK);
return n->dfs_num_in;
}
unsigned int dir_index = dom_convert_dir_to_idx (dir);
struct et_node *n = bb->dom[dir_index];
- gcc_assert (dom_computed[dir_index] == DOM_OK);
+ gcc_checking_assert (dom_computed[dir_index] == DOM_OK);
return n->dfs_num_out;
}
/* Verify invariants of dominator structure. */
-void
+DEBUG_FUNCTION void
verify_dominators (enum cdi_direction dir)
{
int err = 0;
calc_dfs_tree (&di, reverse);
calc_idoms (&di, reverse);
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
{
imm_bb = get_immediate_dominator (dir, bb);
if (!imm_bb)
edge e;
edge_iterator ei;
- gcc_assert (dom_computed[dir_index]);
+ gcc_checking_assert (dom_computed[dir_index]);
if (dir == CDI_DOMINATORS)
{
from BBS. */
static void
-prune_bbs_to_update_dominators (VEC (basic_block, heap) *bbs,
+prune_bbs_to_update_dominators (vec<basic_block> bbs,
bool conservative)
{
unsigned i;
edge_iterator ei;
edge e;
- for (i = 0; VEC_iterate (basic_block, bbs, i, bb);)
+ for (i = 0; bbs.iterate (i, &bb);)
{
- if (bb == ENTRY_BLOCK_PTR)
+ if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
goto succeed;
if (single_pred_p (bb))
continue;
succeed:
- VEC_unordered_remove (basic_block, bbs, i);
+ bbs.unordered_remove (i);
}
}
static basic_block
root_of_dom_tree (enum cdi_direction dir, basic_block bb)
{
- return et_root (bb->dom[dom_convert_dir_to_idx (dir)])->data;
+ return (basic_block) et_root (bb->dom[dom_convert_dir_to_idx (dir)])->data;
}
/* See the comment in iterate_fix_dominators. Finds the immediate dominators
blocks. */
static void
-determine_dominators_for_sons (struct graph *g, VEC (basic_block, heap) *bbs,
+determine_dominators_for_sons (struct graph *g, vec<basic_block> bbs,
int y, int *son, int *brother)
{
bitmap gprime;
int i, a, nc;
- VEC (int, heap) **sccs;
+ vec<int> *sccs;
basic_block bb, dom, ybb;
unsigned si;
edge e;
if (son[y] == -1)
return;
- if (y == (int) VEC_length (basic_block, bbs))
- ybb = ENTRY_BLOCK_PTR;
+ if (y == (int) bbs.length ())
+ ybb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
else
- ybb = VEC_index (basic_block, bbs, y);
+ ybb = bbs[y];
if (brother[son[y]] == -1)
{
/* Handle the common case Y has just one son specially. */
- bb = VEC_index (basic_block, bbs, son[y]);
+ bb = bbs[son[y]];
set_immediate_dominator (CDI_DOMINATORS, bb,
recompute_dominator (CDI_DOMINATORS, bb));
identify_vertices (g, y, son[y]);
nc = graphds_scc (g, gprime);
BITMAP_FREE (gprime);
- sccs = XCNEWVEC (VEC (int, heap) *, nc);
+ /* ??? Needed to work around the pre-processor confusion with
+ using a multi-argument template type as macro argument. */
+ typedef vec<int> vec_int_heap;
+ sccs = XCNEWVEC (vec_int_heap, nc);
for (a = son[y]; a != -1; a = brother[a])
- VEC_safe_push (int, heap, sccs[g->vertices[a].component], a);
+ sccs[g->vertices[a].component].safe_push (a);
for (i = nc - 1; i >= 0; i--)
{
dom = NULL;
- for (si = 0; VEC_iterate (int, sccs[i], si, a); si++)
+ FOR_EACH_VEC_ELT (sccs[i], si, a)
{
- bb = VEC_index (basic_block, bbs, a);
+ bb = bbs[a];
FOR_EACH_EDGE (e, ei, bb->preds)
{
if (root_of_dom_tree (CDI_DOMINATORS, e->src) != ybb)
}
gcc_assert (dom != NULL);
- for (si = 0; VEC_iterate (int, sccs[i], si, a); si++)
+ FOR_EACH_VEC_ELT (sccs[i], si, a)
{
- bb = VEC_index (basic_block, bbs, a);
+ bb = bbs[a];
set_immediate_dominator (CDI_DOMINATORS, bb, dom);
}
}
for (i = 0; i < nc; i++)
- VEC_free (int, heap, sccs[i]);
+ sccs[i].release ();
free (sccs);
for (a = son[y]; a != -1; a = brother[a])
a block of BBS in the current dominance tree dominate it. */
void
-iterate_fix_dominators (enum cdi_direction dir, VEC (basic_block, heap) *bbs,
+iterate_fix_dominators (enum cdi_direction dir, vec<basic_block> bbs,
bool conservative)
{
unsigned i;
size_t dom_i;
edge e;
edge_iterator ei;
- struct pointer_map_t *map;
int *parent, *son, *brother;
unsigned int dir_index = dom_convert_dir_to_idx (dir);
problems would be unused, untested, and almost surely buggy. We keep
the DIR argument for consistency with the rest of the dominator analysis
interface. */
- gcc_assert (dir == CDI_DOMINATORS);
- gcc_assert (dom_computed[dir_index]);
+ gcc_checking_assert (dir == CDI_DOMINATORS && dom_computed[dir_index]);
/* The algorithm we use takes inspiration from the following papers, although
the details are quite different from any of them:
conservatively correct, setting the dominators using the
heuristics in prune_bbs_to_update_dominators could
create cycles in the dominance "tree", and cause ICE. */
- for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
+ FOR_EACH_VEC_ELT (bbs, i, bb)
set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
}
prune_bbs_to_update_dominators (bbs, conservative);
- n = VEC_length (basic_block, bbs);
+ n = bbs.length ();
if (n == 0)
return;
if (n == 1)
{
- bb = VEC_index (basic_block, bbs, 0);
+ bb = bbs[0];
set_immediate_dominator (CDI_DOMINATORS, bb,
recompute_dominator (CDI_DOMINATORS, bb));
return;
}
/* Construct the graph G. */
- map = pointer_map_create ();
- for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
+ hash_map<basic_block, int> map (251);
+ FOR_EACH_VEC_ELT (bbs, i, bb)
{
/* If the dominance tree is conservatively correct, split it now. */
if (conservative)
set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
- *pointer_map_insert (map, bb) = (void *) (size_t) i;
+ map.put (bb, i);
}
- *pointer_map_insert (map, ENTRY_BLOCK_PTR) = (void *) (size_t) n;
+ map.put (ENTRY_BLOCK_PTR_FOR_FN (cfun), n);
g = new_graph (n + 1);
for (y = 0; y < g->n_vertices; y++)
g->vertices[y].data = BITMAP_ALLOC (NULL);
- for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
+ FOR_EACH_VEC_ELT (bbs, i, bb)
{
FOR_EACH_EDGE (e, ei, bb->preds)
{
if (dom == bb)
continue;
- dom_i = (size_t) *pointer_map_contains (map, dom);
+ dom_i = *map.get (dom);
/* Do not include parallel edges to G. */
- if (bitmap_bit_p (g->vertices[dom_i].data, i))
+ if (!bitmap_set_bit ((bitmap) g->vertices[dom_i].data, i))
continue;
- bitmap_set_bit (g->vertices[dom_i].data, i);
add_edge (g, dom_i, i);
}
}
for (y = 0; y < g->n_vertices; y++)
BITMAP_FREE (g->vertices[y].data);
- pointer_map_destroy (map);
/* Find the dominator tree of G. */
son = XNEWVEC (int, n + 1);
{
unsigned int dir_index = dom_convert_dir_to_idx (dir);
- gcc_assert (dom_computed[dir_index]);
- gcc_assert (!bb->dom[dir_index]);
+ gcc_checking_assert (dom_computed[dir_index] && !bb->dom[dir_index]);
n_bbs_in_dom_tree[dir_index]++;
-
+
bb->dom[dir_index] = et_new_tree (bb);
if (dom_computed[dir_index] == DOM_OK)
{
unsigned int dir_index = dom_convert_dir_to_idx (dir);
- gcc_assert (dom_computed[dir_index]);
+ gcc_checking_assert (dom_computed[dir_index]);
et_free_tree (bb->dom[dir_index]);
bb->dom[dir_index] = NULL;
unsigned int dir_index = dom_convert_dir_to_idx (dir);
struct et_node *son = bb->dom[dir_index]->son;
- return son ? son->data : NULL;
+ return (basic_block) (son ? son->data : NULL);
}
/* Returns the next dominance son after BB in the dominator or postdominator
unsigned int dir_index = dom_convert_dir_to_idx (dir);
struct et_node *next = bb->dom[dir_index]->right;
- return next->father->son == next ? NULL : next->data;
+ return (basic_block) (next->father->son == next ? NULL : next->data);
}
/* Return dominance availability for dominance info DIR. */
enum dom_state
-dom_info_state (enum cdi_direction dir)
+dom_info_state (function *fn, enum cdi_direction dir)
{
+ if (!fn->cfg)
+ return DOM_NONE;
+
unsigned int dir_index = dom_convert_dir_to_idx (dir);
+ return fn->cfg->x_dom_computed[dir_index];
+}
- return dom_computed[dir_index];
+enum dom_state
+dom_info_state (enum cdi_direction dir)
+{
+ return dom_info_state (cfun, dir);
}
/* Set the dominance availability for dominance info DIR to NEW_STATE. */
/* Returns true if dominance information for direction DIR is available. */
bool
-dom_info_available_p (enum cdi_direction dir)
+dom_info_available_p (function *fn, enum cdi_direction dir)
{
- unsigned int dir_index = dom_convert_dir_to_idx (dir);
+ return dom_info_state (fn, dir) != DOM_NONE;
+}
- return dom_computed[dir_index] != DOM_NONE;
+bool
+dom_info_available_p (enum cdi_direction dir)
+{
+ return dom_info_available_p (cfun, dir);
}
-void
+DEBUG_FUNCTION void
debug_dominance_info (enum cdi_direction dir)
{
basic_block bb, bb2;
- FOR_EACH_BB (bb)
+ FOR_EACH_BB_FN (bb, cfun)
if ((bb2 = get_immediate_dominator (dir, bb)))
fprintf (stderr, "%i %i\n", bb->index, bb2->index);
}
/* Prints to stderr representation of the dominance tree (for direction DIR)
rooted in ROOT. */
-void
+DEBUG_FUNCTION void
debug_dominance_tree (enum cdi_direction dir, basic_block root)
{
debug_dominance_tree_1 (dir, root, 0, false);
projects / gcc.git / blobdiff