vec.h, v3: Make some ops work with non-trivially copy constructible and/or destructible types
Checks
Commit Message
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?
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.
Jakub
Comments
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
>
>
On Thu, 28 Sept 2023 at 10:17, Jakub Jelinek <jakub@redhat.com> 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?
>
> 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)
Do GCC's coding standards really require a space before the template
argument list, like for a function parameter list?
That style doesn't seem to be used elsewhere (and is not idiomatic for
C++ at all).
> +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> >
The space in "> >" is only required in C++98, we don't need it in C++11.
> + : std::integral_constant<bool, std::is_trivially_copyable<T>::value
> + && std::is_trivially_copyable<U>::value> { };
> +}
> +
On Fri, Sep 29, 2023 at 11:00:01AM +0100, Jonathan Wakely wrote:
> > +/* 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)
>
> Do GCC's coding standards really require a space before the template
> argument list, like for a function parameter list?
> That style doesn't seem to be used elsewhere (and is not idiomatic for
> C++ at all).
Seems it is mixed, in gcc/ subdirectory:
grep ' <[a-zA-Z]' *.h *.cc */*.h */*.cc | grep -v '#.*include' | wc -l
7143
grep '[^ ]<[a-zA-Z]' *.h *.cc */*.h */*.cc | grep -v '#.*include' | wc -l
13579
> > + template<typename T, typename U>
> > + struct is_trivially_copyable_or_pair<std::pair<T, U> >
>
> The space in "> >" is only required in C++98, we don't need it in C++11.
I know, I was just following what code around used as well. Though
admittedly that is from the days where we needed C++98 compatibility.
Jakub
@@ -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);
}
@@ -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
@@ -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;
@@ -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;
}
}