2008-07-05 Daniel Berlin <dberlin@dberlin.org>

	
	Fix PR tree-optimization/23455
	Fix PR tree-optimization/35286
	Fix PR tree-optimization/35287
	* Makefile.in (OBJS-common): Remove tree-vn.o.
	tree-vn.o: Remove.
	* dbgcnt.def: Add treepre_insert debug counter.
	* gcc/tree-flow.h (add_to_value): Updated for other changes.
	(debug_value_expressions): Ditto.
	(print_value_expressions): Ditto.
	* tree-pretty-print.c (dump_generic_node): Updated for
	VALUE_HANDLE removal.
	* tree-ssa-dom.c (record_equality): Ditto.
	(cprop_operand): Ditto.
	(lookup_avail_expr): Ditto.
	* tree-ssa-threadedge.c
	(record_temporary_equivalences_from_stmts_at_dest): Ditto.
	(simplify_control_stmt_condition): Ditto.
	* tree.c (tree_code_size): Ditto.
	(tree_node_structure): Ditto.
	(iterative_hash_expr): Ditto.
	* tree.def: Ditto.
	* tree.h (VALUE_HANDLE_ID): Ditto.
	(VALUE_HANDLE_EXPR_SET): Ditto.
	(struct tree_value_handle): Ditto.
	(union tree_node): Ditto.
	* treestruct.def: Ditto.
	* tree-vn.c: Removed.
	* tree-ssa-pre.c: Rewritten entirely.
	* tree-ssa-sccvn.c (constant_to_value_id): New hashtable.
	(constant_value_ids): Ditto.
	(vn_nary_op_t): Moved to header.
	(vn_phi_t): Ditto.
	(vn_reference_op_t): Ditto
	(vn_reference_t): Ditto.
	(next_value_id): New variable.
	(VN_INFO): Add an assert.
	(vn_constant_eq): New function.
	(vn_constant_hash): Ditto.
	(get_or_alloc_constant_value_id): Ditto.
	(value_id_constant_p): Ditto.
	(vn_reference_compute_hash): De-staticify.
	(copy_reference_ops_from_ref): Don't use get_callee_fndecl.
	Disable some code with a FIXME.
	Remove VALUE_HANDLE use.
	(valueize_refs): Update opcode if it changes from ssa name to
	constant.
	(vn_reference_lookup_1): Add new argument.
	(vn_reference_lookup):  Ditto.
	(vn_reference_lookup_pieces): New function.
	(vn_reference_insert): Add return type. Modify to deal with value
	ids.
	(vn_reference_insert_pieces):  New function.
	(vn_nary_op_compute_hash): De-staticify.
	(vn_nary_op_eq): Ditto.
	(vn_nary_op_lookup_pieces): New function.
	(vn_nary_op_lookup): Add new argument.  
	(vn_nary_op_insert_pieces): New function.
	(vn_nary_op_insert): Add return type. Modify to deal with value
	ids.
	(vn_phi_insert): Ditto.
	(visit_unary_op): Update for callee changes.
	(visit_binary_op): Ditto.
	(visit_reference_op_load): Ditto.
	(visit_reference_op_store): Ditto.
	(init_scc_vn): Init next_value_id, constant_to_value_id and
	constant_value_ids. 
	(free_scc_vn): Free them.
	(set_hashtable_value_ids): New function.
	(run_scc_vn): Use it.
	(get_max_value_id): New function.
	(get_next_value_id): Ditto.
	(expressions_equal_p): Moved from tree-vn.c
	(sort_vuses): Ditto.
	(sort_vuses_heap): Ditto.
	* tree-ssa-sccvn.h: Structures moved from tree-ssa-sccvn.c (noted
	above).
	* tree.c (iterative_hash_hashval_t): Made non-static
	* tree.h (iterative_hash_hashval_t): Declare it.



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

1 files changed, 501 insertions, 109 deletions

diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
index 99cc08d8445..659fecdfa8a 100644
--- a/gcc/tree-ssa-sccvn.c
+++ b/gcc/tree-ssa-sccvn.c
@@ -115,72 +115,9 @@ typedef struct vn_tables_s
   alloc_pool references_pool;
 } *vn_tables_t;
 
-/* Nary operations in the hashtable consist of length operands, an
-   opcode, and a type.  Result is the value number of the operation,
-   and hashcode is stored to avoid having to calculate it
-   repeatedly.  */
+static htab_t constant_to_value_id;
+static bitmap constant_value_ids;
 
