Reduce time in combinational cycle check by skipping duplicated checks #1628
Description
I'm using latest Amaranth release 0.5.7 from pip.
When checking for combinational cycles for Operator cells, time to check all nets grows exponentially with the size of the output. This is an example code that takes ~9s in my computer to generate the Verilog:
from amaranth import *
from amaranth.back import verilog
m = Module()
a = Signal(12)
ports = [a]
for i in range(10):
signal = Signal.like(a, name = f's{i}')
m.d.comb += signal.eq(1 << a)
ports.append(signal)
verilog.convert(m, ports = ports, emit_src=False, strip_internal_attrs=True)If I understand the flow correctly, time can be reduced with the following changes (I know it's not very clean, but something equivalent could be implemented):
diff --git a/amaranth/hdl/_nir.py b/amaranth/hdl/_nir.py
index c15247a..47d7753 100644
--- a/amaranth/hdl/_nir.py
+++ b/amaranth/hdl/_nir.py
@@ -475,8 +475,36 @@ class Netlist:
return cycle
for cell_idx, cell in enumerate(self.cells):
- for net in cell.output_nets(cell_idx):
+ break_early = False
+
+ # Check if we can break early to avoid duplicated comb checks
+ if isinstance(cell, Operator):
+ if len(cell.inputs) == 1:
+ if cell.operator != "~":
+ break_early = True
+ elif len(cell.inputs) == 2:
+ break_early = True
+
+ output_nets = cell.output_nets(cell_idx)
+
+ # If we break early, mark all nets as busy
+ if break_early:
+ busy.update(output_nets)
+
+ for net in output_nets:
+
+ # If we break early, only this net will be checked explicitly
+ if break_early:
+ busy.remove(net)
+
assert traverse(net) is None
+
+ if break_early:
+ break
+
+ if break_early:
+ busy.clear()
+
for value in self.signals.values():
for net in value:
assert traverse(net) is None
Basically, I looked at Operator.comb_edges_to in amaranth/hdl/_nir.py (730:750). When operator is not "~" or when cell has two operands, for each net in the cell's output it's re-checking all of the input nets. The diff I attached basically looks for this condition, and breaks the loop early to avoid re-checking all the inputs nets again. With this change, the same snippet attached above goes from ~9s to ~0.3s.
Let me know if something doesn't look right, or if more information is required. Thanks in advance!
EDIT: I updated the diff to include all the output nets in busy set to avoid missed combinational checks.
EDIT: Update function line numbers of Operator.comb_edges_to (I looked at a different release)