[gcc r14-4306] vec.h: Make some ops work with non-trivially copy constructible and/or destructible types

[gcc r14-4306] vec.h: Make some ops work with non-trivially copy constructible and/or destructible types

[Jakub Jelinek]

https://gcc.gnu.org/g:73cd319b72ca45a537688cc8cc5751d86a00a0e9

commit r14-4306-g73cd319b72ca45a537688cc8cc5751d86a00a0e9
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Thu Sep 28 11:59:10 2023 +0200

    vec.h: Make some ops work with non-trivially copy constructible and/or destructible types
    
    We have some very limited support for non-POD types in vec.h
    (in particular grow_cleared will invoke default ctors on the
    cleared elements and vector copying invokes copy ctors.
    
    My pending work on wide_int/widest_int which makes those two
    non-trivially default constructible, copyable and destructible shows this
    isn't enough though.
    In particular the uses of it in irange shows that quick_push
    still uses just assignment operator rather than copy construction
    and we never invoke destructors on anything.
    
    The following patch does that for quick_push (copy construction
    using placement new rather than assignment, for trivially copy
    constructible types I think it should be the same) and invokes
    destructors (only if non-trivially destructible) in pop, release
    and truncate.  Now as discussed last night on IRC, the pop case
    is problematic, because our pop actually does two things,
    it decreases length (so the previous last element should be destructed)
    but also returns a reference to it.  We have some 300+ uses of this
    and the reference rather than returning it by value is useful at least
    for the elements which are (larger) POD structures, so I'm not
    prepared to change that.  Though obviously for types with non-trivial
    destructors returning a reference to just destructed element is not
    a good idea.  So, this patch for that case only makes pop return void
    instead and any users wishing to get the last element need to use last ()
    and pop () separately (currently there are none).
    
    Note, a lot of vec.h operations is still not friendly for non-POD types,
    and the patch tries to enforce that through static asserts.  Some
    operations are now only allowed on trivially copyable types, sorting
    operations as an extension on trivially copyable types or std::pair
    of 2 trivially copyable types, quick_grow/safe_grow (but not _cleared
    variants) for now have a commented out assert on trivially default
    constructible types - this needs some further work before the assert
    can be enabled - and finally all va_gc/va_gc_atomic vectors require
    trivially destructible types.
    
    2023-09-28  Jakub Jelinek  <jakub@redhat.com>
                Jonathan Wakely  <jwakely@redhat.com>
    
            * vec.h: Mention in file comment limited support for non-POD types
            in some operations.
            (vec_destruct): New function template.
            (release): Use it for non-trivially destructible T.
            (truncate): Likewise.
            (quick_push): Perform a placement new into slot
            instead of assignment.
            (pop): For non-trivially destructible T return void
            rather than T & and destruct the popped element.
            (quick_insert, ordered_remove): Note that they aren't suitable
            for non-trivially copyable types.  Add static_asserts for that.
            (block_remove): Assert T is trivially copyable.
            (vec_detail::is_trivially_copyable_or_pair): New trait.
            (qsort, sort, stablesort): Assert T is trivially copyable or
            std::pair with both trivally copyable types.
            (quick_grow): Add assert T is trivially default constructible,
            for now commented out.
            (quick_grow_cleared): Don't call quick_grow, instead inline it
            by hand except for the new static_assert.
            (gt_ggc_mx): Assert T is trivially destructable.
            (auto_vec::operator=): Formatting fixes.
            (auto_vec::auto_vec): Likewise.
            (vec_safe_grow_cleared): Don't call vec_safe_grow, instead inline
            it manually and call quick_grow_cleared method rather than quick_grow.
            (safe_grow_cleared): Likewise.
            * edit-context.cc (class line_event): Move definition earlier.
            * tree-ssa-loop-im.cc (seq_entry::seq_entry): Make default ctor
            defaulted.
            * ipa-fnsummary.cc (evaluate_properties_for_edge): Use
            safe_grow_cleared instead of safe_grow followed by placement new
            constructing the elements.

Diff:
---
 gcc/edit-context.cc     |  52 ++++++++++----------
 gcc/ipa-fnsummary.cc    |   8 +--
 gcc/tree-ssa-loop-im.cc |   2 +-
 gcc/vec.h               | 127 +++++++++++++++++++++++++++++++++++++++---------
 4 files changed, 133 insertions(+), 56 deletions(-)

diff --git a/gcc/edit-context.cc b/gcc/edit-context.cc
index 6f5bc6b9d8f..09b000c74c4 100644
--- a/gcc/edit-context.cc
+++ b/gcc/edit-context.cc
@@ -122,6 +122,32 @@ class added_line
   int m_len;
 };
 
