Factoring pulls, collapsing pushes

Factoring pulls a common literal out of several product terms, turning a flat sum into a nested form with fewer literals. Collapsing does the reverse: it substitutes one expression into another, flattening the logic so that new common factors appear. The two moves are a pair because collapsing alone usually makes things worse; it pays only when a second factoring pass harvests what the flattening exposed.

The running example is the 3-input majority function, which outputs 1 whenever at least two inputs are 1. Its sum of products lists all three input pairs. The factored form pulls a out of the first two pairs and shares the work that remains. Both forms compute the same function on all eight input rows, and the program near the end of this lesson checks every one of them.

What ABC reaches

Hand counts price one cover you chose; ABC prices every cover the library allows. The script below maps the majority function to the full teaching library and records the area ABC actually reaches, with the cell histogram naming the cover it picked. Areas are library units of the fictional teaching library, never silicon figures.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

read_verilog <<EOV
module maj3(input wire a, input wire b, input wire c, output wire y);
assign y = (a & b) | (a & c) | (b & c);
endmodule
EOV
hierarchy -check -top maj3
proc
opt
techmap
tee -o abc_maj.txt abc -liberty course.lib -constr typical.constr -D 1000
tee -o stat_maj.txt stat -liberty course.lib
write_json net_maj.json
select -assert-none t:$and t:$or t:$not
check
log PASS: majority maps to library cells with no generic gates left

hand count, AND2 and OR2 at 3 units each from the course.lib cell table
original ab + ac + bc: 3 AND2 + 2 OR2 (3-input OR from two OR2)
area = 3 x 3 + 2 x 3 = 9 + 6 = 15 area units
factored a(b + c) + bc: 2 AND2 + 2 OR2
area = 2 x 3 + 2 x 3 = 6 + 6 = 12 area units
saving = 15 - 12 = 3 area units = 3 / 15 = 20%

Set the two hand counts side by side: 15 units for the flat form against 12 for the factored form. The hand saving of 3 units is real but partial, because it compares two covers you drew. When the recorded area beats the hand count, cheaper inverting cells (NAND2 and NOR2 at 2 units against AND2 and OR2 at 3) and complex cells did the extra work; when it trails, the structure deserves a second look, not blind trust.

Sharing

Sharing implements one repeated sub-expression once and reuses its output at every user. The second design computes two outputs from one shared OR: y1 = a & (b | c) and y2 = d & (b | c). The RTL writes the (b | c) term twice, so after elaboration the recorded netlist holds two identical OR cells. The opt stage merges them, and the assertions pin the shared result: one OR cell feeding two AND cells.

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

read_verilog <<EOV
module share2(input wire a, input wire b, input wire c, input wire d, output wire y1, output wire y2);
assign y1 = a & (b | c);
assign y2 = d & (b | c);
endmodule
EOV
hierarchy -check -top share2
proc
opt
check
write_json net_share_opt.json
select -assert-count 1 t:$or
select -assert-count 2 t:$and
techmap
tee -o abc_share.txt abc -liberty course.lib -constr typical.constr -D 1000
tee -o stat_share.txt stat -liberty course.lib
write_json net_share.json
select -assert-none t:$and t:$or t:$not
check
log PASS: one shared OR feeds both ANDs through mapping

hand count for the shared pair, same cell prices
duplicated, sharing forbidden: 2 OR2 + 2 AND2 = 2 x 3 + 2 x 3 = 12 area units
shared, one OR built once: 1 OR2 + 2 AND2 = 3 + 6 = 9 area units
saving = 12 - 9 = 3 area units, one OR2 not built

The recorded generic netlist after optimisation holds 1 OR cell and 2 AND cells: the duplicate OR merged exactly as the hand count assumed. Mapping then reaches area 8 with the histogram 2 x INV, 3 x NOR2. The recorded mapped netlist holds no OR2 cell at all: ABC reworked the cone during mapping, so read its cover on its own terms rather than as your factored form. Either way, the sharing decision belongs to the generic stage, where identical inputs are easy to match, and mapping only prices what sharing left behind.

Hierarchy hides sharing

