nwkFlow.c File Reference

#include "nwk.h"

Go to the source code of this file.

Functions
static ABC_NAMESPACE_IMPL_START Nwk_Obj_t *	Nwk_ObjPred (Nwk_Obj_t *pObj)
	DECLARATIONS ///. More...
static int	Nwk_ObjSetPred (Nwk_Obj_t *pObj, Nwk_Obj_t *p)
static int	Nwk_ObjIsSink (Nwk_Obj_t *pObj)
static void	Nwk_ObjSetSink (Nwk_Obj_t *pObj)
static int	Nwk_ObjHasFlow (Nwk_Obj_t *pObj)
static void	Nwk_ObjSetFlow (Nwk_Obj_t *pObj)
static void	Nwk_ObjClearFlow (Nwk_Obj_t *pObj)
static int	Nwk_ObjVisitedBotOnly (Nwk_Obj_t *pObj)
static int	Nwk_ObjVisitedBot (Nwk_Obj_t *pObj)
static int	Nwk_ObjVisitedTop (Nwk_Obj_t *pObj)
static void	Nwk_ObjSetVisitedBot (Nwk_Obj_t *pObj)
static void	Nwk_ObjSetVisitedTop (Nwk_Obj_t *pObj)
static void	Nwk_ManIncrementTravIdFlow (Nwk_Man_t *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)
void	Nwk_ManMarkTfiCone_rec (Nwk_Obj_t *pObj)
	FUNCTION DEFINITIONS ///. More...
void	Nwk_ManMarkTfoCone_rec (Nwk_Obj_t *pObj)
int	Nwk_ManPushForwardFast_rec (Nwk_Obj_t *pObj, Nwk_Obj_t *pPred)
int	Nwk_ManPushBackwardFast_rec (Nwk_Obj_t *pObj, Nwk_Obj_t *pPred)
int	Nwk_ManVerifyCut_rec (Nwk_Obj_t *pObj)
int	Nwk_ManRetimeVerifyCutForward (Nwk_Man_t *pMan, Vec_Ptr_t *vNodes)
int	Nwk_ManRetimeVerifyCutBackward (Nwk_Man_t *pMan, Vec_Ptr_t *vNodes)
Vec_Ptr_t *	Nwk_ManRetimeCutForward (Nwk_Man_t *pMan, int nLatches, int fVerbose)
Vec_Ptr_t *	Nwk_ManRetimeCutBackward (Nwk_Man_t *pMan, int nLatches, int fVerbose)

Function Documentation

static void Nwk_ManIncrementTravIdFlow ( Nwk_Man_t *  pMan )

inlinestatic

Definition at line 84 of file nwkFlow.c.

{
    Nwk_ManIncrementTravId( pMan );
    Nwk_ManIncrementTravId( pMan );
    Nwk_ManIncrementTravId( pMan );
}

void Nwk_ManMarkTfiCone_rec

