df-core.c: Added to header comments.

2006-05-23  Kenneth Zadeck <zadeck@naturalbridge.com>

        * df-core.c: Added to header comments.
	* df.h (df_ru_bb_info, df_rd_bb_info, df_lr_bb_info,
	df_ur_bb_info, df_urec_bb_info): Added comments.
	* df-problems (df_ref_bitmap, ru, rd, lr, ur, 
	urec, ri problems): Fixed header comments.
	(df_ru_transfer_function): Fixed in-out set dyslexia when copying 
	code from df_rd_transfer_function.

From-SVN: r114024

4 files changed, 142 insertions, 40 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 36612a3..d5ed078 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,13 @@
+2006-05-23  Kenneth Zadeck <zadeck@naturalbridge.com>
+
+        * df-core.c: Added to header comments.
+	* df.h (df_ru_bb_info, df_rd_bb_info, df_lr_bb_info,
+	df_ur_bb_info, df_urec_bb_info): Added comments.
+	* df-problems (df_ref_bitmap, ru, rd, lr, ur, 
+	urec, ri problems): Fixed header comments.
+	(df_ru_transfer_function): Fixed in-out set dyslexia when copying 
+	code from df_rd_transfer_function.
+	
 2006-05-23  Richard Sandiford  <richard@codesourcery.com>
 
 	* libgcc2.c (LIBGCC2_MAX_UNITS_PER_WORD): New macro.
diff --git a/gcc/df-core.c b/gcc/df-core.c
index 1d4aff2..f0c62c9 100644
--- a/gcc/df-core.c
+++ b/gcc/df-core.c
@@ -113,7 +113,10 @@ df_set_blocks, these blocks are added to the set of blocks.
 
 DF_ANALYZE causes all of the defined problems to be (re)solved.  It
 does not cause blocks to be (re)scanned at the rtl level unless no
-prior call is made to df_rescan_blocks.
+prior call is made to df_rescan_blocks.  When DF_ANALYZE is completes,
+the IN and OUT sets for each basic block contain the computer
+information.  The DF_*_BB_INFO macros can be used to access these
+bitvectors.
 
 
 DF_DUMP can then be called to dump the information produce to some
diff --git a/gcc/df-problems.c b/gcc/df-problems.c
index 051ec33..e12c28a 100644
--- a/gcc/df-problems.c
+++ b/gcc/df-problems.c
@@ -239,7 +239,9 @@ df_print_bb_index (basic_block bb, FILE *file)
 }
 
 
-/* Return the set of reference ids in CHAIN, caching the result in *BMAP.  */
+/* Return a bitmap for REGNO from the cache MAPS.  The bitmap is to
+   contain COUNT bits starting at START.  These bitmaps are not to be
+   changed since there is a cache of them.  */
 
 static inline bitmap
 df_ref_bitmap (bitmap *maps, unsigned int regno, int start, int count)
@@ -282,12 +284,41 @@ df_unset_seen (void)
    REACHING USES
 
    Find the locations in the function where each use site for a pseudo
-   can reach backwards.
+   can reach backwards.  In and out bitvectors are built for each basic
+   block.  The id field in the ref is used to index into these sets.
+   See df.h for details.
 
 ----------------------------------------------------------------------------*/
 
