abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
cutNode.c
Go to the documentation of this file.
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 
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 ***********************************************************************/
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 ***********************************************************************/
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 ***********************************************************************/
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 ***********************************************************************/
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 ***********************************************************************/
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 ***********************************************************************/
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 ***********************************************************************/
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 ***********************************************************************/
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  {
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  {
395  Cut_ListForEachCut( pList, pCut )
396  Vec_IntPush( p->vCutPairs, ((pCut->Num1 << 16) | pCut->Num0) );
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 )
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 ***********************************************************************/
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 ***********************************************************************/
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 ***********************************************************************/
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 ***********************************************************************/
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 ***********************************************************************/
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 ***********************************************************************/
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 ***********************************************************************/
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 
1004 
ABC_NAMESPACE_IMPL_START Cut_Cut_t * Cut_CutAlloc(Cut_Man_t *p)
DECLARATIONS ///.
Definition: cutCut.c:45
static Cut_Cut_t * Cut_ListFinish(Cut_List_t *p)
Definition: cutList.h:191
Cut_Cut_t * Cut_NodeUnionCuts(Cut_Man_t *p, Vec_Int_t *vNodes)
Definition: cutNode.c:678
static int Cut_CutCheckDominance(Cut_Cut_t *pDom, Cut_Cut_t *pCut)
FUNCTION DEFINITIONS ///.
Definition: cutNode.c:48
Cut_Cut_t * Cut_NodeReadCutsTemp(Cut_Man_t *p, int Node)
Definition: cutApi.c:80
Cut_Cut_t * Cut_NodeReadCutsOld(Cut_Man_t *p, int Node)
Definition: cutApi.c:63
static void Cut_ListAdd(Cut_List_t *p, Cut_Cut_t *pCut)
Definition: cutList.h:87
Vec_Ptr_t * vCutsMax
Definition: cutInt.h:79
Cut_Cut_t * Cut_NodeComputeCuts(Cut_Man_t *p, int Node, int Node0, int Node1, int fCompl0, int fCompl1, int fTriv, int TreeCode)
Definition: cutNode.c:369
static int Cut_CutFilterGlobal(Cut_Man_t *p, Cut_Cut_t *pCut)
Definition: cutNode.c:224
#define Cut_ListForEachCutStop(pList, pCut, pStop)
Definition: cutInt.h:108
Vec_Ptr_t * vTemp
Definition: cutInt.h:64
typedefABC_NAMESPACE_HEADER_START struct Cut_ListStruct_t_ Cut_List_t
INCLUDES ///.
Definition: cutList.h:40
#define Vec_PtrForEachEntryStart(Type, vVec, pEntry, i, Start)
Definition: vecPtr.h:57
static int Cut_CutProcessTwo(Cut_Man_t *p, Cut_Cut_t *pCut0, Cut_Cut_t *pCut1, Cut_List_t *pSuperList)
Definition: cutNode.c:312
static Llb_Mgr_t * p
Definition: llb3Image.c:950
static int Cut_CutFilterOne(Cut_Man_t *p, Cut_List_t *pSuperList, Cut_Cut_t *pCut)
Definition: cutNode.c:152
#define Cut_ListForEachCutSafe(pList, pCut, pCut2)
Definition: cutInt.h:112
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
int Cut_CutListVerify(Cut_Cut_t *pList)
Definition: cutNode.c:979
static int Cut_CutFilterOneEqual(Cut_Man_t *p, Cut_List_t *pSuperList, Cut_Cut_t *pCut)
Definition: cutNode.c:122
static unsigned * Cut_CutReadTruth(Cut_Cut_t *p)
Definition: cut.h:94
static void Vec_PtrFillExtra(Vec_Ptr_t *p, int nSize, void *Fill)
Definition: vecPtr.h:469
Cut_Cut_t * pNext
Definition: cut.h:88
unsigned fSimul
Definition: cut.h:81
static void Vec_PtrPush(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:606
Cut_Cut_t * Cut_NodeUnionCutsSeq(Cut_Man_t *p, Vec_Int_t *vNodes, int CutSetNum, int fFirst)
Definition: cutNode.c:795
static abctime Abc_Clock()
Definition: abc_global.h:279
void Cut_NodeWriteCutsTemp(Cut_Man_t *p, int Node, Cut_Cut_t *pList)
Definition: cutApi.c:129
Vec_Int_t * vNodeStarts
Definition: cutInt.h:76
static void Cut_CutFilter(Cut_Man_t *p, Cut_Cut_t *pList)
Definition: cutNode.c:74
Vec_Int_t * vNodeAttrs
Definition: cutInt.h:53
int nNodesNoCuts
Definition: cutInt.h:93
void Cut_TruthCompute(Cut_Man_t *p, Cut_Cut_t *pCut, Cut_Cut_t *pCut0, Cut_Cut_t *pCut1, int fCompl0, int fCompl1)
Definition: cutTruth.c:177
static void Vec_IntWriteEntry(Vec_Int_t *p, int i, int Entry)
Definition: bblif.c:285
int fRecordAig
Definition: cut.h:69
static int Cut_CutReadLeaveNum(Cut_Cut_t *p)
Definition: cut.h:92
int pLeaves[0]
Definition: cut.h:89
void Aig_RManRecord(unsigned *pTruth, int nVarsInit)
Definition: aigCanon.c:598
unsigned nLeaves
Definition: cut.h:84
abctime timeMerge
Definition: cutInt.h:95
unsigned Num0
Definition: cut.h:79
unsigned uSign
Definition: cut.h:85
Vec_Int_t * vCutPairs
Definition: cutInt.h:77
void Cut_NodeFreeCuts(Cut_Man_t *p, int Node)
Definition: cutApi.c:184
Vec_Int_t * vDelays
Definition: cutInt.h:80
static int Vec_IntEntry(Vec_Int_t *p, int i)
Definition: bblif.c:268
static ABC_NAMESPACE_IMPL_START int Cut_NodeMapping(Cut_Man_t *p, Cut_Cut_t *pCuts, int Node, int Node0, int Node1)
DECLARATIONS ///.
Definition: cutNode.c:489
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
static void Vec_IntPush(Vec_Int_t *p, int Entry)
Definition: bblif.c:468
static int Counter
void Cut_CutNumberList(Cut_Cut_t *pList)
Definition: cutCut.c:219
Cut_Cut_t * pCompareNew
Definition: cutInt.h:72
#define Vec_IntForEachEntryStart(vVec, Entry, i, Start)
Definition: vecInt.h:56
void Cut_CutPrint(Cut_Cut_t *pCut, int fSeq)
Definition: cutCut.c:276
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)
Definition: cutNode.c:572
Cut_Cut_t * Cut_CutCreateTriv(Cut_Man_t *p, int Node)
Definition: cutCut.c:238
void Cut_CutRecycle(Cut_Man_t *p, Cut_Cut_t *pCut)
Definition: cutCut.c:72
static void Vec_PtrWriteEntry(Vec_Ptr_t *p, int i, void *Entry)
Definition: vecPtr.h:396
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
Cut_Cut_t * pCompareOld
Definition: cutInt.h:71
int Cut_ManMappingArea_rec(Cut_Man_t *p, int Node)
Definition: cutNode.c:544
static void * Vec_PtrEntry(Vec_Ptr_t *p, int i)
Definition: vecPtr.h:362
static void Cut_ListStart(Cut_List_t *p)
MACRO DEFINITIONS ///.
Definition: cutList.h:66
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
Vec_Int_t * vDelays2
Definition: cutInt.h:81
static int Cut_NodeMapping2(Cut_Man_t *p, Cut_Cut_t *pCuts, int Node, int Node0, int Node1)
Definition: cutNode.c:446
Cut_Cut_t * Cut_CutMergeTwo(Cut_Man_t *p, Cut_Cut_t *pCut0, Cut_Cut_t *pCut1)
Definition: cutMerge.c:170
unsigned fCompl
Definition: cut.h:82
abctime timeUnion
Definition: cutInt.h:96
static int Cut_CutFilterOld(Cut_Man_t *p, Cut_Cut_t *pList, Cut_Cut_t *pCut)
Definition: cutNode.c:250
Vec_Int_t * vNodeCuts
Definition: cutInt.h:75
Cut_Params_t * pParams
Definition: cutInt.h:51
#define assert(ex)
Definition: util_old.h:213
static void Vec_PtrClear(Vec_Ptr_t *p)
Definition: vecPtr.h:545
#define Cut_ListForEachCut(pList, pCut)
Definition: cutInt.h:104
unsigned Num1
Definition: cut.h:80
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
ABC_INT64_T abctime
Definition: abc_global.h:278
void Cut_NodeWriteCutsNew(Cut_Man_t *p, int Node, Cut_Cut_t *pList)
Definition: cutApi.c:97
#define Vec_IntForEachEntry(vVec, Entry, i)
MACRO DEFINITIONS ///.
Definition: vecInt.h:54
Cut_Cut_t * Cut_NodeReadCutsNew(Cut_Man_t *p, int Node)
MACRO DEFINITIONS ///.
Definition: cutApi.c:45
unsigned nVarsMax
Definition: cut.h:83
int nCutsFilter
Definition: cutInt.h:89
Vec_Ptr_t * vCutsNew
Definition: cutInt.h:55
abctime timeMap
Definition: cutInt.h:100
int nCutsLimit
Definition: cutInt.h:90