abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
abcMffc.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [abcMffc.c]
4 
5  SystemName [ABC: Logic synthesis and verification system.]
6 
7  PackageName [Network and node package.]
8 
9  Synopsis [Computing multi-output maximum fanout-free cones.]
10 
11  Author [Alan Mishchenko]
12 
13  Affiliation [UC Berkeley]
14 
15  Date [Ver. 1.0. Started - June 20, 2005.]
16 
17  Revision [$Id: abcMffc.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include "base/abc/abc.h"
22 
23 ABC_NAMESPACE_IMPL_START
24 
25 ////////////////////////////////////////////////////////////////////////
26 /// DECLARATIONS ///
27 ////////////////////////////////////////////////////////////////////////
28 
29 ////////////////////////////////////////////////////////////////////////
30 /// FUNCTION DEFINITIONS ///
31 ////////////////////////////////////////////////////////////////////////
32 
33 /**Function*************************************************************
34 
35  Synopsis [Dereferences and collects the nodes.]
36 
37  Description []
38 
39  SideEffects []
40 
41  SeeAlso []
42 
43 ***********************************************************************/
44 void Abc_MffcDeref_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vNodes )
45 {
46  Abc_Obj_t * pFanin;
47  int i;
48  if ( Abc_ObjIsCi(pNode) )
49  return;
50  Abc_ObjForEachFanin( pNode, pFanin, i )
51  {
52  assert( pFanin->vFanouts.nSize > 0 );
53  if ( --pFanin->vFanouts.nSize == 0 )
54  Abc_MffcDeref_rec( pFanin, vNodes );
55  }
56  if ( vNodes )
57  Vec_PtrPush( vNodes, pNode );
58 }
59 
60 /**Function*************************************************************
61 
62  Synopsis [References the nodes.]
63 
64  Description []
65 
66  SideEffects []
67 
68  SeeAlso []
69 
70 ***********************************************************************/
71 void Abc_MffcRef_rec( Abc_Obj_t * pNode )
72 {
73  Abc_Obj_t * pFanin;
74  int i;
75  if ( Abc_ObjIsCi(pNode) )
76  return;
77  Abc_ObjForEachFanin( pNode, pFanin, i )
78  {
79  if ( pFanin->vFanouts.nSize++ == 0 )
80  Abc_MffcRef_rec( pFanin );
81  }
82 }
83 
84 /**Function*************************************************************
85 
86  Synopsis [Collects nodes belonging to the MFFC.]
87 
88  Description []
89 
90  SideEffects []
91 
92  SeeAlso []
93 
94 ***********************************************************************/
95 void Abc_MffcCollectNodes( Abc_Obj_t ** pNodes, int nNodes, Vec_Ptr_t * vNodes )
96 {
97  int i;
98  Vec_PtrClear( vNodes );
99  for ( i = 0; i < nNodes; i++ )
100  Abc_MffcDeref_rec( pNodes[i], vNodes );
101  for ( i = 0; i < nNodes; i++ )
102  Abc_MffcRef_rec( pNodes[i] );
103 }
104 
105 /**Function*************************************************************
106 
107  Synopsis [Collects leaves of the MFFC.]
108 
109  Description []
110 
111  SideEffects []
112 
113  SeeAlso []
114 
115 ***********************************************************************/
116 void Abc_MffcCollectLeaves( Vec_Ptr_t * vNodes, Vec_Ptr_t * vLeaves )
117 {
118  Abc_Obj_t * pNode, * pFanin;
119  int i, k;
120  assert( Vec_PtrSize(vNodes) > 0 );
121  pNode = (Abc_Obj_t *)Vec_PtrEntry( vNodes, 0 );
122  // label them
123  Abc_NtkIncrementTravId( pNode->pNtk );
124  Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
125  Abc_NodeSetTravIdCurrent( pNode );
126  // collect non-labeled fanins
127  Vec_PtrClear( vLeaves );
128  Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
129  Abc_ObjForEachFanin( pNode, pFanin, k )
130  {
131  if ( Abc_NodeIsTravIdCurrent(pFanin) )
132  continue;
133  Abc_NodeSetTravIdCurrent( pFanin );
134  Vec_PtrPush( vLeaves, pFanin );
135  }
136 }
137 
138 /**Function*************************************************************
139 
140  Synopsis [Collects internal nodes that are roots of MFFCs.]
141 
142  Description []
143 
144  SideEffects []
145 
146  SeeAlso []
147 
148 ***********************************************************************/
149 Vec_Ptr_t * Abc_NktMffcMarkRoots( Abc_Ntk_t * pNtk, int fSkipPis )
150 {
151  Vec_Ptr_t * vRoots, * vNodes, * vLeaves;
152  Abc_Obj_t * pObj, * pLeaf;
153  int i, k;
154  Abc_NtkCleanMarkA( pNtk );
155  // mark the drivers of combinational outputs
156  vRoots = Vec_PtrAlloc( 1000 );
157  Abc_NtkForEachCo( pNtk, pObj, i )
158  {
159  pObj = Abc_ObjFanin0( pObj );
160 // if ( Abc_ObjIsCi(pObj) || Abc_ObjFaninNum(pObj) == 0 || pObj->fMarkA )
161  if ( Abc_ObjIsCi(pObj) || pObj->fMarkA )
162  continue;
163  pObj->fMarkA = 1;
164  Vec_PtrPush( vRoots, pObj );
165  }
166  // explore starting from the drivers
167  vNodes = Vec_PtrAlloc( 100 );
168  vLeaves = Vec_PtrAlloc( 100 );
169  Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
170  {
171  if ( Abc_ObjIsCi(pObj) )
172  continue;
173  // collect internal nodes
174  Abc_MffcCollectNodes( &pObj, 1, vNodes );
175  // collect leaves
176  Abc_MffcCollectLeaves( vNodes, vLeaves );
177  // add non-PI leaves
178  Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pLeaf, k )
179  {
180  if ( (fSkipPis && Abc_ObjIsCi(pLeaf)) || pLeaf->fMarkA )
181  continue;
182  pLeaf->fMarkA = 1;
183  Vec_PtrPush( vRoots, pLeaf );
184  }
185  }
186  Vec_PtrFree( vLeaves );
187  Vec_PtrFree( vNodes );
188  Abc_NtkCleanMarkA( pNtk );
189  return vRoots;
190 }
191 
192 /**Function*************************************************************
193 
194  Synopsis [Collect fanout reachable root nodes.]
195 
196  Description []
197 
198  SideEffects []
199 
200  SeeAlso []
201 
202 ***********************************************************************/
203 void Abc_NktMffcCollectFanout_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vFanouts )
204 {
205  Abc_Obj_t * pFanout;
206  int i;
207  if ( Abc_ObjIsCo(pObj) )
208  return;
209  if ( Abc_ObjFanoutNum(pObj) > 64 )
210  return;
211  if ( Abc_NodeIsTravIdCurrent(pObj) )
212  return;
213  Abc_NodeSetTravIdCurrent(pObj);
214  if ( pObj->fMarkA )
215  {
216  if ( pObj->vFanouts.nSize > 0 )
217  Vec_PtrPush( vFanouts, pObj );
218  return;
219  }
220  Abc_ObjForEachFanout( pObj, pFanout, i )
221  Abc_NktMffcCollectFanout_rec( pFanout, vFanouts );
222 }
223 
224 /**Function*************************************************************
225 
226  Synopsis [Collect fanout reachable root nodes.]
227 
228  Description []
229 
230  SideEffects []
231 
232  SeeAlso []
233 
234 ***********************************************************************/
235 void Abc_NktMffcCollectFanout( Abc_Obj_t ** pNodes, int nNodes, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vFanouts )
236 {
237  Abc_Obj_t * pFanin, * pFanout;
238  int i, k;
239  // dereference nodes
240  for ( i = 0; i < nNodes; i++ )
241  Abc_MffcDeref_rec( pNodes[i], NULL );
242  // collect fanouts
243  Vec_PtrClear( vFanouts );
244  pFanin = (Abc_Obj_t *)Vec_PtrEntry( vLeaves, 0 );
245  Abc_NtkIncrementTravId( pFanin->pNtk );
246  Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pFanin, i )
247  Abc_ObjForEachFanout( pFanin, pFanout, k )
248  Abc_NktMffcCollectFanout_rec( pFanout, vFanouts );
249  // reference nodes
250  for ( i = 0; i < nNodes; i++ )
251  Abc_MffcRef_rec( pNodes[i] );
252 }
253 
254 /**Function*************************************************************
255 
256  Synopsis [Grow one node.]
257 
258  Description []
259 
260  SideEffects []
261 
262  SeeAlso []
263 
264 ***********************************************************************/
265 Abc_Obj_t * Abc_NktMffcGrowOne( Abc_Ntk_t * pNtk, Abc_Obj_t ** ppObjs, int nObjs, Vec_Ptr_t * vNodes, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vFanouts )
266 {
267  Abc_Obj_t * pFanout, * pFanoutBest = NULL;
268  double CostBest = 0.0;
269  int i, k;
270  Abc_MffcCollectNodes( ppObjs, nObjs, vNodes );
271  Abc_MffcCollectLeaves( vNodes, vLeaves );
272  // collect fanouts of all fanins
273  Abc_NktMffcCollectFanout( ppObjs, nObjs, vLeaves, vFanouts );
274  // try different fanouts
275  Vec_PtrForEachEntry( Abc_Obj_t *, vFanouts, pFanout, i )
276  {
277  for ( k = 0; k < nObjs; k++ )
278  if ( pFanout == ppObjs[k] )
279  break;
280  if ( k < nObjs )
281  continue;
282  ppObjs[nObjs] = pFanout;
283  Abc_MffcCollectNodes( ppObjs, nObjs+1, vNodes );
284  Abc_MffcCollectLeaves( vNodes, vLeaves );
285  if ( pFanoutBest == NULL || CostBest < 1.0 * Vec_PtrSize(vNodes)/Vec_PtrSize(vLeaves) )
286  {
287  CostBest = 1.0 * Vec_PtrSize(vNodes)/Vec_PtrSize(vLeaves);
288  pFanoutBest = pFanout;
289  }
290  }
291  return pFanoutBest;
292 }
293 
294 /**Function*************************************************************
295 
296  Synopsis [Procedure to increase MFF size by pairing nodes.]
297 
298  Description [For each node in the array vRoots, find a matching node,
299  so that the ratio of nodes inside to the leaf nodes is maximized.]
300 
301  SideEffects []
302 
303  SeeAlso []
304 
305 ***********************************************************************/
306 Vec_Ptr_t * Abc_NktMffcGrowRoots( Abc_Ntk_t * pNtk, Vec_Ptr_t * vRoots )
307 {
308  Vec_Ptr_t * vRoots1, * vNodes, * vLeaves, * vFanouts;
309  Abc_Obj_t * pObj, * pRoot2, * pNodes[2];
310  int i;
311  Abc_NtkCleanMarkA( pNtk );
312  Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
313  pObj->fMarkA = 1;
314  vRoots1 = Vec_PtrAlloc( 100 );
315  vNodes = Vec_PtrAlloc( 100 );
316  vLeaves = Vec_PtrAlloc( 100 );
317  vFanouts = Vec_PtrAlloc( 100 );
318  Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
319  {
320  pNodes[0] = pObj;
321  pRoot2 = Abc_NktMffcGrowOne( pNtk, pNodes, 1, vNodes, vLeaves, vFanouts );
322  Vec_PtrPush( vRoots1, pRoot2 );
323  }
324  Vec_PtrFree( vNodes );
325  Vec_PtrFree( vLeaves );
326  Vec_PtrFree( vFanouts );
327  Abc_NtkCleanMarkA( pNtk );
328  return vRoots1;
329 }
330 
331 /**Function*************************************************************
332 
333  Synopsis [Procedure to increase MFF size by pairing nodes.]
334 
335  Description [For each node in the array vRoots, find a matching node,
336  so that the ratio of nodes inside to the leaf nodes is maximized.]
337 
338  SideEffects []
339 
340  SeeAlso []
341 
342 ***********************************************************************/
343 Vec_Ptr_t * Abc_NktMffcGrowRootsAgain( Abc_Ntk_t * pNtk, Vec_Ptr_t * vRoots, Vec_Ptr_t * vRoots1 )
344 {
345  Vec_Ptr_t * vRoots2, * vNodes, * vLeaves, * vFanouts;
346  Abc_Obj_t * pObj, * pRoot2, * ppObjs[3];
347  int i;
348  Abc_NtkCleanMarkA( pNtk );
349  Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
350  pObj->fMarkA = 1;
351  vRoots2 = Vec_PtrAlloc( 100 );
352  vNodes = Vec_PtrAlloc( 100 );
353  vLeaves = Vec_PtrAlloc( 100 );
354  vFanouts = Vec_PtrAlloc( 100 );
355  Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
356  {
357  ppObjs[0] = pObj;
358  ppObjs[1] = (Abc_Obj_t *)Vec_PtrEntry( vRoots1, i );
359  if ( ppObjs[1] == NULL )
360  {
361  Vec_PtrPush( vRoots2, NULL );
362  continue;
363  }
364  pRoot2 = Abc_NktMffcGrowOne( pNtk, ppObjs, 2, vNodes, vLeaves, vFanouts );
365  Vec_PtrPush( vRoots2, pRoot2 );
366  }
367  Vec_PtrFree( vNodes );
368  Vec_PtrFree( vLeaves );
369  Vec_PtrFree( vFanouts );
370  Abc_NtkCleanMarkA( pNtk );
371  assert( Vec_PtrSize(vRoots) == Vec_PtrSize(vRoots2) );
372  return vRoots2;
373 }
374 
375 /**Function*************************************************************
376 
377  Synopsis [Testbench.]
378 
379  Description []
380 
381  SideEffects []
382 
383  SeeAlso []
384 
385 ***********************************************************************/
386 void Abc_NktMffcPrint( char * pFileName, Abc_Obj_t ** pNodes, int nNodes, Vec_Ptr_t * vNodes, Vec_Ptr_t * vLeaves )
387 {
388  FILE * pFile;
389  Abc_Obj_t * pObj, * pFanin;
390  int i, k;
391  // convert the network
392  Abc_NtkToSop( pNodes[0]->pNtk, 0 );
393  // write the file
394  pFile = fopen( pFileName, "wb" );
395  fprintf( pFile, ".model %s_part\n", pNodes[0]->pNtk->pName );
396  fprintf( pFile, ".inputs" );
397  Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
398  fprintf( pFile, " %s", Abc_ObjName(pObj) );
399  fprintf( pFile, "\n" );
400  fprintf( pFile, ".outputs" );
401  for ( i = 0; i < nNodes; i++ )
402  fprintf( pFile, " %s", Abc_ObjName(pNodes[i]) );
403  fprintf( pFile, "\n" );
404  Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
405  {
406  fprintf( pFile, ".names" );
407  Abc_ObjForEachFanin( pObj, pFanin, k )
408  fprintf( pFile, " %s", Abc_ObjName(pFanin) );
409  fprintf( pFile, " %s", Abc_ObjName(pObj) );
410  fprintf( pFile, "\n%s", (char *)pObj->pData );
411  }
412  fprintf( pFile, ".end\n" );
413  fclose( pFile );
414 }
415 
416 /**Function*************************************************************
417 
418  Synopsis [Testbench.]
419 
420  Description []
421 
422  SideEffects []
423 
424  SeeAlso []
425 
426 ***********************************************************************/
427 void Abc_NktMffcPrintInt( char * pFileName, Abc_Ntk_t * pNtk, Vec_Int_t * vRoots, Vec_Int_t * vNodes, Vec_Int_t * vLeaves )
428 {
429  FILE * pFile;
430  Abc_Obj_t * pObj, * pFanin;
431  int i, k;
432  // convert the network
433  Abc_NtkToSop( pNtk, 0 );
434  // write the file
435  pFile = fopen( pFileName, "wb" );
436  fprintf( pFile, ".model %s_part\n", pNtk->pName );
437  fprintf( pFile, ".inputs" );
438  Abc_NtkForEachObjVec( vLeaves, pNtk, pObj, i )
439  fprintf( pFile, " %s", Abc_ObjName(pObj) );
440  fprintf( pFile, "\n" );
441  fprintf( pFile, ".outputs" );
442  Abc_NtkForEachObjVec( vRoots, pNtk, pObj, i )
443  fprintf( pFile, " %s", Abc_ObjName(pObj) );
444  fprintf( pFile, "\n" );
445  Abc_NtkForEachObjVec( vNodes, pNtk, pObj, i )
446  {
447  fprintf( pFile, ".names" );
448  Abc_ObjForEachFanin( pObj, pFanin, k )
449  fprintf( pFile, " %s", Abc_ObjName(pFanin) );
450  fprintf( pFile, " %s", Abc_ObjName(pObj) );
451  fprintf( pFile, "\n%s", (char *)pObj->pData );
452  }
453  fprintf( pFile, ".end\n" );
454  fclose( pFile );
455 }
456 
457 /**Function*************************************************************
458 
459  Synopsis [Testbench.]
460 
461  Description []
462 
463  SideEffects []
464 
465  SeeAlso []
466 
467 ***********************************************************************/
468 void Abc_NktMffcTest( Abc_Ntk_t * pNtk )
469 {
470  char pFileName[1000];
471  Vec_Ptr_t * vRoots, * vRoots1, * vRoots2, * vNodes, * vLeaves;
472  Abc_Obj_t * pNodes[3], * pObj;
473  int i, nNodes = 0, nNodes2 = 0;
474  vRoots = Abc_NktMffcMarkRoots( pNtk, 1 );
475  vRoots1 = Abc_NktMffcGrowRoots( pNtk, vRoots );
476  vRoots2 = Abc_NktMffcGrowRootsAgain( pNtk, vRoots, vRoots1 );
477  vNodes = Vec_PtrAlloc( 100 );
478  vLeaves = Vec_PtrAlloc( 100 );
479  Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
480  {
481  printf( "%6d : ", i );
482 
483  Abc_MffcCollectNodes( &pObj, 1, vNodes );
484  Abc_MffcCollectLeaves( vNodes, vLeaves );
485  nNodes += Vec_PtrSize(vNodes);
486  printf( "%6d ", Abc_ObjId(pObj) );
487  printf( "Vol =%3d ", Vec_PtrSize(vNodes) );
488  printf( "Cut =%3d ", Vec_PtrSize(vLeaves) );
489  if ( Vec_PtrSize(vLeaves) < 2 )
490  {
491  printf( "\n" );
492  continue;
493  }
494 
495  pNodes[0] = pObj;
496  pNodes[1] = (Abc_Obj_t *)Vec_PtrEntry( vRoots1, i );
497  pNodes[2] = (Abc_Obj_t *)Vec_PtrEntry( vRoots2, i );
498  if ( pNodes[1] == NULL || pNodes[2] == NULL )
499  {
500  printf( "\n" );
501  continue;
502  }
503  Abc_MffcCollectNodes( pNodes, 3, vNodes );
504  Abc_MffcCollectLeaves( vNodes, vLeaves );
505  nNodes2 += Vec_PtrSize(vNodes);
506  printf( "%6d ", Abc_ObjId(pNodes[1]) );
507  printf( "%6d ", Abc_ObjId(pNodes[2]) );
508  printf( "Vol =%3d ", Vec_PtrSize(vNodes) );
509  printf( "Cut =%3d ", Vec_PtrSize(vLeaves) );
510 
511  printf( "%4.2f ", 1.0 * Vec_PtrSize(vNodes)/Vec_PtrSize(vLeaves) );
512  printf( "\n" );
513 
514  // generate file
515  if ( Vec_PtrSize(vNodes) < 10 )
516  continue;
517  sprintf( pFileName, "%s_mffc%04d_%02d.blif", Abc_NtkName(pNtk), Abc_ObjId(pObj), Vec_PtrSize(vNodes) );
518  Abc_NktMffcPrint( pFileName, pNodes, 3, vNodes, vLeaves );
519  }
520  printf( "Total nodes = %d. Root nodes = %d. Mffc nodes = %d. Mffc nodes2 = %d.\n",
521  Abc_NtkNodeNum(pNtk), Vec_PtrSize(vRoots), nNodes, nNodes2 );
522  Vec_PtrFree( vNodes );
523  Vec_PtrFree( vLeaves );
524  Vec_PtrFree( vRoots );
525  Vec_PtrFree( vRoots1 );
526  Vec_PtrFree( vRoots2 );
527 }
528 
529 
530 
531 /**Function*************************************************************
532 
533  Synopsis [Create the network of supernodes.]
534 
535  Description []
536 
537  SideEffects []
538 
539  SeeAlso []
540 
541 ***********************************************************************/
542 void Abc_NktMffcTestSuper( Abc_Ntk_t * pNtk )
543 {
544  Vec_Ptr_t * vRoots, * vFanins, * vFanouts, * vNodes, * vLeaves;
545  Abc_Obj_t * pObj, * pFanin;
546  Vec_Int_t * vCounts, * vNumbers, * vSizes, * vMarks;
547  Vec_Int_t * vNode1, * vNode2;
548  int i, k, Entry, nSizes;
549  abctime clk = Abc_Clock();
550  vRoots = Abc_NktMffcMarkRoots( pNtk, 1 );
551  vFanins = Vec_PtrStart( Abc_NtkObjNumMax(pNtk) );
552  vFanouts = Vec_PtrStart( Abc_NtkObjNumMax(pNtk) );
553  vCounts = Vec_IntStart( Abc_NtkObjNumMax(pNtk) );
554  vNode1 = Vec_IntStart( Abc_NtkObjNumMax(pNtk) );
555  vNode2 = Vec_IntStart( Abc_NtkObjNumMax(pNtk) );
556  vSizes = Vec_IntStart( Abc_NtkObjNumMax(pNtk) );
557  vMarks = Vec_IntStart( Abc_NtkObjNumMax(pNtk) );
558 
559  // create fanins/fanouts
560  Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
561  {
562  Vec_PtrWriteEntry( vFanins, Abc_ObjId(pObj), Vec_IntAlloc(8) );
563  Vec_PtrWriteEntry( vFanouts, Abc_ObjId(pObj), Vec_IntAlloc(8) );
564  }
565  // add fanins/fanouts
566  vNodes = Vec_PtrAlloc( 100 );
567  vLeaves = Vec_PtrAlloc( 100 );
568  Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
569  {
570  Abc_MffcCollectNodes( &pObj, 1, vNodes );
571  Abc_MffcCollectLeaves( vNodes, vLeaves );
572  Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pFanin, k )
573  {
574  if ( !Abc_ObjIsNode(pFanin) )
575  continue;
576  Vec_IntPush( (Vec_Int_t *)Vec_PtrEntry(vFanins, Abc_ObjId(pObj)), Abc_ObjId(pFanin) );
577  Vec_IntPush( (Vec_Int_t *)Vec_PtrEntry(vFanouts, Abc_ObjId(pFanin)), Abc_ObjId(pObj) );
578  // count how many times each object is a fanin
579  Vec_IntAddToEntry( vCounts, Abc_ObjId(pFanin), 1 );
580  }
581  Vec_IntWriteEntry( vSizes, Abc_ObjId(pObj), Vec_PtrSize(vNodes) );
582  }
583 
584  Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
585  {
586  Abc_MffcCollectNodes( &pObj, 1, vNodes );
587  Abc_MffcCollectLeaves( vNodes, vLeaves );
588  Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pFanin, k )
589  {
590  if ( !Abc_ObjIsNode(pFanin) )
591  continue;
592  if ( Vec_IntEntry(vCounts, Abc_ObjId(pFanin)) != 2 )
593  continue;
594  if ( Vec_IntEntry(vNode1, Abc_ObjId(pFanin)) == 0 )
595  Vec_IntWriteEntry( vNode1, Abc_ObjId(pFanin), Abc_ObjId(pObj) );
596  else //if ( Vec_IntEntry(vNode2, Abc_ObjId(pFanin)) == 0 )
597  Vec_IntWriteEntry( vNode2, Abc_ObjId(pFanin), Abc_ObjId(pObj) );
598 
599  Vec_IntWriteEntry( vMarks, Abc_ObjId(pFanin), 1 );
600  Vec_IntWriteEntry( vMarks, Abc_ObjId(pObj), 1 );
601  }
602  }
603 
604  // count sizes
605  nSizes = 0;
606  Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
607  {
608  if ( Vec_IntEntry( vMarks, Abc_ObjId(pObj) ) )
609  nSizes += Vec_IntEntry( vSizes, Abc_ObjId(pObj) );
610  }
611  printf( "Included = %6d. Total = %6d. (%6.2f %%)\n",
612  nSizes, Abc_NtkNodeNum(pNtk), 100.0 * nSizes / Abc_NtkNodeNum(pNtk) );
613 
614 
615  Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
616  {
617  if ( Vec_IntEntry(vCounts, Abc_ObjId(pObj)) != 2 )
618  continue;
619  printf( "%d ", Vec_IntEntry( vSizes, Abc_ObjId(pObj) ) +
620  Vec_IntEntry( vSizes, Vec_IntEntry(vNode1, Abc_ObjId(pObj)) ) +
621  Vec_IntEntry( vSizes, Vec_IntEntry(vNode2, Abc_ObjId(pObj)) ) );
622  }
623  printf( "\n" );
624 
625  // print how many times they appear
626  vNumbers = Vec_IntStart( 32 );
627  Vec_IntForEachEntry( vCounts, Entry, i )
628  {
629 /*
630 if ( Entry == 2 )
631 {
632  pObj = Abc_NtkObj( pNtk, i );
633  Abc_MffcCollectNodes( &pObj, 1, vNodes );
634  Abc_MffcCollectLeaves( vNodes, vLeaves );
635  printf( "%d(%d) ", Vec_PtrSize(vNodes), Vec_PtrSize(vLeaves) );
636 }
637 */
638  if ( Entry == 0 )
639  continue;
640  if ( Entry <= 10 )
641  Vec_IntAddToEntry( vNumbers, Entry, 1 );
642  else if ( Entry <= 100 )
643  Vec_IntAddToEntry( vNumbers, 10 + Entry/10, 1 );
644  else if ( Entry < 1000 )
645  Vec_IntAddToEntry( vNumbers, 20 + Entry/100, 1 );
646  else
647  Vec_IntAddToEntry( vNumbers, 30, 1 );
648  }
649  for ( i = 1; i <= 10; i++ )
650  if ( Vec_IntEntry(vNumbers,i) )
651  printf( " n = %4d %6d\n", i, Vec_IntEntry(vNumbers,i) );
652  for ( i = 11; i <= 20; i++ )
653  if ( Vec_IntEntry(vNumbers,i) )
654  printf( "%4d < n <= %4d %6d\n", 10*(i-10), 10*(i-9), Vec_IntEntry(vNumbers,i) );
655  for ( i = 21; i < 30; i++ )
656  if ( Vec_IntEntry(vNumbers,i) )
657  printf( "%4d < n <= %4d %6d\n", 100*(i-20), 100*(i-19), Vec_IntEntry(vNumbers,i) );
658  if ( Vec_IntEntry(vNumbers,31) )
659  printf( " n > 1000 %6d\n", Vec_IntEntry(vNumbers,30) );
660  printf( "Total MFFCs = %d. ", Vec_PtrSize(vRoots) );
661  Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
662  Vec_IntFree( vNumbers );
663  Vec_PtrFree( vNodes );
664  Vec_PtrFree( vLeaves );
665 
666  // delete fanins/fanouts
667  Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
668  {
669  Vec_IntFree( (Vec_Int_t *)Vec_PtrEntry(vFanins, Abc_ObjId(pObj)) );
670  Vec_IntFree( (Vec_Int_t *)Vec_PtrEntry(vFanouts, Abc_ObjId(pObj)) );
671  }
672 
673  Vec_IntFree( vCounts );
674  Vec_PtrFree( vFanouts );
675  Vec_PtrFree( vFanins );
676  Vec_PtrFree( vRoots );
677 }
678 
679 
680 /**Function*************************************************************
681 
682  Synopsis [Collects the leaves and the roots of the window.]
683 
684  Description []
685 
686  SideEffects []
687 
688  SeeAlso []
689 
690 ***********************************************************************/
691 void Abc_NktMffCollectLeafRoot( Abc_Ntk_t * pNtk, Vec_Ptr_t * vNodes, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vRoots )
692 {
693  Abc_Obj_t * pObj, * pNext;
694  int i, k;
695  // mark
696  Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
697  pObj->fMarkA = 1;
698  // collect leaves
699  Vec_PtrClear( vLeaves );
700  Abc_NtkIncrementTravId( pNtk );
701  Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
702  Abc_ObjForEachFanin( pObj, pNext, k )
703  {
704  if ( pNext->fMarkA || Abc_NodeIsTravIdCurrent(pNext) )
705  continue;
706  Abc_NodeSetTravIdCurrent(pNext);
707  Vec_PtrPush( vLeaves, pNext );
708  }
709  // collect roots
710  Vec_PtrClear( vRoots );
711  Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
712  {
713  Abc_ObjForEachFanout( pObj, pNext, k )
714  if ( !pNext->fMarkA )
715  {
716  Vec_PtrPush( vRoots, pObj );
717  break;
718  }
719  }
720  // unmark
721  Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
722  pObj->fMarkA = 0;
723 }
724 
725 /**Function*************************************************************
726 
727  Synopsis [Collects the leaves and the roots of the window.]
728 
729  Description []
730 
731  SideEffects []
732 
733  SeeAlso []
734 
735 ***********************************************************************/
736 void Abc_NktMffCollectLeafRootInt( Abc_Ntk_t * pNtk, Vec_Int_t * vNodes, Vec_Int_t * vLeaves, Vec_Int_t * vRoots )
737 {
738  Abc_Obj_t * pObj, * pNext;
739  int i, k;
740  // mark
741  Abc_NtkForEachObjVec( vNodes, pNtk, pObj, i )
742  pObj->fMarkA = 1;
743  // collect leaves
744  Vec_IntClear( vLeaves );
745  Abc_NtkIncrementTravId( pNtk );
746  Abc_NtkForEachObjVec( vNodes, pNtk, pObj, i )
747  Abc_ObjForEachFanin( pObj, pNext, k )
748  {
749  if ( pNext->fMarkA || Abc_NodeIsTravIdCurrent(pNext) )
750  continue;
751  Abc_NodeSetTravIdCurrent(pNext);
752  Vec_IntPush( vLeaves, Abc_ObjId(pNext) );
753  }
754  // collect roots
755  if ( vRoots )
756  {
757  Vec_IntClear( vRoots );
758  Abc_NtkForEachObjVec( vNodes, pNtk, pObj, i )
759  {
760  Abc_ObjForEachFanout( pObj, pNext, k )
761  if ( !pNext->fMarkA )
762  {
763  Vec_IntPush( vRoots, Abc_ObjId(pObj) );
764  break;
765  }
766  }
767  }
768  // unmark
769  Abc_NtkForEachObjVec( vNodes, pNtk, pObj, i )
770  pObj->fMarkA = 0;
771 }
772 
773 
774 /**Function*************************************************************
775 
776  Synopsis [Create the network of supernodes.]
777 
778  Description []
779 
780  SideEffects []
781 
782  SeeAlso []
783 
784 ***********************************************************************/
785 void Abc_NktMffcTestIdeaOne( Abc_Ntk_t * pNtk, Abc_Obj_t * pObj )
786 {
787  Vec_Ptr_t * vNodes, * vLeaves, * vRoots, * vVolume;
788  Vec_Ptr_t * vLeaves2, * vRoots2, * vVolume2;
789  Abc_Obj_t * pNode, * pNodeBest = pObj;
790  double Cost, CostBest = 0.0;
791  int i, k;
792  vNodes = Vec_PtrAlloc( 100 );
793  vLeaves = Vec_PtrAlloc( 100 );
794  vRoots = Vec_PtrAlloc( 100 );
795  vVolume = Vec_PtrAlloc( 100 );
796  vLeaves2 = Vec_PtrAlloc( 100 );
797  vRoots2 = Vec_PtrAlloc( 100 );
798  vVolume2 = Vec_PtrAlloc( 100 );
799 printf( "\n" );
800  for ( i = 1; i <= 16; i++ )
801  {
802  Vec_PtrPush( vNodes, pNodeBest );
803  Abc_NktMffCollectLeafRoot( pNtk, vNodes, vLeaves, vRoots );
804  Abc_MffcCollectNodes( (Abc_Obj_t **)Vec_PtrArray(vRoots), Vec_PtrSize(vRoots), vVolume );
805 
806  printf( "%2d : Node =%6d (%2d%3d) Cost =%6.2f ", i, Abc_ObjId(pNodeBest),
807  Abc_ObjFaninNum(pNodeBest), Abc_ObjFanoutNum(pNodeBest), CostBest );
808  printf( "Leaf =%2d Root =%2d Vol =%2d\n", Vec_PtrSize(vLeaves), Vec_PtrSize(vRoots), Vec_PtrSize(vVolume) );
809 
810  // try including different nodes
811  pNodeBest = NULL;
812  Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pNode, k )
813  {
814  if ( !Abc_ObjIsNode(pNode) )
815  continue;
816  Vec_PtrPush( vNodes, pNode );
817  Abc_NktMffCollectLeafRoot( pNtk, vNodes, vLeaves2, vRoots2 );
818  Abc_MffcCollectNodes( (Abc_Obj_t **)Vec_PtrArray(vRoots2), Vec_PtrSize(vRoots2), vVolume2 );
819  Cost = 1.0 * Vec_PtrSize(vVolume2) / (Vec_PtrSize(vLeaves2) + 3 * Vec_PtrSize(vRoots2));
820  if ( pNodeBest == NULL || CostBest < Cost )
821  {
822  pNodeBest = pNode;
823  CostBest = Cost;
824  }
825  Vec_PtrPop( vNodes );
826  }
827  Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pNode, k )
828  {
829  if ( Vec_PtrFind(vNodes, pNode) >= 0 )
830  continue;
831  if ( !Abc_ObjIsNode(pNode) )
832  continue;
833  Vec_PtrPush( vNodes, pNode );
834  Abc_NktMffCollectLeafRoot( pNtk, vNodes, vLeaves2, vRoots2 );
835  Abc_MffcCollectNodes( (Abc_Obj_t **)Vec_PtrArray(vRoots2), Vec_PtrSize(vRoots2), vVolume2 );
836  Cost = 1.0 * Vec_PtrSize(vVolume2) / (Vec_PtrSize(vLeaves2) + 3 * Vec_PtrSize(vRoots2));
837  if ( pNodeBest == NULL || CostBest < Cost )
838  {
839  pNodeBest = pNode;
840  CostBest = Cost;
841  }
842  Vec_PtrPop( vNodes );
843  }
844  if ( pNodeBest == NULL )
845  break;
846  }
847 
848  Vec_PtrFree( vNodes );
849  Vec_PtrFree( vLeaves );
850  Vec_PtrFree( vRoots );
851  Vec_PtrFree( vVolume );
852  Vec_PtrFree( vLeaves2 );
853  Vec_PtrFree( vRoots2 );
854  Vec_PtrFree( vVolume2 );
855 }
856 
857 /**Function*************************************************************
858 
859  Synopsis [Create the network of supernodes.]
860 
861  Description []
862 
863  SideEffects []
864 
865  SeeAlso []
866 
867 ***********************************************************************/
868 void Abc_NktMffcTestIdea( Abc_Ntk_t * pNtk )
869 {
870  Abc_Obj_t * pObj;
871  int i;
872  Abc_NtkForEachNode( pNtk, pObj, i )
873  if ( Abc_ObjIsNode(pObj) && Abc_ObjId(pObj) % 100 == 0 )
874  Abc_NktMffcTestIdeaOne( pNtk, pObj );
875 }
876 
877 
878 
879 
880 
881 /**Function*************************************************************
882 
883  Synopsis [Creates MFFCs and their fanins/fanouts/volumes.]
884 
885  Description []
886 
887  SideEffects []
888 
889  SeeAlso []
890 
891 ***********************************************************************/
892 Vec_Ptr_t * Abc_NktMffcDerive( Abc_Ntk_t * pNtk, Vec_Ptr_t ** pvFanins, Vec_Ptr_t ** pvFanouts, Vec_Ptr_t ** pvVolumes )
893 {
894  Vec_Ptr_t * vRoots, * vFanins, * vFanouts, * vVolumes, * vNodes, * vLeaves;
895  Abc_Obj_t * pObj, * pFanin;
896  int i, k;
897  abctime clk = Abc_Clock();
898  // create roots
899  vRoots = Abc_NktMffcMarkRoots( pNtk, 0 );
900  // create fanins/fanouts/volumes
901  vFanins = Vec_PtrStart( Abc_NtkObjNumMax(pNtk) );
902  vFanouts = Vec_PtrStart( Abc_NtkObjNumMax(pNtk) );
903  vVolumes = Vec_PtrStart( Abc_NtkObjNumMax(pNtk) );
904  Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
905  {
906  Vec_PtrWriteEntry( vFanins, Abc_ObjId(pObj), Vec_IntAlloc(8) );
907  Vec_PtrWriteEntry( vFanouts, Abc_ObjId(pObj), Vec_IntAlloc(8) );
908  Vec_PtrWriteEntry( vVolumes, Abc_ObjId(pObj), Vec_IntAlloc(8) );
909  }
910  // add fanins/fanouts
911  vNodes = Vec_PtrAlloc( 100 );
912  vLeaves = Vec_PtrAlloc( 100 );
913  Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
914  {
915  if ( Abc_ObjIsCi(pObj) )
916  continue;
917  Abc_MffcCollectNodes( &pObj, 1, vNodes );
918  Abc_MffcCollectLeaves( vNodes, vLeaves );
919  Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pFanin, k )
920  {
921  Vec_IntPush( (Vec_Int_t *)Vec_PtrEntry(vFanins, Abc_ObjId(pObj)), Abc_ObjId(pFanin) );
922  Vec_IntPush( (Vec_Int_t *)Vec_PtrEntry(vFanouts, Abc_ObjId(pFanin)), Abc_ObjId(pObj) );
923  }
924  Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pFanin, k )
925  Vec_IntPush( (Vec_Int_t *)Vec_PtrEntry(vVolumes, Abc_ObjId(pObj)), Abc_ObjId(pFanin) );
926  }
927 
928  Vec_PtrFree( vNodes );
929  Vec_PtrFree( vLeaves );
930  // sort
931  Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
932  {
933  Vec_IntSort( (Vec_Int_t *)Vec_PtrEntry(vFanins, Abc_ObjId(pObj)), 0 );
934  Vec_IntSort( (Vec_Int_t *)Vec_PtrEntry(vFanouts, Abc_ObjId(pObj)), 0 );
935  }
936  // return
937  *pvFanins = vFanins;
938  *pvFanouts = vFanouts;
939  *pvVolumes = vVolumes;
940  return vRoots;
941 }
942 
943 /**Function*************************************************************
944 
945  Synopsis [Frees MFFCs and their fanins/fanouts.]
946 
947  Description []
948 
949  SideEffects []
950 
951  SeeAlso []
952 
953 ***********************************************************************/
954 void Abc_NktMffcFree( Vec_Ptr_t * vRoots, Vec_Ptr_t * vFanins, Vec_Ptr_t * vFanouts, Vec_Ptr_t * vVolumes )
955 {
956  Abc_Obj_t * pObj;
957  int i;
958  Vec_PtrForEachEntry( Abc_Obj_t *, vRoots, pObj, i )
959  {
960  Vec_IntFree( (Vec_Int_t *)Vec_PtrEntry(vFanins, Abc_ObjId(pObj)) );
961  Vec_IntFree( (Vec_Int_t *)Vec_PtrEntry(vFanouts, Abc_ObjId(pObj)) );
962  Vec_IntFree( (Vec_Int_t *)Vec_PtrEntry(vVolumes, Abc_ObjId(pObj)) );
963  }
964  Vec_PtrFree( vVolumes );
965  Vec_PtrFree( vFanouts );
966  Vec_PtrFree( vFanins );
967  Vec_PtrFree( vRoots );
968 }
969 
970 
971 /**Function*************************************************************
972 
973  Synopsis [Returns the cost of two supports.]
974 
975  Description []
976 
977  SideEffects []
978 
979  SeeAlso []
980 
981 ***********************************************************************/
982 double Abc_NktMffcCostTwo( Vec_Int_t * vSupp1, Vec_Int_t * vSupp2, int Volume, int Limit )
983 {
984  int nCommon = Vec_IntTwoCountCommon( vSupp1, vSupp2 );
985 //printf( "s1=%2d s2=%2d c=%2d v=%2d ", Vec_IntSize(vSupp1), Vec_IntSize(vSupp2), nCommon, Volume );
986  if ( Vec_IntSize(vSupp1) + Vec_IntSize(vSupp2) - nCommon > Limit )
987  return (double)-ABC_INFINITY;
988  return 0.6 * nCommon - 1.2 * Vec_IntSize(vSupp2) + 0.8 * Volume;
989 }
990 
991 /**Function*************************************************************
992 
993  Synopsis [Returns support of the group.]
994 
995  Description []
996 
997  SideEffects []
998 
999  SeeAlso []
1000 
1001 ***********************************************************************/
1002 Vec_Int_t * Abc_NktMffcSupport( Vec_Ptr_t * vThis, Vec_Ptr_t * vFanins )
1003 {
1004  Vec_Int_t * vIns, * vIns2, * vTemp;
1005  Abc_Obj_t * pObj;
1006  int i;
1007  vIns = Vec_IntAlloc( 100 );
1008  Vec_PtrForEachEntry( Abc_Obj_t *, vThis, pObj, i )
1009  {
1010  vIns2 = (Vec_Int_t *)Vec_PtrEntry( vFanins, Abc_ObjId(pObj) );
1011  vIns = Vec_IntTwoMerge( vTemp = vIns, vIns2 );
1012  Vec_IntFree( vTemp );
1013  }
1014  return vIns;
1015 }
1016 
1017 /**Function*************************************************************
1018 
1019  Synopsis [Returns the best merger for the cluster of given node (pPivot).]
1020 
1021  Description []
1022 
1023  SideEffects []
1024 
1025  SeeAlso []
1026 
1027 ***********************************************************************/
1028 Abc_Obj_t * Abc_NktMffcFindBest( Abc_Ntk_t * pNtk, Vec_Int_t * vMarks, Vec_Int_t * vIns, Vec_Ptr_t * vFanins, Vec_Ptr_t * vFanouts, Vec_Ptr_t * vVolumes, int Limit )
1029 {
1030  Vec_Int_t * vIns2, * vOuts, * vOuts2, * vTemp;
1031  Abc_Obj_t * pPivot2, * pObj, * pObjBest = NULL;
1032  double Cost, CostBest = (double)-ABC_INFINITY;
1033  int i, Volume;
1034  // collect the fanouts of the fanins
1035  vOuts = Vec_IntAlloc( 100 );
1036  Abc_NtkForEachObjVec( vIns, pNtk, pObj, i )
1037  {
1038  vOuts2 = (Vec_Int_t *)Vec_PtrEntry( vFanouts, Abc_ObjId(pObj) );
1039  if ( Vec_IntSize(vOuts2) > 16 )
1040  continue;
1041  vOuts = Vec_IntTwoMerge( vTemp = vOuts, vOuts2 );
1042  Vec_IntFree( vTemp );
1043  }
1044  // check the pairs
1045  Abc_NtkForEachObjVec( vOuts, pNtk, pPivot2, i )
1046  {
1047  if ( Vec_IntEntry(vMarks, Abc_ObjId(pPivot2)) == 0 )
1048  continue;
1049  vIns2 = (Vec_Int_t *)Vec_PtrEntry( vFanins, Abc_ObjId(pPivot2) );
1050  Volume = Vec_IntSize((Vec_Int_t *)Vec_PtrEntry(vVolumes, Abc_ObjId(pPivot2)));
1051  Cost = Abc_NktMffcCostTwo( vIns, vIns2, Volume, Limit );
1052 //printf( "%5d %2d\n", Abc_ObjId(pPivot2), Cost );
1053  if ( Cost == (double)-ABC_INFINITY )
1054  continue;
1055  if ( pObjBest == NULL || CostBest < Cost )
1056  {
1057  pObjBest = pPivot2;
1058  CostBest = Cost;
1059  }
1060  }
1061 //printf( "Choosing %d\n", pObjBest->Id );
1062  Vec_IntFree( vOuts );
1063  return pObjBest;
1064 }
1065 
1066 /**Function*************************************************************
1067 
1068  Synopsis [Processes one cluster.]
1069 
1070  Description []
1071 
1072  SideEffects []
1073 
1074  SeeAlso []
1075 
1076 ***********************************************************************/
1077 Vec_Int_t * Abc_NktMffcSaveOne( Vec_Ptr_t * vThis, Vec_Ptr_t * vVolumes )
1078 {
1079  Vec_Int_t * vVolume, * vResult;
1080  Abc_Obj_t * pObj;
1081  int i, k, Entry;
1082  vResult = Vec_IntAlloc( 100 );
1083  Vec_PtrForEachEntry( Abc_Obj_t *, vThis, pObj, i )
1084  {
1085  vVolume = (Vec_Int_t *)Vec_PtrEntry( vVolumes, Abc_ObjId(pObj) );
1086  Vec_IntForEachEntry( vVolume, Entry, k )
1087  Vec_IntPush( vResult, Entry );
1088  }
1089  return vResult;
1090 }
1091 
1092 /**Function*************************************************************
1093 
1094  Synopsis [Procedure used for sorting the nodes in decreasing order of levels.]
1095 
1096  Description []
1097 
1098  SideEffects []
1099 
1100  SeeAlso []
1101 
1102 ***********************************************************************/
1103 int Abc_NodeCompareVolumeDecrease( Abc_Obj_t ** pp1, Abc_Obj_t ** pp2 )
1104 {
1105  int Diff = Abc_ObjRegular(*pp1)->iTemp - Abc_ObjRegular(*pp2)->iTemp;
1106  if ( Diff > 0 )
1107  return -1;
1108  if ( Diff < 0 )
1109  return 1;
1110  Diff = Abc_ObjRegular(*pp1)->Id - Abc_ObjRegular(*pp2)->Id;
1111  if ( Diff > 0 )
1112  return -1;
1113  if ( Diff < 0 )
1114  return 1;
1115  return 0;
1116 }
1117 
1118 /**Function*************************************************************
1119 
1120  Synopsis [Create the network of supernodes.]
1121 
1122  Description [Returns array of interger arrays of IDs of nodes
1123  included in a disjoint structural decomposition of the network.]
1124 
1125  SideEffects []
1126 
1127  SeeAlso []
1128 
1129 ***********************************************************************/
1130 Vec_Ptr_t * Abc_NktMffcServer( Abc_Ntk_t * pNtk, int nInMax, int nOutMax )
1131 {
1132  Vec_Ptr_t * vResult, * vThis;
1133  Vec_Ptr_t * vPivots, * vFanins, * vFanouts, * vVolumes;
1134  Vec_Int_t * vLeaves, * vMarks;
1135  Abc_Obj_t * pObj, * pObj2;
1136  int i, k;
1137  assert( nOutMax >= 1 && nOutMax <= 32 );
1138  vResult = Vec_PtrAlloc( 100 );
1139  // create fanins/fanouts
1140  vPivots = Abc_NktMffcDerive( pNtk, &vFanins, &vFanouts, &vVolumes );
1141  // sort by their MFFC size
1142  Vec_PtrForEachEntry( Abc_Obj_t *, vPivots, pObj, i )
1143  pObj->iTemp = Vec_IntSize((Vec_Int_t *)Vec_PtrEntry(vVolumes, Abc_ObjId(pObj)));
1144  Vec_PtrSort( vPivots, (int (*)(void))Abc_NodeCompareVolumeDecrease );
1145  // create marks
1146  vMarks = Vec_IntStart( Abc_NtkObjNumMax(pNtk) );
1147  Vec_PtrForEachEntry( Abc_Obj_t *, vPivots, pObj, i )
1148  if ( Abc_ObjIsNode(pObj) && Vec_IntSize((Vec_Int_t *)Vec_PtrEntry(vVolumes, Abc_ObjId(pObj))) > 1 )
1149  Vec_IntWriteEntry( vMarks, Abc_ObjId(pObj), 1 );
1150  // consider nodes in the order of the marks
1151  vThis = Vec_PtrAlloc( 10 );
1152 // while ( 1 )
1153  Vec_PtrForEachEntry( Abc_Obj_t *, vPivots, pObj, i )
1154  {
1155 // pObj = Abc_NtkObj( pNtk, 589 );
1156  if ( Vec_IntEntry(vMarks, Abc_ObjId(pObj)) == 0 )
1157  continue;
1158  // start the set
1159  Vec_PtrClear( vThis );
1160  Vec_PtrPush( vThis, pObj );
1161  Vec_IntWriteEntry( vMarks, Abc_ObjId(pObj), 0 );
1162  // quit if exceeded the limit
1163  vLeaves = (Vec_Int_t *)Vec_PtrEntry( vFanins, Abc_ObjId(pObj) );
1164  if ( Vec_IntSize(vLeaves) > nInMax )
1165  {
1166  Vec_PtrPush( vResult, Abc_NktMffcSaveOne(vThis, vVolumes) );
1167  continue;
1168  }
1169  // try adding one node at a time
1170  for ( k = 1; k < nOutMax; k++ )
1171  {
1172  // quit if exceeded the limit
1173  vLeaves = Abc_NktMffcSupport( vThis, vFanins );
1174  assert( Vec_IntSize(vLeaves) <= nInMax );
1175  pObj2 = Abc_NktMffcFindBest( pNtk, vMarks, vLeaves, vFanins, vFanouts, vVolumes, nInMax );
1176  Vec_IntFree( vLeaves );
1177  // quit if there is no extension
1178  if ( pObj2 == NULL )
1179  break;
1180  Vec_PtrPush( vThis, pObj2 );
1181  Vec_IntWriteEntry( vMarks, Abc_ObjId(pObj2), 0 );
1182  }
1183  Vec_PtrPush( vResult, Abc_NktMffcSaveOne(vThis, vVolumes) );
1184 // break;
1185  }
1186  Vec_PtrFree( vThis );
1187  Vec_IntFree( vMarks );
1188  // delele fanins/outputs
1189  Abc_NktMffcFree( vPivots, vFanins, vFanouts, vVolumes );
1190  return vResult;
1191 }
1192 
1193 /**Function*************************************************************
1194 
1195  Synopsis [Testbench.]
1196 
1197  Description []
1198 
1199  SideEffects []
1200 
1201  SeeAlso []
1202 
1203 ***********************************************************************/
1204 void Abc_NktMffcServerTest( Abc_Ntk_t * pNtk )
1205 {
1206  char pFileName[1000];
1207  Vec_Ptr_t * vGlobs;
1208  Vec_Int_t * vGlob, * vLeaves, * vRoots;
1209  double Cost, CostAll = 0.0;
1210  int i, k, Entry, nNodes = 0;
1211  abctime clk = Abc_Clock();
1212  vGlobs = Abc_NktMffcServer( pNtk, 18, 3 );
1213  vLeaves = Vec_IntAlloc( 100 );
1214  vRoots = Vec_IntAlloc( 100 );
1215  Vec_PtrForEachEntry( Vec_Int_t *, vGlobs, vGlob, i )
1216  {
1217  nNodes += Vec_IntSize(vGlob);
1218  Abc_NktMffCollectLeafRootInt( pNtk, vGlob, vLeaves, vRoots );
1219  if ( Vec_IntSize(vGlob) <= Vec_IntSize(vRoots) )
1220  continue;
1221  Cost = 1.0 * Vec_IntSize(vGlob)/(Vec_IntSize(vLeaves) + Vec_IntSize(vRoots));
1222  CostAll += Cost;
1223  if ( Cost < 0.5 )
1224  continue;
1225 
1226  printf( "%6d : Root =%3d. Leaf =%3d. Node =%4d. ",
1227  i, Vec_IntSize(vRoots), Vec_IntSize(vLeaves), Vec_IntSize(vGlob) );
1228  printf( "Cost =%6.2f ", Cost );
1229  Vec_IntForEachEntry( vRoots, Entry, k )
1230  printf( "%d ", Entry );
1231  printf( "\n" );
1232 
1233  sprintf( pFileName, "%sc%04di%02dn%02d.blif", Abc_NtkName(pNtk), i, Vec_IntSize(vLeaves), Vec_IntSize(vGlob) );
1234  Abc_NktMffcPrintInt( pFileName, pNtk, vRoots, vGlob, vLeaves );
1235  }
1236  Vec_IntFree( vLeaves );
1237  Vec_IntFree( vRoots );
1238  Vec_PtrForEachEntry( Vec_Int_t *, vGlobs, vGlob, i )
1239  Vec_IntFree( vGlob );
1240  Vec_PtrFree( vGlobs );
1241  printf( "Total = %6d. Nodes = %6d. ", Abc_NtkNodeNum(pNtk), nNodes );
1242  printf( "Cost = %6.2f ", CostAll );
1243  Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
1244 }
1245 
1246 ABC_NAMESPACE_IMPL_END
1247 
1248 ////////////////////////////////////////////////////////////////////////
1249 /// END OF FILE ///
1250 ////////////////////////////////////////////////////////////////////////
1251 
1252 
Abc_Obj_t_::iTemp
int iTemp
Definition: abc.h:149
Abc_ObjId
static unsigned Abc_ObjId(Abc_Obj_t *pObj)
Definition: abc.h:329
Vec_PtrStart
static Vec_Ptr_t * Vec_PtrStart(int nSize)
Definition: vecPtr.h:106
Vec_Ptr_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
Abc_MffcCollectNodes
void Abc_MffcCollectNodes(Abc_Obj_t **pNodes, int nNodes, Vec_Ptr_t *vNodes)
Definition: abcMffc.c:95
Abc_NktMffcGrowOne
Abc_Obj_t * Abc_NktMffcGrowOne(Abc_Ntk_t *pNtk, Abc_Obj_t **ppObjs, int nObjs, Vec_Ptr_t *vNodes, Vec_Ptr_t *vLeaves, Vec_Ptr_t *vFanouts)
Definition: abcMffc.c:265
Abc_ObjIsCi
static int Abc_ObjIsCi(Abc_Obj_t *pObj)
Definition: abc.h:351
Abc_Obj_t_::fMarkA
unsigned fMarkA
Definition: abc.h:134
Abc_NtkObjNumMax
static int Abc_NtkObjNumMax(Abc_Ntk_t *pNtk)
Definition: abc.h:284
Vec_Int_t
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
Abc_Ntk_t_
Definition: abc.h:153
Abc_ObjFanoutNum
static int Abc_ObjFanoutNum(Abc_Obj_t *pObj)
Definition: abc.h:365
Abc_ObjFaninNum
static int Abc_ObjFaninNum(Abc_Obj_t *pObj)
Definition: abc.h:364
Abc_NktMffcPrint
void Abc_NktMffcPrint(char *pFileName, Abc_Obj_t **pNodes, int nNodes, Vec_Ptr_t *vNodes, Vec_Ptr_t *vLeaves)
Definition: abcMffc.c:386
Vec_PtrSort
static void Vec_PtrSort(Vec_Ptr_t *p, int(*Vec_PtrSortCompare)()) ___unused
Definition: vecPtr.h:851
Vec_PtrPush
static void Vec_PtrPush(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:606
Abc_NtkForEachCo
#define Abc_NtkForEachCo(pNtk, pCo, i)
Definition: abc.h:519
Abc_Clock
static abctime Abc_Clock()
Definition: abc_global.h:279
Vec_PtrSize
static int Vec_PtrSize(Vec_Ptr_t *p)
Definition: vecPtr.h:295
Vec_PtrPop
static void * Vec_PtrPop(Vec_Ptr_t *p)
Definition: vecPtr.h:677
Vec_IntSort
static void Vec_IntSort(Vec_Int_t *p, int fReverse)
Definition: vecInt.h:1293
Vec_IntTwoCountCommon
static int Vec_IntTwoCountCommon(Vec_Int_t *vArr1, Vec_Int_t *vArr2)
Definition: vecInt.h:1528
Abc_ObjFanin0
static Abc_Obj_t * Abc_ObjFanin0(Abc_Obj_t *pObj)
Definition: abc.h:373
Vec_PtrFind
static int Vec_PtrFind(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:694
Abc_ObjIsCo
static int Abc_ObjIsCo(Abc_Obj_t *pObj)
Definition: abc.h:352
Abc_NktMffcPrintInt
void Abc_NktMffcPrintInt(char *pFileName, Abc_Ntk_t *pNtk, Vec_Int_t *vRoots, Vec_Int_t *vNodes, Vec_Int_t *vLeaves)
Definition: abcMffc.c:427
Abc_NktMffcCollectFanout_rec
void Abc_NktMffcCollectFanout_rec(Abc_Obj_t *pObj, Vec_Ptr_t *vFanouts)
Definition: abcMffc.c:203
Abc_Obj_t_
Definition: abc.h:128
Abc_PrintTime
static void Abc_PrintTime(int level, const char *pStr, abctime time)
Definition: abc_global.h:367
Vec_IntWriteEntry
static void Vec_IntWriteEntry(Vec_Int_t *p, int i, int Entry)
Definition: bblif.c:285
Abc_ObjIsNode
static int Abc_ObjIsNode(Abc_Obj_t *pObj)
Definition: abc.h:355
Abc_NtkNodeNum
static int Abc_NtkNodeNum(Abc_Ntk_t *pNtk)
Definition: abc.h:293
Abc_NtkCleanMarkA
ABC_DLL void Abc_NtkCleanMarkA(Abc_Ntk_t *pNtk)
Definition: abcUtil.c:663
Vec_IntStart
static Vec_Int_t * Vec_IntStart(int nSize)
Definition: bblif.c:172
Abc_NktMffcSaveOne
Vec_Int_t * Abc_NktMffcSaveOne(Vec_Ptr_t *vThis, Vec_Ptr_t *vVolumes)
Definition: abcMffc.c:1077
Abc_NktMffcTest
void Abc_NktMffcTest(Abc_Ntk_t *pNtk)
Definition: abcMffc.c:468
Vec_IntAlloc
static Vec_Int_t * Vec_IntAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: bblif.c:149
Abc_NktMffcTestIdeaOne
void Abc_NktMffcTestIdeaOne(Abc_Ntk_t *pNtk, Abc_Obj_t *pObj)
Definition: abcMffc.c:785
Abc_NtkToSop
ABC_DLL int Abc_NtkToSop(Abc_Ntk_t *pNtk, int fDirect)
Definition: abcFunc.c:1124
Vec_IntAddToEntry
static void Vec_IntAddToEntry(Vec_Int_t *p, int i, int Addition)
Definition: bblif.c:302
Abc_NtkForEachObjVec
#define Abc_NtkForEachObjVec(vIds, pNtk, pObj, i)
Definition: abc.h:452
Abc_NktMffcGrowRootsAgain
Vec_Ptr_t * Abc_NktMffcGrowRootsAgain(Abc_Ntk_t *pNtk, Vec_Ptr_t *vRoots, Vec_Ptr_t *vRoots1)
Definition: abcMffc.c:343
Abc_NktMffcMarkRoots
Vec_Ptr_t * Abc_NktMffcMarkRoots(Abc_Ntk_t *pNtk, int fSkipPis)
Definition: abcMffc.c:149
Vec_IntEntry
static int Vec_IntEntry(Vec_Int_t *p, int i)
Definition: bblif.c:268
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
if
if(last==0)
Definition: sparse_int.h:34
Abc_NktMffcCollectFanout
void Abc_NktMffcCollectFanout(Abc_Obj_t **pNodes, int nNodes, Vec_Ptr_t *vLeaves, Vec_Ptr_t *vFanouts)
Definition: abcMffc.c:235
Vec_IntPush
static void Vec_IntPush(Vec_Int_t *p, int Entry)
Definition: bblif.c:468
sprintf
char * sprintf()
Vec_IntTwoMerge
static Vec_Int_t * Vec_IntTwoMerge(Vec_Int_t *vArr1, Vec_Int_t *vArr2)
Definition: vecInt.h:1684
Abc_NktMffcTestSuper
void Abc_NktMffcTestSuper(Abc_Ntk_t *pNtk)
Definition: abcMffc.c:542
Abc_MffcCollectLeaves
void Abc_MffcCollectLeaves(Vec_Ptr_t *vNodes, Vec_Ptr_t *vLeaves)
Definition: abcMffc.c:116
Vec_PtrWriteEntry
static void Vec_PtrWriteEntry(Vec_Ptr_t *p, int i, void *Entry)
Definition: vecPtr.h:396
Abc_NktMffcTestIdea
void Abc_NktMffcTestIdea(Abc_Ntk_t *pNtk)
Definition: abcMffc.c:868
Abc_NtkForEachNode
#define Abc_NtkForEachNode(pNtk, pNode, i)
Definition: abc.h:461
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
Vec_PtrEntry
static void * Vec_PtrEntry(Vec_Ptr_t *p, int i)
Definition: vecPtr.h:362
Abc_MffcDeref_rec
ABC_NAMESPACE_IMPL_START void Abc_MffcDeref_rec(Abc_Obj_t *pNode, Vec_Ptr_t *vNodes)
DECLARATIONS ///.
Definition: abcMffc.c:44
Abc_NodeIsTravIdCurrent
static int Abc_NodeIsTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:411
Abc_ObjRegular
static Abc_Obj_t * Abc_ObjRegular(Abc_Obj_t *p)
Definition: abc.h:323
Abc_Obj_t_::pNtk
Abc_Ntk_t * pNtk
Definition: abc.h:130
Abc_NktMffcDerive
Vec_Ptr_t * Abc_NktMffcDerive(Abc_Ntk_t *pNtk, Vec_Ptr_t **pvFanins, Vec_Ptr_t **pvFanouts, Vec_Ptr_t **pvVolumes)
Definition: abcMffc.c:892
Vec_IntSize
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
Abc_ObjForEachFanout
#define Abc_ObjForEachFanout(pObj, pFanout, i)
Definition: abc.h:526
Abc_NtkName
static char * Abc_NtkName(Abc_Ntk_t *pNtk)
Definition: abc.h:270
Vec_PtrAlloc
static Vec_Ptr_t * Vec_PtrAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecPtr.h:83
Abc_ObjForEachFanin
#define Abc_ObjForEachFanin(pObj, pFanin, i)
Definition: abc.h:524
Abc_NktMffcServer
Vec_Ptr_t * Abc_NktMffcServer(Abc_Ntk_t *pNtk, int nInMax, int nOutMax)
Definition: abcMffc.c:1130
Abc_Obj_t_::Id
int Id
Definition: abc.h:132
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_NktMffcCostTwo
double Abc_NktMffcCostTwo(Vec_Int_t *vSupp1, Vec_Int_t *vSupp2, int Volume, int Limit)
Definition: abcMffc.c:982
ABC_INFINITY
#define ABC_INFINITY
MACRO DEFINITIONS ///.
Definition: abc_global.h:216
assert
#define assert(ex)
Definition: util_old.h:213
Vec_PtrClear
static void Vec_PtrClear(Vec_Ptr_t *p)
Definition: vecPtr.h:545
Abc_NktMffcSupport
Vec_Int_t * Abc_NktMffcSupport(Vec_Ptr_t *vThis, Vec_Ptr_t *vFanins)
Definition: abcMffc.c:1002
Abc_Obj_t_::pData
void * pData
Definition: abc.h:145
Vec_IntFree
static void Vec_IntFree(Vec_Int_t *p)
Definition: bblif.c:235
Vec_PtrForEachEntry
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
Vec_IntClear
static void Vec_IntClear(Vec_Int_t *p)
Definition: bblif.c:452
Abc_MffcRef_rec
void Abc_MffcRef_rec(Abc_Obj_t *pNode)
Definition: abcMffc.c:71
abctime
ABC_INT64_T abctime
Definition: abc_global.h:278
Abc_NktMffcFree
void Abc_NktMffcFree(Vec_Ptr_t *vRoots, Vec_Ptr_t *vFanins, Vec_Ptr_t *vFanouts, Vec_Ptr_t *vVolumes)
Definition: abcMffc.c:954
Vec_IntForEachEntry
#define Vec_IntForEachEntry(vVec, Entry, i)
MACRO DEFINITIONS ///.
Definition: vecInt.h:54
Vec_PtrArray
static void ** Vec_PtrArray(Vec_Ptr_t *p)
Definition: vecPtr.h:279
Abc_NodeCompareVolumeDecrease
int Abc_NodeCompareVolumeDecrease(Abc_Obj_t **pp1, Abc_Obj_t **pp2)
Definition: abcMffc.c:1103
Abc_Ntk_t_::pName
char * pName
Definition: abc.h:158
Abc_NktMffcServerTest
void Abc_NktMffcServerTest(Abc_Ntk_t *pNtk)
Definition: abcMffc.c:1204
Abc_NktMffcFindBest
Abc_Obj_t * Abc_NktMffcFindBest(Abc_Ntk_t *pNtk, Vec_Int_t *vMarks, Vec_Int_t *vIns, Vec_Ptr_t *vFanins, Vec_Ptr_t *vFanouts, Vec_Ptr_t *vVolumes, int Limit)
Definition: abcMffc.c:1028
Abc_NktMffCollectLeafRoot
void Abc_NktMffCollectLeafRoot(Abc_Ntk_t *pNtk, Vec_Ptr_t *vNodes, Vec_Ptr_t *vLeaves, Vec_Ptr_t *vRoots)
Definition: abcMffc.c:691
Abc_NodeSetTravIdCurrent
static void Abc_NodeSetTravIdCurrent(Abc_Obj_t *p)
Definition: abc.h:409
Abc_NktMffcGrowRoots
Vec_Ptr_t * Abc_NktMffcGrowRoots(Abc_Ntk_t *pNtk, Vec_Ptr_t *vRoots)
Definition: abcMffc.c:306
Vec_PtrFree
static void Vec_PtrFree(Vec_Ptr_t *p)
Definition: vecPtr.h:223
Abc_NktMffCollectLeafRootInt
void Abc_NktMffCollectLeafRootInt(Abc_Ntk_t *pNtk, Vec_Int_t *vNodes, Vec_Int_t *vLeaves, Vec_Int_t *vRoots)
Definition: abcMffc.c:736