profile doc patch

[Nathan Sidwell <nathan at codesourcery dot com>]

Hi,
I've installed this patch to both source comments and the documentation
proper. It explains the profile coverage spanning tree theory, and
some other bits.

nathan
-- 
Dr Nathan Sidwell   ::   http://www.codesourcery.com   ::   CodeSourcery LLC
         'But that's a lie.' - 'Yes it is. What's your point?'
nathan@codesourcery.com : http://www.cs.bris.ac.uk/~nathan/ : nathan@acm.org
2002-07-29  Nathan Sidwell  <nathan@codesourcery.com>

	* profile.c: Add file comment describing the overall algorithm and
	structures.
	(struct edge_info): Add comments.
	(struct bb_info): Add comments.
	* basic-block.h (EDGE_*): Add comments.
	* doc/gcov.texi (Gcov Data Files): Document bit flags.

Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.157
diff -c -3 -p -r1.157 basic-block.h
*** basic-block.h	21 Jul 2002 14:32:24 -0000	1.157
--- basic-block.h	29 Jul 2002 18:17:13 -0000
*************** typedef struct edge_def {
*** 135,147 ****
  				   in profile.c  */
  } *edge;
  
! #define EDGE_FALLTHRU		1
! #define EDGE_ABNORMAL		2
! #define EDGE_ABNORMAL_CALL	4
! #define EDGE_EH			8
! #define EDGE_FAKE		16
! #define EDGE_DFS_BACK		32
! #define EDGE_CAN_FALLTHRU	64
  
  #define EDGE_COMPLEX	(EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_EH)
  
--- 135,150 ----
  				   in profile.c  */
  } *edge;
  
! #define EDGE_FALLTHRU		1	/* 'Straight line' flow */
! #define EDGE_ABNORMAL		2	/* Strange flow, like computed
! 					   label, or eh */
! #define EDGE_ABNORMAL_CALL	4	/* Call with abnormal exit
! 					   like an exception, or sibcall */
! #define EDGE_EH			8	/* Exception throw */
! #define EDGE_FAKE		16	/* Not a real edge (profile.c) */
! #define EDGE_DFS_BACK		32	/* A backwards edge */
! #define EDGE_CAN_FALLTHRU	64	/* Candidate for straight line
! 					   flow. */
  
  #define EDGE_COMPLEX	(EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_EH)
  
Index: profile.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/profile.c,v
retrieving revision 1.94
diff -c -3 -p -r1.94 profile.c
*** profile.c	21 Jul 2002 22:01:58 -0000	1.94
--- profile.c	29 Jul 2002 18:17:14 -0000
*************** along with GCC; see the file COPYING.  I
*** 22,27 ****
--- 22,61 ----
  Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  02111-1307, USA.  */
  
+ /* Generate basic block profile instrumentation and auxiliary files.
+    Profile generation is optimized, so that not all arcs in the basic
+    block graph need instrumenting. First, the BB graph is closed with
+    one entry (function start), and one exit (function exit).  Any
+    ABNORMAL_EDGE cannot be instrumented (because there is no control
+    path to place the code). We close the graph by inserting fake
+    EDGE_FAKE edges to the EXIT_BLOCK, from the sources of abnormal
+    edges that do not go to the exit_block. We ignore such abnormal
+    edges.  Naturally these fake edges are never directly traversed,
+    and so *cannot* be directly instrumented.  Some other graph
+    massaging is done. To optimize the instrumentation we generate the
+    BB minimal span tree, only edges that are not on the span tree
+    (plus the entry point) need instrumenting. From that information
+    all other edge counts can be deduced.  By construction all fake
+    edges must be on the spanning tree. We also attempt to place
+    EDGE_CRITICAL edges on the spanning tree.
+ 
+    The two auxiliary files generated are <dumpbase>.bb and
+    <dumpbase>.bbg. The former contains the BB->linenumber
+    mappings, and the latter describes the BB graph.
+ 
+    The BB file contains line numbers for each block. For each basic
+    block, a zero count is output (to mark the start of a block), then
+    the line numbers of that block are listed. A zero ends the file
+    too.
+ 
+    The BBG file contains a count of the blocks, followed by edge
+    information, for every edge in the graph. The edge information
+    lists the source and target block numbers, and a bit mask
+    describing the type of edge.
+ 
+    The BB and BBG file formats are fully described in the gcov
+    documentation.  */
+ 
  /* ??? Register allocation should use basic block execution counts to
     give preference to the most commonly executed blocks.  */
  
