Michael Matz <matzmich@cs.tu-berlin.de>

        * dominance.c: New file.
        * Makefile.in (OBJS): Add dominance.o.

        * flow.c (compute_flow_dominators): Remove.
        (compute_immediate_dominators): Remove.
        (compute_immediate_postdominators): Remove.
        * basic-block.h: Remove their prototypes.
        (calculate_dominance_info): Add prototype.

        * dce.c (eliminate_dead_code): Change calls to above functions.
        Don't compute dominators but only immediate dominators.
        * flow.c (flow_loops_find): Change callers.
        * gcse.c (compute_code_hoist_data): Likewise.
        * haifa-sched.c (schedule_insns): Likewise.
        * ifcvt.c (if_convert): Likewise.
        * ssa.c (convert_to_ssa): Likewise, and only compute immediate
        dominators.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@37449 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 622 insertions, 0 deletions

diff --git a/gcc/dominance.c b/gcc/dominance.c
new file mode 100644
index 00000000000..66ff11e2bae
--- /dev/null
+++ b/gcc/dominance.c
@@ -0,0 +1,622 @@
+/* Calculate (post)dominators in slightly super-linear time.
+   Copyright (C) 2000 Free Software Foundation, Inc.
+   Contributed by Michael Matz (matz@ifh.de).
+  
+   This file is part of GNU CC.
+ 
+   GNU CC is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   GNU CC is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with GNU CC; see the file COPYING.  If not, write to
+   the Free Software Foundation, 59 Temple Place - Suite 330,
+   Boston, MA 02111-1307, USA.  */
+
+/* This file implements the well known algorithm from Lengauer and Tarjan
+   to compute the dominators in a control flow graph.  A basic block D is said
+   to dominate another block X, when all paths from the entry node of the CFG
+   to X go also over D.  The dominance relation is a transitive reflexive
+   relation and its minimal transitive reduction is a tree, called the
+   dominator tree.  So for each block X besides the entry block exists a
+   block I(X), called the immediate dominator of X, which is the parent of X
+   in the dominator tree.
+
+   The algorithm computes this dominator tree implicitely by computing for
+   each block its immediate dominator.  We use tree balancing and path
+   compression, so its the O(e*a(e,v)) variant, where a(e,v) is the very
+   slowly growing functional inverse of the Ackerman function.  */
+
+#include "config.h"
+#include "system.h"
+#include "rtl.h"
+#include "hard-reg-set.h"
+#include "basic-block.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
+   number of the corresponding basic block.  Please note, that we include the
+   artificial ENTRY_BLOCK (or EXIT_BLOCK in the post-dom case) in our lists to
+   support multiple entry points.  As it has no real basic block index we use
+   'n_basic_blocks' for that.  Its dfs number is of course 1.  */
+
+/* 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.  */
+
+struct dom_info
+{
+  /* 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
+     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
+     of x.  */
+  TBB *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 representant
+     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
+     be understood as the next sibling of x.  */
+  TBB *set_child;
+
+  /* If b is the number of a basic block (BB->index), 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;
+  /* If x is the DFS-index of a node which correspondends with an 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;
+
+  /* This is the next free DFS number when creating the DFS tree or forest. */
+  unsigned int dfsnum;
+  /* The number of nodes in the DFS tree (==dfsnum-1).  */
+  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));
+static void idoms_to_doms		PARAMS ((struct dom_info *,
+						 sbitmap *));
+
+/* 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) = (type *) xcalloc ((num), sizeof (type));		\
+    else							\
+      {								\
+        (var) = (type *) 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.  */
+
+static void
+init_dom_info (di)
+     struct dom_info *di;
+{
+  /* We need memory for n_basic_blocks nodes and the ENTRY_BLOCK or
+     EXIT_BLOCK.  */
+  unsigned int num = n_basic_blocks + 1 + 1;
+  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);
+
+  init_ar (di->bucket, TBB, num, 0);
+  init_ar (di->next_bucket, TBB, num, 0);
+
+  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);
+
+  init_ar (di->dfs_order, TBB, (unsigned int) n_basic_blocks + 1, 0);
+  init_ar (di->dfs_to_bb, basic_block, num, 0);
+
+  di->dfsnum = 1;
+  di->nodes = 0;
+}
+
+#undef init_ar
+
+/* Free all allocated memory in DI, but not DI itself.  */
+
+static void
+free_dom_info (di)
+     struct dom_info *di;
+{
+  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);
+}
+
+/* The nonrecursive variant of creating a DFS tree.  DI is our working
+   structure, BB the starting basic block for this tree and REVERSE
+   is true, if predecessors should be visited instead of successors of a
+   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 (di, bb, reverse)
+     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.  */
+  edge e;
+  TBB child_i, my_i = 0;
+  edge *stack;
+  int sp;
+  /* Start block (ENTRY_BLOCK_PTR for forward problem, EXIT_BLOCK for backward
+     problem).  */
+  basic_block en_block;
+  /* Ending block.  */
+  basic_block ex_block;
+
+  stack = (edge *) xmalloc ((n_basic_blocks + 3) * sizeof (edge));
+  sp = 0;
+
+  /* Initialize our border blocks, and the first edge.  */
+  if (reverse)
+    {
+      e = bb->pred;
+      en_block = EXIT_BLOCK_PTR;
+      ex_block = ENTRY_BLOCK_PTR;
+    }
+  else
+    {
+      e = bb->succ;
+      en_block = ENTRY_BLOCK_PTR;
+      ex_block = EXIT_BLOCK_PTR;
+    }
+
+  /* When the stack is empty we break out of this loop.  */
+  while (1)
+    {
+      basic_block bn;
+
+      /* This loop traverses edges e in depth first manner, and fills the
+         stack.  */
+      while (e)
+	{
+	  edge e_next;
+
+	  /* Deduce from E the current and the next block (BB and BN), and the
+	     next edge.  */
+	  if (reverse)
+	    {
+	      bn = e->src;
+
+	      /* 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 (di->dfs_order[bn->index] || bn == ex_block)
+		{
+		  e = e->pred_next;
+		  continue;
+		}
+	      bb = e->dest;
+	      e_next = bn->pred;
+	    }
+	  else
+	    {
+	      bn = e->dest;
+	      if (di->dfs_order[bn->index] || bn == ex_block)
+		{
+		  e = e->succ_next;
+		  continue;
+		}
+	      bb = e->src;
+	      e_next = bn->succ;
+	    }
+
+	  if (bn == en_block)
+	    abort ();
+
+	  /* Fill the DFS tree info calculatable _before_ recursing.  */
+	  if (bb != en_block)
+	    my_i = di->dfs_order[bb->index];
+	  else
+	    my_i = di->dfs_order[n_basic_blocks];
+	  child_i = di->dfs_order[bn->index] = di->dfsnum++;
+	  di->dfs_to_bb[child_i] = bn;
+	  di->dfs_parent[child_i] = my_i;
+
+	  /* Save the current point in the CFG on the stack, and recurse.  */
+	  stack[sp++] = e;
+	  e = e_next;
+	}
+
+      if (!sp)
+	break;
+      e = stack[--sp];
+
+      /* OK.  The edge-list was exhausted, meaning normally we would
+         end the recursion.  After returning from the recursive call,
+         there were (may be) other statements which were run after a
+         child node was completely considered by DFS.  Here is the
+         point to do it in the non-recursive variant.
+         E.g. The block just completed is in e->dest for forward DFS,
+         the block not yet completed (the parent of the one above)
+         in e->src.  This could be used e.g. for computing the number of
+         descendants or the tree depth.  */
+      if (reverse)
+	e = e->pred_next;
+      else
+	e = e->succ_next;
+    }
+  free (stack);
+}
+
+/* The main entry for calculating the DFS tree or forest.  DI is our working
+   structure and REVERSE is true, if we are interested in the reverse flow
+   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 (di, reverse)
+     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;
+  di->dfs_order[n_basic_blocks] = di->dfsnum;
+  di->dfs_to_bb[di->dfsnum] = begin;
+  di->dfsnum++;
+
+  calc_dfs_tree_nonrec (di, begin, reverse);
+
+  if (reverse)
+    {
+      /* In the post-dom case we may have nodes without a path to EXIT_BLOCK.
+         They are reverse-unreachable.  In the dom-case we disallow such
+         nodes, but in post-dom we have to deal with them, so we simply
+         include them in the DFS tree which actually becomes a forest.  */
+      int i;
+      for (i = n_basic_blocks - 1; i >= 0; i--)
+	{
+	  basic_block b = BASIC_BLOCK (i);
+	  if (di->dfs_order[b->index])
+	    continue;
+	  di->dfs_order[b->index] = di->dfsnum;
+	  di->dfs_to_bb[di->dfsnum] = b;
+	  di->dfsnum++;
+	  calc_dfs_tree_nonrec (di, b, reverse);
+	}
+    }
+
+  di->nodes = di->dfsnum - 1;
+
+  /* This aborts e.g. when there is _no_ path from ENTRY to EXIT at all.  */
+  if (di->nodes != (unsigned int) n_basic_blocks + 1)
+    abort ();
+}
+
+/* Compress the path from V to the root of its set and update path_min at the
+   same time.  After compress(di, V) set_chain[V] is the root of the set V is
+   in and path_min[V] is the node with the smallest key[] value on the path
+   from V to that root.  */
+
+static void
+compress (di, v)
+     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).
+     Also performance wise compress() ranges _far_ behind eval().  */
+  TBB parent = di->set_chain[v];
+  if (di->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 the path from V to the set root of V if needed (when the root has
+   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 (di, v)
+     struct dom_info *di;
+     TBB v;
+{
+  /* The representant of the set V is in, also called root (as the set
+     representation is a tree).  */
+  TBB rep = di->set_chain[v];
+
+  /* V itself is the root.  */
+  if (!rep)
+    return di->path_min[v];
+
+  /* Compress only if necessary.  */
+  if (di->set_chain[rep])
+    {
+      compress (di, v);
+      rep = di->set_chain[v];
+    }
+
+  if (di->key[di->path_min[rep]] >= di->key[di->path_min[v]])
+    return di->path_min[v];
+  else
+    return di->path_min[rep];
+}
+
+/* This essentially merges the two sets of V and W, giving a single set with
+   the new root V.  The internal representation of these disjoint sets is a
+   balanced tree.  Currently link(V,W) is only used with V being the parent
+   of W.  */
+
+static void
+link_roots (di, v, w)
+     struct dom_info *di;
+     TBB v, w;
+{
+  TBB s = w;
+
+  /* Rebalance the tree.  */
+  while (di->key[di->path_min[w]] < di->key[di->path_min[di->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]])
+	{
+	  di->set_chain[di->set_child[s]] = s;
+	  di->set_child[s] = di->set_child[di->set_child[s]];
+	}
+      else
+	{
+	  di->set_size[di->set_child[s]] = di->set_size[s];
+	  s = di->set_chain[s] = di->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])
+    {
+      TBB tmp = s;
+      s = di->set_child[v];
+      di->set_child[v] = tmp;
+    }
+
+  /* Merge all subtrees.  */
+  while (s)
+    {
+      di->set_chain[s] = v;
+      s = di->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].  */
+
+static void
+calc_idoms (di, reverse)
+     struct dom_info *di;
+     enum cdi_direction reverse;
+{
+  TBB v, w, k, par;
+  basic_block en_block;
+  if (reverse)
+    en_block = EXIT_BLOCK_PTR;
+  else
+    en_block = ENTRY_BLOCK_PTR;
+
+  /* Go backwards in DFS order, to first look at the leafs.  */
+  v = di->nodes;
+  while (v > 1)
+    {
+      basic_block bb = di->dfs_to_bb[v];
+      edge e, e_next;
+
+      par = di->dfs_parent[v];
+      k = v;
+      if (reverse)
+	e = bb->succ;
+      else
+	e = bb->pred;
+
+      /* Search all direct predecessors for the smallest node with a path
+         to them.  That way we have the smallest node with also a path to
+         us only over nodes behind us.  In effect we search for our
+         semidominator.  */
+      for (; e; e = e_next)
+	{
+	  TBB k1;
+	  basic_block b;
+
+	  if (reverse)
+	    {
+	      b = e->dest;
+	      e_next = e->succ_next;
+	    }
+	  else
+	    {
+	      b = e->src;
+	      e_next = e->pred_next;
+	    }
+	  if (b == en_block)
+	    k1 = di->dfs_order[n_basic_blocks];
+	  else
+	    k1 = di->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)];
+	  if (k1 < k)
+	    k = k1;
+	}
+
+      di->key[v] = k;
+      link_roots (di, par, v);
+      di->next_bucket[v] = di->bucket[k];
+      di->bucket[k] = v;
+
+      /* Transform semidominators into dominators.  */
+      for (w = di->bucket[par]; w; w = di->next_bucket[w])
+	{
+	  k = eval (di, w);
+	  if (di->key[k] < di->key[w])
+	    di->dom[w] = k;
+	  else
+	    di->dom[w] = par;
+	}
+      /* We don't need to cleanup next_bucket[].  */
+      di->bucket[par] = 0;
+      v--;
+    }
+
+  /* Explicitely 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]];
+}
+
+/* Convert the information about immediate dominators (in DI) to sets of all
+   dominators (in DOMINATORS).  */
+
+static void
+idoms_to_doms (di, dominators)
+     struct dom_info *di;
+     sbitmap *dominators;
+{
+  TBB i, e_index;
+  int bb, bb_idom;
+  sbitmap_vector_zero (dominators, n_basic_blocks);
+  /* We have to be careful, to not include the ENTRY_BLOCK or EXIT_BLOCK
+     in the list of (post)-doms, so remember that in e_index.  */
+  e_index = di->dfs_order[n_basic_blocks];
+
+  for (i = 1; i <= di->nodes; i++)
+    {
+      if (i == e_index)
+	continue;
+      bb = di->dfs_to_bb[i]->index;
+
+      if (di->dom[i] && (di->dom[i] != e_index))
+	{
+	  bb_idom = di->dfs_to_bb[di->dom[i]]->index;
+	  sbitmap_copy (dominators[bb], dominators[bb_idom]);
+	}
+      else
+	{
+	  /* It has no immediate dom or only ENTRY_BLOCK or EXIT_BLOCK.
+	     If it is a child of ENTRY_BLOCK that's OK, and it's only
+	     dominated by itself; if it's _not_ a child of ENTRY_BLOCK, it
+	     means, it is unreachable.  That case has been disallowed in the
+	     building of the DFS tree, so we are save here.  For the reverse
+	     flow graph it means, it has no children, so, to be compatible
+	     with the old code, we set the post_dominators to all one.  */
+	  if (!di->dom[i])
+	    {
+	      sbitmap_ones (dominators[bb]);
+	    }
+	}
+      SET_BIT (dominators[bb], bb);
+    }
+}
+
+/* The main entry point into this module.  IDOM is an integer array with room
+   for n_basic_blocks integers, DOMS is a preallocated sbitmap array having
+   room for n_basic_blocks^2 bits, and POST is true if the caller wants to
+   know post-dominators.
+
+   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.
+
+   Either IDOM or DOMS may be NULL (meaning the caller is not interested in
+   immediate resp. all dominators).  */
+
+void
+calculate_dominance_info (idom, doms, reverse)
+     int *idom;
+     sbitmap *doms;
+     enum cdi_direction reverse;
+{
+  struct dom_info di;
+
+  if (!doms && !idom)
+    return;
+  init_dom_info (&di);
+  calc_dfs_tree (&di, reverse);
+  calc_idoms (&di, reverse);
+
+  if (idom)
+    {
+      int i;
+      for (i = 0; i < n_basic_blocks; i++)
+	{
+	  basic_block b = BASIC_BLOCK (i);
+	  TBB d = di.dom[di.dfs_order[b->index]];
+
+	  /* The old code didn't modify array elements of nodes having only
+	     itself as dominator (d==0) or only ENTRY_BLOCK (resp. EXIT_BLOCK)
+	     (d==1).  */
+	  if (d > 1)
+	    idom[i] = di.dfs_to_bb[d]->index;
+	}
+    }
+  if (doms)
+    idoms_to_doms (&di, doms);
+
+  free_dom_info (&di);
+}