[PATCH]: Add missing comments to GVNPRE

[Daniel Berlin <dberlin at dberlin dot org>]

This adds the comments to structure fields, adds comments in a few 
more key places, makes sure all comments are up to date, renames a few 
variables so they make  sense, etc.  Just general cleanup, no functional 
changes.

2004-06-16  Daniel Berlin  <dberlin@dberlin.org>

	* tree-ssa-pre.c:  Update comments.
	(val_expr_pair_eq): Factor code from here.
	(expr_pred_trans_eq): and here.
	(expressions_equal_p): To here.
	(print_value_set): Print value for expression.
	(phi_trans_lookup): Rename some variables.
	(lookup): Ditto.
	(value_exists_in_set_bitmap): Ditto.
	(value_remove_from_set_bitmap): Ditto.
	(value_insert_into_set_bitmap): Ditto.

Index: tree-ssa-pre.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-pre.c,v
retrieving revision 2.11
diff -u -3 -p -r2.11 tree-ssa-pre.c
--- tree-ssa-pre.c	17 Jun 2004 02:46:43 -0000	2.11
+++ tree-ssa-pre.c	17 Jun 2004 02:47:23 -0000
@@ -182,19 +182,38 @@ Boston, MA 02111-1307, USA.  */
    expressions/constants/values.  */
 typedef struct value_set_node
 {
+  /* An expression.  */
   tree expr;
+
+  /* A pointer to the next element of the value set.  */
   struct value_set_node *next;
 } *value_set_node_t;


-/* A value set, which is the head of the linked list, and we also keep
-   the tail because we have to append for the topolofical sort.  */
+/* A value set.  This is a singly linked list of value_set_node
+   elements with a possible bitmap that tells us what values exist in
+   the set.  This set must be kept in topologically sorted order.  */
 typedef struct value_set
 {
+  /* The head of the list.  Used for iterating over the list in
+     order.  */
   value_set_node_t head;
+
+  /* The tail of the list.  Used for tail insertions, which are
+     necessary to keep the set in topologically sorted order because
+     of how the set is built.  */
   value_set_node_t tail;
+ 
+  /* The length of the list.  */
   size_t length;
+ 
+  /* True if the set is indexed, which means it contains a backing
+     bitmap for quick determination of whether certain values exist in the
+     set.  */
   bool indexed;
+ 
+  /* The bitmap of values that exist in the set.  May be NULL in an
+     empty or non-indexed set.  */
   bitmap values;

 } *value_set_t;
@@ -202,13 +221,32 @@ typedef struct value_set
 /* All of the following sets, except for TMP_GEN, are indexed.
    TMP_GEN is only ever iterated over, we never check what values
    exist in it.  */
+
 typedef struct bb_value_sets
 {
+  /* The EXP_GEN set, which represents expressions/values generated in
+     a basic block.  */
   value_set_t exp_gen;
+
+  /* The PHI_GEN set, which represents PHI results generated in a
+     basic block.  */
   value_set_t phi_gen;
+
+  /* The TMP_GEN set, which represents results/temporaries genererated
+     in a basic block. IE the LHS of an expression.  */
   value_set_t tmp_gen;
+
+  /* The AVAIL_OUT set, which represents which values are available in
+     a given basic block.  */
   value_set_t avail_out;
+
+  /* The ANTIC_IN set, which represents which values are anticiptable
+     in a given basic block.  */
   value_set_t antic_in;
+
+  /* The NEW_SETS set, which is used during insertion to augment the
+     AVAIL_OUT set of blocks with the new insertions performed during
+     the current iteration.  */
   value_set_t new_sets;
 } *bb_value_sets_t;

@@ -219,10 +257,17 @@ typedef struct bb_value_sets
 #define ANTIC_IN(BB)	((bb_value_sets_t) ((BB)->aux))->antic_in
 #define NEW_SETS(BB)	((bb_value_sets_t) ((BB)->aux))->new_sets

