---
title: The SEQ Stages
module: Processor Design
moduleNumber: 4
lessonNumber: 2
order: 402
summary: >
  The six SEQ stages, made exact. For every Y86-64 instruction — halt, nop, the
  moves, OPq, the jumps, call and ret, pushq and popq — we write down what Fetch,
  Decode, Execute, Memory, Write-back, and PC update each compute, as
  per-instruction stage tables with every row justified. Once the tables are filled
  in, the processor is fully specified; the remaining lessons turn them into wires.
topics: [Processor Design]
sources:
  - book: Bryant & O'Hallaron
    ref: "CS:APP — §4.3 Sequential Y86-64 Implementations"
  - book: Bistriceanu
    ref: "Computer Architecture Notes — §5 CPU Implementation (Executing an instruction; Hardwired control)"
---

The [last lesson](/computer-architecture/processor-design/the-fetch-decode-execute-cycle)
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:
  $\texttt{valP} = \texttt{PC} + 1 + r + 8c$, 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
  $\texttt{valA} \leftarrow R[\texttt{srcA}]$, $\texttt{valB} \leftarrow R[\texttt{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 ($\texttt{valM} \leftarrow M[\,]$) or
  writes ($M[\,] \leftarrow$).
- **Write-back** writes $R[\texttt{dstE}] \leftarrow \texttt{valE}$ and
  $R[\texttt{dstM}] \leftarrow \texttt{valM}$.
- **PC update** picks `newPC`.

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

> **Convention (Signal naming).** The last letter of each `val` name says where the
> value was produced: `valC` is the **C**onstant read from the instruction bytes,
> `valP` the incremented **P**C, `valE` the **E**xecute-stage ALU result, `valM` the
> word the **M**emory stage read. `valA` and `valB` are whatever the register file's
> A and B read ports returned. A stage table never invents a new name; if a value
> appears in some row, one earlier row (or the register file or memory) produced it
> under exactly that name.

The discipline pays off when tables look alike. `pushq` and `call` both write
$M_8[\texttt{valE}] \leftarrow \cdots$ 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[\texttt{rB}] \leftarrow R[\texttt{rB}] \mathbin{\text{OP}} R[\texttt{rA}]$, sets
the condition codes, and falls through to the next instruction. Every stage gets a
concrete value.

$$
% caption: The OPq rA,rB stage table. Decode reads both operands; Execute applies the
% caption: ifun-selected ALU op to valB OP valA and sets the condition codes; Memory
% caption: is idle; Write-back stores valE into rB; PC falls through to valP.
\begin{tikzpicture}[font=\footnotesize,
  lbl/.style={anchor=east, text=acc, font=\scriptsize},
  row/.style={anchor=west}]
  \definecolor{acc}{HTML}{2348F2}
  \draw[acc!40] (-2.6,0.45) -- (10.2,0.45);
  \foreach \y/\stage/\comp in {
    0/{Fetch}/{$\mathtt{icode{:}ifun} = M_1[\mathtt{PC}]$;\ \ $\mathtt{rA{:}rB} = M_1[\mathtt{PC}{+}1]$;\ \ $\mathtt{valP}=\mathtt{PC}{+}2$},
    -0.85/{Decode}/{$\mathtt{valA} = R[\mathtt{rA}]$;\ \ $\mathtt{valB} = R[\mathtt{rB}]$},
    -1.7/{Execute}/{$\mathtt{valE}=\mathtt{valB}\ \mathrm{OP}\ \mathtt{valA}$;\ \ set CC (ZF/SF/OF)},
    -2.55/{Memory}/{-},
    -3.4/{Write-back}/{$R[\mathtt{rB}] = \mathtt{valE}$},
    -4.25/{PC update}/{$\mathtt{PC} = \mathtt{valP}$}} {
    \node[lbl] at (-0.1,\y) {\stage};
    \node[row] at (0.2,\y) {\comp};
    \draw[acc!40] (-2.6,\y-0.42) -- (10.2,\y-0.42);
  }
\end{tikzpicture}
$$

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[\texttt{rB}] - R[\texttt{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.

$$
% caption: nop (left) and halt (right). Both fetch one byte and compute valP; nop
% caption: falls through, while halt sets Stat to HLT so no further cycle begins.
% caption: Every other stage is idle for both.
\begin{tikzpicture}[font=\footnotesize,
  lbl/.style={anchor=east, text=acc, font=\scriptsize}, row/.style={anchor=west}]
  \definecolor{acc}{HTML}{2348F2}
  \node[anchor=west, text=acc] at (-2.7,0.95) {\texttt{nop}};
  \draw[acc!40] (-2.7,0.45) -- (4.6,0.45);
  \foreach \y/\stage/\comp in {
    0/{Fetch}/{$\mathtt{icode{:}ifun} = M_1[\mathtt{PC}]$;\ $\mathtt{valP}=\mathtt{PC}{+}1$},
    -0.85/{Decode}/{-},
    -1.7/{Execute}/{-},
    -2.55/{Memory}/{-},
    -3.4/{Write-back}/{-},
    -4.25/{PC update}/{$\mathtt{PC} = \mathtt{valP}$}} {
    \node[lbl] at (-0.2,\y) {\stage};
    \node[row] at (0.1,\y) {\comp};
    \draw[acc!40] (-2.7,\y-0.42) -- (4.6,\y-0.42);
  }
  \node[anchor=west, text=acc] at (6.1,0.95) {\texttt{halt}};
  \draw[acc!40] (6.1,0.45) -- (13.4,0.45);
  \foreach \y/\stage/\comp in {
    0/{Fetch}/{$\mathtt{icode{:}ifun} = M_1[\mathtt{PC}]$;\ $\mathtt{valP}=\mathtt{PC}{+}1$},
    -0.85/{Decode}/{-},
    -1.7/{Execute}/{-},
    -2.55/{Memory}/{-},
    -3.4/{Write-back}/{-},
    -4.25/{PC update}/{Stat = HLT; machine stops}} {
    \node[lbl] at (6.6,\y) {\stage};
    \node[row] at (6.9,\y) {\comp};
    \draw[acc!40] (6.1,\y-0.42) -- (13.4,\y-0.42);
  }
\end{tikzpicture}
$$

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](/computer-architecture/processor-design/assembling-seq),
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
$\texttt{valE} = 0 + \texttt{valA}$; `irmovq` computes
$\texttt{valE} = 0 + \texttt{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.

$$
% caption: rrmovq rA,rB (left) and irmovq V,rB (right). Both pass their value through
% caption: the ALU by adding 0 — valA for rrmovq, valC for irmovq — and write valE
% caption: into rB. The cmovXX variants add Cnd in Execute and write only if it holds.
\begin{tikzpicture}[font=\footnotesize,
  lbl/.style={anchor=east, text=acc, font=\scriptsize}, row/.style={anchor=west}]
  \definecolor{acc}{HTML}{2348F2}
  \node[anchor=west, text=acc] at (-2.7,0.95) {\texttt{rrmovq rA,rB}};
  \draw[acc!40] (-2.7,0.45) -- (4.9,0.45);
  \foreach \y/\stage/\comp in {
    0/{Fetch}/{$\mathtt{rA{:}rB} = M_1[\mathtt{PC}{+}1]$;\ $\mathtt{valP}=\mathtt{PC}{+}2$},
    -0.85/{Decode}/{$\mathtt{valA} = R[\mathtt{rA}]$},
    -1.7/{Execute}/{$\mathtt{valE}=0+\mathtt{valA}$},
    -2.55/{Memory}/{-},
    -3.4/{Write-back}/{$R[\mathtt{rB}] = \mathtt{valE}$},
    -4.25/{PC update}/{$\mathtt{PC} = \mathtt{valP}$}} {
    \node[lbl] at (-0.2,\y) {\stage};
    \node[row] at (0.1,\y) {\comp};
    \draw[acc!40] (-2.7,\y-0.42) -- (4.9,\y-0.42);
  }
  \node[anchor=west, text=acc] at (6.4,0.95) {\texttt{irmovq V,rB}};
  \draw[acc!40] (6.4,0.45) -- (14.4,0.45);
  \foreach \y/\stage/\comp in {
    0/{Fetch}/{$\mathtt{rA{:}rB} = M_1[\mathtt{PC}{+}1]$;\ $\mathtt{valC} = M_8[\mathtt{PC}{+}2]$;\ $\mathtt{valP}=\mathtt{PC}{+}10$},
    -0.85/{Decode}/{-},
    -1.7/{Execute}/{$\mathtt{valE}=0+\mathtt{valC}$},
    -2.55/{Memory}/{-},
    -3.4/{Write-back}/{$R[\mathtt{rB}] = \mathtt{valE}$},
    -4.25/{PC update}/{$\mathtt{PC} = \mathtt{valP}$}} {
    \node[lbl] at (6.9,\y) {\stage};
    \node[row] at (7.2,\y) {\comp};
    \draw[acc!40] (6.4,\y-0.42) -- (14.4,\y-0.42);
  }
\end{tikzpicture}
$$

The conditional moves `cmovXX rA, rB` share `rrmovq`'s `icode` (they differ only in
`ifun`) and its table, with one addition: Execute also evaluates
$\texttt{Cnd} = \mathrm{Cond}(\mathtt{CC}, \mathtt{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[\texttt{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.

$$
% caption: rmmovq rA,D(rB) (left) and mrmovq D(rB),rA (right). Both add valC to valB
% caption: in Execute to form the address. rmmovq writes valA to that address and
% caption: writes no register; mrmovq reads valM from it and writes valM into rA.
\begin{tikzpicture}[font=\footnotesize,
  lbl/.style={anchor=east, text=acc, font=\scriptsize}, row/.style={anchor=west}]
  \definecolor{acc}{HTML}{2348F2}
  % left table: rmmovq
  \node[anchor=west, text=acc] at (-2.6,0.95) {\texttt{rmmovq rA,D(rB)}};
  \draw[acc!40] (-2.6,0.45) -- (5.3,0.45);
  \foreach \y/\stage/\comp in {
    0/{Fetch}/{$\mathtt{valC} = M_8[\mathtt{PC}{+}2]$;\ $\mathtt{valP}=\mathtt{PC}{+}10$},
    -0.85/{Decode}/{$\mathtt{valA} = R[\mathtt{rA}]$;\ $\mathtt{valB} = R[\mathtt{rB}]$},
    -1.7/{Execute}/{$\mathtt{valE}=\mathtt{valB}+\mathtt{valC}$},
    -2.55/{Memory}/{$M_8[\mathtt{valE}] = \mathtt{valA}$},
    -3.4/{Write-back}/{-},
    -4.25/{PC update}/{$\mathtt{PC} = \mathtt{valP}$}} {
    \node[lbl] at (-0.1,\y) {\stage};
    \node[row] at (0.2,\y) {\comp};
    \draw[acc!40] (-2.6,\y-0.42) -- (5.3,\y-0.42);
  }
  % right table: mrmovq
  \node[anchor=west, text=acc] at (6.8,0.95) {\texttt{mrmovq D(rB),rA}};
  \draw[acc!40] (6.8,0.45) -- (14.7,0.45);
  \foreach \y/\stage/\comp in {
    0/{Fetch}/{$\mathtt{valC} = M_8[\mathtt{PC}{+}2]$;\ $\mathtt{valP}=\mathtt{PC}{+}10$},
    -0.85/{Decode}/{$\mathtt{valB} = R[\mathtt{rB}]$},
    -1.7/{Execute}/{$\mathtt{valE}=\mathtt{valB}+\mathtt{valC}$},
    -2.55/{Memory}/{$\mathtt{valM} = M_8[\mathtt{valE}]$},
    -3.4/{Write-back}/{$R[\mathtt{rA}] = \mathtt{valM}$},
    -4.25/{PC update}/{$\mathtt{PC} = \mathtt{valP}$}} {
    \node[lbl] at (7.3,\y) {\stage};
    \node[row] at (7.6,\y) {\comp};
    \draw[acc!40] (6.8,\y-0.42) -- (14.7,\y-0.42);
  }
\end{tikzpicture}
$$

`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`.

$$
% caption: mrmovq 8(%rdx),%rax traced with %rdx = 0x200 and M[0x208] = 0x2a. Fetch
% caption: pulls valC = 8; Decode reads valB = 0x200; Execute adds to valE = 0x208;
% caption: Memory reads valM = 0x2a from that address; Write-back stores it into %rax.
\begin{tikzpicture}[font=\footnotesize,
  lbl/.style={anchor=east, text=acc, font=\scriptsize}, row/.style={anchor=west}]
  \definecolor{acc}{HTML}{2348F2}
  \draw[acc!40] (-2.6,0.45) -- (11.4,0.45);
  \foreach \y/\stage/\comp in {
    0/{Fetch}/{icode:ifun $=$ 5:0; rA:rB $=$ 0:2; valC $=$ 0x8; valP $=$ PC $+$ 10},
    -0.85/{Decode}/{srcB $=$ rB $=$ \%rdx: valB $=$ 0x200},
    -1.7/{Execute}/{valE $=$ valB $+$ valC $=$ 0x200 $+$ 0x8 $=$ 0x208},
    -2.55/{Memory}/{valM $= M_8[\mathtt{0x208}] =$ 0x2a},
    -3.4/{Write-back}/{$R[\mathtt{\%rax}] =$ valM $=$ 0x2a},
    -4.25/{PC update}/{PC $=$ valP}} {
    \node[lbl] at (-0.1,\y) {\stage};
    \node[row] at (0.2,\y) {\comp};
    \draw[acc!40] (-2.6,\y-0.42) -- (11.4,\y-0.42);
  }
\end{tikzpicture}
$$

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.

$$
% caption: pushq rA (left) decrements %rsp by 8 in Execute, then stores valA at the
% caption: new top, and writes the decremented pointer back. popq rA (right)
% caption: increments %rsp by 8 but reads from the OLD top (valA, the unincremented
% caption: %rsp), writing both the incremented pointer (dstE) and the loaded word.
\begin{tikzpicture}[font=\footnotesize,
  lbl/.style={anchor=east, text=acc, font=\scriptsize}, row/.style={anchor=west}]
  \definecolor{acc}{HTML}{2348F2}
  \node[anchor=west, text=acc] at (-2.7,0.95) {\texttt{pushq rA}};
  \draw[acc!40] (-2.7,0.45) -- (5.4,0.45);
  \foreach \y/\stage/\comp in {
    0/{Fetch}/{$\mathtt{rA{:}rB} = M_1[\mathtt{PC}{+}1]$;\ $\mathtt{valP}=\mathtt{PC}{+}2$},
    -0.85/{Decode}/{$\mathtt{valA} = R[\mathtt{rA}]$;\ $\mathtt{valB} = R[\mathtt{\%rsp}]$},
    -1.7/{Execute}/{$\mathtt{valE}=\mathtt{valB}$ - 8},
    -2.55/{Memory}/{$M_8[\mathtt{valE}] = \mathtt{valA}$},
    -3.4/{Write-back}/{$R[\mathtt{\%rsp}] = \mathtt{valE}$},
    -4.25/{PC update}/{$\mathtt{PC} = \mathtt{valP}$}} {
    \node[lbl] at (-0.2,\y) {\stage};
    \node[row] at (0.1,\y) {\comp};
    \draw[acc!40] (-2.7,\y-0.42) -- (5.4,\y-0.42);
  }
  \node[anchor=west, text=acc] at (6.9,0.95) {\texttt{popq rA}};
  \draw[acc!40] (6.9,0.45) -- (15.0,0.45);
  \foreach \y/\stage/\comp in {
    0/{Fetch}/{$\mathtt{rA{:}rB} = M_1[\mathtt{PC}{+}1]$;\ $\mathtt{valP}=\mathtt{PC}{+}2$},
    -0.85/{Decode}/{$\mathtt{valA} = R[\mathtt{\%rsp}]$;\ $\mathtt{valB} = R[\mathtt{\%rsp}]$},
    -1.7/{Execute}/{$\mathtt{valE}=\mathtt{valB}+8$},
    -2.55/{Memory}/{$\mathtt{valM} = M_8[\mathtt{valA}]$},
    -3.4/{Write-back}/{$R[\mathtt{\%rsp}] = \mathtt{valE}$;\ $R[\mathtt{rA}] = \mathtt{valM}$},
    -4.25/{PC update}/{$\mathtt{PC} = \mathtt{valP}$}} {
    \node[lbl] at (7.0,\y) {\stage};
    \node[row] at (7.3,\y) {\comp};
    \draw[acc!40] (6.9,\y-0.42) -- (15.0,\y-0.42);
  }
\end{tikzpicture}
$$

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

> **Invariant (pushq %rsp pushes the old value).** `pushq %rsp` stores the value
> `%rsp` held _before_ the instruction, not the decremented one. The table forces
> this: Decode reads $\texttt{valA} = R[\texttt{\%rsp}]$ before Execute computes the
> decrement, and Memory stores `valA`. A design that pushed the decremented pointer
> would be self-consistent too — the encoding does not decide — so this is a
> specification choice, made to match x86-64's behavior.

> **Invariant (popq %rsp loads, not increments).** `popq %rsp` leaves `%rsp` holding
> the value read from memory. Its Write-back row writes `%rsp` twice — `valE` through
> `dstE` and `valM` through `dstM` — and the definition says the `M` write wins. So
> `popq %rsp` means "load the top-of-stack word into `%rsp`", and the increment is
> discarded.

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
$\texttt{Cnd} = \mathrm{Cond}(\mathtt{CC}, \mathtt{ifun})$ from the condition codes
that some earlier `OPq` left behind.

$$
% caption: The jXX Dest stage table. Fetch reads the 8-byte destination valC; Execute
% caption: evaluates Cnd from the condition codes and ifun; nothing touches the
% caption: register file or memory. PC update picks valC if Cnd holds, else valP.
\begin{tikzpicture}[font=\footnotesize,
  lbl/.style={anchor=east, text=acc, font=\scriptsize}, row/.style={anchor=west}]
  \definecolor{acc}{HTML}{2348F2}
  \draw[acc!40] (-2.6,0.45) -- (9.4,0.45);
  \foreach \y/\stage/\comp in {
    0/{Fetch}/{$\mathtt{icode{:}ifun} = M_1[\mathtt{PC}]$;\ $\mathtt{valC} = M_8[\mathtt{PC}{+}1]$;\ $\mathtt{valP}=\mathtt{PC}{+}9$},
    -0.85/{Decode}/{-},
    -1.7/{Execute}/{$\mathtt{Cnd} = \mathrm{Cond}(\mathtt{CC},\mathtt{ifun})$},
    -2.55/{Memory}/{-},
    -3.4/{Write-back}/{-},
    -4.25/{PC update}/{$\mathtt{PC} = \mathtt{Cnd}$ ? $\mathtt{valC}$ : $\mathtt{valP}$}} {
    \node[lbl] at (-0.1,\y) {\stage};
    \node[row] at (0.2,\y) {\comp};
    \draw[acc!40] (-2.6,\y-0.42) -- (9.4,\y-0.42);
  }
\end{tikzpicture}
$$

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](/computer-architecture/processor-design/control-logic-and-sequencing).
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.

$$
% caption: call Dest (left) decrements %rsp, stores the return address valP at the new
% caption: top, and sets newPC to the call target valC. ret (right) reads valM from
% caption: the current top, increments %rsp, and sets newPC to that loaded address.
\begin{tikzpicture}[font=\footnotesize,
  lbl/.style={anchor=east, text=acc, font=\scriptsize}, row/.style={anchor=west}]
  \definecolor{acc}{HTML}{2348F2}
  \node[anchor=west, text=acc] at (-2.7,0.95) {\texttt{call Dest}};
  \draw[acc!40] (-2.7,0.45) -- (5.5,0.45);
  \foreach \y/\stage/\comp in {
    0/{Fetch}/{$\mathtt{valC} = M_8[\mathtt{PC}{+}1]$;\ $\mathtt{valP}=\mathtt{PC}{+}9$},
    -0.85/{Decode}/{$\mathtt{valB} = R[\mathtt{\%rsp}]$},
    -1.7/{Execute}/{$\mathtt{valE}=\mathtt{valB}$ - 8},
    -2.55/{Memory}/{$M_8[\mathtt{valE}] = \mathtt{valP}$},
    -3.4/{Write-back}/{$R[\mathtt{\%rsp}] = \mathtt{valE}$},
    -4.25/{PC update}/{$\mathtt{PC} = \mathtt{valC}$}} {
    \node[lbl] at (-0.2,\y) {\stage};
    \node[row] at (0.1,\y) {\comp};
    \draw[acc!40] (-2.7,\y-0.42) -- (5.5,\y-0.42);
  }
  \node[anchor=west, text=acc] at (7.0,0.95) {\texttt{ret}};
  \draw[acc!40] (7.0,0.45) -- (15.2,0.45);
  \foreach \y/\stage/\comp in {
    0/{Fetch}/{$\mathtt{valP}=\mathtt{PC}{+}1$},
    -0.85/{Decode}/{$\mathtt{valA} = R[\mathtt{\%rsp}]$;\ $\mathtt{valB} = R[\mathtt{\%rsp}]$},
    -1.7/{Execute}/{$\mathtt{valE}=\mathtt{valB}+8$},
    -2.55/{Memory}/{$\mathtt{valM} = M_8[\mathtt{valA}]$},
    -3.4/{Write-back}/{$R[\mathtt{\%rsp}] = \mathtt{valE}$},
    -4.25/{PC update}/{$\mathtt{PC} = \mathtt{valM}$}} {
    \node[lbl] at (7.1,\y) {\stage};
    \node[row] at (7.4,\y) {\comp};
    \draw[acc!40] (7.0,\y-0.42) -- (15.2,\y-0.42);
  }
\end{tikzpicture}
$$

`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 `%rsp`
**three times**: Decode reads it twice ($\texttt{srcA}$ supplies the memory address,
$\texttt{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.

$$
% caption: The six SEQ stages as a single vertical column, the common skeleton of
% caption: every Y86-64 instruction. The contents differ per instruction (the tables
% caption: above); the order and the signal hand-off between stages never do.
\begin{tikzpicture}[font=\footnotesize,>=stealth,
  s/.style={draw, fill=acc!8, minimum width=34mm, minimum height=10mm,
            align=center, inner sep=2pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[s] (f) at (0,0)     {Fetch};
  \node[s] (d) at (0,-1.5)  {Decode};
  \node[s] (e) at (0,-3.0)  {Execute};
  \node[s] (m) at (0,-4.5)  {Memory};
  \node[s] (w) at (0,-6.0)  {Write-back};
  \node[s] (p) at (0,-7.5)  {PC update};
  \foreach \a/\b in {f/d, d/e, e/m, m/w, w/p} \draw[->] (\a.south) -- (\b.north);
  \node[anchor=west, font=\scriptsize, text=acc] at (1.9,-0.75) {icode, ifun, rA, rB, valC, valP};
  \node[anchor=west, font=\scriptsize, text=acc] at (1.9,-2.25) {valA, valB};
  \node[anchor=west, font=\scriptsize, text=acc] at (1.9,-3.75) {valE, Cnd};
  \node[anchor=west, font=\scriptsize, text=acc] at (1.9,-5.25) {valM};
  \node[anchor=west, font=\scriptsize, text=acc] at (1.9,-6.75) {(register state)};
\end{tikzpicture}
$$

## 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.

> **Takeaway.** Every Y86-64 instruction flows through the same six stages, and a
> stage table records what each stage computes for it. The recurring traps are
> small and exact: `OPq` computes `valB OP valA` and writes `rB`; the moves pass
> their value through the ALU by adding 0; `pushq` decrements `%rsp` then stores the
> _old_ value while `popq` reads the old top then increments; `popq %rsp` keeps the
> loaded word; `jXX` touches nothing but `valC` and `Cnd`; `call` stores `valP` and
> jumps to `valC` while `ret` uses `%rsp` three times and loads `valM` into the PC.
> These tables are the processor's specification — the rest of the module turns
> them into wires.

With every instruction's stage table fixed, the
[next lesson](/computer-architecture/processor-design/control-logic-and-sequencing)
derives the control signals — `srcA`, `dstE`, the ALU function, the memory
controls, `newPC` — that select among these computations from `icode` alone.