1 /**CFile****************************************************************
2
3 FileName [cutNode.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [K-feasible cut computation package.]
8
9 Synopsis [Procedures to compute cuts for a node.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: cutNode.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "cutInt.h"
22
23 ABC_NAMESPACE_IMPL_START
24
25
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29
30 static int Cut_NodeMapping( Cut_Man_t * p, Cut_Cut_t * pCuts, int Node, int Node0, int Node1 );
31 static int Cut_NodeMapping2( Cut_Man_t * p, Cut_Cut_t * pCuts, int Node, int Node0, int Node1 );
32
33 ////////////////////////////////////////////////////////////////////////
34 /// FUNCTION DEFINITIONS ///
35 ////////////////////////////////////////////////////////////////////////
36
37 /**Function*************************************************************
38
39 Synopsis [Returns 1 if pDom is contained in pCut.]
40
41 Description []
42
43 SideEffects []
44
45 SeeAlso []
46
47 ***********************************************************************/
Cut_CutCheckDominance(Cut_Cut_t * pDom,Cut_Cut_t * pCut)48 static inline int Cut_CutCheckDominance( Cut_Cut_t * pDom, Cut_Cut_t * pCut )
49 {
50 int i, k;
51 for ( i = 0; i < (int)pDom->nLeaves; i++ )
52 {
53 for ( k = 0; k < (int)pCut->nLeaves; k++ )
54 if ( pDom->pLeaves[i] == pCut->pLeaves[k] )
55 break;
56 if ( k == (int)pCut->nLeaves ) // node i in pDom is not contained in pCut
57 return 0;
58 }
59 // every node in pDom is contained in pCut
60 return 1;
61 }
62
63 /**Function*************************************************************
64
65 Synopsis [Filters cuts using dominance.]
66
67 Description []
68
69 SideEffects []
70
71 SeeAlso []
72
73 ***********************************************************************/
Cut_CutFilter(Cut_Man_t * p,Cut_Cut_t * pList)74 static inline void Cut_CutFilter( Cut_Man_t * p, Cut_Cut_t * pList )
75 {
76 Cut_Cut_t * pListR, ** ppListR = &pListR;
77 Cut_Cut_t * pCut, * pCut2, * pDom, * pPrev;
78 // save the first cut
79 *ppListR = pList, ppListR = &pList->pNext;
80 // try to filter out other cuts
81 pPrev = pList;
82 Cut_ListForEachCutSafe( pList->pNext, pCut, pCut2 )
83 {
84 assert( pCut->nLeaves > 1 );
85 // go through all the previous cuts up to pCut
86 Cut_ListForEachCutStop( pList->pNext, pDom, pCut )
87 {
88 if ( pDom->nLeaves > pCut->nLeaves )
89 continue;
90 if ( (pDom->uSign & pCut->uSign) != pDom->uSign )
91 continue;
92 if ( Cut_CutCheckDominance( pDom, pCut ) )
93 break;
94 }
95 if ( pDom != pCut ) // pDom is contained in pCut - recycle pCut
96 {
97 // make sure cuts are connected after removing
98 pPrev->pNext = pCut->pNext;
99 // recycle the cut
100 Cut_CutRecycle( p, pCut );
101 }
102 else // pDom is NOT contained in pCut - save pCut
103 {
104 *ppListR = pCut, ppListR = &pCut->pNext;
105 pPrev = pCut;
106 }
107 }
108 *ppListR = NULL;
109 }
110
111 /**Function*************************************************************
112
113 Synopsis [Checks equality of one cut.]
114
115 Description [Returns 1 if the cut is removed.]
116
117 SideEffects []
118
119 SeeAlso []
120
121 ***********************************************************************/
Cut_CutFilterOneEqual(Cut_Man_t * p,Cut_List_t * pSuperList,Cut_Cut_t * pCut)122 static inline int Cut_CutFilterOneEqual( Cut_Man_t * p, Cut_List_t * pSuperList, Cut_Cut_t * pCut )
123 {
124 Cut_Cut_t * pTemp;
125 Cut_ListForEachCut( pSuperList->pHead[pCut->nLeaves], pTemp )
126 {
127 // skip the non-contained cuts
128 if ( pCut->uSign != pTemp->uSign )
129 continue;
130 // check containment seriously
131 if ( Cut_CutCheckDominance( pTemp, pCut ) )
132 {
133 p->nCutsFilter++;
134 Cut_CutRecycle( p, pCut );
135 return 1;
136 }
137 }
138 return 0;
139 }
140
141 /**Function*************************************************************
142
143 Synopsis [Checks containment for one cut.]
144
145 Description [Returns 1 if the cut is removed.]
146
147 SideEffects [May remove other cuts in the set.]
148
149 SeeAlso []
150
151 ***********************************************************************/
Cut_CutFilterOne(Cut_Man_t * p,Cut_List_t * pSuperList,Cut_Cut_t * pCut)152 static inline int Cut_CutFilterOne( Cut_Man_t * p, Cut_List_t * pSuperList, Cut_Cut_t * pCut )
153 {
154 Cut_Cut_t * pTemp, * pTemp2, ** ppTail;
155 int a;
156
157 // check if this cut is filtered out by smaller cuts
158 for ( a = 2; a <= (int)pCut->nLeaves; a++ )
159 {
160 Cut_ListForEachCut( pSuperList->pHead[a], pTemp )
161 {
162 // skip the non-contained cuts
163 if ( (pTemp->uSign & pCut->uSign) != pTemp->uSign )
164 continue;
165 // check containment seriously
166 if ( Cut_CutCheckDominance( pTemp, pCut ) )
167 {
168 p->nCutsFilter++;
169 Cut_CutRecycle( p, pCut );
170 return 1;
171 }
172 }
173 }
174
175 // filter out other cuts using this one
176 for ( a = pCut->nLeaves + 1; a <= (int)pCut->nVarsMax; a++ )
177 {
178 ppTail = pSuperList->pHead + a;
179 Cut_ListForEachCutSafe( pSuperList->pHead[a], pTemp, pTemp2 )
180 {
181 // skip the non-contained cuts
182 if ( (pTemp->uSign & pCut->uSign) != pCut->uSign )
183 {
184 ppTail = &pTemp->pNext;
185 continue;
186 }
187 // check containment seriously
188 if ( Cut_CutCheckDominance( pCut, pTemp ) )
189 {
190 p->nCutsFilter++;
191 p->nNodeCuts--;
192 // move the head
193 if ( pSuperList->pHead[a] == pTemp )
194 pSuperList->pHead[a] = pTemp->pNext;
195 // move the tail
196 if ( pSuperList->ppTail[a] == &pTemp->pNext )
197 pSuperList->ppTail[a] = ppTail;
198 // skip the given cut in the list
199 *ppTail = pTemp->pNext;
200 // recycle pTemp
201 Cut_CutRecycle( p, pTemp );
202 }
203 else
204 ppTail = &pTemp->pNext;
205 }
206 assert( ppTail == pSuperList->ppTail[a] );
207 assert( *ppTail == NULL );
208 }
209
210 return 0;
211 }
212
213 /**Function*************************************************************
214
215 Synopsis [Checks if the cut is local and can be removed.]
216
217 Description [Returns 1 if the cut is removed.]
218
219 SideEffects []
220
221 SeeAlso []
222
223 ***********************************************************************/
Cut_CutFilterGlobal(Cut_Man_t * p,Cut_Cut_t * pCut)224 static inline int Cut_CutFilterGlobal( Cut_Man_t * p, Cut_Cut_t * pCut )
225 {
226 int a;
227 if ( pCut->nLeaves == 1 )
228 return 0;
229 for ( a = 0; a < (int)pCut->nLeaves; a++ )
230 if ( Vec_IntEntry( p->vNodeAttrs, pCut->pLeaves[a] ) ) // global
231 return 0;
232 // there is no global nodes, the cut should be removed
233 p->nCutsFilter++;
234 Cut_CutRecycle( p, pCut );
235 return 1;
236 }
237
238
239 /**Function*************************************************************
240
241 Synopsis [Checks containment for one cut.]
242
243 Description [Returns 1 if the cut is removed.]
244
245 SideEffects [May remove other cuts in the set.]
246
247 SeeAlso []
248
249 ***********************************************************************/
Cut_CutFilterOld(Cut_Man_t * p,Cut_Cut_t * pList,Cut_Cut_t * pCut)250 static inline int Cut_CutFilterOld( Cut_Man_t * p, Cut_Cut_t * pList, Cut_Cut_t * pCut )
251 {
252 Cut_Cut_t * pPrev, * pTemp, * pTemp2, ** ppTail;
253
254 // check if this cut is filtered out by smaller cuts
255 pPrev = NULL;
256 Cut_ListForEachCut( pList, pTemp )
257 {
258 if ( pTemp->nLeaves > pCut->nLeaves )
259 break;
260 pPrev = pTemp;
261 // skip the non-contained cuts
262 if ( (pTemp->uSign & pCut->uSign) != pTemp->uSign )
263 continue;
264 // check containment seriously
265 if ( Cut_CutCheckDominance( pTemp, pCut ) )
266 {
267 p->nCutsFilter++;
268 Cut_CutRecycle( p, pCut );
269 return 1;
270 }
271 }
272 assert( pPrev->pNext == pTemp );
273
274 // filter out other cuts using this one
275 ppTail = &pPrev->pNext;
276 Cut_ListForEachCutSafe( pTemp, pTemp, pTemp2 )
277 {
278 // skip the non-contained cuts
279 if ( (pTemp->uSign & pCut->uSign) != pCut->uSign )
280 {
281 ppTail = &pTemp->pNext;
282 continue;
283 }
284 // check containment seriously
285 if ( Cut_CutCheckDominance( pCut, pTemp ) )
286 {
287 p->nCutsFilter++;
288 p->nNodeCuts--;
289 // skip the given cut in the list
290 *ppTail = pTemp->pNext;
291 // recycle pTemp
292 Cut_CutRecycle( p, pTemp );
293 }
294 else
295 ppTail = &pTemp->pNext;
296 }
297 assert( *ppTail == NULL );
298 return 0;
299 }
300
301 /**Function*************************************************************
302
303 Synopsis [Processes two cuts.]
304
305 Description [Returns 1 if the limit has been reached.]
306
307 SideEffects []
308
309 SeeAlso []
310
311 ***********************************************************************/
Cut_CutProcessTwo(Cut_Man_t * p,Cut_Cut_t * pCut0,Cut_Cut_t * pCut1,Cut_List_t * pSuperList)312 static inline int Cut_CutProcessTwo( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1, Cut_List_t * pSuperList )
313 {
314 Cut_Cut_t * pCut;
315 // merge the cuts
316 if ( pCut0->nLeaves >= pCut1->nLeaves )
317 pCut = Cut_CutMergeTwo( p, pCut0, pCut1 );
318 else
319 pCut = Cut_CutMergeTwo( p, pCut1, pCut0 );
320 if ( pCut == NULL )
321 return 0;
322 assert( p->pParams->fSeq || pCut->nLeaves > 1 );
323 // set the signature
324 pCut->uSign = pCut0->uSign | pCut1->uSign;
325 if ( p->pParams->fRecord )
326 pCut->Num0 = pCut0->Num0, pCut->Num1 = pCut1->Num0;
327 // check containment
328 if ( p->pParams->fFilter )
329 {
330 if ( Cut_CutFilterOne(p, pSuperList, pCut) )
331 // if ( Cut_CutFilterOneEqual(p, pSuperList, pCut) )
332 return 0;
333 if ( p->pParams->fSeq )
334 {
335 if ( p->pCompareOld && Cut_CutFilterOld(p, p->pCompareOld, pCut) )
336 return 0;
337 if ( p->pCompareNew && Cut_CutFilterOld(p, p->pCompareNew, pCut) )
338 return 0;
339 }
340 }
341
342 if ( p->pParams->fGlobal )
343 {
344 assert( p->vNodeAttrs != NULL );
345 if ( Cut_CutFilterGlobal( p, pCut ) )
346 return 0;
347 }
348
349 // compute the truth table
350 if ( p->pParams->fTruth )
351 Cut_TruthCompute( p, pCut, pCut0, pCut1, p->fCompl0, p->fCompl1 );
352 // add to the list
353 Cut_ListAdd( pSuperList, pCut );
354 // return status (0 if okay; 1 if exceeded the limit)
355 return ++p->nNodeCuts == p->pParams->nKeepMax;
356 }
357
358 /**Function*************************************************************
359
360 Synopsis [Computes the cuts by merging cuts at two nodes.]
361
362 Description []
363
364 SideEffects []
365
366 SeeAlso []
367
368 ***********************************************************************/
Cut_NodeComputeCuts(Cut_Man_t * p,int Node,int Node0,int Node1,int fCompl0,int fCompl1,int fTriv,int TreeCode)369 Cut_Cut_t * Cut_NodeComputeCuts( Cut_Man_t * p, int Node, int Node0, int Node1, int fCompl0, int fCompl1, int fTriv, int TreeCode )
370 {
371 Cut_List_t Super, * pSuper = &Super;
372 Cut_Cut_t * pList, * pCut;
373 abctime clk;
374 // start the number of cuts at the node
375 p->nNodes++;
376 p->nNodeCuts = 0;
377 // prepare information for recording
378 if ( p->pParams->fRecord )
379 {
380 Cut_CutNumberList( Cut_NodeReadCutsNew(p, Node0) );
381 Cut_CutNumberList( Cut_NodeReadCutsNew(p, Node1) );
382 }
383 // compute the cuts
384 clk = Abc_Clock();
385 Cut_ListStart( pSuper );
386 Cut_NodeDoComputeCuts( p, pSuper, Node, fCompl0, fCompl1, Cut_NodeReadCutsNew(p, Node0), Cut_NodeReadCutsNew(p, Node1), fTriv, TreeCode );
387 pList = Cut_ListFinish( pSuper );
388 p->timeMerge += Abc_Clock() - clk;
389 // verify the result of cut computation
390 // Cut_CutListVerify( pList );
391 // performing the recording
392 if ( p->pParams->fRecord )
393 {
394 Vec_IntWriteEntry( p->vNodeStarts, Node, Vec_IntSize(p->vCutPairs) );
395 Cut_ListForEachCut( pList, pCut )
396 Vec_IntPush( p->vCutPairs, ((pCut->Num1 << 16) | pCut->Num0) );
397 Vec_IntWriteEntry( p->vNodeCuts, Node, Vec_IntSize(p->vCutPairs) - Vec_IntEntry(p->vNodeStarts, Node) );
398 }
399 if ( p->pParams->fRecordAig )
400 {
401 extern void Aig_RManRecord( unsigned * pTruth, int nVarsInit );
402 Cut_ListForEachCut( pList, pCut )
403 if ( Cut_CutReadLeaveNum(pCut) > 4 )
404 Aig_RManRecord( Cut_CutReadTruth(pCut), Cut_CutReadLeaveNum(pCut) );
405 }
406 // check if the node is over the list
407 if ( p->nNodeCuts == p->pParams->nKeepMax )
408 p->nCutsLimit++;
409 // set the list at the node
410 Vec_PtrFillExtra( p->vCutsNew, Node + 1, NULL );
411 assert( Cut_NodeReadCutsNew(p, Node) == NULL );
412 /////
413 // pList->pNext = NULL;
414 /////
415 Cut_NodeWriteCutsNew( p, Node, pList );
416 // filter the cuts
417 //clk = Abc_Clock();
418 // if ( p->pParams->fFilter )
419 // Cut_CutFilter( p, pList0 );
420 //p->timeFilter += Abc_Clock() - clk;
421 // perform mapping of this node with these cuts
422 clk = Abc_Clock();
423 if ( p->pParams->fMap && !p->pParams->fSeq )
424 {
425 // int Delay1, Delay2;
426 // Delay1 = Cut_NodeMapping( p, pList, Node, Node0, Node1 );
427 // Delay2 = Cut_NodeMapping2( p, pList, Node, Node0, Node1 );
428 // assert( Delay1 >= Delay2 );
429 Cut_NodeMapping( p, pList, Node, Node0, Node1 );
430 }
431 p->timeMap += Abc_Clock() - clk;
432 return pList;
433 }
434
435 /**Function*************************************************************
436
437 Synopsis [Returns optimum delay mapping.]
438
439 Description []
440
441 SideEffects []
442
443 SeeAlso []
444
445 ***********************************************************************/
Cut_NodeMapping2(Cut_Man_t * p,Cut_Cut_t * pCuts,int Node,int Node0,int Node1)446 int Cut_NodeMapping2( Cut_Man_t * p, Cut_Cut_t * pCuts, int Node, int Node0, int Node1 )
447 {
448 Cut_Cut_t * pCut;
449 int DelayMin, DelayCur, i;
450 if ( pCuts == NULL )
451 p->nDelayMin = -1;
452 if ( p->nDelayMin == -1 )
453 return -1;
454 DelayMin = 1000000;
455 Cut_ListForEachCut( pCuts, pCut )
456 {
457 if ( pCut->nLeaves == 1 )
458 continue;
459 DelayCur = 0;
460 for ( i = 0; i < (int)pCut->nLeaves; i++ )
461 if ( DelayCur < Vec_IntEntry(p->vDelays, pCut->pLeaves[i]) )
462 DelayCur = Vec_IntEntry(p->vDelays, pCut->pLeaves[i]);
463 if ( DelayMin > DelayCur )
464 DelayMin = DelayCur;
465 }
466 if ( DelayMin == 1000000 )
467 {
468 p->nDelayMin = -1;
469 return -1;
470 }
471 DelayMin++;
472 Vec_IntWriteEntry( p->vDelays, Node, DelayMin );
473 if ( p->nDelayMin < DelayMin )
474 p->nDelayMin = DelayMin;
475 return DelayMin;
476 }
477
478 /**Function*************************************************************
479
480 Synopsis [Returns optimum delay mapping using the largest cut.]
481
482 Description []
483
484 SideEffects []
485
486 SeeAlso []
487
488 ***********************************************************************/
Cut_NodeMapping(Cut_Man_t * p,Cut_Cut_t * pCuts,int Node,int Node0,int Node1)489 int Cut_NodeMapping( Cut_Man_t * p, Cut_Cut_t * pCuts, int Node, int Node0, int Node1 )
490 {
491 Cut_Cut_t * pCut0, * pCut1, * pCut;
492 int Delay0, Delay1, Delay;
493 // get the fanin cuts
494 Delay0 = Vec_IntEntry( p->vDelays2, Node0 );
495 Delay1 = Vec_IntEntry( p->vDelays2, Node1 );
496 pCut0 = (Delay0 == 0) ? (Cut_Cut_t *)Vec_PtrEntry( p->vCutsNew, Node0 ) : (Cut_Cut_t *)Vec_PtrEntry( p->vCutsMax, Node0 );
497 pCut1 = (Delay1 == 0) ? (Cut_Cut_t *)Vec_PtrEntry( p->vCutsNew, Node1 ) : (Cut_Cut_t *)Vec_PtrEntry( p->vCutsMax, Node1 );
498 if ( Delay0 == Delay1 )
499 Delay = (Delay0 == 0) ? Delay0 + 1: Delay0;
500 else if ( Delay0 > Delay1 )
501 {
502 Delay = Delay0;
503 pCut1 = (Cut_Cut_t *)Vec_PtrEntry( p->vCutsNew, Node1 );
504 assert( pCut1->nLeaves == 1 );
505 }
506 else // if ( Delay0 < Delay1 )
507 {
508 Delay = Delay1;
509 pCut0 = (Cut_Cut_t *)Vec_PtrEntry( p->vCutsNew, Node0 );
510 assert( pCut0->nLeaves == 1 );
511 }
512 // merge the cuts
513 if ( pCut0->nLeaves < pCut1->nLeaves )
514 pCut = Cut_CutMergeTwo( p, pCut1, pCut0 );
515 else
516 pCut = Cut_CutMergeTwo( p, pCut0, pCut1 );
517 if ( pCut == NULL )
518 {
519 Delay++;
520 pCut = Cut_CutAlloc( p );
521 pCut->nLeaves = 2;
522 pCut->pLeaves[0] = Node0 < Node1 ? Node0 : Node1;
523 pCut->pLeaves[1] = Node0 < Node1 ? Node1 : Node0;
524 }
525 assert( Delay > 0 );
526 Vec_IntWriteEntry( p->vDelays2, Node, Delay );
527 Vec_PtrWriteEntry( p->vCutsMax, Node, pCut );
528 if ( p->nDelayMin < Delay )
529 p->nDelayMin = Delay;
530 return Delay;
531 }
532
533 /**Function*************************************************************
534
535 Synopsis [Computes area after mapping.]
536
537 Description []
538
539 SideEffects []
540
541 SeeAlso []
542
543 ***********************************************************************/
Cut_ManMappingArea_rec(Cut_Man_t * p,int Node)544 int Cut_ManMappingArea_rec( Cut_Man_t * p, int Node )
545 {
546 Cut_Cut_t * pCut;
547 int i, Counter;
548 if ( p->vCutsMax == NULL )
549 return 0;
550 pCut = (Cut_Cut_t *)Vec_PtrEntry( p->vCutsMax, Node );
551 if ( pCut == NULL || pCut->nLeaves == 1 )
552 return 0;
553 Counter = 0;
554 for ( i = 0; i < (int)pCut->nLeaves; i++ )
555 Counter += Cut_ManMappingArea_rec( p, pCut->pLeaves[i] );
556 Vec_PtrWriteEntry( p->vCutsMax, Node, NULL );
557 return 1 + Counter;
558 }
559
560
561 /**Function*************************************************************
562
563 Synopsis [Computes the cuts by merging cuts at two nodes.]
564
565 Description []
566
567 SideEffects []
568
569 SeeAlso []
570
571 ***********************************************************************/
Cut_NodeDoComputeCuts(Cut_Man_t * p,Cut_List_t * pSuper,int Node,int fCompl0,int fCompl1,Cut_Cut_t * pList0,Cut_Cut_t * pList1,int fTriv,int TreeCode)572 void Cut_NodeDoComputeCuts( Cut_Man_t * p, Cut_List_t * pSuper, int Node, int fCompl0, int fCompl1, Cut_Cut_t * pList0, Cut_Cut_t * pList1, int fTriv, int TreeCode )
573 {
574 Cut_Cut_t * pStop0, * pStop1, * pTemp0, * pTemp1;
575 Cut_Cut_t * pStore0 = NULL, * pStore1 = NULL; // Suppress "might be used uninitialized"
576 int i, nCutsOld, Limit;
577 // start with the elementary cut
578 if ( fTriv )
579 {
580 // printf( "Creating trivial cut %d.\n", Node );
581 pTemp0 = Cut_CutCreateTriv( p, Node );
582 Cut_ListAdd( pSuper, pTemp0 );
583 p->nNodeCuts++;
584 }
585 // get the cut lists of children
586 if ( pList0 == NULL || pList1 == NULL || (p->pParams->fLocal && TreeCode) )
587 return;
588
589 // remember the old number of cuts
590 nCutsOld = p->nCutsCur;
591 Limit = p->pParams->nVarsMax;
592 // get the simultation bit of the node
593 p->fSimul = (fCompl0 ^ pList0->fSimul) & (fCompl1 ^ pList1->fSimul);
594 // set temporary variables
595 p->fCompl0 = fCompl0;
596 p->fCompl1 = fCompl1;
597 // if tree cuts are computed, make sure only the unit cuts propagate over the DAG nodes
598 if ( TreeCode & 1 )
599 {
600 assert( pList0->nLeaves == 1 );
601 pStore0 = pList0->pNext;
602 pList0->pNext = NULL;
603 }
604 if ( TreeCode & 2 )
605 {
606 assert( pList1->nLeaves == 1 );
607 pStore1 = pList1->pNext;
608 pList1->pNext = NULL;
609 }
610 // find the point in the list where the max-var cuts begin
611 Cut_ListForEachCut( pList0, pStop0 )
612 if ( pStop0->nLeaves == (unsigned)Limit )
613 break;
614 Cut_ListForEachCut( pList1, pStop1 )
615 if ( pStop1->nLeaves == (unsigned)Limit )
616 break;
617
618 // small by small
619 Cut_ListForEachCutStop( pList0, pTemp0, pStop0 )
620 Cut_ListForEachCutStop( pList1, pTemp1, pStop1 )
621 {
622 if ( Cut_CutProcessTwo( p, pTemp0, pTemp1, pSuper ) )
623 goto Quits;
624 }
625 // small by large
626 Cut_ListForEachCutStop( pList0, pTemp0, pStop0 )
627 Cut_ListForEachCut( pStop1, pTemp1 )
628 {
629 if ( (pTemp0->uSign & pTemp1->uSign) != pTemp0->uSign )
630 continue;
631 if ( Cut_CutProcessTwo( p, pTemp0, pTemp1, pSuper ) )
632 goto Quits;
633 }
634 // small by large
635 Cut_ListForEachCutStop( pList1, pTemp1, pStop1 )
636 Cut_ListForEachCut( pStop0, pTemp0 )
637 {
638 if ( (pTemp0->uSign & pTemp1->uSign) != pTemp1->uSign )
639 continue;
640 if ( Cut_CutProcessTwo( p, pTemp0, pTemp1, pSuper ) )
641 goto Quits;
642 }
643 // large by large
644 Cut_ListForEachCut( pStop0, pTemp0 )
645 Cut_ListForEachCut( pStop1, pTemp1 )
646 {
647 assert( pTemp0->nLeaves == (unsigned)Limit && pTemp1->nLeaves == (unsigned)Limit );
648 if ( pTemp0->uSign != pTemp1->uSign )
649 continue;
650 for ( i = 0; i < Limit; i++ )
651 if ( pTemp0->pLeaves[i] != pTemp1->pLeaves[i] )
652 break;
653 if ( i < Limit )
654 continue;
655 if ( Cut_CutProcessTwo( p, pTemp0, pTemp1, pSuper ) )
656 goto Quits;
657 }
658 if ( p->nNodeCuts == 0 )
659 p->nNodesNoCuts++;
660 Quits:
661 if ( TreeCode & 1 )
662 pList0->pNext = pStore0;
663 if ( TreeCode & 2 )
664 pList1->pNext = pStore1;
665 }
666
667 /**Function*************************************************************
668
669 Synopsis [Computes the cuts by unioning cuts at a choice node.]
670
671 Description []
672
673 SideEffects []
674
675 SeeAlso []
676
677 ***********************************************************************/
Cut_NodeUnionCuts(Cut_Man_t * p,Vec_Int_t * vNodes)678 Cut_Cut_t * Cut_NodeUnionCuts( Cut_Man_t * p, Vec_Int_t * vNodes )
679 {
680 Cut_List_t Super, * pSuper = &Super;
681 Cut_Cut_t * pList, * pListStart, * pCut, * pCut2;
682 Cut_Cut_t * pTop = NULL; // Suppress "might be used uninitialized"
683 int i, k, Node, Root, Limit = p->pParams->nVarsMax;
684 abctime clk = Abc_Clock();
685
686 // start the new list
687 Cut_ListStart( pSuper );
688
689 // remember the root node to save the resulting cuts
690 Root = Vec_IntEntry( vNodes, 0 );
691 p->nNodeCuts = 1;
692
693 // collect small cuts first
694 Vec_PtrClear( p->vTemp );
695 Vec_IntForEachEntry( vNodes, Node, i )
696 {
697 // get the cuts of this node
698 pList = Cut_NodeReadCutsNew( p, Node );
699 Cut_NodeWriteCutsNew( p, Node, NULL );
700 assert( pList );
701 // remember the starting point
702 pListStart = pList->pNext;
703 pList->pNext = NULL;
704 // save or recycle the elementary cut
705 if ( i == 0 )
706 Cut_ListAdd( pSuper, pList ), pTop = pList;
707 else
708 Cut_CutRecycle( p, pList );
709 // save all the cuts that are smaller than the limit
710 Cut_ListForEachCutSafe( pListStart, pCut, pCut2 )
711 {
712 if ( pCut->nLeaves == (unsigned)Limit )
713 {
714 Vec_PtrPush( p->vTemp, pCut );
715 break;
716 }
717 // check containment
718 if ( p->pParams->fFilter && Cut_CutFilterOne( p, pSuper, pCut ) )
719 continue;
720 // set the complemented bit by comparing the first cut with the current cut
721 pCut->fCompl = pTop->fSimul ^ pCut->fSimul;
722 pListStart = pCut->pNext;
723 pCut->pNext = NULL;
724 // add to the list
725 Cut_ListAdd( pSuper, pCut );
726 if ( ++p->nNodeCuts == p->pParams->nKeepMax )
727 {
728 // recycle the rest of the cuts of this node
729 Cut_ListForEachCutSafe( pListStart, pCut, pCut2 )
730 Cut_CutRecycle( p, pCut );
731 // recycle all cuts of other nodes
732 Vec_IntForEachEntryStart( vNodes, Node, k, i+1 )
733 Cut_NodeFreeCuts( p, Node );
734 // recycle the saved cuts of other nodes
735 Vec_PtrForEachEntry( Cut_Cut_t *, p->vTemp, pList, k )
736 Cut_ListForEachCutSafe( pList, pCut, pCut2 )
737 Cut_CutRecycle( p, pCut );
738 goto finish;
739 }
740 }
741 }
742 // collect larger cuts next
743 Vec_PtrForEachEntry( Cut_Cut_t *, p->vTemp, pList, i )
744 {
745 Cut_ListForEachCutSafe( pList, pCut, pCut2 )
746 {
747 // check containment
748 if ( p->pParams->fFilter && Cut_CutFilterOne( p, pSuper, pCut ) )
749 continue;
750 // set the complemented bit
751 pCut->fCompl = pTop->fSimul ^ pCut->fSimul;
752 pListStart = pCut->pNext;
753 pCut->pNext = NULL;
754 // add to the list
755 Cut_ListAdd( pSuper, pCut );
756 if ( ++p->nNodeCuts == p->pParams->nKeepMax )
757 {
758 // recycle the rest of the cuts
759 Cut_ListForEachCutSafe( pListStart, pCut, pCut2 )
760 Cut_CutRecycle( p, pCut );
761 // recycle the saved cuts of other nodes
762 Vec_PtrForEachEntryStart( Cut_Cut_t *, p->vTemp, pList, k, i+1 )
763 Cut_ListForEachCutSafe( pList, pCut, pCut2 )
764 Cut_CutRecycle( p, pCut );
765 goto finish;
766 }
767 }
768 }
769 finish :
770 // set the cuts at the node
771 assert( Cut_NodeReadCutsNew(p, Root) == NULL );
772 pList = Cut_ListFinish( pSuper );
773 Cut_NodeWriteCutsNew( p, Root, pList );
774 p->timeUnion += Abc_Clock() - clk;
775 // filter the cuts
776 //clk = Abc_Clock();
777 // if ( p->pParams->fFilter )
778 // Cut_CutFilter( p, pList );
779 //p->timeFilter += Abc_Clock() - clk;
780 p->nNodes -= vNodes->nSize - 1;
781 return pList;
782 }
783
784 /**Function*************************************************************
785
786 Synopsis [Computes the cuts by unioning cuts at a choice node.]
787
788 Description []
789
790 SideEffects []
791
792 SeeAlso []
793
794 ***********************************************************************/
Cut_NodeUnionCutsSeq(Cut_Man_t * p,Vec_Int_t * vNodes,int CutSetNum,int fFirst)795 Cut_Cut_t * Cut_NodeUnionCutsSeq( Cut_Man_t * p, Vec_Int_t * vNodes, int CutSetNum, int fFirst )
796 {
797 Cut_List_t Super, * pSuper = &Super;
798 Cut_Cut_t * pList, * pListStart, * pCut, * pCut2, * pTop;
799 int i, k, Node, Root, Limit = p->pParams->nVarsMax;
800 abctime clk = Abc_Clock();
801
802 // start the new list
803 Cut_ListStart( pSuper );
804
805 // remember the root node to save the resulting cuts
806 Root = Vec_IntEntry( vNodes, 0 );
807 p->nNodeCuts = 1;
808
809 // store the original lists for comparison
810 p->pCompareOld = Cut_NodeReadCutsOld( p, Root );
811 p->pCompareNew = (CutSetNum >= 0)? Cut_NodeReadCutsNew( p, Root ) : NULL;
812
813 // get the topmost cut
814 pTop = NULL;
815 if ( (pTop = Cut_NodeReadCutsOld( p, Root )) == NULL )
816 pTop = Cut_NodeReadCutsNew( p, Root );
817 assert( pTop != NULL );
818
819 // collect small cuts first
820 Vec_PtrClear( p->vTemp );
821 Vec_IntForEachEntry( vNodes, Node, i )
822 {
823 // get the cuts of this node
824 if ( i == 0 && CutSetNum >= 0 )
825 {
826 pList = Cut_NodeReadCutsTemp( p, CutSetNum );
827 Cut_NodeWriteCutsTemp( p, CutSetNum, NULL );
828 }
829 else
830 {
831 pList = Cut_NodeReadCutsNew( p, Node );
832 Cut_NodeWriteCutsNew( p, Node, NULL );
833 }
834 if ( pList == NULL )
835 continue;
836
837 // process the cuts
838 if ( fFirst )
839 {
840 // remember the starting point
841 pListStart = pList->pNext;
842 pList->pNext = NULL;
843 // save or recycle the elementary cut
844 if ( i == 0 )
845 Cut_ListAdd( pSuper, pList );
846 else
847 Cut_CutRecycle( p, pList );
848 }
849 else
850 pListStart = pList;
851
852 // save all the cuts that are smaller than the limit
853 Cut_ListForEachCutSafe( pListStart, pCut, pCut2 )
854 {
855 if ( pCut->nLeaves == (unsigned)Limit )
856 {
857 Vec_PtrPush( p->vTemp, pCut );
858 break;
859 }
860 // check containment
861 // if ( p->pParams->fFilter && Cut_CutFilterOne( p, pSuper, pCut ) )
862 // continue;
863 if ( p->pParams->fFilter )
864 {
865 if ( Cut_CutFilterOne(p, pSuper, pCut) )
866 continue;
867 if ( p->pParams->fSeq )
868 {
869 if ( p->pCompareOld && Cut_CutFilterOld(p, p->pCompareOld, pCut) )
870 continue;
871 if ( p->pCompareNew && Cut_CutFilterOld(p, p->pCompareNew, pCut) )
872 continue;
873 }
874 }
875
876 // set the complemented bit by comparing the first cut with the current cut
877 pCut->fCompl = pTop->fSimul ^ pCut->fSimul;
878 pListStart = pCut->pNext;
879 pCut->pNext = NULL;
880 // add to the list
881 Cut_ListAdd( pSuper, pCut );
882 if ( ++p->nNodeCuts == p->pParams->nKeepMax )
883 {
884 // recycle the rest of the cuts of this node
885 Cut_ListForEachCutSafe( pListStart, pCut, pCut2 )
886 Cut_CutRecycle( p, pCut );
887 // recycle all cuts of other nodes
888 Vec_IntForEachEntryStart( vNodes, Node, k, i+1 )
889 Cut_NodeFreeCuts( p, Node );
890 // recycle the saved cuts of other nodes
891 Vec_PtrForEachEntry( Cut_Cut_t *, p->vTemp, pList, k )
892 Cut_ListForEachCutSafe( pList, pCut, pCut2 )
893 Cut_CutRecycle( p, pCut );
894 goto finish;
895 }
896 }
897 }
898 // collect larger cuts next
899 Vec_PtrForEachEntry( Cut_Cut_t *, p->vTemp, pList, i )
900 {
901 Cut_ListForEachCutSafe( pList, pCut, pCut2 )
902 {
903 // check containment
904 // if ( p->pParams->fFilter && Cut_CutFilterOne( p, pSuper, pCut ) )
905 // continue;
906 if ( p->pParams->fFilter )
907 {
908 if ( Cut_CutFilterOne(p, pSuper, pCut) )
909 continue;
910 if ( p->pParams->fSeq )
911 {
912 if ( p->pCompareOld && Cut_CutFilterOld(p, p->pCompareOld, pCut) )
913 continue;
914 if ( p->pCompareNew && Cut_CutFilterOld(p, p->pCompareNew, pCut) )
915 continue;
916 }
917 }
918
919 // set the complemented bit
920 pCut->fCompl = pTop->fSimul ^ pCut->fSimul;
921 pListStart = pCut->pNext;
922 pCut->pNext = NULL;
923 // add to the list
924 Cut_ListAdd( pSuper, pCut );
925 if ( ++p->nNodeCuts == p->pParams->nKeepMax )
926 {
927 // recycle the rest of the cuts
928 Cut_ListForEachCutSafe( pListStart, pCut, pCut2 )
929 Cut_CutRecycle( p, pCut );
930 // recycle the saved cuts of other nodes
931 Vec_PtrForEachEntryStart( Cut_Cut_t *, p->vTemp, pList, k, i+1 )
932 Cut_ListForEachCutSafe( pList, pCut, pCut2 )
933 Cut_CutRecycle( p, pCut );
934 goto finish;
935 }
936 }
937 }
938 finish :
939 // set the cuts at the node
940 pList = Cut_ListFinish( pSuper );
941
942 // set the lists at the node
943 // assert( Cut_NodeReadCutsNew(p, Root) == NULL );
944 // Cut_NodeWriteCutsNew( p, Root, pList );
945 if ( CutSetNum >= 0 )
946 {
947 assert( Cut_NodeReadCutsTemp(p, CutSetNum) == NULL );
948 Cut_NodeWriteCutsTemp( p, CutSetNum, pList );
949 }
950 else
951 {
952 assert( Cut_NodeReadCutsNew(p, Root) == NULL );
953 Cut_NodeWriteCutsNew( p, Root, pList );
954 }
955
956 p->timeUnion += Abc_Clock() - clk;
957 // filter the cuts
958 //clk = Abc_Clock();
959 // if ( p->pParams->fFilter )
960 // Cut_CutFilter( p, pList );
961 //p->timeFilter += Abc_Clock() - clk;
962 // if ( fFirst )
963 // p->nNodes -= vNodes->nSize - 1;
964 return pList;
965 }
966
967
968 /**Function*************************************************************
969
970 Synopsis [Verifies that the list contains only non-dominated cuts.]
971
972 Description []
973
974 SideEffects []
975
976 SeeAlso []
977
978 ***********************************************************************/
Cut_CutListVerify(Cut_Cut_t * pList)979 int Cut_CutListVerify( Cut_Cut_t * pList )
980 {
981 Cut_Cut_t * pCut, * pDom;
982 Cut_ListForEachCut( pList, pCut )
983 {
984 Cut_ListForEachCutStop( pList, pDom, pCut )
985 {
986 if ( Cut_CutCheckDominance( pDom, pCut ) )
987 {
988 printf( "******************* These are contained cuts:\n" );
989 Cut_CutPrint( pDom, 1 );
990 Cut_CutPrint( pDom, 1 );
991 return 0;
992 }
993 }
994 }
995 return 1;
996 }
997
998 ////////////////////////////////////////////////////////////////////////
999 /// END OF FILE ///
1000 ////////////////////////////////////////////////////////////////////////
1001
1002
1003 ABC_NAMESPACE_IMPL_END
1004
1005