+/* Class for representing edit events that have occurred on one line of
+   one file: the replacement of some text betweeen some columns
+   on the line.
+
+   Subsequent events will need their columns adjusting if they're
+   are on this line and their column is >= the start point.  */
+
+class line_event
+{
+ public:
+  line_event (int start, int next, int len) : m_start (start),
+    m_delta (len - (next - start)) {}
+
+  int get_effective_column (int orig_column) const
+  {
+    if (orig_column >= m_start)
+      return orig_column += m_delta;
+    else
+      return orig_column;
+  }
+
+ private:
+  int m_start;
+  int m_delta;
+};
+
 /* The state of one edited line within an edited_file.
    As well as the current content of the line, it contains a record of
    the changes, so that further changes can be applied in the correct
@@ -172,32 +198,6 @@ class edited_line
   auto_vec <added_line *> m_predecessors;
 };
 
-/* Class for representing edit events that have occurred on one line of
-   one file: the replacement of some text betweeen some columns
-   on the line.
-
-   Subsequent events will need their columns adjusting if they're
-   are on this line and their column is >= the start point.  */
-
-class line_event
-{
- public:
-  line_event (int start, int next, int len) : m_start (start),
-    m_delta (len - (next - start)) {}
-
-  int get_effective_column (int orig_column) const
-  {
-    if (orig_column >= m_start)
-      return orig_column += m_delta;
-    else
-      return orig_column;
-  }
-
- private:
-  int m_start;
-  int m_delta;
-};
-
 /* Forward decls.  */
 
 static void
diff --git a/gcc/ipa-fnsummary.cc b/gcc/ipa-fnsummary.cc
index f1244da291c..a2495ffe63e 100644
--- a/gcc/ipa-fnsummary.cc
+++ b/gcc/ipa-fnsummary.cc
@@ -679,12 +679,8 @@ evaluate_properties_for_edge (struct cgraph_edge *e, bool inline_p,
 		    if (!vr.undefined_p () && !vr.varying_p ())
 		      {
 			if (!avals->m_known_value_ranges.length ())
-			  {
-			    avals->m_known_value_ranges.safe_grow (count, true);
-			    for (int i = 0; i < count; ++i)
-			      new (&avals->m_known_value_ranges[i])
-				Value_Range ();
-			  }
+			  avals->m_known_value_ranges.safe_grow_cleared (count,
+									 true);
 			avals->m_known_value_ranges[i] = vr;
 		      }
 		  }
