* [PATCH] vec.h: Make some ops work with non-trivially copy constructible and/or destructible types
@ 2023-09-27 5:03 Jakub Jelinek
2023-09-27 7:17 ` Richard Biener
0 siblings, 1 reply; 11+ messages in thread
From: Jakub Jelinek @ 2023-09-27 5:03 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches, Jonathan Wakely
Hi!
We have some very limited support for non-POD types in vec.h
(in particular grow_cleared will invoke default ctors on the
cleared elements and vector copying invokes copy ctors.
My pending work on wide_int/widest_int which makes those two
non-trivially default/copy constructible, assignable and destructible
shows this isn't enough though.
In particular the uses of it in irange shows that quick_push
still uses just assignment operator rather than copy construction
and we never invoke destructors on anything.
The following patch does that for quick_push (copy construction
using placement new rather than assignment, for trivially copy
constructible types I think it should be the same) and invokes
destructors (only if non-trivially destructible) in pop, release
and truncate. Now as discussed last night on IRC, the pop case
is problematic, because our pop actually does two things,
it decreases length (so the previous last element should be destructed)
but also returns a reference to it. We have some 300+ uses of this
and the reference rather than returning it by value is useful at least
for the elements which are (larger) POD structures, so I'm not
prepared to change that. Though obviously for types with non-trivial
destructors returning a reference to just destructed element is not
a good idea. So, this patch for that case only makes pop return void
instead and any users wishing to get the last element need to use last ()
and pop () separately (currently there are none).
Note, a lot of vec.h operations is still not friendly for non-POD types,
I've added a comment for quick_insert and ordered_remove, but qsort is
such a case as well and in fact most others too. For non-POD, I'd say
with this patch it is safe just to {quick,safe}_grow_cleared (but not
just *_grow), {quick,safe}_push, pop, truncate, release, copy
them around and ops which do not add/remove any elements or move them
around. And obviously using non-trivially destructible types in
va_gc vectors is undesirable as well.
Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
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.
(quick_insert, ordered_remove): Note that they aren't suitable
for non-PODs.
(pop): For non-trivially destructible T return void
rather than T & and destruct the popped element.
* edit-context.cc (class line_event): Move definition earlier.
--- gcc/vec.h.jj 2023-09-26 16:44:30.637902359 +0200
+++ gcc/vec.h 2023-09-26 21:17:30.366534474 +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);
@@ -1005,19 +1021,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 +1049,16 @@ 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-PODs. */
template<typename T, typename A>
inline void
@@ -1050,7 +1074,7 @@ 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-PODs. */
template<typename T, typename A>
inline void
@@ -1518,7 +1542,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);
@@ -1986,10 +2013,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 ();
--- gcc/edit-context.cc.jj 2023-01-02 09:32:43.106985882 +0100
+++ gcc/edit-context.cc 2023-09-26 19:39:20.213374419 +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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH] vec.h: Make some ops work with non-trivially copy constructible and/or destructible types
2023-09-27 5:03 [PATCH] vec.h: Make some ops work with non-trivially copy constructible and/or destructible types Jakub Jelinek
@ 2023-09-27 7:17 ` Richard Biener
2023-09-27 10:46 ` [PATCH] vec.h, v2: " Jakub Jelinek
0 siblings, 1 reply; 11+ messages in thread
From: Richard Biener @ 2023-09-27 7:17 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: gcc-patches, Jonathan Wakely
On Wed, 27 Sep 2023, Jakub Jelinek wrote:
> Hi!
>
> We have some very limited support for non-POD types in vec.h
> (in particular grow_cleared will invoke default ctors on the
> cleared elements and vector copying invokes copy ctors.
>
> My pending work on wide_int/widest_int which makes those two
> non-trivially default/copy constructible, assignable and destructible
> shows this isn't enough though.
> In particular the uses of it in irange shows that quick_push
> still uses just assignment operator rather than copy construction
> and we never invoke destructors on anything.
>
> The following patch does that for quick_push (copy construction
> using placement new rather than assignment, for trivially copy
> constructible types I think it should be the same) and invokes
> destructors (only if non-trivially destructible) in pop, release
> and truncate. Now as discussed last night on IRC, the pop case
> is problematic, because our pop actually does two things,
> it decreases length (so the previous last element should be destructed)
> but also returns a reference to it. We have some 300+ uses of this
> and the reference rather than returning it by value is useful at least
> for the elements which are (larger) POD structures, so I'm not
> prepared to change that. Though obviously for types with non-trivial
> destructors returning a reference to just destructed element is not
> a good idea. So, this patch for that case only makes pop return void
> instead and any users wishing to get the last element need to use last ()
> and pop () separately (currently there are none).
>
> Note, a lot of vec.h operations is still not friendly for non-POD types,
> I've added a comment for quick_insert and ordered_remove, but qsort is
> such a case as well and in fact most others too. For non-POD, I'd say
> with this patch it is safe just to {quick,safe}_grow_cleared (but not
> just *_grow), {quick,safe}_push, pop, truncate, release, copy
> them around and ops which do not add/remove any elements or move them
> around. And obviously using non-trivially destructible types in
> va_gc vectors is undesirable as well.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
OK I guess. Can you summarize the limitations for non-POD types
in the big comment at the start of vec.h? (can we put in static_asserts
in the places that obviously do not work?)
Thanks,
Richard.
> 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.
> (quick_insert, ordered_remove): Note that they aren't suitable
> for non-PODs.
> (pop): For non-trivially destructible T return void
> rather than T & and destruct the popped element.
> * edit-context.cc (class line_event): Move definition earlier.
>
> --- gcc/vec.h.jj 2023-09-26 16:44:30.637902359 +0200
> +++ gcc/vec.h 2023-09-26 21:17:30.366534474 +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);
> @@ -1005,19 +1021,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 +1049,16 @@ 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-PODs. */
>
> template<typename T, typename A>
> inline void
> @@ -1050,7 +1074,7 @@ 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-PODs. */
>
> template<typename T, typename A>
> inline void
> @@ -1518,7 +1542,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);
> @@ -1986,10 +2013,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 ();
> --- gcc/edit-context.cc.jj 2023-01-02 09:32:43.106985882 +0100
> +++ gcc/edit-context.cc 2023-09-26 19:39:20.213374419 +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 <rguenther@suse.de>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Ivo Totev, Andrew McDonald, Werner Knoblich; (HRB 36809, AG Nuernberg)
^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH] vec.h, v2: Make some ops work with non-trivially copy constructible and/or destructible types
2023-09-27 7:17 ` Richard Biener
@ 2023-09-27 10:46 ` Jakub Jelinek
2023-09-27 11:15 ` Richard Biener
` (2 more replies)
0 siblings, 3 replies; 11+ messages in thread
From: Jakub Jelinek @ 2023-09-27 10:46 UTC (permalink / raw)
To: Richard Biener, Jonathan Wakely, Richard Sandiford; +Cc: gcc-patches
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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH] vec.h, v2: Make some ops work with non-trivially copy constructible and/or destructible types
2023-09-27 10:46 ` [PATCH] vec.h, v2: " Jakub Jelinek
@ 2023-09-27 11:15 ` Richard Biener
2023-09-29 8:57 ` [PATCH] use *_grow_cleared rather than *_grow on vect_unpromoted_value Jakub Jelinek
2023-09-27 13:15 ` [PATCH] vec.h, v2: Make some ops work with non-trivially copy constructible and/or destructible types Mikael Morin
2023-09-28 9:17 ` [PATCH] vec.h, v3: " Jakub Jelinek
2 siblings, 1 reply; 11+ messages in thread
From: Richard Biener @ 2023-09-27 11:15 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: Jonathan Wakely, Richard Sandiford, gcc-patches
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 <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
>
>
--
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)
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH] vec.h, v2: Make some ops work with non-trivially copy constructible and/or destructible types
2023-09-27 10:46 ` [PATCH] vec.h, v2: " Jakub Jelinek
2023-09-27 11:15 ` Richard Biener
@ 2023-09-27 13:15 ` Mikael Morin
2023-09-28 9:17 ` [PATCH] vec.h, v3: " Jakub Jelinek
2 siblings, 0 replies; 11+ messages in thread
From: Mikael Morin @ 2023-09-27 13:15 UTC (permalink / raw)
To: Jakub Jelinek, Richard Biener, Jonathan Wakely, Richard Sandiford
Cc: gcc-patches
Hello,
Le 27/09/2023 à 12:46, Jakub Jelinek a écrit :
> --- gcc/vec.h.jj 2023-09-27 10:38:50.635845540 +0200
> +++ gcc/vec.h 2023-09-27 12:11:56.665586490 +0200
> @@ -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);
Shouldn't this line be:
vec_destruct (address () + *size*, l - size);
instead?
> m_vecpfx.m_num = size;
> }
>
>
^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH] vec.h, v3: Make some ops work with non-trivially copy constructible and/or destructible types
2023-09-27 10:46 ` [PATCH] vec.h, v2: " Jakub Jelinek
2023-09-27 11:15 ` Richard Biener
2023-09-27 13:15 ` [PATCH] vec.h, v2: Make some ops work with non-trivially copy constructible and/or destructible types Mikael Morin
@ 2023-09-28 9:17 ` Jakub Jelinek
2023-09-28 9:30 ` Richard Biener
2023-09-29 10:00 ` Jonathan Wakely
2 siblings, 2 replies; 11+ messages in thread
From: Jakub Jelinek @ 2023-09-28 9:17 UTC (permalink / raw)
To: Richard Biener, Jonathan Wakely, Richard Sandiford; +Cc: gcc-patches
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)
+ 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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH] vec.h, v3: Make some ops work with non-trivially copy constructible and/or destructible types
2023-09-28 9:17 ` [PATCH] vec.h, v3: " Jakub Jelinek
@ 2023-09-28 9:30 ` Richard Biener
2023-09-29 10:00 ` Jonathan Wakely
1 sibling, 0 replies; 11+ messages in thread
From: Richard Biener @ 2023-09-28 9:30 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: Jonathan Wakely, Richard Sandiford, gcc-patches
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)
^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH] use *_grow_cleared rather than *_grow on vect_unpromoted_value
2023-09-27 11:15 ` Richard Biener
@ 2023-09-29 8:57 ` Jakub Jelinek
2023-09-29 9:13 ` Richard Biener
0 siblings, 1 reply; 11+ messages in thread
From: Jakub Jelinek @ 2023-09-29 8:57 UTC (permalink / raw)
To: Richard Biener; +Cc: Jonathan Wakely, Richard Sandiford, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1788 bytes --]
On Wed, Sep 27, 2023 at 11:15:26AM +0000, Richard Biener wrote:
> > 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 ...
So, I had a look at this and I think using quick_grow_cleared is best choice
here. The nops is 2 or 1 most of the time, worst case 3, so the price of
extra initialization of 4 pointer-sized-or-less members times 1, 2 or 3
doesn't seem worth bothering, it is similar to the bitmap_head case where
we already pay the price for just one structure anytime we do
vect_unpromoted_value unprom_diff;
(and later set_op on it) or even
vect_unpromoted_value unprom0[2];
With this patch and Richard S's poly_int_pod removal the static_assert can
be enabled as well and gcc builds.
Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
The second patch waits for the poly_int_pod removal commit and has been just
build tested but not bootstrapped yet.
2023-09-29 Jakub Jelinek <jakub@redhat.com>
* tree-vect-patterns.cc (vect_recog_over_widening_pattern): Use
quick_grow_cleared method on unprom rather than quick_grow.
--- gcc/tree-vect-patterns.cc.jj 2023-08-24 15:37:29.321410276 +0200
+++ gcc/tree-vect-patterns.cc 2023-09-29 09:45:27.980168865 +0200
@@ -2944,7 +2944,7 @@ vect_recog_over_widening_pattern (vec_in
/* Check the operands. */
unsigned int nops = gimple_num_ops (last_stmt) - first_op;
auto_vec <vect_unpromoted_value, 3> unprom (nops);
- unprom.quick_grow (nops);
+ unprom.quick_grow_cleared (nops);
unsigned int min_precision = 0;
bool single_use_p = false;
for (unsigned int i = 0; i < nops; ++i)
Jakub
[-- Attachment #2: Q017 --]
[-- Type: text/plain, Size: 536 bytes --]
2023-09-29 Jakub Jelinek <jakub@redhat.com>
* vec.h (quick_grow): Uncomment static_assert.
--- gcc/vec.h.jj 2023-09-29 10:39:09.327223861 +0200
+++ gcc/vec.h 2023-09-29 10:44:03.764108443 +0200
@@ -1396,7 +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, "");
+ static_assert (std::is_trivially_default_constructible <T>::value, "");
m_vecpfx.m_num = len;
}
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH] use *_grow_cleared rather than *_grow on vect_unpromoted_value
2023-09-29 8:57 ` [PATCH] use *_grow_cleared rather than *_grow on vect_unpromoted_value Jakub Jelinek
@ 2023-09-29 9:13 ` Richard Biener
0 siblings, 0 replies; 11+ messages in thread
From: Richard Biener @ 2023-09-29 9:13 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: Jonathan Wakely, Richard Sandiford, gcc-patches
On Fri, 29 Sep 2023, Jakub Jelinek wrote:
> On Wed, Sep 27, 2023 at 11:15:26AM +0000, Richard Biener wrote:
> > > 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 ...
>
> So, I had a look at this and I think using quick_grow_cleared is best choice
> here. The nops is 2 or 1 most of the time, worst case 3, so the price of
> extra initialization of 4 pointer-sized-or-less members times 1, 2 or 3
> doesn't seem worth bothering, it is similar to the bitmap_head case where
> we already pay the price for just one structure anytime we do
> vect_unpromoted_value unprom_diff;
> (and later set_op on it) or even
> vect_unpromoted_value unprom0[2];
>
> With this patch and Richard S's poly_int_pod removal the static_assert can
> be enabled as well and gcc builds.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
OK.
> The second patch waits for the poly_int_pod removal commit and has been just
> build tested but not bootstrapped yet.
>
> 2023-09-29 Jakub Jelinek <jakub@redhat.com>
>
> * tree-vect-patterns.cc (vect_recog_over_widening_pattern): Use
> quick_grow_cleared method on unprom rather than quick_grow.
>
> --- gcc/tree-vect-patterns.cc.jj 2023-08-24 15:37:29.321410276 +0200
> +++ gcc/tree-vect-patterns.cc 2023-09-29 09:45:27.980168865 +0200
> @@ -2944,7 +2944,7 @@ vect_recog_over_widening_pattern (vec_in
> /* Check the operands. */
> unsigned int nops = gimple_num_ops (last_stmt) - first_op;
> auto_vec <vect_unpromoted_value, 3> unprom (nops);
> - unprom.quick_grow (nops);
> + unprom.quick_grow_cleared (nops);
> unsigned int min_precision = 0;
> bool single_use_p = false;
> for (unsigned int i = 0; i < nops; ++i)
>
>
> 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)
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH] vec.h, v3: Make some ops work with non-trivially copy constructible and/or destructible types
2023-09-28 9:17 ` [PATCH] vec.h, v3: " Jakub Jelinek
2023-09-28 9:30 ` Richard Biener
@ 2023-09-29 10:00 ` Jonathan Wakely
2023-09-29 10:07 ` Jakub Jelinek
1 sibling, 1 reply; 11+ messages in thread
From: Jonathan Wakely @ 2023-09-29 10:00 UTC (permalink / raw)
To: Jakub Jelinek; +Cc: Richard Biener, Richard Sandiford, gcc-patches
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> { };
> +}
> +
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH] vec.h, v3: Make some ops work with non-trivially copy constructible and/or destructible types
2023-09-29 10:00 ` Jonathan Wakely
@ 2023-09-29 10:07 ` Jakub Jelinek
0 siblings, 0 replies; 11+ messages in thread
From: Jakub Jelinek @ 2023-09-29 10:07 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: Richard Biener, Richard Sandiford, gcc-patches
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
^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2023-09-29 10:07 UTC | newest]
Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-09-27 5:03 [PATCH] vec.h: Make some ops work with non-trivially copy constructible and/or destructible types Jakub Jelinek
2023-09-27 7:17 ` Richard Biener
2023-09-27 10:46 ` [PATCH] vec.h, v2: " Jakub Jelinek
2023-09-27 11:15 ` Richard Biener
2023-09-29 8:57 ` [PATCH] use *_grow_cleared rather than *_grow on vect_unpromoted_value Jakub Jelinek
2023-09-29 9:13 ` Richard Biener
2023-09-27 13:15 ` [PATCH] vec.h, v2: Make some ops work with non-trivially copy constructible and/or destructible types Mikael Morin
2023-09-28 9:17 ` [PATCH] vec.h, v3: " Jakub Jelinek
2023-09-28 9:30 ` Richard Biener
2023-09-29 10:00 ` Jonathan Wakely
2023-09-29 10:07 ` Jakub Jelinek
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).