/**CFile****************************************************************
FileName [seqUtil.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [Construction and manipulation of sequential AIGs.]
Synopsis [Various utilities working with sequential AIGs.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - June 20, 2005.]
Revision [$Id: seqUtil.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
***********************************************************************/
#include "seqInt.h"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Returns the maximum latch number on any of the fanouts.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Seq_NtkLevelMax( Abc_Ntk_t * pNtk )
{
Abc_Obj_t * pNode;
int i, Result;
assert( Abc_NtkIsSeq(pNtk) );
Result = 0;
Abc_NtkForEachPo( pNtk, pNode, i )
{
pNode = Abc_ObjFanin0(pNode);
if ( Result < (int)pNode->Level )
Result = pNode->Level;
}
Abc_SeqForEachCutsetNode( pNtk, pNode, i )
{
if ( Result < (int)pNode->Level )
Result = pNode->Level;
}
return Result;
}
/**Function*************************************************************
Synopsis [Returns the maximum latch number on any of the fanouts.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Seq_ObjFanoutLMax( Abc_Obj_t * pObj )
{
Abc_Obj_t * pFanout;
int i, nLatchCur, nLatchRes;
if ( Abc_ObjFanoutNum(pObj) == 0 )
return 0;
nLatchRes = 0;
Abc_ObjForEachFanout( pObj, pFanout, i )
{
nLatchCur = Seq_ObjFanoutL(pObj, pFanout);
if ( nLatchRes < nLatchCur )
nLatchRes = nLatchCur;
}
assert( nLatchRes >= 0 );
return nLatchRes;
}
/**Function*************************************************************
Synopsis [Returns the minimum latch number on any of the fanouts.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Seq_ObjFanoutLMin( Abc_Obj_t * pObj )
{
Abc_Obj_t * pFanout;
int i, nLatchCur, nLatchRes;
if ( Abc_ObjFanoutNum(pObj) == 0 )
return 0;
nLatchRes = ABC_INFINITY;
Abc_ObjForEachFanout( pObj, pFanout, i )
{
nLatchCur = Seq_ObjFanoutL(pObj, pFanout);
if ( nLatchRes > nLatchCur )
nLatchRes = nLatchCur;
}
assert( nLatchRes < ABC_INFINITY );
return nLatchRes;
}
/**Function*************************************************************
Synopsis [Returns the sum of latches on the fanout edges.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Seq_ObjFanoutLSum( Abc_Obj_t * pObj )
{
Abc_Obj_t * pFanout;
int i, nSum = 0;
Abc_ObjForEachFanout( pObj, pFanout, i )
nSum += Seq_ObjFanoutL(pObj, pFanout);
return nSum;
}
/**Function*************************************************************
Synopsis [Returns the sum of latches on the fanin edges.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Seq_ObjFaninLSum( Abc_Obj_t * pObj )
{
Abc_Obj_t * pFanin;
int i, nSum = 0;
Abc_ObjForEachFanin( pObj, pFanin, i )
nSum += Seq_ObjFaninL(pObj, i);
return nSum;
}
/**Function*************************************************************
Synopsis [Generates the printable edge label with the initial state.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
char * Seq_ObjFaninGetInitPrintable( Abc_Obj_t * pObj, int Edge )
{
static char Buffer[1000];
Abc_InitType_t Init;
int nLatches, i;
nLatches = Seq_ObjFaninL( pObj, Edge );
for ( i = 0; i < nLatches; i++ )
{
Init = Seq_LatInit( Seq_NodeGetLat(pObj, Edge, i) );
if ( Init == ABC_INIT_NONE )
Buffer[i] = '_';
else if ( Init == ABC_INIT_ZERO )
Buffer[i] = '0';
else if ( Init == ABC_INIT_ONE )
Buffer[i] = '1';
else if ( Init == ABC_INIT_DC )
Buffer[i] = 'x';
else assert( 0 );
}
Buffer[nLatches] = 0;
return Buffer;
}
/**Function*************************************************************
Synopsis [Sets the given value to all the latches of the edge.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Seq_NodeLatchSetValues( Abc_Obj_t * pObj, int Edge, Abc_InitType_t Init )
{
Seq_Lat_t * pLat, * pRing;
int c;
pRing = Seq_NodeGetRing(pObj, Edge);
if ( pRing == NULL )
return;
for ( c = 0, pLat = pRing; !c || pLat != pRing; c++, pLat = pLat->pNext )
Seq_LatSetInit( pLat, Init );
}
/**Function*************************************************************
Synopsis [Sets the given value to all the latches of the edge.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Seq_NtkLatchSetValues( Abc_Ntk_t * pNtk, Abc_InitType_t Init )
{
Abc_Obj_t * pObj;
int i;
assert( Abc_NtkIsSeq( pNtk ) );
Abc_NtkForEachPo( pNtk, pObj, i )
Seq_NodeLatchSetValues( pObj, 0, Init );
Abc_NtkForEachNode( pNtk, pObj, i )
{
Seq_NodeLatchSetValues( pObj, 0, Init );
Seq_NodeLatchSetValues( pObj, 1, Init );
}
}
/**Function*************************************************************
Synopsis [Counts the number of latches in the sequential AIG.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Seq_NtkLatchNum( Abc_Ntk_t * pNtk )
{
Abc_Obj_t * pObj;
int i, Counter;
assert( Abc_NtkIsSeq( pNtk ) );
Counter = 0;
Abc_NtkForEachNode( pNtk, pObj, i )
Counter += Seq_ObjFaninLSum( pObj );
Abc_NtkForEachPo( pNtk, pObj, i )
Counter += Seq_ObjFaninLSum( pObj );
return Counter;
}
/**Function*************************************************************
Synopsis [Counts the number of latches in the sequential AIG.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Seq_NtkLatchNumMax( Abc_Ntk_t * pNtk )
{
Abc_Obj_t * pObj;
int i, Max, Cur;
assert( Abc_NtkIsSeq( pNtk ) );
Max = 0;
Abc_AigForEachAnd( pNtk, pObj, i )
{
Cur = Seq_ObjFaninLMax( pObj );
if ( Max < Cur )
Max = Cur;
}
Abc_NtkForEachPo( pNtk, pObj, i )
{
Cur = Seq_ObjFaninL0( pObj );
if ( Max < Cur )
Max = Cur;
}
return Max;
}
/**Function*************************************************************
Synopsis [Counts the number of latches in the sequential AIG.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Seq_NtkLatchNumShared( Abc_Ntk_t * pNtk )
{
Abc_Obj_t * pObj;
int i, Counter;
assert( Abc_NtkIsSeq( pNtk ) );
Counter = 0;
Abc_NtkForEachPi( pNtk, pObj, i )
Counter += Seq_ObjFanoutLMax( pObj );
Abc_NtkForEachNode( pNtk, pObj, i )
Counter += Seq_ObjFanoutLMax( pObj );
return Counter;
}
/**Function*************************************************************
Synopsis [Counts the number of latches in the sequential AIG.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Seq_ObjLatchGetInitNums( Abc_Obj_t * pObj, int Edge, int * pInits )
{
Abc_InitType_t Init;
int nLatches, i;
nLatches = Seq_ObjFaninL( pObj, Edge );
for ( i = 0; i < nLatches; i++ )
{
Init = Seq_NodeGetInitOne( pObj, Edge, i );
pInits[Init]++;
}
}
/**Function*************************************************************
Synopsis [Counts the number of latches in the sequential AIG.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Seq_NtkLatchGetInitNums( Abc_Ntk_t * pNtk, int * pInits )
{
Abc_Obj_t * pObj;
int i;
assert( Abc_NtkIsSeq( pNtk ) );
for ( i = 0; i < 4; i++ )
pInits[i] = 0;
Abc_NtkForEachPo( pNtk, pObj, i )
Seq_ObjLatchGetInitNums( pObj, 0, pInits );
Abc_NtkForEachNode( pNtk, pObj, i )
{
if ( Abc_ObjFaninNum(pObj) > 0 )
Seq_ObjLatchGetInitNums( pObj, 0, pInits );
if ( Abc_ObjFaninNum(pObj) > 1 )
Seq_ObjLatchGetInitNums( pObj, 1, pInits );
}
}
/**Function*************************************************************
Synopsis [Report nodes with equal fanins.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Seq_NtkLatchGetEqualFaninNum( Abc_Ntk_t * pNtk )
{
Abc_Obj_t * pObj;
int i, Counter;
assert( Abc_NtkIsSeq( pNtk ) );
Counter = 0;
Abc_AigForEachAnd( pNtk, pObj, i )
if ( Abc_ObjFaninId0(pObj) == Abc_ObjFaninId1(pObj) )
Counter++;
if ( Counter )
printf( "The number of nodes with equal fanins = %d.\n", Counter );
return Counter;
}
/**Function*************************************************************
Synopsis [Returns the maximum latch number on any of the fanouts.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Seq_NtkCountNodesAboveLimit( Abc_Ntk_t * pNtk, int Limit )
{
Abc_Obj_t * pNode;
int i, Counter;
assert( !Abc_NtkIsSeq(pNtk) );
Counter = 0;
Abc_NtkForEachNode( pNtk, pNode, i )
if ( Abc_ObjFaninNum(pNode) > Limit )
Counter++;
return Counter;
}
/**Function*************************************************************
Synopsis [Computes area flows.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Seq_MapComputeAreaFlows( Abc_Ntk_t * pNtk, int fVerbose )
{
Abc_Seq_t * p = pNtk->pManFunc;
Abc_Obj_t * pObj;
float AFlow;
int i, c;
assert( Abc_NtkIsSeq(pNtk) );
Vec_IntFill( p->vAFlows, p->nSize, Abc_Float2Int( (float)0.0 ) );
// update all values iteratively
for ( c = 0; c < 7; c++ )
{
Abc_AigForEachAnd( pNtk, pObj, i )
{
AFlow = (float)1.0 + Seq_NodeGetFlow( Abc_ObjFanin0(pObj) ) + Seq_NodeGetFlow( Abc_ObjFanin1(pObj) );
AFlow /= Abc_ObjFanoutNum(pObj);
pObj->pNext = (void *)Abc_Float2Int( AFlow );
}
Abc_AigForEachAnd( pNtk, pObj, i )
{
AFlow = Abc_Int2Float( (int)pObj->pNext );
pObj->pNext = NULL;
Seq_NodeSetFlow( pObj, AFlow );
// printf( "%5d : %6.1f\n", pObj->Id, Seq_NodeGetFlow(pObj) );
}
// printf( "\n" );
}
return 1;
}
/**Function*************************************************************
Synopsis [Collects all the internal nodes reachable from POs.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Seq_NtkReachNodesFromPos_rec( Abc_Obj_t * pAnd, Vec_Ptr_t * vNodes )
{
// skip if this is a non-PI node
if ( !Abc_AigNodeIsAnd(pAnd) )
return;
// skip a visited node
if ( Abc_NodeIsTravIdCurrent(pAnd) )
return;
Abc_NodeSetTravIdCurrent(pAnd);
// visit the fanin nodes
Seq_NtkReachNodesFromPos_rec( Abc_ObjFanin0(pAnd), vNodes );
Seq_NtkReachNodesFromPos_rec( Abc_ObjFanin1(pAnd), vNodes );
// add this node
Vec_PtrPush( vNodes, pAnd );
}
/**Function*************************************************************
Synopsis [Collects all the internal nodes reachable from POs.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Seq_NtkReachNodesFromPis_rec( Abc_Obj_t * pAnd, Vec_Ptr_t * vNodes )
{
Abc_Obj_t * pFanout;
int k;
// skip if this is a non-PI node
if ( !Abc_AigNodeIsAnd(pAnd) )
return;
// skip a visited node
if ( Abc_NodeIsTravIdCurrent(pAnd) )
return;
Abc_NodeSetTravIdCurrent(pAnd);
// visit the fanin nodes
Abc_ObjForEachFanout( pAnd, pFanout, k )
Seq_NtkReachNodesFromPis_rec( pFanout, vNodes );
// add this node
Vec_PtrPush( vNodes, pAnd );
}
/**Function*************************************************************
Synopsis [Collects all the internal nodes reachable from POs.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Vec_Ptr_t * Seq_NtkReachNodes( Abc_Ntk_t * pNtk, int fFromPos )
{
Vec_Ptr_t * vNodes;
Abc_Obj_t * pObj, * pFanout;
int i, k;
assert( Abc_NtkIsSeq(pNtk) );
vNodes = Vec_PtrAlloc( 1000 );
Abc_NtkIncrementTravId( pNtk );
if ( fFromPos )
{
// traverse the cone of each PO
Abc_NtkForEachPo( pNtk, pObj, i )
Seq_NtkReachNodesFromPos_rec( Abc_ObjFanin0(pObj), vNodes );
}
else
{
// tranvers the reverse cone of the constant node
pObj = Abc_AigConst1( pNtk );
Abc_ObjForEachFanout( pObj, pFanout, k )
Seq_NtkReachNodesFromPis_rec( pFanout, vNodes );
// tranvers the reverse cone of the PIs
Abc_NtkForEachPi( pNtk, pObj, i )
Abc_ObjForEachFanout( pObj, pFanout, k )
Seq_NtkReachNodesFromPis_rec( pFanout, vNodes );
}
return vNodes;
}
/**Function*************************************************************
Synopsis [Perform sequential cleanup.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Seq_NtkCleanup( Abc_Ntk_t * pNtk, int fVerbose )
{
Vec_Ptr_t * vNodesPo, * vNodesPi;
int Counter = 0;
assert( Abc_NtkIsSeq(pNtk) );
// collect the nodes reachable from POs and PIs
vNodesPo = Seq_NtkReachNodes( pNtk, 1 );
vNodesPi = Seq_NtkReachNodes( pNtk, 0 );
printf( "Total nodes = %6d. Reachable from POs = %6d. Reachable from PIs = %6d.\n",
Abc_NtkNodeNum(pNtk), Vec_PtrSize(vNodesPo), Vec_PtrSize(vNodesPi) );
if ( Abc_NtkNodeNum(pNtk) > Vec_PtrSize(vNodesPo) )
{
// Counter = Abc_NtkReduceNodes( pNtk, vNodesPo );
Counter = 0;
if ( fVerbose )
printf( "Cleanup removed %d nodes that are not reachable from the POs.\n", Counter );
}
Vec_PtrFree( vNodesPo );
Vec_PtrFree( vNodesPi );
return Counter;
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END