Enlist the FreeBSD-CURRENT users as testers of what is to become Gcc 3.1.0.

These bits are taken from the FSF anoncvs repo on 1-Feb-2002 08:20 PST.

1 files changed, 798 insertions, 1302 deletions

diff --git a/contrib/gcc/profile.c b/contrib/gcc/profile.c
index 17923c5..0c4acdf 100644
--- a/contrib/gcc/profile.c
+++ b/contrib/gcc/profile.c
@@ -1,29 +1,26 @@
-/* Calculate branch probabilities, and basic block execution counts. 
-   Copyright (C) 1990, 91-94, 96-98, 1999 Free Software Foundation, Inc.
+/* Calculate branch probabilities, and basic block execution counts.
+   Copyright (C) 1990, 1991, 1992, 1993, 1994, 1996, 1997, 1998, 1999,
+   2000, 2001  Free Software Foundation, Inc.
    Contributed by James E. Wilson, UC Berkeley/Cygnus Support;
    based on some ideas from Dain Samples of UC Berkeley.
    Further mangling by Bob Manson, Cygnus Support.
 
-This file is part of GNU CC.
+This file is part of GCC.
 
-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.
+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.
 
-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.
+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 GNU CC; see the file COPYING.  If not, write to
-the Free Software Foundation, 59 Temple Place - Suite 330,
-Boston, MA 02111-1307, USA.  */
-
-/* ??? Really should not put insns inside of LIBCALL sequences, when putting
-   insns after a call, should look for the insn setting the retval, and
-   insert the insns after that one.  */
+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.  */
 
 /* ??? Register allocation should use basic block execution counts to
    give preference to the most commonly executed blocks.  */
@@ -36,111 +33,76 @@ Boston, MA 02111-1307, USA.  */
 /* ??? Should calculate branch probabilities before instrumenting code, since
    then we can use arc counts to help decide which arcs to instrument.  */
 
-/* ??? Rearrange code so that the most frequently executed arcs become from
-   one block to the next block (i.e. a fall through), move seldom executed
-   code outside of loops even at the expense of adding a few branches to
-   achieve this, see Dain Sample's UC Berkeley thesis.  */
-
 #include "config.h"
 #include "system.h"
 #include "rtl.h"
+#include "tree.h"
 #include "flags.h"
-#include "insn-flags.h"
 #include "insn-config.h"
 #include "output.h"
 #include "regs.h"
-#include "tree.h"
-#include "output.h"
-#include "gcov-io.h"
+#include "expr.h"
+#include "function.h"
 #include "toplev.h"
+#include "ggc.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
+#include "gcov-io.h"
+#include "target.h"
 
-/* One of these is dynamically created whenever we identify an arc in the
-   function.  */
-
-struct adj_list
-{
-  int source;
-  int target;
-  int arc_count;
-  unsigned int count_valid : 1;
-  unsigned int on_tree : 1;
-  unsigned int fake : 1;
-  unsigned int fall_through : 1;
-  rtx branch_insn;
-  struct adj_list *pred_next;
-  struct adj_list *succ_next;
-};
-
-#define ARC_TARGET(ARCPTR) (ARCPTR->target)
-#define ARC_SOURCE(ARCPTR) (ARCPTR->source)
-#define ARC_COUNT(ARCPTR)  (ARCPTR->arc_count)
-
-/* Count the number of basic blocks, and create an array of these structures,
-   one for each bb in the function.  */
-
+/* Additional information about the edges we need.  */
+struct edge_info
+  {
+    unsigned int count_valid : 1;
+    unsigned int on_tree : 1;
+    unsigned int ignore : 1;
+  };
 struct bb_info
-{
-  struct adj_list *succ;
-  struct adj_list *pred;
-  int succ_count;
-  int pred_count;
-  int exec_count;
-  unsigned int count_valid : 1;
-  unsigned int on_tree : 1;
-  rtx first_insn;
-};
-
-/* Indexed by label number, gives the basic block number containing that
-   label.  */
-
-static int *label_to_bb;
-
-/* Number of valid entries in the label_to_bb array.  */
-
-static int label_to_bb_size;
-
-/* Indexed by block index, holds the basic block graph.  */
-
-static struct bb_info *bb_graph;
+  {
+    unsigned int count_valid : 1;
+    gcov_type succ_count;
+    gcov_type pred_count;
+  };
+
+#define EDGE_INFO(e)  ((struct edge_info *) (e)->aux)
+#define BB_INFO(b)  ((struct bb_info *) (b)->aux)
+
+/* Keep all basic block indexes nonnegative in the gcov output.  Index 0
+   is used for entry block, last block exit block.  */
+#define GCOV_INDEX_TO_BB(i)  ((i) == 0 ? ENTRY_BLOCK_PTR		\
+			      : (((i) == n_basic_blocks + 1)		\
+			         ? EXIT_BLOCK_PTR : BASIC_BLOCK ((i)-1)))
+#define BB_TO_GCOV_INDEX(bb)  ((bb) == ENTRY_BLOCK_PTR ? 0		\
+			       : ((bb) == EXIT_BLOCK_PTR		\
+				  ? n_basic_blocks + 1 : (bb)->index + 1))
 
 /* Name and file pointer of the output file for the basic block graph.  */
 
-static char *bbg_file_name;
 static FILE *bbg_file;
 
 /* Name and file pointer of the input file for the arc count data.  */
 
-static char *da_file_name;
 static FILE *da_file;
 
-/* Pointer of the output file for the basic block/line number map. */
+/* Pointer of the output file for the basic block/line number map.  */
 static FILE *bb_file;
 
-/* Last source file name written to bb_file. */
+/* Last source file name written to bb_file.  */
 
 static char *last_bb_file_name;
 
-/* Indicates whether the next line number note should be output to
-   bb_file or not.  Used to eliminate a redundant note after an
-   expanded inline function call.  */
-
-static int ignore_next_note;
-
 /* Used by final, for allocating the proper amount of storage for the
    instrumented arc execution counts.  */
 
-int count_instrumented_arcs;
-
-/* Number of executions for the return label.  */
-
-int return_label_execution_count;
+int count_instrumented_edges;
 
 /* Collect statistics on the performance of this pass for the entire source
    file.  */
 
 static int total_num_blocks;
-static int total_num_arcs;
-static int total_num_arcs_instrumented;
+static int total_num_edges;
+static int total_num_edges_ignored;
+static int total_num_edges_instrumented;
 static int total_num_blocks_created;
 static int total_num_passes;
 static int total_num_times_called;
@@ -149,248 +111,76 @@ static int total_num_never_executed;
 static int total_num_branches;
 
 /* Forward declarations.  */
-static void init_arc PROTO((struct adj_list *, int, int, rtx));
-static void find_spanning_tree PROTO((int));
-static void expand_spanning_tree PROTO((int));
-static void fill_spanning_tree PROTO((int));
-static void init_arc_profiler PROTO((void));
-static void output_arc_profiler PROTO((int, rtx));
-
-#ifndef LONG_TYPE_SIZE
-#define LONG_TYPE_SIZE BITS_PER_WORD
-#endif
+static void find_spanning_tree PARAMS ((struct edge_list *));
+static void init_edge_profiler PARAMS ((void));
+static rtx gen_edge_profiler PARAMS ((int));
+static void instrument_edges PARAMS ((struct edge_list *));
+static void output_gcov_string PARAMS ((const char *, long));
+static void compute_branch_probabilities PARAMS ((void));
+static basic_block find_group PARAMS ((basic_block));
+static void union_groups PARAMS ((basic_block, basic_block));
 
 /* If non-zero, we need to output a constructor to set up the
-   per-object-file data. */
+   per-object-file data.  */
 static int need_func_profiler = 0;
-
 
-/* Add arc instrumentation code to the entire insn chain.
+/* Add edge instrumentation code to the entire insn chain.
 
    F is the first insn of the chain.
-   NUM_BLOCKS is the number of basic blocks found in F.
-   DUMP_FILE, if nonzero, is an rtl dump file we can write to.  */
+   NUM_BLOCKS is the number of basic blocks found in F.  */
 
 static void
