One node type

An And-Inverter Graph builds every function from a single node type: the two-input AND. Inversion lives on the edges, drawn as bubbles, never as gates. An OR of two signals becomes an AND of their inversions with an inverted output, by De Morgan's law, and a NAND is one AND node with one inverted edge. One uniform node type makes rewriting simple: the tool matches small AND-inverter patterns and replaces them with cheaper equivalents, without ever reasoning about a dozen gate kinds.

The hand-drawn figure below shows the whole idea on y = ab + ac. Nodes n1 and n2 build the two products with plain edges. Node n3 ANDs their inversions, through the two input bubbles, and the output bubble inverts once more, so n3 plus the output bubble is exactly the OR of the products. Three AND nodes, three bubbles, no other gate kind. No tool drew this picture: it is drawn from the definition so you can read the notation before the measured numbers arrive.

Depth: a chain against a tree

Depth is the longest chain of nodes from an input to the output, counted in gates. It hints at delay: more levels usually mean more gate delays in series, but the library, the load, and ABC's internal rebalancing decide the mapped result. The script below builds the same 8-wide AND twice, once as a chain and once as a balanced tree, then records the longest topological path with ltp and saves both netlists. The assertions pin what the two forms share: seven generic AND cells each.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

read_verilog <<EOV
module chain8(input wire a, input wire b, input wire c, input wire d, input wire e, input wire f, input wire g, input wire h, output wire y);
assign y = ((((((a & b) & c) & d) & e) & f) & g) & h;
endmodule
module tree8(input wire a, input wire b, input wire c, input wire d, input wire e, input wire f, input wire g, input wire h, output wire y);
wire t1 = a & b;
wire t2 = c & d;
wire t3 = e & f;
wire t4 = g & h;
wire u1 = t1 & t2;
wire u2 = t3 & t4;
assign y = u1 & u2;
endmodule
EOV
design -save raw
hierarchy -check -top chain8
proc
opt
tee -o ltp_chain.txt ltp
write_json net_chain.json
select -assert-count 7 t:$and
techmap
tee -o abc_chain.txt abc -liberty course.lib -constr typical.constr -D 1000
tee -o stat_chain.txt stat -liberty course.lib
design -load raw
hierarchy -check -top tree8
proc
opt
tee -o ltp_tree.txt ltp
write_json net_tree.json
select -assert-count 7 t:$and
techmap
tee -o abc_tree.txt abc -liberty course.lib -constr typical.constr -D 1000
tee -o stat_tree.txt stat -liberty course.lib
select -assert-none t:$and t:$or t:$not
check
log PASS: chain and tree use the same gates at different depths

The counts match and the depths do not: identical gates at depth 7 against depth 3. Balancing kept every gate and cut the longest path by more than half, which is the cheapest depth reduction available: the same logic, only parenthesised better. The recorded ltp reports below corroborate the table; ltp counts gates topologically and ignores delays, so on generic netlists it agrees with the recount.

recorded ltp for the chain
5. Executing LTP pass (find longest path).

Longest topological path in chain8 (length=7):
    0: \a
    1: $and$<inlined>:2$1_Y (via $and$<inlined>:2$1)
    2: $and$<inlined>:2$2_Y (via $and$<inlined>:2$2)
    3: $and$<inlined>:2$3_Y (via $and$<inlined>:2$3)
    4: $and$<inlined>:2$4_Y (via $and$<inlined>:2$4)
    5: $and$<inlined>:2$5_Y (via $and$<inlined>:2$5)
    6: $and$<inlined>:2$6_Y (via $and$<inlined>:2$6)
    7: \y (via $and$<inlined>:2$7)

recorded ltp for the tree
13. Executing LTP pass (find longest path).

Longest topological path in tree8 (length=3):
    0: \a
    1: \t1 (via $and$<inlined>:5$8)
    2: \u1 (via $and$<inlined>:9$12)
    3: \y (via $and$<inlined>:11$14)

A real cone: the 4-bit adder

Chains and trees are tidy; an adder is what depth analysis actually looks like. The second script synthesises a 4-bit adder, saves the generic structure, records its longest path, then maps it with ABC and records the area. The assertions pin only robust facts: no generic or internal gate type survives mapping.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

read_verilog <<EOV
module adder4(input wire [3:0] a, input wire [3:0] b, output wire [4:0] s);
assign s = a + b;
endmodule
EOV
synth -top adder4
write_json net_adder.json
tee -o ltp_adder.txt ltp
tee -o abc_adder.txt abc -liberty course.lib -constr typical.constr -D 1000
tee -o stat_adder.txt stat -liberty course.lib
write_json net_adder_map.json
select -assert-none t:$and
select -assert-none t:$or
select -assert-none t:$xor
select -assert-none t:$xnor
select -assert-none t:$mux
select -assert-none t:$not
select -assert-none t:$_AND_
select -assert-none t:$_OR_
select -assert-none t:$_XOR_
select -assert-none t:$_XNOR_
select -assert-none t:$_MUX_
select -assert-none t:$_NOT_
select -assert-none t:$_NAND_
select -assert-none t:$_NOR_
check
log PASS: adder structure recorded before and after mapping

The recorded generic adder holds 17 cells at depth 7, and mapping reaches area 59 with the histogram 1 x AND2, 1 x AOI21, 5 x NAND2, 2 x NOR2, 2 x OAI21, 1 x OR2, 3 x XNOR2, 3 x XOR2. Depth 7 is the carry chain showing up as structure: each carry bit waits for the last, so the longest path runs the length of the adder.

recorded ltp for the adder
4. Executing LTP pass (find longest path).

Longest topological path in adder4 (length=7):
    0: \b [1]
    1: $abc$156$new_n16 (via $abc$156$blif$156$2)
    2: $abc$156$new_n17 (via $abc$156$blif$156$3)
    3: $abc$156$new_n19 (via $abc$156$blif$156$5)
    4: $abc$156$new_n22 (via $abc$156$blif$156$8)
    5: $abc$156$new_n24 (via $abc$156$blif$156$10)
    6: $abc$156$new_n27 (via $abc$156$blif$156$13)
    7: \s [4] (via $abc$156$blif$156$16)

Break it: let mapping rework the structure

Now the setup change that matters: map both the chain and the tree with ABC and compare what mapping reports. Generic depth hints the tree is far faster. But ABC runs its default optimisation script, which rebalances (via dc2/&dch), inside every call, so the chain may not stay a chain. The mapping stage of the first script already recorded both ABC Delay lines alongside both covers.

Read the cover column against the depth column. Both forms record the same cover, 1 x AND2, 2 x NAND2, 1 x NAND3, 1 x NOR3: mapping reworked both structures into one cover, erasing the structural gap the generic depths 7 and 3 show. Both forms record the same mapped delay, 382.31 ps: the generic depth gap left no trace in either cover or delay. Mapping reworks the structure, rebalances slow paths and covers with library cells, so generic depth only hints at delay and never sets the cover. Depth first tells you where to look; the mapped report tells you what the tool did about it.

One balancing note: turning a chain into a tree is the rebalancing in ABC's default script (via dc2/&dch), which already runs inside every abc call above.

Area and the trade-off

Sharing cuts area by reusing nodes across outputs. Duplication cuts depth by giving each output its own cone, which costs area. Balancing is the special case that cuts depth for free, when the structure allows it.

Common mistakes

No rewrite helps on every circuit. Sharing on the critical path adds load to the shared node, and duplication off the critical path adds area for no timing gain: optimise the critical path first and leave the rest small.

Related topics

• Previous: Factoring, collapsing and sharing

• Next: Don't-cares