[ADT] Add IntrusiveVariant, VariantTraits, and new STLForwardCompat

[scott.linder]

Summary

Add a compact, restricted version of the C++17 std::variant called
IntrusiveVariant. IntrusiveVariant stores the dynamic tag at the
beginning of every alternative type object, allowing for more efficient
packing in some cases.

Add an llvm::visit, which is compatible with std::visit and is generic
over any variant-like type which implements llvm::VariantTraits. Also
add llvm::visitSameAlternative which can be used when it is known that
all variants hold the same alternative type.

Also adds make_array, type_identity, in_place_index, and in_place_type
to STLForwardCompat.h

[whisperity]

llvm/include/llvm/ADT/IntrusiveVariant.h

13

Itself

Who? The IntrusiveVariant or the union members?

36–37

I think the implementation detail in the parens could go somewhere else. If this little bit of trivia shouldn't interest the average client library, it shouldn't be placed into an obvious position.

37–39

So is it visit or Visit?

55

Is it possible to suggest here writing an implicit conversion operator (operator int() const { return Int; }) and an assignment operator (AltInt& operator=(int Int)) to the wrapped type? Writing

if (V.holdsAlternative<AltDouble>())
{
  AltDouble AD = V.get<AltDouble>();
  takes_a_double(AD.getDouble());
  AD.setDouble(8.f);
}

is just incredibly superfluous when std::variant does this already with the get<> and the assignment operator.

I'm more concerned about the assignment operator. Can we assign a (mutable) reference to the variant's alternative?

139

The referred macro(?) is not defined anywhere.

[whisperity]

llvm/include/llvm/ADT/IntrusiveVariant.h

38

How much is the limit. Where is it stored? Might need a mention of the actual value (or symbol name) here.

60–68

I honestly believe for usability perspectives we should offer the user the option not to write all this out by hand. Just a simple wrapper over a double is 9 lines (or 11 if we include the assignment and implicit conversion from the suggestion above).

This is just waaaaaay too much. If we have like 2 or 3 variations in the variant, we are not much better (if any) than writing out the enum+union ourselves.

At least please consider providing a simple macro that wraps any alternate type into such a variant-capable thing.

For example, I'd like to use a variant like as follows. This is how one would use (std|boost)::variant, right?

struct Something { /* 3 data members */ };
struct SomeOtherThing { /* 3 other data members of different type! */ };


Variant<Something, SomeOtherThing> ThisOrThat;

Now I understand this doesn't work in your case directly. The whole intrusiveness would mean that I have to deal with either making the initial data member private, and then what happens to my other data members that should (or, must!) be public instead?

As a user, I am happy to put up with having to write two additional lines, i.e.

struct Something { /* 3 data members */ };
struct SomeOtherThing { /* 3 other data members of different type! */ };

MAKE_VARIANT_ALTERNATIVE_TYPE(Something);
MAKE_VARIANT_ALTERNATIVE_TYPE(SomeOtherThing);

Variant<AltSomething, AltSomeOtherThing> ThisOrThat;
//      ^~~           ^~~  Might be tricky to figure out!

But the idea is that some of the boilerplate required to make my types (or wrappers thereof) compatible with a working variant (which I love the idea of, by the way!) should not require me to write almost the same insane amount of code as I would have to with a conventional tagged union.

145–146

Are instances of this class only instantiated in the global scope? What's the guarantee that Index will initialise to anything?

[whisperity]

I'm not qualified with template magic and I am definitely not a person of authority on this library, so all my comments come from a generally strictly "user's perspective". I would love to have a variant type (it's surprising there never has been one in the code for so long), and I am happy I found this patch instead of trying to get into writing a similar thing myself...

llvm/include/llvm/ADT/IntrusiveVariant.h

208–209

There is a bit too much template "magic" to wrap my head around so quickly, but I have a question: does this implementation allow non-default-constructible alternative types? Or any chance that it forbids default-constructible ones? What's the stance on that. The examples in the leading documentation seem to indicate that all alternatives are non-default-ctorable... However, the "formal" requirements only say they must be trivially-dtorable and standard layout. What's the stance on default constructibleness?

[scott.linder]

Thank you for taking a look @whisperity! I'm glad there is interest from others in the new type, I was worried at first it may be too niche of a use.

I didn't notice your comments until late today, but next week I will make a pass over them, respond, and update the patch.

I had intended to add more potentially-interested reviewers, possibly by posting to llvm-dev, but I was also in the process of rebasing the patchset which precipitated me factoring this out into include/ADT and wanted to make sure it was at the very least usable in that context, so thank you for adding some!

I'm also leaving a few comments I had already drafted as a reminder to myself.

llvm/include/llvm/ADT/IntrusiveVariant.h

216

Should be a move constructor?

258

Maybe rename to FallibleIntrusiveVariantVisitor and fallibleVisit or visitOrError?

llvm/unittests/ADT/IntrusiveVariantTest.cpp

28

These could be simplified, e.g. ASSERT_TRUE(V.hasAlternative<A>())

[whisperity]

In D98477#2638731, @scott.linder wrote:

I'm glad there is interest from others in the new type, I was worried at first it may be too niche of a use.

At face value, I'd like to use it in D75041 in the following context, instead of the tagged union, do have an Optional<Variant<ConvertingCtor, ConversionOperator>> UserConversion. 🙂

enum UserDefinedConversionKind { UDCK_None, UDCK_Ctor, UDCK_Oper };

struct UserDefinedConvertingConstructor {
  const CXXConstructorDecl *Fun;
  QualType ConstructorParameterType;
  QualType UserDefinedType;
};

struct UserDefinedConversionOperator {
  const CXXConversionDecl *Fun;
  QualType UserDefinedType;
  QualType ConversionOperatorResultType;
};

/// The details of the user-defined conversion involved, as a tagged union.
union {
  char None;
  UserDefinedConvertingConstructor UDConvCtor;
  UserDefinedConversionOperator UDConvOp;
};
UserDefinedConversionKind UDConvKind;

[scott.linder]

• Address feedback
• Fix bug where last alternative type could not be emplaced
• Misc cleanup

[scott.linder]

llvm/include/llvm/ADT/IntrusiveVariant.h

13

I tried to reword this a little to clarify, let me know if it helps or if you still see room for improvement.

The "alternative types" wording is lifted from std::variant, and that's what I was attempting to refer to here.

36–37

Good point, I think it can simply be deleted as the comments in detail should be sufficient to capture this. I also changed the phrasing "the set of alternative types must be unique" as I don't think it really says what I intended it to. Let me know what you think.

38

I added static constexpr members to IntrusiveVariant to describe the limits, and just referred to them everywhere the limits are mentioned.

The only place where this breaks down is in the macro to generate the actual switch in the implementation of llvm::visit and similar, but there are already other similar caveats and I see no way to overcome them without ditching the approach entirely.

55

Is it possible to suggest here writing an implicit conversion operator (operator int() const { return Int; }) and an assignment operator (AltInt& operator=(int Int)) to the wrapped type? Writing

I think in the context of this (admittedly over-simplified) example that makes perfect sense, but the moment you have anything more complex than a wrapper around another type it is not as useful anymore. For example I don't see any opportunity to simplify the following with implicit conversions:

if (V.holdsAlternative<Frobinator>()) {
  reticulate(V.get<Frobinator>().getSplines());
  V.get<Frobinator>().setWidget(getCachedWidgets());
}

if (V.holdsAlternative<AltDouble>())
{
  AltDouble AD = V.get<AltDouble>();
  takes_a_double(AD.getDouble());
  AD.setDouble(8.f);
}

is just incredibly superfluous when std::variant does this already with the get<> and the assignment operator.

I'm more concerned about the assignment operator. Can we assign a (mutable) reference to the variant's alternative?

Yes there is a non-const overload for IntrusiveVariant::get that you can assign into if the alternative type provides the appropriate copy/move assignment operator.

60–68

I agree there is a good chunk of boilerplate, but AFAICT there is no clean way to avoid this, and the real utility of the new type is in providing a type-safe, modern interface to a tagged union which is squeezed into the smallest possible memory footprint. For example instead of:

switch (MyTaggedUnion.getKind()) {
case MyTaggedUnion::K_int:
  // use MyTaggedUnion.getInt(), don't accidentally use any other accessors...
  break;
case MyTaggedUnion::K_float:
  // use MyTaggedUnion.getFloat(), don't accidentally use any other accessors...
  break;
case MyTaggedUnion::K_IntPair:
  // use MyTaggedUnion.getFirstInt(), don't accidentally use any other accessors...
  // use MyTaggedUnion.getSecondInt(), don't accidentally use any other accessors...
  break;
}

You can write:

visit(makeVisitor(
         [](AltInt I) { /* use I.getInt() */},
         [](AltFloat) { /* use I.getFloat() */},
         [](AltIntPair IP) { /* use IP.getFirstInt() and IP.getSecondInt() */}
       ), MyVariant);

And at several points things which would be runtime UB in the hand-written tagged-union case are now compile-time errors.

In trying to work through providing a simpler interface I run into problems with each approach. If you are just naively wrapping another type, then in general you are losing out on the optimization the IntrusiveVariant was designed around, which is to get more optimal packing when the "wrapped" type has spare padding that the tag could live in. Consider for example:

struct Inner { char X; int Y; };
struct Outer { char C; Inner I; };
struct Flat { char C; char X; int Y; };
static_assert(sizeof(Flat) < sizeof(Outer), "");

So the only way I see to implement something along the lines of what you suggest is to have a handful of macros to "begin", "add_member", and "end" an alternative:

BEGIN_VARIANT_ALTERNATIVE_TYPE(AltSomething)
ADD_MEMBER_VARIANT_ALTERNATIVE_TYPE(TypeA, A);
ADD_MEMBER_VARIANT_ALTERNATIVE_TYPE(TypeB, B);
ADD_MEMBER_VARIANT_ALTERNATIVE_TYPE(TypeC, C);
END_VARIANT_ALTERNATIVE_TYPE()

Where the above would expand to a class definition.

This seems less attractive than just having some boilerplate, and it doesn't cover the reasonable cases where a class doesn't want to expose all of its members uniformly.

208–209

There is a bit too much template "magic" to wrap my head around so quickly

