This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Optimize type streaming
- 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 10:49:49 +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>
> 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 ;)
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.
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.
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