tree.h (VALUE_HANDLE_VUSES): New.

2005-12-29  Daniel Berlin  <dberlin@dberlin.org>

	* tree.h (VALUE_HANDLE_VUSES): New.
	(struct tree_value_handle): Add vuses.

	* tree-vn.c (struct val_expr_pair_d): Remove stmt, add vuses.
	(vn_compute): Remove stmt argument.
	Don't use vuses in hash value computation.
	(val_expr_pair_eq): Compare vuse lists.
	(copy_vuses_from_stmt): New function.
	(shared_vuses_from_stmt): Ditto.
	(vn_add): Rewrite in terms of vn_add_with_vuses.
	(vn_add_with_vuses): New function.
	(vn_lookup): Rewrite in terms of vn_lookup_with_vuses.
	(vn_lookup_with_vuses): New function.
	(vuses_compare): New function.
	(print_creation_to_file): Ditto.
	(vn_lookup_or_add): Rewrite to handle vuses.
	(sort_vuses): New function.
	(vn_lookup_or_add_with_vuses): Ditto.
	(vn_init): Initialize shared_lookup_vuses.
	(vn_delete): Free shared_lookup_vuses.

	* tree-ssa-pre.c: Update todo list.
	(bb_value_sets_t): Add rvuse_in, rvuse_out, rvuse_gen, and
	rvuse_kill.
	(RVUSE_IN): New macro.
	(RVUSE_GEN): Ditto.
	(RVUSE_KILL): Ditto.
	(RVUSE_OUT): Ditto.
	(modify_expr_node_pool): New function.
	(pretemp): New.
	(storetemp): Ditto.
	(mergephitemp): Ditto.
	(prephitemp): Ditto.
	(struct expr_pred_trans_d): Add vuses member.
	(expr_pred_trans_eq): Compare vuses.
	(phi_trans_lookup): Add vuses argument.
	(phi_trans_add): Ditto.
	(translate_vuses_through_block): New function.
	(phi_translate): Use vuses to ask about those expressions that can
	have vuses.
	Properly translate virtual uses through phis, and use
	vn_lookup_or_add_with vuses.  Handle tcc_reference.
	(phi_translate_set): Don't add pointless translations to the
	cache.
	(get_representative): New function.
	(vuses_dies_in_block_x): Ditto.
	(valid_in_set): Add block argument.  Check virtual use validity.
	(clean): Add block argument. Update call to valid_in_set
	(compute_antic_aux): Update call to clean.
	(dump_bitmap_of_names): New function.
	(compute_vuse_representatives): Ditto.
	(compute_rvuse): Ditto.
	(can_value_number_call): Modified to accept calls with vuses.
	(can_value_number_operation): New function.
	(can_PRE_operation): Ditto.
	(need_creation): New vector of stores that may need creation.
	(find_or_generate_expression): use can_PRE_operation.
	(create_expression_by_pieces): Handle INDIRECT_REF.
	Only create one temp until we have to change types.
	Mark new vars for renaming.
	(insert_into_preds_of_block): Ignore loopiness of loads.
	Use can_PRE_operation.
	Only create one temp until we have to chnge types.
	(insert_aux): Use can_PRE_operation.
	Don't pass name to insert_into_preds_of_block.
	(insert_extra_phis): Only use one temp until we have to change
	types.
	(poolify_tree): New function.
	(modify_expr_template): New var.
	(poolify_modify_expr): New function.
	(insert_fake_stores): Ditto.
	(realify_fake_stores): Ditto.
	(compute_avail): Use can_value_number_operation.
	(mark_operand_necessary): Return NULL for non-SSA names.
	(remove_dead_inserted_code): Update comment.
	(init_pre): Initialize pretemp, need_creation, storetemp,
	mergephitemp, prephitemp.
	Create modify_expr_node_pool.
	(fini_pre): Free modify_expr_node_pool and need_creation array.
	(execute_pre): Call insert_fake_stores, compute_rvuse, and
	realify_fake_stores. 
	* tree-flow.h (vn_compute): Fix prototype.
	(vn_add): Ditto.
	(vn_lookup): Ditto.
	(sort_vuses): New.
	(vn_lookup_or_add_with_vuses): Ditto.
	(vn_add_with_vuses): Ditto.
	(vn_lookup_with_vuses): Ditto.
	* passes.c (pass_may_alias): Add.

