On Tue, 2020-01-14 at 00:26 +0100, Jakub Jelinek wrote:
> On Mon, Jan 13, 2020 at 11:56:14PM +0100, Jakub Jelinek wrote:
> > > Some options:
> > > (a) the patch to fix hash_table::empty, and the analyzer kit
> > > (b) the analyzer kit with the following kludge
> > > (c) someone with better C++-fu than me figure out a way to get
> > > the
> > > memset optimization for hash_map with 0-valued empty (or to give
> > > me
> > > some suggestions)
> > > (d) not merge the analyzer for gcc 10
> >
> > For (c), I see right now we have 37 mark_empty definitions:
> > find -type f | grep -v 'testsuite/\|ChangeLog' | xargs grep
> > mark_empty | wc -l
> > 37
> > > From quick skimming of them, most of them are just zeroing one or
> > > more
> > fields, exceptions are profile.c, attribs.c (this one only in self-
> > tests
> > and it is unclear why deleted is two NULLs and empty two ""s rather
> > than
> > vice versa), and gcov.c. Also, int_hash can be zero or non-zero,
> > depending
> > on template argument, e.g.
> > typedef hash_map<int_hash <unsigned int, -1U>, unsigned int>
> > live_vars_map;
> > struct uid_hash : int_hash <int, -1, -2> {};
> > are not either.
> > Can't we add next to the mark_empty and is_empty methods also a
> > static const
> > bool data member empty_zero_p or similar and use it in in the two
> > hash-table.h spots where this would make a difference?
> > In alloc_entries the
> > for (size_t i = 0; i < n; i++)
> > mark_empty (nentries[i]);
> > loop could be conditionalized on !Descriptor::empty_zero_p because
> > both
> > allocation paths actually allocate cleared memory, and in the spot
> > you are talking about.
>
> Just as a proof of concept, the following compiles (but haven't done
> any
> testing beoyond that, not even looked if/when the memcpy vs. loop is
> in
> there), the formatting/placement of the static data members could be
> adjusted, in graphite.c I just gave up (it is weird, empty is when
> one field
> is NULL, deleted when another field is NULL, but what is zeroed
> memory, is
> that both empty and deleted at the same time?).
Thanks. Does it have warnings, though?
My attempt was similar, but ran into warnings from -Wclass-memaccess in
four places, like this:
../../src/gcc/hash-map-traits.h:102:12: warning: ‘void* memset(void*,
int, size_t)’ clearing an object of type ‘struct hash_map<tree_node*,
std::pair<tree_node*, tree_node*> >::hash_entry’ with no trivial copy-
assignment; use assignment or value-initialization instead [-Wclass-
memaccess]
102 | memset (entry, 0, sizeof (T) * count);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
where the types in question are:
(1)
struct hash_map<tree_node*, std::pair<tree_node*, tree_node*>
>::hash_entry
../../src/gcc/tree-data-ref.c:844:17: required from here
(2)
struct hash_map<tree_node*, std::pair<int, unsigned int>
>::hash_entry
../../src/gcc/tree-ssa-strlen.c:5925:32: required from here
(3)
struct hash_map<edge_def*, auto_vec<edge_var_map> >::hash_entry
../../src/gcc/tree-ssa.c:130:27: required from here
(4)
struct hash_map<tree_decl_hash, class_decl_loc_t>::hash_entry
../../src/gcc/cp/parser.c:31073:20: required from here
I tried to use std::is_pod, but got stuck.
Dave
>
> 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<excl_pair>
> 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/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 98572bdbad1..c3ca4c8dace 100644
> --- a/gcc/cp/cp-tree.h
> +++ b/gcc/cp/cp-tree.h
> @@ -900,6 +900,7 @@ struct named_decl_hash : ggc_remove <tree>
> 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
> <named_label_entry *>
> 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 <tree>
> 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 <function_start>
> 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
> <seir_cache_key>
> && 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-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 <typename T> static inline void remove (T &);
> + static const bool empty_zero_p = H::empty_zero_p;
> template <typename T> static inline bool is_empty (const T &);
> template <typename T> static inline bool is_deleted (const T &);
> template <typename T> static inline void mark_empty (T &);
> @@ -113,6 +114,7 @@ template <typename Value>
> struct unbounded_hashmap_traits
> {
> template <typename T> static inline void remove (T &);
> + static const bool empty_zero_p = default_hash_traits
> <Value>::empty_zero_p;
> template <typename T> static inline bool is_empty (const T &);
> template <typename T> static inline bool is_deleted (const T &);
> template <typename T> 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<int, -1, -2>
> 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<Descriptor, Lazy,
> nentries = ::ggc_cleared_vec_alloc<value_type> (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<Descriptor, Lazy,
> Allocator>::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 <Type>
> 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 <type_pair>
> {
> 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 <ipa_bits *>
> {
> 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 <value_range *>
> {
> 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
> <location_triplet>
> 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 <sanopt_tree_triplet>
> ref.t1 = reinterpret_cast<tree> (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 <sanopt_tree_couple>
> ref.ptr = reinterpret_cast<tree> (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<tree> (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
> <vn_ssa_aux_t>
> 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<scalar_cond_masked_key>
> && operand_equal_p (existing.op1, candidate.op1, 0));
> }
>
> + static const bool empty_zero_p = true;
> +
> static inline void
> mark_empty (value_type &v)
> {
>
>
> Jakub
