What logic synthesis is
Logic synthesis turns a register-transfer level (RTL) description, which says what a circuit should compute, into a gate-level netlist built from a standard-cell library, optimized for power, performance, and area. It is the front of the physical-design flow: the netlist it produces is what floorplanning, placement, clock tree synthesis, and routing then implement. If synthesis builds bloated or slow logic, no amount of good placement recovers it, so the quality of results is set here first.
Synthesis works in three passes. It first simplifies the logic with no knowledge of the target library, then maps that logic onto real library cells, and alongside both it optimizes the sequential elements, the flip-flops. The passes are kept apart because they answer different questions with different cost models.
| pass | question it answers | example moves |
|---|---|---|
| technology-independent optimization | what is the smallest logic that computes this function | Boolean minimization, factoring, constant propagation |
| technology mapping | which library cells cover that logic most cheaply | decompose, match, cover for area or for delay |
| sequential optimization | where should the registers sit, and how should state be encoded | retiming, state encoding |
Technology-independent optimization
Before any library is chosen, synthesis works on an abstract Boolean network and shrinks it. The cost it minimizes is the amount of logic, counted as literals (each appearance of a variable or its complement) or as gates.
Two-level minimization. Any Boolean function can be written as a sum of products (SOP), an OR of AND terms. The minimal two-level form uses the fewest, largest product terms that still cover every input combination for which the function is 1. Those largest terms are the prime implicants, and choosing the smallest set of prime implicants that covers all the 1s is the classic minimization problem.
- product term: one AND of some inputs, a single gate in the AND plane
- prime implicant: a product term that cannot be made larger (fewer literals) while still covering only 1s
A term that covers a 1 no other chosen term covers is essential and must be taken. The rest are chosen to cover what is left at the least cost.
Multi-level optimization and factoring. Two-level form is rarely the smallest overall. Multi-level logic shares subexpressions: if the same term appears in several places it is built once and fanned out. Factoring pulls a common factor out of an expression, turning a flat sum of products into a smaller multi-level structure.
The left side uses eight literals in four product terms. The right uses four literals in two small gates. Same function, less logic.
Constant propagation and dead-logic removal. When an input is tied to a constant (a mode pin strapped, an unused feature disabled), that constant flows through the network: an AND with a constant 0 is 0, an OR with a constant 1 is 1, and so on. Gates whose outputs become constant, and gates whose outputs no longer drive anything, are swept away. This is often the cheapest large win, because a tied configuration can remove whole cones of logic.
Technology mapping
Now the optimized network is turned into real cells. It is first decomposed into a canonical base of simple gates, typically 2-input NAND (Not-AND) gates and inverters, which forms an and-inverter graph. Then the library cells (inverter, NAND2, NOR2 (Not-OR), AOI21 (AND-OR-Invert), and larger complex gates) are used to cover that graph: choose a set of cell-sized patterns that tile every node, each node covered once, at the least cost.
- cover: an assignment of library cells to the nodes of the decomposed graph so that together they compute the same function
- a complex cell such as AOI21 (AND-OR-Invert) covers several base nodes at once, usually cheaper than the equivalent separate gates
For a tree, dynamic programming from the leaves up gives the provably cheapest cover. A general graph with reconvergent fanout is harder, and is covered heuristically.
Area versus delay. The smallest cover is usually not the fastest. Under a delay cost the mapper spends area to shorten the critical path: it picks larger, stronger cells on the late paths and may duplicate logic so signals arrive in parallel rather than in series.
The same decomposed graph, mapped once for area and once for delay, gives two different netlists. Which one is right depends on whether the block is area-limited or timing-limited, which is why the cost function is an input to synthesis, not a fixed rule.
Sequential optimization
Retiming. A pipeline's clock period is set by its slowest combinational stage, the longest run of logic between two flip-flops. Retiming relocates flip-flops across combinational gates, without changing what the circuit computes at its inputs and outputs, so the stages are balanced and the slowest one is as fast as possible.
Moving a register earlier shortens the stage after it and lengthens the stage before it, so retiming is a balancing act: push registers off the heavy stage onto the light one until no single stage dominates.
State encoding. A finite-state machine (FSM) has a set of named states, and the synthesizer must assign each a binary code stored in the state flip-flops. The encoding decides how much next-state and output logic is needed: codes that place related states close together make the transition logic simpler. Dense binary uses the fewest flip-flops. One-hot (one flip-flop per state) uses the most flip-flops but often the least and fastest next-state logic. The right encoding depends on the machine.
Datapath and operator selection
An arithmetic operator like + in the register-transfer level (RTL) is not one circuit: it has many gate-level implementations that compute the same result with very different power, performance, and area. An adder can be a ripple-carry chain (small, but the carry ripples through every bit, so it is slow) or a carry-lookahead or carry-select structure (larger, but the carry is computed in parallel, so it is fast). Synthesis selects the architecture that meets the delay target at the least area, which is why the same + can synthesize to very different gate counts in a timing-critical block versus an area-critical one.
Where synthesis hands off
The gate-level netlist goes to floorplanning and placement, and its timing is later re-checked in static timing analysis (STA). Some optimizations do not end at synthesis: timing-driven restructuring and gate sizing return as engineering change order (ECO) moves once the design is placed and real wire delays are known, so the ECO topic revisits them with layout in hand. In the open-source flow, Yosys performs synthesis and calls ABC for the technology-independent optimization and technology mapping described above.