After gcc commit 6f00ccbad3d72a39d9e2bc0d500dbd62d1abc60f Author: François Dumont fdumont@gcc.gnu.org

libstdc++: Fix and improve std::vector<bool> implementation.

the following benchmarks grew in size by more than 1%: - 447.dealII grew in size by 2% from 348834 to 356146 bytes

Below reproducer instructions can be used to re-build both "first_bad" and "last_good" cross-toolchains used in this bisection. Naturally, the scripts will fail when triggerring benchmarking jobs if you don't have access to Linaro TCWG CI.

For your convenience, we have uploaded tarballs with pre-processed source and assembly files at: - First_bad save-temps: https://ci.linaro.org/job/tcwg_bmk_ci_llvm-bisect-tcwg_bmk_apm-llvm-release-... - Last_good save-temps: https://ci.linaro.org/job/tcwg_bmk_ci_llvm-bisect-tcwg_bmk_apm-llvm-release-... - Baseline save-temps: https://ci.linaro.org/job/tcwg_bmk_ci_llvm-bisect-tcwg_bmk_apm-llvm-release-...

Configuration: - Benchmark: SPEC CPU2006 - Toolchain: Clang + Glibc + LLVM Linker - Version: all components were built from their latest release branch - Target: aarch64-linux-gnu - Compiler flags: -Os -flto - Hardware: APM Mustang 8x X-Gene1

This benchmarking CI is work-in-progress, and we welcome feedback and suggestions at linaro-toolchain@lists.linaro.org . In our improvement plans is to add support for SPEC CPU2017 benchmarks and provide "perf report/annotate" data behind these reports.

THIS IS THE END OF INTERESTING STUFF. BELOW ARE LINKS TO BUILDS, REPRODUCTION INSTRUCTIONS, AND THE RAW COMMIT.

This commit has regressed these CI configurations: - tcwg_bmk_llvm_apm/llvm-release-aarch64-spec2k6-Os_LTO

First_bad build: https://ci.linaro.org/job/tcwg_bmk_ci_llvm-bisect-tcwg_bmk_apm-llvm-release-... Last_good build: https://ci.linaro.org/job/tcwg_bmk_ci_llvm-bisect-tcwg_bmk_apm-llvm-release-... Baseline build: https://ci.linaro.org/job/tcwg_bmk_ci_llvm-bisect-tcwg_bmk_apm-llvm-release-... Even more details: https://ci.linaro.org/job/tcwg_bmk_ci_llvm-bisect-tcwg_bmk_apm-llvm-release-...

Reproduce builds: <cut> mkdir investigate-gcc-6f00ccbad3d72a39d9e2bc0d500dbd62d1abc60f cd investigate-gcc-6f00ccbad3d72a39d9e2bc0d500dbd62d1abc60f

# Fetch scripts git clone https://git.linaro.org/toolchain/jenkins-scripts

# Fetch manifests and test.sh script mkdir -p artifacts/manifests curl -o artifacts/manifests/build-baseline.sh https://ci.linaro.org/job/tcwg_bmk_ci_llvm-bisect-tcwg_bmk_apm-llvm-release-... --fail curl -o artifacts/manifests/build-parameters.sh https://ci.linaro.org/job/tcwg_bmk_ci_llvm-bisect-tcwg_bmk_apm-llvm-release-... --fail curl -o artifacts/test.sh https://ci.linaro.org/job/tcwg_bmk_ci_llvm-bisect-tcwg_bmk_apm-llvm-release-... --fail chmod +x artifacts/test.sh

# Reproduce the baseline build (build all pre-requisites) ./jenkins-scripts/tcwg_bmk-build.sh @@ artifacts/manifests/build-baseline.sh

# Save baseline build state (which is then restored in artifacts/test.sh) mkdir -p ./bisect rsync -a --del --delete-excluded --exclude /bisect/ --exclude /artifacts/ --exclude /gcc/ ./ ./bisect/baseline/

cd gcc

# Reproduce first_bad build git checkout --detach 6f00ccbad3d72a39d9e2bc0d500dbd62d1abc60f ../artifacts/test.sh

# Reproduce last_good build git checkout --detach 5f9669d9e23a1116e040c80e0f3d4f43639bda52 ../artifacts/test.sh

cd .. </cut>

