Combinational Logic and HCL

The previous lesson built gates and wired a few together by hand. That does not scale: a real datapath has thousands of gates, and drawing each one is hopeless. Engineers describe hardware in text instead, with a hardware description language, and a tool turns the text into gates. CS:APP uses a small teaching language called HCL (Hardware Control Language) for exactly this, and the Y86-64 processor we build later is written in it. This lesson covers what kind of logic HCL describes (combinational logic) and the handful of constructs the language provides.

Combinational versus sequential

Every digital circuit falls into one of two camps, and the distinction is about memory.

A sequential circuit, by contrast, has state: its outputs depend on the history of inputs, not just the present ones. The memory elements of the next two lessons (latches, flip-flops, registers) are sequential; everything in this lesson and the next is combinational. Two rules keep a network combinational:

Every input to each gate is either a primary input or the output of another gate. No wire dangles.
There are no cycles: no path leads from a gate's output back to its own input. Feedback is what creates memory, so forbidding it guarantees there is none.

The mental model is a cloud of gates: signals enter on the left, ripple through, and emerge on the right, with the only delay being the time for the slowest path of gates to settle.

A combinational block is a Boolean function of its current inputs. Input signals enter a cloud of acyclic gate logic and, after propagation, stable outputs emerge. No feedback, no memory.

Gate delays and the critical path

After a brief propagation delay hides the number that decides how fast a processor can run. Each gate contributes the $t_{p d}$ of the previous lesson, and delays accumulate along paths: a gate's output cannot begin to settle until its latest-arriving input has, so the arrival time at any wire is the maximum over the paths feeding it. The output of the whole block settles when its slowest path does.

The accounting is mechanical. Take a small network with three gates: an AND and an OR at 25 ps each, and an XOR at 75 ps (internally it is three gate levels: inverters, ANDs, OR), wired so that one input must traverse all three.

Gate-delay accounting. Inputs are valid at t = 0; each gate adds its delay to its latest-arriving input. The highlighted path a - g1 - g2 - g3 accumulates 25 + 25 + 75 = 125 ps and is the critical path: no output of this block can be trusted before 125 ps.

Input $d$ reaches the XOR at $t = 0$ but does not help: the XOR's other input arrives at $t = 50$ , and only then does its own 75 ps start counting. The wire $f$ settles at $t = 125$ ps, and the path that set the number — $a$ through all three gates — is the critical path.

The critical path is what bounds the clock. In the synchronous designs of lesson 4, combinational blocks sit between storage elements, and the clock period must be long enough for the slowest block to settle: a path forty gate levels deep at 25 ps per level needs a nanosecond, capping the clock at 1 GHz no matter how fast every other block is. Making a processor faster is therefore mostly a matter of shortening the worst path, not the average one: replace a deep circuit with a shallow one (the carry-lookahead adder of the next lesson is the classic case), or cut a long path in half with a register and spend two cycles, which is the whole idea of pipelining, later in the course.

One more consequence of unequal path delays: on the way to settling, an output may pass through values that are wrong. If two inputs of an OR gate swap roles, one falling and the other rising a moment later, the output can dip low for the skew between them, a transient called a glitch (or hazard).

A glitch. Input x falls before input y rises, so their OR dips low for the interval between the two edges before settling back to 1. The final value is correct; the waveform on the way there is not.

Combinational logic guarantees only the settled value, not the waveform on the way there: outputs are meaningful after settling, and the clock enforces that nothing samples earlier. That contract (wait out the worst case, then sample) is the reason glitches are harmless in a properly clocked design.

Working the arrival times as a table

The graphical accounting scales to a spreadsheet. Number the gates, and for each one write down when its inputs are ready and add its own delay. The arrival time at a gate's output is $max (input arrivals) + t_{p d}$ ; the block's outputs are ready at the max over all of them. Take a slightly bigger network: inputs $a, b, c, d, e$ valid at $t = 0$ , and five gates wired

g_{1} = a \land b, g_{2} = c \lor d, g_{3} = g_{1} \oplus e, g_{4} = g_{2} \land g_{3}, f = g_{4} \lor g_{1},

with delays AND/OR $= 20$ ps, XOR $= 60$ ps. Fill the table left to right, each row depending only on rows above it:

gate	inputs	input arrival (max)	$+ t_{p d}$	output ready
$g_{1}$	$a, b$	$0$	$20$	$20$
$g_{2}$	$c, d$	$0$	$20$	$20$
$g_{3}$	$g_{1}, e$	$max (20, 0) = 20$	$60$	$80$
$g_{4}$	$g_{2}, g_{3}$	$max (20, 80) = 80$	$20$	$100$
$f$	$g_{4}, g_{1}$	$max (100, 20) = 100$	$20$	$120$

