OSDN Git Service

Initial revision
authordje <dje@138bc75d-0d04-0410-961f-82ee72b054a4>
Fri, 28 Mar 1997 22:43:13 +0000 (22:43 +0000)
committerdje <dje@138bc75d-0d04-0410-961f-82ee72b054a4>
Fri, 28 Mar 1997 22:43:13 +0000 (22:43 +0000)
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@13824 138bc75d-0d04-0410-961f-82ee72b054a4

gcc/gcov-io.h [new file with mode: 0644]
gcc/gcov.c [new file with mode: 0644]
gcc/profile.c [new file with mode: 0644]

diff --git a/gcc/gcov-io.h b/gcc/gcov-io.h
new file mode 100644 (file)
index 0000000..59d802c
--- /dev/null
@@ -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 (file)
index 0000000..26374c1
--- /dev/null
@@ -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);
+}
+\f
+/* 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);
+    }
+}
+\f
+/* 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();
+       }
+    }
+}
+\f
+/* 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 (file)
index 0000000..dcdd5fe
--- /dev/null
@@ -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;
+
+\f
+/* 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);
+}
+\f
+/* 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];
+    }
+
+}
+\f
+/* 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));
+}
+\f
+/* 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);
+       }
+    }
+}
+\f
+/* 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)));
+}