Full commit (up to 1000 lines): <cut> commit 6f00ccbad3d72a39d9e2bc0d500dbd62d1abc60f Author: François Dumont fdumont@gcc.gnu.org Date: Tue Jan 21 07:18:08 2020 +0100

libstdc++: Fix and improve std::vector<bool> implementation.

Do not consider allocator noexcept qualification for vector<bool> move constructor. Improve swap performance using TBAA like in main vector implementation. Bypass _M_initialize_dispatch/_M_assign_dispatch in post-c++11 modes.

libstdc++-v3/ChangeLog:

* include/bits/stl_bvector.h [_GLIBCXX_INLINE_VERSION](_Bvector_impl_data::_M_start): Define as _Bit_type*. (_Bvector_impl_data(const _Bvector_impl_data&)): Default. (_Bvector_impl_data(_Bvector_impl_data&&)): Delegate to latter. (_Bvector_impl_data::operator=(const _Bvector_impl_data&)): Default. (_Bvector_impl_data::_M_move_data(_Bvector_impl_data&&)): Use latter. (_Bvector_impl_data::_M_reset()): Likewise. (_Bvector_impl_data::_M_swap_data): New. (_Bvector_impl::_Bvector_impl(_Bvector_impl&&)): Implement explicitely. (_Bvector_impl::_Bvector_impl(_Bit_alloc_type&&, _Bvector_impl&&)): New. (_Bvector_base::_Bvector_base(_Bvector_base&&, const allocator_type&)): New, use latter. (vector::vector(vector&&, const allocator_type&, true_type)): New, use latter. (vector::vector(vector&&, const allocator_type&, false_type)): New. (vector::vector(vector&&, const allocator_type&)): Use latters. (vector::vector(const vector&, const allocator_type&)): Adapt. [__cplusplus >= 201103](vector::vector(_InputIt, _InputIt, const allocator_type&)): Use _M_initialize_range. (vector::operator[](size_type)): Use iterator operator[]. (vector::operator[](size_type) const): Use const_iterator operator[]. (vector::swap(vector&)): Add assertions on allocators. Use _M_swap_data. [__cplusplus >= 201103](vector::insert(const_iterator, _InputIt, _InputIt)): Use _M_insert_range. (vector::_M_initialize(size_type)): Adapt. [__cplusplus >= 201103](vector::_M_initialize_dispatch): Remove. [__cplusplus >= 201103](vector::_M_insert_dispatch): Remove. * python/libstdcxx/v6/printers.py (StdVectorPrinter._iterator): Stop using start _M_offset. (StdVectorPrinter.to_string): Likewise. * testsuite/23_containers/vector/bool/allocator/swap.cc: Adapt. * testsuite/23_containers/vector/bool/cons/noexcept_move_construct.cc: Add check. --- libstdc++-v3/include/bits/stl_bvector.h | 140 +++++++++++++-------- libstdc++-v3/python/libstdcxx/v6/printers.py | 5 +- .../23_containers/vector/bool/allocator/swap.cc | 22 ++-- .../vector/bool/cons/noexcept_move_construct.cc | 32 ++++- 4 files changed, 130 insertions(+), 69 deletions(-)

diff --git a/libstdc++-v3/include/bits/stl_bvector.h b/libstdc++-v3/include/bits/stl_bvector.h index a365e7182eb..d6f5435bdfb 100644 --- a/libstdc++-v3/include/bits/stl_bvector.h +++ b/libstdc++-v3/include/bits/stl_bvector.h @@ -427,53 +427,75 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER

