Skip to content

Lesson 10.4 — Casting and dispatch: LLVM-style RTTI, C++ RTTI, variants and visitors

Techniques: LLVM-style RTTI (classof, isa/cast/dyn_cast/dyn_cast_if_present, CastInfo customization), C++ RTTI (dynamic_cast, typeid), closed sum types (std::variant + std::visit), the visitor pattern (InstVisitor) · Pebble uses: LLVM-style RTTI everywhere; InstVisitor in the lab; the Pebble AST (Ch 4) uses LLVM-style RTTI too · Lab: Lab 10.3 (raw casts vs InstVisitor) · Prerequisites: Lesson 10.2 · Time: 3 hours

An optimization looks at %c = sub i32 %b, %a through a Value *. Before it can ask for the opcode or the operands, it must know that the value is a BinaryOperator, and not an argument, a constant or a phi. C++ offers dynamic_cast, but for LLVM's Value that does not even compile (the real-world box shows the error). This lesson covers four ways to answer "what kind of object is this?" and "run the code for this kind". Lab 10.3 then has you write the same analysis with two of them.

1. Problem and motivation

IR, AST and type hierarchies are closed (the compiler defines every node kind), deep (Value → User → Instruction → UnaryInstruction → CastInst → ZExtInst) and queried constantly, often in the innermost loop of a pass. The type test has to be cheap, safe (a wrong downcast must be impossible or caught), and extensible when the hierarchy grows. There are two basic designs: store a kind tag in every object and test it, or let the language find the dynamic type (vtables, discriminated unions) [LLVM-RTTI, Str94].

LLVM-style RTTI

