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