[PATCH] vec.h, v2: Make some ops work with non-trivially copy constructible and/or destructible types

[Jakub Jelinek <jakub@redhat.com>]

On Wed, Sep 27, 2023 at 07:17:22AM +0000, Richard Biener wrote:
> OK I guess.  Can you summarize the limitations for non-POD types
> in the big comment at the start of vec.h?

Still haven't done that, but will do after we flesh out the details
below.

> (can we put in static_asserts
> in the places that obviously do not work?)

I've tried to do this though, I think the static_asserts will allow
making sure we only use what is supportable and will serve better than
any kind of comment.

But, I've run into quite a few triggered assertion failures with that, and
the question is what we want to do with them.  Applying
--- gcc/vec.h.jj	2023-09-27 12:11:56.000000000 +0200
+++ gcc/vec.h	2023-09-27 12:39:50.971613964 +0200
@@ -1160,7 +1160,7 @@ template<typename T, typename A>
 inline void
 vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *))
 {
-  static_assert (std::is_trivially_copyable <T>::value, "");
+//  static_assert (std::is_trivially_copyable <T>::value, "");
   if (length () > 1)
     gcc_qsort (address (), length (), sizeof (T), cmp);
 }
@@ -1359,7 +1359,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, "");
+//  static_assert (std::is_trivially_default_constructible <T>::value, "");
   m_vecpfx.m_num = len;
 }
 
incremental patch makes stuff work (at lest make in gcc subdir for
x86_64-linux with --enable-languages=c,c++,fortran,lto succeeds), so it is just
those 2 asserts.
Following is full list of failures and discusses details.

