Index: gcc/gimple.c
===================================================================
--- gcc/gimple.c	(revision 162371)
+++ gcc/gimple.c	(working copy)
@@ -3174,6 +3174,9 @@ struct type_pair_d
 };
 typedef struct type_pair_d *type_pair_t;
 
+DEF_VEC_P(type_pair_t);
+DEF_VEC_ALLOC_P(type_pair_t,heap);
+
 /* Return a hash value for the type pair pointed-to by P.  */
 
 static hashval_t
@@ -3231,6 +3234,21 @@ lookup_type_pair (tree t1, tree t2, htab
   return p;
 }
 
+/* Per pointer state for the SCC finding.  The on_sccstack flag
+   is not strictly required, it is true when there is no hash value
+   recorded for the type and false otherwise.  But querying that
+   is slower.  */
+
+struct sccs
+{
+  unsigned int dfsnum;
+  unsigned int low;
+  bool on_sccstack;
+  hashval_t hash;
+};
+
+static unsigned int next_dfs_num;
+static unsigned int gtc_next_dfs_num;
 
 /* Return true if T1 and T2 have the same name.  If FOR_COMPLETION_P is
    true then if any type has no name return false, otherwise return
@@ -3344,13 +3362,20 @@ gimple_compatible_complete_and_incomplet
   return false;
 }
 
-/* Return 1 iff T1 and T2 are structurally identical.
-   Otherwise, return 0.  */
+static bool
+gimple_types_compatible_p_1 (tree, tree, bool, VEC(type_pair_t, heap) **,
+			     struct pointer_map_t *, struct obstack *);
 
-bool
-gimple_types_compatible_p (tree t1, tree t2, bool for_merging_p)
+static bool
+gtc_visit (tree t1, tree t2, bool for_merging_p,
+	   struct sccs *state,
+	   VEC(type_pair_t, heap) **sccstack,
+	   struct pointer_map_t *sccstate,
+	   struct obstack *sccstate_obstack)
 {
-  type_pair_t p = NULL;
+  struct sccs *cstate = NULL;
+  type_pair_t p;
+  void **slot;
 
   /* Check first for the obvious case of pointer identity.  */
   if (t1 == t2)
@@ -3404,12 +3429,6 @@ gimple_types_compatible_p (tree t1, tree
 	  || FIXED_POINT_TYPE_P (t1))
 	return 1;
 
-      /* Perform cheap tail-recursion for vector and complex types.  */
-      if (TREE_CODE (t1) == VECTOR_TYPE
-	  || TREE_CODE (t1) == COMPLEX_TYPE)
-	return gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2),
-					  for_merging_p);
-
       /* For integral types fall thru to more complex checks.  */
     }
 
