Decode Bandwidth and the Cost of Variable Instruction Length

The front end of a processor has one job that scales badly: find the boundaries between instructions. Every stage after decode works on a single instruction and can be replicated as wide as the issue width allows, but the boundaries must be discovered in the byte stream before anything can be dispatched. A fixed-width encoding makes that discovery free, because the boundaries are at every fourth byte. A variable-length encoding makes it a data-dependent scan, and the scan is the reason x86 front ends are built differently from every other part of the machine.

The boundary problem stated precisely

Given a byte stream and no side information, a variable-length decoder must determine the length of the instruction at the current position before it can find the next instruction. The length is a function of the bytes: prefix bytes extend it, opcode escapes extend it, the ModR/M and SIB bytes may or may not be present depending on the opcode, and a displacement and an immediate may follow.

x86 imposes a hard limit of fifteen bytes per instruction, which is the only thing that makes the scan bounded. Without the limit, a stream of prefix bytes would have no defined length, and the decoder could not be asked to guarantee termination. The limit is architectural and every conforming implementation must fault on an instruction longer than fifteen bytes; the fault is a general-protection exception rather than a fetch fault, because the bytes were fetched successfully.

A fixed-width ISA has none of this. In AArch64 the instruction at address p ends at p + 4, and the instruction at p + 4 begins there. The fetch unit can read sixteen bytes and know it holds four instructions, a regularity that Fixed-Width Instruction Encoding and Where the Fields Go shows is bought at the cost of field rigidity. RISC-V’s base ISA is the same until the compressed extension is enabled, at which point the low two bits of each halfword determine whether the instruction is two or four bytes and the boundary becomes a function of the data again — a small one, with only two possible lengths, but enough to require a prefix-sum over the halfwords.

/* Length discovery for a stream that mixes 16- and 32-bit forms.
   Each halfword's low bits decide whether the next boundary is +2 or +4. */
static size_t advance(const uint16_t *h, size_t i)
{
    return ((h[i] & 0x3) == 0x3) ? i + 2 : i + 1;   /* units of halfwords */
}

Fixed width buys parallel decode

Because the boundaries are known, a fixed-width front end can instantiate several decoders and feed each one a slice of the fetched block. Four decoders, each taking four bytes, decode four instructions per cycle from a sixteen-byte fetch. The decoders are identical, the wiring is regular, and the only cross-instruction work is the branch resolution that determines whether the fetch block is the right one.

The scaling is nearly linear in the number of decoders until other limits bind. The first limit is the fetch bandwidth from the instruction cache: sixteen bytes per cycle is a common figure for a four-wide machine, and a wider machine needs either a wider cache port or a longer fetch block. The second is the instruction cache’s line size, which is 64 bytes on the common architectures, so a sixteen-byte fetch is a quarter of a line and four fetches consume one line. The third is that taken branches break the alignment: a branch target at a non-zero offset within the fetch block wastes the instructions before it, and a fixed-width machine cannot re-align the block without refetching.

AArch64 and RISC-V (without compression) sit at four instructions per cycle for a sixteen-byte fetch. Wider machines exist and pay for a wider fetch port. The decoder’s cost per instruction is a set of fixed-position field extractions, which is a handful of gates and a small table lookup for the opcode.

Variable length buys density and costs the scan

The x86 front end cannot instantiate four independent decoders and hand each one four bytes, because it does not know where the second instruction starts. The classic solution is a staged decoder: one stage determines the length of the first instruction, a second determines the length of the second given the first, and so on. A four-wide decode then requires four dependent length determinations, which is a serial chain.

The chain is what limits decode width. The length determination for instruction n depends on the bytes of instructions 1 through n−1, so a four-wide decoder has four levels of logic before the fourth instruction’s fields are known. Implementations mitigate this in several ways, none of which removes the dependency.

The first is a predecode stage that annotates the instruction cache with length and boundary information when a line is filled. The annotation is computed once per line fill and reused for every subsequent fetch from that line, which amortises the serial scan over the line’s lifetime. The cost is extra bits per instruction byte in the cache and a fill path that is slower than a plain copy.

