2004-06-17 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.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@83290 138bc75d-0d04-0410-961f-82ee72b054a4

2 files changed, 165 insertions, 70 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 17ffc884dcb..551a2ec8792 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,16 @@
+2004-06-17  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.
+
 2004-06-17  Ulrich Weigand  <uweigand@de.ibm.com>
 
 	* config/s390/s390-modes.def (CCL3mode): New machine mode.
diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index fe7738c185d..e98fbfc6025 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -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, tree);
 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 pred)
 }
 
 
-/* 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_t set, tree e)
 #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_t set, tree e)
       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_set_t set,
 	   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, ", ");
 	}
@@ -921,9 +999,9 @@ phi_translate (tree expr, value_set_t set,  basic_block pred,
 	  return NULL;
 	if (newop1 != oldop1)
 	  {
-	    newexpr = pool_alloc (unary_node_pool);	   
+	    newexpr = pool_alloc (unary_node_pool);
 	    memcpy (newexpr, expr, tree_size (expr));
-	    create_expr_ann (newexpr);
+	    create_expr_ann (newexpr);	 
 	    TREE_OPERAND (newexpr, 0) = get_value_handle (newop1);
 	    lookup_or_add (value_table, newexpr);
 	    expr = newexpr;
@@ -1047,9 +1125,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)
@@ -1179,6 +1257,7 @@ compute_antic_aux (basic_block block)
       value_insert_into_set (ANTIC_IN (block), node->expr);
     }
   clean (ANTIC_IN (block));
+  
 
   if (!set_equal (old, ANTIC_IN (block)))
     changed = true;
@@ -1274,12 +1353,12 @@ insert_aux (basic_block block)
 		      tree *avail;
 		      tree val;
 		      bool by_some = false;
+		      bool cant_insert = false;
 		      bool all_same = true;
 		      tree first_s = NULL;
 		      edge pred;
 		      basic_block bprime;
 		      tree eprime;
-		      bool cant_insert = false;
 
 		      val = get_value_handle (node->expr);
 		      if (set_contains_value (PHI_GEN (block), val))
@@ -1331,7 +1410,7 @@ insert_aux (basic_block block)
 			  else
 			    {
 			      avail[bprime->index] = edoubleprime;
-			      by_some = true;
+			      by_some = true; 
 			      if (first_s == NULL)
 				first_s = edoubleprime;
 			      else if (first_s != edoubleprime)
@@ -1341,11 +1420,14 @@ insert_aux (basic_block block)
 				abort ();
 			    }
 			}
-
+		      /* If we can insert it, it's not the same value
+			 already existing along every predecessor, and
+			 it's defined by some predecessor, it is
+			 partially redundant.  */
 		      if (!cant_insert && !all_same && by_some)
 			{
-			  tree temp;
 			  tree type = TREE_TYPE (avail[block->pred->src->index]);
+			  tree temp;
 			  tree v;
 
 			  if (dump_file && (dump_flags & TDF_DETAILS))