+/* This structure is used to keep track of statistics on what
+   optimization PRE was able to perform.  */
 static struct
 {
+  /* The number of RHS computations eliminated by PRE.  */
   int eliminations;
+
+  /* The number of new expressions/temporaries generated by PRE.  */
   int insertions;
+
+  /* The number of new PHI nodes added by PRE.  */
   int phis;
 } pre_stats;

@@ -232,6 +277,7 @@ static void insert_into_set (value_set_t
 static void add_to_value (tree, tree);
 static value_set_t set_new  (bool);
 static bool is_undefined_value (tree);
+static bool expressions_equal_p (tree, tree);

 /* We can add and remove elements and entries to and from sets
    and hash tables, so we use alloc pools for them.  */
@@ -242,12 +288,34 @@ static alloc_pool binary_node_pool;
 static alloc_pool unary_node_pool;

 /* The value table that maps expressions to values.  */
+
 static htab_t value_table;

 /* The phi_translate_table caches phi translations for a given
    expression and predecessor.  */
+
 static htab_t phi_translate_table;

+/* Compare two expressions E1 and E2 and return true if they are
+   equal.  */
+
+static bool
+expressions_equal_p (tree e1, tree e2)
+{
+  tree te1, te2;
+ 
+  if (e1 == e2)
+    return true;
+ 
+  te1 = TREE_TYPE (e1);
+  te2 = TREE_TYPE (e2);
+
+  if (TREE_CODE (e1) == TREE_CODE (e2) 
+      && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2))
+      && operand_equal_p (e1, e2, 0))
+    return true;
+  return false;
+}

 /* Map expressions to values.  These are simple pairs of expressions
    and the values they represent.  To find the value represented by
@@ -261,7 +329,9 @@ typedef struct val_expr_pair_d
 } *val_expr_pair_t;


-/* Hash a {v,e} pair.  We really only hash the expression.  */
+/* Hash a {v,e} pair that is pointed to by P.
+   The hashcode is cached in the val_expr_pair, so we just return
+   that.  */

 static hashval_t
 val_expr_pair_hash (const void *p)
@@ -271,34 +341,26 @@ val_expr_pair_hash (const void *p)
 }


-/* Are {e2,v2} and {e1,v1} the same?  Again, only the expression
-   matters.  */
+/* Given two val_expr_pair_t's, return true if they represent the same
+   expression, false otherwise.
+   P1 and P2 should point to the val_expr_pair_t's to be compared.  */

 static int
 val_expr_pair_expr_eq (const void *p1, const void *p2)
 {
   const val_expr_pair_t ve1 = (val_expr_pair_t) p1;
   const val_expr_pair_t ve2 = (val_expr_pair_t) p2;
-  tree e1 = ve1->e;
-  tree e2 = ve2->e;
-  tree te1;
-  tree te2;
-  if (e1 == e2)
-    return true;

-  te1 = TREE_TYPE (e1);
-  te2 = TREE_TYPE (e2);
-  if (TREE_CODE (e1) == TREE_CODE (e2) 
-      && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2))
-      && operand_equal_p (e1, e2, 0))
+  if (expressions_equal_p (ve1->e, ve2->e))
     return true;
-
+
   return false;
 }


 /* Get the value handle of EXPR.  This is the only correct way to get
-   the value handle for a "thing".  */
+   the value handle for a "thing". 
+   Returns NULL if the value handle does not exist.  */

 tree
 get_value_handle (tree expr)
@@ -328,7 +390,7 @@ get_value_handle (tree expr)
 }


-/* Set the value handle for E to V */
+/* Set the value handle for expression E to value V */

 void
 set_value_handle (tree e, tree v)
@@ -348,9 +410,17 @@ set_value_handle (tree e, tree v)

 typedef struct expr_pred_trans_d
 {
+  /* The expression. */
   tree e;
+
+  /* The predecessor block along which we translated the expression.  */
   basic_block pred;
+
+  /* The value that resulted from the translation.  */
   tree v;
+
+  /* The hashcode for the expression, pred pair. This is cached for
+     speed reasons.  */
   hashval_t hashcode;
 } *expr_pred_trans_t;

