And-Inverter Graph Rewriting

The idea

An and-inverter graph builds every function from one kind of node, a two-input AND, with inversion marked on the edges. The uniformity makes it compact and cheap to manipulate. Structural hashing merges any two AND nodes with the same inputs as the graph is built, so identical logic is never stored twice.

Rewriting (Mishchenko, Chatterjee and Brayton, 2006) walks the graph. At each node it enumerates small cuts: sets of up to four nodes that separate this node from the rest of the logic. Each cut implements some four-input function. Up to permuting and negating the inputs and the output, there are only 222 distinct four-input functions, and an optimal and-inverter structure for each one is computed once and stored. If the stored structure, after sharing whatever logic already exists in the graph, uses fewer nodes than the logic it would replace, the swap is made. Repeated passes of rewriting, together with balancing (which reduces depth) and refactoring (which collapses larger cuts and factors them again), make up the standard optimization scripts.

Watch it work: one cut, swapped for a smaller structure

f = ab + ac as an and-inverter graph of three nodes. The walkthrough picks a cut, computes the function it implements, looks up the stored optimal structure for that function, and swaps it in when it is smaller.

The fine print

Rewriting is local and structural: the result depends on the structure it starts from, and it cannot find an optimization that needs a wider view than a four-input cut. Keeping several equivalent structures ("structural choices") and letting the mapper choose among them softens this. Node count is a proxy for area; delay is handled by balancing and by the mapper that follows.

Where you meet it today

ABC implements it, and the OpenROAD flow's own ABC script (abc_speed.script) alternates &st (structural hashing), &syn2 (rewriting and balancing), &dch (structural choices) and &nf (mapping). Every design synthesized in the open flow, including the runs behind this site's drills, passed through it.