c++ - How is LLVM isa<> implemented?

Question

From http://llvm.org/docs/CodingStandards.html#ci_rtti_exceptions

LLVM does make extensive use of a hand-rolled form of RTTI that use templates like isa<>, cast<>, and dyn_cast<>. This form of RTTI is opt-in and can be added to any class. It is also substantially more efficient than dynamic_cast<>.

How is isa and the others implemented?

Answer 1

First of all, the LLVM system is extremely specific and not at all a drop-in replacement for the RTTI system.

Premises

• For most classes, it is unnecessary to generate RTTI information
• When it is required, the information only makes sense within a given hierarchy
• We preclude multi-inheritance from this system

Identifying an object class

Take a simple hierarchy, for example:

struct Base {}; /* abstract */
struct DerivedLeft: Base {}; /* abstract */
struct DerivedRight:Base {};
struct MostDerivedL1: DerivedLeft {};
struct MostDerivedL2: DerivedLeft {};
struct MostDerivedR: DerivedRight {};

We will create an enum specific to this hierarchy, with an enum member for each of the hierarchy member that can be instantiated (the others would be useless).

enum BaseId {
  DerivedRightId,
  MostDerivedL1Id,
  MostDerivedL2Id,
  MostDerivedRId
};

Then, the Base class will be augmented with a method that will return this enum.

struct Base {
  static inline bool classof(Base const*) { return true; }

  Base(BaseId id): Id(id) {}

  BaseId getValueID() const { return Id; }

  BaseId Id;
};

And each concrete class is augmented too, in this manner:

struct DerivedRight: Base {
  static inline bool classof(DerivedRight const*) { return true; }

  static inline bool classof(Base const* B) {
    switch(B->getValueID()) {
    case DerivedRightId: case MostDerivedRId: return true;
    default: return false;
    }
  }

  DerivedRight(BaseId id = DerivedRightId): Base(id) {}
};

Now, it is possible, simply, to query the exact type, for casting.

Hiding implementation details

Having the users murking with getValueID would be troublesome though, so in LLVM this is hidden with the use of classof methods.

A given class should implement two classof methods: one for its deepest base (with a test of the suitable values of BaseId) and one for itself (pure optimization). For example:

struct MostDerivedL1: DerivedLeft {
  static inline bool classof(MostDerivedL1 const*) { return true; }

  static inline bool classof(Base const* B) {
    return B->getValueID() == MostDerivedL1Id;
  }

  MostDerivedL1(): DerivedLeft(MostDerivedL1Id) {}
};

This way, we can check whether a cast is possible or not through the templates:

template <typename To, typename From>
bool isa(From const& f) {
  return To::classof(&f);
}

Imagine for a moment that To is MostDerivedL1:

• if From is MostDerivedL1, then we invoke the first overload of classof, and it works
• if From is anything other, then we invoke the second overload of classof, and the check uses the enum to determine if the concrete type match.

Hope it's clearer.