+/* This problem plays a large number of games for the sake of
+   efficiency.  
+   
+   1) The order of the bits in the bitvectors.  After the scanning
+   phase, all of the uses are sorted.  All of the uses for the reg 0
+   are first, followed by all uses for reg 1 and so on.
+   
+   2) There are two kill sets, one if the number of uses is less or
+   equal to DF_SPARSE_THRESHOLD and another if it is greater.
+
+   <= : There is a bitmap for each register, uses_sites[N], that is
+   built on demand.  This bitvector contains a 1 for each use or reg
+   N.
+
+   > : One level of indirection is used to keep from generating long
+   strings of 1 bits in the kill sets.  Bitvectors that are indexed
+   by the regnum are used to represent that there is a killing def
+   for the register.  The confluence and transfer functions use
+   these along with the bitmap_clear_range call to remove ranges of
+   bits without actually generating a knockout vector.
+
+   The kill and sparse_kill and the dense_invalidated_by_call and
+   sparse_invalidated_by call both play this game.  */
+
+/* Private data used to compute the solution for this problem.  These
+   data structures are not accessable outside of this module.  */
 struct df_ru_problem_data
 {
+
   bitmap *use_sites;            /* Bitmap of uses for each pseudo.  */
   unsigned int use_sites_size;  /* Size of use_sites.  */
   /* The set of defs to regs invalidated by call.  */
@@ -656,7 +687,7 @@ df_ru_transfer_function (struct dataflow *dflow, int bb_index)
       struct df *df = dflow->df;
       bool changed = false;
       bitmap tmp = BITMAP_ALLOC (NULL);
-      bitmap_copy (tmp, in);
+      bitmap_copy (tmp, out);
       EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
 	{
 	  bitmap_clear_range (tmp, 
@@ -668,7 +699,7 @@ df_ru_transfer_function (struct dataflow *dflow, int bb_index)
       changed = !bitmap_equal_p (tmp, in);
       if (changed)
 	{
-	  BITMAP_FREE (out);
+	  BITMAP_FREE (in);
 	  bb_info->in = tmp;
 	}
       else 
@@ -810,16 +841,29 @@ df_ru_add_problem (struct df *df, int flags)
    REACHING DEFINITIONS
 
    Find the locations in the function where each definition site for a
-   pseudo reaches.
-----------------------------------------------------------------------------*/
+   pseudo reaches.  In and out bitvectors are built for each basic
+   block.  The id field in the ref is used to index into these sets.
+   See df.h for details.
+   ----------------------------------------------------------------------------*/
+
+/* See the comment at the top of the Reaching Uses problem for how the
+   uses are represented in the kill sets. The same games are played
+   here for the defs.  */
 
+/* Private data used to compute the solution for this problem.  These
+   data structures are not accessable outside of this module.  */
 struct df_rd_problem_data
 {
+  /* If the number of defs for regnum N is less than
+     DF_SPARSE_THRESHOLD, uses_sites[N] contains a mask of the all of
+     the defs of reg N indexed by the id in the ref structure.  If
+     there are more than DF_SPARSE_THRESHOLD defs for regnum N a
+     different mechanism is used to mask the def.  */
   bitmap *def_sites;            /* Bitmap of defs for each pseudo.  */
   unsigned int def_sites_size;  /* Size of def_sites.  */
   /* The set of defs to regs invalidated by call.  */
   bitmap sparse_invalidated_by_call;  
-  /* The set of defs to regs invalidate by call for ru.  */  
+  /* The set of defs to regs invalidate by call for rd.  */  
   bitmap dense_invalidated_by_call;   
 };
 
@@ -1321,9 +1365,11 @@ df_rd_add_problem (struct df *df, int flags)
 /*----------------------------------------------------------------------------
    LIVE REGISTERS
 
-   Find the locations in the function where any use of a pseudo can reach
-   in the backwards direction.
-----------------------------------------------------------------------------*/
+   Find the locations in the function where any use of a pseudo can
+   reach in the backwards direction.  In and out bitvectors are built
+   for each basic block.  The regnum is used to index into these sets.
+   See df.h for details.
+   ----------------------------------------------------------------------------*/
 
 /* Get basic block info.  */
 
@@ -1734,7 +1780,9 @@ df_lr_add_problem (struct df *df, int flags)
    UNINITIALIZED REGISTERS
 
    Find the set of uses for registers that are reachable from the entry
-   block without passing thru a definition.
+   block without passing thru a definition.  In and out bitvectors are built
+   for each basic block.  The regnum is used to index into these sets.
+   See df.h for details.
 ----------------------------------------------------------------------------*/
 
 /* Get basic block info.  */
@@ -2088,12 +2136,18 @@ df_ur_add_problem (struct df *df, int flags)
    UNINITIALIZED REGISTERS WITH EARLYCLOBBER
 
    Find the set of uses for registers that are reachable from the entry
-   block without passing thru a definition.
+   block without passing thru a definition.  In and out bitvectors are built
+   for each basic block.  The regnum is used to index into these sets.
+   See df.h for details.
 
    This is a variant of the UR problem above that has a lot of special
-   features just for the register allocation phase.
-----------------------------------------------------------------------------*/
+   features just for the register allocation phase.  This problem
+   should go a away if someone would fix the interference graph.
+
+   ----------------------------------------------------------------------------*/
 
+/* Private data used to compute the solution for this problem.  These
+   data structures are not accessable outside of this module.  */
 struct df_urec_problem_data
 {
   bool earlyclobbers_found;     /* True if any instruction contains an
@@ -3089,8 +3143,13 @@ df_chain_add_problem (struct df *df, int flags)
 /*----------------------------------------------------------------------------
    REGISTER INFORMATION
 
-   Currently this consists of only lifetime information and reg_dead
-   and reg_unused.  
+   This pass properly computes REG_DEAD and REG_UNUSED notes.
+
+   If the DF_RI_LIFE flag is set the following vectors containing
+   information about register usage are properly set: REG_N_REFS,
+   REG_N_DEATHS, REG_N_SETS, REG_LIVE_LENGTH, REG_N_CALLS_CROSSED,
+   REG_N_THROWING_CALLS_CROSSED and REG_BASIC_BLOCK.
+
    ----------------------------------------------------------------------------*/
 
 #ifdef REG_DEAD_DEBUGGING
diff --git a/gcc/df.h b/gcc/df.h
index b1e9384..c27bbdc 100644
--- a/gcc/df.h
+++ b/gcc/df.h
@@ -491,55 +491,85 @@ struct df_scan_bb_info
 };
 
 
-/* Reaching uses.  */
+/* Reaching uses.  All bitmaps are indexed by the id field of the ref
+   except sparse_kill (see below).  */
 struct df_ru_bb_info 
 {
+  /* Local sets to describe the basic blocks.  */
+  /* The kill set is the set of uses that are killed in this block.
+     However, if the number of uses for this register is greater than
+     DF_SPARSE_THRESHOLD, the sparse_kill is used instead. In
+     sparse_kill, each register gets a slot and a 1 in this bitvector
+     means that all of the uses of that register are killed.  This is
+     a very useful efficiency hack in that it keeps from having push
+     around big groups of 1s.  This is implemened by the
+     bitmap_clear_range call.  */
+
   bitmap kill;
   bitmap sparse_kill;
-  bitmap gen;
-  bitmap in;
-  bitmap out;
+  bitmap gen;   /* The set of uses generated in this block.  */
+
+  /* The results of the dataflow problem.  */
+  bitmap in;    /* At the top of the block.  */
+  bitmap out;   /* At the bottom of the block.  */
 };
 
 
-/* Reaching definitions.  */
+/* Reaching definitions.  All bitmaps are indexed by the id field of
+   the ref except sparse_kill (see above).  */
 struct df_rd_bb_info 
 {
-  bitmap kill;
+  /* Local sets to describe the basic blocks.  See the note in the RU
+     datastructures for kill and sparse_kill.  */
+  bitmap kill;  
   bitmap sparse_kill;
-  bitmap gen;
-  bitmap in;
-  bitmap out;
+  bitmap gen;   /* The set of defs generated in this block.  */
+
+  /* The results of the dataflow problem.  */
+  bitmap in;    /* At the top of the block.  */
+  bitmap out;   /* At the bottom of the block.  */
 };
 
 
-/* Live registers.  */
+/* Live registers.  All bitmaps are referenced by the register number.  */
 struct df_lr_bb_info 
 {
-  bitmap def;
-  bitmap use;
-  bitmap in;
-  bitmap out;
+  /* Local sets to describe the basic blocks.  */
+  bitmap def;   /* The set of registers set in this block.  */
+  bitmap use;   /* The set of registers used in this block.  */
+
+  /* The results of the dataflow problem.  */
+  bitmap in;    /* At the top of the block.  */
+  bitmap out;   /* At the bottom of the block.  */
 };
 
 
-/* Uninitialized registers.  */
+/* Uninitialized registers.  All bitmaps are referenced by the register number.  */
 struct df_ur_bb_info 
 {
-  bitmap kill;
-  bitmap gen;
-  bitmap in;
-  bitmap out;
+  /* Local sets to describe the basic blocks.  */
+  bitmap kill;  /* The set of registers unset in this block.  Calls,
+		   for instance, unset registers.  */
+  bitmap gen;   /* The set of registers set in this block.  */
+
+  /* The results of the dataflow problem.  */
+  bitmap in;    /* At the top of the block.  */
+  bitmap out;   /* At the bottom of the block.  */
 };
 
-/* Uninitialized registers.  */
+/* Uninitialized registers.  All bitmaps are referenced by the register number.  */
 struct df_urec_bb_info 
 {
-  bitmap earlyclobber;
+  /* Local sets to describe the basic blocks.  */
+  bitmap earlyclobber;  /* The set of registers that are referenced
+			   with an an early clobber mode.  */
+  /* Kill and gen are defined as in the UR problem.  */
   bitmap kill;
   bitmap gen;
-  bitmap in;
-  bitmap out;
+
+  /* The results of the dataflow problem.  */
+  bitmap in;    /* At the top of the block.  */
+  bitmap out;   /* At the bottom of the block.  */
 };