[libc++] Make sure we use the libdispatch backend on Apple platforms

[ldionne]

Summary

The Apple.cmake cache wasn't set up properly, so we wouldn't enable
the libdispatch backend by default on Apple platforms. This patch
fixes the issue and adds a test.

We also need to make various drive-by fixes:

• Drop the usage of std::vector in libdispatch.h to avoid changing the transitive includes only on Apple platforms.
• Fix includes
• Use __construct at since construct_at is unavailable in C++17
• Get rid of the (unused) __get_memory_resource function since that adds a back-deployment requirement and we don't use it right now.
• Fix bugs in the chunking logic around boundary conditions.

[philnik]

LGTM % comment.

libcxx/include/__algorithm/pstl_backends/cpu_backends/libdispatch.h

31

pushing and popping the min/max macros is missing.

[ldionne]

Push/pop macros.

[ldionne]

Fix formatting.

[ldionne]

Fix modules

[ldionne]

Fix remaining issues.

[ldionne]

Fix more issues caught by backdeployment CI

[philnik]

libcxx/include/__algorithm/pstl_backends/cpu_backends/libdispatch.h

178–179

I don't understand this change. Is this just an optimization, or is something here assuming a size > 0?

[ldionne]

libcxx/include/__algorithm/pstl_backends/cpu_backends/libdispatch.h

178–179

Otherwise we crash below:

std::__construct_at(__values.get() + __chunk, __reduction(__first + __index + 2, __first + __index + __this_chunk_size, __combiner(__transform(__first + __index), __transform(__first + __index + 1))));

libcxx/cmake/caches/Apple.cmake

 set(CMAKE_BUILD_TYPE MinSizeRel CACHE STRING "")
 set(CMAKE_POSITION_INDEPENDENT_CODE OFF CACHE BOOL "")
 
 set(LIBCXX_USE_COMPILER_RT ON CACHE BOOL "")
 set(LIBCXX_ABI_VERSION "1" CACHE STRING "")
 set(LIBCXX_ENABLE_STATIC ON CACHE BOOL "")
 set(LIBCXX_ENABLE_SHARED ON CACHE BOOL "")
 set(LIBCXX_CXX_ABI libcxxabi CACHE STRING "")
 set(LIBCXX_ENABLE_VENDOR_AVAILABILITY_ANNOTATIONS ON CACHE BOOL "")
-set(LIBCXX_PSTL_CPU_BACKEND libdispatch)
+set(LIBCXX_PSTL_CPU_BACKEND libdispatch CACHE STRING "")
 
 set(LIBCXX_HERMETIC_STATIC_LIBRARY ON CACHE BOOL "")
 set(LIBCXXABI_HERMETIC_STATIC_LIBRARY ON CACHE BOOL "")
 
 set(LIBCXXABI_ENABLE_ASSERTIONS OFF CACHE BOOL "")
 set(LIBCXXABI_ENABLE_FORGIVING_DYNAMIC_CAST ON CACHE BOOL "")
 
 set(LIBCXX_TEST_CONFIG "apple-libc++-shared.cfg.in" CACHE STRING "")
 set(LIBCXXABI_TEST_CONFIG "apple-libc++abi-shared.cfg.in" CACHE STRING "")

libcxx/include/__algorithm/pstl_backends/cpu_backends/libdispatch.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_LIBDISPATCH_H
 #define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_LIBDISPATCH_H
 
 #include <__algorithm/lower_bound.h>
+#include <__algorithm/max.h>
 #include <__algorithm/upper_bound.h>
 #include <__atomic/atomic.h>
 #include <__config>
 #include <__exception/terminate.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/move_iterator.h>
 #include <__memory/construct_at.h>
 #include <__memory/unique_ptr.h>
 #include <__memory_resource/memory_resource.h>
 #include <__numeric/reduce.h>
 #include <__utility/exception_guard.h>
 #include <__utility/move.h>
 #include <__utility/terminate_on_exception.h>
 #include <cstddef>
 #include <new>
