--- title: Control Logic and Sequencing module: Processor Design moduleNumber: 4 lessonNumber: 3 order: 403 summary: > The stage tables say what each instruction needs; the control logic computes it from icode. We write the HCL for the register-port selections (srcA, srcB, dstE, dstM), the ALU function and input selection, the memory read/write and address, the branch condition, and the next-PC mux — each a case expression on icode that compiles to a mux — and see how one blob of combinational logic serves every instruction at once. We close by contrasting hardwired control with the microprogrammed alternative. 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 [stage tables](/computer-architecture/processor-design/the-seq-stages) said, for each instruction, which register feeds `srcA`, what the ALU computes, whether memory reads or writes, and where the next PC comes from. All of those are **functions of `icode`** (with `ifun` for variants), and the job of the control unit is to compute them. This lesson writes that logic in HCL, one control signal at a time. Each signal is a `case` expression scanning `icode`: the hardware is the [mux tree](/computer-architecture/digital-logic/multiplexers-decoders-and-the-alu) the `case` compiles to. By the end the control unit is fully specified — a pile of combinational equations with no clock and no state of its own. ## The instruction fields Fetch hands over Fetch splits the instruction bytes into named fields, and every later signal is built from them. The first byte gives `icode` (high nibble) and `ifun` (low nibble). If the instruction has a register byte, it gives `rA` and `rB` (an absent register is the code `0xF`, `RNONE`). If it has a constant, that is `valC`. Fetch also computes `valP`, and three status facts: `instr_valid` (was the `icode` a real opcode?), `imem_error` (did the fetch address fault?), and whether this was `halt`. These feed `Stat`. The [previous lesson on fetch](/computer-architecture/processor-design/the-fetch-decode-execute-cycle) worked out how the byte stream is carved up; here we care only about the field names, because they are the inputs to everything below. $$ % caption: The instruction fields every control signal is built from. The first byte % caption: splits into icode and ifun; an optional register byte gives rA and rB; an % caption: optional 8-byte constant gives valC. Fetch also computes the fall-through % caption: address valP from icode alone. \begin{tikzpicture}[font=\footnotesize, by/.style={draw, fill=acc!8, minimum width=12mm, minimum height=8mm, inner sep=0pt}, vb/.style={draw, fill=acc!8, minimum width=30mm, minimum height=8mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \node[by] (op) at (0,0) {}; \draw (0,-0.4) -- (0,0.4); \node at (-0.3,0) {\scriptsize ic}; \node at (0.3,0) {\scriptsize if}; \node[by] (rb) at (1.5,0) {}; \draw (1.5,-0.4) -- (1.5,0.4); \node at (1.2,0) {\scriptsize rA}; \node at (1.8,0) {\scriptsize rB}; \node[vb] (vc) at (4.2,0) {valC (8 bytes)}; \node[anchor=south, text=acc, font=\scriptsize] at (0,0.65) {icode:ifun}; \node[anchor=south, text=acc, font=\scriptsize] at (1.5,0.65) {rA:rB}; \node[anchor=south, text=acc, font=\scriptsize] at (4.2,0.65) {constant / displacement}; \node[anchor=west] at (6.4,0) {$\mathtt{valP}=\mathtt{PC}+1+r+8c$}; \end{tikzpicture} $$ ## Register-port selection: srcA, srcB, dstE, dstM The register file has four ports, and four signals name which physical register each touches. The selections come straight off the stage tables: | Signal | `= rA/rB` for | `= %rsp` for | Note | | --- | --- | --- | --- | | `srcA`→`valA` | `OPq`, `rrmovq`/`cmovXX`, `rmmovq`, `pushq` (`rA`) | `popq`, `ret` | reads stack top | | `srcB`→`valB` | `OPq`, `rmmovq`, `mrmovq` (`rB`) | `pushq`, `popq`, `call`, `ret` | touches `%rsp` | | `dstE`←`valE` | `irmovq`, `OPq` (`rB`); `cmovXX` `rB` iff `Cnd` | `pushq`, `popq`, `call`, `ret` | else `RNONE` | | `dstM`←`valM` | `mrmovq`, `popq` (`rA`) | — | the two memory loads | A conditional move that fails sets `dstE = RNONE` and writes nothing. ```c [seq-decode.hcl] /* srcA: which register supplies valA */ word srcA = [ icode in { IOPQ, IRRMOVQ, IRMMOVQ, IPUSHQ } : rA; icode in { IPOPQ, IRET } : RRSP; 1 : RNONE; /* read nothing */ ]; /* srcB: which register supplies valB */ word srcB = [ icode in { IOPQ, IRMMOVQ, IMRMOVQ } : rB; icode in { IPUSHQ, IPOPQ, ICALL, IRET } : RRSP; 1 : RNONE; ]; /* dstE: register written from valE (cmov writes only if Cnd) */ word dstE = [ icode in { IRRMOVQ } && Cnd : rB; /* conditional move */ icode in { IIRMOVQ, IOPQ } : rB; icode in { IPUSHQ, IPOPQ, ICALL, IRET } : RRSP; 1 : RNONE; ]; /* dstM: register written from valM (the two memory loads) */ word dstM = [ icode in { IMRMOVQ, IPOPQ } : rA; 1 : RNONE; ]; ``` Reading `RNONE` ($=0\text{xF}$) from a port reads zero and writing to it is a no-op, so an instruction that does not need a port simply selects `RNONE` and the port idles. This is why the same four-port register file serves every instruction unchanged. ## What a case expression is in hardware An HCL `case` looks like software, but nothing executes it. Each bracketed expression compiles to a **multiplexer**: the guards become the select logic, the right-hand sides become the data inputs, and the first true guard wins because the select logic is built with that priority. Take `srcA`. Its three cases become a three-input mux whose select is computed by two small comparator circuits testing `icode` against constant nibbles. $$ % caption: The srcA case expression compiled to hardware. Each guard becomes a % caption: comparator network on icode; the guards drive the select of a mux whose % caption: data inputs are the right-hand sides rA, 4 (%rsp), and F (RNONE). Every % caption: HCL case in this lesson is this same picture with different constants. \begin{tikzpicture}[font=\footnotesize,>=stealth, cs/.style={anchor=west, font=\ttfamily\footnotesize}, mx/.style={draw, fill=acc!8, minimum width=14mm, minimum height=26mm, align=center}, cmp/.style={draw, fill=acc!8, minimum width=30mm, minimum height=7mm, align=center, font=\scriptsize, inner sep=2pt}] \definecolor{acc}{HTML}{2348F2} % the case text on the left \node[cs] at (-0.2,1.0) {icode in (OPq, rrmovq, rmmovq, pushq) : rA}; \node[cs] at (-0.2,0) {icode in (popq, ret) : RRSP}; \node[cs] at (-0.2,-1.0) {1 : RNONE}; % the mux \node[mx] (m) at (8.6,0) {srcA\\mux}; \draw[->] (6.6,1.0) -- (m.152) node[pos=0.3,above,font=\scriptsize]{rA}; \draw[->] (6.6,0) -- (m.180) node[pos=0.3,above,font=\scriptsize]{4}; \draw[->] (6.6,-1.0) -- (m.208) node[pos=0.3,above,font=\scriptsize]{F}; \draw[->] (m.east) -- ++(1.4,0) node[anchor=west]{srcA}; % select logic below \node[cmp] (c1) at (8.6,-2.6) {\texttt{icode} = 6, 2, 4, or A?}; \draw[->, acc] (c1.north) -- (m.south) node[midway,right,font=\scriptsize,text=acc]{select}; \draw[->] (8.6,-3.6) -- (c1.south) node[pos=0,below,font=\footnotesize]{\texttt{icode}}; \end{tikzpicture} $$ Two things follow from this compilation, and they define hardwired control. First, **there is no order of evaluation**: comparators and mux settle together, within the propagation delay of the gates. Second, **every control signal is computed on every cycle for every instruction**: the `srcA` mux produces an answer even when the instruction reads no register; the answer is just `RNONE` and nothing downstream uses it. One blob of combinational logic serves all twelve instructions because each instruction merely selects a different path through the same muxes. No gate is ever "off"; gates the instruction does not need simply compute values that no state element keeps. ## The ALU: function and input selection The Execute stage is one ALU plus the two muxes feeding it. Two control signals pick its inputs, one picks its function, and one decides whether its result sets the condition codes. - **`aluA`** (the ALU's `A` operand) is `valA` for `OPq` and `rrmovq`; `valC` for `irmovq`, `rmmovq`, `mrmovq`; and the constant $\pm 8$ for the stack instructions — $-8$ for `pushq`/`call`, $+8$ for `popq`/`ret`. - **`aluB`** (the `B` operand) is `valB` for `OPq`, the memory and stack instructions; and `0` for `irmovq` and `rrmovq` (passing `aluA` straight through). - **`alufun`** is the `OPq` `ifun` for `OPq`, and `ADD` for everything else: addresses and stack adjustments are all additions. - **`set_cc`** is true only for `OPq`: only arithmetic updates the condition codes. ```c [seq-execute.hcl] /* aluA: the A input to the ALU */ word aluA = [ icode in { IRRMOVQ, IOPQ } : valA; icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ }: valC; icode in { ICALL, IPUSHQ } : -8; icode in { IRET, IPOPQ } : 8; /* no other instruction uses the ALU */ ]; /* aluB: the B input to the ALU */ word aluB = [ icode in { IRMMOVQ, IMRMOVQ, IOPQ, ICALL, IPUSHQ, IRET, IPOPQ } : valB; icode in { IRRMOVQ, IIRMOVQ } : 0; ]; /* alufun: OPq uses its ifun; all others add */ word alufun = [ icode == IOPQ : ifun; 1 : ALUADD; ]; /* set_cc: only arithmetic touches the condition codes */ bool set_cc = icode in { IOPQ }; ``` The single adder in the ALU therefore serves four duties: arithmetic results (`valB OP valA`), effective addresses (`valB + valC`), immediate pass-through (`0 + valC`), and stack-pointer adjustment (`valB ± 8`). Reusing one adder this way is the whole reason `aluA`/`aluB` are muxes. ## The branch condition: Cnd One small combinational unit, `Cond`, turns the three condition-code bits and `ifun` into the one-bit answer `Cnd`. It serves double duty: `jXX` uses it to pick the next PC, and `cmovXX` uses it to gate `dstE`. The logic is a direct transcription of what each comparison means for signed arithmetic — `ZF` says the last `OPq` result was zero, `SF` says it was negative, and `OF` says it overflowed, so "signed less than" is `SF` disagreeing with `OF`. $$ % caption: The Cond unit. Inputs are ifun and the three condition codes; the output % caption: Cnd feeds the PC-select logic (for jXX) and the dstE gate (for cmovXX). % caption: Each row is a small Boolean function of ZF, SF, OF. \begin{tikzpicture}[font=\footnotesize, lbl/.style={anchor=east, text=acc, font=\ttfamily\footnotesize}, row/.style={anchor=west, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \draw[acc!40] (-1.9,0.45) -- (7.4,0.45); \foreach \y/\mn/\cond in { 0/{jmp, rrmovq}/{always 1}, -0.75/{jle, cmovle}/{(SF xor OF) or ZF}, -1.5/{jl, cmovl}/{SF xor OF}, -2.25/{je, cmove}/{ZF}, -3.0/{jne, cmovne}/{not ZF}, -3.75/{jge, cmovge}/{not (SF xor OF)}, -4.5/{jg, cmovg}/{not (SF xor OF) and not ZF}} { \node[lbl] at (0.3,\y) {\mn}; \node[row] at (0.7,\y) {\cond}; \draw[acc!40] (-1.9,\y-0.37) -- (7.4,\y-0.37); } \end{tikzpicture} $$ Written in HCL for the two cases we meet most: ```c [seq-cond.hcl] bool cnd_e = ZF; /* je, cmove */ bool cnd_l = SF ^ OF; /* jl, cmovl */ bool cnd_le = (SF ^ OF) || ZF; /* jle, cmovle */ /* the rest are negations and conjunctions of these */ ``` `jle` is $(\text{SF} \oplus \text{OF}) \lor \text{ZF}$ because a signed $a \le b$ comparison is done by computing $b - a$ and checking whether the result was zero (`ZF`) or genuinely negative (`SF` differing from `OF`, which corrects for overflow). The [control-flow lesson](/computer-architecture/machine-level-x86-64/control-flow) derived these identities; here they simply get wired in. Feed the unit a real flag setting and read the outputs off the table. Suppose the last `OPq` computed `5 - 8 = -3`: the result is negative and did not overflow, so `ZF = 0`, `SF = 1`, `OF = 0`. Then `SF ^ OF = 1`, and every condition depending on it resolves at once: `jl`/`cmovl` fires (`SF ^ OF = 1`, "less"); `jle`/`cmovle` fires (`(SF ^ OF) or ZF = 1`); `je`/`cmove` does not (`ZF = 0`); `jge`/`cmovge` does not (`not(SF ^ OF) = 0`); `jg`/`cmovg` does not. So after `5 - 8` a `jl` branches and a `jge` falls through — which is right, since $5 < 8$. Now suppose instead the subtract overflowed, giving `SF = 0` while the true result was negative: `SF ^ OF` is still 1 (because `OF = 1`), and `jl` still fires. That single XOR is what makes the branch correct even when the arithmetic wrapped, and it is why the `Cond` unit tests `SF ^ OF` rather than `SF` alone. ## Memory control and address The Memory stage needs to know three things: whether to read, whether to write, and at what address. All three are `case` expressions on `icode`. - **`mem_read`** is true for `mrmovq`, `popq`, and `ret` — the instructions that load a word into `valM`. - **`mem_write`** is true for `rmmovq`, `pushq`, and `call` — the instructions that store a word. - **`mem_addr`** is `valE` for `rmmovq`, `mrmovq`, `pushq`, and `call` (the computed effective address or the decremented stack top), and `valA` for `popq` and `ret` (the **old** stack top, before the increment). - **`mem_data`**, the value stored, is `valA` for `rmmovq` and `pushq`, and `valP` for `call` (the return address). ```c [seq-memory.hcl] bool mem_read = icode in { IMRMOVQ, IPOPQ, IRET }; bool mem_write = icode in { IRMMOVQ, IPUSHQ, ICALL }; /* address: computed valE, except popq/ret use the old %rsp in valA */ word mem_addr = [ icode in { IRMMOVQ, IPUSHQ, ICALL, IMRMOVQ } : valE; icode in { IPOPQ, IRET } : valA; ]; /* data to store: valA, except call stores the return address valP */ word mem_data = [ icode in { IRMMOVQ, IPUSHQ } : valA; icode in { ICALL } : valP; ]; ``` The `mem_addr` mux is the row to check against the stage tables: `popq` and `ret` must read the word at the stack top as it was _before_ the increment, and the unincremented pointer lives in `valA`. Feeding `valE` there instead is the classic off-by-eight bug — the design would pop the word just _above_ the top. ## PC selection: the next-instruction mux Everything funnels into one signal, `newPC`, chosen by a three-input mux. The default is `valP`, the fall-through; a `call` or a **taken** jump uses `valC`; a `ret` uses `valM`, the address it just popped. $$ % caption: The next-PC mux. The default newPC is valP (fall through). A call or a % caption: taken jump (Cnd from the condition codes) selects valC; a ret selects valM, % caption: the address just loaded from the stack. The selected value clocks into PC. \begin{tikzpicture}[font=\footnotesize,>=stealth, mux/.style={draw, fill=acc!8, inner sep=2pt}] \definecolor{acc}{HTML}{2348F2} \node[mux, minimum width=14mm, minimum height=30mm, align=center] (m) at (0,0) {New\\PC}; \node[anchor=east] at (-2.6,1.05) {$\mathtt{valC}$}; \node[anchor=east] at (-2.6,0) {$\mathtt{valM}$}; \node[anchor=east] at (-2.6,-1.05){$\mathtt{valP}$}; \draw (-2.6,1.05) -- (-0.7,1.05) node[midway,above,font=\scriptsize]{call / jump taken}; \draw (-2.6,0) -- (-0.7,0) node[midway,above,font=\scriptsize]{ret}; \draw (-2.6,-1.05)-- (-0.7,-1.05) node[midway,below,font=\scriptsize]{otherwise}; \draw[->] (m.east) -- ++(2.0,0) node[anchor=west,text=acc] {$\mathtt{PC}$ register}; \node[anchor=south] at (0,1.9) {icode, Cnd}; \draw[->] (0,1.85) -- (m.north); \end{tikzpicture} $$ ```c [seq-pc.hcl] /* the next program counter */ word newPC = [ icode == ICALL : valC; /* jump to the call target */ icode == IJXX && Cnd : valC; /* taken branch */ icode == IRET : valM; /* return address off the stack */ 1 : valP; /* fall through */ ]; ``` ## One instruction, every signal at once To see how the pieces fit together, fix an instruction and evaluate every case expression for it. Take `popq %rbx` (`icode = B`): - `srcA = %rsp`, `srcB = %rsp`: both read ports fetch the stack pointer; - `dstE = %rsp`, `dstM = rA = %rbx`: both write ports will be used; - `aluA = 8`, `aluB = valB`, `alufun = ADD`, `set_cc = 0`: the ALU increments; - `mem_read = 1`, `mem_write = 0`, `mem_addr = valA`: read the old top; - `newPC = valP`: `popq` is not a control transfer. Ten muxes settled, and the datapath _is_ a `popq` executor for this cycle. Feed it `icode = 6` next cycle and the same gates settle into an `OPq` executor. That is hardwired control: the machine is effectively re-wired every cycle by re-evaluating every `case` at gate speed. A store instruction exercises a different subset, including the memory signals. Take `rmmovq %rax, 8(%rdx)` (`icode = 4`), which writes `%rax` to the address `8 + R[%rdx]`: - `srcA = rA = %rax`, `srcB = rB = %rdx`: read the value to store and the base; - `dstE = RNONE`, `dstM = RNONE`: `rmmovq` writes no register, so both write ports idle; - `aluA = valC`, `aluB = valB`, `alufun = ADD`, `set_cc = 0`: form the address `valE = valB + valC`; - `mem_write = 1`, `mem_read = 0`, `mem_addr = valE`, `mem_data = valA`: store `%rax` to the computed address; - `newPC = valP`: fall through. Compare it against `popq` line by line: `popq` read memory and wrote two registers; `rmmovq` writes memory and no register. Same ten `case` expressions, evaluated on a different `icode`, and the datapath becomes a different machine. Notice too that `dstE` and `dstM` both land on `RNONE` here — the default line of their `case` expressions — so the register file's two write ports simply do nothing this cycle, exactly as the empty Write-back row of the `rmmovq` stage table demanded. ## Hardwired vs. microprogrammed control Everything above is **hardwired control**: each signal is a fixed combinational function of `icode`, realized as a tree of gates that settles within one clock period. There is no sequencer stepping through steps — the "sequencing" is just the data flowing through the stages in one cycle. It is fast and, for a regular ISA like Y86-64, compact. > **Definition (Hardwired vs. microprogrammed control).** _Hardwired_ control > computes each datapath signal directly from `icode` with fixed combinational logic > (the HCL above). _Microprogrammed_ control instead stores, in a small control ROM, a > sequence of micro-instructions per machine instruction; a microsequencer steps a > micro-PC through them, and each micro-instruction's bits drive the datapath for one > step. The microprogrammed style trades speed for flexibility: a complex, irregular ISA (the historical reason microcode was invented) is easier to express as little programs in a ROM than as a forest of special-case gates, and the ROM can be patched after fabrication. The cost is an extra level of indirection — a control-store read per step — so it is slower. Y86-64's regularity makes hardwired control the obvious choice, and it is what this module builds. ## Microcode, from Wilkes to today The choice between the two styles shaped decades of processor design. Microprogramming was proposed by Maurice Wilkes in 1951 (Wilkes, "The Best Way to Design an Automatic Calculating Machine," Manchester University Computer Inaugural Conference) precisely to tame control complexity: rather than hand-designing the tangle of gates that hardwired control demands, a designer writes each machine instruction as a short program of micro-instructions in a control store. As instruction sets grew ornate through the 1960s and 1970s — the DEC VAX being the canonical example, with instructions like a single polynomial-evaluation opcode — microcode was what made them buildable and patchable at all. The pendulum swung back with RISC. CS:APP's aside on RISC versus CISC (Bryant & O'Hallaron, _CS:APP_ §4.1) tells the story: RISC architectures deliberately kept instructions simple and regular enough to hardwire, betting that a fast, hardwired, pipelined implementation of a lean instruction set would beat a microcoded implementation of a rich one — and, with better compilers, it largely did. But the resolution was a hybrid, not a winner. Modern x86 processors, whose instruction set is irreducibly CISC, hardwire the common, simple instructions for speed and fall back to microcode only for the rare, complex ones (CS:APP §5.7). The control store survives for another reason too: it is patchable after the chip ships, which is how vendors distribute microcode updates to fix errata in the field — a capability a pure hardwired design cannot offer. Y86-64 sits at the RISC-friendly end of this spectrum, which is why the entire control unit of this module fits on a page of HCL `case` expressions rather than a ROM full of little programs. > **Takeaway.** Every SEQ control signal is a `case` expression on `icode`, and every > `case` compiles to a mux plus comparator select logic: > `srcA`/`srcB`/`dstE`/`dstM` pick register ports (`%rsp` for the stack instructions, > `RNONE` to idle a port, `rB`-if-`Cnd` for conditional moves); `aluA`/`aluB`/ > `alufun` feed the one shared adder; `mem_read`/`mem_write`/`mem_addr`/`mem_data` > drive the memory port; `Cond` turns `CC` and `ifun` into `Cnd`; and `newPC` muxes > `valC` (call/taken jump), `valM` (ret), or `valP` (otherwise). All of it is > combinational, all of it evaluates every cycle, and each instruction is just a > different setting of the same muxes. The control logic and the stage computations are now both written down. The [next lesson](/computer-architecture/processor-design/assembling-seq) wires the functional units and these signals into the complete SEQ datapath.