ABC mapping worse in recent version

Dear abc developers,

I am referring to a discussion from yosys, which uses abc for technology mapping. The discussion can be found here: https://github.com/YosysHQ/yosys/discussions/3834

So the problem is the following. For some reason abcs mapping became different/worse in some version bump. I understand that the process itself is not necessarily deterministic, but the results are not optimal. We were able to reproduce the same results by using abc directly, not only with yosys.

Basically we are trying to decompose a LUT into "basic" boolean gates for a given genlib.

Genlib:

#basic_hal_i4
GATE HAL_VDD 0.0000 O=CONST1;
GATE HAL_GND 0.0000 O=CONST0;
GATE HAL_XOR3 3.0000 O=((A * ((B * C) + ((! B) * (! C)))) + ((! A) * ((B + C) * ((! B) + (! C)))));
PIN A NONINV 1 999 1 0 1 0
PIN B NONINV 1 999 1 0 1 0
PIN C NONINV 1 999 1 0 1 0
GATE HAL_MUX3 1.5000 O=((A + (! S1)) * ((C * (! S2)) + (S1 + (B * S2))));
PIN A NONINV 1 999 1 0 1 0
PIN B NONINV 1 999 1 0 1 0
PIN C NONINV 1 999 1 0 1 0
PIN S1 NONINV 1 999 1 0 1 0
PIN S2 NONINV 1 999 1 0 1 0
GATE HAL_BUF 1.0000 O=A;
PIN A NONINV 1 999 1 0 1 0
GATE HAL_XOR4 4.0000 O=((B * ((A + ((C * D) + ((! C) * (! D)))) * ((! A) + ((C + D) * ((! C) + (! D)))))) + ((! B) * ((A * ((C * D) + ((! C) * (! D)))) + ((! A) * ((C + D) * ((! C) + (! D)))))));
PIN A NONINV 1 999 1 0 1 0
PIN B NONINV 1 999 1 0 1 0
PIN C NONINV 1 999 1 0 1 0
PIN D NONINV 1 999 1 0 1 0
GATE HAL_MUX4 1.5000 O=(((D * (! S2)) + (S1 + (C * S2))) * ((B * (! S2)) + ((! S1) + (A * S2))));
PIN A NONINV 1 999 1 0 1 0
PIN B NONINV 1 999 1 0 1 0
PIN C NONINV 1 999 1 0 1 0
PIN D NONINV 1 999 1 0 1 0
PIN S1 NONINV 1 999 1 0 1 0
PIN S2 NONINV 1 999 1 0 1 0
GATE HAL_MUX 1.5000 O=((B + S) * (A + (! S)));
PIN A NONINV 1 999 1 0 1 0
PIN B NONINV 1 999 1 0 1 0
PIN S NONINV 1 999 1 0 1 0
GATE HAL_XOR2 2.0000 O=((A + B) * ((! A) + (! B)));
PIN A NONINV 1 999 1 0 1 0
PIN B NONINV 1 999 1 0 1 0
GATE HAL_OR2 2.0000 O=(A + B);
PIN A NONINV 1 999 1 0 1 0
PIN B NONINV 1 999 1 0 1 0
GATE HAL_AND2 2.0000 O=(A * B);
PIN A NONINV 1 999 1 0 1 0
PIN B NONINV 1 999 1 0 1 0
GATE HAL_INV 1.0000 O=(! A);
PIN A INV 1 999 1 0 1 0

module top (I5, I1, I2, I4, I3, I0, O);
input I5;
input I1;
input I2;
input I4;
input I3;
input I0;
output O;

assign O = ((I5 & ((I3 | ((I0 & (! I4)) | ((! I0) & I4))) & ((! I3) | ((I0 | (! I4)) & ((! I0) | I4))))) | ((I3 | ((I0 & (! I2)) | ((! I0) & I2))) & ((! I5) & ((I1 & I4) | ((! I3) | ((! I1) & (! I4)))))));

endmodule

The options used are the following:

7.1.1. Executing ABC.
Running ABC command: "<yosys-exe-dir>/yosys-abc" -s -f <abc-temp-dir>/abc.script 2>&1
ABC: ABC command line: "source <abc-temp-dir>/abc.script".
ABC: 
ABC: + read_blif <abc-temp-dir>/input.blif 
ABC: + read_library /Users/eve/Desktop/new_gate_library.genlib 
ABC: Entered genlib library with 12 gates from file "/Users/eve/Desktop/new_gate_library.genlib".
ABC: + strash 
ABC: + &get -n 
ABC: + &fraig -x 
ABC: + &put 
ABC: + scorr 
ABC: Warning: The network is combinational (run "fraig" or "fraig_sweep").
ABC: + dc2 
ABC: + dretime 
ABC: + strash 
ABC: + &get -n 
ABC: + &dch -f 
ABC: + &nf 
ABC: + &put 
ABC: + write_blif <abc-temp-dir>/output.blif

The output differs depending on the commit used:

7.1.2. Re-integrating ABC results.
ABC RESULTS:           HAL_INV cells:        1
ABC RESULTS:          HAL_XOR2 cells:        2
ABC RESULTS:          HAL_XOR3 cells:        1
ABC RESULTS:          HAL_MUX3 cells:        1
ABC RESULTS:        internal signals:       11
ABC RESULTS:           input signals:        6
ABC RESULTS:          output signals:        1
Removing temp directory.

