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

int DepthFwd, DepthBwd, DepthFwdMax, DepthBwdMax;

////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

// predecessors
static inline Nwk_Obj_t * Nwk_ObjPred( Nwk_Obj_t * pObj )                   { return 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 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);
    DepthFwd++;
    if ( DepthFwdMax < DepthFwd )
        DepthFwdMax = DepthFwd;
    // propagate through the internal edge
    if ( Nwk_ObjHasFlow(pObj) )
    {
        if ( Nwk_ObjPred(pObj) )
            if ( Nwk_ManPushForwardTop_rec( Nwk_ObjPred(pObj), Nwk_ObjPred(pObj) ) )
            {
                DepthFwd--;
                return Nwk_ObjSetPred( pObj, pPred ); 
            }
    }
    else if ( Nwk_ManPushForwardTop_rec(pObj, pObj) )
    {
        DepthFwd--;
        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 ) )
        {
            DepthFwd--;
            return 1;
        }
    DepthFwd--;
    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;
    DepthFwd++;
    if ( DepthFwdMax < DepthFwd )
        DepthFwdMax = DepthFwd;
    // try to push through the fanouts
    Nwk_ObjForEachFanout( pObj, pNext, i )
        if ( Nwk_ManPushForwardBot_rec( pNext, pPred ) )
        {
            DepthFwd--;
            return 1;
        }
    // redirect the flow
    if ( Nwk_ObjHasFlow(pObj) && !Nwk_ObjIsCi(pObj) )
        if ( Nwk_ManPushForwardBot_rec( pObj, Nwk_ObjPred(pObj) ) )
        {
            DepthFwd--;
            Nwk_ObjClearFlow( pObj );
            return Nwk_ObjSetPred( pObj, NULL );
        }
    DepthFwd--;
    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;
    clock_t clk = 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
    DepthFwdMax = DepthFwd = 0;
    Nwk_ManIncrementTravIdFlow( pMan );
    Nwk_ManForEachLoSeq( pMan, pObj, i )
    {
    printf( "%d ", DepthFwdMax );
        if ( !Nwk_ManPushForwardBot_rec( pObj, NULL ) )
            continue;
        assert( DepthFwd == 0 );
        Nwk_ManIncrementTravIdFlow( pMan );
        Counter2++;
    }
    printf( "DepthMax = %d.\n", DepthFwdMax );
    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 );
    PRT( "Time", 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;
    clock_t clk = 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 );
    PRT( "Time", clock() - clk );
    }
    return vNodes;
}


////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


ABC_NAMESPACE_IMPL_END