/**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