Logic synthesis

Synthesis is where the RTL first meets a real cell library, real timing goals and a real cost function. The tool’s job is to produce a gate-level netlist (a Verilog file listing every library cell instance and the wires between them) that does exactly what the RTL does, meets the timing constraints written in SDC with some margin, and leaves the layout tools a manageable problem. Synopsys Design Compiler and Fusion Compiler, Cadence Genus and open-source Yosys with ABC all follow the same broad order:

1. Elaborate the RTL into a generic circuit.
2. Optimize it without reference to any library.
3. Map it onto library cells.
4. Optimize incrementally for timing and power: resize cells, restructure logic, add buffers.¹

The quality of results here (QoR, in tool reports) sets a ceiling for the rest of the flow. Layout tools can resize cells, add buffers and restructure logic locally, but they rarely recover from a poorly structured arithmetic block or a badly encoded state machine. Most of the risk at this stage sits in the inputs and estimates rather than in the algorithms:

• Constraints. SDC that asks for too little leaves real paths unoptimized and unchecked. SDC that asks for too much wastes area and power.
• Wire estimates. Nothing is placed yet, so wire delay is a guess. When the guess disagrees with what placement later finds, timing moves. Physical-aware synthesis exists to narrow that gap.¹²
• Verification. Transformations such as retiming (moving flip-flops through the logic) and re-encoding state machines make it harder to prove, with equivalence checking, that the netlist still matches the RTL.

Real runs take more inputs than the table shows:

• A dont_use list of cells the tool must not pick.
• Modules or instances to keep intact rather than optimize across.
• Power intent, usually a UPF file, if the design has more than one voltage domain.
• Library sets that cover several threshold-voltage flavors (the same cells built to be faster and leakier, or slower and more frugal) and at least one slow corner for checking setup timing.
• For physical-aware runs, the technology LEF, the cell LEFs and a floorplan DEF (die size, positions of large blocks, blocked areas), so the tool can run a coarse placement while it optimizes.

The teams downstream need more than the netlist. Design for test needs to know which flip-flops sit behind clock-gating cells, and whether those cells’ test-enable pins are tied off or left for the scan chains. Floorplanning wants big blocks kept as separate modules. The equivalence checker needs the RTL, the netlist and any notes the synthesis tool wrote about flip-flops it renamed, merged or moved.

Elaboration and the generic netlist

Elaboration fixes parameter values, expands generate loops, connects the module hierarchy and turns each process (an always block) into word-level operators, multiplexer trees and storage elements. Yosys keeps these as coarse cells in its internal format, RTLIL (one cell for a whole 32-bit adder, say), and lowers them to single-bit gates later.² Its default synth script shows the order most tools follow:¹

1. proc converts processes into multiplexers and flip-flops.
2. fsm finds and re-encodes state machines, wreduce trims operators to the bit widths actually used, and alumacc gathers arithmetic into adder and multiply-accumulate units.
3. share merges operators that are never active together, and the memory passes recognize memories.
4. techmap lowers everything to generic single-bit gates, and abc optimizes and maps them.

Commercial tools add datapath synthesis, which picks an adder or multiplier architecture (a small, slow ripple-carry adder or a large, fast parallel-prefix one, for example) from the timing context. Review elaboration warnings before anything else. Latches nobody intended (from a combinational block that leaves a signal unassigned on some branch), truncated widths, nets driven from two places and missing modules turned into black boxes all show up here first.

Technology-independent optimization

The logic is restructured on an And-Inverter Graph (AIG), in which every function is a network of two-input ANDs whose connections may be inverted. That uniform form makes small local rewrites cheap. Two kinds alternate. Rewriting and refactoring replace small pieces of the graph with smaller equivalents, cutting the node count (a rough proxy for area) without adding levels. Balancing reshapes chains into trees, cutting the number of levels (a rough proxy for delay) without adding nodes.²⁵ “Under the hood” shows how. Structural transformations also run at this level:

