The Y86-64 Instruction Set

To build a processor from scratch — which the next module does — we need an ISA small enough to hold in our heads and implement in logic, yet rich enough that real programs compile to it. Y86-64 is that ISA: a deliberate simplification of x86-64 that keeps the same register names, the same little-endian byte order, and a recognizable subset of the operations, while throwing out the hundreds of instructions and irregular encodings that make x86 hard to implement by hand. This lesson defines exactly what state a Y86-64 program can see and exactly how every instruction is encoded in bytes — and getting those bytes right is essential, because the processor we build later decodes them literally.

The programmer-visible state

Y86-64's visible state is five things, and an instruction can touch nothing else.

• The fifteen integer registers %rax through %r14, each 64 bits. These are x86-64's registers minus %r15, which Y86-64 omits so the register identifier needs exactly four bits with one code left over to mean no register. %rsp is still the stack pointer.
• The three condition codes ZF (zero), SF (sign), and OF (overflow), each a single bit. An arithmetic instruction sets them from its result; the conditional moves and jumps read them. This is a leaner set than x86's flags, but enough for every signed comparison.
• The program counter PC, the address of the next instruction.
• Memory, the byte-addressable array, little-endian as always.
• The status code Stat, a small field reporting execution state: AOK (running normally), HLT (a halt instruction executed), ADR (an invalid memory address), or INS (an invalid instruction). The processor we build uses Stat to decide whether to keep running.

The instructions and their encodings

Every Y86-64 instruction begins with a single byte split into two nibbles: the high nibble is the instruction code icode, naming the operation family, and the low nibble is the function code ifun, distinguishing variants within a family (the four arithmetic ops, the seven branch conditions, the seven conditional moves). After that first byte come, when the instruction needs them, a register-specifier byte holding two register IDs rA:rB, and an 8-byte constant — an immediate value, a displacement, or a destination address — always stored little-endian.

The register IDs are one nibble each: %rax 0, %rcx 1, %rdx 2, %rbx 3, %rsp 4, %rbp 5, %rsi 6, %rdi 7, %r8 8, %r9 9, %r10 A, %r11 B, %r12 C, %r13 D, %r14 E, and the special code F meaning no register. When an instruction has a register byte but uses only one register, the unused half is F.

The function codes fill in the variants. For the arithmetic family OPq the ifun selects the operation; for jXX and cmovXX it selects the condition, and the two families number their conditions identically.

The rrmovq row is worth a pause: an unconditional move is just the always case of conditional move, so it shares icode 2 with ifun 0. The full one-byte opcodes are then halt 0:0, nop 1:0, irmovq 3:0, rmmovq 4:0, mrmovq 5:0, call 8:0, ret 9:0, pushq A:0, popq B:0.

The stack and procedure instructions carry their exact semantics in the encoding table. pushq rA decrements %rsp by 8, then writes R[rA] at the new top: $R[\text{rsp}]\leftarrow R[\text{rsp}]-8$, then $M[R[\text{rsp}]]\leftarrow R[\text{rA}]$. popq rA reads the top into rA and increments %rsp by 8. call Dest pushes the return address (the address of the instruction after the call) and sets the PC to Dest; ret pops that address back into the PC. One convention question the encoding forces: pushq %rsp pushes the old value of %rsp, the value before the decrement — the ISA must pick an order, and Y86-64 follows x86-64's choice.

Condition codes: how jXX and cmovXX decide

Only the four OPq instructions touch the condition codes. Each one sets all three from its result $t$: ZF if $t=0$, SF if $t<0$ (the sign bit of $t$), and OF if the operation overflowed two's-complement range (for andq and xorq, OF is always cleared). Everything conditional in Y86-64 — every jump, every conditional move — is a Boolean function of those three bits, evaluated at the moment the jXX or cmovXX executes.

