abcRr.c

/**CFile****************************************************************

  FileName    [abcRr.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Network and node package.]

  Synopsis    [Redundancy removal.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - June 20, 2005.]

  Revision    [$Id: abcRr.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]

***********************************************************************/

#include "base/abc/abc.h"
#include "proof/fraig/fraig.h"
#include "opt/sim/sim.h"

ABC_NAMESPACE_IMPL_START


////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

typedef struct Abc_RRMan_t_ Abc_RRMan_t;
struct Abc_RRMan_t_
{
    // the parameters
    Abc_Ntk_t *      pNtk;             // the network
    int              nFaninLevels;     // the number of fanin levels
    int              nFanoutLevels;    // the number of fanout levels
    // the node/fanin/fanout
    Abc_Obj_t *      pNode;            // the node
    Abc_Obj_t *      pFanin;           // the fanin
    Abc_Obj_t *      pFanout;          // the fanout
    // the intermediate cones
    Vec_Ptr_t *      vFaninLeaves;     // the leaves of the fanin cone
    Vec_Ptr_t *      vFanoutRoots;     // the roots of the fanout cone
    // the window
    Vec_Ptr_t *      vLeaves;          // the leaves of the window
    Vec_Ptr_t *      vCone;            // the internal nodes of the window
    Vec_Ptr_t *      vRoots;           // the roots of the window
    Abc_Ntk_t *      pWnd;             // the window derived for the edge
    // the miter 
    Abc_Ntk_t *      pMiter;           // the miter derived from the window
    Prove_Params_t * pParams;          // the miter proving parameters
    // statistical variables
    int              nNodesOld;        // the old number of nodes
    int              nLevelsOld;       // the old number of levels
    int              nEdgesTried;      // the number of nodes tried
    int              nEdgesRemoved;    // the number of nodes proved
    clock_t          timeWindow;       // the time to construct the window
    clock_t          timeMiter;        // the time to construct the miter
    clock_t          timeProve;        // the time to prove the miter
    clock_t          timeUpdate;       // the network update time
    clock_t          timeTotal;        // the total runtime
};

static Abc_RRMan_t * Abc_RRManStart();
static void          Abc_RRManStop( Abc_RRMan_t * p );
static void          Abc_RRManPrintStats( Abc_RRMan_t * p );
static void          Abc_RRManClean( Abc_RRMan_t * p );
static int           Abc_NtkRRProve( Abc_RRMan_t * p );
static int           Abc_NtkRRUpdate( Abc_Ntk_t * pNtk, Abc_Obj_t * pNode, Abc_Obj_t * pFanin, Abc_Obj_t * pFanout );
static int           Abc_NtkRRWindow( Abc_RRMan_t * p );

static int           Abc_NtkRRTfi_int( Vec_Ptr_t * vLeaves, int LevelLimit );
static int           Abc_NtkRRTfo_int( Vec_Ptr_t * vLeaves, Vec_Ptr_t * vRoots, int LevelLimit, Abc_Obj_t * pEdgeFanin, Abc_Obj_t * pEdgeFanout );
static int           Abc_NtkRRTfo_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vRoots, int LevelLimit );
static void          Abc_NtkRRTfi_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vCone, int LevelLimit );
static Abc_Ntk_t *   Abc_NtkWindow( Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vCone, Vec_Ptr_t * vRoots );

static void          Abc_NtkRRSimulateStart( Abc_Ntk_t * pNtk );
static void          Abc_NtkRRSimulateStop( Abc_Ntk_t * pNtk );

////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