@@ -3427,8 +3446,7 @@ gimple_types_compatible_p (tree t1, tree
   if (gimple_type_hash (t1) != gimple_type_hash (t2))
     return 0;
 
-  /* If we've visited this type pair before (in the case of aggregates
-     with self-referential types), and we made a decision, return it.  */
+  /* Allocate a new cache entry for this comparison.  */
   p = lookup_type_pair (t1, t2,
 			for_merging_p ? &gtc_visited : &gtc_visited2,
 			for_merging_p ? &gtc_ob : &gtc_ob2);
@@ -3438,17 +3456,60 @@ gimple_types_compatible_p (tree t1, tree
 	 same, return the cached result.  */
       return p->same_p == 1;
     }
-  else if (p->same_p == -1)
+
+  gcc_assert (p->same_p == -2);
+
+  if ((slot = pointer_map_contains (sccstate, p)) != NULL)
+    cstate = (struct sccs *)*slot;
+  if (!cstate)
     {
-      /* We are currently comparing this pair of types, assume
-	 that they are the same and let the caller decide.  */
-      return 1;
+      int res;
+      /* Not yet visited.  DFS recurse.  */
+      res = gimple_types_compatible_p_1 (t1, t2, for_merging_p,
+					 sccstack, sccstate, sccstate_obstack);
+      if (!cstate)
+	cstate = (struct sccs *)* pointer_map_contains (sccstate, p);
+      state->low = MIN (state->low, cstate->low);
+      /* If the type is no longer on the SCC stack and thus is not part
+	 of the parents SCC mix in its hash value.  Otherwise we will
+	 ignore the type for hashing purposes and return the unaltered
+	 hash value.  */
+      if (!cstate->on_sccstack)
+	return res;
     }
+  if (cstate->dfsnum < state->dfsnum
+      && cstate->on_sccstack)
+    state->low = MIN (cstate->dfsnum, state->low);
+
+  /* We are part of our parents SCC, skip this entry and return true.  */
+  return 1;
+}
+
+/* Return 1 iff T1 and T2 are structurally identical.
+   Otherwise, return 0.  */
+
+static bool
+gimple_types_compatible_p_1 (tree t1, tree t2, bool for_merging_p,
+			     VEC(type_pair_t, heap) **sccstack,
+			     struct pointer_map_t *sccstate,
+			     struct obstack *sccstate_obstack)
+{
+  type_pair_t p;
+  struct sccs *state;
 
+  /* Allocate a new cache entry for this comparison.  */
+  p = lookup_type_pair (t1, t2,
+			for_merging_p ? &gtc_visited : &gtc_visited2,
+			for_merging_p ? &gtc_ob : &gtc_ob2);
   gcc_assert (p->same_p == -2);
 
-  /* Mark the (T1, T2) comparison in progress.  */
-  p->same_p = -1;
+  state = XOBNEW (sccstate_obstack, struct sccs);
+  *pointer_map_insert (sccstate, p) = state;
+
+  VEC_safe_push (type_pair_t, heap, *sccstack, p);
+  state->dfsnum = gtc_next_dfs_num++;
+  state->low = state->dfsnum;
+  state->on_sccstack = true;
 
   /* If their attributes are not the same they can't be the same type.  */
   if (!attribute_list_equal (TYPE_ATTRIBUTES (t1), TYPE_ATTRIBUTES (t2)))
@@ -3457,11 +3518,18 @@ gimple_types_compatible_p (tree t1, tree
   /* Do type-specific comparisons.  */
   switch (TREE_CODE (t1))
     {
+    case VECTOR_TYPE:
+    case COMPLEX_TYPE:
+      if (!gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2), for_merging_p,
+		      state, sccstack, sccstate, sccstate_obstack))
+	goto different_types;
+      goto same_types;
+
     case ARRAY_TYPE:
       /* Array types are the same if the element types are the same and
 	 the number of elements are the same.  */
-      if (!gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2),
-				      for_merging_p)
+      if (!gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2), for_merging_p,
+		      state, sccstack, sccstate, sccstate_obstack)
 	  || TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2)
 	  || TYPE_NONALIASED_COMPONENT (t1) != TYPE_NONALIASED_COMPONENT (t2))
 	goto different_types;
@@ -3509,8 +3577,9 @@ gimple_types_compatible_p (tree t1, tree
 
     case METHOD_TYPE:
       /* Method types should belong to the same class.  */
-      if (!gimple_types_compatible_p (TYPE_METHOD_BASETYPE (t1),
-				      TYPE_METHOD_BASETYPE (t2), for_merging_p))
+      if (!gtc_visit (TYPE_METHOD_BASETYPE (t1), TYPE_METHOD_BASETYPE (t2),
+		      for_merging_p,
+		      state, sccstack, sccstate, sccstate_obstack))
 	goto different_types;
 
       /* Fallthru  */
@@ -3521,8 +3590,8 @@ gimple_types_compatible_p (tree t1, tree
       if ((for_merging_p
 	   || !gimple_compatible_complete_and_incomplete_subtype_p
 	         (TREE_TYPE (t1), TREE_TYPE (t2)))
-	  && !gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2),
-					 for_merging_p))
+	  && !gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2), for_merging_p,
+			 state, sccstack, sccstate, sccstate_obstack))
 	goto different_types;
 
       if (!targetm.comp_type_attributes (t1, t2))