The sharing demo above hides a step: both copies of (b | c) sit in one module, so elaboration already exposes them. Real RTL often parks one copy behind a submodule boundary, where no generic pass merges through. The script below does that on purpose, records the hierarchical netlist, then dissolves the boundary with flatten and optimises again. That is sharing across hierarchy, not Boolean collapsing: collapsing means substituting one expression into another so new factors appear, while here the factor already exists twice and only the boundary stops the merge.

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 sh(input wire a, input wire b, input wire c, output wire y1);
assign y1 = a & (b | c);
endmodule
module collapse(input wire a, input wire b, input wire c, input wire d, output wire y1, output wire y2);
sh s (.a(a), .b(b), .c(c), .y1(y1));
assign y2 = d & (b | c);
endmodule
EOV
hierarchy -check -top collapse
proc
design -save pre
tee -o stat_col_hier.txt stat
write_json net_col_hier.json
design -load pre
flatten
delete t:$scopeinfo
opt
check
tee -o stat_col_flat.txt stat
write_json net_col_flat.json
select -assert-count 1 t:$or
select -assert-count 2 t:$and
techmap
tee -o abc_col.txt abc -liberty course.lib -constr typical.constr -D 1000
tee -o stat_col.txt stat -liberty course.lib
write_json net_col.json
select -assert-none t:$and t:$or t:$not
check
log PASS: flattening exposes the shared factor for one OR and two ANDs

Read the middle row as the payoff: dissolving the boundary exposes the duplicate the hierarchy hid, and the merge pass harvests it, leaving 2 AND cells and 1 OR cell where the hierarchy kept 2 ANDs and 2 ORs in separate modules. Mapping then covers the shared structure once, and the recorded cover is the receipt.

Proof in Python

The program below checks all 8 input rows for equality. It also counts literals from the expression trees and requires the factored form to be smaller.

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
38
39
40
41
42
43
44
45

import sys

def f_orig(a, b, c):
    return (a and b) or (a and c) or (b and c)

def f_fact(a, b, c):
    return (a and (b or c)) or (b and c)

def count_lits(node):
    if isinstance(node, str):
        return 1
    return sum(count_lits(k) for k in node[1:])

ORIG = ("or", ("and", "a", "b"), ("and", "a", "c"), ("and", "b", "c"))
FACT = ("or", ("and", "a", ("or", "b", "c")), ("and", "b", "c"))

rows = 0
diff = 0
for a in (0, 1):
    for b in (0, 1):
        for c in (0, 1):
            rows += 1
            if bool(f_orig(a, b, c)) != bool(f_fact(a, b, c)):
                diff += 1

no = count_lits(ORIG)
nf = count_lits(FACT)

if rows != 8:
    print("FAIL: walked " + str(rows) + " rows, want 8")
    sys.exit(1)
if diff != 0:
    print("FAIL: " + str(diff) + " rows differ")
    sys.exit(1)
if no != 6:
    print("FAIL: original counts " + str(no) + " literals, want 6")
    sys.exit(1)
if nf != 5:
    print("FAIL: factored counts " + str(nf) + " literals, want 5")
    sys.exit(1)
if not nf < no:
    print("FAIL: factored form is not smaller")
    sys.exit(1)

print("PASS: factored form agrees on 8 of 8 rows with 5 literals against 6")

Break it: take away the library

Now change the setup the other way: keep the majority function but map it against nand_only.lib, which stocks only inverters, buffers and 2-input NANDs. Every AND and OR in the design must now be built out of NANDs, so the cover needs more cells. The script maps the identical design and records the restricted area.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

read_verilog <<EOV
module maj3(input wire a, input wire b, input wire c, output wire y);
assign y = (a & b) | (a & c) | (b & c);
endmodule
EOV
hierarchy -check -top maj3
proc
opt
techmap
tee -o abc_nand.txt abc -liberty nand_only.lib -constr typical.constr -D 1000
tee -o stat_nand.txt stat -liberty nand_only.lib
write_json net_nand.json
select -assert-none t:$and t:$or t:$not
select -assert-min 1 t:NAND2
check
log PASS: majority also maps to NAND-only cells at higher cost

The restricted cover reaches area 10 against 7 on the full library. Read the two recorded histograms against each other: the full-library cover is 2 x NAND2, 1 x OAI21, while the restricted cover rebuilds the same function as 2 x INV, 4 x NAND2. Without the complex cells ABC pays extra NANDs and inverters, and the area gap between the two covers is that tax.

Common mistakes

Fewer literals need not mean less area or delay. Factoring can add levels, and collapsing can duplicate terms before anything improves. Price the factored form by hand, read the recorded mapped area, and believe the report when the two disagree: the report priced covers you never drew.

Related topics

• Previous: Redundancy removal

• Next: AIGs, depth and area