@@ -363,49 +433,44 @@ expr_pred_trans_hash (const void *p)
   return ve->hashcode;
 }

-/* Return true if two phi translation table entries are the same.  */
+/* Return true if two phi translation table entries are the same.
+   P1 and P2 should point to the expr_pred_trans_t's to be compared.*/

 static int
 expr_pred_trans_eq (const void *p1, const void *p2)
 {
   const expr_pred_trans_t ve1 = (expr_pred_trans_t) p1;
   const expr_pred_trans_t ve2 = (expr_pred_trans_t) p2;
-  tree e1 = ve1->e;
-  tree e2 = ve2->e;
   basic_block b1 = ve1->pred;
   basic_block b2 = ve2->pred;
-  tree te1;
-  tree te2;

+ 
+  /* If they are not translations for the same basic block, they can't
+     be equal.  */
   if (b1 != b2)
     return false;

-  if (e1 == e2)
-    return true;
- 
-  te1 = TREE_TYPE (e1);
-  te2 = TREE_TYPE (e2);
-
-  if (TREE_CODE (e1) == TREE_CODE (e2) 
-      && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2))
-      && operand_equal_p (e1, e2, 0))
+  /* If they are for the same basic block, determine if the
+     expressions are equal.   */ 
+  if (expressions_equal_p (ve1->e, ve2->e))
     return true;

   return false;
 }

-/* Search in the phi translation table for the translation of E in
-   PRED. Return the translated value, if found, NULL otherwise.  */
+/* Search in the phi translation table for the translation of
+   expression E in basic block PRED. Return the translated value, if
+   found, NULL otherwise. */

 static inline tree
 phi_trans_lookup (tree e, basic_block pred)
 {
   void **slot;
-  struct expr_pred_trans_d ugly;
-  ugly.e = e;
-  ugly.pred = pred;
-  ugly.hashcode = iterative_hash_expr (e, (unsigned long) pred);
-  slot = htab_find_slot_with_hash (phi_translate_table, &ugly, ugly.hashcode,
+  struct expr_pred_trans_d ept;
+  ept.e = e;
+  ept.pred = pred;
+  ept.hashcode = iterative_hash_expr (e, (unsigned long) pred);
+  slot = htab_find_slot_with_hash (phi_translate_table, &ept, ept.hashcode,
 				   NO_INSERT);
   if (!slot)
     return NULL;
@@ -414,7 +479,8 @@ phi_trans_lookup (tree e, basic_block pr
 }


-/* Add the tuple mapping {e, pred}->v to the phi translation table.  */
+/* Add the tuple mapping from {expression E, basic block PRED} to
+   value V, to the phi translation table.  */

 static inline void
 phi_trans_add (tree e, tree v, basic_block pred)
@@ -439,17 +505,17 @@ static inline tree
 lookup (htab_t table, tree e)
 {
   void **slot;
-  struct val_expr_pair_d ugly = {NULL, NULL, 0};
-  ugly.e = e;
-  ugly.hashcode = iterative_hash_expr (e,0); 
-  slot = htab_find_slot_with_hash (table, &ugly, ugly.hashcode, NO_INSERT);
+  struct val_expr_pair_d vep = {NULL, NULL, 0};
+  vep.e = e;
+  vep.hashcode = iterative_hash_expr (e,0); 
+  slot = htab_find_slot_with_hash (table, &vep, vep.hashcode, NO_INSERT);
   if (!slot)
     return NULL_TREE;
   else
     return ((val_expr_pair_t) *slot)->v;
 }

-/* Add E to the expression set of V.  */
+/* Add expression E to the expression set of value V.  */

 static inline void
 add_to_value (tree v, tree e)
@@ -480,7 +546,8 @@ add_to_value (tree v, tree e)
 #endif
 }

-/* Insert E into TABLE with value V, and add E to the value set for V.  */
+/* Insert E into TABLE with value V, and add expression E to the value
+   set for value V.  */

 static inline void
 add (htab_t table, tree e, tree v)
@@ -502,9 +569,12 @@ add (htab_t table, tree e, tree v)

 }

