1 /**CFile****************************************************************
2
3 FileName [lpkCut.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Fast Boolean matching for LUT structures.]
8
9 Synopsis []
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - April 28, 2007.]
16
17 Revision [$Id: lpkCut.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "lpkInt.h"
22 #include "bool/kit/cloud.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 [Computes the truth table of one cut.]
38
39 Description []
40
41 SideEffects []
42
43 SeeAlso []
44
45 ***********************************************************************/
Lpk_CutTruthBdd_rec(CloudManager * dd,Hop_Man_t * pMan,Hop_Obj_t * pObj,int nVars)46 CloudNode * Lpk_CutTruthBdd_rec( CloudManager * dd, Hop_Man_t * pMan, Hop_Obj_t * pObj, int nVars )
47 {
48 CloudNode * pTruth, * pTruth0, * pTruth1;
49 assert( !Hop_IsComplement(pObj) );
50 if ( pObj->pData )
51 {
52 assert( ((unsigned)(ABC_PTRUINT_T)pObj->pData) & 0xffff0000 );
53 return (CloudNode *)pObj->pData;
54 }
55 // get the plan for a new truth table
56 if ( Hop_ObjIsConst1(pObj) )
57 pTruth = dd->one;
58 else
59 {
60 assert( Hop_ObjIsAnd(pObj) );
61 // compute the truth tables of the fanins
62 pTruth0 = Lpk_CutTruthBdd_rec( dd, pMan, Hop_ObjFanin0(pObj), nVars );
63 pTruth1 = Lpk_CutTruthBdd_rec( dd, pMan, Hop_ObjFanin1(pObj), nVars );
64 pTruth0 = Cloud_NotCond( pTruth0, Hop_ObjFaninC0(pObj) );
65 pTruth1 = Cloud_NotCond( pTruth1, Hop_ObjFaninC1(pObj) );
66 // creat the truth table of the node
67 pTruth = Cloud_bddAnd( dd, pTruth0, pTruth1 );
68 }
69 pObj->pData = pTruth;
70 return pTruth;
71 }
72
73 /**Function*************************************************************
74
75 Synopsis [Verifies that the factoring is correct.]
76
77 Description []
78
79 SideEffects []
80
81 SeeAlso []
82
83 ***********************************************************************/
Lpk_CutTruthBdd(Lpk_Man_t * p,Lpk_Cut_t * pCut)84 CloudNode * Lpk_CutTruthBdd( Lpk_Man_t * p, Lpk_Cut_t * pCut )
85 {
86 CloudManager * dd = p->pDsdMan->dd;
87 Hop_Man_t * pManHop = (Hop_Man_t *)p->pNtk->pManFunc;
88 Hop_Obj_t * pObjHop;
89 Abc_Obj_t * pObj, * pFanin;
90 CloudNode * pTruth = NULL; // Suppress "might be used uninitialized"
91 int i, k;
92
93 // return NULL;
94 // Lpk_NodePrintCut( p, pCut );
95 // initialize the leaves
96 Lpk_CutForEachLeaf( p->pNtk, pCut, pObj, i )
97 pObj->pCopy = (Abc_Obj_t *)dd->vars[pCut->nLeaves-1-i];
98
99 // construct truth table in the topological order
100 Lpk_CutForEachNodeReverse( p->pNtk, pCut, pObj, i )
101 {
102 // get the local AIG
103 pObjHop = Hop_Regular((Hop_Obj_t *)pObj->pData);
104 // clean the data field of the nodes in the AIG subgraph
105 Hop_ObjCleanData_rec( pObjHop );
106 // set the initial truth tables at the fanins
107 Abc_ObjForEachFanin( pObj, pFanin, k )
108 {
109 assert( ((unsigned)(ABC_PTRUINT_T)pFanin->pCopy) & 0xffff0000 );
110 Hop_ManPi( pManHop, k )->pData = pFanin->pCopy;
111 }
112 // compute the truth table of internal nodes
113 pTruth = Lpk_CutTruthBdd_rec( dd, pManHop, pObjHop, pCut->nLeaves );
114 if ( Hop_IsComplement((Hop_Obj_t *)pObj->pData) )
115 pTruth = Cloud_Not(pTruth);
116 // set the truth table at the node
117 pObj->pCopy = (Abc_Obj_t *)pTruth;
118
119 }
120
121 // Cloud_bddPrint( dd, pTruth );
122 // printf( "Bdd size = %d. Total nodes = %d.\n", Cloud_DagSize( dd, pTruth ), dd->nNodesCur-dd->nVars-1 );
123 return pTruth;
124 }
125
126
127 /**Function*************************************************************
128
129 Synopsis [Computes the truth table of one cut.]
130
131 Description []
132
133 SideEffects []
134
135 SeeAlso []
136
137 ***********************************************************************/
Lpk_CutTruth_rec(Hop_Man_t * pMan,Hop_Obj_t * pObj,int nVars,Vec_Ptr_t * vTtNodes,int * piCount)138 unsigned * Lpk_CutTruth_rec( Hop_Man_t * pMan, Hop_Obj_t * pObj, int nVars, Vec_Ptr_t * vTtNodes, int * piCount )
139 {
140 unsigned * pTruth, * pTruth0, * pTruth1;
141 assert( !Hop_IsComplement(pObj) );
142 if ( pObj->pData )
143 {
144 assert( ((unsigned)(ABC_PTRUINT_T)pObj->pData) & 0xffff0000 );
145 return (unsigned *)pObj->pData;
146 }
147 // get the plan for a new truth table
148 pTruth = (unsigned *)Vec_PtrEntry( vTtNodes, (*piCount)++ );
149 if ( Hop_ObjIsConst1(pObj) )
150 Kit_TruthFill( pTruth, nVars );
151 else
152 {
153 assert( Hop_ObjIsAnd(pObj) );
154 // compute the truth tables of the fanins
155 pTruth0 = Lpk_CutTruth_rec( pMan, Hop_ObjFanin0(pObj), nVars, vTtNodes, piCount );
156 pTruth1 = Lpk_CutTruth_rec( pMan, Hop_ObjFanin1(pObj), nVars, vTtNodes, piCount );
157 // creat the truth table of the node
158 Kit_TruthAndPhase( pTruth, pTruth0, pTruth1, nVars, Hop_ObjFaninC0(pObj), Hop_ObjFaninC1(pObj) );
159 }
160 pObj->pData = pTruth;
161 return pTruth;
162 }
163
164 /**Function*************************************************************
165
166 Synopsis [Computes the truth able of one cut.]
167
168 Description []
169
170 SideEffects []
171
172 SeeAlso []
173
174 ***********************************************************************/
Lpk_CutTruth(Lpk_Man_t * p,Lpk_Cut_t * pCut,int fInv)175 unsigned * Lpk_CutTruth( Lpk_Man_t * p, Lpk_Cut_t * pCut, int fInv )
176 {
177 Hop_Man_t * pManHop = (Hop_Man_t *)p->pNtk->pManFunc;
178 Hop_Obj_t * pObjHop;
179 Abc_Obj_t * pObj = NULL; // Suppress "might be used uninitialized"
180 Abc_Obj_t * pFanin;
181 unsigned * pTruth = NULL; // Suppress "might be used uninitialized"
182 int i, k, iCount = 0;
183 // Lpk_NodePrintCut( p, pCut );
184 assert( pCut->nNodes > 0 );
185
186 // initialize the leaves
187 Lpk_CutForEachLeaf( p->pNtk, pCut, pObj, i )
188 pObj->pCopy = (Abc_Obj_t *)Vec_PtrEntry( p->vTtElems, fInv? pCut->nLeaves-1-i : i );
189
190 // construct truth table in the topological order
191 Lpk_CutForEachNodeReverse( p->pNtk, pCut, pObj, i )
192 {
193 // get the local AIG
194 pObjHop = Hop_Regular((Hop_Obj_t *)pObj->pData);
195 // clean the data field of the nodes in the AIG subgraph
196 Hop_ObjCleanData_rec( pObjHop );
197 // set the initial truth tables at the fanins
198 Abc_ObjForEachFanin( pObj, pFanin, k )
199 {
200 assert( ((unsigned)(ABC_PTRUINT_T)pFanin->pCopy) & 0xffff0000 );
201 Hop_ManPi( pManHop, k )->pData = pFanin->pCopy;
202 }
203 // compute the truth table of internal nodes
204 pTruth = Lpk_CutTruth_rec( pManHop, pObjHop, pCut->nLeaves, p->vTtNodes, &iCount );
205 if ( Hop_IsComplement((Hop_Obj_t *)pObj->pData) )
206 Kit_TruthNot( pTruth, pTruth, pCut->nLeaves );
207 // set the truth table at the node
208 pObj->pCopy = (Abc_Obj_t *)pTruth;
209 }
210
211 // make sure direct truth table is stored elsewhere (assuming the first call for direct truth!!!)
212 if ( fInv == 0 )
213 {
214 pTruth = (unsigned *)Vec_PtrEntry( p->vTtNodes, iCount++ );
215 Kit_TruthCopy( pTruth, (unsigned *)(ABC_PTRUINT_T)pObj->pCopy, pCut->nLeaves );
216 }
217 assert( iCount <= Vec_PtrSize(p->vTtNodes) );
218 return pTruth;
219 }
220
221
222 /**Function*************************************************************
223
224 Synopsis [Returns 1 if at least one entry has changed.]
225
226 Description []
227
228 SideEffects []
229
230 SeeAlso []
231
232 ***********************************************************************/
Lpk_NodeRecordImpact(Lpk_Man_t * p)233 void Lpk_NodeRecordImpact( Lpk_Man_t * p )
234 {
235 Lpk_Cut_t * pCut;
236 Vec_Ptr_t * vNodes = Vec_VecEntry( p->vVisited, p->pObj->Id );
237 Abc_Obj_t * pNode, * pNode2;
238 int i, k;
239 // collect the nodes that impact the given node
240 Vec_PtrClear( vNodes );
241 for ( i = 0; i < p->nCuts; i++ )
242 {
243 pCut = p->pCuts + i;
244 for ( k = 0; k < (int)pCut->nLeaves; k++ )
245 {
246 pNode = Abc_NtkObj( p->pNtk, pCut->pLeaves[k] );
247 if ( pNode->fMarkC )
248 continue;
249 pNode->fMarkC = 1;
250 Vec_PtrPush( vNodes, (void *)(ABC_PTRUINT_T)pNode->Id );
251 Vec_PtrPush( vNodes, (void *)(ABC_PTRUINT_T)Abc_ObjFanoutNum(pNode) );
252 }
253 }
254 // clear the marks
255 Vec_PtrForEachEntryDouble( Abc_Obj_t *, Abc_Obj_t *, vNodes, pNode, pNode2, i )
256 {
257 pNode = Abc_NtkObj( p->pNtk, (int)(ABC_PTRUINT_T)pNode );
258 pNode->fMarkC = 0;
259 // i++;
260 }
261 //printf( "%d ", Vec_PtrSize(vNodes) );
262 }
263
264 /**Function*************************************************************
265
266 Synopsis [Returns 1 if the cut has structural DSD.]
267
268 Description []
269
270 SideEffects []
271
272 SeeAlso []
273
274 ***********************************************************************/
Lpk_NodeCutsCheckDsd(Lpk_Man_t * p,Lpk_Cut_t * pCut)275 int Lpk_NodeCutsCheckDsd( Lpk_Man_t * p, Lpk_Cut_t * pCut )
276 {
277 Abc_Obj_t * pObj, * pFanin;
278 int i, k, nCands, fLeavesOnly, RetValue;
279 assert( pCut->nLeaves > 0 );
280 // clear ref counters
281 memset( p->pRefs, 0, sizeof(int) * pCut->nLeaves );
282 // mark cut leaves
283 Lpk_CutForEachLeaf( p->pNtk, pCut, pObj, i )
284 {
285 assert( pObj->fMarkA == 0 );
286 pObj->fMarkA = 1;
287 pObj->pCopy = (Abc_Obj_t *)(ABC_PTRUINT_T)i;
288 }
289 // ref leaves pointed from the internal nodes
290 nCands = 0;
291 Lpk_CutForEachNode( p->pNtk, pCut, pObj, i )
292 {
293 fLeavesOnly = 1;
294 Abc_ObjForEachFanin( pObj, pFanin, k )
295 if ( pFanin->fMarkA )
296 p->pRefs[(int)(ABC_PTRUINT_T)pFanin->pCopy]++;
297 else
298 fLeavesOnly = 0;
299 if ( fLeavesOnly )
300 p->pCands[nCands++] = pObj->Id;
301 }
302 // look at the nodes that only point to the leaves
303 RetValue = 0;
304 for ( i = 0; i < nCands; i++ )
305 {
306 pObj = Abc_NtkObj( p->pNtk, p->pCands[i] );
307 Abc_ObjForEachFanin( pObj, pFanin, k )
308 {
309 assert( pFanin->fMarkA == 1 );
310 if ( p->pRefs[(int)(ABC_PTRUINT_T)pFanin->pCopy] > 1 )
311 break;
312 }
313 if ( k == Abc_ObjFaninNum(pObj) )
314 {
315 RetValue = 1;
316 break;
317 }
318 }
319 // unmark cut leaves
320 Lpk_CutForEachLeaf( p->pNtk, pCut, pObj, i )
321 pObj->fMarkA = 0;
322 return RetValue;
323 }
324
325 /**Function*************************************************************
326
327 Synopsis [Returns 1 if pDom is contained in pCut.]
328
329 Description []
330
331 SideEffects []
332
333 SeeAlso []
334
335 ***********************************************************************/
Lpk_NodeCutsOneDominance(Lpk_Cut_t * pDom,Lpk_Cut_t * pCut)336 static inline int Lpk_NodeCutsOneDominance( Lpk_Cut_t * pDom, Lpk_Cut_t * pCut )
337 {
338 int i, k;
339 for ( i = 0; i < (int)pDom->nLeaves; i++ )
340 {
341 for ( k = 0; k < (int)pCut->nLeaves; k++ )
342 if ( pDom->pLeaves[i] == pCut->pLeaves[k] )
343 break;
344 if ( k == (int)pCut->nLeaves ) // node i in pDom is not contained in pCut
345 return 0;
346 }
347 // every node in pDom is contained in pCut
348 return 1;
349 }
350
351 /**Function*************************************************************
352
353 Synopsis [Check if the cut exists.]
354
355 Description [Returns 1 if the cut exists.]
356
357 SideEffects []
358
359 SeeAlso []
360
361 ***********************************************************************/
Lpk_NodeCutsOneFilter(Lpk_Cut_t * pCuts,int nCuts,Lpk_Cut_t * pCutNew)362 int Lpk_NodeCutsOneFilter( Lpk_Cut_t * pCuts, int nCuts, Lpk_Cut_t * pCutNew )
363 {
364 Lpk_Cut_t * pCut;
365 int i, k;
366 assert( pCutNew->uSign[0] || pCutNew->uSign[1] );
367 // try to find the cut
368 for ( i = 0; i < nCuts; i++ )
369 {
370 pCut = pCuts + i;
371 if ( pCut->nLeaves == 0 )
372 continue;
373 if ( pCut->nLeaves == pCutNew->nLeaves )
374 {
375 if ( pCut->uSign[0] == pCutNew->uSign[0] && pCut->uSign[1] == pCutNew->uSign[1] )
376 {
377 for ( k = 0; k < (int)pCutNew->nLeaves; k++ )
378 if ( pCut->pLeaves[k] != pCutNew->pLeaves[k] )
379 break;
380 if ( k == (int)pCutNew->nLeaves )
381 return 1;
382 }
383 continue;
384 }
385 if ( pCut->nLeaves < pCutNew->nLeaves )
386 {
387 // skip the non-contained cuts
388 if ( (pCut->uSign[0] & pCutNew->uSign[0]) != pCut->uSign[0] )
389 continue;
390 if ( (pCut->uSign[1] & pCutNew->uSign[1]) != pCut->uSign[1] )
391 continue;
392 // check containment seriously
393 if ( Lpk_NodeCutsOneDominance( pCut, pCutNew ) )
394 return 1;
395 continue;
396 }
397 // check potential containment of other cut
398
399 // skip the non-contained cuts
400 if ( (pCut->uSign[0] & pCutNew->uSign[0]) != pCutNew->uSign[0] )
401 continue;
402 if ( (pCut->uSign[1] & pCutNew->uSign[1]) != pCutNew->uSign[1] )
403 continue;
404 // check containment seriously
405 if ( Lpk_NodeCutsOneDominance( pCutNew, pCut ) )
406 pCut->nLeaves = 0; // removed
407 }
408 return 0;
409 }
410
411 /**Function*************************************************************
412
413 Synopsis [Prints the given cut.]
414
415 Description []
416
417 SideEffects []
418
419 SeeAlso []
420
421 ***********************************************************************/
Lpk_NodePrintCut(Lpk_Man_t * p,Lpk_Cut_t * pCut,int fLeavesOnly)422 void Lpk_NodePrintCut( Lpk_Man_t * p, Lpk_Cut_t * pCut, int fLeavesOnly )
423 {
424 Abc_Obj_t * pObj;
425 int i;
426 if ( !fLeavesOnly )
427 printf( "LEAVES:\n" );
428 Lpk_CutForEachLeaf( p->pNtk, pCut, pObj, i )
429 printf( "%d,", pObj->Id );
430 if ( !fLeavesOnly )
431 {
432 printf( "\nNODES:\n" );
433 Lpk_CutForEachNode( p->pNtk, pCut, pObj, i )
434 {
435 printf( "%d,", pObj->Id );
436 assert( Abc_ObjIsNode(pObj) );
437 }
438 printf( "\n" );
439 }
440 }
441
442 /**Function*************************************************************
443
444 Synopsis [Set the cut signature.]
445
446 Description []
447
448 SideEffects []
449
450 SeeAlso []
451
452 ***********************************************************************/
Lpk_NodeCutSignature(Lpk_Cut_t * pCut)453 void Lpk_NodeCutSignature( Lpk_Cut_t * pCut )
454 {
455 unsigned i;
456 pCut->uSign[0] = pCut->uSign[1] = 0;
457 for ( i = 0; i < pCut->nLeaves; i++ )
458 {
459 pCut->uSign[(pCut->pLeaves[i] & 32) > 0] |= (1 << (pCut->pLeaves[i] & 31));
460 if ( i != pCut->nLeaves - 1 )
461 assert( pCut->pLeaves[i] < pCut->pLeaves[i+1] );
462 }
463 }
464
465
466 /**Function*************************************************************
467
468 Synopsis [Computes the set of all cuts.]
469
470 Description []
471
472 SideEffects []
473
474 SeeAlso []
475
476 ***********************************************************************/
Lpk_NodeCutsOne(Lpk_Man_t * p,Lpk_Cut_t * pCut,int Node)477 void Lpk_NodeCutsOne( Lpk_Man_t * p, Lpk_Cut_t * pCut, int Node )
478 {
479 Lpk_Cut_t * pCutNew;
480 Abc_Obj_t * pObj, * pFanin;
481 int i, k, j, nLeavesNew;
482 /*
483 printf( "Exploring cut " );
484 Lpk_NodePrintCut( p, pCut, 1 );
485 printf( "with node %d\n", Node );
486 */
487 // check if the cut can stand adding one more internal node
488 if ( pCut->nNodes == LPK_SIZE_MAX )
489 return;
490
491 // if the node is a PI, quit
492 pObj = Abc_NtkObj( p->pNtk, Node );
493 if ( Abc_ObjIsCi(pObj) )
494 return;
495 assert( Abc_ObjIsNode(pObj) );
496 // assert( Abc_ObjFaninNum(pObj) <= p->pPars->nLutSize );
497
498 // if the node is not in the MFFC, check the limit
499 if ( !Abc_NodeIsTravIdCurrent(pObj) )
500 {
501 if ( (int)pCut->nNodesDup == p->pPars->nLutsOver )
502 return;
503 assert( (int)pCut->nNodesDup < p->pPars->nLutsOver );
504 }
505
506 // check the possibility of adding this node using the signature
507 nLeavesNew = pCut->nLeaves - 1;
508 Abc_ObjForEachFanin( pObj, pFanin, i )
509 {
510 if ( (pCut->uSign[(pFanin->Id & 32) > 0] & (1 << (pFanin->Id & 31))) )
511 continue;
512 if ( ++nLeavesNew > p->pPars->nVarsMax )
513 return;
514 }
515
516 // initialize the set of leaves to the nodes in the cut
517 assert( p->nCuts < LPK_CUTS_MAX );
518 pCutNew = p->pCuts + p->nCuts;
519 pCutNew->nLeaves = 0;
520 for ( i = 0; i < (int)pCut->nLeaves; i++ )
521 if ( pCut->pLeaves[i] != Node )
522 pCutNew->pLeaves[pCutNew->nLeaves++] = pCut->pLeaves[i];
523
524 // add new nodes
525 Abc_ObjForEachFanin( pObj, pFanin, i )
526 {
527 // find the place where this node belongs
528 for ( k = 0; k < (int)pCutNew->nLeaves; k++ )
529 if ( pCutNew->pLeaves[k] >= pFanin->Id )
530 break;
531 if ( k < (int)pCutNew->nLeaves && pCutNew->pLeaves[k] == pFanin->Id )
532 continue;
533 // check if there is room
534 if ( (int)pCutNew->nLeaves == p->pPars->nVarsMax )
535 return;
536 // move all the nodes
537 for ( j = pCutNew->nLeaves; j > k; j-- )
538 pCutNew->pLeaves[j] = pCutNew->pLeaves[j-1];
539 pCutNew->pLeaves[k] = pFanin->Id;
540 pCutNew->nLeaves++;
541 assert( pCutNew->nLeaves <= LPK_SIZE_MAX );
542
543 }
544 // skip the contained cuts
545 Lpk_NodeCutSignature( pCutNew );
546 if ( Lpk_NodeCutsOneFilter( p->pCuts, p->nCuts, pCutNew ) )
547 return;
548
549 // update the set of internal nodes
550 assert( pCut->nNodes < LPK_SIZE_MAX );
551 memcpy( pCutNew->pNodes, pCut->pNodes, pCut->nNodes * sizeof(int) );
552 pCutNew->nNodes = pCut->nNodes;
553 pCutNew->nNodesDup = pCut->nNodesDup;
554
555 // check if the node is already there
556 // if so, move the node to be the last
557 for ( i = 0; i < (int)pCutNew->nNodes; i++ )
558 if ( pCutNew->pNodes[i] == Node )
559 {
560 for ( k = i; k < (int)pCutNew->nNodes - 1; k++ )
561 pCutNew->pNodes[k] = pCutNew->pNodes[k+1];
562 pCutNew->pNodes[k] = Node;
563 break;
564 }
565 if ( i == (int)pCutNew->nNodes ) // new node
566 {
567 pCutNew->pNodes[ pCutNew->nNodes++ ] = Node;
568 pCutNew->nNodesDup += !Abc_NodeIsTravIdCurrent(pObj);
569 }
570 // the number of nodes does not exceed MFFC plus duplications
571 assert( pCutNew->nNodes <= p->nMffc + pCutNew->nNodesDup );
572 // add the cut to storage
573 assert( p->nCuts < LPK_CUTS_MAX );
574 p->nCuts++;
575 }
576
577 /**Function*************************************************************
578
579 Synopsis [Count support.]
580
581 Description []
582
583 SideEffects []
584
585 SeeAlso []
586
587 ***********************************************************************/
Lpk_CountSupp(Abc_Ntk_t * p,Vec_Ptr_t * vNodes)588 int Lpk_CountSupp( Abc_Ntk_t * p, Vec_Ptr_t * vNodes )
589 {
590 Abc_Obj_t * pObj, * pFanin;
591 int i, k, Count = 0;
592 Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
593 {
594 Abc_ObjForEachFanin( pObj, pFanin, k )
595 {
596 if ( Abc_NodeIsTravIdCurrent(pFanin) )
597 continue;
598 Count += !pFanin->fPersist;
599 pFanin->fPersist = 1;
600 }
601 }
602 Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
603 Abc_ObjForEachFanin( pObj, pFanin, k )
604 pFanin->fPersist = 0;
605 return Count;
606 }
607
608 /**Function*************************************************************
609
610 Synopsis [Computes the set of all cuts.]
611
612 Description []
613
614 SideEffects []
615
616 SeeAlso []
617
618 ***********************************************************************/
Lpk_NodeCuts(Lpk_Man_t * p)619 int Lpk_NodeCuts( Lpk_Man_t * p )
620 {
621 Lpk_Cut_t * pCut, * pCut2;
622 int i, k, Temp, nMffc, fChanges;
623 //int nSupp;
624
625 // mark the MFFC of the node with the current trav ID
626 Vec_PtrClear( p->vTemp );
627 nMffc = p->nMffc = Abc_NodeMffcLabel( p->pObj, p->vTemp );
628 assert( nMffc > 0 );
629 if ( nMffc == 1 )
630 return 0;
631 /*
632 // count the leaves
633 nSupp = Lpk_CountSupp( p->pNtk, p->vTemp );
634 if ( nMffc > 10 && nSupp <= 10 )
635 printf( "Obj = %4d : Supp = %4d. Mffc = %4d.\n", p->pObj->Id, nSupp, nMffc );
636 */
637 // initialize the first cut
638 pCut = p->pCuts; p->nCuts = 1;
639 pCut->nNodes = 0;
640 pCut->nNodesDup = 0;
641 pCut->nLeaves = 1;
642 pCut->pLeaves[0] = p->pObj->Id;
643 // assign the signature
644 Lpk_NodeCutSignature( pCut );
645
646 // perform the cut computation
647 for ( i = 0; i < p->nCuts; i++ )
648 {
649 pCut = p->pCuts + i;
650 if ( pCut->nLeaves == 0 )
651 continue;
652
653 // try to expand the fanins of this cut
654 for ( k = 0; k < (int)pCut->nLeaves; k++ )
655 {
656 // create a new cut
657 Lpk_NodeCutsOne( p, pCut, pCut->pLeaves[k] );
658 // quit if the number of cuts has exceeded the limit
659 if ( p->nCuts == LPK_CUTS_MAX )
660 break;
661 }
662 if ( p->nCuts == LPK_CUTS_MAX )
663 break;
664 }
665 if ( p->nCuts == LPK_CUTS_MAX )
666 p->nNodesOver++;
667
668 // record the impact of this node
669 if ( p->pPars->fSatur )
670 Lpk_NodeRecordImpact( p );
671
672 // compress the cuts by removing empty ones, those with negative Weight, and decomposable ones
673 p->nEvals = 0;
674 for ( i = 0; i < p->nCuts; i++ )
675 {
676 pCut = p->pCuts + i;
677 if ( pCut->nLeaves < 2 )
678 continue;
679 // compute the minimum number of LUTs needed to implement this cut
680 // V = N * (K-1) + 1 ~~~~~ N = Ceiling[(V-1)/(K-1)] = (V-1)/(K-1) + [(V-1)%(K-1) > 0]
681 pCut->nLuts = Lpk_LutNumLuts( pCut->nLeaves, p->pPars->nLutSize );
682 // pCut->Weight = (float)1.0 * (pCut->nNodes - pCut->nNodesDup - 1) / pCut->nLuts; //p->pPars->nLutsMax;
683 pCut->Weight = (float)1.0 * (pCut->nNodes - pCut->nNodesDup) / pCut->nLuts; //p->pPars->nLutsMax;
684 if ( pCut->Weight <= 1.001 )
685 // if ( pCut->Weight <= 0.999 )
686 continue;
687 pCut->fHasDsd = Lpk_NodeCutsCheckDsd( p, pCut );
688 if ( pCut->fHasDsd )
689 continue;
690 p->pEvals[p->nEvals++] = i;
691
692 // if ( pCut->nLeaves <= 9 && pCut->nNodes > 15 )
693 // printf( "%5d : Obj = %4d Leaves = %4d Nodes = %4d LUTs = %4d\n", i, p->pObj->Id, pCut->nLeaves, pCut->nNodes, pCut->nLuts );
694 }
695 if ( p->nEvals == 0 )
696 return 0;
697
698 // sort the cuts by Weight
699 do {
700 fChanges = 0;
701 for ( i = 0; i < p->nEvals - 1; i++ )
702 {
703 pCut = p->pCuts + p->pEvals[i];
704 pCut2 = p->pCuts + p->pEvals[i+1];
705 if ( pCut->Weight >= pCut2->Weight - 0.001 )
706 continue;
707 Temp = p->pEvals[i];
708 p->pEvals[i] = p->pEvals[i+1];
709 p->pEvals[i+1] = Temp;
710 fChanges = 1;
711 }
712 } while ( fChanges );
713 /*
714 for ( i = 0; i < p->nEvals; i++ )
715 {
716 pCut = p->pCuts + p->pEvals[i];
717 printf( "Cut %3d : W = %5.2f.\n", i, pCut->Weight );
718 }
719 printf( "\n" );
720 */
721 return 1;
722 }
723
724 ////////////////////////////////////////////////////////////////////////
725 /// END OF FILE ///
726 ////////////////////////////////////////////////////////////////////////
727
728
729 ABC_NAMESPACE_IMPL_END
730
731