[libcxx/variant] Introduce `switch`-based mechanism for `std::visit`.

[mpark]

Summary

This patch introduces mechanism for std::visit backed by switch.
The switch is structured such that it's a flattened manual vtable (an n-ary array).
The switch mechanism is enabled if (1 * ... * vs.size()) < 256.

The following are performance numbers from the benchmarks added in D85419, tested on my 2017 Macbook Pro.

Before: using only the manual vtable mechanism.

$ ./projects/libcxx/benchmarks/variant_visit_1.libcxx.out
2020-08-09 23:55:14
Running ./projects/libcxx/benchmarks/variant_visit_1.libcxx.out
Run on (8 X 3100 MHz CPU s)
CPU Caches:
  L1 Data 32K (x4)
  L1 Instruction 32K (x4)
  L2 Unified 262K (x4)
  L3 Unified 8388K (x1)
Load Average: 2.03, 2.36, 2.43
------------------------------------------------------------
Benchmark                 Time             CPU   Iterations
------------------------------------------------------------
BM_Visit<1, 1>        0.260 ns        0.260 ns   1000000000
BM_Visit<1, 2>         1.56 ns         1.56 ns    435925220
BM_Visit<1, 3>         1.55 ns         1.55 ns    444416228
BM_Visit<1, 4>         1.57 ns         1.57 ns    427951336
BM_Visit<1, 5>         1.57 ns         1.56 ns    444766371
BM_Visit<1, 6>         1.70 ns         1.68 ns    446639358
BM_Visit<1, 7>         1.64 ns         1.64 ns    400441630
BM_Visit<1, 8>         1.56 ns         1.56 ns    430729471
BM_Visit<1, 9>         1.58 ns         1.58 ns    449894596
BM_Visit<1, 10>        1.54 ns         1.54 ns    449660506
BM_Visit<1, 20>        1.56 ns         1.56 ns    450813074
BM_Visit<1, 30>        1.59 ns         1.59 ns    440032940
BM_Visit<1, 40>        1.59 ns         1.59 ns    443731656
BM_Visit<1, 50>        1.56 ns         1.56 ns    444709859
BM_Visit<1, 60>        1.59 ns         1.58 ns    439527320
BM_Visit<1, 70>        1.57 ns         1.57 ns    438450890
BM_Visit<1, 80>        1.58 ns         1.58 ns    443001525
BM_Visit<1, 90>        1.63 ns         1.62 ns    448456349
BM_Visit<1, 100>       1.57 ns         1.57 ns    445740630

$ ./projects/libcxx/benchmarks/variant_visit_2.libcxx.out
2020-08-09 23:59:35
Running ./projects/libcxx/benchmarks/variant_visit_2.libcxx.out
Run on (8 X 3100 MHz CPU s)
CPU Caches:
  L1 Data 32K (x4)
  L1 Instruction 32K (x4)
  L2 Unified 262K (x4)
  L3 Unified 8388K (x1)
Load Average: 1.40, 1.94, 2.22
-----------------------------------------------------------
Benchmark                Time             CPU   Iterations
-----------------------------------------------------------
BM_Visit<2, 1>       0.261 ns        0.260 ns   1000000000
BM_Visit<2, 2>        1.55 ns         1.54 ns    432844219
BM_Visit<2, 3>        1.30 ns         1.30 ns    532529974
BM_Visit<2, 4>        1.54 ns         1.54 ns    446055910
BM_Visit<2, 5>        1.31 ns         1.31 ns    531099680
BM_Visit<2, 6>        1.56 ns         1.56 ns    443203475
BM_Visit<2, 7>        1.29 ns         1.29 ns    526478087
BM_Visit<2, 8>        1.56 ns         1.56 ns    439000834
BM_Visit<2, 9>        1.30 ns         1.30 ns    528756817
BM_Visit<2, 10>       1.56 ns         1.55 ns    442923039
BM_Visit<2, 20>       1.35 ns         1.35 ns    517021072
BM_Visit<2, 30>       1.60 ns         1.59 ns    419724661
BM_Visit<2, 40>       1.45 ns         1.44 ns    472137163
BM_Visit<2, 50>       1.65 ns         1.65 ns    421389743

$ ./projects/libcxx/benchmarks/variant_visit_3.libcxx.out
2020-08-10 00:01:32
Running ./projects/libcxx/benchmarks/variant_visit_3.libcxx.out
Run on (8 X 3100 MHz CPU s)
CPU Caches:
  L1 Data 32K (x4)
  L1 Instruction 32K (x4)
  L2 Unified 262K (x4)
  L3 Unified 8388K (x1)
Load Average: 2.20, 2.01, 2.21
-----------------------------------------------------------
Benchmark                Time             CPU   Iterations
-----------------------------------------------------------
BM_Visit<3, 1>       0.272 ns        0.271 ns   1000000000
BM_Visit<3, 2>        1.87 ns         1.86 ns    361858090
BM_Visit<3, 3>        1.77 ns         1.77 ns    391192579
BM_Visit<3, 4>        1.84 ns         1.84 ns    374694223
BM_Visit<3, 5>        1.75 ns         1.75 ns    408270392
BM_Visit<3, 6>        1.88 ns         1.88 ns    378759185
BM_Visit<3, 7>        1.79 ns         1.79 ns    395498102
BM_Visit<3, 8>        1.85 ns         1.85 ns    371660366
BM_Visit<3, 9>        1.80 ns         1.80 ns    386872851
BM_Visit<3, 10>       1.84 ns         1.84 ns    362367606
BM_Visit<3, 15>       1.77 ns         1.77 ns    392060220
BM_Visit<3, 20>       1.85 ns         1.85 ns    379157188

After: using the switch-based mechanism.

$ ./projects/libcxx/benchmarks/variant_visit_1.libcxx.out
2020-08-12 04:17:33
Running ./projects/libcxx/benchmarks/variant_visit_1.libcxx.out
Run on (8 X 3100 MHz CPU s)
CPU Caches:
  L1 Data 32K (x4)
  L1 Instruction 32K (x4)
  L2 Unified 262K (x4)
  L3 Unified 8388K (x1)
Load Average: 1.96, 2.26, 3.49
------------------------------------------------------------
Benchmark                 Time             CPU   Iterations
------------------------------------------------------------
BM_Visit<1, 1>        0.280 ns        0.279 ns   1000000000
BM_Visit<1, 2>        0.285 ns        0.282 ns   1000000000
BM_Visit<1, 3>        0.281 ns        0.279 ns   1000000000
BM_Visit<1, 4>        0.278 ns        0.277 ns   1000000000
BM_Visit<1, 5>        0.283 ns        0.282 ns   1000000000
BM_Visit<1, 6>        0.279 ns        0.278 ns   1000000000
BM_Visit<1, 7>        0.279 ns        0.278 ns   1000000000
BM_Visit<1, 8>        0.273 ns        0.272 ns   1000000000
BM_Visit<1, 9>        0.275 ns        0.274 ns   1000000000
BM_Visit<1, 10>       0.274 ns        0.273 ns   1000000000
BM_Visit<1, 20>       0.277 ns        0.276 ns   1000000000
BM_Visit<1, 30>       0.278 ns        0.277 ns   1000000000
BM_Visit<1, 40>       0.269 ns        0.268 ns   1000000000
BM_Visit<1, 50>       0.271 ns        0.271 ns   1000000000
BM_Visit<1, 60>       0.272 ns        0.270 ns   1000000000
BM_Visit<1, 70>       0.275 ns        0.274 ns   1000000000
BM_Visit<1, 80>       0.278 ns        0.276 ns   1000000000
BM_Visit<1, 90>       0.272 ns        0.271 ns   1000000000
BM_Visit<1, 100>      0.269 ns        0.268 ns   1000000000