(

Nwk_Obj_t *

pObj

)

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis [Marks TFI of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 112 of file nwkFlow.c.

{
    Nwk_Obj_t * pNext;
    int i;
    if ( pObj->MarkA )
        return;
    pObj->MarkA = 1;
    Nwk_ObjForEachFanin( pObj, pNext, i )
        Nwk_ManMarkTfiCone_rec( pNext );
}

void Nwk_ManMarkTfoCone_rec

(

Nwk_Obj_t *

pObj

)

Function*************************************************************

Synopsis [Marks TFO of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 134 of file nwkFlow.c.

{
    Nwk_Obj_t * pNext;
    int i;
    if ( pObj->MarkA )
        return;
    pObj->MarkA = 1;
    Nwk_ObjForEachFanout( pObj, pNext, i )
        Nwk_ManMarkTfoCone_rec( pNext );
}

int Nwk_ManPushBackwardBot_rec ( Nwk_Obj_t *  pObj, Nwk_Obj_t *  pPred  )

static

Function*************************************************************

Synopsis [Pushing the flow through the bottom part of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 296 of file nwkFlow.c.

{
    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;
}

int Nwk_ManPushBackwardFast_rec	(	Nwk_Obj_t *	pObj,
		Nwk_Obj_t *	pPred
	)

Function*************************************************************

Synopsis [Fast backward flow pushing.]

Description []

SideEffects []

SeeAlso []

Definition at line 190 of file nwkFlow.c.

{
    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;
}

int Nwk_ManPushBackwardTop_rec ( Nwk_Obj_t *  pObj, Nwk_Obj_t *  pPred  )

static

Function*************************************************************

Synopsis [Pushing the flow through the top part of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 327 of file nwkFlow.c.

{
    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;
}

int Nwk_ManPushForwardBot_rec ( Nwk_Obj_t *  pObj, Nwk_Obj_t *  pPred  )

static

Function*************************************************************

Synopsis [Pushing the flow through the bottom part of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 224 of file nwkFlow.c.

{
    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;
}

int Nwk_ManPushForwardFast_rec	(	Nwk_Obj_t *	pObj,
		Nwk_Obj_t *	pPred
	)

Function*************************************************************

Synopsis [Fast forward flow pushing.]

Description []

SideEffects []

SeeAlso []

Definition at line 156 of file nwkFlow.c.

{
    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;
}

int Nwk_ManPushForwardTop_rec ( Nwk_Obj_t *  pObj, Nwk_Obj_t *  pPred  )

static

Function*************************************************************

Synopsis [Pushing the flow through the top part of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 261 of file nwkFlow.c.

{
    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;
}

Vec_Ptr_t* Nwk_ManRetimeCutBackward	(	Nwk_Man_t *	pMan,
		int	nLatches,
		int	fVerbose
	)

Function*************************************************************

Synopsis [Computes minimum cut for backward retiming.]

Description []

SideEffects []

SeeAlso []

Definition at line 523 of file nwkFlow.c.

{
    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;
}

Vec_Ptr_t* Nwk_ManRetimeCutForward	(	Nwk_Man_t *	pMan,
		int	nLatches,
		int	fVerbose
	)

Function*************************************************************

Synopsis [Computes minimum cut for forward retiming.]

Description []

SideEffects []

SeeAlso []

Definition at line 442 of file nwkFlow.c.

{
    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;
}

int Nwk_ManRetimeVerifyCutBackward	(	Nwk_Man_t *	pMan,
		Vec_Ptr_t *	vNodes
	)

Function*************************************************************

Synopsis [Verifies the forward cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 426 of file nwkFlow.c.

{
    return 1;
}

int Nwk_ManRetimeVerifyCutForward	(	Nwk_Man_t *	pMan,
		Vec_Ptr_t *	vNodes
	)

Function*************************************************************

Synopsis [Verifies the forward cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 394 of file nwkFlow.c.

{
    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;
}

int Nwk_ManVerifyCut_rec

(

Nwk_Obj_t *

pObj

)

Function*************************************************************

Synopsis [Returns 0 if there is an unmarked path to a CI.]

Description []

SideEffects []

SeeAlso []

Definition at line 366 of file nwkFlow.c.

{
    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;
}

static void Nwk_ObjClearFlow ( Nwk_Obj_t *  pObj )

inlinestatic

Definition at line 47 of file nwkFlow.c.

{ pObj->MarkB = 0;           }

static int Nwk_ObjHasFlow ( Nwk_Obj_t *  pObj )

inlinestatic

Definition at line 45 of file nwkFlow.c.

{ return pObj->MarkB;        }

static int Nwk_ObjIsSink ( Nwk_Obj_t *  pObj )

inlinestatic

Definition at line 42 of file nwkFlow.c.

{ return pObj->MarkA;        }

static ABC_NAMESPACE_IMPL_START Nwk_Obj_t* Nwk_ObjPred ( Nwk_Obj_t *  pObj )

inlinestatic

DECLARATIONS ///.

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

]

Definition at line 39 of file nwkFlow.c.

{ return (Nwk_Obj_t *)pObj->pCopy;        }

static void Nwk_ObjSetFlow ( Nwk_Obj_t *  pObj )

inlinestatic

Definition at line 46 of file nwkFlow.c.

{ pObj->MarkB = 1;           }

static int Nwk_ObjSetPred ( Nwk_Obj_t *  pObj, Nwk_Obj_t *  p  )

inlinestatic

Definition at line 40 of file nwkFlow.c.

{ pObj->pCopy = p; return 1; }

static void Nwk_ObjSetSink ( Nwk_Obj_t *  pObj )

inlinestatic

Definition at line 43 of file nwkFlow.c.

{ pObj->MarkA = 1;           }

static void Nwk_ObjSetVisitedBot ( Nwk_Obj_t *  pObj )

inlinestatic

Definition at line 66 of file nwkFlow.c.

{
    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 void Nwk_ObjSetVisitedTop ( Nwk_Obj_t *  pObj )

inlinestatic

Definition at line 75 of file nwkFlow.c.

{
    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 int Nwk_ObjVisitedBot ( Nwk_Obj_t *  pObj )

inlinestatic

Definition at line 58 of file nwkFlow.c.

{ 
    return pObj->TravId == pObj->pMan->nTravIds - 2 || pObj->TravId == pObj->pMan->nTravIds; 
}

static int Nwk_ObjVisitedBotOnly ( Nwk_Obj_t *  pObj )

inlinestatic

Definition at line 54 of file nwkFlow.c.

{
    return pObj->TravId == pObj->pMan->nTravIds - 2;
}

static int Nwk_ObjVisitedTop ( Nwk_Obj_t *  pObj )

inlinestatic

Definition at line 62 of file nwkFlow.c.

{ 
    return pObj->TravId == pObj->pMan->nTravIds - 1 || pObj->TravId == pObj->pMan->nTravIds; 
}