Every class in the hierarchy defines static bool classof(const Base *), typically a comparison of a kind tag (Value::getValueID(), Type::getTypeID(), Clang's Stmt::getStmtClass()). The templates isa<>, cast<>, dyn_cast<> and their _if_present forms are built on classof. LLVM is built with -fno-rtti by default, and Value has no vtable at all, so this is the only type test available [LLVM-RTTI, LLVM-PM, LLVM-Casting]. Pebble's AST uses the same scheme.

C++ RTTI

dynamic_cast<T *>(p) and typeid use the vtable of a polymorphic class to find the dynamic type and, for dynamic_cast, to search the inheritance graph [Str94, ItaniumABI]. They are general (multiple and virtual inheritance, cross-casts) and need no code in the classes. The cost is a vtable pointer per object, type information emitted for every polymorphic class, and a library call per cast. LLVM's coding standards forbid it in LLVM itself [LLVM-CS].

std::variant and visit

A closed set of alternatives can be a sum type: std::variant<Bin, Cmp, Sel> stores an index and the active member, and std::visit dispatches on the index. The compiler checks that the visitor handles every alternative [P0088]. This is the Rust or ML approach (enum + match). It suits small, value-semantic hierarchies and ASTs, not LLVM's pointer-identity IR.

InstVisitor

The visitor pattern [GoF94] separates "the operation" from "the class hierarchy". InstVisitor<Derived> is a CRTP (static) visitor: visit(I) switches on the opcode once and calls visitAdd, visitICmpInst, visitIntrinsicInst, and so on. Each unimplemented handler delegates to the handler of its parent class, down to visitInstruction [LLVM-InstVisitor]. Lab 10.3's Style::Visitor and LLVM's interpreter (Interpreter is an InstVisitor) are built this way.

2. Definitions and algorithms

Definition 10.4.1 (Class hierarchy, subtype relation)

A class hierarchy is a rooted tree \((\mathcal{C}, \mathrm{parent}, \mathit{root})\) of classes (single inheritance). \(C \sqsubseteq D\) ("\(C\) is a subclass of \(D\)") means \(D\) lies on the path from \(C\) to the root, \(C\) itself included. A class is concrete if objects can have it as their dynamic type \(\mathrm{dyn}(o)\). An object \(o\) is a \(D\) when \(\mathrm{dyn}(o) \sqsubseteq D\).

Definition 10.4.2 (Kind tag and classof)

A kind tag is an injective map \(\kappa\) from concrete classes to integers, stored in each object (\(\kappa(\mathrm{dyn}(o))\) is getValueID()). For a class \(D\), let \(S_D = \{\, \kappa(C) \mid C \text{ concrete},\ C \sqsubseteq D \,\}\). A predicate \(\mathrm{classof}_D(o)\) is correct if \(\mathrm{classof}_D(o) \iff \kappa(\mathrm{dyn}(o)) \in S_D \iff o \text{ is a } D\).

Kinds in LLVM

llvm/IR/Value.def lists the concrete value classes in an order where each abstract class's members are consecutive. Constant::classof is getValueID() <= ConstantLastVal, Instruction::classof(const Value *) is getValueID() >= InstructionVal, and ConstantInt::classof is getValueID() == ConstantIntVal. For instructions, the opcode refines the kind: BinaryOperator::classof(const Instruction *) tests isBinaryOp(), a range of opcodes.

LLVM-style RTTI

Algorithm 10.4.3 (isa, cast, dyn_cast and the _if_present forms)

  • Input: a class \(D\) and a pointer \(p\) of static type Base * (or a reference, a smart pointer, a std::optional, …).
  • Output: a boolean (isa) or a D * / null.
  • Precondition: \(p \ne\) null for isa/cast/dyn_cast; \(\mathrm{classof}_D\) is correct.
  • Postcondition: isa<D>(p) \(\iff\) \(*p\) is a \(D\); cast<D>(p) \(= p\) viewed as D * when \(*p\) is a \(D\) (otherwise an assertion failure, or undefined behavior in release builds); dyn_cast<D>(p) $= $ cast<D>(p) if isa<D>(p), else null; isa_and_present<D>(p) / dyn_cast_if_present<D>(p) / cast_if_present<D>(p) return false / null / null when \(p\) is null and otherwise behave like isa / dyn_cast / cast.
  • Invariant: none (no state).
function IsA(D, p):                        # isa_impl_cl / CastInfo::isPossible
    assert p ≠ null                        # "isa<> used on a null pointer"
    if static type of p ⊑ D: return true   # upcast: decided at compile time
    q ← simplify(p)                        # simplify_type: Use → Value *, etc.
    return D::classof(q)
function Cast(D, p):
    assert IsA(D, p)                       # "cast<Ty>() argument of incompatible type!"
    return (D *) p                         # CastInfo::doCast: a static_cast
function DynCast(D, p):
    assert p ≠ null
    return IsA(D, p) ? Cast(D, p) : null
function DynCastIfPresent(D, p):
    return p = null ? null : DynCast(D, p)
function IsA(D₁, …, Dₖ, p):                 # variadic isa
    return IsA(D₁, p) ∨ … ∨ IsA(Dₖ, p)

CastInfo<To, From> (llvm/include/llvm/Support/Casting.h) is the customization point. Specializing it (or inheriting from helpers such as ValueFromPointerCast, OptionalValueCast, UniquePtrCast) teaches the templates new source types, for example casting an MLIR Type value or a PointerUnion (Lesson 10.6) [LLVM-Casting, LLVM-RTTI].

classof compiles to a range test; dynamic_cast to a library call

Reproduce (clang 23.1.2, Linux x86-64):

cd chapters/10-llvm-cpp-api/examples
clang++-23 -O2 -S -emit-llvm -fno-discard-value-names shapes.cpp -o - \
  | grep -v "^;\|^$\|^!\|attributes\|source_filename\|target "

shapes.cpp defines asCircle(Shape *S) { return dynamic_cast<Circle *>(S); } over a polymorphic Shape, and asBinary(Node *N) with a kind enum {K_Add, K_Sub, K_Mul, K_LastBinary = K_Mul, K_Load, K_Store} and classof(N) = N->TheKind <= K_LastBinary.

Output (complete):

$_ZTI6Circle = comdat any
$_ZTS6Circle = comdat any
@_ZTI5Shape = external constant ptr
@_ZTI6Circle = linkonce_odr dso_local constant { ptr, ptr, ptr } { ptr getelementptr inbounds (ptr, ptr @_ZTVN10__cxxabiv120__si_class_type_infoE, i64 2), ptr @_ZTS6Circle, ptr @_ZTI5Shape }, comdat, align 8
@_ZTVN10__cxxabiv120__si_class_type_infoE = external global [0 x ptr]
@_ZTS6Circle = linkonce_odr dso_local constant [8 x i8] c"6Circle\00", comdat, align 1
define dso_local noundef ptr @_Z8asCircleP5Shape(ptr nofree noundef readonly %S) local_unnamed_addr #0 {
entry:
  %0 = icmp eq ptr %S, null
  br i1 %0, label %dynamic_cast.end, label %dynamic_cast.notnull
dynamic_cast.notnull:                             ; preds = %entry
  %1 = tail call ptr @__dynamic_cast(ptr nonnull %S, ptr nonnull @_ZTI5Shape, ptr nonnull @_ZTI6Circle, i64 0) #3
  br label %dynamic_cast.end
dynamic_cast.end:                                 ; preds = %entry, %dynamic_cast.notnull
  %2 = phi ptr [ %1, %dynamic_cast.notnull ], [ null, %entry ]
  ret ptr %2
}
declare ptr @__dynamic_cast(ptr, ptr, ptr, i64) local_unnamed_addr #1
define dso_local noundef ptr @_Z8asBinaryP4Node(ptr nofree noundef readonly captures(ret: address, provenance) %N) local_unnamed_addr #2 {
entry:
  %0 = load i32, ptr %N, align 4, !tbaa !9
  %cmp.i = icmp slt i32 %0, 3
  %cond = select i1 %cmp.i, ptr %N, ptr null
  ret ptr %cond
}

