1 /**CFile****************************************************************
2
3 FileName [ivyFastMap.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [And-Inverter Graph package.]
8
9 Synopsis [Fast FPGA mapping.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - May 11, 2006.]
16
17 Revision [$Id: ivyFastMap.c,v 1.00 2006/05/11 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "ivy.h"
22
23 ABC_NAMESPACE_IMPL_START
24
25
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29
30 #define IVY_INFINITY 10000
31
32 typedef struct Ivy_SuppMan_t_ Ivy_SuppMan_t;
33 struct Ivy_SuppMan_t_
34 {
35 int nLimit; // the limit on the number of inputs
36 int nObjs; // the number of entries
37 int nSize; // size of each entry in bytes
38 char * pMem; // memory allocated
39 Vec_Vec_t * vLuts; // the array of nodes used in the mapping
40 };
41
42 typedef struct Ivy_Supp_t_ Ivy_Supp_t;
43 struct Ivy_Supp_t_
44 {
45 char nSize; // the number of support nodes
46 char fMark; // multipurpose mask
47 char fMark2; // multipurpose mask
48 char fMark3; // multipurpose mask
49 int nRefs; // the number of references
50 short Delay; // the delay of the node
51 short DelayR; // the reverse delay of the node
52 int pArray[0]; // the support nodes
53 };
54
Ivy_ObjSupp(Ivy_Man_t * pAig,Ivy_Obj_t * pObj)55 static inline Ivy_Supp_t * Ivy_ObjSupp( Ivy_Man_t * pAig, Ivy_Obj_t * pObj )
56 {
57 return (Ivy_Supp_t *)(((Ivy_SuppMan_t*)pAig->pData)->pMem + pObj->Id * ((Ivy_SuppMan_t*)pAig->pData)->nSize);
58 }
Ivy_ObjSuppStart(Ivy_Man_t * pAig,Ivy_Obj_t * pObj)59 static inline Ivy_Supp_t * Ivy_ObjSuppStart( Ivy_Man_t * pAig, Ivy_Obj_t * pObj )
60 {
61 Ivy_Supp_t * pSupp;
62 pSupp = Ivy_ObjSupp( pAig, pObj );
63 pSupp->fMark = 0;
64 pSupp->Delay = 0;
65 pSupp->nSize = 1;
66 pSupp->pArray[0] = pObj->Id;
67 return pSupp;
68 }
69
70 static void Ivy_FastMapPrint( Ivy_Man_t * pAig, int Delay, int Area, abctime Time, char * pStr );
71 static int Ivy_FastMapDelay( Ivy_Man_t * pAig );
72 static int Ivy_FastMapArea( Ivy_Man_t * pAig );
73 static void Ivy_FastMapNode( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit );
74 static void Ivy_FastMapNodeArea( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit );
75 static int Ivy_FastMapMerge( Ivy_Supp_t * pSupp0, Ivy_Supp_t * pSupp1, Ivy_Supp_t * pSupp, int nLimit );
76 static void Ivy_FastMapRequired( Ivy_Man_t * pAig, int Delay, int fSetInter );
77 static void Ivy_FastMapRecover( Ivy_Man_t * pAig, int nLimit );
78 static int Ivy_FastMapNodeDelay( Ivy_Man_t * pAig, Ivy_Obj_t * pObj );
79 static int Ivy_FastMapNodeAreaRefed( Ivy_Man_t * pAig, Ivy_Obj_t * pObj );
80 static int Ivy_FastMapNodeAreaDerefed( Ivy_Man_t * pAig, Ivy_Obj_t * pObj );
81 static void Ivy_FastMapNodeRecover( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vFrontOld );
82 static int Ivy_FastMapNodeRef( Ivy_Man_t * pAig, Ivy_Obj_t * pObj );
83 static int Ivy_FastMapNodeDeref( Ivy_Man_t * pAig, Ivy_Obj_t * pObj );
84
85
86 extern abctime s_MappingTime;
87 extern int s_MappingMem;
88
89
90 ////////////////////////////////////////////////////////////////////////
91 /// FUNCTION DEFINITIONS ///
92 ////////////////////////////////////////////////////////////////////////
93
94 /**Function*************************************************************
95
96 Synopsis [Performs fast K-LUT mapping of the AIG.]
97
98 Description []
99
100 SideEffects []
101
102 SeeAlso []
103
104 ***********************************************************************/
Ivy_FastMapPerform(Ivy_Man_t * pAig,int nLimit,int fRecovery,int fVerbose)105 void Ivy_FastMapPerform( Ivy_Man_t * pAig, int nLimit, int fRecovery, int fVerbose )
106 {
107 Ivy_SuppMan_t * pMan;
108 Ivy_Obj_t * pObj;
109 int i, Delay, Area;
110 abctime clk, clkTotal = Abc_Clock();
111 // start the memory for supports
112 pMan = ABC_ALLOC( Ivy_SuppMan_t, 1 );
113 memset( pMan, 0, sizeof(Ivy_SuppMan_t) );
114 pMan->nLimit = nLimit;
115 pMan->nObjs = Ivy_ManObjIdMax(pAig) + 1;
116 pMan->nSize = sizeof(Ivy_Supp_t) + nLimit * sizeof(int);
117 pMan->pMem = (char *)ABC_ALLOC( char, pMan->nObjs * pMan->nSize );
118 memset( pMan->pMem, 0, pMan->nObjs * pMan->nSize );
119 pMan->vLuts = Vec_VecAlloc( 100 );
120 pAig->pData = pMan;
121 clk = Abc_Clock();
122 // set the PI mapping
123 Ivy_ObjSuppStart( pAig, Ivy_ManConst1(pAig) );
124 Ivy_ManForEachPi( pAig, pObj, i )
125 Ivy_ObjSuppStart( pAig, pObj );
126 // iterate through all nodes in the topological order
127 Ivy_ManForEachNode( pAig, pObj, i )
128 Ivy_FastMapNode( pAig, pObj, nLimit );
129 // find the best arrival time and area
130 Delay = Ivy_FastMapDelay( pAig );
131 Area = Ivy_FastMapArea(pAig);
132 if ( fVerbose )
133 Ivy_FastMapPrint( pAig, Delay, Area, Abc_Clock() - clk, "Delay oriented mapping: " );
134
135 // 2-1-2 (doing 2-1-2-1-2 improves 0.5%)
136
137 if ( fRecovery )
138 {
139 clk = Abc_Clock();
140 Ivy_FastMapRequired( pAig, Delay, 0 );
141 // remap the nodes
142 Ivy_FastMapRecover( pAig, nLimit );
143 Delay = Ivy_FastMapDelay( pAig );
144 Area = Ivy_FastMapArea(pAig);
145 if ( fVerbose )
146 Ivy_FastMapPrint( pAig, Delay, Area, Abc_Clock() - clk, "Area recovery 2 : " );
147
148 clk = Abc_Clock();
149 Ivy_FastMapRequired( pAig, Delay, 0 );
150 // iterate through all nodes in the topological order
151 Ivy_ManForEachNode( pAig, pObj, i )
152 Ivy_FastMapNodeArea( pAig, pObj, nLimit );
153 Delay = Ivy_FastMapDelay( pAig );
154 Area = Ivy_FastMapArea(pAig);
155 if ( fVerbose )
156 Ivy_FastMapPrint( pAig, Delay, Area, Abc_Clock() - clk, "Area recovery 1 : " );
157
158 clk = Abc_Clock();
159 Ivy_FastMapRequired( pAig, Delay, 0 );
160 // remap the nodes
161 Ivy_FastMapRecover( pAig, nLimit );
162 Delay = Ivy_FastMapDelay( pAig );
163 Area = Ivy_FastMapArea(pAig);
164 if ( fVerbose )
165 Ivy_FastMapPrint( pAig, Delay, Area, Abc_Clock() - clk, "Area recovery 2 : " );
166 }
167
168
169 s_MappingTime = Abc_Clock() - clkTotal;
170 s_MappingMem = pMan->nObjs * pMan->nSize;
171 /*
172 {
173 Vec_Ptr_t * vNodes;
174 vNodes = Vec_PtrAlloc( 100 );
175 Vec_VecForEachEntry( Ivy_Obj_t *, pMan->vLuts, pObj, i, k )
176 Vec_PtrPush( vNodes, pObj );
177 Ivy_ManShow( pAig, 0, vNodes );
178 Vec_PtrFree( vNodes );
179 }
180 */
181 }
182
183 /**Function*************************************************************
184
185 Synopsis [Cleans memory used for decomposition.]
186
187 Description []
188
189 SideEffects []
190
191 SeeAlso []
192
193 ***********************************************************************/
Ivy_FastMapStop(Ivy_Man_t * pAig)194 void Ivy_FastMapStop( Ivy_Man_t * pAig )
195 {
196 Ivy_SuppMan_t * p = (Ivy_SuppMan_t *)pAig->pData;
197 Vec_VecFree( p->vLuts );
198 ABC_FREE( p->pMem );
199 ABC_FREE( p );
200 pAig->pData = NULL;
201 }
202
203 /**Function*************************************************************
204
205 Synopsis [Prints statistics.]
206
207 Description []
208
209 SideEffects []
210
211 SeeAlso []
212
213 ***********************************************************************/
Ivy_FastMapPrint(Ivy_Man_t * pAig,int Delay,int Area,abctime Time,char * pStr)214 void Ivy_FastMapPrint( Ivy_Man_t * pAig, int Delay, int Area, abctime Time, char * pStr )
215 {
216 printf( "%s : Delay = %3d. Area = %6d. ", pStr, Delay, Area );
217 ABC_PRT( "Time", Time );
218 }
219
220 /**Function*************************************************************
221
222 Synopsis [Computes delay after LUT mapping.]
223
224 Description []
225
226 SideEffects []
227
228 SeeAlso []
229
230 ***********************************************************************/
Ivy_FastMapDelay(Ivy_Man_t * pAig)231 int Ivy_FastMapDelay( Ivy_Man_t * pAig )
232 {
233 Ivy_Supp_t * pSupp;
234 Ivy_Obj_t * pObj;
235 int i, DelayMax = 0;
236 Ivy_ManForEachPo( pAig, pObj, i )
237 {
238 pObj = Ivy_ObjFanin0(pObj);
239 if ( !Ivy_ObjIsNode(pObj) )
240 continue;
241 pSupp = Ivy_ObjSupp( pAig, pObj );
242 if ( DelayMax < pSupp->Delay )
243 DelayMax = pSupp->Delay;
244 }
245 return DelayMax;
246 }
247
248 /**Function*************************************************************
249
250 Synopsis [Computes area after mapping.]
251
252 Description []
253
254 SideEffects []
255
256 SeeAlso []
257
258 ***********************************************************************/
Ivy_FastMapArea_rec(Ivy_Man_t * pAig,Ivy_Obj_t * pObj,Vec_Vec_t * vLuts)259 int Ivy_FastMapArea_rec( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, Vec_Vec_t * vLuts )
260 {
261 Ivy_Supp_t * pSupp;
262 int i, Counter;
263 pSupp = Ivy_ObjSupp( pAig, pObj );
264 // skip visited nodes and PIs
265 if ( pSupp->fMark || pSupp->nSize == 1 )
266 return 0;
267 pSupp->fMark = 1;
268 // compute the area of this node
269 Counter = 0;
270 for ( i = 0; i < pSupp->nSize; i++ )
271 Counter += Ivy_FastMapArea_rec( pAig, Ivy_ManObj(pAig, pSupp->pArray[i]), vLuts );
272 // add the node to the array of LUTs
273 Vec_VecPush( vLuts, pSupp->Delay, pObj );
274 return 1 + Counter;
275 }
276
277 /**Function*************************************************************
278
279 Synopsis [Computes area after mapping.]
280
281 Description []
282
283 SideEffects []
284
285 SeeAlso []
286
287 ***********************************************************************/
Ivy_FastMapArea(Ivy_Man_t * pAig)288 int Ivy_FastMapArea( Ivy_Man_t * pAig )
289 {
290 Vec_Vec_t * vLuts;
291 Ivy_Obj_t * pObj;
292 int i, Counter = 0;
293 // get the array to store the nodes
294 vLuts = ((Ivy_SuppMan_t *)pAig->pData)->vLuts;
295 Vec_VecClear( vLuts );
296 // explore starting from each node
297 Ivy_ManForEachPo( pAig, pObj, i )
298 Counter += Ivy_FastMapArea_rec( pAig, Ivy_ObjFanin0(pObj), vLuts );
299 // clean the marks
300 Ivy_ManForEachNode( pAig, pObj, i )
301 Ivy_ObjSupp( pAig, pObj )->fMark = 0;
302 return Counter;
303 }
304
305 /**Function*************************************************************
306
307 Synopsis [Performs fast mapping for one node.]
308
309 Description []
310
311 SideEffects []
312
313 SeeAlso []
314
315 ***********************************************************************/
Ivy_ObjIsNodeInt1(Ivy_Obj_t * pObj)316 static inline int Ivy_ObjIsNodeInt1( Ivy_Obj_t * pObj )
317 {
318 return Ivy_ObjIsNode(pObj) && Ivy_ObjRefs(pObj) == 1;
319 }
320
321 /**Function*************************************************************
322
323 Synopsis [Performs fast mapping for one node.]
324
325 Description []
326
327 SideEffects []
328
329 SeeAlso []
330
331 ***********************************************************************/
Ivy_ObjIsNodeInt2(Ivy_Obj_t * pObj)332 static inline int Ivy_ObjIsNodeInt2( Ivy_Obj_t * pObj )
333 {
334 return Ivy_ObjIsNode(pObj) && Ivy_ObjRefs(pObj) <= 2;
335 }
336
337 /**Function*************************************************************
338
339 Synopsis [Performs fast mapping for one node.]
340
341 Description []
342
343 SideEffects []
344
345 SeeAlso []
346
347 ***********************************************************************/
Vec_IntRemoveDup(int * pArray,int nSize)348 static inline int Vec_IntRemoveDup( int * pArray, int nSize )
349 {
350 int i, k;
351 if ( nSize < 2 )
352 return nSize;
353 for ( i = k = 1; i < nSize; i++ )
354 if ( pArray[i] != pArray[i-1] )
355 pArray[k++] = pArray[i];
356 return k;
357 }
358
359 /**Function*************************************************************
360
361 Synopsis [Performs fast mapping for one node.]
362
363 Description []
364
365 SideEffects []
366
367 SeeAlso []
368
369 ***********************************************************************/
Ivy_FastMapNodeArea2(Ivy_Man_t * pAig,Ivy_Obj_t * pObj,int nLimit)370 void Ivy_FastMapNodeArea2( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit )
371 {
372 static int Store[32], StoreSize;
373 static char Supp0[16], Supp1[16];
374 static Ivy_Supp_t * pTemp0 = (Ivy_Supp_t *)Supp0;
375 static Ivy_Supp_t * pTemp1 = (Ivy_Supp_t *)Supp1;
376 Ivy_Obj_t * pFanin0, * pFanin1;
377 Ivy_Supp_t * pSupp0, * pSupp1, * pSupp;
378 int RetValue, DelayOld;
379 assert( nLimit <= 32 );
380 assert( Ivy_ObjIsNode(pObj) );
381 // get the fanins
382 pFanin0 = Ivy_ObjFanin0(pObj);
383 pFanin1 = Ivy_ObjFanin1(pObj);
384 // get the supports
385 pSupp0 = Ivy_ObjSupp( pAig, pFanin0 );
386 pSupp1 = Ivy_ObjSupp( pAig, pFanin1 );
387 pSupp = Ivy_ObjSupp( pAig, pObj );
388 assert( pSupp->fMark == 0 );
389 // get the old delay of the node
390 DelayOld = Ivy_FastMapNodeDelay(pAig, pObj);
391 assert( DelayOld <= pSupp->DelayR );
392 // copy the current cut
393 memcpy( Store, pSupp->pArray, sizeof(int) * pSupp->nSize );
394 StoreSize = pSupp->nSize;
395 // get the fanin support
396 if ( Ivy_ObjRefs(pFanin0) > 1 && pSupp0->Delay < pSupp->DelayR )
397 {
398 pSupp0 = pTemp0;
399 pSupp0->nSize = 1;
400 pSupp0->pArray[0] = Ivy_ObjFaninId0(pObj);
401 }
402 // get the fanin support
403 if ( Ivy_ObjRefs(pFanin1) > 1 && pSupp1->Delay < pSupp->DelayR )
404 {
405 pSupp1 = pTemp1;
406 pSupp1->nSize = 1;
407 pSupp1->pArray[0] = Ivy_ObjFaninId1(pObj);
408 }
409 // merge the cuts
410 if ( pSupp0->nSize < pSupp1->nSize )
411 RetValue = Ivy_FastMapMerge( pSupp1, pSupp0, pSupp, nLimit );
412 else
413 RetValue = Ivy_FastMapMerge( pSupp0, pSupp1, pSupp, nLimit );
414 if ( !RetValue )
415 {
416 pSupp->nSize = 2;
417 pSupp->pArray[0] = Ivy_ObjFaninId0(pObj);
418 pSupp->pArray[1] = Ivy_ObjFaninId1(pObj);
419 }
420 // check the resulting delay
421 pSupp->Delay = Ivy_FastMapNodeDelay(pAig, pObj);
422 if ( pSupp->Delay > pSupp->DelayR )
423 {
424 pSupp->nSize = StoreSize;
425 memcpy( pSupp->pArray, Store, sizeof(int) * pSupp->nSize );
426 pSupp->Delay = DelayOld;
427 }
428 }
429
430 /**Function*************************************************************
431
432 Synopsis [Performs fast mapping for one node.]
433
434 Description []
435
436 SideEffects []
437
438 SeeAlso []
439
440 ***********************************************************************/
Ivy_FastMapNodeArea(Ivy_Man_t * pAig,Ivy_Obj_t * pObj,int nLimit)441 void Ivy_FastMapNodeArea( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit )
442 {
443 static int Store[32], StoreSize;
444 static char Supp0[16], Supp1[16];
445 static Ivy_Supp_t * pTemp0 = (Ivy_Supp_t *)Supp0;
446 static Ivy_Supp_t * pTemp1 = (Ivy_Supp_t *)Supp1;
447 Ivy_Obj_t * pFanin0, * pFanin1;
448 Ivy_Supp_t * pSupp0, * pSupp1, * pSupp;
449 int RetValue, DelayOld, RefsOld;
450 int AreaBef, AreaAft;
451 assert( nLimit <= 32 );
452 assert( Ivy_ObjIsNode(pObj) );
453 // get the fanins
454 pFanin0 = Ivy_ObjFanin0(pObj);
455 pFanin1 = Ivy_ObjFanin1(pObj);
456 // get the supports
457 pSupp0 = Ivy_ObjSupp( pAig, pFanin0 );
458 pSupp1 = Ivy_ObjSupp( pAig, pFanin1 );
459 pSupp = Ivy_ObjSupp( pAig, pObj );
460 assert( pSupp->fMark == 0 );
461
462 // get the area
463 if ( pSupp->nRefs == 0 )
464 AreaBef = Ivy_FastMapNodeAreaDerefed( pAig, pObj );
465 else
466 AreaBef = Ivy_FastMapNodeAreaRefed( pAig, pObj );
467 // if ( AreaBef == 1 )
468 // return;
469
470 // deref the cut if the node is refed
471 if ( pSupp->nRefs != 0 )
472 Ivy_FastMapNodeDeref( pAig, pObj );
473
474 // get the old delay of the node
475 DelayOld = Ivy_FastMapNodeDelay(pAig, pObj);
476 assert( DelayOld <= pSupp->DelayR );
477 // copy the current cut
478 memcpy( Store, pSupp->pArray, sizeof(int) * pSupp->nSize );
479 StoreSize = pSupp->nSize;
480 // get the fanin support
481 if ( Ivy_ObjRefs(pFanin0) > 2 && pSupp0->Delay < pSupp->DelayR )
482 // if ( pSupp0->nRefs > 0 && pSupp0->Delay < pSupp->DelayR ) // this leads to 2% worse results
483 {
484 pSupp0 = pTemp0;
485 pSupp0->nSize = 1;
486 pSupp0->pArray[0] = Ivy_ObjFaninId0(pObj);
487 }
488 // get the fanin support
489 if ( Ivy_ObjRefs(pFanin1) > 2 && pSupp1->Delay < pSupp->DelayR )
490 // if ( pSupp1->nRefs > 0 && pSupp1->Delay < pSupp->DelayR )
491 {
492 pSupp1 = pTemp1;
493 pSupp1->nSize = 1;
494 pSupp1->pArray[0] = Ivy_ObjFaninId1(pObj);
495 }
496 // merge the cuts
497 if ( pSupp0->nSize < pSupp1->nSize )
498 RetValue = Ivy_FastMapMerge( pSupp1, pSupp0, pSupp, nLimit );
499 else
500 RetValue = Ivy_FastMapMerge( pSupp0, pSupp1, pSupp, nLimit );
501 if ( !RetValue )
502 {
503 pSupp->nSize = 2;
504 pSupp->pArray[0] = Ivy_ObjFaninId0(pObj);
505 pSupp->pArray[1] = Ivy_ObjFaninId1(pObj);
506 }
507
508 // check the resulting delay
509 pSupp->Delay = Ivy_FastMapNodeDelay(pAig, pObj);
510
511 RefsOld = pSupp->nRefs; pSupp->nRefs = 0;
512 AreaAft = Ivy_FastMapNodeAreaDerefed( pAig, pObj );
513 pSupp->nRefs = RefsOld;
514
515 if ( AreaAft > AreaBef || pSupp->Delay > pSupp->DelayR )
516 // if ( pSupp->Delay > pSupp->DelayR )
517 {
518 pSupp->nSize = StoreSize;
519 memcpy( pSupp->pArray, Store, sizeof(int) * pSupp->nSize );
520 pSupp->Delay = DelayOld;
521 // printf( "-" );
522 }
523 // else
524 // printf( "+" );
525
526 if ( pSupp->nRefs != 0 )
527 Ivy_FastMapNodeRef( pAig, pObj );
528 }
529
530 /**Function*************************************************************
531
532 Synopsis [Performs fast mapping for one node.]
533
534 Description []
535
536 SideEffects []
537
538 SeeAlso []
539
540 ***********************************************************************/
Ivy_FastMapNode(Ivy_Man_t * pAig,Ivy_Obj_t * pObj,int nLimit)541 void Ivy_FastMapNode( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit )
542 {
543 Ivy_Supp_t * pSupp0, * pSupp1, * pSupp;
544 int fFaninParam = 2;
545 int RetValue;
546 assert( Ivy_ObjIsNode(pObj) );
547 // get the supports
548 pSupp0 = Ivy_ObjSupp( pAig, Ivy_ObjFanin0(pObj) );
549 pSupp1 = Ivy_ObjSupp( pAig, Ivy_ObjFanin1(pObj) );
550 pSupp = Ivy_ObjSupp( pAig, pObj );
551 pSupp->fMark = 0;
552 // get the delays
553 if ( pSupp0->Delay == pSupp1->Delay )
554 pSupp->Delay = (pSupp0->Delay == 0) ? pSupp0->Delay + 1: pSupp0->Delay;
555 else if ( pSupp0->Delay > pSupp1->Delay )
556 {
557 pSupp->Delay = pSupp0->Delay;
558 pSupp1 = Ivy_ObjSupp( pAig, Ivy_ManConst1(pAig) );
559 pSupp1->pArray[0] = Ivy_ObjFaninId1(pObj);
560 }
561 else // if ( pSupp0->Delay < pSupp1->Delay )
562 {
563 pSupp->Delay = pSupp1->Delay;
564 pSupp0 = Ivy_ObjSupp( pAig, Ivy_ManConst1(pAig) );
565 pSupp0->pArray[0] = Ivy_ObjFaninId0(pObj);
566 }
567 // merge the cuts
568 if ( pSupp0->nSize < pSupp1->nSize )
569 RetValue = Ivy_FastMapMerge( pSupp1, pSupp0, pSupp, nLimit );
570 else
571 RetValue = Ivy_FastMapMerge( pSupp0, pSupp1, pSupp, nLimit );
572 if ( !RetValue )
573 {
574 pSupp->Delay++;
575 if ( fFaninParam == 2 )
576 {
577 pSupp->nSize = 2;
578 pSupp->pArray[0] = Ivy_ObjFaninId0(pObj);
579 pSupp->pArray[1] = Ivy_ObjFaninId1(pObj);
580 }
581 else if ( fFaninParam == 3 )
582 {
583 Ivy_Obj_t * pFanin0, * pFanin1, * pFaninA, * pFaninB;
584 pFanin0 = Ivy_ObjFanin0(pObj);
585 pFanin1 = Ivy_ObjFanin1(pObj);
586 pSupp->nSize = 0;
587 // process the first fanin
588 if ( Ivy_ObjIsNodeInt1(pFanin0) )
589 {
590 pFaninA = Ivy_ObjFanin0(pFanin0);
591 pFaninB = Ivy_ObjFanin1(pFanin0);
592 if ( Ivy_ObjIsNodeInt1(pFaninA) && Ivy_ObjIsNodeInt1(pFaninB) )
593 pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFanin0);
594 else
595 {
596 pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFaninA);
597 pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFaninB);
598 }
599 }
600 else
601 pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFanin0);
602 // process the second fanin
603 if ( Ivy_ObjIsNodeInt1(pFanin1) )
604 {
605 pFaninA = Ivy_ObjFanin0(pFanin1);
606 pFaninB = Ivy_ObjFanin1(pFanin1);
607 if ( Ivy_ObjIsNodeInt1(pFaninA) && Ivy_ObjIsNodeInt1(pFaninB) )
608 pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFanin1);
609 else
610 {
611 pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFaninA);
612 pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFaninB);
613 }
614 }
615 else
616 pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFanin1);
617 // sort the fanins
618 Vec_IntSelectSort( pSupp->pArray, pSupp->nSize );
619 pSupp->nSize = Vec_IntRemoveDup( pSupp->pArray, pSupp->nSize );
620 assert( pSupp->pArray[0] < pSupp->pArray[1] );
621 }
622 else if ( fFaninParam == 4 )
623 {
624 Ivy_Obj_t * pFanin0, * pFanin1, * pFaninA, * pFaninB;
625 pFanin0 = Ivy_ObjFanin0(pObj);
626 pFanin1 = Ivy_ObjFanin1(pObj);
627 pSupp->nSize = 0;
628 // consider the case when exactly one of them is internal
629 if ( Ivy_ObjIsNodeInt1(pFanin0) ^ Ivy_ObjIsNodeInt1(pFanin1) )
630 {
631 pSupp0 = Ivy_ObjSupp( pAig, Ivy_ObjFanin0(pObj) );
632 pSupp1 = Ivy_ObjSupp( pAig, Ivy_ObjFanin1(pObj) );
633 if ( Ivy_ObjIsNodeInt1(pFanin0) && pSupp0->nSize < nLimit )
634 {
635 pSupp->Delay = IVY_MAX( pSupp0->Delay, pSupp1->Delay + 1 );
636 pSupp1 = Ivy_ObjSupp( pAig, Ivy_ManConst1(pAig) );
637 pSupp1->pArray[0] = Ivy_ObjId(pFanin1);
638 // merge the cuts
639 RetValue = Ivy_FastMapMerge( pSupp0, pSupp1, pSupp, nLimit );
640 assert( RetValue );
641 assert( pSupp->nSize > 1 );
642 return;
643 }
644 if ( Ivy_ObjIsNodeInt1(pFanin1) && pSupp1->nSize < nLimit )
645 {
646 pSupp->Delay = IVY_MAX( pSupp1->Delay, pSupp0->Delay + 1 );
647 pSupp0 = Ivy_ObjSupp( pAig, Ivy_ManConst1(pAig) );
648 pSupp0->pArray[0] = Ivy_ObjId(pFanin0);
649 // merge the cuts
650 RetValue = Ivy_FastMapMerge( pSupp1, pSupp0, pSupp, nLimit );
651 assert( RetValue );
652 assert( pSupp->nSize > 1 );
653 return;
654 }
655 }
656 // process the first fanin
657 if ( Ivy_ObjIsNodeInt1(pFanin0) )
658 {
659 pFaninA = Ivy_ObjFanin0(pFanin0);
660 pFaninB = Ivy_ObjFanin1(pFanin0);
661 if ( Ivy_ObjIsNodeInt1(pFaninA) && Ivy_ObjIsNodeInt1(pFaninB) )
662 pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFanin0);
663 else
664 {
665 pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFaninA);
666 pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFaninB);
667 }
668 }
669 else
670 pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFanin0);
671 // process the second fanin
672 if ( Ivy_ObjIsNodeInt1(pFanin1) )
673 {
674 pFaninA = Ivy_ObjFanin0(pFanin1);
675 pFaninB = Ivy_ObjFanin1(pFanin1);
676 if ( Ivy_ObjIsNodeInt1(pFaninA) && Ivy_ObjIsNodeInt1(pFaninB) )
677 pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFanin1);
678 else
679 {
680 pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFaninA);
681 pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFaninB);
682 }
683 }
684 else
685 pSupp->pArray[(int)(pSupp->nSize++)] = Ivy_ObjId(pFanin1);
686 // sort the fanins
687 Vec_IntSelectSort( pSupp->pArray, pSupp->nSize );
688 pSupp->nSize = Vec_IntRemoveDup( pSupp->pArray, pSupp->nSize );
689 assert( pSupp->pArray[0] < pSupp->pArray[1] );
690 assert( pSupp->nSize > 1 );
691 }
692 }
693 assert( pSupp->Delay > 0 );
694 }
695
696 /**Function*************************************************************
697
698 Synopsis [Merges two supports]
699
700 Description []
701
702 SideEffects []
703
704 SeeAlso []
705
706 ***********************************************************************/
Ivy_FastMapMerge(Ivy_Supp_t * pSupp0,Ivy_Supp_t * pSupp1,Ivy_Supp_t * pSupp,int nLimit)707 int Ivy_FastMapMerge( Ivy_Supp_t * pSupp0, Ivy_Supp_t * pSupp1, Ivy_Supp_t * pSupp, int nLimit )
708 {
709 int i, k, c;
710 assert( pSupp0->nSize >= pSupp1->nSize );
711 // the case of the largest cut sizes
712 if ( pSupp0->nSize == nLimit && pSupp1->nSize == nLimit )
713 {
714 for ( i = 0; i < pSupp0->nSize; i++ )
715 if ( pSupp0->pArray[i] != pSupp1->pArray[i] )
716 return 0;
717 for ( i = 0; i < pSupp0->nSize; i++ )
718 pSupp->pArray[i] = pSupp0->pArray[i];
719 pSupp->nSize = pSupp0->nSize;
720 return 1;
721 }
722 // the case when one of the cuts is the largest
723 if ( pSupp0->nSize == nLimit )
724 {
725 for ( i = 0; i < pSupp1->nSize; i++ )
726 {
727 for ( k = pSupp0->nSize - 1; k >= 0; k-- )
728 if ( pSupp0->pArray[k] == pSupp1->pArray[i] )
729 break;
730 if ( k == -1 ) // did not find
731 return 0;
732 }
733 for ( i = 0; i < pSupp0->nSize; i++ )
734 pSupp->pArray[i] = pSupp0->pArray[i];
735 pSupp->nSize = pSupp0->nSize;
736 return 1;
737 }
738
739 // compare two cuts with different numbers
740 i = k = 0;
741 for ( c = 0; c < nLimit; c++ )
742 {
743 if ( k == pSupp1->nSize )
744 {
745 if ( i == pSupp0->nSize )
746 {
747 pSupp->nSize = c;
748 return 1;
749 }
750 pSupp->pArray[c] = pSupp0->pArray[i++];
751 continue;
752 }
753 if ( i == pSupp0->nSize )
754 {
755 if ( k == pSupp1->nSize )
756 {
757 pSupp->nSize = c;
758 return 1;
759 }
760 pSupp->pArray[c] = pSupp1->pArray[k++];
761 continue;
762 }
763 if ( pSupp0->pArray[i] < pSupp1->pArray[k] )
764 {
765 pSupp->pArray[c] = pSupp0->pArray[i++];
766 continue;
767 }
768 if ( pSupp0->pArray[i] > pSupp1->pArray[k] )
769 {
770 pSupp->pArray[c] = pSupp1->pArray[k++];
771 continue;
772 }
773 pSupp->pArray[c] = pSupp0->pArray[i++];
774 k++;
775 }
776 if ( i < pSupp0->nSize || k < pSupp1->nSize )
777 return 0;
778 pSupp->nSize = c;
779 return 1;
780 }
781
782 /**Function*************************************************************
783
784 Synopsis [Creates integer vector with the support of the node.]
785
786 Description []
787
788 SideEffects []
789
790 SeeAlso []
791
792 ***********************************************************************/
Ivy_FastMapReadSupp(Ivy_Man_t * pAig,Ivy_Obj_t * pObj,Vec_Int_t * vLeaves)793 void Ivy_FastMapReadSupp( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, Vec_Int_t * vLeaves )
794 {
795 Ivy_Supp_t * pSupp;
796 pSupp = Ivy_ObjSupp( pAig, pObj );
797 vLeaves->nCap = 8;
798 vLeaves->nSize = pSupp->nSize;
799 vLeaves->pArray = pSupp->pArray;
800 }
801
802 /**Function*************************************************************
803
804 Synopsis [Sets the required times of the intermediate nodes.]
805
806 Description []
807
808 SideEffects []
809
810 SeeAlso []
811
812 ***********************************************************************/
Ivy_FastMapRequired_rec(Ivy_Man_t * pAig,Ivy_Obj_t * pObj,Ivy_Obj_t * pRoot,int DelayR)813 void Ivy_FastMapRequired_rec( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, Ivy_Obj_t * pRoot, int DelayR )
814 {
815 Ivy_Supp_t * pSupp;
816 pSupp = Ivy_ObjSupp( pAig, pObj );
817 if ( pObj != pRoot && (pSupp->nRefs > 0 || Ivy_ObjIsCi(pObj)) )
818 return;
819 Ivy_FastMapRequired_rec( pAig, Ivy_ObjFanin0(pObj), pRoot, DelayR );
820 Ivy_FastMapRequired_rec( pAig, Ivy_ObjFanin1(pObj), pRoot, DelayR );
821 // assert( pObj == pRoot || pSupp->DelayR == IVY_INFINITY );
822 pSupp->DelayR = DelayR;
823 }
824
825 /**Function*************************************************************
826
827 Synopsis [Computes the required times for each node.]
828
829 Description [Sets reference counters for each node.]
830
831 SideEffects []
832
833 SeeAlso []
834
835 ***********************************************************************/
Ivy_FastMapRequired(Ivy_Man_t * pAig,int Delay,int fSetInter)836 void Ivy_FastMapRequired( Ivy_Man_t * pAig, int Delay, int fSetInter )
837 {
838 Vec_Vec_t * vLuts;
839 Vec_Ptr_t * vNodes;
840 Ivy_Obj_t * pObj;
841 Ivy_Supp_t * pSupp, * pSuppF;
842 int i, k, c;
843 // clean the required times
844 Ivy_ManForEachPi( pAig, pObj, i )
845 {
846 pSupp = Ivy_ObjSupp( pAig, pObj );
847 pSupp->DelayR = IVY_INFINITY;
848 pSupp->nRefs = 0;
849 }
850 Ivy_ManForEachNode( pAig, pObj, i )
851 {
852 pSupp = Ivy_ObjSupp( pAig, pObj );
853 pSupp->DelayR = IVY_INFINITY;
854 pSupp->nRefs = 0;
855 }
856 // set the required times of the POs
857 Ivy_ManForEachPo( pAig, pObj, i )
858 {
859 pSupp = Ivy_ObjSupp( pAig, Ivy_ObjFanin0(pObj) );
860 pSupp->DelayR = Delay;
861 pSupp->nRefs++;
862 }
863 // get the levelized nodes used in the mapping
864 vLuts = ((Ivy_SuppMan_t *)pAig->pData)->vLuts;
865 // propagate the required times
866 Vec_VecForEachLevelReverse( vLuts, vNodes, i )
867 Vec_PtrForEachEntry( Ivy_Obj_t *, vNodes, pObj, k )
868 {
869 pSupp = Ivy_ObjSupp( pAig, pObj );
870 assert( pSupp->nRefs > 0 );
871 for ( c = 0; c < pSupp->nSize; c++ )
872 {
873 pSuppF = Ivy_ObjSupp( pAig, Ivy_ManObj(pAig, pSupp->pArray[c]) );
874 pSuppF->DelayR = IVY_MIN( pSuppF->DelayR, pSupp->DelayR - 1 );
875 pSuppF->nRefs++;
876 }
877 }
878 /*
879 // print out some of the required times
880 Ivy_ManForEachPi( pAig, pObj, i )
881 {
882 pSupp = Ivy_ObjSupp( pAig, pObj );
883 printf( "%d ", pSupp->DelayR );
884 }
885 printf( "\n" );
886 */
887
888 if ( fSetInter )
889 {
890 // set the required times of the intermediate nodes
891 Vec_VecForEachLevelReverse( vLuts, vNodes, i )
892 Vec_PtrForEachEntry( Ivy_Obj_t *, vNodes, pObj, k )
893 {
894 pSupp = Ivy_ObjSupp( pAig, pObj );
895 Ivy_FastMapRequired_rec( pAig, pObj, pObj, pSupp->DelayR );
896 }
897 // make sure that all required times are assigned
898 Ivy_ManForEachNode( pAig, pObj, i )
899 {
900 pSupp = Ivy_ObjSupp( pAig, pObj );
901 assert( pSupp->DelayR < IVY_INFINITY );
902 }
903 }
904 }
905
906 /**Function*************************************************************
907
908 Synopsis [Performs area recovery for each node.]
909
910 Description []
911
912 SideEffects []
913
914 SeeAlso []
915
916 ***********************************************************************/
Ivy_FastMapRecover(Ivy_Man_t * pAig,int nLimit)917 void Ivy_FastMapRecover( Ivy_Man_t * pAig, int nLimit )
918 {
919 Vec_Ptr_t * vFront, * vFrontOld;
920 Ivy_Obj_t * pObj;
921 int i;
922 vFront = Vec_PtrAlloc( nLimit );
923 vFrontOld = Vec_PtrAlloc( nLimit );
924 Ivy_ManCleanTravId( pAig );
925 // iterate through all nodes in the topological order
926 Ivy_ManForEachNode( pAig, pObj, i )
927 Ivy_FastMapNodeRecover( pAig, pObj, nLimit, vFront, vFrontOld );
928 Vec_PtrFree( vFrontOld );
929 Vec_PtrFree( vFront );
930 }
931
932 /**Function*************************************************************
933
934 Synopsis [Computes the delay of the cut rooted at this node.]
935
936 Description []
937
938 SideEffects []
939
940 SeeAlso []
941
942 ***********************************************************************/
Ivy_FastMapNodeDelay(Ivy_Man_t * pAig,Ivy_Obj_t * pObj)943 int Ivy_FastMapNodeDelay( Ivy_Man_t * pAig, Ivy_Obj_t * pObj )
944 {
945 Ivy_Supp_t * pSupp, * pSuppF;
946 int c, Delay = 0;
947 pSupp = Ivy_ObjSupp( pAig, pObj );
948 for ( c = 0; c < pSupp->nSize; c++ )
949 {
950 pSuppF = Ivy_ObjSupp( pAig, Ivy_ManObj(pAig, pSupp->pArray[c]) );
951 Delay = IVY_MAX( Delay, pSuppF->Delay );
952 }
953 return 1 + Delay;
954 }
955
956
957 /**function*************************************************************
958
959 synopsis [References the cut.]
960
961 description [This procedure is similar to the procedure NodeReclaim.]
962
963 sideeffects []
964
965 seealso []
966
967 ***********************************************************************/
Ivy_FastMapNodeRef(Ivy_Man_t * pAig,Ivy_Obj_t * pObj)968 int Ivy_FastMapNodeRef( Ivy_Man_t * pAig, Ivy_Obj_t * pObj )
969 {
970 Ivy_Supp_t * pSupp, * pSuppF;
971 Ivy_Obj_t * pNodeChild;
972 int aArea, i;
973 // start the area of this cut
974 aArea = 1;
975 // go through the children
976 pSupp = Ivy_ObjSupp( pAig, pObj );
977 assert( pSupp->nSize > 1 );
978 for ( i = 0; i < pSupp->nSize; i++ )
979 {
980 pNodeChild = Ivy_ManObj(pAig, pSupp->pArray[i]);
981 pSuppF = Ivy_ObjSupp( pAig, pNodeChild );
982 assert( pSuppF->nRefs >= 0 );
983 if ( pSuppF->nRefs++ > 0 )
984 continue;
985 if ( pSuppF->nSize == 1 )
986 continue;
987 aArea += Ivy_FastMapNodeRef( pAig, pNodeChild );
988 }
989 return aArea;
990 }
991
992 /**function*************************************************************
993
994 synopsis [Dereferences the cut.]
995
996 description [This procedure is similar to the procedure NodeRecusiveDeref.]
997
998 sideeffects []
999
1000 seealso []
1001
1002 ***********************************************************************/
Ivy_FastMapNodeDeref(Ivy_Man_t * pAig,Ivy_Obj_t * pObj)1003 int Ivy_FastMapNodeDeref( Ivy_Man_t * pAig, Ivy_Obj_t * pObj )
1004 {
1005 Ivy_Supp_t * pSupp, * pSuppF;
1006 Ivy_Obj_t * pNodeChild;
1007 int aArea, i;
1008 // start the area of this cut
1009 aArea = 1;
1010 // go through the children
1011 pSupp = Ivy_ObjSupp( pAig, pObj );
1012 assert( pSupp->nSize > 1 );
1013 for ( i = 0; i < pSupp->nSize; i++ )
1014 {
1015 pNodeChild = Ivy_ManObj(pAig, pSupp->pArray[i]);
1016 pSuppF = Ivy_ObjSupp( pAig, pNodeChild );
1017 assert( pSuppF->nRefs > 0 );
1018 if ( --pSuppF->nRefs > 0 )
1019 continue;
1020 if ( pSuppF->nSize == 1 )
1021 continue;
1022 aArea += Ivy_FastMapNodeDeref( pAig, pNodeChild );
1023 }
1024 return aArea;
1025 }
1026
1027 /**function*************************************************************
1028
1029 synopsis [Computes the exact area associated with the cut.]
1030
1031 description []
1032
1033 sideeffects []
1034
1035 seealso []
1036
1037 ***********************************************************************/
Ivy_FastMapNodeAreaRefed(Ivy_Man_t * pAig,Ivy_Obj_t * pObj)1038 int Ivy_FastMapNodeAreaRefed( Ivy_Man_t * pAig, Ivy_Obj_t * pObj )
1039 {
1040 Ivy_Supp_t * pSupp;
1041 int aResult, aResult2;
1042 if ( Ivy_ObjIsCi(pObj) )
1043 return 0;
1044 assert( Ivy_ObjIsNode(pObj) );
1045 pSupp = Ivy_ObjSupp( pAig, pObj );
1046 assert( pSupp->nRefs > 0 );
1047 aResult = Ivy_FastMapNodeDeref( pAig, pObj );
1048 aResult2 = Ivy_FastMapNodeRef( pAig, pObj );
1049 assert( aResult == aResult2 );
1050 return aResult;
1051 }
1052
1053 /**function*************************************************************
1054
1055 synopsis [Computes the exact area associated with the cut.]
1056
1057 description []
1058
1059 sideeffects []
1060
1061 seealso []
1062
1063 ***********************************************************************/
Ivy_FastMapNodeAreaDerefed(Ivy_Man_t * pAig,Ivy_Obj_t * pObj)1064 int Ivy_FastMapNodeAreaDerefed( Ivy_Man_t * pAig, Ivy_Obj_t * pObj )
1065 {
1066 Ivy_Supp_t * pSupp;
1067 int aResult, aResult2;
1068 if ( Ivy_ObjIsCi(pObj) )
1069 return 0;
1070 assert( Ivy_ObjIsNode(pObj) );
1071 pSupp = Ivy_ObjSupp( pAig, pObj );
1072 assert( pSupp->nRefs == 0 );
1073 aResult2 = Ivy_FastMapNodeRef( pAig, pObj );
1074 aResult = Ivy_FastMapNodeDeref( pAig, pObj );
1075 assert( aResult == aResult2 );
1076 return aResult;
1077 }
1078
1079
1080
1081
1082 /**Function*************************************************************
1083
1084 Synopsis [Counts the number of nodes with no external fanout.]
1085
1086 Description []
1087
1088 SideEffects []
1089
1090 SeeAlso []
1091
1092 ***********************************************************************/
Ivy_FastMapCutCost(Ivy_Man_t * pAig,Vec_Ptr_t * vFront)1093 int Ivy_FastMapCutCost( Ivy_Man_t * pAig, Vec_Ptr_t * vFront )
1094 {
1095 Ivy_Supp_t * pSuppF;
1096 Ivy_Obj_t * pFanin;
1097 int i, Counter = 0;
1098 Vec_PtrForEachEntry( Ivy_Obj_t *, vFront, pFanin, i )
1099 {
1100 pSuppF = Ivy_ObjSupp( pAig, pFanin );
1101 if ( pSuppF->nRefs == 0 )
1102 Counter++;
1103 }
1104 return Counter;
1105 }
1106
1107 /**Function*************************************************************
1108
1109 Synopsis [Performs area recovery for each node.]
1110
1111 Description []
1112
1113 SideEffects []
1114
1115 SeeAlso []
1116
1117 ***********************************************************************/
Ivy_FastMapMark_rec(Ivy_Man_t * pAig,Ivy_Obj_t * pObj)1118 void Ivy_FastMapMark_rec( Ivy_Man_t * pAig, Ivy_Obj_t * pObj )
1119 {
1120 if ( Ivy_ObjIsTravIdCurrent(pAig, pObj) )
1121 return;
1122 assert( Ivy_ObjIsNode(pObj) );
1123 Ivy_FastMapMark_rec( pAig, Ivy_ObjFanin0(pObj) );
1124 Ivy_FastMapMark_rec( pAig, Ivy_ObjFanin1(pObj) );
1125 Ivy_ObjSetTravIdCurrent(pAig, pObj);
1126 }
1127
1128 /**Function*************************************************************
1129
1130 Synopsis [Returns 1 if the number of fanins will grow.]
1131
1132 Description []
1133
1134 SideEffects []
1135
1136 SeeAlso []
1137
1138 ***********************************************************************/
Ivy_FastMapNodeWillGrow(Ivy_Man_t * pAig,Ivy_Obj_t * pObj)1139 int Ivy_FastMapNodeWillGrow( Ivy_Man_t * pAig, Ivy_Obj_t * pObj )
1140 {
1141 Ivy_Obj_t * pFanin0, * pFanin1;
1142 assert( Ivy_ObjIsNode(pObj) );
1143 pFanin0 = Ivy_ObjFanin0(pObj);
1144 pFanin1 = Ivy_ObjFanin1(pObj);
1145 return !Ivy_ObjIsTravIdCurrent(pAig, pFanin0) && !Ivy_ObjIsTravIdCurrent(pAig, pFanin1);
1146 }
1147
1148 /**Function*************************************************************
1149
1150 Synopsis [Returns the increase in the number of fanins with no external refs.]
1151
1152 Description []
1153
1154 SideEffects []
1155
1156 SeeAlso []
1157
1158 ***********************************************************************/
Ivy_FastMapNodeFaninCost(Ivy_Man_t * pAig,Ivy_Obj_t * pObj)1159 int Ivy_FastMapNodeFaninCost( Ivy_Man_t * pAig, Ivy_Obj_t * pObj )
1160 {
1161 Ivy_Supp_t * pSuppF;
1162 Ivy_Obj_t * pFanin;
1163 int Counter = 0;
1164 assert( Ivy_ObjIsNode(pObj) );
1165 // check if the node has external refs
1166 pSuppF = Ivy_ObjSupp( pAig, pObj );
1167 if ( pSuppF->nRefs == 0 )
1168 Counter--;
1169 // increment the number of fanins without external refs
1170 pFanin = Ivy_ObjFanin0(pObj);
1171 pSuppF = Ivy_ObjSupp( pAig, pFanin );
1172 if ( !Ivy_ObjIsTravIdCurrent(pAig, pFanin) && pSuppF->nRefs == 0 )
1173 Counter++;
1174 // increment the number of fanins without external refs
1175 pFanin = Ivy_ObjFanin1(pObj);
1176 pSuppF = Ivy_ObjSupp( pAig, pFanin );
1177 if ( !Ivy_ObjIsTravIdCurrent(pAig, pFanin) && pSuppF->nRefs == 0 )
1178 Counter++;
1179 return Counter;
1180 }
1181
1182 /**Function*************************************************************
1183
1184 Synopsis [Updates the frontier.]
1185
1186 Description []
1187
1188 SideEffects []
1189
1190 SeeAlso []
1191
1192 ***********************************************************************/
Ivy_FastMapNodeFaninUpdate(Ivy_Man_t * pAig,Ivy_Obj_t * pObj,Vec_Ptr_t * vFront)1193 void Ivy_FastMapNodeFaninUpdate( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, Vec_Ptr_t * vFront )
1194 {
1195 Ivy_Obj_t * pFanin;
1196 assert( Ivy_ObjIsNode(pObj) );
1197 Vec_PtrRemove( vFront, pObj );
1198 pFanin = Ivy_ObjFanin0(pObj);
1199 if ( !Ivy_ObjIsTravIdCurrent(pAig, pFanin) )
1200 {
1201 Ivy_ObjSetTravIdCurrent(pAig, pFanin);
1202 Vec_PtrPush( vFront, pFanin );
1203 }
1204 pFanin = Ivy_ObjFanin1(pObj);
1205 if ( !Ivy_ObjIsTravIdCurrent(pAig, pFanin) )
1206 {
1207 Ivy_ObjSetTravIdCurrent(pAig, pFanin);
1208 Vec_PtrPush( vFront, pFanin );
1209 }
1210 }
1211
1212 /**Function*************************************************************
1213
1214 Synopsis [Compacts the number of external refs.]
1215
1216 Description []
1217
1218 SideEffects []
1219
1220 SeeAlso []
1221
1222 ***********************************************************************/
Ivy_FastMapNodeFaninCompact0(Ivy_Man_t * pAig,Ivy_Obj_t * pObj,int nLimit,Vec_Ptr_t * vFront)1223 int Ivy_FastMapNodeFaninCompact0( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront )
1224 {
1225 Ivy_Obj_t * pFanin;
1226 int i;
1227 Vec_PtrForEachEntry( Ivy_Obj_t *, vFront, pFanin, i )
1228 {
1229 if ( Ivy_ObjIsCi(pFanin) )
1230 continue;
1231 if ( Ivy_FastMapNodeWillGrow(pAig, pFanin) )
1232 continue;
1233 if ( Ivy_FastMapNodeFaninCost(pAig, pFanin) <= 0 )
1234 {
1235 Ivy_FastMapNodeFaninUpdate( pAig, pFanin, vFront );
1236 return 1;
1237 }
1238 }
1239 return 0;
1240 }
1241
1242 /**Function*************************************************************
1243
1244 Synopsis [Compacts the number of external refs.]
1245
1246 Description []
1247
1248 SideEffects []
1249
1250 SeeAlso []
1251
1252 ***********************************************************************/
Ivy_FastMapNodeFaninCompact1(Ivy_Man_t * pAig,Ivy_Obj_t * pObj,int nLimit,Vec_Ptr_t * vFront)1253 int Ivy_FastMapNodeFaninCompact1( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront )
1254 {
1255 Ivy_Obj_t * pFanin;
1256 int i;
1257 Vec_PtrForEachEntry( Ivy_Obj_t *, vFront, pFanin, i )
1258 {
1259 if ( Ivy_ObjIsCi(pFanin) )
1260 continue;
1261 if ( Ivy_FastMapNodeFaninCost(pAig, pFanin) < 0 )
1262 {
1263 Ivy_FastMapNodeFaninUpdate( pAig, pFanin, vFront );
1264 return 1;
1265 }
1266 }
1267 return 0;
1268 }
1269
1270 /**Function*************************************************************
1271
1272 Synopsis [Compacts the number of external refs.]
1273
1274 Description []
1275
1276 SideEffects []
1277
1278 SeeAlso []
1279
1280 ***********************************************************************/
Ivy_FastMapNodeFaninCompact2(Ivy_Man_t * pAig,Ivy_Obj_t * pObj,int nLimit,Vec_Ptr_t * vFront)1281 int Ivy_FastMapNodeFaninCompact2( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront )
1282 {
1283 Ivy_Obj_t * pFanin;
1284 int i;
1285 Vec_PtrForEachEntry( Ivy_Obj_t *, vFront, pFanin, i )
1286 {
1287 if ( Ivy_ObjIsCi(pFanin) )
1288 continue;
1289 if ( Ivy_FastMapNodeFaninCost(pAig, pFanin) <= 0 )
1290 {
1291 Ivy_FastMapNodeFaninUpdate( pAig, pFanin, vFront );
1292 return 1;
1293 }
1294 }
1295 return 0;
1296 }
1297
1298 /**Function*************************************************************
1299
1300 Synopsis [Compacts the number of external refs.]
1301
1302 Description []
1303
1304 SideEffects []
1305
1306 SeeAlso []
1307
1308 ***********************************************************************/
Ivy_FastMapNodeFaninCompact_int(Ivy_Man_t * pAig,Ivy_Obj_t * pObj,int nLimit,Vec_Ptr_t * vFront)1309 int Ivy_FastMapNodeFaninCompact_int( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront )
1310 {
1311 if ( Ivy_FastMapNodeFaninCompact0(pAig, pObj, nLimit, vFront) )
1312 return 1;
1313 if ( Vec_PtrSize(vFront) < nLimit && Ivy_FastMapNodeFaninCompact1(pAig, pObj, nLimit, vFront) )
1314 return 1;
1315 if ( Vec_PtrSize(vFront) < nLimit && Ivy_FastMapNodeFaninCompact2(pAig, pObj, nLimit, vFront) )
1316 return 1;
1317 assert( Vec_PtrSize(vFront) <= nLimit );
1318 return 0;
1319 }
1320
1321 /**Function*************************************************************
1322
1323 Synopsis [Compacts the number of external refs.]
1324
1325 Description []
1326
1327 SideEffects []
1328
1329 SeeAlso []
1330
1331 ***********************************************************************/
Ivy_FastMapNodeFaninCompact(Ivy_Man_t * pAig,Ivy_Obj_t * pObj,int nLimit,Vec_Ptr_t * vFront)1332 void Ivy_FastMapNodeFaninCompact( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront )
1333 {
1334 while ( Ivy_FastMapNodeFaninCompact_int( pAig, pObj, nLimit, vFront ) );
1335 }
1336
1337 /**Function*************************************************************
1338
1339 Synopsis [Prepares node mapping.]
1340
1341 Description []
1342
1343 SideEffects []
1344
1345 SeeAlso []
1346
1347 ***********************************************************************/
Ivy_FastMapNodePrepare(Ivy_Man_t * pAig,Ivy_Obj_t * pObj,int nLimit,Vec_Ptr_t * vFront,Vec_Ptr_t * vFrontOld)1348 void Ivy_FastMapNodePrepare( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vFrontOld )
1349 {
1350 Ivy_Supp_t * pSupp;
1351 Ivy_Obj_t * pFanin;
1352 int i;
1353 pSupp = Ivy_ObjSupp( pAig, pObj );
1354 // expand the cut downwards from the given place
1355 Vec_PtrClear( vFront );
1356 Vec_PtrClear( vFrontOld );
1357 Ivy_ManIncrementTravId( pAig );
1358 for ( i = 0; i < pSupp->nSize; i++ )
1359 {
1360 pFanin = Ivy_ManObj(pAig, pSupp->pArray[i]);
1361 Vec_PtrPush( vFront, pFanin );
1362 Vec_PtrPush( vFrontOld, pFanin );
1363 Ivy_ObjSetTravIdCurrent( pAig, pFanin );
1364 }
1365 // mark the nodes in the cone
1366 Ivy_FastMapMark_rec( pAig, pObj );
1367 }
1368
1369 /**Function*************************************************************
1370
1371 Synopsis [Updates the frontier.]
1372
1373 Description []
1374
1375 SideEffects []
1376
1377 SeeAlso []
1378
1379 ***********************************************************************/
Ivy_FastMapNodeUpdate(Ivy_Man_t * pAig,Ivy_Obj_t * pObj,Vec_Ptr_t * vFront)1380 void Ivy_FastMapNodeUpdate( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, Vec_Ptr_t * vFront )
1381 {
1382 Ivy_Supp_t * pSupp;
1383 Ivy_Obj_t * pFanin;
1384 int i;
1385 pSupp = Ivy_ObjSupp( pAig, pObj );
1386 // deref node's cut
1387 Ivy_FastMapNodeDeref( pAig, pObj );
1388 // update the node's cut
1389 pSupp->nSize = Vec_PtrSize(vFront);
1390 Vec_PtrForEachEntry( Ivy_Obj_t *, vFront, pFanin, i )
1391 pSupp->pArray[i] = pFanin->Id;
1392 // ref the new cut
1393 Ivy_FastMapNodeRef( pAig, pObj );
1394 }
1395
1396 /**Function*************************************************************
1397
1398 Synopsis [Performs area recovery for each node.]
1399
1400 Description []
1401
1402 SideEffects []
1403
1404 SeeAlso []
1405
1406 ***********************************************************************/
Ivy_FastMapNodeRecover2(Ivy_Man_t * pAig,Ivy_Obj_t * pObj,int nLimit,Vec_Ptr_t * vFront,Vec_Ptr_t * vFrontOld)1407 void Ivy_FastMapNodeRecover2( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vFrontOld )
1408 {
1409 Ivy_Supp_t * pSupp;
1410 int CostBef, CostAft;
1411 int AreaBef, AreaAft;
1412 pSupp = Ivy_ObjSupp( pAig, pObj );
1413 // if ( pSupp->nRefs == 0 )
1414 // return;
1415 if ( pSupp->nRefs == 0 )
1416 AreaBef = Ivy_FastMapNodeAreaDerefed( pAig, pObj );
1417 else
1418 AreaBef = Ivy_FastMapNodeAreaRefed( pAig, pObj );
1419 // get the area
1420 if ( AreaBef == 1 )
1421 return;
1422
1423 if ( pSupp->nRefs == 0 )
1424 {
1425 pSupp->nRefs = 1000000;
1426 Ivy_FastMapNodeRef( pAig, pObj );
1427 }
1428 // the cut is non-trivial
1429 Ivy_FastMapNodePrepare( pAig, pObj, nLimit, vFront, vFrontOld );
1430 // iteratively modify the cut
1431 CostBef = Ivy_FastMapCutCost( pAig, vFront );
1432 Ivy_FastMapNodeFaninCompact( pAig, pObj, nLimit, vFront );
1433 CostAft = Ivy_FastMapCutCost( pAig, vFront );
1434 assert( CostBef >= CostAft );
1435 // update the node
1436 Ivy_FastMapNodeUpdate( pAig, pObj, vFront );
1437 // get the new area
1438 AreaAft = Ivy_FastMapNodeAreaRefed( pAig, pObj );
1439 if ( AreaAft > AreaBef )
1440 {
1441 Ivy_FastMapNodeUpdate( pAig, pObj, vFrontOld );
1442 AreaAft = Ivy_FastMapNodeAreaRefed( pAig, pObj );
1443 assert( AreaAft == AreaBef );
1444 }
1445 if ( pSupp->nRefs == 1000000 )
1446 {
1447 pSupp->nRefs = 0;
1448 Ivy_FastMapNodeDeref( pAig, pObj );
1449 }
1450 }
1451
1452 /**Function*************************************************************
1453
1454 Synopsis [Performs area recovery for each node.]
1455
1456 Description []
1457
1458 SideEffects []
1459
1460 SeeAlso []
1461
1462 ***********************************************************************/
Ivy_FastMapNodeRecover(Ivy_Man_t * pAig,Ivy_Obj_t * pObj,int nLimit,Vec_Ptr_t * vFront,Vec_Ptr_t * vFrontOld)1463 void Ivy_FastMapNodeRecover( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vFrontOld )
1464 {
1465 Ivy_Supp_t * pSupp;
1466 int CostBef, CostAft;
1467 int AreaBef, AreaAft;
1468 int DelayOld;
1469 pSupp = Ivy_ObjSupp( pAig, pObj );
1470 DelayOld = pSupp->Delay = Ivy_FastMapNodeDelay( pAig, pObj );
1471 assert( pSupp->Delay <= pSupp->DelayR );
1472 if ( pSupp->nRefs == 0 )
1473 return;
1474 // get the area
1475 AreaBef = Ivy_FastMapNodeAreaRefed( pAig, pObj );
1476 // if ( AreaBef == 1 )
1477 // return;
1478 // the cut is non-trivial
1479 Ivy_FastMapNodePrepare( pAig, pObj, nLimit, vFront, vFrontOld );
1480 // iteratively modify the cut
1481 Ivy_FastMapNodeDeref( pAig, pObj );
1482 CostBef = Ivy_FastMapCutCost( pAig, vFront );
1483 Ivy_FastMapNodeFaninCompact( pAig, pObj, nLimit, vFront );
1484 CostAft = Ivy_FastMapCutCost( pAig, vFront );
1485 Ivy_FastMapNodeRef( pAig, pObj );
1486 assert( CostBef >= CostAft );
1487 // update the node
1488 Ivy_FastMapNodeUpdate( pAig, pObj, vFront );
1489 pSupp->Delay = Ivy_FastMapNodeDelay( pAig, pObj );
1490 // get the new area
1491 AreaAft = Ivy_FastMapNodeAreaRefed( pAig, pObj );
1492 if ( AreaAft > AreaBef || pSupp->Delay > pSupp->DelayR )
1493 {
1494 Ivy_FastMapNodeUpdate( pAig, pObj, vFrontOld );
1495 AreaAft = Ivy_FastMapNodeAreaRefed( pAig, pObj );
1496 assert( AreaAft == AreaBef );
1497 pSupp->Delay = DelayOld;
1498 }
1499 }
1500
1501 /**Function*************************************************************
1502
1503 Synopsis [Performs area recovery for each node.]
1504
1505 Description []
1506
1507 SideEffects []
1508
1509 SeeAlso []
1510
1511 ***********************************************************************/
Ivy_FastMapNodeRecover4(Ivy_Man_t * pAig,Ivy_Obj_t * pObj,int nLimit,Vec_Ptr_t * vFront,Vec_Ptr_t * vFrontOld)1512 void Ivy_FastMapNodeRecover4( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vFrontOld )
1513 {
1514 Ivy_Supp_t * pSupp;
1515 int CostBef, CostAft;
1516 int AreaBef, AreaAft;
1517 int DelayOld;
1518 pSupp = Ivy_ObjSupp( pAig, pObj );
1519 DelayOld = pSupp->Delay = Ivy_FastMapNodeDelay( pAig, pObj );
1520 assert( pSupp->Delay <= pSupp->DelayR );
1521 // if ( pSupp->nRefs == 0 )
1522 // return;
1523 // AreaBef = Ivy_FastMapNodeAreaRefed( pAig, pObj );
1524 // get the area
1525 if ( pSupp->nRefs == 0 )
1526 AreaBef = Ivy_FastMapNodeAreaDerefed( pAig, pObj );
1527 else
1528 AreaBef = Ivy_FastMapNodeAreaRefed( pAig, pObj );
1529 if ( AreaBef == 1 )
1530 return;
1531
1532 if ( pSupp->nRefs == 0 )
1533 {
1534 pSupp->nRefs = 1000000;
1535 Ivy_FastMapNodeRef( pAig, pObj );
1536 }
1537 // the cut is non-trivial
1538 Ivy_FastMapNodePrepare( pAig, pObj, nLimit, vFront, vFrontOld );
1539 // iteratively modify the cut
1540 CostBef = Ivy_FastMapCutCost( pAig, vFront );
1541 Ivy_FastMapNodeFaninCompact( pAig, pObj, nLimit, vFront );
1542 CostAft = Ivy_FastMapCutCost( pAig, vFront );
1543 assert( CostBef >= CostAft );
1544 // update the node
1545 Ivy_FastMapNodeUpdate( pAig, pObj, vFront );
1546 pSupp->Delay = Ivy_FastMapNodeDelay( pAig, pObj );
1547 // get the new area
1548 AreaAft = Ivy_FastMapNodeAreaRefed( pAig, pObj );
1549 if ( AreaAft > AreaBef || pSupp->Delay > pSupp->DelayR )
1550 {
1551 Ivy_FastMapNodeUpdate( pAig, pObj, vFrontOld );
1552 AreaAft = Ivy_FastMapNodeAreaRefed( pAig, pObj );
1553 assert( AreaAft == AreaBef );
1554 pSupp->Delay = DelayOld;
1555 }
1556 if ( pSupp->nRefs == 1000000 )
1557 {
1558 pSupp->nRefs = 0;
1559 Ivy_FastMapNodeDeref( pAig, pObj );
1560 }
1561 }
1562
1563 ////////////////////////////////////////////////////////////////////////
1564 /// END OF FILE ///
1565 ////////////////////////////////////////////////////////////////////////
1566
1567
1568 ABC_NAMESPACE_IMPL_END
1569
1570