@@ -44,6 +44,10 @@
#include "timevar.h"
#include "graphds.h"
+#ifndef ENABLE_CHECKING
+# define ENABLE_CHECKING 0
+#endif
+
/* 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
number of the corresponding basic block. Please note, that we include the
@@ -53,139 +57,154 @@
/* Type of Basic Block aka. TBB */
typedef unsigned int TBB;
-/* We work in a poor-mans object oriented fashion, and carry an instance of
- this structure through all our 'methods'. It holds various arrays
- reflecting the (sub)structure of the flowgraph. Most of them are of type
- TBB and are also indexed by TBB. */
+namespace {
+
+/* This class holds various arrays reflecting the (sub)structure of the
+ flowgraph. Most of them are of type TBB and are also indexed by TBB. */
-struct dom_info
+class dom_info
{
+public:
+ dom_info (function *, cdi_direction);
+ ~dom_info ();
+ void calc_dfs_tree (bool);
+ void calc_idoms (bool);
+
+ inline basic_block get_idom (basic_block);
+private:
+ void calc_dfs_tree_nonrec (basic_block, bool);
+ void compress (TBB);
+ TBB eval (TBB);
+ void link_roots (TBB, TBB);
+
/* The parent of a node in the DFS tree. */
- TBB *dfs_parent;
- /* For a node x key[x] is roughly the node nearest to the root from which
+ TBB *m_dfs_parent;
+ /* For a node x m_key[x] is roughly the node nearest to the root from which
exists a way to x only over nodes behind x. Such a node is also called
semidominator. */
- TBB *key;
- /* The value in path_min[x] is the node y on the path from x to the root of
- the tree x is in with the smallest key[y]. */
- TBB *path_min;
- /* bucket[x] points to the first node of the set of nodes having x as key. */
- TBB *bucket;
- /* And next_bucket[x] points to the next node. */
- TBB *next_bucket;
- /* After the algorithm is done, dom[x] contains the immediate dominator
+ TBB *m_key;
+ /* The value in m_path_min[x] is the node y on the path from x to the root of
+ the tree x is in with the smallest m_key[y]. */
+ TBB *m_path_min;
+ /* m_bucket[x] points to the first node of the set of nodes having x as
+ key. */
+ TBB *m_bucket;
+ /* And m_next_bucket[x] points to the next node. */
+ TBB *m_next_bucket;
+ /* After the algorithm is done, m_dom[x] contains the immediate dominator
of x. */
- TBB *dom;
+ TBB *m_dom;
/* The following few fields implement the structures needed for disjoint
sets. */
- /* set_chain[x] is the next node on the path from x to the representative
- of the set containing x. If set_chain[x]==0 then x is a root. */
- TBB *set_chain;
- /* set_size[x] is the number of elements in the set named by x. */
- unsigned int *set_size;
- /* set_child[x] is used for balancing the tree representing a set. It can
+ /* m_set_chain[x] is the next node on the path from x to the representative
+ of the set containing x. If m_set_chain[x]==0 then x is a root. */
+ TBB *m_set_chain;
+ /* m_set_size[x] is the number of elements in the set named by x. */
+ unsigned int *m_set_size;
+ /* m_set_child[x] is used for balancing the tree representing a set. It can
be understood as the next sibling of x. */
- TBB *set_child;
+ TBB *m_set_child;
- /* If b is the number of a basic block (BB->index), dfs_order[b] is the
+ /* If b is the number of a basic block (BB->index), m_dfs_order[b] is the
number of that node in DFS order counted from 1. This is an index
into most of the other arrays in this structure. */
- TBB *dfs_order;
+ TBB *m_dfs_order;
/* If x is the DFS-index of a node which corresponds with a basic block,
- dfs_to_bb[x] is that basic block. Note, that in our structure there are
- more nodes that basic blocks, so only dfs_to_bb[dfs_order[bb->index]]==bb
- is true for every basic block bb, but not the opposite. */
- basic_block *dfs_to_bb;
+ m_dfs_to_bb[x] is that basic block. Note, that in our structure there are
+ more nodes that basic blocks, so only
+ m_dfs_to_bb[m_dfs_order[bb->index]]==bb is true for every basic block bb,
+ but not the opposite. */
+ basic_block *m_dfs_to_bb;
/* 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;
+ unsigned int m_dfsnum;
+ /* The number of nodes in the DFS tree (==m_dfsnum-1). */
+ unsigned int m_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;
+ bitmap m_fake_exit_edge;
+
+ /* The function being processed. */
+ function *m_fn;
};
-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, 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 *, bool);
-void debug_dominance_info (enum cdi_direction);
-void debug_dominance_tree (enum cdi_direction, basic_block);
-
-/* Helper macro for allocating and initializing an array,
- for aesthetic reasons. */
-#define init_ar(var, type, num, content) \
- do \
- { \
- unsigned int i = 1; /* Catch content == i. */ \
- if (! (content)) \
- (var) = XCNEWVEC (type, num); \
- else \
- { \
- (var) = XNEWVEC (type, (num)); \
- for (i = 0; i < num; i++) \
- (var)[i] = (content); \
- } \
- } \
- while (0)
-
-/* Allocate all needed memory in a pessimistic fashion (so we round up).
- This initializes the contents of DI, which already must be allocated. */
+} /* anon namespace */
-static void
-init_dom_info (struct dom_info *di, enum cdi_direction dir)
+void debug_dominance_info (cdi_direction);
+void debug_dominance_tree (cdi_direction, basic_block);
+
+/* Allocate and zero-initialize NUM elements of type T (T must be a
+ POD-type). Note: after transition to C++11 or later,
+ `x = new_zero_array <T> (num);' can be replaced with
+ `x = new T[num] {};'. */
+
+template<typename T>
+inline T *new_zero_array (size_t num)
+{
+ T *result = new T[num];
+ memset (result, 0, sizeof (T) * num);
+ return result;
+}
+
+/* Allocate all needed memory in a pessimistic fashion (so we round up). */
+
+dom_info::dom_info (function *fn, cdi_direction dir) : m_fn (fn)
{
/* We need memory for n_basic_blocks nodes. */
- 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->dom, TBB, num, 0);
+ size_t num = n_basic_blocks_for_fn (fn);
+ m_dfs_parent = new_zero_array <TBB> (num);
+ m_dom = new_zero_array <TBB> (num);
+
+ m_path_min = new TBB[num];
+ m_key = new TBB[num];
+ m_set_size = new unsigned int[num];
+ for (size_t i = 0; i < num; i++)
+ {
+ m_path_min[i] = m_key[i] = i;
+ m_set_size[i] = 1;
+ }
- init_ar (di->bucket, TBB, num, 0);
- init_ar (di->next_bucket, TBB, num, 0);
+ m_bucket = new_zero_array <TBB> (num);
+ m_next_bucket = new_zero_array <TBB> (num);
- init_ar (di->set_chain, TBB, num, 0);
- init_ar (di->set_size, unsigned int, num, 1);
- init_ar (di->set_child, TBB, num, 0);
+ m_set_chain = new_zero_array <TBB> (num);
+ m_set_child = new_zero_array <TBB> (num);
- 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);
+ m_dfs_order = new_zero_array <TBB> ((size_t)last_basic_block_for_fn (fn) + 1);
+ m_dfs_to_bb = new_zero_array <basic_block> (num);
- di->dfsnum = 1;
- di->nodes = 0;
+ m_dfsnum = 1;
+ m_nodes = 0;
switch (dir)
{
case CDI_DOMINATORS:
- di->fake_exit_edge = NULL;
+ m_fake_exit_edge = NULL;
break;
case CDI_POST_DOMINATORS:
- di->fake_exit_edge = BITMAP_ALLOC (NULL);
+ m_fake_exit_edge = BITMAP_ALLOC (NULL);
break;
default:
gcc_unreachable ();
- break;
}
}
-#undef init_ar
+inline basic_block
+dom_info::get_idom (basic_block bb)
+{
+ TBB d = m_dom[m_dfs_order[bb->index]];
+ return m_dfs_to_bb[d];
+}
/* 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)
+static inline unsigned int
+dom_convert_dir_to_idx (cdi_direction dir)
{
gcc_checking_assert (dir == CDI_DOMINATORS || dir == CDI_POST_DOMINATORS);
return dir - 1;
@@ -193,21 +212,20 @@ dom_convert_dir_to_idx (enum cdi_direction dir)
/* Free all allocated memory in DI, but not DI itself. */
-static void
-free_dom_info (struct dom_info *di)
+dom_info::~dom_info ()
{
- free (di->dfs_parent);
- free (di->path_min);
- free (di->key);
- free (di->dom);
- free (di->bucket);
- free (di->next_bucket);
- free (di->set_chain);
- free (di->set_size);
- free (di->set_child);
- free (di->dfs_order);
- free (di->dfs_to_bb);
- BITMAP_FREE (di->fake_exit_edge);
+ delete[] m_dfs_parent;
+ delete[] m_path_min;
+ delete[] m_key;
+ delete[] m_dom;
+ delete[] m_bucket;
+ delete[] m_next_bucket;
+ delete[] m_set_chain;
+ delete[] m_set_size;
+ delete[] m_set_child;
+ delete[] m_dfs_order;
+ delete[] m_dfs_to_bb;
+ BITMAP_FREE (m_fake_exit_edge);
}
/* The nonrecursive variant of creating a DFS tree. DI is our working
@@ -216,48 +234,45 @@ free_dom_info (struct dom_info *di)
node. After this is done all nodes reachable from BB were visited, have
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, bool reverse)
+void
+dom_info::calc_dfs_tree_nonrec (basic_block bb, bool reverse)
{
/* We call this _only_ if bb is not already visited. */
- edge e;
- TBB child_i, my_i = 0;
- edge_iterator *stack;
- edge_iterator ei, einext;
- int sp;
+ edge_iterator ei;
/* 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_for_fn (cfun) + 1);
- sp = 0;
+ edge_iterator *stack = new edge_iterator[n_basic_blocks_for_fn (m_fn) + 1];
+ int sp = 0;
/* Initialize our border blocks, and the first edge. */
if (reverse)
{
ei = ei_start (bb->preds);
- en_block = EXIT_BLOCK_PTR_FOR_FN (cfun);
- ex_block = ENTRY_BLOCK_PTR_FOR_FN (cfun);
+ en_block = EXIT_BLOCK_PTR_FOR_FN (m_fn);
+ ex_block = ENTRY_BLOCK_PTR_FOR_FN (m_fn);
}
else
{
ei = ei_start (bb->succs);
- en_block = ENTRY_BLOCK_PTR_FOR_FN (cfun);
- ex_block = EXIT_BLOCK_PTR_FOR_FN (cfun);
+ en_block = ENTRY_BLOCK_PTR_FOR_FN (m_fn);
+ ex_block = EXIT_BLOCK_PTR_FOR_FN (m_fn);
}
/* When the stack is empty we break out of this loop. */
while (1)
{
basic_block bn;
+ edge_iterator einext;
/* This loop traverses edges e in depth first manner, and fills the
stack. */
while (!ei_end_p (ei))
{
- e = ei_edge (ei);
+ edge e = ei_edge (ei);
/* Deduce from E the current and the next block (BB and BN), and the
next edge. */
@@ -268,7 +283,7 @@ calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, bool reverse)
/* If the next node BN is either already visited or a border
block the current edge is useless, and simply overwritten
with the next edge out of the current node. */
- if (bn == ex_block || di->dfs_order[bn->index])
+ if (bn == ex_block || m_dfs_order[bn->index])
{
ei_next (&ei);
continue;
@@ -279,7 +294,7 @@ calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, bool reverse)
else
{
bn = e->dest;
- if (bn == ex_block || di->dfs_order[bn->index])
+ if (bn == ex_block || m_dfs_order[bn->index])
{
ei_next (&ei);
continue;
@@ -291,13 +306,14 @@ calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, bool reverse)
gcc_assert (bn != en_block);
/* Fill the DFS tree info calculatable _before_ recursing. */
+ TBB my_i;
if (bb != en_block)
- my_i = di->dfs_order[bb->index];
+ my_i = m_dfs_order[bb->index];
else
- 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;
+ my_i = m_dfs_order[last_basic_block_for_fn (m_fn)];
+ TBB child_i = m_dfs_order[bn->index] = m_dfsnum++;
+ m_dfs_to_bb[child_i] = bn;
+ m_dfs_parent[child_i] = my_i;
/* Save the current point in the CFG on the stack, and recurse. */
stack[sp++] = ei;
@@ -319,7 +335,7 @@ calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, bool reverse)
descendants or the tree depth. */
ei_next (&ei);
}
- free (stack);
+ delete[] stack;
}
/* The main entry for calculating the DFS tree or forest. DI is our working
@@ -327,17 +343,17 @@ calc_dfs_tree_nonrec (struct dom_info *di, basic_block bb, bool reverse)
graph. In that case the result is not necessarily a tree but a forest,
because there may be nodes from which the EXIT_BLOCK is unreachable. */
-static void
-calc_dfs_tree (struct dom_info *di, bool reverse)
+void
+dom_info::calc_dfs_tree (bool reverse)
{
/* The first block is the ENTRY_BLOCK (or EXIT_BLOCK if REVERSE). */
- 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 begin = (reverse ? EXIT_BLOCK_PTR_FOR_FN (m_fn)
+ : ENTRY_BLOCK_PTR_FOR_FN (m_fn));
+ m_dfs_order[last_basic_block_for_fn (m_fn)] = m_dfsnum;
+ m_dfs_to_bb[m_dfsnum] = begin;
+ m_dfsnum++;
- calc_dfs_tree_nonrec (di, begin, reverse);
+ calc_dfs_tree_nonrec (begin, reverse);
if (reverse)
{
@@ -354,48 +370,47 @@ calc_dfs_tree (struct dom_info *di, bool reverse)
basic_block b;
bool saw_unconnected = false;
- FOR_EACH_BB_REVERSE_FN (b, cfun)
+ FOR_EACH_BB_REVERSE_FN (b, m_fn)
{
if (EDGE_COUNT (b->succs) > 0)
{
- if (di->dfs_order[b->index] == 0)
+ if (m_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_for_fn (cfun)];
- di->dfsnum++;
- calc_dfs_tree_nonrec (di, b, reverse);
+ bitmap_set_bit (m_fake_exit_edge, b->index);
+ m_dfs_order[b->index] = m_dfsnum;
+ m_dfs_to_bb[m_dfsnum] = b;
+ m_dfs_parent[m_dfsnum] =
+ m_dfs_order[last_basic_block_for_fn (m_fn)];
+ m_dfsnum++;
+ calc_dfs_tree_nonrec (b, reverse);
}
if (saw_unconnected)
{
- FOR_EACH_BB_REVERSE_FN (b, cfun)
+ FOR_EACH_BB_REVERSE_FN (b, m_fn)
{
- basic_block b2;
- if (di->dfs_order[b->index])
+ if (m_dfs_order[b->index])
continue;
- 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, b2, reverse);
- gcc_checking_assert (di->dfs_order[b->index]);
+ basic_block b2 = dfs_find_deadend (b);
+ gcc_checking_assert (m_dfs_order[b2->index] == 0);
+ bitmap_set_bit (m_fake_exit_edge, b2->index);
+ m_dfs_order[b2->index] = m_dfsnum;
+ m_dfs_to_bb[m_dfsnum] = b2;
+ m_dfs_parent[m_dfsnum] =
+ m_dfs_order[last_basic_block_for_fn (m_fn)];
+ m_dfsnum++;
+ calc_dfs_tree_nonrec (b2, reverse);
+ gcc_checking_assert (m_dfs_order[b->index]);
}
}
}
- di->nodes = di->dfsnum - 1;
+ m_nodes = m_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_for_fn (cfun) - 1);
+ gcc_assert (m_nodes == (unsigned int) n_basic_blocks_for_fn (m_fn) - 1);
}
/* Compress the path from V to the root of its set and update path_min at the
@@ -403,19 +418,19 @@ calc_dfs_tree (struct dom_info *di, bool reverse)
in and path_min[V] is the node with the smallest key[] value on the path
from V to that root. */
-static void
-compress (struct dom_info *di, TBB v)
+void
+dom_info::compress (TBB v)
{
/* Btw. It's not worth to unrecurse compress() as the depth is usually not
greater than 5 even for huge graphs (I've not seen call depth > 4).
Also performance wise compress() ranges _far_ behind eval(). */
- TBB parent = di->set_chain[v];
- if (di->set_chain[parent])
+ TBB parent = m_set_chain[v];
+ if (m_set_chain[parent])
{
- compress (di, parent);
- if (di->key[di->path_min[parent]] < di->key[di->path_min[v]])
- di->path_min[v] = di->path_min[parent];
- di->set_chain[v] = di->set_chain[parent];
+ compress (parent);
+ if (m_key[m_path_min[parent]] < m_key[m_path_min[v]])
+ m_path_min[v] = m_path_min[parent];
+ m_set_chain[v] = m_set_chain[parent];
}
}
@@ -423,28 +438,28 @@ compress (struct dom_info *di, TBB v)
changed since the last call). Returns the node with the smallest key[]
value on the path from V to the root. */
-static inline TBB
-eval (struct dom_info *di, TBB v)
+inline TBB
+dom_info::eval (TBB v)
{
/* The representative of the set V is in, also called root (as the set
representation is a tree). */
- TBB rep = di->set_chain[v];
+ TBB rep = m_set_chain[v];
/* V itself is the root. */
if (!rep)
- return di->path_min[v];
+ return m_path_min[v];
/* Compress only if necessary. */
- if (di->set_chain[rep])
+ if (m_set_chain[rep])
{
- compress (di, v);
- rep = di->set_chain[v];
+ compress (v);
+ rep = m_set_chain[v];
}
- if (di->key[di->path_min[rep]] >= di->key[di->path_min[v]])
- return di->path_min[v];
+ if (m_key[m_path_min[rep]] >= m_key[m_path_min[v]])
+ return m_path_min[v];
else
- return di->path_min[rep];
+ return m_path_min[rep];
}
/* This essentially merges the two sets of V and W, giving a single set with
@@ -452,72 +467,67 @@ eval (struct dom_info *di, TBB v)
balanced tree. Currently link(V,W) is only used with V being the parent
of W. */
-static void
-link_roots (struct dom_info *di, TBB v, TBB w)
+void
+dom_info::link_roots (TBB v, TBB w)
{
TBB s = w;
/* Rebalance the tree. */
- while (di->key[di->path_min[w]] < di->key[di->path_min[di->set_child[s]]])
+ while (m_key[m_path_min[w]] < m_key[m_path_min[m_set_child[s]]])
{
- if (di->set_size[s] + di->set_size[di->set_child[di->set_child[s]]]
- >= 2 * di->set_size[di->set_child[s]])
+ if (m_set_size[s] + m_set_size[m_set_child[m_set_child[s]]]
+ >= 2 * m_set_size[m_set_child[s]])
{
- di->set_chain[di->set_child[s]] = s;
- di->set_child[s] = di->set_child[di->set_child[s]];
+ m_set_chain[m_set_child[s]] = s;
+ m_set_child[s] = m_set_child[m_set_child[s]];
}
else
{
- di->set_size[di->set_child[s]] = di->set_size[s];
- s = di->set_chain[s] = di->set_child[s];
+ m_set_size[m_set_child[s]] = m_set_size[s];
+ s = m_set_chain[s] = m_set_child[s];
}
}
- 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])
- std::swap (di->set_child[v], s);
+ m_path_min[s] = m_path_min[w];
+ m_set_size[v] += m_set_size[w];
+ if (m_set_size[v] < 2 * m_set_size[w])
+ std::swap (m_set_child[v], s);
/* Merge all subtrees. */
while (s)
{
- di->set_chain[s] = v;
- s = di->set_child[s];
+ m_set_chain[s] = v;
+ s = m_set_child[s];
}
}
/* This calculates the immediate dominators (or post-dominators if REVERSE is
true). DI is our working structure and should hold the DFS forest.
- On return the immediate dominator to node V is in di->dom[V]. */
+ On return the immediate dominator to node V is in m_dom[V]. */
-static void
-calc_idoms (struct dom_info *di, bool reverse)
+void
+dom_info::calc_idoms (bool reverse)
{
- TBB v, w, k, par;
- basic_block en_block;
- edge_iterator ei, einext;
-
- if (reverse)
- en_block = EXIT_BLOCK_PTR_FOR_FN (cfun);
- else
- en_block = ENTRY_BLOCK_PTR_FOR_FN (cfun);
+ const basic_block en_block = reverse ? EXIT_BLOCK_PTR_FOR_FN (m_fn)
+ : ENTRY_BLOCK_PTR_FOR_FN (m_fn);
/* Go backwards in DFS order, to first look at the leafs. */
- v = di->nodes;
- while (v > 1)
+ for (TBB v = m_nodes; v > 1; v--)
{
- basic_block bb = di->dfs_to_bb[v];
+ basic_block bb = m_dfs_to_bb[v];
edge e;
- par = di->dfs_parent[v];
- k = v;
+ TBB par = m_dfs_parent[v];
+ TBB k = v;
- ei = (reverse) ? ei_start (bb->succs) : ei_start (bb->preds);
+ edge_iterator ei = (reverse) ? ei_start (bb->succs)
+ : ei_start (bb->preds);
+ edge_iterator einext;
if (reverse)
{
/* If this block has a fake edge to exit, process that first. */
- if (bitmap_bit_p (di->fake_exit_edge, bb->index))
+ if (bitmap_bit_p (m_fake_exit_edge, bb->index))
{
einext = ei;
einext.index = 0;
@@ -542,60 +552,57 @@ calc_idoms (struct dom_info *di, bool reverse)
if (b == en_block)
{
do_fake_exit_edge:
- k1 = di->dfs_order[last_basic_block_for_fn (cfun)];
+ k1 = m_dfs_order[last_basic_block_for_fn (m_fn)];
}
else
- k1 = di->dfs_order[b->index];
+ k1 = m_dfs_order[b->index];
/* Call eval() only if really needed. If k1 is above V in DFS tree,
then we know, that eval(k1) == k1 and key[k1] == k1. */
if (k1 > v)
- k1 = di->key[eval (di, k1)];
+ k1 = m_key[eval (k1)];
if (k1 < k)
k = k1;
ei = einext;
}
- di->key[v] = k;
- link_roots (di, par, v);
- di->next_bucket[v] = di->bucket[k];
- di->bucket[k] = v;
+ m_key[v] = k;
+ link_roots (par, v);
+ m_next_bucket[v] = m_bucket[k];
+ m_bucket[k] = v;
/* Transform semidominators into dominators. */
- for (w = di->bucket[par]; w; w = di->next_bucket[w])
+ for (TBB w = m_bucket[par]; w; w = m_next_bucket[w])
{
- k = eval (di, w);
- if (di->key[k] < di->key[w])
- di->dom[w] = k;
+ k = eval (w);
+ if (m_key[k] < m_key[w])
+ m_dom[w] = k;
else
- di->dom[w] = par;
+ m_dom[w] = par;
}
/* We don't need to cleanup next_bucket[]. */
- di->bucket[par] = 0;
- v--;
+ m_bucket[par] = 0;
}
/* Explicitly define the dominators. */
- di->dom[1] = 0;
- for (v = 2; v <= di->nodes; v++)
- if (di->dom[v] != di->key[v])
- di->dom[v] = di->dom[di->dom[v]];
+ m_dom[1] = 0;
+ for (TBB v = 2; v <= m_nodes; v++)
+ if (m_dom[v] != m_key[v])
+ m_dom[v] = m_dom[m_dom[v]];
}
/* Assign dfs numbers starting from NUM to NODE and its sons. */
static void
-assign_dfs_numbers (struct et_node *node, int *num)
+assign_dfs_numbers (et_node *node, int *num)
{
- struct et_node *son;
-
node->dfs_num_in = (*num)++;
if (node->son)
{
assign_dfs_numbers (node->son, num);
- for (son = node->son->right; son != node->son; son = son->right)
+ for (et_node *son = node->son->right; son != node->son; son = son->right)
assign_dfs_numbers (son, num);
}
@@ -606,7 +613,7 @@ assign_dfs_numbers (struct et_node *node, int *num)
static dominator tree. */
static void
-compute_dom_fast_query (enum cdi_direction dir)
+compute_dom_fast_query (cdi_direction dir)
{
int num = 0;
basic_block bb;
@@ -630,52 +637,46 @@ compute_dom_fast_query (enum cdi_direction dir)
we want to compute dominators or postdominators. */
void
-calculate_dominance_info (enum cdi_direction dir)
+calculate_dominance_info (cdi_direction dir)
{
- 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_index] == DOM_OK)
{
-#if ENABLE_CHECKING
- verify_dominators (dir);
-#endif
+ if (ENABLE_CHECKING)
+ verify_dominators (dir);
return;
}
timevar_push (TV_DOMINANCE);
- if (!dom_info_available_p (dir))
+ if (!dom_info_available_p (cfun, dir))
{
gcc_assert (!n_bbs_in_dom_tree[dir_index]);
+ basic_block 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_for_fn (cfun);
- init_dom_info (&di, dir);
- calc_dfs_tree (&di, reverse);
- calc_idoms (&di, reverse);
+ dom_info di (cfun, dir);
+ di.calc_dfs_tree (reverse);
+ di.calc_idoms (reverse);
FOR_EACH_BB_FN (b, cfun)
{
- TBB d = di.dom[di.dfs_order[b->index]];
-
- if (di.dfs_to_bb[d])
- et_set_father (b->dom[dir_index], di.dfs_to_bb[d]->dom[dir_index]);
+ if (basic_block d = di.get_idom (b))
+ et_set_father (b->dom[dir_index], d->dom[dir_index]);
}
- free_dom_info (&di);
dom_computed[dir_index] = DOM_NO_FAST_QUERY;
}
else
{
-#if ENABLE_CHECKING
- verify_dominators (dir);
-#endif
+ if (ENABLE_CHECKING)
+ verify_dominators (dir);
}
compute_dom_fast_query (dir);
@@ -685,14 +686,14 @@ calculate_dominance_info (enum cdi_direction dir)
/* Free dominance information for direction DIR. */
void
-free_dominance_info (function *fn, enum cdi_direction dir)
+free_dominance_info (function *fn, cdi_direction dir)
{
- basic_block bb;
unsigned int dir_index = dom_convert_dir_to_idx (dir);
if (!dom_info_available_p (fn, dir))
return;
+ basic_block bb;
FOR_ALL_BB_FN (bb, fn)
{
et_free_tree_force (bb->dom[dir_index]);
@@ -706,17 +707,17 @@ free_dominance_info (function *fn, enum cdi_direction dir)
}
void
-free_dominance_info (enum cdi_direction dir)
+free_dominance_info (cdi_direction dir)
{
free_dominance_info (cfun, dir);
}
/* Return the immediate dominator of basic block BB. */
basic_block
-get_immediate_dominator (enum cdi_direction dir, basic_block bb)
+get_immediate_dominator (cdi_direction dir, basic_block bb)
{
unsigned int dir_index = dom_convert_dir_to_idx (dir);
- struct et_node *node = bb->dom[dir_index];
+ et_node *node = bb->dom[dir_index];
gcc_checking_assert (dom_computed[dir_index]);
@@ -729,11 +730,11 @@ get_immediate_dominator (enum cdi_direction dir, basic_block bb)
/* Set the immediate dominator of the block possibly removing
existing edge. NULL can be used to remove any edge. */
void
-set_immediate_dominator (enum cdi_direction dir, basic_block bb,
+set_immediate_dominator (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];
+ et_node *node = bb->dom[dir_index];
gcc_checking_assert (dom_computed[dir_index]);
@@ -753,11 +754,11 @@ set_immediate_dominator (enum cdi_direction dir, basic_block bb,
/* Returns the list of basic blocks immediately dominated by BB, in the
direction DIR. */
-vec<basic_block>
-get_dominated_by (enum cdi_direction dir, basic_block bb)
+vec<basic_block>
+get_dominated_by (cdi_direction dir, basic_block bb)
{
unsigned int dir_index = dom_convert_dir_to_idx (dir);
- struct et_node *node = bb->dom[dir_index], *son = node->son, *ason;
+ et_node *node = bb->dom[dir_index], *son = node->son;
vec<basic_block> bbs = vNULL;
gcc_checking_assert (dom_computed[dir_index]);
@@ -766,7 +767,7 @@ get_dominated_by (enum cdi_direction dir, basic_block bb)
return vNULL;
bbs.safe_push ((basic_block) son->data);
- for (ason = son->right; ason != son; ason = ason->right)
+ for (et_node *ason = son->right; ason != son; ason = ason->right)
bbs.safe_push ((basic_block) ason->data);
return bbs;
@@ -775,24 +776,21 @@ get_dominated_by (enum cdi_direction dir, basic_block bb)
/* 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>
-get_dominated_by_region (enum cdi_direction dir, basic_block *region,
+vec<basic_block>
+get_dominated_by_region (cdi_direction dir, basic_block *region,
unsigned n_region)
{
- unsigned i;
- basic_block dom;
vec<basic_block> doms = vNULL;
- for (i = 0; i < n_region; i++)
+ for (unsigned 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]);
+ for (unsigned i = 0; i < n_region; i++)
+ for (basic_block dom = first_dom_son (dir, region[i]);
dom;
dom = next_dom_son (dir, dom))
if (!(dom->flags & BB_DUPLICATED))
doms.safe_push (dom);
- for (i = 0; i < n_region; i++)
+ for (unsigned i = 0; i < n_region; i++)
region[i]->flags &= ~BB_DUPLICATED;
return doms;
@@ -803,31 +801,25 @@ get_dominated_by_region (enum cdi_direction dir, basic_block *region,
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>
+get_dominated_to_depth (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 (); */
+ unsigned next_level_start = 1; /* = bbs.length (); */
- do
+ for (unsigned i = 0; i < next_level_start; i++)
{
- basic_block son;
-
- bb = bbs[i++];
- for (son = first_dom_son (dir, bb);
+ basic_block level_start_bb = bbs[i];
+ for (basic_block son = first_dom_son (dir, level_start_bb);
son;
son = next_dom_son (dir, son))
bbs.safe_push (son);
- if (i == next_level_start && --depth)
+ if (i + 1 == next_level_start && --depth)
next_level_start = bbs.length ();
}
- while (i < next_level_start);
return bbs;
}
@@ -835,32 +827,28 @@ get_dominated_to_depth (enum cdi_direction dir, basic_block bb, int depth)
/* 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)
+vec<basic_block>
+get_all_dominated_blocks (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,
+redirect_immediate_dominators (cdi_direction dir, basic_block bb,
basic_block to)
{
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];
+ et_node *bb_node = bb->dom[dir_index],
+ *to_node = to->dom[dir_index];
gcc_checking_assert (dom_computed[dir_index]);
if (!bb_node->son)
return;
- while (bb_node->son)
+ while (et_node *son = bb_node->son)
{
- son = bb_node->son;
-
et_split (son);
et_set_father (son, to_node);
}
@@ -871,7 +859,7 @@ redirect_immediate_dominators (enum cdi_direction dir, basic_block bb,
/* 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)
+nearest_common_dominator (cdi_direction dir, basic_block bb1, basic_block bb2)
{
unsigned int dir_index = dom_convert_dir_to_idx (dir);
@@ -890,14 +878,13 @@ nearest_common_dominator (enum cdi_direction dir, basic_block bb1, basic_block b
using dominance direction DIR. */
basic_block
-nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
+nearest_common_dominator_for_set (cdi_direction dir, bitmap blocks)
{
- unsigned i, first;
+ unsigned i;
bitmap_iterator bi;
- basic_block dom;
- first = bitmap_first_set_bit (blocks);
- dom = BASIC_BLOCK_FOR_FN (cfun, first);
+ unsigned first = bitmap_first_set_bit (blocks);
+ basic_block dom = BASIC_BLOCK_FOR_FN (cfun, first);
EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi)
if (dom != BASIC_BLOCK_FOR_FN (cfun, i))
dom = nearest_common_dominator (dir, dom, BASIC_BLOCK_FOR_FN (cfun, i));
@@ -982,10 +969,10 @@ nearest_common_dominator_for_set (enum cdi_direction dir, bitmap blocks)
/* 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)
+dominated_by_p (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];
+ et_node *n1 = bb1->dom[dir_index], *n2 = bb2->dom[dir_index];
gcc_checking_assert (dom_computed[dir_index]);
@@ -999,10 +986,10 @@ dominated_by_p (enum cdi_direction dir, const_basic_block bb1, const_basic_block
/* 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)
+bb_dom_dfs_in (cdi_direction dir, basic_block bb)
{
unsigned int dir_index = dom_convert_dir_to_idx (dir);
- struct et_node *n = bb->dom[dir_index];
+ et_node *n = bb->dom[dir_index];
gcc_checking_assert (dom_computed[dir_index] == DOM_OK);
return n->dfs_num_in;
@@ -1011,10 +998,10 @@ bb_dom_dfs_in (enum cdi_direction dir, basic_block bb)
/* 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)
+bb_dom_dfs_out (cdi_direction dir, basic_block bb)
{
unsigned int dir_index = dom_convert_dir_to_idx (dir);
- struct et_node *n = bb->dom[dir_index];
+ et_node *n = bb->dom[dir_index];
gcc_checking_assert (dom_computed[dir_index] == DOM_OK);
return n->dfs_num_out;
@@ -1022,38 +1009,36 @@ bb_dom_dfs_out (enum cdi_direction dir, basic_block bb)
/* Verify invariants of dominator structure. */
DEBUG_FUNCTION void
-verify_dominators (enum cdi_direction dir)
+verify_dominators (cdi_direction dir)
{
- int err = 0;
- basic_block bb, imm_bb, imm_bb_correct;
- struct dom_info di;
bool reverse = (dir == CDI_POST_DOMINATORS) ? true : false;
gcc_assert (dom_info_available_p (dir));
- init_dom_info (&di, dir);
- calc_dfs_tree (&di, reverse);
- calc_idoms (&di, reverse);
+ dom_info di (cfun, dir);
+ di.calc_dfs_tree (reverse);
+ di.calc_idoms (reverse);
+ bool err = false;
+ basic_block bb;
FOR_EACH_BB_FN (bb, cfun)
{
- imm_bb = get_immediate_dominator (dir, bb);
+ basic_block imm_bb = get_immediate_dominator (dir, bb);
if (!imm_bb)
{
error ("dominator of %d status unknown", bb->index);
- err = 1;
+ err = true;
}
- imm_bb_correct = di.dfs_to_bb[di.dom[di.dfs_order[bb->index]]];
+ basic_block imm_bb_correct = di.get_idom (bb);
if (imm_bb != imm_bb_correct)
{
error ("dominator of %d should be %d, not %d",
bb->index, imm_bb_correct->index, imm_bb->index);
- err = 1;
+ err = true;
}
}
- free_dom_info (&di);
gcc_assert (!err);
}
@@ -1063,7 +1048,7 @@ verify_dominators (enum cdi_direction dir)
reaches a fixed point. */
basic_block
-recompute_dominator (enum cdi_direction dir, basic_block bb)
+recompute_dominator (cdi_direction dir, basic_block bb)
{
unsigned int dir_index = dom_convert_dir_to_idx (dir);
basic_block dom_bb = NULL;
@@ -1100,8 +1085,7 @@ recompute_dominator (enum cdi_direction dir, basic_block bb)
from BBS. */
static void
-prune_bbs_to_update_dominators (vec<basic_block> bbs,
- bool conservative)
+prune_bbs_to_update_dominators (vec<basic_block> bbs, bool conservative)
{
unsigned i;
bool single;
@@ -1160,7 +1144,7 @@ succeed:
BB. */
static basic_block
-root_of_dom_tree (enum cdi_direction dir, basic_block bb)
+root_of_dom_tree (cdi_direction dir, basic_block bb)
{
return (basic_block) et_root (bb->dom[dom_convert_dir_to_idx (dir)])->data;
}
@@ -1171,54 +1155,50 @@ root_of_dom_tree (enum cdi_direction dir, basic_block bb)
blocks. */
static void
-determine_dominators_for_sons (struct graph *g, vec<basic_block> bbs,
- int y, int *son, int *brother)
+determine_dominators_for_sons (graph *g, vec<basic_block> bbs, int y, int *son,
+ int *brother)
{
- bitmap gprime;
- int i, a, nc;
- vec<int> *sccs;
- basic_block bb, dom, ybb;
- unsigned si;
- edge e;
- edge_iterator ei;
-
if (son[y] == -1)
return;
- if (y == (int) bbs.length ())
- ybb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
- else
- ybb = bbs[y];
if (brother[son[y]] == -1)
{
/* Handle the common case Y has just one son specially. */
- bb = bbs[son[y]];
+ basic_block bb = bbs[son[y]];
set_immediate_dominator (CDI_DOMINATORS, bb,
recompute_dominator (CDI_DOMINATORS, bb));
identify_vertices (g, y, son[y]);
return;
}
- gprime = BITMAP_ALLOC (NULL);
- for (a = son[y]; a != -1; a = brother[a])
+ bitmap gprime = BITMAP_ALLOC (NULL);
+ for (int a = son[y]; a != -1; a = brother[a])
bitmap_set_bit (gprime, a);
- nc = graphds_scc (g, gprime);
+ int nc = graphds_scc (g, gprime);
BITMAP_FREE (gprime);
- /* ??? 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<int> *sccs = XCNEWVEC (vec<int>, nc);
+ for (int a = son[y]; a != -1; a = brother[a])
sccs[g->vertices[a].component].safe_push (a);
- for (i = nc - 1; i >= 0; i--)
+ basic_block ybb;
+ if (y == (int) bbs.length ())
+ ybb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
+ else
+ ybb = bbs[y];
+
+ for (int i = nc - 1; i >= 0; i--)
{
- dom = NULL;
+ basic_block dom = NULL;
+
+ int a;
+ unsigned si;
FOR_EACH_VEC_ELT (sccs[i], si, a)
{
- bb = bbs[a];
+ basic_block bb = bbs[a];
+ edge e;
+ edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->preds)
{
if (root_of_dom_tree (CDI_DOMINATORS, e->src) != ybb)
@@ -1231,16 +1211,16 @@ determine_dominators_for_sons (struct graph *g, vec<basic_block> bbs,
gcc_assert (dom != NULL);
FOR_EACH_VEC_ELT (sccs[i], si, a)
{
- bb = bbs[a];
+ basic_block bb = bbs[a];
set_immediate_dominator (CDI_DOMINATORS, bb, dom);
}
}
- for (i = 0; i < nc; i++)
+ for (int i = 0; i < nc; i++)
sccs[i].release ();
free (sccs);
- for (a = son[y]; a != -1; a = brother[a])
+ for (int a = son[y]; a != -1; a = brother[a])
identify_vertices (g, y, a);
}
@@ -1252,17 +1232,9 @@ determine_dominators_for_sons (struct graph *g, vec<basic_block> bbs,
a block of BBS in the current dominance tree dominate it. */
void
-iterate_fix_dominators (enum cdi_direction dir, vec<basic_block> bbs,
+iterate_fix_dominators (cdi_direction dir, vec<basic_block> bbs,
bool conservative)
{
- unsigned i;
- basic_block bb, dom;
- struct graph *g;
- int n, y;
- size_t dom_i;
- edge e;
- edge_iterator ei;
- int *parent, *son, *brother;
unsigned int dir_index = dom_convert_dir_to_idx (dir);
/* We only support updating dominators. There are some problems with
@@ -1330,19 +1302,21 @@ iterate_fix_dominators (enum cdi_direction dir, vec<basic_block> bbs,
conservatively correct, setting the dominators using the
heuristics in prune_bbs_to_update_dominators could
create cycles in the dominance "tree", and cause ICE. */
+ unsigned i;
+ basic_block bb;
FOR_EACH_VEC_ELT (bbs, i, bb)
set_immediate_dominator (CDI_DOMINATORS, bb, NULL);
}
prune_bbs_to_update_dominators (bbs, conservative);
- n = bbs.length ();
+ int n = bbs.length ();
if (n == 0)
return;
if (n == 1)
{
- bb = bbs[0];
+ basic_block bb = bbs[0];
set_immediate_dominator (CDI_DOMINATORS, bb,
recompute_dominator (CDI_DOMINATORS, bb));
return;
@@ -1350,6 +1324,8 @@ iterate_fix_dominators (enum cdi_direction dir, vec<basic_block> bbs,
/* Construct the graph G. */
hash_map<basic_block, int> map (251);
+ basic_block bb;
+ unsigned i;
FOR_EACH_VEC_ELT (bbs, i, bb)
{
/* If the dominance tree is conservatively correct, split it now. */
@@ -1359,18 +1335,20 @@ iterate_fix_dominators (enum cdi_direction dir, vec<basic_block> bbs,
}
map.put (ENTRY_BLOCK_PTR_FOR_FN (cfun), n);
- g = new_graph (n + 1);
- for (y = 0; y < g->n_vertices; y++)
+ graph *g = new_graph (n + 1);
+ for (int y = 0; y < g->n_vertices; y++)
g->vertices[y].data = BITMAP_ALLOC (NULL);
FOR_EACH_VEC_ELT (bbs, i, bb)
{
+ edge e;
+ edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->preds)
{
- dom = root_of_dom_tree (CDI_DOMINATORS, e->src);
+ basic_block dom = root_of_dom_tree (CDI_DOMINATORS, e->src);
if (dom == bb)
continue;
- dom_i = *map.get (dom);
+ int dom_i = *map.get (dom);
/* Do not include parallel edges to G. */
if (!bitmap_set_bit ((bitmap) g->vertices[dom_i].data, i))
@@ -1379,16 +1357,17 @@ iterate_fix_dominators (enum cdi_direction dir, vec<basic_block> bbs,
add_edge (g, dom_i, i);
}
}
- for (y = 0; y < g->n_vertices; y++)
+ for (int y = 0; y < g->n_vertices; y++)
BITMAP_FREE (g->vertices[y].data);
/* Find the dominator tree of G. */
- son = XNEWVEC (int, n + 1);
- brother = XNEWVEC (int, n + 1);
- parent = XNEWVEC (int, n + 1);
+ int *son = new int[n + 1],
+ *brother = new int[n + 1],
+ *parent = new int[n + 1];
graphds_domtree (g, n, parent, son, brother);
/* Finally, traverse the tree and find the immediate dominators. */
+ int y;
for (y = n; son[y] != -1; y = son[y])
continue;
while (y != -1)
@@ -1405,15 +1384,15 @@ iterate_fix_dominators (enum cdi_direction dir, vec<basic_block> bbs,
y = parent[y];
}
- free (son);
- free (brother);
- free (parent);
+ delete[] son;
+ delete[] brother;
+ delete[] parent;
free_graph (g);
}
void
-add_to_dominance_info (enum cdi_direction dir, basic_block bb)
+add_to_dominance_info (cdi_direction dir, basic_block bb)
{
unsigned int dir_index = dom_convert_dir_to_idx (dir);
@@ -1428,7 +1407,7 @@ add_to_dominance_info (enum cdi_direction dir, basic_block bb)
}
void
-delete_from_dominance_info (enum cdi_direction dir, basic_block bb)
+delete_from_dominance_info (cdi_direction dir, basic_block bb)
{
unsigned int dir_index = dom_convert_dir_to_idx (dir);
@@ -1446,10 +1425,10 @@ delete_from_dominance_info (enum cdi_direction dir, basic_block bb)
as determined by DIR. */
basic_block
-first_dom_son (enum cdi_direction dir, basic_block bb)
+first_dom_son (cdi_direction dir, basic_block bb)
{
unsigned int dir_index = dom_convert_dir_to_idx (dir);
- struct et_node *son = bb->dom[dir_index]->son;
+ et_node *son = bb->dom[dir_index]->son;
return (basic_block) (son ? son->data : NULL);
}
@@ -1458,18 +1437,18 @@ first_dom_son (enum cdi_direction dir, basic_block bb)
tree as determined by DIR, or NULL if it was the last one. */
basic_block
-next_dom_son (enum cdi_direction dir, basic_block bb)
+next_dom_son (cdi_direction dir, basic_block bb)
{
unsigned int dir_index = dom_convert_dir_to_idx (dir);
- struct et_node *next = bb->dom[dir_index]->right;
+ et_node *next = bb->dom[dir_index]->right;
return (basic_block) (next->father->son == next ? NULL : next->data);
}
/* Return dominance availability for dominance info DIR. */
-enum dom_state
-dom_info_state (function *fn, enum cdi_direction dir)
+dom_state
+dom_info_state (function *fn, cdi_direction dir)
{
if (!fn->cfg)
return DOM_NONE;
@@ -1478,8 +1457,8 @@ dom_info_state (function *fn, enum cdi_direction dir)
return fn->cfg->x_dom_computed[dir_index];
}
-enum dom_state
-dom_info_state (enum cdi_direction dir)
+dom_state
+dom_info_state (cdi_direction dir)
{
return dom_info_state (cfun, dir);
}
@@ -1487,7 +1466,7 @@ dom_info_state (enum cdi_direction dir)
/* 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)
+set_dom_info_availability (cdi_direction dir, dom_state new_state)
{
unsigned int dir_index = dom_convert_dir_to_idx (dir);
@@ -1497,23 +1476,23 @@ set_dom_info_availability (enum cdi_direction dir, enum dom_state new_state)
/* Returns true if dominance information for direction DIR is available. */
bool
-dom_info_available_p (function *fn, enum cdi_direction dir)
+dom_info_available_p (function *fn, cdi_direction dir)
{
return dom_info_state (fn, dir) != DOM_NONE;
}
bool
-dom_info_available_p (enum cdi_direction dir)
+dom_info_available_p (cdi_direction dir)
{
return dom_info_available_p (cfun, dir);
}
DEBUG_FUNCTION void
-debug_dominance_info (enum cdi_direction dir)
+debug_dominance_info (cdi_direction dir)
{
- basic_block bb, bb2;
+ basic_block bb;
FOR_EACH_BB_FN (bb, cfun)
- if ((bb2 = get_immediate_dominator (dir, bb)))
+ if (basic_block bb2 = get_immediate_dominator (dir, bb))
fprintf (stderr, "%i %i\n", bb->index, bb2->index);
}
@@ -1522,19 +1501,16 @@ debug_dominance_info (enum cdi_direction dir)
the first line of the output is not indented. */
static void
-debug_dominance_tree_1 (enum cdi_direction dir, basic_block root,
- unsigned indent, bool indent_first)
+debug_dominance_tree_1 (cdi_direction dir, basic_block root, unsigned indent,
+ bool indent_first)
{
- basic_block son;
- unsigned i;
- bool first = true;
-
if (indent_first)
- for (i = 0; i < indent; i++)
+ for (unsigned i = 0; i < indent; i++)
fprintf (stderr, "\t");
fprintf (stderr, "%d\t", root->index);
- for (son = first_dom_son (dir, root);
+ bool first = true;
+ for (basic_block son = first_dom_son (dir, root);
son;
son = next_dom_son (dir, son))
{
@@ -1550,7 +1526,7 @@ debug_dominance_tree_1 (enum cdi_direction dir, basic_block root,
rooted in ROOT. */
DEBUG_FUNCTION void
-debug_dominance_tree (enum cdi_direction dir, basic_block root)
+debug_dominance_tree (cdi_direction dir, basic_block root)
{
debug_dominance_tree_1 (dir, root, 0, false);
}
@@ -35,44 +35,38 @@ enum dom_state
DOM_OK /* Everything is ok. */
};
-extern void calculate_dominance_info (enum cdi_direction);
-extern void free_dominance_info (function *, enum cdi_direction);
-extern void free_dominance_info (enum cdi_direction);
-extern basic_block get_immediate_dominator (enum cdi_direction, basic_block);
-extern void set_immediate_dominator (enum cdi_direction, basic_block,
+extern void calculate_dominance_info (cdi_direction);
+extern void free_dominance_info (function *, cdi_direction);
+extern void free_dominance_info (cdi_direction);
+extern basic_block get_immediate_dominator (cdi_direction, basic_block);
+extern void set_immediate_dominator (cdi_direction, basic_block,
basic_block);
-extern vec<basic_block> get_dominated_by (enum cdi_direction, basic_block);
-extern vec<basic_block> get_dominated_by_region (enum cdi_direction,
- basic_block *,
- unsigned);
-extern vec<basic_block> get_dominated_to_depth (enum cdi_direction,
- basic_block, int);
-extern vec<basic_block> get_all_dominated_blocks (enum cdi_direction,
- basic_block);
-extern void redirect_immediate_dominators (enum cdi_direction, basic_block,
+extern vec<basic_block> get_dominated_by (cdi_direction, basic_block);
+extern vec<basic_block> get_dominated_by_region (cdi_direction, basic_block *,
+ unsigned);
+extern vec<basic_block> get_dominated_to_depth (cdi_direction, basic_block,
+ int);
+extern vec<basic_block> get_all_dominated_blocks (cdi_direction, basic_block);
+extern void redirect_immediate_dominators (cdi_direction, basic_block,
basic_block);
-extern basic_block nearest_common_dominator (enum cdi_direction,
+extern basic_block nearest_common_dominator (cdi_direction,
basic_block, basic_block);
-extern basic_block nearest_common_dominator_for_set (enum cdi_direction,
- bitmap);
-extern bool dominated_by_p (enum cdi_direction, const_basic_block,
+extern basic_block nearest_common_dominator_for_set (cdi_direction, bitmap);
+extern bool dominated_by_p (cdi_direction, const_basic_block,
const_basic_block);
-unsigned bb_dom_dfs_in (enum cdi_direction, basic_block);
-unsigned bb_dom_dfs_out (enum cdi_direction, basic_block);
-extern void verify_dominators (enum cdi_direction);
-basic_block recompute_dominator (enum cdi_direction, basic_block);
-extern void iterate_fix_dominators (enum cdi_direction,
- vec<basic_block> , bool);
-extern void add_to_dominance_info (enum cdi_direction, basic_block);
-extern void delete_from_dominance_info (enum cdi_direction, basic_block);
-extern basic_block first_dom_son (enum cdi_direction, basic_block);
-extern basic_block next_dom_son (enum cdi_direction, basic_block);
-extern enum dom_state dom_info_state (function *, enum cdi_direction);
-extern enum dom_state dom_info_state (enum cdi_direction);
-extern void set_dom_info_availability (enum cdi_direction, enum dom_state);
-extern bool dom_info_available_p (function *, enum cdi_direction);
-extern bool dom_info_available_p (enum cdi_direction);
-
-
+unsigned bb_dom_dfs_in (cdi_direction, basic_block);
+unsigned bb_dom_dfs_out (cdi_direction, basic_block);
+extern void verify_dominators (cdi_direction);
+basic_block recompute_dominator (cdi_direction, basic_block);
+extern void iterate_fix_dominators (cdi_direction, vec<basic_block> , bool);
+extern void add_to_dominance_info (cdi_direction, basic_block);
+extern void delete_from_dominance_info (cdi_direction, basic_block);
+extern basic_block first_dom_son (cdi_direction, basic_block);
+extern basic_block next_dom_son (cdi_direction, basic_block);
+extern dom_state dom_info_state (function *, cdi_direction);
+extern dom_state dom_info_state (cdi_direction);
+extern void set_dom_info_availability (cdi_direction, dom_state);
+extern bool dom_info_available_p (function *, cdi_direction);
+extern bool dom_info_available_p (cdi_direction);
#endif /* GCC_DOMINANCE_H */
Hi all. These two patches are refactoring of dominator-related code. The comment in dominance.c says: "We work in a poor-mans object oriented fashion, and carry an instance of this structure through all our 'methods'". So, the first patch converts the mentioned structure (dom_info) into a class with proper encapsulation. It also adds a new member - m_fn (the function currently being compiled) to this structure and replaces some uses of cfun with m_fn. It also contains some fixes, related to current coding standards: move variable declarations to place of first use, replace elaborated type specifiers (i.e. "struct/enum foo") by simple ones (i.e., just "foo") in function prototypes. Bootstrapped and regtested on x86_64-linux. Tested build of config-list.mk. gcc/ChangeLog: 2015-08-14 Mikhail Maltsev <maltsevm@gmail.com> * (ENABLE_CHECKING): Define as 0 by default. dominance.c (new_zero_array): Define. (dom_info): Define as class instead of struct. (dom_info::dom_info, ~dom_info): Define. Use new/delete for memory allocations/deallocations. Pass function as parameter (instead of using cfun). (dom_info::get_idom): Define accessor method. (dom_info::calc_dfs_tree_nonrec, calc_dfs_tree, compress, eval, link_roots, calc_idoms): Redefine as class members. Use m_fn instead of cfun. (init_dom_info, free_dom_info): Remove (use dom_info ctor/dtor). (dom_convert_dir_to_idx): Fix prototype. (assign_dfs_numbers): Move variable declarations to their first uses. (calculate_dominance_info): Remove conditional compilation, move variables. (free_dominance_info, get_immediate_dominator, set_immediate_dominator, get_dominated_b, get_dominated_by_region, get_dominated_to_depth, redirect_immediate_dominators, nearest_common_dominator_for_set, dominated_by_p, bb_dom_dfs_in, bb_dom_dfs_out, verify_dominators, determine_dominators_for_sons, iterate_fix_dominators, first_dom_son, next_dom_son, debug_dominance_info, debug_dominance_tree_1): Adjust to use class dom_info. Move variable declarations to the place of first use. Fix prototypes (remove struct/enum). * dominance.h: Fix prototypes (remove struct/enum).