src/base/abc/abcRefs.c File Reference

#include "abc.h"
Include dependency graph for abcRefs.c:

Go to the source code of this file.

Functions

static int Abc_NodeRefDeref (Abc_Obj_t *pNode, bool fReference, bool fLabel)
static int Abc_NodeRefDerefStop (Abc_Obj_t *pNode, bool fReference)
int Abc_NodeMffcSize (Abc_Obj_t *pNode)
int Abc_NodeMffcSizeStop (Abc_Obj_t *pNode)
int Abc_NodeMffcLabelAig (Abc_Obj_t *pNode)
int Abc_NodeDeref_rec (Abc_Obj_t *pNode)
int Abc_NodeRef_rec (Abc_Obj_t *pNode)
void Abc_NodeMffsConeSupp_rec (Abc_Obj_t *pNode, Vec_Ptr_t *vCone, Vec_Ptr_t *vSupp, int fTopmost)
void Abc_NodeMffsConeSupp (Abc_Obj_t *pNode, Vec_Ptr_t *vCone, Vec_Ptr_t *vSupp)
void Abc_NodeMffsConeSuppPrint (Abc_Obj_t *pNode)
int Abc_NodeMffsInside (Abc_Obj_t *pNode, Vec_Ptr_t *vLeaves, Vec_Ptr_t *vInside)
Vec_Ptr_t * Abc_NodeMffsInsideCollect (Abc_Obj_t *pNode)
void Abc_NodeMffcLabel_rec (Abc_Obj_t *pNode, int fTopmost)
int Abc_NodeMffcLabel (Abc_Obj_t *pNode)

Function Documentation

int Abc_NodeDeref_rec ( Abc_Obj_t *  pNode  ) 

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

