abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
abcReconv.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [abcReconv.c]
4 
5  SystemName [ABC: Logic synthesis and verification system.]
6 
7  PackageName [Network and node package.]
8 
9  Synopsis [Computation of reconvergence-driven cuts.]
10 
11  Author [Alan Mishchenko]
12 
13  Affiliation [UC Berkeley]
14 
15  Date [Ver. 1.0. Started - June 20, 2005.]
16 
17  Revision [$Id: abcReconv.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include "base/abc/abc.h"
22 #include "misc/extra/extraBdd.h"
23 
24 ABC_NAMESPACE_IMPL_START
25 
26 
27 ////////////////////////////////////////////////////////////////////////
28 /// DECLARATIONS ///
29 ////////////////////////////////////////////////////////////////////////
30 
31 struct Abc_ManCut_t_
32 {
33  // user specified parameters
34  int nNodeSizeMax; // the limit on the size of the supernode
35  int nConeSizeMax; // the limit on the size of the containing cone
36  int nNodeFanStop; // the limit on the size of the supernode
37  int nConeFanStop; // the limit on the size of the containing cone
38  // internal parameters
39  Vec_Ptr_t * vNodeLeaves; // fanins of the collapsed node (the cut)
40  Vec_Ptr_t * vConeLeaves; // fanins of the containing cone
41  Vec_Ptr_t * vVisited; // the visited nodes
42  Vec_Vec_t * vLevels; // the data structure to compute TFO nodes
43  Vec_Ptr_t * vNodesTfo; // the nodes in the TFO of the cut
44 };
45 
46 static int Abc_NodeBuildCutLevelOne_int( Vec_Ptr_t * vVisited, Vec_Ptr_t * vLeaves, int nSizeLimit, int nFaninLimit );
47 static int Abc_NodeBuildCutLevelTwo_int( Vec_Ptr_t * vVisited, Vec_Ptr_t * vLeaves, int nFaninLimit );
48 static void Abc_NodeConeMarkCollect_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vVisited );
49 
50 ////////////////////////////////////////////////////////////////////////
51 /// FUNCTION DEFINITIONS ///
52 ////////////////////////////////////////////////////////////////////////
53 
54 /**Function*************************************************************
55 
56  Synopsis [Unmarks the TFI cone.]
57 
58  Description []
59 
60  SideEffects []
61 
62  SeeAlso []
63 
64 ***********************************************************************/
65 static inline void Abc_NodesMark( Vec_Ptr_t * vVisited )
66 {
67  Abc_Obj_t * pNode;
68  int i;
69  Vec_PtrForEachEntry( Abc_Obj_t *, vVisited, pNode, i )
70  pNode->fMarkA = 1;
71 }
72 
73 /**Function*************************************************************
74 
75  Synopsis [Unmarks the TFI cone.]
76 
77  Description []
78 
79  SideEffects []
80 
81  SeeAlso []
82 
83 ***********************************************************************/
84 static inline void Abc_NodesUnmark( Vec_Ptr_t * vVisited )
85 {
86  Abc_Obj_t * pNode;
87  int i;
88  Vec_PtrForEachEntry( Abc_Obj_t *, vVisited, pNode, i )
89  pNode->fMarkA = 0;
90 }
91 
92 /**Function*************************************************************
93 
94  Synopsis [Unmarks the TFI cone.]
95 
96  Description []
97 
98  SideEffects []
99 
100  SeeAlso []
101 
102 ***********************************************************************/
103 static inline void Abc_NodesUnmarkB( Vec_Ptr_t * vVisited )
104 {
105  Abc_Obj_t * pNode;
106  int i;
107  Vec_PtrForEachEntry( Abc_Obj_t *, vVisited, pNode, i )
108  pNode->fMarkB = 0;
109 }
110 
111 /**Function*************************************************************
112 
113  Synopsis [Evaluate the cost of removing the node from the set of leaves.]
114 
115  Description [Returns the number of new leaves that will be brought in.
116  Returns large number if the node cannot be removed from the set of leaves.]
117 
118  SideEffects []
119 
120  SeeAlso []
121 
122 ***********************************************************************/
123 static inline int Abc_NodeGetLeafCostOne( Abc_Obj_t * pNode, int nFaninLimit )
124 {
125  int Cost;
126  // make sure the node is in the construction zone
127  assert( pNode->fMarkB == 1 );
128  // cannot expand over the PI node
129  if ( Abc_ObjIsCi(pNode) )
130  return 999;
131  // get the cost of the cone
132  Cost = (!Abc_ObjFanin0(pNode)->fMarkB) + (!Abc_ObjFanin1(pNode)->fMarkB);
133  // always accept if the number of leaves does not increase
134  if ( Cost < 2 )
135  return Cost;
136  // skip nodes with many fanouts
137  if ( Abc_ObjFanoutNum(pNode) > nFaninLimit )
138  return 999;
139  // return the number of nodes that will be on the leaves if this node is removed
140  return Cost;
141 }
142 
143 /**Function*************************************************************
144 
145  Synopsis [Evaluate the cost of removing the node from the set of leaves.]
146 
147  Description [Returns the number of new leaves that will be brought in.
148  Returns large number if the node cannot be removed from the set of leaves.]
149 
150  SideEffects []
151 
152  SeeAlso []
153 
154 ***********************************************************************/
155 static inline int Abc_NodeGetLeafCostTwo( Abc_Obj_t * pNode, int nFaninLimit,
156  Abc_Obj_t ** ppLeafToAdd, Abc_Obj_t ** pNodeToMark1, Abc_Obj_t ** pNodeToMark2 )
157 {
158  Abc_Obj_t * pFanin0, * pFanin1, * pTemp;
159  Abc_Obj_t * pGrand, * pGrandToAdd;
160  // make sure the node is in the construction zone
161  assert( pNode->fMarkB == 1 );
162  // cannot expand over the PI node
163  if ( Abc_ObjIsCi(pNode) )
164  return 999;
165  // skip nodes with many fanouts
166 // if ( Abc_ObjFanoutNum(pNode) > nFaninLimit )
167 // return 999;
168  // get the children
169  pFanin0 = Abc_ObjFanin0(pNode);
170  pFanin1 = Abc_ObjFanin1(pNode);
171  assert( !pFanin0->fMarkB && !pFanin1->fMarkB );
172  // count the number of unique grandchildren that will be included
173  // return infinite cost if this number if more than 1
174  if ( Abc_ObjIsCi(pFanin0) && Abc_ObjIsCi(pFanin1) )
175  return 999;
176  // consider the special case when a non-CI fanin can be dropped
177  if ( !Abc_ObjIsCi(pFanin0) && Abc_ObjFanin0(pFanin0)->fMarkB && Abc_ObjFanin1(pFanin0)->fMarkB )
178  {
179  *ppLeafToAdd = pFanin1;
180  *pNodeToMark1 = pFanin0;
181  *pNodeToMark2 = NULL;
182  return 1;
183  }
184  if ( !Abc_ObjIsCi(pFanin1) && Abc_ObjFanin0(pFanin1)->fMarkB && Abc_ObjFanin1(pFanin1)->fMarkB )
185  {
186  *ppLeafToAdd = pFanin0;
187  *pNodeToMark1 = pFanin1;
188  *pNodeToMark2 = NULL;
189  return 1;
190  }
191 
192  // make the first node CI if any
193  if ( Abc_ObjIsCi(pFanin1) )
194  pTemp = pFanin0, pFanin0 = pFanin1, pFanin1 = pTemp;
195  // consider the first node
196  pGrandToAdd = NULL;
197  if ( Abc_ObjIsCi(pFanin0) )
198  {
199  *pNodeToMark1 = NULL;
200  pGrandToAdd = pFanin0;
201  }
202  else
203  {
204  *pNodeToMark1 = pFanin0;
205  pGrand = Abc_ObjFanin0(pFanin0);
206  if ( !pGrand->fMarkB )
207  {
208  if ( pGrandToAdd && pGrandToAdd != pGrand )
209  return 999;
210  pGrandToAdd = pGrand;
211  }
212  pGrand = Abc_ObjFanin1(pFanin0);
213  if ( !pGrand->fMarkB )
214  {
215  if ( pGrandToAdd && pGrandToAdd != pGrand )
216  return 999;
217  pGrandToAdd = pGrand;
218  }
219  }
220  // consider the second node
221  *pNodeToMark2 = pFanin1;
222  pGrand = Abc_ObjFanin0(pFanin1);
223  if ( !pGrand->fMarkB )
224  {
225  if ( pGrandToAdd && pGrandToAdd != pGrand )
226  return 999;
227  pGrandToAdd = pGrand;
228  }
229  pGrand = Abc_ObjFanin1(pFanin1);
230  if ( !pGrand->fMarkB )
231  {
232  if ( pGrandToAdd && pGrandToAdd != pGrand )
233  return 999;
234  pGrandToAdd = pGrand;
235  }
236  assert( pGrandToAdd != NULL );
237  *ppLeafToAdd = pGrandToAdd;
238  return 1;
239 }
240 
241 
242 /**Function*************************************************************
243 
244  Synopsis [Finds a fanin-limited, reconvergence-driven cut for the node.]
245 
246  Description []
247 
248  SideEffects []
249 
250  SeeAlso []
251 
252 ***********************************************************************/
253 Vec_Ptr_t * Abc_NodeFindCut( Abc_ManCut_t * p, Abc_Obj_t * pRoot, int fContain )
254 {
255  Abc_Obj_t * pNode;
256  int i;
257 
258  assert( !Abc_ObjIsComplement(pRoot) );
259  assert( Abc_ObjIsNode(pRoot) );
260 
261  // start the visited nodes and mark them
262  Vec_PtrClear( p->vVisited );
263  Vec_PtrPush( p->vVisited, pRoot );
264  Vec_PtrPush( p->vVisited, Abc_ObjFanin0(pRoot) );
265  Vec_PtrPush( p->vVisited, Abc_ObjFanin1(pRoot) );
266  pRoot->fMarkB = 1;
267  Abc_ObjFanin0(pRoot)->fMarkB = 1;
268  Abc_ObjFanin1(pRoot)->fMarkB = 1;
269 
270  // start the cut
271  Vec_PtrClear( p->vNodeLeaves );
272  Vec_PtrPush( p->vNodeLeaves, Abc_ObjFanin0(pRoot) );
273  Vec_PtrPush( p->vNodeLeaves, Abc_ObjFanin1(pRoot) );
274 
275  // compute the cut
276  while ( Abc_NodeBuildCutLevelOne_int( p->vVisited, p->vNodeLeaves, p->nNodeSizeMax, p->nNodeFanStop ) );
277  assert( Vec_PtrSize(p->vNodeLeaves) <= p->nNodeSizeMax );
278 
279  // return if containing cut is not requested
280  if ( !fContain )
281  {
282  // unmark both fMarkA and fMarkB in tbe TFI
283  Abc_NodesUnmarkB( p->vVisited );
284  return p->vNodeLeaves;
285  }
286 
287 //printf( "\n\n\n" );
288  // compute the containing cut
289  assert( p->nNodeSizeMax < p->nConeSizeMax );
290  // copy the current boundary
291  Vec_PtrClear( p->vConeLeaves );
292  Vec_PtrForEachEntry( Abc_Obj_t *, p->vNodeLeaves, pNode, i )
293  Vec_PtrPush( p->vConeLeaves, pNode );
294  // compute the containing cut
295  while ( Abc_NodeBuildCutLevelOne_int( p->vVisited, p->vConeLeaves, p->nConeSizeMax, p->nConeFanStop ) );
296  assert( Vec_PtrSize(p->vConeLeaves) <= p->nConeSizeMax );
297  // unmark TFI using fMarkA and fMarkB
298  Abc_NodesUnmarkB( p->vVisited );
299  return p->vNodeLeaves;
300 }
301 
302 /**Function*************************************************************
303 
304  Synopsis [Builds reconvergence-driven cut by changing one leaf at a time.]
305 
306  Description [This procedure looks at the current leaves and tries to change
307  one leaf at a time in such a way that the cut grows as little as possible.
308  In evaluating the fanins, this procedure looks only at their immediate
309  predecessors (this is why it is called a one-level construction procedure).]
310 
311  SideEffects []
312 
313  SeeAlso []
314 
315 ***********************************************************************/
316 int Abc_NodeBuildCutLevelOne_int( Vec_Ptr_t * vVisited, Vec_Ptr_t * vLeaves, int nSizeLimit, int nFaninLimit )
317 {
318  Abc_Obj_t * pNode, * pFaninBest, * pNext;
319  int CostBest, CostCur, i;
320  // find the best fanin
321  CostBest = 100;
322  pFaninBest = NULL;
323 //printf( "Evaluating fanins of the cut:\n" );
324  Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pNode, i )
325  {
326  CostCur = Abc_NodeGetLeafCostOne( pNode, nFaninLimit );
327 //printf( " Fanin %s has cost %d.\n", Abc_ObjName(pNode), CostCur );
328 // if ( CostBest > CostCur ) // performance improvement: expand the variable with the smallest level
329  if ( CostBest > CostCur ||
330  (CostBest == CostCur && pNode->Level > pFaninBest->Level) )
331  {
332  CostBest = CostCur;
333  pFaninBest = pNode;
334  }
335  if ( CostBest == 0 )
336  break;
337  }
338  if ( pFaninBest == NULL )
339  return 0;
340 // return Abc_NodeBuildCutLevelTwo_int( vVisited, vLeaves, nFaninLimit );
341 
342  assert( CostBest < 3 );
343  if ( vLeaves->nSize - 1 + CostBest > nSizeLimit )
344  return 0;
345 // return Abc_NodeBuildCutLevelTwo_int( vVisited, vLeaves, nFaninLimit );
346 
347  assert( Abc_ObjIsNode(pFaninBest) );
348  // remove the node from the array
349  Vec_PtrRemove( vLeaves, pFaninBest );
350 //printf( "Removing fanin %s.\n", Abc_ObjName(pFaninBest) );
351 
352  // add the left child to the fanins
353  pNext = Abc_ObjFanin0(pFaninBest);
354  if ( !pNext->fMarkB )
355  {
356 //printf( "Adding fanin %s.\n", Abc_ObjName(pNext) );
357  pNext->fMarkB = 1;
358  Vec_PtrPush( vLeaves, pNext );
359  Vec_PtrPush( vVisited, pNext );
360  }
361  // add the right child to the fanins
362  pNext = Abc_ObjFanin1(pFaninBest);
363  if ( !pNext->fMarkB )
364  {
365 //printf( "Adding fanin %s.\n", Abc_ObjName(pNext) );
366  pNext->fMarkB = 1;
367  Vec_PtrPush( vLeaves, pNext );
368  Vec_PtrPush( vVisited, pNext );
369  }
370  assert( vLeaves->nSize <= nSizeLimit );
371  // keep doing this
372  return 1;
373 }
374 
375 /**Function*************************************************************
376 
377  Synopsis [Builds reconvergence-driven cut by changing one leaf at a time.]
378 
379  Description [This procedure looks at the current leaves and tries to change
380  one leaf at a time in such a way that the cut grows as little as possible.
381  In evaluating the fanins, this procedure looks across two levels of fanins
382  (this is why it is called a two-level construction procedure).]
383 
384  SideEffects []
385 
386  SeeAlso []
387 
388 ***********************************************************************/
389 int Abc_NodeBuildCutLevelTwo_int( Vec_Ptr_t * vVisited, Vec_Ptr_t * vLeaves, int nFaninLimit )
390 {
391  Abc_Obj_t * pNode = NULL, * pLeafToAdd, * pNodeToMark1, * pNodeToMark2;
392  int CostCur = 0, i;
393  // find the best fanin
394  Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pNode, i )
395  {
396  CostCur = Abc_NodeGetLeafCostTwo( pNode, nFaninLimit, &pLeafToAdd, &pNodeToMark1, &pNodeToMark2 );
397  if ( CostCur < 2 )
398  break;
399  }
400  if ( CostCur > 2 )
401  return 0;
402  // remove the node from the array
403  Vec_PtrRemove( vLeaves, pNode );
404  // add the node to the leaves
405  if ( pLeafToAdd )
406  {
407  assert( !pLeafToAdd->fMarkB );
408  pLeafToAdd->fMarkB = 1;
409  Vec_PtrPush( vLeaves, pLeafToAdd );
410  Vec_PtrPush( vVisited, pLeafToAdd );
411  }
412  // mark the other nodes
413  if ( pNodeToMark1 )
414  {
415  assert( !pNodeToMark1->fMarkB );
416  pNodeToMark1->fMarkB = 1;
417  Vec_PtrPush( vVisited, pNodeToMark1 );
418  }
419  if ( pNodeToMark2 )
420  {
421  assert( !pNodeToMark2->fMarkB );
422  pNodeToMark2->fMarkB = 1;
423  Vec_PtrPush( vVisited, pNodeToMark2 );
424  }
425  // keep doing this
426  return 1;
427 }
428 
429 
430 /**Function*************************************************************
431 
432  Synopsis [Get the nodes contained in the cut.]
433 
434  Description []
435 
436  SideEffects []
437 
438  SeeAlso []
439 
440 ***********************************************************************/
441 void Abc_NodeConeCollect( Abc_Obj_t ** ppRoots, int nRoots, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vVisited, int fIncludeFanins )
442 {
443  Abc_Obj_t * pTemp;
444  int i;
445  // mark the fanins of the cone
446  Abc_NodesMark( vLeaves );
447  // collect the nodes in the DFS order
448  Vec_PtrClear( vVisited );
449  // add the fanins
450  if ( fIncludeFanins )
451  Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pTemp, i )
452  Vec_PtrPush( vVisited, pTemp );
453  // add other nodes
454  for ( i = 0; i < nRoots; i++ )
455  Abc_NodeConeMarkCollect_rec( ppRoots[i], vVisited );
456  // unmark both sets
457  Abc_NodesUnmark( vLeaves );
458  Abc_NodesUnmark( vVisited );
459 }
460 
461 /**Function*************************************************************
462 
463  Synopsis [Marks the TFI cone.]
464 
465  Description []
466 
467  SideEffects []
468 
469  SeeAlso []
470 
471 ***********************************************************************/
472 void Abc_NodeConeMarkCollect_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vVisited )
473 {
474  if ( pNode->fMarkA == 1 )
475  return;
476  // visit transitive fanin
477  if ( Abc_ObjIsNode(pNode) )
478  {
479  Abc_NodeConeMarkCollect_rec( Abc_ObjFanin0(pNode), vVisited );
480  Abc_NodeConeMarkCollect_rec( Abc_ObjFanin1(pNode), vVisited );
481  }
482  assert( pNode->fMarkA == 0 );
483  pNode->fMarkA = 1;
484  Vec_PtrPush( vVisited, pNode );
485 }
486 
487 /**Function*************************************************************
488 
489  Synopsis [Returns BDD representing the logic function of the cone.]
490 
491  Description []
492 
493  SideEffects []
494 
495  SeeAlso []
496 
497 ***********************************************************************/
498 DdNode * Abc_NodeConeBdd( DdManager * dd, DdNode ** pbVars, Abc_Obj_t * pRoot, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vVisited )
499 {
500  Abc_Obj_t * pNode;
501  DdNode * bFunc0, * bFunc1, * bFunc = NULL;
502  int i;
503  // get the nodes in the cut without fanins in the DFS order
504  Abc_NodeConeCollect( &pRoot, 1, vLeaves, vVisited, 0 );
505  // set the elementary BDDs
506  Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pNode, i )
507  pNode->pCopy = (Abc_Obj_t *)pbVars[i];
508  // compute the BDDs for the collected nodes
509  Vec_PtrForEachEntry( Abc_Obj_t *, vVisited, pNode, i )
510  {
511  assert( !Abc_ObjIsPi(pNode) );
512  bFunc0 = Cudd_NotCond( Abc_ObjFanin0(pNode)->pCopy, (int)Abc_ObjFaninC0(pNode) );
513  bFunc1 = Cudd_NotCond( Abc_ObjFanin1(pNode)->pCopy, (int)Abc_ObjFaninC1(pNode) );
514  bFunc = Cudd_bddAnd( dd, bFunc0, bFunc1 ); Cudd_Ref( bFunc );
515  pNode->pCopy = (Abc_Obj_t *)bFunc;
516  }
517  assert(bFunc);
518  Cudd_Ref( bFunc );
519  // dereference the intermediate ones
520  Vec_PtrForEachEntry( Abc_Obj_t *, vVisited, pNode, i )
521  Cudd_RecursiveDeref( dd, (DdNode *)pNode->pCopy );
522  Cudd_Deref( bFunc );
523  return bFunc;
524 }
525 
526 /**Function*************************************************************
527 
528  Synopsis [Returns BDD representing the transition relation of the cone.]
529 
530  Description []
531 
532  SideEffects []
533 
534  SeeAlso []
535 
536 ***********************************************************************/
537 DdNode * Abc_NodeConeDcs( DdManager * dd, DdNode ** pbVarsX, DdNode ** pbVarsY, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vRoots, Vec_Ptr_t * vVisited )
538 {
539  DdNode * bFunc0, * bFunc1, * bFunc, * bTrans, * bTemp, * bCube, * bResult;
540  Abc_Obj_t * pNode;
541  int i;
542  // get the nodes in the cut without fanins in the DFS order
543  Abc_NodeConeCollect( (Abc_Obj_t **)vRoots->pArray, vRoots->nSize, vLeaves, vVisited, 0 );
544  // set the elementary BDDs
545  Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pNode, i )
546  pNode->pCopy = (Abc_Obj_t *)pbVarsX[i];
547  // compute the BDDs for the collected nodes
548  Vec_PtrForEachEntry( Abc_Obj_t *, vVisited, pNode, i )
549  {
550  bFunc0 = Cudd_NotCond( Abc_ObjFanin0(pNode)->pCopy, (int)Abc_ObjFaninC0(pNode) );
551  bFunc1 = Cudd_NotCond( Abc_ObjFanin1(pNode)->pCopy, (int)Abc_ObjFaninC1(pNode) );
552  bFunc = Cudd_bddAnd( dd, bFunc0, bFunc1 ); Cudd_Ref( bFunc );
553  pNode->pCopy = (Abc_Obj_t *)bFunc;
554  }
555  // compute the transition relation of the cone
556  bTrans = b1; Cudd_Ref( bTrans );
557  Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pNode, i )
558  {
559  bFunc = Cudd_bddXnor( dd, (DdNode *)pNode->pCopy, pbVarsY[i] ); Cudd_Ref( bFunc );
560  bTrans = Cudd_bddAnd( dd, bTemp = bTrans, bFunc ); Cudd_Ref( bTrans );
561  Cudd_RecursiveDeref( dd, bTemp );
562  Cudd_RecursiveDeref( dd, bFunc );
563  }
564  // dereference the intermediate ones
565  Vec_PtrForEachEntry( Abc_Obj_t *, vVisited, pNode, i )
566  Cudd_RecursiveDeref( dd, (DdNode *)pNode->pCopy );
567  // compute don't-cares
568  bCube = Extra_bddComputeRangeCube( dd, vRoots->nSize, vRoots->nSize + vLeaves->nSize ); Cudd_Ref( bCube );
569  bResult = Cudd_bddExistAbstract( dd, bTrans, bCube ); Cudd_Ref( bResult );
570  bResult = Cudd_Not( bResult );
571  Cudd_RecursiveDeref( dd, bCube );
572  Cudd_RecursiveDeref( dd, bTrans );
573  Cudd_Deref( bResult );
574  return bResult;
575 }
576 
577 /**Function*************************************************************
578 
579  Synopsis [Starts the resynthesis manager.]
580 
581  Description []
582 
583  SideEffects []
584 
585  SeeAlso []
586 
587 ***********************************************************************/
588 Abc_ManCut_t * Abc_NtkManCutStart( int nNodeSizeMax, int nConeSizeMax, int nNodeFanStop, int nConeFanStop )
589 {
590  Abc_ManCut_t * p;
591  p = ABC_ALLOC( Abc_ManCut_t, 1 );
592  memset( p, 0, sizeof(Abc_ManCut_t) );
593  p->vNodeLeaves = Vec_PtrAlloc( 100 );
594  p->vConeLeaves = Vec_PtrAlloc( 100 );
595  p->vVisited = Vec_PtrAlloc( 100 );
596  p->vLevels = Vec_VecAlloc( 100 );
597  p->vNodesTfo = Vec_PtrAlloc( 100 );
598  p->nNodeSizeMax = nNodeSizeMax;
599  p->nConeSizeMax = nConeSizeMax;
600  p->nNodeFanStop = nNodeFanStop;
601  p->nConeFanStop = nConeFanStop;
602  return p;
603 }
604 
605 /**Function*************************************************************
606 
607  Synopsis [Stops the resynthesis manager.]
608 
609  Description []
610 
611  SideEffects []
612 
613  SeeAlso []
614 
615 ***********************************************************************/
616 void Abc_NtkManCutStop( Abc_ManCut_t * p )
617 {
618  Vec_PtrFree( p->vNodeLeaves );
619  Vec_PtrFree( p->vConeLeaves );
620  Vec_PtrFree( p->vVisited );
621  Vec_VecFree( p->vLevels );
622  Vec_PtrFree( p->vNodesTfo );
623  ABC_FREE( p );
624 }
625 
626 /**Function*************************************************************
627 
628  Synopsis [Returns the leaves of the cone.]
629 
630  Description []
631 
632  SideEffects []
633 
634  SeeAlso []
635 
636 ***********************************************************************/
637 Vec_Ptr_t * Abc_NtkManCutReadCutLarge( Abc_ManCut_t * p )
638 {
639  return p->vConeLeaves;
640 }
641 
642 /**Function*************************************************************
643 
644  Synopsis [Returns the leaves of the cone.]
645 
646  Description []
647 
648  SideEffects []
649 
650  SeeAlso []
651 
652 ***********************************************************************/
653 Vec_Ptr_t * Abc_NtkManCutReadCutSmall( Abc_ManCut_t * p )
654 {
655  return p->vNodeLeaves;
656 }
657 
658 /**Function*************************************************************
659 
660  Synopsis [Returns the leaves of the cone.]
661 
662  Description []
663 
664  SideEffects []
665 
666  SeeAlso []
667 
668 ***********************************************************************/
669 Vec_Ptr_t * Abc_NtkManCutReadVisited( Abc_ManCut_t * p )
670 {
671  return p->vVisited;
672 }
673 
674 
675 
676 /**Function*************************************************************
677 
678  Synopsis [Collects the TFO of the cut in the topological order.]
679 
680  Description [TFO of the cut is defined as a set of nodes, for which the cut
681  is a cut, that is, every path from the collected nodes to the CIs goes through
682  a node in the cut. The nodes are collected if their level does not exceed
683  the given number (LevelMax). The nodes are returned in the topological order.
684  If the root node is given, its MFFC is marked, so that the collected nodes
685  do not contain any nodes in the MFFC.]
686 
687  SideEffects []
688 
689  SeeAlso []
690 
691 ***********************************************************************/
692 Vec_Ptr_t * Abc_NodeCollectTfoCands( Abc_ManCut_t * p, Abc_Obj_t * pRoot, Vec_Ptr_t * vLeaves, int LevelMax )
693 {
694  Abc_Ntk_t * pNtk = pRoot->pNtk;
695  Vec_Ptr_t * vVec;
696  Abc_Obj_t * pNode, * pFanout;
697  int i, k, v, LevelMin;
698  assert( Abc_NtkIsStrash(pNtk) );
699 
700  // assuming that the structure is clean
701  Vec_VecForEachLevel( p->vLevels, vVec, i )
702  assert( vVec->nSize == 0 );
703 
704  // put fanins into the structure while labeling them
705  Abc_NtkIncrementTravId( pNtk );
706  LevelMin = -1;
707  Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pNode, i )
708  {
709  if ( pNode->Level > (unsigned)LevelMax )
710  continue;
711  Abc_NodeSetTravIdCurrent( pNode );
712  Vec_VecPush( p->vLevels, pNode->Level, pNode );
713  if ( LevelMin < (int)pNode->Level )
714  LevelMin = pNode->Level;
715  }
716  assert( LevelMin >= 0 );
717 
718  // mark MFFC
719  if ( pRoot )
720  Abc_NodeMffcLabelAig( pRoot );
721 
722  // go through the levels up
723  Vec_PtrClear( p->vNodesTfo );
724  Vec_VecForEachEntryStart( Abc_Obj_t *, p->vLevels, pNode, i, k, LevelMin )
725  {
726  if ( i > LevelMax )
727  break;
728  // if the node is not marked, it is not a fanin
729  if ( !Abc_NodeIsTravIdCurrent(pNode) )
730  {
731  // check if it belongs to the TFO
732  if ( !Abc_NodeIsTravIdCurrent(Abc_ObjFanin0(pNode)) ||
733  !Abc_NodeIsTravIdCurrent(Abc_ObjFanin1(pNode)) )
734  continue;
735  // save the node in the TFO and label it
736  Vec_PtrPush( p->vNodesTfo, pNode );
737  Abc_NodeSetTravIdCurrent( pNode );
738  }
739  // go through the fanouts and add them to the structure if they meet the conditions
740  Abc_ObjForEachFanout( pNode, pFanout, v )
741  {
742  // skip if fanout is a CO or its level exceeds
743  if ( Abc_ObjIsCo(pFanout) || pFanout->Level > (unsigned)LevelMax )
744  continue;
745  // skip if it is already added or if it is in MFFC
746  if ( Abc_NodeIsTravIdCurrent(pFanout) )
747  continue;
748  // add it to the structure but do not mark it (until tested later)
749  Vec_VecPushUnique( p->vLevels, pFanout->Level, pFanout );
750  }
751  }
752 
753  // clear the levelized structure
754  Vec_VecForEachLevelStart( p->vLevels, vVec, i, LevelMin )
755  {
756  if ( i > LevelMax )
757  break;
758  Vec_PtrClear( vVec );
759  }
760  return p->vNodesTfo;
761 }
762 
763 ////////////////////////////////////////////////////////////////////////
764 /// END OF FILE ///
765 ////////////////////////////////////////////////////////////////////////
766 
767 
768 ABC_NAMESPACE_IMPL_END
769 
memset
char * memset()
Vec_VecForEachLevel
#define Vec_VecForEachLevel(vGlob, vVec, i)
MACRO DEFINITIONS ///.
Definition: vecVec.h:55
Abc_ManCut_t_::vConeLeaves
Vec_Ptr_t * vConeLeaves
Definition: abcReconv.c:40
Abc_NodeConeBdd
DdNode * Abc_NodeConeBdd(DdManager *dd, DdNode **pbVars, Abc_Obj_t *pRoot, Vec_Ptr_t *vLeaves, Vec_Ptr_t *vVisited)
Definition: abcReconv.c:498
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
Vec_VecPush
static void Vec_VecPush(Vec_Vec_t *p, int Level, void *Entry)
Definition: vecVec.h:456
Vec_VecAlloc
static Vec_Vec_t * Vec_VecAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecVec.h:145
Abc_ObjIsCi
static int Abc_ObjIsCi(Abc_Obj_t *pObj)
Definition: abc.h:351
Abc_Obj_t_::fMarkA
unsigned fMarkA
Definition: abc.h:134
Cudd_RecursiveDeref
void Cudd_RecursiveDeref(DdManager *table, DdNode *n)
Definition: cuddRef.c:154
DdNode
Definition: cudd.h:278
Cudd_Not
#define Cudd_Not(node)
Definition: cudd.h:367
Abc_NodesMark
static void Abc_NodesMark(Vec_Ptr_t *vVisited)
FUNCTION DEFINITIONS ///.
Definition: abcReconv.c:65
Vec_Vec_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Vec_t_ Vec_Vec_t
INCLUDES ///.
Definition: vecVec.h:42
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Abc_ObjFaninC1
static int Abc_ObjFaninC1(Abc_Obj_t *pObj)
Definition: abc.h:378
Abc_ManCut_t_::vNodeLeaves
Vec_Ptr_t * vNodeLeaves
Definition: abcReconv.c:39
Abc_NtkManCutReadCutLarge
Vec_Ptr_t * Abc_NtkManCutReadCutLarge(Abc_ManCut_t *p)
Definition: abcReconv.c:637
Cudd_Deref
void Cudd_Deref(DdNode *node)
Definition: cuddRef.c:438
Abc_NodeConeMarkCollect_rec
static void Abc_NodeConeMarkCollect_rec(Abc_Obj_t *pNode, Vec_Ptr_t *vVisited)
Definition: abcReconv.c:472
Abc_Ntk_t_
Definition: abc.h:153
Abc_ObjFanoutNum
static int Abc_ObjFanoutNum(Abc_Obj_t *pObj)
Definition: abc.h:365
b1
#define b1
Definition: extraBdd.h:76
Vec_VecForEachLevelStart
#define Vec_VecForEachLevelStart(vGlob, vVec, i, LevelStart)
Definition: vecVec.h:57
Cudd_bddExistAbstract
DdNode * Cudd_bddExistAbstract(DdManager *manager, DdNode *f, DdNode *cube)
Definition: cuddBddAbs.c:130
Abc_NodeBuildCutLevelTwo_int
static int Abc_NodeBuildCutLevelTwo_int(Vec_Ptr_t *vVisited, Vec_Ptr_t *vLeaves, int nFaninLimit)
Definition: abcReconv.c:389
Abc_ObjFaninC0
static int Abc_ObjFaninC0(Abc_Obj_t *pObj)
Definition: abc.h:377
Abc_ObjIsPi
static int Abc_ObjIsPi(Abc_Obj_t *pObj)
Definition: abc.h:347
Vec_PtrPush
static void Vec_PtrPush(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:606
Abc_ManCut_t_::nNodeSizeMax
int nNodeSizeMax
Definition: abcReconv.c:34
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Abc_NodeMffcLabelAig
ABC_DLL int Abc_NodeMffcLabelAig(Abc_Obj_t *pNode)
Definition: abcRefs.c:100
Abc_NodeConeCollect
void Abc_NodeConeCollect(Abc_Obj_t **ppRoots, int nRoots, Vec_Ptr_t *vLeaves, Vec_Ptr_t *vVisited, int fIncludeFanins)
Definition: abcReconv.c:441
Abc_NtkManCutStart
Abc_ManCut_t * Abc_NtkManCutStart(int nNodeSizeMax, int nConeSizeMax, int nNodeFanStop, int nConeFanStop)
Definition: abcReconv.c:588
Abc_ManCut_t_::nConeFanStop
int nConeFanStop
Definition: abcReconv.c:37
Vec_PtrSize
static int Vec_PtrSize(Vec_Ptr_t *p)
Definition: vecPtr.h:295
Vec_VecFree
static void Vec_VecFree(Vec_Vec_t *p)
Definition: vecVec.h:347
Abc_ObjFanin0
static Abc_Obj_t * Abc_ObjFanin0(Abc_Obj_t *pObj)
Definition: abc.h:373
Vec_PtrRemove
static void Vec_PtrRemove(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:714
Abc_Obj_t_::Level
unsigned Level
Definition: abc.h:142
Abc_ObjIsCo
static int Abc_ObjIsCo(Abc_Obj_t *pObj)
Definition: abc.h:352
Abc_NodesUnmark
static void Abc_NodesUnmark(Vec_Ptr_t *vVisited)
Definition: abcReconv.c:84
Abc_Obj_t_
Definition: abc.h:128
Abc_ManCut_t_::nNodeFanStop
int nNodeFanStop
Definition: abcReconv.c:36
Abc_ObjIsNode
static int Abc_ObjIsNode(Abc_Obj_t *pObj)
Definition: abc.h:355
Abc_NodeGetLeafCostOne
static int Abc_NodeGetLeafCostOne(Abc_Obj_t *pNode, int nFaninLimit)
Definition: abcReconv.c:123
Abc_Obj_t_::pCopy
Abc_Obj_t * pCopy
Definition: abc.h:148
Extra_bddComputeRangeCube
DdNode * Extra_bddComputeRangeCube(DdManager *dd, int iStart, int iStop)
Definition: extraBddMisc.c:699
Abc_ManCut_t_::nConeSizeMax
int nConeSizeMax
Definition: abcReconv.c:35
Abc_NodeFindCut
Vec_Ptr_t * Abc_NodeFindCut(Abc_ManCut_t *p, Abc_Obj_t *pRoot, int fContain)
Definition: abcReconv.c:253
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
Abc_NodeBuildCutLevelOne_int
static int Abc_NodeBuildCutLevelOne_int(Vec_Ptr_t *vVisited, Vec_Ptr_t *vLeaves, int nSizeLimit, int nFaninLimit)
Definition: abcReconv.c:316
Abc_NtkManCutReadVisited
Vec_Ptr_t * Abc_NtkManCutReadVisited(Abc_ManCut_t *p)
Definition: abcReconv.c:669
Abc_NtkManCutReadCutSmall
Vec_Ptr_t * Abc_NtkManCutReadCutSmall(Abc_ManCut_t *p)
Definition: abcReconv.c:653
Cudd_bddXnor
DdNode * Cudd_bddXnor(DdManager *dd, DdNode *f, DdNode *g)
Definition: cuddBddIte.c:507
Abc_NodeConeDcs
DdNode * Abc_NodeConeDcs(DdManager *dd, DdNode **pbVarsX, DdNode **pbVarsY, Vec_Ptr_t *vLeaves, Vec_Ptr_t *vRoots, Vec_Ptr_t *vVisited)
Definition: abcReconv.c:537
Vec_VecForEachEntryStart
#define Vec_VecForEachEntryStart(Type, vGlob, pEntry, i, k, LevelStart)
Definition: vecVec.h:92
ABC_NAMESPACE_IMPL_START
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
Abc_NodeIsTravIdCurrent
static int Abc_NodeIsTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:411
Abc_ManCut_t_::vVisited
Vec_Ptr_t * vVisited
Definition: abcReconv.c:41
Abc_Obj_t_::pNtk
Abc_Ntk_t * pNtk
Definition: abc.h:130
Abc_Obj_t_::fMarkB
unsigned fMarkB
Definition: abc.h:135
Abc_NtkManCutStop
void Abc_NtkManCutStop(Abc_ManCut_t *p)
Definition: abcReconv.c:616
Abc_ObjForEachFanout
#define Abc_ObjForEachFanout(pObj, pFanout, i)
Definition: abc.h:526
Vec_PtrAlloc
static Vec_Ptr_t * Vec_PtrAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecPtr.h:83
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
Abc_NtkIncrementTravId
static void Abc_NtkIncrementTravId(Abc_Ntk_t *p)
Definition: abc.h:406
Abc_NodeCollectTfoCands
Vec_Ptr_t * Abc_NodeCollectTfoCands(Abc_ManCut_t *p, Abc_Obj_t *pRoot, Vec_Ptr_t *vLeaves, int LevelMax)
Definition: abcReconv.c:692
Cudd_NotCond
#define Cudd_NotCond(node, c)
Definition: cudd.h:383
Cudd_bddAnd
DdNode * Cudd_bddAnd(DdManager *dd, DdNode *f, DdNode *g)
Definition: cuddBddIte.c:314
assert
#define assert(ex)
Definition: util_old.h:213
Vec_PtrClear
static void Vec_PtrClear(Vec_Ptr_t *p)
Definition: vecPtr.h:545
Cudd_Ref
void Cudd_Ref(DdNode *n)
Definition: cuddRef.c:129
Abc_ManCut_t_::vLevels
Vec_Vec_t * vLevels
Definition: abcReconv.c:42
Vec_PtrForEachEntry
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
Abc_NodeGetLeafCostTwo
static int Abc_NodeGetLeafCostTwo(Abc_Obj_t *pNode, int nFaninLimit, Abc_Obj_t **ppLeafToAdd, Abc_Obj_t **pNodeToMark1, Abc_Obj_t **pNodeToMark2)
Definition: abcReconv.c:155
Abc_ObjIsComplement
static int Abc_ObjIsComplement(Abc_Obj_t *p)
Definition: abc.h:322
Abc_NodesUnmarkB
static void Abc_NodesUnmarkB(Vec_Ptr_t *vVisited)
Definition: abcReconv.c:103
Abc_ManCut_t_
DECLARATIONS ///.
Definition: abcReconv.c:31
Abc_ManCut_t_::vNodesTfo
Vec_Ptr_t * vNodesTfo
Definition: abcReconv.c:43
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
Vec_VecPushUnique
static void Vec_VecPushUnique(Vec_Vec_t *p, int Level, void *Entry)
Definition: vecVec.h:492