lsils / mockturtle

C++ logic network library
MIT License
191 stars 133 forks source link

Fixing non-simplified gates handling in networks #632

Closed aletempiac closed 5 months ago

aletempiac commented 5 months ago

This PR solves a bug that may occur when using the methods substitute_node_no_restrash or replace_in_node_no_restrash.

In particular, these methods may create non-simplified gates such as buffer nodes. For instance, in an AIG, a buffer could be seen as an AND node where both fanins are connected to the same node with the same phase. In this case, this node is seen as a PI or a CI according to the previous code. This PR solves this issue by reserving the unused field data[1].h2 to track if a node is a PI or CI.

Moreover, another related issue is present in the XAG and XMG networks. In xag_network, AND and XOR are distinguished by the ordering of the indexes such that AND: index0 < index1, and XOR: index0 > index1. The behavior is undefined when index0 = index1. The proposed patch treats the equal case as an AND. When index0 = index1 is an XOR gate, the gate is transformed into an AND gate by setting the inputs to constants, i.e. by performing the simplification. XMGs handles this case similarly by treating the equal case as an MAJ3 gate.

Finally, this PR includes runtime improvements to air_balance and xag_balance, which had long run times on very large benchmarks. The default optimization method to improve size has been reduced from quadratic to linear complexity, in terms of the number of nodes. The old version is available by setting the parameter fast_mode to false.

codecov-commenter commented 5 months ago

Codecov Report

Attention: 25 lines in your changes are missing coverage. Please review.

Comparison is base (1134d1d) 83.68% compared to head (0c32859) 83.54%. Report is 1 commits behind head on master.

Files Patch % Lines
include/mockturtle/algorithms/xag_balancing.hpp 87.09% 8 Missing :warning:
include/mockturtle/networks/xmg.hpp 38.46% 8 Missing :warning:
include/mockturtle/networks/xag.hpp 62.50% 6 Missing :warning:
include/mockturtle/algorithms/aig_balancing.hpp 90.32% 3 Missing :warning:

:exclamation: Your organization needs to install the Codecov GitHub app to enable full functionality.

Additional details and impacted files ```diff @@ Coverage Diff @@ ## master #632 +/- ## ========================================== - Coverage 83.68% 83.54% -0.14% ========================================== Files 186 187 +1 Lines 29617 29837 +220 ========================================== + Hits 24784 24927 +143 - Misses 4833 4910 +77 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.