Analyzer status

Analyzer status

[David Malcolm]

I posted the initial version of the analyzer patch kit on 2019-11-15,
shortly before the close of stage 1.

Jeff reviewed (most of) the latest version of the kit on Friday, and
said:

> I'm not going to have time to finish #22 or #37 -- hell, I'm not even
> supposed to be working today :-)
> 
> I'd suggest committing now and we can iterate on any issues.  The code
> is appropriately conditionalized, so it shouldn't affect anyone that
> doesn't ask for it and it was submitted prior to stage1 close.
> 
> I would also suggest that we have a fairly loose policy for these bits
> right now.  Again, they're conditionally compiled and it's effectively
> "tech preview", so if we muck something up, the after-effects are
> relatively small.

Unfortunately, I didn't resolve the hash_table/hash_map issue
referred to here:
  https://gcc.gnu.org/ml/gcc-patches/2019-12/msg00734.html
where r279139 on 2019-12-09 introduced the assumption that empty
hash_table entries and empty hash_map keys are all zeroes.

The analyzer uses hash_map::empty in a single place with a hash_map
where the "empty" key value is all-ones.

Unfortunately, without a fix for this issue, the analyzer can hang,
leading to DejaGnu hanging, which I clearly don't want to push to
master as-is.

The patch here fixes the issue:
  https://gcc.gnu.org/ml/gcc-patches/2019-12/msg00776.html
but Jakub has expressed concern about the effect on code generated
for the compiler.

As noted here:
  https://gcc.gnu.org/ml/gcc-patches/2020-01/msg00651.html
gcc successfully converts this back to a memset to 0 for hash_table
at -O2, but not for hash_map, since it can't "know" that it's OK to
clobber the values as well as the keys; it instead generates a loop
that zeroes the keys without touching the values.

I've been experimenting with adding template specializations to try
to allow for memset to 0 for hash_map, but haven't been successful
(e.g. std::is_pod is C++11-only); my closest attempt so far is at:
  https://dmalcolm.fedorapeople.org/gcc/2020-01-13/0001-FIXME-experiments-with-fixing-hash_map-empty.patch
which at least expresses the memset to 0 without needing
optimization for hash_table of *pointer* types, but I wasn't able to
do the same for hash_map, today at least.

If the hash_map::empty patch is unacceptable, I've also successfully
B&R-ed the following kludge to the analyzer, which avoids using
hash_map::empty at the single place where it's problematic.  This
kludge is entirely confined to the analyzer.

I'd like to get the analyzer code into gcc 10, but I appreciate it's
now stage 4.  Jakub suggested on IRC that with approval before the
end of stage 3 (which it was), there may be some flexibility if we
get it in soon and I take steps to minimize disruption.

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

My preferred approach is option (a), but option (b) is confined to
the analyzer.

Thoughts?

I also have a series of followup patches to the analyzer (and
diagnostic subsystem, for diagnostic_path-handling) to fix bugs
found since I posted the kit, which I've been posting to gcc-patches
since November with an "analyzer: " prefix in the subject line.
I wonder if it's OK for me to take Jeff's message about "fairly
loose policy" above as blanket pre-approval to make bug fixes to the
analyzer subdirectory?

(See also:
  https://gcc.gnu.org/wiki/DavidMalcolm/StaticAnalyzer )

Here's the analyzer-specific kludge for the hash_map::empty issue:

---
 gcc/analyzer/program-state.cc | 12 ++++++++++++
 1 file changed, 12 insertions(+)

diff --git a/gcc/analyzer/program-state.cc b/gcc/analyzer/program-state.cc
index 04346ae9dc8..4c6c82cdf5d 100644
--- a/gcc/analyzer/program-state.cc
+++ b/gcc/analyzer/program-state.cc
@@ -405,7 +405,19 @@ sm_state_map::remap_svalue_ids (const svalue_id_map &map)
     }
 
   /* Clear the existing values.  */
+  /* FIXME: hash_map::empty and hash_table::empty make the assumption that
+     the empty value for the key is all zeroes, which isn't the case for
+     this hash_map.  See
+       https://gcc.gnu.org/ml/gcc-patches/2019-12/msg00776.html
+     and
+       https://gcc.gnu.org/ml/gcc-patches/2020-01/msg00651.html  */
+#if 0
   m_map.empty ();
+#else
+  /* Workaround: manually remove each element.  */
+  while (!m_map.is_empty ())
+    m_map.remove ((*m_map.begin ()).first);
+#endif
 
   /* Copy over from intermediate map.  */
   for (typename map_t::iterator iter = tmp_map.begin ();
-- 
2.21.0

Re: Analyzer status

[Jakub Jelinek]

On Mon, Jan 13, 2020 at 05:10:24PM -0500, David Malcolm wrote:
> Unfortunately, I didn't resolve the hash_table/hash_map issue
> referred to here:
>   https://gcc.gnu.org/ml/gcc-patches/2019-12/msg00734.html
> where r279139 on 2019-12-09 introduced the assumption that empty
> hash_table entries and empty hash_map keys are all zeroes.
> 
> The analyzer uses hash_map::empty in a single place with a hash_map
> where the "empty" key value is all-ones.
> 
> Unfortunately, without a fix for this issue, the analyzer can hang,
> leading to DejaGnu hanging, which I clearly don't want to push to
> master as-is.
> 
> The patch here fixes the issue:
>   https://gcc.gnu.org/ml/gcc-patches/2019-12/msg00776.html
> but Jakub has expressed concern about the effect on code generated
> for the compiler.
> 
> As noted here:
>   https://gcc.gnu.org/ml/gcc-patches/2020-01/msg00651.html
> gcc successfully converts this back to a memset to 0 for hash_table
> at -O2, but not for hash_map, since it can't "know" that it's OK to
> clobber the values as well as the keys; it instead generates a loop
> that zeroes the keys without touching the values.

I guess in some cases the loop could be better (e.g. if the values are
large and/or keys too and mark_empty only sets something small), but I bet
in most cases the memset will be better.

> 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.

Or isn't there (e), tweak whatever hash_table traits you use so that
empty case is all zeros?

	Jakub

Re: Analyzer status

[Jakub Jelinek]

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?).

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