The output $f$ settles at $120$ ps, and tracing the max backward names the critical path: $f \leftarrow g_{4} \leftarrow g_{3} \leftarrow g_{1} \leftarrow a$ (or $b$ ). The XOR $g_{3}$ dominates because its 60 ps sits on that chain; the parallel branch through $g_{2}$ finishes at $20$ ps and waits idle. Two lessons fall out of the table. First, speeding up $g_{2}$ does nothing — it is not on the critical path — so effort spent there is wasted, a recurring mistake of optimizing the average instead of the worst case. Second, if this block sits between clocked registers, the clock period must exceed $120$ ps plus the flip-flop overheads the clocking lesson adds. Every real timing tool is this table run over millions of gates.

Don't-cares

Sometimes a truth table has rows you genuinely do not care about, because those input combinations can never occur or the output is never used when they do. Marking such rows as don't-cares (written $\times$ ) instead of forcing a $0$ or $1$ gives the synthesizer freedom, which translates into smaller circuits.

A concrete case: a 4-bit input $b_{3} b_{2} b_{1} b_{0}$ holds a decimal digit $0$ – $9$ (binary-coded decimal), and we want $f = 1$ when the digit is $5$ or more. The six patterns $10$ – $15$ can never arrive, so their rows are don't-cares:

digit	$b_{3} b_{2} b_{1} b_{0}$	$f$
$0$ – $4$	`0000`–`0100`	$0$
$5$ – $9$	`0101`–`1001`	$1$
(unused)	`1010`–`1111`	$\times$

Forced to output $0$ on the unused rows, the minimal circuit is $f = b_{3} \overline{b_{2}} \overline{b_{1}} + \overline{b_{3}} b_{2} (b_{1} + b_{0})$ ; it must carefully exclude the impossible patterns. Allowed to output anything on them, the synthesizer can pick $1$ for the unused rows and the function collapses to

f = b_{3} + b_{2} (b_{1} + b_{0}),

three gates instead of six or seven. The Karnaugh map shows why the don't-cares are worth so much. Lay $f$ out on a four-variable map, $b_{3} b_{2}$ down the side and $b_{1} b_{0}$ across the top, both in Gray-code order, and mark the six impossible patterns $\times$ :

The digit-at-least-5 function on a 4-variable K-map. The six impossible patterns 10-15 are don't-cares (marked d). Grouped as 1s, they let the whole bottom half (b3 = 1) merge into one term, and the two real 1s in the b3 = 0 half give b2(b1 + b0), so f = b3 + b2(b1 + b0).

The whole lower half of the map — the eight cells where $b_{3} = 1$ — is now all $1$ s and $\times$ s, so it merges into the single term $b_{3}$ : an eight-cell block naming one variable. The two remaining real $1$ s in the $b_{3} = 0$ half (digits $5$ – $7$ , all with $b_{2} = 1$ and at least one of $b_{1}, b_{0}$ set) contribute $b_{2} b_{1}$ and $b_{2} b_{0}$ , which factor to $b_{2} (b_{1} + b_{0})$ . Read off the map: $f = b_{3} + b_{2} (b_{1} + b_{0})$ . Without the don't-cares, that bottom-half block would have holes at digits $10$ – $15$ and could not merge, forcing the clumsier five-literal expression. The freedom to fill impossible cells with whichever value grows a block is precisely what buys the smaller circuit.

HCL has the same freedom built into its case expression below: the selects you list are the cases you care about, and a final default arm sweeps up the rest.

HCL: describing logic as expressions

HCL lets you write a circuit as expressions, much like a programming language, and a compiler maps the expressions onto gates. It has two kinds of signal. A bit-level signal is a single wire carrying $0$ or $1$ ; a word-level signal is a bundle of wires carrying an integer (in Y86-64, typically 64 bits wide).

The bit-level operators are written like C's logical operators but mean plain single-bit gates, because every HCL bit signal is already one bit:

&& is AND, || is OR, ! is NOT.

So s1 && !s0 is one AND gate fed by s1 and an inverted s0. There is no short-circuiting here: this is hardware, and both inputs to the AND gate exist as wires at all times. A bit-level HCL expression is just a Boolean formula, and the compiler realizes it as the corresponding gate network.

bitlevel.hclc

bool xor   = (a && !b) || (!a && b);   /* 1 when a, b differ */
bool eq    = !xor;                     /* 1 when a, b are equal */
bool maj   = (a && b) || (a && c) || (b && c);  /* majority of three */

The bool keyword declares a single-bit signal. These three lines describe the XOR, equality, and majority circuits from the previous lesson: the same gates, now as text a tool can synthesize.

Word-level signals and equality nets

A word-level signal carries many bits at once; we write word for a 64-bit signal. Comparisons between word signals produce a bit result, realized in hardware as a tree of XNOR gates (per-bit equality) feeding one big AND.

wordlevel.hclc

word Reg;                   /* a 64-bit word signal */
bool isZero = (Reg == 0);   /* 1 iff every bit of Reg is 0 */
bool isRSP  = (rA == RRSP); /* register-id field equals the stack pointer id */

Equality ==, inequality !=, and the ordering comparisons are all word-level operators that return a bit. At the gate level Reg == 0 asks are all 64 bits zero? — a 64-input NOR — and rA == RRSP compares two 4-bit register-id fields bit for bit. The point is that HCL hides the gate tree: you write the comparison, the synthesizer builds the XNOR-and-AND network.

