Instruction Formats and Encoding

An instruction encoding is a mapping from a bit string to a fully specified machine operation: which functional unit activates, which registers or memory locations are read and written, and what constant operand (if any) participates. Each encoding partitions the instruction word into fields — contiguous or split groups of bits with fixed semantic roles. The three field families that appear in essentially every ISA are the opcode (identifies the operation, and often the format itself), register specifiers (index into the register file to select source and destination operands), and immediates (constant values embedded directly in the instruction, avoiding a separate memory or register access). The central design tension is fixed-length versus variable-length encoding. A fixed-length format — every instruction occupies exactly 32 bits, say — lets hardware know the instruction boundary before decoding a single field: the next instruction always starts 4 bytes later. This determinism is what makes deep, simple pipelines tractable, because instruction fetch never needs to inspect earlier instructions to know where the next one begins. A variable-length format lets common, simple instructions (like "increment a register") occupy one or two bytes, while rare, complex instructions occupy many more — shrinking overall code size, which matters for instruction-cache hit rates and memory bandwidth, but forcing the decoder to determine each instruction's length before it can even locate the next opcode. A second axis is format regularity — how many distinct field layouts the ISA defines, and whether a given field (say, the destination register) sits in the same bit positions across every format. High regularity means one small piece of hardware can extract "the destination register" for any instruction without knowing the opcode first, which shortens the critical path in decode and is a hallmark of RISC design tied to RISC versus CISC Design Philosophies. Low regularity (opcode-dependent field meanings, optional prefixes, variable field widths) is the norm in CISC ISAs like x86, trading decode simplicity for code density and backward-compatible extensibility.

Step 1 — Reserve an opcode field. Every format begins with a small field, usually a fixed number of bits at a fixed position (often bits [6:0] or [31:26] depending on convention), that names the operation or operation class. Hardware reads this field first, in parallel with everything else, and uses it to select the rest of the decoding logic — essentially a giant multiplexer/demultiplexer keyed on the opcode.

Step 2 — Lay out register-specifier fields at consistent positions across formats. In a well-designed fixed-length RISC ISA, the bits that hold "register rs1" occupy the same position whether the instruction is an add, a load, or a branch, even though these instructions belong to different formats. This lets a single hardwired path from instruction bits to the register file's read-address ports exist unconditionally, without waiting to know the opcode. This is a deliberate, load-bearing design decision, not an accident.

Step 3 — Pack the immediate, splitting and reordering bits as necessary. Immediates rarely fit as a clean contiguous field once register fields have claimed their fixed slots. Real formats scatter immediate bits across several disjoint ranges of the word, and decode hardware reassembles them, inserting sign-extension bits at the top. The scattering looks messy but is chosen precisely so that other fields (registers, opcode) keep fixed positions.

Step 4 — Determine instruction length (variable-length ISAs only). Before any field extraction, a variable-length decoder must consume prefix/length-indicating bits (e.g., x86's legacy prefixes, REX/VEX prefixes, and opcode-length escape bytes) to learn how many bytes this instruction occupies — this step is inherently sequential, because you cannot know where instruction k+1 begins until you have parsed instruction k.

Step 5 — Dispatch to format-specific field extraction. Once opcode (and, for variable-length ISAs, length) is known, combinational logic (a set of shifts, masks, and sign-extension muxes, or in CISC decoders, a microcode/PLA lookup) extracts the semantic fields — source registers, destination register, immediate, function/sub-opcode bits — and forwards them to the datapath. ```pseudocode // Fixed-length RISC-style decode (e.g., RISC-V RV32I, 32-bit word) function decode(instr: 32-bit word) -> DecodedInstruction: opcode = instr[6:0] // always same bits, all formats format = FORMAT_TABLE[opcode] // R, I, S, B, U, or J switch format: case R: // register-register ops rd = instr[11:7] funct3 = instr[14:12] rs1 = instr[19:15] rs2 = instr[24:20] funct7 = instr[31:25] return RType(opcode, rd, funct3, rs1, rs2, funct7) case I: // loads, immediate-arith, jalr rd = instr[11:7] funct3 = instr[14:12] rs1 = instr[19:15] imm = sign_extend(instr[31:20], from_bit=12) return IType(opcode, rd, funct3, rs1, imm) case S: // stores funct3 = instr[14:12] rs1 = instr[19:15] rs2 = instr[24:20] imm = sign_extend(concat(instr[31:25], instr[11:7]), from_bit=12) return SType(opcode, funct3, rs1, rs2, imm) case B: // branches (imm is even, bit0 implicit 0) funct3 = instr[14:12] rs1 = instr[19:15] rs2 = instr[24:20] imm = sign_extend( concat(instr[31], instr[7], instr[30:25], instr[11:8], '0'), from_bit=13) return BType(opcode, funct3, rs1, rs2, imm) case U: // lui, auipc: imm occupies top 20 bits rd = instr[11:7] imm = instr[31:12] << 12 return UType(opcode, rd, imm) case J: // jal rd = instr[11:7] imm = sign_extend( concat(instr[31], instr[19:12], instr[20], instr[30:21], '0'), from_bit=21) return JType(opcode, rd, imm) default: raise IllegalInstructionException ``` ```pseudocode // Variable-length CISC-style decode sketch (x86-flavored, simplified) function decode(byte_stream, start: pointer) -> (DecodedInstruction, next_pointer): ptr = start prefixes = [] while byte_stream[ptr] is a legal PREFIX_BYTE: // sequential — must read to know length prefixes.append(byte_stream[ptr]) ptr += 1 opcode_byte = byte_stream[ptr] ptr += 1 if opcode_byte == ESCAPE_BYTE: // multi-byte opcode opcode_byte = (opcode_byte, byte_stream[ptr]) ptr += 1 op_info = OPCODE_TABLE[opcode_byte] // tells us: needs ModRM? imm size? etc. if op_info.has_modrm: modrm = byte_stream[ptr]; ptr += 1 mod, reg, rm = split_modrm(modrm) if needs_sib(mod, rm): sib = byte_stream[ptr]; ptr += 1 if needs_displacement(mod, rm): disp = read_bytes(byte_stream, ptr, op_info.disp_size) ptr += op_info.disp_size if op_info.has_immediate: imm = read_bytes(byte_stream, ptr, op_info.imm_size) ptr += op_info.imm_size return (assemble(op_info, prefixes, modrm_fields, disp, imm), ptr) ```

Decode time. In a fixed-length, regular RISC encoding, field extraction is a pure combinational function of the instruction bits: bit-slicing, a small number of muxes for sign-extension, and a table lookup (or PLA/ROM) keyed on the opcode to select the ALU control signals. This is O(1) in instruction count and, in circuit terms, has depth proportional to $O(\log w)$ where $w$ is the word width, dominated by the sign-extension/shift network — a handful of gate delays, easily fit within a single clock cycle even at high frequency. Crucially, decode of instruction $i$ never depends on decode of instruction $i-1$, so multiple instructions can be fetched and decoded in parallel — the structural basis for superscalar and pipelined fetch. In a variable-length encoding, determining where instruction $i+1$ begins requires knowing the length of instruction $i$, which in turn may require parsing prefix bytes, an escape opcode byte, a ModRM byte, and a SIB byte in sequence. This makes decode inherently serial across instruction boundaries within a fetch block: in the worst case, determining the length of $n$ consecutive instructions is $O(n)$ sequential steps even though each individual instruction's field extraction is still fast once its boundaries are known. This is precisely why high-performance x86 implementations invest enormous hardware (multiple parallel predecoders, length-prediction caches, micro-op caches that memoize the decoded form) to hide this cost — a direct, measurable consequence of the encoding choice.

Space (code density). Let $k$ be the number of distinct opcodes/operations needed and $r$ the number of addressable registers. A fixed format must reserve $\lceil \log_2 k \rceil$ opcode bits and $\lceil \log_2 r \rceil$ bits per register operand even for the simplest instructions, because every instruction occupies the same width. A variable-length format can give the most frequent instructions the shortest encodings (an idea directly analogous to Huffman/prefix-free coding), so average code size can be provably smaller for a given static instruction mix — this is the formal reason CISC and compressed-RISC (e.g., RISC-V "C" extension, ARM Thumb) encodings shrink binaries relative to naïve fixed-width RISC.

Correctness argument. An encoding is correct if the mapping from bit strings to instructions is a well-defined, decodable function — formally, if the code is uniquely decodable: no valid instruction's bit pattern is a prefix of another valid instruction's bit pattern (for variable length), and every opcode value maps to exactly one format and one field layout (for fixed length). For fixed-width RISC ISAs this reduces to a simple invariant: the opcode field, wherever it sits, must partition the entire opcode space into disjoint format classes, and within a class every field's bit range must be identical for every legal instruction of that opcode. RISC-V's designers verify this by construction — the format table itself is the proof, since decode is a total function from opcode to exactly one of {R, I, S, B, U, J}. For variable-length ISAs, unique decodability is guaranteed by the prefix-code structure of the opcode map (extended by escape bytes), analogous to how Huffman codes guarantee unambiguous decompression — no legal short opcode is a byte-prefix of a legal long opcode.

Honest tradeoffs. Fixed-length encoding wastes bits (an `addi x1, x2, 1` still burns a full 12-bit immediate field and a full 32-bit word) and caps the number of opcodes and register-file size once the format is frozen, constraining future extensibility. Variable-length encoding maximizes density and backward compatibility but multiplies decoder complexity, power consumption in the decode stage, and — because instruction boundaries aren't statically obvious — makes tasks like disassembly, branch-target validation, and even certain security mitigations (control-flow integrity, avoiding "gadget" reinterpretation of byte streams) fundamentally harder, a real-world consequence exploited by return-oriented-programming attacks on x86.

Take the RISC-V instruction `sw x6, 8(x5)` — store the word in register `x6` to memory address `x5 + 8`. This is an S-type instruction. Its 32-bit encoding is: ``` 0000000 00110 00101 010 01000 0100011 imm[11:5] rs2 rs1 f3 imm[4:0] opcode ```

Decode reconstructs the immediate by concatenation: `imm = sign_extend({imm[11:5], imm[4:0]}) = sign_extend(0000000_01000) = 0b0000_0000_1000 = 8`. Since bit 11 (the sign bit of the 12-bit immediate) is 0, sign extension pads with zeros, correctly yielding `+8`. Now contrast with `beq x5, x6, -4` (branch if `x5 == x6` to PC−4), a B-type instruction, to show why immediates get scattered even more aggressively: ``` 1 111111 00110 00101 000 1110 1 1100011 imm[12] imm[10:5] rs2 rs1 f3 imm[4:1] imm[11] opcode ```

Reassembling: `imm = sign_extend({imm[12], imm[11], imm[10:5], imm[4:1], 0}) = sign_extend(1_1_111111_1110_0)`. That's 13 bits `1111111111100` = −4 in two's complement (branch offsets are always even, so bit 0 is implicit and never stored — B-type immediates encode only 12 bits of real information but represent a 13-bit range). Note that `rd` is absent from B-type entirely (branches write no register), yet `rs1` and `rs2` still sit at the same bit positions as in R-type and S-type — the regularity invariant holds even though the immediate bit-scrambling looks chaotic.

The instruction-format problem crystallized as computers moved from single-purpose plugboards to stored-program machines whose "program" was itself just data in memory — the architecture pioneered by John von Neumann's design reports. Once instructions and data shared a common memory and word format, engineers had to decide, once and for all, how many bits an opcode needed, how operands would be addressed, and how much of the word each part would claim. Early machines used generous, uniform fields because memory was scarce and simplicity mattered more than density; the accumulator-based machines of the 1950s typically devoted most of a word to a single memory-address operand plus a short opcode. The RISC/CISC schism of the late 1970s and 1980s, associated with the work of John Cocke, John Hennessy, and David Patterson, turned instruction encoding into an explicit, quantified engineering tradeoff rather than an incidental byproduct of hardware cost. RISC projects (Berkeley RISC, Stanford MIPS) deliberately chose small, fixed sets of instruction formats with rigidly consistent field positions specifically to shrink and simplify the decode stage, enabling the pipelining techniques that came to dominate general-purpose computing.

Instruction encoding decisions are load-bearing in nearly every processor shipped today. ARM's AArch64 and RISC-V both use fixed 32-bit instruction formats precisely to keep fetch and decode simple across pipeline stages, enabling the wide superscalar decode found in modern mobile and server chips. x86-64, still dominant in desktops, laptops, and cloud servers, retains variable-length legacy encoding for backward compatibility, which is why Intel and AMD invest heavily in micro-op caches and complex predecode logic specifically to amortize the cost of repeatedly re-parsing variable-length instruction streams. Compressed instruction extensions — RISC-V's "C" extension, ARM's Thumb/Thumb-2 — deliberately reintroduce controlled variable-length encoding on top of a fixed-length base, targeting embedded and mobile systems where code density (and hence instruction-cache footprint and energy per fetch) dominates over raw decode simplicity. Understanding instruction encoding is also the direct prerequisite for reasoning about Addressing Modes (which fields specify how an operand is located) and for building The Single-Cycle Datapath, where decoded fields become literal control signals wired into muxes, register-file ports, and the ALU.

Ask the tutor: How would you redesign an existing instruction format to add a brand-new opcode without breaking binary compatibility with already-compiled programs?