struct _Bvector_impl_data { - _Bit_iterator _M_start; - _Bit_iterator _M_finish; - _Bit_pointer _M_end_of_storage; +#if !_GLIBCXX_INLINE_VERSION + _Bit_iterator _M_start; +#else + // We don't need the offset field for the start, it's always zero. + struct { + _Bit_type* _M_p; + // Allow assignment from iterators (assume offset is zero): + void operator=(_Bit_iterator __it) { _M_p = __it._M_p; } + } _M_start; +#endif + _Bit_iterator _M_finish; + _Bit_pointer _M_end_of_storage;

_Bvector_impl_data() _GLIBCXX_NOEXCEPT : _M_start(), _M_finish(), _M_end_of_storage() { }

#if __cplusplus >= 201103L + _Bvector_impl_data(const _Bvector_impl_data&) = default; + _Bvector_impl_data& + operator=(const _Bvector_impl_data&) = default; + _Bvector_impl_data(_Bvector_impl_data&& __x) noexcept - : _M_start(__x._M_start), _M_finish(__x._M_finish) - , _M_end_of_storage(__x._M_end_of_storage) + : _Bvector_impl_data(__x) { __x._M_reset(); }

void _M_move_data(_Bvector_impl_data&& __x) noexcept { - this->_M_start = __x._M_start; - this->_M_finish = __x._M_finish; - this->_M_end_of_storage = __x._M_end_of_storage; + *this = __x; __x._M_reset(); } #endif

void _M_reset() _GLIBCXX_NOEXCEPT + { *this = _Bvector_impl_data(); } + + void + _M_swap_data(_Bvector_impl_data& __x) _GLIBCXX_NOEXCEPT { - _M_start = _M_finish = _Bit_iterator(); - _M_end_of_storage = _Bit_pointer(); + // Do not use std::swap(_M_start, __x._M_start), etc as it loses + // information used by TBAA. + std::swap(*this, __x); } };

struct _Bvector_impl : public _Bit_alloc_type, public _Bvector_impl_data - { - public: - _Bvector_impl() _GLIBCXX_NOEXCEPT_IF( - is_nothrow_default_constructible<_Bit_alloc_type>::value) - : _Bit_alloc_type() - { } + { + _Bvector_impl() _GLIBCXX_NOEXCEPT_IF( + is_nothrow_default_constructible<_Bit_alloc_type>::value) + : _Bit_alloc_type() + { }

- _Bvector_impl(const _Bit_alloc_type& __a) _GLIBCXX_NOEXCEPT - : _Bit_alloc_type(__a) - { } + _Bvector_impl(const _Bit_alloc_type& __a) _GLIBCXX_NOEXCEPT + : _Bit_alloc_type(__a) + { }

#if __cplusplus >= 201103L - _Bvector_impl(_Bvector_impl&&) = default; + // Not defaulted, to enforce noexcept(true) even when + // !is_nothrow_move_constructible<_Bit_alloc_type>. + _Bvector_impl(_Bvector_impl&& __x) noexcept + : _Bit_alloc_type(std::move(__x)), _Bvector_impl_data(std::move(__x)) + { } + + _Bvector_impl(_Bit_alloc_type&& __a, _Bvector_impl&& __x) noexcept + : _Bit_alloc_type(std::move(__a)), _Bvector_impl_data(std::move(__x)) + { } #endif

_Bit_type* @@ -511,6 +533,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER

#if __cplusplus >= 201103L _Bvector_base(_Bvector_base&&) = default; + + _Bvector_base(_Bvector_base&& __x, const allocator_type& __a) noexcept + : _M_impl(_Bit_alloc_type(__a), std::move(__x._M_impl)) + { } #endif

~_Bvector_base() @@ -647,14 +673,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator())) { _M_initialize(__x.size()); - _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start); + _M_copy_aligned(__x.begin(), __x.end(), begin()); }

#if __cplusplus >= 201103L vector(vector&&) = default;

- vector(vector&& __x, const allocator_type& __a) - noexcept(_Bit_alloc_traits::_S_always_equal()) + private: + vector(vector&& __x, const allocator_type& __a, true_type) noexcept + : _Base(std::move(__x), __a) + { } + + vector(vector&& __x, const allocator_type& __a, false_type) : _Base(__a) { if (__x.get_allocator() == __a) @@ -667,11 +697,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } }

+ public: + vector(vector&& __x, const allocator_type& __a) + noexcept(_Bit_alloc_traits::_S_always_equal()) + : vector(std::move(__x), __a, + typename _Bit_alloc_traits::is_always_equal{}) + { } + vector(const vector& __x, const allocator_type& __a) : _Base(__a) { _M_initialize(__x.size()); - _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start); + _M_copy_aligned(__x.begin(), __x.end(), begin()); }