@@ -3541,9 +3610,9 @@ gimple_types_compatible_p (tree t1, tree
 	      if ((for_merging_p
 		   || !gimple_compatible_complete_and_incomplete_subtype_p
 		         (TREE_VALUE (parms1), TREE_VALUE (parms2)))
-		  && !gimple_types_compatible_p (TREE_VALUE (parms1),
-						 TREE_VALUE (parms2),
-						 for_merging_p))
+		  && !gtc_visit (TREE_VALUE (parms1), TREE_VALUE (parms2),
+				 for_merging_p,
+				 state, sccstack, sccstate, sccstate_obstack))
 		goto different_types;
 	    }
 
@@ -3555,11 +3624,11 @@ gimple_types_compatible_p (tree t1, tree
 
     case OFFSET_TYPE:
       {
-	if (!gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2),
-					for_merging_p)
-	    || !gimple_types_compatible_p (TYPE_OFFSET_BASETYPE (t1),
-					   TYPE_OFFSET_BASETYPE (t2),
-					   for_merging_p))
+	if (!gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2), for_merging_p,
+			state, sccstack, sccstate, sccstate_obstack)
+	    || !gtc_visit (TYPE_OFFSET_BASETYPE (t1),
+			   TYPE_OFFSET_BASETYPE (t2), for_merging_p,
+			   state, sccstack, sccstate, sccstate_obstack))
 	  goto different_types;
 
 	goto same_types;
@@ -3582,8 +3651,8 @@ gimple_types_compatible_p (tree t1, tree
 
 	/* Otherwise, pointer and reference types are the same if the
 	   pointed-to types are the same.  */
-	if (gimple_types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2),
-				       for_merging_p))
+	if (gtc_visit (TREE_TYPE (t1), TREE_TYPE (t2), for_merging_p,
+		       state, sccstack, sccstate, sccstate_obstack))
 	  goto same_types;
 
 	goto different_types;
@@ -3678,8 +3747,8 @@ gimple_types_compatible_p (tree t1, tree
 	    if (DECL_NAME (f1) != DECL_NAME (f2)
 		|| DECL_NONADDRESSABLE_P (f1) != DECL_NONADDRESSABLE_P (f2)
 		|| !gimple_compare_field_offset (f1, f2)
-		|| !gimple_types_compatible_p (TREE_TYPE (f1),
-					       TREE_TYPE (f2), for_merging_p))
+		|| !gtc_visit (TREE_TYPE (f1), TREE_TYPE (f2), for_merging_p,
+			       state, sccstack, sccstate, sccstate_obstack))
 	      goto different_types;
 	  }
 
@@ -3697,32 +3766,139 @@ gimple_types_compatible_p (tree t1, tree
 
   /* Common exit path for types that are not compatible.  */
 different_types:
-  p->same_p = 0;
-  return 0;
+  state->hash/*same_p*/ = 0;
+  goto pop;
 
   /* Common exit path for types that are compatible.  */
 same_types:
-  p->same_p = 1;
-  return 1;
+  state->hash/*same_p*/ = 1;
+  goto pop;
+
+pop:
+  if (state->low == state->dfsnum)
+    {
+      type_pair_t x;
+
+      /* Pop off the SCC and set its cache values.  */
+      do
+	{
+	  struct sccs *cstate;
+	  x = VEC_pop (type_pair_t, *sccstack);
+	  cstate = (struct sccs *)*pointer_map_contains (sccstate, x);
+	  cstate->on_sccstack = false;
+	  x->same_p = cstate->hash/*same_p*/;
+	}
+      while (x != p);
+    }
+
+  return state->hash/*same_p*/;
 }
 