What to notice: the LLVM-style cast is one load, one compare and a select: Theorem 10.4.10's interval test, with the lower bound folded away because the first kind is 0. The C++ cast emits type-info objects (_ZTI6Circle points to its base's _ZTI5Shape, which is the chain the runtime walks) and calls __dynamic_cast with the hint i64 0 (Algorithm 10.4.5). The null check is inlined in both.

C++ RTTI

Definition 10.4.4 (dynamic_cast semantics)

For a pointer \(v\) to a subobject of a polymorphic complete object \(o\), dynamic_cast<T *>(v) is:

  • (i) downcast: if \(v\) points to a public base subobject of exactly one \(T\) subobject of \(o\), a pointer to that \(T\);
  • (ii) cross-cast: otherwise, if \(v\) points to a public base subobject of \(o\) and \(o\)'s dynamic type has an unambiguous public base \(T\), a pointer to that base;
  • (iii) otherwise null.

dynamic_cast<void *>(v) returns the address of \(o\) (via the vtable's offset-to-top). typeid(*v) returns \(o\)'s std::type_info [ItaniumABI §2.9.6–2.9.7].

Algorithm 10.4.5 (Itanium __dynamic_cast, outline)

  • Input: sub (a non-null pointer to a polymorphic subobject), src (its static type info), dst (the target type info), and a hint src2dst_offset (a non-negative offset when src is a unique public non-virtual base of dst, or a negative code: −1 no hint, −2 not a public base, −3 multiple non-virtual).
  • Output: the adjusted pointer or null.
  • Precondition: the vtables and type infos follow the Itanium C++ ABI.
  • Postcondition: Definition 10.4.4.
  • Invariant: the search visits each base-class record of the dynamic type at most once per path.
function DynamicCast(sub, src, dst, hint):
    vptr ← *(void **) sub
    whole ← sub + offset_to_top(vptr)             # the complete object o
    dynT ← type_info(vptr)                        # its dynamic type
    if dynT = dst:                                # most common: cast to the dynamic type
        if hint ≥ 0: return (whole + hint = sub) ? whole : null
        return (sub is a public src-subobject of whole) ? whole : null
    # otherwise walk dynT's base-class records (direct bases only are stored;
    # indirect ones are reached by chasing type_info pointers), looking for
    # dst subobjects that contain sub publicly (downcast), or for a unique
    # public dst base of whole (cross-cast)
    return SearchBases(dynT, whole, sub, src, dst)

llvm::Value is not polymorphic: dynamic_cast does not compile

Reproduce (clang 23.1.2, LLVM 23.1.2 headers):

cd chapters/10-llvm-cpp-api/examples
clang++-23 $(llvm-config --cxxflags) -std=c++23 -c notpoly.cpp -o /dev/null

Output (complete):

notpoly.cpp:4:34: error: 'llvm::Value' is not polymorphic
    4 | bool isBinary(Value *V) { return dynamic_cast<BinaryOperator *>(V) != nullptr; }
      |                                  ^                              ~
1 error generated.

What to notice: dynamic_cast needs a vtable to find the dynamic type (Algorithm 10.4.5, first line). Value deliberately has none: its subclasses are distinguished by SubclassID and deleted through Value::deleteValue(), which switches on it. So LLVM-style RTTI is not a style preference for Value. It is the only option.

std::variant and visit

Definition 10.4.6 (Closed sum type)

A sum type \(T = A_0 + A_1 + \dots + A_{m-1}\) is represented as a pair \((i, a)\) of an index \(i \in \{0, \dots, m-1\}\) and a value \(a\) of type \(A_i\) (std::variant<A_0, …, A_{m-1}>, with index() and storage for the largest alternative). A visitor is a callable \(f\) with an overload \(f_i : A_i \to R\) for every \(i\). \(\mathrm{visit}(f, (i, a)) = f_i(a)\). holds_alternative<A_j> is the test \(i = j\) [P0088].

Algorithm 10.4.7 (std::visit dispatch)

  • Input: a visitor \(f\) and a variant \((i, a)\).
  • Output: \(f_i(a)\).
  • Precondition: \(f\) is callable with every alternative (checked at compile time), and the variant is not valueless (otherwise bad_variant_access).
  • Postcondition: exactly one overload ran, the one for the active alternative.
  • Invariant: none.
function Visit(f, v):
    table ← [ λa. f(a as A_0), …, λa. f(a as A_{m−1}) ]   # built at compile time
    return table[v.index()](v.storage)                  # or a switch on the index

std::visit compiles to a switch on the index

Reproduce (clang 23.1.2 with libstdc++ 14, Linux x86-64):

cd chapters/10-llvm-cpp-api/examples
clang++-23 -std=c++23 -O2 -S -emit-llvm -fno-discard-value-names variant.cpp -o - | sed -n '/^define/,/^}/p'

variant.cpp computes a cost over std::variant<Bin, Cmp, Sel> with a generic lambda and if constexpr.

Output (abridged: the 400-character mangled name of the join block is shown as %exit):

define dso_local noundef range(i32 1, 5) i32 @_Z4costRKSt7variantIJ3Bin3Cmp3SelEE(ptr nofree noundef nonnull readonly align 4 captures(none) dereferenceable(5) %N) local_unnamed_addr #0 {
entry:
  %_M_index.i.i.i = getelementptr inbounds nuw i8, ptr %N, i64 4
  %0 = load i8, ptr %_M_index.i.i.i, align 4, !tbaa !9
  switch i8 %0, label %sw.default.i.i [
    i8 0, label %sw.bb.i.i
    i8 1, label %exit
    i8 2, label %sw.bb5.i.i
  ]

sw.bb.i.i:                                        ; preds = %entry
  %1 = load i32, ptr %N, align 4, !tbaa !11
  %cmp.i.i.i.i.i.i = icmp eq i32 %1, 3
  %cond.i.i.i.i.i.i = select i1 %cmp.i.i.i.i.i.i, i32 4, i32 1
  br label %exit

sw.bb5.i.i:                                       ; preds = %entry
  br label %exit

sw.default.i.i:                                   ; preds = %entry
  unreachable

exit: ; preds = %entry, %sw.bb.i.i, %sw.bb5.i.i
  %retval.0.i.i = phi i32 [ %cond.i.i.i.i.i.i, %sw.bb.i.i ], [ 2, %sw.bb5.i.i ], [ 1, %entry ]
  ret i32 %retval.0.i.i
}