• Resource sharing merges operators that are never active in the same cycle, such as two adders in different branches of a case, into one with a multiplexer on its inputs. It saves area but adds that multiplexer’s delay, so a timing-driven tool may decline to share, or un-share, on critical paths. Yosys proves the operators are mutually exclusive with a SAT solver.³
• State machines can be re-encoded. Yosys documents one-hot (one flip-flop per state) as its recoding target.⁴ Binary or Gray encodings use fewer flip-flops but deeper next-state logic. Either way, recoding changes the set of flip-flops, which matters for equivalence checking later.

Mapping against Liberty

Mapping covers the optimized graph with library cells: every node must end up inside some cell, and the cover should be fast on critical paths and small elsewhere. The cell data comes from the Liberty file:⁷

• area and leakage power;
• input pin capacitance, which sets the load each pin puts on whatever drives it;
• NLDM tables of delay and output transition, indexed by input transition (also called slew) and output load;
• internal-energy tables for power;
• timing checks such as setup and hold for flip-flops, and limits such as max_capacitance on outputs.

The Transistors guide’s cell-library chapter walks through how those tables are measured and read. Design-rule limits (max_transition, max_capacitance, max_fanout) work as rules rather than costs: a net that breaks one gets fixed even if its timing was fine. That is why a net with a very high fanout, one driver feeding thousands of pins, ends up as a tree of buffers. OpenROAD’s repair_design command, for example, inserts buffers specifically to fix max slew, capacitance and fanout violations.¹¹ Huge nets such as reset and scan enable are usually left alone in synthesis, marked ideal (assumed to have no delay), and buffered once placement shows where their loads sit.

Timing-driven synthesis

The tool times every path against the SDC. For a path from one flip-flop to another it computes two numbers:

• Arrival time: the launching flip-flop’s clock-to-output delay plus every cell and wire delay along the path.
• Required time: the next clock edge, minus the capturing flip-flop’s setup time, minus any clock uncertainty.

Slack is required minus arrival. Paths from the block’s inputs and to its outputs use the budgets set by set_input_delay and set_output_delay in place of the missing flip-flop. No clock tree exists yet, so clocks are ideal: every flip-flop is assumed to see the edge at the same instant. In silicon the edge reaches different flip-flops at slightly different times (skew) and wobbles from cycle to cycle (jitter), so set_clock_uncertainty subtracts a margin to cover them.⁸ Exceptions need care:

• A false path removes a path from both optimization and checking.
• A multicycle path with -setup N moves the setup check $N$ cycles out. By default the hold check moves with it, to one cycle before the new setup edge, so you add -hold N−1 to put the hold check back on the original edge.⁸

Optimization tracks two numbers per group of paths: WNS (worst negative slack, the single worst path) and TNS (total negative slack, the sum over every failing endpoint). On paths with negative slack the tool:

• upsizes cells to stronger drive strengths;
• swaps cells to a faster, leakier threshold-voltage flavor;
• restructures logic so late-arriving signals pass through fewer levels;
• duplicates drivers that have many loads, and inserts buffers.

On paths with positive slack it does the reverse, downsizing cells to reclaim area and leakage. Yosys’s ABC integration shows the open-source version of this. A delay target (-D, in picoseconds) adds retiming toward that target, and a constraint file (-constr) adds buffering and up- and down-sizing steps.⁶

Power-oriented transformations

• Clock gating. A flip-flop with an enable is normally built with a feedback multiplexer: when the enable is low it reloads its own output, but it still clocks every cycle. When many flip-flops share one enable, synthesis removes their multiplexers and puts one integrated clock-gating (ICG) cell on their clock instead. The ICG holds the enable in a latch while the clock is active, so the gated clock can’t glitch.¹⁵ Yosys’s clockgate pass groups flip-flops by clock and enable, can pick ICGs from Liberty, skips groups below a minimum size, and can tie a named ICG pin low for later connection to scan enable.⁶ The cost is timing. The ICG sits upstream of the flip-flops it feeds, so its clock edge arrives earlier than theirs, and the enable has to reach the ICG before that earlier edge. Some enables become new critical paths.
• Multibit banking. Multibit flip-flops pack two, four or more bits into one cell that shares its internal clock buffering and presents a smaller clock load. Merging works best on flip-flops that end up close together, so many flows bank at or after placement instead of, or as well as, in synthesis. OpenROAD-flow-scripts, for example, clusters flip-flops during placement.¹⁶¹⁰

