Optimizeimplementation

Devirtualization

Turn an indirect call through a dispatch table into a direct call to a known function — and then, because the target is known, inline it. The whole value is in that second step; a direct call on its own is barely cheaper than an indirect one.

The question

My hot loop calls a virtual method. Can the compiler turn that into a direct call, and what does it have to know first?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

IR containing an indirect call: a call whose target is a value loaded from memory — a vtable slot, a function pointer, a closure environment — rather than a symbol. That representation is what makes the call opaque: no analysis can see into a callee it cannot name. Devirtualization rewrites the call to name a symbol, which turns an unanalysable edge in the call graph into an ordinary one.

What this phase may assume or do

The compiler must prove that the dynamic target is a specific function on every execution that reaches this call, or else guard the direct call with a check that the receiver is what it assumed and fall back otherwise. Proof comes from: the receiver's dynamic type being known exactly at the call site, the class hierarchy admitting exactly one implementation, or a language rule that forbids further overriding — final, sealed, a non-exported class in a closed world. A profile is not proof; it is evidence that justifies speculation plus a guard.

Key points

The saving from a direct call over an indirect one is small; the saving from being able to inline the now-known target is large.
An indirect call is an optimization barrier: nothing propagates through it, no memory assumption survives it, and a loop containing it will not vectorize.
Static proof comes from exact type knowledge, from final/sealed, or from class-hierarchy analysis in a genuinely closed world.
Dynamic loading breaks the closed-world assumption, which is why a JIT devirtualizes more than a static compiler while proving less — it can take the decision back.
Speculative devirtualization is legal only with a guard, and the guard needs a destination: an else-arm in a static compiler, a deoptimization point in a JIT.
Inline caches are speculative devirtualization done incrementally at run time, and megamorphic sites are where the technique gives up.

What a virtual call costs, and why the cost is not the point

A virtual call in the usual vtable implementation is: load the vtable pointer from the object, load the function pointer from a fixed slot, call through it. Two dependent loads and an indirect branch. On a modern core with an indirect-branch predictor and both loads in cache, that is a handful of cycles more than a direct call — real, but not usually what makes a program slow.

What makes it expensive is that it is an optimization barrier. The compiler does not know which function runs, so it must assume the callee may write to any memory it could reach and clobber every caller-saved register. Nothing propagates through it, no load across it can be reused, the loop containing it cannot be vectorized, and the body cannot be specialized to this caller. The indirect call costs a few cycles and blocks an unbounded amount of optimization.

That is why devirtualization is valuable, and it is also why devirtualization *alone* is nearly worthless. Rewriting the indirect call to a direct call saves the vtable loads. Rewriting it to a direct call and then inlining the target is what removes the barrier. The two transformations are separate and only the pair pays.

Two steps, and the second is where the value is

Before

struct Shape { virtual double area() const = 0; };
struct Square final : Shape {
  double s;
  double area() const override { return s * s; }
};

double total(const Square& sq) { return sq.area(); }

After

// step 1, devirtualize: the static type is Square, which is final,
// so Shape::area resolves to exactly Square::area.
//   call Square::area(&sq)
// step 2, inline the now-known target:
double total(const Square& sq) { return sq.s * sq.s; }

Legal only when

The receiver's static type is Square, Square is declared final so nothing may derive from it and override area, and the reference cannot refer to a more-derived object. The dynamic type is therefore exactly Square on every execution, and the target is a single known function — which then becomes an ordinary inlining candidate.

Illegal when

The receiver is a Shape& and the program may load a shared library at run time that defines another Shape. The set of possible targets is not closed, so no static proof exists; the compiler may still speculate on the type it has seen, but only behind a guard that checks the vtable pointer and branches to the indirect call when it does not match — see [[guards]].

The three ways a compiler gets to a known target

implementationHotSpot performs class-hierarchy analysis at run time and records a dependency, so that loading a class which invalidates the assumption triggers recompilation of the affected methods. A static C++ compiler has no such mechanism, which is why identical-looking code is devirtualized in Java and not in C++ — the difference is the ability to take it back, not the sophistication of the analysis.

The first is exact type knowledge. The receiver was constructed in this function, or came from a new the compiler can see, or has a static type that is final. Then there is nothing to prove and the call is direct.

The second is class-hierarchy analysis: enumerate every class in the program that overrides this method, and if there is exactly one, the target is known. This is sound only in a closed world — and the world is closed only if nothing can be added later. C++ with dynamic linking is not closed; C++ with -fwhole-program or LTO and no dlopen is closer; Java is not closed because classes can be loaded at run time, which is why the JVM must be able to *undo* a devirtualization when a new class is loaded.

The third is speculation. Measure which target is taken, emit a check against that target, call it directly when the check passes, and fall back to the indirect call when it does not. That is what an inline cache is, and what a JIT does routinely: the guard is cheap — a comparison of a type word — and the payoff is that the guarded direct call can then be inlined. A static compiler can do a version of this with profile data, emitting if (target == Known) Known(x); else (*target)(x); — a transformation usually called indirect-call promotion.

