nwkFlow.c File Reference

#include "nwk.h"

Include dependency graph for nwkFlow.c:

Go to the source code of this file.

Functions
void	Nwk_ManMarkTfiCone_rec (Nwk_Obj_t *pObj)
	FUNCTION DEFINITIONS ///.
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

Nwk_ManMarkTfiCone_rec()

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

Here is the call graph for this function:

Here is the caller graph for this function:

Nwk_ManMarkTfoCone_rec()

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

Here is the call graph for this function:

Here is the caller graph for this function:

Nwk_ManPushBackwardFast_rec()

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

Here is the call graph for this function:

Here is the caller graph for this function:

Nwk_ManPushForwardFast_rec()

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

Here is the call graph for this function:

Here is the caller graph for this function:

Nwk_ManRetimeCutBackward()

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

Nwk_ManRetimeCutForward()

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

Nwk_ManRetimeVerifyCutBackward()

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

Nwk_ManRetimeVerifyCutForward()

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

Here is the call graph for this function:

Nwk_ManVerifyCut_rec()

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

Here is the call graph for this function:

Here is the caller graph for this function: