Gcc 3.4.2 20040728.

1 files changed, 250 insertions, 187 deletions

diff --git a/contrib/gcc/dominance.c b/contrib/gcc/dominance.c
index 1bba31f..d608391 100644
--- a/contrib/gcc/dominance.c
+++ b/contrib/gcc/dominance.c
@@ -1,5 +1,5 @@
 /* Calculate (post)dominators in slightly super-linear time.
-   Copyright (C) 2000 Free Software Foundation, Inc.
+   Copyright (C) 2000, 2003, 2004 Free Software Foundation, Inc.
    Contributed by Michael Matz (matz@ifh.de).
 
    This file is part of GCC.
@@ -35,22 +35,16 @@
 
 #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 "errors.h"
 #include "et-forest.h"
 
-struct dominance_info
-{
-  et_forest_t forest;
-  varray_type varray;
-};
-
-#define BB_NODE(info, bb) \
-  ((et_forest_node_t)VARRAY_GENERIC_PTR ((info)->varray, (bb)->index + 2))
-#define SET_BB_NODE(info, bb, node) \
-  (VARRAY_GENERIC_PTR ((info)->varray, (bb)->index + 2) = (node))
+/* Whether the dominators and the postdominators are available.  */
+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
@@ -113,19 +107,16 @@ struct dom_info
   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 (enum cdi_direction);
 
 /* Helper macro for allocating and initializing an array,
    for aesthetic reasons.  */
@@ -134,10 +125,10 @@ void debug_dominance_info		PARAMS ((dominance_info));
     {								\
       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);				\
 	}							\
@@ -148,8 +139,7 @@ void debug_dominance_info		PARAMS ((dominance_info));
    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.  */
@@ -178,8 +168,7 @@ init_dom_info (di)
 /* 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);
@@ -201,10 +190,7 @@ free_dom_info (di)
    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.  */
@@ -218,7 +204,7 @@ calc_dfs_tree_nonrec (di, bb, reverse)
   /* 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.  */
@@ -319,9 +305,7 @@ calc_dfs_tree_nonrec (di, bb, reverse)
    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;
@@ -362,9 +346,7 @@ calc_dfs_tree (di, reverse)
    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).
@@ -384,9 +366,7 @@ compress (di, v)
    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).  */
@@ -415,9 +395,7 @@ eval (di, v)
    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;
 
@@ -459,9 +437,7 @@ link_roots (di, v, 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;
@@ -542,191 +518,250 @@ calc_idoms (di, reverse)
       di->dom[v] = di->dom[di->dom[v]];
 }
 
-/* The main entry point into this module.  IDOM is an integer array with room
-   for last_basic_block integers, DOMS is a preallocated sbitmap array having
-   room for last_basic_block^2 bits, and POST is true if the caller wants to
-   know post-dominators.
+/* Assign dfs numbers starting from NUM to NODE and its sons.  */
+
+static void
+assign_dfs_numbers (struct 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)
+      assign_dfs_numbers (son, num);
+    }
 
-   On return IDOM[i] will be the BB->index of the immediate (post) dominator
-   of basic block i, and DOMS[i] will have set bit j if basic block j is a
-   (post)dominator for block i.
+  node->dfs_num_out = (*num)++;
+}
 
-   Either IDOM or DOMS may be NULL (meaning the caller is not interested in
-   immediate resp. all dominators).  */
+/* Compute the data necessary for fast resolving of dominator queries in a
+   static dominator tree.  */
 
