Re: Optimize type streaming

[Jan Hubicka <hubicka at ucw dot cz>]

> 
> Well - as we re-use the streamer cache to store the hash value it isn't
> really possible to do better ... (at least I don't have a clever idea)

OK, no cleverness on my side either.
> 
> Yeah (though you wouldn't need the extra hashing - we only need to know
> the hash of the SCC).  The current iterating to iterate until no
> duplicate hashes are found is bogous IMHO - better do the right thing
> from the start or only iterate until at least _one_ hash is unique
> (you get rid of the scc_entry_len > 1 case which can be quite expensive).

agreed. I just got this implemented before I got into enough of understading
of the lto/lto.c side of the machinery - I assumed that identical nodes
are tested deeply but that would of course be expensive

> Of course the question is whether we can always guarantee this property
> ... if we can then the offline compare can be expanded to all trees
> (it requires a stable sort of the SCCs independent on SCC entry).

I do not think we need stable sorting here.  This is what I think extra
DFS walk should ensure - as soon as we have unique entry (by identifying first
node w/o conflict), the DFS walks in all units will give same order.

I do not think we can 100% guarantee it, but we can get very close to 100%.
If we won't find unique entry, I suppose we can stick with current scheme or
just drop the complicated path with multiple entries and do not merge in this
case (or just merge when the entry happens to match by accident).
> 
> > This is because those otherwise equivalent trees are not really 
> > equivalent from merging perspective. You test strict pointer equivalence 
> > outside SCC regions, so it matters whether two same trees are referred 
> > or two equivalent copies.
> 
> Hmm?  So you say you have two identical trees in the _same_ SCC?
> How can that be?  Answer: not possible - they at least differ
> in the edges forming the SCC (unless we have a cyclic list but
> I don't think we (should) have that).

We hash only on outgoing SCC edges.  You can easily have
main variant type T and variants T1,T2 that are same all used by type
T again.

T1 and T2 differs by references in T, but they will always have same
hash and in theory they can be merged if your code worked recursively
on nested SCC regions (as given by Tarjan's algorithm).  Because you work on
outermost SCC regions only, we never merge T1 and T2.

The congruence you compute is not best possible, but best possible assuming no
duplicates within compilation units.  I think this is sane, we should look
towards eliminating such duplicates rather than working harder in the streamer.
> 
> Btw, if you re-hash only nodes with duplicate hashes might there be
> a higher probability of ending up with a hash that collides with
> one that was not a duplicate one?  That is, why not simply re-hash
> all nodes?  (premature optimization...?)
> 
> So - can you can iterate on this re-doing the DFS walk with the
> found entry node?

Yep, that is the plan. Iterate long enough until I get unqiue hash.  Can I
easilly re-do the DFS walk?

Honza
> 
> Thanks,
> Richard.
> 
> > Honza
> > 
> > 	* lto-streamer-out.c (hash_tree): Add map argument;
> > 	remove special purpose hack for pointer types.
> > 	(visit): Update it.
> > 	(hash_scc): Add iteration until equivalence classes stabilize.
> > Index: lto-streamer-out.c
> > ===================================================================
> > --- lto-streamer-out.c	(revision 212426)
> > +++ lto-streamer-out.c	(working copy)
> > @@ -690,13 +712,19 @@ DFS_write_tree_body (struct output_block
> >  /* Return a hash value for the tree T.  */
> >  
> >  static hashval_t
> > -hash_tree (struct streamer_tree_cache_d *cache, tree t)
> > +hash_tree (struct streamer_tree_cache_d *cache, hash_map<tree, hashval_t> *map, tree t)
> >  {
> >  #define visit(SIBLING) \
> >    do { \
> >      unsigned ix; \
> > -    if (SIBLING && streamer_tree_cache_lookup (cache, SIBLING, &ix)) \
> > +    if (!SIBLING) \
> > +      v = iterative_hash_hashval_t (0, v); \
> > +    else if (streamer_tree_cache_lookup (cache, SIBLING, &ix)) \
> >        v = iterative_hash_hashval_t (streamer_tree_cache_get_hash (cache, ix), v); \
> > +    else if (map) \
> > +      v = iterative_hash_hashval_t (*map->get (SIBLING), v); \
> > +    else \
> > +      v = iterative_hash_hashval_t (1, v); \
> >    } while (0)
> >  
> >    /* Hash TS_BASE.  */
> > @@ -896,23 +924,7 @@ hash_tree (struct streamer_tree_cache_d
> >  
> >    if (CODE_CONTAINS_STRUCT (code, TS_TYPED))
> >      {
> > -      if (POINTER_TYPE_P (t))
> > -	{
> > -	  /* For pointers factor in the pointed-to type recursively as
> > -	     we cannot recurse through only pointers.
> > -	     ???  We can generalize this by keeping track of the
> > -	     in-SCC edges for each tree (or arbitrarily the first
> > -	     such edge) and hashing that in in a second stage
> > -	     (instead of the quadratic mixing of the SCC we do now).  */
> > -	  hashval_t x;
> > -	  unsigned ix;
> > -	  if (streamer_tree_cache_lookup (cache, TREE_TYPE (t), &ix))
> > -	    x = streamer_tree_cache_get_hash (cache, ix);
> > -	  else
> > -	    x = hash_tree (cache, TREE_TYPE (t));
> > -	  v = iterative_hash_hashval_t (x, v);
> > -	}
> > -      else if (code != IDENTIFIER_NODE)
> > +      if (code != IDENTIFIER_NODE)
> >  	visit (TREE_TYPE (t));
> >      }
> >  
> > @@ -1122,28 +1156,78 @@ scc_entry_compare (const void *p1_, cons
> >  static hashval_t
> >  hash_scc (struct streamer_tree_cache_d *cache, unsigned first, unsigned size)
> >  {
> > +  unsigned int last_classes = 0, iterations = 0;
> > +
> >    /* Compute hash values for the SCC members.  */
> >    for (unsigned i = 0; i < size; ++i)
> > -    sccstack[first+i].hash = hash_tree (cache, sccstack[first+i].t);
> > +    sccstack[first+i].hash = hash_tree (cache, NULL, sccstack[first+i].t);
> >  
> >    if (size == 1)
> >      return sccstack[first].hash;
> >  
> > -  /* Sort the SCC of type, hash pairs so that when we mix in
> > -     all members of the SCC the hash value becomes independent on
> > -     the order we visited the SCC.  Produce hash of the whole SCC as
> > -     combination of hashes of individual elements.  Then combine that hash into
> > -     hash of each element, so othewise identically looking elements from two
> > -     different SCCs are distinguished.  */
> > -  qsort (&sccstack[first], size, sizeof (scc_entry), scc_entry_compare);
> > -
> > -  hashval_t scc_hash = sccstack[first].hash;
> > -  for (unsigned i = 1; i < size; ++i)
> > -    scc_hash = iterative_hash_hashval_t (scc_hash,
> > -					 sccstack[first+i].hash);
> > -  for (unsigned i = 0; i < size; ++i)
> > -    sccstack[first+i].hash = iterative_hash_hashval_t (sccstack[first+i].hash, scc_hash);
> > -  return scc_hash;
> > +  /* We may want to iterate multiple times across SCC propagating across the internal
> > +     edges in order to get different hash values for individual trees.  */
> > +  do
> > +    {
> > +      /* Sort the SCC of type, hash pairs so that when we mix in
> > +	 all members of the SCC the hash value becomes independent on
> > +	 the order we visited the SCC.  Produce hash of the whole SCC as
> > +	 combination of hashes of individual elements.  Then combine that hash into
> > +	 hash of each element, so othewise identically looking elements from two
> > +	 different SCCs are distinguished.  */
> > +      qsort (&sccstack[first], size, sizeof (scc_entry), scc_entry_compare);
> > +
> > +      unsigned int classes = 1;
> > +      hashval_t scc_hash = sccstack[first].hash;
> > +      for (unsigned i = 1; i < size; ++i)
> > +        {
> > +          if (sccstack[first+i-1].hash != sccstack[first+i].hash)
> > +	    classes++;
> > +          scc_hash = iterative_hash_hashval_t (scc_hash,
> > +					       sccstack[first+i].hash);
> > +        }
> > +
> > +      /* If we have no duplicated entries, or we no longer get refinements,
> > +	 we are done.  */
> > +      if (classes <= last_classes || classes == size || iterations > 16)
> > +	{
> > +	  for (unsigned i = 1; i < size - 1; ++i)
> > +	    {
> > +	      hashval_t hash = sccstack[first+i].hash;
> > +
> > +	      if (hash == sccstack[first+i+1].hash)
> > +		for (;i < size && sccstack[first+i].hash == hash; i++)
> > +		  debug_tree (sccstack[first+i].t);
> > +	      else
> > +		i++;
> > +	    }
> > +	  for (unsigned i = 0; i < size; ++i)
> > +	    sccstack[first+i].hash = iterative_hash_hashval_t (sccstack[first+i].hash, scc_hash);
> > +	  return scc_hash;
> > +	}
> > +
> > +      /* Otherwise try to propagate hash values across the edges.  */
> > +      last_classes = classes;
> > +      iterations++;
> > +      {
> > +	hash_map <tree, hashval_t> map(size*2);
> > +	for (unsigned i = 0; i < size; ++i)
> > +	  map.put (sccstack[first+i].t, sccstack[first+i].hash);
> > +
> > +	for (unsigned i = 0; i < size - 1;)
> > +	  {
> > +	    hashval_t hash = sccstack[first+i].hash;
> > +
> > +	    /* Rehash only the entries that have duplicate hash values.  */
> > +	    if (hash == sccstack[first+i+1].hash)
> > +	      for (;i < size && sccstack[first+i].hash == hash; i++)
> > +	        sccstack[first+i].hash = hash_tree (cache, &map, sccstack[first+i].t);
> > +	    else
> > +	      i++;
> > +	  }
> > +      }
> > +    }
> > +  while (true);
> >  }
> >  
> >  /* DFS walk EXPR and stream SCCs of tree bodies if they are not
> > 
> > 
> 
> -- 
> Richard Biener <rguenther@suse.de>
> SUSE / SUSE Labs
> SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
> GF: Jeff Hawn, Jennifer Guild, Felix Imend"orffer