src/aig/aig/aigMffc.c File Reference

#include "aig.h"
Include dependency graph for aigMffc.c:

Go to the source code of this file.

Functions

int Aig_NodeDeref_rec (Aig_Obj_t *pNode, unsigned LevelMin)
int Aig_NodeRef_rec (Aig_Obj_t *pNode, unsigned LevelMin)
int Aig_NodeRefLabel_rec (Aig_Man_t *p, Aig_Obj_t *pNode, unsigned LevelMin)
void Aig_NodeMffsSupp_rec (Aig_Man_t *p, Aig_Obj_t *pNode, unsigned LevelMin, Vec_Ptr_t *vSupp, int fTopmost, Aig_Obj_t *pObjSkip)
int Aig_NodeMffsSupp (Aig_Man_t *p, Aig_Obj_t *pNode, int LevelMin, Vec_Ptr_t *vSupp)
int Aig_NodeMffsLabel (Aig_Man_t *p, Aig_Obj_t *pNode)
int Aig_NodeMffsLabelCut (Aig_Man_t *p, Aig_Obj_t *pNode, Vec_Ptr_t *vLeaves)
int Aig_NodeMffsExtendCut (Aig_Man_t *p, Aig_Obj_t *pNode, Vec_Ptr_t *vLeaves, Vec_Ptr_t *vResult)

Function Documentation

int Aig_NodeDeref_rec ( Aig_Obj_t *  pNode,
unsigned  LevelMin 
)

CFile****************************************************************

