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
@@ -11,7 +11,7 @@
 
 #include <__algorithm/any_of.h>
 #include <__config>
-#include <__functional/not_fn.h>
+#include <__iterator/iterator_traits.h>
 #include <__pstl/internal/parallel_impl.h>
 #include <__pstl/internal/unseq_backend_simd.h>
 #include <__type_traits/enable_if.h>
@@ -58,7 +58,9 @@
           enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
 _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI bool
 all_of(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred __pred) {
-  return !std::any_of(__policy, __first, __last, std::not_fn(__pred));
+  return !std::any_of(__policy, __first, __last, [&](__iter_reference<_ForwardIterator> __value) {
+    return !__pred(__value);
+  });
 }
 
 template <class _ExecutionPolicy,
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
@@ -12,7 +12,6 @@
 #include <__algorithm/comp.h>
 #include <__algorithm/find.h>
 #include <__config>
-#include <__functional/not_fn.h>
 #include <__pstl/internal/parallel_impl.h>
 #include <__pstl/internal/unseq_backend_simd.h>
 #include <__type_traits/is_execution_policy.h>
@@ -94,7 +93,9 @@
           enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
 _LIBCPP_HIDE_FROM_ABI _ForwardIterator
 find_if_not(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
-  return std::find_if(__policy, __first, __last, std::not_fn(std::move(__pred)));
+  return std::find_if(__policy, __first, __last, [&](__iter_reference<_ForwardIterator> __value) {
+    return !__pred(__value);
+  });
 }
 
 _LIBCPP_END_NAMESPACE_STD
diff --git a/libcxx/include/__iterator/iterator_traits.h b/libcxx/include/__iterator/iterator_traits.h
--- a/libcxx/include/__iterator/iterator_traits.h
+++ b/libcxx/include/__iterator/iterator_traits.h
@@ -534,6 +534,9 @@
 template<class _InputIterator>
 using __iter_value_type = typename iterator_traits<_InputIterator>::value_type;
 
+template <class _Iter>
+using __iter_reference = typename iterator_traits<_Iter>::reference;
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ITERATOR_ITERATOR_TRAITS_H
diff --git a/libcxx/include/__memory/allocator.h b/libcxx/include/__memory/allocator.h
--- a/libcxx/include/__memory/allocator.h
+++ b/libcxx/include/__memory/allocator.h
@@ -21,7 +21,6 @@
 #include <__utility/forward.h>
 #include <cstddef>
 #include <new>
-#include <stdexcept>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
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
@@ -10,7 +10,9 @@
 #ifndef _PSTL_EXECUTION_POLICY_DEFS_H
 #define _PSTL_EXECUTION_POLICY_DEFS_H
 
-#include <type_traits>
+#include <__type_traits/decay.h>
+#include <__type_traits/enable_if.h>
+#include <__type_traits/integral_constant.h>
 
 #include "pstl_config.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
@@ -10,8 +10,7 @@
 #ifndef _PSTL_EXECUTION_IMPL_H
 #define _PSTL_EXECUTION_IMPL_H
 
-#include <iterator>
-#include <type_traits>
+#include <__iterator/iterator_traits.h>
 
 #include "execution_defs.h"
 #include "pstl_config.h"
diff --git a/libcxx/include/__pstl/internal/parallel_backend_utils.h b/libcxx/include/__pstl/internal/parallel_backend_utils.h
--- a/libcxx/include/__pstl/internal/parallel_backend_utils.h
+++ b/libcxx/include/__pstl/internal/parallel_backend_utils.h
@@ -10,8 +10,9 @@
 #ifndef _PSTL_PARALLEL_BACKEND_UTILS_H
 #define _PSTL_PARALLEL_BACKEND_UTILS_H
 
-#include <iterator>
-#include <utility>
+#include <__iterator/iterator_traits.h>
+#include <__memory/addressof.h>
+
 #include "utils.h"
 
 #include "pstl_config.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
@@ -12,10 +12,8 @@
 
 #include "pstl_config.h"
 
+#include <__atomic/atomic.h>
 #include <__pstl/internal/parallel_backend.h>
-#include <atomic>
-// This header defines the minimum set of parallel routines required to support Parallel STL,
-// implemented on top of Intel(R) Threading Building Blocks (Intel(R) TBB) library
 
 namespace __pstl
 {
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,7 @@
 #define _PSTL_UNSEQ_BACKEND_SIMD_H
 
 #include <__functional/operations.h>
-#include <type_traits>
+#include <__utility/pair.h>
 
 #include "pstl_config.h"
 #include "utils.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
@@ -11,9 +11,9 @@
 #define _PSTL_UTILS_H
 
 #include <__exception/terminate.h>
-#include <iterator>
+#include <__pstl/internal/pstl_config.h>
+#include <__utility/forward.h>
 #include <new>
-#include <utility>
 
 namespace __pstl {
 namespace __internal {
diff --git a/libcxx/include/__utility/terminate_on_exception.h b/libcxx/include/__utility/terminate_on_exception.h
--- a/libcxx/include/__utility/terminate_on_exception.h
+++ b/libcxx/include/__utility/terminate_on_exception.h
@@ -10,7 +10,7 @@
 #define _LIBCPP___UTILITY_TERMINATE_ON_EXCEPTION_H
 
 #include <__config>
-#include <exception>
+#include <__exception/terminate.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
diff --git a/libcxx/include/any b/libcxx/include/any
--- a/libcxx/include/any
+++ b/libcxx/include/any
@@ -721,6 +721,7 @@
 #  include <iosfwd>
 #  include <iterator>
 #  include <memory>
+#  include <stdexcept>
 #  include <type_traits>
 #  include <variant>
 #endif
diff --git a/libcxx/include/valarray b/libcxx/include/valarray
--- a/libcxx/include/valarray
+++ b/libcxx/include/valarray
@@ -4937,6 +4937,7 @@
 #  include <cstdlib>
 #  include <cstring>
 #  include <functional>
+#  include <stdexcept>
 #  include <type_traits>
 #endif
 
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
@@ -13,7 +13,6 @@
 any initializer_list
 any limits
 any new
-any stdexcept
 any typeinfo
 any version
 array compare
@@ -635,7 +634,6 @@
 valarray initializer_list
 valarray limits
 valarray new
-valarray stdexcept
 valarray version
 variant compare
 variant cstddef
diff --git a/libcxx/test/support/test_execution_policies.h b/libcxx/test/support/test_execution_policies.h
--- a/libcxx/test/support/test_execution_policies.h
+++ b/libcxx/test/support/test_execution_policies.h
@@ -10,6 +10,7 @@
 #define TEST_SUPPORT_TEST_EXECUTION_POLICIES
 
 #include <cstdlib>
+#include <exception>
 #include <execution>
 #include <type_traits>
 #include <utility>