abc9 crash on synth_ice40 in Yosys 0.38

[spth]

Version

Yosys 0.38 (git sha1 543faed9c8c, gcc 13.2.0-13 -fPIC -Os)

On which OS did this happen?

Linux

Reproduction Steps

yosys> read_verilog -sv cpu_flat.v
yosys> synth_ice40 -top cpu

cpu_flat.v.gz

Expected Behavior

synthesis completes (as it does when using -noabc9)

Actual Behavior

[…]
2.41.10. Executing ABC9_OPS pass (helper functions for ABC9).
<suppressed ~141 debug messages>
ERROR: Assert `no_loops' failed in passes/techmap/abc9_ops.cc:795.

[Ravenslofty]

Your code really does have a logic loop.

2.41.3. Executing SCC pass (detecting logic loops).
Found an SCC: [snip]
Found 1 SCCs in module cpu.
Found 1 SCCs.

And Verilator agrees, e.g.:

%Warning-UNOPTFLAT: cpu_flat.sv:214:14: Signal unoptimizable: Circular combinational logic: 'cpu.next_flags'
  214 |  logic [7:0] next_flags;
      |              ^~~~~~~~~~
                    cpu_flat.sv:214:14:      Example path: cpu.next_flags
                    cpu_flat.sv:336:2:      Example path: ALWAYS
                    cpu_flat.sv:222:15:      Example path: cpu.next_pc_noint
                    cpu_flat.sv:567:2:      Example path: ALWAYS
                    cpu_flat.sv:173:15:      Example path: cpu.op0
                    cpu_flat.sv:65:16:      Example path: ALWAYS
                    cpu_flat.sv:31:14:      Example path: cpu.alu.result
                    cpu_flat.sv:567:2:      Example path: ALWAYS

Even the original ABC flow reports it needs to break loops, e.g.

Breaking loop using new signal $abcloop$100682: \alu.c_out -> $flatten\alu.$ternary$cpu_flat.sv:86$319_Y
                                                \alu.c_out -> $flatten\alu.$xor$cpu_flat.sv:86$316_Y
                                                \alu.c_out -> $flatten\alu.$xor$cpu_flat.sv:86$314_Y
                                                \alu.c_out -> $flatten\alu.$xor$cpu_flat.sv:86$312_Y
                                                \alu.c_out -> $flatten\alu.$xor$cpu_flat.sv:86$310_Y
                                                \alu.c_out -> $flatten\alu.$xor$cpu_flat.sv:86$308_Y
                                                \alu.c_out -> $flatten\alu.$xor$cpu_flat.sv:86$306_Y
                                                \alu.c_out -> $flatten\alu.$xor$cpu_flat.sv:86$304_Y
                                                \alu.c_out -> $flatten\alu.$xor$cpu_flat.sv:86$302_Y
                                                \alu.c_out -> $flatten\alu.$xor$cpu_flat.sv:86$300_Y
                                                \alu.c_out -> $flatten\alu.$xor$cpu_flat.sv:86$298_Y
                                                \alu.c_out -> $flatten\alu.$xor$cpu_flat.sv:86$296_Y
                                                \alu.c_out -> $flatten\alu.$xor$cpu_flat.sv:86$294_Y
                                                \alu.c_out -> $flatten\alu.$xor$cpu_flat.sv:86$292_Y
                                                \alu.c_out -> $6\next_flags[1:1]

I would suggest fixing this; most timing analysis tools do not handle logic loops like this.

[spth]

Well, I'm new to Verilog synthesis (I did use Verilog for CPLDs a bit many years ago, but never for a bigger design), so it is not surprising that I write bad code. While a compiler might emit diagnostics (errors or warnings) for bad code, I think it shouldn't crash with an internal assertion failure.

[povik]

While a compiler might emit diagnostics (errors or warnings) for bad code, I think it shouldn't crash with an internal assertion failure.

Yes, it shouldn't, this is a valid issue with Yosys.

[nakengelhardt]

abc9 seems to already have handling for combinatorial loops, and this line: https://github.com/YosysHQ/yosys/blob/8d004661dc39fc647edb3dd418a09fda692f5670/passes/techmap/abc9.cc#L359 should be inserting some loop-breaking cells to handle this. We'll have to investigate what's going wrong.

[Ravenslofty]

I think this might be a bug in the scc pass; running it reports one SCC found, which abc9_ops -break_scc duly breaks, but in debug mode it reports there are 572 unbroken loops which should have been found by scc.

[jix]

What abc9_ops -break_scc does is only sufficient when every SCC consists of a single loop (it picks a single arbitrary cell per SCC and breaks all outputs), but a SCC can have multiple loops with no single cell being part of every loop.

If you change it to break all outputs of each cells in every SCC (e.g. using the diff below) synth_ice40 completes without errors. Breaking all outputs of each SCC cell is excessive but always sufficient and shows that the issue is most likely not with the scc pass.

diff --git a/passes/techmap/abc9_ops.cc b/passes/techmap/abc9_ops.cc
index 4eaed1f75..f1bcea735 100644
--- a/passes/techmap/abc9_ops.cc
+++ b/passes/techmap/abc9_ops.cc
@@ -584,11 +584,9 @@ void break_scc(RTLIL::Module *module)
        for (auto cell : scc_cells) {
                auto it = cell->attributes.find(ID::abc9_scc_id);
                log_assert(it != cell->attributes.end());
-               auto id = it->second;
-               auto r = ids_seen.insert(id);
-               cell->attributes.erase(it);
-               if (!r.second)
+               if (ids_seen.count(it->second))
                        continue;
+               cell->attributes.erase(it);
                for (auto &c : cell->connections_) {
                        if (c.second.is_fully_const()) continue;
                        if (cell->output(c.first)) {

[povik]

Agreed, we were just discussing the same with @Ravenslofty and I offer to change abc9_ops -break_scc to make it break SCCs robustly.

[Ravenslofty]

I wrote about this on the YosysHQ internal slack, but I'll copy my thinking here:

Take the following badly-drawn example graph:

How many SCCs are there here? There is the loop A -> B -> C -> A and the loop B -> C -> B. The scc pass seems to only return the first loop, but the ABC9 breaker code seems to expect both loops to be returned; that's how this issue manifests.

[povik]

4260 has a minimal testcase with a logic SCC that won't be fully broken by abc9_ops -break_scc.

[Ravenslofty]

Either way, since this is an issue on the Yosys side of things rather than with ABC itself, does anybody object to me removing the ABC tag here?