* flow.c (flow_nodes_print, flow_loops_cfg_dump): New functions.

	(flow_loop_nested_p, flow_loops_dump, flow_loops_free): Likewise.
	(flow_loop_exits_find, flow_loop_nodes_find): Likewise.
	(flow_depth_first_order_compute, flow_loop_pre_header_find): Likewise.
	(flow_loop_tree_node_add, flow_loops_tree_build): Likewise.
	(flow_loop_level_compute, low_loops_level_compute): Likewise.
	(flow_loops_find, flow_loop_outside_edge_p): Likewise.
	* basic-block.h: Protect from multiple inclusion.
	(flow_loops_find, flow_loops_free, flow_loop_dump): Add protoypes.
	(struct loops, struct loop): Define structures.
	* sbitmap.c (sbitmap_a_subset_b_p): New function.
	* sbitmap.h: Protect from multiple inclusion.
	(sbitmap_a_subset_b_p): Add prototype.
	* Makefile.in (LOOP_H): New macro.
	(stmt.o, integrate.o, loop.o, unroll.o): Replace loop.h with LOOP_H.


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

6 files changed, 818 insertions, 4 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index dff51d3d83e..facaadc5698 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,21 @@
+1999-11-30  Michael Hayes  <m.hayes@elec.canterbury.ac.nz>
+
+	* flow.c (flow_nodes_print, flow_loops_cfg_dump): New functions.
+	(flow_loop_nested_p, flow_loops_dump, flow_loops_free): Likewise.
+	(flow_loop_exits_find, flow_loop_nodes_find): Likewise.
+	(flow_depth_first_order_compute, flow_loop_pre_header_find): Likewise.
+	(flow_loop_tree_node_add, flow_loops_tree_build): Likewise.
+	(flow_loop_level_compute, low_loops_level_compute): Likewise.
+	(flow_loops_find, flow_loop_outside_edge_p): Likewise.
+	* basic-block.h: Protect from multiple inclusion.
+	(flow_loops_find, flow_loops_free, flow_loop_dump): Add protoypes.
+	(struct loops, struct loop): Define structures.
+	* sbitmap.c (sbitmap_a_subset_b_p): New function.
+	* sbitmap.h: Protect from multiple inclusion.
+	(sbitmap_a_subset_b_p): Add prototype.
+	* Makefile.in (LOOP_H): New macro.
+	(stmt.o, integrate.o, loop.o, unroll.o): Replace loop.h with LOOP_H.
+
 Tue Nov 30 01:34:47 1999  Philippe De Muyter  <phdm@macqel.be>
 
 	* cppinit.c (CAT): The argument list of this macro may not contain
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 17a6a2bfef1..61144c4f14c 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -748,6 +748,7 @@ DEMANGLE_H = $(srcdir)/../include/demangle.h
 RECOG_H = recog.h
 EXPR_H = expr.h insn-codes.h
 REGS_H = regs.h varray.h $(MACHMODE_H)
+LOOP_H = loop.h varray.h
 #
 # Language makefile fragments.
 
@@ -1484,7 +1485,7 @@ function.o : function.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h \
    insn-config.h $(RECOG_H) output.h toplev.h except.h hash.h ggc.h
 stmt.o : stmt.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h function.h  \
    insn-flags.h insn-config.h insn-codes.h hard-reg-set.h $(EXPR_H) except.h \
-   loop.h $(RECOG_H) toplev.h output.h varray.h ggc.h
+   $(LOOP_H) $(RECOG_H) toplev.h output.h varray.h ggc.h
 except.o : except.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h \
    function.h insn-flags.h $(EXPR_H) $(REGS_H) hard-reg-set.h \
    insn-config.h $(RECOG_H) output.h except.h toplev.h intl.h ggc.h
@@ -1527,7 +1528,7 @@ emit-rtl.o : emit-rtl.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h \
 real.o : real.c $(CONFIG_H) system.h $(TREE_H) toplev.h
 integrate.o : integrate.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h \
    integrate.h insn-flags.h insn-config.h $(EXPR_H) real.h $(REGS_H) \
