1 /**CFile****************************************************************
2
3 FileName [ifUtil.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [FPGA mapping based on priority cuts.]
8
9 Synopsis [Various utilities.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - November 21, 2006.]
16
17 Revision [$Id: ifUtil.c,v 1.00 2006/11/21 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "if.h"
22
23 ABC_NAMESPACE_IMPL_START
24
25
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29
30 ////////////////////////////////////////////////////////////////////////
31 /// FUNCTION DEFINITIONS ///
32 ////////////////////////////////////////////////////////////////////////
33
34 /**Function*************************************************************
35
36 Synopsis [Sets all the node copy to NULL.]
37
38 Description []
39
40 SideEffects []
41
42 SeeAlso []
43
44 ***********************************************************************/
If_ManCleanNodeCopy(If_Man_t * p)45 void If_ManCleanNodeCopy( If_Man_t * p )
46 {
47 If_Obj_t * pObj;
48 int i;
49 If_ManForEachObj( p, pObj, i )
50 If_ObjSetCopy( pObj, NULL );
51 }
52
53 /**Function*************************************************************
54
55 Synopsis [Sets all the cut data to NULL.]
56
57 Description []
58
59 SideEffects []
60
61 SeeAlso []
62
63 ***********************************************************************/
If_ManCleanCutData(If_Man_t * p)64 void If_ManCleanCutData( If_Man_t * p )
65 {
66 If_Obj_t * pObj;
67 int i;
68 If_ManForEachObj( p, pObj, i )
69 If_CutSetData( If_ObjCutBest(pObj), NULL );
70 }
71
72 /**Function*************************************************************
73
74 Synopsis [Sets all visited marks to 0.]
75
76 Description []
77
78 SideEffects []
79
80 SeeAlso []
81
82 ***********************************************************************/
If_ManCleanMarkV(If_Man_t * p)83 void If_ManCleanMarkV( If_Man_t * p )
84 {
85 If_Obj_t * pObj;
86 int i;
87 If_ManForEachObj( p, pObj, i )
88 pObj->fVisit = 0;
89 }
90
91 #if 0
92
93 /**Function*************************************************************
94
95 Synopsis [Computes area, references, and nodes used in the mapping.]
96
97 Description []
98
99 SideEffects []
100
101 SeeAlso []
102
103 ***********************************************************************/
104 float If_ManScanMapping_rec( If_Man_t * p, If_Obj_t * pObj, If_Obj_t ** ppStore )
105 {
106 If_Obj_t * pLeaf;
107 If_Cut_t * pCutBest;
108 float aArea;
109 int i;
110 if ( pObj->nRefs++ || If_ObjIsCi(pObj) || If_ObjIsConst1(pObj) )
111 return 0.0;
112 // store the node in the structure by level
113 assert( If_ObjIsAnd(pObj) );
114 pObj->pCopy = (char *)ppStore[pObj->Level];
115 ppStore[pObj->Level] = pObj;
116 // visit the transitive fanin of the selected cut
117 pCutBest = If_ObjCutBest(pObj);
118 p->nNets += pCutBest->nLeaves;
119 aArea = If_CutLutArea( p, pCutBest );
120 If_CutForEachLeaf( p, pCutBest, pLeaf, i )
121 aArea += If_ManScanMapping_rec( p, pLeaf, ppStore );
122 return aArea;
123 }
124
125 /**Function*************************************************************
126
127 Synopsis [Computes area, references, and nodes used in the mapping.]
128
129 Description [Collects the nodes in reverse topological order in array
130 p->vMapping.]
131
132 SideEffects []
133
134 SeeAlso []
135
136 ***********************************************************************/
137 float If_ManScanMapping( If_Man_t * p )
138 {
139 If_Obj_t * pObj, ** ppStore;
140 float aArea;
141 int i;
142 assert( !p->pPars->fLiftLeaves );
143 // clean all references
144 p->nNets = 0;
145 If_ManForEachObj( p, pObj, i )
146 {
147 pObj->Required = IF_FLOAT_LARGE;
148 pObj->nVisits = pObj->nVisitsCopy;
149 pObj->nRefs = 0;
150 }
151 // allocate place to store the nodes
152 ppStore = ABC_ALLOC( If_Obj_t *, p->nLevelMax + 1 );
153 memset( ppStore, 0, sizeof(If_Obj_t *) * (p->nLevelMax + 1) );
154 // collect nodes reachable from POs in the DFS order through the best cuts
155 aArea = 0;
156 If_ManForEachCo( p, pObj, i )
157 aArea += If_ManScanMapping_rec( p, If_ObjFanin0(pObj), ppStore );
158 // reconnect the nodes in reverse topological order
159 Vec_PtrClear( p->vMapped );
160 for ( i = p->nLevelMax; i >= 0; i-- )
161 for ( pObj = ppStore[i]; pObj; pObj = pObj->pCopy )
162 Vec_PtrPush( p->vMapped, pObj );
163 ABC_FREE( ppStore );
164 return aArea;
165 }
166
167 /**Function*************************************************************
168
169 Synopsis [Computes area, references, and nodes used in the mapping.]
170
171 Description [Collects the nodes in reverse topological order in array
172 p->vMapping.]
173
174 SideEffects []
175
176 SeeAlso []
177
178 ***********************************************************************/
179 float If_ManScanMappingDirect( If_Man_t * p )
180 {
181 If_Obj_t * pObj, ** ppStore;
182 float aArea;
183 int i;
184 assert( !p->pPars->fLiftLeaves );
185 // clean all references
186 If_ManForEachObj( p, pObj, i )
187 {
188 pObj->Required = IF_FLOAT_LARGE;
189 pObj->nVisits = pObj->nVisitsCopy;
190 pObj->nRefs = 0;
191 }
192 // allocate place to store the nodes
193 ppStore = ABC_ALLOC( If_Obj_t *, p->nLevelMax + 1 );
194 memset( ppStore, 0, sizeof(If_Obj_t *) * (p->nLevelMax + 1) );
195 // collect nodes reachable from POs in the DFS order through the best cuts
196 aArea = 0;
197 If_ManForEachCo( p, pObj, i )
198 aArea += If_ManScanMapping_rec( p, If_ObjFanin0(pObj), ppStore );
199 // reconnect the nodes in reverse topological order
200 Vec_PtrClear( p->vMapped );
201 // for ( i = p->nLevelMax; i >= 0; i-- )
202 for ( i = 0; i <= p->nLevelMax; i++ )
203 for ( pObj = ppStore[i]; pObj; pObj = pObj->pCopy )
204 Vec_PtrPush( p->vMapped, pObj );
205 ABC_FREE( ppStore );
206 return aArea;
207 }
208
209 /**Function*************************************************************
210
211 Synopsis [Computes area, references, and nodes used in the mapping.]
212
213 Description []
214
215 SideEffects []
216
217 SeeAlso []
218
219 ***********************************************************************/
220 float If_ManScanMappingSeq_rec( If_Man_t * p, If_Obj_t * pObj, Vec_Ptr_t * vMapped )
221 {
222 If_Obj_t * pLeaf;
223 If_Cut_t * pCutBest;
224 float aArea;
225 int i, Shift;
226 // treat latches transparently
227 if ( If_ObjIsLatch(pObj) )
228 return If_ManScanMappingSeq_rec( p, If_ObjFanin0(pObj), vMapped );
229 // consider trivial cases
230 if ( pObj->nRefs++ || If_ObjIsPi(pObj) || If_ObjIsConst1(pObj) )
231 return 0.0;
232 // store the node in the structure by level
233 assert( If_ObjIsAnd(pObj) );
234 // visit the transitive fanin of the selected cut
235 pCutBest = If_ObjCutBest(pObj);
236 aArea = If_ObjIsAnd(pObj)? If_CutLutArea(p, pCutBest) : (float)0.0;
237 If_CutForEachLeafSeq( p, pCutBest, pLeaf, Shift, i )
238 aArea += If_ManScanMappingSeq_rec( p, pLeaf, vMapped );
239 // add the node
240 Vec_PtrPush( vMapped, pObj );
241 return aArea;
242 }
243
244 /**Function*************************************************************
245
246 Synopsis [Computes area, references, and nodes used in the mapping.]
247
248 Description [Collects the nodes in reverse topological order in array
249 p->vMapping.]
250
251 SideEffects []
252
253 SeeAlso []
254
255 ***********************************************************************/
256 float If_ManScanMappingSeq( If_Man_t * p )
257 {
258 If_Obj_t * pObj;
259 float aArea;
260 int i;
261 assert( p->pPars->fLiftLeaves );
262 // clean all references
263 If_ManForEachObj( p, pObj, i )
264 pObj->nRefs = 0;
265 // collect nodes reachable from POs in the DFS order through the best cuts
266 aArea = 0;
267 Vec_PtrClear( p->vMapped );
268 If_ManForEachPo( p, pObj, i )
269 aArea += If_ManScanMappingSeq_rec( p, If_ObjFanin0(pObj), p->vMapped );
270 return aArea;
271 }
272
273 #endif
274
275 /**Function*************************************************************
276
277 Synopsis [Computes area, references, and nodes used in the mapping.]
278
279 Description [Collects the nodes in reverse topological order in array
280 p->vMapping.]
281
282 SideEffects []
283
284 SeeAlso []
285
286 ***********************************************************************/
If_ManResetOriginalRefs(If_Man_t * p)287 void If_ManResetOriginalRefs( If_Man_t * p )
288 {
289 If_Obj_t * pObj;
290 int i;
291 If_ManForEachObj( p, pObj, i )
292 pObj->nRefs = 0;
293 If_ManForEachObj( p, pObj, i )
294 {
295 if ( If_ObjIsAnd(pObj) )
296 {
297 pObj->pFanin0->nRefs++;
298 pObj->pFanin1->nRefs++;
299 }
300 else if ( If_ObjIsCo(pObj) )
301 pObj->pFanin0->nRefs++;
302 }
303 }
304
305 /**Function*************************************************************
306
307 Synopsis [Computes cross-cut of the circuit.]
308
309 Description []
310
311 SideEffects []
312
313 SeeAlso []
314
315 ***********************************************************************/
If_ManCrossCut(If_Man_t * p)316 int If_ManCrossCut( If_Man_t * p )
317 {
318 If_Obj_t * pObj, * pFanin;
319 int i, nCutSize = 0, nCutSizeMax = 0;
320 If_ManForEachObj( p, pObj, i )
321 {
322 if ( !If_ObjIsAnd(pObj) )
323 continue;
324 // consider the node
325 if ( nCutSizeMax < ++nCutSize )
326 nCutSizeMax = nCutSize;
327 if ( pObj->nVisits == 0 )
328 nCutSize--;
329 // consider the fanins
330 pFanin = If_ObjFanin0(pObj);
331 if ( !If_ObjIsCi(pFanin) && --pFanin->nVisits == 0 )
332 nCutSize--;
333 pFanin = If_ObjFanin1(pObj);
334 if ( !If_ObjIsCi(pFanin) && --pFanin->nVisits == 0 )
335 nCutSize--;
336 // consider the choice class
337 if ( pObj->fRepr )
338 for ( pFanin = pObj; pFanin; pFanin = pFanin->pEquiv )
339 if ( !If_ObjIsCi(pFanin) && --pFanin->nVisits == 0 )
340 nCutSize--;
341 }
342 If_ManForEachObj( p, pObj, i )
343 {
344 assert( If_ObjIsCi(pObj) || pObj->fVisit == 0 );
345 pObj->nVisits = pObj->nVisitsCopy;
346 }
347 assert( nCutSize == 0 );
348 // Abc_Print( 1, "Max cross cut size = %6d.\n", nCutSizeMax );
349 return nCutSizeMax;
350 }
351
352 /**Function*************************************************************
353
354 Synopsis [Computes the reverse topological order of nodes.]
355
356 Description []
357
358 SideEffects []
359
360 SeeAlso []
361
362 ***********************************************************************/
If_ManReverseOrder(If_Man_t * p)363 Vec_Ptr_t * If_ManReverseOrder( If_Man_t * p )
364 {
365 Vec_Ptr_t * vOrder;
366 If_Obj_t * pObj, ** ppStore;
367 int i;
368 // allocate place to store the nodes
369 ppStore = ABC_ALLOC( If_Obj_t *, p->nLevelMax + 1 );
370 memset( ppStore, 0, sizeof(If_Obj_t *) * (p->nLevelMax + 1) );
371 // add the nodes
372 If_ManForEachObj( p, pObj, i )
373 {
374 assert( pObj->Level >= 0 && pObj->Level <= (unsigned)p->nLevelMax );
375 pObj->pCopy = (char *)ppStore[pObj->Level];
376 ppStore[pObj->Level] = pObj;
377 }
378 vOrder = Vec_PtrAlloc( If_ManObjNum(p) );
379 for ( i = p->nLevelMax; i >= 0; i-- )
380 for ( pObj = ppStore[i]; pObj; pObj = (If_Obj_t *)pObj->pCopy )
381 Vec_PtrPush( vOrder, pObj );
382 ABC_FREE( ppStore );
383 // print the order
384 // Vec_PtrForEachEntry( If_Obj_t *, vOrder, pObj, i )
385 // Abc_Print( 1, "Obj %2d Type %d Level = %d\n", pObj->Id, pObj->Type, pObj->Level );
386 return vOrder;
387 }
388
389 /**Function*************************************************************
390
391 Synopsis [Computes area, references, and nodes used in the mapping.]
392
393 Description []
394
395 SideEffects []
396
397 SeeAlso []
398
399 ***********************************************************************/
If_ManMarkMapping_rec(If_Man_t * p,If_Obj_t * pObj)400 float If_ManMarkMapping_rec( If_Man_t * p, If_Obj_t * pObj )
401 {
402 If_Obj_t * pLeaf;
403 If_Cut_t * pCutBest;
404 float * pSwitching = p->vSwitching? (float*)p->vSwitching->pArray : NULL;
405 float aArea;
406 int i;
407 if ( pObj->nRefs++ || If_ObjIsCi(pObj) || If_ObjIsConst1(pObj) )
408 return 0.0;
409 // store the node in the structure by level
410 assert( If_ObjIsAnd(pObj) );
411 // visit the transitive fanin of the selected cut
412 pCutBest = If_ObjCutBest(pObj);
413 p->nNets += pCutBest->nLeaves;
414 aArea = If_CutLutArea( p, pCutBest );
415 If_CutForEachLeaf( p, pCutBest, pLeaf, i )
416 {
417 p->dPower += pSwitching? pSwitching[pLeaf->Id] : 0.0;
418 aArea += If_ManMarkMapping_rec( p, pLeaf );
419 }
420 return aArea;
421 }
422
423 /**Function*************************************************************
424
425 Synopsis [Computes area, references, and nodes used in the mapping.]
426
427 Description []
428
429 SideEffects []
430
431 SeeAlso []
432
433 ***********************************************************************/
If_ManMarkMapping(If_Man_t * p)434 void If_ManMarkMapping( If_Man_t * p )
435 {
436 If_Obj_t * pObj;
437 int i;
438 If_ManForEachObj( p, pObj, i )
439 {
440 pObj->Required = IF_FLOAT_LARGE;
441 pObj->nVisits = pObj->nVisitsCopy;
442 pObj->nRefs = 0;
443 }
444 p->nNets = 0;
445 p->dPower = 0.0;
446 p->AreaGlo = 0.0;
447 If_ManForEachCo( p, pObj, i )
448 p->AreaGlo += If_ManMarkMapping_rec( p, If_ObjFanin0(pObj) );
449 }
450
451 /**Function*************************************************************
452
453 Synopsis [Collects nodes used in the mapping in the topological order.]
454
455 Description []
456
457 SideEffects []
458
459 SeeAlso []
460
461 ***********************************************************************/
If_ManCollectMappingDirect(If_Man_t * p)462 Vec_Ptr_t * If_ManCollectMappingDirect( If_Man_t * p )
463 {
464 Vec_Ptr_t * vOrder;
465 If_Obj_t * pObj;
466 int i;
467 If_ManMarkMapping( p );
468 vOrder = Vec_PtrAlloc( If_ManObjNum(p) );
469 If_ManForEachObj( p, pObj, i )
470 if ( If_ObjIsAnd(pObj) && pObj->nRefs )
471 Vec_PtrPush( vOrder, pObj );
472 return vOrder;
473 }
474
475 /**Function*************************************************************
476
477 Synopsis [Collects nodes used in the mapping in the topological order.]
478
479 Description [Represents mapping as an array of integers.]
480
481 SideEffects []
482
483 SeeAlso []
484
485 ***********************************************************************/
If_ManCollectMappingInt(If_Man_t * p)486 Vec_Int_t * If_ManCollectMappingInt( If_Man_t * p )
487 {
488 Vec_Int_t * vOrder;
489 If_Cut_t * pCutBest;
490 If_Obj_t * pObj;
491 int i, k, nLeaves, * ppLeaves;
492 If_ManMarkMapping( p );
493 vOrder = Vec_IntAlloc( If_ManObjNum(p) );
494 If_ManForEachObj( p, pObj, i )
495 if ( If_ObjIsAnd(pObj) && pObj->nRefs )
496 {
497 pCutBest = If_ObjCutBest( pObj );
498 nLeaves = If_CutLeaveNum( pCutBest );
499 ppLeaves = If_CutLeaves( pCutBest );
500 // save the number of leaves, the leaves, and finally, the root
501 Vec_IntPush( vOrder, nLeaves );
502 for ( k = 0; k < nLeaves; k++ )
503 Vec_IntPush( vOrder, ppLeaves[k] );
504 Vec_IntPush( vOrder, pObj->Id );
505 }
506 return vOrder;
507 }
508
509 /**Function*************************************************************
510
511 Synopsis [Returns the number of POs pointing to the same internal nodes.]
512
513 Description []
514
515 SideEffects []
516
517 SeeAlso []
518
519 ***********************************************************************/
If_ManCountSpecialPos(If_Man_t * p)520 int If_ManCountSpecialPos( If_Man_t * p )
521 {
522 If_Obj_t * pObj;
523 int i, Counter = 0;
524 // clean all marks
525 If_ManForEachPo( p, pObj, i )
526 If_ObjFanin0(pObj)->fMark = 0;
527 // label nodes
528 If_ManForEachPo( p, pObj, i )
529 if ( !If_ObjFaninC0(pObj) )
530 If_ObjFanin0(pObj)->fMark = 1;
531 // label nodes
532 If_ManForEachPo( p, pObj, i )
533 if ( If_ObjFaninC0(pObj) )
534 Counter += If_ObjFanin0(pObj)->fMark;
535 // clean all marks
536 If_ManForEachPo( p, pObj, i )
537 If_ObjFanin0(pObj)->fMark = 0;
538 return Counter;
539 }
540
541
542 /**Function*************************************************************
543
544 Synopsis [Traverse the cut and counts its volume.]
545
546 Description []
547
548 SideEffects []
549
550 SeeAlso []
551
552 ***********************************************************************/
If_CutTraverse_rec(If_Obj_t * pNode,Vec_Ptr_t * vNodes)553 static void If_CutTraverse_rec( If_Obj_t * pNode, Vec_Ptr_t * vNodes )
554 {
555 if ( pNode->fMark )
556 return;
557 pNode->fMark = 1;
558 // assert( !If_ObjIsCi(pNode) ); // does not hold with cut minimization
559 if ( If_ObjIsAnd(pNode) )
560 If_CutTraverse_rec( If_ObjFanin0(pNode), vNodes );
561 if ( If_ObjIsAnd(pNode) )
562 If_CutTraverse_rec( If_ObjFanin1(pNode), vNodes );
563 Vec_PtrPush( vNodes, pNode );
564 }
If_CutTraverse(If_Man_t * p,If_Obj_t * pRoot,If_Cut_t * pCut,Vec_Ptr_t * vNodes)565 void If_CutTraverse( If_Man_t * p, If_Obj_t * pRoot, If_Cut_t * pCut, Vec_Ptr_t * vNodes )
566 {
567 If_Obj_t * pLeaf;
568 int i;
569 // collect the internal nodes of the cut
570 Vec_PtrClear( vNodes );
571 If_CutForEachLeaf( p, pCut, pLeaf, i )
572 {
573 Vec_PtrPush( vNodes, pLeaf );
574 assert( pLeaf->fMark == 0 );
575 pLeaf->fMark = 1;
576 }
577 // collect other nodes
578 If_CutTraverse_rec( pRoot, vNodes );
579 // clean the mark
580 Vec_PtrForEachEntry( If_Obj_t *, vNodes, pLeaf, i )
581 pLeaf->fMark = 0;
582 }
If_CutTraverseTest(If_Man_t * p,If_Obj_t * pRoot,If_Cut_t * pCut)583 void If_CutTraverseTest( If_Man_t * p, If_Obj_t * pRoot, If_Cut_t * pCut )
584 {
585 Vec_Ptr_t * vNodes;
586 vNodes = Vec_PtrAlloc( 1000 );
587 If_CutTraverse( p, pRoot, pCut, vNodes );
588 //if ( Vec_PtrSize(vNodes) > 30 )
589 //printf( "%d ", Vec_PtrSize(vNodes) );
590 Vec_PtrFree( vNodes );
591 }
592
593 /**Function*************************************************************
594
595 Synopsis []
596
597 Description []
598
599 SideEffects []
600
601 SeeAlso []
602
603 ***********************************************************************/
If_ObjPrint(If_Obj_t * pObj)604 void If_ObjPrint( If_Obj_t * pObj )
605 {
606 if ( pObj == NULL )
607 {
608 printf( "Object is NULL." );
609 return;
610 }
611 printf( "Obj %4d : ", If_ObjId(pObj) );
612 if ( If_ObjIsConst1(pObj) )
613 printf( "constant 1" );
614 else if ( If_ObjIsCi(pObj) )
615 printf( "PI" );
616 else if ( If_ObjIsCo(pObj) )
617 printf( "PO( %4d%s )", If_ObjId(If_ObjFanin0(pObj)), (If_ObjFaninC0(pObj)? "\'" : " ") );
618 else
619 printf( "AND( %4d%s, %4d%s )",
620 If_ObjId(If_ObjFanin0(pObj)), (If_ObjFaninC0(pObj)? "\'" : " "),
621 If_ObjId(If_ObjFanin1(pObj)), (If_ObjFaninC1(pObj)? "\'" : " ") );
622 printf( " (refs = %3d)", pObj->nVisitsCopy );
623 printf( "\n" );
624 }
625
626 ////////////////////////////////////////////////////////////////////////
627 /// END OF FILE ///
628 ////////////////////////////////////////////////////////////////////////
629
630
631 ABC_NAMESPACE_IMPL_END
632
633