Major restructuring of the code.

1 files changed, 0 insertions, 631 deletions

diff --git a/src/aig/nwk/nwkFlow_depth.c b/src/aig/nwk/nwkFlow_depth.c
deleted file mode 100644
index 6c2e7eb9..00000000
--- a/src/aig/nwk/nwkFlow_depth.c
+++ /dev/null
@@ -1,631 +0,0 @@
-/**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;
-    int 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;
-    int 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
-