The second is to decode only the first instruction’s length in the fetch stage and to let the rest of the pipeline work on a queue. The queue absorbs the variable-rate production and lets the back end consume at a steady rate as long as the average decode rate exceeds the average consumption rate. This is why x86 machines carry large instruction queues: the queue is the buffer that converts a bursty front end into a smooth back end.

The third is to cache decoded instructions in a structure that holds them in a fixed internal form, so that a hit bypasses the variable-length stream entirely. Every modern x86 core has such a structure, and its hit rate on loop-heavy code is high enough that the decode bottleneck applies mainly to code that runs once.

Where the two designs actually land

The comparison that matters is not decode width in isolation but the sustained rate of instructions delivered to the back end, per unit of cache and per unit of energy.

A fixed-width machine with four decoders delivers at most four instructions per cycle, and it delivers them whenever the fetch stream is aligned and predicted correctly. Its instruction cache holds fewer instructions per byte than a dense variable-length cache does, because the average fixed-width instruction is four bytes and the average x86 instruction is closer to three. For a given cache size, the fixed-width machine holds roughly three-quarters as many instructions, so it refetches more often for the same working set.

A variable-length machine delivers fewer instructions per cycle from its decoders but holds more instructions per cache line. The product of the two is what determines performance, and it depends on the code: dense code that fits in cache favours the variable-length machine’s capacity, while code with a large instruction footprint and predictable control flow favours the fixed-width machine’s width.

The decode-cache structure changes the balance. Once instructions are in the decoded form, both machines deliver at the width of the decoded cache rather than the width of the decoders, and the variable-length machine’s disadvantage disappears for the code that hits. This is why the variable-length penalty is concentrated on cold code, on code with many taken branches that flush the decoded cache, and on code whose instruction mix defeats the predecode annotation. Long vector encodings make the pressure worse, since SIMD Encoding shows that a single masked 512-bit operation can occupy ten bytes or more.

Alignment, fetch blocks and the cost of a taken branch

Both designs pay for a taken branch, but they pay differently.

A fixed-width machine’s fetch block is aligned to a multiple of its size, and a branch target within the block means the instructions before the target are wasted. If the target is at offset twelve in a sixteen-byte block, three of four instruction slots are discarded. A variable-length machine’s fetch block starts at the target and the decoder scans from there, so the waste is a partial instruction rather than whole slots, but the scan has to restart.

The asymmetry favours the fixed-width machine when branch targets are aligned, which they usually are because the ISA requires it. AArch64 requires four-byte alignment for every instruction and every branch target, so a target is always at a block boundary of four bytes. RISC-V with compression allows two-byte targets, and the fetch block must be able to start at an odd halfword, which means the fetch unit’s alignment logic is more complex.

The instruction cache’s line size interacts with this. A 64-byte line holds sixteen fixed-width instructions or a variable number of x86 instructions. A taken branch to an address in the middle of a line fetches the whole line, and the line is then available for subsequent fetches that fall inside it. For a loop whose body is smaller than a line, the whole loop is fetched once and the branch is resolved from the decoded cache thereafter, which is why loop-heavy code is insensitive to the front end’s design.

What the encoding forces on the rest of the machine

The length decision propagates beyond the front end.

A fixed-width machine can compute the address of the instruction after the current one by adding four, which means a return address is a simple increment and a call instruction does not need to save anything extra. A variable-length machine must save the actual address, and a call instruction that pushes a return address pushes a value the front end computed rather than one the ISA defines.

A fixed-width machine can speculatively fetch the next sequential block before the current one is decoded, because the next block’s address is known. A variable-length machine can do the same, but the block boundary is not an instruction boundary, so a fetch that starts at the block boundary may start in the middle of an instruction. The fetch unit must then carry the partial instruction across the boundary, which is a state that a fixed-width machine does not need.

A fixed-width machine’s branch predictor can index on the low bits of the address with the knowledge that the bits are instruction-aligned. A variable-length machine’s predictor sees addresses with no such structure, and the low bits carry less information per index bit.

None of these make one design correct and the other wrong. They make the front end’s complexity a function of a decision made when the ISA was defined, and they explain why an ISA’s age shows most clearly in the parts of the machine that have to find instruction boundaries rather than in the parts that execute them.