Re: Analyzer status

[David Malcolm]

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

Re: Analyzer status

[Jakub Jelinek]

On Mon, Jan 13, 2020 at 06:42:06PM -0500, David Malcolm wrote:
> 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

I don't understand how there could be new warnings.
The patch doesn't add any new memsets, all it does is if (0) code in
alloc_entries for certain traits and in empty_slow stops using memset
for some traits and uses mark_empty loop there instead.
This was non-bootstrapped build, but I didn't see new warnings in there,
and for tree-data-ref.c which you've mentioned I've tried to compile
with installed trunk compiler and didn't get any warnings either.

	Jakub

Re: Analyzer status

[David Malcolm]

On Tue, 2020-01-14 at 00:55 +0100, Jakub Jelinek wrote:
> On Mon, Jan 13, 2020 at 06:42:06PM -0500, David Malcolm wrote:
> > 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
> 
> I don't understand how there could be new warnings.
> The patch doesn't add any new memsets, all it does is if (0) code in
> alloc_entries for certain traits and in empty_slow stops using memset
> for some traits and uses mark_empty loop there instead.

Your patch didn't add new memsets; mine did - clearly I misspoke when
saying they were similar, mine had a somewhat different approach.

Sorry for the noise, and thanks for your patch.

I've extended your patch to cover the various hash traits in the
analyzer and it passes the analyzer's tests.  I also added in the
selftests from my older patch.

I examined the generated code, and it seems correct:

* cfg.s correctly has a call to memset (even with no optimization) for
hash_table<bb_copy_hasher>::empty_slow

* the hash_map example with nonzero empty for the analyzer:
analyzer/program-state.s: sm_state_map::remap_svalue_ids:   hash_map
<svalue_id, entry_t> map_t; correctly shows a loop of calls to
mark_empty

* a hash_map example with zero empty: tree-ssa.s edge_var_maps
correctly has a memset in the empty_slow, even with no optimization.

...which is promising.


For the graphite case, I wondered what happens if both is_empty and
is_deleted are true; looking at hash-table.h, sometimes one is checked
first, sometimes the other, but I don't think it matters for this
case:; you have empty_zero_p = false,so it uses mark_empty, rather than
trying to memset, which is correct - empty_zero_p being true can be
thought of as a "it is safe to optimize this hash_table/hash_map by
treating empty slots as all zero", if you will.


I'm trying a bootstrap build and full regression suite now, for all
languages (with graphite enabled, I believe).  Will post the patches if
it succeeds...

> This was non-bootstrapped build, but I didn't see new warnings in
> there,
> and for tree-data-ref.c which you've mentioned I've tried to compile
> with installed trunk compiler and didn't get any warnings either.
> 
> 	Jakub

Thanks!  Sorry again about getting this wrong.

Dave

[PATCH 1/2] hash-table.h: support non-zero empty values in empty_slow (v2)

[David Malcolm]

On Mon, 2020-01-13 at 21:58 -0500, David Malcolm wrote:
> On Tue, 2020-01-14 at 00:55 +0100, Jakub Jelinek wrote:
> > On Mon, Jan 13, 2020 at 06:42:06PM -0500, David Malcolm wrote:
> > > 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
> > 
> > I don't understand how there could be new warnings.
> > The patch doesn't add any new memsets, all it does is if (0) code
> > in
> > alloc_entries for certain traits and in empty_slow stops using
> > memset
> > for some traits and uses mark_empty loop there instead.
> 
> Your patch didn't add new memsets; mine did - clearly I misspoke when
> saying they were similar, mine had a somewhat different approach.
> 
> Sorry for the noise, and thanks for your patch.
> 
> I've extended your patch to cover the various hash traits in the
> analyzer and it passes the analyzer's tests.  I also added in the
> selftests from my older patch.
> 
> I examined the generated code, and it seems correct:
> 
> * cfg.s correctly has a call to memset (even with no optimization)
> for
> hash_table<bb_copy_hasher>::empty_slow
> 
> * the hash_map example with nonzero empty for the analyzer:
> analyzer/program-state.s: sm_state_map::remap_svalue_ids:   hash_map
> <svalue_id, entry_t> map_t; correctly shows a loop of calls to
> mark_empty
> 
> * a hash_map example with zero empty: tree-ssa.s edge_var_maps
> correctly has a memset in the empty_slow, even with no optimization.
> 
> ...which is promising.
> 
> 
> For the graphite case, I wondered what happens if both is_empty and
> is_deleted are true; looking at hash-table.h, sometimes one is
> checked
> first, sometimes the other, but I don't think it matters for this
> case:; you have empty_zero_p = false,so it uses mark_empty, rather
> than
> trying to memset, which is correct - empty_zero_p being true can be
> thought of as a "it is safe to optimize this hash_table/hash_map by
> treating empty slots as all zero", if you will.
> 
> 
> I'm trying a bootstrap build and full regression suite now, for all
> languages (with graphite enabled, I believe).  Will post the patches
> if
> it succeeds...
> 
> > This was non-bootstrapped build, but I didn't see new warnings in
> > there,
> > and for tree-data-ref.c which you've mentioned I've tried to
> > compile
> > with installed trunk compiler and didn't get any warnings either.
> > 
> >        Jakub
> 
> Thanks!  Sorry again about getting this wrong.
> 
> Dave

Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu (in
conjuction with the analyzer patch kit, which it fixes)