-instrument_arcs (f, num_blocks, dump_file)
-     rtx f;
-     int num_blocks;
-     FILE *dump_file;
+instrument_edges (el)
+     struct edge_list *el;
 {
-  register int i;
-  register struct adj_list *arcptr, *backptr;
-  int num_arcs = 0;
-  int num_instr_arcs = 0;
-  rtx insn;
-
-  /* Instrument the program start.  */
-  /* Handle block 0 specially, since it will always be instrumented,
-     but it doesn't have a valid first_insn or branch_insn.  We must
-     put the instructions before the NOTE_INSN_FUNCTION_BEG note, so
-     that they don't clobber any of the parameters of the current
-     function.  */
-  for (insn = f; insn; insn = NEXT_INSN (insn))
-    if (GET_CODE (insn) == NOTE
-	&& NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG)
-      break;
-  insn = PREV_INSN (insn);
-  need_func_profiler = 1;
-  output_arc_profiler (total_num_arcs_instrumented + num_instr_arcs++, insn);
-
-  for (i = 1; i < num_blocks; i++)
-    for (arcptr = bb_graph[i].succ; arcptr; arcptr = arcptr->succ_next)
-      if (! arcptr->on_tree)
+  int i;
+  int num_instr_edges = 0;
+  int num_edges = NUM_EDGES (el);
+  remove_fake_edges ();
+
+  for (i = 0; i < n_basic_blocks + 2; i++)
+    {
+      basic_block bb = GCOV_INDEX_TO_BB (i);
+      edge e = bb->succ;
+      while (e)
 	{
-	  if (dump_file)
-	    fprintf (dump_file, "Arc %d to %d instrumented\n", i,
-		     ARC_TARGET (arcptr));
-
-	  /* Check to see if this arc is the only exit from its source block,
-	     or the only entrance to its target block.  In either case,
-	     we don't need to create a new block to instrument the arc.  */
-	  
-	  if (bb_graph[i].succ == arcptr && arcptr->succ_next == 0)
-	    {
-	      /* Instrument the source block.  */
-	      output_arc_profiler (total_num_arcs_instrumented
-				   + num_instr_arcs++,
-				   PREV_INSN (bb_graph[i].first_insn));
-	    }
-	  else if (arcptr == bb_graph[ARC_TARGET (arcptr)].pred
-		   && arcptr->pred_next == 0)
+	  struct edge_info *inf = EDGE_INFO (e);
+	  if (!inf->ignore && !inf->on_tree)
 	    {
-	      /* Instrument the target block.  */
-	      output_arc_profiler (total_num_arcs_instrumented
-				   + num_instr_arcs++, 
-				   PREV_INSN (bb_graph[ARC_TARGET (arcptr)].first_insn));
-	    }
-	  else if (arcptr->fall_through)
-	    {
-	      /* This is a fall-through; put the instrumentation code after
-		 the branch that ends this block.  */
-	      
-	      for (backptr = bb_graph[i].succ; backptr;
-		   backptr = backptr->succ_next)
-		if (backptr != arcptr)
-		  break;
-	      
-	      output_arc_profiler (total_num_arcs_instrumented
-				   + num_instr_arcs++,
-				   backptr->branch_insn);
-	    }
-	  else
-	    {
-	      /* Must emit a new basic block to hold the arc counting code.  */
-	      enum rtx_code code = GET_CODE (PATTERN (arcptr->branch_insn));
-
-	      if (code == SET)
-		{
-		  /* Create the new basic block right after the branch.
-		     Invert the branch so that it jumps past the end of the new
-		     block.  The new block will consist of the instrumentation
-		     code, and a jump to the target of this arc.  */
-		  int this_is_simplejump = simplejump_p (arcptr->branch_insn);
-		  rtx new_label = gen_label_rtx ();
-		  rtx old_label, set_src;
-		  rtx after = arcptr->branch_insn;
-		  
-		  /* Simplejumps can't reach here.  */
-		  if (this_is_simplejump)
-		    abort ();
-
-		  /* We can't use JUMP_LABEL, because it won't be set if we
-		     are compiling without optimization.  */
-
-		  set_src = SET_SRC (single_set (arcptr->branch_insn));
-		  if (GET_CODE (set_src) == LABEL_REF)
-		    old_label = set_src;
-		  else if (GET_CODE (set_src) != IF_THEN_ELSE)
-		    abort ();
-		  else if (XEXP (set_src, 1) == pc_rtx)
-		    old_label = XEXP (XEXP (set_src, 2), 0);
-		  else
-		    old_label = XEXP (XEXP (set_src, 1), 0);
-
-		  /* Set the JUMP_LABEL so that redirect_jump will work.  */
-		  JUMP_LABEL (arcptr->branch_insn) = old_label;
-
-		  /* Add a use for OLD_LABEL that will be needed when we emit
-		     the JUMP_INSN below.  If we don't do this here,
-		     `invert_jump' might delete it for us.  We must add two
-		     when not optimizing, because the NUSES is zero now,
-		     but must be at least two to prevent the label from being
-		     deleted.  */
-		  LABEL_NUSES (old_label) += 2;
-		  
-		  /* Emit the insns for the new block in reverse order,
-		     since that is most convenient.  */
-
-		  if (this_is_simplejump)
-		    {
-		      after = NEXT_INSN (arcptr->branch_insn);
-		      if (! redirect_jump (arcptr->branch_insn, new_label))
-			/* Don't know what to do if this branch won't
-			   redirect.  */
-			abort ();
-		    }
-		  else
-		    {
-		      if (! invert_jump (arcptr->branch_insn, new_label))
-			/* Don't know what to do if this branch won't invert.  */
-			abort ();
-
-		      emit_label_after (new_label, after);
-		      LABEL_NUSES (new_label)++;
-		    }
-		  emit_barrier_after (after);
-		  emit_jump_insn_after (gen_jump (old_label), after);
-		  JUMP_LABEL (NEXT_INSN (after)) = old_label;
-		  
-		  /* Instrument the source arc.  */
-		  output_arc_profiler (total_num_arcs_instrumented
-				       + num_instr_arcs++,
-				       after);
-		  if (this_is_simplejump)
-		    {
-		      emit_label_after (new_label, after);
-		      LABEL_NUSES (new_label)++;
-		    }
-		}
-	      else if (code == ADDR_VEC || code == ADDR_DIFF_VEC)
-		{
-		  /* A table jump.  Create a new basic block immediately
-		     after the table, by emitting a barrier, a label, a
-		     counting note, and a jump to the old label.  Put the
-		     new label in the table.  */
-		  
-		  rtx new_label = gen_label_rtx ();
-		  rtx old_lref, new_lref;
-		  int index;
-		  
-		  /* Must determine the old_label reference, do this
-		     by counting the arcs after this one, which will
-		     give the index of our label in the table.  */
-		  
-		  index = 0;
-		  for (backptr = arcptr->succ_next; backptr;
-		       backptr = backptr->succ_next)
-		    index++;
-		  
-		  old_lref = XVECEXP (PATTERN (arcptr->branch_insn),
-				      (code == ADDR_DIFF_VEC), index);
-		  
-		  /* Emit the insns for the new block in reverse order,
-		     since that is most convenient.  */
-		  emit_jump_insn_after (gen_jump (XEXP (old_lref, 0)),
-					arcptr->branch_insn);
-		  JUMP_LABEL (NEXT_INSN (arcptr->branch_insn))
-		    = XEXP (old_lref, 0);
-
-		  /* Instrument the source arc.  */
-		  output_arc_profiler (total_num_arcs_instrumented
-				       + num_instr_arcs++,
-				       arcptr->branch_insn);
-
-		  emit_label_after (new_label, arcptr->branch_insn);
-		  LABEL_NUSES (NEXT_INSN (arcptr->branch_insn))++;
-		  emit_barrier_after (arcptr->branch_insn);
-		  
-		  /* Fix up the table jump.  */
-		  new_lref = gen_rtx_LABEL_REF (Pmode, new_label);
-		  XVECEXP (PATTERN (arcptr->branch_insn),
-			   (code == ADDR_DIFF_VEC), index) = new_lref;
-		}
-	      else
+	      if (e->flags & EDGE_ABNORMAL)
 		abort ();
-
-	      num_arcs += 1;
-	      if (dump_file)
-		fprintf (dump_file,
-			 "Arc %d to %d needed new basic block\n", i,
-			 ARC_TARGET (arcptr));
+	      if (rtl_dump_file)
+		fprintf (rtl_dump_file, "Edge %d to %d instrumented%s\n",
+			 e->src->index, e->dest->index,
+			 EDGE_CRITICAL_P (e) ? " (and split)" : "");
+	      need_func_profiler = 1;
+	      insert_insn_on_edge (
+			 gen_edge_profiler (total_num_edges_instrumented
+					    + num_instr_edges++), e);
 	    }
+	  e = e->succ_next;
 	}
-  
-  total_num_arcs_instrumented += num_instr_arcs;
-  count_instrumented_arcs = total_num_arcs_instrumented;
-
-  total_num_blocks_created += num_arcs;
-  if (dump_file)
-    {
-      fprintf (dump_file, "%d arcs instrumented\n", num_instr_arcs);
-      fprintf (dump_file, "%d extra basic blocks created\n", num_arcs);
     }
+
+  total_num_edges_instrumented += num_instr_edges;
+  count_instrumented_edges = total_num_edges_instrumented;
+
+  total_num_blocks_created += num_edges;
+  if (rtl_dump_file)
+    fprintf (rtl_dump_file, "%d edges instrumented\n", num_instr_edges);
+
+  commit_edge_insertions ();
 }
 
 /* Output STRING to bb_file, surrounded by DELIMITER.  */
 
 static void
 output_gcov_string (string, delimiter)
-     char *string;
+     const char *string;
      long delimiter;
 {
   long temp;
-			
+
   /* Write a delimiter to indicate that a file name follows.  */
   __write_long (delimiter, bb_file, 4);
 
@@ -408,606 +198,99 @@ output_gcov_string (string, delimiter)
       fwrite (c, sizeof (char), 4 - temp, bb_file);
     }
 
-  /* Store another delimiter in the .bb file, just to make it easy to find the
-     end of the file name.  */
+  /* Store another delimiter in the .bb file, just to make it easy to find
+     the end of the file name.  */
   __write_long (delimiter, bb_file, 4);
 }
 
-/* Return TRUE if this insn must be a tablejump entry insn.  This works for
-   the MIPS port, but may give false negatives for some targets.  */
-
-int
-tablejump_entry_p (insn, label)
-     rtx insn, label;
-{
-  rtx next = next_active_insn (insn);
-  enum rtx_code code = GET_CODE (PATTERN (next));
-
-  if (code != ADDR_DIFF_VEC && code != ADDR_VEC)
-    return 0;
-
-  if (PREV_INSN (next) == XEXP (label, 0))
-    return 1;
 
-  return 0;
-}
-
-/* Instrument and/or analyze program behavior based on program flow graph.
-   In either case, this function builds a flow graph for the function being
-   compiled.  The flow graph is stored in BB_GRAPH.
-
-   When FLAG_PROFILE_ARCS is nonzero, this function instruments the arcs in
-   the flow graph that are needed to reconstruct the dynamic behavior of the
-   flow graph.
-
-   When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
-   information from a data file containing arc count information from previous
-   executions of the function being compiled.  In this case, the flow graph is
-   annotated with actual execution counts, which are later propagated into the
-   rtl for optimization purposes.
+/* Compute the branch probabilities for the various branches.
+   Annotate them accordingly.  */
 
