Initial revision

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

3 files changed, 3150 insertions, 0 deletions

diff --git a/gcc/gcov-io.h b/gcc/gcov-io.h
new file mode 100644
index 00000000000..59d802ccaed
--- /dev/null
+++ b/gcc/gcov-io.h
@@ -0,0 +1,136 @@
+/* Machine-independent I/O routines for gcov.
+   Copyright (C) 1996, 1997 Free Software Foundation, Inc.
+   Contributed by Bob Manson <manson@cygnus.com>.
+
+This file is part of GNU CC.
+
+GNU CC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+GNU CC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU CC; see the file COPYING.  If not, write to
+the Free Software Foundation, 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA.  */
+
+#ifndef GCOV_IO_H
+#define GCOV_IO_H
+#include <stdio.h>
+
+/* These routines only work for signed values. */
+
+/* Store a portable representation of VALUE in DEST using BYTES*8-1 bits.
+   Return a non-zero value if VALUE requires more than BYTES*8-1 bits
+   to store. */
+
+static int
+__store_long (value, dest, bytes)
+     long value;
+     char *dest;
+     int bytes;
+{
+  int upper_bit = (value < 0 ? 128 : 0);
+  int i;
+
+  if (value < 0)
+    {
+      long oldvalue = value;
+      value = -value;
+      if (oldvalue != -value)
+	return 1;
+    }
+
+  for(i = 0 ; i < (sizeof (value) < bytes ? sizeof (value) : bytes) ; i++) {
+    dest[i] = value & (i == (bytes - 1) ? 127 : 255);
+    value = value / 256;
+  }
+
+  if (value && value != -1)
+    return 1;
+
+  for(; i < bytes ; i++) 
+    dest[i] = 0;
+  dest[bytes - 1] |= upper_bit;
+  return 0;
+}
+
+/* Retrieve a quantity containing BYTES*8-1 bits from SOURCE and store
+   the result in DEST. Returns a non-zero value if the value in SOURCE
+   will not fit in DEST. */
+
+static int
+__fetch_long (dest, source, bytes)
+     long *dest;
+     char *source;
+     int bytes;
+{
+  long value = 0;
+  int i;
+
+  for (i = bytes - 1; i > (sizeof (*dest) - 1); i--)
+    if (source[i] & (i == (bytes - 1) ? 127 : 255 ))
+      return 1;
+
+  for (; i >= 0; i--)
+    value = value * 256 + (source[i] & (i == (bytes - 1) ? 127 : 255));
+
+  if ((source[bytes - 1] & 128) && (value > 0))
+    value = - value;
+
+  *dest = value;
+  return 0;
+}
+
+/* Write a BYTES*8-bit quantity to FILE, portably. Returns a non-zero
+   value if the write fails, or if VALUE can't be stored in BYTES*8
+   bits.
+
+   Note that VALUE may not actually be large enough to hold BYTES*8
+   bits, but BYTES characters will be written anyway.
+
+   BYTES may be a maximum of 10. */
+
+static int
+__write_long (value, file, bytes)
+     long value;
+     FILE *file;
+     int bytes;
+{
+  char c[10];
+
+  if (bytes > 10 || __store_long (value, c, bytes))
+    return 1;
+  else
+    return fwrite(c, 1, bytes, file) != bytes;
+}
+
+/* Read a quantity containing BYTES bytes from FILE, portably. Return
+   a non-zero value if the read fails or if the value will not fit
+   in DEST.
+
+   Note that DEST may not be large enough to hold all of the requested
+   data, but the function will read BYTES characters anyway.
+
+   BYTES may be a maximum of 10. */
+
+static int
+__read_long (dest, file, bytes)
+     long *dest;
+     FILE *file;
+     int bytes;
+{
+  char c[10];
+
+  if (bytes > 10 || fread(c, 1, bytes, file) != bytes)
+    return 1;
+  else
+    return __fetch_long (dest, c, bytes);
+}
+
+#endif
diff --git a/gcc/gcov.c b/gcc/gcov.c
new file mode 100644
index 00000000000..26374c1df6d
--- /dev/null
+++ b/gcc/gcov.c
@@ -0,0 +1,1380 @@
+/* Gcov.c: prepend line execution counts and branch probabilities to a
+   source file.
+   Copyright (C) 1990, 1991, 1992, 1993, 1994, 1996, 1997 Free Software
+   Foundation, Inc.
+   Contributed by James E. Wilson of Cygnus Support.
+   Mongled by Bob Manson of Cygnus Support.
+
+Gcov 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.
+
+Gcov 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 Gcov; see the file COPYING.  If not, write to
+the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
+
+/* ??? The code in final.c that produces the struct bb assumes that there is
+   no padding between the fields.  This is not necessary true.  The current
+   code can only be trusted if longs and pointers are the same size.  */
+
+/* ??? No need to print an execution count on every line, could just print
+   it on the first line of each block, and only print it on a subsequent
+   line in the same block if the count changes.  */
+
+/* ??? Print a list of the ten blocks with the highest execution counts,
+   and list the line numbers corresponding to those blocks.  Also, perhaps
+   list the line numbers with the highest execution counts, only printing
+   the first if there are several which are all listed in the same block.  */
+
+/* ??? Should have an option to print the number of basic blocks, and the
+   percent of them that are covered.  */
+
+/* ??? Does not correctly handle the case where two .bb files refer to the
+   same included source file.  For example, if one has a short file containing
+   only inline functions, which is then included in two other files, then
+   there will be two .bb files which refer to the include file, but there
+   is no way to get the total execution counts for the included file, can
+   only get execution counts for one or the other of the including files.  */
+
+#include <stdio.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+
+/* The only need for this is so that we get macro definitions for rindex
+   if necessary.  */
+#include "config.h"
+
+#include "gcov-io.h"
+
+extern char * rindex ();
+
+/* The .bb file format consists of several lists of 4-byte integers
+   which are the line numbers of each basic block in the file.  Each
+   list is terminated by a zero.  These lists correspond to the basic
+   blocks in the reconstructed program flow graph.
+
+   A line number of -1 indicates that a source file name (padded to a
+   long boundary) follows.  The padded file name is followed by
+   another -1 to make it easy to scan past file names.  A -2 indicates
+   that a function name (padded to a long boundary) follows; the name
+   is followed by another -2 to make it easy to scan past the function
+   name.
+
+   The .bbg file contains enough info to enable gcov to reconstruct the
+   program flow graph.  The first word is the number of basic blocks,
+   the second word is the number of arcs, followed by the list of arcs
+   (source bb, dest bb pairs), then a -1, then the number of instrumented
+   arcs followed by the instrumented arcs, followed by another -1.  This
+   is repeated for each function.
+
+   The .da file contains the execution count for each instrumented branch.
+
+   The .bb and .bbg files are created by giving GCC the -ftest-coverage option,
+   and the .da files are created when an executable compiled with
+   -fprofile-arcs is run.  */
+
+/* The functions in this file for creating and solution program flow graphs
+   are very similar to functions in the gcc source file profile.c.  */
+
+char gcov_version_string[] = "GNU gcov version 1.5\n";
+
+/* This is the size of the buffer used to read in source file lines.  */
+
+#define STRING_SIZE 200
+
+/* One copy of this structure is created for each source file mentioned in the
+   .bb file.  */
+
+struct sourcefile
+{
+  char *name;
+  int maxlineno;
+  struct sourcefile *next;
+};
+
+/* This points to the head of the sourcefile structure list.  */
+
+struct sourcefile *sources;
+
+/* 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;
+#if 0
+  /* Not needed for gcov, but defined in profile.c.  */
+  rtx branch_insn;
+#endif
+  struct adj_list *pred_next;
+  struct adj_list *succ_next;
+};
+
+/* Count the number of basic blocks, and create an array of these structures,
+   one for each bb in the function.  */
+
+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;
+#if 0
+  /* Not needed for gcov, but defined in profile.c.  */
+  rtx first_insn;
+#endif
+};
+
+/* When outputting branch probabilities, one of these structures is created
+   for each branch/call.  */
+
+struct arcdata
+{
+  int prob;
+  int call_insn;
+  struct arcdata *next;
+};
+
+/* Used to save the list of bb_graphs, one per function.  */
+
+struct bb_info_list {
+  /* Indexed by block number, holds the basic block graph for one function.  */
+  struct bb_info *bb_graph;
+  int num_blocks;
+  struct bb_info_list *next;
+};
+
+/* Holds a list of function basic block graphs.  */
+
+static struct bb_info_list *bb_graph_list = 0;
+
+/* Name and file pointer of the input 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;
+
+/* Name and file pointer of the input file for the basic block line counts.  */
+
+static char *bb_file_name;
+static FILE *bb_file;
+
+/* Holds the entire contents of the bb_file read into memory.  */
+
+static char *bb_data;
+
+/* Size of bb_data array in longs.  */
+
+static long bb_data_size;
+
+/* Name and file pointer of the output file.  */
+
+static char *gcov_file_name;
+static FILE *gcov_file;
+
+/* Name of the file mentioned on the command line.  */
+
+static char *input_file_name = 0;
+
+/* Output branch probabilities if true.  */
+
+static int output_branch_probs = 0;
+
+/* Output a gcov file if this is true.  This is on by default, and can
+   be turned off by the -n option.  */
+
+static int output_gcov_file = 1;
+
+/* For included files, make the gcov output file name include the name of
+   the input source file.  For example, if x.h is included in a.c, then the
+   output file name is a.c.x.h.gcov instead of x.h.gcov.  This works only
+   when a single source file is specified.  */
+
+static int output_long_names = 0;
+
+/* Output summary info for each function.  */
+
+static int output_function_summary = 0;
+
+/* Object directory file prefix.  This is the directory where .bb and .bbg
+   files are looked for, if non-zero.  */
+
+static char *object_directory = 0;
+
+/* Forward declarations.  */
+static void process_args ();
+static void open_files ();
+static void read_files ();
+static void scan_for_source_files ();
+static void output_data ();
+char * xmalloc ();
+
+int
+main (argc, argv)
+     int argc;
+     char **argv;
+{
+  process_args (argc, argv);
+
+  open_files ();
+
+  read_files ();
+
+  scan_for_source_files ();
+
+  output_data ();
+
+  return 0;
+}
+
+char *
+xmalloc (size)
+     unsigned size;
+{
+  register char *value = (char *) malloc (size);
+  if (value == 0)
+    {
+      fprintf (stderr, "error: virtual memory exhausted");
+      exit (1);
+    }
+  return value;
+}
+
+/* More 'friendly' abort that prints the line and file.
+   config.h can #define abort fancy_abort if you like that sort of thing.  */
+
+void
+fancy_abort ()
+{
+  fprintf (stderr, "Internal gcc abort.\n");
+  exit (FATAL_EXIT_CODE);
+}
+
+/* Print a usage message and exit.  */
+
+static void
+print_usage ()
+{
+  fprintf (stderr, "gcov [-b] [-v] [-n] [-l] [-f] [-o OBJDIR] file\n");
+  exit (1);
+}
+
+/* Parse the command line.  */
+
+static void
+process_args (argc, argv)
+     int argc;
+     char **argv;
+{
+  int i;
+
+  for (i = 1; i < argc; i++)
+    {
+      if (argv[i][0] == '-')
+	{
+	  if (argv[i][1] == 'b')
+	    output_branch_probs = 1;
+	  else if (argv[i][1] == 'v')
+	    fputs (gcov_version_string, stderr);
+	  else if (argv[i][1] == 'n')
+	    output_gcov_file = 0;
+	  else if (argv[i][1] == 'l')
+	    output_long_names = 1;
+	  else if (argv[i][1] == 'f')
+	    output_function_summary = 1;
+	  else if (argv[i][1] == 'o' && argv[i][2] == '\0')
+	    object_directory = argv[++i];
+	  else
+	    print_usage ();
+	}
+      else if (! input_file_name)
+	input_file_name = argv[i];
+      else
+	print_usage ();
+    }
+
+  if (! input_file_name)
+    print_usage ();
+}
+
+
+/* Find and open the .bb, .da, and .bbg files.  */
+
+static void
+open_files ()
+{
+  int count, objdir_count;
+  char *cptr;
+
+  /* Determine the names of the .bb, .bbg, and .da files.  Strip off the
+     extension, if any, and append the new extensions.  */
+  count = strlen (input_file_name);
+  if (object_directory)
+    objdir_count = strlen (object_directory);
+  else
+    objdir_count = 0;
+
+  da_file_name = xmalloc (count + objdir_count + 4);
+  bb_file_name = xmalloc (count + objdir_count + 4);
+  bbg_file_name = xmalloc (count + objdir_count + 5);
+
+  if (object_directory)
+    {
+      strcpy (da_file_name, object_directory);
+      strcpy (bb_file_name, object_directory);
+      strcpy (bbg_file_name, object_directory);
+
+      if (object_directory[objdir_count - 1] != '/')
+	{
+	  strcat (da_file_name, "/");
+	  strcat (bb_file_name, "/");
+	  strcat (bbg_file_name, "/");
+	}
+
+      cptr = rindex (input_file_name, '/');
+      if (cptr)
+	{
+	  strcat (da_file_name, cptr + 1);
+	  strcat (bb_file_name, cptr + 1);
+	  strcat (bbg_file_name, cptr + 1);
+	}
+      else
+	{
+	  strcat (da_file_name, input_file_name);
+	  strcat (bb_file_name, input_file_name);
+	  strcat (bbg_file_name, input_file_name);
+	}
+    }
+  else
+    {
+      strcpy (da_file_name, input_file_name);
+      strcpy (bb_file_name, input_file_name);
+      strcpy (bbg_file_name, input_file_name);
+    }
+
+  cptr = rindex (bb_file_name, '.');
+  if (cptr)
+    strcpy (cptr, ".bb");
+  else
+    strcat (bb_file_name, ".bb");
+
+  cptr = rindex (da_file_name, '.');
+  if (cptr)
+    strcpy (cptr, ".da");
+  else
+    strcat (da_file_name, ".da");
+
+  cptr = rindex (bbg_file_name, '.');
+  if (cptr)
+    strcpy (cptr, ".bbg");
+  else
+    strcat (bbg_file_name, ".bbg");
+
+  bb_file = fopen (bb_file_name, "r");
+  if (bb_file == NULL)
+    {
+      fprintf (stderr, "Could not open basic block file %s.\n", bb_file_name);
+      exit (1);
+    }
+
+  /* If none of the functions in the file were executed, then there won't
+     be a .da file.  Just assume that all counts are zero in this case.  */
+  da_file = fopen (da_file_name, "r");
+  if (da_file == NULL)
+    {
+      fprintf (stderr, "Could not open data file %s.\n", da_file_name);
+      fprintf (stderr, "Assuming that all execution counts are zero.\n");
+    }
+    
+  bbg_file = fopen (bbg_file_name, "r");
+  if (bbg_file == NULL)
+    {
+      fprintf (stderr, "Could not open program flow graph file %s.\n",
+	       bbg_file_name);
+      exit (1);
+    }
+
+  /* Check for empty .bbg file.  This indicates that there is no executable
+     code in this source file.  */
+  /* Set the EOF condition if at the end of file.  */
+  ungetc (getc (bbg_file), bbg_file);
+  if (feof (bbg_file))
+    {
+      fprintf (stderr, "No executable code associated with file %s.\n",
+	       input_file_name);
+      exit (2);
+    }
+}
+
+/* Initialize a new arc.  */
+
+static void
+init_arc (arcptr, source, target, bb_graph)
+     struct adj_list *arcptr;
+     int source, target;
+     struct bb_info *bb_graph;
+{
+  arcptr->target = target;
+  arcptr->source = source;
+
+  arcptr->arc_count = 0;
+  arcptr->count_valid = 0;
+  arcptr->on_tree = 0;
+  arcptr->fake = 0;
+  arcptr->fall_through = 0;
+
+  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++;
+}
+
+
+/* Reverse the arcs on a arc list.  */
+
+static struct adj_list *
+reverse_arcs (arcptr)
+     struct adj_list *arcptr;
+{
+  struct adj_list *prev = 0;
+  struct adj_list *next;
+
+  for ( ; arcptr; arcptr = next)
+    {
+      next = arcptr->succ_next;
+      arcptr->succ_next = prev;
+      prev = arcptr;
+    }
+
+  return prev;
+}
+
+
+/* Construct the program flow graph from the .bbg file, and read in the data
+   in the .da file.  */
+
+static void
+create_program_flow_graph (bptr)
+     struct bb_info_list *bptr;
+{
+  long num_blocks, number_arcs, src, dest, flag_bits, num_arcs_per_block;
+  int i;
+  struct adj_list *arcptr;
+  struct bb_info *bb_graph;
+
+  /* Read the number of blocks.  */
+  __read_long (&num_blocks, bbg_file, 4);
+
+  /* Create an array of size bb number of bb_info structs.  Bzero it.  */
+  bb_graph = (struct bb_info *) xmalloc (num_blocks
+					 * sizeof (struct bb_info));
+  bzero ((char *) bb_graph, sizeof (struct bb_info) * num_blocks);
+
+  bptr->bb_graph = bb_graph;
+  bptr->num_blocks = num_blocks;
+
+  /* Read and create each arc from the .bbg file.  */
+  __read_long (&number_arcs, bbg_file, 4);
+  for (i = 0; i < num_blocks; i++)
+    {
+      int j;
+
+      __read_long (&num_arcs_per_block, bbg_file, 4);
+      for (j = 0; j < num_arcs_per_block; j++)
+	{
+	  if (number_arcs-- < 0)
+	    abort ();
+
+	  src = i;
+	  __read_long (&dest, bbg_file, 4);
+
+	  arcptr = (struct adj_list *) xmalloc (sizeof (struct adj_list));
+	  init_arc (arcptr, src, dest, bb_graph);
+
+	  __read_long (&flag_bits, bbg_file, 4);
+	  arcptr->on_tree = flag_bits & 0x1;
+	  arcptr->fake = !! (flag_bits & 0x2);
+	  arcptr->fall_through = !! (flag_bits & 0x4);
+	}
+    }
+
+  if (number_arcs)
+    abort ();
+
+  /* Read and ignore the -1 separating the arc list from the arc list of the
+     next function.  */
+  __read_long (&src, bbg_file, 4);
+  if (src != -1)
+    abort ();
+
+  /* Must reverse the order of all succ arcs, to ensure that they match
+     the order of the data in the .da file.  */
+
+  for (i = 0; i < num_blocks; i++)
+    if (bb_graph[i].succ)
+      bb_graph[i].succ = reverse_arcs (bb_graph[i].succ);
+
+  /* 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.  */
+
+  /* This duplicates code in branch_prob in profile.c.  */
+
+  for (i = 0; i < num_blocks; i++)
+    for (arcptr = bb_graph[i].succ; arcptr; arcptr = arcptr->succ_next)
+      if (! arcptr->on_tree)
+	{
+	  long tmp_count = 0;;
+	  if (da_file && __read_long (&tmp_count, da_file, 8))
+	    abort();
+
+	  arcptr->arc_count = tmp_count;
+	  arcptr->count_valid = 1;
+	  bb_graph[i].succ_count--;
+	  bb_graph[arcptr->target].pred_count--;
+	}
+}
+  
+static void
+solve_program_flow_graph (bptr)
+     struct bb_info_list *bptr;
+{
+  int passes, changes, total;
+  int i;
+  struct adj_list *arcptr;
+  struct bb_info *bb_graph;
+  int num_blocks;
+
+  num_blocks = bptr->num_blocks;
+  bb_graph = bptr->bb_graph;
+
+  /* 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
+
+     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.  */
+
+  /* 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
+     faster if we propagate numbers from the end to the start.
+
+     This takes an average of slightly more than 3 passes.  */
+
+  changes = 1;
+  passes = 0;
+  while (changes)
+    {
+      passes++;
+      changes = 0;
+
+      for (i = num_blocks - 1; i >= 0; i--)
+	{
+	  if (! bb_graph[i].count_valid)
+	    {
+	      if (bb_graph[i].succ_count == 0)
+		{
+		  total = 0;
+		  for (arcptr = bb_graph[i].succ; arcptr;
+		       arcptr = arcptr->succ_next)
+		    total += arcptr->arc_count;
+		  bb_graph[i].exec_count = total;
+		  bb_graph[i].count_valid = 1;
+		  changes = 1;
+		}
+	      else if (bb_graph[i].pred_count == 0)
+		{
+		  total = 0;
+		  for (arcptr = bb_graph[i].pred; arcptr;
+		       arcptr = arcptr->pred_next)
+		    total += arcptr->arc_count;
+		  bb_graph[i].exec_count = total;
+		  bb_graph[i].count_valid = 1;
+		  changes = 1;
+		}
+	    }
+	  if (bb_graph[i].count_valid)
+	    {
+	      if (bb_graph[i].succ_count == 1)
+		{
+		  total = 0;
+		  /* One of the counts will be invalid, but it is zero,
+		     so adding it in also doesn't hurt.  */
+		  for (arcptr = bb_graph[i].succ; arcptr;
+		       arcptr = arcptr->succ_next)
+		    total += arcptr->arc_count;
+		  /* Calculate count for remaining arc by conservation.  */
+		  total = bb_graph[i].exec_count - total;
+		  /* Search for the invalid arc, and set its count.  */
+		  for (arcptr = bb_graph[i].succ; arcptr;
+		       arcptr = arcptr->succ_next)
+		    if (! arcptr->count_valid)
+		      break;
+		  if (! arcptr)
+		    abort ();
+		  arcptr->count_valid = 1;
+		  arcptr->arc_count = total;
+		  bb_graph[i].succ_count--;
+
+		  bb_graph[arcptr->target].pred_count--;
+		  changes = 1;
+		}
+	      if (bb_graph[i].pred_count == 1)
+		{
+		  total = 0;
+		  /* One of the counts will be invalid, but it is zero,
+		     so adding it in also doesn't hurt.  */
+		  for (arcptr = bb_graph[i].pred; arcptr;
+		       arcptr = arcptr->pred_next)
+		    total += arcptr->arc_count;
+		  /* Calculate count for remaining arc by conservation.  */
+		  total = bb_graph[i].exec_count - total;
+		  /* Search for the invalid arc, and set its count.  */
+		  for (arcptr = bb_graph[i].pred; arcptr;
+		       arcptr = arcptr->pred_next)
+		    if (! arcptr->count_valid)
+		      break;
+		  if (! arcptr)
+		    abort ();
+		  arcptr->count_valid = 1;
+		  arcptr->arc_count = total;
+		  bb_graph[i].pred_count--;
+
+		  bb_graph[arcptr->source].succ_count--;
+		  changes = 1;
+		}
+	    }
+	}
+    }
+	      
+  /* 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++)
+    if (bb_graph[i].succ_count || bb_graph[i].pred_count)
+      abort ();
+}
+
+
+static void
+read_files ()
+{
+  struct stat buf;
+  struct bb_info_list *list_end = 0;
+  struct bb_info_list *b_ptr;
+  long total, first_time;
+
+  /* Read and ignore the first word of the .da file, which is the count of
+     how many numbers follow.  */
+  if (da_file && __read_long (&total, da_file, 8))
+    abort();
+
+  while (! feof (bbg_file))
+    {
+      b_ptr = (struct bb_info_list *) xmalloc (sizeof (struct bb_info_list));
+
+      b_ptr->next = 0;
+      if (list_end)
+	list_end->next = b_ptr;
+      else
+	bb_graph_list = b_ptr;
+      list_end = b_ptr;
+
+      /* Read in the data in the .bbg file and reconstruct the program flow
+	 graph for one function.  */
+      create_program_flow_graph (b_ptr, first_time);
+
+      /* Set the EOF condition if at the end of file.  */
+      ungetc (getc (bbg_file), bbg_file);
+    }
+
+  /* Check to make sure the .da file data is valid.  */
+
+  if (da_file)
+    {
+      if (feof (da_file))
+	fprintf (stderr, ".da file contents exhausted too early\n");
+      /* Should be at end of file now.  */
+      if (__read_long (&total, da_file, 8) == 0)
+	fprintf (stderr, ".da file contents not exhausted\n");
+    }
+
+  /* Calculate all of the basic block execution counts and branch
+     taken probabilities.  */
+
+  for (b_ptr = bb_graph_list; b_ptr; b_ptr = b_ptr->next)
+    solve_program_flow_graph (b_ptr);
+
+  /* Read in all of the data from the .bb file.   This info will be accessed
+     sequentially twice.  */
+  stat (bb_file_name, &buf);
+  bb_data_size = buf.st_size / 4;
+
+  bb_data = (char *) xmalloc (buf.st_size);
+  fread (bb_data, sizeof (char), buf.st_size, bb_file);
+  
+  fclose (bb_file);
+  if (da_file)
+    fclose (da_file);
+  fclose (bbg_file);
+}
+
+
+/* Scan the data in the .bb file to find all source files referenced,
+   and the largest line number mentioned in each one.  */
+
+static void
+scan_for_source_files ()
+{
+  struct sourcefile *s_ptr;
+  char *ptr;
+  int count;
+  long line_num;
+
+  /* Search the bb_data to find:
+     1) The number of sources files contained herein, and
+     2) The largest line number for each source file.  */
+
+  ptr = bb_data;
+  sources = 0;
+  for (count = 0; count < bb_data_size; count++)
+    {
+      __fetch_long (&line_num, ptr, 4);
+      ptr += 4;
+      if (line_num == -1)
+	{
+	  /* A source file name follows.  Check to see if we already have
+	   a sourcefile structure for this file.  */
+	  s_ptr = sources;
+	  while (s_ptr && strcmp (s_ptr->name, ptr))
+	    s_ptr = s_ptr->next;
+
+	  if (s_ptr == 0)
+	    {
+	      /* No sourcefile structure for this file name exists, create
+		 a new one, and append it to the front of the sources list.  */
+	      s_ptr = (struct sourcefile *) xmalloc (sizeof(struct sourcefile));
+	      s_ptr->name = xmalloc (strlen ((char *) ptr) + 1);
+	      strcpy (s_ptr->name, (char *) ptr);
+	      s_ptr->maxlineno = 0;
+	      s_ptr->next = sources;
+	      sources = s_ptr;
+	    }
+
+	  /* Scan past the file name.  */
+	  {
+	    long delim;
+	    do {
+	      count++;
+	      __fetch_long (&delim, ptr, 4);
+	      ptr += 4;
+	    } while (delim != line_num);
+	  }
+	}
+      else if (line_num == -2)
+	{
+	  long delim;
+
+	  /* A function name follows.  Ignore it.  */
+	  do {
+	    count++;
+	    __fetch_long (&delim, ptr, 4);
+	    ptr += 4;
+	  } while (delim != line_num);
+	}
+      /* There will be a zero before the first file name, in which case s_ptr
+	 will still be uninitialized.  So, only try to set the maxlineno
+	 field if line_num is non-zero.  */
+      else if (line_num > 0)
+	{
+	  if (s_ptr->maxlineno <= line_num)
+	    s_ptr->maxlineno = line_num + 1;
+	}
+      else if (line_num < 0)
+	{
+	  /* Don't know what this is, but it's garbage. */
+	  abort();
+	}
+    }
+}
+
+/* For calculating coverage at the function level.  */
+
+static int function_source_lines;
+static int function_source_lines_executed;
+static int function_branches;
+static int function_branches_executed;
+static int function_branches_taken;
+static int function_calls;
+static int function_calls_executed;
+static char *function_name;
+
+/* Calculate the branch taken probabilities for all arcs branches at the
+   end of this block.  */
+
+static void
+calculate_branch_probs (current_graph, block_num, branch_probs, last_line_num)
+     struct bb_info_list *current_graph;
+     int block_num;
+     struct arcdata **branch_probs;
+     int last_line_num;
+{
+  int total;
+  struct adj_list *arcptr;
+  struct arcdata *end_ptr, *a_ptr;
+
+  total = current_graph->bb_graph[block_num].exec_count;
+  for (arcptr = current_graph->bb_graph[block_num].succ; arcptr;
+       arcptr = arcptr->succ_next)
+    {
+      /* Ignore fall through arcs as they aren't really branches.  */
+
+      if (arcptr->fall_through)
+	continue;
+		      
+      a_ptr = (struct arcdata *) xmalloc (sizeof (struct arcdata));
+      if (total == 0)
+	a_ptr->prob = -1;
+      else
+	a_ptr->prob = ((arcptr->arc_count * 100) + (total >> 1)) / total;
+      a_ptr->call_insn = arcptr->fake;
+
+      if (output_function_summary)
+	{
+	  if (a_ptr->call_insn)
+	    {
+	      function_calls++;
+	      if (a_ptr->prob != -1)
+		function_calls_executed++;
+	    }
+	  else
+	    {
+	      function_branches++;
+	      if (a_ptr->prob != -1)
+		function_branches_executed++;
+	      if (a_ptr->prob > 0)
+		function_branches_taken++;
+	    }
+	}
+
+      /* Append the new branch to the end of the list.  */
+      a_ptr->next = 0;
+      if (! branch_probs[last_line_num])
+	branch_probs[last_line_num] = a_ptr;
+      else
+	{
+	  end_ptr = branch_probs[last_line_num];
+	  while (end_ptr->next != 0)
+	    end_ptr = end_ptr->next;
+	  end_ptr->next = a_ptr;
+	}
+    }
+}
+
+/* Output summary info for a function.  */
+
+static void
+function_summary ()
+{
+  if (function_source_lines)
+    fprintf (stdout, "%6.2lf%% of %d source lines executed in function %s\n",
+	     (((double) function_source_lines_executed / function_source_lines)
+	      * 100), function_source_lines, function_name);
+  else
+    fprintf (stdout, "No executable source lines in function %s\n",
+	     function_name);
+
+  if (output_branch_probs)
+    {
+      if (function_branches)
+	{
+	  fprintf (stdout, "%6.2lf%% of %d branches executed in funcion %s\n",
+		   (((double) function_branches_executed / function_branches)
+		    * 100), function_branches, function_name);
+	  fprintf (stdout,
+		"%6.2lf%% of %d branches taken at least once in function %s\n",
+		   (((double) function_branches_taken / function_branches)
+		    * 100), function_branches, function_name);
+	}
+      else
+	fprintf (stdout, "No branches in function %s\n", function_name);
+      if (function_calls)
+	fprintf (stdout, "%6.2lf%% of %d calls executed in function %s\n",
+		 (((double) function_calls_executed / function_calls)
+		  * 100), function_calls, function_name);
+      else
+	fprintf (stdout, "No calls in function %s\n", function_name);
+    }
+}
+
+/* Calculate line execution counts, and output the data to a .tcov file.  */
+
+static void
+output_data ()
+{
+  /* When scanning data, this is true only if the data applies to the
+     current source file.  */
+  int this_file;
+  /* An array indexed by line number which indicates how many times that line
+     was executed.  */
+  long *line_counts;
+  /* An array indexed by line number which indicates whether the line was
+     present in the bb file (i.e. whether it had code associate with it).
+     Lines never executed are those which both exist, and have zero execution
+     counts.  */
+  char *line_exists;
+  /* An array indexed by line number, which contains a list of branch
+     probabilities, one for each branch on that line.  */
+  struct arcdata **branch_probs;
+  struct sourcefile *s_ptr;
+  char *source_file_name;
+  FILE *source_file;
+  struct bb_info_list *current_graph;
+  int count;
+  char *cptr;
+  long block_num;
+  long line_num;
+  long last_line_num;
+  int i;
+  struct arcdata *a_ptr;
+  /* Buffer used for reading in lines from the source file.  */
+  char string[STRING_SIZE];
+  /* For calculating coverage at the file level.  */
+  int total_source_lines;
+  int total_source_lines_executed;
+  int total_branches;
+  int total_branches_executed;
+  int total_branches_taken;
+  int total_calls;
+  int total_calls_executed;
+
+  /* Now, for each source file, allocate an array big enough to hold a count
+     for each line.  Scan through the bb_data, and when the file name matches
+     the current file name, then for each following line number, increment
+     the line number execution count indicated by the execution count of
+     the appropriate basic block.  */
+
+  for (s_ptr = sources; s_ptr; s_ptr = s_ptr->next)
+    {
+      /* If this is a relative file name, and an object directory has been
+	 specified, then make it relative to the object directory name.  */
+      if (*s_ptr->name != '/' && object_directory != 0
+	  && *object_directory != '\0')
+	{
+	  int objdir_count = strlen (object_directory);
+	  source_file_name = xmalloc (objdir_count + strlen (s_ptr->name) + 2);
+	  strcpy (source_file_name, object_directory);
+	  if (object_directory[objdir_count - 1] != '/')
+	    source_file_name[objdir_count++] = '/';
+	  strcpy (source_file_name + objdir_count, s_ptr->name);
+	}
+      else
+	source_file_name = s_ptr->name;
+
+      line_counts = (long *) xmalloc (sizeof (long) * s_ptr->maxlineno);
+      bzero ((char *) line_counts, sizeof (long) * s_ptr->maxlineno);
+      line_exists = xmalloc (s_ptr->maxlineno);
+      bzero (line_exists, s_ptr->maxlineno);
+      if (output_branch_probs)
+	{
+	  branch_probs = (struct arcdata **) xmalloc (sizeof (struct arcdata **)
+						      * s_ptr->maxlineno);
+	  bzero ((char *) branch_probs, 
+		 sizeof (struct arcdata **) * s_ptr->maxlineno);
+	}
+      
+      /* There will be a zero at the beginning of the bb info, before the
+	 first list of line numbers, so must initialize block_num to 0.  */
+      block_num = 0;
+      this_file = 0;
+      current_graph = 0;
+      {
+	/* Pointer into the bb_data, incremented while scanning the data.  */
+	char *ptr = bb_data;
+	for (count = 0; count < bb_data_size; count++)
+	  {
+	    long delim;
+
+	    __fetch_long (&line_num, ptr, 4);
+	    ptr += 4;
+	    if (line_num == -1)
+	      {
+		/* Marks the beginning of a file name.  Check to see whether
+		   this is the filename we are currently collecting data for.  */
+
+		if (strcmp (s_ptr->name, ptr))
+		  this_file = 0;
+		else
+		  this_file = 1;
+	      
+		/* Scan past the file name.  */
+		do {
+		  count++;
+		  __fetch_long (&delim, ptr, 4);
+		  ptr += 4;
+		} while (delim != line_num);
+	      }
+	    else if (line_num == -2)
+	      {
+		/* Marks the start of a new function.  Advance to the next
+		   program flow graph.  */
+
+		if (! current_graph)
+		  current_graph = bb_graph_list;
+		else
+		  {
+		    if (block_num == current_graph->num_blocks - 1)
+		      /* Last block falls through to exit.  */
+		      ;
+		    else if (block_num == current_graph->num_blocks - 2)
+		      {
+			if (output_branch_probs && this_file)
+			  calculate_branch_probs (current_graph, block_num,
+						  branch_probs, last_line_num);
+		      }
+		    else
+		      {
+			fprintf (stderr,
+				 "didn't use all bb entries of graph, function %s\n",
+				 function_name);
+			fprintf (stderr, "block_num = %d, num_blocks = %d\n",
+				 block_num, current_graph->num_blocks);
+		      }
+
+		    current_graph = current_graph->next;
+		    block_num = 0;
+
+		    if (output_function_summary && this_file)
+		      function_summary ();
+		  }
+
+		if (output_function_summary)
+		  {
+		    function_source_lines = 0;
+		    function_source_lines_executed = 0;
+		    function_branches = 0;
+		    function_branches_executed = 0;
+		    function_branches_taken = 0;
+		    function_calls = 0;
+		    function_calls_executed = 0;
+		  }
+
+		/* Save the function name for later use.  */
+		function_name = ptr;
+
+		/* Scan past the file name.  */
+		do {
+		  count++;
+		  __fetch_long (&delim, ptr, 4);
+		  ptr += 4;
+		} while (delim != line_num);
+	      }
+	    else if (line_num == 0)
+	      {
+		/* Marks the end of a block.  */
+
+		if (block_num >= current_graph->num_blocks)
+		  {
+		    fprintf (stderr, "ERROR: too many basic blocks in .bb file %s\n",
+			     function_name);
+		    abort ();
+		  }
+		  
+		if (output_branch_probs && this_file)
+		  calculate_branch_probs (current_graph, block_num,
+					  branch_probs, last_line_num);
+
+		block_num++;
+	      }
+	    else if (this_file)
+	      {
+		if (output_function_summary)
+		  {
+		    if (line_exists[line_num] == 0)
+		      function_source_lines++;
+		    if (line_counts[line_num] == 0
+			&& current_graph->bb_graph[block_num].exec_count != 0)
+		      function_source_lines_executed++;
+		  }
+
+		/* Accumulate execution data for this line number.  */
+
+		line_counts[line_num]
+		  += current_graph->bb_graph[block_num].exec_count;
+		line_exists[line_num] = 1;
+		last_line_num = line_num;
+	      }
+	  }
+      }
+
+      if (output_function_summary && this_file)
+	function_summary ();
+
+      /* Calculate summary test coverage statistics.  */
+
+      total_source_lines = 0;
+      total_source_lines_executed = 0;
+      total_branches = 0;
+      total_branches_executed = 0;
+      total_branches_taken = 0;
+      total_calls = 0;
+      total_calls_executed = 0;
+
+      for (count = 1; count < s_ptr->maxlineno; count++)
+	{
+	  if (line_exists[count])
+	    {
+	      total_source_lines++;
+	      if (line_counts[count])
+		total_source_lines_executed++;
+	    }
+	  if (output_branch_probs)
+	    {
+	      for (a_ptr = branch_probs[count]; a_ptr; a_ptr = a_ptr->next)
+		{
+		  if (a_ptr->call_insn)
+		    {
+		      total_calls++;
+		      if (a_ptr->prob != -1)
+			total_calls_executed++;
+		    }
+		  else
+		    {
+		      total_branches++;
+		      if (a_ptr->prob != -1)
+			total_branches_executed++;
+		      if (a_ptr->prob > 0)
+			total_branches_taken++;
+		    }
+		}
+	    }
+	}
+
+      if (total_source_lines)
+	fprintf (stdout,
+		 "%6.2lf%% of %d source lines executed in file %s\n",
+		 (((double) total_source_lines_executed / total_source_lines)
+		  * 100), total_source_lines, source_file_name);
+      else
+	fprintf (stdout, "No executable source lines in file %s\n",
+		 source_file_name);
+
+      if (output_branch_probs)
+	{
+	  if (total_branches)
+	    {
+	      fprintf (stdout, "%6.2lf%% of %d branches executed in file %s\n",
+		       (((double) total_branches_executed / total_branches)
+			* 100), total_branches, source_file_name);
+	      fprintf (stdout,
+		    "%6.2lf%% of %d branches taken at least once in file %s\n",
+		       (((double) total_branches_taken / total_branches)
+			* 100), total_branches, source_file_name);
+	    }
+	  else
+	    fprintf (stdout, "No branches in file %s\n", source_file_name);
+	  if (total_calls)
+	    fprintf (stdout, "%6.2lf%% of %d calls executed in file %s\n",
+		     (((double) total_calls_executed / total_calls)
+		      * 100), total_calls, source_file_name);
+	  else
+	    fprintf (stdout, "No calls in file %s\n", source_file_name);
+	}
+
+      if (output_gcov_file)
+	{
+	  /* Now the statistics are ready.  Read in the source file one line
+	     at a time, and output that line to the gcov file preceeded by
+	     its execution count if non zero.  */
+      
+	  source_file = fopen (source_file_name, "r");
+	  if (source_file == NULL)
+	    {
+	      fprintf (stderr, "Could not open source file %s.\n",
+		       source_file_name);
+	      free (line_counts);
+	      free (line_exists);
+	      continue;
+	    }
+
+	  count = strlen (source_file_name);
+	  cptr = rindex (s_ptr->name, '/');
+	  if (cptr)
+	    cptr = cptr + 1;
+	  else
+	    cptr = s_ptr->name;
+	  if (output_long_names && strcmp (cptr, input_file_name))
+	    {
+	      gcov_file_name = xmalloc (count + 7 + strlen (input_file_name));
+	      
+	      cptr = rindex (input_file_name, '/');
+	      if (cptr)
+		strcpy (gcov_file_name, cptr + 1);
+	      else
+		strcpy (gcov_file_name, input_file_name);
+
+	      strcat (gcov_file_name, ".");
+
+	      cptr = rindex (source_file_name, '/');
+	      if (cptr)
+		strcat (gcov_file_name, cptr + 1);
+	      else
+		strcat (gcov_file_name, source_file_name);
+	    }
+	  else
+	    {
+	      gcov_file_name = xmalloc (count + 6);
+	      cptr = rindex (source_file_name, '/');
+	      if (cptr)
+		strcpy (gcov_file_name, cptr + 1);
+	      else
+		strcpy (gcov_file_name, source_file_name);
+	    }
+
+	  /* Don't strip off the ending for compatibility with tcov, since
+	     this results in confusion if there is more than one file with
+	     the same basename, e.g. tmp.c and tmp.h.  */
+	  strcat (gcov_file_name, ".gcov");
+
+	  gcov_file = fopen (gcov_file_name, "w");
+
+	  if (gcov_file == NULL)
+	    {
+	      fprintf (stderr, "Could not open output file %s.\n",
+		       gcov_file_name);
+	      fclose (source_file);
+	      free (line_counts);
+	      free (line_exists);
+	      continue;
+	    }
+
+	  fprintf (stdout, "Creating %s.\n", gcov_file_name);
+
+	  for (count = 1; count < s_ptr->maxlineno; count++)
+	    {
+	      char *retval;
+	      int len;
+
+	      retval = fgets (string, STRING_SIZE, source_file);
+
+	      /* For lines which don't exist in the .bb file, print nothing
+		 before the source line.  For lines which exist but were never
+		 executed, print ###### before the source line.  Otherwise,
+		 print the execution count before the source line.  */
+	      /* There are 16 spaces of identation added before the source line
+		 so that tabs won't be messed up.  */
+	      if (line_exists[count])
+		{
+		  if (line_counts[count])
+		    fprintf (gcov_file, "%12d    %s", line_counts[count],
+			     string);
+		  else
+		    fprintf (gcov_file, "      ######    %s", string);
+		}
+	      else
+		fprintf (gcov_file, "\t\t%s", string);
+
+	      /* In case the source file line is larger than our buffer, keep
+		 reading and outputing lines until we get a newline.  */
+	      len = strlen (string);
+	      while ((len == 0 || string[strlen (string) - 1] != '\n') &&
+		     retval != NULL)
+		{
+		  retval = fgets (string, STRING_SIZE, source_file);
+		  fputs (string, gcov_file);
+		}
+
+	      if (output_branch_probs)
+		{
+		  for (i = 0, a_ptr = branch_probs[count]; a_ptr;
+		       a_ptr = a_ptr->next, i++)
+		    {
+		      if (a_ptr->call_insn)
+			{
+			  if (a_ptr->prob == -1)
+			    fprintf (gcov_file, "call %d never executed\n", i);
+			  else
+			    fprintf (gcov_file,
+				     "call %d returns = %d%%\n",
+				     i, 100 - a_ptr->prob);
+			}
+		      else
+			{
+			  if (a_ptr->prob == -1)
+			    fprintf (gcov_file, "branch %d never executed\n",
+				     i);
+			  else
+			    fprintf (gcov_file, "branch %d taken = %d%%\n", i,
+				     a_ptr->prob);
+			}
+		    }
+		}
+
+	      /* Gracefully handle errors while reading the source file.  */
+	      if (retval == NULL)
+		{
+		  fprintf (stderr,
+			   "Unexpected EOF while reading source file %s.\n",
+			   source_file_name);
+		  break;
+		}
+	    }
+
+	  /* Handle all remaining source lines.  There may be lines
+	     after the last line of code.  */
+
+	  {
+	    char *retval = fgets (string, STRING_SIZE, source_file);
+	    while (retval != NULL)
+	      {
+		int len;
+
+		fprintf (gcov_file, "\t\t%s", string);
+
+		/* In case the source file line is larger than our buffer, keep
+		   reading and outputing lines until we get a newline.  */
+		len = strlen (string);
+		while ((len == 0 || string[strlen (string) - 1] != '\n') &&
+		       retval != NULL)
+		  {
+		    retval = fgets (string, STRING_SIZE, source_file);
+		    fputs (string, gcov_file);
+		  }
+
+		retval = fgets (string, STRING_SIZE, source_file);
+	      }
+	  }
+
+	  fclose (source_file);
+	  fclose (gcov_file);
+	}
+
+      free (line_counts);
+      free (line_exists);
+    }
+}
diff --git a/gcc/profile.c b/gcc/profile.c
new file mode 100644
index 00000000000..dcdd5fe6574
--- /dev/null
+++ b/gcc/profile.c
@@ -0,0 +1,1634 @@
+/* Calculate branch probabilities, and basic block execution counts. 
+   Copyright (C) 1990, 1991, 1992, 1993, 1994, 1996, 1997 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.
+
+GNU CC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+GNU CC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU CC; see the file COPYING.  If not, write to
+the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, 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.  */
+
+/* ??? Register allocation should use basic block execution counts to
+   give preference to the most commonly executed blocks.  */
+
+/* ??? The .da files are not safe.  Changing the program after creating .da
+   files or using different options when compiling with -fbranch-probabilities
+   can result the arc data not matching the program.  Maybe add instrumented
+   arc count to .bbg file?  Maybe check whether PFG matches the .bbg file?  */
+
+/* ??? 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 "rtl.h"
+#include "flags.h"
+#include "insn-flags.h"
+#include "insn-config.h"
+#include "output.h"
+#include <stdio.h>
+#include "tree.h"
+#include "output.h"
+#include "gcov-io.h"
+
+extern char * xmalloc ();
+extern void free ();
+extern tree get_file_function_name ();
+
+/* 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.  */
+
+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;
+
+/* 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. */
+static FILE *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;
+
+/* 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_blocks_created;
+static int total_num_passes;
+static int total_num_times_called;
+static int total_hist_br_prob[20];
+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
+
+/* If non-zero, we need to output a constructor to set up the
+   per-object-file data. */
+static int need_func_profiler = 0;
+
+
+/* Add arc 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.  */
+
+static void
+instrument_arcs (f, num_blocks, dump_file)
+     rtx f;
+     int num_blocks;
+     FILE *dump_file;
+{
+  register int i;
+  register struct adj_list *arcptr, *backptr;
+  int num_arcs = 0;
+  int num_instr_arcs = 0;
+  rtx insn;
+
+  int neg_one = -1;
+  int zero = 0;
+  int inverted;
+  rtx note;
+
+  /* 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)
+	{
+	  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)
+	    {
+	      /* 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
+		abort ();
+
+	      num_arcs += 1;
+	      if (dump_file)
+		fprintf (dump_file,
+			 "Arc %d to %d needed new basic block\n", i,
+			 ARC_TARGET (arcptr));
+	    }
+	}
+  
+  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);
+    }
+}
+
+/* Output STRING to bb_file, surrounded by DELIMITER.  */
+
+static void
+output_gcov_string (string, delimiter)
+     char *string;
+     long delimiter;
+{
+  long temp;
+			
+  /* Write a delimiter to indicate that a file name follows.  */
+  __write_long (delimiter, bb_file, 4);
+
+  /* Write the string.  */
+  temp = strlen (string) + 1;
+  fwrite (string, temp, 1, bb_file);
+
+  /* Append a few zeros, to align the output to a 4 byte boundary.  */
+  temp = temp & 0x3;
+  if (temp)
+    {
+      char c[4];
+
+      c[0] = c[1] = c[2] = c[3] = 0;
+      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.  */
+  __write_long (delimiter, bb_file, 4);
+}
+
+/* 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 auxilliary
+   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.
+
+   Main entry point of this file.  */
+
+void
+branch_prob (f, dump_file)
+     rtx f;
+     FILE *dump_file;
+{
+  int i, num_blocks;
+  int dest;
+  rtx insn;
+  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);
+	  }
+      }
+
+    /* 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;
+  }
+
+  total_num_blocks += num_blocks;
+  if (dump_file)
+    fprintf (dump_file, "%d basic blocks\n", num_blocks);
+
+  /* If we are only doing test coverage here, then return now.  */
+  if (! profile_arc_flag && ! flag_branch_probabilities)
+    return;
+
+  /* Create and initialize the arrays that will hold bb_graph
+     and execution count info.  */
+
+  bb_graph = (struct bb_info *) alloca (num_blocks * sizeof (struct bb_info));
+  bzero ((char *) bb_graph, (sizeof (struct bb_info) * num_blocks));
+
+  {
+    /* 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;
+
+    /* 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)))
+	  {
+	    /* This is the first insn of the block.  */
+	    i += 1;
+	    if (fall_through)
+	      {
+		arcptr = (struct adj_list *) alloca (sizeof (struct adj_list));
+		init_arc (arcptr, i - 1, i, 0);
+		arcptr->fall_through = 1;
+
+		num_arcs++;
+	      }
+	    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.  */
+
+	    if (GET_CODE (pattern) == PARALLEL)
+	      {
+		/* This assumes that PARALLEL jumps are tablejump entry
+		   jumps.  */
+		/* 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 ();
+	      }
+	    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 ((tem = SET_SRC (pattern))
+		     && GET_CODE (tem) == LABEL_REF)
+	      dest = label_to_bb[CODE_LABEL_NUMBER (XEXP (tem, 0))];
+	    else
+	      {
+		rtx label_ref;
+
+		/* Must be an IF_THEN_ELSE branch.  */
+		if (GET_CODE (tem) != IF_THEN_ELSE)
+		  abort ();
+		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)
+	  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.
+
+     Fallthough 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);
+
+  /* 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);
+
+  /* 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
+
+     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.  */
+
+  /* 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
+     faster if we propagate numbers from the end to the start.
+     
+     This takes an average of slightly more than 3 passes.  */
+
+  changes = 1;
+  passes = 0;
+  while (changes)
+    {
+      passes++;
+      changes = 0;
+
+      for (i = num_blocks - 1; i >= 0; i--)
+	{
+	  struct bb_info *binfo = &bb_graph[i];
+	  if (! binfo->count_valid)
+	    {
+	      if (binfo->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;
+		  changes = 1;
+		}
+	      else if (binfo->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;
+		  changes = 1;
+		}
+	    }
+	  if (binfo->count_valid)
+	    {
+	      if (binfo->succ_count == 1)
+		{
+		  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)
+		      break;
+		  if (! arcptr)
+		    abort ();
+		  arcptr->count_valid = 1;
+		  ARC_COUNT (arcptr) = total;
+		  binfo->succ_count--;
+		  
+		  bb_graph[ARC_TARGET (arcptr)].pred_count--;
+		  changes = 1;
+		}
+	      if (binfo->pred_count == 1)
+		{
+		  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)
+		      break;
+		  if (! arcptr)
+		    abort ();
+		  arcptr->count_valid = 1;
+		  ARC_COUNT (arcptr) = total;
+		  binfo->pred_count--;
+		  
+		  bb_graph[ARC_SOURCE (arcptr)].succ_count--;
+		  changes = 1;
+		}
+	    }
+	}
+    }
+
+  total_num_passes += passes;
+  if (dump_file)
+    fprintf (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++)
+    {
+      struct bb_info *binfo = &bb_graph[i];
+      if (binfo->succ_count || binfo->pred_count)
+	abort ();
+    }
+
+  /* For every arc, calculate its branch probability and add a reg_note
+     to the branch insn to indicate this.  */
+
+  for (i = 0; i < 20; i++)
+    hist_br_prob[i] = 0;
+  num_never_executed = 0;
+  num_branches = 0;
+
+  for (i = 0; i < num_blocks; i++)
+    {
+      struct bb_info *binfo = &bb_graph[i];
+
+      total = binfo->exec_count;
+      for (arcptr = binfo->succ; arcptr; arcptr = arcptr->succ_next)
+	{
+	  if (arcptr->branch_insn)
+	    {
+	      /* 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++;
+	      else
+		{
+		  int index = prob * 20 / REG_BR_PROB_BASE;
+		  if (index == 20)
+		    index = 19;
+		  hist_br_prob[index]++;
+		}
+	      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 ();
+	}
+      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;
+	}
+    }
+  
+  /* This should never happen.  */
+  if (bad_counts)
+    warning ("Arc profiling: some arc counts were bad.");
+
+  if (dump_file)
+    {
+      fprintf (dump_file, "%d branches\n", num_branches);
+      fprintf (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);
+
+      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];
+    }
+
+}
+
+/* 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++;
+}
+
+/* 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.  */
+
+static void
+find_spanning_tree (num_blocks)
+     int num_blocks;
+{
+  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++)
+    {
+      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;
+	      }
+	  }
+    }
+
+  /* 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;
+
+  /* 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.  */
+
+  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)
+	{
+	  fill_spanning_tree (i);
+	  break;
+	}
+}
+
+/* Add arcs reached from BLOCK to the spanning tree if they are needed and
+   not already there.  */
+
+static void
+fill_spanning_tree (block)
+     int block;
+{
+  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));
+      }
+}
+
+/* When first visit a block, must add all blocks that are already connected
+   to this block via tree arcs to the spanning tree.  */
+
+static void
+expand_spanning_tree (block)
+     int block;
+{
+  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));
+}
+
+/* Perform file-level initialization for branch-prob processing.  */
+
+void
+init_branch_prob (filename)
+     char *filename;
+{
+  long len;
+  int i;
+
+  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);
+      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);
+
+      /* 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);
+
+      /* Initialize to zero, to ensure that the first file name will be
+	 written to the .bb file.  */
+      last_bb_file_name = 0;
+    }
+
+  if (flag_branch_probabilities)
+    {
+      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.",
+		 da_file_name);
+
+      /* The first word in the .da file gives the number of instrumented arcs,
+	 which is not needed for our purposes.  */
+
+      if (da_file)
+	__read_long (&len, da_file, 8);
+    }
+
+  if (profile_arc_flag)
+    init_arc_profiler ();
+
+  total_num_blocks = 0;
+  total_num_arcs = 0;
+  total_num_arcs_instrumented = 0;
+  total_num_blocks_created = 0;
+  total_num_passes = 0;
+  total_num_times_called = 0;
+  total_num_branches = 0;
+  total_num_never_executed = 0;
+  for (i = 0; i < 20; i++)
+    total_hist_br_prob[i] = 0;
+}
+
+/* Performs file-level cleanup after branch-prob processing
+   is completed.  */
+
+void
+end_branch_prob (dump_file)
+     FILE *dump_file;
+{
+  if (flag_test_coverage)
+    {
+      fclose (bb_file);
+      fclose (bbg_file);
+    }
+
+  if (flag_branch_probabilities)
+    {
+      if (da_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. */
+	  if (feof (da_file))
+	    warning (".da file contents exhausted too early\n");
+	  /* Should be at end of file now.  */
+	  if (__read_long (&temp, da_file, 8) == 0)
+	    warning (".da file contents not exhausted\n");
+	  fclose (da_file);
+	}
+    }
+
+  if (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",
+	       total_num_blocks_created);
+      fprintf (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",
+		 (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",
+	       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",
+		     (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.  */
+
+static rtx profiler_label;
+
+/* Initialize the profiler_label.  */
+
+static void
+init_arc_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);
+}
+
+/* Output instructions as RTL to increment the arc execution count.  */
+
+static void
+output_arc_profiler (arcno, insert_after)
+     int arcno;
+     rtx insert_after;
+{
+  rtx profiler_target_addr
+    = (arcno
+       ? gen_rtx (CONST, Pmode,
+		  gen_rtx (PLUS, Pmode, profiler_label,
+			   gen_rtx (CONST_INT, VOIDmode,
+				    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;
+  rtx sequence;
+
+#ifdef SMALL_REGISTER_CLASSES
+  /* 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);
+
+      if (GET_CODE (next_insert_after) == INSN)
+	{
+	  /* The first insn after the call may be a stack pop, skip it.  */
+	  if (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 (GET_CODE (PATTERN (insert_after)) == SET)
+	    return_reg = SET_DEST (PATTERN (insert_after));
+	  else
+	    return_reg = SET_DEST (XVECEXP (PATTERN (insert_after), 0, 0));
+
+	  if (reg_referenced_p (return_reg, PATTERN (next_insert_after)))
+	    insert_after = next_insert_after;
+	}
+    }
+#endif
+
+  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);
+
+  add_ref = gen_rtx (PLUS, mode, profiler_reg, GEN_INT (1));
+  emit_move_insn (profiler_reg, add_ref);
+
+  /* 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);
+
+  sequence = gen_sequence ();
+  end_sequence ();
+  emit_insn_after (sequence, insert_after);
+}
+
+/* Output code for a constructor that will invoke __bb_init_func, if
+   this has not already been done. */
+
+void
+output_func_start_profiler ()
+{
+  tree fnname, fndecl;
+  char *name, *cfnname;
+  rtx table_address;
+  enum machine_mode mode = mode_for_size (LONG_TYPE_SIZE, MODE_INT, 0);
+
+  /* It's either already been output, or we don't need it because we're
+     not doing profile-arcs. */
+  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 ();
+
+  /* Try and make a unique name given the "file function name".
+
+     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);
+  fnname = get_identifier (name);
+  free (name);
+
+  fndecl = build_decl (FUNCTION_DECL, fnname,
+		       build_function_type (void_type_node, NULL_TREE));
+  DECL_EXTERNAL (fndecl) = 1;
+  TREE_PUBLIC (fndecl) = 1;
+  DECL_ASSEMBLER_NAME (fndecl) = fnname;
+  DECL_RESULT (fndecl) = build_decl (RESULT_DECL, NULL_TREE, void_type_node);
+  current_function_decl = fndecl;
+  pushlevel (0);
+  make_function_rtl (fndecl);
+  init_function_start (fndecl, input_filename, lineno);
+  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,
+		     mode, 1, table_address, Pmode);
+
+  expand_function_end (input_filename, lineno, 0);
+  poplevel (1, 0, 1);
+  rest_of_compilation (fndecl);
+  fflush (asm_out_file);
+  current_function_decl = NULL_TREE;
+
+  assemble_constructor (IDENTIFIER_POINTER (DECL_NAME (fndecl)));
+}