abcSweep.c

Go to the documentation of this file.

 
#include "base/abc/abc.h"
#include "base/main/main.h"
#include "proof/fraig/fraig.h"
 
#ifdef ABC_USE_CUDD
#include "bdd/extrab/extraBdd.h"
#endif
 
ABC_NAMESPACE_IMPL_START

 
static void           Abc_NtkFraigSweepUsingExdc( Fraig_Man_t * pMan, Abc_Ntk_t * pNtk );
static stmm_table *   Abc_NtkFraigEquiv( Abc_Ntk_t * pNtk, int fUseInv, int fVerbose, int fVeryVerbose );
static void           Abc_NtkFraigTransform( Abc_Ntk_t * pNtk, stmm_table * tEquiv, int fUseInv, int fVerbose );
static void           Abc_NtkFraigMergeClassMapped( Abc_Ntk_t * pNtk, Abc_Obj_t * pChain, int fUseInv, int fVerbose );
static void           Abc_NtkFraigMergeClass( Abc_Ntk_t * pNtk, Abc_Obj_t * pChain, int fUseInv, int fVerbose );
static int            Abc_NodeDroppingCost( Abc_Obj_t * pNode );
 
static int            Abc_NtkReduceNodes( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes );
static void           Abc_NodeSweep( Abc_Obj_t * pNode, int fVerbose );


int Abc_NtkFraigSweep( Abc_Ntk_t * pNtk, int fUseInv, int fExdc, int fVerbose, int fVeryVerbose )
{
    Fraig_Params_t Params;
    Abc_Ntk_t * pNtkAig;
    Fraig_Man_t * pMan;
    stmm_table * tEquiv;
    Abc_Obj_t * pObj;
    int i, fUseTrick;
 
    assert( !Abc_NtkIsStrash(pNtk) );
 
    // save gate assignments
    fUseTrick = 0;
    if ( Abc_NtkIsMappedLogic(pNtk) )
    {
        fUseTrick = 1;
        Abc_NtkForEachNode( pNtk, pObj, i )
            pObj->pNext = (Abc_Obj_t *)pObj->pData;
    }
    // derive the AIG
    pNtkAig = Abc_NtkStrash( pNtk, 0, 1, 0 );
    // reconstruct gate assignments
    if ( fUseTrick )
    {
//        extern void * Abc_FrameReadLibGen(); 
        Hop_ManStop( (Hop_Man_t *)pNtk->pManFunc );
        pNtk->pManFunc = Abc_FrameReadLibGen();
        pNtk->ntkFunc = ABC_FUNC_MAP;
        Abc_NtkForEachNode( pNtk, pObj, i )
            pObj->pData = pObj->pNext, pObj->pNext = NULL;
    }
 
    // perform fraiging of the AIG
    Fraig_ParamsSetDefault( &Params );
    Params.fInternal = 1;
    pMan = (Fraig_Man_t *)Abc_NtkToFraig( pNtkAig, &Params, 0, 0 );   
    // cannot use EXDC with FRAIG because it can create classes of equivalent FRAIG nodes
    // with representative nodes that do not correspond to the nodes with the current network
 
    // update FRAIG using EXDC
    if ( fExdc )
    {
        if ( pNtk->pExdc == NULL )
            printf( "Warning: Networks has no EXDC.\n" );
        else
            Abc_NtkFraigSweepUsingExdc( pMan, pNtk );
    }
    // assign levels to the nodes of the network
    Abc_NtkLevel( pNtk );
 
    // collect the classes of equivalent nets
    tEquiv = Abc_NtkFraigEquiv( pNtk, fUseInv, fVerbose, fVeryVerbose );
 
    // transform the network into the equivalent one
    Abc_NtkFraigTransform( pNtk, tEquiv, fUseInv, fVerbose );
    stmm_free_table( tEquiv );
 
    // free the manager
    Fraig_ManFree( pMan );
    Abc_NtkDelete( pNtkAig );
 
    // cleanup the dangling nodes
    if ( Abc_NtkHasMapping(pNtk) )
        Abc_NtkCleanup( pNtk, fVerbose );
    else
        Abc_NtkSweep( pNtk, fVerbose );
 
    // check
    if ( !Abc_NtkCheck( pNtk ) )
    {
        printf( "Abc_NtkFraigSweep: The network check has failed.\n" );
        return 0;
    }
    return 1;
}