Retiming

Retiming moves flip-flops across logic, forward or backward, to minimize the clock period or the number of flip-flops, while keeping the circuit’s cycle-by-cycle behavior at its inputs and outputs.²⁰ A simple case: one pipeline stage takes 1.2 ns and the next 0.6 ns. Moving the register between them earlier, past the last 0.3 ns of the first stage’s logic, gives two 0.9 ns stages that both fit a 1.0 ns clock, with no added latency.

It is powerful on deep, unbalanced pipelines. The price is that it renames, splits and merges flip-flops, which complicates equivalence checking, debugging and any later change that refers to register names. Open flows treat it with caution. OpenROAD-flow-scripts marks its module retiming option experimental, warns that nothing checks the retimed design is equivalent, and notes that its objective ignores the SDC, even the clock period.¹⁰

Hierarchy

Flattening dissolves module boundaries so optimization can reach across them: constants propagate into blocks, logic moves across ports, and outputs nobody reads disappear. Keeping hierarchy preserves block boundaries for hierarchical floorplanning, limits how far a late change spreads, and makes equivalence checking and timing debug easier. A common compromise keeps large blocks and flattens small ones. OpenROAD-flow-scripts exposes exactly that threshold, measured in multiples of a basic NAND2 gate’s area.¹⁰

Physical-aware synthesis

A wire’s delay depends on its length, which isn’t known until placement. Classic synthesis guessed it with a wire-load model, a table in the Liberty file that maps fanout (the number of pins a net drives) to an estimated length, capacitance and resistance.⁷ As processes scaled and wire delay grew, that broke down. A wire-load model guesses a net’s length from its pin count alone, but real nets with the same pin count vary widely, and many turn out longer than the model predicts, so synthesis underestimates their delay.¹²

Physical-aware synthesis replaces the table with distances from a real, if rough, placement: the tool places cells quickly and estimates each net from where its pins sit. Coupling synthesis to placement has its own trap. Each logic change, such as upsizing a cell to fix timing, can disturb the placement and so the wire estimates, and iterating synthesis and placement this way may never converge. Integrated flows therefore update the placement incrementally, keeping it close to the final one throughout.¹²

Equivalence checking

Logical equivalence checking (LEC) works in two steps. First it matches state points (flip-flops, ports and black boxes) between the RTL, the reference, and the netlist, the implementation, mostly by name. That cuts the design into cones: the pure logic feeding each state point. Then it proves each matched pair of cones equivalent. Anything that breaks one-to-one matching needs extra handling: retiming, state re-encoding, and flip-flops merged because they held duplicate or constant values. EQY, for instance, lets you declare a new state encoding in a recode section, or exclude state registers from matching and use a sequential strategy that reasons across several cycles.¹⁸ Commercial synthesis tools can write guidance files describing such changes for the LEC tool.

The simulator is a toy version of the front of the flow: truth table, two-level SOP minimization, then a cover with a generic library (INV, NAND2, NOR2, AND2, OR2, XOR2, XNOR2, AOI21, OAI21) costed by area and a fixed per-cell delay summed along the longest path, which tracks logic depth.

• Use a ^ b ^ c ^ d to see why two-level minimization lost to multi-level synthesis. No two input combinations that give a 1 differ in a single bit, so nothing merges: the SOP is eight 4-literal terms, while a balanced XOR tree is two levels deep.
• Use !((a & b) | c) to watch a complex gate absorb three levels of generic logic.
• Use (a & b) | (a & c) | (b & c) (majority) to compare covers chosen for area and for depth.

Real mappers replace the fixed per-cell delay with NLDM lookups that depend on load and input transition.

The artifacts below follow an open-source flow (Yosys and ABC, with OpenSTA-style timing reports). Commercial tools lay their reports out differently but carry the same information. All numbers are illustrative.

A summary of the whole run condenses those reports. Formats vary by tool; the fields don’t.

