#include "timevar.h"
/* Whether the dominators and the postdominators are available. */
-enum dom_state dom_computed[2];
+static enum dom_state dom_computed[2];
/* 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
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_dfs_tree (struct dom_info *, enum cdi_direction);
+static void calc_dfs_tree_nonrec (struct dom_info *, basic_block, bool);
+static void calc_dfs_tree (struct dom_info *, bool);
static void compress (struct dom_info *, TBB);
static TBB eval (struct dom_info *, TBB);
static void link_roots (struct dom_info *, TBB, TBB);
-static void calc_idoms (struct dom_info *, enum cdi_direction);
+static void calc_idoms (struct dom_info *, bool);
void debug_dominance_info (enum cdi_direction);
/* Keeps track of the*/
di->dfsnum = 1;
di->nodes = 0;
- di->fake_exit_edge = dir ? BITMAP_ALLOC (NULL) : NULL;
+ switch (dir)
+ {
+ case CDI_DOMINATORS:
+ di->fake_exit_edge = NULL;
+ break;
+ case CDI_POST_DOMINATORS:
+ di->fake_exit_edge = BITMAP_ALLOC (NULL);
+ break;
+ default:
+ gcc_unreachable ();
+ break;
+ }
}
#undef init_ar
+/* Map dominance calculation type to array index used for various
+ dominance information arrays. This version is simple -- it will need
+ to be modified, obviously, if additional values are added to
+ cdi_direction. */
+
+static unsigned int
+dom_convert_dir_to_idx (enum cdi_direction dir)
+{
+ gcc_assert (dir == CDI_DOMINATORS || dir == CDI_POST_DOMINATORS);
+ return dir - 1;
+}
+
/* Free all allocated memory in DI, but not DI itself. */
static void
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, bool reverse)
{
/* We call this _only_ if bb is not already visited. */
edge e;
because there may be nodes from which the EXIT_BLOCK is unreachable. */
static void
-calc_dfs_tree (struct dom_info *di, enum cdi_direction reverse)
+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;
On return the immediate dominator to node V is in di->dom[V]. */
static void
-calc_idoms (struct dom_info *di, enum cdi_direction reverse)
+calc_idoms (struct dom_info *di, bool reverse)
{
TBB v, w, k, par;
basic_block en_block;
{
int num = 0;
basic_block bb;
+ unsigned int dir_index = dom_convert_dir_to_idx (dir);
gcc_assert (dom_info_available_p (dir));
- if (dom_computed[dir] == DOM_OK)
+ if (dom_computed[dir_index] == DOM_OK)
return;
FOR_ALL_BB (bb)
{
- if (!bb->dom[dir]->father)
- assign_dfs_numbers (bb->dom[dir], &num);
+ if (!bb->dom[dir_index]->father)
+ assign_dfs_numbers (bb->dom[dir_index], &num);
}
- dom_computed[dir] = DOM_OK;
+ dom_computed[dir_index] = DOM_OK;
}
/* The main entry point into this module. DIR is set depending on whether
{
struct dom_info di;
basic_block b;
+ unsigned int dir_index = dom_convert_dir_to_idx (dir);
+ bool reverse = (dir == CDI_POST_DOMINATORS) ? true : false;
- if (dom_computed[dir] == DOM_OK)
+ if (dom_computed[dir_index] == DOM_OK)
return;
timevar_push (TV_DOMINANCE);
if (!dom_info_available_p (dir))
{
- gcc_assert (!n_bbs_in_dom_tree[dir]);
+ gcc_assert (!n_bbs_in_dom_tree[dir_index]);
FOR_ALL_BB (b)
{
- b->dom[dir] = et_new_tree (b);
+ b->dom[dir_index] = et_new_tree (b);
}
- n_bbs_in_dom_tree[dir] = n_basic_blocks;
+ n_bbs_in_dom_tree[dir_index] = n_basic_blocks;
init_dom_info (&di, dir);
- calc_dfs_tree (&di, dir);
- calc_idoms (&di, dir);
+ calc_dfs_tree (&di, reverse);
+ calc_idoms (&di, reverse);
FOR_EACH_BB (b)
{
TBB d = di.dom[di.dfs_order[b->index]];
if (di.dfs_to_bb[d])
- et_set_father (b->dom[dir], di.dfs_to_bb[d]->dom[dir]);
+ et_set_father (b->dom[dir_index], di.dfs_to_bb[d]->dom[dir_index]);
}
free_dom_info (&di);
- dom_computed[dir] = DOM_NO_FAST_QUERY;
+ dom_computed[dir_index] = DOM_NO_FAST_QUERY;
}
compute_dom_fast_query (dir);
free_dominance_info (enum cdi_direction dir)
{
basic_block bb;
+ unsigned int dir_index = dom_convert_dir_to_idx (dir);
if (!dom_info_available_p (dir))
return;
FOR_ALL_BB (bb)
{
- et_free_tree_force (bb->dom[dir]);
- bb->dom[dir] = NULL;
+ et_free_tree_force (bb->dom[dir_index]);
+ bb->dom[dir_index] = NULL;
}
et_free_pools ();
- n_bbs_in_dom_tree[dir] = 0;
+ n_bbs_in_dom_tree[dir_index] = 0;
- dom_computed[dir] = DOM_NONE;
+ dom_computed[dir_index] = DOM_NONE;
}
/* Return the immediate dominator of basic block BB. */
basic_block
get_immediate_dominator (enum cdi_direction dir, basic_block bb)
{
- struct et_node *node = bb->dom[dir];
+ unsigned int dir_index = dom_convert_dir_to_idx (dir);
+ struct et_node *node = bb->dom[dir_index];
- gcc_assert (dom_computed[dir]);
+ gcc_assert (dom_computed[dir_index]);
if (!node->father)
return NULL;
set_immediate_dominator (enum cdi_direction dir, basic_block bb,
basic_block dominated_by)
{
- struct et_node *node = bb->dom[dir];
-
- gcc_assert (dom_computed[dir]);
+ unsigned int dir_index = dom_convert_dir_to_idx (dir);
+ struct et_node *node = bb->dom[dir_index];
+
+ gcc_assert (dom_computed[dir_index]);
if (node->father)
{
}
if (dominated_by)
- et_set_father (node, dominated_by->dom[dir]);
+ et_set_father (node, dominated_by->dom[dir_index]);
- if (dom_computed[dir] == DOM_OK)
- dom_computed[dir] = DOM_NO_FAST_QUERY;
+ if (dom_computed[dir_index] == DOM_OK)
+ dom_computed[dir_index] = DOM_NO_FAST_QUERY;
}
/* Store all basic blocks immediately dominated by BB into BBS and return
int
get_dominated_by (enum cdi_direction dir, basic_block bb, basic_block **bbs)
{
+ unsigned int dir_index = dom_convert_dir_to_idx (dir);
int n;
- struct et_node *node = bb->dom[dir], *son = node->son, *ason;
-
- gcc_assert (dom_computed[dir]);
+ struct et_node *node = bb->dom[dir_index], *son = node->son, *ason;
+
+ gcc_assert (dom_computed[dir_index]);
if (!son)
{
redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
basic_block to)
{
- struct et_node *bb_node = bb->dom[dir], *to_node = to->dom[dir], *son;
+ 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]);
+ gcc_assert (dom_computed[dir_index]);
if (!bb_node->son)
return;
et_set_father (son, to_node);
}
- if (dom_computed[dir] == DOM_OK)
- dom_computed[dir] = DOM_NO_FAST_QUERY;
+ if (dom_computed[dir_index] == DOM_OK)
+ dom_computed[dir_index] = DOM_NO_FAST_QUERY;
}
/* Find first basic block in the tree dominating both BB1 and BB2. */
basic_block
nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block bb2)
{
- gcc_assert (dom_computed[dir]);
+ unsigned int dir_index = dom_convert_dir_to_idx (dir);
+
+ gcc_assert (dom_computed[dir_index]);
if (!bb1)
return bb2;
if (!bb2)
return bb1;
- return et_nca (bb1->dom[dir], bb2->dom[dir])->data;
+ return et_nca (bb1->dom[dir_index], bb2->dom[dir_index])->data;
}
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];
-
- gcc_assert (dom_computed[dir]);
+ 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]);
- if (dom_computed[dir] == DOM_OK)
+ if (dom_computed[dir_index] == DOM_OK)
return (n1->dfs_num_in >= n2->dfs_num_in
&& 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)
+{
+ 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);
+ 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)
+{
+ 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);
+ return n->dfs_num_out;
+}
+
/* Verify invariants of dominator structure. */
void
verify_dominators (enum cdi_direction dir)
basic_block
recount_dominator (enum cdi_direction dir, basic_block bb)
{
+ unsigned int dir_index = dom_convert_dir_to_idx (dir);
basic_block dom_bb = NULL;
edge e;
edge_iterator ei;
- gcc_assert (dom_computed[dir]);
+ gcc_assert (dom_computed[dir_index]);
if (dir == CDI_DOMINATORS)
{
void
iterate_fix_dominators (enum cdi_direction dir, basic_block *bbs, int n)
{
+ unsigned int dir_index = dom_convert_dir_to_idx (dir);
int i, changed = 1;
basic_block old_dom, new_dom;
- gcc_assert (dom_computed[dir]);
+ gcc_assert (dom_computed[dir_index]);
for (i = 0; i < n; i++)
set_immediate_dominator (dir, bbs[i], NULL);
void
add_to_dominance_info (enum cdi_direction dir, basic_block bb)
{
- gcc_assert (dom_computed[dir]);
- gcc_assert (!bb->dom[dir]);
+ unsigned int dir_index = dom_convert_dir_to_idx (dir);
- n_bbs_in_dom_tree[dir]++;
+ gcc_assert (dom_computed[dir_index]);
+ gcc_assert (!bb->dom[dir_index]);
+
+ n_bbs_in_dom_tree[dir_index]++;
- bb->dom[dir] = et_new_tree (bb);
+ bb->dom[dir_index] = et_new_tree (bb);
- if (dom_computed[dir] == DOM_OK)
- dom_computed[dir] = DOM_NO_FAST_QUERY;
+ if (dom_computed[dir_index] == DOM_OK)
+ dom_computed[dir_index] = DOM_NO_FAST_QUERY;
}
void
delete_from_dominance_info (enum cdi_direction dir, basic_block bb)
{
- gcc_assert (dom_computed[dir]);
+ unsigned int dir_index = dom_convert_dir_to_idx (dir);
+
+ gcc_assert (dom_computed[dir_index]);
- et_free_tree (bb->dom[dir]);
- bb->dom[dir] = NULL;
- n_bbs_in_dom_tree[dir]--;
+ et_free_tree (bb->dom[dir_index]);
+ bb->dom[dir_index] = NULL;
+ n_bbs_in_dom_tree[dir_index]--;
- if (dom_computed[dir] == DOM_OK)
- dom_computed[dir] = DOM_NO_FAST_QUERY;
+ if (dom_computed[dir_index] == DOM_OK)
+ dom_computed[dir_index] = DOM_NO_FAST_QUERY;
}
/* Returns the first son of BB in the dominator or postdominator tree
basic_block
first_dom_son (enum cdi_direction dir, basic_block bb)
{
- struct et_node *son = bb->dom[dir]->son;
+ unsigned int dir_index = dom_convert_dir_to_idx (dir);
+ struct et_node *son = bb->dom[dir_index]->son;
return son ? son->data : NULL;
}
basic_block
next_dom_son (enum cdi_direction dir, basic_block bb)
{
- struct et_node *next = bb->dom[dir]->right;
+ 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 dominance availability for dominance info DIR. */
+
+enum dom_state
+dom_info_state (enum cdi_direction dir)
+{
+ unsigned int dir_index = dom_convert_dir_to_idx (dir);
+
+ return dom_computed[dir_index];
+}
+
+/* Set the dominance availability for dominance info DIR to NEW_STATE. */
+
+void
+set_dom_info_availability (enum cdi_direction dir, enum dom_state new_state)
+{
+ unsigned int dir_index = dom_convert_dir_to_idx (dir);
+
+ dom_computed[dir_index] = new_state;
+}
+
/* 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;
+ unsigned int dir_index = dom_convert_dir_to_idx (dir);
+
+ return dom_computed[dir_index] != DOM_NONE;
}
void
OSDN Git Service