+bool
+gimple_types_compatible_p (tree t1, tree t2, bool for_merging_p)
+{
+  VEC(type_pair_t, heap) *sccstack = NULL;
+  struct pointer_map_t *sccstate;
+  struct obstack sccstate_obstack;
+  type_pair_t p = NULL;
+  bool res;
 
+  /* Before starting to set up the SCC machinery handle simple cases.  */
 
+  /* Check first for the obvious case of pointer identity.  */
+  if (t1 == t2)
+    return 1;
 
-/* Per pointer state for the SCC finding.  The on_sccstack flag
-   is not strictly required, it is true when there is no hash value
-   recorded for the type and false otherwise.  But querying that
-   is slower.  */
+  /* Check that we have two types to compare.  */
+  if (t1 == NULL_TREE || t2 == NULL_TREE)
+    return 0;
 
-struct sccs
-{
-  unsigned int dfsnum;
-  unsigned int low;
-  bool on_sccstack;
-  hashval_t hash;
-};
+  /* If the types have been previously registered and found equal
+     they still are.  */
+  if (TYPE_CANONICAL (t1)
+      && TYPE_CANONICAL (t1) == TYPE_CANONICAL (t2))
+    return 1;
+
+  /* Can't be the same type if the types don't have the same code.  */
+  if (TREE_CODE (t1) != TREE_CODE (t2))
+    return 0;
+
+  /* Can't be the same type if they have different CV qualifiers.  */
+  if (TYPE_QUALS (t1) != TYPE_QUALS (t2))
+    return 0;
+
+  /* Void types are always the same.  */
+  if (TREE_CODE (t1) == VOID_TYPE)
+    return 1;
+
+  /* Do some simple checks before doing three hashtable queries.  */
+  if (INTEGRAL_TYPE_P (t1)
+      || SCALAR_FLOAT_TYPE_P (t1)
+      || FIXED_POINT_TYPE_P (t1)
+      || TREE_CODE (t1) == VECTOR_TYPE
+      || TREE_CODE (t1) == COMPLEX_TYPE
+      || TREE_CODE (t1) == OFFSET_TYPE)
+    {
+      /* Can't be the same type if they have different alignment,
+	 sign, precision or mode.  */
+      if (TYPE_ALIGN (t1) != TYPE_ALIGN (t2)
+	  || TYPE_PRECISION (t1) != TYPE_PRECISION (t2)
+	  || TYPE_MODE (t1) != TYPE_MODE (t2)
+	  || TYPE_UNSIGNED (t1) != TYPE_UNSIGNED (t2))
+	return 0;
+
+      if (TREE_CODE (t1) == INTEGER_TYPE
+	  && (TYPE_IS_SIZETYPE (t1) != TYPE_IS_SIZETYPE (t2)
+	      || TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2)))
+	return 0;
+
+      /* That's all we need to check for float and fixed-point types.  */
+      if (SCALAR_FLOAT_TYPE_P (t1)
+	  || FIXED_POINT_TYPE_P (t1))
+	return 1;
+
+      /* For integral types fall thru to more complex checks.  */
+    }
+
+  else if (AGGREGATE_TYPE_P (t1) || POINTER_TYPE_P (t1))
+    {
+      /* Can't be the same type if they have different alignment or mode.  */
+      if (TYPE_ALIGN (t1) != TYPE_ALIGN (t2)
+	  || TYPE_MODE (t1) != TYPE_MODE (t2))
+	return 0;
+    }
+
+  /* If the hash values of t1 and t2 are different the types can't
+     possibly be the same.  This helps keeping the type-pair hashtable
+     small, only tracking comparisons for hash collisions.  */
+  if (gimple_type_hash (t1) != gimple_type_hash (t2))
+    return 0;
+
+  /* If we've visited this type pair before (in the case of aggregates
+     with self-referential types), and we made a decision, return it.  */
+  p = lookup_type_pair (t1, t2,
+			for_merging_p ? &gtc_visited : &gtc_visited2,
+			for_merging_p ? &gtc_ob : &gtc_ob2);
+  if (p->same_p == 0 || p->same_p == 1)
+    {
+      /* We have already decided whether T1 and T2 are the
+	 same, return the cached result.  */
+      return p->same_p == 1;
+    }
+
+  /* Now set up the SCC machinery for the comparison.  */
+  gtc_next_dfs_num = 1;
+  sccstate = pointer_map_create ();
+  gcc_obstack_init (&sccstate_obstack);
+  res = gimple_types_compatible_p_1 (t1, t2, for_merging_p,
+				     &sccstack, sccstate, &sccstate_obstack);
+  VEC_free (type_pair_t, heap, sccstack);
+  pointer_map_destroy (sccstate);
+  obstack_free (&sccstate_obstack, NULL);
+
+  return res;
+}
 
-static unsigned int next_dfs_num;
 
 static hashval_t
 iterative_hash_gimple_type (tree, hashval_t, VEC(tree, heap) **,