What to notice: the index is the byte at offset 4 (after the 4-byte largest alternative), and dispatch is a switch on it (Algorithm 10.4.7). The default case is unreachable, because the compiler knows every index is handled. There is no vtable, no library call and no kind tag in the objects themselves: the tag lives in the variant.

InstVisitor

Definition 10.4.8 (Static visitor with delegation)

InstVisitor<SubClass, RetTy> defines, for every opcode \(o\) with instruction class \(C_o\), a method \(\mathrm{visit}_o(C_o\&)\), and for every class \(C\) in the instruction hierarchy a method \(\mathrm{visit}_C(C\&)\). The default body of \(\mathrm{visit}_o\) calls \(\mathrm{visit}_{C_o}\). The default body of \(\mathrm{visit}_C\) calls \(\mathrm{visit}_{\mathrm{parent}(C)}\) ("delegation"), down to \(\mathrm{visit}_{\mathit{Instruction}}\), which does nothing. Every call goes through static_cast<SubClass *>(this), so a method the subclass defines hides the default (CRTP: no virtual functions). Two routes are special. Calls go through delegateCallInst, so a call to an intrinsic reaches the specific intrinsic class (for example visitMemCpyInst) and then visitIntrinsicInst before visitCallInst. Terminators (visitReturnInst, visitSwitchInst, …, the two branch handlers visitUncondBrInst and visitCondBrInst by way of the deprecated visitBranchInst, and visitCallBase for invoke/callbr) pass through the pseudo-class handler visitTerminator before visitInstruction.

Algorithm 10.4.9 (InstVisitor::visit)

  • Input: an instruction \(I\) and a subclass object \(V\).
  • Output: the result of the most specific handler \(V\) overrides for \(I\).
  • Precondition: \(V\)'s handlers have the signatures RetTy visitX(X &).
  • Postcondition: Theorem 10.4.14.
  • Invariant: each delegation step moves to a strictly less specific class.
function Visit(V, I):
    switch I.opcode:                          # generated from Instruction.def
        case o: return V.visit_o(I as C_o)    # e.g. visitAdd(BinaryOperator &)
default visit_o(x):        return V.visit_{C_o}(x)          # opcode → class
default visit_C(x):        return V.visit_{parent(C)}(x)    # DELEGATE(parent)
default visit_Instruction(x): return RetTy()                # the fallback
function VisitFunction(V, F):
    for B in F.blocks: for I in B.instructions: Visit(V, I)