/**Function*************************************************************

  Synopsis    [Removes stuck-at redundancies.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkRR( Abc_Ntk_t * pNtk, int nFaninLevels, int nFanoutLevels, int fUseFanouts, int fVerbose )
{
    ProgressBar * pProgress;
    Abc_RRMan_t * p;
    Abc_Obj_t * pNode, * pFanin, * pFanout;
    int i, k, m, nNodes, RetValue;
    clock_t clk, clkTotal = clock();
    // start the manager
    p = Abc_RRManStart();
    p->pNtk          = pNtk;
    p->nFaninLevels  = nFaninLevels;
    p->nFanoutLevels = nFanoutLevels;
    p->nNodesOld     = Abc_NtkNodeNum(pNtk);
    p->nLevelsOld    = Abc_AigLevel(pNtk);
    // remember latch values
//    Abc_NtkForEachLatch( pNtk, pNode, i )
//        pNode->pNext = pNode->pData;
    // go through the nodes
    Abc_NtkCleanCopy(pNtk);
    nNodes = Abc_NtkObjNumMax(pNtk);
    Abc_NtkRRSimulateStart(pNtk);
    pProgress = Extra_ProgressBarStart( stdout, nNodes );
    Abc_NtkForEachNode( pNtk, pNode, i )
    {
        Extra_ProgressBarUpdate( pProgress, i, NULL );
        // stop if all nodes have been tried once
        if ( i >= nNodes )
            break;
        // skip the constant node
//        if ( Abc_NodeIsConst(pNode) )
//            continue;
        // skip persistant nodes
        if ( Abc_NodeIsPersistant(pNode) )
            continue;
        // skip the nodes with many fanouts
        if ( Abc_ObjFanoutNum(pNode) > 1000 )
            continue;
        // construct the window
        if ( !fUseFanouts )
        {
            Abc_ObjForEachFanin( pNode, pFanin, k )
            {
                // skip the nodes with only one fanout (tree nodes)
                if ( Abc_ObjFanoutNum(pFanin) == 1 )
                    continue;
/*
                if ( pFanin->Id == 228 && pNode->Id == 2649 )
                {
                    int k = 0;
                }
*/
                p->nEdgesTried++;
                Abc_RRManClean( p );
                p->pNode   = pNode;
                p->pFanin  = pFanin;
                p->pFanout = NULL;

                clk = clock();
                RetValue = Abc_NtkRRWindow( p );
                p->timeWindow += clock() - clk;
                if ( !RetValue )
                    continue;
/*
                if ( pFanin->Id == 228 && pNode->Id == 2649 )
                {
                    Abc_NtkShowAig( p->pWnd, 0 );
                }
*/
                clk = clock();
                RetValue = Abc_NtkRRProve( p );
                p->timeMiter += clock() - clk;
                if ( !RetValue )
                    continue;
//printf( "%d -> %d (%d)\n", pFanin->Id, pNode->Id, k );

                clk = clock();
                Abc_NtkRRUpdate( pNtk, p->pNode, p->pFanin, p->pFanout );
                p->timeUpdate += clock() - clk;

                p->nEdgesRemoved++;
                break;
            }
            continue;
        }
        // use the fanouts
        Abc_ObjForEachFanin( pNode, pFanin, k )
        Abc_ObjForEachFanout( pNode, pFanout, m )
        {
            // skip the nodes with only one fanout (tree nodes)
//            if ( Abc_ObjFanoutNum(pFanin) == 1 && Abc_ObjFanoutNum(pNode) == 1 )
//                continue;

            p->nEdgesTried++;
            Abc_RRManClean( p );
            p->pNode   = pNode;
            p->pFanin  = pFanin;
            p->pFanout = pFanout;

            clk = clock();
            RetValue = Abc_NtkRRWindow( p );
            p->timeWindow += clock() - clk;
            if ( !RetValue )
                continue;

            clk = clock();
            RetValue = Abc_NtkRRProve( p );
            p->timeMiter += clock() - clk;
            if ( !RetValue )
                continue;

            clk = clock();
            Abc_NtkRRUpdate( pNtk, p->pNode, p->pFanin, p->pFanout );
            p->timeUpdate += clock() - clk;

            p->nEdgesRemoved++;
            break;
        }
    }
    Abc_NtkRRSimulateStop(pNtk);
    Extra_ProgressBarStop( pProgress );
    p->timeTotal = clock() - clkTotal;
    if ( fVerbose )
        Abc_RRManPrintStats( p );
    Abc_RRManStop( p );
    // restore latch values
//    Abc_NtkForEachLatch( pNtk, pNode, i )
//        pNode->pData = pNode->pNext, pNode->pNext = NULL;
    // put the nodes into the DFS order and reassign their IDs
    Abc_NtkReassignIds( pNtk );
    Abc_NtkLevel( pNtk );
    // check
    if ( !Abc_NtkCheck( pNtk ) )
    {
        printf( "Abc_NtkRR: The network check has failed.\n" );
        return 0;
    }
    return 1;
}