-   Main entry point of this file.  */
-
-void
-branch_prob (f, dump_file)
-     rtx f;
-     FILE *dump_file;
+static void
+compute_branch_probabilities ()
 {
-  int i, num_blocks;
-  struct adj_list *arcptr;
-  int num_arcs, changes, passes;
-  int total, prob;
-  int hist_br_prob[20], num_never_executed, num_branches;
-  /* Set to non-zero if we got bad count information.  */
-  int bad_counts = 0;
-
-  /* start of a function.  */
-  if (flag_test_coverage)
-    output_gcov_string (current_function_name, (long) -2);
-
-  /* Execute this only if doing arc profiling or branch probabilities.  */
-  if (! profile_arc_flag && ! flag_branch_probabilities
-      && ! flag_test_coverage)
-    abort ();
-
-  total_num_times_called++;
-
-  /* Create an array label_to_bb of ints of size max_label_num.  */
-  label_to_bb_size = max_label_num ();
-  label_to_bb = (int *) oballoc (label_to_bb_size * sizeof (int));
-  bzero ((char *) label_to_bb, label_to_bb_size * sizeof (int));
-
-  /* Scan the insns in the function, count the number of basic blocks
-     present.  When a code label is passed, set label_to_bb[label] = bb
-     number.  */
-
-  /* The first block found will be block 1, so that function entry can be
-     block 0.  */
-
-  {
-    register RTX_CODE prev_code = JUMP_INSN;
-    register RTX_CODE code;
-    register rtx insn;
-    register int i;
-    int block_separator_emitted = 0;
-
-    ignore_next_note = 0;
-
-    for (insn = NEXT_INSN (f), i = 0; insn; insn = NEXT_INSN (insn))
-      {
-	code = GET_CODE (insn);
-
-	if (code == BARRIER)
-	  ;
-	else if (code == CODE_LABEL)
-	  /* This label is part of the next block, but we can't increment
-	     block number yet since there might be multiple labels.  */
-	  label_to_bb[CODE_LABEL_NUMBER (insn)] = i + 1;
-	/* We make NOTE_INSN_SETJMP notes into a block of their own, so that
-	   they can be the target of the fake arc for the setjmp call.
-	   This avoids creating cycles of fake arcs, which would happen if
-	   the block after the setjmp call contained a call insn.  */
-	else if ((prev_code == JUMP_INSN || prev_code == CALL_INSN
-		  || prev_code == CODE_LABEL || prev_code == BARRIER)
-		 && (GET_RTX_CLASS (code) == 'i'
-		     || (code == NOTE
-			 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)))
-	  {
-	    i += 1;
-
-	    /* Emit the block separator if it hasn't already been emitted.  */
-	    if (flag_test_coverage && ! block_separator_emitted)
-	      {
-		/* Output a zero to the .bb file to indicate that a new
-		   block list is starting.  */
-		__write_long (0, bb_file, 4);
-	      }
-	    block_separator_emitted = 0;
-	  }
-	/* If flag_test_coverage is true, then we must add an entry to the
-	   .bb file for every note.  */
-	else if (code == NOTE && flag_test_coverage)
-	  {
-	    /* Must ignore the line number notes that immediately follow the
-	       end of an inline function to avoid counting it twice.  There
-	       is a note before the call, and one after the call.  */
-	    if (NOTE_LINE_NUMBER (insn) == NOTE_REPEATED_LINE_NUMBER)
-	      ignore_next_note = 1;
-	    else if (NOTE_LINE_NUMBER (insn) > 0)
-	      {
-		if (ignore_next_note)
-		  ignore_next_note = 0;
-		else
-		  {
-		    /* Emit a block separator here to ensure that a NOTE
-		       immediately following a JUMP_INSN or CALL_INSN will end
-		       up in the right basic block list.  */
-		    if ((prev_code == JUMP_INSN || prev_code == CALL_INSN
-			 || prev_code == CODE_LABEL || prev_code == BARRIER)
-			&& ! block_separator_emitted)
-		      {
-			/* Output a zero to the .bb file to indicate that
-			   a new block list is starting.  */
-			__write_long (0, bb_file, 4);
-
-			block_separator_emitted = 1;
-		      }
-		    
-		    /* If this is a new source file, then output the file's
-		       name to the .bb file.  */
-		    if (! last_bb_file_name
-			|| strcmp (NOTE_SOURCE_FILE (insn),
-				   last_bb_file_name))
-		      {
-			if (last_bb_file_name)
-			  free (last_bb_file_name);
-			last_bb_file_name
-			  = xmalloc (strlen (NOTE_SOURCE_FILE (insn)) + 1);
-			strcpy (last_bb_file_name, NOTE_SOURCE_FILE (insn));
-			output_gcov_string (NOTE_SOURCE_FILE (insn), (long)-1);
-		      }
-
-		    /* Output the line number to the .bb file.  Must be done
-		       after the output_bb_profile_data() call, and after the
-		       file name is written, to ensure that it is correctly
-		       handled by gcov.  */
-		    __write_long (NOTE_LINE_NUMBER (insn), bb_file, 4);
-		  }
-	      }
-	  }
-
-	if (code != NOTE)
-	  prev_code = code;
-	else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
-	  prev_code = CALL_INSN;
-      }
-
-    /* Allocate last `normal' entry for bb_graph.  */
-
-    /* The last insn was a jump, call, or label.  In that case we have
-       a block at the end of the function with no insns.  */
-    if (prev_code == JUMP_INSN || prev_code == CALL_INSN
-	|| prev_code == CODE_LABEL || prev_code == BARRIER)
-      {
-	i++;
-
-	/* Emit the block separator if it hasn't already been emitted.  */
-	if (flag_test_coverage && ! block_separator_emitted)
-	  {
-	    /* Output a zero to the .bb file to indicate that a new
-	       block list is starting.  */
-	    __write_long (0, bb_file, 4);
-	  }
-      }
+  int i;
+  int num_edges = 0;
+  int changes;
+  int passes;
+  int hist_br_prob[20];
+  int num_never_executed;
+  int num_branches;
 
-    /* Create another block to stand for EXIT, and make all return insns, and
-       the last basic block point here.  Add one more to account for block
-       zero.  */
-    num_blocks = i + 2;
-  }
+  /* Attach extra info block to each bb.  */
 
-  total_num_blocks += num_blocks;
-  if (dump_file)
-    fprintf (dump_file, "%d basic blocks\n", num_blocks);
+  alloc_aux_for_blocks (sizeof (struct bb_info));
+  for (i = 0; i < n_basic_blocks + 2; i++)
+    {
+      basic_block bb = GCOV_INDEX_TO_BB (i);
+      edge e;
+
+      for (e = bb->succ; e; e = e->succ_next)
+	if (!EDGE_INFO (e)->ignore)
+	  BB_INFO (bb)->succ_count++;
+      for (e = bb->pred; e; e = e->pred_next)
+	if (!EDGE_INFO (e)->ignore)
+	  BB_INFO (bb)->pred_count++;
+    }
 
-  /* If we are only doing test coverage here, then return now.  */
-  if (! profile_arc_flag && ! flag_branch_probabilities)
-    return;
+  /* Avoid predicting entry on exit nodes.  */
+  BB_INFO (EXIT_BLOCK_PTR)->succ_count = 2;
+  BB_INFO (ENTRY_BLOCK_PTR)->pred_count = 2;
 
-  /* Create and initialize the arrays that will hold bb_graph
-     and execution count info.  */
+  /* For each edge not on the spanning tree, set its execution count from
+     the .da file.  */
 
-  bb_graph = (struct bb_info *) alloca (num_blocks * sizeof (struct bb_info));
-  bzero ((char *) bb_graph, (sizeof (struct bb_info) * num_blocks));
+  /* The first count in the .da file is the number of times that the function
+     was entered.  This is the exec_count for block zero.  */
 
-  {
-    /* Scan the insns again:
-       - at the entry to each basic block, increment the predecessor count
-       (and successor of previous block) if it is a fall through entry,
-       create adj_list entries for this and the previous block
-       - at each jump insn, increment predecessor/successor counts for
-       target/source basic blocks, add this insn to pred/succ lists.
-
-       This also cannot be broken out as a separate subroutine
-       because it uses `alloca'.  */
-
-    register RTX_CODE prev_code = JUMP_INSN;
-    register RTX_CODE code;
-    register rtx insn;
-    register int i;
-    int fall_through = 0;
-    struct adj_list *arcptr;
-    int dest = 0;
-
-    /* Block 0 always falls through to block 1.  */
-    num_arcs = 0;
-    arcptr = (struct adj_list *) alloca (sizeof (struct adj_list));
-    init_arc (arcptr, 0, 1, 0);
-    arcptr->fall_through = 1;
-    num_arcs++;
-
-    /* Add a fake fall through arc from the last block to block 0, to make the
-       graph complete.  */
-    arcptr = (struct adj_list *) alloca (sizeof (struct adj_list));
-    init_arc (arcptr, num_blocks - 1, 0, 0);
-    arcptr->fake = 1;
-    num_arcs++;
-
-    /* Exit must be one node of the graph, and all exits from the function
-       must point there.  When see a return branch, must point the arc to the
-       exit node.  */
-
-    /* Must start scan with second insn in function as above.  */
-    for (insn = NEXT_INSN (f), i = 0; insn; insn = NEXT_INSN (insn))
-      {
-	code = GET_CODE (insn);
-
-	if (code == BARRIER)
-	  fall_through = 0;
-	else if (code == CODE_LABEL)
-	  ;
-	/* We make NOTE_INSN_SETJMP notes into a block of their own, so that
-	   they can be the target of the fake arc for the setjmp call.
-	   This avoids creating cycles of fake arcs, which would happen if
-	   the block after the setjmp call ended with a call.  */
-	else if ((prev_code == JUMP_INSN || prev_code == CALL_INSN
-		  || prev_code == CODE_LABEL || prev_code == BARRIER)
-		 && (GET_RTX_CLASS (code) == 'i'
-		     || (code == NOTE
-			 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)))
+  for (i = 0; i < n_basic_blocks + 2; i++)
+    {
+      basic_block bb = GCOV_INDEX_TO_BB (i);
+      edge e;
+      for (e = bb->succ; e; e = e->succ_next)
+	if (!EDGE_INFO (e)->ignore && !EDGE_INFO (e)->on_tree)
 	  {
-	    /* This is the first insn of the block.  */
-	    i += 1;
-	    if (fall_through)
+	    num_edges++;
+	    if (da_file)
 	      {
-		arcptr = (struct adj_list *) alloca (sizeof (struct adj_list));
-		init_arc (arcptr, i - 1, i, 0);
-		arcptr->fall_through = 1;
-
-		num_arcs++;
+		gcov_type value;
+		__read_gcov_type (&value, da_file, 8);
+		e->count = value;
 	      }
-	    fall_through = 1;
-	    bb_graph[i].first_insn = insn;
-	  }
-	else if (code == NOTE)
-	  {;}
-
-	if (code == CALL_INSN)
-	  {
-	    /* In the normal case, the call returns, and this is just like
-	       a branch fall through.  */
-	    fall_through = 1;
-
-	    /* Setjmp may return more times than called, so to make the graph
-	       solvable, add a fake arc from the function entrance to the
-	       next block.
-
-	       All other functions may return fewer times than called (if
-	       a descendent call longjmp or exit), so to make the graph
-	       solvable, add a fake arc to the function exit from the
-	       current block.
-
-	       Distinguish the cases by checking for a SETJUMP note.
-	       A call_insn can be the last ins of a function, so must check
-	       to see if next insn actually exists.  */
-	    arcptr = (struct adj_list *) alloca (sizeof (struct adj_list));
-	    if (NEXT_INSN (insn)
-		&& GET_CODE (NEXT_INSN (insn)) == NOTE
-		&& NOTE_LINE_NUMBER (NEXT_INSN (insn)) == NOTE_INSN_SETJMP)
-	      init_arc (arcptr, 0, i+1, insn);
 	    else
-	      init_arc (arcptr, i, num_blocks-1, insn);
-	    arcptr->fake = 1;
-	    num_arcs++;
-	  }
-	else if (code == JUMP_INSN)
-	  {
-	    rtx tem, pattern = PATTERN (insn);
-	    rtx tablejump = 0;
-
-	    /* If running without optimization, then jump label won't be valid,
-	       so we must search for the destination label in that case.
-	       We have to handle tablejumps and returns specially anyways, so
-	       we don't check the JUMP_LABEL at all here.  */
-
-	    /* ??? This code should be rewritten.  We need a more elegant way
-	       to find the LABEL_REF.  We need a more elegant way to
-	       differentiate tablejump entries from computed gotos.
-	       We should perhaps reuse code from flow to compute the CFG
-	       instead of trying to compute it here.
-
-	       We can't use current_function_has_computed_jump, because that
-	       is calculated later by flow.  We can't use computed_jump_p,
-	       because that returns true for tablejump entry insns for some
-	       targets, e.g. HPPA and MIPS.  */
-
-	    if (GET_CODE (pattern) == PARALLEL)
+	      e->count = 0;
+	    EDGE_INFO (e)->count_valid = 1;
+	    BB_INFO (bb)->succ_count--;
+	    BB_INFO (e->dest)->pred_count--;
+	    if (rtl_dump_file)
 	      {
-		/* This assumes that PARALLEL jumps with a USE are
-		   tablejump entry jumps.  The same assumption can be found
-		   in computed_jump_p.  */
-		/* Make an arc from this jump to the label of the
-		   jump table.  This will instrument the number of
-		   times the switch statement is executed.  */
-		if (GET_CODE (XVECEXP (pattern, 0, 1)) == USE)
-		  {
-		    tem = XEXP (XVECEXP (pattern, 0, 1), 0);
-		    if (GET_CODE (tem) != LABEL_REF)
-		      abort ();
-		    dest = label_to_bb[CODE_LABEL_NUMBER (XEXP (tem, 0))];
-		  }
-		else if (GET_CODE (XVECEXP (pattern, 0, 0)) == SET
-			 && SET_DEST (XVECEXP (pattern, 0, 0)) == pc_rtx)
-		  {
-		    tem = SET_SRC (XVECEXP (pattern, 0, 0));
-		    if (GET_CODE (tem) == PLUS
-			&& GET_CODE (XEXP (tem, 1)) == LABEL_REF)
-		      {
-			tem = XEXP (tem, 1);
-			dest = label_to_bb [CODE_LABEL_NUMBER (XEXP (tem, 0))];
-		      }
-		  }
-		else
-		  abort ();
+		fprintf (rtl_dump_file, "\nRead edge from %i to %i, count:",
+			 bb->index, e->dest->index);
+		fprintf (rtl_dump_file, HOST_WIDEST_INT_PRINT_DEC,
+			 (HOST_WIDEST_INT) e->count);
 	      }
-	    else if (GET_CODE (pattern) == ADDR_VEC
-		     || GET_CODE (pattern) == ADDR_DIFF_VEC)
-	      tablejump = pattern;
-	    else if (GET_CODE (pattern) == RETURN)
-	      dest = num_blocks - 1;
-	    else if (GET_CODE (pattern) != SET)
-	      abort ();
-	    else if ((tem = SET_SRC (pattern))
-		     && GET_CODE (tem) == LABEL_REF)
-	      dest = label_to_bb[CODE_LABEL_NUMBER (XEXP (tem, 0))];
-	    /* Recognize HPPA table jump entry.  This code is similar to
-	       the code above in the PARALLEL case.  */
-	    else if (GET_CODE (tem) == PLUS
-		     && GET_CODE (XEXP (tem, 0)) == MEM
-		     && GET_CODE (XEXP (XEXP (tem, 0), 0)) == PLUS
-		     && GET_CODE (XEXP (XEXP (XEXP (tem, 0), 0), 0)) == PC
-		     && GET_CODE (XEXP (tem, 1)) == LABEL_REF
-		     && tablejump_entry_p (insn, XEXP (tem, 1)))
-	      dest = label_to_bb[CODE_LABEL_NUMBER (XEXP (XEXP (tem, 1), 0))];
-	    /* Recognize the MIPS table jump entry.  */
-	    else if (GET_CODE (tem) == PLUS
-		     && GET_CODE (XEXP (tem, 0)) == REG
-		     && GET_CODE (XEXP (tem, 1)) == LABEL_REF
-		     && tablejump_entry_p (insn, XEXP (tem, 1)))
-	      dest = label_to_bb[CODE_LABEL_NUMBER (XEXP (XEXP (tem, 1), 0))];
-	    else
-	      {
-		rtx label_ref;
-
-		/* Must be an IF_THEN_ELSE branch.  If it isn't, assume it
-		   is a computed goto, which aren't supported yet.  */
-		if (GET_CODE (tem) != IF_THEN_ELSE)
-		  fatal ("-fprofile-arcs does not support computed gotos");
-		if (XEXP (tem, 1) != pc_rtx)
-		  label_ref = XEXP (tem, 1);
-		else
-		  label_ref = XEXP (tem, 2);
-		dest = label_to_bb[CODE_LABEL_NUMBER (XEXP (label_ref, 0))];
-	      }
-
-	    if (tablejump)
-	      {
-		int diff_vec_p = GET_CODE (tablejump) == ADDR_DIFF_VEC;
-		int len = XVECLEN (tablejump, diff_vec_p);
-		int k;
-
-		for (k = 0; k < len; k++)
-		  {
-		    rtx tem = XEXP (XVECEXP (tablejump, diff_vec_p, k), 0);
-		    dest = label_to_bb[CODE_LABEL_NUMBER (tem)];
-
-		    arcptr = (struct adj_list *) alloca (sizeof(struct adj_list));
-		    init_arc (arcptr, i, dest, insn);
-
-		    num_arcs++;
-		  }
-	      }
-	    else
-	      {
-		arcptr = (struct adj_list *) alloca (sizeof (struct adj_list));
-		init_arc (arcptr, i, dest, insn);
-
-		num_arcs++;
-	      }
-
-	    /* Determine whether or not this jump will fall through.
-	       Unconditional jumps and returns are not always followed by
-	       barriers.  */
-	    pattern = PATTERN (insn);
-	    if (GET_CODE (pattern) == PARALLEL
-		|| GET_CODE (pattern) == RETURN)
-	      fall_through = 0;
-	    else if (GET_CODE (pattern) == ADDR_VEC
-		     || GET_CODE (pattern) == ADDR_DIFF_VEC)
-	      /* These aren't actually jump insns, but they never fall
-		 through, so...  */
-	      fall_through = 0;
-	    else
-	      {
-		if (GET_CODE (pattern) != SET || SET_DEST (pattern) != pc_rtx)
-		  abort ();
-		if (GET_CODE (SET_SRC (pattern)) != IF_THEN_ELSE)
-		  fall_through = 0;
-	      }
-	  }
-
-	if (code != NOTE)
-	  prev_code = code;
-	else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
-	  {
-	    /* Make a fake insn to tag our notes on.  */
-	    bb_graph[i].first_insn = insn
-	      = emit_insn_after (gen_rtx_USE (VOIDmode, stack_pointer_rtx),
-				 insn);
-	    prev_code = CALL_INSN;
 	  }
-      }
-
-    /* If the code at the end of the function would give a new block, then
-       do the following.  */
-
-    if (prev_code == JUMP_INSN || prev_code == CALL_INSN
-	|| prev_code == CODE_LABEL || prev_code == BARRIER)
-      {
-	if (fall_through)
-	  {
-	    arcptr = (struct adj_list *) alloca (sizeof (struct adj_list));
-	    init_arc (arcptr, i, i + 1, 0);
-	    arcptr->fall_through = 1;
-
-	    num_arcs++;
-	  }
-	  
-	/* This may not be a real insn, but that should not cause a problem.  */
-	bb_graph[i+1].first_insn = get_last_insn ();
-      }
-
-    /* There is always a fake arc from the last block of the function
-       to the function exit block.  */
-    arcptr = (struct adj_list *) alloca (sizeof (struct adj_list));
-    init_arc (arcptr, num_blocks-2, num_blocks-1, 0);
-    arcptr->fake = 1;
-    num_arcs++;
-  }
-
-  total_num_arcs += num_arcs;
-  if (dump_file)
-    fprintf (dump_file, "%d arcs\n", num_arcs);
-
-  /* Create spanning tree from basic block graph, mark each arc that is
-     on the spanning tree.  */
-
-  /* To reduce the instrumentation cost, make two passes over the tree.
-     First, put as many must-split (crowded and fake) arcs on the tree as
-     possible, then on the second pass fill in the rest of the tree.
-     Note that the spanning tree is considered undirected, so that as many
-     must-split arcs as possible can be put on it.
-
-     Fallthrough arcs which are crowded should not be chosen on the first
-     pass, since they do not require creating a new basic block.  These
-     arcs will have fall_through set.  */
-
-  find_spanning_tree (num_blocks);
-
-  /* Create a .bbg file from which gcov can reconstruct the basic block
-     graph.  First output the number of basic blocks, and then for every
-     arc output the source and target basic block numbers.
-     NOTE: The format of this file must be compatible with gcov.  */
-
-  if (flag_test_coverage)
-    {
-      int flag_bits;
-
-      __write_long (num_blocks, bbg_file, 4);
-      __write_long (num_arcs, bbg_file, 4);
-
-      for (i = 0; i < num_blocks; i++)
-	{
-	  long count = 0;
-	  for (arcptr = bb_graph[i].succ; arcptr; arcptr = arcptr->succ_next)
-	    count++;
-	  __write_long (count, bbg_file, 4);
-
-	  for (arcptr = bb_graph[i].succ; arcptr; arcptr = arcptr->succ_next)
-	    {
-	      flag_bits = 0;
-	      if (arcptr->on_tree)
-		flag_bits |= 0x1;
-	      if (arcptr->fake)
-		flag_bits |= 0x2;
-	      if (arcptr->fall_through)
-		flag_bits |= 0x4;
-
-	      __write_long (ARC_TARGET (arcptr), bbg_file, 4);
-	      __write_long (flag_bits, bbg_file, 4);
-	    }
-	}
-
-      /* Emit a -1 to separate the list of all arcs from the list of
-	 loop back edges that follows.  */
-      __write_long (-1, bbg_file, 4);
     }
 
-  /* For each arc not on the spanning tree, add counting code as rtl.  */
-
-  if (profile_arc_flag)
-    {
-      instrument_arcs (f, num_blocks, dump_file);
-      allocate_reg_info (max_reg_num (), FALSE, FALSE);
-    }
-
-  /* Execute the rest only if doing branch probabilities.  */
-  if (! flag_branch_probabilities)
-    return;
-
-  /* For each arc not on the spanning tree, set its execution count from
-     the .da file.  */
-
-  /* The first count in the .da file is the number of times that the function
-     was entered.  This is the exec_count for block zero.  */
-
-  num_arcs = 0;
-  for (i = 0; i < num_blocks; i++)
-    for (arcptr = bb_graph[i].succ; arcptr; arcptr = arcptr->succ_next)
-      if (! arcptr->on_tree)
-	{
-	  num_arcs++;
-	  if (da_file)
-	    {
-	      long value;
-	      __read_long (&value, da_file, 8);
-	      ARC_COUNT (arcptr) = value;
-	    }
-	  else
-	    ARC_COUNT (arcptr) = 0;
-	  arcptr->count_valid = 1;
-	  bb_graph[i].succ_count--;
-	  bb_graph[ARC_TARGET (arcptr)].pred_count--;
-	}
-
-  if (dump_file)
-    fprintf (dump_file, "%d arc counts read\n", num_arcs);
+  if (rtl_dump_file)
+    fprintf (rtl_dump_file, "\n%d edge counts read\n", num_edges);
 
   /* For every block in the file,
-     - if every exit/entrance arc has a known count, then set the block count
-     - if the block count is known, and every exit/entrance arc but one has
-       a known execution count, then set the count of the remaining arc
+     - if every exit/entrance edge has a known count, then set the block count
+     - if the block count is known, and every exit/entrance edge but one has
+     a known execution count, then set the count of the remaining edge
 
-     As arc counts are set, decrement the succ/pred count, but don't delete
-     the arc, that way we can easily tell when all arcs are known, or only
-     one arc is unknown.  */
+     As edge counts are set, decrement the succ/pred count, but don't delete
+     the edge, that way we can easily tell when all edges are known, or only
+     one edge is unknown.  */
 
   /* The order that the basic blocks are iterated through is important.
      Since the code that finds spanning trees starts with block 0, low numbered
-     arcs are put on the spanning tree in preference to high numbered arcs.
-     Hence, most instrumented arcs are at the end.  Graph solving works much
+     edges are put on the spanning tree in preference to high numbered edges.
+     Hence, most instrumented edges are at the end.  Graph solving works much
      faster if we propagate numbers from the end to the start.
-     
+
      This takes an average of slightly more than 3 passes.  */
 
   changes = 1;
@@ -1016,101 +299,111 @@ branch_prob (f, dump_file)
     {
       passes++;
       changes = 0;
-
-      for (i = num_blocks - 1; i >= 0; i--)
+      for (i = n_basic_blocks + 1; i >= 0; i--)
 	{
-	  struct bb_info *binfo = &bb_graph[i];
-	  if (! binfo->count_valid)
+	  basic_block bb = GCOV_INDEX_TO_BB (i);
+	  struct bb_info *bi = BB_INFO (bb);
+	  if (! bi->count_valid)
 	    {
-	      if (binfo->succ_count == 0)
+	      if (bi->succ_count == 0)
 		{
-		  total = 0;
-		  for (arcptr = binfo->succ; arcptr;
-		       arcptr = arcptr->succ_next)
-		    total += ARC_COUNT (arcptr);
-		  binfo->exec_count = total;
-		  binfo->count_valid = 1;
+		  edge e;
+		  gcov_type total = 0;
+
+		  for (e = bb->succ; e; e = e->succ_next)
+		    total += e->count;
+		  bb->count = total;
+		  bi->count_valid = 1;
 		  changes = 1;
 		}
-	      else if (binfo->pred_count == 0)
+	      else if (bi->pred_count == 0)
 		{
-		  total = 0;
-		  for (arcptr = binfo->pred; arcptr;
-		       arcptr = arcptr->pred_next)
-		    total += ARC_COUNT (arcptr);
-		  binfo->exec_count = total;
-		  binfo->count_valid = 1;
+		  edge e;
+		  gcov_type total = 0;
+
+		  for (e = bb->pred; e; e = e->pred_next)
+		    total += e->count;
+		  bb->count = total;
+		  bi->count_valid = 1;
 		  changes = 1;
 		}
 	    }
-	  if (binfo->count_valid)
+	  if (bi->count_valid)
 	    {
-	      if (binfo->succ_count == 1)
+	      if (bi->succ_count == 1)
 		{
-		  total = 0;
+		  edge e;
+		  gcov_type total = 0;
+
 		  /* One of the counts will be invalid, but it is zero,
 		     so adding it in also doesn't hurt.  */
-		  for (arcptr = binfo->succ; arcptr;
-		       arcptr = arcptr->succ_next)
-		    total += ARC_COUNT (arcptr);
-		  /* Calculate count for remaining arc by conservation.  */
-		  total = binfo->exec_count - total;
-		  /* Search for the invalid arc, and set its count.  */
-		  for (arcptr = binfo->succ; arcptr;
-		       arcptr = arcptr->succ_next)
-		    if (! arcptr->count_valid)
+		  for (e = bb->succ; e; e = e->succ_next)
+		    total += e->count;
+
+		  /* Seedgeh for the invalid edge, and set its count.  */
+		  for (e = bb->succ; e; e = e->succ_next)
+		    if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore)
 		      break;
-		  if (! arcptr)
+
+		  /* Calculate count for remaining edge by conservation.  */
+		  total = bb->count - total;
+
+		  if (! e)
 		    abort ();
-		  arcptr->count_valid = 1;
-		  ARC_COUNT (arcptr) = total;
-		  binfo->succ_count--;
-		  
-		  bb_graph[ARC_TARGET (arcptr)].pred_count--;
+		  EDGE_INFO (e)->count_valid = 1;
+		  e->count = total;
+		  bi->succ_count--;
+
+		  BB_INFO (e->dest)->pred_count--;
 		  changes = 1;
 		}
-	      if (binfo->pred_count == 1)
+	      if (bi->pred_count == 1)
 		{
-		  total = 0;
+		  edge e;
+		  gcov_type total = 0;
+
 		  /* One of the counts will be invalid, but it is zero,
 		     so adding it in also doesn't hurt.  */
-		  for (arcptr = binfo->pred; arcptr;
-		       arcptr = arcptr->pred_next)
-		    total += ARC_COUNT (arcptr);
-		  /* Calculate count for remaining arc by conservation.  */
-		  total = binfo->exec_count - total;
-		  /* Search for the invalid arc, and set its count.  */
-		  for (arcptr = binfo->pred; arcptr;
-		       arcptr = arcptr->pred_next)
-		    if (! arcptr->count_valid)
+		  for (e = bb->pred; e; e = e->pred_next)
+		    total += e->count;
+
+		  /* Seedgeh for the invalid edge, and set its count.  */
+		  for (e = bb->pred; e; e = e->pred_next)
+		    if (! EDGE_INFO (e)->count_valid && ! EDGE_INFO (e)->ignore)
 		      break;
-		  if (! arcptr)
+
+		  /* Calculate count for remaining edge by conservation.  */
+		  total = bb->count - total + e->count;
+
+		  if (! e)
 		    abort ();
-		  arcptr->count_valid = 1;
-		  ARC_COUNT (arcptr) = total;
-		  binfo->pred_count--;
-		  
-		  bb_graph[ARC_SOURCE (arcptr)].succ_count--;
+		  EDGE_INFO (e)->count_valid = 1;
+		  e->count = total;
+		  bi->pred_count--;
+
+		  BB_INFO (e->src)->succ_count--;
 		  changes = 1;
 		}
 	    }
 	}
     }
+  if (rtl_dump_file)
+    dump_flow_info (rtl_dump_file);
 
   total_num_passes += passes;
-  if (dump_file)
-    fprintf (dump_file, "Graph solving took %d passes.\n\n", passes);
+  if (rtl_dump_file)
+    fprintf (rtl_dump_file, "Graph solving took %d passes.\n\n", passes);
 
   /* If the graph has been correctly solved, every block will have a
      succ and pred count of zero.  */
-  for (i = 0; i < num_blocks; i++)
+  for (i = 0; i < n_basic_blocks; i++)
     {
-      struct bb_info *binfo = &bb_graph[i];
-      if (binfo->succ_count || binfo->pred_count)
+      basic_block bb = BASIC_BLOCK (i);
+      if (BB_INFO (bb)->succ_count || BB_INFO (bb)->pred_count)
 	abort ();
     }
 
-  /* For every arc, calculate its branch probability and add a reg_note
+  /* For every edge, calculate its branch probability and add a reg_note
      to the branch insn to indicate this.  */
 
   for (i = 0; i < 20; i++)
@@ -1118,289 +411,520 @@ branch_prob (f, dump_file)
   num_never_executed = 0;
   num_branches = 0;
 
-  for (i = 0; i < num_blocks; i++)
+  for (i = 0; i <= n_basic_blocks + 1; i++)
     {
-      struct bb_info *binfo = &bb_graph[i];
+      basic_block bb = GCOV_INDEX_TO_BB (i);
+      edge e;
+      gcov_type total;
+      rtx note;
 
-      total = binfo->exec_count;
-      for (arcptr = binfo->succ; arcptr; arcptr = arcptr->succ_next)
+      total = bb->count;
+      if (total)
 	{
-	  if (arcptr->branch_insn)
+	  for (e = bb->succ; e; e = e->succ_next)
 	    {
-	      /* This calculates the branch probability as an integer between
-		 0 and REG_BR_PROB_BASE, properly rounded to the nearest
-		 integer.  Perform the arithmetic in double to avoid
-		 overflowing the range of ints.  */
-
-	      if (total == 0)
-		prob = -1;
-	      else
-		{
-		  rtx pat = PATTERN (arcptr->branch_insn);
-		  
-		  prob = (((double)ARC_COUNT (arcptr) * REG_BR_PROB_BASE)
-			  + (total >> 1)) / total;
-		  if (prob < 0 || prob > REG_BR_PROB_BASE)
-		    {
-		      if (dump_file)
-			fprintf (dump_file, "bad count: prob for %d-%d thought to be %d (forcibly normalized)\n",
-				 ARC_SOURCE (arcptr), ARC_TARGET (arcptr),
-				 prob);
-
-		      bad_counts = 1;
-		      prob = REG_BR_PROB_BASE / 2;
-		    }
-		  
-		  /* Match up probability with JUMP pattern.  */
-
-		  if (GET_CODE (pat) == SET
-		      && GET_CODE (SET_SRC (pat)) == IF_THEN_ELSE)
-		    {
-		      if (ARC_TARGET (arcptr) == ARC_SOURCE (arcptr) + 1)
-			{
-			  /* A fall through arc should never have a
-			     branch insn.  */
-			  abort ();
-			}
-		      else
-			{
-			  /* This is the arc for the taken branch.  */
-			  if (GET_CODE (XEXP (SET_SRC (pat), 2)) != PC)
-			    prob = REG_BR_PROB_BASE - prob;
-			}
-		    }
-		}
-	      
-	      if (prob == -1)
-		num_never_executed++;
+		e->probability = (e->count * REG_BR_PROB_BASE + total / 2) / total;
+		if (e->probability < 0 || e->probability > REG_BR_PROB_BASE)
+		  {
+		    error ("corrupted profile info: prob for %d-%d thought to be %d",
+			   e->src->index, e->dest->index, e->probability);
+		    e->probability = REG_BR_PROB_BASE / 2;
+		  }
+	    }
+	  if (bb->index >= 0
+	      && any_condjump_p (bb->end)
+	      && bb->succ->succ_next)
+	    {
+	      int prob;
+	      edge e;
+	      int index;
+
+	      /* Find the branch edge.  It is possible that we do have fake
+		 edges here.  */
+	      for (e = bb->succ; e->flags & (EDGE_FAKE | EDGE_FALLTHRU);
+		   e = e->succ_next)
+		continue; /* Loop body has been intentionally left blank.  */
+
+	      prob = e->probability;
+	      index = prob * 20 / REG_BR_PROB_BASE;
+
+	      if (index == 20)
+		index = 19;
+	      hist_br_prob[index]++;
+
+	      note = find_reg_note (bb->end, REG_BR_PROB, 0);
+	      /* There may be already note put by some other pass, such
+		 as builtin_expect expander.  */
+	      if (note)
+		XEXP (note, 0) = GEN_INT (prob);
 	      else
-		{
-		  int index = prob * 20 / REG_BR_PROB_BASE;
-		  if (index == 20)
-		    index = 19;
-		  hist_br_prob[index]++;
-		}
+		REG_NOTES (bb->end)
+		  = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
+				       REG_NOTES (bb->end));
 	      num_branches++;
-	      
-	      REG_NOTES (arcptr->branch_insn)
-		= gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
-				     REG_NOTES (arcptr->branch_insn));
 	    }
 	}
