[tree-ssa][mainline] Fix counting of line executions in gcov

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

the following problem showed up with tree-ssa-branch + LOOP_EXPR
lowering patch; since gcov is unchanged there, it also applies for
mainline.

As far as I understand the code in accumulate_line_counts to determine
number of executions of a line that contains several basic blocks, it
tries to split the graph into elementary cycles.  The problem is that
there are a few bugs in the algorithm; when the cycle is found, it
should be removed by decreasing counts of all edges it belong to it,
this is not done.  Instead the markers of the path are left in the
graph, which does not work -- consider

         - 10 <---------
       /                 \
     /                     \
A   C -5-> D -5-> E --10--> B
  \   \         /          /
    \    -5->--          /
      ->-- 1 -----------

With current algorithm, a cycle B - C - D - E is found, contributing 5.
E is left marked as a part of the path, so it does not find any
other cycles, giving total result of 6 (with 1 from entry edge),
instead of 11 we want.

Zdenek

	* gcov.c (typedef struct arc_info): New field cs_count.
	(accumulate_line_counts): Find cycles correctly.

Index: gcov.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/gcov.c,v
retrieving revision 1.43.2.14
diff -c -3 -p -r1.43.2.14 gcov.c
*** gcov.c	23 Jul 2003 16:59:46 -0000	1.43.2.14
--- gcov.c	26 Aug 2003 17:23:42 -0000
*************** typedef struct arc_info
*** 82,87 ****
--- 82,89 ----
  
    /* transition counts.  */
    gcov_type count;
+   /* used in cycle search, so that we do not clobber original counts.  */
+   gcov_type cs_count;
  
    unsigned int count_valid : 1;
    unsigned int on_tree : 1;
*************** accumulate_line_counts (source_t *src)
*** 1622,1627 ****
--- 1624,1633 ----
  		  if (flag_branches)
  		    add_branch_counts (&src->coverage, arc);
  		}
+ 
+ 	      /* Initialize the cs_count.  */
+ 	      for (arc = block->succ; arc; arc = arc->succ_next)
+ 		arc->cs_count = arc->count;
  	    }
  
  	  /* Find the loops. This uses the algorithm described in
*************** accumulate_line_counts (source_t *src)
*** 1638,1644 ****
  
  	     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;
--- 1644,1651 ----
  
  	     For each loop we find, locate the arc with the smallest
  	     transition count, and add that to the cumulative
! 	     count.  Decrease flow over the cycle and remove the arc
! 	     from consideration.  */
  	  for (block = line->u.blocks; block; block = block->chain)
  	    {
  	      block_t *head = block;
*************** accumulate_line_counts (source_t *src)
*** 1664,1688 ****
  		  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.  */
--- 1671,1703 ----
  		  if (dst == block)
  		    {
  		      /* Found a closing arc.  */
! 		      gcov_type cycle_count = arc->cs_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->cs_count)
  			  {
! 			    cycle_count = probe_arc->cs_count;
  			    cycle_arc = probe_arc;
  			  }
  
  		      count += cycle_count;
  		      cycle_arc->cycle = 1;
+ 
+ 		      /* Remove the flow from the cycle.  */
+ 		      arc->cs_count -= cycle_count;
+ 		      for (dst = head; (probe_arc = dst->u.cycle.arc);
+ 			   dst = probe_arc->src)
+ 			probe_arc->cs_count -= cycle_count;
+ 
  		      /* Unwind to the cyclic arc.  */
  		      while (head != cycle_arc->src)
  			{
  			  arc = head->u.cycle.arc;
+ 			  head->u.cycle.arc = NULL;
  			  head = arc->src;
  			}
  		      /* Move on.  */