[gcov]: Fix loop detection

[Nathan Sidwell <nathan at codesourcery dot com>]

Hi,
I've installed this obvious fix for the loop detection needed in gcov's
all-block mode - silly me was using the wrong algorithm. It also tweaks
which line blocks are attached to in that mode (their last), which fits
better with non-block mode, and user intuition.

booted & tested on i686-pc-linux-gnu.

nathan
--
Nathan Sidwell    ::   http://www.codesourcery.com   ::     CodeSourcery LLC
         The voices in my head said this was stupid too
nathan at codesourcery dot com : http://www.cs.bris.ac.uk/~nathan/ : nathan at acm dot org

2003-04-05  Nathan Sidwell  <nathan at codesourcery dot com>

	* gcov.c (struct arc_info): Replace local_span with cycle.
	(struct block_info): Replace u.span with u.cycle. Add is_call_return.
	(solve_flow_graph): Set is_call_return.
	(add_line_counts): Adjust. In block mode, blocks attach to last line.
	(accumulate_line_counts): Find graph cycles, not spanning tree.
	(output_branch_count): Adjust.
	(output_lines): Adjust.
	* doc/gcov.texi: Update.

Index: gcov.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/gcov.c,v
retrieving revision 1.55
diff -c -3 -p -r1.55 gcov.c
*** gcov.c	4 Apr 2003 15:48:19 -0000	1.55
--- gcov.c	6 Apr 2003 11:19:47 -0000
*************** typedef struct arc_info
*** 96,104 ****
    /* Is an unconditional branch.  */
    unsigned int is_unconditional : 1;
  
!   /* Arc on the local block spanning tree. */
!   unsigned int local_span : 1;
!   
    /* Next branch on line.  */
    struct arc_info *line_next;
    
--- 96,104 ----
    /* Is an unconditional branch.  */
    unsigned int is_unconditional : 1;
  
!   /* Loop making arc.  */
!   unsigned int cycle : 1;
! 
    /* Next branch on line.  */
    struct arc_info *line_next;
    
*************** typedef struct block_info
*** 128,134 ****
    unsigned invalid_chain : 1;
  
    /* Block is a call instrumenting site.  */
!   unsigned is_call_site : 1;
  
    /* Block is a landing pad for longjmp or throw.  */
    unsigned is_nonlocal_return : 1;
--- 128,135 ----
    unsigned invalid_chain : 1;
  
    /* Block is a call instrumenting site.  */
!   unsigned is_call_site : 1; /* Does the call.  */
!   unsigned is_call_return : 1; /* Is the return.  */
  
    /* Block is a landing pad for longjmp or throw.  */
    unsigned is_nonlocal_return : 1;
*************** typedef struct block_info
*** 146,155 ****
      } line; /* Valid until blocks are linked onto lines */
      struct
      {
!       /* Single line spanning tree workspace.  Used for all-blocks mode. */
!       struct block_info *root;
!       unsigned siblings;
!     } span; /* Used in all-blocks mode, after blocks are linked onto
  	       lines. */
    } u;
  
--- 147,157 ----
      } line; /* Valid until blocks are linked onto lines */
      struct
      {
!       /* Single line graph cycle workspace.  Used for all-blocks
! 	 mode. */
!       arc_t *arc;
!       unsigned ident;
!     } cycle; /* Used in all-blocks mode, after blocks are linked onto
  	       lines. */
    } u;
  
*************** solve_flow_graph (fn)
*** 1185,1201 ****
  		arc->is_unconditional = 1;
  		/* If this block is instrumenting a call, it might be
  		   an artifical block. It is not artificial if it has
! 		   a non-fallthrough exit, or the destination of the
! 		   exit has more than one entry.  */
! 		if (!arc->fall_through
! 		    || arc->dst->pred != arc || arc->pred_next)
! 		  blk->is_call_site = 0;
  	      }
  	}
