diff options
Diffstat (limited to 'src/opt/ret/retFlow.c')
-rw-r--r-- | src/opt/ret/retFlow.c | 370 |
1 files changed, 316 insertions, 54 deletions
diff --git a/src/opt/ret/retFlow.c b/src/opt/ret/retFlow.c index 642a1f69..24d7bf57 100644 --- a/src/opt/ret/retFlow.c +++ b/src/opt/ret/retFlow.c @@ -46,14 +46,40 @@ static inline Abc_Obj_t * Abc_ObjGetFaninPath( Abc_Obj_t * pObj ) return pFanin; return NULL; } +static inline Abc_Obj_t * Abc_ObjGetPredecessorBwd( Abc_Obj_t * pObj ) +{ + Abc_Obj_t * pNext; + int i; + Abc_ObjForEachFanout( pObj, pNext, i ) + if ( Abc_ObjGetPath(pNext) == pObj ) + return pNext; + Abc_ObjForEachFanin( pObj, pNext, i ) + if ( Abc_ObjGetPath(pNext) == pObj ) + return pNext; + return NULL; +} +static inline Abc_Obj_t * Abc_ObjGetPredecessorFwd( Abc_Obj_t * pObj ) +{ + Abc_Obj_t * pNext; + int i; + Abc_ObjForEachFanin( pObj, pNext, i ) + if ( Abc_ObjGetPath(pNext) == pObj ) + return pNext; + Abc_ObjForEachFanout( pObj, pNext, i ) + if ( Abc_ObjGetPath(pNext) == pObj ) + return pNext; + return NULL; +} -static int Abc_NtkMaxFlowPath( Abc_Ntk_t * pNtk, int * pStart, int fForward ); static int Abc_NtkMaxFlowBwdPath_rec( Abc_Obj_t * pObj ); static int Abc_NtkMaxFlowFwdPath_rec( Abc_Obj_t * pObj ); -static Vec_Ptr_t * Abc_NtkMaxFlowMinCut( Abc_Ntk_t * pNtk ); +static int Abc_NtkMaxFlowBwdPath2_rec( Abc_Obj_t * pObj ); +static int Abc_NtkMaxFlowFwdPath2_rec( Abc_Obj_t * pObj ); +static Vec_Ptr_t * Abc_NtkMaxFlowMinCut( Abc_Ntk_t * pNtk, int fForward ); +static void Abc_NtkMaxFlowMinCutUpdate( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward ); static int Abc_NtkMaxFlowVerifyCut( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward ); +static void Abc_NtkMaxFlowPrintCut( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut ); static void Abc_NtkMaxFlowPrintFlow( Abc_Ntk_t * pNtk, int fForward ); -static void Abc_NtkMaxFlowPrintCut( Vec_Ptr_t * vMinCut ); //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// @@ -93,6 +119,7 @@ void Abc_NtkMaxFlowTest( Abc_Ntk_t * pNtk ) vMinCut = Abc_NtkMaxFlow( pNtk, 0, 1 ); Vec_PtrFree( vMinCut ); Abc_NtkCleanMarkA( pNtk ); + } /**Function************************************************************* @@ -109,37 +136,102 @@ void Abc_NtkMaxFlowTest( Abc_Ntk_t * pNtk ) Vec_Ptr_t * Abc_NtkMaxFlow( Abc_Ntk_t * pNtk, int fForward, int fVerbose ) { Vec_Ptr_t * vMinCut; - int Flow, RetValue; + Abc_Obj_t * pLatch; + int Flow, FlowCur, RetValue, i; int clk = clock(); - int Start = 0; + int fUseDirectedFlow = 1; // find the max-flow Abc_NtkCleanCopy( pNtk ); - for ( Flow = 0; Abc_NtkMaxFlowPath( pNtk, &Start, fForward ); Flow++ ); + Flow = 0; + Abc_NtkIncrementTravId(pNtk); + Abc_NtkForEachLatch( pNtk, pLatch, i ) + { + if ( fForward ) + { +// assert( !Abc_ObjFanout0(pLatch)->fMarkA ); + FlowCur = Abc_NtkMaxFlowFwdPath2_rec( Abc_ObjFanout0(pLatch) ); + Flow += FlowCur; + } + else + { + assert( !Abc_ObjFanin0(pLatch)->fMarkA ); + FlowCur = Abc_NtkMaxFlowBwdPath2_rec( Abc_ObjFanin0(pLatch) ); + Flow += FlowCur; + } + if ( FlowCur ) + Abc_NtkIncrementTravId(pNtk); + } + + if ( !fUseDirectedFlow ) + { + Abc_NtkIncrementTravId(pNtk); + Abc_NtkForEachLatch( pNtk, pLatch, i ) + { + if ( fForward ) + { + // assert( !Abc_ObjFanout0(pLatch)->fMarkA ); + FlowCur = Abc_NtkMaxFlowFwdPath_rec( Abc_ObjFanout0(pLatch) ); + Flow += FlowCur; + } + else + { + assert( !Abc_ObjFanin0(pLatch)->fMarkA ); + FlowCur = Abc_NtkMaxFlowBwdPath_rec( Abc_ObjFanin0(pLatch) ); + Flow += FlowCur; + } + if ( FlowCur ) + Abc_NtkIncrementTravId(pNtk); + } + } // Abc_NtkMaxFlowPrintFlow( pNtk, fForward ); + // mark the nodes reachable from the latches + Abc_NtkIncrementTravId(pNtk); + Abc_NtkForEachLatch( pNtk, pLatch, i ) + { + if ( fForward ) + { +// assert( !Abc_ObjFanout0(pLatch)->fMarkA ); + if ( fUseDirectedFlow ) + RetValue = Abc_NtkMaxFlowFwdPath2_rec( Abc_ObjFanout0(pLatch) ); + else + RetValue = Abc_NtkMaxFlowFwdPath_rec( Abc_ObjFanout0(pLatch) ); + } + else + { + assert( !Abc_ObjFanin0(pLatch)->fMarkA ); + if ( fUseDirectedFlow ) + RetValue = Abc_NtkMaxFlowBwdPath2_rec( Abc_ObjFanin0(pLatch) ); + else + RetValue = Abc_NtkMaxFlowBwdPath_rec( Abc_ObjFanin0(pLatch) ); + } + assert( RetValue == 0 ); + } + // find the min-cut with the smallest volume - RetValue = Abc_NtkMaxFlowPath( pNtk, NULL, fForward ); - assert( RetValue == 0 ); - vMinCut = Abc_NtkMaxFlowMinCut( pNtk ); + vMinCut = Abc_NtkMaxFlowMinCut( pNtk, fForward ); + // verify the cut if ( !Abc_NtkMaxFlowVerifyCut(pNtk, vMinCut, fForward) ) printf( "Abc_NtkMaxFlow() error! The computed min-cut is not a cut!\n" ); + // make the cut retimable + Abc_NtkMaxFlowMinCutUpdate( pNtk, vMinCut, fForward ); // report the results if ( fVerbose ) { - printf( "Latches = %6d. %s max-flow = %6d. Min-cut = %6d. ", + printf( "L = %6d. %s max-flow = %6d. Min-cut = %6d. ", Abc_NtkLatchNum(pNtk), fForward? "Forward " : "Backward", Flow, Vec_PtrSize(vMinCut) ); PRT( "Time", clock() - clk ); } -// Abc_NtkMaxFlowPrintCut( vMinCut ); +// Abc_NtkMaxFlowPrintCut( pNtk, vMinCut ); return vMinCut; } /**Function************************************************************* - Synopsis [Finds and augments one path.] + Synopsis [Tries to find an augmenting path originating in this node.] Description [] @@ -148,35 +240,44 @@ PRT( "Time", clock() - clk ); SeeAlso [] ***********************************************************************/ -int Abc_NtkMaxFlowPath( Abc_Ntk_t * pNtk, int * pStart, int fForward ) +int Abc_NtkMaxFlowBwdPath_rec( Abc_Obj_t * pObj ) { - Abc_Obj_t * pLatch; - int i, LatchStart = pStart? *pStart : 0; - Abc_NtkIncrementTravId(pNtk); - Vec_PtrForEachEntryStart( pNtk->vBoxes, pLatch, i, LatchStart ) + Abc_Obj_t * pNext, * pPred; + int i; + // skip visited nodes + if ( Abc_NodeIsTravIdCurrent(pObj) ) + return 0; + Abc_NodeSetTravIdCurrent(pObj); + // get the predecessor + pPred = Abc_ObjGetPredecessorBwd( pObj ); + // process node without flow + if ( !Abc_ObjGetPath(pObj) ) { - if ( !Abc_ObjIsLatch(pLatch) ) - continue; - if ( fForward ) - { - assert( !Abc_ObjFanout0(pLatch)->fMarkA ); - if ( Abc_NtkMaxFlowFwdPath_rec( Abc_ObjFanout0(pLatch) ) ) - { - if ( pStart ) *pStart = i + 1; - return 1; - } - } - else - { - assert( !Abc_ObjFanin0(pLatch)->fMarkA ); - if ( Abc_NtkMaxFlowBwdPath_rec( Abc_ObjFanin0(pLatch) ) ) - { - if ( pStart ) *pStart = i + 1; - return 1; - } - } + // start the path if we reached a terminal node + if ( pObj->fMarkA ) + return Abc_ObjSetPath( pObj, (void *)1 ); + // explore the fanins + Abc_ObjForEachFanin( pObj, pNext, i ) + if ( pNext != pPred && !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowBwdPath_rec(pNext) ) + return Abc_ObjSetPath( pObj, pNext ); + Abc_ObjForEachFanout( pObj, pNext, i ) + if ( pNext != pPred && !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowBwdPath_rec(pNext) ) + return Abc_ObjSetPath( pObj, pNext ); + return 0; } - if ( pStart ) *pStart = 0; + // pObj has flow - find the fanout with flow + if ( pPred == NULL ) + return 0; + // go through the successors of the predecessor + Abc_ObjForEachFanin( pPred, pNext, i ) + if ( !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowBwdPath_rec( pNext ) ) + return Abc_ObjSetPath( pPred, pNext ); + Abc_ObjForEachFanout( pPred, pNext, i ) + if ( !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowBwdPath_rec( pNext ) ) + return Abc_ObjSetPath( pPred, pNext ); + // try the fanout + if ( Abc_NtkMaxFlowBwdPath_rec( pPred ) ) + return Abc_ObjSetPath( pPred, NULL ); return 0; } @@ -191,7 +292,59 @@ int Abc_NtkMaxFlowPath( Abc_Ntk_t * pNtk, int * pStart, int fForward ) SeeAlso [] ***********************************************************************/ -int Abc_NtkMaxFlowBwdPath_rec( Abc_Obj_t * pObj ) +int Abc_NtkMaxFlowFwdPath_rec( Abc_Obj_t * pObj ) +{ + Abc_Obj_t * pNext, * pPred; + int i; + // skip visited nodes + if ( Abc_NodeIsTravIdCurrent(pObj) ) + return 0; + Abc_NodeSetTravIdCurrent(pObj); + // get the predecessor + pPred = Abc_ObjGetPredecessorFwd( pObj ); + // process node without flow + if ( !Abc_ObjGetPath(pObj) ) + { + // start the path if we reached a terminal node + if ( pObj->fMarkA ) + return Abc_ObjSetPath( pObj, (void *)1 ); + // explore the fanins + Abc_ObjForEachFanout( pObj, pNext, i ) + if ( pNext != pPred && !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowFwdPath_rec(pNext) ) + return Abc_ObjSetPath( pObj, pNext ); + Abc_ObjForEachFanin( pObj, pNext, i ) + if ( pNext != pPred && !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowFwdPath_rec(pNext) ) + return Abc_ObjSetPath( pObj, pNext ); + return 0; + } + // pObj has flow - find the fanout with flow + if ( pPred == NULL ) + return 0; + // go through the successors of the predecessor + Abc_ObjForEachFanout( pPred, pNext, i ) + if ( !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowFwdPath_rec( pNext ) ) + return Abc_ObjSetPath( pPred, pNext ); + Abc_ObjForEachFanin( pPred, pNext, i ) + if ( !Abc_ObjIsLatch(pNext) && Abc_NtkMaxFlowFwdPath_rec( pNext ) ) + return Abc_ObjSetPath( pPred, pNext ); + // try the fanout + if ( Abc_NtkMaxFlowFwdPath_rec( pPred ) ) + return Abc_ObjSetPath( pPred, NULL ); + return 0; +} + +/**Function************************************************************* + + Synopsis [Tries to find an augmenting path originating in this node.] + + Description [This procedure works for directed graphs only!] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Abc_NtkMaxFlowBwdPath2_rec( Abc_Obj_t * pObj ) { Abc_Obj_t * pFanout, * pFanin; int i; @@ -207,7 +360,7 @@ int Abc_NtkMaxFlowBwdPath_rec( Abc_Obj_t * pObj ) return Abc_ObjSetPath( pObj, (void *)1 ); // explore the fanins Abc_ObjForEachFanin( pObj, pFanin, i ) - if ( Abc_NtkMaxFlowBwdPath_rec(pFanin) ) + if ( Abc_NtkMaxFlowBwdPath2_rec(pFanin) ) return Abc_ObjSetPath( pObj, pFanin ); return 0; } @@ -217,10 +370,10 @@ int Abc_NtkMaxFlowBwdPath_rec( Abc_Obj_t * pObj ) return 0; // go through the fanins of the fanout with flow Abc_ObjForEachFanin( pFanout, pFanin, i ) - if ( pFanin != pObj && Abc_NtkMaxFlowBwdPath_rec( pFanin ) ) + if ( Abc_NtkMaxFlowBwdPath2_rec( pFanin ) ) return Abc_ObjSetPath( pFanout, pFanin ); // try the fanout - if ( Abc_NtkMaxFlowBwdPath_rec( pFanout ) ) + if ( Abc_NtkMaxFlowBwdPath2_rec( pFanout ) ) return Abc_ObjSetPath( pFanout, NULL ); return 0; } @@ -229,14 +382,14 @@ int Abc_NtkMaxFlowBwdPath_rec( Abc_Obj_t * pObj ) Synopsis [Tries to find an augmenting path originating in this node.] - Description [] + Description [This procedure works for directed graphs only!] SideEffects [] SeeAlso [] ***********************************************************************/ -int Abc_NtkMaxFlowFwdPath_rec( Abc_Obj_t * pObj ) +int Abc_NtkMaxFlowFwdPath2_rec( Abc_Obj_t * pObj ) { Abc_Obj_t * pFanout, * pFanin; int i; @@ -252,7 +405,7 @@ int Abc_NtkMaxFlowFwdPath_rec( Abc_Obj_t * pObj ) return Abc_ObjSetPath( pObj, (void *)1 ); // explore the fanins Abc_ObjForEachFanout( pObj, pFanout, i ) - if ( Abc_NtkMaxFlowFwdPath_rec(pFanout) ) + if ( Abc_NtkMaxFlowFwdPath2_rec(pFanout) ) return Abc_ObjSetPath( pObj, pFanout ); return 0; } @@ -262,18 +415,17 @@ int Abc_NtkMaxFlowFwdPath_rec( Abc_Obj_t * pObj ) return 0; // go through the fanins of the fanout with flow Abc_ObjForEachFanout( pFanin, pFanout, i ) - if ( pFanout != pObj && Abc_NtkMaxFlowFwdPath_rec( pFanout ) ) + if ( Abc_NtkMaxFlowFwdPath2_rec( pFanout ) ) return Abc_ObjSetPath( pFanin, pFanout ); // try the fanout - if ( Abc_NtkMaxFlowFwdPath_rec( pFanin ) ) + if ( Abc_NtkMaxFlowFwdPath2_rec( pFanin ) ) return Abc_ObjSetPath( pFanin, NULL ); return 0; } - /**Function************************************************************* - Synopsis [Find one minumum cut.] + Synopsis [Find minimum-volume minumum cut.] Description [] @@ -282,7 +434,7 @@ int Abc_NtkMaxFlowFwdPath_rec( Abc_Obj_t * pObj ) SeeAlso [] ***********************************************************************/ -Vec_Ptr_t * Abc_NtkMaxFlowMinCut( Abc_Ntk_t * pNtk ) +Vec_Ptr_t * Abc_NtkMaxFlowMinCut( Abc_Ntk_t * pNtk, int fForward ) { Vec_Ptr_t * vMinCut; Abc_Obj_t * pObj; @@ -306,6 +458,113 @@ Vec_Ptr_t * Abc_NtkMaxFlowMinCut( Abc_Ntk_t * pNtk ) /**Function************************************************************* + Synopsis [Marks the TFI cone with MarkA.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkMaxFlowMarkCut_rec( Abc_Obj_t * pObj ) +{ + Abc_Obj_t * pNext; + int i; + if ( pObj->fMarkA ) + return; + pObj->fMarkA = 1; + Abc_ObjForEachFanin( pObj, pNext, i ) + Abc_NtkMaxFlowMarkCut_rec( pNext ); +} + +/**Function************************************************************* + + Synopsis [Visits the TFI up to marked nodes and collects marked nodes.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkMaxFlowCollectCut_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vNodes ) +{ + Abc_Obj_t * pNext; + int i; + if ( Abc_NodeIsTravIdCurrent(pObj) ) + return; + Abc_NodeSetTravIdCurrent(pObj); + if ( pObj->fMarkA ) + { + Vec_PtrPush( vNodes, pObj ); + return; + } + Abc_ObjForEachFanin( pObj, pNext, i ) + Abc_NtkMaxFlowCollectCut_rec( pNext, vNodes ); +} + +/**Function************************************************************* + + Synopsis [Updates the minimum cut to be retimable.] + + Description [This procedure also labels the nodes reachable from + the latches to the cut with fMarkA.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NtkMaxFlowMinCutUpdate( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward ) +{ + Abc_Obj_t * pObj, * pNext; + int i, k; + // clean marks + Abc_NtkForEachObj( pNtk, pObj, i ) + pObj->fMarkA = 0; + // set latch outputs + Abc_NtkForEachLatch( pNtk, pObj, i ) + Abc_ObjFanout0(pObj)->fMarkA = 1; + // traverse from cut nodes + Vec_PtrForEachEntry( vMinCut, pObj, i ) + Abc_NtkMaxFlowMarkCut_rec( pObj ); + if ( fForward ) + { + // change mincut to be nodes with unmarked fanouts + Vec_PtrClear( vMinCut ); + Abc_NtkForEachObj( pNtk, pObj, i ) + { + if ( !pObj->fMarkA ) + continue; + Abc_ObjForEachFanout( pObj, pNext, k ) + { + if ( pNext->fMarkA ) + continue; + Vec_PtrPush( vMinCut, pObj ); + break; + } + } + } + else + { + // change mincut to be marked fanins of the unmarked nodes + Vec_PtrClear( vMinCut ); + Abc_NtkIncrementTravId(pNtk); + Abc_NtkForEachLatch( pNtk, pObj, i ) + Abc_NtkMaxFlowCollectCut_rec( Abc_ObjFanin0(pObj), vMinCut ); + // transfer the attribute + Abc_NtkForEachObj( pNtk, pObj, i ) + pObj->fMarkA = Abc_NodeIsTravIdCurrent(pObj); + // unmark the cut nodes + Vec_PtrForEachEntry( vMinCut, pObj, i ) + pObj->fMarkA = 0; + } +} + +/**Function************************************************************* + Synopsis [Verifies the min-cut is indeed a cut.] Description [] @@ -369,13 +628,11 @@ int Abc_NtkMaxFlowVerifyCut( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut, int fForward { if ( fForward ) { - assert( !Abc_ObjFanout0(pObj)->fMarkA ); if ( !Abc_NtkMaxFlowVerifyCut_rec( Abc_ObjFanout0(pObj), fForward ) ) return 0; } else { - assert( !Abc_ObjFanin0(pObj)->fMarkA ); if ( !Abc_NtkMaxFlowVerifyCut_rec( Abc_ObjFanin0(pObj), fForward ) ) return 0; } @@ -456,13 +713,18 @@ void Abc_NtkMaxFlowPrintFlow( Abc_Ntk_t * pNtk, int fForward ) SeeAlso [] ***********************************************************************/ -void Abc_NtkMaxFlowPrintCut( Vec_Ptr_t * vMinCut ) +void Abc_NtkMaxFlowPrintCut( Abc_Ntk_t * pNtk, Vec_Ptr_t * vMinCut ) { Abc_Obj_t * pObj; int i; printf( "Min-cut: " ); Vec_PtrForEachEntry( vMinCut, pObj, i ) - printf( "%d ", pObj->Id ); + printf( "%s(%d) ", Abc_ObjName(pObj), pObj->Id ); + printf( "\n" ); + printf( "Marked nodes: " ); + Abc_NtkForEachObj( pNtk, pObj, i ) + if ( pObj->fMarkA ) + printf( "%s(%d) ", Abc_ObjName(pObj), pObj->Id ); printf( "\n" ); } |