/**Function*************************************************************

  Synopsis    [Start the manager.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Abc_RRMan_t * Abc_RRManStart()
{
    Abc_RRMan_t * p;
    p = ABC_ALLOC( Abc_RRMan_t, 1 );
    memset( p, 0, sizeof(Abc_RRMan_t) );
    p->vFaninLeaves  = Vec_PtrAlloc( 100 );  // the leaves of the fanin cone
    p->vFanoutRoots  = Vec_PtrAlloc( 100 );  // the roots of the fanout cone
    p->vLeaves       = Vec_PtrAlloc( 100 );  // the leaves of the window
    p->vCone         = Vec_PtrAlloc( 100 );  // the internal nodes of the window
    p->vRoots        = Vec_PtrAlloc( 100 );  // the roots of the window
    p->pParams       = ABC_ALLOC( Prove_Params_t, 1 );
    memset( p->pParams, 0, sizeof(Prove_Params_t) );
    Prove_ParamsSetDefault( p->pParams );
    return p;
}

/**Function*************************************************************

  Synopsis    [Stop the manager.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_RRManStop( Abc_RRMan_t * p )
{
    Abc_RRManClean( p );
    Vec_PtrFree( p->vFaninLeaves  );  
    Vec_PtrFree( p->vFanoutRoots  );  
    Vec_PtrFree( p->vLeaves );  
    Vec_PtrFree( p->vCone );  
    Vec_PtrFree( p->vRoots );  
    ABC_FREE( p->pParams );
    ABC_FREE( p );
}

/**Function*************************************************************

  Synopsis    [Stop the manager.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_RRManPrintStats( Abc_RRMan_t * p )
{
    double Ratio = 100.0*(p->nNodesOld  - Abc_NtkNodeNum(p->pNtk))/p->nNodesOld;
    printf( "Redundancy removal statistics:\n" );
    printf( "Edges tried     = %6d.\n", p->nEdgesTried );
    printf( "Edges removed   = %6d. (%5.2f %%)\n", p->nEdgesRemoved, 100.0*p->nEdgesRemoved/p->nEdgesTried );
    printf( "Node gain       = %6d. (%5.2f %%)\n", p->nNodesOld  - Abc_NtkNodeNum(p->pNtk), Ratio );
    printf( "Level gain      = %6d.\n", p->nLevelsOld - Abc_AigLevel(p->pNtk) );
    ABC_PRT( "Windowing      ", p->timeWindow );
    ABC_PRT( "Miter          ", p->timeMiter );
    ABC_PRT( "    Construct  ", p->timeMiter - p->timeProve );
    ABC_PRT( "    Prove      ", p->timeProve );
    ABC_PRT( "Update         ", p->timeUpdate );
    ABC_PRT( "TOTAL          ", p->timeTotal );
}

/**Function*************************************************************

  Synopsis    [Clean the manager.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_RRManClean( Abc_RRMan_t * p )
{
    p->pNode   = NULL; 
    p->pFanin  = NULL; 
    p->pFanout = NULL; 
    Vec_PtrClear( p->vFaninLeaves  );  
    Vec_PtrClear( p->vFanoutRoots  );  
    Vec_PtrClear( p->vLeaves );  
    Vec_PtrClear( p->vCone );  
    Vec_PtrClear( p->vRoots );  
    if ( p->pWnd )   Abc_NtkDelete( p->pWnd );
    if ( p->pMiter ) Abc_NtkDelete( p->pMiter );
    p->pWnd   = NULL;
    p->pMiter = NULL;
}

/**Function*************************************************************

  Synopsis    [Returns 1 if the miter is constant 0.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkRRProve( Abc_RRMan_t * p )
{
    Abc_Ntk_t * pWndCopy;
    int RetValue;
    clock_t clk;
//    Abc_NtkShowAig( p->pWnd, 0 );
    pWndCopy = Abc_NtkDup( p->pWnd );
    Abc_NtkRRUpdate( pWndCopy, p->pNode->pCopy->pCopy, p->pFanin->pCopy->pCopy, p->pFanout? p->pFanout->pCopy->pCopy : NULL );
    if ( !Abc_NtkIsDfsOrdered(pWndCopy) )
        Abc_NtkReassignIds(pWndCopy);
    p->pMiter = Abc_NtkMiter( p->pWnd, pWndCopy, 1, 0, 0, 0 );
    Abc_NtkDelete( pWndCopy );
clk = clock();
    RetValue  = Abc_NtkMiterProve( &p->pMiter, p->pParams );
p->timeProve += clock() - clk;
    if ( RetValue == 1 )
        return 1;
    return 0;
}

/**Function*************************************************************

  Synopsis    [Updates the network after redundancy removal.]

  Description [This procedure assumes that non-control value of the fanin
  was proved redundant. It is okay to concentrate on non-control values
  because the control values can be seen as redundancy of the fanout edge.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkRRUpdate( Abc_Ntk_t * pNtk, Abc_Obj_t * pNode, Abc_Obj_t * pFanin, Abc_Obj_t * pFanout )
{
    Abc_Obj_t * pNodeNew, * pFanoutNew;
    assert( pFanout == NULL );
    assert( !Abc_ObjIsComplement(pNode) );
    assert( !Abc_ObjIsComplement(pFanin) );
    assert( !Abc_ObjIsComplement(pFanout) );
    // find the node after redundancy removal
    if ( pFanin == Abc_ObjFanin0(pNode) )
        pNodeNew = Abc_ObjChild1(pNode);
    else if ( pFanin == Abc_ObjFanin1(pNode) )
        pNodeNew = Abc_ObjChild0(pNode);
    else assert( 0 );
    // replace
    if ( pFanout == NULL )
    {
        Abc_AigReplace( (Abc_Aig_t *)pNtk->pManFunc, pNode, pNodeNew, 1 );
        return 1;
    }
    // find the fanout after redundancy removal
    if ( pNode == Abc_ObjFanin0(pFanout) )
        pFanoutNew = Abc_AigAnd( (Abc_Aig_t *)pNtk->pManFunc, Abc_ObjNotCond(pNodeNew,Abc_ObjFaninC0(pFanout)), Abc_ObjChild1(pFanout) );
    else if ( pNode == Abc_ObjFanin1(pFanout) )
        pFanoutNew = Abc_AigAnd( (Abc_Aig_t *)pNtk->pManFunc, Abc_ObjNotCond(pNodeNew,Abc_ObjFaninC1(pFanout)), Abc_ObjChild0(pFanout) );
    else assert( 0 );
    // replace
    Abc_AigReplace( (Abc_Aig_t *)pNtk->pManFunc, pFanout, pFanoutNew, 1 );
    return 1;
}

/**Function*************************************************************

  Synopsis    [Constructs window for checking RR.]

  Description [If the window (p->pWnd) with the given scope (p->nFaninLevels, 
  p->nFanoutLevels) cannot be constructed, returns 0. Otherwise, returns 1.
  The levels are measured from the fanin node (pFanin) and the fanout node
  (pEdgeFanout), respectively.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkRRWindow( Abc_RRMan_t * p )
{
    Abc_Obj_t * pObj, * pEdgeFanin, * pEdgeFanout;
    int i, LevelMin, LevelMax, RetValue;

    // get the edge
    pEdgeFanout = p->pFanout? p->pFanout : p->pNode;
    pEdgeFanin  = p->pFanout? p->pNode : p->pFanin;
    // get the minimum and maximum levels of the window
    LevelMin = Abc_MaxInt( 0, ((int)p->pFanin->Level) - p->nFaninLevels );
    LevelMax = (int)pEdgeFanout->Level + p->nFanoutLevels;

    // start the TFI leaves with the fanin
    Abc_NtkIncrementTravId( p->pNtk );
    Abc_NodeSetTravIdCurrent( p->pFanin );
    Vec_PtrPush( p->vFaninLeaves, p->pFanin );
    // mark the TFI cone and collect the leaves down to the given level
    while ( Abc_NtkRRTfi_int(p->vFaninLeaves, LevelMin) );

    // mark the leaves with the new TravId
    Abc_NtkIncrementTravId( p->pNtk );
    Vec_PtrForEachEntry( Abc_Obj_t *, p->vFaninLeaves, pObj, i )
        Abc_NodeSetTravIdCurrent( pObj );
    // traverse the TFO cone of the leaves (while skipping the edge)
    // (a) mark the nodes in the cone using the current TravId
    // (b) collect the nodes that have external fanouts into p->vFanoutRoots
    while ( Abc_NtkRRTfo_int(p->vFaninLeaves, p->vFanoutRoots, LevelMax, pEdgeFanin, pEdgeFanout) );

    // mark the fanout roots
    Vec_PtrForEachEntry( Abc_Obj_t *, p->vFanoutRoots, pObj, i )
        pObj->fMarkA = 1;
    // collect roots reachable from the fanout (p->vRoots)
    RetValue = Abc_NtkRRTfo_rec( pEdgeFanout, p->vRoots, LevelMax + 1 );
    // unmark the fanout roots
    Vec_PtrForEachEntry( Abc_Obj_t *, p->vFanoutRoots, pObj, i )
        pObj->fMarkA = 0;

    // return if the window is infeasible
    if ( RetValue == 0 )
        return 0;

    // collect the DFS-ordered new cone (p->vCone) and new leaves (p->vLeaves)
    // using the previous marks coming from the TFO cone
    Abc_NtkIncrementTravId( p->pNtk );
    Vec_PtrForEachEntry( Abc_Obj_t *, p->vRoots, pObj, i )
        Abc_NtkRRTfi_rec( pObj, p->vLeaves, p->vCone, LevelMin );

    // create a new network
    p->pWnd = Abc_NtkWindow( p->pNtk, p->vLeaves, p->vCone, p->vRoots );
    return 1;
}

/**Function*************************************************************

  Synopsis    [Marks the nodes in the TFI and collects their leaves.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkRRTfi_int( Vec_Ptr_t * vLeaves, int LevelLimit )
{
    Abc_Obj_t * pObj, * pNext;
    int i, k, LevelMax, nSize;
    assert( LevelLimit >= 0 );
    // find the maximum level of leaves
    LevelMax = 0;
    Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
        if ( LevelMax < (int)pObj->Level )
            LevelMax = pObj->Level;
    // if the nodes are all PIs, LevelMax == 0
    if ( LevelMax <= LevelLimit )
        return 0;
    // expand the nodes with the minimum level
    nSize = Vec_PtrSize(vLeaves);
    Vec_PtrForEachEntryStop( Abc_Obj_t *, vLeaves, pObj, i, nSize )
    {
        if ( LevelMax != (int)pObj->Level )
            continue;
        Abc_ObjForEachFanin( pObj, pNext, k )
        {
            if ( Abc_NodeIsTravIdCurrent(pNext) )
                continue;
            Abc_NodeSetTravIdCurrent( pNext );
            Vec_PtrPush( vLeaves, pNext );
        }
    }
    // remove old nodes (cannot remove a PI)
    k = 0;
    Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
    {
        if ( LevelMax == (int)pObj->Level )
            continue;
        Vec_PtrWriteEntry( vLeaves, k++, pObj );
    }
    Vec_PtrShrink( vLeaves, k );
    if ( Vec_PtrSize(vLeaves) > 2000 )
        return 0;
    return 1;
}

/**Function*************************************************************

  Synopsis    [Marks the nodes in the TFO and collects their roots.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkRRTfo_int( Vec_Ptr_t * vLeaves, Vec_Ptr_t * vRoots, int LevelLimit, Abc_Obj_t * pEdgeFanin, Abc_Obj_t * pEdgeFanout )
{
    Abc_Obj_t * pObj, * pNext;
    int i, k, LevelMin, nSize, fObjIsRoot;
    // find the minimum level of leaves
    LevelMin = ABC_INFINITY;
    Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
        if ( LevelMin > (int)pObj->Level )
            LevelMin = pObj->Level;
    // if the minimum level exceed the limit, we are done
    if ( LevelMin > LevelLimit )
        return 0;
    // expand the nodes with the minimum level
    nSize = Vec_PtrSize(vLeaves);
    Vec_PtrForEachEntryStop( Abc_Obj_t *, vLeaves, pObj, i, nSize )
    {
        if ( LevelMin != (int)pObj->Level )
            continue;
        fObjIsRoot = 0;
        Abc_ObjForEachFanout( pObj, pNext, k )
        {
            // check if the fanout is outside of the cone
            if ( Abc_ObjIsCo(pNext) || pNext->Level > (unsigned)LevelLimit )
            {
                fObjIsRoot = 1;
                continue;
            }
            // skip the edge under check
            if ( pObj == pEdgeFanin && pNext == pEdgeFanout )
                continue;
            // skip the visited fanouts
            if ( Abc_NodeIsTravIdCurrent(pNext) )
                continue;
            Abc_NodeSetTravIdCurrent( pNext );
            Vec_PtrPush( vLeaves, pNext );
        }
        if ( fObjIsRoot )
            Vec_PtrPush( vRoots, pObj );
    }
    // remove old nodes
    k = 0;
    Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
    {
        if ( LevelMin == (int)pObj->Level )
            continue;
        Vec_PtrWriteEntry( vLeaves, k++, pObj );
    }
    Vec_PtrShrink( vLeaves, k );
    if ( Vec_PtrSize(vLeaves) > 2000 )
        return 0;
    return 1;
}

/**Function*************************************************************

  Synopsis    [Collects the roots in the TFO of the node.]

  Description [Note that this procedure can be improved by
  marking and skipping the visited nodes.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkRRTfo_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vRoots, int LevelLimit )
{
    Abc_Obj_t * pFanout;
    int i;
    // if we encountered a node outside of the TFO cone of the fanins, quit
    if ( Abc_ObjIsCo(pNode) || pNode->Level > (unsigned)LevelLimit )
        return 0;
    // if we encountered a node on the boundary, add it to the roots
    if ( pNode->fMarkA )
    {
        Vec_PtrPushUnique( vRoots, pNode );
        return 1;
    }
    // mark the node with the current TravId (needed to have all internal nodes marked)
    Abc_NodeSetTravIdCurrent( pNode );
    // traverse the fanouts
    Abc_ObjForEachFanout( pNode, pFanout, i )
        if ( !Abc_NtkRRTfo_rec( pFanout, vRoots, LevelLimit ) )
            return 0;
    return 1;
}

/**Function*************************************************************

  Synopsis    [Collects the leaves and cone of the roots.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NtkRRTfi_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vCone, int LevelLimit )
{
    Abc_Obj_t * pFanin;
    int i;
    // skip visited nodes
    if ( Abc_NodeIsTravIdCurrent(pNode) )
        return;
    // add node to leaves if it is not in TFI cone of the leaves (marked before) or below the limit
    if ( !Abc_NodeIsTravIdPrevious(pNode) || (int)pNode->Level <= LevelLimit )
    {
        Abc_NodeSetTravIdCurrent( pNode );
        Vec_PtrPush( vLeaves, pNode );
        return;
    }
    // mark the node as visited
    Abc_NodeSetTravIdCurrent( pNode );
    // call for the node's fanins
    Abc_ObjForEachFanin( pNode, pFanin, i )
        Abc_NtkRRTfi_rec( pFanin, vLeaves, vCone, LevelLimit );
    // add the node to the cone in topological order
    Vec_PtrPush( vCone, pNode );
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Abc_Ntk_t * Abc_NtkWindow( Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vCone, Vec_Ptr_t * vRoots )
{
    Abc_Ntk_t * pNtkNew; 
    Abc_Obj_t * pObj;
    int fCheck = 1;
    int i;
    assert( Abc_NtkIsStrash(pNtk) );
    // start the network
    pNtkNew = Abc_NtkAlloc( pNtk->ntkType, pNtk->ntkFunc, 1 );
    // duplicate the name and the spec
    pNtkNew->pName = Extra_UtilStrsav( "temp" );
    // map the constant nodes
    Abc_AigConst1(pNtk)->pCopy = Abc_AigConst1(pNtkNew);
    // create and map the PIs
    Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
        pObj->pCopy = Abc_NtkCreatePi(pNtkNew);
    // copy the AND gates
    Vec_PtrForEachEntry( Abc_Obj_t *, vCone, pObj, i )
        pObj->pCopy = Abc_AigAnd( (Abc_Aig_t *)pNtkNew->pManFunc, Abc_ObjChild0Copy(pObj), Abc_ObjChild1Copy(pObj) );
    // compare the number of nodes before and after
    if ( Vec_PtrSize(vCone) != Abc_NtkNodeNum(pNtkNew) )
        printf( "Warning: Structural hashing during windowing reduced %d nodes (this is a bug).\n",
            Vec_PtrSize(vCone) - Abc_NtkNodeNum(pNtkNew) );
    // create the POs
    Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
    {
        assert( !Abc_ObjIsComplement(pObj->pCopy) );
        Abc_ObjAddFanin( Abc_NtkCreatePo(pNtkNew), pObj->pCopy );
    }
    // add the PI/PO names
    Abc_NtkAddDummyPiNames( pNtkNew );
    Abc_NtkAddDummyPoNames( pNtkNew );
    // check
    if ( fCheck && !Abc_NtkCheck( pNtkNew ) )
    {
        printf( "Abc_NtkWindow: The network check has failed.\n" );
        return NULL;
    }
    return pNtkNew;
}


/**Function*************************************************************

  Synopsis    [Starts simulation to detect non-redundant edges.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NtkRRSimulateStart( Abc_Ntk_t * pNtk )
{
    Abc_Obj_t * pObj;
    unsigned uData, uData0, uData1;
    int i;
    Abc_AigConst1(pNtk)->pData = (void *)~((unsigned)0);
    Abc_NtkForEachCi( pNtk, pObj, i )
        pObj->pData = (void *)(ABC_PTRUINT_T)SIM_RANDOM_UNSIGNED;
    Abc_NtkForEachNode( pNtk, pObj, i )
    {
        if ( i == 0 ) continue;
        uData0 = (unsigned)(ABC_PTRUINT_T)Abc_ObjFanin0(pObj)->pData;
        uData1 = (unsigned)(ABC_PTRUINT_T)Abc_ObjFanin1(pObj)->pData;
        uData  = Abc_ObjFaninC0(pObj)? ~uData0 : uData0;
        uData &= Abc_ObjFaninC1(pObj)? ~uData1 : uData1;
        assert( pObj->pData == NULL );
        pObj->pData = (void *)(ABC_PTRUINT_T)uData;
    }
}

/**Function*************************************************************

  Synopsis    [Stops simulation to detect non-redundant edges.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NtkRRSimulateStop( Abc_Ntk_t * pNtk )
{
    Abc_Obj_t * pObj;
    int i;
    Abc_NtkForEachObj( pNtk, pObj, i )
        pObj->pData = NULL;
}







static void Sim_TraverseNodes_rec( Abc_Obj_t * pRoot, Vec_Str_t * vTargets, Vec_Ptr_t * vNodes );
static void Sim_CollectNodes_rec( Abc_Obj_t * pRoot, Vec_Ptr_t * vField );
static void Sim_SimulateCollected( Vec_Str_t * vTargets, Vec_Ptr_t * vNodes, Vec_Ptr_t * vField );

/**Function*************************************************************

  Synopsis    [Simulation to detect non-redundant edges.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Str_t * Abc_NtkRRSimulate( Abc_Ntk_t * pNtk )
{
    Vec_Ptr_t * vNodes, * vField;
    Vec_Str_t * vTargets;
    Abc_Obj_t * pObj;
    unsigned uData, uData0, uData1;
    int PrevCi, Phase, i, k;

    // start the candidates
    vTargets = Vec_StrStart( Abc_NtkObjNumMax(pNtk) + 1 );
    Abc_NtkForEachNode( pNtk, pObj, i )
    {
        Phase = ((Abc_ObjFanoutNum(Abc_ObjFanin1(pObj)) > 1) << 1);
        Phase |= (Abc_ObjFanoutNum(Abc_ObjFanin0(pObj)) > 1);
        Vec_StrWriteEntry( vTargets, pObj->Id, (char)Phase );
    }

    // simulate patters and store them in copy
    Abc_AigConst1(pNtk)->pCopy = (Abc_Obj_t *)~((unsigned)0);
    Abc_NtkForEachCi( pNtk, pObj, i )
        pObj->pCopy = (Abc_Obj_t *)(ABC_PTRUINT_T)SIM_RANDOM_UNSIGNED;
    Abc_NtkForEachNode( pNtk, pObj, i )
    {
        if ( i == 0 ) continue;
        uData0 = (unsigned)(ABC_PTRUINT_T)Abc_ObjFanin0(pObj)->pData;
        uData1 = (unsigned)(ABC_PTRUINT_T)Abc_ObjFanin1(pObj)->pData;
        uData  = Abc_ObjFaninC0(pObj)? ~uData0 : uData0;
        uData &= Abc_ObjFaninC1(pObj)? ~uData1 : uData1;
        pObj->pCopy = (Abc_Obj_t *)(ABC_PTRUINT_T)uData;
    }
    // store the result in data
    Abc_NtkForEachCo( pNtk, pObj, i )
    {
        uData0 = (unsigned)(ABC_PTRUINT_T)Abc_ObjFanin0(pObj)->pData;
        if ( Abc_ObjFaninC0(pObj) )
            pObj->pData = (void *)(ABC_PTRUINT_T)~uData0;
        else
            pObj->pData = (void *)(ABC_PTRUINT_T)uData0;
    }

    // refine the candidates
    for ( PrevCi = 0; PrevCi < Abc_NtkCiNum(pNtk); PrevCi = i )
    {
        vNodes = Vec_PtrAlloc( 10 );
        Abc_NtkIncrementTravId( pNtk );
        for ( i = PrevCi; i < Abc_NtkCiNum(pNtk); i++ )
        {
            Sim_TraverseNodes_rec( Abc_NtkCi(pNtk, i), vTargets, vNodes );
            if ( Vec_PtrSize(vNodes) > 128 )
                break;
        }
        // collect the marked nodes in the topological order
        vField = Vec_PtrAlloc( 10 );
        Abc_NtkIncrementTravId( pNtk );
        Abc_NtkForEachCo( pNtk, pObj, k )
            Sim_CollectNodes_rec( pObj, vField );

        // simulate these nodes
        Sim_SimulateCollected( vTargets, vNodes, vField );
        // prepare for the next loop
        Vec_PtrFree( vNodes );
    }

    // clean
    Abc_NtkForEachObj( pNtk, pObj, i )
        pObj->pData = NULL;
    return vTargets;
}

/**Function*************************************************************

  Synopsis    [Collects nodes starting from the given node.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Sim_TraverseNodes_rec( Abc_Obj_t * pRoot, Vec_Str_t * vTargets, Vec_Ptr_t * vNodes )
{
    Abc_Obj_t * pFanout;
    char Entry;
    int k;
    if ( Abc_NodeIsTravIdCurrent(pRoot) )
        return;
    Abc_NodeSetTravIdCurrent( pRoot );
    // save the reached targets
    Entry = Vec_StrEntry(vTargets, pRoot->Id);
    if ( Entry & 1 )
        Vec_PtrPush( vNodes, Abc_ObjNot(pRoot) );
    if ( Entry & 2 )
        Vec_PtrPush( vNodes, pRoot );
    // explore the fanouts
    Abc_ObjForEachFanout( pRoot, pFanout, k )
        Sim_TraverseNodes_rec( pFanout, vTargets, vNodes );
}

/**Function*************************************************************

  Synopsis    [Collects nodes starting from the given node.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Sim_CollectNodes_rec( Abc_Obj_t * pRoot, Vec_Ptr_t * vField )
{
    Abc_Obj_t * pFanin;
    int i;
    if ( Abc_NodeIsTravIdCurrent(pRoot) )
        return;
    if ( !Abc_NodeIsTravIdPrevious(pRoot) )
        return;
    Abc_NodeSetTravIdCurrent( pRoot );
    Abc_ObjForEachFanin( pRoot, pFanin, i )
        Sim_CollectNodes_rec( pFanin, vField );
    if ( !Abc_ObjIsCo(pRoot) )
        pRoot->pData = (void *)(ABC_PTRUINT_T)Vec_PtrSize(vField);
    Vec_PtrPush( vField, pRoot );
}

/**Function*************************************************************

  Synopsis    [Simulate the given nodes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Sim_SimulateCollected( Vec_Str_t * vTargets, Vec_Ptr_t * vNodes, Vec_Ptr_t * vField )
{
    Abc_Obj_t * pObj, * pFanin0, * pFanin1, * pDisproved;
    Vec_Ptr_t * vSims;
    unsigned * pUnsigned, * pUnsignedF;
    int i, k, Phase, fCompl;
    // get simulation info
    vSims = Sim_UtilInfoAlloc( Vec_PtrSize(vField), Vec_PtrSize(vNodes), 0 );
    // simulate the nodes
    Vec_PtrForEachEntry( Abc_Obj_t *, vField, pObj, i )
    {
        if ( Abc_ObjIsCi(pObj) )
        {
            pUnsigned = (unsigned *)Vec_PtrEntry( vSims, i );
            for ( k = 0; k < Vec_PtrSize(vNodes); k++ )
                pUnsigned[k] = (unsigned)(ABC_PTRUINT_T)pObj->pCopy;
            continue;
        }
        if ( Abc_ObjIsCo(pObj) )
        {
            pUnsigned  = (unsigned *)Vec_PtrEntry( vSims, i );
            pUnsignedF = (unsigned *)Vec_PtrEntry( vSims, (int)(ABC_PTRUINT_T)Abc_ObjFanin0(pObj)->pData );
            if ( Abc_ObjFaninC0(pObj) )
                for ( k = 0; k < Vec_PtrSize(vNodes); k++ )
                    pUnsigned[k] = ~pUnsignedF[k];
            else
                for ( k = 0; k < Vec_PtrSize(vNodes); k++ )
                    pUnsigned[k] = pUnsignedF[k];
            // update targets
            for ( k = 0; k < Vec_PtrSize(vNodes); k++ )
            {
                if ( pUnsigned[k] == (unsigned)(ABC_PTRUINT_T)pObj->pData )
                    continue;
                pDisproved = (Abc_Obj_t *)Vec_PtrEntry( vNodes, k );
                fCompl = Abc_ObjIsComplement(pDisproved);
                pDisproved = Abc_ObjRegular(pDisproved);
                Phase = Vec_StrEntry( vTargets, pDisproved->Id );
                if ( fCompl )
                    Phase = (Phase & 2);
                else
                    Phase = (Phase & 1);
                Vec_StrWriteEntry( vTargets, pDisproved->Id, (char)Phase );
            }
            continue;
        }
        // simulate the node
        pFanin0 = Abc_ObjFanin0(pObj);
        pFanin1 = Abc_ObjFanin1(pObj);
    }
}



/*
                {
                    unsigned uData;
                    if ( pFanin == Abc_ObjFanin0(pNode) )
                    {
                        uData = (unsigned)Abc_ObjFanin1(pNode)->pData;
                        uData = Abc_ObjFaninC1(pNode)? ~uData : uData;
                    }
                    else if ( pFanin == Abc_ObjFanin1(pNode) )
                    {
                        uData = (unsigned)Abc_ObjFanin0(pNode)->pData;
                        uData = Abc_ObjFaninC0(pNode)? ~uData : uData;
                    }
                    uData ^= (unsigned)pNode->pData;
//                    Extra_PrintBinary( stdout, &uData, 32 ); printf( "\n" );
                    if ( Extra_WordCountOnes(uData) > 8 )
                        continue;
                }
*/

////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


ABC_NAMESPACE_IMPL_END