This is the mail archive of the
`gcc-patches@gcc.gnu.org`
mailing list for the GCC project.

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |

Other format: | [Raw text] |

*From*: Jan Hubicka <hubicka at ucw dot cz>*To*: Richard Biener <rguenther at suse dot de>*Cc*: Jan Hubicka <hubicka at ucw dot cz>, Richard Biener <richard dot guenther at gmail dot com>, Dominique Dhumieres <dominiq at lps dot ens dot fr>, GCC Patches <gcc-patches at gcc dot gnu dot org>*Date*: Fri, 11 Jul 2014 11:30:41 +0200*Subject*: Re: Optimize type streaming*Authentication-results*: sourceware.org; auth=none*References*: <20140629111311 dot A2B96105 at mailhost dot lps dot ens dot fr> <20140629195303 dot GA14692 at kam dot mff dot cuni dot cz> <alpine dot LSU dot 2 dot 11 dot 1407071002000 dot 5753 at zhemvz dot fhfr dot qr> <20140708083414 dot GA27367 at kam dot mff dot cuni dot cz> <20140709085857 dot GA12462 at kam dot mff dot cuni dot cz> <CAFiYyc2qsK5D9kvOKhE6eBtVDGae1dRK8ykS3MWOp04xEzuSKg at mail dot gmail dot com> <20140709123657 dot GB12462 at kam dot mff dot cuni dot cz> <58de6ea9-f2c2-4660-b7b8-3954393a1b87 at email dot android dot com> <20140711084948 dot GB30037 at kam dot mff dot cuni dot cz> <alpine dot LSU dot 2 dot 11 dot 1407111100030 dot 5753 at zhemvz dot fhfr dot qr>

> > 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

**Follow-Ups**:**Re: Optimize type streaming***From:*Richard Biener

**References**:**Re: Optimize type streaming***From:*Richard Biener

**Re: Optimize type streaming***From:*Jan Hubicka

**Re: Optimize type streaming***From:*Jan Hubicka

**Re: Optimize type streaming***From:*Richard Biener

**Re: Optimize type streaming***From:*Jan Hubicka

**Re: Optimize type streaming***From:*Richard Biener

**Re: Optimize type streaming***From:*Jan Hubicka

**Re: Optimize type streaming***From:*Richard Biener

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |