[PATCH] avoid invoking assignment on uninitialized objects (PR 92761, 92762)

[PATCH] avoid invoking assignment on uninitialized objects (PR 92761, 92762)

[Martin Sebor]

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

After allocating a new chunk of memory hash_table::expand() copy-
assigns elements from the current array over the newly allocated
elements without constructing them.

Similarly, after destroying existing elements, hash_table::
empty_slow() assigns a new value to them.  This bug was
introduced in r249234 when trying to deal with -Wclass-memaccess
instances when the warning was first added.

Neither of these is a problem for PODs but both cause trouble when
the hash_table contains elements of a type with a user-defined copy
assignment operator.  There are at least two such instances in GCC
already and a third is under review.

The attached patch avoids this by using placement new to construct
new elements in uninitialized storage and restoring the original
call to memset in hash_table::empty_slow(), analogously to what
was done in r272893 for PR90923,

Longer term, to make these templates safely and efficiently usable
with non-POD types with user-defined copy ctors and copy assignment
operators I think these classes will probably need to be enhanced
to make use of "assign" and "move" traits functions to efficiently
assign and move objects.

Martin

[-- Attachment #2: gcc-92761.diff --]
[-- Type: text/x-patch, Size: 2712 bytes --]

PR middle-end/92761 - hash_table::expand invokes assignment on invalid objects
PR middle-end/92762 - hash_table::empty_slow invokes assignment on invalid objects
gcc/ChangeLog:

	PR middle-end/92761
	PR middle-end/92762
	* hash-map-tests.c (test_map_of_type_with_ctor_and_dtor): Tighten
	up tests.
	* hash-table.h (hash_table::expand): Use placement new to copy
	construct objects in uninitialized storage.
	(hash_table::empty_slow): Avoid invoking copy assignment on
	uninitialized objects.

diff --git a/gcc/hash-map-tests.c b/gcc/hash-map-tests.c
index f3b216be07c..a42eac21ab3 100644
--- a/gcc/hash-map-tests.c
+++ b/gcc/hash-map-tests.c
@@ -117,23 +117,26 @@ public:
     ++ndefault;
   }
 
-  hash_map_test_val_t (const hash_map_test_val_t &)
+  hash_map_test_val_t (const hash_map_test_val_t &rhs)
     : ptr (&ptr)
   {
     ++ncopy;
+    gcc_assert (rhs.ptr == &rhs.ptr);
   }
 
-  hash_map_test_val_t& operator= (const hash_map_test_val_t &)
-    {
-     ++nassign;
-     return *this;
-    }
+  hash_map_test_val_t& operator= (const hash_map_test_val_t &rhs)
+  {
+    ++nassign;
+    gcc_assert (ptr == &ptr);
+    gcc_assert (rhs.ptr == &rhs.ptr);
+    return *this;
+  }
 
   ~hash_map_test_val_t ()
-    {
-     gcc_assert (ptr == &ptr);
-     ++ndtor;
-    }
+  {
+    gcc_assert (ptr == &ptr);
+    ++ndtor;
+  }
 
   void *ptr;
 } val_t;
@@ -184,7 +187,6 @@ test_map_of_type_with_ctor_and_dtor ()
     ASSERT_TRUE (nassign == val_t::nassign);
 
     ASSERT_TRUE (&rv1 != pv2);
-    ASSERT_TRUE (pv2->ptr == &pv2->ptr);
   }
 
   ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
@@ -207,7 +209,6 @@ test_map_of_type_with_ctor_and_dtor ()
     ASSERT_TRUE (nassign + 1 == val_t::nassign);
 
     ASSERT_TRUE (&rv1 != pv2);
-    ASSERT_TRUE (pv2->ptr == &pv2->ptr);
   }
 
   ASSERT_TRUE (val_t::ndefault + val_t::ncopy == val_t::ndtor);
diff --git a/gcc/hash-table.h b/gcc/hash-table.h
index ba5d64fb7a3..26bac624a08 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -818,8 +818,7 @@ hash_table<Descriptor, Lazy, Allocator>::expand ()
       if (!is_empty (x) && !is_deleted (x))
         {
           value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
-
-          *q = x;
+	  new ((void*) q) value_type (x);
         }
 
       p++;
@@ -869,14 +868,8 @@ hash_table<Descriptor, Lazy, Allocator>::empty_slow ()
       m_size_prime_index = nindex;
     }
   else
-    {
-#ifndef BROKEN_VALUE_INITIALIZATION
-      for ( ; size; ++entries, --size)
-	*entries = value_type ();
-#else
-      memset (entries, 0, size * sizeof (value_type));
-#endif
-    }
+    memset ((void *) entries, 0, size * sizeof (value_type));
+
   m_n_deleted = 0;
   m_n_elements = 0;
 }

Re: [PATCH] avoid invoking assignment on uninitialized objects (PR 92761, 92762)

[Jeff Law]

On Tue, 2019-12-03 at 15:41 -0700, Martin Sebor wrote:
> PR middle-end/92761 - hash_table::expand invokes assignment on invalid objects
> PR middle-end/92762 - hash_table::empty_slow invokes assignment on invalid objects
> gcc/ChangeLog:
> 
> 	PR middle-end/92761
> 	PR middle-end/92762
> 	* hash-map-tests.c (test_map_of_type_with_ctor_and_dtor): Tighten
> 	up tests.
> 	* hash-table.h (hash_table::expand): Use placement new to copy
> 	construct objects in uninitialized storage.
> 	(hash_table::empty_slow): Avoid invoking copy assignment on
> 	uninitialized objects.
OK
jeff

Re: [PATCH] avoid invoking assignment on uninitialized objects (PR 92761, 92762)

[David Malcolm]

On Tue, 2019-12-03 at 15:41 -0700, Martin Sebor wrote:
> After allocating a new chunk of memory hash_table::expand() copy-
> assigns elements from the current array over the newly allocated
> elements without constructing them.
> 
> Similarly, after destroying existing elements, hash_table::
> empty_slow() assigns a new value to them.  This bug was
> introduced in r249234 when trying to deal with -Wclass-memaccess
> instances when the warning was first added.
> 
> Neither of these is a problem for PODs but both cause trouble when
> the hash_table contains elements of a type with a user-defined copy
> assignment operator.  There are at least two such instances in GCC
> already and a third is under review.
> 
> The attached patch avoids this by using placement new to construct
> new elements in uninitialized storage and restoring the original
> call to memset in hash_table::empty_slow(), analogously to what
> was done in r272893 for PR90923,
> 
> Longer term, to make these templates safely and efficiently usable
> with non-POD types with user-defined copy ctors and copy assignment
> operators I think these classes will probably need to be enhanced
> to make use of "assign" and "move" traits functions to efficiently
> assign and move objects.
> 
> Martin

> diff --git a/gcc/hash-table.h b/gcc/hash-table.h
> index ba5d64fb7a3..26bac624a08 100644
> --- a/gcc/hash-table.h
> +++ b/gcc/hash-table.h
> @@ -818,8 +818,7 @@ hash_table<Descriptor, Lazy, Allocator>::expand ()
>        if (!is_empty (x) && !is_deleted (x))
>          {
>            value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
> -
> -          *q = x;
> +	  new ((void*) q) value_type (x);
>          }
>  
>        p++;
> @@ -869,14 +868,8 @@ hash_table<Descriptor, Lazy, Allocator>::empty_slow ()
>        m_size_prime_index = nindex;
>      }
>    else
> -    {
> -#ifndef BROKEN_VALUE_INITIALIZATION
> -      for ( ; size; ++entries, --size)
> -	*entries = value_type ();
> -#else
> -      memset (entries, 0, size * sizeof (value_type));
> -#endif
> -    }
> +    memset ((void *) entries, 0, size * sizeof (value_type));
> +
>    m_n_deleted = 0;
>    m_n_elements = 0;
>  }

On attempting to rebase my analyzer branch I found that this patch
uncovered a bug in it, but also possibly a bug in hash-table.h.

In the analyzer branch I have a hash_map with a key where the "empty"
value isn't all-zero-bits.

Specifically, in gcc/analyzer/program-state.h: sm_state_map has a
hash_map <svalue_id, entry_t> map_t, where svalue_id, the key type, has
hash traits:

template <>
inline void
pod_hash_traits<svalue_id>::mark_empty (value_type &v)
{
  v = svalue_id::null ();
}

which is a -1 int (all ones).

memset to zero bits populates the "empty" slots with a key with a non-
empty value for this key type, effectively corrupting the data
structure (luckily a selftest caught this).

Looking at the above patch, it looks like I was unwittingly relying on
two things:
(a) #ifndef BROKEN_VALUE_INITIALIZATION, and
(b) that the default ctor for my key type was the "empty" value.

However, shouldn't empty_slow be calling the Descriptor::mark_empty
function?  Doesn't this memset code assume that the "empty" value of
the hash_table entry is all-zeroes (and thus imposing the same
assumption on all hash_maps' key and value types?) - which isn't the
case for my code.  I don't remember seeing that assumption documented.

Or am I misreading this?

Thanks
Dave

Re: [PATCH] avoid invoking assignment on uninitialized objects (PR 92761, 92762)

[Martin Sebor]

On 12/10/19 3:07 PM, David Malcolm wrote:
> On Tue, 2019-12-03 at 15:41 -0700, Martin Sebor wrote:
>> After allocating a new chunk of memory hash_table::expand() copy-
>> assigns elements from the current array over the newly allocated
>> elements without constructing them.
>>
>> Similarly, after destroying existing elements, hash_table::
>> empty_slow() assigns a new value to them.  This bug was
>> introduced in r249234 when trying to deal with -Wclass-memaccess
>> instances when the warning was first added.
>>
>> Neither of these is a problem for PODs but both cause trouble when
>> the hash_table contains elements of a type with a user-defined copy
>> assignment operator.  There are at least two such instances in GCC
>> already and a third is under review.
>>
>> The attached patch avoids this by using placement new to construct
>> new elements in uninitialized storage and restoring the original
>> call to memset in hash_table::empty_slow(), analogously to what
>> was done in r272893 for PR90923,
>>
>> Longer term, to make these templates safely and efficiently usable
>> with non-POD types with user-defined copy ctors and copy assignment
>> operators I think these classes will probably need to be enhanced
>> to make use of "assign" and "move" traits functions to efficiently
>> assign and move objects.
>>
>> Martin
> 
>> diff --git a/gcc/hash-table.h b/gcc/hash-table.h
>> index ba5d64fb7a3..26bac624a08 100644
>> --- a/gcc/hash-table.h
>> +++ b/gcc/hash-table.h
>> @@ -818,8 +818,7 @@ hash_table<Descriptor, Lazy, Allocator>::expand ()
>>         if (!is_empty (x) && !is_deleted (x))
>>           {
>>             value_type *q = find_empty_slot_for_expand (Descriptor::hash (x));
>> -
>> -          *q = x;
>> +	  new ((void*) q) value_type (x);
>>           }
>>   
>>         p++;
>> @@ -869,14 +868,8 @@ hash_table<Descriptor, Lazy, Allocator>::empty_slow ()
>>         m_size_prime_index = nindex;
>>       }
>>     else
>> -    {
>> -#ifndef BROKEN_VALUE_INITIALIZATION
>> -      for ( ; size; ++entries, --size)
>> -	*entries = value_type ();
>> -#else
>> -      memset (entries, 0, size * sizeof (value_type));
>> -#endif
>> -    }
>> +    memset ((void *) entries, 0, size * sizeof (value_type));
>> +
>>     m_n_deleted = 0;
>>     m_n_elements = 0;
>>   }
> 
> On attempting to rebase my analyzer branch I found that this patch
> uncovered a bug in it, but also possibly a bug in hash-table.h.
> 
> In the analyzer branch I have a hash_map with a key where the "empty"
> value isn't all-zero-bits.

There's a test case for it in comment #3 in 92762.