From-SVN: r109180

1 files changed, 187 insertions, 38 deletions

diff --git a/gcc/tree-vn.c b/gcc/tree-vn.c
index 8053187..0bc5c03 100644
--- a/gcc/tree-vn.c
+++ b/gcc/tree-vn.c
@@ -48,8 +48,8 @@ typedef struct val_expr_pair_d
   /* Associated expression.  */
   tree e;
 
-  /* for comparing Virtual uses in E.  */
-  tree stmt;
+  /* For comparing virtual uses in E.  */
+  VEC (tree, gc) *vuses;
 
   /* E's hash value.  */
   hashval_t hashcode;
@@ -77,16 +77,11 @@ make_value_handle (tree type)
    any).
    
    VAL can be used to iterate by passing previous value numbers (it is
-   used by iterative_hash_expr).
-
-   STMT is the stmt associated with EXPR for comparing virtual operands.  */
+   used by iterative_hash_expr).  */
 
 hashval_t
-vn_compute (tree expr, hashval_t val, tree stmt)
+vn_compute (tree expr, hashval_t val)
 {
-  ssa_op_iter iter;
-  tree vuse;
-
   /* EXPR must not be a statement.  We are only interested in value
      numbering expressions on the RHS of assignments.  */
   gcc_assert (expr);
@@ -94,17 +89,9 @@ vn_compute (tree expr, hashval_t val, tree stmt)
 	      || expr->common.ann->common.type != STMT_ANN);
 
   val = iterative_hash_expr (expr, val);
-
-  /* If the expression has virtual uses, incorporate them into the
-     hash value computed for EXPR.  */
-  if (stmt)
-    FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
-      val = iterative_hash_expr (vuse,  val);
-
   return val;
 }
 
-
 /* Compare two expressions E1 and E2 and return true if they are
    equal.  */
 
@@ -163,15 +150,26 @@ val_expr_pair_hash (const void *p)
 static int
 val_expr_pair_expr_eq (const void *p1, const void *p2)
 {
-  bool ret;
+  int i;
+  tree vuse1;
   const val_expr_pair_t ve1 = (val_expr_pair_t) p1;
   const val_expr_pair_t ve2 = (val_expr_pair_t) p2;
 
   if (! expressions_equal_p (ve1->e, ve2->e))
     return false;
 
-  ret = compare_ssa_operands_equal (ve1->stmt, ve2->stmt, SSA_OP_VUSE);
-  return ret;
+  if (ve1->vuses == ve2->vuses)
+    return true;
+
+  if (VEC_length (tree, ve1->vuses) != VEC_length (tree, ve2->vuses))
+    return false;
+
+  for (i = 0; VEC_iterate (tree, ve1->vuses, i, vuse1); i++)
+    {
+      if (VEC_index (tree, ve2->vuses, i) != vuse1)
+	return false;
+    }
+  return true;
 }
 
 
@@ -190,13 +188,68 @@ set_value_handle (tree e, tree v)
     gcc_assert (is_gimple_min_invariant (e));
 }
 
+/* Copy the virtual uses from STMT into a newly allocated VEC(tree),
+   and return the VEC(tree).  */
+
+static VEC (tree, gc) *
+copy_vuses_from_stmt (tree stmt)
+{
+  ssa_op_iter iter;
+  tree vuse;
+  VEC (tree, gc) *vuses = NULL;
+
+  if (!stmt)
+    return NULL;
+
+  FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
+    VEC_safe_push (tree, gc, vuses, vuse);
+
+  return vuses;
+}
+
+/* Place for shared_vuses_from_stmt to shove vuses.  */
+static VEC (tree, gc) *shared_lookup_vuses;
+
+/* Copy the virtual uses from STMT into SHARED_LOOKUP_VUSES.
+   This function will overwrite the current SHARED_LOOKUP_VUSES
+   variable.  */
+
+static VEC (tree, gc) *
+shared_vuses_from_stmt (tree stmt)
+{
+  ssa_op_iter iter;
+  tree vuse;
+
+  if (!stmt)
+    return NULL;
+
+  VEC_truncate (tree, shared_lookup_vuses, 0);
+
+  FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VUSE)
+    VEC_safe_push (tree, gc, shared_lookup_vuses, vuse);
+
+  if (VEC_length (tree, shared_lookup_vuses) > 1)
+    sort_vuses (shared_lookup_vuses);
+
+  return shared_lookup_vuses;
+}
+
+/* Insert EXPR into VALUE_TABLE with value VAL, and add expression
+   EXPR to the value set for value VAL.  */
+
+void
+vn_add (tree expr, tree val)
+{
+  vn_add_with_vuses (expr, val, NULL);
+}
 
 /* Insert EXPR into VALUE_TABLE with value VAL, and add expression
-   EXPR to the value set for value VAL.  STMT represents the stmt
-   associated with EXPR.  It is used when computing a hash value for EXPR.  */
+   EXPR to the value set for value VAL.  VUSES represents the virtual
+   use operands associated with EXPR.  It is used when computing a
+   hash value for EXPR.  */
 
 void
