abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
fpgaCut.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [fpgaCut.c]
4 
5  PackageName [MVSIS 1.3: Multi-valued logic synthesis system.]
6 
7  Synopsis [Generic technology mapping engine.]
8 
9  Author [MVSIS Group]
10 
11  Affiliation [UC Berkeley]
12 
13  Date [Ver. 2.0. Started - August 18, 2004.]
14 
15  Revision [$Id: fpgaCut.c,v 1.3 2004/07/06 04:55:57 alanmi Exp $]
16 
17 ***********************************************************************/
18 
19 #include "fpgaInt.h"
20 
21 ABC_NAMESPACE_IMPL_START
22 
23 
24 ////////////////////////////////////////////////////////////////////////
25 /// DECLARATIONS ///
26 ////////////////////////////////////////////////////////////////////////
27 
28 typedef struct Fpga_CutTableStrutct_t Fpga_CutTable_t;
29 struct Fpga_CutTableStrutct_t
30 {
31  Fpga_Cut_t ** pBins; // the table used for linear probing
32  int nBins; // the size of the table
33  int * pCuts; // the array of cuts currently stored
34  int nCuts; // the number of cuts currently stored
35  Fpga_Cut_t ** pArray; // the temporary array of cuts
36  Fpga_Cut_t ** pCuts1; // the temporary array of cuts
37  Fpga_Cut_t ** pCuts2; // the temporary array of cuts
38 };
39 
40 // the largest number of cuts considered
41 //#define FPGA_CUTS_MAX_COMPUTE 500
42 #define FPGA_CUTS_MAX_COMPUTE 2000
43 // the largest number of cuts used
44 //#define FPGA_CUTS_MAX_USE 200
45 #define FPGA_CUTS_MAX_USE 1000
46 
47 // primes used to compute the hash key
48 static int s_HashPrimes[10] = { 109, 499, 557, 619, 631, 709, 797, 881, 907, 991 };
49 
50 static int bit_count[256] = {
51  0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
52  1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
53  1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
54  2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
55  1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
56  2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
57  2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
58  3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
59 };
60 
61 #define FPGA_COUNT_ONES(u) (bit_count[(u)&255]+bit_count[((u)>>8)&255]+bit_count[((u)>>16)&255]+bit_count[(u)>>24])
62 
63 static Fpga_Cut_t * Fpga_CutCompute( Fpga_Man_t * p, Fpga_CutTable_t * pTable, Fpga_Node_t * pNode );
64 static void Fpga_CutFilter( Fpga_Man_t * p, Fpga_Node_t * pNode );
65 static Fpga_Cut_t * Fpga_CutMergeLists( Fpga_Man_t * p, Fpga_CutTable_t * pTable, Fpga_Cut_t * pList1, Fpga_Cut_t * pList2, int fComp1, int fComp2, int fPivot1, int fPivot2 );
66 static int Fpga_CutMergeTwo( Fpga_Cut_t * pCut1, Fpga_Cut_t * pCut2, Fpga_Node_t * ppNodes[], int nNodesMax );
67 static Fpga_Cut_t * Fpga_CutUnionLists( Fpga_Cut_t * pList1, Fpga_Cut_t * pList2 );
68 static int Fpga_CutBelongsToList( Fpga_Cut_t * pList, Fpga_Node_t * ppNodes[], int nNodes );
69 extern Fpga_Cut_t * Fpga_CutAlloc( Fpga_Man_t * p );
70 extern int Fpga_CutCountAll( Fpga_Man_t * pMan );
71 
72 static void Fpga_CutListPrint( Fpga_Man_t * pMan, Fpga_Node_t * pRoot );
73 static void Fpga_CutListPrint2( Fpga_Man_t * pMan, Fpga_Node_t * pRoot );
74 static void Fpga_CutPrint_( Fpga_Man_t * pMan, Fpga_Cut_t * pCut, Fpga_Node_t * pRoot );
75 
76 static Fpga_CutTable_t * Fpga_CutTableStart( Fpga_Man_t * pMan );
77 static void Fpga_CutTableStop( Fpga_CutTable_t * p );
78 static unsigned Fpga_CutTableHash( Fpga_Node_t * ppNodes[], int nNodes );
79 static int Fpga_CutTableLookup( Fpga_CutTable_t * p, Fpga_Node_t * ppNodes[], int nNodes );
80 static Fpga_Cut_t * Fpga_CutTableConsider( Fpga_Man_t * pMan, Fpga_CutTable_t * p, Fpga_Node_t * ppNodes[], int nNodes );
81 static void Fpga_CutTableRestart( Fpga_CutTable_t * p );
82 
83 static int Fpga_CutSortCutsCompare( Fpga_Cut_t ** pC1, Fpga_Cut_t ** pC2 );
84 static Fpga_Cut_t * Fpga_CutSortCuts( Fpga_Man_t * pMan, Fpga_CutTable_t * p, Fpga_Cut_t * pList );
85 static int Fpga_CutList2Array( Fpga_Cut_t ** pArray, Fpga_Cut_t * pList );
86 static Fpga_Cut_t * Fpga_CutArray2List( Fpga_Cut_t ** pArray, int nCuts );
87 
88 
89 // iterator through all the cuts of the list
90 #define Fpga_ListForEachCut( pList, pCut ) \
91  for ( pCut = pList; \
92  pCut; \
93  pCut = pCut->pNext )
94 #define Fpga_ListForEachCutSafe( pList, pCut, pCut2 ) \
95  for ( pCut = pList, \
96  pCut2 = pCut? pCut->pNext: NULL; \
97  pCut; \
98  pCut = pCut2, \
99  pCut2 = pCut? pCut->pNext: NULL )
100 
101 
102 ////////////////////////////////////////////////////////////////////////
103 /// FUNCTION DEFINITIONS ///
104 ////////////////////////////////////////////////////////////////////////
105 
106 /**Function*************************************************************
107 
108  Synopsis [Computes the cuts for each node in the object graph.]
109 
110  Description [The cuts are computed in one sweep over the mapping graph.
111  First, the elementary cuts, which include the node itself, are assigned
112  to the PI nodes. The internal nodes are considered in the DFS order.
113  Each node is two-input AND-gate. So to compute the cuts at a node, we
114  need to merge the sets of cuts of its two predecessors. The merged set
115  contains only unique cuts with the number of inputs equal to k or less.
116  Finally, the elementary cut, composed of the node itself, is added to
117  the set of cuts for the node.
118 
119  This procedure is pretty fast for 5-feasible cuts, but it dramatically
120  slows down on some "dense" networks when computing 6-feasible cuts.
121  The problem is that there are too many cuts in this case. We should
122  think how to heuristically trim the number of cuts in such cases,
123  to have reasonable runtime.]
124 
125  SideEffects []
126 
127  SeeAlso []
128 
129 ***********************************************************************/
130 void Fpga_MappingCuts( Fpga_Man_t * p )
131 {
132  ProgressBar * pProgress;
133  Fpga_CutTable_t * pTable;
134  Fpga_Node_t * pNode;
135  int nCuts, nNodes, i;
136  clock_t clk = clock();
137 
138  // set the elementary cuts for the PI variables
139  assert( p->nVarsMax > 1 && p->nVarsMax < 11 );
140  Fpga_MappingCreatePiCuts( p );
141 
142  // compute the cuts for the internal nodes
143  nNodes = p->vAnds->nSize;
144  pProgress = Extra_ProgressBarStart( stdout, nNodes );
145  pTable = Fpga_CutTableStart( p );
146  for ( i = 0; i < nNodes; i++ )
147  {
148  Extra_ProgressBarUpdate( pProgress, i, "Cuts ..." );
149  pNode = p->vAnds->pArray[i];
150  if ( !Fpga_NodeIsAnd( pNode ) )
151  continue;
152  Fpga_CutCompute( p, pTable, pNode );
153  }
154  Extra_ProgressBarStop( pProgress );
155  Fpga_CutTableStop( pTable );
156 
157  // report the stats
158  if ( p->fVerbose )
159  {
160  nCuts = Fpga_CutCountAll(p);
161  printf( "Nodes = %6d. Total %d-cuts = %d. Cuts per node = %.1f. ",
162  p->nNodes, p->nVarsMax, nCuts, ((float)nCuts)/p->nNodes );
163  ABC_PRT( "Time", clock() - clk );
164  }
165 
166  // print the cuts for the first primary output
167 // Fpga_CutListPrint( p, Fpga_Regular(p->pOutputs[0]) );
168 }
169 
170 /**Function*************************************************************
171 
172  Synopsis [Performs technology mapping for variable-size-LUTs.]
173 
174  Description []
175 
176  SideEffects []
177 
178  SeeAlso []
179 
180 ***********************************************************************/
181 void Fpga_MappingCreatePiCuts( Fpga_Man_t * p )
182 {
183  Fpga_Cut_t * pCut;
184  int i;
185 
186  // set the elementary cuts for the PI variables
187  for ( i = 0; i < p->nInputs; i++ )
188  {
189  pCut = Fpga_CutAlloc( p );
190  pCut->nLeaves = 1;
191  pCut->ppLeaves[0] = p->pInputs[i];
192  pCut->uSign = (1 << (i%31));
193  p->pInputs[i]->pCuts = pCut;
194  p->pInputs[i]->pCutBest = pCut;
195  // set the input arrival times
196 // p->pInputs[i]->pCut[1]->tArrival = p->pInputArrivals[i];
197  }
198 }
199 
200 /**Function*************************************************************
201 
202  Synopsis [Computes the cuts for one node.]
203 
204  Description []
205 
206  SideEffects []
207 
208  SeeAlso []
209 
210 ***********************************************************************/
211 Fpga_Cut_t * Fpga_CutCompute( Fpga_Man_t * p, Fpga_CutTable_t * pTable, Fpga_Node_t * pNode )
212 {
213  Fpga_Node_t * pTemp;
214  Fpga_Cut_t * pList, * pList1, * pList2;
215  Fpga_Cut_t * pCut;
216  int fTree = 0;
217  int fPivot1 = fTree && (Fpga_NodeReadRef(pNode->p1)>2);
218  int fPivot2 = fTree && (Fpga_NodeReadRef(pNode->p2)>2);
219 
220  // if the cuts are computed return them
221  if ( pNode->pCuts )
222  return pNode->pCuts;
223 
224  // compute the cuts for the children
225  pList1 = Fpga_Regular(pNode->p1)->pCuts;
226  pList2 = Fpga_Regular(pNode->p2)->pCuts;
227  // merge the lists
228  pList = Fpga_CutMergeLists( p, pTable, pList1, pList2,
229  Fpga_IsComplement(pNode->p1), Fpga_IsComplement(pNode->p2),
230  fPivot1, fPivot2 );
231  // if there are functionally equivalent nodes, union them with this list
232  assert( pList );
233  // only add to the list of cuts if the node is a representative one
234  if ( pNode->pRepr == NULL )
235  {
236  for ( pTemp = pNode->pNextE; pTemp; pTemp = pTemp->pNextE )
237  {
238  assert( pTemp->pCuts );
239  pList = Fpga_CutUnionLists( pList, pTemp->pCuts );
240  assert( pTemp->pCuts );
241  pList = Fpga_CutSortCuts( p, pTable, pList );
242  }
243  }
244  // add the new cut
245  pCut = Fpga_CutAlloc( p );
246  pCut->nLeaves = 1;
247  pCut->ppLeaves[0] = pNode;
248  pCut->uSign = (1 << (pNode->Num%31));
249  pCut->fLevel = (float)pCut->ppLeaves[0]->Level;
250  // append (it is important that the elementary cut is appended first)
251  pCut->pNext = pList;
252  // set at the node
253  pNode->pCuts = pCut;
254  // remove the dominated cuts
255 // Fpga_CutFilter( p, pNode );
256  // set the phase correctly
257  if ( pNode->pRepr && Fpga_NodeComparePhase(pNode, pNode->pRepr) )
258  {
259  Fpga_ListForEachCut( pNode->pCuts, pCut )
260  pCut->Phase = 1;
261  }
262 
263 
264 /*
265  {
266  Fpga_Cut_t * pPrev;
267  int i, Counter = 0;
268  for ( pCut = pNode->pCuts->pNext, pPrev = pNode->pCuts; pCut; pCut = pCut->pNext )
269  {
270  for ( i = 0; i < pCut->nLeaves; i++ )
271  if ( pCut->ppLeaves[i]->Level >= pNode->Level )
272  break;
273  if ( i != pCut->nLeaves )
274  pPrev->pNext = pCut->pNext;
275  else
276  pPrev = pCut;
277  }
278  }
279  {
280  int i, Counter = 0;;
281  for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext )
282  for ( i = 0; i < pCut->nLeaves; i++ )
283  Counter += (pCut->ppLeaves[i]->Level >= pNode->Level);
284  if ( Counter )
285  printf( " %d", Counter );
286  }
287 */
288 
289  return pCut;
290 }
291 
292 /**Function*************************************************************
293 
294  Synopsis [Filter the cuts using dominance.]
295 
296  Description []
297 
298  SideEffects []
299 
300  SeeAlso []
301 
302 ***********************************************************************/
303 void Fpga_CutFilter( Fpga_Man_t * p, Fpga_Node_t * pNode )
304 {
305  Fpga_Cut_t * pTemp, * pPrev, * pCut, * pCut2;
306  int i, k, Counter;
307 
308  Counter = 0;
309  pPrev = pNode->pCuts;
310  Fpga_ListForEachCutSafe( pNode->pCuts->pNext, pCut, pCut2 )
311  {
312  // go through all the previous cuts up to pCut
313  for ( pTemp = pNode->pCuts->pNext; pTemp != pCut; pTemp = pTemp->pNext )
314  {
315  // check if every node in pTemp is contained in pCut
316  for ( i = 0; i < pTemp->nLeaves; i++ )
317  {
318  for ( k = 0; k < pCut->nLeaves; k++ )
319  if ( pTemp->ppLeaves[i] == pCut->ppLeaves[k] )
320  break;
321  if ( k == pCut->nLeaves ) // node i in pTemp is not contained in pCut
322  break;
323  }
324  if ( i == pTemp->nLeaves ) // every node in pTemp is contained in pCut
325  {
326  Counter++;
327  break;
328  }
329  }
330  if ( pTemp != pCut ) // pTemp contain pCut
331  {
332  pPrev->pNext = pCut->pNext; // skip pCut
333  // recycle pCut
334  Fpga_CutFree( p, pCut );
335  }
336  else
337  pPrev = pCut;
338  }
339 // printf( "Dominated = %3d. \n", Counter );
340 }
341 
342 
343 /**Function*************************************************************
344 
345  Synopsis [Merges two lists of cuts.]
346 
347  Description []
348 
349  SideEffects []
350 
351  SeeAlso []
352 
353 ***********************************************************************/
354 Fpga_Cut_t * Fpga_CutMergeLists( Fpga_Man_t * p, Fpga_CutTable_t * pTable,
355  Fpga_Cut_t * pList1, Fpga_Cut_t * pList2, int fComp1, int fComp2, int fPivot1, int fPivot2 )
356 {
357  Fpga_Node_t * ppNodes[FPGA_MAX_LEAVES];
358  Fpga_Cut_t * pListNew, ** ppListNew, * pLists[FPGA_MAX_LEAVES+1] = { NULL };
359  Fpga_Cut_t * pCut, * pPrev, * pTemp1, * pTemp2;
360  int nNodes, Counter, i;
361  Fpga_Cut_t ** ppArray1, ** ppArray2, ** ppArray3;
362  int nCuts1, nCuts2, nCuts3, k, fComp3;
363 
364  ppArray1 = pTable->pCuts1;
365  ppArray2 = pTable->pCuts2;
366  nCuts1 = Fpga_CutList2Array( ppArray1, pList1 );
367  nCuts2 = Fpga_CutList2Array( ppArray2, pList2 );
368  if ( fPivot1 )
369  nCuts1 = 1;
370  if ( fPivot2 )
371  nCuts2 = 1;
372  // swap the lists based on their length
373  if ( nCuts1 > nCuts2 )
374  {
375  ppArray3 = ppArray1;
376  ppArray1 = ppArray2;
377  ppArray2 = ppArray3;
378 
379  nCuts3 = nCuts1;
380  nCuts1 = nCuts2;
381  nCuts2 = nCuts3;
382 
383  fComp3 = fComp1;
384  fComp1 = fComp2;
385  fComp2 = fComp3;
386  }
387  // pList1 is shorter or equal length compared to pList2
388 
389  // prepare the manager for the cut computation
390  Fpga_CutTableRestart( pTable );
391  // go through the cut pairs
392  Counter = 0;
393 // for ( pTemp1 = pList1; pTemp1; pTemp1 = fPivot1? NULL: pTemp1->pNext )
394 // for ( pTemp2 = pList2; pTemp2; pTemp2 = fPivot2? NULL: pTemp2->pNext )
395  for ( i = 0; i < nCuts1; i++ )
396  {
397  for ( k = 0; k <= i; k++ )
398  {
399  pTemp1 = ppArray1[i];
400  pTemp2 = ppArray2[k];
401 
402  if ( pTemp1->nLeaves == p->nVarsMax && pTemp2->nLeaves == p->nVarsMax )
403  {
404  if ( pTemp1->ppLeaves[0] != pTemp2->ppLeaves[0] )
405  continue;
406  if ( pTemp1->ppLeaves[1] != pTemp2->ppLeaves[1] )
407  continue;
408  }
409 
410  // check if k-feasible cut exists
411  nNodes = Fpga_CutMergeTwo( pTemp1, pTemp2, ppNodes, p->nVarsMax );
412  if ( nNodes == 0 )
413  continue;
414  // consider the cut for possible addition to the set of new cuts
415  pCut = Fpga_CutTableConsider( p, pTable, ppNodes, nNodes );
416  if ( pCut == NULL )
417  continue;
418  // add data to the cut
419  pCut->pOne = Fpga_CutNotCond( pTemp1, fComp1 );
420  pCut->pTwo = Fpga_CutNotCond( pTemp2, fComp2 );
421  // create the signature
422  pCut->uSign = pTemp1->uSign | pTemp2->uSign;
423  // add it to the corresponding list
424  pCut->pNext = pLists[(int)pCut->nLeaves];
425  pLists[(int)pCut->nLeaves] = pCut;
426  // count this cut and quit if limit is reached
427  Counter++;
428  if ( Counter == FPGA_CUTS_MAX_COMPUTE )
429  goto QUITS;
430  }
431  for ( k = 0; k < i; k++ )
432  {
433  pTemp1 = ppArray1[k];
434  pTemp2 = ppArray2[i];
435 
436  if ( pTemp1->nLeaves == p->nVarsMax && pTemp2->nLeaves == p->nVarsMax )
437  {
438  if ( pTemp1->ppLeaves[0] != pTemp2->ppLeaves[0] )
439  continue;
440  if ( pTemp1->ppLeaves[1] != pTemp2->ppLeaves[1] )
441  continue;
442  }
443 
444 
445  // check if k-feasible cut exists
446  nNodes = Fpga_CutMergeTwo( pTemp1, pTemp2, ppNodes, p->nVarsMax );
447  if ( nNodes == 0 )
448  continue;
449  // consider the cut for possible addition to the set of new cuts
450  pCut = Fpga_CutTableConsider( p, pTable, ppNodes, nNodes );
451  if ( pCut == NULL )
452  continue;
453  // add data to the cut
454  pCut->pOne = Fpga_CutNotCond( pTemp1, fComp1 );
455  pCut->pTwo = Fpga_CutNotCond( pTemp2, fComp2 );
456  // create the signature
457  pCut->uSign = pTemp1->uSign | pTemp2->uSign;
458  // add it to the corresponding list
459  pCut->pNext = pLists[(int)pCut->nLeaves];
460  pLists[(int)pCut->nLeaves] = pCut;
461  // count this cut and quit if limit is reached
462  Counter++;
463  if ( Counter == FPGA_CUTS_MAX_COMPUTE )
464  goto QUITS;
465  }
466  }
467  // consider the rest of them
468  for ( i = nCuts1; i < nCuts2; i++ )
469  for ( k = 0; k < nCuts1; k++ )
470  {
471  pTemp1 = ppArray1[k];
472  pTemp2 = ppArray2[i];
473 
474  if ( pTemp1->nLeaves == p->nVarsMax && pTemp2->nLeaves == p->nVarsMax )
475  {
476  if ( pTemp1->ppLeaves[0] != pTemp2->ppLeaves[0] )
477  continue;
478  if ( pTemp1->ppLeaves[1] != pTemp2->ppLeaves[1] )
479  continue;
480  if ( pTemp1->ppLeaves[2] != pTemp2->ppLeaves[2] )
481  continue;
482  }
483 
484 
485  // check if k-feasible cut exists
486  nNodes = Fpga_CutMergeTwo( pTemp1, pTemp2, ppNodes, p->nVarsMax );
487  if ( nNodes == 0 )
488  continue;
489  // consider the cut for possible addition to the set of new cuts
490  pCut = Fpga_CutTableConsider( p, pTable, ppNodes, nNodes );
491  if ( pCut == NULL )
492  continue;
493  // add data to the cut
494  pCut->pOne = Fpga_CutNotCond( pTemp1, fComp1 );
495  pCut->pTwo = Fpga_CutNotCond( pTemp2, fComp2 );
496  // create the signature
497  pCut->uSign = pTemp1->uSign | pTemp2->uSign;
498  // add it to the corresponding list
499  pCut->pNext = pLists[(int)pCut->nLeaves];
500  pLists[(int)pCut->nLeaves] = pCut;
501  // count this cut and quit if limit is reached
502  Counter++;
503  if ( Counter == FPGA_CUTS_MAX_COMPUTE )
504  goto QUITS;
505  }
506 QUITS :
507  // combine all the lists into one
508  pListNew = NULL;
509  ppListNew = &pListNew;
510  for ( i = 1; i <= p->nVarsMax; i++ )
511  {
512  if ( pLists[i] == NULL )
513  continue;
514  // find the last entry
515  for ( pPrev = pLists[i], pCut = pPrev->pNext; pCut;
516  pPrev = pCut, pCut = pCut->pNext );
517  // connect these lists
518  *ppListNew = pLists[i];
519  ppListNew = &pPrev->pNext;
520  }
521  *ppListNew = NULL;
522  // sort the cuts by arrival times and use only the first FPGA_CUTS_MAX_USE
523  pListNew = Fpga_CutSortCuts( p, pTable, pListNew );
524  return pListNew;
525 }
526 
527 
528 /**Function*************************************************************
529 
530  Synopsis [Merges two lists of cuts.]
531 
532  Description []
533 
534  SideEffects []
535 
536  SeeAlso []
537 
538 ***********************************************************************/
539 Fpga_Cut_t * Fpga_CutMergeLists2( Fpga_Man_t * p, Fpga_CutTable_t * pTable,
540  Fpga_Cut_t * pList1, Fpga_Cut_t * pList2, int fComp1, int fComp2, int fPivot1, int fPivot2 )
541 {
542  Fpga_Node_t * ppNodes[FPGA_MAX_LEAVES];
543  Fpga_Cut_t * pListNew, ** ppListNew, * pLists[FPGA_MAX_LEAVES+1] = { NULL };
544  Fpga_Cut_t * pCut, * pPrev, * pTemp1, * pTemp2;
545  int nNodes, Counter, i;
546 
547  // prepare the manager for the cut computation
548  Fpga_CutTableRestart( pTable );
549  // go through the cut pairs
550  Counter = 0;
551  for ( pTemp1 = pList1; pTemp1; pTemp1 = fPivot1? NULL: pTemp1->pNext )
552  for ( pTemp2 = pList2; pTemp2; pTemp2 = fPivot2? NULL: pTemp2->pNext )
553  {
554  // check if k-feasible cut exists
555  nNodes = Fpga_CutMergeTwo( pTemp1, pTemp2, ppNodes, p->nVarsMax );
556  if ( nNodes == 0 )
557  continue;
558  // consider the cut for possible addition to the set of new cuts
559  pCut = Fpga_CutTableConsider( p, pTable, ppNodes, nNodes );
560  if ( pCut == NULL )
561  continue;
562  // add data to the cut
563  pCut->pOne = Fpga_CutNotCond( pTemp1, fComp1 );
564  pCut->pTwo = Fpga_CutNotCond( pTemp2, fComp2 );
565  // add it to the corresponding list
566  pCut->pNext = pLists[(int)pCut->nLeaves];
567  pLists[(int)pCut->nLeaves] = pCut;
568  // count this cut and quit if limit is reached
569  Counter++;
570  if ( Counter == FPGA_CUTS_MAX_COMPUTE )
571  goto QUITS;
572  }
573 QUITS :
574  // combine all the lists into one
575  pListNew = NULL;
576  ppListNew = &pListNew;
577  for ( i = 1; i <= p->nVarsMax; i++ )
578  {
579  if ( pLists[i] == NULL )
580  continue;
581  // find the last entry
582  for ( pPrev = pLists[i], pCut = pPrev->pNext; pCut;
583  pPrev = pCut, pCut = pCut->pNext );
584  // connect these lists
585  *ppListNew = pLists[i];
586  ppListNew = &pPrev->pNext;
587  }
588  *ppListNew = NULL;
589  // sort the cuts by arrival times and use only the first FPGA_CUTS_MAX_USE
590  pListNew = Fpga_CutSortCuts( p, pTable, pListNew );
591  return pListNew;
592 }
593 
594 /**Function*************************************************************
595 
596  Synopsis [Merges two cuts.]
597 
598  Description [Returns the number of nodes in the resulting cut, or 0 if the
599  cut is infeasible. Returns the resulting nodes in the array ppNodes[].]
600 
601  SideEffects []
602 
603  SeeAlso []
604 
605 ***********************************************************************/
606 int Fpga_CutMergeTwo( Fpga_Cut_t * pCut1, Fpga_Cut_t * pCut2, Fpga_Node_t * ppNodes[], int nNodesMax )
607 {
608  Fpga_Node_t * pNodeTemp;
609  int nTotal, i, k, min, Counter;
610  unsigned uSign;
611 
612  // use quick prefiltering
613  uSign = pCut1->uSign | pCut2->uSign;
614  Counter = FPGA_COUNT_ONES(uSign);
615  if ( Counter > nNodesMax )
616  return 0;
617 /*
618  // check the special case when at least of the cuts is the largest
619  if ( pCut1->nLeaves == nNodesMax )
620  {
621  if ( pCut2->nLeaves == nNodesMax )
622  {
623  // return 0 if the cuts are different
624  for ( i = 0; i < nNodesMax; i++ )
625  if ( pCut1->ppLeaves[i] != pCut2->ppLeaves[i] )
626  return 0;
627  // return nNodesMax if they are the same
628  for ( i = 0; i < nNodesMax; i++ )
629  ppNodes[i] = pCut1->ppLeaves[i];
630  return nNodesMax;
631  }
632  else if ( pCut2->nLeaves == nNodesMax - 1 )
633  {
634  // return 0 if the cuts are different
635  fMismatch = 0;
636  for ( i = 0; i < nNodesMax; i++ )
637  if ( pCut1->ppLeaves[i] != pCut2->ppLeaves[i - fMismatch] )
638  {
639  if ( fMismatch == 1 )
640  return 0;
641  fMismatch = 1;
642  }
643  // return nNodesMax if they are the same
644  for ( i = 0; i < nNodesMax; i++ )
645  ppNodes[i] = pCut1->ppLeaves[i];
646  return nNodesMax;
647  }
648  }
649  else if ( pCut1->nLeaves == nNodesMax - 1 && pCut2->nLeaves == nNodesMax )
650  {
651  // return 0 if the cuts are different
652  fMismatch = 0;
653  for ( i = 0; i < nNodesMax; i++ )
654  if ( pCut1->ppLeaves[i - fMismatch] != pCut2->ppLeaves[i] )
655  {
656  if ( fMismatch == 1 )
657  return 0;
658  fMismatch = 1;
659  }
660  // return nNodesMax if they are the same
661  for ( i = 0; i < nNodesMax; i++ )
662  ppNodes[i] = pCut2->ppLeaves[i];
663  return nNodesMax;
664  }
665 */
666  // count the number of unique entries in pCut2
667  nTotal = pCut1->nLeaves;
668  for ( i = 0; i < pCut2->nLeaves; i++ )
669  {
670  // try to find this entry among the leaves of pCut1
671  for ( k = 0; k < pCut1->nLeaves; k++ )
672  if ( pCut2->ppLeaves[i] == pCut1->ppLeaves[k] )
673  break;
674  if ( k < pCut1->nLeaves ) // found
675  continue;
676  // we found a new entry to add
677  if ( nTotal == nNodesMax )
678  return 0;
679  ppNodes[nTotal++] = pCut2->ppLeaves[i];
680  }
681  // we know that the feasible cut exists
682 
683  // add the starting entries
684  for ( k = 0; k < pCut1->nLeaves; k++ )
685  ppNodes[k] = pCut1->ppLeaves[k];
686 
687  // selection-sort the entries
688  for ( i = 0; i < nTotal - 1; i++ )
689  {
690  min = i;
691  for ( k = i+1; k < nTotal; k++ )
692 // if ( ppNodes[k] < ppNodes[min] ) // reported bug fix (non-determinism!)
693  if ( ppNodes[k]->Num < ppNodes[min]->Num )
694  min = k;
695  pNodeTemp = ppNodes[i];
696  ppNodes[i] = ppNodes[min];
697  ppNodes[min] = pNodeTemp;
698  }
699 
700  return nTotal;
701 }
702 
703 /**Function*************************************************************
704 
705  Synopsis [Computes the union of the two lists of cuts.]
706 
707  Description []
708 
709  SideEffects []
710 
711  SeeAlso []
712 
713 ***********************************************************************/
714 Fpga_Cut_t * Fpga_CutUnionLists( Fpga_Cut_t * pList1, Fpga_Cut_t * pList2 )
715 {
716  Fpga_Cut_t * pTemp, * pRoot;
717  // find the last cut in the first list
718  pRoot = pList1;
719  Fpga_ListForEachCut( pList1, pTemp )
720  pRoot = pTemp;
721  // attach the non-trival part of the second cut to the end of the first
722  assert( pRoot->pNext == NULL );
723  pRoot->pNext = pList2->pNext;
724  pList2->pNext = NULL;
725  return pList1;
726 }
727 
728 
729 /**Function*************************************************************
730 
731  Synopsis [Checks whether the given cut belongs to the list.]
732 
733  Description [This procedure takes most of the runtime in the cut
734  computation.]
735 
736  SideEffects []
737 
738  SeeAlso []
739 
740 ***********************************************************************/
741 int Fpga_CutBelongsToList( Fpga_Cut_t * pList, Fpga_Node_t * ppNodes[], int nNodes )
742 {
743  Fpga_Cut_t * pTemp;
744  int i;
745  for ( pTemp = pList; pTemp; pTemp = pTemp->pNext )
746  {
747  for ( i = 0; i < nNodes; i++ )
748  if ( pTemp->ppLeaves[i] != ppNodes[i] )
749  break;
750  if ( i == nNodes )
751  return 1;
752  }
753  return 0;
754 }
755 
756 /**Function*************************************************************
757 
758  Synopsis [Counts all the cuts.]
759 
760  Description []
761 
762  SideEffects []
763 
764  SeeAlso []
765 
766 ***********************************************************************/
767 int Fpga_CutCountAll( Fpga_Man_t * pMan )
768 {
769  Fpga_Node_t * pNode;
770  Fpga_Cut_t * pCut;
771  int i, nCuts;
772  // go through all the nodes in the unique table of the manager
773  nCuts = 0;
774  for ( i = 0; i < pMan->nBins; i++ )
775  for ( pNode = pMan->pBins[i]; pNode; pNode = pNode->pNext )
776  for ( pCut = pNode->pCuts; pCut; pCut = pCut->pNext )
777  if ( pCut->nLeaves > 1 ) // skip the elementary cuts
778  {
779 // Fpga_CutVolume( pCut );
780  nCuts++;
781  }
782  return nCuts;
783 }
784 
785 
786 /**Function*************************************************************
787 
788  Synopsis [Clean the signatures.]
789 
790  Description []
791 
792  SideEffects []
793 
794  SeeAlso []
795 
796 ***********************************************************************/
797 void Fpga_CutsCleanSign( Fpga_Man_t * pMan )
798 {
799  Fpga_Node_t * pNode;
800  Fpga_Cut_t * pCut;
801  int i;
802  for ( i = 0; i < pMan->nBins; i++ )
803  for ( pNode = pMan->pBins[i]; pNode; pNode = pNode->pNext )
804  for ( pCut = pNode->pCuts; pCut; pCut = pCut->pNext )
805  pCut->uSign = 0;
806 }
807 
808 /**Function*************************************************************
809 
810  Synopsis [Clean the signatures.]
811 
812  Description []
813 
814  SideEffects []
815 
816  SeeAlso []
817 
818 ***********************************************************************/
819 void Fpga_CutsCleanRoot( Fpga_Man_t * pMan )
820 {
821  Fpga_Node_t * pNode;
822  Fpga_Cut_t * pCut;
823  int i;
824  for ( i = 0; i < pMan->nBins; i++ )
825  for ( pNode = pMan->pBins[i]; pNode; pNode = pNode->pNext )
826  for ( pCut = pNode->pCuts; pCut; pCut = pCut->pNext )
827  pCut->pRoot = NULL;
828 }
829 
830 
831 
832 /**Function*************************************************************
833 
834  Synopsis [Prints the cuts in the list.]
835 
836  Description []
837 
838  SideEffects []
839 
840  SeeAlso []
841 
842 ***********************************************************************/
843 void Fpga_CutListPrint( Fpga_Man_t * pMan, Fpga_Node_t * pRoot )
844 {
845  Fpga_Cut_t * pTemp;
846  int Counter;
847  for ( Counter = 0, pTemp = pRoot->pCuts; pTemp; pTemp = pTemp->pNext, Counter++ )
848  {
849  printf( "%2d : ", Counter + 1 );
850  Fpga_CutPrint_( pMan, pTemp, pRoot );
851  }
852 }
853 
854 /**Function*************************************************************
855 
856  Synopsis [Prints the cuts in the list.]
857 
858  Description []
859 
860  SideEffects []
861 
862  SeeAlso []
863 
864 ***********************************************************************/
865 void Fpga_CutListPrint2( Fpga_Man_t * pMan, Fpga_Node_t * pRoot )
866 {
867  Fpga_Cut_t * pTemp;
868  int Counter;
869  for ( Counter = 0, pTemp = pRoot->pCuts; pTemp; pTemp = pTemp->pNext, Counter++ )
870  {
871  printf( "%2d : ", Counter + 1 );
872  Fpga_CutPrint_( pMan, pTemp, pRoot );
873  }
874 }
875 
876 /**Function*************************************************************
877 
878  Synopsis [Prints the cut.]
879 
880  Description []
881 
882  SideEffects []
883 
884  SeeAlso []
885 
886 ***********************************************************************/
887 void Fpga_CutPrint_( Fpga_Man_t * pMan, Fpga_Cut_t * pCut, Fpga_Node_t * pRoot )
888 {
889  int i;
890  printf( "(%3d) {", pRoot->Num );
891  for ( i = 0; i < pMan->nVarsMax; i++ )
892  if ( pCut->ppLeaves[i] )
893  printf( " %3d", pCut->ppLeaves[i]->Num );
894  printf( " }\n" );
895 }
896 
897 
898 
899 
900 
901 
902 
903 
904 /**Function*************************************************************
905 
906  Synopsis [Starts the hash table to canonicize cuts.]
907 
908  Description []
909 
910  SideEffects []
911 
912  SeeAlso []
913 
914 ***********************************************************************/
915 Fpga_CutTable_t * Fpga_CutTableStart( Fpga_Man_t * pMan )
916 {
917  Fpga_CutTable_t * p;
918  // allocate the table
919  p = ABC_ALLOC( Fpga_CutTable_t, 1 );
920  memset( p, 0, sizeof(Fpga_CutTable_t) );
921  p->nBins = Abc_PrimeCudd( 10 * FPGA_CUTS_MAX_COMPUTE );
922  p->pBins = ABC_ALLOC( Fpga_Cut_t *, p->nBins );
923  memset( p->pBins, 0, sizeof(Fpga_Cut_t *) * p->nBins );
924  p->pCuts = ABC_ALLOC( int, 2 * FPGA_CUTS_MAX_COMPUTE );
925  p->pArray = ABC_ALLOC( Fpga_Cut_t *, 2 * FPGA_CUTS_MAX_COMPUTE );
926  p->pCuts1 = ABC_ALLOC( Fpga_Cut_t *, 2 * FPGA_CUTS_MAX_COMPUTE );
927  p->pCuts2 = ABC_ALLOC( Fpga_Cut_t *, 2 * FPGA_CUTS_MAX_COMPUTE );
928  return p;
929 }
930 
931 /**Function*************************************************************
932 
933  Synopsis [Stops the hash table.]
934 
935  Description []
936 
937  SideEffects []
938 
939  SeeAlso []
940 
941 ***********************************************************************/
942 void Fpga_CutTableStop( Fpga_CutTable_t * p )
943 {
944  ABC_FREE( p->pCuts1 );
945  ABC_FREE( p->pCuts2 );
946  ABC_FREE( p->pArray );
947  ABC_FREE( p->pBins );
948  ABC_FREE( p->pCuts );
949  ABC_FREE( p );
950 }
951 
952 /**Function*************************************************************
953 
954  Synopsis [Computes the hash value of the cut.]
955 
956  Description []
957 
958  SideEffects []
959 
960  SeeAlso []
961 
962 ***********************************************************************/
963 unsigned Fpga_CutTableHash( Fpga_Node_t * ppNodes[], int nNodes )
964 {
965  unsigned uRes;
966  int i;
967  uRes = 0;
968  for ( i = 0; i < nNodes; i++ )
969  uRes += s_HashPrimes[i] * ppNodes[i]->Num;
970  return uRes;
971 }
972 
973 /**Function*************************************************************
974 
975  Synopsis [Looks up the table for the available cut.]
976 
977  Description [Returns -1 if the same cut is found. Returns the index
978  of the cell where the cut should be added, if it does not exist.]
979 
980  SideEffects []
981 
982  SeeAlso []
983 
984 ***********************************************************************/
985 int Fpga_CutTableLookup( Fpga_CutTable_t * p, Fpga_Node_t * ppNodes[], int nNodes )
986 {
987  Fpga_Cut_t * pCut;
988  unsigned Key;
989  int b, i;
990 
991  Key = Fpga_CutTableHash(ppNodes, nNodes) % p->nBins;
992  for ( b = Key; p->pBins[b]; b = (b+1) % p->nBins )
993  {
994  pCut = p->pBins[b];
995  if ( pCut->nLeaves != nNodes )
996  continue;
997  for ( i = 0; i < nNodes; i++ )
998  if ( pCut->ppLeaves[i] != ppNodes[i] )
999  break;
1000  if ( i == nNodes )
1001  return -1;
1002  }
1003  return b;
1004 }
1005 
1006 
1007 /**Function*************************************************************
1008 
1009  Synopsis [Starts the hash table to canonicize cuts.]
1010 
1011  Description [Considers addition of the cut to the hash table.]
1012 
1013  SideEffects []
1014 
1015  SeeAlso []
1016 
1017 ***********************************************************************/
1018 Fpga_Cut_t * Fpga_CutTableConsider( Fpga_Man_t * pMan, Fpga_CutTable_t * p, Fpga_Node_t * ppNodes[], int nNodes )
1019 {
1020  Fpga_Cut_t * pCut;
1021  int Place, i;
1022  // check the cut
1023  Place = Fpga_CutTableLookup( p, ppNodes, nNodes );
1024  if ( Place == -1 )
1025  return NULL;
1026  assert( nNodes > 0 );
1027  // create the new cut
1028  pCut = Fpga_CutAlloc( pMan );
1029  pCut->nLeaves = nNodes;
1030  pCut->fLevel = 0.0;
1031  for ( i = 0; i < nNodes; i++ )
1032  {
1033  pCut->ppLeaves[i] = ppNodes[i];
1034  pCut->fLevel += ppNodes[i]->Level;
1035  }
1036  pCut->fLevel /= nNodes;
1037  // add the cut to the table
1038  assert( p->pBins[Place] == NULL );
1039  p->pBins[Place] = pCut;
1040  // add the cut to the new list
1041  p->pCuts[ p->nCuts++ ] = Place;
1042  return pCut;
1043 }
1044 
1045 /**Function*************************************************************
1046 
1047  Synopsis [Prepares the table to be used with other cuts.]
1048 
1049  Description [Restarts the table by cleaning the info about cuts stored
1050  when the previous node was considered.]
1051 
1052  SideEffects []
1053 
1054  SeeAlso []
1055 
1056 ***********************************************************************/
1057 void Fpga_CutTableRestart( Fpga_CutTable_t * p )
1058 {
1059  int i;
1060  for ( i = 0; i < p->nCuts; i++ )
1061  {
1062  assert( p->pBins[ p->pCuts[i] ] );
1063  p->pBins[ p->pCuts[i] ] = NULL;
1064  }
1065  p->nCuts = 0;
1066 }
1067 
1068 
1069 
1070 /**Function*************************************************************
1071 
1072  Synopsis [Compares the cuts by the number of leaves and then by delay.]
1073 
1074  Description []
1075 
1076  SideEffects []
1077 
1078  SeeAlso []
1079 
1080 ***********************************************************************/
1081 int Fpga_CutSortCutsCompare( Fpga_Cut_t ** pC1, Fpga_Cut_t ** pC2 )
1082 {
1083  if ( (*pC1)->nLeaves < (*pC2)->nLeaves )
1084  return -1;
1085  if ( (*pC1)->nLeaves > (*pC2)->nLeaves )
1086  return 1;
1087 /*
1088  if ( (*pC1)->fLevel > (*pC2)->fLevel )
1089  return -1;
1090  if ( (*pC1)->fLevel < (*pC2)->fLevel )
1091  return 1;
1092 */
1093  return 0;
1094 }
1095 
1096 /**Function*************************************************************
1097 
1098  Synopsis [Sorts the cuts by average arrival time.]
1099 
1100  Description []
1101 
1102  SideEffects []
1103 
1104  SeeAlso []
1105 
1106 ***********************************************************************/
1107 Fpga_Cut_t * Fpga_CutSortCuts( Fpga_Man_t * pMan, Fpga_CutTable_t * p, Fpga_Cut_t * pList )
1108 {
1109  Fpga_Cut_t * pListNew;
1110  int nCuts, i;
1111  // move the cuts from the list into the array
1112  nCuts = Fpga_CutList2Array( p->pCuts1, pList );
1113  assert( nCuts <= FPGA_CUTS_MAX_COMPUTE );
1114  // sort the cuts
1115  qsort( (void *)p->pCuts1, nCuts, sizeof(void *),
1116  (int (*)(const void *, const void *)) Fpga_CutSortCutsCompare );
1117  // move them back into the list
1118  if ( nCuts > FPGA_CUTS_MAX_USE - 1 )
1119  {
1120 // printf( "*" );
1121  // free the remaining cuts
1122  for ( i = FPGA_CUTS_MAX_USE - 1; i < nCuts; i++ )
1123  Extra_MmFixedEntryRecycle( pMan->mmCuts, (char *)p->pCuts1[i] );
1124  // update the number of cuts
1125  nCuts = FPGA_CUTS_MAX_USE - 1;
1126  }
1127  pListNew = Fpga_CutArray2List( p->pCuts1, nCuts );
1128  return pListNew;
1129 }
1130 
1131 /**Function*************************************************************
1132 
1133  Synopsis [Moves the nodes from the list into the array.]
1134 
1135  Description []
1136 
1137  SideEffects []
1138 
1139  SeeAlso []
1140 
1141 ***********************************************************************/
1142 int Fpga_CutList2Array( Fpga_Cut_t ** pArray, Fpga_Cut_t * pList )
1143 {
1144  int i;
1145  for ( i = 0; pList; pList = pList->pNext, i++ )
1146  pArray[i] = pList;
1147  return i;
1148 }
1149 
1150 /**Function*************************************************************
1151 
1152  Synopsis [Moves the nodes from the array into the list.]
1153 
1154  Description []
1155 
1156  SideEffects []
1157 
1158  SeeAlso []
1159 
1160 ***********************************************************************/
1161 Fpga_Cut_t * Fpga_CutArray2List( Fpga_Cut_t ** pArray, int nCuts )
1162 {
1163  Fpga_Cut_t * pListNew, ** ppListNew;
1164  int i;
1165  pListNew = NULL;
1166  ppListNew = &pListNew;
1167  for ( i = 0; i < nCuts; i++ )
1168  {
1169  // connect these lists
1170  *ppListNew = pArray[i];
1171  ppListNew = &pArray[i]->pNext;
1172 //printf( " %d(%.2f)", pArray[i]->nLeaves, pArray[i]->fLevel );
1173  }
1174 //printf( "\n" );
1175 
1176  *ppListNew = NULL;
1177  return pListNew;
1178 }
1179 
1180 
1181 ////////////////////////////////////////////////////////////////////////
1182 /// END OF FILE ///
1183 ////////////////////////////////////////////////////////////////////////
1184 
1185 ABC_NAMESPACE_IMPL_END
1186 
Fpga_CutFilter
static void Fpga_CutFilter(Fpga_Man_t *p, Fpga_Node_t *pNode)
Definition: fpgaCut.c:303
memset
char * memset()
Fpga_CutCompute
static Fpga_Cut_t * Fpga_CutCompute(Fpga_Man_t *p, Fpga_CutTable_t *pTable, Fpga_Node_t *pNode)
Definition: fpgaCut.c:211
Fpga_CutTableRestart
static void Fpga_CutTableRestart(Fpga_CutTable_t *p)
Definition: fpgaCut.c:1057
FPGA_CUTS_MAX_COMPUTE
#define FPGA_CUTS_MAX_COMPUTE
Definition: fpgaCut.c:42
Abc_PrimeCudd
static int Abc_PrimeCudd(unsigned int p)
Definition: abc_global.h:383
Fpga_CutNotCond
#define Fpga_CutNotCond(p, c)
Definition: fpgaInt.h:76
Fpga_ManStruct_t_::pInputs
Fpga_Node_t ** pInputs
Definition: fpgaInt.h:104
Fpga_ManStruct_t_::nInputs
int nInputs
Definition: fpgaInt.h:105
Fpga_CutTableStrutct_t::nCuts
int nCuts
Definition: fpgaCut.c:34
Fpga_CutTableLookup
static int Fpga_CutTableLookup(Fpga_CutTable_t *p, Fpga_Node_t *ppNodes[], int nNodes)
Definition: fpgaCut.c:985
Fpga_CutMergeLists2
Fpga_Cut_t * Fpga_CutMergeLists2(Fpga_Man_t *p, Fpga_CutTable_t *pTable, Fpga_Cut_t *pList1, Fpga_Cut_t *pList2, int fComp1, int fComp2, int fPivot1, int fPivot2)
Definition: fpgaCut.c:539
Fpga_CutFree
void Fpga_CutFree(Fpga_Man_t *p, Fpga_Cut_t *pCut)
Definition: fpgaCutUtils.c:85
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Fpga_CutStruct_t_::fLevel
float fLevel
Definition: fpgaInt.h:238
FPGA_MAX_LEAVES
#define FPGA_MAX_LEAVES
INCLUDES ///.
Definition: fpgaInt.h:52
Fpga_CutStruct_t_
Definition: fpgaInt.h:232
Fpga_NodeStruct_t_::Level
unsigned Level
Definition: fpgaInt.h:195
FPGA_COUNT_ONES
#define FPGA_COUNT_ONES(u)
Definition: fpgaCut.c:61
Fpga_CutPrint_
static void Fpga_CutPrint_(Fpga_Man_t *pMan, Fpga_Cut_t *pCut, Fpga_Node_t *pRoot)
Definition: fpgaCut.c:887
Fpga_ManStruct_t_::nBins
int nBins
Definition: fpgaInt.h:103
Fpga_NodeComparePhase
int Fpga_NodeComparePhase(Fpga_Node_t *p1, Fpga_Node_t *p2)
Definition: fpgaCreate.c:128
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Fpga_CutAlloc
Fpga_Cut_t * Fpga_CutAlloc(Fpga_Man_t *p)
DECLARATIONS ///.
Definition: fpgaCutUtils.c:43
Fpga_CutBelongsToList
static int Fpga_CutBelongsToList(Fpga_Cut_t *pList, Fpga_Node_t *ppNodes[], int nNodes)
Definition: fpgaCut.c:741
Fpga_CutListPrint
static void Fpga_CutListPrint(Fpga_Man_t *pMan, Fpga_Node_t *pRoot)
Definition: fpgaCut.c:843
Fpga_CutStruct_t_::pTwo
Fpga_Cut_t * pTwo
Definition: fpgaInt.h:235
Fpga_CutMergeTwo
static int Fpga_CutMergeTwo(Fpga_Cut_t *pCut1, Fpga_Cut_t *pCut2, Fpga_Node_t *ppNodes[], int nNodesMax)
Definition: fpgaCut.c:606
bit_count
static int bit_count[256]
Definition: fpgaCut.c:50
for
for(p=first;p->value< newval;p=p->next)
Fpga_NodeStruct_t_::pCuts
Fpga_Cut_t * pCuts
Definition: fpgaInt.h:224
Fpga_CutCountAll
int Fpga_CutCountAll(Fpga_Man_t *pMan)
Definition: fpgaCut.c:767
Fpga_CutTableStrutct_t::pCuts2
Fpga_Cut_t ** pCuts2
Definition: fpgaCut.c:37
Fpga_CutTableStrutct_t::pBins
Fpga_Cut_t ** pBins
Definition: fpgaCut.c:31
Fpga_CutStruct_t_::ppLeaves
Fpga_Node_t * ppLeaves[FPGA_MAX_LEAVES+1]
Definition: fpgaInt.h:237
Fpga_NodeStruct_t_::p1
Fpga_Node_t * p1
Definition: fpgaInt.h:200
ProgressBarStruct
DECLARATIONS ///.
Definition: extraUtilProgress.c:32
Fpga_CutArray2List
static Fpga_Cut_t * Fpga_CutArray2List(Fpga_Cut_t **pArray, int nCuts)
Definition: fpgaCut.c:1161
Fpga_CutStruct_t_::pOne
Fpga_Cut_t * pOne
Definition: fpgaInt.h:234
Fpga_ManStruct_t_::nVarsMax
int nVarsMax
Definition: fpgaInt.h:121
Fpga_CutStruct_t_::uSign
unsigned uSign
Definition: fpgaInt.h:239
Fpga_ManStruct_t_::fVerbose
int fVerbose
Definition: fpgaInt.h:123
Fpga_CutTable_t
typedefABC_NAMESPACE_IMPL_START struct Fpga_CutTableStrutct_t Fpga_CutTable_t
DECLARATIONS ///.
Definition: fpgaCut.c:28
Fpga_NodeStruct_t_::pNext
Fpga_Node_t * pNext
Definition: fpgaInt.h:183
Fpga_NodeStruct_t_::pRepr
Fpga_Node_t * pRepr
Definition: fpgaInt.h:203
Fpga_CutsCleanSign
void Fpga_CutsCleanSign(Fpga_Man_t *pMan)
Definition: fpgaCut.c:797
Fpga_CutTableStrutct_t
Definition: fpgaCut.c:29
Fpga_MappingCreatePiCuts
void Fpga_MappingCreatePiCuts(Fpga_Man_t *p)
Definition: fpgaCut.c:181
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
if
if(last==0)
Definition: sparse_int.h:34
Fpga_CutTableStart
static Fpga_CutTable_t * Fpga_CutTableStart(Fpga_Man_t *pMan)
Definition: fpgaCut.c:915
Counter
static int Counter
Definition: extraBddMisc.c:1877
Extra_ProgressBarStop
void Extra_ProgressBarStop(ProgressBar *p)
Definition: extraUtilProgress.c:118
Fpga_CutTableHash
static unsigned Fpga_CutTableHash(Fpga_Node_t *ppNodes[], int nNodes)
Definition: fpgaCut.c:963
ABC_NAMESPACE_IMPL_START
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
Fpga_CutSortCutsCompare
static int Fpga_CutSortCutsCompare(Fpga_Cut_t **pC1, Fpga_Cut_t **pC2)
Definition: fpgaCut.c:1081
Fpga_ListForEachCutSafe
#define Fpga_ListForEachCutSafe(pList, pCut, pCut2)
Definition: fpgaCut.c:94
Fpga_NodeIsAnd
int Fpga_NodeIsAnd(Fpga_Node_t *p)
Definition: fpgaCreate.c:127
FPGA_CUTS_MAX_USE
#define FPGA_CUTS_MAX_USE
Definition: fpgaCut.c:45
Fpga_CutTableStrutct_t::pCuts1
Fpga_Cut_t ** pCuts1
Definition: fpgaCut.c:36
Fpga_CutsCleanRoot
void Fpga_CutsCleanRoot(Fpga_Man_t *pMan)
Definition: fpgaCut.c:819
Fpga_CutStruct_t_::Phase
char Phase
Definition: fpgaInt.h:241
Fpga_CutList2Array
static int Fpga_CutList2Array(Fpga_Cut_t **pArray, Fpga_Cut_t *pList)
Definition: fpgaCut.c:1142
Fpga_ManStruct_t_::nNodes
int nNodes
Definition: fpgaInt.h:108
Fpga_NodeReadRef
#define Fpga_NodeReadRef(p)
Definition: fpgaInt.h:85
Fpga_ManStruct_t_::mmCuts
Extra_MmFixed_t * mmCuts
Definition: fpgaInt.h:141
Fpga_ManStruct_t_
STRUCTURE DEFINITIONS ///.
Definition: fpgaInt.h:99
Fpga_Regular
#define Fpga_Regular(p)
Definition: fpga.h:58
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
ABC_PRT
#define ABC_PRT(a, t)
Definition: abc_global.h:220
Fpga_CutStruct_t_::pRoot
Fpga_Node_t * pRoot
Definition: fpgaInt.h:236
Extra_ProgressBarStart
ProgressBar * Extra_ProgressBarStart(FILE *pFile, int nItemsTotal)
FUNCTION DEFINITIONS ///.
Definition: extraUtilProgress.c:62
Fpga_CutUnionLists
static Fpga_Cut_t * Fpga_CutUnionLists(Fpga_Cut_t *pList1, Fpga_Cut_t *pList2)
Definition: fpgaCut.c:714
Fpga_CutTableStrutct_t::nBins
int nBins
Definition: fpgaCut.c:32
Fpga_NodeStruct_t_::Num
int Num
Definition: fpgaInt.h:185
Fpga_CutStruct_t_::nLeaves
char nLeaves
Definition: fpgaInt.h:242
Fpga_ListForEachCut
#define Fpga_ListForEachCut(pList, pCut)
Definition: fpgaCut.c:90
Fpga_NodeStruct_t_
Definition: fpgaInt.h:180
Fpga_CutSortCuts
static Fpga_Cut_t * Fpga_CutSortCuts(Fpga_Man_t *pMan, Fpga_CutTable_t *p, Fpga_Cut_t *pList)
Definition: fpgaCut.c:1107
assert
#define assert(ex)
Definition: util_old.h:213
Extra_ProgressBarUpdate
static void Extra_ProgressBarUpdate(ProgressBar *p, int nItemsCur, char *pString)
Definition: extra.h:243
Fpga_CutMergeLists
static Fpga_Cut_t * Fpga_CutMergeLists(Fpga_Man_t *p, Fpga_CutTable_t *pTable, Fpga_Cut_t *pList1, Fpga_Cut_t *pList2, int fComp1, int fComp2, int fPivot1, int fPivot2)
Definition: fpgaCut.c:354
Extra_MmFixedEntryRecycle
void Extra_MmFixedEntryRecycle(Extra_MmFixed_t *p, char *pEntry)
Definition: extraUtilMemory.c:253
Fpga_CutTableConsider
static Fpga_Cut_t * Fpga_CutTableConsider(Fpga_Man_t *pMan, Fpga_CutTable_t *p, Fpga_Node_t *ppNodes[], int nNodes)
Definition: fpgaCut.c:1018
Fpga_NodeVecStruct_t_::pArray
Fpga_Node_t ** pArray
Definition: fpgaInt.h:252
Fpga_CutTableStrutct_t::pArray
Fpga_Cut_t ** pArray
Definition: fpgaCut.c:35
Fpga_NodeStruct_t_::pCutBest
Fpga_Cut_t * pCutBest
Definition: fpgaInt.h:222
Fpga_NodeStruct_t_::p2
Fpga_Node_t * p2
Definition: fpgaInt.h:201
Fpga_CutStruct_t_::pNext
Fpga_Cut_t * pNext
Definition: fpgaInt.h:246
Fpga_ManStruct_t_::pBins
Fpga_Node_t ** pBins
Definition: fpgaInt.h:102
Fpga_CutListPrint2
static void Fpga_CutListPrint2(Fpga_Man_t *pMan, Fpga_Node_t *pRoot)
Definition: fpgaCut.c:865
Fpga_NodeStruct_t_::pNextE
Fpga_Node_t * pNextE
Definition: fpgaInt.h:202
Fpga_ManStruct_t_::vAnds
Fpga_NodeVec_t * vAnds
Definition: fpgaInt.h:112
Fpga_CutTableStop
static void Fpga_CutTableStop(Fpga_CutTable_t *p)
Definition: fpgaCut.c:942
Fpga_IsComplement
#define Fpga_IsComplement(p)
GLOBAL VARIABLES ///.
Definition: fpga.h:57
s_HashPrimes
static int s_HashPrimes[10]
Definition: fpgaCut.c:48
Fpga_CutTableStrutct_t::pCuts
int * pCuts
Definition: fpgaCut.c:33
Fpga_NodeVecStruct_t_::nSize
int nSize
Definition: fpgaInt.h:253
nTotal
int nTotal
DECLARATIONS ///.
Definition: cutTruth.c:37
Fpga_MappingCuts
void Fpga_MappingCuts(Fpga_Man_t *p)
FUNCTION DEFINITIONS ///.
Definition: fpgaCut.c:130