Design                    : top
Corner                    : slow (setup)
Clock clk period          : 1.000 ns
WNS (setup)               : -0.022 ns
TNS (setup)               : -0.311 ns
Violating endpoints       : 27
Max transition violations : 3
Combinational cells       : 41,206
Flip-flop bits            : 9,730  (4,914 single-bit, 1,204 x 4-bit multibit)
Clock-gating cells        : 212   (gated flop bits: 88.4%)
Total cell area           : 48,930.6 µm²
Leakage power             : 1.84 mW
Dynamic power (estimate)  : 63.2 mW  (default toggle rate)

Read the slack distribution before chasing the worst path. Here the worst path misses by 22 ps, but 27 endpoints fail for a total of 311 ps, about 12 ps each on average. Thousands of endpoints failing by a few picoseconds usually means the clock target, the uncertainty or a missing exception is wrong. A handful of deep failures points at specific RTL structures. Before the hand-off, time the same netlist and SDC again in a standalone timing tool, and run equivalence checking.

• Exceptions that hide real paths. A wildcard set_false_path, or a set_clock_groups declaration that calls two clocks unrelated when a real synchronous path runs between them, removes that path from optimization and from signoff, the final checks before manufacturing. Lint the SDC with a constraint checker, and review every exception with the RTL owner.
• Multicycle hold mistakes. A setup multicycle without the matching hold adjustment moves the hold check a cycle late. That produces large hold violations that aren’t real, which later stages may then “fix” by inserting delay cells, cells whose only job is to slow a signal down.⁸
• Correlation gaps. Synthesis with wire-load models, or with no wire delay at all, followed by a real placement can shift slack a lot, because a wire-load model guesses each net’s length from its pin count and underestimates many nets.¹² Physical-aware synthesis narrows the gap, but only if the placement it works from stays close to the final one.
• Equivalence checks that give up or fail. Large multipliers and deep arithmetic can make the proof for a single cone so hard that the checker aborts.²³ Retiming, state re-encoding and merged flip-flops break the matching of state points.¹⁸ Keep the synthesis tool’s guidance, use the checker’s settings for arithmetic, and don’t stack aggressive sequential transformations without a plan to verify them.
• Clock-gating side effects. An enable must reach its ICG before the ICG’s clock edge, which comes earlier than the flip-flops’ edge, and the ICG’s test-enable pin must be connected or tied correctly for scan testing.⁶ Many tiny gating groups waste area and complicate clock tree synthesis, the later step that builds the clock wiring; set a minimum group size.
• Boundary optimization and late changes. Flattened blocks, or blocks optimized across their boundaries, lose the meaning of their ports. That makes engineering change orders (small, late edits made directly to the netlist) and partial re-synthesis harder. Decide which blocks to keep before the first full run.¹⁰
• Library hygiene. Flows keep a dont_use list so the mapper avoids cells it shouldn’t pick, such as cells whose pins are hard for the router to reach.¹⁰ Loading the wrong corner or threshold-voltage set skews every result.

NPN classes of 4-input functions

222

Typical 5-input cuts per AIG node

20–30

Node types in an AIG

AND2 + inverted edges

Sources: Mishchenko et al. 2006 for the NPN class count, and Mishchenko et al. 2005 for the typical cut count per node. Both terms are explained below.²⁵²⁶

From two-level to multi-level logic

Early logic minimization targeted two-level form, a sum of products (an OR of AND terms), which maps directly onto programmable logic arrays. Quine–McCluskey solves it exactly in two steps: list every prime implicant (an AND term that can’t be shortened without covering a 0), then choose the smallest set that covers every 1. It starts from the truth table, so its time and memory roughly double with every input added. Espresso (Brayton and colleagues at IBM, later refined at UC Berkeley) avoids expanding the function into its minterms, the individual rows of the truth table. It works heuristically on cubes (product terms) of the ON-set, the don’t-care set and the OFF-set, and its results come very close to minimal and are always free of redundant terms.²²