void Abc_NtkFraigSweepUsingExdc( Fraig_Man_t * pMan, Abc_Ntk_t * pNtk )
{
    Fraig_Node_t * gNodeExdc, * gNode, * gNodeRes;
    Abc_Obj_t * pNode, * pNodeAig;
    int i;
    extern Fraig_Node_t * Abc_NtkToFraigExdc( Fraig_Man_t * pMan, Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkExdc );
 
    assert( pNtk->pExdc );
    // derive FRAIG node representing don't-cares in the EXDC network
    gNodeExdc = Abc_NtkToFraigExdc( pMan, pNtk, pNtk->pExdc );
    // update the node pointers
    Abc_NtkForEachNode( pNtk, pNode, i )
    {
        // skip the constant input nodes
        if ( Abc_ObjFaninNum(pNode) == 0 )
            continue;
        // get the strashed node
        pNodeAig = pNode->pCopy;
        // skip the dangling nodes
        if ( pNodeAig == NULL )
            continue;
        // get the FRAIG node
        gNode = Fraig_NotCond( Abc_ObjRegular(pNodeAig)->pCopy, (int)Abc_ObjIsComplement(pNodeAig) );
        // perform ANDing with EXDC
        gNodeRes = Fraig_NodeAnd( pMan, gNode, Fraig_Not(gNodeExdc) );
        // write the node back
        Abc_ObjRegular(pNodeAig)->pCopy = (Abc_Obj_t *)Fraig_NotCond( gNodeRes, (int)Abc_ObjIsComplement(pNodeAig) );
    }
}

stmm_table * Abc_NtkFraigEquiv( Abc_Ntk_t * pNtk, int fUseInv, int fVerbose, int fVeryVerbose )
{
    Abc_Obj_t * pList, * pNode, * pNodeAig;
    Fraig_Node_t * gNode;
    Abc_Obj_t ** ppSlot;
    stmm_table * tStrash2Net;
    stmm_table * tResult;
    stmm_generator * gen;
    int c, Counter;
 
    // create mapping of strashed nodes into the corresponding network nodes
    tStrash2Net = stmm_init_table(stmm_ptrcmp,stmm_ptrhash);
    Abc_NtkForEachNode( pNtk, pNode, c )
    {
        // skip the constant input nodes
        if ( Abc_ObjFaninNum(pNode) == 0 )
            continue;
        // get the strashed node
        pNodeAig = pNode->pCopy;
        // skip the dangling nodes
        if ( pNodeAig == NULL )
            continue;
        // skip the nodes that fanout into COs
        if ( Abc_NodeFindCoFanout(pNode) )
            continue;
        // get the FRAIG node
        gNode = Fraig_NotCond( Abc_ObjRegular(pNodeAig)->pCopy, (int)Abc_ObjIsComplement(pNodeAig) );
        if ( !stmm_find_or_add( tStrash2Net, (char *)Fraig_Regular(gNode), (char ***)&ppSlot ) )
            *ppSlot = NULL;
        // add the node to the list
        pNode->pNext = *ppSlot;
        *ppSlot = pNode;
        // mark the node if it is complemented
        pNode->fPhase = Fraig_IsComplement(gNode);
    }
 
    // print the classes
    c = 0;
    Counter = 0;
    tResult = stmm_init_table(stmm_ptrcmp,stmm_ptrhash);
    stmm_foreach_item( tStrash2Net, gen, (char **)&gNode, (char **)&pList )
    {
        // skip the trival classes
        if ( pList == NULL || pList->pNext == NULL )
            continue;
        // add the non-trival class
        stmm_insert( tResult, (char *)pList, NULL );
        // count nodes in the non-trival classes
        for ( pNode = pList; pNode; pNode = pNode->pNext )
            Counter++;
 
        if ( fVeryVerbose )
        {
            printf( "Class %2d : {", c );
            for ( pNode = pList; pNode; pNode = pNode->pNext )
            {
                pNode->pCopy = NULL;
                printf( " %s", Abc_ObjName(pNode) );
                printf( "(%c)", pNode->fPhase? '-' : '+' );
                printf( "(%d)", pNode->Level );
            }
            printf( " }\n" );
            c++;
        }
    }
    if ( fVerbose || fVeryVerbose )
    {
        printf( "Sweeping stats for network \"%s\":\n", pNtk->pName );
        printf( "Internal nodes = %d. Different functions (up to compl) = %d.\n", Abc_NtkNodeNum(pNtk), stmm_count(tStrash2Net) );
        printf( "Non-trivial classes = %d. Nodes in non-trivial classes = %d.\n", stmm_count(tResult), Counter );
    }
    stmm_free_table( tStrash2Net );
    return tResult;
}
 