What each language and toolchain can actually proveimplementation

Setting	Where the proof comes from	What defeats it
C++, single TU, `final` classspec	The language: nothing may override a `final` method	Nothing — this is a genuine static proof
C++, LTO, no dynamic loadingimplementation	Class-hierarchy analysis over the whole program	`dlopen` of a library defining another override; the closed-world assumption is then false
C++, separate compilation	Only exact-type knowledge at the call site	Any receiver whose dynamic type is not visible in this translation unit
Java / HotSpotimplementation	Class-hierarchy analysis at run time, plus observed receiver types	A class loaded later that overrides the method — handled by invalidating the compiled code and deoptimizing
JavaScript / V8implementation	Inline caches recording the hidden classes actually seen at this site	A site that sees many shapes becomes megamorphic and stops being specialized at all
Rust, `dyn Trait`	Exact type at the call site, or monomorphization avoiding the vtable entirely	A `dyn Trait` whose concrete type is genuinely dynamic — the vtable call stands

Speculation needs a guard, and a guard needs somewhere to go

The speculative form of devirtualization is the interesting one because it is where compiler and runtime meet. The compiler emits a check — compare the receiver's type word against the expected one — and the direct, inlined body behind it. When the check fails, something must happen, and what that something is defines the system.

In a static compiler, the fallback is simply the original indirect call, sitting in the else arm. The cost is one comparison and a slightly larger function; the benefit is that the common path is inlined and optimizable. This is indirect-call promotion, and it is what a C++ compiler does with profile data.

In a JIT, the fallback can be much more aggressive: the compiled code can contain no fallback at all, and the guard branches to a deoptimization point that reconstructs the interpreter state and resumes there. That is why a JIT can inline a virtual call *and* propagate constants through it as though the type were certain — it is not obliged to keep a slow path in the compiled code, only a way back. The price is the state map that makes the reconstruction possible, which the compiler must emit and keep accurate through every subsequent transformation. See [[deoptimization]], [[guards]] and [[inline-caches]].

A monomorphic inline cache handles one type; a polymorphic one handles a small set with a short chain of checks; a site that sees too many becomes megamorphic and reverts to the generic dispatch. That progression is observable in JavaScript performance and is the mechanism behind the advice to keep object shapes consistent.

How it works

The steps, in the order the compiler takes them.

Identify the call as indirect: its target is a loaded value rather than a symbol.
Attempt exact type resolution — is the receiver's dynamic type known at this point from a constructor, an allocation, or a final static type?
If not, consult the class hierarchy for the number of implementations of this method that could apply, and check whether the world is genuinely closed.
If neither yields a unique target, consult profile or inline-cache data for the dominant target, and decide whether the frequency justifies speculation.
For a proven target, replace the indirect call with a direct call to the symbol. For a speculated one, emit a type check, the direct call on the true edge, and either the indirect call or a deoptimization point on the false edge.
Run the inliner over the now-direct call, which is where the payoff is realised, and then re-run simplification on the enlarged function.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

A hot loop is several times slower than the equivalent non-virtual version, and the profile shows the time inside the loop rather than in the callee — the call barrier stopped vectorization, and the missing optimization costs far more than the dispatch.
JavaScript code that was fast becomes slow after a change that adds a field to some objects and not others; the call site went polymorphic and then megamorphic, and the inline cache stopped specializing.
A Java benchmark reports excellent numbers until a second implementation of an interface is loaded, at which point performance drops sharply and stays down: the class-hierarchy assumption was invalidated and the method was recompiled generically.
A C++ program regresses when a class stops being final in a refactor. Nothing else changed; the compiler simply lost its proof and the call became indirect again, taking the inline with it.
Speculation is applied without a guard by a hand-written optimization, and a program calls the wrong method for an object of an unexpected type — a wrong answer with no crash, which is the worst outcome available.

When it helps

Hot paths written against an interface where, in practice, one implementation is used — the extremely common case that makes speculation profitable.
Iterator and callback patterns, where the indirect call is inside the loop and removing it is what allows the loop body to be optimized at all.
Any language with pervasive dynamic dispatch — Java, JavaScript, Python — where devirtualization plus inlining is the single largest source of speedup a JIT provides.

When it hurts

Genuinely polymorphic sites, where a guard adds a check and a branch on every call and fails often enough to pay for itself twice: once in the check and once in the misprediction.
Code size, when speculation duplicates a body at many sites for a target that was already predicted well by the hardware's indirect-branch predictor.

What it costs

Every one of these is paid by something.

Speculative devirtualization buys an inlinable, optimizable call and pays a guard on every execution plus the code size of both paths — and, in a JIT, the ongoing cost of maintaining the state maps that make the guard's failure recoverable.
Class-hierarchy analysis buys precise proof and costs whole-program visibility: it requires LTO or a closed world, both of which cost build time and rule out dynamic loading.
Marking classes final buys devirtualization and costs extensibility — a real API decision, not a free annotation, and one that is hard to reverse once published.

What else you could do

What a different compiler or language does instead, and when that is better.

