abcSweep.c File Reference

#include "base/abc/abc.h"
#include "base/main/main.h"
#include "proof/fraig/fraig.h"

Include dependency graph for abcSweep.c:

Go to the source code of this file.

Functions
int	Abc_NtkFraigSweep (Abc_Ntk_t *pNtk, int fUseInv, int fExdc, int fVerbose, int fVeryVerbose)
	FUNCTION DEFINITIONS ///.
int	Abc_NtkCleanup (Abc_Ntk_t *pNtk, int fVerbose)
int	Abc_NtkCleanupNodes (Abc_Ntk_t *pNtk, Vec_Ptr_t *vRoots, int fVerbose)
int	Abc_NtkSweep (Abc_Ntk_t *pNtk, int fVerbose)
int	Abc_NodeRemoveNonCurrentObjects (Abc_Ntk_t *pNtk)
void	Abc_NtkSetTravId_rec (Abc_Obj_t *pObj)
int	Abc_NtkCheckConstant_rec (Abc_Obj_t *pObj)
int	Abc_NtkLatchSweep (Abc_Ntk_t *pNtk)
int	Abc_NtkReplaceAutonomousLogic (Abc_Ntk_t *pNtk)
int	Abc_NtkCleanupSeq (Abc_Ntk_t *pNtk, int fLatchSweep, int fAutoSweep, int fVerbose)
int	Abc_NtkSweepBufsInvs (Abc_Ntk_t *pNtk, int fVerbose)

Function Documentation

Abc_NodeRemoveNonCurrentObjects()

int Abc_NodeRemoveNonCurrentObjects

(

Abc_Ntk_t *

pNtk

)

Function*************************************************************

Synopsis [Removes all objects whose trav ID is not current.]

Description []

SideEffects []

SeeAlso []

Definition at line 708 of file abcSweep.c.

{
    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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_NtkCheckConstant_rec()

int Abc_NtkCheckConstant_rec

(

Abc_Obj_t *

pObj

)

Function*************************************************************

Synopsis [Check if the fanin of this latch is a constant.]

Description [Returns 0/1 if constant; -1 if not a constant.]

SideEffects []

SeeAlso []

Definition at line 768 of file abcSweep.c.

{
    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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_NtkCleanup()

int Abc_NtkCleanup	(	Abc_Ntk_t *	pNtk,
		int	fVerbose )

Function*************************************************************

Synopsis [Removes dangling nodes.]

Description [Returns the number of nodes removed.]

SideEffects []

SeeAlso []

Definition at line 478 of file abcSweep.c.

{
    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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_NtkCleanupNodes()

int Abc_NtkCleanupNodes	(	Abc_Ntk_t *	pNtk,
		Vec_Ptr_t *	vRoots,
		int	fVerbose )

Function*************************************************************

Synopsis [Removes dangling nodes.]

Description [Returns the number of nodes removed.]

SideEffects []

SeeAlso []

Definition at line 503 of file abcSweep.c.

{
    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;
}

Here is the call graph for this function:

Abc_NtkCleanupSeq()

int Abc_NtkCleanupSeq	(	Abc_Ntk_t *	pNtk,
		int	fLatchSweep,
		int	fAutoSweep,
		int	fVerbose )

Function*************************************************************

Synopsis [Sequential cleanup.]

Description [Performs three tasks:

• Removes logic that does not feed into POs.
• Removes latches driven by constant values equal to the initial state.
• Replaces the autonomous components by additional PI variables.]

SideEffects []

SeeAlso []

Definition at line 919 of file abcSweep.c.

{
    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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_NtkFraigSweep()

int Abc_NtkFraigSweep	(	Abc_Ntk_t *	pNtk,
		int	fUseInv,
		int	fExdc,
		int	fVerbose,
		int	fVeryVerbose )

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis [Sweping functionally equivalence nodes.]

Description [Removes gates with equivalent functionality. Works for both technology-independent and mapped networks. If the flag is set, allows adding inverters at the gate outputs.]

SideEffects []

SeeAlso []

Definition at line 62 of file abcSweep.c.

{
    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;
}

Here is the call graph for this function:

Abc_NtkLatchSweep()

int Abc_NtkLatchSweep

(

Abc_Ntk_t *

pNtk

)

Function*************************************************************

Synopsis [Removes redundant latches.]

Description [The redundant latches are of two types:

• Latches fed by a constant which matches the init value of the latch.
• Latches fed by a constant which does not match the init value of the latch can be all replaced by one latch.]

SideEffects []

SeeAlso []

Definition at line 812 of file abcSweep.c.

{
    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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_NtkReplaceAutonomousLogic()

int Abc_NtkReplaceAutonomousLogic

(

Abc_Ntk_t *

pNtk

)

Function*************************************************************

Synopsis [Replaces autonumnous logic by free inputs.]

Description [Assumes that non-autonomous logic is marked with the current ID.]

SideEffects []

SeeAlso []

Definition at line 862 of file abcSweep.c.

{
    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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_NtkSetTravId_rec()

void Abc_NtkSetTravId_rec

(

Abc_Obj_t *

pObj

)

Function*************************************************************

Synopsis [Check if the fanin of this latch is a constant.]

Description [Returns 0/1 if constant; -1 if not a constant.]

SideEffects []

SeeAlso []

Definition at line 748 of file abcSweep.c.

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

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_NtkSweep()

int Abc_NtkSweep	(	Abc_Ntk_t *	pNtk,
		int	fVerbose )

Definition at line 692 of file abcSweep.c.

{ return 1; }

Here is the caller graph for this function:

Abc_NtkSweepBufsInvs()

int Abc_NtkSweepBufsInvs	(	Abc_Ntk_t *	pNtk,
		int	fVerbose )

Function*************************************************************

Synopsis [Sweep to remove buffers and inverters.]

Description []

SideEffects []

SeeAlso []

Definition at line 969 of file abcSweep.c.

{
    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;
}

Here is the call graph for this function: