Optimize type streaming
Richard Biener
rguenther@suse.de
Fri Jul 11 12:07:00 GMT 2014
On Fri, 11 Jul 2014, Jan Hubicka wrote:
> > On Fri, 11 Jul 2014, Jan Hubicka wrote:
> >
> > > > > Hmm, walking everything first and then starting streaming sounds bad idea
> > > > > for locality. Can't I just re-do the walk since I know what the SCC is?
> > > > > I will read the code more after lunch.
> > > >
> > > > Might be possible with a 2nd SCC stack set up, yes.
> > >
> > > I set up hash_map to store the hash values anyway. What about "sorting" using
> > > walk_tree with simple callback pushing the parameter on stack if it is in the
> > > hash map and removing it from hash map?
> > >
> > > That way I do not need to duplicate the tricky SCC walking and probably won't
> > > be more terrible in overhead than qsort. Seems like a good idea at least for a
> > > prototype, will try it out.
> >
> > Awww, but you get edges walked that are not walked in the DFS walk ...
> > (basically you can end up walking the whole program IL if you are
> > unlucky).
>
> Why? I just terminate the walk on every node that is not withing the SCC region.
> Yes, I will unnecesarily walk all edges out of my SCC region, but I think we can
> live with that (SCC walk would visit them anyway, too)
Ah, ok. Well, let's hope walk_tree walks all edges the DFS walk walks ;)
A quick look tells me it doesn't walk DECL_VINDEX or
DECL_FUNCTION_PERSONALITY for example.
Richard.
> Honza
> >
> > RIchard.
> >
> > > honza
> > > >
> > > > Richard.
> > > >
> > > > > Honza
> > > > > >
> > > > > > Richard.
> > > > > >
> > > > > > > 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
> > > > > > >
> > > > > > >
> > > > > >
> > > > > > --
> > > > > > 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
> > > > >
> > > > >
> > > >
> > > > --
> > > > 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
> > >
> > >
> >
> > --
> > 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
>
>
--
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
More information about the Gcc-patches
mailing list