*************** Software Foundation, 59 Temple Place - S
*** 54,71 ****
  #include "langhooks.h"
  
  /* Additional information about the edges we need.  */
! struct edge_info
!   {
!     unsigned int count_valid : 1;
!     unsigned int on_tree : 1;
!     unsigned int ignore : 1;
!   };
! struct bb_info
!   {
!     unsigned int count_valid : 1;
!     gcov_type succ_count;
!     gcov_type pred_count;
!   };
  
  #define EDGE_INFO(e)  ((struct edge_info *) (e)->aux)
  #define BB_INFO(b)  ((struct bb_info *) (b)->aux)
--- 88,111 ----
  #include "langhooks.h"
  
  /* Additional information about the edges we need.  */
! struct edge_info {
!   unsigned int count_valid : 1;
!   
!   /* Is on the spanning tree. */
!   unsigned int on_tree : 1;
!   
!   /* Pretend this edge does not exist (it is abnormal and we've
!      inserted a fake to compensate). */
!   unsigned int ignore : 1;
! };
! 
! struct bb_info {
!   unsigned int count_valid : 1;
! 
!   /* Number of successor and predecessor edges. */
!   gcov_type succ_count;
!   gcov_type pred_count;
! };
  
  #define EDGE_INFO(e)  ((struct edge_info *) (e)->aux)
  #define BB_INFO(b)  ((struct bb_info *) (b)->aux)
Index: doc/gcov.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/gcov.texi,v
retrieving revision 1.8
diff -c -3 -p -r1.8 gcov.texi
*** doc/gcov.texi	9 May 2002 12:54:19 -0000	1.8
--- doc/gcov.texi	29 Jul 2002 18:17:56 -0000
*************** functions within those files, and line n
*** 348,359 ****
  basic block in the source file.
  
  The @file{.bb} file format consists of several lists of 4-byte integers
! which correspond to the line numbers of each basic block in the
! file.  Each list is terminated by a line number of 0.  A line number of @minus{}1
! is used to designate that the source file name (padded to a 4-byte
! boundary and followed by another @minus{}1) follows.  In addition, a line number
! of @minus{}2 is used to designate that the name of a function (also padded to a
! 4-byte boundary and followed by a @minus{}2) follows.
  
  The @file{.bbg} file is used to reconstruct the program flow graph for
  the source file.  It contains a list of the program flow arcs (possible
--- 348,360 ----
  basic block in the source file.
  
  The @file{.bb} file format consists of several lists of 4-byte integers
! which correspond to the line numbers of each basic block in the file.
! Each list is terminated by a line number of 0.  A line number of
! @minus{}1 is used to designate that the source file name (padded to a
! 4-byte boundary and followed by another @minus{}1) follows.  In
! addition, a line number of @minus{}2 is used to designate that the name
! of a function (also padded to a 4-byte boundary and followed by a
! @minus{}2) follows.
  
  The @file{.bbg} file is used to reconstruct the program flow graph for
  the source file.  It contains a list of the program flow arcs (possible
*************** correctly.
*** 388,393 ****
--- 389,410 ----
  The function name is stored as a @minus{}1 (4 bytes), the length (4 bytes),
  the name itself (padded to 4-byte boundary) followed by a @minus{}1 (4 bytes).
  
+ The flags are defined as follows:
+ @itemize
+ @item bit0 
+ On function spanning tree
+ 
+ @item bit1
+ Is a fake edge
+ 
+ @item bit2
+ Is the fall through edge from one block to its immediate successor.
+ 
+ @item bit3-bit31
+ For future expansion
+ 
+ @end itemize
+ 
  The @file{.da} file is generated when a program containing object files
  built with the GCC @option{-fprofile-arcs} option is executed.  A
  separate @file{.da} file is created for each source file compiled with
*************** this option, and the name of the @file{.
*** 395,401 ****
  absolute pathname in the resulting object file.  This path name is
  derived from the source file name by substituting a @file{.da} suffix.
  
! The @file{.da} consists of several blocks (one for each run) with the following structure:
  @smallexample
          "magic" number @minus{}123 (4-byte number)
  	number of functions (4-byte number)
--- 412,419 ----
  absolute pathname in the resulting object file.  This path name is
  derived from the source file name by substituting a @file{.da} suffix.
  
! The @file{.da} consists of several blocks (one for each run) with the
! following structure:
  @smallexample
          "magic" number @minus{}123 (4-byte number)
  	number of functions (4-byte number)