/**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 "base/abc/abc.h" #include "base/main/main.h" #include "proof/fraig/fraig.h" #include "misc/extra/extraBdd.h" ABC_NAMESPACE_IMPL_START //////////////////////////////////////////////////////////////////////// /// 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, 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 ); static void Abc_NodeConstantInput( Abc_Obj_t * pNode, Abc_Obj_t * pFanin, int fConst0 ); //////////////////////////////////////////////////////////////////////// /// 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 [] ***********************************************************************/ 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; } /**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, (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) ); } } /**Function************************************************************* Synopsis [Collects equivalence classes 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, (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; } /**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, 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 ); } } /**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_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 ); } /**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 [Removes dangling nodes.] Description [Returns the number of nodes removed.] SideEffects [] SeeAlso [] ***********************************************************************/ 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; } /**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( 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; } /**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 = (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); } /**Function************************************************************* Synopsis [Replaces the local function by its cofactor.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ 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 ); } /**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, (int (*)(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; } /**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; } /**Function************************************************************* Synopsis [Sweep to remove buffers and inverters.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ 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; } //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// ABC_NAMESPACE_IMPL_END