Instruction Formats and Operands

Every instruction answers two questions: what operation and on which data. The first is the opcode, a small code naming the operation: add, load, jump. The second is the operands, the names of the inputs and the destination. The deepest structural choice an ISA designer makes is how many operands an instruction is even allowed to name, because that single number determines the size of every instruction, the number of instructions a program needs, and how much hardware the machine must carry. This lesson counts operands by running one tiny computation through four machines, then makes the abstraction physical by laying out real instructions byte by byte.

Opcode plus operands

An instruction is a packed binary word. Conceptually it splits into fields: a field for the opcode and one field per operand. The opcode field's width fixes how many distinct operations the ISA can have ($k$ bits name $2^k$ opcodes); each operand field's width fixes how many things that operand can name. A register operand needs only enough bits to index the register file — four bits for sixteen registers — so register operands are cheap to encode. A memory operand may need a full address, and addresses are wide.

How many operand fields there are is the operand count, and it defines a whole class of machine.

One computation, four machines

Take the most ordinary statement imaginable, C = A + B, where A, B, and C live in memory. Each machine class below computes exactly this, and the contrast is the entire point: as operands per instruction shrink, instructions grow more numerous and lean harder on hidden state. One notational caution: the generic pseudo-assembly here writes the destination first (add C, A, B means $C=A+B$), the usual textbook convention, which is the opposite of the AT&T destination-last order used everywhere else in this course.

3-address machines name every operand. add C, A, B reads A and B, adds them, writes C — one instruction, three operands. This is the most expressive and the most expensive to encode, since three operand fields must fit in the instruction word. Most RISC ISAs are register 3-address: add %rd, %rs1, %rs2.

2-address machines drop the separate destination by making one source double as the destination. add C, B means C = C + B, so reaching C = A + B first requires mov C, A. Two instructions, but each is shorter. x86 is a 2-address machine: addq %rsi, %rdi computes %rdi = %rdi + %rsi, clobbering %rdi.

1-address machines name a single operand and keep the other in a dedicated hidden register, the accumulator. Every arithmetic instruction implicitly reads and writes the accumulator: load A puts A there, add B adds B into it, store C writes it out. Instructions are tiny, one operand each, but a program is a long chain of loads and stores shuttling values through the one accumulator.

0-address machines name no operands at all. Operands live on a stack; arithmetic instructions pop their inputs from the top and push the result back. push A and push B load the stack, add pops two and pushes their sum, pop C stores it. This is how a stack-based virtual machine like the JVM works, and why its bytecode is so compact.

The trade is consistent: fewer operand fields make each instruction smaller and simpler to decode, but force the program to spell the computation out in more steps, leaning on implicit state (an accumulator, a stack) the instruction no longer names.

The one-line example understates the effect; it grows with the expression. Take something slightly larger, E = (A + B) * (C + D), with all five in memory, and count instructions per class. A 3-address machine needs four: two adds into temporaries and a multiply, plus one store — actually three arithmetic and one store if the destination is memory, four in all. A 2-address machine must first mov each accumuland into place before it can overwrite it, roughly doubling the count to seven. The 1-address accumulator threads everything through one register, so it pays a load/store pair around each subexpression: load A, add B, store t1; load C, add D; mul t1; store E — eight. The 0-address stack machine names nothing but pushes every leaf: push A, push B, add, push C, push D, add, mul, pop E — eight again, but each instruction is tiny.

Register operands versus memory operands

Cutting across operand count is a second axis: may an operand live in memory, or must it first be in a register? It matters because the two are not remotely the same speed. A register access is essentially free — the value is right there in the datapath — while a memory access costs many cycles even on a hit and far more on a cache miss.

This is why the register machine won. Modern ISAs give the programmer a generous bank of fast registers and steer almost all work through them. The extreme form is the RISC load/store discipline from the previous lesson: arithmetic instructions take only register operands, and the only instructions that touch memory are explicit load and store. The compiler keeps hot values in registers across long stretches of code, paying for memory traffic only when it must.

Real bytes: one add, two encodings

Fields and operand counts stay abstract until you watch an assembler pack them. Here is the same 2-address register add in the two ISAs this course uses, byte for byte.

In x86-64, addq %rsi, %rdi assembles to exactly three bytes: 48 01 f7. Each byte is a field with a job.

• 48, the REX prefix. Its high nibble 0100 marks it as REX; its low four bits are flags W R X B. Here only W = 1 is set, which promotes the operation to 64 bits. (The R and B bits, zero here, extend the register fields to reach %r8–%r15, the encoding's escape hatch for having sixteen registers but only 3-bit register fields, a seam left by x86's 8-register past.)
• 01, the opcode: add a 64-bit register into a register or memory operand.
• f7, the ModRM byte, which names both operands in one byte: two bits mod, three bits reg, three bits rm. f7 is 11 110 111: mod = 11 says the rm operand is a plain register (not memory), reg = 110 names the source %rsi (register 6), and rm = 111 names the destination %rdi (register 7).