-       else
- 	/* If there is more than one exit, it cannot be an artificial
- 	   call instrumenting site.  */
- 	blk->is_call_site = 0;
        
        /* Sort the successor arcs into ascending dst order. profile.c
  	 normally produces arcs in the right order, but sometimes with
--- 1187,1201 ----
  		arc->is_unconditional = 1;
  		/* If this block is instrumenting a call, it might be
  		   an artifical block. It is not artificial if it has
! 		   a non-fallthrough exit, or the destination of this
! 		   arc has more than one entry.  Mark the destination
! 		   block as a return site, if none of those conditions
! 		   hold.  */
! 		if (blk->is_call_site && arc->fall_through
! 		    && arc->dst->pred == arc && !arc->pred_next)
! 		  arc->dst->is_call_return = 1;
  	      }
  	}
        
        /* Sort the successor arcs into ascending dst order. profile.c
  	 normally produces arcs in the right order, but sometimes with
*************** add_line_counts (coverage, fn)
*** 1558,1564 ****
        unsigned *encoding;
        const source_t *src = NULL;
        unsigned jx;
-       line_t *first_line = NULL;
  
        if (block->count && ix && ix + 1 != fn->num_blocks)
  	fn->blocks_executed++;
--- 1558,1563 ----
*************** add_line_counts (coverage, fn)
*** 1585,1607 ****
  	      }
  	    line->exists = 1;
  	    line->count += block->count;
- 	    if (!first_line)
- 	      first_line = line;
  	  }
        free (block->u.line.encoding);
!       block->u.span.root = NULL;
!       if (!first_line)
! 	first_line = line;
! 	  
        if (!ix || ix + 1 == fn->num_blocks)
  	/* Entry or exit block */;
        else if (flag_all_blocks)
  	{
! 	  if (!first_line)
! 	    first_line = &fn->src->lines[fn->line];
  	  
! 	  block->chain = first_line->u.blocks;
! 	  first_line->u.blocks = block;
  	}
        else if (flag_branches)
  	{
--- 1584,1602 ----
  	      }
  	    line->exists = 1;
  	    line->count += block->count;
  	  }
        free (block->u.line.encoding);
!       block->u.cycle.arc = NULL;
!       block->u.cycle.ident = ~0U;
!       
        if (!ix || ix + 1 == fn->num_blocks)
  	/* Entry or exit block */;
        else if (flag_all_blocks)
  	{
! 	  line_t *block_line = line ? line : &fn->src->lines[fn->line];
  	  
! 	  block->chain = block_line->u.blocks;
! 	  block_line->u.blocks = block;
  	}
        else if (flag_branches)
  	{
*************** accumulate_line_counts (src)
*** 1661,1670 ****
  	  /* The user expects the line count to be the number of times
  	     a line has been executed. Simply summing the block count
  	     will give an artificially high number.  The Right Thing
! 	     is to generate the spanning tree of the blocks on this
! 	     line, and the sum the entry arcs to that tree.  */
  	  block_t *block, *block_p, *block_n;
- 	  int changes = 1;
  	  gcov_type count = 0;
  	  
  	  /* Reverse the block information */
--- 1656,1665 ----
  	  /* The user expects the line count to be the number of times
  	     a line has been executed. Simply summing the block count
  	     will give an artificially high number.  The Right Thing
! 	     is to sum the entry counts to the graph of blocks on this
! 	     line, then find the elementary cycles of the local graph
! 	     and add the transition counts of those cycles.  */
  	  block_t *block, *block_p, *block_n;
  	  gcov_type count = 0;
  	  
  	  /* Reverse the block information */
*************** accumulate_line_counts (src)
*** 1673,1749 ****
  	    {
  	      block_n = block->chain;
  	      block->chain = block_p;
! 	      /* Each block is it's own spanning tree, with no siblings  */
! 	      block->u.span.root = block;
! 	      block->u.span.siblings = 0;
  	    }
  	  line->u.blocks = block_p;
  
! 	  while (changes)
  	    {
! 	      changes = 0;
  	      
! 	      for (block = line->u.blocks; block; block = block->chain)
  		{
! 		  arc_t *arc;
  		  
! 		  for (arc = block->succ; arc; arc = arc->succ_next)
  		    {
! 		      block_t *dst = arc->dst;
  		      
! 		      if (!dst->u.span.root)
! 			/* Not on this line.  */;
! 		      else if (dst->u.span.root == block->u.span.root)
! 			/* Same spanning tree.  */;
! 		      else
  			{
! 			  block_t *root = block->u.span.root;
! 			  block_t *dst_root = dst->u.span.root;
! 
! 			  /* Join spanning trees */
! 			  if (root->u.span.siblings
! 			      && !dst_root->u.span.siblings)
! 			    {
! 			      root = dst->u.span.root;
! 			      dst_root = block->u.span.root;
! 			    }
! 			  
! 			  dst_root->u.span.root = root;
! 			  root->u.span.siblings
! 			    += 1 + dst_root->u.span.siblings;
! 			  
! 			  if (dst_root->u.span.siblings)
! 			    {
! 			      block_t *dst_sib;
! 			      
! 			      dst_root->u.span.siblings = 0;
! 			      for (dst_sib = line->u.blocks; dst_sib;
! 				   dst_sib = dst_sib->chain)
! 				if (dst_sib->u.span.root == dst_root)
! 				  dst_sib->u.span.root = root;
! 			    }
! 			  arc->local_span = 1;
! 			  changes = 1;
  			}
  		    }
  		}
! 	    }
! 
! 	  /* Now sum the entry counts */
! 	  for (block = line->u.blocks; block; block = block->chain)
! 	    {
! 	      arc_t *arc;
! 
! 	      for (arc = block->succ; arc; arc = arc->succ_next)
  		{
! 		  if (!arc->local_span)
! 		    count += arc->count;
! 		  if (flag_branches)
! 		    add_branch_counts (&src->coverage, arc);
  		}
! 	      block->u.span.root = NULL;
  	    }
! 	  
  	  line->count = count;
  	}
        
