Refactoring creates cyclic network

[lee30sonia]

Suspected bug in refactoring and/or direct_resynthesis reported by @KamilDre in #511.
Test case and code to reproduce:

module top( x0 , x1 , x2 , y0 );
  input x0 , x1 , x2 ;
  output y0 ;
  wire n4 , n5 , n6 , n7 , n8 , n9 , n10 , n11 , n12 , n13 , n14 , n15 , n16 , n17 , n18 , n19 , n20 , n21 , n22 , n23 , n24 , n25 , n26 , n27 ;
  assign n4 = x0 | x1 ;
  assign n5 = x1 & ~n4 ;
  assign n6 = x1 & ~x2 ;
  assign n7 = n5 & ~n6 ;
  assign n8 = x1 | n4 ;
  assign n9 = n6 | n8 ;
  assign n10 = ~n7 & n9 ;
  assign n11 = x0 & x1 ;
  assign n12 = ~n5 & n6 ;
  assign n13 = ~n11 & n12 ;
  assign n14 = n10 & ~n13 ;
  assign n15 = x0 & ~n4 ;
  assign n16 = x0 | n15 ;
  assign n17 = x0 & n15 ;
  assign n18 = n16 & ~n17 ;
  assign n19 = n14 & ~n18 ;
  assign n20 = n18 | n19 ;
  assign n21 = ( ~n14 & n19 ) | ( ~n14 & n20 ) | ( n19 & n20 ) ;
  assign n22 = ~n13 & n18 ;
  assign n23 = n10 & ~n22 ;
  assign n24 = n17 & ~n23 ;
  assign n25 = ~n17 & n23 ;
  assign n26 = n24 | n25 ;
  assign n27 = n21 | n26 ;
  assign y0 = ~n27 ;
endmodule

#include <mockturtle/networks/mig.hpp>
#include <mockturtle/io/verilog_reader.hpp>
#include <mockturtle/algorithms/refactoring.hpp>
#include <mockturtle/algorithms/node_resynthesis/direct.hpp>
#include <mockturtle/utils/debugging_utils.hpp>
#include <lorina/verilog.hpp>

int main()
{
    using namespace mockturtle;

    mig_network ntk;
    auto lorina_res = lorina::read_verilog( "acyclic.v", verilog_reader( ntk ) );
    assert( lorina_res == lorina::return_code::success );
    assert( network_is_acylic( ntk ) );

    direct_resynthesis<mig_network> resyn;
    refactoring( ntk, resyn );
    if ( network_is_acylic( ntk ) )
        return 0; // bug-free
    else
        return 1; // buggy
}

Note: The reproducibility of the bug using the above case might be platform-dependent, as the bug seems to be related to an uninitialized variable (see below).

[lee30sonia]

After some investigation, it seems that the bug is caused by:

• direct_resynthesis does not support all of the 3-input functions (including 2-input functions such as AND/OR that are passed as a 3-input truth table).
• refactoring does not check if the callback of the resynthesis functor is actually called, neither does it initialize new_f to something non-random. (line 176)

Which result in the algorithm sometimes substituting nodes more-or-less randomly.