The Y86-64 encoding of the same operation, addq %rsi, %rdi, is two bytes: 60 67. The first byte's high nibble 6 is the instruction code for the arithmetic family, its low nibble 0 selects add; the second byte packs the two 4-bit register IDs, source %rsi = 6 and destination %rdi = 7. Nothing is implicit: with 4-bit register fields there is no REX-style escape hatch to bolt on, and the two operands take exactly the byte they need.

The comparison flips the moment a large constant enters. x86-64's movq $0x100, %rax is seven bytes: REX, opcode, ModRM, then the constant as a 4-byte immediate that the hardware sign-extends to 64 bits, because the encoder exploits the fact that most constants are small. Y86-64's equivalent irmovq $0x100, %rax is ten bytes: its one immediate format always carries a full 8-byte constant, small value or not. That is the density tax of regularity in one example: Y86-64 spends three extra bytes to keep its format count at a handful, while x86-64 spends encoder and decoder complexity to shave them. Neither is wrong; the two designs optimize different costs.

The ModRM byte does more than name two registers, and one more x86-64 example shows where the CISC complexity actually accumulates. A memory operand with an index — movq (%rbx,%rcx,8), %rax, loading a[i] where %rbx is the base and %rcx the index — cannot fit in ModRM alone, because ModRM has three bits for the rm operand and there is no room to name a second register and a scale. So the encoding grows a fourth byte, the SIB byte (scale-index-base), which ModRM's rm = 100 escapes to. The instruction assembles to 48 8b 04 cb: 48 REX, 8b the load opcode, 04 the ModRM (mod = 00, reg = 000 for %rax, rm = 100 meaning SIB follows), and cb the SIB byte (scale = 11 for $\times 8$, index = 001 for %rcx, base = 011 for %rbx). Four bytes to encode one addressing calculation the hardware then performs — base plus index times scale — in the address-generation unit.

Fixed versus variable encoding

The last format choice is whether all instructions are the same length or not, and the x86/Y86 pair above already shows both answers in miniature. A fixed-length encoding — say every instruction exactly 4 bytes — makes the hardware that fetches and decodes instructions simple and fast. A variable-length encoding lets each instruction be exactly as long as it needs: 1 byte for a push, three for an add, seven or more for an instruction hauling a constant.

The cost of variable length is paid at fetch, before decoding proper even starts. The front end pulls a block of bytes from the instruction cache and must find where each instruction begins; with variable lengths, instruction $n+1$'s start is a function of instruction $n$'s length, so boundary-finding is serial by nature, and hardware that decodes several instructions per cycle has to guess boundaries speculatively and discard the misses.

What variable length buys back is density, and the previous section priced it: one byte for the hottest instructions, three for a typical add, with long forms reserved for the rare constant-heavy cases. Fixed length pays four bytes for everything and wastes bits on a nop; in exchange the fetch stage is trivial and the decoders run fully in parallel. This is precisely the RISC/CISC split of the previous lesson showing up at byte granularity. The Y86-64 ISA we build in this module takes a middle road (variable lengths, but only a small set of formats, from 1 to 10 bytes, so an instruction's first byte alone determines its length), and the next lesson fills in the remaining piece: once an operand field names a memory location, exactly how does it compute the address it reaches?

Operand count in modern ISAs

CS:APP presents the operand-count taxonomy on small classical machines. It maps cleanly onto ISAs shipping today, and one modern wrinkle is worth knowing.

The destructive-two-address tax. x86's 2-address form, where the destination overwrites a source, is not free: a compiler that needs both a and a + b afterward must insert a mov to preserve a before the add clobbers it. On code heavy with common subexpressions this is a measurable stream of copy instructions. RISC ISAs avoid it by being 3-address throughout — add rd, rs1, rs2 leaves both sources intact — which is one reason ARM64 and RISC-V code, despite fixed 4-byte instructions, is not as much larger than x86 as the byte-per-instruction figures alone suggest: it needs fewer instructions because it wastes none on preservation copies.

Why vector x86 went 3-address. The clearest evidence is inside x86 itself. When Intel and AMD extended the vector unit, the old 2-address SSE form mulps xmm1, xmm2 (which computes xmm1 = xmm1 * xmm2, destroying xmm1) became a bottleneck for exactly the copy-insertion reason above, in the innermost loops where it hurts most. So the AVX encoding introduced in 2011 added a new prefix — the VEX prefix — whose entire purpose is to carry a third register field, turning the instruction non-destructive: vmulps xmm0, xmm1, xmm2 computes xmm0 = xmm1 * xmm2 and leaves both sources alone.¹ A CISC architecture, having spent decades 2-address, paid real encoding bytes to buy back the 3-address form for its performance-critical instructions. The operand-count choice this lesson frames as a one-time design decision turns out to be one an ISA can revisit — at a price — when the workload makes the old choice expensive.