Opcode Space Allocation and How Extensions Claim Encodings

An opcode is a name for an operation, and the set of all opcodes is a finite resource that every version of an architecture must divide among the operations it defines. The division is not done once. It is done at design time for the base instruction set, then renegotiated with every extension, and the history of those renegotiations is written into the encodings that survive. A byte that means one thing on a 1978 processor and something else on a 2020 one, with the old meaning still required to work, is the normal condition of a mature instruction set rather than a defect.

Understanding how the space is allocated explains a class of behaviours that otherwise look arbitrary: why one instruction needs a two-byte escape, why some bit patterns are guaranteed to fault, and why a new extension can sometimes be added without touching existing binaries and sometimes cannot.

A fixed map and a hierarchical one

The simplest allocation gives the opcode field a flat range and assigns each value to an operation. The RISC-V base ISA does this with a seven-bit major opcode: 0x33 is the register-register integer operation, 0x13 is register-immediate, 0x03 is load, 0x23 is store, 0x63 is branch, 0x6F is jump-and-link. Within 0x33, a three-bit field and a seven-bit field select the operation, giving a two-level tree whose leaves are the actual instructions.

The flat scheme’s advantage is that decoding is shallow: the major opcode tells the pipeline which execution unit the instruction belongs to, and the pipeline can begin dispatching before the rest of the fields are examined. The disadvantage is granularity. With 128 major opcodes, an extension that needs one new instruction consumes a whole major opcode, which is wasteful when the extension is small.

The hierarchical scheme, which x86 and AArch64 both use in different forms, allocates the top level coarsely and subdivides aggressively. x86 has a one-byte opcode map of 256 values, and a set of those values are escape bytes that shift the decoder into a second, third or fourth map. 0x0F is the two-byte escape, 0x0F 0x38 selects one extension map, 0x0F 0x3A another, and the VEX and EVEX prefixes open further maps with their own field widths. The decoder therefore has a state machine rather than a table lookup, and the state machine is what makes it possible to keep adding instructions to a byte-wide map for four decades.

AArch64 takes a third approach: the top bits of the thirty-two-bit word select an encoding group, and each group has its own internal layout. The groups are defined by the architecture’s own classification rather than by an escape convention, so a group can have fields at positions that would be illegal in another group. The cost is that the decoder’s first step is a comparison against a set of group masks rather than a shift and a table index. The register numbers still occupy the same five-bit slots in most groups; the constraint that Fixed-Width Instruction Encoding and Where the Fields Go explains is a hardware requirement rather than a stylistic one.

What a reserved encoding is worth

Every mature ISA reserves a fraction of its encoding space for future use, and the reservation is a promise with conditions attached. RISC-V reserves four major opcodes, 0x0B, 0x2B, 0x5B and 0x7B, for custom extensions, so a vendor can add instructions in those slots without any risk of colliding with a future standard extension. The base specification also defines several fields as reserved, meaning the encoding must not be generated by a conforming compiler and its behaviour is unspecified.

The value of a reserved encoding is entirely in the guarantee. An encoding that is merely undefined can be assigned by anyone, and a program that uses it has no portability. An encoding that is reserved for a named purpose can be used by the party that owns it, and everyone else knows to leave it alone. The distinction matters because binary translation and emulation depend on it: a translator that sees an unknown opcode in a reserved slot can report a precise fault, while an unknown opcode in an undefined slot must be treated as potentially meaningful on some other implementation.

Reservation also has a failure mode. If an architecture reserves a large block and then never uses it, the space is wasted; if it unreserves the block later, every binary that relied on the reservation is now either illegal or ambiguous. The usual resolution is to keep the reservation and define a new extension point elsewhere, which is why architectures accumulate escape mechanisms rather than reclaiming space.

Escape bytes and the cost of a second map

An escape byte converts one opcode value into a prefix that redefines the meaning of the following byte. The mechanism is cheap in encoding terms: one byte buys 256 new opcodes. It is expensive in decode terms, because the decoder must recognise the escape before it can classify the instruction, and recognition is a comparison against a small set of values on the critical path.

x86’s two-byte escape illustrates the accumulation. The 0x0F map was introduced to extend the original one-byte map and now contains system instructions, conditional moves, bit operations and the first level of SIMD. When it filled, 0x0F 0x38 and 0x0F 0x3A were defined as three-byte escapes with different operand conventions: the 0x38 map takes a ModR/M byte and no immediate, the 0x3A map takes a ModR/M byte and an immediate. When those filled, the VEX prefix replaced the escape-plus-prefix combination with a two- or three-byte prefix that carries the opcode map selector as a field, and EVEX extended the same idea to four bytes with more register bits.