> 
> Specifically, in gcc/analyzer/program-state.h: sm_state_map has a
> hash_map <svalue_id, entry_t> map_t, where svalue_id, the key type, has
> hash traits:
> 
> template <>
> inline void
> pod_hash_traits<svalue_id>::mark_empty (value_type &v)
> {
>    v = svalue_id::null ();
> }
> 
> which is a -1 int (all ones).
> 
> memset to zero bits populates the "empty" slots with a key with a non-
> empty value for this key type, effectively corrupting the data
> structure (luckily a selftest caught this).
> 
> Looking at the above patch, it looks like I was unwittingly relying on
> two things:
> (a) #ifndef BROKEN_VALUE_INITIALIZATION, and
> (b) that the default ctor for my key type was the "empty" value.
> 
> However, shouldn't empty_slow be calling the Descriptor::mark_empty
> function?  Doesn't this memset code assume that the "empty" value of
> the hash_table entry is all-zeroes (and thus imposing the same
> assumption on all hash_maps' key and value types?) - which isn't the
> case for my code.  I don't remember seeing that assumption documented.
> 
> Or am I misreading this?

IIRC, I had tried the below but it caused problems during bootstrap
that I didn't spend enough time investigating.

   for (size_t i = size - 1; i < size; i--)
     if (!is_empty (entries[i]) && !is_deleted (entries[i]))
       {
         Descriptor::remove (entries[i]);
         mark_empty (entries[i]);
       }

(I think it also caused compilation error in one of the IPA passes
because of a missing mark_empty function in its traits class; maybe
ipa_bit_ggc_hash_traits in ipa-prop.c).

To be honest, I'm not sure I understand why the memset is even there.
It seems like a leak to me (I can reproduce leaks with a user-defined
type).  I was going to get back to it at some point.

Martin

[PATCH] hash-table.h: support non-zero empty values in empty_slow

[David Malcolm]

On Tue, 2019-12-10 at 16:00 -0700, Martin Sebor wrote:
> On 12/10/19 3:07 PM, David Malcolm wrote:
> > On Tue, 2019-12-03 at 15:41 -0700, Martin Sebor wrote:
> > > After allocating a new chunk of memory hash_table::expand() copy-
> > > assigns elements from the current array over the newly allocated
> > > elements without constructing them.
> > > 
> > > Similarly, after destroying existing elements, hash_table::
> > > empty_slow() assigns a new value to them.  This bug was
> > > introduced in r249234 when trying to deal with -Wclass-memaccess
> > > instances when the warning was first added.
> > > 
> > > Neither of these is a problem for PODs but both cause trouble
> > > when
> > > the hash_table contains elements of a type with a user-defined
> > > copy
> > > assignment operator.  There are at least two such instances in
> > > GCC
> > > already and a third is under review.
> > > 
> > > The attached patch avoids this by using placement new to
> > > construct
> > > new elements in uninitialized storage and restoring the original
> > > call to memset in hash_table::empty_slow(), analogously to what
> > > was done in r272893 for PR90923,
> > > 
> > > Longer term, to make these templates safely and efficiently
> > > usable
> > > with non-POD types with user-defined copy ctors and copy
> > > assignment
> > > operators I think these classes will probably need to be enhanced
> > > to make use of "assign" and "move" traits functions to
> > > efficiently
> > > assign and move objects.
> > > 
> > > Martin
> > > diff --git a/gcc/hash-table.h b/gcc/hash-table.h
> > > index ba5d64fb7a3..26bac624a08 100644
> > > --- a/gcc/hash-table.h
> > > +++ b/gcc/hash-table.h
> > > @@ -818,8 +818,7 @@ hash_table<Descriptor, Lazy,
> > > Allocator>::expand ()
> > >         if (!is_empty (x) && !is_deleted (x))
> > >           {
> > >             value_type *q = find_empty_slot_for_expand
> > > (Descriptor::hash (x));
> > > -
> > > -          *q = x;
> > > +	  new ((void*) q) value_type (x);
> > >           }
> > >   
> > >         p++;
> > > @@ -869,14 +868,8 @@ hash_table<Descriptor, Lazy,
> > > Allocator>::empty_slow ()
> > >         m_size_prime_index = nindex;
> > >       }
> > >     else
> > > -    {
> > > -#ifndef BROKEN_VALUE_INITIALIZATION
> > > -      for ( ; size; ++entries, --size)
> > > -	*entries = value_type ();
> > > -#else
> > > -      memset (entries, 0, size * sizeof (value_type));
> > > -#endif
> > > -    }
> > > +    memset ((void *) entries, 0, size * sizeof (value_type));
> > > +
> > >     m_n_deleted = 0;
> > >     m_n_elements = 0;
> > >   }
> > 
> > On attempting to rebase my analyzer branch I found that this patch
> > uncovered a bug in it, but also possibly a bug in hash-table.h.
> > 
> > In the analyzer branch I have a hash_map with a key where the
> > "empty"
> > value isn't all-zero-bits.
> 
> There's a test case for it in comment #3 in 92762.

