Fix hashing of prestreamed nodes
Jan Hubicka
hubicka@ucw.cz
Thu May 21 10:59:49 GMT 2020
Hi,
this patch seems to solve basically all collisions while building cc1.
From:
[WPA] read 3312246 unshared trees
[WPA] read 1144381 mergeable SCCs of average size 4.833785
[WPA] 8843938 tree bodies read in total
[WPA] tree SCC table: size 524287, 197767 elements, collision ratio: 0.506446
[WPA] tree SCC max chain length 43 (size 1)
[WPA] Compared 946614 SCCs, 775077 collisions (0.818789)
to
[WPA] read 3314520 unshared trees
[WPA] read 1144763 mergeable SCCs of average size 4.835021
[WPA] 8849473 tree bodies read in total
[WPA] tree SCC table: size 524287, 200574 elements, collision ratio: 0.486418
[WPA] tree SCC max chain length 2 (size 1)
[WPA] Compared 944189 SCCs, 179 collisions (0.000190)
The problem is that preloaded nodes all have hash code 0 because
cache->nodes.length is not updated while streaming out.
I also added an arbitrary constant to avoid clash with constant of 0 used to
hash NULL pointers and 1 used to hash pointers inside SCC.
Bootstrapped/regtested x86_64-linux, comitted.
* tree-streamer.c (record_common_node): Fix hash value of pre-streamed
nodes.
diff --git a/gcc/tree-streamer.c b/gcc/tree-streamer.c
index f6181fafc4c..b0afa1dc6c0 100644
--- a/gcc/tree-streamer.c
+++ b/gcc/tree-streamer.c
@@ -299,10 +299,11 @@ record_common_node (struct streamer_tree_cache_d *cache, tree node)
if (!node)
node = error_mark_node;
- /* ??? FIXME, devise a better hash value. But the hash needs to be equal
- for all frontend and lto1 invocations. So just use the position
- in the cache as hash value. */
- streamer_tree_cache_append (cache, node, cache->nodes.length ());
+ /* This hash needs to be equal for all frontend and lto1 invocations. So
+ just use the position in the cache as hash value.
+ Small integers are used by hash_tree to record positions within scc
+ hash. Values are not in same range. */
+ streamer_tree_cache_append (cache, node, cache->next_idx + 0xc001);
switch (TREE_CODE (node))
{
More information about the Gcc-patches
mailing list