N to 1 matching is does not appear to be working

[d-m-bailey]

netgen 1.5.233

The layout contains prefixed and unprefixed cells that should match to the same unprefixed name in gl verilog.

eg. BO_sky130_fd_sc_hd__clkbuf_8 and sky130_fd_sc_hd__clkbuf_8 should both match sky130_fd_sc_hd__clkbuf_8 in the spice library.

The setup file contains

            equate classes "-circuit2 sky130_fd_sc_hd__clkbuf_8" "-circuit1 BO_sky130_fd_sc_hd__clkbuf_8"
            equate classes "-circuit2 sky130_fd_sc_hd__clkbuf_8" "-circuit1 sky130_fd_sc_hd__clkbuf_8"

because "netlist with the N names should always be the second netlist". However, only the matching cell comparison is preformed and BO_sky130_fd_sc_hdclkbuf_8 is flattened during prematch, which causes sky130_fd_sc_hdclkbuf_8 to be flattened also.

1 to 1 matching with prefixes using equate classes works as expected. Both of the following are ok.

            equate classes "-circuit2 precharge_0" "-circuit1 BO_sky130_sram_2kbyte_1rw1r_32x512_8_precharge_0"
            equate classes "-circuit2 sky130_fd_bd_sram__openram_write_driver" "-circuit1 BO_sky130_fd_bd_sram__openram_write_driver"

Contents of circuit 1:  Circuit: 'BO_sky130_sram_2kbyte_1rw1r_32x512_8_precharge_0'
Circuit BO_sky130_sram_2kbyte_1rw1r_32x512_8_precharge_0 contains 3 device instances.
  Class: sky130_fd_pr__pfet_01v8 instances:   3
Circuit contains 4 nets.
Contents of circuit 2:  Circuit: 'precharge_0'
Circuit precharge_0 contains 3 device instances.
  Class: sky130_fd_pr__pfet_01v8 instances:   3
Circuit contains 4 nets.

Contents of circuit 1:  Circuit: 'BO_sky130_fd_bd_sram__openram_write_driver'
Circuit BO_sky130_fd_bd_sram__openram_write_driver contains 16 device instances.
  Class: sky130_fd_pr__nfet_01v8 instances:   9
  Class: sky130_fd_pr__pfet_01v8 instances:   7
Circuit contains 15 nets.
Contents of circuit 2:  Circuit: 'sky130_fd_bd_sram__openram_write_driver'
Circuit sky130_fd_bd_sram__openram_write_driver contains 16 device instances.
  Class: sky130_fd_pr__nfet_01v8 instances:   9
  Class: sky130_fd_pr__pfet_01v8 instances:   7
Circuit contains 13 nets.

However, N to 1 matching yields

Subcircuit summary:
Circuit 1: sky130_fd_sc_hd__clkbuf_8       |Circuit 2: sky130_fd_sc_hd__clkbuf_8
-------------------------------------------|-------------------------------------------
sky130_fd_pr__pfet_01v8_hvt (10->2)        |sky130_fd_pr__pfet_01v8_hvt (10->2)
sky130_fd_pr__nfet_01v8 (10->2)            |sky130_fd_pr__nfet_01v8 (10->2)
Number of devices: 4                       |Number of devices: 4
Number of nets: 7                          |Number of nets: 7
---------------------------------------------------------------------------------------
Netlists match uniquely.

and then

Flattening unmatched subcell BO_sky130_fd_sc_hd__clkbuf_8 in circuit BO_mgmt_core (0)(40 instances)
...
Flattening instances of sky130_fd_sc_hd__clkbuf_8 in cell mgmt_core (1) makes a better match
...
Making another compare attempt.

To duplicate, see https://github.com/efabless/caravel/issues/159 Warning: not a minimal case.

Note: This is not a critical problem. It causes longer LVS runs, but they still pass.

[d-m-bailey]

Here's the code from base/netcmp.c

