From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 9F7C13858D20 for ; Thu, 28 Sep 2023 09:17:08 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 9F7C13858D20 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1695892628; h=from:from:reply-to:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type:in-reply-to:in-reply-to: references:references; bh=zun1wIYc/75bBH2Hg9+WqHLfyfHXAYlXMjpcE/kbSp4=; b=XfScDaEVYMJUyVSql57FwZqDDcVQTZYaFuE4WwJIfdyIlqJ4dAAq1waPMAkFaZ/hAdn3+Z FVMd8nIM8DsO97I73Exhks5VEzIHJXW85GvfzQOMp2gZ8gbgmWcmUoRmLGAjDnNzvDoXyo 4XVvl4dpQ9XbNy6xC+YAHChI9kRDLu0= Received: from mimecast-mx02.redhat.com (mx-ext.redhat.com [66.187.233.73]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-604-8-e-xfL5MDmaChEGYJZwPw-1; Thu, 28 Sep 2023 05:17:05 -0400 X-MC-Unique: 8-e-xfL5MDmaChEGYJZwPw-1 Received: from smtp.corp.redhat.com (int-mx05.intmail.prod.int.rdu2.redhat.com [10.11.54.5]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id 9FBE938125A7; Thu, 28 Sep 2023 09:17:04 +0000 (UTC) Received: from tucnak.zalov.cz (unknown [10.39.193.202]) by smtp.corp.redhat.com (Postfix) with ESMTPS id E9D7A170EC; Thu, 28 Sep 2023 09:17:03 +0000 (UTC) Received: from tucnak.zalov.cz (localhost [127.0.0.1]) by tucnak.zalov.cz (8.17.1/8.17.1) with ESMTPS id 38S9H1uh2638716 (version=TLSv1.3 cipher=TLS_AES_256_GCM_SHA384 bits=256 verify=NOT); Thu, 28 Sep 2023 11:17:01 +0200 Received: (from jakub@localhost) by tucnak.zalov.cz (8.17.1/8.17.1/Submit) id 38S9H0l62638715; Thu, 28 Sep 2023 11:17:00 +0200 Date: Thu, 28 Sep 2023 11:17:00 +0200 From: Jakub Jelinek To: Richard Biener , Jonathan Wakely , Richard Sandiford Cc: gcc-patches@gcc.gnu.org Subject: [PATCH] vec.h, v3: Make some ops work with non-trivially copy constructible and/or destructible types Message-ID: Reply-To: Jakub Jelinek References: MIME-Version: 1.0 In-Reply-To: X-Scanned-By: MIMEDefang 3.1 on 10.11.54.5 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=us-ascii Content-Disposition: inline X-Spam-Status: No, score=-0.9 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H3,RCVD_IN_MSPIKE_WL,RCVD_IN_SBL_CSS,SPF_HELO_NONE,SPF_NONE,TXREP autolearn=no autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: 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 Jonathan Wakely * 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) @@ -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 +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::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 ::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 (vecaddress () + 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::quick_push (const T { gcc_checking_assert (space (1)); T *slot = &address ()[m_vecpfx.m_num++]; - *slot = obj; + ::new (static_cast(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 -inline T & +inline typename vec::pop_ret_type vec::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 ::value) + last.~T (); + return static_cast (last); } @@ -1028,13 +1068,17 @@ template inline void vec::truncate (unsigned size) { - gcc_checking_assert (length () >= size); + unsigned l = length (); + gcc_checking_assert (l >= size); + if (!std::is_trivially_destructible ::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 inline void @@ -1042,6 +1086,7 @@ vec::quick_insert (unsig { gcc_checking_assert (length () < allocated ()); gcc_checking_assert (ix <= length ()); + static_assert (std::is_trivially_copyable ::value, ""); T *slot = &address ()[ix]; memmove (slot + 1, slot, (m_vecpfx.m_num++ - ix) * sizeof (T)); *slot = obj; @@ -1050,13 +1095,14 @@ vec::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 inline void vec::ordered_remove (unsigned ix) { gcc_checking_assert (ix < length ()); + static_assert (std::is_trivially_copyable ::value, ""); T *slot = &address ()[ix]; memmove (slot, slot + 1, (--m_vecpfx.m_num - ix) * sizeof (T)); } @@ -1104,6 +1150,7 @@ inline void vec::unordered_remove (unsigned ix) { gcc_checking_assert (ix < length ()); + static_assert (std::is_trivially_copyable ::value, ""); T *p = address (); p[ix] = p[--m_vecpfx.m_num]; } @@ -1117,12 +1164,32 @@ inline void vec::block_remove (unsigned ix, unsigned len) { gcc_checking_assert (ix + len <= length ()); + static_assert (std::is_trivially_copyable ::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 + struct is_trivially_copyable_or_pair : std::is_trivially_copyable { }; + + template + struct is_trivially_copyable_or_pair > + : std::integral_constant::value + && std::is_trivially_copyable::value> { }; +} + /* Sort the contents of this vector with qsort. CMP is the comparison function to pass to qsort. */ @@ -1130,6 +1197,7 @@ template inline void vec::qsort (int (*cmp) (const void *, const void *)) { + static_assert (vec_detail::is_trivially_copyable_or_pair ::value, ""); if (length () > 1) gcc_qsort (address (), length (), sizeof (T), cmp); } @@ -1142,6 +1210,7 @@ inline void vec::sort (int (*cmp) (const void *, const void *, void *), void *data) { + static_assert (vec_detail::is_trivially_copyable_or_pair ::value, ""); if (length () > 1) gcc_sort_r (address (), length (), sizeof (T), cmp, data); } @@ -1154,6 +1223,7 @@ inline void vec::stablesort (int (*cmp) (const void *, const void *, void *), void *data) { + static_assert (vec_detail::is_trivially_copyable_or_pair ::value, ""); if (length () > 1) gcc_stablesort_r (address (), length (), sizeof (T), cmp, data); } @@ -1326,6 +1396,7 @@ inline void vec::quick_grow (unsigned len) { gcc_checking_assert (length () <= len && len <= m_vecpfx.m_alloc); +// static_assert (std::is_trivially_default_constructible ::value, ""); m_vecpfx.m_num = len; } @@ -1339,7 +1410,8 @@ vec::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 void gt_ggc_mx (vec *v) { + static_assert (std::is_trivially_destructible ::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 void gt_ggc_mx (vec *v ATTRIBUTE_UNUSED) { + static_assert (std::is_trivially_destructible ::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 ::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&& 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 &&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::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 -inline T & +inline typename vec::pop_ret_type vec::pop (void) { return m_vec->pop (); @@ -2038,10 +2117,12 @@ vec::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 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