| /**CFile**************************************************************** | |
| FileName [nwkFlow.c] | |
| SystemName [ABC: Logic synthesis and verification system.] | |
| PackageName [Netlist representation.] | |
| Synopsis [Max-flow/min-cut computation.] | |
| Author [Alan Mishchenko] | |
| Affiliation [UC Berkeley] | |
| Date [Ver. 1.0. Started - June 20, 2005.] | |
| Revision [$Id: nwkFlow.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] | |
| ***********************************************************************/ | |
| #include "nwk.h" | |
| ABC_NAMESPACE_IMPL_START | |
| /* | |
| This code is based on the papers: | |
| A. Hurst, A. Mishchenko, and R. Brayton, "Fast minimum-register retiming | |
| via binary maximum-flow", Proc. FMCAD '07, pp. 181-187. | |
| A. Hurst, A. Mishchenko, and R. Brayton, "Scalable min-area retiming | |
| under simultaneous delay and initial state constraints". Proc. DAC'08. | |
| */ | |
| //////////////////////////////////////////////////////////////////////// | |
| /// DECLARATIONS /// | |
| //////////////////////////////////////////////////////////////////////// | |
| // predecessors | |
| static inline Nwk_Obj_t * Nwk_ObjPred( Nwk_Obj_t * pObj ) { return (Nwk_Obj_t *)pObj->pCopy; } | |
| static inline int Nwk_ObjSetPred( Nwk_Obj_t * pObj, Nwk_Obj_t * p ) { pObj->pCopy = p; return 1; } | |
| // sink | |
| static inline int Nwk_ObjIsSink( Nwk_Obj_t * pObj ) { return pObj->MarkA; } | |
| static inline void Nwk_ObjSetSink( Nwk_Obj_t * pObj ) { pObj->MarkA = 1; } | |
| // flow | |
| static inline int Nwk_ObjHasFlow( Nwk_Obj_t * pObj ) { return pObj->MarkB; } | |
| static inline void Nwk_ObjSetFlow( Nwk_Obj_t * pObj ) { pObj->MarkB = 1; } | |
| static inline void Nwk_ObjClearFlow( Nwk_Obj_t * pObj ) { pObj->MarkB = 0; } | |
| // representation of visited nodes | |
| // pObj->TravId < pNtk->nTravIds-2 --- not visited | |
| // pObj->TravId == pNtk->nTravIds-2 --- visited bot only | |
| // pObj->TravId == pNtk->nTravIds-1 --- visited top only | |
| // pObj->TravId == pNtk->nTravIds --- visited bot and top | |
| static inline int Nwk_ObjVisitedBotOnly( Nwk_Obj_t * pObj ) | |
| { | |
| return pObj->TravId == pObj->pMan->nTravIds - 2; | |
| } | |
| static inline int Nwk_ObjVisitedBot( Nwk_Obj_t * pObj ) | |
| { | |
| return pObj->TravId == pObj->pMan->nTravIds - 2 || pObj->TravId == pObj->pMan->nTravIds; | |
| } | |
| static inline int Nwk_ObjVisitedTop( Nwk_Obj_t * pObj ) | |
| { | |
| return pObj->TravId == pObj->pMan->nTravIds - 1 || pObj->TravId == pObj->pMan->nTravIds; | |
| } | |
| static inline void Nwk_ObjSetVisitedBot( Nwk_Obj_t * pObj ) | |
| { | |
| if ( pObj->TravId < pObj->pMan->nTravIds - 2 ) | |
| pObj->TravId = pObj->pMan->nTravIds - 2; | |
| else if ( pObj->TravId == pObj->pMan->nTravIds - 1 ) | |
| pObj->TravId = pObj->pMan->nTravIds; | |
| else | |
| assert( 0 ); | |
| } | |
| static inline void Nwk_ObjSetVisitedTop( Nwk_Obj_t * pObj ) | |
| { | |
| if ( pObj->TravId < pObj->pMan->nTravIds - 2 ) | |
| pObj->TravId = pObj->pMan->nTravIds - 1; | |
| else if ( pObj->TravId == pObj->pMan->nTravIds - 2 ) | |
| pObj->TravId = pObj->pMan->nTravIds; | |
| else | |
| assert( 0 ); | |
| } | |
| static inline void Nwk_ManIncrementTravIdFlow( Nwk_Man_t * pMan ) | |
| { | |
| Nwk_ManIncrementTravId( pMan ); | |
| Nwk_ManIncrementTravId( pMan ); | |
| Nwk_ManIncrementTravId( pMan ); | |
| } | |
| static int Nwk_ManPushForwardTop_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred ); | |
| static int Nwk_ManPushForwardBot_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred ); | |
| static int Nwk_ManPushBackwardTop_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred ); | |
| static int Nwk_ManPushBackwardBot_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred ); | |
| //////////////////////////////////////////////////////////////////////// | |
| /// FUNCTION DEFINITIONS /// | |
| //////////////////////////////////////////////////////////////////////// | |
| /**Function************************************************************* | |
| Synopsis [Marks TFI of the node.] | |
| Description [] | |
| SideEffects [] | |
| SeeAlso [] | |
| ***********************************************************************/ | |
| void Nwk_ManMarkTfiCone_rec( Nwk_Obj_t * pObj ) | |
| { | |
| Nwk_Obj_t * pNext; | |
| int i; | |
| if ( pObj->MarkA ) | |
| return; | |
| pObj->MarkA = 1; | |
| Nwk_ObjForEachFanin( pObj, pNext, i ) | |
| Nwk_ManMarkTfiCone_rec( pNext ); | |
| } | |
| /**Function************************************************************* | |
| Synopsis [Marks TFO of the node.] | |
| Description [] | |
| SideEffects [] | |
| SeeAlso [] | |
| ***********************************************************************/ | |
| void Nwk_ManMarkTfoCone_rec( Nwk_Obj_t * pObj ) | |
| { | |
| Nwk_Obj_t * pNext; | |
| int i; | |
| if ( pObj->MarkA ) | |
| return; | |
| pObj->MarkA = 1; | |
| Nwk_ObjForEachFanout( pObj, pNext, i ) | |
| Nwk_ManMarkTfoCone_rec( pNext ); | |
| } | |
| /**Function************************************************************* | |
| Synopsis [Fast forward flow pushing.] | |
| Description [] | |
| SideEffects [] | |
| SeeAlso [] | |
| ***********************************************************************/ | |
| int Nwk_ManPushForwardFast_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred ) | |
| { | |
| Nwk_Obj_t * pNext; | |
| int i; | |
| if ( Nwk_ObjIsTravIdCurrent( pObj ) ) | |
| return 0; | |
| Nwk_ObjSetTravIdCurrent( pObj ); | |
| if ( Nwk_ObjHasFlow(pObj) ) | |
| return 0; | |
| if ( Nwk_ObjIsSink(pObj) ) | |
| { | |
| Nwk_ObjSetFlow(pObj); | |
| return Nwk_ObjSetPred( pObj, pPred ); | |
| } | |
| Nwk_ObjForEachFanout( pObj, pNext, i ) | |
| if ( Nwk_ManPushForwardFast_rec( pNext, pObj ) ) | |
| { | |
| Nwk_ObjSetFlow(pObj); | |
| return Nwk_ObjSetPred( pObj, pPred ); | |
| } | |
| return 0; | |
| } | |
| /**Function************************************************************* | |
| Synopsis [Fast backward flow pushing.] | |
| Description [] | |
| SideEffects [] | |
| SeeAlso [] | |
| ***********************************************************************/ | |
| int Nwk_ManPushBackwardFast_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred ) | |
| { | |
| Nwk_Obj_t * pNext; | |
| int i; | |
| if ( Nwk_ObjIsTravIdCurrent( pObj ) ) | |
| return 0; | |
| Nwk_ObjSetTravIdCurrent( pObj ); | |
| if ( Nwk_ObjHasFlow(pObj) ) | |
| return 0; | |
| if ( Nwk_ObjIsSink(pObj) ) | |
| { | |
| Nwk_ObjSetFlow(pObj); | |
| return Nwk_ObjSetPred( pObj, pPred ); | |
| } | |
| Nwk_ObjForEachFanin( pObj, pNext, i ) | |
| if ( Nwk_ManPushBackwardFast_rec( pNext, pObj ) ) | |
| { | |
| Nwk_ObjSetFlow(pObj); | |
| return Nwk_ObjSetPred( pObj, pPred ); | |
| } | |
| return 0; | |
| } | |
| /**Function************************************************************* | |
| Synopsis [Pushing the flow through the bottom part of the node.] | |
| Description [] | |
| SideEffects [] | |
| SeeAlso [] | |
| ***********************************************************************/ | |
| int Nwk_ManPushForwardBot_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred ) | |
| { | |
| Nwk_Obj_t * pNext; | |
| int i; | |
| if ( Nwk_ObjVisitedBot(pObj) ) | |
| return 0; | |
| Nwk_ObjSetVisitedBot(pObj); | |
| // propagate through the internal edge | |
| if ( Nwk_ObjHasFlow(pObj) ) | |
| { | |
| if ( Nwk_ObjPred(pObj) ) | |
| if ( Nwk_ManPushForwardTop_rec( Nwk_ObjPred(pObj), Nwk_ObjPred(pObj) ) ) | |
| return Nwk_ObjSetPred( pObj, pPred ); | |
| } | |
| else if ( Nwk_ManPushForwardTop_rec(pObj, pObj) ) | |
| { | |
| Nwk_ObjSetFlow( pObj ); | |
| return Nwk_ObjSetPred( pObj, pPred ); | |
| } | |
| // try to push through the fanins | |
| Nwk_ObjForEachFanin( pObj, pNext, i ) | |
| if ( Nwk_ManPushForwardBot_rec( pNext, pPred ) ) | |
| return 1; | |
| return 0; | |
| } | |
| /**Function************************************************************* | |
| Synopsis [Pushing the flow through the top part of the node.] | |
| Description [] | |
| SideEffects [] | |
| SeeAlso [] | |
| ***********************************************************************/ | |
| int Nwk_ManPushForwardTop_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred ) | |
| { | |
| Nwk_Obj_t * pNext; | |
| int i; | |
| if ( Nwk_ObjVisitedTop(pObj) ) | |
| return 0; | |
| Nwk_ObjSetVisitedTop(pObj); | |
| // check if this is the sink | |
| if ( Nwk_ObjIsSink(pObj) ) | |
| return 1; | |
| // try to push through the fanouts | |
| Nwk_ObjForEachFanout( pObj, pNext, i ) | |
| if ( Nwk_ManPushForwardBot_rec( pNext, pPred ) ) | |
| return 1; | |
| // redirect the flow | |
| if ( Nwk_ObjHasFlow(pObj) && !Nwk_ObjIsCi(pObj) ) | |
| if ( Nwk_ManPushForwardBot_rec( pObj, Nwk_ObjPred(pObj) ) ) | |
| { | |
| Nwk_ObjClearFlow( pObj ); | |
| return Nwk_ObjSetPred( pObj, NULL ); | |
| } | |
| return 0; | |
| } | |
| /**Function************************************************************* | |
| Synopsis [Pushing the flow through the bottom part of the node.] | |
| Description [] | |
| SideEffects [] | |
| SeeAlso [] | |
| ***********************************************************************/ | |
| int Nwk_ManPushBackwardBot_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred ) | |
| { | |
| if ( Nwk_ObjVisitedBot(pObj) ) | |
| return 0; | |
| Nwk_ObjSetVisitedBot(pObj); | |
| // propagate through the internal edge | |
| if ( Nwk_ObjHasFlow(pObj) ) | |
| { | |
| if ( Nwk_ObjPred(pObj) ) | |
| if ( Nwk_ManPushBackwardTop_rec( Nwk_ObjPred(pObj), Nwk_ObjPred(pObj) ) ) | |
| return Nwk_ObjSetPred( pObj, pPred ); | |
| } | |
| else if ( Nwk_ManPushBackwardTop_rec(pObj, pObj) ) | |
| { | |
| Nwk_ObjSetFlow( pObj ); | |
| return Nwk_ObjSetPred( pObj, pPred ); | |
| } | |
| return 0; | |
| } | |
| /**Function************************************************************* | |
| Synopsis [Pushing the flow through the top part of the node.] | |
| Description [] | |
| SideEffects [] | |
| SeeAlso [] | |
| ***********************************************************************/ | |
| int Nwk_ManPushBackwardTop_rec( Nwk_Obj_t * pObj, Nwk_Obj_t * pPred ) | |
| { | |
| Nwk_Obj_t * pNext; | |
| int i; | |
| if ( Nwk_ObjVisitedTop(pObj) ) | |
| return 0; | |
| Nwk_ObjSetVisitedTop(pObj); | |
| // check if this is the sink | |
| if ( Nwk_ObjIsSink(pObj) ) | |
| return 1; | |
| // try to push through the fanins | |
| Nwk_ObjForEachFanin( pObj, pNext, i ) | |
| if ( Nwk_ManPushBackwardBot_rec( pNext, pPred ) ) | |
| return 1; | |
| // try to push through the fanouts | |
| Nwk_ObjForEachFanout( pObj, pNext, i ) | |
| if ( !Nwk_ObjIsCo(pObj) && Nwk_ManPushBackwardTop_rec( pNext, pPred ) ) | |
| return 1; | |
| // redirect the flow | |
| if ( Nwk_ObjHasFlow(pObj) ) | |
| if ( Nwk_ObjPred(pObj) && Nwk_ManPushBackwardBot_rec( pObj, Nwk_ObjPred(pObj) ) ) | |
| { | |
| Nwk_ObjClearFlow( pObj ); | |
| return Nwk_ObjSetPred( pObj, NULL ); | |
| } | |
| return 0; | |
| } | |
| /**Function************************************************************* | |
| Synopsis [Returns 0 if there is an unmarked path to a CI.] | |
| Description [] | |
| SideEffects [] | |
| SeeAlso [] | |
| ***********************************************************************/ | |
| int Nwk_ManVerifyCut_rec( Nwk_Obj_t * pObj ) | |
| { | |
| Nwk_Obj_t * pNext; | |
| int i; | |
| if ( pObj->MarkA ) | |
| return 1; | |
| if ( Nwk_ObjIsLo(pObj) ) | |
| return 0; | |
| if ( Nwk_ObjIsTravIdCurrent( pObj ) ) | |
| return 1; | |
| Nwk_ObjSetTravIdCurrent( pObj ); | |
| Nwk_ObjForEachFanin( pObj, pNext, i ) | |
| if ( !Nwk_ManVerifyCut_rec( pNext ) ) | |
| return 0; | |
| return 1; | |
| } | |
| /**Function************************************************************* | |
| Synopsis [Verifies the forward cut.] | |
| Description [] | |
| SideEffects [] | |
| SeeAlso [] | |
| ***********************************************************************/ | |
| int Nwk_ManRetimeVerifyCutForward( Nwk_Man_t * pMan, Vec_Ptr_t * vNodes ) | |
| { | |
| Nwk_Obj_t * pObj; | |
| int i; | |
| // mark the nodes | |
| Vec_PtrForEachEntry( Nwk_Obj_t *, vNodes, pObj, i ) | |
| { | |
| assert( pObj->MarkA == 0 ); | |
| pObj->MarkA = 1; | |
| } | |
| // traverse from the COs | |
| Nwk_ManIncrementTravId( pMan ); | |
| Nwk_ManForEachCo( pMan, pObj, i ) | |
| if ( !Nwk_ManVerifyCut_rec( pObj ) ) | |
| printf( "Nwk_ManRetimeVerifyCutForward(): Internal cut verification failed.\n" ); | |
| // unmark the nodes | |
| Vec_PtrForEachEntry( Nwk_Obj_t *, vNodes, pObj, i ) | |
| pObj->MarkA = 0; | |
| return 1; | |
| } | |
| /**Function************************************************************* | |
| Synopsis [Verifies the forward cut.] | |
| Description [] | |
| SideEffects [] | |
| SeeAlso [] | |
| ***********************************************************************/ | |
| int Nwk_ManRetimeVerifyCutBackward( Nwk_Man_t * pMan, Vec_Ptr_t * vNodes ) | |
| { | |
| return 1; | |
| } | |
| /**Function************************************************************* | |
| Synopsis [Computes minimum cut for forward retiming.] | |
| Description [] | |
| SideEffects [] | |
| SeeAlso [] | |
| ***********************************************************************/ | |
| Vec_Ptr_t * Nwk_ManRetimeCutForward( Nwk_Man_t * pMan, int nLatches, int fVerbose ) | |
| { | |
| Vec_Ptr_t * vNodes; | |
| Nwk_Obj_t * pObj; | |
| int i, RetValue, Counter = 0, Counter2 = 0; | |
| abctime clk = Abc_Clock(); | |
| // set the sequential parameters | |
| pMan->nLatches = nLatches; | |
| pMan->nTruePis = Nwk_ManCiNum(pMan) - nLatches; | |
| pMan->nTruePos = Nwk_ManCoNum(pMan) - nLatches; | |
| // mark the COs and the TFO of PIs | |
| Nwk_ManForEachCo( pMan, pObj, i ) | |
| pObj->MarkA = 1; | |
| Nwk_ManForEachPiSeq( pMan, pObj, i ) | |
| Nwk_ManMarkTfoCone_rec( pObj ); | |
| // start flow computation from each LO | |
| Nwk_ManIncrementTravIdFlow( pMan ); | |
| Nwk_ManForEachLoSeq( pMan, pObj, i ) | |
| { | |
| if ( !Nwk_ManPushForwardFast_rec( pObj, NULL ) ) | |
| continue; | |
| Nwk_ManIncrementTravIdFlow( pMan ); | |
| Counter++; | |
| } | |
| if ( fVerbose ) | |
| printf( "Forward: Max-flow = %4d -> ", Counter ); | |
| // continue flow computation from each LO | |
| Nwk_ManIncrementTravIdFlow( pMan ); | |
| Nwk_ManForEachLoSeq( pMan, pObj, i ) | |
| { | |
| if ( !Nwk_ManPushForwardBot_rec( pObj, NULL ) ) | |
| continue; | |
| Nwk_ManIncrementTravIdFlow( pMan ); | |
| Counter2++; | |
| } | |
| if ( fVerbose ) | |
| printf( "%4d. ", Counter+Counter2 ); | |
| // repeat flow computation from each LO | |
| if ( Counter2 > 0 ) | |
| { | |
| Nwk_ManIncrementTravIdFlow( pMan ); | |
| Nwk_ManForEachLoSeq( pMan, pObj, i ) | |
| { | |
| RetValue = Nwk_ManPushForwardBot_rec( pObj, NULL ); | |
| assert( !RetValue ); | |
| } | |
| } | |
| // cut is a set of nodes whose bottom is visited but top is not visited | |
| vNodes = Vec_PtrAlloc( Counter+Counter2 ); | |
| Counter = 0; | |
| Nwk_ManForEachObj( pMan, pObj, i ) | |
| { | |
| if ( Nwk_ObjVisitedBotOnly(pObj) ) | |
| { | |
| assert( Nwk_ObjHasFlow(pObj) ); | |
| assert( !Nwk_ObjIsCo(pObj) ); | |
| Vec_PtrPush( vNodes, pObj ); | |
| Counter += Nwk_ObjIsCi(pObj); | |
| } | |
| } | |
| Nwk_ManCleanMarks( pMan ); | |
| // assert( Nwk_ManRetimeVerifyCutForward(pMan, vNodes) ); | |
| if ( fVerbose ) | |
| { | |
| printf( "Min-cut = %4d. Unmoved = %4d. ", Vec_PtrSize(vNodes), Counter ); | |
| ABC_PRT( "Time", Abc_Clock() - clk ); | |
| } | |
| return vNodes; | |
| } | |
| /**Function************************************************************* | |
| Synopsis [Computes minimum cut for backward retiming.] | |
| Description [] | |
| SideEffects [] | |
| SeeAlso [] | |
| ***********************************************************************/ | |
| Vec_Ptr_t * Nwk_ManRetimeCutBackward( Nwk_Man_t * pMan, int nLatches, int fVerbose ) | |
| { | |
| Vec_Ptr_t * vNodes; | |
| Nwk_Obj_t * pObj; | |
| int i, RetValue, Counter = 0, Counter2 = 0; | |
| abctime clk = Abc_Clock(); | |
| // set the sequential parameters | |
| pMan->nLatches = nLatches; | |
| pMan->nTruePis = Nwk_ManCiNum(pMan) - nLatches; | |
| pMan->nTruePos = Nwk_ManCoNum(pMan) - nLatches; | |
| // mark the CIs, the TFI of POs, and the constant nodes | |
| Nwk_ManForEachCi( pMan, pObj, i ) | |
| pObj->MarkA = 1; | |
| Nwk_ManForEachPoSeq( pMan, pObj, i ) | |
| Nwk_ManMarkTfiCone_rec( pObj ); | |
| Nwk_ManForEachNode( pMan, pObj, i ) | |
| if ( Nwk_ObjFaninNum(pObj) == 0 ) | |
| pObj->MarkA = 1; | |
| // start flow computation from each LI driver | |
| Nwk_ManIncrementTravIdFlow( pMan ); | |
| Nwk_ManForEachLiSeq( pMan, pObj, i ) | |
| { | |
| if ( !Nwk_ManPushBackwardFast_rec( Nwk_ObjFanin0(pObj), NULL ) ) | |
| continue; | |
| Nwk_ManIncrementTravIdFlow( pMan ); | |
| Counter++; | |
| } | |
| if ( fVerbose ) | |
| printf( "Backward: Max-flow = %4d -> ", Counter ); | |
| // continue flow computation from each LI driver | |
| Nwk_ManIncrementTravIdFlow( pMan ); | |
| Nwk_ManForEachLiSeq( pMan, pObj, i ) | |
| { | |
| if ( !Nwk_ManPushBackwardBot_rec( Nwk_ObjFanin0(pObj), NULL ) ) | |
| continue; | |
| Nwk_ManIncrementTravIdFlow( pMan ); | |
| Counter2++; | |
| } | |
| if ( fVerbose ) | |
| printf( "%4d. ", Counter+Counter2 ); | |
| // repeat flow computation from each LI driver | |
| if ( Counter2 > 0 ) | |
| { | |
| Nwk_ManIncrementTravIdFlow( pMan ); | |
| Nwk_ManForEachLiSeq( pMan, pObj, i ) | |
| { | |
| RetValue = Nwk_ManPushBackwardBot_rec( Nwk_ObjFanin0(pObj), NULL ); | |
| assert( !RetValue ); | |
| } | |
| } | |
| // cut is a set of nodes whose bottom is visited but top is not visited | |
| vNodes = Vec_PtrAlloc( Counter+Counter2 ); | |
| Nwk_ManForEachObj( pMan, pObj, i ) | |
| { | |
| if ( Nwk_ObjVisitedBotOnly(pObj) ) | |
| { | |
| assert( Nwk_ObjHasFlow(pObj) ); | |
| assert( !Nwk_ObjIsCo(pObj) ); | |
| Vec_PtrPush( vNodes, pObj ); | |
| } | |
| } | |
| // count CO drivers | |
| Counter = 0; | |
| Nwk_ManForEachLiSeq( pMan, pObj, i ) | |
| if ( Nwk_ObjVisitedBotOnly( Nwk_ObjFanin0(pObj) ) ) | |
| Counter++; | |
| Nwk_ManCleanMarks( pMan ); | |
| // assert( Nwk_ManRetimeVerifyCutBackward(pMan, vNodes) ); | |
| if ( fVerbose ) | |
| { | |
| printf( "Min-cut = %4d. Unmoved = %4d. ", Vec_PtrSize(vNodes), Counter ); | |
| ABC_PRT( "Time", Abc_Clock() - clk ); | |
| } | |
| return vNodes; | |
| } | |
| //////////////////////////////////////////////////////////////////////// | |
| /// END OF FILE /// | |
| //////////////////////////////////////////////////////////////////////// | |
| ABC_NAMESPACE_IMPL_END | |