abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
abcRefs.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [abcRefs.c]
4 
5  SystemName [ABC: Logic synthesis and verification system.]
6 
7  PackageName [Network and node package.]
8 
9  Synopsis [Procedures using reference counting of the AIG nodes.]
10 
11  Author [Alan Mishchenko]
12 
13  Affiliation [UC Berkeley]
14 
15  Date [Ver. 1.0. Started - June 20, 2005.]
16 
17  Revision [$Id: abcRefs.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include "abc.h"
22 
23 ABC_NAMESPACE_IMPL_START
24 
25 
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29 
30 static int Abc_NodeRefDeref( Abc_Obj_t * pNode, int fReference, int fLabel );
31 static int Abc_NodeRefDerefStop( Abc_Obj_t * pNode, int fReference );
32 
33 ////////////////////////////////////////////////////////////////////////
34 /// FUNCTION DEFINITIONS ///
35 ////////////////////////////////////////////////////////////////////////
36 
37 /**Function*************************************************************
38 
39  Synopsis [Returns the MFFC size.]
40 
41  Description []
42 
43  SideEffects []
44 
45  SeeAlso []
46 
47 ***********************************************************************/
48 int Abc_NodeMffcSize( Abc_Obj_t * pNode )
49 {
50  int nConeSize1, nConeSize2;
51 // assert( Abc_NtkIsStrash(pNode->pNtk) );
52 // assert( !Abc_ObjIsComplement( pNode ) );
53  assert( Abc_ObjIsNode( pNode ) );
54  if ( Abc_ObjFaninNum(pNode) == 0 )
55  return 0;
56  nConeSize1 = Abc_NodeRefDeref( pNode, 0, 0 ); // dereference
57  nConeSize2 = Abc_NodeRefDeref( pNode, 1, 0 ); // reference
58  assert( nConeSize1 == nConeSize2 );
59  assert( nConeSize1 > 0 );
60  return nConeSize1;
61 }
62 
63 /**Function*************************************************************
64 
65  Synopsis [Returns the MFFC size while stopping at the complemented edges.]
66 
67  Description []
68 
69  SideEffects []
70 
71  SeeAlso []
72 
73 ***********************************************************************/
74 int Abc_NodeMffcSizeStop( Abc_Obj_t * pNode )
75 {
76  int nConeSize1, nConeSize2;
77  assert( Abc_NtkIsStrash(pNode->pNtk) );
78  assert( !Abc_ObjIsComplement( pNode ) );
79  assert( Abc_ObjIsNode( pNode ) );
80  if ( Abc_ObjFaninNum(pNode) == 0 )
81  return 0;
82  nConeSize1 = Abc_NodeRefDerefStop( pNode, 0 ); // dereference
83  nConeSize2 = Abc_NodeRefDerefStop( pNode, 1 ); // reference
84  assert( nConeSize1 == nConeSize2 );
85  assert( nConeSize1 > 0 );
86  return nConeSize1;
87 }
88 
89 /**Function*************************************************************
90 
91  Synopsis [Labels MFFC with the current traversal ID.]
92 
93  Description []
94 
95  SideEffects []
96 
97  SeeAlso []
98 
99 ***********************************************************************/
100 int Abc_NodeMffcLabelAig( Abc_Obj_t * pNode )
101 {
102  int nConeSize1, nConeSize2;
103  assert( Abc_NtkIsStrash(pNode->pNtk) );
104  assert( !Abc_ObjIsComplement( pNode ) );
105  assert( Abc_ObjIsNode( pNode ) );
106  if ( Abc_ObjFaninNum(pNode) == 0 )
107  return 0;
108  nConeSize1 = Abc_NodeRefDeref( pNode, 0, 1 ); // dereference
109  nConeSize2 = Abc_NodeRefDeref( pNode, 1, 0 ); // reference
110  assert( nConeSize1 == nConeSize2 );
111  assert( nConeSize1 > 0 );
112  return nConeSize1;
113 }
114 
115 /**Function*************************************************************
116 
117  Synopsis [References/references the node and returns MFFC size.]
118 
119  Description []
120 
121  SideEffects []
122 
123  SeeAlso []
124 
125 ***********************************************************************/
126 int Abc_NodeRefDeref( Abc_Obj_t * pNode, int fReference, int fLabel )
127 {
128  Abc_Obj_t * pNode0, * pNode1;
129  int Counter;
130  // label visited nodes
131  if ( fLabel )
132  Abc_NodeSetTravIdCurrent( pNode );
133  // skip the CI
134  if ( Abc_ObjIsCi(pNode) )
135  return 0;
136  // process the internal node
137  pNode0 = Abc_ObjFanin0(pNode);
138  pNode1 = Abc_ObjFanin1(pNode);
139  Counter = 1;
140  if ( fReference )
141  {
142  if ( pNode0->vFanouts.nSize++ == 0 )
143  Counter += Abc_NodeRefDeref( pNode0, fReference, fLabel );
144  if ( pNode1->vFanouts.nSize++ == 0 )
145  Counter += Abc_NodeRefDeref( pNode1, fReference, fLabel );
146  }
147  else
148  {
149  assert( pNode0->vFanouts.nSize > 0 );
150  assert( pNode1->vFanouts.nSize > 0 );
151  if ( --pNode0->vFanouts.nSize == 0 )
152  Counter += Abc_NodeRefDeref( pNode0, fReference, fLabel );
153  if ( --pNode1->vFanouts.nSize == 0 )
154  Counter += Abc_NodeRefDeref( pNode1, fReference, fLabel );
155  }
156  return Counter;
157 }
158 
159 
160 /**Function*************************************************************
161 
162  Synopsis [References/references the node and returns MFFC size.]
163 
164  Description [Stops at the complemented edges.]
165 
166  SideEffects []
167 
168  SeeAlso []
169 
170 ***********************************************************************/
171 int Abc_NodeRefDerefStop( Abc_Obj_t * pNode, int fReference )
172 {
173  Abc_Obj_t * pNode0, * pNode1;
174  int Counter;
175  // skip the CI
176  if ( Abc_ObjIsCi(pNode) )
177  return 0;
178  // process the internal node
179  pNode0 = Abc_ObjFanin0(pNode);
180  pNode1 = Abc_ObjFanin1(pNode);
181  Counter = 1;
182  if ( fReference )
183  {
184  if ( !Abc_ObjFaninC0(pNode) && pNode0->vFanouts.nSize++ == 0 )
185  Counter += Abc_NodeRefDerefStop( pNode0, fReference );
186  if ( !Abc_ObjFaninC1(pNode) && pNode1->vFanouts.nSize++ == 0 )
187  Counter += Abc_NodeRefDerefStop( pNode1, fReference );
188  }
189  else
190  {
191  assert( pNode0->vFanouts.nSize > 0 );
192  assert( pNode1->vFanouts.nSize > 0 );
193  if ( !Abc_ObjFaninC0(pNode) && --pNode0->vFanouts.nSize == 0 )
194  Counter += Abc_NodeRefDerefStop( pNode0, fReference );
195  if ( !Abc_ObjFaninC1(pNode) && --pNode1->vFanouts.nSize == 0 )
196  Counter += Abc_NodeRefDerefStop( pNode1, fReference );
197  }
198  return Counter;
199 }
200 
201 
202 
203 
204 /**Function*************************************************************
205 
206  Synopsis [Dereferences the node's MFFC.]
207 
208  Description []
209 
210  SideEffects []
211 
212  SeeAlso []
213 
214 ***********************************************************************/
215 int Abc_NodeDeref_rec( Abc_Obj_t * pNode )
216 {
217  Abc_Obj_t * pFanin;
218  int i, Counter = 1;
219  if ( Abc_ObjIsCi(pNode) )
220  return 0;
221  Abc_ObjForEachFanin( pNode, pFanin, i )
222  {
223  assert( pFanin->vFanouts.nSize > 0 );
224  if ( --pFanin->vFanouts.nSize == 0 )
225  Counter += Abc_NodeDeref_rec( pFanin );
226  }
227  return Counter;
228 }
229 
230 /**Function*************************************************************
231 
232  Synopsis [References the node's MFFC.]
233 
234  Description []
235 
236  SideEffects []
237 
238  SeeAlso []
239 
240 ***********************************************************************/
241 int Abc_NodeRef_rec( Abc_Obj_t * pNode )
242 {
243  Abc_Obj_t * pFanin;
244  int i, Counter = 1;
245  if ( Abc_ObjIsCi(pNode) )
246  return 0;
247  Abc_ObjForEachFanin( pNode, pFanin, i )
248  {
249  if ( pFanin->vFanouts.nSize++ == 0 )
250  Counter += Abc_NodeRef_rec( pFanin );
251  }
252  return Counter;
253 }
254 
255 /**Function*************************************************************
256 
257  Synopsis [Collects the internal and boundary nodes in the derefed MFFC.]
258 
259  Description []
260 
261  SideEffects []
262 
263  SeeAlso []
264 
265 ***********************************************************************/
266 void Abc_NodeMffcConeSupp_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vCone, Vec_Ptr_t * vSupp, int fTopmost )
267 {
268  Abc_Obj_t * pFanin;
269  int i;
270  // skip visited nodes
271  if ( Abc_NodeIsTravIdCurrent(pNode) )
272  return;
273  Abc_NodeSetTravIdCurrent(pNode);
274  // add to the new support nodes
275  if ( !fTopmost && (Abc_ObjIsCi(pNode) || pNode->vFanouts.nSize > 0) )
276  {
277  if ( vSupp ) Vec_PtrPush( vSupp, pNode );
278  return;
279  }
280  // recur on the children
281  Abc_ObjForEachFanin( pNode, pFanin, i )
282  Abc_NodeMffcConeSupp_rec( pFanin, vCone, vSupp, 0 );
283  // collect the internal node
284  if ( vCone ) Vec_PtrPush( vCone, pNode );
285 // printf( "%d ", pNode->Id );
286 }
287 
288 /**Function*************************************************************
289 
290  Synopsis [Collects the support of the derefed MFFC.]
291 
292  Description []
293 
294  SideEffects []
295 
296  SeeAlso []
297 
298 ***********************************************************************/
299 void Abc_NodeMffcConeSupp( Abc_Obj_t * pNode, Vec_Ptr_t * vCone, Vec_Ptr_t * vSupp )
300 {
301  assert( Abc_ObjIsNode(pNode) );
302  assert( !Abc_ObjIsComplement(pNode) );
303  if ( vCone ) Vec_PtrClear( vCone );
304  if ( vSupp ) Vec_PtrClear( vSupp );
305  Abc_NtkIncrementTravId( pNode->pNtk );
306  Abc_NodeMffcConeSupp_rec( pNode, vCone, vSupp, 1 );
307 // printf( "\n" );
308 }
309 
310 /**Function*************************************************************
311 
312  Synopsis [Collects the support of the derefed MFFC.]
313 
314  Description []
315 
316  SideEffects []
317 
318  SeeAlso []
319 
320 ***********************************************************************/
321 void Abc_NodeMffcConeSuppPrint( Abc_Obj_t * pNode )
322 {
323  Vec_Ptr_t * vCone, * vSupp;
324  Abc_Obj_t * pObj;
325  int i;
326  vCone = Vec_PtrAlloc( 100 );
327  vSupp = Vec_PtrAlloc( 100 );
328  Abc_NodeDeref_rec( pNode );
329  Abc_NodeMffcConeSupp( pNode, vCone, vSupp );
330  Abc_NodeRef_rec( pNode );
331  printf( "Node = %6s : Supp = %3d Cone = %3d (",
332  Abc_ObjName(pNode), Vec_PtrSize(vSupp), Vec_PtrSize(vCone) );
333  Vec_PtrForEachEntry( Abc_Obj_t *, vCone, pObj, i )
334  printf( " %s", Abc_ObjName(pObj) );
335  printf( " )\n" );
336  Vec_PtrFree( vCone );
337  Vec_PtrFree( vSupp );
338 }
339 
340 /**Function*************************************************************
341 
342  Synopsis [Collects the internal nodes of the MFFC limited by cut.]
343 
344  Description []
345 
346  SideEffects [Increments the trav ID and marks visited nodes.]
347 
348  SeeAlso []
349 
350 ***********************************************************************/
351 int Abc_NodeMffcInside( Abc_Obj_t * pNode, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vInside )
352 {
353  Abc_Obj_t * pObj;
354  int i, Count1, Count2;
355  // increment the fanout counters for the leaves
356  Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
357  pObj->vFanouts.nSize++;
358  // dereference the node
359  Count1 = Abc_NodeDeref_rec( pNode );
360  // collect the nodes inside the MFFC
361  Abc_NodeMffcConeSupp( pNode, vInside, NULL );
362  // reference it back
363  Count2 = Abc_NodeRef_rec( pNode );
364  assert( Count1 == Count2 );
365  // remove the extra counters
366  Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
367  pObj->vFanouts.nSize--;
368  return Count1;
369 }
370 
371 /**Function*************************************************************
372 
373  Synopsis [Collects the internal nodes of the MFFC limited by cut.]
374 
375  Description []
376 
377  SideEffects [Increments the trav ID and marks visited nodes.]
378 
379  SeeAlso []
380 
381 ***********************************************************************/
382 Vec_Ptr_t * Abc_NodeMffcInsideCollect( Abc_Obj_t * pNode )
383 {
384  Vec_Ptr_t * vInside;
385  int Count1, Count2;
386  // dereference the node
387  Count1 = Abc_NodeDeref_rec( pNode );
388  // collect the nodes inside the MFFC
389  vInside = Vec_PtrAlloc( 10 );
390  Abc_NodeMffcConeSupp( pNode, vInside, NULL );
391  // reference it back
392  Count2 = Abc_NodeRef_rec( pNode );
393  assert( Count1 == Count2 );
394  return vInside;
395 }
396 
397 /**Function*************************************************************
398 
399  Synopsis [Collects the internal and boundary nodes in the derefed MFFC.]
400 
401  Description []
402 
403  SideEffects []
404 
405  SeeAlso []
406 
407 ***********************************************************************/
408 void Abc_NodeMffcLabel_rec( Abc_Obj_t * pNode, int fTopmost )
409 {
410  Abc_Obj_t * pFanin;
411  int i;
412  // add to the new support nodes
413  if ( !fTopmost && (Abc_ObjIsCi(pNode) || pNode->vFanouts.nSize > 0) )
414  return;
415  // skip visited nodes
416  if ( Abc_NodeIsTravIdCurrent(pNode) )
417  return;
418  Abc_NodeSetTravIdCurrent(pNode);
419  // recur on the children
420  Abc_ObjForEachFanin( pNode, pFanin, i )
421  Abc_NodeMffcLabel_rec( pFanin, 0 );
422  // collect the internal node
423 // printf( "%d ", pNode->Id );
424 }
425 
426 /**Function*************************************************************
427 
428  Synopsis [Collects the internal nodes of the MFFC limited by cut.]
429 
430  Description []
431 
432  SideEffects [Increments the trav ID and marks visited nodes.]
433 
434  SeeAlso []
435 
436 ***********************************************************************/
437 int Abc_NodeMffcLabel( Abc_Obj_t * pNode )
438 {
439  int Count1, Count2;
440  // dereference the node
441  Count1 = Abc_NodeDeref_rec( pNode );
442  // collect the nodes inside the MFFC
443  Abc_NtkIncrementTravId( pNode->pNtk );
444  Abc_NodeMffcLabel_rec( pNode, 1 );
445  // reference it back
446  Count2 = Abc_NodeRef_rec( pNode );
447  assert( Count1 == Count2 );
448  return Count1;
449 }
450 
451 ////////////////////////////////////////////////////////////////////////
452 /// END OF FILE ///
453 ////////////////////////////////////////////////////////////////////////
454 
455 
456 ABC_NAMESPACE_IMPL_END
457 
Abc_NtkIsStrash
static int Abc_NtkIsStrash(Abc_Ntk_t *pNtk)
Definition: abc.h:251
Vec_Ptr_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
Abc_ObjFanin1
static Abc_Obj_t * Abc_ObjFanin1(Abc_Obj_t *pObj)
Definition: abc.h:374
Abc_ObjIsCi
static int Abc_ObjIsCi(Abc_Obj_t *pObj)
Definition: abc.h:351
Abc_NodeMffcInside
int Abc_NodeMffcInside(Abc_Obj_t *pNode, Vec_Ptr_t *vLeaves, Vec_Ptr_t *vInside)
Definition: abcRefs.c:351
Abc_ObjFaninC1
static int Abc_ObjFaninC1(Abc_Obj_t *pObj)
Definition: abc.h:378
Abc_NodeDeref_rec
int Abc_NodeDeref_rec(Abc_Obj_t *pNode)
Definition: abcRefs.c:215
Abc_NodeMffcLabelAig
int Abc_NodeMffcLabelAig(Abc_Obj_t *pNode)
Definition: abcRefs.c:100
Abc_ObjFaninNum
static int Abc_ObjFaninNum(Abc_Obj_t *pObj)
Definition: abc.h:364
Abc_NodeMffcConeSuppPrint
void Abc_NodeMffcConeSuppPrint(Abc_Obj_t *pNode)
Definition: abcRefs.c:321
Abc_ObjFaninC0
static int Abc_ObjFaninC0(Abc_Obj_t *pObj)
Definition: abc.h:377
Vec_PtrPush
static void Vec_PtrPush(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:606
Abc_NodeMffcLabel
int Abc_NodeMffcLabel(Abc_Obj_t *pNode)
Definition: abcRefs.c:437
Abc_NodeRefDerefStop
static int Abc_NodeRefDerefStop(Abc_Obj_t *pNode, int fReference)
Definition: abcRefs.c:171
Vec_PtrSize
static int Vec_PtrSize(Vec_Ptr_t *p)
Definition: vecPtr.h:295
Abc_ObjFanin0
static Abc_Obj_t * Abc_ObjFanin0(Abc_Obj_t *pObj)
Definition: abc.h:373
Abc_NodeMffcSizeStop
int Abc_NodeMffcSizeStop(Abc_Obj_t *pNode)
Definition: abcRefs.c:74
Abc_Obj_t_
Definition: abc.h:128
Abc_ObjIsNode
static int Abc_ObjIsNode(Abc_Obj_t *pObj)
Definition: abc.h:355
Abc_NodeRef_rec
int Abc_NodeRef_rec(Abc_Obj_t *pNode)
Definition: abcRefs.c:241
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
Abc_NodeMffcLabel_rec
void Abc_NodeMffcLabel_rec(Abc_Obj_t *pNode, int fTopmost)
Definition: abcRefs.c:408
Counter
static int Counter
Definition: extraBddMisc.c:1877
Abc_NodeRefDeref
static ABC_NAMESPACE_IMPL_START int Abc_NodeRefDeref(Abc_Obj_t *pNode, int fReference, int fLabel)
DECLARATIONS ///.
Definition: abcRefs.c:126
ABC_NAMESPACE_IMPL_START
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
Abc_Obj_t_::vFanouts
Vec_Int_t vFanouts
Definition: abc.h:144
Abc_NodeIsTravIdCurrent
static int Abc_NodeIsTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:411
Abc_Obj_t_::pNtk
Abc_Ntk_t * pNtk
Definition: abc.h:130
Vec_PtrAlloc
static Vec_Ptr_t * Vec_PtrAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecPtr.h:83
Abc_NodeMffcInsideCollect
Vec_Ptr_t * Abc_NodeMffcInsideCollect(Abc_Obj_t *pNode)
Definition: abcRefs.c:382
Abc_ObjForEachFanin
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition: abc.h:524
Abc_ObjName
ABC_DLL char * Abc_ObjName(Abc_Obj_t *pNode)
DECLARATIONS ///.
Definition: abcNames.c:48
Abc_NtkIncrementTravId
static void Abc_NtkIncrementTravId(Abc_Ntk_t *p)
Definition: abc.h:406
Abc_NodeMffcConeSupp
void Abc_NodeMffcConeSupp(Abc_Obj_t *pNode, Vec_Ptr_t *vCone, Vec_Ptr_t *vSupp)
Definition: abcRefs.c:299
assert
#define assert(ex)
Definition: util_old.h:213
Vec_PtrClear
static void Vec_PtrClear(Vec_Ptr_t *p)
Definition: vecPtr.h:545
Vec_PtrForEachEntry
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
Abc_ObjIsComplement
static int Abc_ObjIsComplement(Abc_Obj_t *p)
Definition: abc.h:322
Abc_NodeMffcSize
int Abc_NodeMffcSize(Abc_Obj_t *pNode)
FUNCTION DEFINITIONS ///.
Definition: abcRefs.c:48
Abc_NodeMffcConeSupp_rec
void Abc_NodeMffcConeSupp_rec(Abc_Obj_t *pNode, Vec_Ptr_t *vCone, Vec_Ptr_t *vSupp, int fTopmost)
Definition: abcRefs.c:266
Abc_NodeSetTravIdCurrent
static void Abc_NodeSetTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:409
Vec_PtrFree
static void Vec_PtrFree(Vec_Ptr_t *p)
Definition: vecPtr.h:223