OK for master?

gcc/cp/ChangeLog:  Jakub Jelinek  <jakub@redhat.com>
	* 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:  Jakub Jelinek  <jakub@redhat.com>,
		David Malcolm  <dmalcolm@redhat.com>
	* 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 <Value>.
	* 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 <type_pair>::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<scalar_cond_masked_key>::empty_zero_p):
	Likewise.
---
 gcc/attribs.c         |  2 ++
 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 ++
 20 files changed, 61 insertions(+), 3 deletions(-)

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 827d240d11a..f401fe93fea 100644
--- a/gcc/cp/cp-gimplify.c
+++ b/gcc/cp/cp-gimplify.c
@@ -3043,6 +3043,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-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<int, INT_MIN, INT_MAX> IntHash;
+  hash_map<int, int, simple_hashmap_traits<IntHash, int> > 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 <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 ddb3c9b21bc..d90cdf24454 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 68cf96f6766..361f9a0741a 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)
   {
-- 
2.21.0

[PATCH 2/2] analyzer: add empty_zero_p for the various hash traits

[David Malcolm]

Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu

OK for master?

gcc/analyzer/ChangeLog:
	* diagnostic-manager.cc (dedupe_hash_map_traits::empty_zero_p):
	New static constant.
	* engine.cc
	(default_hash_traits<function_call_string>::empty_zero_p): Likewise.
	* exploded-graph.h (eg_hash_map_traits::empty_zero_p): Likewise.
	(eg_point_hash_map_traits::empty_zero_p): Likewise.
	(eg_call_string_hash_map_traits::empty_zero_p): Likewise.
	* program-state.h (default_hash_traits<svalue_id>::empty_zero_p):
	Likewise.
	* state-purge.h
	(default_hash_traits<function_point>::empty_zero_p): Likewise.
---
 gcc/analyzer/diagnostic-manager.cc | 2 +-
 gcc/analyzer/engine.cc             | 1 +
 gcc/analyzer/exploded-graph.h      | 3 +++
 gcc/analyzer/program-state.h       | 1 +
 gcc/analyzer/state-purge.h         | 1 +
 5 files changed, 7 insertions(+), 1 deletion(-)

diff --git a/gcc/analyzer/diagnostic-manager.cc b/gcc/analyzer/diagnostic-manager.cc
index 12b8e5a4ac4..cd2c3bf2076 100644
--- a/gcc/analyzer/diagnostic-manager.cc
+++ b/gcc/analyzer/diagnostic-manager.cc
@@ -265,7 +265,7 @@ public:
   {
     return entry.m_key == NULL;
   }
-
+  static const bool empty_zero_p = true;
 };
 
 /* A class for deduplicating diagnostics and finding (and emitting) the
diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc
index 3e3d8a120b7..720fa219d16 100644
--- a/gcc/analyzer/engine.cc
+++ b/gcc/analyzer/engine.cc
@@ -2913,6 +2913,7 @@ struct function_call_string
 template <> struct default_hash_traits<function_call_string>
 : public pod_hash_traits<function_call_string>
 {
+  static const bool empty_zero_p = false;
 };
 
 template <>
diff --git a/gcc/analyzer/exploded-graph.h b/gcc/analyzer/exploded-graph.h
index ddc5e06b3b6..8c29e552cac 100644
--- a/gcc/analyzer/exploded-graph.h
+++ b/gcc/analyzer/exploded-graph.h
@@ -407,6 +407,7 @@ struct eg_hash_map_traits
   {
     return entry.m_key == NULL;
   }
+  static const bool empty_zero_p = false;
 };
 
 /* Per-program_point data for an exploded_graph.  */
@@ -473,6 +474,7 @@ struct eg_point_hash_map_traits
   {
     return entry.m_key == NULL;
   }
+  static const bool empty_zero_p = false;
 };
 
 /* Data about a particular call_string within an exploded_graph.  */
@@ -539,6 +541,7 @@ struct eg_call_string_hash_map_traits
   {
     return entry.m_key == NULL;
   }
+  static const bool empty_zero_p = false;
 };
 
 /* Data about a particular function within an exploded_graph.  */
