profile.c

GCC编译器源代码

    /* If the code at the end of the function would give a new block, then
       do the following.  */

    if (prev_code == JUMP_INSN || prev_code == CALL_INSN
	|| prev_code == CODE_LABEL || prev_code == BARRIER)
      {
	if (fall_through)
	  {
	    arcptr = (struct adj_list *) alloca (sizeof (struct adj_list));
	    init_arc (arcptr, i, i + 1, 0);
	    arcptr->fall_through = 1;

	    num_arcs++;
	  }
	  
	/* This may not be a real insn, but that should not cause a problem.  */
	bb_graph[i+1].first_insn = get_last_insn ();
      }

    /* There is always a fake arc from the last block of the function
       to the function exit block.  */
    arcptr = (struct adj_list *) alloca (sizeof (struct adj_list));
    init_arc (arcptr, num_blocks-2, num_blocks-1, 0);
    arcptr->fake = 1;
    num_arcs++;
  }

  total_num_arcs += num_arcs;
  if (dump_file)
    fprintf (dump_file, "%d arcs\n", num_arcs);

  /* Create spanning tree from basic block graph, mark each arc that is
     on the spanning tree.  */

  /* To reduce the instrumentation cost, make two passes over the tree.
     First, put as many must-split (crowded and fake) arcs on the tree as
     possible, then on the second pass fill in the rest of the tree.
     Note that the spanning tree is considered undirected, so that as many
     must-split arcs as possible can be put on it.

     Fallthrough arcs which are crowded should not be chosen on the first
     pass, since they do not require creating a new basic block.  These
     arcs will have fall_through set.  */

  find_spanning_tree (num_blocks);

  /* Create a .bbg file from which gcov can reconstruct the basic block
     graph.  First output the number of basic blocks, and then for every
     arc output the source and target basic block numbers.
     NOTE: The format of this file must be compatible with gcov.  */

  if (flag_test_coverage)
    {
      int flag_bits;

      __write_long (num_blocks, bbg_file, 4);
      __write_long (num_arcs, bbg_file, 4);

      for (i = 0; i < num_blocks; i++)
	{
	  long count = 0;
	  for (arcptr = bb_graph[i].succ; arcptr; arcptr = arcptr->succ_next)
	    count++;
	  __write_long (count, bbg_file, 4);

	  for (arcptr = bb_graph[i].succ; arcptr; arcptr = arcptr->succ_next)
	    {
	      flag_bits = 0;
	      if (arcptr->on_tree)
		flag_bits |= 0x1;
	      if (arcptr->fake)
		flag_bits |= 0x2;
	      if (arcptr->fall_through)
		flag_bits |= 0x4;

	      __write_long (ARC_TARGET (arcptr), bbg_file, 4);
	      __write_long (flag_bits, bbg_file, 4);
	    }
	}

      /* Emit a -1 to separate the list of all arcs from the list of
	 loop back edges that follows.  */
      __write_long (-1, bbg_file, 4);
    }

  /* For each arc not on the spanning tree, add counting code as rtl.  */

  if (profile_arc_flag)
    instrument_arcs (f, num_blocks, dump_file);

  /* Execute the rest only if doing branch probabilities.  */
  if (! flag_branch_probabilities)
    return;

  /* For each arc not on the spanning tree, set its execution count from
     the .da file.  */

  /* The first count in the .da file is the number of times that the function
     was entered.  This is the exec_count for block zero.  */

  num_arcs = 0;
  for (i = 0; i < num_blocks; i++)
    for (arcptr = bb_graph[i].succ; arcptr; arcptr = arcptr->succ_next)
      if (! arcptr->on_tree)
	{
	  num_arcs++;
	  if (da_file)
	    {
	      long value;
	      __read_long (&value, da_file, 8);
	      ARC_COUNT (arcptr) = value;
	    }
	  else
	    ARC_COUNT (arcptr) = 0;
	  arcptr->count_valid = 1;
	  bb_graph[i].succ_count--;
	  bb_graph[ARC_TARGET (arcptr)].pred_count--;
	}

  if (dump_file)
    fprintf (dump_file, "%d arc counts read\n", num_arcs);

  /* For every block in the file,
     - if every exit/entrance arc has a known count, then set the block count
     - if the block count is known, and every exit/entrance arc but one has
       a known execution count, then set the count of the remaining arc

     As arc counts are set, decrement the succ/pred count, but don't delete
     the arc, that way we can easily tell when all arcs are known, or only
     one arc is unknown.  */

  /* The order that the basic blocks are iterated through is important.
     Since the code that finds spanning trees starts with block 0, low numbered
     arcs are put on the spanning tree in preference to high numbered arcs.
     Hence, most instrumented arcs are at the end.  Graph solving works much
     faster if we propagate numbers from the end to the start.
     
     This takes an average of slightly more than 3 passes.  */

  changes = 1;
  passes = 0;
  while (changes)
    {
      passes++;
      changes = 0;

      for (i = num_blocks - 1; i >= 0; i--)
	{
	  struct bb_info *binfo = &bb_graph[i];
	  if (! binfo->count_valid)
	    {
	      if (binfo->succ_count == 0)
		{
		  total = 0;
		  for (arcptr = binfo->succ; arcptr;
		       arcptr = arcptr->succ_next)
		    total += ARC_COUNT (arcptr);
		  binfo->exec_count = total;
		  binfo->count_valid = 1;
		  changes = 1;
		}
	      else if (binfo->pred_count == 0)
		{
		  total = 0;
		  for (arcptr = binfo->pred; arcptr;
		       arcptr = arcptr->pred_next)
		    total += ARC_COUNT (arcptr);
		  binfo->exec_count = total;
		  binfo->count_valid = 1;
		  changes = 1;
		}
	    }
	  if (binfo->count_valid)
	    {
	      if (binfo->succ_count == 1)
		{
		  total = 0;
		  /* One of the counts will be invalid, but it is zero,
		     so adding it in also doesn't hurt.  */
		  for (arcptr = binfo->succ; arcptr;
		       arcptr = arcptr->succ_next)
		    total += ARC_COUNT (arcptr);
		  /* Calculate count for remaining arc by conservation.  */
		  total = binfo->exec_count - total;
		  /* Search for the invalid arc, and set its count.  */
		  for (arcptr = binfo->succ; arcptr;
		       arcptr = arcptr->succ_next)
		    if (! arcptr->count_valid)
		      break;
		  if (! arcptr)
		    abort ();
		  arcptr->count_valid = 1;
		  ARC_COUNT (arcptr) = total;
		  binfo->succ_count--;
		  
		  bb_graph[ARC_TARGET (arcptr)].pred_count--;
		  changes = 1;
		}
	      if (binfo->pred_count == 1)
		{
		  total = 0;
		  /* One of the counts will be invalid, but it is zero,
		     so adding it in also doesn't hurt.  */
		  for (arcptr = binfo->pred; arcptr;
		       arcptr = arcptr->pred_next)
		    total += ARC_COUNT (arcptr);
		  /* Calculate count for remaining arc by conservation.  */
		  total = binfo->exec_count - total;
		  /* Search for the invalid arc, and set its count.  */
		  for (arcptr = binfo->pred; arcptr;
		       arcptr = arcptr->pred_next)
		    if (! arcptr->count_valid)
		      break;
		  if (! arcptr)
		    abort ();
		  arcptr->count_valid = 1;
		  ARC_COUNT (arcptr) = total;
		  binfo->pred_count--;
		  
		  bb_graph[ARC_SOURCE (arcptr)].succ_count--;
		  changes = 1;
		}
	    }
	}
    }

  total_num_passes += passes;
  if (dump_file)
    fprintf (dump_file, "Graph solving took %d passes.\n\n", passes);

  /* If the graph has been correctly solved, every block will have a
     succ and pred count of zero.  */
  for (i = 0; i < num_blocks; i++)
    {
      struct bb_info *binfo = &bb_graph[i];
      if (binfo->succ_count || binfo->pred_count)
	abort ();
    }

  /* For every arc, calculate its branch probability and add a reg_note
     to the branch insn to indicate this.  */

  for (i = 0; i < 20; i++)
    hist_br_prob[i] = 0;
  num_never_executed = 0;
  num_branches = 0;

  for (i = 0; i < num_blocks; i++)
    {
      struct bb_info *binfo = &bb_graph[i];

      total = binfo->exec_count;
      for (arcptr = binfo->succ; arcptr; arcptr = arcptr->succ_next)
	{
	  if (arcptr->branch_insn)
	    {
	      /* This calculates the branch probability as an integer between
		 0 and REG_BR_PROB_BASE, properly rounded to the nearest
		 integer.  Perform the arithmetic in double to avoid
		 overflowing the range of ints.  */

	      if (total == 0)
		prob = -1;
	      else
		{
		  rtx pat = PATTERN (arcptr->branch_insn);
		  
		  prob = (((double)ARC_COUNT (arcptr) * REG_BR_PROB_BASE)
			  + (total >> 1)) / total;
		  if (prob < 0 || prob > REG_BR_PROB_BASE)
		    {
		      if (dump_file)
			fprintf (dump_file, "bad count: prob for %d-%d thought to be %d (forcibly normalized)\n",
				 ARC_SOURCE (arcptr), ARC_TARGET (arcptr),
				 prob);

		      bad_counts = 1;
		      prob = REG_BR_PROB_BASE / 2;
		    }
		  
		  /* Match up probability with JUMP pattern.  */

		  if (GET_CODE (pat) == SET
		      && GET_CODE (SET_SRC (pat)) == IF_THEN_ELSE)
		    {
		      if (ARC_TARGET (arcptr) == ARC_SOURCE (arcptr) + 1)
			{
			  /* A fall through arc should never have a
			     branch insn.  */
			  abort ();
			}
		      else
			{
			  /* This is the arc for the taken branch.  */
			  if (GET_CODE (XEXP (SET_SRC (pat), 2)) != PC)
			    prob = REG_BR_PROB_BASE - prob;
			}
		    }
		}
	      
	      if (prob == -1)
		num_never_executed++;
	      else
		{
		  int index = prob * 20 / REG_BR_PROB_BASE;
		  if (index == 20)
		    index = 19;
		  hist_br_prob[index]++;
		}
	      num_branches++;
	      
	      REG_NOTES (arcptr->branch_insn)
		= gen_rtx (EXPR_LIST, REG_BR_PROB, GEN_INT (prob),
			   REG_NOTES (arcptr->branch_insn));
	    }
	}

      /* Add a REG_EXEC_COUNT note to the first instruction of this block.  */
      if (! binfo->first_insn 
	  || GET_RTX_CLASS (GET_CODE (binfo->first_insn)) != 'i')
	{
	  /* Block 0 is a fake block representing function entry, and does
	     not have a real first insn.  The second last block might not
	     begin with a real insn.  */
	  if (i == num_blocks - 1)
	    return_label_execution_count = total;
	  else if (i != 0 && i != num_blocks - 2)
	    abort ();
	}
      else
	{
	  REG_NOTES (binfo->first_insn)
	    = gen_rtx (EXPR_LIST, REG_EXEC_COUNT, GEN_INT (total),
		       REG_NOTES (binfo->first_insn));
	  if (i == num_blocks - 1)
	    return_label_execution_count = total;
	}
    }
  
  /* This should never happen.  */
  if (bad_counts)
    warning ("Arc profiling: some arc counts were bad.");

  if (dump_file)
    {
      fprintf (dump_file, "%d branches\n", num_branches);
      fprintf (dump_file, "%d branches never executed\n",
	       num_never_executed);
      if (num_branches)
	for (i = 0; i < 10; i++)
	  fprintf (dump_file, "%d%% branches in range %d-%d%%\n",
		   (hist_br_prob[i]+hist_br_prob[19-i])*100/num_branches,
		   5*i, 5*i+5);

      total_num_branches += num_branches;
      total_num_never_executed += num_never_executed;
      for (i = 0; i < 20; i++)
	total_hist_br_prob[i] += hist_br_prob[i];
    }

}