Two-level form is the wrong target for standard cells. Some common functions, parity among them, need exponentially many product terms.²³ MIS and then SIS moved to multi-level Boolean networks: a graph in which each node holds a small SOP, simplified with Espresso against local don’t-cares (input combinations that can’t occur at that node), while algebraic operations (extraction, kerneling, resubstitution) find logic that several nodes can share.²¹²⁴ The SIS scripts that drove this worked well but were slow and needed hand-tuning.²⁵

And-Inverter Graphs

An AIG is a directed acyclic graph (connections run one way and never loop back) in which every internal node is a two-input AND and any edge may carry an inversion. Primary inputs have no incoming edges. Each register is cut in two: its output acts as an extra input and its input as an extra output, so only the logic between registers remains. Structural hashing during construction keeps a table of every node’s pair of inputs, so no two AND nodes share the same pair and trivially duplicated logic merges for free.²⁵ AIGs came out of formal verification and replaced SOP- and BDD-based representations in ABC’s synthesis flow. ABC now handles designs with millions of nodes that SIS could not finish.²⁴

Rewriting, refactoring and balancing

Two ideas make rewriting work.

• A cut of a node is a small set of nodes that every path from the inputs to that node must pass through. The logic between the cut and the node is then a small function of the cut’s nodes. A cut is 4-feasible if it has at most four nodes, so its function fits in a 16-entry truth table.
• Two functions are in the same NPN class if one becomes the other by negating inputs (N), permuting them (P) or negating the output (N). The 65,536 functions of four inputs fall into just 222 classes.

Rewriting is a greedy local search. It visits nodes in topological order, inputs first. For each node it enumerates the 4-feasible cuts, computes each cut’s function as a 16-bit truth table, looks up its NPN class and tries the precomputed AIG subgraphs stored for that class. For each candidate it counts how many nodes would disappear with the old subgraph and how many the new one needs, reusing nodes that already exist elsewhere in the graph (this is what “DAG-aware” means). It keeps the replacement that saves the most nodes without adding delay.²⁵

Refactoring takes one larger cut per node, collapses the logic inside it and factors it again algebraically. Balancing reduces depth by algebraic tree-height reduction: the chain $((a \cdot b) \cdot c) \cdot d$, three levels deep, becomes $(a \cdot b) \cdot (c \cdot d)$, two levels deep, with the same number of nodes. ABC’s resyn2 script interleaves these. It balances first, then alternates rewriting and refactoring (less area, no more delay) with balancing (less delay, no more area). Each pass is cheap, so many passes add up to a global effect. The authors report it is several orders of magnitude faster than SIS and MVSIS, with comparable or better quality after mapping.²⁵

Cut enumeration and cut-based technology mapping

Classical mappers broke logic into a subject graph of NAND2 gates and inverters, described each library cell as a small pattern graph of the same gates, and covered the subject graph with those patterns using tree covering (as in SIS) or DAG covering.²¹ Because matching compared graph shapes, the result inherited the subject graph’s structure, good or bad. This is called structural bias.²⁶

Cut-based mapping with Boolean matching, from the same Berkeley group, compares functions instead of shapes. It works in five steps:²⁶

1. Enumerate the $k$-feasible cuts (at most $k$ nodes) of every AIG node.
2. Compute each cut’s truth table.
3. Look the truth table up in a hash table of library cell functions. This is Boolean matching; it also settles which cell pin connects to which cut node, and in which polarity.
4. In topological order, compute the best arrival time at each node using the fastest matching cell.
5. In reverse order, from the outputs back, select the cover, then recover area on paths that aren’t critical.

Boolean matching is faster than structural matching and finds more matches, especially for industrial libraries with large, complex gates. Two extensions attack structural bias further:

• Supergates are small precomputed networks of library gates treated as single gates, so larger functions can match.
• Choice nodes store several equivalent structures for the same logic in one AIG, so the mapper can pick among them.²⁶

The number of cuts grows quickly with $k$: the same authors found most test cases have 20 to 30 five-input cuts per node.²⁶ For mapping into FPGA lookup tables, priority cuts keep only a few of the best cuts per node, which makes memory and runtime linear in circuit size while preserving quality; the authors note that similar cut-based methods exist for standard cells. The same paper extends mapping to search combined mapping-and-retiming solutions.²⁷ The FPGA flow built around LUT mapping is the subject of From hardware code to bitstream.

