Extensible LLVM RTTI

[lhames]

Summary

This patch extracts the RTTI part of llvm::ErrorInfo into its own class (RTTIExtends) so that it can be used in other non-error hierarchies, and makes it compatible with the existing LLVM RTTI function templates (isa, cast, dyn_cast, dyn_cast_or_null) by adding the classof method.

This system makes different trade-offs to the existing LLVM RTTI approach (described in https://llvm.org/docs/HowToSetUpLLVMStyleRTTI.html) and would be complementary to the existing system rather than replacing it. Specifically: the extensible scheme is slower than the existing scheme (requiring a virtual call per isa check), but it leaves hierarchies open for extension and is slightly easier to use (since it eliminates the enumeration and switch boilerplate).

I believe that extensible RTTI makes sense for the Error hierarchy (which is why it was originally developed there) and I speculate that it may be useful in other hierarchies (e.g. Object) where casting is expected to be rare and not performance sensitive. I don't have a use-case in tree yet and am in no rush for this to go in, but thought I would throw it up for discussion, and in case it is useful to anyone else.

[dblaikie]

Interesting idea - yeah, curious to hear how others feel about the tradeoff (non-closed, virtual call).

The virtual call could be removed, perhaps, by having the base class hold a non-static member void* and derived classes (possibly through CRTP - which could be used in the existing design too, maybe? to reduce boilerplate) could pass the address of their ID through to the base ctor to initialize that member.

[lhames]

The virtual call could be removed, perhaps, by having the base class hold a non-static member void*...

Oh that's clever. I hadn't thought of that. There is a space trade-off though as it would require one char per RTTI object (in addition to the current requirement of one BSS char per class).

My current thinking is that open hierarchies are primarily (perhaps only?) useful for types that use virtual methods already, and RTTI calls are likely to be rare / non-performance-sensitive for such types. If it were accepted, my advice was going to be "Use the new system if you know you need an open hierarchy, or you know you don't care about performance". E.g. libObject. (If it sounds surprising that Object should be an open hierarchy, consider Apple's text-based API files: We want them to present as symbolic files, but they're unlike any in-tree format. It seems reasonable that other users may have similarly quirky formats that they still might want to work with llvm-nm, etc.).

[dblaikie]

Support/ExtensibleRTTITest.cpp

21 ↗

(On Diff #119629)

These chars could be provided in the CRTP base, perhaps? Less boilerplate. (though this would mean they'd have linkonce linkage, rather than having strong external definitions - but I doubt that duplication in objects would be too painful?)

Could even be local to the RTTIExtends::classID function (& dynamicClassID would just call classID)

[chandlerc]

In D39111#902702, @lhames wrote:

The virtual call could be removed, perhaps, by having the base class hold a non-static member void*...

Oh that's clever. I hadn't thought of that. There is a space trade-off though as it would require one char per RTTI object (in addition to the current requirement of one BSS char per class).

I'm not sure... If there are other virtual functions, then there would need to be some other base class with that virtual interface? At that point, you get multiple inheritance, and it isn't clear this is a win.

This actually seems a bit hard to use interestingly with RTTIRoot and virtual methods.... Hmm...

Oh, I guess the pattern is that you have your base, abstract interface derive from RTTIRoot, and then you extend that abstract interface further using the CRTP RTTIExtends? I think having this spelled out a bit more in the comments would be helpful.

The interesting tradeoff here is that if the user is going to devirtualize their interface by using dyn_cast and isa, they might end up preferring a simpler mechanism using a data member in the base class because they wouldn't have a vptr. But if they *do* have a vptr, almost certainly want to use this to avoid growing the memory of the base class.

You could design this to be parameterizable and handle both cases, but not sure if you want to do that now or wait for a concrete use case...

My current thinking is that open hierarchies are primarily (perhaps only?) useful for types that use virtual methods already, and RTTI calls are likely to be rare / non-performance-sensitive for such types. If it were accepted, my advice was going to be "Use the new system if you know you need an open hierarchy, or you know you don't care about performance".

My preference would be to focus *only* on open vs. closed. Maybe something along the lines of: "If at all possible, prefer a closed hierarchy rather than an open one, and use <technique> as it is faster and <reasons>. However, if you need an open, extensible type system use <technique> but be aware of <performance implications>."

Support/ExtensibleRTTITest.cpp

21 ↗

(On Diff #119629)

Sadly, this will (I suspect) run into the non-conforming implementation of static data members of class templates on MSVC between DLLs. Specifically, the address of ID will be different between two DLLs. =[

I'm actually a bit hesitant with this entire thing as a consequence. We need to really clearly document the hard constraints on how this CRTP base is used as a consequence of this (you cannot use this as part of class templates unless you explicitly instantiate all specializations of them).

llvm/Support/ExtensibleRTTI.h

22 ↗

(On Diff #119629)

Stale comment referencing error info...

Actually, this type doesn't really make a lot of sense to me (see my larger comment above)

[lhames]

Oh, I guess the pattern is that you have your base, abstract interface derive from RTTIRoot, and then you extend that abstract interface further using the CRTP RTTIExtends? I think having this spelled out a bit more in the comments would be helpful.

Yep. More documentation is definitely required. I just wanted to sanity check the concept before I went to the trouble of writing it. :)

My preference would be to focus *only* on open vs. closed. Maybe something along the lines of: "If at all possible, prefer a closed hierarchy rather than an open one, and use <technique> as it is faster and <reasons>. However, if you need an open, extensible type system use <technique> but be aware of <performance implications>."

That seems reasonable.

Support/ExtensibleRTTITest.cpp

21 ↗

(On Diff #119629)

Sadly, this will (I suspect) run into the non-conforming implementation of static data members of class templates on MSVC between DLLs. Specifically, the address of ID will be different between two DLLs. =[

I'm not familiar with this. Is it only a problem for static data members on class templates, or does it apply to static members of ordinary classes too?

In this case MyBaseClass is an ordinary class, so I would have hoped it would be safe.

I had originally defined ID in the RTTIExtends class template so the user didn't have to write anything at all, but ran in to an issue (similar to the one you described) with MinGW, so abandoned that idea.

[chandlerc]

Support/ExtensibleRTTITest.cpp

21 ↗

(On Diff #119629)

Only an issue for static data members on class templates.

So, as long as the types providing the IDs are non-templates and you're getting the correct one's address via a virtual function call, this should work out fine IIRC. But moving them into the CRTP base class won't work. =/

[lhames]

Updated to add documentation, comments.

[lhames]

Swinging back around to this, as I have a concrete use-case now (allowing JIT clients to query MaterializationUnit types when deciding how to dispatch compiler invocations in the JIT).

[lhames]

Gentle ping.

[lhames]

Ping.

[chandlerc]

Sorry this completely fell off my radar. It is back on my radar, and I'll try to get to it in the next day or two.

[lhames]

Gentle ping. Work on JITLink bought me some time, but I'm starting to hit situations where I would like to use this again. ;)

[lhames]

@dblaikie, @chandlerc -- Any further thoughts on this one?

I'd like to get this in as we have some use cases in the JIT (e.g. querying and down casting to user defined MaterializationUnit types when dispatching JIT work). At the time these were future use cases, now they're current ones. :)

[dblaikie]

In D39111#1925642, @lhames wrote:

@dblaikie, @chandlerc -- Any further thoughts on this one?

I'd like Chandler to come back around on this, given the reservations he expressed, but not sure he'll get to it - so might have to just figure it out ourselves. I share some of those reservations (that'd be easy to misuse this & have code that doesn't work on Windows - people won't read the documentation & might write the broken template situation), but maybe less concerned than Chandler was.

I'd like to get this in as we have some use cases in the JIT (e.g. querying and down casting to user defined MaterializationUnit types when dispatching JIT work). At the time these were future use cases, now they're current ones. :)

Could you sketch up a user/use case to demonstrate the use (maybe a Kaleidoscope example?)?

[lhames]

In D39111#1928251, @dblaikie wrote:

In D39111#1925642, @lhames wrote:

@dblaikie, @chandlerc -- Any further thoughts on this one?

I'd like Chandler to come back around on this, given the reservations he expressed, but not sure he'll get to it - so might have to just figure it out ourselves. I share some of those reservations (that'd be easy to misuse this & have code that doesn't work on Windows - people won't read the documentation & might write the broken template situation), but maybe less concerned than Chandler was.

Were there reservations about windows related to this patch? This certainly came up with the original design of the RTTI for Error: ErrorInfo originally defined the ID member for you, which Chandler pointed out is unsafe on Windows. We solved that in the ErrorInfo case by requiring you to define the ID member in your own class, and RTTIExtends takes the same approach.

I'd like to get this in as we have some use cases in the JIT (e.g. querying and down casting to user defined MaterializationUnit types when dispatching JIT work). At the time these were future use cases, now they're current ones. :)

Could you sketch up a user/use case to demonstrate the use (maybe a Kaleidoscope example?)?

Here are some simplified versions of the two use cases I want to use straight away:

In LLJIT set up we want the object linking layer type to be detectable to simplify setup code. E.g.

auto J = ExitOnErr(LLJITBuilder().create());
if (auto *RTDyldLinkLayer = dyn_cast<RTDyldObjectLinkingLayer>(J->getObjLinkingLayer()))
  RTDyldLinkLayer->setProcessAllSections(...);
else if (auto *ObjLinkLayer = dyn_cast<ObjectLinkingLayer>(J->getObjLinkingLayer()))
  installObjLinkingLayerPlugins(*ObjLinkingLayer);

In the dispatcher we want to be able to inspect the dynamic type of MU to decide how to dispatch the work:

ES.setDispatchMaterialization([](JITDylib &JD, std::unique_ptr<MaterializationUnit> MU) {
  if (isa<SplattingMaterializationUnit>(*MU))
    MU->doMaterialize(JD); // Materialize splatting MUs in-place.
  else if (auto &IRMU = dyn_cast<IRMaterializationUnit>(*MU))
    dispatchIRMU(std::move(MU)); // Analyze IR and decide how to dispatch
  else
    CompileThreads->async([MU=std::move(MU), &JD]() {
      MU->doMaterialization(JD); // Otherwise default to materializing on background thread
    });
});

As soon as this lands I'll add an OrcV2Example project covering it. Stefan is also planning to use this in his ThinLtoJIT example.

[dblaikie]

In D39111#1929413, @lhames wrote:

In D39111#1928251, @dblaikie wrote:

In D39111#1925642, @lhames wrote:

@dblaikie, @chandlerc -- Any further thoughts on this one?

I'd like Chandler to come back around on this, given the reservations he expressed, but not sure he'll get to it - so might have to just figure it out ourselves. I share some of those reservations (that'd be easy to misuse this & have code that doesn't work on Windows - people won't read the documentation & might write the broken template situation), but maybe less concerned than Chandler was.

Were there reservations about windows related to this patch?

I think this bit amounts to "reservations because of Windows":

"Sadly, [using a CRTP base to provide the ID] will (I suspect) run into the non-conforming implementation of static data members of class templates on MSVC between DLLs. Specifically, the address of ID will be different between two DLLs. =[

I'm actually a bit hesitant with this entire thing as a consequence. We need to really clearly document the hard constraints on how this CRTP base is used as a consequence of this (you cannot use this as part of class templates unless you explicitly instantiate all specializations of them)."

This certainly came up with the original design of the RTTI for Error: ErrorInfo originally defined the ID member for you, which Chandler pointed out is unsafe on Windows. We solved that in the ErrorInfo case by requiring you to define the ID member in your own class, and RTTIExtends takes the same approach.

The existence of the ErrorInfo doing something similar (could it be ported to use this infrastructure, then?) does help justify this a bit, but I appreciate the concerns of generalizing this further.

I'd like to get this in as we have some use cases in the JIT (e.g. querying and down casting to user defined MaterializationUnit types when dispatching JIT work). At the time these were future use cases, now they're current ones. :)

Could you sketch up a user/use case to demonstrate the use (maybe a Kaleidoscope example?)?

Here are some simplified versions of the two use cases I want to use straight away:

In LLJIT set up we want the object linking layer type to be detectable to simplify setup code. E.g.

auto J = ExitOnErr(LLJITBuilder().create());
if (auto *RTDyldLinkLayer = dyn_cast<RTDyldObjectLinkingLayer>(J->getObjLinkingLayer()))
  RTDyldLinkLayer->setProcessAllSections(...);
else if (auto *ObjLinkLayer = dyn_cast<ObjectLinkingLayer>(J->getObjLinkingLayer()))
  installObjLinkingLayerPlugins(*ObjLinkingLayer);

This currently would vary by platform & some other things, such that it's a dynamic choice you want to check for?

But for a user-defined ObjLinkingLayer - the user would know which type they had used and could static_cast instead, yes?

I guess maybe that raises a thought: Is this about having an open hierarchy, where you can dyn_cast to specific pre-provided types, or necessarily to support dyn_casting to user-provided types too? Would a solution that only allows dyn_cast between LLVM-provided types be sufficient for your use cases? (yeah, I know it'd be weird & I could see not wanting to do that because of the awkward asymmetry, but trying to understand the problem space a bit further)

In the dispatcher we want to be able to inspect the dynamic type of MU to decide how to dispatch the work:

ES.setDispatchMaterialization([](JITDylib &JD, std::unique_ptr<MaterializationUnit> MU) {
  if (isa<SplattingMaterializationUnit>(*MU))
    MU->doMaterialize(JD); // Materialize splatting MUs in-place.
  else if (auto &IRMU = dyn_cast<IRMaterializationUnit>(*MU))
    dispatchIRMU(std::move(MU)); // Analyze IR and decide how to dispatch
  else
    CompileThreads->async([MU=std::move(MU), &JD]() {
      MU->doMaterialization(JD); // Otherwise default to materializing on background thread
    });
});

Same sort of question - I guess the LLVM version of this code would be closed, but users would provide their own kinds of MUs - to support those users using both their own custom ones and standard ones, do the users control the MUs, such that they could test for all the types of MUs they know they are using in their JIT. Yeah, that'd be a bit awkward to be "is it MyCustomMU3" ends up being "is it not an IRMU, not a <other LLVM-provided MU>, etc... then it must be a MyCustomMU of some kind, so then do a different pseudo RTTI test".

[lhames]

In D39111#1929571, @dblaikie wrote:

I think this bit amounts to "reservations because of Windows":

"Sadly, [using a CRTP base to provide the ID] will (I suspect) run into the non-conforming implementation of static data members of class templates on MSVC between DLLs. Specifically, the address of ID will be different between two DLLs. =["

I think this was Chandler responding to your suggestion that the ID be moved into the CRTP base, rather than to this patch. :)

"I'm actually a bit hesitant with this entire thing as a consequence. We need to really clearly document the hard constraints on how this CRTP base is used as a consequence of this (you cannot use this as part of class templates unless you explicitly instantiate all specializations of them)."

The "entire thing" presumably applies to this patch, but I think this just requires sufficient documentation. The rules are simple enough to convey:

1. Your class must provide a static char ID member (failure to do so will result in RTTI failures at runtime).

2. RTTIExtends should *only* be subclassed by classes, not class templates, due to Windows handling of ODR static data members.

If we wanted to preclude the problem with (1) we could switch to a traits class for supplying the ID, but we can't do much for (2) except document.

This certainly came up with the original design of the RTTI for Error: ErrorInfo originally defined the ID member for you, which Chandler pointed out is unsafe on Windows. We solved that in the ErrorInfo case by requiring you to define the ID member in your own class, and RTTIExtends takes the same approach.

The existence of the ErrorInfo doing something similar (could it be ported to use this infrastructure, then?)...

That's my plan: Replace ErrorInfo with RTTIExtends if this lands.

This currently would vary by platform & some other things, such that it's a dynamic choice you want to check for?

Yep. The idea is that the client shouldn't have to replicate the JIT's internal logic to intuit the layer type, since that internal logic is subject to change and casting to the wrong type could (in the worst case) fail quietly but disastrously. Since the client may be using a repackaged JIT that could mix in its own layer types / setup I would consider this a dynamic choice on an effectively open hierarchy.

I guess maybe that raises a thought: Is this about having an open hierarchy, where you can dyn_cast to specific pre-provided types, or necessarily to support dyn_casting to user-provided types too?

This is specifically to support a fully open hierarchy. A solution that allows dyn_cast between LLVM-provided types only (or any fixed set of types) would be insufficient.

Same sort of question - I guess the LLVM version of this code would be closed, but users would provide their own kinds of MUs - to support those users using both their own custom ones and standard ones, do the users control the MUs, such that they could test for all the types of MUs they know they are using in their JIT. Yeah, that'd be a bit awkward to be "is it MyCustomMU3" ends up being "is it not an IRMU, not a <other LLVM-provided MU>, etc... then it must be a MyCustomMU of some kind, so then do a different pseudo RTTI test".

Yep. And what if the client is using a JIT built on top of ORC that has their own set of MU types? Then you can't even reason by elimination: Ok, it's not an LLVM MU, but is it one of mine, or one of the other library author's?

[dblaikie]

Fair enough :)

[lhames]

Cool. I'll get this tidied up and clarify the rules about the ID member.

Did you have any thoughts on switching to type_traits for the ID? On the one hand it's safer since you couldn't accidentally fall through to your parent's ID, on the other hand it's more complex boilerplate: an extern specialization rather than a static id.

• Lang.

[dblaikie]

Yeah, I'm not sure a template specialization solution would be a huge improvement (& maybe even more likely people would define the constants in headers?). Hmm - could you use a /function/ pointer instead? Would that work I guess it'd have the same problem (if it's an inline function I guess Microsoft doesn't use a single address/value across dynamic libraries).

I don't expect this'll be used widely to the point where it becomes a real lot of gotchas, but probably good if you setup some Herald rules to watch for uses of this if possible to keep an eye on new uses.

[dblaikie]

(oh, for the mailing list - I accidentally "unapproved this" because I'd already approved it so when I reached for the UI approve it was the "unapprove" Button... anyway - approved again/now)

[rriddle]

Support/ExtensibleRTTITest.cpp

21 ↗

(On Diff #119629)

This is a solvable problem so long as we have the ability to properly annotate with dllexport/dllimport. I did an annoying amount of DLL testing when writing mlir::TypeID, but we don't have a way to do that in LLVM right now AFAIK so I've punted on doing that.

(https://github.com/llvm/llvm-project/blob/master/mlir/include/mlir/Support/TypeID.h)

[sammccall]

llvm/lib/Support/CMakeLists.txt

94

This file doesn't exist, so removed this line in dffbeffa39f5625fab98ca203b0922e0ba14d06b

[lhames]

Support/ExtensibleRTTITest.cpp

21 ↗

(On Diff #119629)

Interesting. I'd never looked in to *why* weak symbols weren't uniqued across DLLs. Is it just because they weren't visible by default?

llvm/lib/Support/CMakeLists.txt

94

Thanks Sam. File and line have been added back in 255cc202ea.

[rriddle]

Support/ExtensibleRTTITest.cpp

21 ↗

(On Diff #119629)

I don't know the exact details, but DLLs generally require explicit visibility rules and when a symbol is imported vs. exported. Getting weak functions uniqued across DLLs is solvable, but I've run into lots of problems trying to get variables/static data members uniqued. This is why I opted for a static variable inside an inline function, as that is guaranteed to be safe if the visibility is set properly.

https://devblogs.microsoft.com/oldnewthing/20140109-00/?p=2123

[jdoerfert]

So this broke my builds :(, I tried to use a fresh build folder but no luck

FAILED: unittests/Support/SupportTests 
: && clang++  --gcc-toolchain=/soft/compilers/gcc/6.5.0/linux-rhel7-x86_64 -fPIC -fvisibility-inlines-hidden -Werror -Werror=date-time -Werror=unguarded-availability-new -Wall -Wextra -Wno-unused
unittests/Support/CMakeFiles/SupportTests.dir/ExtensibleRTTITest.cpp.o:ExtensibleRTTITest.cpp:function llvm::RTTIRoot::RTTIRoot(): error: undefined reference to 'vtable for llvm::RTTIRoot'
/usr/bin/ld.gold: the vtable symbol may be undefined because the class is missing its key function
unittests/Support/CMakeFiles/SupportTests.dir/ExtensibleRTTITest.cpp.o:ExtensibleRTTITest.cpp:function llvm::RTTIRoot::classID(): error: undefined reference to 'llvm::RTTIRoot::ID'
unittests/Support/CMakeFiles/SupportTests.dir/ExtensibleRTTITest.cpp.o:ExtensibleRTTITest.cpp:vtable for (anonymous namespace)::MyBaseType: error: undefined reference to 'llvm::RTTIRoot::anchor()'
unittests/Support/CMakeFiles/SupportTests.dir/ExtensibleRTTITest.cpp.o:ExtensibleRTTITest.cpp:vtable for llvm::RTTIExtends<(anonymous namespace)::MyBaseType, llvm::RTTIRoot>: error: undefined reference to 'llvm::RTTIRoot::anchor()'
unittests/Support/CMakeFiles/SupportTests.dir/ExtensibleRTTITest.cpp.o:ExtensibleRTTITest.cpp:vtable for (anonymous namespace)::MyDerivedType: error: undefined reference to 'llvm::RTTIRoot::anchor()'
unittests/Support/CMakeFiles/SupportTests.dir/ExtensibleRTTITest.cpp.o:ExtensibleRTTITest.cpp:vtable for llvm::RTTIExtends<(anonymous namespace)::MyDerivedType, (anonymous namespace)::MyBaseType>: error: undefined reference to 'llvm
clang-9: error: linker command failed with exit code 1 (use -v to see invocation)

[jdoerfert]

It seems 255cc202ea610f9d6f5a5c6c9d40a2f2be235701 fixed my issue, apologies for the noise.

llvm/docs/HowToSetUpLLVMStyleRTTI.rst

#. The argument to ``classof`` should be a ``const Base *``, where ``Base``
    is some ancestor in the inheritance hierarchy. The argument should
    *never* be a derived class or the class itself: the template machinery
    for ``isa<>`` already handles this case and optimizes it.
 #. For each class in the hierarchy that has no children, implement a
    ``classof`` that checks only against its ``Kind``.
 #. For each class in the hierarchy that has children, implement a
    ``classof`` that checks a range of the first child's ``Kind`` and the
    last child's ``Kind``.
+
+RTTI for Open Class Hierarchies
+===============================
+
+Sometimes it is not possible to know all types in a hierarchy ahead of time.
+For example, in the shapes hierarchy described above the authors may have
+wanted their code to work for user defined shapes too. To support use cases
+that require open hierarchies LLVM provides the ``RTTIRoot`` and
+``RTTIExtends`` utilities.
+
+The ``RTTIRoot`` class describes an interface for performing RTTI checks. The
+``RTTIExtends`` class template provides an implementation of this interface
+for classes derived from ``RTTIRoot``. ``RTTIExtends`` uses the "`Curiously
+Recurring Template Idiom`_", taking the class being defined as its first
+template argument and the parent class as the second argument. Any class that
+uses ``RTTIExtends`` must define a ``static char ID`` member, the address of
+which will be used to identify the type.
+
+This open-hierarchy RTTI support should only be used if your use case requries
+it. Otherwise the standard LLVM RTTI system should be preferred.
+
+.. _`Curiously Recurring Template Idiom`:
+https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern
+
+E.g.
+
+.. code-block:: c++
+
+   class Shape : public RTTIExtends<Shape, RTTIRoot> {
+   public:
+     static char ID;
+     virtual double computeArea() = 0;
+   };
+
+   class Square : public RTTIExtends<Square, Shape> {
+     double SideLength;
+   public:
+     static char ID;
+
+     Square(double S) : SideLength(S) {}
+     double computeArea() override;
+   };
+
+   class Circle : public RTTIExtends<Circle, Shape> {
+     double Radius;
+   public:
+     static char ID;
+
+     Circle(double R) : Radius(R) {}
+     double computeArea() override;
+   };
+
+   char Shape::ID = 0;
+   char Square::ID = 0;
+   char Circle::ID = 0;

llvm/include/llvm/Support/ExtensibleRTTI.h

+//===-- llvm/Support/ExtensibleRTTI.h - ExtensibleRTTI support --*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// \file
+//
+// Defines an extensible RTTI mechanism designed to work with Casting.h.
+//
+// Extensible RTTI differs from LLVM's primary RTTI mechanism (see
+// llvm.org/docs/HowToSetUpLLVMStyleRTTI.html) by supporting open type
+// hierarchies, where new types can be added from outside libraries without
+// needing to change existing code. LLVM's primary RTTI mechanism should be
+// preferred where possible, but where open hierarchies are needed this system
+// can be used.
+//
+// The RTTIRoot class defines methods for comparing type ids. Implementations
+// of these methods can be injected into new classes using the RTTIExtends
+// class template.
+//
+// E.g.
+//
+//   @code{.cpp}
+//   class MyBaseClass : public RTTIExtends<MyBaseClass, RTTIRoot> {
+//   public:
+//     static char ID;
+//     virtual void foo() = 0;
+//   };
+//
+//   class MyDerivedClass1 : public RTTIExtends<MyDerivedClass1, MyBaseClass> {
+//   public:
+//     static char ID;
+//     void foo() override {}
+//   };
+//
+//   class MyDerivedClass2 : public RTTIExtends<MyDerivedClass2, MyBaseClass> {
+//   public:
+//     static char ID;
+//     void foo() override {}
+//   };
+//
+//   char MyBaseClass::ID = 0;
+//   char MyDerivedClass1::ID = 0;
+//   char MyDerivedClass2:: ID = 0;
+//
+//   void fn() {
+//     std::unique_ptr<MyBaseClass> B = llvm::make_unique<MyDerivedClass1>();
+//     llvm::outs() << isa<MyBaseClass>(B) << "\n"; // Outputs "1".
+//     llvm::outs() << isa<MyDerivedClass1>(B) << "\n"; // Outputs "1".
+//     llvm::outs() << isa<MyDerivedClass2>(B) << "\n"; // Outputs "0'.
+//   }
+//
+//   @endcode
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_EXTENSIBLERTTI_H
+#define LLVM_SUPPORT_EXTENSIBLERTTI_H
+
+namespace llvm {
+
+template <typename ThisT, typename ParentT> class RTTIExtends;
+
+/// Base class for the extensible RTTI hierarchy.
+///
+/// This class defines virtual methods, dynamicClassID and isA, that enable
+/// type comparisons.
+class RTTIRoot {
+public:
+  virtual ~RTTIRoot() = default;
+
+  /// Returns the class ID for this type.
+  static const void *classID() { return &ID; }
+
+  /// Returns the class ID for the dynamic type of this RTTIRoot instance.
+  virtual const void *dynamicClassID() const = 0;
+
+  /// Returns true if this class's ID matches the given class ID.
+  virtual bool isA(const void *const ClassID) const {
+    return ClassID == classID();
+  }
+
+  /// Check whether this instance is a subclass of QueryT.
+  template <typename QueryT>
+  bool isA() const { return isA(QueryT::classID()); }
+
+private:
+  virtual void anchor();
+
+  static char ID;
+};
+
+/// Inheritance utility for extensible RTTI.
+///
+/// Supports single inheritance only: A class can only have one
+/// ExtensibleRTTI-parent (i.e. a parent for which the isa<> test will work),
+/// though it can have many non-ExtensibleRTTI parents.
+///
+/// RTTIExtents uses CRTP so the first template argument to RTTIExtends is the
+/// newly introduced type, and the *second* argument is the parent class.
+///
+/// class MyType : public RTTIExtends<MyType, RTTIRoot> {
+/// public:
+///   static char ID;
+/// };
+///
+/// class MyDerivedType : public RTTIExtends<MyDerivedType, MyType> {
+/// public:
+///   static char ID;
+/// };
+///
+template <typename ThisT, typename ParentT>
+class RTTIExtends : public ParentT {
+public:
+  // Inherit constructors from ParentT.
+  using ParentT::ParentT;
+
+  static const void *classID() { return &ThisT::ID; }
+
+  const void *dynamicClassID() const override { return &ThisT::ID; }
+
+  bool isA(const void *const ClassID) const override {
+    return ClassID == classID() || ParentT::isA(ClassID);
+  }
+
+  static bool classof(const RTTIRoot *R) { return R->isA<ThisT>(); }
+};
+
+} // end namespace llvm
+
+#endif // LLVM_SUPPORT_EXTENSIBLERTTI_H

llvm/lib/Support/CMakeLists.txt

add_llvm_component_library(LLVMSupport
   DebugCounter.cpp
   DeltaAlgorithm.cpp
   DAGDeltaAlgorithm.cpp
   DJB.cpp
   ELFAttributeParser.cpp
   ELFAttributes.cpp
   Error.cpp
   ErrorHandling.cpp
+  ExtensibleRTTI.cpp
   FileCheck.cpp
   FileCollector.cpp
   FileUtilities.cpp
   FileOutputBuffer.cpp
   FoldingSet.cpp
   FormattedStream.cpp
   FormatVariadic.cpp
   GlobPattern.cpp

llvm/unittests/Support/CMakeLists.txt

add_llvm_unittest(SupportTests
   DebugCounterTest.cpp
   DJBTest.cpp
   EndianStreamTest.cpp
   EndianTest.cpp
   ELFAttributeParserTest.cpp
   ErrnoTest.cpp
   ErrorOrTest.cpp
   ErrorTest.cpp
+  ExtensibleRTTITest.cpp
   FileCheckTest.cpp
   FileCollectorTest.cpp
   FileOutputBufferTest.cpp
   FileUtilitiesTest.cpp
   FormatVariadicTest.cpp
   GlobPatternTest.cpp
   Host.cpp
   ItaniumManglingCanonicalizerTest.cpp

llvm/unittests/Support/ExtensibleRTTITest.cpp

+//===------ unittests/ExtensibleRTTITest.cpp - Extensible RTTI Tests ------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/ExtensibleRTTI.h"
+#include "llvm/Support/Casting.h"
+
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace {
+
+class MyBaseType : public RTTIExtends<MyBaseType, RTTIRoot> {
+public:
+  static char ID;
+};
+
+class MyDerivedType : public RTTIExtends<MyDerivedType, MyBaseType> {
+public:
+  static char ID;
+};
+
+class MyOtherDerivedType : public RTTIExtends<MyOtherDerivedType, MyBaseType> {
+public:
+  static char ID;
+};
+
+class MyDeeperDerivedType
+    : public RTTIExtends<MyDeeperDerivedType, MyDerivedType> {
+public:
+  static char ID;
+};
+
+char MyBaseType::ID = 0;
+char MyDerivedType::ID = 0;
+char MyOtherDerivedType::ID = 0;
+char MyDeeperDerivedType::ID = 0;
+
+TEST(ExtensibleRTTI, isa) {
+  MyBaseType B;
+  MyDerivedType D;
+  MyDeeperDerivedType DD;
+
+  EXPECT_TRUE(isa<MyBaseType>(B));
+  EXPECT_FALSE(isa<MyDerivedType>(B));
+  EXPECT_FALSE(isa<MyOtherDerivedType>(B));
+  EXPECT_FALSE(isa<MyDeeperDerivedType>(B));
+
+  EXPECT_TRUE(isa<MyBaseType>(D));
+  EXPECT_TRUE(isa<MyDerivedType>(D));
+  EXPECT_FALSE(isa<MyOtherDerivedType>(D));
+  EXPECT_FALSE(isa<MyDeeperDerivedType>(D));
+
+  EXPECT_TRUE(isa<MyBaseType>(DD));
+  EXPECT_TRUE(isa<MyDerivedType>(DD));
+  EXPECT_FALSE(isa<MyOtherDerivedType>(DD));
+  EXPECT_TRUE(isa<MyDeeperDerivedType>(DD));
+}
+
+TEST(ExtensibleRTTI, cast) {
+  MyDerivedType D;
+  MyBaseType &BD = D;
+
+  cast<MyBaseType>(D);
+  cast<MyBaseType>(BD);
+  cast<MyDerivedType>(BD);
+}
+
+TEST(ExtensibleRTTI, dyn_cast) {
+  MyBaseType B;
+  MyDerivedType D;
+  MyBaseType &BD = D;
+
+  EXPECT_EQ(dyn_cast<MyDerivedType>(&B), nullptr);
+  EXPECT_EQ(dyn_cast<MyDerivedType>(&D), &D);
+  EXPECT_EQ(dyn_cast<MyBaseType>(&BD), &BD);
+  EXPECT_EQ(dyn_cast<MyDerivedType>(&BD), &D);
+}
+
+} // namespace