/* Initialize a new arc.
   ARCPTR is the empty adj_list this function fills in.
   SOURCE is the block number of the source block.
   TARGET is the block number of the target block.
   INSN is the insn which transfers control from SOURCE to TARGET,
   or zero if the transfer is implicit.  */

static void
init_arc (arcptr, source, target, insn)
     struct adj_list *arcptr;
     int source, target;
     rtx insn;
{
  ARC_TARGET (arcptr) = target;
  ARC_SOURCE (arcptr) = source;

  ARC_COUNT (arcptr) = 0;
  arcptr->count_valid = 0;
  arcptr->on_tree = 0;
  arcptr->fake = 0;
  arcptr->fall_through = 0;
  arcptr->branch_insn = insn;

  arcptr->succ_next = bb_graph[source].succ;
  bb_graph[source].succ = arcptr;
  bb_graph[source].succ_count++;

  arcptr->pred_next = bb_graph[target].pred;
  bb_graph[target].pred = arcptr;
  bb_graph[target].pred_count++;
}

/* This function searches all of the arcs in the program flow graph, and puts
   as many bad arcs as possible onto the spanning tree.  Bad arcs include
   fake arcs (needed for setjmp(), longjmp(), exit()) which MUST be on the
   spanning tree as they can't be instrumented.  Also, arcs which must be
   split when instrumented should be part of the spanning tree if possible.  */

static void
find_spanning_tree (num_blocks)
     int num_blocks;
{
  int i;
  struct adj_list *arcptr;
  struct bb_info *binfo = &bb_graph[0];

  /* Fake arcs must be part of the spanning tree, and are always safe to put
     on the spanning tree.  Fake arcs will either be a successor of node 0,