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 ***********************************************************************/
Fpga_MappingDfs(Fpga_Man_t * pMan,int fCollectEquiv)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 ***********************************************************************/
Fpga_MappingDfs_rec(Fpga_Node_t * pNode,Fpga_NodeVec_t * vNodes,int fCollectEquiv)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 ***********************************************************************/
Fpga_MappingDfsNodes(Fpga_Man_t * pMan,Fpga_Node_t ** ppNodes,int nNodes,int fEquiv)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 ***********************************************************************/
Fpga_MappingGetAreaFlow(Fpga_Man_t * p)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 ***********************************************************************/
Fpga_MappingArea(Fpga_Man_t * pMan)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 ***********************************************************************/
Fpga_MappingArea_rec(Fpga_Man_t * pMan,Fpga_Node_t * pNode,Fpga_NodeVec_t * vNodes)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 ***********************************************************************/
Fpga_MappingAreaTrav(Fpga_Man_t * pMan)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 ***********************************************************************/
Fpga_MappingSetRefsAndArea_rec(Fpga_Man_t * pMan,Fpga_Node_t * pNode,Fpga_Node_t ** ppStore)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 ***********************************************************************/
Fpga_MappingSetRefsAndArea(Fpga_Man_t * pMan)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 ***********************************************************************/
Fpga_MappingCompareOutputDelay(Fpga_Node_t ** ppNode1,Fpga_Node_t ** ppNode2)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 ***********************************************************************/
Fpga_MappingFindLatest(Fpga_Man_t * p,int * pNodes,int nNodesMax)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 ***********************************************************************/
Fpga_MappingPrintOutputArrivals(Fpga_Man_t * p)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 ***********************************************************************/
Fpga_MappingSetupTruthTables(unsigned uTruths[][2])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 ***********************************************************************/
Fpga_MappingSetupMask(unsigned uMask[],int nVarsMax)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 ***********************************************************************/
Fpga_ManCheckConsistency(Fpga_Man_t * p)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 ***********************************************************************/
Fpga_CompareNodesByLevelDecreasing(Fpga_Node_t ** ppS1,Fpga_Node_t ** ppS2)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 ***********************************************************************/
Fpga_CompareNodesByLevelIncreasing(Fpga_Node_t ** ppS1,Fpga_Node_t ** ppS2)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 ***********************************************************************/
Fpga_MappingSortByLevel(Fpga_Man_t * pMan,Fpga_NodeVec_t * vNodes,int fIncreasing)584 void Fpga_MappingSortByLevel( Fpga_Man_t * pMan, Fpga_NodeVec_t * vNodes, int fIncreasing )
585 {
586 if ( fIncreasing )
587 qsort( (void *)vNodes->pArray, (size_t)vNodes->nSize, sizeof(Fpga_Node_t *),
588 (int (*)(const void *, const void *)) Fpga_CompareNodesByLevelIncreasing );
589 else
590 qsort( (void *)vNodes->pArray, (size_t)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 ***********************************************************************/
Fpga_DfsLim(Fpga_Man_t * pMan,Fpga_Node_t * pNode,int nLevels)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 ***********************************************************************/
Fpga_DfsLim_rec(Fpga_Node_t * pNode,int Level,Fpga_NodeVec_t * vNodes)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 ***********************************************************************/
Fpga_ManCleanData0(Fpga_Man_t * pMan)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 ***********************************************************************/
Fpga_CollectNodeTfo(Fpga_Man_t * pMan,Fpga_Node_t * pNode)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 ***********************************************************************/
Fpga_CollectNodeTfo_rec(Fpga_Node_t * pNode,Fpga_Node_t * pPivot,Fpga_NodeVec_t * vVisited,Fpga_NodeVec_t * vTfo)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 ***********************************************************************/
Fpga_MappingLevelize(Fpga_Man_t * pMan,Fpga_NodeVec_t * vNodes)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 ***********************************************************************/
Fpga_MappingMaxLevel(Fpga_Man_t * pMan)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 ***********************************************************************/
Fpga_MappingUpdateLevel_rec(Fpga_Man_t * pMan,Fpga_Node_t * pNode,int fMaximum)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 ***********************************************************************/
Fpga_MappingSetChoiceLevels(Fpga_Man_t * pMan)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 ***********************************************************************/
Fpga_ManReportChoices(Fpga_Man_t * pMan)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 ***********************************************************************/
Fpga_MappingOrderCosByLevel(Fpga_Man_t * pMan)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
991