Makefile.in (cfg.o, [...]): New.

	* Makefile.in (cfg.o, cfganal.o, cfgloop.o, cfgbuild.o, cfgcleanup.o):
	New.
	* basic-block.h (flow_obstack, label_value_list,
	tail_recursion_label_list): Declare
	(tidy_fallthru_edges): Declare.
	(expunge_block, last_loop_beg_note): Delete.
	(can_fallthru, flow_nodes_print, flow_edge_list_print): Declare.
	* cfg.c: New file
	(basic_block_for_insn, label_value_list): Move from flow.c; make global.
	(n_basic_blocks, n_edges, basic_block_info, entry_exit_blocks,
	init_flow, clear_edges, can_delete_note_p, can_delete_label_p,
	flow_delete_insn, flow_delete_insn_chain, create_basic_block,
	expunge_block, flow_delete_block, compute_bb_for_insn,
	update_bb_for_insn, set_block_for_insn, set_block_for_new_insns,
	make_edge, remove_edge, redirect_edge_succ, redirect_edge_succ_nodup,
	redirect_edge_pred, split_block, marge_blocks_nomove, block_label,
	try_redirect_by_replacing_jump, last_loop_beg_note,
	redirect_edge_and_branch, redirect_edge_and_branch_force,
	tidy_fallthru_edge, tidy_fallthru_edges, back_edge_of_syntactic_loop_p,
	split_edge, insert_insn_on_edge, commit_one_edge_insertion,
	commit_edge_insertions, dump_flow_info, debug_flow_info,
	dump_edge_info, dump_bb, debug_bb, debug_bb_n, print_rtl_with_bb,
	verify_flow_info, purge_dead_edges, purge_all_dead_edges):
	Move here from flow.c
	* cfganal.c: New file.
	(forwarder_block_p, can_fallthru, mark_critical_edges,
	 mark_dfs_back_edges, need_fake_edge_p, flow_call_edges_add,
	 find_unreachable_blocks, create_edge_list, free_edge_list,
	 print_edge_list, verify_edge_list, find_edge_index, flow_nodes_print,
	 flow_edge_list_print, remove_fake_successors, remove_fake_edges,
	 add_noreturn_fake_exit_edges, connect_infinite_loops_to_exit,
	 flow_reverse_top_sort_order_compute, flow_depth_first_order_compute,
	 flow_dfs_compute_reverse_init, flow_dfs-compute_reverse_add_bb,
	 flow_dfs-compute_reverse_execute, flow_dfs_compute_reverse_finish);
	Move here from flow.c
	* cfgbuild.c: New file
	(count_basic_blocks, find_label_refs, make_label_edge, make_eh_edge,
	 make_edges, find_basic_blocks_1, find_basic_blocks,
	 find_sub_basic_blocks): Move here from flow.c
	* cfgcleanup.c: New file.
	(try_simplify_condjump, try_forward_edges, tail_recursion_label_p,
	 merge_blocks_move_predecessor_nojumps,
	 merge_blocks_move_successor_nojumps, merge_blocks,
	 flow_find_cross_jump, outgoing_edges_match, try_crossjump_to_edge,
	 try_crossjump_bb, try_optimize_cfg): Move here from flow.c
	(delete_unreachable_blocks, cleanup_cfg): Likewise; return true
	if succeeded.
	* cfgloop.c: New file
	(flow_loops_cfg_dump, flow_loop_nested_p, flow_loop_dump,
	 flow_loops_dump, flow_loops_free, flow_loop_entry_edges_find,
	 flow_loop_exit_edges_find, flow_loop_nodes_find,
	 flow_loop_pre_header_scan, flow_loop_pre_header_find,
	 flow_loop_tree_node_add, flow_loops_tree_build,
	 flow_loop_level_compute, flow_loops_level_compute, flow_loop_scan,
	 flow_loops_find, flow_loops_update, flow_loop_outside_edge_p):
	Move here from flow.c
	* flow.c: Remove everything moved elsewhere
	* output.h (cleanup_cfg): Return bool.

	* bb-reorder.c (reorder_block_def): Remove 'index'.
	(insert_intra_1): Add argument BB, set block for new note.
	(make_reorder_chain): Do not depdent on BB indexes.
	(make_reorder_chain_1): Do not use BB indexes.
	(label_for_bb): Likewise; set BB for new insn.
	(emit_jump_to_block_after): Likewise.
	(fixup_reoder_chain): Sanity check that all basic blocks
	are chained; verify newly created insn chain; remove
	undocnitional jump simplifying; Do not use BB indexes;
	properly initialize count and frequency information;
	dump reordered sequence.
	(insert_intra_bb_scope_notes): update call of insert_intra_1.
	(insert_inter_bb_scope_notes): Set block for new insn.
	(reorder_basic_blocks): Dump flow info before reoredering.

