/* Calculate (post)dominators in slightly super-linear time.
- Copyright (C) 2000 Free Software Foundation, Inc.
+ Copyright (C) 2000, 2003 Free Software Foundation, Inc.
Contributed by Michael Matz (matz@ifh.de).
This file is part of GCC.
#include "config.h"
#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
#include "rtl.h"
#include "hard-reg-set.h"
#include "basic-block.h"
-#include "error.h"
+#include "errors.h"
#include "et-forest.h"
struct dominance_info
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;
- /* If x is the DFS-index of a node which corresponds with an basic block,
+ /* 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. */
unsigned int nodes;
};
-static void init_dom_info PARAMS ((struct dom_info *));
-static void free_dom_info PARAMS ((struct dom_info *));
-static void calc_dfs_tree_nonrec PARAMS ((struct dom_info *,
- basic_block,
- enum cdi_direction));
-static void calc_dfs_tree PARAMS ((struct dom_info *,
- enum cdi_direction));
-static void compress PARAMS ((struct dom_info *, TBB));
-static TBB eval PARAMS ((struct dom_info *, TBB));
-static void link_roots PARAMS ((struct dom_info *, TBB, TBB));
-static void calc_idoms PARAMS ((struct dom_info *,
- enum cdi_direction));
-void debug_dominance_info PARAMS ((dominance_info));
+static void init_dom_info (struct dom_info *);
+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 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);
+void debug_dominance_info (dominance_info);
/* Helper macro for allocating and initializing an array,
for aesthetic reasons. */
{ \
unsigned int i = 1; /* Catch content == i. */ \
if (! (content)) \
- (var) = (type *) xcalloc ((num), sizeof (type)); \
+ (var) = xcalloc ((num), sizeof (type)); \
else \
{ \
- (var) = (type *) xmalloc ((num) * sizeof (type)); \
+ (var) = xmalloc ((num) * sizeof (type)); \
for (i = 0; i < num; i++) \
(var)[i] = (content); \
} \
while (0)
/* Allocate all needed memory in a pessimistic fashion (so we round up).
- This initialises the contents of DI, which already must be allocated. */
+ This initializes the contents of DI, which already must be allocated. */
static void
-init_dom_info (di)
- struct dom_info *di;
+init_dom_info (struct dom_info *di)
{
/* We need memory for n_basic_blocks nodes and the ENTRY_BLOCK or
EXIT_BLOCK. */
/* Free all allocated memory in DI, but not DI itself. */
static void
-free_dom_info (di)
- struct dom_info *di;
+free_dom_info (struct dom_info *di)
{
free (di->dfs_parent);
free (di->path_min);
assigned their dfs number and are linked together to form a tree. */
static void
-calc_dfs_tree_nonrec (di, bb, reverse)
- 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. */
/* Ending block. */
basic_block ex_block;
- stack = (edge *) xmalloc ((n_basic_blocks + 3) * sizeof (edge));
+ stack = xmalloc ((n_basic_blocks + 3) * sizeof (edge));
sp = 0;
/* Initialize our border blocks, and the first edge. */
because there may be nodes from which the EXIT_BLOCK is unreachable. */
static void
-calc_dfs_tree (di, reverse)
- struct dom_info *di;
- enum cdi_direction reverse;
+calc_dfs_tree (struct dom_info *di, enum cdi_direction reverse)
{
/* The first block is the ENTRY_BLOCK (or EXIT_BLOCK if REVERSE). */
basic_block begin = reverse ? EXIT_BLOCK_PTR : ENTRY_BLOCK_PTR;
from V to that root. */
static void
-compress (di, v)
- struct dom_info *di;
- TBB v;
+compress (struct dom_info *di, 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).
value on the path from V to the root. */
static inline TBB
-eval (di, v)
- struct dom_info *di;
- TBB v;
+eval (struct dom_info *di, TBB v)
{
/* The representant of the set V is in, also called root (as the set
representation is a tree). */
of W. */
static void
-link_roots (di, v, w)
- struct dom_info *di;
- TBB v, w;
+link_roots (struct dom_info *di, TBB v, TBB w)
{
TBB s = w;
On return the immediate dominator to node V is in di->dom[V]. */
static void
-calc_idoms (di, reverse)
- struct dom_info *di;
- enum cdi_direction reverse;
+calc_idoms (struct dom_info *di, enum cdi_direction reverse)
{
TBB v, w, k, par;
basic_block en_block;
immediate resp. all dominators). */
dominance_info
-calculate_dominance_info (reverse)
- enum cdi_direction reverse;
+calculate_dominance_info (enum cdi_direction reverse)
{
struct dom_info di;
dominance_info info;
basic_block b;
- /* allocate structure for dominance information. */
+ /* Allocate structure for dominance information. */
info = xmalloc (sizeof (struct dominance_info));
info->forest = et_forest_create ();
VARRAY_GENERIC_PTR_INIT (info->varray, last_basic_block + 3, "dominance info");
/* Free dominance information. */
void
-free_dominance_info (info)
- dominance_info info;
+free_dominance_info (dominance_info info)
{
basic_block bb;
/* Return the immediate dominator of basic block BB. */
basic_block
-get_immediate_dominator (dom, bb)
- dominance_info dom;
- basic_block bb;
+get_immediate_dominator (dominance_info dom, basic_block bb)
{
return et_forest_node_value (dom->forest,
et_forest_parent (dom->forest,
/* Set the immediate dominator of the block possibly removing
existing edge. NULL can be used to remove any edge. */
inline void
-set_immediate_dominator (dom, bb, dominated_by)
- dominance_info dom;
- basic_block bb, dominated_by;
+set_immediate_dominator (dominance_info dom, basic_block bb, basic_block dominated_by)
{
void *aux_bb_node;
et_forest_node_t bb_node = BB_NODE (dom, bb);
/* Store all basic blocks dominated by BB into BBS and return their number. */
int
-get_dominated_by (dom, bb, bbs)
- dominance_info dom;
- basic_block bb;
- basic_block **bbs;
+get_dominated_by (dominance_info dom, basic_block bb, basic_block **bbs)
{
int n, i;
/* Redirect all edges pointing to BB to TO. */
void
-redirect_immediate_dominators (dom, bb, to)
- dominance_info dom;
- basic_block bb;
- basic_block to;
+redirect_immediate_dominators (dominance_info dom, basic_block bb, basic_block to)
{
et_forest_node_t *bbs = xmalloc (n_basic_blocks * sizeof (basic_block));
et_forest_node_t node = BB_NODE (dom, bb);
/* Find first basic block in the tree dominating both BB1 and BB2. */
basic_block
-nearest_common_dominator (dom, bb1, bb2)
- dominance_info dom;
- basic_block bb1;
- basic_block bb2;
+nearest_common_dominator (dominance_info dom, basic_block bb1, basic_block bb2)
{
if (!bb1)
return bb2;
/* Return TRUE in case BB1 is dominated by BB2. */
bool
-dominated_by_p (dom, bb1, bb2)
- dominance_info dom;
- basic_block bb1;
- basic_block bb2;
+dominated_by_p (dominance_info dom, basic_block bb1, basic_block bb2)
{
return nearest_common_dominator (dom, bb1, bb2) == bb2;
}
/* Verify invariants of dominator structure. */
void
-verify_dominators (dom)
- dominance_info dom;
+verify_dominators (dominance_info dom)
{
int err = 0;
basic_block bb;
/* Recount dominator of BB. */
basic_block
-recount_dominator (dom, bb)
- dominance_info dom;
- basic_block bb;
+recount_dominator (dominance_info dom, basic_block bb)
{
basic_block dom_bb = NULL;
edge e;
/* Iteratively recount dominators of BBS. The change is supposed to be local
and not to grow further. */
void
-iterate_fix_dominators (dom, bbs, n)
- dominance_info dom;
- basic_block *bbs;
- int n;
+iterate_fix_dominators (dominance_info dom, basic_block *bbs, int n)
{
int i, changed = 1;
basic_block old_dom, new_dom;
}
void
-add_to_dominance_info (dom, bb)
- dominance_info dom;
- basic_block bb;
+add_to_dominance_info (dominance_info dom, basic_block bb)
{
VARRAY_GROW (dom->varray, last_basic_block + 3);
#ifdef ENABLE_CHECKING
}
void
-delete_from_dominance_info (dom, bb)
- dominance_info dom;
- basic_block bb;
+delete_from_dominance_info (dominance_info dom, basic_block bb)
{
et_forest_remove_node (dom->forest, BB_NODE (dom, bb));
SET_BB_NODE (dom, bb, NULL);
}
void
-debug_dominance_info (dom)
- dominance_info dom;
+debug_dominance_info (dominance_info dom)
{
basic_block bb, bb2;
FOR_EACH_BB (bb)
OSDN Git Service
