On Fri, 11 Jul 2014, Jan Hubicka wrote:
> > Are we sure it ever stabilizes? But yes, I had something like this in mind
> > (just do one iteration always) in case we need to improve hashing.
>
> Hi,
> this is bit quick experiment with strengthening the hash by iteration. I don't
> seem to be able to measure WPA time difference for the patch though (but on
> positive side, it also does not make streaming out slower). I did not find
> clean way to hook things into streamer cache, so I added separate hash for
> that; I am sure you will know better ;)
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)
> I added dumping for duplicated trees withing SCC regions that shows some
> interesting
> info. It seems that at firefox we do have duplicate type variants, duplicated
> const decls such as:
> <function_type 0x2aaaabf2a540
> type <integer_type 0x2aaaabde95e8 int sizes-gimplified public SI
> size <integer_cst 0x2aaaabdd4e70 constant 32>
> unit size <integer_cst 0x2aaaabdd4e88 constant 4>
> align 32 symtab 0 alias set 0 canonical type 0x2aaaabde95e8 precision
> 32 min <integer_cst 0x2aaaabdd4e28 -2147483648> max <integer_cst
> 0x2aaaabdd4e40 2147483647> context <translation_unit_decl 0x2aaaadb62a00
> /aux/hubicka/firefox/db/sqlite3/src/sqlite3.c>
> pointer_to_this <pointer_type 0x2aaaadc527e0>>
> QI
> size <integer_cst 0x2aaaabdd4d20 type <integer_type 0x2aaaabde90a8
> bitsizetype> constant 8>
> unit size <integer_cst 0x2aaaabdd4d38 type <integer_type 0x2aaaabde9000
> sizetype> constant 1>
> align 8 symtab 0 alias set -1 canonical type 0x2aaaabf2a5e8
> arg-types <tree_list 0x2aaaabeedd20
> value <pointer_type 0x2aaaabf1e930 type <record_type 0x2aaaabf1e5e8
> sqlite3_file>
> sizes-gimplified public unsigned DI
> size <integer_cst 0x2aaaabdd4c30 constant 64>
> unit size <integer_cst 0x2aaaabdd4c48 constant 8>
> align 64 symtab 0 alias set -1 canonical type 0x2aaaabf1e9d8
> pointer_to_this <pointer_type 0x2aaaac5dadc8>>
> chain <tree_list 0x2aaaabeedcf8 value <integer_type 0x2aaaabde95e8
> int>
> chain <tree_list 0x2aaaabde4640 value <void_type 0x2aaaabde9f18
> void>>>>
> pointer_to_this <pointer_type 0x2aaaabf2a690>>
> <function_type 0x2aaaabf2adc8
> type <integer_type 0x2aaaabde95e8 int sizes-gimplified public SI
> size <integer_cst 0x2aaaabdd4e70 constant 32>
> unit size <integer_cst 0x2aaaabdd4e88 constant 4>
> align 32 symtab 0 alias set 0 canonical type 0x2aaaabde95e8 precision
> 32 min <integer_cst 0x2aaaabdd4e28 -2147483648> max <integer_cst
> 0x2aaaabdd4e40 2147483647> context <translation_unit_decl 0x2aaaadb62a00
> /aux/hubicka/firefox/db/sqlite3/src/sqlite3.c>
> pointer_to_this <pointer_type 0x2aaaadc527e0>>
> QI
> size <integer_cst 0x2aaaabdd4d20 type <integer_type 0x2aaaabde90a8
> bitsizetype> constant 8>
> unit size <integer_cst 0x2aaaabdd4d38 type <integer_type 0x2aaaabde9000
> sizetype> constant 1>
> align 8 symtab 0 alias set -1 canonical type 0x2aaaabf2ae70
> arg-types <tree_list 0x2aaaabeedfa0
> value <pointer_type 0x2aaaabf1e930 type <record_type 0x2aaaabf1e5e8
> sqlite3_file>
> sizes-gimplified public unsigned DI
> size <integer_cst 0x2aaaabdd4c30 constant 64>
> unit size <integer_cst 0x2aaaabdd4c48 constant 8>
> align 64 symtab 0 alias set -1 canonical type 0x2aaaabf1e9d8
> pointer_to_this <pointer_type 0x2aaaac5dadc8>>
> chain <tree_list 0x2aaaabeedf78 value <pointer_type 0x2aaaabdf1690>
> chain <tree_list 0x2aaaabde4640 value <void_type 0x2aaaabde9f18
> void>>>>
> pointer_to_this <pointer_type 0x2aaaabf2af18>>
>
> constants as:
>
> <integer_cst 0x2aaaae8101b0 type <enumeral_type 0x2aaaae7e55e8 tag_nsresult>
> constant 0>
> <integer_cst 0x2aaaae810600 type <enumeral_type 0x2aaaae7e55e8 tag_nsresult>
> constant 0>
> <integer_cst 0x2aaaae810c90 type <enumeral_type 0x2aaaae7e55e8 tag_nsresult>
> constant 0>
> <integer_cst 0x2aaaae810cc0 type <enumeral_type 0x2aaaae7e55e8 tag_nsresult>
> constant 0>
> <integer_cst 0x2aaaae810ee8 type <enumeral_type 0x2aaaae7e55e8 tag_nsresult>
> constant 0>
> <integer_cst 0x2aaaae810fd8 type <enumeral_type 0x2aaaae7e55e8 tag_nsresult>
> constant 5242893>
> <integer_cst 0x2aaaae8130a8 type <enumeral_type 0x2aaaae7e55e8 tag_nsresult>
> constant 5242893>
> <integer_cst 0x2aaaae814858 type <enumeral_type 0x2aaaae7e55e8 tag_nsresult>
> constant 7864321>
> <integer_cst 0x2aaaae814870 type <enumeral_type 0x2aaaae7e55e8 tag_nsresult>
> constant 7864321>
> <integer_cst 0x2aaaae810f78 type <enumeral_type 0x2aaaae7e55e8 tag_nsresult>
> constant 2152726542>
> <integer_cst 0x2aaaae8130c0 type <enumeral_type 0x2aaaae7e55e8 tag_nsresult>
> constant 2152726542>
>
> tree lists:
>
> <tree_list 0x2aaaae952708
> value <pointer_type 0x2aaaae954888
> type <record_type 0x2aaaae9509d8 PLDHashTable sizes-gimplified type_5
> type_6 BLK
> size <integer_cst 0x2aaaad5229a8 constant 384>
> unit size <integer_cst 0x2aaaad522960 constant 48>
> align 64 symtab 0 alias set -1 canonical type 0x2aaaae950930
> fields <field_decl 0x2aaaae955000 ops> context <translation_unit_decl
> 0x2aaaabdec0a0 /aux/hubicka/firefox/webapprt/gtk2/webapprt.cpp>
> full-name "PLDHashTable"
> X() X(constX&) this=(X&) sorted-fields 0x2aaaae90e9c0 n_parents=0
> use_template=0 interface-unknown
> pointer_to_this <pointer_type 0x2aaaae954888> reference_to_this
> <reference_type 0x2aaaaf15e5e8> chain <type_decl 0x2aaaae9530a0 PLDHashTable>>
> unsigned type_6 DI
> size <integer_cst 0x2aaaabdd4de0 constant 64>
> unit size <integer_cst 0x2aaaabdd4df8 constant 8>
> align 64 symtab 0 alias set -1 canonical type 0x2aaaae954930>
> chain <tree_list 0x2aaaae952730
> value <pointer_type 0x2aaaabdf7000 type <void_type 0x2aaaabdeff18
> void>
> sizes-gimplified public unsigned type_6 DI size <integer_cst
> 0x2aaaabdd4de0 64> unit size <integer_cst 0x2aaaabdd4df8 8>
> align 64 symtab 0 alias set -1 canonical type 0x2aaaabdf7000
> pointer_to_this <pointer_type 0x2aaaabdfedc8> reference_to_this
> <reference_type 0x2aaaaf563a80>>
> chain <tree_list 0x2aaaabde4b40 value <void_type 0x2aaaabdeff18
> void>>>>
> <tree_list 0x2aaaae9527f8
> value <pointer_type 0x2aaaae954888
> type <record_type 0x2aaaae9509d8 PLDHashTable sizes-gimplified type_5
> type_6 BLK
> size <integer_cst 0x2aaaad5229a8 constant 384>
> unit size <integer_cst 0x2aaaad522960 constant 48>
> align 64 symtab 0 alias set -1 canonical type 0x2aaaae950930
> fields <field_decl 0x2aaaae955000 ops> context <translation_unit_decl
> 0x2aaaabdec0a0 /aux/hubicka/firefox/webapprt/gtk2/webapprt.cpp>
> full-name "PLDHashTable"
> X() X(constX&) this=(X&) sorted-fields 0x2aaaae90e9c0 n_parents=0
> use_template=0 interface-unknown
> pointer_to_this <pointer_type 0x2aaaae954888> reference_to_this
> <reference_type 0x2aaaaf15e5e8> chain <type_decl 0x2aaaae9530a0 PLDHashTable>>
> unsigned type_6 DI
> size <integer_cst 0x2aaaabdd4de0 constant 64>
> unit size <integer_cst 0x2aaaabdd4df8 constant 8>
> align 64 symtab 0 alias set -1 canonical type 0x2aaaae954930>
> chain <tree_list 0x2aaaae952820
> value <pointer_type 0x2aaaabdf7150 type <void_type 0x2aaaabdf70a8
> void>
> unsigned type_6 DI size <integer_cst 0x2aaaabdd4de0 64> unit size
> <integer_cst 0x2aaaabdd4df8 8>
> align 64 symtab 0 alias set -1 canonical type 0x2aaaabdf7150
> pointer_to_this <pointer_type 0x2aaaabf3b738>>
> chain <tree_list 0x2aaaabde4b40 value <void_type 0x2aaaabdeff18
> void>>>>
>
> and binfos:
>
> <tree_binfo 0x2aaaaf107360
> type <record_type 0x2aaaaf131000 nsTHashtable sizes-gimplified
> addressable needs-constructing type_1 type_4 type_5 type_6 BLK
> size <integer_cst 0x2aaaad5229a8 constant 384>
> unit size <integer_cst 0x2aaaad522960 constant 48>
> align 64 symtab 0 alias set -1 canonical type 0x2aaaaf131000
> fields <field_decl 0x2aaaaf12f558 mTable type <record_type
> 0x2aaaae9509d8 PLDHashTable>
> used protected nonlocal decl_3 BLK file
> ../../dist/include/nsTHashtable.h line 294 col 16 size <integer_cst
> 0x2aaaad5229a8 384> unit size <integer_cst 0x2aaaad522960 48>
> align 64 offset_align 128
> offset <integer_cst 0x2aaaabdd4e10 constant 0>
> bit offset <integer_cst 0x2aaaabdd4e58 constant 0> context
> <record_type 0x2aaaaf131000 nsTHashtable> chain <type_decl 0x2aaaaf125d20
> nsTHashtable>> context <translation_unit_decl 0x2aaaabdec0a0
> /aux/hubicka/firefox/webapprt/gtk2/webapprt.cpp>
> full-name "class nsTHashtable<nsBaseHashtableET<nsDepCharHashKey,
> nsAutoPtr<nsINIParser::INIValue> > >"
> needs-constructor needs-destructor X() X(X&) this=(X&) sorted-fields
> 0x2aaaaf10ca50 n_parents=0 use_template=1 interface-unknown
> pointer_to_this <pointer_type 0x2aaaaf1311f8> reference_to_this
> <reference_type 0x2aaaaf131690> chain <type_decl 0x2aaaaf125c80 nsTHashtable>>
> private>
> <tree_binfo 0x2aaaaf1073c0
> type <record_type 0x2aaaaf131000 nsTHashtable sizes-gimplified
> addressable needs-constructing type_1 type_4 type_5 type_6 BLK
> size <integer_cst 0x2aaaad5229a8 constant 384>
> unit size <integer_cst 0x2aaaad522960 constant 48>
> align 64 symtab 0 alias set -1 canonical type 0x2aaaaf131000
> fields <field_decl 0x2aaaaf12f558 mTable type <record_type
> 0x2aaaae9509d8 PLDHashTable>
> used protected nonlocal decl_3 BLK file
> ../../dist/include/nsTHashtable.h line 294 col 16 size <integer_cst
> 0x2aaaad5229a8 384> unit size <integer_cst 0x2aaaad522960 48>
> align 64 offset_align 128
> offset <integer_cst 0x2aaaabdd4e10 constant 0>
> bit offset <integer_cst 0x2aaaabdd4e58 constant 0> context
> <record_type 0x2aaaaf131000 nsTHashtable> chain <type_decl 0x2aaaaf125d20
> nsTHashtable>> context <translation_unit_decl 0x2aaaabdec0a0
> /aux/hubicka/firefox/webapprt/gtk2/webapprt.cpp>
> full-name "class nsTHashtable<nsBaseHashtableET<nsDepCharHashKey,
> nsAutoPtr<nsINIParser::INIValue> > >"
> needs-constructor needs-destructor X() X(X&) this=(X&) sorted-fields
> 0x2aaaaf10ca50 n_parents=0 use_template=1 interface-unknown
> pointer_to_this <pointer_type 0x2aaaaf1311f8> reference_to_this
> <reference_type 0x2aaaaf131690> chain <type_decl 0x2aaaaf125c80 nsTHashtable>>
> >
>
> along with the vtable addresses
>
> <addr_expr 0x2aaaad0c92c0
> type <pointer_type 0x2aaaabf3bd20
> type <pointer_type 0x2aaaabf3bbd0 __vtbl_ptr_type type <function_type
> 0x2aaaabf3bb28>
> unsigned DI
> size <integer_cst 0x2aaaabdd4de0 constant 64>
> unit size <integer_cst 0x2aaaabdd4df8 constant 8>
> align 64 symtab 0 alias set -1 canonical type 0x2aaaabf3bbd0
> pointer_to_this <pointer_type 0x2aaaabf3bd20>>
> public unsigned DI size <integer_cst 0x2aaaabdd4de0 64> unit size
> <integer_cst 0x2aaaabdd4df8 8>
> align 64 symtab 0 alias set -1 canonical type 0x2aaaabf3bd20>
> readonly constant
> arg 0 <var_decl 0x2aaaad0c23f0 _ZTV21nsSemanticUnitScanner
> type <array_type 0x2aaaad0c8738 type <pointer_type 0x2aaaabf3bbd0
> __vtbl_ptr_type>
> BLK
> size <integer_cst 0x2aaaac504258 constant 1216>
> unit size <integer_cst 0x2aaaac504060 constant 152>
> align 64 symtab 0 alias set -1 canonical type 0x2aaaad0c8738
> domain <integer_type 0x2aaaad0c8690>
> pointer_to_this <pointer_type 0x2aaaad21a738>>
> readonly addressable used public static ignored weak virtual decl_5
> BLK file /aux/hubicka/firefox/intl/lwbrk/src/nsSemanticUnitScanner.h line 13
> col 7 size <integer_cst 0x2aaaac504258 1216> unit size <integer_cst
> 0x2aaaac504060 152>
> user align 64 context <record_type 0x2aaaad0c0b28
> nsSemanticUnitScanner> initial <constructor 0x2aaaad0b2e58>
>
> (mem/u/c:BLK (symbol_ref/i:DI ("_ZTV21nsSemanticUnitScanner") [flags
> 0x2] <var_decl 0x2aaaad0c23f0 _ZTV21nsSemanticUnitScanner>) [0
> _ZTV21nsSemanticUnitScanner+0 S152 A64])>>
> <addr_expr 0x2aaaad0c9060
> type <pointer_type 0x2aaaabf3bd20
> type <pointer_type 0x2aaaabf3bbd0 __vtbl_ptr_type type <function_type
> 0x2aaaabf3bb28>
> unsigned DI
> size <integer_cst 0x2aaaabdd4de0 constant 64>
> unit size <integer_cst 0x2aaaabdd4df8 constant 8>
> align 64 symtab 0 alias set -1 canonical type 0x2aaaabf3bbd0
> pointer_to_this <pointer_type 0x2aaaabf3bd20>>
> public unsigned DI size <integer_cst 0x2aaaabdd4de0 64> unit size
> <integer_cst 0x2aaaabdd4df8 8>
> align 64 symtab 0 alias set -1 canonical type 0x2aaaabf3bd20>
> readonly constant
> arg 0 <var_decl 0x2aaaad0c23f0 _ZTV21nsSemanticUnitScanner
> type <array_type 0x2aaaad0c8738 type <pointer_type 0x2aaaabf3bbd0
> __vtbl_ptr_type>
> BLK
> size <integer_cst 0x2aaaac504258 constant 1216>
> unit size <integer_cst 0x2aaaac504060 constant 152>
> align 64 symtab 0 alias set -1 canonical type 0x2aaaad0c8738
> domain <integer_type 0x2aaaad0c8690>
> pointer_to_this <pointer_type 0x2aaaad21a738>>
> readonly addressable used public static ignored weak virtual decl_5
> BLK file /aux/hubicka/firefox/intl/lwbrk/src/nsSemanticUnitScanner.h line 13
> col 7 size <integer_cst 0x2aaaac504258 1216> unit size <integer_cst
> 0x2aaaac504060 152>
> user align 64 context <record_type 0x2aaaad0c0b28
> nsSemanticUnitScanner> initial <constructor 0x2aaaad0b2e58>
>
> (mem/u/c:BLK (symbol_ref/i:DI ("_ZTV21nsSemanticUnitScanner") [flags
> 0x2] <var_decl 0x2aaaad0c23f0 _ZTV21nsSemanticUnitScanner>) [0
> _ZTV21nsSemanticUnitScanner+0 S152 A64])>>
>
> I will check what I can do about binfos, I think it is C++ FE just duplicating
> all binfos when producing derived class while it may need to duplicate only
> ones where some information differs.
>
> If I run testsuite I get some duplicates in C/C++ common testcases that do not
> have the duplicates when compiled by C FE.
>
> I think the most consistent approach would be to iterate long enough to
> get one unique hash. Then declare the first unique tree (in hash order)
> to be root of the SCC region and re-do the DFS walk to get unique order
> on the rest. Then iterative hash the index within the SCC region into
> the hash of each of the elements.
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).
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).
> 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).
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?
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 <rguent...@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend"orffer