FileName [aigMffc.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [AIG package.]

Synopsis [Computation of MFFCs.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - April 28, 2007.]

Revision [

Id
aigMffc.c,v 1.00 2007/04/28 00:00:00 alanmi Exp

] DECLARATIONS /// FUNCTION DEFINITIONS ///Function*************************************************************

Synopsis [Dereferences the node's MFFC.]

Description []

SideEffects []

SeeAlso []

Definition at line 42 of file aigMffc.c.

00043 {
00044     Aig_Obj_t * pFanin;
00045     int Counter = 0;
00046     if ( Aig_ObjIsPi(pNode) )
00047         return 0;
00048     // consider the first fanin
00049     pFanin = Aig_ObjFanin0(pNode);
00050     assert( pFanin->nRefs > 0 );
00051     if ( --pFanin->nRefs == 0 && (!LevelMin || pFanin->Level > LevelMin) )
00052         Counter += Aig_NodeDeref_rec( pFanin, LevelMin );
00053     // skip the buffer
00054     if ( Aig_ObjIsBuf(pNode) )
00055         return Counter;
00056     assert( Aig_ObjIsNode(pNode) );
00057     // consider the second fanin
00058     pFanin = Aig_ObjFanin1(pNode);
00059     assert( pFanin->nRefs > 0 );
00060     if ( --pFanin->nRefs == 0 && (!LevelMin || pFanin->Level > LevelMin) )
00061         Counter += Aig_NodeDeref_rec( pFanin, LevelMin );
00062     return Counter + 1;
00063 }

int Aig_NodeMffsExtendCut ( Aig_Man_t *  p,
Aig_Obj_t *  pNode,
Vec_Ptr_t *  vLeaves,
Vec_Ptr_t *  vResult 
)

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

Synopsis [Expands the cut by adding the most closely related node.]

Description [Returns 1 if the cut exists.]

SideEffects []

SeeAlso []

Definition at line 248 of file aigMffc.c.

00249 {
00250     Aig_Obj_t * pObj, * pLeafBest;
00251     int i, LevelMax, ConeSize1, ConeSize2, ConeCur1, ConeCur2, ConeBest;
00252     // dereference the current cut
00253     LevelMax = 0;
00254     Vec_PtrForEachEntry( vLeaves, pObj, i )
00255         LevelMax = AIG_MAX( LevelMax, (int)pObj->Level );
00256     if ( LevelMax == 0 )
00257         return 0;
00258     // dereference the cut
00259     ConeSize1 = Aig_NodeDeref_rec( pNode, 0 );
00260     // try expanding each node in the boundary
00261     ConeBest = AIG_INFINITY;
00262     pLeafBest = NULL;
00263     Vec_PtrForEachEntry( vLeaves, pObj, i )
00264     {
00265         if ( (int)pObj->Level != LevelMax )
00266             continue;
00267         ConeCur1 = Aig_NodeDeref_rec( pObj, 0 );
00268         if ( ConeBest > ConeCur1 )
00269         {
00270             ConeBest = ConeCur1;
00271             pLeafBest = pObj;
00272         }
00273         ConeCur2 = Aig_NodeRef_rec( pObj, 0 );
00274         assert( ConeCur1 == ConeCur2 );
00275     }
00276     assert( pLeafBest != NULL );
00277     assert( Aig_ObjIsNode(pLeafBest) );
00278     // deref the best leaf
00279     ConeCur1 = Aig_NodeDeref_rec( pLeafBest, 0 );
00280     // collect the cut nodes
00281     Vec_PtrClear( vResult );
00282     Aig_ManIncrementTravId( p );
00283     Aig_NodeMffsSupp_rec( p, pNode, 0, vResult, 1, pLeafBest );
00284     // ref the nodes
00285     ConeCur2 = Aig_NodeRef_rec( pLeafBest, 0 );
00286     assert( ConeCur1 == ConeCur2 );
00287     // ref the original node
00288     ConeSize2 = Aig_NodeRef_rec( pNode, 0 );
00289     assert( ConeSize1 == ConeSize2 );
00290     return 1;
00291 }

int Aig_NodeMffsLabel ( Aig_Man_t *  p,
Aig_Obj_t *  pNode 
)

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

Synopsis [Labels the nodes in the MFFC.]

Description [Returns the number of internal nodes in the MFFC.]

SideEffects []

SeeAlso []

Definition at line 195 of file aigMffc.c.

00196 {
00197     int ConeSize1, ConeSize2;
00198     assert( !Aig_IsComplement(pNode) );
00199     assert( Aig_ObjIsNode(pNode) );
00200     Aig_ManIncrementTravId( p );
00201     ConeSize1 = Aig_NodeDeref_rec( pNode, 0 );
00202     ConeSize2 = Aig_NodeRefLabel_rec( p, pNode, 0 );
00203     assert( ConeSize1 == ConeSize2 );
00204     assert( ConeSize1 > 0 );
00205     return ConeSize1;
00206 }

int Aig_NodeMffsLabelCut ( Aig_Man_t *  p,
Aig_Obj_t *  pNode,
Vec_Ptr_t *  vLeaves 
)

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

Synopsis [Labels the nodes in the MFFC.]

Description [Returns the number of internal nodes in the MFFC.]

SideEffects []

SeeAlso []

Definition at line 219 of file aigMffc.c.

00220 {
00221     Aig_Obj_t * pObj;
00222     int i, ConeSize1, ConeSize2;
00223     assert( !Aig_IsComplement(pNode) );
00224     assert( Aig_ObjIsNode(pNode) );
00225     Aig_ManIncrementTravId( p );
00226     Vec_PtrForEachEntry( vLeaves, pObj, i )
00227         pObj->nRefs++;
00228     ConeSize1 = Aig_NodeDeref_rec( pNode, 0 );
00229     ConeSize2 = Aig_NodeRefLabel_rec( p, pNode, 0 );
00230     Vec_PtrForEachEntry( vLeaves, pObj, i )
00231         pObj->nRefs--;
00232     assert( ConeSize1 == ConeSize2 );
00233     assert( ConeSize1 > 0 );
00234     return ConeSize1;
00235 }

int Aig_NodeMffsSupp ( Aig_Man_t *  p,
Aig_Obj_t *  pNode,
int  LevelMin,
Vec_Ptr_t *  vSupp 
)

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

Synopsis [Collects the support of depth-limited MFFC.]

Description [Returns the number of internal nodes in the MFFC.]

SideEffects []

SeeAlso []

Definition at line 169 of file aigMffc.c.

00170 {
00171     int ConeSize1, ConeSize2;
00172     assert( !Aig_IsComplement(pNode) );
00173     assert( Aig_ObjIsNode(pNode) );
00174     if ( vSupp ) Vec_PtrClear( vSupp );
00175     Aig_ManIncrementTravId( p );
00176     ConeSize1 = Aig_NodeDeref_rec( pNode, LevelMin );
00177     Aig_NodeMffsSupp_rec( p, pNode, LevelMin, vSupp, 1, NULL );
00178     ConeSize2 = Aig_NodeRef_rec( pNode, LevelMin );
00179     assert( ConeSize1 == ConeSize2 );
00180     assert( ConeSize1 > 0 );
00181     return ConeSize1;
00182 }

void Aig_NodeMffsSupp_rec ( Aig_Man_t *  p,
Aig_Obj_t *  pNode,
unsigned  LevelMin,
Vec_Ptr_t *  vSupp,
int  fTopmost,
Aig_Obj_t *  pObjSkip 
)

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 140 of file aigMffc.c.

00141 {
00142     // skip visited nodes
00143     if ( Aig_ObjIsTravIdCurrent(p, pNode) )
00144         return;
00145     Aig_ObjSetTravIdCurrent(p, pNode);
00146     // add to the new support nodes
00147     if ( !fTopmost && pNode != pObjSkip && (Aig_ObjIsPi(pNode) || pNode->nRefs > 0 || pNode->Level <= LevelMin) )
00148     {
00149         if ( vSupp ) Vec_PtrPush( vSupp, pNode );
00150         return;
00151     }
00152     assert( Aig_ObjIsNode(pNode) );
00153     // recur on the children
00154     Aig_NodeMffsSupp_rec( p, Aig_ObjFanin0(pNode), LevelMin, vSupp, 0, pObjSkip );
00155     Aig_NodeMffsSupp_rec( p, Aig_ObjFanin1(pNode), LevelMin, vSupp, 0, pObjSkip );
00156 }

int Aig_NodeRef_rec ( Aig_Obj_t *  pNode,
unsigned  LevelMin 
)

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

Synopsis [References the node's MFFC.]

Description []

SideEffects []

SeeAlso []

Definition at line 76 of file aigMffc.c.

00077 {
00078     Aig_Obj_t * pFanin;
00079     int Counter = 0;
00080     if ( Aig_ObjIsPi(pNode) )
00081         return 0;
00082     // consider the first fanin
00083     pFanin = Aig_ObjFanin0(pNode);
00084     if ( pFanin->nRefs++ == 0 && (!LevelMin || pFanin->Level > LevelMin) )
00085         Counter += Aig_NodeRef_rec( pFanin, LevelMin );
00086     // skip the buffer
00087     if ( Aig_ObjIsBuf(pNode) )
00088         return Counter;
00089     assert( Aig_ObjIsNode(pNode) );
00090     // consider the second fanin
00091     pFanin = Aig_ObjFanin1(pNode);
00092     if ( pFanin->nRefs++ == 0 && (!LevelMin || pFanin->Level > LevelMin) )
00093         Counter += Aig_NodeRef_rec( pFanin, LevelMin );
00094     return Counter + 1;
00095 }

int Aig_NodeRefLabel_rec ( Aig_Man_t *  p,
Aig_Obj_t *  pNode,
unsigned  LevelMin 
)

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

Synopsis [References the node's MFFC.]

Description []

SideEffects []

SeeAlso []

Definition at line 108 of file aigMffc.c.

00109 {
00110     Aig_Obj_t * pFanin;
00111     int Counter = 0;
00112     if ( Aig_ObjIsPi(pNode) )
00113         return 0;
00114     Aig_ObjSetTravIdCurrent( p, pNode );
00115     // consider the first fanin
00116     pFanin = Aig_ObjFanin0(pNode);
00117     if ( pFanin->nRefs++ == 0 && (!LevelMin || pFanin->Level > LevelMin) )
00118         Counter += Aig_NodeRefLabel_rec( p, pFanin, LevelMin );
00119     if ( Aig_ObjIsBuf(pNode) )
00120         return Counter;
00121     assert( Aig_ObjIsNode(pNode) );
00122     // consider the second fanin
00123     pFanin = Aig_ObjFanin1(pNode);
00124     if ( pFanin->nRefs++ == 0 && (!LevelMin || pFanin->Level > LevelMin) )
00125         Counter += Aig_NodeRefLabel_rec( p, pFanin, LevelMin );
00126     return Counter + 1;
00127 }

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