Avoid the dynamic dispatch: static polymorphism through templates or generics resolves the target at compile time by construction, at the cost of code size and compile time — [[monomorphization]].
Use a tagged union or enum plus a switch instead of a class hierarchy. The dispatch becomes a jump table the compiler can reason about and often invert, at the cost of a closed set of cases in the source.
Sort or batch by concrete type so each call site sees one type at a time, which turns a megamorphic site into several monomorphic ones without any language change.
Let the JIT do it: in a managed runtime the profile-driven version is already happening and is better informed than any static analysis — [[speculative-optimization]].

See it for yourself

The flag, dump or tool that shows you this directly.

Clang: -Rpass=devirt and -Rpass-missed=inline together show whether the call was resolved and then whether the resolved target was inlined.
GCC: -fdump-ipa-devirt-details prints each devirtualization attempt and the hierarchy reasoning behind it.
Try the experiment: compile the same class with and without final and diff the assembly. The vtable loads appearing and disappearing is the clearest demonstration available.
HotSpot: -XX:+PrintInlining marks inlined virtual calls and shows when a call site is bimorphic or megamorphic; -XX:+TraceDeoptimization shows the assumption being withdrawn.
V8: --trace-ic prints inline-cache state transitions per site, which is the direct view of monomorphic to polymorphic to megamorphic.

Plausible wrong readings

Stated the way a confident engineer states them.

"Virtual calls are slow because of the extra indirection." The indirection is a few cycles. The cost is the optimization barrier, which is unbounded and does not show up as time spent in the call instruction.
"The compiler can devirtualize whenever there is only one implementation." Only if it can prove there will only ever be one. With dynamic linking, it cannot, which is why the same code devirtualizes under LTO and not under separate compilation.
"A JIT devirtualizes because it has better analysis." It has worse analysis and better information — measured receiver types — plus the ability to undo the decision. Deoptimization is the enabling mechanism, not the analysis.
"Devirtualization made my call direct, so the job is done." A direct call that is not inlined has bought almost nothing. Check -Rpass=inline next.

Misconceptions

The claim, and what is actually true.

Devirtualization is about saving the vtable lookup.

It is about naming the callee so it can be inlined and reasoned through. The lookup itself is minor; the barrier it creates is not.

If only one class implements the interface, the compiler will call it directly.

Only where the world is provably closed. In a separately compiled, dynamically linked program the compiler cannot know that another implementation will not arrive at run time.

Speculative devirtualization is unsafe.

It is safe precisely because it is guarded. What would be unsafe is the same rewrite without the check — and the interesting engineering is in making the guard cheap and its failure recoverable.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

A virtual call does not name the function it calls; it looks the function up at run time. If the compiler can work out which function it will actually be, it can call it by name — and then paste the body in, which is where the real speedup comes from.

practical

If a hot path goes through an interface, check whether the call was devirtualized before assuming the dispatch is the cost. final (C++), sealed (C#, Kotlin), and keeping object shapes consistent (JavaScript) all help the compiler prove what it needs. In managed runtimes, watch for a call site going megamorphic after a seemingly harmless change — that is usually the real regression.

advanced

The frontier is the interaction between speculation and everything downstream. Once a call is inlined behind a guard, later passes optimize the body assuming the guard held, which means every subsequent transformation must preserve enough information to reconstruct the pre-speculation state if the guard fails. That is the state map: a mapping from optimized machine locations back to interpreter frame slots, maintained through inlining, scheduling and register allocation. Emitting it is the compiler's half of deoptimization, and its correctness is much harder to test than the optimization it enables — a wrong state map produces a program that is correct until a guard fails, which may be days into production.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

implementationHotSpot devirtualizes aggressively using run-time class-hierarchy analysis and records a dependency so a later class load can invalidate the compiled method; V8 uses inline caches keyed on hidden classes. A static C++ compiler has neither mechanism and devirtualizes only where it can prove the target, which is why the same source shape performs differently across the two worlds.

specIn C++ the closed-world assumption is not available in general: a translation unit may be linked with another that derives further, and dlopen can introduce overrides at run time. final is the language-level way to say the hierarchy is closed at this point, and it is a promise the compiler is entitled to rely on.

targetHow much an unresolved indirect call costs depends on the indirect-branch predictor. A site that is effectively monomorphic in practice predicts well and costs little in dispatch; the same site on a core with a weaker predictor, or a genuinely polymorphic site, costs a misprediction each time it changes.

If you were asked this in an interview

What does a compiler need to prove before turning a virtual call into a direct call?
Why can HotSpot devirtualize a call that a C++ compiler compiling the same shape of code will not?
You devirtualize speculatively and the guard fails. Walk me through what has to happen next.

Connections

Computer Architecturebranch-prediction speculative-execution instruction-cache

Performancejit-and-warmup cpu-profiling

Domains that do not exist yet

Programming Languages & Runtime Internals — Vtables, hidden classes and the run-time dispatch mechanism itself
How an object finds its method at run time is the runtime's subject. Ours is the compiler-side half: proving the target, emitting the guard, and maintaining the metadata that lets the guess be withdrawn.