-typedef struct vn_nary_op_s
-{
-  ENUM_BITFIELD(tree_code) opcode : 16;
-  unsigned length : 16;
-  hashval_t hashcode;
-  tree result;
-  tree type;
-  tree op[4];
-} *vn_nary_op_t;
-typedef const struct vn_nary_op_s *const_vn_nary_op_t;
-
-/* Phi nodes in the hashtable consist of their non-VN_TOP phi
-   arguments, and the basic block the phi is in. Result is the value
-   number of the operation, and hashcode is stored to avoid having to
-   calculate it repeatedly.  Phi nodes not in the same block are never
-   considered equivalent.  */
-
-typedef struct vn_phi_s
-{
-  VEC (tree, heap) *phiargs;
-  basic_block block;
-  hashval_t hashcode;
-  tree result;
-} *vn_phi_t;
-typedef const struct vn_phi_s *const_vn_phi_t;
-
-/* Reference operands only exist in reference operations structures.
-   They consist of an opcode, type, and some number of operands.  For
-   a given opcode, some, all, or none of the operands may be used.
-   The operands are there to store the information that makes up the
-   portion of the addressing calculation that opcode performs.  */
-
-typedef struct vn_reference_op_struct
-{
-  enum tree_code opcode;
-  tree type;
-  tree op0;
-  tree op1;
-} vn_reference_op_s;
-typedef vn_reference_op_s *vn_reference_op_t;
-typedef const vn_reference_op_s *const_vn_reference_op_t;
-
-DEF_VEC_O(vn_reference_op_s);
-DEF_VEC_ALLOC_O(vn_reference_op_s, heap);
-
-/* A reference operation in the hashtable is representation as a
-   collection of vuses, representing the memory state at the time of
-   the operation, and a collection of operands that make up the
-   addressing calculation.  If two vn_reference_t's have the same set
-   of operands, they access the same memory location. We also store
-   the resulting value number, and the hashcode.  The vuses are
-   always stored in order sorted by ssa name version.  */
-
-typedef struct vn_reference_s
-{
-  VEC (tree, gc) *vuses;
-  VEC (vn_reference_op_s, heap) *operands;
-  hashval_t hashcode;
-  tree result;
-} *vn_reference_t;
-typedef const struct vn_reference_s *const_vn_reference_t;
 
 /* Valid hashtables storing information we have proven to be
    correct.  */
@@ -215,6 +152,10 @@ static int *rpo_numbers;
 
 tree VN_TOP;
 
+/* Unique counter for our value ids.  */
+
+static unsigned int next_value_id;
+
 /* Next DFS number and the stack for strongly connected component
    detection. */
 
@@ -239,8 +180,10 @@ static struct obstack vn_ssa_aux_obstack;
 vn_ssa_aux_t
 VN_INFO (tree name)
 {
-  return VEC_index (vn_ssa_aux_t, vn_ssa_aux_table,
-		    SSA_NAME_VERSION (name));
+  vn_ssa_aux_t res = VEC_index (vn_ssa_aux_t, vn_ssa_aux_table,
+				SSA_NAME_VERSION (name));
+  gcc_assert (res);
+  return res;
 }
 
 /* Set the value numbering info for a given SSA name to a given
@@ -290,6 +233,58 @@ free_reference (void *vp)
   VEC_free (vn_reference_op_s, heap, vr->operands);
 }
 
+/* Hash table equality function for vn_constant_t.  */
+
+static int
+vn_constant_eq (const void *p1, const void *p2)
+{
+  const struct vn_constant_s *vc1 = (const struct vn_constant_s *) p1;
+  const struct vn_constant_s *vc2 = (const struct vn_constant_s *) p2;
+
+  return expressions_equal_p (vc1->constant, vc2->constant);
+}
+
+/* Hash table hash function for vn_constant_t.  */
+   
+static hashval_t
+vn_constant_hash (const void *p1)
+{
+  const struct vn_constant_s *vc1 = (const struct vn_constant_s *) p1;
+  return vc1->hashcode;
+}
+
+/* Lookup a value id for CONSTANT, and if it does not exist, create a
+   new one and return it.  If it does exist, return it.  */
+
+unsigned int
+get_or_alloc_constant_value_id (tree constant)
+{
+  void **slot;
+  vn_constant_t vc = XNEW (struct vn_constant_s);
+  
+  vc->hashcode = iterative_hash_expr (constant, 0);
+  vc->constant = constant;
+  slot = htab_find_slot_with_hash (constant_to_value_id, vc,
+				   vc->hashcode, INSERT);  
+  if (*slot)
+    {
+      free (vc);
+      return ((vn_constant_t)*slot)->value_id;
+    }
+  vc->value_id = get_next_value_id ();
+  *slot = vc;
+  bitmap_set_bit (constant_value_ids, vc->value_id);
+  return vc->value_id;
+}
+
+/* Return true if V is a value id for a constant.  */
+
+bool
+value_id_constant_p (unsigned int v)
+{
+  return bitmap_bit_p (constant_value_ids, v);  
+}
+
 /* Compare two reference operands P1 and P2 for equality.  Return true if
    they are equal, and false otherwise.  */
 
