ABC: A System for Sequential Synthesis and Verification
 
Loading...
Searching...
No Matches
absRpm.c
Go to the documentation of this file.
1
20
21#include "abs.h"
22#include "misc/vec/vecWec.h"
23
24ABC_NAMESPACE_IMPL_START
25
29
30static inline int Gia_ObjDom( Gia_Man_t * p, Gia_Obj_t * pObj ) { return Vec_IntEntry(p->vDoms, Gia_ObjId(p, pObj)); }
31static inline void Gia_ObjSetDom( Gia_Man_t * p, Gia_Obj_t * pObj, int d ) { Vec_IntWriteEntry(p->vDoms, Gia_ObjId(p, pObj), d); }
32
33static int Abs_ManSupport2( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSupp );
34static int Abs_GiaObjDeref_rec( Gia_Man_t * p, Gia_Obj_t * pNode );
35static int Abs_GiaObjRef_rec( Gia_Man_t * p, Gia_Obj_t * pNode );
36
40
53void Gia_ManAddDom( Gia_Man_t * p, Gia_Obj_t * pObj, int iDom0 )
54{
55 int iDom1, iDomNext;
56 if ( Gia_ObjDom(p, pObj) == -1 )
57 {
58 Gia_ObjSetDom( p, pObj, iDom0 );
59 return;
60 }
61 iDom1 = Gia_ObjDom( p, pObj );
62 while ( 1 )
63 {
64 if ( iDom0 > iDom1 )
65 {
66 iDomNext = Gia_ObjDom( p, Gia_ManObj(p, iDom1) );
67 if ( iDomNext == iDom1 )
68 break;
69 iDom1 = iDomNext;
70 continue;
71 }
72 if ( iDom1 > iDom0 )
73 {
74 iDomNext = Gia_ObjDom( p, Gia_ManObj(p, iDom0) );
75 if ( iDomNext == iDom0 )
76 break;
77 iDom0 = iDomNext;
78 continue;
79 }
80 assert( iDom0 == iDom1 );
81 Gia_ObjSetDom( p, pObj, iDom0 );
82 return;
83 }
84 Gia_ObjSetDom( p, pObj, Gia_ObjId(p, pObj) );
85}
86void Gia_ManComputeDoms( Gia_Man_t * p )
87{
88 Gia_Obj_t * pObj;
89 int i;
90 if ( p->vDoms == NULL )
91 p->vDoms = Vec_IntAlloc( 0 );
92 Vec_IntFill( p->vDoms, Gia_ManObjNum(p), -1 );
93 Gia_ManForEachObjReverse( p, pObj, i )
94 {
95 if ( i == 0 || Gia_ObjIsCi(pObj) )
96 continue;
97 if ( pObj->fMark1 || (p->pRefs && Gia_ObjIsAnd(pObj) && Gia_ObjRefNum(p, pObj) == 0) )
98 continue;
99 if ( Gia_ObjIsCo(pObj) )
100 {
101 Gia_ObjSetDom( p, pObj, i );
102 Gia_ManAddDom( p, Gia_ObjFanin0(pObj), i );
103 continue;
104 }
105 assert( Gia_ObjIsAnd(pObj) );
106 Gia_ManAddDom( p, Gia_ObjFanin0(pObj), i );
107 Gia_ManAddDom( p, Gia_ObjFanin1(pObj), i );
108 }
109}
110
111
123Vec_Wec_t * Gia_ManCreateSupps( Gia_Man_t * p, int fVerbose )
124{
125 abctime clk = Abc_Clock();
126 Gia_Obj_t * pObj; int i, Id;
127 Vec_Wec_t * vSupps = Vec_WecStart( Gia_ManObjNum(p) );
128 Gia_ManForEachCiId( p, Id, i )
129 Vec_IntPush( Vec_WecEntry(vSupps, Id), i );
130 Gia_ManForEachAnd( p, pObj, Id )
131 Vec_IntTwoMerge2( Vec_WecEntry(vSupps, Gia_ObjFaninId0(pObj, Id)),
132 Vec_WecEntry(vSupps, Gia_ObjFaninId1(pObj, Id)),
133 Vec_WecEntry(vSupps, Id) );
134// Gia_ManForEachCo( p, pObj, i )
135// Vec_IntAppend( Vec_WecEntry(vSupps, Gia_ObjId(p, pObj)), Vec_WecEntry(vSupps, Gia_ObjFaninId0p(p, pObj)) );
136 if ( fVerbose )
137 Abc_PrintTime( 1, "Support computation", Abc_Clock() - clk );
138 return vSupps;
139}
140void Gia_ManDomTest( Gia_Man_t * p )
141{
142 Vec_Int_t * vDoms = Vec_IntAlloc( 100 );
143 Vec_Int_t * vSupp = Vec_IntAlloc( 100 );
144 Vec_Wec_t * vSupps = Gia_ManCreateSupps( p, 1 );
145 Vec_Wec_t * vDomeds = Vec_WecStart( Gia_ManObjNum(p) );
146 Gia_Obj_t * pObj, * pDom; int i, Id, nMffcSize;
147 Gia_ManCreateRefs( p );
148 Gia_ManComputeDoms( p );
149 Gia_ManForEachCi( p, pObj, i )
150 {
151 if ( Gia_ObjDom(p, pObj) == -1 )
152 continue;
153 for ( pDom = Gia_ManObj(p, Gia_ObjDom(p, pObj)); Gia_ObjIsAnd(pDom); pDom = Gia_ManObj(p, Gia_ObjDom(p, pDom)) )
154 Vec_IntPush( Vec_WecEntry(vDomeds, Gia_ObjId(p, pDom)), i );
155 }
156 Gia_ManForEachAnd( p, pObj, i )
157 if ( Vec_IntEqual(Vec_WecEntry(vSupps, i), Vec_WecEntry(vDomeds, i)) )
158 Vec_IntPush( vDoms, i );
159 Vec_WecFree( vSupps );
160 Vec_WecFree( vDomeds );
161
162 // check MFFC sizes
163 Vec_IntForEachEntry( vDoms, Id, i )
164 Gia_ObjRefInc( p, Gia_ManObj(p, Id) );
165 Vec_IntForEachEntry( vDoms, Id, i )
166 {
167 nMffcSize = Gia_NodeMffcSizeSupp( p, Gia_ManObj(p, Id), vSupp );
168 printf( "%d(%d:%d) ", Id, Vec_IntSize(vSupp), nMffcSize );
169 }
170 printf( "\n" );
171 Vec_IntForEachEntry( vDoms, Id, i )
172 Gia_ObjRefDec( p, Gia_ManObj(p, Id) );
173
174// Vec_IntPrint( vDoms );
175 Vec_IntFree( vDoms );
176 Vec_IntFree( vSupp );
177}
178
190void Gia_ManTestDoms2( Gia_Man_t * p )
191{
192 Vec_Int_t * vNodes;
193 Gia_Obj_t * pObj, * pDom;
194 abctime clk = Abc_Clock();
195 int i;
196 assert( p->vDoms == NULL );
197 Gia_ManComputeDoms( p );
198/*
199 Gia_ManForEachPi( p, pObj, i )
200 if ( Gia_ObjId(p, pObj) != Gia_ObjDom(p, pObj) )
201 printf( "PI =%6d Id =%8d. Dom =%8d.\n", i, Gia_ObjId(p, pObj), Gia_ObjDom(p, pObj) );
202*/
203 Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
204 // for each dominated PI, when if the PIs is in a leaf of the MFFC of the dominator
205 Gia_ManCleanMark1( p );
206 Gia_ManForEachPi( p, pObj, i )
207 pObj->fMark1 = 1;
208 vNodes = Vec_IntAlloc( 100 );
209 Gia_ManCreateRefs( p );
210 Gia_ManForEachPi( p, pObj, i )
211 {
212 if ( Gia_ObjId(p, pObj) == Gia_ObjDom(p, pObj) )
213 continue;
214
215 pDom = Gia_ManObj(p, Gia_ObjDom(p, pObj));
216 if ( Gia_ObjIsCo(pDom) )
217 {
218 assert( Gia_ObjFanin0(pDom) == pObj );
219 continue;
220 }
221 assert( Gia_ObjIsAnd(pDom) );
222 Abs_GiaObjDeref_rec( p, pDom );
223 Abs_ManSupport2( p, pDom, vNodes );
224 Abs_GiaObjRef_rec( p, pDom );
225
226 if ( Vec_IntFind(vNodes, Gia_ObjId(p, pObj)) == -1 )
227 printf( "FAILURE.\n" );
228// else
229// printf( "Success.\n" );
230 }
231 Vec_IntFree( vNodes );
232 Gia_ManCleanMark1( p );
233}
234
246Vec_Int_t * Gia_ManCollectDoms( Gia_Man_t * p )
247{
248 Vec_Int_t * vNodes;
249 Gia_Obj_t * pObj;
250 int Lev, LevMax = ABC_INFINITY;
251 int i, iDom, iDomNext;
252 vNodes = Vec_IntAlloc( 100 );
253 Gia_ManForEachObj( p, pObj, i )
254 {
255 if ( !pObj->fMark1 )
256 continue;
257 if ( p->pRefs && Gia_ObjRefNum(p, pObj) == 0 )
258 continue;
259 iDom = Gia_ObjDom(p, pObj);
260 if ( iDom == -1 )
261 continue;
262 if ( iDom == i )
263 continue;
264 for ( Lev = 0; Lev < LevMax && Gia_ObjIsAnd( Gia_ManObj(p, iDom) ); Lev++ )
265 {
266 Vec_IntPush( vNodes, iDom );
267 iDomNext = Gia_ObjDom( p, Gia_ManObj(p, iDom) );
268 if ( iDomNext == iDom )
269 break;
270 iDom = iDomNext;
271 }
272 }
273 Vec_IntUniqify( vNodes );
274 return vNodes;
275}
276Vec_Int_t * Gia_ManComputePiDoms( Gia_Man_t * p )
277{
278 Vec_Int_t * vNodes;
279 Gia_ManComputeDoms( p );
280 vNodes = Gia_ManCollectDoms( p );
281// Vec_IntPrint( vNodes );
282 return vNodes;
283}
284void Gia_ManTestDoms( Gia_Man_t * p )
285{
286 Vec_Int_t * vNodes;
287 Gia_Obj_t * pObj;
288 int i;
289 // mark PIs
290// Gia_ManCreateRefs( p );
291 Gia_ManCleanMark1( p );
292 Gia_ManForEachPi( p, pObj, i )
293 pObj->fMark1 = 1;
294 // compute dominators
295 assert( p->vDoms == NULL );
296 vNodes = Gia_ManComputePiDoms( p );
297// printf( "Nodes = %d. Doms = %d.\n", Gia_ManAndNum(p), Vec_IntSize(vNodes) );
298 Vec_IntFree( vNodes );
299 // unmark PIs
300 Gia_ManCleanMark1( p );
301}
302
303
315void Gia_ManCountFanoutlessFlops( Gia_Man_t * p )
316{
317 Gia_Obj_t * pObj;
318 int i;
319 int Counter = 0;
320 Gia_ManCreateRefs( p );
321 Gia_ManForEachRo( p, pObj, i )
322 if ( Gia_ObjRefNum(p, pObj) == 0 )
323 Counter++;
324 printf( "Fanoutless flops = %d.\n", Counter );
325 ABC_FREE( p->pRefs );
326}
327
339void Gia_ManCountPisNodes_rec( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vPis, Vec_Int_t * vAnds )
340{
341 if ( Gia_ObjIsTravIdCurrent(p, pObj) )
342 return;
343 Gia_ObjSetTravIdCurrent(p, pObj);
344 if ( pObj->fMark1 )
345 {
346 Vec_IntPush( vPis, Gia_ObjId(p, pObj) );
347 return;
348 }
349 assert( Gia_ObjIsAnd(pObj) );
350 Gia_ManCountPisNodes_rec( p, Gia_ObjFanin0(pObj), vPis, vAnds );
351 Gia_ManCountPisNodes_rec( p, Gia_ObjFanin1(pObj), vPis, vAnds );
352 Vec_IntPush( vAnds, Gia_ObjId(p, pObj) );
353}
354void Gia_ManCountPisNodes( Gia_Man_t * p, Vec_Int_t * vPis, Vec_Int_t * vAnds )
355{
356 Gia_Obj_t * pObj;
357 int i;
358 // mark const0 and flop output
359 Gia_ManIncrementTravId( p );
360 Gia_ObjSetTravIdCurrent( p, Gia_ManConst0(p) );
361 Gia_ManForEachRo( p, pObj, i )
362 Gia_ObjSetTravIdCurrent( p, pObj );
363 // count PIs and internal nodes reachable from COs
364 Vec_IntClear( vPis );
365 Vec_IntClear( vAnds );
366 Gia_ManForEachCo( p, pObj, i )
367 Gia_ManCountPisNodes_rec( p, Gia_ObjFanin0(pObj), vPis, vAnds );
368}
369
381int Abs_GiaObjDeref_rec( Gia_Man_t * p, Gia_Obj_t * pNode )
382{
383 Gia_Obj_t * pFanin;
384 int Counter = 0;
385 if ( pNode->fMark1 || Gia_ObjIsRo(p, pNode) )
386 return 0;
387 assert( Gia_ObjIsAnd(pNode) );
388 pFanin = Gia_ObjFanin0(pNode);
389 assert( Gia_ObjRefNum(p, pFanin) > 0 );
390 if ( Gia_ObjRefDec(p, pFanin) == 0 )
391 Counter += Abs_GiaObjDeref_rec( p, pFanin );
392 pFanin = Gia_ObjFanin1(pNode);
393 assert( Gia_ObjRefNum(p, pFanin) > 0 );
394 if ( Gia_ObjRefDec(p, pFanin) == 0 )
395 Counter += Abs_GiaObjDeref_rec( p, pFanin );
396 return Counter + 1;
397}
398int Abs_GiaObjRef_rec( Gia_Man_t * p, Gia_Obj_t * pNode )
399{
400 Gia_Obj_t * pFanin;
401 int Counter = 0;
402 if ( pNode->fMark1 || Gia_ObjIsRo(p, pNode) )
403 return 0;
404 assert( Gia_ObjIsAnd(pNode) );
405 pFanin = Gia_ObjFanin0(pNode);
406 if ( Gia_ObjRefInc(p, pFanin) == 0 )
407 Counter += Abs_GiaObjRef_rec( p, pFanin );
408 pFanin = Gia_ObjFanin1(pNode);
409 if ( Gia_ObjRefInc(p, pFanin) == 0 )
410 Counter += Abs_GiaObjRef_rec( p, pFanin );
411 return Counter + 1;
412}
413
425int Abs_GiaSortNodes( Gia_Man_t * p, Vec_Int_t * vSupp )
426{
427 Gia_Obj_t * pObj;
428 int nSize = Vec_IntSize(vSupp);
429 int i, RetValue;
430 Gia_ManForEachObjVec( vSupp, p, pObj, i )
431 if ( i < nSize && Gia_ObjRefNum(p, pObj) == 0 && !Gia_ObjIsRo(p, pObj) ) // add removable leaves
432 {
433 assert( pObj->fMark1 );
434 Vec_IntPush( vSupp, Gia_ObjId(p, pObj) );
435 }
436 RetValue = Vec_IntSize(vSupp) - nSize;
437 Gia_ManForEachObjVec( vSupp, p, pObj, i )
438 if ( i < nSize && !(Gia_ObjRefNum(p, pObj) == 0 && !Gia_ObjIsRo(p, pObj)) ) // add non-removable leaves
439 Vec_IntPush( vSupp, Gia_ObjId(p, pObj) );
440 assert( Vec_IntSize(vSupp) == 2 * nSize );
441 memmove( Vec_IntArray(vSupp), Vec_IntArray(vSupp) + nSize, sizeof(int) * nSize );
442 Vec_IntShrink( vSupp, nSize );
443 return RetValue;
444}
445
446
458void Abs_ManSupport1_rec( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSupp )
459{
460 if ( Gia_ObjIsTravIdCurrent(p, pObj) )
461 return;
462 Gia_ObjSetTravIdCurrent(p, pObj);
463 if ( pObj->fMark1 || Gia_ObjIsRo(p, pObj) )
464 {
465 Vec_IntPush( vSupp, Gia_ObjId(p, pObj) );
466 return;
467 }
468 assert( Gia_ObjIsAnd(pObj) );
469 Abs_ManSupport1_rec( p, Gia_ObjFanin0(pObj), vSupp );
470 Abs_ManSupport1_rec( p, Gia_ObjFanin1(pObj), vSupp );
471}
472int Abs_ManSupport1( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSupp )
473{
474 assert( Gia_ObjIsAnd(pObj) );
475 Vec_IntClear( vSupp );
476 Gia_ManIncrementTravId( p );
477 Abs_ManSupport1_rec( p, pObj, vSupp );
478 return Vec_IntSize(vSupp);
479}
480
492void Abs_ManSupport2_rec( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSupp )
493{
494 if ( Gia_ObjIsTravIdCurrent(p, pObj) )
495 return;
496 Gia_ObjSetTravIdCurrent(p, pObj);
497 if ( pObj->fMark1 || Gia_ObjIsRo(p, pObj) || Gia_ObjRefNum(p, pObj) > 0 )
498 {
499 Vec_IntPush( vSupp, Gia_ObjId(p, pObj) );
500 return;
501 }
502 assert( Gia_ObjIsAnd(pObj) );
503 Abs_ManSupport2_rec( p, Gia_ObjFanin0(pObj), vSupp );
504 Abs_ManSupport2_rec( p, Gia_ObjFanin1(pObj), vSupp );
505}
506int Abs_ManSupport2( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSupp )
507{
508 assert( Gia_ObjIsAnd(pObj) );
509 Vec_IntClear( vSupp );
510 Gia_ManIncrementTravId( p );
511 Abs_ManSupport2_rec( p, Gia_ObjFanin0(pObj), vSupp );
512 Abs_ManSupport2_rec( p, Gia_ObjFanin1(pObj), vSupp );
513 Gia_ObjSetTravIdCurrent(p, pObj);
514 return Vec_IntSize(vSupp);
515}
516
528int Abs_ManSupport3( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSupp )
529{
530 Gia_Obj_t * pTemp, * pFan0, * pFan1;
531 int i, nSize0;
532 // collect MFFC
533 Abs_ManSupport2( p, pObj, vSupp );
534 // move dominated to the front
535 nSize0 = Abs_GiaSortNodes( p, vSupp );
536 assert( nSize0 > 0 );
537 // consider remaining nodes
538 while ( 1 )
539 {
540 int fChanges = 0;
541 Gia_ManForEachObjVec( vSupp, p, pTemp, i )
542 {
543 if ( i < nSize0 )
544 continue;
545 if ( !Gia_ObjIsAnd(pTemp) )
546 continue;
547 assert( !pTemp->fMark1 );
548 assert( Gia_ObjRefNum(p, pTemp) > 0 );
549 pFan0 = Gia_ObjFanin0(pTemp);
550 pFan1 = Gia_ObjFanin1(pTemp);
551 if ( Gia_ObjIsTravIdCurrent(p, pFan0) && Gia_ObjIsTravIdCurrent(p, pFan1) )
552 {
553 Vec_IntRemove( vSupp, Gia_ObjId(p, pTemp) );
554 fChanges = 1;
555 break;
556 }
557 if ( Gia_ObjIsTravIdCurrent(p, pFan0) )
558 {
559 Vec_IntRemove( vSupp, Gia_ObjId(p, pTemp) );
560 Vec_IntPush( vSupp, Gia_ObjId(p, pFan1) );
561 assert( !Gia_ObjIsTravIdCurrent(p, pFan1) );
562 Gia_ObjSetTravIdCurrent(p, pFan1);
563 fChanges = 1;
564 break;
565 }
566 if ( Gia_ObjIsTravIdCurrent(p, pFan1) )
567 {
568 Vec_IntRemove( vSupp, Gia_ObjId(p, pTemp) );
569 Vec_IntPush( vSupp, Gia_ObjId(p, pFan0) );
570 assert( !Gia_ObjIsTravIdCurrent(p, pFan0) );
571 Gia_ObjSetTravIdCurrent(p, pFan0);
572 fChanges = 1;
573 break;
574 }
575 }
576 if ( !fChanges )
577 break;
578 }
579 return Vec_IntSize(vSupp);
580}
581
582
594int Abs_GiaCofPrint( word * pTruth, int nSize, int nSize0, int Res )
595{
596 int i, Bit;
597 int nBits = (1 << nSize);
598 int nStep = (1 << nSize0);
599 int Mark[2] = {1,1};
600 for ( i = 0; i < nBits; i++ )
601 {
602 if ( i % nStep == 0 )
603 {
604 printf( " " );
605 assert( Res || (Mark[0] && Mark[1]) );
606 Mark[0] = Mark[1] = 0;
607 }
608 Bit = Abc_InfoHasBit((unsigned *)pTruth, i);
609 Mark[Bit] = 1;
610 printf( "%d", Bit );
611 }
612 printf( "\n" );
613 assert( Res || (Mark[0] && Mark[1]) );
614 return 1;
615}
616
629int Abs_GiaCheckTruth( word * pTruth, int nSize, int nSize0 )
630{
631 unsigned char * pStr = (unsigned char *)pTruth;
632 int nStr = (nSize >= 3 ? (1 << (nSize - 3)) : 1);
633 int i, k, nSteps;
634 assert( nSize0 > 0 && nSize0 <= nSize );
635 if ( nSize0 == 1 )
636 {
637 for ( i = 0; i < nStr; i++ )
638 if ( (((unsigned)pStr[i] ^ ((unsigned)pStr[i] >> 1)) & 0x55) != 0x55 )
639 return 0;
640 return 1;
641 }
642 if ( nSize0 == 2 )
643 {
644 for ( i = 0; i < nStr; i++ )
645 if ( ((unsigned)pStr[i] & 0xF) == 0x0 || (((unsigned)pStr[i] >> 4) & 0xF) == 0x0 ||
646 ((unsigned)pStr[i] & 0xF) == 0xF || (((unsigned)pStr[i] >> 4) & 0xF) == 0xF )
647 return 0;
648 return 1;
649 }
650 assert( nSize0 >= 3 );
651 nSteps = (1 << (nSize0 - 3));
652 for ( i = 0; i < nStr; i += nSteps )
653 {
654 for ( k = 0; k < nSteps; k++ )
655 if ( ((unsigned)pStr[i+k] & 0xFF) != 0x00 )
656 break;
657 if ( k == nSteps )
658 break;
659 for ( k = 0; k < nSteps; k++ )
660 if ( ((unsigned)pStr[i+k] & 0xFF) != 0xFF )
661 break;
662 if ( k == nSteps )
663 break;
664 }
665 assert( i <= nStr );
666 return (int)( i == nStr );
667}
668
680void Abs_RpmPerformMark( Gia_Man_t * p, int nCutMax, int fVerbose, int fVeryVerbose )
681{
682 Vec_Int_t * vPis, * vAnds, * vDoms;
683 Vec_Int_t * vSupp, * vSupp1, * vSupp2;
684 Gia_Obj_t * pObj;
685 word * pTruth;
686 int Iter, i, nSize0, nNodes;
687 int fHasConst, fChanges = 1;
688 Gia_ManCreateRefs( p );
689 Gia_ManCleanMark1( p );
690 Gia_ManForEachPi( p, pObj, i )
691 pObj->fMark1 = 1;
692 vPis = Vec_IntAlloc( 100 );
693 vAnds = Vec_IntAlloc( 100 );
694 vSupp1 = Vec_IntAlloc( 100 );
695 vSupp2 = Vec_IntAlloc( 100 );
696 for ( Iter = 0; fChanges; Iter++ )
697 {
698 fChanges = 0;
699 vDoms = Gia_ManComputePiDoms( p );
700 // count the number of PIs and internal nodes
701 if ( fVerbose || fVeryVerbose )
702 {
703 Gia_ManCountPisNodes( p, vPis, vAnds );
704 printf( "Iter %3d : ", Iter );
705 printf( "PI = %5d (%6.2f %%) ", Vec_IntSize(vPis), 100.0 * Vec_IntSize(vPis) / Gia_ManPiNum(p) );
706 printf( "And = %6d (%6.2f %%) ", Vec_IntSize(vAnds), 100.0 * Vec_IntSize(vAnds) / Gia_ManAndNum(p) );
707 printf( "Dom = %5d (%6.2f %%) ", Vec_IntSize(vDoms), 100.0 * Vec_IntSize(vDoms) / Gia_ManAndNum(p) );
708 printf( "\n" );
709 }
710// pObj = Gia_ObjFanin0( Gia_ManPo(p, 1) );
711 Gia_ManForEachObjVec( vDoms, p, pObj, i )
712 {
713 assert( !pObj->fMark1 );
714 assert( Gia_ObjRefNum( p, pObj ) > 0 );
715 // dereference root node
716 nNodes = Abs_GiaObjDeref_rec( p, pObj );
717/*
718 // compute support of full cone
719 if ( Abs_ManSupport1(p, pObj, vSupp1) > nCutMax )
720// if ( 1 )
721 {
722 // check support of MFFC
723 if ( Abs_ManSupport2(p, pObj, vSupp2) > nCutMax )
724// if ( 1 )
725 {
726 Abs_GiaObjRef_rec( p, pObj );
727 continue;
728 }
729 vSupp = vSupp2;
730// printf( "-" );
731 }
732 else
733 {
734 vSupp = vSupp1;
735// printf( "+" );
736 }
737*/
738 if ( Abs_ManSupport2(p, pObj, vSupp2) > nCutMax )
739 {
740 Abs_GiaObjRef_rec( p, pObj );
741 continue;
742 }
743 vSupp = vSupp2;
744
745 // order nodes by their ref counts
746 nSize0 = Abs_GiaSortNodes( p, vSupp );
747 assert( nSize0 > 0 && nSize0 <= nCutMax );
748 // check if truth table has const cofs
749 pTruth = Gia_ObjComputeTruthTableCut( p, pObj, vSupp );
750 if ( pTruth == NULL )
751 {
752 Abs_GiaObjRef_rec( p, pObj );
753 continue;
754 }
755 fHasConst = !Abs_GiaCheckTruth( pTruth, Vec_IntSize(vSupp), nSize0 );
756 if ( fVeryVerbose )
757 {
758 printf( "Nodes =%3d ", nNodes );
759 printf( "Size =%3d ", Vec_IntSize(vSupp) );
760 printf( "Size0 =%3d ", nSize0 );
761 printf( "%3s", fHasConst ? "yes" : "no" );
762 Abs_GiaCofPrint( pTruth, Vec_IntSize(vSupp), nSize0, fHasConst );
763 }
764 if ( fHasConst )
765 {
766 Abs_GiaObjRef_rec( p, pObj );
767 continue;
768 }
769 // pObj can be reparamed
770 pObj->fMark1 = 1;
771 fChanges = 1;
772 }
773 Vec_IntFree( vDoms );
774 }
775 // count the number of PIs and internal nodes
776 if ( fVeryVerbose )
777 {
778 Gia_ManCountPisNodes( p, vPis, vAnds );
779 printf( "Iter %3d : ", Iter );
780 printf( "PI = %5d (%6.2f %%) ", Vec_IntSize(vPis), 100.0 * Vec_IntSize(vPis) / Gia_ManPiNum(p) );
781 printf( "And = %6d (%6.2f %%) ", Vec_IntSize(vAnds), 100.0 * Vec_IntSize(vAnds) / Gia_ManAndNum(p) );
782// printf( "Dom = %5d (%6.2f %%) ", Vec_IntSize(vDoms), 100.0 * Vec_IntSize(vDoms) / Gia_ManAndNum(p) );
783 printf( "\n" );
784 }
785 // cleanup
786 Vec_IntFree( vPis );
787 Vec_IntFree( vAnds );
788 Vec_IntFree( vSupp1 );
789 Vec_IntFree( vSupp2 );
790// Gia_ManCleanMark1( p ); // this will erase markings
791 ABC_FREE( p->pRefs );
792}
793
805Gia_Man_t * Gia_ManDupRpm( Gia_Man_t * p )
806{
807 Vec_Int_t * vPis, * vAnds;
808 Gia_Man_t * pNew;
809 Gia_Obj_t * pObj;
810 int i;
811 // derive PIs and internal nodes
812 vPis = Vec_IntAlloc( 100 );
813 vAnds = Vec_IntAlloc( 100 );
814 Gia_ManCountPisNodes( p, vPis, vAnds );
815
816 // duplicate AIG
817 Gia_ManFillValue( p );
818 pNew = Gia_ManStart( Gia_ManObjNum(p) );
819 pNew->pName = Abc_UtilStrsav( p->pName );
820 pNew->pSpec = Abc_UtilStrsav( p->pSpec );
821 Gia_ManConst0(p)->Value = 0;
822 // create PIs
823 Gia_ManForEachObjVec( vPis, p, pObj, i )
824 pObj->Value = Gia_ManAppendCi(pNew);
825 // create flops
826 Gia_ManForEachRo( p, pObj, i )
827 pObj->Value = Gia_ManAppendCi( pNew );
828 // create internal nodes
829 Gia_ManForEachObjVec( vAnds, p, pObj, i )
830 pObj->Value = Gia_ManAppendAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
831 // create COs
832 Gia_ManForEachCo( p, pObj, i )
833 Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
834 Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
835
836 // cleanup
837 Vec_IntFree( vPis );
838 Vec_IntFree( vAnds );
839 return pNew;
840}
841
853Gia_Man_t * Abs_RpmPerform( Gia_Man_t * p, int nCutMax, int fVerbose, int fVeryVerbose )
854{
855 Gia_Man_t * pNew;
856// Gia_ManTestDoms( p );
857// return NULL;
858 // perform structural analysis
859 Gia_ObjComputeTruthTableStart( p, nCutMax );
860 Abs_RpmPerformMark( p, nCutMax, fVerbose, fVeryVerbose );
861 Gia_ObjComputeTruthTableStop( p );
862 // derive new AIG
863 pNew = Gia_ManDupRpm( p );
864 Gia_ManCleanMark1( p );
865 return pNew;
866}
867
871
872
873ABC_NAMESPACE_IMPL_END
874
abctime
ABC_INT64_T abctime
Definition abc_global.h:332
ABC_INFINITY
#define ABC_INFINITY
MACRO DEFINITIONS ///.
Definition abc_global.h:250
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
Gia_ManTestDoms2
void Gia_ManTestDoms2(Gia_Man_t *p)
Definition absRpm.c:190
Gia_ManCreateSupps
Vec_Wec_t * Gia_ManCreateSupps(Gia_Man_t *p, int fVerbose)
Definition absRpm.c:123
Abs_GiaCheckTruth
int Abs_GiaCheckTruth(word *pTruth, int nSize, int nSize0)
Definition absRpm.c:629
Gia_ManDomTest
void Gia_ManDomTest(Gia_Man_t *p)
Definition absRpm.c:140
Abs_RpmPerform
Gia_Man_t * Abs_RpmPerform(Gia_Man_t *p, int nCutMax, int fVerbose, int fVeryVerbose)
Definition absRpm.c:853
Abs_ManSupport2_rec
void Abs_ManSupport2_rec(Gia_Man_t *p, Gia_Obj_t *pObj, Vec_Int_t *vSupp)
Definition absRpm.c:492
Abs_RpmPerformMark
void Abs_RpmPerformMark(Gia_Man_t *p, int nCutMax, int fVerbose, int fVeryVerbose)
Definition absRpm.c:680
Gia_ManCountPisNodes_rec
void Gia_ManCountPisNodes_rec(Gia_Man_t *p, Gia_Obj_t *pObj, Vec_Int_t *vPis, Vec_Int_t *vAnds)
Definition absRpm.c:339
Gia_ManComputePiDoms
Vec_Int_t * Gia_ManComputePiDoms(Gia_Man_t *p)
Definition absRpm.c:276
Gia_ManCountFanoutlessFlops
void Gia_ManCountFanoutlessFlops(Gia_Man_t *p)
Definition absRpm.c:315
Gia_ManCountPisNodes
void Gia_ManCountPisNodes(Gia_Man_t *p, Vec_Int_t *vPis, Vec_Int_t *vAnds)
Definition absRpm.c:354
Gia_ManComputeDoms
void Gia_ManComputeDoms(Gia_Man_t *p)
Definition absRpm.c:86
Gia_ManDupRpm
Gia_Man_t * Gia_ManDupRpm(Gia_Man_t *p)
Definition absRpm.c:805
Abs_ManSupport3
int Abs_ManSupport3(Gia_Man_t *p, Gia_Obj_t *pObj, Vec_Int_t *vSupp)
Definition absRpm.c:528
Abs_GiaCofPrint
int Abs_GiaCofPrint(word *pTruth, int nSize, int nSize0, int Res)
Definition absRpm.c:594
Abs_GiaSortNodes
int Abs_GiaSortNodes(Gia_Man_t *p, Vec_Int_t *vSupp)
Definition absRpm.c:425
Gia_ManAddDom
void Gia_ManAddDom(Gia_Man_t *p, Gia_Obj_t *pObj, int iDom0)
FUNCTION DEFINITIONS ///.
Definition absRpm.c:53
Abs_ManSupport1
int Abs_ManSupport1(Gia_Man_t *p, Gia_Obj_t *pObj, Vec_Int_t *vSupp)
Definition absRpm.c:472
Abs_ManSupport1_rec
void Abs_ManSupport1_rec(Gia_Man_t *p, Gia_Obj_t *pObj, Vec_Int_t *vSupp)
Definition absRpm.c:458
Gia_ManTestDoms
void Gia_ManTestDoms(Gia_Man_t *p)
Definition absRpm.c:284
Gia_ManCollectDoms
Vec_Int_t * Gia_ManCollectDoms(Gia_Man_t *p)
Definition absRpm.c:246
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
Gia_ManForEachRo
#define Gia_ManForEachRo(p, pObj, i)
Definition gia.h:1252
Gia_ObjComputeTruthTableCut
word * Gia_ObjComputeTruthTableCut(Gia_Man_t *p, Gia_Obj_t *pObj, Vec_Int_t *vLeaves)
Definition giaTruth.c:628
Gia_NodeMffcSizeSupp
int Gia_NodeMffcSizeSupp(Gia_Man_t *p, Gia_Obj_t *pNode, Vec_Int_t *vSupp)
Definition giaUtil.c:1279
Gia_ManForEachAnd
#define Gia_ManForEachAnd(p, pObj, i)
Definition gia.h:1214
Gia_ManSetRegNum
void Gia_ManSetRegNum(Gia_Man_t *p, int nRegs)
Definition giaMan.c:764
Gia_ManForEachObjReverse
#define Gia_ManForEachObjReverse(p, pObj, i)
Definition gia.h:1206
Gia_ManForEachPi
#define Gia_ManForEachPi(p, pObj, i)
Definition gia.h:1248
Gia_ManStart
Gia_Man_t * Gia_ManStart(int nObjsMax)
FUNCTION DEFINITIONS ///.
Definition giaMan.c:57
Gia_Obj_t
struct Gia_Obj_t_ Gia_Obj_t
Definition gia.h:76
Gia_ManFillValue
void Gia_ManFillValue(Gia_Man_t *p)
Definition giaUtil.c:369
Gia_Man_t
struct Gia_Man_t_ Gia_Man_t
Definition gia.h:96
Gia_ManForEachObjVec
#define Gia_ManForEachObjVec(vVec, p, pObj, i)
Definition gia.h:1194
Gia_ObjComputeTruthTableStart
void Gia_ObjComputeTruthTableStart(Gia_Man_t *p, int nVarsMax)
Definition giaTruth.c:552
Gia_ObjComputeTruthTableStop
void Gia_ObjComputeTruthTableStop(Gia_Man_t *p)
Definition giaTruth.c:568
Gia_ManCreateRefs
void Gia_ManCreateRefs(Gia_Man_t *p)
Definition giaUtil.c:779
Gia_ManIncrementTravId
void Gia_ManIncrementTravId(Gia_Man_t *p)
Definition giaUtil.c:190
Gia_ManForEachObj
#define Gia_ManForEachObj(p, pObj, i)
MACRO DEFINITIONS ///.
Definition gia.h:1190
Gia_ManForEachCo
#define Gia_ManForEachCo(p, pObj, i)
Definition gia.h:1236
Gia_ManForEachCi
#define Gia_ManForEachCi(p, pObj, i)
Definition gia.h:1228
Gia_ManForEachCiId
#define Gia_ManForEachCiId(p, Id, i)
Definition gia.h:1230
Gia_ManCleanMark1
void Gia_ManCleanMark1(Gia_Man_t *p)
Definition giaUtil.c:313
word
unsigned __int64 word
DECLARATIONS ///.
Definition kitPerm.c:36
Gia_Man_t_::pSpec
char * pSpec
Definition gia.h:100
Gia_Man_t_::pName
char * pName
Definition gia.h:99
Gia_Obj_t_::fMark1
unsigned fMark1
Definition gia.h:86
Gia_Obj_t_::Value
unsigned Value
Definition gia.h:89
assert
#define assert(ex)
Definition util_old.h:213
memmove
char * memmove()
Vec_IntForEachEntry
#define Vec_IntForEachEntry(vVec, Entry, i)
MACRO DEFINITIONS ///.
Definition vecInt.h:54
Vec_Wec_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Wec_t_ Vec_Wec_t
INCLUDES ///.
Definition vecWec.h:42