diff --git a/libcxx/include/__tuple b/libcxx/include/__tuple
--- a/libcxx/include/__tuple
+++ b/libcxx/include/__tuple
@@ -383,12 +383,6 @@
   typedef _LIBCPP_NODEBUG_TYPE __tuple_types<_Types...> type;
 };
 
-template <bool ..._Preds>
-struct __all_dummy;
-
-template <bool ..._Pred>
-using __all = _IsSame<__all_dummy<_Pred...>, __all_dummy<((void)_Pred, true)...>>;
-
 struct __tuple_sfinae_base {
   template <template <class, class...> class _Trait,
             class ..._LArgs, class ..._RArgs>
diff --git a/libcxx/include/type_traits b/libcxx/include/type_traits
--- a/libcxx/include/type_traits
+++ b/libcxx/include/type_traits
@@ -461,6 +461,50 @@
 template <bool _Val>
 using _BoolConstant _LIBCPP_NODEBUG_TYPE = integral_constant<bool, _Val>;
 
+// is_same
+
+#if __has_keyword(__is_same)
+
+template <class _Tp, class _Up>
+struct _LIBCPP_TEMPLATE_VIS is_same : _BoolConstant<__is_same(_Tp, _Up)> { };
+
+#if _LIBCPP_STD_VER > 14 && !defined(_LIBCPP_HAS_NO_VARIABLE_TEMPLATES)
+template <class _Tp, class _Up>
+_LIBCPP_INLINE_VAR _LIBCPP_CONSTEXPR bool is_same_v = __is_same(_Tp, _Up);
+#endif
+
+#else
+
+template <class _Tp, class _Up> struct _LIBCPP_TEMPLATE_VIS is_same           : public false_type {};
+template <class _Tp>            struct _LIBCPP_TEMPLATE_VIS is_same<_Tp, _Tp> : public true_type {};
+
+#if _LIBCPP_STD_VER > 14 && !defined(_LIBCPP_HAS_NO_VARIABLE_TEMPLATES)
+template <class _Tp, class _Up>
+_LIBCPP_INLINE_VAR _LIBCPP_CONSTEXPR bool is_same_v
+    = is_same<_Tp, _Up>::value;
+#endif
+
+#endif // __is_same
+
+template <class _Tp, class _Up>
+using _IsSame = _BoolConstant<
+#ifdef __clang__
+    __is_same(_Tp, _Up)
+#else
+    _VSTD::is_same<_Tp, _Up>::value
+#endif
+>;
+
+template <class _Tp, class _Up>
+using _IsNotSame = _BoolConstant<
+#ifdef __clang__
+    !__is_same(_Tp, _Up)
+#else
+    !_VSTD::is_same<_Tp, _Up>::value
+#endif
+>;
+
+// type_traits helpers for use within the library
 template <bool> struct _MetaBase;
 template <>
 struct _MetaBase<true> {
@@ -476,8 +520,6 @@
   using _EnableIfImpl _LIBCPP_NODEBUG_TYPE = _Tp;
   template <class _Result, class _First, class ..._Rest>
   using _OrImpl _LIBCPP_NODEBUG_TYPE = typename _MetaBase<_First::value != true && sizeof...(_Rest) != 0>::template _OrImpl<_First, _Rest...>;
-  template <class _Result, class _First, class ..._Rest>
-  using _AndImpl _LIBCPP_NODEBUG_TYPE = typename _MetaBase<_First::value == true && sizeof...(_Rest) != 0>::template _AndImpl<_First, _Rest...>;
 };
 
 template <>
@@ -488,8 +530,6 @@
   using _SelectApplyImpl _LIBCPP_NODEBUG_TYPE = _SecondFn<_Args...>;
   template <class _Result, class ...>
   using _OrImpl _LIBCPP_NODEBUG_TYPE = _Result;
-  template <class _Result, class ...>
-  using _AndImpl _LIBCPP_NODEBUG_TYPE = _Result;
 };
 template <bool _Cond, class _Ret = void>
 using _EnableIf _LIBCPP_NODEBUG_TYPE = typename _MetaBase<_Cond>::template _EnableIfImpl<_Ret>;
@@ -497,8 +537,6 @@
 using _If _LIBCPP_NODEBUG_TYPE = typename _MetaBase<_Cond>::template _SelectImpl<_IfRes, _ElseRes>;
 template <class ..._Rest>
 using _Or _LIBCPP_NODEBUG_TYPE = typename _MetaBase< sizeof...(_Rest) != 0 >::template _OrImpl<false_type, _Rest...>;