-   intl.h function.h output.h $(RECOG_H) except.h toplev.h loop.h
+   intl.h function.h output.h $(RECOG_H) except.h toplev.h $(LOOP_H)
 jump.o : jump.c $(CONFIG_H) system.h $(RTL_H) flags.h hard-reg-set.h $(REGS_H) \
    insn-config.h insn-flags.h $(RECOG_H) $(EXPR_H) real.h except.h function.h \
    toplev.h insn-attr.h
@@ -1550,11 +1551,11 @@ lcm.o : lcm.c $(CONFIG_H) system.h $(RTL_H) $(REGS_H) hard-reg-set.h flags.h \
 profile.o : profile.c $(CONFIG_H) system.h $(RTL_H) flags.h insn-flags.h \
    gcov-io.h $(TREE_H) output.h $(REGS_H) toplev.h function.h insn-config.h \
    ggc.h
-loop.o : loop.c $(CONFIG_H) system.h $(RTL_H) flags.h loop.h insn-config.h \
+loop.o : loop.c $(CONFIG_H) system.h $(RTL_H) flags.h $(LOOP_H) insn-config.h \
    insn-flags.h $(REGS_H) hard-reg-set.h $(RECOG_H) $(EXPR_H) real.h \
    $(BASIC_BLOCK_H) function.h toplev.h varray.h except.h
 unroll.o : unroll.c $(CONFIG_H) system.h $(RTL_H) insn-config.h function.h \
-   integrate.h $(REGS_H) $(RECOG_H) flags.h $(EXPR_H) loop.h toplev.h varray.h
+   integrate.h $(REGS_H) $(RECOG_H) flags.h $(EXPR_H) $(LOOP_H) toplev.h varray.h
 flow.o : flow.c $(CONFIG_H) system.h $(RTL_H) $(TREE_H) flags.h insn-config.h \
    $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h $(RECOG_H) \
    insn-flags.h function.h except.h
diff --git a/gcc/basic-block.h b/gcc/basic-block.h
index 499f86ec4de..ef7276e0b87 100644
--- a/gcc/basic-block.h
+++ b/gcc/basic-block.h
@@ -18,6 +18,8 @@ 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.  */
 
+#ifndef _BASIC_BLOCK_H
+#define _BASIC_BLOCK_H 1
 
 #include "bitmap.h"
 #include "sbitmap.h"
@@ -222,6 +224,92 @@ extern void remove_fake_edges		PROTO ((void));
 extern void add_noreturn_fake_exit_edges	PROTO ((void));
 extern void flow_delete_insn_chain	PROTO((rtx, rtx));
 
