Re: Minor type merging optimization

[Richard Guenther <rguenther at suse dot de>]

On Mon, 9 May 2011, Jan Hubicka wrote:

> > On Fri, May 6, 2011 at 10:24 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
> > > Hi,
> > > while looking at type merging code I noticed that type pairs can be managed
> > > to be ordered by their UIDs. ?This save some of hashing overhead in one of
> > > most intensively querried hashes.
> > >
> > > Also gimple_lookup_type_leader is hot function that is better to be inlined.
> > >
> > > I also wonder, why unionfind algorithm is not used here to maintain the
> > > positive answers?
> > 
> > Can you elaborate?
> 
> Well, just use unionfind to record the equivalences found and then
> prior checking the hashtable ask it for equivalence class representative.
> Either you will already find that the pairs are equivalent (in faster
> way than by querying the hash) or you at least save the memory by caching
> the negative andwers only across the equivalence classes.
> 
> I hacked quick unionfind two days ago, but the stopper is that the cache
> is temporarily caching equilvaences in SCC regions.  You mentioned it is no
> longer neccesary, so perhaps if you send me patch to remove this, I can give
> a try to this idea.

I haven't yet tested this (apart from with running the LTO testsuite),
but I'm going to give the following bootstrap & SPEC2k6 LTO build tests.

Richard.

2011-05-09  Richard Guenther  <rguenther@suse.de>

	* gimple.c (gtc_visited, gtc_ob, struct type_pair_d, type_pair_t,
	type_pair_hash, type_pair_eq, lookup_type_pair): Remove.
	(gtc_visit): Adjust.  Use the first type to identify the
	part of the SCC we are visiting.
	(gimple_types_compatible_p_1): Likewise.
	(gimple_types_compatible_p): Likewise.
	(print_gimple_types_stats): Do not print comparison cache stats.
	(free_gimple_type_tables): Do not free the comparison cache.