@@ -301,7 +296,8 @@ vn_reference_op_eq (const void *p1, const void *p2)
   return vro1->opcode == vro2->opcode
     && vro1->type == vro2->type
     && expressions_equal_p (vro1->op0, vro2->op0)
-    && expressions_equal_p (vro1->op1, vro2->op1);
+    && expressions_equal_p (vro1->op1, vro2->op1)
+    && expressions_equal_p (vro1->op2, vro2->op2);
 }
 
 /* Compute the hash for a reference operand VRO1.  */
@@ -324,7 +320,7 @@ vn_reference_hash (const void *p1)
 
 /* Compute a hash for the reference operation VR1 and return it.  */
 
-static inline hashval_t
+hashval_t
 vn_reference_compute_hash (const vn_reference_t vr1)
 {
   hashval_t result = 0;
@@ -343,7 +339,7 @@ vn_reference_compute_hash (const vn_reference_t vr1)
 /* Return true if reference operations P1 and P2 are equivalent.  This
    means they have the same set of operands and vuses.  */
 
-static int
+int
 vn_reference_eq (const void *p1, const void *p2)
 {
   tree v;
@@ -484,10 +480,18 @@ copy_reference_ops_from_ref (tree ref, VEC(vn_reference_op_s, heap) **result)
       temp.type = TREE_TYPE (ref);
       temp.opcode = CALL_EXPR;
       VEC_safe_push (vn_reference_op_s, heap, *result, &temp);
-
-      callfn = get_callee_fndecl (ref);
-      if (!callfn)
-	callfn = CALL_EXPR_FN (ref);
+      
+      /* We make no attempt to simplify the called function because
+      the typical &FUNCTION_DECL form is also used in function pointer
+      cases that become constant.  If we simplify the original to
+      FUNCTION_DECL but not the function pointer case (which can
+      happen because we have no fold functions that operate on
+      vn_reference_t), we will claim they are not equivalent.
+
+      An example of this behavior can be see if CALL_EXPR_FN below is
+      replaced with get_callee_fndecl and gcc.dg/tree-ssa/ssa-pre-13.c
+      is compiled.  */
+      callfn = CALL_EXPR_FN (ref);
       temp.type = TREE_TYPE (callfn);
       temp.opcode = TREE_CODE (callfn);
       temp.op0 = callfn;
@@ -554,6 +558,7 @@ copy_reference_ops_from_ref (tree ref, VEC(vn_reference_op_s, heap) **result)
 	     a matching type is not necessary and a mismatching type
 	     is always a spurious difference.  */
 	  temp.type = NULL_TREE;
+#if FIXME
 	  /* If this is a reference to a union member, record the union
 	     member size as operand.  Do so only if we are doing
 	     expression insertion (during FRE), as PRE currently gets
@@ -564,14 +569,17 @@ copy_reference_ops_from_ref (tree ref, VEC(vn_reference_op_s, heap) **result)
 	      && integer_zerop (DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref, 1))))
 	    temp.op0 = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (ref, 1)));
 	  else
+#endif
 	    /* Record field as operand.  */
 	    temp.op0 = TREE_OPERAND (ref, 1);
+	    temp.op1 = TREE_OPERAND (ref, 2);	  
 	  break;
 	case ARRAY_RANGE_REF:
 	case ARRAY_REF:
 	  /* Record index as operand.  */
 	  temp.op0 = TREE_OPERAND (ref, 1);
-	  temp.op1 = TREE_OPERAND (ref, 3);
+	  temp.op1 = TREE_OPERAND (ref, 2);
+	  temp.op2 = TREE_OPERAND (ref, 3);
 	  break;
 	case STRING_CST:
 	case INTEGER_CST:
@@ -579,7 +587,6 @@ copy_reference_ops_from_ref (tree ref, VEC(vn_reference_op_s, heap) **result)
 	case VECTOR_CST:
 	case REAL_CST:
 	case CONSTRUCTOR:
-	case VALUE_HANDLE:
 	case VAR_DECL:
 	case PARM_DECL:
 	case CONST_DECL:
@@ -653,7 +660,16 @@ valueize_refs (VEC (vn_reference_op_s, heap) *orig)
     {
       if (vro->opcode == SSA_NAME
 	  || (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME))
-	vro->op0 = SSA_VAL (vro->op0);
+	{
+	  vro->op0 = SSA_VAL (vro->op0);
+	  /* If it transforms from an SSA_NAME to a constant, update
+	     the opcode.  */
+	  if (TREE_CODE (vro->op0) != SSA_NAME && vro->opcode == SSA_NAME)
+	    vro->opcode = TREE_CODE (vro->op0);
+	}
+      /* TODO: Do we want to valueize op2 and op1 of
+	 ARRAY_REF/COMPONENT_REF for Ada */
+      
     }
 
   return orig;
@@ -733,10 +749,11 @@ cont:
 
 /* Lookup a SCCVN reference operation VR in the current hash table.
    Returns the resulting value number if it exists in the hash table,
-   NULL_TREE otherwise.  */
+   NULL_TREE otherwise.  VNRESULT will be filled in with the actual
+   vn_reference_t stored in the hashtable if something is found.  */
 
 static tree
-vn_reference_lookup_1 (vn_reference_t vr)
+vn_reference_lookup_1 (vn_reference_t vr, vn_reference_t *vnresult)
 {
   void **slot;
   hashval_t hash;
@@ -748,25 +765,58 @@ vn_reference_lookup_1 (vn_reference_t vr)
     slot = htab_find_slot_with_hash (valid_info->references, vr,
 				     hash, NO_INSERT);
   if (slot)
-    return ((vn_reference_t)*slot)->result;
-
+    {
+      if (vnresult)
+	*vnresult = (vn_reference_t)*slot;
+      return ((vn_reference_t)*slot)->result;
+    }
+  
   return NULL_TREE;
 }
 
-/* Lookup OP in the current hash table, and return the resulting
-   value number if it exists in the hash table.  Return NULL_TREE if
-   it does not exist in the hash table. */
+
+/* Lookup a reference operation by it's parts, in the current hash table.
+   Returns the resulting value number if it exists in the hash table,
+   NULL_TREE otherwise.  VNRESULT will be filled in with the actual
+   vn_reference_t stored in the hashtable if something is found.  */
 
 tree
-vn_reference_lookup (tree op, VEC (tree, gc) *vuses, bool maywalk)
+vn_reference_lookup_pieces (VEC (tree, gc) *vuses,
+			    VEC (vn_reference_op_s, heap) *operands,
+			    vn_reference_t *vnresult) 
+{
+  struct vn_reference_s vr1;
+  tree result;
+  if (vnresult)
+    *vnresult = NULL;
+  
+  vr1.vuses = valueize_vuses (vuses);
+  vr1.operands = valueize_refs (operands);
+  vr1.hashcode = vn_reference_compute_hash (&vr1);
+  result = vn_reference_lookup_1 (&vr1, vnresult);
+
+  return result;
+}
+
+/* Lookup OP in the current hash table, and return the resulting value
+   number if it exists in the hash table.  Return NULL_TREE if it does
+   not exist in the hash table or if the result field of the structure
+   was NULL..  VNRESULT will be filled in with the vn_reference_t
+   stored in the hashtable if one exists.  */
+
+tree
+vn_reference_lookup (tree op, VEC (tree, gc) *vuses, bool maywalk,
+		     vn_reference_t *vnresult)
 {
   struct vn_reference_s vr1;
   tree result, def_stmt;
+  if (vnresult)
+    *vnresult = NULL;
 
   vr1.vuses = valueize_vuses (vuses);
   vr1.operands = valueize_refs (shared_reference_ops_from_ref (op));
   vr1.hashcode = vn_reference_compute_hash (&vr1);
-  result = vn_reference_lookup_1 (&vr1);
+  result = vn_reference_lookup_1 (&vr1, vnresult);
 
   /* If there is a single defining statement for all virtual uses, we can
      use that, following virtual use-def chains.  */
@@ -786,23 +836,27 @@ vn_reference_lookup (tree op, VEC (tree, gc) *vuses, bool maywalk)
       vdefs_to_vec (def_stmt, &vuses);
       vr1.vuses = valueize_vuses (vuses);
       vr1.hashcode = vn_reference_compute_hash (&vr1);
-      result = vn_reference_lookup_1 (&vr1);
+      result = vn_reference_lookup_1 (&vr1, vnresult);
     }
 
   return result;
 }
 
+
 /* Insert OP into the current hash table with a value number of
-   RESULT.  */
+   RESULT, and return the resulting reference structure we created.  */
 
-void
+vn_reference_t
 vn_reference_insert (tree op, tree result, VEC (tree, gc) *vuses)
 {
   void **slot;
   vn_reference_t vr1;
 
   vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
-
+  if (TREE_CODE (result) == SSA_NAME)
+    vr1->value_id = VN_INFO (result)->value_id;
+  else
+    vr1->value_id = get_or_alloc_constant_value_id (result);
   vr1->vuses = valueize_vuses (vuses);
   vr1->operands = valueize_refs (create_reference_ops_from_ref (op));
   vr1->hashcode = vn_reference_compute_hash (vr1);
@@ -824,11 +878,48 @@ vn_reference_insert (tree op, tree result, VEC (tree, gc) *vuses)
     free_reference (*slot);
 
   *slot = vr1;
+  return vr1;
+}
+
+/* Insert a reference by it's pieces into the current hash table with
+   a value number of RESULT.  Return the resulting reference
+   structure we created.  */
+
+vn_reference_t
+vn_reference_insert_pieces (VEC (tree, gc) *vuses,
+			    VEC (vn_reference_op_s, heap) *operands,
+			    tree result, unsigned int value_id)
+
+{
+  void **slot;
+  vn_reference_t vr1;
+
+  vr1 = (vn_reference_t) pool_alloc (current_info->references_pool);
+  vr1->value_id =  value_id;
+  vr1->vuses = valueize_vuses (vuses);
+  vr1->operands = valueize_refs (operands);
+  vr1->hashcode = vn_reference_compute_hash (vr1);
+  if (result && TREE_CODE (result) == SSA_NAME)
+    result = SSA_VAL (result);
+  vr1->result = result;
+
+  slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode,
+				   INSERT);
+  
+  /* At this point we should have all the things inserted that we have
+  seen before, and we should never try inserting something that
+  already exists.  */
+  gcc_assert (!*slot);
+  if (*slot)
+    free_reference (*slot);
+
+  *slot = vr1;
+  return vr1;
 }
 
 /* Compute and return the hash value for nary operation VBO1.  */
 