diff --git a/gcc/analyzer/program-state.h b/gcc/analyzer/program-state.h
index 37fb7cc4101..75b65b780c9 100644
--- a/gcc/analyzer/program-state.h
+++ b/gcc/analyzer/program-state.h
@@ -50,6 +50,7 @@ public:
 template <> struct default_hash_traits<svalue_id>
 : public pod_hash_traits<svalue_id>
 {
+  static const bool empty_zero_p = false;
 };
 
 template <>
diff --git a/gcc/analyzer/state-purge.h b/gcc/analyzer/state-purge.h
index 77b7f622bbd..e33733a6cc5 100644
--- a/gcc/analyzer/state-purge.h
+++ b/gcc/analyzer/state-purge.h
@@ -26,6 +26,7 @@ along with GCC; see the file COPYING3.  If not see
 template <> struct default_hash_traits<function_point>
 : public pod_hash_traits<function_point>
 {
+  static const bool empty_zero_p = false;
 };
 
 template <>
-- 
2.21.0

Re: [PATCH 1/2] hash-table.h: support non-zero empty values in empty_slow (v2)

[Jakub Jelinek]

On Mon, Jan 13, 2020 at 11:51:53PM -0500, David Malcolm wrote:
> > * cfg.s correctly has a call to memset (even with no optimization)
> > for
> > hash_table<bb_copy_hasher>::empty_slow

I have intestigated unpatched cc1plus and in the (usually inlined)
alloc_entries I see in all the places the xcalloc or ggc_internal_cleared_alloc
followed by either a loop storing some zeros or a memset, which is something
I'd hope the patch also improves.

As for graphite.c, sure, empty_zero_p = false is a fallback value, the
question was not directly related to this patch, but rather wondering how it
can work at all.

> Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu (in
> conjuction with the analyzer patch kit, which it fixes)
> 
> OK for master?

Yes to both patches, thanks.

> gcc/cp/ChangeLog:  Jakub Jelinek  <jakub@redhat.com>
> 	* 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:  Jakub Jelinek  <jakub@redhat.com>,
> 		David Malcolm  <dmalcolm@redhat.com>
> 	* 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 <Value>.
> 	* 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 <type_pair>::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<scalar_cond_masked_key>::empty_zero_p):
> 	Likewise.

	Jakub

Re: [PATCH 1/2] hash-table.h: support non-zero empty values in empty_slow (v2)

[David Malcolm]

On Tue, 2020-01-14 at 11:02 +0100, Jakub Jelinek wrote:
> On Mon, Jan 13, 2020 at 11:51:53PM -0500, David Malcolm wrote:
> > > * cfg.s correctly has a call to memset (even with no
> > > optimization)
> > > for
> > > hash_table<bb_copy_hasher>::empty_slow
> 
> I have intestigated unpatched cc1plus and in the (usually inlined)
> alloc_entries I see in all the places the xcalloc or
> ggc_internal_cleared_alloc
> followed by either a loop storing some zeros or a memset, which is
> something
> I'd hope the patch also improves.

It does: I looked at tree-ssa.s, at the alloc_entries code generated
for:
   static hash_map<edge, auto_vec<edge_var_map> > *edge_var_maps;

In an unoptimized build:
  Before the patch I see the loop in the .s calling mark_empty after
the calls to data_alloc and ggc_cleared_vec_alloc; 
  After the patch there's no longer that loop in the generated .s

With -O2 it's harder to follow as the ctor gets inlined into
redirect_edge_var_map_add, but:
  Before the patch there's a loop that's zeroing the keys after the
call to ggc_internal_cleared_alloc
  After the patch that loop isn't present.

> As for graphite.c, sure, empty_zero_p = false is a fallback value,
> the
> question was not directly related to this patch, but rather wondering
> how it
> can work at all.
> 
> > Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu (in
> > conjuction with the analyzer patch kit, which it fixes)
> > 
> > OK for master?
> 
> Yes to both patches, thanks.

Thanks.  I rebased and did another bootstrap&regression test with just
patch 1 to be sure.  I've pushed it to master as
7ca50de02cf12c759f4f8daf60913704782b7d45.


I've rebased and squashed the analyzer patch kit and squashed patch 2
into it, and am re-testing it now.

Dave

Re: Analyzer status

[Richard Biener]

