On Wed, 27 Sep 2023, 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.
>
> 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
make an exception as discussed on IRC
> 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.
I've added the CTOR for checking purposes, I suppose we can add
a bitmap_head_pod omitting it?
> 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.
Possibly? It's also a pattern that might go into vec:: directly,
it's a splice_at (aka insert other vector at position). Using
safe_grow_cleared would be OK here.
>
> 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?
That's vec_perm_builder in the end, maybe yes, poly_int_pod would work
there.
> tree-vect-patterns.cc:2947 unprom.quick_grow (nops);
> T = vect_unpromoted_value
> Go for quick_grow_cleared? Something else?
The CTOR zero-initializes everything, so maybe it can go. In theory
.set_op could also be changed to .push_op ...
> 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?
I guess so. I fail to know the difference between both.
>
> 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?
It does
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 ();
if that's then semantically the same yes.
Richard.
> 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 <ja...@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
>
>
--
Richard Biener <rguent...@suse.de>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)
