Correctly insert explicit inverters when PO reference to negated signal in AQFP

[lee30sonia]

Background In AQFP, input negation is for free, thus we don't need explicit inverters most of the time. However, when a gate is referenced by a primary output in its negated form, explicit inverter cells (= input negated buffers) might be necessary. In some (rare) cases, i.e., a gate on the critical path is referenced in both polarities by two POs, this necessary inverter might even increase the circuit depth and, if POs are assumed to be balanced, result in (#POs) more buffers needed.

Current solution As can be observed, dealing with output negations in the "not-stupid" way involves quite some case splitting, although the problem seems straight-forward.

1. If there is no negative PO reference (i.e. "only positive PO(s)" or "positive PO(s) + gates"), things are unchanged.
2. If there is only one negative PO reference and no balancing buffers are needed and the concerned node is a gate, then its output negation is pushed to its fanins. No additional buffer/inverter needed.
3. If there are only negative PO(s) and there are either balancing buffers or splitters or the concerned node is a PI, then the first buffer/splitter is turned into an inverter. The number of buffers is not affected, expect if it is a non-branched PI.
4. If POs are assumed to be balanced, and there are gate fanouts and negative PO(s), then the highest level of buffers (connecting to the POs) are inverted. The number of buffers is not affected.
5. If POs are assumed to be balanced, and there are gate fanouts, negative PO(s) and positive PO(s), then similar to the previous case. More buffers might be needed (e.g. 2 positive POs could share a buffer but 1 positive + 1 negative POs need 2 buffers).
6. If POs are assumed to be NOT balanced, and there are gate fanouts and negative PO(s) with or without positive PO(s), then the buffer tree is first built for the gate fanouts, then splitters are inserted to ensure enough slots for positive PO(s) + 1, then an inverter is added and finally the splitter tree for the negative PO(s) is constructed on top of the inverter.

This scheme is not optimal (not even locally, for some cases). However, we expect that the complicated cases should not appear often in real designs and/or that the negation could be dealt with in the next sequential stage.

[codecov-commenter]

Codecov Report

Merging #532 (04f8bce) into master (f427196) will decrease coverage by 0.09%. The diff coverage is 70.65%.

@@            Coverage Diff             @@
##           master     #532      +/-   ##
==========================================
- Coverage   82.61%   82.52%   -0.10%     
==========================================
  Files         146      146              
  Lines       18099    18207     +108     
==========================================
+ Hits        14953    15025      +72     
- Misses       3146     3182      +36     

Impacted Files	Coverage Δ
...mockturtle/algorithms/aqfp/buffer_verification.hpp	100.00% <ø> (ø)
include/mockturtle/networks/buffered.hpp	90.43% <58.82%> (-4.01%)	:arrow_down:
...de/mockturtle/algorithms/aqfp/buffer_insertion.hpp	78.52% <72.00%> (-1.99%)	:arrow_down:
include/mockturtle/properties/aqfpcost.hpp	100.00% <0.00%> (ø)
...le/algorithms/aqfp_resynthesis/detail/dag_cost.hpp
...algorithms/aqfp_resynthesis/detail/partial_dag.hpp
...le/algorithms/aqfp_resynthesis/detail/dag_util.hpp
...tle/algorithms/aqfp_resynthesis/detail/dag_gen.hpp
...kturtle/algorithms/aqfp_resynthesis/detail/dag.hpp
...ude/mockturtle/algorithms/aqfp/detail/dag_cost.hpp	100.00% <0.00%> (ø)
... and 5 more

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update f427196...04f8bce. Read the comment docs.