From 7ca50de02cf12c759f4f8daf60913704782b7d45 Mon Sep 17 00:00:00 2001 From: David Malcolm Date: Tue, 10 Dec 2019 21:18:23 -0500 Subject: [PATCH] hash-table.h: support non-zero empty values in empty_slow (v2) gcc/cp/ChangeLog: * cp-gimplify.c (source_location_table_entry_hash::empty_zero_p): New static constant. * cp-tree.h (named_decl_hash::empty_zero_p): Likewise. (struct named_label_hash::empty_zero_p): Likewise. * decl2.c (mangled_decl_hash::empty_zero_p): Likewise. gcc/ChangeLog: * attribs.c (excl_hash_traits::empty_zero_p): New static constant. * gcov.c (function_start_pair_hash::empty_zero_p): Likewise. * graphite.c (struct sese_scev_hash::empty_zero_p): Likewise. * hash-map-tests.c (selftest::test_nonzero_empty_key): New selftest. (selftest::hash_map_tests_c_tests): Call it. * hash-map-traits.h (simple_hashmap_traits::empty_zero_p): New static constant, using the value of = H::empty_zero_p. (unbounded_hashmap_traits::empty_zero_p): Likewise, using the value from default_hash_traits . * hash-map.h (hash_map::empty_zero_p): Likewise, using the value from Traits. * hash-set-tests.c (value_hash_traits::empty_zero_p): Likewise. * hash-table.h (hash_table::alloc_entries): Guard the loop of calls to mark_empty with !Descriptor::empty_zero_p. (hash_table::empty_slow): Conditionalize the memset call with a check that Descriptor::empty_zero_p; otherwise, loop through the entries calling mark_empty on them. * hash-traits.h (int_hash::empty_zero_p): New static constant. (pointer_hash::empty_zero_p): Likewise. (pair_hash::empty_zero_p): Likewise. * ipa-devirt.c (default_hash_traits ::empty_zero_p): Likewise. * ipa-prop.c (ipa_bit_ggc_hash_traits::empty_zero_p): Likewise. (ipa_vr_ggc_hash_traits::empty_zero_p): Likewise. * profile.c (location_triplet_hash::empty_zero_p): Likewise. * sanopt.c (sanopt_tree_triplet_hash::empty_zero_p): Likewise. (sanopt_tree_couple_hash::empty_zero_p): Likewise. * tree-hasher.h (int_tree_hasher::empty_zero_p): Likewise. * tree-ssa-sccvn.c (vn_ssa_aux_hasher::empty_zero_p): Likewise. * tree-vect-slp.c (bst_traits::empty_zero_p): Likewise. * tree-vectorizer.h (default_hash_traits::empty_zero_p): Likewise. --- gcc/ChangeLog | 36 ++++++++++++++++++++++++++++++++++++ gcc/attribs.c | 2 ++ gcc/cp/ChangeLog | 8 ++++++++ gcc/cp/cp-gimplify.c | 2 ++ gcc/cp/cp-tree.h | 2 ++ gcc/cp/decl2.c | 1 + gcc/gcov.c | 2 ++ gcc/graphite.c | 1 + gcc/hash-map-tests.c | 22 ++++++++++++++++++++++ gcc/hash-map-traits.h | 2 ++ gcc/hash-map.h | 1 + gcc/hash-set-tests.c | 2 ++ gcc/hash-table.h | 10 +++++++--- gcc/hash-traits.h | 3 +++ gcc/ipa-devirt.c | 1 + gcc/ipa-prop.c | 2 ++ gcc/profile.c | 2 ++ gcc/sanopt.c | 4 ++++ gcc/tree-hasher.h | 1 + gcc/tree-ssa-sccvn.c | 1 + gcc/tree-vect-slp.c | 1 + gcc/tree-vectorizer.h | 2 ++ 22 files changed, 105 insertions(+), 3 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index f3301b16464..4f586fee17c 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,39 @@ +2020-01-14 David Malcolm + + * attribs.c (excl_hash_traits::empty_zero_p): New static constant. + * gcov.c (function_start_pair_hash::empty_zero_p): Likewise. + * graphite.c (struct sese_scev_hash::empty_zero_p): Likewise. + * hash-map-tests.c (selftest::test_nonzero_empty_key): New selftest. + (selftest::hash_map_tests_c_tests): Call it. + * hash-map-traits.h (simple_hashmap_traits::empty_zero_p): + New static constant, using the value of = H::empty_zero_p. + (unbounded_hashmap_traits::empty_zero_p): Likewise, using the value + from default_hash_traits . + * hash-map.h (hash_map::empty_zero_p): Likewise, using the value + from Traits. + * hash-set-tests.c (value_hash_traits::empty_zero_p): Likewise. + * hash-table.h (hash_table::alloc_entries): Guard the loop of + calls to mark_empty with !Descriptor::empty_zero_p. + (hash_table::empty_slow): Conditionalize the memset call with a + check that Descriptor::empty_zero_p; otherwise, loop through the + entries calling mark_empty on them. + * hash-traits.h (int_hash::empty_zero_p): New static constant. + (pointer_hash::empty_zero_p): Likewise. + (pair_hash::empty_zero_p): Likewise. + * ipa-devirt.c (default_hash_traits ::empty_zero_p): + Likewise. + * ipa-prop.c (ipa_bit_ggc_hash_traits::empty_zero_p): Likewise. + (ipa_vr_ggc_hash_traits::empty_zero_p): Likewise. + * profile.c (location_triplet_hash::empty_zero_p): Likewise. + * sanopt.c (sanopt_tree_triplet_hash::empty_zero_p): Likewise. + (sanopt_tree_couple_hash::empty_zero_p): Likewise. + * tree-hasher.h (int_tree_hasher::empty_zero_p): Likewise. + * tree-ssa-sccvn.c (vn_ssa_aux_hasher::empty_zero_p): Likewise. + * tree-vect-slp.c (bst_traits::empty_zero_p): Likewise. + * tree-vectorizer.h + (default_hash_traits::empty_zero_p): + Likewise. + 2020-01-14 Kewen Lin * cfgloopanal.c (average_num_loop_insns): Free bbs when early return, diff --git a/gcc/attribs.c b/gcc/attribs.c index ca89443eb3e..c66d4ae2c06 100644 --- a/gcc/attribs.c +++ b/gcc/attribs.c @@ -2048,6 +2048,8 @@ struct excl_hash_traits: typed_noop_remove x = value_type (NULL, NULL); } + static const bool empty_zero_p = false; + static void mark_empty (value_type &x) { x = value_type ("", ""); diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog index 3fd35b437b4..004ce0fdcdf 100644 --- a/gcc/cp/ChangeLog +++ b/gcc/cp/ChangeLog @@ -1,3 +1,11 @@ +2020-01-14 David Malcolm + + * cp-gimplify.c (source_location_table_entry_hash::empty_zero_p): + New static constant. + * cp-tree.h (named_decl_hash::empty_zero_p): Likewise. + (struct named_label_hash::empty_zero_p): Likewise. + * decl2.c (mangled_decl_hash::empty_zero_p): Likewise. + 2020-01-14 Jason Merrill PR c++/92594 - ICE with inherited trivial default ctor. diff --git a/gcc/cp/cp-gimplify.c b/gcc/cp/cp-gimplify.c index 3d764bb6928..f3aeb7475da 100644 --- a/gcc/cp/cp-gimplify.c +++ b/gcc/cp/cp-gimplify.c @@ -3045,6 +3045,8 @@ struct source_location_table_entry_hash ref.var = NULL_TREE; } + static const bool empty_zero_p = true; + static void mark_empty (source_location_table_entry &ref) { diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h index 01fcf663a29..4e26acc22a5 100644 --- a/gcc/cp/cp-tree.h +++ b/gcc/cp/cp-tree.h @@ -900,6 +900,7 @@ struct named_decl_hash : ggc_remove inline static hashval_t hash (const value_type decl); inline static bool equal (const value_type existing, compare_type candidate); + static const bool empty_zero_p = true; static inline void mark_empty (value_type &p) {p = NULL_TREE;} static inline bool is_empty (value_type p) {return !p;} @@ -1870,6 +1871,7 @@ struct named_label_hash : ggc_remove inline static hashval_t hash (value_type); inline static bool equal (const value_type, compare_type); + static const bool empty_zero_p = true; inline static void mark_empty (value_type &p) {p = NULL;} inline static bool is_empty (value_type p) {return !p;} diff --git a/gcc/cp/decl2.c b/gcc/cp/decl2.c index a641667991f..042d6fa12df 100644 --- a/gcc/cp/decl2.c +++ b/gcc/cp/decl2.c @@ -120,6 +120,7 @@ struct mangled_decl_hash : ggc_remove return candidate == name; } + static const bool empty_zero_p = true; static inline void mark_empty (value_type &p) {p = NULL_TREE;} static inline bool is_empty (value_type p) {return !p;} diff --git a/gcc/gcov.c b/gcc/gcov.c index 1dca3049777..a291bac3e9e 100644 --- a/gcc/gcov.c +++ b/gcc/gcov.c @@ -1225,6 +1225,8 @@ struct function_start_pair_hash : typed_noop_remove ref.start_line = ~1U; } + static const bool empty_zero_p = false; + static void mark_empty (function_start &ref) { diff --git a/gcc/graphite.c b/gcc/graphite.c index 0ac46766b15..27f1e486e1f 100644 --- a/gcc/graphite.c +++ b/gcc/graphite.c @@ -233,6 +233,7 @@ struct sese_scev_hash : typed_noop_remove && operand_equal_p (key1.expr, key2.expr, 0)); } static void mark_deleted (seir_cache_key &key) { key.expr = NULL_TREE; } + static const bool empty_zero_p = false; static void mark_empty (seir_cache_key &key) { key.entry_dest = 0; } static bool is_deleted (const seir_cache_key &key) { return !key.expr; } static bool is_empty (const seir_cache_key &key) { return key.entry_dest == 0; } diff --git a/gcc/hash-map-tests.c b/gcc/hash-map-tests.c index 743fb26d571..63574029065 100644 --- a/gcc/hash-map-tests.c +++ b/gcc/hash-map-tests.c @@ -280,6 +280,27 @@ test_map_of_type_with_ctor_and_dtor () } } +/* Test calling empty on a hash_map that has a key type with non-zero + "empty" value. */ + +static void +test_nonzero_empty_key () +{ + typedef int_hash IntHash; + hash_map > x; + + for (int i = 1; i != 32; ++i) + x.put (i, i); + + ASSERT_EQ (x.get (0), NULL); + ASSERT_EQ (*x.get (1), 1); + + x.empty (); + + ASSERT_EQ (x.get (0), NULL); + ASSERT_EQ (x.get (1), NULL); +} + /* Run all of the selftests within this file. */ void @@ -288,6 +309,7 @@ hash_map_tests_c_tests () test_map_of_strings_to_int (); test_map_of_int_to_strings (); test_map_of_type_with_ctor_and_dtor (); + test_nonzero_empty_key (); } } // namespace selftest diff --git a/gcc/hash-map-traits.h b/gcc/hash-map-traits.h index 4764380b364..3b16be35f7d 100644 --- a/gcc/hash-map-traits.h +++ b/gcc/hash-map-traits.h @@ -36,6 +36,7 @@ struct simple_hashmap_traits static inline hashval_t hash (const key_type &); static inline bool equal_keys (const key_type &, const key_type &); template static inline void remove (T &); + static const bool empty_zero_p = H::empty_zero_p; template static inline bool is_empty (const T &); template static inline bool is_deleted (const T &); template static inline void mark_empty (T &); @@ -113,6 +114,7 @@ template struct unbounded_hashmap_traits { template static inline void remove (T &); + static const bool empty_zero_p = default_hash_traits ::empty_zero_p; template static inline bool is_empty (const T &); template static inline bool is_deleted (const T &); template static inline void mark_empty (T &); diff --git a/gcc/hash-map.h b/gcc/hash-map.h index 7cb466767ea..5b8fd184e32 100644 --- a/gcc/hash-map.h +++ b/gcc/hash-map.h @@ -66,6 +66,7 @@ class GTY((user)) hash_map return Traits::is_deleted (e); } + static const bool empty_zero_p = Traits::empty_zero_p; static void mark_empty (hash_entry &e) { Traits::mark_empty (e); } static bool is_empty (const hash_entry &e) { return Traits::is_empty (e); } diff --git a/gcc/hash-set-tests.c b/gcc/hash-set-tests.c index 696e35e9be0..bb32094be20 100644 --- a/gcc/hash-set-tests.c +++ b/gcc/hash-set-tests.c @@ -199,6 +199,8 @@ struct value_hash_traits: int_hash base_type::mark_deleted (v.val); } + static const bool empty_zero_p = false; + static void mark_empty (value_type &v) { base_type::mark_empty (v.val); diff --git a/gcc/hash-table.h b/gcc/hash-table.h index e0ddac5f578..a1423c78112 100644 --- a/gcc/hash-table.h +++ b/gcc/hash-table.h @@ -713,8 +713,9 @@ hash_table (n PASS_MEM_STAT); gcc_assert (nentries != NULL); - for (size_t i = 0; i < n; i++) - mark_empty (nentries[i]); + if (!Descriptor::empty_zero_p) + for (size_t i = 0; i < n; i++) + mark_empty (nentries[i]); return nentries; } @@ -867,8 +868,11 @@ hash_table::empty_slow () m_size = nsize; m_size_prime_index = nindex; } - else + else if (Descriptor::empty_zero_p) memset ((void *) entries, 0, size * sizeof (value_type)); + else + for (size_t i = 0; i < size; i++) + mark_empty (entries[i]); m_n_deleted = 0; m_n_elements = 0; diff --git a/gcc/hash-traits.h b/gcc/hash-traits.h index d259a41a418..3bca74c56ea 100644 --- a/gcc/hash-traits.h +++ b/gcc/hash-traits.h @@ -88,6 +88,7 @@ struct int_hash : typed_noop_remove static inline hashval_t hash (value_type); static inline bool equal (value_type existing, value_type candidate); static inline void mark_deleted (Type &); + static const bool empty_zero_p = Empty == 0; static inline void mark_empty (Type &); static inline bool is_deleted (Type); static inline bool is_empty (Type); @@ -150,6 +151,7 @@ struct pointer_hash static inline bool equal (const value_type &existing, const compare_type &candidate); static inline void mark_deleted (Type *&); + static const bool empty_zero_p = true; static inline void mark_empty (Type *&); static inline bool is_deleted (Type *); static inline bool is_empty (Type *); @@ -323,6 +325,7 @@ struct pair_hash static inline bool equal (const value_type &, const compare_type &); static inline void remove (value_type &); static inline void mark_deleted (value_type &); + static const bool empty_zero_p = T1::empty_zero_p; static inline void mark_empty (value_type &); static inline bool is_deleted (const value_type &); static inline bool is_empty (const value_type &); diff --git a/gcc/ipa-devirt.c b/gcc/ipa-devirt.c index b888186134c..f0031957375 100644 --- a/gcc/ipa-devirt.c +++ b/gcc/ipa-devirt.c @@ -150,6 +150,7 @@ struct default_hash_traits { return TYPE_UID (p.first) ^ TYPE_UID (p.second); } + static const bool empty_zero_p = true; static bool is_empty (type_pair p) { diff --git a/gcc/ipa-prop.c b/gcc/ipa-prop.c index 6dc3cf6b355..12cdb95cf2a 100644 --- a/gcc/ipa-prop.c +++ b/gcc/ipa-prop.c @@ -78,6 +78,7 @@ struct ipa_bit_ggc_hash_traits : public ggc_cache_remove { return a->value == b->value && a->mask == b->mask; } + static const bool empty_zero_p = true; static void mark_empty (ipa_bits *&p) { @@ -123,6 +124,7 @@ struct ipa_vr_ggc_hash_traits : public ggc_cache_remove { return a->equal_p (*b); } + static const bool empty_zero_p = true; static void mark_empty (value_range *&p) { diff --git a/gcc/profile.c b/gcc/profile.c index e124dc6173a..6a2de21c3bd 100644 --- a/gcc/profile.c +++ b/gcc/profile.c @@ -932,6 +932,8 @@ struct location_triplet_hash : typed_noop_remove ref.lineno = -1; } + static const bool empty_zero_p = false; + static void mark_empty (location_triplet &ref) { diff --git a/gcc/sanopt.c b/gcc/sanopt.c index 8a29abe99e2..619aae45a15 100644 --- a/gcc/sanopt.c +++ b/gcc/sanopt.c @@ -129,6 +129,8 @@ struct sanopt_tree_triplet_hash : typed_noop_remove ref.t1 = reinterpret_cast (1); } + static const bool empty_zero_p = true; + static void mark_empty (sanopt_tree_triplet &ref) { @@ -184,6 +186,8 @@ struct sanopt_tree_couple_hash : typed_noop_remove ref.ptr = reinterpret_cast (1); } + static const bool empty_zero_p = true; + static void mark_empty (sanopt_tree_couple &ref) { diff --git a/gcc/tree-hasher.h b/gcc/tree-hasher.h index 787d1ad6a62..9194d6227a2 100644 --- a/gcc/tree-hasher.h +++ b/gcc/tree-hasher.h @@ -40,6 +40,7 @@ struct int_tree_hasher } static void mark_deleted (value_type &v) { v.to = reinterpret_cast (0x1); } static bool is_empty (const value_type &v) { return v.to == NULL; } + static const bool empty_zero_p = true; static void mark_empty (value_type &v) { v.to = NULL; } static void remove (value_type &) {} }; diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c index 6f6b19eb165..3b27c50ef75 100644 --- a/gcc/tree-ssa-sccvn.c +++ b/gcc/tree-ssa-sccvn.c @@ -335,6 +335,7 @@ struct vn_ssa_aux_hasher : typed_noop_remove static inline hashval_t hash (const value_type &); static inline bool equal (const value_type &, const compare_type &); static inline void mark_deleted (value_type &) {} + static const bool empty_zero_p = true; static inline void mark_empty (value_type &e) { e = NULL; } static inline bool is_deleted (value_type &) { return false; } static inline bool is_empty (value_type &e) { return e == NULL; } diff --git a/gcc/tree-vect-slp.c b/gcc/tree-vect-slp.c index 9cb724b95ae..d164937b4b0 100644 --- a/gcc/tree-vect-slp.c +++ b/gcc/tree-vect-slp.c @@ -1193,6 +1193,7 @@ struct bst_traits static inline bool equal (value_type existing, value_type candidate); static inline bool is_empty (value_type x) { return !x.exists (); } static inline bool is_deleted (value_type x) { return !x.exists (); } + static const bool empty_zero_p = true; static inline void mark_empty (value_type &x) { x.release (); } static inline void mark_deleted (value_type &x) { x.release (); } static inline void remove (value_type &x) { x.release (); } diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h index 375fba28d20..ed7fcb0b825 100644 --- a/gcc/tree-vectorizer.h +++ b/gcc/tree-vectorizer.h @@ -232,6 +232,8 @@ struct default_hash_traits && operand_equal_p (existing.op1, candidate.op1, 0)); } + static const bool empty_zero_p = true; + static inline void mark_empty (value_type &v) { -- 2.30.2