Gate sizing and logical effort

After mapping, which cells to use is fixed but their sizes are not.

Logical effort gives the intuition. The delay of one stage, in units of a basic inverter’s delay, is:¹⁹

• $g$, the logical effort, says how much worse than an inverter the gate is at delivering current for the same input capacitance: 1 for an inverter, 4/3 for NAND2, 5/3 for NOR2.
• $h$, the electrical effort, is the load capacitance divided by the gate’s own input capacitance. A bigger gate gets a smaller $h$ for the same load.
• $p$, the parasitic delay, is the gate’s delay from its own internal capacitance, even with no load.

For example, a NAND2 driving four copies of itself has $h = 4$ and $p = 2$, so $d = (4/3) \cdot 4 + 2 \approx 7.3$ units. A path’s delay is smallest when every stage carries the same effort $gh$.¹⁹ This explains why covers built from NANDs beat covers built from NORs, and why a net with a large fanout wants a tree of buffers that grow gradually in size.

Gain-based (constant-delay) synthesis builds on this. Gain is the $h$ above: the load a stage drives divided by its input capacitance. The tool fixes each gate’s delay during mapping; as placement changes the wire loads, it resizes gates to hold those delays, so what changes is area rather than timing.¹³ Its limits are real:

• It assumes continuous sizing, while real libraries offer a few discrete drive strengths.¹³
• It ignores input slope.¹⁹
• Real wires force another pass of buffering or remapping.¹⁹¹³

Mapping a continuous-sizing solution onto a discrete library can leave a sub-optimal netlist.¹⁴ That is why mapped netlists still go through discrete sizing against the library’s NLDM tables.

Retiming

Leiserson and Saxe model a circuit as a graph. Vertices are blocks of logic, each with a delay; edges are connections, each labeled with the number of registers on it. Retiming gives every vertex $v$ an integer lag $r(v)$, the number of registers moved from its outgoing edges to its incoming edges. An edge from $u$ to $v$ that held $w$ registers then holds $w + r(v) - r(u)$, which must not go negative. Along any path the inner lags cancel, and the inputs and outputs keep a lag of 0, so every input-to-output path keeps its register count and the circuit’s I/O behavior. They give an efficient algorithm for the minimum clock period, show that minimizing the register count is solvable in polynomial time, and characterize optimal retiming as a mixed-integer linear program.²⁰ In a full synthesis flow retiming interacts with mapping, and searching both together covers a larger space than mapping first and retiming afterward.²⁷

Equivalence checking: BDDs vs SAT

Combinational equivalence checking builds a miter: tie the two circuits’ matching inputs together, XOR each pair of matching outputs, and OR all the XORs into one output. That output can only be 1 for an input that makes the circuits disagree, so they are equivalent exactly when it is constant 0.²⁸

One way to prove that uses binary decision diagrams. A reduced ordered BDD represents a function as a decision graph that tests variables in a fixed order and shares identical subgraphs. For a given order each function has exactly one such graph (it is canonical), so once both sides are built, equivalence is a pointer comparison. The catch is size. It depends heavily on the variable order, and for the outputs of an integer multiplier it grows exponentially with word size for every order.²³

Modern checkers lean on SAT solvers instead, which search for an input that sets the miter output to 1 and either find one (a counterexample) or prove none exists. They:

1. Convert the miter to an AIG and structurally hash it.
2. Simulate random and guided input vectors to find internal nodes that look equivalent.
3. Prove or refute those candidates in topological order with SAT, or with BDDs under small resource limits.
4. Merge the nodes proven equal, interleaving light AIG rewriting to shrink the problem before attacking the outputs.

Structural similarity between RTL and netlist is what makes this work: each proven internal equivalence simplifies the next SAT call.²⁸ ABC’s equivalence checker grew out of exactly this need to verify its own synthesis results.²⁴ It also explains the pain points. Retiming and state re-encoding remove the internal correspondences these methods feed on, and deep arithmetic has few internal equivalences to exploit.