diff --git a/gcc/tree-ssa-loop-im.cc b/gcc/tree-ssa-loop-im.cc
index b8e33a4d49a..6931b61f54e 100644
--- a/gcc/tree-ssa-loop-im.cc
+++ b/gcc/tree-ssa-loop-im.cc
@@ -2324,7 +2324,7 @@ execute_sm (class loop *loop, im_mem_ref *ref,
 enum sm_kind { sm_ord, sm_unord, sm_other };
 struct seq_entry
 {
-  seq_entry () {}
+  seq_entry () = default;
   seq_entry (unsigned f, sm_kind k, tree fr = NULL)
     : first (f), second (k), from (fr) {}
   unsigned first;
diff --git a/gcc/vec.h b/gcc/vec.h
index 8a9a8d83de5..8aacb5a8def 100644
--- a/gcc/vec.h
+++ b/gcc/vec.h
@@ -111,6 +111,24 @@ extern void *ggc_realloc (void *, size_t MEM_STAT_DECL);
    the 'space' predicate will tell you whether there is spare capacity
    in the vector.  You will not normally need to use these two functions.
 
+   Not all vector operations support non-POD types and such restrictions
+   are enforced through static assertions.  Some operations which often use
+   memmove to move elements around like quick_insert, safe_insert,
+   ordered_remove, unordered_remove, block_remove etc. require trivially
+   copyable types.  Sorting operations, qsort, sort and stablesort, require
+   those too but as an extension allow also std::pair of 2 trivially copyable
+   types which happens to work even when std::pair itself isn't trivially
+   copyable.  The quick_grow and safe_grow operations require trivially
+   default constructible types.  One can use quick_grow_cleared or
+   safe_grow_cleared for non-trivially default constructible types if needed
+   (but of course such operation is more expensive then).  The pop operation
+   returns reference to the last element only for trivially destructible
+   types, for non-trivially destructible types one should use last operation
+   followed by pop which in that case returns void.
+   And finally, the GC and GC atomic vectors should always be used with
+   trivially destructible types, as nothing will invoke destructors when they
+   are freed during GC.
+
    Notes on the different layout strategies
 
    * Embeddable vectors (vec<T, A, vl_embed>)
@@ -185,6 +203,16 @@ extern void dump_vec_loc_statistics (void);
 /* Hashtable mapping vec addresses to descriptors.  */
 extern htab_t vec_mem_usage_hash;
 
+/* Destruct N elements in DST.  */
+
+template <typename T>
+inline void
+vec_destruct (T *dst, unsigned n)
+{
+  for ( ; n; ++dst, --n)
+    dst->~T ();
+}
+
 /* Control data for vectors.  This contains the number of allocated
    and used slots inside a vector.  */
 
@@ -310,6 +338,9 @@ va_heap::release (vec<T, va_heap, vl_embed> *&v)
   if (v == NULL)
     return;
 
+  if (!std::is_trivially_destructible <T>::value)
+    vec_destruct (v->address (), v->length ());
+
   if (GATHER_STATISTICS)
     v->m_vecpfx.release_overhead (v, elt_size * v->allocated (),
 				  v->allocated (), true);
@@ -588,7 +619,10 @@ public:
   void splice (const vec &);
   void splice (const vec *src);
   T *quick_push (const T &);
-  T &pop (void);
+  using pop_ret_type
+    = typename std::conditional <std::is_trivially_destructible <T>::value,
+				 T &, void>::type;
+  pop_ret_type pop (void);
   void truncate (unsigned);
   void quick_insert (unsigned, const T &);
   void ordered_remove (unsigned);
@@ -735,8 +769,9 @@ vec_safe_grow_cleared (vec<T, A, vl_embed> *&v, unsigned len,
 		       bool exact = false CXX_MEM_STAT_INFO)
 {
   unsigned oldlen = vec_safe_length (v);
-  vec_safe_grow (v, len, exact PASS_MEM_STAT);
-  vec_default_construct (v->address () + oldlen, len - oldlen);
+  gcc_checking_assert (len >= oldlen);
+  vec_safe_reserve (v, len - oldlen, exact PASS_MEM_STAT);
+  v->quick_grow_cleared (len);
 }
 
 
@@ -1005,19 +1040,24 @@ vec<T, A, vl_embed>::quick_push (const T &obj)
 {
   gcc_checking_assert (space (1));
   T *slot = &address ()[m_vecpfx.m_num++];
-  *slot = obj;
+  ::new (static_cast<void*>(slot)) T (obj);
   return slot;
 }
 
 
-/* Pop and return the last element off the end of the vector.  */
+/* Pop and return a reference to the last element off the end of the
+   vector.  If T has non-trivial destructor, this method just pops
+   the element and returns void type.  */
 
 template<typename T, typename A>
-inline T &
+inline typename vec<T, A, vl_embed>::pop_ret_type
 vec<T, A, vl_embed>::pop (void)
 {
   gcc_checking_assert (length () > 0);
-  return address ()[--m_vecpfx.m_num];
+  T &last = address ()[--m_vecpfx.m_num];
+  if (!std::is_trivially_destructible <T>::value)
+    last.~T ();
+  return static_cast <pop_ret_type> (last);
 }
 
 
@@ -1028,13 +1068,17 @@ template<typename T, typename A>
 inline void
 vec<T, A, vl_embed>::truncate (unsigned size)
 {
-  gcc_checking_assert (length () >= size);
+  unsigned l = length ();
+  gcc_checking_assert (l >= size);
+  if (!std::is_trivially_destructible <T>::value)
+    vec_destruct (address () + size, l - size);
   m_vecpfx.m_num = size;
 }
 
 
 /* Insert an element, OBJ, at the IXth position of this vector.  There
-   must be sufficient space.  */
+   must be sufficient space.  This operation is not suitable for non-trivially
+   copyable types.  */
 
 template<typename T, typename A>
 inline void
@@ -1042,6 +1086,7 @@ vec<T, A, vl_embed>::quick_insert (unsigned ix, const T &obj)
 {
   gcc_checking_assert (length () < allocated ());
   gcc_checking_assert (ix <= length ());
+  static_assert (std::is_trivially_copyable <T>::value, "");
   T *slot = &address ()[ix];
   memmove (slot + 1, slot, (m_vecpfx.m_num++ - ix) * sizeof (T));
   *slot = obj;
@@ -1050,13 +1095,14 @@ vec<T, A, vl_embed>::quick_insert (unsigned ix, const T &obj)
 
 /* Remove an element from the IXth position of this vector.  Ordering of
    remaining elements is preserved.  This is an O(N) operation due to
-   memmove.  */
+   memmove.  Not suitable for non-trivially copyable types.  */
 
 template<typename T, typename A>
 inline void
 vec<T, A, vl_embed>::ordered_remove (unsigned ix)
 {
   gcc_checking_assert (ix < length ());
+  static_assert (std::is_trivially_copyable <T>::value, "");
   T *slot = &address ()[ix];
   memmove (slot, slot + 1, (--m_vecpfx.m_num - ix) * sizeof (T));
 }
@@ -1104,6 +1150,7 @@ inline void
 vec<T, A, vl_embed>::unordered_remove (unsigned ix)
 {
   gcc_checking_assert (ix < length ());
+  static_assert (std::is_trivially_copyable <T>::value, "");
   T *p = address ();
   p[ix] = p[--m_vecpfx.m_num];
 }
@@ -1117,12 +1164,32 @@ inline void
 vec<T, A, vl_embed>::block_remove (unsigned ix, unsigned len)
 {
   gcc_checking_assert (ix + len <= length ());
+  static_assert (std::is_trivially_copyable <T>::value, "");
   T *slot = &address ()[ix];
   m_vecpfx.m_num -= len;
   memmove (slot, slot + len, (m_vecpfx.m_num - ix) * sizeof (T));
 }
 
 
+namespace vec_detail
+{
+  /* gcc_{qsort,qsort_r,stablesort_r} implementation under the hood
+     uses memcpy/memmove to reorder the array elements.
+     We want to assert these methods aren't used on types for which
+     that isn't appropriate, but unfortunately std::pair of 2 trivially
+     copyable types isn't trivially copyable and we use qsort on many
+     such std::pair instantiations.  Let's allow both trivially
+     copyable types and std::pair of 2 trivially copyable types as
+     exception for qsort/sort/stablesort.  */
+  template<typename T>
+  struct is_trivially_copyable_or_pair : std::is_trivially_copyable<T> { };
+
+  template<typename T, typename U>
+  struct is_trivially_copyable_or_pair<std::pair<T, U> >
+  : std::integral_constant<bool, std::is_trivially_copyable<T>::value
+    && std::is_trivially_copyable<U>::value> { };
+}
+
 /* Sort the contents of this vector with qsort.  CMP is the comparison
    function to pass to qsort.  */
 
@@ -1130,6 +1197,7 @@ template<typename T, typename A>
 inline void
 vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *))
 {
+  static_assert (vec_detail::is_trivially_copyable_or_pair <T>::value, "");
   if (length () > 1)
     gcc_qsort (address (), length (), sizeof (T), cmp);
 }
@@ -1142,6 +1210,7 @@ inline void
 vec<T, A, vl_embed>::sort (int (*cmp) (const void *, const void *, void *),
 			   void *data)
 {
+  static_assert (vec_detail::is_trivially_copyable_or_pair <T>::value, "");
   if (length () > 1)
     gcc_sort_r (address (), length (), sizeof (T), cmp, data);
 }
@@ -1154,6 +1223,7 @@ inline void
 vec<T, A, vl_embed>::stablesort (int (*cmp) (const void *, const void *,
 					     void *), void *data)
 {
+  static_assert (vec_detail::is_trivially_copyable_or_pair <T>::value, "");
   if (length () > 1)
     gcc_stablesort_r (address (), length (), sizeof (T), cmp, data);
 }
@@ -1326,6 +1396,7 @@ inline void
 vec<T, A, vl_embed>::quick_grow (unsigned len)
 {
   gcc_checking_assert (length () <= len && len <= m_vecpfx.m_alloc);
+//  static_assert (std::is_trivially_default_constructible <T>::value, "");
   m_vecpfx.m_num = len;
 }
 
@@ -1339,7 +1410,8 @@ vec<T, A, vl_embed>::quick_grow_cleared (unsigned len)
 {
   unsigned oldlen = length ();
   size_t growby = len - oldlen;
-  quick_grow (len);
+  gcc_checking_assert (length () <= len && len <= m_vecpfx.m_alloc);
+  m_vecpfx.m_num = len;
   if (growby != 0)
     vec_default_construct (address () + oldlen, growby);
 }
@@ -1350,6 +1422,7 @@ template<typename T>
 void
 gt_ggc_mx (vec<T, va_gc> *v)
 {
+  static_assert (std::is_trivially_destructible <T>::value, "");
   extern void gt_ggc_mx (T &);
   for (unsigned i = 0; i < v->length (); i++)
     gt_ggc_mx ((*v)[i]);
@@ -1359,6 +1432,7 @@ template<typename T>
 void
 gt_ggc_mx (vec<T, va_gc_atomic, vl_embed> *v ATTRIBUTE_UNUSED)
 {
+  static_assert (std::is_trivially_destructible <T>::value, "");
   /* Nothing to do.  Vectors of atomic types wrt GC do not need to
      be traversed.  */
 }
@@ -1518,7 +1592,10 @@ public:
   void safe_splice (const vec & CXX_MEM_STAT_INFO);
   T *quick_push (const T &);
   T *safe_push (const T &CXX_MEM_STAT_INFO);
-  T &pop (void);
+  using pop_ret_type
+    = typename std::conditional <std::is_trivially_destructible <T>::value,
+				 T &, void>::type;
+  pop_ret_type pop (void);
   void truncate (unsigned);
   void safe_grow (unsigned, bool = false CXX_MEM_STAT_INFO);
   void safe_grow_cleared (unsigned, bool = false CXX_MEM_STAT_INFO);
@@ -1627,8 +1704,8 @@ public:
 
   auto_vec& operator= (vec<T, va_heap>&& r)
     {
-	    if (this == &r)
-		    return *this;
+      if (this == &r)
+	return *this;
 
       gcc_assert (!r.using_auto_storage ());
       this->release ();
@@ -1639,8 +1716,8 @@ public:
 
   auto_vec& operator= (auto_vec<T> &&r)
     {
-	    if (this == &r)
-		    return *this;
+      if (this == &r)
+	return *this;
 
       gcc_assert (!r.using_auto_storage ());
       this->release ();
@@ -1660,7 +1737,7 @@ public:
   // You probably don't want to copy a vector, so these are deleted to prevent
   // unintentional use.  If you really need a copy of the vectors contents you
   // can use copy ().
-  auto_vec(const auto_vec &) = delete;
+  auto_vec (const auto_vec &) = delete;
   auto_vec &operator= (const auto_vec &) = delete;
 };
 
@@ -1986,10 +2063,12 @@ vec<T, va_heap, vl_ptr>::safe_push (const T &obj MEM_STAT_DECL)
 }
 
 
-/* Pop and return the last element off the end of the vector.  */
+/* Pop and return a reference to the last element off the end of the
+   vector.  If T has non-trivial destructor, this method just pops
+   last element and returns void.  */
 
 template<typename T>
-inline T &
+inline typename vec<T, va_heap, vl_ptr>::pop_ret_type
 vec<T, va_heap, vl_ptr>::pop (void)
 {
   return m_vec->pop ();
@@ -2038,10 +2117,12 @@ vec<T, va_heap, vl_ptr>::safe_grow_cleared (unsigned len, bool exact
 					    MEM_STAT_DECL)
 {
   unsigned oldlen = length ();
-  size_t growby = len - oldlen;
-  safe_grow (len, exact PASS_MEM_STAT);
-  if (growby != 0)
-    vec_default_construct (address () + oldlen, growby);
+  gcc_checking_assert (oldlen <= len);
+  reserve (len - oldlen, exact PASS_MEM_STAT);
+  if (m_vec)
+    m_vec->quick_grow_cleared (len);
+  else
+    gcc_checking_assert (len == 0);
 }