void Abc_NtkFraigTransform( Abc_Ntk_t * pNtk, stmm_table * tEquiv, int fUseInv, int fVerbose )
{
    stmm_generator * gen;
    Abc_Obj_t * pList;
    if ( stmm_count(tEquiv) == 0 )
        return;
    // merge nodes in the classes
    if ( Abc_NtkHasMapping( pNtk ) )
    {
        Abc_NtkDelayTrace( pNtk, NULL, NULL, 0 );
        stmm_foreach_item( tEquiv, gen, (char **)&pList, NULL )
            Abc_NtkFraigMergeClassMapped( pNtk, pList, fUseInv, fVerbose );
    }
    else 
    {
        stmm_foreach_item( tEquiv, gen, (char **)&pList, NULL )
            Abc_NtkFraigMergeClass( pNtk, pList, fUseInv, fVerbose );
    }
}
 

void Abc_NtkFraigMergeClassMapped( Abc_Ntk_t * pNtk, Abc_Obj_t * pChain, int fUseInv, int fVerbose )
{
    Abc_Obj_t * pListDir, * pListInv;
    Abc_Obj_t * pNodeMin, * pNode, * pNext;
    float Arrival1, Arrival2;
 
    assert( pChain );
    assert( pChain->pNext );
 
    // divide the nodes into two parts: 
    // those that need the invertor and those that don't need
    pListDir = pListInv = NULL;
    for ( pNode = pChain, pNext = pChain->pNext; 
          pNode; 
          pNode = pNext, pNext = pNode? pNode->pNext : NULL )
    {
        // check to which class the node belongs
        if ( pNode->fPhase == 1 )
        {
            pNode->pNext = pListDir;
            pListDir = pNode;
        }
        else
        {
            pNode->pNext = pListInv;
            pListInv = pNode;
        }
    }
 
    // find the node with the smallest number of logic levels
    pNodeMin = pListDir;
    for ( pNode = pListDir; pNode; pNode = pNode->pNext )
    {
        Arrival1 = Abc_NodeReadArrivalWorst(pNodeMin);
        Arrival2 = Abc_NodeReadArrivalWorst(pNode   );
//        assert( Abc_ObjIsCi(pNodeMin) || Arrival1 > 0 );
//        assert( Abc_ObjIsCi(pNode)    || Arrival2 > 0 );
        if (  Arrival1 > Arrival2 ||
              (Arrival1 == Arrival2 && pNodeMin->Level >  pNode->Level) ||
              (Arrival1 == Arrival2 && pNodeMin->Level == pNode->Level &&
              Abc_NodeDroppingCost(pNodeMin) < Abc_NodeDroppingCost(pNode))  )
            pNodeMin = pNode;
    }
 
    // move the fanouts of the direct nodes
    for ( pNode = pListDir; pNode; pNode = pNode->pNext )
        if ( pNode != pNodeMin )
            Abc_ObjTransferFanout( pNode, pNodeMin );
 
    // find the node with the smallest number of logic levels
    pNodeMin = pListInv;
    for ( pNode = pListInv; pNode; pNode = pNode->pNext )
    {
        Arrival1 = Abc_NodeReadArrivalWorst(pNodeMin);
        Arrival2 = Abc_NodeReadArrivalWorst(pNode   );
//        assert( Abc_ObjIsCi(pNodeMin) || Arrival1 > 0 );
//        assert( Abc_ObjIsCi(pNode)    || Arrival2 > 0 );
        if (  Arrival1 > Arrival2 ||
              (Arrival1 == Arrival2 && pNodeMin->Level >  pNode->Level) ||
              (Arrival1 == Arrival2 && pNodeMin->Level == pNode->Level &&
              Abc_NodeDroppingCost(pNodeMin) < Abc_NodeDroppingCost(pNode))  )
            pNodeMin = pNode;
    }
 
    // move the fanouts of the direct nodes
    for ( pNode = pListInv; pNode; pNode = pNode->pNext )
        if ( pNode != pNodeMin )
            Abc_ObjTransferFanout( pNode, pNodeMin );
}