+
+/* Structure to hold information for each natural loop.  */
+struct loop
+{
+  int num;
+
+  /* Basic block of loop header.  */
+  basic_block header;
+
+  /* Basic block of loop latch.  */
+  basic_block latch;
+
+  /* Basic block of loop pre-header or NULL if it does not exist.  */
+  basic_block pre_header;
+
+  /* Bitmap of blocks contained within the loop.  */
+  sbitmap nodes;
+
+  /* Number of blocks contained within the loop.  */
+  int num_nodes;
+
+  /* Array of edges that exit the loop.  */
+  edge *exits;
+
+  /* Number of edges that exit the loop.  */
+  int num_exits;
+
+  /* The loop nesting depth.  */
+  int depth;
+
+  /* The height of the loop (enclosed loop levels) within the loop
+     hierarchy tree.  */
+  int level;
+
+  /* The outer (parent) loop or NULL if outermost loop.  */
+  struct loop *outer;
+
+  /* The first inner (child) loop or NULL if innermost loop.  */
+  struct loop *inner;
+
+  /* Link to the next (sibling) loop.  */
+  struct loop *next;
+
+  /* Non-zero if the loop shares a header with another loop.  */
+  int shared;
+
+  /* Non-zero if the loop is invalid (e.g., contains setjmp.).  */
+  int invalid;
+
+  /* Auxiliary info specific to a pass.  */
+  void *info;
+};
+
+
+/* Structure to hold CFG information about natural loops within a function.  */
+struct loops
+{
+  /* Number of natural loops in the function.  */
+  int num;
+
+  /* Array of natural loop descriptors (scanning this array in reverse order
+     will find the inner loops before their enclosing outer loops).  */
+  struct loop *array;
+
+  /* Pointer to root of loop heirachy tree.  */
+  struct loop *tree;
+
+  /* Information derived from the CFG.  */
+  struct cfg
+  {
+    /* The bitmap vector of dominators or NULL if not computed.  */
+    sbitmap *dom;
+
+    /* The ordering of the basic blocks in a depth first search.  */
+    int *dfs_order;
+  } cfg;
+
+  /* Headers shared by multiple loops that should be merged.  */
+  sbitmap shared_headers;
+};
+
+extern int flow_loops_find PROTO ((struct loops *));
+extern void flow_loops_free PROTO ((struct loops *));
+extern void flow_loops_dump PROTO ((const struct loops *, FILE *, int));
+
+
 /* This structure maintains an edge list vector.  */
 struct edge_list 
 {
@@ -295,3 +383,5 @@ extern void compute_available		PROTO ((sbitmap *, sbitmap *,
 /* In emit-rtl.c.  */
 extern rtx emit_block_insn_after	PROTO((rtx, rtx, basic_block));
 extern rtx emit_block_insn_before	PROTO((rtx, rtx, basic_block));
+
+#endif /* _BASIC_BLOCK_H */
diff --git a/gcc/flow.c b/gcc/flow.c
index 83783722288..f147b7e4e51 100644
--- a/gcc/flow.c
+++ b/gcc/flow.c
@@ -6332,3 +6332,684 @@ add_noreturn_fake_exit_edges ()
     if (BASIC_BLOCK (x)->succ == NULL)
       make_edge (NULL, BASIC_BLOCK (x), EXIT_BLOCK_PTR, EDGE_FAKE);
 }
+
+/* Dump the list of basic blocks in the bitmap NODES.  */
+static void 
+flow_nodes_print (str, nodes, file)
+     const char *str;
+     const sbitmap nodes;
+     FILE *file;
+{
+  int node;
+
+  fprintf (file, "%s { ", str);
+  EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {fprintf (file, "%d ", node);});
+  fputs ("}\n", file);
+}
+
+
+/* Dump the list of exiting edges in the array EDGES.  */
+static void 
+flow_exits_print (str, edges, num_edges, file)
+     const char *str;
+     const edge *edges;
+     int num_edges;
+     FILE *file;
+{
+  int i;
+
+  fprintf (file, "%s { ", str);
+  for (i = 0; i < num_edges; i++)
+    fprintf (file, "%d->%d ", edges[i]->src->index, edges[i]->dest->index);
+  fputs ("}\n", file);
+}
+
+
+/* Dump loop related CFG information.  */
+static void
+flow_loops_cfg_dump (loops, file)
+     const struct loops *loops;
+     FILE *file;
+{
+  int i;
+
+  if (! loops->num || ! file || ! loops->cfg.dom)
+    return;
+
+  for (i = 0; i < n_basic_blocks; i++)
+    {
+      edge succ;
+
+      fprintf (file, ";; %d succs { ", i);
+      for (succ = BASIC_BLOCK (i)->succ; succ; succ = succ->succ_next)
+	fprintf (file, "%d ", succ->dest->index);
+      flow_nodes_print ("} dom", loops->cfg.dom[i], file);	
+    }
+
+
+  /* Dump the DFS node order.  */
+  if (loops->cfg.dfs_order)
+    {
+      fputs (";; DFS order: ", file);
+      for (i = 0; i < n_basic_blocks; i++)
+	fprintf (file, "%d ", loops->cfg.dfs_order[i]);
+      fputs ("\n", file);
+    }
+}
+
+
+/* Return non-zero if the nodes of LOOP are a subset of OUTER.  */
+int
+flow_loop_nested_p (outer, loop)
+     struct loop *outer;
+     struct loop *loop;
+{
+  return sbitmap_a_subset_b_p (loop->nodes, outer->nodes);
+}
+
+
+/* Dump the loop information specified by LOOPS to the stream FILE.  */
+void 
+flow_loops_dump (loops, file, verbose)
+     const struct loops *loops;
+     FILE *file;
+     int verbose;
+{
+  int i;
+  int num_loops;
+
+  num_loops = loops->num;
+  if (! num_loops || ! file)
+    return;
+
+  fprintf (file, ";; %d loops found\n", num_loops);
+
+  for (i = 0; i < num_loops; i++)
+    {
+      struct loop *loop = &loops->array[i];
+
+      fprintf (file, ";; loop %d (%d to %d):\n"
+	       ";;   header %d, latch %d, pre-header %d,"
+	       " depth %d, level %d, outer %d\n",
+	       i, INSN_UID (loop->header->head), INSN_UID (loop->latch->end),
+	       loop->header->index, loop->latch->index,
+	       loop->pre_header ? loop->pre_header->index : -1, 
+	       loop->depth, loop->level,
+	       loop->outer ? (loop->outer - loops->array) : -1);
+      fprintf (file, ";;   %d", loop->num_nodes);
+      flow_nodes_print (" nodes", loop->nodes, file);
+      fprintf (file, ";;   %d", loop->num_exits);
+      flow_exits_print (" exits", loop->exits, loop->num_exits, file);
+
+      if (loop->shared)
+	{
+	  int j;
+
+	  for (j = 0; j < i; j++)
+	    {
+	      struct loop *oloop = &loops->array[j];
+
+	      if (loop->header == oloop->header)
+		{
+		  int disjoint;
+		  int smaller;
+
+		  smaller = loop->num_nodes < oloop->num_nodes;
+
+		  /* If the union of LOOP and OLOOP is different than
+		     the larger of LOOP and OLOOP then LOOP and OLOOP
+		     must be disjoint.  */
+		  disjoint = ! flow_loop_nested_p (smaller ? loop : oloop);
+		  fprintf (file, ";; loop header %d shared by loops %d, %d"
+			   " %s\n",
+			   loop->header->index, i, j,
+			   disjoint ? "disjoint" : "nested");
+		}
+	    }
+	}
+
+      if (verbose)
+	{
+	  /* Print diagnostics to compare our concept of a loop with
+	     what the loop notes say.  */
+	  if (GET_CODE (PREV_INSN (loop->header->head)) != NOTE
+	      || NOTE_LINE_NUMBER (PREV_INSN (loop->header->head))
+	      != NOTE_INSN_LOOP_BEG)
+	    fprintf (file, ";; No NOTE_INSN_LOOP_BEG at %d\n", 
+		     INSN_UID (PREV_INSN (loop->header->head)));
+	  if (GET_CODE (NEXT_INSN (loop->latch->end)) != NOTE
+	      || NOTE_LINE_NUMBER (NEXT_INSN (loop->latch->end))
+	      != NOTE_INSN_LOOP_END)
+	    fprintf (file, ";; No NOTE_INSN_LOOP_END at %d\n",
+		     INSN_UID (NEXT_INSN (loop->latch->end)));
+	}
+    }
+
+  if (verbose)
+    flow_loops_cfg_dump (loops, file);
+}
+
+
+/* Free all the memory allocated for LOOPS.  */
+void 
+flow_loops_free (loops)
+       struct loops *loops;
+{
+  if (loops->array)
+    {
+      int i;
+
+      if (! loops->num)
+	abort ();
+
+      /* Free the loop descriptors.  */
+      for (i = 0; i < loops->num; i++)
+	{
+	  struct loop *loop = &loops->array[i];
+	  
+	  if (loop->nodes)
+	    sbitmap_free (loop->nodes);
+	  if (loop->exits)
+	    free (loop->exits);
+	}
+      free (loops->array);
+      loops->array = NULL;
+      
+      if (loops->cfg.dom)
+	sbitmap_vector_free (loops->cfg.dom);
+      if (loops->cfg.dfs_order)
+	free (loops->cfg.dfs_order);
+
+      sbitmap_free (loops->shared_headers);
+    }
+}
+
+
+/* Find the exits from the loop using the bitmap of loop nodes NODES
+   and store in EXITS array.  Return the number of exits from the
+   loop.  */
+static int
+flow_loop_exits_find (nodes, exits)
+     const sbitmap nodes;
+     edge **exits;
+{
+  edge e;
+  int node;
+  int num_exits;
+
+  *exits = NULL;
+
+  /* Check all nodes within the loop to see if there are any
+     successors not in the loop.  Note that a node may have multiple
+     exiting edges.  */
+  num_exits = 0;
+  EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {
+    for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next)
+      {
+	basic_block dest = e->dest;	  
+
+	if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index))
+	    num_exits++;
+      }
+  });
+
+  if (! num_exits)
+    return 0;
+
+  *exits = (edge *) xmalloc (num_exits * sizeof (edge *));
+
+  /* Store all exiting edges into an array.  */
+  num_exits = 0;
+  EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {
+    for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next)
+      {
+	basic_block dest = e->dest;	  
+
+	if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index))
+	  (*exits)[num_exits++] = e;
+      }
+  });
+
+  return num_exits;
+}
+
+
+/* Find the nodes contained within the loop with header HEADER and
+   latch LATCH and store in NODES.  Return the number of nodes within
+   the loop.  */
+static int 
+flow_loop_nodes_find (header, latch, nodes)
+     basic_block header;
+     basic_block latch;
+     sbitmap nodes;
+{
+  basic_block *stack;
+  int sp;
+  int num_nodes = 0;
+
+  stack = (basic_block *) xmalloc (n_basic_blocks * sizeof (basic_block));
+  sp = 0;
+
+  /* Start with only the loop header in the set of loop nodes.  */
+  sbitmap_zero (nodes);
+  SET_BIT (nodes, header->index);
+  num_nodes++;
+
+  /* Push the loop latch on to the stack.  */
+  if (! TEST_BIT (nodes, latch->index))
+    {
+      SET_BIT (nodes, latch->index);
+      num_nodes++;
+      stack[sp++] = latch;
+    }
+
+  while (sp)
+    {
+      basic_block node;
+      edge e;
+
+      node = stack[--sp];
+      for (e = node->pred; e; e = e->pred_next)
+	{
+	  basic_block ancestor = e->src;
+	  
+	  /* If each ancestor not marked as part of loop, add to set of
+	     loop nodes and push on to stack.  */
+	  if (ancestor != ENTRY_BLOCK_PTR
+	      && ! TEST_BIT (nodes, ancestor->index))
+	    {
+	      SET_BIT (nodes, ancestor->index);
+	      num_nodes++;
+	      stack[sp++] = ancestor;
+	    }
+	}
+    }
+  free (stack);
+  return num_nodes;
+}
+
+
+/* Compute the depth first search order and store in the array
+   DFS_ORDER, marking the nodes visited in VISITED.  Returns the
+   number of nodes visited.  */
+static int
+flow_depth_first_order_compute (dfs_order)
+     int *dfs_order;
+{
+  edge e;
+  edge *stack;
+  int sp;
+  int dfsnum = 0;
+  sbitmap visited;
+
+  /* Allocate stack for back-tracking up CFG.  */
+  stack = (edge *) xmalloc (n_basic_blocks * sizeof (edge));
+  sp = 0;
+
+  /* Allocate bitmap to track nodes that have been visited.  */
+  visited = sbitmap_alloc (n_basic_blocks);
+
+  /* None of the nodes in the CFG have been visited yet.  */
+  sbitmap_zero (visited);
+  
+  /* Start with the first successor edge from the entry block.  */
+  e = ENTRY_BLOCK_PTR->succ;
+  while (e)
+    {
+      basic_block src = e->src;
+      basic_block dest = e->dest;
+      
+      /* Mark that we have visited this node.  */
+      if (src != ENTRY_BLOCK_PTR)
+	SET_BIT (visited, src->index);
+
+      /* If this node has not been visited before, push the current
+	 edge on to the stack and proceed with the first successor
+	 edge of this node.  */
+      if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)
+	  && dest->succ)
+	{
+	  stack[sp++] = e;
+	  e = dest->succ;
+	}
+      else
+	{
+	  if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index)
+	      && ! dest->succ)
+	    {
+	      /* DEST has no successors (for example, a non-returning
+                 function is called) so do not push the current edge
+                 but carry on with its next successor.  */
+	      dfs_order[dest->index] = n_basic_blocks - ++dfsnum;
+	      SET_BIT (visited, dest->index);
+	    }
+
+	  while (! e->succ_next && src != ENTRY_BLOCK_PTR)
+	    {
+	      dfs_order[src->index] = n_basic_blocks - ++dfsnum;
+
+	      /* Pop edge off stack.  */
+	      e = stack[--sp];
+	      src = e->src;
+	    }
+	  e = e->succ_next;
+	}
+    }
+  free (stack);
+  sbitmap_free (visited);
+
+  /* The number of nodes visited should not be greater than
+     n_basic_blocks.  */
+  if (dfsnum > n_basic_blocks)
+    abort ();
+
+  /* There are some nodes left in the CFG that are unreachable.  */
+  if (dfsnum < n_basic_blocks)
+    abort ();
+  return dfsnum;
+}
+
+
+/* Return the block for the pre-header of the loop with header
+   HEADER where DOM specifies the dominator information.  Return NULL if
+   there is no pre-header.  */
+static basic_block
+flow_loop_pre_header_find (header, dom)
+     basic_block header;
+     const sbitmap *dom;     
+{
+  basic_block pre_header;
+  edge e;
+
+  /* If block p is a predecessor of the header and is the only block
+     that the header does not dominate, then it is the pre-header.  */
+  pre_header = NULL;
+  for (e = header->pred; e; e = e->pred_next)
+    {
+      basic_block node = e->src;
+      
+      if (node != ENTRY_BLOCK_PTR
+	  && ! TEST_BIT (dom[node->index], header->index))
+	{
+	  if (pre_header == NULL)
+	    pre_header = node;
+	  else
+	    {
+	      /* There are multiple edges into the header from outside 
+		 the loop so there is no pre-header block.  */
+	      pre_header = NULL;
+	      break;
+	    }
+	}
+    }
+  return pre_header;
+}
+
+
+/* Add LOOP to the loop hierarchy tree so that it is a sibling or a
+   descendant of ROOT.  */
+static void
+flow_loop_tree_node_add (root, loop)
+     struct loop *root;
+     struct loop *loop;
+{
+  struct loop *outer;
+
+  if (! loop)
+    return;
+
+  for (outer = root; outer; outer = outer->next)
+    {
+      if (flow_loop_nested_p (outer, loop))
+	{
+	  if (outer->inner)
+	    {
+	      /* Add LOOP as a sibling or descendent of OUTER->INNER.  */
+	      flow_loop_tree_node_add (outer->inner, loop);
+	    }
+	  else
+	    {
+	      /* Add LOOP as child of OUTER.  */
+	      outer->inner = loop;
+	      loop->outer = outer;
+	      loop->next = NULL;
+	    }
+	  return;
+	}
+    }
+  /* Add LOOP as a sibling of ROOT.  */
+  loop->next = root->next;
+  root->next = loop;
+  loop->outer = root->outer;
+}
+
+
+/* Build the loop hierarchy tree for LOOPS.  */
+static void
+flow_loops_tree_build (loops)
+       struct loops *loops;
+{
+  int i;
+  int num_loops;
+
+  num_loops = loops->num;
+  if (! num_loops)
+    return;
+
+  /* Root the loop hierarchy tree with the first loop found.
+     Since we used a depth first search this should be the 
+     outermost loop.  */
+  loops->tree = &loops->array[0];
+  loops->tree->outer = loops->tree->inner = loops->tree->next = NULL;
+
+  /* Add the remaining loops to the tree.  */
+  for (i = 1; i < num_loops; i++)
+    flow_loop_tree_node_add (loops->tree, &loops->array[i]);
+}
+
+
+/* Helper function to compute loop nesting depth and enclosed loop level
+   for the natural loop specified by LOOP at the loop depth DEPTH.   
+   Returns the loop level.  */
+static int
+flow_loop_level_compute (loop, depth)
+     struct loop *loop;
+     int depth;
+{
+  struct loop *inner;
+  int level = 0;
+
+  if (! loop)
+    return 0;
+
+  /* Traverse loop tree assigning depth and computing level as the
+     maximum level of all the inner loops of this loop.  The loop
+     level is equivalent to the height of the loop in the loop tree
+     and corresponds to the number of enclosed loop levels.  */
+  for (inner = loop->inner; inner; inner = inner->next)
+    {
+      int ilevel;
+
+      ilevel = flow_loop_level_compute (inner, depth + 1) + 1;
+
+      if (ilevel > level)
+	level = ilevel;
+    }
+  loop->level = level;
+  loop->depth = depth;
+  return level;
+}
+
+
+/* Compute the loop nesting depth and enclosed loop level for the loop
+   hierarchy tree specfied by LOOPS.  Return the maximum enclosed loop
+   level.  */
+static int 
+flow_loops_level_compute (loops)
+     struct loops *loops;
+{
+  return flow_loop_level_compute (loops->tree, 0);
+}
+
+
+/* Find all the natural loops in the function and save in LOOPS structure.
+   Return the number of natural loops found.  */
+int 
+flow_loops_find (loops)
+       struct loops *loops;
+{
+  int i;
+  int b;
+  int num_loops;
+  edge e;
+  sbitmap headers;
+  sbitmap *dom;
+  int *dfs_order;
+  
+  loops->num = 0;
+  loops->array = NULL;
+  loops->tree = NULL;
+  dfs_order = NULL;
+
+  /* Taking care of this degenerate case makes the rest of
+     this code simpler.  */
+  if (n_basic_blocks == 0)
+    return 0;
+
+  /* Compute the dominators.  */
+  dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
+  compute_flow_dominators (dom, NULL);
+
+  /* Count the number of loop edges (back edges).  This should be the
+     same as the number of natural loops.  */
+  num_loops = 0;
+  for (b = 0; b < n_basic_blocks; b++)
+    {
+      for (e = BASIC_BLOCK (b)->pred; e; e = e->pred_next)
+	{
+	  basic_block latch = e->src;
+	  
+	  /* Look for back edges where a predecessor is dominated
+	     by this block.  A natural loop has a single entry
+	     node (header) that dominates all the nodes in the
+	     loop.  It also has single back edge to the header
+	     from a latch node.  Note that multiple natural loops
+	     may share the same header.  */
+	  if (latch != ENTRY_BLOCK_PTR && TEST_BIT (dom[latch->index], b))
+	    num_loops++;
+	}
+    }
+  
+  if (num_loops)
+    {
+      /* Compute depth first search order of the CFG so that outer
+	 natural loops will be found before inner natural loops.  */
+      dfs_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
+      flow_depth_first_order_compute (dfs_order);
+
+      /* Allocate loop structures.  */
+      loops->array = (struct loop *)
+	xcalloc (num_loops, sizeof (struct loop));
+      
+      headers = sbitmap_alloc (n_basic_blocks);
+      sbitmap_zero (headers);
+
+      loops->shared_headers = sbitmap_alloc (n_basic_blocks);
+      sbitmap_zero (loops->shared_headers);
+
+      /* Find and record information about all the natural loops
+	 in the CFG.  */
+      num_loops = 0;
+      for (b = 0; b < n_basic_blocks; b++)
+	{
+	  basic_block header;
+
+	  /* Search the nodes of the CFG in DFS order that we can find
+	     outer loops first.  */
+	  header = BASIC_BLOCK (dfs_order[b]);
+	  
+	  /* Look for all the possible latch blocks for this header.  */
+	  for (e = header->pred; e; e = e->pred_next)
+	    {
+	      basic_block latch = e->src;
+	      
+	      /* Look for back edges where a predecessor is dominated
+		 by this block.  A natural loop has a single entry
+		 node (header) that dominates all the nodes in the
+		 loop.  It also has single back edge to the header
+		 from a latch node.  Note that multiple natural loops
+		 may share the same header.  */
+	      if (latch != ENTRY_BLOCK_PTR
+		  && TEST_BIT (dom[latch->index], header->index))
+		{
+		  struct loop *loop;
+		  
+		  loop = loops->array + num_loops;
+		  
+		  loop->header = header;
+		  loop->latch = latch;
+		  
+		  /* Keep track of blocks that are loop headers so
+		     that we can tell which loops should be merged.  */
+		  if (TEST_BIT (headers, header->index))
+		    SET_BIT (loops->shared_headers, header->index);
+		  SET_BIT (headers, header->index);
+		  
+		  /* Find nodes contained within the loop.  */
+		  loop->nodes = sbitmap_alloc (n_basic_blocks);
+		  loop->num_nodes =
+		    flow_loop_nodes_find (header, latch, loop->nodes);
+		  
+		  /* Find edges which exit the loop.  Note that a node
+		     may have several exit edges.  */
+		  loop->num_exits
+		    = flow_loop_exits_find (loop->nodes, &loop->exits);
+
+		  /* Look to see if the loop has a pre-header node.  */
+		  loop->pre_header 
+		    = flow_loop_pre_header_find (header, dom);
+
+		  num_loops++;
+		}
+	    }
+	}
+      
+      /* Natural loops with shared headers may either be disjoint or
+	 nested.  Disjoint loops with shared headers cannot be inner
+	 loops and should be merged.  For now just mark loops that share
+	 headers.  */
+      for (i = 0; i < num_loops; i++)
+	if (TEST_BIT (loops->shared_headers, loops->array[i].header->index))
+	  loops->array[i].shared = 1;
+
+      sbitmap_free (headers);
+    }
+
+  loops->num = num_loops;
+
+  /* Save CFG derived information to avoid recomputing it.  */
+  loops->cfg.dom = dom;
+  loops->cfg.dfs_order = dfs_order;
+
+  /* Build the loop hierarchy tree.  */
+  flow_loops_tree_build (loops);
+
+  /* Assign the loop nesting depth and enclosed loop level for each
+     loop.  */
+  flow_loops_level_compute (loops);
+
+  return num_loops;
+}
+
+
+/* Return non-zero if edge E enters header of LOOP from outside of LOOP.  */
+int
+flow_loop_outside_edge_p (loop, e)
+     const struct loop *loop;
+     edge e;
+{
+  if (e->dest != loop->header)
+    abort ();
+  return (e->src == ENTRY_BLOCK_PTR)
+    || ! TEST_BIT (loop->nodes, e->src->index);
+}
diff --git a/gcc/sbitmap.c b/gcc/sbitmap.c
index 4cc7c85f5c1..dece5e5ef25 100644
--- a/gcc/sbitmap.c
+++ b/gcc/sbitmap.c
@@ -265,6 +265,25 @@ sbitmap_a_or_b (dst, a, b)
     }
   return changed;
 }