Y86-64 has no compare instruction, so the comparison idiom is subtraction: to ask how does %rbx stand relative to %rax?, compute subq %rax, %rbx, which sets the codes from $t=R[\text{rbx}]-R[\text{rax}]$ (and, unlike x86's cmpq, overwrites %rbx with $t$ — the price of the smaller instruction set). The six conditions then read:

The exclusive-or is the interesting part. Naively, less than should just be result negative ($\text{SF}$), and usually it is: with %rbx = 3 and %rax = 5, the subtraction gives $t=-2$, so $\text{SF}=1$, $\text{OF}=0$, and $\text{SF}\oplus \text{OF}=1$ says 3 < 5, correctly. But subtraction can overflow. With %rbx holding the most negative value $-2^{63}$ and %rax = 1, the true difference $-2^{63}-1$ is not representable; the computed $t$ wraps to $+2^{63}-1$, a positive number, so $\text{SF}=0$. The overflow bit corrects the comparison: $\text{OF}=1$, and $\text{SF}\oplus \text{OF}=1$ still reports less than, which is the truth. The xor folds the overflow correction into one gate, exactly the kind of trick that makes the ALU cheap to build.

For example, trace one comparison through the whole chain. Suppose %rbx holds 7 and %rax holds 12, and the code runs subq %rax, %rbx followed by jl target. The subtraction computes $t=7-12=-5$. From $t$: it is nonzero, so $\text{ZF}=0$; it is negative, so $\text{SF}=1$; and $-5$ is well inside two's-complement range, so no overflow, $\text{OF}=0$. The jl condition is $\text{SF}\oplus \text{OF}=1\oplus 0=1$, so the branch is taken — correctly, since $7<12$. Here SF carried the sign of the difference, and OF (zero) confirmed no overflow corrupted it.

cmovXX rA, rB applies the same conditions to data movement: if the condition holds, R[rB] gets R[rA]; if not, the instruction is a no-op. Either way the condition codes are untouched — conditional moves read them, never write them. The point of cmovXX is to replace a short branch (test, jump around a move) with straight-line code, an idiom whose real payoff appears when branch mispredictions start costing pipeline bubbles.

Encode: from assembly to bytes

The encoding rules are easiest to trust once you have walked a real instruction byte by byte. Take irmovq $0x100, %rax — move the immediate 0x100 into %rax. Its icode:ifun is 3:0. irmovq carries a register byte with no source register, so rA is F and rB is the destination %rax = 0, giving F0. Then the 8-byte value 0x100, little-endian, is 00 01 00 00 00 00 00 00.

Now a memory store. The reference gives rmmovq %rsi, 0x8(%rbx) as 40 63 08 00 00 00 00 00 00 00: icode:ifun = 4:0, register byte rA:rB = %rsi:%rbx = 6:3, then the displacement 0x8 little-endian. The same shape holds for rmmovq %rax, 0x8(%rsp): 40, then rA:rB = %rax:%rsp = 0:4 giving 04, then 08 00 00 00 00 00 00 00. The operand order is worth pinning down: for rmmovq rA, D(rB) the source register is rA and the destination is the memory at D + R[rB]; mrmovq reverses it, mrmovq D(rB), rA, loading from memory into rA, but the byte layout — icode:ifun, then rA:rB, then D — is identical.

Decode: from raw bytes back to meaning

The processor runs the same walk in reverse, and so should you. Suppose the fetch unit reads these bytes at the current PC:

50 15 f8 ff ff ff ff ff ff ff

Byte 0 splits into icode = 5, ifun = 0: an mrmovq, so the instruction is 10 bytes long and has both a register byte and a displacement. Byte 1 is 15: rA = 1 = %rcx (the destination of a load) and rB = 5 = %rbp (the base). Bytes 2–9, read little-endian, assemble to 0xfffffffffffffff8, which as a signed 64-bit value is $-8$. The instruction is mrmovq -8(%rbp), %rcx: load the 8 bytes at R[%rbp] $-$ 8 into %rcx. A negative displacement is nothing special — it is just a constant whose high bytes are ff, and reading f8 ff ff ... backwards as 0xff...f8 is the little-endian discipline from the foundations lesson in action.

Notice what made the walk possible: the first byte alone told us the instruction's length. That is by design, and it is the property the fetch stage leans on. From the icode, two yes/no questions — does this instruction have a register byte? does it have an 8-byte constant? — fix the length as $1+r+8c$ with $r,c\in \{0,1\}$: lengths 1, 2, 9, or 10, and nothing else.

Contrast that with x86-64, where the length can depend on everything up to and including the addressing-mode byte, and the appeal of Y86-64 as a machine to implement by hand is plain. These layouts are what the fetch stage of the sequential processor reads to pull out its fields. With the encodings fixed, the next lesson writes complete Y86-64 programs and watches the assembler turn assembly text into exactly these bytes.

How real ISAs handle conditions

Y86-64's condition-code design is a faithful miniature of x86's, and comparing it to what other real ISAs do shows the design space the simplification sits inside.

x86's extra flag, and the missing cmpq. x86-64 has a fourth arithmetic flag Y86-64 drops: the carry flag CF, needed for unsigned comparisons (unsigned below is CF, where signed less is $\text{SF}\oplus \text{OF}$). Y86-64 keeps only the three signed-comparison flags, so it can compare signed integers but has no clean unsigned test — an honest simplification CS:APP notes. x86 also keeps a non-destructive cmpq/testq pair that set flags without writing a result, which is why real code rarely pays Y86-64's the subtraction clobbers a register tax; the andq x, x and subq idioms this module leans on are Y86-64 working around a compare instruction it deliberately omits.

ARM's condition flags and full predication. ARM carries the same four flags (N, Z, C, V — sign, zero, carry, overflow) but historically went much further than cmovXX: in 32-bit ARM, almost every instruction could be predicated, carrying a 4-bit condition field so that ADDNE, MOVGT, and the like execute only when the flags match.¹ A whole if-body could be straight-line predicated code with no branch at all — Y86-64's conditional-move idea generalized to the entire instruction set. AArch64 (64-bit ARM) pulled most of this back, keeping predication only for a handful of select and conditional-compare instructions, because full predication wastes an encoding bit on every instruction and modern branch predictors made the branch-avoidance payoff smaller. The arc — add predication for the pipeline, then retreat when prediction improved — is the same cost-driven revisiting seen throughout these lessons.

The XOR trick is universal. The one piece of Y86-64's condition logic that is not a simplification at all is $\text{SF}\oplus \text{OF}$ for signed less than. That exact Boolean is how x86, ARM, RISC-V comparison sequences, and essentially every two's-complement machine define the signed-less-than condition, for the exact overflow reason the lesson traced. It is one of the small pieces of the teaching ISA that is bit-for-bit identical to the production ones.