Type Feedback and Inline Caches in Dynamic Call Sites

A call site in a dynamically typed language is an unresolved question at every execution. The code says “call this function with these arguments”; the values at run time determine what the operation actually does. A compiler that guesses wrong must emit a dispatch sequence, and a compiler that knows the answer can emit a direct call. The mechanism that turns a sequence of observations into that knowledge is an inline cache, and the record it produces is what the optimizing compiler consumes.

The Cache as a Self-Modifying Call Site

An inline cache starts as a stub that, on first execution, looks up the correct target the slow way and then rewrites the call site to check that same case directly. The rewrite is the defining move: the call site’s own instructions are patched so that subsequent executions take a fast path that compares a type identifier and jumps to the target, falling back to the slow lookup only on a mismatch.

The comparison is on an identity rather than a name. Each object carries a reference to a type descriptor, which may be a class, a shape, or a map, and the cache compares the object’s descriptor pointer against one it has recorded. Pointer comparison is one load and one branch, far cheaper than a name lookup in a table. In a virtual machine whose objects have a header containing a class pointer, the check is a load from a fixed offset and a compare, which is what makes the fast path viable inside a per-call sequence.

When the site sees a second type, it has a choice. It can chain a second entry onto the first, producing a polymorphic inline cache; it can give up and call a general dispatch routine, producing a megamorphic site; or it can keep the original entry and treat the new type as a miss that always takes the slow path. The chain is the usual design, with a small limit, often four entries or fewer, after which the site is declared megamorphic and the cache is replaced by a stub that performs full lookup.

The limit exists because the fast path’s cost grows linearly with the number of entries, and a site that checks eight type descriptors per call is slower than a direct table lookup. The crossover is a few entries in practice, and the exact number is a tuning parameter rather than a law.

// A source-level model of a two-entry polymorphic inline cache.
function makeSite(computeSlow) {
  let shape0 = null, target0 = null;
  let shape1 = null, target1 = null;
  return function call(receiver, ...args) {
    const s = shapeOf(receiver);         // one load from the object header
    if (s === shape0) return target0(receiver, ...args);
    if (s === shape1) return target1(receiver, ...args);
    const [shape, target] = computeSlow(receiver);   // full lookup, then patch
    if (shape0 === null) { shape0 = shape; target0 = target; }
    else { shape1 = shape; target1 = target; }
    return target(receiver, ...args);
  };
}

The stub above holds two entries and overwrites the second when a third shape arrives, so a site that alternates among three shapes never stabilizes: the third shape misses on every call and pays the full lookup each time. Real caches either promote to a small hash table of shape-to-target pairs or reset the cache on overflow, accepting the cost of relearning so that the common case stays fast.

From Cache to Feedback

A cache serves execution; a compiler needs a record. The same observations that populate the cache can be summarized for the compiler as feedback: at this call site, the receiver has been type A some number of times and type B some other number of times. The JVM’s approach makes this explicit with a per-call-site profile that counts receiver classes, and the optimizing compiler reads those counts to decide between a monomorphic direct call, a bimorphic comparison chain, and a generic dispatch.

The counts matter as much as the identities. A site that has seen type A a thousand times and type B once is a monomorphic site with a rare exception, and the compiler should specialize for A with a guard that deoptimizes when B arrives, rather than emit a two-way comparison. A site that has seen both types with comparable frequency is genuinely bimorphic, and a two-way inline cache is the right generated code. The distinction changes the guard structure, which is why guard placement depends on the profile and not just on the set of types seen.

Feedback is also attached to branches. A conditional whose true side has been taken every time can be laid out with the false side out of line, keeping the hot path contiguous and improving instruction-cache locality. A branch with a fifty-fifty split should not be laid out that way, since the out-of-line path then costs a taken branch every other execution. The same counting machinery serves both uses.

Why Monomorphism Changes the Code

The payoff from monomorphic feedback is not merely a saved comparison. When the compiler knows the receiver’s exact type at a call site, it can inline the callee’s body, and once inlined the callee’s field accesses become accesses at known offsets rather than lookups. That is the difference between a sequence of dependent memory loads and a handful of arithmetic instructions on values already in registers.

Consider a loop calling a method on each element of a collection. With no feedback, every iteration performs an indirect call through a dispatch mechanism, and the callee cannot be optimized in the caller’s context. With monomorphic feedback and a successful inline, the loop body contains the callee’s instructions directly, the field offsets are constants, and the compiler can hoist invariant loads out of the loop. The speedup is a factor, not a percentage, and it comes from removing an entire layer of indirection rather than from a better implementation of the same layer.

The inline cache and the optimizing compiler thus form a pipeline: the cache keeps interpreted execution acceptable while it learns, and the accumulated learning is what makes the compiled code specialized. A runtime without caches can still compile, but its compiled code must implement general dispatch, and the result is not much faster than a good interpreter.

Megamorphism and Its Costs

A site that sees many types defeats the cache. The general dispatch path may involve a hash lookup on the type name, a search through a method table, or a full run-time resolution, all of which are expensive relative to the cached path. Megamorphic sites are common in generic collection code, where a single implementation is used with many element types, and in code that treats heterogeneous records uniformly.

Two responses exist. The first is to make the general path faster: a per-type method table indexed by a small integer slot number turns lookup into an array access, so the fallback is a load plus a call rather than a search. The second is to avoid the polymorphism at the source, by duplicating the generic code per type. Both cost something: the first requires slot numbers to be assigned and stable, and the second multiplies code size.

A subtler problem is that a site’s polymorphism is often a property of the program’s phase rather than of the site. A function may be called with one type during initialization and another type during the main loop. A profile collected across both phases records a polymorphic site, and the compiler generates a two-way cache that is worse than either monomorphic version would have been. Runtimes address this with per-phase profiling or with recompilation after the site’s behaviour changes, which is one reason recompilation policy is not a one-shot decision.

Correctness Under Changing Types

The cache’s fast path is a bet that the type will not change. When the bet fails, the check fails, and execution takes the slow path. This is safe by construction because the check is on identity and the slow path recomputes the answer.

The compiled code that consumes the feedback is not automatically safe. An optimizing compiler that inlined a callee based on a monomorphic profile must insert a guard at the inlined entry, checking that the receiver still has the profiled type. Without that guard the inlined body would execute field accesses at offsets the actual object does not have, reading arbitrary memory. The guard converts a wrong bet into a deoptimization, and the machinery that recovers from it is frame state reconstruction.

Two failure modes follow. If the guard is too coarse, checking a supertype rather than the exact type, the inlined body may still be wrong for a subtype that overrides the inlined method, so guards must check the precise condition the inlining assumed. If the guard is too fine, it fails on every subtype that does not override anything, producing deoptimizations where a slightly wider check would have been correct. Getting this boundary right is one of the places where an optimizing JIT’s correctness argument is most delicate, and it is why the set of assumptions an inlined body makes is recorded explicitly rather than left implicit in the compiler’s logic.