int EquivalenceClasses(char *name1, int file1, char *name2, int file2)
{
   char *class1, *class2;
   struct Correspond *newc;
   struct nlist *tp, *tp2, *tpx;
   unsigned char need_new_seed = 0;
   int reverse = 0;

   if (file1 != -1 && file2 != -1) {

      tp = LookupClassEquivalent(name1, file1, file2);
      if (tp && (*matchfunc)(tp->name, name2))
         return 1;      /* Already equivalent */      ===> 1 <===

      tp = LookupCellFile(name1, file1);
      tp2 = LookupCellFile(name2, file2);
      if (tp->classhash == tp2->classhash)
         return 1;      /* Already equivalent */

      /* Where cells with duplicate cell names have been checked and    */
      /* found to be equivalent, the original keeps the hash value.     */

      if (tp->flags & CELL_DUPLICATE)
         reverse = 1;

      /* Do a cross-check for each name in the other netlist.  If       */
      /* conflicting names exist, then alter the classhash to make it   */
      /* unique.  In the case of duplicate cells, don't do this.        */

      if (!(tp->flags & CELL_DUPLICATE) && !(tp2->flags & CELL_DUPLICATE)) {    ===> 2 <===
         tpx = LookupCellFile(name1, file2);
         if (tpx != NULL) need_new_seed = 1;
         tpx = LookupCellFile(name2, file1);
         if (tpx != NULL) need_new_seed = 1;
      }

We want netgen to equate both BO_sky130_fd_sc_hd__clkbuf_8 and sky130_fd_sc_hd__clkbuf_8 in the layout to sky130_fd_sc_hd__clkbuf_8 in the netlist.

equate classes "-circuit2 sky130_fd_sc_hd__clkbuf_8" "-circuit1 BO_sky130_fd_sc_hd__clkbuf_8"

Is insufficient because, the correspondence between similarly named sky130_fd_sc_hd__clkbuf_8 and sky130_fd_sc_hd__clkbuf_8 is lost (see ===> 2 <=== above).

If we try to force correspondence between similarly named cells, like this

equate classes "-circuit2 sky130_fd_sc_hd__clkbuf_8" "-circuit1 sky130_fd_sc_hd__clkbuf_8"
equate classes "-circuit2 sky130_fd_sc_hd__clkbuf_8" "-circuit1 BO_sky130_fd_sc_hd__clkbuf_8"

I think we get the same result because the first equate statement is ineffective, because they are already equivalent (see ===> 1 <=== above).

If we try to reestablish correspondence between similarly named cells afterwards like this,

equate classes "-circuit2 sky130_fd_sc_hd__clkbuf_8" "-circuit1 BO_sky130_fd_sc_hd__clkbuf_8"
equate classes "-circuit2 sky130_fd_sc_hd__clkbuf_8" "-circuit1 sky130_fd_sc_hd__clkbuf_8"

it appears that the first correspondence is lost because the name exists in the other netlist causing the hash to be reset (see ===> 2 <=== above).

Maybe adding a check to not reset the hash at ===> 2 <=== if both names are the same would solve the problem.

I'll test.

[d-m-bailey]

The change appears to work. I'll make a pull request.

Here's the test data. I copied BO_sky130_fd_sc_hd__clkbuf_2 in the extracted netlist to a new (unused in the layout) subckt sky130_fd_sc_hd__clkbuf_2. With this subckt, both BO_sky130_fd_sc_hd__clkbuf_2 in the layout and sky130_fd_sc_hd__clkbuf_2 in the verilog are flattened. Without this subckt in the layout, there is no flattening of mismatched cells.

tar xzf test_equate.tar.gz
cd test_equate
./run_lvs

test_equate.tar.gz

Before

Device classes sky130_fd_sc_hd__clkbuf_2 and sky130_fd_sc_hd__clkbuf_2 are equivalent.
Flattening unmatched subcell BO_sky130_fd_sc_hd__clkbuf_2 in circuit BO_DFFRAM (0)(708 instances)

Flattening instances of sky130_fd_sc_hd__clkbuf_2 in cell DFFRAM (1) makes a better match
Making another compare attempt.

Class BO_DFFRAM (0):  Merged 16461 parallel devices.
Class DFFRAM (1):  Merged 15045 parallel devices.
Subcircuit summary:
Circuit 1: BO_DFFRAM                                                              |Circuit 2: DFFRAM
----------------------------------------------------------------------------------|----------------------------------------------------------------------------------
sky130_fd_pr__pfet_01v8_hvt (2124->1416)                                          |sky130_fd_pr__pfet_01v8_hvt (2124->1416)
sky130_fd_pr__nfet_01v8 (2124->1416)                                              |sky130_fd_pr__nfet_01v8 (2124->1416)
BO_sky130_fd_sc_hd__dfxtp_1 (8448)                                                |sky130_fd_sc_hd__dfxtp_1 (8448)

After

Device classes BO_sky130_fd_sc_hd__and2_2 and sky130_fd_sc_hd__and2_2 are equivalent.

Class BO_DFFRAM (0):  Merged 15045 parallel devices.
Class DFFRAM (1):  Merged 15045 parallel devices.
Subcircuit summary:
Circuit 1: BO_DFFRAM                                                              |Circuit 2: DFFRAM
----------------------------------------------------------------------------------|----------------------------------------------------------------------------------
BO_sky130_fd_sc_hd__clkbuf_2 (708)                                                |sky130_fd_sc_hd__clkbuf_2 (708)
BO_sky130_fd_sc_hd__dfxtp_1 (8448)                                                |sky130_fd_sc_hd__dfxtp_1 (8448)

[d-m-bailey]

@RTimothyEdwards Looks like there's still a problem when trying to match more than 2 cells in the layout with 1 cell in the source.

For example, the layout contains

P1_sky130_fs_sc_hd__decap_12
HH_sky130_fs_sc_hd__decap_12
sky130_fs_sc_hd__decap_12

while the source contains only

sky130_fs_sc_hd__decap_12

My setup file detects these matches and creates the following equate statements

equate "-circuit2 sky130_fs_sc_hd__decap_12" "-circuit1 P1_sky130_fs_sc_hd__decap_12"
equate "-circuit2 sky130_fs_sc_hd__decap_12" "-circuit1 sky130_fs_sc_hd__decap_12"
equate "-circuit2 sky130_fs_sc_hd__decap_12" "-circuit1 HH_sky130_fs_sc_hd__decap_12"
equate "-circuit2 sky130_fs_sc_hd__decap_12" "-circuit1 sky130_fs_sc_hd__decap_12"

The first equate statement invalidates the default matching by name. The second equate statement reinstates matching by name. However, the third equate statement invalidates the preceding 2 equate statements because a new seed is created according to EquivalenceClasses in base/netcmp.c (edited function name)

      if (!(tp->flags & CELL_DUPLICATE) && !(tp2->flags & CELL_DUPLICATE) &&
                        !(*matchfunc)(name1, name2)) {
         tpx = LookupCellFile(name1, file2);
         if (tpx != NULL) need_new_seed = 1;
         tpx = LookupCellFile(name2, file1);
         if (tpx != NULL) need_new_seed = 1;
      }

Is there a way to differentiate between an explicit equate and an implicit equate? If that's possible, then maybe only reseed for implicit equates.

[RTimothyEdwards]

@d-m-bailey : Does it work correctly if you remove the equate statements for A = A? I don't know that the code was written expecting that, since it is always assumed that cells with the same name should be compared. I think maybe the correct solution is that if given equate A A, the EquivalenceClasses() subroutine should just return without doing anything.

[d-m-bailey]

@RTimothyEdwards The reason I added equates for A(2) = A(1) is because setting A(2) = xx_A(1) invalidates A(2) = A(1). The code snippet I posted above resets the seed if the name exists in the other file. Initially, A(2) = A(1) is set as equated. When, A(2) = xx_A(1) is set, the above code checks for A in (1) or xx_A in (2). If it finds either, then the seed is reset and previous equivalence is lost. It seems to me that the code is saying, if you set an explicit equivalence, the implicit equivalence is invalid.

What I did in the setup file was to reestablish equivalence between same named cells, if they exist. That was the addition of the !(*matchfunc) (name1, name2). However, you can only do that once. The second A(2) = yy_A(2) will invalidate both A(2) = xx_A(1) and A(2) = A(1).

I'm going to try deleting that code.

[RTimothyEdwards]

What if you swap the entries for circuit1 and circuit2?

[d-m-bailey]

The documentation says that the first entry in the equate statement must be the unique value, so I don't think swapping works.

[d-m-bailey]

Fixed in 1.5.249