[libc++] Shrink variant's index type when possible

Summary:
Currently `std::variant` always uses an unsigned int to store the variant index. However this isn't nessesary and causes `std::variant` to be larger than it needs to be in most cases.

This patch changes the index type to be `unsigned char` when possible, and `unsigned short` or `unsigned int` otherwise, depending on the size (Although it's questionable if it's even possible to create a variant with 65535 elements.

Unfortunately this change is an ABI break, and as such is only enabled in ABI v2.

Reviewers: mpark

Reviewed By: mpark

Subscribers: cfe-commits

Differential Revision: https://reviews.llvm.org/D40210

llvm-svn: 318621

3 files changed, 103 insertions, 8 deletions

diff --git a/libcxx/include/__config b/libcxx/include/__config
index f62859f3401..561eb36ac1d 100644
--- a/libcxx/include/__config
+++ b/libcxx/include/__config
@@ -76,9 +76,11 @@
 // its vtable and typeinfo to libc++ rather than having all other libraries
 // using that class define their own copies.
 #define _LIBCPP_ABI_BAD_FUNCTION_CALL_KEY_FUNCTION
-
 // Enable optimized version of __do_get_(un)signed which avoids redundant copies.
 #define _LIBCPP_ABI_OPTIMIZED_LOCALE_NUM_GET
+// Use the smallest possible integer type to represent the index of the variant.
+// Previously libc++ used "unsigned int" exclusivly.
+#define _LIBCPP_ABI_VARIANT_INDEX_TYPE_OPTIMIZATION
 #elif _LIBCPP_ABI_VERSION == 1
 #if !defined(_LIBCPP_OBJECT_FORMAT_COFF)
 // Enable compiling copies of now inline methods into the dylib to support
diff --git a/libcxx/include/variant b/libcxx/include/variant
index f8d3e28bae4..13450ddf29b 100644
--- a/libcxx/include/variant
+++ b/libcxx/include/variant
@@ -207,6 +207,7 @@ namespace std {
 #include <tuple>
 #include <type_traits>
 #include <utility>
+#include <limits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
@@ -283,7 +284,28 @@ struct _LIBCPP_TEMPLATE_VIS variant_alternative<_Ip, variant<_Types...>> {
 };
 
 constexpr size_t variant_npos = static_cast<size_t>(-1);
-constexpr unsigned int __variant_npos = static_cast<unsigned int>(-1);
+
+constexpr int __choose_index_type(unsigned int __num_elem) {
+  if (__num_elem < std::numeric_limits<unsigned char>::max())
+    return 0;
+  if (__num_elem < std::numeric_limits<unsigned short>::max())
+    return 1;
+  return 2;
+}
+
+template <size_t _NumAlts>
+using __variant_index_t =
+#ifndef _LIBCPP_ABI_VARIANT_INDEX_TYPE_OPTIMIZATION
+  unsigned int;
+#else
+  std::tuple_element_t<
+      __choose_index_type(_NumAlts),
+      std::tuple<unsigned char, unsigned short, unsigned int>
+  >;
+#endif
+
+template <class _IndexType>
+constexpr _IndexType __variant_npos = static_cast<_IndexType>(-1);
 
 namespace __find_detail {
 
@@ -647,9 +669,11 @@ _LIBCPP_VARIANT_UNION(_Trait::_Unavailable, ~__union() = delete;);
 template <_Trait _DestructibleTrait, class... _Types>
 class _LIBCPP_TEMPLATE_VIS __base {
 public:
+  using __index_t = __variant_index_t<sizeof...(_Types)>;
+
   inline _LIBCPP_INLINE_VISIBILITY
   explicit constexpr __base(__valueless_t tag) noexcept
-      : __data(tag), __index(__variant_npos) {}
+      : __data(tag), __index(__variant_npos<__index_t>) {}
 
   template <size_t _Ip, class... _Args>
   inline _LIBCPP_INLINE_VISIBILITY
@@ -665,7 +689,7 @@ public:
 
   inline _LIBCPP_INLINE_VISIBILITY
   constexpr size_t index() const noexcept {
-    return __index == __variant_npos ? variant_npos : __index;
+    return __index == __variant_npos<__index_t> ? variant_npos : __index;
   }
 
 protected:
@@ -685,7 +709,7 @@ protected:
   static constexpr size_t __size() { return sizeof...(_Types); }
 
   __union<_DestructibleTrait, 0, _Types...> __data;
-  unsigned int __index;
+  __index_t __index;
 
   friend struct __access::__base;
   friend struct __visitation::__base;
@@ -696,10 +720,11 @@ class _LIBCPP_TEMPLATE_VIS __destructor;
 
 #define _LIBCPP_VARIANT_DESTRUCTOR(destructible_trait, destructor, destroy)    \
   template <class... _Types>                                                   \
-  class _LIBCPP_TEMPLATE_VIS __destructor<__traits<_Types...>,                \
+  class _LIBCPP_TEMPLATE_VIS __destructor<__traits<_Types...>,                 \
                                            destructible_trait>                 \
       : public __base<destructible_trait, _Types...> {                         \
     using __base_type = __base<destructible_trait, _Types...>;                 \
+    using __index_t = typename __base_type::__index_t;                         \
                                                                                \
   public:                                                                      \
     using __base_type::__base_type;                                            \
@@ -719,7 +744,7 @@ class _LIBCPP_TEMPLATE_VIS __destructor;
 _LIBCPP_VARIANT_DESTRUCTOR(
     _Trait::_TriviallyAvailable,
     ~__destructor() = default;,
-    void __destroy() noexcept { this->__index = __variant_npos; });
+    void __destroy() noexcept { this->__index = __variant_npos<__index_t>; });
 
 _LIBCPP_VARIANT_DESTRUCTOR(
     _Trait::_Available,
@@ -733,7 +758,7 @@ _LIBCPP_VARIANT_DESTRUCTOR(
             },
             *this);
       }
-      this->__index = __variant_npos;
+      this->__index = __variant_npos<__index_t>;
     });
 
 _LIBCPP_VARIANT_DESTRUCTOR(
diff --git a/libcxx/test/libcxx/utilities/variant/variant.variant/variant_size.pass.cpp b/libcxx/test/libcxx/utilities/variant/variant.variant/variant_size.pass.cpp
new file mode 100644
index 00000000000..a836ef5169e
--- /dev/null
+++ b/libcxx/test/libcxx/utilities/variant/variant.variant/variant_size.pass.cpp
@@ -0,0 +1,68 @@
+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <variant>
+
+// template <class ...Types> class variant;
+
+#include <limits>
+#include <type_traits>
+#include <utility>
+#include <variant>
+
+template <class Sequence>
+struct make_variant_imp;
+
+template <size_t ...Indices>
+struct make_variant_imp<std::integer_sequence<size_t, Indices...>> {
+  using type = std::variant<decltype((Indices, char(0)))...>;
+};
+
+template <size_t N>
+using make_variant_t = typename make_variant_imp<std::make_index_sequence<N>>::type;
+
+constexpr bool ExpectEqual =
+#ifdef _LIBCPP_ABI_VARIANT_INDEX_TYPE_OPTIMIZATION
+  false;
+#else
+  true;
+#endif
+
+template <class IndexType>
+void test_index_type() {
+  using Lim = std::numeric_limits<IndexType>;
+  using T1 = make_variant_t<Lim::max() - 1>;
+  using T2 = make_variant_t<Lim::max()>;
+  static_assert((sizeof(T1) == sizeof(T2)) == ExpectEqual, "");
+}
+
+template <class IndexType>
+void test_index_internals() {
+  using Lim = std::numeric_limits<IndexType>;
+  static_assert(std::__choose_index_type(Lim::max() -1) !=
+                std::__choose_index_type(Lim::max()), "");
+  static_assert(std::is_same_v<
+      std::__variant_index_t<Lim::max()-1>,
+      std::__variant_index_t<Lim::max()>
+    > == ExpectEqual, "");
+  using IndexT = std::__variant_index_t<Lim::max()-1>;
+  using IndexLim = std::numeric_limits<IndexT>;
+  static_assert(std::__variant_npos<IndexT> == IndexLim::max(), "");
+}
+
+int main() {
+  test_index_type<unsigned char>();
+  // This won't compile due to template depth issues.
+  //test_index_type<unsigned short>();
+  test_index_internals<unsigned char>();
+  test_index_internals<unsigned short>();
+}