+/* A unique counter that is incremented every time we create a new
+   value.  */
 static int pre_uid;

-/* Create a new value handle for EXPR.  */
+/* Create a new value handle for expression EXPR.  */
+
 static tree
 create_new_value (tree expr)
 {
@@ -523,7 +593,10 @@ create_new_value (tree expr)
   return a;
 }

-/* Like lookup, but adds V as the value for E if E does not have a value.  */
+/* Like lookup, but creates a new value for expression E if E doesn't
+   already have a value.
+   Return the existing/created value for E.  */
+
 static inline tree
 lookup_or_add (htab_t table, tree e)
 {
@@ -540,25 +613,25 @@ lookup_or_add (htab_t table, tree e)
 }


-/* Search in the bitmap for SET to see if E exists.  */
+/* Return true if value V exists in the bitmap for SET.  */

 static inline bool
-value_exists_in_set_bitmap (value_set_t set, tree e)
+value_exists_in_set_bitmap (value_set_t set, tree v)
 {
-  if (TREE_CODE (e) != VAR_DECL)
+  if (TREE_CODE (v) != VAR_DECL)
     abort ();

   if (!set->values)
     return false;
-  return bitmap_bit_p (set->values, get_var_ann (e)->uid);
+  return bitmap_bit_p (set->values, get_var_ann (v)->uid);
 }

-/* Remove E from the bitmap for SET.  */
+/* Remove value V from the bitmap for SET.  */

 static void
-value_remove_from_set_bitmap (value_set_t set, tree e)
+value_remove_from_set_bitmap (value_set_t set, tree v)
 {
-  if (TREE_CODE (e) != VAR_DECL)
+  if (TREE_CODE (v) != VAR_DECL)
     abort ();
 #ifdef ENABLE_CHECKING
   if (!set->indexed)
@@ -566,17 +639,17 @@ value_remove_from_set_bitmap (value_set_
 #endif
   if (!set->values)
     return;
-  bitmap_clear_bit (set->values, get_var_ann (e)->uid);
+  bitmap_clear_bit (set->values, get_var_ann (v)->uid);
 }


-/* Insert the value number E into the bitmap of values existing in
+/* Insert the value number V into the bitmap of values existing in
    SET.  */

 static inline void
-value_insert_into_set_bitmap (value_set_t set, tree e)
+value_insert_into_set_bitmap (value_set_t set, tree v)
 {
-  if (TREE_CODE (e) != VAR_DECL)
+  if (TREE_CODE (v) != VAR_DECL)
     abort ();
 #ifdef ENABLE_CHECKING
   if (!set->indexed)
@@ -587,7 +660,7 @@ value_insert_into_set_bitmap (value_set_
       set->values = BITMAP_GGC_ALLOC ();
       bitmap_clear (set->values);
     }
-  bitmap_set_bit (set->values, get_var_ann (e)->uid);
+  bitmap_set_bit (set->values, get_var_ann (v)->uid);
 }

 /* Create a new set.  */
@@ -824,6 +897,11 @@ print_value_set (FILE *outfile, value_se
 	   node = node->next)
 	{
 	  print_generic_expr (outfile, node->expr, 0);
+ 
+	  fprintf (outfile, " (");
+	  print_generic_expr (outfile, get_value_handle (node->expr), 0);
+	  fprintf (outfile, ") ");
+
 	  if (node->next)
 	    fprintf (outfile, ", ");
 	}
@@ -1047,9 +1126,9 @@ valid_in_set (value_set_t set, tree expr
   return false;
 }

-/* Clean the set of expressions that are no longer valid in the
-   specified set.  This means expressions that are made up of values
-   we have no leaders for in the current set, etc.  */
+/* Clean the set of expressions that are no longer valid in SET.  This
+   means expressions that are made up of values we have no leaders for
+   in SET.  */

 static void
 clean (value_set_t set)