abc70930: src/base/abc/abcRefs.c Source File

00001 
00021 #include "abc.h"
00022 
00026 
00027 static int Abc_NodeRefDeref( Abc_Obj_t * pNode, bool fReference, bool fLabel );
00028 static int Abc_NodeRefDerefStop( Abc_Obj_t * pNode, bool fReference );
00029 
00033 
00045 int Abc_NodeMffcSize( Abc_Obj_t * pNode )
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 }
00059 
00071 int Abc_NodeMffcSizeStop( Abc_Obj_t * pNode )
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 }
00085 
00097 int Abc_NodeMffcLabelAig( Abc_Obj_t * pNode )
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 }
00111 
00123 int Abc_NodeRefDeref( Abc_Obj_t * pNode, bool fReference, bool fLabel )
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 }
00155 
00156 
00168 int Abc_NodeRefDerefStop( Abc_Obj_t * pNode, bool fReference )
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 }
00197 
00198 
00199 
00200 
00212 int Abc_NodeDeref_rec( Abc_Obj_t * pNode )
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 }
00226 
00238 int Abc_NodeRef_rec( Abc_Obj_t * pNode )
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 }
00251 
00263 void Abc_NodeMffsConeSupp_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vCone, Vec_Ptr_t * vSupp, int fTopmost )
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 }
00284 
00296 void Abc_NodeMffsConeSupp( Abc_Obj_t * pNode, Vec_Ptr_t * vCone, Vec_Ptr_t * vSupp )
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 }
00306 
00318 void Abc_NodeMffsConeSuppPrint( Abc_Obj_t * pNode )
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 }
00336 
00348 int Abc_NodeMffsInside( Abc_Obj_t * pNode, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vInside )
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 }
00367 
00379 Vec_Ptr_t * Abc_NodeMffsInsideCollect( Abc_Obj_t * pNode )
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 }
00393 
00405 void Abc_NodeMffcLabel_rec( Abc_Obj_t * pNode, int fTopmost )
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 }
00422 
00434 int Abc_NodeMffcLabel( Abc_Obj_t * pNode )
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 }
00447 
00451 
00452