The Fetch-Decode-Execute Cycle

The previous module fixed the Y86-64 instruction set: exactly what state a program can see and exactly how each instruction is encoded in bytes. The module before that built the combinational and storage elements: muxes, decoders, the ALU, the register file, memory. This module spends those parts on one goal: a circuit that, started at an address, runs a Y86-64 program. The whole thing is one loop, repeated billions of times a second, and this first lesson draws that loop and names its pieces before we wire a single gate.

The stored-program machine

The defining idea of the modern computer is older than any chip: the program lives in the same memory as the data, as bytes the machine reads and obeys. A processor holds one piece of private state that points into that memory, the program counter, and its entire behavior is a loop: read the bytes at the PC, treat them as an instruction, carry it out, and update the PC to point at the next instruction. Nothing tells the hardware whether a given byte is code or data; the PC decides, by pointing at it.

That single loop is the instruction cycle, and the machine never leaves it until a halt instruction sets Stat to HLT.

The PC update is what makes the loop a loop. For most instructions the next PC is simply the address just past the bytes we read; for a jump or a call it is somewhere else entirely; for a return it comes off the stack. Getting that one value right on every instruction is what keeps the machine on the rails.

The datapath: the units the loop drives

The loop above is behavior; the datapath is the hardware that carries it out: the functional units, wired together, that hold and move the bits. Five units do almost all of the work, and we have already built every one of them in isolation.

• The program counter (PC) is a single 64-bit register holding the address of the current instruction. It is the only state outside memory and the register file, and it is updated once per instruction.
• Instruction memory is the part of memory the fetch stage reads. Given the PC it returns the instruction bytes: the icode:ifun opcode, an optional register byte, an optional 8-byte constant. (In Y86-64 there is one memory; instruction memory and data memory are two read/write ports onto it.)
• The register file holds the fifteen program registers %rax–%r14. It has two read ports (so both ALU operands can be read at once) and two write ports (so an instruction can update two registers — an ALU result and a memory value — in one cycle).
• The ALU does the arithmetic: it adds, subtracts, ANDs, and XORs under a function-code control input, and on arithmetic instructions it sets the condition codes ZF/SF/OF.
• Data memory is the part of memory loads and stores touch, addressed by an address the ALU usually computes.

Two more pieces glue these together. Condition codes are three flip-flops the ALU writes and the branches read. And multiplexers sit at the input of nearly every unit, choosing, under control-unit signals, which of several possible values that unit should see this cycle. The next operand might be a register or an immediate; the write-back value might be the ALU result or a loaded word; the next PC might be the fall-through address, a jump target, or a return address. Every such choice is a mux.

The register file deserves a closer look, because its shape is dictated by what a single instruction must do in one cycle. popq %rbx, for instance, updates two registers at once — it writes the incremented %rsp and the loaded word into %rbx — and it reads %rsp while doing so. So the register file has two read ports and two write ports, each an independent address-plus-data channel into the same array of fifteen 64-bit registers. Reads are combinational (present an ID, the value appears after a gate delay); writes are clocked (they commit only at the cycle's rising edge). A register ID is four bits, so 0x0–0xE name %rax–%r14 and the spare code 0xF is RNONE: addressing a port with RNONE reads zero and writes nowhere, which is how an instruction that needs only one operand leaves the other port idle.

The control unit: sequencing the datapath

The datapath can compute anything, but it does not know what to compute on a given cycle. That is the control unit's job. It reads the one field that names the operation, icode (with ifun for variants), and from it computes every control signal the datapath needs: which registers to read and write, what function the ALU performs, whether memory reads or writes, and where the next PC comes from. In a hardwired control unit — the kind we build in this module — that computation is pure combinational logic, written in HCL: a set of Boolean and case expressions of icode. There is no little program inside the processor; the control is the circuit.

Breaking the cycle into stages

To turn the loop into a circuit we slice it into a fixed sequence of stages, each a clean band of computation that hands its results to the next. CS:APP's sequential design (SEQ) uses six, and every Y86-64 instruction flows through the same six in the same order. Instructions that do not need a stage simply pass through it.

The stages are worth naming once, because the rest of the module fills in exactly what each one computes for each instruction.

• Fetch reads the instruction bytes at the PC, splits out icode:ifun, the register byte, and the constant valC, and computes valP, the address of the next instruction in sequence.
• Decode reads up to two register operands from the register file into valA and valB.
• Execute uses the ALU — to compute an arithmetic result, a memory address, or a stack adjustment — producing valE, and on arithmetic instructions sets the condition codes. It also evaluates the branch condition Cnd.
• Memory reads a word from data memory into valM, or writes a value to data memory.
• Write-back writes up to two results back to the register file: valE to one register, valM to another.
• PC update computes the address of the next instruction: normally valP, but valC for a call or taken jump, and valM for a return.

Not every instruction uses every stage, but every instruction passes through all six in lockstep — a stage it does not need simply produces a value nothing uses. An OPq like addq reads registers (Decode), computes in the ALU (Execute), and writes a register (Write-back), but its Memory stage does nothing: addq touches no memory, so Memory is a cycle spent idle. A nop uses only Fetch and PC update; a jmp adds Execute (to evaluate the always-true condition) but skips Decode, Memory, and Write-back; a ret is the busiest short instruction, exercising Decode, Execute, Memory, Write-back, and a non-default PC update. Keeping the stage sequence fixed — rather than letting instructions take custom paths — is what lets one control unit and one datapath serve all twelve opcodes, at the cost of stages an instruction leaves idle; pipelining later recovers that cost.

How fetch finds the instruction boundaries

Everything downstream depends on fetch getting one job exactly right: carving a stream of undifferentiated bytes into instructions. Y86-64 instructions are variable-length (1, 2, 9, or 10 bytes), so there is no fixed stride the PC can advance by. The machine cannot look ahead, and it does not need to: the first byte alone determines the length of the whole instruction. Its high nibble is icode, its low nibble ifun, and icode fixes the format:

• Does the instruction have a register byte? Yes for rrmovq/cmovXX, OPq, pushq, popq, irmovq, rmmovq, and mrmovq; no for halt, nop, jXX, call, and ret. Call this bit need_regids, or $r$.
• Does it have an 8-byte constant valC? Yes for irmovq, rmmovq, mrmovq (the immediate or displacement) and for jXX and call (the destination address). Call this bit need_valC, or $c$.

Both bits are one-line HCL predicates on icode, and together they give the instruction length and therefore the fall-through address:

bool need_regids = icode in { IRRMOVQ, IOPQ, IPUSHQ, IPOPQ,
                              IIRMOVQ, IRMMOVQ, IMRMOVQ };

bool need_valC   = icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ, IJXX, ICALL };