$ ./projects/libcxx/benchmarks/variant_visit_2.libcxx.out
2020-08-12 04:09:59
Running ./projects/libcxx/benchmarks/variant_visit_2.libcxx.out
Run on (8 X 3100 MHz CPU s)
CPU Caches:
  L1 Data 32K (x4)
  L1 Instruction 32K (x4)
  L2 Unified 262K (x4)
  L3 Unified 8388K (x1)
Load Average: 2.17, 4.20, 4.78
-----------------------------------------------------------
Benchmark                Time             CPU   Iterations
-----------------------------------------------------------
BM_Visit<2, 1>       0.302 ns        0.301 ns   1000000000
BM_Visit<2, 2>       0.297 ns        0.295 ns   1000000000
BM_Visit<2, 3>       0.353 ns        0.351 ns   1000000000
BM_Visit<2, 4>       0.276 ns        0.276 ns   1000000000
BM_Visit<2, 5>       0.285 ns        0.283 ns   1000000000
BM_Visit<2, 6>       0.290 ns        0.287 ns   1000000000
BM_Visit<2, 7>       0.282 ns        0.280 ns   1000000000
BM_Visit<2, 8>       0.290 ns        0.287 ns   1000000000
BM_Visit<2, 9>       0.291 ns        0.285 ns   1000000000
BM_Visit<2, 10>      0.293 ns        0.287 ns   1000000000
BM_Visit<2, 20>       1.70 ns         1.68 ns    391400375
BM_Visit<2, 30>       1.64 ns         1.63 ns    418925874
BM_Visit<2, 40>       1.63 ns         1.62 ns    423623677
BM_Visit<2, 50>       1.68 ns         1.67 ns    411687212

$ ./projects/libcxx/benchmarks/variant_visit_3.libcxx.out
2020-08-12 04:10:43
Running ./projects/libcxx/benchmarks/variant_visit_3.libcxx.out
Run on (8 X 3100 MHz CPU s)
CPU Caches:
  L1 Data 32K (x4)
  L1 Instruction 32K (x4)
  L2 Unified 262K (x4)
  L3 Unified 8388K (x1)
Load Average: 1.57, 3.76, 4.59
-----------------------------------------------------------
Benchmark                Time             CPU   Iterations
-----------------------------------------------------------
BM_Visit<3, 1>       0.271 ns        0.270 ns   1000000000
BM_Visit<3, 2>       0.344 ns        0.334 ns   1000000000
BM_Visit<3, 3>       0.347 ns        0.336 ns   1000000000
BM_Visit<3, 4>       0.300 ns        0.296 ns   1000000000
BM_Visit<3, 5>       0.290 ns        0.286 ns   1000000000
BM_Visit<3, 6>       0.272 ns        0.271 ns   1000000000
BM_Visit<3, 7>        1.72 ns         1.71 ns    415765841
BM_Visit<3, 8>        1.73 ns         1.72 ns    408909555
BM_Visit<3, 9>        2.16 ns         2.04 ns    380898485
BM_Visit<3, 10>       2.45 ns         2.40 ns    295714256
BM_Visit<3, 15>       1.92 ns         1.85 ns    375990332
BM_Visit<3, 20>       1.66 ns         1.65 ns    414456233

[xbolva00]

libcxx/include/variant

501

_LIBCPP_VARIANT_DISPATCH(__index);

?

[mpark]

libcxx/include/variant

501

No, we need it to be a compile-time value.

[mpark]

Used a different switch-based approach.

[mpark]

Minor cleanup update.

[mpark]

Use _LIBCPP_CONCAT.

[ldionne]

Geez, that's some nice speedup for smaller variants! Do you have an explanation for why the code is so much better?

libcxx/include/variant

541

I don't think the ability to disable the switch implementation is useful -- it'll just lead to an unused customization point. Or do you have a use case for it? That could provide interesting information about this patch.

libcxx/test/libcxx/utilities/variant/variant.visit/visit_without_switch.pass.cpp

2

Is there any difference between this file and libcxx/test/std/utilities/variant/variant.visit/visit.pass.cpp beyond the #define _LIBCPP_DISABLE_SWITCH_VISIT_IN_VARIANT bit? If not, we should structure the tests to avoid such duplication IMO.

[mpark]

The improvements are from enabling compilers to inline the invocation by using a switch.
Compilers currently can't seem to inline through function pointers even if it's constexpr.

libcxx/include/variant

541

The only real use case is fully testing the manual vtable approach. Perhaps we can do that through a different mechanism?

libcxx/test/libcxx/utilities/variant/variant.visit/visit_without_switch.pass.cpp

2

No, there's no difference. I was wondering if there's something I could do with ADDITONAL_COMPILE_FLAGS or something but I couldn't find anything. Do you have a suggestion?

[ldionne]

In D85420#2211176, @mpark wrote:

The improvements are from enabling compilers to inline the invocation by using a switch.
Compilers currently can't seem to inline through function pointers even if it's constexpr.

Interesting.

libcxx/include/variant

541

I think if we test the overall std::visit with all sizes of variants, then we'll be exercising both the switch and the manual vtable implementations to the extent they are used. I believe that should be sufficient, and it would also remove the duplication in the tests IIUC. What do you think about that?

[mpark]

libcxx/include/variant

541

Yep, fine with me.

[mpark]

Addressed ldionne's comments.

[ldionne]

libcxx/test/std/utilities/variant/variant.visit/visit.pass.cpp

347 ↗