An InstVisitor census of clang -O1 output

Reproduce (clang 23.1.2, LLVM 23.1.2, Linux x86-64):

cd chapters/10-llvm-cpp-api/examples
clang-23 -O1 -S -emit-llvm -fno-discard-value-names gcd.c -o gcd.ll
clang++-23 $(llvm-config --cxxflags) -std=c++23 visit.cpp $(llvm-config --ldflags --libs) \
  -Wl,-rpath,$(llvm-config --libdir) -o visit && ./visit gcd.ll

visit.cpp overrides visitBinaryOperator, visitCmpInst, visitLoadInst, visitStoreInst, visitPHINode and visitInstruction (the fallback).

Output (complete):

gcd: binary=1 cmp=2 mem=0 phi=3 other=3
sum: binary=3 cmp=2 mem=1 phi=3 other=6

What to notice: icmp reached visitCmpInst although the visitor has no visitICmpInst: visitICmp → visitICmpInst → visitCmpInst by delegation (Definition 10.4.8). The shl and adds landed in visitBinaryOperator. Everything else (branches, ret, getelementptr, zext) fell through to visitInstruction, counted as "other". In gcd, the one binary operator is the srem.

3. Worked example

The objects: the running example's %a (add), %c (sub), an icmp slt named %p, a call to llvm.smax named %m, the argument %x, and the constant i32 7. We ask "is it a BinaryOperator?" and "which handler runs?" with each technique.

LLVM-style RTTI

isa<BinaryOperator>(V) evaluates Instruction::classof (a Value-ID range test) and then BinaryOperator::classof(const Instruction *) (an opcode range test):

object getValueID() >= InstructionVal? opcode binary? isa<BinaryOperator> dyn_cast<BinaryOperator> isa<Constant> (ID <= ConstantLastVal)
%a add yes yes true ptr false
%c sub yes yes true ptr false
%p icmp yes no false null false
%m call yes no false null false
%x argument no — false null false
i32 7 no — false null true

cast<BinaryOperator>(%p) would assert in a debug build. isa<BinaryOperator>(nullptr) asserts too, and isa_and_present returns false.

C++ RTTI

Suppose LLVM's classes had virtual functions: dynamic_cast<BinaryOperator *>(p) on %a would find the dynamic type BinaryOperator equal to dst in the first test of Algorithm 10.4.5 and return whole. On %p (dynamic type ICmpInst) it would walk ICmpInst's base chain CmpInst → Instruction → User → Value, find no BinaryOperator, and return null after four type-info comparisons.

std::variant and visit

With std::variant<Bin, Cmp, Call, Arg, Const>, the objects become \((0, \mathit{add})\), \((0, \mathit{sub})\), \((1, \mathit{slt})\), \((2, \mathit{smax})\), \((3, x)\) and \((4, 7)\). holds_alternative<Bin> compares the index with 0 (true, true, false, false, false, false), and visit jumps to entry \(i\) of its table.

InstVisitor

The visitor overrides visitBinaryOperator, visitCmpInst and visitIntrinsicInst. Delegation chains:

object opcode entry delegation steps handler that runs
%a visitAdd(BinaryOperator &) → visitBinaryOperator visitBinaryOperator
%c visitSub → visitBinaryOperator visitBinaryOperator
%p visitICmp(ICmpInst &) → visitICmpInst → visitCmpInst visitCmpInst
%m visitCall(CallInst &) → delegateCallInst: intrinsic → visitIntrinsicInst visitIntrinsicInst
ret visitRet(ReturnInst &) → visitReturnInst → visitTerminator → visitInstruction visitInstruction (default)

%x and i32 7 are not instructions, so an InstVisitor never sees them.

Try it

./course drill cast-semantics --seed 4 --difficulty hard evaluates isa/cast/dyn_cast/_if_present on LLVM's hierarchy (including null) and asks for classof ranges.

4. Invariants and correctness

LLVM-style RTTI

Theorem 10.4.10 (Preorder numbering makes classof an interval test)

Number the concrete classes of a hierarchy in a depth-first preorder (a class before its descendants, subtrees contiguous). Then for every class \(D\), \(S_D\) (Definition 10.4.2) is an interval \([\mathit{first}_D, \mathit{last}_D]\) of consecutive numbers, so first <= K && K <= last is a correct classof. With the kinds numbered \(0, 1, \dots\), a subtree that starts at 0 needs only the upper test, and a subtree that ends at the maximum needs only the lower one.

Proof