dbgcnt.cc:132  limits[index].qsort (cmp_tuples);
T = std::pair<unsigned int, unsigned int>
where std::pair is not trivially copyable.  Our qsort implementation uses
memcpys/memmoves to reshuffle the array elements (as it isn't inlined and
so can't use std::swap and the like), so I think we need the types trivially
copyable (or at least trivially copy assignable from the same type or
something similar if we close all eyes).  Is there some std::pair
alternative which is trivially copyable, or do we need to define structures
to achieve that?  Or just close all eyes and allow qsort/sort/stablesort
either on trivially copyable types, or on std::pair where both template
parameters are trivially copyable?

genrecog.cc:3466      candidates.qsort (subroutine_candidate_cmp);
T = std::pair<transition*, state_size>
ditto

dwarf2asm.cc:1061  temp.qsort (compare_strings);
T = std::pair<const char*, tree_node*>
ditto

tree-ssa-dce.cc:1776      args.qsort (sort_phi_args);
T = std::pair<edge_def*, unsigned int>
ditto

tree-ssa-loop-manip.cc:376  names.qsort (loop_name_cmp);
T = std::pair<int, int>
ditto

omp-oacc-neuter-broadcast.cc:1730  priority.qsort (sort_size_descending);
T = std::pair<int, tree_node*>
ditto

ipa-icf.cc:3087  to_split.qsort (sort_congruence_split);
T = std::pair<ipa_icf::congruence_class*, bitmap_head*>
ditto

ipa-icf.cc:3360  classes.qsort (sort_congruence_class_groups_by_decl_uid);
T = std::pair<ipa_icf::congruence_class_group*, int>
ditto

tree-vect-slp.cc:6991  li_scalar_costs.qsort (li_cost_vec_cmp);
T = std::pair<unsigned int, stmt_info_for_cost*>
ditto

tree-vect-slp.cc:7249              lane_defs.qsort (vld_cmp);
T = std::pair<unsigned int, tree_node*>
ditto

cfganal.cc:471  control_dependence_map.quick_grow (last_basic_block_for_fn (cfun));
T = bitmap_head
This is a different case, bitmap_head has a non-trivial default constructor
that essentially fills it with zeros, and for quick_grow we have
quick_grow_cleared which default constructs elements, but quick_grow leaves
them unconstructed/uninitialized, which is why I wanted to add an assert
there, e.g. quick_grow on the wide_int/widest_int WIP would break stuff
terribly.  In the cfganal.cc case, we call bitmap_initialize on it after
growing it, which overwrites all elements and doesn't depend on values of
any, so grow_cleared actually is invalid from strict C++ POV, but not
in reality.  Do we still want the assert in and slow cfganal.cc slightly
by using quick_grow_cleared?  Or another option would be to make
quick_grow work transparently the same as quick_grow_cleared for
non-trivially default constructible types.  Though, I think it might be
better if people explicitly see that the operation is more expensive.

tree-ssa-loop-im.cc:2592                      first_edge_seq.safe_grow (fes_length
			                                                + extra_refs.length ());
T = seq_entry
Here, seq_entry is:
struct seq_entry
{
  seq_entry () {}
  seq_entry (unsigned f, sm_kind k, tree fr = NULL)
    : first (f), second (k), from (fr) {}
  unsigned first;
  sm_kind second;
  tree from;
};
Wonder if making seq_entry () = default;
wouldn't cure this.

tree-ssa-loop-im.cc:3499  memory_accesses.refs_loaded_in_loop.quick_grow (number_of_loops (cfun));
T = bitmap_head
like the cfganal.cc case.

tree-ssa-live.cc:1364  active.quick_grow (last_basic_block_for_fn (fn));
T = bitmap_head
ditto

rtl-ssa/blocks.cc:60  bb_phis.quick_grow (num_bb_indices);
T = rtl_ssa::function_info::bb_phi_info
This structure contains bitmap_head, so again isn't default constructible.

rtl-ssa/blocks.cc:617  frontiers.safe_grow (num_bb_indices);
T = bitmap_head
see above

tree-vect-data-refs.cc:5369          sel.quick_grow (nelt);
T = poly_int<1, long int>
Should this use poly_int_pod<1, long int> instead?  Or quick_grow_cleared?

tree-vect-patterns.cc:2947  unprom.quick_grow (nops);
T = vect_unpromoted_value
Go for quick_grow_cleared?  Something else?

tree-ssa-sccvn.cc:5562                accesses.quick_grow (accesses.length () + 1);
T = ao_ref
This isn't trivially copyable because of 3 poly_int64 members I believe. 
Shall those be poly_int64_pod?

tree-vect-stmts.cc:2811      sel.quick_grow (count);
T = poly_int<1, long int>
see above

ipa-fnsummary.cc:683                            avals->m_known_value_ranges.safe_grow (count, true);
T = Value_Range
Go for cleared?

tree-vect-slp.cc:8344  mask.quick_grow (count);
T = poly_int<1, long int>
see above

tree-vect-loop.cc:9042        sel.quick_grow (6);
T = poly_int<1, long int>
see above

config/i386/sse.md:16172          sel.quick_grow (8);
T = poly_int<1, long int>
see above

2023-09-27  Jakub Jelinek  <jakub@redhat.com>

	* vec.h (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, qsort, sort, stablesort): Assert T is trivially
	copyable.
	(quick_grow): Assert T is trivially default constructible.
	(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.

--- gcc/vec.h.jj	2023-09-27 10:38:50.635845540 +0200
+++ gcc/vec.h	2023-09-27 12:11:56.665586490 +0200
@@ -185,6 +185,16 @@ extern void dump_vec_loc_statistics (voi
 /* 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 +320,9 @@ va_heap::release (vec<T, va_heap, vl_emb
   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 +601,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 +751,9 @@ vec_safe_grow_cleared (vec<T, A, vl_embe
 		       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 +1022,24 @@ vec<T, A, vl_embed>::quick_push (const T
 {
   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 +1050,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 () + l, 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 +1068,7 @@ vec<T, A, vl_embed>::quick_insert (unsig
 {
   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 +1077,14 @@ vec<T, A, vl_embed>::quick_insert (unsig
 
 /* 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 +1132,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,6 +1146,7 @@ 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));
@@ -1130,6 +1160,7 @@ template<typename T, typename A>
 inline void
 vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *))
 {
+  static_assert (std::is_trivially_copyable <T>::value, "");
   if (length () > 1)
     gcc_qsort (address (), length (), sizeof (T), cmp);
 }
@@ -1142,6 +1173,7 @@ inline void
 vec<T, A, vl_embed>::sort (int (*cmp) (const void *, const void *, void *),
 			   void *data)
 {
+  static_assert (std::is_trivially_copyable <T>::value, "");
   if (length () > 1)
     gcc_sort_r (address (), length (), sizeof (T), cmp, data);
 }
@@ -1154,6 +1186,7 @@ inline void
 vec<T, A, vl_embed>::stablesort (int (*cmp) (const void *, const void *,
 					     void *), void *data)
 {
+  static_assert (std::is_trivially_copyable <T>::value, "");
   if (length () > 1)
     gcc_stablesort_r (address (), length (), sizeof (T), cmp, data);
 }
@@ -1326,6 +1359,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 +1373,8 @@ vec<T, A, vl_embed>::quick_grow_cleared
 {
   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 +1385,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 +1395,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 +1555,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 +1667,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 +1679,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 +1700,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 +2026,12 @@ vec<T, va_heap, vl_ptr>::safe_push (cons
 }
 
 
-/* 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 +2080,12 @@ vec<T, va_heap, vl_ptr>::safe_grow_clear
 					    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);
 }
 
 
--- gcc/edit-context.cc.jj	2023-09-27 10:37:38.600848724 +0200
+++ gcc/edit-context.cc	2023-09-27 10:40:04.834812220 +0200
@@ -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

	Jakub