abcBridge-0.10.0.0: abc-build/src/base/abc/abcRefs.c
/**CFile****************************************************************
FileName [abcRefs.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [Network and node package.]
Synopsis [Procedures using reference counting of the AIG nodes.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - June 20, 2005.]
Revision [$Id: abcRefs.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
***********************************************************************/
#include "abc.h"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
static int Abc_NodeRefDeref( Abc_Obj_t * pNode, int fReference, int fLabel );
static int Abc_NodeRefDerefStop( Abc_Obj_t * pNode, int fReference );
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Returns the MFFC size.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NodeMffcSize( Abc_Obj_t * pNode )
{
int nConeSize1, nConeSize2;
// assert( Abc_NtkIsStrash(pNode->pNtk) );
// assert( !Abc_ObjIsComplement( pNode ) );
assert( Abc_ObjIsNode( pNode ) );
if ( Abc_ObjFaninNum(pNode) == 0 )
return 0;
nConeSize1 = Abc_NodeRefDeref( pNode, 0, 0 ); // dereference
nConeSize2 = Abc_NodeRefDeref( pNode, 1, 0 ); // reference
assert( nConeSize1 == nConeSize2 );
assert( nConeSize1 > 0 );
return nConeSize1;
}
/**Function*************************************************************
Synopsis [Returns the MFFC size while stopping at the complemented edges.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NodeMffcSizeStop( Abc_Obj_t * pNode )
{
int nConeSize1, nConeSize2;
assert( Abc_NtkIsStrash(pNode->pNtk) );
assert( !Abc_ObjIsComplement( pNode ) );
assert( Abc_ObjIsNode( pNode ) );
if ( Abc_ObjFaninNum(pNode) == 0 )
return 0;
nConeSize1 = Abc_NodeRefDerefStop( pNode, 0 ); // dereference
nConeSize2 = Abc_NodeRefDerefStop( pNode, 1 ); // reference
assert( nConeSize1 == nConeSize2 );
assert( nConeSize1 > 0 );
return nConeSize1;
}
/**Function*************************************************************
Synopsis [Labels MFFC with the current traversal ID.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NodeMffcLabelAig( Abc_Obj_t * pNode )
{
int nConeSize1, nConeSize2;
assert( Abc_NtkIsStrash(pNode->pNtk) );
assert( !Abc_ObjIsComplement( pNode ) );
assert( Abc_ObjIsNode( pNode ) );
if ( Abc_ObjFaninNum(pNode) == 0 )
return 0;
nConeSize1 = Abc_NodeRefDeref( pNode, 0, 1 ); // dereference
nConeSize2 = Abc_NodeRefDeref( pNode, 1, 0 ); // reference
assert( nConeSize1 == nConeSize2 );
assert( nConeSize1 > 0 );
return nConeSize1;
}
/**Function*************************************************************
Synopsis [References/references the node and returns MFFC size.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NodeRefDeref( Abc_Obj_t * pNode, int fReference, int fLabel )
{
Abc_Obj_t * pNode0, * pNode1;
int Counter;
// label visited nodes
if ( fLabel )
Abc_NodeSetTravIdCurrent( pNode );
// skip the CI
if ( Abc_ObjIsCi(pNode) )
return 0;
// process the internal node
pNode0 = Abc_ObjFanin0(pNode);
pNode1 = Abc_ObjFanin1(pNode);
Counter = 1;
if ( fReference )
{
if ( pNode0->vFanouts.nSize++ == 0 )
Counter += Abc_NodeRefDeref( pNode0, fReference, fLabel );
if ( pNode1->vFanouts.nSize++ == 0 )
Counter += Abc_NodeRefDeref( pNode1, fReference, fLabel );
}
else
{
assert( pNode0->vFanouts.nSize > 0 );
assert( pNode1->vFanouts.nSize > 0 );
if ( --pNode0->vFanouts.nSize == 0 )
Counter += Abc_NodeRefDeref( pNode0, fReference, fLabel );
if ( --pNode1->vFanouts.nSize == 0 )
Counter += Abc_NodeRefDeref( pNode1, fReference, fLabel );
}
return Counter;
}
/**Function*************************************************************
Synopsis [References/references the node and returns MFFC size.]
Description [Stops at the complemented edges.]
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NodeRefDerefStop( Abc_Obj_t * pNode, int fReference )
{
Abc_Obj_t * pNode0, * pNode1;
int Counter;
// skip the CI
if ( Abc_ObjIsCi(pNode) )
return 0;
// process the internal node
pNode0 = Abc_ObjFanin0(pNode);
pNode1 = Abc_ObjFanin1(pNode);
Counter = 1;
if ( fReference )
{
if ( !Abc_ObjFaninC0(pNode) && pNode0->vFanouts.nSize++ == 0 )
Counter += Abc_NodeRefDerefStop( pNode0, fReference );
if ( !Abc_ObjFaninC1(pNode) && pNode1->vFanouts.nSize++ == 0 )
Counter += Abc_NodeRefDerefStop( pNode1, fReference );
}
else
{
assert( pNode0->vFanouts.nSize > 0 );
assert( pNode1->vFanouts.nSize > 0 );
if ( !Abc_ObjFaninC0(pNode) && --pNode0->vFanouts.nSize == 0 )
Counter += Abc_NodeRefDerefStop( pNode0, fReference );
if ( !Abc_ObjFaninC1(pNode) && --pNode1->vFanouts.nSize == 0 )
Counter += Abc_NodeRefDerefStop( pNode1, fReference );
}
return Counter;
}
/**Function*************************************************************
Synopsis [Dereferences the node's MFFC.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NodeDeref_rec( Abc_Obj_t * pNode )
{
Abc_Obj_t * pFanin;
int i, Counter = 1;
if ( Abc_ObjIsCi(pNode) )
return 0;
Abc_ObjForEachFanin( pNode, pFanin, i )
{
assert( pFanin->vFanouts.nSize > 0 );
if ( --pFanin->vFanouts.nSize == 0 )
Counter += Abc_NodeDeref_rec( pFanin );
}
return Counter;
}
/**Function*************************************************************
Synopsis [References the node's MFFC.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_NodeRef_rec( Abc_Obj_t * pNode )
{
Abc_Obj_t * pFanin;
int i, Counter = 1;
if ( Abc_ObjIsCi(pNode) )
return 0;
Abc_ObjForEachFanin( pNode, pFanin, i )
{
if ( pFanin->vFanouts.nSize++ == 0 )
Counter += Abc_NodeRef_rec( pFanin );
}
return Counter;
}
/**Function*************************************************************
Synopsis [Collects the internal and boundary nodes in the derefed MFFC.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_NodeMffcConeSupp_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vCone, Vec_Ptr_t * vSupp, int fTopmost )
{
Abc_Obj_t * pFanin;
int i;
// skip visited nodes
if ( Abc_NodeIsTravIdCurrent(pNode) )
return;
Abc_NodeSetTravIdCurrent(pNode);
// add to the new support nodes
if ( !fTopmost && (Abc_ObjIsCi(pNode) || pNode->vFanouts.nSize > 0) )
{
if ( vSupp ) Vec_PtrPush( vSupp, pNode );
return;
}
// recur on the children
Abc_ObjForEachFanin( pNode, pFanin, i )
Abc_NodeMffcConeSupp_rec( pFanin, vCone, vSupp, 0 );
// collect the internal node
if ( vCone ) Vec_PtrPush( vCone, pNode );
// printf( "%d ", pNode->Id );
}
/**Function*************************************************************
Synopsis [Collects the support of the derefed MFFC.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_NodeMffcConeSupp( Abc_Obj_t * pNode, Vec_Ptr_t * vCone, Vec_Ptr_t * vSupp )
{
assert( Abc_ObjIsNode(pNode) );
assert( !Abc_ObjIsComplement(pNode) );
if ( vCone ) Vec_PtrClear( vCone );
if ( vSupp ) Vec_PtrClear( vSupp );
Abc_NtkIncrementTravId( pNode->pNtk );
Abc_NodeMffcConeSupp_rec( pNode, vCone, vSupp, 1 );
// printf( "\n" );
}
/**Function*************************************************************
Synopsis [Collects the support of the derefed MFFC.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_NodeMffcConeSuppPrint( Abc_Obj_t * pNode )
{
Vec_Ptr_t * vCone, * vSupp;
Abc_Obj_t * pObj;
int i;
vCone = Vec_PtrAlloc( 100 );
vSupp = Vec_PtrAlloc( 100 );
Abc_NodeDeref_rec( pNode );
Abc_NodeMffcConeSupp( pNode, vCone, vSupp );
Abc_NodeRef_rec( pNode );
printf( "Node = %6s : Supp = %3d Cone = %3d (",
Abc_ObjName(pNode), Vec_PtrSize(vSupp), Vec_PtrSize(vCone) );
Vec_PtrForEachEntry( Abc_Obj_t *, vCone, pObj, i )
printf( " %s", Abc_ObjName(pObj) );
printf( " )\n" );
Vec_PtrFree( vCone );
Vec_PtrFree( vSupp );
}
/**Function*************************************************************
Synopsis [Collects the internal nodes of the MFFC limited by cut.]
Description []
SideEffects [Increments the trav ID and marks visited nodes.]
SeeAlso []
***********************************************************************/
int Abc_NodeMffcInside( Abc_Obj_t * pNode, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vInside )
{
Abc_Obj_t * pObj;
int i, Count1, Count2;
// increment the fanout counters for the leaves
Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
pObj->vFanouts.nSize++;
// dereference the node
Count1 = Abc_NodeDeref_rec( pNode );
// collect the nodes inside the MFFC
Abc_NodeMffcConeSupp( pNode, vInside, NULL );
// reference it back
Count2 = Abc_NodeRef_rec( pNode );
assert( Count1 == Count2 );
// remove the extra counters
Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
pObj->vFanouts.nSize--;
return Count1;
}
/**Function*************************************************************
Synopsis [Collects the internal nodes of the MFFC limited by cut.]
Description []
SideEffects [Increments the trav ID and marks visited nodes.]
SeeAlso []
***********************************************************************/
Vec_Ptr_t * Abc_NodeMffcInsideCollect( Abc_Obj_t * pNode )
{
Vec_Ptr_t * vInside;
int Count1, Count2;
// dereference the node
Count1 = Abc_NodeDeref_rec( pNode );
// collect the nodes inside the MFFC
vInside = Vec_PtrAlloc( 10 );
Abc_NodeMffcConeSupp( pNode, vInside, NULL );
// reference it back
Count2 = Abc_NodeRef_rec( pNode );
assert( Count1 == Count2 );
return vInside;
}
/**Function*************************************************************
Synopsis [Collects the internal and boundary nodes in the derefed MFFC.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_NodeMffcLabel_rec( Abc_Obj_t * pNode, int fTopmost )
{
Abc_Obj_t * pFanin;
int i;
// add to the new support nodes
if ( !fTopmost && (Abc_ObjIsCi(pNode) || pNode->vFanouts.nSize > 0) )
return;
// skip visited nodes
if ( Abc_NodeIsTravIdCurrent(pNode) )
return;
Abc_NodeSetTravIdCurrent(pNode);
// recur on the children
Abc_ObjForEachFanin( pNode, pFanin, i )
Abc_NodeMffcLabel_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 Abc_NodeMffcLabel( Abc_Obj_t * pNode )
{
int Count1, Count2;
// dereference the node
Count1 = Abc_NodeDeref_rec( pNode );
// collect the nodes inside the MFFC
Abc_NtkIncrementTravId( pNode->pNtk );
Abc_NodeMffcLabel_rec( pNode, 1 );
// reference it back
Count2 = Abc_NodeRef_rec( pNode );
assert( Count1 == Count2 );
return Count1;
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END