void Abc_NtkFraigMergeClass( Abc_Ntk_t * pNtk, Abc_Obj_t * pChain, int fUseInv, int fVerbose )
{
    Abc_Obj_t * pListDir, * pListInv;
    Abc_Obj_t * pNodeMin, * pNodeMinInv;
    Abc_Obj_t * pNode, * pNext;
 
    assert( pChain );
    assert( pChain->pNext );
 
    // find the node with the smallest number of logic levels
    pNodeMin = pChain;
    for ( pNode = pChain->pNext; pNode; pNode = pNode->pNext )
        if (  pNodeMin->Level >  pNode->Level || 
            ( pNodeMin->Level == pNode->Level && 
              Abc_NodeDroppingCost(pNodeMin) < Abc_NodeDroppingCost(pNode) ) )
            pNodeMin = pNode;
 
    // divide the nodes into two parts: 
    // those that need the invertor and those that don't need
    pListDir = pListInv = NULL;
    for ( pNode = pChain, pNext = pChain->pNext; 
          pNode; 
          pNode = pNext, pNext = pNode? pNode->pNext : NULL )
    {
        if ( pNode == pNodeMin )
            continue;
        // check to which class the node belongs
        if ( pNodeMin->fPhase == pNode->fPhase )
        {
            pNode->pNext = pListDir;
            pListDir = pNode;
        }
        else
        {
            pNode->pNext = pListInv;
            pListInv = pNode;
        }
    }
 
    // move the fanouts of the direct nodes
    for ( pNode = pListDir; pNode; pNode = pNode->pNext )
        Abc_ObjTransferFanout( pNode, pNodeMin );
 
    // skip if there are no inverted nodes
    if ( pListInv == NULL )
        return;
 
    // add the invertor
    pNodeMinInv = Abc_NtkCreateNodeInv( pNtk, pNodeMin );
   
    // move the fanouts of the inverted nodes
    for ( pNode = pListInv; pNode; pNode = pNode->pNext )
        Abc_ObjTransferFanout( pNode, pNodeMinInv );
}
 

int Abc_NodeDroppingCost( Abc_Obj_t * pNode )
{ 
    return 1;
}
 
 
 
 

int Abc_NtkCleanup( Abc_Ntk_t * pNtk, int fVerbose )
{
    Vec_Ptr_t * vNodes;
    int Counter;
    assert( Abc_NtkIsLogic(pNtk) );
    // mark the nodes reachable from the POs
    vNodes = Abc_NtkDfs( pNtk, 0 );
    Counter = Abc_NtkReduceNodes( pNtk, vNodes );
    if ( fVerbose )
        printf( "Cleanup removed %d dangling nodes.\n", Counter );
    Vec_PtrFree( vNodes );
    return Counter;
}

int Abc_NtkCleanupNodes( Abc_Ntk_t * pNtk, Vec_Ptr_t * vRoots, int fVerbose )
{
    Vec_Ptr_t * vNodes, * vStarts;
    Abc_Obj_t * pObj;
    int i, Counter;
    assert( Abc_NtkIsLogic(pNtk) );
    // collect starting nodes into one array
    vStarts = Vec_PtrAlloc( 1000 );
    Abc_NtkForEachCo( pNtk, pObj, i )
        Vec_PtrPush( vStarts, pObj );
    Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
        if ( pObj )
            Vec_PtrPush( vStarts, pObj );
    // mark the nodes reachable from the POs
    vNodes = Abc_NtkDfsNodes( pNtk, (Abc_Obj_t **)Vec_PtrArray(vStarts), Vec_PtrSize(vStarts) );
    Vec_PtrFree( vStarts );
    Counter = Abc_NtkReduceNodes( pNtk, vNodes );
    if ( fVerbose )
        printf( "Cleanup removed %d dangling nodes.\n", Counter );
    Vec_PtrFree( vNodes );
    return Counter;
}

int Abc_NtkReduceNodes( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes )
{
    Abc_Obj_t * pNode;
    int i, Counter;
    assert( Abc_NtkIsLogic(pNtk) );
    // mark the nodes reachable from the POs
    Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
        pNode->fMarkA = 1;
    // remove the non-marked nodes
    Counter = 0;
    Abc_NtkForEachNode( pNtk, pNode, i )
        if ( pNode->fMarkA == 0 )
        {
            Abc_NtkDeleteObj( pNode );
            Counter++;
        }
    // unmark the remaining nodes
    Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
        pNode->fMarkA = 0;
    // check
    if ( !Abc_NtkCheck( pNtk ) )
        printf( "Abc_NtkCleanup: The network check has failed.\n" );
    return Counter;
}
 
 
 
 
#ifdef ABC_USE_CUDD

void Abc_NodeConstantInput( Abc_Obj_t * pNode, Abc_Obj_t * pFanin, int fConst0 )
{
    DdManager * dd = (DdManager *)pNode->pNtk->pManFunc;
    DdNode * bVar, * bTemp;
    int iFanin;
    assert( Abc_NtkIsBddLogic(pNode->pNtk) ); 
    if ( (iFanin = Vec_IntFind( &pNode->vFanins, pFanin->Id )) == -1 )
    {
        printf( "Node %s should be among", Abc_ObjName(pFanin) );
        printf( " the fanins of node %s...\n", Abc_ObjName(pNode) );
        return;
    }
    bVar = Cudd_NotCond( Cudd_bddIthVar(dd, iFanin), fConst0 );
    pNode->pData = Cudd_Cofactor( dd, bTemp = (DdNode *)pNode->pData, bVar );   Cudd_Ref( (DdNode *)pNode->pData );
    Cudd_RecursiveDeref( dd, bTemp );
}

int Abc_NtkSweep( Abc_Ntk_t * pNtk, int fVerbose )
{
    Vec_Ptr_t * vNodes;
    Abc_Obj_t * pNode, * pFanout, * pDriver;
    int i, nNodesOld;
    assert( Abc_NtkIsLogic(pNtk) ); 
    // convert network to BDD representation
    if ( !Abc_NtkToBdd(pNtk) )
    {
        fprintf( stdout, "Converting to BDD has failed.\n" );
        return 1;
    }
    // perform cleanup
    nNodesOld = Abc_NtkNodeNum(pNtk);
    Abc_NtkCleanup( pNtk, 0 );
    // prepare nodes for sweeping
    //Abc_NtkRemoveDupFanins(pNtk);
    Abc_NtkMinimumBase(pNtk);
    // collect sweepable nodes
    vNodes = Vec_PtrAlloc( 100 );
    Abc_NtkForEachNode( pNtk, pNode, i )
        if ( Abc_ObjFaninNum(pNode) < 2 )
            Vec_PtrPush( vNodes, pNode );
    // sweep the nodes
    while ( Vec_PtrSize(vNodes) > 0 )
    {
        // get any sweepable node
        pNode = (Abc_Obj_t *)Vec_PtrPop(vNodes);
        if ( !Abc_ObjIsNode(pNode) )
            continue;
        // get any non-CO fanout of this node
        pFanout = Abc_NodeFindNonCoFanout(pNode);
        if ( pFanout == NULL )
            continue;
        assert( Abc_ObjIsNode(pFanout) );
        // transform the function of the fanout
        if ( Abc_ObjFaninNum(pNode) == 0 )
            Abc_NodeConstantInput( pFanout, pNode, Abc_NodeIsConst0(pNode) );
        else 
        {
            assert( Abc_ObjFaninNum(pNode) == 1 );
            pDriver = Abc_ObjFanin0(pNode);
            if ( Abc_NodeIsInv(pNode) )
                Abc_NodeComplementInput( pFanout, pNode );
            Abc_ObjPatchFanin( pFanout, pNode, pDriver );
        }
        //Abc_NodeRemoveDupFanins( pFanout );
        Abc_NodeMinimumBase( pFanout );
        // check if the fanout should be added
        if ( Abc_ObjFaninNum(pFanout) < 2 )
            Vec_PtrPush( vNodes, pFanout );
        // check if the node has other fanouts
        if ( Abc_ObjFanoutNum(pNode) > 0 )
            Vec_PtrPush( vNodes, pNode );
        else
            Abc_NtkDeleteObj_rec( pNode, 1 );
    }
    Vec_PtrFree( vNodes );
    // sweep a node into its CO fanout if all of this is true:
    // (a) this node is a single-input node
    // (b) the driver of the node has only one fanout (this node)
    // (c) the driver is a node
    Abc_NtkForEachCo( pNtk, pFanout, i )
    {
        pNode = Abc_ObjFanin0(pFanout);
        if ( Abc_ObjFaninNum(pNode) != 1 )
            continue;
        pDriver = Abc_ObjFanin0(pNode);
        if ( !(Abc_ObjFanoutNum(pDriver) == 1 && Abc_ObjIsNode(pDriver)) )
            continue;
        // trasform this CO
        if ( Abc_NodeIsInv(pNode) )
            pDriver->pData = Cudd_Not(pDriver->pData);
        Abc_ObjPatchFanin( pFanout, pNode, pDriver );
    }
    // perform cleanup
    Abc_NtkCleanup( pNtk, 0 );
    // report
    if ( fVerbose )
        printf( "Sweep removed %d nodes.\n", nNodesOld - Abc_NtkNodeNum(pNtk) );
    return nNodesOld - Abc_NtkNodeNum(pNtk);
}
 
 
#else
 
int Abc_NtkSweep( Abc_Ntk_t * pNtk, int fVerbose ) { return 1; }
 
#endif
 

int Abc_NodeRemoveNonCurrentObjects( Abc_Ntk_t * pNtk )
{
    Abc_Obj_t * pObj;
    int Counter, i;
    int fVerbose = 0;
 
    // report on the nodes to be deleted
    if ( fVerbose )
    {
        printf( "These nodes will be deleted: \n" );
        Abc_NtkForEachObj( pNtk, pObj, i )
            if ( !Abc_NodeIsTravIdCurrent( pObj ) )
            {
                printf( "    " );
                Abc_ObjPrint( stdout, pObj );
            }
    }
    
    // delete the nodes    
    Counter = 0;
    Abc_NtkForEachObj( pNtk, pObj, i )
        if ( !Abc_NodeIsTravIdCurrent( pObj ) )
        {
            Abc_NtkDeleteObj( pObj );
            Counter++;
        }
    return Counter;
}

void Abc_NtkSetTravId_rec( Abc_Obj_t * pObj )
{
    Abc_NodeSetTravIdCurrent(pObj);
    if ( Abc_ObjFaninNum(pObj) == 0 )
        return;
    assert( Abc_ObjFaninNum(pObj) == 1 );
    Abc_NtkSetTravId_rec( Abc_ObjFanin0(pObj) );    
}

