Simplify multidimensional methods by flattening c-arrays before constructing elements

[brenoguim]

Summary

Multidimensional methods construct arrays of objects with special
attention to c-arrays. In that case, each c-array is recursively built
to make sure each element is destroyed in the reverse order of creation.

This patch simplifies this task by treating C elements of T[N][M] as
C*N*M elements of T.
This prevents the recursion, using only a single guard.

Arguably, it makes the code easier to read and better codegen.

(Added as reviewers the same list of https://reviews.llvm.org/D62641 which introduced these methods. I hope that's fine)

[brenoguim]

libcxx/include/__memory/uninitialized_algorithms.h

441

This is not valid for bidirectional iterators, only for pointers. The code either needs to be enhanced to actually support bidirectional iterators, or take pointers as parameters.

[brenoguim]

Don't use std::is_bounded_array because it broke some CI verifications. There is probably a correct way to allow it, but I'm not sure how to yet.

[brenoguim]

Uglify names

[brenoguim]

Adjust the patch to only accept pointers as inputs. Is that something that we can live with? It's a requirement now.

[brenoguim]

Same as before but now for the destructor version

[brenoguim]

The code generation seems to be better. I pasted the new code in Godbolt with a flag to enable/disable it: https://godbolt.org/z/e4xbn4zce
With the flag enabled (the new code) it's possible to even read through the assembly for the constructors being called and the destructors in the exceptional condition.
Without the flag it's all much harder to read.
This is no proof that the code generation *is* better, but a good indication.

[philnik]

Could you split this into two patches? One where you merge fill_n and value_construct_n and another one where you do the optimization. Also, please add a benchmark in libcxx/benchmarks.

libcxx/include/__memory/uninitialized_algorithms.h

366–369

Why not is_bounded_array?

libcxx/include/__memory/shared_ptr.h

 {
     _LIBCPP_HIDE_FROM_ABI constexpr
     _Tp* __get_data() noexcept { return __data_; }
 
     _LIBCPP_HIDE_FROM_ABI
     explicit __unbounded_array_control_block(_Alloc const& __alloc, size_t __count, _Tp const& __arg)
         : __alloc_(__alloc), __count_(__count)
     {
-        std::__uninitialized_allocator_fill_n_multidimensional(__alloc_, std::begin(__data_), __count_, __arg);
+        std::__uninitialized_allocator_construct_n_multidimensional(__alloc_, __data_, __count_, __arg);
     }
 
     _LIBCPP_HIDE_FROM_ABI
     explicit __unbounded_array_control_block(_Alloc const& __alloc, size_t __count)
         : __alloc_(__alloc), __count_(__count)
     {
 #if _LIBCPP_STD_VER >= 20
         if constexpr (is_same_v<typename _Alloc::value_type, __for_overwrite_tag>) {
             // We are purposefully not using an allocator-aware default construction because the spec says so.
             // There's currently no way of expressing default initialization in an allocator-aware manner anyway.
             std::uninitialized_default_construct_n(std::begin(__data_), __count_);
         } else {
-            std::__uninitialized_allocator_value_construct_n_multidimensional(__alloc_, std::begin(__data_), __count_);
+            std::__uninitialized_allocator_construct_n_multidimensional(__alloc_, __data_, __count_);
         }
 #else
-        std::__uninitialized_allocator_value_construct_n_multidimensional(__alloc_, std::begin(__data_), __count_);
+        std::__uninitialized_allocator_construct_n_multidimensional(__alloc_, __data_, __count_);
 #endif
     }
 
     // Returns the number of bytes required to store a control block followed by the given number
     // of elements of _Tp, with the whole storage being aligned to a multiple of _Tp's alignment.
     _LIBCPP_HIDE_FROM_ABI
     static constexpr size_t __bytes_for(size_t __elements) {
         // When there's 0 elements, the control block alone is enough since it holds one element.

 
 private:
     void __on_zero_shared() _NOEXCEPT override {
 #if _LIBCPP_STD_VER >= 20
         if constexpr (is_same_v<typename _Alloc::value_type, __for_overwrite_tag>) {
             std::__reverse_destroy(__data_, __data_ + __count_);
         } else {
             __allocator_traits_rebind_t<_Alloc, _Tp> __value_alloc(__alloc_);
-            std::__allocator_destroy_multidimensional(__value_alloc, __data_, __data_ + __count_);
+            std::__allocator_destroy_n_multidimensional(__value_alloc, __data_, __count_);
         }
 #else
         __allocator_traits_rebind_t<_Alloc, _Tp> __value_alloc(__alloc_);
-        std::__allocator_destroy_multidimensional(__value_alloc, __data_, __data_ + __count_);
+        std::__allocator_destroy_n_multidimensional(__value_alloc, __data_, __count_);
 #endif
     }
 
     void __on_zero_shared_weak() _NOEXCEPT override {
         using _AlignedStorage = __sp_aligned_storage<alignof(__unbounded_array_control_block)>;
         using _StorageAlloc = __allocator_traits_rebind_t<_Alloc, _AlignedStorage>;
         using _PointerTraits = pointer_traits<typename allocator_traits<_StorageAlloc>::pointer>;
 

 struct __bounded_array_control_block<_Tp[_Count], _Alloc>
     : __shared_weak_count
 {
     _LIBCPP_HIDE_FROM_ABI constexpr
     _Tp* __get_data() noexcept { return __data_; }
 
     _LIBCPP_HIDE_FROM_ABI
     explicit __bounded_array_control_block(_Alloc const& __alloc, _Tp const& __arg) : __alloc_(__alloc) {
-        std::__uninitialized_allocator_fill_n_multidimensional(__alloc_, std::addressof(__data_[0]), _Count, __arg);
+        std::__uninitialized_allocator_construct_n_multidimensional(__alloc_, __data_, _Count, __arg);
     }
 
     _LIBCPP_HIDE_FROM_ABI
     explicit __bounded_array_control_block(_Alloc const& __alloc) : __alloc_(__alloc) {
 #if _LIBCPP_STD_VER >= 20
         if constexpr (is_same_v<typename _Alloc::value_type, __for_overwrite_tag>) {
             // We are purposefully not using an allocator-aware default construction because the spec says so.
             // There's currently no way of expressing default initialization in an allocator-aware manner anyway.
             std::uninitialized_default_construct_n(std::addressof(__data_[0]), _Count);
         } else {
-            std::__uninitialized_allocator_value_construct_n_multidimensional(__alloc_, std::addressof(__data_[0]), _Count);
+            std::__uninitialized_allocator_construct_n_multidimensional(__alloc_, __data_, _Count);
         }
 #else
-        std::__uninitialized_allocator_value_construct_n_multidimensional(__alloc_, std::addressof(__data_[0]), _Count);
+        std::__uninitialized_allocator_construct_n_multidimensional(__alloc_, __data_, _Count);
 #endif
     }
 
     _LIBCPP_HIDE_FROM_ABI_VIRTUAL
     ~__bounded_array_control_block() override { } // can't be `= default` because of the sometimes-non-trivial union member __data_
 
 private:
     void __on_zero_shared() _NOEXCEPT override {
 #if _LIBCPP_STD_VER >= 20
         if constexpr (is_same_v<typename _Alloc::value_type, __for_overwrite_tag>) {
             std::__reverse_destroy(__data_, __data_ + _Count);
         } else {
             __allocator_traits_rebind_t<_Alloc, _Tp> __value_alloc(__alloc_);
-            std::__allocator_destroy_multidimensional(__value_alloc, __data_, __data_ + _Count);
+            std::__allocator_destroy_n_multidimensional(__value_alloc, __data_, _Count);
         }
 #else
         __allocator_traits_rebind_t<_Alloc, _Tp> __value_alloc(__alloc_);
-        std::__allocator_destroy_multidimensional(__value_alloc, __data_, __data_ + _Count);
+        std::__allocator_destroy_n_multidimensional(__value_alloc, __data_, _Count);
 #endif
     }
 
     void __on_zero_shared_weak() _NOEXCEPT override {
         using _ControlBlockAlloc = __allocator_traits_rebind_t<_Alloc, __bounded_array_control_block>;
         using _PointerTraits = pointer_traits<typename allocator_traits<_ControlBlockAlloc>::pointer>;
 
         _ControlBlockAlloc __tmp(__alloc_);

libcxx/include/__memory/uninitialized_algorithms.h

 uninitialized_move_n(_InputIterator __ifirst, _Size __n, _ForwardIterator __ofirst) {
   using _ValueType = typename iterator_traits<_ForwardIterator>::value_type;
   auto __iter_move = [](auto&& __iter) -> decltype(auto) { return _VSTD::move(*__iter); };
 
   return _VSTD::__uninitialized_move_n<_ValueType>(_VSTD::move(__ifirst), __n, _VSTD::move(__ofirst),
                                                    __unreachable_sentinel(), __iter_move);
 }
 
+template<class _Tp>
+struct _IsBoundedArray { static constexpr bool value = false; };
+template<class _Tp, int _Num>
+struct _IsBoundedArray<_Tp[_Num]> { static constexpr bool value = true; };
+
+// For a type T[N][M] calculate T and N*M
+template<class _Tp>
+struct __flatten
+{
+    using element_type = _Tp;
+    static constexpr int element_count = 1;
+};
+
+template<class _Tp, int _Num>
+struct __flatten<_Tp[_Num]>
+{
+    using element_type = typename __flatten<_Tp>::element_type;
+    static constexpr int element_count = __flatten<_Tp>::element_count * _Num;
+};
+
+// Get the address of the first element of a possibly nested c-style array
+template<class _Tp>
+_LIBCPP_HIDE_FROM_ABI constexpr
+auto* __flat_addressof(_Tp& __t)
+{
+    if constexpr (_IsBoundedArray<_Tp>::value)
+        return std::__flat_addressof(__t[0]);
+    else
+        return std::addressof(__t);
+}
+
 // TODO: Rewrite this to iterate left to right and use reverse_iterators when calling
 // Destroys every element in the range [first, last) FROM RIGHT TO LEFT using allocator
 // destruction. If elements are themselves C-style arrays, they are recursively destroyed
 // in the same manner.
 //
 // This function assumes that destructors do not throw, and that the allocator is bound to
 // the correct type.
-template<class _Alloc, class _BidirIter, class = __enable_if_t<
-    __is_cpp17_bidirectional_iterator<_BidirIter>::value
->>
-_LIBCPP_HIDE_FROM_ABI
-constexpr void __allocator_destroy_multidimensional(_Alloc& __alloc, _BidirIter __first, _BidirIter __last) noexcept {
-    using _ValueType = typename iterator_traits<_BidirIter>::value_type;
-    static_assert(is_same_v<typename allocator_traits<_Alloc>::value_type, _ValueType>,
-        "The allocator should already be rebound to the correct type");
-
-    if (__first == __last)
+template<class _Alloc, class _Tp, class _Size = typename iterator_traits<_Tp*>::difference_type>
+_LIBCPP_HIDE_FROM_ABI constexpr void
+__allocator_destroy_n_multidimensional(const _Alloc& __alloc, _Tp* __first, _Size __n) noexcept {
+    if (__n == 0)
         return;
 
-    if constexpr (is_array_v<_ValueType>) {
-        static_assert(!__libcpp_is_unbounded_array<_ValueType>::value,
-            "arrays of unbounded arrays don't exist, but if they did we would mess up here");
-
-        using _Element = remove_extent_t<_ValueType>;
-        __allocator_traits_rebind_t<_Alloc, _Element> __elem_alloc(__alloc);
-        do {
-            --__last;
-            decltype(auto) __array = *__last;
-            std::__allocator_destroy_multidimensional(__elem_alloc, __array, __array + extent_v<_ValueType>);
-        } while (__last != __first);
-    } else {
-        do {
-            --__last;
-            allocator_traits<_Alloc>::destroy(__alloc, std::addressof(*__last));
-        } while (__last != __first);
-    }
-}
-
-// Constructs the object at the given location using the allocator's construct method.
-//
-// If the object being constructed is an array, each element of the array is allocator-constructed,
-// recursively. If an exception is thrown during the construction of an array, the initialized
-// elements are destroyed in reverse order of initialization using allocator destruction.
-//
-// This function assumes that the allocator is bound to the correct type.
-template<class _Alloc, class _Tp>
-_LIBCPP_HIDE_FROM_ABI
-constexpr void __allocator_construct_at_multidimensional(_Alloc& __alloc, _Tp* __loc) {
-    static_assert(is_same_v<typename allocator_traits<_Alloc>::value_type, _Tp>,
-        "The allocator should already be rebound to the correct type");
-
-    if constexpr (is_array_v<_Tp>) {
-        using _Element = remove_extent_t<_Tp>;
-        __allocator_traits_rebind_t<_Alloc, _Element> __elem_alloc(__alloc);
-        size_t __i = 0;
-        _Tp& __array = *__loc;
+    using _FlatTp = typename __flatten<_Tp>::element_type;
+    __n *= __flatten<_Tp>::element_count;
 
-        // If an exception is thrown, destroy what we have constructed so far in reverse order.
-        auto __guard = std::__make_exception_guard([&]() {
-          std::__allocator_destroy_multidimensional(__elem_alloc, __array, __array + __i);
-        });
-
-        for (; __i != extent_v<_Tp>; ++__i) {
-            std::__allocator_construct_at_multidimensional(__elem_alloc, std::addressof(__array[__i]));
-        }
-        __guard.__complete();
-    } else {
-        allocator_traits<_Alloc>::construct(__alloc, __loc);
-    }
-}
+    using _FlatTpAlloc = __allocator_traits_rebind_t<_Alloc, _FlatTp>;
+    _FlatTpAlloc __ftp_alloc(__alloc);
 
-// Constructs the object at the given location using the allocator's construct method, passing along
-// the provided argument.
-//
-// If the object being constructed is an array, the argument is also assumed to be an array. Each
-// each element of the array being constructed is allocator-constructed from the corresponding
-// element of the argument array. If an exception is thrown during the construction of an array,
-// the initialized elements are destroyed in reverse order of initialization using allocator
-// destruction.
-//
-// This function assumes that the allocator is bound to the correct type.
-template<class _Alloc, class _Tp, class _Arg>
-_LIBCPP_HIDE_FROM_ABI
-constexpr void __allocator_construct_at_multidimensional(_Alloc& __alloc, _Tp* __loc, _Arg const& __arg) {
-    static_assert(is_same_v<typename allocator_traits<_Alloc>::value_type, _Tp>,
-        "The allocator should already be rebound to the correct type");
-
-    if constexpr (is_array_v<_Tp>) {
-        static_assert(is_array_v<_Arg>,
-            "Provided non-array initialization argument to __allocator_construct_at_multidimensional when "
-            "trying to construct an array.");
-
-        using _Element = remove_extent_t<_Tp>;
-        __allocator_traits_rebind_t<_Alloc, _Element> __elem_alloc(__alloc);
-        size_t __i = 0;
-        _Tp& __array = *__loc;
+    auto* __flat_first = std::__flat_addressof(*__first);
+    auto* __flat_last = __flat_first + __n;
 
-        // If an exception is thrown, destroy what we have constructed so far in reverse order.
-        auto __guard = std::__make_exception_guard([&]() {
-          std::__allocator_destroy_multidimensional(__elem_alloc, __array, __array + __i);
-        });
-        for (; __i != extent_v<_Tp>; ++__i) {
-            std::__allocator_construct_at_multidimensional(__elem_alloc, std::addressof(__array[__i]), __arg[__i]);
-        }
-        __guard.__complete();
-    } else {
-        allocator_traits<_Alloc>::construct(__alloc, __loc, __arg);
-    }
+    while (__flat_first != __flat_last)
+        allocator_traits<_FlatTpAlloc>::destroy(__ftp_alloc, --__flat_last);
 }
 
 // Given a range starting at it and containing n elements, initializes each element in the
 // range from left to right using the construct method of the allocator (rebound to the
 // correct type).
 //
 // If an exception is thrown, the initialized elements are destroyed in reverse order of
-// initialization using allocator_traits destruction. If the elements in the range are C-style
-// arrays, they are initialized element-wise using allocator construction, and recursively so.
-template<class _Alloc, class _BidirIter, class _Tp, class _Size = typename iterator_traits<_BidirIter>::difference_type>
+// initialization using allocator_traits destruction.
+//
+// If the elements in the range are C-style arrays, they are initialized element-wise
+// using allocator construction and treating them as single larger flat array
+template<class _Alloc, class _Tp, class... _OptArg, class _Size = typename iterator_traits<_Tp*>::difference_type>
 _LIBCPP_HIDE_FROM_ABI constexpr void
-__uninitialized_allocator_fill_n_multidimensional(_Alloc& __alloc, _BidirIter __it, _Size __n, _Tp const& __value) {
-    using _ValueType = typename iterator_traits<_BidirIter>::value_type;
-    __allocator_traits_rebind_t<_Alloc, _ValueType> __value_alloc(__alloc);
-    _BidirIter __begin = __it;
-
-    // If an exception is thrown, destroy what we have constructed so far in reverse order.
-    auto __guard = std::__make_exception_guard([&]() { std::__allocator_destroy_multidimensional(__value_alloc, __begin, __it); });
-    for (; __n != 0; --__n, ++__it) {
-        std::__allocator_construct_at_multidimensional(__value_alloc, std::addressof(*__it), __value);
-    }
-    __guard.__complete();
-}
+__uninitialized_allocator_construct_n_multidimensional(const _Alloc& __alloc, _Tp* __it, _Size __n, _OptArg const&... __opt_arg) {
 
-// Same as __uninitialized_allocator_fill_n_multidimensional, but doesn't pass any initialization argument
-// to the allocator's construct method, which results in value initialization.
-template <class _Alloc, class _BidirIter, class _Size = typename iterator_traits<_BidirIter>::difference_type>
-_LIBCPP_HIDE_FROM_ABI constexpr void
-__uninitialized_allocator_value_construct_n_multidimensional(_Alloc& __alloc, _BidirIter __it, _Size __n) {
-    using _ValueType = typename iterator_traits<_BidirIter>::value_type;
-    __allocator_traits_rebind_t<_Alloc, _ValueType> __value_alloc(__alloc);
-    _BidirIter __begin = __it;
-
-    // If an exception is thrown, destroy what we have constructed so far in reverse order.
-    auto __guard = std::__make_exception_guard([&]() { std::__allocator_destroy_multidimensional(__value_alloc, __begin, __it); });
-    for (; __n != 0; --__n, ++__it) {
-        std::__allocator_construct_at_multidimensional(__value_alloc, std::addressof(*__it));
+    // Either default initialization or value initialization
+    static_assert(sizeof...(_OptArg) <= 1);
+
+    using _FlatTp = typename __flatten<_Tp>::element_type;
+    __n *= __flatten<_Tp>::element_count;
+
+    using _FlatTpAlloc = __allocator_traits_rebind_t<_Alloc, _FlatTp>;
+    _FlatTpAlloc __ftp_alloc(__alloc);
+
+    auto* __flat_it = std::__flat_addressof(*__it);
+    _Size __idx = 0;
+
+    auto __guard = std::__make_exception_guard([&]() {
+        for (; __idx != 0; --__idx)
+            allocator_traits<_FlatTpAlloc>::destroy(__ftp_alloc, --__flat_it);
+    });
+
+    if constexpr (sizeof...(_OptArg) == 1) {
+        auto* __fill_ptr = std::__flat_addressof(__opt_arg...);
+        constexpr int __fill_element_count = __flatten<_OptArg...>::element_count;
+
+        for (; __idx < __n; ++__flat_it, ++__idx)
+            allocator_traits<_FlatTpAlloc>::construct(__ftp_alloc, __flat_it, __fill_ptr[__idx % __fill_element_count]);
+
+    } else {
+        for (; __idx < __n; ++__flat_it, ++__idx)
+            allocator_traits<_FlatTpAlloc>::construct(__ftp_alloc, __flat_it);
     }
+
     __guard.__complete();
 }
 
 #endif // _LIBCPP_STD_VER >= 17
 
 // Destroy all elements in [__first, __last) from left to right using allocator destruction.
 template <class _Alloc, class _Iter, class _Sent>
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void