Each generation of escape costs the decoder one more level of indirection and one more byte in the instruction stream. The bytes matter: a three-byte escape plus a ModR/M byte plus a displacement can push an instruction past the fifteen-byte architectural limit, and the limit exists precisely because the decoder cannot be asked to handle unbounded length, which is the front-end argument set out in Decode Bandwidth and the Cost of Instruction Length.

/* Classify the first byte of an x86 instruction. Real decoders
   handle prefixes, but the escape structure is what matters here. */
static int map_of(const uint8_t *p, size_t n, size_t *len)
{
    if (n >= 2 && p[0] == 0x0F) {
        if (n >= 3 && p[1] == 0x38) { *len = 3; return 1; }  /* 0F 38 */
        if (n >= 3 && p[1] == 0x3A) { *len = 3; return 2; }  /* 0F 3A */
        *len = 2; return 0;                                   /* 0F */
    }
    *len = 1;
    return 3;                                                 /* one-byte map */
}

The n checks are not defensive padding. A truncated instruction at the end of a page must be detected before the decoder reads past it, and the fault must be reported as an instruction fetch fault rather than as a data access to an unmapped page. Every variable-length decoder has this structure somewhere, and it is one of the reasons the front end is more complicated than the execution units it feeds.

Overlapping meanings and the mode bit

The hardest allocation problem is not running out of opcodes but assigning a second meaning to an opcode that already has one. Two mechanisms are common.

The first is a mode bit that changes the interpretation of the whole instruction stream. x86’s code segment descriptor has a default-operand-size bit, and in 64-bit mode several opcodes change meaning outright: the one-byte 0x40–0x4F range, which encodes single-byte inc and dec in 32-bit mode, becomes a set of REX prefixes that extend the register fields. The same byte is a prefix in one mode and an instruction in another, and the decoder selects between them from a bit that is not in the instruction stream at all.

The second is a feature-dependent meaning, where an extension reuses an encoding that the base architecture defined as reserved. RISC-V’s compressed extension does this with the low two bits of a halfword: in the base ISA every instruction is four bytes and the low two bits are always 11, so any halfword whose low bits are not 11 is illegal. The compressed extension assigns meanings to those patterns. A processor without the extension traps on them; a processor with it executes them. The encoding was reserved, so nothing that worked before stops working.

The mode bit is more dangerous than the feature bit because it is invisible in the instruction stream. A disassembler given a byte sequence with no indication of the current mode will produce a plausible and wrong listing, and a binary translator that forgets to track the mode will mistranslate prefixes as instructions. Architectures that avoid mode bits — AArch64 has a single instruction set for the application level — pay for it by having no way to reuse an opcode, and therefore by needing more escape structure when the map fills.

When the map is genuinely exhausted

Sooner or later an architecture reaches a point where the remaining unassigned encodings are not enough for the operations it wants to add. Three responses exist, and each has a cost.

The first is to add a new instruction length. This is what the compressed extension does in the other direction, and what a hypothetical longer encoding would do: it opens an entirely new map at the cost of making the decoder’s length determination harder. The second is to move functionality out of the instruction set and into a co-processor interface, which is how some architectures handle vector and cryptographic operations that would otherwise need many opcodes. The third is to accept that the instruction set is complete and express new operations as sequences of existing ones, which is what happens to most proposals that do not fit.

The third response is more common than it appears. A multiply-accumulate that does not fit in the encoding becomes a multiply followed by an add, and the compiler is responsible for scheduling them; the hardware does not need a new opcode, and the software pays one extra instruction per operation. Whether that is acceptable depends on the operation’s frequency, which is exactly the kind of judgement that cannot be made from the encoding alone.

Allocation failures that reach the programmer

Opcode allocation is invisible until it is not. Three situations expose it.

A compiler that emits an instruction from a newer extension produces a binary that faults on an older processor with an illegal-instruction trap at the first occurrence. The fault is precise and the instruction is identified, but the program has no recovery path unless it checked for the feature first. This is why feature detection is a normal part of process startup on extensible ISAs, and why the detection mechanism itself is usually the first thing an architecture defines.

An emulator that implements the base ISA but not an extension must decide what to do with the reserved encodings. Trapping is correct; silently treating them as no-ops is not, because the program will proceed with wrong results instead of a clean failure. The same requirement drives the run-time feature detection described in ISA Families, Extension Levels and Binary Compatibility.

A binary translator that rewrites instructions must preserve the escape structure exactly, including prefixes that have no effect on the current processor but are architecturally required to be ignored. Dropping a redundant prefix changes the instruction’s length in the original stream and can break a subsequent jump into the middle of the translated region, which is why translation units are usually bounded at basic-block boundaries that the original code cannot jump into.

The encoding map is therefore not just a naming scheme. It is a contract about which byte sequences are legal, which are reserved, and which are guaranteed to fault, and every tool in the chain depends on that contract being stable across decades.