[-- Attachment #1: Type: text/plain, Size: 5488 bytes --]

On Mon, 13 Jan 2020, David Malcolm wrote:

> I posted the initial version of the analyzer patch kit on 2019-11-15,
> shortly before the close of stage 1.
> 
> Jeff reviewed (most of) the latest version of the kit on Friday, and
> said:
> 
> > I'm not going to have time to finish #22 or #37 -- hell, I'm not even
> > supposed to be working today :-)
> > 
> > I'd suggest committing now and we can iterate on any issues.  The code
> > is appropriately conditionalized, so it shouldn't affect anyone that
> > doesn't ask for it and it was submitted prior to stage1 close.
> > 
> > I would also suggest that we have a fairly loose policy for these bits
> > right now.  Again, they're conditionally compiled and it's effectively
> > "tech preview", so if we muck something up, the after-effects are
> > relatively small.
> 
> Unfortunately, I didn't resolve the hash_table/hash_map issue
> referred to here:
>   https://gcc.gnu.org/ml/gcc-patches/2019-12/msg00734.html
> where r279139 on 2019-12-09 introduced the assumption that empty
> hash_table entries and empty hash_map keys are all zeroes.
> 
> The analyzer uses hash_map::empty in a single place with a hash_map
> where the "empty" key value is all-ones.
> 
> Unfortunately, without a fix for this issue, the analyzer can hang,
> leading to DejaGnu hanging, which I clearly don't want to push to
> master as-is.
> 
> The patch here fixes the issue:
>   https://gcc.gnu.org/ml/gcc-patches/2019-12/msg00776.html
> but Jakub has expressed concern about the effect on code generated
> for the compiler.
> 
> As noted here:
>   https://gcc.gnu.org/ml/gcc-patches/2020-01/msg00651.html
> gcc successfully converts this back to a memset to 0 for hash_table
> at -O2, but not for hash_map, since it can't "know" that it's OK to
> clobber the values as well as the keys; it instead generates a loop
> that zeroes the keys without touching the values.
> 
> I've been experimenting with adding template specializations to try
> to allow for memset to 0 for hash_map, but haven't been successful
> (e.g. std::is_pod is C++11-only); my closest attempt so far is at:
>   https://dmalcolm.fedorapeople.org/gcc/2020-01-13/0001-FIXME-experiments-with-fixing-hash_map-empty.patch
> which at least expresses the memset to 0 without needing
> optimization for hash_table of *pointer* types, but I wasn't able to
> do the same for hash_map, today at least.
> 
> If the hash_map::empty patch is unacceptable, I've also successfully
> B&R-ed the following kludge to the analyzer, which avoids using
> hash_map::empty at the single place where it's problematic.  This
> kludge is entirely confined to the analyzer.
> 
> I'd like to get the analyzer code into gcc 10, but I appreciate it's
> now stage 4.  Jakub suggested on IRC that with approval before the
> end of stage 3 (which it was), there may be some flexibility if we
> get it in soon and I take steps to minimize disruption.
> 
> 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
> 
> My preferred approach is option (a), but option (b) is confined to
> the analyzer.
> 
> Thoughts?

(b)

we can iterate on (a)/(c) if deemed necessary but also this can be done
during next stage1.

> I also have a series of followup patches to the analyzer (and
> diagnostic subsystem, for diagnostic_path-handling) to fix bugs
> found since I posted the kit, which I've been posting to gcc-patches
> since November with an "analyzer: " prefix in the subject line.
> I wonder if it's OK for me to take Jeff's message about "fairly
> loose policy" above as blanket pre-approval to make bug fixes to the
> analyzer subdirectory?

If the analyzer is defaulted to be disabled at compile-time then
changes cannot disrupt anything release critical.  In that case
I'd be fine with you mucking at will inside analyzer/ with your
own risk ask shipping something unusable.

Richard.

> (See also:
>   https://gcc.gnu.org/wiki/DavidMalcolm/StaticAnalyzer )
> 
> Here's the analyzer-specific kludge for the hash_map::empty issue:
> 
> ---
>  gcc/analyzer/program-state.cc | 12 ++++++++++++
>  1 file changed, 12 insertions(+)
> 
> diff --git a/gcc/analyzer/program-state.cc b/gcc/analyzer/program-state.cc
> index 04346ae9dc8..4c6c82cdf5d 100644
> --- a/gcc/analyzer/program-state.cc
> +++ b/gcc/analyzer/program-state.cc
> @@ -405,7 +405,19 @@ sm_state_map::remap_svalue_ids (const svalue_id_map &map)
>      }
>  
>    /* Clear the existing values.  */
> +  /* FIXME: hash_map::empty and hash_table::empty make the assumption that
> +     the empty value for the key is all zeroes, which isn't the case for
> +     this hash_map.  See
> +       https://gcc.gnu.org/ml/gcc-patches/2019-12/msg00776.html
> +     and
> +       https://gcc.gnu.org/ml/gcc-patches/2020-01/msg00651.html  */
> +#if 0
>    m_map.empty ();
> +#else
> +  /* Workaround: manually remove each element.  */
> +  while (!m_map.is_empty ())
> +    m_map.remove ((*m_map.begin ()).first);
> +#endif
>  
>    /* Copy over from intermediate map.  */
>    for (typename map_t::iterator iter = tmp_map.begin ();
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
Germany; GF: Felix Imendörffer; HRB 36809 (AG Nuernberg)

Analyzer committed to master (was Re: Analyzer status)

[David Malcolm]

On Tue, 2020-01-14 at 08:55 +0100, Richard Biener wrote:
> On Mon, 13 Jan 2020, David Malcolm wrote:
> 
> > I posted the initial version of the analyzer patch kit on 2019-11-
> > 15,
> > shortly before the close of stage 1.
> > 
> > Jeff reviewed (most of) the latest version of the kit on Friday,
> > and
> > said:
> > 
> > > I'm not going to have time to finish #22 or #37 -- hell, I'm not
> > > even
> > > supposed to be working today :-)
> > > 
> > > I'd suggest committing now and we can iterate on any issues.  The
> > > code
> > > is appropriately conditionalized, so it shouldn't affect anyone
> > > that
> > > doesn't ask for it and it was submitted prior to stage1 close.
> > > 
> > > I would also suggest that we have a fairly loose policy for these
> > > bits
> > > right now.  Again, they're conditionally compiled and it's
> > > effectively
> > > "tech preview", so if we muck something up, the after-effects are
> > > relatively small.
> > 
> > Unfortunately, I didn't resolve the hash_table/hash_map issue
> > referred to here:
> >   https://gcc.gnu.org/ml/gcc-patches/2019-12/msg00734.html
> > where r279139 on 2019-12-09 introduced the assumption that empty
> > hash_table entries and empty hash_map keys are all zeroes.
> > 
> > The analyzer uses hash_map::empty in a single place with a hash_map
> > where the "empty" key value is all-ones.
> > 
> > Unfortunately, without a fix for this issue, the analyzer can hang,
> > leading to DejaGnu hanging, which I clearly don't want to push to
> > master as-is.
> > 
> > The patch here fixes the issue:
> >   https://gcc.gnu.org/ml/gcc-patches/2019-12/msg00776.html
> > but Jakub has expressed concern about the effect on code generated
> > for the compiler.
> > 
> > As noted here:
> >   https://gcc.gnu.org/ml/gcc-patches/2020-01/msg00651.html
> > gcc successfully converts this back to a memset to 0 for hash_table
> > at -O2, but not for hash_map, since it can't "know" that it's OK to
> > clobber the values as well as the keys; it instead generates a loop
> > that zeroes the keys without touching the values.
> > 
> > I've been experimenting with adding template specializations to try
> > to allow for memset to 0 for hash_map, but haven't been successful
> > (e.g. std::is_pod is C++11-only); my closest attempt so far is at:
> >   
> > https://dmalcolm.fedorapeople.org/gcc/2020-01-13/0001-FIXME-experiments-with-fixing-hash_map-empty.patch
> > which at least expresses the memset to 0 without needing
> > optimization for hash_table of *pointer* types, but I wasn't able
> > to
> > do the same for hash_map, today at least.
> > 
> > If the hash_map::empty patch is unacceptable, I've also
> > successfully
> > B&R-ed the following kludge to the analyzer, which avoids using
> > hash_map::empty at the single place where it's problematic.  This
> > kludge is entirely confined to the analyzer.
> > 
> > I'd like to get the analyzer code into gcc 10, but I appreciate
> > it's
> > now stage 4.  Jakub suggested on IRC that with approval before the
> > end of stage 3 (which it was), there may be some flexibility if we
> > get it in soon and I take steps to minimize disruption.
> > 
> > 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
> > 
> > My preferred approach is option (a), but option (b) is confined to
> > the analyzer.
> > 
> > Thoughts?
> 
> (b)
> 
> we can iterate on (a)/(c) if deemed necessary but also this can be
> done
> during next stage1.