Synopsis [Dereferences the node's MFFC.]

Description []

SideEffects []

SeeAlso []

Definition at line 212 of file abcRefs.c.

00213 {
00214     Abc_Obj_t * pFanin;
00215     int i, Counter = 1;
00216     if ( Abc_ObjIsCi(pNode) )
00217         return 0;
00218     Abc_ObjForEachFanin( pNode, pFanin, i )
00219     {
00220         assert( pFanin->vFanouts.nSize > 0 );
00221         if ( --pFanin->vFanouts.nSize == 0 )
00222             Counter += Abc_NodeDeref_rec( pFanin );
00223     }
00224     return Counter;
00225 }

int Abc_NodeMffcLabel ( Abc_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 434 of file abcRefs.c.

00435 {
00436     int Count1, Count2;
00437     // dereference the node
00438     Count1 = Abc_NodeDeref_rec( pNode );
00439     // collect the nodes inside the MFFC
00440     Abc_NtkIncrementTravId( pNode->pNtk );
00441     Abc_NodeMffcLabel_rec( pNode, 1 );
00442     // reference it back
00443     Count2 = Abc_NodeRef_rec( pNode );
00444     assert( Count1 == Count2 );
00445     return Count1;
00446 }

void Abc_NodeMffcLabel_rec ( Abc_Obj_t *  pNode,
int  fTopmost 
)

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 405 of file abcRefs.c.

00406 {
00407     Abc_Obj_t * pFanin;
00408     int i;
00409     // add to the new support nodes
00410     if ( !fTopmost && (Abc_ObjIsCi(pNode) || pNode->vFanouts.nSize > 0) )
00411         return;
00412     // skip visited nodes
00413     if ( Abc_NodeIsTravIdCurrent(pNode) )
00414         return;
00415     Abc_NodeSetTravIdCurrent(pNode);
00416     // recur on the children
00417     Abc_ObjForEachFanin( pNode, pFanin, i )
00418         Abc_NodeMffcLabel_rec( pFanin, 0 );
00419     // collect the internal node
00420 //    printf( "%d ", pNode->Id );
00421 }

int Abc_NodeMffcLabelAig ( Abc_Obj_t *  pNode  ) 

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

Synopsis [Labels MFFC with the current traversal ID.]

Description []

SideEffects []

SeeAlso []

Definition at line 97 of file abcRefs.c.

00098 {
00099     int nConeSize1, nConeSize2;
00100     assert( Abc_NtkIsStrash(pNode->pNtk) );
00101     assert( !Abc_ObjIsComplement( pNode ) );
00102     assert( Abc_ObjIsNode( pNode ) );
00103     if ( Abc_ObjFaninNum(pNode) == 0 )
00104         return 0;
00105     nConeSize1 = Abc_NodeRefDeref( pNode, 0, 1 ); // dereference
00106     nConeSize2 = Abc_NodeRefDeref( pNode, 1, 0 ); // reference
00107     assert( nConeSize1 == nConeSize2 );
00108     assert( nConeSize1 > 0 );
00109     return nConeSize1;
00110 }

int Abc_NodeMffcSize ( Abc_Obj_t *  pNode  ) 

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

Synopsis [Returns the MFFC size.]

Description []

SideEffects []

SeeAlso []

Definition at line 45 of file abcRefs.c.

00046 {
00047     int nConeSize1, nConeSize2;
00048 //    assert( Abc_NtkIsStrash(pNode->pNtk) );
00049 //    assert( !Abc_ObjIsComplement( pNode ) );
00050     assert( Abc_ObjIsNode( pNode ) );
00051     if ( Abc_ObjFaninNum(pNode) == 0 )
00052         return 0;
00053     nConeSize1 = Abc_NodeRefDeref( pNode, 0, 0 ); // dereference
00054     nConeSize2 = Abc_NodeRefDeref( pNode, 1, 0 ); // reference
00055     assert( nConeSize1 == nConeSize2 );
00056     assert( nConeSize1 > 0 );
00057     return nConeSize1;
00058 }

int Abc_NodeMffcSizeStop ( Abc_Obj_t *  pNode  ) 

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

Synopsis [Returns the MFFC size while stopping at the complemented edges.]

Description []

SideEffects []

SeeAlso []

Definition at line 71 of file abcRefs.c.

00072 {
00073     int nConeSize1, nConeSize2;
00074     assert( Abc_NtkIsStrash(pNode->pNtk) );
00075     assert( !Abc_ObjIsComplement( pNode ) );
00076     assert( Abc_ObjIsNode( pNode ) );
00077     if ( Abc_ObjFaninNum(pNode) == 0 )
00078         return 0;
00079     nConeSize1 = Abc_NodeRefDerefStop( pNode, 0 ); // dereference
00080     nConeSize2 = Abc_NodeRefDerefStop( pNode, 1 ); // reference
00081     assert( nConeSize1 == nConeSize2 );
00082     assert( nConeSize1 > 0 );
00083     return nConeSize1;
00084 }

void Abc_NodeMffsConeSupp ( Abc_Obj_t *  pNode,
Vec_Ptr_t *  vCone,
Vec_Ptr_t *  vSupp 
)

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

Synopsis [Collects the support of the derefed MFFC.]

Description []

SideEffects []

SeeAlso []

Definition at line 296 of file abcRefs.c.

00297 {
00298     assert( Abc_ObjIsNode(pNode) );
00299     assert( !Abc_ObjIsComplement(pNode) );
00300     if ( vCone ) Vec_PtrClear( vCone );
00301     if ( vSupp ) Vec_PtrClear( vSupp );
00302     Abc_NtkIncrementTravId( pNode->pNtk );
00303     Abc_NodeMffsConeSupp_rec( pNode, vCone, vSupp, 1 );
00304 //    printf( "\n" );
00305 }

void Abc_NodeMffsConeSupp_rec ( Abc_Obj_t *  pNode,
Vec_Ptr_t *  vCone,
Vec_Ptr_t *  vSupp,
int  fTopmost 
)

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 263 of file abcRefs.c.

00264 {
00265     Abc_Obj_t * pFanin;
00266     int i;
00267     // skip visited nodes
00268     if ( Abc_NodeIsTravIdCurrent(pNode) )
00269         return;
00270     Abc_NodeSetTravIdCurrent(pNode);
00271     // add to the new support nodes
00272     if ( !fTopmost && (Abc_ObjIsCi(pNode) || pNode->vFanouts.nSize > 0) )
00273     {
00274         if ( vSupp ) Vec_PtrPush( vSupp, pNode );
00275         return;
00276     }
00277     // recur on the children
00278     Abc_ObjForEachFanin( pNode, pFanin, i )
00279         Abc_NodeMffsConeSupp_rec( pFanin, vCone, vSupp, 0 );
00280     // collect the internal node
00281     if ( vCone ) Vec_PtrPush( vCone, pNode );
00282 //    printf( "%d ", pNode->Id );
00283 }

void Abc_NodeMffsConeSuppPrint ( Abc_Obj_t *  pNode  ) 

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

Synopsis [Collects the support of the derefed MFFC.]

Description []

SideEffects []

SeeAlso []

Definition at line 318 of file abcRefs.c.

00319 {
00320     Vec_Ptr_t * vCone, * vSupp;
00321     Abc_Obj_t * pObj;
00322     int i;
00323     vCone = Vec_PtrAlloc( 100 );
00324     vSupp = Vec_PtrAlloc( 100 );
00325     Abc_NodeDeref_rec( pNode );
00326     Abc_NodeMffsConeSupp( pNode, vCone, vSupp );
00327     Abc_NodeRef_rec( pNode );
00328     printf( "Node = %6s : Supp = %3d  Cone = %3d  (", 
00329         Abc_ObjName(pNode), Vec_PtrSize(vSupp), Vec_PtrSize(vCone) );
00330     Vec_PtrForEachEntry( vCone, pObj, i )
00331         printf( " %s", Abc_ObjName(pObj) );
00332     printf( " )\n" );
00333     Vec_PtrFree( vCone );
00334     Vec_PtrFree( vSupp );
00335 }

int Abc_NodeMffsInside ( Abc_Obj_t *  pNode,
Vec_Ptr_t *  vLeaves,
Vec_Ptr_t *  vInside 
)

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 348 of file abcRefs.c.

00349 {
00350     Abc_Obj_t * pObj;
00351     int i, Count1, Count2;
00352     // increment the fanout counters for the leaves
00353     Vec_PtrForEachEntry( vLeaves, pObj, i )
00354         pObj->vFanouts.nSize++;
00355     // dereference the node
00356     Count1 = Abc_NodeDeref_rec( pNode );
00357     // collect the nodes inside the MFFC
00358     Abc_NodeMffsConeSupp( pNode, vInside, NULL );
00359     // reference it back
00360     Count2 = Abc_NodeRef_rec( pNode );
00361     assert( Count1 == Count2 );
00362     // remove the extra counters
00363     Vec_PtrForEachEntry( vLeaves, pObj, i )
00364         pObj->vFanouts.nSize--;
00365     return Count1;
00366 }

Vec_Ptr_t* Abc_NodeMffsInsideCollect ( Abc_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 379 of file abcRefs.c.

00380 {
00381     Vec_Ptr_t * vInside;
00382     int Count1, Count2;
00383     // dereference the node
00384     Count1 = Abc_NodeDeref_rec( pNode );
00385     // collect the nodes inside the MFFC
00386     vInside = Vec_PtrAlloc( 10 );
00387     Abc_NodeMffsConeSupp( pNode, vInside, NULL );
00388     // reference it back
00389     Count2 = Abc_NodeRef_rec( pNode );
00390     assert( Count1 == Count2 );
00391     return vInside;
00392 }

int Abc_NodeRef_rec ( Abc_Obj_t *  pNode  ) 

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

Synopsis [References the node's MFFC.]

Description []

SideEffects []

SeeAlso []

Definition at line 238 of file abcRefs.c.

00239 {
00240     Abc_Obj_t * pFanin;
00241     int i, Counter = 1;
00242     if ( Abc_ObjIsCi(pNode) )
00243         return 0;
00244     Abc_ObjForEachFanin( pNode, pFanin, i )
00245     {
00246         if ( pFanin->vFanouts.nSize++ == 0 )
00247             Counter += Abc_NodeRef_rec( pFanin );
00248     }
00249     return Counter;
00250 }

int Abc_NodeRefDeref ( Abc_Obj_t *  pNode,
bool  fReference,
bool  fLabel 
) [static]

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

] DECLARATIONS ///

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

Synopsis [References/references the node and returns MFFC size.]

Description []

SideEffects []

SeeAlso []

Definition at line 123 of file abcRefs.c.

00124 {
00125     Abc_Obj_t * pNode0, * pNode1;
00126     int Counter;
00127     // label visited nodes
00128     if ( fLabel )
00129         Abc_NodeSetTravIdCurrent( pNode );
00130     // skip the CI
00131     if ( Abc_ObjIsCi(pNode) )
00132         return 0;
00133     // process the internal node
00134     pNode0 = Abc_ObjFanin0(pNode);
00135     pNode1 = Abc_ObjFanin1(pNode);
00136     Counter = 1;
00137     if ( fReference )
00138     {
00139         if ( pNode0->vFanouts.nSize++ == 0 )
00140             Counter += Abc_NodeRefDeref( pNode0, fReference, fLabel );
00141         if ( pNode1->vFanouts.nSize++ == 0 )
00142             Counter += Abc_NodeRefDeref( pNode1, fReference, fLabel );
00143     }
00144     else
00145     {
00146         assert( pNode0->vFanouts.nSize > 0 );
00147         assert( pNode1->vFanouts.nSize > 0 );
00148         if ( --pNode0->vFanouts.nSize == 0 )
00149             Counter += Abc_NodeRefDeref( pNode0, fReference, fLabel );
00150         if ( --pNode1->vFanouts.nSize == 0 )
00151             Counter += Abc_NodeRefDeref( pNode1, fReference, fLabel );
00152     }
00153     return Counter;
00154 }

int Abc_NodeRefDerefStop ( Abc_Obj_t *  pNode,
bool  fReference 
) [static]

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

Synopsis [References/references the node and returns MFFC size.]

Description [Stops at the complemented edges.]

SideEffects []

SeeAlso []

Definition at line 168 of file abcRefs.c.

00169 {
00170     Abc_Obj_t * pNode0, * pNode1;
00171     int Counter;
00172     // skip the CI
00173     if ( Abc_ObjIsCi(pNode) )
00174         return 0;
00175     // process the internal node
00176     pNode0 = Abc_ObjFanin0(pNode);
00177     pNode1 = Abc_ObjFanin1(pNode);
00178     Counter = 1;
00179     if ( fReference )
00180     {
00181         if ( pNode0->vFanouts.nSize++ == 0 && !Abc_ObjFaninC0(pNode) )
00182             Counter += Abc_NodeRefDerefStop( pNode0, fReference );
00183         if ( pNode1->vFanouts.nSize++ == 0 && !Abc_ObjFaninC1(pNode) )
00184             Counter += Abc_NodeRefDerefStop( pNode1, fReference );
00185     }
00186     else
00187     {
00188         assert( pNode0->vFanouts.nSize > 0 );
00189         assert( pNode1->vFanouts.nSize > 0 );
00190         if ( --pNode0->vFanouts.nSize == 0 && !Abc_ObjFaninC0(pNode) )
00191             Counter += Abc_NodeRefDerefStop( pNode0, fReference );
00192         if ( --pNode1->vFanouts.nSize == 0 && !Abc_ObjFaninC1(pNode) )
00193             Counter += Abc_NodeRefDerefStop( pNode1, fReference );
00194     }
00195     return Counter;
00196 }

Generated on Tue Jan 5 12:18:32 2010 for abc70930 by  doxygen 1.6.1