| /**CFile**************************************************************** |
| |
| FileName [nwkDfs.c] |
| |
| SystemName [ABC: Logic synthesis and verification system.] |
| |
| PackageName [Logic network representation.] |
| |
| Synopsis [DFS traversals.] |
| |
| Author [Alan Mishchenko] |
| |
| Affiliation [UC Berkeley] |
| |
| Date [Ver. 1.0. Started - June 20, 2005.] |
| |
| Revision [$Id: nwkDfs.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] |
| |
| ***********************************************************************/ |
| |
| #include "nwk.h" |
| |
| ABC_NAMESPACE_IMPL_START |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// DECLARATIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// FUNCTION DEFINITIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| /**Function************************************************************* |
| |
| Synopsis [Verifies that the objects are in a topo order.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Nwk_ManVerifyTopoOrder( Nwk_Man_t * pNtk ) |
| { |
| Nwk_Obj_t * pObj, * pNext; |
| int i, k, iBox, iTerm1, nTerms; |
| Nwk_ManIncrementTravId( pNtk ); |
| Nwk_ManForEachObj( pNtk, pObj, i ) |
| { |
| if ( Nwk_ObjIsNode(pObj) || Nwk_ObjIsCo(pObj) ) |
| { |
| Nwk_ObjForEachFanin( pObj, pNext, k ) |
| { |
| if ( !Nwk_ObjIsTravIdCurrent(pNext) ) |
| { |
| printf( "Node %d has fanin %d that is not in a topological order.\n", pObj->Id, pNext->Id ); |
| return 0; |
| } |
| } |
| } |
| else if ( Nwk_ObjIsCi(pObj) ) |
| { |
| if ( pNtk->pManTime ) |
| { |
| iBox = Tim_ManBoxForCi( pNtk->pManTime, pObj->PioId ); |
| if ( iBox >= 0 ) // this is not a true PI |
| { |
| iTerm1 = Tim_ManBoxInputFirst( pNtk->pManTime, iBox ); |
| nTerms = Tim_ManBoxInputNum( pNtk->pManTime, iBox ); |
| for ( k = 0; k < nTerms; k++ ) |
| { |
| pNext = Nwk_ManCo( pNtk, iTerm1 + k ); |
| if ( !Nwk_ObjIsTravIdCurrent(pNext) ) |
| { |
| printf( "Box %d has input %d that is not in a topological order.\n", iBox, pNext->Id ); |
| return 0; |
| } |
| } |
| } |
| } |
| } |
| else |
| assert( 0 ); |
| Nwk_ObjSetTravIdCurrent( pObj ); |
| } |
| return 1; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes the number of logic levels not counting PIs/POs.] |
| |
| Description [Assumes that white boxes have unit level.] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Nwk_ManLevelBackup( Nwk_Man_t * pNtk ) |
| { |
| Tim_Man_t * pManTimeUnit; |
| Nwk_Obj_t * pObj, * pFanin; |
| int i, k, LevelMax, Level; |
| assert( Nwk_ManVerifyTopoOrder(pNtk) ); |
| // clean the levels |
| Nwk_ManForEachObj( pNtk, pObj, i ) |
| Nwk_ObjSetLevel( pObj, 0 ); |
| // perform level computation |
| LevelMax = 0; |
| pManTimeUnit = pNtk->pManTime ? Tim_ManDup( pNtk->pManTime, 1 ) : NULL; |
| if ( pManTimeUnit ) |
| Tim_ManIncrementTravId( pManTimeUnit ); |
| Nwk_ManForEachObj( pNtk, pObj, i ) |
| { |
| if ( Nwk_ObjIsCi(pObj) ) |
| { |
| Level = pManTimeUnit? (int)Tim_ManGetCiArrival( pManTimeUnit, pObj->PioId ) : 0; |
| Nwk_ObjSetLevel( pObj, Level ); |
| } |
| else if ( Nwk_ObjIsCo(pObj) ) |
| { |
| Level = Nwk_ObjLevel( Nwk_ObjFanin0(pObj) ); |
| if ( pManTimeUnit ) |
| Tim_ManSetCoArrival( pManTimeUnit, pObj->PioId, (float)Level ); |
| Nwk_ObjSetLevel( pObj, Level ); |
| if ( LevelMax < Nwk_ObjLevel(pObj) ) |
| LevelMax = Nwk_ObjLevel(pObj); |
| } |
| else if ( Nwk_ObjIsNode(pObj) ) |
| { |
| Level = 0; |
| Nwk_ObjForEachFanin( pObj, pFanin, k ) |
| if ( Level < Nwk_ObjLevel(pFanin) ) |
| Level = Nwk_ObjLevel(pFanin); |
| Nwk_ObjSetLevel( pObj, Level + 1 ); |
| } |
| else |
| assert( 0 ); |
| } |
| // set the old timing manager |
| if ( pManTimeUnit ) |
| Tim_ManStop( pManTimeUnit ); |
| return LevelMax; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes the number of logic levels not counting PIs/POs.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Nwk_ManLevel_rec( Nwk_Obj_t * pObj ) |
| { |
| Tim_Man_t * pManTime = pObj->pMan->pManTime; |
| Nwk_Obj_t * pNext; |
| int i, iBox, iTerm1, nTerms, LevelMax = 0; |
| if ( Nwk_ObjIsTravIdCurrent( pObj ) ) |
| return; |
| Nwk_ObjSetTravIdCurrent( pObj ); |
| if ( Nwk_ObjIsCi(pObj) ) |
| { |
| if ( pManTime ) |
| { |
| iBox = Tim_ManBoxForCi( pManTime, pObj->PioId ); |
| if ( iBox >= 0 ) // this is not a true PI |
| { |
| iTerm1 = Tim_ManBoxInputFirst( pManTime, iBox ); |
| nTerms = Tim_ManBoxInputNum( pManTime, iBox ); |
| for ( i = 0; i < nTerms; i++ ) |
| { |
| pNext = Nwk_ManCo(pObj->pMan, iTerm1 + i); |
| Nwk_ManLevel_rec( pNext ); |
| if ( LevelMax < Nwk_ObjLevel(pNext) ) |
| LevelMax = Nwk_ObjLevel(pNext); |
| } |
| LevelMax++; |
| } |
| } |
| } |
| else if ( Nwk_ObjIsNode(pObj) || Nwk_ObjIsCo(pObj) ) |
| { |
| Nwk_ObjForEachFanin( pObj, pNext, i ) |
| { |
| Nwk_ManLevel_rec( pNext ); |
| if ( LevelMax < Nwk_ObjLevel(pNext) ) |
| LevelMax = Nwk_ObjLevel(pNext); |
| } |
| if ( Nwk_ObjIsNode(pObj) && Nwk_ObjFaninNum(pObj) > 0 ) |
| LevelMax++; |
| } |
| else |
| assert( 0 ); |
| Nwk_ObjSetLevel( pObj, LevelMax ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes the number of logic levels not counting PIs/POs.] |
| |
| Description [Does not assume that the objects are in a topo order.] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Nwk_ManLevel( Nwk_Man_t * pNtk ) |
| { |
| Nwk_Obj_t * pObj; |
| int i, LevelMax = 0; |
| Nwk_ManForEachObj( pNtk, pObj, i ) |
| Nwk_ObjSetLevel( pObj, 0 ); |
| Nwk_ManIncrementTravId( pNtk ); |
| Nwk_ManForEachPo( pNtk, pObj, i ) |
| { |
| Nwk_ManLevel_rec( pObj ); |
| if ( LevelMax < Nwk_ObjLevel(pObj) ) |
| LevelMax = Nwk_ObjLevel(pObj); |
| } |
| Nwk_ManForEachCi( pNtk, pObj, i ) |
| { |
| Nwk_ManLevel_rec( pObj ); |
| if ( LevelMax < Nwk_ObjLevel(pObj) ) |
| LevelMax = Nwk_ObjLevel(pObj); |
| } |
| return LevelMax; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes the number of logic levels not counting PIs/POs.] |
| |
| Description [Does not assume that the objects are in a topo order.] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Nwk_ManLevelMax( Nwk_Man_t * pNtk ) |
| { |
| Nwk_Obj_t * pObj; |
| int i, LevelMax = 0; |
| Nwk_ManForEachPo( pNtk, pObj, i ) |
| if ( LevelMax < Nwk_ObjLevel(pObj) ) |
| LevelMax = Nwk_ObjLevel(pObj); |
| return LevelMax; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Returns the array of objects in the AIG manager ordered by level.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Vec_t * Nwk_ManLevelize( Nwk_Man_t * pNtk ) |
| { |
| Nwk_Obj_t * pObj; |
| Vec_Vec_t * vLevels; |
| int nLevels, i; |
| assert( Nwk_ManVerifyLevel(pNtk) ); |
| nLevels = Nwk_ManLevelMax( pNtk ); |
| vLevels = Vec_VecStart( nLevels + 1 ); |
| Nwk_ManForEachNode( pNtk, pObj, i ) |
| { |
| assert( Nwk_ObjLevel(pObj) <= nLevels ); |
| Vec_VecPush( vLevels, Nwk_ObjLevel(pObj), pObj ); |
| } |
| return vLevels; |
| } |
| |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Performs DFS for one node.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Nwk_ManDfs_rec( Nwk_Obj_t * pObj, Vec_Ptr_t * vNodes ) |
| { |
| Nwk_Obj_t * pNext; |
| int i; |
| if ( Nwk_ObjIsTravIdCurrent( pObj ) ) |
| return; |
| Nwk_ObjSetTravIdCurrent( pObj ); |
| Nwk_ObjForEachFanin( pObj, pNext, i ) |
| Nwk_ManDfs_rec( pNext, vNodes ); |
| Vec_PtrPush( vNodes, pObj ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Returns the DFS ordered array of all objects except latches.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Ptr_t * Nwk_ManDfs( Nwk_Man_t * pNtk ) |
| { |
| Vec_Ptr_t * vNodes; |
| Nwk_Obj_t * pObj; |
| int i; |
| Nwk_ManIncrementTravId( pNtk ); |
| vNodes = Vec_PtrAlloc( 100 ); |
| Nwk_ManForEachObj( pNtk, pObj, i ) |
| { |
| if ( Nwk_ObjIsCi(pObj) ) |
| { |
| Nwk_ObjSetTravIdCurrent( pObj ); |
| Vec_PtrPush( vNodes, pObj ); |
| } |
| else if ( Nwk_ObjIsCo(pObj) ) |
| Nwk_ManDfs_rec( pObj, vNodes ); |
| } |
| return vNodes; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Performs DFS for one node.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Nwk_ManDfsNodes_rec( Nwk_Obj_t * pObj, Vec_Ptr_t * vNodes ) |
| { |
| Nwk_Obj_t * pNext; |
| int i; |
| if ( Nwk_ObjIsTravIdCurrent( pObj ) ) |
| return; |
| Nwk_ObjSetTravIdCurrent( pObj ); |
| if ( Nwk_ObjIsCi(pObj) ) |
| return; |
| assert( Nwk_ObjIsNode(pObj) ); |
| Nwk_ObjForEachFanin( pObj, pNext, i ) |
| Nwk_ManDfsNodes_rec( pNext, vNodes ); |
| Vec_PtrPush( vNodes, pObj ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Returns the set of internal nodes rooted in the given nodes.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Ptr_t * Nwk_ManDfsNodes( Nwk_Man_t * pNtk, Nwk_Obj_t ** ppNodes, int nNodes ) |
| { |
| Vec_Ptr_t * vNodes; |
| int i; |
| // set the traversal ID |
| Nwk_ManIncrementTravId( pNtk ); |
| // start the array of nodes |
| vNodes = Vec_PtrAlloc( 100 ); |
| // go through the PO nodes and call for each of them |
| for ( i = 0; i < nNodes; i++ ) |
| if ( Nwk_ObjIsCo(ppNodes[i]) ) |
| Nwk_ManDfsNodes_rec( Nwk_ObjFanin0(ppNodes[i]), vNodes ); |
| else |
| Nwk_ManDfsNodes_rec( ppNodes[i], vNodes ); |
| return vNodes; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Performs DFS for one node.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Nwk_ManDfsReverse_rec( Nwk_Obj_t * pObj, Vec_Ptr_t * vNodes ) |
| { |
| Nwk_Obj_t * pNext; |
| int i, iBox, iTerm1, nTerms; |
| if ( Nwk_ObjIsTravIdCurrent( pObj ) ) |
| return; |
| Nwk_ObjSetTravIdCurrent( pObj ); |
| if ( Nwk_ObjIsCo(pObj) ) |
| { |
| if ( pObj->pMan->pManTime ) |
| { |
| iBox = Tim_ManBoxForCo( pObj->pMan->pManTime, pObj->PioId ); |
| if ( iBox >= 0 ) // this is not a true PO |
| { |
| iTerm1 = Tim_ManBoxOutputFirst( pObj->pMan->pManTime, iBox ); |
| nTerms = Tim_ManBoxOutputNum( pObj->pMan->pManTime, iBox ); |
| for ( i = 0; i < nTerms; i++ ) |
| { |
| pNext = Nwk_ManCi(pObj->pMan, iTerm1 + i); |
| Nwk_ManDfsReverse_rec( pNext, vNodes ); |
| } |
| } |
| } |
| } |
| else if ( Nwk_ObjIsNode(pObj) || Nwk_ObjIsCi(pObj) ) |
| { |
| Nwk_ObjForEachFanout( pObj, pNext, i ) |
| Nwk_ManDfsReverse_rec( pNext, vNodes ); |
| } |
| else |
| assert( 0 ); |
| Vec_PtrPush( vNodes, pObj ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Returns the DFS ordered array of all objects except latches.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Ptr_t * Nwk_ManDfsReverse( Nwk_Man_t * pNtk ) |
| { |
| Vec_Ptr_t * vNodes; |
| Nwk_Obj_t * pObj; |
| int i; |
| Nwk_ManIncrementTravId( pNtk ); |
| vNodes = Vec_PtrAlloc( 100 ); |
| Nwk_ManForEachPi( pNtk, pObj, i ) |
| Nwk_ManDfsReverse_rec( pObj, vNodes ); |
| // add nodes without fanins |
| Nwk_ManForEachNode( pNtk, pObj, i ) |
| if ( Nwk_ObjFaninNum(pObj) == 0 && !Nwk_ObjIsTravIdCurrent(pObj) ) |
| Vec_PtrPush( vNodes, pObj ); |
| return vNodes; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Performs DFS for one node.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Nwk_ManSupportNodes_rec( Nwk_Obj_t * pNode, Vec_Ptr_t * vNodes ) |
| { |
| Nwk_Obj_t * pFanin; |
| int i; |
| // if this node is already visited, skip |
| if ( Nwk_ObjIsTravIdCurrent( pNode ) ) |
| return; |
| // mark the node as visited |
| Nwk_ObjSetTravIdCurrent( pNode ); |
| // collect the CI |
| if ( Nwk_ObjIsCi(pNode) ) |
| { |
| Vec_PtrPush( vNodes, pNode ); |
| return; |
| } |
| assert( Nwk_ObjIsNode( pNode ) ); |
| // visit the transitive fanin of the node |
| Nwk_ObjForEachFanin( pNode, pFanin, i ) |
| Nwk_ManSupportNodes_rec( pFanin, vNodes ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Returns the set of CI nodes in the support of the given nodes.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Ptr_t * Nwk_ManSupportNodes( Nwk_Man_t * pNtk, Nwk_Obj_t ** ppNodes, int nNodes ) |
| { |
| Vec_Ptr_t * vNodes; |
| int i; |
| // set the traversal ID |
| Nwk_ManIncrementTravId( pNtk ); |
| // start the array of nodes |
| vNodes = Vec_PtrAlloc( 100 ); |
| // go through the PO nodes and call for each of them |
| for ( i = 0; i < nNodes; i++ ) |
| if ( Nwk_ObjIsCo(ppNodes[i]) ) |
| Nwk_ManSupportNodes_rec( Nwk_ObjFanin0(ppNodes[i]), vNodes ); |
| else |
| Nwk_ManSupportNodes_rec( ppNodes[i], vNodes ); |
| return vNodes; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computes the sum total of supports of all outputs.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Nwk_ManSupportSum( Nwk_Man_t * pNtk ) |
| { |
| Vec_Ptr_t * vSupp; |
| Nwk_Obj_t * pObj; |
| int i, nTotalSupps = 0; |
| Nwk_ManForEachCo( pNtk, pObj, i ) |
| { |
| vSupp = Nwk_ManSupportNodes( pNtk, &pObj, 1 ); |
| nTotalSupps += Vec_PtrSize( vSupp ); |
| Vec_PtrFree( vSupp ); |
| } |
| printf( "Total supports = %d.\n", nTotalSupps ); |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Dereferences the node's MFFC.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Nwk_ObjDeref_rec( Nwk_Obj_t * pNode ) |
| { |
| Nwk_Obj_t * pFanin; |
| int i, Counter = 1; |
| if ( Nwk_ObjIsCi(pNode) ) |
| return 0; |
| Nwk_ObjForEachFanin( pNode, pFanin, i ) |
| { |
| assert( pFanin->nFanouts > 0 ); |
| if ( --pFanin->nFanouts == 0 ) |
| Counter += Nwk_ObjDeref_rec( pFanin ); |
| } |
| return Counter; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [References the node's MFFC.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Nwk_ObjRef_rec( Nwk_Obj_t * pNode ) |
| { |
| Nwk_Obj_t * pFanin; |
| int i, Counter = 1; |
| if ( Nwk_ObjIsCi(pNode) ) |
| return 0; |
| Nwk_ObjForEachFanin( pNode, pFanin, i ) |
| { |
| if ( pFanin->nFanouts++ == 0 ) |
| Counter += Nwk_ObjRef_rec( pFanin ); |
| } |
| return Counter; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Collects the internal and boundary nodes in the derefed MFFC.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Nwk_ObjMffcLabel_rec( Nwk_Obj_t * pNode, int fTopmost ) |
| { |
| Nwk_Obj_t * pFanin; |
| int i; |
| // add to the new support nodes |
| if ( !fTopmost && (Nwk_ObjIsCi(pNode) || pNode->nFanouts > 0) ) |
| return; |
| // skip visited nodes |
| if ( Nwk_ObjIsTravIdCurrent(pNode) ) |
| return; |
| Nwk_ObjSetTravIdCurrent(pNode); |
| // recur on the children |
| Nwk_ObjForEachFanin( pNode, pFanin, i ) |
| Nwk_ObjMffcLabel_rec( pFanin, 0 ); |
| // collect the internal node |
| // printf( "%d ", pNode->Id ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Collects the internal nodes of the MFFC limited by cut.] |
| |
| Description [] |
| |
| SideEffects [Increments the trav ID and marks visited nodes.] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Nwk_ObjMffcLabel( Nwk_Obj_t * pNode ) |
| { |
| int Count1, Count2; |
| // dereference the node |
| Count1 = Nwk_ObjDeref_rec( pNode ); |
| // collect the nodes inside the MFFC |
| Nwk_ManIncrementTravId( pNode->pMan ); |
| Nwk_ObjMffcLabel_rec( pNode, 1 ); |
| // reference it back |
| Count2 = Nwk_ObjRef_rec( pNode ); |
| assert( Count1 == Count2 ); |
| return Count1; |
| } |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// END OF FILE /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
| ABC_NAMESPACE_IMPL_END |
| |
