diff --git a/libcxx/CMakeLists.txt b/libcxx/CMakeLists.txt
--- a/libcxx/CMakeLists.txt
+++ b/libcxx/CMakeLists.txt
@@ -68,7 +68,6 @@
 option(LIBCXX_ENABLE_FILESYSTEM "Build filesystem as part of the main libc++ library"
     ${ENABLE_FILESYSTEM_DEFAULT})
 option(LIBCXX_INCLUDE_TESTS "Build the libc++ tests." ${LLVM_INCLUDE_TESTS})
-option(LIBCXX_ENABLE_PARALLEL_ALGORITHMS "Enable the parallel algorithms library. This requires the PSTL to be available." OFF)
 option(LIBCXX_ENABLE_DEBUG_MODE
   "Whether to build libc++ with the debug mode enabled.
    By default, this is turned off. Turning it on results in a different ABI (additional
@@ -791,7 +790,6 @@
 config_define_if(LIBCXX_BUILD_EXTERNAL_THREAD_LIBRARY _LIBCPP_HAS_THREAD_LIBRARY_EXTERNAL)
 config_define_if(LIBCXX_HAS_MUSL_LIBC _LIBCPP_HAS_MUSL_LIBC)
 config_define_if(LIBCXX_NO_VCRUNTIME _LIBCPP_NO_VCRUNTIME)
-config_define_if(LIBCXX_ENABLE_PARALLEL_ALGORITHMS _LIBCPP_HAS_PARALLEL_ALGORITHMS)
 config_define_if_not(LIBCXX_ENABLE_FILESYSTEM _LIBCPP_HAS_NO_FILESYSTEM_LIBRARY)
 config_define_if_not(LIBCXX_ENABLE_RANDOM_DEVICE _LIBCPP_HAS_NO_RANDOM_DEVICE)
 config_define_if_not(LIBCXX_ENABLE_LOCALIZATION _LIBCPP_HAS_NO_LOCALIZATION)
diff --git a/libcxx/cmake/caches/With-pstl.cmake b/libcxx/cmake/caches/With-pstl.cmake
deleted file mode 100644
--- a/libcxx/cmake/caches/With-pstl.cmake
+++ /dev/null
@@ -1,4 +0,0 @@
-# TODO: Remove this cache file once the PSTL is under `-fexperimental-library`
-set(LIBCXX_TEST_PARAMS "std=c++17" CACHE STRING "")
-set(LIBCXXABI_TEST_PARAMS "${LIBCXX_TEST_PARAMS}" CACHE STRING "")
-set(LIBCXX_ENABLE_PARALLEL_ALGORITHMS ON CACHE BOOL "")
diff --git a/libcxx/include/__algorithm/pstl_any_all_none_of.h b/libcxx/include/__algorithm/pstl_any_all_none_of.h
--- a/libcxx/include/__algorithm/pstl_any_all_none_of.h
+++ b/libcxx/include/__algorithm/pstl_any_all_none_of.h
@@ -16,13 +16,14 @@
 #include <__pstl/internal/unseq_backend_simd.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/is_execution_policy.h>
+#include <__type_traits/remove_cvref.h>
 #include <__utility/terminate_on_exception.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
-#if _LIBCPP_STD_VER >= 17
+#if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
@@ -74,6 +75,6 @@
 
 _LIBCPP_END_NAMESPACE_STD
 
-#endif // _LIBCPP_STD_VER >= 17
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_ANY_ALL_NONE_OF_H
diff --git a/libcxx/include/__algorithm/pstl_fill.h b/libcxx/include/__algorithm/pstl_fill.h
--- a/libcxx/include/__algorithm/pstl_fill.h
+++ b/libcxx/include/__algorithm/pstl_fill.h
@@ -15,13 +15,14 @@
 #include <__pstl/internal/parallel_impl.h>
 #include <__pstl/internal/unseq_backend_simd.h>
 #include <__type_traits/is_execution_policy.h>
+#include <__type_traits/remove_cvref.h>
 #include <__utility/terminate_on_exception.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
-#if _LIBCPP_STD_VER >= 17
+#if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
@@ -66,6 +67,6 @@
 
 _LIBCPP_END_NAMESPACE_STD
 
-#endif // _LIBCPP_STD_VER >= 17
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_FILL_H
diff --git a/libcxx/include/__algorithm/pstl_find.h b/libcxx/include/__algorithm/pstl_find.h
--- a/libcxx/include/__algorithm/pstl_find.h
+++ b/libcxx/include/__algorithm/pstl_find.h
@@ -15,12 +15,15 @@
 #include <__pstl/internal/parallel_impl.h>
 #include <__pstl/internal/unseq_backend_simd.h>
 #include <__type_traits/is_execution_policy.h>
+#include <__type_traits/remove_cvref.h>
 #include <__utility/terminate_on_exception.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
+#if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _ExecutionPolicy,
@@ -100,4 +103,6 @@
 
 _LIBCPP_END_NAMESPACE_STD
 
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
 #endif // _LIBCPP___ALGORITHM_PSTL_FIND_H
diff --git a/libcxx/include/__algorithm/pstl_for_each.h b/libcxx/include/__algorithm/pstl_for_each.h
--- a/libcxx/include/__algorithm/pstl_for_each.h
+++ b/libcxx/include/__algorithm/pstl_for_each.h
@@ -16,13 +16,14 @@
 #include <__pstl/internal/parallel_backend.h>
 #include <__pstl/internal/unseq_backend_simd.h>
 #include <__type_traits/is_execution_policy.h>
+#include <__type_traits/remove_cvref.h>
 #include <__utility/terminate_on_exception.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
-#if defined(_LIBCPP_HAS_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17
+#if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
@@ -68,6 +69,6 @@
 
 _LIBCPP_END_NAMESPACE_STD
 
-#endif // defined(_LIBCPP_HAS_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_FOR_EACH_H
diff --git a/libcxx/include/__config b/libcxx/include/__config
--- a/libcxx/include/__config
+++ b/libcxx/include/__config
@@ -272,6 +272,7 @@
 // easier to grep for target specific flags once the feature is complete.
 #  if !defined(_LIBCPP_ENABLE_EXPERIMENTAL) && !defined(_LIBCPP_BUILDING_LIBRARY)
 #    define _LIBCPP_HAS_NO_INCOMPLETE_FORMAT
+#    define _LIBCPP_HAS_NO_INCOMPLETE_PSTL
 #  endif
 
 // Need to detect which libc we're using if we're on Linux.
diff --git a/libcxx/include/__config_site.in b/libcxx/include/__config_site.in
--- a/libcxx/include/__config_site.in
+++ b/libcxx/include/__config_site.in
@@ -25,7 +25,6 @@
 #cmakedefine _LIBCPP_NO_VCRUNTIME
 #cmakedefine _LIBCPP_TYPEINFO_COMPARISON_IMPLEMENTATION @_LIBCPP_TYPEINFO_COMPARISON_IMPLEMENTATION@
 #cmakedefine _LIBCPP_HAS_NO_FILESYSTEM_LIBRARY
-#cmakedefine _LIBCPP_HAS_PARALLEL_ALGORITHMS
 #cmakedefine _LIBCPP_HAS_NO_RANDOM_DEVICE
 #cmakedefine _LIBCPP_HAS_NO_LOCALIZATION
 #cmakedefine _LIBCPP_HAS_NO_FSTREAM
diff --git a/libcxx/include/__pstl/internal/execution_defs.h b/libcxx/include/__pstl/internal/execution_defs.h
--- a/libcxx/include/__pstl/internal/execution_defs.h
+++ b/libcxx/include/__pstl/internal/execution_defs.h
@@ -16,6 +16,8 @@
 
 #include "pstl_config.h"
 
+#if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
 namespace __pstl {
 namespace execution {
 inline namespace v1 {
@@ -70,4 +72,6 @@
 
 } // namespace __pstl
 
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
 #endif /* _PSTL_EXECUTION_POLICY_DEFS_H */
diff --git a/libcxx/include/__pstl/internal/execution_impl.h b/libcxx/include/__pstl/internal/execution_impl.h
--- a/libcxx/include/__pstl/internal/execution_impl.h
+++ b/libcxx/include/__pstl/internal/execution_impl.h
@@ -11,10 +11,15 @@
 #define _PSTL_EXECUTION_IMPL_H
 
 #include <__iterator/iterator_traits.h>
+#include <__type_traits/conditional.h>
+#include <__type_traits/conjunction.h>
+#include <__type_traits/is_base_of.h>
 
 #include "execution_defs.h"
 #include "pstl_config.h"
 
+#if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
 namespace __pstl {
 namespace __internal {
 
@@ -29,15 +34,15 @@
 struct __tbb_backend_tag {};
 struct __openmp_backend_tag {};
 
-#if defined(_PSTL_PAR_BACKEND_TBB)
+#  if defined(_PSTL_PAR_BACKEND_TBB)
 using __par_backend_tag = __tbb_backend_tag;
-#elif defined(_PSTL_PAR_BACKEND_OPENMP)
+#  elif defined(_PSTL_PAR_BACKEND_OPENMP)
 using __par_backend_tag = __openmp_backend_tag;
-#elif defined(_PSTL_PAR_BACKEND_SERIAL)
+#  elif defined(_PSTL_PAR_BACKEND_SERIAL)
 using __par_backend_tag = __serial_backend_tag;
-#else
-#  error "A parallel backend must be specified";
-#endif
+#  else
+#    error "A parallel backend must be specified";
+#  endif
 
 template <class _IsVector>
 struct __serial_tag {
@@ -85,4 +90,6 @@
 } // namespace __internal
 } // namespace __pstl
 
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
 #endif /* _PSTL_EXECUTION_IMPL_H */
diff --git a/libcxx/include/__pstl/internal/parallel_backend.h b/libcxx/include/__pstl/internal/parallel_backend.h
--- a/libcxx/include/__pstl/internal/parallel_backend.h
+++ b/libcxx/include/__pstl/internal/parallel_backend.h
@@ -14,10 +14,12 @@
 
 #if defined(_PSTL_PAR_BACKEND_SERIAL)
 #    include "parallel_backend_serial.h"
+#    if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 namespace __pstl
 {
 namespace __par_backend = __serial_backend;
 } // namespace __pstl
+#    endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 #elif defined(_PSTL_PAR_BACKEND_TBB)
 #    include "parallel_backend_tbb.h"
 namespace __pstl
diff --git a/libcxx/include/__pstl/internal/parallel_backend_serial.h b/libcxx/include/__pstl/internal/parallel_backend_serial.h
--- a/libcxx/include/__pstl/internal/parallel_backend_serial.h
+++ b/libcxx/include/__pstl/internal/parallel_backend_serial.h
@@ -16,6 +16,8 @@
 
 #include "pstl_config.h"
 
+#if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
 namespace __pstl
 {
 namespace __serial_backend
@@ -129,4 +131,6 @@
 } // namespace __serial_backend
 } // namespace __pstl
 
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
 #endif /* _PSTL_PARALLEL_BACKEND_SERIAL_H */
diff --git a/libcxx/include/__pstl/internal/parallel_impl.h b/libcxx/include/__pstl/internal/parallel_impl.h
--- a/libcxx/include/__pstl/internal/parallel_impl.h
+++ b/libcxx/include/__pstl/internal/parallel_impl.h
@@ -13,8 +13,11 @@
 #include "pstl_config.h"
 
 #include <__atomic/atomic.h>
+#include <__atomic/memory_order.h>
 #include <__pstl/internal/parallel_backend.h>
 
+#if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
 namespace __pstl
 {
 namespace __internal
@@ -81,4 +84,6 @@
 } // namespace __internal
 } // namespace __pstl
 
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
 #endif /* _PSTL_PARALLEL_IMPL_H */
diff --git a/libcxx/include/__pstl/internal/unseq_backend_simd.h b/libcxx/include/__pstl/internal/unseq_backend_simd.h
--- a/libcxx/include/__pstl/internal/unseq_backend_simd.h
+++ b/libcxx/include/__pstl/internal/unseq_backend_simd.h
@@ -11,7 +11,10 @@
 #define _PSTL_UNSEQ_BACKEND_SIMD_H
 
 #include <__functional/operations.h>
+#include <__type_traits/is_arithmetic.h>
 #include <__utility/pair.h>
+#include <cstddef>
+#include <cstdint>
 
 #include "pstl_config.h"
 #include "utils.h"
@@ -19,6 +22,8 @@
 // This header defines the minimum set of vector routines required
 // to support parallel STL.
 
+#if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
 namespace __pstl
 {
 namespace __unseq_backend
@@ -806,4 +811,6 @@
 } // namespace __unseq_backend
 } // namespace __pstl
 
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
 #endif /* _PSTL_UNSEQ_BACKEND_SIMD_H */
diff --git a/libcxx/include/__pstl/internal/utils.h b/libcxx/include/__pstl/internal/utils.h
--- a/libcxx/include/__pstl/internal/utils.h
+++ b/libcxx/include/__pstl/internal/utils.h
@@ -15,6 +15,8 @@
 #include <__utility/forward.h>
 #include <new>
 
+#if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
 namespace __pstl {
 namespace __internal {
 
@@ -137,4 +139,6 @@
 } // namespace __internal
 } // namespace __pstl
 
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
 #endif /* _PSTL_UTILS_H */
diff --git a/libcxx/include/__type_traits/is_execution_policy.h b/libcxx/include/__type_traits/is_execution_policy.h
--- a/libcxx/include/__type_traits/is_execution_policy.h
+++ b/libcxx/include/__type_traits/is_execution_policy.h
@@ -39,7 +39,7 @@
 // Removes the "parallel" part of an execution policy.
 // For example, turns par_unseq into unseq, and par into seq.
 template <class _ExecutionPolicy>
-const auto& __remove_parallel_policy(_ExecutionPolicy&&);
+_LIBCPP_HIDE_FROM_ABI const auto& __remove_parallel_policy(_ExecutionPolicy&&);
 
 _LIBCPP_END_NAMESPACE_STD
 
diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm
--- a/libcxx/include/algorithm
+++ b/libcxx/include/algorithm
@@ -1788,6 +1788,10 @@
 #include <__algorithm/partition_point.h>
 #include <__algorithm/pop_heap.h>
 #include <__algorithm/prev_permutation.h>
+#include <__algorithm/pstl_any_all_none_of.h>
+#include <__algorithm/pstl_fill.h>
+#include <__algorithm/pstl_find.h>
+#include <__algorithm/pstl_for_each.h>
 #include <__algorithm/push_heap.h>
 #include <__algorithm/ranges_adjacent_find.h>
 #include <__algorithm/ranges_all_of.h>
@@ -1908,13 +1912,6 @@
 #include <__algorithm/unwrap_iter.h>
 #include <__algorithm/upper_bound.h>
 
-#ifdef _LIBCPP_HAS_PARALLEL_ALGORITHMS
-#  include <__algorithm/pstl_any_all_none_of.h>
-#  include <__algorithm/pstl_fill.h>
-#  include <__algorithm/pstl_find.h>
-#  include <__algorithm/pstl_for_each.h>
-#endif
-
 // standard-mandated includes
 
 // [algorithm.syn]
diff --git a/libcxx/include/execution b/libcxx/include/execution
--- a/libcxx/include/execution
+++ b/libcxx/include/execution
@@ -43,7 +43,7 @@
 #  pragma GCC system_header
 #endif
 
-#if defined(_LIBCPP_HAS_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17
+#if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
@@ -135,7 +135,7 @@
 struct is_execution_policy : bool_constant<is_execution_policy_v<_Tp>> {};
 
 template <class _ExecutionPolicy>
-const auto& __remove_parallel_policy(_ExecutionPolicy&&) {
+_LIBCPP_HIDE_FROM_ABI const auto& __remove_parallel_policy(_ExecutionPolicy&&) {
   using _ExecPol = __remove_cvref_t<_ExecutionPolicy>;
   if constexpr (is_same_v<_ExecPol, execution::parallel_policy>) {
     return execution::seq;
@@ -146,6 +146,6 @@
 
 _LIBCPP_END_NAMESPACE_STD
 
-#endif // defined(_LIBCPP_HAS_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP_EXECUTION
diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in
--- a/libcxx/include/module.modulemap.in
+++ b/libcxx/include/module.modulemap.in
@@ -635,7 +635,11 @@
         private header "__atomic/aliases.h"
         export atomic
       }
-      module atomic              { private header "__atomic/atomic.h" }
+      module atomic              {
+        private header "__atomic/atomic.h"
+
+        export atomic_base
+      }
       module atomic_base         { private header "__atomic/atomic_base.h" }
       module atomic_flag         { private header "__atomic/atomic_flag.h" }
       module atomic_init         { private header "__atomic/atomic_init.h" }
diff --git a/libcxx/test/libcxx/diagnostics/pstl.nodiscard_extensions.compile.pass.cpp b/libcxx/test/libcxx/diagnostics/pstl.nodiscard_extensions.compile.pass.cpp
--- a/libcxx/test/libcxx/diagnostics/pstl.nodiscard_extensions.compile.pass.cpp
+++ b/libcxx/test/libcxx/diagnostics/pstl.nodiscard_extensions.compile.pass.cpp
@@ -11,12 +11,13 @@
 
 // ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_DISABLE_NODISCARD_EXT
 
-// REQUIRES: with-pstl
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
 
 // UNSUPPORTED: c++03, c++11, c++14
 
 #include <algorithm>
 #include <execution>
+#include <iterator>
 
 void test() {
   int a[] = {1};
diff --git a/libcxx/test/libcxx/diagnostics/pstl.nodiscard_extensions.verify.cpp b/libcxx/test/libcxx/diagnostics/pstl.nodiscard_extensions.verify.cpp
--- a/libcxx/test/libcxx/diagnostics/pstl.nodiscard_extensions.verify.cpp
+++ b/libcxx/test/libcxx/diagnostics/pstl.nodiscard_extensions.verify.cpp
@@ -8,12 +8,13 @@
 
 // Check that PSTL algorithms are marked [[nodiscard]] as a conforming extension
 
-// REQUIRES: with-pstl
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
 
 // UNSUPPORTED: c++03, c++11, c++14
 
 #include <algorithm>
 #include <execution>
+#include <iterator>
 
 void test() {
   int a[] = {1};
diff --git a/libcxx/test/libcxx/transitive_includes.sh.cpp b/libcxx/test/libcxx/transitive_includes.sh.cpp
--- a/libcxx/test/libcxx/transitive_includes.sh.cpp
+++ b/libcxx/test/libcxx/transitive_includes.sh.cpp
@@ -32,9 +32,6 @@
 // this test instead.
 // UNSUPPORTED: transitive-includes-disabled
 
-// FIXME: This should pass with the PSTL enabled
-// XFAIL: with-pstl
-
 // Prevent <ext/hash_map> from generating deprecated warnings for this test.
 #if defined(__DEPRECATED)
 #    undef __DEPRECATED
diff --git a/libcxx/test/libcxx/transitive_includes/cxx03.csv b/libcxx/test/libcxx/transitive_includes/cxx03.csv
--- a/libcxx/test/libcxx/transitive_includes/cxx03.csv
+++ b/libcxx/test/libcxx/transitive_includes/cxx03.csv
@@ -6,12 +6,14 @@
 algorithm cstdint
 algorithm cstdlib
 algorithm cstring
+algorithm ctime
 algorithm initializer_list
 algorithm iosfwd
 algorithm iterator
 algorithm limits
 algorithm memory
 algorithm new
+algorithm ratio
 algorithm stdexcept
 algorithm type_traits
 algorithm utility
diff --git a/libcxx/test/libcxx/transitive_includes/cxx11.csv b/libcxx/test/libcxx/transitive_includes/cxx11.csv
--- a/libcxx/test/libcxx/transitive_includes/cxx11.csv
+++ b/libcxx/test/libcxx/transitive_includes/cxx11.csv
@@ -6,12 +6,14 @@
 algorithm cstdint
 algorithm cstdlib
 algorithm cstring
+algorithm ctime
 algorithm initializer_list
 algorithm iosfwd
 algorithm iterator
 algorithm limits
 algorithm memory
 algorithm new
+algorithm ratio
 algorithm stdexcept
 algorithm type_traits
 algorithm utility
diff --git a/libcxx/test/libcxx/transitive_includes/cxx14.csv b/libcxx/test/libcxx/transitive_includes/cxx14.csv
--- a/libcxx/test/libcxx/transitive_includes/cxx14.csv
+++ b/libcxx/test/libcxx/transitive_includes/cxx14.csv
@@ -6,12 +6,14 @@
 algorithm cstdint
 algorithm cstdlib
 algorithm cstring
+algorithm ctime
 algorithm initializer_list
 algorithm iosfwd
 algorithm iterator
 algorithm limits
 algorithm memory
 algorithm new
+algorithm ratio
 algorithm stdexcept
 algorithm type_traits
 algorithm utility
diff --git a/libcxx/test/libcxx/transitive_includes/cxx17.csv b/libcxx/test/libcxx/transitive_includes/cxx17.csv
--- a/libcxx/test/libcxx/transitive_includes/cxx17.csv
+++ b/libcxx/test/libcxx/transitive_includes/cxx17.csv
@@ -6,12 +6,14 @@
 algorithm cstdint
 algorithm cstdlib
 algorithm cstring
+algorithm ctime
 algorithm initializer_list
 algorithm iosfwd
 algorithm iterator
 algorithm limits
 algorithm memory
 algorithm new
+algorithm ratio
 algorithm stdexcept
 algorithm type_traits
 algorithm utility
diff --git a/libcxx/test/libcxx/transitive_includes/cxx20.csv b/libcxx/test/libcxx/transitive_includes/cxx20.csv
--- a/libcxx/test/libcxx/transitive_includes/cxx20.csv
+++ b/libcxx/test/libcxx/transitive_includes/cxx20.csv
@@ -6,12 +6,14 @@
 algorithm cstdint
 algorithm cstdlib
 algorithm cstring
+algorithm ctime
 algorithm initializer_list
 algorithm iosfwd
 algorithm iterator
 algorithm limits
 algorithm memory
 algorithm new
+algorithm ratio
 algorithm stdexcept
 algorithm type_traits
 algorithm utility
diff --git a/libcxx/test/libcxx/transitive_includes/cxx2b.csv b/libcxx/test/libcxx/transitive_includes/cxx2b.csv
--- a/libcxx/test/libcxx/transitive_includes/cxx2b.csv
+++ b/libcxx/test/libcxx/transitive_includes/cxx2b.csv
@@ -2,10 +2,12 @@
 algorithm cstddef
 algorithm cstdint
 algorithm cstring
+algorithm ctime
 algorithm initializer_list
 algorithm iosfwd
 algorithm limits
 algorithm new
+algorithm ratio
 algorithm version
 any cstddef
 any cstdint
diff --git a/libcxx/test/libcxx/utilities/expol/policies.compile.pass.cpp b/libcxx/test/libcxx/utilities/expol/policies.compile.pass.cpp
--- a/libcxx/test/libcxx/utilities/expol/policies.compile.pass.cpp
+++ b/libcxx/test/libcxx/utilities/expol/policies.compile.pass.cpp
@@ -10,7 +10,7 @@
 
 // UNSUPPORTED: c++03, c++11, c++14
 
-// REQUIRES: with-pstl
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
 
 #include <execution>
 #include <type_traits>
diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/pstl.fill.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/pstl.fill.pass.cpp
--- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/pstl.fill.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/pstl.fill.pass.cpp
@@ -10,7 +10,7 @@
 
 // UNSUPPORTED: c++03, c++11, c++14
 
-// REQUIRES: with-pstl
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
 
 // template<class ExecutionPolicy, class ForwardIterator, class T>
 //   void fill(ExecutionPolicy&& exec,
@@ -61,9 +61,11 @@
   }
 };
 
+#ifndef TEST_HAS_NO_EXCEPTIONS
 struct ThrowOnCopy {
   ThrowOnCopy& operator=(const ThrowOnCopy&) { throw int{}; }
 };
+#endif
 
 int main(int, char**) {
   types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/pstl.fill_n.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/pstl.fill_n.pass.cpp
--- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/pstl.fill_n.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/pstl.fill_n.pass.cpp
@@ -10,7 +10,7 @@
 
 // UNSUPPORTED: c++03, c++11, c++14
 
-// REQUIRES: with-pstl
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
 
 // template<class ExecutionPolicy, class ForwardIterator, class Size, class T>
 //   ForwardIterator fill_n(ExecutionPolicy&& exec,
@@ -61,9 +61,11 @@
   }
 };
 
+#ifndef TEST_HAS_NO_EXCEPTIONS
 struct ThrowOnCopy {
   ThrowOnCopy& operator=(const ThrowOnCopy&) { throw int{}; }
 };
+#endif
 
 int main(int, char**) {
   types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.all_of/pstl.all_of.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.all_of/pstl.all_of.pass.cpp
--- a/libcxx/test/std/algorithms/alg.nonmodifying/alg.all_of/pstl.all_of.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.all_of/pstl.all_of.pass.cpp
@@ -8,7 +8,7 @@
 
 // UNSUPPORTED: c++03, c++11, c++14
 
-// REQUIRES: with-pstl
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
 
 // <algorithm>
 
diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.any_of/pstl.any_of.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.any_of/pstl.any_of.pass.cpp
--- a/libcxx/test/std/algorithms/alg.nonmodifying/alg.any_of/pstl.any_of.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.any_of/pstl.any_of.pass.cpp
@@ -8,7 +8,7 @@
 
 // UNSUPPORTED: c++03, c++11, c++14
 
-// REQUIRES: with-pstl
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
 
 // <algorithm>
 
diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/pstl.find.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/pstl.find.pass.cpp
--- a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/pstl.find.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/pstl.find.pass.cpp
@@ -8,7 +8,7 @@
 
 // UNSUPPORTED: c++03, c++11, c++14
 
-// REQUIRES: with-pstl
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
 
 // <algorithm>
 
@@ -63,7 +63,9 @@
 
 struct ThrowOnCompare {};
 
+#ifndef TEST_HAS_NO_EXCEPTIONS
 bool operator==(ThrowOnCompare, ThrowOnCompare) { throw int{}; }
+#endif
 
 int main(int, char**) {
   types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/pstl.find_if.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/pstl.find_if.pass.cpp
--- a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/pstl.find_if.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/pstl.find_if.pass.cpp
@@ -8,7 +8,7 @@
 
 // UNSUPPORTED: c++03, c++11, c++14
 
-// REQUIRES: with-pstl
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
 
 // <algorithm>
 
diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/pstl.find_if_not.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/pstl.find_if_not.pass.cpp
--- a/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/pstl.find_if_not.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.find/pstl.find_if_not.pass.cpp
@@ -8,7 +8,7 @@
 
 // UNSUPPORTED: c++03, c++11, c++14
 
-// REQUIRES: with-pstl
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
 
 // <algorithm>
 
diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/pstl.for_each.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/pstl.for_each.pass.cpp
--- a/libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/pstl.for_each.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/pstl.for_each.pass.cpp
@@ -8,7 +8,7 @@
 
 // UNSUPPORTED: c++03, c++11, c++14
 
-// REQUIRES: with-pstl
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
 
 // <algorithm>
 
diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/pstl.for_each_n.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/pstl.for_each_n.pass.cpp
--- a/libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/pstl.for_each_n.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/pstl.for_each_n.pass.cpp
@@ -8,7 +8,7 @@
 
 // UNSUPPORTED: c++03, c++11, c++14
 
-// REQUIRES: with-pstl
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
 
 // <algorithm>
 
diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.none_of/pstl.none_of.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.none_of/pstl.none_of.pass.cpp
--- a/libcxx/test/std/algorithms/alg.nonmodifying/alg.none_of/pstl.none_of.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.none_of/pstl.none_of.pass.cpp
@@ -6,7 +6,9 @@
 //
 //===----------------------------------------------------------------------===//
 
-// REQUIRES: with-pstl
+// UNSUPPORTED: c++03, c++11, c++14
+
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
 
 // <algorithm>
 
diff --git a/libcxx/test/std/utilities/expol/is_execution_policy.compile.pass.cpp b/libcxx/test/std/utilities/expol/is_execution_policy.compile.pass.cpp
--- a/libcxx/test/std/utilities/expol/is_execution_policy.compile.pass.cpp
+++ b/libcxx/test/std/utilities/expol/is_execution_policy.compile.pass.cpp
@@ -11,7 +11,7 @@
 
 // UNSUPPORTED: c++03, c++11, c++14
 
-// REQUIRES: with-pstl
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
 
 #include <execution>
 
diff --git a/libcxx/test/std/utilities/expol/policies.compile.pass.cpp b/libcxx/test/std/utilities/expol/policies.compile.pass.cpp
--- a/libcxx/test/std/utilities/expol/policies.compile.pass.cpp
+++ b/libcxx/test/std/utilities/expol/policies.compile.pass.cpp
@@ -18,7 +18,7 @@
 
 // UNSUPPORTED: c++03, c++11, c++14
 
-// REQUIRES: with-pstl
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
 
 #include <execution>
 #include <type_traits>
diff --git a/libcxx/utils/ci/buildkite-pipeline.yml b/libcxx/utils/ci/buildkite-pipeline.yml
--- a/libcxx/utils/ci/buildkite-pipeline.yml
+++ b/libcxx/utils/ci/buildkite-pipeline.yml
@@ -465,22 +465,6 @@
           limit: 2
     timeout_in_minutes: 120
 
-  - label: "With PSTL support"
-    command: "libcxx/utils/ci/run-buildbot with-pstl"
-    artifact_paths:
-      - "**/test-results.xml"
-    env:
-      CC: "clang-${LLVM_HEAD_VERSION}"
-      CXX: "clang++-${LLVM_HEAD_VERSION}"
-    agents:
-      queue: "libcxx-builders"
-      os: "linux"
-    retry:
-      automatic:
-        - exit_status: -1  # Agent was lost
-          limit: 2
-    timeout_in_minutes: 120
-
   - label: "With LLVM's libunwind"
     command: "libcxx/utils/ci/run-buildbot generic-with_llvm_unwinder"
     artifact_paths:
diff --git a/libcxx/utils/ci/run-buildbot b/libcxx/utils/ci/run-buildbot
--- a/libcxx/utils/ci/run-buildbot
+++ b/libcxx/utils/ci/run-buildbot
@@ -448,11 +448,6 @@
     generate-cmake -C "${MONOREPO_ROOT}/libcxx/cmake/caches/Generic-abi-unstable.cmake"
     check-runtimes
 ;;
-with-pstl)
-    clean
-    generate-cmake -C "${MONOREPO_ROOT}/libcxx/cmake/caches/With-pstl.cmake"
-    check-runtimes
-;;
 apple-system)
     clean
 
diff --git a/libcxx/utils/libcxx/test/features.py b/libcxx/utils/libcxx/test/features.py
--- a/libcxx/utils/libcxx/test/features.py
+++ b/libcxx/utils/libcxx/test/features.py
@@ -209,7 +209,6 @@
   '_LIBCPP_HAS_NO_WIDE_CHARACTERS': 'no-wide-characters',
   '_LIBCPP_HAS_NO_UNICODE': 'libcpp-has-no-unicode',
   '_LIBCPP_ENABLE_DEBUG_MODE': 'libcpp-has-debug-mode',
-  '_LIBCPP_HAS_PARALLEL_ALGORITHMS': 'with-pstl',
 }
 for macro, feature in macros.items():
   DEFAULT_FEATURES.append(
diff --git a/libcxx/utils/libcxx/test/params.py b/libcxx/utils/libcxx/test/params.py
--- a/libcxx/utils/libcxx/test/params.py
+++ b/libcxx/utils/libcxx/test/params.py
@@ -184,6 +184,7 @@
               AddCompileFlag('-D_LIBCPP_ENABLE_EXPERIMENTAL'),
             ] if experimental else [
               AddFeature('libcpp-has-no-incomplete-format'),
+              AddFeature('libcpp-has-no-incomplete-pstl'),
             ]),
 
   Parameter(name='long_tests', choices=[True, False], type=bool, default=True,