ABC: A System for Sequential Synthesis and Verification
 
Loading...
Searching...
No Matches
giaKf.c
Go to the documentation of this file.
1
20
21#include "gia.h"
22#include "misc/vec/vecSet.h"
23
24#ifdef _MSC_VER
25#define unlink _unlink
26#else
27#include <unistd.h>
28#endif
29
30#ifdef ABC_USE_PTHREADS
31
32#ifdef _WIN32
33#include "../lib/pthread.h"
34#else
35#include <pthread.h>
36#endif
37
38#endif
39
40ABC_NAMESPACE_IMPL_START
41
45
46#ifndef ABC_USE_PTHREADS
47
48void Kf_ManSetDefaultPars( Jf_Par_t * pPars ) {}
49Gia_Man_t * Kf_ManPerformMapping( Gia_Man_t * pGia, Jf_Par_t * pPars ) { return NULL; }
50
51#else // pthreads are used
52
53#define KF_LEAF_MAX 16
54#define KF_CUT_MAX 32
55#define KF_PROC_MAX 32
56#define KF_WORD_MAX ((KF_LEAF_MAX > 6) ? 1 << (KF_LEAF_MAX-6) : 1)
57#define KF_LOG_TABLE 8
58
59#define KF_ADD_ON1 2 // offset in cut storage for each node (cut count; best cut)
60#define KF_ADD_ON2 4 // offset in cut storage for each cut (leaf count; function, cut delay; cut area)
61
62typedef struct Kf_Cut_t_ Kf_Cut_t;
63typedef struct Kf_Set_t_ Kf_Set_t;
64typedef struct Kf_Man_t_ Kf_Man_t;
65
66struct Kf_Cut_t_
67{
68 word Sign; // signature
69 int Polar; // polarity
70 int Delay; // delay
71 float Area; // area
72 int iFunc; // function
73 int iNext; // next cut
74 int nLeaves; // number of leaves
75 int pLeaves[KF_LEAF_MAX];
76};
77struct Kf_Set_t_
78{
79 Kf_Man_t * pMan; // manager
80 unsigned short nLutSize; // lut size
81 unsigned short nCutNum; // cut count
82 int nCuts0; // fanin0 cut count
83 int nCuts1; // fanin1 cut count
84 int nCuts; // resulting cut count
85 int nTEntries; // hash table entries
86 int TableMask; // hash table mask
87 int pTable[1 << KF_LOG_TABLE];
88 int pValue[1 << KF_LOG_TABLE];
89 int pPlace[KF_LEAF_MAX];
90 int pList [KF_LEAF_MAX+1];
91 Kf_Cut_t pCuts0[KF_CUT_MAX];
92 Kf_Cut_t pCuts1[KF_CUT_MAX];
93 Kf_Cut_t pCutsR[KF_CUT_MAX*KF_CUT_MAX];
94 Kf_Cut_t * ppCuts[KF_CUT_MAX];
95 Kf_Cut_t * pCutBest;
96 word CutCount[4]; // statistics
97};
98struct Kf_Man_t_
99{
100 Gia_Man_t * pGia; // user's manager
101 Jf_Par_t * pPars; // user's parameters
102 Vec_Set_t pMem; // cut storage
103 Vec_Int_t vCuts; // node params
104 Vec_Int_t vTime; // node params
105 Vec_Flt_t vArea; // node params
106 Vec_Flt_t vRefs; // node params
107 Vec_Int_t * vTemp; // temporary
108 abctime clkStart; // starting time
109 Kf_Set_t pSett[KF_PROC_MAX];
110};
111
112static inline int Kf_SetCutId( Kf_Set_t * p, Kf_Cut_t * pCut ) { return pCut - p->pCutsR; }
113static inline Kf_Cut_t * Kf_SetCut( Kf_Set_t * p, int i ) { return i >= 0 ? p->pCutsR + i : NULL; }
114
115static inline int Kf_ObjTime( Kf_Man_t * p, int i ) { return Vec_IntEntry(&p->vTime, i); }
116static inline float Kf_ObjArea( Kf_Man_t * p, int i ) { return Vec_FltEntry(&p->vArea, i); }
117static inline float Kf_ObjRefs( Kf_Man_t * p, int i ) { return Vec_FltEntry(&p->vRefs, i); }
118
119static inline void Kf_ObjSetCuts( Kf_Man_t * p, int i, Vec_Int_t * vVec ) { Vec_IntWriteEntry(&p->vCuts, i, Vec_SetAppend(&p->pMem, Vec_IntArray(vVec), Vec_IntSize(vVec))); }
120static inline int * Kf_ObjCuts( Kf_Man_t * p, int i ) { return (int *)Vec_SetEntry(&p->pMem, Vec_IntEntry(&p->vCuts, i)); }
121static inline int * Kf_ObjCuts0( Kf_Man_t * p, int i ) { return Kf_ObjCuts(p, Gia_ObjFaninId0(Gia_ManObj(p->pGia, i), i)); }
122static inline int * Kf_ObjCuts1( Kf_Man_t * p, int i ) { return Kf_ObjCuts(p, Gia_ObjFaninId1(Gia_ManObj(p->pGia, i), i)); }
123static inline int * Kf_ObjCutBest( Kf_Man_t * p, int i ) { int * pCuts = Kf_ObjCuts(p, i); return pCuts + pCuts[1]; }
124
125#define Kf_ObjForEachCutInt( pList, pCut, i ) for ( i = 0, pCut = pList + KF_ADD_ON1; i < pList[0]; i++, pCut += pCut[0] + KF_ADD_ON2 )
126#define Kf_ListForEachCut( p, iList, pCut ) for ( pCut = Kf_SetCut(p, p->pList[iList]); pCut; pCut = Kf_SetCut(p, pCut->iNext) )
127#define Kf_ListForEachCutP( p, iList, pCut, pPlace ) for ( pPlace = p->pList+iList, pCut = Kf_SetCut(p, *pPlace); pCut; pCut = Kf_SetCut(p, *pPlace) )
128
132
144static inline int Kf_SetLoadCuts( Kf_Cut_t * pCuts, int * pIntCuts )
145{
146 Kf_Cut_t * pCut;
147 int k, * pIntCut, nCuts = 0;
148 Kf_ObjForEachCutInt( pIntCuts, pIntCut, nCuts )
149 {
150 pCut = pCuts + nCuts;
151 pCut->Sign = 0;
152 pCut->Polar = 0;
153 pCut->iFunc = pIntCut[pIntCut[0] + 1];
154 pCut->Delay = pIntCut[pIntCut[0] + 2];
155 pCut->Area = Abc_Int2Float(pIntCut[pIntCut[0] + 3]);
156 pCut->nLeaves = pIntCut[0];
157 for ( k = 0; k < pIntCut[0]; k++ )
158 {
159 pCut->pLeaves[k] = Abc_Lit2Var(pIntCut[k+1]);
160 pCut->Sign |= ((word)1) << (pCut->pLeaves[k] & 0x3F);
161 if ( Abc_LitIsCompl(pIntCut[k+1]) )
162 pCut->Polar |= (1 << k);
163 }
164 }
165 return nCuts;
166}
167static inline void Kf_SetPrepare( Kf_Set_t * p, int * pCuts0, int * pCuts1 )
168{
169 int i;
170 // prepare hash table
171// for ( i = 0; i <= p->TableMask; i++ )
172// assert( p->pTable[i] == 0 );
173 // prepare cut storage
174 for ( i = 0; i <= p->nLutSize; i++ )
175 p->pList[i] = -1;
176 // transfer cuts
177 p->nCuts0 = Kf_SetLoadCuts( p->pCuts0, pCuts0 );
178 p->nCuts1 = Kf_SetLoadCuts( p->pCuts1, pCuts1 );
179 p->nCuts = 0;
180}
181
193static inline void Kf_ManStoreStart( Vec_Int_t * vTemp, int nCuts )
194{
195 Vec_IntClear( vTemp );
196 Vec_IntPush( vTemp, nCuts ); // cut count
197 Vec_IntPush( vTemp, -1 ); // best offset
198}
199static inline void Kf_ManStoreAddUnit( Vec_Int_t * vTemp, int iObj, int Time, float Area )
200{
201 Vec_IntAddToEntry( vTemp, 0, 1 );
202 Vec_IntPush( vTemp, 1 ); // cut size
203 Vec_IntPush( vTemp, Abc_Var2Lit(iObj, 0) ); // leaf
204 Vec_IntPush( vTemp, 2 ); // function
205 Vec_IntPush( vTemp, Time ); // delay
206 Vec_IntPush( vTemp, Abc_Float2Int(Area) ); // area
207}
208static inline void Kf_ManSaveResults( Kf_Cut_t ** ppCuts, int nCuts, Kf_Cut_t * pCutBest, Vec_Int_t * vTemp )
209{
210 int i, k;
211 assert( nCuts > 0 && nCuts < KF_CUT_MAX );
212 Kf_ManStoreStart( vTemp, nCuts );
213 for ( i = 0; i < nCuts; i++ )
214 {
215 if ( ppCuts[i] == pCutBest )
216 Vec_IntWriteEntry( vTemp, 1, Vec_IntSize(vTemp) );
217 Vec_IntPush( vTemp, ppCuts[i]->nLeaves );
218// Vec_IntPushArray( vTemp, ppCuts[i]->pLeaves, ppCuts[i]->nLeaves );
219 for ( k = 0; k < ppCuts[i]->nLeaves; k++ )
220 Vec_IntPush( vTemp, Abc_Var2Lit(ppCuts[i]->pLeaves[k], 0) );
221 Vec_IntPush( vTemp, ppCuts[i]->iFunc );
222 Vec_IntPush( vTemp, ppCuts[i]->Delay );
223 Vec_IntPush( vTemp, Abc_Float2Int(ppCuts[i]->Area) );
224 }
225 assert( Vec_IntEntry(vTemp, 1) > 0 );
226}
227static inline int Kf_SetCompareCuts( Kf_Cut_t * p1, Kf_Cut_t * p2 )
228{
229 if ( p1 == NULL || p2 == NULL )
230 return (p1 != NULL) - (p2 != NULL);
231 if ( p1->nLeaves != p2->nLeaves )
232 return p1->nLeaves - p2->nLeaves;
233 return memcmp( p1->pLeaves, p2->pLeaves, sizeof(int)*p1->nLeaves );
234}
235static inline void Kf_SetAddToList( Kf_Set_t * p, Kf_Cut_t * pCut, int fSort )
236{
237 if ( !fSort )
238 pCut->iNext = p->pList[pCut->nLeaves], p->pList[pCut->nLeaves] = Kf_SetCutId(p, pCut);
239 else
240 {
241 int Value, * pPlace;
242 Kf_Cut_t * pTemp;
243 Vec_IntSelectSort( pCut->pLeaves, pCut->nLeaves );
244 Kf_ListForEachCutP( p, pCut->nLeaves, pTemp, pPlace )
245 {
246 if ( (Value = Kf_SetCompareCuts(pTemp, pCut)) > 0 )
247 break;
248 assert( Value < 0 );
249 pPlace = &pTemp->iNext;
250 }
251 pCut->iNext = *pPlace, *pPlace = Kf_SetCutId(p, pCut);
252 }
253}
254static inline int Kf_CutCompare( Kf_Cut_t * pCut0, Kf_Cut_t * pCut1, int fArea )
255{
256 if ( fArea )
257 {
258 if ( pCut0->Area < pCut1->Area ) return -1;
259 if ( pCut0->Area > pCut1->Area ) return 1;
260 if ( pCut0->Delay < pCut1->Delay ) return -1;
261 if ( pCut0->Delay > pCut1->Delay ) return 1;
262 if ( pCut0->nLeaves < pCut1->nLeaves ) return -1;
263 if ( pCut0->nLeaves > pCut1->nLeaves ) return 1;
264 }
265 else
266 {
267 if ( pCut0->Delay < pCut1->Delay ) return -1;
268 if ( pCut0->Delay > pCut1->Delay ) return 1;
269 if ( pCut0->nLeaves < pCut1->nLeaves ) return -1;
270 if ( pCut0->nLeaves > pCut1->nLeaves ) return 1;
271 if ( pCut0->Area < pCut1->Area ) return -1;
272 if ( pCut0->Area > pCut1->Area ) return 1;
273 }
274 return 0;
275}
276static inline int Kf_SetStoreAddOne( Kf_Set_t * p, int nCuts, int nCutNum, Kf_Cut_t * pCut, int fArea )
277{
278 int i;
279 p->ppCuts[nCuts] = pCut;
280 if ( nCuts == 0 )
281 return 1;
282 for ( i = nCuts; i > 0; i-- )
283 if ( Kf_CutCompare(p->ppCuts[i-1], p->ppCuts[i], fArea) > 0 )
284 ABC_SWAP( Kf_Cut_t *, p->ppCuts[i-1], p->ppCuts[i] )
285 else
286 break;
287 return Abc_MinInt( nCuts+1, nCutNum );
288}
289static inline void Kf_SetSelectBest( Kf_Set_t * p, int fArea, int fSort )
290{
291// int fArea = p->pMan->pPars->fArea;
292 Kf_Cut_t * pCut;
293 int i, nCuts = 0;
294 for ( i = 0; i <= p->nLutSize; i++ )
295 Kf_ListForEachCut( p, i, pCut )
296 nCuts = Kf_SetStoreAddOne( p, nCuts, p->nCutNum-1, pCut, fArea );
297 assert( nCuts > 0 && nCuts < p->nCutNum );
298 p->nCuts = nCuts;
299 p->pCutBest = p->ppCuts[0];
300 if ( !fSort )
301 return;
302 // sort by size in the reverse order
303 for ( i = 0; i <= p->nLutSize; i++ )
304 p->pList[i] = -1;
305 for ( i = 0; i < nCuts; i++ )
306 Kf_SetAddToList( p, p->ppCuts[i], 0 );
307 p->nCuts = 0;
308 for ( i = p->nLutSize; i >= 0; i-- )
309 Kf_ListForEachCut( p, i, pCut )
310 p->ppCuts[p->nCuts++] = pCut;
311 assert( p->nCuts == nCuts );
312}
313
325static inline int Kf_CheckCut( Kf_Cut_t * pBase, Kf_Cut_t * pCut ) // check if pCut is contained in pBase
326{
327 int nSizeB = pBase->nLeaves;
328 int nSizeC = pCut->nLeaves;
329 int * pB = pBase->pLeaves;
330 int * pC = pCut->pLeaves;
331 int i, k;
332 for ( i = 0; i < nSizeC; i++ )
333 {
334 for ( k = 0; k < nSizeB; k++ )
335 if ( pC[i] == pB[k] )
336 break;
337 if ( k == nSizeB )
338 return 0;
339 }
340 return 1;
341}
342static inline int Kf_CheckCuts( Kf_Set_t * p )
343{
344 Kf_Cut_t * pCut0, * pCut1;
345 int i, k, m, n, Value;
346 assert( p->nCuts > 0 );
347 for ( i = 0; i <= p->nLutSize; i++ )
348 Kf_ListForEachCut( p, i, pCut0 )
349 {
350 // check duplicates
351 for ( m = 0; m < pCut0->nLeaves; m++ )
352 for ( n = m+1; n < pCut0->nLeaves; n++ )
353 assert( pCut0->pLeaves[m] != pCut0->pLeaves[n] );
354 // check pairs
355 for ( k = 0; k <= p->nLutSize; k++ )
356 Kf_ListForEachCut( p, k, pCut1 )
357 {
358 if ( pCut0 == pCut1 )
359 continue;
360 // check containments
361 Value = Kf_CheckCut( pCut0, pCut1 );
362 assert( Value == 0 );
363 }
364 }
365 return 1;
366}
367
379static inline int Kf_HashLookup( Kf_Set_t * p, int i )
380{
381 int k;
382 assert( i > 0 );
383 for ( k = i & p->TableMask; p->pTable[k]; k = (k + 1) & p->TableMask )
384 if ( p->pTable[k] == i )
385 return -1;
386 return k;
387}
388static inline int Kf_HashFindOrAdd( Kf_Set_t * p, int i )
389{
390 int k = Kf_HashLookup( p, i );
391 if ( k == -1 )
392 return 0;
393 if ( p->nTEntries == p->nLutSize )
394 return 1;
395 assert( p->pTable[k] == 0 );
396 p->pTable[k] = i;
397 p->pPlace[p->nTEntries] = k;
398 p->pValue[k] = p->nTEntries++;
399 return 0;
400}
401static inline void Kf_HashPopulate( Kf_Set_t * p, Kf_Cut_t * pCut )
402{
403 int i;
404 assert( p->nTEntries == 0 );
405 for ( i = 0; i < pCut->nLeaves; i++ )
406 Kf_HashFindOrAdd( p, pCut->pLeaves[i] );
407 assert( p->nTEntries == pCut->nLeaves );
408}
409static inline void Kf_HashCleanup( Kf_Set_t * p, int iStart )
410{
411 int i;
412 for ( i = iStart; i < p->nTEntries; i++ )
413 p->pTable[p->pPlace[i]] = 0;
414 p->nTEntries = iStart;
415}
416
428static inline int Kf_SetCountBits( word i )
429{
430 i = i - ((i >> 1) & 0x5555555555555555);
431 i = (i & 0x3333333333333333) + ((i >> 2) & 0x3333333333333333);
432 i = ((i + (i >> 4)) & 0x0F0F0F0F0F0F0F0F);
433 return (i*(0x0101010101010101))>>56;
434}
435static inline word Kf_SetCutGetSign( Kf_Cut_t * p )
436{
437 word Sign = 0; int i;
438 for ( i = 0; i < p->nLeaves; i++ )
439 Sign |= ((word)1) << (p->pLeaves[i] & 0x3F);
440 return Sign;
441}
442// returns 1 if the cut in hash table is dominated by the given one
443static inline int Kf_SetCutDominatedByThis( Kf_Set_t * p, Kf_Cut_t * pCut )
444{
445 int i;
446 for ( i = 0; i < pCut->nLeaves; i++ )
447 if ( Kf_HashLookup(p, pCut->pLeaves[i]) >= 0 )
448 return 0;
449 return 1;
450}
451static inline int Kf_SetRemoveDuplicates( Kf_Set_t * p, int nLeaves, word Sign )
452{
453 Kf_Cut_t * pCut;
454 Kf_ListForEachCut( p, nLeaves, pCut )
455 if ( pCut->Sign == Sign && Kf_SetCutDominatedByThis(p, pCut) )
456 return 1;
457 return 0;
458}
459static inline void Kf_SetFilter( Kf_Set_t * p )
460{
461 Kf_Cut_t * pCut0, * pCut1;
462 int i, k, * pPlace;
463 assert( p->nCuts > 0 );
464 for ( i = 0; i <= p->nLutSize; i++ )
465 Kf_ListForEachCutP( p, i, pCut0, pPlace )
466 {
467 Kf_HashPopulate( p, pCut0 );
468 for ( k = 0; k < pCut0->nLeaves; k++ )
469 Kf_ListForEachCut( p, k, pCut1 )
470 if ( (pCut0->Sign & pCut1->Sign) == pCut1->Sign && Kf_SetCutDominatedByThis(p, pCut1) )
471 { k = pCut0->nLeaves; p->nCuts--; break; }
472 if ( k == pCut0->nLeaves + 1 ) // remove pCut0
473 *pPlace = pCut0->iNext;
474 else
475 pPlace = &pCut0->iNext;
476 Kf_HashCleanup( p, 0 );
477 }
478 assert( p->nCuts > 0 );
479}
480static inline void Kf_SetMergePairs( Kf_Set_t * p, Kf_Cut_t * pCut0, Kf_Cut_t * pCuts, int nCuts, int fArea )
481{
482 Kf_Cut_t * pCut1, * pCutR; int i;
483 Kf_HashPopulate( p, pCut0 );
484 for ( pCut1 = pCuts; pCut1 < pCuts + nCuts; pCut1++ )
485 {
486 if ( pCut0->nLeaves + pCut1->nLeaves > p->nLutSize && Kf_SetCountBits(pCut0->Sign | pCut1->Sign) > p->nLutSize )
487 continue;
488 Kf_HashCleanup( p, pCut0->nLeaves );
489 for ( i = 0; i < pCut1->nLeaves; i++ )
490 if ( Kf_HashFindOrAdd(p, pCut1->pLeaves[i]) )
491 break;
492 if ( i < pCut1->nLeaves )
493 continue;
494 p->CutCount[1]++;
495 if ( Kf_SetRemoveDuplicates(p, p->nTEntries, pCut0->Sign | pCut1->Sign) )
496 continue;
497 // create new cut
498 pCutR = p->pCutsR + p->nCuts++;
499 pCutR->nLeaves = p->nTEntries;
500 for ( i = 0; i < p->nTEntries; i++ )
501 pCutR->pLeaves[i] = p->pTable[p->pPlace[i]];
502 pCutR->Sign = pCut0->Sign | pCut1->Sign;
503 pCutR->Delay = Abc_MaxInt(pCut0->Delay, pCut1->Delay);
504 pCutR->Area = pCut0->Area + pCut1->Area;
505 // add new cut
506 Kf_SetAddToList( p, pCutR, 0 );
507 }
508 Kf_HashCleanup( p, 0 );
509}
510static inline void Kf_SetMerge( Kf_Set_t * p, int * pCuts0, int * pCuts1, int fArea, int fCutMin )
511{
512 int c0, c1;
513 Kf_SetPrepare( p, pCuts0, pCuts1 );
514 p->CutCount[0] += p->nCuts0 * p->nCuts1;
515// for ( c0 = 1; c0 < p->nCuts0; c0++ )
516// assert( p->pCuts0[c0-1].nLeaves >= p->pCuts0[c0].nLeaves );
517 for ( c0 = c1 = 0; c0 < p->nCuts0 && c1 < p->nCuts1; )
518 {
519 if ( p->pCuts0[c0].nLeaves >= p->pCuts1[c1].nLeaves )
520 Kf_SetMergePairs( p, p->pCuts0 + c0++, p->pCuts1 + c1, p->nCuts1 - c1, fArea );
521 else
522 Kf_SetMergePairs( p, p->pCuts1 + c1++, p->pCuts0 + c0, p->nCuts0 - c0, fArea );
523 }
524 p->CutCount[2] += p->nCuts;
525 Kf_SetFilter( p );
526// Kf_CheckCuts( p );
527 p->CutCount[3] += Abc_MinInt( p->nCuts, p->nCutNum-1 );
528 Kf_SetSelectBest( p, fArea, 1 );
529}
530
542static inline int Kf_SetCutIsContainedSimple( Kf_Cut_t * pBase, Kf_Cut_t * pCut ) // check if pCut is contained in pBase
543{
544 int nSizeB = pBase->nLeaves;
545 int nSizeC = pCut->nLeaves;
546 int * pB = pBase->pLeaves;
547 int * pC = pCut->pLeaves;
548 int i, k;
549 assert( nSizeB >= nSizeC );
550 for ( i = 0; i < nSizeC; i++ )
551 {
552 for ( k = 0; k < nSizeB; k++ )
553 if ( pC[i] == pB[k] )
554 break;
555 if ( k == nSizeB )
556 return 0;
557 }
558 return 1;
559}
560static inline int Kf_SetMergeSimpleOne( Kf_Cut_t * pCut0, Kf_Cut_t * pCut1, Kf_Cut_t * pCut, int nLutSize )
561{
562 int nSize0 = pCut0->nLeaves;
563 int nSize1 = pCut1->nLeaves;
564 int * pC0 = pCut0->pLeaves;
565 int * pC1 = pCut1->pLeaves;
566 int * pC = pCut->pLeaves;
567 int i, k, c;
568 // compare two cuts with different numbers
569 c = nSize0;
570 for ( i = 0; i < nSize1; i++ )
571 {
572 for ( k = 0; k < nSize0; k++ )
573 if ( pC1[i] == pC0[k] )
574 break;
575 if ( k < nSize0 )
576 continue;
577 if ( c == nLutSize )
578 return 0;
579 pC[c++] = pC1[i];
580 }
581 for ( i = 0; i < nSize0; i++ )
582 pC[i] = pC0[i];
583 pCut->nLeaves = c;
584 return 1;
585}
586static inline int Kf_SetRemoveDuplicatesSimple( Kf_Set_t * p, Kf_Cut_t * pCutNew )
587{
588 Kf_Cut_t * pCut;
589 Kf_ListForEachCut( p, pCutNew->nLeaves, pCut )
590 if ( pCut->Sign == pCutNew->Sign && Kf_SetCutIsContainedSimple(pCut, pCutNew) )
591 return 1;
592 return 0;
593}
594static inline void Kf_SetFilterSimple( Kf_Set_t * p )
595{
596 Kf_Cut_t * pCut0, * pCut1;
597 int i, k, * pPlace;
598 assert( p->nCuts > 0 );
599 for ( i = 0; i <= p->nLutSize; i++ )
600 Kf_ListForEachCutP( p, i, pCut0, pPlace )
601 {
602 for ( k = 0; k < pCut0->nLeaves; k++ )
603 Kf_ListForEachCut( p, k, pCut1 )
604 if ( (pCut0->Sign & pCut1->Sign) == pCut1->Sign && Kf_SetCutIsContainedSimple(pCut0, pCut1) )
605 { k = pCut0->nLeaves; p->nCuts--; break; }
606 if ( k == pCut0->nLeaves + 1 ) // remove pCut0
607 *pPlace = pCut0->iNext;
608 else
609 pPlace = &pCut0->iNext;
610 }
611 assert( p->nCuts > 0 );
612}
613static inline void Kf_SetMergeSimple( Kf_Set_t * p, int * pCuts0, int * pCuts1, int fArea, int fCutMin )
614{
615 Kf_Cut_t * pCut0, * pCut1, * pCutR;
616 Kf_SetPrepare( p, pCuts0, pCuts1 );
617 p->CutCount[0] += p->nCuts0 * p->nCuts1;
618 for ( pCut0 = p->pCuts0; pCut0 < p->pCuts0 + p->nCuts0; pCut0++ )
619 for ( pCut1 = p->pCuts1; pCut1 < p->pCuts1 + p->nCuts1; pCut1++ )
620 {
621 if ( pCut0->nLeaves + pCut1->nLeaves > p->nLutSize && Kf_SetCountBits(pCut0->Sign | pCut1->Sign) > p->nLutSize )
622 continue;
623 p->CutCount[1]++;
624 pCutR = p->pCutsR + p->nCuts;
625 if ( !Kf_SetMergeSimpleOne(pCut0, pCut1, pCutR, p->nLutSize) )
626 continue;
627 p->CutCount[2]++;
628 pCutR->Sign = pCut0->Sign | pCut1->Sign;
629 if ( Kf_SetRemoveDuplicatesSimple(p, pCutR) )
630 continue;
631 p->nCuts++;
632 if ( fCutMin )
633 {
634 int nOldSupp = pCutR->nLeaves;
635// pCutR->iFunc = Kf_SetComputeTruth( p, pCut0->iFunc, pCut1->iFunc, pCut0, pCut1, pCutR );
636 assert( pCutR->nLeaves <= nOldSupp );
637 if ( pCutR->nLeaves < nOldSupp )
638 pCutR->Sign = Kf_SetCutGetSign( pCutR );
639 // delay and area are inaccurate
640 }
641 assert( pCutR->nLeaves > 1 );
642 pCutR->Delay = Abc_MaxInt(pCut0->Delay, pCut1->Delay);
643 pCutR->Area = pCut0->Area + pCut1->Area;
644 // add new cut
645 Kf_SetAddToList( p, pCutR, 0 );
646 }
647 Kf_SetFilterSimple( p );
648// Kf_CheckCuts( p );
649 p->CutCount[3] += Abc_MinInt( p->nCuts, p->nCutNum-1 );
650 Kf_SetSelectBest( p, fArea, 1 );
651}
652
664static inline int Kf_SetCutIsContainedOrder( Kf_Cut_t * pBase, Kf_Cut_t * pCut ) // check if pCut is contained in pBase
665{
666 int nSizeB = pBase->nLeaves;
667 int nSizeC = pCut->nLeaves;
668 int i, k;
669 if ( nSizeB == nSizeC )
670 {
671 for ( i = 0; i < nSizeB; i++ )
672 if ( pBase->pLeaves[i] != pCut->pLeaves[i] )
673 return 0;
674 return 1;
675 }
676 assert( nSizeB > nSizeC );
677 for ( i = k = 0; i < nSizeB; i++ )
678 {
679 if ( pBase->pLeaves[i] > pCut->pLeaves[k] )
680 return 0;
681 if ( pBase->pLeaves[i] == pCut->pLeaves[k] )
682 {
683 if ( ++k == nSizeC )
684 return 1;
685 }
686 }
687 return 0;
688}
689static inline int Kf_SetMergeOrderOne( Kf_Cut_t * pCut0, Kf_Cut_t * pCut1, Kf_Cut_t * pCut, int nLutSize )
690{
691 int nSize0 = pCut0->nLeaves;
692 int nSize1 = pCut1->nLeaves;
693 int * pC0 = pCut0->pLeaves;
694 int * pC1 = pCut1->pLeaves;
695 int * pC = pCut->pLeaves;
696 int i, k, c;
697 // the case of the largest cut sizes
698 if ( nSize0 == nLutSize && nSize1 == nLutSize )
699 {
700 for ( i = 0; i < nSize0; i++ )
701 {
702 if ( pC0[i] != pC1[i] ) return 0;
703 pC[i] = pC0[i];
704 }
705 pCut->nLeaves = nLutSize;
706 return 1;
707 }
708 // compare two cuts with different numbers
709 i = k = c = 0;
710 while ( 1 )
711 {
712 if ( c == nLutSize ) return 0;
713 if ( pC0[i] < pC1[k] )
714 {
715 pC[c++] = pC0[i++];
716 if ( i >= nSize0 ) goto FlushCut1;
717 }
718 else if ( pC0[i] > pC1[k] )
719 {
720 pC[c++] = pC1[k++];
721 if ( k >= nSize1 ) goto FlushCut0;
722 }
723 else
724 {
725 pC[c++] = pC0[i++]; k++;
726 if ( i >= nSize0 ) goto FlushCut1;
727 if ( k >= nSize1 ) goto FlushCut0;
728 }
729 }
730
731FlushCut0:
732 if ( c + nSize0 > nLutSize + i ) return 0;
733 while ( i < nSize0 )
734 pC[c++] = pC0[i++];
735 pCut->nLeaves = c;
736 return 1;
737
738FlushCut1:
739 if ( c + nSize1 > nLutSize + k ) return 0;
740 while ( k < nSize1 )
741 pC[c++] = pC1[k++];
742 pCut->nLeaves = c;
743 return 1;
744}
745static inline int Kf_SetRemoveDuplicatesOrder( Kf_Set_t * p, Kf_Cut_t * pCutNew )
746{
747 Kf_Cut_t * pCut;
748 Kf_ListForEachCut( p, pCutNew->nLeaves, pCut )
749 if ( pCut->Sign == pCutNew->Sign && Kf_SetCutIsContainedOrder(pCut, pCutNew) )
750 return 1;
751 return 0;
752}
753static inline void Kf_SetFilterOrder( Kf_Set_t * p )
754{
755 Kf_Cut_t * pCut0, * pCut1;
756 int i, k, * pPlace;
757 assert( p->nCuts > 0 );
758 for ( i = 0; i <= p->nLutSize; i++ )
759 Kf_ListForEachCutP( p, i, pCut0, pPlace )
760 {
761 for ( k = 0; k < pCut0->nLeaves; k++ )
762 Kf_ListForEachCut( p, k, pCut1 )
763 if ( (pCut0->Sign & pCut1->Sign) == pCut1->Sign && Kf_SetCutIsContainedOrder(pCut0, pCut1) )
764 { k = pCut0->nLeaves; p->nCuts--; break; }
765 if ( k == pCut0->nLeaves + 1 ) // remove pCut0
766 *pPlace = pCut0->iNext;
767 else
768 pPlace = &pCut0->iNext;
769 }
770 assert( p->nCuts > 0 );
771}
772/*
773int Kf_SetComputeTruth( Kf_Man_t * p, int iFuncLit0, int iFuncLit1, int * pCut0, int * pCut1, int * pCutOut )
774{
775 word uTruth[JF_WORD_MAX], uTruth0[JF_WORD_MAX], uTruth1[JF_WORD_MAX];
776 int fCompl, truthId;
777 int LutSize = p->pPars->nLutSize;
778 int nWords = Abc_Truth6WordNum(p->pPars->nLutSize);
779 word * pTruth0 = Vec_MemReadEntry(p->vTtMem, Abc_Lit2Var(iFuncLit0));
780 word * pTruth1 = Vec_MemReadEntry(p->vTtMem, Abc_Lit2Var(iFuncLit1));
781 Abc_TtCopy( uTruth0, pTruth0, nWords, Abc_LitIsCompl(iFuncLit0) );
782 Abc_TtCopy( uTruth1, pTruth1, nWords, Abc_LitIsCompl(iFuncLit1) );
783 Abc_TtExpand( uTruth0, LutSize, pCut0 + 1, Kf_CutSize(pCut0), pCutOut + 1, Kf_CutSize(pCutOut) );
784 Abc_TtExpand( uTruth1, LutSize, pCut1 + 1, Kf_CutSize(pCut1), pCutOut + 1, Kf_CutSize(pCutOut) );
785 fCompl = (int)(uTruth0[0] & uTruth1[0] & 1);
786 Abc_TtAnd( uTruth, uTruth0, uTruth1, nWords, fCompl );
787 pCutOut[0] = Abc_TtMinBase( uTruth, pCutOut + 1, pCutOut[0], LutSize );
788 assert( (uTruth[0] & 1) == 0 );
789 truthId = Vec_MemHashInsert(p->vTtMem, uTruth);
790 return Abc_Var2Lit( truthId, fCompl );
791}
792*/
793static inline void Kf_SetMergeOrder( Kf_Set_t * p, int * pCuts0, int * pCuts1, int fArea, int fCutMin )
794{
795 Kf_Cut_t * pCut0, * pCut1, * pCutR;
796 Kf_SetPrepare( p, pCuts0, pCuts1 );
797 p->CutCount[0] += p->nCuts0 * p->nCuts1;
798 for ( pCut0 = p->pCuts0; pCut0 < p->pCuts0 + p->nCuts0; pCut0++ )
799 for ( pCut1 = p->pCuts1; pCut1 < p->pCuts1 + p->nCuts1; pCut1++ )
800 {
801 if ( pCut0->nLeaves + pCut1->nLeaves > p->nLutSize && Kf_SetCountBits(pCut0->Sign | pCut1->Sign) > p->nLutSize )
802 continue;
803 p->CutCount[1]++;
804 pCutR = p->pCutsR + p->nCuts;
805 if ( !Kf_SetMergeOrderOne(pCut0, pCut1, pCutR, p->nLutSize) )
806 continue;
807 p->CutCount[2]++;
808 pCutR->Sign = pCut0->Sign | pCut1->Sign;
809 if ( Kf_SetRemoveDuplicatesOrder(p, pCutR) )
810 continue;
811 p->nCuts++;
812 if ( fCutMin )
813 {
814 int nOldSupp = pCutR->nLeaves;
815// pCutR->iFunc = Kf_SetComputeTruth( p, pCut0->iFunc, pCut1->iFunc, pCut0, pCut1, pCutR );
816 assert( pCutR->nLeaves <= nOldSupp );
817 if ( pCutR->nLeaves < nOldSupp )
818 pCutR->Sign = Kf_SetCutGetSign( pCutR );
819 // delay and area are inaccurate
820 }
821 assert( pCutR->nLeaves > 1 );
822 pCutR->Delay = Abc_MaxInt(pCut0->Delay, pCut1->Delay);
823 pCutR->Area = pCut0->Area + pCut1->Area;
824 // add new cut
825 Kf_SetAddToList( p, pCutR, 0 );
826 }
827 Kf_SetFilterOrder( p );
828// Kf_CheckCuts( p );
829 p->CutCount[3] += Abc_MinInt( p->nCuts, p->nCutNum-1 );
830 Kf_SetSelectBest( p, fArea, 1 );
831}
832
833
845static inline int Kf_CutSize( int * pCut ) { return pCut[0]; }
846static inline int Kf_CutFunc( int * pCut ) { return pCut[pCut[0] + 1]; }
847static inline int Kf_CutLeaf( int * pCut, int i ) { assert(i); return Abc_Lit2Var(pCut[i]); }
848static inline int Kf_CutTime( Kf_Man_t * p, int * pCut )
849{
850 int i, Time = 0;
851 for ( i = 1; i <= Kf_CutSize(pCut); i++ )
852 Time = Abc_MaxInt( Time, Kf_ObjTime(p, Kf_CutLeaf(pCut, i)) );
853 return Time + 1;
854}
855static inline void Kf_CutRef( Kf_Man_t * p, int * pCut )
856{
857 int i;
858 for ( i = 1; i <= Kf_CutSize(pCut); i++ )
859 Gia_ObjRefIncId( p->pGia, Kf_CutLeaf(pCut, i) );
860}
861static inline void Kf_CutDeref( Kf_Man_t * p, int * pCut )
862{
863 int i;
864 for ( i = 1; i <= Kf_CutSize(pCut); i++ )
865 Gia_ObjRefDecId( p->pGia, Kf_CutLeaf(pCut, i) );
866}
867static inline void Kf_CutPrint( int * pCut )
868{
869 int i;
870 printf( "%d {", Kf_CutSize(pCut) );
871 for ( i = 1; i <= Kf_CutSize(pCut); i++ )
872 printf( " %d", Kf_CutLeaf(pCut, i) );
873 printf( " } Func = %d\n", Kf_CutFunc(pCut) );
874}
875static inline void Gia_CutSetPrint( int * pCuts )
876{
877 int i, * pCut;
878 Kf_ObjForEachCutInt( pCuts, pCut, i )
879 Kf_CutPrint( pCut );
880 printf( "\n" );
881}
882
894int Kf_ManComputeDelay( Kf_Man_t * p, int fEval )
895{
896 Gia_Obj_t * pObj;
897 int i, Delay = 0;
898 if ( fEval )
899 {
900 Gia_ManForEachAnd( p->pGia, pObj, i )
901 if ( Gia_ObjRefNum(p->pGia, pObj) > 0 )
902 Vec_IntWriteEntry( &p->vTime, i, Kf_CutTime(p, Kf_ObjCutBest(p, i)) );
903 }
904 Gia_ManForEachCoDriver( p->pGia, pObj, i )
905 {
906 assert( Gia_ObjRefNum(p->pGia, pObj) > 0 );
907 Delay = Abc_MaxInt( Delay, Kf_ObjTime(p, Gia_ObjId(p->pGia, pObj)) );
908 }
909 return Delay;
910}
911int Kf_ManComputeRefs( Kf_Man_t * p )
912{
913 Gia_Obj_t * pObj;
914 float nRefsNew; int i, * pCut;
915 float * pRefs = Vec_FltArray(&p->vRefs);
916 float * pFlow = Vec_FltArray(&p->vArea);
917 assert( p->pGia->pRefs != NULL );
918 memset( p->pGia->pRefs, 0, sizeof(int) * Gia_ManObjNum(p->pGia) );
919 p->pPars->Area = p->pPars->Edge = 0;
920 Gia_ManForEachObjReverse( p->pGia, pObj, i )
921 {
922 if ( Gia_ObjIsCo(pObj) || Gia_ObjIsBuf(pObj) )
923 Gia_ObjRefInc( p->pGia, Gia_ObjFanin0(pObj) );
924 else if ( Gia_ObjIsAnd(pObj) && Gia_ObjRefNum(p->pGia, pObj) > 0 )
925 {
926 pCut = Kf_ObjCutBest(p, i);
927 Kf_CutRef( p, pCut );
928 p->pPars->Edge += Kf_CutSize(pCut);
929 p->pPars->Area++;
930 }
931 }
932 // blend references and normalize flow
933 for ( i = 0; i < Gia_ManObjNum(p->pGia); i++ )
934 {
935 if ( p->pPars->fOptEdge )
936 nRefsNew = Abc_MaxFloat( 1, 0.8 * pRefs[i] + 0.2 * p->pGia->pRefs[i] );
937 else
938 nRefsNew = Abc_MaxFloat( 1, 0.2 * pRefs[i] + 0.8 * p->pGia->pRefs[i] );
939 pFlow[i] = pFlow[i] * pRefs[i] / nRefsNew;
940 pRefs[i] = nRefsNew;
941 assert( pFlow[i] >= 0 );
942 }
943 // compute delay
944 p->pPars->Delay = Kf_ManComputeDelay( p, 1 );
945 return p->pPars->Area;
946}
947
959#define PAR_THR_MAX 100
960typedef struct Kf_ThData_t_
961{
962 Kf_Set_t * pSett;
963 int Id;
964 int Status;
965 abctime clkUsed;
966} Kf_ThData_t;
967void * Kf_WorkerThread( void * pArg )
968{
969 Kf_ThData_t * pThData = (Kf_ThData_t *)pArg;
970 Kf_Man_t * pMan = pThData->pSett->pMan;
971 int fAreaOnly = pThData->pSett->pMan->pPars->fAreaOnly;
972 int fCutMin = pThData->pSett->pMan->pPars->fCutMin;
973 volatile int * pPlace = &pThData->Status;
974 abctime clk;
975 while ( 1 )
976 {
977 while ( *pPlace == 0 );
978 assert( pThData->Status == 1 );
979 if ( pThData->Id == -1 )
980 {
981 pthread_exit( NULL );
982 assert( 0 );
983 return NULL;
984 }
985 assert( pThData->Id >= 0 );
986 clk = Abc_Clock();
987 Kf_SetMergeOrder( pThData->pSett, Kf_ObjCuts0(pMan, pThData->Id), Kf_ObjCuts1(pMan, pThData->Id), fAreaOnly, fCutMin );
988 pThData->clkUsed += Abc_Clock() - clk;
989 pThData->Status = 0;
990// printf( "Finished object %d\n", pThData->Id );
991 }
992 assert( 0 );
993 return NULL;
994}
995Vec_Int_t * Kf_ManCreateFaninCounts( Gia_Man_t * p )
996{
997 Vec_Int_t * vCounts;
998 Gia_Obj_t * pObj; int i;
999 vCounts = Vec_IntAlloc( Gia_ManObjNum(p) );
1000 Gia_ManForEachObj( p, pObj, i )
1001 {
1002 if ( Gia_ObjIsAnd(pObj) )
1003 Vec_IntPush( vCounts, 2 - Gia_ObjIsCi(Gia_ObjFanin0(pObj)) - Gia_ObjIsCi(Gia_ObjFanin1(pObj)) );
1004 else
1005 Vec_IntPush( vCounts, 0 );
1006 }
1007 assert( Vec_IntSize(vCounts) == Gia_ManObjNum(p) );
1008 return vCounts;
1009}
1010void Kf_ManComputeCuts( Kf_Man_t * p )
1011{
1012 pthread_t WorkerThread[PAR_THR_MAX];
1013 Kf_ThData_t ThData[PAR_THR_MAX];
1014 Vec_Int_t * vStack, * vFanins;
1015 Gia_Obj_t * pObj;
1016 int nProcs = p->pPars->nProcNum;
1017 int i, k, iFan, status, nCountFanins, fRunning;
1018 abctime clk, clkUsed = 0;
1019 assert( nProcs <= PAR_THR_MAX );
1020 // start fanins
1021 vFanins = Kf_ManCreateFaninCounts( p->pGia );
1022 Gia_ManStaticFanoutStart( p->pGia );
1023 // start the stack
1024 vStack = Vec_IntAlloc( 1000 );
1025 Gia_ManForEachObjReverse( p->pGia, pObj, k )
1026 if ( Gia_ObjIsAnd(pObj) && Vec_IntEntry(vFanins, k) == 0 )
1027 Vec_IntPush( vStack, k );
1028 // start the threads
1029 for ( i = 0; i < nProcs; i++ )
1030 {
1031 ThData[i].pSett = p->pSett + i;
1032 ThData[i].Id = -1;
1033 ThData[i].Status = 0;
1034 ThData[i].clkUsed = 0;
1035 status = pthread_create( WorkerThread + i, NULL, Kf_WorkerThread, (void *)(ThData + i) ); assert( status == 0 );
1036 }
1037 nCountFanins = Vec_IntSum(vFanins);
1038 fRunning = 1;
1039 while ( nCountFanins > 0 || Vec_IntSize(vStack) > 0 || fRunning )
1040 {
1041 for ( i = 0; i < nProcs; i++ )
1042 {
1043 if ( ThData[i].Status )
1044 continue;
1045 assert( ThData[i].Status == 0 );
1046 if ( ThData[i].Id >= 0 )
1047 {
1048 int iObj = ThData[i].Id;
1049 Kf_Set_t * pSett = p->pSett + i;
1050 //printf( "Closing obj %d with Thread %d:\n", iObj, i );
1051 clk = Abc_Clock();
1052 // finalize the results
1053 Kf_ManSaveResults( pSett->ppCuts, pSett->nCuts, pSett->pCutBest, p->vTemp );
1054 Vec_IntWriteEntry( &p->vTime, iObj, pSett->pCutBest->Delay + 1 );
1055 Vec_FltWriteEntry( &p->vArea, iObj, (pSett->pCutBest->Area + 1)/Kf_ObjRefs(p, iObj) );
1056 if ( pSett->pCutBest->nLeaves > 1 )
1057 Kf_ManStoreAddUnit( p->vTemp, iObj, Kf_ObjTime(p, iObj), Kf_ObjArea(p, iObj) );
1058 Kf_ObjSetCuts( p, iObj, p->vTemp );
1059 //Gia_CutSetPrint( Kf_ObjCuts(p, iObj) );
1060 clkUsed += Abc_Clock() - clk;
1061 // schedule other nodes
1062 Gia_ObjForEachFanoutStaticId( p->pGia, iObj, iFan, k )
1063 {
1064 if ( !Gia_ObjIsAnd(Gia_ManObj(p->pGia, iFan)) )
1065 continue;
1066 assert( Vec_IntEntry(vFanins, iFan) > 0 );
1067 if ( Vec_IntAddToEntry(vFanins, iFan, -1) == 0 )
1068 Vec_IntPush( vStack, iFan );
1069 assert( nCountFanins > 0 );
1070 nCountFanins--;
1071 }
1072 ThData[i].Id = -1;
1073 }
1074 if ( Vec_IntSize(vStack) > 0 )
1075 {
1076 ThData[i].Id = Vec_IntPop( vStack );
1077 ThData[i].Status = 1;
1078 //printf( "Scheduling %d for Thread %d\n", ThData[i].Id, i );
1079 }
1080 }
1081 fRunning = 0;
1082 for ( i = 0; i < nProcs; i++ )
1083 if ( ThData[i].Status == 1 || (ThData[i].Status == 0 && ThData[i].Id >= 0) )
1084 fRunning = 1;
1085// printf( "fRunning %d\n", fRunning );
1086 }
1087 Vec_IntForEachEntry( vFanins, iFan, k )
1088 if ( iFan != 0 )
1089 {
1090 printf( "%d -> %d ", k, iFan );
1091 Gia_ObjPrint( p->pGia, Gia_ManObj(p->pGia, k) );
1092 }
1093 assert( Vec_IntSum(vFanins) == 0 );
1094 // stop the threads
1095 for ( i = 0; i < nProcs; i++ )
1096 {
1097 assert( ThData[i].Status == 0 );
1098 ThData[i].Id = -1;
1099 ThData[i].Status = 1;
1100 }
1101 Gia_ManStaticFanoutStop( p->pGia );
1102 Vec_IntFree( vStack );
1103 Vec_IntFree( vFanins );
1104 if ( !p->pPars->fVerbose )
1105 return;
1106 // print runtime statistics
1107 printf( "Main : " );
1108 Abc_PrintTime( 1, "Time", clkUsed );
1109 for ( i = 0; i < nProcs; i++ )
1110 {
1111 printf( "Thread %d : ", i );
1112 Abc_PrintTime( 1, "Time", ThData[i].clkUsed );
1113 }
1114
1115}
1116
1128void Kf_ManPrintStats( Kf_Man_t * p, char * pTitle )
1129{
1130 if ( !p->pPars->fVerbose )
1131 return;
1132 printf( "%s : ", pTitle );
1133 printf( "Level =%6lu ", (long)p->pPars->Delay );
1134 printf( "Area =%9lu ", (long)p->pPars->Area );
1135 printf( "Edge =%9lu ", (long)p->pPars->Edge );
1136 Abc_PrintTime( 1, "Time", Abc_Clock() - p->clkStart );
1137 fflush( stdout );
1138}
1139void Kf_ManComputeMapping( Kf_Man_t * p )
1140{
1141 Gia_Obj_t * pObj; int i, iPi;
1142 if ( p->pPars->fVerbose )
1143 {
1144 printf( "Aig: CI = %d CO = %d AND = %d ", Gia_ManCiNum(p->pGia), Gia_ManCoNum(p->pGia), Gia_ManAndNum(p->pGia) );
1145 printf( "LutSize = %d CutMax = %d Threads = %d\n", p->pPars->nLutSize, p->pPars->nCutNum, p->pPars->nProcNum );
1146 printf( "Computing cuts...\r" );
1147 fflush( stdout );
1148 }
1149 Gia_ManForEachCi( p->pGia, pObj, iPi )
1150 {
1151 i = Gia_ObjId(p->pGia, pObj);
1152 Kf_ManStoreStart( p->vTemp, 0 );
1153 Kf_ManStoreAddUnit( p->vTemp, i, 0, 0 );
1154 assert( Vec_IntSize(p->vTemp) == 1 + KF_ADD_ON1 + KF_ADD_ON2 );
1155 Kf_ObjSetCuts( p, i, p->vTemp );
1156 }
1157 if ( p->pPars->nProcNum > 0 )
1158 Kf_ManComputeCuts( p );
1159 else
1160 {
1161 Gia_ManForEachAnd( p->pGia, pObj, i )
1162 {
1163 if ( p->pPars->fCutHashing )
1164 Kf_SetMerge( p->pSett, Kf_ObjCuts0(p, i), Kf_ObjCuts1(p, i), p->pPars->fAreaOnly, p->pPars->fCutMin );
1165 else if ( p->pPars->fCutSimple )
1166 Kf_SetMergeSimple( p->pSett, Kf_ObjCuts0(p, i), Kf_ObjCuts1(p, i), p->pPars->fAreaOnly, p->pPars->fCutMin );
1167 else
1168 Kf_SetMergeOrder( p->pSett, Kf_ObjCuts0(p, i), Kf_ObjCuts1(p, i), p->pPars->fAreaOnly, p->pPars->fCutMin );
1169 Kf_ManSaveResults( p->pSett->ppCuts, p->pSett->nCuts, p->pSett->pCutBest, p->vTemp );
1170 Vec_IntWriteEntry( &p->vTime, i, p->pSett->pCutBest->Delay + 1 );
1171 Vec_FltWriteEntry( &p->vArea, i, (p->pSett->pCutBest->Area + 1)/Kf_ObjRefs(p, i) );
1172 if ( p->pSett->pCutBest->nLeaves > 1 )
1173 Kf_ManStoreAddUnit( p->vTemp, i, Kf_ObjTime(p, i), Kf_ObjArea(p, i) );
1174 Kf_ObjSetCuts( p, i, p->vTemp );
1175 //Gia_CutSetPrint( Kf_ObjCuts(p, i) );
1176 }
1177 }
1178 Kf_ManComputeRefs( p );
1179 if ( p->pPars->fVerbose )
1180 {
1181 printf( "CutPair = %lu ", (long)p->pSett->CutCount[0] );
1182 printf( "Merge = %lu ", (long)p->pSett->CutCount[1] );
1183 printf( "Eval = %lu ", (long)p->pSett->CutCount[2] );
1184 printf( "Cut = %lu ", (long)p->pSett->CutCount[3] );
1185 Abc_PrintTime( 1, "Time", Abc_Clock() - p->clkStart );
1186 printf( "Memory: " );
1187 printf( "Gia = %.2f MB ", Gia_ManMemory(p->pGia) / (1<<20) );
1188 printf( "Man = %.2f MB ", 4.0 * sizeof(int) * Gia_ManObjNum(p->pGia) / (1<<20) );
1189 printf( "Cuts = %.2f MB ",Vec_ReportMemory(&p->pMem) / (1<<20) );
1190 printf( "Set = %.2f KB ", 1.0 * sizeof(Kf_Set_t) / (1<<10) );
1191 printf( "\n" );
1192 fflush( stdout );
1193 Kf_ManPrintStats( p, "Start" );
1194 }
1195}
1196
1208void Kf_ManSetInitRefs( Gia_Man_t * p, Vec_Flt_t * vRefs )
1209{
1210 Gia_Obj_t * pObj, * pCtrl, * pData0, * pData1; int i;
1211 Vec_FltFill( vRefs, Gia_ManObjNum(p), 0 );
1212 Gia_ManForEachAnd( p, pObj, i )
1213 {
1214 Vec_FltAddToEntry( vRefs, Gia_ObjFaninId0(pObj, i), 1 );
1215 Vec_FltAddToEntry( vRefs, Gia_ObjFaninId1(pObj, i), 1 );
1216 if ( !Gia_ObjIsMuxType(pObj) )
1217 continue;
1218 // discount XOR/MUX
1219 pCtrl = Gia_ObjRecognizeMux( pObj, &pData1, &pData0 );
1220 Vec_FltAddToEntry( vRefs, Gia_ObjId(p, Gia_Regular(pCtrl)), -1 );
1221 if ( Gia_Regular(pData0) == Gia_Regular(pData1) )
1222 Vec_FltAddToEntry( vRefs, Gia_ObjId(p, Gia_Regular(pData0)), -1 );
1223 }
1224 Gia_ManForEachCo( p, pObj, i )
1225 Vec_FltAddToEntry( vRefs, Gia_ObjFaninId0(pObj, Gia_ObjId(p, pObj)), 1 );
1226 for ( i = 0; i < Gia_ManObjNum(p); i++ )
1227 Vec_FltUpdateEntry( vRefs, i, 1 );
1228}
1229Kf_Man_t * Kf_ManAlloc( Gia_Man_t * pGia, Jf_Par_t * pPars )
1230{
1231 Kf_Man_t * p; int i;
1232 assert( pPars->nLutSize <= KF_LEAF_MAX );
1233 assert( pPars->nCutNum <= KF_CUT_MAX );
1234 assert( pPars->nProcNum <= KF_PROC_MAX );
1235 Vec_IntFreeP( &pGia->vMapping );
1236 p = ABC_CALLOC( Kf_Man_t, 1 );
1237 p->clkStart = Abc_Clock();
1238 p->pGia = pGia;
1239 p->pPars = pPars;
1240 Vec_SetAlloc_( &p->pMem, 20 );
1241 Vec_IntFill( &p->vCuts, Gia_ManObjNum(pGia), 0 );
1242 Vec_IntFill( &p->vTime, Gia_ManObjNum(pGia), 0 );
1243 Vec_FltFill( &p->vArea, Gia_ManObjNum(pGia), 0 );
1244 Kf_ManSetInitRefs( pGia, &p->vRefs );
1245 p->vTemp = Vec_IntAlloc( 1000 );
1246 pGia->pRefs = ABC_CALLOC( int, Gia_ManObjNum(pGia) );
1247 // prepare cut sets
1248 for ( i = 0; i < Abc_MaxInt(1, pPars->nProcNum); i++ )
1249 {
1250 (p->pSett + i)->pMan = p;
1251 (p->pSett + i)->nLutSize = (unsigned short)pPars->nLutSize;
1252 (p->pSett + i)->nCutNum = (unsigned short)pPars->nCutNum;
1253 (p->pSett + i)->TableMask = (1 << KF_LOG_TABLE) - 1;
1254 }
1255 return p;
1256}
1257void Kf_ManFree( Kf_Man_t * p )
1258{
1259 ABC_FREE( p->pGia->pRefs );
1260 ABC_FREE( p->vCuts.pArray );
1261 ABC_FREE( p->vTime.pArray );
1262 ABC_FREE( p->vArea.pArray );
1263 ABC_FREE( p->vRefs.pArray );
1264 Vec_IntFreeP( &p->vTemp );
1265 Vec_SetFree_( &p->pMem );
1266 ABC_FREE( p );
1267}
1268Gia_Man_t * Kf_ManDerive( Kf_Man_t * p )
1269{
1270 Vec_Int_t * vMapping;
1271 Gia_Obj_t * pObj;
1272 int i, k, * pCut;
1273 assert( !p->pPars->fCutMin );
1274 vMapping = Vec_IntAlloc( Gia_ManObjNum(p->pGia) + (int)p->pPars->Edge + (int)p->pPars->Area * 2 );
1275 Vec_IntFill( vMapping, Gia_ManObjNum(p->pGia), 0 );
1276 Gia_ManForEachAnd( p->pGia, pObj, i )
1277 {
1278 if ( Gia_ObjIsBuf(pObj) || Gia_ObjRefNum(p->pGia, pObj) == 0 )
1279 continue;
1280 pCut = Kf_ObjCutBest( p, i );
1281 Vec_IntWriteEntry( vMapping, i, Vec_IntSize(vMapping) );
1282 Vec_IntPush( vMapping, Kf_CutSize(pCut) );
1283 for ( k = 1; k <= Kf_CutSize(pCut); k++ )
1284 Vec_IntPush( vMapping, Kf_CutLeaf(pCut, k) );
1285 Vec_IntPush( vMapping, i );
1286 }
1287 assert( Vec_IntCap(vMapping) == 16 || Vec_IntSize(vMapping) == Vec_IntCap(vMapping) );
1288 p->pGia->vMapping = vMapping;
1289// Gia_ManMappingVerify( p->pGia );
1290 return p->pGia;
1291}
1292
1304void Kf_ManSetDefaultPars( Jf_Par_t * pPars )
1305{
1306 memset( pPars, 0, sizeof(Jf_Par_t) );
1307 pPars->nLutSize = 6;
1308 pPars->nCutNum = 8;
1309 pPars->nProcNum = 0;
1310 pPars->nRounds = 1;
1311 pPars->nVerbLimit = 5;
1312 pPars->DelayTarget = -1;
1313 pPars->fAreaOnly = 0;
1314 pPars->fOptEdge = 1;
1315 pPars->fCoarsen = 0;
1316 pPars->fCutMin = 0;
1317 pPars->fFuncDsd = 0;
1318 pPars->fGenCnf = 0;
1319 pPars->fPureAig = 0;
1320 pPars->fCutHashing = 0;
1321 pPars->fCutSimple = 0;
1322 pPars->fVerbose = 0;
1323 pPars->fVeryVerbose = 0;
1324 pPars->nLutSizeMax = KF_LEAF_MAX;
1325 pPars->nCutNumMax = KF_CUT_MAX;
1326 pPars->nProcNumMax = KF_PROC_MAX;
1327}
1328Gia_Man_t * Kf_ManPerformMapping( Gia_Man_t * pGia, Jf_Par_t * pPars )
1329{
1330 Kf_Man_t * p;
1331 Gia_Man_t * pNew;
1332 p = Kf_ManAlloc( pGia, pPars );
1333 Kf_ManComputeMapping( p );
1334 pNew = Kf_ManDerive( p );
1335 Kf_ManFree( p );
1336 return pNew;
1337}
1338
1342
1343#endif // pthreads are used
1344
1345ABC_NAMESPACE_IMPL_END
1346
ABC_SWAP
#define ABC_SWAP(Type, a, b)
Definition abc_global.h:253
abctime
ABC_INT64_T abctime
Definition abc_global.h:332
ABC_CALLOC
#define ABC_CALLOC(type, num)
Definition abc_global.h:265
ABC_FREE
#define ABC_FREE(obj)
Definition abc_global.h:267
ABC_NAMESPACE_IMPL_START
#define ABC_NAMESPACE_IMPL_START
Definition abc_namespaces.h:54
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition abc_namespaces.h:55
Vec_Int_t
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition bblif.c:37
PAR_THR_MAX
#define PAR_THR_MAX
DECLARATIONS ///.
Definition bmcBmcG.c:31
p
Cube * p
Definition exorList.c:222
Kf_ManSetDefaultPars
ABC_NAMESPACE_IMPL_START void Kf_ManSetDefaultPars(Jf_Par_t *pPars)
DECLARATIONS ///.
Definition giaKf.c:48
Kf_ManPerformMapping
Gia_Man_t * Kf_ManPerformMapping(Gia_Man_t *pGia, Jf_Par_t *pPars)
Definition giaKf.c:49
Gia_ManStaticFanoutStart
void Gia_ManStaticFanoutStart(Gia_Man_t *p)
Definition giaFanout.c:238
Gia_ManStaticFanoutStop
void Gia_ManStaticFanoutStop(Gia_Man_t *p)
Definition giaFanout.c:393
Gia_ManMemory
double Gia_ManMemory(Gia_Man_t *p)
Definition giaMan.c:194
Gia_ObjRecognizeMux
Gia_Obj_t * Gia_ObjRecognizeMux(Gia_Obj_t *pNode, Gia_Obj_t **ppNodeT, Gia_Obj_t **ppNodeE)
Definition giaUtil.c:1056
Gia_ManForEachAnd
#define Gia_ManForEachAnd(p, pObj, i)
Definition gia.h:1214
Gia_ManForEachObjReverse
#define Gia_ManForEachObjReverse(p, pObj, i)
Definition gia.h:1206
Gia_Obj_t
struct Gia_Obj_t_ Gia_Obj_t
Definition gia.h:76
Gia_ObjIsMuxType
int Gia_ObjIsMuxType(Gia_Obj_t *pNode)
Definition giaUtil.c:982
Gia_ObjPrint
void Gia_ObjPrint(Gia_Man_t *p, Gia_Obj_t *pObj)
Definition giaUtil.c:1456
Gia_Man_t
struct Gia_Man_t_ Gia_Man_t
Definition gia.h:96
Jf_Par_t
struct Jf_Par_t_ Jf_Par_t
Definition gia.h:333
Gia_ObjForEachFanoutStaticId
#define Gia_ObjForEachFanoutStaticId(p, Id, FanId, i)
Definition gia.h:1127
Gia_ManForEachObj
#define Gia_ManForEachObj(p, pObj, i)
MACRO DEFINITIONS ///.
Definition gia.h:1190
Gia_ManForEachCo
#define Gia_ManForEachCo(p, pObj, i)
Definition gia.h:1236
Gia_ManForEachCi
#define Gia_ManForEachCi(p, pObj, i)
Definition gia.h:1228
Gia_ManForEachCoDriver
#define Gia_ManForEachCoDriver(p, pObj, i)
Definition gia.h:1244
word
unsigned __int64 word
DECLARATIONS ///.
Definition kitPerm.c:36
Gia_Man_t_::vMapping
Vec_Int_t * vMapping
Definition gia.h:136
Gia_Man_t_::pRefs
int * pRefs
Definition gia.h:118
Jf_Par_t_::nProcNumMax
int nProcNumMax
Definition gia.h:374
Jf_Par_t_::nRounds
int nRounds
Definition gia.h:339
Jf_Par_t_::fGenCnf
int fGenCnf
Definition gia.h:360
Jf_Par_t_::fFuncDsd
int fFuncDsd
Definition gia.h:359
Jf_Par_t_::fCutSimple
int fCutSimple
Definition gia.h:368
Jf_Par_t_::nProcNum
int nProcNum
Definition gia.h:338
Jf_Par_t_::nCutNum
int nCutNum
Definition gia.h:337
Jf_Par_t_::fOptEdge
int fOptEdge
Definition gia.h:354
Jf_Par_t_::fAreaOnly
int fAreaOnly
Definition gia.h:350
Jf_Par_t_::nCutNumMax
int nCutNumMax
Definition gia.h:373
Jf_Par_t_::fCoarsen
int fCoarsen
Definition gia.h:357
Jf_Par_t_::nLutSizeMax
int nLutSizeMax
Definition gia.h:372
Jf_Par_t_::nLutSize
int nLutSize
Definition gia.h:336
Jf_Par_t_::fVeryVerbose
int fVeryVerbose
Definition gia.h:371
Jf_Par_t_::fCutMin
int fCutMin
Definition gia.h:358
Jf_Par_t_::fPureAig
int fPureAig
Definition gia.h:365
Jf_Par_t_::fCutHashing
int fCutHashing
Definition gia.h:367
Jf_Par_t_::fVerbose
int fVerbose
Definition gia.h:370
Jf_Par_t_::nVerbLimit
int nVerbLimit
Definition gia.h:345
Jf_Par_t_::DelayTarget
int DelayTarget
Definition gia.h:349
assert
#define assert(ex)
Definition util_old.h:213
memset
char * memset()
memcmp
int memcmp()
Vec_Flt_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Flt_t_ Vec_Flt_t
INCLUDES ///.
Definition vecFlt.h:42
Vec_IntForEachEntry
#define Vec_IntForEachEntry(vVec, Entry, i)
MACRO DEFINITIONS ///.
Definition vecInt.h:54
Vec_Set_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Set_t_ Vec_Set_t
INCLUDES ///.
Definition vecSet.h:49