abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
mapperUtils.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [mapperUtils.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 - June 1, 2004.]
14 
15  Revision [$Id: mapperUtils.c,v 1.8 2004/11/03 22:41:45 satrajit Exp $]
16 
17 ***********************************************************************/
18 
19 #include "mapperInt.h"
20 
21 ABC_NAMESPACE_IMPL_START
22 
23 
24 ////////////////////////////////////////////////////////////////////////
25 /// DECLARATIONS ///
26 ////////////////////////////////////////////////////////////////////////
27 
28 #define MAP_CO_LIST_SIZE 5
29 
30 static int Map_MappingCountLevels_rec( Map_Node_t * pNode );
31 static float Map_MappingSetRefsAndArea_rec( Map_Man_t * pMan, Map_Node_t * pNode );
32 static float Map_MappingSetRefsAndSwitch_rec( Map_Man_t * pMan, Map_Node_t * pNode );
33 static float Map_MappingSetRefsAndWire_rec( Map_Man_t * pMan, Map_Node_t * pNode );
34 static void Map_MappingDfsCuts_rec( Map_Node_t * pNode, Map_NodeVec_t * vNodes );
35 static float Map_MappingArea_rec( Map_Man_t * pMan, Map_Node_t * pNode, Map_NodeVec_t * vNodes );
36 static int Map_MappingCompareOutputDelay( Map_Node_t ** ppNode1, Map_Node_t ** ppNode2 );
37 static void Map_MappingFindLatest( Map_Man_t * p, int * pNodes, int nNodesMax );
38 static unsigned Map_MappingExpandTruth_rec( unsigned uTruth, int nVars );
39 static int Map_MappingCountUsedNodes( Map_Man_t * pMan, int fChoices );
40 
41 ////////////////////////////////////////////////////////////////////////
42 /// FUNCTION DEFINITIONS ///
43 ////////////////////////////////////////////////////////////////////////
44 
45 /**Function*************************************************************
46 
47  Synopsis [Computes the DFS ordering of the nodes.]
48 
49  Description []
50 
51  SideEffects []
52 
53  SeeAlso []
54 
55 ***********************************************************************/
56 void Map_MappingDfs_rec( Map_Node_t * pNode, Map_NodeVec_t * vNodes, int fCollectEquiv )
57 {
58  assert( !Map_IsComplement(pNode) );
59  if ( pNode->fMark0 )
60  return;
61  // visit the transitive fanin
62  if ( Map_NodeIsAnd(pNode) )
63  {
64  Map_MappingDfs_rec( Map_Regular(pNode->p1), vNodes, fCollectEquiv );
65  Map_MappingDfs_rec( Map_Regular(pNode->p2), vNodes, fCollectEquiv );
66  }
67  // visit the equivalent nodes
68  if ( fCollectEquiv && pNode->pNextE )
69  Map_MappingDfs_rec( pNode->pNextE, vNodes, fCollectEquiv );
70  // make sure the node is not visited through the equivalent nodes
71  assert( pNode->fMark0 == 0 );
72  // mark the node as visited
73  pNode->fMark0 = 1;
74  // add the node to the list
75  Map_NodeVecPush( vNodes, pNode );
76 }
77 Map_NodeVec_t * Map_MappingDfs( Map_Man_t * pMan, int fCollectEquiv )
78 {
79  Map_NodeVec_t * vNodes;
80  int i;
81  // perform the traversal
82  vNodes = Map_NodeVecAlloc( 100 );
83  for ( i = 0; i < pMan->nOutputs; i++ )
84  Map_MappingDfs_rec( Map_Regular(pMan->pOutputs[i]), vNodes, fCollectEquiv );
85  for ( i = 0; i < vNodes->nSize; i++ )
86  vNodes->pArray[i]->fMark0 = 0;
87 // for ( i = 0; i < pMan->nOutputs; i++ )
88 // Map_MappingUnmark_rec( Map_Regular(pMan->pOutputs[i]) );
89  return vNodes;
90 }
91 
92 /**Function*************************************************************
93 
94  Synopsis [Computes the number of logic levels not counting PIs/POs.]
95 
96  Description []
97 
98  SideEffects [Note that this procedure will reassign the levels assigned
99  originally by NodeCreate() because it counts the number of levels with
100  choices differently!]
101 
102  SeeAlso []
103 
104 ***********************************************************************/
105 int Map_MappingCountLevels( Map_Man_t * pMan )
106 {
107  int i, LevelsMax, LevelsCur;
108  // perform the traversal
109  LevelsMax = -1;
110  for ( i = 0; i < pMan->nOutputs; i++ )
111  {
112  LevelsCur = Map_MappingCountLevels_rec( Map_Regular(pMan->pOutputs[i]) );
113  if ( LevelsMax < LevelsCur )
114  LevelsMax = LevelsCur;
115  }
116  for ( i = 0; i < pMan->nOutputs; i++ )
117  Map_MappingUnmark_rec( Map_Regular(pMan->pOutputs[i]) );
118  return LevelsMax;
119 }
120 
121 /**Function*************************************************************
122 
123  Synopsis [Recursively computes the number of logic levels.]
124 
125  Description []
126 
127  SideEffects []
128 
129  SeeAlso []
130 
131 ***********************************************************************/
132 int Map_MappingCountLevels_rec( Map_Node_t * pNode )
133 {
134  int Level1, Level2;
135  assert( !Map_IsComplement(pNode) );
136  if ( !Map_NodeIsAnd(pNode) )
137  {
138  pNode->Level = 0;
139  return 0;
140  }
141  if ( pNode->fMark0 )
142  return pNode->Level;
143  pNode->fMark0 = 1;
144  // visit the transitive fanin
145  Level1 = Map_MappingCountLevels_rec( Map_Regular(pNode->p1) );
146  Level2 = Map_MappingCountLevels_rec( Map_Regular(pNode->p2) );
147  // set the number of levels
148  pNode->Level = 1 + ((Level1>Level2)? Level1: Level2);
149  return pNode->Level;
150 }
151 
152 /**Function*************************************************************
153 
154  Synopsis [Unmarks the nodes.]
155 
156  Description []
157 
158  SideEffects []
159 
160  SeeAlso []
161 
162 ***********************************************************************/
163 void Map_MappingUnmark( Map_Man_t * pMan )
164 {
165  int i;
166  for ( i = 0; i < pMan->nOutputs; i++ )
167  Map_MappingUnmark_rec( Map_Regular(pMan->pOutputs[i]) );
168 }
169 
170 /**Function*************************************************************
171 
172  Synopsis [Recursively unmarks the nodes.]
173 
174  Description []
175 
176  SideEffects []
177 
178  SeeAlso []
179 
180 ***********************************************************************/
181 void Map_MappingUnmark_rec( Map_Node_t * pNode )
182 {
183  assert( !Map_IsComplement(pNode) );
184  if ( pNode->fMark0 == 0 )
185  return;
186  pNode->fMark0 = 0;
187  if ( !Map_NodeIsAnd(pNode) )
188  return;
189  Map_MappingUnmark_rec( Map_Regular(pNode->p1) );
190  Map_MappingUnmark_rec( Map_Regular(pNode->p2) );
191  // visit the equivalent nodes
192  if ( pNode->pNextE )
193  Map_MappingUnmark_rec( pNode->pNextE );
194 }
195 
196 /**Function*************************************************************
197 
198  Synopsis []
199 
200  Description []
201 
202  SideEffects []
203 
204  SeeAlso []
205 
206 ***********************************************************************/
207 void Map_MappingMark_rec( Map_Node_t * pNode )
208 {
209  assert( !Map_IsComplement(pNode) );
210  if ( pNode->fMark0 == 1 )
211  return;
212  pNode->fMark0 = 1;
213  if ( !Map_NodeIsAnd(pNode) )
214  return;
215  // visit the transitive fanin of the selected cut
216  Map_MappingMark_rec( Map_Regular(pNode->p1) );
217  Map_MappingMark_rec( Map_Regular(pNode->p2) );
218 }
219 
220 /**Function*************************************************************
221 
222  Synopsis [Compares the outputs by their arrival times.]
223 
224  Description []
225 
226  SideEffects []
227 
228  SeeAlso []
229 
230 ***********************************************************************/
231 int Map_MappingCompareOutputDelay( Map_Node_t ** ppNode1, Map_Node_t ** ppNode2 )
232 {
233  Map_Node_t * pNode1 = Map_Regular(*ppNode1);
234  Map_Node_t * pNode2 = Map_Regular(*ppNode2);
235  int fPhase1 = !Map_IsComplement(*ppNode1);
236  int fPhase2 = !Map_IsComplement(*ppNode2);
237  float Arrival1 = pNode1->tArrival[fPhase1].Worst;
238  float Arrival2 = pNode2->tArrival[fPhase2].Worst;
239  if ( Arrival1 < Arrival2 )
240  return -1;
241  if ( Arrival1 > Arrival2 )
242  return 1;
243  return 0;
244 }
245 
246 /**Function*************************************************************
247 
248  Synopsis [Finds given number of latest arriving COs.]
249 
250  Description []
251 
252  SideEffects []
253 
254  SeeAlso []
255 
256 ***********************************************************************/
257 void Map_MappingFindLatest( Map_Man_t * p, int * pNodes, int nNodesMax )
258 {
259  int nNodes, i, k, v;
260  assert( p->nOutputs >= nNodesMax );
261  pNodes[0] = 0;
262  nNodes = 1;
263  for ( i = 1; i < p->nOutputs; i++ )
264  {
265  for ( k = nNodes - 1; k >= 0; k-- )
266  if ( Map_MappingCompareOutputDelay( &p->pOutputs[pNodes[k]], &p->pOutputs[i] ) >= 0 )
267  break;
268  if ( k == nNodesMax - 1 )
269  continue;
270  if ( nNodes < nNodesMax )
271  nNodes++;
272  for ( v = nNodes - 1; v > k+1; v-- )
273  pNodes[v] = pNodes[v-1];
274  pNodes[k+1] = i;
275  }
276 }
277 
278 /**Function*************************************************************
279 
280  Synopsis [Prints a bunch of latest arriving outputs.]
281 
282  Description []
283 
284  SideEffects []
285 
286  SeeAlso []
287 
288 ***********************************************************************/
289 void Map_MappingPrintOutputArrivals( Map_Man_t * p )
290 {
291  int pSorted[MAP_CO_LIST_SIZE];
292  Map_Time_t * pTimes;
293  Map_Node_t * pNode;
294  int fPhase, Limit, i;
295  int MaxNameSize;
296 
297  // determine the number of nodes to print
298  Limit = (p->nOutputs > MAP_CO_LIST_SIZE)? MAP_CO_LIST_SIZE : p->nOutputs;
299 
300  // determine the order
301  Map_MappingFindLatest( p, pSorted, Limit );
302 
303  // determine max size of the node's name
304  MaxNameSize = 0;
305  for ( i = 0; i < Limit; i++ )
306  if ( MaxNameSize < (int)strlen(p->ppOutputNames[pSorted[i]]) )
307  MaxNameSize = strlen(p->ppOutputNames[pSorted[i]]);
308 
309  // print the latest outputs
310  for ( i = 0; i < Limit; i++ )
311  {
312  // get the i-th latest output
313  pNode = Map_Regular(p->pOutputs[pSorted[i]]);
314  fPhase =!Map_IsComplement(p->pOutputs[pSorted[i]]);
315  pTimes = pNode->tArrival + fPhase;
316  // print out the best arrival time
317  printf( "Output %-*s : ", MaxNameSize + 3, p->ppOutputNames[pSorted[i]] );
318  printf( "Delay = (%5.2f, %5.2f) ", (double)pTimes->Rise, (double)pTimes->Fall );
319  printf( "%s", fPhase? "POS" : "NEG" );
320  printf( "\n" );
321  }
322 }
323 
324 /**Function*************************************************************
325 
326  Synopsis [Sets up the truth tables.]
327 
328  Description []
329 
330  SideEffects []
331 
332  SeeAlso []
333 
334 ***********************************************************************/
335 void Map_MappingSetupTruthTables( unsigned uTruths[][2] )
336 {
337  int m, v;
338  // set up the truth tables
339  for ( m = 0; m < 32; m++ )
340  for ( v = 0; v < 5; v++ )
341  if ( m & (1 << v) )
342  uTruths[v][0] |= (1 << m);
343  // make adjustments for the case of 6 variables
344  for ( v = 0; v < 5; v++ )
345  uTruths[v][1] = uTruths[v][0];
346  uTruths[5][0] = 0;
347  uTruths[5][1] = MAP_FULL;
348 }
349 
350 /**Function*************************************************************
351 
352  Synopsis [Sets up the truth tables.]
353 
354  Description []
355 
356  SideEffects []
357 
358  SeeAlso []
359 
360 ***********************************************************************/
361 void Map_MappingSetupTruthTablesLarge( unsigned uTruths[][32] )
362 {
363  int m, v;
364  // clean everything
365  for ( m = 0; m < 32; m++ )
366  for ( v = 0; v < 10; v++ )
367  uTruths[v][m] = 0;
368  // set up the truth tables
369  for ( m = 0; m < 32; m++ )
370  for ( v = 0; v < 5; v++ )
371  if ( m & (1 << v) )
372  {
373  uTruths[v][0] |= (1 << m);
374  uTruths[v+5][m] = MAP_FULL;
375  }
376  // extend this info for the rest of the first 5 variables
377  for ( m = 0; m < 32; m++ )
378  for ( v = 0; v < 5; v++ )
379  uTruths[v][m] = uTruths[v][0];
380 /*
381  // verify
382  for ( m = 0; m < 1024; m++, printf("\n") )
383  for ( v = 0; v < 10; v++ )
384  if ( Map_InfoReadVar( uTruths[v], m ) )
385  printf( "1" );
386  else
387  printf( "0" );
388 */
389 }
390 
391 /**Function*************************************************************
392 
393  Synopsis [Sets up the mask.]
394 
395  Description []
396 
397  SideEffects []
398 
399  SeeAlso []
400 
401 ***********************************************************************/
402 void Map_MappingSetupMask( unsigned uMask[], int nVarsMax )
403 {
404  if ( nVarsMax == 6 )
405  uMask[0] = uMask[1] = MAP_FULL;
406  else
407  {
408  uMask[0] = MAP_MASK(1 << nVarsMax);
409  uMask[1] = 0;
410  }
411 }
412 
413 /**Function*************************************************************
414 
415  Synopsis [Verify one useful property.]
416 
417  Description [This procedure verifies one useful property. After
418  the FRAIG construction with choice nodes is over, each primary node
419  should have fanins that are primary nodes. The primary nodes is the
420  one that does not have pNode->pRepr set to point to another node.]
421 
422  SideEffects []
423 
424  SeeAlso []
425 
426 ***********************************************************************/
427 int Map_ManCheckConsistency( Map_Man_t * p )
428 {
429  Map_Node_t * pNode;
430  Map_NodeVec_t * pVec;
431  int i;
432  pVec = Map_MappingDfs( p, 0 );
433  for ( i = 0; i < pVec->nSize; i++ )
434  {
435  pNode = pVec->pArray[i];
436  if ( Map_NodeIsVar(pNode) )
437  {
438  if ( pNode->pRepr )
439  printf( "Primary input %d is a secondary node.\n", pNode->Num );
440  }
441  else if ( Map_NodeIsConst(pNode) )
442  {
443  if ( pNode->pRepr )
444  printf( "Constant 1 %d is a secondary node.\n", pNode->Num );
445  }
446  else
447  {
448  if ( pNode->pRepr )
449  printf( "Internal node %d is a secondary node.\n", pNode->Num );
450  if ( Map_Regular(pNode->p1)->pRepr )
451  printf( "Internal node %d has first fanin that is a secondary node.\n", pNode->Num );
452  if ( Map_Regular(pNode->p2)->pRepr )
453  printf( "Internal node %d has second fanin that is a secondary node.\n", pNode->Num );
454  }
455  }
456  Map_NodeVecFree( pVec );
457  return 1;
458 }
459 
460 /**Function*************************************************************
461 
462  Synopsis [Returns 1 if current mapping of the node violates fanout limits.]
463 
464  Description []
465 
466  SideEffects []
467 
468  SeeAlso []
469 
470 ***********************************************************************/
471 int Map_MappingNodeIsViolator( Map_Node_t * pNode, Map_Cut_t * pCut, int fPosPol )
472 {
473  return pNode->nRefAct[fPosPol] > (int)pCut->M[fPosPol].pSuperBest->nFanLimit;
474 }
475 
476 /**Function*************************************************************
477 
478  Synopsis [Computes the total are flow of the network.]
479 
480  Description []
481 
482  SideEffects []
483 
484  SeeAlso []
485 
486 ***********************************************************************/
487 float Map_MappingGetAreaFlow( Map_Man_t * p )
488 {
489  Map_Node_t * pNode;
490  Map_Cut_t * pCut;
491  float aFlowFlowTotal = 0;
492  int fPosPol, i;
493  for ( i = 0; i < p->nOutputs; i++ )
494  {
495  pNode = Map_Regular(p->pOutputs[i]);
496  if ( !Map_NodeIsAnd(pNode) )
497  continue;
498  fPosPol = !Map_IsComplement(p->pOutputs[i]);
499  pCut = pNode->pCutBest[fPosPol];
500  if ( pCut == NULL )
501  {
502  fPosPol = !fPosPol;
503  pCut = pNode->pCutBest[fPosPol];
504  }
505  aFlowFlowTotal += pNode->pCutBest[fPosPol]->M[fPosPol].AreaFlow;
506  }
507  return aFlowFlowTotal;
508 }
509 
510 
511 /**Function*************************************************************
512 
513  Synopsis [Compares the supergates by their level.]
514 
515  Description []
516 
517  SideEffects []
518 
519  SeeAlso []
520 
521 ***********************************************************************/
522 int Map_CompareNodesByLevel( Map_Node_t ** ppS1, Map_Node_t ** ppS2 )
523 {
524  Map_Node_t * pN1 = Map_Regular(*ppS1);
525  Map_Node_t * pN2 = Map_Regular(*ppS2);
526  if ( pN1->Level > pN2->Level )
527  return -1;
528  if ( pN1->Level < pN2->Level )
529  return 1;
530  return 0;
531 }
532 
533 /**Function*************************************************************
534 
535  Synopsis [Orders the nodes in the decreasing order of levels.]
536 
537  Description []
538 
539  SideEffects []
540 
541  SeeAlso []
542 
543 ***********************************************************************/
544 void Map_MappingSortByLevel( Map_Man_t * pMan, Map_NodeVec_t * vNodes )
545 {
546  qsort( (void *)vNodes->pArray, vNodes->nSize, sizeof(Map_Node_t *),
547  (int (*)(const void *, const void *)) Map_CompareNodesByLevel );
548 // assert( Map_CompareNodesByLevel( vNodes->pArray, vNodes->pArray + vNodes->nSize - 1 ) <= 0 );
549 }
550 
551 
552 /**Function*************************************************************
553 
554  Synopsis [Compares the supergates by their pointer.]
555 
556  Description []
557 
558  SideEffects []
559 
560  SeeAlso []
561 
562 ***********************************************************************/
563 int Map_CompareNodesByPointer( Map_Node_t ** ppS1, Map_Node_t ** ppS2 )
564 {
565  if ( *ppS1 < *ppS2 )
566  return -1;
567  if ( *ppS1 > *ppS2 )
568  return 1;
569  return 0;
570 }
571 
572 /**Function*************************************************************
573 
574  Synopsis [Counts how many AIG nodes are mapped in both polarities.]
575 
576  Description []
577 
578  SideEffects []
579 
580  SeeAlso []
581 
582 ***********************************************************************/
583 int Map_MappingCountDoubles( Map_Man_t * pMan, Map_NodeVec_t * vNodes )
584 {
585  Map_Node_t * pNode;
586  int Counter, i;
587  // count the number of equal adjacent nodes
588  Counter = 0;
589  for ( i = 0; i < vNodes->nSize; i++ )
590  {
591  pNode = vNodes->pArray[i];
592  if ( !Map_NodeIsAnd(pNode) )
593  continue;
594  if ( (pNode->nRefAct[0] && pNode->pCutBest[0]) &&
595  (pNode->nRefAct[1] && pNode->pCutBest[1]) )
596  Counter++;
597  }
598  return Counter;
599 }
600 
601 
602 /**Function*************************************************************
603 
604  Synopsis []
605 
606  Description []
607 
608  SideEffects []
609 
610  SeeAlso []
611 
612 ***********************************************************************/
613  st__table * Map_CreateTableGate2Super( Map_Man_t * pMan )
614 {
615  Map_Super_t * pSuper;
616  st__table * tTable;
617  int i, nInputs, v;
618  tTable = st__init_table(strcmp, st__strhash);
619  for ( i = 0; i < pMan->pSuperLib->nSupersAll; i++ )
620  {
621  pSuper = pMan->pSuperLib->ppSupers[i];
622  if ( pSuper->nGates == 1 )
623  {
624  // skip different versions of the same root gate
625  nInputs = Mio_GateReadPinNum(pSuper->pRoot);
626  for ( v = 0; v < nInputs; v++ )
627  if ( pSuper->pFanins[v]->Num != nInputs - 1 - v )
628  break;
629  if ( v != nInputs )
630  continue;
631 // printf( "%s\n", Mio_GateReadName(pSuper->pRoot) );
632  if ( st__insert( tTable, (char *)pSuper->pRoot, (char *)pSuper ) )
633  {
634  assert( 0 );
635  }
636  }
637  }
638  return tTable;
639 }
640 
641 /**Function*************************************************************
642 
643  Synopsis [Get the FRAIG node with phase.]
644 
645  Description []
646 
647  SideEffects []
648 
649  SeeAlso []
650 
651 ***********************************************************************/
652 void Map_ManCleanData( Map_Man_t * p )
653 {
654  int i;
655  for ( i = 0; i < p->vMapObjs->nSize; i++ )
656  p->vMapObjs->pArray[i]->pData0 = p->vMapObjs->pArray[i]->pData1 = 0;
657 }
658 
659 /**Function*************************************************************
660 
661  Synopsis [Expand the truth table]
662 
663  Description []
664 
665  SideEffects []
666 
667  SeeAlso []
668 
669 ***********************************************************************/
670 void Map_MappingExpandTruth( unsigned uTruth[2], int nVars )
671 {
672  assert( nVars < 7 );
673  if ( nVars == 6 )
674  return;
675  if ( nVars < 5 )
676  {
677  uTruth[0] &= MAP_MASK( (1<<nVars) );
678  uTruth[0] = Map_MappingExpandTruth_rec( uTruth[0], nVars );
679  }
680  uTruth[1] = uTruth[0];
681 }
682 
683 /**Function*************************************************************
684 
685  Synopsis [Expand the truth table]
686 
687  Description []
688 
689  SideEffects []
690 
691  SeeAlso []
692 
693 ***********************************************************************/
694 unsigned Map_MappingExpandTruth_rec( unsigned uTruth, int nVars )
695 {
696  assert( nVars < 6 );
697  if ( nVars == 5 )
698  return uTruth;
699  return Map_MappingExpandTruth_rec( uTruth | (uTruth << (1 << nVars)), nVars + 1 );
700 }
701 
702 /**Function*************************************************************
703 
704  Synopsis [Compute the arrival times.]
705 
706  Description []
707 
708  SideEffects []
709 
710  SeeAlso []
711 
712 ***********************************************************************/
713 float Map_MappingComputeDelayWithFanouts( Map_Man_t * p )
714 {
715  Map_Node_t * pNode;
716  float Result;
717  int i;
718  for ( i = 0; i < p->vMapObjs->nSize; i++ )
719  {
720  // skip primary inputs
721  pNode = p->vMapObjs->pArray[i];
722  if ( !Map_NodeIsAnd( pNode ) )
723  continue;
724  // skip a secondary node
725  if ( pNode->pRepr )
726  continue;
727  // count the switching nodes
728  if ( pNode->nRefAct[0] > 0 )
729  Map_TimeCutComputeArrival( pNode, pNode->pCutBest[0], 0, MAP_FLOAT_LARGE );
730  if ( pNode->nRefAct[1] > 0 )
731  Map_TimeCutComputeArrival( pNode, pNode->pCutBest[1], 1, MAP_FLOAT_LARGE );
732  }
733  Result = Map_TimeComputeArrivalMax(p);
734  printf( "Max arrival times with fanouts = %10.2f.\n", Result );
735  return Result;
736 }
737 
738 
739 /**Function*************************************************************
740 
741  Synopsis [Sets up the mask.]
742 
743  Description []
744 
745  SideEffects []
746 
747  SeeAlso []
748 
749 ***********************************************************************/
750 int Map_MappingGetMaxLevel( Map_Man_t * pMan )
751 {
752  int nLevelMax, i;
753  nLevelMax = 0;
754  for ( i = 0; i < pMan->nOutputs; i++ )
755  nLevelMax = ((unsigned)nLevelMax) > Map_Regular(pMan->pOutputs[i])->Level?
756  nLevelMax : Map_Regular(pMan->pOutputs[i])->Level;
757  return nLevelMax;
758 }
759 
760 /**Function*************************************************************
761 
762  Synopsis [Analyses choice nodes.]
763 
764  Description []
765 
766  SideEffects []
767 
768  SeeAlso []
769 
770 ***********************************************************************/
771 int Map_MappingUpdateLevel_rec( Map_Man_t * pMan, Map_Node_t * pNode, int fMaximum )
772 {
773  Map_Node_t * pTemp;
774  int Level1, Level2, LevelE;
775  assert( !Map_IsComplement(pNode) );
776  if ( !Map_NodeIsAnd(pNode) )
777  return pNode->Level;
778  // skip the visited node
779  if ( pNode->TravId == pMan->nTravIds )
780  return pNode->Level;
781  pNode->TravId = pMan->nTravIds;
782  // compute levels of the children nodes
783  Level1 = Map_MappingUpdateLevel_rec( pMan, Map_Regular(pNode->p1), fMaximum );
784  Level2 = Map_MappingUpdateLevel_rec( pMan, Map_Regular(pNode->p2), fMaximum );
785  pNode->Level = 1 + MAP_MAX( Level1, Level2 );
786  if ( pNode->pNextE )
787  {
788  LevelE = Map_MappingUpdateLevel_rec( pMan, pNode->pNextE, fMaximum );
789  if ( fMaximum )
790  {
791  if ( pNode->Level < (unsigned)LevelE )
792  pNode->Level = LevelE;
793  }
794  else
795  {
796  if ( pNode->Level > (unsigned)LevelE )
797  pNode->Level = LevelE;
798  }
799  // set the level of all equivalent nodes to be the same minimum
800  if ( pNode->pRepr == NULL ) // the primary node
801  for ( pTemp = pNode->pNextE; pTemp; pTemp = pTemp->pNextE )
802  pTemp->Level = pNode->Level;
803  }
804  return pNode->Level;
805 }
806 
807 /**Function*************************************************************
808 
809  Synopsis [Resets the levels of the nodes in the choice graph.]
810 
811  Description [Makes the level of the choice nodes to be equal to the
812  maximum of the level of the nodes in the equivalence class. This way
813  sorting by level leads to the reverse topological order, which is
814  needed for the required time computation.]
815 
816  SideEffects []
817 
818  SeeAlso []
819 
820 ***********************************************************************/
821 void Map_MappingSetChoiceLevels( Map_Man_t * pMan )
822 {
823  int i;
824  pMan->nTravIds++;
825  for ( i = 0; i < pMan->nOutputs; i++ )
826  Map_MappingUpdateLevel_rec( pMan, Map_Regular(pMan->pOutputs[i]), 1 );
827 }
828 
829 /**Function*************************************************************
830 
831  Synopsis [Reports statistics on choice nodes.]
832 
833  Description [The number of choice nodes is the number of primary nodes,
834  which has pNextE set to a pointer. The number of choices is the number
835  of entries in the equivalent-node lists of the primary nodes.]
836 
837  SideEffects []
838 
839  SeeAlso []
840 
841 ***********************************************************************/
842 void Map_MappingReportChoices( Map_Man_t * pMan )
843 {
844  Map_Node_t * pNode, * pTemp;
845  int nChoiceNodes, nChoices;
846  int i, LevelMax1, LevelMax2;
847 
848  // report the number of levels
849  LevelMax1 = Map_MappingGetMaxLevel( pMan );
850  pMan->nTravIds++;
851  for ( i = 0; i < pMan->nOutputs; i++ )
852  Map_MappingUpdateLevel_rec( pMan, Map_Regular(pMan->pOutputs[i]), 0 );
853  LevelMax2 = Map_MappingGetMaxLevel( pMan );
854 
855  // report statistics about choices
856  nChoiceNodes = nChoices = 0;
857  for ( i = 0; i < pMan->vMapObjs->nSize; i++ )
858  {
859  pNode = pMan->vMapObjs->pArray[i];
860  if ( pNode->pRepr == NULL && pNode->pNextE != NULL )
861  { // this is a choice node = the primary node that has equivalent nodes
862  nChoiceNodes++;
863  for ( pTemp = pNode; pTemp; pTemp = pTemp->pNextE )
864  nChoices++;
865  }
866  }
867  printf( "Maximum level: Original = %d. Reduced due to choices = %d.\n", LevelMax1, LevelMax2 );
868  printf( "Choice stats: Choice nodes = %d. Total choices = %d.\n", nChoiceNodes, nChoices );
869 }
870 
871 /**Function*************************************************************
872 
873  Synopsis [Computes the maximum and minimum levels of the choice nodes.]
874 
875  Description []
876 
877  SideEffects []
878 
879  SeeAlso []
880 
881 ***********************************************************************/
882 int Map_MappingCountUsedNodes( Map_Man_t * pMan, int fChoices )
883 {
884  Map_NodeVec_t * vNodes;
885  int Result;
886  vNodes = Map_MappingDfs( pMan, fChoices );
887  Result = vNodes->nSize;
888  Map_NodeVecFree( vNodes );
889  return Result;
890 }
891 
892 ////////////////////////////////////////////////////////////////////////
893 /// END OF FILE ///
894 ////////////////////////////////////////////////////////////////////////
895 
896 
897 ABC_NAMESPACE_IMPL_END
898 
Map_MappingMark_rec
void Map_MappingMark_rec(Map_Node_t *pNode)
Definition: mapperUtils.c:207
Map_MappingArea_rec
static float Map_MappingArea_rec(Map_Man_t *pMan, Map_Node_t *pNode, Map_NodeVec_t *vNodes)
Map_NodeIsAnd
int Map_NodeIsAnd(Map_Node_t *p)
Definition: mapperCreate.c:115
Map_NodeVecAlloc
Map_NodeVec_t * Map_NodeVecAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: mapperVec.c:45
Map_NodeStruct_t_::pNextE
Map_Node_t * pNextE
Definition: mapperInt.h:223
MAP_FLOAT_LARGE
#define MAP_FLOAT_LARGE
Definition: mapperInt.h:60
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Map_TimeStruct_t_::Worst
float Worst
Definition: mapper.h:56
st__insert
int st__insert(st__table *table, const char *key, char *value)
Definition: st.c:171
Map_MappingSetChoiceLevels
void Map_MappingSetChoiceLevels(Map_Man_t *pMan)
Definition: mapperUtils.c:821
Map_CompareNodesByLevel
int Map_CompareNodesByLevel(Map_Node_t **ppS1, Map_Node_t **ppS2)
Definition: mapperUtils.c:522
Map_NodeStruct_t_::pCutBest
Map_Cut_t * pCutBest[2]
Definition: mapperInt.h:239
Map_MappingSortByLevel
void Map_MappingSortByLevel(Map_Man_t *pMan, Map_NodeVec_t *vNodes)
Definition: mapperUtils.c:544
Map_MappingUnmark_rec
void Map_MappingUnmark_rec(Map_Node_t *pNode)
Definition: mapperUtils.c:181
MAP_MASK
#define MAP_MASK(n)
INCLUDES ///.
Definition: mapperInt.h:51
Map_CompareNodesByPointer
int Map_CompareNodesByPointer(Map_Node_t **ppS1, Map_Node_t **ppS2)
Definition: mapperUtils.c:563
Map_NodeVecStruct_t_::nSize
int nSize
Definition: mapperInt.h:302
Map_MappingGetAreaFlow
float Map_MappingGetAreaFlow(Map_Man_t *p)
Definition: mapperUtils.c:487
Map_CutStruct_t_
Definition: mapperInt.h:260
Map_NodeStruct_t_::nRefAct
int nRefAct[3]
Definition: mapperInt.h:216
Map_NodeStruct_t_::Num
int Num
Definition: mapperInt.h:206
Map_MappingCompareOutputDelay
static int Map_MappingCompareOutputDelay(Map_Node_t **ppNode1, Map_Node_t **ppNode2)
Definition: mapperUtils.c:231
Map_MappingSetRefsAndWire_rec
static float Map_MappingSetRefsAndWire_rec(Map_Man_t *pMan, Map_Node_t *pNode)
Map_NodeStruct_t_::tArrival
Map_Time_t tArrival[2]
Definition: mapperInt.h:235
Map_MappingReportChoices
void Map_MappingReportChoices(Map_Man_t *pMan)
Definition: mapperUtils.c:842
Map_TimeStruct_t_::Rise
float Rise
Definition: mapper.h:54
Map_MappingDfs_rec
void Map_MappingDfs_rec(Map_Node_t *pNode, Map_NodeVec_t *vNodes, int fCollectEquiv)
FUNCTION DEFINITIONS ///.
Definition: mapperUtils.c:56
Map_NodeIsConst
int Map_NodeIsConst(Map_Node_t *p)
Definition: mapperCreate.c:112
Map_IsComplement
#define Map_IsComplement(p)
GLOBAL VARIABLES ///.
Definition: mapper.h:67
Map_MatchStruct_t_::pSuperBest
Map_Super_t * pSuperBest
Definition: mapperInt.h:253
MAP_FULL
#define MAP_FULL
Definition: mapperInt.h:52
Map_NodeStruct_t_::Level
unsigned Level
Definition: mapperInt.h:214
strcmp
int strcmp()
Map_MappingSetRefsAndArea_rec
static float Map_MappingSetRefsAndArea_rec(Map_Man_t *pMan, Map_Node_t *pNode)
Map_MappingSetupMask
void Map_MappingSetupMask(unsigned uMask[], int nVarsMax)
Definition: mapperUtils.c:402
st__init_table
st__table * st__init_table(st__compare_func_type compare, st__hash_func_type hash)
Definition: st.c:72
Map_SuperStruct_t_
Definition: mapperInt.h:275
Mio_GateReadPinNum
int Mio_GateReadPinNum(Mio_Gate_t *pGate)
Definition: mioApi.c:151
Map_MappingSetupTruthTables
void Map_MappingSetupTruthTables(unsigned uTruths[][2])
Definition: mapperUtils.c:335
Map_SuperStruct_t_::nGates
unsigned nGates
Definition: mapperInt.h:281
Map_SuperStruct_t_::pRoot
Mio_Gate_t * pRoot
Definition: mapperInt.h:288
st__strhash
int st__strhash(const char *string, int modulus)
Definition: st.c:449
Map_MappingGetMaxLevel
int Map_MappingGetMaxLevel(Map_Man_t *pMan)
Definition: mapperUtils.c:750
Map_MappingDfsCuts_rec
static void Map_MappingDfsCuts_rec(Map_Node_t *pNode, Map_NodeVec_t *vNodes)
Map_MappingExpandTruth_rec
static unsigned Map_MappingExpandTruth_rec(unsigned uTruth, int nVars)
Definition: mapperUtils.c:694
Map_MatchStruct_t_::AreaFlow
float AreaFlow
Definition: mapperInt.h:256
Map_MappingComputeDelayWithFanouts
float Map_MappingComputeDelayWithFanouts(Map_Man_t *p)
Definition: mapperUtils.c:713
Map_MappingFindLatest
static void Map_MappingFindLatest(Map_Man_t *p, int *pNodes, int nNodesMax)
Definition: mapperUtils.c:257
Map_TimeComputeArrivalMax
float Map_TimeComputeArrivalMax(Map_Man_t *p)
DECLARATIONS ///.
Definition: mapperTime.c:42
st__table
Definition: st.h:52
Map_NodeVecStruct_t_::pArray
Map_Node_t ** pArray
Definition: mapperInt.h:301
Map_MappingSetupTruthTablesLarge
void Map_MappingSetupTruthTablesLarge(unsigned uTruths[][32])
Definition: mapperUtils.c:361
Map_ManCleanData
void Map_ManCleanData(Map_Man_t *p)
Definition: mapperUtils.c:652
Map_SuperStruct_t_::nFanLimit
unsigned nFanLimit
Definition: mapperInt.h:282
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
Map_NodeIsVar
int Map_NodeIsVar(Map_Node_t *p)
Definition: mapperCreate.c:113
Map_SuperStruct_t_::pFanins
Map_Super_t * pFanins[6]
Definition: mapperInt.h:287
MAP_CO_LIST_SIZE
#define MAP_CO_LIST_SIZE
DECLARATIONS ///.
Definition: mapperUtils.c:28
Map_TimeCutComputeArrival
float Map_TimeCutComputeArrival(Map_Node_t *pNode, Map_Cut_t *pCut, int fPhase, float tWorstCaseLimit)
Definition: mapperTime.c:72
Map_ManCheckConsistency
int Map_ManCheckConsistency(Map_Man_t *p)
Definition: mapperUtils.c:427
Counter
static int Counter
Definition: extraBddMisc.c:1877
Map_MappingDfs
Map_NodeVec_t * Map_MappingDfs(Map_Man_t *pMan, int fCollectEquiv)
Definition: mapperUtils.c:77
Map_NodeStruct_t_::p2
Map_Node_t * p2
Definition: mapperInt.h:222
Map_MappingCountUsedNodes
static int Map_MappingCountUsedNodes(Map_Man_t *pMan, int fChoices)
Definition: mapperUtils.c:882
Map_NodeStruct_t_::p1
Map_Node_t * p1
Definition: mapperInt.h:221
ABC_NAMESPACE_IMPL_START
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
Map_TimeStruct_t_::Fall
float Fall
Definition: mapper.h:55
Map_Regular
#define Map_Regular(p)
Definition: mapper.h:68
Map_Man_t
typedefABC_NAMESPACE_HEADER_START struct Map_ManStruct_t_ Map_Man_t
INCLUDES ///.
Definition: mapper.h:40
Map_NodeVecStruct_t_
Definition: mapperInt.h:299
Map_CreateTableGate2Super
st__table * Map_CreateTableGate2Super(Map_Man_t *pMan)
Definition: mapperUtils.c:613
Map_MappingPrintOutputArrivals
void Map_MappingPrintOutputArrivals(Map_Man_t *p)
Definition: mapperUtils.c:289
Map_NodeVecFree
void Map_NodeVecFree(Map_NodeVec_t *p)
Definition: mapperVec.c:68
Map_NodeStruct_t_::pRepr
Map_Node_t * pRepr
Definition: mapperInt.h:224
Map_MappingUnmark
void Map_MappingUnmark(Map_Man_t *pMan)
Definition: mapperUtils.c:163
Map_MappingCountDoubles
int Map_MappingCountDoubles(Map_Man_t *pMan, Map_NodeVec_t *vNodes)
Definition: mapperUtils.c:583
Map_MappingNodeIsViolator
int Map_MappingNodeIsViolator(Map_Node_t *pNode, Map_Cut_t *pCut, int fPosPol)
Definition: mapperUtils.c:471
Map_MappingExpandTruth
void Map_MappingExpandTruth(unsigned uTruth[2], int nVars)
Definition: mapperUtils.c:670
Map_MappingCountLevels
int Map_MappingCountLevels(Map_Man_t *pMan)
Definition: mapperUtils.c:105
Map_SuperStruct_t_::Num
int Num
Definition: mapperInt.h:277
Map_MappingUpdateLevel_rec
int Map_MappingUpdateLevel_rec(Map_Man_t *pMan, Map_Node_t *pNode, int fMaximum)
Definition: mapperUtils.c:771
assert
#define assert(ex)
Definition: util_old.h:213
strlen
int strlen()
Map_NodeStruct_t_::fMark0
unsigned fMark0
Definition: mapperInt.h:209
Map_NodeStruct_t_
Definition: mapperInt.h:201
Map_MappingSetRefsAndSwitch_rec
static float Map_MappingSetRefsAndSwitch_rec(Map_Man_t *pMan, Map_Node_t *pNode)
Map_NodeVecPush
void Map_NodeVecPush(Map_NodeVec_t *p, Map_Node_t *Entry)
Definition: mapperVec.c:190
Map_MappingCountLevels_rec
static int Map_MappingCountLevels_rec(Map_Node_t *pNode)
Definition: mapperUtils.c:132
Map_CutStruct_t_::M
Map_Match_t M[2]
Definition: mapperInt.h:271
Map_NodeStruct_t_::TravId
int TravId
Definition: mapperInt.h:207
MAP_MAX
#define MAP_MAX(a, b)
Definition: mapperInt.h:57
Map_TimeStruct_t_
Definition: mapper.h:52