(On Diff #285033)

Do we have tests with sufficiently large variants?

[mpark]

libcxx/test/std/utilities/variant/variant.visit/visit.pass.cpp

347 ↗

(On Diff #285033)

Yeah, I adjusted the # of switch cases from 1024 to 256 (see the adjusted numbers). This test needs 5^4 = 625 cases, so it uses the vtable approach.

[mpark]

Add inline _LIBCPP_INLINE_VISIBILITY to several functions.

[mpark]

s/std::integral_constant/integral_constant/

[mehdi_amini]

I think this change is breaking one of our uses right now:

include/c++/v1/variant:599:16: error: call to deleted constructor of 'std::__u::basic_ostream<char>'
        return __invoke_constexpr(
               ^~~~~~~~~~~~~~~~~~~
include/c++/v1/variant:618:59: note: in instantiation of function template specialization 'std::__u::__variant_detail::__visitation::__base::__visit_alt_impl(index_sequence<0UL>, std::__u::__variant_detail::__visitation::__variant::__value_visitor<YYY &> &&, const std::__u::__variant_detail::__impl<XXX, ZZZ> &)::(anonymous class)::operator()<std::__u::integral_constant<unsigned long, 1>>' requested here
        _LIBCPP_VARIANT_CASES(_LIBCPP_VARIANT_SWITCH_MAX, _LIBCPP_VARIANT_CASE)
                                                          ^
include/c++/v1/variant:586:14: note: in instantiation of function template specialization 'std::__u::__variant_detail::__visitation::__base::__visit_alt_impl<0, std::__u::__variant_detail::__visitation::__variant::__value_visitor<YYY &>, const std::__u::__variant_detail::__impl<XXX, ZZZ> &>' requested here
      return __visit_alt_impl(index_sequence_for<_Vs...>{},
             ^
include/c++/v1/variant:645:20: note: in instantiation of function template specialization 'std::__u::__variant_detail::__visitation::__base::__visit_alt<, std::__u::__variant_detail::__visitation::__variant::__value_visitor<YYY &>, const std::__u::__variant_detail::__impl<XXX, ZZZ> &>' requested here
    return __base::__visit_alt(_VSTD::forward<_Vis>(__vis),
                   ^
include/c++/v1/variant:662:12: note: in instantiation of function template specialization 'std::__u::__variant_detail::__visitation::__variant::__visit_alt<std::__u::__variant_detail::__visitation::__variant::__value_visitor<YYY &>, const std::__u::variant<XXX, ZZZ> &>' requested here
    return __visit_alt(__make_value_visitor(_VSTD::forward<_Vis>(__vis)),
           ^
include/c++/v1/variant:1685:21: note: in instantiation of function template specialization 'std::__u::__variant_detail::__visitation::__variant::__visit_value<YYY &, const std::__u::variant<XXX, ZZZ> &>' requested here
  return __variant::__visit_value(_VSTD::forward<_Vis>(__vis),
                    ^

I don't know if this trace is enough to figure is there is an issue upstream?

[mpark]

Hi Mehdi,

I've submitted https://reviews.llvm.org/D86006 and I believe that will be
the correct fix for this issue.
It was likely incorrectly returning the stream by value as a return type
coming out of visit.

[dblaikie]

libcxx/include/variant

890

This surprises me a bit - doesn't result need to be mangled (as __result, for instance) as in other places, like __make_vtable_impl?

[ldionne]

libcxx/include/variant

890

This was fixed in https://reviews.llvm.org/D86827.

libcxx/include/variant

 } // namespace __find_detail
 
 namespace __variant_detail {
 
 struct __valueless_t {};
 
 enum class _Trait { _TriviallyAvailable, _Available, _Unavailable };
 
-template <typename _Tp,
-          template <typename> class _IsTriviallyAvailable,
-          template <typename> class _IsAvailable>
+template <class _Tp,
+          template <class> class _IsTriviallyAvailable,
+          template <class> class _IsAvailable>
 constexpr _Trait __trait =
     _IsTriviallyAvailable<_Tp>::value
         ? _Trait::_TriviallyAvailable
         : _IsAvailable<_Tp>::value ? _Trait::_Available : _Trait::_Unavailable;
 
 inline _LIBCPP_INLINE_VISIBILITY
 constexpr _Trait __common_trait(initializer_list<_Trait> __traits) {
   _Trait __result = _Trait::_TriviallyAvailable;
   for (_Trait __t : __traits) {
     if (static_cast<int>(__t) > static_cast<int>(__result)) {
       __result = __t;
     }
   }
   return __result;
 }
 
-template <typename... _Types>
+template <class... _Types>
 struct __traits {
   static constexpr _Trait __copy_constructible_trait =
       __common_trait({__trait<_Types,
                               is_trivially_copy_constructible,
                               is_copy_constructible>...});
 
   static constexpr _Trait __move_constructible_trait =
       __common_trait({__trait<_Types,
static constexpr auto&& __get_alt(_Vp&& __v) {
     return __base::__get_alt<_Ip>(_VSTD::forward<_Vp>(__v).__impl);
   }
 };
 
 } // namespace __access
 
 namespace __visitation {
 
-struct __base {
-  template <class _Visitor, class... _Vs>
-  inline _LIBCPP_INLINE_VISIBILITY
-  static constexpr decltype(auto)
-  __visit_alt_at(size_t __index, _Visitor&& __visitor, _Vs&&... __vs) {
-    constexpr auto __fdiagonal =
-        __make_fdiagonal<_Visitor&&,
-                         decltype(_VSTD::forward<_Vs>(__vs).__as_base())...>();
-    return __fdiagonal[__index](_VSTD::forward<_Visitor>(__visitor),
-                                _VSTD::forward<_Vs>(__vs).__as_base()...);
-  }
-
-  template <class _Visitor, class... _Vs>
-  inline _LIBCPP_INLINE_VISIBILITY
-  static constexpr decltype(auto) __visit_alt(_Visitor&& __visitor,
-                                              _Vs&&... __vs) {
-    constexpr auto __fmatrix =
-        __make_fmatrix<_Visitor&&,
-                       decltype(_VSTD::forward<_Vs>(__vs).__as_base())...>();
-    return __at(__fmatrix, __vs.index()...)(
-        _VSTD::forward<_Visitor>(__visitor),
-        _VSTD::forward<_Vs>(__vs).__as_base()...);
+#define _LIBCPP_VARIANT_CASES_4(_Case, _Base)                                  \
+  _Case(_Base + 0)                                                             \
+  _Case(_Base + 1)                                                             \
+  _Case(_Base + 2)                                                             \
+  _Case(_Base + 3)
+
+#define _LIBCPP_VARIANT_CASES_16(_Case, _Base)                                 \
+  _LIBCPP_VARIANT_CASES_4(_Case, _Base + 4 * 0)                                \
+  _LIBCPP_VARIANT_CASES_4(_Case, _Base + 4 * 1)                                \
+  _LIBCPP_VARIANT_CASES_4(_Case, _Base + 4 * 2)                                \
+  _LIBCPP_VARIANT_CASES_4(_Case, _Base + 4 * 3)
+
+#define _LIBCPP_VARIANT_CASES_64(_Case, _Base)                                 \
+  _LIBCPP_VARIANT_CASES_16(_Case, _Base + 16 * 0)                              \
+  _LIBCPP_VARIANT_CASES_16(_Case, _Base + 16 * 1)                              \
+  _LIBCPP_VARIANT_CASES_16(_Case, _Base + 16 * 2)                              \
+  _LIBCPP_VARIANT_CASES_16(_Case, _Base + 16 * 3)
+
+#define _LIBCPP_VARIANT_CASES_256(_Case, _Base)                                \
+  _LIBCPP_VARIANT_CASES_64(_Case, _Base + 64 * 0)                              \
+  _LIBCPP_VARIANT_CASES_64(_Case, _Base + 64 * 1)                              \
+  _LIBCPP_VARIANT_CASES_64(_Case, _Base + 64 * 2)                              \
+  _LIBCPP_VARIANT_CASES_64(_Case, _Base + 64 * 3)
+
+#define _LIBCPP_VARIANT_CASES_1024(_Case, _Base)                               \
+  _LIBCPP_VARIANT_CASES_256(_Case, _Base + 256 * 0)                            \
+  _LIBCPP_VARIANT_CASES_256(_Case, _Base + 256 * 1)                            \
+  _LIBCPP_VARIANT_CASES_256(_Case, _Base + 256 * 2)                            \
+  _LIBCPP_VARIANT_CASES_256(_Case, _Base + 256 * 3)
+
+#define _LIBCPP_VARIANT_CASES(_NumCases, _Case)                                \
+  _LIBCPP_CONCAT(_LIBCPP_VARIANT_CASES_, _NumCases)(_Case, 0)
+
+#define _LIBCPP_VARIANT_SWITCH_VISIT_MAX 1024
+
+template <class _Iter, class _Fp, size_t... _Is>
+static constexpr void __fill_cartesian_impl(
+    _Iter __iter, _Fp __f, index_sequence<_Is...>) {
+  *__iter = __f(integral_constant<size_t, _Is>{}...);
+}
+
+template <class _Iter, class _Fp, size_t... _Is, size_t... _Js, class... _Ls>
+static constexpr void __fill_cartesian_impl(
+    _Iter __iter, _Fp __f, index_sequence<_Is...>, index_sequence<_Js...>, _Ls... __ls) {
+  constexpr size_t _Mp = (1 * ... * _Ls::size());
+  (__fill_cartesian_impl(
+      __iter + _Js * _Mp, __f, index_sequence<_Is..., _Js>{}, __ls...), ...);
+}
+
+template <size_t... _Ns, class _Iter, class _Fp>
+static constexpr void __fill_cartesian(_Iter __iter, _Fp __f) {
+  __fill_cartesian_impl(
+      __iter, __f, index_sequence<>{}, make_index_sequence<_Ns>{}...);
+}
+
+template <size_t _Np, size_t... _Ns>
+struct __multi {
+  static constexpr size_t __size = (_Np * ... * _Ns);
+
+  static constexpr size_t
+  __index(const size_t (&__is)[sizeof...(_Ns) + 1]) noexcept {
+    constexpr size_t __ns[] = {_Ns..., 1};
+    size_t __result = 0;
+    for (size_t __i = 0; __i < sizeof...(_Ns) + 1; ++__i) {
+      if (__is[__i] == variant_npos) {
+        return variant_npos;
+      }
+      __result += __is[__i];
+      __result *= __ns[__i];
+    }
+    return __result;
   }
+};
 
-private:
-  template <class _Tp>
-  inline _LIBCPP_INLINE_VISIBILITY
-  static constexpr const _Tp& __at(const _Tp& __elem) { return __elem; }
+template <size_t... _Ns>
+struct __indices {
+  static constexpr auto __value = [] {
+    using _Tp = array<size_t, sizeof...(_Ns)>;
+    array<_Tp, (1 * ... * _Ns)> __result = {};
+    __fill_cartesian<_Ns...>(__result.begin(),
+                             [](auto... __is) -> _Tp { return {__is...}; });
+    return __result;
+  }();
+};
 
-  template <class _Tp, size_t _Np, typename... _Indices>
-  inline _LIBCPP_INLINE_VISIBILITY
-  static constexpr auto&& __at(const array<_Tp, _Np>& __elems,
-                               size_t __index, _Indices... __indices) {
-    return __at(__elems[__index], __indices...);
-  }
+template <size_t... _Ns, class _Fp, class _Rp, class... _Args>
+static constexpr auto __make_vtable_impl(_Fp __f, _Rp (*)(_Args...)) {
+  array<_Rp (*)(_Args...), (1 * ... * _Ns) + 1> __result = {
+      [](_Args...) -> _Rp { __throw_bad_variant_access(); }
+  };
+  __fill_cartesian<_Ns...>(__result.begin() + 1, __f);
+  return __result;
 
-  template <class _Fp, class... _Fs>
-  static constexpr void __std_visit_visitor_return_type_check() {
-    static_assert(
-        __all<is_same_v<_Fp, _Fs>...>::value,
-        "`std::visit` requires the visitor to have a single return type.");
-  }
+template <size_t... _Ns, class _Fp>
+static constexpr auto __make_vtable(_Fp __f) {
+  using _Tp = decltype(__f(std::integral_constant<size_t, (_Ns, 0)>{}...));
+  return __make_vtable_impl<_Ns...>(__f, _Tp{});
 
-  template <class... _Fs>
-  inline _LIBCPP_INLINE_VISIBILITY
-  static constexpr auto __make_farray(_Fs&&... __fs) {
-    __std_visit_visitor_return_type_check<__uncvref_t<_Fs>...>();
-    using __result = array<common_type_t<__uncvref_t<_Fs>...>, sizeof...(_Fs)>;
-    return __result{{_VSTD::forward<_Fs>(__fs)...}};
+struct __base {
+  template <size_t size>
+  static constexpr bool __switch_visit() {
+    return
+#ifdef _LIBCPP_DISABLE_SWITCH_VISIT_IN_VARIANT
+        false;
+#else
+        size <= _LIBCPP_VARIANT_SWITCH_VISIT_MAX;
+#endif
   }
 
-  template <std::size_t... _Is>
-  struct __dispatcher {
-    template <class _Fp, class... _Vs>
-    inline _LIBCPP_INLINE_VISIBILITY
-    static constexpr decltype(auto) __dispatch(_Fp __f, _Vs... __vs) {
+  template <class _Vis, class _Vp, class _Wp>
+  static constexpr decltype(auto)
+  __visit_alt_at(size_t __index, _Vis&& __vis, _Vp&& __v, _Wp&& __w) {
+    constexpr size_t __size = __uncvref_t<_Vp>::__size();
+    static_assert(__size == __uncvref_t<_Wp>::__size());
+    constexpr auto __dispatch = [](auto __i) {
+      return +[](_Vis&& __vis, _Vp&& __v, _Wp&& __w) -> decltype(auto) {
+        constexpr size_t _Ip = decltype(__i)::value;
         return __invoke_constexpr(
-            static_cast<_Fp>(__f),
-            __access::__base::__get_alt<_Is>(static_cast<_Vs>(__vs))...);
+            _VSTD::forward<_Vis>(__vis),
+            __access::__base::__get_alt<_Ip>(_VSTD::forward<_Vp>(__v)),
+            __access::__base::__get_alt<_Ip>(_VSTD::forward<_Wp>(__w)));
+      };
+    };
+    if constexpr (__switch_visit<__size>()) {
+#define _LIBCPP_VARIANT_CASE(_Ip)                                              \
+  case _Ip: {                                                                  \
+    if constexpr (_Ip < __size) {                                              \
+      return __dispatch(integral_constant<size_t, _Ip>{})(                     \
+          _VSTD::forward<_Vis>(__vis),                                         \
+          _VSTD::forward<_Vp>(__v),                                            \
+          _VSTD::forward<_Wp>(__w));                                           \
+    } else {                                                                   \
+      _LIBCPP_UNREACHABLE();                                                   \
+    }                                                                          \
+  }
+      switch (__index) {
+        _LIBCPP_VARIANT_CASES(_LIBCPP_VARIANT_SWITCH_VISIT_MAX,
+                              _LIBCPP_VARIANT_CASE)
+        default: __throw_bad_variant_access();
       }
-  };
-
-  template <class _Fp, class... _Vs, size_t... _Is>
-  inline _LIBCPP_INLINE_VISIBILITY
-  static constexpr auto __make_dispatch(index_sequence<_Is...>) {
-    return __dispatcher<_Is...>::template __dispatch<_Fp, _Vs...>;
+#undef _LIBCPP_VARIANT_CASE
+    } else {
+      constexpr auto __vtable = __make_vtable<__size>(__dispatch);
+      return __vtable[__index + 1](_VSTD::forward<_Vis>(__vis),
+                                   _VSTD::forward<_Vp>(__v),
+                                   _VSTD::forward<_Wp>(__w));
     }
-
-  template <size_t _Ip, class _Fp, class... _Vs>
-  inline _LIBCPP_INLINE_VISIBILITY
-  static constexpr auto __make_fdiagonal_impl() {
-    return __make_dispatch<_Fp, _Vs...>(
-        index_sequence<(__identity<_Vs>{}, _Ip)...>{});
   }
 
-  template <class _Fp, class... _Vs, size_t... _Is>
+  template <size_t... _Is, class _Vis, class... _Vs>
   inline _LIBCPP_INLINE_VISIBILITY
-  static constexpr auto __make_fdiagonal_impl(index_sequence<_Is...>) {
-    return __base::__make_farray(__make_fdiagonal_impl<_Is, _Fp, _Vs...>()...);
+  static constexpr decltype(auto) __visit_alt(_Vis&& __vis, _Vs&&... __vs) {
+    if constexpr (sizeof...(_Vs) == 0) {
+      return __invoke_constexpr(_VSTD::forward<_Vis>(__vis));
+    } else {
+      return __visit_alt_impl(index_sequence_for<_Vs...>{},
+                              _VSTD::forward<_Vis>(__vis),
+                              _VSTD::forward<_Vs>(__vs)...);
     }
-
-  template <class _Fp, class _Vp, class... _Vs>
-  inline _LIBCPP_INLINE_VISIBILITY
-  static constexpr auto __make_fdiagonal() {
-    constexpr size_t _Np = __uncvref_t<_Vp>::__size();
-    static_assert(__all<(_Np == __uncvref_t<_Vs>::__size())...>::value);
-    return __make_fdiagonal_impl<_Fp, _Vp, _Vs...>(make_index_sequence<_Np>{});
   }
 
-  template <class _Fp, class... _Vs, size_t... _Is>
+  template <size_t... _Is, class _Vis, class... _Vs>
   inline _LIBCPP_INLINE_VISIBILITY
-  static constexpr auto __make_fmatrix_impl(index_sequence<_Is...> __is) {
-    return __make_dispatch<_Fp, _Vs...>(__is);
+  static constexpr decltype(auto)
+  __visit_alt_impl(index_sequence<_Is...>, _Vis&& __vis, _Vs&&... __vs) {
+    using __multi = __multi<__uncvref_t<_Vs>::__size()...>;
+    constexpr auto __dispatch = [](auto... __is) {
+      return +[](_Vis&& __vis, _Vs&&... __vs) {
+        return __invoke_constexpr(
+            _VSTD::forward<_Vis>(__vis),
+            __access::__base::__get_alt<decltype(__is)::value>(
+                _VSTD::forward<_Vs>(__vs))...);
+      };
+    };
+    if constexpr (__switch_visit<__multi::__size>()) {
+      constexpr const auto& __itable =
+          __indices<__uncvref_t<_Vs>::__size()...>::__value;
+#define _LIBCPP_VARIANT_CASE(_Ip)                                              \
+  case _Ip: {                                                                  \
+    if constexpr (_Ip < __multi::__size) {                                     \
+      return __dispatch(integral_constant<size_t, __itable[_Ip][_Is]>{}...)(   \
+          _VSTD::forward<_Vis>(__vis), _VSTD::forward<_Vs>(__vs)...);          \
+    } else {                                                                   \
+      _LIBCPP_UNREACHABLE();                                                   \
+    }                                                                          \
+  }
+      switch (__multi::__index({__vs.index()...})) {
+        _LIBCPP_VARIANT_CASES(_LIBCPP_VARIANT_SWITCH_VISIT_MAX,
+                              _LIBCPP_VARIANT_CASE)
+        default: __throw_bad_variant_access();
       }
-
-  template <class _Fp, class... _Vs, size_t... _Is, size_t... _Js, class... _Ls>
-  inline _LIBCPP_INLINE_VISIBILITY
-  static constexpr auto __make_fmatrix_impl(index_sequence<_Is...>,
-                                            index_sequence<_Js...>,
-                                            _Ls... __ls) {
-    return __base::__make_farray(__make_fmatrix_impl<_Fp, _Vs...>(
-        index_sequence<_Is..., _Js>{}, __ls...)...);
+#undef _LIBCPP_VARIANT_CASE
+    } else {
+      constexpr auto __vtable =
+          __make_vtable<__uncvref_t<_Vs>::__size()...>(__dispatch);
+      return __vtable[__multi::__index({__vs.index()...}) + 1](
+          _VSTD::forward<_Vis>(__vis), _VSTD::forward<_Vs>(__vs)...);
     }
-
-  template <class _Fp, class... _Vs>
-  inline _LIBCPP_INLINE_VISIBILITY
-  static constexpr auto __make_fmatrix() {
-    return __make_fmatrix_impl<_Fp, _Vs...>(
-        index_sequence<>{}, make_index_sequence<__uncvref_t<_Vs>::__size()>{}...);
   }
 };
 
 struct __variant {
-  template <class _Visitor, class... _Vs>
+  template <class _Vis, class _Vp, class _Wp>
   inline _LIBCPP_INLINE_VISIBILITY
   static constexpr decltype(auto)
-  __visit_alt_at(size_t __index, _Visitor&& __visitor, _Vs&&... __vs) {
+  __visit_alt_at(size_t __index, _Vis&& __vis, _Vp&& __v, _Wp&& __w) {
     return __base::__visit_alt_at(__index,
-                                  _VSTD::forward<_Visitor>(__visitor),
-                                  _VSTD::forward<_Vs>(__vs).__impl...);
+                                  _VSTD::forward<_Vis>(__vis),
+                                  _VSTD::forward<_Vp>(__v).__impl,
+                                  _VSTD::forward<_Wp>(__w).__impl);
   }
 
-  template <class _Visitor, class... _Vs>
+  template <class _Vis, class... _Vs>
   inline _LIBCPP_INLINE_VISIBILITY
-  static constexpr decltype(auto) __visit_alt(_Visitor&& __visitor,
-                                              _Vs&&... __vs) {
-    return __base::__visit_alt(_VSTD::forward<_Visitor>(__visitor),
+  static constexpr decltype(auto) __visit_alt(_Vis&& __vis, _Vs&&... __vs) {
+    return __base::__visit_alt(_VSTD::forward<_Vis>(__vis),
                                _VSTD::forward<_Vs>(__vs).__impl...);
   }
 
-  template <class _Visitor, class... _Vs>
+  template <class _Vis, class _Vp, class _Wp>
   inline _LIBCPP_INLINE_VISIBILITY
   static constexpr decltype(auto)
-  __visit_value_at(size_t __index, _Visitor&& __visitor, _Vs&&... __vs) {
-    return __visit_alt_at(
-        __index,
-        __make_value_visitor(_VSTD::forward<_Visitor>(__visitor)),
-        _VSTD::forward<_Vs>(__vs)...);
+  __visit_value_at(size_t __index, _Vis&& __vis, _Vp&& __v, _Wp&& __w) {
+    return __visit_alt_at(__index,
+                          __make_value_visitor(_VSTD::forward<_Vis>(__vis)),
+                          _VSTD::forward<_Vp>(__v),
+                          _VSTD::forward<_Wp>(__w));
   }
 
-  template <class _Visitor, class... _Vs>
+  template <class _Vis, class... _Vs>
   inline _LIBCPP_INLINE_VISIBILITY
-  static constexpr decltype(auto) __visit_value(_Visitor&& __visitor,
-                                                _Vs&&... __vs) {
-    return __visit_alt(
-        __make_value_visitor(_VSTD::forward<_Visitor>(__visitor)),
+  static constexpr decltype(auto) __visit_value(_Vis&& __vis, _Vs&&... __vs) {
+    return __visit_alt(__make_value_visitor(_VSTD::forward<_Vis>(__vis)),
                        _VSTD::forward<_Vs>(__vs)...);
   }
 
 private:
-  template <class _Visitor, class... _Values>
+  template <class _Vis, class... _Values>
+  inline _LIBCPP_INLINE_VISIBILITY
   static constexpr void __std_visit_exhaustive_visitor_check() {
-    static_assert(is_invocable_v<_Visitor, _Values...>,
+    static_assert(is_invocable_v<_Vis, _Values...>,
                   "`std::visit` requires the visitor to be exhaustive.");
   }
 
-  template <class _Visitor>
+  template <class _Vis>
   struct __value_visitor {
     template <class... _Alts>
     inline _LIBCPP_INLINE_VISIBILITY
     constexpr decltype(auto) operator()(_Alts&&... __alts) const {
       __std_visit_exhaustive_visitor_check<
-          _Visitor,
-          decltype((_VSTD::forward<_Alts>(__alts).__value))...>();
-      return __invoke_constexpr(_VSTD::forward<_Visitor>(__visitor),
+          _Vis, decltype((_VSTD::forward<_Alts>(__alts).__value))...>();
+      return __invoke_constexpr(_VSTD::forward<_Vis>(__vis),
                                 _VSTD::forward<_Alts>(__alts).__value...);
     }
-    _Visitor&& __visitor;
+    _Vis&& __vis;
   };
 
-  template <class _Visitor>
+  template <class _Vis>
   inline _LIBCPP_INLINE_VISIBILITY
-  static constexpr auto __make_value_visitor(_Visitor&& __visitor) {
-    return __value_visitor<_Visitor>{_VSTD::forward<_Visitor>(__visitor)};
+  static constexpr auto __make_value_visitor(_Vis&& __vis) {
+    return __value_visitor<_Vis>{_VSTD::forward<_Vis>(__vis)};
   }
 };
 
+#undef _LIBCPP_VARIANT_SWITCH_VISIT_MAX
+#undef _LIBCPP_VARIANT_CASES
+#undef _LIBCPP_VARIANT_CASES_IMPL
+#undef _LIBCPP_VARIANT_CASES_1024
+#undef _LIBCPP_VARIANT_CASES_256
+#undef _LIBCPP_VARIANT_CASES_64
+#undef _LIBCPP_VARIANT_CASES_16
+#undef _LIBCPP_VARIANT_CASES_4
+#undef _LIBCPP_VARIANT_CASES_0
+
 } // namespace __visitation
 
 template <size_t _Index, class _Tp>
 struct _LIBCPP_TEMPLATE_VIS __alt {
   using __value_type = _Tp;
 
   template <class... _Args>
   inline _LIBCPP_INLINE_VISIBILITY
   explicit constexpr __alt(in_place_t, _Args&&... __args)
       : __value(_VSTD::forward<_Args>(__args)...) {}
 
   __value_type __value;
 };
 
 template <_Trait _DestructibleTrait, size_t _Index, class... _Types>
 union _LIBCPP_TEMPLATE_VIS __union;
 
 template <_Trait _DestructibleTrait, size_t _Index>
 union _LIBCPP_TEMPLATE_VIS __union<_DestructibleTrait, _Index> {};
 
 #define _LIBCPP_VARIANT_UNION(destructible_trait, destructor)                  \
   template <size_t _Index, class _Tp, class... _Types>                         \
-  union _LIBCPP_TEMPLATE_VIS __union<destructible_trait,                      \
+  union _LIBCPP_TEMPLATE_VIS __union<destructible_trait,                       \
                                       _Index,                                  \
                                       _Tp,                                     \
                                       _Types...> {                             \
   public:                                                                      \
     inline _LIBCPP_INLINE_VISIBILITY                                           \
     explicit constexpr __union(__valueless_t) noexcept : __dummy{} {}          \
                                                                                \
     template <class... _Args>                                                  \

 public:
   using __base_type::__base_type;
   using __base_type::operator=;
 
 protected:
   template <size_t _Ip, class _Tp, class... _Args>
   inline _LIBCPP_INLINE_VISIBILITY
   static _Tp& __construct_alt(__alt<_Ip, _Tp>& __a, _Args&&... __args) {
-    ::new ((void*)_VSTD::addressof(__a))
+    auto* result = ::new ((void*)_VSTD::addressof(__a))
         __alt<_Ip, _Tp>(in_place, _VSTD::forward<_Args>(__args)...);
-    return __a.__value;
+    return result->__value;
   }
 
   template <class _Rhs>
   inline _LIBCPP_INLINE_VISIBILITY
   static void __generic_construct(__constructor& __lhs, _Rhs&& __rhs) {
     __lhs.__destroy();
     if (!__rhs.valueless_by_exception()) {
       __visitation::__base::__visit_alt_at(

 };
 
 template <class _Traits, _Trait = _Traits::__move_constructible_trait>
 class _LIBCPP_TEMPLATE_VIS __move_constructor;
 
 #define _LIBCPP_VARIANT_MOVE_CONSTRUCTOR(move_constructible_trait,             \
                                          move_constructor)                     \
   template <class... _Types>                                                   \
-  class _LIBCPP_TEMPLATE_VIS __move_constructor<__traits<_Types...>,          \
+  class _LIBCPP_TEMPLATE_VIS __move_constructor<__traits<_Types...>,           \
                                                  move_constructible_trait>     \
       : public __constructor<__traits<_Types...>> {                            \
     using __base_type = __constructor<__traits<_Types...>>;                    \
                                                                                \
   public:                                                                      \
     using __base_type::__base_type;                                            \
     using __base_type::operator=;                                              \
                                                                                \

 #undef _LIBCPP_VARIANT_MOVE_CONSTRUCTOR
 
 template <class _Traits, _Trait = _Traits::__copy_constructible_trait>
 class _LIBCPP_TEMPLATE_VIS __copy_constructor;
 
 #define _LIBCPP_VARIANT_COPY_CONSTRUCTOR(copy_constructible_trait,             \
                                          copy_constructor)                     \
   template <class... _Types>                                                   \
-  class _LIBCPP_TEMPLATE_VIS __copy_constructor<__traits<_Types...>,          \
+  class _LIBCPP_TEMPLATE_VIS __copy_constructor<__traits<_Types...>,           \
                                                  copy_constructible_trait>     \
       : public __move_constructor<__traits<_Types...>> {                       \
     using __base_type = __move_constructor<__traits<_Types...>>;               \
                                                                                \
   public:                                                                      \
     using __base_type::__base_type;                                            \
     using __base_type::operator=;                                              \
                                                                                \
public:
   using __base_type::__base_type;
   using __base_type::operator=;
 
   template <size_t _Ip, class... _Args>
   inline _LIBCPP_INLINE_VISIBILITY
   auto& __emplace(_Args&&... __args) {
     this->__destroy();
     auto& __res = this->__construct_alt(__access::__base::__get_alt<_Ip>(*this),
                                         _VSTD::forward<_Args>(__args)...);
     this->__index = _Ip;
     return __res;
   }
 
 protected:
   template <size_t _Ip, class _Tp, class _Arg>
   inline _LIBCPP_INLINE_VISIBILITY
   void __assign_alt(__alt<_Ip, _Tp>& __a, _Arg&& __arg) {

 };
 
 template <class _Traits, _Trait = _Traits::__move_assignable_trait>
 class _LIBCPP_TEMPLATE_VIS __move_assignment;
 
 #define _LIBCPP_VARIANT_MOVE_ASSIGNMENT(move_assignable_trait,                 \
                                         move_assignment)                       \
   template <class... _Types>                                                   \
-  class _LIBCPP_TEMPLATE_VIS __move_assignment<__traits<_Types...>,           \
+  class _LIBCPP_TEMPLATE_VIS __move_assignment<__traits<_Types...>,            \
                                                 move_assignable_trait>         \
       : public __assignment<__traits<_Types...>> {                             \
     using __base_type = __assignment<__traits<_Types...>>;                     \
                                                                                \
   public:                                                                      \
     using __base_type::__base_type;                                            \
     using __base_type::operator=;                                              \
                                                                                \

 #undef _LIBCPP_VARIANT_MOVE_ASSIGNMENT
 
 template <class _Traits, _Trait = _Traits::__copy_assignable_trait>
 class _LIBCPP_TEMPLATE_VIS __copy_assignment;
 
 #define _LIBCPP_VARIANT_COPY_ASSIGNMENT(copy_assignable_trait,                 \
                                         copy_assignment)                       \
   template <class... _Types>                                                   \
-  class _LIBCPP_TEMPLATE_VIS __copy_assignment<__traits<_Types...>,           \
+  class _LIBCPP_TEMPLATE_VIS __copy_assignment<__traits<_Types...>,            \
                                                 copy_assignable_trait>         \
       : public __move_assignment<__traits<_Types...>> {                        \
     using __base_type = __move_assignment<__traits<_Types...>>;                \
                                                                                \
   public:                                                                      \
     using __base_type::__base_type;                                            \
     using __base_type::operator=;                                              \
                                                                                \
constexpr bool operator>=(const variant<_Types...>& __lhs,
   if (__rhs.valueless_by_exception()) return true;
   if (__lhs.valueless_by_exception()) return false;
   if (__lhs.index() > __rhs.index()) return true;
   if (__lhs.index() < __rhs.index()) return false;
   return __variant::__visit_value_at(
       __lhs.index(), __convert_to_bool<greater_equal<>>{}, __lhs, __rhs);
 }
 
-template <class _Visitor, class... _Vs>
+template <class _Vis, class... _Vs>
 inline _LIBCPP_INLINE_VISIBILITY
 _LIBCPP_AVAILABILITY_THROW_BAD_VARIANT_ACCESS
-constexpr decltype(auto) visit(_Visitor&& __visitor, _Vs&&... __vs) {
+constexpr decltype(auto) visit(_Vis&& __vis, _Vs&&... __vs) {
   using __variant_detail::__visitation::__variant;
-  bool __results[] = {__vs.valueless_by_exception()...};
-  for (bool __result : __results) {
-    if (__result) {
-      __throw_bad_variant_access();
-    }
-  }
-  return __variant::__visit_value(_VSTD::forward<_Visitor>(__visitor),
+  return __variant::__visit_value(_VSTD::forward<_Vis>(__vis),
                                   _VSTD::forward<_Vs>(__vs)...);
 }
 
 struct _LIBCPP_TEMPLATE_VIS monostate {};
 
 inline _LIBCPP_INLINE_VISIBILITY
 constexpr bool operator<(monostate, monostate) noexcept { return false; }
 

libcxx/test/libcxx/utilities/variant/variant.visit/visit_without_switch.pass.cpp

+// -*- 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, c++14
+
+// Throwing bad_variant_access is supported starting in macosx10.13
+// XFAIL: with_system_cxx_lib=macosx10.12 && !no-exceptions
+// XFAIL: with_system_cxx_lib=macosx10.11 && !no-exceptions
+// XFAIL: with_system_cxx_lib=macosx10.10 && !no-exceptions
+// XFAIL: with_system_cxx_lib=macosx10.9 && !no-exceptions
+
+// <variant>
+// template <class Visitor, class... Variants>
+// constexpr see below visit(Visitor&& vis, Variants&&... vars);
+
+#define _LIBCPP_DISABLE_SWITCH_VISIT_IN_VARIANT
+
+#include <cassert>
+#include <memory>
+#include <string>
+#include <type_traits>
+#include <utility>
+#include <variant>
+
+#include "test_macros.h"
+#include "type_id.h"
+#include "variant_test_helpers.h"
+
+enum CallType : unsigned {
+  CT_None,
+  CT_NonConst = 1,
+  CT_Const = 2,
+  CT_LValue = 4,
+  CT_RValue = 8
+};
+
+inline constexpr CallType operator|(CallType LHS, CallType RHS) {
+  return static_cast<CallType>(static_cast<unsigned>(LHS) |
+                               static_cast<unsigned>(RHS));
+}
+
+struct ForwardingCallObject {
+
+  template <class... Args> bool operator()(Args &&...) & {
+    set_call<Args &&...>(CT_NonConst | CT_LValue);
+    return true;
+  }
+
+  template <class... Args> bool operator()(Args &&...) const & {
+    set_call<Args &&...>(CT_Const | CT_LValue);
+    return true;
+  }
+
+  // Don't allow the call operator to be invoked as an rvalue.
+  template <class... Args> bool operator()(Args &&...) && {
+    set_call<Args &&...>(CT_NonConst | CT_RValue);
+    return true;
+  }
+
+  template <class... Args> bool operator()(Args &&...) const && {
+    set_call<Args &&...>(CT_Const | CT_RValue);
+    return true;
+  }
+
+  template <class... Args> static void set_call(CallType type) {
+    assert(last_call_type == CT_None);
+    assert(last_call_args == nullptr);
+    last_call_type = type;
+    last_call_args = std::addressof(makeArgumentID<Args...>());
+  }
+
+  template <class... Args> static bool check_call(CallType type) {
+    bool result = last_call_type == type && last_call_args &&
+                  *last_call_args == makeArgumentID<Args...>();
+    last_call_type = CT_None;
+    last_call_args = nullptr;
+    return result;
+  }
+
+  static CallType last_call_type;
+  static const TypeID *last_call_args;
+};
+
+CallType ForwardingCallObject::last_call_type = CT_None;
+const TypeID *ForwardingCallObject::last_call_args = nullptr;
+
+void test_call_operator_forwarding() {
+  using Fn = ForwardingCallObject;
+  Fn obj{};
+  const Fn &cobj = obj;
+  { // test call operator forwarding - no variant
+    std::visit(obj);
+    assert(Fn::check_call<>(CT_NonConst | CT_LValue));
+    std::visit(cobj);
+    assert(Fn::check_call<>(CT_Const | CT_LValue));
+    std::visit(std::move(obj));
+    assert(Fn::check_call<>(CT_NonConst | CT_RValue));
+    std::visit(std::move(cobj));
+    assert(Fn::check_call<>(CT_Const | CT_RValue));
+  }
+  { // test call operator forwarding - single variant, single arg
+    using V = std::variant<int>;
+    V v(42);
+    std::visit(obj, v);
+    assert(Fn::check_call<int &>(CT_NonConst | CT_LValue));
+    std::visit(cobj, v);
+    assert(Fn::check_call<int &>(CT_Const | CT_LValue));
+    std::visit(std::move(obj), v);
+    assert(Fn::check_call<int &>(CT_NonConst | CT_RValue));
+    std::visit(std::move(cobj), v);
+    assert(Fn::check_call<int &>(CT_Const | CT_RValue));
+  }
+  { // test call operator forwarding - single variant, multi arg
+    using V = std::variant<int, long, double>;
+    V v(42l);
+    std::visit(obj, v);
+    assert(Fn::check_call<long &>(CT_NonConst | CT_LValue));
+    std::visit(cobj, v);
+    assert(Fn::check_call<long &>(CT_Const | CT_LValue));
+    std::visit(std::move(obj), v);
+    assert(Fn::check_call<long &>(CT_NonConst | CT_RValue));
+    std::visit(std::move(cobj), v);
+    assert(Fn::check_call<long &>(CT_Const | CT_RValue));
+  }
+  { // test call operator forwarding - multi variant, multi arg
+    using V = std::variant<int, long, double>;
+    using V2 = std::variant<int *, std::string>;
+    V v(42l);
+    V2 v2("hello");
+    std::visit(obj, v, v2);
+    assert((Fn::check_call<long &, std::string &>(CT_NonConst | CT_LValue)));
+    std::visit(cobj, v, v2);
+    assert((Fn::check_call<long &, std::string &>(CT_Const | CT_LValue)));
+    std::visit(std::move(obj), v, v2);
+    assert((Fn::check_call<long &, std::string &>(CT_NonConst | CT_RValue)));
+    std::visit(std::move(cobj), v, v2);
+    assert((Fn::check_call<long &, std::string &>(CT_Const | CT_RValue)));
+  }
+}
+
+void test_argument_forwarding() {
+  using Fn = ForwardingCallObject;
+  Fn obj{};
+  const auto Val = CT_LValue | CT_NonConst;
+  { // single argument - value type
+    using V = std::variant<int>;
+    V v(42);
+    const V &cv = v;
+    std::visit(obj, v);
+    assert(Fn::check_call<int &>(Val));
+    std::visit(obj, cv);
+    assert(Fn::check_call<const int &>(Val));
+    std::visit(obj, std::move(v));
+    assert(Fn::check_call<int &&>(Val));
+    std::visit(obj, std::move(cv));
+    assert(Fn::check_call<const int &&>(Val));
+  }
+#if !defined(TEST_VARIANT_HAS_NO_REFERENCES)
+  { // single argument - lvalue reference
+    using V = std::variant<int &>;
+    int x = 42;
+    V v(x);
+    const V &cv = v;
+    std::visit(obj, v);
+    assert(Fn::check_call<int &>(Val));
+    std::visit(obj, cv);
+    assert(Fn::check_call<int &>(Val));
+    std::visit(obj, std::move(v));
+    assert(Fn::check_call<int &>(Val));
+    std::visit(obj, std::move(cv));
+    assert(Fn::check_call<int &>(Val));
+  }
+  { // single argument - rvalue reference
+    using V = std::variant<int &&>;
+    int x = 42;
+    V v(std::move(x));
+    const V &cv = v;
+    std::visit(obj, v);
+    assert(Fn::check_call<int &>(Val));
+    std::visit(obj, cv);
+    assert(Fn::check_call<int &>(Val));
+    std::visit(obj, std::move(v));
+    assert(Fn::check_call<int &&>(Val));
+    std::visit(obj, std::move(cv));
+    assert(Fn::check_call<int &&>(Val));
+  }
+  { // multi argument - multi variant
+    using S = const std::string &;
+    using V = std::variant<int, S, long &&>;
+    const std::string str = "hello";
+    long l = 43;
+    V v1(42);
+    const V &cv1 = v1;
+    V v2(str);
+    const V &cv2 = v2;
+    V v3(std::move(l));
+    const V &cv3 = v3;
+    std::visit(obj, v1, v2, v3);
+    assert((Fn::check_call<int &, S, long &>(Val)));
+    std::visit(obj, cv1, cv2, std::move(v3));
+    assert((Fn::check_call<const int &, S, long &&>(Val)));
+  }
+#endif
+}
+
+struct ReturnFirst {
+  template <class... Args> constexpr int operator()(int f, Args &&...) const {
+    return f;
+  }
+};
+
+struct ReturnArity {
+  template <class... Args> constexpr int operator()(Args &&...) const {
+    return sizeof...(Args);
+  }
+};
+
+void test_constexpr() {
+  constexpr ReturnFirst obj{};
+  constexpr ReturnArity aobj{};
+  {
+    using V = std::variant<int>;
+    constexpr V v(42);
+    static_assert(std::visit(obj, v) == 42, "");
+  }
+  {
+    using V = std::variant<short, long, char>;
+    constexpr V v(42l);
+    static_assert(std::visit(obj, v) == 42, "");
+  }
+  {
+    using V1 = std::variant<int>;
+    using V2 = std::variant<int, char *, long long>;
+    using V3 = std::variant<bool, int, int>;
+    constexpr V1 v1;
+    constexpr V2 v2(nullptr);
+    constexpr V3 v3;
+    static_assert(std::visit(aobj, v1, v2, v3) == 3, "");
+  }
+  {
+    using V1 = std::variant<int>;
+    using V2 = std::variant<int, char *, long long>;
+    using V3 = std::variant<void *, int, int>;
+    constexpr V1 v1;
+    constexpr V2 v2(nullptr);
+    constexpr V3 v3;
+    static_assert(std::visit(aobj, v1, v2, v3) == 3, "");
+  }
+}
+
+void test_exceptions() {
+#ifndef TEST_HAS_NO_EXCEPTIONS
+  ReturnArity obj{};
+  auto test = [&](auto &&... args) {
+    try {
+      std::visit(obj, args...);
+    } catch (const std::bad_variant_access &) {
+      return true;
+    } catch (...) {
+    }
+    return false;
+  };
+  {
+    using V = std::variant<int, MakeEmptyT>;
+    V v;
+    makeEmpty(v);
+    assert(test(v));
+  }
+  {
+    using V = std::variant<int, MakeEmptyT>;
+    using V2 = std::variant<long, std::string, void *>;
+    V v;
+    makeEmpty(v);
+    V2 v2("hello");
+    assert(test(v, v2));
+  }
+  {
+    using V = std::variant<int, MakeEmptyT>;
+    using V2 = std::variant<long, std::string, void *>;
+    V v;
+    makeEmpty(v);
+    V2 v2("hello");
+    assert(test(v2, v));
+  }
+  {
+    using V = std::variant<int, MakeEmptyT>;
+    using V2 = std::variant<long, std::string, void *, MakeEmptyT>;
+    V v;
+    makeEmpty(v);
+    V2 v2;
+    makeEmpty(v2);
+    assert(test(v, v2));
+  }
+#endif
+}
+
+// See https://bugs.llvm.org/show_bug.cgi?id=31916
+void test_caller_accepts_nonconst() {
+  struct A {};
+  struct Visitor {
+    void operator()(A&) {}
+  };
+  std::variant<A> v;
+  std::visit(Visitor{}, v);
+}
+
+int main(int, char**) {
+  test_call_operator_forwarding();
+  test_argument_forwarding();
+  test_constexpr();
+  test_exceptions();
+  test_caller_accepts_nonconst();
+
+  return 0;
+}