Names like RRSP follow a convention kept throughout the processor module: capitalized HCL constants stand for fixed nibble values from the instruction encoding. IOPQ is the icode of the OPq instructions (6), RRSP the register id of %rsp (4), RNONE the no register id (0xF), ALUADD the ALU's add function code (0). Writing rA == RRSP instead of rA == 4 costs nothing in hardware — both compile to the same comparator against a constant — and it lets the control logic read as intent rather than magic numbers.

What A == B costs in gates, shown for 4 bits. One XNOR per bit pair answers "do these bits match?"; an AND tree combines the answers into a single eq bit. A 64-bit compare is the same shape, six AND levels deep.

The tree shape matters for speed: combining 64 bit-equalities pairwise takes $log_{2} 64 = 6$ AND levels, not 63: the same balanced-tree structure the fast adder of the next lesson applies to carries.

One more word-level form appears constantly in the processor's control logic: set membership, written in. The expression icode in { IOPQ, IRRMOVQ } asks whether the word icode equals any member of the listed set, and it compiles to exactly what that suggests — one equality comparator per member, their outputs ORed together.

membership.hclc

bool need_regids =
    icode in { IRRMOVQ, IOPQ, IPUSHQ, IPOPQ, IIRMOVQ, IRMMOVQ, IMRMOVQ };
/* same circuit as: icode == IRRMOVQ || icode == IOPQ || ... */

A five-member test on a 4-bit field is five 4-bit comparators feeding a 5-input OR — cheap, fixed-delay hardware. The processor module's case expressions are guarded almost entirely by membership tests (is this one of the instructions that reads memory?), and each one is just an OR of equality nets.

The case expression is a multiplexer

The construct that carries most of HCL's weight is the case expression, written with square brackets. It is a list of pairs, each a Boolean select and a word-level value:

case.hclc

word Out = [
    s2 : A;      /* if s2 is true, Out = A      */
    s1 : B;      /* else if s1 is true, Out = B */
    1  : C;      /* else (default), Out = C     */
];

The semantics are priority from top to bottom: scan the selects in order, and the value of the first one that is true becomes the result. A final select of 1 is the catch-all default, guaranteeing some case always matches, and doubling as the don't-care escape hatch: input combinations no listed select covers land in the default arm, where any value that keeps the hardware simple will do. This is not sequential if/else executed over time. It is a description of a multiplexer, a combinational circuit that routes one of several data inputs to the output according to the select signals. All the values $A$ , $B$ , $C$ exist on wires simultaneously; the selects merely steer which one reaches Out.

The case expression maps to a multiplexer tree. Each select drives a 2:1 mux; top-of-list priority means the highest matching select wins. With s2 true, A passes through regardless of s1.

The priority ordering matters: in the figure, if $s_{2}$ is true the top mux passes $A$ through and the value of $s_{1}$ is irrelevant, exactly matching the first true select wins. When the selects are mutually exclusive (at most one true at a time) the priority is harmless and the case reads like a plain table; when they can overlap, the top-down rule resolves the conflict. This single construct expresses nearly every control decision in a processor — which result the ALU produces, which register to write, whether to take a branch — and the next lesson shows the multiplexer it compiles to in full gate detail.

From HCL to industrial HDLs

HCL is a deliberately tiny language — bit and word signals, && || !, comparisons, in, and case. It exists to make the Y86-64 control logic readable, not to tape out a chip. The industrial languages it stands in for are worth knowing.

Verilog, VHDL, SystemVerilog. Real hardware is described in one of these. A combinational block that HCL writes as a case expression appears in Verilog as a always @(*) block with a case statement, or as a chain of continuous assigns; the synthesizer infers the same mux tree. The discipline these languages enforce, which HCL sidesteps by construction, is the split between combinational and sequential code. Assign a signal in an edge-sensitive block (always @(posedge clk)) and you get a flip-flop; assign it combinationally and you get gates. Forget to cover a case — leave a combinational signal unassigned on some path — and the tool infers an unwanted latch, a classic bug the linters warn about, and exactly the transparency hazard the next-lesson clock discipline is built to avoid. SystemVerilog added always_comb and always_ff precisely so the designer states which one they mean and the tool checks it.

The two-language problem and its escapes. Verilog and VHDL describe hardware at the register-transfer level: you specify every register and the logic between them. Newer flows raise the altitude. Chisel (Bachrach et al., 2012), a hardware construction language embedded in Scala, lets a generator emit families of circuits parametrically and compiles down to Verilog; it is what the open RISC-V Rocket and BOOM cores are written in. High-level synthesis goes further, compiling a restricted subset of C or C++ directly to RTL, trading designer control for productivity on datapath-heavy blocks. All of them still bottom out in the gates, muxes, and critical-path arithmetic of this lesson — the abstraction rises, the physics does not. The critical path is still the sum of gate delays on the worst route, and closing timing on it is still the central chore of every tape-out.

Next we build the multiplexers, decoders, and the ALU that these expressions stand for.