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 ***********************************************************************/
Nwk_ManGraphAlloc(int nVertsMax)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 ***********************************************************************/
Nwk_ManGraphFree(Nwk_Grf_t * p)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 ***********************************************************************/
Nwk_ManGraphReportMemoryUsage(Nwk_Grf_t * p)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 ***********************************************************************/
Nwk_ManGraphHashEdge(Nwk_Grf_t * p,int iLut1,int iLut2)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 ***********************************************************************/
Nwk_ManGraphListAdd(Nwk_Grf_t * p,int * pList,Nwk_Vrt_t * pVertex)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 ***********************************************************************/
Nwk_ManGraphListDelete(Nwk_Grf_t * p,int * pList,Nwk_Vrt_t * pVertex)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 ***********************************************************************/
Nwk_ManGraphListInsert(Nwk_Grf_t * p,Nwk_Vrt_t * pVertex)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 ***********************************************************************/
Nwk_ManGraphListExtract(Nwk_Grf_t * p,Nwk_Vrt_t * pVertex)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 ***********************************************************************/
Nwk_ManGraphPrepare(Nwk_Grf_t * p)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 ***********************************************************************/
Nwk_ManGraphSortPairs(Nwk_Grf_t * p)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 ***********************************************************************/
Nwk_ManGraphCheckLists(Nwk_Grf_t * p)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 ***********************************************************************/
Nwk_ManGraphVertexRemoveEdge(Nwk_Vrt_t * pThis,Nwk_Vrt_t * pNext)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 ***********************************************************************/
Nwk_ManGraphUpdate(Nwk_Grf_t * p,Nwk_Vrt_t * pVertex,Nwk_Vrt_t * pNext)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 ***********************************************************************/
Nwk_ManGraphListLength(Nwk_Grf_t * p,int List)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 ***********************************************************************/
Nwk_ManGraphListFindMinEdge(Nwk_Grf_t * p,Nwk_Vrt_t * pVert)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 ***********************************************************************/
Nwk_ManGraphListFindMin(Nwk_Grf_t * p,int List)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 ***********************************************************************/
Nwk_ManGraphSolve(Nwk_Grf_t * p)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 ***********************************************************************/
Nwk_ManLutMergeReadGraph(char * pFileName)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 ***********************************************************************/
Nwk_ManLutMergeGraphTest(char * pFileName)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 ***********************************************************************/
Nwk_ManMarkFanins_rec(Nwk_Obj_t * pLut,int nLevMin)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 ***********************************************************************/
Nwk_ManMarkFanouts_rec(Nwk_Obj_t * pLut,int nLevMax,int nFanMax)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 ***********************************************************************/
Nwk_ManCollectCircle(Vec_Ptr_t * vStart,Vec_Ptr_t * vNext,int nFanMax)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 ***********************************************************************/
Nwk_ManCollectNonOverlapCands(Nwk_Obj_t * pLut,Vec_Ptr_t * vStart,Vec_Ptr_t * vNext,Vec_Ptr_t * vCands,Nwk_LMPars_t * pPars)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 ***********************************************************************/
Nwk_ManCountTotalFanins(Nwk_Obj_t * pLut,Nwk_Obj_t * pCand)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 ***********************************************************************/
Nwk_ManCollectOverlapCands(Nwk_Obj_t * pLut,Vec_Ptr_t * vCands,Nwk_LMPars_t * pPars)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 ***********************************************************************/
Nwk_ManLutMerge(Nwk_Man_t * pNtk,void * pParsInit)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 
1047