-static inline hashval_t
+inline hashval_t
 vn_nary_op_compute_hash (const vn_nary_op_t vno1)
 {
   hashval_t hash = 0;
@@ -865,7 +956,7 @@ vn_nary_op_hash (const void *p1)
 /* Compare nary operations P1 and P2 and return true if they are
    equivalent.  */
 
-static int
+int
 vn_nary_op_eq (const void *p1, const void *p2)
 {
   const_vn_nary_op_t const vno1 = (const_vn_nary_op_t) p1;
@@ -883,17 +974,56 @@ vn_nary_op_eq (const void *p1, const void *p2)
   return true;
 }
 
-/* Lookup OP in the current hash table, and return the resulting
-   value number if it exists in the hash table.  Return NULL_TREE if
-   it does not exist in the hash table. */
+/* Lookup a n-ary operation by its pieces and return the resulting value
+   number if it exists in the hash table.  Return NULL_TREE if it does
+   not exist in the hash table or if the result field of the operation
+   is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
+   if it exists.  */
 
 tree
-vn_nary_op_lookup (tree op)
+vn_nary_op_lookup_pieces (unsigned int length, enum tree_code code,
+			  tree type, tree op0, tree op1, tree op2,
+			  tree op3, vn_nary_op_t *vnresult) 
+{
+  void **slot;
+  struct vn_nary_op_s vno1;
+  if (vnresult)
+    *vnresult = NULL;
+  vno1.opcode = code;
+  vno1.length = length;
+  vno1.type = type;
+  vno1.op[0] = op0;
+  vno1.op[1] = op1;
+  vno1.op[2] = op2;
+  vno1.op[3] = op3;
+  vno1.hashcode = vn_nary_op_compute_hash (&vno1);
+  slot = htab_find_slot_with_hash (current_info->nary, &vno1, vno1.hashcode,
+				   NO_INSERT);
+  if (!slot && current_info == optimistic_info)
+    slot = htab_find_slot_with_hash (valid_info->nary, &vno1, vno1.hashcode,
+				     NO_INSERT);
+  if (!slot)
+    return NULL_TREE;
+  if (vnresult)
+    *vnresult = (vn_nary_op_t)*slot;
+  return ((vn_nary_op_t)*slot)->result;
+}
+
+/* Lookup OP in the current hash table, and return the resulting value
+   number if it exists in the hash table.  Return NULL_TREE if it does
+   not exist in the hash table or if the result field of the operation
+   is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable
+   if it exists.  */
+
+tree
+vn_nary_op_lookup (tree op, vn_nary_op_t *vnresult)
 {
   void **slot;
   struct vn_nary_op_s vno1;
   unsigned i;
 
+  if (vnresult)
+    *vnresult = NULL;
   vno1.opcode = TREE_CODE (op);
   vno1.length = TREE_CODE_LENGTH (TREE_CODE (op));
   vno1.type = TREE_TYPE (op);
@@ -907,13 +1037,56 @@ vn_nary_op_lookup (tree op)
 				     NO_INSERT);
   if (!slot)
     return NULL_TREE;
+  if (vnresult)
+    *vnresult = (vn_nary_op_t)*slot;
   return ((vn_nary_op_t)*slot)->result;
 }
 
