The SEQ Stages · study.

The last lesson named the six SEQ stages and gave each a one-line job. That is not enough to build anything: a circuit needs the exact value on every wire, for every instruction. This lesson supplies it. For each Y86-64 instruction we fill in a stage table: six rows, one per stage, each holding the precise computation that instruction requires of that stage. These tables are the specification of the processor; lessons 3 through 5 are just the work of realizing them in hardware. Get a table wrong here and the silicon runs the wrong program.

The signals every stage produces

Before the tables, the vocabulary. Each stage produces named signals that later stages consume, and the same names recur in every table.

Fetch produces icode:ifun (the opcode), rA, rB (register IDs, if the instruction has a register byte), valC (the 8-byte constant, if present), and valP, the address of the following instruction: $valP = PC + 1 + r + 8 c$ , where $r$ is 1 if the instruction has a register byte and $c$ is 1 if it has a valC.
Decode selects two source register IDs srcA, srcB and reads $valA \leftarrow R [srcA]$ , $valB \leftarrow R [srcB]$ . It also selects two destination IDs dstE, dstM for write-back.
Execute drives the ALU with inputs aluA, aluB and a function, producing valE; on OPq it sets the condition codes; for branches and conditional moves it computes Cnd.
Memory computes an address, then reads ( $valM \leftarrow M []$ ) or writes ( $M [] \leftarrow$ ).
Write-back writes $R [dstE] \leftarrow valE$ and $R [dstM] \leftarrow valM$ .
PC update picks newPC.

The names follow a discipline that reading stage tables fluently depends on.

The discipline pays off when tables look alike. pushq and call both write $M_{8} [valE] \leftarrow \dots$ in Memory, and the names tell you the address was computed by the ALU (valE), not read from a register. popq and ret both read at valA, and the name tells you the address came straight from a register read, bypassing the ALU.

Reading a stage table: OPq

Take the arithmetic instruction OPq rA, rB (which covers addq, subq, andq, xorq — the ifun selects which). It reads both rA and rB, computes $R [rB] \leftarrow R [rB] OP R [rA]$ , sets the condition codes, and falls through to the next instruction. Every stage gets a concrete value.

The OPq rA,rB stage table. Decode reads both operands; Execute applies the ifun-selected ALU op to valB OP valA and sets the condition codes; Memory is idle; Write-back stores valE into rB; PC falls through to valP.

For OPq the source registers are exactly rA and rB, and the one destination is rB, written from valE. The ALU's second operand aluA is valA and its first aluB is valB, and the result is valB OP valA — order matters, because subq rA, rB must compute $R [rB] - R [rA]$ .

The trivial pair: nop and halt

Two instructions do almost nothing, and their tables say so. nop occupies a byte and a cycle: fetch it, compute valP, and fall through; every other row is empty. halt is one row stranger: it too fetches and computes valP, but it also sets the status Stat to HLT, and a machine whose status is not AOK does not begin another cycle, so the PC-update row is moot. Nothing else in the datapath moves.

nop (left) and halt (right). Both fetch one byte and compute valP; nop falls through, while halt sets Stat to HLT so no further cycle begins. Every other stage is idle for both.

Idle rows are not wasted rows. nop still takes a full cycle, because in SEQ every instruction takes exactly one cycle regardless of how little it does, a fact with consequences for timing, since the clock must be slow enough for the longest instruction, and nop then pays for time it never uses.

Register moves: rrmovq, cmovXX, irmovq

The register-to-register move rrmovq rA, rB and the immediate move irmovq V, rB share a trick: neither has any arithmetic to do, but both route their value through the ALU anyway, adding zero. rrmovq computes $valE = 0 + valA$ ; irmovq computes $valE = 0 + valC$ . The ALU is sitting in the middle of the datapath whether we use it or not, so the cheapest path from value in hand to register write port is straight through it with the other input forced to zero.

rrmovq rA,rB (left) and irmovq V,rB (right). Both pass their value through the ALU by adding 0 — valA for rrmovq, valC for irmovq — and write valE into rB. The cmovXX variants add Cnd in Execute and write only if it holds.

The conditional moves cmovXX rA, rB share rrmovq's icode (they differ only in ifun) and its table, with one addition: Execute also evaluates $Cnd = Cond (CC, ifun)$ , and Write-back happens only when Cnd holds: the destination select dstE becomes RNONE on a failed condition, so the write port idles and rB keeps its old value. The move is squashed, not skipped: the instruction still spends its cycle and still falls through to valP.

Memory instructions: rmmovq and mrmovq

The memory instructions use the Execute stage as an address adder and give the Memory stage real work. rmmovq rA, D(rB) stores R[rA] to memory at $D + R [rB]$ ; mrmovq D(rB), rA loads from the same address into rA. The ALU adds the displacement valC to the base valB in both cases; the difference is only the direction of the memory access and which register, if any, is written.

rmmovq rA,D(rB) (left) and mrmovq D(rB),rA (right). Both add valC to valB in Execute to form the address. rmmovq writes valA to that address and writes no register; mrmovq reads valM from it and writes valM into rA.

rmmovq writes a register in no stage (its Write-back row is empty), while mrmovq writes rA from valM. Compare the two Memory rows: the same address valE appears on both, once as a write target, once as a read source: one address computation serves both directions.

It is worth running one table with real numbers, because the abstract rows hide how little arithmetic each stage does. Take mrmovq 8(%rdx), %rax with %rdx = 0x200 and the eight bytes at address 0x208 holding the value 0x2a. The bytes of the instruction, laid out by the assembler, are 50 02 then the 8-byte displacement 08 00 00 00 00 00 00 00.

