* 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.


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

1 files changed, 1074 insertions, 0 deletions

diff --git a/gcc/cfganal.c b/gcc/cfganal.c
new file mode 100644
index 00000000000..96a20b8f3c3
--- /dev/null
+++ b/gcc/cfganal.c
@@ -0,0 +1,1074 @@
+/* Control flow graph analysis code for GNU compiler.
+   Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
+   1999, 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.  */
+
+/* This file contains various simple utilities to analyze the CFG.  */
+#include "config.h"
+#include "system.h"
+#include "rtl.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
+#include "toplev.h"
+
+#include "obstack.h"
+
+/* Store the data structures necessary for depth-first search.  */
+struct depth_first_search_dsS {
+  /* stack for backtracking during the algorithm */
+  basic_block *stack;
+
+  /* number of edges in the stack.  That is, positions 0, ..., sp-1
+     have edges.  */
+  unsigned int sp;
+
+  /* record of basic blocks already seen by depth-first search */
+  sbitmap visited_blocks;
+};
+typedef struct depth_first_search_dsS *depth_first_search_ds;
+
+static void flow_dfs_compute_reverse_init
+  PARAMS ((depth_first_search_ds));
+static void flow_dfs_compute_reverse_add_bb
+  PARAMS ((depth_first_search_ds, basic_block));
+static basic_block flow_dfs_compute_reverse_execute
+  PARAMS ((depth_first_search_ds));
+static void flow_dfs_compute_reverse_finish
+  PARAMS ((depth_first_search_ds));
+static void remove_fake_successors	PARAMS ((basic_block));
+static bool need_fake_edge_p		PARAMS ((rtx));
+
+/* Return true if the block has no effect and only forwards control flow to
+   its single destination.  */
+bool
+forwarder_block_p (bb)
+     basic_block bb;
+{
+  rtx insn = bb->head;
+  if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR
+      || !bb->succ || bb->succ->succ_next)
+    return false;
+
+  while (insn != bb->end)
+    {
+      if (active_insn_p (insn))
+	return false;
+      insn = NEXT_INSN (insn);
+    }
+  return (!active_insn_p (insn)
+	  || (GET_CODE (insn) == JUMP_INSN && onlyjump_p (insn)));
+}
+
+/* Return nonzero if we can reach target from src by falling trought.  */
+bool
+can_fallthru (src, target)
+     basic_block src, target;
+{
+  rtx insn = src->end;
+  rtx insn2 = target->head;
+
+  if (src->index + 1 == target->index && !active_insn_p (insn2))
+    insn2 = next_active_insn (insn2);
+  /* ??? Later we may add code to move jump tables offline.  */
+  return next_active_insn (insn) == insn2;
+}
+
+/* Identify critical edges and set the bits appropriately.  */
+
+void
+mark_critical_edges ()
+{
+  int i, n = n_basic_blocks;
+  basic_block bb;
+
+  /* We begin with the entry block.  This is not terribly important now,
+     but could be if a front end (Fortran) implemented alternate entry
+     points.  */
+  bb = ENTRY_BLOCK_PTR;
+  i = -1;
+
+  while (1)
+    {
+      edge e;
+
+      /* (1) Critical edges must have a source with multiple successors.  */
+      if (bb->succ && bb->succ->succ_next)
+	{
+	  for (e = bb->succ; e; e = e->succ_next)
+	    {
+	      /* (2) Critical edges must have a destination with multiple
+		 predecessors.  Note that we know there is at least one
+		 predecessor -- the edge we followed to get here.  */
+	      if (e->dest->pred->pred_next)
+		e->flags |= EDGE_CRITICAL;
+	      else
+		e->flags &= ~EDGE_CRITICAL;
+	    }
+	}
+      else
+	{
+	  for (e = bb->succ; e; e = e->succ_next)
+	    e->flags &= ~EDGE_CRITICAL;
+	}
+
+      if (++i >= n)
+	break;
+      bb = BASIC_BLOCK (i);
+    }
+}
+
+/* Mark the back edges in DFS traversal.
+   Return non-zero if a loop (natural or otherwise) is present.
+   Inspired by Depth_First_Search_PP described in:
+
+     Advanced Compiler Design and Implementation
+     Steven Muchnick
+     Morgan Kaufmann, 1997
+
+   and heavily borrowed from flow_depth_first_order_compute.  */
+
+bool
+mark_dfs_back_edges ()
+{
+  edge *stack;
+  int *pre;
+  int *post;
+  int sp;
+  int prenum = 1;
+  int postnum = 1;
+  sbitmap visited;
+  bool found = false;
+
+  /* Allocate the preorder and postorder number arrays.  */
+  pre = (int *) xcalloc (n_basic_blocks, sizeof (int));
+  post = (int *) xcalloc (n_basic_blocks, sizeof (int));
+
+  /* Allocate stack for back-tracking up CFG.  */
+  stack = (edge *) xmalloc ((n_basic_blocks + 1) * 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);
+
+  /* Push the first edge on to the stack.  */
+  stack[sp++] = ENTRY_BLOCK_PTR->succ;
+
+  while (sp)
+    {
+      edge e;
+      basic_block src;
+      basic_block dest;
+
+      /* Look at the edge on the top of the stack.  */
+      e = stack[sp - 1];
+      src = e->src;
+      dest = e->dest;
+      e->flags &= ~EDGE_DFS_BACK;
+
+      /* Check if the edge destination has been visited yet.  */
+      if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
+	{
+	  /* Mark that we have visited the destination.  */
+	  SET_BIT (visited, dest->index);
+
+	  pre[dest->index] = prenum++;
+
+	  if (dest->succ)
+	    {
+	      /* Since the DEST node has been visited for the first
+		 time, check its successors.  */
+	      stack[sp++] = dest->succ;
+	    }
+	  else
+	    post[dest->index] = postnum++;
+	}
+      else
+	{
+	  if (dest != EXIT_BLOCK_PTR && src != ENTRY_BLOCK_PTR
+	      && pre[src->index] >= pre[dest->index]
+	      && post[dest->index] == 0)
+	    e->flags |= EDGE_DFS_BACK, found = true;
+
+	  if (! e->succ_next && src != ENTRY_BLOCK_PTR)
+	    post[src->index] = postnum++;
+
+	  if (e->succ_next)
+	    stack[sp - 1] = e->succ_next;
+	  else
+	    sp--;
+	}
+    }
+
+  free (pre);
+  free (post);
+  free (stack);
+  sbitmap_free (visited);
+
+  return found;
+}
+
+/* Return true if we need to add fake edge to exit.
+   Helper function for the flow_call_edges_add.  */
+
+static bool
+need_fake_edge_p (insn)
+     rtx insn;
+{
+  if (!INSN_P (insn))
+    return false;
+
+  if ((GET_CODE (insn) == CALL_INSN
+       && !SIBLING_CALL_P (insn)
+       && !find_reg_note (insn, REG_NORETURN, NULL)
+       && !find_reg_note (insn, REG_ALWAYS_RETURN, NULL)
+       && !CONST_OR_PURE_CALL_P (insn)))
+    return true;
+
+  return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS
+	   && MEM_VOLATILE_P (PATTERN (insn)))
+	  || (GET_CODE (PATTERN (insn)) == PARALLEL
+	      && asm_noperands (insn) != -1
+	      && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0)))
+	  || GET_CODE (PATTERN (insn)) == ASM_INPUT);
+}
+
+/* Add fake edges to the function exit for any non constant and non noreturn
+   calls, volatile inline assembly in the bitmap of blocks specified by
+   BLOCKS or to the whole CFG if BLOCKS is zero.  Return the nuber of blocks
+   that were split.
+
+   The goal is to expose cases in which entering a basic block does not imply
+   that all subsequent instructions must be executed.  */
+
+int
+flow_call_edges_add (blocks)
+     sbitmap blocks;
+{
+  int i;
+  int blocks_split = 0;
+  int bb_num = 0;
+  basic_block *bbs;
+  bool check_last_block = false;
+
+  /* Map bb indicies into basic block pointers since split_block
+     will renumber the basic blocks.  */
+
+  bbs = xmalloc (n_basic_blocks * sizeof (*bbs));
+
+  if (! blocks)
+    {
+      for (i = 0; i < n_basic_blocks; i++)
+	bbs[bb_num++] = BASIC_BLOCK (i);
+      check_last_block = true;
+    }
+  else
+    {
+      EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i,
+      {
+	bbs[bb_num++] = BASIC_BLOCK (i);
+	if (i == n_basic_blocks - 1)
+	  check_last_block = true;
+      });
+    }
+
+  /* In the last basic block, before epilogue generation, there will be
+     a fallthru edge to EXIT.  Special care is required if the last insn
+     of the last basic block is a call because make_edge folds duplicate
+     edges, which would result in the fallthru edge also being marked
+     fake, which would result in the fallthru edge being removed by
+     remove_fake_edges, which would result in an invalid CFG.
+
+     Moreover, we can't elide the outgoing fake edge, since the block
+     profiler needs to take this into account in order to solve the minimal
+     spanning tree in the case that the call doesn't return.
+
+     Handle this by adding a dummy instruction in a new last basic block.  */
+  if (check_last_block
+      && need_fake_edge_p (BASIC_BLOCK (n_basic_blocks - 1)->end))
+    {
+       edge e;
+       for (e = BASIC_BLOCK (n_basic_blocks - 1)->succ; e; e = e->succ_next)
+	 if (e->dest == EXIT_BLOCK_PTR)
+	    break;
+       insert_insn_on_edge (gen_rtx_USE (VOIDmode, const0_rtx), e);
+       commit_edge_insertions ();
+    }
+
+
+  /* Now add fake edges to the function exit for any non constant
+     calls since there is no way that we can determine if they will
+     return or not...  */
+
+  for (i = 0; i < bb_num; i++)
+    {
+      basic_block bb = bbs[i];
+      rtx insn;
+      rtx prev_insn;
+
+      for (insn = bb->end; ; insn = prev_insn)
+	{
+	  prev_insn = PREV_INSN (insn);
+	  if (need_fake_edge_p (insn))
+	    {
+	      edge e;
+
+	      /* The above condition should be enought to verify that there is
+		 no edge to the exit block in CFG already.  Calling make_edge in
+		 such case would make us to mark that edge as fake and remove it
+		 later.  */
+#ifdef ENABLE_CHECKING
+	      if (insn == bb->end)
+		for (e = bb->succ; e; e = e->succ_next)
+		  if (e->dest == EXIT_BLOCK_PTR)
+		    abort ();
+#endif
+
+	      /* Note that the following may create a new basic block
+		 and renumber the existing basic blocks.  */
+	      e = split_block (bb, insn);
+	      if (e)
+		blocks_split++;
+
+	      make_edge (NULL, bb, EXIT_BLOCK_PTR, EDGE_FAKE);
+	    }
+	  if (insn == bb->head)
+	    break;
+	}
+    }
+
+  if (blocks_split)
+    verify_flow_info ();
+
+  free (bbs);
+  return blocks_split;
+}
+/* Find unreachable blocks.  An unreachable block will have 0 in
+   the reachable bit in block->flags.  A non-zero value indicates the
+   block is reachable.  */
+
+void
+find_unreachable_blocks ()
+{
+  edge e;
+  int i, n;
+  basic_block *tos, *worklist;
+
+  n = n_basic_blocks;
+  tos = worklist = (basic_block *) xmalloc (sizeof (basic_block) * n);
+
+  /* Clear all the reachability flags.  */
+
+  for (i = 0; i < n; ++i)
+    BASIC_BLOCK (i)->flags &= ~BB_REACHABLE;
+
+  /* Add our starting points to the worklist.  Almost always there will
+     be only one.  It isn't inconcievable that we might one day directly
+     support Fortran alternate entry points.  */
+
+  for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
+    {
+      *tos++ = e->dest;
+
+      /* Mark the block reachable.  */
+      e->dest->flags |= BB_REACHABLE;
+    }
+
+  /* Iterate: find everything reachable from what we've already seen.  */
+
+  while (tos != worklist)
+    {
+      basic_block b = *--tos;
+
+      for (e = b->succ; e; e = e->succ_next)
+	if (!(e->dest->flags & BB_REACHABLE))
+	  {
+	    *tos++ = e->dest;
+	    e->dest->flags |= BB_REACHABLE;
+	  }
+    }
+
+  free (worklist);
+}
+
+/* Functions to access an edge list with a vector representation.
+   Enough data is kept such that given an index number, the
+   pred and succ that edge represents can be determined, or
+   given a pred and a succ, its index number can be returned.
+   This allows algorithms which consume a lot of memory to
+   represent the normally full matrix of edge (pred,succ) with a
+   single indexed vector,  edge (EDGE_INDEX (pred, succ)), with no
+   wasted space in the client code due to sparse flow graphs.  */
+
+/* This functions initializes the edge list. Basically the entire
+   flowgraph is processed, and all edges are assigned a number,
+   and the data structure is filled in.  */
+
+struct edge_list *
+create_edge_list ()
+{
+  struct edge_list *elist;
+  edge e;
+  int num_edges;
+  int x;
+  int block_count;
+
+  block_count = n_basic_blocks + 2;   /* Include the entry and exit blocks.  */
+
+  num_edges = 0;
+
+  /* Determine the number of edges in the flow graph by counting successor
+     edges on each basic block.  */
+  for (x = 0; x < n_basic_blocks; x++)
+    {
+      basic_block bb = BASIC_BLOCK (x);
+
+      for (e = bb->succ; e; e = e->succ_next)
+	num_edges++;
+    }
+  /* Don't forget successors of the entry block.  */
+  for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
+    num_edges++;
+
+  elist = (struct edge_list *) xmalloc (sizeof (struct edge_list));
+  elist->num_blocks = block_count;
+  elist->num_edges = num_edges;
+  elist->index_to_edge = (edge *) xmalloc (sizeof (edge) * num_edges);
+
+  num_edges = 0;
+
+  /* Follow successors of the entry block, and register these edges.  */
+  for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
+    {
+      elist->index_to_edge[num_edges] = e;
+      num_edges++;
+    }
+
+  for (x = 0; x < n_basic_blocks; x++)
+    {
+      basic_block bb = BASIC_BLOCK (x);
+
+      /* Follow all successors of blocks, and register these edges.  */
+      for (e = bb->succ; e; e = e->succ_next)
+	{
+	  elist->index_to_edge[num_edges] = e;
+	  num_edges++;
+	}
+    }
+  return elist;
+}
+
+/* This function free's memory associated with an edge list.  */
+
+void
+free_edge_list (elist)
+     struct edge_list *elist;
+{
+  if (elist)
+    {
+      free (elist->index_to_edge);
+      free (elist);
+    }
+}
+
+/* This function provides debug output showing an edge list.  */
+
+void
+print_edge_list (f, elist)
+     FILE *f;
+     struct edge_list *elist;
+{
+  int x;
+  fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
+	   elist->num_blocks - 2, elist->num_edges);
+
+  for (x = 0; x < elist->num_edges; x++)
+    {
+      fprintf (f, " %-4d - edge(", x);
+      if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR)
+	fprintf (f, "entry,");
+      else
+	fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index);
+
+      if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR)
+	fprintf (f, "exit)\n");
+      else
+	fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index);
+    }
+}
+
+/* This function provides an internal consistency check of an edge list,
+   verifying that all edges are present, and that there are no
+   extra edges.  */
+
+void
+verify_edge_list (f, elist)
+     FILE *f;
+     struct edge_list *elist;
+{
+  int x, pred, succ, index;
+  edge e;
+
+  for (x = 0; x < n_basic_blocks; x++)
+    {
+      basic_block bb = BASIC_BLOCK (x);
+
+      for (e = bb->succ; e; e = e->succ_next)
+	{
+	  pred = e->src->index;
+	  succ = e->dest->index;
+	  index = EDGE_INDEX (elist, e->src, e->dest);
+	  if (index == EDGE_INDEX_NO_EDGE)
+	    {
+	      fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ);
+	      continue;
+	    }
+	  if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
+	    fprintf (f, "*p* Pred for index %d should be %d not %d\n",
+		     index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
+	  if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
+	    fprintf (f, "*p* Succ for index %d should be %d not %d\n",
+		     index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
+	}
+    }
+  for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
+    {
+      pred = e->src->index;
+      succ = e->dest->index;
+      index = EDGE_INDEX (elist, e->src, e->dest);
+      if (index == EDGE_INDEX_NO_EDGE)
+	{
+	  fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ);
+	  continue;
+	}
+      if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
+	fprintf (f, "*p* Pred for index %d should be %d not %d\n",
+		 index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
+      if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
+	fprintf (f, "*p* Succ for index %d should be %d not %d\n",
+		 index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
+    }
+  /* We've verified that all the edges are in the list, no lets make sure
+     there are no spurious edges in the list.  */
+
+  for (pred = 0; pred < n_basic_blocks; pred++)
+    for (succ = 0; succ < n_basic_blocks; succ++)
+      {
+	basic_block p = BASIC_BLOCK (pred);
+	basic_block s = BASIC_BLOCK (succ);
+
+	int found_edge = 0;
+
+	for (e = p->succ; e; e = e->succ_next)
+	  if (e->dest == s)
+	    {
+	      found_edge = 1;
+	      break;
+	    }
+	for (e = s->pred; e; e = e->pred_next)
+	  if (e->src == p)
+	    {
+	      found_edge = 1;
+	      break;
+	    }
+	if (EDGE_INDEX (elist, BASIC_BLOCK (pred), BASIC_BLOCK (succ))
+	    == EDGE_INDEX_NO_EDGE && found_edge != 0)
+	  fprintf (f, "*** Edge (%d, %d) appears to not have an index\n",
+		   pred, succ);
+	if (EDGE_INDEX (elist, BASIC_BLOCK (pred), BASIC_BLOCK (succ))
+	    != EDGE_INDEX_NO_EDGE && found_edge == 0)
+	  fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
+		   pred, succ, EDGE_INDEX (elist, BASIC_BLOCK (pred),
+					   BASIC_BLOCK (succ)));
+      }
+  for (succ = 0; succ < n_basic_blocks; succ++)
+    {
+      basic_block p = ENTRY_BLOCK_PTR;
+      basic_block s = BASIC_BLOCK (succ);
+
+      int found_edge = 0;
+
+      for (e = p->succ; e; e = e->succ_next)
+	if (e->dest == s)
+	  {
+	    found_edge = 1;
+	    break;
+	  }
+      for (e = s->pred; e; e = e->pred_next)
+	if (e->src == p)
+	  {
+	    found_edge = 1;
+	    break;
+	  }
+      if (EDGE_INDEX (elist, ENTRY_BLOCK_PTR, BASIC_BLOCK (succ))
+	  == EDGE_INDEX_NO_EDGE && found_edge != 0)
+	fprintf (f, "*** Edge (entry, %d) appears to not have an index\n",
+		 succ);
+      if (EDGE_INDEX (elist, ENTRY_BLOCK_PTR, BASIC_BLOCK (succ))
+	  != EDGE_INDEX_NO_EDGE && found_edge == 0)
+	fprintf (f, "*** Edge (entry, %d) has index %d, but no edge exists\n",
+		 succ, EDGE_INDEX (elist, ENTRY_BLOCK_PTR,
+				   BASIC_BLOCK (succ)));
+    }
+  for (pred = 0; pred < n_basic_blocks; pred++)
+    {
+      basic_block p = BASIC_BLOCK (pred);
+      basic_block s = EXIT_BLOCK_PTR;
+
+      int found_edge = 0;
+
+      for (e = p->succ; e; e = e->succ_next)
+	if (e->dest == s)
+	  {
+	    found_edge = 1;
+	    break;
+	  }
+      for (e = s->pred; e; e = e->pred_next)
+	if (e->src == p)
+	  {
+	    found_edge = 1;
+	    break;
+	  }
+      if (EDGE_INDEX (elist, BASIC_BLOCK (pred), EXIT_BLOCK_PTR)
+	  == EDGE_INDEX_NO_EDGE && found_edge != 0)
+	fprintf (f, "*** Edge (%d, exit) appears to not have an index\n",
+		 pred);
+      if (EDGE_INDEX (elist, BASIC_BLOCK (pred), EXIT_BLOCK_PTR)
+	  != EDGE_INDEX_NO_EDGE && found_edge == 0)
+	fprintf (f, "*** Edge (%d, exit) has index %d, but no edge exists\n",
+		 pred, EDGE_INDEX (elist, BASIC_BLOCK (pred),
+				   EXIT_BLOCK_PTR));
+    }
+}
+
+/* This routine will determine what, if any, edge there is between
+   a specified predecessor and successor.  */
+
+int
+find_edge_index (edge_list, pred, succ)
+     struct edge_list *edge_list;
+     basic_block pred, succ;
+{
+  int x;
+  for (x = 0; x < NUM_EDGES (edge_list); x++)
+    {
+      if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
+	  && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
+	return x;
+    }
+  return (EDGE_INDEX_NO_EDGE);
+}
+
+/* Dump the list of basic blocks in the bitmap NODES.  */
+
+void
+flow_nodes_print (str, nodes, file)
+     const char *str;
+     const sbitmap nodes;
+     FILE *file;
+{
+  int node;
+
+  if (! nodes)
+    return;
+
+  fprintf (file, "%s { ", str);
+  EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {fprintf (file, "%d ", node);});
+  fputs ("}\n", file);
+}
+
+/* Dump the list of edges in the array EDGE_LIST.  */
+
+void
+flow_edge_list_print (str, edge_list, num_edges, file)
+     const char *str;
+     const edge *edge_list;
+     int num_edges;
+     FILE *file;
+{
+  int i;
+
+  if (! edge_list)
+    return;
+
+  fprintf (file, "%s { ", str);
+  for (i = 0; i < num_edges; i++)
+    fprintf (file, "%d->%d ", edge_list[i]->src->index,
+	     edge_list[i]->dest->index);
+  fputs ("}\n", file);
+}
+
+
+/* This routine will remove any fake successor edges for a basic block.
+   When the edge is removed, it is also removed from whatever predecessor
+   list it is in.  */
+
+static void
+remove_fake_successors (bb)
+     basic_block bb;
+{
+  edge e;
+  for (e = bb->succ; e;)
+    {
+      edge tmp = e;
+      e = e->succ_next;
+      if ((tmp->flags & EDGE_FAKE) == EDGE_FAKE)
+	remove_edge (tmp);
+    }
+}
+
+/* This routine will remove all fake edges from the flow graph.  If
+   we remove all fake successors, it will automatically remove all
+   fake predecessors.  */
+
+void
+remove_fake_edges ()
+{
+  int x;
+
+  for (x = 0; x < n_basic_blocks; x++)
+    remove_fake_successors (BASIC_BLOCK (x));
+
+  /* We've handled all successors except the entry block's.  */
+  remove_fake_successors (ENTRY_BLOCK_PTR);
+}
+
+/* This function will add a fake edge between any block which has no
+   successors, and the exit block. Some data flow equations require these
+   edges to exist.  */
+
+void
+add_noreturn_fake_exit_edges ()
+{
+  int x;
+
+  for (x = 0; x < n_basic_blocks; x++)
+    if (BASIC_BLOCK (x)->succ == NULL)
+      make_edge (NULL, BASIC_BLOCK (x), EXIT_BLOCK_PTR, EDGE_FAKE);
+}
+
+/* This function adds a fake edge between any infinite loops to the
+   exit block.  Some optimizations require a path from each node to
+   the exit node.
+
+   See also Morgan, Figure 3.10, pp. 82-83.
+
+   The current implementation is ugly, not attempting to minimize the
+   number of inserted fake edges.  To reduce the number of fake edges
+   to insert, add fake edges from _innermost_ loops containing only
+   nodes not reachable from the exit block.  */
+
+void
+connect_infinite_loops_to_exit ()
+{
+  basic_block unvisited_block;
+
+  /* Perform depth-first search in the reverse graph to find nodes
+     reachable from the exit block.  */
+  struct depth_first_search_dsS dfs_ds;
+
+  flow_dfs_compute_reverse_init (&dfs_ds);
+  flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR);
+
+  /* Repeatedly add fake edges, updating the unreachable nodes.  */
+  while (1)
+    {
+      unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds);
+      if (!unvisited_block)
+	break;
+      make_edge (NULL, unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE);
+      flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block);
+    }
+
+  flow_dfs_compute_reverse_finish (&dfs_ds);
+
+  return;
+}
+
+/* Compute reverse top sort order */
+void
+flow_reverse_top_sort_order_compute (rts_order)
+     int *rts_order;
+{
+  edge *stack;
+  int sp;
+  int postnum = 0;
+  sbitmap visited;
+
+  /* Allocate stack for back-tracking up CFG.  */
+  stack = (edge *) xmalloc ((n_basic_blocks + 1) * 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);
+
+  /* Push the first edge on to the stack.  */
+  stack[sp++] = ENTRY_BLOCK_PTR->succ;
+
+  while (sp)
+    {
+      edge e;
+      basic_block src;
+      basic_block dest;
+
+      /* Look at the edge on the top of the stack.  */
+      e = stack[sp - 1];
+      src = e->src;
+      dest = e->dest;
+
+      /* Check if the edge destination has been visited yet.  */
+      if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
+	{
+	  /* Mark that we have visited the destination.  */
+	  SET_BIT (visited, dest->index);
+
+	  if (dest->succ)
+	    {
+	      /* Since the DEST node has been visited for the first
+		 time, check its successors.  */
+	      stack[sp++] = dest->succ;
+	    }
+	  else
+	    rts_order[postnum++] = dest->index;
+	}
+      else
+	{
+	  if (! e->succ_next && src != ENTRY_BLOCK_PTR)
+	   rts_order[postnum++] = src->index;
+
+	  if (e->succ_next)
+	    stack[sp - 1] = e->succ_next;
+	  else
+	    sp--;
+	}
+    }
+
+  free (stack);
+  sbitmap_free (visited);
+}
+
+/* Compute the depth first search order and store in the array
+  DFS_ORDER if non-zero, marking the nodes visited in VISITED.  If
+  RC_ORDER is non-zero, return the reverse completion number for each
+  node.  Returns the number of nodes visited.  A depth first search
+  tries to get as far away from the starting point as quickly as
+  possible.  */
+
+int
+flow_depth_first_order_compute (dfs_order, rc_order)
+     int *dfs_order;
+     int *rc_order;
+{
+  edge *stack;
+  int sp;
+  int dfsnum = 0;
+  int rcnum = n_basic_blocks - 1;
+  sbitmap visited;
+
+  /* Allocate stack for back-tracking up CFG.  */
+  stack = (edge *) xmalloc ((n_basic_blocks + 1) * 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);
+
+  /* Push the first edge on to the stack.  */
+  stack[sp++] = ENTRY_BLOCK_PTR->succ;
+
+  while (sp)
+    {
+      edge e;
+      basic_block src;
+      basic_block dest;
+
+      /* Look at the edge on the top of the stack.  */
+      e = stack[sp - 1];
+      src = e->src;
+      dest = e->dest;
+
+      /* Check if the edge destination has been visited yet.  */
+      if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
+	{
+	  /* Mark that we have visited the destination.  */
+	  SET_BIT (visited, dest->index);
+
+	  if (dfs_order)
+	    dfs_order[dfsnum++] = dest->index;
+
+	  if (dest->succ)
+	    {
+	      /* Since the DEST node has been visited for the first
+		 time, check its successors.  */
+	      stack[sp++] = dest->succ;
+	    }
+	  else
+	    {
+	      /* There are no successors for the DEST node so assign
+		 its reverse completion number.  */
+	      if (rc_order)
+		rc_order[rcnum--] = dest->index;
+	    }
+	}
+      else
+	{
+	  if (! e->succ_next && src != ENTRY_BLOCK_PTR)
+	    {
+	      /* There are no more successors for the SRC node
+		 so assign its reverse completion number.  */
+	      if (rc_order)
+		rc_order[rcnum--] = src->index;
+	    }
+
+	  if (e->succ_next)
+	    stack[sp - 1] = e->succ_next;
+	  else
+	    sp--;
+	}
+    }
+
+  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;
+}
+
+/* Compute the depth first search order on the _reverse_ graph and
+   store in the array DFS_ORDER, marking the nodes visited in VISITED.
+   Returns the number of nodes visited.
+
+   The computation is split into three pieces:
+
+   flow_dfs_compute_reverse_init () creates the necessary data
+   structures.
+
+   flow_dfs_compute_reverse_add_bb () adds a basic block to the data
+   structures.  The block will start the search.
+
+   flow_dfs_compute_reverse_execute () continues (or starts) the
+   search using the block on the top of the stack, stopping when the
+   stack is empty.
+
+   flow_dfs_compute_reverse_finish () destroys the necessary data
+   structures.
+
+   Thus, the user will probably call ..._init(), call ..._add_bb() to
+   add a beginning basic block to the stack, call ..._execute(),
+   possibly add another bb to the stack and again call ..._execute(),
+   ..., and finally call _finish().  */
+
+/* Initialize the data structures used for depth-first search on the
+   reverse graph.  If INITIALIZE_STACK is nonzero, the exit block is
+   added to the basic block stack.  DATA is the current depth-first
+   search context.  If INITIALIZE_STACK is non-zero, there is an
+   element on the stack.  */
+
+static void
+flow_dfs_compute_reverse_init (data)
+     depth_first_search_ds data;
+{
+  /* Allocate stack for back-tracking up CFG.  */
+  data->stack =
+    (basic_block *) xmalloc ((n_basic_blocks - (INVALID_BLOCK + 1))
+			     * sizeof (basic_block));
+  data->sp = 0;
+
+  /* Allocate bitmap to track nodes that have been visited.  */
+  data->visited_blocks = sbitmap_alloc (n_basic_blocks - (INVALID_BLOCK + 1));
+
+  /* None of the nodes in the CFG have been visited yet.  */
+  sbitmap_zero (data->visited_blocks);
+
+  return;
+}
+
+/* Add the specified basic block to the top of the dfs data
+   structures.  When the search continues, it will start at the
+   block.  */
+
+static void
+flow_dfs_compute_reverse_add_bb (data, bb)
+     depth_first_search_ds data;
+     basic_block bb;
+{
+  data->stack[data->sp++] = bb;
+  return;
+}
+
+/* Continue the depth-first search through the reverse graph starting
+   with the block at the stack's top and ending when the stack is
+   empty.  Visited nodes are marked.  Returns an unvisited basic
+   block, or NULL if there is none available.  */
+
+static basic_block
+flow_dfs_compute_reverse_execute (data)
+     depth_first_search_ds data;
+{
+  basic_block bb;
+  edge e;
+  int i;
+
+  while (data->sp > 0)
+    {
+      bb = data->stack[--data->sp];
+
+      /* Mark that we have visited this node.  */
+      if (!TEST_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1)))
+	{
+	  SET_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1));
+
+	  /* Perform depth-first search on adjacent vertices.  */
+	  for (e = bb->pred; e; e = e->pred_next)
+	    flow_dfs_compute_reverse_add_bb (data, e->src);
+	}
+    }
+
+  /* Determine if there are unvisited basic blocks.  */
+  for (i = n_basic_blocks - (INVALID_BLOCK + 1); --i >= 0;)
+    if (!TEST_BIT (data->visited_blocks, i))
+      return BASIC_BLOCK (i + (INVALID_BLOCK + 1));
+  return NULL;
+}
+
+/* Destroy the data structures needed for depth-first search on the
+   reverse graph.  */
+
+static void
+flow_dfs_compute_reverse_finish (data)
+     depth_first_search_ds data;
+{
+  free (data->stack);
+  sbitmap_free (data->visited_blocks);
+  return;
+}