nwkDfs.c File Reference

#include "nwk.h"

Go to the source code of this file.

Functions
ABC_NAMESPACE_IMPL_START int	Nwk_ManVerifyTopoOrder (Nwk_Man_t *pNtk)
	DECLARATIONS ///. More...
int	Nwk_ManLevelBackup (Nwk_Man_t *pNtk)
void	Nwk_ManLevel_rec (Nwk_Obj_t *pObj)
int	Nwk_ManLevel (Nwk_Man_t *pNtk)
int	Nwk_ManLevelMax (Nwk_Man_t *pNtk)
Vec_Vec_t *	Nwk_ManLevelize (Nwk_Man_t *pNtk)
void	Nwk_ManDfs_rec (Nwk_Obj_t *pObj, Vec_Ptr_t *vNodes)
Vec_Ptr_t *	Nwk_ManDfs (Nwk_Man_t *pNtk)
void	Nwk_ManDfsNodes_rec (Nwk_Obj_t *pObj, Vec_Ptr_t *vNodes)
Vec_Ptr_t *	Nwk_ManDfsNodes (Nwk_Man_t *pNtk, Nwk_Obj_t **ppNodes, int nNodes)
void	Nwk_ManDfsReverse_rec (Nwk_Obj_t *pObj, Vec_Ptr_t *vNodes)
Vec_Ptr_t *	Nwk_ManDfsReverse (Nwk_Man_t *pNtk)
void	Nwk_ManSupportNodes_rec (Nwk_Obj_t *pNode, Vec_Ptr_t *vNodes)
Vec_Ptr_t *	Nwk_ManSupportNodes (Nwk_Man_t *pNtk, Nwk_Obj_t **ppNodes, int nNodes)
void	Nwk_ManSupportSum (Nwk_Man_t *pNtk)
int	Nwk_ObjDeref_rec (Nwk_Obj_t *pNode)
int	Nwk_ObjRef_rec (Nwk_Obj_t *pNode)
void	Nwk_ObjMffcLabel_rec (Nwk_Obj_t *pNode, int fTopmost)
int	Nwk_ObjMffcLabel (Nwk_Obj_t *pNode)

Function Documentation

Vec_Ptr_t* Nwk_ManDfs

(

Nwk_Man_t *

pNtk

)

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

Synopsis [Returns the DFS ordered array of all objects except latches.]

Description []

SideEffects []

SeeAlso []

Definition at line 321 of file nwkDfs.c.

{
    Vec_Ptr_t * vNodes;
    Nwk_Obj_t * pObj;
    int i;
    Nwk_ManIncrementTravId( pNtk );
    vNodes = Vec_PtrAlloc( 100 );
    Nwk_ManForEachObj( pNtk, pObj, i )
    {
        if ( Nwk_ObjIsCi(pObj) )
        {
            Nwk_ObjSetTravIdCurrent( pObj );
            Vec_PtrPush( vNodes, pObj );
        }
        else if ( Nwk_ObjIsCo(pObj) )
            Nwk_ManDfs_rec( pObj, vNodes );
    }
    return vNodes;
}

void Nwk_ManDfs_rec	(	Nwk_Obj_t *	pObj,
		Vec_Ptr_t *	vNodes
	)

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

Synopsis [Performs DFS for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 298 of file nwkDfs.c.

{
    Nwk_Obj_t * pNext;
    int i;
    if ( Nwk_ObjIsTravIdCurrent( pObj ) )
        return;
    Nwk_ObjSetTravIdCurrent( pObj );
    Nwk_ObjForEachFanin( pObj, pNext, i )
        Nwk_ManDfs_rec( pNext, vNodes );
    Vec_PtrPush( vNodes, pObj );
}

Vec_Ptr_t* Nwk_ManDfsNodes	(	Nwk_Man_t *	pNtk,
		Nwk_Obj_t **	ppNodes,
		int	nNodes
	)

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

Synopsis [Returns the set of internal nodes rooted in the given nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 378 of file nwkDfs.c.

{
    Vec_Ptr_t * vNodes;
    int i;
    // set the traversal ID
    Nwk_ManIncrementTravId( pNtk );
    // start the array of nodes
    vNodes = Vec_PtrAlloc( 100 );
    // go through the PO nodes and call for each of them
    for ( i = 0; i < nNodes; i++ )
        if ( Nwk_ObjIsCo(ppNodes[i]) )
            Nwk_ManDfsNodes_rec( Nwk_ObjFanin0(ppNodes[i]), vNodes );
        else
            Nwk_ManDfsNodes_rec( ppNodes[i], vNodes );
    return vNodes;
}

void Nwk_ManDfsNodes_rec	(	Nwk_Obj_t *	pObj,
		Vec_Ptr_t *	vNodes
	)

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

Synopsis [Performs DFS for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 352 of file nwkDfs.c.

{
    Nwk_Obj_t * pNext;
    int i;
    if ( Nwk_ObjIsTravIdCurrent( pObj ) )
        return;
    Nwk_ObjSetTravIdCurrent( pObj );
    if ( Nwk_ObjIsCi(pObj) )
        return;
    assert( Nwk_ObjIsNode(pObj) );
    Nwk_ObjForEachFanin( pObj, pNext, i )
        Nwk_ManDfsNodes_rec( pNext, vNodes );
    Vec_PtrPush( vNodes, pObj );
}

Vec_Ptr_t* Nwk_ManDfsReverse

(

Nwk_Man_t *

pNtk

)

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

Synopsis [Returns the DFS ordered array of all objects except latches.]

Description []

SideEffects []

SeeAlso []

Definition at line 451 of file nwkDfs.c.

{
    Vec_Ptr_t * vNodes;
    Nwk_Obj_t * pObj;
    int i;
    Nwk_ManIncrementTravId( pNtk );
    vNodes = Vec_PtrAlloc( 100 );
    Nwk_ManForEachPi( pNtk, pObj, i )
        Nwk_ManDfsReverse_rec( pObj, vNodes );
    // add nodes without fanins
    Nwk_ManForEachNode( pNtk, pObj, i )
        if ( Nwk_ObjFaninNum(pObj) == 0 && !Nwk_ObjIsTravIdCurrent(pObj) )
            Vec_PtrPush( vNodes, pObj );
    return vNodes;
}

void Nwk_ManDfsReverse_rec	(	Nwk_Obj_t *	pObj,
		Vec_Ptr_t *	vNodes
	)

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

Synopsis [Performs DFS for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 406 of file nwkDfs.c.

{
    Nwk_Obj_t * pNext;
    int i, iBox, iTerm1, nTerms;
    if ( Nwk_ObjIsTravIdCurrent( pObj ) )
        return;
    Nwk_ObjSetTravIdCurrent( pObj );
    if ( Nwk_ObjIsCo(pObj) )
    {
        if ( pObj->pMan->pManTime )
        {
            iBox = Tim_ManBoxForCo( pObj->pMan->pManTime, pObj->PioId );
            if ( iBox >= 0 ) // this is not a true PO
            {
                iTerm1 = Tim_ManBoxOutputFirst( pObj->pMan->pManTime, iBox );
                nTerms = Tim_ManBoxOutputNum( pObj->pMan->pManTime, iBox );
                for ( i = 0; i < nTerms; i++ )
                {
                    pNext = Nwk_ManCi(pObj->pMan, iTerm1 + i);
                    Nwk_ManDfsReverse_rec( pNext, vNodes );
                }
            }
        }
    }
    else if ( Nwk_ObjIsNode(pObj) || Nwk_ObjIsCi(pObj) )
    {
        Nwk_ObjForEachFanout( pObj, pNext, i )
            Nwk_ManDfsReverse_rec( pNext, vNodes );
    }
    else
        assert( 0 );
    Vec_PtrPush( vNodes, pObj );
}

int Nwk_ManLevel

(

Nwk_Man_t *

pNtk

)

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

Synopsis [Computes the number of logic levels not counting PIs/POs.]

Description [Does not assume that the objects are in a topo order.]

SideEffects []

SeeAlso []

Definition at line 215 of file nwkDfs.c.

{
    Nwk_Obj_t * pObj;
    int i, LevelMax = 0;
    Nwk_ManForEachObj( pNtk, pObj, i )
        Nwk_ObjSetLevel( pObj, 0 );
    Nwk_ManIncrementTravId( pNtk );
    Nwk_ManForEachPo( pNtk, pObj, i )
    {
        Nwk_ManLevel_rec( pObj );
        if ( LevelMax < Nwk_ObjLevel(pObj) )
            LevelMax = Nwk_ObjLevel(pObj);
    }
    Nwk_ManForEachCi( pNtk, pObj, i )
    {
        Nwk_ManLevel_rec( pObj );
        if ( LevelMax < Nwk_ObjLevel(pObj) )
            LevelMax = Nwk_ObjLevel(pObj);
    }
    return LevelMax;
}

void Nwk_ManLevel_rec

(

Nwk_Obj_t *

pObj

)

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

Synopsis [Computes the number of logic levels not counting PIs/POs.]

Description []

SideEffects []

SeeAlso []

Definition at line 160 of file nwkDfs.c.

{
    Tim_Man_t * pManTime = pObj->pMan->pManTime;
    Nwk_Obj_t * pNext;
    int i, iBox, iTerm1, nTerms, LevelMax = 0;
    if ( Nwk_ObjIsTravIdCurrent( pObj ) )
        return;
    Nwk_ObjSetTravIdCurrent( pObj );
    if ( Nwk_ObjIsCi(pObj) )
    {
        if ( pManTime ) 
        {
            iBox = Tim_ManBoxForCi( pManTime, pObj->PioId );
            if ( iBox >= 0 ) // this is not a true PI
            {
                iTerm1 = Tim_ManBoxInputFirst( pManTime, iBox );
                nTerms = Tim_ManBoxInputNum( pManTime, iBox );
                for ( i = 0; i < nTerms; i++ )
                {
                    pNext = Nwk_ManCo(pObj->pMan, iTerm1 + i);
                    Nwk_ManLevel_rec( pNext );
                    if ( LevelMax < Nwk_ObjLevel(pNext) )
                        LevelMax = Nwk_ObjLevel(pNext);
                }
                LevelMax++;
            }
        }
    }
    else if ( Nwk_ObjIsNode(pObj) || Nwk_ObjIsCo(pObj) )
    {
        Nwk_ObjForEachFanin( pObj, pNext, i )
        {
            Nwk_ManLevel_rec( pNext );
            if ( LevelMax < Nwk_ObjLevel(pNext) )
                LevelMax = Nwk_ObjLevel(pNext);
        }
        if ( Nwk_ObjIsNode(pObj) && Nwk_ObjFaninNum(pObj) > 0 )
            LevelMax++;
    }
    else
        assert( 0 );
    Nwk_ObjSetLevel( pObj, LevelMax );
}

int Nwk_ManLevelBackup

(

Nwk_Man_t *

pNtk

)

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

Synopsis [Computes the number of logic levels not counting PIs/POs.]

Description [Assumes that white boxes have unit level.]

SideEffects []

SeeAlso []

Definition at line 102 of file nwkDfs.c.

{
    Tim_Man_t * pManTimeUnit;
    Nwk_Obj_t * pObj, * pFanin;
    int i, k, LevelMax, Level;
    assert( Nwk_ManVerifyTopoOrder(pNtk) );
    // clean the levels
    Nwk_ManForEachObj( pNtk, pObj, i )
        Nwk_ObjSetLevel( pObj, 0 );
    // perform level computation
    LevelMax = 0;
    pManTimeUnit = pNtk->pManTime ? Tim_ManDup( pNtk->pManTime, 1 ) : NULL;
    if ( pManTimeUnit )
        Tim_ManIncrementTravId( pManTimeUnit );
    Nwk_ManForEachObj( pNtk, pObj, i )
    {
        if ( Nwk_ObjIsCi(pObj) )
        {
            Level = pManTimeUnit? (int)Tim_ManGetCiArrival( pManTimeUnit, pObj->PioId ) : 0;
            Nwk_ObjSetLevel( pObj, Level );
        }
        else if ( Nwk_ObjIsCo(pObj) )
        {
            Level = Nwk_ObjLevel( Nwk_ObjFanin0(pObj) );
            if ( pManTimeUnit )
                Tim_ManSetCoArrival( pManTimeUnit, pObj->PioId, (float)Level );
            Nwk_ObjSetLevel( pObj, Level );
            if ( LevelMax < Nwk_ObjLevel(pObj) )
                LevelMax = Nwk_ObjLevel(pObj);
        }
        else if ( Nwk_ObjIsNode(pObj) )
        {
            Level = 0;
            Nwk_ObjForEachFanin( pObj, pFanin, k )
                if ( Level < Nwk_ObjLevel(pFanin) )
                    Level = Nwk_ObjLevel(pFanin);
            Nwk_ObjSetLevel( pObj, Level + 1 );
        }
        else
            assert( 0 );
    }
    // set the old timing manager
    if ( pManTimeUnit )
        Tim_ManStop( pManTimeUnit );
    return LevelMax;
}

Vec_Vec_t* Nwk_ManLevelize

(

Nwk_Man_t *

pNtk

)

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

Synopsis [Returns the array of objects in the AIG manager ordered by level.]

Description []

SideEffects []

SeeAlso []

Definition at line 269 of file nwkDfs.c.

{
    Nwk_Obj_t * pObj;
    Vec_Vec_t * vLevels;
    int nLevels, i;
    assert( Nwk_ManVerifyLevel(pNtk) );
    nLevels = Nwk_ManLevelMax( pNtk );
    vLevels = Vec_VecStart( nLevels + 1 );
    Nwk_ManForEachNode( pNtk, pObj, i )
    {
        assert( Nwk_ObjLevel(pObj) <= nLevels );
        Vec_VecPush( vLevels, Nwk_ObjLevel(pObj), pObj );
    }
    return vLevels;
}

int Nwk_ManLevelMax

(

Nwk_Man_t *

pNtk

)

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

Synopsis [Computes the number of logic levels not counting PIs/POs.]

Description [Does not assume that the objects are in a topo order.]

SideEffects []

SeeAlso []

Definition at line 248 of file nwkDfs.c.

{
    Nwk_Obj_t * pObj;
    int i, LevelMax = 0;
    Nwk_ManForEachPo( pNtk, pObj, i )
        if ( LevelMax < Nwk_ObjLevel(pObj) )
            LevelMax = Nwk_ObjLevel(pObj);
    return LevelMax;
}

Vec_Ptr_t* Nwk_ManSupportNodes	(	Nwk_Man_t *	pNtk,
		Nwk_Obj_t **	ppNodes,
		int	nNodes
	)

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

Synopsis [Returns the set of CI nodes in the support of the given nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 510 of file nwkDfs.c.

{
    Vec_Ptr_t * vNodes;
    int i;
    // set the traversal ID
    Nwk_ManIncrementTravId( pNtk );
    // start the array of nodes
    vNodes = Vec_PtrAlloc( 100 );
    // go through the PO nodes and call for each of them
    for ( i = 0; i < nNodes; i++ )
        if ( Nwk_ObjIsCo(ppNodes[i]) )
            Nwk_ManSupportNodes_rec( Nwk_ObjFanin0(ppNodes[i]), vNodes );
        else
            Nwk_ManSupportNodes_rec( ppNodes[i], vNodes );
    return vNodes;
}

void Nwk_ManSupportNodes_rec	(	Nwk_Obj_t *	pNode,
		Vec_Ptr_t *	vNodes
	)

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

Synopsis [Performs DFS for one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 478 of file nwkDfs.c.

{
    Nwk_Obj_t * pFanin;
    int i;
    // if this node is already visited, skip
    if ( Nwk_ObjIsTravIdCurrent( pNode ) )
        return;
    // mark the node as visited
    Nwk_ObjSetTravIdCurrent( pNode );
    // collect the CI
    if ( Nwk_ObjIsCi(pNode) )
    {
        Vec_PtrPush( vNodes, pNode );
        return;
    }
    assert( Nwk_ObjIsNode( pNode ) );
    // visit the transitive fanin of the node
    Nwk_ObjForEachFanin( pNode, pFanin, i )
        Nwk_ManSupportNodes_rec( pFanin, vNodes );
}

void Nwk_ManSupportSum

(

Nwk_Man_t *

pNtk

)

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

Synopsis [Computes the sum total of supports of all outputs.]

Description []

SideEffects []

SeeAlso []

Definition at line 538 of file nwkDfs.c.

{
    Vec_Ptr_t * vSupp;
    Nwk_Obj_t * pObj;
    int i, nTotalSupps = 0;
    Nwk_ManForEachCo( pNtk, pObj, i )
    {
        vSupp = Nwk_ManSupportNodes( pNtk, &pObj, 1 );
        nTotalSupps += Vec_PtrSize( vSupp );
        Vec_PtrFree( vSupp );
    }
    printf( "Total supports = %d.\n", nTotalSupps );
}

ABC_NAMESPACE_IMPL_START int Nwk_ManVerifyTopoOrder

(

Nwk_Man_t *

pNtk

)

DECLARATIONS ///.

CFile****************************************************************

FileName [nwkDfs.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Logic network representation.]

Synopsis [DFS traversals.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - June 20, 2005.]

Revision [

Id:

nwkDfs.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

]FUNCTION DEFINITIONS /// Function*************************************************************

Synopsis [Verifies that the objects are in a topo order.]

Description []

SideEffects []

SeeAlso []

Definition at line 45 of file nwkDfs.c.

{
    Nwk_Obj_t * pObj, * pNext;
    int i, k, iBox, iTerm1, nTerms;
    Nwk_ManIncrementTravId( pNtk );
    Nwk_ManForEachObj( pNtk, pObj, i )
    {
        if ( Nwk_ObjIsNode(pObj) || Nwk_ObjIsCo(pObj) )
        {
            Nwk_ObjForEachFanin( pObj, pNext, k )
            {
                if ( !Nwk_ObjIsTravIdCurrent(pNext) )
                {
                    printf( "Node %d has fanin %d that is not in a topological order.\n", pObj->Id, pNext->Id );
                    return 0;
                }
            }
        }
        else if ( Nwk_ObjIsCi(pObj) )
        {
            if ( pNtk->pManTime )
            {
                iBox = Tim_ManBoxForCi( pNtk->pManTime, pObj->PioId );
                if ( iBox >= 0 ) // this is not a true PI
                {
                    iTerm1 = Tim_ManBoxInputFirst( pNtk->pManTime, iBox );
                    nTerms = Tim_ManBoxInputNum( pNtk->pManTime, iBox );
                    for ( k = 0; k < nTerms; k++ )
                    {
                        pNext = Nwk_ManCo( pNtk, iTerm1 + k );
                        if ( !Nwk_ObjIsTravIdCurrent(pNext) )
                        {
                            printf( "Box %d has input %d that is not in a topological order.\n", iBox, pNext->Id );
                            return 0;
                        }
                    }
                }
            }
        }
        else
            assert( 0 );
        Nwk_ObjSetTravIdCurrent( pObj );
    }
    return 1;
}

int Nwk_ObjDeref_rec

(

Nwk_Obj_t *

pNode

)

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

Synopsis [Dereferences the node's MFFC.]

Description []

SideEffects []

SeeAlso []

Definition at line 564 of file nwkDfs.c.

{
    Nwk_Obj_t * pFanin;
    int i, Counter = 1;
    if ( Nwk_ObjIsCi(pNode) )
        return 0;
    Nwk_ObjForEachFanin( pNode, pFanin, i )
    {
        assert( pFanin->nFanouts > 0 );
        if ( --pFanin->nFanouts == 0 )
            Counter += Nwk_ObjDeref_rec( pFanin );
    }
    return Counter;
}

int Nwk_ObjMffcLabel

(

Nwk_Obj_t *

pNode

)

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

Synopsis [Collects the internal nodes of the MFFC limited by cut.]

Description []

SideEffects [Increments the trav ID and marks visited nodes.]

SeeAlso []

Definition at line 644 of file nwkDfs.c.

{
    int Count1, Count2;
    // dereference the node
    Count1 = Nwk_ObjDeref_rec( pNode );
    // collect the nodes inside the MFFC
    Nwk_ManIncrementTravId( pNode->pMan );
    Nwk_ObjMffcLabel_rec( pNode, 1 );
    // reference it back
    Count2 = Nwk_ObjRef_rec( pNode );
    assert( Count1 == Count2 );
    return Count1;
}

void Nwk_ObjMffcLabel_rec	(	Nwk_Obj_t *	pNode,
		int	fTopmost
	)

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

Synopsis [Collects the internal and boundary nodes in the derefed MFFC.]

Description []

SideEffects []

SeeAlso []

Definition at line 615 of file nwkDfs.c.

{
    Nwk_Obj_t * pFanin;
    int i;
    // add to the new support nodes
    if ( !fTopmost && (Nwk_ObjIsCi(pNode) || pNode->nFanouts > 0) )
        return;
    // skip visited nodes
    if ( Nwk_ObjIsTravIdCurrent(pNode) )
        return;
    Nwk_ObjSetTravIdCurrent(pNode);
    // recur on the children
    Nwk_ObjForEachFanin( pNode, pFanin, i )
        Nwk_ObjMffcLabel_rec( pFanin, 0 );
    // collect the internal node
//    printf( "%d ", pNode->Id );
}

int Nwk_ObjRef_rec

(

Nwk_Obj_t *

pNode

)

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

Synopsis [References the node's MFFC.]

Description []

SideEffects []

SeeAlso []

Definition at line 590 of file nwkDfs.c.

{
    Nwk_Obj_t * pFanin;
    int i, Counter = 1;
    if ( Nwk_ObjIsCi(pNode) )
        return 0;
    Nwk_ObjForEachFanin( pNode, pFanin, i )
    {
        if ( pFanin->nFanouts++ == 0 )
            Counter += Nwk_ObjRef_rec( pFanin );
    }
    return Counter;
}