-dominance_info
-calculate_dominance_info (reverse)
-     enum cdi_direction reverse;
+static void
+compute_dom_fast_query (enum cdi_direction dir)
+{
+  int num = 0;
+  basic_block bb;
+
+  if (dom_computed[dir] < DOM_NO_FAST_QUERY)
+    abort ();
+
+  if (dom_computed[dir] == DOM_OK)
+    return;
+
+  FOR_ALL_BB (bb)
+    {
+      if (!bb->dom[dir]->father)
+      assign_dfs_numbers (bb->dom[dir], &num);
+    }
+
+  dom_computed[dir] = DOM_OK;
+}
+
+/* The main entry point into this module.  DIR is set depending on whether
+   we want to compute dominators or postdominators.  */
+
+void
+calculate_dominance_info (enum cdi_direction dir)
 {
   struct dom_info di;
-  dominance_info info;
   basic_block b;
 
-  /* 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");
+  if (dom_computed[dir] == DOM_OK)
+    return;
 
-  /* Add the two well-known basic blocks.  */
-  SET_BB_NODE (info, ENTRY_BLOCK_PTR, et_forest_add_node (info->forest,
-							  ENTRY_BLOCK_PTR));
-  SET_BB_NODE (info, EXIT_BLOCK_PTR, et_forest_add_node (info->forest,
-							 EXIT_BLOCK_PTR));
-  FOR_EACH_BB (b)
-    SET_BB_NODE (info, b, et_forest_add_node (info->forest, b));
+  if (dom_computed[dir] != DOM_NO_FAST_QUERY)
+    {
+      if (dom_computed[dir] != DOM_NONE)
+      free_dominance_info (dir);
 
-  init_dom_info (&di);
-  calc_dfs_tree (&di, reverse);
-  calc_idoms (&di, reverse);
+      FOR_ALL_BB (b)
+	{
+	  b->dom[dir] = et_new_tree (b);
+	}
 
+      init_dom_info (&di);
+      calc_dfs_tree (&di, dir);
+      calc_idoms (&di, dir);
 
-  FOR_EACH_BB (b)
-    {
-      TBB d = di.dom[di.dfs_order[b->index]];
+      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]);
+	}
 
-      if (di.dfs_to_bb[d])
-        et_forest_add_edge (info->forest, BB_NODE (info, di.dfs_to_bb[d]), BB_NODE (info, b));
+      free_dom_info (&di);
+      dom_computed[dir] = DOM_NO_FAST_QUERY;
     }
 
-  free_dom_info (&di);
-  return info;
+  compute_dom_fast_query (dir);
 }
 
-/* Free dominance information.  */
+/* Free dominance information for direction DIR.  */
 void
-free_dominance_info (info)
-     dominance_info info;
+free_dominance_info (enum cdi_direction dir)
 {
   basic_block bb;
 
-  /* Allow users to create new basic block without setting up the dominance
-     information for them.  */
-  FOR_EACH_BB (bb)
-    if (bb->index < (int)(info->varray->num_elements - 2)
-	&& BB_NODE (info, bb))
-      delete_from_dominance_info (info, bb);
-  delete_from_dominance_info (info, ENTRY_BLOCK_PTR);
-  delete_from_dominance_info (info, EXIT_BLOCK_PTR);
-  et_forest_delete (info->forest);
-  VARRAY_GROW (info->varray, 0);
-  free (info);
+  if (!dom_computed[dir])
+    return;
+
+  FOR_ALL_BB (bb)
+    {
+      delete_from_dominance_info (dir, bb);
+    }
+
+  dom_computed[dir] = DOM_NONE;
 }
 
 /* Return the immediate dominator of basic block BB.  */
 basic_block