--- 1668,1777 ----
  	    {
  	      block_n = block->chain;
  	      block->chain = block_p;
! 	      block->u.cycle.ident = ix;
  	    }
  	  line->u.blocks = block_p;
+ 	  
+ 	  /* Sum the entry arcs.  */
+ 	  for (block = line->u.blocks; block; block = block->chain)
+ 	    {
+ 	      arc_t *arc;
  
! 	      for (arc = block->pred; arc; arc = arc->pred_next)
! 		{
! 		  if (arc->src->u.cycle.ident != ix)
! 		    count += arc->count;
! 		  if (flag_branches)
! 		    add_branch_counts (&src->coverage, arc);
! 		}
! 	    }
! 
! 	  /* Find the loops. This uses the algorithm described in
! 	     Tiernan 'An Efficient Search Algorithm to Find the
! 	     Elementary Circuits of a Graph', CACM Dec 1970. We hold
! 	     the P array by having each block point to the arc that
! 	     connects to the previous block. The H array is implicitly
! 	     held because of the arc ordering, and the block's
! 	     previous arc pointer.
! 
! 	     Although the algorithm is O(N^3) for highly connected
! 	     graphs, at worst we'll have O(N^2), as most blocks have
! 	     only one or two exits. Most graphs will be small.
! 
! 	     For each loop we find, locate the arc with the smallest
! 	     transition count, and add that to the cumulative
! 	     count. Remove the arc from consideration.  */
! 	  for (block = line->u.blocks; block; block = block->chain)
  	    {
! 	      block_t *head = block;
! 	      arc_t *arc;
  	      
! 	    next_vertex:;
! 	      arc = head->succ;
! 	    current_vertex:;
! 	      while (arc)
  		{
! 		  block_t *dst = arc->dst;
! 		  if (/* Already used that arc.  */
! 		      arc->cycle
! 		      /* Not to same graph, or before first vertex.  */
! 		      || dst->u.cycle.ident != ix
! 		      /* Already in path.  */
! 		      || dst->u.cycle.arc)
! 		    {
! 		      arc = arc->succ_next;
! 		      continue;
! 		    }
  		  
! 		  if (dst == block)
  		    {
! 		      /* Found a closing arc.  */
! 		      gcov_type cycle_count = arc->count;
! 		      arc_t *cycle_arc = arc;
! 		      arc_t *probe_arc;
  		      
! 		      /* Locate the smallest arc count of the loop. */
! 		      for (dst = head; (probe_arc = dst->u.cycle.arc);
! 			   dst = probe_arc->src)
! 			if (cycle_count > probe_arc->count)
! 			  {
! 			    cycle_count = probe_arc->count;
! 			    cycle_arc = probe_arc;
! 			  }
! 		      
! 		      count += cycle_count;
! 		      cycle_arc->cycle = 1;
! 		      /* Unwind to the cyclic arc.  */
! 		      while (head != cycle_arc->src)
  			{
! 			  arc = head->u.cycle.arc;
! 			  head = arc->src;
  			}
+ 		      /* Move on.  */
+ 		      arc = arc->succ_next;
+ 		      continue;
  		    }
+ 		  
+ 		  /* Add new block to chain.  */
+ 		  dst->u.cycle.arc = arc;
+ 		  head = dst;
+ 		  goto next_vertex;
  		}
! 	      /* We could not add another vertex to the path. Remove
! 		 the last vertex from the list.  */
! 	      arc = head->u.cycle.arc;
! 	      if (arc)
  		{
! 		  /* It was not the first vertex. Move onto next arc. */
! 		  head->u.cycle.arc = NULL;
! 		  head = arc->src;
! 		  arc = arc->succ_next;
! 		  goto current_vertex;
  		}
! 	      /* Mark this block as unusable.  */
! 	      block->u.cycle.ident = ~0U;
  	    }
! 
  	  line->count = count;
  	}
        
*************** output_branch_count (gcov_file, ix, arc)
*** 1786,1792 ****
        else
  	fnotice (gcov_file, "branch %2d never executed\n", ix);
      }
