Superinstruction Selection and In-Place Opcode Quickening

Dispatch overhead scales with the number of instructions executed, not with the amount of work they perform. That asymmetry is what makes bytecode specialization profitable: if three consecutive instructions that always appear together can be replaced by one, the same work now costs one dispatch instead of three, and the handlers can be merged so the intermediate values never leave machine registers. The baseline this improves on, one indirect branch per opcode through a table of handler addresses, is described in computed goto and direct threading. Two mechanisms exploit the asymmetry. Superinstructions fuse a fixed sequence of opcodes into a single new opcode. Quickening rewrites a general opcode into a specialized one that assumes what the first execution discovered.

Both modify the code array while the program runs. That is what makes them worth doing and also the source of nearly all their complexity.

Fusing pairs, and why pairs are enough

The straightforward fusion takes two opcodes that frequently follow each other and defines a new opcode whose handler does both operations. The handler for LOAD_LOCAL 3; ADD reads local 3, adds the top of stack, and leaves the result, with one dispatch instead of two. The fused opcode needs its own operand encoding, since it must carry the local index that the load required.

Proebsting’s work on superoperators established the selection method: profile the executed opcode sequence, count adjacent pairs, and pick the pairs whose combined execution count is highest, subject to a bound on how much the additional handlers may enlarge the interpreter. The counting is done on a recorded instruction stream, so the selection follows the program rather than a guess about typical code.

Pairs rather than longer sequences are the usual choice for a specific reason. The number of distinct pairs grows as the square of the opcode count, while triples grow as the cube, and the benefit per fusion is roughly the same for each additional opcode removed. Fusing pairs captures most of the available dispatch savings, and it keeps the opcode space and the number of handlers manageable. A format with 200 opcodes has at most 40,000 ordered pairs, of which only a small fraction actually occur; triples would be 8 million candidates.

Fixed superinstructions are the offline variant. The bytecode compiler, knowing the language’s idioms, emits a fused opcode for patterns that are statically recognizable, such as a load followed by a branch or a load followed by a store. This costs nothing at run time and requires no profiling, but it only captures patterns the compiler anticipated and it bloats the opcode set with instructions used by few programs.

The branch target problem

Fusing two instructions into one changes the code layout. The second instruction’s offset disappears, or rather becomes an interior offset of the fused instruction. Any branch that targeted the second instruction now targets the middle of a fused instruction, which is invalid.

Three approaches exist. The first forbids fusion across a branch target: the selector records which offsets are targets and refuses to fuse a pair whose second element is one. This is simple and safe, and it loses exactly the fusion opportunities where a target sits between two otherwise adjacent instructions, which is common at loop headers. The second inserts a no-op or keeps the original opcode as a padding byte so the offset remains valid, which preserves the target but wastes the dispatch saving at that point. The third rewrites the branch targets when fusion happens, which requires knowing every branch that reaches the offset; a linear scan over the code can collect them, but the scan is proportional to code size per rewrite.

The usual production answer is the first: maintain a bitmap of branch targets, built once by scanning the code, and require that neither element of a fused pair be a target except the first. The bitmap is also needed for other reasons, such as exception table lookups, so it is usually already present.

Quickening: replacing an opcode with a faster one

Quickening is a different transformation. The first execution of a general instruction performs the expensive work and then rewrites the instruction in place to a specialized form that skips it. The classic example is a global variable load: the general instruction looks up a name in a module dictionary, finds a slot, and loads from it. After the first execution the instruction can be replaced with a load-from-slot instruction that carries the slot index, so subsequent executions skip the dictionary lookup.

The Java HotSpot virtual machine’s interpreter once rewrote field and method references in place this way, an approach later dropped in favour of recording the resolved reference in a constant pool cache rather than in the code itself; CPython’s specializing interpreter applies the same idea, replacing an adaptive instruction with a specialized one once its guards have held for a small number of executions, with the specialized form carrying a cache entry that holds the resolved target.

The rewrite must preserve the instruction’s length or pad it. Since the specialized form usually needs at least as many operand bytes as the general form, the common approach is to make the general form’s encoding wide enough to hold the specialized operands, and to pad with a no-op if the specialized form is shorter. The interpreter’s dispatch then simply executes whatever opcode now sits at that offset.

#include <string.h>

typedef struct { uint8_t *bytes; uint32_t len; } Code;

