diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2007-09-30 08:01:00 -0700 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2007-09-30 08:01:00 -0700 |
commit | e54d9691616b9a0326e2fdb3156bb4eeb8abfcd7 (patch) | |
tree | de3ffe87c3e17950351e3b7d97fa18318bd5ea9a /src/base/abci/abcSweep.c | |
parent | 7d7e60f2dc84393cd4c5db22d2eaf7b1fb1a79b2 (diff) | |
download | abc-e54d9691616b9a0326e2fdb3156bb4eeb8abfcd7.tar.gz abc-e54d9691616b9a0326e2fdb3156bb4eeb8abfcd7.tar.bz2 abc-e54d9691616b9a0326e2fdb3156bb4eeb8abfcd7.zip |
Version abc70930
Diffstat (limited to 'src/base/abci/abcSweep.c')
-rw-r--r-- | src/base/abci/abcSweep.c | 948 |
1 files changed, 0 insertions, 948 deletions
diff --git a/src/base/abci/abcSweep.c b/src/base/abci/abcSweep.c deleted file mode 100644 index 1ae8745b..00000000 --- a/src/base/abci/abcSweep.c +++ /dev/null @@ -1,948 +0,0 @@ -/**CFile**************************************************************** - - FileName [abcDsd.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [Network and node package.] - - Synopsis [Technology dependent sweep.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - June 20, 2005.] - - Revision [$Id: abcDsd.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "abc.h" -#include "fraig.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -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, bool 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 ); -static void Abc_NodeConstantInput( Abc_Obj_t * pNode, Abc_Obj_t * pFanin, bool fConst0 ); -static void Abc_NodeComplementInput( Abc_Obj_t * pNode, Abc_Obj_t * pFanin ); - -//////////////////////////////////////////////////////////////////////// -/// 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 [] - -***********************************************************************/ -bool 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 = pObj->pData; - } - // derive the AIG - pNtkAig = Abc_NtkStrash( pNtk, 0, 1, 0 ); - // reconstruct gate assignments - if ( fUseTrick ) - { - extern void * Abc_FrameReadLibGen(); - Hop_ManStop( 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 ); - pMan = 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; -} - -/**Function************************************************************* - - Synopsis [Sweep the network using EXDC.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -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, 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, Abc_ObjIsComplement(pNodeAig) ); - } -} - -/**Function************************************************************* - - Synopsis [Collects equivalence classses of node in the network.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -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, 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; -} - - -/**Function************************************************************* - - Synopsis [Transforms the network using the equivalence relation on nodes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Abc_NtkFraigTransform( Abc_Ntk_t * pNtk, stmm_table * tEquiv, int fUseInv, bool 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 ); - 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 ); - } -} - - -/**Function************************************************************* - - Synopsis [Transforms the list of one-phase equivalent nodes.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -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_NodeReadArrival(pNodeMin)->Worst; - Arrival2 = Abc_NodeReadArrival(pNode )->Worst; -// 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_NodeReadArrival(pNodeMin)->Worst; - Arrival2 = Abc_NodeReadArrival(pNode )->Worst; -// 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 ); -} - -/**Function************************************************************* - - Synopsis [Process one equivalence class of nodes.] - - Description [This function does not remove the nodes. It only switches - around the connections.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -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 ); -} - - -/**Function************************************************************* - - Synopsis [Returns the number of literals saved if this node becomes useless.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Abc_NodeDroppingCost( Abc_Obj_t * pNode ) -{ - return 1; -} - - - - - -/**Function************************************************************* - - Synopsis [Removes dangling nodes.] - - Description [Returns the number of nodes removed.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -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; -} - -/**Function************************************************************* - - Synopsis [Preserves the nodes collected in the array.] - - Description [Returns the number of nodes removed.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -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( 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( vNodes, pNode, i ) - pNode->fMarkA = 0; - // check - if ( !Abc_NtkCheck( pNtk ) ) - printf( "Abc_NtkCleanup: The network check has failed.\n" ); - return Counter; -} - - - - -/**Function************************************************************* - - Synopsis [Tranditional sweep of the network.] - - Description [Propagates constant and single-input node, removes dangling nodes.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -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 = 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); -} - - -/**Function************************************************************* - - Synopsis [Replaces the local function by its cofactor.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Abc_NodeConstantInput( Abc_Obj_t * pNode, Abc_Obj_t * pFanin, bool fConst0 ) -{ - DdManager * dd = 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 = pNode->pData, bVar ); Cudd_Ref( pNode->pData ); - Cudd_RecursiveDeref( dd, bTemp ); -} - -/**Function************************************************************* - - Synopsis [Changes the polarity of one fanin.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Abc_NodeComplementInput( Abc_Obj_t * pNode, Abc_Obj_t * pFanin ) -{ - DdManager * dd = pNode->pNtk->pManFunc; - DdNode * bVar, * bCof0, * bCof1; - 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_bddIthVar( dd, iFanin ); - bCof0 = Cudd_Cofactor( dd, pNode->pData, Cudd_Not(bVar) ); Cudd_Ref( bCof0 ); - bCof1 = Cudd_Cofactor( dd, pNode->pData, bVar ); Cudd_Ref( bCof1 ); - Cudd_RecursiveDeref( dd, pNode->pData ); - pNode->pData = Cudd_bddIte( dd, bVar, bCof0, bCof1 ); Cudd_Ref( pNode->pData ); - Cudd_RecursiveDeref( dd, bCof0 ); - Cudd_RecursiveDeref( dd, bCof1 ); -} - - - -/**Function************************************************************* - - Synopsis [Removes all objects whose trav ID is not current.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -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; -} - -/**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 [] - -***********************************************************************/ -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) ); -} - -/**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 [] - -***********************************************************************/ -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; -} - -/**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 [] - -***********************************************************************/ -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; -} - -/**Function************************************************************* - - Synopsis [Replaces autonumnous logic by free inputs.] - - Description [Assumes that non-autonomous logic is marked with - the current ID.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -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, Abc_ObjPointerCompare ); - // replace these nodes by the PIs - Vec_PtrForEachEntry( 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; -} - -/**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 [] - -***********************************************************************/ -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; -} - - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - |