/**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 $]
***********************************************************************/
#include "nwk.h"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Verifies that the objects are in a topo order.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Nwk_ManVerifyTopoOrder( Nwk_Man_t * pNtk )
{
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;
}
/**Function*************************************************************
Synopsis [Computes the number of logic levels not counting PIs/POs.]
Description [Assumes that white boxes have unit level.]
SideEffects []
SeeAlso []
***********************************************************************/
int Nwk_ManLevelBackup( Nwk_Man_t * pNtk )
{
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;
}
/**Function*************************************************************
Synopsis [Computes the number of logic levels not counting PIs/POs.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Nwk_ManLevel_rec( Nwk_Obj_t * pObj )
{
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 );
}
/**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 []
***********************************************************************/
int Nwk_ManLevel( Nwk_Man_t * pNtk )
{
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;
}
/**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 []
***********************************************************************/
int Nwk_ManLevelMax( Nwk_Man_t * pNtk )
{
Nwk_Obj_t * pObj;
int i, LevelMax = 0;
Nwk_ManForEachPo( pNtk, pObj, i )
if ( LevelMax < Nwk_ObjLevel(pObj) )
LevelMax = Nwk_ObjLevel(pObj);
return LevelMax;
}
/**Function*************************************************************
Synopsis [Returns the array of objects in the AIG manager ordered by level.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Vec_Vec_t * Nwk_ManLevelize( Nwk_Man_t * pNtk )
{
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;
}
/**Function*************************************************************
Synopsis [Performs DFS for one node.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Nwk_ManDfs_rec( Nwk_Obj_t * pObj, Vec_Ptr_t * vNodes )
{
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 );
}
/**Function*************************************************************
Synopsis [Returns the DFS ordered array of all objects except latches.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Vec_Ptr_t * Nwk_ManDfs( Nwk_Man_t * pNtk )
{
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;
}
/**Function*************************************************************
Synopsis [Performs DFS for one node.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Nwk_ManDfsNodes_rec( Nwk_Obj_t * pObj, Vec_Ptr_t * vNodes )
{
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 );
}
/**Function*************************************************************
Synopsis [Returns the set of internal nodes rooted in the given nodes.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Vec_Ptr_t * Nwk_ManDfsNodes( Nwk_Man_t * pNtk, Nwk_Obj_t ** ppNodes, int nNodes )
{
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;
}
/**Function*************************************************************
Synopsis [Performs DFS for one node.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Nwk_ManDfsReverse_rec( Nwk_Obj_t * pObj, Vec_Ptr_t * vNodes )
{
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 );
}
/**Function*************************************************************
Synopsis [Returns the DFS ordered array of all objects except latches.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Vec_Ptr_t * Nwk_ManDfsReverse( Nwk_Man_t * pNtk )
{
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;
}
/**Function*************************************************************
Synopsis [Performs DFS for one node.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Nwk_ManSupportNodes_rec( Nwk_Obj_t * pNode, Vec_Ptr_t * vNodes )
{
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 );
}
/**Function*************************************************************
Synopsis [Returns the set of CI nodes in the support of the given nodes.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Vec_Ptr_t * Nwk_ManSupportNodes( Nwk_Man_t * pNtk, Nwk_Obj_t ** ppNodes, int nNodes )
{
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;
}
/**Function*************************************************************
Synopsis [Computes the sum total of supports of all outputs.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Nwk_ManSupportSum( Nwk_Man_t * pNtk )
{
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 );
}
/**Function*************************************************************
Synopsis [Dereferences the node's MFFC.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Nwk_ObjDeref_rec( Nwk_Obj_t * pNode )
{
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;
}
/**Function*************************************************************
Synopsis [References the node's MFFC.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Nwk_ObjRef_rec( Nwk_Obj_t * pNode )
{
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;
}
/**Function*************************************************************
Synopsis [Collects the internal and boundary nodes in the derefed MFFC.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Nwk_ObjMffcLabel_rec( Nwk_Obj_t * pNode, int fTopmost )
{
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 );
}
/**Function*************************************************************
Synopsis [Collects the internal nodes of the MFFC limited by cut.]
Description []
SideEffects [Increments the trav ID and marks visited nodes.]
SeeAlso []
***********************************************************************/
int Nwk_ObjMffcLabel( Nwk_Obj_t * pNode )
{
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;
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END