+/* Insert a n-ary operation into the current hash table using it's
+   pieces.  Return the vn_nary_op_t structure we created and put in
+   the hashtable.  */
+
+vn_nary_op_t
+vn_nary_op_insert_pieces (unsigned int length, enum tree_code code,
+			  tree type, tree op0,
+			  tree op1, tree op2, tree op3,
+			  tree result,
+			  unsigned int value_id) 
+{
+  void **slot;
+  vn_nary_op_t vno1;
+
+  vno1 = (vn_nary_op_t) obstack_alloc (&current_info->nary_obstack,
+				       (sizeof (struct vn_nary_op_s)
+					- sizeof (tree) * (4 - length)));
+  vno1->value_id = value_id;
+  vno1->opcode = code;
+  vno1->length = length;
+  vno1->type = type;
+  if (length >= 1)
+    vno1->op[0] = op0;
+  if (length >= 2)
+    vno1->op[1] = op1;
+  if (length >= 3)
+    vno1->op[2] = op2;
+  if (length >= 4)
+    vno1->op[3] = op3;
+  vno1->result = result;
+  vno1->hashcode = vn_nary_op_compute_hash (vno1);
+  slot = htab_find_slot_with_hash (current_info->nary, vno1, vno1->hashcode,
+				   INSERT);
+  gcc_assert (!*slot);
+
+  *slot = vno1;
+  return vno1;
+  
+}
+
 /* Insert OP into the current hash table with a value number of
-   RESULT.  */
+   RESULT.  Return the vn_nary_op_t structure we created and put in
+   the hashtable.  */
 
