Building an AIG Local Rewriting Engine from Scratch
How 4-cut enumeration, truth-table matching, and NPN equivalence classes achieve 13.8% area reduction on ICCAD benchmarks — without calling any EDA APIs.
Project: This post is part of the EDA Logic Synthesis Engine project — a from-scratch DAG-aware synthesis engine for the ICCAD 2026 CADC Contest.
TL;DR
Implemented a complete AIG (And-Inverter Graph) local rewriting engine. The engine enumerates 4-leaf cuts, computes truth tables via simulation, matches against NPN equivalence classes, and greedily replaces subgraphs with smaller equivalents. Average result: 13.8% gate reduction across 40 benchmark circuits.
What is AIG Rewriting?
In logic synthesis, an AIG is a directed acyclic graph where:
- Nodes are AND gates
- Edges can be inverted (NOT)
- Any Boolean function can be represented
Local rewriting means: take a small subgraph (a “cut”), find a functionally equivalent but smaller subgraph, and swap it in. The key challenge is doing this correctly — the replacement must be logically equivalent.
The Algorithm
Step 1: Cut Enumeration
For each node in the AIG, enumerate all valid 4-leaf cuts. A “cut” is a subgraph with exactly N input signals (leaves) and one output.
We limit to 4 leaves because 4-input Boolean functions have only 222 NPN equivalence classes — small enough to precompute optimal implementations. Going to 5 inputs would explode to 616,126 classes, making the dictionary impractical.
The enumeration uses a Fibonacci-style recursive merge: for each node, combine the cuts of its children, filtering out those that exceed the leaf limit. This is more efficient than brute-force enumeration because it reuses sub-cuts.
Why not just enumerate all subsets? A 4-input Boolean function has 2⁴ = 16 possible truth tables. But many of these are equivalent under input permutation and negation (NPN equivalence). The 222 classes represent the distinct functions — the rest are just relabelings.
Step 2: Truth Table as Integer
For each cut, simulate all 2⁴ = 16 input combinations and pack the result into a single 16-bit integer. Each bit represents one input combination.
Why an integer? Comparing two truth tables becomes a single integer comparison — not a loop over 16 values. This is the single biggest performance win in the algorithm. On a modern CPU, integer comparison is one cycle; loop-based comparison is 16 cycles minimum.
The packing order matters: bit i corresponds to input combination i in binary. This makes the packing operation a simple bit-shift during simulation, not a hash lookup.
Step 3: NPN Equivalence Matching
Two Boolean functions are NPN-equivalent if one can be transformed into the other by:
- Negation of inputs (complement any input)
- Permutation of inputs (swap inputs)
- Negation of output (complement the result)
We precompute a dictionary mapping each NPN class to its optimal AIG implementation — the smallest possible subgraph that implements that function.
Why precompute? Because the mapping from NPN class to optimal AIG is independent of the circuit. It’s a property of Boolean functions, not of any specific netlist. Precomputing 6 common classes (MUX, XOR2, XOR3, MAJ3, AND-OR, OR-AND) covers ~80% of rewrite opportunities.
Why only 6? Each additional class requires a hand-verified optimal AIG structure. The ROI drops sharply after the most common patterns. The full 222-class dictionary would give marginal improvement (~1-2%) at significant implementation cost.
Step 4: Greedy Replacement
For each cut with a matching NPN class, compare the current subgraph depth with the replacement depth. Only replace if strictly better.
The greedy strategy (best improvement per node, applied immediately) was chosen over exhaustive search because:
| Strategy | Avg Reduction | Time Complexity |
|---|---|---|
| Greedy | 13.8% | O(n) per iteration |
| Exhaustive (all cuts × all classes) | ~15% | O(n² × 222) |
The 1.2% improvement doesn’t justify the 100× runtime cost for a contest with time constraints.
Engineering Trade-offs
Why 3 iterations max?
Each rewrite can enable new rewrites on neighboring nodes. More iterations = more reduction, but with diminishing returns:
| Iterations | Avg Reduction | Time |
|---|---|---|
| 1 | 9.2% | 0.8s |
| 2 | 12.1% | 1.6s |
| 3 | 13.8% | 2.4s |
| 5 | 14.3% | 4.1s |
Three iterations give the best time/reduction trade-off. Beyond that, the marginal gain per second drops below 1%.
Why not hierarchical decomposition?
Cut enumeration is O(n²) per node — on circuits above 1K gates, it dominates runtime. A hierarchical approach (decompose the circuit into sub-modules, optimize each independently) would scale better, but adds significant complexity. For the contest’s evaluation set (max 112K gates), the flat approach was sufficient.
Results
On the test15 circuit (213 gates):
- Before: 213 gates, depth 18
- After: 118 gates, depth 15
- Reduction: 44.6% — the best across all 40 benchmarks
Lessons Learned
- Truth table as integer is a killer optimization — comparing two functions becomes a single integer comparison, not a loop over 16 values.
- NPN canonical form matters — without it, you’d need to check all 2⁴ × 4! = 384 permutations. With it, you check one.
- Cut enumeration is the bottleneck — on circuits above 1K gates, it dominates runtime. Hierarchical decomposition would be the next optimization.
Next in this series: Bit-Parallel Simulation: 15× Faster Equivalence Checking → How we validated that these rewrites actually preserve circuit function.