From-SVN: r45504

1 files changed, 854 insertions, 0 deletions

diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c
new file mode 100644
index 0000000..d8b5b4d
--- /dev/null
+++ b/gcc/cfgloop.c
@@ -0,0 +1,854 @@
+/* Natural loop discovery code for GNU compiler.
+   Copyright (C) 2000, 2001 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC 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.
+
+GCC 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 GCC; see the file COPYING.  If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA.  */
+
+#include "config.h"
+#include "system.h"
+#include "rtl.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
+
+static void flow_loops_cfg_dump		PARAMS ((const struct loops *,
+						 FILE *));
+static int flow_loop_nested_p		PARAMS ((struct loop *,
+						 struct loop *));
+static int flow_loop_entry_edges_find	PARAMS ((basic_block, const sbitmap,
+						 edge **));
+static int flow_loop_exit_edges_find	PARAMS ((const sbitmap, edge **));
+static int flow_loop_nodes_find	PARAMS ((basic_block, basic_block, sbitmap));
+static void flow_loop_pre_header_scan PARAMS ((struct loop *));
+static basic_block flow_loop_pre_header_find PARAMS ((basic_block,
+						      const sbitmap *));
+static void flow_loop_tree_node_add	PARAMS ((struct loop *, struct loop *));
+static void flow_loops_tree_build	PARAMS ((struct loops *));
+static int flow_loop_level_compute	PARAMS ((struct loop *, int));
+static int flow_loops_level_compute	PARAMS ((struct loops *));
+
+/* 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);
+    }
+  /* Dump the reverse completion node order.  */
+  if (loops->cfg.rc_order)
+    {
+      fputs (";; RC order: ", file);
+      for (i = 0; i < n_basic_blocks; i++)
+	fprintf (file, "%d ", loops->cfg.rc_order[i]);
+      fputs ("\n", file);
+    }
+}
+
+/* Return non-zero if the nodes of LOOP are a subset of OUTER.  */
+
+static 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 LOOP to the stream FILE
+   using auxiliary dump callback function LOOP_DUMP_AUX if non null.  */
+
+void
+flow_loop_dump (loop, file, loop_dump_aux, verbose)
+     const struct loop *loop;
+     FILE *file;
+     void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int));
+     int verbose;
+{
+  if (! loop || ! loop->header)
+    return;
+
+  if (loop->first->head && loop->last->end)
+    fprintf (file, ";;\n;; Loop %d (%d to %d):%s%s\n",
+	    loop->num, INSN_UID (loop->first->head),
+	    INSN_UID (loop->last->end),
+	    loop->shared ? " shared" : "",
+	    loop->invalid ? " invalid" : "");
+  else
+    fprintf (file, ";;\n;; Loop %d:%s%s\n", loop->num,
+	     loop->shared ? " shared" : "",
+	     loop->invalid ? " invalid" : "");
+
+  fprintf (file, ";;  header %d, latch %d, pre-header %d, first %d, last %d\n",
+	   loop->header->index, loop->latch->index,
+	   loop->pre_header ? loop->pre_header->index : -1,
+	   loop->first->index, loop->last->index);
+  fprintf (file, ";;  depth %d, level %d, outer %ld\n",
+	   loop->depth, loop->level,
+	   (long) (loop->outer ? loop->outer->num : -1));
+
+  if (loop->pre_header_edges)
+    flow_edge_list_print (";;  pre-header edges", loop->pre_header_edges,
+			  loop->num_pre_header_edges, file);
+  flow_edge_list_print (";;  entry edges", loop->entry_edges,
+			loop->num_entries, file);
+  fprintf (file, ";;  %d", loop->num_nodes);
+  flow_nodes_print (" nodes", loop->nodes, file);
+  flow_edge_list_print (";;  exit edges", loop->exit_edges,
+			loop->num_exits, file);
+  if (loop->exits_doms)
+    flow_nodes_print (";;  exit doms", loop->exits_doms, file);
+  if (loop_dump_aux)
+    loop_dump_aux (loop, file, verbose);
+}
+
+/* Dump the loop information specified by LOOPS to the stream FILE,
+   using auxiliary dump callback function LOOP_DUMP_AUX if non null.  */
+
+void
+flow_loops_dump (loops, file, loop_dump_aux, verbose)
+     const struct loops *loops;
+     FILE *file;
+     void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int));
+     int verbose;
+{
+  int i;
+  int num_loops;
+
+  num_loops = loops->num;
+  if (! num_loops || ! file)
+    return;
+
+  fprintf (file, ";; %d loops found, %d levels\n",
+	   num_loops, loops->levels);
+
+  for (i = 0; i < num_loops; i++)
+    {
+      struct loop *loop = &loops->array[i];
+
+      flow_loop_dump (loop, file, loop_dump_aux, verbose);
+
+      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,
+						   smaller ? oloop : loop);
+		  fprintf (file,
+			   ";; loop header %d shared by loops %d, %d %s\n",
+			   loop->header->index, i, j,
+			   disjoint ? "disjoint" : "nested");
+		}
+	    }
+	}
+    }
+
+  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->pre_header_edges)
+	    free (loop->pre_header_edges);
+	  if (loop->nodes)
+	    sbitmap_free (loop->nodes);
+	  if (loop->entry_edges)
+	    free (loop->entry_edges);
+	  if (loop->exit_edges)
+	    free (loop->exit_edges);
+	  if (loop->exits_doms)
+	    sbitmap_free (loop->exits_doms);
+	}
+      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);
+
+      if (loops->shared_headers)
+	sbitmap_free (loops->shared_headers);
+    }
+}
+
+/* Find the entry edges into the loop with header HEADER and nodes
+   NODES and store in ENTRY_EDGES array.  Return the number of entry
+   edges from the loop.  */
+
+static int
+flow_loop_entry_edges_find (header, nodes, entry_edges)
+     basic_block header;
+     const sbitmap nodes;
+     edge **entry_edges;
+{
+  edge e;
+  int num_entries;
+
+  *entry_edges = NULL;
+
+  num_entries = 0;
+  for (e = header->pred; e; e = e->pred_next)
+    {
+      basic_block src = e->src;
+
+      if (src == ENTRY_BLOCK_PTR || ! TEST_BIT (nodes, src->index))
+	num_entries++;
+    }
+
+  if (! num_entries)
+    abort ();
+
+  *entry_edges = (edge *) xmalloc (num_entries * sizeof (edge *));
+
+  num_entries = 0;
+  for (e = header->pred; e; e = e->pred_next)
+    {
+      basic_block src = e->src;
+
+      if (src == ENTRY_BLOCK_PTR || ! TEST_BIT (nodes, src->index))
+	(*entry_edges)[num_entries++] = e;
+    }
+
+  return num_entries;
+}
+
+/* Find the exit edges from the loop using the bitmap of loop nodes
+   NODES and store in EXIT_EDGES array.  Return the number of
+   exit edges from the loop.  */
+
+static int
+flow_loop_exit_edges_find (nodes, exit_edges)
+     const sbitmap nodes;
+     edge **exit_edges;
+{
+  edge e;
+  int node;
+  int num_exits;
+
+  *exit_edges = 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 ?????  A node can have one jumping edge and one fallthru
+     edge so only one of these can exit the loop.  */
+  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;
+
+  *exit_edges = (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))
+	  (*exit_edges)[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++;
+  header->loop_depth++;
+
+  /* Push the loop latch on to the stack.  */
+  if (! TEST_BIT (nodes, latch->index))
+    {
+      SET_BIT (nodes, latch->index);
+      latch->loop_depth++;
+      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);
+	      ancestor->loop_depth++;
+	      num_nodes++;
+	      stack[sp++] = ancestor;
+	    }
+	}
+    }
+  free (stack);
+  return num_nodes;
+}
+
+/* Find the root node of the loop pre-header extended basic block and
+   the edges along the trace from the root node to the loop header.  */
+
+static void
+flow_loop_pre_header_scan (loop)
+     struct loop *loop;
+{
+  int num = 0;
+  basic_block ebb;
+
+  loop->num_pre_header_edges = 0;
+
+  if (loop->num_entries != 1)
+     return;
+
+  ebb = loop->entry_edges[0]->src;
+
+  if (ebb != ENTRY_BLOCK_PTR)
+    {
+      edge e;
+
+      /* Count number of edges along trace from loop header to
+	 root of pre-header extended basic block.  Usually this is
+	 only one or two edges.  */
+      num++;
+      while (ebb->pred->src != ENTRY_BLOCK_PTR && ! ebb->pred->pred_next)
+	{
+	  ebb = ebb->pred->src;
+	  num++;
+	}
+
+      loop->pre_header_edges = (edge *) xmalloc (num * sizeof (edge *));
+      loop->num_pre_header_edges = num;
+
+      /* Store edges in order that they are followed.   The source
+	 of the first edge is the root node of the pre-header extended
+	 basic block and the destination of the last last edge is
+	 the loop header.  */
+      for (e = loop->entry_edges[0]; num; e = e->src->pred)
+	{
+	  loop->pre_header_edges[--num] = e;
+	}
+    }
+}
+
+/* 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 where PREVLOOP was the loop
+   previously added.  The insertion algorithm assumes that the loops
+   are added in the order found by a depth first search of the CFG.  */
+
+static void
+flow_loop_tree_node_add (prevloop, loop)
+     struct loop *prevloop;
+     struct loop *loop;
+{
+
+  if (flow_loop_nested_p (prevloop, loop))
+    {
+      prevloop->inner = loop;
+      loop->outer = prevloop;
+      return;
+    }
+
+  while (prevloop->outer)
+    {
+      if (flow_loop_nested_p (prevloop->outer, loop))
+	{
+	  prevloop->next = loop;
+	  loop->outer = prevloop->outer;
+	  return;
+	}
+      prevloop = prevloop->outer;
+    }
+
+  prevloop->next = loop;
+  loop->outer = NULL;
+}
+
+/* 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_root = &loops->array[0];
+  loops->tree_root->outer = loops->tree_root->inner = loops->tree_root->next = NULL;
+
+  /* Add the remaining loops to the tree.  */
+  for (i = 1; i < num_loops; i++)
+    flow_loop_tree_node_add (&loops->array[i - 1], &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 = 1;
+
+  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 (including
+     itself).  */
+  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;
+{
+  struct loop *loop;
+  int level;
+  int levels = 0;
+
+  /* Traverse all the outer level loops.  */
+  for (loop = loops->tree_root; loop; loop = loop->next)
+    {
+      level = flow_loop_level_compute (loop, 1);
+      if (level > levels)
+	levels = level;
+    }
+  return levels;
+}
+
+/* Scan a single natural loop specified by LOOP collecting information
+   about it specified by FLAGS.  */
+
+int
+flow_loop_scan (loops, loop, flags)
+     struct loops *loops;
+     struct loop *loop;
+     int flags;
+{
+  /* Determine prerequisites.  */
+  if ((flags & LOOP_EXITS_DOMS) && ! loop->exit_edges)
+    flags |= LOOP_EXIT_EDGES;
+
+  if (flags & LOOP_ENTRY_EDGES)
+    {
+      /* Find edges which enter the loop header.
+	 Note that the entry edges should only
+	 enter the header of a natural loop.  */
+      loop->num_entries
+	= flow_loop_entry_edges_find (loop->header,
+				      loop->nodes,
+				      &loop->entry_edges);
+    }
+
+  if (flags & LOOP_EXIT_EDGES)
+    {
+      /* Find edges which exit the loop.  */
+      loop->num_exits
+	= flow_loop_exit_edges_find (loop->nodes,
+				     &loop->exit_edges);
+    }
+
+  if (flags & LOOP_EXITS_DOMS)
+    {
+      int j;
+
+      /* Determine which loop nodes dominate all the exits
+	 of the loop.  */
+      loop->exits_doms = sbitmap_alloc (n_basic_blocks);
+      sbitmap_copy (loop->exits_doms, loop->nodes);
+      for (j = 0; j < loop->num_exits; j++)
+	sbitmap_a_and_b (loop->exits_doms, loop->exits_doms,
+			 loops->cfg.dom[loop->exit_edges[j]->src->index]);
+
+      /* The header of a natural loop must dominate
+	 all exits.  */
+      if (! TEST_BIT (loop->exits_doms, loop->header->index))
+	abort ();
+    }
+
+  if (flags & LOOP_PRE_HEADER)
+    {
+      /* Look to see if the loop has a pre-header node.  */
+      loop->pre_header
+	= flow_loop_pre_header_find (loop->header, loops->cfg.dom);
+
+      /* Find the blocks within the extended basic block of
+	 the loop pre-header.  */
+      flow_loop_pre_header_scan (loop);
+    }
+  return 1;
+}
+
+/* Find all the natural loops in the function and save in LOOPS structure
+   and recalculate loop_depth information in basic block structures.
+   FLAGS controls which loop information is collected.
+   Return the number of natural loops found.  */
+
+int
+flow_loops_find (loops, flags)
+     struct loops *loops;
+     int flags;
+{
+  int i;
+  int b;
+  int num_loops;
+  edge e;
+  sbitmap headers;
+  sbitmap *dom;
+  int *dfs_order;
+  int *rc_order;
+
+  /* This function cannot be repeatedly called with different
+     flags to build up the loop information.  The loop tree
+     must always be built if this function is called.  */
+  if (! (flags & LOOP_TREE))
+    abort ();
+
+  memset (loops, 0, sizeof (*loops));
+
+  /* Taking care of this degenerate case makes the rest of
+     this code simpler.  */
+  if (n_basic_blocks == 0)
+    return 0;
+
+  dfs_order = NULL;
+  rc_order = NULL;
+
+  /* Compute the dominators.  */
+  dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
+  calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
+
+  /* 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++)
+    {
+      basic_block header;
+
+      header = BASIC_BLOCK (b);
+      header->loop_depth = 0;
+
+      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 (b != header->index)
+	    abort ();
+
+	  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));
+      rc_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
+      flow_depth_first_order_compute (dfs_order, rc_order);
+
+      /* Save CFG derived information to avoid recomputing it.  */
+      loops->cfg.dom = dom;
+      loops->cfg.dfs_order = dfs_order;
+      loops->cfg.rc_order = rc_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 reverse completion order
+	     so that we can find outer loops first.  */
+	  header = BASIC_BLOCK (rc_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;
+		  loop->num = num_loops;
+
+		  num_loops++;
+		}
+	    }
+	}
+
+      for (i = 0; i < num_loops; i++)
+	{
+	  struct loop *loop = &loops->array[i];
+
+	  /* Keep track of blocks that are loop headers so
+	     that we can tell which loops should be merged.  */
+	  if (TEST_BIT (headers, loop->header->index))
+	    SET_BIT (loops->shared_headers, loop->header->index);
+	  SET_BIT (headers, loop->header->index);
+
+	  /* Find nodes contained within the loop.  */
+	  loop->nodes = sbitmap_alloc (n_basic_blocks);
+	  loop->num_nodes
+	    = flow_loop_nodes_find (loop->header, loop->latch, loop->nodes);
+
+	  /* Compute first and last blocks within the loop.
+	     These are often the same as the loop header and
+	     loop latch respectively, but this is not always
+	     the case.  */
+	  loop->first
+	    = BASIC_BLOCK (sbitmap_first_set_bit (loop->nodes));
+	  loop->last
+	    = BASIC_BLOCK (sbitmap_last_set_bit (loop->nodes));
+
+	  flow_loop_scan (loops, loop, flags);
+	}
+
+      /* 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);
+    }
+  else
+    {
+      sbitmap_vector_free (dom);
+    }
+
+  loops->num = num_loops;
+
+  /* Build the loop hierarchy tree.  */
+  flow_loops_tree_build (loops);
+
+  /* Assign the loop nesting depth and enclosed loop level for each
+     loop.  */
+  loops->levels = flow_loops_level_compute (loops);
+
+  return num_loops;
+}
+
+/* Update the information regarding the loops in the CFG
+   specified by LOOPS.  */
+int
+flow_loops_update (loops, flags)
+     struct loops *loops;
+     int flags;
+{
+  /* One day we may want to update the current loop data.  For now
+     throw away the old stuff and rebuild what we need.  */
+  if (loops->array)
+    flow_loops_free (loops);
+
+  return flow_loops_find (loops, flags);
+}
+
+/* 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);
+}