abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
fpgaUtils.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [fpgaUtils.c]
4 
5  PackageName [MVSIS 1.3: Multi-valued logic synthesis system.]
6 
7  Synopsis [Technology mapping for variable-size-LUT FPGAs.]
8 
9  Author [MVSIS Group]
10 
11  Affiliation [UC Berkeley]
12 
13  Date [Ver. 2.0. Started - August 18, 2004.]
14 
15  Revision [$Id: fpgaUtils.c,v 1.3 2004/07/06 04:55:58 alanmi Exp $]
16 
17 ***********************************************************************/
18 
19 #include "fpgaInt.h"
20 
21 ABC_NAMESPACE_IMPL_START
22 
23 
24 ////////////////////////////////////////////////////////////////////////
25 /// DECLARATIONS ///
26 ////////////////////////////////////////////////////////////////////////
27 
28 #define FPGA_CO_LIST_SIZE 5
29 
30 static void Fpga_MappingDfs_rec( Fpga_Node_t * pNode, Fpga_NodeVec_t * vNodes, int fCollectEquiv );
31 static void Fpga_MappingDfsCuts_rec( Fpga_Node_t * pNode, Fpga_NodeVec_t * vNodes );
32 static int Fpga_MappingCompareOutputDelay( Fpga_Node_t ** ppNode1, Fpga_Node_t ** ppNode2 );
33 static void Fpga_MappingFindLatest( Fpga_Man_t * p, int * pNodes, int nNodesMax );
34 static void Fpga_DfsLim_rec( Fpga_Node_t * pNode, int Level, Fpga_NodeVec_t * vNodes );
35 static int Fpga_CollectNodeTfo_rec( Fpga_Node_t * pNode, Fpga_Node_t * pPivot, Fpga_NodeVec_t * vVisited, Fpga_NodeVec_t * vTfo );
36 static Fpga_NodeVec_t * Fpga_MappingOrderCosByLevel( Fpga_Man_t * pMan );
37 
38 ////////////////////////////////////////////////////////////////////////
39 /// FUNCTION DEFINITIONS ///
40 ////////////////////////////////////////////////////////////////////////
41 
42 
43 /**Function*************************************************************
44 
45  Synopsis [Computes the DFS ordering of the nodes.]
46 
47  Description []
48 
49  SideEffects []
50 
51  SeeAlso []
52 
53 ***********************************************************************/
54 Fpga_NodeVec_t * Fpga_MappingDfs( Fpga_Man_t * pMan, int fCollectEquiv )
55 {
56  Fpga_NodeVec_t * vNodes;//, * vNodesCo;
57  Fpga_Node_t * pNode;
58  int i;
59  // collect the CO nodes by level
60 // vNodesCo = Fpga_MappingOrderCosByLevel( pMan );
61  // start the array
62  vNodes = Fpga_NodeVecAlloc( 100 );
63  // collect the PIs
64  for ( i = 0; i < pMan->nInputs; i++ )
65  {
66  pNode = pMan->pInputs[i];
67  Fpga_NodeVecPush( vNodes, pNode );
68  pNode->fMark0 = 1;
69  }
70  // perform the traversal
71  for ( i = 0; i < pMan->nOutputs; i++ )
72  Fpga_MappingDfs_rec( Fpga_Regular(pMan->pOutputs[i]), vNodes, fCollectEquiv );
73 // for ( i = vNodesCo->nSize - 1; i >= 0 ; i-- )
74 // for ( pNode = vNodesCo->pArray[i]; pNode; pNode = (Fpga_Node_t *)pNode->pData0 )
75 // Fpga_MappingDfs_rec( pNode, vNodes, fCollectEquiv );
76  // clean the node marks
77  for ( i = 0; i < vNodes->nSize; i++ )
78  vNodes->pArray[i]->fMark0 = 0;
79 // for ( i = 0; i < pMan->nOutputs; i++ )
80 // Fpga_MappingUnmark_rec( Fpga_Regular(pMan->pOutputs[i]) );
81 // Fpga_NodeVecFree( vNodesCo );
82  return vNodes;
83 }
84 
85 /**Function*************************************************************
86 
87  Synopsis [Recursively computes the DFS ordering of the nodes.]
88 
89  Description []
90 
91  SideEffects []
92 
93  SeeAlso []
94 
95 ***********************************************************************/
96 void Fpga_MappingDfs_rec( Fpga_Node_t * pNode, Fpga_NodeVec_t * vNodes, int fCollectEquiv )
97 {
98  assert( !Fpga_IsComplement(pNode) );
99  if ( pNode->fMark0 )
100  return;
101  // visit the transitive fanin
102  if ( Fpga_NodeIsAnd(pNode) )
103  {
104  Fpga_MappingDfs_rec( Fpga_Regular(pNode->p1), vNodes, fCollectEquiv );
105  Fpga_MappingDfs_rec( Fpga_Regular(pNode->p2), vNodes, fCollectEquiv );
106  }
107  // visit the equivalent nodes
108  if ( fCollectEquiv && pNode->pNextE )
109  Fpga_MappingDfs_rec( pNode->pNextE, vNodes, fCollectEquiv );
110  // make sure the node is not visited through the equivalent nodes
111  assert( pNode->fMark0 == 0 );
112  // mark the node as visited
113  pNode->fMark0 = 1;
114  // add the node to the list
115  Fpga_NodeVecPush( vNodes, pNode );
116 }
117 
118 /**Function*************************************************************
119 
120  Synopsis [Computes the DFS ordering of the nodes.]
121 
122  Description []
123 
124  SideEffects []
125 
126  SeeAlso []
127 
128 ***********************************************************************/
129 Fpga_NodeVec_t * Fpga_MappingDfsNodes( Fpga_Man_t * pMan, Fpga_Node_t ** ppNodes, int nNodes, int fEquiv )
130 {
131  Fpga_NodeVec_t * vNodes;
132  int i;
133  // perform the traversal
134  vNodes = Fpga_NodeVecAlloc( 200 );
135  for ( i = 0; i < nNodes; i++ )
136  Fpga_MappingDfs_rec( ppNodes[i], vNodes, fEquiv );
137  for ( i = 0; i < vNodes->nSize; i++ )
138  vNodes->pArray[i]->fMark0 = 0;
139  return vNodes;
140 }
141 
142 /**Function*************************************************************
143 
144  Synopsis []
145 
146  Description []
147 
148  SideEffects []
149 
150  SeeAlso []
151 
152 ***********************************************************************/
153 float Fpga_MappingGetAreaFlow( Fpga_Man_t * p )
154 {
155  float aFlowFlowTotal = 0;
156  int i;
157  for ( i = 0; i < p->nOutputs; i++ )
158  {
159  if ( Fpga_NodeIsConst(p->pOutputs[i]) )
160  continue;
161  aFlowFlowTotal += Fpga_Regular(p->pOutputs[i])->pCutBest->aFlow;
162  }
163  return aFlowFlowTotal;
164 }
165 
166 /**Function*************************************************************
167 
168  Synopsis [Computes the area of the current mapping.]
169 
170  Description []
171 
172  SideEffects []
173 
174  SeeAlso []
175 
176 ***********************************************************************/
177 float Fpga_MappingArea( Fpga_Man_t * pMan )
178 {
179  Fpga_Node_t * pNode;
180  float aTotal;
181  int i;
182  // perform the traversal
183  aTotal = 0;
184  for ( i = 0; i < pMan->vMapping->nSize; i++ )
185  {
186  pNode = pMan->vMapping->pArray[i];
187  aTotal += pMan->pLutLib->pLutAreas[(int)pNode->pCutBest->nLeaves];
188  }
189  return aTotal;
190 }
191 
192 /**Function*************************************************************
193 
194  Synopsis [Recursively computes the DFS ordering of the nodes.]
195 
196  Description []
197 
198  SideEffects []
199 
200  SeeAlso []
201 
202 ***********************************************************************/
203 float Fpga_MappingArea_rec( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_NodeVec_t * vNodes )
204 {
205  float aArea;
206  int i;
207  assert( !Fpga_IsComplement(pNode) );
208  if ( !Fpga_NodeIsAnd(pNode) )
209  return 0;
210  if ( pNode->fMark0 )
211  return 0;
212  assert( pNode->pCutBest != NULL );
213  // visit the transitive fanin of the selected cut
214  aArea = 0;
215  for ( i = 0; i < pNode->pCutBest->nLeaves; i++ )
216  aArea += Fpga_MappingArea_rec( pMan, pNode->pCutBest->ppLeaves[i], vNodes );
217  // make sure the node is not visited through the fanin nodes
218  assert( pNode->fMark0 == 0 );
219  // mark the node as visited
220  pNode->fMark0 = 1;
221  // add the node to the list
222  aArea += pMan->pLutLib->pLutAreas[(int)pNode->pCutBest->nLeaves];
223  // add the node to the list
224  Fpga_NodeVecPush( vNodes, pNode );
225  return aArea;
226 }
227 
228 /**Function*************************************************************
229 
230  Synopsis [Computes the area of the current mapping.]
231 
232  Description []
233 
234  SideEffects []
235 
236  SeeAlso []
237 
238 ***********************************************************************/
239 float Fpga_MappingAreaTrav( Fpga_Man_t * pMan )
240 {
241  Fpga_NodeVec_t * vNodes;
242  float aTotal;
243  int i;
244  // perform the traversal
245  aTotal = 0;
246  vNodes = Fpga_NodeVecAlloc( 100 );
247  for ( i = 0; i < pMan->nOutputs; i++ )
248  aTotal += Fpga_MappingArea_rec( pMan, Fpga_Regular(pMan->pOutputs[i]), vNodes );
249  for ( i = 0; i < vNodes->nSize; i++ )
250  vNodes->pArray[i]->fMark0 = 0;
251  Fpga_NodeVecFree( vNodes );
252  return aTotal;
253 }
254 
255 
256 /**Function*************************************************************
257 
258  Synopsis [Recursively computes the DFS ordering of the nodes.]
259 
260  Description []
261 
262  SideEffects []
263 
264  SeeAlso []
265 
266 ***********************************************************************/
267 float Fpga_MappingSetRefsAndArea_rec( Fpga_Man_t * pMan, Fpga_Node_t * pNode, Fpga_Node_t ** ppStore )
268 {
269  float aArea;
270  int i;
271  assert( !Fpga_IsComplement(pNode) );
272  if ( pNode->nRefs++ )
273  return 0;
274  if ( !Fpga_NodeIsAnd(pNode) )
275  return 0;
276  assert( pNode->pCutBest != NULL );
277  // store the node in the structure by level
278  pNode->pData0 = (char *)ppStore[pNode->Level];
279  ppStore[pNode->Level] = pNode;
280  // visit the transitive fanin of the selected cut
281  aArea = pMan->pLutLib->pLutAreas[(int)pNode->pCutBest->nLeaves];
282  for ( i = 0; i < pNode->pCutBest->nLeaves; i++ )
283  aArea += Fpga_MappingSetRefsAndArea_rec( pMan, pNode->pCutBest->ppLeaves[i], ppStore );
284  return aArea;
285 }
286 
287 /**Function*************************************************************
288 
289  Synopsis [Sets the correct reference counts for the mapping.]
290 
291  Description [Collects the nodes in reverse topological order
292  and places in them in array pMan->vMapping.]
293 
294  SideEffects []
295 
296  SeeAlso []
297 
298 ***********************************************************************/
299 float Fpga_MappingSetRefsAndArea( Fpga_Man_t * pMan )
300 {
301  Fpga_Node_t * pNode, ** ppStore;
302  float aArea;
303  int i, LevelMax;
304 
305  // clean all references
306  for ( i = 0; i < pMan->vNodesAll->nSize; i++ )
307  pMan->vNodesAll->pArray[i]->nRefs = 0;
308 
309  // allocate place to store the nodes
310  LevelMax = Fpga_MappingMaxLevel( pMan );
311  ppStore = ABC_ALLOC( Fpga_Node_t *, LevelMax + 1 );
312  memset( ppStore, 0, sizeof(Fpga_Node_t *) * (LevelMax + 1) );
313 
314  // collect nodes reachable from POs in the DFS order through the best cuts
315  aArea = 0;
316  for ( i = 0; i < pMan->nOutputs; i++ )
317  {
318  pNode = Fpga_Regular(pMan->pOutputs[i]);
319  if ( pNode == pMan->pConst1 )
320  continue;
321  aArea += Fpga_MappingSetRefsAndArea_rec( pMan, pNode, ppStore );
322  pNode->nRefs++;
323  }
324 
325  // reconnect the nodes in reverse topological order
326  pMan->vMapping->nSize = 0;
327  for ( i = LevelMax; i >= 0; i-- )
328  for ( pNode = ppStore[i]; pNode; pNode = (Fpga_Node_t *)pNode->pData0 )
329  Fpga_NodeVecPush( pMan->vMapping, pNode );
330  ABC_FREE( ppStore );
331  return aArea;
332 }
333 
334 
335 /**Function*************************************************************
336 
337  Synopsis [Compares the outputs by their arrival times.]
338 
339  Description []
340 
341  SideEffects []
342 
343  SeeAlso []
344 
345 ***********************************************************************/
346 int Fpga_MappingCompareOutputDelay( Fpga_Node_t ** ppNode1, Fpga_Node_t ** ppNode2 )
347 {
348  Fpga_Node_t * pNode1 = Fpga_Regular(*ppNode1);
349  Fpga_Node_t * pNode2 = Fpga_Regular(*ppNode2);
350  float Arrival1 = pNode1->pCutBest? pNode1->pCutBest->tArrival : 0;
351  float Arrival2 = pNode2->pCutBest? pNode2->pCutBest->tArrival : 0;
352  if ( Arrival1 < Arrival2 )
353  return -1;
354  if ( Arrival1 > Arrival2 )
355  return 1;
356  return 0;
357 }
358 
359 /**Function*************************************************************
360 
361  Synopsis [Finds given number of latest arriving COs.]
362 
363  Description []
364 
365  SideEffects []
366 
367  SeeAlso []
368 
369 ***********************************************************************/
370 void Fpga_MappingFindLatest( Fpga_Man_t * p, int * pNodes, int nNodesMax )
371 {
372  int nNodes, i, k, v;
373  assert( p->nOutputs >= nNodesMax );
374  pNodes[0] = 0;
375  nNodes = 1;
376  for ( i = 1; i < p->nOutputs; i++ )
377  {
378  for ( k = nNodes - 1; k >= 0; k-- )
379  if ( Fpga_MappingCompareOutputDelay( &p->pOutputs[pNodes[k]], &p->pOutputs[i] ) >= 0 )
380  break;
381  if ( k == nNodesMax - 1 )
382  continue;
383  if ( nNodes < nNodesMax )
384  nNodes++;
385  for ( v = nNodes - 1; v > k+1; v-- )
386  pNodes[v] = pNodes[v-1];
387  pNodes[k+1] = i;
388  }
389 }
390 
391 /**Function*************************************************************
392 
393  Synopsis [Prints a bunch of latest arriving outputs.]
394 
395  Description []
396 
397  SideEffects []
398 
399  SeeAlso []
400 
401 ***********************************************************************/
402 void Fpga_MappingPrintOutputArrivals( Fpga_Man_t * p )
403 {
404  Fpga_Node_t * pNode;
405  int pSorted[FPGA_CO_LIST_SIZE];
406  int fCompl, Limit, MaxNameSize, i;
407 
408  // determine the number of nodes to print
409  Limit = (p->nOutputs > FPGA_CO_LIST_SIZE)? FPGA_CO_LIST_SIZE : p->nOutputs;
410 
411  // determine the order
412  Fpga_MappingFindLatest( p, pSorted, Limit );
413 
414  // determine max size of the node's name
415  MaxNameSize = 0;
416  for ( i = 0; i < Limit; i++ )
417  if ( MaxNameSize < (int)strlen(p->ppOutputNames[pSorted[i]]) )
418  MaxNameSize = strlen(p->ppOutputNames[pSorted[i]]);
419 
420  // print the latest outputs
421  for ( i = 0; i < Limit; i++ )
422  {
423  // get the i-th latest output
424  pNode = Fpga_Regular(p->pOutputs[pSorted[i]]);
425  fCompl = Fpga_IsComplement(p->pOutputs[pSorted[i]]);
426  // print out the best arrival time
427  printf( "Output %-*s : ", MaxNameSize + 3, p->ppOutputNames[pSorted[i]] );
428  printf( "Delay = %8.2f ", (double)pNode->pCutBest->tArrival );
429  if ( fCompl )
430  printf( "NEG" );
431  else
432  printf( "POS" );
433  printf( "\n" );
434  }
435 }
436 
437 
438 /**Function*************************************************************
439 
440  Synopsis [Sets up the truth tables.]
441 
442  Description []
443 
444  SideEffects []
445 
446  SeeAlso []
447 
448 ***********************************************************************/
449 void Fpga_MappingSetupTruthTables( unsigned uTruths[][2] )
450 {
451  int m, v;
452  // set up the truth tables
453  for ( m = 0; m < 32; m++ )
454  for ( v = 0; v < 5; v++ )
455  if ( m & (1 << v) )
456  uTruths[v][0] |= (1 << m);
457  // make adjustments for the case of 6 variables
458  for ( v = 0; v < 5; v++ )
459  uTruths[v][1] = uTruths[v][0];
460  uTruths[5][0] = 0;
461  uTruths[5][1] = FPGA_FULL;
462 }
463 
464 /**Function*************************************************************
465 
466  Synopsis [Sets up the mask.]
467 
468  Description []
469 
470  SideEffects []
471 
472  SeeAlso []
473 
474 ***********************************************************************/
475 void Fpga_MappingSetupMask( unsigned uMask[], int nVarsMax )
476 {
477  if ( nVarsMax == 6 )
478  uMask[0] = uMask[1] = FPGA_FULL;
479  else
480  {
481  uMask[0] = FPGA_MASK(1 << nVarsMax);
482  uMask[1] = 0;
483  }
484 }
485 
486 /**Function*************************************************************
487 
488  Synopsis [Verify one useful property.]
489 
490  Description [This procedure verifies one useful property. After
491  the FRAIG construction with choice nodes is over, each primary node
492  should have fanins that are primary nodes. The primary nodes is the
493  one that does not have pNode->pRepr set to point to another node.]
494 
495  SideEffects []
496 
497  SeeAlso []
498 
499 ***********************************************************************/
500 int Fpga_ManCheckConsistency( Fpga_Man_t * p )
501 {
502  Fpga_Node_t * pNode;
503  Fpga_NodeVec_t * pVec;
504  int i;
505  pVec = Fpga_MappingDfs( p, 0 );
506  for ( i = 0; i < pVec->nSize; i++ )
507  {
508  pNode = pVec->pArray[i];
509  if ( Fpga_NodeIsVar(pNode) )
510  {
511  if ( pNode->pRepr )
512  printf( "Primary input %d is a secondary node.\n", pNode->Num );
513  }
514  else if ( Fpga_NodeIsConst(pNode) )
515  {
516  if ( pNode->pRepr )
517  printf( "Constant 1 %d is a secondary node.\n", pNode->Num );
518  }
519  else
520  {
521  if ( pNode->pRepr )
522  printf( "Internal node %d is a secondary node.\n", pNode->Num );
523  if ( Fpga_Regular(pNode->p1)->pRepr )
524  printf( "Internal node %d has first fanin that is a secondary node.\n", pNode->Num );
525  if ( Fpga_Regular(pNode->p2)->pRepr )
526  printf( "Internal node %d has second fanin that is a secondary node.\n", pNode->Num );
527  }
528  }
529  Fpga_NodeVecFree( pVec );
530  return 1;
531 }
532 
533 /**Function*************************************************************
534 
535  Synopsis [Compares the supergates by their level.]
536 
537  Description []
538 
539  SideEffects []
540 
541  SeeAlso []
542 
543 ***********************************************************************/
544 int Fpga_CompareNodesByLevelDecreasing( Fpga_Node_t ** ppS1, Fpga_Node_t ** ppS2 )
545 {
546  if ( Fpga_Regular(*ppS1)->Level > Fpga_Regular(*ppS2)->Level )
547  return -1;
548  if ( Fpga_Regular(*ppS1)->Level < Fpga_Regular(*ppS2)->Level )
549  return 1;
550  return 0;
551 }
552 
553 /**Function*************************************************************
554 
555  Synopsis [Compares the supergates by their level.]
556 
557  Description []
558 
559  SideEffects []
560 
561  SeeAlso []
562 
563 ***********************************************************************/
564 int Fpga_CompareNodesByLevelIncreasing( Fpga_Node_t ** ppS1, Fpga_Node_t ** ppS2 )
565 {
566  if ( Fpga_Regular(*ppS1)->Level < Fpga_Regular(*ppS2)->Level )
567  return -1;
568  if ( Fpga_Regular(*ppS1)->Level > Fpga_Regular(*ppS2)->Level )
569  return 1;
570  return 0;
571 }
572 
573 /**Function*************************************************************
574 
575  Synopsis [Orders the nodes in the decreasing order of levels.]
576 
577  Description []
578 
579  SideEffects []
580 
581  SeeAlso []
582 
583 ***********************************************************************/
584 void Fpga_MappingSortByLevel( Fpga_Man_t * pMan, Fpga_NodeVec_t * vNodes, int fIncreasing )
585 {
586  if ( fIncreasing )
587  qsort( (void *)vNodes->pArray, vNodes->nSize, sizeof(Fpga_Node_t *),
588  (int (*)(const void *, const void *)) Fpga_CompareNodesByLevelIncreasing );
589  else
590  qsort( (void *)vNodes->pArray, vNodes->nSize, sizeof(Fpga_Node_t *),
591  (int (*)(const void *, const void *)) Fpga_CompareNodesByLevelDecreasing );
592 // assert( Fpga_CompareNodesByLevel( vNodes->pArray, vNodes->pArray + vNodes->nSize - 1 ) <= 0 );
593 }
594 
595 /**Function*************************************************************
596 
597  Synopsis [Computes the limited DFS ordering for one node.]
598 
599  Description []
600 
601  SideEffects []
602 
603  SeeAlso []
604 
605 ***********************************************************************/
606 Fpga_NodeVec_t * Fpga_DfsLim( Fpga_Man_t * pMan, Fpga_Node_t * pNode, int nLevels )
607 {
608  Fpga_NodeVec_t * vNodes;
609  int i;
610  // perform the traversal
611  vNodes = Fpga_NodeVecAlloc( 100 );
612  Fpga_DfsLim_rec( pNode, nLevels, vNodes );
613  for ( i = 0; i < vNodes->nSize; i++ )
614  vNodes->pArray[i]->fMark0 = 0;
615  return vNodes;
616 }
617 
618 /**Function*************************************************************
619 
620  Synopsis [Recursively computes the DFS ordering of the nodes.]
621 
622  Description []
623 
624  SideEffects []
625 
626  SeeAlso []
627 
628 ***********************************************************************/
629 void Fpga_DfsLim_rec( Fpga_Node_t * pNode, int Level, Fpga_NodeVec_t * vNodes )
630 {
631  assert( !Fpga_IsComplement(pNode) );
632  if ( pNode->fMark0 )
633  return;
634  pNode->fMark0 = 1;
635  // visit the transitive fanin
636  Level--;
637  if ( Level > 0 && Fpga_NodeIsAnd(pNode) )
638  {
639  Fpga_DfsLim_rec( Fpga_Regular(pNode->p1), Level, vNodes );
640  Fpga_DfsLim_rec( Fpga_Regular(pNode->p2), Level, vNodes );
641  }
642  // add the node to the list
643  Fpga_NodeVecPush( vNodes, pNode );
644 }
645 
646 /**Function*************************************************************
647 
648  Synopsis [Computes the limited DFS ordering for one node.]
649 
650  Description []
651 
652  SideEffects []
653 
654  SeeAlso []
655 
656 ***********************************************************************/
657 void Fpga_ManCleanData0( Fpga_Man_t * pMan )
658 {
659  int i;
660  for ( i = 0; i < pMan->vNodesAll->nSize; i++ )
661  pMan->vNodesAll->pArray[i]->pData0 = 0;
662 }
663 
664 /**Function*************************************************************
665 
666  Synopsis [Collects the TFO of the node.]
667 
668  Description []
669 
670  SideEffects []
671 
672  SeeAlso []
673 
674 ***********************************************************************/
675 Fpga_NodeVec_t * Fpga_CollectNodeTfo( Fpga_Man_t * pMan, Fpga_Node_t * pNode )
676 {
677  Fpga_NodeVec_t * vVisited, * vTfo;
678  int i;
679  // perform the traversal
680  vVisited = Fpga_NodeVecAlloc( 100 );
681  vTfo = Fpga_NodeVecAlloc( 100 );
682  for ( i = 0; i < pMan->nOutputs; i++ )
683  Fpga_CollectNodeTfo_rec( Fpga_Regular(pMan->pOutputs[i]), pNode, vVisited, vTfo );
684  for ( i = 0; i < vVisited->nSize; i++ )
685  vVisited->pArray[i]->fMark0 = vVisited->pArray[i]->fMark1 = 0;
686  Fpga_NodeVecFree( vVisited );
687  return vTfo;
688 }
689 
690 /**Function*************************************************************
691 
692  Synopsis [Collects the TFO of the node.]
693 
694  Description [Returns 1 if the node should be collected.]
695 
696  SideEffects []
697 
698  SeeAlso []
699 
700 ***********************************************************************/
701 int Fpga_CollectNodeTfo_rec( Fpga_Node_t * pNode, Fpga_Node_t * pPivot, Fpga_NodeVec_t * vVisited, Fpga_NodeVec_t * vTfo )
702 {
703  int Ret1, Ret2;
704  assert( !Fpga_IsComplement(pNode) );
705  // skip visited nodes
706  if ( pNode->fMark0 )
707  return pNode->fMark1;
708  pNode->fMark0 = 1;
709  Fpga_NodeVecPush( vVisited, pNode );
710 
711  // return the pivot node
712  if ( pNode == pPivot )
713  {
714  pNode->fMark1 = 1;
715  return 1;
716  }
717  if ( pNode->Level < pPivot->Level )
718  {
719  pNode->fMark1 = 0;
720  return 0;
721  }
722  // visit the transitive fanin
723  assert( Fpga_NodeIsAnd(pNode) );
724  Ret1 = Fpga_CollectNodeTfo_rec( Fpga_Regular(pNode->p1), pPivot, vVisited, vTfo );
725  Ret2 = Fpga_CollectNodeTfo_rec( Fpga_Regular(pNode->p2), pPivot, vVisited, vTfo );
726  if ( Ret1 || Ret2 )
727  {
728  pNode->fMark1 = 1;
729  Fpga_NodeVecPush( vTfo, pNode );
730  }
731  else
732  pNode->fMark1 = 0;
733  return pNode->fMark1;
734 }
735 
736 /**Function*************************************************************
737 
738  Synopsis [Levelizes the nodes accessible from the POs.]
739 
740  Description []
741 
742  SideEffects []
743 
744  SeeAlso []
745 
746 ***********************************************************************/
747 Fpga_NodeVec_t * Fpga_MappingLevelize( Fpga_Man_t * pMan, Fpga_NodeVec_t * vNodes )
748 {
749  Fpga_NodeVec_t * vLevels;
750  Fpga_Node_t ** ppNodes;
751  Fpga_Node_t * pNode;
752  int nNodes, nLevelsMax, i;
753 
754  // reassign the levels (this may be necessary for networks which choices)
755  ppNodes = vNodes->pArray;
756  nNodes = vNodes->nSize;
757  for ( i = 0; i < nNodes; i++ )
758  {
759  pNode = ppNodes[i];
760  if ( !Fpga_NodeIsAnd(pNode) )
761  {
762  pNode->Level = 0;
763  continue;
764  }
765  pNode->Level = 1 + FPGA_MAX( Fpga_Regular(pNode->p1)->Level, Fpga_Regular(pNode->p2)->Level );
766  }
767 
768  // get the max levels
769  nLevelsMax = 0;
770  for ( i = 0; i < pMan->nOutputs; i++ )
771  nLevelsMax = FPGA_MAX( nLevelsMax, (int)Fpga_Regular(pMan->pOutputs[i])->Level );
772  nLevelsMax++;
773 
774  // allocate storage for levels
775  vLevels = Fpga_NodeVecAlloc( nLevelsMax );
776  for ( i = 0; i < nLevelsMax; i++ )
777  Fpga_NodeVecPush( vLevels, NULL );
778 
779  // go through the nodes and add them to the levels
780  for ( i = 0; i < nNodes; i++ )
781  {
782  pNode = ppNodes[i];
783  pNode->pLevel = NULL;
784  if ( !Fpga_NodeIsAnd(pNode) )
785  continue;
786  // attach the node to this level
787  pNode->pLevel = Fpga_NodeVecReadEntry( vLevels, pNode->Level );
788  Fpga_NodeVecWriteEntry( vLevels, pNode->Level, pNode );
789  }
790  return vLevels;
791 }
792 
793 /**Function*************************************************************
794 
795  Synopsis [Sets up the mask.]
796 
797  Description []
798 
799  SideEffects []
800 
801  SeeAlso []
802 
803 ***********************************************************************/
804 int Fpga_MappingMaxLevel( Fpga_Man_t * pMan )
805 {
806  int nLevelMax, i;
807  nLevelMax = 0;
808  for ( i = 0; i < pMan->nOutputs; i++ )
809  nLevelMax = nLevelMax > (int)Fpga_Regular(pMan->pOutputs[i])->Level?
810  nLevelMax : (int)Fpga_Regular(pMan->pOutputs[i])->Level;
811  return nLevelMax;
812 }
813 
814 
815 /**Function*************************************************************
816 
817  Synopsis [Analyses choice nodes.]
818 
819  Description []
820 
821  SideEffects []
822 
823  SeeAlso []
824 
825 ***********************************************************************/
826 int Fpga_MappingUpdateLevel_rec( Fpga_Man_t * pMan, Fpga_Node_t * pNode, int fMaximum )
827 {
828  Fpga_Node_t * pTemp;
829  int Level1, Level2, LevelE;
830  assert( !Fpga_IsComplement(pNode) );
831  if ( !Fpga_NodeIsAnd(pNode) )
832  return pNode->Level;
833  // skip the visited node
834  if ( pNode->TravId == pMan->nTravIds )
835  return pNode->Level;
836  pNode->TravId = pMan->nTravIds;
837  // compute levels of the children nodes
838  Level1 = Fpga_MappingUpdateLevel_rec( pMan, Fpga_Regular(pNode->p1), fMaximum );
839  Level2 = Fpga_MappingUpdateLevel_rec( pMan, Fpga_Regular(pNode->p2), fMaximum );
840  pNode->Level = 1 + FPGA_MAX( Level1, Level2 );
841  if ( pNode->pNextE )
842  {
843  LevelE = Fpga_MappingUpdateLevel_rec( pMan, pNode->pNextE, fMaximum );
844  if ( fMaximum )
845  {
846  if ( pNode->Level < (unsigned)LevelE )
847  pNode->Level = LevelE;
848  }
849  else
850  {
851  if ( pNode->Level > (unsigned)LevelE )
852  pNode->Level = LevelE;
853  }
854  // set the level of all equivalent nodes to be the same minimum
855  if ( pNode->pRepr == NULL ) // the primary node
856  for ( pTemp = pNode->pNextE; pTemp; pTemp = pTemp->pNextE )
857  pTemp->Level = pNode->Level;
858  }
859  return pNode->Level;
860 }
861 
862 /**Function*************************************************************
863 
864  Synopsis [Resets the levels of the nodes in the choice graph.]
865 
866  Description [Makes the level of the choice nodes to be equal to the
867  maximum of the level of the nodes in the equivalence class. This way
868  sorting by level leads to the reverse topological order, which is
869  needed for the required time computation.]
870 
871  SideEffects []
872 
873  SeeAlso []
874 
875 ***********************************************************************/
876 void Fpga_MappingSetChoiceLevels( Fpga_Man_t * pMan )
877 {
878  int i;
879  pMan->nTravIds++;
880  for ( i = 0; i < pMan->nOutputs; i++ )
881  Fpga_MappingUpdateLevel_rec( pMan, Fpga_Regular(pMan->pOutputs[i]), 1 );
882 }
883 
884 /**Function*************************************************************
885 
886  Synopsis [Reports statistics on choice nodes.]
887 
888  Description [The number of choice nodes is the number of primary nodes,
889  which has pNextE set to a pointer. The number of choices is the number
890  of entries in the equivalent-node lists of the primary nodes.]
891 
892  SideEffects []
893 
894  SeeAlso []
895 
896 ***********************************************************************/
897 void Fpga_ManReportChoices( Fpga_Man_t * pMan )
898 {
899  Fpga_Node_t * pNode, * pTemp;
900  int nChoiceNodes, nChoices;
901  int i, LevelMax1, LevelMax2;
902 
903  // report the number of levels
904  LevelMax1 = Fpga_MappingMaxLevel( pMan );
905  pMan->nTravIds++;
906  for ( i = 0; i < pMan->nOutputs; i++ )
907  Fpga_MappingUpdateLevel_rec( pMan, Fpga_Regular(pMan->pOutputs[i]), 0 );
908  LevelMax2 = Fpga_MappingMaxLevel( pMan );
909 
910  // report statistics about choices
911  nChoiceNodes = nChoices = 0;
912  for ( i = 0; i < pMan->vAnds->nSize; i++ )
913  {
914  pNode = pMan->vAnds->pArray[i];
915  if ( pNode->pRepr == NULL && pNode->pNextE != NULL )
916  { // this is a choice node = the primary node that has equivalent nodes
917  nChoiceNodes++;
918  for ( pTemp = pNode; pTemp; pTemp = pTemp->pNextE )
919  nChoices++;
920  }
921  }
922  if ( pMan->fVerbose )
923  {
924  printf( "Maximum level: Original = %d. Reduced due to choices = %d.\n", LevelMax1, LevelMax2 );
925  printf( "Choice stats: Choice nodes = %d. Total choices = %d.\n", nChoiceNodes, nChoices );
926  }
927 /*
928  {
929  FILE * pTable;
930  pTable = fopen( "stats_choice.txt", "a+" );
931  fprintf( pTable, "%s ", pMan->pFileName );
932  fprintf( pTable, "%4d ", LevelMax1 );
933  fprintf( pTable, "%4d ", pMan->vAnds->nSize - pMan->nInputs );
934  fprintf( pTable, "%4d ", LevelMax2 );
935  fprintf( pTable, "%7d ", nChoiceNodes );
936  fprintf( pTable, "%7d ", nChoices + nChoiceNodes );
937  fprintf( pTable, "\n" );
938  fclose( pTable );
939  }
940 */
941 }
942 
943 /**Function*************************************************************
944 
945  Synopsis [Returns the array of CO nodes sorted by level.]
946 
947  Description []
948 
949  SideEffects []
950 
951  SeeAlso []
952 
953 ***********************************************************************/
954 Fpga_NodeVec_t * Fpga_MappingOrderCosByLevel( Fpga_Man_t * pMan )
955 {
956  Fpga_Node_t * pNode;
957  Fpga_NodeVec_t * vNodes;
958  int i, nLevels;
959  // get the largest level of a CO
960  nLevels = Fpga_MappingMaxLevel( pMan );
961  // allocate the array of nodes
962  vNodes = Fpga_NodeVecAlloc( nLevels + 1 );
963  for ( i = 0; i <= nLevels; i++ )
964  Fpga_NodeVecPush( vNodes, NULL );
965  // clean the marks
966  for ( i = 0; i < pMan->nOutputs; i++ )
967  Fpga_Regular(pMan->pOutputs[i])->fMark0 = 0;
968  // put the nodes into the structure
969  for ( i = 0; i < pMan->nOutputs; i++ )
970  {
971  pNode = Fpga_Regular(pMan->pOutputs[i]);
972  if ( pNode->fMark0 )
973  continue;
974  pNode->fMark0 = 1;
975  pNode->pData0 = (char *)Fpga_NodeVecReadEntry( vNodes, pNode->Level );
976  Fpga_NodeVecWriteEntry( vNodes, pNode->Level, pNode );
977  }
978  for ( i = 0; i < pMan->nOutputs; i++ )
979  Fpga_Regular(pMan->pOutputs[i])->fMark0 = 0;
980  return vNodes;
981 
982 }
983 
984 ////////////////////////////////////////////////////////////////////////
985 /// END OF FILE ///
986 ////////////////////////////////////////////////////////////////////////
987 
988 
989 ABC_NAMESPACE_IMPL_END
990 
memset
char * memset()
Fpga_CollectNodeTfo_rec
static int Fpga_CollectNodeTfo_rec(Fpga_Node_t *pNode, Fpga_Node_t *pPivot, Fpga_NodeVec_t *vVisited, Fpga_NodeVec_t *vTfo)
Definition: fpgaUtils.c:701
Fpga_NodeStruct_t_::fMark1
unsigned fMark1
Definition: fpgaInt.h:190
FPGA_FULL
#define FPGA_FULL
Definition: fpgaInt.h:56
Fpga_NodeStruct_t_::pData0
char * pData0
Definition: fpgaInt.h:228
Fpga_ManStruct_t_::pInputs
Fpga_Node_t ** pInputs
Definition: fpgaInt.h:104
Fpga_ManStruct_t_::nInputs
int nInputs
Definition: fpgaInt.h:105
Fpga_CompareNodesByLevelIncreasing
int Fpga_CompareNodesByLevelIncreasing(Fpga_Node_t **ppS1, Fpga_Node_t **ppS2)
Definition: fpgaUtils.c:564
Fpga_MappingCompareOutputDelay
static int Fpga_MappingCompareOutputDelay(Fpga_Node_t **ppNode1, Fpga_Node_t **ppNode2)
Definition: fpgaUtils.c:346
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Fpga_DfsLim_rec
static void Fpga_DfsLim_rec(Fpga_Node_t *pNode, int Level, Fpga_NodeVec_t *vNodes)
Definition: fpgaUtils.c:629
Fpga_MappingOrderCosByLevel
static Fpga_NodeVec_t * Fpga_MappingOrderCosByLevel(Fpga_Man_t *pMan)
Definition: fpgaUtils.c:954
Fpga_MappingPrintOutputArrivals
void Fpga_MappingPrintOutputArrivals(Fpga_Man_t *p)
Definition: fpgaUtils.c:402
Fpga_NodeStruct_t_::Level
unsigned Level
Definition: fpgaInt.h:195
Fpga_MappingSetRefsAndArea_rec
float Fpga_MappingSetRefsAndArea_rec(Fpga_Man_t *pMan, Fpga_Node_t *pNode, Fpga_Node_t **ppStore)
Definition: fpgaUtils.c:267
Fpga_MappingDfs
Fpga_NodeVec_t * Fpga_MappingDfs(Fpga_Man_t *pMan, int fCollectEquiv)
FUNCTION DEFINITIONS ///.
Definition: fpgaUtils.c:54
Fpga_ManStruct_t_::pOutputs
Fpga_Node_t ** pOutputs
Definition: fpgaInt.h:106
Fpga_MappingUpdateLevel_rec
int Fpga_MappingUpdateLevel_rec(Fpga_Man_t *pMan, Fpga_Node_t *pNode, int fMaximum)
Definition: fpgaUtils.c:826
Fpga_MappingMaxLevel
int Fpga_MappingMaxLevel(Fpga_Man_t *pMan)
Definition: fpgaUtils.c:804
Fpga_ManReportChoices
void Fpga_ManReportChoices(Fpga_Man_t *pMan)
Definition: fpgaUtils.c:897
Fpga_ManStruct_t_::vMapping
Fpga_NodeVec_t * vMapping
Definition: fpgaInt.h:113
Fpga_NodeStruct_t_::pLevel
Fpga_Node_t * pLevel
Definition: fpgaInt.h:184
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Fpga_ManStruct_t_::ppOutputNames
char ** ppOutputNames
Definition: fpgaInt.h:117
FPGA_MAX
#define FPGA_MAX(a, b)
Definition: fpgaInt.h:62
Fpga_NodeStruct_t_::fMark0
unsigned fMark0
Definition: fpgaInt.h:189
Fpga_LutLibStruct_t_::pLutAreas
float pLutAreas[FPGA_MAX_LUTSIZE+1]
Definition: fpgaInt.h:175
Fpga_CutStruct_t_::tArrival
float tArrival
Definition: fpgaInt.h:244
Fpga_MappingLevelize
Fpga_NodeVec_t * Fpga_MappingLevelize(Fpga_Man_t *pMan, Fpga_NodeVec_t *vNodes)
Definition: fpgaUtils.c:747
Fpga_NodeVecStruct_t_
Definition: fpgaInt.h:250
Fpga_MappingAreaTrav
float Fpga_MappingAreaTrav(Fpga_Man_t *pMan)
Definition: fpgaUtils.c:239
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
Fpga_ManStruct_t_::nTravIds
int nTravIds
Definition: fpgaInt.h:126
Fpga_ManStruct_t_::vNodesAll
Fpga_NodeVec_t * vNodesAll
Definition: fpgaInt.h:111
Fpga_NodeVecAlloc
Fpga_NodeVec_t * Fpga_NodeVecAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: fpgaVec.c:45
Fpga_NodeVecFree
void Fpga_NodeVecFree(Fpga_NodeVec_t *p)
Definition: fpgaVec.c:68
Fpga_MappingDfsNodes
Fpga_NodeVec_t * Fpga_MappingDfsNodes(Fpga_Man_t *pMan, Fpga_Node_t **ppNodes, int nNodes, int fEquiv)
Definition: fpgaUtils.c:129
Fpga_ManStruct_t_::fVerbose
int fVerbose
Definition: fpgaInt.h:123
Fpga_NodeStruct_t_::pRepr
Fpga_Node_t * pRepr
Definition: fpgaInt.h:203
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
Fpga_MappingArea
float Fpga_MappingArea(Fpga_Man_t *pMan)
Definition: fpgaUtils.c:177
Fpga_ManStruct_t_::pConst1
Fpga_Node_t * pConst1
Definition: fpgaInt.h:110
Fpga_DfsLim
Fpga_NodeVec_t * Fpga_DfsLim(Fpga_Man_t *pMan, Fpga_Node_t *pNode, int nLevels)
Definition: fpgaUtils.c:606
Fpga_NodeIsConst
int Fpga_NodeIsConst(Fpga_Node_t *p)
Definition: fpgaCreate.c:125
Fpga_MappingArea_rec
float Fpga_MappingArea_rec(Fpga_Man_t *pMan, Fpga_Node_t *pNode, Fpga_NodeVec_t *vNodes)
Definition: fpgaUtils.c:203
ABC_NAMESPACE_IMPL_START
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
Fpga_ManStruct_t_::nOutputs
int nOutputs
Definition: fpgaInt.h:107
Fpga_NodeIsAnd
int Fpga_NodeIsAnd(Fpga_Node_t *p)
Definition: fpgaCreate.c:127
Fpga_MappingSetupTruthTables
void Fpga_MappingSetupTruthTables(unsigned uTruths[][2])
Definition: fpgaUtils.c:449
Fpga_ManCleanData0
void Fpga_ManCleanData0(Fpga_Man_t *pMan)
Definition: fpgaUtils.c:657
Fpga_MappingFindLatest
static void Fpga_MappingFindLatest(Fpga_Man_t *p, int *pNodes, int nNodesMax)
Definition: fpgaUtils.c:370
Fpga_MappingSetRefsAndArea
float Fpga_MappingSetRefsAndArea(Fpga_Man_t *pMan)
Definition: fpgaUtils.c:299
Fpga_NodeStruct_t_::nRefs
int nRefs
Definition: fpgaInt.h:188
Fpga_NodeIsVar
int Fpga_NodeIsVar(Fpga_Node_t *p)
Definition: fpgaCreate.c:126
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
Fpga_NodeStruct_t_::TravId
int TravId
Definition: fpgaInt.h:197
FPGA_CO_LIST_SIZE
#define FPGA_CO_LIST_SIZE
DECLARATIONS ///.
Definition: fpgaUtils.c:28
Fpga_NodeStruct_t_::Num
int Num
Definition: fpgaInt.h:185
Fpga_CutStruct_t_::nLeaves
char nLeaves
Definition: fpgaInt.h:242
Fpga_MappingSetupMask
void Fpga_MappingSetupMask(unsigned uMask[], int nVarsMax)
Definition: fpgaUtils.c:475
Fpga_NodeStruct_t_
Definition: fpgaInt.h:180
Fpga_NodeVecReadEntry
Fpga_Node_t * Fpga_NodeVecReadEntry(Fpga_NodeVec_t *p, int i)
Definition: fpgaVec.c:246
assert
#define assert(ex)
Definition: util_old.h:213
Fpga_NodeVecWriteEntry
void Fpga_NodeVecWriteEntry(Fpga_NodeVec_t *p, int i, Fpga_Node_t *Entry)
Definition: fpgaVec.c:229
strlen
int strlen()
Fpga_CollectNodeTfo
Fpga_NodeVec_t * Fpga_CollectNodeTfo(Fpga_Man_t *pMan, Fpga_Node_t *pNode)
Definition: fpgaUtils.c:675
Fpga_ManStruct_t_::pLutLib
Fpga_LutLib_t * pLutLib
Definition: fpgaInt.h:137
Fpga_NodeVecStruct_t_::pArray
Fpga_Node_t ** pArray
Definition: fpgaInt.h:252
Fpga_MappingSortByLevel
void Fpga_MappingSortByLevel(Fpga_Man_t *pMan, Fpga_NodeVec_t *vNodes, int fIncreasing)
Definition: fpgaUtils.c:584
Fpga_CompareNodesByLevelDecreasing
int Fpga_CompareNodesByLevelDecreasing(Fpga_Node_t **ppS1, Fpga_Node_t **ppS2)
Definition: fpgaUtils.c:544
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_NodeStruct_t_::pNextE
Fpga_Node_t * pNextE
Definition: fpgaInt.h:202
Fpga_ManStruct_t_::vAnds
Fpga_NodeVec_t * vAnds
Definition: fpgaInt.h:112
Fpga_ManCheckConsistency
int Fpga_ManCheckConsistency(Fpga_Man_t *p)
Definition: fpgaUtils.c:500
Fpga_MappingDfs_rec
static void Fpga_MappingDfs_rec(Fpga_Node_t *pNode, Fpga_NodeVec_t *vNodes, int fCollectEquiv)
Definition: fpgaUtils.c:96
Fpga_IsComplement
#define Fpga_IsComplement(p)
GLOBAL VARIABLES ///.
Definition: fpga.h:57
Fpga_NodeVecPush
void Fpga_NodeVecPush(Fpga_NodeVec_t *p, Fpga_Node_t *Entry)
Definition: fpgaVec.c:169
Fpga_NodeVecStruct_t_::nSize
int nSize
Definition: fpgaInt.h:253
FPGA_MASK
#define FPGA_MASK(n)
Definition: fpgaInt.h:55
Fpga_MappingSetChoiceLevels
void Fpga_MappingSetChoiceLevels(Fpga_Man_t *pMan)
Definition: fpgaUtils.c:876
Fpga_MappingGetAreaFlow
float Fpga_MappingGetAreaFlow(Fpga_Man_t *p)
Definition: fpgaUtils.c:153
Fpga_MappingDfsCuts_rec
static void Fpga_MappingDfsCuts_rec(Fpga_Node_t *pNode, Fpga_NodeVec_t *vNodes)