In a depth-first traversal, the nodes visited between entering \(D\) and leaving it are exactly the descendants of \(D\) (the standard DFS interval property, as in Ch 15, Corollary 15.1.7). A preorder numbering assigns consecutive numbers in visiting order, so the descendants of \(D\), \(D\) included, receive a contiguous block. Restricting to concrete classes deletes some numbers but, if we number only concrete classes in the same visiting order, keeps each subtree's numbers contiguous: removing elements from a contiguous run of a sequence and renumbering consecutively leaves it contiguous. So \(S_D = \{\mathit{first}_D, \dots, \mathit{last}_D\}\), and the two comparisons test membership exactly.

This is how llvm/IR/Value.def is ordered (constants first, with ConstantData a contiguous sub-run, then Argument, BasicBlock, … and the instructions last), and why Clang's StmtNodes.td generates firstXConstant/lastXConstant pairs. The drill's part 2 computes such intervals.

Proposition 10.4.11 (dyn_cast is exactly the guarded cast)

If classof is correct, then for non-null \(p\): dyn_cast<D>(p) \(\ne\) null \(\iff\) isa<D>(p) \(\iff\) \(*p\) is a \(D\), and when non-null it equals cast<D>(p).

Proof

Immediate from Algorithm 10.4.3: DynCast returns Cast(D, p) exactly when IsA(D, p) holds, and IsA is classof (or a compile-time upcast), which is correct by hypothesis. With single inheritance and no virtual bases (LLVM's hierarchies), Cast is a static_cast that does not change the address.

When it breaks: a classof that forgets a subclass (for example, a new instruction added outside the opcode range) makes isa false for objects that are of the class. cast then asserts in debug builds and is undefined behavior in release. LLVM's isa_impl also has static_asserts that reject casting to a type unrelated to the source.

C++ RTTI

Proposition 10.4.12 (dynamic_cast is correct without per-class code)

If every class is polymorphic and the compiler emits type info as specified by the ABI, Algorithm 10.4.5 returns exactly the result of Definition 10.4.4.

Proof sketch (full specification and rationale: [ItaniumABI §2.9.7])

The first test handles the dominant case (the dynamic type is the target) using the offset-to-top in the vtable to find the complete object. Otherwise the search enumerates the dynamic type's base-class subobjects from the type-info records (each record lists direct bases with offsets and public/virtual flags). It tracks the paths that contain sub and the dst subobjects found, and applies the downcast rule, then the cross-cast rule, rejecting ambiguous or non-public results. The ABI document states the conditions checked. The C++ standard's [expr.dynamic.cast] gives the semantics the algorithm implements.

std::variant and visit

Theorem 10.4.13 (Exhaustive, exactly-once dispatch)

If std::visit(f, v) compiles, then for every non-valueless variant value \(v\) exactly one overload of \(f\) runs, namely the one for \(v\)'s active alternative. Adding an alternative to the variant type makes every visitor that lacks an overload for it fail to compile.

Proof

visit instantiates \(f\)'s call for every alternative when building its dispatch table (Algorithm 10.4.7). If some alternative has no viable overload, that instantiation is ill-formed and compilation fails, so compilation implies coverage. At run time, the table is indexed by v.index(), which denotes the active alternative (the variant's invariant maintained by its constructors and assignments), so exactly that entry runs.

InstVisitor

Theorem 10.4.14 (Delegation reaches the most specific handler)

Let \(I\) have opcode \(o\) and class \(C_o\), and let the subclass override a set \(H\) of handlers. visit(I) calls the first overridden handler on the chain \(\mathrm{visit}_o, \mathrm{visit}_{C_o}, \mathrm{visit}_{\mathrm{parent}(C_o)}, \dots, \mathrm{visit}_{\mathit{Instruction}}\) (for calls, the chain passes through the intrinsic classes first). It calls exactly one such handler, and does so in \(O(\mathrm{depth})\) calls.

Proof

visit dispatches on the opcode to \(\mathrm{visit}_o\) (Algorithm 10.4.9). Because each call goes through static_cast<SubClass *>(this), name lookup finds the subclass's handler if it declares one with that name, and the default otherwise. A default handler's only action is to call the next handler in the chain, so the call sequence follows the chain until it reaches the first overridden handler, which does not delegate unless it chooses to. Each step moves to the parent class (Definition 10.4.8), and the hierarchy is a finite tree, so the chain has length at most \(1 + \mathrm{depth}(C_o)\) and ends at \(\mathrm{visit}_{\mathit{Instruction}}\) if nothing is overridden.

5. Complexity

Variables: \(d\) = depth of the hierarchy, \(b\) = number of base-class records reachable from the dynamic type, \(m\) = number of alternatives.