-void
+vn_nary_op_t
 vn_nary_op_insert (tree op, tree result)
 {
   unsigned length = TREE_CODE_LENGTH (TREE_CODE (op));
@@ -924,6 +1097,7 @@ vn_nary_op_insert (tree op, tree result)
   vno1 = (vn_nary_op_t) obstack_alloc (&current_info->nary_obstack,
 			(sizeof (struct vn_nary_op_s)
 			 - sizeof (tree) * (4 - length)));
+  vno1->value_id = VN_INFO (result)->value_id;
   vno1->opcode = TREE_CODE (op);
   vno1->length = length;
   vno1->type = TREE_TYPE (op);
@@ -936,6 +1110,7 @@ vn_nary_op_insert (tree op, tree result)
   gcc_assert (!*slot);
 
   *slot = vno1;
+  return vno1;
 }
 
 /* Compute a hashcode for PHI operation VP1 and return it.  */
@@ -1034,7 +1209,7 @@ vn_phi_lookup (tree phi)
 /* Insert PHI into the current hash table with a value number of
    RESULT.  */
 
-static void
+static vn_phi_t
 vn_phi_insert (tree phi, tree result)
 {
   void **slot;
@@ -1049,6 +1224,7 @@ vn_phi_insert (tree phi, tree result)
       def = TREE_CODE (def) == SSA_NAME ? SSA_VAL (def) : def;
       VEC_safe_push (tree, heap, args, def);
     }
+  vp1->value_id = VN_INFO (result)->value_id;
   vp1->phiargs = args;
   vp1->block = bb_for_stmt (phi);
   vp1->result = result;
@@ -1060,6 +1236,7 @@ vn_phi_insert (tree phi, tree result)
   /* Because we iterate over phi operations more than once, it's
      possible the slot might already exist here, hence no assert.*/
   *slot = vp1;
+  return vp1;
 }
 
 
