Bubbles move

An inverter at a gate input is a bubble: a small circle marking a complemented input. De Morgan's laws push bubbles through gates — NOT (a AND b) is (NOT a) OR (NOT b), and the dual for OR — so a bubble slides between a gate's output and its inputs while the function stays the same. The mapper slides bubbles until they merge: an inverter over an AND becomes a NAND2, a leftover pair folds into an AOI or OAI cell, and whatever cannot merge stays as a discrete inverter the cover must place.

Take y = NOT ((NOT a) AND (NOT b)): two inverters feeding a NAND2. Push both bubbles through and the function is a plain OR of a and b. The calc block prices that move from library data (INV 1, NAND2 2, OR2 3): 4 before against 3 after. The saving of 1 unit is not the point; the mechanism is: bubbles travel until they find the cheapest gate to live in.

y = NOT ((NOT a) AND (NOT b)); areas in teaching-library area units
before: INV (1) + INV (1) + NAND2 (2) = 4
De Morgan: y = a OR b
after: OR2 (3) = 3
saving = 4 - 3 = 1 area unit

Polarity is a choice

For each output the mapper can build the function as written or its complement plus an inverter, keeping whichever is cheaper — arithmetic, not style. The table shows both directions on XOR (XOR2 and XNOR2 at 5 units each, inverter at 1).

Both rows resolve the same way: the direct cell wins by exactly the inverter it avoids — until a ban removes the direct cell, and the complement route becomes the only cover. The recorded covers below follow the same arithmetic on f: the free run absorbs the output inversion inside its single AOI21, while the double-banned run complements input c with a discrete INV feeding the AND2 beside the NAND2.

Banning cells, recorded

Libraries mark some cells dont_use, and the mapper must skip them even when they match: uncharacterised at this corner, kept only for legacy netlists, or unroutable in this block. Every ban shrinks the choice set, so re-read area and delay after each change.

The script maps f = NOT ((a AND b) OR c) three times against course.lib: free, then AOI21 and OAI21 banned, then NOR2 banned on top. All three runs use typical.constr with a very loose 100000 ps target, so every ABC report carries its Gates, Area, and Delay line. The assertions prove no generic gate survives any run and no banned cell survives its ban (1 AOI21 cell free; 0 AOI21 or OAI21 cells and 0 banned-kind cells after the bans).

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

read_verilog <<EOV
module cover(input a, b, c, output y);
assign y = ~((a & b) | c);
endmodule
EOV
synth -top cover
design -save generic
tee -o abc_base.txt abc -liberty course.lib -constr typical.constr -D 100000
tee -o stat_base.txt stat -liberty course.lib
write_json net_base.json
select -assert-none t:$and t:$or t:$xor t:$xnor t:$mux t:$not
select -assert-none t:$_AND_ t:$_OR_ t:$_XOR_ t:$_XNOR_ t:$_MUX_ t:$_NOT_ t:$_NAND_ t:$_NOR_
check
design -load generic
tee -o abc_ban1.txt abc -liberty course.lib -dont_use AOI21 -dont_use OAI21 -constr typical.constr -D 100000
tee -o stat_ban1.txt stat -liberty course.lib
write_json net_ban1.json
select -assert-none t:$and t:$or t:$xor t:$xnor t:$mux t:$not
select -assert-none t:$_AND_ t:$_OR_ t:$_XOR_ t:$_XNOR_ t:$_MUX_ t:$_NOT_ t:$_NAND_ t:$_NOR_
select -assert-none t:AOI21 t:OAI21
check
design -load generic
tee -o abc_ban2.txt abc -liberty course.lib -dont_use AOI21 -dont_use OAI21 -dont_use NOR2 -constr typical.constr -D 100000
tee -o stat_ban2.txt stat -liberty course.lib
write_json net_ban2.json
select -assert-none t:$and t:$or t:$xor t:$xnor t:$mux t:$not
select -assert-none t:$_AND_ t:$_OR_ t:$_XOR_ t:$_XNOR_ t:$_MUX_ t:$_NOT_ t:$_NAND_ t:$_NOR_
select -assert-none t:AOI21 t:OAI21 t:NOR2
check
log PASS: one function maps cleanly with two stacked bans

Read the table as a staircase built by subtraction. The free run holds 1 cell at area 3. The first ban forces it off the complex cells onto AND2 x1, NOR2 x1 at area 5, and the second ban takes the NOR2 fallback away as well for AND2 x1, INV x1, NAND2 x1 at area 6. The whole staircase is the price of the ban list.

Break it: ban the direct XOR cell

The polarity table says the complement route wins when the direct cell is banned. This break-it records exactly that on a one-gate function, y = a XOR b, mapped twice against course.lib: free, then with XOR2 banned. Both runs use typical.constr with the same very loose 100000 ps target. The assertions prove no generic gate survives either run, the free run really uses an XOR2, and none survives the ban.

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

read_verilog <<EOV
module xorf(input a, b, output y);
assign y = a ^ b;
endmodule
EOV
synth -top xorf
design -save generic
tee -o abc_xfree.txt abc -liberty course.lib -constr typical.constr -D 100000
tee -o stat_xfree.txt stat -liberty course.lib
write_json net_xfree.json
select -assert-none t:$and t:$or t:$xor t:$xnor t:$mux t:$not
select -assert-none t:$_AND_ t:$_OR_ t:$_XOR_ t:$_XNOR_ t:$_MUX_ t:$_NOT_ t:$_NAND_ t:$_NOR_
select -assert-min 1 t:XOR2
check
design -load generic
tee -o abc_xxor.txt abc -liberty course.lib -dont_use XOR2 -constr typical.constr -D 100000
tee -o stat_xxor.txt stat -liberty course.lib
write_json net_xxor.json
select -assert-none t:$and t:$or t:$xor t:$xnor t:$mux t:$not
select -assert-none t:$_AND_ t:$_OR_ t:$_XOR_ t:$_XNOR_ t:$_MUX_ t:$_NOT_ t:$_NAND_ t:$_NOR_
select -assert-none t:XOR2
check
log PASS: xor maps free and without its direct cell

The free run holds XOR2 x1 at area 5: the direct cell, exactly as the table prices it. The banned run holds INV x1, XNOR2 x1 at area 6, with 0 XOR2 cells left — the complement route at the priced 6. The ban never strands the cone: XNOR2 plus INV build any XOR, so a complete library always leaves a cover and only the price moves. Arrival slips from 194 ps to 248 ps on two gates of logic, so recheck delay after every ban-list edit, not just area.

Common mistakes

Related topics

• Area Against Delay

• Mapping in Yosys

• See also: Structuring and Buffering