/* Rewrite in place: general load-global becomes load-slot. */
static void quicken_load_global(Code *c, uint32_t pc, uint32_t slot)
{
    /* Instruction is 5 bytes: opcode + 4-byte operand. */
    memcpy(&c->bytes[pc + 1], &slot, sizeof slot);
    /* Release store publishes the operand along with the opcode. */
    __atomic_store_n(&c->bytes[pc], OP_LOAD_SLOT, __ATOMIC_RELEASE);
}

/* Reader side: the dispatch fetch must be an acquire load. */
static uint8_t fetch_opcode(Code *c, uint32_t pc)
{
    return __atomic_load_n(&c->bytes[pc], __ATOMIC_ACQUIRE);
}

The ordering of the stores matters. If the operand is written after the opcode, a concurrent interpreter can read the new opcode with the old operand. Writing the operand first and publishing the opcode with a release store ensures that any thread which observes the new opcode also observes the new operand, provided the reader loads the opcode with acquire semantics. This is the same publication discipline used for any immutable structure shared between threads.

Guards and invalidation

A quickened instruction is a bet: it assumes the fact discovered on first execution still holds. Something must notice when the bet is lost. In a global load, the assumption is that the module’s dictionary has not been modified; if another thread adds or deletes a name, or if the module is reloaded, the cached slot becomes wrong.

The standard solution is a version counter per assumption domain. Each module has a version number incremented whenever its dictionary changes. The specialized instruction carries the version it was created under, and the handler compares the current version against the carried one before trusting the slot. If they differ, it takes a slow path, re-resolves, and rewrites the instruction with the new slot and version.

Comparing a version number per execution is much cheaper than a dictionary lookup, but it is not free. Runtimes that want to eliminate it use a different structure: a per-domain list of all instructions that depend on the domain, so that invalidation walks the list once and rewrites or reverts every dependent instruction. That makes the common path a bare load with no check, at the cost of a global write to the code array on invalidation and the memory to store the list.

The choice between per-instruction version checks and per-domain invalidation lists is a latency-versus-throughput trade. The check costs one load and one compare per execution, forever. The list costs nothing per execution but makes invalidation a stop-the-world-ish operation over a set of code locations, which is problematic when the code is shared between threads.

Sharing, thread safety, and the writable code problem

Quickening mutates code. If two threads run the same function, they share the same code array, and one thread’s rewrite is visible to the other. That is acceptable if the rewrite is semantically transparent, which the version-check design makes it: both the general and the specialized form compute the same result, so a thread that sees either is correct. It is not acceptable if the rewrite depends on state that differs between threads.

That constraint rules out some otherwise attractive specializations. A cache that holds a receiver class from the last call site is thread-shared, so two threads calling the same site with different receiver classes will thrash the cache. Runtimes that must support this either duplicate the code per thread or restrict specialization to facts that are thread-invariant, such as the module dictionary slot for a global that no thread mutates.

The write itself needs care even when the semantics are safe. Code pages are usually mapped read-only to catch stray writes, so quickening requires a mapping that permits writes, or a call into the runtime to change the protection for the page. Runtimes that map code read-only therefore batch rewrites into a region-level operation. Processors with separate instruction and data caches also require an instruction-cache flush after modifying code, or at least a synchronization that guarantees the new bytes are visible to the instruction fetch path. On architectures with a unified cache and coherent instruction fetch, the flush is cheap; on others it requires serializing the processor pipeline.

Where specialization stops paying

Each rewrite adds a decision the runtime must maintain: what assumption it encodes, how to test it, and how to undo it. A specialization that succeeds often but fails occasionally is worse than no specialization, because the failure path costs more than the general path it replaced and the thrashing destroys the benefit.

The practical ceiling is that specialization only helps instructions whose general form does real work beyond the operation itself. A plain integer add has no resolution step to skip, so quickening it produces nothing. Instructions that resolve names, check types, or dispatch methods have a substantial general path, and those are where the gains are.

There is also a code-size cost. Every specialized form occupies an opcode slot, and the dispatch table grows. More importantly, each specialized handler is code in the interpreter’s text section, which competes for instruction cache with the rest of the interpreter. A design with 400 handlers, most of them rarely executed, can lose to a design with 200 because the hot handlers no longer fit together. The selection problem is thus a two-sided one: maximize saved dispatches while keeping the hot set of handlers small enough to stay resident.

The interaction with resumable control flow is another limit. A generator or coroutine can suspend in the middle of a fused or quickened instruction, and the suspended state must be expressible in terms of the original instruction’s semantics. Frames that can be resumed are the subject of resumable frames for generators and coroutines.