-get_immediate_dominator (dom, bb)
-     dominance_info dom;
-     basic_block bb;
+get_immediate_dominator (enum cdi_direction dir, basic_block bb)
 {
-  return et_forest_node_value (dom->forest,
-			       et_forest_parent (dom->forest,
-						 BB_NODE (dom, bb)));
+  struct et_node *node = bb->dom[dir];
+
+  if (!dom_computed[dir])
+    abort ();
+
+  if (!node->father)
+    return NULL;
+
+  return node->father->data; 
 }
 
 /* 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 (enum cdi_direction dir, basic_block bb,
+			 basic_block dominated_by)
 {
-  void *aux_bb_node;
-  et_forest_node_t bb_node = BB_NODE (dom, bb);
+  struct et_node *node = bb->dom[dir];
+
+  if (!dom_computed[dir])
+    abort ();
 
-  aux_bb_node = et_forest_parent (dom->forest, bb_node);
-  if (aux_bb_node)
-    et_forest_remove_edge (dom->forest, aux_bb_node, bb_node);
-  if (dominated_by != NULL)
+  if (node->father)
     {
-      if (bb == dominated_by)
-	abort ();
-      if (!et_forest_add_edge (dom->forest, BB_NODE (dom, dominated_by), bb_node))
-	abort ();
+      if (node->father->data == dominated_by)
+      return;
+      et_split (node);
     }
+
+  if (dominated_by)
+    et_set_father (node, dominated_by->dom[dir]);
+
+  if (dom_computed[dir] == DOM_OK)
+    dom_computed[dir] = DOM_NO_FAST_QUERY;
 }
 
-/* Store all basic blocks dominated by BB into BBS and return their number.  */
+/* Store all basic blocks immediately 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 (enum cdi_direction dir, basic_block bb, basic_block **bbs)
 {
-  int n, i;
+  int n;
+  struct et_node *node = bb->dom[dir], *son = node->son, *ason;
+
+  if (!dom_computed[dir])
+    abort ();
+
+  if (!son)
+    {
+      *bbs = NULL;
+      return 0;
+    }
+
+  for (ason = son->right, n = 1; ason != son; ason = ason->right)
+    n++;
+
+  *bbs = xmalloc (n * sizeof (basic_block));
+  (*bbs)[0] = son->data;
+  for (ason = son->right, n = 1; ason != son; ason = ason->right)
+    (*bbs)[n++] = ason->data;
 
-  *bbs = xmalloc (n_basic_blocks * sizeof (basic_block));
-  n = et_forest_enumerate_sons (dom->forest, BB_NODE (dom, bb), (et_forest_node_t *)*bbs);
-  for (i = 0; i < n; i++)
-   (*bbs)[i] = et_forest_node_value (dom->forest, (et_forest_node_t)(*bbs)[i]);
   return n;
 }
 
 /* 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 (enum cdi_direction dir, 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);
-  et_forest_node_t node2 = BB_NODE (dom, to);
-  int n = et_forest_enumerate_sons (dom->forest, node, bbs);
-  int i;
+  struct et_node *bb_node = bb->dom[dir], *to_node = to->dom[dir], *son;
+
+  if (!dom_computed[dir])
+    abort ();
 
-  for (i = 0; i < n; i++)
+  if (!bb_node->son)
+    return;
+
+  while (bb_node->son)
     {
-      et_forest_remove_edge (dom->forest, node, bbs[i]);
-      et_forest_add_edge (dom->forest, node2, bbs[i]);
+      son = bb_node->son;
+
+      et_split (son);
+      et_set_father (son, to_node);
     }
-  free (bbs);
+
+  if (dom_computed[dir] == DOM_OK)
+    dom_computed[dir] = DOM_NO_FAST_QUERY;
 }
 
 /* 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 (enum cdi_direction dir, basic_block bb1, basic_block bb2)
 {
+  if (!dom_computed[dir])
+    abort ();
+
   if (!bb1)
     return bb2;
   if (!bb2)
     return bb1;
-  return et_forest_node_value (dom->forest,
-			       et_forest_common_ancestor (dom->forest,
-							  BB_NODE (dom, bb1),
-							  BB_NODE (dom,
-								   bb2)));
+
+  return et_nca (bb1->dom[dir], bb2->dom[dir])->data;
 }
 
 /* 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 (enum cdi_direction dir, basic_block bb1, basic_block bb2)
 {
-  return nearest_common_dominator (dom, bb1, bb2) == bb2;
+  struct et_node *n1 = bb1->dom[dir], *n2 = bb2->dom[dir];
+
+  if (!dom_computed[dir])
+    abort ();
+
+  if (dom_computed[dir] == DOM_OK)
+    return (n1->dfs_num_in >= n2->dfs_num_in
+	    && n1->dfs_num_out <= n2->dfs_num_out);
+
+  return et_below (n1, n2);
 }
 
 /* Verify invariants of dominator structure.  */
 void
-verify_dominators (dom)
-     dominance_info dom;
+verify_dominators (enum cdi_direction dir)
 {
   int err = 0;
   basic_block bb;
 
+  if (!dom_computed[dir])
+    abort ();
+
   FOR_EACH_BB (bb)
     {
       basic_block dom_bb;
 
-      dom_bb = recount_dominator (dom, bb);
-      if (dom_bb != get_immediate_dominator (dom, bb))
+      dom_bb = recount_dominator (dir, bb);
+      if (dom_bb != get_immediate_dominator (dir, bb))
 	{
 	  error ("dominator of %d should be %d, not %d",
-	   bb->index, dom_bb->index, get_immediate_dominator(dom, bb)->index);
+	   bb->index, dom_bb->index, get_immediate_dominator(dir, bb)->index);
 	  err = 1;
 	}
     }