Thanks.  Jakub's proposed fix worked, so I've effectively gone with
(c).

I've rebased and squashed the analyzer patch kit and squashed patch 2
of the hash_table fix into it, and re-tested it successfully, so I've
pushed it to master (as 757bf1dff5e8cee34c0a75d06140ca972bfecfa7).

I'm going to work through the various followup patches I had on my
branch and re-test and push to master those that seem appropriate.

Dave

Re: Analyzer committed to master (was Re: Analyzer status)

[Rainer Orth]

Hi David,

> I've rebased and squashed the analyzer patch kit and squashed patch 2
> of the hash_table fix into it, and re-tested it successfully, so I've
> pushed it to master (as 757bf1dff5e8cee34c0a75d06140ca972bfecfa7).
>
> I'm going to work through the various followup patches I had on my
> branch and re-test and push to master those that seem appropriate.

I'm seeing quite a number of failures on Solaris (both sparc and x86),
but also some on 32-bit Linux/x86:

 Running target unix/-m32
+FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 610)
+FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 611)
+FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 615)
+FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 616)
+FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 657)
+FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 658)
+FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 662)
+FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 663)
+FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 705)
+FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 706)
+FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 710)
+FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 711)
+FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 753)
+FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 754)
+FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 758)
+FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 759)
+FAIL: gcc.dg/analyzer/data-model-1.c (test for excess errors)

I'll file PRs for the Solaris ones once I get to it.

Wasn't analyzer supposed to be off by default, though?

	Rainer

-- 
-----------------------------------------------------------------------------
Rainer Orth, Center for Biotechnology, Bielefeld University

Re: Analyzer committed to master (was Re: Analyzer status)

[Dimitar Dimitrov]

On Wed, 15.01.2020, 14:30:43 EET Rainer Orth wrote:
> Hi David,
> 
> > I've rebased and squashed the analyzer patch kit and squashed patch 2
> > of the hash_table fix into it, and re-tested it successfully, so I've
> > pushed it to master (as 757bf1dff5e8cee34c0a75d06140ca972bfecfa7).
> > 
> > I'm going to work through the various followup patches I had on my
> > branch and re-test and push to master those that seem appropriate.
> 
> I'm seeing quite a number of failures on Solaris (both sparc and x86),
> but also some on 32-bit Linux/x86:
> 
>  Running target unix/-m32
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 610)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 611)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 615)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 616)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 657)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 658)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 662)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 663)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 705)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 706)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 710)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 711)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 753)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 754)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 758)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 759)
> +FAIL: gcc.dg/analyzer/data-model-1.c (test for excess errors)
> 
I see those errors on PRU and AVR backends.

Regards,
Dimitar

Re: Analyzer committed to master (was Re: Analyzer status)

[Iain Sandoe]

