gcov.c

GCC编译器源代码

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 ((unsigned) buf.st_size);
  fread (bb_data, sizeof (char), buf.st_size, bb_file);
  
  fclose (bb_file);
  if (da_file)
    fclose (da_file);
  fclose (bbg_file);
}


/* Scan the data in the .bb file to find all source files referenced,
   and the largest line number mentioned in each one.  */

static void
scan_for_source_files ()
{
  struct sourcefile *s_ptr;
  char *ptr;
  int count;
  long line_num;

  /* Search the bb_data to find:
     1) The number of sources files contained herein, and
     2) The largest line number for each source file.  */

  ptr = bb_data;
  sources = 0;
  for (count = 0; count < bb_data_size; count++)
    {
      __fetch_long (&line_num, ptr, 4);
      ptr += 4;
      if (line_num == -1)
	{
	  /* A source file name follows.  Check to see if we already have
	   a sourcefile structure for this file.  */
	  s_ptr = sources;
	  while (s_ptr && strcmp (s_ptr->name, ptr))
	    s_ptr = s_ptr->next;

	  if (s_ptr == 0)
	    {
	      /* No sourcefile structure for this file name exists, create
		 a new one, and append it to the front of the sources list.  */
	      s_ptr = (struct sourcefile *) xmalloc (sizeof(struct sourcefile));
	      s_ptr->name = xmalloc (strlen ((char *) ptr) + 1);
	      strcpy (s_ptr->name, (char *) ptr);
	      s_ptr->maxlineno = 0;
	      s_ptr->next = sources;
	      sources = s_ptr;
	    }

	  /* Scan past the file name.  */
	  {
	    long delim;
	    do {
	      count++;
	      __fetch_long (&delim, ptr, 4);
	      ptr += 4;
	    } while (delim != line_num);
	  }
	}
      else if (line_num == -2)
	{
	  long delim;

	  /* A function name follows.  Ignore it.  */
	  do {
	    count++;
	    __fetch_long (&delim, ptr, 4);
	    ptr += 4;
	  } while (delim != line_num);
	}
      /* There will be a zero before the first file name, in which case s_ptr
	 will still be uninitialized.  So, only try to set the maxlineno
	 field if line_num is non-zero.  */
      else if (line_num > 0)
	{
	  if (s_ptr->maxlineno <= line_num)
	    s_ptr->maxlineno = line_num + 1;
	}
      else if (line_num < 0)
	{
	  /* Don't know what this is, but it's garbage. */
	  abort();
	}
    }
}

/* For calculating coverage at the function level.  */

static int function_source_lines;
static int function_source_lines_executed;
static int function_branches;
static int function_branches_executed;
static int function_branches_taken;
static int function_calls;
static int function_calls_executed;
static char *function_name;

/* Calculate the branch taken probabilities for all arcs branches at the
   end of this block.  */

static void
calculate_branch_probs (current_graph, block_num, branch_probs, last_line_num)
     struct bb_info_list *current_graph;
     int block_num;
     struct arcdata **branch_probs;
     int last_line_num;
{
  int total;
  struct adj_list *arcptr;
  struct arcdata *end_ptr, *a_ptr;

  total = current_graph->bb_graph[block_num].exec_count;
  for (arcptr = current_graph->bb_graph[block_num].succ; arcptr;
       arcptr = arcptr->succ_next)
    {
      /* Ignore fall through arcs as they aren't really branches.  */

      if (arcptr->fall_through)
	continue;
		      
      a_ptr = (struct arcdata *) xmalloc (sizeof (struct arcdata));
      if (total == 0)
	a_ptr->prob = -1;
      else
	a_ptr->prob = ((arcptr->arc_count * 100) + (total >> 1)) / total;
      a_ptr->call_insn = arcptr->fake;

      if (output_function_summary)
	{
	  if (a_ptr->call_insn)
	    {
	      function_calls++;
	      if (a_ptr->prob != -1)
		function_calls_executed++;
	    }
	  else
	    {
	      function_branches++;
	      if (a_ptr->prob != -1)
		function_branches_executed++;
	      if (a_ptr->prob > 0)
		function_branches_taken++;
	    }
	}

      /* Append the new branch to the end of the list.  */
      a_ptr->next = 0;
      if (! branch_probs[last_line_num])
	branch_probs[last_line_num] = a_ptr;
      else
	{
	  end_ptr = branch_probs[last_line_num];
	  while (end_ptr->next != 0)
	    end_ptr = end_ptr->next;
	  end_ptr->next = a_ptr;
	}
    }
}

/* Output summary info for a function.  */

static void
function_summary ()
{
  if (function_source_lines)
    fprintf (stdout, "%6.2lf%% of %d source lines executed in function %s\n",
	     (((double) function_source_lines_executed / function_source_lines)
	      * 100), function_source_lines, function_name);
  else
    fprintf (stdout, "No executable source lines in function %s\n",
	     function_name);

  if (output_branch_probs)
    {
      if (function_branches)
	{
	  fprintf (stdout, "%6.2lf%% of %d branches executed in function %s\n",
		   (((double) function_branches_executed / function_branches)