-
-      /* Add a REG_EXEC_COUNT note to the first instruction of this block.  */
-      if (! binfo->first_insn 
-	  || GET_RTX_CLASS (GET_CODE (binfo->first_insn)) != 'i')
-	{
-	  /* Block 0 is a fake block representing function entry, and does
-	     not have a real first insn.  The second last block might not
-	     begin with a real insn.  */
-	  if (i == num_blocks - 1)
-	    return_label_execution_count = total;
-	  else if (i != 0 && i != num_blocks - 2)
-	    abort ();
-	}
+      /* Otherwise distribute the probabilities evenly so we get sane sum.
+	 Use simple heuristics that if there are normal edges, give all abnormals
+	 frequency of 0, otherwise distribute the frequency over abnormals
+	 (this is the case of noreturn calls).  */
       else
 	{
-	  REG_NOTES (binfo->first_insn)
-	    = gen_rtx_EXPR_LIST (REG_EXEC_COUNT, GEN_INT (total),
-				 REG_NOTES (binfo->first_insn));
-	  if (i == num_blocks - 1)
-	    return_label_execution_count = total;
+	  for (e = bb->succ; e; e = e->succ_next)
+	    if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
+	      total ++;
+	  if (total)
+	    {
+	      for (e = bb->succ; e; e = e->succ_next)
+		if (!(e->flags & (EDGE_COMPLEX | EDGE_FAKE)))
+		  e->probability = REG_BR_PROB_BASE / total;
+		else
+		  e->probability = 0;
+	    }
+	  else
+	    {
+	      for (e = bb->succ; e; e = e->succ_next)
+		total ++;
+	      for (e = bb->succ; e; e = e->succ_next)
+		e->probability = REG_BR_PROB_BASE / total;
+	    }
+	  if (bb->index >= 0
+	      && any_condjump_p (bb->end)
+	      && bb->succ->succ_next)
+	    num_branches++, num_never_executed;
 	}
     }
