From 1089a367c4b05b5e3f072adca8913904ed65928c Mon Sep 17 00:00:00 2001 From: Jan Hubicka Date: Fri, 22 May 2020 12:31:34 +0200 Subject: [PATCH] Fix hashing of prestreamed nodes 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. * tree-streamer.c (record_common_node): Fix hash value of pre-streamed nodes. --- gcc/ChangeLog | 5 +++++ gcc/tree-streamer.c | 9 +++++---- 2 files changed, 10 insertions(+), 4 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 820240fc827..d22e9aa250e 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,8 @@ +2020-05-22 Jan Hubicka + + * tree-streamer.c (record_common_node): Fix hash value of pre-streamed + nodes. + 2020-05-22 Jan Hubicka * lto-streamer-in.c (lto_read_tree): Do not stream end markers. 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)) { -- 2.30.2