Thanks.  I've adapted that into a selftest in this patch.

> > Specifically, in gcc/analyzer/program-state.h: sm_state_map has a
> > hash_map <svalue_id, entry_t> map_t, where svalue_id, the key type,
> > has
> > hash traits:
> > 
> > template <>
> > inline void
> > pod_hash_traits<svalue_id>::mark_empty (value_type &v)
> > {
> >    v = svalue_id::null ();
> > }
> > 
> > which is a -1 int (all ones).
> > 
> > memset to zero bits populates the "empty" slots with a key with a
> > non-
> > empty value for this key type, effectively corrupting the data
> > structure (luckily a selftest caught this).
> > 
> > Looking at the above patch, it looks like I was unwittingly relying
> > on
> > two things:
> > (a) #ifndef BROKEN_VALUE_INITIALIZATION, and
> > (b) that the default ctor for my key type was the "empty" value.
> > 
> > However, shouldn't empty_slow be calling the Descriptor::mark_empty
> > function?  Doesn't this memset code assume that the "empty" value
> > of
> > the hash_table entry is all-zeroes (and thus imposing the same
> > assumption on all hash_maps' key and value types?) - which isn't
> > the
> > case for my code.  I don't remember seeing that assumption
> > documented.

Correcting myself, I *think* this would impose the assumption that all
hash_maps' keys types "empty" value is all-zeroes; I don't think that
holds for the value types though.

> > 
> > Or am I misreading this?
> 
> IIRC, I had tried the below but it caused problems during bootstrap
> that I didn't spend enough time investigating.
> 
>    for (size_t i = size - 1; i < size; i--)
>      if (!is_empty (entries[i]) && !is_deleted (entries[i]))
>        {
>          Descriptor::remove (entries[i]);
>          mark_empty (entries[i]);
>        }
> 
> (I think it also caused compilation error in one of the IPA passes
> because of a missing mark_empty function in its traits class; maybe
> ipa_bit_ggc_hash_traits in ipa-prop.c).
> 
> To be honest, I'm not sure I understand why the memset is even there.
> It seems like a leak to me (I can reproduce leaks with a user-defined
> type).  I was going to get back to it at some point.
> 
> Martin

Thanks for all the info.

Considering the change you tried to hash_table::empty_slow, AIUI, an
entry in a hash_table can be in one of three states:
(a) "empty"
(b) "deleted"
(c) a properly constructed object

If I'm reading the change you tried above correctly, it's only marking
as empty the entries that are in state (c); it's leaving "deleted"
entries untouched.

Later in empty_slow, control flow splits into resize vs non-resize
cases.  In the resize case, alloc_entries is called, and alloc_entries
has this loop:
  for (size_t i = 0; i < n; i++)
    mark_empty (nentries[i]);
thus ensuring that every entry is in the "empty" state.
However, for the non-resize case, we now currently reach the code
touched in r279139 (the above patch):
   memset (entries, 0, size * sizeof (value_type));
Hence if a hash_map is emptied without being resized, we end up with
either entries still being marked as deleted despite m_n_deleted == 0
(the fix you tried above), or all the entries being zero-filled and
thus effectively things if zero isn't an "empty" state (current trunk).

The following patch updates hash_table::empty_slow so that the
non-resize case uses the same loop as the resize case, thus marking all
entries as empty, without assuming that in must be all-zeroes.

The patch is actually on top of:
  https://gcc.gnu.org/ml/gcc-patches/2019-11/msg01514.html
which merely adds more selftests to hash-map-tests.c and which Jeff
already approved (the hash_map in that new test used an EMPTY value of
-1, but the various ops happened not to call empty_slow).

Hopefully I'm understanding things correctly.

Is it OK for a hash_map key to have a "empty" value that isn't
all-zeroes (and thus the same for a hash_table entry)?

Is the following patch OK for trunk?

Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu (albeit
in conjuction with the rest of the analyzer patch kit, which it fixes;
I'll retest cleanly before committing if approved).

Thanks
Dave

gcc/ChangeLog:
	* hash-map-tests.c (selftest::test_nonzero_empty_key): New selftest.
	(selftest::hash_map_tests_c_tests): Call it.
	* hash-table.h
	(hash_table<Descriptor, Lazy, Allocator>::empty_slow): When not
	resizing the entries buffer, replace the memset to zero with a
	loop that calls mark_empty on all elements.
---
 gcc/hash-map-tests.c | 22 ++++++++++++++++++++++
 gcc/hash-table.h     |  5 ++++-
 2 files changed, 26 insertions(+), 1 deletion(-)

diff --git a/gcc/hash-map-tests.c b/gcc/hash-map-tests.c
index 9a13a80442c8..9a92425df5db 100644
--- a/gcc/hash-map-tests.c
+++ b/gcc/hash-map-tests.c
@@ -278,6 +278,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
@@ -286,6 +307,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-table.h b/gcc/hash-table.h
index 26bac624a082..126bd6d22ad5 100644
--- a/gcc/hash-table.h
+++ b/gcc/hash-table.h
@@ -868,7 +868,10 @@ hash_table<Descriptor, Lazy, Allocator>::empty_slow ()
       m_size_prime_index = nindex;
     }
   else
-    memset ((void *) entries, 0, size * sizeof (value_type));
+    {
+      for (size_t i = 0; i < size; i++)
+	mark_empty (entries[i]);
+    }
 
   m_n_deleted = 0;
   m_n_elements = 0;
-- 
2.21.0

Re: [PATCH] hash-table.h: support non-zero empty values in empty_slow

[Jakub Jelinek]

On Wed, Dec 11, 2019 at 10:44:58AM -0500, David Malcolm wrote:
> Is it OK for a hash_map key to have a "empty" value that isn't
> all-zeroes (and thus the same for a hash_table entry)?
> 
> Is the following patch OK for trunk?

I'd say that it is important to analyze the generated code for the common
case where empty elt is all zeros (and perhaps POD only).
Perhaps -ftree-loop-distribute-patterns can handle it in most cases?
Perhaps only when built in C++14 or later mode, that would still affect
bootstrapped compilers.  Like, could we conditionally constexpr evaluate
what mark_empty does and determine at compile time if it is all zeros or
not or something similar?

	Jakub

Re: [PATCH] hash-table.h: support non-zero empty values in empty_slow

[David Malcolm]

On Wed, 2019-12-11 at 17:00 +0100, Jakub Jelinek wrote:
> On Wed, Dec 11, 2019 at 10:44:58AM -0500, David Malcolm wrote:
> > Is it OK for a hash_map key to have a "empty" value that isn't
> > all-zeroes (and thus the same for a hash_table entry)?
> > 
> > Is the following patch OK for trunk?
> 
> I'd say that it is important to analyze the generated code for the
> common
> case where empty elt is all zeros (and perhaps POD only).
> Perhaps -ftree-loop-distribute-patterns can handle it in most cases?
> Perhaps only when built in C++14 or later mode, that would still
> affect
> bootstrapped compilers.  Like, could we conditionally constexpr
> evaluate
> what mark_empty does and determine at compile time if it is all zeros
> or
> not or something similar?
> 
> 	Jakub

I did a release build with gcc 9 at -O2, and examined the generated
code for cfg.o's class hash_table<bb_copy_hasher>'s empty_slow (which
has such an all zeroes empty element).

The mark_empty loop there was converted to a memset (without needing
-ftree-loop-distribute-patterns), which is promising.

However, that only covers hash_table.

Our hash_map is built on top of hash_table, where the entries in the
hash_map are key/value pairs.  A memset to 0 of all of the entries in
such a hash_table is not the same as a per-entry mark_empty, as the
latter only touches the m_key part of each entry, not the m_value
part.  It doesn't matter that we don't preserve the m_value for my POD
value cases, but it means the optimizer could never replace a loop of
mark_empty of m_key of 0 with a memset to 0 of all entries, since it
doesn't "know" that m_value can be safely zeroed also.

Is that an issue?  Is it necessarily better to memset the whole of the
buffer, rather than zeroing just the keys?  Hacking out hash_map::empty
shows that it's used in 6 places in the code currently.

[Jeff approved the analyzer, but I realise that this issue is still
blocking it; bother]

Dave