Index: gcc/gimple.c
===================================================================
--- gcc/gimple.c	(revision 173560)
+++ gcc/gimple.c	(working copy)
@@ -50,11 +50,6 @@ static GTY((if_marked ("tree_int_map_mar
 static GTY((if_marked ("tree_int_map_marked_p"), param_is (struct tree_int_map)))
   htab_t canonical_type_hash_cache;
 
-/* Global type comparison cache.  This is by TYPE_UID for space efficiency
-   and thus cannot use and does not need GC.  */
-static htab_t gtc_visited;
-static struct obstack gtc_ob;
-
 /* All the tuples have their operand vector (if present) at the very bottom
    of the structure.  Therefore, the offset required to find the
    operands vector the size of the structure minus the size of the 1
@@ -3210,92 +3205,6 @@ gimple_call_copy_skip_args (gimple stmt,
 
 static hashval_t gimple_type_hash_1 (const void *, enum gtc_mode);
 
-/* Structure used to maintain a cache of some type pairs compared by
-   gimple_types_compatible_p when comparing aggregate types.  There are
-   three possible values for SAME_P:
-
-   	-2: The pair (T1, T2) has just been inserted in the table.
-	 0: T1 and T2 are different types.
-	 1: T1 and T2 are the same type.
-
-   The two elements in the SAME_P array are indexed by the comparison
-   mode gtc_mode.  */
-
-struct type_pair_d
-{
-  unsigned int uid1;
-  unsigned int uid2;
-  signed char same_p[2];
-};
-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
-type_pair_hash (const void *p)
-{
-  const struct type_pair_d *pair = (const struct type_pair_d *) p;
-  hashval_t val1 = pair->uid1;
-  hashval_t val2 = pair->uid2;
-  return iterative_hash_hashval_t (val1, val2);
-}
-
-/* Compare two type pairs pointed-to by P1 and P2.  */
-
-static int
-type_pair_eq (const void *p1, const void *p2)
-{
-  const struct type_pair_d *pair1 = (const struct type_pair_d *) p1;
-  const struct type_pair_d *pair2 = (const struct type_pair_d *) p2;
-  return (pair1->uid1 == pair2->uid1 && pair1->uid2 == pair2->uid2);
-}
-
-/* Lookup the pair of types T1 and T2 in *VISITED_P.  Insert a new
-   entry if none existed.  */
-
-static type_pair_t
-lookup_type_pair (tree t1, tree t2, htab_t *visited_p, struct obstack *ob_p)
-{
-  struct type_pair_d pair;
-  type_pair_t p;
-  void **slot;
-
-  if (*visited_p == NULL)
-    {
-      *visited_p = htab_create (251, type_pair_hash, type_pair_eq, NULL);
-      gcc_obstack_init (ob_p);
-    }
-
-  if (TYPE_UID (t1) < TYPE_UID (t2))
-    {
-      pair.uid1 = TYPE_UID (t1);
-      pair.uid2 = TYPE_UID (t2);
-    }
-  else
-    {
-      pair.uid1 = TYPE_UID (t2);
-      pair.uid2 = TYPE_UID (t1);
-    }
-  slot = htab_find_slot (*visited_p, &pair, INSERT);
-
-  if (*slot)
-    p = *((type_pair_t *) slot);
-  else
-    {
-      p = XOBNEW (ob_p, struct type_pair_d);
-      p->uid1 = pair.uid1;
-      p->uid2 = pair.uid2;
-      p->same_p[0] = -2;
-      p->same_p[1] = -2;
-      *slot = (void *) p;
-    }
-
-  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
@@ -3457,8 +3366,8 @@ gimple_compatible_complete_and_incomplet
 }
 
 static bool
-gimple_types_compatible_p_1 (tree, tree, enum gtc_mode, type_pair_t,
-			     VEC(type_pair_t, heap) **,
+gimple_types_compatible_p_1 (tree, tree, enum gtc_mode,
+			     VEC(tree, heap) **,
 			     struct pointer_map_t *, struct obstack *);
 
 /* DFS visit the edge from the callers type pair with state *STATE to
@@ -3470,12 +3379,11 @@ gimple_types_compatible_p_1 (tree, tree,
 static bool
 gtc_visit (tree t1, tree t2, enum gtc_mode mode,
 	   struct sccs *state,
-	   VEC(type_pair_t, heap) **sccstack,
+	   VEC(tree, heap) **sccstack,
 	   struct pointer_map_t *sccstate,
 	   struct obstack *sccstate_obstack)
 {
   struct sccs *cstate = NULL;
-  type_pair_t p;
   void **slot;
 
   /* Check first for the obvious case of pointer identity.  */
@@ -3559,23 +3467,16 @@ gtc_visit (tree t1, tree t2, enum gtc_mo
   if (gimple_type_hash_1 (t1, mode) != gimple_type_hash_1 (t2, mode))
     return false;
 
-  /* Allocate a new cache entry for this comparison.  */
-  p = lookup_type_pair (t1, t2, &gtc_visited, &gtc_ob);
-  if (p->same_p[mode] == 0 || p->same_p[mode] == 1)
-    {
-      /* We have already decided whether T1 and T2 are the
-	 same, return the cached result.  */
-      return p->same_p[mode] == 1;
-    }
-
-  if ((slot = pointer_map_contains (sccstate, p)) != NULL)
+  /* ???  We used to have a SCC state per t1, t2 pair.  */
+  if ((slot = pointer_map_contains (sccstate, t1)) != NULL)
     cstate = (struct sccs *)*slot;
   /* Not yet visited.  DFS recurse.  */
   if (!cstate)
     {
-      gimple_types_compatible_p_1 (t1, t2, mode, p,
+      gimple_types_compatible_p_1 (t1, t2, mode,
 				   sccstack, sccstate, sccstate_obstack);
-      cstate = (struct sccs *)* pointer_map_contains (sccstate, p);
+      /* ???  We used to have a SCC state per t1, t2 pair.  */
+      cstate = (struct sccs *)* pointer_map_contains (sccstate, t1);
       state->low = MIN (state->low, cstate->low);
     }
   /* If the type is still on the SCC stack adjust the parents low.  */
@@ -3594,19 +3495,18 @@ gtc_visit (tree t1, tree t2, enum gtc_mo
 
 static bool
 gimple_types_compatible_p_1 (tree t1, tree t2, enum gtc_mode mode,
-			     type_pair_t p,
-			     VEC(type_pair_t, heap) **sccstack,
+			     VEC(tree, heap) **sccstack,
 			     struct pointer_map_t *sccstate,
 			     struct obstack *sccstate_obstack)
 {
   struct sccs *state;
 
-  gcc_assert (p->same_p[mode] == -2);
-
   state = XOBNEW (sccstate_obstack, struct sccs);
-  *pointer_map_insert (sccstate, p) = state;
+  /* ???  We used to have a SCC state per t1, t2 pair.  */
+  *pointer_map_insert (sccstate, t1) = state;
 
-  VEC_safe_push (type_pair_t, heap, *sccstack, p);
+  /* ???  We used to have a SCC stack of t1, t2 pairs.  */
+  VEC_safe_push (tree, heap, *sccstack, t1);
   state->dfsnum = gtc_next_dfs_num++;
   state->low = state->dfsnum;
   state->on_sccstack = true;
@@ -3886,19 +3786,18 @@ same_types:
 pop:
   if (state->low == state->dfsnum)
     {
-      type_pair_t x;
+      tree x;
 
       /* Pop off the SCC and set its cache values to the final
          comparison result.  */
       do
 	{
 	  struct sccs *cstate;
-	  x = VEC_pop (type_pair_t, *sccstack);
+	  x = VEC_pop (tree, *sccstack);
 	  cstate = (struct sccs *)*pointer_map_contains (sccstate, x);
 	  cstate->on_sccstack = false;
-	  x->same_p[mode] = state->u.same_p;
 	}
-      while (x != p);
+      while (x != t1);
     }
 
   return state->u.same_p;
@@ -3911,10 +3810,9 @@ pop:
 bool
 gimple_types_compatible_p (tree t1, tree t2, enum gtc_mode mode)
 {
-  VEC(type_pair_t, heap) *sccstack = NULL;
+  VEC(tree, 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.  */
@@ -4000,23 +3898,13 @@ gimple_types_compatible_p (tree t1, tree
   if (gimple_type_hash_1 (t1, mode) != gimple_type_hash_1 (t2, mode))
     return false;
 
-  /* 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, &gtc_visited, &gtc_ob);
-  if (p->same_p[mode] == 0 || p->same_p[mode] == 1)
-    {
-      /* We have already decided whether T1 and T2 are the
-	 same, return the cached result.  */
-      return p->same_p[mode] == 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, mode, p,
+  res = gimple_types_compatible_p_1 (t1, t2, mode,
 				     &sccstack, sccstate, &sccstate_obstack);
-  VEC_free (type_pair_t, heap, sccstack);
+  VEC_free (tree, heap, sccstack);
   pointer_map_destroy (sccstate);
   obstack_free (&sccstate_obstack, NULL);
 
@@ -4585,16 +4473,6 @@ print_gimple_types_stats (void)
 	     htab_collisions (canonical_type_hash_cache));
   else
     fprintf (stderr, "GIMPLE canonical type hash table is empty\n");
-  if (gtc_visited)
-    fprintf (stderr, "GIMPLE type comparison table: size %ld, %ld "
-	     "elements, %ld searches, %ld collisions (ratio: %f)\n",
-	     (long) htab_size (gtc_visited),
-	     (long) htab_elements (gtc_visited),
-	     (long) gtc_visited->searches,
-	     (long) gtc_visited->collisions,
-	     htab_collisions (gtc_visited));
-  else
-    fprintf (stderr, "GIMPLE type comparison table is empty\n");
 }
 
 /* Free the gimple type hashtables used for LTO type merging.  */
@@ -4626,12 +4504,6 @@ free_gimple_type_tables (void)
       htab_delete (canonical_type_hash_cache);
       canonical_type_hash_cache = NULL;
     }
-  if (gtc_visited)
-    {
-      htab_delete (gtc_visited);
-      obstack_free (&gtc_ob, NULL);
-      gtc_visited = NULL;
-    }
   gimple_type_leader = NULL;
 }