-vn_add (tree expr, tree val, tree stmt)
+vn_add_with_vuses (tree expr, tree val, VEC (tree, gc) *vuses)
 {
   void **slot;
   val_expr_pair_t new_pair;
@@ -204,8 +257,8 @@ vn_add (tree expr, tree val, tree stmt)
   new_pair = XNEW (struct val_expr_pair_d);
   new_pair->e = expr;
   new_pair->v = val;
-  new_pair->stmt = stmt;
-  new_pair->hashcode = vn_compute (expr, 0, stmt);
+  new_pair->vuses = vuses;
+  new_pair->hashcode = vn_compute (expr, 0);
   slot = htab_find_slot_with_hash (value_table, new_pair, new_pair->hashcode,
 				   INSERT);
   if (*slot)
@@ -213,7 +266,8 @@ vn_add (tree expr, tree val, tree stmt)
   *slot = (void *) new_pair;
 
   set_value_handle (expr, val);
-  add_to_value (val, expr);
+  if (TREE_CODE (val) == VALUE_HANDLE)
+    add_to_value (val, expr);
 }
 
 
@@ -225,6 +279,17 @@ vn_add (tree expr, tree val, tree stmt)
 tree
 vn_lookup (tree expr, tree stmt)
 {
+  return vn_lookup_with_vuses (expr, shared_vuses_from_stmt (stmt));
+}
+
+/* Search in VALUE_TABLE for an existing instance of expression EXPR,
+   and return its value, or NULL if none has been set.  VUSES is the
+   list of virtual use operands associated with EXPR.  It is used when
+   computing the hash value for EXPR.  */
+
+tree
+vn_lookup_with_vuses (tree expr, VEC (tree, gc) *vuses)
+{
   void **slot;
   struct val_expr_pair_d vep = {NULL, NULL, NULL, 0};
 
@@ -233,8 +298,8 @@ vn_lookup (tree expr, tree stmt)
     return expr;
 
   vep.e = expr;
-  vep.stmt = stmt;
-  vep.hashcode = vn_compute (expr, 0, stmt); 
+  vep.vuses = vuses;
+  vep.hashcode = vn_compute (expr, 0);
   slot = htab_find_slot_with_hash (value_table, &vep, vep.hashcode, NO_INSERT);
   if (!slot)
     return NULL_TREE;
@@ -243,10 +308,53 @@ vn_lookup (tree expr, tree stmt)
 }
 
 
