abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
nwkMerge.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [nwkMerge.c]
4 
5  SystemName [ABC: Logic synthesis and verification system.]
6 
7  PackageName [Netlist representation.]
8 
9  Synopsis [LUT merging algorithm.]
10 
11  Author [Alan Mishchenko]
12 
13  Affiliation [UC Berkeley]
14 
15  Date [Ver. 1.0. Started - June 20, 2005.]
16 
17  Revision [$Id: nwkMerge.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include "nwk.h"
22 #include "nwkMerge.h"
23 
24 ABC_NAMESPACE_IMPL_START
25 
26 
27 ////////////////////////////////////////////////////////////////////////
28 /// DECLARATIONS ///
29 ////////////////////////////////////////////////////////////////////////
30 
31 ////////////////////////////////////////////////////////////////////////
32 /// FUNCTION DEFINITIONS ///
33 ////////////////////////////////////////////////////////////////////////
34 
35 /**Function*************************************************************
36 
37  Synopsis [Allocates the graph.]
38 
39  Description []
40 
41  SideEffects []
42 
43  SeeAlso []
44 
45 ***********************************************************************/
46 Nwk_Grf_t * Nwk_ManGraphAlloc( int nVertsMax )
47 {
48  Nwk_Grf_t * p;
49  p = ABC_ALLOC( Nwk_Grf_t, 1 );
50  memset( p, 0, sizeof(Nwk_Grf_t) );
51  p->nVertsMax = nVertsMax;
52  p->nEdgeHash = Abc_PrimeCudd( 3 * nVertsMax );
53  p->pEdgeHash = ABC_CALLOC( Nwk_Edg_t *, p->nEdgeHash );
54  p->pMemEdges = Aig_MmFixedStart( sizeof(Nwk_Edg_t), p->nEdgeHash );
55  p->vPairs = Vec_IntAlloc( 1000 );
56  return p;
57 }
58 
59 /**Function*************************************************************
60 
61  Synopsis [Deallocates the graph.]
62 
63  Description []
64 
65  SideEffects []
66 
67  SeeAlso []
68 
69 ***********************************************************************/
70 void Nwk_ManGraphFree( Nwk_Grf_t * p )
71 {
72  if ( p->vPairs ) Vec_IntFree( p->vPairs );
73  if ( p->pMemEdges ) Aig_MmFixedStop( p->pMemEdges, 0 );
74  if ( p->pMemVerts ) Aig_MmFlexStop( p->pMemVerts, 0 );
75  ABC_FREE( p->pVerts );
76  ABC_FREE( p->pEdgeHash );
77  ABC_FREE( p->pMapLut2Id );
78  ABC_FREE( p->pMapId2Lut );
79  ABC_FREE( p );
80 }
81 
82 /**Function*************************************************************
83 
84  Synopsis [Prepares the graph for solving the problem.]
85 
86  Description []
87 
88  SideEffects []
89 
90  SeeAlso []
91 
92 ***********************************************************************/
93 void Nwk_ManGraphReportMemoryUsage( Nwk_Grf_t * p )
94 {
95  p->nMemBytes1 =
96  sizeof(Nwk_Grf_t) +
97  sizeof(void *) * p->nEdgeHash +
98  sizeof(int) * (p->nObjs + p->nVertsMax) +
99  sizeof(Nwk_Edg_t) * p->nEdges;
100  p->nMemBytes2 =
101  sizeof(Nwk_Vrt_t) * p->nVerts +
102  sizeof(int) * 2 * p->nEdges;
103  printf( "Memory usage stats: Preprocessing = %.2f MB. Solving = %.2f MB.\n",
104  1.0 * p->nMemBytes1 / (1<<20), 1.0 * p->nMemBytes2 / (1<<20) );
105 }
106 
107 
108 /**Function*************************************************************
109 
110  Synopsis [Finds or adds the edge to the graph.]
111 
112  Description []
113 
114  SideEffects []
115 
116  SeeAlso []
117 
118 ***********************************************************************/
119 void Nwk_ManGraphHashEdge( Nwk_Grf_t * p, int iLut1, int iLut2 )
120 {
121  Nwk_Edg_t * pEntry;
122  unsigned Key;
123  if ( iLut1 == iLut2 )
124  return;
125  if ( iLut1 > iLut2 )
126  {
127  Key = iLut1;
128  iLut1 = iLut2;
129  iLut2 = Key;
130  }
131  assert( iLut1 < iLut2 );
132  if ( p->nObjs < iLut2 )
133  p->nObjs = iLut2;
134  Key = (unsigned)(741457 * iLut1 + 4256249 * iLut2) % p->nEdgeHash;
135  for ( pEntry = p->pEdgeHash[Key]; pEntry; pEntry = pEntry->pNext )
136  if ( pEntry->iNode1 == iLut1 && pEntry->iNode2 == iLut2 )
137  return;
138  pEntry = (Nwk_Edg_t *)Aig_MmFixedEntryFetch( p->pMemEdges );
139  pEntry->iNode1 = iLut1;
140  pEntry->iNode2 = iLut2;
141  pEntry->pNext = p->pEdgeHash[Key];
142  p->pEdgeHash[Key] = pEntry;
143  p->nEdges++;
144 }
145 
146 /**Function*************************************************************
147 
148  Synopsis [Adds one entry to the list.]
149 
150  Description []
151 
152  SideEffects []
153 
154  SeeAlso []
155 
156 ***********************************************************************/
157 static inline void Nwk_ManGraphListAdd( Nwk_Grf_t * p, int * pList, Nwk_Vrt_t * pVertex )
158 {
159  if ( *pList )
160  {
161  Nwk_Vrt_t * pHead;
162  pHead = p->pVerts[*pList];
163  pVertex->iPrev = 0;
164  pVertex->iNext = pHead->Id;
165  pHead->iPrev = pVertex->Id;
166  }
167  *pList = pVertex->Id;
168 }
169 
170 /**Function*************************************************************
171 
172  Synopsis [Deletes one entry from the list.]
173 
174  Description []
175 
176  SideEffects []
177 
178  SeeAlso []
179 
180 ***********************************************************************/
181 static inline void Nwk_ManGraphListDelete( Nwk_Grf_t * p, int * pList, Nwk_Vrt_t * pVertex )
182 {
183  assert( *pList );
184  if ( pVertex->iPrev )
185  {
186 // assert( p->pVerts[pVertex->iPrev]->iNext == pVertex->Id );
187  p->pVerts[pVertex->iPrev]->iNext = pVertex->iNext;
188  }
189  if ( pVertex->iNext )
190  {
191 // assert( p->pVerts[pVertex->iNext]->iPrev == pVertex->Id );
192  p->pVerts[pVertex->iNext]->iPrev = pVertex->iPrev;
193  }
194  if ( *pList == pVertex->Id )
195  *pList = pVertex->iNext;
196  pVertex->iPrev = pVertex->iNext = 0;
197 }
198 
199 /**Function*************************************************************
200 
201  Synopsis [Inserts the edge into one of the linked lists.]
202 
203  Description []
204 
205  SideEffects []
206 
207  SeeAlso []
208 
209 ***********************************************************************/
210 static inline void Nwk_ManGraphListInsert( Nwk_Grf_t * p, Nwk_Vrt_t * pVertex )
211 {
212  Nwk_Vrt_t * pNext;
213  assert( pVertex->nEdges > 0 );
214 
215  if ( pVertex->nEdges == 1 )
216  {
217  pNext = p->pVerts[ pVertex->pEdges[0] ];
218  if ( pNext->nEdges >= NWK_MAX_LIST )
219  Nwk_ManGraphListAdd( p, p->pLists1 + NWK_MAX_LIST, pVertex );
220  else
221  Nwk_ManGraphListAdd( p, p->pLists1 + pNext->nEdges, pVertex );
222  }
223  else
224  {
225  if ( pVertex->nEdges >= NWK_MAX_LIST )
226  Nwk_ManGraphListAdd( p, p->pLists2 + NWK_MAX_LIST, pVertex );
227  else
228  Nwk_ManGraphListAdd( p, p->pLists2 + pVertex->nEdges, pVertex );
229  }
230 }
231 
232 /**Function*************************************************************
233 
234  Synopsis [Extracts the edge from one of the linked lists.]
235 
236  Description []
237 
238  SideEffects []
239 
240  SeeAlso []
241 
242 ***********************************************************************/
243 static inline void Nwk_ManGraphListExtract( Nwk_Grf_t * p, Nwk_Vrt_t * pVertex )
244 {
245  Nwk_Vrt_t * pNext;
246  assert( pVertex->nEdges > 0 );
247 
248  if ( pVertex->nEdges == 1 )
249  {
250  pNext = p->pVerts[ pVertex->pEdges[0] ];
251  if ( pNext->nEdges >= NWK_MAX_LIST )
252  Nwk_ManGraphListDelete( p, p->pLists1 + NWK_MAX_LIST, pVertex );
253  else
254  Nwk_ManGraphListDelete( p, p->pLists1 + pNext->nEdges, pVertex );
255  }
256  else
257  {
258  if ( pVertex->nEdges >= NWK_MAX_LIST )
259  Nwk_ManGraphListDelete( p, p->pLists2 + NWK_MAX_LIST, pVertex );
260  else
261  Nwk_ManGraphListDelete( p, p->pLists2 + pVertex->nEdges, pVertex );
262  }
263 }
264 
265 /**Function*************************************************************
266 
267  Synopsis [Prepares the graph for solving the problem.]
268 
269  Description []
270 
271  SideEffects []
272 
273  SeeAlso []
274 
275 ***********************************************************************/
276 void Nwk_ManGraphPrepare( Nwk_Grf_t * p )
277 {
278  Nwk_Edg_t * pEntry;
279  Nwk_Vrt_t * pVertex;
280  int * pnEdges, nBytes, i;
281  // allocate memory for the present objects
282  p->pMapLut2Id = ABC_ALLOC( int, p->nObjs+1 );
283  p->pMapId2Lut = ABC_ALLOC( int, p->nVertsMax+1 );
284  memset( p->pMapLut2Id, 0xff, sizeof(int) * (p->nObjs+1) );
285  memset( p->pMapId2Lut, 0xff, sizeof(int) * (p->nVertsMax+1) );
286  // mark present objects
287  Nwk_GraphForEachEdge( p, pEntry, i )
288  {
289  assert( pEntry->iNode1 <= p->nObjs );
290  assert( pEntry->iNode2 <= p->nObjs );
291  p->pMapLut2Id[ pEntry->iNode1 ] = 0;
292  p->pMapLut2Id[ pEntry->iNode2 ] = 0;
293  }
294  // map objects
295  p->nVerts = 0;
296  for ( i = 0; i <= p->nObjs; i++ )
297  {
298  if ( p->pMapLut2Id[i] == 0 )
299  {
300  p->pMapLut2Id[i] = ++p->nVerts;
301  p->pMapId2Lut[p->nVerts] = i;
302  }
303  }
304  // count the edges and mark present objects
305  pnEdges = ABC_CALLOC( int, p->nVerts+1 );
306  Nwk_GraphForEachEdge( p, pEntry, i )
307  {
308  // translate into vertices
309  assert( pEntry->iNode1 <= p->nObjs );
310  assert( pEntry->iNode2 <= p->nObjs );
311  pEntry->iNode1 = p->pMapLut2Id[pEntry->iNode1];
312  pEntry->iNode2 = p->pMapLut2Id[pEntry->iNode2];
313  // count the edges
314  assert( pEntry->iNode1 <= p->nVerts );
315  assert( pEntry->iNode2 <= p->nVerts );
316  pnEdges[pEntry->iNode1]++;
317  pnEdges[pEntry->iNode2]++;
318  }
319  // allocate the real graph
320  p->pMemVerts = Aig_MmFlexStart();
321  p->pVerts = ABC_ALLOC( Nwk_Vrt_t *, p->nVerts + 1 );
322  p->pVerts[0] = NULL;
323  for ( i = 1; i <= p->nVerts; i++ )
324  {
325  assert( pnEdges[i] > 0 );
326  nBytes = sizeof(Nwk_Vrt_t) + sizeof(int) * pnEdges[i];
327  p->pVerts[i] = (Nwk_Vrt_t *)Aig_MmFlexEntryFetch( p->pMemVerts, nBytes );
328  memset( p->pVerts[i], 0, nBytes );
329  p->pVerts[i]->Id = i;
330  }
331  // add edges to the real graph
332  Nwk_GraphForEachEdge( p, pEntry, i )
333  {
334  pVertex = p->pVerts[pEntry->iNode1];
335  pVertex->pEdges[ pVertex->nEdges++ ] = pEntry->iNode2;
336  pVertex = p->pVerts[pEntry->iNode2];
337  pVertex->pEdges[ pVertex->nEdges++ ] = pEntry->iNode1;
338  }
339  // put vertices into the data structure
340  for ( i = 1; i <= p->nVerts; i++ )
341  {
342  assert( p->pVerts[i]->nEdges == pnEdges[i] );
343  Nwk_ManGraphListInsert( p, p->pVerts[i] );
344  }
345  // clean up
346  Aig_MmFixedStop( p->pMemEdges, 0 ); p->pMemEdges = NULL;
347  ABC_FREE( p->pEdgeHash );
348 // p->nEdgeHash = 0;
349  ABC_FREE( pnEdges );
350 }
351 
352 /**Function*************************************************************
353 
354  Synopsis [Sort pairs by the first vertex in the topological order.]
355 
356  Description []
357 
358  SideEffects []
359 
360  SeeAlso []
361 
362 ***********************************************************************/
363 void Nwk_ManGraphSortPairs( Nwk_Grf_t * p )
364 {
365  int nSize = Vec_IntSize(p->vPairs);
366  int * pIdToPair, i;
367  // allocate storage
368  pIdToPair = ABC_ALLOC( int, p->nObjs+1 );
369  for ( i = 0; i <= p->nObjs; i++ )
370  pIdToPair[i] = -1;
371  // create mapping
372  for ( i = 0; i < p->vPairs->nSize; i += 2 )
373  {
374  assert( pIdToPair[ p->vPairs->pArray[i] ] == -1 );
375  pIdToPair[ p->vPairs->pArray[i] ] = p->vPairs->pArray[i+1];
376  }
377  // recreate pairs
378  Vec_IntClear( p->vPairs );
379  for ( i = 0; i <= p->nObjs; i++ )
380  if ( pIdToPair[i] >= 0 )
381  {
382  assert( i < pIdToPair[i] );
383  Vec_IntPush( p->vPairs, i );
384  Vec_IntPush( p->vPairs, pIdToPair[i] );
385  }
386  assert( nSize == Vec_IntSize(p->vPairs) );
387  ABC_FREE( pIdToPair );
388 }
389 
390 
391 /**Function*************************************************************
392 
393  Synopsis [Updates the problem after pulling out one edge.]
394 
395  Description []
396 
397  SideEffects []
398 
399  SeeAlso []
400 
401 ***********************************************************************/
402 void Nwk_ManGraphCheckLists( Nwk_Grf_t * p )
403 {
404  Nwk_Vrt_t * pVertex, * pNext;
405  int i, j;
406  assert( p->pLists1[0] == 0 );
407  for ( i = 1; i <= NWK_MAX_LIST; i++ )
408  if ( p->pLists1[i] )
409  {
410  pVertex = p->pVerts[ p->pLists1[i] ];
411  assert( pVertex->nEdges == 1 );
412  pNext = p->pVerts[ pVertex->pEdges[0] ];
413  assert( pNext->nEdges == i || pNext->nEdges > NWK_MAX_LIST );
414  }
415  // find the next vertext to extract
416  assert( p->pLists2[0] == 0 );
417  assert( p->pLists2[1] == 0 );
418  for ( j = 2; j <= NWK_MAX_LIST; j++ )
419  if ( p->pLists2[j] )
420  {
421  pVertex = p->pVerts[ p->pLists2[j] ];
422  assert( pVertex->nEdges == j || pVertex->nEdges > NWK_MAX_LIST );
423  }
424 }
425 
426 /**Function*************************************************************
427 
428  Synopsis [Extracts the edge from one of the linked lists.]
429 
430  Description []
431 
432  SideEffects []
433 
434  SeeAlso []
435 
436 ***********************************************************************/
437 static inline void Nwk_ManGraphVertexRemoveEdge( Nwk_Vrt_t * pThis, Nwk_Vrt_t * pNext )
438 {
439  int k;
440  for ( k = 0; k < pThis->nEdges; k++ )
441  if ( pThis->pEdges[k] == pNext->Id )
442  break;
443  assert( k < pThis->nEdges );
444  pThis->nEdges--;
445  for ( ; k < pThis->nEdges; k++ )
446  pThis->pEdges[k] = pThis->pEdges[k+1];
447 }
448 
449 /**Function*************************************************************
450 
451  Synopsis [Updates the problem after pulling out one edge.]
452 
453  Description []
454 
455  SideEffects []
456 
457  SeeAlso []
458 
459 ***********************************************************************/
460 void Nwk_ManGraphUpdate( Nwk_Grf_t * p, Nwk_Vrt_t * pVertex, Nwk_Vrt_t * pNext )
461 {
462  Nwk_Vrt_t * pChanged, * pOther;
463  int i, k;
464 // Nwk_ManGraphCheckLists( p );
465  Nwk_ManGraphListExtract( p, pVertex );
466  Nwk_ManGraphListExtract( p, pNext );
467  // update neihbors of pVertex
468  Nwk_VertexForEachAdjacent( p, pVertex, pChanged, i )
469  {
470  if ( pChanged == pNext )
471  continue;
472  Nwk_ManGraphListExtract( p, pChanged );
473  // move those that use this one
474  if ( pChanged->nEdges > 1 )
475  Nwk_VertexForEachAdjacent( p, pChanged, pOther, k )
476  {
477  if ( pOther == pVertex || pOther->nEdges > 1 )
478  continue;
479  assert( pOther->nEdges == 1 );
480  Nwk_ManGraphListExtract( p, pOther );
481  pChanged->nEdges--;
482  Nwk_ManGraphListInsert( p, pOther );
483  pChanged->nEdges++;
484  }
485  // remove the edge
486  Nwk_ManGraphVertexRemoveEdge( pChanged, pVertex );
487  // add the changed vertex back
488  if ( pChanged->nEdges > 0 )
489  Nwk_ManGraphListInsert( p, pChanged );
490  }
491  // update neihbors of pNext
492  Nwk_VertexForEachAdjacent( p, pNext, pChanged, i )
493  {
494  if ( pChanged == pVertex )
495  continue;
496  Nwk_ManGraphListExtract( p, pChanged );
497  // move those that use this one
498  if ( pChanged->nEdges > 1 )
499  Nwk_VertexForEachAdjacent( p, pChanged, pOther, k )
500  {
501  if ( pOther == pNext || pOther->nEdges > 1 )
502  continue;
503  assert( pOther->nEdges == 1 );
504  Nwk_ManGraphListExtract( p, pOther );
505  pChanged->nEdges--;
506  Nwk_ManGraphListInsert( p, pOther );
507  pChanged->nEdges++;
508  }
509  // remove the edge
510  Nwk_ManGraphVertexRemoveEdge( pChanged, pNext );
511  // add the changed vertex back
512  if ( pChanged->nEdges > 0 )
513  Nwk_ManGraphListInsert( p, pChanged );
514  }
515  // add to the result
516  if ( pVertex->Id < pNext->Id )
517  {
518  Vec_IntPush( p->vPairs, p->pMapId2Lut[pVertex->Id] );
519  Vec_IntPush( p->vPairs, p->pMapId2Lut[pNext->Id] );
520  }
521  else
522  {
523  Vec_IntPush( p->vPairs, p->pMapId2Lut[pNext->Id] );
524  Vec_IntPush( p->vPairs, p->pMapId2Lut[pVertex->Id] );
525  }
526 // Nwk_ManGraphCheckLists( p );
527 }
528 
529 /**Function*************************************************************
530 
531  Synopsis [Counts the number of entries in the list.]
532 
533  Description []
534 
535  SideEffects []
536 
537  SeeAlso []
538 
539 ***********************************************************************/
540 int Nwk_ManGraphListLength( Nwk_Grf_t * p, int List )
541 {
542  Nwk_Vrt_t * pThis;
543  int fVerbose = 0;
544  int Counter = 0;
545  Nwk_ListForEachVertex( p, List, pThis )
546  {
547  if ( fVerbose && Counter < 20 )
548  printf( "%d ", p->pVerts[pThis->pEdges[0]]->nEdges );
549  Counter++;
550  }
551  if ( fVerbose )
552  printf( "\n" );
553  return Counter;
554 }
555 
556 /**Function*************************************************************
557 
558  Synopsis [Returns the adjacent vertex with the mininum number of edges.]
559 
560  Description []
561 
562  SideEffects []
563 
564  SeeAlso []
565 
566 ***********************************************************************/
567 Nwk_Vrt_t * Nwk_ManGraphListFindMinEdge( Nwk_Grf_t * p, Nwk_Vrt_t * pVert )
568 {
569  Nwk_Vrt_t * pThis, * pMinCost = NULL;
570  int k;
571  Nwk_VertexForEachAdjacent( p, pVert, pThis, k )
572  {
573  if ( pMinCost == NULL || pMinCost->nEdges > pThis->nEdges )
574  pMinCost = pThis;
575  }
576  return pMinCost;
577 }
578 
579 /**Function*************************************************************
580 
581  Synopsis [Finds the best vertext in the list.]
582 
583  Description []
584 
585  SideEffects []
586 
587  SeeAlso []
588 
589 ***********************************************************************/
590 Nwk_Vrt_t * Nwk_ManGraphListFindMin( Nwk_Grf_t * p, int List )
591 {
592  Nwk_Vrt_t * pThis, * pMinCost = NULL;
593  int k, Counter = 10000, BestCost = 1000000;
594  Nwk_ListForEachVertex( p, List, pThis )
595  {
596  for ( k = 0; k < pThis->nEdges; k++ )
597  {
598  if ( pMinCost == NULL || BestCost > p->pVerts[pThis->pEdges[k]]->nEdges )
599  {
600  BestCost = p->pVerts[pThis->pEdges[k]]->nEdges;
601  pMinCost = pThis;
602  }
603  }
604  if ( --Counter == 0 )
605  break;
606  }
607  return pMinCost;
608 }
609 
610 /**Function*************************************************************
611 
612  Synopsis [Solves the problem by extracting one edge at a time.]
613 
614  Description []
615 
616  SideEffects []
617 
618  SeeAlso []
619 
620 ***********************************************************************/
621 void Nwk_ManGraphSolve( Nwk_Grf_t * p )
622 {
623  Nwk_Vrt_t * pVertex, * pNext;
624  int i, j;
625  Nwk_ManGraphPrepare( p );
626  while ( 1 )
627  {
628  // find the next vertex to extract
629  assert( p->pLists1[0] == 0 );
630  for ( i = 1; i <= NWK_MAX_LIST; i++ )
631  if ( p->pLists1[i] )
632  {
633 // printf( "%d ", i );
634 // printf( "ListA = %2d. Length = %5d.\n", i, Nwk_ManGraphListLength(p,p->pLists1[i]) );
635  pVertex = p->pVerts[ p->pLists1[i] ];
636  assert( pVertex->nEdges == 1 );
637  pNext = p->pVerts[ pVertex->pEdges[0] ];
638  Nwk_ManGraphUpdate( p, pVertex, pNext );
639  break;
640  }
641  if ( i < NWK_MAX_LIST + 1 )
642  continue;
643  // find the next vertex to extract
644  assert( p->pLists2[0] == 0 );
645  assert( p->pLists2[1] == 0 );
646  for ( j = 2; j <= NWK_MAX_LIST; j++ )
647  if ( p->pLists2[j] )
648  {
649 // printf( "***%d ", j );
650 // printf( "ListB = %2d. Length = %5d.\n", j, Nwk_ManGraphListLength(p,p->pLists2[j]) );
651  pVertex = Nwk_ManGraphListFindMin( p, p->pLists2[j] );
652  assert( pVertex->nEdges == j || j == NWK_MAX_LIST );
653  pNext = Nwk_ManGraphListFindMinEdge( p, pVertex );
654  Nwk_ManGraphUpdate( p, pVertex, pNext );
655  break;
656  }
657  if ( j == NWK_MAX_LIST + 1 )
658  break;
659  }
660  Nwk_ManGraphSortPairs( p );
661 }
662 
663 /**Function*************************************************************
664 
665  Synopsis [Reads graph from file.]
666 
667  Description []
668 
669  SideEffects []
670 
671  SeeAlso []
672 
673 ***********************************************************************/
674 Nwk_Grf_t * Nwk_ManLutMergeReadGraph( char * pFileName )
675 {
676  Nwk_Grf_t * p;
677  FILE * pFile;
678  char Buffer[100];
679  int nNodes, nEdges, iNode1, iNode2;
680  int RetValue;
681  pFile = fopen( pFileName, "r" );
682  RetValue = fscanf( pFile, "%s %d", Buffer, &nNodes );
683  RetValue = fscanf( pFile, "%s %d", Buffer, &nEdges );
684  p = Nwk_ManGraphAlloc( nNodes );
685  while ( fscanf( pFile, "%s %d %d", Buffer, &iNode1, &iNode2 ) == 3 )
686  Nwk_ManGraphHashEdge( p, iNode1, iNode2 );
687  assert( p->nEdges == nEdges );
688  fclose( pFile );
689  return p;
690 }
691 
692 /**Function*************************************************************
693 
694  Synopsis [Solves the graph coming from file.]
695 
696  Description []
697 
698  SideEffects []
699 
700  SeeAlso []
701 
702 ***********************************************************************/
703 int Nwk_ManLutMergeGraphTest( char * pFileName )
704 {
705  int nPairs;
706  Nwk_Grf_t * p;
707  abctime clk = Abc_Clock();
708  p = Nwk_ManLutMergeReadGraph( pFileName );
709  ABC_PRT( "Reading", Abc_Clock() - clk );
710  clk = Abc_Clock();
711  Nwk_ManGraphSolve( p );
712  printf( "GRAPH: Nodes = %6d. Edges = %6d. Pairs = %6d. ",
713  p->nVerts, p->nEdges, Vec_IntSize(p->vPairs)/2 );
714  ABC_PRT( "Solving", Abc_Clock() - clk );
715  nPairs = Vec_IntSize(p->vPairs)/2;
716  Nwk_ManGraphReportMemoryUsage( p );
717  Nwk_ManGraphFree( p );
718  return nPairs;
719 }
720 
721 
722 
723 
724 /**Function*************************************************************
725 
726  Synopsis [Marks the fanins of the node with the current trav ID.]
727 
728  Description []
729 
730  SideEffects []
731 
732  SeeAlso []
733 
734 ***********************************************************************/
735 void Nwk_ManMarkFanins_rec( Nwk_Obj_t * pLut, int nLevMin )
736 {
737  Nwk_Obj_t * pNext;
738  int i;
739  if ( !Nwk_ObjIsNode(pLut) )
740  return;
741  if ( Nwk_ObjIsTravIdCurrent( pLut ) )
742  return;
743  Nwk_ObjSetTravIdCurrent( pLut );
744  if ( Nwk_ObjLevel(pLut) < nLevMin )
745  return;
746  Nwk_ObjForEachFanin( pLut, pNext, i )
747  Nwk_ManMarkFanins_rec( pNext, nLevMin );
748 }
749 
750 /**Function*************************************************************
751 
752  Synopsis [Marks the fanouts of the node with the current trav ID.]
753 
754  Description []
755 
756  SideEffects []
757 
758  SeeAlso []
759 
760 ***********************************************************************/
761 void Nwk_ManMarkFanouts_rec( Nwk_Obj_t * pLut, int nLevMax, int nFanMax )
762 {
763  Nwk_Obj_t * pNext;
764  int i;
765  if ( !Nwk_ObjIsNode(pLut) )
766  return;
767  if ( Nwk_ObjIsTravIdCurrent( pLut ) )
768  return;
769  Nwk_ObjSetTravIdCurrent( pLut );
770  if ( Nwk_ObjLevel(pLut) > nLevMax )
771  return;
772  if ( Nwk_ObjFanoutNum(pLut) > nFanMax )
773  return;
774  Nwk_ObjForEachFanout( pLut, pNext, i )
775  Nwk_ManMarkFanouts_rec( pNext, nLevMax, nFanMax );
776 }
777 
778 /**Function*************************************************************
779 
780  Synopsis [Collects the circle of nodes around the given set.]
781 
782  Description []
783 
784  SideEffects []
785 
786  SeeAlso []
787 
788 ***********************************************************************/
789 void Nwk_ManCollectCircle( Vec_Ptr_t * vStart, Vec_Ptr_t * vNext, int nFanMax )
790 {
791  Nwk_Obj_t * pObj, * pNext;
792  int i, k;
793  Vec_PtrClear( vNext );
794  Vec_PtrForEachEntry( Nwk_Obj_t *, vStart, pObj, i )
795  {
796  Nwk_ObjForEachFanin( pObj, pNext, k )
797  {
798  if ( !Nwk_ObjIsNode(pNext) )
799  continue;
800  if ( Nwk_ObjIsTravIdCurrent( pNext ) )
801  continue;
802  Nwk_ObjSetTravIdCurrent( pNext );
803  Vec_PtrPush( vNext, pNext );
804  }
805  Nwk_ObjForEachFanout( pObj, pNext, k )
806  {
807  if ( !Nwk_ObjIsNode(pNext) )
808  continue;
809  if ( Nwk_ObjIsTravIdCurrent( pNext ) )
810  continue;
811  Nwk_ObjSetTravIdCurrent( pNext );
812  if ( Nwk_ObjFanoutNum(pNext) > nFanMax )
813  continue;
814  Vec_PtrPush( vNext, pNext );
815  }
816  }
817 }
818 
819 /**Function*************************************************************
820 
821  Synopsis [Collects the circle of nodes removes from the given one.]
822 
823  Description []
824 
825  SideEffects []
826 
827  SeeAlso []
828 
829 ***********************************************************************/
830 void Nwk_ManCollectNonOverlapCands( Nwk_Obj_t * pLut, Vec_Ptr_t * vStart, Vec_Ptr_t * vNext, Vec_Ptr_t * vCands, Nwk_LMPars_t * pPars )
831 {
832  Vec_Ptr_t * vTemp;
833  Nwk_Obj_t * pObj;
834  int i, k;
835  Vec_PtrClear( vCands );
836  if ( pPars->nMaxSuppSize - Nwk_ObjFaninNum(pLut) <= 1 )
837  return;
838 
839  // collect nodes removed by this distance
840  assert( pPars->nMaxDistance > 0 );
841  Vec_PtrClear( vStart );
842  Vec_PtrPush( vStart, pLut );
843  Nwk_ManIncrementTravId( pLut->pMan );
844  Nwk_ObjSetTravIdCurrent( pLut );
845  for ( i = 1; i <= pPars->nMaxDistance; i++ )
846  {
847  Nwk_ManCollectCircle( vStart, vNext, pPars->nMaxFanout );
848  vTemp = vStart;
849  vStart = vNext;
850  vNext = vTemp;
851  // collect the nodes in vStart
852  Vec_PtrForEachEntry( Nwk_Obj_t *, vStart, pObj, k )
853  Vec_PtrPush( vCands, pObj );
854  }
855 
856  // mark the TFI/TFO nodes
857  Nwk_ManIncrementTravId( pLut->pMan );
858  if ( pPars->fUseTfiTfo )
859  Nwk_ObjSetTravIdCurrent( pLut );
860  else
861  {
862  Nwk_ObjSetTravIdPrevious( pLut );
863  Nwk_ManMarkFanins_rec( pLut, Nwk_ObjLevel(pLut) - pPars->nMaxDistance );
864  Nwk_ObjSetTravIdPrevious( pLut );
865  Nwk_ManMarkFanouts_rec( pLut, Nwk_ObjLevel(pLut) + pPars->nMaxDistance, pPars->nMaxFanout );
866  }
867 
868  // collect nodes satisfying the following conditions:
869  // - they are close enough in terms of distance
870  // - they are not in the TFI/TFO of the LUT
871  // - they have no more than the given number of fanins
872  // - they have no more than the given diff in delay
873  k = 0;
874  Vec_PtrForEachEntry( Nwk_Obj_t *, vCands, pObj, i )
875  {
876  if ( Nwk_ObjIsTravIdCurrent(pObj) )
877  continue;
878  if ( Nwk_ObjFaninNum(pLut) + Nwk_ObjFaninNum(pObj) > pPars->nMaxSuppSize )
879  continue;
880  if ( Nwk_ObjLevel(pLut) - Nwk_ObjLevel(pObj) > pPars->nMaxLevelDiff ||
881  Nwk_ObjLevel(pObj) - Nwk_ObjLevel(pLut) > pPars->nMaxLevelDiff )
882  continue;
883  Vec_PtrWriteEntry( vCands, k++, pObj );
884  }
885  Vec_PtrShrink( vCands, k );
886 }
887 
888 
889 /**Function*************************************************************
890 
891  Synopsis [Count the total number of fanins.]
892 
893  Description []
894 
895  SideEffects []
896 
897  SeeAlso []
898 
899 ***********************************************************************/
900 int Nwk_ManCountTotalFanins( Nwk_Obj_t * pLut, Nwk_Obj_t * pCand )
901 {
902  Nwk_Obj_t * pFanin;
903  int i, nCounter = Nwk_ObjFaninNum(pLut);
904  Nwk_ObjForEachFanin( pCand, pFanin, i )
905  nCounter += !pFanin->MarkC;
906  return nCounter;
907 }
908 
909 /**Function*************************************************************
910 
911  Synopsis [Collects overlapping candidates.]
912 
913  Description []
914 
915  SideEffects []
916 
917  SeeAlso []
918 
919 ***********************************************************************/
920 void Nwk_ManCollectOverlapCands( Nwk_Obj_t * pLut, Vec_Ptr_t * vCands, Nwk_LMPars_t * pPars )
921 {
922  Nwk_Obj_t * pFanin, * pObj;
923  int i, k;
924  // mark fanins of pLut
925  Nwk_ObjForEachFanin( pLut, pFanin, i )
926  pFanin->MarkC = 1;
927  // collect the matching fanouts of each fanin of the node
928  Vec_PtrClear( vCands );
929  Nwk_ManIncrementTravId( pLut->pMan );
930  Nwk_ObjSetTravIdCurrent( pLut );
931  Nwk_ObjForEachFanin( pLut, pFanin, i )
932  {
933  if ( !Nwk_ObjIsNode(pFanin) )
934  continue;
935  if ( Nwk_ObjFanoutNum(pFanin) > pPars->nMaxFanout )
936  continue;
937  Nwk_ObjForEachFanout( pFanin, pObj, k )
938  {
939  if ( !Nwk_ObjIsNode(pObj) )
940  continue;
941  if ( Nwk_ObjIsTravIdCurrent( pObj ) )
942  continue;
943  Nwk_ObjSetTravIdCurrent( pObj );
944  // check the difference in delay
945  if ( Nwk_ObjLevel(pLut) - Nwk_ObjLevel(pObj) > pPars->nMaxLevelDiff ||
946  Nwk_ObjLevel(pObj) - Nwk_ObjLevel(pLut) > pPars->nMaxLevelDiff )
947  continue;
948  // check the total number of fanins of the node
949  if ( Nwk_ManCountTotalFanins(pLut, pObj) > pPars->nMaxSuppSize )
950  continue;
951  Vec_PtrPush( vCands, pObj );
952  }
953  }
954  // unmark fanins of pLut
955  Nwk_ObjForEachFanin( pLut, pFanin, i )
956  pFanin->MarkC = 0;
957 }
958 
959 /**Function*************************************************************
960 
961  Synopsis [Performs LUT merging with parameters.]
962 
963  Description []
964 
965  SideEffects []
966 
967  SeeAlso []
968 
969 ***********************************************************************/
970 Vec_Int_t * Nwk_ManLutMerge( Nwk_Man_t * pNtk, void * pParsInit )
971 {
972  Nwk_LMPars_t * pPars = (Nwk_LMPars_t *)pParsInit;
973  Nwk_Grf_t * p;
974  Vec_Int_t * vResult;
975  Vec_Ptr_t * vStart, * vNext, * vCands1, * vCands2;
976  Nwk_Obj_t * pLut, * pCand;
977  int i, k, nVertsMax, nCands;
978  abctime clk = Abc_Clock();
979  // count the number of vertices
980  nVertsMax = 0;
981  Nwk_ManForEachNode( pNtk, pLut, i )
982  nVertsMax += (int)(Nwk_ObjFaninNum(pLut) <= pPars->nMaxLutSize);
983  p = Nwk_ManGraphAlloc( nVertsMax );
984  // create graph
985  vStart = Vec_PtrAlloc( 1000 );
986  vNext = Vec_PtrAlloc( 1000 );
987  vCands1 = Vec_PtrAlloc( 1000 );
988  vCands2 = Vec_PtrAlloc( 1000 );
989  nCands = 0;
990  Nwk_ManForEachNode( pNtk, pLut, i )
991  {
992  if ( Nwk_ObjFaninNum(pLut) > pPars->nMaxLutSize )
993  continue;
994  Nwk_ManCollectOverlapCands( pLut, vCands1, pPars );
995  if ( pPars->fUseDiffSupp )
996  Nwk_ManCollectNonOverlapCands( pLut, vStart, vNext, vCands2, pPars );
997  if ( Vec_PtrSize(vCands1) == 0 && Vec_PtrSize(vCands2) == 0 )
998  continue;
999  nCands += Vec_PtrSize(vCands1) + Vec_PtrSize(vCands2);
1000  // save candidates
1001  Vec_PtrForEachEntry( Nwk_Obj_t *, vCands1, pCand, k )
1002  Nwk_ManGraphHashEdge( p, Nwk_ObjId(pLut), Nwk_ObjId(pCand) );
1003  Vec_PtrForEachEntry( Nwk_Obj_t *, vCands2, pCand, k )
1004  Nwk_ManGraphHashEdge( p, Nwk_ObjId(pLut), Nwk_ObjId(pCand) );
1005  // print statistics about this node
1006  if ( pPars->fVeryVerbose )
1007  printf( "Node %6d : Fanins = %d. Fanouts = %3d. Cand1 = %3d. Cand2 = %3d.\n",
1008  Nwk_ObjId(pLut), Nwk_ObjFaninNum(pLut), Nwk_ObjFaninNum(pLut),
1009  Vec_PtrSize(vCands1), Vec_PtrSize(vCands2) );
1010  }
1011  Vec_PtrFree( vStart );
1012  Vec_PtrFree( vNext );
1013  Vec_PtrFree( vCands1 );
1014  Vec_PtrFree( vCands2 );
1015  if ( pPars->fVerbose )
1016  {
1017  printf( "Mergable LUTs = %6d. Total cands = %6d. ", p->nVertsMax, nCands );
1018  ABC_PRT( "Deriving graph", Abc_Clock() - clk );
1019  }
1020  // solve the graph problem
1021  clk = Abc_Clock();
1022  Nwk_ManGraphSolve( p );
1023  if ( pPars->fVerbose )
1024  {
1025  printf( "GRAPH: Nodes = %6d. Edges = %6d. Pairs = %6d. ",
1026  p->nVerts, p->nEdges, Vec_IntSize(p->vPairs)/2 );
1027  ABC_PRT( "Solving", Abc_Clock() - clk );
1028  Nwk_ManGraphReportMemoryUsage( p );
1029  }
1030  vResult = p->vPairs; p->vPairs = NULL;
1031 /*
1032  for ( i = 0; i < vResult->nSize; i += 2 )
1033  printf( "(%d,%d) ", vResult->pArray[i], vResult->pArray[i+1] );
1034  printf( "\n" );
1035 */
1036  Nwk_ManGraphFree( p );
1037  return vResult;
1038 }
1039 
1040 ////////////////////////////////////////////////////////////////////////
1041 /// END OF FILE ///
1042 ////////////////////////////////////////////////////////////////////////
1043 
1044 
1045 ABC_NAMESPACE_IMPL_END
1046 
memset
char * memset()
Nwk_ManGraphReportMemoryUsage
void Nwk_ManGraphReportMemoryUsage(Nwk_Grf_t *p)
Definition: nwkMerge.c:93
Nwk_ManGraphListInsert
static void Nwk_ManGraphListInsert(Nwk_Grf_t *p, Nwk_Vrt_t *pVertex)
Definition: nwkMerge.c:210
Nwk_ManLutMerge
Vec_Int_t * Nwk_ManLutMerge(Nwk_Man_t *pNtk, void *pParsInit)
Definition: nwkMerge.c:970
Nwk_Edg_t_::iNode1
int iNode1
Definition: nwkMerge.h:63
Vec_Ptr_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
Abc_PrimeCudd
static int Abc_PrimeCudd(unsigned int p)
Definition: abc_global.h:383
Nwk_Grf_t_::nMemBytes1
int nMemBytes1
Definition: nwkMerge.h:103
Nwk_LMPars_t_::fUseDiffSupp
int fUseDiffSupp
Definition: nwkMerge.h:53
Nwk_Vrt_t_::iPrev
int iPrev
Definition: nwkMerge.h:73
Nwk_LMPars_t_::nMaxFanout
int nMaxFanout
Definition: nwkMerge.h:52
Nwk_ObjFanoutNum
static int Nwk_ObjFanoutNum(Nwk_Obj_t *p)
Definition: nwk.h:138
Nwk_ManMarkFanins_rec
void Nwk_ManMarkFanins_rec(Nwk_Obj_t *pLut, int nLevMin)
Definition: nwkMerge.c:735
Nwk_Obj_t
typedefABC_NAMESPACE_HEADER_START struct Nwk_Obj_t_ Nwk_Obj_t
INCLUDES ///.
Definition: nwk.h:49
Nwk_ManGraphVertexRemoveEdge
static void Nwk_ManGraphVertexRemoveEdge(Nwk_Vrt_t *pThis, Nwk_Vrt_t *pNext)
Definition: nwkMerge.c:437
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_Int_t
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
Nwk_Vrt_t_::iNext
int iNext
Definition: nwkMerge.h:74
Nwk_ListForEachVertex
#define Nwk_ListForEachVertex(p, List, pVrt)
Definition: nwkMerge.h:115
Nwk_ManCountTotalFanins
int Nwk_ManCountTotalFanins(Nwk_Obj_t *pLut, Nwk_Obj_t *pCand)
Definition: nwkMerge.c:900
Aig_MmFixedStop
void Aig_MmFixedStop(Aig_MmFixed_t *p, int fVerbose)
Definition: aigMem.c:132
Nwk_Grf_t_::pVerts
Nwk_Vrt_t ** pVerts
Definition: nwkMerge.h:92
Nwk_Vrt_t_::Id
int Id
Definition: nwkMerge.h:72
Aig_MmFlexEntryFetch
char * Aig_MmFlexEntryFetch(Aig_MmFlex_t *p, int nBytes)
Definition: aigMem.c:366
Nwk_ObjId
static int Nwk_ObjId(Nwk_Obj_t *p)
Definition: nwk.h:135
Nwk_GraphForEachEdge
#define Nwk_GraphForEachEdge(p, pEdge, k)
MACRO DEFINITIONS ///.
Definition: nwkMerge.h:111
Nwk_Grf_t_::nEdgeHash
int nEdgeHash
Definition: nwkMerge.h:86
Nwk_ObjForEachFanout
#define Nwk_ObjForEachFanout(pObj, pFanout, i)
Definition: nwk.h:201
Nwk_LMPars_t_::nMaxDistance
int nMaxDistance
Definition: nwkMerge.h:50
Nwk_ManGraphFree
void Nwk_ManGraphFree(Nwk_Grf_t *p)
Definition: nwkMerge.c:70
Nwk_ManGraphListExtract
static void Nwk_ManGraphListExtract(Nwk_Grf_t *p, Nwk_Vrt_t *pVertex)
Definition: nwkMerge.c:243
Nwk_Grf_t_::nEdges
int nEdges
Definition: nwkMerge.h:90
Nwk_Vrt_t_::pEdges
int pEdges[0]
Definition: nwkMerge.h:76
Nwk_ManGraphListLength
int Nwk_ManGraphListLength(Nwk_Grf_t *p, int List)
Definition: nwkMerge.c:540
Nwk_ManGraphSolve
void Nwk_ManGraphSolve(Nwk_Grf_t *p)
Definition: nwkMerge.c:621
Vec_PtrPush
static void Vec_PtrPush(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:606
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Nwk_Grf_t_::nVertsMax
int nVertsMax
Definition: nwkMerge.h:85
Abc_Clock
static abctime Abc_Clock()
Definition: abc_global.h:279
Nwk_Grf_t_::pLists2
int pLists2[NWK_MAX_LIST+1]
Definition: nwkMerge.h:96
Vec_PtrSize
static int Vec_PtrSize(Vec_Ptr_t *p)
Definition: vecPtr.h:295
Aig_MmFixedStart
Aig_MmFixed_t * Aig_MmFixedStart(int nEntrySize, int nEntriesMax)
FUNCTION DEFINITIONS ///.
Definition: aigMem.c:96
Nwk_ManLutMergeGraphTest
int Nwk_ManLutMergeGraphTest(char *pFileName)
Definition: nwkMerge.c:703
Nwk_ManGraphListAdd
static void Nwk_ManGraphListAdd(Nwk_Grf_t *p, int *pList, Nwk_Vrt_t *pVertex)
Definition: nwkMerge.c:157
Nwk_Grf_t_::pMemVerts
Aig_MmFlex_t * pMemVerts
Definition: nwkMerge.h:93
Nwk_ObjFaninNum
static int Nwk_ObjFaninNum(Nwk_Obj_t *p)
Definition: nwk.h:137
Nwk_Grf_t_::nVerts
int nVerts
Definition: nwkMerge.h:91
Nwk_Edg_t
struct Nwk_Edg_t_ Nwk_Edg_t
Definition: nwkMerge.h:60
Nwk_VertexForEachAdjacent
#define Nwk_VertexForEachAdjacent(p, pVrt, pNext, k)
Definition: nwkMerge.h:119
Nwk_ObjSetTravIdCurrent
static void Nwk_ObjSetTravIdCurrent(Nwk_Obj_t *pObj)
Definition: nwk.h:166
Nwk_ManGraphListDelete
static void Nwk_ManGraphListDelete(Nwk_Grf_t *p, int *pList, Nwk_Vrt_t *pVertex)
Definition: nwkMerge.c:181
Nwk_Edg_t_
Definition: nwkMerge.h:61
Nwk_LMPars_t_::nMaxSuppSize
int nMaxSuppSize
Definition: nwkMerge.h:49
Nwk_Vrt_t_::nEdges
int nEdges
Definition: nwkMerge.h:75
Nwk_Grf_t_::pLists1
int pLists1[NWK_MAX_LIST+1]
Definition: nwkMerge.h:95
Vec_IntAlloc
static Vec_Int_t * Vec_IntAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: bblif.c:149
Nwk_Grf_t_::nMemBytes2
int nMemBytes2
Definition: nwkMerge.h:104
Nwk_ManCollectOverlapCands
void Nwk_ManCollectOverlapCands(Nwk_Obj_t *pLut, Vec_Ptr_t *vCands, Nwk_LMPars_t *pPars)
Definition: nwkMerge.c:920
Nwk_Man_t_
Definition: nwk.h:61
Nwk_ManGraphCheckLists
void Nwk_ManGraphCheckLists(Nwk_Grf_t *p)
Definition: nwkMerge.c:402
Nwk_ManGraphHashEdge
void Nwk_ManGraphHashEdge(Nwk_Grf_t *p, int iLut1, int iLut2)
Definition: nwkMerge.c:119
Nwk_Grf_t_::nObjs
int nObjs
Definition: nwkMerge.h:84
Nwk_ObjIsTravIdCurrent
static int Nwk_ObjIsTravIdCurrent(Nwk_Obj_t *pObj)
Definition: nwk.h:168
Nwk_ManGraphAlloc
ABC_NAMESPACE_IMPL_START Nwk_Grf_t * Nwk_ManGraphAlloc(int nVertsMax)
DECLARATIONS ///.
Definition: nwkMerge.c:46
Nwk_Grf_t
struct Nwk_Grf_t_ Nwk_Grf_t
Definition: nwkMerge.h:80
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
Nwk_LMPars_t_::fVeryVerbose
int fVeryVerbose
Definition: nwkMerge.h:55
Nwk_LMPars_t_::fUseTfiTfo
int fUseTfiTfo
Definition: nwkMerge.h:54
Nwk_ObjSetTravIdPrevious
static void Nwk_ObjSetTravIdPrevious(Nwk_Obj_t *pObj)
Definition: nwk.h:167
Aig_MmFixedEntryFetch
char * Aig_MmFixedEntryFetch(Aig_MmFixed_t *p)
Definition: aigMem.c:161
Vec_IntPush
static void Vec_IntPush(Vec_Int_t *p, int Entry)
Definition: bblif.c:468
Nwk_ManGraphListFindMinEdge
Nwk_Vrt_t * Nwk_ManGraphListFindMinEdge(Nwk_Grf_t *p, Nwk_Vrt_t *pVert)
Definition: nwkMerge.c:567
Nwk_ManIncrementTravId
ABC_DLL void Nwk_ManIncrementTravId(Nwk_Man_t *pNtk)
DECLARATIONS ///.
Definition: nwkUtil.c:47
Counter
static int Counter
Definition: extraBddMisc.c:1877
Nwk_Grf_t_::pEdgeHash
Nwk_Edg_t ** pEdgeHash
Definition: nwkMerge.h:87
Nwk_Grf_t_::pMapLut2Id
int * pMapLut2Id
Definition: nwkMerge.h:100
Nwk_ManGraphUpdate
void Nwk_ManGraphUpdate(Nwk_Grf_t *p, Nwk_Vrt_t *pVertex, Nwk_Vrt_t *pNext)
Definition: nwkMerge.c:460
Nwk_ManGraphSortPairs
void Nwk_ManGraphSortPairs(Nwk_Grf_t *p)
Definition: nwkMerge.c:363
Nwk_Edg_t_::iNode2
int iNode2
Definition: nwkMerge.h:64
NWK_MAX_LIST
#define NWK_MAX_LIST
INCLUDES ///.
Definition: nwkMerge.h:38
Nwk_Edg_t_::pNext
Nwk_Edg_t * pNext
Definition: nwkMerge.h:65
Vec_PtrWriteEntry
static void Vec_PtrWriteEntry(Vec_Ptr_t *p, int i, void *Entry)
Definition: vecPtr.h:396
Nwk_ManLutMergeReadGraph
Nwk_Grf_t * Nwk_ManLutMergeReadGraph(char *pFileName)
Definition: nwkMerge.c:674
Nwk_ObjIsNode
static int Nwk_ObjIsNode(Nwk_Obj_t *p)
Definition: nwk.h:148
ABC_NAMESPACE_IMPL_START
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
Nwk_Grf_t_::pMapId2Lut
int * pMapId2Lut
Definition: nwkMerge.h:101
Nwk_Grf_t_
Definition: nwkMerge.h:81
Nwk_ManMarkFanouts_rec
void Nwk_ManMarkFanouts_rec(Nwk_Obj_t *pLut, int nLevMax, int nFanMax)
Definition: nwkMerge.c:761
Vec_IntSize
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
Nwk_Vrt_t
struct Nwk_Vrt_t_ Nwk_Vrt_t
Definition: nwkMerge.h:69
Vec_PtrAlloc
static Vec_Ptr_t * Vec_PtrAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecPtr.h:83
Nwk_ObjForEachFanin
#define Nwk_ObjForEachFanin(pObj, pFanin, i)
Definition: nwk.h:199
Nwk_ManCollectNonOverlapCands
void Nwk_ManCollectNonOverlapCands(Nwk_Obj_t *pLut, Vec_Ptr_t *vStart, Vec_Ptr_t *vNext, Vec_Ptr_t *vCands, Nwk_LMPars_t *pPars)
Definition: nwkMerge.c:830
Nwk_ManGraphPrepare
void Nwk_ManGraphPrepare(Nwk_Grf_t *p)
Definition: nwkMerge.c:276
Aig_MmFlexStart
Aig_MmFlex_t * Aig_MmFlexStart()
Definition: aigMem.c:305
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
ABC_PRT
#define ABC_PRT(a, t)
Definition: abc_global.h:220
Aig_MmFlexStop
void Aig_MmFlexStop(Aig_MmFlex_t *p, int fVerbose)
Definition: aigMem.c:337
Nwk_LMPars_t_::nMaxLutSize
int nMaxLutSize
Definition: nwkMerge.h:48
ABC_CALLOC
#define ABC_CALLOC(type, num)
Definition: abc_global.h:230
Nwk_ObjLevel
static int Nwk_ObjLevel(Nwk_Obj_t *pObj)
Definition: nwk.h:162
Nwk_Vrt_t_
Definition: nwkMerge.h:70
Nwk_Grf_t_::vPairs
Vec_Int_t * vPairs
Definition: nwkMerge.h:98
assert
#define assert(ex)
Definition: util_old.h:213
Vec_PtrClear
static void Vec_PtrClear(Vec_Ptr_t *p)
Definition: vecPtr.h:545
Nwk_ManGraphListFindMin
Nwk_Vrt_t * Nwk_ManGraphListFindMin(Nwk_Grf_t *p, int List)
Definition: nwkMerge.c:590
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
Nwk_ManCollectCircle
void Nwk_ManCollectCircle(Vec_Ptr_t *vStart, Vec_Ptr_t *vNext, int nFanMax)
Definition: nwkMerge.c:789
Vec_IntClear
static void Vec_IntClear(Vec_Int_t *p)
Definition: bblif.c:452
abctime
ABC_INT64_T abctime
Definition: abc_global.h:278
Vec_PtrShrink
static void Vec_PtrShrink(Vec_Ptr_t *p, int nSizeNew)
Definition: vecPtr.h:528
Nwk_LMPars_t_::fVerbose
int fVerbose
Definition: nwkMerge.h:56
Nwk_LMPars_t_
Definition: nwkMerge.h:46
Nwk_LMPars_t_::nMaxLevelDiff
int nMaxLevelDiff
Definition: nwkMerge.h:51
Nwk_Grf_t_::pMemEdges
Aig_MmFixed_t * pMemEdges
Definition: nwkMerge.h:88
Vec_PtrFree
static void Vec_PtrFree(Vec_Ptr_t *p)
Definition: vecPtr.h:223
Nwk_ManForEachNode
#define Nwk_ManForEachNode(p, pObj, i)
Definition: nwk.h:192