-template <class ..._Rest>
-using _And _LIBCPP_NODEBUG_TYPE = typename _MetaBase< sizeof...(_Rest) != 0 >::template _AndImpl<true_type, _Rest...>;
 template <class _Pred>
 struct _Not : _BoolConstant<!_Pred::value> {};
 template <class ..._Args>
@@ -506,6 +544,15 @@
 template <class ..._Args>
 using _SecondType _LIBCPP_NODEBUG_TYPE = typename _MetaBase<(sizeof...(_Args) >= 2)>::template _SecondImpl<_Args...>;
 
+template <bool ..._Preds> struct __all_dummy;
+template <bool ..._Pred> using __all = _IsSame<__all_dummy<_Pred...>, __all_dummy<((void)_Pred, true)...> >;
+template <class ..._Pred>
+__all<_EnableIf<_Pred::value, bool>(true)...> __and_helper(int);
+template <class ...>
+false_type __and_helper(...);
+template <class ..._Pred>
+using _And _LIBCPP_NODEBUG_TYPE = decltype(__and_helper<_Pred...>(0));
+
 template <template <class...> class _Func, class ..._Args>
 struct _Lazy : _Func<_Args...> {};
 
@@ -548,49 +595,6 @@
 template <bool _Bp, class _Tp = void> using enable_if_t = typename enable_if<_Bp, _Tp>::type;
 #endif
 
-// is_same
-
-#if __has_keyword(__is_same)
-
-template <class _Tp, class _Up>
-struct _LIBCPP_TEMPLATE_VIS is_same : _BoolConstant<__is_same(_Tp, _Up)> { };
-
-#if _LIBCPP_STD_VER > 14 && !defined(_LIBCPP_HAS_NO_VARIABLE_TEMPLATES)
-template <class _Tp, class _Up>
-_LIBCPP_INLINE_VAR _LIBCPP_CONSTEXPR bool is_same_v = __is_same(_Tp, _Up);
-#endif
-
-#else
-
-template <class _Tp, class _Up> struct _LIBCPP_TEMPLATE_VIS is_same           : public false_type {};
-template <class _Tp>            struct _LIBCPP_TEMPLATE_VIS is_same<_Tp, _Tp> : public true_type {};
-
-#if _LIBCPP_STD_VER > 14 && !defined(_LIBCPP_HAS_NO_VARIABLE_TEMPLATES)
-template <class _Tp, class _Up>
-_LIBCPP_INLINE_VAR _LIBCPP_CONSTEXPR bool is_same_v
-    = is_same<_Tp, _Up>::value;
-#endif
-
-#endif // __is_same
-
-template <class _Tp, class _Up>
-using _IsSame = _BoolConstant<
-#ifdef __clang__
-    __is_same(_Tp, _Up)
-#else
-    _VSTD::is_same<_Tp, _Up>::value
-#endif
->;
-
-template <class _Tp, class _Up>
-using _IsNotSame = _BoolConstant<
-#ifdef __clang__
-    !__is_same(_Tp, _Up)
-#else
-    !_VSTD::is_same<_Tp, _Up>::value
-#endif
->;
-
 
 template <class _Tp>
 using __test_for_primary_template = _EnableIf<
@@ -603,8 +607,6 @@
 
 struct __two {char __lx[2];};
 
-// helper class:
-
 // is_const
 
 #if __has_keyword(__is_const)
diff --git a/libcxx/test/std/utilities/tuple/tuple.tuple/tuple.cnstr/recursion_depth.pass.cpp b/libcxx/test/std/utilities/tuple/tuple.tuple/tuple.cnstr/recursion_depth.pass.cpp
new file mode 100644
--- /dev/null
+++ b/libcxx/test/std/utilities/tuple/tuple.tuple/tuple.cnstr/recursion_depth.pass.cpp
@@ -0,0 +1,35 @@
+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11
+
+// Make sure that we don't blow up the template instantiation recursion depth
+// for tuples of size <= 1024.
+
+#include <tuple>
+#include <cassert>
+#include <utility>
+
+template <size_t... I>
+constexpr void CreateTuple(std::index_sequence<I...>) {
+  std::tuple<decltype(I)...> tuple(I...);
+  assert(std::get<0>(tuple) == 0);
+  assert(std::get<sizeof...(I)-1>(tuple) == sizeof...(I)-1);
+}
+
+constexpr bool test() {
+  CreateTuple(std::make_index_sequence<1024>{});
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test(), "");
+  return 0;
+}