mrmovq 8(%rdx),%rax traced with %rdx = 0x200 and M[0x208] = 0x2a. Fetch pulls valC = 8; Decode reads valB = 0x200; Execute adds to valE = 0x208; Memory reads valM = 0x2a from that address; Write-back stores it into %rax.

Five of the six rows carry a concrete value, and every one is forced by an earlier row or by prior state: valC = 0x8 came out of the instruction bytes, valB = 0x200 was already in %rdx, valE = 0x208 is the one addition the ALU performs, and valM = 0x2a is what memory returned at that address. Nothing in the table is a choice; the only decisions — which register feeds srcB, which ALU function runs, whether memory reads — belong to the control logic of the next lesson. The stage table is what the control logic must arrange to be true.

Stack instructions: pushq and popq

The stack instructions are where the ALU does an off-to-the-side adjustment of %rsp. pushq rA decrements %rsp by 8, then stores R[rA] at the new top.popq rA reads the word at the current top, then increments %rsp by 8. The order matters and the tables make it exact.

pushq rA (left) decrements %rsp by 8 in Execute, then stores valA at the new top, and writes the decremented pointer back. popq rA (right) increments %rsp by 8 but reads from the OLD top (valA, the unincremented %rsp), writing both the incremented pointer (dstE) and the loaded word.

Both tables hide edge cases that surface exactly when rA is %rsp itself, and both are resolved by reading the rows in order.

For every other rA, the two write ports of the register file are what let popq update %rsp (from valE) and rA (from valM) in the same cycle, the reason the register file was built with two write ports at all.

Control transfer: jXX, call, ret

The control instructions are the ones that make newPC interesting. Start with the jumps: jXX Dest carries the destination in valC and needs neither the register file nor the ALU. Its whole Execute row is the evaluation of the branch condition $Cnd = Cond (CC, ifun)$ from the condition codes that some earlier OPq left behind.

The jXX Dest stage table. Fetch reads the 8-byte destination valC; Execute evaluates Cnd from the condition codes and ifun; nothing touches the register file or memory. PC update picks valC if Cnd holds, else valP.

The seven conditions (jmp always, then jle, jl, je, jne, jge, jg) are Boolean functions of ZF, SF, OF, selected by ifun, the same Cond unit the cmovXX family uses, derived in the next lesson. An untaken jump is a nop that cost nine bytes: it computes Cnd = 0 and falls through to valP.

call Dest and ret complete the set. call pushes the return address valP and jumps to valC; ret pops the return address into the PC.

call Dest (left) decrements %rsp, stores the return address valP at the new top, and sets newPC to the call target valC. ret (right) reads valM from the current top, increments %rsp, and sets newPC to that loaded address.

call and pushq share their Execute and Memory shape — decrement %rsp, store at the new top — but call stores valP (the return address) rather than a register value, and its newPC is valC, not valP. ret and popq are the mirror image: read from the old top, increment %rsp.

ret deserves a slower look, because one byte of encoding drives more machinery than any other instruction its size. It names no register, yet it uses %rspthree times: Decode reads it twice ( $srcA$ supplies the memory address, $srcB$ the value to increment), and Write-back stores the incremented pointer through dstE. On top of that it reads data memory at the old top (valA, not valE — read the Memory row carefully) and commandeers the PC mux. The single difference between ret and popq is the last row: ret sends valM to the PC, while popq sends it to a register and falls through to valP. That one mux input is the entire difference between return from a function and pop a value.

The vertical view: six stages, every instruction

Stacking the stages vertically, every instruction is the same column of six boxes — only the contents of the boxes change. This shape mirrors how lesson 4 lays out the complete datapath: six horizontal bands, Fetch at the bottom, PC update at the top.

The six SEQ stages as a single vertical column, the common skeleton of every Y86-64 instruction. The contents differ per instruction (the tables above); the order and the signal hand-off between stages never do.

Stage tables as the ancestor of micro-ops

A stage table is a claim that every instruction, however different its surface syntax, decomposes into the same small vocabulary of primitive steps: a register read, one ALU operation, at most one memory access, a register write, a PC choice. That decomposition is also how real high-performance processors run a complicated instruction set.

Modern x86-64 cores do not execute their sprawling CISC instructions directly. Instead, the front end cracks each architectural instruction into a sequence of uniform internal operations, the micro-operations (µops) mentioned in CS:APP's RISC versus CISC aside (Bryant & O'Hallaron, CS:APP §4.1) and developed in its treatment of modern processors (§5.7). A Y86-64 pushq already shows the pattern in miniature: its stage table is subtract 8, then store, which is exactly two µops' worth of work riding on one instruction. On a real x86 machine, an instruction with a memory-operand-and-arithmetic form similarly expands into a load µop, an ALU µop, and sometimes a store µop — each of which looks like one filled-in row of a stage table. The back end then schedules these uniform µops out of order across duplicated functional units. The reason the translation is even possible is the reason stage tables are worth writing: once you have reduced every instruction to a fixed sequence of primitive stage operations, the hardware that carries out any one primitive can be built once and shared by all. The SEQ tables are that reduction done by hand, for a small enough ISA that the whole vocabulary fits on a page.

With every instruction's stage table fixed, the next lesson derives the control signals — srcA, dstE, the ALU function, the memory controls, newPC — that select among these computations from icode alone.