-  
-  /* This should never happen.  */
-  if (bad_counts)
-    warning ("Arc profiling: some arc counts were bad.");
 
-  if (dump_file)
+  if (rtl_dump_file)
     {
-      fprintf (dump_file, "%d branches\n", num_branches);
-      fprintf (dump_file, "%d branches never executed\n",
+      fprintf (rtl_dump_file, "%d branches\n", num_branches);
+      fprintf (rtl_dump_file, "%d branches never executed\n",
 	       num_never_executed);
       if (num_branches)
 	for (i = 0; i < 10; i++)
-	  fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
-		   (hist_br_prob[i]+hist_br_prob[19-i])*100/num_branches,
-		   5*i, 5*i+5);
+	  fprintf (rtl_dump_file, "%d%% branches in range %d-%d%%\n",
+		   (hist_br_prob[i] + hist_br_prob[19-i]) * 100 / num_branches,
+		   5 * i, 5 * i + 5);
 
       total_num_branches += num_branches;
       total_num_never_executed += num_never_executed;
       for (i = 0; i < 20; i++)
 	total_hist_br_prob[i] += hist_br_prob[i];
+
+      fputc ('\n', rtl_dump_file);
+      fputc ('\n', rtl_dump_file);
     }
 
+  free_aux_for_blocks ();
 }
-
-/* Initialize a new arc.
-   ARCPTR is the empty adj_list this function fills in.
-   SOURCE is the block number of the source block.
-   TARGET is the block number of the target block.
-   INSN is the insn which transfers control from SOURCE to TARGET,
-   or zero if the transfer is implicit.  */
 
-static void
-init_arc (arcptr, source, target, insn)
-     struct adj_list *arcptr;
-     int source, target;
-     rtx insn;
-{
-  ARC_TARGET (arcptr) = target;
-  ARC_SOURCE (arcptr) = source;
-
-  ARC_COUNT (arcptr) = 0;
-  arcptr->count_valid = 0;
-  arcptr->on_tree = 0;
-  arcptr->fake = 0;
-  arcptr->fall_through = 0;
-  arcptr->branch_insn = insn;
-
-  arcptr->succ_next = bb_graph[source].succ;
-  bb_graph[source].succ = arcptr;
-  bb_graph[source].succ_count++;
-
-  arcptr->pred_next = bb_graph[target].pred;
-  bb_graph[target].pred = arcptr;
-  bb_graph[target].pred_count++;
-}
+/* Instrument and/or analyze program behavior based on program flow graph.
+   In either case, this function builds a flow graph for the function being
+   compiled.  The flow graph is stored in BB_GRAPH.
 
-/* This function searches all of the arcs in the program flow graph, and puts
-   as many bad arcs as possible onto the spanning tree.  Bad arcs include
-   fake arcs (needed for setjmp(), longjmp(), exit()) which MUST be on the
-   spanning tree as they can't be instrumented.  Also, arcs which must be
-   split when instrumented should be part of the spanning tree if possible.  */
+   When FLAG_PROFILE_ARCS is nonzero, this function instruments the edges in
+   the flow graph that are needed to reconstruct the dynamic behavior of the
+   flow graph.
 