Dimitar Dimitrov <dimitar@dinux.eu> wrote:

> On Wed, 15.01.2020, 14:30:43 EET Rainer Orth wrote:
>> Hi David,
>>
>>> I've rebased and squashed the analyzer patch kit and squashed patch 2
>>> of the hash_table fix into it, and re-tested it successfully, so I've
>>> pushed it to master (as 757bf1dff5e8cee34c0a75d06140ca972bfecfa7).
>>>
>>> I'm going to work through the various followup patches I had on my
>>> branch and re-test and push to master those that seem appropriate.
>>
>> I'm seeing quite a number of failures on Solaris (both sparc and x86),
>> but also some on 32-bit Linux/x86:
>>
>> Running target unix/-m32
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 610)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 611)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 615)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 616)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 657)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 658)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 662)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 663)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 705)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 706)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 710)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 711)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 753)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 754)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 758)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 759)
>> +FAIL: gcc.dg/analyzer/data-model-1.c (test for excess errors)
> I see those errors on PRU and AVR backends.

Likewise, on 32b Darwin host and 32b multilib on 64b hosts.
+ a couple of others related to setjmp
not had a chance to triage any further yet.

cheers
Iain

Re: Analyzer committed to master (was Re: Analyzer status)

[David Malcolm]

On Wed, 2020-01-15 at 13:30 +0100, Rainer Orth wrote:
> Hi David,
> 
> > I've rebased and squashed the analyzer patch kit and squashed patch
> > 2
> > of the hash_table fix into it, and re-tested it successfully, so
> > I've
> > pushed it to master (as 757bf1dff5e8cee34c0a75d06140ca972bfecfa7).
> > 
> > I'm going to work through the various followup patches I had on my
> > branch and re-test and push to master those that seem appropriate.
> 
> I'm seeing quite a number of failures on Solaris (both sparc and
> x86),
> but also some on 32-bit Linux/x86:
> 
>  Running target unix/-m32
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 610)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 611)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 615)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 616)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 657)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 658)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 662)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 663)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 705)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 706)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 710)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 711)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 753)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 754)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 758)
> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 759)
> +FAIL: gcc.dg/analyzer/data-model-1.c (test for excess errors)

Thanks, and sorry about this; I've filed this for myself as:
  https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93281
and have been investigating.

> I'll file PRs for the Solaris ones once I get to it.
> 
> Wasn't analyzer supposed to be off by default, though?

It's configured on by default but can be disabled with --disable-
analyzer.

It doesn't *run* by default; it needs -fanalyzer for that.


Dave

[PATCH] analyzer: fix handling of negative byte offsets (PR 93281)

[David Malcolm]

Various 32-bit targets show failures in gcc.dg/analyzer/data-model-1.c
with tests of the form:
  __analyzer_eval (q[-2].x == 107024); /* { dg-warning "TRUE" } */
  __analyzer_eval (q[-2].y == 107025); /* { dg-warning "TRUE" } */
where they emit UNKNOWN instead.

The root cause is that gimple has a byte-based twos-complement offset
of -16 expressed like this:
  _55 = q_92 + 4294967280;  (32-bit)
or:
  _55 = q_92 + 18446744073709551600; (64-bit)

Within region_model::convert_byte_offset_to_array_index that unsigned
offset was being divided by the element size to get an offset within
an array.

This happened to work on 64-bit target and host, but not elsewhere;
the offset needs to be converted to a signed type before the division
is meaningful.

This patch does so, fixing the failures.

Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu;
verified with -m32 and -m64.

OK for master?

gcc/analyzer/ChangeLog:
	PR analyzer/93281
	* region-model.cc
	(region_model::convert_byte_offset_to_array_index): Convert
	offset_cst to ssizetype before dividing by byte_size.
---
 gcc/analyzer/region-model.cc | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc
index 5c39be4fd7f..b62ddf82a40 100644
--- a/gcc/analyzer/region-model.cc
+++ b/gcc/analyzer/region-model.cc
@@ -6414,9 +6414,12 @@ region_model::convert_byte_offset_to_array_index (tree ptr_type,
       /* This might not be a constant.  */
       tree byte_size = size_in_bytes (elem_type);
 
+      /* Ensure we're in a signed representation before doing the division.  */
+      tree signed_offset_cst = fold_convert (ssizetype, offset_cst);
+
       tree index
 	= fold_build2 (TRUNC_DIV_EXPR, integer_type_node,
-		       offset_cst, byte_size);
+		       signed_offset_cst, byte_size);
 
       if (CONSTANT_CLASS_P (index))
 	return get_or_create_constant_svalue (index);
-- 
2.21.0

Re: [PATCH] analyzer: fix handling of negative byte offsets (PR 93281)

[Richard Biener]

On January 16, 2020 12:56:48 AM GMT+01:00, David Malcolm <dmalcolm@redhat.com> wrote:
>Various 32-bit targets show failures in gcc.dg/analyzer/data-model-1.c
>with tests of the form:
>  __analyzer_eval (q[-2].x == 107024); /* { dg-warning "TRUE" } */
>  __analyzer_eval (q[-2].y == 107025); /* { dg-warning "TRUE" } */
>where they emit UNKNOWN instead.
>
>The root cause is that gimple has a byte-based twos-complement offset
>of -16 expressed like this:
>  _55 = q_92 + 4294967280;  (32-bit)
>or:
>  _55 = q_92 + 18446744073709551600; (64-bit)
>
>Within region_model::convert_byte_offset_to_array_index that unsigned
>offset was being divided by the element size to get an offset within
>an array.
>
>This happened to work on 64-bit target and host, but not elsewhere;
>the offset needs to be converted to a signed type before the division
>is meaningful.
>
>This patch does so, fixing the failures.
>
>Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu;
>verified with -m32 and -m64.
>
>OK for master?