int Abc_NtkCheckConstant_rec( Abc_Obj_t * pObj )
{
    if ( Abc_ObjFaninNum(pObj) == 0 )
    {
        if ( !Abc_ObjIsNode(pObj) )
            return -1;
        if ( Abc_NodeIsConst0(pObj) )
            return 0;
        if ( Abc_NodeIsConst1(pObj) )
            return 1;
        assert( 0 );
        return -1;
    }
    if ( Abc_ObjIsLatch(pObj) || Abc_ObjFaninNum(pObj) > 1 )
        return -1;
    if ( !Abc_ObjIsNode(pObj) || Abc_NodeIsBuf(pObj) )
        return Abc_NtkCheckConstant_rec( Abc_ObjFanin0(pObj) );
    if ( Abc_NodeIsInv(pObj) )
    {
        int RetValue = Abc_NtkCheckConstant_rec( Abc_ObjFanin0(pObj) );
        if ( RetValue == 0 )
            return 1;
        if ( RetValue == 1 )
            return 0;
        return RetValue;
    }
    assert( 0 );
    return -1;
}

int Abc_NtkLatchSweep( Abc_Ntk_t * pNtk )
{
    Abc_Obj_t * pFanin, * pLatch, * pLatchPivot = NULL;
    int Counter, RetValue, i;
    Counter = 0;
    // go through the latches
    Abc_NtkForEachLatch( pNtk, pLatch, i )
    {
        // check if the latch has constant input
        RetValue = Abc_NtkCheckConstant_rec( Abc_ObjFanin0(pLatch) );
        if ( RetValue == -1 )
            continue;
        // found a latch with constant fanin
        if ( (RetValue == 1 && Abc_LatchIsInit0(pLatch)) ||
             (RetValue == 0 && Abc_LatchIsInit1(pLatch)) )
        {
            // fanin constant differs from the latch init value
            if ( pLatchPivot == NULL )
            {
                pLatchPivot = pLatch;
                continue;
            }
            if ( Abc_LatchInit(pLatch) != Abc_LatchInit(pLatchPivot) ) // add inverter
                pFanin = Abc_NtkCreateNodeInv( pNtk, Abc_ObjFanout0(pLatchPivot) );
            else
                pFanin = Abc_ObjFanout0(pLatchPivot);
        }
        else
            pFanin = Abc_ObjFanin0(Abc_ObjFanin0(pLatch));
        // replace latch
        Abc_ObjTransferFanout( Abc_ObjFanout0(pLatch), pFanin );
        // delete the extra nodes
        Abc_NtkDeleteObj_rec( Abc_ObjFanout0(pLatch), 0 );
        Counter++;
    }
    return Counter;
}

int Abc_NtkReplaceAutonomousLogic( Abc_Ntk_t * pNtk )
{
    Abc_Obj_t * pNode, * pFanin;
    Vec_Ptr_t * vNodes;
    int i, k, Counter;
    // collect the nodes that feed into the reachable logic
    vNodes = Vec_PtrAlloc( 100 );
    Abc_NtkForEachObj( pNtk, pNode, i )
    {
        // skip non-visited fanins
        if ( !Abc_NodeIsTravIdCurrent(pNode) )
            continue;
        // look for non-visited fanins
        Abc_ObjForEachFanin( pNode, pFanin, k )
        {
            // skip visited fanins
            if ( Abc_NodeIsTravIdCurrent(pFanin) )
                continue;
            // skip constants and latches fed by constants
            if ( Abc_NtkCheckConstant_rec(pFanin) != -1 ||
                 (Abc_ObjIsBo(pFanin) && Abc_NtkCheckConstant_rec(Abc_ObjFanin0(Abc_ObjFanin0(pFanin))) != -1) )
            {
                Abc_NtkSetTravId_rec( pFanin );
                continue;
            }
            assert( !Abc_ObjIsLatch(pFanin) );
            Vec_PtrPush( vNodes, pFanin );
        }
    }
    Vec_PtrUniqify( vNodes, (int (*)(const void *, const void *))Abc_ObjPointerCompare );
    // replace these nodes by the PIs
    Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
    {
        pFanin = Abc_NtkCreatePi(pNtk);
        Abc_ObjAssignName( pFanin, Abc_ObjName(pFanin), NULL );
        Abc_NodeSetTravIdCurrent( pFanin );
        Abc_ObjTransferFanout( pNode, pFanin );
    }
    Counter = Vec_PtrSize(vNodes);
    Vec_PtrFree( vNodes );
    return Counter;
}

int Abc_NtkCleanupSeq( Abc_Ntk_t * pNtk, int fLatchSweep, int fAutoSweep, int fVerbose )
{
    Vec_Ptr_t * vNodes;
    int Counter;
    assert( Abc_NtkIsLogic(pNtk) );
    // mark the nodes reachable from the POs
    vNodes = Abc_NtkDfsSeq( pNtk );
    Vec_PtrFree( vNodes );
    // remove the non-marked nodes
    Counter = Abc_NodeRemoveNonCurrentObjects( pNtk );
    if ( fVerbose )
        printf( "Cleanup removed %4d dangling objects.\n", Counter );
    // check if some of the latches can be removed
    if ( fLatchSweep )
    {
        Counter = Abc_NtkLatchSweep( pNtk );
        if ( fVerbose )
            printf( "Cleanup removed %4d redundant latches.\n", Counter );
    }
    // detect the autonomous components
    if ( fAutoSweep )
    {
        vNodes = Abc_NtkDfsSeqReverse( pNtk );
        Vec_PtrFree( vNodes );
        // replace them by PIs
        Counter = Abc_NtkReplaceAutonomousLogic( pNtk );
        if ( fVerbose )
            printf( "Cleanup added   %4d additional PIs.\n", Counter );
        // remove the non-marked nodes
        Counter = Abc_NodeRemoveNonCurrentObjects( pNtk );
        if ( fVerbose )
            printf( "Cleanup removed %4d autonomous objects.\n", Counter );
    }
    // check
    if ( !Abc_NtkCheck( pNtk ) )
        printf( "Abc_NtkCleanupSeq: The network check has failed.\n" );
    return 1;
}

int Abc_NtkSweepBufsInvs( Abc_Ntk_t * pNtk, int fVerbose )
{
    Hop_Man_t * pMan;
    Abc_Obj_t * pObj, * pFanin;
    int i, k, fChanges = 1, Counter = 0;
    assert( Abc_NtkIsLogic(pNtk) ); 
    // convert network to BDD representation
    if ( !Abc_NtkToAig(pNtk) )
    {
        fprintf( stdout, "Converting to SOP has failed.\n" );
        return 1;
    }
    // get AIG manager
    pMan = (Hop_Man_t *)pNtk->pManFunc;
    // label selected nodes
    Abc_NtkIncrementTravId( pNtk );
    // iterate till no improvement
    while ( fChanges )
    {
        fChanges = 0;
        Abc_NtkForEachObj( pNtk, pObj, i )
        {
            Abc_ObjForEachFanin( pObj, pFanin, k )
            {
                // do not eliminate marked fanins
                if ( Abc_NodeIsTravIdCurrent(pFanin) )
                    continue;
                // do not eliminate constant nodes
                if ( !Abc_ObjIsNode(pFanin) || Abc_ObjFaninNum(pFanin) != 1 )
                    continue;
                // do not eliminate inverters into COs
                if ( Abc_ObjIsCo(pObj) && Abc_NodeIsInv(pFanin) )
                    continue;
                // do not eliminate buffers connecting PIs and POs 
//                if ( Abc_ObjIsCo(pObj) && Abc_ObjIsCi(Abc_ObjFanin0(pFanin)) )
//                    continue;
                fChanges = 1;
                Counter++;
                // update function of the node
                if ( Abc_NodeIsInv(pFanin) )
                    pObj->pData = Hop_Compose( pMan, (Hop_Obj_t *)pObj->pData, Hop_Not(Hop_IthVar(pMan, k)), k );
                // update the fanin
                Abc_ObjPatchFanin( pObj, pFanin, Abc_ObjFanin0(pFanin) );
                if ( Abc_ObjFanoutNum(pFanin) == 0 )
                    Abc_NtkDeleteObj(pFanin);            
            }
        }
    }
    if ( fVerbose )
        printf( "Removed %d single input nodes.\n", Counter );
    return Counter;
}
 
 

 
 
ABC_NAMESPACE_IMPL_END