Control Logic and Sequencing

The stage tables 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 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 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.

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:

A conditional move that fails sets dstE = RNONE and writes nothing.

/* 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.

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.

/* 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.

Written in HCL for the two cases we meet most:

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})\vee \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 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).

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.

/* 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.

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.

The control logic and the stage computations are now both written down. The next lesson wires the functional units and these signals into the complete SEQ datapath.