-static void
-find_spanning_tree (num_blocks)
-     int num_blocks;
+   When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
+   information from a data file containing edge count information from previous
+   executions of the function being compiled.  In this case, the flow graph is
+   annotated with actual execution counts, which are later propagated into the
+   rtl for optimization purposes.
+
+   Main entry point of this file.  */
+
+void
+branch_prob ()
 {
   int i;
-  struct adj_list *arcptr;
-  struct bb_info *binfo = &bb_graph[0];
-
-  /* Fake arcs must be part of the spanning tree, and are always safe to put
-     on the spanning tree.  Fake arcs will either be a successor of node 0,
-     a predecessor of the last node, or from the last node to node 0.  */
-
-  for (arcptr = bb_graph[0].succ; arcptr; arcptr = arcptr->succ_next)
-    if (arcptr->fake)
-      {
-	/* Adding this arc should never cause a cycle.  This is a fatal 
-	   error if it would.  */
-	if (bb_graph[ARC_TARGET (arcptr)].on_tree && binfo->on_tree)
-	  abort();
-	else
-	  {
-	    arcptr->on_tree = 1;
-	    bb_graph[ARC_TARGET (arcptr)].on_tree = 1;
-	    binfo->on_tree = 1;
-	  }
-      }
-
-  binfo = &bb_graph[num_blocks-1];
-  for (arcptr = binfo->pred; arcptr; arcptr = arcptr->pred_next)
-    if (arcptr->fake)
-      {
-	/* Adding this arc should never cause a cycle.  This is a fatal 
-	   error if it would.  */
-	if (bb_graph[ARC_SOURCE (arcptr)].on_tree && binfo->on_tree)
-	  abort();
-	else
-	  {
-	    arcptr->on_tree = 1;
-	    bb_graph[ARC_SOURCE (arcptr)].on_tree = 1;
-	    binfo->on_tree = 1;
-	  }
-      }
-  /* The only entrace to node zero is a fake arc.  */
-  bb_graph[0].pred->on_tree = 1;
-  
-  /* Arcs which are crowded at both the source and target should be put on
-     the spanning tree if possible, except for fall_throuch arcs which never
-     require adding a new block even if crowded, add arcs with the same source
-     and dest which must always be instrumented.  */
-  for (i = 0; i < num_blocks; i++)
+  int num_edges, ignored_edges;
+  struct edge_list *el;
+
+  /* Start of a function.  */
+  if (flag_test_coverage)
+    output_gcov_string (current_function_name, (long) -2);
+
+  total_num_times_called++;
+
+  flow_call_edges_add (NULL);
+  add_noreturn_fake_exit_edges ();
+
+  /* We can't handle cyclic regions constructed using abnormal edges.
+     To avoid these we replace every source of abnormal edge by a fake
+     edge from entry node and every destination by fake edge to exit.
+     This keeps graph acyclic and our calculation exact for all normal
+     edges except for exit and entrance ones.
+
+     We also add fake exit edges for each call and asm statement in the
+     basic, since it may not return.  */
+
+  for (i = 0; i < n_basic_blocks ; i++)
     {
-      binfo = &bb_graph[i];
-
-      for (arcptr = binfo->succ; arcptr; arcptr = arcptr->succ_next)
-	if (! ((binfo->succ == arcptr && arcptr->succ_next == 0)
-	       || (bb_graph[ARC_TARGET (arcptr)].pred
-		   && arcptr->pred_next == 0))
-	    && ! arcptr->fall_through
-	    && ARC_TARGET (arcptr) != i)
-	  {
-	    /* This is a crowded arc at both source and target.  Try to put
-	       in on the spanning tree.  Can do this if either the source or
-	       target block is not yet on the tree.  */
-	    if (! bb_graph[ARC_TARGET (arcptr)].on_tree	|| ! binfo->on_tree)
-	      {
-		arcptr->on_tree = 1;
-		bb_graph[ARC_TARGET (arcptr)].on_tree = 1;
-		binfo->on_tree = 1;
-	      }
-	  }
+      int need_exit_edge = 0, need_entry_edge = 0;
+      int have_exit_edge = 0, have_entry_edge = 0;
+      basic_block bb = BASIC_BLOCK (i);
+      rtx insn;
+      edge e;
+
+      /* Add fake edges from entry block to the call insns that may return
+	 twice.  The CFG is not quite correct then, as call insn plays more
+	 role of CODE_LABEL, but for our purposes, everything should be OK,
+	 as we never insert code to the beggining of basic block.  */
+      for (insn = bb->head; insn != NEXT_INSN (bb->end);
+	   insn = NEXT_INSN (insn))
+	{
+	  if (GET_CODE (insn) == CALL_INSN
+	      && find_reg_note (insn, REG_SETJMP, NULL))
+	    {
+	      if (GET_CODE (bb->head) == CODE_LABEL
+		  || insn != NEXT_INSN (bb->head))
+		{
+		  e = split_block (bb, PREV_INSN (insn));
+		  make_edge (ENTRY_BLOCK_PTR, e->dest, EDGE_FAKE);
+		  break;
+		}
+	      else
+		{
+		  /* We should not get abort here, as call to setjmp should not
+		     be the very first instruction of function.  */
+		  if (!i)
+		    abort ();
+		  make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE);
+		}
+	    }
+	}
+
+      for (e = bb->succ; e; e = e->succ_next)
+	{
+	  if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
+	       && e->dest != EXIT_BLOCK_PTR)
+	    need_exit_edge = 1;
+	  if (e->dest == EXIT_BLOCK_PTR)
+	    have_exit_edge = 1;
+	}
+      for (e = bb->pred; e; e = e->pred_next)
+	{
+	  if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
+	       && e->src != ENTRY_BLOCK_PTR)
+	    need_entry_edge = 1;
+	  if (e->src == ENTRY_BLOCK_PTR)
+	    have_entry_edge = 1;
+	}
+
+      if (need_exit_edge && !have_exit_edge)
+	{
+	  if (rtl_dump_file)
+	    fprintf (rtl_dump_file, "Adding fake exit edge to bb %i\n",
+		     bb->index);
+          make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
+	}
+      if (need_entry_edge && !have_entry_edge)
+	{
+	  if (rtl_dump_file)
+	    fprintf (rtl_dump_file, "Adding fake entry edge to bb %i\n",
+		     bb->index);
+          make_edge (ENTRY_BLOCK_PTR, bb, EDGE_FAKE);
+	}
     }
 
-  /* Clear all of the basic block on_tree bits, so that we can use them to
-     create the spanning tree.  */
-  for (i = 0; i < num_blocks; i++)
-    bb_graph[i].on_tree = 0;
+  el = create_edge_list ();
+  num_edges = NUM_EDGES (el);
+  alloc_aux_for_edges (sizeof (struct edge_info));
+
+  ignored_edges = 0;
+  for (i = 0 ; i < num_edges ; i++)
+    {
+      edge e = INDEX_EDGE (el, i);
+      e->count = 0;
+
+      /* Mark edges we've replaced by fake edges above as ignored.  */
+      if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
+	  && e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR)
+        {
+	  EDGE_INFO (e)->ignore = 1;
+	  ignored_edges++;
+        }
+    }
 
-  /* Now fill in the spanning tree until every basic block is on it.
-     Don't put the 0 to 1 fall through arc on the tree, since it is 
-     always cheap to instrument, so start filling the tree from node 1.  */
+#ifdef ENABLE_CHECKING
+  verify_flow_info ();
+#endif
 
-  for (i = 1; i < num_blocks; i++)
-    for (arcptr = bb_graph[i].succ; arcptr; arcptr = arcptr->succ_next)
-      if (! arcptr->on_tree
-	  && ! bb_graph[ARC_TARGET (arcptr)].on_tree)
+  /* Output line number information about each basic block for
+     GCOV utility.  */
+  if (flag_test_coverage)
+    {
+      int i = 0;
+      for (i = 0 ; i < n_basic_blocks; i++)
+        {
+	  basic_block bb = BASIC_BLOCK (i);
+	  rtx insn = bb->head;
+          static int ignore_next_note = 0;
+
+	  /* We are looking for line number notes.  Search backward before
+	     basic block to find correct ones.  */
+	  insn = prev_nonnote_insn (insn);
+	  if (!insn)
+	    insn = get_insns ();
+	  else
+	    insn = NEXT_INSN (insn);
+
+	  /* Output a zero to the .bb file to indicate that a new
+	     block list is starting.  */
+	  __write_long (0, bb_file, 4);
+
+	  while (insn != bb->end)
+	    {
+	      if (GET_CODE (insn) == NOTE)
+		{
+		  /* Must ignore the line number notes that immediately
+		     follow the end of an inline function to avoid counting
+		     it twice.  There is a note before the call, and one
+		     after the call.  */
+		  if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_REPEATED_LINE_NUMBER)
+		    ignore_next_note = 1;
+		  else if (NOTE_LINE_NUMBER (insn) > 0)
+		    {
+		      if (ignore_next_note)
+			ignore_next_note = 0;
+		      else
+			{
+			  /* If this is a new source file, then output the
+			     file's name to the .bb file.  */
+			  if (! last_bb_file_name
+			      || strcmp (NOTE_SOURCE_FILE (insn),
+					 last_bb_file_name))
+			    {
+			      if (last_bb_file_name)
+				free (last_bb_file_name);
+			      last_bb_file_name
+				= xstrdup (NOTE_SOURCE_FILE (insn));
+			      output_gcov_string (NOTE_SOURCE_FILE (insn),
+						  (long)-1);
+			    }
+			  /* Output the line number to the .bb file.  Must be
+			     done after the output_bb_profile_data() call, and
+			     after the file name is written, to ensure that it
+			     is correctly handled by gcov.  */
+			  __write_long (NOTE_LINE_NUMBER (insn), bb_file, 4);
+			}
+		    }
+		}
+	      insn = NEXT_INSN (insn);
+	    }
+        }
+      __write_long (0, bb_file, 4);
+    }
+
+  /* Create spanning tree from basic block graph, mark each edge that is
+     on the spanning tree.  We insert as many abnormal and critical edges
+     as possible to minimize number of edge splits necessary.  */
+
+  find_spanning_tree (el);
+
+  /* Fake edges that are not on the tree will not be instrumented, so
+     mark them ignored.  */
+  for (i = 0; i < num_edges; i++)
+    {
+      edge e = INDEX_EDGE (el, i);
+      struct edge_info *inf = EDGE_INFO (e);
+      if ((e->flags & EDGE_FAKE) && !inf->ignore && !inf->on_tree)
+        {
+          inf->ignore = 1;
+          ignored_edges++;
+        }
+    }
+
+  total_num_blocks += n_basic_blocks + 2;
+  if (rtl_dump_file)
+    fprintf (rtl_dump_file, "%d basic blocks\n", n_basic_blocks);
+
+  total_num_edges += num_edges;
+  if (rtl_dump_file)
+    fprintf (rtl_dump_file, "%d edges\n", num_edges);
+
+  total_num_edges_ignored += ignored_edges;
+  if (rtl_dump_file)
+    fprintf (rtl_dump_file, "%d ignored edges\n", ignored_edges);
+
+  /* Create a .bbg file from which gcov can reconstruct the basic block
+     graph.  First output the number of basic blocks, and then for every
+     edge output the source and target basic block numbers.
+     NOTE: The format of this file must be compatible with gcov.  */
+
+  if (flag_test_coverage)
+    {
+      int flag_bits;
+
+      /* The plus 2 stands for entry and exit block.  */
+      __write_long (n_basic_blocks + 2, bbg_file, 4);
+      __write_long (num_edges - ignored_edges + 1, bbg_file, 4);
+
+      for (i = 0; i < n_basic_blocks + 1; i++)
 	{
-	  fill_spanning_tree (i);
-	  break;
+	  basic_block bb = GCOV_INDEX_TO_BB (i);
+	  edge e;
+	  long count = 0;
+
+	  for (e = bb->succ; e; e = e->succ_next)
+	    if (!EDGE_INFO (e)->ignore)
+	      count++;
+	  __write_long (count, bbg_file, 4);
+
+	  for (e = bb->succ; e; e = e->succ_next)
+	    {
+	      struct edge_info *i = EDGE_INFO (e);
+	      if (!i->ignore)
+		{
+		  flag_bits = 0;
+		  if (i->on_tree)
+		    flag_bits |= 0x1;
+		  if (e->flags & EDGE_FAKE)
+		    flag_bits |= 0x2;
+		  if (e->flags & EDGE_FALLTHRU)
+		    flag_bits |= 0x4;
+
+		  __write_long (BB_TO_GCOV_INDEX (e->dest), bbg_file, 4);
+		  __write_long (flag_bits, bbg_file, 4);
+	        }
+	    }
 	}
+      /* Emit fake loopback edge for EXIT block to maintain compatibility with
+         old gcov format.  */
+      __write_long (1, bbg_file, 4);
+      __write_long (0, bbg_file, 4);
+      __write_long (0x1, bbg_file, 4);
+
+      /* Emit a -1 to separate the list of all edges from the list of
+	 loop back edges that follows.  */
+      __write_long (-1, bbg_file, 4);
+    }
+
+  if (flag_branch_probabilities)
+    compute_branch_probabilities ();
+
+  /* For each edge not on the spanning tree, add counting code as rtl.  */
+
+  if (profile_arc_flag)
+    {
+      instrument_edges (el);
+      allocate_reg_info (max_reg_num (), FALSE, FALSE);
+    }
+
+  remove_fake_edges ();
+  /* Re-merge split basic blocks and the mess introduced by
+     insert_insn_on_edge.  */
+  cleanup_cfg (profile_arc_flag ? CLEANUP_EXPENSIVE : 0);
+  if (rtl_dump_file)
+    dump_flow_info (rtl_dump_file);
+
+  free_aux_for_edges ();
+  free_edge_list (el);
 }