You and me both :^) I tried to skip as many features as seemed reasonable in an effort to keep the amount of template/preprocessor magic to the bare minimum, but the result is still pretty dense :(

does this implementation allow non-default-constructible alternative types? Or any chance that it forbids default-constructible ones? What's the stance on that.

This supports both default-constructible and non-default-constructible alternative types. The possibilities are:

The type pack ArgTs is empty, in which case it is essentially equivalent to:

template <std::size_t I>
UnionImpl(InPlaceIndex<I>) {

Which will result in default-constructing the appropriate union member if it is default-constructible, otherwise it will result in a compile-time error indicating overload resolution could not find an appropriate constructor.

Or, the type pack is not empty, and we forward whatever arguments along to the appropriate union member's non-default constructor.

The examples in the leading documentation seem to indicate that all alternatives are non-default-ctorable

I can add an example of a type that is default-constructible, but there is explicit documentation as part of IntrusiveVariant itself that an IntrusiveVariant is default-constructible iff the first alternative type is:

/// A default constructed IntrusiveVariant holds a default constructed value
/// of its first alternative. Only enabled if the first alternative has a
/// default constructor.
template <int B = std::is_default_constructible<detail::NthType<0, Ts...>>{},
           typename std::enable_if_t<B, int> = 0>
constexpr IntrusiveVariant() : Union(detail::InPlaceIndex<0>{}) {}

And otherwise the default constructors are just constructors with no arguments, and you can emplace using any alternative type constructor.

[dblaikie]

Looks like this visitor infrastructure has some overlap with D99560 and D99561 - be good to deduplicate some work here, perhaps.

[dblaikie]

Perhaps PointerUnion could be implemented as a derivation from this intrusive variant in a follow-up change, subsuming D99561

[scott.linder]

In D98477#2660482, @dblaikie wrote:

Looks like this visitor infrastructure has some overlap with D99560 and D99561 - be good to deduplicate some work here, perhaps.

Yes, I agree that factoring out llvm::makeVisitor and llvm::visit and making it work over all variant-like types makes sense. It's unfortunate that even once we move to C++17 we won't be able to re-open std to specialize std::visit for our types, at least if I understand correctly. We may just be stuck with llvm::visit and std::visit living side-by-side?

I also think things like InPlaceType could be moved somewhere general; llvm::Optional has an in_place_t as a detail, so pulling all of those new disambiguation types into a common place would also be good.

[scott.linder]

In D98477#2660486, @dblaikie wrote:

Perhaps PointerUnion could be implemented as a derivation from this intrusive variant in a follow-up change, subsuming D99561

I'm not as familiar with the implementation of PointerUnion, I just noted when I did a pass over the LLVM container types that it wouldn't be sufficient for the specific thing I was working on, so I started writing my own compact variant-like type. At the very least I think we should have a common llvm::visit with specializations for both llvm::PointerUnion and llvm::IntrusiveVariant.

[dblaikie]

In D98477#2664061, @scott.linder wrote:

In D98477#2660486, @dblaikie wrote:

Perhaps PointerUnion could be implemented as a derivation from this intrusive variant in a follow-up change, subsuming D99561

I'm not as familiar with the implementation of PointerUnion, I just noted when I did a pass over the LLVM container types that it wouldn't be sufficient for the specific thing I was working on, so I started writing my own compact variant-like type. At the very least I think we should have a common llvm::visit with specializations for both llvm::PointerUnion and llvm::IntrusiveVariant.

Hopefully/probably overloads, rather than specializations (it's not possible to partially specialize a function template, in any case), but yeah -

llvm/include/llvm/ADT/IntrusiveVariant.h

160–167

Can we instead use/generalize something like the type traits used for PointerUnion that declare the number of spare bits in the type? Since we already have those in LLVM (& to macro-y).

277–281

Not sure I follow why this ends up as a runtime error - what if the overload with unreachable (down at 307) wasn't defined? Wouldn't that produce a compile-time error only when the index is out of bounds?

328–344

There's a fair bit of macro expansion stuff here - any chance it can be restructured to use variadic templates to generalize better/reduce the macro usage?

430–433

Technically C++ doesn't allow access to a common initial sequence except for types with standard layout, I think? So types with non-trivial copy ops, etc, wouldn't be usable here. (I wonder what PointerUnion does? I guess it just stuffs everything in void* or uintptr_t, which isn't exactly applicable here - but maybe some aligned storage would be suitable here)

[scott.linder]

llvm/include/llvm/ADT/IntrusiveVariant.h

160–167

My understanding of the PointerUnion case is that the standard allows the bitwise manipulation of pointer representations so long as you jump through the appropriate casting hoops (i.e. to (u)intptr_t and back) and ensure you end up with the same representation before casting back. For objects of arbitrary standard-layout type I don't know that we have any neat way to ensure we don't invoke UB, as the "padding" bits in the object representation are not guaranteed to be preserved over most uses of the struct, AFAIK.

That said, if I'm just missing something I would be very happy to remove DECLARE_INTRUSIVE_ALTERNATIVE. I currently see it as an acceptable concession needed to meet the requirements of the "common initial sequence" rule, which seems like the only way to get the compact layout without invoking UB.

277–281

AFAICT the only way to get that behavior is to have a separate overload for every size of IntrusiveVariant we support, as there is no way to recursively generate the switch itself, and if we just declare a switch with some arbitrary number of case limbs (in my patch this is 32) then it is a compile-time error to use any IntrusiveVariant with fewer than 32 alternatives.

In the simplest case:

visit(Callable C, IntrusiveVariant<A> IV) { // i.e. toy example of a monomorphized visit for a variant with a single alternative type A
  switch (IV.index()) {
  case 0: C(IV.Union.getMember(InPlaceIndex{0})); break;
  case 1: C(IV.Union.getMember(InPlaceIndex{1})); break; // This does not resolve to any overload of getMember, and is a compile-time error.
  }
}

In the above, if we only wrote one template for visit and it has two case limbs in the switch, then it will only compile for variants with exactly two alternative types. If we could recursively generate the body of visit we could do this without the unreachable workaround, but I don't see how to.

328–344

I think this is getting at the same issue as above, and I don't see any way to generate a switch with a compile-time determined number of case limbs using variadic templates :/

430–433

Yes, that's my understanding too, and I do static_assert the standard-layout-ness of all alternative types and mention this restriction in the file header comment.

maybe some aligned storage would be suitable here

I think this is the point I may be missing up above, but if I understand what you're getting at the idea would be to basically:

• Allocate an array of char with the maximum alignment of any of the alternative types
• If possible, put our index tag in any padding left over after the value representation of all the alternative types (as I mentioned above, this is the part I'm unsure about concerning UB)
• Manage all of the construction, copying, moving, destruction of alternative types in the array of char

If there is a way to do this without relying on UB, then it seems reasonable to me. I do worry it would end up being a lot of code, in particular I think we would need to do something like the libcxx implementation of std::variant to support all of the possible combinations of levels of trivial-ness of construction, copying, destruction, etc. which was something I wanted to avoid doing purely to make the code simpler.

[dblaikie]

llvm/include/llvm/ADT/IntrusiveVariant.h

160–167

Wondering if it might be more intuitive for users to work from the back instead - bit more work in the implementation, though?

eg: if I've got a {int, char} struct, and I use some tool to dump the layout and find I have 3 bytes of tail padding I could create an array of 3 chars at the end ({int, char, char[3]}) and specialize some template to say "I have 3 bytes of tail padding char array" - guess that still doesn't provide compatibility/foundation to implement pointer union on. Would have to declare the spare space in bits, and the aliasing would still be a problem for the pointer case

I guess the system you've got means you don't have to specialize another template, etc - the existence of a friend-accessed member with a specific name you can check for is enough evidence the type has agreed to be intrusively varianted.

I'd love to here @rsmith's or other C++-y folks thoughts on this, as it's some non-trivial design with interesting overlap on existing constructs.

277–281

I've missed a step in the logic here.

I'm still trying to wrap my head around: What happens if the function defined below with llvm_unreachable was instead not defined at all? Where is the code that's creating a dead call to this code such that it needs to be defined, but is guaranteed never to be called?

Separately, as for the switches: Presumably some recursion could be used instead. Yeah, it doesn't scale well especially at -O0 codegen.

Oh, maybe an array of function pointers could be used - a function template templated on the index? Would avoid the recursion.

430–433

Ah. Rather than using the common initial sequence rule - could you instead take a pointer and reinterpret_cast it - knowing that the member is at the start of the object? I would've thought that would be valid even without the common initial sequence rule - but maybe there's some pointer providence that makes that approach invalid?

(eg: if I know struct x { int; }; starts with an int, and I have x *y = &some_x; can I not reinterpret_cast y to int* and dereference it?)

but, yeah - partly I was thinking of putting it at the end rather than the beginning - and, yeah, I'm not sure what happens if you have some of these chars at the end of the object, then some trailing after the object (if some of the objects are of different sizes) it may be fussy to correctly address all those bytes (struct-internal padding, and external padding) in a simple/uniform way.

[scott.linder]

Sorry for the delay in replying, you pose some very good questions and I wanted to revisit the reasoning that led me to my current approach in as thorough a way as possible (which meant it took some time, and I didn't get around to it right away).

llvm/include/llvm/ADT/IntrusiveVariant.h

277–281

What happens if the function defined below with llvm_unreachable was instead not defined at all?

In short, it is a compile-time error to use any IntrusiveVariant without exactly MaxNumberOfAlternatives alternative types. In effect, the compiler sees exactly one switch with exactly MaxNumberOfAlternatives non-default cases, each of which calls FallibleIntrusiveVariantVisitor::operator(). If the IntrusiveVariant has fewer than MaxNumberOfAlternatives, some of those calls do not resolve to any overload and the compiler complains.

More generally, with the approach I'm taking, when calling visit defined with N non-default switch cases on an IntrusiveVariant with M alternative types:

• If N == M, each alternative type corresponds to exactly one case, and exactly one meaningful overload of FallibleIntrusiveVariantVisitor::operator().
• If N < M, the first M alternative types correspond to exactly one case, and exactly one meaningful overload of FallibleIntrusiveVariantVisitor::operator(). The remaining M - N cases correspond to the default: case, and we hit a runtime error. This should be a compile time error, which I manually enforce with static_assert(sizeof...(Ts) <= MaxNumberOfAlternatives); this isn't particularly pretty, but with the simplest switch-based approach I don't know how to achieve anything better.
• If N > M, the first M alternative types correspond to exactly one case, and exactly one meaningful overload of FallibleIntrusiveVariantVisitor::operator(). However, there are N - M additional cases in the switch, which call "invalid" or "non-meaningful" overloads of FallibleIntrusiveVariantVisitor::operator(). We must provide a definition of these functions to satisfy the compiler/linker, but by construction we ensure they can never actually be called at runtime. To try to convey this to the compiler, we define them to call llvm_unreachable.

Separately, as for the switches: Presumably some recursion could be used instead. Yeah, it doesn't scale well especially at -O0 codegen.

Oh, maybe an array of function pointers could be used - a function template templated on the index? Would avoid the recursion.

Both of these are definitely viable, and have different tradeoffs. I landed on switch-based because:

• It demands the least amount of work by the compiler to be efficient at runtime. As you mention, this matters most at -O0
• It demands the least amount of work by the compiler to produce a compact binary. This is (or at least was) apparently an issue in some real world cases with e.g. libc++'s array-of-function-pointer based approach, resulting in pretty significant code-bloat. It has led to multiple attempts to incorporate a switch-based approach into libc++'s implementation of visit.
• It seemed (definitely subjectively) like the simplest to write and read. The need for the "fallible" adapter might negate some of this, though, so I'm not so certain this is true anymore.

The current state of this in libc++ seems to be that the switch-based approach has been landed and reverted multiple times, each time the revert noting the general approach is still sound, but some issue with the exact implementation was identified and could not be fixed in a short enough window to avoid reverting. The most recent revert is https://reviews.llvm.org/D91662

The fix to this in my patch is to simply not implement the full generality, and have some relatively small limit on the number of alternative type supported. That way the code generated scales linearly with the number of unique IntrusiveVariant types instantiated, and has a pretty small constant factor (a 32-case switch where each branch is a call). At higher optimization levels I would expect all of this to be pretty routinely optimized away, but I haven't actually verified that.

Maybe @mpark, @ldionne, @EricWF have some guidance on what the best implementation strategy for an LLVM-specific visit might be?

[scott.linder]

Rebase and do some cleanup

[dblaikie]

Could you reupload this (or maybe you can handle this just by editing the revision here on the web UI?) using arc/phab's ability to flag dependent patches/part of a series, hopefully that'll make it easier to apply the patch to test things? (tried just applying this patch and of course no template named 'TypeAtIndex')

llvm/include/llvm/ADT/IntrusiveVariant.h

277–281

Yeah, would be happy to hear from the libc++ folks - though, for what it's worth I think maybe the array of function pointers might be simpler (once the patch series is updated so it's easier to apply for testing, I'll poke around with a few options) for our purposes without having to necessarily have the same priorities a highly general library like libc++ has.

[scott.linder]

In D98477#2775242, @dblaikie wrote:

Could you reupload this (or maybe you can handle this just by editing the revision here on the web UI?) using arc/phab's ability to flag dependent patches/part of a series, hopefully that'll make it easier to apply the patch to test things? (tried just applying this patch and of course no template named 'TypeAtIndex')

Yes, I had meant to from the start, I think it should be correct now if you want to try again

llvm/include/llvm/ADT/IntrusiveVariant.h

277–281

That's fair, thinking about it again the fact that we are not intending to support visiting multiple variants means the array will be 1-dimensional, which should make it easier to read and reduce the code-bloat in the unoptimized case. I can also draft an implementation of that

[dblaikie]

Side thought: If this is going to use a prefix for the discriminator - could that be a base class that all types being used as union members have to derive from? No need for a macro, etc. Could use an offsetof comparison to make sure that not only is it a base class, but the first non-empty base class.

(still haven't been able to easily apply this locally - looks like it hit a conflict with c6f20d70a8c93ab3d50c9777c477fe040460a664 - though I thought arc would sync to the right version to apply the patch... not sure what's going on - might just wait to try that until the other patches have been committed)

[scott.linder]

Try to factor out the implementation of visit to be based on specializations
of a type VariantTraits. This should make it possible to share one
implementation with other variant-like types, for example PointerUnion.

Switch to an array-of-functions approach which doesn't have any restrictions on
the number of alternative types or the number of variants visited at once.

There are still some WIP things, including SFINAE tests on at least
llvm::visit, a lot of documentation, and the trait implementation for
PointerUnion. Other functions like holds_alternative and get could also be
handled in the same way.

I wanted to get feedback on the general approach before going any further.

[scott.linder]

In D98477#2780702, @dblaikie wrote:

Side thought: If this is going to use a prefix for the discriminator - could that be a base class that all types being used as union members have to derive from? No need for a macro, etc. Could use an offsetof comparison to make sure that not only is it a base class, but the first non-empty base class.

(still haven't been able to easily apply this locally - looks like it hit a conflict with c6f20d70a8c93ab3d50c9777c477fe040460a664 - though I thought arc would sync to the right version to apply the patch... not sure what's going on - might just wait to try that until the other patches have been committed)

Unfortunately having any non-static data members as part of a base class will make the alternative types non-standard-layout, which means we can't use the "common initial sequence" rule to pack them.

[dblaikie]

In D98477#2783276, @scott.linder wrote:

In D98477#2780702, @dblaikie wrote:

Side thought: If this is going to use a prefix for the discriminator - could that be a base class that all types being used as union members have to derive from? No need for a macro, etc. Could use an offsetof comparison to make sure that not only is it a base class, but the first non-empty base class.

(still haven't been able to easily apply this locally - looks like it hit a conflict with c6f20d70a8c93ab3d50c9777c477fe040460a664 - though I thought arc would sync to the right version to apply the patch... not sure what's going on - might just wait to try that until the other patches have been committed)

Unfortunately having any non-static data members as part of a base class will make the alternative types non-standard-layout, which means we can't use the "common initial sequence" rule to pack them.

But would we need to use the common initial sequence rule? If the base object was at the start of the layout - a pointer to the start of the layout would be a valid pointer to the base object, yeah?

[scott.linder]

In D98477#2787409, @dblaikie wrote:

In D98477#2783276, @scott.linder wrote:

In D98477#2780702, @dblaikie wrote:

Side thought: If this is going to use a prefix for the discriminator - could that be a base class that all types being used as union members have to derive from? No need for a macro, etc. Could use an offsetof comparison to make sure that not only is it a base class, but the first non-empty base class.

(still haven't been able to easily apply this locally - looks like it hit a conflict with c6f20d70a8c93ab3d50c9777c477fe040460a664 - though I thought arc would sync to the right version to apply the patch... not sure what's going on - might just wait to try that until the other patches have been committed)

Unfortunately having any non-static data members as part of a base class will make the alternative types non-standard-layout, which means we can't use the "common initial sequence" rule to pack them.

But would we need to use the common initial sequence rule? If the base object was at the start of the layout - a pointer to the start of the layout would be a valid pointer to the base object, yeah?

AFAIK that isn't true: we can't assume the base subobject is at the start of the layout of the derived object unless both are standard-layout. The first example I could think of where the assumption breaks down with any reasonable compiler is multiple inheritence, e.g. in https://godbolt.org/z/K9rnxbPo9 it is impossible to know where to find the base subobject for the dynamic alternative object when all we have is a pointer to whatever is providing storage for it. Put another way, we need to already know the dynamic derived type to do this, which is the thing we are after in the first place.

The example in the above godbolt is:

#include <cstdint>

struct Base { int tag; };
struct Unrelated { int foo; };
struct AlternativeA : Base { int bar; };
struct AlternativeB : Unrelated, Base { int baz; };

AlternativeA A;
AlternativeB B;

uintptr_t AddrA() { return (uintptr_t)(void*)&A; }
uintptr_t AddrAtoBase() { return (uintptr_t)(void*)(Base*)&A; }

uintptr_t AddrB() { return (uintptr_t)(void*)&B; }
uintptr_t AddrBtoBase() { return (uintptr_t)(void*)(Base*)&B; }
uintptr_t AddrBtoUnrelated() { return (uintptr_t)(void*)(Unrelated*)&B; }

Where in trunk clang AddrB() != AddrBtoBase().

Maybe there are not other examples where a reasonable compiler doesn't lay out a sole base class at the start of the derived class, but even still it violates strict aliasing if we aren't talking about standard-layout types.

I also tried to look deeper into how this might be implemented using aligned storage, which you suggested earlier. As you point out, there are potential provenance issues. The pointer to the object which provides storage cannot be cast to a derived type without std::launder in at least some cases, although std::launder doesn't exist until C++17 and it isn't clear what the correct interpretation is for a C++14 compiler. Additionally, your example of reinterpret_cast to access the first member is only valid for standard-layout types.

The suggestion to put the tag at the end, starting after the object representation of the biggest alternative type, seems the most feasible, assuming:

• We don't need std::launder pre-C++17
• No reasonable compiler we support for compiling LLVM will be modifying trailing padding, i.e. bits in the object representation that are not a part of the value representation. The only thing I found with a quick search is __builtin_clear_padding which seems to be intended for use with atomics https://reviews.llvm.org/D87974?id=292987
• We can figure out some way to know where the padding in each alternative object starts. You suggested a traits-like mechanism where the alternative itself tries to occupy all the space it expects to be padding with a char array, and makes our implementation aware of it. I don't think I'm happy with that approach for the reasons you mention, and because it seems very non-ergonomic for the user, much more than requiring them to invoke a macro or derive from a base class.

If we can come up with a reliable way to know what padding bits are available, and are comfortable with the fact that compilers are not interested in clobbering them, then I think the std::launder issue seems like a minor detail we can figure out one way or another.

Do you have any thoughts on how I might go about tackling this? It would be really nice to have a cleaner interface to IntrusiveVariant, but I'm still just stuck on how to achieve it in a portable way.

Edit: Also, thank you for being so thorough and responsive in reviewing this! I'm excited to see the design moving in a cleaner direction :^)

Edit: Where I say "it violates strict aliasing" above, I'm not sure if I'm using that term too loosely, but to clarify: the specific case of a reinterpret_cast between a pointer to a standard-layout struct and its first member/base subobject is allowed by (9.2.19):

If a standard-layout class object has any non-static data members, its address is the same as the address of its first non-static data member. Otherwise, its address is the same as the address of its first base class subobject (if any). [ Note: There might therefore be unnamed padding within a standard-layout struct object, but not at its beginning, as necessary to achieve appropriate alignment. — end note ]

combined with (5.2.9.13):

A prvalue of type “pointer to cv1 void” can be converted to a prvalue of type “pointer to cv2 T,” where T is an object type and cv2 is the same cv-qualification as, or greater cv qualification than, cv1. The null pointer value is converted to the null pointer value of the destination type. If the original pointer value represents the address A of a byte in memory and A satisfies the alignment requirement of T, then the resulting pointer value represents the same address as the original pointer value, that is, A. The result of any other such pointer conversion is unspecified. A value of type pointer to object converted to “pointer to cv void” and back, possibly with different cv-qualification, shall have its original value.

I.e. they have the same address, so you can reinterpret_cast between them. C++17 adds a pointer-interconvertible relation which seems to formalize this more.

[dblaikie]

In D98477#2797129, @scott.linder wrote:

In D98477#2787409, @dblaikie wrote:

In D98477#2783276, @scott.linder wrote:

In D98477#2780702, @dblaikie wrote:

Side thought: If this is going to use a prefix for the discriminator - could that be a base class that all types being used as union members have to derive from? No need for a macro, etc. Could use an offsetof comparison to make sure that not only is it a base class, but the first non-empty base class.

(still haven't been able to easily apply this locally - looks like it hit a conflict with c6f20d70a8c93ab3d50c9777c477fe040460a664 - though I thought arc would sync to the right version to apply the patch... not sure what's going on - might just wait to try that until the other patches have been committed)

Unfortunately having any non-static data members as part of a base class will make the alternative types non-standard-layout, which means we can't use the "common initial sequence" rule to pack them.

But would we need to use the common initial sequence rule? If the base object was at the start of the layout - a pointer to the start of the layout would be a valid pointer to the base object, yeah?

AFAIK that isn't true: we can't assume the base subobject is at the start of the layout of the derived object unless both are standard-layout.

My hope/thought was/is to use offsetof to check that the member is at the start of the object. Though, yes, for maximal portability, offsetof does require standard layout (though it seems both clang and gcc support it at least in some more cases than that: https://godbolt.org/z/Pjr6YEqMq )

In any case - even if it still leaves us with the standard layout restriction - using a base class rather than a macro+member seems like a nicer/more usable solution?

But yeah, that still means standard layout, and potentially using the common initial sequence rules - I think I'm OK with that. Type punning's probably OK there too, but common initial sequence seems OK. And since it's only one byte - I'm OK with going at the front rather than the end.

But, yeah, I think using a base class rather than a macro would be good & I think it's as valid.

llvm/unittests/ADT/IntrusiveVariantTest.cpp

48–77

Could this be a template (& 3 typedefs), rather than a macro?

[scott.linder]

In D98477#2798018, @dblaikie wrote:

In D98477#2797129, @scott.linder wrote:

In D98477#2787409, @dblaikie wrote:

In D98477#2783276, @scott.linder wrote:

In D98477#2780702, @dblaikie wrote:

Side thought: If this is going to use a prefix for the discriminator - could that be a base class that all types being used as union members have to derive from? No need for a macro, etc. Could use an offsetof comparison to make sure that not only is it a base class, but the first non-empty base class.

(still haven't been able to easily apply this locally - looks like it hit a conflict with c6f20d70a8c93ab3d50c9777c477fe040460a664 - though I thought arc would sync to the right version to apply the patch... not sure what's going on - might just wait to try that until the other patches have been committed)

Unfortunately having any non-static data members as part of a base class will make the alternative types non-standard-layout, which means we can't use the "common initial sequence" rule to pack them.

But would we need to use the common initial sequence rule? If the base object was at the start of the layout - a pointer to the start of the layout would be a valid pointer to the base object, yeah?

AFAIK that isn't true: we can't assume the base subobject is at the start of the layout of the derived object unless both are standard-layout.

My hope/thought was/is to use offsetof to check that the member is at the start of the object. Though, yes, for maximal portability, offsetof does require standard layout (though it seems both clang and gcc support it at least in some more cases than that: https://godbolt.org/z/Pjr6YEqMq )

In any case - even if it still leaves us with the standard layout restriction - using a base class rather than a macro+member seems like a nicer/more usable solution?

The moment we have non-static data members in both a derived class and its base class the derived class becomes non-standard-layout, though. Even just the following will not work:

struct VariantHeader {
  uint8_t Tag;
};

// SomeAlternative is not standard-layout
struct SomeAlternative : VariantHeader {
  int Foo;
};

But yeah, that still means standard layout, and potentially using the common initial sequence rules - I think I'm OK with that. Type punning's probably OK there too, but common initial sequence seems OK. And since it's only one byte - I'm OK with going at the front rather than the end.

But, yeah, I think using a base class rather than a macro would be good & I think it's as valid.

[dblaikie]

In D98477#2800058, @scott.linder wrote:

In D98477#2798018, @dblaikie wrote:

In D98477#2797129, @scott.linder wrote:

In D98477#2787409, @dblaikie wrote:

In D98477#2783276, @scott.linder wrote:

In D98477#2780702, @dblaikie wrote:

Side thought: If this is going to use a prefix for the discriminator - could that be a base class that all types being used as union members have to derive from? No need for a macro, etc. Could use an offsetof comparison to make sure that not only is it a base class, but the first non-empty base class.

(still haven't been able to easily apply this locally - looks like it hit a conflict with c6f20d70a8c93ab3d50c9777c477fe040460a664 - though I thought arc would sync to the right version to apply the patch... not sure what's going on - might just wait to try that until the other patches have been committed)

Unfortunately having any non-static data members as part of a base class will make the alternative types non-standard-layout, which means we can't use the "common initial sequence" rule to pack them.

But would we need to use the common initial sequence rule? If the base object was at the start of the layout - a pointer to the start of the layout would be a valid pointer to the base object, yeah?

AFAIK that isn't true: we can't assume the base subobject is at the start of the layout of the derived object unless both are standard-layout.

My hope/thought was/is to use offsetof to check that the member is at the start of the object. Though, yes, for maximal portability, offsetof does require standard layout (though it seems both clang and gcc support it at least in some more cases than that: https://godbolt.org/z/Pjr6YEqMq )

In any case - even if it still leaves us with the standard layout restriction - using a base class rather than a macro+member seems like a nicer/more usable solution?

The moment we have non-static data members in both a derived class and its base class the derived class becomes non-standard-layout, though. Even just the following will not work:

struct VariantHeader {
  uint8_t Tag;
};

// SomeAlternative is not standard-layout
struct SomeAlternative : VariantHeader {
  int Foo;
};

Ah, thanks for the correction, I missed the "Has all non-static data members and bit-fields declared in the same class (either all in the derived or all in some base)" part of the Standard Layout requirement.

@rsmith got any thoughts on this? I'd rather not have a macro stamping out this member, though I appreciate wanting to have it only be accessible to the variant type (so wanting it to be private+friended) - I do rather like/prefer being able to use a base class, though it means going off-spec with offsetof usage in a non-standard-layout type (& possibly making the offsetof check only done on certain compilers - crossing our fingers that the compilers we didn't test on don't break the layout requirement))

[scott.linder]

• Clean up, rename, and document the VariantTraits interfaces
• Expose IntrusiveVariant::index() as it is already available through the traits
• Fix a bug in IntrusiveVariant comparison functions

[scott.linder]

Ping

I did try to write an offsetof-based version using inheritance instead of the "common initial sequence" rule, but I am not sure how to do the necessary checks statically. The best I can see to do would be to have some dynamic ASSERTs to confirm that casting the alternative type to the base type does not change the underlying representation (i.e. if both pointers are cast to uintptr_t they are equal).

[scott.linder]

Add an extra function makeThunkForSameAlternative to force old versions of
gcc to deduce the return value of the overloaded "thunk" being instantiated
before deducing the template arguments for make_array.

Workaround for https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64194

[dblaikie]

@rsmith @dexonsmith @aaron.ballman - folks who might have some opinions on C++ API design. Any thoughts on this patch in general, but also in particular how the discriminator is represented in supported classes? (I'd like to avoid macros, and there are a few tradeoffs around that)

[scott.linder]

Rebase, ping

[ldionne]

Sorry, I don't have bandwidth to chime in.

[scott.linder]

No worries, I understand the patch is pretty big and the template code is (unfortunately) dense.

If it would help any other reviewers I can also try to split things up further. One easy axis to do this is the addition of llvm::make_array, and another is VariantTraits.h, both of which can be reviewed independently. Just let me know if this would simplify things for anyone!

I also intend to address an issue with return type inference for overloaded visitor operator()s, like the standards body did with http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0655r0.pdf in C++20 (essentially adding a visit<R> where you can specify the return type). This makes some common use-cases with makeVisitor nicer to look at.

[scott.linder]

Implement explicit return version of llvm::visit

When the common return type of the visitor is ambiguous it is useful to be able
to specify a type to coerce the result to. This implements the equivalent
std::visit addition in C++20.

llvm/include/llvm/ADT/IntrusiveVariant.h

+//===- IntrusiveVariant.h - Compact type safe union -------------*- 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file provides IntrusiveVariant, a class template modeled in the spirit
+// of std::variant, but leveraging the "common initial sequence" rule for union
+// members to store the runtime tag at the beginning of the IntrusiveVariant's
+// alternative types, allowing for it to be packed more efficiently into bits
+// that would otherwise be used for padding.
+//
+// However, this requires several restrictions be placed on valid alternative
+// types. All alternative types of an IntrusiveVariant must:
+//
+//  * Be standard-layout. This implies (among other things):
+//    * All non-static data members must have the same access control.
+//    * All non-static data members must be declared in only one class in the
+//      inheritence hierarchy.
+//    * No virtual methods.
+//  * Begin their class definition by invoking the
+//    DECLARE_INTRUSIVE_ALTERNATIVE macro. This declares a member named
+//    `IntrusiveVariantTagMember` which must not be referenced outside of the
+//    implementation of IntrusiveVariant, and declares some `friend` types to
+//    make the tag accessible to the implementation.
+//
+// Additionally, some features were omitted that are present in the C++17
+// std::variant to keep the code simpler:
+//
+//  * All alternative types must be trivially-destructible.
+//  * All copy/move constructors and assignment operators for the variant are
+//    disabled if any type is not trivially-constructible and/or
+//    trivially-copyable, respectively.
+//  * All alternative types must be unique, and cannot be referred to by index.
+//  * No equivalent to std::monostate. An instantiation must have at least
+//    IntrusiveVariant::MinNumberOfAlternatives alternatives.
+//
+// If a use case for the above materializes these can always be added
+// retroactively.
+//
+// Example:
+//
+//  class AltInt {
+//    DECLARE_INTRUSIVE_ALTERNATIVE
+//    int Int;
+//
+//  public:
+//    AltInt() : Int(0) {}
+//    AltInt(int Int) : Int(Int) {}
+//    int getInt() const { return Int; }
+//    void setInt(int Int) { this->Int = Int; }
+//  };
+//
+//  class AltDouble {
+//    DECLARE_INTRUSIVE_ALTERNATIVE
+//    double Double;
+//
+//  public:
+//    AltDouble(double Double) : Double(Double) {}
+//    double getDouble() const { return Double; }
+//    void setDouble(double Double) { this->Double = Double; }
+//  };
+//
+//  class AltComplexInt {
+//    DECLARE_INTRUSIVE_ALTERNATIVE
+//    int Real;
+//    int Imag;
+//
+//  public:
+//    AltComplexInt(int Real, int Imag) : Real(Real), Imag(Imag) {}
+//    int getReal() const { return Real; }
+//    void setReal(int Real) { this->Real = Real; }
+//    int getImag() const { return Imag; }
+//    void setImag(int Imag) { this->Imag = Imag; }
+//  };
+//
+//  TEST(VariantTest, HeaderExample) {
+//    using MyVariant = IntrusiveVariant<AltInt, AltDouble, AltComplexInt>;
+//
+//    MyVariant DefaultConstructedVariant;
+//    ASSERT_TRUE(DefaultConstructedVariant.holdsAlternative<AltInt>());
+//    ASSERT_EQ(DefaultConstructedVariant.get<AltInt>().getInt(), 0);
+//    MyVariant Variant{in_place_type<AltComplexInt>, 4, 2};
+//    ASSERT_TRUE(Variant.holdsAlternative<AltComplexInt>());
+//    int NonSense = visit(
+//        makeVisitor(
+//            [](AltInt &AI) { return AI.getInt(); },
+//            [](AltDouble &AD) { return static_cast<int>(AD.getDouble()); },
+//            [](AltComplexInt &ACI) { return ACI.getReal() + ACI.getImag(); }),
+//        Variant);
+//    ASSERT_EQ(NonSense, 6);
+//    Variant.emplace<AltDouble>(2.0);
+//    ASSERT_TRUE(Variant.holdsAlternative<AltDouble>());
+//    Variant.get<AltDouble>().setDouble(3.0);
+//    AltDouble AD = Variant.get<AltDouble>();
+//    double D = AD.getDouble();
+//    ASSERT_EQ(D, 3.0);
+//    Variant.emplace<AltComplexInt>(4, 5);
+//    ASSERT_EQ(Variant.get<AltComplexInt>().getReal(), 4);
+//    ASSERT_EQ(Variant.get<AltComplexInt>().getImag(), 5);
+//  }
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_INTRUSIVEVARIANT_H
+#define LLVM_ADT_INTRUSIVEVARIANT_H
+
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/VariantTraits.h"
+#include "llvm/Support/ErrorHandling.h"
+#include <cstdint>
+#include <type_traits>
+#include <utility>
+
+namespace llvm {
+
+template <typename... Ts> class IntrusiveVariant;
+
+/// Helper to get the number of alternative types of a (possibly cv-qualified)
+/// IntrusiveVariant type as a constexpr. See std::variant_size.
+template <typename T>
+struct IntrusiveVariantSize : IntrusiveVariantSize<std::remove_cv_t<T>> {};
+template <typename... Ts>
+struct IntrusiveVariantSize<IntrusiveVariant<Ts...>>
+    : std::integral_constant<size_t, sizeof...(Ts)> {};
+
+/// Simple value type which must be the first member of all alternative types
+/// of an IntrusiveVariant. See DECLARE_INTRUSIVE_ALTERNATIVE.
+///
+/// The internal implementation assumes this is layout-compatible with the
+/// "common initial sequence" of all alternative types contained in the private
+/// union of the IntrusiveVariant.
+struct IntrusiveVariantTag {
+  uint8_t Index = std::numeric_limits<uint8_t>::max();
+  IntrusiveVariantTag() {}
+  IntrusiveVariantTag(uint8_t Index) : Index(Index) {}
+};
+
+/// A helper macro to add the declarations needed to use a type as an
+/// alternative for IntrusiveVariant. Must be the first declaration of the
+/// class.
+#define DECLARE_INTRUSIVE_ALTERNATIVE                                          \
+  ::llvm::IntrusiveVariantTag IntrusiveVariantTagMember;                       \
+  template <typename...> friend class ::llvm::IntrusiveVariant;                \
+  template <size_t, typename, typename...>                                     \
+  friend union ::llvm::detail::UnionImpl;
+
+namespace detail {
+// This struct is used to access the intrusive tag of the alternative types.
+//
+// All such types must be have an initial sequence which is layout-compatible
+// with this struct or the access causes undefined behavior.
+struct CommonInitialSequenceT {
+  IntrusiveVariantTag Tag;
+};
+
+// The inner implementation of the "type safe union". Members are only
+// accessible directly via an Index, so IntrusiveVariant must use indexOf to
+// convert a pair of T and Ts... into an index.
+//
+// Effectively implemented as a "linked list" of recursively defined union
+// templates. This is the recursive portion of the definition.
+//
+// We use in_place_index_t here both to disambiguate the constructor and to make
+// defining the overload set for getMember more natural.
+template <size_t Index, typename HeadT, typename... TailTs> union UnionImpl {
+  using TailT = UnionImpl<Index + 1, TailTs...>;
+  HeadT Head;
+  TailT Tail;
+  HeadT &getMember(in_place_index_t<Index>) { return Head; }
+  const HeadT &getMember(in_place_index_t<Index>) const { return Head; }
+  template <size_t I> decltype(auto) getMember(in_place_index_t<I>) {
+    return Tail.getMember(in_place_index<I>);
+  }
+  template <size_t I> decltype(auto) getMember(in_place_index_t<I>) const {
+    return Tail.getMember(in_place_index<I>);
+  }
+  template <typename... ArgTs>
+  UnionImpl(in_place_index_t<Index>, ArgTs &&...Args) {
+    new (&Head) HeadT(std::forward<ArgTs>(Args)...);
+    Head.IntrusiveVariantTagMember.Index = Index;
+  }
+  template <size_t I, typename... ArgTs>
+  UnionImpl(in_place_index_t<I>, ArgTs &&...Args) {
+    new (&Tail) TailT(in_place_index_t<I>{}, std::forward<ArgTs>(Args)...);
+  }
+  UnionImpl(const UnionImpl &) = default;
+  UnionImpl(UnionImpl &&) = default;
+  UnionImpl &operator=(const UnionImpl &) = default;
+  UnionImpl &operator=(UnionImpl &&) = default;
+  // This is safe, assuming the member types are all trivially destructible.
+  ~UnionImpl() = default;
+};
+// The base case for the above, i.e. when the tail pack is empty. This is the
+// "(cons head nil)" of the linked list.
+template <size_t Index, typename HeadT> union UnionImpl<Index, HeadT> {
+  HeadT Head;
+  HeadT &getMember(in_place_index_t<Index>) { return Head; }
+  const HeadT &getMember(in_place_index_t<Index>) const { return Head; }
+  template <typename... ArgTs>
+  UnionImpl(in_place_index_t<Index>, ArgTs &&...Args) {
+    new (&Head) HeadT(std::forward<ArgTs>(Args)...);
+    Head.IntrusiveVariantTagMember.Index = Index;
+  }
+  UnionImpl(const UnionImpl &) = default;
+  UnionImpl(UnionImpl &&) = default;
+  UnionImpl &operator=(const UnionImpl &) = default;
+  UnionImpl &operator=(UnionImpl &&) = default;
+  // This is safe, assuming the member types are all trivially destructible.
+  ~UnionImpl() = default;
+};
+} // end namespace detail
+
+template <typename... Ts> struct VariantTraits<IntrusiveVariant<Ts...>> {
+  static constexpr size_t size() { return sizeof...(Ts); }
+  static constexpr size_t index(const IntrusiveVariant<Ts...> &Variant) {
+    return Variant.index();
+  }
+  template <size_t Index, typename VariantT = IntrusiveVariant<Ts...>>
+  static constexpr decltype(auto) get(VariantT &&Variant) {
+    return std::forward<VariantT>(Variant)
+        .template get<TypeAtIndex<Index, Ts...>>();
+  }
+};
+
+/// A class template modeled in the spirit of std::variant, but leveraging the
+/// "common initial sequence" rule for union members to store the runtime tag
+/// at the beginning of each variant alternative itself, allowing for it to be
+/// packed more efficiently into bits that would otherwise be used for padding.
+template <typename... Ts> class IntrusiveVariant {
+public:
+  /// The static minimum number of alternative types supported for an
+  /// instantiation of IntrusiveVariant.
+  static constexpr size_t MinNumberOfAlternatives = 1;
+
+private:
+  static_assert(llvm::conjunction<std::is_standard_layout<Ts>...>::value,
+                "IntrusiveVariant alternatives must be standard-layout.");
+  static_assert(
+      llvm::conjunction<std::is_trivially_destructible<Ts>...>::value,
+      "IntrusiveVariant alternatives must be trivially-destructible.");
+  template <typename... Us> static constexpr bool tagIsFirstMember() {
+    constexpr bool IsFirstMember[] = {
+        !offsetof(Us, IntrusiveVariantTagMember)...};
+    for (size_t I = 0; I < sizeof...(Us); ++I)
+      if (!IsFirstMember[I])
+        return false;
+    return true;
+  }
+  static_assert(
+      tagIsFirstMember<Ts...>() &&
+          llvm::conjunction<
+              std::is_same<IntrusiveVariantTag Ts::*,
+                           decltype(&Ts::IntrusiveVariantTagMember)>...>::value,
+      "IntrusiveVariant alternatives' class definition must begin with "
+      "DECLARE_INTRUSIVE_ALTERNATIVE");
+  static_assert(
+      TypesAreDistinct<Ts...>{},
+      "Repeated alternative types in IntrusiveVariant are not allowed.");
+
+  // Alias for the UnionImpl of this IntrusiveVariant.
+  using UnionT = detail::UnionImpl<0, Ts...>;
+  // Helper to get the in_place_index_t for T in Ts...
+  template <typename T>
+  using InPlaceIndexT = in_place_index_t<FirstIndexOfType<T, Ts...>{}>;
+  // Helper to check if a type is in the set Ts...
+  template <typename T> using IsAlternativeType = llvm::is_one_of<T, Ts...>;
+
+  // The only data member of IntrusiveVariant, meaning the variant is the same
+  // size and has the same alignment requirements as the union of all of its
+  // alternative types.
+  union {
+    detail::CommonInitialSequenceT CommonInitialSequence;
+    UnionT Union;
+  };
+
+  // Convenience methods to get the union member for an alternative type T.
+  template <typename T> T &getAlt() {
+    return Union.getMember(InPlaceIndexT<T>{});
+  }
+  template <typename T> const T &getAlt() const {
+    return Union.getMember(InPlaceIndexT<T>{});
+  }
+
+public:
+  /// A default constructed IntrusiveVariant holds a default constructed value
+  /// of its first alternative. Only enabled if the first alternative has a
+  /// default constructor.
+  template <int B = std::is_default_constructible<TypeAtIndex<0, Ts...>>{},
+            typename std::enable_if_t<B, int> = 0>
+  constexpr IntrusiveVariant() : Union(in_place_index_t<0>{}) {}
+  /// The forwarding constructor requires a disambiguation tag
+  /// in_place_type_t<T>, and creates an IntrusiveVariant holding the
+  /// alternative T constructed with the constructor arguments Args...
+  template <typename T, std::enable_if_t<IsAlternativeType<T>{}, int> = 0,
+            typename... ArgTs>
+  explicit constexpr IntrusiveVariant(in_place_type_t<T>, ArgTs &&...Args)
+      : Union(InPlaceIndexT<T>{}, std::forward<ArgTs>(Args)...) {}
+  /// Converting constructor from alternative types.
+  template <typename T, std::enable_if_t<IsAlternativeType<T>{}, int> = 0>
+  constexpr IntrusiveVariant(T &&Alt)
+      : Union(InPlaceIndexT<T>{}, std::forward<T>(Alt)) {}
+  IntrusiveVariant(const IntrusiveVariant &) = default;
+  IntrusiveVariant(IntrusiveVariant &&) = default;
+  ~IntrusiveVariant() = default;
+  IntrusiveVariant &operator=(const IntrusiveVariant &) = default;
+  IntrusiveVariant &operator=(IntrusiveVariant &&) = default;
+  /// Replaces the held value with a new value of alternative type T in-place,
+  /// constructing the new value with constructor arguments Args...
+  ///
+  /// Returns the newly constructed alternative type value.
+  template <typename T, typename... ArgTs> T &emplace(ArgTs &&...Args) {
+    new (&Union) UnionT(InPlaceIndexT<T>{}, std::forward<ArgTs>(Args)...);
+    return Union.getMember(InPlaceIndexT<T>{});
+  }
+  /// Returns the index of the alternative type held by this variant.
+  size_t index() const { return CommonInitialSequence.Tag.Index; }
+  /// Check if this variant holds a value of the given alternative type T.
+  template <class T> constexpr bool holdsAlternative() const {
+    return index() == FirstIndexOfType<T, Ts...>();
+  }
+  /// Reads the value of alternative type T.
+  ///
+  /// Behavior undefined if this does not hold a value of alternative type T.
+  template <class T> constexpr T &get() {
+    assert(holdsAlternative<T>());
+    return getAlt<T>();
+  }
+  /// Reads the value of alternative type T.
+  ///
+  /// Behavior undefined if this does not hold a value of alternative type T.
+  template <class T> constexpr const T &get() const {
+    assert(holdsAlternative<T>());
+    return getAlt<T>();
+  }
+  /// Obtains a pointer to the value of alternative type T if this holds a
+  /// value of alternative type T. Otherwise, returns nullptr.
+  template <class T> constexpr T *getIf() {
+    if (holdsAlternative<T>())
+      return &getAlt<T>();
+    return nullptr;
+  }
+  /// Obtains a pointer to the value of alternative type T if this holds a
+  /// value of alternative type T. Otherwise, returns nullptr.
+  template <class T> constexpr const T *getIf() const {
+    if (holdsAlternative<T>())
+      return &getAlt<T>();
+    return nullptr;
+  }
+
+  /// Equality operator.
+  ///
+  /// The alternative types held by LHS and RHS are T and U, respectively; then:
+  ///
+  /// If T != U, returns false.
+  /// Otherwise, returns LHS.get<T>() == RHS.get<U>().
+  friend constexpr bool operator==(const IntrusiveVariant<Ts...> &LHS,
+                                   const IntrusiveVariant<Ts...> &RHS) {
+    if (LHS.index() != RHS.index())
+      return false;
+    return visitSameAlternative(std::equal_to<>{}, LHS, RHS);
+  }
+
+  /// Inequality operator.
+  ///
+  /// The alternative types held by LHS and RHS are T and U, respectively; then:
+  ///
+  /// If T != U, returns true.
+  /// Otherwise, returns LHS.get<T>() != RHS.get<U>().
+  friend constexpr bool operator!=(const IntrusiveVariant<Ts...> &LHS,
+                                   const IntrusiveVariant<Ts...> &RHS) {
+    if (LHS.index() != RHS.index())
+      return true;
+    return visitSameAlternative(std::not_equal_to<>{}, LHS, RHS);
+  }
+
+  /// Less-than operator.
+  ///
+  /// The alternative types held by LHS and RHS are T and U, respectively; then:
+  ///
+  /// If T precedes U in Ts..., returns true.
+  /// If U precedes T in Ts..., returns false.
+  /// Otherwise, returns LHS.get<T>() < RHS.get<U>().
+  friend constexpr bool operator<(const IntrusiveVariant<Ts...> &LHS,
+                                  const IntrusiveVariant<Ts...> &RHS) {
+    if (LHS.index() < RHS.index())
+      return true;
+    if (LHS.index() > RHS.index())
+      return false;
+    return visitSameAlternative(std::less<>{}, LHS, RHS);
+  }
+
+  /// Greater-than operator.
+  ///
+  /// The alternative types held by LHS and RHS are T and U, respectively; then:
+  ///
+  /// If T precedes U in Ts..., returns false.
+  /// If U precedes T in Ts..., returns true.
+  /// Otherwise, returns LHS.get<T>() > RHS.get<U>().
+  friend constexpr bool operator>(const IntrusiveVariant<Ts...> &LHS,
+                                  const IntrusiveVariant<Ts...> &RHS) {
+    if (LHS.index() < RHS.index())
+      return false;
+    if (LHS.index() > RHS.index())
+      return true;
+    return visitSameAlternative(std::greater<>{}, LHS, RHS);
+  }
+
+  /// Less-equal operator.
+  ///
+  /// The alternative types held by LHS and RHS are T and U, respectively; then:
+  ///
+  /// If T precedes U in Ts..., returns true.
+  /// If U precedes T in Ts..., returns false.
+  /// Otherwise, returns LHS.get<T>() <= RHS.get<U>().
+  friend constexpr bool operator<=(const IntrusiveVariant<Ts...> &LHS,
+                                   const IntrusiveVariant<Ts...> &RHS) {
+    if (LHS.index() < RHS.index())
+      return true;
+    if (LHS.index() > RHS.index())
+      return false;
+    return visitSameAlternative(std::less_equal<>{}, LHS, RHS);
+  }
+
+  /// Greater-equal operator.
+  ///
+  /// The alternative types held by LHS and RHS are T and U, respectively; then:
+  ///
+  /// If T precedes U in Ts..., returns false.
+  /// If U precedes T in Ts..., returns true.
+  /// Otherwise, returns LHS.get<T>() >= RHS.get<U>().
+  friend constexpr bool operator>=(const IntrusiveVariant<Ts...> &LHS,
+                                   const IntrusiveVariant<Ts...> &RHS) {
+    if (LHS.index() < RHS.index())
+      return false;
+    if (LHS.index() > RHS.index())
+      return true;
+    return visitSameAlternative(std::greater_equal<>{}, LHS, RHS);
+  }
+
+  /// Enabled if all alternative types overload hash_value.
+  friend hash_code hash_value(const IntrusiveVariant &IV) {
+    return visit(
+        [&](auto &&Alt) { return hash_combine(IV.index(), hash_value(Alt)); },
+        IV);
+  }
+};
+
+} // end namespace llvm
+
+#endif // LLVM_ADT_INTRUSIVEVARIANT_H

llvm/include/llvm/ADT/STLForwardCompat.h

 // These should be replaced with their STL counterparts as the C++ version LLVM
 // is compiled with is updated.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_STLFORWARDCOMPAT_H
 #define LLVM_ADT_STLFORWARDCOMPAT_H
 
+#include <array>
 #include <type_traits>
 
 namespace llvm {
 
 //===----------------------------------------------------------------------===//
+//     Features from C++20
+//===----------------------------------------------------------------------===//
+
+template <typename T>
+struct remove_cvref // NOLINT(readability-identifier-naming)
+{
+  using type = std::remove_cv_t<std::remove_reference_t<T>>;
+};
+
+template <typename T>
+using remove_cvref_t // NOLINT(readability-identifier-naming)
+    = typename llvm::remove_cvref<T>::type;
+
+template <typename T>
+struct type_identity // NOLINT(readability-identifier-naming)
+{
+  using type = T;
+};
+
+//===----------------------------------------------------------------------===//
 //     Features from C++17
 //===----------------------------------------------------------------------===//
 
 template <typename T>
 struct negation // NOLINT(readability-identifier-naming)
     : std::integral_constant<bool, !bool(T::value)> {};
 
 template <typename...>

 /// \warning This must not be odr-used, as it cannot be made \c inline in C++14.
 constexpr in_place_t in_place; // NOLINT(readability-identifier-naming)
 
 template <typename T>
 struct in_place_type_t // NOLINT(readability-identifier-naming)
 {
   explicit in_place_type_t() = default;
 };
+/// \warning This must not be odr-used, as it cannot be made \c inline in C++14.
+template <typename T>
+constexpr in_place_type_t<T>
+    in_place_type; // NOLINT(readability-identifier-naming)
 
 template <std::size_t I>
 struct in_place_index_t // NOLINT(readability-identifier-naming)
 {
   explicit in_place_index_t() = default;
 };
+/// \warning This must not be odr-used, as it cannot be made \c inline in C++14.
+template <std::size_t I>
+constexpr in_place_index_t<I>
+    in_place_index; // NOLINT(readability-identifier-naming)
 
-//===----------------------------------------------------------------------===//
-//     Features from C++20
-//===----------------------------------------------------------------------===//
-
-template <typename T>
-struct remove_cvref // NOLINT(readability-identifier-naming)
-{
-  using type = std::remove_cv_t<std::remove_reference_t<T>>;
-};
-
-template <typename T>
-using remove_cvref_t // NOLINT(readability-identifier-naming)
-    = typename llvm::remove_cvref<T>::type;
+/// Implementation of std::experimental::make_array. Should be deleted in favor
+/// of the C++17 deduction guide for std::array.
+template <typename ExplicitT = void, typename... ArgTs>
+static constexpr auto
+make_array(ArgTs &&...Args) // NOLINT(readability-identifier-naming)
+    -> std::array<typename std::conditional_t<std::is_same<ExplicitT, void>{},
+                                              std::common_type<ArgTs...>,
+                                              type_identity<ExplicitT>>::type,
+                  sizeof...(ArgTs)> {
+  return {std::forward<ArgTs>(Args)...};
+}
 
 } // namespace llvm
 
 #endif // LLVM_ADT_STLFORWARDCOMPAT_H

llvm/include/llvm/ADT/VariantTraits.h

+//===- VariantTraits.h - Common interfaces for variant-like types --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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains common interfaces for variant-like types.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/STLExtras.h"
+
+#ifndef LLVM_ADT_VARIANTTRAITS_H
+#define LLVM_ADT_VARIANTTRAITS_H
+
+namespace llvm {
+
+/// Trait type which can be specialized over std::variant-like types to provide
+/// the minimum interface needed to share the implementation of llvm::visit and
+/// llvm::visitSameAlternative.
+template <typename VariantT> struct VariantTraits {
+  // // Returns the number of alternative types of VariantT.
+  // static constexpr size_t size();
+  //
+  // // Returns the index of the current alternative type of Variant.
+  // static constexpr size_t index(const VariantT &Variant);
+  //
+  // // Gets the alternative type at Index.
+  // template <size_t Index, typename VariantT = VariantT>
+  // static constexpr decltype(auto) get(VariantT &&Variant);
+};
+
+namespace variant_traits_detail {
+
+template <typename T> using Traits = struct VariantTraits<remove_cvref_t<T>>;
+
+template <typename T> struct HasTraits {
+  using Absent = char;
+  using Present = long;
+  template <typename U> static Absent size(...);
+  template <typename U> static Present size(SameType<size_t (*)(), &U::size> *);
+  template <typename U> static Absent index(...);
+  template <typename U>
+  static Present
+  index(SameType<size_t (*)(const remove_cvref_t<T> &), &U::index> *);
+  template <typename U> static Absent get(...);
+  template <typename U, typename R>
+  static Present get(SameType<R (*)(remove_cvref_t<T> &&), &U::get> *);
+
+  static bool const value = // NOLINT(readability-identifier-naming)
+      sizeof(size<Traits<T>>(nullptr)) == sizeof(Present) &&
+      sizeof(index<Traits<T>>(nullptr)) == sizeof(Present) &&
+      sizeof(get<Traits<T>>(nullptr) == sizeof(Present));
+};
+
+template <typename HeadT, typename... TailTs>
+struct AreSame : conjunction<std::is_same<HeadT, TailTs>...> {};
+
+template <typename... ThunkTs, std::enable_if_t<AreSame<ThunkTs...>{}, int> = 0>
+static constexpr auto makeThunkArray(ThunkTs &&...Thunks) {
+  return make_array(std::forward<ThunkTs>(Thunks)...);
+}
+
+template <size_t Index, typename VisitorT, typename... VariantTs>
+static constexpr decltype(auto)
+thunkForSameAlternative(VisitorT &&Visitor, VariantTs &&...Variants) {
+  return std::forward<VisitorT>(Visitor)(Traits<VariantTs>::template get<Index>(
+      std::forward<VariantTs>(Variants))...);
+}
+
+template <size_t Index, typename VisitorT, typename... VariantTs>
+static constexpr auto makeThunkForSameAlternative() {
+  return thunkForSameAlternative<Index, VisitorT, VariantTs...>;
+}
+
+template <typename VisitorT, typename HeadVariantT, typename... TailVariantTs,
+          size_t... Indexes>
+static constexpr auto
+visitSameAlternativeImpl(size_t Index, std::index_sequence<Indexes...>,
+                         VisitorT &&Visitor, HeadVariantT &&HeadVariant,
+                         TailVariantTs &&...TailVariants) {
+  constexpr auto Thunks = makeThunkArray(
+      makeThunkForSameAlternative<Indexes, VisitorT, HeadVariantT,
+                                  TailVariantTs...>()...);
+  return Thunks[Index](std::forward<VisitorT>(Visitor),
+                       std::forward<HeadVariantT>(HeadVariant),
+                       std::forward<TailVariantTs>(TailVariants)...);
+}
+
+template <size_t... Indexes> struct Thunk {
+  template <typename VisitorT, typename... VariantTs>
+  inline static constexpr decltype(auto) thunk(VisitorT &&Visitor,
+                                               VariantTs &&...Variants) {
+    return std::forward<VisitorT>(Visitor)(
+        Traits<VariantTs>::template get<Indexes>(
+            std::forward<VariantTs>(Variants))...);
+  }
+
+  template <typename R, typename VisitorT, typename... VariantTs>
+  inline static constexpr R thunkR(VisitorT &&Visitor,
+                                   VariantTs &&...Variants) {
+    return std::forward<VisitorT>(Visitor)(
+        Traits<VariantTs>::template get<Indexes>(
+            std::forward<VariantTs>(Variants))...);
+  }
+};
+
+template <typename VisitorT, typename... VariantTs, size_t... Indexes>
+static constexpr auto makeThunkForSequence(std::index_sequence<Indexes...>) {
+  return Thunk<Indexes...>::template thunk<VisitorT, VariantTs...>;
+}
+
+template <typename R, typename VisitorT, typename... VariantTs,
+          size_t... Indexes>
+static constexpr auto makeThunkForSequenceR(std::index_sequence<Indexes...>) {
+  return Thunk<Indexes...>::template thunkR<R, VisitorT, VariantTs...>;
+}
+
+template <typename VisitorT, typename... VariantTs,
+          size_t... AccumulatedIndexes>
+static constexpr auto
+accumulateCartesianProductThunks(std::index_sequence<AccumulatedIndexes...>) {
+  return makeThunkForSequence<VisitorT, VariantTs...>(
+      std::index_sequence<AccumulatedIndexes...>{});
+}
+
+template <typename R, typename VisitorT, typename... VariantTs,
+          size_t... AccumulatedIndexes>
+static constexpr auto
+accumulateCartesianProductThunksR(std::index_sequence<AccumulatedIndexes...>) {
+  return makeThunkForSequenceR<R, VisitorT, VariantTs...>(
+      std::index_sequence<AccumulatedIndexes...>{});
+}
+
+template <typename VisitorT, typename... VariantTs,
+          size_t... AccumulatedIndexes, size_t... HeadIndexes,
+          typename... TailSequenceTs>
+static constexpr auto
+accumulateCartesianProductThunks(std::index_sequence<AccumulatedIndexes...>,
+                                 std::index_sequence<HeadIndexes...>,
+                                 TailSequenceTs... Tail) {
+  return makeThunkArray(
+      accumulateCartesianProductThunks<VisitorT, VariantTs...>(
+          std::index_sequence<AccumulatedIndexes..., HeadIndexes>{},
+          Tail...)...);
+}
+
+template <typename R, typename VisitorT, typename... VariantTs,
+          size_t... AccumulatedIndexes, size_t... HeadIndexes,
+          typename... TailSequenceTs>
+static constexpr auto
+accumulateCartesianProductThunksR(std::index_sequence<AccumulatedIndexes...>,
+                                  std::index_sequence<HeadIndexes...>,
+                                  TailSequenceTs... Tail) {
+  return makeThunkArray(
+      accumulateCartesianProductThunksR<R, VisitorT, VariantTs...>(
+          std::index_sequence<AccumulatedIndexes..., HeadIndexes>{},
+          Tail...)...);
+}
+
+template <typename VisitorT, typename... VariantTs>
+static constexpr auto makeThunkMatrix() {
+  return accumulateCartesianProductThunks<VisitorT, VariantTs...>(
+      std::index_sequence<>{},
+      std::make_index_sequence<Traits<VariantTs>::size()>{}...);
+}
+
+template <typename R, typename VisitorT, typename... VariantTs>
+static constexpr auto makeThunkMatrixR() {
+  return accumulateCartesianProductThunksR<R, VisitorT, VariantTs...>(
+      std::index_sequence<>{},
+      std::make_index_sequence<Traits<VariantTs>::size()>{}...);
+}
+
+template <typename ThunkT>
+static constexpr const ThunkT &indexThunkMatrix(const ThunkT &Thunk) {
+  return Thunk;
+}
+
+template <typename ThunkMatrixT, typename... TailIndexTs>
+static constexpr auto &&indexThunkMatrix(const ThunkMatrixT &ThunkMatrix,
+                                         size_t HeadIndex,
+                                         TailIndexTs... TailIndexes) {
+  return indexThunkMatrix(ThunkMatrix[HeadIndex], TailIndexes...);
+}
+
+} // namespace variant_traits_detail
+
+/// Invokes the provided Visitor using overload resolution based on the
+/// dynamic alternative type held in each Variant. See std::variant.
+///
+/// The return type is effectively
+/// decltype(Visitor(Variants.get<HeldAlternatives>()...)). This must be a
+/// valid expression of the same type and value category for every combination
+/// of alternative types of the variant types.
+template <
+    typename VisitorT, typename... VariantTs,
+    typename std::enable_if_t<
+        conjunction<variant_traits_detail::HasTraits<VariantTs>...>::value,
+        int> = 0>
+constexpr decltype(auto) visit(VisitorT &&Visitor, VariantTs &&...Variants) {
+  constexpr auto ThunkMatrix =
+      variant_traits_detail::makeThunkMatrix<VisitorT, VariantTs...>();
+  const auto &Thunk = variant_traits_detail::indexThunkMatrix(
+      ThunkMatrix, variant_traits_detail::Traits<VariantTs>::index(
+                       std::forward<VariantTs>(Variants))...);
+  return Thunk(std::forward<VisitorT>(Visitor),
+               std::forward<VariantTs>(Variants)...);
+}
+
+/// Invokes the provided Visitor using overload resolution based on the
+/// dynamic alternative type held in each Variant. See std::variant.
+///
+/// The return type is effectively
+/// decltype(Visitor(Variants.get<HeldAlternatives>()...)), implicity converted
+/// to R.
+template <
+    typename R, typename VisitorT, typename... VariantTs,
+    typename std::enable_if_t<
+        conjunction<variant_traits_detail::HasTraits<VariantTs>...>::value,
+        int> = 0>
+constexpr R visit(VisitorT &&Visitor, VariantTs &&...Variants) {
+  constexpr auto ThunkMatrix =
+      variant_traits_detail::makeThunkMatrixR<R, VisitorT, VariantTs...>();
+  const auto &Thunk = variant_traits_detail::indexThunkMatrix(
+      ThunkMatrix, variant_traits_detail::Traits<VariantTs>::index(
+                       std::forward<VariantTs>(Variants))...);
+  return Thunk(std::forward<VisitorT>(Visitor),
+               std::forward<VariantTs>(Variants)...);
+}
+
+/// Invokes the provided Visitor using overload resolution based on the dynamic
+/// alternative type held in each Variant, assuming the variants are all of the
+/// same type and hold the same dynamic alternative type.
+///
+/// \warning llvm::visit must be used instead when there is no guarantee that
+/// all variants currently hold the same alternative type. However, when such a
+/// guarantee can be made llvm::visitSameAlternative may reduce code bloat,
+/// especially for debug builds.
+///
+/// The return type is effectively
+/// decltype(Visitor(Variants.get<HeldAlternative>()...)). This must be a valid
+/// expression of the same type and value category for every alternative type
+/// of the variant type.
+template <
+    typename VisitorT, typename HeadVariantT, typename... TailVariantTs,
+    typename std::enable_if_t<
+        conjunction<variant_traits_detail::HasTraits<HeadVariantT>,
+                    variant_traits_detail::HasTraits<TailVariantTs>...>::value,
+        int> = 0>
+static constexpr decltype(auto)
+visitSameAlternative(VisitorT &&Visitor, HeadVariantT &&HeadVariant,
+                     TailVariantTs &&...TailVariants) {
+  static_assert(conjunction<std::is_same<remove_cvref_t<HeadVariantT>,
+                                         remove_cvref_t<TailVariantTs>>...>{},
+                "all variant arguments to visitSameAlternative must "
+                "be of the same type");
+  using Traits = variant_traits_detail::Traits<HeadVariantT>;
+#ifdef EXPENSIVE_CHECKS
+  size_t Index = Traits::index(std::forward<HeadVariantT>(HeadVariant));
+  for (auto &&V : {std::forward<TailVariantTs>(TailVariants)...})
+    assert(Traits::index(V) == Index &&
+           "all variant arguments to visitSameAlternative must have "
+           "the same index");
+#endif
+  return variant_traits_detail::visitSameAlternativeImpl(
+      Traits::index(std::forward<HeadVariantT>(HeadVariant)),
+      std::make_index_sequence<Traits::size()>{},
+      std::forward<VisitorT>(Visitor), std::forward<HeadVariantT>(HeadVariant),
+      std::forward<TailVariantTs>(TailVariants)...);
+}
+
+} // namespace llvm
+
+#endif // LLVM_ADT_VARIANTTRAITS_H

llvm/unittests/ADT/CMakeLists.txt

add_llvm_unittest(ADTTests
   IListSentinelTest.cpp
   IListTest.cpp
   ImmutableListTest.cpp
   ImmutableMapTest.cpp
   ImmutableSetTest.cpp
   IntEqClassesTest.cpp
   IntervalMapTest.cpp
   IntrusiveRefCntPtrTest.cpp
+  IntrusiveVariantTest.cpp
   IteratorTest.cpp
   MappedIteratorTest.cpp
   MapVectorTest.cpp
   OptionalTest.cpp
   PackedVectorTest.cpp
   PointerEmbeddedIntTest.cpp
   PointerIntPairTest.cpp
   PointerSumTypeTest.cpp

llvm/unittests/ADT/IntrusiveVariantTest.cpp

+//===- llvm/unittest/Support/AnyTest.cpp - Any tests ---===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/IntrusiveVariant.h"
+#include "gtest/gtest.h"
+#include <cstdlib>
+
+using namespace llvm;
+
+namespace {
+
+class A {
+  DECLARE_INTRUSIVE_ALTERNATIVE
+};
+
+class B {
+  DECLARE_INTRUSIVE_ALTERNATIVE
+};
+
+TEST(IntrusiveVariantTest, SingleAlternative) { IntrusiveVariant<A> V; }
+
+TEST(IntrusiveVariantTest, ZeroArgConstructionAndAssignment) {
+  IntrusiveVariant<A, B> V;
+  ASSERT_TRUE(V.holdsAlternative<A>());
+  visit(makeVisitor([](A) {}, [](B) { FAIL(); }), V);
+  visit(makeVisitor([](B) { FAIL(); }, [](A) {}), V);
+  visit(makeVisitor([](A &) {}, [](B &) { FAIL(); }), V);
+  visit(makeVisitor([](A) {}, [](B &) { FAIL(); }), V);
+  visit(makeVisitor([](A &) {}, [](B) { FAIL(); }), V);
+  visit(makeVisitor([](auto &&) {}), V);
+
+  V.emplace<B>();
+  ASSERT_TRUE(V.holdsAlternative<B>());
+
+  IntrusiveVariant<A, B> W{V};
+  ASSERT_TRUE(W.holdsAlternative<B>());
+
+  const IntrusiveVariant<A, B> X{V};
+  ASSERT_TRUE(X.holdsAlternative<B>());
+}
+
+TEST(IntrusiveVariantTest, MustHaveSingleReturn) {
+  IntrusiveVariant<A, B> V;
+  visit<Optional<bool>>(
+      makeVisitor([](A) { return true; }, [](B) { return None; }), V);
+}
+
+template <typename T> class Alt {
+  DECLARE_INTRUSIVE_ALTERNATIVE
+  T Val;
+
+public:
+  Alt(T Val) : Val(Val) {}
+  T getVal() const { return Val; }
+  friend bool operator==(const Alt &LHS, const Alt &RHS) {
+    return LHS.getVal() == RHS.getVal();
+  }
+  friend bool operator!=(const Alt &LHS, const Alt &RHS) {
+    return LHS.getVal() != RHS.getVal();
+  }
+  friend bool operator<(const Alt &LHS, const Alt &RHS) {
+    return LHS.getVal() < RHS.getVal();
+  }
+  friend bool operator>(const Alt &LHS, const Alt &RHS) {
+    return LHS.getVal() > RHS.getVal();
+  }
+  friend bool operator<=(const Alt &LHS, const Alt &RHS) {
+    return LHS.getVal() <= RHS.getVal();
+  }
+  friend bool operator>=(const Alt &LHS, const Alt &RHS) {
+    return LHS.getVal() >= RHS.getVal();
+  }
+};
+using I = Alt<int>;
+using F = Alt<float>;
+using D = Alt<double>;
+
+TEST(IntrusiveVariantTest, ConstructionAndAssignment) {
+  IntrusiveVariant<I, F, D> V{in_place_type<F>, 2.0f};
+  visit(makeVisitor([](I) { FAIL(); }, [](F X) { EXPECT_EQ(X.getVal(), 2.0f); },
+                    [](D) { FAIL(); }),
+        V);
+  IntrusiveVariant<I, F, D> W{V};
+  visit(makeVisitor([](I) { FAIL(); }, [](F X) { EXPECT_EQ(X.getVal(), 2.0f); },
+                    [](D) { FAIL(); }),
+        W);
+  W.emplace<I>(42);
+  visit(makeVisitor([](I X) { EXPECT_EQ(X.getVal(), 42); }, [](F) { FAIL(); },
+                    [](D) { FAIL(); }),
+        W);
+  W = V;
+  visit(makeVisitor([](I) { FAIL(); }, [](F X) { EXPECT_EQ(X.getVal(), 2.0f); },
+                    [](D) { FAIL(); }),
+        W);
+}
+
+TEST(IntrusiveVariantTest, Comparison) {
+  IntrusiveVariant<I, F, D> V{in_place_type<I>, 1};
+  IntrusiveVariant<I, F, D> W{in_place_type<F>, 2.0f};
+  IntrusiveVariant<I, F, D> X{in_place_type<F>, 2.0f};
+  IntrusiveVariant<I, F, D> Y{in_place_type<F>, 3.0f};
+  IntrusiveVariant<I, F, D> Z{in_place_type<D>, 3.0};
+  EXPECT_NE(V, W);
+  EXPECT_LT(V, W);
+  EXPECT_LE(V, W);
+  EXPECT_GT(W, V);
+  EXPECT_GE(W, V);
+  EXPECT_EQ(W, X);
+  EXPECT_LE(W, X);
+  EXPECT_GE(W, X);
+  EXPECT_NE(W, Y);
+  EXPECT_NE(X, Y);
+  EXPECT_LT(X, Y);
+  EXPECT_LE(X, Y);
+  EXPECT_GT(Y, X);
+  EXPECT_GE(Y, X);
+  EXPECT_NE(Y, Z);
+  std::swap(X, Y);
+  EXPECT_EQ(W, Y);
+  EXPECT_NE(W, X);
+}
+
+TEST(IntrusiveVariantTest, IntrusiveVariantSize) {
+  constexpr auto One = IntrusiveVariantSize<IntrusiveVariant<I>>{};
+  EXPECT_EQ(One, 1u);
+  constexpr auto Two = IntrusiveVariantSize<IntrusiveVariant<I, F>>{};
+  EXPECT_EQ(Two, 2u);
+  constexpr auto Three = IntrusiveVariantSize<IntrusiveVariant<I, F, D>>{};
+  EXPECT_EQ(Three, 3u);
+}
+
+TEST(IntrusiveVariantTest, HoldsAlternative) {
+  IntrusiveVariant<I, F, D> V{in_place_type<D>, 2.0};
+  EXPECT_FALSE(V.holdsAlternative<I>());
+  EXPECT_FALSE(V.holdsAlternative<F>());
+  EXPECT_TRUE(V.holdsAlternative<D>());
+  V.emplace<I>(1);
+  EXPECT_TRUE(V.holdsAlternative<I>());
+  EXPECT_FALSE(V.holdsAlternative<F>());
+  EXPECT_FALSE(V.holdsAlternative<D>());
+  const IntrusiveVariant<I, F, D> C{in_place_type<F>, 2.0f};
+  EXPECT_FALSE(C.holdsAlternative<I>());
+  EXPECT_TRUE(C.holdsAlternative<F>());
+  EXPECT_FALSE(C.holdsAlternative<D>());
+}
+
+TEST(IntrusiveVariantTest, Get) {
+  IntrusiveVariant<I, F, D> V{in_place_type<D>, 2.0};
+  EXPECT_EQ(V.get<D>(), D{2.0});
+  EXPECT_EQ(V.get<D>(), *V.getIf<D>());
+  EXPECT_EQ(&V.get<D>(), V.getIf<D>());
+  V.emplace<I>(1);
+  EXPECT_EQ(V.get<I>(), I{1});
+  EXPECT_EQ(V.get<I>(), *V.getIf<I>());
+  EXPECT_EQ(&V.get<I>(), V.getIf<I>());
+  const IntrusiveVariant<I, F, D> C{in_place_type<D>, 2.0};
+  EXPECT_EQ(C.get<D>(), D{2.0});
+  EXPECT_EQ(C.get<D>(), *C.getIf<D>());
+  EXPECT_EQ(&C.get<D>(), C.getIf<D>());
+}
+
+TEST(IntrusiveVariantTest, GetIf) {
+  IntrusiveVariant<I, F, D> V{in_place_type<D>, 2.0};
+  EXPECT_EQ(V.getIf<I>(), nullptr);
+  EXPECT_EQ(V.getIf<F>(), nullptr);
+  EXPECT_NE(V.getIf<D>(), nullptr);
+  V.emplace<I>(1);
+  EXPECT_NE(V.getIf<I>(), nullptr);
+  EXPECT_EQ(V.getIf<F>(), nullptr);
+  EXPECT_EQ(V.getIf<D>(), nullptr);
+  const IntrusiveVariant<I, F, D> C{in_place_type<F>, 2.0f};
+  EXPECT_EQ(C.getIf<I>(), nullptr);
+  EXPECT_NE(C.getIf<F>(), nullptr);
+  EXPECT_EQ(C.getIf<D>(), nullptr);
+}
+
+struct IntA {
+  DECLARE_INTRUSIVE_ALTERNATIVE
+  int Val;
+  IntA(int Val) : Val(Val) {}
+  friend hash_code hash_value(const IntA &IA) { return hash_value(IA.Val); }
+};
+
+struct IntB {
+  DECLARE_INTRUSIVE_ALTERNATIVE
+  int Val;
+  IntB(int Val) : Val(Val) {}
+  friend hash_code hash_value(const IntB &IB) { return hash_value(IB.Val); }
+};
+
+TEST(IntrusiveVariantTest, HashValue) {
+  IntrusiveVariant<IntA, IntB> ATwo{in_place_type<IntA>, 2};
+  IntrusiveVariant<IntA, IntB> AThree{in_place_type<IntA>, 3};
+  IntrusiveVariant<IntA, IntB> BTwo{in_place_type<IntB>, 2};
+  EXPECT_EQ(hash_value(ATwo), hash_value(ATwo));
+  EXPECT_NE(hash_value(ATwo), hash_value(AThree));
+  EXPECT_NE(hash_value(ATwo), hash_value(BTwo));
+}
+
+class AltInt {
+  DECLARE_INTRUSIVE_ALTERNATIVE
+  int Int;
+
+public:
+  AltInt() : Int(0) {}
+  AltInt(int Int) : Int(Int) {}
+  int getInt() const { return Int; }
+  void setInt(int Int) { this->Int = Int; }
+};
+
+class AltDouble {
+  DECLARE_INTRUSIVE_ALTERNATIVE
+  double Double;
+
+public:
+  AltDouble(double Double) : Double(Double) {}
+  double getDouble() const { return Double; }
+  void setDouble(double Double) { this->Double = Double; }
+};
+
+class AltComplexInt {
+  DECLARE_INTRUSIVE_ALTERNATIVE
+  int Real;
+  int Imag;
+
+public:
+  AltComplexInt(int Real, int Imag) : Real(Real), Imag(Imag) {}
+  int getReal() const { return Real; }
+  void setReal(int Real) { this->Real = Real; }
+  int getImag() const { return Imag; }
+  void setImag(int Imag) { this->Imag = Imag; }
+};
+
+TEST(IntrusiveVariantTest, HeaderExample) {
+  using MyVariant = IntrusiveVariant<AltInt, AltDouble, AltComplexInt>;
+
+  MyVariant DefaultConstructedVariant;
+  ASSERT_TRUE(DefaultConstructedVariant.holdsAlternative<AltInt>());
+  ASSERT_EQ(DefaultConstructedVariant.get<AltInt>().getInt(), 0);
+  MyVariant Variant{in_place_type<AltComplexInt>, 4, 2};
+  ASSERT_TRUE(Variant.holdsAlternative<AltComplexInt>());
+  int NonSense = visit(
+      makeVisitor(
+          [](AltInt &AI) { return AI.getInt(); },
+          [](AltDouble &AD) { return static_cast<int>(AD.getDouble()); },
+          [](AltComplexInt &ACI) { return ACI.getReal() + ACI.getImag(); }),
+      Variant);
+  ASSERT_EQ(NonSense, 6);
+  Variant.emplace<AltDouble>(2.0);
+  ASSERT_TRUE(Variant.holdsAlternative<AltDouble>());
+  Variant.get<AltDouble>().setDouble(3.0);
+  AltDouble AD = Variant.get<AltDouble>();
+  double D = AD.getDouble();
+  ASSERT_EQ(D, 3.0);
+  Variant.emplace<AltComplexInt>(4, 5);
+  ASSERT_EQ(Variant.get<AltComplexInt>().getReal(), 4);
+  ASSERT_EQ(Variant.get<AltComplexInt>().getImag(), 5);
+}
+
+} // anonymous namespace

llvm/unittests/ADT/STLForwardCompatTest.cpp

TEST(STLForwardCompatTest, DisjunctionTest) {
   EXPECT_TRUE((llvm::disjunction<std::true_type, incomplete_type>::value));
   EXPECT_TRUE((llvm::disjunction<std::false_type, std::true_type>::value));
   EXPECT_TRUE((llvm::disjunction<std::true_type, std::false_type>::value));
   EXPECT_TRUE((llvm::disjunction<std::true_type, std::true_type>::value));
   EXPECT_TRUE((llvm::disjunction<std::true_type, std::true_type,
                                  std::true_type>::value));
 }
 
+TEST(STLForwardCompatTest, MakeArrayTest) {
+  ASSERT_EQ((llvm::make_array<int>()), (std::array<int, 0u>{}));
+  ASSERT_EQ((llvm::make_array<size_t>()), (std::array<size_t, 0u>{}));
+  ASSERT_EQ((llvm::make_array<size_t>(1u, 2u, 3u)),
+            (std::array<size_t, 3u>{1, 2, 3}));
+  ASSERT_EQ((llvm::make_array<size_t>(1u, 2u, 3u)),
+            (llvm::make_array(size_t(1), size_t(2u), size_t(3u))));
+  ASSERT_EQ((llvm::make_array(true, false, false, true)),
+            (std::array<bool, 4u>{true, false, false, true}));
+}
+
 template <typename T>
 class STLForwardCompatRemoveCVRefTest : public ::testing::Test {};
 
 using STLForwardCompatRemoveCVRefTestTypes = ::testing::Types<
     // clang-format off
     std::pair<int, int>,
     std::pair<int &, int>,
     std::pair<const int, int>,