vec.h: Make some ops work with non-trivially copy constructible and/or destructible...

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 --git a/gcc/edit-context.cc b/gcc/edit-context.cc
index 6f5bc6b9d8f42e50b7e41ae797524299f10dc66f..09b000c74c42811ad2d86a7d32e1c6ff02d5bce0 100644 (file)
--- 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 f1244da291ca51713e4934b1ef6b9306137990b9..a2495ffe63e143dfe4a2ef37f2e43c94f6c1f927 100644 (file)
--- 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 b8e33a4d49a131c422eacb1754ca55d9564ae9d4..6931b61f54ed01c51fb2d536b70f059392bbb1b9 100644 (file)
--- 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 8a9a8d83de51896fb02f91ea942386d614fe09b4..8aacb5a8defa8e762750123c00757bb65ae084bc 100644 (file)
--- 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);
 }