+
+/* Union find algorithm implementation for the basic blocks using
+   aux fields.  */
+
+static basic_block
+find_group (bb)
+     basic_block bb;
+{
+  basic_block group = bb, bb1;
+
+  while ((basic_block) group->aux != group)
+    group = (basic_block) group->aux;
 
-/* Add arcs reached from BLOCK to the spanning tree if they are needed and
-   not already there.  */
+  /* Compress path.  */
+  while ((basic_block) bb->aux != group)
+    {
+      bb1 = (basic_block) bb->aux;
+      bb->aux = (void *) group;
+      bb = bb1;
+    }
+  return group;
+}
 
 static void
-fill_spanning_tree (block)
-     int block;
+union_groups (bb1, bb2)
+     basic_block bb1, bb2;
 {
-  struct adj_list *arcptr;
-  
-  expand_spanning_tree (block);
-
-  for (arcptr = bb_graph[block].succ; arcptr; arcptr = arcptr->succ_next)
-    if (! arcptr->on_tree
-	&& ! bb_graph[ARC_TARGET (arcptr)].on_tree)
-      {
-	arcptr->on_tree = 1;
-	fill_spanning_tree (ARC_TARGET (arcptr));
-      }
-}
+  basic_block bb1g = find_group (bb1);
+  basic_block bb2g = find_group (bb2);
+
+  /* ??? I don't have a place for the rank field.  OK.  Lets go w/o it,
+     this code is unlikely going to be performance problem anyway.  */
+  if (bb1g == bb2g)
+    abort ();
 
-/* When first visit a block, must add all blocks that are already connected
-   to this block via tree arcs to the spanning tree.  */
+  bb1g->aux = bb2g;
+}
+
+/* This function searches all of the edges in the program flow graph, and puts
+   as many bad edges as possible onto the spanning tree.  Bad edges include
+   abnormals edges, which can't be instrumented at the moment.  Since it is
+   possible for fake edges to form an cycle, we will have to develop some
+   better way in the future.  Also put critical edges to the tree, since they
+   are more expensive to instrument.  */
 
 static void
-expand_spanning_tree (block)
-     int block;
+find_spanning_tree (el)
+     struct edge_list *el;
 {
-  struct adj_list *arcptr;
-
-  bb_graph[block].on_tree = 1;
-
-  for (arcptr = bb_graph[block].succ; arcptr; arcptr = arcptr->succ_next)
-    if (arcptr->on_tree && ! bb_graph[ARC_TARGET (arcptr)].on_tree)
-      expand_spanning_tree (ARC_TARGET (arcptr));
-    
-  for (arcptr = bb_graph[block].pred;
-       arcptr; arcptr = arcptr->pred_next)
-    if (arcptr->on_tree && ! bb_graph[ARC_SOURCE (arcptr)].on_tree)
-      expand_spanning_tree (ARC_SOURCE (arcptr));
+  int i;
+  int num_edges = NUM_EDGES (el);
+
+  /* We use aux field for standard union-find algorithm.  */
+  EXIT_BLOCK_PTR->aux = EXIT_BLOCK_PTR;
+  ENTRY_BLOCK_PTR->aux = ENTRY_BLOCK_PTR;
+  for (i = 0; i < n_basic_blocks; i++)
+    BASIC_BLOCK (i)->aux = BASIC_BLOCK (i);
+
+  /* Add fake edge exit to entry we can't instrument.  */
+  union_groups (EXIT_BLOCK_PTR, ENTRY_BLOCK_PTR);
+
+  /* First add all abnormal edges to the tree unless they form an cycle.  */
+  for (i = 0; i < num_edges; i++)
+    {
+      edge e = INDEX_EDGE (el, i);
+      if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_FAKE))
+	  && !EDGE_INFO (e)->ignore
+	  && (find_group (e->src) != find_group (e->dest)))
+	{
+	  EDGE_INFO (e)->on_tree = 1;
+	  union_groups (e->src, e->dest);
+	}
+    }
+
+  /* Now insert all critical edges to the tree unless they form an cycle.  */
+  for (i = 0; i < num_edges; i++)
+    {
+      edge e = INDEX_EDGE (el, i);
+      if ((EDGE_CRITICAL_P (e))
+	  && !EDGE_INFO (e)->ignore
+	  && (find_group (e->src) != find_group (e->dest)))
+	{
+	  EDGE_INFO (e)->on_tree = 1;
+	  union_groups (e->src, e->dest);
+	}
+    }
+
+  /* And now the rest.  */
+  for (i = 0; i < num_edges; i++)
+    {
+      edge e = INDEX_EDGE (el, i);
+      if (find_group (e->src) != find_group (e->dest)
+	  && !EDGE_INFO (e)->ignore)
+	{
+	  EDGE_INFO (e)->on_tree = 1;
+	  union_groups (e->src, e->dest);
+	}
+    }
+
+  EXIT_BLOCK_PTR->aux = NULL;
+  ENTRY_BLOCK_PTR->aux = NULL;
+  for (i = 0; i < n_basic_blocks; i++)
+    BASIC_BLOCK (i)->aux = NULL;
 }
 
 /* Perform file-level initialization for branch-prob processing.  */
