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

[Richard Biener <rguenther@suse.de>]

On Thu, 28 Sep 2023, Jakub Jelinek wrote:

> Hi!
> 
> On Wed, Sep 27, 2023 at 12:46:45PM +0200, Jakub Jelinek wrote:
> > 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.
> 
> The following patch adds the file comment, as discussed on IRC adds an
> exception for qsort/sort/stablesort such that std::pair of 2 trivially
> copyable types is also allowed, and fixes some of the grow vs. grow_cleared
> issues (on top of the bitmap_head_pod patch far more), but still not all
> yet, so I've kept that static_assert for now commented out.  Richard
> Sandiford said he's playing with poly_int_pod vs. poly_int and I'll resolve
> the remaining stuff incrementally afterwards plus enable the assert.
> 
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

OK.

Thanks,
Richard.

> 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.
> 
> --- gcc/vec.h.jj	2023-09-27 10:38:50.635845540 +0200
> +++ gcc/vec.h	2023-09-28 11:05:14.776215137 +0200
> @@ -111,6 +111,24 @@ extern void *ggc_realloc (void *, size_t
>     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 (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 +338,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 +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_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 +1040,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 +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 (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 +1095,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 +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 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 (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 +2117,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
> --- gcc/tree-ssa-loop-im.cc.jj	2023-08-21 11:57:44.403313911 +0200
> +++ gcc/tree-ssa-loop-im.cc	2023-09-27 14:21:18.486901776 +0200
> @@ -2324,7 +2324,7 @@ execute_sm (class loop *loop, im_mem_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;
> --- gcc/ipa-fnsummary.cc.jj	2023-07-11 13:40:39.158446599 +0200
> +++ gcc/ipa-fnsummary.cc	2023-09-27 13:42:53.069666030 +0200
> @@ -679,12 +679,8 @@ evaluate_properties_for_edge (struct cgr
>  		    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;
>  		      }
>  		  }
> 
> 
> 	Jakub
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)