bool instr_valid = icode in { INOP, IHALT, IRRMOVQ, IIRMOVQ, IRMMOVQ,
                              IMRMOVQ, IOPQ, IJXX, ICALL, IRET,
                              IPUSHQ, IPOPQ };

The four possible lengths come from the four combinations of $r$ and $c$: 1 byte ($r=0,c=0$, e.g. ret), 2 bytes ($r=1,c=0$, e.g. addq), 9 bytes ($r=0,c=1$, e.g. jne), and 10 bytes ($r=1,c=1$, e.g. irmovq).

Trace it on a real byte stream. Suppose memory from address 0x000 holds 30 f2 09 00 00 00 00 00 00 00 60 20 90 and the PC starts at 0x000.

• Fetch reads byte 30: icode = 3 (irmovq), so $r=1$, $c=1$, length 10. The register byte f2 gives rB = %rdx, the next 8 bytes give valC = 9, and valP = 0x000 + 10 = 0x00a.
• At 0x00a, byte 60: icode = 6 (OPq, and ifun = 0 says addq), so $r=1$, $c=0$, length 2. The register byte 20 names %rdx and %rax; valP = 0x00c.
• At 0x00c, byte 90: icode = 9 (ret), $r=0$, $c=0$, length 1; valP = 0x00d, though ret will discard it and take the return address instead.

Three instructions, three different lengths, and at no point did the hardware guess: each first byte fixed how many bytes belonged to its instruction, and valP landed exactly on the next boundary.

Fetch is also the machine's first line of defense against a broken program. Two things can go wrong before an instruction even runs, and fetch catches both by setting the two-bit status code Stat that every cycle carries alongside the instruction. If the icode nibble is not one of the twelve valid opcodes, instr_valid goes false and Stat becomes INS, an illegal-instruction halt, rather than executing garbage. If the PC points outside valid memory, imem_error raises Stat = ADR. A clean instruction leaves Stat = AOK, halt sets Stat = HLT, and the rule is simply that the machine begins another cycle only while Stat is AOK.

Suppose the byte at the PC were f0. Its high nibble f is not among the twelve opcodes (the largest valid icode is 0xB, popq), so instr_valid = 0, Stat = INS, and the machine halts here instead of decoding a phantom instruction with a phantom length. This is why a valid-opcode check belongs in fetch and nowhere else: fetch is the one stage that has seen the raw byte before any downstream logic has committed to a length or a register read.

In hardware, fetch is a small datapath of its own: instruction memory produces ten bytes starting at the PC; a split unit divides byte 0 into icode and ifun; an align unit routes bytes 1–9 into rA, rB, and valC (bytes 1–8 form valC when there is no register byte, bytes 2–9 when there is); and a dedicated PC-increment adder computes $\text{PC}+1+r+8c$. There is no reason to occupy the main ALU with the PC increment (it is busy computing the instruction's own result), so fetch gets its own small adder.

Where the six stages go next

SEQ commits to one instruction per clock cycle, and the whole loop must settle inside that cycle. That is a deliberate teaching simplification, and the very next design in CS:APP starts undoing it. The first move is a bookkeeping one called SEQ+ (Bryant & O'Hallaron, CS:APP §4.5.1): the PC-update stage is shifted from the end of the cycle to the beginning, so the machine computes the address of the instruction it is about to run from state saved on the previous cycle. SEQ+ has no PC register at all — the program counter is reconstructed each cycle from a handful of saved signals (pIcode, pValC, pValM, …). CS:APP notes this is an instance of circuit retiming (Leiserson & Saxe, 1991), a transformation that relocates state across combinational logic without changing what the circuit computes, used here to balance stage delays. It leads directly to pipelining: once every stage begins and ends at a clean register boundary, you can let several instructions occupy different stages at once.

Real processors carry the same six-stage skeleton, but the fetch-and-decode front end looks nothing like Y86-64's tidy nibble-splitter. x86-64 instructions run from 1 to 15 bytes with prefixes, escape bytes, and mode-dependent operands, so decode is a serious pipeline of its own. Modern x86 cores translate each architectural instruction into one or more fixed-format internal operations — micro-operations, or µops — and the back end schedules those, out of order, across many functional units (Bryant & O'Hallaron, §4.1 aside on RISC vs. CISC; and CS:APP §5.7 on modern processors). The principle the aside on SEQ+ states plainly is what licenses all of this: a processor may represent its state however it likes, so long as it produces the correct programmer-visible values for any machine-language program. SEQ is the baseline against which those later liberties make sense.

The next lesson makes the six stages precise, writing down exactly what each one computes for each Y86-64 instruction.