!   else if (flag_unconditional && !arc->src->is_call_site)
      {
        if (arc->src->count)
  	fnotice (gcov_file, "unconditional %2d taken %s\n", ix,
--- 1814,1820 ----
        else
  	fnotice (gcov_file, "branch %2d never executed\n", ix);
      }
!   else if (flag_unconditional && !arc->dst->is_call_return)
      {
        if (arc->src->count)
  	fnotice (gcov_file, "unconditional %2d taken %s\n", ix,
*************** output_lines (gcov_file, src)
*** 1895,1911 ****
        if (flag_all_blocks)
  	{
  	  block_t *block;
  	  int ix, jx;
  	  
  	  for (ix = jx = 0, block = line->u.blocks; block;
  	       block = block->chain)
  	    {
! 	      arc_t *arc;
! 
! 	      if (!block->is_call_site)
  		fprintf (gcov_file, "%9s:%5u-block %2d\n",
  			 !line->exists ? "-" : !block->count ? "$$$$$"
! 			 : format_gcov (block->count, 0, -1), line_num, ix++);
  	      if (flag_branches)
  		for (arc = block->succ; arc; arc = arc->succ_next)
  		  jx += output_branch_count (gcov_file, jx, arc);
--- 1923,1939 ----
        if (flag_all_blocks)
  	{
  	  block_t *block;
+ 	  arc_t *arc;
  	  int ix, jx;
  	  
  	  for (ix = jx = 0, block = line->u.blocks; block;
  	       block = block->chain)
  	    {
! 	      if (!block->is_call_return)
  		fprintf (gcov_file, "%9s:%5u-block %2d\n",
  			 !line->exists ? "-" : !block->count ? "$$$$$"
! 			 : format_gcov (block->count, 0, -1),
! 			 line_num, ix++);
  	      if (flag_branches)
  		for (arc = block->succ; arc; arc = arc->succ_next)
  		  jx += output_branch_count (gcov_file, jx, arc);
Index: doc/gcov.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/gcov.texi,v
retrieving revision 1.15
diff -c -3 -p -r1.15 gcov.texi
*** doc/gcov.texi	31 Mar 2003 15:18:24 -0000	1.15
--- doc/gcov.texi	6 Apr 2003 12:47:27 -0000
*************** and exit without doing any further proce
*** 152,162 ****
  Write individual execution counts for every basic block. Normally gcov
  outputs execution counts only for the main blocks of a line. With this
  option you can determine if blocks within a single line are not being
! executed. In this mode each block is shown, and contributes to the
! occupancy and execution count of, the first line of source that it
! contains. A multi-line block will only contribute to that first line,
! and other lines will not be show to contain code, unless a subsequent
! block begins on those lines.
  
  @item -b
  @itemx --branch-probabilities
--- 152,158 ----
  Write individual execution counts for every basic block. Normally gcov
  outputs execution counts only for the main blocks of a line. With this
  option you can determine if blocks within a single line are not being
! executed.
  
  @item -b
  @itemx --branch-probabilities
*************** function main called 1 returned 1 blocks
*** 327,332 ****
--- 323,339 ----
          -:   17:@}
  @end smallexample
  
+ In this mode, each basic block is only shown on one line -- the last
+ line of the block. A multi-line block will only contribute to the
+ execution count of that last line, and other lines will not be shown
+ to contain code, unless previous blocks end on those lines.
+ The total execution count of a line is shown and subsequent lines show
+ the execution counts for individual blocks that end on that line. After each
+ block, the branch and call counts of the block will be shown, if the
+ @option{-b} option is given.
+ 
+ Because of the way gcc instruments calls, a call count can be shown
+ after a line with no individual blocks.
  As you can see, line 13 contains a basic block that was not executed.
  
  @need 450

/* Test gcov block mode.  */

/* { dg-options "-fprofile-arcs -ftest-coverage" } */
/* { dg-do run { target native } } */

int main ()
{
  unsigned ix;
  
  for (ix = 10; ix--;); /* count(11) */

  return 0;
}

/* { dg-final { run-gcov { -a gcov-9.c } } } */

/* Test gcov block mode.  */

/* { dg-options "-fprofile-arcs -ftest-coverage" } */
/* { dg-do run { target native } } */

int main ()
{
  unsigned ix, jx = 0;
  
  for (ix = 10; ix--;) if (ix & 1) jx++; /* count(11) */

  return jx != 5;
}

/* { dg-final { run-gcov { -a gcov-10.c } } } */

/* Test gcov block mode.  */

/* { dg-options "-fprofile-arcs -ftest-coverage" } */
/* { dg-do run { target native } } */

int one = 1; /* subvert constant folder. */
int zero = 0;

int foo (int ix)
{
  return ix & 1 ? one : zero; /* count(10) */
}

int main ()
{
  unsigned ix, jx = 0;
  
  for (ix = 10; ix--;) jx += foo (ix); /* count(11) */

  return jx != 5;
}

/* { dg-final { run-gcov { -a gcov-11.c } } } */