diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt
--- a/libcxx/include/CMakeLists.txt
+++ b/libcxx/include/CMakeLists.txt
@@ -59,6 +59,7 @@
   __algorithm/mismatch.h
   __algorithm/move.h
   __algorithm/move_backward.h
+  __algorithm/negate_function.h
   __algorithm/next_permutation.h
   __algorithm/none_of.h
   __algorithm/nth_element.h
diff --git a/libcxx/include/__algorithm/negate_function.h b/libcxx/include/__algorithm/negate_function.h
new file mode 100644
--- /dev/null
+++ b/libcxx/include/__algorithm/negate_function.h
@@ -0,0 +1,41 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_NEGATE_FUNCTION_H
+#define _LIBCPP___ALGORITHM_NEGATE_FUNCTION_H
+
+#include <__config>
+#include <__utility/forward.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _Functor>
+struct _NegFunctor {
+  _Functor& __func_;
+  _NegFunctor(_Functor& __func) : __func_(__func) {}
+
+  template <class... _Args>
+  decltype(auto) operator()(_Args&&... __args) {
+    return !__func_(std::forward<_Args>(__args)...);
+  }
+};
+
+_LIBCPP_CTAD_SUPPORTED_FOR_TYPE(_NegFunctor);
+
+template <class _Functor>
+auto __negate_function(_Functor& __func) {
+  return _NegFunctor{__func};
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___ALGORITHM_NEGATE_FUNCTION_H
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
@@ -10,8 +10,8 @@
 #define _LIBCPP___ALGORITHM_PSTL_ANY_ALL_NONE_OF_H
 
 #include <__algorithm/any_of.h>
+#include <__algorithm/negate_function.h>
 #include <__config>
-#include <__functional/not_fn.h>
 #include <__pstl/internal/parallel_impl.h>
 #include <__pstl/internal/unseq_backend_simd.h>
 #include <__type_traits/enable_if.h>
@@ -58,7 +58,7 @@
           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, std::__negate_function(__pred));
 }
 
 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
@@ -11,8 +11,8 @@
 
 #include <__algorithm/comp.h>
 #include <__algorithm/find.h>
+#include <__algorithm/negate_function.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 +94,7 @@
           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, std::__negate_function(__pred));
 }
 
 _LIBCPP_END_NAMESPACE_STD
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_base.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
 {
@@ -35,7 +33,7 @@
     typedef typename std::iterator_traits<_Index>::difference_type _DifferenceType;
     const _DifferenceType __n = __last - __first;
     _DifferenceType __initial_dist = __b_first ? __n : -1;
-    std::atomic<_DifferenceType> __extremum(__initial_dist);
+    std::__atomic_base<_DifferenceType> __extremum(__initial_dist);
     // TODO: find out what is better here: parallel_for or parallel_reduce
     __par_backend::__parallel_for(__tag, std::forward<_ExecutionPolicy>(__exec), __first, __last,
                                   [__comp, __f, __first, &__extremum](_Index __i, _Index __j)
@@ -67,7 +65,7 @@
 template <class _BackendTag, class _ExecutionPolicy, class _Index, class _Brick>
 _LIBCPP_HIDE_FROM_ABI
 bool __parallel_or(_BackendTag __tag, _ExecutionPolicy&& __exec, _Index __first, _Index __last, _Brick __f) {
-    std::atomic<bool> __found(false);
+    std::__atomic_base<bool> __found(false);
     __par_backend::__parallel_for(__tag, std::forward<_ExecutionPolicy>(__exec), __first, __last,
                                   [__f, &__found](_Index __i, _Index __j)
                                   {
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/module.modulemap.in b/libcxx/include/module.modulemap.in
--- a/libcxx/include/module.modulemap.in
+++ b/libcxx/include/module.modulemap.in
@@ -310,6 +310,7 @@
       module mismatch                        { private header "__algorithm/mismatch.h" }
       module move                            { private header "__algorithm/move.h" }
       module move_backward                   { private header "__algorithm/move_backward.h" }
+      module negate_function                { private header "__algorithm/negate_function.h" }
       module next_permutation                { private header "__algorithm/next_permutation.h" }
       module none_of                         { private header "__algorithm/none_of.h" }
       module nth_element                     { private header "__algorithm/nth_element.h" }
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/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp
--- a/libcxx/test/libcxx/private_headers.verify.cpp
+++ b/libcxx/test/libcxx/private_headers.verify.cpp
@@ -104,6 +104,7 @@
 #include <__algorithm/mismatch.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/mismatch.h'}}
 #include <__algorithm/move.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/move.h'}}
 #include <__algorithm/move_backward.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/move_backward.h'}}
+#include <__algorithm/negate_function.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/negate_function.h'}}
 #include <__algorithm/next_permutation.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/next_permutation.h'}}
 #include <__algorithm/none_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/none_of.h'}}
 #include <__algorithm/nth_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/nth_element.h'}}
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>