Technique Test / dispatch time Space per object Space per class Notes
LLVM-style RTTI \(O(1)\): one load + one or two compares (Theorem 10.4.10) a kind field (LLVM packs SubclassID into 8 bits) a classof measured: 134 ms per \(6 \times 10^7\) tests
C++ RTTI \(O(1)\) best (exact dynamic type); \(O(b)\) worst (base search) a vtable pointer type info + name string measured: 893 ms per \(6 \times 10^7\) tests (6.7× slower)
std::variant \(O(1)\): index compare or table jump index byte + largest alternative none measured: 157 ms per \(6 \times 10^7\) tests
InstVisitor \(O(1)\) switch + \(O(d)\) delegation calls (inlined) none (uses the opcode) none handlers usually inline into the switch

Proposition 10.4.15 (Cost of a failed dynamic_cast)

Under single inheritance, a failing dynamic_cast from a pointer whose dynamic type has depth \(d\) compares at least \(d\) type infos, while LLVM-style isa does at most two integer comparisons.

Proof

With single inheritance each __si_class_type_info stores one base pointer. To conclude that dst is not among the bases, the search must follow the chain from the dynamic type to the root, comparing each type info with dst, which is \(d\) comparisons (each a pointer compare, or a string compare on platforms where type infos are not unique). The classof range test is independent of \(d\) (Theorem 10.4.10).

Measurement (reproduce with examples/dispatch.cpp, compiled with -O2): \(6 \times 10^7\) "is this a binary node?" queries over 3 000 objects of three kinds took 134.1 ms with llvm::isa (classof), 893.1 ms with dynamic_cast and 156.5 ms with std::holds_alternative (clang 23.1.2, x86-64, one run; numbers vary by machine). Pathological input: deep hierarchies under C++ RTTI, such as a cast to a sibling of a class 10 levels down, pay the full base walk on every failed test. LLVM's Value hierarchy goes more than ten levels deep for the memory intrinsics (MemCpyInst → MemTransferInst → … → IntrinsicInst → CallInst → CallBase → Instruction → User → Value), and dyn_cast chains in hot loops multiply the difference.

6. Variants and refinements

LLVM-style RTTI

  • Open hierarchies ("How to set up LLVM-style RTTI", the "Concrete Bases and Deeper Hierarchies" and "Rules of Thumb" sections): when subclasses live in other libraries, reserve kind ranges (FirstXKind/LastXKind sentinels) [LLVM-RTTI].
  • CastInfo specializations for value types (MLIR Type/Attribute are cheap handles, not pointers), PointerUnion, std::optional, std::unique_ptr (unique_dyn_cast) [LLVM-Casting].
  • TypeSwitch (llvm/include/llvm/ADT/TypeSwitch.h): a fluent .Case<A>(…).Case<B>(…).Default(…) chain built on dyn_cast, used heavily in MLIR.

C++ RTTI

  • Compiler-generated hints (src2dst_offset) make the common downcast a single compare [ItaniumABI].
  • Unique vs non-unique type info: on platforms where a class's type info may be duplicated across shared objects, equality falls back to name comparison, which is slower.
  • typeid with a hash map from std::type_index to handlers: a user-built dispatch table.