vector(initializer_list<bool> __l, @@ -689,13 +726,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a = allocator_type()) : _Base(__a) - { _M_initialize_dispatch(__first, __last, __false_type()); } + { + _M_initialize_range(__first, __last, + std::__iterator_category(__first)); + } #else template<typename _InputIterator> vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a = allocator_type()) : _Base(__a) { + // Check whether it's an integral type. If so, it's not an iterator. typedef typename std::__is_integer<_InputIterator>::__type _Integral; _M_initialize_dispatch(__first, __last, _Integral()); } @@ -762,7 +803,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER vector& operator=(initializer_list<bool> __l) { - this->assign (__l.begin(), __l.end()); + this->assign(__l.begin(), __l.end()); return *this; } #endif @@ -786,6 +827,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER void assign(_InputIterator __first, _InputIterator __last) { + // Check whether it's an integral type. If so, it's not an iterator. typedef typename std::__is_integer<_InputIterator>::__type _Integral; _M_assign_dispatch(__first, __last, _Integral()); } @@ -874,17 +916,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER

reference operator[](size_type __n) - { - return *iterator(this->_M_impl._M_start._M_p - + __n / int(_S_word_bit), __n % int(_S_word_bit)); - } + { return begin()[__n]; }

const_reference operator[](size_type __n) const - { - return *const_iterator(this->_M_impl._M_start._M_p - + __n / int(_S_word_bit), __n % int(_S_word_bit)); - } + { return begin()[__n]; }

protected: void @@ -951,10 +987,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER void swap(vector& __x) _GLIBCXX_NOEXCEPT { - std::swap(this->_M_impl._M_start, __x._M_impl._M_start); - std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); - std::swap(this->_M_impl._M_end_of_storage, - __x._M_impl._M_end_of_storage); +#if __cplusplus >= 201103L + __glibcxx_assert(_Bit_alloc_traits::propagate_on_container_swap::value + || _M_get_Bit_allocator() == __x._M_get_Bit_allocator()); +#endif + this->_M_impl._M_swap_data(__x._M_impl); _Bit_alloc_traits::_S_on_swap(_M_get_Bit_allocator(), __x._M_get_Bit_allocator()); } @@ -992,8 +1029,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _InputIterator __first, _InputIterator __last) { difference_type __offset = __position - cbegin(); - _M_insert_dispatch(__position._M_const_cast(), - __first, __last, __false_type()); + _M_insert_range(__position._M_const_cast(), + __first, __last, + std::__iterator_category(__first)); return begin() + __offset; } #else @@ -1002,6 +1040,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER insert(iterator __position, _InputIterator __first, _InputIterator __last) { + // Check whether it's an integral type. If so, it's not an iterator. typedef typename std::__is_integer<_InputIterator>::__type _Integral; _M_insert_dispatch(__position, __first, __last, _Integral()); } @@ -1113,15 +1152,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { _Bit_pointer __q = this->_M_allocate(__n); this->_M_impl._M_end_of_storage = __q + _S_nword(__n); - this->_M_impl._M_start = iterator(std::__addressof(*__q), 0); + iterator __start = iterator(std::__addressof(*__q), 0); + this->_M_impl._M_start = __start; + this->_M_impl._M_finish = __start + difference_type(__n); } - else - { - this->_M_impl._M_end_of_storage = _Bit_pointer(); - this->_M_impl._M_start = iterator(0, 0); - } - this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n); - }

void @@ -1141,8 +1175,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER _M_shrink_to_fit(); #endif

- // Check whether it's an integral type. If so, it's not an iterator. - +#if __cplusplus < 201103L // _GLIBCXX_RESOLVE_LIB_DEFECTS // 438. Ambiguity in the "do the right thing" clause template<typename _Integer> @@ -1159,6 +1192,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER __false_type) { _M_initialize_range(__first, __last, std::__iterator_category(__first)); } +#endif

template<typename _InputIterator> void @@ -1176,7 +1210,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER { const size_type __n = std::distance(__first, __last); _M_initialize(__n); - std::copy(__first, __last, this->_M_impl._M_start); + std::copy(__first, __last, begin()); }

#if __cplusplus < 201103L @@ -1240,8 +1274,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER } }

- // Check whether it's an integral type. If so, it's not an iterator. - +#if __cplusplus < 201103L // _GLIBCXX_RESOLVE_LIB_DEFECTS // 438. Ambiguity in the "do the right thing" clause template<typename _Integer> @@ -1257,6 +1290,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER __false_type) { _M_insert_range(__pos, __first, __last, std::__iterator_category(__first)); } +#endif

