Synthesis

From schematics to code said that a tool turns Verilog into gates. That tool is a synthesiser, and this page watches one work. It’s Yosys, running in the page: the same program, on the same Verilog, that would build the design for a real chip.

1 · What synthesis does

Synthesis is a series of passes, each turning the design into something a little closer to hardware:

Processes. Every always block is turned into hardware it could be: its ifs and cases into multiplexers, a clocked block into flip-flops, and each operator into a cell of its own: + into an adder, == into a comparator.
Optimisation. Constants are worked out, duplicate cells merged, logic nothing uses thrown away, and buses cut down to the bits that matter.
Gates. Every cell is broken into single-bit gates, and the whole lot simplified by ABC, a logic optimiser from the University of California, Berkeley: by program, what a Karnaugh map does by hand, on circuits far too big for one.
Technology mapping. The gates are fitted onto the parts the target actually has. A chip designed from scratch has a library of gates to choose from; an FPGA has its own fixed parts, and these pages use the iCE40’s.

Choose a design and a stage. Each stage is drawn as a netlist: the inputs on the left, the outputs on the right, and each cell placed after the cells that feed it. Thick wires are buses; dashed ones loop back, out of a flip-flop. The full adder is 5 gates at stage 3 and 2 look-up tables at stage 4, one per output. The 8-bit adder is 55 gates, but 8 LUTs and 8 carry cells on the FPGA. The ALU, Part 1’s in 26 lines of Verilog, is 288 gates: too many to draw.

2 · Processes become multiplexers, flip-flops and tables

At stage 1, the counter’s if (reset || count == 9) count <= 0; else count <= count + 1; is an adder, a comparator, an OR, and a multiplexer choosing between 0 and count + 1, feeding a flip-flop: exactly the counter from Clocked circuits, worked out from the code.

The decoder’s case doesn’t become multiplexers at all. Yosys sees that every row gives a constant, and makes a ROM: a table of contents, read at address d. That’s the 7-segment ROM on Memory and buses, found by the tool. (On the FPGA it then becomes logic again, since a 16-entry table is just seven truth tables.)

3 · Optimisation

Stage 2 tidies. In the counter, the multiplexer that chooses 0 has gone: the iCE40’s flip-flops, like many, can reset themselves, so Yosys folds “choose 0 when reset” into a flip-flop with a reset, one cell where there were two. Optimisations like this are why synthesised hardware is often smaller than the obvious drawing of the code.

4 · An FPGA’s parts: look-up tables

An FPGA has no AND gates or OR gates. Its basic part is a look-up table (LUT): a tiny memory with 4 address inputs and 16 one-bit entries, so it can hold any 4-input truth table at all. To an FPGA, every function of up to 4 inputs costs the same, one LUT, however complicated it is.

That changes what’s cheap. The decoder is 33 gates at stage 3, but each segment depends only on d’s four bits, so on the FPGA it’s exactly 7 LUTs, one per segment. Click a LUT at stage 4 to see the truth table stored in it. The 8-bit adder, on the other hand, would need a long chain of LUTs for its carries, so the iCE40 has a separate carry chain, a fast dedicated wire from each column to the next: 8 LUTs for the sums, and 8 carry cells. Inside an FPGA looks at both.

5 · A latch by mistake

An always @* block describes logic with no memory, but only if it gives every output a value every time. Here’s the decoder again, with its default row left out:

For d from 10 to 15, the block doesn’t say what s should be, so s has to keep its old value, and that takes memory: Yosys builds a latch (red) and warns. Look at stages 1 and 3, then switch to the decoder with its default: no latch. The iCE40 flow refuses the latch outright at stage 4, with an error.

Latches by mistake are one of the commonest bugs in Verilog. The fix is always the same: give every output a value in every case, with a default, or a value at the top of the block, as the ALU does.

6 · How big is a CPU?

The 6502 from Part 2 has been written in Verilog too, for these pages: about 750 lines, exact to the bus cycle like the emulator, and checked the same way, in simulation, against all 1,510,000 of Tom Harte’s tests and Klaus Dormann’s functional test. (It’s in the site’s source, under sites/cpu/hdl.) Yosys and nextpnr make it, for the UP5K:

	LUTs	Flip-flops	Carry cells	Logic cells (of 5,280)	Fastest clock
The 6502	961	147	173	1,098	18.5 MHz
The whole little computer, with its devices	1,427	276	266	1,616	17.8 MHz

A whole processor in about a fifth of a small FPGA, able to run eighteen times as fast as the little computer’s 1 MHz. The original chip ran at 1 or 2 MHz, but it was 3,500 transistors laid out by hand.

Summary

A synthesiser turns Verilog into hardware in stages: processes into multiplexers, flip-flops and cells, then optimisation, then gates, then the target’s own parts (technology mapping).
Yosys spots patterns: a case of constants becomes a ROM, a multiplexer to 0 becomes a flip-flop’s reset.
An FPGA’s logic is 4-input look-up tables, each any truth table of 4 inputs, plus carry chains for adding.
An always @* that leaves an output unset in some case makes a latch, almost always by mistake.
The 6502 in Verilog takes 1,098 of the UP5K’s 5,280 logic cells.