std::variant and visit

  • Pattern matching in the language (Rust match, Swift switch over enum): the same sum type plus nested patterns and exhaustiveness checking at the source level.
  • Tagged unions by hand (a kind enum plus a union): what std::variant automates. It is what many C compilers do (GCC's tree uses a TREE_CODE tag with a union of node structs).

InstVisitor

  • Dynamic (virtual) visitors, the classic [GoF94] double dispatch: open to new operations without recompiling the hierarchy, but a virtual call per node.
  • RecursiveASTVisitor (Clang): a CRTP visitor for trees, with traversal as well as dispatch, and hooks for pre/post order.
  • Clang StmtVisitor/TypeVisitor, generated from .td/.def lists like Instruction.def.

7. In real compilers

LLVM-style RTTI

LLVM

llvm/include/llvm/Support/Casting.h (isa_impl, CastInfo, isa, cast, dyn_cast, isa_and_present, dyn_cast_if_present, cast_if_present), llvm/include/llvm/IR/Value.def (the kind order), llvm/include/llvm/IR/Constant.h Constant::classof, llvm/include/llvm/IR/Instruction.h Instruction::classof, llvm/include/llvm/IR/InstrTypes.h UnaryInstruction::classof [LLVM-Casting].

  • Clang clang/include/clang/AST/Stmt.h Stmt::getStmtClass() and generated classofs. MLIR Operation/Type with CastInfo. Pebble's AST (Ch 4).

Find where LLVM does it. In Constant.h, read Constant::classof. Question: why is there only one comparison, and what does the static_assert next to it guarantee? (Quiz llvm-where-constant-classof.)

C++ RTTI

Itanium C++ ABI

__dynamic_cast and the __class_type_info/__si_class_type_info/__vmi_class_type_info records (ABI §2.9.5–2.9.7) [ItaniumABI]. Implementations: libc++abi libcxxabi/src/private_typeinfo.cpp (__dynamic_cast) in the llvm-project tree at llvmorg-23.1.2, and libstdc++'s libsupc++/dyncast.cc (GCC 15).

  • LLVM's coding standards ("Do not use RTTI or Exceptions") [LLVM-CS]. Chromium and many game engines likewise build with -fno-rtti.

std::variant and visit

libstdc++ / libc++

std::variant and std::visit in <variant> (libstdc++ 14 as used in this course's Linux build; libc++ in the llvm-project tree, libcxx/include/variant) [P0088].

  • rustc represents MIR and types as Rust enums with match. Cranelift's InstructionData is an enum generated by its meta crate. Both are closed sum types.

InstVisitor

LLVM

llvm/include/llvm/IR/InstVisitor.h (visit, DELEGATE, delegateCallInst), and llvm/lib/ExecutionEngine/Interpreter/Interpreter.h: class Interpreter : public ExecutionEngine, public InstVisitor<Interpreter> [LLVM-InstVisitor, LLVM-Interp].

  • Clang StmtVisitor, RecursiveASTVisitor. GCC dispatches by switch (TREE_CODE (t)) and gimple_code, which is hand-written dispatch.

Find where LLVM does it. In InstVisitor.h, find delegateCallInst. Question: which handler does a call to llvm.memcpy reach first if the visitor overrides only visitIntrinsicInst and visitCallInst? (Quiz instvisitor-memcpy.)

8. Comparison

Technique Power / precision Speed Output / error quality Implementation effort Typical use
LLVM-style RTTI single-inheritance hierarchies you control; exact (Theorem 10.4.10) \(O(1)\), ~1 compare; fastest measured wrong cast asserts only in debug builds a kind enum + a classof per class LLVM, Clang, MLIR, Pebble AST
C++ RTTI any hierarchy incl. multiple/virtual inheritance, cross-casts \(O(1)\)–\(O(b)\); 6.7× slower measured failed cast → null; no per-class code to get wrong none (compiler-generated) general C++ code; not LLVM (-fno-rtti)
std::variant + visit closed sets of value types; exhaustive at compile time (Theorem 10.4.13) \(O(1)\) switch a missing case is a compile error small; clumsy for deep hierarchies small ASTs, tokens, results
InstVisitor per-opcode dispatch with class-level fallbacks (Theorem 10.4.14) \(O(1)\) switch, delegation inlined an unhandled case silently reaches the fallback a class with overrides interpreters, analyses over all instructions, Lab 10.3

Choose LLVM-style RTTI for any hierarchy of heap objects with identity that you own. It is fast and needs no vtable, and it is the idiom every LLVM API expects. Choose C++ RTTI only in code that must interoperate with polymorphic types you do not control. Choose std::variant for small closed value types where exhaustiveness checking is worth more than extensibility. Choose InstVisitor when you handle many instruction kinds with shared fallbacks: the class hierarchy does your case analysis.

The Lab 10.3 comparison: the raw-cast and visitor styles of the reference solution are 92 and 83 lines (solutions/labs/ch10-compare/src/RawCasts.cpp, Visitor.cpp), and they run the corpus in 2.3 and 2.9 ms per 2 000 rounds (ch10-apibench).

9. Assessment

Technique Quiz ids (solutions/quizzes/ch10.yaml) Drill Flashcard tag Exercises
LLVM-style RTTI cast-eval, classof-range, llvm-where-constant-classof ./course drill cast-semantics llvm-rtti Lab 10.3 R1
C++ RTTI value-not-polymorphic, dynamic-cast-cases ./course drill cast-semantics (the same queries answered by dynamic_cast semantics) cxx-rtti —
std::variant + visit variant-exhaustive, variant-cost — (see note) variant —
InstVisitor instvisitor-delegation, instvisitor-memcpy ./course drill cast-semantics (hierarchy reasoning) instvisitor Lab 10.3 R2

std::variant dispatch has no randomizable computation: the index names the handler. The quiz asks what happens when an alternative is added (a compile error) instead.

Pitfall

isa<X>(V) on a null V is not false. It asserts in a debug build and is undefined behavior in a release build. When a value may be absent (getParent() of an unlinked instruction, dyn_cast results passed along, optional operands), use isa_and_present and dyn_cast_if_present. The old names dyn_cast_or_null and cast_or_null still forward to them in LLVM 23.

References

See the chapter references.