+/* A comparison function for use in qsort to compare vuses.  Simply
+   subtracts version numbers.  */
+
+static int
+vuses_compare (const void *pa, const void *pb)
+{
+  const tree vusea = *((const tree *)pa);
+  const tree vuseb = *((const tree *)pb);
+  int sn = SSA_NAME_VERSION (vusea) - SSA_NAME_VERSION (vuseb);
+
+  return sn;
+}
+
+/* Print out the "Created value <x> for <Y>" statement to the
+   dump_file.
+   This is factored because both versions of lookup use it, and it
+   obscures the real work going on in those functions.  */
+
+static void
+print_creation_to_file (tree v, tree expr, VEC (tree, gc) *vuses)
+{
+  fprintf (dump_file, "Created value ");
+  print_generic_expr (dump_file, v, dump_flags);
+  fprintf (dump_file, " for ");
+  print_generic_expr (dump_file, expr, dump_flags);
+  
+  if (vuses && VEC_length (tree, vuses) != 0)
+    {
+      size_t i;
+      tree vuse;
+      
+      fprintf (dump_file, " vuses: (");
+      for (i = 0; VEC_iterate (tree, vuses, i, vuse); i++)
+	{
+	  print_generic_expr (dump_file, vuse, dump_flags);
+	  if (VEC_length (tree, vuses) - 1 != i)
+	    fprintf (dump_file, ",");
+	}
+      fprintf (dump_file, ")");
+    }		   
+  fprintf (dump_file, "\n");
+}
+
 /* Like vn_lookup, but creates a new value for expression EXPR, if
    EXPR doesn't already have a value.  Return the existing/created
-   value for EXPR.  STMT represents the stmt associated with EXPR.  It is used
-   when computing the hash value for EXPR.  */
+   value for EXPR.  STMT represents the stmt associated with EXPR.  It
+   is used when computing the VUSES for EXPR.  */
 
 tree
 vn_lookup_or_add (tree expr, tree stmt)
@@ -254,18 +362,17 @@ vn_lookup_or_add (tree expr, tree stmt)
   tree v = vn_lookup (expr, stmt);
   if (v == NULL_TREE)
     {
+      VEC(tree,gc) *vuses;
+
       v = make_value_handle (TREE_TYPE (expr));
+      vuses = copy_vuses_from_stmt (stmt);
+      sort_vuses (vuses);
 
       if (dump_file && (dump_flags & TDF_DETAILS))
-	{     
-	  fprintf (dump_file, "Created value ");
-	  print_generic_expr (dump_file, v, dump_flags);
-	  fprintf (dump_file, " for ");
-	  print_generic_expr (dump_file, expr, dump_flags);
-	  fprintf (dump_file, "\n");
-	}
+	print_creation_to_file (v, expr, vuses);
 
-      vn_add (expr, v, stmt);
+      VALUE_HANDLE_VUSES (v) = vuses;
+      vn_add_with_vuses (expr, v, vuses);
     }
 
   set_value_handle (expr, v);
@@ -273,6 +380,46 @@ vn_lookup_or_add (tree expr, tree stmt)
   return v;
 }
 
+/* Sort the VUSE array so that we can do equality comparisons
+   quicker on two vuse vecs.  */
+
+void 
+sort_vuses (VEC (tree,gc) *vuses)
+{
+  if (VEC_length (tree, vuses) > 1)
+    qsort (VEC_address (tree, vuses),
+	   VEC_length (tree, vuses),
+	   sizeof (tree),
+	   vuses_compare);
+}
+
+/* Like vn_lookup, but creates a new value for expression EXPR, if
+   EXPR doesn't already have a value.  Return the existing/created
+   value for EXPR.  STMT represents the stmt associated with EXPR.  It is used
+   when computing the hash value for EXPR.  */
+
+tree
+vn_lookup_or_add_with_vuses (tree expr, VEC (tree, gc) *vuses)
+{
+  tree v = vn_lookup_with_vuses (expr, vuses);
+  if (v == NULL_TREE)
+    {
+      v = make_value_handle (TREE_TYPE (expr));
+      sort_vuses (vuses);
+
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	print_creation_to_file (v, expr, vuses);
+
+      VALUE_HANDLE_VUSES (v) = vuses;
+      vn_add_with_vuses (expr, v, vuses);
+    }
+
+  set_value_handle (expr, v);
+
+  return v;
+}
+
+
 
 /* Get the value handle of EXPR.  This is the only correct way to get
    the value handle for a "thing".  If EXPR does not have a value
@@ -306,6 +453,7 @@ vn_init (void)
 {
   value_table = htab_create (511, val_expr_pair_hash,
 			     val_expr_pair_expr_eq, free);
+  shared_lookup_vuses = NULL;
 }
 
 
@@ -315,5 +463,6 @@ void
 vn_delete (void)
 {
   htab_delete (value_table);
+  VEC_free (tree, gc, shared_lookup_vuses);
   value_table = NULL;
 }