void _M_fill_insert(iterator __position, size_type __n, bool __x); diff --git a/libstdc++-v3/python/libstdcxx/v6/printers.py b/libstdc++-v3/python/libstdcxx/v6/printers.py index e4da8dfe5b6..0bf307b8e5f 100644 --- a/libstdc++-v3/python/libstdcxx/v6/printers.py +++ b/libstdc++-v3/python/libstdcxx/v6/printers.py @@ -405,7 +405,7 @@ class StdVectorPrinter: self.bitvec = bitvec if bitvec: self.item = start['_M_p'] - self.so = start['_M_offset'] + self.so = 0 self.finish = finish['_M_p'] self.fo = finish['_M_offset'] itype = self.item.dereference().type @@ -453,12 +453,11 @@ class StdVectorPrinter: end = self.val['_M_impl']['_M_end_of_storage'] if self.is_bool: start = self.val['_M_impl']['_M_start']['_M_p'] - so = self.val['_M_impl']['_M_start']['_M_offset'] finish = self.val['_M_impl']['_M_finish']['_M_p'] fo = self.val['_M_impl']['_M_finish']['_M_offset'] itype = start.dereference().type bl = 8 * itype.sizeof - length = (bl - so) + bl * ((finish - start) - 1) + fo + length = bl * (finish - start) + fo capacity = bl * (end - start) return ('%s<bool> of length %d, capacity %d' % (self.typename, int (length), int (capacity))) diff --git a/libstdc++-v3/testsuite/23_containers/vector/bool/allocator/swap.cc b/libstdc++-v3/testsuite/23_containers/vector/bool/allocator/swap.cc index a8107145c58..793115b473e 100644 --- a/libstdc++-v3/testsuite/23_containers/vector/bool/allocator/swap.cc +++ b/libstdc++-v3/testsuite/23_containers/vector/bool/allocator/swap.cc @@ -28,19 +28,17 @@ namespace __gnu_test // It is undefined behaviour to swap() containers with unequal allocators // if the allocator doesn't propagate, so ensure the allocators compare // equal, while still being able to test propagation via get_personality(). - bool - operator==(const propagating_allocator<T, false>&, - const propagating_allocator<T, false>&) - { - return true; - } + template<typename Type> + bool + operator==(const propagating_allocator<Type, false>&, + const propagating_allocator<Type, false>&) + { return true; }

- bool - operator!=(const propagating_allocator<T, false>&, - const propagating_allocator<T, false>&) - { - return false; - } + template<typename Type> + bool + operator!=(const propagating_allocator<Type, false>&, + const propagating_allocator<Type, false>&) + { return false; } }

using __gnu_test::propagating_allocator; diff --git a/libstdc++-v3/testsuite/23_containers/vector/bool/cons/noexcept_move_construct.cc b/libstdc++-v3/testsuite/23_containers/vector/bool/cons/noexcept_move_construct.cc index 03794d8ebd8..296ba33bba8 100644 --- a/libstdc++-v3/testsuite/23_containers/vector/bool/cons/noexcept_move_construct.cc +++ b/libstdc++-v3/testsuite/23_containers/vector/bool/cons/noexcept_move_construct.cc @@ -23,4 +23,34 @@

typedef std::vector<bool> vbtype;

-static_assert(std::is_nothrow_move_constructible<vbtype>::value, "Error"); +static_assert( std::is_nothrow_move_constructible<vbtype>::value, + "noexcept move constructor" ); +static_assert( std::is_nothrow_constructible<vbtype, + vbtype&&, const typename vbtype::allocator_type&>::value, + "noexcept move constructor with allocator" ); + +template<typename Type> + class not_noexcept_move_constructor_alloc : public std::allocator<Type> + { + public: + not_noexcept_move_constructor_alloc() noexcept { } + + not_noexcept_move_constructor_alloc( + const not_noexcept_move_constructor_alloc& x) noexcept + : std::allocator<Type>(x) + { } + + not_noexcept_move_constructor_alloc( + not_noexcept_move_constructor_alloc&& x) noexcept(false) + : std::allocator<Type>(std::move(x)) + { } + + template<typename _Tp1> + struct rebind + { typedef not_noexcept_move_constructor_alloc<_Tp1> other; }; + }; + +typedef std::vector<bool, not_noexcept_move_constructor_alloc<bool>> vbtype2; + +static_assert( std::is_nothrow_move_constructible<vbtype2>::value, + "noexcept move constructor with not noexcept alloc" ); </cut>