-#include <vector>
 
 #if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 namespace __par_backend {
 inline namespace __libdispatch {
 
 // ::dispatch_apply is marked as __attribute__((nothrow)) because it doesn't let exceptions propagate, and neither do
 // we.
 // TODO: Do we want to add [[_Clang::__callback__(__func, __context, __)]]?
if (__partitions.__chunk_count_ == 0)
     return;
 
   if (__partitions.__chunk_count_ == 1) {
     __leaf_merge(__first1, __last1, __first2, __last2, __result, __comp);
     return;
   }
 
   using __merge_range_t = __merge_range<_RandomAccessIterator1, _RandomAccessIterator2, _RandomAccessIterator3>;
+  auto const __n_ranges = __partitions.__chunk_count_ + 1;
 
-  vector<__merge_range_t> __ranges;
-  __ranges.reserve(__partitions.__chunk_count_ + 1);
+  // TODO: use __uninitialized_buffer
+  auto __destroy = [=](__merge_range_t* __ptr) {
+    std::destroy_n(__ptr, __n_ranges);
+    std::allocator<__merge_range_t>().deallocate(__ptr, __n_ranges);
+  };
+  unique_ptr<__merge_range_t[], decltype(__destroy)> __ranges(
+    std::allocator<__merge_range_t>().allocate(__n_ranges), __destroy);
 
   // TODO: Improve the case where the smaller range is merged into just a few (or even one) chunks of the larger case
   std::__terminate_on_exception([&] {
-    __ranges.emplace_back(__first1, __first2, __result);
+    __merge_range_t* __r = __ranges.get();
+    std::construct_at(__r++, __first1, __first2, __result);
 
     bool __iterate_first_range = __last1 - __first1 > __last2 - __first2;
 
     auto __compute_chunk = [&](size_t __chunk_size) -> __merge_range_t {
       auto [__mid1, __mid2] = [&] {
         if (__iterate_first_range) {
           auto __m1 = __first1 + __chunk_size;
           auto __m2 = std::lower_bound(__first2, __last2, __m1[-1], __comp);
           return std::make_pair(__m1, __m2);
         } else {
           auto __m2 = __first2 + __chunk_size;
           auto __m1 = std::lower_bound(__first1, __last1, __m2[-1], __comp);
           return std::make_pair(__m1, __m2);
         }
       }();
 
       __result += (__mid1 - __first1) + (__mid2 - __first2);
       __first1 = __mid1;
       __first2 = __mid2;
       return {std::move(__mid1), std::move(__mid2), __result};
     };
 
     // handle first chunk
-    __ranges.emplace_back(__compute_chunk(__partitions.__first_chunk_size_));
+    std::construct_at(__r++, __compute_chunk(__partitions.__first_chunk_size_));
 
     // handle 2 -> N - 1 chunks
     for (ptrdiff_t __i = 0; __i != __partitions.__chunk_count_ - 2; ++__i)
-      __ranges.emplace_back(__compute_chunk(__partitions.__chunk_size_));
+      std::construct_at(__r++, __compute_chunk(__partitions.__chunk_size_));
 
     // handle last chunk
-    __ranges.emplace_back(__last1, __last2, __result);
+    std::construct_at(__r, __last1, __last2, __result);
 
     __libdispatch::__dispatch_apply(__partitions.__chunk_count_, [&](size_t __index) {
       auto __first_iters = __ranges[__index];
       auto __last_iters  = __ranges[__index + 1];
       __leaf_merge(
           __first_iters.__mid1_,
           __last_iters.__mid1_,
           __first_iters.__mid2_,
           __last_iters.__mid2_,
           __first_iters.__result_,
           __comp);
     });
   });
 }
 
 template <class _RandomAccessIterator, class _Transform, class _Value, class _Combiner, class _Reduction>
 _LIBCPP_HIDE_FROM_ABI _Value __parallel_transform_reduce(
     _RandomAccessIterator __first,
     _RandomAccessIterator __last,
     _Transform __transform,
     _Value __init,
     _Combiner __combiner,
     _Reduction __reduction) {
   auto __partitions = __libdispatch::__partition_chunks(__last - __first);
 
   auto __destroy = [__count = __partitions.__chunk_count_](_Value* __ptr) {
     std::destroy_n(__ptr, __count);
     std::allocator<_Value>().deallocate(__ptr, __count);
   };
 
   // TODO: use __uninitialized_buffer
   // TODO: allocate one element per worker instead of one element per chunk
   unique_ptr<_Value[], decltype(__destroy)> __values(

libcxx/test/libcxx/vendor/apple/system-install-properties.sh.cpp

 // XRUNX: otool -L "%{lib}/libc++.1.dylib" | grep '/usr/lib/libc++.1.dylib'
 // XRUNX: ! otool -l "%{lib}/libc++.1.dylib" | grep -E "LC_RPATH|@loader_path|@rpath"
 
 // Make sure the compatibility_version of libc++ is 1.0.0.
 // Failure to respect this can result in applications not being able to find libc++
 // when they are loaded by dyld, if the compatibility version was bumped.
 //
 // RUN: otool -L "%{lib}/libc++.1.dylib" | grep "libc++.1.dylib" | grep "compatibility version 1.0.0"
+
+// Make sure we use the libdispatch backend for the PSTL.
+//
+// RUN: grep "%{include}/__config_site" -e '#define _LIBCPP_PSTL_CPU_BACKEND_LIBDISPATCH'