diff options
Diffstat (limited to 'src/opt/nwk/nwkTiming.c')
| -rw-r--r-- | src/opt/nwk/nwkTiming.c | 894 |
1 files changed, 894 insertions, 0 deletions
diff --git a/src/opt/nwk/nwkTiming.c b/src/opt/nwk/nwkTiming.c new file mode 100644 index 00000000..9419c175 --- /dev/null +++ b/src/opt/nwk/nwkTiming.c @@ -0,0 +1,894 @@ +/**CFile**************************************************************** + + FileName [nwkTiming.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Logic network representation.] + + Synopsis [Manipulation of timing information.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: nwkTiming.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "nwk.h" + +ABC_NAMESPACE_IMPL_START + + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Cleans timing information for all nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Nwk_ManCleanTiming( Nwk_Man_t * pNtk ) +{ + Nwk_Obj_t * pObj; + int i; + Nwk_ManForEachObj( pNtk, pObj, i ) + { + pObj->tArrival = pObj->tSlack = 0.0; + pObj->tRequired = TIM_ETERNITY; + } +} + +/**Function************************************************************* + + Synopsis [Sorts the pins in the decreasing order of delays.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Nwk_ManDelayTraceSortPins( Nwk_Obj_t * pNode, int * pPinPerm, float * pPinDelays ) +{ + Nwk_Obj_t * pFanin; + int i, j, best_i, temp; + // start the trivial permutation and collect pin delays + Nwk_ObjForEachFanin( pNode, pFanin, i ) + { + pPinPerm[i] = i; + pPinDelays[i] = Nwk_ObjArrival(pFanin); + } + // selection sort the pins in the decreasible order of delays + // this order will match the increasing order of LUT input pins + for ( i = 0; i < Nwk_ObjFaninNum(pNode)-1; i++ ) + { + best_i = i; + for ( j = i+1; j < Nwk_ObjFaninNum(pNode); j++ ) + if ( pPinDelays[pPinPerm[j]] > pPinDelays[pPinPerm[best_i]] ) + best_i = j; + if ( best_i == i ) + continue; + temp = pPinPerm[i]; + pPinPerm[i] = pPinPerm[best_i]; + pPinPerm[best_i] = temp; + } + // verify + assert( Nwk_ObjFaninNum(pNode) == 0 || pPinPerm[0] < Nwk_ObjFaninNum(pNode) ); + for ( i = 1; i < Nwk_ObjFaninNum(pNode); i++ ) + { + assert( pPinPerm[i] < Nwk_ObjFaninNum(pNode) ); + assert( pPinDelays[pPinPerm[i-1]] >= pPinDelays[pPinPerm[i]] ); + } +} + +/**Function************************************************************* + + Synopsis [Sorts the pins in the decreasing order of delays.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Nwk_ManWhereIsPin( Nwk_Obj_t * pFanout, Nwk_Obj_t * pFanin, int * pPinPerm ) +{ + int i; + for ( i = 0; i < Nwk_ObjFaninNum(pFanout); i++ ) + if ( Nwk_ObjFanin(pFanout, pPinPerm[i]) == pFanin ) + return i; + return -1; +} + +/**Function************************************************************* + + Synopsis [Computes the arrival times for the given object.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Nwk_NodeComputeArrival( Nwk_Obj_t * pObj, int fUseSorting ) +{ + If_Lib_t * pLutLib = pObj->pMan->pLutLib; + int pPinPerm[32]; + float pPinDelays[32]; + Nwk_Obj_t * pFanin; + float tArrival, * pDelays; + int k; + assert( Nwk_ObjIsNode(pObj) || Nwk_ObjIsCi(pObj) || Nwk_ObjIsCo(pObj) ); + if ( Nwk_ObjIsCi(pObj) ) + return Nwk_ObjArrival(pObj); + if ( Nwk_ObjIsCo(pObj) ) + return Nwk_ObjArrival( Nwk_ObjFanin0(pObj) ); + tArrival = -TIM_ETERNITY; + if ( pLutLib == NULL ) + { + Nwk_ObjForEachFanin( pObj, pFanin, k ) + if ( tArrival < Nwk_ObjArrival(pFanin) + 1.0 ) + tArrival = Nwk_ObjArrival(pFanin) + 1.0; + } + else if ( !pLutLib->fVarPinDelays ) + { + pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pObj)]; + Nwk_ObjForEachFanin( pObj, pFanin, k ) + if ( tArrival < Nwk_ObjArrival(pFanin) + pDelays[0] ) + tArrival = Nwk_ObjArrival(pFanin) + pDelays[0]; + } + else + { + pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pObj)]; + if ( fUseSorting ) + { + Nwk_ManDelayTraceSortPins( pObj, pPinPerm, pPinDelays ); + Nwk_ObjForEachFanin( pObj, pFanin, k ) + if ( tArrival < Nwk_ObjArrival(Nwk_ObjFanin(pObj,pPinPerm[k])) + pDelays[k] ) + tArrival = Nwk_ObjArrival(Nwk_ObjFanin(pObj,pPinPerm[k])) + pDelays[k]; + } + else + { + Nwk_ObjForEachFanin( pObj, pFanin, k ) + if ( tArrival < Nwk_ObjArrival(pFanin) + pDelays[k] ) + tArrival = Nwk_ObjArrival(pFanin) + pDelays[k]; + } + } + if ( Nwk_ObjFaninNum(pObj) == 0 ) + tArrival = 0.0; + return tArrival; +} + +/**Function************************************************************* + + Synopsis [Computes the required times for the given node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Nwk_NodeComputeRequired( Nwk_Obj_t * pObj, int fUseSorting ) +{ + If_Lib_t * pLutLib = pObj->pMan->pLutLib; + int pPinPerm[32]; + float pPinDelays[32]; + Nwk_Obj_t * pFanout; + float tRequired, tDelay, * pDelays; + int k, iFanin; + assert( Nwk_ObjIsNode(pObj) || Nwk_ObjIsCi(pObj) || Nwk_ObjIsCo(pObj) ); + if ( Nwk_ObjIsCo(pObj) ) + return Nwk_ObjRequired(pObj); + tRequired = TIM_ETERNITY; + if ( pLutLib == NULL ) + { + Nwk_ObjForEachFanout( pObj, pFanout, k ) + { + tDelay = Nwk_ObjIsCo(pFanout)? 0.0 : 1.0; + if ( tRequired > Nwk_ObjRequired(pFanout) - tDelay ) + tRequired = Nwk_ObjRequired(pFanout) - tDelay; + } + } + else if ( !pLutLib->fVarPinDelays ) + { + Nwk_ObjForEachFanout( pObj, pFanout, k ) + { + pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pFanout)]; + tDelay = Nwk_ObjIsCo(pFanout)? 0.0 : pDelays[0]; + if ( tRequired > Nwk_ObjRequired(pFanout) - tDelay ) + tRequired = Nwk_ObjRequired(pFanout) - tDelay; + } + } + else + { + if ( fUseSorting ) + { + Nwk_ObjForEachFanout( pObj, pFanout, k ) + { + pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pFanout)]; + Nwk_ManDelayTraceSortPins( pFanout, pPinPerm, pPinDelays ); + iFanin = Nwk_ManWhereIsPin( pFanout, pObj, pPinPerm ); + assert( Nwk_ObjFanin(pFanout,pPinPerm[iFanin]) == pObj ); + tDelay = Nwk_ObjIsCo(pFanout)? 0.0 : pDelays[iFanin]; + if ( tRequired > Nwk_ObjRequired(pFanout) - tDelay ) + tRequired = Nwk_ObjRequired(pFanout) - tDelay; + } + } + else + { + Nwk_ObjForEachFanout( pObj, pFanout, k ) + { + pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pFanout)]; + iFanin = Nwk_ObjFindFanin( pFanout, pObj ); + assert( Nwk_ObjFanin(pFanout,iFanin) == pObj ); + tDelay = Nwk_ObjIsCo(pFanout)? 0.0 : pDelays[iFanin]; + if ( tRequired > Nwk_ObjRequired(pFanout) - tDelay ) + tRequired = Nwk_ObjRequired(pFanout) - tDelay; + } + } + } + return tRequired; +} + +/**Function************************************************************* + + Synopsis [Propagates the required times through the given node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Nwk_NodePropagateRequired( Nwk_Obj_t * pObj, int fUseSorting ) +{ + If_Lib_t * pLutLib = pObj->pMan->pLutLib; + int pPinPerm[32]; + float pPinDelays[32]; + Nwk_Obj_t * pFanin; + float tRequired = 0.0; // Suppress "might be used uninitialized" + float * pDelays; + int k; + assert( Nwk_ObjIsNode(pObj) ); + if ( pLutLib == NULL ) + { + tRequired = Nwk_ObjRequired(pObj) - (float)1.0; + Nwk_ObjForEachFanin( pObj, pFanin, k ) + if ( Nwk_ObjRequired(pFanin) > tRequired ) + Nwk_ObjSetRequired( pFanin, tRequired ); + } + else if ( !pLutLib->fVarPinDelays ) + { + pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pObj)]; + tRequired = Nwk_ObjRequired(pObj) - pDelays[0]; + Nwk_ObjForEachFanin( pObj, pFanin, k ) + if ( Nwk_ObjRequired(pFanin) > tRequired ) + Nwk_ObjSetRequired( pFanin, tRequired ); + } + else + { + pDelays = pLutLib->pLutDelays[Nwk_ObjFaninNum(pObj)]; + if ( fUseSorting ) + { + Nwk_ManDelayTraceSortPins( pObj, pPinPerm, pPinDelays ); + Nwk_ObjForEachFanin( pObj, pFanin, k ) + { + tRequired = Nwk_ObjRequired(pObj) - pDelays[k]; + if ( Nwk_ObjRequired(Nwk_ObjFanin(pObj,pPinPerm[k])) > tRequired ) + Nwk_ObjSetRequired( Nwk_ObjFanin(pObj,pPinPerm[k]), tRequired ); + } + } + else + { + Nwk_ObjForEachFanin( pObj, pFanin, k ) + { + tRequired = Nwk_ObjRequired(pObj) - pDelays[k]; + if ( Nwk_ObjRequired(pFanin) > tRequired ) + Nwk_ObjSetRequired( pFanin, tRequired ); + } + } + } + return tRequired; +} + +/**Function************************************************************* + + Synopsis [Computes the delay trace of the given network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +float Nwk_ManDelayTraceLut( Nwk_Man_t * pNtk ) +{ + Vec_Ptr_t * vObjs; + int fUseSorting = 1; + If_Lib_t * pLutLib = pNtk->pLutLib; + Vec_Ptr_t * vNodes; + Nwk_Obj_t * pObj; + float tArrival, tRequired, tSlack; + int i; + + // get the library + if ( pLutLib && pLutLib->LutMax < Nwk_ManGetFaninMax(pNtk) ) + { + printf( "The max LUT size (%d) is less than the max fanin count (%d).\n", + pLutLib->LutMax, Nwk_ManGetFaninMax(pNtk) ); + return -TIM_ETERNITY; + } + + // compute the reverse order of all objects + vNodes = Nwk_ManDfsReverse( pNtk ); + + // initialize the arrival times + Nwk_ManCleanTiming( pNtk ); + + // propagate arrival times + if ( pNtk->pManTime ) + Tim_ManIncrementTravId( pNtk->pManTime ); +// Nwk_ManForEachObj( pNtk, pObj, i ) + vObjs = Nwk_ManDfs( pNtk ); + Vec_PtrForEachEntry( Nwk_Obj_t *, vObjs, pObj, i ) + { + tArrival = Nwk_NodeComputeArrival( pObj, fUseSorting ); + if ( Nwk_ObjIsCi(pObj) && pNtk->pManTime ) + tArrival = Tim_ManGetCiArrival( pNtk->pManTime, pObj->PioId ); + if ( Nwk_ObjIsCo(pObj) && pNtk->pManTime ) + Tim_ManSetCoArrival( pNtk->pManTime, pObj->PioId, tArrival ); + Nwk_ObjSetArrival( pObj, tArrival ); + } + Vec_PtrFree( vObjs ); + + // get the latest arrival times + tArrival = -TIM_ETERNITY; + Nwk_ManForEachPo( pNtk, pObj, i ) + if ( tArrival < Nwk_ObjArrival(pObj) ) + tArrival = Nwk_ObjArrival(pObj); + + // initialize the required times + if ( pNtk->pManTime ) + { + Tim_ManIncrementTravId( pNtk->pManTime ); + Tim_ManSetCoRequiredAll( pNtk->pManTime, tArrival ); + } + else + { + Nwk_ManForEachCo( pNtk, pObj, i ) + Nwk_ObjSetRequired( pObj, tArrival ); + } + + // propagate the required times + Vec_PtrForEachEntry( Nwk_Obj_t *, vNodes, pObj, i ) + { + if ( Nwk_ObjIsNode(pObj) ) + { + Nwk_NodePropagateRequired( pObj, fUseSorting ); + } + else if ( Nwk_ObjIsCi(pObj) ) + { + if ( pNtk->pManTime ) + Tim_ManSetCiRequired( pNtk->pManTime, pObj->PioId, Nwk_ObjRequired(pObj) ); + } + else if ( Nwk_ObjIsCo(pObj) ) + { + if ( pNtk->pManTime ) + { + tRequired = Tim_ManGetCoRequired( pNtk->pManTime, pObj->PioId ); + Nwk_ObjSetRequired( pObj, tRequired ); + } + if ( Nwk_ObjRequired(Nwk_ObjFanin0(pObj)) > Nwk_ObjRequired(pObj) ) + Nwk_ObjSetRequired( Nwk_ObjFanin0(pObj), Nwk_ObjRequired(pObj) ); + } + + // set slack for this object + tSlack = Nwk_ObjRequired(pObj) - Nwk_ObjArrival(pObj); + assert( tSlack + 0.01 > 0.0 ); + Nwk_ObjSetSlack( pObj, tSlack < 0.0 ? 0.0 : tSlack ); + } + Vec_PtrFree( vNodes ); + return tArrival; +} + +/**Function************************************************************* + + Synopsis [Computes the arrival times for the given node.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Nwk_ManVerifyTiming( Nwk_Man_t * pNtk ) +{ + Nwk_Obj_t * pObj; + float tArrival, tRequired; + int i; + Nwk_ManForEachObj( pNtk, pObj, i ) + { + if ( Nwk_ObjIsCi(pObj) && Nwk_ObjFanoutNum(pObj) == 0 ) + continue; + tArrival = Nwk_NodeComputeArrival( pObj, 1 ); + tRequired = Nwk_NodeComputeRequired( pObj, 1 ); + if ( !Nwk_ManTimeEqual( tArrival, Nwk_ObjArrival(pObj), (float)0.01 ) ) + printf( "Nwk_ManVerifyTiming(): Object %d has different arrival time (%.2f) from computed (%.2f).\n", + pObj->Id, Nwk_ObjArrival(pObj), tArrival ); + if ( !Nwk_ManTimeEqual( tRequired, Nwk_ObjRequired(pObj), (float)0.01 ) ) + printf( "Nwk_ManVerifyTiming(): Object %d has different required time (%.2f) from computed (%.2f).\n", + pObj->Id, Nwk_ObjRequired(pObj), tRequired ); + } + return 1; +} + +/**Function************************************************************* + + Synopsis [Prints the delay trace for the given network.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Nwk_ManDelayTracePrint( Nwk_Man_t * pNtk ) +{ + If_Lib_t * pLutLib = pNtk->pLutLib; + Nwk_Obj_t * pNode; + int i, Nodes, * pCounters; + float tArrival, tDelta, nSteps, Num; + // get the library + if ( pLutLib && pLutLib->LutMax < Nwk_ManGetFaninMax(pNtk) ) + { + printf( "The max LUT size (%d) is less than the max fanin count (%d).\n", + pLutLib->LutMax, Nwk_ManGetFaninMax(pNtk) ); + return; + } + // decide how many steps + nSteps = pLutLib ? 20 : Nwk_ManLevelMax(pNtk); + pCounters = ABC_ALLOC( int, nSteps + 1 ); + memset( pCounters, 0, sizeof(int)*(nSteps + 1) ); + // perform delay trace + tArrival = Nwk_ManDelayTraceLut( pNtk ); + tDelta = tArrival / nSteps; + // count how many nodes have slack in the corresponding intervals + Nwk_ManForEachNode( pNtk, pNode, i ) + { + if ( Nwk_ObjFaninNum(pNode) == 0 ) + continue; + Num = Nwk_ObjSlack(pNode) / tDelta; + if ( Num > nSteps ) + continue; + assert( Num >=0 && Num <= nSteps ); + pCounters[(int)Num]++; + } + // print the results + printf( "Max delay = %6.2f. Delay trace using %s model:\n", tArrival, pLutLib? "LUT library" : "unit-delay" ); + Nodes = 0; + for ( i = 0; i < nSteps; i++ ) + { + Nodes += pCounters[i]; + printf( "%3d %s : %5d (%6.2f %%)\n", pLutLib? 5*(i+1) : i+1, + pLutLib? "%":"lev", Nodes, 100.0*Nodes/Nwk_ManNodeNum(pNtk) ); + } + ABC_FREE( pCounters ); +} + + +/**Function************************************************************* + + Synopsis [Inserts node into the queue of nodes sorted by level.] + + Description [The inserted node should not go before the current position + given by iCurrent. If the arrival times are computed, the nodes are sorted + in the increasing order of levels. If the required times are computed, + the nodes are sorted in the decreasing order of levels.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Nwk_NodeUpdateAddToQueue( Vec_Ptr_t * vQueue, Nwk_Obj_t * pObj, int iCurrent, int fArrival ) +{ + Nwk_Obj_t * pTemp1, * pTemp2; + int i; + Vec_PtrPush( vQueue, pObj ); + for ( i = Vec_PtrSize(vQueue) - 1; i > iCurrent + 1; i-- ) + { + pTemp1 = (Nwk_Obj_t *)vQueue->pArray[i]; + pTemp2 = (Nwk_Obj_t *)vQueue->pArray[i-1]; + if ( fArrival ) + { + if ( Nwk_ObjLevel(pTemp2) <= Nwk_ObjLevel(pTemp1) ) + break; + } + else + { + if ( Nwk_ObjLevel(pTemp2) >= Nwk_ObjLevel(pTemp1) ) + break; + } + vQueue->pArray[i-1] = pTemp1; + vQueue->pArray[i] = pTemp2; + } + // verification + for ( i = iCurrent + 1; i < Vec_PtrSize(vQueue) - 1; i++ ) + { + pTemp1 = (Nwk_Obj_t *)vQueue->pArray[i]; + pTemp2 = (Nwk_Obj_t *)vQueue->pArray[i+1]; + if ( fArrival ) + assert( Nwk_ObjLevel(pTemp1) <= Nwk_ObjLevel(pTemp2) ); + else + assert( Nwk_ObjLevel(pTemp1) >= Nwk_ObjLevel(pTemp2) ); + } +} + +/**Function************************************************************* + + Synopsis [Incrementally updates arrival times of the node.] + + Description [Supports variable-pin delay model and white-boxes.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Nwk_NodeUpdateArrival( Nwk_Obj_t * pObj ) +{ + Tim_Man_t * pManTime = pObj->pMan->pManTime; + Vec_Ptr_t * vQueue = pObj->pMan->vTemp; + Nwk_Obj_t * pTemp; + Nwk_Obj_t * pNext = NULL; // Suppress "might be used uninitialized" + float tArrival; + int iCur, k, iBox, iTerm1, nTerms; + assert( Nwk_ObjIsNode(pObj) ); + // verify the arrival time + tArrival = Nwk_NodeComputeArrival( pObj, 1 ); + assert( Nwk_ManTimeLess( tArrival, Nwk_ObjRequired(pObj), (float)0.01 ) ); + // initialize the queue with the node + Vec_PtrClear( vQueue ); + Vec_PtrPush( vQueue, pObj ); + pObj->MarkA = 1; + // process objects + if ( pManTime ) + Tim_ManIncrementTravId( pManTime ); + Vec_PtrForEachEntry( Nwk_Obj_t *, vQueue, pTemp, iCur ) + { + pTemp->MarkA = 0; + tArrival = Nwk_NodeComputeArrival( pTemp, 1 ); + if ( Nwk_ObjIsCi(pTemp) && pManTime ) + tArrival = Tim_ManGetCiArrival( pManTime, pTemp->PioId ); + if ( Nwk_ManTimeEqual( tArrival, Nwk_ObjArrival(pTemp), (float)0.01 ) ) + continue; + Nwk_ObjSetArrival( pTemp, tArrival ); + // add the fanouts to the queue + if ( Nwk_ObjIsCo(pTemp) ) + { + if ( pManTime ) + { + iBox = Tim_ManBoxForCo( pManTime, pTemp->PioId ); + if ( iBox >= 0 ) // this CO is an input of the box + { + // it may happen that a box-input (CO) was already marked as visited + // when some other box-input of the same box was visited - here we undo this + if ( Tim_ManIsCoTravIdCurrent( pManTime, pTemp->PioId ) ) + Tim_ManSetPreviousTravIdBoxInputs( pManTime, iBox ); + Tim_ManSetCoArrival( pManTime, pTemp->PioId, tArrival ); + Tim_ManSetCurrentTravIdBoxInputs( pManTime, iBox ); + iTerm1 = Tim_ManBoxOutputFirst( pManTime, iBox ); + nTerms = Tim_ManBoxOutputNum( pManTime, iBox ); + for ( k = 0; k < nTerms; k++ ) + { + pNext = Nwk_ManCi(pNext->pMan, iTerm1 + k); + if ( pNext->MarkA ) + continue; + Nwk_NodeUpdateAddToQueue( vQueue, pNext, iCur, 1 ); + pNext->MarkA = 1; + } + } + } + } + else + { + Nwk_ObjForEachFanout( pTemp, pNext, k ) + { + if ( pNext->MarkA ) + continue; + Nwk_NodeUpdateAddToQueue( vQueue, pNext, iCur, 1 ); + pNext->MarkA = 1; + } + } + } +} + +/**Function************************************************************* + + Synopsis [Incrementally updates required times of the node.] + + Description [Supports variable-pin delay model and white-boxes.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Nwk_NodeUpdateRequired( Nwk_Obj_t * pObj ) +{ + Tim_Man_t * pManTime = pObj->pMan->pManTime; + Vec_Ptr_t * vQueue = pObj->pMan->vTemp; + Nwk_Obj_t * pTemp; + Nwk_Obj_t * pNext = NULL; // Suppress "might be used uninitialized" + float tRequired; + int iCur, k, iBox, iTerm1, nTerms; + assert( Nwk_ObjIsNode(pObj) ); + // make sure the node's required time remained the same + tRequired = Nwk_NodeComputeRequired( pObj, 1 ); + assert( Nwk_ManTimeEqual( tRequired, Nwk_ObjRequired(pObj), (float)0.01 ) ); + // initialize the queue with the node's faninsa and the old node's fanins + Vec_PtrClear( vQueue ); + Nwk_ObjForEachFanin( pObj, pNext, k ) + { + if ( pNext->MarkA ) + continue; + Nwk_NodeUpdateAddToQueue( vQueue, pNext, -1, 0 ); + pNext->MarkA = 1; + } + // process objects + if ( pManTime ) + Tim_ManIncrementTravId( pManTime ); + Vec_PtrForEachEntry( Nwk_Obj_t *, vQueue, pTemp, iCur ) + { + pTemp->MarkA = 0; + tRequired = Nwk_NodeComputeRequired( pTemp, 1 ); + if ( Nwk_ObjIsCo(pTemp) && pManTime ) + tRequired = Tim_ManGetCoRequired( pManTime, pTemp->PioId ); + if ( Nwk_ManTimeEqual( tRequired, Nwk_ObjRequired(pTemp), (float)0.01 ) ) + continue; + Nwk_ObjSetRequired( pTemp, tRequired ); + // add the fanins to the queue + if ( Nwk_ObjIsCi(pTemp) ) + { + if ( pManTime ) + { + iBox = Tim_ManBoxForCi( pManTime, pTemp->PioId ); + if ( iBox >= 0 ) // this CI is an output of the box + { + // it may happen that a box-output (CI) was already marked as visited + // when some other box-output of the same box was visited - here we undo this + if ( Tim_ManIsCiTravIdCurrent( pManTime, pTemp->PioId ) ) + Tim_ManSetPreviousTravIdBoxOutputs( pManTime, iBox ); + Tim_ManSetCiRequired( pManTime, pTemp->PioId, tRequired ); + Tim_ManSetCurrentTravIdBoxOutputs( pManTime, iBox ); + iTerm1 = Tim_ManBoxInputFirst( pManTime, iBox ); + nTerms = Tim_ManBoxInputNum( pManTime, iBox ); + for ( k = 0; k < nTerms; k++ ) + { + pNext = Nwk_ManCo(pNext->pMan, iTerm1 + k); + if ( pNext->MarkA ) + continue; + Nwk_NodeUpdateAddToQueue( vQueue, pNext, iCur, 0 ); + pNext->MarkA = 1; + } + } + } + } + else + { + Nwk_ObjForEachFanin( pTemp, pNext, k ) + { + if ( pNext->MarkA ) + continue; + Nwk_NodeUpdateAddToQueue( vQueue, pNext, iCur, 0 ); + pNext->MarkA = 1; + } + } + } +} + +/**Function************************************************************* + + Synopsis [Computes the level of the node using its fanin levels.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Nwk_ObjLevelNew( Nwk_Obj_t * pObj ) +{ + Tim_Man_t * pManTime = pObj->pMan->pManTime; + Nwk_Obj_t * pFanin; + int i, iBox, iTerm1, nTerms, Level = 0; + if ( Nwk_ObjIsCi(pObj) || Nwk_ObjIsLatch(pObj) ) + { + if ( pManTime ) + { + iBox = Tim_ManBoxForCi( pManTime, pObj->PioId ); + if ( iBox >= 0 ) // this CI is an output of the box + { + iTerm1 = Tim_ManBoxInputFirst( pManTime, iBox ); + nTerms = Tim_ManBoxInputNum( pManTime, iBox ); + for ( i = 0; i < nTerms; i++ ) + { + pFanin = Nwk_ManCo(pObj->pMan, iTerm1 + i); + Level = Abc_MaxInt( Level, Nwk_ObjLevel(pFanin) ); + } + Level++; + } + } + return Level; + } + assert( Nwk_ObjIsNode(pObj) || Nwk_ObjIsCo(pObj) ); + Nwk_ObjForEachFanin( pObj, pFanin, i ) + Level = Abc_MaxInt( Level, Nwk_ObjLevel(pFanin) ); + return Level + (Nwk_ObjIsNode(pObj) && Nwk_ObjFaninNum(pObj) > 0); +} + +/**Function************************************************************* + + Synopsis [Incrementally updates level of the nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Nwk_ManUpdateLevel( Nwk_Obj_t * pObj ) +{ + Tim_Man_t * pManTime = pObj->pMan->pManTime; + Vec_Ptr_t * vQueue = pObj->pMan->vTemp; + Nwk_Obj_t * pTemp; + Nwk_Obj_t * pNext = NULL; // Suppress "might be used uninitialized" + int LevelNew, iCur, k, iBox, iTerm1, nTerms; + assert( Nwk_ObjIsNode(pObj) ); + // initialize the queue with the node + Vec_PtrClear( vQueue ); + Vec_PtrPush( vQueue, pObj ); + pObj->MarkA = 1; + // process objects + Vec_PtrForEachEntry( Nwk_Obj_t *, vQueue, pTemp, iCur ) + { + pTemp->MarkA = 0; + LevelNew = Nwk_ObjLevelNew( pTemp ); + if ( LevelNew == Nwk_ObjLevel(pTemp) ) + continue; + Nwk_ObjSetLevel( pTemp, LevelNew ); + // add the fanouts to the queue + if ( Nwk_ObjIsCo(pTemp) ) + { + if ( pManTime ) + { + iBox = Tim_ManBoxForCo( pManTime, pTemp->PioId ); + if ( iBox >= 0 ) // this is not a true PO + { + Tim_ManSetCurrentTravIdBoxInputs( pManTime, iBox ); + iTerm1 = Tim_ManBoxOutputFirst( pManTime, iBox ); + nTerms = Tim_ManBoxOutputNum( pManTime, iBox ); + for ( k = 0; k < nTerms; k++ ) + { + pNext = Nwk_ManCi(pNext->pMan, iTerm1 + k); + if ( pNext->MarkA ) + continue; + Nwk_NodeUpdateAddToQueue( vQueue, pNext, iCur, 1 ); + pNext->MarkA = 1; + } + } + } + } + else + { + Nwk_ObjForEachFanout( pTemp, pNext, k ) + { + if ( pNext->MarkA ) + continue; + Nwk_NodeUpdateAddToQueue( vQueue, pNext, iCur, 1 ); + pNext->MarkA = 1; + } + } + } +} + +/**Function************************************************************* + + Synopsis [Computes the level of the node using its fanin levels.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Nwk_ManVerifyLevel( Nwk_Man_t * pNtk ) +{ + Nwk_Obj_t * pObj; + int LevelNew, i; + Nwk_ManForEachObj( pNtk, pObj, i ) + { + assert( pObj->MarkA == 0 ); + LevelNew = Nwk_ObjLevelNew( pObj ); + if ( Nwk_ObjLevel(pObj) != LevelNew ) + { + printf( "Object %6d: Mismatch betweeh levels: Actual = %d. Correct = %d.\n", + i, Nwk_ObjLevel(pObj), LevelNew ); + } + } + return 1; +} + +/**Function************************************************************* + + Synopsis [Replaces the node and incrementally updates levels.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Nwk_ManUpdate( Nwk_Obj_t * pObj, Nwk_Obj_t * pObjNew, Vec_Vec_t * vLevels ) +{ + assert( pObj->pMan == pObjNew->pMan ); + assert( pObj != pObjNew ); + assert( Nwk_ObjFanoutNum(pObj) > 0 ); + assert( Nwk_ObjIsNode(pObj) && !Nwk_ObjIsCo(pObjNew) ); + // transfer fanouts to the old node + Nwk_ObjTransferFanout( pObj, pObjNew ); + // transfer the timing information + // (this is needed because updating level happens if the level has changed; + // when we set the old level, it will be recomputed by the level updating + // procedure, which will update level of other nodes if there is a difference) + pObjNew->Level = pObj->Level; + pObjNew->tArrival = pObj->tArrival; + pObjNew->tRequired = pObj->tRequired; + // update required times of the old fanins + pObj->tRequired = TIM_ETERNITY; + Nwk_NodeUpdateRequired( pObj ); + // remove the old node + Nwk_ManDeleteNode_rec( pObj ); + // update the information of the new node + Nwk_ManUpdateLevel( pObjNew ); + Nwk_NodeUpdateArrival( pObjNew ); + Nwk_NodeUpdateRequired( pObjNew ); +//Nwk_ManVerifyTiming( pObjNew->pMan ); +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + +ABC_NAMESPACE_IMPL_END + |