ABC: A System for Sequential Synthesis and Verification
 
Loading...
Searching...
No Matches
ivyFastMap.c
Go to the documentation of this file.
1
20
21#include "ivy.h"
22
23ABC_NAMESPACE_IMPL_START
24
25
29
30#define IVY_INFINITY 10000
31
32typedef struct Ivy_SuppMan_t_ Ivy_SuppMan_t;
33struct 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
42typedef struct Ivy_Supp_t_ Ivy_Supp_t;
43struct 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
55static 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}
59static 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
70static void Ivy_FastMapPrint( Ivy_Man_t * pAig, int Delay, int Area, abctime Time, char * pStr );
71static int Ivy_FastMapDelay( Ivy_Man_t * pAig );
72static int Ivy_FastMapArea( Ivy_Man_t * pAig );
73static void Ivy_FastMapNode( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit );
74static void Ivy_FastMapNodeArea( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit );
75static int Ivy_FastMapMerge( Ivy_Supp_t * pSupp0, Ivy_Supp_t * pSupp1, Ivy_Supp_t * pSupp, int nLimit );
76static void Ivy_FastMapRequired( Ivy_Man_t * pAig, int Delay, int fSetInter );
77static void Ivy_FastMapRecover( Ivy_Man_t * pAig, int nLimit );
78static int Ivy_FastMapNodeDelay( Ivy_Man_t * pAig, Ivy_Obj_t * pObj );
79static int Ivy_FastMapNodeAreaRefed( Ivy_Man_t * pAig, Ivy_Obj_t * pObj );
80static int Ivy_FastMapNodeAreaDerefed( Ivy_Man_t * pAig, Ivy_Obj_t * pObj );
81static void Ivy_FastMapNodeRecover( Ivy_Man_t * pAig, Ivy_Obj_t * pObj, int nLimit, Vec_Ptr_t * vFront, Vec_Ptr_t * vFrontOld );
82static int Ivy_FastMapNodeRef( Ivy_Man_t * pAig, Ivy_Obj_t * pObj );
83static int Ivy_FastMapNodeDeref( Ivy_Man_t * pAig, Ivy_Obj_t * pObj );
84
85
86extern abctime s_MappingTime;
87extern int s_MappingMem;
88
89
93
105void 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;
121clk = 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 {
139clk = 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
148clk = 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
158clk = 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
194void 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
214void 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
231int 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
259int 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
288int 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
316static inline int Ivy_ObjIsNodeInt1( Ivy_Obj_t * pObj )
317{
318 return Ivy_ObjIsNode(pObj) && Ivy_ObjRefs(pObj) == 1;
319}
320
332static inline int Ivy_ObjIsNodeInt2( Ivy_Obj_t * pObj )
333{
334 return Ivy_ObjIsNode(pObj) && Ivy_ObjRefs(pObj) <= 2;
335}
336
348static 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
370void 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
441void 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
541void 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
707int 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
793void 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
813void 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
836void 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
917void 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
943int 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
968int 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
1003int 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
1038int 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
1064int 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
1093int 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
1118void 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
1139int 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
1159int 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
1193void 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
1223int 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
1253int 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
1281int 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
1309int 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
1332void 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
1348void 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
1380void 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
1407void 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
1463void 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
1512void 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
1566
1567
1568ABC_NAMESPACE_IMPL_END
1569
abctime
ABC_INT64_T abctime
Definition abc_global.h:332
ABC_PRT
#define ABC_PRT(a, t)
Definition abc_global.h:255
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition abc_global.h:264
ABC_FREE
#define ABC_FREE(obj)
Definition abc_global.h:267
ABC_NAMESPACE_IMPL_START
#define ABC_NAMESPACE_IMPL_START
Definition abc_namespaces.h:54
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition abc_namespaces.h:55
Vec_Int_t
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition bblif.c:37
p
Cube * p
Definition exorList.c:222
s_MappingTime
abctime s_MappingTime
DECLARATIONS ///.
Definition abcPrint.c:47
Ivy_FastMapNodePrepare
void Ivy_FastMapNodePrepare(Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront, Vec_Ptr_t *vFrontOld)
Definition ivyFastMap.c:1348
Ivy_FastMapCutCost
int Ivy_FastMapCutCost(Ivy_Man_t *pAig, Vec_Ptr_t *vFront)
Definition ivyFastMap.c:1093
Ivy_FastMapNodeRecover4
void Ivy_FastMapNodeRecover4(Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront, Vec_Ptr_t *vFrontOld)
Definition ivyFastMap.c:1512
Ivy_FastMapNodeFaninCompact1
int Ivy_FastMapNodeFaninCompact1(Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront)
Definition ivyFastMap.c:1253
Ivy_FastMapNodeUpdate
void Ivy_FastMapNodeUpdate(Ivy_Man_t *pAig, Ivy_Obj_t *pObj, Vec_Ptr_t *vFront)
Definition ivyFastMap.c:1380
Ivy_FastMapMark_rec
void Ivy_FastMapMark_rec(Ivy_Man_t *pAig, Ivy_Obj_t *pObj)
Definition ivyFastMap.c:1118
Ivy_FastMapStop
void Ivy_FastMapStop(Ivy_Man_t *pAig)
Definition ivyFastMap.c:194
Ivy_FastMapNodeFaninCompact0
int Ivy_FastMapNodeFaninCompact0(Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront)
Definition ivyFastMap.c:1223
Ivy_FastMapArea_rec
int Ivy_FastMapArea_rec(Ivy_Man_t *pAig, Ivy_Obj_t *pObj, Vec_Vec_t *vLuts)
Definition ivyFastMap.c:259
Ivy_FastMapNodeWillGrow
int Ivy_FastMapNodeWillGrow(Ivy_Man_t *pAig, Ivy_Obj_t *pObj)
Definition ivyFastMap.c:1139
Ivy_FastMapNodeFaninCompact2
int Ivy_FastMapNodeFaninCompact2(Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront)
Definition ivyFastMap.c:1281
IVY_INFINITY
#define IVY_INFINITY
DECLARATIONS ///.
Definition ivyFastMap.c:30
s_MappingMem
int s_MappingMem
Definition abcPrint.c:48
Ivy_FastMapNodeFaninCost
int Ivy_FastMapNodeFaninCost(Ivy_Man_t *pAig, Ivy_Obj_t *pObj)
Definition ivyFastMap.c:1159
Ivy_FastMapNodeRecover2
void Ivy_FastMapNodeRecover2(Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront, Vec_Ptr_t *vFrontOld)
Definition ivyFastMap.c:1407
Ivy_FastMapNodeArea2
void Ivy_FastMapNodeArea2(Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit)
Definition ivyFastMap.c:370
Ivy_SuppMan_t
struct Ivy_SuppMan_t_ Ivy_SuppMan_t
Definition ivyFastMap.c:32
Ivy_FastMapReadSupp
void Ivy_FastMapReadSupp(Ivy_Man_t *pAig, Ivy_Obj_t *pObj, Vec_Int_t *vLeaves)
Definition ivyFastMap.c:793
Ivy_FastMapNodeFaninCompact_int
int Ivy_FastMapNodeFaninCompact_int(Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront)
Definition ivyFastMap.c:1309
Ivy_FastMapPerform
void Ivy_FastMapPerform(Ivy_Man_t *pAig, int nLimit, int fRecovery, int fVerbose)
FUNCTION DEFINITIONS ///.
Definition ivyFastMap.c:105
Ivy_Supp_t
struct Ivy_Supp_t_ Ivy_Supp_t
Definition ivyFastMap.c:42
Ivy_FastMapNodeFaninCompact
void Ivy_FastMapNodeFaninCompact(Ivy_Man_t *pAig, Ivy_Obj_t *pObj, int nLimit, Vec_Ptr_t *vFront)
Definition ivyFastMap.c:1332
Ivy_FastMapNodeFaninUpdate
void Ivy_FastMapNodeFaninUpdate(Ivy_Man_t *pAig, Ivy_Obj_t *pObj, Vec_Ptr_t *vFront)
Definition ivyFastMap.c:1193
Ivy_FastMapRequired_rec
void Ivy_FastMapRequired_rec(Ivy_Man_t *pAig, Ivy_Obj_t *pObj, Ivy_Obj_t *pRoot, int DelayR)
Definition ivyFastMap.c:813
Ivy_Man_t
typedefABC_NAMESPACE_HEADER_START struct Ivy_Man_t_ Ivy_Man_t
INCLUDES ///.
Definition ivy.h:46
Ivy_ManIncrementTravId
void Ivy_ManIncrementTravId(Ivy_Man_t *p)
DECLARATIONS ///.
Definition ivyUtil.c:45
IVY_MAX
#define IVY_MAX(a, b)
Definition ivy.h:183
Ivy_ManForEachNode
#define Ivy_ManForEachNode(p, pObj, i)
Definition ivy.h:402
IVY_MIN
#define IVY_MIN(a, b)
MACRO DEFINITIONS ///.
Definition ivy.h:182
Ivy_ManForEachPo
#define Ivy_ManForEachPo(p, pObj, i)
Definition ivy.h:390
Ivy_Obj_t
struct Ivy_Obj_t_ Ivy_Obj_t
Definition ivy.h:47
Ivy_ManCleanTravId
void Ivy_ManCleanTravId(Ivy_Man_t *p)
Definition ivyUtil.c:63
Ivy_ManForEachPi
#define Ivy_ManForEachPi(p, pObj, i)
ITERATORS ///.
Definition ivy.h:387
Ivy_Obj_t_::Id
int Id
Definition ivy.h:75
Ivy_SuppMan_t_
Definition ivyFastMap.c:34
Ivy_SuppMan_t_::nSize
int nSize
Definition ivyFastMap.c:37
Ivy_SuppMan_t_::nLimit
int nLimit
Definition ivyFastMap.c:35
Ivy_SuppMan_t_::nObjs
int nObjs
Definition ivyFastMap.c:36
Ivy_SuppMan_t_::vLuts
Vec_Vec_t * vLuts
Definition ivyFastMap.c:39
Ivy_SuppMan_t_::pMem
char * pMem
Definition ivyFastMap.c:38
Ivy_Supp_t_
Definition ivyFastMap.c:44
Ivy_Supp_t_::fMark
char fMark
Definition ivyFastMap.c:46
Ivy_Supp_t_::fMark2
char fMark2
Definition ivyFastMap.c:47
Ivy_Supp_t_::Delay
short Delay
Definition ivyFastMap.c:50
Ivy_Supp_t_::nSize
char nSize
Definition ivyFastMap.c:45
Ivy_Supp_t_::fMark3
char fMark3
Definition ivyFastMap.c:48
Ivy_Supp_t_::pArray
int pArray[0]
Definition ivyFastMap.c:52
Ivy_Supp_t_::DelayR
short DelayR
Definition ivyFastMap.c:51
Ivy_Supp_t_::nRefs
int nRefs
Definition ivyFastMap.c:49
assert
#define assert(ex)
Definition util_old.h:213
memcpy
char * memcpy()
memset
char * memset()
Vec_Ptr_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition vecPtr.h:42
Vec_PtrForEachEntry
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition vecPtr.h:55
Vec_VecForEachLevelReverse
#define Vec_VecForEachLevelReverse(vGlob, vVec, i)
Definition vecVec.h:63
Vec_Vec_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Vec_t_ Vec_Vec_t
INCLUDES ///.
Definition vecVec.h:42