@@ -1168,7 +1345,7 @@ static bool
 visit_unary_op (tree lhs, tree op)
 {
   bool changed = false;
-  tree result = vn_nary_op_lookup (op);
+  tree result = vn_nary_op_lookup (op, NULL);
 
   if (result)
     {
@@ -1190,7 +1367,7 @@ static bool
 visit_binary_op (tree lhs, tree op)
 {
   bool changed = false;
-  tree result = vn_nary_op_lookup (op);
+  tree result = vn_nary_op_lookup (op, NULL);
 
   if (result)
     {
@@ -1212,7 +1389,8 @@ static bool
 visit_reference_op_load (tree lhs, tree op, tree stmt)
 {
   bool changed = false;
-  tree result = vn_reference_lookup (op, shared_vuses_from_stmt (stmt), true);
+  tree result = vn_reference_lookup (op, shared_vuses_from_stmt (stmt), true,
+				     NULL);
 
   /* We handle type-punning through unions by value-numbering based
      on offset and size of the access.  Be prepared to handle a
@@ -1236,7 +1414,7 @@ visit_reference_op_load (tree lhs, tree op, tree stmt)
       result = val;
       if (!is_gimple_min_invariant (val)
 	  && TREE_CODE (val) != SSA_NAME)
-	result = vn_nary_op_lookup (val);
+	result = vn_nary_op_lookup (val, NULL);
       /* If the expression is not yet available, value-number lhs to
 	 a new SSA_NAME we create.  */
       if (!result && may_insert)
@@ -1319,7 +1497,8 @@ visit_reference_op_store (tree lhs, tree op, tree stmt)
      Otherwise, the vdefs for the store are used when inserting into
      the table, since the store generates a new memory state.  */
 
-  result = vn_reference_lookup (lhs, shared_vuses_from_stmt (stmt), false);
+  result = vn_reference_lookup (lhs, shared_vuses_from_stmt (stmt), false,
+				NULL);
 
   if (result)
     {
@@ -2146,12 +2325,18 @@ init_scc_vn (void)
 
   calculate_dominance_info (CDI_DOMINATORS);
   sccstack = NULL;
+  constant_to_value_id = htab_create (23, vn_constant_hash, vn_constant_eq,
+				  free);
+  
+  constant_value_ids = BITMAP_ALLOC (NULL);
+  
   next_dfs_num = 1;
-
+  next_value_id = 1;
+  
   vn_ssa_aux_table = VEC_alloc (vn_ssa_aux_t, heap, num_ssa_names + 1);
   /* VEC_alloc doesn't actually grow it to the right size, it just
      preallocates the space to do so.  */
-  VEC_safe_grow (vn_ssa_aux_t, heap, vn_ssa_aux_table, num_ssa_names + 1);
+  VEC_safe_grow_cleared (vn_ssa_aux_t, heap, vn_ssa_aux_table, num_ssa_names + 1);
   gcc_obstack_init (&vn_ssa_aux_obstack);
 
   shared_lookup_phiargs = NULL;
@@ -2180,6 +2365,7 @@ init_scc_vn (void)
 	{
 	  VN_INFO_GET (name)->valnum = VN_TOP;
 	  VN_INFO (name)->expr = name;
+	  VN_INFO (name)->value_id = 0;
 	}
     }
 
@@ -2206,6 +2392,8 @@ free_scc_vn (void)
 {
   size_t i;
 
+  htab_delete (constant_to_value_id);
+  BITMAP_FREE (constant_value_ids);
   VEC_free (tree, heap, shared_lookup_phiargs);
   VEC_free (tree, gc, shared_lookup_vops);
   VEC_free (vn_reference_op_s, heap, shared_lookup_references);
@@ -2215,8 +2403,7 @@ free_scc_vn (void)
     {
       tree name = ssa_name (i);
       if (name
-	  && SSA_NAME_VALUE (name)
-	  && TREE_CODE (SSA_NAME_VALUE (name)) == VALUE_HANDLE)
+	  && SSA_NAME_VALUE (name))
 	SSA_NAME_VALUE (name) = NULL;
       if (name
 	  && VN_INFO (name)->needs_insertion)
@@ -2237,6 +2424,91 @@ free_scc_vn (void)
     }
 }
 
+/* Set the value ids in the valid/optimistic hash tables.  */
+
+static void
+set_hashtable_value_ids (void)
+{
+  htab_iterator hi;
+  vn_nary_op_t vno;
+  vn_reference_t vr;
+  vn_phi_t vp;
+  
+  /* Now set the value ids of the things we had put in the hash
+     table.  */
+
+  FOR_EACH_HTAB_ELEMENT (valid_info->nary,
+			 vno, vn_nary_op_t, hi) 
+    {
+      if (vno->result)
+	{
+	  if (TREE_CODE (vno->result) == SSA_NAME)
+	    vno->value_id = VN_INFO (vno->result)->value_id;
+	  else if (is_gimple_min_invariant (vno->result))
+	    vno->value_id = get_or_alloc_constant_value_id (vno->result);
+	}
+    }
+
+  FOR_EACH_HTAB_ELEMENT (optimistic_info->nary,
+			 vno, vn_nary_op_t, hi) 
+    {
+      if (vno->result)
+	{
+	  if (TREE_CODE (vno->result) == SSA_NAME)
+	    vno->value_id = VN_INFO (vno->result)->value_id;
+	  else if (is_gimple_min_invariant (vno->result))
+	    vno->value_id = get_or_alloc_constant_value_id (vno->result);
+	}
+    }
+
+  FOR_EACH_HTAB_ELEMENT (valid_info->phis,
+			 vp, vn_phi_t, hi) 
+    {
+      if (vp->result)
+	{
+	  if (TREE_CODE (vp->result) == SSA_NAME)
+	    vp->value_id = VN_INFO (vp->result)->value_id;
+	  else if (is_gimple_min_invariant (vp->result))
+	    vp->value_id = get_or_alloc_constant_value_id (vp->result);
+	}
+    }
+  FOR_EACH_HTAB_ELEMENT (optimistic_info->phis,
+			 vp, vn_phi_t, hi) 
+    {
+      if (vp->result)
+	{
+	  if (TREE_CODE (vp->result) == SSA_NAME)
+	    vp->value_id = VN_INFO (vp->result)->value_id;
+	  else if (is_gimple_min_invariant (vp->result))
+	    vp->value_id = get_or_alloc_constant_value_id (vp->result);
+	}
+    }
+
+
+  FOR_EACH_HTAB_ELEMENT (valid_info->references,
+			 vr, vn_reference_t, hi) 
+    {
+      if (vr->result)
+	{
+	  if (TREE_CODE (vr->result) == SSA_NAME)
+	    vr->value_id = VN_INFO (vr->result)->value_id;
+	  else if (is_gimple_min_invariant (vr->result))
+	    vr->value_id = get_or_alloc_constant_value_id (vr->result);
+	}
+    }
+  FOR_EACH_HTAB_ELEMENT (optimistic_info->references,
+			 vr, vn_reference_t, hi) 
+    {
+      if (vr->result)
+	{
+	  if (TREE_CODE (vr->result) == SSA_NAME)
+	    vr->value_id = VN_INFO (vr->result)->value_id;
+	  else if (is_gimple_min_invariant (vr->result))
+	    vr->value_id = get_or_alloc_constant_value_id (vr->result);
+	}
+    }
+}
+
 /* Do SCCVN.  Returns true if it finished, false if we bailed out
    due to resource constraints.  */
 
@@ -2245,7 +2517,8 @@ run_scc_vn (bool may_insert_arg)
 {
   size_t i;
   tree param;
-
+  bool changed = true;
+  
   may_insert = may_insert_arg;
 
   init_scc_vn ();
@@ -2276,6 +2549,45 @@ run_scc_vn (bool may_insert_arg)
 	  }
     }
 
+  /* Initialize the value ids.  */
+      
+  for (i = 1; i < num_ssa_names; ++i)
+    {
+      tree name = ssa_name (i);
+      vn_ssa_aux_t info;
+      if (!name)
+	continue;
+      info = VN_INFO (name);
+      if (info->valnum == name)
+	info->value_id = get_next_value_id ();
+      else if (is_gimple_min_invariant (info->valnum))
+	info->value_id = get_or_alloc_constant_value_id (info->valnum);
+    }
+  
+  /* Propagate until they stop changing.  */
+  while (changed)
+    {
+      changed = false;
+      for (i = 1; i < num_ssa_names; ++i)
+	{
+	  tree name = ssa_name (i);
+	  vn_ssa_aux_t info;
+	  if (!name)
+	    continue;
+	  info = VN_INFO (name);
+	  if (TREE_CODE (info->valnum) == SSA_NAME
+	      && info->valnum != name
+	      && TREE_CODE (info->valnum) == SSA_NAME
+	      && info->value_id != VN_INFO (info->valnum)->value_id)
+	    {
+	      changed = true;
+	      info->value_id = VN_INFO (info->valnum)->value_id;
+	    }
+	}
+    }
+  
+  set_hashtable_value_ids ();
+  
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
       fprintf (dump_file, "Value numbers:\n");
@@ -2300,3 +2612,83 @@ run_scc_vn (bool may_insert_arg)
   may_insert = false;
   return true;
 }
+
+/* Return the maximum value id we have ever seen.  */
+
+unsigned int
+get_max_value_id (void) 
+{
+  return next_value_id;
+}
+
+/* Return the next unique value id.  */
+
+unsigned int
+get_next_value_id (void)
+{
+  return next_value_id++;
+}
+
+
+/* Compare two expressions E1 and E2 and return true if they are
+   equal.  */
+
+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_LIST && TREE_CODE (e2) == TREE_LIST)
+    {
+      tree lop1 = e1;
+      tree lop2 = e2;
+      for (lop1 = e1, lop2 = e2;
+	   lop1 || lop2;
+	   lop1 = TREE_CHAIN (lop1), lop2 = TREE_CHAIN (lop2))
+	{
+	  if (!lop1 || !lop2)
+	    return false;
+	  if (!expressions_equal_p (TREE_VALUE (lop1), TREE_VALUE (lop2)))
+	    return false;
+	}
+      return true;
+
+    }
+  else if (TREE_CODE (e1) == TREE_CODE (e2)
+	   && operand_equal_p (e1, e2, OEP_PURE_SAME))
+    return true;
+
+  return false;
+}
+
+/* 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),
+	   operand_build_cmp);
+}
+
+/* Sort the VUSE array so that we can do equality comparisons
+   quicker on two vuse vecs.  */
+
+void
+sort_vuses_heap (VEC (tree,heap) *vuses)
+{
+  if (VEC_length (tree, vuses) > 1)
+    qsort (VEC_address (tree, vuses),
+	   VEC_length (tree, vuses),
+	   sizeof (tree),
+	   operand_build_cmp);
+}