@@ -736,17 +771,18 @@ verify_dominators (dom)
 
 /* Recount dominator of BB.  */
 basic_block
-recount_dominator (dom, bb)
-     dominance_info dom;
-     basic_block bb;
+recount_dominator (enum cdi_direction dir, basic_block bb)
 {
    basic_block dom_bb = NULL;
    edge e;
 
+  if (!dom_computed[dir])
+    abort ();
+
    for (e = bb->pred; e; e = e->pred_next)
      {
-       if (!dominated_by_p (dom, e->src, bb))
-         dom_bb = nearest_common_dominator (dom, dom_bb, e->src);
+       if (!dominated_by_p (dir, e->src, bb))
+         dom_bb = nearest_common_dominator (dir, dom_bb, e->src);
      }
 
    return dom_bb;
@@ -755,58 +791,85 @@ recount_dominator (dom, bb)
 /* 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 (enum cdi_direction dir, basic_block *bbs, int n)
 {
   int i, changed = 1;
   basic_block old_dom, new_dom;
 
+  if (!dom_computed[dir])
+    abort ();
+
   while (changed)
     {
       changed = 0;
       for (i = 0; i < n; i++)
 	{
-	  old_dom = get_immediate_dominator (dom, bbs[i]);
-	  new_dom = recount_dominator (dom, bbs[i]);
+	  old_dom = get_immediate_dominator (dir, bbs[i]);
+	  new_dom = recount_dominator (dir, bbs[i]);
 	  if (old_dom != new_dom)
 	    {
 	      changed = 1;
-	      set_immediate_dominator (dom, bbs[i], new_dom);
+	      set_immediate_dominator (dir, bbs[i], new_dom);
 	    }
 	}
     }
 }
 
 void
-add_to_dominance_info (dom, bb)
-     dominance_info dom;
-     basic_block bb;
+add_to_dominance_info (enum cdi_direction dir, basic_block bb)
 {
-  VARRAY_GROW (dom->varray, last_basic_block + 3);
-#ifdef ENABLE_CHECKING
-  if (BB_NODE (dom, bb))
+  if (!dom_computed[dir])
     abort ();
-#endif
-  SET_BB_NODE (dom, bb, et_forest_add_node (dom->forest, bb));
+
+  if (bb->dom[dir])
+    abort ();
+
+  bb->dom[dir] = et_new_tree (bb);
+
+  if (dom_computed[dir] == DOM_OK)
+    dom_computed[dir] = DOM_NO_FAST_QUERY;
 }
 
 void
-delete_from_dominance_info (dom, bb)
-     dominance_info dom;
-     basic_block bb;
+delete_from_dominance_info (enum cdi_direction dir, basic_block bb)
+{
+  if (!dom_computed[dir])
+    abort ();
+
+  et_free_tree (bb->dom[dir]);
+  bb->dom[dir] = NULL;
+
+  if (dom_computed[dir] == DOM_OK)
+    dom_computed[dir] = DOM_NO_FAST_QUERY;
+}
+
+/* Returns the first son of BB in the dominator or postdominator tree
+   as determined by DIR.  */
+
+basic_block
+first_dom_son (enum cdi_direction dir, basic_block bb)
 {
-  et_forest_remove_node (dom->forest, BB_NODE (dom, bb));
-  SET_BB_NODE (dom, bb, NULL);
+  struct et_node *son = bb->dom[dir]->son;
+
+  return son ? son->data : NULL;
+}
+
+/* Returns the next dominance son after BB in the dominator or postdominator
+   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)
+{
+  struct et_node *next = bb->dom[dir]->right;
+
+  return next->father->son == next ? NULL : next->data;
 }
 
 void
-debug_dominance_info (dom)
-  dominance_info dom;
+debug_dominance_info (enum cdi_direction dir)
 {
   basic_block bb, bb2;
   FOR_EACH_BB (bb)
-    if ((bb2 = get_immediate_dominator (dom, bb)))
+    if ((bb2 = get_immediate_dominator (dir, bb)))
       fprintf (stderr, "%i %i\n", bb->index, bb2->index);
 }