Analyzer status

Message ID 20200113221024.29991-1-dmalcolm@redhat.com
State New
Headers show
Series
  • Analyzer status
Related show

Commit Message

David Malcolm Jan. 13, 2020, 10:10 p.m.
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(+)

-- 
2.21.0

Comments

Jakub Jelinek Jan. 13, 2020, 10:56 p.m. | #1
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
Jakub Jelinek Jan. 13, 2020, 11:26 p.m. | #2
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
David Malcolm Jan. 13, 2020, 11:42 p.m. | #3
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
Jakub Jelinek Jan. 13, 2020, 11:55 p.m. | #4
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
David Malcolm Jan. 14, 2020, 2:58 a.m. | #5
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
Richard Biener Jan. 14, 2020, 7:55 a.m. | #6
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)
David Malcolm Jan. 14, 2020, 8:49 p.m. | #7
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
Rainer Orth Jan. 15, 2020, 12:30 p.m. | #8
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
Dimitar Dimitrov Jan. 15, 2020, 7:41 p.m. | #9
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
Iain Sandoe Jan. 15, 2020, 8:10 p.m. | #10
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
David Malcolm Jan. 15, 2020, 8:29 p.m. | #11
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
Rainer Orth Jan. 18, 2020, 2:51 p.m. | #12
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

Patch

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 ();