Technically it depends on where you get that offset from. For MEM_REF there's mem_ref_offset which does the change for you for example. 

But, OK. 

Richard. 

>
>gcc/analyzer/ChangeLog:
>	PR analyzer/93281
>	* region-model.cc
>	(region_model::convert_byte_offset_to_array_index): Convert
>	offset_cst to ssizetype before dividing by byte_size.
>---
> gcc/analyzer/region-model.cc | 5 ++++-
> 1 file changed, 4 insertions(+), 1 deletion(-)
>
>diff --git a/gcc/analyzer/region-model.cc
>b/gcc/analyzer/region-model.cc
>index 5c39be4fd7f..b62ddf82a40 100644
>--- a/gcc/analyzer/region-model.cc
>+++ b/gcc/analyzer/region-model.cc
>@@ -6414,9 +6414,12 @@ region_model::convert_byte_offset_to_array_index
>(tree ptr_type,
>       /* This might not be a constant.  */
>       tree byte_size = size_in_bytes (elem_type);
> 
>+      /* Ensure we're in a signed representation before doing the
>division.  */
>+      tree signed_offset_cst = fold_convert (ssizetype, offset_cst);
>+
>       tree index
> 	= fold_build2 (TRUNC_DIV_EXPR, integer_type_node,
>-		       offset_cst, byte_size);
>+		       signed_offset_cst, byte_size);
> 
>       if (CONSTANT_CLASS_P (index))
> 	return get_or_create_constant_svalue (index);

Re: [PATCH] analyzer: fix handling of negative byte offsets (PR 93281)

[Jakub Jelinek]

On Wed, Jan 15, 2020 at 06:56:48PM -0500, David Malcolm wrote:
> gcc/analyzer/ChangeLog:
> 	PR analyzer/93281
> 	* region-model.cc
> 	(region_model::convert_byte_offset_to_array_index): Convert
> 	offset_cst to ssizetype before dividing by byte_size.
> ---
>  gcc/analyzer/region-model.cc | 5 ++++-
>  1 file changed, 4 insertions(+), 1 deletion(-)
> 
> diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc
> index 5c39be4fd7f..b62ddf82a40 100644
> --- a/gcc/analyzer/region-model.cc
> +++ b/gcc/analyzer/region-model.cc
> @@ -6414,9 +6414,12 @@ region_model::convert_byte_offset_to_array_index (tree ptr_type,
>        /* This might not be a constant.  */
>        tree byte_size = size_in_bytes (elem_type);
>  
> +      /* Ensure we're in a signed representation before doing the division.  */
> +      tree signed_offset_cst = fold_convert (ssizetype, offset_cst);
> +
>        tree index
>  	= fold_build2 (TRUNC_DIV_EXPR, integer_type_node,
> -		       offset_cst, byte_size);
> +		       signed_offset_cst, byte_size);

I'd say you want to fold_convert byte_size to ssizetype too.
Another thing is the integer_type_node, that looks wrong when you are
dividing ssizetype by ssizetype.  The fold-const.c folders are sensitive to
using incorrect types and type mismatches.
And, I think fold_build2 is wasteful, you only care if you can simplify it
to a constant (just constant or INTEGER_CST only?).
So, either use fold_binary (TRUNC_DIV_EXPR, ssizetype, offset_cst,
			    fold_convert (ssizetype, byte_size))
or, if you have checked that both arguments are INTEGER_CSTs, perhaps
int_const_binop or so.

>        if (CONSTANT_CLASS_P (index))

And this would need to be if (index && TREE_CODE (index) == INTEGER_CST)
(or if you can handle other constants (index && CONSTANT_CLASS_P (index)).

>  	return get_or_create_constant_svalue (index);

	Jakub

Re: Analyzer committed to master (was Re: Analyzer status)

[Rainer Orth]

Hi David,

>> I'm seeing quite a number of failures on Solaris (both sparc and
>> x86),
>> but also some on 32-bit Linux/x86:
>> 
>>  Running target unix/-m32
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 610)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 611)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 615)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 616)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 657)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 658)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 662)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 663)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 705)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 706)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 710)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 711)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 753)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 754)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 758)
>> +FAIL: gcc.dg/analyzer/data-model-1.c  (test for warnings, line 759)
>> +FAIL: gcc.dg/analyzer/data-model-1.c (test for excess errors)
>
> Thanks, and sorry about this; I've filed this for myself as:
>   https://gcc.gnu.org/bugzilla/show_bug.cgi?id=93281
> and have been investigating.
>
>> I'll file PRs for the Solaris ones once I get to it.

I've now filed PR analyzer/93316 for the rest; most of the errors there
also occur on at least one non-Solaris target.

	Rainer

-- 
-----------------------------------------------------------------------------
Rainer Orth, Center for Biotechnology, Bielefeld University