@@ -1414,23 +938,24 @@ init_branch_prob (filename)
 
   if (flag_test_coverage)
     {
-      /* Open an output file for the basic block/line number map.  */
       int len = strlen (filename);
-      char *data_file = (char *) alloca (len + 4);
+      char *data_file, *bbg_file_name;
+
+      /* Open an output file for the basic block/line number map.  */
+      data_file = (char *) alloca (len + 4);
       strcpy (data_file, filename);
       strip_off_ending (data_file, len);
       strcat (data_file, ".bb");
-      if ((bb_file = fopen (data_file, "w")) == 0)
-	pfatal_with_name (data_file);
+      if ((bb_file = fopen (data_file, "wb")) == 0)
+	fatal_io_error ("can't open %s", data_file);
 
       /* Open an output file for the program flow graph.  */
-      len = strlen (filename);
       bbg_file_name = (char *) alloca (len + 5);
       strcpy (bbg_file_name, filename);
       strip_off_ending (bbg_file_name, len);
       strcat (bbg_file_name, ".bbg");
-      if ((bbg_file = fopen (bbg_file_name, "w")) == 0)
-	pfatal_with_name (bbg_file_name);
+      if ((bbg_file = fopen (bbg_file_name, "wb")) == 0)
+	fatal_io_error ("can't open %s", bbg_file_name);
 
       /* Initialize to zero, to ensure that the first file name will be
 	 written to the .bb file.  */
@@ -1439,28 +964,31 @@ init_branch_prob (filename)
 
   if (flag_branch_probabilities)
     {
+      char *da_file_name;
+
       len = strlen (filename);
       da_file_name = (char *) alloca (len + 4);
       strcpy (da_file_name, filename);
       strip_off_ending (da_file_name, len);
       strcat (da_file_name, ".da");
-      if ((da_file = fopen (da_file_name, "r")) == 0)
-	warning ("file %s not found, execution counts assumed to be zero.",
+      if ((da_file = fopen (da_file_name, "rb")) == 0)
+	warning ("file %s not found, execution counts assumed to be zero",
 		 da_file_name);
 
-      /* The first word in the .da file gives the number of instrumented arcs,
-	 which is not needed for our purposes.  */
+      /* The first word in the .da file gives the number of instrumented
+	 edges, which is not needed for our purposes.  */
 
       if (da_file)
 	__read_long (&len, da_file, 8);
     }
 
   if (profile_arc_flag)
-    init_arc_profiler ();
+    init_edge_profiler ();
 
   total_num_blocks = 0;
-  total_num_arcs = 0;
-  total_num_arcs_instrumented = 0;
+  total_num_edges = 0;
+  total_num_edges_ignored = 0;
+  total_num_edges_instrumented = 0;
   total_num_blocks_created = 0;
   total_num_passes = 0;
   total_num_times_called = 0;
@@ -1474,8 +1002,7 @@ init_branch_prob (filename)
    is completed.  */
 
 void
-end_branch_prob (dump_file)
-     FILE *dump_file;
+end_branch_prob ()
 {
   if (flag_test_coverage)
     {
@@ -1490,182 +1017,140 @@ end_branch_prob (dump_file)
 	  long temp;
 	  /* This seems slightly dangerous, as it presumes the EOF
 	     flag will not be set until an attempt is made to read
-	     past the end of the file. */
+	     past the end of the file.  */
 	  if (feof (da_file))
-	    warning (".da file contents exhausted too early\n");
+	    error (".da file contents exhausted too early");
 	  /* Should be at end of file now.  */
 	  if (__read_long (&temp, da_file, 8) == 0)
-	    warning (".da file contents not exhausted\n");
+	    error (".da file contents not exhausted");
 	  fclose (da_file);
 	}
     }
 
-  if (dump_file)
+  if (rtl_dump_file)
     {
-      fprintf (dump_file, "\n");
-      fprintf (dump_file, "Total number of blocks: %d\n", total_num_blocks);
-      fprintf (dump_file, "Total number of arcs: %d\n", total_num_arcs);
-      fprintf (dump_file, "Total number of instrumented arcs: %d\n",
-	       total_num_arcs_instrumented);
-      fprintf (dump_file, "Total number of blocks created: %d\n",
+      fprintf (rtl_dump_file, "\n");
+      fprintf (rtl_dump_file, "Total number of blocks: %d\n",
+	       total_num_blocks);
+      fprintf (rtl_dump_file, "Total number of edges: %d\n", total_num_edges);
+      fprintf (rtl_dump_file, "Total number of ignored edges: %d\n",
+	       total_num_edges_ignored);
+      fprintf (rtl_dump_file, "Total number of instrumented edges: %d\n",
+	       total_num_edges_instrumented);
+      fprintf (rtl_dump_file, "Total number of blocks created: %d\n",
 	       total_num_blocks_created);
-      fprintf (dump_file, "Total number of graph solution passes: %d\n",
+      fprintf (rtl_dump_file, "Total number of graph solution passes: %d\n",
 	       total_num_passes);
       if (total_num_times_called != 0)
-	fprintf (dump_file, "Average number of graph solution passes: %d\n",
+	fprintf (rtl_dump_file, "Average number of graph solution passes: %d\n",
 		 (total_num_passes + (total_num_times_called  >> 1))
 		 / total_num_times_called);
-      fprintf (dump_file, "Total number of branches: %d\n", total_num_branches);
-      fprintf (dump_file, "Total number of branches never executed: %d\n",
+      fprintf (rtl_dump_file, "Total number of branches: %d\n",
+	       total_num_branches);
+      fprintf (rtl_dump_file, "Total number of branches never executed: %d\n",
 	       total_num_never_executed);
       if (total_num_branches)
 	{
 	  int i;
 
 	  for (i = 0; i < 10; i++)
-	    fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
+	    fprintf (rtl_dump_file, "%d%% branches in range %d-%d%%\n",
 		     (total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100
 		     / total_num_branches, 5*i, 5*i+5);
 	}
     }
 }
 
-/* The label used by the arc profiling code.  */
+/* The label used by the edge profiling code.  */
 
 static rtx profiler_label;
 
 /* Initialize the profiler_label.  */
 
 static void
-init_arc_profiler ()
+init_edge_profiler ()
 {
   /* Generate and save a copy of this so it can be shared.  */
-  char *name = xmalloc (20);
-  ASM_GENERATE_INTERNAL_LABEL (name, "LPBX", 2);
-  profiler_label = gen_rtx_SYMBOL_REF (Pmode, name);
+  char buf[20];
+  ASM_GENERATE_INTERNAL_LABEL (buf, "LPBX", 2);
+  profiler_label = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (buf));
+  ggc_add_rtx_root (&profiler_label, 1);
 }
 
-/* Output instructions as RTL to increment the arc execution count.  */
+/* Output instructions as RTL to increment the edge execution count.  */
 
-static void
-output_arc_profiler (arcno, insert_after)
-     int arcno;
-     rtx insert_after;
+static rtx
+gen_edge_profiler (edgeno)
+     int edgeno;
 {
-  rtx profiler_target_addr
-    = (arcno
-       ? gen_rtx_CONST (Pmode,
-			gen_rtx_PLUS (Pmode, profiler_label,
-				      GEN_INT (LONG_TYPE_SIZE / BITS_PER_UNIT * arcno)))
-       : profiler_label);
-  enum machine_mode mode = mode_for_size (LONG_TYPE_SIZE, MODE_INT, 0);
-  rtx profiler_reg = gen_reg_rtx (mode);
-  rtx address_reg = gen_reg_rtx (Pmode);
-  rtx mem_ref, add_ref;
+  enum machine_mode mode = mode_for_size (GCOV_TYPE_SIZE, MODE_INT, 0);
+  rtx mem_ref, tmp;
   rtx sequence;
 
-  /* In this case, reload can use explicitly mentioned hard registers for
-     reloads.  It is not safe to output profiling code between a call
-     and the instruction that copies the result to a pseudo-reg.  This
-     is because reload may allocate one of the profiling code pseudo-regs
-     to the return value reg, thus clobbering the return value.  So we
-     must check for calls here, and emit the profiling code after the
-     instruction that uses the return value, if any.
-
-     ??? The code here performs the same tests that reload does so hopefully
-     all the bases are covered.  */
-
-  if (SMALL_REGISTER_CLASSES
-      && GET_CODE (insert_after) == CALL_INSN
-      && (GET_CODE (PATTERN (insert_after)) == SET
-	  || (GET_CODE (PATTERN (insert_after)) == PARALLEL
-	      && GET_CODE (XVECEXP (PATTERN (insert_after), 0, 0)) == SET)))
-    {
-      rtx return_reg;
-      rtx next_insert_after = next_nonnote_insn (insert_after);
-
-      /* The first insn after the call may be a stack pop, skip it.  */
-      if (next_insert_after
-	  && GET_CODE (next_insert_after) == INSN
-	  && GET_CODE (PATTERN (next_insert_after)) == SET
-	  && SET_DEST (PATTERN (next_insert_after)) == stack_pointer_rtx)
-	next_insert_after = next_nonnote_insn (next_insert_after);
-
-      if (next_insert_after
-	  && GET_CODE (next_insert_after) == INSN)
-	{
-	  if (GET_CODE (PATTERN (insert_after)) == SET)
-	    return_reg = SET_DEST (PATTERN (insert_after));
-	  else
-	    return_reg = SET_DEST (XVECEXP (PATTERN (insert_after), 0, 0));
-
-	  /* Now, NEXT_INSERT_AFTER may be an instruction that uses the
-	     return value.  However, it could also be something else,
-	     like a CODE_LABEL, so check that the code is INSN.  */
-	  if (next_insert_after != 0
-	      && GET_RTX_CLASS (GET_CODE (next_insert_after)) == 'i'
-	      && reg_referenced_p (return_reg, PATTERN (next_insert_after)))
-	    insert_after = next_insert_after;
-	}
-    }
-
   start_sequence ();
 
-  emit_move_insn (address_reg, profiler_target_addr);
-  mem_ref = gen_rtx_MEM (mode, address_reg);
-  emit_move_insn (profiler_reg, mem_ref);
+  tmp = force_reg (Pmode, profiler_label);
+  tmp = plus_constant (tmp, GCOV_TYPE_SIZE / BITS_PER_UNIT * edgeno);
+  mem_ref = validize_mem (gen_rtx_MEM (mode, tmp));
 
-  add_ref = gen_rtx_PLUS (mode, profiler_reg, GEN_INT (1));
-  emit_move_insn (profiler_reg, add_ref);
+  tmp = expand_simple_binop (mode, PLUS, mem_ref, const1_rtx,
+			     mem_ref, 0, OPTAB_WIDEN);
 
-  /* This is the same rtx as above, but it is not legal to share this rtx.  */
-  mem_ref = gen_rtx_MEM (mode, address_reg);
-  emit_move_insn (mem_ref, profiler_reg);
+  if (tmp != mem_ref)
+    emit_move_insn (copy_rtx (mem_ref), tmp);
 
   sequence = gen_sequence ();
   end_sequence ();
-  emit_insn_after (sequence, insert_after);
+  return sequence;
 }
 
 /* Output code for a constructor that will invoke __bb_init_func, if
-   this has not already been done. */
+   this has not already been done.  */
 
 void
 output_func_start_profiler ()
 {
   tree fnname, fndecl;
-  char *name, *cfnname;
+  char *name;
+  char buf[20];
+  const char *cfnname;
   rtx table_address;
-  enum machine_mode mode = mode_for_size (LONG_TYPE_SIZE, MODE_INT, 0);
+  enum machine_mode mode = mode_for_size (GCOV_TYPE_SIZE, MODE_INT, 0);
   int save_flag_inline_functions = flag_inline_functions;
+  int save_flag_test_coverage = flag_test_coverage;
+  int save_profile_arc_flag = profile_arc_flag;
+  int save_flag_branch_probabilities = flag_branch_probabilities;
 
   /* It's either already been output, or we don't need it because we're
-     not doing profile-arcs. */
+     not doing profile-edges.  */
   if (! need_func_profiler)
     return;
 
   need_func_profiler = 0;
 
   /* Synthesize a constructor function to invoke __bb_init_func with a
-     pointer to this object file's profile block. */
-  start_sequence ();
+     pointer to this object file's profile block.  */
 
   /* Try and make a unique name given the "file function name".
 
-     And no, I don't like this either. */
+     And no, I don't like this either.  */
 
   fnname = get_file_function_name ('I');
   cfnname = IDENTIFIER_POINTER (fnname);
-  name = xmalloc (strlen (cfnname) + 5);
-  sprintf (name, "%sGCOV",cfnname);
+  name = concat (cfnname, "GCOV", NULL);
   fnname = get_identifier (name);
   free (name);
 
   fndecl = build_decl (FUNCTION_DECL, fnname,
 		       build_function_type (void_type_node, NULL_TREE));
   DECL_EXTERNAL (fndecl) = 0;
-  TREE_PUBLIC (fndecl) = 1;
-  DECL_ASSEMBLER_NAME (fndecl) = fnname;
+
+  /* It can be a static function as long as collect2 does not have
+     to scan the object file to find its ctor/dtor routine.  */
+  TREE_PUBLIC (fndecl) = ! targetm.have_ctors_dtors;
+
+  TREE_USED (fndecl) = 1;
+
   DECL_RESULT (fndecl) = build_decl (RESULT_DECL, NULL_TREE, void_type_node);
 
   fndecl = pushdecl (fndecl);
@@ -1673,17 +1158,16 @@ output_func_start_profiler ()
   announce_function (fndecl);
   current_function_decl = fndecl;
   DECL_INITIAL (fndecl) = error_mark_node;
-  temporary_allocation ();
-  pushlevel (0);
-  make_function_rtl (fndecl);
+  make_decl_rtl (fndecl, NULL);
   init_function_start (fndecl, input_filename, lineno);
+  pushlevel (0);
   expand_function_start (fndecl, 0);
 
-  /* Actually generate the code to call __bb_init_func. */
-  name = xmalloc (20);
-  ASM_GENERATE_INTERNAL_LABEL (name, "LPBX", 0);
-  table_address = force_reg (Pmode, gen_rtx_SYMBOL_REF (Pmode, name));
-  emit_library_call (gen_rtx_SYMBOL_REF (Pmode, "__bb_init_func"), 0,
+  /* Actually generate the code to call __bb_init_func.  */
+  ASM_GENERATE_INTERNAL_LABEL (buf, "LPBX", 0);
+  table_address = force_reg (Pmode,
+			     gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (buf)));
+  emit_library_call (gen_rtx_SYMBOL_REF (Pmode, "__bb_init_func"), LCT_NORMAL,
 		     mode, 1, table_address, Pmode);
 
   expand_function_end (input_filename, lineno, 0);
@@ -1694,14 +1178,26 @@ output_func_start_profiler ()
      flag_inline_functions.  */
   flag_inline_functions = 0;
 
+  /* Don't instrument the function that turns on instrumentation.  Which
+     is also handy since we'd get silly warnings about not consuming all
+     of our da_file input.  */
+  flag_test_coverage = 0;
+  profile_arc_flag = 0;
+  flag_branch_probabilities = 0;
+
   rest_of_compilation (fndecl);
 
   /* Reset flag_inline_functions to its original value.  */
   flag_inline_functions = save_flag_inline_functions;
+  flag_test_coverage = save_flag_test_coverage;
+  profile_arc_flag = save_profile_arc_flag;
+  flag_branch_probabilities = save_flag_branch_probabilities;
 
   if (! quiet_flag)
     fflush (asm_out_file);
   current_function_decl = NULL_TREE;
 
-  assemble_constructor (IDENTIFIER_POINTER (DECL_NAME (fndecl)));
+  if (targetm.have_ctors_dtors)
+    (* targetm.asm_out.constructor) (XEXP (DECL_RTL (fndecl), 0),
+				     DEFAULT_INIT_PRIORITY);
 }