+/* Return non-zero if A is a subset of B.  */
+
+int
+sbitmap_a_subset_b_p (a, b)
+     sbitmap a, b;
+{
+  int i;
+  sbitmap_ptr ap, bp;
+
+  ap = a->elms;
+  bp = b->elms;
+  for (i = 0; i < a->size; i++)
+    {
+      if ((*ap | *bp) != *bp)
+	return 0;
+      ap++; bp++;
+    }
+  return 1;
+}
 
 /* Set DST to be (A or (B and C)).
    Return non-zero if any change is made.  */
diff --git a/gcc/sbitmap.h b/gcc/sbitmap.h
index ca2f99730a5..1fc30041223 100644
--- a/gcc/sbitmap.h
+++ b/gcc/sbitmap.h
@@ -18,6 +18,9 @@ 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.  */
 
+#ifndef _SBITMAP_H
+#define _SBITMAP_H 1
+
 /* It's not clear yet whether using bitmap.[ch] will be a win.
    It should be straightforward to convert so for now we keep things simple
    while more important issues are dealt with.  */
@@ -109,6 +112,7 @@ extern int sbitmap_a_or_b_and_c PROTO ((sbitmap, sbitmap, sbitmap, sbitmap));
 extern int sbitmap_a_and_b_or_c PROTO ((sbitmap, sbitmap, sbitmap, sbitmap));
 extern int sbitmap_a_and_b PROTO ((sbitmap, sbitmap, sbitmap));
 extern int sbitmap_a_or_b PROTO ((sbitmap, sbitmap, sbitmap));
+extern int sbitmap_a_subset_b_p PROTO ((sbitmap, sbitmap));
 
 struct int_list;
 extern void sbitmap_intersect_of_predsucc PROTO ((sbitmap, sbitmap *,
@@ -129,3 +133,4 @@ extern void sbitmap_intersection_of_preds    PROTO ((sbitmap, sbitmap *, int));
 extern void sbitmap_union_of_succs	     PROTO ((sbitmap, sbitmap *, int));
 extern void sbitmap_union_of_preds	     PROTO ((sbitmap, sbitmap *, int));
 
+#endif /* _SBITMAP_H */