7.1.2. Re-integrating ABC results.
ABC RESULTS:           HAL_MUX cells:        1
ABC RESULTS:          HAL_XOR2 cells:        3
ABC RESULTS:           HAL_INV cells:        3
ABC RESULTS:          HAL_AND2 cells:        4
ABC RESULTS:           HAL_OR2 cells:        2
ABC RESULTS:        internal signals:       11
ABC RESULTS:           input signals:        6
ABC RESULTS:          output signals:        1
Removing temp directory.

ABC maps the LUT to 13 cells vs. 5. The 5 cells are much "cheaper" area wise.

I am wondering if there are new optimisations that need to be enabled or anything else that could explain the different behaviour. The mapping is not really optimal and the circuit is not complex.

Any help is appreciated! Thanks :)

I reproduced your result successfully, and I tried on ABC with following standalone script:

read_verilog issue229.v
read_library issue229.genlib
strash
&get -n
&fraig -x
&put
scorr
dc2
dretime
strash
&get -n
&dch -f
&nf
&put
write_blif output.blif

(issue229.v and issue229.genlib are equal to what you have mentioned)

Took @nakengelhardt advice in YosysHQ/yosys#3834 , here is what git bisect shows:

# bad: [a603186d8ecffcb195637994b3b8d560647286d9] "Fixing usage message of &ps."
# good: [e9b487666d7cab3cc8a02faa34160d2ed4cb6178] Suggested changes to collect and pass timing information (unused variable).
git bisect start 'HEAD' 'e9b4876'
# good: [99b33e5dbf5508833a2f4c19d234435cdac3738e] Improvements to command 'twoexact'.
git bisect good 99b33e5dbf5508833a2f4c19d234435cdac3738e
# bad: [9f4ab5a2c1612400b1c9ebf95573a7d8bdf8b5db] Bug fix in SAT sweeping.
git bisect bad 9f4ab5a2c1612400b1c9ebf95573a7d8bdf8b5db
# good: [70a07869c65f8ca7f8d4f083815d86dcd3681add] Updating interface of scorr.
git bisect good 70a07869c65f8ca7f8d4f083815d86dcd3681add
# bad: [91aaff257591d7c625150d955d4e7fcfe8320d90] More compiler warnings.
git bisect bad 91aaff257591d7c625150d955d4e7fcfe8320d90
# good: [aa4cada26820387ecf5ec42bdb58fbe765c16705] Experiments with multiplier generation (linker problem).
git bisect good aa4cada26820387ecf5ec42bdb58fbe765c16705
# good: [581c58b9c48772b549dc921fd7c854484470ed8c] Experiment with choice computation.
git bisect good 581c58b9c48772b549dc921fd7c854484470ed8c
# bad: [b57b54649437636e2734233417272dc6f24e6964] Compiler warnings.
git bisect bad b57b54649437636e2734233417272dc6f24e6964
# bad: [0d0063f7de69388c80e4a6adc4bfc27287a3e19a] Experiment with cost functions.
git bisect bad 0d0063f7de69388c80e4a6adc4bfc27287a3e19a
# first bad commit: [0d0063f7de69388c80e4a6adc4bfc27287a3e19a] Experiment with cost functions.

So the commit 0d0063f7de69388c80e4a6adc4bfc27287a3e19a caused the issue, after this commit the output blif changes to the one with more gates. I took a brief look of the changes in Gitlens, it seems like the only change is on the minsaved parameter.

Blif before this commit:

# Benchmark "top" written by ABC on Sat Aug 12 12:40:18 2023
.model top
.inputs I5 I1 I2 I4 I3 I0
.outputs O
.gate HAL_INV  A=I1 O=new_n8_
.gate HAL_XOR2 A=new_n8_ B=I4 O=new_n9_
.gate HAL_XOR2 A=I2 B=I0 O=new_n10_
.gate HAL_XOR3 A=I4 B=I3 C=I0 O=new_n11_
.gate HAL_MUX3 A=new_n11_ B=new_n9_ C=new_n10_ S1=I5 S2=I3 O=O
.end

Blif after this commit:

# Benchmark "top" written by ABC on Sat Aug 12 10:21:27 2023
.model top
.inputs I5 I1 I2 I4 I3 I0
.outputs O
.gate HAL_INV  A=I5 O=new_n8_
.gate HAL_INV  A=I1 O=new_n9_
.gate HAL_XOR2 A=I4 B=I0 O=new_n10_
.gate HAL_OR2  A=I3 B=new_n10_ O=new_n11_
.gate HAL_AND2 A=I3 B=new_n10_ O=new_n12_
.gate HAL_INV  A=new_n12_ O=new_n13_
.gate HAL_AND2 A=I5 B=new_n11_ O=new_n14_
.gate HAL_AND2 A=new_n13_ B=new_n14_ O=new_n15_
.gate HAL_XOR2 A=new_n9_ B=I4 O=new_n16_
.gate HAL_XOR2 A=I2 B=I0 O=new_n17_
.gate HAL_MUX  A=new_n16_ B=new_n17_ S=I3 O=new_n18_
.gate HAL_AND2 A=new_n8_ B=new_n18_ O=new_n19_
.gate HAL_OR2  A=new_n15_ B=new_n19_ O=O
.end

Note: I have also noticed that there's another issue after this commit in YosysHQ/yosys#3827.

berkeley-abc / abc

ABC mapping worse in recent version #229